[PATCH] Revised^2 gcc.texi passes documentation update

[Daniel Berlin <dan at cgsoftware dot com>]

Added a little more on SSA (also described the -fssa option), fixed
the -fdce opindex problem Joseph pointed out, added spew.c and
semantics.c to the list of files involved in C++ parsing, and lastly,
added the list of files used in Tree->RTL conversion.

With a texinfo comment for someone who wants to work more on that part of the
docs that those are the files that *should* be involved (IE
that's their purpose, as the top of the file, and code, says and doe), but
there are many more because of how spread out this stuff got.
I have a neat little diagram i made with xfig that shows the overview
of the flow of gcc. Pretty simple, of course. We have a few boxes
that are language specific parsers at the top, that go to a box with
tree formation in it, which goes to a box with tree optimization in
it, which goes to rtl conversion, which goes to machine independent
basic RTL
optimizations (which include rtx based inlining, tail call merging,
jump stuff), which goes to either SSA optimizations (including dead
code elimination) , or machine independent main RTL optimizations
(PRE/loop optimizations/etc), which goes to machine specific code
optimization (combine), which goes to register allocation and
scheduling, which goes to assembly generation.

Should I submit it, or does no one care about stuff like
that?
I always see them in compiler books and docs for other ocmpilers, so i
figured i'd make one for gcc.

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/12 19:37:41
*************** 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,3136 ----
  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 files involved in transforming
! the trees into RTL are @file{expr.c}, @file{expmed.c}, and
! @file{stmt.c}. 
! @c Note, the above files aren't strictly the only files involved. It's
! @c all over the place (function.c, final.c,etc).  However, those are
! @c the files that are supposed to be directly involved, and have
! @c their purpose listed as such, so i've only listed them.
! 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
--- 3143,3150 ----
  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.
--- 3159,3165 ----
  @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},
--- 3168,3182 ----
  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},
*************** They are @file{parse.y},
*** 3194,3200 ****
  @file{except.c},@*
  @file{expr.c}, @file{init.c}, @file{lex.c},
  @file{method.c}, @file{ptree.c},@*
! @file{search.c}, @file{tree.c},
  @file{typeck2.c}, and
  @file{typeck.c}, along with header files @file{cp-tree.def},
  @file{cp-tree.h}, and @file{decl.h}.
--- 3196,3203 ----
  @file{except.c},@*
  @file{expr.c}, @file{init.c}, @file{lex.c},
  @file{method.c}, @file{ptree.c},@*
! @file{search.c}, @file{spew.c}, @*
! @file{semantics.c}, @file{tree.c},
  @file{typeck2.c}, and
  @file{typeck.c}, along with header files @file{cp-tree.def},
  @file{cp-tree.h}, and @file{decl.h}.
*************** 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,
--- 3209,3232 ----
  
  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
--- 3267,3273 ----
  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 ****
--- 3284,3305 ----
  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}
+ 
+ @opindex di
+ The option @option{-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
--- 3346,3416 ----
  @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
+ @opindex fssa
+ @item
+ Static Single Assignment (SSA) based optimization passes. The
+ SSA conversion passes (to/from) are turned on by the @option{-fssa}
+ option (it is also done automatically if you enable an SSA optimization pass).
+ 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}.
+ 
+ @opindex de
+ The option @option{-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
+ @opindex fdce
+ @item
+ Dead Code Elimination.  Turned on by the @option{-fdce} option. 
+ This pass performs elimination of code considered unnecessary because it
+ is never executed.  It operates in linear time.
+ 
+ @opindex dX
+ The option @option{-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). 
! 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}. 
  
  @opindex dG
  The option @option{-dG} causes a debugging dump of the RTL code after
*************** and optionally does strength-reduction a
*** 3349,3354 ****
--- 3426,3432 ----
  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 ****
--- 3478,3495 ----
  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}.
+ 
+ @opindex dE
+ The option @option{-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 ****
--- 3579,3595 ----
  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}.
+ 
+ @opindex dB
+ The option @option{-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:
--- 3653,3661 ----
  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'm writing a book.  I've got the page numbers done, so now I
just have to fill in the rest.
"-Steven Wright