DAG（有向无环图），也是编译器表示程序代码的一种数据结构。

跟抽象语法树（AST）相比，DAG可以发现程序里的公共子表达式，因而可以对代码进行更细致的优化。

AST节点的父节点只有1个，但DAG节点的父节点可以有多个。

在构造DAG节点之前，先查找以前的DAG节点是否有同样的：如果有则返回之前的节点，如果没有才会创建新的DAG节点。

如果有多个同样的子表达式只会创建1个DAG节点，自然机器码也只需要生成一次，从而提高了程序的运行速度。

例如：

int f(int i)

{

return i / 3 + i / 3;

}

这段代码的AST和DAG如下两图所示：

AST

可以看出，在DAG里两个子表达式 i / 3 只出现了1次，而在AST里出现了2次。

DAG的除法运算符 / 则有2个父节点，表示更上层的加法运算的两个数都是同样的子表达式。

如果直接生成代码的话，AST的代码是：

t0 = i / 3，

t1 = i / 3，

return t0 + t1.

而DAG的则少了一次除法运算，如下：

t = i / 3，

return t + t.

DAG

把中间代码转化成DAG，然后再转化回去，就可以优化掉程序里的公共子表达式。

生成DAG时最关键的只有一点：什么样的DAG节点是同样的子表达式？

i / 3 + i / 3的两个i / 3是同样的子表达式，因为在计算两个i / 3时变量i的值都没有改变过，所以之前计算出来的结果仍然可以使用。

但a = a + b，b = a - b，a = a - b，这3个式子里的a - b就不是同样的子表达式，因为（两次计算a - b时）变量b的值被赋值运算改变了。

也就是说，在判断是否是“公共的子表达式”时，两次计算时操作数的值必须一样。

即：两次计算的间隔内不能有对相关操作数的赋值运算或读、更新、写运算。

=、+=、++、--，这类的运算都是不可以的。

在生成DAG之后，还可以根据变量活跃情况进一步的优化。例如：

int g(int i, int j)

{

i += 1;

j += 2; // 无效的死代码

return i / 5 + i / 5;

}

这段代码的DAG如下：

从DAG图上可以清晰地看出来，右侧的表达式 j += 2与return语句无关。

函数出口的活跃变量只有return语句生成的临时变量，即加法运算的结果t = i / 5 + i / 5。

j += 2这行代码只涉及到变量j，它与return语句无关，在函数的出口不活跃。

上面代码的DAG

只需要以return为根节点把DAG再转化成中间代码，就可以去掉无效的语句j += 2。

scf编译器框架的DAG优化，有2个文件：

scf_dag.c，DAG的算法实现，

scf_optimizer_basic_block.c，对基本块的DAG优化。

到这里，编译器后端的机器无关优化就都说完了。

机器无关优化，是指与CPU指令集无关的优化（它不受CPU型号的限制）。

接下来，就是寄存器分配和机器码生成。

寄存器分配我之前写文章说过的，机器码生成则非常的无聊，按照intel手册编码就行。

然后，把生成的机器码按照ELF文件的格式写到文件里，就是编译完成的目标文件（.o）。

最后，把.o文件连接起来就是可执行文件（可以在shell里直接运行）。