gcc/tree-data-ref.h

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