Here is the documentation for the data dependence analysis.
@node Dependency analysis
@section Data Dependency Analysis
@cindex Data Dependency Analysis
The code for the data dependence analysis can be found in
@file{tree-data-ref.c} and its interface and data structures are
described in @file{tree-data-ref.h}. The function that computes the
data dependences for all the array and pointer references for a given
loop is @code{compute_data_dependences_for_loop}. This function is
currently used by the linear loop transform and the vectorization
passes. Before calling this function, one has to allocate two
vectors: a first vector will contain the set of data references that
are contained in the analyzed loop body, and the second vector will
contain the dependence relations between the data references. Thus if
the vector of data references is of size @code{n}, the vector
containing the dependence relations will contain @code{n*n} elements.
However if the analyzed loop contains side effects, such as calls that
potentially can interfere with the data references in the current
analyzed loop, the analysis stops while scanning the loop body for
data references, and inserts a single @code{chrec_dont_know} in the
dependence relation array.
The data references are discovered in a particular order during the
scanning of the loop body: the loop body is analyzed in execution
order, and the data references of each statement are pushed at the end
of the data reference array. Two data references syntactically occur
in the program in the same order as in the array of data references.
This 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.
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:
@itemize
@item a pointer to each data reference,
@item a tree node @code{are_dependent} that is set to
@code{chrec_known} if the analysis has proved that there is no
dependence between these two data references, @code{chrec_dont_know}
if the analysis was not able to determine any useful result and
potentially there could exist a dependence between these data
references, and @code{are_dependent} is set to @code{NULL_TREE} if
there exist a dependence relation between the data references, and the
description of this dependence relation is given in the
@code{subscripts}, @code{dir_vects}, and @code{dist_vects} arrays,
@item a boolean that determines whether the dependence relation can be
represented by a classical distance vector,
@item an array @code{subscripts} that contains a description of each
subscript of the data references. Given two array accesses a
subscript is the tuple composed of the access functions for a given
dimension. For example, given @code{A[f1][f2][f3]} and
@code{B[g1][g2][g3]}, there are three subscripts: @code{(f1, g1), (f2,
g2), (f3, g3)}.
@item two arrays @code{dir_vects} and @code{dist_vects} that contain
classical representations of the data dependences under the form of
direction and distance dependence vectors,
@item an array of loops @code{loop_nest} that contains the loops to
which the distance and direction vectors refer to.
@end itemize
Several functions for pretty printing the information extracted by the
data dependence analysis are available: @code{dump_ddrs} prints with a
maximum verbosity the details of a data dependence relations array,
@code{dump_dist_dir_vectors} prints only the classical distance and
direction vectors for a data dependence relations array, and
@code{dump_data_references} prints the details of the data references
contained in a data reference array.
