passes.texi

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

It does so by storing the values of these computations to a bank
of temporary variables that are rotated at the end of loop.  To avoid
the need for this rotation, the loop is then unrolled and the copies
of the loop body are rewritten to use the appropriate version of
the temporary variable.  This pass is located in @file{tree-predcom.c}
and described by @code{pass_predcom}.

@item Array prefetching

This pass issues prefetch instructions for array references inside
loops.  The pass is located in @file{tree-ssa-loop-prefetch.c} and
described by @code{pass_loop_prefetch}.

@item Reassociation

This pass rewrites arithmetic expressions to enable optimizations that
operate on them, like redundancy elimination and vectorization.  The
pass is located in @file{tree-ssa-reassoc.c} and described by
@code{pass_reassoc}.

@item Optimization of @code{stdarg} functions

This pass tries to avoid the saving of register arguments into the
stack on entry to @code{stdarg} functions.  If the function doesn't
use any @code{va_start} macros, no registers need to be saved.  If
@code{va_start} macros are used, the @code{va_list} variables don't
escape the function, it is only necessary to save registers that will
be used in @code{va_arg} macros.  For instance, if @code{va_arg} is
only used with integral types in the function, floating point
registers don't need to be saved.  This pass is located in
@code{tree-stdarg.c} and described by @code{pass_stdarg}.

@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
@file{stmt.c},
@file{calls.c},
@file{expr.c},
@file{explow.c},
@file{expmed.c},
@file{function.c},
@file{optabs.c}
and @file{emit-rtl.c}.
Also, the file
@file{insn-emit.c}, generated from the machine description by the
program @code{genemit}, is used in this pass.  The header file
@file{expr.h} is used for communication within this pass.

@findex genflags
@findex gencodes
The header files @file{insn-flags.h} and @file{insn-codes.h},
generated from the machine description by the programs @code{genflags}
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

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

@item Cleanup control flow graph

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

@item Forward propagation of single-def values

This pass attempts to remove redundant computation by substituting
variables that come from a single definition, and
seeing if the result can be simplified.  It performs copy propagation
and addressing mode selection.  The pass is run twice, with values
being propagated into loops only on the second run.  It 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}.

@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).
When optimizing for size, GCSE is done using Morel-Renvoise Partial
Redundancy Elimination, with the exception that it does not try to move
invariants out of loops---that is left to  the loop optimization pass.
If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
well as load motion.
If you are optimizing for speed, LCM (lazy code motion) based GCSE is
done.  LCM is based on the work of Knoop, Ruthing, and Steffen.  LCM
based GCSE also does loop invariant code motion.  We also perform load
and store motion when optimizing for speed.
Regardless of which type of GCSE is used, the GCSE pass also performs
global constant and  copy propagation.
The source file for this pass is @file{gcse.c}, and the LCM routines
are in @file{lcm.c}.

@item Loop optimization

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

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

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

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

Source files are @file{reload.c} and @file{reload1.c}, plus the header
@file{reload.h} used for communication between them.
@end itemize

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

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

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

@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

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

@item Final

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.

@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