死代码消除 ·如果一个变量在某个程序点上的值可能会在之后 被使用,那么这个变量在这个点上活跃;否则这 个变量就是死的,此时对这个变量的赋值就是没 有用的死代码; 死代码多半是因为前面的优化而形成的; ·比如,B中的=3就是死代码 ·消除后得到 Xt3 a[t2]=t5 a[t2]=t5 [4]=t3 goto B2 coto b
死代码消除 • 如果一个变量在某个程序点上的值可能会在之后 被使用，那么这个变量在这个点上活跃；否则这 个变量就是死的，此时对这个变量的赋值就是没 有用的死代码； • 死代码多半是因为前面的优化而形成的； • 比如，B5中的x=t3就是死代码； • 消除后得到 a[t2] = t5 a[t4] = t3 goto B2 x=t3 a[t2] = t5 a[t4] = t3 goto B2 ==>
代码移动 ·循环中的代码会被执行很多次 ·循环不变表达式:循环的同一次运行的不同迭代 中,表达式的值不变 ·把循环不变表达式移动到循环入口之前讣算可以 提高效率 循环入口:进入循环的跳转都以这个入口为目 标 while(i<= limit-2) 如果循环体不改变 limit的值,可以在循环外讣算lmit-2 t=limit-2 while(is-t
代码移动 • 循环中的代码会被执行很多次 • 循环不变表达式：循环的同一次运行的不同迭代 中，表达式的值不变 • 把循环不变表达式移动到循环入口之前计算可以 提高效率 – 循环入口：进入循环的跳转都以这个入口为目 标 • while(i <= limit-2) … – 如果循环体不改变limit的值，可以在循环外计算limit - 2 t=limit-2 while(i<= t) …
归纳变量和强度消减 归纳变量 =m-1 每次对x的赋值都使得X的 t1=4*n 值增加c,那么ⅹ就是归纳 v= a[tl 变量 t4=4*j 把对ⅹ的赋值改成增量操 作,可消减计算强度,提 i=i+1 t2=4*i 高效率; t3= a[t2] if t3<v goto B 如果两个归纳变量步调· 致,还可以删除其中的某 个 B t4=t4-4 t5= a[t4] 例子 if t5>v goto B3 如果在循环开始时刻保持 4=4 f i>=] goto B 那么 1后面的t4=4 每次赋值使得t4减4 x= t3 替换为t4=t4-4: a[t2]=t5 t14 a[tll t2也可以同样处理 goto a[tl)=x 图98对基本块B3中的4*j应用强度消减优化
归纳变量和强度消减 • 归纳变量 – 每次对x的赋值都使得x的 值增加c，那么x就是归纳 变量； – 把对x的赋值改成增量操 作，可消减计算强度，提 高效率； – 如果两个归纳变量步调一 致，还可以删除其中的某 一个； • 例子 – 如果在循环开始时刻保持 t4=4*j – 那么，j=j-1后面的t4=4*j 每次赋值使得t4减4 – 替换为t4 = t4 – 4; – t2也可以同样处理
继续优化 t1=4 对t2强度消减 t4=4 B4中对和的测 t2=t2+4 t3=a[t2] 试可以替换为 if t3<v goto B 对t2t4的测试 t5 t4] if t5>v goto B t24· if t2>t4 goto B goto n t5>v goto f a[t2]=t5 t14=a[t1 a[ t4 ]=t3B a[t2]=t14|B it i>) soto.8. goto B a[t1]=t3 图9-9归纳变量消除之后的流图 图98对基本块B中的4应用强度消减优化
继续优化 • 对t2强度消减 • B4中对i和j的测 试可以替换为 对t2,t4的测试
数据流分析 数据流分析 用于获取数据着程序执行路径流动的信息的 相关技术。 是优化的基础 例如 两个表达式是否一定计算得到相同的值?(公 共子表达式) 一个语句的计算结果有没有可能被后续语句使 用?(死代码消除)
数据流分析 • 数据流分析 – 用于获取数据沿着程序执行路径流动的信息的 相关技术。 – 是优化的基础 • 例如 – 两个表达式是否一定计算得到相同的值？（公 共子表达式） – 一个语句的计算结果有没有可能被后续语句使 用？（死代码消除）