haskell - 如何合并Hoopl图 block /如何通过 block

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的顺序)很奇怪，因为order of从 AST 构建递归图。为了生成代码，我需要以更自然的方式重新排序 block ，比如将 return RETVAL 放置到函数末尾，像这样合并 block

    branch Lx:
Lx: ...

进入一个 block ，依此类推。似乎我需要这样的东西:

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 的实现不会改变任何本地的，这有什么意义变量并始终将控制转移到 block 的下一条指令？如果调用指令定义如下

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

可以使用 HOOPL 实现“ block 合并”。你的问题太笼统了，我给你一个方案:

1. 确定此优化需要的分析类型(前向或后向)
2. 设计分析格
3. 设计传递函数
4. 设计重写函数
5. 创建通行证
6. 将 channel 与同一方向的其他 channel 合并，使它们交错
7. 使用燃料运行通行证
8. 将优化图转换回您需要的形式

您在哪个阶段遇到问题？阅读论文后，第 1 步和第 2 步应该相当简单。

您还应该了解 basic block 的一般概念- 为什么指令合并到 block 中，为什么控制流图由 block 而不是单个指令组成，为什么分析是在 block 上而不是在单个指令上执行的。

你的重写函数应该使用事实来重写 block 中的最后一个节点。因此，事实格不仅应包含“有关可达性的信息”，还应包含目标 block 本身。