精华内容
下载资源
问答
  • 编译原理代码优化
    千次阅读
    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

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

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

    千次阅读 2018-10-22 01:34:29
    代码优化: 因为抽象语法树中可能包括错误,因此不能在抽象语法树阶段进行优化。 函数式的优化:输入一个抽象语法树,输出一个抽象语法树: 在循环中,如果E仍在缩小,就持续常量折叠。 本来...

    代码优化:

    因为抽象语法树中可能包括错误,因此不能在抽象语法树阶段进行优化。

    函数式的优化:输入一个抽象语法树,输出一个抽象语法树:

    在循环中,如果E仍在缩小,就持续常量折叠。

    本来预期是异常,但是优化之后,如果不报异常了,那也是错误的。

    中间代码优化

    这个与单纯的语法制导翻译不同,是结合上下文的。

    即如果变量在后面不会用到,就可以将这代码优化掉。

     

    展开全文
  • 代码优化部分的内容主要参考张素琴等《编译原理》(1998,清华大学出版社)。由中大计算机系李文军教授编写
  • 编译原理代码优化

    千次阅读 2021-10-07 21:54:55
    常用的优化方法 删除公共子表达式 删除无用代码 常量合并 代码移动 强度削弱 删除归纳变量 基本块的优化: 局部优化技术大部分都是将基本块转为有向无环图(DAG). 每个语句s都对应一个内部结点N 结点N的标号是s中...


    前言

    定值: 对变量的赋值即为定值,这将会kill掉之前对变量的定值。
    引用:对变量的使用。

    活跃范围: 从定值到最后一次引用即为变量的活跃范围。

    a = ...		//	10
    ....
    .... = a+1	//	20
    ...  =
    a = ...		//	25
    ...
    .... = a+2	//	40
    

    如上面代码所示,10对a进行了赋值/定值,20对a的值进行了最后一次使用,因此a的活跃范围是{10,20}。而后a的值在25被再次定值,那么a之前的定值无法被使用,也就是被kill掉。a的新值在40处被使用,a的活跃范围就是{10,20},{25,40}。

    一、基本块的优化

    局部优化技术大部分都是将基本块转为有向无环图(DAG).

    有向无环图的好处就是可以明确变量之间的依赖关系和指令执行顺序的关系。

    每个语句s都对应一个内部结点N

    • 结点N的标号是s中的运算符;同时还有一个定值变量表被关联到N ,表示s是在此基本块内最晚对表中变量进行定值的语句
    • N的子结点是基本块中在s之前、最后一个对s所使用的运算分量进行定值的语句对应的结点。

    基于DAG删除无用代码:
    删除所有没有附加活跃变量(活跃变量是指其值可能会在以后被使用的变量)的根结点(即没有父
    结点的结点) 。

    在这里插入图片描述

    二、数据流分析

    1.到达-定值分析 (Reaching-Definition Analysis)

    定值 (Definition) :变量x的定值是(可能)将一个值赋给x的语句。 如果某个变量x的一个定值d到达点p,在点p处使用的x的值可能就是由d最后赋予的。

    计算方法:
    在这里插入图片描述
    引用-定值链(Use-Definition Chains),即ud链,对于变量的每一次引用,到达该引用的所有定值都在该列表中。

    ud链的核心在于,可以通过该链,明确当前使用的链,在哪里被定值,被定值是否是常量等。

    应用:

    1. 循环不变计算的检测
      如果表达式的运算分量是常数,或者所有定值点都在循环外部,则可将该表达式标记为循环不变。可以提到循环外部。
    2. 常量合并
    3. 判定变量x在p点上是否未经定值就被引用
    4. 强度削弱

    1.1 强度削弱

    强度削弱比较复杂,展开描述:
    强度削弱利用了归纳变量和到达定值分析的结果。
    对于一个变量x ,如果存在一个正的或负的常量c ,使得每次x被赋值时,它的值总是增加c ,则称x为归纳变量。

    计算方法:
    寻找L中只有一次定值的变量k,它具有下面的形式:k=c′×j+d′。其中c′和d′是常量,j是基本的或非基本的归纳变量.

    效果:
    在这里插入图片描述

    2.活跃变量分析 (Live-Variable Analysis)

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

    活跃变量分析的核心在于,在寄存器分配时,同时活跃(即为冲突)的变量分配到不同的寄存器。
    此外,如果变量是不冲突的,那么可以进行寄存器合并,但是寄存器合并时,会导致寄存器的占用时间增长,而导致存在寄存器溢出,需要降寄存器写回内存的风险。

    计算方法:
    在这里插入图片描述

    3.定值引用链分析

    定值-引用链:设变量x有一个定值d,该定值所有能够到达的引用u的集合称为x在d处的定值-引用链,简称du链。

    1. 删除无用赋值
      如果定值之后,再也没有被引用,那么就是无用定值/赋值,可以删除。

    2. 基本块分配寄存器
      分配寄存器时,优先选择不后续不再被引用的寄存器。

    此外,在进行寄存器分配时,同时活跃的变量,即为“冲突”的,不可以将其放入同一个寄存器。
    通过画出冲突图,利用图着色算法,对寄存器进行分配。

    4.可用表达式分析 (Available-Expression Analysis)

    删除公共表达式:如果一个表达式在程序的每个分支上都进行了计算,那么在分支的汇聚出口,我们可以直接使用该表达式结果。

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

    计算方法:
    在这里插入图片描述
    用途:

    1. 消除全局公共子表达式
      在这里插入图片描述
    2. 进行复制传播
      在这里插入图片描述

    5.支配节点树(Dominator Tree)

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

    通过支配节点树,我们可以分析程序的必经路径和必经路径边界信息。

    利用支配节点树的边界信息,可以产生SSA表达式的phi节点。

    计算方法:
    在这里插入图片描述

    支配结点树的例子:
    在这里插入图片描述

    总结

    常用的优化方法

    • 删除公共子表达式 : 可用表达式
    • 复制传播 : 可用表达式
    • 删除无用代码:定值引用链
    • 常量合并:引用定值链
    • 代码移动:引用定值链
    • 强度削弱:引用定值链
    • 删除归纳变量:引用定值链

    欢迎关注我的公众号《处理器与AI芯片》

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

    2020-11-03 09:50:21
    文章目录代码优化的目标、对象、范围和策略代码优化的目标代码优化的对象代码优化的范围代码优化的策略一些优化的场景数据流分析实例图示半格理论 代码优化的目标、对象、范围和策略 代码优化的目标 代码优化的目标...

    代码优化的目标、对象、范围和策略

    代码优化的目标

    • 代码优化的目标,是优化程序对计算机资源的使用。我们平常最关心的就是 CPU 资源,最大效率地利用 CPU 资源可以提高程序的性能。代码优化有时候还会有其他目标,比如代码大小、内存占用大小、磁盘访问次数、网络通讯次数等等。

    代码优化的对象

    从代码优化的对象看,大多数的代码优化都是在 IR 上做的,而不是在前一阶段的 AST 和后一阶段汇编代码上进行的,为什么呢?

    • 其实,在 AST 上也能做一些优化,比如在讲前端内容的时候,我们曾经会把一些不必要的AST 层次削减掉(例如 add->mul->pri->Int,每个父节点只有一个子节点,可以直接简化为一个 Int 节点),但它抽象层次太高,含有的硬件架构信息太少,难以执行很多优化算法。 在汇编代码上进行优化会让算法跟机器相关,当换一个目标机器的时候,还要重新编写优化代码。所以,在 IR 上是最合适的,它能尽量做到机器独立,同时又暴露出很多的优化机会。

    代码优化的范围

    从优化的范围看,分为本地优化、全局优化和过程间优化。

    • 优化通常针对一组指令,最常用也是最重要的指令组,就是基本块。基本块的特点是:每个基本块只能从入口进入,从最后一条指令退出,每条指令都会被顺序执行。因着这个特点,我们在做某些优化时会比较方便。比如,针对下面的基本块,我们可以很安全地把第 3 行的“y:=t+x”改成“y:= 3 * x”,因为 t 的赋值一定是在 y 的前面:
    BB1:
    	t:=2 * x 
    	y:=t + x 
    	Goto BB2
    
    
    • 这种针对基本块的优化,我们叫做本地优化(Local Optimization)。

    • 超越基本块的范围进行分析,我们需要用到控制流图(Control Flow Graph,CFG)。CFG 是一种有向图,它体现了基本块之前的指令流转关系。如果从 BB1 的最后一条指令是跳转到 BB2,那么从 BB1 到 BB2 就有一条边。一个函数(或过程)里如果包含多个基本块,可以表达为一个 CFG
      在这里插入图片描述

    • 比全局优化更大范围的优化,叫做过程间优化(Inter-procedural Optimization),它能跨越函数的边界,对多个函数之间的关系进行优化,而不是仅针对一个函数做优化。

    代码优化的策略

    • 最后,你不需要每次都把代码优化做彻底,因为做代码优化本身也需要消耗计算机的资源。所以,你需要权衡代码优化带来的好处和优化本身的开支这两个方面,然后确定做多少优化。比如,在浏览器里加载 JavaScript 的时候,JavaScript 引擎一定会对 JavaScript 做优化,但如果优化消耗的时间太长,界面的响应会变慢,反倒影响用户使用页面的体验,所以JavaScript 引擎做优化时要掌握合适的度或调整优化时机。

    一些优化的场景

    代数优化(Algebraic Optimazation)

    • 代数优化是最简单的一种优化,当操作符是代数运算的时候,你可以根据学过的数学知识进
      行优化。
    • 比如“x:=x+0 ”这行代码,操作前后 x 没有任何变化,所以这样的代码可以删掉;又比如“x:=x0” 可以简化成“x:=0”;对某些机器来说,移位运算的速度比乘法的快,那么“x:=x8”可以优化成“x:=x<<3”。

    常数折叠(Constant Folding)

    • 它是指,对常数的运算可以在编译时计算,比如 “x:= 20 * 3 ”可以优化成“x:=60”。另外,在 if 条件中,如果条件是一个常量,那就可以确定地取某个分支。比如:“If 2>0Goto BB2” 可以简化成“Goto BB2”就好了。

    删除不可达的基本块

    • 有些代码永远不可能被激活。比如在条件编译的场景中,我们会写这样的程序:“if(DEBUG) {…}”。如果编译时,DEBUG 是一个常量 false,那这个代码块就没必要编译了。

    删除公共子表达式(Common Subexpression Elimination)

    • 下面这两行代码,x 和 y 右边的形式是一样的,如果这两行代码之间,a 和 b 的值没有发生变化(比如采用 SSA 形式),那么 x 和 y 的值一定是一样的。
    x := a + b 
    y := a + b
    
    • 那我们就可以让 y 等于 x,从而减少了一次“a+b”的计算,这种优化叫做删除公共子表达式
    x := a + b 
    y := x
    

    拷贝传播(Copy Propagation)和常数传播(Constant Propagation)

    • 下面的示例代码中,第三行可以被替换成“z:= 2 * x”, 因为 y 的值就等于 x,这叫做拷贝传播
    x := a + b
    y := x
    z := 2 * y
    
    • 如果 y := 10,常数 10 也可以传播下去,把最后一行替换成 z:= 2 * 10,这叫做常数传播。再做一次常数折叠,就变成 z:=20 了。

    死代码删除(Ded code elimintation)

    • 在上面的拷贝传播中,如果没有其他地方使用 y 变量了,那么第二行就是死代码,就可以删除掉,这种优化叫做死代码删除。

    一个优化可能导致另一个优化,比如,拷贝传播导致 y 不再被使用,我们又可以进行死代码删除的优化。所以,一般进行多次优化、多次扫描。

    数据流分析

    基于 CFG 做优化分析的方法框架,就叫做数据流分析

    实例图示

    • 在做全局优化时,情况就要复杂一些:代码不是在一个基本块里简单地顺序执行,而可能经过控制流图(CFG)中的多条路径。我们来看一个例子(例子由 if 语句形成了两条分支语句):
      在这里插入图片描述

    基于这个 CFG,我们可以做全局的活跃性分析。从最底下的基本块开始,倒着向前计算活跃变量的集合(也就是从基本块 5 倒着向基本块 1 计算)。

    • 需要注意,对基本块 1 进行计算的时候,它的输入是基本块 2 的输出,也就是{a, b,c},和基本块 3 的输出,也就是{a, c},计算结果是这两个集合的并集{a, b, c}。也就是说,基本块 1 的后序基本块,有可能用到这三个变量。这里就是与本地优化不同的地方,我们要基于多条路径来计算。
      在这里插入图片描述
    • 基于这个分析图,我们马上发现 y 变量可以被删掉(因为它前面的活变量集合{a}不包括y,也就是不被后面的代码所使用),并且影响到了活跃变量的集合。
      在这里插入图片描述
    • 删掉 y 变量以后,再继续优化一轮,会发现 d 也可以删掉。
      在这里插入图片描述
    • d 删掉以后,2 号基本块里面已经没有代码了,也可以被删掉,最后的 CFG 是下面这样:
      在这里插入图片描述
    • 到目前为止,我们发现:全局优化总体来说跟本地优化很相似,唯一的不同,就是要基于多个分支计算集合的内容(也就是 V 值)。在进入基本块 1 时,2 和 3 两个分支相遇(meet),我们取了 2 和 3V 值的并集。这就是数据流分析的基本特征

    半格理论

    • 首先,半格是一种偏序集。偏序集就是集合中只有部分成员能够互相比较大小。举例来说会比较直观。在做全局活跃性分析的时候,{a, b, c}和{a, c}相遇,产生的新值是{a, b, c}。我们形式化地写成{a, b, c} Λ {a, c} = {a, b, c}。这时候我们说{a, b, c}是可以跟{a, c}比较大小的。那么哪个大哪个小呢?

      • 如果 XΛY=X,我们说 X<=Y。
    • 所以,{a, b, c}是比较小的,{a, c}是比较大的。

    • 当然,{a, b, c}也可以跟{a, b}比较大小,但它没有办法跟{c, d}比较大小。所以把包含了{{a,b, c}、{a, c}、{a, b}、{c, d}…}这样的一个集合,叫做偏序集,它们中只有部分成员之间可以比较大小。哪些成员可以比较呢?就是下面的半格图中,可以通过有方向的线连起来的。

    • 半格可以画成图形,理解起来更直观,假设我们的程序只有 a, b, c 三个变量,那么这个半格画成图形是这样的:
      在这里插入图片描述

    • 沿着上面图中的线,两个值是可以比较大小的,按箭头的方向依次减少:{}>{a}>{a, b}> {a,b, c}。如果两个值之间没有一条路径,那么它们之间就是不能比较大小的,就像{a}和{b}就不能比较大小。

    • 对于这个半格,我们把{}(空集)叫做 Top,Top 大于所有的其他的值。而{a, b, c}叫做Bottom,它是最小的值。

      • 如果一个偏序集中,任意两个元素都有最大下界,那么这个偏序集就叫做交半格(MeetSemilattice)。
      • 与此相对应的,如果集合中的每个元素都有最小上界(Least Upper Bound),那么这个偏序集叫做并半格(Join Semilattice)。
      • 如果一个偏序集既是交半格,又是并半格,我们说这个偏序集是一个格,示例的这个偏序集就是一个格。

    你知道的越多,你不知道的越多。
    有道无术,术尚可求,有术无道,止于术。
    如有其它问题,欢迎大家留言,我们一起讨论,一起学习,一起进步

    展开全文
  • 东北大学编译原理实验报告,用编译语言实现目标代码优化,有详细的代码
  • 一、常用的代码优化方法 优化的分类: 机器无关优化 :针对中间代码 机器相关优化 :针对目标代码 局部代码优化 :单个基本块范围内的优化 全局代码优化 :面向多项基本块的优化 常用的优化方法: 删除公共子...
  • #include #include #include #include using namespace std; #define dd(x) cout #define de(x) cout //词法分析双向链表(存已识别的词单元(endSign)) typedef struct WordAnalysisList ... struct WordAnalysisList *...
  • 编制程序,完成局部优化过程中的基本块划分。给定一段代码,判定程序的入口语句,划分基本块,删除无用产生式和冗余节点。
  • 基本块构造DAG的算法 for (i=0;i;i++) /*QlistLenth 之值为基本块中四元式的个数*/ {  取出第i四元式Qi; if (NODE(B)==NULL) {  建立一个以B为标记的叶结点,其编号为NODE (B);
  • 编译原理(8):代码优化

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

    千次阅读 2019-06-20 14:17:55
    文章目录一、优化主要为两类:二、常用优化方式三、局部优化1. 求出程序中可做基本块入口的语句,它们是:2. 对以上入口语句,构造其所属的基本块:3. 删除未被纳入任何基本块的语句。四、基本块的DAG表示及其应用1....
  • 编译原理:第11章 代码优化.pdf
  • N - DAG优化编译原理

    千次阅读 2020-12-07 19:32:31
    大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。 Input 输入第一行为一个整数n(n < 100),表示该组输入的表达式的个数 之后n行为表达式,每个变量为一个字母,表达式仅包括二元运算 + -...
  • 编译原理过程简述及中间代码优化

    千次阅读 2017-09-28 17:21:23
    一、编译过程图示如下:词法分析作用:找出单词 。...二、中间代码优化所谓代码优化是指对程序代码进行等价(指不改变程序的运行结果)变换。程序代码可以是中间代码(如四元式代码),也可以是目标代码。
  • 代码优化 代码优化可分为与机器有关的优化和与机器无关的优化。 与机器有关的优化一般在目标代码上进行。与机器无关的优化一般在中间代码上进行。 代码优化也可分为局部优化、 循环优化和全局优化: ...
  • 对于一个给定的程序,我们可以把它划分为一系列的基本块。...局限于基本块范围内的优化称为基本块内的优化,或者称为局部优化。所谓基本块,是指程序中一个顺序执行的语句序列,其中只有一个入口和一个出口。 ...
  • 编译原理实验六—代码优化

    千次阅读 2017-05-26 23:00:26
    1. 通过上机实习,加深对代码优化的理解,掌握基本块优化、循环优化的方法。  2. 掌握利用 DAG 进行基本块优化的技术。  坑....闷头写了两天总算模拟出了个能跑得起来的差不多的代码,里面还有很多地方可以...
  • 代码生成器。它依次把每条中间代码变换成目标代码,并且在一个基本块范围内考虑如何充分利用寄存器的问题。 代码生成器。它依次把每条中间代码变换成目标代码,并且在一个基本块范围内考虑如何充分利用寄存器的问题...
  • 编译原理实验源码.zip

    2020-12-07 21:15:23
    华中科技大学编译原理实验源码一到四,运行makefile文件即可,不过电脑应该先安装c编译器。 实验一:词法语法分析器的设计与实现; 实验二:符号表管和语义检查; 实验三:中间代码生成和优化; 实验四:目标代码...
  • 上海大学2013年编译原理实验报告 附代码
  • 代码优化_1 1 优化可生成()的目标代码。 A. 运行时间较短 B. 占用存储空间较小 C. 运行时间短但占用内存空间大 D. 运行时间短且占用存储空间小 2 基本块内的优化为 ( )。 A. 代码外提,删除归纳变量 B. 删除多余...
  • 这是我收集的哈工大的编译原理这门课程的课件,很基础。适合想学习编译原理的同学。
  • 编译原理】中间代码优化(三) 循环优化

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

    2013-03-14 15:52:21
    编译原理的课设,DAG的优化,内有源代码
  • 这个是我们上课老师给我们用的PPT,有了这个我们可以考试过关的啊。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 163,534
精华内容 65,413
关键字:

编译原理代码优化