gcc/tree-data-ref.h

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