第九章独立于机器的优化

第九章独立于机器的优化内容摘要：

} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 000 0000 B3 000 0000 B4 000 0000 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 000 0000 B4 000 0000 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 0000 B4 000 0000 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 000 0000 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 001 1110 000 0000 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0111 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1100 000 1110 B4 001 1110 001 0111 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1110 000 1110 B4 001 1110 001 0111 不再继续演示迭代计算 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 • 到达 定值数据流等式是 正向 的方程 OUT [B] = gen [B]  (IN [B]  kill [B]) IN [B] = P是 B的前驱 OUT [P] 某些数据流等式是 反向 的 • 到达 定值数据流等式的合流运算是求并集 IN [B] = P是 B的前驱 OUT [P] 某些数据流等式的合流运算是求交集 • 对到达 定值数据流方程，迭代求它的最小解 某些数据流方程可能需要求最大解 数据流分析介绍 数据流分析模式 • 数据流值 – 数据流分析总把程序点和数据流值联系起来 – 数据流值代表在程序点能观测到的所有可能程序状态集合的一个抽象 – 语句 s前后两点数据流值用 IN[s]和 OUT[s]来表示 – 数据流问题就是通过 基于语句语义的约束 （迁移函数）和 基于控制流的约束 来寻找所有语句 s的IN[s]和 OUT[s] 的一个解 数据流分析介绍 数据流分析模式 • 迁移函数 f – 语句前后两点的数据流值受该语句的语义约束 – 若 沿执行路径正向传播，则 OUT[s] = fs(IN[s]) – 若沿执行路径逆向传播，则 IN[s] = fs(OUT[s]) 若基本块 B由语句 s1, s2, …, sn依次组成，则 – IN[si+1] = OUT[si], i = 1, 2, …, n1（逆向 … ） – fB = fn  . . .  f2  f1 (逆向 fB = f1  . . .  fn 1  fn ) – OUT[B] = fB (IN[B]) (逆向 IN[B] = fB (OUT[B]) ) 数据流分析介绍 数据流分析模式 • 控制流约束 – 正向传播 IN[B] =  P是 B的前驱 OUT[P]（可能用 ） – 逆向传播 OUT[B] =  S是 B的后继 IN[S] （可能用 ） • 约束方程组的解通常不是唯一的 – 求解的目标是要找到满足这两组约束（控制流约束和迁移约束）的最 “ 精确 ” 解 数据流分析介绍 活跃变量 • 定义 – x的值在 p点开始的某条执行路径上被引用，则说x在 p点活跃，否则称 x在 p点已经死亡 – IN[B]： 块 B开始点的活跃变量集合 – OUT[B]： 块 B结束点的活跃变量集合 – useB： 块 B中有引用且在引用前无定值的变量集 – defB： 块 B中有定值的变量集 • 应用 – 一种重要应用就是基本块的寄存器分配 数据流分析介绍 活跃变量 • 例 – use[B2] = { i, j } – def[B2] = { i, j } d1: i = m 1 d2: j = n d3: a = u1 B1 B2 d7: i = u3 B4 d4: i = i + 1 d5: j = j  1 d6: a = u2 B3 数据流分析介绍 活跃变量 • 活跃变量数据流等式 – IN [B] = useB  (OUT [B]  defB ) – OUT[B] =  S是 B。