机器无关的优化

引言

  • 代码优化或代码改进
    • 消除不必要
    • 替换为更快的同功能指令
  • 全局优化
    • 具体的优化实现基于数据流分析计数
    • 用以收集程序相关信息的算法

优化的来源

  • 编译器只能通过一些相对底层的语义等价转换来优化代码
    • 冗余的原因
      • 源程序中的冗余
      • 高级语言的副产品
    • 语义不变的优化
      • 公共子表达式的消除0
      • 复制传播
      • 死代码消除
      • 常量折叠
    • 全局公共子表达式
      • 表达式E
        • 如果某次出现之前必然被计算过
        • 且E的运算分量在该计算之后没有被改变
        • 那么E的本次出现就是一个公共子表达式
      • 如果上次E赋值给了x, 且x的值没有被修改过, 则可以使用x而不是计算E
    • 复制传播
      • 形如u=v的复制语句, 使得之后的程序点上, u的值等于v的值
        • 如果某点一定相等, 则u课替换为v
        • 有时可以彻底消除对u的引用
      • 尽可能用v替代u, 可能就用不着这个
    • 死代码消除
      • 如果某个变量的值算出来后, 有被使用, 则是活跃的, 反之是死的
      • 死代码多半是因为先前的优化产生的
    • 代码移动
      • 循环中的代码会被执行很多次
        • 循环不变表达式: 循环的同一次运行的不哦她那个迭代中, 表达式的值不改变
        • 移到入口计算, 能提高效率
    • 归纳变量和强度消减
      • 归纳变量
        • 每次对x赋值都使x增加c, 则把赋值改成增量操作, 可以减少开销
        • 两个变量步调一致, 可删除一个

          数据流分析

  • 数据流分析
    • 用于获取数据沿着程序执行路径, 流动信息的相关技术
    • 是优化的基础
  • 数据流抽象
    • 程序点: 三地址语句之前或之后的位置
      • 基本块内部: 一个语句之后的程序点, 等于下一个语句之前的程序点
      • 如果流图中有B1到B2的边, 那么B2的第一个语句执行之前的点, 可能紧跟在B1的最后语句之后的点后面执行
    • 从p1到pn的执行路径
      • 要么pi是一个语句之前的点, pi+1是该语句之后的点
      • 要么pi是某个基本块的结尾, 且pi+1是基本块某个后继的开头
    • 出现在某个点的程序状态
      • 某个运行时刻, 当指令指针指向这个程序点时, 各个变量和动态内存中存放的值
      • 指令指针可能多次指向同一个程序点, 因此一个程序点可能对应多个程序状态
    • 数据流分析把可能出现在同一个程序点上的状态集合, 总结为一些特性
      • 不管程序怎么运行, 到达该点, 程序状态总是满足分析得到的特性
      • 不同的分析技术关心不同的信息
    • 性质和算法
      • 根据不同的需要来设置不同的性质集合, 然后设计分析算法
        • 程序点上的性质被表示成为数据流值, 求解这些数据流值实际上就是推导这些性质的过程
      • 到达定值
        • 如果要求出变量在某个点上的值可能在哪里定制, 可以使用到达定值
          • 性质形式: x由d1定值
        • 如果希望实现常量折叠优化, 关心的是某个点上x的值是否总是由某个常量赋值语句给予
          • 性质形式: x=c, x = NAC
    • 数据流分析模式
      • 数据流分析中, 程序点和数据流值关联在一起
        • 数据流值表示了程序点的性质
        • 和某个程序点相关的数据流值: 程序运行中经过这个点时必然具有的性质(安全)
      • 域
        • 某个数据流所有可能值的集合
        • 不容的应用选不同的域, 例如到达定值, 数据流值是定值(三地址语句)的集合
    • 数据流分析
      • 对一组数据约束求解, 得到各个点上的数据流值
        • 两类约束: 语义约束和控制流
      • 基于语义的约束
        • 一个语句之前和之后的数据流值, 受到其语义的约束
        • 语句语义通常用传递函数表示, 它把一个数据流值映射为另一个数据流值
      • 基于控制流的约束
        • 在基本块内部, 一个语句的输出=下一个语句的输入
        • 流图的控制流边也对应新的约束
    • 基本块内的数据流模式
      • 非常简单
        • 从头到尾不会中断
        • 没有分支
      • 基本块的效果, 就是各个语句效果的复合
      • 可以预先处理基本块内部数据流关系, 给出基本块对应的传递函数
    • 基本块之间的控制流约束
      • 前向数据流问题
        • B的传递函数根据IN计算OUT
        • IN和B的各个前驱基本块之间的OUT值具有约束关系
      • 逆向数据流问题
        • B的传递函数根据OUT计算得到IN
        • OUT和B的各个后继基本块之间具有约束关系
    • 数据流方程解的精确性和安全性
      • 数据流方程通常没有唯一解
      • 目标是寻找一个最精确且满足约束的解
        • 精确: 进行最多的改进
        • 满足约束: 根据分析结果来改进代码是安全的
    • 到达定值
      • 到达定值
        • 假定x有定值d, 如果存在一个路径, 从紧随d的点到达某点p, 并且此路径上没有x的其他定值点, 则称x的定值d到达p
        • 如果路径上有对x的其他定值, 我们说变量x的这个定值d被杀死了
      • 如果某个变量x的一个定值d到达了点p, 在p点使用x的时候, x的值是由d最后定值的
      • 到达定值的解允许不精确, 但必须是安全的
        • 分析得到的到达定值可能实际上不会到达
        • 但是实际到达的一定被分析出来, 否则不安全
      • 比如确定x在p是否为常量
        • 忽略变化, 可能被误认为常量, 不安全
        • 过多估计则相反
      • 语句/基本块的传递方程
        • 定值d: u = v + w
          • 生成了对变量u的新定值, 杀死其他对u的定值
          • 生成-杀死形式: $f_d(x) = gen_d\cup (x-kill_d)$
          • $gen_d = {d}, kill_d = \{程序中其他对u的定值\}$
        • 生成-杀死形式的函数复合仍具有该形式
          • (直接函数复合就好)
          • 生成的定值: 第二部分生成, 第一部分生成且没被第二部分杀死
          • 杀死的定值: 第一部分, 第二部分杀死的定值
        • 设B有n个语句, 第i个语句的传递函数为fi
          • $f_B(x)=gen_b\cup(x-kill_B)$
          • $gen_B$是所有i, 被第i个句子生成, 且未被其后的句子杀死的定值集合
          • $kill_B$
        • 到达定值的控制流方程
          • 只要一个定值能够沿某条路径到达一个程序点, 那么他就是到达定值
          • $IN[B]=\cup_{P是B的前驱基本块}OUT[P]$
            • 如果从P到B有一条控制流边, 则$OUT[P]$在$IN[B]$中
            • 一个定值必然先出现在前驱, 才能出现在B
          • $\cup$交汇运算符: 不一定是并集
        • 控制流方程的迭代解法
          • ENTRY基本块的传递函数是常函数: $OUT[ENTRY] = \emptyset$
          • 其他基本块
            • $OUT[B] = gen_B\cup(IN[B] - kill_B)$
            • $IN[B]=\cup_{P是B的前驱基本块}OUT[P]$
          • 迭代解法
            • 先求出各个基本块的$gen$和$kill$
            • 令所有的$OUT[B]$为空集, 然后不停迭代, 得到最小不动点的解
          • 解法的正确性: 不断传递定值, 直到被杀死
          • 为什么不出现死循环
            • 各个OUT不会变小
            • 各个OUT有穷的上界
            • 只有增加了某个OUT的值, 算法才会继续迭代
          • 最大迭代次数: 流图的结点数n, 任意定值经过n步必然到达所有可能的结点
          • 结束时, 各个IN/OUT必然满足数据流方程
  • 活跃变量分析
    • 活跃变量分析
      • x在p上的值是否会在某条从p出发的路径中使用
      • 变量x在p上活跃, 当且仅当存在一条从p开始的路径, 其末端使用了x, 且路径上没有对x进行覆盖
    • 用途: 寄存器分配/死代码删除
    • 数据流值: (活跃)变量的集合
    • 基本块内的数据流方程
      • 基本块内的传递函数依然是生成-杀死形式, 但是从OUT算IN(逆向)
        • $use_B$: 在B中先于定值被使用
        • $def_B$: 在B中先于使用被定值
      • 语句的传递函数
        • s: x = y + z
        • $use_s = \{y,z\}$
        • $def_s = \{x\} - \{y,z\}$
      • 多个语句
        • 每一个语句的use需减去其前所有def, 然后cup得到整个块的use
        • 每一个语句的def需减去其前所有use, 然后cup得到整个块的def
    • 活跃变量数据流方程
      • 任何变量在程序出口不再活跃: $IN[EXIT] = 空集$
      • 对于所有不等于EXIT的基本块
        • $IN[B] = use_B\cup(OUT[B]-def_B)$
        • $OUT[B] = \bigcup_{S是B的后继基本块}IN[S]$
      • 与到达定值比较
        • 都使用并运算; 数据流向不同(逆向)
    • 活跃变量分析的迭代方法
      • 首先所有IN都是空集
      • 对除了EXIT的所有基本块
        • 计算新OUT
        • 计算新IN
      • 直到各个IN无变化
      • IN越来越大, 且有上界, 因此必然停机

  • 可用表达式分析

    • x+y在p点可用
      • 从流图入口结点到达p的每条路径都对x+y求值, 且在最后一次求值之后再也没有对x或y赋值
    • 主要用途
      • 寻找全局公共子表达式
    • 生成-杀死
      • 生成: 基本块求值x+y, 且之后没有对x或y赋值, 那么它生成了x+y
      • 杀死: 基本块对x或y赋值, 且没有重新计算x+y, 那么它杀死了x+y
    • 计算基本块生成的表达式
      • 初始化S={}
      • 从头到尾处理每个指令x=y+z
        • y+z添加到S中, 从S中删除任何涉及变量x的表达式
      • 遍历结束得到基本块生成的表达式集合
    • 计算基本块杀死的表达式: 表达式的某个分量被定值, 且没有被再次生成
    • 可用表达式的数据流方程
      • ENTRY结点的出口处没有可用表达式: $OUT[ENTRY]=空集$
    • 其他基本块的方程
      • OUT: 跟到达定值一样
      • IN: 求交集而不是并集

    • 算法

      • $OUT[ENTRY]$为空集, 而其余的OUT初始化为全集

      ||到达定值|活跃变量|可用表达式|
      |-|-|-|-|
      |方向|正向|反向|正向|
      |传递函数|$gen_B\cup(x-kill_B)$|$use_B\cup(x-def_B)$|$e_gen_B\cup(x-e_kill_B)$|
      |边界条件|$OUT[ENTRY]=\emptyset$|$IN[EXIT]=\emptyset$|$OUT[ENTRY]=\emptyset$|
      |交汇运算$\wedge$|$\cup$|$\cup$|$\cap$|
      |方程组|$OUT[B]=f_B(IN[B])\quad IN[B]=\bigwedge_{P,pred(B)}OUT[P]$|$IN[B]=f_B(OUT[B])\quad OUT[B]=\bigvee_{S,succ(B)}IN[S]$|$OUT[B] = f_B(IN[B])\quad IN[B]=\bigvee_{P,pred(B)}OUT[P]$|
      |初始值|$OUT[B]=\emptyset$|$IN[B]=\emptyset$|$OUT[B]=U$|

部分冗余消除

  • 部分冗余消除
    • 目标: 尽量减少表达式求值的次数
    • 对于表达式x+y
      • 全局公共子表达式: 如果x+y求值前的程序点上x+y可用, 那么不需要再对x+y求值
      • 循环不变表达式: 循环中表达式x+y的值不变, 可以只计算一次
      • 部分冗余: 在程序按照某些路径到达这个点的时候x+y已经计算过, 但另一些尚未计算过
    • 需要更复杂的数据流分析技术
    • 需要添加基本块来消除的冗余
      • 进行两种操作
        • 在关键边上增加基本块
        • 进行代码复制
      • 关键边
        • 从具有多个后继的结点, 到达具有多个前驱的结点
    • 懒惰代码移动
      • 目标
        • 所有不复制代码就可消除的冗余计算都被消除
        • 优化后的代码不会执行源程序中不执行的任何计算
        • 表达式的计算应该尽量靠后, 利于寄存器分配
      • 冗余消除
        • 完全冗余
        • 部分冗余: 在流图中放置表达式x+y的拷贝, 使得某处的x+y成为完全冗余从而删除
      • 基本步骤
        • 找出各个程序点上预期执行的所有表达式
          • 被预期执行: 如果从p出发的所有路径都会计算b+c的值, 并且b和c在那时的值就是p的值, 那么b+c在p预期执行
          • 数据流分析框架
            • 逆向分析
            • 基本块内部: 当表达式在B出口处被预期执行, 且它没有被B杀死, 那么它在B入口处也被预期执行
            • 基本块之间: 当在B的所有后继基本块的入口处都被预期执行, 那么表达式在B出口处被预期执行
            • 在整个程序的出口处, 没有表达式被预期执行
          • 求出预期执行点之后, 表达式被放置到首次被预期执行的程序点上: 一些表达式因此变成完全冗余
        • 在表达式被预期执行但是不可用的程序点上, 放置表达式的计算
          • 可用表达式: 和前面的可用表达式类似, 但假设代码已经被复制到的预期执行点上
          • 表达式在基本块的出口处可用的条件
            • 在基本块的入口处可用, 或在基本块的入口处的预期执行表达式中
            • 且没有被这个基本块杀死
        • 把表达式尽量后延到某个程序点, 在到达这个程序点的所有路径上, 这个表达式在这个程序点之前被预期执行, 但还没有使用这个值
          • 可后延表达式
            • 在保持程序语义的情况下， 尽可能延后计算表达式
            • x + y可后延到p的条件: 所有从程序入口到达p的路径 中都会碰到一个位置较前的x + y，且在最后一个这样的位 置到p之间没有使用x + y
            • 粗略地说，一个表达式将被放置在边界上，即一 个表达式从可后延变成不可后延的地方
        • 消除只使用一次的临时变量
          • 确定一个被引入的临时变量是否在它所在基本块 之外的其它地方使用+
            • 对表达式的活跃性分析
            • 如果从程序点p出发的一条路径在表达式被重新求值之 前使用了该表达式，那么该表达式在点p上被使用

循环的识别分析和优化

  • 循环的重要性+ 程序的大部分执行时间都花在循环上
    • 也是数据流分析需要经过若干次迭代的原因
  • 相关概念
    • 支配结点
      • 支配 (Dominate): 如果每条从入口结点到达n的路径都经过d，那么d支配n，记为d dom n
      • 支配结点树可以表示支配关系
        • 根结点：入口结点
        • 每个结点d支配且只支配树中的后代结点
      • 直接支配结点
        • 从入口结点到达n的任何路径 (不含n) 中，它是路径中 最后一个支配n的结点
        • n的直接支配结点m具有如下性质：如果d ≠ n且d dom n，那么d dom m
      • 寻找支配结点算法
        +
    • 深度优先排序
    • 回边
    • 图的深度
    • 可归约性