《编译原理》课程教学资源（PPT课件讲稿）代码优化——全局数据流分析技术

C代码优化

代码优化

代码优化的目标 ■提高最终目标代码的运行效率(性能) 时间:运行的更快 空间:降低内存需求 保持源程序的语义

•代码优化的目标  提高最终目标代码的运行效率（性能） － 时间：运行的更快 － 空间：降低内存需求 • 保持源程序的语义

代码优化(续) 全局数据流分析技术 2021/2/11 《编译原理与技术》之代码优化 3

2021/2/11 《编译原理与技术》之代码优化 3 代码优化（续） － 全局数据流分析技术

全局数据流分析 到达基本块入口处 的相关数据流信息 IN[B] 基本块“产生” 的相关数据流信 GENB 基本块“注销” 的相关数据流信 KILLIBI 息 到达基本块出口 基本块 处的相关数据流 信息 OUT[B 2021/2/11 《编译原理与技术》之代码优化 4

2021/2/11 《编译原理与技术》之代码优化 4 •全局数据流分析 基本块 IN[B] OUT[B] KILL[B] GEN[B] 到达基本块入口处 的相关数据流信息 到达基本块出口 处的相关数据流 信息 基本块“产生” 的相关数据流信 息 基本块“注销” 的相关数据流信 息

全局数据流分析 ■数据流的“方向” 正向(向前)数据流:与控制流方向一致 前驱1 前驱2 OUT[B]由N[B]来计算 NB]则由B的所有前驱结 点的OUT来决定 基本块B 表示数据流信息交汇(合流)处 —→控制流 2021/2/11 数握 理与技术》之代码优化 5

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

全局数据流分析 ■数据流的“方向” 反向(向后)数据流:与控制流方向相逆 ↓↓ NB]由OUT[B]来计算 基本块B OUT[B]则由B的所有后继结 点的N来决定 表示数据流信息交汇(合流)处 后继1 后继2 —→控制流 2021/2/11 数握 理与技术》之代码优化 6

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

全局数据流分析 向前流 向后流 OUT[B]= GEN[B] U(INBI-KILLIBI) B]= GEN[B] U(OUT[BI-KILL[BD) 任意 路径NB= UOUTIPI, PEEred OUT[B]= U INS, SE Succ(B) OUTB=GENB]∪( NB]KILL[B)NB]=GENB]∪( OUT[BKILL[B 全路径 INB]=∩oUTP],P∈Pred(B) OUTB]=∩NS],S∈succ(B) 表1.数据流分析方程 2021/2/11 《编译原理与技术》之代码优化 7

2021/2/11 《编译原理与技术》之代码优化 7 •全局数据流分析 向前流 向后流 任意 路径 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. 数据流分析方程

仝局数据流方程求解 迭代计算:直至某先后两次迭代计算结果一样 迭代次序 向前流:流图深度优先次序 向后流:流图深度优先次序的逆序 流图深度优先次序: 对流图进行深度优先遍历,得到流图深度 优先扩展树;对该树进行前序遍历时最后 访问结点的逆序 迭代初始计算(值) 2021/2/11 《编译原理与技术》之代码优化 8

2021/2/11 《编译原理与技术》之代码优化 8 •全局数据流方程求解  迭代计算：直至某先后两次迭代计算结果一样  迭代次序 － 向前流：流图深度优先次序 － 向后流：流图深度优先次序的逆序 － 流图深度优先次序： － 对流图进行深度优先遍历，得到流图深度 优先扩展树；对该树进行前序遍历时最后 访问结点的逆序  迭代初始计算（值）

3 4 5 8 8 10 eg深度优先扩 展树 eg.一个流图 前序遍历: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,10 2021/2/11 《编译原理与技术》之代码优化 9

2021/2/11 《编译原理与技术》之代码优化 9 1 2 3 4 5 6 7 8 9 10 e.g. 一个流图 1 2 3 4 6 7 8 10 9 5 e.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，10

全局数据流方程求解 向前流 向后流 问题 初始值 问题 初始值 任意到达定值/链 活跃变量 路径未初始化变量所有变量 du链 全路可用表达式 0非常忙表达式0 径 复写传播 表2.常用的数据流分析 2021/2/11 《编译原理与技术》之代码优化 10

2021/2/11 《编译原理与技术》之代码优化 10 •全局数据流方程求解 向前流 向后流 问题 初始值 问题 初始值 任意 路径 到达-定值/ud链 ∅ 活跃变量 ∅ 未初始化变量 所有变量 du链 ∅ 全路 径 可用表达式 ∅ 非常忙表达式 ∅ 复写传播 ∅ 表2. 常用的数据流分析