Line data Source code
1 : /* Data references and dependences detectors.
2 : Copyright (C) 2003-2026 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 "tree-chrec.h"
26 : #include "opt-problem.h"
27 :
28 : /*
29 : innermost_loop_behavior describes the evolution of the address of the memory
30 : reference in the innermost enclosing loop. The address is expressed as
31 : BASE + STEP * # of iteration, and base is further decomposed as the base
32 : pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
33 : constant offset (INIT). Examples, in loop nest
34 :
35 : for (i = 0; i < 100; i++)
36 : for (j = 3; j < 100; j++)
37 :
38 : Example 1 Example 2
39 : data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
40 :
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 : /* BASE_ADDRESS is known to be misaligned by BASE_MISALIGNMENT bytes
57 : from an alignment boundary of BASE_ALIGNMENT bytes. For example,
58 : if we had:
59 :
60 : struct S __attribute__((aligned(16))) { ... };
61 :
62 : char *ptr;
63 : ... *(struct S *) (ptr - 4) ...;
64 :
65 : the information would be:
66 :
67 : base_address: ptr
68 : base_aligment: 16
69 : base_misalignment: 4
70 : init: -4
71 :
72 : where init cancels the base misalignment. If instead we had a
73 : reference to a particular field:
74 :
75 : struct S __attribute__((aligned(16))) { ... int f; ... };
76 :
77 : char *ptr;
78 : ... ((struct S *) (ptr - 4))->f ...;
79 :
80 : the information would be:
81 :
82 : base_address: ptr
83 : base_aligment: 16
84 : base_misalignment: 4
85 : init: -4 + offsetof (S, f)
86 :
87 : where base_address + init might also be misaligned, and by a different
88 : amount from base_address. */
89 : unsigned int base_alignment;
90 : unsigned int base_misalignment;
91 :
92 : /* The largest power of two that divides OFFSET, capped to a suitably
93 : high value if the offset is zero. This is a byte rather than a bit
94 : quantity. */
95 : unsigned int offset_alignment;
96 :
97 : /* Likewise for STEP. */
98 : unsigned int step_alignment;
99 : };
100 :
101 : /* Describes the evolutions of indices of the memory reference. The indices
102 : are indices of the ARRAY_REFs, indexes in artificial dimensions
103 : added for member selection of records and the operands of MEM_REFs.
104 : BASE_OBJECT is the part of the reference that is loop-invariant
105 : (note that this reference does not have to cover the whole object
106 : being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
107 : not recommended to use BASE_OBJECT in any code generation).
108 : For the examples above,
109 :
110 : base_object: a *(p + x + 4B * j_0)
111 : indices: {j_0, +, 1}_2 {16, +, 4}_2
112 : 4
113 : {i_0, +, 1}_1
114 : {j_0, +, 1}_2
115 : */
116 :
117 : struct indices
118 : {
119 : /* The object. */
120 : tree base_object;
121 :
122 : /* A list of chrecs. Access functions of the indices. */
123 : vec<tree> access_fns;
124 :
125 : /* Whether BASE_OBJECT is an access representing the whole object
126 : or whether the access could not be constrained. */
127 : bool unconstrained_base;
128 : };
129 :
130 : struct dr_alias
131 : {
132 : /* The base pointer whose points-to information should be used for new
133 : pointers to this location or NULL. */
134 : const pt_solution *ptr_info;
135 : };
136 :
137 : /* An integer vector. A vector formally consists of an element of a vector
138 : space. A vector space is a set that is closed under vector addition
139 : and scalar multiplication. In this vector space, an element is a list of
140 : integers. */
141 : typedef HOST_WIDE_INT lambda_int;
142 : typedef lambda_int *lambda_vector;
143 :
144 : /* An integer matrix. A matrix consists of m vectors of length n (IE
145 : all vectors are the same length). */
146 : typedef lambda_vector *lambda_matrix;
147 :
148 :
149 :
150 : struct data_reference
151 : {
152 : /* A pointer to the statement that contains this DR. */
153 : gimple *stmt;
154 :
155 : /* A pointer to the memory reference. */
156 : tree ref;
157 :
158 : /* Auxiliary info specific to a pass. */
159 : void *aux;
160 :
161 : /* True when the data reference is in RHS of a stmt. */
162 : bool is_read;
163 :
164 : /* True when the data reference is conditional within STMT,
165 : i.e. if it might not occur even when the statement is executed
166 : and runs to completion. */
167 : bool is_conditional_in_stmt;
168 :
169 : /* Alias information for the data reference. */
170 : struct dr_alias alias;
171 :
172 : /* Behavior of the memory reference in the innermost loop. */
173 : struct innermost_loop_behavior innermost;
174 :
175 : /* Upper bound for the number of loop iterations for which this DR's
176 : IV does not wrap. */
177 : tree nowrap_bound;
178 :
179 : /* Subscripts of this data reference. */
180 : struct indices indices;
181 :
182 : /* Alternate subscripts initialized lazily and used by data-dependence
183 : analysis only when the main indices of two DRs are not comparable.
184 : Keep last to keep vec_info_shared::check_datarefs happy. */
185 : struct indices alt_indices;
186 : };
187 :
188 : #define DR_STMT(DR) (DR)->stmt
189 : #define DR_REF(DR) (DR)->ref
190 : #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
191 : #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base
192 : #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
193 : #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I]
194 : #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length ()
195 : #define DR_IS_READ(DR) (DR)->is_read
196 : #define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
197 : #define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
198 : #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
199 : #define DR_OFFSET(DR) (DR)->innermost.offset
200 : #define DR_INIT(DR) (DR)->innermost.init
201 : #define DR_STEP(DR) (DR)->innermost.step
202 : #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
203 : #define DR_BASE_ALIGNMENT(DR) (DR)->innermost.base_alignment
204 : #define DR_BASE_MISALIGNMENT(DR) (DR)->innermost.base_misalignment
205 : #define DR_OFFSET_ALIGNMENT(DR) (DR)->innermost.offset_alignment
206 : #define DR_STEP_ALIGNMENT(DR) (DR)->innermost.step_alignment
207 : #define DR_INNERMOST(DR) (DR)->innermost
208 : #define DR_NOWRAP_BOUND(DR) (DR)->nowrap_bound
209 :
210 : typedef struct data_reference *data_reference_p;
211 :
212 : /* This struct is used to store the information of a data reference,
213 : including the data ref itself and the segment length for aliasing
214 : checks. This is used to merge alias checks. */
215 :
216 : class dr_with_seg_len
217 : {
218 : public:
219 72918 : dr_with_seg_len (data_reference_p d, tree len, unsigned HOST_WIDE_INT size,
220 : unsigned int a)
221 72918 : : dr (d), seg_len (len), access_size (size), align (a) {}
222 :
223 : data_reference_p dr;
224 : /* The offset of the last access that needs to be checked minus
225 : the offset of the first. */
226 : tree seg_len;
227 : /* A value that, when added to abs (SEG_LEN), gives the total number of
228 : bytes in the segment. */
229 : poly_uint64 access_size;
230 : /* The minimum common alignment of DR's start address, SEG_LEN and
231 : ACCESS_SIZE. */
232 : unsigned int align;
233 : };
234 :
235 : /* Flags that describe a potential alias between two dr_with_seg_lens.
236 : In general, each pair of dr_with_seg_lens represents a composite of
237 : multiple access pairs P, so testing flags like DR_IS_READ on the DRs
238 : does not give meaningful information.
239 :
240 : DR_ALIAS_RAW:
241 : There is a pair in P for which the second reference is a read
242 : and the first is a write.
243 :
244 : DR_ALIAS_WAR:
245 : There is a pair in P for which the second reference is a write
246 : and the first is a read.
247 :
248 : DR_ALIAS_WAW:
249 : There is a pair in P for which both references are writes.
250 :
251 : DR_ALIAS_ARBITRARY:
252 : Either
253 : (a) it isn't possible to classify one pair in P as RAW, WAW or WAR; or
254 : (b) there is a pair in P that breaks the ordering assumption below.
255 :
256 : This flag overrides the RAW, WAR and WAW flags above.
257 :
258 : DR_ALIAS_UNSWAPPED:
259 : DR_ALIAS_SWAPPED:
260 : Temporary flags that indicate whether there is a pair P whose
261 : DRs have or haven't been swapped around.
262 :
263 : DR_ALIAS_MIXED_STEPS:
264 : The DR_STEP for one of the data references in the pair does not
265 : accurately describe that reference for all members of P. (Note
266 : that the flag does not say anything about whether the DR_STEPs
267 : of the two references in the pair are the same.)
268 :
269 : The ordering assumption mentioned above is that for every pair
270 : (DR_A, DR_B) in P:
271 :
272 : (1) The original code accesses n elements for DR_A and n elements for DR_B,
273 : interleaved as follows:
274 :
275 : one access of size DR_A.access_size at DR_A.dr
276 : one access of size DR_B.access_size at DR_B.dr
277 : one access of size DR_A.access_size at DR_A.dr + STEP_A
278 : one access of size DR_B.access_size at DR_B.dr + STEP_B
279 : one access of size DR_A.access_size at DR_A.dr + STEP_A * 2
280 : one access of size DR_B.access_size at DR_B.dr + STEP_B * 2
281 : ...
282 :
283 : (2) The new code accesses the same data in exactly two chunks:
284 :
285 : one group of accesses spanning |DR_A.seg_len| + DR_A.access_size
286 : one group of accesses spanning |DR_B.seg_len| + DR_B.access_size
287 :
288 : A pair might break this assumption if the DR_A and DR_B accesses
289 : in the original or the new code are mingled in some way. For example,
290 : if DR_A.access_size represents the effect of two individual writes
291 : to nearby locations, the pair breaks the assumption if those writes
292 : occur either side of the access for DR_B.
293 :
294 : Note that DR_ALIAS_ARBITRARY describes whether the ordering assumption
295 : fails to hold for any individual pair in P. If the assumption *does*
296 : hold for every pair in P, it doesn't matter whether it holds for the
297 : composite pair or not. In other words, P should represent the complete
298 : set of pairs that the composite pair is testing, so only the ordering
299 : of two accesses in the same member of P matters. */
300 : const unsigned int DR_ALIAS_RAW = 1U << 0;
301 : const unsigned int DR_ALIAS_WAR = 1U << 1;
302 : const unsigned int DR_ALIAS_WAW = 1U << 2;
303 : const unsigned int DR_ALIAS_ARBITRARY = 1U << 3;
304 : const unsigned int DR_ALIAS_SWAPPED = 1U << 4;
305 : const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5;
306 : const unsigned int DR_ALIAS_MIXED_STEPS = 1U << 6;
307 :
308 : /* This struct contains two dr_with_seg_len objects with aliasing data
309 : refs. Two comparisons are generated from them. */
310 :
311 : class dr_with_seg_len_pair_t
312 : {
313 : public:
314 : /* WELL_ORDERED indicates that the ordering assumption described above
315 : DR_ALIAS_ARBITRARY holds. REORDERED indicates that it doesn't. */
316 : enum sequencing { WELL_ORDERED, REORDERED };
317 :
318 : dr_with_seg_len_pair_t (const dr_with_seg_len &,
319 : const dr_with_seg_len &, sequencing);
320 :
321 : dr_with_seg_len first;
322 : dr_with_seg_len second;
323 : unsigned int flags;
324 : };
325 :
326 72918 : inline dr_with_seg_len_pair_t::
327 : dr_with_seg_len_pair_t (const dr_with_seg_len &d1, const dr_with_seg_len &d2,
328 : sequencing seq)
329 72918 : : first (d1), second (d2), flags (0)
330 : {
331 72918 : if (DR_IS_READ (d1.dr) && DR_IS_WRITE (d2.dr))
332 43009 : flags |= DR_ALIAS_WAR;
333 29909 : else if (DR_IS_WRITE (d1.dr) && DR_IS_READ (d2.dr))
334 9096 : flags |= DR_ALIAS_RAW;
335 20813 : else if (DR_IS_WRITE (d1.dr) && DR_IS_WRITE (d2.dr))
336 20813 : flags |= DR_ALIAS_WAW;
337 : else
338 0 : gcc_unreachable ();
339 72918 : if (seq == REORDERED)
340 8183 : flags |= DR_ALIAS_ARBITRARY;
341 72918 : }
342 :
343 : enum data_dependence_direction {
344 : dir_positive,
345 : dir_negative,
346 : dir_equal,
347 : dir_positive_or_negative,
348 : dir_positive_or_equal,
349 : dir_negative_or_equal,
350 : dir_star,
351 : dir_independent
352 : };
353 :
354 : /* The description of the grid of iterations that overlap. At most
355 : two loops are considered at the same time just now, hence at most
356 : two functions are needed. For each of the functions, we store
357 : the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
358 : where x, y, ... are variables. */
359 :
360 : #define MAX_DIM 2
361 :
362 : /* Special values of N. */
363 : #define NO_DEPENDENCE 0
364 : #define NOT_KNOWN (MAX_DIM + 1)
365 : #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
366 : #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
367 : #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
368 :
369 : typedef vec<tree> affine_fn;
370 :
371 : struct conflict_function
372 : {
373 : unsigned n;
374 : affine_fn fns[MAX_DIM];
375 : };
376 :
377 : /* What is a subscript? Given two array accesses a subscript is the
378 : tuple composed of the access functions for a given dimension.
379 : Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
380 : subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
381 : are stored in the data_dependence_relation structure under the form
382 : of an array of subscripts. */
383 :
384 : struct subscript
385 : {
386 : /* The access functions of the two references. */
387 : tree access_fn[2];
388 :
389 : /* A description of the iterations for which the elements are
390 : accessed twice. */
391 : conflict_function *conflicting_iterations_in_a;
392 : conflict_function *conflicting_iterations_in_b;
393 :
394 : /* This field stores the information about the iteration domain
395 : validity of the dependence relation. */
396 : tree last_conflict;
397 :
398 : /* Distance from the iteration that access a conflicting element in
399 : A to the iteration that access this same conflicting element in
400 : B. The distance is a tree scalar expression, i.e. a constant or a
401 : symbolic expression, but certainly not a chrec function. */
402 : tree distance;
403 : };
404 :
405 : typedef struct subscript *subscript_p;
406 :
407 : #define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
408 : #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
409 : #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
410 : #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
411 : #define SUB_DISTANCE(SUB) (SUB)->distance
412 :
413 : /* A data_dependence_relation represents a relation between two
414 : data_references A and B. */
415 :
416 : struct data_dependence_relation
417 : {
418 :
419 : struct data_reference *a;
420 : struct data_reference *b;
421 :
422 : /* A "yes/no/maybe" field for the dependence relation:
423 :
424 : - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
425 : relation between A and B, and the description of this relation
426 : is given in the SUBSCRIPTS array,
427 :
428 : - when "ARE_DEPENDENT == chrec_known", there is no dependence and
429 : SUBSCRIPTS is empty,
430 :
431 : - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
432 : but the analyzer cannot be more specific. */
433 : tree are_dependent;
434 :
435 : /* If nonnull, COULD_BE_INDEPENDENT_P is true and the accesses are
436 : independent when the runtime addresses of OBJECT_A and OBJECT_B
437 : are different. The addresses of both objects are invariant in the
438 : loop nest. */
439 : tree object_a;
440 : tree object_b;
441 :
442 : /* For each subscript in the dependence test, there is an element in
443 : this array. This is the attribute that labels the edge A->B of
444 : the data_dependence_relation. */
445 : vec<subscript_p> subscripts;
446 :
447 : /* The analyzed loop nest. */
448 : vec<loop_p> loop_nest;
449 :
450 : /* The classic direction vector. */
451 : vec<lambda_vector> dir_vects;
452 :
453 : /* The classic distance vector. */
454 : vec<lambda_vector> dist_vects;
455 :
456 : /* Is the dependence reversed with respect to the lexicographic order? */
457 : bool reversed_p;
458 :
459 : /* When the dependence relation is affine, it can be represented by
460 : a distance vector. */
461 : bool affine_p;
462 :
463 : /* Set to true when the dependence relation is on the same data
464 : access. */
465 : bool self_reference_p;
466 :
467 : /* True if the dependence described is conservatively correct rather
468 : than exact, and if it is still possible for the accesses to be
469 : conditionally independent. For example, the a and b references in:
470 :
471 : struct s *a, *b;
472 : for (int i = 0; i < n; ++i)
473 : a->f[i] += b->f[i];
474 :
475 : conservatively have a distance vector of (0), for the case in which
476 : a == b, but the accesses are independent if a != b. Similarly,
477 : the a and b references in:
478 :
479 : struct s *a, *b;
480 : for (int i = 0; i < n; ++i)
481 : a[0].f[i] += b[i].f[i];
482 :
483 : conservatively have a distance vector of (0), but they are independent
484 : when a != b + i. In contrast, the references in:
485 :
486 : struct s *a;
487 : for (int i = 0; i < n; ++i)
488 : a->f[i] += a->f[i];
489 :
490 : have the same distance vector of (0), but the accesses can never be
491 : independent. */
492 : bool could_be_independent_p;
493 : };
494 :
495 : typedef struct data_dependence_relation *ddr_p;
496 :
497 : #define DDR_A(DDR) (DDR)->a
498 : #define DDR_B(DDR) (DDR)->b
499 : #define DDR_AFFINE_P(DDR) (DDR)->affine_p
500 : #define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
501 : #define DDR_OBJECT_A(DDR) (DDR)->object_a
502 : #define DDR_OBJECT_B(DDR) (DDR)->object_b
503 : #define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
504 : #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
505 : #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
506 :
507 : #define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
508 : /* The size of the direction/distance vectors: the number of loops in
509 : the loop nest. */
510 : #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
511 : #define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
512 :
513 : #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
514 : #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
515 : #define DDR_NUM_DIST_VECTS(DDR) \
516 : (DDR_DIST_VECTS (DDR).length ())
517 : #define DDR_NUM_DIR_VECTS(DDR) \
518 : (DDR_DIR_VECTS (DDR).length ())
519 : #define DDR_DIR_VECT(DDR, I) \
520 : DDR_DIR_VECTS (DDR)[I]
521 : #define DDR_DIST_VECT(DDR, I) \
522 : DDR_DIST_VECTS (DDR)[I]
523 : #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
524 : #define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
525 :
526 :
527 : opt_result dr_analyze_innermost (innermost_loop_behavior *, tree,
528 : class loop *, const gimple *,
529 : tree * = nullptr);
530 : extern bool compute_data_dependences_for_loop (class loop *, bool,
531 : vec<loop_p> *,
532 : vec<data_reference_p> *,
533 : vec<ddr_p> *);
534 : extern void debug_ddrs (vec<ddr_p> );
535 : extern void dump_data_reference (FILE *, struct data_reference *);
536 : extern void debug (data_reference &ref);
537 : extern void debug (data_reference *ptr);
538 : extern void debug_data_reference (struct data_reference *);
539 : extern void debug_data_references (vec<data_reference_p> );
540 : extern void debug (vec<data_reference_p> &ref);
541 : extern void debug (vec<data_reference_p> *ptr);
542 : extern void debug_data_dependence_relation (const data_dependence_relation *);
543 : extern void dump_data_dependence_relations (FILE *, const vec<ddr_p> &);
544 : extern void debug (vec<ddr_p> &ref);
545 : extern void debug (vec<ddr_p> *ptr);
546 : extern void debug_data_dependence_relations (vec<ddr_p> );
547 : extern void free_dependence_relation (struct data_dependence_relation *);
548 : extern void free_dependence_relations (vec<ddr_p>& );
549 : extern void free_data_ref (data_reference_p);
550 : extern void free_data_refs (vec<data_reference_p>& );
551 : void dr_reset (data_reference *);
552 : extern opt_result find_data_references_in_stmt (class loop *, gimple *,
553 : vec<data_reference_p> *,
554 : bool = false);
555 : extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
556 : vec<data_reference_p> *);
557 : tree find_data_references_in_loop (class loop *, vec<data_reference_p> *);
558 : bool loop_nest_has_data_refs (loop_p loop);
559 : struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
560 : bool, bool = false);
561 : extern bool find_loop_nest (class loop *, vec<loop_p> *);
562 : extern struct data_dependence_relation *initialize_data_dependence_relation
563 : (struct data_reference *, struct data_reference *, vec<loop_p>);
564 : extern void compute_affine_dependence (struct data_dependence_relation *,
565 : loop_p);
566 : extern void compute_self_dependence (struct data_dependence_relation *);
567 : extern bool compute_all_dependences (const vec<data_reference_p> &,
568 : vec<ddr_p> *,
569 : const vec<loop_p> &, bool);
570 : extern tree find_data_references_in_bb (class loop *, basic_block,
571 : vec<data_reference_p> *);
572 : extern unsigned int dr_alignment (innermost_loop_behavior *);
573 : extern tree get_base_for_alignment (tree, unsigned int *);
574 :
575 : /* Return the alignment in bytes that DR is guaranteed to have at all
576 : times. */
577 :
578 : inline unsigned int
579 153728 : dr_alignment (data_reference *dr)
580 : {
581 76864 : return dr_alignment (&DR_INNERMOST (dr));
582 : }
583 :
584 : extern bool dr_may_alias_p (const struct data_reference *,
585 : const struct data_reference *, class loop *);
586 : extern bool dr_equal_offsets_p (struct data_reference *,
587 : struct data_reference *);
588 :
589 : extern opt_result runtime_alias_check_p (ddr_p, class loop *, bool);
590 : extern int data_ref_compare_tree (tree, tree);
591 : extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
592 : poly_uint64);
593 : extern void create_runtime_alias_checks (class loop *,
594 : const vec<dr_with_seg_len_pair_t> *,
595 : tree*);
596 : extern tree dr_direction_indicator (struct data_reference *);
597 : extern tree dr_zero_step_indicator (struct data_reference *);
598 : extern bool dr_known_forward_stride_p (struct data_reference *);
599 :
600 : /* Return true when the base objects of data references A and B are
601 : the same memory object. */
602 :
603 : inline bool
604 2750 : same_data_refs_base_objects (data_reference_p a, data_reference_p b)
605 : {
606 5429 : return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
607 2750 : && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
608 : }
609 :
610 : /* Return true when the data references A and B are accessing the same
611 : memory object with the same access functions. Optionally skip the
612 : last OFFSET dimensions in the data reference. */
613 :
614 : inline bool
615 12054 : same_data_refs (data_reference_p a, data_reference_p b, int offset = 0)
616 : {
617 12054 : unsigned int i;
618 :
619 : /* The references are exactly the same. */
620 12054 : if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
621 : return true;
622 :
623 2750 : if (!same_data_refs_base_objects (a, b))
624 : return false;
625 :
626 115 : for (i = offset; i < DR_NUM_DIMENSIONS (a); i++)
627 57 : if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
628 : return false;
629 :
630 : return true;
631 : }
632 :
633 : /* Returns true when all the dependences are computable. */
634 :
635 : inline bool
636 : known_dependences_p (vec<ddr_p> dependence_relations)
637 : {
638 : ddr_p ddr;
639 : unsigned int i;
640 :
641 : FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
642 : if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
643 : return false;
644 :
645 : return true;
646 : }
647 :
648 : /* Returns the dependence level for a vector DIST of size LENGTH.
649 : LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
650 : to the sequence of statements, not carried by any loop. */
651 :
652 : inline unsigned
653 321 : dependence_level (lambda_vector dist_vect, int length)
654 : {
655 321 : int i;
656 :
657 1928 : for (i = 0; i < length; i++)
658 1519 : if (dist_vect[i] != 0)
659 854 : return i + 1;
660 :
661 : return 0;
662 : }
663 :
664 : /* Return the dependence level for the DDR relation. */
665 :
666 : inline unsigned
667 : ddr_dependence_level (ddr_p ddr)
668 : {
669 : unsigned vector;
670 : unsigned level = 0;
671 :
672 : if (DDR_DIST_VECTS (ddr).exists ())
673 : level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
674 :
675 : for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
676 : level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
677 : DDR_NB_LOOPS (ddr)));
678 : return level;
679 : }
680 :
681 : /* Return the index of the variable VAR in the LOOP_NEST array. */
682 :
683 : inline int
684 186425 : index_in_loop_nest (int var, const vec<loop_p> &loop_nest)
685 : {
686 186425 : class loop *loopi;
687 186425 : int var_index;
688 :
689 192328 : for (var_index = 0; loop_nest.iterate (var_index, &loopi); var_index++)
690 192328 : if (loopi->num == var)
691 186425 : return var_index;
692 :
693 0 : gcc_unreachable ();
694 : }
695 :
696 : /* Returns true when the data reference DR the form "A[i] = ..."
697 : with a stride equal to its unit type size. */
698 :
699 : inline bool
700 : adjacent_dr_p (struct data_reference *dr)
701 : {
702 : /* If this is a bitfield store bail out. */
703 : if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
704 : && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
705 : return false;
706 :
707 : if (!DR_STEP (dr)
708 : || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
709 : return false;
710 :
711 : return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
712 : DR_STEP (dr)),
713 : TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
714 : }
715 :
716 : void split_constant_offset (tree , tree *, tree *);
717 :
718 : /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
719 :
720 : inline lambda_int
721 : lambda_vector_gcd (lambda_vector vector, int size)
722 : {
723 : int i;
724 : lambda_int gcd1 = 0;
725 :
726 : if (size > 0)
727 : {
728 : gcd1 = vector[0];
729 : for (i = 1; i < size; i++)
730 : gcd1 = gcd (gcd1, vector[i]);
731 : }
732 : return gcd1;
733 : }
734 :
735 : /* Allocate a new vector of given SIZE. */
736 :
737 : inline lambda_vector
738 2328675 : lambda_vector_new (int size)
739 : {
740 : /* ??? We shouldn't abuse the GC allocator here. */
741 2328675 : return ggc_cleared_vec_alloc<lambda_int> (size);
742 : }
743 :
744 : /* Clear out vector VEC1 of length SIZE. */
745 :
746 : inline void
747 638 : lambda_vector_clear (lambda_vector vec1, int size)
748 : {
749 638 : memset (vec1, 0, size * sizeof (*vec1));
750 : }
751 :
752 : /* Returns true when the vector V is lexicographically positive, in
753 : other words, when the first nonzero element is positive. */
754 :
755 : inline bool
756 50895 : lambda_vector_lexico_pos (lambda_vector v,
757 : unsigned n)
758 : {
759 50895 : unsigned i;
760 56610 : for (i = 0; i < n; i++)
761 : {
762 55630 : if (v[i] == 0)
763 2248 : continue;
764 53382 : if (v[i] < 0)
765 : return false;
766 : if (v[i] > 0)
767 : return true;
768 : }
769 : return true;
770 : }
771 :
772 : /* Return true if vector VEC1 of length SIZE is the zero vector. */
773 :
774 : inline bool
775 44074 : lambda_vector_zerop (lambda_vector vec1, int size)
776 : {
777 44074 : int i;
778 92278 : for (i = 0; i < size; i++)
779 54438 : if (vec1[i] != 0)
780 : return false;
781 : return true;
782 : }
783 :
784 : /* Allocate a matrix of M rows x N cols. */
785 :
786 : inline lambda_matrix
787 5070541 : lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
788 : {
789 5070541 : lambda_matrix mat;
790 5070541 : int i;
791 :
792 5070541 : mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
793 :
794 15210851 : for (i = 0; i < m; i++)
795 10140310 : mat[i] = XOBNEWVEC (lambda_obstack, lambda_int, n);
796 :
797 5070541 : return mat;
798 : }
799 :
800 : #endif /* GCC_TREE_DATA_REF_H */
|