1/* Data references and dependences detectors. 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <s.pop@laposte.net> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22#ifndef GCC_TREE_DATA_REF_H 23#define GCC_TREE_DATA_REF_H 24 25#include "lambda.h" 26 27/** {base_address + offset + init} is the first location accessed by data-ref 28 in the loop, and step is the stride of data-ref in the loop in bytes; 29 e.g.: 30 31 Example 1 Example 2 32 data-ref a[j].b[i][j] a + x + 16B (a is int*) 33 34First location info: 35 base_address &a a 36 offset j_0*D_j + i_0*D_i + C_a x 37 init C_b 16 38 step D_j 4 39 access_fn NULL {16, +, 1} 40 41Base object info: 42 base_object a NULL 43 access_fn <access_fns of indexes of b> NULL 44 45 **/ 46struct first_location_in_loop 47{ 48 tree base_address; 49 tree offset; 50 tree init; 51 tree step; 52 /* Access function related to first location in the loop. */ 53 VEC(tree,heap) *access_fns; 54 55}; 56 57struct base_object_info 58{ 59 /* The object. */ 60 tree base_object; 61 62 /* A list of chrecs. Access functions related to BASE_OBJECT. */ 63 VEC(tree,heap) *access_fns; 64}; 65 66enum data_ref_type { 67 ARRAY_REF_TYPE, 68 POINTER_REF_TYPE 69}; 70 71struct data_reference 72{ 73 /* A pointer to the statement that contains this DR. */ 74 tree stmt; 75 76 /* A pointer to the ARRAY_REF node. */ 77 tree ref; 78 79 /* Auxiliary info specific to a pass. */ 80 int aux; 81 82 /* True when the data reference is in RHS of a stmt. */ 83 bool is_read; 84 85 /* First location accessed by the data-ref in the loop. */ 86 struct first_location_in_loop first_location; 87 88 /* Base object related info. */ 89 struct base_object_info object_info; 90 91 /* Aliasing information. This field represents the symbol that 92 should be aliased by a pointer holding the address of this data 93 reference. If the original data reference was a pointer 94 dereference, then this field contains the memory tag that should 95 be used by the new vector-pointer. */ 96 tree memtag; 97 struct ptr_info_def *ptr_info; 98 subvar_t subvars; 99 100 /* Alignment information. */ 101 /* The offset of the data-reference from its base in bytes. */ 102 tree misalignment; 103 /* The maximum data-ref's alignment. */ 104 tree aligned_to; 105 106 /* The type of the data-ref. */ 107 enum data_ref_type type; 108}; 109 110#define DR_STMT(DR) (DR)->stmt 111#define DR_REF(DR) (DR)->ref 112#define DR_BASE_OBJECT(DR) (DR)->object_info.base_object 113#define DR_TYPE(DR) (DR)->type 114#define DR_ACCESS_FNS(DR)\ 115 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ 116 (DR)->object_info.access_fns : (DR)->first_location.access_fns) 117#define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I) 118#define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR)) 119#define DR_IS_READ(DR) (DR)->is_read 120#define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address 121#define DR_OFFSET(DR) (DR)->first_location.offset 122#define DR_INIT(DR) (DR)->first_location.init 123#define DR_STEP(DR) (DR)->first_location.step 124#define DR_MEMTAG(DR) (DR)->memtag 125#define DR_ALIGNED_TO(DR) (DR)->aligned_to 126#define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment 127#define DR_PTR_INFO(DR) (DR)->ptr_info 128#define DR_SUBVARS(DR) (DR)->subvars 129 130#define DR_ACCESS_FNS_ADDR(DR) \ 131 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ 132 &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns)) 133#define DR_SET_ACCESS_FNS(DR, ACC_FNS) \ 134{ \ 135 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ 136 (DR)->object_info.access_fns = ACC_FNS; \ 137 else \ 138 (DR)->first_location.access_fns = ACC_FNS; \ 139} 140#define DR_FREE_ACCESS_FNS(DR) \ 141{ \ 142 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ 143 VEC_free (tree, heap, (DR)->object_info.access_fns); \ 144 else \ 145 VEC_free (tree, heap, (DR)->first_location.access_fns); \ 146} 147 148enum data_dependence_direction { 149 dir_positive, 150 dir_negative, 151 dir_equal, 152 dir_positive_or_negative, 153 dir_positive_or_equal, 154 dir_negative_or_equal, 155 dir_star, 156 dir_independent 157}; 158 159/* What is a subscript? Given two array accesses a subscript is the 160 tuple composed of the access functions for a given dimension. 161 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three 162 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts 163 are stored in the data_dependence_relation structure under the form 164 of an array of subscripts. */ 165 166struct subscript 167{ 168 /* A description of the iterations for which the elements are 169 accessed twice. */ 170 tree conflicting_iterations_in_a; 171 tree conflicting_iterations_in_b; 172 173 /* This field stores the information about the iteration domain 174 validity of the dependence relation. */ 175 tree last_conflict; 176 177 /* Distance from the iteration that access a conflicting element in 178 A to the iteration that access this same conflicting element in 179 B. The distance is a tree scalar expression, i.e. a constant or a 180 symbolic expression, but certainly not a chrec function. */ 181 tree distance; 182}; 183 184#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a 185#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b 186#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict 187#define SUB_DISTANCE(SUB) SUB->distance 188 189/* A data_dependence_relation represents a relation between two 190 data_references A and B. */ 191 192struct data_dependence_relation 193{ 194 195 struct data_reference *a; 196 struct data_reference *b; 197 198 /* When the dependence relation is affine, it can be represented by 199 a distance vector. */ 200 bool affine_p; 201 202 /* A "yes/no/maybe" field for the dependence relation: 203 204 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 205 relation between A and B, and the description of this relation 206 is given in the SUBSCRIPTS array, 207 208 - when "ARE_DEPENDENT == chrec_known", there is no dependence and 209 SUBSCRIPTS is empty, 210 211 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 212 but the analyzer cannot be more specific. */ 213 tree are_dependent; 214 215 /* For each subscript in the dependence test, there is an element in 216 this array. This is the attribute that labels the edge A->B of 217 the data_dependence_relation. */ 218 varray_type subscripts; 219 220 /* The size of the direction/distance vectors: the depth of the 221 analyzed loop nest. */ 222 int size_vect; 223 224 /* The classic direction vector. */ 225 VEC(lambda_vector,heap) *dir_vects; 226 227 /* The classic distance vector. */ 228 VEC(lambda_vector,heap) *dist_vects; 229}; 230 231#define DDR_A(DDR) DDR->a 232#define DDR_B(DDR) DDR->b 233#define DDR_AFFINE_P(DDR) DDR->affine_p 234#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent 235#define DDR_SUBSCRIPTS(DDR) DDR->subscripts 236#define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \ 237 VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector"); 238#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I) 239#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR)) 240#define DDR_SIZE_VECT(DDR) DDR->size_vect 241 242#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) 243#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) 244#define DDR_NUM_DIST_VECTS(DDR) \ 245 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR))) 246#define DDR_NUM_DIR_VECTS(DDR) \ 247 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR))) 248#define DDR_DIR_VECT(DDR, I) \ 249 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I) 250#define DDR_DIST_VECT(DDR, I) \ 251 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I) 252 253 254 255extern tree find_data_references_in_loop (struct loop *, varray_type *); 256extern struct data_dependence_relation *initialize_data_dependence_relation 257(struct data_reference *, struct data_reference *); 258extern void compute_affine_dependence (struct data_dependence_relation *); 259extern void analyze_all_data_dependences (struct loops *); 260extern void compute_data_dependences_for_loop (struct loop *, bool, 261 varray_type *, varray_type *); 262 263extern void dump_subscript (FILE *, struct subscript *); 264extern void dump_ddrs (FILE *, varray_type); 265extern void dump_dist_dir_vectors (FILE *, varray_type); 266extern void dump_data_reference (FILE *, struct data_reference *); 267extern void dump_data_references (FILE *, varray_type); 268extern void dump_data_dependence_relation (FILE *, 269 struct data_dependence_relation *); 270extern void dump_data_dependence_relations (FILE *, varray_type); 271extern void dump_data_dependence_direction (FILE *, 272 enum data_dependence_direction); 273extern void free_dependence_relation (struct data_dependence_relation *); 274extern void free_dependence_relations (varray_type); 275extern void free_data_refs (varray_type); 276extern void compute_subscript_distance (struct data_dependence_relation *); 277extern struct data_reference *analyze_array (tree, tree, bool); 278extern void estimate_iters_using_array (tree, tree); 279 280 281 282 283#endif /* GCC_TREE_DATA_REF_H */ 284