компилятор

Т.е. там сначала оптимизируется AST (как избавленный от макросов исходный код), а потом он уже переводится в flow graph на котором делаются другие оптимизации (такие же как в gcc, но гораздо больше), и потом уже это представление переводится в представление виртуальной машины для оптимизаций следующего уровня (на этот раз меньше чем у gcc), ну и в конце происходит генерация кода для бакэнда (архетектуры).

> Т.е. там сначала оптимизируется AST (как избавленный от макросов исходный код)

И что, dead code elimination и tail recursion делаются на AST? O_o

И что, dead code elimination и tail recursion делаются на AST? O_o

Нет, конечно, это делается на довольно поздней стадии (в середине стадии IR2). С другой стороны количество преобразований AST (source transformation) тоже очень велико (где-то 5-10% от всего компилера, может поменьше).

> С другой стороны количество преобразований AST (source transformation) тоже очень велико

И каков примерно их состав?

И каков примерно их состав?

Например, приведение произвольных арифметических форм, - арифметические выражения от переменных и констант, - вместо множества инструкций (это ещё не учитывая что там могут быть большие числа) мы получаем 0 инструкций (если в выражениях только константы), либо существенно меньше инструкций (если мы собираем константы и переменные исходя из транзитивности выражений, либо из каких-то других свойств позволяющих делать упрощения выражений).

Плюс разные функции от последовательностей (map, ФВП, фукции от векторов) сводятся к своим частным случаям - в зависимости от того что известно и типах элементов/переменных.

Если обобщать, то суть в том что можно определить произвольное преобразование AST -> F(AST) - анализируя исходный код (и сам по себе и его мета-информацию - типы) мы отдаём другой исходный код, с которым и будет работать компилятор.

к сведению любопытствующих: Были такие любопытные книжки в советское ещё время «теория схем программ», и (если память не изменяет) «автоматические преобразования и оптимизация программ» - там очень хорошо были расписаны высокоуровневые оптимизирующие преобразования над графами программ (фактически над AST), вплоть до основ оптимизации для паралелльных вычислений.

p.s. сильна была советская наука

Как оказалось получить компилятор под любую платформу, поддерживаемую gcc достаточно просто.

Можно построить промежуточный код(gimple) и отправить его на дальнейшие оптимизации(это как приятный бонус), а главное на «reg allocations» gcc. Все собственные оптимизации можно проводить как на низком уровне(маш. кодов), но между тем абстрагированном от знания конкретной архитектуры, так собственно и при парсинге выражений реализуемого языка. Так же можно расширять gcc, что особенно не нужно. Опять же всё это даёт атоматическое обновление низкоуровневых оптимизаций в будущем.

Т.е. как прослойка между абстрагированными маш.кодами и маш.кодами определённой машины gcc подходит идеально.

Заниматься генерацией gimple-кода несложно на любом ЯВУ и пожалуй нет смысла возлагать это на gcc(генерируя С код) с его AST(без AST можно в общем обойтись).

Если я что-то понял не правильно прошу поправить

Гг

Можно построить промежуточный код(gimple)

Как? Ты уже выяснил формат? Он стабилен? %)

и отправить его на дальнейшие оптимизации

Как? :D

Как? Ты уже выяснил формат? Он стабилен? %)

к примеру будем строить «Lowering Gimple» - построить просто, а CFG он сам уже построит. Вот только мне не очень понятно как gimple там память раздаёт, вроде выделяется последовательный кусок просто?

Как? :D

сейчас точно не приведу названия файлов, но каждом шаге в «Importan Phases» gcc пишет представление того, с чем он работает на этом шаге, в файл. Думаю наверняка можно скормить ему эти представления, ведь они самодостаточны

%)

блин, я не понимаю, то ли это издевательская улыбка, то ли одобряющая :)

> блин, я не понимаю, то ли это издевательская улыбка, то ли одобряющая :)

Офигевшая. Я думаю, у тебя не получится сгенерировать GIMPLE (ну разве что ты сам напишешь инструменты для этого), и, даже если ты его сгенерируешь, не получится скормить твой GIMPLE в GCC (это просто не предусмотрено).

И, даже если я ошибаюсь по обоим пунктам, какой тебе профит от GIMPLE по сравнению с Си?

сгенерировать GIMPLE

в СИКПе рассматривается код, который практически это и делает. Но тут ещё проще - не надо биндить переменные в регистры.

сам напишешь инструменты для этого

это и есть работа «моего» компилятора, gcc используется в основном для работы с RTL. я не говорю, что прямо бросаюсь это делать, пока мне просто интересно.

профит от GIMPLE по сравнению с Си

получается, что пишется компилятор кода в платформо-независимый асм + халявная оптимизация от gcc + возможность внедрения даже в эту халявную оптимизацию(pass)

переменные в регистры

к регистрам

>Почему тогда так много архитектурно зависимых компиллеров?

потому что С тоже может быть скомпилирован по разному, с учетом железа

>> сгенерировать GIMPLE

в СИКПе рассматривается код, который практически это и делает

Ты просто не понимаешь, о чем я.

Почему бы просто не взять LLVM? В отличии от gcc у него есть стабильный интерфейс для разработчиков языков (куча языков использует его для генерации кода).

К слову, Scheme->LLVM там тоже есть (правда немного страшный), для любителя SICP должно быть самое то ;)

Ну над графами это немного другое, почти все классические компиляторы так поступают - делают Code -> AST -> Flow Graph и оптимизируют на последнем. А вот делать сначала оптимизации на AST это фактически макро-подобные оптимизации и используется они только в CL (ну и ещё вроде как в C++ (templates))

может вы мне объясните зачем нужен AST, тем более если он не используется для каких-то хитрых оптимизаций? Почему просто рекурсивно не обрабатывать выражение за выражением? В чём выгода от раскидывания выражения по иерархии?

Не вполне понимаю вопроса, я бы спросил - «почему AST может быть не нужен»? AST это «исходный код с которым можно что-то делать» (не просто текст).

В общем:

Почему просто рекурсивно не обрабатывать выражение за выражением?

Оверхед по количеству генерируемых инструкций. Не факт, что низлежащий компилятор (gcc или llvm) с ним справится.

В чём выгода от раскидывания выражения по иерархии?

Нелокальные оптимизации.

Чуть подробнее:

К примеру, пусть у нас есть такой код

function foo (a b c)
  let x = 1
      y = 2
      z = 3
    a + x + b + y + c + z

apply foo 1 2 3
=> 12

Он вводит функциональный объект с помощью которого можно производить вычисления. Наша задача - преобразовать source code в target code, например - код выше в код ассемблерных инструкций x86. Что вы предлагаете? Как это - «почему просто рекурсивно не обрабатывать выражение за выражением?» - это как в SICP?

Очевидно, нужно провести код через ряд фаз (phases). Возможные подходы:

1.1) Первая фаза - сложный reader.

С кодом выше трудно что-то делать, это просто текст. Но у этого текста есть грамматика - нечто что придаёт ему структуру, поэтому естественно что задача читателя - отыскать и построить эту структуру. Со времён Хомского и МакКарти ещё принято брать за грамматику языков контекстно-свободные формы - в этом случае мы можем найти однозначное преобразование текста программы в синтаксическое дерево - структура теста представляется деревом.

Т.е. для нашего языка мы пишем определения грамматик (в форме Хомского или в BNF), и определяем преобразование:

reader : Text ->(bnf) AST ;; отображение зависит от принятого множества продукций

Если интерпретировать это с точки зрения языка Си, то Text это поток (FILE) или строка (char*), AST это просто РТД, А reader это функция:

typedef char* Text;

typedef struct AST_node {
  // whatever;
} AST_node;

typedef struct AST {
  AST_node   *node;
  struct AST *first;
  struct AST *rest;
} AST;

AST reader (Text text) {
  /*
   * a.k.a. parser there
   */
}

1.2) Не трудно догадаться, что предыдущий пункт может быть выброшен - полученное AST может иметь текстовую запись вроде

(function foo (a b c)
  (let ((x 1) (y 2) (z 3))
    (+ a x b y c z)))

(apply foo 1 2 3)

reader остаётся, но он не требует правил грамматики и может быть написан как довольно тривиальная процедура.

К слову, следующий код также будет иметь регулярный синтаксис, но пресловутых скобочек в нём нет:

function foo
         a b c
  let
      x 1
      y 2
      z 3
    + a x b y c z

apply foo 1 2 3

2.1) Вот теперь есть вложенная структура AST в памяти (полученная с помощью 1.1 или 1.2 - неважно, и, кстати, если не нравится аббревиатура AST и у вас source это lisp, то можно так и говорить «вот есть лисп-код»)). Что дальше? Можно конечно сделать как в SICP - написать функцию compiler для рекурсивной обработки AST и набор emmit-оров для каждого примитива. Если совместить с 1.2 то получится очень простой транслятор. Но если рассмотреть подробнее:

;; При рекурсивном обходе будут найдены примитивы:

function - для этого примитива мы перечисляем пролог/эпилог функции, выделяем кадр стека.
let - для этого мы выделяем объект-локальное-окружение - фактически это аллокация памяти и запоминание адресов для каждой переменной.
+ - генерируем 5 инструкций ADD.
apply - сохраняем регистры, помещаем аргументы в стек и генерируем CALL или JMP.

Вроде ничего, но даже на таком простом примере можно видеть, какой оверхед это несёт. В SICP есть комментарий про это - мол, в реальных компиляторах мы бы так конечно не делали.

2.2) Какая альтернатива? Вообще можно оставить всё как 2.1 и пытаться привязать peephole оптимизатор но это значит устранять проблемы вместо устранения причин их проявления - причины раздутости кода после 2.1 находятся в том как работает сам 2.1.

2.3) Пусть с каждым примитивом связана AST трансформация:

source-transform(primitive1) : AST -> AST
source-transform(primitive2) : AST -> AST
...

грубо говоря это макросы (макросы на AST как в лиспах). Например мы можем определить

(+ &rest args) = `(+ ,@(reduce + (constants-from args)) ,@(variables-from args))

В этом случае:

(+ a 1 b 2 c 3) -> (+ 6 a b c)
5 инструкций -> 3 инструкции

Однако для того примера который мы рассматриваем это ничего не даст - вместо 1 2 3 у нас там x=1 y=2 z=3. source-transform работает локально - только с тем AST что был ему отдан. Поэтому второй вопрос - как нам сделать оптимизации на AST учитывая контексты и прочие нелокальные условия? На самом деле решения тут нет - нужно пойти дальше.

3) Intermediate Representation или IR это не просто AST (синтаксическое дерево), это ASeG так сказать - семантический граф. В то время как алгоритмы на дереве по большей части хороши для локальных преобразований, алгоритмы на графах хороши для нелокальных - элементы кода могут ссылаться друг на друга самым различным образом.

first-ir-processing : AST -> ICR

Ещё раз почему это нужно: AST представляет только синтаксис, в то время как flow-graph или Implicit Continuation Representation (ICR) представляет семантику.

На нашем примере:

function_foo:
  function_environment:
    a, b, c
  block_foo:
    block_let:
      local-environment
        x = 1; y = 2; z = 3;
      return_foo:
        function-call
          + a x b y c z

Путём анализа этот граф сводится к

function_foo:
  function_environment:
    a, b, c
  block_foo:
    return_foo:
      function-call
        + 6 a b c

И мы избавляемся от аллокации окружения - тоже лишние инструкции.

4) Ну и другое IR это Virtual Machine Representation (VMR) - последовательный набор инструкций виртуальной-машины/целевой-архитектуры. Тут происходит реальная редукция графа - каждый элемент транслируется в последовательность инструкций.

5) Возможно инструкции VMR не вполне соответствуют инструкциям целевого кода - являются виртуальными инструкциями, тогда нужно их ещё транслировать в реальные инструкции.

6) Набор инструкций нужно как-то преобразовывать в машинный код или в байт код, поэтому нужен ещё ассемблер.

7) И последнее - нужно как-то преобразовывать адреса и, возможно, разделять код - т.е. нужен линкер или дампер.

Выводы:

Reader строит AST, либо сложным путём из текста с нерегулярным синтаксисом, либо простым из теста с синтаксисом отражающим этот AST. В каком-то смысле читатель «расставляет скобочки».

Трансформациями AST мы можем достичь некоторых упрощений, но с обязательным условием - *локальных* упрощений, т.е. упрощения кода без учёта его контекста. Мы можем упрости какую-нибудь форму, например (+ 1 2 3) = 6, но не можем упростить (let ((a 1) (b 2) (c 3)) (+ a b c)) = 6.

Оптимизации на flow graph служат для того, чтобы при оптимизации X можно было учитывать контекст X, или даже какой-то другой Y.

reader                        : Text ->(bnf) AST
source-transforms(primitives) : AST -> AST
first-ir-processing           : AST -> ICR
second-ir-processing          : ICR -> VMR
assembler-processing          : VMR -> ASM
dumper/linker-processing      : VMR, ASM -> target-code

Огромное спасибо, очень доходчиво написано, я бы вообще выделил это в статью куда нибудь на lisper.ru.

Открылась тайна почему же я не мог понять зачем строить AST - я думал о lisp синтаксисе, который и так не требует дополнительных преобразований в AST. А ф-ции, которые я называл ф-циями оптимизации над выражениями лиспа, по сути уже работают с AST :)

ICR и в самом деле удобен, в том числе сразу приходит в голову отсеивать unreachable код и вообще всякие нездоровые переходы по графу.

second-ir-processing : ICR -> VMR assembler-processing : VMR -> ASM dumper/linker-processing : VMR, ASM -> target-code

В качесте VMR берём ir какой нибудь кроссплатформенной штуки, типа LLVM или gcc и последние 2 преобразования получаем в подарок и для всех систем, для который портированна выбранная штука :)

вы где нибудь пишете, там в блоге например?

Как это - «почему просто рекурсивно не обрабатывать выражение за выражением?» - это как в SICP?

да, если выражение сложное(имеет вложенные выражения), то рекурсивно разбирать их. то же дерево

да, если выражение сложное(имеет вложенные выражения), то рекурсивно разбирать их. то же дерево

Значит я правильно понял - про это выше и написал (2.1). Хотя по идеи в этом нет чего-то сверх плохого (так чтобы из-за выбора такой стратегии совместно с качественным бакендом случился большой fail по производительности), но всё же - лучше пилить существующие реализации чем делать заведомо худший вариант ;) Тот же gambit-c вроде как просто подходит ко всем вопросам - так и генерирует си-код. Ещё в книжке L.I.S.P (Lisp in a small pices) есть про это, gambit (насколько я помню) по ней сначала и делался.

я бы вообще выделил это в статью куда нибудь на lisper.ru.

Ну есть гораздо более подробные статьи на английском - это просто краткая выжимка (мне тоже полезно - кратко расписать что знаю).

Можно взять хотя бы:

http://sbcl-internals.cliki.net/index

и

http://insidelisp.blogspot.com/

В качесте VMR берём ir какой нибудь кроссплатформенной штуки, типа LLVM

Для SBCL делали полусырой LLVM бакенд, хотя, в данном случае, это не очень здорово так как отбрасывается куча наработок из самого SBCL. Вот, ну и ещё ради пиара - у SBCL есть мульти-архетектурный VMR ;) (но если задумать его использовать как stand-alone - само собой придётся много пилить).

З.Ы. не, не пишу (пока) в блоге.

подробные статьи на английском

после такого краткого и понятного экскурса можно перейти и к более подробному изучению, к примеру «sbcl internals»

спасибо всем за информацию :)