Size: a a a

Compiler Development

2020 June 18

I

Ilmir in Compiler Development
Ilmir
Разница в том, вызов какой функции мы заменяем. Если вызов себя, то это, очевидно, выгодно настолько, что мы делаем замену всегда, иначе надо считать, выгодно ли вызвать другую функцию или лучше прыгнуть. Во втором случае, ктсати, ещё регистры надо не забыть почистить (если мы не имеет доступа к телу функции, а ABI гарантирует, что эти регистры можно использовать для локальных переменных).
Хотя не, я чего-то путаю с другой оптимизацией. Регистры чистить не надо.
источник

PS

Peter Sovietov in Compiler Development
Ilmir
Разница в том, вызов какой функции мы заменяем. Если вызов себя, то это, очевидно, выгодно настолько, что мы делаем замену всегда, иначе надо считать, выгодно ли вызвать другую функцию или лучше прыгнуть. Во втором случае, ктсати, ещё регистры надо не забыть почистить (если мы не имеет доступа к телу функции, а ABI гарантирует, что эти регистры можно использовать для локальных переменных).
Да, но второй случай это уже не про хвостовую рекурсию.
источник

I

Ilmir in Compiler Development
Peter Sovietov
Да, но второй случай это уже не про хвостовую рекурсию.
По это я и говорю. Эта оптимизация не про хвостовую рекурсию https://t.me/CompilerDev/68238
источник

PS

Peter Sovietov in Compiler Development
А, действительно! Спасибо, невнимательно я прочел.
источник

PS

Peter Sovietov in Compiler Development
Мне вот любопытно, а есть ли в природе системы команд (для процессоров или VM), в которых команда пролога функции определяет, откуда к ней обратились, из call или из jump, и далее ведет себя соответственно. В случае, jump, например, переиспользует текущий фрейм, а не создает новый.

Вот варианты команды tail_call (с удалением фрейма, как я предлагал выше)  существуют. Например: https://github.com/WebAssembly/tail-call/blob/master/proposals/tail-call/Overview.md

Или: https://docs.microsoft.com/en-us/previous-versions/windows/silverlight/dotnet-windows-silverlight/56c08k0k(v=vs.95)?redirectedfrom=MSDN
источник

AT

Alexander Tchitchigi... in Compiler Development
Peter Sovietov
Да, но второй случай это уже не про хвостовую рекурсию.
В "Tail Call Optimization" нет слова "рекурсия" — любой вызов функции, идущий последней инструкцией является хвостовым.

В чём принципиальная разница между рекурсивным и нерекурсивным случаями?
источник

PS

Peter Sovietov in Compiler Development
Alexander Tchitchigin
В "Tail Call Optimization" нет слова "рекурсия" — любой вызов функции, идущий последней инструкцией является хвостовым.

В чём принципиальная разница между рекурсивным и нерекурсивным случаями?
Вызов в духе call foo; ret достаточно легко распознать и заменить на jump foo. Для этого достаточно простого правила peephole-оптимизации.
А вот определение вызова хвостовой рекурсии — значительно более сложная задача.
Кроме того, при хвостовой рекурсии мы могли бы переиспользовать текущий фрейм.
источник

AT

Alexander Tchitchigi... in Compiler Development
Peter Sovietov
Вызов в духе call foo; ret достаточно легко распознать и заменить на jump foo. Для этого достаточно простого правила peephole-оптимизации.
А вот определение вызова хвостовой рекурсии — значительно более сложная задача.
Кроме того, при хвостовой рекурсии мы могли бы переиспользовать текущий фрейм.
А как ещё хвостовая рекурсия может выглядеть?

Если у нас в calling convention стек чистит вызывающая функция перед возвратом, то вообще никакой проблемы нет — мы в любом случае его чистим, а там уже неважно чем он будет перезаполнен, тем же самым фреймом или новым. 🤷‍♀️
источник

PS

Peter Sovietov in Compiler Development
Alexander Tchitchigin
А как ещё хвостовая рекурсия может выглядеть?

Если у нас в calling convention стек чистит вызывающая функция перед возвратом, то вообще никакой проблемы нет — мы в любом случае его чистим, а там уже неважно чем он будет перезаполнен, тем же самым фреймом или новым. 🤷‍♀️
Иногда выгоднее не чистить стек полностью, а просто заменить точечно что-то во фрейме — и снова его использовать :)

Как может выглядеть хвостовая рекурсия? В рекурсивных функциях обязательно есть какое-то условие выхода из рекурсии. А где условие — там и jump :)
источник

AN

Alexander Nasonov in Compiler Development
Peter Sovietov
Иногда выгоднее не чистить стек полностью, а просто заменить точечно что-то во фрейме — и снова его использовать :)

Как может выглядеть хвостовая рекурсия? В рекурсивных функциях обязательно есть какое-то условие выхода из рекурсии. А где условие — там и jump :)
Про jump, почти, но https://github.com/xoreaxeaxeax/movfuscator
источник

PS

Peter Sovietov in Compiler Development
Давайте я приведу пример хвостовой рекурсии.

Предположим, мы компилируем следующую функцию:

(define gcd (m n)
   (if (= n 0)
       m
       (gcd n (mod m n))))

Очевидно, что вызов gcd здесь хвостовой. Теперь давайте получим промежуточное стековое представление. Причем, используем оптимизацию для if (поменяем if и else части местами, чтобы избежать лишней проверки):

Enter('gcd', ['m', 'n'])
Load('n')
Jump0(0)
Load('n')
Load('m')
Over()
Op('mod')
Call('gcd')
Jump(1)
Label(0)
Load('m')
Label(1)
Return()

Вот и проблема. Вызов оказался где-то в центре кода скомпилированной функции, а главное, за ним не следует Return.

А вот грамотный оптимизатор способен с этим справиться:

Enter('gcd', ['m', 'n'])
Load('n')
Jump0(0)
Load('n')
Load('m')
Over()
Op('mod')
TCall('gcd')
Label(0)
Load('m')
Return()
источник

K

Kir in Compiler Development
CPS-трансформация, вроде как, решает вопрос с хвоствой рекурсией на корню
источник

PS

Peter Sovietov in Compiler Development
Kir
CPS-трансформация, вроде как, решает вопрос с хвоствой рекурсией на корню
Если бы это было так, то в стандарте на ту же Scheme не отводили бы специальный раздел на правила оптимизации хвостовой рекурсии.
источник

D

Danya in Compiler Development
По поводу flex/bison
Можете посоветовать годные туториалы/книги?
Просто стандартная документация как-то meh, беглый поиск ничего хорошего мне не дал, а университетские методички, которые у меня есть слишком скудные..
источник

A

Alex in Compiler Development
Чего не хватает в университетских/обычной документации?
источник

D

Danya in Compiler Development
Простоты, что ли
источник

D

Danya in Compiler Development
Я конечно глубоко не вникал ещё
источник

D

Danya in Compiler Development
Но просто хочется потратить минимум времени, чтобы достичь максимум профита
источник

PS

Peter Sovietov in Compiler Development
Danya
По поводу flex/bison
Можете посоветовать годные туториалы/книги?
Просто стандартная документация как-то meh, беглый поиск ничего хорошего мне не дал, а университетские методички, которые у меня есть слишком скудные..
А Вы начните с решения конкретной простой задачи. Тогда и вопросы появятся по существу.
источник

A

Alex in Compiler Development
Danya
Но просто хочется потратить минимум времени, чтобы достичь максимум профита
)))))))))
источник