编译原理与技术之代码优化.ppt

《编译原理与技术之代码优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、代码优化9/17/20211《编译原理与技术》之代码优化代码优化的目标提高最终目标代码的运行效率（性能）－时间：运行的更快－空间：降低内存需求保持源程序的语义9/17/20212《编译原理与技术》之代码优化代码优化（续）－全局数据流分析技术9/17/20213《编译原理与技术》之代码优化全局数据流分析基本块IN[B]OUT[B]KILL[B]GEN[B]到达基本块入口处的相关数据流信息到达基本块出口处的相关数据流信息基本块“产生”的相关数据流信息基本块“注销”的相关数据流信息9/17/20214《编译原理与技术》之代码优化

2、全局数据流分析数据流的“方向”－正向（向前）数据流：与控制流方向一致－OUT[B]由IN[B]来计算－IN[B]则由B的所有前驱结点的OUT来决定控制流数据流前驱1前驱2基本块B表示数据流信息交汇（合流）处9/17/20215《编译原理与技术》之代码优化全局数据流分析数据流的“方向”－反向（向后）数据流：与控制流方向相逆－IN[B]由OUT[B]来计算－OUT[B]则由B的所有后继结点的IN来决定控制流数据流基本块B后继1后继2表示数据流信息交汇（合流）处9/17/20216《编译原理与技术》之代码优化全局数据流分析向前流

3、向后流任意路径OUT[B]=GEN[B]∪(IN[B]-KILL[B])IN[B]=∪OUT[P],P∈Pred(B)IN[B]=GEN[B]∪(OUT[B]-KILL[B])OUT[B]=∪IN[S],S∈Succ(B)全路径OUT[B]=GEN[B]∪(IN[B]-KILL[B])IN[B]=∩OUT[P],P∈Pred(B)IN[B]=GEN[B]∪(OUT[B]-KILL[B])OUT[B]=∩IN[S],S∈Succ(B)表1.数据流分析方程9/17/20217《编译原理与技术》之代码优化全局数据流方程求解迭代计

4、算：直至某先后两次迭代计算结果一样迭代次序－向前流：流图深度优先次序－向后流：流图深度优先次序的逆序－流图深度优先次序：－对流图进行深度优先遍历，得到流图深度优先扩展树；对该树进行前序遍历时最后访问结点的逆序迭代初始计算（值）9/17/20218《编译原理与技术》之代码优化12345678910e.g.一个流图12346781095e.g.深度优先扩展树前序遍历：1->2->3->4->6->7->8->10->8->9->8->7->6->4->5->4->3->2->1深度优先次序：1，2，3，4，5，6，7，8，9，

5、109/17/20219《编译原理与技术》之代码优化全局数据流方程求解向前流向后流问题初始值问题初始值任意路径到达-定值/ud链∅活跃变量∅未初始化变量所有变量du链∅全路径可用表达式∅非常忙表达式∅复写传播∅表2.常用的数据流分析9/17/202110《编译原理与技术》之代码优化到达－定值数据流分析定值与引用d:x:=y+z//语句d是变量x的一个定值点u:w:=x+v//语句u是变量x的一个引用点变量x在d点的定值到达u点流图中有路径d---->u，且该路径上没有x的其它（无二义）定值。9/17/202111《编译原理

6、与技术》之代码优化到达－定值数据流分析解决的问题－定值“传播”数据流归属－任意路径、向前流的数据流分析－IN[B]，到达基本块入口处定值集合－OUT[B]，到达基本块出口处定值集合－GEN[B]，基本块产生且能到达基本块出口的定值集合－KILL[B]，由基本块注销的定值集合（这些定值不能传播或到达到块出口）数据流应用－ud链，即引用－定值链。可以据此判断基本块内的某变量引用，其值来自何方（定值）。如应用于循环不变式的寻找。9/17/202112《编译原理与技术》之代码优化OUT:dm:x:=…OUT:dn:x:=…前驱1前

7、驱2…ds:s:=…x……dt:x:=……du:x:=……IN[B]OUT[B]=?控制流9/17/202113《编译原理与技术》之代码优化OUT:dm:x:=…OUT:dn:x:=…前驱1前驱2…ds:s:=…x……dt:x:=……du:x:=……IN[B]OUT[B]=?英雄惜英雄，dm和dn相会在汇流点，共赴IN[B]9/17/202114《编译原理与技术》之代码优化OUT:dm:x:=…OUT:dn:x:=…前驱1前驱2…ds:s:=…x……dt:x:=……du:x:=……IN[B]OUT[B]=?dm和dn：一路

8、无险遇ds9/17/202115《编译原理与技术》之代码优化OUT:dm:x:=…OUT:dn:x:=…前驱1前驱2…ds:s:=…x……dt:x:=……du:x:=……IN[B]OUT[B]=?dm和dn：再走一程见dt，^_^9/17/202116《编译原理与技术》之代码优化OUT:dm:x:=…O