-@c markers: CROSSREF BUG TODO
+@c markers: 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 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+@c Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.
* 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.
+* Tree SSA passes:: Optimizations on a high-level representation.
* RTL passes:: Optimizations on a low-level representation.
@end menu
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
+appropriate. The C front end uses GENERIC trees (@pxref{GENERIC}), 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.
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,
+The C front end manually invokes the gimplifier (@pxref{GIMPLE}) 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.
+nodes directly to GIMPLE 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)
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
+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
@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'',
+(@pxref{GIMPLE}). 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.
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 should have a unique name.
+Each pass may have its own dump file (for GCC debugging purposes).
+Passes with a name starting with a star do not dump anything.
+Sometimes passes are supposed to share a dump file / option name.
+To still give these unique names, you can use a prefix that is delimited
+by a space from the part that is used for the dump file / option name.
+E.g. When the pass name is "ud dce", the name used for dump file/options
+is "dce".
+
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{}
+I need to look at what info RTL passes use first@enddots{}
-@node Tree-SSA passes
-@section Tree-SSA passes
+@node Tree SSA passes
+@section Tree SSA passes
-The following briefly describes the tree optimization passes that are
+The following briefly describes the Tree optimization passes that are
run after gimplification and what source files they are located in.
@itemize @bullet
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
+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 @file{tree-ssa.c}
and is defined by @code{pass_early_warn_uninitialized} and
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}
+throughout the optimization process. It is located in @file{tree-ssa-dom.c}
and is described by @code{pass_dominator}.
@item Forward propagation of single-use variables
@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
+occur on all paths. It is located in @file{tree-ssa-pre.c} and
described by @code{pass_fre}.
@item Loop optimization
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
+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
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
+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
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
+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
+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}.
+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),
+@file{tree-vect-loop.c} and @file{tree-vect-loop-manip.c} (loop specific parts
+and general loop utilities), @file{tree-vect-slp} (loop-aware SLP
+functionality), @file{tree-vect-stmts.c} and @file{tree-vect-data-refs.c}.
Analysis of data references is in @file{tree-data-ref.c}.
+SLP Vectorization. This pass performs vectorization of straight-line code. The
+pass is implemented in @file{tree-vectorizer.c} (the main driver),
+@file{tree-vect-slp.c}, @file{tree-vect-stmts.c} and
+@file{tree-vect-data-refs.c}.
+
Autoparallelization. This pass splits the loop iteration space to run
into several threads. The pass is implemented in @file{tree-parloops.c}.
+Graphite is a loop transformation framework based on the polyhedral
+model. Graphite stands for Gimple Represented as Polyhedra. The
+internals of this infrastructure are documented in
+@w{@uref{http://gcc.gnu.org/wiki/Graphite}}. The passes working on
+this representation are implemented in the various @file{graphite-*}
+files.
+
@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}.
+and available vector operations. This pass is located in
+@file{tree-if-conv.c} and is described by @code{pass_if_conversion}.
@item Conditional constant propagation
@node RTL passes
@section RTL passes
-The following briefly describes the rtl generation and optimization
-passes that are run after tree optimization.
+The following briefly describes the RTL generation and optimization
+passes that are run after the Tree optimization passes.
@itemize @bullet
@item RTL generation
and @code{gencodes}, tell this pass which standard names are available
for use and which patterns correspond to them.
-@item Generate exception handling landing pads
+@item 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 @dfn{landing pads}. The code
-for this pass is located within @file{except.c}.
+for this pass is located in @file{except.c}.
-@item Cleanup control flow graph
+@item 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.
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. It is located in
-@file{fwprop.c}.
+being propagated into loops only on the second run. The code is
+located in @file{fwprop.c}.
@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}.
+The code for this pass is located in @file{cse.c}.
-@item Global common subexpression elimination.
+@item Global common subexpression elimination
This pass performs two
different types of GCSE depending on whether you are optimizing for
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}.
+when supported by the target. The code 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}.
+allocation. The code for this pass is located in @file{web.c}.
@item Instruction combination
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}.
+the machine description. The code 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}.
+used by the instruction to avoid the move instruction. The code is
+located in @file{regmove.c}.
-@item Optimize mode switching
+@item 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 source is located in @file{mode-switching.c}.
+completely target-specific. The code for this pass is located in
+@file{mode-switching.c}.
@cindex modulo scheduling
@cindex sms, swing, software pipelining
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}).
+immediately before instruction scheduling. The code for this pass is
+located in @file{modulo-sched.c}.
@item Instruction scheduling
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},
+allocation. The code for this 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}.
@itemize @bullet
@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}.
-
-@item
-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}.
+Register move optimizations. This pass makes some simple RTL code
+transformations which improve the subsequent register allocation. The
+source file is @file{regmove.c}.
@item
-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}.
+The integrated register allocator (@acronym{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 @file{ira.c}, @file{ira-build.c},
+@file{ira-costs.c}, @file{ira-conflicts.c}, @file{ira-color.c},
+@file{ira-emit.c}, @file{ira-lives}, plus header files @file{ira.h}
+and @file{ira-int.h} used for the communication between the allocator
+and the rest of the compiler and between the IRA files.
@cindex reloading
@item
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.
+location lists. The code is located in @file{var-tracking.c}.
@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}.
+delay slots of other instructions, usually jumps and calls. The code
+for this pass is located in @file{reorg.c}.
@item Branch shortening
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 @file{final.c}.
@item 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
-source file name is @file{reg-stack.c}.
+for the floating-point registers of the Intel 80387 coprocessor. The
+code for this pass is located in @file{reg-stack.c}.
@item Final
OSDN Git Service
