编译方法、技术与实践 课件 第六章 中间代码优化.pdf

第六章中间代码优化

提纲

◼数据流分析理论与框架

◼到达定值分析

◼可用表达式分析

◼活跃变量分析

◼局部优化/全局优化

引言

◼代码优化

在目标代码中消除不必要的指令

把一个指令序列替换为一个完成相同功能的

更快的指令序列

◼全局优化

◼基于数据流分析技术

用以收集程序相关信息的算法

优化的主要来源

◼编译器只能通过一些相对低层的语义等价转换来

优化代码

◼冗余运算的原因

源程序中的冗余

高级程序设计语言编程的副产品

◼比如A[i][j].f=0;A[i][j].k=1;中的冗余运算

◼语义不变的优化

公共子表达式消除

复制传播

死代码消除

常量折叠

优化的主要来源

语义功能一致的不同改写策略

自动化重构技术：

重写规则：

(1)with上下文管理器重写规则;

(2)推导表达式重写规则;

(3)lambda表达式重写规则;

(4)yieldfrom重写规则;

(5)map、reduce、filter、sorted重写规则;

(6)装饰器重写规则等;

拟实现方法：

•源码静态分析，生成AST树

•对AST树进行规则匹配，并完成相应替换

实现机制不同

优化的例子（1）

◼快速排序算法

优化的例子（2）

◼三地址代码

Quicksort的流图

◼循环：

B

2

B

3

B、B、B、

234

B

5

数据流分析

◼数据流分析

用于获取数据沿着程序执行路径流动的信息

的相关技术

是优化的基础

◼例如

两个表达式是否一定计算得到相同的值？

（公共子表达式）

一个语句的计算结果有没有可能被后续语句

使用？（死代码消除）

数据流抽象（1）

◼程序点

三地址语句之前或之后的位置

基本块内部：一个语句之后的程序点等于下一

个语句之前的程序点

如果流图中有B到B的边，那么B的第一个语

122

句之前的点可能紧跟在B的最后语句之后的点

1