1*38fd1498Szrj /* Data references and dependences detectors.
2*38fd1498Szrj Copyright (C) 2003-2018 Free Software Foundation, Inc.
3*38fd1498Szrj Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4*38fd1498Szrj
5*38fd1498Szrj This file is part of GCC.
6*38fd1498Szrj
7*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
8*38fd1498Szrj the terms of the GNU General Public License as published by the Free
9*38fd1498Szrj Software Foundation; either version 3, or (at your option) any later
10*38fd1498Szrj version.
11*38fd1498Szrj
12*38fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*38fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*38fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*38fd1498Szrj for more details.
16*38fd1498Szrj
17*38fd1498Szrj You should have received a copy of the GNU General Public License
18*38fd1498Szrj along with GCC; see the file COPYING3. If not see
19*38fd1498Szrj <http://www.gnu.org/licenses/>. */
20*38fd1498Szrj
21*38fd1498Szrj #ifndef GCC_TREE_DATA_REF_H
22*38fd1498Szrj #define GCC_TREE_DATA_REF_H
23*38fd1498Szrj
24*38fd1498Szrj #include "graphds.h"
25*38fd1498Szrj #include "tree-chrec.h"
26*38fd1498Szrj
27*38fd1498Szrj /*
28*38fd1498Szrj innermost_loop_behavior describes the evolution of the address of the memory
29*38fd1498Szrj reference in the innermost enclosing loop. The address is expressed as
30*38fd1498Szrj BASE + STEP * # of iteration, and base is further decomposed as the base
31*38fd1498Szrj pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
32*38fd1498Szrj constant offset (INIT). Examples, in loop nest
33*38fd1498Szrj
34*38fd1498Szrj for (i = 0; i < 100; i++)
35*38fd1498Szrj for (j = 3; j < 100; j++)
36*38fd1498Szrj
37*38fd1498Szrj Example 1 Example 2
38*38fd1498Szrj data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
39*38fd1498Szrj
40*38fd1498Szrj
41*38fd1498Szrj innermost_loop_behavior
42*38fd1498Szrj base_address &a p
43*38fd1498Szrj offset i * D_i x
44*38fd1498Szrj init 3 * D_j + offsetof (b) 28
45*38fd1498Szrj step D_j 4
46*38fd1498Szrj
47*38fd1498Szrj */
48*38fd1498Szrj struct innermost_loop_behavior
49*38fd1498Szrj {
50*38fd1498Szrj tree base_address;
51*38fd1498Szrj tree offset;
52*38fd1498Szrj tree init;
53*38fd1498Szrj tree step;
54*38fd1498Szrj
55*38fd1498Szrj /* BASE_ADDRESS is known to be misaligned by BASE_MISALIGNMENT bytes
56*38fd1498Szrj from an alignment boundary of BASE_ALIGNMENT bytes. For example,
57*38fd1498Szrj if we had:
58*38fd1498Szrj
59*38fd1498Szrj struct S __attribute__((aligned(16))) { ... };
60*38fd1498Szrj
61*38fd1498Szrj char *ptr;
62*38fd1498Szrj ... *(struct S *) (ptr - 4) ...;
63*38fd1498Szrj
64*38fd1498Szrj the information would be:
65*38fd1498Szrj
66*38fd1498Szrj base_address: ptr
67*38fd1498Szrj base_aligment: 16
68*38fd1498Szrj base_misalignment: 4
69*38fd1498Szrj init: -4
70*38fd1498Szrj
71*38fd1498Szrj where init cancels the base misalignment. If instead we had a
72*38fd1498Szrj reference to a particular field:
73*38fd1498Szrj
74*38fd1498Szrj struct S __attribute__((aligned(16))) { ... int f; ... };
75*38fd1498Szrj
76*38fd1498Szrj char *ptr;
77*38fd1498Szrj ... ((struct S *) (ptr - 4))->f ...;
78*38fd1498Szrj
79*38fd1498Szrj the information would be:
80*38fd1498Szrj
81*38fd1498Szrj base_address: ptr
82*38fd1498Szrj base_aligment: 16
83*38fd1498Szrj base_misalignment: 4
84*38fd1498Szrj init: -4 + offsetof (S, f)
85*38fd1498Szrj
86*38fd1498Szrj where base_address + init might also be misaligned, and by a different
87*38fd1498Szrj amount from base_address. */
88*38fd1498Szrj unsigned int base_alignment;
89*38fd1498Szrj unsigned int base_misalignment;
90*38fd1498Szrj
91*38fd1498Szrj /* The largest power of two that divides OFFSET, capped to a suitably
92*38fd1498Szrj high value if the offset is zero. This is a byte rather than a bit
93*38fd1498Szrj quantity. */
94*38fd1498Szrj unsigned int offset_alignment;
95*38fd1498Szrj
96*38fd1498Szrj /* Likewise for STEP. */
97*38fd1498Szrj unsigned int step_alignment;
98*38fd1498Szrj };
99*38fd1498Szrj
100*38fd1498Szrj /* Describes the evolutions of indices of the memory reference. The indices
101*38fd1498Szrj are indices of the ARRAY_REFs, indexes in artificial dimensions
102*38fd1498Szrj added for member selection of records and the operands of MEM_REFs.
103*38fd1498Szrj BASE_OBJECT is the part of the reference that is loop-invariant
104*38fd1498Szrj (note that this reference does not have to cover the whole object
105*38fd1498Szrj being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
106*38fd1498Szrj not recommended to use BASE_OBJECT in any code generation).
107*38fd1498Szrj For the examples above,
108*38fd1498Szrj
109*38fd1498Szrj base_object: a *(p + x + 4B * j_0)
110*38fd1498Szrj indices: {j_0, +, 1}_2 {16, +, 4}_2
111*38fd1498Szrj 4
112*38fd1498Szrj {i_0, +, 1}_1
113*38fd1498Szrj {j_0, +, 1}_2
114*38fd1498Szrj */
115*38fd1498Szrj
116*38fd1498Szrj struct indices
117*38fd1498Szrj {
118*38fd1498Szrj /* The object. */
119*38fd1498Szrj tree base_object;
120*38fd1498Szrj
121*38fd1498Szrj /* A list of chrecs. Access functions of the indices. */
122*38fd1498Szrj vec<tree> access_fns;
123*38fd1498Szrj
124*38fd1498Szrj /* Whether BASE_OBJECT is an access representing the whole object
125*38fd1498Szrj or whether the access could not be constrained. */
126*38fd1498Szrj bool unconstrained_base;
127*38fd1498Szrj };
128*38fd1498Szrj
129*38fd1498Szrj struct dr_alias
130*38fd1498Szrj {
131*38fd1498Szrj /* The alias information that should be used for new pointers to this
132*38fd1498Szrj location. */
133*38fd1498Szrj struct ptr_info_def *ptr_info;
134*38fd1498Szrj };
135*38fd1498Szrj
136*38fd1498Szrj /* An integer vector. A vector formally consists of an element of a vector
137*38fd1498Szrj space. A vector space is a set that is closed under vector addition
138*38fd1498Szrj and scalar multiplication. In this vector space, an element is a list of
139*38fd1498Szrj integers. */
140*38fd1498Szrj typedef int *lambda_vector;
141*38fd1498Szrj
142*38fd1498Szrj /* An integer matrix. A matrix consists of m vectors of length n (IE
143*38fd1498Szrj all vectors are the same length). */
144*38fd1498Szrj typedef lambda_vector *lambda_matrix;
145*38fd1498Szrj
146*38fd1498Szrj
147*38fd1498Szrj
148*38fd1498Szrj struct data_reference
149*38fd1498Szrj {
150*38fd1498Szrj /* A pointer to the statement that contains this DR. */
151*38fd1498Szrj gimple *stmt;
152*38fd1498Szrj
153*38fd1498Szrj /* A pointer to the memory reference. */
154*38fd1498Szrj tree ref;
155*38fd1498Szrj
156*38fd1498Szrj /* Auxiliary info specific to a pass. */
157*38fd1498Szrj void *aux;
158*38fd1498Szrj
159*38fd1498Szrj /* True when the data reference is in RHS of a stmt. */
160*38fd1498Szrj bool is_read;
161*38fd1498Szrj
162*38fd1498Szrj /* True when the data reference is conditional within STMT,
163*38fd1498Szrj i.e. if it might not occur even when the statement is executed
164*38fd1498Szrj and runs to completion. */
165*38fd1498Szrj bool is_conditional_in_stmt;
166*38fd1498Szrj
167*38fd1498Szrj /* Behavior of the memory reference in the innermost loop. */
168*38fd1498Szrj struct innermost_loop_behavior innermost;
169*38fd1498Szrj
170*38fd1498Szrj /* Subscripts of this data reference. */
171*38fd1498Szrj struct indices indices;
172*38fd1498Szrj
173*38fd1498Szrj /* Alias information for the data reference. */
174*38fd1498Szrj struct dr_alias alias;
175*38fd1498Szrj };
176*38fd1498Szrj
177*38fd1498Szrj #define DR_STMT(DR) (DR)->stmt
178*38fd1498Szrj #define DR_REF(DR) (DR)->ref
179*38fd1498Szrj #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
180*38fd1498Szrj #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base
181*38fd1498Szrj #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
182*38fd1498Szrj #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I]
183*38fd1498Szrj #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length ()
184*38fd1498Szrj #define DR_IS_READ(DR) (DR)->is_read
185*38fd1498Szrj #define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
186*38fd1498Szrj #define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
187*38fd1498Szrj #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
188*38fd1498Szrj #define DR_OFFSET(DR) (DR)->innermost.offset
189*38fd1498Szrj #define DR_INIT(DR) (DR)->innermost.init
190*38fd1498Szrj #define DR_STEP(DR) (DR)->innermost.step
191*38fd1498Szrj #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
192*38fd1498Szrj #define DR_BASE_ALIGNMENT(DR) (DR)->innermost.base_alignment
193*38fd1498Szrj #define DR_BASE_MISALIGNMENT(DR) (DR)->innermost.base_misalignment
194*38fd1498Szrj #define DR_OFFSET_ALIGNMENT(DR) (DR)->innermost.offset_alignment
195*38fd1498Szrj #define DR_STEP_ALIGNMENT(DR) (DR)->innermost.step_alignment
196*38fd1498Szrj #define DR_INNERMOST(DR) (DR)->innermost
197*38fd1498Szrj
198*38fd1498Szrj typedef struct data_reference *data_reference_p;
199*38fd1498Szrj
200*38fd1498Szrj /* This struct is used to store the information of a data reference,
201*38fd1498Szrj including the data ref itself and the segment length for aliasing
202*38fd1498Szrj checks. This is used to merge alias checks. */
203*38fd1498Szrj
204*38fd1498Szrj struct dr_with_seg_len
205*38fd1498Szrj {
dr_with_seg_lendr_with_seg_len206*38fd1498Szrj dr_with_seg_len (data_reference_p d, tree len, unsigned HOST_WIDE_INT size,
207*38fd1498Szrj unsigned int a)
208*38fd1498Szrj : dr (d), seg_len (len), access_size (size), align (a) {}
209*38fd1498Szrj
210*38fd1498Szrj data_reference_p dr;
211*38fd1498Szrj /* The offset of the last access that needs to be checked minus
212*38fd1498Szrj the offset of the first. */
213*38fd1498Szrj tree seg_len;
214*38fd1498Szrj /* A value that, when added to abs (SEG_LEN), gives the total number of
215*38fd1498Szrj bytes in the segment. */
216*38fd1498Szrj poly_uint64 access_size;
217*38fd1498Szrj /* The minimum common alignment of DR's start address, SEG_LEN and
218*38fd1498Szrj ACCESS_SIZE. */
219*38fd1498Szrj unsigned int align;
220*38fd1498Szrj };
221*38fd1498Szrj
222*38fd1498Szrj /* This struct contains two dr_with_seg_len objects with aliasing data
223*38fd1498Szrj refs. Two comparisons are generated from them. */
224*38fd1498Szrj
225*38fd1498Szrj struct dr_with_seg_len_pair_t
226*38fd1498Szrj {
dr_with_seg_len_pair_tdr_with_seg_len_pair_t227*38fd1498Szrj dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
228*38fd1498Szrj const dr_with_seg_len& d2)
229*38fd1498Szrj : first (d1), second (d2) {}
230*38fd1498Szrj
231*38fd1498Szrj dr_with_seg_len first;
232*38fd1498Szrj dr_with_seg_len second;
233*38fd1498Szrj };
234*38fd1498Szrj
235*38fd1498Szrj enum data_dependence_direction {
236*38fd1498Szrj dir_positive,
237*38fd1498Szrj dir_negative,
238*38fd1498Szrj dir_equal,
239*38fd1498Szrj dir_positive_or_negative,
240*38fd1498Szrj dir_positive_or_equal,
241*38fd1498Szrj dir_negative_or_equal,
242*38fd1498Szrj dir_star,
243*38fd1498Szrj dir_independent
244*38fd1498Szrj };
245*38fd1498Szrj
246*38fd1498Szrj /* The description of the grid of iterations that overlap. At most
247*38fd1498Szrj two loops are considered at the same time just now, hence at most
248*38fd1498Szrj two functions are needed. For each of the functions, we store
249*38fd1498Szrj the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
250*38fd1498Szrj where x, y, ... are variables. */
251*38fd1498Szrj
252*38fd1498Szrj #define MAX_DIM 2
253*38fd1498Szrj
254*38fd1498Szrj /* Special values of N. */
255*38fd1498Szrj #define NO_DEPENDENCE 0
256*38fd1498Szrj #define NOT_KNOWN (MAX_DIM + 1)
257*38fd1498Szrj #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
258*38fd1498Szrj #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
259*38fd1498Szrj #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
260*38fd1498Szrj
261*38fd1498Szrj typedef vec<tree> affine_fn;
262*38fd1498Szrj
263*38fd1498Szrj struct conflict_function
264*38fd1498Szrj {
265*38fd1498Szrj unsigned n;
266*38fd1498Szrj affine_fn fns[MAX_DIM];
267*38fd1498Szrj };
268*38fd1498Szrj
269*38fd1498Szrj /* What is a subscript? Given two array accesses a subscript is the
270*38fd1498Szrj tuple composed of the access functions for a given dimension.
271*38fd1498Szrj Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
272*38fd1498Szrj subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
273*38fd1498Szrj are stored in the data_dependence_relation structure under the form
274*38fd1498Szrj of an array of subscripts. */
275*38fd1498Szrj
276*38fd1498Szrj struct subscript
277*38fd1498Szrj {
278*38fd1498Szrj /* The access functions of the two references. */
279*38fd1498Szrj tree access_fn[2];
280*38fd1498Szrj
281*38fd1498Szrj /* A description of the iterations for which the elements are
282*38fd1498Szrj accessed twice. */
283*38fd1498Szrj conflict_function *conflicting_iterations_in_a;
284*38fd1498Szrj conflict_function *conflicting_iterations_in_b;
285*38fd1498Szrj
286*38fd1498Szrj /* This field stores the information about the iteration domain
287*38fd1498Szrj validity of the dependence relation. */
288*38fd1498Szrj tree last_conflict;
289*38fd1498Szrj
290*38fd1498Szrj /* Distance from the iteration that access a conflicting element in
291*38fd1498Szrj A to the iteration that access this same conflicting element in
292*38fd1498Szrj B. The distance is a tree scalar expression, i.e. a constant or a
293*38fd1498Szrj symbolic expression, but certainly not a chrec function. */
294*38fd1498Szrj tree distance;
295*38fd1498Szrj };
296*38fd1498Szrj
297*38fd1498Szrj typedef struct subscript *subscript_p;
298*38fd1498Szrj
299*38fd1498Szrj #define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
300*38fd1498Szrj #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
301*38fd1498Szrj #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
302*38fd1498Szrj #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
303*38fd1498Szrj #define SUB_DISTANCE(SUB) (SUB)->distance
304*38fd1498Szrj
305*38fd1498Szrj /* A data_dependence_relation represents a relation between two
306*38fd1498Szrj data_references A and B. */
307*38fd1498Szrj
308*38fd1498Szrj struct data_dependence_relation
309*38fd1498Szrj {
310*38fd1498Szrj
311*38fd1498Szrj struct data_reference *a;
312*38fd1498Szrj struct data_reference *b;
313*38fd1498Szrj
314*38fd1498Szrj /* A "yes/no/maybe" field for the dependence relation:
315*38fd1498Szrj
316*38fd1498Szrj - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
317*38fd1498Szrj relation between A and B, and the description of this relation
318*38fd1498Szrj is given in the SUBSCRIPTS array,
319*38fd1498Szrj
320*38fd1498Szrj - when "ARE_DEPENDENT == chrec_known", there is no dependence and
321*38fd1498Szrj SUBSCRIPTS is empty,
322*38fd1498Szrj
323*38fd1498Szrj - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
324*38fd1498Szrj but the analyzer cannot be more specific. */
325*38fd1498Szrj tree are_dependent;
326*38fd1498Szrj
327*38fd1498Szrj /* If nonnull, COULD_BE_INDEPENDENT_P is true and the accesses are
328*38fd1498Szrj independent when the runtime addresses of OBJECT_A and OBJECT_B
329*38fd1498Szrj are different. The addresses of both objects are invariant in the
330*38fd1498Szrj loop nest. */
331*38fd1498Szrj tree object_a;
332*38fd1498Szrj tree object_b;
333*38fd1498Szrj
334*38fd1498Szrj /* For each subscript in the dependence test, there is an element in
335*38fd1498Szrj this array. This is the attribute that labels the edge A->B of
336*38fd1498Szrj the data_dependence_relation. */
337*38fd1498Szrj vec<subscript_p> subscripts;
338*38fd1498Szrj
339*38fd1498Szrj /* The analyzed loop nest. */
340*38fd1498Szrj vec<loop_p> loop_nest;
341*38fd1498Szrj
342*38fd1498Szrj /* The classic direction vector. */
343*38fd1498Szrj vec<lambda_vector> dir_vects;
344*38fd1498Szrj
345*38fd1498Szrj /* The classic distance vector. */
346*38fd1498Szrj vec<lambda_vector> dist_vects;
347*38fd1498Szrj
348*38fd1498Szrj /* An index in loop_nest for the innermost loop that varies for
349*38fd1498Szrj this data dependence relation. */
350*38fd1498Szrj unsigned inner_loop;
351*38fd1498Szrj
352*38fd1498Szrj /* Is the dependence reversed with respect to the lexicographic order? */
353*38fd1498Szrj bool reversed_p;
354*38fd1498Szrj
355*38fd1498Szrj /* When the dependence relation is affine, it can be represented by
356*38fd1498Szrj a distance vector. */
357*38fd1498Szrj bool affine_p;
358*38fd1498Szrj
359*38fd1498Szrj /* Set to true when the dependence relation is on the same data
360*38fd1498Szrj access. */
361*38fd1498Szrj bool self_reference_p;
362*38fd1498Szrj
363*38fd1498Szrj /* True if the dependence described is conservatively correct rather
364*38fd1498Szrj than exact, and if it is still possible for the accesses to be
365*38fd1498Szrj conditionally independent. For example, the a and b references in:
366*38fd1498Szrj
367*38fd1498Szrj struct s *a, *b;
368*38fd1498Szrj for (int i = 0; i < n; ++i)
369*38fd1498Szrj a->f[i] += b->f[i];
370*38fd1498Szrj
371*38fd1498Szrj conservatively have a distance vector of (0), for the case in which
372*38fd1498Szrj a == b, but the accesses are independent if a != b. Similarly,
373*38fd1498Szrj the a and b references in:
374*38fd1498Szrj
375*38fd1498Szrj struct s *a, *b;
376*38fd1498Szrj for (int i = 0; i < n; ++i)
377*38fd1498Szrj a[0].f[i] += b[i].f[i];
378*38fd1498Szrj
379*38fd1498Szrj conservatively have a distance vector of (0), but they are indepenent
380*38fd1498Szrj when a != b + i. In contrast, the references in:
381*38fd1498Szrj
382*38fd1498Szrj struct s *a;
383*38fd1498Szrj for (int i = 0; i < n; ++i)
384*38fd1498Szrj a->f[i] += a->f[i];
385*38fd1498Szrj
386*38fd1498Szrj have the same distance vector of (0), but the accesses can never be
387*38fd1498Szrj independent. */
388*38fd1498Szrj bool could_be_independent_p;
389*38fd1498Szrj };
390*38fd1498Szrj
391*38fd1498Szrj typedef struct data_dependence_relation *ddr_p;
392*38fd1498Szrj
393*38fd1498Szrj #define DDR_A(DDR) (DDR)->a
394*38fd1498Szrj #define DDR_B(DDR) (DDR)->b
395*38fd1498Szrj #define DDR_AFFINE_P(DDR) (DDR)->affine_p
396*38fd1498Szrj #define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
397*38fd1498Szrj #define DDR_OBJECT_A(DDR) (DDR)->object_a
398*38fd1498Szrj #define DDR_OBJECT_B(DDR) (DDR)->object_b
399*38fd1498Szrj #define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
400*38fd1498Szrj #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
401*38fd1498Szrj #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
402*38fd1498Szrj
403*38fd1498Szrj #define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
404*38fd1498Szrj /* The size of the direction/distance vectors: the number of loops in
405*38fd1498Szrj the loop nest. */
406*38fd1498Szrj #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
407*38fd1498Szrj #define DDR_INNER_LOOP(DDR) (DDR)->inner_loop
408*38fd1498Szrj #define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
409*38fd1498Szrj
410*38fd1498Szrj #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
411*38fd1498Szrj #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
412*38fd1498Szrj #define DDR_NUM_DIST_VECTS(DDR) \
413*38fd1498Szrj (DDR_DIST_VECTS (DDR).length ())
414*38fd1498Szrj #define DDR_NUM_DIR_VECTS(DDR) \
415*38fd1498Szrj (DDR_DIR_VECTS (DDR).length ())
416*38fd1498Szrj #define DDR_DIR_VECT(DDR, I) \
417*38fd1498Szrj DDR_DIR_VECTS (DDR)[I]
418*38fd1498Szrj #define DDR_DIST_VECT(DDR, I) \
419*38fd1498Szrj DDR_DIST_VECTS (DDR)[I]
420*38fd1498Szrj #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
421*38fd1498Szrj #define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
422*38fd1498Szrj
423*38fd1498Szrj
424*38fd1498Szrj bool dr_analyze_innermost (innermost_loop_behavior *, tree, struct loop *);
425*38fd1498Szrj extern bool compute_data_dependences_for_loop (struct loop *, bool,
426*38fd1498Szrj vec<loop_p> *,
427*38fd1498Szrj vec<data_reference_p> *,
428*38fd1498Szrj vec<ddr_p> *);
429*38fd1498Szrj extern void debug_ddrs (vec<ddr_p> );
430*38fd1498Szrj extern void dump_data_reference (FILE *, struct data_reference *);
431*38fd1498Szrj extern void debug (data_reference &ref);
432*38fd1498Szrj extern void debug (data_reference *ptr);
433*38fd1498Szrj extern void debug_data_reference (struct data_reference *);
434*38fd1498Szrj extern void debug_data_references (vec<data_reference_p> );
435*38fd1498Szrj extern void debug (vec<data_reference_p> &ref);
436*38fd1498Szrj extern void debug (vec<data_reference_p> *ptr);
437*38fd1498Szrj extern void debug_data_dependence_relation (struct data_dependence_relation *);
438*38fd1498Szrj extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
439*38fd1498Szrj extern void debug (vec<ddr_p> &ref);
440*38fd1498Szrj extern void debug (vec<ddr_p> *ptr);
441*38fd1498Szrj extern void debug_data_dependence_relations (vec<ddr_p> );
442*38fd1498Szrj extern void free_dependence_relation (struct data_dependence_relation *);
443*38fd1498Szrj extern void free_dependence_relations (vec<ddr_p> );
444*38fd1498Szrj extern void free_data_ref (data_reference_p);
445*38fd1498Szrj extern void free_data_refs (vec<data_reference_p> );
446*38fd1498Szrj extern bool find_data_references_in_stmt (struct loop *, gimple *,
447*38fd1498Szrj vec<data_reference_p> *);
448*38fd1498Szrj extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
449*38fd1498Szrj vec<data_reference_p> *);
450*38fd1498Szrj tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
451*38fd1498Szrj bool loop_nest_has_data_refs (loop_p loop);
452*38fd1498Szrj struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
453*38fd1498Szrj bool);
454*38fd1498Szrj extern bool find_loop_nest (struct loop *, vec<loop_p> *);
455*38fd1498Szrj extern struct data_dependence_relation *initialize_data_dependence_relation
456*38fd1498Szrj (struct data_reference *, struct data_reference *, vec<loop_p>);
457*38fd1498Szrj extern void compute_affine_dependence (struct data_dependence_relation *,
458*38fd1498Szrj loop_p);
459*38fd1498Szrj extern void compute_self_dependence (struct data_dependence_relation *);
460*38fd1498Szrj extern bool compute_all_dependences (vec<data_reference_p> ,
461*38fd1498Szrj vec<ddr_p> *,
462*38fd1498Szrj vec<loop_p>, bool);
463*38fd1498Szrj extern tree find_data_references_in_bb (struct loop *, basic_block,
464*38fd1498Szrj vec<data_reference_p> *);
465*38fd1498Szrj extern unsigned int dr_alignment (innermost_loop_behavior *);
466*38fd1498Szrj extern tree get_base_for_alignment (tree, unsigned int *);
467*38fd1498Szrj
468*38fd1498Szrj /* Return the alignment in bytes that DR is guaranteed to have at all
469*38fd1498Szrj times. */
470*38fd1498Szrj
471*38fd1498Szrj inline unsigned int
dr_alignment(data_reference * dr)472*38fd1498Szrj dr_alignment (data_reference *dr)
473*38fd1498Szrj {
474*38fd1498Szrj return dr_alignment (&DR_INNERMOST (dr));
475*38fd1498Szrj }
476*38fd1498Szrj
477*38fd1498Szrj extern bool dr_may_alias_p (const struct data_reference *,
478*38fd1498Szrj const struct data_reference *, bool);
479*38fd1498Szrj extern bool dr_equal_offsets_p (struct data_reference *,
480*38fd1498Szrj struct data_reference *);
481*38fd1498Szrj
482*38fd1498Szrj extern bool runtime_alias_check_p (ddr_p, struct loop *, bool);
483*38fd1498Szrj extern int data_ref_compare_tree (tree, tree);
484*38fd1498Szrj extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
485*38fd1498Szrj poly_uint64);
486*38fd1498Szrj extern void create_runtime_alias_checks (struct loop *,
487*38fd1498Szrj vec<dr_with_seg_len_pair_t> *, tree*);
488*38fd1498Szrj extern tree dr_direction_indicator (struct data_reference *);
489*38fd1498Szrj extern tree dr_zero_step_indicator (struct data_reference *);
490*38fd1498Szrj extern bool dr_known_forward_stride_p (struct data_reference *);
491*38fd1498Szrj
492*38fd1498Szrj /* Return true when the base objects of data references A and B are
493*38fd1498Szrj the same memory object. */
494*38fd1498Szrj
495*38fd1498Szrj static inline bool
same_data_refs_base_objects(data_reference_p a,data_reference_p b)496*38fd1498Szrj same_data_refs_base_objects (data_reference_p a, data_reference_p b)
497*38fd1498Szrj {
498*38fd1498Szrj return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
499*38fd1498Szrj && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
500*38fd1498Szrj }
501*38fd1498Szrj
502*38fd1498Szrj /* Return true when the data references A and B are accessing the same
503*38fd1498Szrj memory object with the same access functions. */
504*38fd1498Szrj
505*38fd1498Szrj static inline bool
same_data_refs(data_reference_p a,data_reference_p b)506*38fd1498Szrj same_data_refs (data_reference_p a, data_reference_p b)
507*38fd1498Szrj {
508*38fd1498Szrj unsigned int i;
509*38fd1498Szrj
510*38fd1498Szrj /* The references are exactly the same. */
511*38fd1498Szrj if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
512*38fd1498Szrj return true;
513*38fd1498Szrj
514*38fd1498Szrj if (!same_data_refs_base_objects (a, b))
515*38fd1498Szrj return false;
516*38fd1498Szrj
517*38fd1498Szrj for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
518*38fd1498Szrj if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
519*38fd1498Szrj return false;
520*38fd1498Szrj
521*38fd1498Szrj return true;
522*38fd1498Szrj }
523*38fd1498Szrj
524*38fd1498Szrj /* Returns true when all the dependences are computable. */
525*38fd1498Szrj
526*38fd1498Szrj inline bool
known_dependences_p(vec<ddr_p> dependence_relations)527*38fd1498Szrj known_dependences_p (vec<ddr_p> dependence_relations)
528*38fd1498Szrj {
529*38fd1498Szrj ddr_p ddr;
530*38fd1498Szrj unsigned int i;
531*38fd1498Szrj
532*38fd1498Szrj FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
533*38fd1498Szrj if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
534*38fd1498Szrj return false;
535*38fd1498Szrj
536*38fd1498Szrj return true;
537*38fd1498Szrj }
538*38fd1498Szrj
539*38fd1498Szrj /* Returns the dependence level for a vector DIST of size LENGTH.
540*38fd1498Szrj LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
541*38fd1498Szrj to the sequence of statements, not carried by any loop. */
542*38fd1498Szrj
543*38fd1498Szrj static inline unsigned
dependence_level(lambda_vector dist_vect,int length)544*38fd1498Szrj dependence_level (lambda_vector dist_vect, int length)
545*38fd1498Szrj {
546*38fd1498Szrj int i;
547*38fd1498Szrj
548*38fd1498Szrj for (i = 0; i < length; i++)
549*38fd1498Szrj if (dist_vect[i] != 0)
550*38fd1498Szrj return i + 1;
551*38fd1498Szrj
552*38fd1498Szrj return 0;
553*38fd1498Szrj }
554*38fd1498Szrj
555*38fd1498Szrj /* Return the dependence level for the DDR relation. */
556*38fd1498Szrj
557*38fd1498Szrj static inline unsigned
ddr_dependence_level(ddr_p ddr)558*38fd1498Szrj ddr_dependence_level (ddr_p ddr)
559*38fd1498Szrj {
560*38fd1498Szrj unsigned vector;
561*38fd1498Szrj unsigned level = 0;
562*38fd1498Szrj
563*38fd1498Szrj if (DDR_DIST_VECTS (ddr).exists ())
564*38fd1498Szrj level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
565*38fd1498Szrj
566*38fd1498Szrj for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
567*38fd1498Szrj level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
568*38fd1498Szrj DDR_NB_LOOPS (ddr)));
569*38fd1498Szrj return level;
570*38fd1498Szrj }
571*38fd1498Szrj
572*38fd1498Szrj /* Return the index of the variable VAR in the LOOP_NEST array. */
573*38fd1498Szrj
574*38fd1498Szrj static inline int
index_in_loop_nest(int var,vec<loop_p> loop_nest)575*38fd1498Szrj index_in_loop_nest (int var, vec<loop_p> loop_nest)
576*38fd1498Szrj {
577*38fd1498Szrj struct loop *loopi;
578*38fd1498Szrj int var_index;
579*38fd1498Szrj
580*38fd1498Szrj for (var_index = 0; loop_nest.iterate (var_index, &loopi);
581*38fd1498Szrj var_index++)
582*38fd1498Szrj if (loopi->num == var)
583*38fd1498Szrj break;
584*38fd1498Szrj
585*38fd1498Szrj return var_index;
586*38fd1498Szrj }
587*38fd1498Szrj
588*38fd1498Szrj /* Returns true when the data reference DR the form "A[i] = ..."
589*38fd1498Szrj with a stride equal to its unit type size. */
590*38fd1498Szrj
591*38fd1498Szrj static inline bool
adjacent_dr_p(struct data_reference * dr)592*38fd1498Szrj adjacent_dr_p (struct data_reference *dr)
593*38fd1498Szrj {
594*38fd1498Szrj /* If this is a bitfield store bail out. */
595*38fd1498Szrj if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
596*38fd1498Szrj && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
597*38fd1498Szrj return false;
598*38fd1498Szrj
599*38fd1498Szrj if (!DR_STEP (dr)
600*38fd1498Szrj || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
601*38fd1498Szrj return false;
602*38fd1498Szrj
603*38fd1498Szrj return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
604*38fd1498Szrj DR_STEP (dr)),
605*38fd1498Szrj TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
606*38fd1498Szrj }
607*38fd1498Szrj
608*38fd1498Szrj void split_constant_offset (tree , tree *, tree *);
609*38fd1498Szrj
610*38fd1498Szrj /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
611*38fd1498Szrj
612*38fd1498Szrj static inline int
lambda_vector_gcd(lambda_vector vector,int size)613*38fd1498Szrj lambda_vector_gcd (lambda_vector vector, int size)
614*38fd1498Szrj {
615*38fd1498Szrj int i;
616*38fd1498Szrj int gcd1 = 0;
617*38fd1498Szrj
618*38fd1498Szrj if (size > 0)
619*38fd1498Szrj {
620*38fd1498Szrj gcd1 = vector[0];
621*38fd1498Szrj for (i = 1; i < size; i++)
622*38fd1498Szrj gcd1 = gcd (gcd1, vector[i]);
623*38fd1498Szrj }
624*38fd1498Szrj return gcd1;
625*38fd1498Szrj }
626*38fd1498Szrj
627*38fd1498Szrj /* Allocate a new vector of given SIZE. */
628*38fd1498Szrj
629*38fd1498Szrj static inline lambda_vector
lambda_vector_new(int size)630*38fd1498Szrj lambda_vector_new (int size)
631*38fd1498Szrj {
632*38fd1498Szrj /* ??? We shouldn't abuse the GC allocator here. */
633*38fd1498Szrj return ggc_cleared_vec_alloc<int> (size);
634*38fd1498Szrj }
635*38fd1498Szrj
636*38fd1498Szrj /* Clear out vector VEC1 of length SIZE. */
637*38fd1498Szrj
638*38fd1498Szrj static inline void
lambda_vector_clear(lambda_vector vec1,int size)639*38fd1498Szrj lambda_vector_clear (lambda_vector vec1, int size)
640*38fd1498Szrj {
641*38fd1498Szrj memset (vec1, 0, size * sizeof (*vec1));
642*38fd1498Szrj }
643*38fd1498Szrj
644*38fd1498Szrj /* Returns true when the vector V is lexicographically positive, in
645*38fd1498Szrj other words, when the first nonzero element is positive. */
646*38fd1498Szrj
647*38fd1498Szrj static inline bool
lambda_vector_lexico_pos(lambda_vector v,unsigned n)648*38fd1498Szrj lambda_vector_lexico_pos (lambda_vector v,
649*38fd1498Szrj unsigned n)
650*38fd1498Szrj {
651*38fd1498Szrj unsigned i;
652*38fd1498Szrj for (i = 0; i < n; i++)
653*38fd1498Szrj {
654*38fd1498Szrj if (v[i] == 0)
655*38fd1498Szrj continue;
656*38fd1498Szrj if (v[i] < 0)
657*38fd1498Szrj return false;
658*38fd1498Szrj if (v[i] > 0)
659*38fd1498Szrj return true;
660*38fd1498Szrj }
661*38fd1498Szrj return true;
662*38fd1498Szrj }
663*38fd1498Szrj
664*38fd1498Szrj /* Return true if vector VEC1 of length SIZE is the zero vector. */
665*38fd1498Szrj
666*38fd1498Szrj static inline bool
lambda_vector_zerop(lambda_vector vec1,int size)667*38fd1498Szrj lambda_vector_zerop (lambda_vector vec1, int size)
668*38fd1498Szrj {
669*38fd1498Szrj int i;
670*38fd1498Szrj for (i = 0; i < size; i++)
671*38fd1498Szrj if (vec1[i] != 0)
672*38fd1498Szrj return false;
673*38fd1498Szrj return true;
674*38fd1498Szrj }
675*38fd1498Szrj
676*38fd1498Szrj /* Allocate a matrix of M rows x N cols. */
677*38fd1498Szrj
678*38fd1498Szrj static inline lambda_matrix
lambda_matrix_new(int m,int n,struct obstack * lambda_obstack)679*38fd1498Szrj lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
680*38fd1498Szrj {
681*38fd1498Szrj lambda_matrix mat;
682*38fd1498Szrj int i;
683*38fd1498Szrj
684*38fd1498Szrj mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
685*38fd1498Szrj
686*38fd1498Szrj for (i = 0; i < m; i++)
687*38fd1498Szrj mat[i] = XOBNEWVEC (lambda_obstack, int, n);
688*38fd1498Szrj
689*38fd1498Szrj return mat;
690*38fd1498Szrj }
691*38fd1498Szrj
692*38fd1498Szrj #endif /* GCC_TREE_DATA_REF_H */
693