This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Initial tree-ssa.texi documentation
Thanks for the feedback. This patch just fixes the formatting. More
content to follow.
Diego.
2004-02-24 Diego Novillo <dnovillo@redhat.com>
* doc/tree-ssa.texi: Fix formatting mark ups.
Index: doc/tree-ssa.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/Attic/tree-ssa.texi,v
retrieving revision 1.1.2.2
diff -d -c -p -r1.1.2.2 tree-ssa.texi
*** doc/tree-ssa.texi 24 Feb 2004 15:26:29 -0000 1.1.2.2
--- doc/tree-ssa.texi 24 Feb 2004 21:20:43 -0000
***************
*** 13,23 ****
@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,
--- 13,23 ----
@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,
*************** This chapter describes the data structur
*** 34,40 ****
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 statements and variables.
--- 34,40 ----
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 statements and variables.
*************** is considered real, otherwise it is a vi
*** 95,101 ****
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 it is considered a definition (e.g., the operand at the LHS of
an assignment).
Virtual and real operands also have very different data flow
--- 95,101 ----
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
*************** definitions to mark that statement as a
*** 138,144 ****
@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 @code{-vops} option to @code{-fdump-tree}:
@smallexample
@{
--- 138,144 ----
@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
@{
*************** The following are all the accessor macro
*** 174,201 ****
operands. To access all the other operand arrays, just change the
name accordingly:
! @ftable @code
! @item USE_OPS(ANN)
Returns the array of operands used by the statement with annotation
! @code{ANN}.
! @item STMT_USE_OPS(STMT)
! Alternate version of USE_OPS that takes the statement as input.
! @item NUM_USES(OPS)
! Return the number of USE operands in array OPS.
! @item USE_OP_PTR(OPS, I)
! Return a pointer to the Ith operand in array OPS.
! @item USE_OP(OPS, I)
! Return the Ith operand in array OPS.
! @end ftable
The following function shows how to print all the operands of a given
statement:
! @example
void
print_ops (tree stmt)
@{
--- 174,205 ----
operands. To access all the other operand arrays, just change the
name accordingly:
! @defmac USE_OPS (@var{ann})
Returns the array of operands used by the statement with annotation
! @var{ann}.
! @end defmac
! @defmac STMT_USE_OPS (@var{stmt})
! Alternate version of USE_OPS that takes the statement @var{stmt} as
! input.
! @end defmac
! @defmac NUM_USES (@var{ops})
! Return the number of USE operands in array @var{ops}.
! @end defmac
! @defmac USE_OP_PTR (@var{ops}, @var{i})
! Return a pointer to the @var{i}th operand in array @var{ops}.
! @end defmac
! @defmac USE_OP (@var{ops}, @var{i})
! Return the @var{i}th operand in array @var{ops}.
! @end defmac
The following function shows how to print all the operands of a given
statement:
! @smallexample
void
print_ops (tree stmt)
@{
*************** print_ops (tree stmt)
*** 225,231 ****
for (i = 0; i < NUM_VUSES (vuses); i++)
print_generic_expr (stderr, VUSE_OP (vuses, i), 0);
@}
! @end example
To collect the operands, you first need to call
@code{get_stmt_operands}. Since that is a potentially expensive
--- 229,235 ----
for (i = 0; i < NUM_VUSES (vuses); i++)
print_generic_expr (stderr, VUSE_OP (vuses, i), 0);
@}
! @end smallexample
To collect the operands, you first need to call
@code{get_stmt_operands}. Since that is a potentially expensive
*************** inserts an artificial definition for tha
*** 272,278 ****
all the incoming versions of the variable to create a new name
for it. For instance,
! @example
if (...)
a_1 = 5;
else if (...)
--- 276,282 ----
all the incoming versions of the variable to create a new name
for it. For instance,
! @smallexample
if (...)
a_1 = 5;
else if (...)
*************** else
*** 282,288 ****
# a_4 = PHI <a_1, a_2, a_3>
return a_4;
! @end example
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},
--- 286,292 ----
# 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},
*************** which''.
*** 294,318 ****
The following macros can be used to examine PHI nodes
! @ftable @code
! @item PHI_RESULT(PHI)
! Returns the SSA_NAME created by this PHI node (i.e., its LHS).
! @item PHI_NUM_ARGS(PHI)
! Returns the number of arguments in PHI. This number is exactly the
! number of incoming edges to the basic block holding PHI.
! @item PHI_ARG_ELT(PHI, I)
! Returns a tuple representing the Ith argument of PHI. Each element of
! this tuple contains an SSA_NAME and the incoming edge through which
! this name flows.
! @item PHI_ARG_EDGE(PHI, I)
! Returns the incoming edge for the Ith argument of PHI.
! @item PHI_ARG_DEF(PHI, I)
! Returns the SSA_NAME for the Ith argument of PHI.
! @end ftable
@subsection Preserving the SSA form
--- 298,326 ----
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
*************** new variables in the global bitmap @code
*** 329,371 ****
your pass has finished, the pass manager will invoke the SSA
renamer to put the program into SSA once more.
! @subsection Examining SSA_NAME nodes
@cindex examining SSA_NAMEs
- The following macros can be used to examine SSA_NAME nodes
! @ftable @code
! @item SSA_NAME_DEF_STMT
! Returns the statement S that creates the given SSA_NAME. If S is
! an empty statement (@code{IS_EMPTY_STMT}), it means that the
! first reference to this variable is a USE or a VUSE.
- @item SSA_NAME_VERSION
- Return the version number of this SSA_NAME object.
- @end ftable
@subsection Walking use-def chains
- @findex @code{walk_use_def_chains (VAR, FN, DATA)}
- Walks use-def chains starting at the SSA variable @code{VAR}. Calls
- function @code{FN} at each reaching definition found. @code{FN} takes
- three arguments: @code{VAR}, its defining statement (@code{DEF_STMT})
- and a generic pointer to whatever state information that @code{FN} may want
- to maintain (@code{DATA}). @code{FN} is able to stop the walk by returning
- @code{true}, otherwise in order to continue the walk, @code{FN} should
- return false@.
! Note, that if @code{DEF_STMT} is a @code{PHI} node, the semantics are
! slightly different. For each argument @code{ARG} of the PHI node, this
function will:
@enumerate
! @item Walk the use-def chains for @code{ARG}.
! @item Call @code{FN (ARG, PHI, DATA)}.
@end enumerate
! Note how the first argument to @code{FN} is no longer the original
! variable @code{VAR}, but the PHI argument currently being examined.
! If @code{FN} wants to get at @code{VAR}, it should call
! @code{PHI_RESULT} (PHI).
@subsection Walking the dominator tree
@cindex walk dominator tree
--- 337,385 ----
your pass has finished, the pass manager will invoke the SSA
renamer to put the program into SSA once more.
! @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
@cindex walk dominator tree
*************** three things:
*** 393,399 ****
@item Pointers and ADDR_EXPR that escape the current function.
@end itemize
! The concept of 'escaping' is the same one used in the Java world.
When a pointer or an ADDR_EXPR escapes, it means that it has been
exposed outside of the current function. So, assignment to
global variables, function arguments and returning a pointer are
--- 407,413 ----
@item Pointers and ADDR_EXPR that escape the current function.
@end itemize
! The concept of `escaping' is the same one used in the Java world.
When a pointer or an ADDR_EXPR escapes, it means that it has been
exposed outside of the current function. So, assignment to
global variables, function arguments and returning a pointer are
*************** the variables pointed-to by P_i (and its
*** 413,420 ****
We have two classes of memory tags. Memory tags associated with
the pointed-to data type of the pointers in the program. These
! tags are called "type memory tag" (TMT). The other class are
! those associated with SSA_NAMEs, called "name memory tag" (NMT).
The basic idea is that when adding operands for an INDIRECT_REF
*P_i, we will first check whether P_i has a name tag, if it does
we use it, because that will have more precise aliasing
--- 427,434 ----
We have two classes of memory tags. Memory tags associated with
the pointed-to data type of the pointers in the program. These
! tags are called ``type memory tag'' (TMT). The other class are
! those associated with SSA_NAMEs, called ``name memory tag'' (NMT).
The basic idea is that when adding operands for an INDIRECT_REF
*P_i, we will first check whether P_i has a name tag, if it does
we use it, because that will have more precise aliasing
*************** call-clobbered the variables it points t
*** 430,438 ****
This pass will compare the alias set of every type memory tag and
every addressable variable found in the program. Given a type
! memory tag TMT and an addressable variable V. If the alias sets
of TMT and V conflict (as computed by may_alias_p), then V is
! marked as an alias tag and added to the alias set of TMT.
@end enumerate
For instance, consider the following function:
--- 444,452 ----
This pass will compare the alias set of every type memory tag and
every addressable variable found in the program. Given a type
! memory tag TMT and an addressable variable V@. If the alias sets
of TMT and V conflict (as computed by may_alias_p), then V is
! marked as an alias tag and added to the alias set of TMT@.
@end enumerate
For instance, consider the following function:
*************** foo (int i)
*** 455,463 ****
@end example
After aliasing analysis has finished, the type memory tag for
! pointer 'p' will have two aliases, namely variables 'a' and 'b'.
! Every time pointer 'p' is dereferenced, we want to mark the
! operation as a potential reference to 'a' and 'b'.
@example
foo (int i)
--- 469,478 ----
@end example
After aliasing analysis has finished, the type memory tag for
! pointer @code{p} will have two aliases, namely variables @code{a} and
! @code{b}.
! Every time pointer @code{p} is dereferenced, we want to mark the
! operation as a potential reference to @code{a} and @code{b}.
@example
foo (int i)
*************** compile-time slow downs and memory consu
*** 496,554 ****
grouping heuristic proceeds as follows:
@enumerate
! @item Sort the list of pointers in decreasing number of contributed
! virtual operands.
! @item Take the first pointer from the list and reverse the role
! of the memory tag and its aliases. Usually, whenever an
! aliased variable Vi is found to alias with a memory tag
! T, we add Vi to the may-aliases set for T. Meaning that
! after alias analysis, we will have:
! may-aliases(T) = @{ V1, V2, V3, ..., Vn @}
! This means that every statement that references T, will get 'n'
! virtual operands for each of the Vi tags. But, when alias
! grouping is enabled, we make T an alias tag and add it to the
! alias set of all the Vi variables:
! may-aliases(V1) = @{ T @}
! may-aliases(V2) = @{ T @}
! ...
! may-aliases(Vn) = @{ T @}
! This has two effects: (a) statements referencing T will only get
! a single virtual operand, and, (b) all the variables Vi will now
! appear to alias each other. So, we lose alias precision to
! improve compile time. But, in theory, a program with such a high
! level of aliasing should not be very optimizable in the first
! place.
! @item Since variables may be in the alias set of more than one
! memory tag, the grouping done in step (2) needs to be extended
! to all the memory tags that have a non-empty intersection with
! the may-aliases set of tag T. For instance, if we originally
! had these may-aliases sets:
! may-aliases(T) = @{ V1, V2, V3 @}
! may-aliases(R) = @{ V2, V4 @}
! In step (2) we would have reverted the aliases for T as:
! may-aliases(V1) = @{ T @}
! may-aliases(V2) = @{ T @}
! may-aliases(V3) = @{ T @}
! But note that now V2 is no longer aliased with R. We could
! add R to may-aliases(V2), but we are in the process of
! grouping aliases to reduce virtual operands so what we do is
! add V4 to the grouping to obtain:
! may-aliases(V1) = @{ T @}
! may-aliases(V2) = @{ T @}
! may-aliases(V3) = @{ T @}
! may-aliases(V4) = @{ T @}
! @item If the total number of virtual operands due to aliasing is
! still above the threshold set by max-alias-vops, go back to (2).
@end enumerate
--- 511,579 ----
grouping heuristic proceeds as follows:
@enumerate
! @item Sort the list of pointers in decreasing number of contributed
! virtual operands.
! @item Take the first pointer from the list and reverse the role
! of the memory tag and its aliases. Usually, whenever an
! aliased variable Vi is found to alias with a memory tag
! T, we add Vi to the may-aliases set for T@. Meaning that
! after alias analysis, we will have:
! @smallexample
! may-aliases(T) = @{ V1, V2, V3, ..., Vn @}
! @end smallexample
! This means that every statement that references T, will get
! @code{n} virtual operands for each of the Vi tags. But, when
! alias grouping is enabled, we make T an alias tag and add it
! to the alias set of all the Vi variables:
! @smallexample
! may-aliases(V1) = @{ T @}
! may-aliases(V2) = @{ T @}
! ...
! may-aliases(Vn) = @{ T @}
! @end smallexample
! This has two effects: (a) statements referencing T will only get
! a single virtual operand, and, (b) all the variables Vi will now
! appear to alias each other. So, we lose alias precision to
! improve compile time. But, in theory, a program with such a high
! level of aliasing should not be very optimizable in the first
! place.
! @item Since variables may be in the alias set of more than one
! memory tag, the grouping done in step (2) needs to be extended
! to all the memory tags that have a non-empty intersection with
! the may-aliases set of tag T@. For instance, if we originally
! had these may-aliases sets:
! @smallexample
! may-aliases(T) = @{ V1, V2, V3 @}
! may-aliases(R) = @{ V2, V4 @}
! @end smallexample
! In step (2) we would have reverted the aliases for T as:
! @smallexample
! may-aliases(V1) = @{ T @}
! may-aliases(V2) = @{ T @}
! may-aliases(V3) = @{ T @}
! @end smallexample
! But note that now V2 is no longer aliased with R@. We could
! add R to may-aliases(V2), but we are in the process of
! grouping aliases to reduce virtual operands so what we do is
! add V4 to the grouping to obtain:
! @smallexample
! may-aliases(V1) = @{ T @}
! may-aliases(V2) = @{ T @}
! may-aliases(V3) = @{ T @}
! may-aliases(V4) = @{ T @}
! @end smallexample
! @item If the total number of virtual operands due to aliasing is
! still above the threshold set by max-alias-vops, go back to (2).
@end enumerate