* doc/loop.texi: Add data references analysis description.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@117453 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3be345c..513e7c7 100644 (file)
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,7 @@
+2006-10-05  Ira Rosen  <irar@il.ibm.com>
+
+       * doc/loop.texi: Add data references analysis description.
+
 2006-10-04  Brooks Moses  <bmoses@stanford.edu>
 
        * doc/gcov.texi: Add formatting to "Invoking gcov" section head.

diff --git a/gcc/doc/loop.texi b/gcc/doc/loop.texi
index 1282f22..b207b38 100644 (file)
--- a/gcc/doc/loop.texi
+++ b/gcc/doc/loop.texi
@@ -476,6 +476,63 @@ syntactic order is important in some classical data dependence tests,
 and mapping this order to the elements of this array avoids costly
 queries to the loop body representation.
 
+Three types of data references are currently handled: ARRAY_REF, 
+INDIRECT_REF and COMPONENT_REF. The data structure for the data reference 
+is @code{data_reference}, where @code{data_reference_p} is a name of a 
+pointer to the data reference structure. The structure contains the 
+following elements:
+
+@itemize
+@item @code{base_object_info}: Provides information about the base object 
+of the data reference and its access functions. These access functions 
+represent the evolution of the data reference in the loop relative to 
+its base, in keeping with the classical meaning of the data reference 
+access function for the support of arrays. For example, for a reference 
+@code{a.b[i][j]}, the base object is @code{a.b} and the access functions, 
+one for each array subscript, are: 
+@code{@{i_init, + i_step@}_1, @{j_init, +, j_step@}_2}.
+
+@item @code{first_location_in_loop}: Provides information about the first 
+location accessed by the data reference in the loop and about the access 
+function used to represent evolution relative to this location. This data 
+is used to support pointers, and is not used for arrays (for which we 
+have base objects). Pointer accesses are represented as a one-dimensional
+access that starts from the first location accessed in the loop. For 
+example:
+
+@smallexample
+      for1 i
+         for2 j
+          *((int *)p + i + j) = a[i][j];
+@end smallexample
+
+The access function of the pointer access is @code{@{0, + 4B@}_for2} 
+relative to @code{p + i}. The access functions of the array are 
+@code{@{i_init, + i_step@}_for1} and @code{@{j_init, +, j_step@}_for2} 
+relative to @code{a}.
+
+Usually, the object the pointer refers to is either unknown, or we can't 
+prove that the access is confined to the boundaries of a certain object. 
+
+Two data references can be compared only if at least one of these two 
+representations has all its fields filled for both data references. 
+
+The current strategy for data dependence tests is as follows: 
+If both @code{a} and @code{b} are represented as arrays, compare 
+@code{a.base_object} and @code{b.base_object};
+if they are equal, apply dependence tests (use access functions based on 
+base_objects).
+Else if both @code{a} and @code{b} are represented as pointers, compare 
+@code{a.first_location} and @code{b.first_location}; 
+if they are equal, apply dependence tests (use access functions based on 
+first location).
+However, if @code{a} and @code{b} are represented differently, only try 
+to prove that the bases are definitely different.
+
+@item Aliasing information.
+@item Alignment information.
+@end itemize
+
 The structure describing the relation between two data references is
 @code{data_dependence_relation} and the shorter name for a pointer to
 such a structure is @code{ddr_p}.  This structure contains: