GCC4优化技术汇总.doc

GCC的优化编译过程（version4）GCC的编译过程可分为4个子过程，包括Parsing pass、Gimplifcation pass、Tree SSA passes、RTL passes 。在这四个子过程中，GCC优化主要在Tree SSA passes和RTL passes中进行。1、SSA 优化(1)删除无用语句（Remove useless statements） 该过程对gimple代码进行非常简单的扫描，识别出明显的死代码并删除。我们在这里做的一些事情包括，简化具有不变条件的if语句，删除对显然不会抛出异常的代码所做的异常处理，删除不含有变量的词法绑定（lexical bindings），以及其它各种简单的清除。这是为了能够快速的去掉一些显而易见的东西，而不是等到后面去花费更多的功夫。该过程在tree-cfg.c中，并且由pass_remove_useless_stmts来描述。(2)死代码消除（Dead code elimination） 该过程扫描函数来寻找没有副作用，且结果没有被使用的语句。它不进行内存活跃分析，所以任何存储在内存中值都被认为是被使用的。该过程在整个优化处理中被运行多次。它位于tree-ssa-dce.c中，并由pass_dce来描述。(3)dominator优化（Dominator optimizations） 该过程执行平凡的基于dominator的复制和常量传播，表达式简化，以及跳转线程化。它在整个优化处理中被运行多次。它位于tree-ssa-dom.c中，并由pass_dominator来描述。(4)单用变量向前传播（Forward propagation of single-use variables） 该过程尝试移除冗余计算，通过将只使用一次的变量替换为使用它们的表达式，并查看是否得到的结果可以被简化。它位于tree-ssa-forwprop.c中，并由pass_forwprop来描述。(5)可能别名优化（May-alias optimization） 该过程执行一个流敏感基于SSA指向的分析。所得的may-alias, must-alias和escape分析信息用来将变量从内存中可寻址的对象提升为可以被重命名为SSA形式的无别名变量。过程位于tree-ssa-alias.c中，并由pass_may_alias来描述。(6)死存储消除（Dead store elimination） 该过程消除死存储，即存储到内存中，而该内存被随后的另一个存储操作重新写入，并且之间没有加载操作。过程位于tree-ssa-dse.c中，并由pass_dse来描述。(7)尾递归消除（Tail recursion elimination） 该过程将所有的尾递归转换到一个循环中。它位于tree-tailcall.c中，并由pass_tail_recursion来描述。(8)部分冗余消除（Partial redundancy elimination） 该过程消除部分冗余计算，同时执行加载移动。过程位于tree-ssa-pre.c中，并由pass_pre来描述。如果设置了-funsafe-math-optimizations，则在部分冗余消除前，GCC尝试通过倒数方式将除法转换为乘法。过程位于tree-ssa-math-opts.c中，并由pass_cse_reciprocal来描述。(9)完全冗余消除（Full redundancy elimination） 这是一个较简单的PRE形式，只消除在所有路径上产生的冗余。它位于tree-ssa-pre.c中，并由pass_fre来描述。(10)循环优化（Loop optimization） 该过程的主驱动程序位于tree-ssa-loop.c中，并且由pass_loop来描述。该过程执行的优化为：循环不变量移动。该过程只移动在rtl级难以处理的不变量（函数调用，扩展成非平凡insn序列的操作）。使用-funswitch-loops时，它还将不变的条件操作数移到循环外面，使得我们能够在循环外提过程中只需要进行平凡不变量分析。该过程还包括存储移动。该过程在tree-ssa-loop-im.c中实现。规约变量优化。该过程执行标准的规约变量优化，包括强度缩减，规约变量合并，以及规约变量消除。该过程在tree-ssa-loop-ivopts.c中实现。循环外提。该过程将不变的条件跳转移到循环外面。为了达到这一点，对于每种可能的条件跳转结果都会创建一个循环副本。该过程在tree-ssa-loop-unswitch.c中实现。该过程应该最终替代在loop-unswitch.c中的rtl级的循环外提，但是目前rtl级的过程还不是完全多余的，是因为还缺少tree级的别名分析。这些优化还用到了tree-ssa-loop-manip.c，cfgloop.c，cfgloopanal.c和cfgloopmanip.c中的各种函数。(11)用于向量化的Tree级if转换 （Tree level if-conversion for vectorizer） 该过程应用if转换来简化循环，以助于向量化。我们识别可以if转换的循环，并将基本块合并到一个大块中。想法是将循环表现为这样的形式，使得向量化能够对语句和可用的向量操作进行一一映射。该过程位于tree-if-conv.c中，并由pass_if_conversion来描述。(12)条件常量传播（Conditional constant propagation） 该过程松弛一个点阵值用于识别那些即使在条件分支中也肯定是常数的。该过程位于tree-ssa-ccp.c中，并由pass_ccp来描述。(13)条件复制传播（Conditional copy propagation） 这类似于常量传播，它消除代码中的冗余复制。该过程位于tree-ssa-copy.c中，并由pass_copy_prop来描述。(14) 控制依赖死代码消除（Control dependence dead code elimination） 该过程是死代码消除的较强形式，能够消除不必要的控制流程语句。它位于tree-ssa-dce.c中，并由pass_cd_dce来描述。(15) 尾调用消除（Tail call elimination） 该过程识别可以被重写为跳转的函数调用。这里没有进行实际的代码转换，不过却解决了数据流和控制流的问题。代码转换需要目标机支持，因此被推迟到RTL级。该过程位于tree-tailcall.c中，并且由pass_tail_calls来描述。RTL转换由calls.c中的fixup_tail_calls来处理。(16) 返回值优化（Return value optimization） 如果函数总是返回同一局部变量，并且那个局部变量是一个聚合类型，则变量将由函数返回值来替换。这相当于作用于GIMPLE的C+命名返回值优化。该过程位于tree-nrv.c中，并且由pass_nrv来描述。(17) 返回槽优化（Return slot optimization） 如果函数返回一个内存对象，并且像var=foo()这样被调用，该过程尝试改变调用，使得var的地址传送给调用者，以避免一次额外的内存复制。该过程位于tree_nrv.c中，并由pass_return_slot来描述。(18) 循环不变量移动（Loop invariant motion） 该过程将昂贵的循环不变量计算移出循环。该过程位于tree-ssa-loop.c中，并由pass_lim来描述。(19) 循环嵌套优化（Loop nest optimizations） 这是一类工作于循环嵌套的循环转换。它包括循环变换（loop interchange），scaling，skewing和逆转（reversal），并且它们用来配合。该过程位于tree-loop-linear.c中，并由pass_linear_transform来描述。(20) 空循环移除（Removal of empty loops） 该过程移除不含代码的循环。该过程位于tree-ssa-loop-ivcanon.c中，并由pass_empty_loop来描述。(21) 小循环展开（Unrolling of small loops） 该过程将迭代次数很少的循环完全展开。该过程位于tree-ssa-loop-ivcanon.c中，并由pass_complete_unroll来描述。(22) 预测公约（Predictive commoning） 该过程使代码可以重用先前循环迭代的计算，特别是对内存的加载和存贮。该过程位于tree-predcom.c中，并由pass_predcom来描述。(23) 重组（Reassociation） 该过程将算术表达式重写为可以进行优化的形式，例如冗余消除和向量化。过程位于tree-ssa-reassoc.c中，并由pass_reassoc来描述。2、RTL优化(24) 单定义值的向前传播（Forward propagation of single-def values） 该过程尝试通过替换来自单一定义的变量，并观察结果是否能够被简化的方式，来去除冗余计算。它执行了复制传播和寻址模式选择。该过程运行两次，并只在第二次的时候将值传播到循环中。它位于fwprop.c中。(25)公共子表达式消除（Common subexpression elimination） 该过程去除基本块中的冗余计算，并且根据代价来优化寻址模式。该过程运行两次。源代码位于cse.c中。(26)全局公共子表达式消除（Global common subexpression elimination） 该过程执行两种不同类型的GCSE，取决于你是否在优化代码大小（基于LCM的GCSE趋向于通过增加代码大小来获得速度，而基于Morel-Renvoise的GCSE则不是）。当优化代码大小时，使用Morel-Renvoise Partial Redundancy Elimination（部分冗余消除）来做GCSE，并不尝试将不变量移到循环之外这留到循环优化过程。如果进行MR PRE，则还会进行代码提升（code hoisting），（也称为code unification），还有加载移动（load motion）。如果你在优化速度，则会进行基于LCM（lazy code motion）的GCSE。LCM是基于Knoop, Ruthing和Steffen的工作。基于LCM的GCSE也会进行循环不变量代码移动。当优化速度时，我们还执行加载和存储移动。不管使用哪一种类型的GCSE，该过程都还执行全局常量传播和复制传播。该过程的源代码为gcse.c，LCM程序在lcm.c中。(27)循环优化（Loop optimization） 该过程执行几个循环相关的优化。源文件cfgloopanal.c和cfgloopmanip.c包含了通用的循环分析和操作代码。循环结构体的初始化和完成（finalization）由loop-init.c处理。循环不变量移动过程在loop-invariant.c中实现。基本块级的优化unrolling,peeling和unswitching在loop-unswitch.c和loop-unroll.c中实现。loop-doloop.c是关于使用特定的机器相关结构来替代循环退出条件的处理。(28)If转换（If conversion） 该过程尝试使用This pass attempts to replace conditional branches and surrounding assignments with arithmetic, boolean value producing comparison instructions, and conditional move instructions.。如果目标机支持，则在reload之后的最近的一次调用中，会生成预测指令（predicated instructions）。该过程位于ifcvt.c。(29)指令合并（Instruction combination） 该过程尝试去将数据流相关的两条或者三条指令组合并为单一指令。它通过替代，使用代数简化结果的方式来为指令合并RTL表达式，然后尝试去将结果跟机器描述匹配。该过程位于combine.c。(30) 寄存器移动（Register movement） 该过程寻找这样的情况，即当匹配约束条件时会迫使指令需要重载，并且这个重载为一个寄存器到寄存器的move操作。然后它尝试改变指令使用的寄存器来避免move指令。该过程位于regmove.c中。(31) 优化模式转换（Optimize mode switching） 该过程寻找这样的指令，即需要处理器处于特定的模式（mode），然后将模式改变的数目减到最少。这些模式是什么以及应用于什么完全是目标机特定的。源代码位于mode-switching.c中。(32) 模调度（Modulo scheduling） 该过程查看内部循环并且通过复合不同的迭代来重排它们的指令。模调度在指令调度之后立即被执行。该过程位于modulo-sched.c。(33)指令调度（Instruction scheduling） 该过程寻找这样的指令，其输出在后来的指令中不会用到。在RISC机器上，内存加载和浮点指令经常会有这样的特征。它重新排序基本块中的指令以尝试将定义和使用分开，从而避免引起流水线阻塞。该过程执行两次，分别在寄存器分配之前和之后。该过程位于haifa-sched.c, sched-deps.c, sched-ebb.c, sched-rgn.c和sched-vis.c中。(34) 寄存器分配（Register allocation） 这些过程确保所有伪寄存器都被去除，或者通过给它们分配硬件寄存器，或者使用等价表达式来替换（例如常数），或者将它们放在栈中。这由几个子过程来完成：寄存器类别选择。扫描RTL代码来找出哪一种寄存器类别是最适合于每个伪寄存器。源文件为 regclass.c. 局部寄存器分配。该过程为只在基本块里使用的伪寄存器分配硬件寄存器。因为基本块是线性的，所以能够使