OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-data-ref.h] - Blame information for rev 709

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Data references and dependences detectors.
2
   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3
   Free Software Foundation, Inc.
4
   Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
#ifndef GCC_TREE_DATA_REF_H
23
#define GCC_TREE_DATA_REF_H
24
 
25
#include "graphds.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
  struct ptr_info_def *ptr_info;
91
 
92
  /* The set of virtual operands corresponding to this memory reference,
93
     serving as a description of the alias information for the memory
94
     reference.  This could be eliminated if we had alias oracle.  */
95
  bitmap vops;
96
};
97
 
98
/* An integer vector.  A vector formally consists of an element of a vector
99
   space. A vector space is a set that is closed under vector addition
100
   and scalar multiplication.  In this vector space, an element is a list of
101
   integers.  */
102
typedef int *lambda_vector;
103
DEF_VEC_P(lambda_vector);
104
DEF_VEC_ALLOC_P(lambda_vector,heap);
105
DEF_VEC_ALLOC_P(lambda_vector,gc);
106
 
107
/* An integer matrix.  A matrix consists of m vectors of length n (IE
108
   all vectors are the same length).  */
109
typedef lambda_vector *lambda_matrix;
110
 
111
/* Each vector of the access matrix represents a linear access
112
   function for a subscript.  First elements correspond to the
113
   leftmost indices, ie. for a[i][j] the first vector corresponds to
114
   the subscript in "i".  The elements of a vector are relative to
115
   the loop nests in which the data reference is considered,
116
   i.e. the vector is relative to the SCoP that provides the context
117
   in which this data reference occurs.
118
 
119
   For example, in
120
 
121
   | loop_1
122
   |    loop_2
123
   |      a[i+3][2*j+n-1]
124
 
125
   if "i" varies in loop_1 and "j" varies in loop_2, the access
126
   matrix with respect to the loop nest {loop_1, loop_2} is:
127
 
128
   | loop_1  loop_2  param_n  cst
129
   |   1       0        0      3
130
   |   0       2        1     -1
131
 
132
   whereas the access matrix with respect to loop_2 considers "i" as
133
   a parameter:
134
 
135
   | loop_2  param_i  param_n  cst
136
   |   0       1         0      3
137
   |   2       0         1     -1
138
*/
139
struct access_matrix
140
{
141
  VEC (loop_p, heap) *loop_nest;
142
  int nb_induction_vars;
143
  VEC (tree, heap) *parameters;
144
  VEC (lambda_vector, gc) *matrix;
145
};
146
 
147
#define AM_LOOP_NEST(M) (M)->loop_nest
148
#define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars
149
#define AM_PARAMETERS(M) (M)->parameters
150
#define AM_MATRIX(M) (M)->matrix
151
#define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M)))
152
#define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
153
#define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
154
#define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I)
155
#define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
156
 
157
/* Return the column in the access matrix of LOOP_NUM.  */
158
 
159
static inline int
160
am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num)
161
{
162
  int i;
163
  loop_p l;
164
 
165
  for (i = 0; VEC_iterate (loop_p, AM_LOOP_NEST (access_matrix), i, l); i++)
166
    if (l->num == loop_num)
167
      return i;
168
 
169
  gcc_unreachable();
170
}
171
 
172
int access_matrix_get_index_for_parameter (tree, struct access_matrix *);
173
 
174
struct data_reference
175
{
176
  /* A pointer to the statement that contains this DR.  */
177
  gimple stmt;
178
 
179
  /* A pointer to the memory reference.  */
180
  tree ref;
181
 
182
  /* Auxiliary info specific to a pass.  */
183
  void *aux;
184
 
185
  /* True when the data reference is in RHS of a stmt.  */
186
  bool is_read;
187
 
188
  /* Behavior of the memory reference in the innermost loop.  */
189
  struct innermost_loop_behavior innermost;
190
 
191
  /* Subscripts of this data reference.  */
192
  struct indices indices;
193
 
194
  /* Alias information for the data reference.  */
195
  struct dr_alias alias;
196
 
197
  /* Matrix representation for the data access functions.  */
198
  struct access_matrix *access_matrix;
199
};
200
 
201
#define DR_STMT(DR)                (DR)->stmt
202
#define DR_REF(DR)                 (DR)->ref
203
#define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
204
#define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
205
#define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
206
#define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))
207
#define DR_IS_READ(DR)             (DR)->is_read
208
#define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
209
#define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
210
#define DR_OFFSET(DR)              (DR)->innermost.offset
211
#define DR_INIT(DR)                (DR)->innermost.init
212
#define DR_STEP(DR)                (DR)->innermost.step
213
#define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
214
#define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
215
#define DR_ACCESS_MATRIX(DR)       (DR)->access_matrix
216
 
217
typedef struct data_reference *data_reference_p;
218
DEF_VEC_P(data_reference_p);
219
DEF_VEC_ALLOC_P (data_reference_p, heap);
220
 
221
enum data_dependence_direction {
222
  dir_positive,
223
  dir_negative,
224
  dir_equal,
225
  dir_positive_or_negative,
226
  dir_positive_or_equal,
227
  dir_negative_or_equal,
228
  dir_star,
229
  dir_independent
230
};
231
 
232
/* The description of the grid of iterations that overlap.  At most
233
   two loops are considered at the same time just now, hence at most
234
   two functions are needed.  For each of the functions, we store
235
   the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
236
   where x, y, ... are variables.  */
237
 
238
#define MAX_DIM 2
239
 
240
/* Special values of N.  */
241
#define NO_DEPENDENCE 0
242
#define NOT_KNOWN (MAX_DIM + 1)
243
#define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
244
#define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
245
#define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
246
 
247
typedef VEC (tree, heap) *affine_fn;
248
 
249
typedef struct
250
{
251
  unsigned n;
252
  affine_fn fns[MAX_DIM];
253
} conflict_function;
254
 
255
/* What is a subscript?  Given two array accesses a subscript is the
256
   tuple composed of the access functions for a given dimension.
257
   Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
258
   subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
259
   are stored in the data_dependence_relation structure under the form
260
   of an array of subscripts.  */
261
 
262
struct subscript
263
{
264
  /* A description of the iterations for which the elements are
265
     accessed twice.  */
266
  conflict_function *conflicting_iterations_in_a;
267
  conflict_function *conflicting_iterations_in_b;
268
 
269
  /* This field stores the information about the iteration domain
270
     validity of the dependence relation.  */
271
  tree last_conflict;
272
 
273
  /* Distance from the iteration that access a conflicting element in
274
     A to the iteration that access this same conflicting element in
275
     B.  The distance is a tree scalar expression, i.e. a constant or a
276
     symbolic expression, but certainly not a chrec function.  */
277
  tree distance;
278
};
279
 
280
typedef struct subscript *subscript_p;
281
DEF_VEC_P(subscript_p);
282
DEF_VEC_ALLOC_P (subscript_p, heap);
283
 
284
#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
285
#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
286
#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
287
#define SUB_DISTANCE(SUB) SUB->distance
288
 
289
/* A data_dependence_relation represents a relation between two
290
   data_references A and B.  */
291
 
292
struct data_dependence_relation
293
{
294
 
295
  struct data_reference *a;
296
  struct data_reference *b;
297
 
298
  /* A "yes/no/maybe" field for the dependence relation:
299
 
300
     - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
301
       relation between A and B, and the description of this relation
302
       is given in the SUBSCRIPTS array,
303
 
304
     - when "ARE_DEPENDENT == chrec_known", there is no dependence and
305
       SUBSCRIPTS is empty,
306
 
307
     - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
308
       but the analyzer cannot be more specific.  */
309
  tree are_dependent;
310
 
311
  /* For each subscript in the dependence test, there is an element in
312
     this array.  This is the attribute that labels the edge A->B of
313
     the data_dependence_relation.  */
314
  VEC (subscript_p, heap) *subscripts;
315
 
316
  /* The analyzed loop nest.  */
317
  VEC (loop_p, heap) *loop_nest;
318
 
319
  /* The classic direction vector.  */
320
  VEC (lambda_vector, heap) *dir_vects;
321
 
322
  /* The classic distance vector.  */
323
  VEC (lambda_vector, heap) *dist_vects;
324
 
325
  /* An index in loop_nest for the innermost loop that varies for
326
     this data dependence relation.  */
327
  unsigned inner_loop;
328
 
329
  /* Is the dependence reversed with respect to the lexicographic order?  */
330
  bool reversed_p;
331
 
332
  /* When the dependence relation is affine, it can be represented by
333
     a distance vector.  */
334
  bool affine_p;
335
 
336
  /* Set to true when the dependence relation is on the same data
337
     access.  */
338
  bool self_reference_p;
339
};
340
 
341
typedef struct data_dependence_relation *ddr_p;
342
DEF_VEC_P(ddr_p);
343
DEF_VEC_ALLOC_P(ddr_p,heap);
344
 
345
#define DDR_A(DDR) DDR->a
346
#define DDR_B(DDR) DDR->b
347
#define DDR_AFFINE_P(DDR) DDR->affine_p
348
#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
349
#define DDR_SUBSCRIPTS(DDR) DDR->subscripts
350
#define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
351
#define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
352
 
353
#define DDR_LOOP_NEST(DDR) DDR->loop_nest
354
/* The size of the direction/distance vectors: the number of loops in
355
   the loop nest.  */
356
#define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
357
#define DDR_INNER_LOOP(DDR) DDR->inner_loop
358
#define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
359
 
360
#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
361
#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
362
#define DDR_NUM_DIST_VECTS(DDR) \
363
  (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
364
#define DDR_NUM_DIR_VECTS(DDR) \
365
  (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
366
#define DDR_DIR_VECT(DDR, I) \
367
  VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
368
#define DDR_DIST_VECT(DDR, I) \
369
  VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
370
#define DDR_REVERSED_P(DDR) DDR->reversed_p
371
 
372
 
373
 
374
/* Describes a location of a memory reference.  */
375
 
376
typedef struct data_ref_loc_d
377
{
378
  /* Position of the memory reference.  */
379
  tree *pos;
380
 
381
  /* True if the memory reference is read.  */
382
  bool is_read;
383
} data_ref_loc;
384
 
385
DEF_VEC_O (data_ref_loc);
386
DEF_VEC_ALLOC_O (data_ref_loc, heap);
387
 
388
bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **);
389
bool dr_analyze_innermost (struct data_reference *, struct loop *);
390
extern bool compute_data_dependences_for_loop (struct loop *, bool,
391
                                               VEC (loop_p, heap) **,
392
                                               VEC (data_reference_p, heap) **,
393
                                               VEC (ddr_p, heap) **);
394
extern bool compute_data_dependences_for_bb (basic_block, bool,
395
                                             VEC (data_reference_p, heap) **,
396
                                             VEC (ddr_p, heap) **);
397
extern void print_direction_vector (FILE *, lambda_vector, int);
398
extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
399
extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
400
extern void dump_subscript (FILE *, struct subscript *);
401
extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
402
extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
403
extern void dump_data_reference (FILE *, struct data_reference *);
404
extern void debug_data_reference (struct data_reference *);
405
extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
406
extern void debug_data_references (VEC (data_reference_p, heap) *);
407
extern void debug_data_dependence_relation (struct data_dependence_relation *);
408
extern void dump_data_dependence_relation (FILE *,
409
                                           struct data_dependence_relation *);
410
extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
411
extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
412
extern void dump_data_dependence_direction (FILE *,
413
                                            enum data_dependence_direction);
414
extern void free_dependence_relation (struct data_dependence_relation *);
415
extern void free_dependence_relations (VEC (ddr_p, heap) *);
416
extern void free_data_ref (data_reference_p);
417
extern void free_data_refs (VEC (data_reference_p, heap) *);
418
extern bool find_data_references_in_stmt (struct loop *, gimple,
419
                                          VEC (data_reference_p, heap) **);
420
extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
421
                                                   VEC (data_reference_p, heap) **);
422
struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
423
extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
424
extern struct data_dependence_relation *initialize_data_dependence_relation
425
     (struct data_reference *, struct data_reference *, VEC (loop_p, heap) *);
426
extern void compute_self_dependence (struct data_dependence_relation *);
427
extern bool compute_all_dependences (VEC (data_reference_p, heap) *,
428
                                     VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
429
                                     bool);
430
extern tree find_data_references_in_bb (struct loop *, basic_block,
431
                                        VEC (data_reference_p, heap) **);
432
 
433
extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
434
extern bool dr_may_alias_p (const struct data_reference *,
435
                            const struct data_reference *, bool);
436
extern bool dr_equal_offsets_p (struct data_reference *,
437
                                struct data_reference *);
438
 
439
 
440
/* Return true when the base objects of data references A and B are
441
   the same memory object.  */
442
 
443
static inline bool
444
same_data_refs_base_objects (data_reference_p a, data_reference_p b)
445
{
446
  return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
447
    && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
448
}
449
 
450
/* Return true when the data references A and B are accessing the same
451
   memory object with the same access functions.  */
452
 
453
static inline bool
454
same_data_refs (data_reference_p a, data_reference_p b)
455
{
456
  unsigned int i;
457
 
458
  /* The references are exactly the same.  */
459
  if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
460
    return true;
461
 
462
  if (!same_data_refs_base_objects (a, b))
463
    return false;
464
 
465
  for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
466
    if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
467
      return false;
468
 
469
  return true;
470
}
471
 
472
/* Return true when the DDR contains two data references that have the
473
   same access functions.  */
474
 
475
static inline bool
476
same_access_functions (const struct data_dependence_relation *ddr)
477
{
478
  unsigned i;
479
 
480
  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
481
    if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
482
                          DR_ACCESS_FN (DDR_B (ddr), i)))
483
      return false;
484
 
485
  return true;
486
}
487
 
488
/* Return true when DDR is an anti-dependence relation.  */
489
 
490
static inline bool
491
ddr_is_anti_dependent (ddr_p ddr)
492
{
493
  return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
494
          && DR_IS_READ (DDR_A (ddr))
495
          && DR_IS_WRITE (DDR_B (ddr))
496
          && !same_access_functions (ddr));
497
}
498
 
499
/* Return true when DEPENDENCE_RELATIONS contains an anti-dependence.  */
500
 
501
static inline bool
502
ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
503
{
504
  unsigned i;
505
  ddr_p ddr;
506
 
507
  for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
508
    if (ddr_is_anti_dependent (ddr))
509
      return true;
510
 
511
  return false;
512
}
513
 
514
/* Returns the dependence level for a vector DIST of size LENGTH.
515
   LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
516
   to the sequence of statements, not carried by any loop.  */
517
 
518
static inline unsigned
519
dependence_level (lambda_vector dist_vect, int length)
520
{
521
  int i;
522
 
523
  for (i = 0; i < length; i++)
524
    if (dist_vect[i] != 0)
525
      return i + 1;
526
 
527
  return 0;
528
}
529
 
530
/* Return the dependence level for the DDR relation.  */
531
 
532
static inline unsigned
533
ddr_dependence_level (ddr_p ddr)
534
{
535
  unsigned vector;
536
  unsigned level = 0;
537
 
538
  if (DDR_DIST_VECTS (ddr))
539
    level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
540
 
541
  for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
542
    level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
543
                                          DDR_NB_LOOPS (ddr)));
544
  return level;
545
}
546
 
547
 
548
 
549
/* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
550
typedef struct rdg_vertex
551
{
552
  /* The statement represented by this vertex.  */
553
  gimple stmt;
554
 
555
  /* True when the statement contains a write to memory.  */
556
  bool has_mem_write;
557
 
558
  /* True when the statement contains a read from memory.  */
559
  bool has_mem_reads;
560
} *rdg_vertex_p;
561
 
562
#define RDGV_STMT(V)     ((struct rdg_vertex *) ((V)->data))->stmt
563
#define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
564
#define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
565
#define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
566
#define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
567
#define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
568
 
569
void dump_rdg_vertex (FILE *, struct graph *, int);
570
void debug_rdg_vertex (struct graph *, int);
571
void dump_rdg_component (FILE *, struct graph *, int, bitmap);
572
void debug_rdg_component (struct graph *, int);
573
void dump_rdg (FILE *, struct graph *);
574
void debug_rdg (struct graph *);
575
int rdg_vertex_for_stmt (struct graph *, gimple);
576
 
577
/* Data dependence type.  */
578
 
579
enum rdg_dep_type
580
{
581
  /* Read After Write (RAW).  */
582
  flow_dd = 'f',
583
 
584
  /* Write After Read (WAR).  */
585
  anti_dd = 'a',
586
 
587
  /* Write After Write (WAW).  */
588
  output_dd = 'o',
589
 
590
  /* Read After Read (RAR).  */
591
  input_dd = 'i'
592
};
593
 
594
/* Dependence information attached to an edge of the RDG.  */
595
 
596
typedef struct rdg_edge
597
{
598
  /* Type of the dependence.  */
599
  enum rdg_dep_type type;
600
 
601
  /* Levels of the dependence: the depth of the loops that carry the
602
     dependence.  */
603
  unsigned level;
604
 
605
  /* Dependence relation between data dependences, NULL when one of
606
     the vertices is a scalar.  */
607
  ddr_p relation;
608
} *rdg_edge_p;
609
 
610
#define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
611
#define RDGE_LEVEL(E)       ((struct rdg_edge *) ((E)->data))->level
612
#define RDGE_RELATION(E)    ((struct rdg_edge *) ((E)->data))->relation
613
 
614
struct graph *build_rdg (struct loop *,
615
                         VEC (loop_p, heap) **,
616
                         VEC (ddr_p, heap) **,
617
                         VEC (data_reference_p, heap) **);
618
struct graph *build_empty_rdg (int);
619
void free_rdg (struct graph *);
620
 
621
/* Return the index of the variable VAR in the LOOP_NEST array.  */
622
 
623
static inline int
624
index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
625
{
626
  struct loop *loopi;
627
  int var_index;
628
 
629
  for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
630
       var_index++)
631
    if (loopi->num == var)
632
      break;
633
 
634
  return var_index;
635
}
636
 
637
void stores_from_loop (struct loop *, VEC (gimple, heap) **);
638
void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **);
639
void remove_similar_memory_refs (VEC (gimple, heap) **);
640
bool rdg_defs_used_in_other_loops_p (struct graph *, int);
641
bool have_similar_memory_accesses (gimple, gimple);
642
bool stmt_with_adjacent_zero_store_dr_p (gimple);
643
 
644
/* Returns true when STRIDE is equal in absolute value to the size of
645
   the unit type of TYPE.  */
646
 
647
static inline bool
648
stride_of_unit_type_p (tree stride, tree type)
649
{
650
  return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride),
651
                                         stride),
652
                             TYPE_SIZE_UNIT (type));
653
}
654
 
655
/* Determines whether RDG vertices V1 and V2 access to similar memory
656
   locations, in which case they have to be in the same partition.  */
657
 
658
static inline bool
659
rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
660
{
661
  return have_similar_memory_accesses (RDG_STMT (rdg, v1),
662
                                       RDG_STMT (rdg, v2));
663
}
664
 
665
/* In tree-data-ref.c  */
666
void split_constant_offset (tree , tree *, tree *);
667
 
668
/* Strongly connected components of the reduced data dependence graph.  */
669
 
670
typedef struct rdg_component
671
{
672
  int num;
673
  VEC (int, heap) *vertices;
674
} *rdgc;
675
 
676
DEF_VEC_P (rdgc);
677
DEF_VEC_ALLOC_P (rdgc, heap);
678
 
679
DEF_VEC_P (bitmap);
680
DEF_VEC_ALLOC_P (bitmap, heap);
681
 
682
/* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
683
 
684
static inline int
685
lambda_vector_gcd (lambda_vector vector, int size)
686
{
687
  int i;
688
  int gcd1 = 0;
689
 
690
  if (size > 0)
691
    {
692
      gcd1 = vector[0];
693
      for (i = 1; i < size; i++)
694
        gcd1 = gcd (gcd1, vector[i]);
695
    }
696
  return gcd1;
697
}
698
 
699
/* Allocate a new vector of given SIZE.  */
700
 
701
static inline lambda_vector
702
lambda_vector_new (int size)
703
{
704
  return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size);
705
}
706
 
707
/* Clear out vector VEC1 of length SIZE.  */
708
 
709
static inline void
710
lambda_vector_clear (lambda_vector vec1, int size)
711
{
712
  memset (vec1, 0, size * sizeof (*vec1));
713
}
714
 
715
/* Returns true when the vector V is lexicographically positive, in
716
   other words, when the first nonzero element is positive.  */
717
 
718
static inline bool
719
lambda_vector_lexico_pos (lambda_vector v,
720
                          unsigned n)
721
{
722
  unsigned i;
723
  for (i = 0; i < n; i++)
724
    {
725
      if (v[i] == 0)
726
        continue;
727
      if (v[i] < 0)
728
        return false;
729
      if (v[i] > 0)
730
        return true;
731
    }
732
  return true;
733
}
734
 
735
/* Return true if vector VEC1 of length SIZE is the zero vector.  */
736
 
737
static inline bool
738
lambda_vector_zerop (lambda_vector vec1, int size)
739
{
740
  int i;
741
  for (i = 0; i < size; i++)
742
    if (vec1[i] != 0)
743
      return false;
744
  return true;
745
}
746
 
747
/* Allocate a matrix of M rows x  N cols.  */
748
 
749
static inline lambda_matrix
750
lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
751
{
752
  lambda_matrix mat;
753
  int i;
754
 
755
  mat = (lambda_matrix) obstack_alloc (lambda_obstack,
756
                                       sizeof (lambda_vector *) * m);
757
 
758
  for (i = 0; i < m; i++)
759
    mat[i] = lambda_vector_new (n);
760
 
761
  return mat;
762
}
763
 
764
#endif  /* GCC_TREE_DATA_REF_H  */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.