1、第九章 机器无关的优化优化的主要来源 编译器只能通过一些相对低层的语义等价转换来优化代码；冗余运算的原因 源程序中的冗余；高级程序设计语言编程的副产品 比如Aij.f=0;Aij.k=1;中的冗余运算；语义不变的优化 公共子表达式消除 复制传播 死代码消除 常量折叠优化的例子（1）快速排序算法优化的例子（2）三地址代码Quicksort的流图 循环：B2 B3 B2、B3、B4、B5全局公共子表达式 如果E 在某次出现之前必然已经被计算过，且 E的分量在该次计算之后一直没有被改变，那么E的本次出现就是一个公共子表达式 如果上一次E的值赋给了x，且x的值至今没有被修改过，那么我们就可以使用x，而
2、不需要计算E；例子见左边t7=4*it10=4*j不需要重新计算；基本块内的公共子表达式全局公共子表达式的例子 右图 在B2、B3中计算了4*i和4*j 到达B5之前必然经过B2、B3；t2、t4在赋值之后没有被改变过，因此B5中可直接使用它们；t4在替换t8之后，B5：at8和B3：at4又相同；同样：B5中赋给x的值和B2中赋给t3的值相同；B6中的at13和B1中的at1不同，因为B5中可能改变a的值；消除公共子表达式后的结果复制传播 形如u=v的复制语句使得语句后面的程序点上，u的值等于v的值；如果在某个位置上u一定等于v，那么可以把u替换为v；有时可以彻底消除对u的使用，从而消除对u
3、的赋值语句；右图所示，消除公共子表达式时引入了复制语句；如果尽可能用t来替换c，可能就不需要c=t这个语句了。复制传播的例子 右图显示了对B5进行复制传播处理的情况 可能消除所有对x的使用死代码消除 如果一个变量在某个程序点上的值可能会在之后被使用，那么这个变量在这个点上活跃；否则这个变量就是死的，此时对这个变量的赋值就是没有用的死代码；死代码多半是因为前面的优化而形成的；比如，B5中的x=t3就是死代码；消除后得到at2=t5at4=t3goto B2x=t3at2=t5at4=t3goto B2=代码移动 循环中的代码会被执行很多次 循环不变表达式：循环的同一次运行的不同迭代中，表达式的值
4、不变 把循环不变表达式移动到循环入口之前计算可以提高效率 循环入口：进入循环的跳转都以这个入口为目标while(i=limit-2)如果循环体不改变limit的值，可以在循环外计算limit-2t=limit-2while(i=t)归纳变量和强度消减归纳变量 每次对x的赋值都使得x的值增加c，那么x就是归纳变量；把对x的赋值改成增量操作，可消减计算强度，提高效率；如果两个归纳变量步调一致，还可以删除其中的某一个；例子 如果在循环开始时刻保持t4=4*j 那么，j=j-1后面的t4=4*j每次赋值使得t4减4 替换为t4=t4 4;t2也可以同样处理继续优化 对t2强度消减 B4中对i和j的测试
5、可以替换为对t2,t4的测试数据流分析 数据流分析 用于获取数据沿着程序执行路径流动的信息的相关技术。是优化的基础 例如 两个表达式是否一定计算得到相同的值？（公共子表达式）一个语句的计算结果有没有可能被后续语句使用？（死代码消除）数据流抽象（1）程序点 三地址语句之前或之后的位置 基本块内部：一个语句之后的程序点等于下一个语句之前的程序点 如果流图中有B1到B2的边，那么B2的第一个语句之前的点可能紧跟在B1的最后语句之后的点后面执行；从p1到p2的执行路径：p1,p2,pn 要么pi是一个语句之前的点，且pi+1是该语句之后的点 要么pi是某个基本块的结尾，且pi+1是该基本块的某个后继的
6、开头。数据流抽象（2）出现在某个程序点的程序状态：在某个运行时刻，当指令指针指向这个程序点时，各个变量和动态内存中存放的值 指令指针可能多次指向同一个程序点 因此一个程序点可能对应多个程序状态 数据流分析把可能出现在某个程序点上的程序状态集合总结为一些特性；不管程序怎么运行，当它到达某个程序点时，程序状态总是满足分析得到的特性；不同的分析技术关心不同的信息；为了高效、自动地进行数据流分析，通常要求这些特性能够被高效地表示和求解；例子（1）路径 1,2,3,4,9 1,2,3,4,5,6,7,8,9 第一次到达(5)，a=1；第二次到达(5)，a=243；且之后都是243。我们可以说：点(5)具
7、有特性a=1 or a=243。表示成为性质和算法 根据不同的需要来设置不同的性质集合；然后设计分析算法 程序点上的性质被表示成为数据流值；求解这些数据流值的过程实际上就是推导这些性质的过程 例子 如果要求出变量在某个点上的值可能在哪里定值，可以使用到达定值(reaching definition)性质形式：x由d1定值 如果希望实现常量折叠优化，我们关心的是某个点上变量x的值是否总是由某个特定的常量赋值语句赋予的。性质形式：x=c，以及x=NAC 分析得到的性质集合应该是一个安全的估计值 即根据这些性质进行优化不会改变程序的语义数据流分析模式 数据流分析中，程序点和数据流值关联起来 数据流值
8、表示了程序点具有的性质；和某个程序点关联的数据流值：程序运行中经过这个点时必然满足的这个条件；域 所有可能的数据流值的集合称为这个数据流值的域 不同的应用选用不同的域；比如到达定值：目标是分析在某个点上，各个变量的值由哪些语句由哪些语句定值；因此数据流值是定值（即三地址语句）的集合，表明集合中的定值对某个变量定值了。数据流分析 对一组约束求解，得到各个点上数据流值。约束分成两类：基于语句和基于控制流 基于语句语义的约束 一个语句之前和之后的数据流值受到该语句语义的约束；语句语义通常用传递函数表示，它把一个数据流值映射为另一个数据流值；INs=fs(OUTs)（逆向）OUTs=fs(INs)（正
9、向）基于控制流的约束 在基本块内部，一个语句的输出和下一语句的输入相同；流图的控制流边也对应新的约束例子（1）假设我们考虑各个变量在某个程序点上是否常量 s是语句x=3；考虑变量x，y，z；INs：x:NAC;y:7;z:3 那么OUTs就是：x:3；y:7；z:3 如果 s是x=y+z，OUTs是？s是x=x+y，OUTs是？例子（1）设有如右图的流图 且数据流值 OUTs1：x:3，y:4，z:NAC OUTs2：x:4，y:3，z:NAC 则 INs：x:NAC，y:NAC，z:NAC OUTs是什么？能推出z:7吗?s1:x=3s2:y=3x=4;y=4;z=a+b;s:z=x+y基本
10、块上的数据流模式 基本块的控制流非常简单 从头到尾不会中断 没有分支 基本块的效果就是各个语句的效果的复合 可以预先处理基本块内部的数据流关系，给出基本块对应的传递函数；INB=fB(OUTB)或者 OUTB=fB(INB)设基本块包含语句s1,s2,sn；fB=fsn fs2 fs1基本块之间的控制流约束 前向数据流问题 B的传递函数根据INB计算得到OUTB；INB和B的各前驱基本块的OUT值之间具有约束关系；逆向数据流问题 B的传递函数根据OUTB计算INB；OUTB和B的各后继基本块的IN值之间具有约束关系；B1B3BB2前向数据流的例子：假如：OUTB1：x:3y:4z:NAC OU
11、TB2：x:3y:5z:7 OUTB3：x:3y:4z:7则：INB：x:3y:NACz:NAC数据流方程解的精确性和安全性 数据流方程通常没有唯一解。目标是寻找一个最“精确的”、满足约束的解 精确：能够进行更多的改进 满足约束：根据分析结果来改进代码是安全的到达定值（1）到达定值 如果存在一条从定值d后面的程序点到达某个点p的路径，且这条路径上d没有被杀死，那么定值d到达p 杀死：路径上对x的其他定值杀死了之前对x的定值；考虑到间接赋值，如果定值可能不是对x进行复制，则不能杀死这个定值 直观含义 如果d到达p，那么在p点使用的x的值就可能是由d定值的。到达定值（2）到达定值的解允许不精确，但
12、必须是安全的 分析得到的到达定值可能实际上不会到达；但是实际到达的一定被分析出来，否则不安全 用途：确定x在p点是否常量 忽略实际的到达定值使得变化的值被误认为常量；将这些值替换为常量会引起错误，不安全 过多估计则相反 确定变量是否先使用后定值到达定值的例子 B1中全部定值到达B2的开头；d5到达B2的开头（循环）d2被d5杀死，不能到达B3、B4的开头；d4不能到达B2的开头，因为被d7杀死；d6到达B2的开头语句/基本块的传递方程（1）定值 d:u=v+w 生成了对变量u的定值d；杀死其他对u的定值；生成-杀死形式：fd(s)=gend(x-killd)gend=d，killd=程序中其他
13、对u的定值 生成-杀死形式的函数的并置（复合）仍具有这个形式 f2(f1(x)=gen2 (gen1 (x-kill1)-kill2)=(gen2(gen1-kill2)(x-kill1kill2)生成的定值：由第二部分生成、以及由第一个部分生成且没有被第二部分杀死；杀死的定值：被第一部分杀死的定值、以及被第二部分杀死的定值语句/基本块的传递方程（2）设B有n个语句，第i个语句的传递函数为fi fB(s)=genB(x-killB)genB=genn(genn-1-killn)(genn-2-killn-1-killn)(gen1-kill2-kill3-killn)killB=kill1ki
14、ll2 killn killB 为被B各个语句杀死的定值的并集 genB是被第i个语句生成，且没有被其后的句子杀死的定值的集合gen和kill的例子 基本块：d1:a=3 d2:a=4 gen集合：d2 kill集合：流图中所有针对a的定值到达定值的控制流方程 只要一个定值能够沿某条路径到达一个程序点，这个定值就是到达定值；INB=P是B的前驱基本块OUTP 如果从基本块P到B有一条控制流边，那么OUTP在INB中；一个定值必然先在某个前驱的OUT值中，才能出现在B的IN中 称为到达定值的交汇运算符P1P3BP2d:x=y+zdd此路径上x不一定被覆盖控制流方程的迭代解法（1）ENTRY基本块
15、的传递函数是常函数；OUTENTRY=空集 其他基本块OUTB=genB(INB-killB)INB=P是B的前驱基本块OUTP 迭代解法 首先求出各基本块的gen和kill 令所有的OUTB都是空集，然后不停迭代，得到最小不动点的解控制流方程的迭代解法（2）输入：流图、各基本块的kill和gen集合 输出：INB和OUTB 方法：控制流方程的迭代解法（3）解法的正确性 直观解释：不断向前传递各个定值，直到该定值被杀死为止；为什么不会死循环？各个OUTB在算法执行过程中不会变小；且OUTB显然有有穷的上界；只有一次迭代之后增大了某个OUTB的值，算法才会进行下一次迭代；最大迭代次数是流图的结点
16、个数n 定值经过n步必然已经到达所有可能到达的结点 算法结束时，各个OUT/IN值必然满足数据流方程到达定值求解的例子7个bit从左到右表示d1,d2,dnfor循环时依次遍历B1,B2,B3,B4,EXIT每一列表示一次迭代计算；B1生成d1,d2,d3，杀死d4,d5,d6,d7B2生成d4,d5，杀死d1,d2,d7B3生成d6，杀死d3B4生成d7，杀死d1,d4活跃变量分析 活跃变量分析 x在p上的值是否会在某条从p出发的路径中使用；一个变量x在p上活跃，当前仅当存在一条从p点开始的路径，该路径的末端使用了x，且路径上没有对x进行覆盖。用途 寄存器分配/死代码删除/数据流值(活跃)变
17、量的集合基本块内的数据流方程 基本块的传递函数仍然是生成-杀死形式，但是从OUT值计算出IN值（逆向）useB，可能在B中先于定值被使用（GEN）defB，在B中一定先于使用被定值（KILL）例子：基本块：i=i+1;j=j-1 use i,j;def USEB和DEFB的用法 语句的传递函数 s:x=y+z uses=y,z defs=x-y,z/x=y+z是模板，y、z可能和x相同 假设基本块中包含语句s1,s2,sn，那么 useB=use1(use2-def1)(use3-def1-def2)(usen-def1-def2-defn-1)defB=def1def2defn活跃变量数据流
18、方程 任何变量在程序出口处不再活跃 INEXIT=空集 对于所有不等于EXIT的基本块 INB=useB(OUTB-defB)OUTB=S是B的后继基本块INS 和到达定值相比较 都使用并集运算作为交汇运算 数据流值的传递方向相反：因此初始化的值不一样活跃变量分析的迭代方法 这个算法中INB总是越来越大，且INB都有上界，因此必然会停机；可用表达式分析 x+y在p点可用的条件 从流图入口结点到达p的每条路径都对x+y求值，且在最后一次求值之后再没有对x或者y赋值 主要用途 寻找全局公共子表达式 生成-杀死 杀死：基本块对x或y赋值，且没有重新计算x+y，那么它杀死了x+y；生成：基本块求值x+
19、y，且之后没有对x或者y赋值，那么它生成了x+y；计算基本块生成的表达式 初始化S=从头到尾逐个处理基本块中的指令x=y+z 把y+z添加到S中；从S中删除任何涉及变量x的表达式 遍历结束时得到基本块生成的表达式集合；杀死的表达式集合 表达式的某个分量在基本块中定值，且没有被再次生成基本块生成/杀死的表达式的例子可用表达式的数据流方程 ENTRY结点的出口处没有可用表达式 OUTENTRY=其他基本块的方程 OUTB=e_genB(INB-e_killB)INB=P是B的前驱基本块OUTP 和其他方程类比 前向传播 交汇运算是交集运算可用表达式分析的迭代方法 注意：OUT值的初始化值是全集 这
20、样的初始集合可以求得更有用的解三种数据流方程的总结数据流分析的理论基础 问题：数据流分析中的迭代算法在什么情况下正确？得到的解有多精确？迭代算法是否收敛？方程组的解的含义是什么？基于群论，首先给出数据流模式的预期特性，并证明这些特性所蕴含的对上面问题的回答。数据流分析框架 数据流分析框架(D,V,F)D：方向，FORWARD、BACKWARD V，：半格，值域为V，交汇运算(meet)为 F：V到V的传递函数族 包含刻画边界条件的函数，包含单元函数 对于组合运算封闭，即如果f1和f2在F中，那么f1 f2仍然在F中。半格 半格的定义：对于V中所有的x,y,z：xx=x,xy=yx,x(yz)=
21、(xy)z 半格有顶元素T，对于所有的x，Tx=x 底元素，对于所有的x，x=x。半格的偏序 x y 当且仅当(xy)=x V中x和y的最大下界（glb）g x g y 如果z满足z x,z y，那么z g；性质：g=xy格图 值域 定值集合d1,d2,d3的超集 ：包含关系 交函数：并集运算到达定值中的传递函数 F：具有生成-杀死形式的函数f(x)=gen(x-kill)单元函数 gen和kill都为空的函数 对组合的封闭性 f1(x)=gen1(x-kill1)f2(x)=gen2(x-kill2)f2(f1(x)=gen2(gen1(x-kill1)-kill2)=gen2(gen1-k
22、ill2)(x-kill1kill2)框架的单调性和可分配性 单调框架 对于任意的x,y,f，x y 蕴含 f(x)f(y)可分配性 f(xy)=f(x)f(y)可分配性蕴含单调性 前面的几个数据流方程都是可分配的框架数据流框架的通用算法 前向 逆向一些有用的性质 如果算法收敛，那么得到的就是数据流方程组的一个解 如果框架是单调的，那么得到的解救是数据流方程组的最大不动点 方程组的任意其它解的IN和OUT值和这个解的对应值之间都有关系 如果框架是单调的，且高度有穷，那么迭代算法收敛；解的含义 理想解 基于交运算的解MOP IDEAL 最大不动点MFP和MOP解 MFP不会大于MOP解 因此MF
23、P不大于IDEAL解常量传播 常量传播 将每次运行总是得到相同常量值的表达式替换为该常量 常量传播数据流框架 数据流值的集合是无界的；不可分配 前向数据流问题数据流值域 数据流值的集合是一个乘积格，每个分量对应于程序中的一个变量；单个变量的格的元素包括：所有符合该变量类型的常量值 值NAC：not a constant，不是常量，有多种定值 方式；值UNDEF：未定义，还不能确定这个变量的任何信息，可能是某个常量，可能不是；交运算 分量格的交汇运算 UNDEF v=v NACv=NAC cc=c c1c2=NAC 乘积格的交汇运算 mm=m当且仅当 对于所有的变量v,m(v)m(v)=m(v)
24、。传递函数（1）常量传播框架的传递函数 参数：从程序变量到常量格中元素的映射 返回：相同类型的映射 ENTRY结点的常值传递函数 返回的映射对任意变量都给出UNDEF值；传递函数（2）语句的传递函数 s不是赋值语句：fs就是单元函数 s是对x的赋值，假设输入是m，输出是m m(v)=v(v)如果x不等于v 如果s的右部是常量，那么m(x)=c 如果右部是y+z，那么当m(y),m(z)都是常量值时，m(x)=m(y)+m(z)；如果有一个是NAC，m(x)=NAC；否则m(x)=UNDEF；如果右部是其它表达式，m(x)=NAC框架的特性 框架是单调的，但不是可分配的；半格的高度是有限的；可以
25、使用通用的数据流分析算法来解决这个问题。部分冗余消除 目标：尽量减少表达式求值的次数 对于表达式x+y 公共表达式：如果对x+y求值前的程序点上x+y可用，那么我们不需要再对x+y求值；循环不变表达式：循环中的表达式x+y的值不变，可以只计算一次；部分冗余：在程序按照某些路径到达这个点的时候x+y已经被计算过，但是沿着另外一些路径到达时，x+y尚未计算过 处理方法：移动对x+y求值的位置；需要使用四个数据流方程来达到优化的目的冗余的例子 允许进行两种操作 在关键边上增加基本块；进行代码复制 关键边：从具有多个后继的结点到达具有多个前驱的结点懒惰代码移动 目标：所有不复制代码就可消除的冗余计算都
26、被消除 优化后的代码不会执行原程序中不执行的任何计算 表达式的计算应该尽量靠后，以利于寄存器的分配 试图通过在流图中放置表达式x+y的拷贝，使得某处的x+y成为完全冗余，从而删除；问题的简化：假设每个基本块只包含一个指令；基本步骤 按照如下四个步骤进行处理 找出各个程序点上预期执行的所有表达式 即运行到某程序点时，有哪些表达式将来一定会执行 重新放置表达式，使得表达式在某些点上变成可用的；这些点上的表达式可以删除 在保证不会引入冗余的情况下，设法把表达式后延 消除只使用一次的临时变量；预处理 在关键边上插入新的基本块；我们只允许在基本块开头增加代码；例子图9-33（完整版）预期执行表达式 数据
27、流分析框架 逆向 当表达式B在出口处预期执行，且它没有被B杀死，那么此表达式在B的入口处被预期执行 当B的所有所有后继基本块的入口处都被预期执行，那么表达式在出口处被预期执行 在整个程序的出口处，没有表达式被预期执行；求出预期执行点之后，表达式被放置到首次被预期执行的程序点上 此时一些表达式变得完全冗余；可用表达式（考虑代码复制）和前面的可用表达式类似，但是假设代码已经被复制到了预期执行点上 表达式在基本块的出口处可用的条件 条件一：在基本块的入口处可用；在基本块的入口处的预期执行表达式中 没有被这个基本块杀死 在一个基本块的开头放置的表达式：earliestB=anticipatedB.in
28、 availableB.in 所有预期执行的表达式，只要它（在放置后）不冗余则放置在B的开头；没有被放置的实际上被删除了。可后延表达式（1）保持程序语义且最小化冗余的情况下，尽可能延后计算表达式的时刻 表达式x+y可以后延到p的条件 所有从程序入口到达p的路径中都会碰到一个位置较前的x+y，并且在最后一个这样的位置之后没有使用x+y；右边的例子 前面的处理把b+c放到了B1处；b+c可以后延到B4B7的边上；可后延表达式（2）程序的入口处没有“后延”表达式 如果 一个表达式在B中没有被用到 且可以后延到B的入口处、或者在earliestB中，它就可以被后延到B的出口处；只有一个基本块的所有前驱
29、结点的出口处都包含了某个表达式，这个表达式才可以被后延到这个基本块的入口处；最终表达式将被放在边界上，即表达式从可后延变成不可后延的地方；x+y在B的入口处的earliest集合或可后延集合中 且：e不在B的出口处的可后延集合中，或e不能被后延到B的某个后继基本块被使用的表达式 确定一个被引入的临时变量是否在它所在基本块之外的其它地方使用综合步骤在每个关键边上出入空基本块计算出anticipatedB.in的值计算出avaiableB.in的值计算最早放置位置：earliest B=anticipatedB.in availableB.in计算postponableB.in计算最后放置集合：L
30、atestB=(earliestB postphonableB.in)(e_useB ()计算出所有usedB.out的值对于每个表达式x+y作如下处理 创建x+y的临时变量t；如果x+y在latestB usedB.out中，把t=x+y加入到B的开头 如果x+y在e_useB（latestB used.outB)中，用t替换B中的x+y。流图中的循环 循环的重要性在于程序的大部分执行时间都花在循环上。相关概念 支配结点 深度优先排序 回边 图的深度 可归约性支配结点如果每一条从入口结点到达n的路径都经过d，我们就说d支配(dominate)n，记为d dom n。右图：2只支配自己 3支配
31、除了1，2之外的其它所有结点 4支配1、2、3之外的其它结点；5、6只支配自身 7支配7,8,9,10；8支配8,9,10；9，10只支配自身支配结点树 支配结点树可以表示支配关系 根结点：入口结点；每个结点d支配且只支配树中的后代结点 直接支配结点 从入口结点到达n的任何路径（不含n）中，它是路径中最后一个支配n的结点；前面的例子：1直接支配3，3直接支配4 n的直接支配结点m具有如下性质：如果d dom n，那么d dom m；寻找支配结点 求解如右图所示的数据流方程组，就可以得到各个结点对应的支配结点 D(n)=OUTn；深度优先排序 深度优先排序 先访问一个结点，然后遍历该结点的最右子
32、结点，再遍历这个子结点左边的子结点，依此类推 具体访问时，我们可以自己设定各个子结点的顺序 哪个是最右的，哪个是下一个子结点等 例子见右图：1,2,3,4,5,6,7,8,9,10深度优先生成树和排序算法 dfnn表示n的深度优先编号；c的值从n逐步递减到1；T中记录了生成树的边集合；流图的边的分类 前进边 从结点m到达m在DFST树中的一个真后代的边；DFST中的所有边都是前进边 后退边 从m到达m在DFST树中的某个祖先的边 交叉边 边的src和dest都不是对方的祖先；一个结点的子结点按照它们被加入到树中的顺序从左到右排列，那么所有的交叉边都是从右到左的。回边和可归约性 回边 边ab，头
33、b支配了尾a；每条回边都是后退边，但不是所有后退边都是回边；如果一个流图的任何优先生成树中的所有后退边都是回边，那么该流图就是可归约的；可归约流图的DFST的后退边集合就是回边集合；不可归约流图的DFST中可能有一些后退边不是回边，但是所有的回边仍然都是后退边；实践中出现的流图基本都是可归约的。流图的深度 一个流图，相对于一棵DFST，的深度 各条无环路径上后退边数中的最大值 这个深度不会大于直观上所说的流图中的循环嵌套深度。对于可归约的流图，我们可以使用“回边”来定义，而且可以说是“流图的深度”右边的流图深度为3 10743自然循环 自然循环的性质 有一个唯一的入口结点（循环头 header
34、）。这个结点支配循环中的所有结点 必然存在进入循环头的回边；自然循环的定义 给定回边nd的自然循环是d，加上不经过d就能够到达n的结点的集合；d是这个循环的头；自然循环构造算法 输入：流图G和回边nd;输出：回边nd的自然循环中的所有结点的集合loop；方法：loop=n,d,d标记为visited；从n开始，逆向地对数据流图进行深度优先搜索，把所有访问到的结点都加入loop，加入loop的结点都标记为visited。搜索过程中，不越过标记为visited的结点；自然循环的例子 回边：107 7,8,10 回边：74 4,5,6,7,8,10 包含了前面的循环 回边43,83 同样的头 同样的
35、结点集合3,4,5,6,7,8,10 回边91 整个流图自然循环的性质 除非两个循环具有同样的循环头，他们 要么互不相交（分离的）要么一个嵌套于另一个中 最内层循环 不包含其它循环的循环 通常是最需要进行优化的地方；数据流迭代算法的收敛速度（1）最大迭代次数是格的高度乘以流图结点数 对求值过程适当排序可以加速算法的收敛速度 一些数据流分析的迭代过程实际上是某个事实沿着路径传播的过程，且这个传播过程不需要考虑路径中的环路 到达定值：一个定值沿着路径传播，直到被杀死 可用表达式：表达式不可用的情况（尚未被计算/或者被杀死）沿着路径传播 活跃变量：变量被使用的事实沿着路径逆向传播数据流迭代算法的收敛
36、速度（2）调整访问结点的顺序，保证经过几轮访问就使得各个信息充分传递 前向数据流问题：按照深度优先顺序来访问for(按照深度优先顺序，对所有不同于ENTRY的基本块B)迭代测试不超过流图的深度加一 对于逆向数据流问题 按照深度优先顺序的逆序进行访问 迭代轮次不超过流图的深度加一传播的例子假设定值d按照路径35193516234541017(3,5,等是基本块的深度优先编号）第一轮迭代 从3传递到5、19、35；此时16已经被处理过了，因此不能继续传播第二轮迭代 162345第三轮迭代 41017传播过程总是按照递增序列传播；每轮迭代时，传播过程总是停在后退边上 因此迭代次数等于路径上的后退边数
37、量。基于区域的分析 从基本语句开始，为逐步增大的程序区域构造传递函数。该传递函数描述了该区域运行的情况 最终构造出整个过程的传递函数，然后直接得到数据流值 基于区域的分析技术需要以下元素 数据流值的半格 传递函数的半格 交汇运送、组合运算符、闭包运算符区域 程序被看作区域的层次结构 区域：流图中满足如下条件的结点集N和边集E N中有一个支配所有结点的头结点h 如果某个结点m能够不经过h到达N中的n，那么m也在N中；E是所有的、N中的任意两个结点之间的控制流边的集合；但是有些进入h的边可能不在其中；自然循环就是区域，但是区域可能不包括回边区域的例子 B1，B2和B1B2形成区域；B1、B2、B3
38、和B1B2、B2B3，B1B3形成一个区域 B2、B3和B2B3不形成区域 因为没有头结点可归约流图的区域层次结构 构造区域层次结构时，先找出所有自然循环 自然循环之间要么不相交，要么是包含关系 从最内层循环开始，逐渐把循环替换成为单个结点 循环L的循环体（除回边之外的所有结点和边）替换为一个结点，成为区域R（称为体区域）；到达循环头的边现在进入R；从L的出口结点出发的边变成了从R出发的边；回边变成了R上的一个圈；构造代表整个自然循环L的区域R（称为循环区域）包含R以及回边 不断重复这个步骤，直到把整个程序变成单个结点区域层次结构的例子叶子区域：R1,R2,R3,R4,R5;循环体区域：R6循
39、环区域：R7整个程序的区域：R8基于区域的分析技术的概述（1）对每个区域R及R中的每个子区域R，我们计算传递函数fR,INR，概括从R的入口到达R的入口的全部可能路径的运行效果 出口基本块 区域R内的基本块B有到R之外的边，B就是R的出口基本块 计算从R入口基本块到B的出口处的传递函数fR,OUTB。基于区域的分析技术的步骤（1）从最小的区域开始，为越来越大的区域计算传递函数 叶子区域的传递函数：fB,INB是单元函数，fB,OUTB是B的传递函数 逐步处理更大的R R是一个体区域 R是它的子区域组成的无环图；按照拓扑排序计算各个传递函数 R是循环区域 考虑回边的效果基于区域的分析技术的步骤（
40、2）最终得到整个程序的传递函数之后，按照相反顺序计算得到各个基本块入口处的数据流值 设R入口处的数据流值x，子区域R入口处的数据流值fR,INR(X)直到计算完成各个基本块的入口处的值传递函数的假设 需要三个作用于传递函数的基本运算 组合、交汇运算、闭包运算 组合 用于计算一个结点序列对应的传递函数 gen_kill模式的传递函数对组合封闭 交汇运算f(f1ff2)(x)=f1(x)f2(x)闭包预算 f*=n=0fn。对于gen_kill模式的传递函数ff*(x)=genx基于区域的分析算法 方法：构造区域序列R1,R2,Rn，其中Rn是顶层区域 按照自底向上顺序，处理各个区域 如果R是一个
41、基本块B，fR,INB=I,fR,OUTB=fB 如果R是循环体区域，执行子算法9-50a 如果R是循环区域，执行子算法9-50b 计算各个区域开始处的数据流值 INRn=INENTRY 自顶向下顺序：INR=fR,INR(INR)子算法 计算图9-48a中的到达定值基于区域的分析的例子gen_kill形式上的运算符 函数的交 Gen：gen的并集；Kill：kill集合的交集 组合 Gen：gen的并集减去kill2 Kill：Kill集合的并集 闭包 Gen：原来的gen Kill：空集计算传递函数 R1,R2,R5 fRi,INBi是单元函数，fRi,OUTBi是基本块的传递函数 处理R6 顺序处理R6的子区域R2,R3,R4 处理R7 计算相应的函数闭包 处理R8 顺序处理子区域R1,R7和R5自顶向下计算数据流值
