精华内容
下载资源
问答
  • 2020-12-11 20:52:32

    优化原因

    • 逐条语句进行的代码生成策略经常产生含有大量冗余指令和次最优解结构的目标代码。
    • 代码优化就是被优化程序进行一种语义保持的变换

     

    优化位置

    • 中间代码优化(与机器无关)
    • 目标代码优化(与机器有关)

     

    优化分类

    • 局部优化
    • 循环优化
    • 全局优化

     

    优化技术

    • 删除公共子表达式t1 = 4 * it2 = 4 * i的右侧是公共的,优化为t1 = 4 * it2 = t1
    • 复写传播t1 = f[t2]t3 = t2t4 = f[t3]优化为t1 = f[t2]t3 = t2t4 = f[t2]
    • 删除无用表达式:把上面的t3 = t2删掉(事实上,复写传播的目的正是使某些变量的复制变为无用)
    • 强度削弱t1 = 4 * i,i的值每次循环减1,优化为t1 = t1 - 4,将强度较高乘法运算优化为强度较低的加法运算
    • 删除归纳变量:若存在线性关系t1 = 4 * it2 = 4 * j,则i > j优化为t1 > t2

     
     

    流图构造

    ——— 根据中间代码构造流图需要三步:

    1. 入口语句程序的第一句 + 转移语句的目标句 + 转移语句的下一句
    2. 根据入口语句划分基本块
    3. 画图

    ——— 例题练手 >_<:

    (1) read x
    (2) read y
    (3) r = x mod y
    (4) if r = 0 goto (8)
    (5) x = y
    (6) y = r
    (7) goto (3)
    (8) write y
    (9) end
    
    1. 找入口语句:(1) (3) (5) (8)
    2. 划分基本块:(1)(2); (3)(4); (5)(6)(7); (8)(9)
    3. 画图
      在这里插入图片描述

     
     
     

    DAG优化

    (1) T0 = 3.14
    (2) T1 = 2 * T0
    (3) T2 = R + r
    (4) A = T1 * T2
    (5) B = A
    (6) T3 = 2 * T0
    (7) T4 = R + r
    (8) T5 = T3 * T4
    (9) T6 = R - r
    (10) B = T5 * T6
    

    在这里插入图片描述

    (1) T0 = 3.14
    (2) T1 = 6.28
    (3) T3 = 6.28
    (4) T2 = R + r
    (5) T4 = T2
    (6) A = 6.28 * T2
    (7) T5 = A
    (8) T6 = R - r
    (9) B = A * T6
    

     
     
     
     

     
     
     
     

     
     
     
     

    E N D END END

    更多相关内容
  • 编译原理之代码优化

    万次阅读 多人点赞 2017-12-18 10:43:49
    编译原理出于代码编译的模块化组装考虑,一般会在语义分析的阶段生成平台无关的中间代码,经过中间代码级的代码优化,而后作为输入进入代码生成阶段,产生最终运行机器平台上的目标代码,再经过一次目标代码级别的...

    前面介绍完了词法分析、语法分析和语义分析,以及各阶段如何利用符号表来实现代码合理性确认以及代码地址拉链式回填等工作。编译原理出于代码编译的模块化组装考虑,一般会在语义分析的阶段生成平台无关的中间代码,经过中间代码级的代码优化,而后作为输入进入代码生成阶段,产生最终运行机器平台上的目标代码,再经过一次目标代码级别的代码优化(一般和具体机器的硬件结构高度耦合,复杂且不通用)。故而出于理解编译原理的角度考虑,代码优化一般都是以中间代码级代码优化手段作为研究对象。


    代码优化按照优化的代码块尺度分为:局部优化、循环优化和全局优化。即
    1. 局部优化:只有一个控制流入口、一个控制流出口的基本程序块上进行的优化;
    2. 循环优化:对循环中的代码进行的优化;
    3. 全局优化:在整个程序范围内进行的优化。

    1. 常见的代码优化手段

    常见的代码优化技术有:删除多余运算、合并已知量和复写传播,删除无用赋值等。采用转载自《编译原理》教材中关于这些优化技术的图例快速地展示下各优化技术的具体内容。

    针对目标代码:

    P := 0
    for I := 1 to 20 do 
        P := P + A[I]*B[I] 

    假设其翻译所得的中间代码如下



    1. 删除多余运算
    分析上图的中间代码,可以发现 (3)和式 (6)属于重复计算( 因为I并没有发生变化),故而式 (6)是多余的,完全可以采用 T4∶=T1代替。

    2. 代码外提
    减少循环中代码总数的一个重要办法是循环中不变的代码段外提。这种变换把循环不变运算,即结果独立于循环执行次数的表达式,提到循环的前面,使之只在循环外计算一次。针对改定的例子,显然数组A和 B的首地址在计算过程中并不改变,则作出的改动如下

    3. 强度削弱
    强度削弱的本质是把强度大的运算换算成强度小的运算,例如将乘法换成加法运算。针对上面的循环过程,每循环一次,I的值增加1T1的值与I保持线性关系,每次总是增加4。因此,可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算,而在循环中将其变换成加法运算。

    4. 变换循环控制条件
    IT1始终保持T1=4*I的线性关系,因此可以把四元式(12)的循环控制条件I≤20变换成T1≤80,这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后,循环中I的值在循环后不会被引用,四元式(11)成为多余运算,可以从循环中删除。变换循环控制条件可以达到代码优化的目的。

    5. 合并已知量和复写传播
    四元式(3)计算4*I时,I必为1。即4*I的两个运算对象都是编码时的已知量,可在编译时计算出它的值,即四元式(3)可变为T1=4,这种变换称为合并已知量。

    四元式(6)T1的值复写到T4中,四元式(8)要引用T4的值,而从四元式(6)到四元式(8)之间未改变T4T1的值,则将四元式(8)改为T6∶=T5[T1],这种变换称为复写传播。

    6. 删除无用赋值
    (6)T4赋值,但T4未被引用;另外,(2)(11)对I赋值,但只有(11)引用I。所以,只要程序中其它地方不需要引用T4I,则(6)(2)(11)对程序的运行结果无任何作用。我们称之为无用赋值,无用赋值可以从程序中删除。至此,我们可以得到删减后简洁的代码

    2. 基本块内的局部优化

    1. 基本块的划分
      入口语句的定义如下:
      ① 程序的第一个语句;或者,
      ② 条件转移语句或无条件转移语句的转移目标语句;
      ③ 紧跟在条件转移语句后面的语句。
    有了入口语句的概念之后,就可以给出划分中间代码(四元式程序)为基本块的算法,
      其步骤如下:
      ① 求出四元式程序中各个基本块的入口语句。
      ② 对每一入口语句,构造其所属的基本块。它是由该入口语句到下一入口语句(不包括下一入口语句),或到一转移语句(包括该转移语句),或到一停语句(包括该停语句)之间的语句序列组成的。
      ③ 凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句,因而也是不会被执行到的语句,可以把它们删除。

    2. 基本块的优化手段
    由于基本块内的逻辑清晰,故而要做的优化手段都是较为直接浅层次的。目前基本块内的常见的块内优化手段有:
    1. 删除公共子表达式
    2. 删除无用代码
    3. 重新命名临时变量 (一般是用来应对创建过多临时变量的,如t2 := t1 + 3如果后续并没有对t1的引用,则可以t1 := t1 + 3来节省一个临时变量的创建
    4. 交换语句顺序
    5. 在结果不变的前提下,更换代数操作(x∶=y**2是需要根据**运算符重载指数函数的,这是挺耗时的操作,故而可以用强度更低的x∶=y*y来代替
    根据以上原则,对如下代码进行优化

    t1 := 4 - 2
    t2 := t1 / 2 
    t3 := a * t2
    t4 := t3 * t1
    t5 := b + t4
     c := t5 * t5

    给出优化的终版代码

       t1 := a + a
       t1 := b + t1
        c := t1 * t1

    显然代码优化的工作不能像上面那样的人工一步步确认和遍历,显然必然要将这些优化工作公理化。而一般到涉及到数据流和控制流简化的这种阶段,都是到了图论一展身手的时候。

    3. DAG(无环路有向图)应用于基本块的优化工作
    在DAG图中,通过节点间的连线和层次关系来表示表示式或运算的归属关系:
    ① 图的叶结点,即无后继的结点,以一标识符(变量名)或常数作为标记,表示这个结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址,则用addr(A)作为这个结点的标记。
    ② 图的内部结点,即有后继的结点,以一运算符作为标记,表示这个结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
    (注:该部分内容转载自教材《编译原理》第11章DAG无环路有向图应用于代码优化)

    DAG构建的流程如下

    对基本块的每一四元式,依次执行:
      1. 如果NODE(B)无定义,则构造一标记为B的叶结点并定义NODE(B)为这个结点;
      如果当前四元式是0型,则记NODE(B)的值为n,转4。
      如果当前四元式是1型,则转2.(1)。
      如果当前四元式是2型,则:(Ⅰ)如果NODE(C)无定义,则构造一标记为C的叶结点并定义NODE(C)为这个结点,(Ⅱ)转2.(2)。
      2. 
      (1) 如果NODE(B)是标记为常数的叶结点,则转2.(3),否则转3.(1)。
      (2) 如果NODE(B)和NODE(C)都是标记为常数的叶结点,则转2.(4),否则转3.(2)。
      (3) 执行op B(即合并已知量),令得到的新常数为P。如果NODE(B)是处理当前四元式时 新构造出来的结点,则删除它。如果NODE(P)无定义,则构造一用P做标记的叶结点n。置NODE(P)=n,转4.。
      (4) 执行B op C(即合并已知量),令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点,则删除它。如果NODE(P)无定义,则构造一用P做标记的叶结点n。置NODE(P)=n,转4.。
      3.
      (1) 检查DAG中是否已有一结点,其唯一后继为NODE(B),且标记为op(即找公共子表达式)。如果没有,则构造该结点n,否则就把已有的结点作为它的结点并设该结点为n,转4.。
      (2) 检查DAG中是否已有一结点,其左后继为NODE(B),右后继为NODE(C),且标记为op(即找公共子表达式)。如果没有,则构造该结点n,否则就把已有的结点作为它的结点并设该结点为n。转4.。
      4.
      如果NODE(A)无定义,则把A附加在结点n上并令NODE(A)=n;否则先把A从NODE(A)结点上的附加标识符集中删除(注意,如果NODE(A)是叶结点,则其标记A不删除),把A附加到新结点n上并令NODE(A)=n。转处理下一四元式。

    说着很复杂,下面看一个案例

    (1) T0∶=3.14
    (2) T1∶=2 * T0
    (3) T2∶=R + r
    (4) A∶=T1 * T2
    (5) B∶=A
    (6) T3∶=2 * T0
    (7) T4∶=R + r
    (8) T5∶=T3 * T4
    (9) T6∶=R - r
    (10) B∶=T5 * T6

    其DAG图的构建过程如下

    通过DAG图可以发现诸多的优化信息,如重复定义、无用定义等,则根据上图的DAG图可以构建最后的优化代码序列

      (1) S1∶=R+r
      (2) A∶=6.28*S1
      (3) S2∶=R-r
      (4) B∶=A *S2

    3.循环优化

    根据上面基本块的定义,我们将诸多基本块组装在一起,构建成程序循环图,如针对下面这个例子

      (1) read x
      (2) read y
      (3) r∶=x mod y
      (4) if r=0 goto (8)
      (5) x∶=y
      (6) y∶=r
      (7) goto (3)
      (8) write y
      (9) halt

    则按照上面基本块的划分,可以分成四个部分,四个部分的控制流分析可知可以得到一个循环图

    循环块最主要的特点是只有一个数据流和控制流入口,而出口可能有多个。循环优化的主要手段有:循环次数无关性代码外提、删除归纳变量和运算强度削弱。关于这三种手段的理解可以借助此前的描述进行类比,基本并无太多差异。

    展开全文
  • 第一步,用一个编译程序把高级语言翻译成机器语言程序; 第二步,运行所得的机器语言程序求得计算结果。 1.几种基本的翻译程序 1.1翻译程序 通常所说的翻译程序是指这样的一个程序,它能够把某一种语言程序(称为源...


    要在计算机上执行用 高级语言(或汇编语言)编写的程序,必须通过特定的途径来进行,也就是要通过 翻译程序把用高级语言(或汇编语言)编写的程序翻译成为机器语言构成的程序,计算机才能执行。
    在计算机上执行一个高级语言程序一般要分为两步:
    第一步,用一个编译程序把高级语言翻译成机器语言程序;
    第二步,运行所得的机器语言程序求得计算结果。

    1.几种基本的翻译程序

    1.1翻译程序

    通常所说的翻译程序是指这样的一个程序,它能够把某一种语言程序(称为源语言程序或源程序)转换成另一种语言程序(称为目标语言程序或目标程序)
    在这里插入图片描述

    1.2汇编程序(Assembler)

    如果源语言是某种汇编语言,而目标语言是某种计算机的机器语言,这样的一个翻译程序就称为汇编程序。
    在这里插入图片描述

    1.3编译程序(Compiler)

    如果源语言是某种高级语言,而目标语言是某种低级语言(汇编语言或机器语言),这样的一个翻译程序就称为编译程序。在这里插入图片描述

    1.4解释程序(Interpreter)

    这是另外一种类型的翻译程序,在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译(解释),边解释边执行直至结束,它不产生目标程序,它的工作结果就是源程序的执行结果,这样的一个翻译程序就称为解释程序。在这里插入图片描述

    1.5总结

    编译程序与其他几种翻译程序的区别在于源语言和目标语言的不同,编译程序的源语言是某种高级语言,功能是将其翻译成某种低级语言。
    根据不同的用途,编译程序可进一步分类:
    (1)诊断编译程序(Diagnostic Compiler): 专门用于帮助程序开发和调试的编译程序。
    (2)优化编译程序(Optimizing Compiler): 着重于提高目标代码效率的编译程序。
    (3)交叉编译程序(Cross Compiler): 如果一个编译程序产生不同于其宿主机的机器代码。
    (4)可变目标编译程序(Retargetable Compiler): 不需重写编译程序中与机器无关的部分就能改变目标机。

    2.编译程序的运行过程

    编译程序的工作过程一般可以划分为五个阶段:
    1.词法分析——2.语法分析——3.语义分析——4.中间代码产生、优化——5.目标代码生成。
    在这里插入图片描述

    2.1词法分析(Lexical analysis)

    此阶段的任务是: 输入源程序,对构成源程序的字符串进行扫描和分解,识别出一个个的单词。在词法分析阶段的工作中所依循的是语言的词法规则(或称构词规则)。描述词法规则的有效工具是正规式,识别词法规则的有效工具是有限自动机。在这里插入图片描述

    2.2语法分析(Syntax Analysis)

    此阶段的任务是:在词法分析的基础上,根据语言的语法规则,把单词符号串分解成各类语法单位(语法范畴),如“短语”、“子句”、“句子”(“语句”)、“程序段”和“程序”等。通过语法分析,确定整个输入串是否构成语法上正确的“程序”。
    语法分析所依循的是语言的语法规则。语法规则通常用上下文无关文法描述。词法分析是一种线性分析,而语法分析是一种层次结构分析。
    例如,在很多语言中,符号串 z:=X十0.618*Y 代表一个“赋值语句”,而其中的 X+0.618*Y代表一个“算术表达式”。因而,语法分析的任务就是识别 X+0.618*Y为算术表达式,同时,识别上述整个符号串属于赋值语句这个范畴。

    2.3语义分析与中间代码产生(Semantic Analysis and Intermediate Generator)

    此阶段的任务是:对语法分析所识别出的各类语法范畴,分析其含义,并进行初步翻译(产生中间代码)。
    语义处理:
    ①变量的存储分配 ②表达式的求值 ③语句的翻译(中间代码的生成)
    中间代码
    中间代码是一种独立于具体硬件的记号系统。
    常用的中间代码:三地址码(四元式、三元式、间接三元式),逆波兰式,树形表示等。所谓“中间代码”是一种含义明确、便于处理的记号系统,它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近,或者能够比较容易地把它变换成现代计算机的机器指令。

    2.4优化(Optimization)

    优化的任务:对产生的中间代码进行加工变换,以期在最后阶段能产生出更为高效(省时间和空间)的目标代码。
    优化的主要方面有:公共子表达式提取、循环优化、删除无用代码等等。有时,为了便于“并行运算”,还可以对代码进行并行化处理。优化所依循的原则:程序的等价变换规则。

    2.5目标代码生成(Code Generation)

    这一阶段的任务是:把中间代码(或经优化处理之后)变换成特定机器上的低级语言代码。
    目标代码的三种形式:
    1.汇编语言代码 2.能够立即执行的机器语言代码 3.待装配的机器代码模块

    3.表格管理 (symbol-table manager)

    编译程序在工作过程中需要保存一系列的表格,以登记源程序的各类信息和编译各阶段的进展状况。合理地设计和使用表格是编译程序构造的一个重要问题。在编译程序使用的表格中,最重要的是符号表。它用来登记源程序中出现的每个名字以及名字的各种属性。

    4.出错处理(error handler)

    一个编译程序不仅应能对书写正确的程序进行翻译,而且应能对出现在源程序中的错误进行处理。
    源程序中的错误通常分为语法错误和语义错误两大类。
    语法错误是指源程序中不符合语法(或词法)规则的错误,它们可在词法分析或语法分析时检测出来。例如,词法分析阶段能够检测出“非法字符”之类的错误;语法分析阶段能够检测出诸如“括号不匹配”、“缺少;”之类的错误。
    语义错误是指源程序中不符合语义规则的错误,这些错误一般在语义分析时检测出来,有的语义错误要在运行时才能检测出来。语义错误通常包括:说明错误、作用域错误、类型不一致等等。

    5.编译前端与后端

    编译过程划分为前端和后端的目的:在多种源语言和多种目标语言的开发过程中,可以灵活搭配前端和后端,消除重复开发的工作量,提高编译系统的开发效率。
    前端主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码产生,有的代码优化工作也可包括在前端。
    后端包括编译程序中与目标机有关的那些部分,如与目标机有关的代码优化和目标代码生成等。通常,后端不依赖于源语言而仅仅依赖于中间语言。

    展开全文
  • 编译原理】中间代码优化(三) 循环优化

    千次阅读 多人点赞 2020-06-29 18:02:54
    也正是由于这部分代码序列可能会被反复执行,所以在进行中间代码优化时应着重考虑循环优化,这对提高目标代码的效率起到很大的作用。为了进行循环优化,首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构...

    循环优化概述.

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

    计算必经节点集.

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

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

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

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

    循环查找算法.

    1.查找回边.

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

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

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

    在这里插入图片描述

    2.查找循环.

    求出了程序流图中的回边之后,我们就可以基于回边来查找循环。具体的方法是,若<N i _i i→N j _j j>是一条回边,那么该回边构成的循环中的结点包括:N i _i i和N j _j j以及所有不经过N i _i i能够到达N j _j 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】

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

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

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

    I:=3
    if X<Y goto B3
    

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

    强度削弱.

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

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

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

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

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

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

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

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

    删除归纳变量.

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

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

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

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

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

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

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

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

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

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

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

    展开全文
  • 程序编译代码优化

    千次阅读 2016-05-31 15:20:23
    一早期(编译期)优化 1概述 Java语言的“编译期”是一段“不确定”的操作过程,因为它可能是指一个前端编译器(其实叫“编译器的前端”更准确一些)把*.java文件转变成*.class文件的过程;也可能是指虚拟机的...
  • 优化其实可以在编译的各个阶段进行,但最主要的一类优化是在目标代码生成以前,对语法分析、语义分析后产生的中间代码进行优化。这是因为中间代码的形式不依赖于具体的计算机,它可以是三地址码的形式,所以相应的...
  • 文章目录早期(编译期)优化概述Javac编译器Javac的源码与调试解析与填充符号表注解处理器语义分析与字节码生成Java 语法糖的味道泛型与类型擦除自动装箱、拆箱与遍历循环条件编译实战:插入式注解处理器晚期(运行...
  • 两个编译器必须等价,编译的结果必须是正确的,即使有99.99%的可能性是不正确的,但是效率很好也不行,正确性是根本。 二、中间代码优化的分类 从优化的种类来看,中间代码的优化可有如下分类: 局部优化 循环上...
  • 对于一个给定的程序,我们可以把它划分为一系列的基本块。在各个基本块范围内,分别进行优化。局限于基本块范围内的优化称为基本...所谓基本块,是指程序中一个顺序执行的语句序列,其中只有一个入口一个出口。 ...
  • 以基本块为单位,进行运算上的推导优化。堪称妙!原来编译器这么强大!
  • 编译原理过程简述及中间代码优化

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

    千次阅读 2020-02-18 18:34:47
    声明:本系列文章,是根据中国大学MOOC网 哈工大的编译原理 这门课学习而成的学习笔记。 一、流图 基本块(Basic Block) 基本块是满足下列条件的最大的连续三地址指令序列 控制流只能从基本块的第一个指令进入该块...
  • 解释程序和编译程序的区别

    万次阅读 多人点赞 2019-05-09 15:13:56
    编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成6个阶段。目标程序可以独立于源程序运行。(编译程序是一个语言处理程序,它可以把高级语言程序给语言翻译成某个机器的汇编语言...
  • 关于keil编译优化代码大小的方法

    千次阅读 2020-09-10 15:44:22
    2,代码优化等级 说明: level 0 :近乎不优化,用于调试代码。出现代码行不能设置断点可如此设置试试。 level 1 :部分优化。移除未调用的内联函数静态函数,关闭debug窗口优化,此状态也能用于调试 ...
  • 其理论基础坚实,其形式化系统不仅用于编译程序,还大量用于人工智能、多媒体技术、数据库等领域。 程序设计语言 低级程序语言 特定的计算机系统所固有的语言 即:机器语言、汇编语言 特点:执行效率高、编制效率...
  • 编译程序完成从源程序到目标程序的翻译工作,是一个复杂的整体的过程。从概念上来讲,一个编译程序的整个工作过程是划分成阶段进行的,每个阶段将源程序的一种表示形式转换成另一种表示形式,各个阶段进行的操作在...
  • 代码优化_11 优化可生成()的目标代码。A. 运行时间较短B. 占用存储空间较小C. 运行时间短但占用内存空间大D. 运行时间短且占用存储空间小 2 基本块内的优化为 ( )。A. 代码外提,删除归纳变量B. 删除多余运算,...
  • 编译程序和解释程序有什么区别?

    千次阅读 2020-05-26 22:52:19
    1. 编译程序和解释程序的区别: 编译型是使用编译器编译后生成计算机硬件可直接执行的指令,解释型是在运行时才由解释器逐语句去执行。 编译型代表:C&C++,C#,Java,解释型代表:html,javascript。区别有很多...
  • 编译程序基本原理

    万次阅读 2018-06-25 21:40:01
    编译程序和解释程序 人们利用高级语言与计算机进行交互, 但计算机仍然只能理解执行由 0, 1序列构成的机器语言, 因此高级程序设计语言需要翻译, 担负这一任务的程序称为"语言处理程序", 由于应用的不同, 语言之间...
  • 用机器语言编制程序效率低,可读性差,也难以理解修改维护。因此,人民设计了汇编语言,用容易记忆的符号代替0,1序列,来表示机器指令中的操作码操作数。但汇编语言是面向机器的语言,其书写格式在很大程度上取...
  • 代码:采用某种编程语言编写的计算机程序,人类可读
  • 编译过程概述
  • 编译原理——编译程序的组成

    千次阅读 2020-09-15 13:42:05
    编译原理概述
  • vs代码优化

    千次阅读 2018-07-31 11:42:38
    VS-IDE代码优化: 属性-&gt;配置属性-&gt;C/C++-&gt;代码生成:启用增强指令集,可选用 流式处理 SIMD 扩展 2 (/arch:SSE2) (/arch:SSE2)、流式处理 SIMD 扩展 2 (/arch:SSE2) (/arch:SSE2) 进行加速...
  • 编译原理:什么是编译程序

    千次阅读 2018-04-28 10:25:08
    一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节,使程序员程序设计专家独立于机器,这对于当今机器的数量种类持续不断增长的年代尤为重要。 编译程序的功能: 高级语言程序...
  • 一般整个过程可划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成6个阶段。 有一种说法 编译有七个过程 预处理,词法分析,语法分析,语义分析,中间代码产生,代码优化,目标代码产生。...
  • 什么是编译程序

    万次阅读 2017-05-19 16:04:45
    代码优化;目标代码生成。主要是进行词法分析语法分析,又称为源程序分析,分析过程中发现有语法错误,给出提示信息。 (1) 词法分析 编译程序也叫编译系统,是把用高级语言编写的面向过程的源程序翻译成目标...
  • A 便于目标代码优化 B 便于存储空间的组织 C 便于目标代码的移植 D 便于编译程序的移植 逆波兰表示法表示表达式时无须使用括号。正确 四元式之间的联系是通过(B)实现的。 A 指示器 B 临时变量 C 符号...
  • 1、何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间有何种关系? 源程序 用汇编语言或高级语言编写的程序称为源程序 目标程序 用目标语言所表示的程序 目标语言:机器语言或汇编语言 翻译程序 将源...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 396,149
精华内容 158,459
关键字:

和代码优化不是编译程序必须的