第九章机器无关的优化 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版
许畅 南京大学计算机系 2022年春季 第九章 机器无关的优化 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅
主要内容 引言 ·优化的来源 ·数据流分析 许畅 。 部分冗余消除 0 循环的识别、分析和优化 2
主要内容 • 引言 • 优化的来源 • 数据流分析 • 部分冗余消除 • 循环的识别、分析和优化 2 南大编译许畅
引言 。代码优化或者代码改进 在目标代码中消除不必要的指令 把一个指令序列替换为一个完成相同功能的更快的指 令序列 。全局优化 具体的优化实现基于数据流分析技术 用以收集程序相关信息的算法 3
引言 • 代码优化或者代码改进 – 在目标代码中消除不必要的指令 – 把一个指令序列替换为一个完成相同功能的更快的指 令序列 • 全局优化 – 具体的优化实现基于数据流分析技术 – 用以收集程序相关信息的算法 3 南大编译许畅
优化的主要来源 编译器只能通过一些相对低层的语义等价转换来 优化代码 冗余运算的原因 源程序中的冗余 高级程序设计语言编程的副产品，如A[][].f=0;A[][1k=1; 语义不变的优化 公共子表达式消除 。 复制传播 死代码消除 常量折叠 4
优化的主要来源 • 编译器只能通过一些相对低层的语义等价转换来 优化代码 – 冗余运算的原因 • 源程序中的冗余 • 高级程序设计语言编程的副产品，如A[i][j].f = 0; A[i][j].k = 1; – 语义不变的优化 • 公共子表达式消除 • 复制传播 • 死代码消除 • 常量折叠 4 南大编译许畅
优化的例子(1) 快速排序算法 void quicksort(int m,int n) /*递归地对a[m]和a[n]之间的元素排序*/ { int i,j; int v,x; if (n <m)return; /*片断由此开始*/ i =m-1;j=n;v a[n] while (1){ do i=i+1;while (a[i]<v); do j=j-1;while (a[j]v); if (i>=j)break; x=a[i];a[i]=a[j门；a[j]=x;/*对换a[i]和a[j门*/ x=a[i];a[i]=a[n];a[n]=x;/*对换a[i]和a[n]*/ /*片断在此结束*/ quicksort(m,j);quicksort(i+1,n); 5
优化的例子 (1) • 快速排序算法 5 南大编译许畅