Tree SSA passes - GNU Compiler Collection (GCC) Internals

Next: RTL passes, Previous: Pass manager, Up: Passes

9.4 Tree-SSA过程

下面简要描述了经过gimplification之后的树优化过程，以及所在的源文件。

删除无用语句（Remove useless statements）
该过程对gimple代码进行非常简单的扫描，识别出明显的死代码并删除。我们在这里做的一些事情包括，简化具有不变条件的if语句，删除对显然不会抛出异常的代码所做的异常处理，删除不含有变量的词法绑定（lexical bindings），以及其它各种简单的清除。这是为了能够快速的去掉一些显而易见的东西，而不是等到后面去花费更多的功夫。该过程在tree-cfg.c中，并且由pass_remove_useless_stmts来描述。
Mudflap声明注册（Mudflap declaration registration）
如果启用了mudflap（参见-fmudflap -fmudflapth -fmudflapir我们便产生代码来记录一些使用mudflap运行时的变量声明。特别的，运行时会跟踪这些变量声明的生命期，将它们的地址记录下来，或者哪些边界在编译时不知道（extern）。该过程生成新的异常处理结构（try/finally），因此必须在它们下降之前运行。另外，该过程enqueque生命期扩展为整个程序的静态变量声明。过程位于tree-mudflap.c中，并由pass_mudflap_1来描述。
OpenMP下降（OpenMP lowering）
如果启用了OpenMP生成（-fopenmp），该过程将OpenMP结构下降为GIMPLE。
OpenMP结构下降涉及到为使用数据共享子句映射的局部变量创建替代表达式，揭示最可能同步指令的控制流，以及增加region标记来帮助控制流图的创建。该过程位于omp-low.c中，并由pass_lower_omp来描述。
OpenMP扩展（OpenMP expansion）
如果启用了OpenMP生成（-fopenmp），该过程将并行region扩展为由线程库调用的它们自己的函数。过程位于omp-low.c中，并由pass_expand_omp来描述。
控制流下降（Lower control flow）
该过程压平（flatten）if语句（COND_EXPR），并将词法绑定（BIND_EXPR）移到行外。在该过程之后，所有if语句将会有确切的两条goto语句在then和else处。每条语句的词法绑定信息将在TREE_BLOCK中找到，而不是由BIND_EXPR下的它的位置来推算出。该过程可以在gimple-low.c中找到，并由pass_lower_cf来描述。
异常处理控制流下降（Lower exception handling control flow）
该过程将高级别的异常处理结构（TRY_FINALLY_EXPR和TRY_CATCH_EXPR）转换为能显示表示控制流相关的形式。该过程之后，lookup_stmt_eh_region将会为任何可能具有EH控制流语义的语句返回一个非负数；对于确切的语义可以检查tree_can_throw_internal或tree_can_throw_external。确切的控制流可以从foreach_reachable_handler中提取。EH region嵌套树在except.h和except.c中定义。下降过程本身在tree-eh.c中，并由pass_lower_eh来描述。
构建控制流图（Build the control flow graph）
该过程将函数分解为基本块，并创建所有相连的边。它位于tree-cfg.c中，并由pass_build_cfg描述。
找到所有被引用的变量（Find all referenced variables）
该过程遍历整个函数，并将函数中所有被引用的变量搜集到一个数组中，referenced_vars。每个变量在数组中的索引被用作函数中这个变量的UID。SSA重写程序需要用到该数据。过程位于tree-dfa.c中，并由pass_referenced_vars来描述。
进入静态单赋值形式（Enter static single assignment form）
该过程将函数重写为SSA形式。该过程之后，所有is_gimple_reg变量将通过SSA_NAME来引用，并且所有其它变量将由VDEFS和VUSES来注解；对于每个基本块，PHI节点将会在需要的时候被插入。该过程位于tree-ssa.c中，并由pass_build_ssa来描述。
未初始化变量警告（Warn for uninitialized variables）
该过程扫描函数，寻找使用缺省定义的SSA_NAME。对于非参数变量，这样的使用是未初始化的。该过程运行两次，优化前和优化后。第一次过程中，我们只警告肯定是未初始化的；在第二次过程中，我们警告可能未初始化的。过程位于tree-ssa.c中，并由pass_early_warn_uninitialized和pass_late_warn_uninitialized定义。
死代码消除（Dead code elimination）
该过程扫描函数来寻找没有副作用，且结果没有被使用的语句。它不进行内存活跃分析，所以任何存储在内存中值都被认为是被使用的。该过程在整个优化处理中被运行多次。它位于tree-ssa-dce.c中，并由pass_dce来描述。
dominator优化（Dominator optimizations）
该过程执行平凡的基于dominator的复制和常量传播，表达式简化，以及跳转线程化。它在整个优化处理中被运行多次。它位于tree-ssa-dom.c中，并由pass_dominator来描述。pass_dominator.
单用变量向前传播（Forward propagation of single-use variables）
该过程尝试移除冗余计算，通过将只使用一次的变量替换为使用它们的表达式，并查看是否得到的结果可以被简化。它位于tree-ssa-forwprop.c中，并由pass_forwprop来描述。
复制重名命（Copy Renaming）
该过程尝试改变涉及复制操作的编译器临时对象的名字，例如SSA->normal。当编译器临时对象是用户变量复制时，它还将编译器临时对象重命名为用户变量，使得可以更好的使用用户符号。它位于tree-ssa-copyrename.c中，并由pass_copyrename来描述。
PHI节点优化（PHI node optimizations）
该过程识别可以被表示为条件表达式的PHI输入，并将它们重写成线形的代码。它位于tree-ssa-phiopt.c中，并由pass_phiopt来描述。
可能别名优化（May-alias optimization）
该过程执行一个流敏感基于SSA指向的分析。所得的may-alias, must-alias和escape分析信息用来将变量从内存中可寻址的对象提升为可以被重命名为SSA形式的无别名变量。我们还为非可命名的聚合体更新VDEF/VUSE内存标记，使得可以获得较少的错误。过程位于tree-ssa-alias.c中，并由pass_may_alias来描述。
进程间的指向信息位于tree-ssa-structalias.c中，并由pass_ipa_pta来描述。
Profiling
该过程重写函数，用于搜集运行时块和评估profiling数据。这些数据可以反馈给随后的编译器运行，这样就可以进行基于预期执行频率的优化。过程位于predict.c中，并由pass_profile来描述。
复数算术运算下降（Lower complex arithmetic）
该过程将复数算术运算重写为各部分的标量算术运算。过程位于tree-complex.c中，并由pass_lower_complex来描述。
聚合体标量替换（Scalar replacement of aggregates）
该过程将适当的非别名局部聚合体变量重写为一个标量集合。所得的标量变量被重写成SSA形式，这样就允许后面的优化过程来做更好的工作。过程位于tree-sra.c中，并由pass_sra来描述。
死存储消除（Dead store elimination）
该过程消除死存储，即存储到内存中，而该内存被随后的另一个存储操作重新写入，并且之间没有加载操作。过程位于tree-ssa-dse.c中，并由pass_dse来描述。
尾递归消除（Tail recursion elimination）
该过程将所有的尾递归转换到一个循环中。它位于tree-tailcall.c中，并由pass_tail_recursion来描述。
向前存储移动（Forward store motion）
described by pass_sink_code. 该过程将存储和赋值操作下沉到流图中接近它的使用点。过程位于tree-ssa-sink.c中，并由pass_sink_code来描述。
部分冗余消除（Partial redundancy elimination）
该过程消除部分冗余计算，同时执行加载移动。过程位于tree-ssa-pre.c中，并由pass_pre来描述。
如果设置了-funsafe-math-optimizations，则在部分冗余消除前，GCC尝试通过倒数方式将除法转换为乘法。过程位于tree-ssa-math-opts.c中，并由pass_cse_reciprocal来描述。
完全冗余消除（Full redundancy elimination）
这是一个较简单的PRE形式，只消除在所有路径上产生的冗余。它位于tree-ssa-pre.c中，并由pass_fre来描述。
循环优化（Loop optimization）
该过程的主驱动程序位于tree-ssa-loop.c中，并且由pass_loop来描述。
该过程执行的优化为：
循环不变量移动。该过程只移动在rtl级难以处理的不变量（像函数调用这样的操作被展开成普通的insns序列）。使用-funswitch-loops时，它还将不变的条件操作数移到循环外面，使得我们能够在循环外提过程中只需要进行平凡不变量分析。该过程还包括存储移动。该过程在tree-ssa-loop-im.c中实现。
正规归纳变量创建。该过程为循环迭代次数创建一个简单计数器，并使用它来替换循环的退出条件，以用于当一个复杂的分析需要确定迭代次数的时候。之后的优化便可以容易的确定迭代次数。该过程在tree-ssa-loop-ivcanon.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中的各种函数。
向量化。该过程将循环由标量类型操作转换为向量类型操作。跨越循环迭代的数据并行被利用，将数据元素从连续的迭代中组合成一个向量，对它们并行的操作。取决于可用的目标机的支持，循环在概念上按照因子VF（vectorization factor）被展开。
自动并行化。该过程将循环迭代空间拆分到几个线程来运行。该过程在tree-parloops.c中实现。
Graphite is a loop transformation framework based on the polyhedral model. Graphite stands for Gimple Represented as Polyhedra. The internals of this infrastructure are documented in http://gcc.gnu.org/wiki/Graphite. The passes working on this representation are implemented in the various graphite-* files.
用于向量化的Tree级if转换（Tree level if-conversion for vectorizer）
该过程对简单的循环应用if转换，以助于向量化。我们识别可以if转换的循环，并将基本块合并到一个大块中。想法是将循环表现为这样的形式，使得向量化能够对语句和可用的向量操作进行一一映射。该patch在GIMPLE级重新引入了COND_EXPR。该过程位于tree-if-conv.c中，并由pass_if_conversion来描述。
条件常量传播（Conditional constant propagation）
该过程松弛一个点阵值用于识别那些即使在条件分支中也肯定是常数的。该过程位于tree-ssa-ccp.c中，并由pass_ccp来描述。
一个相关的工作于内存加载和存储，而不只是寄存器值的过程，位于tree-ssa-ccp.c中，并由pass_store_ccp来描述。
条件复制传播（Conditional copy propagation）
这类似于常量传播，不过点阵值是与“copy-of”相关的。它消除代码中的冗余复制。该过程位于tree-ssa-copy.c中，并由pass_copy_prop来描述。
一个相关的工作于内存复制而不只是寄存器复制的过程，位于tree-ssa-copy.c中，并由pass_store_copy_prop来描述。
值范围传播（Value range propagation）
该转换类似于常量传播，只不过它是传播已知值的范围，而不是传播单个常数值。该实现基于Patterson的范围传播算法（Accurate Static Branch Prediction by Value Range Propagation, J. R. C. Patterson, PLDI '95）。相对于Patterson的算法，该实现没有传播分支可能性，也没有对SSA名使用多个范围。这意味着现在的实现不能用于分支预测（虽然并不难实现）。该过程位于tree-vrp.c中，并由pass_vrp来描述。
折叠built-in函数（Folding built-in functions）
该过程适当的简化built-in函数，使用常量参数或者可推算出的字符串长度。它位于tree-ssa-ccp.c中，并由pass_fold_builtins来描述。
拆分临界边（Split critical edges）
该过程识别出临界边，并插入空基本块来将其转换为非临界的。该过程位于tree-cfg.c，并由pass_split_crit_edges描述。
控制依赖死代码消除（Control dependence dead code elimination）
该过程是死代码消除的较强形式，能够消除不必要的控制流程语句。它位于tree-ssa-dce.c中，并由pass_cd_dce来描述。
尾调用消除（Tail call elimination）
该过程识别可以被重写为跳转的函数调用。这里没有进行实际的代码转换，不过却解决了数据流和控制流的问题。代码转换需要目标机支持，因此被推迟到RTL级。同时，CALL_EXPR_TAILCALL被设置，以用来指示可能性。该过程位于tree-tailcall.c中，并且由pass_tail_calls来描述。RTL转换由calls.c中的fixup_tail_calls来处理。
对函数没有返回值的警告（Warn for function return without value）
对于非void型的函数，该过程定位没有指定一个值的返回语句，并产生一个警告。这样的语句可能是在函数结束处。该过程在最后运行，这样我们能够更多可能的去检验这些语句是不可达的。其位于tree-cfg.c中，并由pass_warn_function_return来描述。
Mudflap语句注解（Mudflap statement annotation）
如果启用了mudflap，我们便重写一些内存访问代码以确保内存访问是正确的。特别的，涉及到指针废除的表达式（INDIRECT_REF, ARRARY_REF等等）被替代为检查选择地址范围的代码，而不是mudflap运行时数据库的有效域。该检查包括一个内联的对直接映射缓存的查找，基于对指针值的shift/mask操作，和对运行时的回滚函数调用。该过程位于tree-mudflap.c中，并由pass_mudflap_2来描述。
离开静态单赋值形式（Leave static single assignment form）
该过程重写函数使得其处于正常形式。同时，我们尽可能的消去单一使用的临时对象，这样中间语言就不再是GIMPLE了，而是GENERIC。该过程位于tree-outof-ssa.c中，并且由pass_del_ssa来描述。
合并PHI节点（Merge PHI nodes that feed into one another）
这是CFG清除过程的一部分。它试图将PHI节点从前部CFG块合并到另一个带有PHI节点的块。该过程位于tree-cfgcleanup.c中，并由pass_merge_phi来描述。
返回值优化（Return value optimization）
如果函数总是返回同一局部变量，并且那个局部变量是一个聚合类型，则变量将由函数返回值来替换（即函数的DECL_RESULT）。这相当于作用于GIMPLE的C++命名返回值优化。该过程位于tree-nrv.c中，并且由pass_nrv来描述。
返回槽优化（Return slot optimization）
如果函数返回一个内存对象，并且像var = foo()这样被调用，该过程尝试改变调用，使得var的地址传送给调用者，以避免一次额外的内存复制。该过程位于tree-nrv.c中，并由pass_return_slot来描述。
优化调用__builtin_object_size（Optimize calls to __builtin_object_size）
这是一个类似于CCP的传播过程，其试图移除对__builtin_object_size的调用，当对象的大小能够在编译时计算出的时候。该过程位于tree-object-size.c中，并有pass_object_sizes来描述。
循环不变量移动（Loop invariant motion）
该过程将昂贵的循环不变量计算移出循环。该过程位于tree-ssa-loop.c中，并由pass_lim来描述。
循环嵌套优化（Loop nest optimizations）
这是一类工作于循环嵌套的循环转换。它包括循环变换（loop interchange），scaling，skewing和逆转（reversal），并且它们用来配合。该过程位于tree-loop-linear.c中，并由pass_linear_transform来描述。
空循环移除（Removal of empty loops）
该过程移除不含代码的循环。该过程位于tree-ssa-loop-ivcanon.c中，并由pass_empty_loop来描述。
小循环展开（Unrolling of small loops）
该过程将迭代次数很少的循环完全展开。该过程位于tree-ssa-loop-ivcanon.c中，并由pass_complete_unroll来描述。
预测公约（Predictive commoning）
该过程使代码可以重用先前循环迭代的计算，特别是对内存的加载和存贮。该过程位于tree-predcom.c中，并由pass_predcom来描述。
数组预取（Array prefetching）
该过程为循环中的数组引用产生预提取指令。过程位于tree-ssa-loop-prefetch.c中，并由pass_loop_prefetch来描述。
重组（Reassociation）
该过程将算术表达式重写为可以进行优化的形式，例如冗余消除和向量化。过程位于tree-ssa-reassoc.c中，并由pass_reassoc来描述。
优化stdarg函数
该过程设法避免在stdarg函数入口处将寄存器参数保存到栈中。如果函数不使用任何va_start宏，则没有寄存器需要被保存。如果使用了va_start宏，va_list变量的使用范围不超出该函数，则只需要保存将在va_arg宏中使用的寄存器。例如，如果va_arg在函数中只用于整数类型，则不需要保存浮点寄存器。该过程位于tree-stdarg.c中，并由pass_stdarg来描述。