规范化(Canonicalization)

type

status

date

slug

summary

Intro

很多代码结构都可以用多种方法编写。比如：

规范化就是说选择一种形式作为规范形式，然后在整个program中，将所有与规范形式等价的code，重写为规范形式。

在上面的例子中，通常选择在最右侧有一个常数的形式，所以上面的code都会被重写为x+4 。

Why is canonicaliztion useful?

规范化的目标是提升后续的优化的效率。这是非常关键的，后面我们会具体讨论。抛开这点，也有大量的情况，这样做是有明显的好处的。将所有等价的code重写成其规范形式，意味着后续的优化只用考虑这一种pattern，而不需要去搜索所有的pattern。

换句话说，规范化会把所有x+4可能的其它形式都重写为x+4，这样后续的优化就只用考虑x+4这一种形式，而不用去查找所有其它形式。

How do we choose a canonical from?

2+3的规划形式是5 ，因为这显然是最简单的形式。

但有时就是随便选一个，比如x+4 和 4+x ，选哪个差别其实不大，但是重要的是选一个作为规范形式。所以有时候，更多是看人的美感。

我们很容易会选择在目标机器平台上面最快、最优的形式。确实有时候最快和最简单是一致的，比如将 2+3 规范化 5 ，但也有不一致的时候。

Yeah so what about `x * 2` …

x * 2 和 x + x 是等价的，那应该选择哪个作为规范形式呢？此时可能有人会说：选在目标机器架构上面最优的那个。通常加法要比乘法快，因此这样的话就会选择 x + x 。

但是， x + x 有可能会使后续优化更加困难，因为在 x + x 中， x 有多处使用的地方。如果有多处使用的地方，使得依赖图是一个DAG，而不是一棵树，而通常来说，树要比DAG好处理。所以 x * 2 实际上可能是更好的规范形式，即使他不是最优的（对于目标机器）。

那么，我们也可以考虑将其规范为 x << 1 ，这样，x不仅只用一个usage, 同时也暗示了结果的最低位是0.

在目标机器上的执行效率肯定也是需要关心的，但是我们可以把这个关心推迟到codegen阶段，此时就后续的优化就没那么重要了。在codegen阶段，我们就需要依据哪个的执行效率更高来选择使用 + 、 * 还是 << 了。

规范化的基本哲学是：规范化形式应该是最有利于进行后续中间层优化（mid-level optimizations）的形式。需要指出的是，规范会对codegen本身也是有益的，也是因为不用去识别 x<<1的所有形式。

这里也是容易引起混淆的地方：规范化和优化是一个意思吗？规范化通常也是“优化器”的一部分，并且其中的很多工作也确实能直接产生更优的代码。但是从本质来上讲，规范化只专注与去掉非必要的等价形式，使得后续的优化能够更简单。

Sometimes it’s ambiguous: redundancy elimination

冗余消除（redundancy elimination）是规范化还是优化？

显然，相比多次计算同样的值，一次计算然后在不同的地方使用会更简单。但是这是否利于后续优化呢？得看具体情况了。

有的情况是有帮助的，比如这个冗余消除同时也消除了冗余的memory access。此时，本质上而言，后续的任务/code就不用再检查依赖了，因为对应的memory access都已经被消除了。

有的情况有时没有帮助的，比如在所有value都只有一个usage的代码中，冗余消除可能会使得一些value有多个usage。由于后续的一些优化在DAG上的效果不如在树上，所以可能会导致最终的一些优化做不到。

但是我们通常认为，冗余消除是规范化的一部分。因为从多个usage转换为一个usage可以添加重复的值轻易完成，但反过来的化就需要一些分析了。

Even more ambiguous: inlining

Canonical form isn’t just for arithmetic expressions!

IR中的任何部分都可以是规范化的对象。

比如，对于control flow的规范化可能包含了对基本块进行Reverse Post-Order排序。这样做可以保证，无论用户怎么组织代码，最终都可以实施同样的优化。

死代码消除也是一种规范化，死代码的规范形式是没有代码。

有一些编译器对于循环的处理比较激进，它们会把尽可能一个大循环拆成多个小循环，并假设后面的pass会把这些小循环按照一定策略合并，使得其能充分利用寄存器和cache。

Canonicalization as compression

Excessive canonicalization

The theoretical shape of optimization.

编译器一般都是从一份人类的写的代码开始的。

不同的人有不同的审美，这导致不同的人在写等价的code时，最终的code也是不同的，然而对于编译起来说，这是无关紧要的。

所以编译器的第一步一般都是进行规范化，去除人在代码中的无用影响。

规范化是嵌套的。经常一个规范化的操作会又会触发另一个规范化的操作。如常量折叠可以嵌套进行。

虽然也许规范化无法做到Kolmogorov Complexity级别，但我们确实让程序更接近我们可能认为的其本质，即完成其需要做的事情的最简单形式。

让后编译器就可以开始优化，将规范形式重写为最优形式。

由于实际原因，编译器并不总是可以按照纯粹的规范化阶段和纯粹的优化阶段来构建，但这可以作为在实践中理解编译器的一个有用的参考点。

🙆‍♂️规范化(Canonicalization)