Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Category:

Композиция оптимизаций

Там довольно хитрая проблема:

http://cse.ucsd.edu/sites/cse/files/cse/assets/research/biblio/dataflow_popl_02.pdf

(первые 2 абзаца раздела "introduction", не могу скопипастить)

TL;DR: при последовательном применении разных видов оптимизаций результаты зависят от последовательности оптимизаций нетривиальным образом, и повторения, пока стабилизируется, недостаточно. В результате, как правило, подбирают более-менее приличную последовательность оптимизаций и повторяют её в цикле. Или делают адхок-супероптимизатор (не путать с суперкомпиляцией), который выполняет все оптимизации параллельно и не имеет необходимости подбора последовательности фаз.

Статья предлагает алгоритм автоматического синтеза супероптимизаторов из обычных оптимизаторов. HOOPL реализует этот алгоритм. Но алгоритм накладывает ограничения на исходные оптимизаторы, которые мне пока не удалось удовлетворить.

В вводной части статьи приводится пример constant propagation и unreachable code elimination - они комбинируются, потому что обе оптимизации опираются на "прямой" dataflow-анализ. А, например, устранитель ненужных присваиваний опирается на "обратный" анализ и может быть скомбинирован только с другими "обратными" оптимизациями.

Про прямые и обратные анализы хорошо написано здесь (слайд 10 the flow of liveness) и здесь (слайд 7 direction of flow)

На последнем слайде как раз и написано, что "некоторые задачи требуют анализа в обеих направлениях". Вот, инлайнинг одна из таких задач.

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

Я пока не парюсь, будет больше оптимизаций - больше опыта работы с хуплом - подумаю как избавиться от конюшен.

А пока вот такая последовательность:

https://github.com/kayuri/HNC/blob/master/HN/Optimizer/Frontend.hs#L25
Tags: hn0
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments