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