[PATCH] Updated pass documentation

[Daniel Berlin <dan at cgsoftware dot com>]

Since the last patch, I updated the gcse pass description to explain
that optimizing for size does one type of GCSE, and optimizing for
speed does a different one.  I also added that we use dwarf2out.c and
dwarf2asm.c for outputting DWARF2 symbol table format (which wasn't
mentioned at all in the list of symbol table formats and their files).


Index: gcc.texi
===================================================================
RCS file: /cvs/gcc/egcs/gcc/doc/gcc.texi,v
retrieving revision 1.6
diff -c -3 -p -w -B -b -r1.6 gcc.texi
*** gcc.texi	2001/06/09 18:03:11	1.6
--- gcc.texi	2001/06/11 22:12:15
*************** file is responsible for initialization, 
*** 3118,3131 ****
  closing files, and sequencing the passes.
  
  @cindex parsing pass
! The parsing pass is invoked only once, to parse the entire input.  The RTL
! intermediate code for a function is generated as the function is parsed, a
! statement at a time.  Each statement is read in as a syntax tree and then
! converted to RTL; then the storage for the tree for the statement is
! reclaimed.  Storage for types (and the expressions for their sizes),
! declarations, and a representation of the binding contours and how they nest,
! remain until the function is finished being compiled; these are all needed
! to output the debugging information.
  
  @findex rest_of_compilation
  @findex rest_of_decl_compilation
--- 3118,3129 ----
  closing files, and sequencing the passes.
  
  @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 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
  @findex rest_of_decl_compilation
*************** the assembler language.  All other compi
*** 3138,3144 ****
  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
  @ifset USING
  (@pxref{Inline,,An Inline Function is As Fast As a Macro}).
  @end ifset
--- 3136,3143 ----
  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).
  @ifset USING
  (@pxref{Inline,,An Inline Function is As Fast As a Macro}).
  @end ifset
*************** with @option{-d} options.
*** 3153,3161 ****
  @itemize @bullet
  @item
  Parsing.  This pass reads the entire text of a function definition,
! constructing partial syntax trees.  This and RTL generation are no longer
! truly separate passes (formerly they were), but it is easier to think
! of them as separate.
  
  The tree representation does not entirely follow C syntax, because it is
  intended to support other languages as well.
--- 3152,3158 ----
  @itemize @bullet
  @item
  Parsing.  This pass reads the entire text of a function definition,
! constructing a high level tree representation.
  
  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 
*** 3164,3180 ****
  tree node that represents an expression has a data type attached.
  Variables are represented as declaration nodes.
  
- @cindex constant folding
- @cindex arithmetic simplifications
- @cindex simplifications, arithmetic
- Constant folding and some arithmetic simplifications are also done
- during this pass.
- 
  The language-independent source files for parsing are
  @file{stor-layout.c}, @file{fold-const.c}, and @file{tree.c}.
  There are also header files @file{tree.h} and @file{tree.def}
  which define the format of the tree representation.@refill
  
  @c Avoiding overfull is tricky here.
  The source files to parse C are
  @file{c-parse.in},
--- 3161,3175 ----
  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{stor-layout.c}, @file{fold-const.c}, and @file{tree.c}.
  There are also header files @file{tree.h} and @file{tree.def}
  which define the format of the tree representation.@refill
  
+ @c Err, when we have cpplib docs, point the person there.
+ C Preprocessing, for language front ends, that want or require it, is
+ performed by cpplib, which is covered in seperate documentation.
+ 
  @c Avoiding overfull is tricky here.
  The source files to parse C are
  @file{c-parse.in},
*************** well.
*** 3206,3216 ****
  
  The file @file{c-common.c} is also used for all of the above languages.
  
  @cindex RTL generation
  @item
  RTL generation.  This is the conversion of syntax tree into RTL code.
- It is actually done statement-by-statement during parsing, but for
- most purposes it can be thought of as a separate pass.
  
  @cindex target-parameter-dependent code
  This is where the bulk of target-parameter-dependent code is found,
--- 3201,3224 ----
  
  The file @file{c-common.c} is also used for all of the above languages.
  
+ 
+ @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.  
+ @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.
+ 
  @cindex RTL generation
  @item
  RTL generation.  This is the conversion of syntax tree into RTL code.
  
  @cindex target-parameter-dependent code
  This is where the bulk of target-parameter-dependent code is found,
*************** Aside from debugging information output,
*** 3251,3257 ****
  refers to the tree structure representation of the function (only
  part of which is saved).
  
! @cindex inline, 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
--- 3259,3265 ----
  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 option @option{-dr} causes a debuggi
*** 3268,3273 ****
--- 3276,3296 ----
  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
+ Sibiling 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.
+ 
+ The source file of this pass is @file{sibcall.c}
+ 
+ The option @samp{-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.
+ 
  @cindex jump optimization
  @cindex unreachable code
  @cindex dead code
*************** the second conditional test.  The source
*** 3314,3339 ****
  @cindex constant propagation
  @item
  Common subexpression elimination.  This pass also does constant
! propagation.  Its source file is @file{cse.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 GCSE
! 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.  This pass also performs global constant
! and copy propagation.
  
! The source file for this pass is gcse.c.
  
  @opindex dG
  The option @option{-dG} causes a debugging dump of the RTL code after
--- 3337,3397 ----
  @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 SSA optimizations
+ @cindex Single Static Assignment optimizations
+ @item
+ Static Single Assignment (SSA) based optimization passes.
+ These passes utilize a form called Static Single Assignment. In SSA form,
+ each variable (pseudo register) is only set once, giving you def-use
+ and use-def chains for free, and enabling a lot more optimization
+ passes to be run in linear time.
+ Conversion to and from SSA form is handled by functions in
+ @file{ssa.c}.
+ 
+ The option @samp{-de} causes a debugging dump of the RTL code after
+ this pass.  This dump file's name is made by appending @samp{.ssa} to
+ the input file name.
+ @itemize @bullet
+ @cindex SSA DCE 
+ @cindex DCE, SSA based
+ @cindex dead code elimination
+ @item
+ Dead Code Elimination.  This pass performs elimination of code
+ considered unnecessary because it is never executed.  It operates in
+ linear time.
+ 
+ The option @samp{-dX} causes a debugging dump of the RTL code after
+ this pass. This dump file's name is made by appending @samp{.dce} to
+ the input file name.
+ @end itemize
  @cindex global common subexpression elimination
  @cindex constant propagation
  @cindex copy propagation
  @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-Revoise based GCSE does not). 
! 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 GCSE is done, code hoisting (aka
! unification) is also done.  LCM (Lazy code motion) based GCSE is based on
! the work of Knoop, Ruthing, and Steffen.  LCM based GCSE also does loop
! invariant code motion.  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
*************** and optionally does strength-reduction a
*** 3349,3354 ****
--- 3407,3413 ----
  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}.
+ Loop dependency analysis routines are contained in @file{dependence.c}.
  
  @opindex dL
  The option @option{-dL} causes a debugging dump of the RTL code after
*************** The option @option{-dc} causes a debuggi
*** 3400,3405 ****
--- 3459,3474 ----
  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{if-cvt.c}.
+ The option @samp{-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
*************** The option @option{-dR} causes a debuggi
*** 3489,3494 ****
--- 3558,3573 ----
  this pass.  This dump file's name is made by appending @samp{.sched2}
  to the input file name.
  
+ @cindex basic block reordering
+ @cindex reordering, block
+ @item
+ Basic block reordering.  This pass implements profile guided code
+ positioning. It is implemented in the file @file{bb-reorder.c}.
+ 
+ The option @samp{-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 cross-jumping
  @cindex no-op move instructions
  @item
*************** for communication between these files.
*** 3552,3559 ****
  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, and
! @file{dwarfout.c} for DWARF symbol table format.
  @end itemize
  
  Some additional files are used by all or many passes:
--- 3631,3639 ----
  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, and the files @file{dwarf2out.c} and
! @file{dwarf2asm.c} for DWARF2 symbol table format.
  @end itemize
  
  Some additional files are used by all or many passes:



-- 
"I went to the museum where they had all the heads and arms from
the statues that are in all the other museums.
"-Steven Wright