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 "omega.h"
  26 #include "tree-chrec.h"
  27
  28 /*
  29   innermost_loop_behavior describes the evolution of the address of the memory
  30   reference in the innermost enclosing loop.  The address is expressed as
  31   BASE + STEP * # of iteration, and base is further decomposed as the base
  32   pointer (BASE_ADDRESS),  loop invariant offset (OFFSET) and
  33   constant offset (INIT).  Examples, in loop nest
  34
  35   for (i = 0; i < 100; i++)
  36     for (j = 3; j < 100; j++)
  37
  38                        Example 1                      Example 2
  39       data-ref         a[j].b[i][j]                   *(p + x + 16B + 4B * j)
  40
  41
  42   innermost_loop_behavior
  43       base_address     &a                             p
  44       offset           i * D_i                        x
  45       init             3 * D_j + offsetof (b)         28
  46       step             D_j                            4
  47
  48   */
  49 struct innermost_loop_behavior
  50 {
  51   tree base_address;
  52   tree offset;
  53   tree init;
  54   tree step;
  55
  56   /* Alignment information.  ALIGNED_TO is set to the largest power of two
  57      that divides OFFSET.  */
  58   tree aligned_to;
  59 };
  60
  61 /* Describes the evolutions of indices of the memory reference.  The indices
  62    are indices of the ARRAY_REFs, indexes in artificial dimensions
  63    added for member selection of records and the operands of MEM_REFs.
  64    BASE_OBJECT is the part of the reference that is loop-invariant
  65    (note that this reference does not have to cover the whole object
  66    being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
  67    not recommended to use BASE_OBJECT in any code generation).
  68    For the examples above,
  69
  70    base_object:        a                              *(p + x + 4B * j_0)
  71    indices:            {j_0, +, 1}_2                  {16, +, 4}_2
  72                        4
  73                        {i_0, +, 1}_1
  74                        {j_0, +, 1}_2
  75 */
  76
  77 struct indices
  78 {
  79   /* The object.  */
  80   tree base_object;
  81
  82   /* A list of chrecs.  Access functions of the indices.  */
  83   vec<tree> access_fns;
  84
  85   /* Whether BASE_OBJECT is an access representing the whole object
  86      or whether the access could not be constrained.  */
  87   bool unconstrained_base;
  88 };
  89
  90 struct dr_alias
  91 {
  92   /* The alias information that should be used for new pointers to this
  93      location.  */
  94   struct ptr_info_def *ptr_info;
  95 };
  96
  97 /* An integer vector.  A vector formally consists of an element of a vector
  98    space. A vector space is a set that is closed under vector addition
  99    and scalar multiplication.  In this vector space, an element is a list of
 100    integers.  */
 101 typedef int *lambda_vector;
 102
 103 /* An integer matrix.  A matrix consists of m vectors of length n (IE
 104    all vectors are the same length).  */
 105 typedef lambda_vector *lambda_matrix;
 106
 107
 108
 109 struct data_reference
 110 {
 111   /* A pointer to the statement that contains this DR.  */
 112   gimple stmt;
 113
 114   /* A pointer to the memory reference.  */
 115   tree ref;
 116
 117   /* Auxiliary info specific to a pass.  */
 118   void *aux;
 119
 120   /* True when the data reference is in RHS of a stmt.  */
 121   bool is_read;
 122
 123   /* Behavior of the memory reference in the innermost loop.  */
 124   struct innermost_loop_behavior innermost;
 125
 126   /* Subscripts of this data reference.  */
 127   struct indices indices;
 128
 129   /* Alias information for the data reference.  */
 130   struct dr_alias alias;
 131 };
 132
 133 #define DR_STMT(DR)                (DR)->stmt
 134 #define DR_REF(DR)                 (DR)->ref
 135 #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
 136 #define DR_UNCONSTRAINED_BASE(DR)  (DR)->indices.unconstrained_base
 137 #define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
 138 #define DR_ACCESS_FN(DR, I)        DR_ACCESS_FNS (DR)[I]
 139 #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()
 140 #define DR_IS_READ(DR)             (DR)->is_read
 141 #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
 142 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
 143 #define DR_OFFSET(DR)              (DR)->innermost.offset
 144 #define DR_INIT(DR)                (DR)->innermost.init
 145 #define DR_STEP(DR)                (DR)->innermost.step
 146 #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
 147 #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
 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 bool compute_data_dependences_for_bb (basic_block, bool,
 305                                              vec<data_reference_p> *,
 306                                              vec<ddr_p> *);
 307 extern void debug_ddrs (vec<ddr_p> );
 308 extern void dump_data_reference (FILE *, struct data_reference *);
 309 extern void debug (data_reference &ref);
 310 extern void debug (data_reference *ptr);
 311 extern void debug_data_reference (struct data_reference *);
 312 extern void debug_data_references (vec<data_reference_p> );
 313 extern void debug (vec<data_reference_p> &ref);
 314 extern void debug (vec<data_reference_p> *ptr);
 315 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 316 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
 317 extern void debug (vec<ddr_p> &ref);
 318 extern void debug (vec<ddr_p> *ptr);
 319 extern void debug_data_dependence_relations (vec<ddr_p> );
 320 extern void free_dependence_relation (struct data_dependence_relation *);
 321 extern void free_dependence_relations (vec<ddr_p> );
 322 extern void free_data_ref (data_reference_p);
 323 extern void free_data_refs (vec<data_reference_p> );
 324 extern bool find_data_references_in_stmt (struct loop *, gimple,
 325                                           vec<data_reference_p> *);
 326 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
 327                                                    vec<data_reference_p> *);
 328 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
 329 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
 330 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
 331 extern struct data_dependence_relation *initialize_data_dependence_relation
 332      (struct data_reference *, struct data_reference *, vec<loop_p>);
 333 extern void compute_affine_dependence (struct data_dependence_relation *,
 334                                        loop_p);
 335 extern void compute_self_dependence (struct data_dependence_relation *);
 336 extern bool compute_all_dependences (vec<data_reference_p> ,
 337                                      vec<ddr_p> *,
 338                                      vec<loop_p>, bool);
 339 extern tree find_data_references_in_bb (struct loop *, basic_block,
 340                                         vec<data_reference_p> *);
 341
 342 extern bool dr_may_alias_p (const struct data_reference *,
 343                             const struct data_reference *, bool);
 344 extern bool dr_equal_offsets_p (struct data_reference *,
 345                                 struct data_reference *);
 346 extern void tree_check_data_deps (void);
 347
 348
 349 /* Return true when the base objects of data references A and B are
 350    the same memory object.  */
 351
 352 static inline bool
 353 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
 354 {
 355   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
 356     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
 357 }
 358
 359 /* Return true when the data references A and B are accessing the same
 360    memory object with the same access functions.  */
 361
 362 static inline bool
 363 same_data_refs (data_reference_p a, data_reference_p b)
 364 {
 365   unsigned int i;
 366
 367   /* The references are exactly the same.  */
 368   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
 369     return true;
 370
 371   if (!same_data_refs_base_objects (a, b))
 372     return false;
 373
 374   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
 375     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
 376       return false;
 377
 378   return true;
 379 }
 380
 381 /* Return true when the DDR contains two data references that have the
 382    same access functions.  */
 383
 384 static inline bool
 385 same_access_functions (const struct data_dependence_relation *ddr)
 386 {
 387   unsigned i;
 388
 389   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 390     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
 391                           DR_ACCESS_FN (DDR_B (ddr), i)))
 392       return false;
 393
 394   return true;
 395 }
 396
 397 /* Returns true when all the dependences are computable.  */
 398
 399 inline bool
 400 known_dependences_p (vec<ddr_p> dependence_relations)
 401 {
 402   ddr_p ddr;
 403   unsigned int i;
 404
 405   FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
 406     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 407       return false;
 408
 409   return true;
 410 }
 411
 412 /* Returns the dependence level for a vector DIST of size LENGTH.
 413    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
 414    to the sequence of statements, not carried by any loop.  */
 415
 416 static inline unsigned
 417 dependence_level (lambda_vector dist_vect, int length)
 418 {
 419   int i;
 420
 421   for (i = 0; i < length; i++)
 422     if (dist_vect[i] != 0)
 423       return i + 1;
 424
 425   return 0;
 426 }
 427
 428 /* Return the dependence level for the DDR relation.  */
 429
 430 static inline unsigned
 431 ddr_dependence_level (ddr_p ddr)
 432 {
 433   unsigned vector;
 434   unsigned level = 0;
 435
 436   if (DDR_DIST_VECTS (ddr).exists ())
 437     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
 438
 439   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
 440     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
 441                                           DDR_NB_LOOPS (ddr)));
 442   return level;
 443 }
 444
 445 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 446
 447 static inline int
 448 index_in_loop_nest (int var, vec<loop_p> loop_nest)
 449 {
 450   struct loop *loopi;
 451   int var_index;
 452
 453   for (var_index = 0; loop_nest.iterate (var_index, &loopi);
 454        var_index++)
 455     if (loopi->num == var)
 456       break;
 457
 458   return var_index;
 459 }
 460
 461 /* Returns true when the data reference DR the form "A[i] = ..."
 462    with a stride equal to its unit type size.  */
 463
 464 static inline bool
 465 adjacent_dr_p (struct data_reference *dr)
 466 {
 467   /* If this is a bitfield store bail out.  */
 468   if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
 469       && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
 470     return false;
 471
 472   if (!DR_STEP (dr)
 473       || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
 474     return false;
 475
 476   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
 477                                          DR_STEP (dr)),
 478                              TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
 479 }
 480
 481 void split_constant_offset (tree , tree *, tree *);
 482
 483 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 484
 485 static inline int
 486 lambda_vector_gcd (lambda_vector vector, int size)
 487 {
 488   int i;
 489   int gcd1 = 0;
 490
 491   if (size > 0)
 492     {
 493       gcd1 = vector[0];
 494       for (i = 1; i < size; i++)
 495         gcd1 = gcd (gcd1, vector[i]);
 496     }
 497   return gcd1;
 498 }
 499
 500 /* Allocate a new vector of given SIZE.  */
 501
 502 static inline lambda_vector
 503 lambda_vector_new (int size)
 504 {
 505   /* ???  We shouldn't abuse the GC allocator here.  */
 506   return ggc_cleared_vec_alloc<int> (size);
 507 }
 508
 509 /* Clear out vector VEC1 of length SIZE.  */
 510
 511 static inline void
 512 lambda_vector_clear (lambda_vector vec1, int size)
 513 {
 514   memset (vec1, 0, size * sizeof (*vec1));
 515 }
 516
 517 /* Returns true when the vector V is lexicographically positive, in
 518    other words, when the first nonzero element is positive.  */
 519
 520 static inline bool
 521 lambda_vector_lexico_pos (lambda_vector v,
 522                           unsigned n)
 523 {
 524   unsigned i;
 525   for (i = 0; i < n; i++)
 526     {
 527       if (v[i] == 0)
 528         continue;
 529       if (v[i] < 0)
 530         return false;
 531       if (v[i] > 0)
 532         return true;
 533     }
 534   return true;
 535 }
 536
 537 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 538
 539 static inline bool
 540 lambda_vector_zerop (lambda_vector vec1, int size)
 541 {
 542   int i;
 543   for (i = 0; i < size; i++)
 544     if (vec1[i] != 0)
 545       return false;
 546   return true;
 547 }
 548
 549 /* Allocate a matrix of M rows x  N cols.  */
 550
 551 static inline lambda_matrix
 552 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
 553 {
 554   lambda_matrix mat;
 555   int i;
 556
 557   mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
 558
 559   for (i = 0; i < m; i++)
 560     mat[i] = XOBNEWVEC (lambda_obstack, int, n);
 561
 562   return mat;
 563 }
 564
 565 #endif  /* GCC_TREE_DATA_REF_H  */