复制传播 形如u=)的复制语句使得语句后 a dte b=dte 面的程序点上，u的值等于v的值 如果在某个位置上u一定等于)，那 c=dte 么可以把u替换为) a) 有时可以彻底消除对的使用，从 d+e t dte a t b=t 而消除对u的赋值语句 右图所示，消除公共子表达式时 t 引入了复制语句 b) 如果尽可能用t来替换c,可能就 不需要C=t这个语句了 11
复制传播 • 形如u = v的复制语句使得语句后 面的程序点上，u的值等于v的值 – 如果在某个位置上u一定等于v，那 么可以把u替换为v – 有时可以彻底消除对u的使用，从 而消除对u的赋值语句 • 右图所示，消除公共子表达式时 引入了复制语句 • 如果尽可能用t来替换c，可能就 不需要c = t这个语句了 11 南大编译许畅
复制传播的例子 右图显示了对B5进行复制传播处理的情况 可能消除所有对x的使用 t3 B5 a[t2】 t5 a[t4] goto B2 南大 x =t3 a[t2]= t5 a[t4]= ®3 goto B2 12
复制传播的例子 • 右图显示了对B5进行复制传播处理的情况 – 可能消除所有对x的使用 12 南大编译许畅
死代码消除 如果一个变量在某个程序点上的值可能会在之后 被使用，那么这个变量在这个点上活跃的；否则 这个变量就是死的，此时对该变量的赋值就是没 有用的死代码 死代码多半是因为前面的优化而形成的 比如，B5中的x=3就是死代码 ·消除后得到 X=3 a[t2]=t5 a[t2]=t5 a[t4]=t3 a[t4]=t3 goto B2 goto B2 13
死代码消除 • 如果一个变量在某个程序点上的值可能会在之后 被使用，那么这个变量在这个点上活跃的；否则 这个变量就是死的，此时对该变量的赋值就是没 有用的死代码 • 死代码多半是因为前面的优化而形成的 • 比如，B5中的x = t3就是死代码 • 消除后得到 13 a[t2] = t5 a[t4] = t3 goto B2 x = t3 a[t2] = t5 a[t4] = t3 goto B2 南大编译许畅 ➔
代码移动 ·循环中的代码会被执行很多次 循环不变表达式：循环的同一次运行的不同迭代中， 表达式的值不变 把循环不变表达式移动到循环入口之前计算可以 提高效率 循环入口：进入循环的跳转都以这个入口为目标 while (i<=limit-2)... 如果循环体不改变limit的值，可在循环外计算limit-2 t=limit-2 while (i<=t)... 14
代码移动 • 循环中的代码会被执行很多次 – 循环不变表达式：循环的同一次运行的不同迭代中， 表达式的值不变 • 把循环不变表达式移动到循环入口之前计算可以 提高效率 – 循环入口：进入循环的跳转都以这个入口为目标 • while (i <= limit – 2) … – 如果循环体不改变limit的值，可在循环外计算limit – 2 t = limit – 2 while (i <= t) … 14 南大编译许畅
归纳变量和强度消减 归纳变量 =m-1 B j=n t1=4*n 每次对x赋值都使x增加c v =a[t1] :t4=4*1 把赋值改为增量操作， 1=i+1 可消减计算强度 B2 t2=4*i t3=a[t2] if t t3<v goto B2 两个归纳变量步调一致， 可删除一个 j=j-1 B3 t4=t4-4 例子 t5 a[t4] if t5>v goto B3 循环开始保持t4=4*j if i>=j goto B6 BA j=j-1后面的t4=4*j每 次赋值使t4减4 x t3 x t3 B6 可替换为t4=4-4 a[t2】=t5 t14=a[t1] a[t4】=x a[t2]=t14 goto B2 a[t1]x 2也可同样处理 图9-8 对基本块B,中的4*j应用强度消减优化15
归纳变量和强度消减 • 归纳变量 – 每次对x赋值都使x增加c – 把赋值改为增量操作， 可消减计算强度 – 两个归纳变量步调一致， 可删除一个 – 例子• 循环开始保持t4 = 4 * j • j = j – 1后面的t4 = 4 * j 每 次赋值使t4 减 4 • 可替换为t4 = t4 – 4 • t2也可同样处理 15 南大编译许畅