This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[ast-optimizer-branch] Add documentation (1/5)
- From: Sebastian Pop <m1sp at csc dot liv dot ac dot uk>
- To: gcc-patches at gcc dot gnu dot org
- Cc: dnovillo at redhat dot com
- Date: Thu, 28 Feb 2002 20:03:03 +0000
- Subject: [ast-optimizer-branch] Add documentation (1/5)
Hi,
The following patch adds documentation on the simplify pass,
and on the c-call-graph.
Seb.
PS: Documentation comes first :-)
2002-02-28 Sebastian Pop <s.pop@laposte.net>
* Makefile.in : Add dependences for soft-eng.texi, trees.texi,
and simple.texi.
* c-tree.texi : Remane the node Trees in C-Trees.
Make the C-Trees node a section of Trees node from trees.texi,
and reorder sections hierarchy.
* gcc.texi : Add Soft-Eng in the main menu, and include the file
soft-eng.texi.
* gccint.texi : Change the description for the node Trees.
Include the file trees.texi instead of c-tree.texi
* invoke.texi : Add the option -fdump-call-graph.
* passes.texi : Add an item 'Tree simplification'.
Complete the sentence with the word 'option'.
Move the definition of 'LCM' at its first occurence.
* simple.texi : New file.
* soft-eng.texi : New file.
* trees.texi : New file.
Index: gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.701.2.13
diff -d -p -d -u -p -r1.701.2.13 Makefile.in
--- gcc/Makefile.in 2002/01/26 22:01:54 1.701.2.13
+++ gcc/Makefile.in 2002/02/28 01:56:19
@@ -2289,8 +2289,8 @@ $(docdir)/cpp.info: $(docdir)/cpp.texi $
$(docdir)/gcc.info: $(docdir)/gcc.texi $(docdir)/include/gcc-common.texi \
$(docdir)/frontends.texi $(docdir)/standards.texi \
$(docdir)/invoke.texi $(docdir)/extend.texi $(docdir)/md.texi \
- $(docdir)/objc.texi $(docdir)/gcov.texi $(docdir)/trouble.texi \
- $(docdir)/bugreport.texi $(docdir)/service.texi \
+ $(docdir)/objc.texi $(docdir)/gcov.texi $(docdir)/soft-eng.texi \
+ $(docdir)/trouble.texi $(docdir)/bugreport.texi $(docdir)/service.texi \
$(docdir)/contribute.texi $(docdir)/vms.texi \
$(docdir)/include/funding.texi $(docdir)/gnu.texi \
$(docdir)/include/gpl.texi $(docdir)/include/fdl.texi \
@@ -2301,7 +2301,8 @@ $(docdir)/gccint.info: $(docdir)/gccint.
$(docdir)/include/gcc-common.texi $(docdir)/contribute.texi \
$(docdir)/makefile.texi $(docdir)/configterms.texi \
$(docdir)/portability.texi $(docdir)/interface.texi \
- $(docdir)/passes.texi $(docdir)/c-tree.texi \
+ $(docdir)/passes.texi $(docdir)/trees.texi \
+ $(docdir)/c-tree.texi $(docdir)/simple.texi \
$(docdir)/rtl.texi $(docdir)/md.texi $(docdir)/tm.texi \
$(docdir)/hostconfig.texi $(docdir)/fragments.texi \
$(docdir)/configfiles.texi $(docdir)/collect2.texi \
Index: gcc/doc/c-tree.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/c-tree.texi,v
retrieving revision 1.14.2.2
diff -d -p -d -u -p -r1.14.2.2 c-tree.texi
--- gcc/doc/c-tree.texi 2002/01/26 22:04:16 1.14.2.2
+++ gcc/doc/c-tree.texi 2002/02/28 01:56:22
@@ -7,8 +7,8 @@
@c Trees
@c ---------------------------------------------------------------------
-@node Trees
-@chapter Trees: The intermediate representation used by the C and C++ front ends
+@node C-Trees
+@section Trees: The intermediate representation used by the C and C++ front ends
@cindex Trees
@cindex C/C++ Internal Representation
@@ -62,7 +62,7 @@ should submit your patches for inclusion
@c ---------------------------------------------------------------------
@node Deficiencies
-@section Deficiencies
+@subsection Deficiencies
There are many places in which this document is incomplet and incorrekt.
It is, as of yet, only @emph{preliminary} documentation.
@@ -72,7 +72,7 @@ It is, as of yet, only @emph{preliminary
@c ---------------------------------------------------------------------
@node Tree overview
-@section Overview
+@subsection Overview
@cindex tree
@findex TREE_CODE
@@ -84,8 +84,8 @@ we will refer to trees in ordinary type,
font}, except when talking about the actual C type @code{tree}.
You can tell what kind of node a particular tree is by using the
-@code{TREE_CODE} macro. Many, many macros take a trees as input and
-return trees as output. However, most macros require a certain kinds of
+@code{TREE_CODE} macro. Many, many macros take a tree as input and
+return trees as output. However, most macros require a certain kind of
tree node as input. In other words, there is a type-system for trees,
but it is not reflected in the C type-system.
@@ -169,7 +169,7 @@ bug.
@c ---------------------------------------------------------------------
@node Macros and Functions
-@subsection Trees
+@subsubsection Trees
@cindex tree
This section is not here yet.
@@ -179,7 +179,7 @@ This section is not here yet.
@c ---------------------------------------------------------------------
@node Identifiers
-@subsection Identifiers
+@subsubsection Identifiers
@cindex identifier
@cindex name
@tindex IDENTIFIER_NODE
@@ -225,7 +225,7 @@ operator converts.
@c ---------------------------------------------------------------------
@node Containers
-@subsection Containers
+@subsubsection Containers
@cindex container
@cindex list
@cindex vector
@@ -260,7 +260,7 @@ The elements are indexed from zero.
@c ---------------------------------------------------------------------
@node Types
-@section Types
+@subsection Types
@cindex type
@cindex pointer
@cindex reference
@@ -601,7 +601,7 @@ in hand, using @code{same_type_p}.
@c ---------------------------------------------------------------------
@node Scopes
-@section Scopes
+@subsection Scopes
@cindex namespace, class, scope
The root of the entire intermediate representation is the variable
@@ -625,7 +625,7 @@ keywords.)
@c ---------------------------------------------------------------------
@node Namespaces
-@subsection Namespaces
+@subsubsection Namespaces
@cindex namespace
@tindex NAMESPACE_DECL
@@ -698,7 +698,7 @@ This function cannot be used with namesp
@c ---------------------------------------------------------------------
@node Classes
-@subsection Classes
+@subsubsection Classes
@cindex class
@tindex RECORD_TYPE
@tindex UNION_TYPE
@@ -823,7 +823,7 @@ overloaded.
@c ---------------------------------------------------------------------
@node Declarations
-@section Declarations
+@subsection Declarations
@cindex declaration
@cindex variable
@cindex type declaration
@@ -998,7 +998,7 @@ Back ends can safely ignore these nodes.
@c ---------------------------------------------------------------------
@node Functions
-@section Functions
+@subsection Functions
@cindex function
@tindex FUNCTION_DECL
@tindex OVERLOAD
@@ -1060,7 +1060,7 @@ function, and the back end must take app
@c ---------------------------------------------------------------------
@node Function Basics
-@subsection Function Basics
+@subsubsection Function Basics
@cindex constructor
@cindex destructor
@cindex copy constructor
@@ -1263,7 +1263,7 @@ This predicate holds if the function an
@c ---------------------------------------------------------------------
@node Function Bodies
-@subsection Function Bodies
+@subsubsection Function Bodies
@cindex function body
@cindex statements
@tindex ASM_STMT
@@ -1669,7 +1669,7 @@ The @code{WHILE_BODY} is the body of the
@c Attributes
@c ---------------------------------------------------------------------
@node Attributes
-@section Attributes in trees
+@subsection Attributes in trees
@cindex attributes
Attributes, as specified using the @code{__attribute__} keyword, are
@@ -1701,7 +1701,7 @@ This macro returns the attributes on the
@c ---------------------------------------------------------------------
@node Expression trees
-@section Expressions
+@subsection Expressions
@cindex expression
@findex TREE_OPERAND
@tindex INTEGER_CST
Index: gcc/doc/gcc.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/gcc.texi,v
retrieving revision 1.30.4.2
diff -d -p -d -u -p -r1.30.4.2 gcc.texi
--- gcc/doc/gcc.texi 2002/01/26 22:04:17 1.30.4.2
+++ gcc/doc/gcc.texi 2002/02/28 01:56:22
@@ -165,6 +165,7 @@ Introduction, gccint, GNU Compiler Colle
* C++ Extensions:: GNU extensions to the C++ language.
* Objective-C:: GNU Objective-C runtime features.
* Gcov:: gcov: a GCC test coverage program.
+* Soft-Eng:: Software engineering tools.
* Trouble:: If you have trouble using GCC.
* Bugs:: How, why and where to report bugs.
* Service:: How to find suppliers of support for GCC.
@@ -189,6 +190,7 @@ Introduction, gccint, GNU Compiler Colle
@include extend.texi
@include objc.texi
@include gcov.texi
+@include soft-eng.texi
@include trouble.texi
@include bugreport.texi
@include service.texi
Index: gcc/doc/gccint.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/gccint.texi,v
retrieving revision 1.1.2.2
diff -d -p -d -u -p -r1.1.2.2 gccint.texi
--- gcc/doc/gccint.texi 2002/01/26 22:04:17 1.1.2.2
+++ gcc/doc/gccint.texi 2002/02/28 01:56:22
@@ -161,7 +161,7 @@ Additional tutorial information is linke
* Languages:: Languages for which GCC front ends are written.
* Source Tree:: GCC source tree structure and build system.
* Passes:: Order of passes, what they do, and what each file is for.
-* Trees:: The source representation used by the C and C++ front ends.
+* Trees:: Source representations used by front ends.
* RTL:: The intermediate representation that most passes work on.
* Machine Desc:: How to write machine description instruction patterns.
* Target Macros:: How to write the machine description C macros and functions.
@@ -188,7 +188,7 @@ Additional tutorial information is linke
@include languages.texi
@include sourcebuild.texi
@include passes.texi
-@include c-tree.texi
+@include trees.texi
@include rtl.texi
@include md.texi
@include tm.texi
Index: gcc/doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.39.4.9
diff -d -p -d -u -p -r1.39.4.9 invoke.texi
--- gcc/doc/invoke.texi 2002/01/26 22:04:18 1.39.4.9
+++ gcc/doc/invoke.texi 2002/02/28 01:56:25
@@ -249,6 +249,7 @@ in the following sections.
-fdump-tree-inlined@r{[}-@var{n}@r{]} @gol
-fdump-tree-cfg -fdump-tree-graphviz -fdump-tree-ssa@r{[}-@var{n}@r{]} @gol
-fdump-tree-simple@r{[}-unparse@r{]} @gol
+-fdump-call-graph @gol
-fmem-report -fpretend-float @gol
-fprofile-arcs -ftest-coverage -ftime-report @gol
-g -g@var{level} -gcoff -gdwarf -gdwarf-1 -gdwarf-1+ -gdwarf-2 @gol
Index: gcc/doc/passes.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/passes.texi,v
retrieving revision 1.6.2.2
diff -d -p -d -u -p -r1.6.2.2 passes.texi
--- gcc/doc/passes.texi 2001/12/30 03:26:56 1.6.2.2
+++ gcc/doc/passes.texi 2002/02/28 01:56:25
@@ -121,6 +121,9 @@ and
@file{c-pragma.h},
are also used for all of the above languages.
+@cindex Tree simplification
+@item
+Tree simplification.
@cindex Tree optimization
@item
@@ -285,9 +288,11 @@ the input file name.
@cindex conditional constant propagation
@opindex fssa-ccp
@item
-SSA Conditional Constant Propagation. Turned on by the @option{-fssa-ccp}
+SSA Conditional Constant Propagation. Turned on by the @option{-fssa-ccp}
+option.
SSA Aggressive Dead Code Elimination. Turned on by the @option{-fssa-dce}
-option. This pass performs conditional constant propagation to simplify
+option.
+This pass performs conditional constant propagation to simplify
instructions including conditional branches. This pass is more aggressive
than the constant propgation done by the CSE and GCSE pases, but operates
in linear time.
@@ -333,14 +338,14 @@ the input file name.
@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).
+size or not (LCM (lazy code motion) 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
+If you are optimizing for speed, LCM 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.
Index: gcc/doc/simple.texi
===================================================================
RCS file: simple.texi
diff -N simple.texi
--- /dev/null Tue May 5 13:32:27 1998
+++ gcc/doc/simple.texi Wed Feb 27 17:56:25 2002
@@ -0,0 +1,128 @@
+@c Copyright (C) 2OO2 Free Software Foundation, Inc.
+@c This is part of the GCC manual.
+@c For copying conditions, see the file gcc.texi.
+
+@node Simple
+@section Simple
+@cindex Simple
+Simple is an intermediate representation based on the structure of trees.
+Simple was designed in order to reduce the number of possible cases to be
+analysed by simplifying expressions, and that without changing the initial
+semantic of the program.
+
+@menu
+* Simple-Syntax:: A subset of the languages syntax.
+* Benefits:: Interesting properties of Simple.
+* Work-State:: Current and future work.
+* References:: Some good papers.
+@end menu
+
+
+@node Simple-Syntax
+@subsection A reduced syntax for Simple
+@cindex Simple syntax
+Simple is a subset of the original syntax of the language. The simplify
+pass constructs a semantic equivalent program based on a minimal subset of
+the language syntax.
+@example
+For example the post increment allowed by the C grammar can be very well
+transformed in an affectation and an addition of one, without any loss
+of information.
+@end example
+@noindent
+
+The set of syntax operators is different from a language to another, and worse,
+they can have for a same syntax operator different semantics. The simplify pass
+consists of factoring all these differences in a common subset of primitives
+on which we'll be able to perform analyses and optimisations.
+
+@example
+For example, the C++ language defines a mechanism to handle exceptions,
+but this control flow mechanism is not present in the C language.
+@end example
+@noindent
+An interesting thing to be noted in this example is that the exception mechanism
+can be simulated in C by another set of syntactic expressions. That means that
+the C++ throw can be handled by a smaller syntax set that belongs to the C
+language. However in order to apply such a transformation, we need to prouve
+that the program has not lost information.
+
+@node Benefits
+@subsection What are the benefits of adopting Simple?
+From the simplification pass we obtain a program that has the following
+features:
+@itemize @bullet
+@item
+Control flow is structured and explicit. The number of loop primitives
+is reduced. The control flow is simplified by suppression of breaks,
+continues and gotos. This allows much more optimisations on loops since
+their structure becomes more regular.
+@item
+Accesses to structures and to arrays are retained and not broken to lower
+level statements. Thus, informations like the size of arrays and types is
+not lost. This allows the alias and dependence analysis to work properly
+on Simple trees. Function accesses to arrays is also simplified avoiding
+situations where these functions have side effects. A later pass reconstruct
+from Simple trees the correct access functions in function of loop indices.
+This allows the dependence pass to work on more cases.
+@item
+Data flow structure is not modified. The order of expression evaluations is
+not modified by the simplification pass. This is a crucial issue in the
+validation of our transformations, since floating point arithmetic depends
+on it.
+@end itemize
+
+@node Work-State
+@subsection Work state
+@subsubsection What Simple does for the moment?
+The only transformations we implemented up to now are based on the C/C++
+front-ends, and they perform :
+@itemize @bullet
+@item
+Arithmetic simplifications.
+@item
+Pointer simplifications.
+@end itemize
+
+The next step is to reduce the number of loop structures to a minimal set :
+that is almost implemented to reduce all loop structures to a for statement,
+but in the case of a do_stmt we have to restructure loop indices in order to
+avoid to duplicate the loop body. Thus this simplification will be done after
+the retrieval of the loop indices and their normalisation (here normalisation
+means : a single induction variable by loop, if there is one; a step of one,
+and the induction variable starts at zero.)
+
+A further step will be to extend the Simple representation to other front-ends
+like Java and Fortran. This should avoid the rewriting of analyses and
+optimisations performed on the front end. This step is not yet implemented,
+but the way it will be designed will influence optimisations implementation.
+
+@subsubsection Future work
+Further analyses and optimisations :
+@itemize @bullet
+@item
+Search of loop induction variables.
+@item
+Normalisation of array access functions.
+@item
+Construction of the loop dependence graph : @file{dependence.c} to be readapted
+in order to take the results from tree-cfg (control flow graph), tree-ssa
+(static single assignment) and from alias analysis.
+@item
+Goto, break and continue elimination by transformation of the loop structure.
+@item
+Loop transformations for temporal locality of data references.
+@end itemize
+
+@node References
+@subsection References
+
+"Designing the McCAT Compiler Based on a Family of Structured
+Intermediate Representations,"
+L. Hendren, C. Donawa, M. Emami, G. Gao, Justiani, and B. Sridharan,
+Proceedings of the 5th International Workshop on Languages and
+Compilers for Parallel Computing, no. 757 in Lecture Notes in
+Computer Science, New Haven, Connecticut, pp. 406-420,
+Springer-Verlag, August 3-5, 1992.
+@uref{http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html}
+
Index: gcc/doc/soft-eng.texi
===================================================================
RCS file: soft-eng.texi
diff -N soft-eng.texi
--- /dev/null Tue May 5 13:32:27 1998
+++ gcc/doc/soft-eng.texi Wed Feb 27 17:56:25 2002
@@ -0,0 +1,150 @@
+@c Copyright (C) 2OO2 Free Software Foundation, Inc.
+@c This is part of the GCC manual.
+@c For copying conditions, see the file gcc.texi.
+
+@node Soft-Eng
+@chapter Software Engineering Toolkit
+
+GCC provides a set of software engineering tools. They can be used in
+conjunction with GCC to construct better code.
+
+@menu
+* Call graph:: Construction of the function call graph.
+* Metrics:: Measure of function's complexity.
+@end menu
+
+
+@node Call graph
+@section Function Call Graph
+
+The call graph represents the control flow through the program at the
+function level. Each function definition is represented by a node, and
+each call from the body of the function is represented by an edge. Thus
+the construction of the call graph provides a way to visualise the structure
+of calls as they may occur in the execution of a program. It can help to
+find defined but not used functions by identifying components never reached
+from the main function.
+
+For the moment only the C front-end can dump the call graph.
+
+@menu
+* Construction:: How to construct the call graph.
+* Output format:: Description of the output files.
+@end menu
+
+@node Construction
+@subsection Call Graph Construction
+
+The construction of the call graph can be done by compiling each source file
+with the flag @option{-fdump-call-graph}. This will generate a file called
+@file{@var{sourcefile}.xml} containing the call graph for all compiled functions
+in this file. Thus the call graph does not contain declarations and calls
+from the code deleted by the preprocessor.
+
+At the end of the compilation all these files can be assembled into a single one.
+@smallexample
+$ make CFLAGS='-fdump-call-graph'
+$ find . -regex .*\\.xml -exec cat @{@} \; >> overall-graph.xml
+@end smallexample
+@noindent
+
+However the result may not be a valid XML file, since some nodes are missing.
+That occurs whenever the code contains calls to a library. A solution to this
+problem could be the generation of the call graph of the library, or the
+generation of the nodes corresponding to the library's interface (that is all
+the visible functions without their outgoing edges).
+
+The last step consists of adding the tags @code{<functions>} and @code{</functions>} around
+caller nodes, and including the DTD in the file header.
+
+@node Output format
+@subsection Output File Format
+
+The output is a file describing the graph in XML. The corresponding DTD is:
+@example
+<?xml version=\"1.0\"?>
+<!DOCTYPE functions [
+ <!ELEMENT file (caller|gvar)*>
+ <!ELEMENT gvar EMPTY>
+ <!ATTLIST gvar vid ID #REQUIRED>
+ <!ELEMENT caller ((uvar|callee|caller)*, stats)>
+ <!ATTLIST caller fid ID #REQUIRED>
+ <!ELEMENT callee EMPTY>
+ <!ATTLIST callee fid IDREF #REQUIRED>
+ <!ELEMENT uvar EMPTY>
+ <!ATTLIST uvar vid IDREF #REQUIRED>
+ <!ELEMENT stats EMPTY>
+ <!ATTLIST stats calls CDATA>
+ <!ATTLIST stats decisions CDATA>
+ <!ATTLIST stats stmts CDATA>
+ <!ATTLIST stats Gilb CDATA>
+ <!ATTLIST stats CFG-edges CDATA>
+ <!ATTLIST stats CFG-BB CDATA>
+ <!ATTLIST stats McCabe CDATA>
+]>
+@end example
+@noindent
+
+@node Metrics
+@section Software Metrics
+
+Software metrics provide a way to quantify software characteristics such as
+complexity, readability or maintainability. These quantities can be used in
+order to understand and explain error histories, compare software projects,
+predicting software costs and error rates. If software metrics prove to be
+reliable indicators, they could be used by programmers for self-checking of
+modules, and by managerial or quality assurance staff to check the quality
+of software.
+
+@menu
+* McCabe:: Control flow complexity.
+* Gilb:: Logical complexity.
+* References:: Some papers.
+@end menu
+
+@node McCabe
+@subsection McCabe Metric : Control Flow Complexity
+
+McCabe proposed in 1976 to measure the complexity of a program by calculating
+the number of regions in the planar representation of the Control Flow Graph
+(CFG). Euler has shown that in a planar graph, the number of regions plus
+the number of vertices minus the number of edges is a constant equal to 2.
+That gives a way to calculate the number of regions given the number of basic
+blocks and the number of edges in the CFG :
+@example
+nb_regions = nb_edges - nb_basic_blocks + 2.
+@end example
+@noindent
+
+This metric is dirrectly calculated when the flag @option{-fdump-call-graph}
+is passed to GCC, and it is printed as an attribute @code{McCabe} of the node
+@code{<stats>}. The number of basic blocks and the number of edges in the control
+flow graph are also printed as attributes @code{CFG-BB} and @code{CFG-edges} of the
+node @code{<stats>}.
+
+@node Gilb
+@subsection Gilb Metric : Logical Complexity
+
+This metric use the notion of decision point, that is either an if statement,
+a loop condition, or a switch.
+The absolute logical complexity is the number of decision points in a function.
+The relative logical complexity is the number of decision points divided by the
+total number of statements in the function.
+
+This metric is dirrectly calculated when the flag @option{-fdump-call-graph}
+is passed to GCC, and the relative logical complexity is printed as an attribute
+@code{Gilb} of the node @code{<stats>}. The total number of statements and the number of
+decisions points are printed as attributes @code{stmts} and @code{decisions} of
+the node @code{<stats>}
+
+
+@node References
+@subsection References
+@enumerate
+@item
+McCabe, T.J. (1976) 'A Complexity Measure', IEEE Transactions on Software
+Engineering, 2(4), 308-320.
+@item
+Gilb, T. (1977) Software Metrics, Winthrop, Cambridge, Massachusetts, USA.
+@end enumerate
+@noindent
Index: gcc/doc/trees.texi
===================================================================
RCS file: trees.texi
diff -N trees.texi
--- /dev/null Tue May 5 13:32:27 1998
+++ gcc/doc/trees.texi Wed Feb 27 17:56:25 2002
@@ -0,0 +1,102 @@
+@c Copyright (c) 2002 Free Software Foundation, Inc.
+@c Free Software Foundation, Inc.
+@c This is part of the GCC manual.
+@c For copying conditions, see the file gcc.texi.
+
+@c ---------------------------------------------------------------------
+@c Trees
+@c ---------------------------------------------------------------------
+
+@node Trees
+@chapter Intermediate representations used by front ends
+@cindex AST
+@cindex Abstract Syntax Trees
+@cindex High Level Intermediate Representations
+
+This chapter documents the internal representations used by GCC's front
+ends. When presented with a source program, GCC parses the program,
+performs semantic analysis (including the generation of error messages),
+and then produces an internal representation specific to the front end.
+This representation contains a complete representation for the entire
+translation unit provided as input to the front end. This representation
+could also be used in the creation of source browsers, intelligent editors,
+automatic documentation generators, interpreters, and any other programs
+needing the ability to process C, C++, Objective-C, Ada, CHILL, Fortran,
+or Java@.
+
+A simplification of these representations is performed in order to provide
+a unique high level representation. High level analyzers extract then
+information from this later representation and propagate it in the rest of
+compilation stages. Results of high level optimisations can either be
+unparsed in a file, or processed by a code-generator in order to produce
+machine code@.
+
+@menu
+* Ada-Trees:: The source representation used by the Ada front end.
+* C-Trees:: The source representation used by the C and C++ front ends.
+* Java-Trees:: The source representation used by the Java front end.
+* F77-Trees:: The source representation used by the Fortran77 front end.
+* Simple:: Simplifying the high level representation.
+* Analysers:: Extracting informations from Simple.
+* Optimizers:: Source to source transformations.
+@end menu
+
+@node Ada-Trees
+@section Ada Trees
+@cindex Ada trees
+Not documented yet. Volunteers?
+
+@include c-tree.texi
+
+@node Java-Trees
+@section Java Trees
+@cindex Java trees
+Not documented yet. Volunteers?
+
+@node F77-Trees
+@section Fortran77 Trees
+@cindex F77 trees
+Not documented yet. Volunteers?
+
+@include simple.texi
+
+@node Analysers
+@section Analysers
+At the tree level we handle a structure that represents the exact meaning
+of the program. This can be verified by the fact that we are able to unparse
+the tree to a semantic equivalent program. Thus the information extracted
+at this level reflects exactly the original semantic of the program.
+
+@menu
+* Tree-CFG:: The control flow graph.
+* Alias:: Alias analysis.
+* Loop Dependences:: Dependence graph construction.
+@end menu
+
+@node Tree-CFG
+@subsection The control flow graph
+@cindex Tree Control Flow Graph
+Not documented yet.
+
+@node Alias
+@subsection Alias analysis
+@cindex Alias analysis
+Not documented yet.
+
+@node Loop Dependences
+@subsection Dependence graph
+@cindex Dependence graph
+Not documented yet.
+
+@node Optimizers
+@section Optimizers
+
+@menu
+* Tree-SSA:: Static Single Assignment.
+@end menu
+
+@node Tree-SSA
+@subsection Static Single Assignment
+@cindex Tree Static Single Assignment
+Not documented yet.
+