1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
/* Data references and dependences detectors.
Copyright (C) 2003, 2004 Free Software Foundation, Inc.
Contributed by Sebastian Pop <s.pop@laposte.net>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
#ifndef GCC_TREE_DATA_REF_H
#define GCC_TREE_DATA_REF_H
#include "lambda.h"
struct data_reference
{
/* A pointer to the statement that contains this DR. */
tree stmt;
/* A pointer to the ARRAY_REF node. */
tree ref;
/* The name of the array. */
tree base_name;
/* A list of chrecs. */
varray_type access_fns;
/* Auxiliary info specific to a pass. */
int aux;
/* True when the data reference is in RHS of a stmt. */
bool is_read;
};
#define DR_STMT(DR) DR->stmt
#define DR_REF(DR) DR->ref
#define DR_BASE_NAME(DR) DR->base_name
#define DR_ACCESS_FNS(DR) DR->access_fns
#define DR_ACCESS_FN(DR, I) VARRAY_TREE (DR_ACCESS_FNS (DR), I)
#define DR_NUM_DIMENSIONS(DR) VARRAY_ACTIVE_SIZE (DR_ACCESS_FNS (DR))
#define DR_IS_READ(DR) DR->is_read
enum data_dependence_direction {
dir_positive,
dir_negative,
dir_equal,
dir_positive_or_negative,
dir_positive_or_equal,
dir_negative_or_equal,
dir_star,
dir_independent
};
/* What is a subscript? Given two array accesses a subscript is the
tuple composed of the access functions for a given dimension.
Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
are stored in the data_dependence_relation structure under the form
of an array of subscripts. */
struct subscript
{
/* A description of the iterations for which the elements are
accessed twice. */
tree conflicting_iterations_in_a;
tree conflicting_iterations_in_b;
/* This field stores the information about the iteration domain
validity of the dependence relation. */
tree last_conflict;
/* Distance from the iteration that access a conflicting element in
A to the iteration that access this same conflicting element in
B. The distance is a tree scalar expression, i.e. a constant or a
symbolic expression, but certainly not a chrec function. */
tree distance;
};
#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
#define SUB_DISTANCE(SUB) SUB->distance
/* A data_dependence_relation represents a relation between two
data_references A and B. */
struct data_dependence_relation
{
struct data_reference *a;
struct data_reference *b;
/* When the dependence relation is affine, it can be represented by
a distance vector. */
bool affine_p;
/* A "yes/no/maybe" field for the dependence relation:
- when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
relation between A and B, and the description of this relation
is given in the SUBSCRIPTS array,
- when "ARE_DEPENDENT == chrec_known", there is no dependence and
SUBSCRIPTS is empty,
- when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
but the analyzer cannot be more specific. */
tree are_dependent;
/* For each subscript in the dependence test, there is an element in
this array. This is the attribute that labels the edge A->B of
the data_dependence_relation. */
varray_type subscripts;
/* The size of the direction/distance vectors. */
int size_vect;
/* The classic direction vector. */
lambda_vector dir_vect;
/* The classic distance vector. */
lambda_vector dist_vect;
};
#define DDR_A(DDR) DDR->a
#define DDR_B(DDR) DDR->b
#define DDR_AFFINE_P(DDR) DDR->affine_p
#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
#define DDR_SUBSCRIPTS(DDR) DDR->subscripts
#define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \
VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
#define DDR_SIZE_VECT(DDR) DDR->size_vect
#define DDR_DIR_VECT(DDR) DDR->dir_vect
#define DDR_DIST_VECT(DDR) DDR->dist_vect
extern tree find_data_references_in_loop (struct loop *, varray_type *);
extern struct data_dependence_relation *initialize_data_dependence_relation
(struct data_reference *, struct data_reference *);
extern void compute_affine_dependence (struct data_dependence_relation *);
extern void analyze_all_data_dependences (struct loops *);
extern void compute_data_dependences_for_loop (unsigned, struct loop *,
varray_type *, varray_type *);
extern struct data_reference * init_data_ref (tree, tree, tree, tree, bool);
extern struct data_reference *analyze_array (tree, tree, bool);
extern void dump_subscript (FILE *, struct subscript *);
extern void dump_ddrs (FILE *, varray_type);
extern void dump_dist_dir_vectors (FILE *, varray_type);
extern void dump_data_reference (FILE *, struct data_reference *);
extern void dump_data_references (FILE *, varray_type);
extern void dump_data_dependence_relation (FILE *,
struct data_dependence_relation *);
extern void dump_data_dependence_relations (FILE *, varray_type);
extern void dump_data_dependence_direction (FILE *,
enum data_dependence_direction);
extern bool array_base_name_differ_p (struct data_reference *,
struct data_reference *, bool *);
extern void free_dependence_relation (struct data_dependence_relation *);
extern void free_dependence_relations (varray_type);
extern void free_data_refs (varray_type);
#endif /* GCC_TREE_DATA_REF_H */
|
