[GCC 4.8] Initial check-in of GCC 4.8.0

Change-Id: I0719d8a6d0f69b367a6ab6f10eb75622dbf12771

1 files changed, 919 insertions, 0 deletions

diff --git a/gcc-4.8/gcc/doc/tree-ssa.texi b/gcc-4.8/gcc/doc/tree-ssa.texi
new file mode 100644
index 000000000..fc479d636
--- /dev/null
+++ b/gcc-4.8/gcc/doc/tree-ssa.texi
@@ -0,0 +1,919 @@
+@c Copyright (C) 2004-2013 Free Software Foundation, Inc.
+@c This is part of the GCC manual.
+@c For copying conditions, see the file gcc.texi.
+
+@c ---------------------------------------------------------------------
+@c Tree SSA
+@c ---------------------------------------------------------------------
+
+@node Tree SSA
+@chapter Analysis and Optimization of GIMPLE tuples
+@cindex Tree SSA
+@cindex Optimization infrastructure for GIMPLE
+
+GCC uses three main intermediate languages to represent the program
+during compilation: GENERIC, GIMPLE and RTL@.  GENERIC is a
+language-independent representation generated by each front end.  It
+is used to serve as an interface between the parser and optimizer.
+GENERIC is a common representation that is able to represent programs
+written in all the languages supported by GCC@.
+
+GIMPLE and RTL are used to optimize the program.  GIMPLE is used for
+target and language independent optimizations (e.g., inlining,
+constant propagation, tail call elimination, redundancy elimination,
+etc).  Much like GENERIC, GIMPLE is a language independent, tree based
+representation.  However, it differs from GENERIC in that the GIMPLE
+grammar is more restrictive: expressions contain no more than 3
+operands (except function calls), it has no control flow structures
+and expressions with side-effects are only allowed on the right hand
+side of assignments.  See the chapter describing GENERIC and GIMPLE
+for more details.
+
+This chapter describes the data structures and functions used in the
+GIMPLE optimizers (also known as ``tree optimizers'' or ``middle
+end'').  In particular, it focuses on all the macros, data structures,
+functions and programming constructs needed to implement optimization
+passes for GIMPLE@.
+
+@menu
+* Annotations::         Attributes for variables.
+* SSA Operands::        SSA names referenced by GIMPLE statements.
+* SSA::                 Static Single Assignment representation.
+* Alias analysis::      Representing aliased loads and stores.
+* Memory model::        Memory model used by the middle-end.
+@end menu
+
+@node Annotations
+@section Annotations
+@cindex annotations
+
+The optimizers need to associate attributes with variables during the
+optimization process.  For instance, we need to know whether a
+variable has aliases.  All these attributes are stored in data
+structures called annotations which are then linked to the field
+@code{ann} in @code{struct tree_common}.
+
+Presently, we define annotations for variables (@code{var_ann_t}).
+Annotations are defined and documented in @file{tree-flow.h}.
+
+
+@node SSA Operands
+@section SSA Operands
+@cindex operands
+@cindex virtual operands
+@cindex real operands
+@findex update_stmt
+
+Almost every GIMPLE statement will contain a reference to a variable
+or memory location.  Since statements come in different shapes and
+sizes, their operands are going to be located at various spots inside
+the statement's tree.  To facilitate access to the statement's
+operands, they are organized into lists associated inside each
+statement's annotation.  Each element in an operand list is a pointer
+to a @code{VAR_DECL}, @code{PARM_DECL} or @code{SSA_NAME} tree node.
+This provides a very convenient way of examining and replacing
+operands.
+
+Data flow analysis and optimization is done on all tree nodes
+representing variables.  Any node for which @code{SSA_VAR_P} returns
+nonzero is considered when scanning statement operands.  However, not
+all @code{SSA_VAR_P} variables are processed in the same way.  For the
+purposes of optimization, we need to distinguish between references to
+local scalar variables and references to globals, statics, structures,
+arrays, aliased variables, etc.  The reason is simple, the compiler
+can gather complete data flow information for a local scalar.  On the
+other hand, a global variable may be modified by a function call, it
+may not be possible to keep track of all the elements of an array or
+the fields of a structure, etc.
+
+The operand scanner gathers two kinds of operands: @dfn{real} and
+@dfn{virtual}.  An operand for which @code{is_gimple_reg} returns true
+is considered real, otherwise it is a virtual operand.  We also
+distinguish between uses and definitions.  An operand is used if its
+value is loaded by the statement (e.g., the operand at the RHS of an
+assignment).  If the statement assigns a new value to the operand, the
+operand is considered a definition (e.g., the operand at the LHS of
+an assignment).
+
+Virtual and real operands also have very different data flow
+properties.  Real operands are unambiguous references to the
+full object that they represent.  For instance, given
+
+@smallexample
+@{
+  int a, b;
+  a = b
+@}
+@end smallexample
+
+Since @code{a} and @code{b} are non-aliased locals, the statement
+@code{a = b} will have one real definition and one real use because
+variable @code{a} is completely modified with the contents of
+variable @code{b}.  Real definition are also known as @dfn{killing
+definitions}.  Similarly, the use of @code{b} reads all its bits.
+
+In contrast, virtual operands are used with variables that can have
+a partial or ambiguous reference.  This includes structures, arrays,
+globals, and aliased variables.  In these cases, we have two types of
+definitions.  For globals, structures, and arrays, we can determine from
+a statement whether a variable of these types has a killing definition.
+If the variable does, then the statement is marked as having a
+@dfn{must definition} of that variable.  However, if a statement is only
+defining a part of the variable (i.e.@: a field in a structure), or if we
+know that a statement might define the variable but we cannot say for sure,
+then we mark that statement as having a @dfn{may definition}.  For
+instance, given
+
+@smallexample
+@{
+  int a, b, *p;
+
+  if (@dots{})
+    p = &a;
+  else
+    p = &b;
+  *p = 5;
+  return *p;
+@}
+@end smallexample
+
+The assignment @code{*p = 5} may be a definition of @code{a} or
+@code{b}.  If we cannot determine statically where @code{p} is
+pointing to at the time of the store operation, we create virtual
+definitions to mark that statement as a potential definition site for
+@code{a} and @code{b}.  Memory loads are similarly marked with virtual
+use operands.  Virtual operands are shown in tree dumps right before
+the statement that contains them.  To request a tree dump with virtual
+operands, use the @option{-vops} option to @option{-fdump-tree}:
+
+@smallexample
+@{
+  int a, b, *p;
+
+  if (@dots{})
+    p = &a;
+  else
+    p = &b;
+  # a = VDEF <a>
+  # b = VDEF <b>
+  *p = 5;
+
+  # VUSE <a>
+  # VUSE <b>
+  return *p;
+@}
+@end smallexample
+
+Notice that @code{VDEF} operands have two copies of the referenced
+variable.  This indicates that this is not a killing definition of
+that variable.  In this case we refer to it as a @dfn{may definition}
+or @dfn{aliased store}.  The presence of the second copy of the
+variable in the @code{VDEF} operand will become important when the
+function is converted into SSA form.  This will be used to link all
+the non-killing definitions to prevent optimizations from making
+incorrect assumptions about them.
+
+Operands are updated as soon as the statement is finished via a call
+to @code{update_stmt}.  If statement elements are changed via
+@code{SET_USE} or @code{SET_DEF}, then no further action is required
+(i.e., those macros take care of updating the statement).  If changes
+are made by manipulating the statement's tree directly, then a call
+must be made to @code{update_stmt} when complete.  Calling one of the
+@code{bsi_insert} routines or @code{bsi_replace} performs an implicit
+call to @code{update_stmt}.
+
+@subsection Operand Iterators And Access Routines
+@cindex Operand Iterators
+@cindex Operand Access Routines
+
+Operands are collected by @file{tree-ssa-operands.c}.  They are stored
+inside each statement's annotation and can be accessed through either the
+operand iterators or an access routine.
+
+The following access routines are available for examining operands:
+
+@enumerate
+@item @code{SINGLE_SSA_@{USE,DEF,TREE@}_OPERAND}: These accessors will return
+NULL unless there is exactly one operand matching the specified flags.  If
+there is exactly one operand, the operand is returned as either a @code{tree},
+@code{def_operand_p}, or @code{use_operand_p}.
+
+@smallexample
+tree t = SINGLE_SSA_TREE_OPERAND (stmt, flags);
+use_operand_p u = SINGLE_SSA_USE_OPERAND (stmt, SSA_ALL_VIRTUAL_USES);
+def_operand_p d = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_ALL_DEFS);
+@end smallexample
+
+@item @code{ZERO_SSA_OPERANDS}: This macro returns true if there are no
+operands matching the specified flags.
+
+@smallexample
+if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+  return;
+@end smallexample
+
+@item @code{NUM_SSA_OPERANDS}: This macro Returns the number of operands
+matching 'flags'.  This actually executes a loop to perform the count, so
+only use this if it is really needed.
+
+@smallexample
+int count = NUM_SSA_OPERANDS (stmt, flags)
+@end smallexample
+@end enumerate
+
+
+If you wish to iterate over some or all operands, use the
+@code{FOR_EACH_SSA_@{USE,DEF,TREE@}_OPERAND} iterator.  For example, to print
+all the operands for a statement:
+
+@smallexample
+void
+print_ops (tree stmt)
+@{
+  ssa_op_iter;
+  tree var;
+
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_OPERANDS)
+    print_generic_expr (stderr, var, TDF_SLIM);
+@}
+@end smallexample
+
+
+How to choose the appropriate iterator:
+
+@enumerate
+@item Determine whether you are need to see the operand pointers, or just the
+trees, and choose the appropriate macro:
+
+@smallexample
+Need            Macro:
+----            -------
+use_operand_p   FOR_EACH_SSA_USE_OPERAND
+def_operand_p   FOR_EACH_SSA_DEF_OPERAND
+tree            FOR_EACH_SSA_TREE_OPERAND
+@end smallexample
+
+@item You need to declare a variable of the type you are interested
+in, and an ssa_op_iter structure which serves as the loop controlling
+variable.
+
+@item Determine which operands you wish to use, and specify the flags of
+those you are interested in.  They are documented in
+@file{tree-ssa-operands.h}:
+
+@smallexample
+#define SSA_OP_USE              0x01    /* @r{Real USE operands.}  */
+#define SSA_OP_DEF              0x02    /* @r{Real DEF operands.}  */
+#define SSA_OP_VUSE             0x04    /* @r{VUSE operands.}  */
+#define SSA_OP_VMAYUSE          0x08    /* @r{USE portion of VDEFS.}  */
+#define SSA_OP_VDEF             0x10    /* @r{DEF portion of VDEFS.}  */
+
+/* @r{These are commonly grouped operand flags.}  */
+#define SSA_OP_VIRTUAL_USES     (SSA_OP_VUSE | SSA_OP_VMAYUSE)
+#define SSA_OP_VIRTUAL_DEFS     (SSA_OP_VDEF)
+#define SSA_OP_ALL_USES         (SSA_OP_VIRTUAL_USES | SSA_OP_USE)
+#define SSA_OP_ALL_DEFS         (SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF)
+#define SSA_OP_ALL_OPERANDS     (SSA_OP_ALL_USES | SSA_OP_ALL_DEFS)
+@end smallexample
+@end enumerate
+
+So if you want to look at the use pointers for all the @code{USE} and
+@code{VUSE} operands, you would do something like:
+
+@smallexample
+  use_operand_p use_p;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, (SSA_OP_USE | SSA_OP_VUSE))
+    @{
+      process_use_ptr (use_p);
+    @}
+@end smallexample
+
+The @code{TREE} macro is basically the same as the @code{USE} and
+@code{DEF} macros, only with the use or def dereferenced via
+@code{USE_FROM_PTR (use_p)} and @code{DEF_FROM_PTR (def_p)}.  Since we
+aren't using operand pointers, use and defs flags can be mixed.
+
+@smallexample
+  tree var;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_VUSE)
+    @{
+       print_generic_expr (stderr, var, TDF_SLIM);
+    @}
+@end smallexample
+
+@code{VDEF}s are broken into two flags, one for the
+@code{DEF} portion (@code{SSA_OP_VDEF}) and one for the USE portion
+(@code{SSA_OP_VMAYUSE}).  If all you want to look at are the
+@code{VDEF}s together, there is a fourth iterator macro for this,
+which returns both a def_operand_p and a use_operand_p for each
+@code{VDEF} in the statement.  Note that you don't need any flags for
+this one.
+
+@smallexample
+  use_operand_p use_p;
+  def_operand_p def_p;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
+    @{
+      my_code;
+    @}
+@end smallexample
+
+There are many examples in the code as well, as well as the
+documentation in @file{tree-ssa-operands.h}.
+
+There are also a couple of variants on the stmt iterators regarding PHI
+nodes.
+
+@code{FOR_EACH_PHI_ARG} Works exactly like
+@code{FOR_EACH_SSA_USE_OPERAND}, except it works over @code{PHI} arguments
+instead of statement operands.
+
+@smallexample
+/* Look at every virtual PHI use.  */
+FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_VIRTUAL_USES)
+@{
+   my_code;
+@}
+
+/* Look at every real PHI use.  */
+FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_USES)
+  my_code;
+
+/* Look at every PHI use.  */
+FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_ALL_USES)
+  my_code;
+@end smallexample
+
+@code{FOR_EACH_PHI_OR_STMT_@{USE,DEF@}} works exactly like
+@code{FOR_EACH_SSA_@{USE,DEF@}_OPERAND}, except it will function on
+either a statement or a @code{PHI} node.  These should be used when it is
+appropriate but they are not quite as efficient as the individual
+@code{FOR_EACH_PHI} and @code{FOR_EACH_SSA} routines.
+
+@smallexample
+FOR_EACH_PHI_OR_STMT_USE (use_operand_p, stmt, iter, flags)
+  @{
+     my_code;
+  @}
+
+FOR_EACH_PHI_OR_STMT_DEF (def_operand_p, phi, iter, flags)
+  @{
+     my_code;
+  @}
+@end smallexample
+
+@subsection Immediate Uses
+@cindex Immediate Uses
+
+Immediate use information is now always available.  Using the immediate use
+iterators, you may examine every use of any @code{SSA_NAME}. For instance,
+to change each use of @code{ssa_var} to @code{ssa_var2} and call fold_stmt on
+each stmt after that is done:
+
+@smallexample
+  use_operand_p imm_use_p;
+  imm_use_iterator iterator;
+  tree ssa_var, stmt;
+
+
+  FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var)
+    @{
+      FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator)
+        SET_USE (imm_use_p, ssa_var_2);
+      fold_stmt (stmt);
+    @}
+@end smallexample
+
+There are 2 iterators which can be used. @code{FOR_EACH_IMM_USE_FAST} is
+used when the immediate uses are not changed, i.e., you are looking at the
+uses, but not setting them.
+
+If they do get changed, then care must be taken that things are not changed
+under the iterators, so use the @code{FOR_EACH_IMM_USE_STMT} and
+@code{FOR_EACH_IMM_USE_ON_STMT} iterators.  They attempt to preserve the
+sanity of the use list by moving all the uses for a statement into
+a controlled position, and then iterating over those uses.  Then the
+optimization can manipulate the stmt when all the uses have been
+processed.  This is a little slower than the FAST version since it adds a
+placeholder element and must sort through the list a bit for each statement.
+This placeholder element must be also be removed if the loop is
+terminated early.  The macro @code{BREAK_FROM_IMM_USE_SAFE} is provided
+to do this :
+
+@smallexample
+  FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var)
+    @{
+      if (stmt == last_stmt)
+        BREAK_FROM_SAFE_IMM_USE (iter);
+
+      FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator)
+        SET_USE (imm_use_p, ssa_var_2);
+      fold_stmt (stmt);
+    @}
+@end smallexample
+
+There are checks in @code{verify_ssa} which verify that the immediate use list
+is up to date, as well as checking that an optimization didn't break from the
+loop without using this macro.  It is safe to simply 'break'; from a
+@code{FOR_EACH_IMM_USE_FAST} traverse.
+
+Some useful functions and macros:
+@enumerate
+@item  @code{has_zero_uses (ssa_var)} : Returns true if there are no uses of
+@code{ssa_var}.
+@item   @code{has_single_use (ssa_var)} : Returns true if there is only a
+single use of @code{ssa_var}.
+@item   @code{single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt)} :
+Returns true if there is only a single use of @code{ssa_var}, and also returns
+the use pointer and statement it occurs in, in the second and third parameters.
+@item   @code{num_imm_uses (ssa_var)} : Returns the number of immediate uses of
+@code{ssa_var}. It is better not to use this if possible since it simply
+utilizes a loop to count the uses.
+@item  @code{PHI_ARG_INDEX_FROM_USE (use_p)} : Given a use within a @code{PHI}
+node, return the index number for the use.  An assert is triggered if the use
+isn't located in a @code{PHI} node.
+@item  @code{USE_STMT (use_p)} : Return the statement a use occurs in.
+@end enumerate
+
+Note that uses are not put into an immediate use list until their statement is
+actually inserted into the instruction stream via a @code{bsi_*} routine.
+
+It is also still possible to utilize lazy updating of statements, but this
+should be used only when absolutely required.  Both alias analysis and the
+dominator optimizations currently do this.
+
+When lazy updating is being used, the immediate use information is out of date
+and cannot be used reliably.  Lazy updating is achieved by simply marking
+statements modified via calls to @code{mark_stmt_modified} instead of
+@code{update_stmt}.  When lazy updating is no longer required, all the
+modified statements must have @code{update_stmt} called in order to bring them
+up to date.  This must be done before the optimization is finished, or
+@code{verify_ssa} will trigger an abort.
+
+This is done with a simple loop over the instruction stream:
+@smallexample
+  block_stmt_iterator bsi;
+  basic_block bb;
+  FOR_EACH_BB (bb)
+    @{
+      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+        update_stmt_if_modified (bsi_stmt (bsi));
+    @}
+@end smallexample
+
+@node SSA
+@section Static Single Assignment
+@cindex SSA
+@cindex static single assignment
+
+Most of the tree optimizers rely on the data flow information provided
+by the Static Single Assignment (SSA) form.  We implement the SSA form
+as described in @cite{R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and
+K. Zadeck.  Efficiently Computing Static Single Assignment Form and the
+Control Dependence Graph.  ACM Transactions on Programming Languages
+and Systems, 13(4):451-490, October 1991}.
+
+The SSA form is based on the premise that program variables are
+assigned in exactly one location in the program.  Multiple assignments
+to the same variable create new versions of that variable.  Naturally,
+actual programs are seldom in SSA form initially because variables
+tend to be assigned multiple times.  The compiler modifies the program
+representation so that every time a variable is assigned in the code,
+a new version of the variable is created.  Different versions of the
+same variable are distinguished by subscripting the variable name with
+its version number.  Variables used in the right-hand side of
+expressions are renamed so that their version number matches that of
+the most recent assignment.
+
+We represent variable versions using @code{SSA_NAME} nodes.  The
+renaming process in @file{tree-ssa.c} wraps every real and
+virtual operand with an @code{SSA_NAME} node which contains
+the version number and the statement that created the
+@code{SSA_NAME}.  Only definitions and virtual definitions may
+create new @code{SSA_NAME} nodes.
+
+@cindex PHI nodes
+Sometimes, flow of control makes it impossible to determine the
+most recent version of a variable.  In these cases, the compiler
+inserts an artificial definition for that variable called
+@dfn{PHI function} or @dfn{PHI node}.  This new definition merges
+all the incoming versions of the variable to create a new name
+for it.  For instance,
+
+@smallexample
+if (@dots{})
+  a_1 = 5;
+else if (@dots{})
+  a_2 = 2;
+else
+  a_3 = 13;
+
+# a_4 = PHI <a_1, a_2, a_3>
+return a_4;
+@end smallexample
+
+Since it is not possible to determine which of the three branches
+will be taken at runtime, we don't know which of @code{a_1},
+@code{a_2} or @code{a_3} to use at the return statement.  So, the
+SSA renamer creates a new version @code{a_4} which is assigned
+the result of ``merging'' @code{a_1}, @code{a_2} and @code{a_3}.
+Hence, PHI nodes mean ``one of these operands.  I don't know
+which''.
+
+The following macros can be used to examine PHI nodes
+
+@defmac PHI_RESULT (@var{phi})
+Returns the @code{SSA_NAME} created by PHI node @var{phi} (i.e.,
+@var{phi}'s LHS)@.
+@end defmac
+
+@defmac PHI_NUM_ARGS (@var{phi})
+Returns the number of arguments in @var{phi}.  This number is exactly
+the number of incoming edges to the basic block holding @var{phi}@.
+@end defmac
+
+@defmac PHI_ARG_ELT (@var{phi}, @var{i})
+Returns a tuple representing the @var{i}th argument of @var{phi}@.
+Each element of this tuple contains an @code{SSA_NAME} @var{var} and
+the incoming edge through which @var{var} flows.
+@end defmac
+
+@defmac PHI_ARG_EDGE (@var{phi}, @var{i})
+Returns the incoming edge for the @var{i}th argument of @var{phi}.
+@end defmac
+
+@defmac PHI_ARG_DEF (@var{phi}, @var{i})
+Returns the @code{SSA_NAME} for the @var{i}th argument of @var{phi}.
+@end defmac
+
+
+@subsection Preserving the SSA form
+@findex update_ssa
+@cindex preserving SSA form
+Some optimization passes make changes to the function that
+invalidate the SSA property.  This can happen when a pass has
+added new symbols or changed the program so that variables that
+were previously aliased aren't anymore.  Whenever something like this
+happens, the affected symbols must be renamed into SSA form again.
+Transformations that emit new code or replicate existing statements
+will also need to update the SSA form@.
+
+Since GCC implements two different SSA forms for register and virtual
+variables, keeping the SSA form up to date depends on whether you are
+updating register or virtual names.  In both cases, the general idea
+behind incremental SSA updates is similar: when new SSA names are
+created, they typically are meant to replace other existing names in
+the program@.
+
+For instance, given the following code:
+
+@smallexample
+     1  L0:
+     2  x_1 = PHI (0, x_5)
+     3  if (x_1 < 10)
+     4    if (x_1 > 7)
+     5      y_2 = 0
+     6    else
+     7      y_3 = x_1 + x_7
+     8    endif
+     9    x_5 = x_1 + 1
+     10   goto L0;
+     11 endif
+@end smallexample
+
+Suppose that we insert new names @code{x_10} and @code{x_11} (lines
+@code{4} and @code{8})@.
+
+@smallexample
+     1  L0:
+     2  x_1 = PHI (0, x_5)
+     3  if (x_1 < 10)
+     4    x_10 = @dots{}
+     5    if (x_1 > 7)
+     6      y_2 = 0
+     7    else
+     8      x_11 = @dots{}
+     9      y_3 = x_1 + x_7
+     10   endif
+     11   x_5 = x_1 + 1
+     12   goto L0;
+     13 endif
+@end smallexample
+
+We want to replace all the uses of @code{x_1} with the new definitions
+of @code{x_10} and @code{x_11}.  Note that the only uses that should
+be replaced are those at lines @code{5}, @code{9} and @code{11}.
+Also, the use of @code{x_7} at line @code{9} should @emph{not} be
+replaced (this is why we cannot just mark symbol @code{x} for
+renaming)@.
+
+Additionally, we may need to insert a PHI node at line @code{11}
+because that is a merge point for @code{x_10} and @code{x_11}.  So the
+use of @code{x_1} at line @code{11} will be replaced with the new PHI
+node.  The insertion of PHI nodes is optional.  They are not strictly
+necessary to preserve the SSA form, and depending on what the caller
+inserted, they may not even be useful for the optimizers@.
+
+Updating the SSA form is a two step process.  First, the pass has to
+identify which names need to be updated and/or which symbols need to
+be renamed into SSA form for the first time.  When new names are
+introduced to replace existing names in the program, the mapping
+between the old and the new names are registered by calling
+@code{register_new_name_mapping} (note that if your pass creates new
+code by duplicating basic blocks, the call to @code{tree_duplicate_bb}
+will set up the necessary mappings automatically).
+
+After the replacement mappings have been registered and new symbols
+marked for renaming, a call to @code{update_ssa} makes the registered
+changes.  This can be done with an explicit call or by creating
+@code{TODO} flags in the @code{tree_opt_pass} structure for your pass.
+There are several @code{TODO} flags that control the behavior of
+@code{update_ssa}:
+
+@itemize @bullet
+@item @code{TODO_update_ssa}.  Update the SSA form inserting PHI nodes
+for newly exposed symbols and virtual names marked for updating.
+When updating real names, only insert PHI nodes for a real name
+@code{O_j} in blocks reached by all the new and old definitions for
+@code{O_j}.  If the iterated dominance frontier for @code{O_j}
+is not pruned, we may end up inserting PHI nodes in blocks that
+have one or more edges with no incoming definition for
+@code{O_j}.  This would lead to uninitialized warnings for
+@code{O_j}'s symbol@.
+
+@item @code{TODO_update_ssa_no_phi}.  Update the SSA form without
+inserting any new PHI nodes at all.  This is used by passes that
+have either inserted all the PHI nodes themselves or passes that
+need only to patch use-def and def-def chains for virtuals
+(e.g., DCE)@.
+
+
+@item @code{TODO_update_ssa_full_phi}.  Insert PHI nodes everywhere
+they are needed.  No pruning of the IDF is done.  This is used
+by passes that need the PHI nodes for @code{O_j} even if it
+means that some arguments will come from the default definition
+of @code{O_j}'s symbol (e.g., @code{pass_linear_transform})@.
+
+WARNING: If you need to use this flag, chances are that your
+pass may be doing something wrong.  Inserting PHI nodes for an
+old name where not all edges carry a new replacement may lead to
+silent codegen errors or spurious uninitialized warnings@.
+
+@item @code{TODO_update_ssa_only_virtuals}.  Passes that update the
+SSA form on their own may want to delegate the updating of
+virtual names to the generic updater.  Since FUD chains are
+easier to maintain, this simplifies the work they need to do.
+NOTE: If this flag is used, any OLD->NEW mappings for real names
+are explicitly destroyed and only the symbols marked for
+renaming are processed@.
+@end itemize
+
+@subsection Preserving the virtual SSA form
+@cindex preserving virtual SSA form
+
+The virtual SSA form is harder to preserve than the non-virtual SSA form
+mainly because the set of virtual operands for a statement may change at
+what some would consider unexpected times.  In general, statement
+modifications should be bracketed between calls to
+@code{push_stmt_changes} and @code{pop_stmt_changes}.  For example,
+
+@smallexample
+    munge_stmt (tree stmt)
+    @{
+       push_stmt_changes (&stmt);
+       @dots{} rewrite STMT @dots{}
+       pop_stmt_changes (&stmt);
+    @}
+@end smallexample
+
+The call to @code{push_stmt_changes} saves the current state of the
+statement operands and the call to @code{pop_stmt_changes} compares
+the saved state with the current one and does the appropriate symbol
+marking for the SSA renamer.
+
+It is possible to modify several statements at a time, provided that
+@code{push_stmt_changes} and @code{pop_stmt_changes} are called in
+LIFO order, as when processing a stack of statements.
+
+Additionally, if the pass discovers that it did not need to make
+changes to the statement after calling @code{push_stmt_changes}, it
+can simply discard the topmost change buffer by calling
+@code{discard_stmt_changes}.  This will avoid the expensive operand
+re-scan operation and the buffer comparison that determines if symbols
+need to be marked for renaming.
+
+@subsection Examining @code{SSA_NAME} nodes
+@cindex examining SSA_NAMEs
+
+The following macros can be used to examine @code{SSA_NAME} nodes
+
+@defmac SSA_NAME_DEF_STMT (@var{var})
+Returns the statement @var{s} that creates the @code{SSA_NAME}
+@var{var}.  If @var{s} is an empty statement (i.e., @code{IS_EMPTY_STMT
+(@var{s})} returns @code{true}), it means that the first reference to
+this variable is a USE or a VUSE@.
+@end defmac
+
+@defmac SSA_NAME_VERSION (@var{var})
+Returns the version number of the @code{SSA_NAME} object @var{var}.
+@end defmac
+
+
+@subsection Walking use-def chains
+
+@deftypefn {Tree SSA function} void walk_use_def_chains (@var{var}, @var{fn}, @var{data})
+
+Walks use-def chains starting at the @code{SSA_NAME} node @var{var}.
+Calls function @var{fn} at each reaching definition found.  Function
+@var{FN} takes three arguments: @var{var}, its defining statement
+(@var{def_stmt}) and a generic pointer to whatever state information
+that @var{fn} may want to maintain (@var{data}).  Function @var{fn} is
+able to stop the walk by returning @code{true}, otherwise in order to
+continue the walk, @var{fn} should return @code{false}.
+
+Note, that if @var{def_stmt} is a @code{PHI} node, the semantics are
+slightly different.  For each argument @var{arg} of the PHI node, this
+function will:
+
+@enumerate
+@item Walk the use-def chains for @var{arg}.
+@item Call @code{FN (@var{arg}, @var{phi}, @var{data})}.
+@end enumerate
+
+Note how the first argument to @var{fn} is no longer the original
+variable @var{var}, but the PHI argument currently being examined.
+If @var{fn} wants to get at @var{var}, it should call
+@code{PHI_RESULT} (@var{phi}).
+@end deftypefn
+
+@subsection Walking the dominator tree
+
+@deftypefn {Tree SSA function} void walk_dominator_tree (@var{walk_data}, @var{bb})
+
+This function walks the dominator tree for the current CFG calling a
+set of callback functions defined in @var{struct dom_walk_data} in
+@file{domwalk.h}.  The call back functions you need to define give you
+hooks to execute custom code at various points during traversal:
+
+@enumerate
+@item Once to initialize any local data needed while processing
+@var{bb} and its children.  This local data is pushed into an
+internal stack which is automatically pushed and popped as the
+walker traverses the dominator tree.
+
+@item Once before traversing all the statements in the @var{bb}.
+
+@item Once for every statement inside @var{bb}.
+
+@item Once after traversing all the statements and before recursing
+into @var{bb}'s dominator children.
+
+@item It then recurses into all the dominator children of @var{bb}.
+
+@item After recursing into all the dominator children of @var{bb} it
+can, optionally, traverse every statement in @var{bb} again
+(i.e., repeating steps 2 and 3).
+
+@item Once after walking the statements in @var{bb} and @var{bb}'s
+dominator children.  At this stage, the block local data stack
+is popped.
+@end enumerate
+@end deftypefn
+
+@node Alias analysis
+@section Alias analysis
+@cindex alias
+@cindex flow-sensitive alias analysis
+@cindex flow-insensitive alias analysis
+
+Alias analysis in GIMPLE SSA form consists of two pieces.  First
+the virtual SSA web ties conflicting memory accesses and provides
+a SSA use-def chain and SSA immediate-use chains for walking
+possibly dependent memory accesses.  Second an alias-oracle can
+be queried to disambiguate explicit and implicit memory references.
+
+@enumerate
+@item Memory SSA form.
+
+All statements that may use memory have exactly one accompanied use of
+a virtual SSA name that represents the state of memory at the
+given point in the IL.
+
+All statements that may define memory have exactly one accompanied
+definition of a virtual SSA name using the previous state of memory
+and defining the new state of memory after the given point in the IL.
+
+@smallexample
+int i;
+int foo (void)
+@{
+  # .MEM_3 = VDEF <.MEM_2(D)>
+  i = 1;
+  # VUSE <.MEM_3>
+  return i;
+@}
+@end smallexample
+
+The virtual SSA names in this case are @code{.MEM_2(D)} and
+@code{.MEM_3}.  The store to the global variable @code{i}
+defines @code{.MEM_3} invalidating @code{.MEM_2(D)}.  The
+load from @code{i} uses that new state @code{.MEM_3}.
+
+The virtual SSA web serves as constraints to SSA optimizers
+preventing illegitimate code-motion and optimization.  It
+also provides a way to walk related memory statements.
+
+@item Points-to and escape analysis.
+
+Points-to analysis builds a set of constraints from the GIMPLE
+SSA IL representing all pointer operations and facts we do
+or do not know about pointers.  Solving this set of constraints
+yields a conservatively correct solution for each pointer
+variable in the program (though we are only interested in
+SSA name pointers) as to what it may possibly point to.
+
+This points-to solution for a given SSA name pointer is stored
+in the @code{pt_solution} sub-structure of the
+@code{SSA_NAME_PTR_INFO} record.  The following accessor
+functions are available:
+
+@itemize @bullet
+@item @code{pt_solution_includes}
+@item @code{pt_solutions_intersect}
+@end itemize
+
+Points-to analysis also computes the solution for two special
+set of pointers, @code{ESCAPED} and @code{CALLUSED}.  Those
+represent all memory that has escaped the scope of analysis
+or that is used by pure or nested const calls.
+
+@item Type-based alias analysis
+
+Type-based alias analysis is frontend dependent though generic
+support is provided by the middle-end in @code{alias.c}.  TBAA
+code is used by both tree optimizers and RTL optimizers.
+
+Every language that wishes to perform language-specific alias analysis
+should define a function that computes, given a @code{tree}
+node, an alias set for the node.  Nodes in different alias sets are not
+allowed to alias.  For an example, see the C front-end function
+@code{c_get_alias_set}.
+
+@item Tree alias-oracle
+
+The tree alias-oracle provides means to disambiguate two memory
+references and memory references against statements.  The following
+queries are available:
+
+@itemize @bullet
+@item @code{refs_may_alias_p}
+@item @code{ref_maybe_used_by_stmt_p}
+@item @code{stmt_may_clobber_ref_p}
+@end itemize
+
+In addition to those two kind of statement walkers are available
+walking statements related to a reference ref.
+@code{walk_non_aliased_vuses} walks over dominating memory defining
+statements and calls back if the statement does not clobber ref
+providing the non-aliased VUSE.  The walk stops at
+the first clobbering statement or if asked to.
+@code{walk_aliased_vdefs} walks over dominating memory defining
+statements and calls back on each statement clobbering ref
+providing its aliasing VDEF.  The walk stops if asked to.
+
+@end enumerate
+
+
+@node Memory model
+@section Memory model
+@cindex memory model
+
+The memory model used by the middle-end models that of the C/C++
+languages.  The middle-end has the notion of an effective type
+of a memory region which is used for type-based alias analysis.
+
+The following is a refinement of ISO C99 6.5/6, clarifying the block copy case
+to follow common sense and extending the concept of a dynamic effective
+type to objects with a declared type as required for C++.
+
+@smallexample
+The effective type of an object for an access to its stored value is
+the declared type of the object or the effective type determined by
+a previous store to it.  If a value is stored into an object through
+an lvalue having a type that is not a character type, then the
+type of the lvalue becomes the effective type of the object for that
+access and for subsequent accesses that do not modify the stored value.
+If a value is copied into an object using @code{memcpy} or @code{memmove},
+or is copied as an array of character type, then the effective type
+of the modified object for that access and for subsequent accesses that
+do not modify the value is undetermined.  For all other accesses to an
+object, the effective type of the object is simply the type of the
+lvalue used for the access.
+@end smallexample
+