Как объединить блоки графов Хупла / как пройти через блоки

Question

Я пытаюсь ввести Hoopl в некоторый компилятор и столкнулся с некоторой проблемой: создание графика для Hoopl заставляет узлы появляться в порядке введенных меток.

Например:

(define (test) (if (eq? (random) 1 ) 2 (if (eq? (random) 2 ) 3 0) ) )

"компилируется" в

L25:    call-direct random  -> _tmp7_6
    branch L27
L26:    return RETVAL
L27:    iconst 1 _tmp8_7
    branch L28
L28:    call-direct eq? _tmp7_6, _tmp8_7 -> _tmp4_8
    branch L29
L29:    cond-branch _tmp4_8 L30 L31
L30:    iconst 2 RETVAL
    branch L26
L31:    call-direct random  -> _tmp12_10
    branch L32
L32:    iconst 2 _tmp13_11
    branch L33
L33:    call-direct eq? _tmp12_10, _tmp13_11 -> _tmp9_12
    branch L34
L34:    cond-branch _tmp9_12 L36 L37
L35:    assign RETVAL _tmp6_15
    branch L26
L36:    iconst 3 _tmp6_15
    branch L35
L37:    iconst 0 _tmp6_15
    branch L35

Порядок инструкций (в порядке showGraph) странный из-за порядка построения рекурсивного графа из AST. Чтобы сгенерировать код, мне нужно изменить порядок блоков более естественным образом, скажем, поместите return RETVAL в конец функции, объедините блоки следующим образом.

    branch Lx:
Lx: ...

в один блок и так далее. Кажется, мне нужно что-то вроде:

block1 = get block
Ln = get_last jump
block2 = find block Ln
if (some conditions) 
    remove block2
    replace blick1 (merge block1 block2)

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

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

Есть еще один вопрос. Есть ли смысл делать все инструкции Call нелокальными? Какой смысл в этом, учитывая, что реализация Call не изменяет какие-либо локальные переменные и всегда передает управление следующей инструкции блока? Если инструкции вызова определены как

data Insn e x where
   Call :: [Expr] -> Expr -> Label :: Insn O C -- last instruction of the block

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

-- what the difference with any other primitive, like "add a b -> c" 
Call :: [Expr] -> Expr -> Label :: Insn O O 

Может быть, я не прав с этим?

Answer 1

Я нашел и попробовал несколько способов сделать это:

1. Использование функции foldBlockNodesF3 или других функций foldBlockNodes...
2. Использование функций preorder_dfs* (как в проекте Lambdachine)
3. Постройте график с большими блоками с самого начала

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

Итак, мое окончательное решение - использовать функцию foldBlockNodesF3, линеаризовать график и вручную удалить дополнительные метки с одновременным распределением регистров.

Answer 2

Реализовать "объединение блоков" можно с помощью HOOPL. Ваш вопрос слишком общий, поэтому я даю вам план:

1. Определите, какой тип анализа требуется для этой оптимизации (прямой или обратный)
2. Дизайн решетки анализа
3. Разработать передаточную функцию
4. Разработать функцию перезаписи
5. Создать пропуск
6. Объедините проход с другими проходами того же направления, чтобы они чередовались
7. Запустите проход, используя топливо
8. Конвертировать оптимизированный график обратно в форму, которая вам нужна

С какими этапами у вас проблемы? Шаги 1 и 2 должны быть довольно простыми, как только вы прочитаете бумаги.

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

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