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