学习编译原理ch09-optimization

1、例 基本块划分和流图:第9章代码优化与目标代码生成2代码优化与目标代码生成码优化 代码优化代与码目优标化代码生成在编译程序中的位置词法分析词法分析词法分析从中间表示获取的流图字 字符符流语流法分析语法分析语法分析改进的流图单词流单词流单词流 语义分析和中间代码生成指令调度指令指调令度调度寄存器分配语法分析树机器无关的代码优化窥孔优化窥孔窥优孔化优化中间表示中间表示中间表示目标代码生成优化的中间表示针对机器的代码优化目标代码目标代码目标代码优化的目标代码3代码优化与目标代码生成 (2)代码优化的任务通过 通过通等过价的程序变获换得, 获得获执得行速度快占、用占用占用空间少空的间间程少少序空的间程

2、少序的程序代码生成的任务针目对标 针语对言针目的对标特语殊言性目的标特语殊言性,机器相码关(机器相关机) 器相关4不同阶段的优化法优化 算法优化算法优化有效的数 有据效结的构有数效据的结构算领数和法域据算问结法题构算(领法域问题领) 域问题译优化 编译优化编译优化中间代码 中间代优机码化器中优无间化关代优: 机码化器无关机器无关常数合如并: 常数合并常、数公合共并子表达式删除目标代码 目标代优机码化器目优相标化关代优: 机码化器相关机器相关特殊指如令: 特殊特指殊令结特、构殊特指殊令结构特殊结构5中间代码优化部优化 局部优化局部优化基本块 基括各种转移控制)局优化 全局优化全局优化循环优化 循

3、环优化循、环控优制化流分析与化简、数据流分析8控制流图的构造基本 以块基本块结基为点本结控块点制结, 以流点控制有流流向控为边制有流向边有向边流图 流图流(fl图ow graph)G N, E, n0 基本块N集: 基本块集基本块集初始结n0点: 初始结点初始含结首点语句的基本块E : 有向边集合 A BA 的出口为转移语转句向, 转的向的的紧 跟B 紧跟之紧后A跟之后之, 且且且后A 的出口不是 goto 或或或 return69.1 基本块和流图基本块 基本块基本块(1) i := m - 1控制流 控制只流能控只制能流只从能第一语句进(2) j := n入入、从最后一条语句离开(3) t

4、1 := 4 * n;(4) v := a t1 最的的长最长最的长指令序列(5) i := i + 1语句序列中间没有停止或(6) t2 := 4 * i;分支分支分支(7) t3 := a t2 ;关键 关键关: 确键定每个基本块的(8) if t3 v goto (9)7基本块的划分三地址语句基序本列块表基本块表基本块表(1) i := m - 1定义语句(2) j := n代码序列的第一语句(3) t1 := 4 * n; (4) v := a t1 转移语句的目标语句(5) i := i + 1转移语句的下一条语句(6) t2 := 4 * i;基本块 基本块基本块(7) t3 :=

5、 a t2 ;一语句到下一语句(8) if t3 v goto (9)9 10三地址序列 11程序流图129.2 局部优化合并已知量常数表达式计算重新命名临时变量t1 代替 t2, t4, t6, t7, t10, t11, t12, t15、t3 代替 t5, t8, t13删除公共子表达式公共子表达式表达式E在某次出现之前已经被计算过, 且E变量的值从那次计算到本次出现一直未被改变过(14)(16)、(17)(20)、(23)(25)、(26)(29)13局部优化 (2)删除死代码未出现在程序流图中的代码赋值未的指令交换语句次序对相互独立的语句进行重新排序, 可以降低一个临时值需要保持在寄

6、存器中的时间149.3 循环优化循环体是优化的重点反复执行循环的定义有唯一点的强连通子图强连通子图任意两结点间的通各结点属于子图15方法 1: 代码外提将循环不变运算移到循环外例i = 0;while( i = 76 goto (7)令种类 指令种类指令种类(4) x : = x + 4赋值 赋值赋M值OV(5) y : = t1 + x比较 比较比C较MP条件转移 条件转移条J件LE转移(6) goto (3)转移 转移转J移MP累加 累加累A加DD24生成目标代码三地址代码:(1) MOV R0, Z(1) t1 : = z * 6(2) ADD R0, 6(2) x : = -4(3) MOV R3, R0(3) if x = 76 goto (7)(4) MOV R2, -4(4) x : = x + 4(5) CMP R2, 76(5) y : = t1 + x(6) JGE (12)(6) goto (3)(7) ADD R2, 4一般寄存