На каком этапе я должен реализовать оптимизацию хвостового вызова для моего компилятора

Question

Я написал небольшой компилятор в Racket для схемного языка. Теперь я хочу реализовать TCO для моего компилятора.

Моя идея: мне нужно определить хвостовые звонки, прежде чем преобразовывать их в промежуточное представление. Но из этого page кажется, что TCO обычно выполняется на уровне сборки, меняя call на jmp. Я немного застрял здесь.

Любые предложения будут оценены.

EDIT: Моя цель - код сборки x86. ИК-я использую три адресных кода.

И вот 12 проходит для моего компилятора, то Flatten прохода, где я преобразовать исходный код в ИК

(define test-passes 
(list 
`("uniquify"    ,(uniquify '())         ,interp-scheme) 
`("reveal-functions"  ,(reveal-functions '())       ,interp-F) 
`("convert-to-closures"  ,convert-to-closure        ,interp-F) 
`("expose allocation"  ,expose-allocation        ,interp-F) 
`("flatten"     ,(flatten #f)          ,interp-C) 
`("instruction selection" ,select-instructions        ,interp-x86) 
`("liveness analysis"  ,(uncover-live (void))       ,interp-x86) 
`("build interference"  ,(build-interference (void) (void) (void) (void)) ,interp-x86) 
`("allocate register"  ,allocate-registers        ,interp-x86) 
`("lower-conditionals"  ,lower-conditionals        ,interp-x86) 
`("patch-instructions"  ,patch-instructions        ,interp-x86) 
`("x86"      ,print-x86          #f) 
)) 

Answer 1

Для меня место, чтобы начать процесс реализация хвостовой оптимизации будет обнаруживая его через явную конструкцию языка, аналогичную подходу, принятому Clojure's recur operator, потому что это самая простая вещь, которая может работать. Это приведет к одной процедуре, которая распознает хвостовые вызовы и другую процедуру, которая реализует хвостовые вызовы.

Дальнейшая разработка для автоматического распознавания хвостовых вызовов становится модификацией первой процедуры. Дальнейшая разработка для оптимизации оптимизации становится модификацией второй процедуры. Развитие каждого может происходить независимо [или вообще не существует].

Answer 2

Ответ зависит от вашей цели компиляции.

При компиляции на ассемблере (или машинный код), то вы можете обрабатывать хвостовые вызовы в генераторе кода (см, например, «поэтапный подход к Compiler строительства» по Абдулазиз Ghuloum.

Если целевой язык C-like (т. Е. Вызывает контекст сборки), тогда у вас есть несколько вариантов в зависимости от того, насколько вы бы хотели, чтобы ваш компилятор был. Другие упоминали ANF и CPS как промежуточные формы. Также можно ввести батут. См. «Методы внедрения схемы «Felix Winkelman для списка стратегий.

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

Anyways: Если вы заинтересованы в компиляции Схемы, то не стесняйтесь достать копию LiSP: Lisp в Small Pieces от Christian Queinnec.

Answer 3

Вы можете обнаружить хвостовые звонки довольно рано, в идеале прямо после подъема лямбда (вы не сказали это явно, но, скорее всего, ваш переход к закрытию делает это).

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