优化代码布局是对性能提升的重要手段，之前介绍的 BOLT 和 Propeller 都是基于运行时采集到的 profile 进行优化。最近看到一篇论文，通过静态分析来进行分支的优化，本文简单记录一下。

1、基于静态分析的分支优化

使用静态分析而不是基于 profile 文件，有以下优势：

  • 速度。不需要先对程序采集 profile 信息文件，然后再重新编译来完成优化。
  • 适用性。由于不需要运行时信息，所以可以在所有系统环境适用。
  • 独立性。独立于输入(一般对程序的数据输入会影响程序的运行时行为)，并且可以覆盖所有的执行分支。

那么缺点就主要是，相对于使用 profile 文件，会缺乏准确性。

论文为了说明两点：

  • 静态分析选用的风险较小的执行路径(hazard-less path) 更可能被频繁执行。
  • 使用 profile 信息获取准确的分支预测，并不是代码优化所必要的度量(metric)。

hazard(危害) 意味着某些阻止路径优化和调度的指令。它们可能在编译期间还没法确认其副作用(side effects)。

heuristics(启发式) 通常是基于一些基准测试和回归测试得到的人工组织的规则(策略、policy)。

静态分析使用的启发式会倾向于避免存在像子调用(subroutine call) 等有害状态的路径，因为对这些高风险路径的操作是不利于优化的。那么使用静态分析在这种情况下，是可以更优于使用 profile 的准确分支信息的。

2、超级块

2.1、前置概念

2.1.1、superblock

代码块(basic block) 是一连串的指令，执行流只能从开始的第一条进入，从结束的最后一条离开。即具有原子性，无法从中间跳跃出去，一旦执行，就要全部被执行完。

代码布局优化和调度的目的是为了减少执行时间。当从全局去做时，可能会导致一些局部路径是负优化的。如果能抉择出更好的执行路径，那么就可以达到整体的性能提升。

superblock(超级块) 即是编译器进行路径优化与调度的一种单位。一个 superblock 是一整块指令，执行控制只从顶部进入，但可以从一个或多个出口离开。 (A superblock is a block of instructions in which control may only enter at the top but may leave at one or more exit points.)

2.1.2、trace

trace 的定义就比较多了，论文本身并没有说明这个概念，但构造超级块会用到。

在 llvm 中也有 llvm::Trace 类来定义，是只有一个入口，可以有多个出口，调用频率高的那块代码区域。(A trace is a single entry, multiple exit, region of code that is often hot.)

还有论文《Trace Scheduling》 里，定义为无循环的由输入数据决定的连续执行的指令串。(A trace is a loop-free sequence of instructions which might be executed contiguously for some choice of data.)

结合其他文章里的定义，可以认为是分支语句中的一条执行路径。(A trace, by definition, is a single basic block with the original branches removed.)

2.2、构造超级块

superblock formation(构造) 有两个要点：

  1. 找到 traces 或者说是一系列会线性执行(execute in sequence) 的代码块。
  2. 执行 tail duplication(尾部拷贝) 来消除区域内的多余入口。

2.2.1、案例

如上图，图中节点的数字代表的是基于 profile 获取到的节点执行权重，可以看到 C 的路径更可能被执行，但 D 的存在可能会导致 C、E 指令优化和调度出现困难。通过对 E 进行尾部拷贝，消除了多余的入口，构造成一个超级块，就可以进行优化了。

构造超级块，可以允许优化某条执行路径，而不用受到另外的执行路径的影响和限制。

为什么说之前的 D 会对 C、E 的指令优化和调度有影响？看看下面的案例。

3、静态分析的启发式优化

假设把 profile 中 C 和 D 得到的权重交换一下，那么会变成这样：

准确的分支预测有时并不会带来更好的优化和调度机会，那么可以用静态分析启发式(static branch analysis heuristics) 来避免超级块中的有害指令，同时可以减去进行 profiling(收集 profile 然后优化) 的开销。

静态分析启发式会更倾向于 C 这条没有有害状态的路径，然后就可以执行之前的循环不变优化。同时需要避免因为有害状态导致限制了超级块的构造。

对于循环里的分支路径，很好抉择，因为循环的回边是更有可能执行的，而离开循环的路径会更少执行。已经有很多对循环进行的优化了。

不过对于非循环的分支路径，就需要避开有害状态和使用启发式了。

3.1、hazards

有六种有害状态的指令类型：

  • I/O 指令。会改变程序状态的，比如内存访问。
  • 子调用(subroutine call)。
  • 同步指令(synchronization instructions)。
  • 无法确定的写入指令(ambiguous stores)。
  • 子调用返回(subroutine returns)。
  • 间接跳转(jumps with indirect target addresses)。

那么，如果某条路径上后继节点包含 hazards，或者会无条件转移执行控制到包含 hazards 的节点，以及这个后继节点不后向支配(post-dominate) 这个分支，则选择另一条路径。

post-dominate 即从 n 到出口点(exit) 的每条路径上，都有 d，则称 d 后向支配 n。用在这里，后面那半句是说是否有路径不被 hazards 影响，否则将无法避开 hazards。

比如下面的 B 含有 hazard，但 B 不后向支配这个分支(存在 C 路径到出口)，那么我们选择 ACD 来进行优化。

这个规则称之为 hazard avoidance heuristics。

3.2、heuristics

下面的 heuristics 按从高到低的优先级排，都是静态分析对路径选择的倾向，这些都是论文中根据些研究和实验所选取出来的。

  • Pointer Heuristic。若分支包含有指针指令，指针不太可能是 NULL，且两个指针对比不太可能相等。
  • Loop Heuristic。分支更可能进入循环执行，而不是离开循环。
  • Opcode Heuristic。分支预测会使用分支指令操作码作为参考，已有研究通过大量的 benchmark 程序进行分析的结果，可以判断某种操作码的分支会如何执行。而具有相同操作码的分支指令可以拿来在静态分析中判断。不过需要点限制，操作码不太可能是负数，浮点数对比不太可能相等。
  • Guard Heuristic。如果一个分支是用来保护(guard) 它其中的操作数的使用，那么更有可能会被使用。因为认为这个 guard 通常是检测异常状态的。
  • Branch Direction Heuristic。根据分支跳转的方向来判断，往前跳转(backward branch，即跳转的地址比当前地址要小) 更可能成立，而往后跳转(forward branch) 会少点。像循环就比较多往前跳转，而往后跳转更可能是因为失败而返回。

3.3、测试效果

下图测试效果说明静态分析选用的风险较小的执行路径(hazard-less path) 更可能被频繁执行。

而性能方面，处理器处理速度会对差距放大更明显，不过静态分析基本还是可以达到使用 profile 的一定的效果。

参考