精华内容
下载资源
问答
  • 编制程序,完成局部优化过程中的基本块划分。给定一段代码,判定程序的入口语句,划分基本块,删除无用产生式和冗余节点。
  • 编译原理过程简述及中间代码优化

    千次阅读 2017-09-28 17:21:23
    一、编译过程图示如下:词法分析作用:找出单词 。...二、中间代码优化所谓代码优化是指对程序代码进行等价(指不改变程序的运行结果)变换。程序代码可以是中间代码(如四元式代码),也可以是目标代码。

    一、编译过程图示如下:

    这里写图片描述

    词法分析作用:找出单词 。如int a=b+c; 结果为: int,a,=,b,+,c和;
    语法分析作用:找出表达式,程序段,语句等。如int a=b=c;的语法分析结果为int a=b+c这条语句。
    语义分析作用:查看类型是否匹配等。

    二、中间代码优化

    所谓代码优化是指对程序代码进行等价(指不改变程序的运行结果)变换。程序代码可以是中间代码(如四元式代码),也可以是目标代码。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。优化的含义是最终生成的目标代码短(运行时间更短、占用空间更小),时空效率优化。原则上,优化可以在编译的各个阶段进行,但最主要的一类是对中间代码进行优化,这类优化不依赖于具体的计算机。

    优化目的:在不改变程序运行效果的前提下,对被编译的程序进行等价变换,使之能生成更加高效的目标代码。

    优化原则

    等价原则。经过优化后不应该改变程序运行的结果。
    等效原则。使优化后所产生的目标代码运行时间较短,占用的储存空间较小。
    合算原则。应尽可能以较低的代价取得较好的优化效果。

    附:

    循环优化代码外提
    将在循环入口设置基本块,把循环中的循环不变运算提入基本块,且提入部分必须为循环出口必经运算。如图:

    这里写图片描述

    PS:
    1、 代码优化就是对程序进行等价变换,以提高目标程序的效率,通常只对中间代码进行优化。通常包括控制流分析、数据流分析和变换三部分。
    2、 以程序的基本块为基础,基本块内的优化叫局部优化,跨基本块的优化为全局优化,循环优化是针对循环进行的优化,是全局优化的一部分。
    3、 公共子表达式的删除、复制传播、无用代码删除、代码外提、强度削弱和归纳变量删除等都是一些常用的针对局部或者全局的代码优化方法。

    展开全文
  • 编译原理试验报告 课题:中间代码优化;表达式语法分析等 包含所有的报告以及C++与程序
  • 包括公共子表达式优化、常表达式优化和循环不变式优化
  • 优化其实可以在编译的各个阶段进行,但最主要的一类优化是在目标代码生成以前,对语法分析、语义分析后产生的中间代码进行优化。这是因为中间代码的形式不依赖于具体的计算机,它可以是三地址码的形式,所以相应的...

    代码优化概述.

    通过对程序进行等价变换,使得从变换后的程序出发,能够生成更加有效的目标代码,这种变换我们叫做优化。

    优化其实可以在编译的各个阶段进行,但最主要的一类优化是在目标代码生成以前,对语法分析、语义分析后产生的中间代码进行优化。这是因为中间代码的形式不依赖于具体的计算机,它可以是三地址码的形式,所以相应的对于中间代码的优化也不依赖于具体的计算机。另一类优化是在生成目标代码时进行的,它很大程序上依赖于具体的计算机。
    中间代码的优化中,有很多技术和手段可以应用。大局上来说,中间代码优化器的位置如下图所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    其中编译前端就是词法分析、语法分析、语义分析以及中间代码生成这些阶段。有的优化工作很容易实现,比如基本块内的局部优化。在一个程序运行时,相当一部分的时间是花在循环代码上的,因此基于循环的优化是极其重要的。而有的优化技术涉及对整个程序的控制流、数据流分析,其实现代价是相当高的。
    我们进行中间代码优化的目的是为了产生更加高效的代码,所以由代码优化器提供的,对代码的各种变化必须要遵循一定的原则,一切为了更高效的代码。

    • 等价原则:经过优化后不应该改变程序运行的结果。这是最不应该也不能破坏的原则,试问程序结果都不正确了,优化的意义何在?
    • 有效原则:优化后的代码运行快、存储空间需求小。这也正是我们优化代码的目的,从时空两个维度尽可能让代码效率高。
    • 合算原则:尽可能以较低的代价,取得较高的优化效果。

    优化可以从各个环节着手。首先,在源代码层面,程序员通过选择适当的高效算法,安排适当的实现语句来提高程序的效率。例如,归并排序肯定要比直接插入排序在绝大多数情况下的效率更高,执行时间更短吧;其次,在设计语义动作时,我们不仅可以考虑产生更加高效的中间代码,还可以在语义分析阶段为优化做一些预备工作。例如,为循环代码的begin和end对应的中间代码“打上标记”,这样有助于后续的控制流、数据流分析;代码的分叉处和交汇处(通常是条件判断语句控制)也“打上标记”,这样有助于识别程序流图中的直接前驱和直接后继。对于编译产生的中间代码,我们安排专门的优化阶段,进行各种等价变换,以提高代码的工作效率。而在目标代码这一层面,我们应该考虑如何有效地利用寄存器,如何选择指令以及如何进行窥孔优化等。

    窥孔优化,顾名思义,是一种很局部的优化方式,编译器仅仅在一个基本块或者多个基本块中,针对已经生成的代码,结合CPU自己指令的特点,通过一些认为可能带来性能提升的转换规则,或者通过整体的分析,通过指令转换,提升代码性能。别看这些代码转换很局部,很小,但可能会带来很大的性能提升。这个窥孔,你可以认为是一个滑动窗口,编译器在实施窥孔优化时,就仅仅分析这个窗口内的指令。每次转换之后,可能还会暴露相邻窗口之间的某些优化机会,所以可以多次调用窥孔优化,尽可能提升性能。

    中间代码优化全局大观.

    上面我们说完了代码优化的地位、原因以及目标,接下来我们通过一段中间代码实例以及它从最初到优化完成的过程,来展示、介绍中间代码优化具体做了哪些事。首先我们给出这段中间代码的最初状态:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    图中是中间代码的基本块程序流图展示,至于基本块如何划分,我们后面会给出算法,这里并不是问题的重点。我们是要看,究竟代码优化器,对这样的中间代码,做了怎样的等价变换。

    1.删除公共子表达式(Common Subexpressions Elimination).

    对于一个表达式E,如果它的值在前面已经计算过,并且在这之后E中变量的值并没有发生过改变(至于常量值更是无法改变了,不要ETC),那我们就称这样的表达式E为公共子表达式。对于这样的公共子表达式,我们可以避免对它的重复计算,而全部使用E中已经计算出的结果,称为删除公共子表达式,有时也称为删除多余运算(因为已经计算过了).

    ETC(Electronic Toll Collection),中文翻译是电子不停车收费系统,是高速公路或桥梁自动收费。通过安装在车辆挡风玻璃上的车载电子标签与在收费站 ETC 车道上的微波天线之间进行的专用短程通讯,利用计算机联网技术与银行进行后台结算处理,从而达到车辆通过高速公路或桥梁收费站无需停车而能交纳高速公路或桥梁费用的目的。

    看我们上面给出的中间代码实例,当中哪些是多余运算,或者说公共子表达式呢?着眼于B5_5基本块:

    T6:=4*i
    x:=a[T6]
    T7:=4*i
    T8:=4*j 
    T9:=a[T8]
    a[T7]:=T9
    T10:=4*j
    a[T10]:=x
    goto B2
    

    我们可以看到T6和T7这一组,以及T8和T10这一组一共两组临时变量都属于上面提到的公共子表达式。4*i的结果已经被计算了放在T6变量中,那么T7还有计算的必要吗,显然没有。所以针对这部分代码,我们可以修改如下:

    T6:=4*i
    x:=a[T6]
    T7:=T6
    T8:=4*j 
    T9:=a[T8]
    a[T7]:=T9
    T10:=T8
    a[T10]:=x
    goto B2
    

    修改之后我们发现,B5_5中只需要分别计算一次4*i4*j. 我们还可以在更大的范围内来考虑删除公共子表达式的问题。我们注意到B2_2中计算了4*i的值并且保存在T2中,而B3_3中计算了4*j的值,保存在T4中。并且最关键的是,在这两个地方计算出表达式的值之后,i和j的值一直都没有发生变化,是很标准的公共子表达式(多余运算)。所以B5_5中的中间代码可以变换为如下的形式:

    T6:=T2
    x:=a[T6]
    T7:=T6
    T8:=T4
    T9:=a[T8]
    a[T7]:=T9
    T10:=T8
    a[T10]:=x
    goto B2
    

    对于B6_6我们也进行一次同样的分析之后,我们可以将中间代码修改为下面这样:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    我们可以对比现在的中间代码和最初的中间代码,T1=4*n;T2=4*i;T4=4*j这三个公共子表达式(4*n、4*i、4*j是公共表达式)在B5_5和B6_6中被优化了,删除了多余运算。

    2.复写传播.

    上面的中间代码还可以进一步改进,我们还是着眼于B5_5来进行分析。T6=T2;x=a[T6]这两条语句中,T6的值并没有发生改变,一直是T2的值,因此可以直接将a[T2]的值赋给x,这种变换称为复写传播。

    复写传播(拷贝传播):某些变量的值并未被改变过便赋给其他变量,则可直接引用原值本身.

    通过复写传播的优化方法之后,我们可以将B5_5变换为如下中间代码:

    T6:=T2
    x:=a[T2]
    T7:=T2
    T8:=T4
    T9:=a[T4]
    a[T2]:=T9
    T10:=T4
    a[T4]:=x
    goto B2
    

    进一步分析发现,a[T2]的值曾经在B2_2中被T3=a[T2]计算过,所以x=a[T2]可以变换为x=T3,进而再一次应用复写传播,将a[T4]=x变换为a[T4]=T3;同样的,因为a[T4]在B3_3中被T5=a[T4]计算过,所以T9=a[T4]可以变换为T9=T5,从而也应用复写传播,将a[T2]=T9变换为a[T2]=T5,至此,B5_5中的代码变换成了下面的样子:

    T6:=T2
    x:=T3
    T7:=T2
    T8:=T4
    T9:=T5
    a[T2]:=T5
    T10:=T4
    a[T4]:=T3
    goto B2
    

    对B6_6也进行同样的分析(其实不难发现,B5_5和B6_6的代码几乎是对称的,这段代码是快速排序的代码),我们得到了下面的中间代码:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    复写传播的目的是使得对于某些变量的赋值,变得无用。我们很快就可以看到这一点。

    3.删除无用代码.

    对于进行了复写传播之后的B5_5块进行分析,可以发现变量x以及T6,T8,T9,T10这些临时变量在赋值符号的右边都没有出现过,这就意味着它们的值其实在整个B5_5块内自从被赋值之后,就没有使用过,因此这些变量的赋值对于程序的运行结果没有任何作用,有没有都是一样。但对于代码的执行效率来说就不是这样了,可以看出B5_5代码段其实是在一个循环块内的,很小的性能累赘乘以循环次数就是很大的效率阻碍了。我们可以删除对于这些变量的赋值代码,从而将B5_5转换为下面的代码:

    a[T2]:=T5
    a[T4]:=T3
    goto B2
    

    一下子代码的逻辑清晰明了了许多,之前的代码中那么多赋值颠来倒去,很难看出到底在做什么。删除无用代码之后,不仅效率提高了,代码也清新了许多(虽然我们很少会直接看到中间代码,但代码的清新意味着计算机执行时的快速与高效,这一点比较删除前后的代码,不难看出吧).
    同样地,我们对B6_6段也进行无用代码的删除,当中的变量x以及临时变量T11,T12,T13,T14,T15的赋值语句都属于无用代码,删除之后的代码如下:

    a[T2]:=v
    a[T1]:=T3
    

    至此我们可以给出,删除公共子表达式、复写传播和删除无用代码之后的中间代码形式:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    不难看出,前面所介绍的三种优化都是针对某一个基本块内部所作的优化,例如B5_5块内的优化就只在块内自己进行,那么下面我们要介绍的优化技术,都是涉及循环的优化。

    中间代码优化根据优化所涉及的程序范围分成:

    • 局部优化:在程序基本块内进行的优化;
    • 循环优化:在程序循环体内进行的优化;
    • 全局优化:在整个程序范围内进行的优化。

    4.代码外提.

    对于循环中的某些代码,如果在整个循环的过程中它产生的结果是不变的,就可以将这部分代码提到循环外去,以免每一次循环都要对这条代码进行运算。例如对于while(i<limit-1)...这样的代码,如果limit是一个在循环中没有改变的值,我们完全可以将limit-1提到循环外:
    t=limit-1
    while(i<t)...
    这种变换称为代码外提,但在我们这个实例中,循环过程中并没结果不变的代码,所以这一优化步骤跳过。

    5.强度削弱与删除归纳变量.

    这一优化步骤中我们着眼于基本块B3_3。循环每执行一次,j的值-1,而T4始终与j保持着T4=4*j的线性关系,因而每循环一次T4的值-4. 因此我们可以将循环中对于T4的乘法运算,变换为对T4的减法运算。因为计算机中对于加减法的运算比乘除法要快,所以这一技术称为强度削弱。同理对于B2_2中的T2变量,我们也可以进行这样的强度削弱。

    基本归纳变量——若循环中对 B 只有唯一的递归赋值 B:=B+C 且 C 为循环不变量,则称 B 为循环的基本归纳变量。
    归纳变量——若B为基本归纳变量,而A在循环中的定值可以化归为B的线性函数: A:=C1*B+C2(C1,C2为循环不变量),则称A 为归纳变量,并称 A与 B同族。

    根据这里给出的定义,显然i和j就是定义中的基本归纳变量,而T2和T4就是归纳变量。在我们对T2=4*i以及T4=4*j进行强度削弱之后,i和j除了被用于条件判断语句if i>=j goto B6控制跳转之外,不在其他地方被引用,因此我们完全可以删除这里的基本归纳变量i和j,将条件控制语句用T2和T4的值来完成:if T2>=T4 goto B6。所以完成了强度削弱和删除归纳变量之后的中间代码如下所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
    在这里插入图片描述
    到这里我们完成了一次中间代码优化,并且了解了代码优化的过程中到底做了哪些事情,以及如何完成这些事情的细节。

    展开全文
  • 也正是由于这部分代码序列可能会被反复执行,所以在进行中间代码优化时应着重考虑循环优化,这对提高目标代码的效率起到很大的作用。为了进行循环优化,首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构...

    循环优化概述.

    什么叫做循环?循环就是程序中那些可能反复执行的代码序列。也正是由于这部分代码序列可能会被反复执行,所以在进行中间代码优化时应着重考虑循环优化,这对提高目标代码的效率起到很大的作用。为了进行循环优化,首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构程序设计思想,程序员在编程时应使用高级语言所提供的结构性的循环语句来编写循环。而由高级语言的循环语句所形成的循环,是不难找出的。对于循环中的代码,可以实行代码外提、强度削弱和删除归纳变量等优化操作。一个中间代码序列的程序流图如下所示:
    在这里插入图片描述
    我们不难看出,其中B2_2和B3_3分别构成一个循环,{B2_2,B3_3,B4_4,B5_5}构成一个范围更大的循环。而我们要进行循环优化,首先需要知道循环在哪里,接下来,我们就一步步给出,整个循环优化的过程。

    计算必经节点集.

    【定义】:若从首结点出发到达结点Nj_j的每一条通路都必须经过结点Ni_i,那么我们称Ni_i是Nj_j的必经节点,记为Ni_i dom Nj_j,其中dom是dominate的简写。那么Nj_j所有必经节点的集合,就是Nj_j的必经节点集,记为D(Nj_j).

    计算程序流图中必经节点集的算法也是一个不动点算法,通过每一次的迭代来计算一个结点的必经节点集。当程序流图中所有结点的迭代计算结果都不发生改变时,说明已经获得了最终的结果,算法宣布结束。下面我们给出计算必经节点集的算法:
    在这里插入图片描述
    这里我们也给出一个例题,作为计算必经节点集算法的收尾:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    需要注意的是,该算法并不像图中那样,一次迭代计算就可以确定结果,而是需要再一次迭代确认了所有的结点都没有发生变化,才能确定最终结果的。

    循环查找算法.

    1.查找回边.

    【定义】如果一个程序流图中存在有向边<Ni_i→Nj_j>,并且Nj_j∈D(Ni_i),那么我们称有向边<Ni_i→Nj_j>是一条回边。

    依旧是我们前一部分给出的实例,考察其中的回边:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述

    2.查找循环.

    求出了程序流图中的回边之后,我们就可以基于回边来查找循环。具体的方法是,若<Ni_i→Nj_j>是一条回边,那么该回边构成的循环中的结点包括:Ni_i和Nj_j以及所有不经过Ni_i能够到达Nj_j的结点。我们以上图中求出的三条回边为例,6→6确定的循环中只包括结点6;7→4确定的循环中包括结点有{4,7,5,6};4→2确定的循环中包括的结点有{2,4,3,5,6,7}。

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述

    代码外提.

    至此我们已经完成了查找循环包含结点的工作,接下来就是要对循环体中的中间代码进行优化了。循环中的某些代码虽然随着循环反复地执行,但其中某些运算的结果并没有发生改变,例如循环中有形如A:=B op C的代码,并且如果B和C都是常数,或者到达它们的定值点都在循环外,那么不管循环多少次,每次计算出来得到的B op C的结果都是不变的,对于这样的不变运算,我们完全可以将其外提到循环以外,避免其随着循环多次计算。如此一来,程序的结果没有发生变化,但程序的运行速率却得到了一定程度的提高,这就是代码外提。

    【定义】所谓变量A在程序中某一点d的定值到达了另一点u,或者说变量A的定值点d达到另一点u,指的是程序流图中从d有一条通路到达u,并且通路上没有A的其它定值点。

    实行代码外提时,我们在循环的入口结点之前建立一个新结点(基本块),称为循环的前置结点,该前置结点以循环的入口结点为其唯一后继。并且原来流图中从循环外引到循环入口结点的有向边,都改为引到该前置结点。如下图所示:
    在这里插入图片描述
    我们考虑的循环结构,其入口结点都是唯一的,从而其前置结点也是唯一的,我们后续进行代码外提时所有外提的代码都将提到前置结点中。下面一段Pascal源程序,是我们叙述代码外提的第一个例子:

    for I:=1 to 10 do
    	A[I,2*J]:=A[I,2*J]+1
    

    它对应的中间代码序列如下:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述

    1. 考察序号为3和7的语句,因为循环中并没有J的定值点,所以其中J所有引用的定值点都在循环外,从而3和7都是循环不变运算;
    2. 考察序号为6和10的语句,分配给数组A的首地址addr(A)的值并不会随着循环的一次次执行而改变,所以6和10也都是循环不变运算。

    所以我们可以做出这样的判断:3与7、6与10都可以外提到该循环的前置节点中,进行了代码外提之后的中间代码序列如下所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    那么问题又来了,是不是在任何情况下,都可以将循环不变运算进行外提呢?我们看第二个例子:
    在这里插入图片描述
    从程序流图中我们不难看出,{B2_2,B3_3,B4_4}构成了一个循环,并且B2_2是入口结点,B4_4是出口结点。

    【定义】出口结点是指循环中具有如下性质的结点:从该结点有一条有向边引到循环外的某结点。

    图中我们也不难看出,基本块B3_3中的I:=2语句是循环不变语句,那么我们是否可以直接将这一语句外提到循环以外的前置结点B2_2'呢?我们暂且认为可以这样做,外提之后的程序流图如下所示:
    在这里插入图片描述
    我们看外提了I:=2这一语句的程序流图,执行到基本块B5_5时,变量I的值总会是2,从而J的值也会是2.但我们需要注意的是,在原始的、没有进行I:=2外提的程序流图中,B3_3并不是B4_4的必经结点。我们在原始流图中考虑X=30、Y=25的情况,这样的情况下B3_3是不会被执行的,所以执行到B5_5时变量I的值应该是1,从而J的值也应该是1而非2.那么很显然,我们进行了I:=2外提的程序已经改变了程序运行的结果,这必然是不允许的。问题到底出在什么地方呢?其实前面已经点出,B3_3并不是循环出口结点B4_4的必经节点,再直白一点说,B3_3中的代码并不一定会对B4_4中的代码起到作用,但如果我们将其外提到循环的前置结点,那么该外提的语句必然是会对B4_4产生影响的,这就导致了程序运行结果被改变的风险,我们并不允许这样的风险存在。
    所以从这个例子中我们可以看到,当一个循环不变运算要外提到循环的前置结点时,要求该循环不变运算的语句所在的结点是循环的所有出口结点的必经结点
    另外,我们注意到,如果循环中变量I的所有引用点都是B3_3I的定值点所能到达的,I在循环中不再有其它的定值点,并且出循环之后也不会再引用变量I的值(即在循环外的循环后继结点入口,变量I不是活跃的),那么即使B3_3不是B4_4的必经结点,还是可以将I:=2外提到循环的前置结点,因为这样做并不会改变程序的结果。
    再一个例子,如果我们将上述程序流图中的基本块B2_2改为:

    I:=3
    if X<Y goto B3
    

    考虑B2_2I:=3外提的问题。
    通过计算必经结点集可以发现,B2_2确实是循环出口结点B4_4的必经结点,那么我们是否可以将I:=3进行代码外提呢?同样的论述过程,我们姑且认为可以,那么如果程序的执行过程是2-3-4-2-4-5,则执行B5_5时的变量I值为2,从而J的值也是2;而如果不进行外提操作,那么同样的执行过程下,I和J的值都应该是3,而非2.这一错误的原因在于,循环中除了B2_2以外,B3_3也对同一个变量进行了定值。
    所以从这个例子中我们可以看到,当我们将循环不变运算A:=B op C外提时,要求循环中的其它地方不再有A的定值点
    第三个例子,也是最后一个例子,我们看下面一个程序流图:
    在这里插入图片描述
    考察基本块B4_4中循环不变运算I:=2这一语句的外提操作。首先,B4_4结点就是整个循环的出口结点,并且B4_4结点也是其本身的必经结点;其次整个循环{B2_2,B3_3,B4_4}中也没有第二个对于变量I定值的语句。那么我们是否可以将这一语句外提呢?同样的方法,我们还是暂且认为这一语句可以外提,再比较对于同一个执行过程,外提前后的执行结果。我们考虑X=0、Y=2的情况,循环的执行流程是2-3-4-2-4-5,代码外提前,程序的执行结果为J=2;而代码外提后,程序的执行结果为J=3.
    通过这个例子,我们看到,当将循环不变语句A:=B op C进行代码外提时,要求循环中所有对于A的引用点都是并且仅仅是这一定值语句所能到达的。上述的例子中,能够到达A:=I+1这一对于I的引用的定值语句,不仅有B4_4中的I:=2,还有B1_1中的I:=1.
    最后我们给出查找循环L中不变运算的算法:
    在这里插入图片描述
    以及代码外提算法:
    在这里插入图片描述

    强度削弱.

    我们要介绍的第二种循环优化技术叫做强度削弱。强度削弱是将程序中执行时间较长的运算替换为执行时间较短的运算。例如,最常见的就是将循环中的乘法运算用递归的加法运算来代替。我们考察前面经过了代码外提的示例流图:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    不难看出{B2_2,B5_5}是一个循环,并且B2_2是循环的入口结点。我们注意序号为13的语句,这里的变量I是一个递归赋值的变量,每循环一次,它增加一个常量1。另外,序号为4和8的语句在计算T2_2和T6_6时,都会使用I的值,并且T2_2和T6_6都是I的线性函数,每循环一次,它们都增加一个常量10.因此,如果把4和8外提到循环的前置结点中,并且在13号语句之后添加上为T2_2和T6_6增加常量10的语句,程序的运行结果依然不变。

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    经过上述变换,循环中原来的乘法运算4和8被替换为了在前置结点中进行一次初始化的乘法运算(计算初值)以及在循环中递归赋值的加法运算(4’)和(8’).不仅加法运算一般来说比乘法运算快,而且这种在循环前计算初值,再于循环末尾进行常量递增的运算,可以利用变址器提高运算速度,从而使运算的强度得到削弱。所以我们称这种优化技术为强度削弱。
    强度削弱不仅对于乘法可以实行,对于加法也可以实行。例如上图中序号为5和9的语句,T3_3与T7_7的计算中引用到了T2_2和T6_6,并且T2_2和T6_6也是递归赋值的变量,每循环一次,它们的值就增加一个常量10.而T3_3与T7_7的另一个运算对象都是循环不变量,所以每循环一次,T3_3与T7_7的值就增加一个常量10.很自然地,我们会想到对它们进行强度削弱,即外提一个初始化语句,在循环的末尾添加常量递增语句,得到的优化结果如下所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    从上面的例子中我们可以看到:

    1. 如果循环中有A的递归赋值A:=A±b1_1,并且循环中另一个变量B的赋值运算可以写为B:=k*A±b2_2的形式,那么对于B的赋值运算,我们可以进行强度削弱;
    2. 进行强度削弱之后,循环中可能会出现一些新的无用赋值,例如上图中的(4’)和(8’),因为循环中不再使用T2_2和T6_6,那么如果循环出口之后它们也不是活跃变量,是完全可以删除的;
    3. 循环中下标变量的地址计算是相当耗费时间的,这里介绍的方法对削弱下标变量地址计算的强度是非常有效的。前面的例子中,数组是二维的,如果我们考察一个更高维度的数组,将会进一步看到强度削弱的作用。对于下标变量地址计算来说,强度削弱实际上就是实现下标变量地址的递归计算。

    删除归纳变量.

    我们要介绍的最后一种循环赋值技术叫做删除归纳变量。讲述具体的流程之前,首先给出基本归纳变量以及归纳变量的定义:

    【定义】基本归纳变量:循环中对于变量A的赋值只有唯一的、形如A:=A±b1_1的赋值,那么称A为循环中的基本归纳变量;
    【定义】归纳变量:如果A是一个基本归纳变量,循环中对于B的赋值总是可以化归为A的同一个线性函数,即B:=k*A±b2_2,那么我们称B是一个归纳变量。

    考察进行了代码外提之后的示例程序流图:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    不难发现变量I是循环{B2_2,B3_3}的基本归纳变量,T2_2和T6_6是循环中与I同族的归纳变量,再继续发掘,T3_3和T7_7也是与I同族的归纳变量。
    一个基本归纳变量除了用于自身的递归赋值以外,往往只在循环中用于计算其他的归纳变量和控制循环的进行。经过了强度削弱之后的示例程序流图如下所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    关注基本块B3_3可以发现变量I除了用于自身的递归赋值以外,只用于控制循环的进行。这时,我们可以使用与I同族的某一个归纳变量来代替I控制循环的进行,从而删除变量I.例如,我们选取T3_3(T7_7与T3_3都在循环中被引用,所以是一样的,而T2_2和T6_6在循环中没有被引用)来代替I, 由于T3_3可以写为10*I+T1,并且循环的控制条件为I>10,所以用T3_3代替了I之后,控制条件变为了T3>100+T1.为了不在每一次进行判断时都计算100+T1_1的值,我们引入新的临时变量R:=100+T1_1,所以序号为2的if语句改写为:

    R:=100+T1
    if T3>R goto (15)
    

    然后我们就可以删去变量I了,这一优化技术称为删除归纳变量,也叫变换循环控制条件。如果我们假定T2_2和T6_6在循环出口之后也不是活跃的,那么我们完全可以删去这两个临时变量(因为它们在循环中也没有被使用)。但如果我们在选择代替I的变量时选择了T2_2或T6_6,那么(4’)或(8’)就不能删除了,最后完成删除归纳变量的中间代码如下:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    删除归纳变量是在强度削弱之后进行的。我们在下面统一给出强度削弱和删除归纳变量的算法:
    在这里插入图片描述

    展开全文
  • 一、代码优化的阶段 ...二、中间代码优化的分类 从优化的种类来看,中间代码的优化可有如下分类: 局部优化 循环上的优化(所有优化方法效果最好的) 1. 循环不变体外提 循环中不因循环而改变的部分可以提到循环的

    一、代码优化的阶段

    欲提高源程序的运行速度,需要经过几个阶段的优化:

    1. 用户对源程序进行优化(和编译器无关,与coder设计的算法有关)
    2. 编译器前端对中间代码进行优化
    3. 编译器后端对目标代码进行优化

    两个编译器必须等价,编译的结果必须是正确的,即使有99.99%的可能性是不正确的,但是效率很好也不行,正确性是根本。

    二、中间代码优化的分类

    从优化的种类来看,中间代码的优化可有如下分类:

    1. 局部优化

    循环上的优化(所有优化方法效果最好的)
    1. 循环不变体外提
    循环中不因循环而改变的部分可以提到循环的外部
    2. 削减运算强度
    在一些循环上的计算转换成另一种计算方式实现,比如b=a*2 -> b=a+a
    基本块的优化(按照某些规则划分成基本块)
    1. 常表达式节省
    2. 公共子表达式节省

    1. 全局优化

    全局数据流分析,从而使优化的效果更好
    考虑基本块里如何优化,已经得到的值和变量的表,全局得到更多的信息进行分析。
    在局部优化的基础上进行全局优化才有更大的提高,否则直接进行全局优化的提升效果不明显。

    三、常见的编译优化的种类

    1. 数学上的优化

    情况一:(主要是在生成中间代码的时候会产生)

    (-,a,0,t1) (*,a,1,t2)
    //这种a+0,和a*1的没有太大意义的运算,这样的四元式可以删除
    //正常写普通的代码一般不会出现这种情况
    //但是在一些不明显的地方,比如计算数组中的元素a[i]时,用【i-(数组下界)】xsize
    //数组下界为0的时候和size=1的时候都会产生上面的四元式
    //可直接换但是还要将运算结果进行处理
    

    情况二:

    2*a->a+a
    a^2->a*a
    

    原则上说,可以不计算的直接删去其四元式,直接写出结果;高运算强度的可以转化成低运算强度的。

    2. 表达式短路问题

    在这里插入图片描述
    如果在计算一个表达式的时候可以不用将整个表达式的值都计算出来就可以确定表达式的结果,在这种情况下,后面的计算可以省略。
    或运算:如果计算出第一个表达式的结果是1可以直接返回 true
    与运算:如果计算出第一个表达式的结果是0可以直接返回false

    3. 常表达式的节省

    • 计算过程中有一个表达式是33.14,这个实际上是两个常数,他的结果我是可以计算出来的,这样我们在编译的过程中把33.14算出来,在目标程序的进行中就不用进行计算了。
    • 通过编译程序将可以计算出的结果直接计算出来然后将相应位置替换成计算出的结果。
    • 把有关工作交给编译程序进行可以提高生成的目标程序的运行效率,编译程序可以稍微慢些的工作,因为最后看的还是生成的目标程序的运行效率。

    4. 公共子表达式节省(消除重复操作)

    在这里插入图片描述

    • 所谓公共子表达式即两个子表达式的计算结果是一样的,不需要重复的进行计算,第一次计算出来之后,后面的计算可以利用前面的计算结果。例如前面有表达式ab,后面又有表达式也是ab,而且在第二个表达式和第一个表达式中间,a和b的值没有被改变过,那第二个a*b表达式实际上是可以不用计算的,只需要把前面的计算结果拿过来就可以达到计算的目的。
    • 这种情况在下标变量的计算中体现的非常明显,比方说a[i][j]和a[i][k],下标变量的计算先计算a[i]的地址然后计算j,然后计算a[i][j]的地址,a[i][k]也是一样先计算a[i]的地址在根据k计算a[i][k]的地址,所以前面关于a[i]的计算结果是完全一样的。这样就可以不用重复计算,利用前面的结果达到计算目的。

    5. 循环不变量式外提

    在这里插入图片描述
    循环不变式外提,在循环中,如果有一个表达式的值在循环中不会改变,就需要把它提到循环体的外面去。比方说有一个双重循环1-100和1-100,那么整个两重循环计算下来就是1万次,比方说里面有一个ab的表达式,在循环过程中ab的值如果不改变,那他就重复计算了9999次,假如把ab提到循环体的外面只需要计算1次,在循环里只需要用到它的计算结果。所以这样的表达式在循环体里面是不变的,我们要把他提到循环体的外面,从而提高我们的执行效率,这种效率的提高是最高的。特别是计算量很大的情况下,比方说有多重循环,这种循环不不变式外提可以大大提高程序的执行效率,这种提高的效率大概可以提高十几倍甚至是几十倍,串式程序的并行处理很大的一个研究重点,都是放在循环的并行计算上,比方说1~1000次的循环把它分成段,在不同的处理机上进行执行,从而提高程序的执行效率

    6. 削减程序的运算强度

    在这里插入图片描述
    削减程序的运算强度。这个也通常是针对循环的,一种特例的情形,比方说在程序设计语言中通常来说,一般的程序循环有三种方式分别是:
    1)for循环(有的语言中也称作是步长式的循环),循环形式是for i=e1 to e2 ;step e3{} 也就是说它的执行是i开始获取一个循环初值e1,然后每次循环i都加上e3的值,一直当i大于e2就结束循环,比方说for1=1to 100;step 1,就是1-100步长是1执行100次。
    2)while循环,“当型循环”()
    3)直到型循环 do until ~~的形式

    7. 寄存器优化

    在这里插入图片描述

    生成目标代码的时候一定是和目标机相关的,对于目标机来说提供多少个寄存器,比方说提供了8个,当目标程序真正执行的时候,这8个寄存器是如何被分配的,这是一个问题。简单的说假如说寄存器有空闲的时候,分配方案比较简单,空闲的就分配,这个没问题,什么时候会有问题呢?
    有这样几种情况:
    要用寄存器的时候,是否有空闲的寄存器,如果没有空闲的怎么办?需要剥夺一个寄存器,如何来剥夺?类似的还有内存和外存进行淘汰页的算法是类似的,只不过这个是在更高一级的层面上,寄存器和内存间的变换。这是寄存器分配优化

    8. 消除无用语句,消除冗余代码

    在这里插入图片描述

    消除无用语句,消除冗余代码,假如一个条件语句,if e s1 else s2 ,如果表达式E的值是一个true,那么s2是不可能用到了,所以这个命令就可以删掉了,这个命令也直接可以用s1来替换掉,当然这是一种特殊的情形,产生冗余代码实际上也是这么产生的

    9. 中间变量优化

    在这里插入图片描述

    中间变量的优化,生成中间代码的时候会产生大量的临时变量,大量的临时变量的特点一般都是产生之后使用一次就会不再用了,如果是说有一些临时变量和另外一些临时变量之间没有交集的话,不需要为每一个临时变量都分配独立的存储单元。最简单的方式,把产生临时变量一直到使用临时变量这个区域比方说把它定义为临时变量的活动区,假如两个临时变量的活动区不相交,实际上他们可以共用同一个存储单元,那么这种优化实际上就是临时变量的存储空间上的优化

    10. 目标代码优化

    在这里插入图片描述

    是目标代码的优化,可以通过确定目标代码来减少目标程序的指令个数来提高目标程序的执行效率,比方说有一个变量的值在寄存器里,运算出来的中间结果在寄存器里,假如直接让他参与运算之后,就不用往内存中存了,什么时候需要存,什么时候不存,什么时候需要把它放在寄存器里,这就是需要对目标程序进行的一种优化,根据使用情况来进行。

    11. 全局优化

    在这里插入图片描述
    总而言之这种优化还有很多,比方说全局的数据流分析和全局的优化,因为前面考虑实现的时候由于优化的技术可能比较复杂,都是在局部区做的,比方说一个基本块上做的,要想做到全局的需要对全局的程序做全局的数据流分析,这样的话可能就更复杂了,如果没有特殊需求,一般来说是不做这样的优化的:
    第一个原因就是编译代价太大,因为要做各种各样的分析,导致编译代价很大。
    第二就是提高的效率也并不是十分的明显。

    如果说没有特殊的需求,前面做的局部优化已经能达到想要的效果,全局优化就不用做了,特殊需求的时候才想办法处理。

    ⚠️优化中要注意的一个问题就是优化是在保证正确的情况下进行的,任何一个程序的优化也不能做到最优,而是在一定程度上来提高程序的执行效率。所以优化的过程一定是在保证程序正确的前提下来进行的。

    四、基本块

    (一)基本块的定义

    在这里插入图片描述

    • 基本快:是一个命令的序列,每一条命令都是按照顺序来执行的,进入基本块只能从第一条命令进入,退出基本块只能从最后一条命令退出,也就是说基本块是一个整体,要执行的话就全都执行从头到尾的顺序执行,这样一个特性对于程序进行分析或者是对中间代码进行分析有什么好处呢?对程序基本块中变量的性质是可判定的,假如不是基本块的话,x=10;L y=x+1;如果说只能从x=10这条语句顺序执行的话,y=x+1,这个x就是一个已知的,就是10,y就是11.但是假如说它有另外一个入口,其他地方有一个goto L,就不能判断x的值是不是10,因为外面有一个转移,比方说x=1; goto L x的值就不一定是10了,不是基本块的话程序的性质就不太好判断
    • 假如说是一个基本块都是顺序往下执行的话,那么每一个变量的值是怎么获取的、怎么传播出来的,就可以判断出来,这对我们的处理就非常有意义。因此在基本块上做优化使得问题变的相对简单了。

    (二)基本块的划分原则

    在这里插入图片描述

    1. 进入一个程序,(整个程序的第一条)四元式就是一个基本块的入口四元式;
    2. 遇到一个转移性的四元式,这条转移性的四元式是结束了一个基本块,它的后续四元式就可以作为下一个基本块的第一条四元式;
    3. 遇到一个定位性的四元式或者是标号性的四元式,就结束一个基本块,并作为下一个基本块的第一条四元式;
    4. 那么遇到一些函数的结束标示,就结束当前的四元式。例如p=&x; *p=5; y=x+x; 因为p是间接取址的,所以要结束这个标准块,否则也还是不知道如何来判断。

    在这里插入图片描述
    比方说goto还有(then t1,- ,-)目标程序运行到这的时候要判断t1是真是假,如果是假的话就要跳过t1,所以一定是要产生一个跳转指令的,还比如else这种,也就是说s1执行完一定要产生一个跳转指令跳过s2。
    在这里插入图片描述
    比方说循环指令中的while四元式,当循环体循环结束之后要产生一个跳转指令,要转移到前面重复计算的表达式的位置,假如没有这样一个四元式, 就没有办法确定转移到什么地方。这样的四元式就起到一个定位型四元式,还有比方说endif等等。还有对间接变量的赋值,也表示一个基本块的结束,这是基本块划分的原则,总的来说最关键的两点就是遇到转移型四元式和定位型四元式的开始
    在这里插入图片描述
    在这里插入图片描述

    五、常表达式节省

    在编译过程中能够计算出值的表达式,就在中间代码这级给它计算一个结果,这样就不需要在目标程序执行的时候进行计算了。
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    1. 首先构造一个表,即变量的值表,表中元素是一个二元组,表项左部是一个变量名或者是一个临时变量,右边是已知它的值是什么,就填到这里。
    2. 以后的优化算法也就比较简单,通常来说是这样做的:进入到一个基本快的时候把这个表清空,遇到一个运算型的四元式,比方说有算符 a b t1,首先看一下a和b是不是常量,如果是常量当然可以进行计算,就把t1填到表里。如果是变量的话,就要去表中查一下有没有变量对应的值,如果有值,就把这个变量用值来替换然后来看看可不可以进行计算,能计算就进行计算,不能计算替换完了之后,值就放到四元式中。
    3. 如果遇到一个赋值型四元式,比方说b=a,就要到表里去查a有没有值,如果a是已知的,就把b填到表里,把a的值取出来填给b。按照这样顺序进行计算,能够算出常量值的四元式就被节省掉了。这里要注意,运算型的四元式实际上第一步,严格来说,用常量值替代运算符,比方说3*3.14 t1,就算出t1的结果,以后用到t1的时候就从表里取t1的值就可以了
    4. 中间可以夹杂着用常量定值表对原有四元式进行替换,如果四元式都变成常量的就删除,否则就留着

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • A、 源程序优化 B、 中间代码优化 C、 目标代码优化 正确答案: BC 我的答案:BC 答案解析: 编译阶段的优化分为中间代码优化和目标代码优化 5 【多选题】根据源程序信息来源的不同,中间代码优化方法分为哪几种?...
  • 对于一个给定的程序,我们可以把它划分为一系列的基本块。...局限于基本块范围内的优化称为基本块内的优化,或者称为局部优化。所谓基本块,是指程序中一个顺序执行的语句序列,其中只有一个入口和一个出口。 ...
  • 公共子表达式 * 消除公共子表达式可以得到更简洁的优化代码 * 如果这里有C:=c+1还可以消除吗不可以 * 一种可行的方法是将数组变量a作为一个单独的变量进行考虑将形如x = a[i]的中间代码都表示为x = a [] j其中[]为数...
  • 智能优化算法:麻雀搜索算法-附代码

    万次阅读 多人点赞 2020-09-27 16:34:00
    2020智能优化算法:麻雀搜索算法-附代码 文章目录2020智能优化算法:麻雀搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:麻雀搜索算法(Sparrow Search Algorithm, SSA)是于2020年提出的。SSA ...
  • 内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成
  • 代码优化

    2017-10-29 22:56:41
    所谓代码优化是指对程序代码进行等价(指不改变程序的运行结果)变换。程序代码可以是中间代码(如四元式代码),也可以是目标代码。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。优化的含义是...
  • 本节对UCC编译器的中间代码生成及优化进行简介,给出基本块BasicBlock、三地址码、控制流图CFG的相应数据结构,介绍有条件跳转、无条件跳转和间接跳转等概念。
  • 词法分析程序:读字符流的源程序、识别单词 语法分析程序:层次分析,把源程序的单词序列组成语法短语(表示成语法树). ...代码优化程序: 优化中间代码,节省时间、空间 目标代码生成程序 :转换为机器指令上的绝对指...
  • 中间代码生成中的优化

    千次阅读 2013-07-08 21:56:08
    1) 消除仅初始化一次的临时变量:遍历所有中间变量,对于仅仅在t := x时进行 ...会产生中间代码t1 := #0,  return t1经过优化后变为return #0  2) 常量计算:遍历所有中间变量,对于x := y +/-/*// z的中间

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 260,427
精华内容 104,170
关键字:

中间代码优化方法