Arya

第八章 代码优化(一)note
第八章 代码优化(一)note流图流图的每一个节点都是基本块,所以先来介绍一下基本块。基本块(Basic Bloc...
扫描右侧二维码阅读全文
10
2019/02

第八章 代码优化(一)note

第八章 代码优化(一)note

流图

流图的每一个节点都是基本块,所以先来介绍一下基本块。
基本块(Basic Block)
基本块是满足下列条件的最大连续三地址指令序列

  • 控制流只能从基本块的第一个指令进入该块。也就是说,没有跳转到基本块中间或末尾指令的转移指令
  • 除了基本块的最后一个指令,控制流在离开基本块之前不会跳转或者停机

那么,如何将一个三地址指令序列划分成基本块呢?
由上可知,关键是要确定基本块的首指令,从该块首指令开始一直到下一块的首指令之前的所指令就构成了一个基本块

那么如何确定一个块的首指令呢?
因为控制流只能从基本块的第一个指令进入该块,那么我们可以得知,一个跳转指令的目标指令是一个首指令,此外,紧跟在一个跳转指令之后的指令表示下一个分支的开始,因此它也是一个首指令。

基本块划分算法

输入:
三地址指令序列
输出:
输入序列对应的基本块列表,其中每个指令恰好被分配给一个基本块
方法:

  • 首先,确定指令序列中哪些指令是首指令(leaders),即某个基本块的第一个指令
    1. 指令序列的第一个三地址指令是一个首指令
    2. 任意一个条件或无条件转移指令的目标指令是一个首指令
    3. 紧跟在一个条件或无条件转移指令之后的指令是一个首指令
  • 然后,每个首指令对应的基本块包括了从它自己开始,直到下一个首指令(不含)或者指令序列结尾之间的所有指令

接下来举了一个例子,说明如何划分基本块

Image9-1.png

那么先开始找首指令,因为一个指令序列的第一条指令是一个首指令,所以(1)是一个首指令;此外,跳转指令的目标指令是首指令,那么由(8)(12)(13)(22)可以得知,这些跳转指令的目标指令(5)(9)(23)和均为首指令;除此之外,紧跟在跳转指令之后的第一条指令也是首指令,所以(9)(13)(14)(23),所以在该指令序列中,我们一共找到了6条首指令,分别是(1)(5)(9)(13)(14)(23),,根据这六条指令,我们可以划分出六个基本块

Image9-2.png

流图

  • 流图的结点是一些基本块
  • 从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B的最后一条指令之后执行。此时称B是C的前驱(predecessor),C是B的后继(successor)

有两种方式可以确认这样的边

  • 有一个从B的结尾跳转到C的开头的条件或无条件跳转语句
  • 按照原来的三地址语句序列中的顺序,C紧跟在之B后,且B的结尾不存在无条件跳转语句

那么,对于刚才的例子,我们来绘制基本块流图:

因为B2紧跟在B1之后,且B1的最后一条指令不是无条件跳转指令,所以B1与B2之间有一条边,即,B1→B2

B2的最后一条指令是跳转到5号指令,即,B2的第一条指令,也就是说B2是它本身的后继基本块,因此有一条B2到自身的边;

接着往下是B3,因为B3紧跟在B2之后,且B2的最后一条指令不是无条件跳转指令,因此B2到B3之间存在一条边,即,B2→B3

因为B3的最后一条指令是跳转到9号指令,即,B3的第一条指令,因此,B3也有一条到自己的边

在原始的指令中,B4紧跟在B3之后,且B3的最后一天不是无条件跳转指令,因此,B3→B4

B4的最后一条指令跳转到23号指令,也就是B6的第一条指令,因此在B4到B6之间存在一条指令,即,B4→B6

又因为在原始的指令序列中,B5紧跟在B4之后,所以B4到B5之间存在一条边,即,B4→B5

B5的最后一条指令跳转到5号指令,也就是B2的第一条指令,因此,B5→B2

在原始指令序列中,B6紧跟在B5之后,但是B5的最后一条指令是一条无条件跳转指令,因此B5与B6之间不存在边

最后,综上,画出流程图

Image9-3.png

常用的代码优化方法(一)

代码优化的分类
分类方式一:

  • 机器无关优化
    针对中间代码
  • 机器相关优化
    针对目标代码
    分类方式二:
  • 局部代码优化
    单个基本快范围内的优化
  • 全局代码优化
    面向多个基本块的优化

常用的优化方法

  • 删除公共子表达式
  • 删除无用代码
  • 常量合并
  • 代码移动
  • 强度削弱
  • 删除归纳变量

①删除公共子表达式
公共子表达式:

  • 如果表达式x op y先前已被计算过,并且从先前的计算到现在,x op y中变量的值没有改变,那么x op y的这次出现就称为公共子表达式(common subexpression)

接下来举一个例子

Image9-4.png

首先来分析基本块B5,在B5中第一条指令是计算表达式4*i的值,并赋给基本变量t6,接下来,第三条指令又计算了表达式4*i的值,且第二条表达式并没有改变i的值,因此第三条指令中的4*i是一条公共子表达式,由于4*i的上一次出现在同一个基本块中,因此这个子表达式称为局部子表达式,倒数第三条t10=4*i也是同理,这样我们就可以重写B5中的指令序列。这样一来,我们可以将公共子表达式删除,再使用t6t8代替t7t10,即上图黄框所示

那么接下来我们继续分析现在B5,沿着B5的导入弧逆流而上指向B2,我们可以发现表达式4*i的值已经计算过了,而且从4*i的上一次计算到本次计算之间并没有改变变量i的值,因此这里的4*i依然是公共表达式,因此这里的4*i是在B5中进行的,也即,B2的上一个基本块,因此这个公共表达式也成为全局公共子表达式;B3中的4*j也是同理,为全局公共子表达式。这样我们就可以将t6=4*it8=4*j删除,并用t2t4代替,再来重写B5,如下图

Image9-5.png

继续分析B5,可以看出a[t2]a[t4]的值在B3和B5中都已经计算过了,因此也是一个子表达式,故,改写后如下图

Image9-6.png

B5分析完成之后,分析B6,同上,改写可得黄框

Image9-7.png

那个现在来分析现在的B6中的内容,因为a[t2]在B2中计算过了,与前面B5的情况类似,也是一个公共全局子表达式,a[t1]在B1中也计算过了,那么这个a[t1]是否可以作为公共子表达式呢?

实际上,在a[t1]的上一次计算之后,控制从B1离开后进入B6之前,可能会进入B5,而在B5中存在对数组元素的赋值,这时候的t2t4有可能等于t1,因此这两条指令可能实际上改变了a[t1]的值,是不是没理解,哈哈哈哈,确实老师的说法稍微有些复杂,那么这么解释一下吧

假设t2=t1=1,a[1]=4,t5=6,那么也就是说,在B2中v=a[1],故B1中v=4,此时循环进入B5,在B5中a[1]=t5,那么a[1]=6,再进入B6时,a[1]的值就不是一开始的4而是6,故在这种情况下将a[t1]作为公共子表达式是不稳妥的

常用的代码优化方法(二)

②删除无用代码
复制传播

  • 常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句(形如x = y的赋值语句)
  • 复制传播:在复制语句x = y之后尽可能地用y代替x
    复制传播给删除无用代码带来机会,

例如:

Image9-8.png

无用代码(死代码Dead-Code):其计算结果永远不会被使用的语句

例如:

Image9-9.png

这里的B5与B6中的x=t3中的x,并没有在别的块中参与任何相关计算也没有在别的块或者本身中被引用,所以是一条无用语句,可以被删除

③常量合并(Constant Folding)

  • 如果在编译时刻推导出一个表达式的值是常量,就可以使用该常量来替代这个表达式。该技术被称为常量合并

例: l = 2 3.14 r

Image9-10.png

代码移动(Code Motion)

  • 这个转换处理的是那些不管循环执行多少次都得到相同结果的表达式(即循环不变计算,loop-invariant computation) ,在进入循环之前就对它们求值

例如

Image9-11.png

这里需要注意的是,循环不变计算具有相对性:
对于多重嵌套的循环,循环不变计算是相对于某个循环而言的。可能对于更加外层的循环,它就不是循环不变计算

for(i = 1; i<10; i++)
    for( n=1; n<360/(5*i); n++ )
    { S=(5*i)/360*pi*r*r*n; ... }

这里的i对于内层的for循环来说,是循环不变量,但是对于最外层的for循环来说,是随时会发生变化的,因此这里的i并不是循环不变量

⑤强度削弱(Strength Reduction)
用较的操作代替较的操作,例如用代替

Image9-38.png

循环中的削弱变量可以采用归纳变量的方法:
对于一个变量x ,如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c ,那么x就称为归纳变量(Induction Variable)

Image9-12.png

其中,归纳变量可以通过在每次循环迭代中进行一次简单的增量运算(加法减法)来计算

⑥删除归纳变量

Image9-13.png

在沿着循环运行时,如果有一组归纳变量的值的变化保持步调一致,常常可以将这组变量删除为只剩一个

基本块的优化

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

基本块的DAG表示

例如

 a=b+c
 b=a-d
 c=b+c
 d=a-d

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

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

综上可得:

Image9-14.png

其中对于形如x=y+z的三地址指令,如果已经有一个结点表示y+z,就不往DAG中增加新的结点,而是给已经存在的结点附加定值变量x,例如上图的bd

由此可见基本块的DAG图可以自动帮我们检测出基本块中的公共子表达式

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

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

Image9-15.png

上图中的ce没有父节点,且不是活跃变量,也就是说以后不会被引用,所以这些结点对应的指令是无用代码,可以被删除

数组元素赋值指令的表示

假设有一个这样的表达式

x=a[i]
a[j]=y
z=a[i]

其中a[i]出现了两次,且a[i]的第二次出现看上去是一个公共子表达式,但是由于第二条指令中的j可能会等于i,所以a[i]的值可能发生改变,所以a[i]不是公共子表达式

那么问题来了,在构造DAG的时候,如何防止系统将a[i]误判为公共子表达式?

  • 对于形如a[j] = y的三地址指令,创建一个运算符为“[]=”的结点,这个结点有3个子结点,
    分别表示a、j和y
  • 该结点没有定值变量表
  • 该结点的创建将杀死所有已经建立的、其值依赖于a的结点
  • 一个被杀死的结点不能再获得任何定值变量,也就是说,它不可能成为一个公共子表达式

所以可得

Image9-16.png

因此,综上可以得知,根据基本块的DAG可以获得一些非常有用的信息

  • 确定哪些变量的值在该基本块中赋值前被引用过,即,在DAG中创建了叶结点的那些变量
  • 确定哪些语句计算的值可以在基本块外被引用
    在DAG构造过程中为语句s(该语句为变量x定值)创建的节点N,在DAG构造结束时x仍然是N的定值变量

从DAG到基本块的重组

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

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

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

接下来举了一个例子

Image9-17.png

首先我们删除这个DAG中没有附加活跃变量的根节点,这里有两个根节点,一个是定值变量表中的L,是个活跃变量,因此不可以被删除,第二个根节点是G,而G不是活跃变量,因此可以被删除;此外,当一个节点的定制变量表中存在多个变量的时候,我们只需生成一条三地址指令,并将计算的结果付给其中的一个变量,一般而言,我们会将计算的结果赋值给一个活跃变量,删除其余的变量

然后分析语句,以为①仅为赋值语句,所以之后我们在使用B的时候,可以直接用3来代替,

综上,得

Image9-18.png

数据流分析

数据流分析(data-flow analysis)

  • 一组用来获取程序执行路径上的数据流信息的技术

数据流分析应用

  • 到达-定值分析 (Reaching-Definition Analysis)
  • 活跃变量分析 (Live-Variable Analysis)
  • 可用表达式分析 (Available-Expression Analysis)

在每一种数据流分析应用中,都会把每个程序点和一个数据流值关联起来

数据流的分析模式
语句的数据流模式

  • IN[s]: 语句s之前的数据流值
    OUT[s]: 语句s之后的数据流值
  • fs:语句s的传递函数(transfer function)
    一个赋值语句s之前和之后的数据流值的关系
    传递函数的两种风格
    信息沿执行路径前向传播 (前向数据流问题)
    OUT[s] = fs (IN[s])
    信息沿执行路径逆向传播 (逆向数据流问题)
    IN[s] = fs (OUT[s])
  • 基本块中相邻两个语句之间的数据流值的关系
    设基本块B由语句s1, s2, … , sn 顺序组成,则IN[si+1]= OUT[si] i=1, 2, … , n-1

基本块上的数据流模式

  • IN[B]: 紧靠基本块B之前的数据流值
    OUT[B]: 紧随基本块B之后的数据流值
  • 设基本块B由语句s1,s2,…,sn 顺序组成,则
    IN[B] = IN[s1]
    OUT[B] = OUT[sn]
  • fB:基本块B的传递函数

前向数据流问题:
OUT[B] = fB(IN[B])fB =fsn·…·fs2 ·fs1

这里给出了详细的推算过程

    OUT[B]
= OUT[sn]= fsn(IN[sn])
= fsn(OUT[sn-1])
= fsn·fs(n-1)(IN[sn-1])
= fsn·fs(n-1)(OUT[sn-2])
……
= fsn·fs(n-1)·…·fs2(OUT[s1])
= fsn·fs(n-1)·… ·fs2·fs1(IN[s1])
=fsn·fs(n-1)·… ·fs2·fs1 (IN[B

逆向数据流问题:
IN[B] = fB(OUT[B])fB = fs1· fs2 · …·fsn

到达定值分析

  • 定值 (Definition)
    变量x的定值是(可能)将一个值赋给x的语句
  • 到达定值(Reaching Definition) 如果存在一条从紧跟在定值d后面的点到达某一程序点p的路径,而且在此路径上d没有被“杀死” (如果在此路径上有对变量x的其它定值d′,则称变量x被这个定值d′“杀死”了) ,则称定值d到达程序点p
  • 直观地讲,如果某个变量x的一个定值d到达点p,在点p处使用的x的值可能就是由d最后赋予

Image9-19.png

从B1中的d1,d2,d3到B2的入口的路上,没有对ija重新定值,因此d1,d2,d3都可以到达B2的入口处;再来看d4,从d4到B2的入口处一定会经过B4然后对i重新定值,因此d7就杀死了d4,所以d4无法到达B2的入口处,反之d5则可以;同理,从d6、d7到B2的入口处都没有改变ai的值,因此都可以到达B2入口处

据此分析便可得到上图

到达定值分析的主要用途

  • 循环不变计算的检测
    如果循环中含有赋值x=y+z ,而y和z所有可能的定值都循环外面(包括y或z是常数的特殊情况) ,那么y+z就是循环不变计算
  • 常量合并
    如果对变量x的某次使用只有一个定值可以到达,并且该定值把一个常量赋给x ,那么可以简单地把x替换为该常量
  • 判定变量x在p点上是否未经定值被引用

“生成”与“杀死”定值

Image9-20.png

到达定值的传递函数

Image9-21.png

Image9-22.png

接下来举一个例子

Image9-23.png

这里只分析一下B1,其他的分析方式都是一致的,在B1中,生成了三个定值d1d2d3且都没有被杀死,因此genB1={d1,d2,d3};而在B1中的d1是对程序中的i进行定值,那么就杀死了另外两个定值即d4d5,而d2是对j进行定值,那么就杀死了d5d3则是对a进行定值,那么就杀死了d6,所以killB1={d4,d5,d6,d7}

到达定制的数据流方程

  • IN[B]:到达流图中基本块B的入口处的定值的集合
  • OUT[B] :到达流图中基本块B的出口处的定值的集合

Image9-24.png

到达定值方程的计算

Image9-25.png

接下来举了一个例子

Image9-26.png

1表示定值在集合中出现,0表示不出现。
由上可以看出,在第三轮迭代结束之后,所有值都不再发生改变,结束循环,我们可以根据算法结束时,各个基本块的IN值来得到各个基本块入口处的到达定值信息

Image9-27.png

与之前我们分析的结果一致

引用-定值链 (Use-Definition Chains)
引用-定值链(简称ud链)是一个列表,对于变量的每一 次引用,到达该引用的所有定值都在该列表中

建立ud链的方式有两种:

  • 如果块B中变量a的引用之前a的定值,那么只有a的最后一次定值会在该引用的ud链中

Image9-28.png

如果块B中变量a的引用之前没有a的定值,那么a的这次引用的ud链就是IN[B]中a的定值的集合

Image9-29.png

活跃变量分析

活跃变量

  • 对于变量x和程序点p,如果在流图中沿着从p开始的某条路径会引用变量xp点的值,则称变量x在点p活跃(live)的,否则称变量x在点p不活跃(dead)

Image9-30.png

首先来看a,可以看到在程序的各个基本块中都没有引用a的值,因此在各个基本块的出口醋都不是活跃的,因此用×来表示

对于i,因为控制在离开B1后进入B2,因为B2中引用了i,因此i在B1的出口处是活跃的;控制离开B2后,一定经过B4,而B4对i进行了重新赋值,而从B2到B4的路径上都没有引用i,因此在B2的出口处不是活跃的,B3也是同理;从B4出来后,会经过B2,而B2重新引用了i,因此在B4的出口处是活跃的

余下同理,得上图

活跃变量信息的主要用途

  • 删除无用赋值
    无用赋值:如果x在点p的定值在基本块内所有后继点都不被引用,且x在基本块出口之后又是不活跃的,那么x在点p的定值就是无用的
  • 为基本块分配寄存器
    如果所有寄存器都被占用,并且还需要申请一个寄存器,则应该考虑使用已经存放了死亡值的寄存器,因为这个值不需要保存到内存
    如果一个值在基本块结尾处是死的就不必在结尾处保存这个值

Image9-31.png

活跃变量分析是个逆向数据流问题

Image9-32.png

Image9-33.png

Image9-34.png

接下来举了一个例子

Image9-35.png

经过三次迭代之后, 我们得到每个变量出口处活跃变量的集合

定值-引用链 (Definition-Use Chain

  • 定值-引用链:设变量x有一个定值d,该定值所有能够到达的引用u的集合称为x在d处的定值-引用链,简称du链
  • 如果在求解活跃变量数据流方程中的OUT[B]时,将OUT[B]表示成从B的末尾处能够到达的引用的集合,那么,可以直接利用这些信息计算基本块B中每个变量x在其定值处的du链

具体分为两种情况:

  • 如果B中x的定值d之后有x的第一个定值d′,则d和d′之间x的所有引用构成d的du链

Image9-36.png

  • 如果B中x的定值d之后没有x的新的定值,则B中d之后x的所有引用以及OUT[B]中x的所有引用构成d的du链

Image9-37.png

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

Leave a Comment