Passes and Files of the Compiler
********************************

This chapter is dedicated to giving an overview of the optimization and code generation passes of the compiler.  In the process, it describes some of the language front end interface, though this description is no where near complete.

Parsing pass
============

The language front end is invoked only once, via lang_hooks.parse_file, to parse the entire input.  The language front end may use any intermediate language representation deemed appropriate.  The C front end uses GENERIC trees (CROSSREF), plus a double handful of language specific tree codes defined in c-common.def.  The Fortran front end uses a completely different private representation.

At some point the front end must translate the representation used in the front end to a representation understood by the language-independent portions of the compiler.  Current practice takes one of two forms. The C front end manually invokes the gimplifier (CROSSREF) on each function, and uses the gimplifier callbacks to convert the language-specific tree nodes directly to GIMPLE (CROSSREF) before passing the function off to be compiled. The Fortran front end converts from a private representation to GENERIC, which is later lowered to GIMPLE when the function is compiled.  Which route to choose probably depends on how well GENERIC (plus extensions) can be made to match up with the source language and necessary parsing data structures.

BUG: Gimplification must occur before nested function lowering, and nested function lowering must be done by the front end before passing the data off to cgraph.

TODO: Cgraph should control nested function lowering.  It would only be invoked when it is certain that the outer-most function is used.

TODO: Cgraph needs a gimplify_function callback.  It should be invoked when (1) it is certain that the function is used, (2) warning flags specified by the user require some amount of compilation in order to honor, (3) the language indicates that semantic analysis is not complete until gimplification occurs. Hum... this sounds overly complicated.  Perhaps we should just have the front end gimplify always; in most cases it's only one function call.

The front end needs to pass all function definitions and top level declarations off to the middle-end so that they can be compiled and emitted to the object file.  For a simple procedural language, it is usually most convenient to do this as each top level declaration or definition is seen.  There is also a distinction to be made between generating functional code and generating complete debug information. The only thing that is absolutely required for functional code is that function and data definitions be passed to the middle-end.  For complete debug information, function, data and type declarations should all be passed as well.

In any case, the front end needs each complete top-level function or data declaration, and each data definition should be passed to rest_of_decl_compilation.  Each complete type definition should be passed to rest_of_type_compilation.  Each function definition should be passed to cgraph_finalize_function.

TODO: I know rest_of_compilation currently has all sorts of RTL generation semantics.  I plan to move all code generation bits (both Tree and RTL) to compile_function.  Should we hide cgraph from the front ends and move back to rest_of_compilation as the official interface?  Possibly we should rename all three interfaces such that the names match in some meaningful way and that is more descriptive than "rest_of".

The middle-end will, at its option, emit the function and data definitions immediately or queue them for later processing.

Gimplification pass
===================

Gimplification is a whimsical term for the process of converting the intermediate representation of a function into the GIMPLE language (CROSSREF).  The term stuck, and so words like ``gimplification'', ``gimplify'', ``gimplifier'' and the like are sprinkled throughout this section of code.

While a front end may certainly choose to generate GIMPLE directly if it chooses, this can be a moderately complex process unless the intermediate language used by the front end is already fairly simple. Usually it is easier to generate GENERIC trees plus extensions and let the language-independent gimplifier do most of the work.

The main entry point to this pass is gimplify_function_tree located in gimplify.c.  From here we process the entire function gimplifying each statement in turn.  The main workhorse for this pass is gimplify_expr.  Approximately everything passes through here at least once, and it is from here that we invoke the lang_hooks.gimplify_expr callback.

The callback should examine the expression in question and return GS_UNHANDLED if the expression is not a language specific construct that requires attention.  Otherwise it should alter the expression in some way to such that forward progress is made toward producing valid GIMPLE.  If the callback is certain that the transformation is complete and the expression is valid GIMPLE, it should return GS_ALL_DONE.  Otherwise it should return GS_OK, which will cause the expression to be processed again. If the callback encounters an error during the transformation (because the front end is relying on the gimplification process to finish semantic checks), it should return GS_ERROR.

Pass manager
============

The pass manager is located in passes.c, tree-optimize.c and tree-pass.h. Its job is to run all of the individual passes in the correct order, and take care of standard bookkeeping that applies to every pass.

The theory of operation is that each pass defines a structure that represents everything we need to know about that pass---when it should be run, how it should be run, what intermediate language form or on-the-side data structures it needs.  We register the pass to be run in some particular order, and the pass manager arranges for everything to happen in the correct order.

The actuality doesn't completely live up to the theory at present. Command-line switches and timevar_id_t enumerations must still be defined elsewhere.  The pass manager validates constraints but does not attempt to (re-)generate data structures or lower intermediate language form based on the requirements of the next pass.  Nevertheless, what is present is useful, and a far sight better than nothing at all.

Each pass may have its own dump file (for GCC debugging purposes). Passes without any names, or with a name starting with a star, do not dump anything.

TODO: describe the global variables set up by the pass manager, and a brief description of how a new pass should use it. I need to look at what info RTL passes use first...

Tree SSA passes
===============

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

  * Remove useless statements

     This pass is an extremely simple sweep across the gimple code in which we identify obviously dead code and remove it.  Here we do things like simplify if statements with constant conditions, remove exception handling constructs surrounding code that obviously cannot throw, remove lexical bindings that contain no variables, and other assorted simplistic cleanups.  The idea is to get rid of the obvious stuff quickly rather than wait until later when it's more work to get rid of it.  This pass is located in tree-cfg.c and described by pass_remove_useless_stmts.

  * Mudflap declaration registration

     If mudflap (see -fmudflap -fmudflapth -fmudflapir (Using the GNU Compiler Collection (GCC))) is enabled, we generate code to register some variable declarations with the mudflap runtime.  Specifically, the runtime tracks the lifetimes of those variable declarations that have their addresses taken, or whose bounds are unknown at compile time (extern).  This pass generates new exception handling constructs (try/finally), and so must run before those are lowered.  In addition, the pass enqueues declarations of static variables whose lifetimes extend to the entire program.  The pass is located in tree-mudflap.c and is described by pass_mudflap_1.

  * 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.c 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.c and is described by pass_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 goto statements 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.c and is described by pass_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_external for exact semantics.  Exact control flow may be extracted from foreach_reachable_handler.  The EH region nesting tree is defined in except.h and built in except.c.  The lowering pass itself is in tree-eh.c 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.c and is described by pass_build_cfg.

  * Find all referenced variables

     This pass walks the entire function and collects an array of all variables referenced in the function, referenced_vars.  The index at which a variable is found in the array is used as a UID for the variable within this function.  This data is needed by the SSA rewriting routines.  The pass is located in tree-dfa.c and is described by pass_referenced_vars.

  * 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 by SSA_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-ssa.c 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.c and is defined by pass_early_warn_uninitialized and pass_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 life 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 in tree-ssa-dce.c 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 it located in tree-ssa-dom.c and 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 in tree-ssa-forwprop.c and is described by pass_forwprop.

  * Copy Renaming

     This pass attempts to change the name of compiler temporaries involved in copy operations such that SSA->normal can coalesce the copy away.  When compiler temporaries are copies of user variables, it also renames the compiler temporary to the user variable resulting in better use of user symbols.  It is located in tree-ssa-copyrename.c and is described by pass_copyrename.

  * 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.c and is described by pass_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-alias.c and is described by pass_may_alias.

     Interprocedural points-to information is located in tree-ssa-structalias.c and described by pass_ipa_pta.

  * Profiling

     This pass rewrites 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 predict.c and is described by pass_profile.

  * Lower complex arithmetic

     This pass rewrites complex arithmetic operations into their component scalar arithmetic operations.  The pass is located in tree-complex.c and 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 in tree-sra.c 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.c and is described by pass_dse.

  * Tail recursion elimination

     This pass transforms tail recursion into a loop.  It is located in tree-tailcall.c 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.c 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.c and is described by pass_pre.

     Just before partial redundancy elimination, 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.c and is described by pass_cse_reciprocal.

  * Full redundancy elimination

     This is a simpler form of PRE that only eliminates redundancies that occur an all paths.  It is located in tree-ssa-pre.c and described by pass_fre.

  * Loop optimization

     The main driver of the pass is placed in tree-ssa-loop.c and 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.c.

     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.c.

     Induction variable optimizations.  This pass performs standard induction variable optimizations, including strength reduction, induction variable merging and induction variable elimination.  The pass is implemented in tree-ssa-loop-ivopts.c.

     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 in tree-ssa-loop-unswitch.c.  This pass should eventually replace the RTL level loop unswitching in loop-unswitch.c, but currently the RTL level pass is not completely redundant yet due to deficiencies in tree level alias analysis.

     The optimizations also use various utility functions contained in tree-ssa-loop-manip.c, cfgloop.c, cfgloopanal.c and cfgloopmanip.c.

     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 the VF 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.c (the main driver and general utilities), tree-vect-analyze.c and tree-vect-transform.c. Analysis of data references is in tree-data-ref.c.

     Autoparallelization.  This pass splits the loop iteration space to run into several threads.  The pass is implemented in tree-parloops.c.

  * 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 patch re-introduces COND_EXPR at GIMPLE level.  This pass is located in tree-if-conv.c 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.c and is described by pass_ccp.

     A related pass that works on memory loads and stores, and not just register values, is located in tree-ssa-ccp.c and described by pass_store_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.c and described by pass_copy_prop.

     A related pass that works on memory copies, and not just register copies, is located in tree-ssa-copy.c and described by pass_store_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.c 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 in tree-ssa-ccp.c 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 in tree-cfg.c 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.c 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.c and is described by pass_tail_calls.  The RTL transformation is handled by fixup_tail_calls in calls.c.

  * 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.c and is described by pass_warn_function_return.

  * Mudflap statement annotation

     If mudflap is enabled, we rewrite some memory accesses with code to validate that the memory access is correct.  In particular, expressions involving pointer dereferences (INDIRECT_REF, ARRAY_REF, etc.) are replaced by code that checks the selected address range against the mudflap runtime's database of valid regions.  This check includes an inline lookup into a direct-mapped cache, based on shift/mask operations of the pointer value, with a fallback function call into the runtime.  The pass is located in tree-mudflap.c and is described by pass_mudflap_2.

  * Leave static single assignment form

     This pass rewrites the function such that it is in normal form.  At the same time, we eliminate as many single-use temporaries as possible, so the intermediate language is no longer GIMPLE, but GENERIC.  The pass is located in tree-outof-ssa.c and is described by pass_del_ssa.

  * 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.c and is described by pass_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.c and is described by pass_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 of var is sent to the caller to avoid an extra memory copy.  This pass is located in tree-nrv.c and is described by pass_return_slot.

  * Optimize calls to __builtin_object_size

     This is a propagation pass similar to CCP that tries to remove calls to __builtin_object_size when the size of the object can be computed at compile-time.  This pass is located in tree-object-size.c and is described by pass_object_sizes.

  * Loop invariant motion

     This pass removes expensive loop-invariant computations out of loops. The pass is located in tree-ssa-loop.c and described by pass_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 tree-loop-linear.c and described by pass_linear_transform.

  * Removal of empty loops

     This pass removes loops with no code in them.  The pass is located in tree-ssa-loop-ivcanon.c and described by pass_empty_loop.

  * Unrolling of small loops

     This pass completely unrolls loops with few iterations.  The pass is located in tree-ssa-loop-ivcanon.c and described by pass_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.c and 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.c 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.c and described by pass_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.  If va_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 in tree-stdarg.c and described by pass_stdarg.

RTL passes
==========

The following briefly describes the RTL generation and optimization passes that are run after the Tree optimization passes.

  * RTL generation

     The source files for RTL generation include stmt.c, calls.c, expr.c, explow.c, expmed.c, function.c, optabs.c and emit-rtl.c. Also, the file insn-emit.c, generated from the machine description by the program genemit, is used in this pass.  The header file expr.h is used for communication within this pass.

     The header files insn-flags.h and insn-codes.h, generated from the machine description by the programs genflags and gencodes, tell this pass which standard names are available for use and which patterns correspond to them.

  * Generation of exception landing pads

     This pass generates the glue that handles communication between the exception handling library routines and the exception handlers within the function.  Entry points in the function that are invoked by the exception handling library are called landing pads.  The code for this pass is located in except.c.

  * Control flow graph cleanup

     This pass removes unreachable code, simplifies jumps to next, jumps to jump, jumps across jumps, etc.  The pass is run multiple times. For historical reasons, it is occasionally referred to as the ``jump optimization pass''.  The bulk of the code for this pass is in cfgcleanup.c, and there are support routines in cfgrtl.c and jump.c.

  * Forward propagation of single-def values

     This pass attempts to remove redundant computation by substituting variables that come from a single definition, and seeing if the result can be simplified.  It performs copy propagation and addressing mode selection.  The pass is run twice, with values being propagated into loops only on the second run.  The code is located in fwprop.c.

  * Common subexpression elimination

     This pass removes redundant computation within basic blocks, and optimizes addressing modes based on cost.  The pass is run twice. The code for this pass is located in cse.c.

  * Global common subexpression elimination

     This pass performs two different types of GCSE  depending on whether you are optimizing for size or not (LCM based GCSE tends to increase code size for a gain in speed, while Morel-Renvoise based GCSE does not). When optimizing for size, GCSE is done using Morel-Renvoise Partial Redundancy Elimination, with the exception that it does not try to move invariants out of loops---that is left to  the loop optimization pass. If MR PRE GCSE is done, code hoisting (aka unification) is also done, as well as load motion. If you are optimizing for speed, LCM (lazy code motion) based GCSE is done.  LCM is based on the work of Knoop, Ruthing, and Steffen.  LCM based GCSE also does loop invariant code motion.  We also perform load and store motion when optimizing for speed. Regardless of which type of GCSE is used, the GCSE pass also performs global constant and  copy propagation. The source file for this pass is gcse.c, and the LCM routines are in lcm.c.

  * Loop optimization

     This pass performs several loop related optimizations. The source files cfgloopanal.c and cfgloopmanip.c contain generic loop analysis and manipulation code.  Initialization and finalization of loop structures is handled by loop-init.c. A loop invariant motion pass is implemented in loop-invariant.c. Basic block level optimizations---unrolling, peeling and unswitching loops--- are implemented in loop-unswitch.c and loop-unroll.c. Replacing of the exit condition of loops by special machine-dependent instructions is handled by loop-doloop.c.

  * Jump bypassing

     This pass is an aggressive form of GCSE that transforms the control flow graph of a function by propagating constants into conditional branch instructions.  The source file for this pass is gcse.c.

  * If conversion

     This pass attempts to replace conditional branches and surrounding assignments with arithmetic, boolean value producing comparison instructions, and conditional move instructions.  In the very last invocation after reload, it will generate predicated instructions when supported by the target.  The code is located in ifcvt.c.

  * Web construction

     This pass splits independent uses of each pseudo-register.  This can improve effect of the other transformation, such as CSE or register allocation.  The code for this pass is located in web.c.

  * Instruction combination

     This pass attempts to combine groups of two or three instructions that are related by data flow into single instructions.  It combines the RTL expressions for the instructions by substitution, simplifies the result using algebra, and then attempts to match the result against the machine description.  The code is located in combine.c.

  * Register movement

     This pass looks for cases where matching constraints would force an instruction to need a reload, and this reload would be a register-to-register move.  It then attempts to change the registers used by the instruction to avoid the move instruction.  The code is located in regmove.c.

  * Mode switching optimization

     This pass looks for instructions that require the processor to be in a specific ``mode'' and minimizes the number of mode changes required to satisfy all users.  What these modes are, and what they apply to are completely target-specific.  The code for this pass is located in mode-switching.c.

  * Modulo scheduling

     This pass looks at innermost loops and reorders their instructions by overlapping different iterations.  Modulo scheduling is performed immediately before instruction scheduling.  The code for this pass is located in modulo-sched.c.

  * Instruction scheduling

     This pass looks for instructions whose output will not be available by the time that it is used in subsequent instructions.  Memory loads and floating point instructions often have this behavior on RISC machines. It re-orders instructions within a basic block to try to separate the definition and use of items that otherwise would cause pipeline stalls.  This pass is performed twice, before and after register allocation.  The code for this pass is located in haifa-sched.c, sched-deps.c, sched-ebb.c, sched-rgn.c and sched-vis.c.

  * Register allocation

     These passes make sure that all occurrences of pseudo registers are eliminated, either by allocating them to a hard register, replacing them by an equivalent expression (e.g. a constant) or by placing them on the stack.  This is done in several subpasses:

       * Register move optimizations.  This pass makes some simple RTL code transformations which improve the subsequent register allocation.  The source file is regmove.c.

       * The integrated register allocator (IRA).  It is called integrated because coalescing, register live range splitting, and hard register preferencing are done on-the-fly during coloring.  It also has better integration with the reload pass.  Pseudo-registers spilled by the allocator or the reload have still a chance to get hard-registers if the reload evicts some pseudo-registers from hard-registers.  The allocator helps to choose better pseudos for spilling based on their live ranges and to coalesce stack slots allocated for the spilled pseudo-registers.  IRA is a regional register allocator which is transformed into Chaitin-Briggs allocator if there is one region.  By default, IRA chooses regions using register pressure but the user can force it to use one region or regions corresponding to all loops.

          Source files of the allocator are ira.c, ira-build.c, ira-costs.c, ira-conflicts.c, ira-color.c, ira-emit.c, ira-lives, plus header files ira.h and ira-int.h used for the communication between the allocator and the rest of the compiler and between the IRA files.

       * Reloading.  This pass renumbers pseudo registers with the hardware registers numbers they were allocated.  Pseudo registers that did not get hard registers are replaced with stack slots.  Then it finds instructions that are invalid because a value has failed to end up in a register, or has ended up in a register of the wrong kind.  It fixes up these instructions by reloading the problematical values temporarily into registers.  Additional instructions are generated to do the copying.

          The reload pass also optionally eliminates the frame pointer and inserts instructions to save and restore call-clobbered registers around calls.

          Source files are reload.c and reload1.c, plus the header reload.h used for communication between them.

  * Basic block reordering

     This pass implements profile guided code positioning.  If profile information is not available, various types of static analysis are performed to make the predictions normally coming from the profile feedback (IE execution frequency, branch probability, etc).  It is implemented in the file bb-reorder.c, and the various prediction routines are in predict.c.

  * Variable tracking

     This pass computes where the variables are stored at each position in code and generates notes describing the variable locations to RTL code.  The location lists are then generated according to these notes to debug information if the debugging information format supports location lists.  The code is located in var-tracking.c.

  * Delayed branch scheduling

     This optional pass attempts to find instructions that can go into the delay slots of other instructions, usually jumps and calls.  The code for this pass is located in reorg.c.

  * Branch shortening

     On many RISC machines, branch instructions have a limited range. Thus, longer sequences of instructions must be used for long branches. In this pass, the compiler figures out what how far each instruction will be from each other instruction, and therefore whether the usual instructions, or the longer sequences, must be used for each branch. The code for this pass is located in final.c.

  * Register-to-stack conversion

     Conversion from usage of some hard registers to usage of a register stack may be done at this point.  Currently, this is supported only for the floating-point registers of the Intel 80387 coprocessor.  The code for this pass is located in reg-stack.c.

  * Final

     This pass outputs the assembler code for the function.  The source files are final.c plus insn-output.c; the latter is generated automatically from the machine description by the tool genoutput. The header file conditions.h is used for communication between these files.  If mudflap is enabled, the queue of deferred declarations and any addressed constants (e.g., string literals) is processed by mudflap_finish_file into a synthetic constructor function containing calls into the mudflap runtime.

  * Debugging information output

     This is run after final because it must output the stack slot offsets for pseudo registers that did not get hard registers.  Source files are dbxout.c for DBX symbol table format, sdbout.c for SDB symbol table format, dwarfout.c for DWARF symbol table format, files dwarf2out.c and dwarf2asm.c for DWARF2 symbol table format, and vmsdbgout.c for VMS debug symbol table format.