gcc/tree-data-ref.h

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-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
  34 First 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
  41 Base object info:
  42       base_object      a                              NULL
  43       access_fn        <access_fns of indexes of b>   NULL
  44
  45   **/
  46 struct 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
  57 struct 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
  66 enum data_ref_type {
  67   ARRAY_REF_TYPE,
  68   POINTER_REF_TYPE
  69 };
  70
  71 struct 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 typedef struct data_reference *data_reference_p;
 111 DEF_VEC_P(data_reference_p);
 112 DEF_VEC_ALLOC_P (data_reference_p, heap);
 113
 114 #define DR_STMT(DR)                (DR)->stmt
 115 #define DR_REF(DR)                 (DR)->ref
 116 #define DR_BASE_OBJECT(DR)         (DR)->object_info.base_object
 117 #define DR_TYPE(DR)                (DR)->type
 118 #define DR_ACCESS_FNS(DR)\
 119   (DR_TYPE(DR) == ARRAY_REF_TYPE ?  \
 120    (DR)->object_info.access_fns : (DR)->first_location.access_fns)
 121 #define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
 122 #define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))
 123 #define DR_IS_READ(DR)             (DR)->is_read
 124 #define DR_BASE_ADDRESS(DR)        (DR)->first_location.base_address
 125 #define DR_OFFSET(DR)              (DR)->first_location.offset
 126 #define DR_INIT(DR)                (DR)->first_location.init
 127 #define DR_STEP(DR)                (DR)->first_location.step
 128 #define DR_MEMTAG(DR)              (DR)->memtag
 129 #define DR_ALIGNED_TO(DR)          (DR)->aligned_to
 130 #define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
 131 #define DR_PTR_INFO(DR)            (DR)->ptr_info
 132 #define DR_SUBVARS(DR)             (DR)->subvars
 133
 134 #define DR_ACCESS_FNS_ADDR(DR)       \
 135   (DR_TYPE(DR) == ARRAY_REF_TYPE ?   \
 136    &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
 137 #define DR_SET_ACCESS_FNS(DR, ACC_FNS)         \
 138 {                                              \
 139   if (DR_TYPE(DR) == ARRAY_REF_TYPE)           \
 140     (DR)->object_info.access_fns = ACC_FNS;    \
 141   else                                         \
 142     (DR)->first_location.access_fns = ACC_FNS; \
 143 }
 144 #define DR_FREE_ACCESS_FNS(DR)                              \
 145 {                                                           \
 146   if (DR_TYPE(DR) == ARRAY_REF_TYPE)                        \
 147     VEC_free (tree, heap, (DR)->object_info.access_fns);    \
 148   else                                                      \
 149     VEC_free (tree, heap, (DR)->first_location.access_fns); \
 150 }
 151
 152 enum data_dependence_direction {
 153   dir_positive,
 154   dir_negative,
 155   dir_equal,
 156   dir_positive_or_negative,
 157   dir_positive_or_equal,
 158   dir_negative_or_equal,
 159   dir_star,
 160   dir_independent
 161 };
 162
 163 /* What is a subscript?  Given two array accesses a subscript is the
 164    tuple composed of the access functions for a given dimension.
 165    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 166    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 167    are stored in the data_dependence_relation structure under the form
 168    of an array of subscripts.  */
 169
 170 struct subscript
 171 {
 172   /* A description of the iterations for which the elements are
 173      accessed twice.  */
 174   tree conflicting_iterations_in_a;
 175   tree conflicting_iterations_in_b;
 176
 177   /* This field stores the information about the iteration domain
 178      validity of the dependence relation.  */
 179   tree last_conflict;
 180
 181   /* Distance from the iteration that access a conflicting element in
 182      A to the iteration that access this same conflicting element in
 183      B.  The distance is a tree scalar expression, i.e. a constant or a
 184      symbolic expression, but certainly not a chrec function.  */
 185   tree distance;
 186 };
 187
 188 typedef struct subscript *subscript_p;
 189 DEF_VEC_P(subscript_p);
 190 DEF_VEC_ALLOC_P (subscript_p, heap);
 191
 192 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 193 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 194 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
 195 #define SUB_DISTANCE(SUB) SUB->distance
 196
 197 typedef struct loop *loop_p;
 198 DEF_VEC_P(loop_p);
 199 DEF_VEC_ALLOC_P (loop_p, heap);
 200
 201 /* A data_dependence_relation represents a relation between two
 202    data_references A and B.  */
 203
 204 struct data_dependence_relation
 205 {
 206
 207   struct data_reference *a;
 208   struct data_reference *b;
 209
 210   /* When the dependence relation is affine, it can be represented by
 211      a distance vector.  */
 212   bool affine_p;
 213
 214   /* A "yes/no/maybe" field for the dependence relation:
 215
 216      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 217        relation between A and B, and the description of this relation
 218        is given in the SUBSCRIPTS array,
 219
 220      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 221        SUBSCRIPTS is empty,
 222
 223      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 224        but the analyzer cannot be more specific.  */
 225   tree are_dependent;
 226
 227   /* For each subscript in the dependence test, there is an element in
 228      this array.  This is the attribute that labels the edge A->B of
 229      the data_dependence_relation.  */
 230   VEC (subscript_p, heap) *subscripts;
 231
 232   /* The analyzed loop nest.  */
 233   VEC (loop_p, heap) *loop_nest;
 234
 235   /* The classic direction vector.  */
 236   VEC (lambda_vector, heap) *dir_vects;
 237
 238   /* The classic distance vector.  */
 239   VEC (lambda_vector, heap) *dist_vects;
 240 };
 241
 242 typedef struct data_dependence_relation *ddr_p;
 243 DEF_VEC_P(ddr_p);
 244 DEF_VEC_ALLOC_P(ddr_p,heap);
 245
 246 #define DDR_A(DDR) DDR->a
 247 #define DDR_B(DDR) DDR->b
 248 #define DDR_AFFINE_P(DDR) DDR->affine_p
 249 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 250 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 251 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
 252 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
 253
 254 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 255 /* The size of the direction/distance vectors: the number of loops in
 256    the loop nest.  */
 257 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
 258
 259 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 260 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 261 #define DDR_NUM_DIST_VECTS(DDR) \
 262   (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
 263 #define DDR_NUM_DIR_VECTS(DDR) \
 264   (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
 265 #define DDR_DIR_VECT(DDR, I) \
 266   VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
 267 #define DDR_DIST_VECT(DDR, I) \
 268   VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
 269
 270 \f
 271
 272 extern tree find_data_references_in_loop (struct loop *,
 273                                           VEC (data_reference_p, heap) **);
 274 extern void compute_data_dependences_for_loop (struct loop *, bool,
 275                                                VEC (data_reference_p, heap) **,
 276                                                VEC (ddr_p, heap) **);
 277 extern void print_direction_vector (FILE *, lambda_vector, int);
 278 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 279 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 280 extern void dump_subscript (FILE *, struct subscript *);
 281 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
 282 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
 283 extern void dump_data_reference (FILE *, struct data_reference *);
 284 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
 285 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 286 extern void dump_data_dependence_relation (FILE *,
 287                                            struct data_dependence_relation *);
 288 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
 289 extern void dump_data_dependence_direction (FILE *,
 290                                             enum data_dependence_direction);
 291 extern void free_dependence_relation (struct data_dependence_relation *);
 292 extern void free_dependence_relations (VEC (ddr_p, heap) *);
 293 extern void free_data_refs (VEC (data_reference_p, heap) *);
 294 extern struct data_reference *analyze_array (tree, tree, bool);
 295 extern void estimate_iters_using_array (tree, tree);
 296
 297
 298 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 299
 300 static inline int
 301 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
 302 {
 303   struct loop *loopi;
 304   int var_index;
 305
 306   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
 307        var_index++)
 308     if (loopi->num == var)
 309       break;
 310
 311   return var_index;
 312 }
 313
 314 /* In lambda-code.c  */
 315 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
 316
 317 #endif  /* GCC_TREE_DATA_REF_H  */