> For the complete documentation index, see [llms.txt](https://decaf-lang.gitbook.io/decaf-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://decaf-lang.gitbook.io/decaf-book/rust-kuang-jia-fen-jie-duan-zhi-dao/pa4-zhong-jian-dai-ma-you-hua/chang-liang-chuan-bo.md).

# 常量传播

## 原理

常量传播的目的在于发掘代码中可能存在的常量，尽量用对常量的引用替代对虚拟寄存器的引用(虚拟寄存器和变量是同一个概念，以下都使用变量)，并尽量计算出可以计算的常量表达式。

为了实现常量传播，类比于前两种数据流，不难想象常量传播的数据流是"可用常量分析"，找出在一条语句处有哪些对变量赋的常量值可以到达。每一条涉及到赋值的语句处，杀死之前与左端项相关的赋值，如果右端项为变量则生成对左端项的变量赋值；反之如果对左端项赋予了一个常量值或者常量表达式，则生成对左端项的常量赋值。

形式化地，常量传播的值集是$$R \rightarrow V$$的函数的集合。其中$$R$$是变量，$$V$$是集合$$变量的所有可能取值 \cup {NAC, UNDEF}$$，它用来表示变量在一个程序点处的取值。其中$$NAC$$表示已知它的值不是一个常量；$$UNDEF$$表示不知道它的取值，出现$$UNDEF$$是因为这个程序点处这个变量尚未赋值。

> 如果你觉得函数太抽象了，可以认为值集就是一个元素类型为$$V$$的数组，用变量的id为下标访问，实际上也是这么实现的。
>
> 这个数据流和其他数据流有一个很大的区别：它的值集的大小是无限的。不过这并不影响数据流分析算法的收敛性，感兴趣的同学可以自己查阅相关的资料。

单条语句的传递函数$$f\_S$$定义为：设$$m' = f\_S(m)$$(注意$$m$$和$$m'$$都属于值集，所以它们都是函数)，对于语句$$S$$：

* 如果$$S$$没有给任何变量赋值，则$$m' = m$$
* 否则，设$$S$$对变量$$x$$赋值了(假设一条语句最多只能给一个变量赋值)，则$$m'(y) = m(y), \forall y \in R, y \ne x$$，此外：
  * 如果赋值的右端项是常数$$c$$，则$$m'(x) = c$$
  * 如果赋值的右端项是表达式$$y \oplus z$$($$\oplus$$是任意一个运算符，也不仅局限于两个运算数的情况，单目运算和复写语句都可以归于此类，规则是类似的)则：
    * 如果$$m(y)$$和$$m(z)$$都是常数，则$$m'(x) = m(y) \oplus m(z)$$
    * 如果$$m(y)$$和$$m(z)$$中有一个是$$NAC$$，则$$m'(x) = NAC$$
    * 否则，$$m'(x) = UNDEF$$
  * 否则，$$m'(x) = NAC$$，这里可能包括赋值的右端项是函数的返回值，是访存的结果之类的，在简单的优化器中都直接认为这些结果不是常数

当两个基本块交汇的时候，对于每个变量，需要考虑以下几种情况：

* 如果两个基本块末尾处它都是常量，且两个常量值相等，则交汇结果为这个常量
* 如果一个基本块末尾处它是常量，另一个基本块结尾处它是$$UNDEF$$，则交汇结果为**这个常量**
  * 一旦出现了这样的情形，可能意味着后续程序中有使用未赋初值就使用一个变量的行为，优化器可以依据"未赋初值的变量可以有任何取值"，认为这个取值就是另一个基本块的常量值，从而就回到了前一种情形
* 如果两个基本块末尾处它都是$$UNDEF$$，则交汇结果为$$UNDEF$$
* 否则，交汇结果为$$NAC$$

这个交汇操作用格图表示如下：

![int\_lattice](/files/-Lq10gKqpOOWnABmbxtk)

## 框架中的实现

数据流分析过程中，执行运算$$y \oplus z$$时会有一个corner case，即除/模0的情况。为了简单起见，这样的运算结果我们直接认为是0，这其实就是编译器对于未定义行为的一种处理策略。关于未定义行为，死代码消除一章也有对应的描述。

> 实际的编译器中，对于这样的情形往往会汇报一个警告。你可能会发现，有些情况下编译的优化等级开高了之后会产生一些新的警告。这也许就是编译器在高等级的优化下，进行各种数据流分析的时候发现了程序的漏洞。

完成了数据流分析之后，对于每一条语句，可以得到这条语句处所有变量的取值，把这条语句用到的所有值是常数的变量都换成对应的常数。此外，如果基本块结尾处的条件跳转的条件也是常数，就可以把这个条件跳转替换成无条件跳转，这可能导致一些原先认为可达的基本块变成不可达的，所以可以调用`simplify`函数来删除不可达的基本块。

框架中，初值为对除了传入参数之外的所有变量都赋值$$UNDEF$$，这表示目前还不知道任何关于它的信息；对于表示传入参数的变量赋值$$NAC$$，因为参数一定不是常数(我注意到很多相关资料中都没有提到这一点，但是这一点对于编写实际的优化程序来说是不能忽略的)。

简单起见，实验框架只实现了对整数的常量传播，而像字符串，虚表这些地址则没有实现，统一用$$UNDEF$$来表示。这也就意味着，假设出现这样的代码：

```
  if (b) a = VTBL<C>
  else a = 100
  // use a
```

根据上面描述的交汇规则，下面使用`a`的地方会认为`a`是常量`100`。出现这个结果的直接原因是这样的tac本来就不能算作合法，`VTBL<C>`和`100`本来就不应该以同样的方式被使用，既然是不合法的程序，优化后语义发生变化也是很正常的；更根本的原因是tac中没有类型信息，导致这样的不合法的tac看起来还挺合法的。

> 你可能觉得`VTBL<C>`是地址，地址和整数混用没有什么问题，然而这只是在机器码层面没有什么问题，任何设计良好的ir中，地址和整数一定是不能混用的，它们之间的相互转换一定是有对应的指令的，哪怕这条指令最终并不生成任何机器码，在分析过程中它也是必要的。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://decaf-lang.gitbook.io/decaf-book/rust-kuang-jia-fen-jie-duan-zhi-dao/pa4-zhong-jian-dai-ma-you-hua/chang-liang-chuan-bo.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.