哈工大编译优化笔记

什么是基本块?


什么是流图



优化的分类

  • 机器无关优化
    • 针对中间代码
  • 局部代码优化
    • 单个基本块范围内的优化
  • 全局代码优化
    • 多个基本块的优化

      常用优化方法

      删除公共子表达式


      例子如下,先看B5,对它进行局部和全局公共子表达式消除。



      再看B6



      关键问题,如何自动识别公共子表达式?

      删除无用代码





      关键问题,如何自动识别无用代码?

      常量合并

      循环代码外提


      强度削弱





      基本块的优化

数据流分析


s是一个语句,所以说数据流值在经过s之后会变化发,所谓传递函数。

到达定值分析



注意KILL这个概念,是变量x被重新赋值,则原来的定值(语句)被杀死。

到达定值分析的用途



杀死与生成



到达定值分析的算法


kill置为0,gen置为1

活跃变量分析





活跃变量就是定义了以后会被用到嘛2333

因为这是一个逆向数据流问题,所以用x表示在基本块出口处的活跃变量的集合,f(x)表示基本块入口处活跃变量的集合。

use表示在基本块中首次出现,以引用形式出现的变量的集合,所以这些变量在基本块入口处肯定是活跃的。

def表示在基本块中首次出现,以定值形式出现的变量的集合,所以这些变量在基本块入口处肯定是不活跃的。
所以说def杀死了某些变量在基本块入口处成为活跃变量的可能性。


解释一下B2,i和j在基本块B2中都是以引用形式首次出现,所以在use里,而def为∅



得到活跃变量表

可用表达式分析






z=x op y生成了表达式x op y,加入gen
同时这条语句对z定值,于是删除与z相关的表达式。

z = x op y,于是从kill中删除表达式x op y,代表它复活了。
同时这条语句对z定值,于是把和z相关的表达式加入kill中


注意是IN的交集

对循环的优化

要想对循环进行优化,首先要识别出流图中的循环。

支配节点(Dominators)和回边

  • 支配节点


    在支配节点树中,每个节点只支配它和它的后代节点。
    可以看出一个节点可能会有若干个支配节点,于是给出直接支配节点的定义

    寻找支配节点是一个数据流问题

注意交运算,所以初始化时初始为全集

  • 回边

自然循环及其识别


如图2和3不存在彼此支配的关系,2和3构成了一个循环,控制既可以从2,也可以从3号节点进入,这样循环的入口节点就不唯一了。



删除全局子表达式


删除复制语句



注意到达定义分析是并 IN[P],可用表达式分析是交 IN[P]

代码移动

  • 循环不变计算
  • 代码外提

    循环不变计算

    一条语句是循环不变,当且仅当运算分量的值在循环中不变
  1. 运算分量是常数
  2. 运算分量的所有定值点在循环以外
  3. 运算分量只有一个到达定值,且在循环以内,且该定值本身就是循环内的一个不变计算。

    代码外提

注意不一定所有的循环不变量都能外提

如图,B2并不一定被执行,那么其中的代码外提就是错误的。

如果还有其他语句对x赋值,那么就有可能让原来的定值语句被杀死。