gcc/tree-data-ref.h

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003-2015 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
 148 typedef struct data_reference *data_reference_p;
 149
 150 enum data_dependence_direction {
 151   dir_positive,
 152   dir_negative,
 153   dir_equal,
 154   dir_positive_or_negative,
 155   dir_positive_or_equal,
 156   dir_negative_or_equal,
 157   dir_star,
 158   dir_independent
 159 };
 160
 161 /* The description of the grid of iterations that overlap.  At most
 162    two loops are considered at the same time just now, hence at most
 163    two functions are needed.  For each of the functions, we store
 164    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
 165    where x, y, ... are variables.  */
 166
 167 #define MAX_DIM 2
 168
 169 /* Special values of N.  */
 170 #define NO_DEPENDENCE 0
 171 #define NOT_KNOWN (MAX_DIM + 1)
 172 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
 173 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
 174 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
 175
 176 typedef vec<tree> affine_fn;
 177
 178 struct conflict_function
 179 {
 180   unsigned n;
 181   affine_fn fns[MAX_DIM];
 182 };
 183
 184 /* What is a subscript?  Given two array accesses a subscript is the
 185    tuple composed of the access functions for a given dimension.
 186    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 187    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 188    are stored in the data_dependence_relation structure under the form
 189    of an array of subscripts.  */
 190
 191 struct subscript
 192 {
 193   /* A description of the iterations for which the elements are
 194      accessed twice.  */
 195   conflict_function *conflicting_iterations_in_a;
 196   conflict_function *conflicting_iterations_in_b;
 197
 198   /* This field stores the information about the iteration domain
 199      validity of the dependence relation.  */
 200   tree last_conflict;
 201
 202   /* Distance from the iteration that access a conflicting element in
 203      A to the iteration that access this same conflicting element in
 204      B.  The distance is a tree scalar expression, i.e. a constant or a
 205      symbolic expression, but certainly not a chrec function.  */
 206   tree distance;
 207 };
 208
 209 typedef struct subscript *subscript_p;
 210
 211 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 212 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 213 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
 214 #define SUB_DISTANCE(SUB) SUB->distance
 215
 216 /* A data_dependence_relation represents a relation between two
 217    data_references A and B.  */
 218
 219 struct data_dependence_relation
 220 {
 221
 222   struct data_reference *a;
 223   struct data_reference *b;
 224
 225   /* A "yes/no/maybe" field for the dependence relation:
 226
 227      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 228        relation between A and B, and the description of this relation
 229        is given in the SUBSCRIPTS array,
 230
 231      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 232        SUBSCRIPTS is empty,
 233
 234      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 235        but the analyzer cannot be more specific.  */
 236   tree are_dependent;
 237
 238   /* For each subscript in the dependence test, there is an element in
 239      this array.  This is the attribute that labels the edge A->B of
 240      the data_dependence_relation.  */
 241   vec<subscript_p> subscripts;
 242
 243   /* The analyzed loop nest.  */
 244   vec<loop_p> loop_nest;
 245
 246   /* The classic direction vector.  */
 247   vec<lambda_vector> dir_vects;
 248
 249   /* The classic distance vector.  */
 250   vec<lambda_vector> dist_vects;
 251
 252   /* An index in loop_nest for the innermost loop that varies for
 253      this data dependence relation.  */
 254   unsigned inner_loop;
 255
 256   /* Is the dependence reversed with respect to the lexicographic order?  */
 257   bool reversed_p;
 258
 259   /* When the dependence relation is affine, it can be represented by
 260      a distance vector.  */
 261   bool affine_p;
 262
 263   /* Set to true when the dependence relation is on the same data
 264      access.  */
 265   bool self_reference_p;
 266 };
 267
 268 typedef struct data_dependence_relation *ddr_p;
 269
 270 #define DDR_A(DDR) DDR->a
 271 #define DDR_B(DDR) DDR->b
 272 #define DDR_AFFINE_P(DDR) DDR->affine_p
 273 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 274 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 275 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
 276 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
 277
 278 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 279 /* The size of the direction/distance vectors: the number of loops in
 280    the loop nest.  */
 281 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
 282 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
 283 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
 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   (DDR_DIST_VECTS (DDR).length ())
 289 #define DDR_NUM_DIR_VECTS(DDR) \
 290   (DDR_DIR_VECTS (DDR).length ())
 291 #define DDR_DIR_VECT(DDR, I) \
 292   DDR_DIR_VECTS (DDR)[I]
 293 #define DDR_DIST_VECT(DDR, I) \
 294   DDR_DIST_VECTS (DDR)[I]
 295 #define DDR_REVERSED_P(DDR) DDR->reversed_p
 296
 297 \f
 298 bool dr_analyze_innermost (struct data_reference *, struct loop *);
 299 extern bool compute_data_dependences_for_loop (struct loop *, bool,
 300                                                vec<loop_p> *,
 301                                                vec<data_reference_p> *,
 302                                                vec<ddr_p> *);
 303 extern void debug_ddrs (vec<ddr_p> );
 304 extern void dump_data_reference (FILE *, struct data_reference *);
 305 extern void debug (data_reference &ref);
 306 extern void debug (data_reference *ptr);
 307 extern void debug_data_reference (struct data_reference *);
 308 extern void debug_data_references (vec<data_reference_p> );
 309 extern void debug (vec<data_reference_p> &ref);
 310 extern void debug (vec<data_reference_p> *ptr);
 311 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 312 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
 313 extern void debug (vec<ddr_p> &ref);
 314 extern void debug (vec<ddr_p> *ptr);
 315 extern void debug_data_dependence_relations (vec<ddr_p> );
 316 extern void free_dependence_relation (struct data_dependence_relation *);
 317 extern void free_dependence_relations (vec<ddr_p> );
 318 extern void free_data_ref (data_reference_p);
 319 extern void free_data_refs (vec<data_reference_p> );
 320 extern bool find_data_references_in_stmt (struct loop *, gimple,
 321                                           vec<data_reference_p> *);
 322 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
 323                                                    vec<data_reference_p> *);
 324 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
 325 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
 326 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
 327 extern struct data_dependence_relation *initialize_data_dependence_relation
 328      (struct data_reference *, struct data_reference *, vec<loop_p>);
 329 extern void compute_affine_dependence (struct data_dependence_relation *,
 330                                        loop_p);
 331 extern void compute_self_dependence (struct data_dependence_relation *);
 332 extern bool compute_all_dependences (vec<data_reference_p> ,
 333                                      vec<ddr_p> *,
 334                                      vec<loop_p>, bool);
 335 extern tree find_data_references_in_bb (struct loop *, basic_block,
 336                                         vec<data_reference_p> *);
 337
 338 extern bool dr_may_alias_p (const struct data_reference *,
 339                             const struct data_reference *, bool);
 340 extern bool dr_equal_offsets_p (struct data_reference *,
 341                                 struct data_reference *);
 342
 343 /* Return true when the base objects of data references A and B are
 344    the same memory object.  */
 345
 346 static inline bool
 347 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
 348 {
 349   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
 350     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
 351 }
 352
 353 /* Return true when the data references A and B are accessing the same
 354    memory object with the same access functions.  */
 355
 356 static inline bool
 357 same_data_refs (data_reference_p a, data_reference_p b)
 358 {
 359   unsigned int i;
 360
 361   /* The references are exactly the same.  */
 362   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
 363     return true;
 364
 365   if (!same_data_refs_base_objects (a, b))
 366     return false;
 367
 368   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
 369     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
 370       return false;
 371
 372   return true;
 373 }
 374
 375 /* Return true when the DDR contains two data references that have the
 376    same access functions.  */
 377
 378 static inline bool
 379 same_access_functions (const struct data_dependence_relation *ddr)
 380 {
 381   unsigned i;
 382
 383   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 384     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
 385                           DR_ACCESS_FN (DDR_B (ddr), i)))
 386       return false;
 387
 388   return true;
 389 }
 390
 391 /* Returns true when all the dependences are computable.  */
 392
 393 inline bool
 394 known_dependences_p (vec<ddr_p> dependence_relations)
 395 {
 396   ddr_p ddr;
 397   unsigned int i;
 398
 399   FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
 400     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 401       return false;
 402
 403   return true;
 404 }
 405
 406 /* Returns the dependence level for a vector DIST of size LENGTH.
 407    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
 408    to the sequence of statements, not carried by any loop.  */
 409
 410 static inline unsigned
 411 dependence_level (lambda_vector dist_vect, int length)
 412 {
 413   int i;
 414
 415   for (i = 0; i < length; i++)
 416     if (dist_vect[i] != 0)
 417       return i + 1;
 418
 419   return 0;
 420 }
 421
 422 /* Return the dependence level for the DDR relation.  */
 423
 424 static inline unsigned
 425 ddr_dependence_level (ddr_p ddr)
 426 {
 427   unsigned vector;
 428   unsigned level = 0;
 429
 430   if (DDR_DIST_VECTS (ddr).exists ())
 431     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
 432
 433   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
 434     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
 435                                           DDR_NB_LOOPS (ddr)));
 436   return level;
 437 }
 438
 439 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 440
 441 static inline int
 442 index_in_loop_nest (int var, vec<loop_p> loop_nest)
 443 {
 444   struct loop *loopi;
 445   int var_index;
 446
 447   for (var_index = 0; loop_nest.iterate (var_index, &loopi);
 448        var_index++)
 449     if (loopi->num == var)
 450       break;
 451
 452   return var_index;
 453 }
 454
 455 /* Returns true when the data reference DR the form "A[i] = ..."
 456    with a stride equal to its unit type size.  */
 457
 458 static inline bool
 459 adjacent_dr_p (struct data_reference *dr)
 460 {
 461   /* If this is a bitfield store bail out.  */
 462   if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
 463       && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
 464     return false;
 465
 466   if (!DR_STEP (dr)
 467       || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
 468     return false;
 469
 470   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
 471                                          DR_STEP (dr)),
 472                              TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
 473 }
 474
 475 void split_constant_offset (tree , tree *, tree *);
 476
 477 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 478
 479 static inline int
 480 lambda_vector_gcd (lambda_vector vector, int size)
 481 {
 482   int i;
 483   int gcd1 = 0;
 484
 485   if (size > 0)
 486     {
 487       gcd1 = vector[0];
 488       for (i = 1; i < size; i++)
 489         gcd1 = gcd (gcd1, vector[i]);
 490     }
 491   return gcd1;
 492 }
 493
 494 /* Allocate a new vector of given SIZE.  */
 495
 496 static inline lambda_vector
 497 lambda_vector_new (int size)
 498 {
 499   /* ???  We shouldn't abuse the GC allocator here.  */
 500   return ggc_cleared_vec_alloc<int> (size);
 501 }
 502
 503 /* Clear out vector VEC1 of length SIZE.  */
 504
 505 static inline void
 506 lambda_vector_clear (lambda_vector vec1, int size)
 507 {
 508   memset (vec1, 0, size * sizeof (*vec1));
 509 }
 510
 511 /* Returns true when the vector V is lexicographically positive, in
 512    other words, when the first nonzero element is positive.  */
 513
 514 static inline bool
 515 lambda_vector_lexico_pos (lambda_vector v,
 516                           unsigned n)
 517 {
 518   unsigned i;
 519   for (i = 0; i < n; i++)
 520     {
 521       if (v[i] == 0)
 522         continue;
 523       if (v[i] < 0)
 524         return false;
 525       if (v[i] > 0)
 526         return true;
 527     }
 528   return true;
 529 }
 530
 531 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 532
 533 static inline bool
 534 lambda_vector_zerop (lambda_vector vec1, int size)
 535 {
 536   int i;
 537   for (i = 0; i < size; i++)
 538     if (vec1[i] != 0)
 539       return false;
 540   return true;
 541 }
 542
 543 /* Allocate a matrix of M rows x  N cols.  */
 544
 545 static inline lambda_matrix
 546 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
 547 {
 548   lambda_matrix mat;
 549   int i;
 550
 551   mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
 552
 553   for (i = 0; i < m; i++)
 554     mat[i] = XOBNEWVEC (lambda_obstack, int, n);
 555
 556   return mat;
 557 }
 558
 559 #endif  /* GCC_TREE_DATA_REF_H  */