passes.texi

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

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-renameable
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}.

Interprocedural points-to information is located in
@file{tree-ssa-structalias.c} and described by @code{pass_ipa_pta}.

@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 their
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 Full redundancy elimination

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

@item Loop optimization

The main driver of the pass is placed in @file{tree-ssa-loop.c}
and described by @code{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 @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}.

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

@item 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 @file{tree-if-conv.c} and is
described by @code{pass_if_conversion}.

@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}.

A related pass that works on memory loads and stores, and not just
register values, is located in @file{tree-ssa-ccp.c} and described by
@code{pass_store_ccp}.

@item 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 @file{tree-ssa-copy.c} and described by
@code{pass_copy_prop}.

A related pass that works on memory copies, and not just register
copies, is located in @file{tree-ssa-copy.c} and described by
@code{pass_store_copy_prop}.

@item 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 @file{tree-vrp.c} and is
described by @code{pass_vrp}.

@item Folding built-in functions

This pass simplifies built-in functions, as applicable, with constant
arguments or with inferable 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 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-outof-ssa.c} and is described by
@code{pass_del_ssa}.

@item 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 @file{tree-cfgcleanup.c} and is described by
@code{pass_merge_phi}.

@item 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 @file{tree-nrv.c} and is described by
@code{pass_nrv}.

@item Return slot optimization

If a function returns a memory object and is called as @code{var =
foo()}, this pass tries to change the call so that the address of
@code{var} is sent to the caller to avoid an extra memory copy.  This
pass is located in @code{tree-nrv.c} and is described by
@code{pass_return_slot}.

@item Optimize calls to @code{__builtin_object_size}

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

@item Loop invariant motion

This pass removes expensive loop-invariant computations out of loops.
The pass is located in @file{tree-ssa-loop.c} and described by
@code{pass_lim}.

@item 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
@file{tree-loop-linear.c} and described by
@code{pass_linear_transform}.

@item Removal of empty loops

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

@item Unrolling of small loops

This pass completely unrolls loops with few iterations.  The pass
is located in @file{tree-ssa-loop-ivcanon.c} and described by
@code{pass_complete_unroll}.

@item Predictive commoning

This pass makes the code reuse the computations from the previous
iterations of the loops, especially loads and stores to memory.