Алгоритм встраивания

Question

Кто-нибудь знает какие-либо документы, обсуждающие алгоритмы встраивания? И тесно связаны, отношения родитель-дочерний граф к графу вызовов.

Фон: у меня есть компилятор, написанный на Ocaml который активно использует функции, в основном в результате этой и некоторых других оптимизаций, он генерирует более быстрый код для моего языка программирования, чем большинство других во многих обстоятельствах (включая даже C).

Проблема № 1: Алгоритм имеет проблемы с рекурсией. Для этого мое правило состоит только в том, чтобы встраивать детей в родителей, чтобы предотвратить бесконечную рекурсию, но это исключает вхождение функций одного брата в друг друга.

Проблема № 2: я не знаю простого способа оптимизации операций встраивания. Мой алгоритм обязателен для изменяемого представления функциональных тел, потому что даже отдаленно невозможно создать эффективный алгоритм функционального встраивания. Если граф вызовов является деревом, то ясно, что наклон снизу вверх является оптимальным.

Техническая информация: встраивание состоит из ряда этапов встраивания. Проблема заключается в порядке шагов.

Каждый шаг работает следующим образом:

• мы делаем копию функции для встраивания и бета-сокращения, заменяя параметры типа и параметры значения аргументами.
• Затем мы заменяем оператор return на присвоение новой переменной с последующим переходом к концу тела функции.
• Исходный вызов функции затем заменяется этим телом.
• Однако мы еще не закончили. Мы также должны клонировать всех потомков функции, также уменьшив их бета-версию, и переписать клоны в вызывающую функцию.

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

Стоимость встраивания еще более осложняется необходимостью garbage collect неиспользуемые функции. Поскольку встраивание потенциально экспоненциально, это важно. Если все вызовы функции встроены, мы должны избавиться от функции, если она еще не встроена, в противном случае мы будем тратить время на вставку в функцию, которая больше не используется. На самом деле отслеживание того, кто вызывает то, что чрезвычайно сложно, потому что при встраивании мы работаем не с фактическим представлением функции, а с "распутанным": например, список инструкций обрабатывается последовательно и создается новый список, и в любой момент времени может отсутствовать согласованный список инструкций.

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

Проблема № 3: когда безопасно встроить вызов функции?

Для общего объяснения этой проблемы: в ленивом функциональном языке аргументы заключаются в замыкания, и тогда мы можем встроить приложение; это стандартная модель для Haskell. Однако это также объясняет, почему Haskell так медленно Замыкания не требуются, если аргумент известен, тогда параметр может быть заменен непосредственно его аргументом где это происходит (это нормальный порядок beta-reduction).

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

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

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

Сложность здесь намного больше, чем у функционального языка программирования: Феликс - это процедурный язык с переменными и указателями. Он также имеет классы типов в стиле Haskell. Это делает процедуру встраивания чрезвычайно сложной, например, когда экземпляры класса типов заменяют абстрактные функции, когда это возможно (из-за специализации типов при вызове полиморфной функции может быть возможно найти экземпляр во время встраивания, поэтому теперь у нас есть новая функция, которую мы можно встроить).

Просто чтобы прояснить, я должен добавить еще несколько заметок.

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

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

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

К сожалению, функция может быть рекурсивной или нет. Рекурсивная функция может стать нерекурсивной после оптимизации хвостовой записи. Но есть гораздо более сложный случай: создание экземпляра "виртуальной" функции класса типов может сделать то, что казалось нерекурсивным, рекурсивным.

Что касается родственных вызовов, проблема в том, что учитывая f и g, где f вызывает g, а g вызывает f, я на самом деле хочу вставить f в g и g в f .. один раз. Мое правило остановки бесконечной регрессии - разрешить встраивание f в g только в том случае, если они взаимно рекурсивны, если f является потомком g, что исключает встраивание братьев и сестер.

По сути, я хочу "сгладить" весь код "как можно больше".

Answer 1

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

В функциональном сообществе есть некоторая литература, в основном от людей GHC. Обратите внимание, что они рассматривают встраивание как преобразование в исходном языке, в то время как вы, кажется, работаете на более низком уровне. Работа на исходном языке - или на промежуточном языке с достаточно схожей семантикой - я считаю, очень помогает простоте и правильности.

• GHC Wiki: Inlining (содержит библиографию)
• Тайны Глазго Хаскелл лайнер

Что касается порядка упорядочивания проходов, это довольно загадочно. Тем не менее, в настройках Haskell есть кандидатская диссертация " Компиляция путем преобразования в нестрогом функциональном языке", в которой обсуждается порядок различных проходов компилятора (а также встраивание).

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

Answer 2

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

http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm