Arya

第八章 代码优化(二) note
第八章 代码优化(二) note可用表达式分析可用表达式如果从流图的首节点到达程序点p的每条路径都对表达式x op...
扫描右侧二维码阅读全文
10
2019/02

第八章 代码优化(二) note

第八章 代码优化(二) note

可用表达式分析

可用表达式

  • 如果从流图的首节点到达程序点p每条路径都对表达式x op y进行计算,并且从最后一个这样的计算到点p之间没有再次对x或y定值,那么表达式x op y在点p可用的(available)

表达式可用的直观意义

  • 在点p上,x op y已经在之前被计算过,不需要重新计算

可用表达式信息的主要用途

  • 消除全局子表达式

Image10-1.png

如果在B3的入口处的表达式4*i是可用表达式的话,那么B3中的4*i就是一个全局子表达式,就可以被删除掉,故有图二

  • 进行复制传播

Image10-2.png

可用表达式的传递函数
对于可用表达式数据流模式而言,如果基本块B对x或者y进行了(或可能进行)定值,且以后没有重新计算x op y,则称B杀死表达式x op y。如果基本块B对x op y进行计算,并且之后没有重新定值x或y,则称B生成表达式x op y

Image10-3.png

e_genB的计算

Image10-4.png

e_killB的计算

  • 初始化:e_killB = Φ
  • 顺序扫描基本块的每个语句:z = x op y
    从e_killB 中删除表达式x op y
    把所有和z相关的表达式加入到e_killB 中

可用表达式的数据流方程

Image10-5.png

计算可用表达式的迭代算法

Image10-6.png

支配结点和回边

支配结点(Dominators)

  • 如果从流图的入口结点到结点n的每条路径都经过结点d,则称结点d支配(dominate)结点n,记为d dom n

我们也可以得出,每个节点都支配它自己

Image10-7.png

分析上图,因为结点1是这个图的入口结点,因此支配所有结点,即,1~10;因为控制可以从1号结点直接到3号结点,可以不过2号结点,因此2号结点只能够支配它自己;3号结点可以支配除了1和2以外的所有几点,即,3~10;4号结点可以支配除了除了结点1、2和3号以外的所有结点;5号和6号结点只能支配她们自己;7号结点可以支配7~10号结点;8号结点可以支配8~10号结点;9号和10号结点只能支配它们自己

我们通常用支配结点树来表示支配的信息

直接支配结点 (Immediate Dominator)
从入口结点到达n的所有路径上,结点n的最后一个支配结点称为直接支配结点

寻找支配结点

Image10-8.png

举了一个例子

Image10-9.png

回边(Back Edges)

  • 假定流图中存在两个结点d和n满足d dom n。如果存在从结点n到d的有向边n→d,那么这条边称为回边

Image10-10.png

自然循环以及其识别

自然循环(Natural Loops)
从程序分析的角度来看,循环在代码中以什么形式出现并不重要,重要的是它是否具有易于优化的性质

  • 自然循环是满足以下性质的循环
    有唯一的入口结点,称为首结点(header)首结点支配循环中的所有结点,否则,它就不会成为循环的唯一入口
    循环中至少有一条返回首结点的路径,否则,控制就不可能从“循环”中直接回到循环头,也就无法构成循环

Image10-11.png

自然循环的识别

  • 给定一个回边n → d,该回边的自然循环为:d,以及所有可以不经过d而到达n的结点。d为该循环的首结点

Image10-12.png

这里简单分析一下4→3这条回边对应的自然循环:
首先将这条会变对应的结点,3号和4号结点放在循环中,4号结点还有一个前驱7号结点,因此7号结点可以到达4号结点,因此将7号结点放入循环中,接下来找7号结点的前驱结点为5、6和10号结点,5号和6号结点的前驱结点都是4号结点且都已经在循环中,10号结点的前驱结点是8号结点,因此8号也放入循环中,故,得上图

根据以上分析我们可以得到自然循环的算法

Image10-13.png

自然循环的重要性质

  • 除非两个自然循环的首结点相同,否则,它们或者互不相交,或者一个完全包含(嵌入)在另外一个里面

Image10-14.png

  • 如果两个循环具有相同的首结点,那么很难说哪个是最内循环。此时把两个循环合并

删除全局公共子表达式和复制语句

  • 可用表达式的数据流问题可以帮助确定位于流图中p点的表达式是否为全局公共子表达式

Image10-15.png

全局公共子表达式删除算法

Image10-16.png

删除复制语句

  • 对于复制语句s: x=y,如果在x的所有引用点都可以用对y的引用代替对x的引用(复制传播),那么可以删除复制语句 x=y

Image10-17.png

在x的引用点u用y代替x (复制传播)的条件:

  • 复制语句s: x=y在u点“可用”

删除赋值语句的算法

Image10-18.png

代码移动

代码移动

  • 循环不变计算的检测
  • 代码外提

循环不变计算检测算法

Image10-19.png

代码外提
前置首结点 (preheader)

  • 循环不变计算将被移至首结点之前,为此创建一个称为前置首结点新块。前置首结点的唯一后继首结点,并且原来从循环L外到达L首结点的边都改成进入前置首结点。 从循环L里面到达首结点的边不变

Image10-20.png

作用于归纳变量的强度削弱

  • 对于一个变量x ,如果存在一个正的或负的常量c,使得每次x被赋值时,它的值总是增加c ,则称x为归纳变量
  • 如果循环L中的变量i 只有形如i =i+c的定值(c是常量),则称i为循环L的基本归纳变量
  • 如果j = c×i+d,其中i是基本归纳变量,c和d是常量,则j也是一个归纳变量,称j属于i族,基本归纳变量i属于它自己的族
  • 每个归纳变量都关联一个三元组。如果j = c×i+d,其中i是基本归纳变量,c和d是常量,则与j相关联的三元组是( i, c, d )

Image10-21.png

归纳变量检测算法

Image10-22.png

Image10-23.png

作用于归纳变量的强度削弱算法

Image10-24.png

接下来举一个例子

Image10-25.png

归纳变量的删除

  • 对于在强度削弱算法中引入的复制语句j=t,如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用,并且j在循环的出口处不活跃,则可以删除复制语句j=t

Image10-26.png

其实这里就相当于是删除了不需要的代码,节省空间

仅用于测试的归纳变量

  • 对于在强度削弱算法中引入的复制语句j=t,如果在归纳变量j的所有引用点都可以用对t的引用代替对j的引用,并且j在循环的出口处不活跃,则可以删除复制语句j=t
  • 强度削弱后,有些归纳变量的作用只是用于测试。如果可以用对其它归纳变量的测试代替对这种归纳变量的测试,那么可以删除这种归纳变量
  • 对于仅用于测试的基本归纳变量i,取i族的某个归纳变量j(尽量使得c、d简单,即c=1或d=0的情况)。把每个对i的测试替换成为对j的测试
    ( relop i x B )替换为( relop j c * x+d B ),其中x不是归纳变量,并假设c>0
    ( relop i1 i2 B ),如果能够找到三元组j1 ( i1, c, d )和j2 ( i2, c, d ),那么可以将其替换为( relop j1 j2 B ) (假设c>0 )。否则,测试的替换可能是没有价值的
  • 如果归纳变量i不再被引用,那么可以删除和它相关的指令

Image10-27.png

Last modification:February 10th, 2019 at 08:20 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment