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