CbC/CbC_gcc: gcc/doc/tree-ssa.texi comparison

comparison gcc/doc/tree-ssa.texi @ 55:77e2b8dfacca gcc-4.4.5

update it from 4.4.3 to 4.5.0

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 23:39:51 +0900
parents	a06113de4d67
children	b7f97abdc517

comparison

equal deleted inserted replaced

-:c156f1bd5cd9
+:77e2b8dfacca
 @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
 @}
 @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{b} is completely modified with the contents of
+variable @code{a} is completely modified with the contents of
-variable @code{a}.  Real definition are also known as @dfn{killing
+variable @code{b}.  Real definition are also known as @dfn{killing
-definitions}.  Similarly, the use of @code{a} reads all its bits.
+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
 @section Alias analysis
 @cindex alias
 @cindex flow-sensitive alias analysis
 @cindex flow-insensitive alias analysis
-Alias analysis proceeds in 4 main phases:
+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   Structural alias analysis.
+@item Memory SSA form.
-This phase walks the types for structure variables, and determines which
+All statements that may use memory have exactly one accompanied use of
-of the fields can overlap using offset and size of each field.  For each
+a virtual SSA name that represents the state of memory at the
-field, a ``subvariable'' called a ``Structure field tag'' (SFT)@ is
+given point in the IL.
-created, which represents that field as a separate variable.  All
-accesses that could possibly overlap with a given field will have
+All statements that may define memory have exactly one accompanied
-virtual operands for the SFT of that field.
+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
-struct foo
+@smallexample
+int i;
+int foo (void)
 @{
-int a;
+# .MEM_3 = VDEF <.MEM_2(D)>
-int b;
+i = 1;
+# VUSE <.MEM_3>
+return i;
 @}
-struct foo temp;
+@end smallexample
-int bar (void)
-@{
+The virtual SSA names in this case are @code{.MEM_2(D)} and
-int tmp1, tmp2, tmp3;
+@code{.MEM_3}.  The store to the global variable @code{i}
-SFT.0_2 = VDEF <SFT.0_1>
+defines @code{.MEM_3} invalidating @code{.MEM_2(D)}.  The
-temp.a = 5;
+load from @code{i} uses that new state @code{.MEM_3}.
-SFT.1_4 = VDEF <SFT.1_3>
-temp.b = 6;
+The virtual SSA web serves as constraints to SSA optimizers
+preventing illegitimate code-motion and optimization.  It
-VUSE <SFT.1_4>
+also provides a way to walk related memory statements.
-tmp1_5 = temp.b;
-VUSE <SFT.0_2>
-tmp2_6 = temp.a;
-tmp3_7 = tmp1_5 + tmp2_6;
-return tmp3_7;
-@}
-@end smallexample
-If you copy the symbol tag for a variable for some reason, you probably
-also want to copy the subvariables for that variable.
 @item Points-to and escape analysis.
-This phase walks the use-def chains in the SSA web looking for
+Points-to analysis builds a set of constraints from the GIMPLE
-three things:
+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 Assignments of the form @code{P_i = &VAR}
+@item @code{pt_solution_includes}
-@item Assignments of the form P_i = malloc()
+@item @code{pt_solutions_intersect}
-@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.
+Points-to analysis also computes the solution for two special
-When a pointer or an ADDR_EXPR escapes, it means that it has been
+set of pointers, @code{ESCAPED} and @code{CALLUSED}.  Those
-exposed outside of the current function.  So, assignment to
+represent all memory that has escaped the scope of analysis
-global variables, function arguments and returning a pointer are
+or that is used by pure or nested const calls.
-all escape sites.
+@item Type-based alias analysis
-This is where we are currently limited.  Since not everything is
-renamed into SSA, we lose track of escape properties when a
+Type-based alias analysis is frontend dependent though generic
-pointer is stashed inside a field in a structure, for instance.
+support is provided by the middle-end in @code{alias.c}.  TBAA
-In those cases, we are assuming that the pointer does escape.
+code is used by both tree optimizers and RTL optimizers.
-We use escape analysis to determine whether a variable is
-call-clobbered.  Simply put, if an ADDR_EXPR escapes, then the
-variable is call-clobbered.  If a pointer P_i escapes, then all
-the variables pointed-to by P_i (and its memory tag) also escape.
-@item Compute flow-sensitive aliases
-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 ``symbol memory tag'' (SMT)@.  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
-information.  Otherwise, we use the standard symbol tag.
-In this phase, we go through all the pointers we found in
-points-to analysis and create alias sets for the name memory tags
-associated with each pointer P_i.  If P_i escapes, we mark
-call-clobbered the variables it points to and its tag.
-@item Compute flow-insensitive aliases
-This pass will compare the alias set of every symbol memory tag and
-every addressable variable found in the program.  Given a symbol
-memory tag SMT and an addressable variable V@.  If the alias sets
-of SMT and V conflict (as computed by may_alias_p), then V is
-marked as an alias tag and added to the alias set of SMT@.
 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
-For instance, consider the following function:
+@node Memory model
-@smallexample
+@section Memory model
-foo (int i)
+@cindex memory model
-@{
-int *p, *q, a, b;
+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
-if (i > 10)
+of a memory region which is used for type-based alias analysis.
-p = &a;
-else
+The following is a refinement of ISO C99 6.5/6, clarifying the block copy case
-q = &b;
+to follow common sense and extending the concept of a dynamic effective
+type to objects with a declared type as required for C++.
-*p = 3;
-*q = 5;
+@smallexample
-a = b + 2;
+The effective type of an object for an access to its stored value is
-return *p;
+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
-@end smallexample
+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
-After aliasing analysis has finished, the symbol memory tag for
+access and for subsequent accesses that do not modify the stored value.
-pointer @code{p} will have two aliases, namely variables @code{a} and
+If a value is copied into an object using @code{memcpy} or @code{memmove},
-@code{b}.
+or is copied as an array of character type, then the effective type
-Every time pointer @code{p} is dereferenced, we want to mark the
+of the modified object for that access and for subsequent accesses that
-operation as a potential reference to @code{a} and @code{b}.
+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
-@smallexample
+lvalue used for the access.
-foo (int i)
+@end smallexample
-@{
-int *p, a, b;
-if (i_2 > 10)
-p_4 = &a;
-else
-p_6 = &b;
-# p_1 = PHI <p_4(1), p_6(2)>;
-# a_7 = VDEF <a_3>;
-# b_8 = VDEF <b_5>;
-*p_1 = 3;
-# a_9 = VDEF <a_7>
-# VUSE <b_8>
-a_9 = b_8 + 2;
-# VUSE <a_9>;
-# VUSE <b_8>;
-return *p_1;
-@}
-@end smallexample
-In certain cases, the list of may aliases for a pointer may grow
-too large.  This may cause an explosion in the number of virtual
-operands inserted in the code.  Resulting in increased memory
-consumption and compilation time.
-When the number of virtual operands needed to represent aliased
-loads and stores grows too large (configurable with @option{--param
-max-aliased-vops}), alias sets are grouped to avoid severe
-compile-time slow downs and memory consumption.  The alias
-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, @dots{}, 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 @}
-@dots{}
-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

Mercurial > hg > CbC > CbC_gcc

comparison gcc/doc/tree-ssa.texi @ 55:77e2b8dfacca gcc-4.4.5