The code for the data dependence analysis can be found intree-data-ref.cc and its interface and data structures aredescribed intree-data-ref.h. The function that computes thedata dependences for all the array and pointer references for a givenloop iscompute_data_dependences_for_loop. This function iscurrently used by the linear loop transform and the vectorizationpasses. Before calling this function, one has to allocate two vectors:a first vector will contain the set of data references that arecontained in the analyzed loop body, and the second vector will containthe dependence relations between the data references. Thus if thevector of data references is of sizen, the vector containing thedependence relations will containn*n elements. However if theanalyzed loop contains side effects, such as calls that potentially caninterfere with the data references in the current analyzed loop, theanalysis stops while scanning the loop body for data references, andinserts a singlechrec_dont_know in the dependence relationarray.
The data references are discovered in a particular order during thescanning 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 thedata reference array. Two data references syntactically occur in theprogram in the same order as in the array of data references. Thissyntactic order is important in some classical data dependence tests,and mapping this order to the elements of this array avoids costlyqueries 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 referenceisdata_reference, wheredata_reference_p is a name of apointer to the data reference structure. The structure contains thefollowing elements:
base_object_info: Provides information about the base objectof the data reference and its access functions. These access functionsrepresent the evolution of the data reference in the loop relative toits base, in keeping with the classical meaning of the data referenceaccess function for the support of arrays. For example, for a referencea.b[i][j], the base object isa.b and the access functions,one for each array subscript, are:{i_init, + i_step}_1, {j_init, +, j_step}_2.first_location_in_loop: Provides information about the firstlocation accessed by the data reference in the loop and about the accessfunction used to represent evolution relative to this location. This datais used to support pointers, and is not used for arrays (for which wehave base objects). Pointer accesses are represented as a one-dimensionalaccess that starts from the first location accessed in the loop. Forexample:for1 i for2 j *((int *)p + i + j) = a[i][j];
The access function of the pointer access is{0, + 4B}_for2relative top + i. The access functions of the array are{i_init, + i_step}_for1 and{j_init, +, j_step}_for2relative toa.
Usually, the object the pointer refers to is either unknown, or we cannotprove 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 tworepresentations has all its fields filled for both data references.
The current strategy for data dependence tests is as follows:If botha andb are represented as arrays, comparea.base_object andb.base_object;if they are equal, apply dependence tests (use access functions based onbase_objects).Else if botha andb are represented as pointers, comparea.first_location andb.first_location;if they are equal, apply dependence tests (use access functions based onfirst location).However, ifa andb are represented differently, only tryto prove that the bases are definitely different.
The structure describing the relation between two data references isdata_dependence_relation and the shorter name for a pointer tosuch a structure isddr_p. This structure contains:
are_dependent that is set tochrec_knownif the analysis has proved that there is no dependence between these twodata references,chrec_dont_know if the analysis was not able todetermine any useful result and potentially there could exist adependence between these data references, andare_dependent isset toNULL_TREE if there exist a dependence relation between thedata references, and the description of this dependence relation isgiven in thesubscripts,dir_vects, anddist_vectsarrays,subscripts that contains a description of eachsubscript of the data references. Given two array accesses asubscript is the tuple composed of the access functions for a givendimension. For example, givenA[f1][f2][f3] andB[g1][g2][g3], there are three subscripts:(f1, g1), (f2,g2), (f3, g3).dir_vects anddist_vects that containclassical representations of the data dependences under the form ofdirection and distance dependence vectors,loop_nest that contains the loops towhich the distance and direction vectors refer to.Several functions for pretty printing the information extracted by thedata dependence analysis are available:dump_ddrs prints with amaximum verbosity the details of a data dependence relations array,dump_dist_dir_vectors prints only the classical distance anddirection vectors for a data dependence relations array, anddump_data_references prints the details of the data referencescontained in a data reference array.