Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

HNC - Этап Оптимизатора

Идею что-то оптимизировать ручками я отбросил сразу. Поиск фреймворков композабельных оптимизаций, хорошо работающих с хаскелем, мне не дал ничего, кроме HOOPL. Это библиотека dataflow-оптимизации SSA-подобных basic blocks, которую GHC использует для оптимизации Cmm-кода.

В-общем, это одно из направлений неадхок-оптимизаторов, описанное в общих чертах ещё в Ахо-Ульмане, пережёванное воспалённым сознанием тайпфу-хакеров, пиливших GHС. По современным меркам там примитивное тайпфу, просто GADTы.

Поскольку функциональных оптимизаторов не нашлось, я приспособил императивный оптимизатор под IR в виде бестиповой лямбды. Ниже я упрощаю детали, чтобы хупловское и мое тайп-фу не заслоняли общей картины.
data Node
	= Node Label DefinitionNode -- определение идентификатора

data DefinitionNode
	= LetNode [Label] Expression -- лямбда-абстракция или переменная (если список пуст)
	| ArgNode                    -- аргумент
	| LibNode                    -- идентификатор, определенный в C++/FFI

data Expression
	=   Application Expression [Expression]
	|   Atom Label
	|   Constant Int
Далее Hoopl лепит граф из этих Node и Label. Cсылка на биндинг = ребро графа, а переменные биндятся в 3-х местах:
- в let (из-за особенностей let-полиморфизма и других причин я не могу рассахарить let в функцию),
- в функциях (аргументы)
- снаружи (в стдлибе или foreign-функции).

Ну и далее банальный прямой и обратный датафлоу-анализ с решетками и трансфер-функциями (в инете полно курсов), на который навешан an advanced framework of composable interleaved rewrites, см. пейпер по HOOPL.

Интересно, что unreachable code elimination мне хупл дал бесплатно - просто когда я конструирую обратно лямбда-термы из лямбда-графа, хупловский итератор не заходит в недостижимые из точки входа узлы.

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

Сначала я писал

1) просто инлайнинг идентификаторов, которые используются один раз. Но потом мне захотелось
2) чтобы и аргументы, которые во всех вызовах одинаковы, реврайтились в локальные переменные.
После чего у меня появилось на выходе куча штук вида let a = b in a + a, где a использовалось более 1 раза и поэтому не инлайнилось. Ну я и забацал
3) чтобы тривиальные биндинги тоже инлайнились (по-моему это называется copy propagation).

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

Ну и самое главное, хупл эти проходы умеет лепить в кучу таким образом, чтобы (почти) не надо было думать о порядке. "Почти" означает, что все проходы forward analysis хупл слепливает в один проход, и все обратные проходы слепливает, а в каком порядке и сколько раз эти два макропрохода вызывать - решать мне адхоком. На практике очень даже лучше чем традиционно делать адхоком вообще всё. Тем более что оказалось, что есть хитрые двухсторонние dataflow problems, в терминах хупла оказывающимися односторонними.

Например, если требуется обратный изначальный анализ, но такая прямая перезапись, после которой переанализ внезапно оказывается тоже прямым - всё пучком, никакого адхока.

В-общем, оптимизатор более-менее заработал и ада, на котором бы классификатор-кодогенератор падал (см. Этап Кодогенератора), больше не возникает. Но теперь оказалось, что самое мерзкое в выходном коде - это не шаблоны, сидящие на шаблонах, а отсутствие while и присваивания, из-за которого приходится писать катаморфизмы с boost::function на С++ (c while внутри), и они прямо так и идут на выход.

В-общем, я решил, что мне надо побыстрее довести до proof-of-concept, хрен с ней с полурабочестью кодогена и оптимизатора, и пора приступить к внедрению императивщины. Чтобы можно было писать на входе ФВП с циклом, а на выходе ФВП инлайнилась, и в месте использования так прямо цикл бы и был.
Tags: haskell, hn0, programming
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