编译优化概念：Canonicalization

编译优化概念：Canonicalization - 知乎 (zhihu.com)

anonicalization(规范化) 是编译器 IR(intermediate representation) 设计中的一个重要部分，它使代码转换(transformations) 变得简单高效。大多数编译器都有 canonicalization pass，对于后续进行编译器优化也起到很大作用。

1、简介

canonicalization (有时也称之为 standardization(标准化) 或 normalization(常规化)) 是一种将拥有多种表达形式的数据，转换为 canonical form(规范格式) 的操作。

比如一个表达式有多种等价表达，我们将其都转换为其中一种，作为 canonical form。

x + 4
4 + x
(x + 2) + 2

转换之后，由于只需要匹配 canonical form 即可，极大地简化了后续的优化操作。

在 IR 层面也可以看到这种 canonicalization 转换，如 compiler explorer 代码片段：

这几种代码逻辑，在进行 -O1 优化后，得到的都是相同的 IR 表达：

%4  =  select  i1  %0, i32  %1, i32  %2

这种对于原本的控制流(control flow) 的重写，使得无论我们以何种编写习惯来组织代码，都能够得到同样的优化。

canonicalization 过程是嵌套、迭代的，通常完成某处的转换，也会触发另一处也可以进行转换。

2、如何抉择？

既然有那么多的相同的表达可以选择，那选用哪种作为 canonical form 才是合理的？

一种思路就是越简单越好，如 2 + 3 用 5 表达。但也存在更符合审美的随意选择，比如 4 + x 和 x + 4。对于目标运行平台而言，则更倾向于选择性能更好的、优化程度更高的。

怎么选择很多时候是要符合大众审美标准和期望的，标准并不唯一，比如在 InstructionCombining 中会有比较多的体现，有 Canonicalize boolean +/- a constant to a select，作者在描述中就写了一段关于选用 select (IR 指令，用来作为条件判断选择，类似三元运算符，原始版本是 zext 转换类型加上 add/sub 得到 bool 的判断值) 作为 canonical form 的声明：

(I think it's reasonably clear that we want to have a canonical form for constructs like this; if anyone thinks that a select is not the best canonical form, please tell me.)

大意是，是否认可 select 指令作为此方案中最佳的 canonical form，可以和作者探讨。后来有人发现会影响到生成的指令，然后又去掉了一部分实现。关于怎么选也会涉及到很多的讨论，如 IR canonicalization: vector select or shufflevector?，所以标准要适用和适时。

2.1、冗余消除

x * 2 和 x + x 等价，似乎为了性能更好，我们应当选用 x + x，但实际上它对于后续的优化更加困难。对于同一变量的多处使用会让优化变得复杂，如在依赖图里，这会更像一个 DAG(Directed Acyclic Graph，有向无环图)，而不是树状的，树状可以更简单地进行优化。综合性能考虑，考虑使用 x << 1 会更好。

虽然要关注性能，但我们也可以推迟到代码生成(codegen) 再去思考，最重要的是保证后续的优化可以有效进行。转换成 canonical form 优化之后，对于代码生成也有好处，因为它只需要识别其中一种表达然后生成代码即可。

通常 canonicalization 操作会作为优化器执行的一部分，它本身也专注于生成更优化的代码。canonicalization 消除了不必要的变量，使得后续的优化更加简单。那么冗余消除(redundancy elimination) 本身是 canonicalization 操作，还是优化操作？

冗余消除可以减少重复计算、复用变量值，不过是否对后续优化有帮助还需要视情况而定。一个有好处的例子是消除了重复的取内存操作；一个不好的例子是把只有一次值使用的表达式树，变成对值的多次复用，比起树状，一些优化是很难在 DAG 下进行的。一般我们认为冗余消除是 canonicalization 操作，通过复制代码，把变量复用变成单次值使用是很简单的，但反过来就难了。

3、应用

实际上不只是运算表达式存在对 canonicalization 的应用，在很多地方也会有运用到，前面提到的 -O1 对控制流的重写也是其中一种。

DCE(dead code elimination) 也是其中一种，它的无用代码的 canonical form 就是没有代码(no code)。

在对循环体转换(loop-transforming)时，它其中一种的 canonical form 是 Loop Simplify Form，由 LoopSimplify(-loop-simplify) 这个 pass 实现，pass managers 在调度 LoopPass 时会自动把 LoopSimplify 加到其中。上面说的是其中一种，LLVM 中还有另一种 canonical form 是 Loop Rotation form，有机会写写，这里不做展开。

激进的或者说是过度的 canonicalization 实际上也可能对后续优化造成影响，比如对于源码的指令排列顺序的信息，可能会被去除掉，但是对于后续生成机器码时，这部分信息对于优化 CPU 指令调度时有帮助的。虽然编译器足够智能，但优化指令调度是 NP 完全问题，编译器不总能找到最佳方案，可能就会影响到程序性能。

总的来说，canonicalization 已经成为许多优化当中一个重要的组成部分了。

参考

• Canonicalization - sunfishcode
• Canonicalization - wiki
• Understanding Compiler Optimization
• Left-interpretation-of-an-expression-tree-right-generated-LLVM-IR
• Canonicalize boolean +/- a constant to a select
• Remove a instcombine transform that (no longer?) makes sense
• IR canonicalization: vector select or shufflevector?
• Operation Canonicalization - MLIR