Книга «Основы компиляции: инкрементный подход»06.02.2024 18:00

Привет, Хаброжители!

Компиляторы традиционно считаются одной из самых трудных для понимания и изучения тем. Обычно в книгах каждая глава посвящена отдельному проходу компилятора. Но такая структура не позволяет раскрыть, как языковые средства влияют на решения, принимаемые при проектировании компилятора.

Вместо этого в «Основах компиляции» выбран инкрементный подход: компилятор совершенствуется последовательно, и читатель может написать весь код самостоятельно. Книга помогает создать собственный компилятор для небольшого, но достаточно мощного языка программирования, постепенно, шаг за шагом вводя все более сложные языковые средства.

Джереми Сик объясняет важнейшие концепции, алгоритмы и структуры данных, лежащие в основе современных компиляторов, и закладывает основу для изучения более сложных тем. Это краткое, но доступное руководство уже давно используют студенты и профессионалы.

ЦИКЛЫ И АНАЛИЗ ПОТОКОВ ДАННЫХ

В этой главе рассматриваются две отличительные функциональные возможности императивного программирования: циклы и присваивания локальным переменным. Следующий пример демонстрирует эти новые функции на примере вычисления суммы первых пяти положительных целых чисел:

(let ([sum 0])
  (let ([i 5])
    (begin
       (while (> i 0)
         (begin
            (set! sum (+ sum i))
            (set! i (- i 1))))
       sum)))

Цикл while состоит из условия и тела. Тело вычисляется многократно, пока условие остается истинным. Конструкция set! состоит из переменной и выражения в правой части. set! обновляет значение переменной значением правой части. Циклы while и set! существуют прежде всего ради побочных эффектов, поэтому они не генерируют значимый итоговый результат. Их результатом является значение #. Выражение (void) используется для явного создания значения # и имеет тип Void. Значение # может передаваться в программе LWhile так же, как все остальные значения, и его можно проверить на равенство с другим значением #. Однако в LWhile нет других операций, специ­фичных для значения #. С другой стороны, Racket определяет предикат void?, который возвращает #t при применении к # и #f в противном случае. С добавлением функций, производящих побочные эффекты, таких как циклы while и set!, желательно включить языковое средство для упорядочения побочных эффектов: выражение begin. Оно состоит из одного или нескольких подвыражений, вычисляемых слева направо.

Язык LWhile

На илл. 5.1 приведено описание конкретного синтаксиса LWhile, а на илл. 5.2 — определение его абстрактного синтаксиса. Определительный интерпретатор LWhile приведен на илл. 5.3. В нем появились новые условия для SetBang, WhileLoop, Begin и Void, а еще мы вносим изменения в условия Var и Let, относящиеся к переменным. Чтобы поддерживать присваивание переменным и сделать их срок жизни неопределенным (см. второй пример в разделе 8.2), мы упаковываем значение, связанное с каждой переменной (в Let). Условие для Var распаковывает значение.

Теперь рассмотрим новые случаи. Для SetBang мы находим в окружении переменную, которая должна получить новое значение, после чего при помощи set-box! обновляем ее результатом вычисления правой части. Итоговое значение SetBang равно #. Для цикла WhileLoop мы многократно (1) вычисляем условие, и если результат равен true, (2) вычисляем тело. Значение результата цикла while также равно #. Выражение (Begin es body) вычисляет подвыражения es ради использования их эффектов, после чего вычисляет и возвращает результат из тела. Выражение (Void) производит значение #.

Определение модуля проверки типов для LWhite показано на илл. 5.4. Для проверки типов выражения SetBang необходимо, чтобы типы переменной и правой части соответствовали друг другу. Результат имеет тип Void. Для while условие должно иметь тип Boolean, а результат — тип Void. Для Begin типом результата должен быть тип последнего подвыражения.

На первый взгляд может показаться, что эти языковые средства тривиально преобразуются в x86, потому что промежуточный язык CIf уже поддерживает все необходимые функции: присваивание, goto, условные переходы и упорядочение. Однако затруднения все же возникают и будут рассмотрены в следующем разделе. После этого будут описаны изменения, которые необходимо внести в существующие проходы.

Циклическое выполнение и анализ потоков данных

До сих пор программы, сгенерированные в explicate_control, были только ацикличными. Однако каждый вызов while создает цикл в программе. Важно ли это?

Оказывается, да. Вспомните, что для распределения регистров компилятор выполняет анализ живых переменных, чтобы определить, какие переменные могут храниться в одном регистре. Для этого мы анализировали граф в обратном топологическом порядке (раздел 4.10.1), но топологический порядок нормально определен только для ациклических графов.

Вернемся к примеру с вычислением суммы первых пяти положительных чисел. Ниже приведена программа после выбора инструкций, но до распределения регистров.

Вспомните, что анализ живых переменных работает в обратном порядке, начиная с конца каждой функции. В этом примере можно начать с block8, поскольку мы знаем, что в начале эпилога активны только rax и rsp. Таким образом, живым предмножеством для block8 является {rsp, sum}. Затем можно попытаться проанализировать block5 или block7, но block5 переходит к block7 и наоборот; ситуация кажется тупиковой.

Что делать? Можно вычислить нижнее приближение каждого живого пред-множества, начиная с пустых живых постмножеств. Нижнее приближение (underapproximation) означает, что множество содержит только переменные, живые при некотором выполнении программы, но некоторые живые переменные в нем могут отсутствовать. Затем нижнее приближение каждого блока можно улучшить (1) обновлением живого постмножества каждого блока с использованием приближенных живых предмножеств из других блоков и (2) повторным выполнением анализа живых переменных для каждого блока. При итеративном повторении этого процесса нижние приближения со временем оказываются оправданными. Этот процесс итеративного анализа графа управляющей логики, применимый ко многим задачам статического анализа, известен под названием анализа потоков данных. Его впервые предложил Килделл (Kildall, 1973) в своей докторской диссертации в Вашингтонском университете.

Применим этот подход к ранее представленному примеру. Изначальным живым постмножеством для каждого блока становится пустое множество. Пусть m0 — следующее отображение имен меток на наборы локаций (переменных и регистров):

mainstart: {}, block5: {}, block7: {}, block8: {}

Используя описанные выше приближения живых предмножеств, мы определяем живое постмножество для каждого блока, а затем проводим анализ живых переменных для каждого блока. В результате получаем следующее приближение m1 для живых предмножеств:

mainstart: {}, block5: {i}, block7: {i, sum}, block8: {rsp, sum}

На втором круге живым постмножеством для mainstart является текущее живое предмножество для block5, то есть {i}. Таким образом, анализ живых переменных для mainstart вычисляет пустое множество. Живое постмножество для block5 представляет собой объединение живых предмножеств для block7 и block8, то есть {i, rsp, sum}. Анализ живых переменных для block5 вычисляет {i, rsp, sum}. Живое постмножество для block7 является живым пред-множеством для block5 (из предыдущей итерации), то есть {i}. После анализа живых переменных для block7 остается множество {i, sum}. Вместе они дают следующее приближение m2 для живых предмножеств:

mainstart: {}, block5: {i, rsp, sum}, block7: {i, sum}, block8: {rsp, sum}

В предыдущей итерации изменения затронули только block5, поэтому мы можем ограничиться mainstart и block7 — двумя блоками, переходящими к block5. В результате живые предмножества для mainstart и block7 обновляются с добавлением rsp, и это дает следующее приближение m3:

mainstart: {rsp}, block5: {i,rsp,sum}, block7: {i,rsp,sum}, block8: {rsp,sum}

Так как блок block7 изменился, мы анализируем block5 еще раз, но его живым предмножеством остается {i, rsp, sum}. В этот момент приближения сходятся, так что m3 является решением.

Итеративный процесс гарантированно сходится к решению; это доказано теоремой Клини о неподвижной точке — общей теореме из области функций на решетках (Kleene, 1952). Упрощенно говоря, решеткой (lattice) называется любой набор элементов, для которого определено частичное упорядочение его элементов наименьший (нижний) элемент ⊥ и оператор соединения ⊔. Когда два элемента упорядочены mi mj, это означает, что mj содержит по крайней мере столько же информации, что и mi, так что mj может рассматриваться как «лучшее или равное» приближение по отношению к mi. Нижний элемент ⊥ представляет полное отсутствие информации, то есть худшее приближение. Оператор соединения получает два элемента решетки и объединяет их информацию; другими словами, он генерирует наименьшую верхнюю границу двух элементов.

Анализ потоков данных обычно включает две решетки: одна представляет абстрактные состояния, а другая накапливает абстрактные состояния всех блоков в графе потока управления. Для анализа живых переменных абстрактное состояние представляет собой множество локаций. При формировании решетки L ее элементы задаются как множества локаций, упорядочение — как принадлежность к множеству (⊆), нижняя грань — как пустое множество, а оператор соединения — как объединение множеств. При формировании второй решетки M ее элементы представляют собой отображения меток блоков на множества локаций (элементов L). Отображения упорядочиваются по точкам с использованием упорядочения L. Таким образом, для любых двух заданных отображений mi и mj, mi mj, когда mi (ℓ) ⊆ mj (ℓ) для каждой метки блока ℓ в программе. Нижним элементом M становится отображение ⊥M, которое направляет каждую метку в пустое множество; другими словами,

Одну итерацию анализа живых переменных, примененную ко всей программе,
можно рассматривать как функцию f на решетке M. Функция получает отображение на входе и вычисляет новое отображение.

Теперь подумайте, как должно выглядеть итоговое решение ms. Если выполнить анализ живых переменных с решением ms на входе, на выходе снова должно получиться решение ms. Иначе говоря, решение должно быть неподвижной точкой функции f.

Более того, решение должно включать только те локации, которые обязательно должны в нем присутствовать по результатам проведения анализа живых переменных программы, так что решение должно быть наименьшей неподвижной точкой.

Теорема Клини о неподвижной точке утверждает, что если функция f монотонна (при улучшении ввода улучшается вывод), то наименьшая неподвижная точка f является наименьшей верхней границей восходящей цепи Клини, для построения которой следует начать с ⊥ и выполнять итерации f по следующей схеме:

Если решетка содержит только восходящие цепи конечной длины, то каждая цепь Клини достигает верхнего предела в некоторой неподвижной точке через некоторое количество итераций f.

Анализ живых переменных действительно является монотонной функцией, а решетка M имеет восходящие цепи конечной длины, поскольку количество переменных и блоков в программе ограниченно. Это гарантирует, что итеративное применение анализа живых переменных ко всем блокам в программе в конечном итоге приведет к наименьшей неподвижной точке.

Рассмотрим анализ потоков данных в общем и алгоритм обобщенного списка задач (илл. 5.5). Алгоритм получает четыре параметра: граф потока управления G; функцию transfer, применяющую анализ к одному блоку; операторы bottom и join для решетки абстрактных состояний. Функция analyze_dataflow формулируется как прямой анализ потоков данных, то есть входные данные функции transfer поступают от узлов-предшественников в графе потока управления. Однако анализ живых переменных представляет собой обратный анализ потоков данных, поэтому в данном случае функции analyze_dataflow необходимо передать транспонированный граф потока управления.

Алгоритм начинается с создания нижнего отображения, представленного в форме хеш-таблицы. Затем все узлы графа потока управления заносятся в список задач (очередь). Алгоритм повторяет цикл while, пока в списке задач остаются элементы. При каждой итерации узел извлекается из списка и обрабатывается. Входные данные узла вычисляются объединением абстрактных состояний всех узлов-предшественников. Затем функция transfer применяется для получения выходного абстрактного состояния. Если вывод отличается от предыдущего состояния этого блока, отображение для блока обновляется, а узлы-последователи заносятся в список задач.

Изменяемые переменные и удаление составных операндов

Между проходом remove_complex_operands, добавлением set! и принятым в Racket порядком вычисления слева направо существует неочевидное взаимодействие. Возьмем следующий пример:

(let ([x 2])
  (+ x (begin (set! x 40) x)))

Результат программы равен 42, потому что при первом чтении из x будет получен результат 2, а при втором — 40. Но при небрежном применении прохода remove_complex_operands к этому примеру вы получите следующую программу с результатом 80!

(let ([x 2])
  (let ([tmp (begin (set! x 40) x)])
    (+ x tmp)))

Проблема в том, что с изменяемыми переменными важен порядок чтения и записи, а проход remove_complex_operands переместил set! так, что операция выполняется до первого чтения x.

Мы рекомендуем решать эту задачу специальной обработкой чтения из изменяемых переменных (то есть переменных, находящихся в левой части set!). Каждая операция чтения из изменяемой переменной помечается формой get! (GetBang в абстрактном синтаксисе) для обозначения того, что операция чтения может давать разные результаты в разные моменты времени. Применим эту идею к следующей вариации, которая также включает неизменяемую переменную:

(let ([x 2])
  (let ([y 0])
    (+ y (+ x (begin (set! x 40) x)))))

Сначала мы анализируем программу, чтобы узнать, что переменная x может изменяться, а переменная y не может. Затем программа преобразуется с заменой каждого вхождения x на (get! x):

(let ([x 2])
  (let ([y 0])
    (+ y (+ (get! x) (begin (set! x 40) (get! x))))))

Имея четкое разграничение операций чтения из изменяемых и неизменяемых переменных, мы можем применить проход remove_complex_operands, в котором операции чтения из неизменяемых переменных классифицируются как атомарные выражения, а операции чтения из изменяемых переменных — как составные. Таким образом, remove_complex_operands дает следующую программу:

(let ([x 2])
  (let ([y 0])
    (+ y (let ([t1 (get! x)])
           (let ([t2 (begin (set! x 40) (get! x))])
             (+ t1 t2))))))

Временная переменная t1 получает значение x до set!, то есть 2. Временная переменная t2 получает значение x после set!, то есть 40. Мы не генерируем временную переменную для вхождения y, потому что это неизменяемая переменная. Следует по возможности избегать создания лишних временных переменных, потому что они только увеличивают количество переменных, а это повышает вероятность того, что какие-то из них придется хранить в стеке. Результат программы равен 42 — как и до применения remove_complex_operands.

Описанный подход требует лишь небольшого изменения remove_complex_operands для поддержки get!… С другой стороны, он требует и нового прохода с именем uncover-get!, который будет описан в разделе 5.4.

Заодно следует отметить, что это проблемное взаимодействие между set! и проходом remove_complex_operands относится к специфике языка Racket, но не его предшественника Scheme. Принципиальная разница между ними в том, что в Scheme однозначно не задан порядок вычисления аргументов оператора или вызова функции (Sperber et al., 2009). Таким образом, компилятор Scheme может выбрать любое упорядочение: для программы-примера результаты и 42, и 80 будут верны. Интересно заметить, что реализация Racket построена на базе компилятора Scheme Chez (Dybvig, 2006) и для преобразования Racket в Scheme (Flatt et al., 2019) используется подход, сходный с описанным в этом разделе (с дополнительными привязками let для управления порядком вычисления).

Разобравшись с трудностями, которые создает поддержка присваивания и циклов, обратимся к отдельным проходам компиляции.

Открытие get!

Цель этого прохода — пометить использование изменяемых переменных, чтобы проход remove_complex_operands обрабатывал их как составные выражения и сохранял их порядок относительно побочных эффектов в других операндах. Таким образом, первым шагом должен стать поиск всех изменяемых переменных. Мы рекомендуем создать для этой цели вспомогательную функцию с именем collect-set!, которая рекурсивно обходит выражения и возвращает множество всех переменных, встречающихся в левой части set!… Ниже приведен фрагмент ее реализации.

(define (collect-set! e)
  (match e
    [(Var x) (set)]
    [(Int n) (set)]
    [(Let x rhs body)
      (set-union (collect-set! rhs) (collect-set! body))]
    [(SetBang var rhs)
      (set-union (set var) (collect-set! rhs))]
    ...))

Размещение этого прохода после uniquify позволит не беспокоиться о замещении переменных, а логика Let останется простой, как в этом фрагменте.

Вторым шагом должна стать пометка вхождений изменяемых переменных новым узлом AST GetBang (get! в конкретном синтаксисе). Ниже приведен фрагмент функции uncover-get!-exp, которая получает два параметра: множество изменяемых переменных set!-vars и обрабатываемое выражение e. Секция (Var x) заменяет его (GetBang x), если это изменяемая переменная, или оставляет без изменений в противном случае.

(define ((uncover-get!-exp set!-vars) e)
  (match e
    [(Var x)
      (if (set-member? set!-vars x)
        (GetBang x)
        (Var x))]
    ...))

Затем определите функцию uncover-get! для обработки всей программы. Она должна использовать collect-set! для получения множества изменяемых переменных, а затем uncover-get!-exp для замены их вхождений на GetBang.

Удаление составных операндов

Новые языковые формы get!, set!, begin и while являются составными выражениями. Для подвыражений set!, begin и while допустимо быть составными. На илл. 5.6 определяется выходной язык этого прохода LmonWhile.

Как обычно, при появлении составного выражения в позиции грамматики, которая должна быть атомарной (например, в аргументе примитивного оператора), необходимо ввести временную переменную и связать ее с составным выражением. Этот подход в том же виде применяется и при обработке новых языковых форм. Например, в следующем коде два выражения begin присутствуют как аргументы оператора »+». Затем приводится вывод rco_exp, в котором выражения begin связываются с временными переменными. Вспомните, что выражения let в LmonWhile могут содержать произвольные выражения в правой части, а следовательно, здесь может размещаться и begin.

Проход explicate_control и

Напомним, что в проходе explicate_control мы определяем вспомогательную функцию для каждой разновидности позиций в программе. В языке целых чисел и переменных LVar нам понадобились присваивания и хвостовые позиции. Выражения if языка LIf добавили позиции предикатов. Для LWhile выражение begin добавило еще одну разновидность позиций: позиции эффектов. Подвыражения внутри begin, кроме последнего, вычисляются только ради их эффектов. Их итоговые значения теряются. Если учесть это обстоятельство, мы сможем сгенерировать более эффективный код.

Выходным языком explicate_control является язык (илл. 5.7), почти идентичный CIf. Существует всего пара синтаксических различий — добавление (Void) и возможность использования read как команды. Принципиальное отличие программ, сгенерированных версиями explicate_control из главы 4 и этой главы: графы потока управления во втором случае могут содержать циклы.

Новая вспомогательная функция explicate_effect получает выражение (в позиции эффекта) и код продолжения. Функция возвращает хвост tail, включающий сгенерированный код для входного выражения и следующего за ним продолжения. Если выражение очевидно является чистым (то есть никогда не порождает побочных эффектов), его можно удалить, так что результатом будет только продолжение. Условие для выражений (WhileLoop cnd body) представляет интерес; сгенерированный код представлен на следующей диаграмме:

Сначала для вершины цикла создается новая метка loop. Затем тело body обрабатывается рекурсивно (в позиции эффекта) с переходом goto к loop в качестве продолжения, в результате создается тело body′. Условие cnd (в позиции предиката) обрабатывается с body′ как ветвью then и блоком продолжения как ветвью else. Результат добавляется в словарь basic-blocks с меткой loop. Результат для всего цикла while представляет собой переход goto к метке loop.

Вспомогательные функции для позиций хвостов, присваиваний и предикатов необходимо обновить. Три новые языковые формы, while, set! и begin, могут присутствовать в позициях присваиваний и хвостов. Только begin может присутствовать в позициях предикатов; две другие имеют тип результата Void.

Проход select_instructions

Чтобы проход select_instructions обрабатывал изменения в, достаточно внести два небольших изменения. Во-первых, для обработки (Void) достаточно преобразовать его в 0. Во-вторых, read может присутствовать как автономная команда (вместо появления в правой части команды присваивания). Код генерируется практически так же, как для присваивания; просто опустите инструкцию для перемещения результата в левую часть.

Распределение регистров

Как обсуждалось в разделе 5.2, присутствие циклов в LWhile означает, что циклы могут содержаться в графах потока управления; это усложняет анализ живых переменных, необходимый для распределения регистров. Мы рекомендуем использовать для анализа живых переменных обобщенную функцию analyze_dataflow, представленную в конце раздела 5.2, с заменой кода uncover_live, обрабатывающего базовые блоки в топологическом порядке (раздел 4.10.1).

Функция analyze_dataflow получает четыре параметра.

1. В первом параметре G должен передаваться транспонированный граф потока управления.
2. Во втором параметре transfer должна передаваться функция, применяющая анализ живых переменных к базовому блоку. Функция получает два параметра: метку анализируемого блока и живое постмножество для этого блока. Функция transfer должна возвращать живое предмножество для блока. Кроме того, в качестве побочного эффекта она должна обновлять информацию блока данными живых переменных для каждой инструкции. Чтобы реализовать функцию transfer, необходимо иметь возможность повторно использовать уже существующий код для анализа базовых блоков.
3. В третьем и четвертом параметрах analyze_dataflow передаются нижняя грань (bottom) и объединение (join) для решетки абстрактных состояний, то есть множеств локаций. Для анализа живых переменных нижняя грань изначально является пустым множеством, а оператор объединения — объединением множеств.

На илл. 5.8 представлена схема всех проходов, необходимых для компиляции LWhile.

Более подробно с книгой можно ознакомиться на сайте издательства:

» Оглавление
» Отрывок

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Основы компиляции

© Habrahabr.ru