Кто-нибудь знает о любых обсуждениях статей алгоритмы inlining? И тесно связан, отношение parent-child graph для вызова графика.Алгоритм встраивания
фон: У меня есть компилятор, написанный на Ocaml, которые агрессивно встраивает функцию, в первую очередь в результате этого и некоторые другие оптимизаций он генерирует более быстрый код для моего языка программирования, чем большинство других во многих случаях (в том числе даже C).
Проблема №1: Алгоритм имеет проблемы с рекурсией. Для этого мое правило состоит только в том, чтобы встроить детей в родителей, чтобы предотвратить бесконечную рекурсию, но это исключает однопользовательские функции, связанные друг с другом.
Проблема №2: Я не знаю простого способа оптимизации операций наложения. Мой алгоритм необходим с изменчивым представлением тел функций, потому что не представляется возможным даже сделать возможным эффективный функциональный алгоритм вложения. Если граф вызовов является деревом, становится ясно, что нижняя инкрустация является оптимальной.
Техническая информация: Вкладыши состоят из ряда ступеней. Проблема заключается в упорядочении шагов.
Каждый шаг работает следующим образом:
- мы делаем копию функции быть встраиваемыми и бета-сократить замена обоих параметров типа и параметров значений с аргументами.
- Затем мы заменяем оператор return присваиванием новой переменной , за которой следует переход к концу тела функции.
- Первоначальный вызов функции затем заменяется этим телом.
- Однако мы еще не закончили. Мы также должны клонировать всех детей функции, бета-редукцию их, а также повторять клоны до вызывающей функции.
Операция клонирования чрезвычайно затрудняет встроенные рекурсивные функции. Обычный трюк для хранения списка того, что уже выполняется, и просто проверка на то, что мы уже обрабатываем этот вызов, не работает в наивной форме, потому что рекурсивный вызов теперь перемещается в код с бета-кодом, который вводится в вызывающий функция, и цель рекурсии может быть изменена на клонированного ребенка. Однако этот ребенок при вызове родителя по-прежнему вызывает исходный родитель, который вызывает его дочерний элемент, и теперь разворачивание рекурсии не прекратится. Как уже упоминалось, я нарушил этот регресс, только разрешив вставить рекурсивный призыв к ребенку, не вставляя рекурсии братьев и сестер.
Стоимость встраивания дополнительно осложняется необходимостью garbage collect неиспользованных функций. Поскольку вложение потенциально экспоненциально, это важно. Если все вызовы функции включены, мы должны избавиться от этой функции, если она еще не была встроена, иначе мы будем тратить время на вложение функции, которая больше не используется. Фактически отслеживание того, кто называет то, что чрезвычайно сложно, потому что когда мы встраиваем, мы не работаем с фактическим представлением функции, а «распутываем» одно: например, список инструкций обрабатывается последовательно и создается новый список, и в любой момент времени может не быть согласованного списка инструкций.
В его ML компилятор Стивен Неделях решили использовать ряд небольших оптимизаций, применяемые неоднократно, так как это сделало оптимизации легко писать и легко контролировать, но, к сожалению, это пропускает много возможностей оптимизации по сравнению с рекурсивного алгоритма ,
Проблема №3: , когда безопасно встроить вызов функции?
Чтобы объяснить эту проблему в общем: в ленивом функциональном языке аргументы завернуты в закрытие, а затем мы можем встроить приложение; это стандартная модель для Haskell. Однако это также объясняет, почему Haskell так медленно. Закрытие не требуется, если аргумент известен, тогда параметр может быть заменен непосредственно его аргументом, где происходит (это нормальный порядок beta-reduction).
Однако, если известно, что оценка аргументов не является окончательной, то вместо нее может использоваться нетерпеливая оценка: параметру присваивается значение выражения один раз, а затем повторно используется. Гибрид этих двух методов заключается в использовании замыкания, но кэширование результата внутри объекта замыкания. Тем не менее, GHC не удалось создать очень эффективный код: это явно очень сложно, особенно если у вас есть отдельная компиляция.
В Феликсе я принял противоположный подход. Вместо того, чтобы требовать правильности и постепенно повышать эффективность, подтверждая сохраненную семантику, я утверждаю, что оптимизация определяет семантику. Это гарантирует правильную работу оптимизатора за счет неопределенности относительно того, как будет себя вести определенный код. Идея заключается в том, чтобы предоставить программисту возможность заставить оптимизатора соответствовать намеченной семантике, если стратегия оптимизации по умолчанию слишком агрессивна.
Например, режим передачи параметров по умолчанию позволяет компилятору выбирать, следует ли переносить аргумент в замыкание, заменять параметр аргументом или назначать аргумент параметру. Если программист хочет заставить закрыть, они могут просто пройти в закрытии. Если программист хочет принудительно провести оценку, они отмечают параметр var.
Сложность здесь намного больше, чем функциональный язык программирования: Felix - это процедурный язык с переменными и указателями. Он также имеет стили стиля стиля Haskell. Это делает чрезмерную сложность процедуры вложения, например, экземпляры типа-типа заменяют абстрактные функции по возможности (из-за специализации по типу при вызове полиморфной функции может быть возможно найти экземпляр при вставке, так что теперь у нас есть новая функция, мы может встроить).
Чтобы быть ясным, я должен добавить еще несколько заметок.
Вкладывание и несколько других оптимизаций, таких как сокращение сроков, определяемых пользователем, создание экземпляров типов, проверка потока данных для исключения переменных, оптимизация хвостового ключа, выполняются сразу же по заданной функции.
Проблема с заказом - это не порядок применения различных оптимизаций, задача состоит в том, чтобы заказать функции.
Я использую алгоритм «мертвый мозг» для обнаружения рекурсии: я создаю список всего, что используется непосредственно каждой функцией, находит замыкание, а затем проверяет, находится ли функция в результате. Обратите внимание, что набор настроек многократно увеличивается во время оптимизации, и это серьезное узкое место.
Независимо от того, является ли функция рекурсивной или нет, к сожалению. Рекурсивная функция может стать нерекурсивной после оптимизации хвоста.Но есть гораздо более сложный случай: создание экземпляра виртуальной функции может сделать то, что оказалось нерекурсивным рекурсивным.
Что касается вызовов на сестры, проблема в том, что заданные f и g, где f вызывает g и g вызывает f, я действительно хочу вставить f в g и g в f .. один раз. Мое бесконечное правило остановки регрессии заключается в том, чтобы разрешить встраивание f в g, если они взаимно рекурсивные, если f является дочерним элементом g, что исключает вложение браков и сестер.
В принципе, я хочу «выровнять» весь код «как можно больше».
Я проверил бы GHC Wiki. Также стоит прочитать о MlTon. Однако я, возможно, был немного запутанным: мой компилятор не делает большинство оптимизаций в проходах: они все делаются сразу. – Yttrill 2010-12-17 16:23:19
спасибо за ссылку на Compilation by Equality Saturation: это очень хороший подход! – Yttrill 2010-12-28 23:39:58