gcc/tree-data-ref.h

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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 "lambda.h"
  26 #include "omega.h"
  27 #include "tree-chrec.h"
  28
  29 /*
  30   innermost_loop_behavior describes the evolution of the address of the memory
  31   reference in the innermost enclosing loop.  The address is expressed as
  32   BASE + STEP * # of iteration, and base is further decomposed as the base
  33   pointer (BASE_ADDRESS),  loop invariant offset (OFFSET) and
  34   constant offset (INIT).  Examples, in loop nest
  35
  36   for (i = 0; i < 100; i++)
  37     for (j = 3; j < 100; j++)
  38
  39                        Example 1                      Example 2
  40       data-ref         a[j].b[i][j]                   *(p + x + 16B + 4B * j)
  41
  42
  43   innermost_loop_behavior
  44       base_address     &a                             p
  45       offset           i * D_i                        x
  46       init             3 * D_j + offsetof (b)         28
  47       step             D_j                            4
  48
  49   */
  50 struct innermost_loop_behavior
  51 {
  52   tree base_address;
  53   tree offset;
  54   tree init;
  55   tree step;
  56
  57   /* Alignment information.  ALIGNED_TO is set to the largest power of two
  58      that divides OFFSET.  */
  59   tree aligned_to;
  60 };
  61
  62 /* Describes the evolutions of indices of the memory reference.  The indices
  63    are indices of the ARRAY_REFs and the operands of INDIRECT_REFs.
  64    For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
  65    (note that this reference does not have to be valid, if zero does not
  66    belong to the range of the array; hence it is not recommended to use
  67    BASE_OBJECT in any code generation).  For INDIRECT_REFs, the address is
  68    set to the loop-invariant part of the address of the object, except for
  69    the constant offset.  For the examples above,
  70
  71    base_object:        a[0].b[0][0]                   *(p + x + 4B * j_0)
  72    indices:            {j_0, +, 1}_2                  {16, +, 4}_2
  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,heap) *access_fns;
  84 };
  85
  86 struct dr_alias
  87 {
  88   /* The alias information that should be used for new pointers to this
  89      location.  SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG.  */
  90   tree symbol_tag;
  91   subvar_t subvars;
  92   struct ptr_info_def *ptr_info;
  93
  94   /* The set of virtual operands corresponding to this memory reference,
  95      serving as a description of the alias information for the memory
  96      reference.  This could be eliminated if we had alias oracle.  */
  97   bitmap vops;
  98 };
  99
 100 struct data_reference
 101 {
 102   /* A pointer to the statement that contains this DR.  */
 103   tree stmt;
 104
 105   /* A pointer to the memory reference.  */
 106   tree ref;
 107
 108   /* Auxiliary info specific to a pass.  */
 109   void *aux;
 110
 111   /* True when the data reference is in RHS of a stmt.  */
 112   bool is_read;
 113
 114   /* Behavior of the memory reference in the innermost loop.  */
 115   struct innermost_loop_behavior innermost;
 116
 117   /* Decomposition to indices for alias analysis.  */
 118   struct indices indices;
 119
 120   /* Alias information for the data reference.  */
 121   struct dr_alias alias;
 122 };
 123
 124 typedef struct data_reference *data_reference_p;
 125 DEF_VEC_P(data_reference_p);
 126 DEF_VEC_ALLOC_P (data_reference_p, heap);
 127
 128 #define DR_STMT(DR)                (DR)->stmt
 129 #define DR_REF(DR)                 (DR)->ref
 130 #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
 131 #define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
 132 #define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
 133 #define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))
 134 #define DR_IS_READ(DR)             (DR)->is_read
 135 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
 136 #define DR_OFFSET(DR)              (DR)->innermost.offset
 137 #define DR_INIT(DR)                (DR)->innermost.init
 138 #define DR_STEP(DR)                (DR)->innermost.step
 139 #define DR_SYMBOL_TAG(DR)          (DR)->alias.symbol_tag
 140 #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
 141 #define DR_SUBVARS(DR)             (DR)->alias.subvars
 142 #define DR_VOPS(DR)                (DR)->alias.vops
 143 #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
 144
 145 enum data_dependence_direction {
 146   dir_positive,
 147   dir_negative,
 148   dir_equal,
 149   dir_positive_or_negative,
 150   dir_positive_or_equal,
 151   dir_negative_or_equal,
 152   dir_star,
 153   dir_independent
 154 };
 155
 156 /* The description of the grid of iterations that overlap.  At most
 157    two loops are considered at the same time just now, hence at most
 158    two functions are needed.  For each of the functions, we store
 159    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
 160    where x, y, ... are variables.  */
 161
 162 #define MAX_DIM 2
 163
 164 /* Special values of N.  */
 165 #define NO_DEPENDENCE 0
 166 #define NOT_KNOWN (MAX_DIM + 1)
 167 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
 168 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
 169 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
 170
 171 typedef VEC (tree, heap) *affine_fn;
 172
 173 typedef struct
 174 {
 175   unsigned n;
 176   affine_fn fns[MAX_DIM];
 177 } conflict_function;
 178
 179 /* What is a subscript?  Given two array accesses a subscript is the
 180    tuple composed of the access functions for a given dimension.
 181    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 182    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 183    are stored in the data_dependence_relation structure under the form
 184    of an array of subscripts.  */
 185
 186 struct subscript
 187 {
 188   /* A description of the iterations for which the elements are
 189      accessed twice.  */
 190   conflict_function *conflicting_iterations_in_a;
 191   conflict_function *conflicting_iterations_in_b;
 192
 193   /* This field stores the information about the iteration domain
 194      validity of the dependence relation.  */
 195   tree last_conflict;
 196
 197   /* Distance from the iteration that access a conflicting element in
 198      A to the iteration that access this same conflicting element in
 199      B.  The distance is a tree scalar expression, i.e. a constant or a
 200      symbolic expression, but certainly not a chrec function.  */
 201   tree distance;
 202 };
 203
 204 typedef struct subscript *subscript_p;
 205 DEF_VEC_P(subscript_p);
 206 DEF_VEC_ALLOC_P (subscript_p, heap);
 207
 208 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 209 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 210 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
 211 #define SUB_DISTANCE(SUB) SUB->distance
 212
 213 /* A data_dependence_relation represents a relation between two
 214    data_references A and B.  */
 215
 216 struct data_dependence_relation
 217 {
 218
 219   struct data_reference *a;
 220   struct data_reference *b;
 221
 222   /* When the dependence relation is affine, it can be represented by
 223      a distance vector.  */
 224   bool affine_p;
 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, heap) *subscripts;
 243
 244   /* The analyzed loop nest.  */
 245   VEC (loop_p, heap) *loop_nest;
 246
 247   /* An index in loop_nest for the innermost loop that varies for
 248      this data dependence relation.  */
 249   unsigned inner_loop;
 250
 251   /* The classic direction vector.  */
 252   VEC (lambda_vector, heap) *dir_vects;
 253
 254   /* The classic distance vector.  */
 255   VEC (lambda_vector, heap) *dist_vects;
 256
 257   /* Is the dependence reversed with respect to the lexicographic order?  */
 258   bool reversed_p;
 259 };
 260
 261 typedef struct data_dependence_relation *ddr_p;
 262 DEF_VEC_P(ddr_p);
 263 DEF_VEC_ALLOC_P(ddr_p,heap);
 264
 265 #define DDR_A(DDR) DDR->a
 266 #define DDR_B(DDR) DDR->b
 267 #define DDR_AFFINE_P(DDR) DDR->affine_p
 268 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 269 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 270 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
 271 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
 272
 273 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 274 /* The size of the direction/distance vectors: the number of loops in
 275    the loop nest.  */
 276 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
 277 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
 278
 279 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 280 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 281 #define DDR_NUM_DIST_VECTS(DDR) \
 282   (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
 283 #define DDR_NUM_DIR_VECTS(DDR) \
 284   (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
 285 #define DDR_DIR_VECT(DDR, I) \
 286   VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
 287 #define DDR_DIST_VECT(DDR, I) \
 288   VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
 289 #define DDR_REVERSED_P(DDR) DDR->reversed_p
 290
 291 \f
 292
 293 /* Describes a location of a memory reference.  */
 294
 295 typedef struct data_ref_loc_d
 296 {
 297   /* Position of the memory reference.  */
 298   tree *pos;
 299
 300   /* True if the memory reference is read.  */
 301   bool is_read;
 302 } data_ref_loc;
 303
 304 DEF_VEC_O (data_ref_loc);
 305 DEF_VEC_ALLOC_O (data_ref_loc, heap);
 306
 307 bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
 308 void dr_analyze_innermost (struct data_reference *);
 309 extern void compute_data_dependences_for_loop (struct loop *, bool,
 310                                                VEC (data_reference_p, heap) **,
 311                                                VEC (ddr_p, heap) **);
 312 extern void print_direction_vector (FILE *, lambda_vector, int);
 313 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 314 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 315 extern void dump_subscript (FILE *, struct subscript *);
 316 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
 317 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
 318 extern void dump_data_reference (FILE *, struct data_reference *);
 319 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
 320 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 321 extern void dump_data_dependence_relation (FILE *,
 322                                            struct data_dependence_relation *);
 323 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
 324 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
 325 extern void dump_data_dependence_direction (FILE *,
 326                                             enum data_dependence_direction);
 327 extern void free_dependence_relation (struct data_dependence_relation *);
 328 extern void free_dependence_relations (VEC (ddr_p, heap) *);
 329 extern void free_data_ref (data_reference_p);
 330 extern void free_data_refs (VEC (data_reference_p, heap) *);
 331 struct data_reference *create_data_ref (struct loop *, tree, tree, bool);
 332 bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
 333 void compute_all_dependences (VEC (data_reference_p, heap) *,
 334                               VEC (ddr_p, heap) **, VEC (loop_p, heap) *, bool);
 335
 336 /* Return true when the DDR contains two data references that have the
 337    same access functions.  */
 338
 339 static inline bool
 340 same_access_functions (const struct data_dependence_relation *ddr)
 341 {
 342   unsigned i;
 343
 344   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 345     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
 346                           DR_ACCESS_FN (DDR_B (ddr), i)))
 347       return false;
 348
 349   return true;
 350 }
 351
 352 /* Return true when DDR is an anti-dependence relation.  */
 353
 354 static inline bool
 355 ddr_is_anti_dependent (ddr_p ddr)
 356 {
 357   return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
 358           && DR_IS_READ (DDR_A (ddr))
 359           && !DR_IS_READ (DDR_B (ddr))
 360           && !same_access_functions (ddr));
 361 }
 362
 363 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence.  */
 364
 365 static inline bool
 366 ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
 367 {
 368   unsigned i;
 369   ddr_p ddr;
 370
 371   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
 372     if (ddr_is_anti_dependent (ddr))
 373       return true;
 374
 375   return false;
 376 }
 377
 378 /* Return the dependence level for the DDR relation.  */
 379
 380 static inline unsigned
 381 ddr_dependence_level (ddr_p ddr)
 382 {
 383   unsigned vector;
 384   unsigned level = 0;
 385
 386   if (DDR_DIST_VECTS (ddr))
 387     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
 388
 389   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
 390     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
 391                                           DDR_NB_LOOPS (ddr)));
 392   return level;
 393 }
 394
 395 \f
 396
 397 /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
 398 typedef struct rdg_vertex
 399 {
 400   /* The statement represented by this vertex.  */
 401   tree stmt;
 402
 403   /* True when the statement contains a write to memory.  */
 404   bool has_mem_write;
 405
 406   /* True when the statement contains a read from memory.  */
 407   bool has_mem_reads;
 408 } *rdg_vertex_p;
 409
 410 #define RDGV_STMT(V)     ((struct rdg_vertex *) ((V)->data))->stmt
 411 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
 412 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
 413 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
 414 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
 415 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
 416
 417 void dump_rdg_vertex (FILE *, struct graph *, int);
 418 void debug_rdg_vertex (struct graph *, int);
 419 void dump_rdg_component (FILE *, struct graph *, int, bitmap);
 420 void debug_rdg_component (struct graph *, int);
 421 void dump_rdg (FILE *, struct graph *);
 422 void debug_rdg (struct graph *);
 423 void dot_rdg (struct graph *);
 424 int rdg_vertex_for_stmt (struct graph *, tree);
 425
 426 /* Data dependence type.  */
 427
 428 enum rdg_dep_type
 429 {
 430   /* Read After Write (RAW).  */
 431   flow_dd = 'f',
 432
 433   /* Write After Read (WAR).  */
 434   anti_dd = 'a',
 435
 436   /* Write After Write (WAW).  */
 437   output_dd = 'o',
 438
 439   /* Read After Read (RAR).  */
 440   input_dd = 'i'
 441 };
 442
 443 /* Dependence information attached to an edge of the RDG.  */
 444
 445 typedef struct rdg_edge
 446 {
 447   /* Type of the dependence.  */
 448   enum rdg_dep_type type;
 449
 450   /* Levels of the dependence: the depth of the loops that
 451     carry the dependence.  */
 452   unsigned level;
 453 } *rdg_edge_p;
 454
 455 #define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
 456 #define RDGE_LEVEL(E)       ((struct rdg_edge *) ((E)->data))->level
 457
 458 struct graph *build_rdg (struct loop *);
 459 void free_rdg (struct graph *);
 460
 461 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 462
 463 static inline int
 464 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
 465 {
 466   struct loop *loopi;
 467   int var_index;
 468
 469   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
 470        var_index++)
 471     if (loopi->num == var)
 472       break;
 473
 474   return var_index;
 475 }
 476
 477 void stores_from_loop (struct loop *, VEC (tree, heap) **);
 478 void remove_similar_memory_refs (VEC (tree, heap) **);
 479 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
 480 bool have_similar_memory_accesses (tree, tree);
 481
 482 /* Determines whether RDG vertices V1 and V2 access to similar memory
 483    locations, in which case they have to be in the same partition.  */
 484
 485 static inline bool
 486 rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
 487 {
 488   return have_similar_memory_accesses (RDG_STMT (rdg, v1),
 489                                        RDG_STMT (rdg, v2));
 490 }
 491
 492 /* In lambda-code.c  */
 493 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
 494
 495 /* In tree-data-refs.c  */
 496 void split_constant_offset (tree , tree *, tree *);
 497
 498 #endif  /* GCC_TREE_DATA_REF_H  */