Алгоритм встраивания
Кто-нибудь знает о каких-либо обсуждениях статей , алгоритмах встраивания ? И тесно связанная с этим связь родительско-дочернего графа с графом вызовов.
Предпосылки: У меня есть компилятор, написанный на Ocaml , который агрессивно встраивает функции, в основном в результате этой и некоторых других оптимизаций он генерирует более быстрый код для моего языка программирования, чем большинство других, во многих случаях (включая даже C ).
Проблема №1: Алгоритм имеет проблемы с рекурсией. Для этого мое правило состоит только в том, чтобы встраивать дочерние элементы в родительские, чтобы предотвратить бесконечную рекурсию, но это исключает встраивание одноразовых функций друг в друга.
Проблема №2: Я не знаю простого способа оптимизировать операции встраивания . Мой алгоритм обязателен с изменяемым представлением функциональных тел, потому что даже отдаленно не кажется возможным создать эффективный функциональный алгоритм встраивания. Если граф вызовов является деревом, очевидно, что встраивание снизу вверх является оптимальным.
Техническая информация: Встраивание состоит из ряда шагов встраивания. Проблема в порядке шагов.
Каждый шаг работает следующим образом:
- мы делаем копию функции для встраивания и сокращаем ее бета-версию на заменяя как параметры типа, так и параметры значений аргументами.
- Затем мы заменяем оператор return присвоением новой переменной с последующим переходом в конец тела функции.
- Исходный вызов функции затем заменяется этим телом.
- Однако мы еще не закончили. Мы также должны клонировать всех детей функция, бета-редукция их также, и переродить клонов в вызывающая функция.
Операция клонирования чрезвычайно затрудняет встраивание рекурсивных функций. Обычный трюк, заключающийся в том, чтобы сохранить список того, что уже выполняется, и просто проверить, обрабатываем ли мы уже этот вызов, не работает в наивной форме, потому что рекурсивный вызов теперь перемещен в сокращенный бета-код код, который вставляется в вызов функция, а цель рекурсии могла быть изменена на клонированного дочернего элемента. Однако этот дочерний элемент, вызывая родителя, по-прежнему вызывает исходного родителя, который вызывает своего дочернего элемента, и теперь развертывание рекурсии не прекращается. Как уже упоминалось, я нарушил этот регресс, разрешив только встраивание рекурсивного вызова к дочернему элементу, предотвращая встраивание рекурсий одного и того же уровня.
Стоимость встраивания дополнительно усложняется необходимостью сборки мусора неиспользуемых функций. Поскольку встраивание потенциально экспоненциально, это важно. Если все вызовы функции встроены, мы должны избавиться от функции, если она еще не встроена, иначе мы будем тратить время на встраивание в функцию, которая больше не используется. На самом деле отслеживать, кто вызывает то, что чрезвычайно сложно, потому что при встраивании мы работаем не с реальным представлением функции, а с «распутанным»: например, список инструкций обрабатывается последовательно и создается новый список, и в любой момент времени может не быть согласованного списка инструкций.
В своем компиляторе машинного обучения Стивен Уикс решил использовать несколько небольших оптимизаций, применяемых неоднократно, поскольку это упростило написание оптимизаций и облегчило управление. но, к сожалению, при этом упускается много возможностей оптимизации по сравнению с рекурсивным алгоритмом .
Проблема № 3: когда безопасно встроить вызов функции?
Чтобы объяснить эту проблему в общем: на ленивом функциональном языке аргументы заключаются в замыкания, и затем мы можем встроить приложение; это стандартная модель для Haskell. Однако это также объясняет, почему Haskell такой медленный. Замыкания не требуются, если аргумент известен, тогда параметр может быть заменен непосредственно его аргументом там, где он встречается (это нормальный порядок бета-редукция ).
Однако, если известен аргумент оценка не является непрерывной, вместо нее можно использовать активную оценку: параметру присваивается значение выражения один раз, а затем используется повторно. Гибрид этих двух методов - использовать закрытие, но кэшировать результат внутри закрывающего объекта. Тем не менее, GHC не удалось создать очень эффективный код: это явно очень сложно, особенно если у вас есть отдельная компиляция.
В Felix я использовал противоположный подход. Вместо того, чтобы требовать корректности и постепенно повышать эффективность путем доказательства сохранения семантики оптимизаций, я требую, чтобы оптимизация определяла семантику. Это гарантирует правильную работу оптимизатора за счет неуверенности в том, как будет вести себя определенный код. Идея состоит в том, чтобы предоставить программисту способы заставить оптимизатор соответствовать предполагаемой семантике, если стратегия оптимизации по умолчанию слишком агрессивна.
Например, режим передачи параметров по умолчанию позволяет компилятору выбрать, следует ли заключить аргумент в закрытие, заменить параметр аргументом или назначить аргумент параметру. Если программист хочет принудительно закрыть закрытие, он может просто передать закрытие. Если программист хочет принудительно выполнить оценку, он отмечает параметр var .
Сложность здесь намного выше, чем у функционального языка программирования: Felix - это процедурный язык с переменными и указателями. Он также имеет классы типов в стиле Haskell. Это делает процедуру встраивания чрезвычайно сложной, например, экземпляры класса-типа заменяют абстрактные функции, когда это возможно (из-за специализации типа при вызове полиморфной функции, возможно, можно будет найти экземпляр во время встраивания, поэтому теперь у нас есть новая функция, которую мы может быть встроенным).
Чтобы внести ясность, я должен добавить еще несколько примечаний.
Встраивание и несколько других оптимизаций, таких как определяемое пользователем сокращение терминов, создание экземпляров классов типов, проверки линейного потока данных для исключения переменных, оптимизация хвостовой записи, выполняются одновременно для данной функции.
Проблема упорядочения не в том, чтобы применять различные оптимизации, проблема в том, чтобы упорядочить функции.
Я использую алгоритм с мертвым мозгом для обнаружения рекурсии: я составляю список всего, что используется непосредственно каждой функцией, нахожу закрытие, а затем проверяю, есть ли функция в результате. Обратите внимание, что набор использования создается много раз во время оптимизации, и это серьезное узкое место.
Независимо от того, является ли функция рекурсивной или нет, к сожалению, может измениться. Рекурсивная функция может стать нерекурсивной после оптимизации хвостовой записи. Но есть гораздо более сложный случай: создание экземпляра «виртуальной» функции класса типов может сделать то, что кажется нерекурсивным рекурсивным.
Что касается одноуровневых вызовов, проблема в том, что при заданных f и g, где f вызывает g, а g вызывает f, я действительно хочу встроить f в g, а g в f ... один раз. Мое правило остановки бесконечной регрессии - разрешить встраивание f в g только в том случае, если они взаимно рекурсивны, если f является дочерним элементом g, что исключает встраивание братьев и сестер.
В основном я хочу «сгладить» весь код на столько, сколько возможно ».