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 /* The description of the grid of iterations that overlap.  At most
 194    two loops are considered at the same time just now, hence at most
 195    two functions are needed.  For each of the functions, we store
 196    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
 197    where x, y, ... are variables.  */
 198
 199 #define MAX_DIM 2
 200
 201 /* Special values of N.  */
 202 #define NO_DEPENDENCE 0
 203 #define NOT_KNOWN (MAX_DIM + 1)
 204 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
 205 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
 206 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
 207
 208 typedef VEC (tree, heap) *affine_fn;
 209
 210 typedef struct
 211 {
 212   unsigned n;
 213   affine_fn fns[MAX_DIM];
 214 } conflict_function;
 215
 216 /* What is a subscript?  Given two array accesses a subscript is the
 217    tuple composed of the access functions for a given dimension.
 218    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 219    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 220    are stored in the data_dependence_relation structure under the form
 221    of an array of subscripts.  */
 222
 223 struct subscript
 224 {
 225   /* A description of the iterations for which the elements are
 226      accessed twice.  */
 227   conflict_function *conflicting_iterations_in_a;
 228   conflict_function *conflicting_iterations_in_b;
 229
 230   /* This field stores the information about the iteration domain
 231      validity of the dependence relation.  */
 232   tree last_conflict;
 233
 234   /* Distance from the iteration that access a conflicting element in
 235      A to the iteration that access this same conflicting element in
 236      B.  The distance is a tree scalar expression, i.e. a constant or a
 237      symbolic expression, but certainly not a chrec function.  */
 238   tree distance;
 239 };
 240
 241 typedef struct subscript *subscript_p;
 242 DEF_VEC_P(subscript_p);
 243 DEF_VEC_ALLOC_P (subscript_p, heap);
 244
 245 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 246 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 247 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
 248 #define SUB_DISTANCE(SUB) SUB->distance
 249
 250 /* A data_dependence_relation represents a relation between two
 251    data_references A and B.  */
 252
 253 struct data_dependence_relation
 254 {
 255
 256   struct data_reference *a;
 257   struct data_reference *b;
 258
 259   /* When the dependence relation is affine, it can be represented by
 260      a distance vector.  */
 261   bool affine_p;
 262
 263   /* A "yes/no/maybe" field for the dependence relation:
 264
 265      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 266        relation between A and B, and the description of this relation
 267        is given in the SUBSCRIPTS array,
 268
 269      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 270        SUBSCRIPTS is empty,
 271
 272      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 273        but the analyzer cannot be more specific.  */
 274   tree are_dependent;
 275
 276   /* For each subscript in the dependence test, there is an element in
 277      this array.  This is the attribute that labels the edge A->B of
 278      the data_dependence_relation.  */
 279   VEC (subscript_p, heap) *subscripts;
 280
 281   /* The analyzed loop nest.  */
 282   VEC (loop_p, heap) *loop_nest;
 283
 284   /* The classic direction vector.  */
 285   VEC (lambda_vector, heap) *dir_vects;
 286
 287   /* The classic distance vector.  */
 288   VEC (lambda_vector, heap) *dist_vects;
 289 };
 290
 291 typedef struct data_dependence_relation *ddr_p;
 292 DEF_VEC_P(ddr_p);
 293 DEF_VEC_ALLOC_P(ddr_p,heap);
 294
 295 #define DDR_A(DDR) DDR->a
 296 #define DDR_B(DDR) DDR->b
 297 #define DDR_AFFINE_P(DDR) DDR->affine_p
 298 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 299 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 300 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
 301 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
 302
 303 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 304 /* The size of the direction/distance vectors: the number of loops in
 305    the loop nest.  */
 306 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
 307
 308 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 309 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 310 #define DDR_NUM_DIST_VECTS(DDR) \
 311   (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
 312 #define DDR_NUM_DIR_VECTS(DDR) \
 313   (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
 314 #define DDR_DIR_VECT(DDR, I) \
 315   VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
 316 #define DDR_DIST_VECT(DDR, I) \
 317   VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
 318
 319 \f
 320
 321 /* Describes a location of a memory reference.  */
 322
 323 typedef struct data_ref_loc_d
 324 {
 325   /* Position of the memory reference.  */
 326   tree *pos;
 327
 328   /* True if the memory reference is read.  */
 329   bool is_read;
 330 } data_ref_loc;
 331
 332 DEF_VEC_O (data_ref_loc);
 333 DEF_VEC_ALLOC_O (data_ref_loc, heap);
 334
 335 bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
 336 extern tree find_data_references_in_loop (struct loop *,
 337                                           VEC (data_reference_p, heap) **);
 338 extern void compute_data_dependences_for_loop (struct loop *, bool,
 339                                                VEC (data_reference_p, heap) **,
 340                                                VEC (ddr_p, heap) **);
 341 extern void print_direction_vector (FILE *, lambda_vector, int);
 342 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 343 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 344 extern void dump_subscript (FILE *, struct subscript *);
 345 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
 346 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
 347 extern void dump_data_reference (FILE *, struct data_reference *);
 348 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
 349 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 350 extern void dump_data_dependence_relation (FILE *,
 351                                            struct data_dependence_relation *);
 352 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
 353 extern void dump_data_dependence_direction (FILE *,
 354                                             enum data_dependence_direction);
 355 extern void free_dependence_relation (struct data_dependence_relation *);
 356 extern void free_dependence_relations (VEC (ddr_p, heap) *);
 357 extern void free_data_refs (VEC (data_reference_p, heap) *);
 358 extern struct data_reference *analyze_array (tree, tree, bool);
 359
 360
 361 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 362
 363 static inline int
 364 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
 365 {
 366   struct loop *loopi;
 367   int var_index;
 368
 369   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
 370        var_index++)
 371     if (loopi->num == var)
 372       break;
 373
 374   return var_index;
 375 }
 376
 377 /* In lambda-code.c  */
 378 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
 379
 380 #endif  /* GCC_TREE_DATA_REF_H  */