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

我正在尝试将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建立递归图形。为了生成代码，我需要以更自然的方式对块进行重新排序，例如将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

可能是我错了吗？

最佳答案

使用HOOPL可以实现“块合并”。您的问题太笼统了，所以我给您一个计划:

确定此优化所需的分析类型(向前或向后)

设计分析格

设计传递函数

设计重写功能

创建通行证

将通行证与相同方向的其他通行证合并，以便它们交错

使用燃料

运行通行证

将优化图转换回您需要的形式

您在哪个阶段有问题？阅读论文后，步骤1和2应该非常简单。

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

您的重写功能应使用事实来重写块中的最后一个节点。因此，事实晶格不仅应包括“有关可达性的信息”，还应包括目标自身。