常量传播
Last updated
Last updated
常量传播的目的在于发掘代码中可能存在的常量，尽量用对常量的引用替代对虚拟寄存器的引用(虚拟寄存器和变量是同一个概念，以下都使用变量)，并尽量计算出可以计算的常量表达式。
为了实现常量传播，类比于前两种数据流，不难想象常量传播的数据流是"可用常量分析"，找出在一条语句处有哪些对变量赋的常量值可以到达。每一条涉及到赋值的语句处，杀死之前与左端项相关的赋值，如果右端项为变量则生成对左端项的变量赋值；反之如果对左端项赋予了一个常量值或者常量表达式，则生成对左端项的常量赋值。
形式化地，常量传播的值集是的函数的集合。其中是变量，是集合，它用来表示变量在一个程序点处的取值。其中表示已知它的值不是一个常量；表示不知道它的取值，出现是因为这个程序点处这个变量尚未赋值。
如果你觉得函数太抽象了，可以认为值集就是一个元素类型为的数组，用变量的id为下标访问，实际上也是这么实现的。
这个数据流和其他数据流有一个很大的区别：它的值集的大小是无限的。不过这并不影响数据流分析算法的收敛性，感兴趣的同学可以自己查阅相关的资料。
单条语句的传递函数定义为：设(注意和都属于值集，所以它们都是函数)，对于语句：
如果没有给任何变量赋值，则
否则，设对变量赋值了(假设一条语句最多只能给一个变量赋值)，则，此外：
如果赋值的右端项是常数，则
如果赋值的右端项是表达式(是任意一个运算符，也不仅局限于两个运算数的情况，单目运算和复写语句都可以归于此类，规则是类似的)则：
如果和都是常数，则
如果和中有一个是，则
否则，
否则，，这里可能包括赋值的右端项是函数的返回值，是访存的结果之类的，在简单的优化器中都直接认为这些结果不是常数
当两个基本块交汇的时候，对于每个变量，需要考虑以下几种情况：
如果两个基本块末尾处它都是常量，且两个常量值相等，则交汇结果为这个常量
一旦出现了这样的情形，可能意味着后续程序中有使用未赋初值就使用一个变量的行为，优化器可以依据"未赋初值的变量可以有任何取值"，认为这个取值就是另一个基本块的常量值，从而就回到了前一种情形
这个交汇操作用格图表示如下：
实际的编译器中，对于这样的情形往往会汇报一个警告。你可能会发现，有些情况下编译的优化等级开高了之后会产生一些新的警告。这也许就是编译器在高等级的优化下，进行各种数据流分析的时候发现了程序的漏洞。
完成了数据流分析之后，对于每一条语句，可以得到这条语句处所有变量的取值，把这条语句用到的所有值是常数的变量都换成对应的常数。此外，如果基本块结尾处的条件跳转的条件也是常数，就可以把这个条件跳转替换成无条件跳转，这可能导致一些原先认为可达的基本块变成不可达的，所以可以调用simplify函数来删除不可达的基本块。
根据上面描述的交汇规则，下面使用a的地方会认为a是常量100。出现这个结果的直接原因是这样的tac本来就不能算作合法，VTBL<C>和100本来就不应该以同样的方式被使用，既然是不合法的程序，优化后语义发生变化也是很正常的；更根本的原因是tac中没有类型信息，导致这样的不合法的tac看起来还挺合法的。
你可能觉得
VTBL<C>是地址，地址和整数混用没有什么问题，然而这只是在机器码层面没有什么问题，任何设计良好的ir中，地址和整数一定是不能混用的，它们之间的相互转换一定是有对应的指令的，哪怕这条指令最终并不生成任何机器码，在分析过程中它也是必要的。
如果一个基本块末尾处它是常量，另一个基本块结尾处它是，则交汇结果为这个常量
如果两个基本块末尾处它都是，则交汇结果为
否则，交汇结果为
数据流分析过程中，执行运算时会有一个corner case，即除/模0的情况。为了简单起见，这样的运算结果我们直接认为是0，这其实就是编译器对于未定义行为的一种处理策略。关于未定义行为，死代码消除一章也有对应的描述。
框架中，初值为对除了传入参数之外的所有变量都赋值，这表示目前还不知道任何关于它的信息；对于表示传入参数的变量赋值，因为参数一定不是常数(我注意到很多相关资料中都没有提到这一点，但是这一点对于编写实际的优化程序来说是不能忽略的)。
简单起见，实验框架只实现了对整数的常量传播，而像字符串，虚表这些地址则没有实现，统一用来表示。这也就意味着，假设出现这样的代码：
