1169689Skan/* Data references and dependences detectors. 2169689Skan Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Sebastian Pop <pop@cri.ensmp.fr> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan#ifndef GCC_TREE_DATA_REF_H 23169689Skan#define GCC_TREE_DATA_REF_H 24169689Skan 25169689Skan#include "lambda.h" 26169689Skan 27169689Skan/** {base_address + offset + init} is the first location accessed by data-ref 28169689Skan in the loop, and step is the stride of data-ref in the loop in bytes; 29169689Skan e.g.: 30169689Skan 31169689Skan Example 1 Example 2 32169689Skan data-ref a[j].b[i][j] a + x + 16B (a is int*) 33169689Skan 34169689SkanFirst location info: 35169689Skan base_address &a a 36169689Skan offset j_0*D_j + i_0*D_i + C_a x 37169689Skan init C_b 16 38169689Skan step D_j 4 39169689Skan access_fn NULL {16, +, 1} 40169689Skan 41169689SkanBase object info: 42169689Skan base_object a NULL 43169689Skan access_fn <access_fns of indexes of b> NULL 44169689Skan 45169689Skan **/ 46169689Skanstruct first_location_in_loop 47169689Skan{ 48169689Skan tree base_address; 49169689Skan tree offset; 50169689Skan tree init; 51169689Skan tree step; 52169689Skan /* Access function related to first location in the loop. */ 53169689Skan VEC(tree,heap) *access_fns; 54169689Skan 55169689Skan}; 56169689Skan 57169689Skanstruct base_object_info 58169689Skan{ 59169689Skan /* The object. */ 60169689Skan tree base_object; 61169689Skan 62169689Skan /* A list of chrecs. Access functions related to BASE_OBJECT. */ 63169689Skan VEC(tree,heap) *access_fns; 64169689Skan}; 65169689Skan 66169689Skanenum data_ref_type { 67169689Skan ARRAY_REF_TYPE, 68169689Skan POINTER_REF_TYPE 69169689Skan}; 70169689Skan 71169689Skanstruct data_reference 72169689Skan{ 73169689Skan /* A pointer to the statement that contains this DR. */ 74169689Skan tree stmt; 75169689Skan 76169689Skan /* A pointer to the ARRAY_REF node. */ 77169689Skan tree ref; 78169689Skan 79169689Skan /* Auxiliary info specific to a pass. */ 80169689Skan int aux; 81169689Skan 82169689Skan /* True when the data reference is in RHS of a stmt. */ 83169689Skan bool is_read; 84169689Skan 85169689Skan /* First location accessed by the data-ref in the loop. */ 86169689Skan struct first_location_in_loop first_location; 87169689Skan 88169689Skan /* Base object related info. */ 89169689Skan struct base_object_info object_info; 90169689Skan 91169689Skan /* Aliasing information. This field represents the symbol that 92169689Skan should be aliased by a pointer holding the address of this data 93169689Skan reference. If the original data reference was a pointer 94169689Skan dereference, then this field contains the memory tag that should 95169689Skan be used by the new vector-pointer. */ 96169689Skan tree memtag; 97169689Skan struct ptr_info_def *ptr_info; 98169689Skan subvar_t subvars; 99169689Skan 100169689Skan /* Alignment information. */ 101169689Skan /* The offset of the data-reference from its base in bytes. */ 102169689Skan tree misalignment; 103169689Skan /* The maximum data-ref's alignment. */ 104169689Skan tree aligned_to; 105169689Skan 106169689Skan /* The type of the data-ref. */ 107169689Skan enum data_ref_type type; 108169689Skan}; 109169689Skan 110169689Skantypedef struct data_reference *data_reference_p; 111169689SkanDEF_VEC_P(data_reference_p); 112169689SkanDEF_VEC_ALLOC_P (data_reference_p, heap); 113169689Skan 114169689Skan#define DR_STMT(DR) (DR)->stmt 115169689Skan#define DR_REF(DR) (DR)->ref 116169689Skan#define DR_BASE_OBJECT(DR) (DR)->object_info.base_object 117169689Skan#define DR_TYPE(DR) (DR)->type 118169689Skan#define DR_ACCESS_FNS(DR)\ 119169689Skan (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ 120169689Skan (DR)->object_info.access_fns : (DR)->first_location.access_fns) 121169689Skan#define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I) 122169689Skan#define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR)) 123169689Skan#define DR_IS_READ(DR) (DR)->is_read 124169689Skan#define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address 125169689Skan#define DR_OFFSET(DR) (DR)->first_location.offset 126169689Skan#define DR_INIT(DR) (DR)->first_location.init 127169689Skan#define DR_STEP(DR) (DR)->first_location.step 128169689Skan#define DR_MEMTAG(DR) (DR)->memtag 129169689Skan#define DR_ALIGNED_TO(DR) (DR)->aligned_to 130169689Skan#define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment 131169689Skan#define DR_PTR_INFO(DR) (DR)->ptr_info 132169689Skan#define DR_SUBVARS(DR) (DR)->subvars 133169689Skan 134169689Skan#define DR_ACCESS_FNS_ADDR(DR) \ 135169689Skan (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ 136169689Skan &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns)) 137169689Skan#define DR_SET_ACCESS_FNS(DR, ACC_FNS) \ 138169689Skan{ \ 139169689Skan if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ 140169689Skan (DR)->object_info.access_fns = ACC_FNS; \ 141169689Skan else \ 142169689Skan (DR)->first_location.access_fns = ACC_FNS; \ 143169689Skan} 144169689Skan#define DR_FREE_ACCESS_FNS(DR) \ 145169689Skan{ \ 146169689Skan if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ 147169689Skan VEC_free (tree, heap, (DR)->object_info.access_fns); \ 148169689Skan else \ 149169689Skan VEC_free (tree, heap, (DR)->first_location.access_fns); \ 150169689Skan} 151169689Skan 152169689Skanenum data_dependence_direction { 153169689Skan dir_positive, 154169689Skan dir_negative, 155169689Skan dir_equal, 156169689Skan dir_positive_or_negative, 157169689Skan dir_positive_or_equal, 158169689Skan dir_negative_or_equal, 159169689Skan dir_star, 160169689Skan dir_independent 161169689Skan}; 162169689Skan 163169689Skan/* What is a subscript? Given two array accesses a subscript is the 164169689Skan tuple composed of the access functions for a given dimension. 165169689Skan Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three 166169689Skan subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts 167169689Skan are stored in the data_dependence_relation structure under the form 168169689Skan of an array of subscripts. */ 169169689Skan 170169689Skanstruct subscript 171169689Skan{ 172169689Skan /* A description of the iterations for which the elements are 173169689Skan accessed twice. */ 174169689Skan tree conflicting_iterations_in_a; 175169689Skan tree conflicting_iterations_in_b; 176169689Skan 177169689Skan /* This field stores the information about the iteration domain 178169689Skan validity of the dependence relation. */ 179169689Skan tree last_conflict; 180169689Skan 181169689Skan /* Distance from the iteration that access a conflicting element in 182169689Skan A to the iteration that access this same conflicting element in 183169689Skan B. The distance is a tree scalar expression, i.e. a constant or a 184169689Skan symbolic expression, but certainly not a chrec function. */ 185169689Skan tree distance; 186169689Skan}; 187169689Skan 188169689Skantypedef struct subscript *subscript_p; 189169689SkanDEF_VEC_P(subscript_p); 190169689SkanDEF_VEC_ALLOC_P (subscript_p, heap); 191169689Skan 192169689Skan#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a 193169689Skan#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b 194169689Skan#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict 195169689Skan#define SUB_DISTANCE(SUB) SUB->distance 196169689Skan 197169689Skantypedef struct loop *loop_p; 198169689SkanDEF_VEC_P(loop_p); 199169689SkanDEF_VEC_ALLOC_P (loop_p, heap); 200169689Skan 201169689Skan/* A data_dependence_relation represents a relation between two 202169689Skan data_references A and B. */ 203169689Skan 204169689Skanstruct data_dependence_relation 205169689Skan{ 206169689Skan 207169689Skan struct data_reference *a; 208169689Skan struct data_reference *b; 209169689Skan 210169689Skan /* When the dependence relation is affine, it can be represented by 211169689Skan a distance vector. */ 212169689Skan bool affine_p; 213169689Skan 214169689Skan /* A "yes/no/maybe" field for the dependence relation: 215169689Skan 216169689Skan - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 217169689Skan relation between A and B, and the description of this relation 218169689Skan is given in the SUBSCRIPTS array, 219169689Skan 220169689Skan - when "ARE_DEPENDENT == chrec_known", there is no dependence and 221169689Skan SUBSCRIPTS is empty, 222169689Skan 223169689Skan - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 224169689Skan but the analyzer cannot be more specific. */ 225169689Skan tree are_dependent; 226169689Skan 227169689Skan /* For each subscript in the dependence test, there is an element in 228169689Skan this array. This is the attribute that labels the edge A->B of 229169689Skan the data_dependence_relation. */ 230169689Skan VEC (subscript_p, heap) *subscripts; 231169689Skan 232169689Skan /* The analyzed loop nest. */ 233169689Skan VEC (loop_p, heap) *loop_nest; 234169689Skan 235169689Skan /* The classic direction vector. */ 236169689Skan VEC (lambda_vector, heap) *dir_vects; 237169689Skan 238169689Skan /* The classic distance vector. */ 239169689Skan VEC (lambda_vector, heap) *dist_vects; 240169689Skan}; 241169689Skan 242169689Skantypedef struct data_dependence_relation *ddr_p; 243169689SkanDEF_VEC_P(ddr_p); 244169689SkanDEF_VEC_ALLOC_P(ddr_p,heap); 245169689Skan 246169689Skan#define DDR_A(DDR) DDR->a 247169689Skan#define DDR_B(DDR) DDR->b 248169689Skan#define DDR_AFFINE_P(DDR) DDR->affine_p 249169689Skan#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent 250169689Skan#define DDR_SUBSCRIPTS(DDR) DDR->subscripts 251169689Skan#define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I) 252169689Skan#define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR)) 253169689Skan 254169689Skan#define DDR_LOOP_NEST(DDR) DDR->loop_nest 255169689Skan/* The size of the direction/distance vectors: the number of loops in 256169689Skan the loop nest. */ 257169689Skan#define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR))) 258169689Skan 259169689Skan#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) 260169689Skan#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) 261169689Skan#define DDR_NUM_DIST_VECTS(DDR) \ 262169689Skan (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR))) 263169689Skan#define DDR_NUM_DIR_VECTS(DDR) \ 264169689Skan (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR))) 265169689Skan#define DDR_DIR_VECT(DDR, I) \ 266169689Skan VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I) 267169689Skan#define DDR_DIST_VECT(DDR, I) \ 268169689Skan VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I) 269169689Skan 270169689Skan 271169689Skan 272169689Skanextern tree find_data_references_in_loop (struct loop *, 273169689Skan VEC (data_reference_p, heap) **); 274169689Skanextern void compute_data_dependences_for_loop (struct loop *, bool, 275169689Skan VEC (data_reference_p, heap) **, 276169689Skan VEC (ddr_p, heap) **); 277169689Skanextern void print_direction_vector (FILE *, lambda_vector, int); 278169689Skanextern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int); 279169689Skanextern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int); 280169689Skanextern void dump_subscript (FILE *, struct subscript *); 281169689Skanextern void dump_ddrs (FILE *, VEC (ddr_p, heap) *); 282169689Skanextern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *); 283169689Skanextern void dump_data_reference (FILE *, struct data_reference *); 284169689Skanextern void dump_data_references (FILE *, VEC (data_reference_p, heap) *); 285169689Skanextern void debug_data_dependence_relation (struct data_dependence_relation *); 286169689Skanextern void dump_data_dependence_relation (FILE *, 287169689Skan struct data_dependence_relation *); 288169689Skanextern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *); 289169689Skanextern void dump_data_dependence_direction (FILE *, 290169689Skan enum data_dependence_direction); 291169689Skanextern void free_dependence_relation (struct data_dependence_relation *); 292169689Skanextern void free_dependence_relations (VEC (ddr_p, heap) *); 293169689Skanextern void free_data_refs (VEC (data_reference_p, heap) *); 294169689Skanextern struct data_reference *analyze_array (tree, tree, bool); 295169689Skanextern void estimate_iters_using_array (tree, tree); 296169689Skan 297169689Skan 298169689Skan/* Return the index of the variable VAR in the LOOP_NEST array. */ 299169689Skan 300169689Skanstatic inline int 301169689Skanindex_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest) 302169689Skan{ 303169689Skan struct loop *loopi; 304169689Skan int var_index; 305169689Skan 306169689Skan for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi); 307169689Skan var_index++) 308169689Skan if (loopi->num == var) 309169689Skan break; 310169689Skan 311169689Skan return var_index; 312169689Skan} 313169689Skan 314169689Skan/* In lambda-code.c */ 315169689Skanbool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *); 316169689Skan 317169689Skan#endif /* GCC_TREE_DATA_REF_H */ 318