GCCTreeSSA优化分析中期报告PPT课件

1、GCC Tree SSA优化分析中期报告Everything is Compilable夏惠东 计73 2007011301赵宇航 计73 2007011304 穆太江 计73 2007011312郭静宜 计73 2007011320吴 韬 计73 2007011330 Recent Work 阅读了四篇paper，了解一些优化算法的原理 Constant Propagation with Conditional Branches Partial Redundancy Elimination in SSA Form Accurate Static Branch Prediction by Va

2、lue Range Propagation Analysis of induction variables using chains of recurrences: extensions 阅读了部分SSA代码，初步熟悉SSA的组织结构Work View Two papers Constant Propagation with Conditional Branches Partial Redundancy Elimination in SSA Form Accurate Static Branch Prediction by Value Range PropagationConstant Pro

3、pagation with Conditional Branches 程序流程图与常量传播的Lattice定义 四种优化算法介绍程序流程图 N：赋值声明语句数 +决定分支的表达式数 E：程序流程图中的边数 V：程序中的变量数 常量节点分三类：条件节点、赋值节点、唯一的启示节点。 常量传播的Lattice定义 节点的赋值特征用lattice element来表示 Lattice element分三种： 最高元素top T，最低元素bottom ，中间元素constant 常量的个数可以是无限的 常量之间是无区别的 LatticeCell用于存放lattice element。常量传播的Latti

4、ce定义常量传播的Lattice定义 当一个LatticeCell被赋为时，表示在程序的所有可执行部分，相关的结果或操作数的值总是保持不变直到退出该节点。表示不能被确定的常数，T表示未确定是否为常量的变量。算法开始时，除起始节点以外的节点都是T。通过并这一规则进行运算。并的规则确保汇合点的lattice值不会比前面的输入高。并的规则如下：常量传播的Lattice定义Constant Propagation的四种优化算法 Simple Constant Sparse Simple Constant Conditional Constant Sparse Conditional ConstantS

5、imple Constant 利用程序流图(program flow graph)进行常量传播的表示。对于程序中的每个节点，用两个LatticeCell分别记录节点入口和出口的变量值。对每个节点的访问，就是访问节点中的每个LatticeCellSimple Constant 算法描述 （1）将程序的初始节点放入表中； （2）若表不空，取出表头节点作为待检验节点；否则转（6）； （3）将待检验节点入口LatticeCell中的值作为前面节点出口的值的并；若该节点为声明语句，则以新插入的值为基础进行估计。 （4）若在该节点处被赋值的变量的值与在出口LatticeCell中的值不符，则将跟在被检验节

6、点后面的节点都需要加入到列表中； （5）若出口LatticeCell没有改变，则不加入新的节点；转（2）； （6）结束Simple Constant 算法分析 SC算法中找到的常量被称为简单常量，简单常量有两个特征： 没有关于选择分支的信息假设； 在程序中的每一条路径上保持同一个值。 复杂度：最好情况O(EV)，最坏情况O(EV2)，空间需求：O(NV)Sparse Simple ConstantSparse Simple Constant 算法描述 （1）检验所有的表达式。如果表达式的值不能在编译阶段进行估计，那么相应的LatticeCell被赋值为。如果在表达式中没有变量出现，则表达式被计

7、算且LatticeCell被赋值为i。所有其它的LatticeCell都赋值为T； （2）初始化列表，将所有包含一个不是T的LatticeCell的SSA边都加入到列表中； （3）构造SSA边定义端的LatticeCell值和使用端的LatticeCell值的并。如果值的并与使用端的值不相同，则将使用端的值变成并。新的值被用来重新计算前面的用了以前的值的表达式，然后再重复刚才的操作。如果表达式的新值比原来的低，则所有以该点起始的SSA边都被加入到列表中。 （4）该算法在列表变空时停止；Sparse Simple Constant 算法分析 该算法的时间复杂度与SSA图的大小成比例，O(EV)。

8、效果与SC相同，但与SC相比有更高的效率。实际复杂度是线性的。Conditional Constant 算法描述 （1）将程序流图中的所有边初始化为unexecutable，从起始节点开始象征性的执行程序； （2）当一个赋值节点被执行时，从该节点出发的边被标记为executable，并加入到列表中。当一个条件节点被执行时，估算出控制条件的表达式的值然后决定执行哪个分支。如果表达式被估计为，那么所有的分支都被考虑。与这些分支相对应的边会被加入到列表中。如果表达式被估算为，则只有一个分支被考虑，与该分支相关的边会被加入到列表中。Conditional Constant 算法分析 CC算法比SC算法

9、更有强大，因为当CC算法假设一个条件表达式是常量的时候，它就会假设程序只执行其中的一个固定的分支。 同时，该方法实现了不可达代码段的预测 该算法的时间复杂度与SC相同，在最坏的情况下，没有常数分支，复杂度为O(EV2)。该方法的平均复杂度比SC好。Sparse Conditional Constant 数据结构 FlowWorkList表示程序流程图的边的列表； SSAWorkList表示SSA边的列表；Sparse Conditional ConstantSparse Conditional ConstantSparse Conditional Constant 该算法的复杂度是：程序流程图

10、的边数+SSA边数，实际复杂度是线性的。效果与CC算法相同。Partial Redundancy Elimination in SSA FormPRE简介 Partial Redundancy Elimination(PRE)最早由Morel和Renvoise在1979年开发的一个强大的优化技术。 这项技术通过数据流研究的方式减少在程序中的部分冗余。 虽然全局公共字表达式以及循环不变计算是部分冗余的特殊情况，PRE也可以对它们进行处理。 基于以上原因，PRE已经成为全局优化器中重要的组成部分。SSA简介 SSA (static single-assignment) 是一种热门的优化编译器的方式

11、。 SSA的多用途来自于它能够在程序变量间提供准确的“use-definition”关系以及确切的形式。 很多全局优化算法都是基于SSA的形式开发的。SSAPRE 但是大多数PRE都是基于一种bit-vector的公式化方式以及数据流等式的交互解决方式。 本篇文章试图既包含之前关于PRE效果最好的工作，并且建立在SSA (static single-assignment ) 的形式上.问题 但是大多数SSA的使用被局限在解决与程序变量相关的问题上。 SSA并不能直接应用在解决基于表达式的问题。因为此时对于表达式的 ”use-def” 概念比较模糊。 这篇文章就试图证明这种关系，并且将基于SSA

12、的方法应用于PRE以及其它基于表达式的问题。SSA形式一个程序被认为是SSA形式，若它满足以下条件：它的任何一个变量都只定义一次，并且这个变量的每次使用都只由其定义支配。FRG 对一个操作E给出一个控制流图以及一个冗余关系，我们可以这样定义factored redundancy graph (FRG): E的FRG图中的节点是由在E的冗余关系中真实出现的地方再加上若在一个 模块中，有真实出现的E，则增加一个 结点。 Upward edge: 从部分冗余真实出现的结点以及部分冗余的 操作，指向其代表出现的结点。 Downward edge: upward edge的反向边。 SSAPRE算法 以

13、下，我们将会简要地分四步介绍SSAPRE这个框架 首先我们将会介绍关于SSA程序的简化假设： 每个 赋值含有一个性质：其左操作数以及其所有的运算数是原来程序变量的形式 相同程序变量的不同形式的活动区域不重叠-插入 当相同表达式的不同值到达一个程序的公共点的时候，表达式需要 这里有两种不同的情况会导致 代替表达式 第一种情况是当一个表达式出现的时候，我们会插入 在其迭代DF+ (dominance frontier). 第二种情况是对于在表达式里面包含的任何一个变量都有一个重命名 重命名步骤给表达式的出现赋一个冗余类的值。 冗余类值具有以下两个重要的性质： 第一，每次出现具有相同冗余类的数字就会

14、有相同的数值。 第二，任何表达式包含两个不同类数字的控制流路径必须交叉赋值给表达式的操作数或者down-safety PRE插入一个计算的标准是这个计算在插入的时候是down-safe的。 这个标准时用来保证插入的计算不会引入异常到缺少它们的路径中去，同时新插入的新的冗余到程序中。 不是down-safe的，如果这里有一个控制流路径从 到一个没有在程序退出之前或者被重定义修改之前没有评估的表达式。Will-be-avail 这一步的主要任务是预测表达式是否在每个 出现的时候都会遵守PRE的插入。 这一步首先计算操作数值可以安全计算处的 的集合。 下一步计算表达式的值在任何计算优化可替代处的 值

15、。Finalize 最后一步将FRG转化成优化的形式。 Finalize包含两个部分: Finalize_1的任务 每个真实出现的表达式都用一个标志reload来标识，用来指出它是否可以在这个地方计算或者重载 对于 的will-be-avail是真的地方，在新建立的对应于 操作数的边上执行插入操作。Finalize Finalize_2: 每个真实出现且并没有被重载的地方都会用一个save flag来标志，用来标识表达式的值应该被保存 无关 的应被去掉Accurate Static Branch Predictionby Value Range Propagation 由于流水线结构中存在的控

16、制冒险问题，为了提高系统性能，常常需要对分支的执行情况作出预测。同时，编译器的很多优化策略，也需要准确的分支预测支持。分支预测分为静态预测和动态预测两种，静态分支预测根据编译时刻可知的程序本身结构特性或一些静态执行信息如profile，对分支的行为作出预测判断，并为编译器的其它优化策略提供依据。 编译器使用profile-based和program-based的方法进行静态分支预测。在profile-based的方式中，它有选择地保存控制流图（CFG）中的一些边的执行次数，而后用它们来计算最终预测结果即每个branch的跳转执行的概率和各基本块执行频率；在program-based的方式中，它

17、使用一些启发式策略来预测分支行为，而后综合各策略来得到最终预测结果。 在profile中，采用一个函数为每个变量做记录，命名不同的名字，在程序执行的过程中记录下他们的值，当遇到条件分支的时候，首先采用taken和nottaken的最简单的静态分支预测方式。然后当预测分支结果不正确的时候，即跳转的目标地址不对的时候，采用修正的方案。 ROT进行静态分支预测，静态分支预测主要用于分支cache初始化时候，优先级比动态分支预测低。静态分支预测根据编码在分支指令中的提示信息进行。静态预测充分利用了编译器信息。对于IP相对分支，在ROT阶段计算分支的目标地址，和前面给出的目标地址进行比较，如果不同则证明

18、前面分支预测目标地址错误，需要修正，产生一个周期的气泡。call和return指令利用RSB，call的时候压栈，return的时候弹栈，提供返回地址，正确的返回分支预测延迟为1。 分支的筛选是在编译时进行的，根据前面的静态分支预测，可以在编译的时候减少很多不必要的肯定不会发生的分支，通过这样的方式达到代码的优化，减少运行时间。SSA Framework 我们将TreeSSA优化框架看作一个GCC的模块 这个模块的API定义以及数据结构的定义都在文件tree-flow.h和tree-pass.h中。前者定义了数据流和控制流分析(树上的)，而后者则定义了用于描述一个tree-ssa优化遍的接口和

19、数据结构。SSA Framework 基本文件：passes.c中的init_optimization_passes函数负责调度所有需要执行的遍，它在toplev_main中的general_init函数的最后被调用。所有添加的遍都要在这个函数中注册；tree-optimize.c是所有树优化遍的主要驱动；tree-ssa.c实现了一些操作SSA形式的函数；tree-into-ssa.c将一个一般形式的程序；转化成SSA形式的；tree-outof-ssa.c将一个SSA形式的程序转换成一般形式的；tree-ssanames.c 和tree-phinodes.c实现了对于SSA_NAME和PHI_NODE的操作和存储管理；tree-cfg.c包含创建和操作控制流图的代码； tree-dfa.c包含处理数据流图的代码；tree-ssa-operands.c包含操作ssa操作数的代码；tree-iterator.hc包含操作GENERIC和GIMPLE树语句的迭代器；gimplify.c将GENERIC转换成GIMPLE；tree-gimple.hc包含分析和验证GIMPLE树的代码；Passes 转化遍gimple-low.c将GIMPLE转化成无结构的形式，这个在优化之前做，简化优化器的工作。 优化遍tree-ssa-pre.c t