Skip to content

8. Control Flow

Canonical Trees

Conditional Branches

  • CJUMP(cond,l1,l2) 有条件跳转
  • JUMP(l) 无条件

Basic Block

基本块划分

  • 第一条语句是LABEL
  • 最后一条语句是JUMP或者CJUMP
  • 没有其他的LABEL,JUMP,CJUMP

划分算法: 按顺序扫描语句序列

  • 如果是LABEL就开始
  • 如果是JUMP或CJUMP 就结束当前块。下一条语句，和JUMP的目标语句都开始一个新的块 这样划分完之后，如果一个块开头没有LABEL,就加一个LABEL. 如果结尾没有JUMP/CJUMP, 就加一个JUMP到下一个块的LABEL

Trace

目标是将程序的基本块组织成一系列的迹 (traces)。一个迹是一个基本块序列，如果程序执行到达迹的第一个基本块，那么它会按照顺序执行迹中的所有基本块，直到遇到一个分支到迹外的基本块。

  1. 初始化： 将程序中的所有基本块放入一个列表 Q 中。
  2. 循环直到所有块都被处理： 当 Q 不为空时，执行以下操作：
    • 开始新的迹： 创建一个新的空迹 T。
    • 选择起始块： 从 Q 的头部移除一个基本块 b。
    • 跟踪当前迹： 只要当前块 b 没有被标记（表示它还没有被包含在任何迹中）：
      • 标记并添加到迹： 将 b 标记为已处理，并将 b 添加到当前迹 T 的末尾。
      • 检查后继块： 检查 b 的所有后继块（即 b 分支到的块）。
      • 选择未标记的后继块： 如果存在一个未被标记的后继块 c，则将 b 更新为 c，继续跟踪该后继块。
      • (所有后继块都已标记)： 如果 b 的所有后继块都已经被标记，则当前迹 T 结束。
    • 迹已完成： 当内部的 while 循环结束时，当前的迹 T 就生成完毕了。

Comments