Tree SSA passes (GNU Compiler Collection (GCC) Internals) (original) (raw)

The following briefly describes the Tree optimization passes that are run after gimplification and what source files they are located in.

• OpenMP lowering
  If OpenMP generation (-fopenmp) is enabled, this pass lowers OpenMP constructs into GIMPLE.
  Lowering of OpenMP constructs involves creating replacement expressions for local variables that have been mapped using data sharing clauses, exposing the control flow of most synchronization directives and adding region markers to facilitate the creation of the control flow graph. The pass is located in omp-low.cc and is described by pass_lower_omp.
• OpenMP expansion
  If OpenMP generation (-fopenmp) is enabled, this pass expands parallel regions into their own functions to be invoked by the thread library. The pass is located in omp-low.cc and is described bypass_expand_omp.
• Lower control flow
  This pass flattens if statements (COND_EXPR) and moves lexical bindings (BIND_EXPR) out of line. After this pass, all if statements will have exactly two gotostatements in its then and else arms. Lexical binding information for each statement will be found in TREE_BLOCK rather than being inferred from its position under a BIND_EXPR. This pass is found in gimple-low.cc and is described bypass_lower_cf.
• Lower exception handling control flow
  This pass decomposes high-level exception handling constructs (TRY_FINALLY_EXPR and TRY_CATCH_EXPR) into a form that explicitly represents the control flow involved. After this pass, lookup_stmt_eh_region will return a non-negative number for any statement that may have EH control flow semantics; examine tree_can_throw_internal or tree_can_throw_externalfor exact semantics. Exact control flow may be extracted fromforeach_reachable_handler. The EH region nesting tree is defined in except.h and built in except.cc. The lowering pass itself is in tree-eh.cc and is described by pass_lower_eh.
• Build the control flow graph
  This pass decomposes a function into basic blocks and creates all of the edges that connect them. It is located in tree-cfg.cc and is described by pass_build_cfg.
• Enter static single assignment form
  This pass rewrites the function such that it is in SSA form. After this pass, all is_gimple_reg variables will be referenced bySSA_NAME, and all occurrences of other variables will be annotated with VDEFS and VUSES; PHI nodes will have been inserted as necessary for each basic block. This pass is located in tree-into-ssa.cc and is described by pass_build_ssa.
• Warn for uninitialized variables
  This pass scans the function for uses of SSA_NAMEs that are fed by default definition. For non-parameter variables, such uses are uninitialized. The pass is run twice, before and after optimization (if turned on). In the first pass we only warn for uses that are positively uninitialized; in the second pass we warn for uses that are possibly uninitialized. The pass is located in tree-ssa-uninit.ccand is defined by pass_early_warn_uninitialized andpass_late_warn_uninitialized.
• Dead code elimination
  This pass scans the function for statements without side effects whose result is unused. It does not do memory lifetime analysis, so any value that is stored in memory is considered used. The pass is run multiple times throughout the optimization process. It is located intree-ssa-dce.cc and is described by pass_dce.
• Dominator optimizations
  This pass performs trivial dominator-based copy and constant propagation, expression simplification, and jump threading. It is run multiple times throughout the optimization process. It is located in tree-ssa-dom.ccand is described by pass_dominator.
• Forward propagation of single-use variables
  This pass attempts to remove redundant computation by substituting variables that are used once into the expression that uses them and seeing if the result can be simplified. It is located intree-ssa-forwprop.cc and is described by pass_forwprop.
• PHI node optimizations
  This pass recognizes forms of PHI inputs that can be represented as conditional expressions and rewrites them into straight line code. It is located in tree-ssa-phiopt.cc and is described bypass_phiopt.
• May-alias optimization
  This pass performs a flow sensitive SSA-based points-to analysis. The resulting may-alias, must-alias, and escape analysis information is used to promote variables from in-memory addressable objects to non-aliased variables that can be renamed into SSA form. We also update the VDEF/VUSE memory tags for non-renameable aggregates so that we get fewer false kills. The pass is located in tree-ssa-structalias.cc and is described by pass_may_alias.
  Interprocedural points-to information is described by pass_ipa_pta.
• Profiling
  This pass instruments the function in order to collect runtime block and value profiling data. Such data may be fed back into the compiler on a subsequent run so as to allow optimization based on expected execution frequencies. The pass is located in tree-profile.cc and is described by pass_ipa_tree_profile.
• Static profile estimation
  This pass implements series of heuristics to guess propababilities of branches. The resulting predictions are turned into edge profile by propagating branches across the control flow graphs. The pass is located in tree-profile.cc and is described bypass_profile.
• Lower complex arithmetic
  This pass rewrites complex arithmetic operations into their component scalar arithmetic operations. The pass is located in tree-complex.ccand is described by pass_lower_complex.
• Scalar replacement of aggregates
  This pass rewrites suitable non-aliased local aggregate variables into a set of scalar variables. The resulting scalar variables are rewritten into SSA form, which allows subsequent optimization passes to do a significantly better job with them. The pass is located intree-sra.cc and is described by pass_sra.
• Dead store elimination
  This pass eliminates stores to memory that are subsequently overwritten by another store, without any intervening loads. The pass is located in tree-ssa-dse.cc and is described by pass_dse.
• Tail recursion elimination
  This pass transforms tail recursion into a loop. It is located intree-tailcall.cc and is described by pass_tail_recursion.
• Forward store motion
  This pass sinks stores and assignments down the flowgraph closer to their use point. The pass is located in tree-ssa-sink.cc and is described by pass_sink_code.
• Partial redundancy elimination
  This pass eliminates partially redundant computations, as well as performing load motion. The pass is located in tree-ssa-pre.ccand is described by pass_pre.
• CSE of reciprocals
  If -funsafe-math-optimizations is on, GCC tries to convert divisions to multiplications by the reciprocal. The pass is located in tree-ssa-math-opts.cc and is described bypass_cse_reciprocal.
• Full redundancy elimination
  This is a simpler form of PRE that only eliminates redundancies that occur on all paths. It is located in tree-ssa-pre.cc and described by pass_fre.
• Loop optimization
  The main driver of the pass is placed in tree-ssa-loop.ccand described by pass_loop.
  The optimizations performed by this pass are:
  Loop invariant motion. This pass moves only invariants that would be hard to handle on RTL level (function calls, operations that expand to nontrivial sequences of insns). With -funswitch-loops it also moves operands of conditions that are invariant out of the loop, so that we can use just trivial invariantness analysis in loop unswitching. The pass also includes store motion. The pass is implemented in tree-ssa-loop-im.cc.
  Canonical induction variable creation. This pass creates a simple counter for number of iterations of the loop and replaces the exit condition of the loop using it, in case when a complicated analysis is necessary to determine the number of iterations. Later optimizations then may determine the number easily. The pass is implemented in tree-ssa-loop-ivcanon.cc.
  Induction variable optimizations. This pass performs standard induction variable optimizations, including strength reduction, induction variable merging and induction variable elimination. The pass is implemented intree-ssa-loop-ivopts.cc.
  Loop unswitching. This pass moves the conditional jumps that are invariant out of the loops. To achieve this, a duplicate of the loop is created for each 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 is always true for one part of the iteration space and false for the other this pass splits the loop into two, one dealing with one side the other only with the other, thereby removing one inner-loop conditional. The pass is implemented in tree-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 types instead of scalar types. Data parallelism across loop iterations is exploited to group data elements from consecutive iterations into a vector and operate on them in parallel. Depending on available target support the loop is conceptually unrolled by a factor VF (vectorization factor), which is the 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 place to align the number of iterations, and to align the memory accesses in the loop. The pass is implemented in tree-vectorizer.cc (the main driver),tree-vect-loop.cc and tree-vect-loop-manip.cc (loop specific parts and general loop utilities), tree-vect-slp (loop-aware SLP functionality), tree-vect-stmts.cc, tree-vect-data-refs.cc andtree-vect-slp-patterns.cc containing the SLP pattern matcher. Analysis of data references is in tree-data-ref.cc.
  SLP Vectorization. This pass performs vectorization of straight-line code. The pass is implemented in tree-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 run into several threads. The pass is implemented in tree-parloops.cc.
  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 inhttps://gcc.gnu.org/wiki/Graphite. The passes working on this representation are implemented in the various graphite-*files.
• Tree level if-conversion for vectorizer
  This pass applies if-conversion to simple loops to help vectorizer. We identify if convertible loops, if-convert statements and merge basic blocks in one big block. The idea is to present loop in such form so that vectorizer can have one to one mapping between statements and available vector operations. This pass is located intree-if-conv.cc and is described by pass_if_conversion.
• Conditional constant propagation
  This pass relaxes a lattice of values in order to identify those that must be constant even in the presence of conditional branches. The pass is located in tree-ssa-ccp.cc and is described by pass_ccp.
• Conditional copy propagation
  This is similar to constant propagation but the lattice of values is the “copy-of” relation. It eliminates redundant copies from the code. The pass is located in tree-ssa-copy.cc and described bypass_copy_prop.
• Value range propagation
  This transformation is similar to constant propagation but instead of propagating single constant values, it propagates known value ranges. The implementation is based on Patterson’s range propagation algorithm (Accurate Static Branch Prediction by Value Range Propagation, J. R. C. Patterson, PLDI ’95). In contrast to Patterson’s algorithm, this implementation does not propagate branch probabilities nor it uses more than a single range per SSA name. This means that the current implementation cannot be used for branch prediction (though adapting it would not be difficult). The pass is located in tree-vrp.cc and is described by pass_vrp.
• Folding built-in functions
  This pass simplifies built-in functions, as applicable, with constant arguments or with inferable string lengths. It is located intree-ssa-ccp.cc and is described by pass_fold_builtins.
• Split critical edges
  This pass identifies critical edges and inserts empty basic blocks such that the edge is no longer critical. The pass is located intree-cfg.cc and is described by pass_split_crit_edges.
• Control dependence dead code elimination
  This pass is a stronger form of dead code elimination that can eliminate unnecessary control flow statements. It is located in tree-ssa-dce.cc and is described by pass_cd_dce.
• Tail call elimination
  This pass identifies function calls that may be rewritten into jumps. No code transformation is actually applied here, but the data and control flow problem is solved. The code transformation requires target support, and so is delayed until RTL. In the meantime CALL_EXPR_TAILCALL is set indicating the possibility. The pass is located in tree-tailcall.cc and is described bypass_tail_calls. The RTL transformation is handled byfixup_tail_calls in calls.cc.
• Warn for function return without value
  For non-void functions, this pass locates return statements that do not specify a value and issues a warning. Such a statement may have been injected by falling off the end of the function. This pass is run last so that we have as much time as possible to prove that the statement is not reachable. It is located in tree-cfg.cc and is described by pass_warn_function_return.
• Merge PHI nodes that feed into one another
  This is part of the CFG cleanup passes. It attempts to join PHI nodes from a forwarder CFG block into another block with PHI nodes. The pass is located in tree-cfgcleanup.cc and is described bypass_merge_phi.
• Return value optimization
  If a function always returns the same local variable, and that local variable is an aggregate type, then the variable is replaced with the return value for the function (i.e., the function’s DECL_RESULT). This is equivalent to the C++ named return value optimization applied to GIMPLE. The pass is located in tree-nrv.cc and is described bypass_nrv.
• Return slot optimization
  If a function returns a memory object and is called as var = foo(), this pass tries to change the call so that the address ofvar is sent to the caller to avoid an extra memory copy. This pass is located in tree-nrv.cc and is described bypass_return_slot.
• Optimize calls to __builtin_object_size or__builtin_dynamic_object_size
  This is a propagation pass similar to CCP that tries to remove calls to__builtin_object_size when the upper or lower bound for the size of the object can be computed at compile-time. It also tries to replace calls to __builtin_dynamic_object_size with an expression that evaluates the upper or lower bound for the size of the object. This pass is located in tree-object-size.cc and is described bypass_object_sizes.
• Loop invariant motion
  This pass removes expensive loop-invariant computations out of loops. The pass is located in tree-ssa-loop.cc and described bypass_lim.
• Loop nest optimizations
  This is a family of loop transformations that works on loop nests. It includes loop interchange, scaling, skewing and reversal and they are all geared to the optimization of data locality in array traversals and the removal of dependencies that hamper optimizations such as loop parallelization and vectorization. The pass is located in the graphile-*.cc files and described bypass_graphite.
• Unrolling of small loops
  This pass completely unrolls loops with few iterations. The pass is located in tree-ssa-loop-ivcanon.cc and described bypass_complete_unroll.
• Predictive commoning
  This pass makes the code reuse the computations from the previous iterations of the loops, especially loads and stores to memory. It does so by storing the values of these computations to a bank of temporary variables that are rotated at the end of loop. To avoid the need for this rotation, the loop is then unrolled and the copies of the loop body are rewritten to use the appropriate version of the temporary variable. This pass is located in tree-predcom.ccand described by pass_predcom.
• Array prefetching
  This pass issues prefetch instructions for array references inside loops. The pass is located in tree-ssa-loop-prefetch.cc and described by pass_loop_prefetch.
• Reassociation
  This pass rewrites arithmetic expressions to enable optimizations that operate on them, like redundancy elimination and vectorization. The pass is located in tree-ssa-reassoc.cc and described bypass_reassoc.
• Optimization of stdarg functions
  This pass tries to avoid the saving of register arguments into the stack on entry to stdarg functions. If the function doesn’t use any va_start macros, no registers need to be saved. Ifva_start macros are used, the va_list variables don’t escape the function, it is only necessary to save registers that will be used in va_arg macros. For instance, if va_arg is only used with integral types in the function, floating point registers don’t need to be saved. This pass is located intree-stdarg.cc and described by pass_stdarg.