+@c markers: CROSSREF BUG TODO
+
@c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
-@c 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+@c 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.
@cindex files and passes of the compiler
@cindex compiler passes and files
-@cindex top level of compiler
-The overall control structure of the compiler is in @file{toplev.c}. This
-file is responsible for initialization, decoding arguments, opening and
-closing files, and sequencing the passes. Routines for emitting
-diagnostic messages are defined in @file{diagnostic.c}. The files
-@file{pretty-print.h} and @file{pretty-print.c} provide basic support
-for language-independent pretty-printing.
-
-@cindex parsing pass
-The parsing pass is invoked only once, to parse the entire input. A
-high level tree representation is then generated from the input,
-one function at a time. This tree code is then transformed into RTL
-intermediate code, and processed. The files involved in transforming
-the trees into RTL are @file{expr.c}, @file{expmed.c}, and
-@file{stmt.c}.
-@c Note, the above files aren't strictly the only files involved. It's
-@c all over the place (function.c, final.c,etc). However, those are
-@c the files that are supposed to be directly involved, and have
-@c their purpose listed as such, so i've only listed them.
-The order of trees that are processed, is not
-necessarily the same order they are generated from
-the input, due to deferred inlining, and other considerations.
-
-@findex rest_of_compilation
+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.
+
+@menu
+* Parsing pass:: The language front end turns text into bits.
+* Gimplification pass:: The bits are turned into something we can optimize.
+* Pass manager:: Sequencing the optimization passes.
+* Tree-SSA passes:: Optimizations on a high-level representation.
+* RTL passes:: Optimizations on a low-level representation.
+@end menu
+
+@node Parsing pass
+@section Parsing pass
+@cindex GENERIC
+@findex lang_hooks.parse_file
+The language front end is invoked only once, via
+@code{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
+@file{c-common.def}. The Fortran front end uses a completely different
+private representation.
+
+@cindex GIMPLE
+@cindex gimplification
+@cindex gimplifier
+@cindex language-independent intermediate representation
+@cindex intermediate representation lowering
+@cindex lowering, language-dependent intermediate 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@dots{} 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 @emph{definitions} be passed to the middle-end. For
+complete debug information, function, data and type declarations
+should all be passed as well.
+
@findex rest_of_decl_compilation
-Each time the parsing pass reads a complete function definition or
-top-level declaration, it calls either the function
-@code{rest_of_compilation}, or the function
-@code{rest_of_decl_compilation} in @file{toplev.c}, which are
-responsible for all further processing necessary, ending with output of
-the assembler language. All other compiler passes run, in sequence,
-within @code{rest_of_compilation}. When that function returns from
-compiling a function definition, the storage used for that function
-definition's compilation is entirely freed, unless it is an inline
-function, or was deferred for some reason (this can occur in
-templates, for example).
-(@pxref{Inline,,An Inline Function is As Fast As a Macro,gcc,Using the
-GNU Compiler Collection (GCC)}).
-
-Here is a list of all the passes of the compiler and their source files.
-Also included is a description of where debugging dumps can be requested
-with @option{-d} options.
+@findex rest_of_type_compilation
+@findex cgraph_finalize_function
+In any case, the front end needs each complete top-level function or
+data declaration, and each data definition should be passed to
+@code{rest_of_decl_compilation}. Each complete type definition should
+be passed to @code{rest_of_type_compilation}. Each function definition
+should be passed to @code{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.
+
+@node Gimplification pass
+@section Gimplification pass
+
+@cindex gimplification
+@cindex GIMPLE
+@dfn{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.
+
+@cindex GENERIC
+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.
+
+@findex gimplify_function_tree
+@findex gimplify_expr
+@findex lang_hooks.gimplify_expr
+The main entry point to this pass is @code{gimplify_function_tree}
+located in @file{gimplify.c}. From here we process the entire
+function gimplifying each statement in turn. The main workhorse
+for this pass is @code{gimplify_expr}. Approximately everything
+passes through here at least once, and it is from here that we
+invoke the @code{lang_hooks.gimplify_expr} callback.
+
+The callback should examine the expression in question and return
+@code{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 @code{GS_ALL_DONE}. Otherwise it should return
+@code{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 @code{GS_ERROR}.
+
+@node Pass manager
+@section Pass manager
+
+The pass manager is located in @file{passes.c}, @file{tree-optimize.c}
+and @file{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 @code{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.
+
+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...
+
+@node Tree-SSA passes
+@section Tree-SSA passes
+
+The following briefly describes the tree optimization passes that are
+run after gimplification and what source files they are located in.
@itemize @bullet
-@item
-Parsing. This pass reads the entire text of a function definition,
-constructing a high level tree representation. (Because of the semantic
-analysis that takes place during this pass, it does more than is
-formally considered to be parsing.)
-
-The tree representation does not entirely follow C syntax, because it is
-intended to support other languages as well.
-
-Language-specific data type analysis is also done in this pass, and every
-tree node that represents an expression has a data type attached.
-Variables are represented as declaration nodes.
-
-The language-independent source files for parsing are
-@file{tree.c}, @file{fold-const.c}, and @file{stor-layout.c}.
-There are also header files @file{tree.h} and @file{tree.def}
-which define the format of the tree representation.
-
-C preprocessing, for language front ends, that want or require it, is
-performed by cpplib, which is covered in separate documentation. In
-particular, the internals are covered in @xref{Top, ,Cpplib internals,
-cppinternals, Cpplib Internals}.
-
-The source files to parse C are found in the toplevel directory, and
-by convention are named @file{c-*}. Some of these are also used by
-the other C-like languages: @file{c-common.c},
-@file{c-common.def},
-@file{c-format.c},
-@file{c-opts.c},
-@file{c-pragma.c},
-@file{c-semantics.c},
-@file{c-lex.c},
-@file{c-incpath.c},
-@file{c-ppoutput.c},
-@file{c-cppbuiltin.c},
-@file{c-common.h},
-@file{c-dump.h},
-@file{c.opt},
-@file{c-incpath.h}
-and
-@file{c-pragma.h},
-
-Files specific to each language are in subdirectories named after the
-language in question, like @file{ada}, @file{objc}, @file{cp} (for C++).
-
-@cindex Tree optimization
-@item
-Tree optimization. This is the optimization of the tree
-representation, before converting into RTL code.
-
-@cindex inline on trees, automatic
-Currently, the main optimization performed here is tree-based
-inlining.
-This is implemented in @file{tree-inline.c} and used by both C and C++.
-Note that tree based inlining turns off rtx based inlining (since it's more
-powerful, it would be a waste of time to do rtx based inlining in
-addition).
-
-@cindex constant folding
-@cindex arithmetic simplifications
-@cindex simplifications, arithmetic
-Constant folding and some arithmetic simplifications are also done
-during this pass, on the tree representation.
-The routines that perform these tasks are located in @file{fold-const.c}.
-
-@cindex RTL generation
-@item
-RTL generation. This is the conversion of syntax tree into RTL code.
+@item 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 @code{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 @file{tree-cfg.c} and described by
+@code{pass_remove_useless_stmts}.
+
+@item Mudflap declaration registration
+
+If mudflap (@pxref{Optimize Options,,-fmudflap -fmudflapth
+-fmudflapir,gcc.info,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 (@code{extern}). This pass generates
+new exception handling constructs (@code{try}/@code{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 @file{tree-mudflap.c} and is described
+by @code{pass_mudflap_1}.
+
+@item Lower control flow
+
+This pass flattens @code{if} statements (@code{COND_EXPR}) and
+and moves lexical bindings (@code{BIND_EXPR}) out of line. After
+this pass, all @code{if} statements will have exactly two @code{goto}
+statements in its @code{then} and @code{else} arms. Lexical binding
+information for each statement will be found in @code{TREE_BLOCK} rather
+than being inferred from its position under a @code{BIND_EXPR}. This
+pass is found in @file{gimple-low.c} and is described by
+@code{pass_lower_cf}.
+
+@item Lower exception handling control flow
+
+This pass decomposes high-level exception handling constructs
+(@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form
+that explicitly represents the control flow involved. After this
+pass, @code{lookup_stmt_eh_region} will return a non-negative
+number for any statement that may have EH control flow semantics;
+examine @code{tree_can_throw_internal} or @code{tree_can_throw_external}
+for exact semantics. Exact control flow may be extracted from
+@code{foreach_reachable_handler}. The EH region nesting tree is defined
+in @file{except.h} and built in @file{except.c}. The lowering pass
+itself is in @file{tree-eh.c} and is described by @code{pass_lower_eh}.
+
+@item 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 @file{tree-cfg.c} and
+is described by @code{pass_build_cfg}.
+
+@item Find all referenced variables
+
+This pass walks the entire function and collects an array of all
+variables referenced in the function, @code{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 @file{tree-dfa.c}
+and is described by @code{pass_referenced_vars}.
+
+@item Enter static single assignment form
+
+This pass rewrites the function such that it is in SSA form. After
+this pass, all @code{is_gimple_reg} variables will be referenced by
+@code{SSA_NAME}, and all occurrences of other variables will be
+annotated with @code{VDEFS} and @code{VUSES}; phi nodes will have
+been inserted as necessary for each basic block. This pass is
+located in @file{tree-ssa.c} and is described by @code{pass_build_ssa}.
+
+@item Warn for uninitialized variables
+
+This pass scans the function for uses of @code{SSA_NAME}s that
+are fed by default definition. For non-parameter variables, such
+uses are uninitialized. The pass is run twice, before and after
+optimization. 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 @file{tree-ssa.c}
+and is defined by @code{pass_early_warn_uninitialized} and
+@code{pass_late_warn_uninitialized}.
+
+@item 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
+@file{tree-ssa-dce.c} and is described by @code{pass_dce}.
+
+@item 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 @file{tree-ssa-dom.c}
+and is described by @code{pass_dominator}.
+
+@item Redundant phi elimination
+
+This pass removes phi nodes for which all of the arguments are the same
+value, excluding feedback. Such degenerate forms are typically created
+by removing unreachable code. The pass is run multiple times throughout
+the optimization process. It is located in @file{tree-ssa.c} and is
+described by @code{pass_redundant_phi}.o
+
+@item 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
+@file{tree-ssa-forwprop.c} and is described by @code{pass_forwprop}.
+
+@item 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 @file{tree-ssa-copyrename.c} and is described by
+@code{pass_copyrename}.
+
+@item 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 @file{tree-ssa-phiopt.c} and is described by
+@code{pass_phiopt}.
+
+@item 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 @code{VDEF}/@code{VUSE} memory tags for non-renamable
+aggregates so that we get fewer false kills. The pass is located
+in @file{tree-ssa-alias.c} and is described by @code{pass_may_alias}.
+
+@item 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 @file{predict.c} and
+is described by @code{pass_profile}.
+
+@item Lower complex arithmetic
+
+This pass rewrites complex arithmetic operations into their component
+scalar arithmetic operations. The pass is located in @file{tree-complex.c}
+and is described by @code{pass_lower_complex}.
+
+@item 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
+@file{tree-sra.c} and is described by @code{pass_sra}.
+
+@item 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 @file{tree-ssa-dse.c} and is described by @code{pass_dse}.
+
+@item Tail recursion elimination
+
+This pass transforms tail recursion into a loop. It is located in
+@file{tree-tailcall.c} and is described by @code{pass_tail_recursion}.
+
+@item Forward store motion
+
+This pass sinks stores and assignments down the flowgraph closer to it's
+use point. The pass is located in @file{tree-ssa-sink.c} and is
+described by @code{pass_sink_code}.
+
+@item Partial redundancy elimination
+
+This pass eliminates partially redundant computations, as well as
+performing load motion. The pass is located in @file{tree-ssa-pre.c}
+and is described by @code{pass_pre}.
+
+Just before partial redundancy elimination, if
+@option{-funsafe-math-optimizations} is on, GCC tries to convert
+divisions to multiplications by the reciprocal. The pass is located
+in @file{tree-ssa-math-opts.c} and is described by
+@code{pass_cse_reciprocal}.
+
+@item Loop optimization
-@cindex target-parameter-dependent code
-This is where the bulk of target-parameter-dependent code is found,
-since often it is necessary for strategies to apply only when certain
-standard kinds of instructions are available. The purpose of named
-instruction patterns is to provide this information to the RTL
-generation pass.
+The main driver of the pass is placed in @file{tree-ssa-loop.c}
+and described by @code{pass_loop}.
-@cindex tail recursion optimization
-Optimization is done in this pass for @code{if}-conditions that are
-comparisons, boolean operations or conditional expressions. Tail
-recursion is detected at this time also. Decisions are made about how
-best to arrange loops and how to output @code{switch} statements.
+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 @option{-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 @file{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 @file{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
+@file{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
+@file{tree-ssa-loop-unswitch.c}. This pass should eventually replace the
+rtl-level loop unswitching in @file{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
+@file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and
+@file{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 @code{VF} (vectorization factor), which is
+the number of elements operated upon in parallel in each iteration, and the
+@code{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 @file{tree-vectorizer.c} (the main driver and general
+utilities), @file{tree-vect-analyze.c} and @file{tree-vect-transform.c}.
+Analysis of data references is in @file{tree-data-ref.c}.
+
+@item Tree level if-conversion for vectorizer
+
+This pass applies if-conversion to simple loops to help vectorizer.
+We identify if convertable 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 @file{tree-if-conv.c}.
+
+@item 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 @file{tree-ssa-ccp.c} and is described
+by @code{pass_ccp}.
+
+@item Folding builtin functions
+
+This pass simplifies builtin functions, as applicable, with constant
+arguments or with inferrable string lengths. It is located in
+@file{tree-ssa-ccp.c} and is described by @code{pass_fold_builtins}.
+
+@item 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
+@file{tree-cfg.c} and is described by @code{pass_split_crit_edges}.
+
+@item Partial redundancy elimination
+
+This pass answers the question ``given a hypothetical temporary
+variable, what expressions could we eliminate?'' It is located
+in @file{tree-ssa-pre.c} and is described by @code{pass_pre}.
+
+@item 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 @file{tree-ssa-dce.c} and is described by @code{pass_cd_dce}.
+
+@item 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 @code{CALL_EXPR_TAILCALL} is set indicating the possibility.
+The pass is located in @file{tree-tailcall.c} and is described by
+@code{pass_tail_calls}. The RTL transformation is handled by
+@code{fixup_tail_calls} in @file{calls.c}.
+
+@item 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 @file{tree-cfg.c} and
+is described by @code{pass_warn_function_return}.
+
+@item 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 (@code{INDIRECT_REF}, @code{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 @file{tree-mudflap.c} and
+is described by @code{pass_mudflap_2}.
+
+@item 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 @file{tree-ssa.c} and is described by @code{pass_del_ssa}.
+@end itemize
+
+@node RTL passes
+@section RTL passes
+
+The following briefly describes the rtl generation and optimization
+passes that are run after tree optimization.
+
+@itemize @bullet
+@item RTL generation
@c Avoiding overfull is tricky here.
The source files for RTL generation include
and @code{gencodes}, tell this pass which standard names are available
for use and which patterns correspond to them.
-Aside from debugging information output, none of the following passes
-refers to the tree structure representation of the function (only
-part of which is saved).
-
-@cindex inline on rtx, automatic
-The decision of whether the function can and should be expanded inline
-in its subsequent callers is made at the end of rtl generation. The
-function must meet certain criteria, currently related to the size of
-the function and the types and number of parameters it has. Note that
-this function may contain loops, recursive calls to itself
-(tail-recursive functions can be inlined!), gotos, in short, all
-constructs supported by GCC@. The file @file{integrate.c} contains
-the code to save a function's rtl for later inlining and to inline that
-rtl when the function is called. The header file @file{integrate.h}
-is also used for this purpose.
-
-@opindex dr
-The option @option{-dr} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.rtl} to
-the input file name.
-
-@c Should the exception handling pass be talked about here?
-
-@cindex sibling call optimization
-@item
-Sibling call optimization. This pass performs tail recursion
-elimination, and tail and sibling call optimizations. The purpose of
-these optimizations is to reduce the overhead of function calls,
-whenever possible.
+@item Generate exception handling landing pads
-The source file of this pass is @file{sibcall.c}
+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 @dfn{landing pads}. The code
+for this pass is located within @file{except.c}.
-@opindex di
-The option @option{-di} causes a debugging dump of the RTL code after
-this pass is run. This dump file's name is made by appending
-@samp{.sibling} to the input file name.
+@item Cleanup control flow graph
-@cindex jump optimization
-@cindex unreachable code
-@cindex dead code
-@item
-Jump optimization. This pass simplifies jumps to the following
-instruction, jumps across jumps, and jumps to jumps. It deletes
-unreferenced labels and unreachable code, except that unreachable code
-that contains a loop is not recognized as unreachable in this pass.
-(Such loops are deleted later in the basic block analysis.) It also
-converts some code originally written with jumps into sequences of
-instructions that directly set values from the results of comparisons,
-if the machine has such instructions.
-
-Jump optimization is performed two or three times. The first time is
-immediately following RTL generation. The second time is after CSE,
-but only if CSE says repeated jump optimization is needed. The
-last time is right before the final pass. That time, cross-jumping
-and deletion of no-op move instructions are done together with the
-optimizations described above.
-
-The source file of this pass is @file{jump.c}.
-
-@opindex dj
-The option @option{-dj} causes a debugging dump of the RTL code after
-this pass is run for the first time. This dump file's name is made by
-appending @samp{.jump} to the input file name.
-
-
-@cindex register use analysis
-@item
-Register scan. This pass finds the first and last use of each
-register, as a guide for common subexpression elimination. Its source
-is in @file{regclass.c}.
+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
+@file{cfgcleanup.c}, and there are support routines in @file{cfgrtl.c}
+and @file{jump.c}.
-@cindex jump threading
-@item
-@opindex fthread-jumps
-Jump threading. This pass detects a condition jump that branches to an
-identical or inverse test. Such jumps can be @samp{threaded} through
-the second conditional test. The source code for this pass is in
-@file{jump.c}. This optimization is only performed if
-@option{-fthread-jumps} is enabled.
-
-@cindex common subexpression elimination
-@cindex constant propagation
-@item
-Common subexpression elimination. This pass also does constant
-propagation. Its source files are @file{cse.c}, and @file{cselib.c}.
-If constant propagation causes conditional jumps to become
-unconditional or to become no-ops, jump optimization is run again when
-CSE is finished.
-
-@opindex ds
-The option @option{-ds} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.cse} to
-the input file name.
-
-@cindex global common subexpression elimination
-@cindex constant propagation
-@cindex copy propagation
-@item
-Global common subexpression elimination. This pass performs two
+@item Common subexpression elimination
+
+This pass removes redundant computation within basic blocks, and
+optimizes addressing modes based on cost. The pass is run twice.
+The source is located in @file{cse.c}.
+
+@item 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).
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 @file{gcse.c}, and the LCM routines
are in @file{lcm.c}.
-@opindex dG
-The option @option{-dG} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.gcse} to
-the input file name.
+@item Loop optimization
-@cindex loop optimization
-@cindex code motion
-@cindex strength-reduction
-@item
-Loop optimization. This pass moves constant expressions out of loops,
-and optionally does strength-reduction and loop unrolling as well.
-Its source files are @file{loop.c} and @file{unroll.c}, plus the header
-@file{loop.h} used for communication between them. Loop unrolling uses
-some functions in @file{integrate.c} and the header @file{integrate.h}.
+This pass moves constant expressions out of loops, and optionally does
+strength-reduction as well. The pass is located in @file{loop.c}.
Loop dependency analysis routines are contained in @file{dependence.c}.
-
-Second loop optimization pass takes care of basic block level optimizations --
-unrolling, peeling and unswitching loops. The source files are
-@file{cfgloopanal.c} and @file{cfgloopmanip.c} containing generic loop
-analysis and manipulation code, @file{loop-init.c} with initialization and
-finalization code, @file{loop-unswitch.c} for loop unswitching and
-@file{loop-unroll.c} for loop unrolling and peeling.
-
-@opindex dL
-The option @option{-dL} causes a debugging dump of the RTL code after
-these passes. The dump file names are made by appending @samp{.loop} and
-@samp{.loop2} to the input file name.
-
-@cindex jump bypassing
-@item
-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 @file{gcse.c}.
-
-@opindex dG
-The option @option{-dG} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.bypass}
-to the input file name.
-
-@cindex web construction
-@item
-Simple optimization pass that splits independent uses of each pseudo
-increasing effect of other optimizations. This can improve effect of the
-other transformation, such as CSE or register allocation.
-Its source files are @file{web.c}.
-
-@opindex dZ
-The option @option{-dZ} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.web} to
-the input file name.
-
-@item
-@opindex frerun-cse-after-loop
-If @option{-frerun-cse-after-loop} was enabled, a second common
-subexpression elimination pass is performed after the loop optimization
-pass. Jump threading is also done again at this time if it was specified.
-
-@opindex dt
-The option @option{-dt} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.cse2} to
-the input file name.
-
-@cindex data flow analysis
-@cindex analysis, data flow
-@cindex basic blocks
-@item
-Data flow analysis (@file{flow.c}). This pass divides the program
-into basic blocks (and in the process deletes unreachable loops); then
-it computes which pseudo-registers are live at each point in the
-program, and makes the first instruction that uses a value point at
-the instruction that computed the value.
-
-@cindex autoincrement/decrement analysis
-This pass also deletes computations whose results are never used, and
-combines memory references with add or subtract instructions to make
-autoincrement or autodecrement addressing.
-
-@opindex df
-The option @option{-df} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.flow} to
-the input file name. If stupid register allocation is in use, this
-dump file reflects the full results of such allocation.
-
-@cindex instruction combination
-@item
-Instruction combination (@file{combine.c}). 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.
-
-@opindex dc
-The option @option{-dc} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.combine}
-to the input file name.
-
-@cindex if conversion
-@item
-If-conversion is a transformation that transforms control dependencies
-into data dependencies (IE it transforms conditional code into a
-single control stream).
-It is implemented in the file @file{ifcvt.c}.
-
-@opindex dE
-The option @option{-dE} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.ce} to
-the input file name.
-
-@cindex register movement
-@item
-Register movement (@file{regmove.c}). 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.
-
-@opindex dN
-The option @option{-dN} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.regmove}
-to the input file name.
-
-@cindex instruction scheduling
-@cindex scheduling, instruction
-@item
-Instruction scheduling (@file{sched.c}). 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.
-
-Instruction scheduling is performed twice. The first time is immediately
-after instruction combination and the second is immediately after reload.
-
-@opindex dS
-The option @option{-dS} causes a debugging dump of the RTL code after this
-pass is run for the first time. The dump file's name is made by
-appending @samp{.sched} to the input file name.
-
-@cindex register allocation
-@item
-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
+This pass is seriously out-of-date and is supposed to be replaced by
+a new one described below in near future.
+
+A second loop optimization pass takes care of basic block level
+optimizations---unrolling, peeling and unswitching loops. The source
+files are @file{cfgloopanal.c} and @file{cfgloopmanip.c} containing
+generic loop analysis and manipulation code, @file{loop-init.c} with
+initialization and finalization code, @file{loop-unswitch.c} for loop
+unswitching and @file{loop-unroll.c} for loop unrolling and peeling.
+It also contains a separate loop invariant motion pass implemented in
+@file{loop-invariant.c}.
+
+@item 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 @file{gcse.c}.
+
+@item 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 pass is located in @file{ifcvt.c}.
+
+@item 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. Its source files are @file{web.c}.
+
+@item Life analysis
+
+This pass computes which pseudo-registers are live at each point in
+the program, and makes the first instruction that uses a value point
+at the instruction that computed the value. It then deletes
+computations whose results are never used, and combines memory
+references with add or subtract instructions to make autoincrement or
+autodecrement addressing. The pass is located in @file{flow.c}.
+
+@item 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 pass is located in @file{combine.c}.
+
+@item 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 pass is located in @file{regmove.c}.
+
+@item Optimize mode switching
+
+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 source is located in @file{mode-switching.c}.
+
+@cindex modulo scheduling
+@cindex sms, swing, software pipelining
+@item 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 pass is located in (@file{modulo-sched.c}).
+
+@item 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 pass is located in @file{haifa-sched.c},
+@file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and
+@file{sched-vis.c}.
+
+@item 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:
@itemize @bullet
-@cindex register class preference pass
@item
Register class preferencing. The RTL code is scanned to find out
which register class is best for each pseudo register. The source
file is @file{regclass.c}.
-@cindex local register allocation
-@item
-Local register allocation (@file{local-alloc.c}). This pass allocates
-hard registers to pseudo registers that are used only within one basic
-block. Because the basic block is linear, it can use fast and
-powerful techniques to do a very good job.
-
-@opindex dl
-The option @option{-dl} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.lreg} to
-the input file name.
-
-@cindex global register allocation
@item
-Global register allocation (@file{global.c}). This pass
-allocates hard registers for the remaining pseudo registers (those
-whose life spans are not contained in one basic block).
+Local register allocation. This pass allocates hard registers to
+pseudo registers that are used only within one basic block. Because
+the basic block is linear, it can use fast and powerful techniques to
+do a decent job. The source is located in @file{local-alloc.c}.
-@cindex graph coloring register allocation
-@opindex fnew-ra
-@opindex dl
@item
-Graph coloring register allocator. The files @file{ra.c}, @file{ra-build.c},
-@file{ra-colorize.c}, @file{ra-debug.c}, @file{ra-rewrite.c} together with
-the header @file{ra.h} contain another register allocator, which is used
-when the option @option{-fnew-ra} is given. In that case it is run instead
-of the above mentioned local and global register allocation passes, and the
-option @option{-dl} causes a debugging dump of its work.
+Global register allocation. This pass allocates hard registers for
+the remaining pseudo registers (those whose life spans are not
+contained in one basic block). The pass is located in @file{global.c}.
@cindex reloading
@item
Source files are @file{reload.c} and @file{reload1.c}, plus the header
@file{reload.h} used for communication between them.
-
-@opindex dg
-The option @option{-dg} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.greg} to
-the input file name.
@end itemize
-@cindex instruction scheduling
-@cindex scheduling, instruction
-@item
-Instruction scheduling is repeated here to try to avoid pipeline stalls
-due to memory loads generated for spilled pseudo registers.
+@item Basic block reordering
-@opindex dR
-The option @option{-dR} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.sched2}
-to the input file name.
+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 @file{bb-reorder.c}, and the various
+prediction routines are in @file{predict.c}.
-@cindex basic block reordering
-@cindex reordering, block
-@item
-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 @file{bb-reorder.c}, and the
-various prediction routines are in @file{predict.c}.
-
-@opindex dB
-The option @option{-dB} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.bbro} to
-the input file name.
-
-@cindex variable tracking
-@item
-Variable tracking. This pass computes where the variables are stored at each
+@item 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.
-@opindex dV
-The option @option{-dV} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.vartrack}
-to the input file name.
+@item Delayed branch scheduling
-@cindex delayed branch scheduling
-@cindex scheduling, delayed branch
-@item
-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 source file name is @file{reorg.c}.
+This optional pass attempts to find instructions that can go into the
+delay slots of other instructions, usually jumps and calls. The
+source file name is @file{reorg.c}.
-@opindex dd
-The option @option{-dd} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.dbr}
-to the input file name.
+@item 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.
+
+@item Register-to-stack conversion
-@cindex branch shortening
-@item
-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.
-
-@cindex register-to-stack conversion
-@item
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
source file name is @file{reg-stack.c}.
-@opindex dk
-The options @option{-dk} causes a debugging dump of the RTL code after
-this pass. This dump file's name is made by appending @samp{.stack}
-to the input file name.
+@item Final
-@cindex final pass
-@cindex peephole optimization
-@item
-Final. This pass outputs the assembler code for the function. It is
-also responsible for identifying spurious test and compare
-instructions. Machine-specific peephole optimizations are performed
-at the same time. The function entry and exit sequences are generated
-directly as assembler code in this pass; they never exist as RTL@.
-
-The source files are @file{final.c} plus @file{insn-output.c}; the
-latter is generated automatically from the machine description by the
-tool @file{genoutput}. The header file @file{conditions.h} is used
-for communication between these files.
-
-@cindex debugging information generation
-@item
-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 @file{dbxout.c} for DBX symbol table
-format, @file{sdbout.c} for SDB symbol table format, @file{dwarfout.c}
-for DWARF symbol table format, files @file{dwarf2out.c} and
-@file{dwarf2asm.c} for DWARF2 symbol table format, and @file{vmsdbgout.c}
-for VMS debug symbol table format.
-@end itemize
-
-Some additional files are used by all or many passes:
-
-@itemize @bullet
-@item
-Every pass uses @file{machmode.def} and @file{machmode.h} which define
-the machine modes.
-
-@item
-Several passes use @file{real.h}, which defines the default
-representation of floating point constants and how to operate on them.
-
-@item
-All the passes that work with RTL use the header files @file{rtl.h}
-and @file{rtl.def}, and subroutines in file @file{rtl.c}. The tools
-@code{gen*} also use these files to read and work with the machine
-description RTL@.
-
-@item
-All the tools that read the machine description use support routines
-found in @file{gensupport.c}, @file{errors.c}, and @file{read-rtl.c}.
-
-@findex genconfig
-@item
-Several passes refer to the header file @file{insn-config.h} which
-contains a few parameters (C macro definitions) generated
-automatically from the machine description RTL by the tool
-@code{genconfig}.
+This pass outputs the assembler code for the function. The source files
+are @file{final.c} plus @file{insn-output.c}; the latter is generated
+automatically from the machine description by the tool @file{genoutput}.
+The header file @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
+@code{mudflap_finish_file} into a synthetic constructor function
+containing calls into the mudflap runtime.
-@cindex instruction recognizer
-@item
-Several passes use the instruction recognizer, which consists of
-@file{recog.c} and @file{recog.h}, plus the files @file{insn-recog.c}
-and @file{insn-extract.c} that are generated automatically from the
-machine description by the tools @file{genrecog} and
-@file{genextract}.
+@item Debugging information output
-@item
-Several passes use the header files @file{regs.h} which defines the
-information recorded about pseudo register usage, and @file{basic-block.h}
-which defines the information recorded about basic blocks.
+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 @file{dbxout.c} for DBX symbol table format, @file{sdbout.c} for
+SDB symbol table format, @file{dwarfout.c} for DWARF symbol table
+format, files @file{dwarf2out.c} and @file{dwarf2asm.c} for DWARF2
+symbol table format, and @file{vmsdbgout.c} for VMS debug symbol table
+format.
-@item
-@file{hard-reg-set.h} defines the type @code{HARD_REG_SET}, a bit-vector
-with a bit for each hard register, and some macros to manipulate it.
-This type is just @code{int} if the machine has few enough hard registers;
-otherwise it is an array of @code{int} and some of the macros expand
-into loops.
-
-@item
-Several passes use instruction attributes. A definition of the
-attributes defined for a particular machine is in file
-@file{insn-attr.h}, which is generated from the machine description by
-the program @file{genattr}. The file @file{insn-attrtab.c} contains
-subroutines to obtain the attribute values for insns and information
-about processor pipeline characteristics for the instruction
-scheduler. It is generated from the machine description by the
-program @file{genattrtab}.
@end itemize
OSDN Git Service
