3

我正在尝试将 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

由于从 AST 构建递归图的顺序，指令的顺序（按 showGraph 的顺序）很奇怪。为了生成代码，我需要以更自然的方式重新排序块，比如将返回 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

可能是我错了吗？

4

2 回答 2

2

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

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

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

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

您的重写函数应该使用事实来重写块中的最后一个节点。所以事实格不仅应该包括“可达性信息”，还应该包括目标块本身。

于 2011-08-21T18:59:44.670 回答
2

我已经找到并尝试了几种方法来做到这一点：

  1. 使用 foldBlockNodesF3 函数或其他 foldBlockNodes... 函数
  2. 使用 preorder_dfs* 函数（如在 Lambdachine 项目中）
  3. 从一开始就构建具有较大块的图形

最后一个选项对我没有用，因为 FactBase 与标签链接，所以每条改变变量活跃度的指令都应该有一个标签，以便在下面的分析中使用。

所以，我的最终解决方案是使用 foldBlockNodesF3 函数并线性化图形并手动删除额外的标签，同时分配寄存器

于 2011-08-23T06:55:21.490 回答