gcc/tree-data-ref.h

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003-2016 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_TREE_DATA_REF_H
  22 #define GCC_TREE_DATA_REF_H
  23
  24 #include "graphds.h"
  25 #include "tree-chrec.h"
  26
  27 /*
  28   innermost_loop_behavior describes the evolution of the address of the memory
  29   reference in the innermost enclosing loop.  The address is expressed as
  30   BASE + STEP * # of iteration, and base is further decomposed as the base
  31   pointer (BASE_ADDRESS),  loop invariant offset (OFFSET) and
  32   constant offset (INIT).  Examples, in loop nest
  33
  34   for (i = 0; i < 100; i++)
  35     for (j = 3; j < 100; j++)
  36
  37                        Example 1                      Example 2
  38       data-ref         a[j].b[i][j]                   *(p + x + 16B + 4B * j)
  39
  40
  41   innermost_loop_behavior
  42       base_address     &a                             p
  43       offset           i * D_i                        x
  44       init             3 * D_j + offsetof (b)         28
  45       step             D_j                            4
  46
  47   */
  48 struct innermost_loop_behavior
  49 {
  50   tree base_address;
  51   tree offset;
  52   tree init;
  53   tree step;
  54
  55   /* Alignment information.  ALIGNED_TO is set to the largest power of two
  56      that divides OFFSET.  */
  57   tree aligned_to;
  58 };
  59
  60 /* Describes the evolutions of indices of the memory reference.  The indices
  61    are indices of the ARRAY_REFs, indexes in artificial dimensions
  62    added for member selection of records and the operands of MEM_REFs.
  63    BASE_OBJECT is the part of the reference that is loop-invariant
  64    (note that this reference does not have to cover the whole object
  65    being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
  66    not recommended to use BASE_OBJECT in any code generation).
  67    For the examples above,
  68
  69    base_object:        a                              *(p + x + 4B * j_0)
  70    indices:            {j_0, +, 1}_2                  {16, +, 4}_2
  71                        4
  72                        {i_0, +, 1}_1
  73                        {j_0, +, 1}_2
  74 */
  75
  76 struct indices
  77 {
  78   /* The object.  */
  79   tree base_object;
  80
  81   /* A list of chrecs.  Access functions of the indices.  */
  82   vec<tree> access_fns;
  83
  84   /* Whether BASE_OBJECT is an access representing the whole object
  85      or whether the access could not be constrained.  */
  86   bool unconstrained_base;
  87 };
  88
  89 struct dr_alias
  90 {
  91   /* The alias information that should be used for new pointers to this
  92      location.  */
  93   struct ptr_info_def *ptr_info;
  94 };
  95
  96 /* An integer vector.  A vector formally consists of an element of a vector
  97    space. A vector space is a set that is closed under vector addition
  98    and scalar multiplication.  In this vector space, an element is a list of
  99    integers.  */
 100 typedef int *lambda_vector;
 101
 102 /* An integer matrix.  A matrix consists of m vectors of length n (IE
 103    all vectors are the same length).  */
 104 typedef lambda_vector *lambda_matrix;
 105
 106
 107
 108 struct data_reference
 109 {
 110   /* A pointer to the statement that contains this DR.  */
 111   gimple *stmt;
 112
 113   /* A pointer to the memory reference.  */
 114   tree ref;
 115
 116   /* Auxiliary info specific to a pass.  */
 117   void *aux;
 118
 119   /* True when the data reference is in RHS of a stmt.  */
 120   bool is_read;
 121
 122   /* Behavior of the memory reference in the innermost loop.  */
 123   struct innermost_loop_behavior innermost;
 124
 125   /* Subscripts of this data reference.  */
 126   struct indices indices;
 127
 128   /* Alias information for the data reference.  */
 129   struct dr_alias alias;
 130 };
 131
 132 #define DR_STMT(DR)                (DR)->stmt
 133 #define DR_REF(DR)                 (DR)->ref
 134 #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
 135 #define DR_UNCONSTRAINED_BASE(DR)  (DR)->indices.unconstrained_base
 136 #define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
 137 #define DR_ACCESS_FN(DR, I)        DR_ACCESS_FNS (DR)[I]
 138 #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()
 139 #define DR_IS_READ(DR)             (DR)->is_read
 140 #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
 141 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
 142 #define DR_OFFSET(DR)              (DR)->innermost.offset
 143 #define DR_INIT(DR)                (DR)->innermost.init
 144 #define DR_STEP(DR)                (DR)->innermost.step
 145 #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
 146 #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
 147 #define DR_INNERMOST(DR)           (DR)->innermost
 148
 149 typedef struct data_reference *data_reference_p;
 150
 151 enum data_dependence_direction {
 152   dir_positive,
 153   dir_negative,
 154   dir_equal,
 155   dir_positive_or_negative,
 156   dir_positive_or_equal,
 157   dir_negative_or_equal,
 158   dir_star,
 159   dir_independent
 160 };
 161
 162 /* The description of the grid of iterations that overlap.  At most
 163    two loops are considered at the same time just now, hence at most
 164    two functions are needed.  For each of the functions, we store
 165    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
 166    where x, y, ... are variables.  */
 167
 168 #define MAX_DIM 2
 169
 170 /* Special values of N.  */
 171 #define NO_DEPENDENCE 0
 172 #define NOT_KNOWN (MAX_DIM + 1)
 173 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
 174 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
 175 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
 176
 177 typedef vec<tree> affine_fn;
 178
 179 struct conflict_function
 180 {
 181   unsigned n;
 182   affine_fn fns[MAX_DIM];
 183 };
 184
 185 /* What is a subscript?  Given two array accesses a subscript is the
 186    tuple composed of the access functions for a given dimension.
 187    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 188    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 189    are stored in the data_dependence_relation structure under the form
 190    of an array of subscripts.  */
 191
 192 struct subscript
 193 {
 194   /* A description of the iterations for which the elements are
 195      accessed twice.  */
 196   conflict_function *conflicting_iterations_in_a;
 197   conflict_function *conflicting_iterations_in_b;
 198
 199   /* This field stores the information about the iteration domain
 200      validity of the dependence relation.  */
 201   tree last_conflict;
 202
 203   /* Distance from the iteration that access a conflicting element in
 204      A to the iteration that access this same conflicting element in
 205      B.  The distance is a tree scalar expression, i.e. a constant or a
 206      symbolic expression, but certainly not a chrec function.  */
 207   tree distance;
 208 };
 209
 210 typedef struct subscript *subscript_p;
 211
 212 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 213 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 214 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
 215 #define SUB_DISTANCE(SUB) SUB->distance
 216
 217 /* A data_dependence_relation represents a relation between two
 218    data_references A and B.  */
 219
 220 struct data_dependence_relation
 221 {
 222
 223   struct data_reference *a;
 224   struct data_reference *b;
 225
 226   /* A "yes/no/maybe" field for the dependence relation:
 227
 228      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 229        relation between A and B, and the description of this relation
 230        is given in the SUBSCRIPTS array,
 231
 232      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 233        SUBSCRIPTS is empty,
 234
 235      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 236        but the analyzer cannot be more specific.  */
 237   tree are_dependent;
 238
 239   /* For each subscript in the dependence test, there is an element in
 240      this array.  This is the attribute that labels the edge A->B of
 241      the data_dependence_relation.  */
 242   vec<subscript_p> subscripts;
 243
 244   /* The analyzed loop nest.  */
 245   vec<loop_p> loop_nest;
 246
 247   /* The classic direction vector.  */
 248   vec<lambda_vector> dir_vects;
 249
 250   /* The classic distance vector.  */
 251   vec<lambda_vector> dist_vects;
 252
 253   /* An index in loop_nest for the innermost loop that varies for
 254      this data dependence relation.  */
 255   unsigned inner_loop;
 256
 257   /* Is the dependence reversed with respect to the lexicographic order?  */
 258   bool reversed_p;
 259
 260   /* When the dependence relation is affine, it can be represented by
 261      a distance vector.  */
 262   bool affine_p;
 263
 264   /* Set to true when the dependence relation is on the same data
 265      access.  */
 266   bool self_reference_p;
 267 };
 268
 269 typedef struct data_dependence_relation *ddr_p;
 270
 271 #define DDR_A(DDR) DDR->a
 272 #define DDR_B(DDR) DDR->b
 273 #define DDR_AFFINE_P(DDR) DDR->affine_p
 274 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 275 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 276 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
 277 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
 278
 279 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 280 /* The size of the direction/distance vectors: the number of loops in
 281    the loop nest.  */
 282 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
 283 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
 284 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
 285
 286 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 287 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 288 #define DDR_NUM_DIST_VECTS(DDR) \
 289   (DDR_DIST_VECTS (DDR).length ())
 290 #define DDR_NUM_DIR_VECTS(DDR) \
 291   (DDR_DIR_VECTS (DDR).length ())
 292 #define DDR_DIR_VECT(DDR, I) \
 293   DDR_DIR_VECTS (DDR)[I]
 294 #define DDR_DIST_VECT(DDR, I) \
 295   DDR_DIST_VECTS (DDR)[I]
 296 #define DDR_REVERSED_P(DDR) DDR->reversed_p
 297
 298 \f
 299 bool dr_analyze_innermost (struct data_reference *, struct loop *);
 300 extern bool compute_data_dependences_for_loop (struct loop *, bool,
 301                                                vec<loop_p> *,
 302                                                vec<data_reference_p> *,
 303                                                vec<ddr_p> *);
 304 extern void debug_ddrs (vec<ddr_p> );
 305 extern void dump_data_reference (FILE *, struct data_reference *);
 306 extern void debug (data_reference &ref);
 307 extern void debug (data_reference *ptr);
 308 extern void debug_data_reference (struct data_reference *);
 309 extern void debug_data_references (vec<data_reference_p> );
 310 extern void debug (vec<data_reference_p> &ref);
 311 extern void debug (vec<data_reference_p> *ptr);
 312 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 313 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
 314 extern void debug (vec<ddr_p> &ref);
 315 extern void debug (vec<ddr_p> *ptr);
 316 extern void debug_data_dependence_relations (vec<ddr_p> );
 317 extern void free_dependence_relation (struct data_dependence_relation *);
 318 extern void free_dependence_relations (vec<ddr_p> );
 319 extern void free_data_ref (data_reference_p);
 320 extern void free_data_refs (vec<data_reference_p> );
 321 extern bool find_data_references_in_stmt (struct loop *, gimple *,
 322                                           vec<data_reference_p> *);
 323 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple *,
 324                                                    vec<data_reference_p> *);
 325 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
 326 bool loop_nest_has_data_refs (loop_p loop);
 327 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool);
 328 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
 329 extern struct data_dependence_relation *initialize_data_dependence_relation
 330      (struct data_reference *, struct data_reference *, vec<loop_p>);
 331 extern void compute_affine_dependence (struct data_dependence_relation *,
 332                                        loop_p);
 333 extern void compute_self_dependence (struct data_dependence_relation *);
 334 extern bool compute_all_dependences (vec<data_reference_p> ,
 335                                      vec<ddr_p> *,
 336                                      vec<loop_p>, bool);
 337 extern tree find_data_references_in_bb (struct loop *, basic_block,
 338                                         vec<data_reference_p> *);
 339
 340 extern bool dr_may_alias_p (const struct data_reference *,
 341                             const struct data_reference *, bool);
 342 extern bool dr_equal_offsets_p (struct data_reference *,
 343                                 struct data_reference *);
 344
 345 /* Return true when the base objects of data references A and B are
 346    the same memory object.  */
 347
 348 static inline bool
 349 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
 350 {
 351   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
 352     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
 353 }
 354
 355 /* Return true when the data references A and B are accessing the same
 356    memory object with the same access functions.  */
 357
 358 static inline bool
 359 same_data_refs (data_reference_p a, data_reference_p b)
 360 {
 361   unsigned int i;
 362
 363   /* The references are exactly the same.  */
 364   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
 365     return true;
 366
 367   if (!same_data_refs_base_objects (a, b))
 368     return false;
 369
 370   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
 371     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
 372       return false;
 373
 374   return true;
 375 }
 376
 377 /* Return true when the DDR contains two data references that have the
 378    same access functions.  */
 379
 380 static inline bool
 381 same_access_functions (const struct data_dependence_relation *ddr)
 382 {
 383   unsigned i;
 384
 385   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 386     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
 387                           DR_ACCESS_FN (DDR_B (ddr), i)))
 388       return false;
 389
 390   return true;
 391 }
 392
 393 /* Returns true when all the dependences are computable.  */
 394
 395 inline bool
 396 known_dependences_p (vec<ddr_p> dependence_relations)
 397 {
 398   ddr_p ddr;
 399   unsigned int i;
 400
 401   FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
 402     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 403       return false;
 404
 405   return true;
 406 }
 407
 408 /* Returns the dependence level for a vector DIST of size LENGTH.
 409    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
 410    to the sequence of statements, not carried by any loop.  */
 411
 412 static inline unsigned
 413 dependence_level (lambda_vector dist_vect, int length)
 414 {
 415   int i;
 416
 417   for (i = 0; i < length; i++)
 418     if (dist_vect[i] != 0)
 419       return i + 1;
 420
 421   return 0;
 422 }
 423
 424 /* Return the dependence level for the DDR relation.  */
 425
 426 static inline unsigned
 427 ddr_dependence_level (ddr_p ddr)
 428 {
 429   unsigned vector;
 430   unsigned level = 0;
 431
 432   if (DDR_DIST_VECTS (ddr).exists ())
 433     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
 434
 435   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
 436     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
 437                                           DDR_NB_LOOPS (ddr)));
 438   return level;
 439 }
 440
 441 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 442
 443 static inline int
 444 index_in_loop_nest (int var, vec<loop_p> loop_nest)
 445 {
 446   struct loop *loopi;
 447   int var_index;
 448
 449   for (var_index = 0; loop_nest.iterate (var_index, &loopi);
 450        var_index++)
 451     if (loopi->num == var)
 452       break;
 453
 454   return var_index;
 455 }
 456
 457 /* Returns true when the data reference DR the form "A[i] = ..."
 458    with a stride equal to its unit type size.  */
 459
 460 static inline bool
 461 adjacent_dr_p (struct data_reference *dr)
 462 {
 463   /* If this is a bitfield store bail out.  */
 464   if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
 465       && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
 466     return false;
 467
 468   if (!DR_STEP (dr)
 469       || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
 470     return false;
 471
 472   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
 473                                          DR_STEP (dr)),
 474                              TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
 475 }
 476
 477 void split_constant_offset (tree , tree *, tree *);
 478
 479 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 480
 481 static inline int
 482 lambda_vector_gcd (lambda_vector vector, int size)
 483 {
 484   int i;
 485   int gcd1 = 0;
 486
 487   if (size > 0)
 488     {
 489       gcd1 = vector[0];
 490       for (i = 1; i < size; i++)
 491         gcd1 = gcd (gcd1, vector[i]);
 492     }
 493   return gcd1;
 494 }
 495
 496 /* Allocate a new vector of given SIZE.  */
 497
 498 static inline lambda_vector
 499 lambda_vector_new (int size)
 500 {
 501   /* ???  We shouldn't abuse the GC allocator here.  */
 502   return ggc_cleared_vec_alloc<int> (size);
 503 }
 504
 505 /* Clear out vector VEC1 of length SIZE.  */
 506
 507 static inline void
 508 lambda_vector_clear (lambda_vector vec1, int size)
 509 {
 510   memset (vec1, 0, size * sizeof (*vec1));
 511 }
 512
 513 /* Returns true when the vector V is lexicographically positive, in
 514    other words, when the first nonzero element is positive.  */
 515
 516 static inline bool
 517 lambda_vector_lexico_pos (lambda_vector v,
 518                           unsigned n)
 519 {
 520   unsigned i;
 521   for (i = 0; i < n; i++)
 522     {
 523       if (v[i] == 0)
 524         continue;
 525       if (v[i] < 0)
 526         return false;
 527       if (v[i] > 0)
 528         return true;
 529     }
 530   return true;
 531 }
 532
 533 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 534
 535 static inline bool
 536 lambda_vector_zerop (lambda_vector vec1, int size)
 537 {
 538   int i;
 539   for (i = 0; i < size; i++)
 540     if (vec1[i] != 0)
 541       return false;
 542   return true;
 543 }
 544
 545 /* Allocate a matrix of M rows x  N cols.  */
 546
 547 static inline lambda_matrix
 548 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
 549 {
 550   lambda_matrix mat;
 551   int i;
 552
 553   mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
 554
 555   for (i = 0; i < m; i++)
 556     mat[i] = XOBNEWVEC (lambda_obstack, int, n);
 557
 558   return mat;
 559 }
 560
 561 #endif  /* GCC_TREE_DATA_REF_H  */