passes.texi

理解和实践操作系统的一本好书

@c markers: CROSSREF BUG TODO

@c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
@c 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software
@c Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.

@node Passes
@chapter Passes and Files of the Compiler
@cindex passes and files of the compiler
@cindex files and passes of the compiler
@cindex compiler passes and files

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
@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@enddots{}

@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 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,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 OpenMP lowering

If OpenMP generation (@option{-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 @file{omp-low.c} and is
described by @code{pass_lower_omp}.

@item OpenMP expansion

If OpenMP generation (@option{-fopenmp}) is enabled, this pass expands
parallel regions into their own functions to be invoked by the thread
library.  The pass is located in @file{omp-low.c} and is described by
@code{pass_expand_omp}.

@item Lower control flow

This pass flattens @code{if} statements (@code{COND_EXPR})
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 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