精华内容
下载资源
问答
  • 编译原理之代码优化

    万次阅读 多人点赞 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

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

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

    展开全文
  • 编译原理代码优化

    2012-11-28 18:43:49
    编译原理 代码优化 详细介绍编译原理代码优化方法
  • 编译原理 代码优化

    2012-06-08 14:29:30
    编译原理代码优化,有解答和题目
  • 包括公共子表达式优化、常表达式优化和循环不变式优化
  • 代码优化就是被优化程序进行一种语义保持的变换   优化位置 中间代码优化(与机器无关) 目标代码优化(与机器有关)   优化分类 局部优化 循环优化 全局优化   优化技术 删除公共子表达式:t1...

    优化原因

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

     

    优化位置

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

     

    优化分类

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

     

    优化技术

    • 删除公共子表达式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

    展开全文
  • 编译原理之 代码优化 华东交通大学软件学院 万仲保 第11章 代码优化 优化技术简介 局部优化 控制流分析和循环优化 数据流的分析与全局优化 优化技术简介 优化概念 优化分类 优化技术 优化概念 优化实质上是对代码...
  • 代码优化部分的内容主要参考张素琴等《编译原理》(1998,清华大学出版社)。由中大计算机系李文军教授编写
  • 编制程序,完成局部优化过程中的基本块划分。给定一段代码,判定程序的入口语句,划分基本块,删除无用产生式和冗余节点。
  • 编译原理之代码生成

    千次阅读 2017-12-18 16:13:41
    前面提到了经过了词法分析->语法分析->语义分析->中间代码优化,最后的阶段...所以将编译原理分成这种多阶段多模块的组织形式,本质的考虑其实只有两个方面: 一、代码复用:尽可能在不增加程序员工作量的前提下,增

    前面提到了经过了词法分析->语法分析->语义分析->中间代码优化,最后的阶段便是在目标机器上运行的目标代码的生成了。目标代码生成阶段的任务是:将此前的中间代码转换成特定机器上的机器语言或汇编语言,这种转换程序便被称为代码生成器。

    1. 程序移植性和编译器模块设计的关系

    之所以将编译原理分成这种多阶段多模块的组织形式,本质的考虑其实只有两个方面:
    一、代码复用:尽可能在不增加程序员工作量的前提下,增加应用程序的可移植性。
    可我们知道不同机器的机器指令集和硬件结构,千差万别,而前面又提到了为了将程序的执行效率提升到最大,显然是需要将软件按照硬件特性极尽可能地定制化优化,其实现在AI芯片的发展趋势也是这种思想的另一面体现。现今AI芯片为了加速深度学习为代码的超强度计算效率,出现了针对具体程序架构定制化芯片的需求,如CPU->GPU的发展,便是GPU迎合了深度学习单轮多次简单运算的需求,CPU->FPGA的矩阵运算侧重也是Facebook引领的另一硬件绑定具体软件计算需求的工程案例,而最为极端者莫过于当下Google推出的TPU计算芯片,完全剔除不必要的硬件设备,根据Google的深度学习Tensorflow架构定制化的计算芯片,更是以极致的定制化获取比CPU计算速度高200倍的显著成果。)。

    所以再一次验证了“银弹”理论,如果有问题解决不了,那就加一层抽象层了。所以提高代码移植性的集大成者Java,便是通过引入JVM将应用程序层和具体硬件层隔开。


    图1. Java-多目标机

    显然对于Java程序可以共享一套“词法分析+语法分析+语义分析+中间代码优化引擎”这一套前端套件,而针对不同机型的定制化目标代码生成器则可以通过官方渠道的支持和更新来组装成自己所需的后端套件组。这样便可以让程序员尽可能地有较多的自由编写的空间,极大地提升代码可移植性,而不像C++编写的DLL库,即便采用复杂的COM规则,极为小心地编写,但也可能因为编译器版本不同导致移植性不通过。

    二、特定机器的优化器和生成器复用:针对特定机器的目标代码生成和优化器的工作极为复杂精深,有一套成功的,当然要尽可能复用它。

    由于代码生成阶段的目标代码和具体计算机的结构有关,如指令格式、字长以及寄存器的个数和种类,并与指令的语义和所用操作系统等都密切相关,特别是高级语言的语义功能复杂,并且计算机硬件结构多样性都给代码生成的理论研究带来很大的复杂性,因此实际实现起来是非常困难的。所以难得生成一款后端的代码生成器,当然是想让它可以独立出来,被多次组装参与其他编译器的生产过程。


    图2. 多种语言-一种目标机型

    这种情况被称为定计算机情况:当限定某种计算机时,而高级语言为多种情况下所设计的中间语言,应能充分反映限定计算机的特点称MSIL(Machine Specific Intermediate language)。对这种机器的所有编译程序在分析阶段都生成MSIL,在实现一个编译程序时,尽量把编译过程的大量工作放在代码生成阶段,即MSIL到目标程序的翻译上,以减轻不同语言翻译的分析任务。因不管多少种高级语言,MSIL到目标程序的代码生成只需做一次即可。

    当然也正是这种组织特性,让本来是集团作战的编译器生成工作,现如今变得不再是难以企及。同时也让各行各业根据自身需求和侧重点不同,甚至可以定制化自己的行业的专属语言(Domain Specific Language)变得可实现。

    2. 代码生成的优化手段:寄存器分配

    说了这么多,其实只需要明白代码生成器是结合目标机器平台定制化的一套后端套件,这也是为何业界的主流计算机都是按照x86、x64_86这些业界标准来设计的,如果你家公司另辟蹊径自己设计出一套硬件体系,即便你能设计生产出来,但你确定IT界会有下游供应商给你设计类似于代码生成器这种配套套件吗?

    衡量最终生成的目标代码的质量无非是从两个方面来进行评估:空间占用和运行效率,这其中涉及到诸多和具体硬件绑定的细节,大多数都属于难度高且并不通用的范畴。而寄存器的使用规则则是少数具有通用的手段,故而可以借分析寄存器分配来分析一下目标代码优化和生成过程。

    Q: 为什么在代码生成时要考虑充分利用寄存器?
    A: 因为当变量值存在寄存器时,引用的变量值可直接从寄存器中取,减少对内存的存取次数,这样便可提高运行速度。因此如何充分利用寄存器是提高目标代码运行效率的重要途径。

    Q: 寄存器分配的原则是什么?
    A: (1)逻辑有效范围内尽量保留: 当生成某变量的目标代码时,尽量让变量的值或计算结果保留在寄存器中,直到寄存器不够分配时为止。
     (2) 逻辑块出口处,和内存中的源数据同步:当到基本块出口时,将变量的值存放在内存中,因为一个基本块可能有多个后继结点或多个前驱结点,同一个变量名在不同前驱结点的基本块内出口前存放的R可能不同,或没有定值,所以应在出口前把寄存器的内容放在内存中,这样从基本块外入口的变量值都在内存中
     (3) 及时释放,提升寄存器使用效率:对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放,以提高寄存器的利用效率。

    可以看到在进行缓存淘汰更新时我们采用了LRU策略,LRU策略是属于经典的“线性思维”–即过去常被使用的,在未来也会常被使用。而这里寄存器则不能采用“线性思维”,因为我们看自己的代码都知道,变量的使用虽然在局部范围还算符合“局部性原理”,但是稍微放宽到一定尺度上的变量集使用情况,则发现更多是无序的。所以在进行寄存器分配策略的研究上,只能比较粗暴点,事先将目标代码再次遍历一遍,将变量的使用情况事先整理好,并用所谓“待用信息链”的数据结构来保存每个变量的使用情况。这种策略并非LRU那种后视推导逻辑,而是耍赖的先知般论断逻辑,但是考虑到一旦将目标代码的寄存器使用效率最大化,则无疑是一劳永逸的,故而也是划算的。

    变量的待用信息链计算方法
    前面根据寄存器的使用原则可以看到,寄存器的分配是以基本块为单位的,因为基本块作为程序流的最小单元,存在着数据同步和异步的问题,故而在进行寄存器分配时,要审核的代码范围只需要涉及到当前基本块即可。

    首先为任一变量设置两个信息链:待用信息链和活跃变量信息链。

    考虑到处理的方便,可假定对基本块中的变量在出口处都是活跃的,而对基本块内的临时变量可分为两种情况处理。
      a) 一般情况下基本块内的临时变量在出口处都认为是不活跃的。
      b) 如果中间代码生成时的算法允许某些临时变量在基本块外可以被引用时,则这些临时变量也是活跃的。
      
    在基本块内计算变量的使用信息链(觉得采用栈式更符合这种信息链的更新情况),步骤如下:

    ① 对各基本块的符号表中的”待用信息”栏和”活跃信息”栏置初值,即把”待用信息”栏置”非待用”,对”活跃信息”栏按在基本块出口处是否为活跃而置成”活跃”或”非活跃”。现假定变量都是活跃的,临时变量都是非活跃的。  
    ② 倒着来从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式i:A:=B op C,依次执行下述步骤:
      a) 把符号表中变量A的待用信息和活跃信息附加到四元式i上。
      b) 把符号表中变量A的待用信息栏和活跃信息栏分别置为 “非待用” 和 “非 活跃”。由于在i中对A的定值只能在i以后的四元式才能引用,因而对i以前的四元式来说A是不活跃也不可能是待用的。
      c) 把符号表中B和C的待用信息和活跃信息附加到四元式i上。
      d) 把符号表中B和C的待用信息栏置为”i”,活跃信息栏置为”活跃”。

    说的麻烦,举个例子就好了:

      (1) T∶=A-B
      (2) U∶=A-C
      (3) V∶=T+U
      (4) D∶=V+U

    加上信息链条之后,则标记情况如下

      (1) T【(3)L】:= A【(2)L】 - B【FL】
      (2) U【(3)L】:= A【FL】 - C【FL】
      (3) V【(4)L】:= T【FF】 + U【(4)L】
      (4) D【FL】:= V【FF】 + U【FF】

    这样根据信息链表法,在每次运算到一个表达式时,如果寄存器数目不够,即无空余寄存器可用,则可以遍历一下当前在寄存器中的变量的待用信息链,然后选择接下来最远将被调用的变量释放其所占用寄存器,分配寄存器的算法为:

      ① 如果B的现行值在某寄存器Ri中,且该寄存器只包含B的值,或者BA是同一标识符,或B在该四元式后不会再被引用,则可选取Ri作为所需的寄存器R,并转(4);
      ② 如果有尚未分配的寄存器,则从中选用一个Ri为所需的寄存器R,并转(4);
      ③ 从已分配的寄存器中选取一个Ri作为所需寄存器R,其选择原则为:占用该寄存器的变量值同时在主存中,或在基本块中引用的位置最远,这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如下调整:即对RVALUE[Ri]中的每一变量M,如果M不是AAVALUE[M]不包含M,则需完成以下处理;
      a) 生成目标代码ST Ri,M即把不是A的变量值由Ri中送入内存中;
      b) 如果M不是B,则令AVALUE[M]={M},否则,令AVALUE[M]={M, Ri};
      c) 删除RVALUE[Ri]中的M;
      ④ 给出R,返回。

    至此可以看到,单纯是寄存器分配便是需要较多数据结构配合和工作时间消耗的,管中窥豹,可以看到代码生成器的一个部件工作量便是很复杂的。

    展开全文
  • 之前的传错了 云南大学编译原理-实现代码优化
  • 编译原理试验报告 课题:中间代码优化;表达式语法分析等 包含所有的报告以及C++与程序
  • 编译 原理 第五章 代码 优化 课后 答案 好东西大家来下载
  • 代码外提 (3) 基本块内的优化为 a. 代码外提删除归纳变量 b. 删除多余运算删除无用赋值 c. 强度削弱代码外提 d. 循环展开循环合并 (4) 在程序流图中我们称具有下述性质 的结点序列为一个循环 a. 它们是非连通的且...
  • 编译原理DAG的优化

    2013-03-14 15:52:21
    编译原理的课设,DAG的优化,内有源代码
  • 编译原理:第11章 代码优化.pdf
  • 编译原理过程简述及中间代码优化

    千次阅读 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、 公共子表达式的删除、复制传播、无用代码删除、代码外提、强度削弱和归纳变量删除等都是一些常用的针对局部或者全局的代码优化方法。

    展开全文
  • 东北大学编译原理实验报告,用编译语言实现目标代码优化,有详细的代码
  • 基本块构造DAG的算法 for (i=0;i;i++) /*QlistLenth 值为基本块中四元式的个数*/ {  取出第i四元式Qi; if (NODE(B)==NULL) {  建立一个以B为标记的叶结点,其编号为NODE (B);
  • 也正是由于这部分代码序列可能会被反复执行,所以在进行中间代码优化时应着重考虑循环优化,这对提高目标代码的效率起到很大的作用。为了进行循环优化,首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构...
  • 优化其实可以在编译的各个阶段进行,但最主要的一类优化是在目标代码生成以前,对语法分析、语义分析后产生的中间代码进行优化。这是因为中间代码的形式不依赖于具体的计算机,它可以是三地址码的形式,所以相应的...
  • 对于一个给定的程序,我们可以把它划分为一系列的基本块。...局限于基本块范围内的优化称为基本块内的优化,或者称为局部优化。所谓基本块,是指程序中一个顺序执行的语句序列,其中只有一个入口和一个出口。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,517
精华内容 58,206
关键字:

编译原理之代码优化