Как объединить блоки Hoopl-графа / как пройти через блоки - PullRequest
Новая
       20

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

3 голосов
/ 20 августа 2011

Я пытаюсь внедрить 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 не изменяет какие-либо локальные переменные и всегда передает управление следующей инструкции блока?Если инструкции 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

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

Ответы [ 2 ]

2 голосов
/ 23 августа 2011

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

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

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

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

2 голосов
/ 21 августа 2011

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

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

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

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

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

...