编译器笔记47-代码优化-基本块的优化

基本块的优化

很多重要的局部优化技术首先把一个基本块转换成为一个无环有向图(directed acyclic graph ， DAG)

基本块的DAG表示

例.png

基本块中的每个语句s都对应一个内部结点N

• 结点N的标号是s中的运算符；同时还有一个定值变量表被关联到N，表示s是在此基本块内最晚对表中变量进行定值的语句。
• N的子结点是基本块中在s之前、最后一个对s所使用的运算分量进行定值的语句对应的结点 。如果s的某个运算分量在基本块内没有在s 之前被定值，则这个运算分量对应的子结点就是代表该运算分量初始值的叶结点(为区别起见，叶节点的定值变量表中的变量加上下脚标0)
• 在为语句x=y+z构造结点N的时候，如果x已经在某结点M的定值变量表中，则从M的定值变量表中删除变量x。

基于基本块的DAG删除无用代码

从一个DAG上删除所有没有附加活跃变量（活跃变量是指其值可能会在以后被使用的变量）的根结点(即没有父结点的结点)。重复应用这样的处理过程就可以从DAG中消除所有对应于无用代码的结点。

例.png

数组元素赋值指令的表示

例.png

根据基本块的DAG可以获得一些非常有用的信息

• 确定哪些变量的值在该基本块中赋值前被引用过

  在DAG中创建了叶结点的那些变量

• 确定哪些语句计算的值可以在基本块外被引用

  在DAG构造过程中为语句s（该语句为变量x定值）创建的节点N，在DAG构造结束时x仍然是N的定值变量。

从DAG到基本块的重组

• 对每个具有若干定值变量的节点，构造一个三地址语句来计算其中某个变量的值

  倾向于把计算得到的结果赋给一个在基本块出口处活跃的变量(如果没有全局活跃变量的信息作为依据，就要假设所有变量都在基本块出口处活跃，但是不包含编译器为处理表达式而生成的临时变量)

• 如果结点有多个附加的活跃变量，就必须引入复制语句，以便给每一个变量都赋予正确的值。

例.png 例.png