机器无关的优化.ppt

框架的特性框架是单调的，但不是可分配的；半格的高度是有限的；可以使用通用的数据流分析算法来解决这个问题。部分冗余消除目标：尽量减少表达式求值的次数对于表达式x+y公共表达式：如果对x+y求值前的程序点上x+y可用，那么我们不需要再对x+y求值；循环不变表达式：循环中的表达式x+y的值不变，可以只计算一次；部分冗余：在程序按照某些路径到达这个点的时候x+y已经被计算过，但是沿着另外一些路径到达时，x+y尚未计算过处理方法：移动对x+y求值的位置；需要使用四个数据流方程来达到优化的目的冗余的例子允许进行两种操作在关键边上增加基本块；进行代码复制关键边：从具有多个后继的结点到达具有多个前驱的结点懒惰代码移动目标：所有不复制代码就可消除的冗余计算都被消除优化后的代码不会执行原程序中不执行的任何计算表达式的计算应该尽量靠后，以利于寄存器的分配试图通过在流图中放置表达式x+y的拷贝，使得某处的x+y成为完全冗余，从而删除；问题的简化：假设每个基本块只包含一个指令；基本步骤按照如下四个步骤进行处理找出各个程序点上预期执行的所有表达式即运行到某程序点时，有哪些表达式将来一定会执行重新放置表达式，使得表达式在某些点上变成可用的；这些点上的表达式可以删除在保证不会引入冗余的情况下，设法把表达式后延消除只使用一次的临时变量；预处理在关键边上插入新的基本块；我们只允许在基本块开头增加代码；例子图9-33（完整版）预期执行表达式数据流分析框架逆向当表达式B在出口处预期执行，且它没有被B杀死，那么此表达式在B的入口处被预期执行当B的所有后继基本块的入口处都被预期执行，那么表达式在出口处被预期执行在整个程序的出口处，没有表达式被预期执行；求出预期执行点之后，表达式被放置到首次被预期执行的程序点上此时一些表达式变得完全冗余；可用表达式（考虑代码复制）和前面的可用表达式类似，但是假设代码已经被复制到了预期执行点上表达式在基本块的出口处可用的条件条件一：在基本块的入口处可用；在基本块的入口处的预期执行表达式中没有被这个基本块杀死在一个基本块的开头放置的表达式：earliest[B]=anticipated[B].in–available[B].in所有预期执行的表达式，只要它（在放置后）不冗余则放置在B的开头；没有被放置的实际上被删除了。可后延表达式（1）保持程序语义且最小化冗余的情况下，尽可能延后计算表达式的时刻表达式x+y可以后延到p的条件所有从程序入口到达p的路径中都会碰到一个位置较前的x+y，并且在最后一个这样的位置之后没有使用x+y；右边的例子前面的处理把b+c放到了B1处；b+c可以后延到B4?B7的边上；可后延表达式（2）程序的入口处没有“后延”表达式如果一个表达式在B中没有被用到且可以后延到B的入口处、或者在earliest[B]中，它就可以被后延到B的出口处；只有一个基本块的所有前驱结点的出口处都包含了某个表达式，这个表达式才可以被后延到这个基本块的入口处；最终表达式将被放在边界上，即表达式从可后延变成不可后延的地方；x+y在B的入口处的earliest集合或可后延集合中且：e不在B的出口处的可后延集合中，或e不能被后延到B的某个后继基本块被使用的表达式确定一个被引入的临时变量是否在它所在基本块之外的其它地方使用综合步骤在每个关键边上出入空基本块计算出anticipated[B].in的值计算出avaiable[B].in的值计算最早放置位置：earliest[B]=anticipated[B].in–available[B].in计算postponable[B].in计算最后放置集合：Latest[B]=(earliest[B]∪postphonable[B].in)∩(e_useB∩┓(…)))计算出所有used[B].out的值对于每个表达式x+y作如下处理创建x+y的临时变量t；如果x+y在latest[B]∩used[B].out中，把t=x+y加入到B的开头如果x+y在e_useB∩（┓latest[B]∪used.out[B])中，用t替换B中的x+y。流图中的循环循环的重要性在于程序的大部分执行时间都花在循环上。相关概念支配结点深度优先排序回边图的深度可归约性支配结点如果每一条从入口结点到达n的路径都经过d，我们就说d支配(dominate)n，记为ddomn。右图：2只支配自己3支配除了1，2之外的其它所有结点4支配1、2、3之外的其它结点；5、6只支配自身7支配7,8,9,10