Next:RTL passes, Previous:Inter-procedural optimization passes, Up:Passes and Files of the Compiler [Contents][Index]
The following briefly describes the Tree optimization passes that arerun after gimplification and what source files they are located in.
If OpenMP generation (-fopenmp) is enabled, this pass lowersOpenMP constructs into GIMPLE.
Lowering of OpenMP constructs involves creating replacementexpressions for local variables that have been mapped using datasharing clauses, exposing the control flow of most synchronizationdirectives and adding region markers to facilitate the creation of thecontrol flow graph. The pass is located inomp-low.cc and isdescribed bypass_lower_omp.
If OpenMP generation (-fopenmp) is enabled, this pass expandsparallel regions into their own functions to be invoked by the threadlibrary. The pass is located inomp-low.cc and is described bypass_expand_omp.
This pass flattensif statements (COND_EXPR)and moves lexical bindings (BIND_EXPR) out of line. Afterthis pass, allif statements will have exactly twogotostatements in itsthen andelse arms. Lexical bindinginformation for each statement will be found inTREE_BLOCK ratherthan being inferred from its position under aBIND_EXPR. Thispass is found ingimple-low.cc and is described bypass_lower_cf.
This pass decomposes high-level exception handling constructs(TRY_FINALLY_EXPR andTRY_CATCH_EXPR) into a formthat explicitly represents the control flow involved. After thispass,lookup_stmt_eh_region will return a non-negativenumber for any statement that may have EH control flow semantics;examinetree_can_throw_internal ortree_can_throw_externalfor exact semantics. Exact control flow may be extracted fromforeach_reachable_handler. The EH region nesting tree is definedinexcept.h and built inexcept.cc. The lowering passitself is intree-eh.cc and is described bypass_lower_eh.
This pass decomposes a function into basic blocks and creates all ofthe edges that connect them. It is located intree-cfg.cc andis described bypass_build_cfg.
This pass rewrites the function such that it is in SSA form. Afterthis pass, allis_gimple_reg variables will be referenced bySSA_NAME, and all occurrences of other variables will beannotated withVDEFS andVUSES; PHI nodes will havebeen inserted as necessary for each basic block. This pass islocated intree-into-ssa.cc and is described bypass_build_ssa.
This pass scans the function for uses ofSSA_NAMEs thatare fed by default definition. For non-parameter variables, suchuses are uninitialized. The pass is run twice, before and afteroptimization (if turned on). In the first pass we only warn for uses that arepositively uninitialized; in the second pass we warn for uses thatare possibly uninitialized. The pass is located intree-ssa-uninit.ccand is defined bypass_early_warn_uninitialized andpass_late_warn_uninitialized.
This pass scans the function for statements without side effects whoseresult is unused. It does not do memory lifetime analysis, so any valuethat is stored in memory is considered used. The pass is run multipletimes throughout the optimization process. It is located intree-ssa-dce.cc and is described bypass_dce.
This pass performs trivial dominator-based copy and constant propagation,expression simplification, and jump threading. It is run multiple timesthroughout the optimization process. It is located intree-ssa-dom.ccand is described bypass_dominator.
This pass attempts to remove redundant computation by substitutingvariables that are used once into the expression that uses them andseeing if the result can be simplified. It is located intree-ssa-forwprop.cc and is described bypass_forwprop.
This pass recognizes forms of PHI inputs that can be represented asconditional expressions and rewrites them into straight line code.It is located intree-ssa-phiopt.cc and is described bypass_phiopt.
This pass performs a flow sensitive SSA-based points-to analysis.The resulting may-alias, must-alias, and escape analysis informationis used to promote variables from in-memory addressable objects tonon-aliased variables that can be renamed into SSA form. We alsoupdate theVDEF/VUSE memory tags for non-renameableaggregates so that we get fewer false kills. The pass is locatedintree-ssa-structalias.cc and is described bypass_may_alias.
Interprocedural points-to information is described bypass_ipa_pta.
This pass instruments the function in order to collect runtime blockand value profiling data. Such data may be fed back into the compileron a subsequent run so as to allow optimization based on expectedexecution frequencies. The pass is located intree-profile.cc andis described bypass_ipa_tree_profile.
This pass implements series of heuristics to guess propababilitiesof branches. The resulting predictions are turned into edge profileby propagating branches across the control flow graphs.The pass is located intree-profile.cc and is described bypass_profile.
This pass rewrites complex arithmetic operations into their componentscalar arithmetic operations. The pass is located intree-complex.ccand is described bypass_lower_complex.
This pass rewrites suitable non-aliased local aggregate variables intoa set of scalar variables. The resulting scalar variables arerewritten into SSA form, which allows subsequent optimization passesto do a significantly better job with them. The pass is located intree-sra.cc and is described bypass_sra.
This pass eliminates stores to memory that are subsequently overwrittenby another store, without any intervening loads. The pass is locatedintree-ssa-dse.cc and is described bypass_dse.
This pass transforms tail recursion into a loop. It is located intree-tailcall.cc and is described bypass_tail_recursion.
This pass sinks stores and assignments down the flowgraph closer to theiruse point. The pass is located intree-ssa-sink.cc and isdescribed bypass_sink_code.
This pass eliminates partially redundant computations, as well asperforming load motion. The pass is located intree-ssa-pre.ccand is described bypass_pre.
If-funsafe-math-optimizations is on, GCC tries to convertdivisions to multiplications by the reciprocal. The pass is locatedintree-ssa-math-opts.cc and is described bypass_cse_reciprocal.
This is a simpler form of PRE that only eliminates redundancies thatoccur on all paths. It is located intree-ssa-pre.cc anddescribed bypass_fre.
The main driver of the pass is placed intree-ssa-loop.ccand described bypass_loop.
The optimizations performed by this pass are:
Loop invariant motion. This pass moves only invariants thatwould be hard to handle on RTL level (function calls, operations that expand tonontrivial sequences of insns). With-funswitch-loops it also movesoperands of conditions that are invariant out of the loop, so that we can usejust trivial invariantness analysis in loop unswitching. The pass also includesstore motion. The pass is implemented intree-ssa-loop-im.cc.
Canonical induction variable creation. This pass creates a simple counterfor number of iterations of the loop and replaces the exit condition of theloop using it, in case when a complicated analysis is necessary to determinethe number of iterations. Later optimizations then may determine the numbereasily. The pass is implemented intree-ssa-loop-ivcanon.cc.
Induction variable optimizations. This pass performs standard inductionvariable optimizations, including strength reduction, induction variablemerging and induction variable elimination. The pass is implemented intree-ssa-loop-ivopts.cc.
Loop unswitching. This pass moves the conditional jumps that are invariantout of the loops. To achieve this, a duplicate of the loop is created foreach possible outcome of conditional jump(s). The pass is implemented intree-ssa-loop-unswitch.cc.
Loop splitting. If a loop contains a conditional statement that isalways true for one part of the iteration space and false for the otherthis pass splits the loop into two, one dealing with one side the otheronly with the other, thereby removing one inner-loop conditional. Thepass is implemented intree-ssa-loop-split.cc.
The optimizations also use various utility functions contained intree-ssa-loop-manip.cc,cfgloop.cc,cfgloopanal.cc andcfgloopmanip.cc.
Vectorization. This pass transforms loops to operate on vector typesinstead of scalar types. Data parallelism across loop iterations is exploitedto group data elements from consecutive iterations into a vector and operateon them in parallel. Depending on available target support the loop isconceptually unrolled by a factorVF (vectorization factor), which isthe number of elements operated upon in parallel in each iteration, and theVF copies of each scalar operation are fused to form a vector operation.Additional loop transformations such as peeling and versioning may take placeto align the number of iterations, and to align the memory accesses in theloop.The pass is implemented intree-vectorizer.cc (the main driver),tree-vect-loop.cc andtree-vect-loop-manip.cc (loop specific partsand general loop utilities),tree-vect-slp (loop-aware SLPfunctionality),tree-vect-stmts.cc,tree-vect-data-refs.cc andtree-vect-slp-patterns.cc containing the SLP pattern matcher.Analysis of data references is intree-data-ref.cc.
SLP Vectorization. This pass performs vectorization of straight-line code. Thepass is implemented intree-vectorizer.cc (the main driver),tree-vect-slp.cc,tree-vect-stmts.cc andtree-vect-data-refs.cc.
Autoparallelization. This pass splits the loop iteration space to runinto several threads. The pass is implemented intree-parloops.cc.
Graphite is a loop transformation framework based on the polyhedralmodel. Graphite stands for Gimple Represented as Polyhedra. Theinternals of this infrastructure are documented inhttps://gcc.gnu.org/wiki/Graphite. The passes working onthis representation are implemented in the variousgraphite-*files.
This pass applies if-conversion to simple loops to help vectorizer.We identify if convertible loops, if-convert statements and mergebasic blocks in one big block. The idea is to present loop in suchform so that vectorizer can have one to one mapping between statementsand available vector operations. This pass is located intree-if-conv.cc and is described bypass_if_conversion.
This pass relaxes a lattice of values in order to identify thosethat must be constant even in the presence of conditional branches.The pass is located intree-ssa-ccp.cc and is describedbypass_ccp.
This is similar to constant propagation but the lattice of values isthe “copy-of” relation. It eliminates redundant copies from thecode. The pass is located intree-ssa-copy.cc and described bypass_copy_prop.
This transformation is similar to constant propagation butinstead of propagating single constant values, it propagatesknown value ranges. The implementation is based on Patterson’srange propagation algorithm (Accurate Static Branch Prediction byValue Range Propagation, J. R. C. Patterson, PLDI ’95). Incontrast to Patterson’s algorithm, this implementation does notpropagate branch probabilities nor it uses more than a singlerange per SSA name. This means that the current implementationcannot be used for branch prediction (though adapting it wouldnot be difficult). The pass is located intree-vrp.cc and isdescribed bypass_vrp.
This pass identifies critical edges and inserts empty basic blockssuch that the edge is no longer critical. The pass is located intree-cfg.cc and is described bypass_split_crit_edges.
This pass is a stronger form of dead code elimination that caneliminate unnecessary control flow statements. It is locatedintree-ssa-dce.cc and is described bypass_cd_dce.
This pass identifies function calls that may be rewritten intojumps. No code transformation is actually applied here, but thedata and control flow problem is solved. The code transformationrequires target support, and so is delayed until RTL. In themeantimeCALL_EXPR_TAILCALL is set indicating the possibility.The pass is located intree-tailcall.cc and is described bypass_tail_calls. The RTL transformation is handled byfixup_tail_calls incalls.cc.
For non-void functions, this pass locates return statements that donot specify a value and issues a warning. Such a statement may havebeen injected by falling off the end of the function. This pass isrun last so that we have as much time as possible to prove that thestatement is not reachable. It is located intree-cfg.cc andis described bypass_warn_function_return.
This is part of the CFG cleanup passes. It attempts to join PHI nodesfrom a forwarder CFG block into another block with PHI nodes. Thepass is located intree-cfgcleanup.cc and is described bypass_merge_phi.
If a function always returns the same local variable, and that localvariable is an aggregate type, then the variable is replaced with thereturn value for the function (i.e., the function’s DECL_RESULT). Thisis equivalent to the C++ named return value optimization applied toGIMPLE. The pass is located intree-nrv.cc and is described bypass_nrv.
If a function returns a memory object and is called asvar =foo(), this pass tries to change the call so that the address ofvar is sent to the caller to avoid an extra memory copy. Thispass is located intree-nrv.cc and is described bypass_return_slot.
__builtin_object_size or__builtin_dynamic_object_sizeThis is a propagation pass similar to CCP that tries to remove calls to__builtin_object_size when the upper or lower bound for the sizeof the object can be computed at compile-time. It also tries to replacecalls to__builtin_dynamic_object_size with an expression thatevaluates the upper or lower bound for the size of the object. Thispass is located intree-object-size.cc and is described bypass_object_sizes.
This pass removes expensive loop-invariant computations out of loops.The pass is located intree-ssa-loop.cc and described bypass_lim.
This is a family of loop transformations that works on loop nests. Itincludes loop interchange, scaling, skewing and reversal and they areall geared to the optimization of data locality in array traversalsand the removal of dependencies that hamper optimizations such as loopparallelization and vectorization. The pass is located inthegraphile-*.cc files and described bypass_graphite.
This pass completely unrolls loops with few iterations. The passis located intree-ssa-loop-ivcanon.cc and described bypass_complete_unroll.
This pass makes the code reuse the computations from the previousiterations of the loops, especially loads and stores to memory.It does so by storing the values of these computations to a bankof temporary variables that are rotated at the end of loop. To avoidthe need for this rotation, the loop is then unrolled and the copiesof the loop body are rewritten to use the appropriate version ofthe temporary variable. This pass is located intree-predcom.ccand described bypass_predcom.
This pass issues prefetch instructions for array references insideloops. The pass is located intree-ssa-loop-prefetch.cc anddescribed bypass_loop_prefetch.
This pass rewrites arithmetic expressions to enable optimizations thatoperate on them, like redundancy elimination and vectorization. Thepass is located intree-ssa-reassoc.cc and described bypass_reassoc.
stdarg functionsThis pass tries to avoid the saving of register arguments into thestack on entry tostdarg functions. If the function doesn’tuse anyva_start macros, no registers need to be saved. Ifva_start macros are used, theva_list variables don’tescape the function, it is only necessary to save registers that willbe used inva_arg macros. For instance, ifva_arg isonly used with integral types in the function, floating pointregisters don’t need to be saved. This pass is located intree-stdarg.cc and described bypass_stdarg.
Next:RTL passes, Previous:Inter-procedural optimization passes, Up:Passes and Files of the Compiler [Contents][Index]