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 /*
  28   The first location accessed by data-ref in the loop is the address of data-ref's
  29   base (BASE_ADDRESS) plus the initial offset from the base. We divide the initial offset
  30   into two parts: loop invariant offset (OFFSET) and constant offset (INIT).
  31   STEP is the stride of data-ref in the loop in bytes.
  32
  33                        Example 1                      Example 2
  34       data-ref         a[j].b[i][j]                   a + x + 16B (a is int*)
  35
  36   First location info:
  37       base_address     &a                             a
  38       offset           j_0*D_j + i_0*D_i              x
  39       init             C_b + C_a                      16
  40       step             D_j                            4
  41       access_fn        NULL                           {16, +, 1}
  42
  43   Base object info:
  44       base_object      a                              NULL
  45       access_fn        <access_fns of indexes of b>   NULL
  46
  47   */
  48 struct first_location_in_loop
  49 {
  50   tree base_address;
  51   tree offset;
  52   tree init;
  53   tree step;
  54   /* Access function related to first location in the loop.  */
  55   VEC(tree,heap) *access_fns;
  56 };
  57
  58 struct base_object_info
  59 {
  60   /* The object.  */
  61   tree base_object;
  62
  63   /* A list of chrecs.  Access functions related to BASE_OBJECT.  */
  64   VEC(tree,heap) *access_fns;
  65 };
  66
  67 enum data_ref_type {
  68   ARRAY_REF_TYPE,
  69   POINTER_REF_TYPE
  70 };
  71
  72 struct data_reference
  73 {
  74   /* A pointer to the statement that contains this DR.  */
  75   tree stmt;
  76
  77   /* A pointer to the ARRAY_REF node.  */
  78   tree ref;
  79
  80   /* Auxiliary info specific to a pass.  */
  81   int aux;
  82
  83   /* True when the data reference is in RHS of a stmt.  */
  84   bool is_read;
  85
  86   /* First location accessed by the data-ref in the loop.  */
  87   struct first_location_in_loop first_location;
  88
  89   /* Base object related info.  */
  90   struct base_object_info object_info;
  91
  92   /* Aliasing information.  This field represents the symbol that
  93      should be aliased by a pointer holding the address of this data
  94      reference.  If the original data reference was a pointer
  95      dereference, then this field contains the memory tag that should
  96      be used by the new vector-pointer.  */
  97   tree memtag;
  98   struct ptr_info_def *ptr_info;
  99   subvar_t subvars;
 100
 101   /* Alignment information.
 102      MISALIGNMENT is the offset of the data-reference from its base in bytes.
 103      ALIGNED_TO is the maximum data-ref's alignment.
 104
 105      Example 1,
 106        for i
 107           for (j = 3; j < N; j++)
 108             a[j].b[i][j] = 0;
 109
 110      For a[j].b[i][j], the offset from base (calculated in get_inner_reference()
 111      will be 'i * C_i + j * C_j + C'.
 112      We try to substitute the variables of the offset expression
 113      with initial_condition of the corresponding access_fn in the loop.
 114      'i' cannot be substituted, since its access_fn in the inner loop is i. 'j'
 115      will be substituted with 3.
 116
 117      Example 2
 118         for (j = 3; j < N; j++)
 119           a[j].b[5][j] = 0;
 120
 121      Here the offset expression (j * C_j + C) will not contain variables after
 122      substitution of j=3 (3*C_j + C).
 123
 124      Misalignment can be calculated only if all the variables can be
 125      substituted with constants, otherwise, we record maximum possible alignment
 126      in ALIGNED_TO. In Example 1, since 'i' cannot be substituted,
 127      MISALIGNMENT will be NULL_TREE, and the biggest divider of C_i (a power of
 128      2) will be recorded in ALIGNED_TO.
 129
 130      In Example 2, MISALIGNMENT will be the value of 3*C_j + C in bytes, and
 131      ALIGNED_TO will be NULL_TREE.
 132   */
 133   tree misalignment;
 134   tree aligned_to;
 135
 136   /* The type of the data-ref.  */
 137   enum data_ref_type type;
 138 };
 139
 140 typedef struct data_reference *data_reference_p;
 141 DEF_VEC_P(data_reference_p);
 142 DEF_VEC_ALLOC_P (data_reference_p, heap);
 143
 144 #define DR_STMT(DR)                (DR)->stmt
 145 #define DR_REF(DR)                 (DR)->ref
 146 #define DR_BASE_OBJECT(DR)         (DR)->object_info.base_object
 147 #define DR_TYPE(DR)                (DR)->type
 148 #define DR_ACCESS_FNS(DR)\
 149   (DR_TYPE(DR) == ARRAY_REF_TYPE ?  \
 150    (DR)->object_info.access_fns : (DR)->first_location.access_fns)
 151 #define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
 152 #define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))
 153 #define DR_IS_READ(DR)             (DR)->is_read
 154 #define DR_BASE_ADDRESS(DR)        (DR)->first_location.base_address
 155 #define DR_OFFSET(DR)              (DR)->first_location.offset
 156 #define DR_INIT(DR)                (DR)->first_location.init
 157 #define DR_STEP(DR)                (DR)->first_location.step
 158 #define DR_MEMTAG(DR)              (DR)->memtag
 159 #define DR_ALIGNED_TO(DR)          (DR)->aligned_to
 160 #define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
 161 #define DR_PTR_INFO(DR)            (DR)->ptr_info
 162 #define DR_SUBVARS(DR)             (DR)->subvars
 163
 164 #define DR_ACCESS_FNS_ADDR(DR)       \
 165   (DR_TYPE(DR) == ARRAY_REF_TYPE ?   \
 166    &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
 167 #define DR_SET_ACCESS_FNS(DR, ACC_FNS)         \
 168 {                                              \
 169   if (DR_TYPE(DR) == ARRAY_REF_TYPE)           \
 170     (DR)->object_info.access_fns = ACC_FNS;    \
 171   else                                         \
 172     (DR)->first_location.access_fns = ACC_FNS; \
 173 }
 174 #define DR_FREE_ACCESS_FNS(DR)                              \
 175 {                                                           \
 176   if (DR_TYPE(DR) == ARRAY_REF_TYPE)                        \
 177     VEC_free (tree, heap, (DR)->object_info.access_fns);    \
 178   else                                                      \
 179     VEC_free (tree, heap, (DR)->first_location.access_fns); \
 180 }
 181
 182 enum data_dependence_direction {
 183   dir_positive,
 184   dir_negative,
 185   dir_equal,
 186   dir_positive_or_negative,
 187   dir_positive_or_equal,
 188   dir_negative_or_equal,
 189   dir_star,
 190   dir_independent
 191 };
 192
 193 /* What is a subscript?  Given two array accesses a subscript is the
 194    tuple composed of the access functions for a given dimension.
 195    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 196    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 197    are stored in the data_dependence_relation structure under the form
 198    of an array of subscripts.  */
 199
 200 struct subscript
 201 {
 202   /* A description of the iterations for which the elements are
 203      accessed twice.  */
 204   tree conflicting_iterations_in_a;
 205   tree conflicting_iterations_in_b;
 206
 207   /* This field stores the information about the iteration domain
 208      validity of the dependence relation.  */
 209   tree last_conflict;
 210
 211   /* Distance from the iteration that access a conflicting element in
 212      A to the iteration that access this same conflicting element in
 213      B.  The distance is a tree scalar expression, i.e. a constant or a
 214      symbolic expression, but certainly not a chrec function.  */
 215   tree distance;
 216 };
 217
 218 typedef struct subscript *subscript_p;
 219 DEF_VEC_P(subscript_p);
 220 DEF_VEC_ALLOC_P (subscript_p, heap);
 221
 222 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 223 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 224 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
 225 #define SUB_DISTANCE(SUB) SUB->distance
 226
 227 /* A data_dependence_relation represents a relation between two
 228    data_references A and B.  */
 229
 230 struct data_dependence_relation
 231 {
 232
 233   struct data_reference *a;
 234   struct data_reference *b;
 235
 236   /* When the dependence relation is affine, it can be represented by
 237      a distance vector.  */
 238   bool affine_p;
 239
 240   /* A "yes/no/maybe" field for the dependence relation:
 241
 242      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 243        relation between A and B, and the description of this relation
 244        is given in the SUBSCRIPTS array,
 245
 246      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 247        SUBSCRIPTS is empty,
 248
 249      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 250        but the analyzer cannot be more specific.  */
 251   tree are_dependent;
 252
 253   /* For each subscript in the dependence test, there is an element in
 254      this array.  This is the attribute that labels the edge A->B of
 255      the data_dependence_relation.  */
 256   VEC (subscript_p, heap) *subscripts;
 257
 258   /* The analyzed loop nest.  */
 259   VEC (loop_p, heap) *loop_nest;
 260
 261   /* The classic direction vector.  */
 262   VEC (lambda_vector, heap) *dir_vects;
 263
 264   /* The classic distance vector.  */
 265   VEC (lambda_vector, heap) *dist_vects;
 266 };
 267
 268 typedef struct data_dependence_relation *ddr_p;
 269 DEF_VEC_P(ddr_p);
 270 DEF_VEC_ALLOC_P(ddr_p,heap);
 271
 272 #define DDR_A(DDR) DDR->a
 273 #define DDR_B(DDR) DDR->b
 274 #define DDR_AFFINE_P(DDR) DDR->affine_p
 275 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 276 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 277 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
 278 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
 279
 280 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 281 /* The size of the direction/distance vectors: the number of loops in
 282    the loop nest.  */
 283 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
 284
 285 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 286 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 287 #define DDR_NUM_DIST_VECTS(DDR) \
 288   (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
 289 #define DDR_NUM_DIR_VECTS(DDR) \
 290   (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
 291 #define DDR_DIR_VECT(DDR, I) \
 292   VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
 293 #define DDR_DIST_VECT(DDR, I) \
 294   VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
 295
 296 \f
 297
 298 /* Describes a location of a memory reference.  */
 299
 300 typedef struct data_ref_loc_d
 301 {
 302   /* Position of the memory reference.  */
 303   tree *pos;
 304
 305   /* True if the memory reference is read.  */
 306   bool is_read;
 307 } data_ref_loc;
 308
 309 DEF_VEC_O (data_ref_loc);
 310 DEF_VEC_ALLOC_O (data_ref_loc, heap);
 311
 312 bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
 313 extern tree find_data_references_in_loop (struct loop *,
 314                                           VEC (data_reference_p, heap) **);
 315 extern void compute_data_dependences_for_loop (struct loop *, bool,
 316                                                VEC (data_reference_p, heap) **,
 317                                                VEC (ddr_p, heap) **);
 318 extern void print_direction_vector (FILE *, lambda_vector, int);
 319 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 320 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 321 extern void dump_subscript (FILE *, struct subscript *);
 322 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
 323 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
 324 extern void dump_data_reference (FILE *, struct data_reference *);
 325 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
 326 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 327 extern void dump_data_dependence_relation (FILE *,
 328                                            struct data_dependence_relation *);
 329 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
 330 extern void dump_data_dependence_direction (FILE *,
 331                                             enum data_dependence_direction);
 332 extern void free_dependence_relation (struct data_dependence_relation *);
 333 extern void free_dependence_relations (VEC (ddr_p, heap) *);
 334 extern void free_data_refs (VEC (data_reference_p, heap) *);
 335 extern struct data_reference *analyze_array (tree, tree, bool);
 336
 337
 338 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 339
 340 static inline int
 341 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
 342 {
 343   struct loop *loopi;
 344   int var_index;
 345
 346   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
 347        var_index++)
 348     if (loopi->num == var)
 349       break;
 350
 351   return var_index;
 352 }
 353
 354 /* In lambda-code.c  */
 355 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
 356
 357 #endif  /* GCC_TREE_DATA_REF_H  */