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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 #ifndef GCC_TREE_DATA_REF_H
  23 #define GCC_TREE_DATA_REF_H
  24
  25 #include "graphds.h"
  26 #include "lambda.h"
  27 #include "omega.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   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 and the operands of INDIRECT_REFs.
  63    For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
  64    (note that this reference does not have to be valid, if zero does not
  65    belong to the range of the array; hence it is not recommended to use
  66    BASE_OBJECT in any code generation).  For INDIRECT_REFs, the address is
  67    set to the loop-invariant part of the address of the object, except for
  68    the constant offset.  For the examples above,
  69
  70    base_object:        a[0].b[0][0]                   *(p + x + 4B * j_0)
  71    indices:            {j_0, +, 1}_2                  {16, +, 4}_2
  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,heap) *access_fns;
  83 };
  84
  85 struct dr_alias
  86 {
  87   /* The alias information that should be used for new pointers to this
  88      location.  SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG.  */
  89   tree symbol_tag;
  90   subvar_t subvars;
  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_SUBVARS(DR)             (DR)->alias.subvars
 141 #define DR_VOPS(DR)                (DR)->alias.vops
 142 #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
 143
 144 enum data_dependence_direction {
 145   dir_positive,
 146   dir_negative,
 147   dir_equal,
 148   dir_positive_or_negative,
 149   dir_positive_or_equal,
 150   dir_negative_or_equal,
 151   dir_star,
 152   dir_independent
 153 };
 154
 155 /* The description of the grid of iterations that overlap.  At most
 156    two loops are considered at the same time just now, hence at most
 157    two functions are needed.  For each of the functions, we store
 158    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
 159    where x, y, ... are variables.  */
 160
 161 #define MAX_DIM 2
 162
 163 /* Special values of N.  */
 164 #define NO_DEPENDENCE 0
 165 #define NOT_KNOWN (MAX_DIM + 1)
 166 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
 167 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
 168 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
 169
 170 typedef VEC (tree, heap) *affine_fn;
 171
 172 typedef struct
 173 {
 174   unsigned n;
 175   affine_fn fns[MAX_DIM];
 176 } conflict_function;
 177
 178 /* What is a subscript?  Given two array accesses a subscript is the
 179    tuple composed of the access functions for a given dimension.
 180    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 181    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 182    are stored in the data_dependence_relation structure under the form
 183    of an array of subscripts.  */
 184
 185 struct subscript
 186 {
 187   /* A description of the iterations for which the elements are
 188      accessed twice.  */
 189   conflict_function *conflicting_iterations_in_a;
 190   conflict_function *conflicting_iterations_in_b;
 191
 192   /* This field stores the information about the iteration domain
 193      validity of the dependence relation.  */
 194   tree last_conflict;
 195
 196   /* Distance from the iteration that access a conflicting element in
 197      A to the iteration that access this same conflicting element in
 198      B.  The distance is a tree scalar expression, i.e. a constant or a
 199      symbolic expression, but certainly not a chrec function.  */
 200   tree distance;
 201 };
 202
 203 typedef struct subscript *subscript_p;
 204 DEF_VEC_P(subscript_p);
 205 DEF_VEC_ALLOC_P (subscript_p, heap);
 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   /* When the dependence relation is affine, it can be represented by
 222      a distance vector.  */
 223   bool affine_p;
 224
 225   /* A "yes/no/maybe" field for the dependence relation:
 226
 227      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 228        relation between A and B, and the description of this relation
 229        is given in the SUBSCRIPTS array,
 230
 231      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 232        SUBSCRIPTS is empty,
 233
 234      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 235        but the analyzer cannot be more specific.  */
 236   tree are_dependent;
 237
 238   /* For each subscript in the dependence test, there is an element in
 239      this array.  This is the attribute that labels the edge A->B of
 240      the data_dependence_relation.  */
 241   VEC (subscript_p, heap) *subscripts;
 242
 243   /* The analyzed loop nest.  */
 244   VEC (loop_p, heap) *loop_nest;
 245
 246   /* An index in loop_nest for the innermost loop that varies for
 247      this data dependence relation.  */
 248   unsigned inner_loop;
 249
 250   /* The classic direction vector.  */
 251   VEC (lambda_vector, heap) *dir_vects;
 252
 253   /* The classic distance vector.  */
 254   VEC (lambda_vector, heap) *dist_vects;
 255
 256   /* Is the dependence reversed with respect to the lexicographic order?  */
 257   bool reversed_p;
 258 };
 259
 260 typedef struct data_dependence_relation *ddr_p;
 261 DEF_VEC_P(ddr_p);
 262 DEF_VEC_ALLOC_P(ddr_p,heap);
 263
 264 #define DDR_A(DDR) DDR->a
 265 #define DDR_B(DDR) DDR->b
 266 #define DDR_AFFINE_P(DDR) DDR->affine_p
 267 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 268 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 269 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
 270 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
 271
 272 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 273 /* The size of the direction/distance vectors: the number of loops in
 274    the loop nest.  */
 275 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
 276 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
 277
 278 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 279 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 280 #define DDR_NUM_DIST_VECTS(DDR) \
 281   (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
 282 #define DDR_NUM_DIR_VECTS(DDR) \
 283   (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
 284 #define DDR_DIR_VECT(DDR, I) \
 285   VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
 286 #define DDR_DIST_VECT(DDR, I) \
 287   VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
 288 #define DDR_REVERSED_P(DDR) DDR->reversed_p
 289
 290 \f
 291
 292 /* Describes a location of a memory reference.  */
 293
 294 typedef struct data_ref_loc_d
 295 {
 296   /* Position of the memory reference.  */
 297   tree *pos;
 298
 299   /* True if the memory reference is read.  */
 300   bool is_read;
 301 } data_ref_loc;
 302
 303 DEF_VEC_O (data_ref_loc);
 304 DEF_VEC_ALLOC_O (data_ref_loc, heap);
 305
 306 bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
 307 void dr_analyze_innermost (struct data_reference *);
 308 extern void compute_data_dependences_for_loop (struct loop *, bool,
 309                                                VEC (data_reference_p, heap) **,
 310                                                VEC (ddr_p, heap) **);
 311 extern void print_direction_vector (FILE *, lambda_vector, int);
 312 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 313 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 314 extern void dump_subscript (FILE *, struct subscript *);
 315 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
 316 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
 317 extern void dump_data_reference (FILE *, struct data_reference *);
 318 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
 319 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 320 extern void dump_data_dependence_relation (FILE *,
 321                                            struct data_dependence_relation *);
 322 extern void dump_data_dependence_relations (FILE *, 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_refs (VEC (data_reference_p, heap) *);
 328 struct data_reference *create_data_ref (struct loop *, tree, tree, bool);
 329 bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
 330 void compute_all_dependences (VEC (data_reference_p, heap) *,
 331                               VEC (ddr_p, heap) **, VEC (loop_p, heap) *, bool);
 332
 333 \f
 334
 335 /* A RDG vertex representing a statement.  */
 336 typedef struct rdg_vertex
 337 {
 338   /* The statement represented by this vertex.  */
 339   tree stmt;
 340 } *rdg_vertex_p;
 341
 342 #define RDGV_STMT(V)       ((struct rdg_vertex *) ((V)->data))->stmt
 343
 344 /* Data dependence type.  */
 345
 346 enum rdg_dep_type
 347 {
 348   /* Read After Write (RAW).  */
 349   flow_dd = 'f',
 350
 351   /* Write After Read (WAR).  */
 352   anti_dd = 'a',
 353
 354   /* Write After Write (WAW).  */
 355   output_dd = 'o',
 356
 357   /* Read After Read (RAR).  */
 358   input_dd = 'i'
 359 };
 360
 361 /* Dependence information attached to an edge of the RDG.  */
 362
 363 typedef struct rdg_edge
 364 {
 365   /* Type of the dependence.  */
 366   enum rdg_dep_type type;
 367 } *rdg_edge_p;
 368
 369 #define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
 370
 371 struct graph *build_rdg (struct loop *);
 372
 373 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 374
 375 static inline int
 376 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
 377 {
 378   struct loop *loopi;
 379   int var_index;
 380
 381   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
 382        var_index++)
 383     if (loopi->num == var)
 384       break;
 385
 386   return var_index;
 387 }
 388
 389 /* In lambda-code.c  */
 390 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
 391
 392 #endif  /* GCC_TREE_DATA_REF_H  */