Skip to content

p6-控制流

:material-circle-edit-outline: 约 813 个字 :material-clock-time-two-outline: 预计阅读时间 3 分钟

IR 有几个问题：

  1. CJUMP 指令能跳两个地方，而机器码跳转指令只能指定一个跳转地址
  2. ESEQ 不好用
  3. 。。。

所以我们需要将其进一步处理：

  1. 重写 IR 树，使其不包含 SEQ 和 ESEQ
  2. 将 list 分组为基本块，其中不会包含 jump 和 label
  3. 基本块会被重新排序为一个 trace 的集合，其中的每一个 CJUMP 后面跟的都是它的 false label

Canonical Trees 定义

规范树定义：

  1. 不包含 SEQ 和 ESEQ
  2. 每个 CALL 的父节点一定是 EXP 或 MOVE(TEMP, ...)

基于此有三条性质

  1. 一个规范树至多一个 statement，且一定是根节点，其它结点一定是表达式结点
  2. CALL 的孩子一定不是 CALL
  3. CALL 的父节点一定是根节点
  4. 一个规范树最多一个 CALL
    • 因为 EXP 或 MOVE(TEMP, ...)最多只能挂一个 CALL

转化方式

liminate ESEQs

我们先尝试将 ESEQ 往上提：

image-20250422184118161

image-20250422184811452

但是对于下面这种情况，假设 s = MOVE(MEM(x), y)，e1 = MEM(x)，直接像上面就会出错，我们就需要改写 MOVE 语句，让前提条件一起提上去，用临时变量存储，将临时变量放在其原本的位置

image-20250422185020990

我们在编译时是无法确定一个 statement 是否能与一个 expression 进行交换（commute），只能进行保守的粗略判断：

  • 如果 expression 是一个常量，那么它可以和任何 statement 进行交换
  • 如果一个 statement 是空的，那么它可以和任何 expression 进行交换

此外的任何情况都不能进行交换

于是我们得到了最终的规则：

image-20250422191335765

move CALLs to top level

问题：each function returns its result in the same dedicated return-value register TEMP(RV)，对于 BINOP(PLUS, CALL(...), CALL(...))，the second call will overwrite the RV register before the PLUS can be execute

用临时变量存储第一个返回值即可

CALL(f, args)-> ESEQ(MOVE(TEMP t, CALL(f, args)), TEMP t)

eliminate SEQ

经过上面的处理后，我们的 IR 树形如 SEQ(SEQ(SEQ(..., sx), sy), sz)

我们重复使用这条规则：SEQ(SEQ(a, b), c) = SEQ(a, seq(b, c))，将左子树上的 SEQ 移动到右子树，变成 SEQ(s1, SEQ(s2, ..., SEQ(sn-1, sn)...))

image-20250422192454443

这完全就没有结构信息，就是线性执行，且每个 s 都是一个规范树，由此我们得到了规范树组成的列表

image-20250422193531740

Taming Conditional Branches

Basic Blocks

A basic block is a sequence of statements that is always entered at the beginning and exited at the end

分块的方法就是遇到 label 就是块的开始，遇到 jump 就是块的结束，如果一个块最后没有 jump 我们就加一个跳到下一条指令的 jump

image-20250422194140322

反映在中间代码就是如下：

image-20250422194130528

Traces

A trace is a sequence of statements that could be consecutively executed during the execution of the program and can include conditional branches

一个程序可以有多条不同的、重叠的 trace，我们希望构建出一组 traces，每个 block 只会出现在一条 trace 上，且每个 trace 都不会有循环，而且这一组 traces 刚好覆盖整个程序，且 trace 越少越好

我们通过 DFS 搜索出所有的 trace

得到 traces 后，对其进行处理：

image-20250422200502049

Any frequently executed sequence of instructions (such as the body of a loop) should occupy its own trace

This helps to minimize the number of unconditional jumps

image-20250422201005409