Line data Source code
1 : /* Alias analysis for GNU C
2 : Copyright (C) 1997-2026 Free Software Foundation, Inc.
3 : Contributed by John Carr (jfc@mit.edu).
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 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "target.h"
26 : #include "rtl.h"
27 : #include "tree.h"
28 : #include "gimple.h"
29 : #include "df.h"
30 : #include "memmodel.h"
31 : #include "tm_p.h"
32 : #include "gimple-ssa.h"
33 : #include "emit-rtl.h"
34 : #include "alias.h"
35 : #include "fold-const.h"
36 : #include "varasm.h"
37 : #include "cselib.h"
38 : #include "langhooks.h"
39 : #include "cfganal.h"
40 : #include "rtl-iter.h"
41 : #include "cgraph.h"
42 : #include "ipa-utils.h"
43 :
44 : /* The aliasing API provided here solves related but different problems:
45 :
46 : Say there exists (in c)
47 :
48 : struct X {
49 : struct Y y1;
50 : struct Z z2;
51 : } x1, *px1, *px2;
52 :
53 : struct Y y2, *py;
54 : struct Z z2, *pz;
55 :
56 :
57 : py = &x1.y1;
58 : px2 = &x1;
59 :
60 : Consider the four questions:
61 :
62 : Can a store to x1 interfere with px2->y1?
63 : Can a store to x1 interfere with px2->z2?
64 : Can a store to x1 change the value pointed to by with py?
65 : Can a store to x1 change the value pointed to by with pz?
66 :
67 : The answer to these questions can be yes, yes, yes, and maybe.
68 :
69 : The first two questions can be answered with a simple examination
70 : of the type system. If structure X contains a field of type Y then
71 : a store through a pointer to an X can overwrite any field that is
72 : contained (recursively) in an X (unless we know that px1 != px2).
73 :
74 : The last two questions can be solved in the same way as the first
75 : two questions but this is too conservative. The observation is
76 : that in some cases we can know which (if any) fields are addressed
77 : and if those addresses are used in bad ways. This analysis may be
78 : language specific. In C, arbitrary operations may be applied to
79 : pointers. However, there is some indication that this may be too
80 : conservative for some C++ types.
81 :
82 : The pass ipa-type-escape does this analysis for the types whose
83 : instances do not escape across the compilation boundary.
84 :
85 : Historically in GCC, these two problems were combined and a single
86 : data structure that was used to represent the solution to these
87 : problems. We now have two similar but different data structures,
88 : The data structure to solve the last two questions is similar to
89 : the first, but does not contain the fields whose address are never
90 : taken. For types that do escape the compilation unit, the data
91 : structures will have identical information.
92 : */
93 :
94 : /* The alias sets assigned to MEMs assist the back-end in determining
95 : which MEMs can alias which other MEMs. In general, two MEMs in
96 : different alias sets cannot alias each other, with one important
97 : exception. Consider something like:
98 :
99 : struct S { int i; double d; };
100 :
101 : a store to an `S' can alias something of either type `int' or type
102 : `double'. (However, a store to an `int' cannot alias a `double'
103 : and vice versa.) We indicate this via a tree structure that looks
104 : like:
105 : struct S
106 : / \
107 : / \
108 : |/_ _\|
109 : int double
110 :
111 : (The arrows are directed and point downwards.)
112 : In this situation we say the alias set for `struct S' is the
113 : `superset' and that those for `int' and `double' are `subsets'.
114 :
115 : To see whether two alias sets can point to the same memory, we must
116 : see if either alias set is a subset of the other. We need not trace
117 : past immediate descendants, however, since we propagate all
118 : grandchildren up one level.
119 :
120 : Alias set zero is implicitly a superset of all other alias sets.
121 : However, this is no actual entry for alias set zero. It is an
122 : error to attempt to explicitly construct a subset of zero. */
123 :
124 : struct alias_set_hash : int_hash <int, INT_MIN, INT_MIN + 1> {};
125 :
126 : struct GTY(()) alias_set_entry {
127 : /* The alias set number, as stored in MEM_ALIAS_SET. */
128 : alias_set_type alias_set;
129 :
130 : /* Nonzero if would have a child of zero: this effectively makes this
131 : alias set the same as alias set zero. */
132 : bool has_zero_child;
133 : /* Nonzero if alias set corresponds to pointer type itself (i.e. not to
134 : aggregate contaiing pointer.
135 : This is used for a special case where we need an universal pointer type
136 : compatible with all other pointer types. */
137 : bool is_pointer;
138 : /* Nonzero if is_pointer or if one of childs have has_pointer set. */
139 : bool has_pointer;
140 :
141 : /* The children of the alias set. These are not just the immediate
142 : children, but, in fact, all descendants. So, if we have:
143 :
144 : struct T { struct S s; float f; }
145 :
146 : continuing our example above, the children here will be all of
147 : `int', `double', `float', and `struct S'. */
148 : hash_map<alias_set_hash, int> *children;
149 : };
150 :
151 : static int compare_base_symbol_refs (const_rtx, const_rtx,
152 : HOST_WIDE_INT * = NULL);
153 :
154 : /* Query statistics for the different low-level disambiguators.
155 : A high-level query may trigger multiple of them. */
156 :
157 : static struct {
158 : unsigned long long num_alias_zero;
159 : unsigned long long num_same_alias_set;
160 : unsigned long long num_same_objects;
161 : unsigned long long num_volatile;
162 : unsigned long long num_dag;
163 : unsigned long long num_universal;
164 : unsigned long long num_disambiguated;
165 : } alias_stats;
166 :
167 :
168 : /* Set up all info needed to perform alias analysis on memory references. */
169 :
170 : /* Returns the size in bytes of the mode of X. */
171 : #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
172 :
173 : /* Cap the number of passes we make over the insns propagating alias
174 : information through set chains.
175 : ??? 10 is a completely arbitrary choice. This should be based on the
176 : maximum loop depth in the CFG, but we do not have this information
177 : available (even if current_loops _is_ available). */
178 : #define MAX_ALIAS_LOOP_PASSES 10
179 :
180 : /* reg_base_value[N] gives an address to which register N is related.
181 : If all sets after the first add or subtract to the current value
182 : or otherwise modify it so it does not point to a different top level
183 : object, reg_base_value[N] is equal to the address part of the source
184 : of the first set.
185 :
186 : A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
187 : expressions represent three types of base:
188 :
189 : 1. incoming arguments. There is just one ADDRESS to represent all
190 : arguments, since we do not know at this level whether accesses
191 : based on different arguments can alias. The ADDRESS has id 0.
192 :
193 : 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
194 : (if distinct from frame_pointer_rtx) and arg_pointer_rtx.
195 : Each of these rtxes has a separate ADDRESS associated with it,
196 : each with a negative id.
197 :
198 : GCC is (and is required to be) precise in which register it
199 : chooses to access a particular region of stack. We can therefore
200 : assume that accesses based on one of these rtxes do not alias
201 : accesses based on another of these rtxes.
202 :
203 : 3. bases that are derived from malloc()ed memory (REG_NOALIAS).
204 : Each such piece of memory has a separate ADDRESS associated
205 : with it, each with an id greater than 0.
206 :
207 : Accesses based on one ADDRESS do not alias accesses based on other
208 : ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
209 : alias globals either; the ADDRESSes have Pmode to indicate this.
210 : The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
211 : indicate this. */
212 :
213 : static GTY(()) vec<rtx, va_gc> *reg_base_value;
214 : static rtx *new_reg_base_value;
215 :
216 : /* The single VOIDmode ADDRESS that represents all argument bases.
217 : It has id 0. */
218 : static GTY(()) rtx arg_base_value;
219 :
220 : /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
221 : static int unique_id;
222 :
223 : /* We preserve the copy of old array around to avoid amount of garbage
224 : produced. About 8% of garbage produced were attributed to this
225 : array. */
226 : static GTY((deletable)) vec<rtx, va_gc> *old_reg_base_value;
227 :
228 : /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
229 : registers. */
230 : #define UNIQUE_BASE_VALUE_SP -1
231 : #define UNIQUE_BASE_VALUE_ARGP -2
232 : #define UNIQUE_BASE_VALUE_FP -3
233 : #define UNIQUE_BASE_VALUE_HFP -4
234 :
235 : #define static_reg_base_value \
236 : (this_target_rtl->x_static_reg_base_value)
237 :
238 : #define REG_BASE_VALUE(X) \
239 : (REGNO (X) < vec_safe_length (reg_base_value) \
240 : ? (*reg_base_value)[REGNO (X)] : 0)
241 :
242 : /* Vector indexed by N giving the initial (unchanging) value known for
243 : pseudo-register N. This vector is initialized in init_alias_analysis,
244 : and does not change until end_alias_analysis is called. */
245 : static GTY(()) vec<rtx, va_gc> *reg_known_value;
246 :
247 : /* Vector recording for each reg_known_value whether it is due to a
248 : REG_EQUIV note. Future passes (viz., reload) may replace the
249 : pseudo with the equivalent expression and so we account for the
250 : dependences that would be introduced if that happens.
251 :
252 : The REG_EQUIV notes created in assign_parms may mention the arg
253 : pointer, and there are explicit insns in the RTL that modify the
254 : arg pointer. Thus we must ensure that such insns don't get
255 : scheduled across each other because that would invalidate the
256 : REG_EQUIV notes. One could argue that the REG_EQUIV notes are
257 : wrong, but solving the problem in the scheduler will likely give
258 : better code, so we do it here. */
259 : static sbitmap reg_known_equiv_p;
260 :
261 : /* True when scanning insns from the start of the rtl to the
262 : NOTE_INSN_FUNCTION_BEG note. */
263 : static bool copying_arguments;
264 :
265 :
266 : /* The splay-tree used to store the various alias set entries. */
267 : static GTY (()) vec<alias_set_entry *, va_gc> *alias_sets;
268 :
269 : /* Build a decomposed reference object for querying the alias-oracle
270 : from the MEM rtx and store it in *REF.
271 : Returns false if MEM is not suitable for the alias-oracle. */
272 :
273 : static bool
274 451066799 : ao_ref_from_mem (ao_ref *ref, const_rtx mem)
275 : {
276 451066799 : tree expr = MEM_EXPR (mem);
277 451066799 : tree base;
278 :
279 451066799 : if (!expr)
280 : return false;
281 :
282 405765798 : ao_ref_init (ref, expr);
283 :
284 : /* Get the base of the reference and see if we have to reject or
285 : adjust it. */
286 405765798 : base = ao_ref_base (ref);
287 405765798 : if (base == NULL_TREE)
288 : return false;
289 :
290 : /* The tree oracle doesn't like bases that are neither decls
291 : nor indirect references of SSA names. */
292 436819341 : if (!(DECL_P (base)
293 219207961 : || (TREE_CODE (base) == MEM_REF
294 188319795 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
295 : || (TREE_CODE (base) == TARGET_MEM_REF
296 30849141 : && TREE_CODE (TMR_BASE (base)) == SSA_NAME)))
297 : return false;
298 :
299 405560663 : ref->ref_alias_set = MEM_ALIAS_SET (mem);
300 :
301 : /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
302 : is conservative, so trust it. */
303 405560663 : if (!MEM_OFFSET_KNOWN_P (mem)
304 405560663 : || !MEM_SIZE_KNOWN_P (mem))
305 : return true;
306 :
307 : /* If MEM_OFFSET/MEM_SIZE get us outside of ref->offset/ref->max_size
308 : drop ref->ref. */
309 396693072 : if (maybe_lt (MEM_OFFSET (mem), 0)
310 396693072 : || (ref->max_size_known_p ()
311 352923572 : && maybe_gt ((MEM_OFFSET (mem) + MEM_SIZE (mem)) * BITS_PER_UNIT,
312 : ref->max_size)))
313 41143819 : ref->ref = NULL_TREE;
314 :
315 : /* Refine size and offset we got from analyzing MEM_EXPR by using
316 : MEM_SIZE and MEM_OFFSET. */
317 :
318 396693072 : ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
319 396693072 : ref->size = MEM_SIZE (mem) * BITS_PER_UNIT;
320 :
321 : /* The MEM may extend into adjacent fields, so adjust max_size if
322 : necessary. */
323 396693072 : if (ref->max_size_known_p ())
324 352923617 : ref->max_size = upper_bound (ref->max_size, ref->size);
325 :
326 : /* If MEM_OFFSET and MEM_SIZE might get us outside of the base object of
327 : the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
328 396693072 : if (MEM_EXPR (mem) != get_spill_slot_decl (false)
329 396693072 : && (maybe_lt (ref->offset, 0)
330 355656339 : || (DECL_P (ref->base)
331 137737625 : && (DECL_SIZE (ref->base) == NULL_TREE
332 137618390 : || !poly_int_tree_p (DECL_SIZE (ref->base))
333 137618340 : || maybe_lt (wi::to_poly_offset (DECL_SIZE (ref->base)),
334 534182681 : ref->offset + ref->size)))))
335 128731 : return false;
336 :
337 : return true;
338 : }
339 :
340 : /* Query the alias-oracle on whether the two memory rtx X and MEM may
341 : alias. If TBAA_P is set also apply TBAA. Returns true if the
342 : two rtxen may alias, false otherwise. */
343 :
344 : static bool
345 238249896 : rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
346 : {
347 238249896 : ao_ref ref1, ref2;
348 :
349 238249896 : if (!ao_ref_from_mem (&ref1, x)
350 238249896 : || !ao_ref_from_mem (&ref2, mem))
351 45634867 : return true;
352 :
353 192615029 : return refs_may_alias_p_1 (&ref1, &ref2,
354 : tbaa_p
355 142379167 : && MEM_ALIAS_SET (x) != 0
356 470420473 : && MEM_ALIAS_SET (mem) != 0);
357 : }
358 :
359 : /* Return true if the ref EARLIER behaves the same as LATER with respect
360 : to TBAA for every memory reference that might follow LATER. */
361 :
362 : bool
363 269212 : refs_same_for_tbaa_p (tree earlier, tree later)
364 : {
365 269212 : ao_ref earlier_ref, later_ref;
366 269212 : ao_ref_init (&earlier_ref, earlier);
367 269212 : ao_ref_init (&later_ref, later);
368 269212 : alias_set_type earlier_set = ao_ref_alias_set (&earlier_ref);
369 269212 : alias_set_type later_set = ao_ref_alias_set (&later_ref);
370 326144 : if (!(earlier_set == later_set
371 56932 : || alias_set_subset_of (later_set, earlier_set)))
372 : return false;
373 266562 : alias_set_type later_base_set = ao_ref_base_alias_set (&later_ref);
374 266562 : alias_set_type earlier_base_set = ao_ref_base_alias_set (&earlier_ref);
375 266562 : return (earlier_base_set == later_base_set
376 266562 : || alias_set_subset_of (later_base_set, earlier_base_set));
377 : }
378 :
379 : /* Similar to refs_same_for_tbaa_p() but for use on MEM rtxs. */
380 : bool
381 135324 : mems_same_for_tbaa_p (rtx earlier, rtx later)
382 : {
383 135324 : gcc_assert (MEM_P (earlier));
384 135324 : gcc_assert (MEM_P (later));
385 :
386 135325 : return ((MEM_ALIAS_SET (earlier) == MEM_ALIAS_SET (later)
387 45499 : || alias_set_subset_of (MEM_ALIAS_SET (later),
388 45499 : MEM_ALIAS_SET (earlier)))
389 268162 : && (!MEM_EXPR (earlier)
390 126124 : || refs_same_for_tbaa_p (MEM_EXPR (earlier), MEM_EXPR (later))));
391 : }
392 :
393 : /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
394 : such an entry, or NULL otherwise. */
395 :
396 : static inline alias_set_entry *
397 266388310 : get_alias_set_entry (alias_set_type alias_set)
398 : {
399 532776620 : return (*alias_sets)[alias_set];
400 : }
401 :
402 : /* Returns true if the alias sets for MEM1 and MEM2 are such that
403 : the two MEMs cannot alias each other. */
404 :
405 : static inline bool
406 245688628 : mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
407 : {
408 245688628 : return (flag_strict_aliasing
409 400578233 : && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1),
410 154889605 : MEM_ALIAS_SET (mem2)));
411 : }
412 :
413 : /* Return true if the first alias set is a subset of the second. */
414 :
415 : bool
416 384871 : alias_set_subset_of (alias_set_type set1, alias_set_type set2)
417 : {
418 384871 : alias_set_entry *ase2;
419 :
420 : /* Disable TBAA oracle with !flag_strict_aliasing. */
421 384871 : if (!flag_strict_aliasing)
422 : return true;
423 :
424 : /* Everything is a subset of the "aliases everything" set. */
425 318536 : if (set2 == 0)
426 : return true;
427 :
428 : /* Check if set1 is a subset of set2. */
429 242732 : ase2 = get_alias_set_entry (set2);
430 242732 : if (ase2 != 0
431 242732 : && (ase2->has_zero_child
432 213139 : || (ase2->children && ase2->children->get (set1))))
433 189791 : return true;
434 :
435 : /* As a special case we consider alias set of "void *" to be both subset
436 : and superset of every alias set of a pointer. This extra symmetry does
437 : not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p
438 : to return true on the following testcase:
439 :
440 : void *ptr;
441 : char **ptr2=(char **)&ptr;
442 : *ptr2 = ...
443 :
444 : Additionally if a set contains universal pointer, we consider every pointer
445 : to be a subset of it, but we do not represent this explicitly - doing so
446 : would require us to update transitive closure each time we introduce new
447 : pointer type. This makes aliasing_component_refs_p to return true
448 : on the following testcase:
449 :
450 : struct a {void *ptr;}
451 : char **ptr = (char **)&a.ptr;
452 : ptr = ...
453 :
454 : This makes void * truly universal pointer type. See pointer handling in
455 : get_alias_set for more details. */
456 52941 : if (ase2 && ase2->has_pointer)
457 : {
458 31490 : alias_set_entry *ase1 = get_alias_set_entry (set1);
459 :
460 31490 : if (ase1 && ase1->is_pointer)
461 : {
462 4886 : alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
463 : /* If one is ptr_type_node and other is pointer, then we consider
464 : them subset of each other. */
465 4886 : if (set1 == voidptr_set || set2 == voidptr_set)
466 4238 : return true;
467 : /* If SET2 contains universal pointer's alias set, then we consdier
468 : every (non-universal) pointer. */
469 4083 : if (ase2->children && set1 != voidptr_set
470 4083 : && ase2->children->get (voidptr_set))
471 : return true;
472 : }
473 : }
474 : return false;
475 : }
476 :
477 : /* Return true if the two specified alias sets may conflict. */
478 :
479 : bool
480 310322611 : alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
481 : {
482 310322611 : alias_set_entry *ase1;
483 310322611 : alias_set_entry *ase2;
484 :
485 : /* The easy case. */
486 310322611 : if (alias_sets_must_conflict_p (set1, set2))
487 : return true;
488 :
489 : /* See if the first alias set is a subset of the second. */
490 133712983 : ase1 = get_alias_set_entry (set1);
491 133712983 : if (ase1 != 0
492 133712983 : && ase1->children && ase1->children->get (set2))
493 : {
494 6694330 : ++alias_stats.num_dag;
495 6694330 : return true;
496 : }
497 :
498 : /* Now do the same, but with the alias sets reversed. */
499 127018653 : ase2 = get_alias_set_entry (set2);
500 127018653 : if (ase2 != 0
501 127018653 : && ase2->children && ase2->children->get (set1))
502 : {
503 6968965 : ++alias_stats.num_dag;
504 6968965 : return true;
505 : }
506 :
507 : /* We want void * to be compatible with any other pointer without
508 : really dropping it to alias set 0. Doing so would make it
509 : compatible with all non-pointer types too.
510 :
511 : This is not strictly necessary by the C/C++ language
512 : standards, but avoids common type punning mistakes. In
513 : addition to that, we need the existence of such universal
514 : pointer to implement Fortran's C_PTR type (which is defined as
515 : type compatible with all C pointers). */
516 120049688 : if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer)
517 : {
518 17635204 : alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
519 :
520 : /* If one of the sets corresponds to universal pointer,
521 : we consider it to conflict with anything that is
522 : or contains pointer. */
523 17635204 : if (set1 == voidptr_set || set2 == voidptr_set)
524 : {
525 3613850 : ++alias_stats.num_universal;
526 4449889 : return true;
527 : }
528 : /* If one of sets is (non-universal) pointer and the other
529 : contains universal pointer, we also get conflict. */
530 14021354 : if (ase1->is_pointer && set2 != voidptr_set
531 14021354 : && ase2->children && ase2->children->get (voidptr_set))
532 : {
533 666069 : ++alias_stats.num_universal;
534 666069 : return true;
535 : }
536 13355285 : if (ase2->is_pointer && set1 != voidptr_set
537 13355285 : && ase1->children && ase1->children->get (voidptr_set))
538 : {
539 169970 : ++alias_stats.num_universal;
540 169970 : return true;
541 : }
542 : }
543 :
544 115599799 : ++alias_stats.num_disambiguated;
545 :
546 : /* The two alias sets are distinct and neither one is the
547 : child of the other. Therefore, they cannot conflict. */
548 115599799 : return false;
549 : }
550 :
551 : /* Return true if the two specified alias sets will always conflict. */
552 :
553 : bool
554 310338562 : alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
555 : {
556 : /* Disable TBAA oracle with !flag_strict_aliasing. */
557 310338562 : if (!flag_strict_aliasing)
558 : return true;
559 305619673 : if (set1 == 0 || set2 == 0)
560 : {
561 109302559 : ++alias_stats.num_alias_zero;
562 109302559 : return true;
563 : }
564 196317114 : if (set1 == set2)
565 : {
566 62603628 : ++alias_stats.num_same_alias_set;
567 62603628 : return true;
568 : }
569 :
570 : return false;
571 : }
572 :
573 : /* Return true if any MEM object of type T1 will always conflict (using the
574 : dependency routines in this file) with any MEM object of type T2.
575 : This is used when allocating temporary storage. If T1 and/or T2 are
576 : NULL_TREE, it means we know nothing about the storage. */
577 :
578 : bool
579 10285612 : objects_must_conflict_p (tree t1, tree t2)
580 : {
581 10285612 : alias_set_type set1, set2;
582 :
583 : /* If neither has a type specified, we don't know if they'll conflict
584 : because we may be using them to store objects of various types, for
585 : example the argument and local variables areas of inlined functions. */
586 10285612 : if (t1 == 0 && t2 == 0)
587 : return false;
588 :
589 : /* If they are the same type, they must conflict. */
590 64187 : if (t1 == t2)
591 : {
592 48266 : ++alias_stats.num_same_objects;
593 48266 : return true;
594 : }
595 : /* Likewise if both are volatile. */
596 15921 : if (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2))
597 : {
598 0 : ++alias_stats.num_volatile;
599 0 : return true;
600 : }
601 :
602 15921 : set1 = t1 ? get_alias_set (t1) : 0;
603 15921 : set2 = t2 ? get_alias_set (t2) : 0;
604 :
605 : /* We can't use alias_sets_conflict_p because we must make sure
606 : that every subtype of t1 will conflict with every subtype of
607 : t2 for which a pair of subobjects of these respective subtypes
608 : overlaps on the stack. */
609 15921 : return alias_sets_must_conflict_p (set1, set2);
610 : }
611 :
612 : /* Return true if T is an end of the access path which can be used
613 : by type based alias oracle. */
614 :
615 : bool
616 496939946 : ends_tbaa_access_path_p (const_tree t)
617 : {
618 496939946 : switch (TREE_CODE (t))
619 : {
620 369219013 : case COMPONENT_REF:
621 369219013 : if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
622 : return true;
623 : /* Permit type-punning when accessing a union, provided the access
624 : is directly through the union. For example, this code does not
625 : permit taking the address of a union member and then storing
626 : through it. Even the type-punning allowed here is a GCC
627 : extension, albeit a common and useful one; the C standard says
628 : that such accesses have implementation-defined behavior. */
629 363443859 : else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE)
630 : return true;
631 : break;
632 :
633 122452193 : case ARRAY_REF:
634 122452193 : case ARRAY_RANGE_REF:
635 122452193 : if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
636 : return true;
637 : break;
638 :
639 : case REALPART_EXPR:
640 : case IMAGPART_EXPR:
641 : break;
642 :
643 : case BIT_FIELD_REF:
644 : case VIEW_CONVERT_EXPR:
645 : /* Bitfields and casts are never addressable. */
646 : return true;
647 0 : break;
648 :
649 0 : default:
650 0 : gcc_unreachable ();
651 : }
652 : return false;
653 : }
654 :
655 : /* Return the outermost parent of component present in the chain of
656 : component references handled by get_inner_reference in T with the
657 : following property:
658 : - the component is non-addressable
659 : or NULL_TREE if no such parent exists. In the former cases, the alias
660 : set of this parent is the alias set that must be used for T itself. */
661 :
662 : tree
663 1126422674 : component_uses_parent_alias_set_from (const_tree t)
664 : {
665 1126422674 : const_tree found = NULL_TREE;
666 :
667 1591644724 : while (handled_component_p (t))
668 : {
669 465222050 : if (ends_tbaa_access_path_p (t))
670 16749756 : found = t;
671 :
672 465222050 : t = TREE_OPERAND (t, 0);
673 : }
674 :
675 1126422674 : if (found)
676 16534290 : return TREE_OPERAND (found, 0);
677 :
678 : return NULL_TREE;
679 : }
680 :
681 :
682 : /* Return whether the pointer-type T effective for aliasing may
683 : access everything and thus the reference has to be assigned
684 : alias-set zero. */
685 :
686 : static bool
687 983074857 : ref_all_alias_ptr_type_p (const_tree t)
688 : {
689 983074857 : return (VOID_TYPE_P (TREE_TYPE (t))
690 983074857 : || TYPE_REF_CAN_ALIAS_ALL (t));
691 : }
692 :
693 : /* Return the alias set for the memory pointed to by T, which may be
694 : either a type or an expression. Return -1 if there is nothing
695 : special about dereferencing T. */
696 :
697 : static alias_set_type
698 131895985 : get_deref_alias_set_1 (tree t)
699 : {
700 : /* All we care about is the type. */
701 131895985 : if (! TYPE_P (t))
702 14 : t = TREE_TYPE (t);
703 :
704 : /* If we have an INDIRECT_REF via a void pointer, we don't
705 : know anything about what that might alias. Likewise if the
706 : pointer is marked that way. */
707 131895985 : if (ref_all_alias_ptr_type_p (t))
708 26737049 : return 0;
709 :
710 : return -1;
711 : }
712 :
713 : /* Return the alias set for the memory pointed to by T, which may be
714 : either a type or an expression. */
715 :
716 : alias_set_type
717 203637531 : get_deref_alias_set (tree t)
718 : {
719 : /* If we're not doing any alias analysis, just assume everything
720 : aliases everything else. */
721 203637531 : if (!flag_strict_aliasing)
722 : return 0;
723 :
724 131895985 : alias_set_type set = get_deref_alias_set_1 (t);
725 :
726 : /* Fall back to the alias-set of the pointed-to type. */
727 131895985 : if (set == -1)
728 : {
729 105158936 : if (! TYPE_P (t))
730 14 : t = TREE_TYPE (t);
731 105158936 : set = get_alias_set (TREE_TYPE (t));
732 : }
733 :
734 : return set;
735 : }
736 :
737 : /* Return the pointer-type relevant for TBAA purposes from the
738 : memory reference tree *T or NULL_TREE in which case *T is
739 : adjusted to point to the outermost component reference that
740 : can be used for assigning an alias set. */
741 :
742 : tree
743 1301126438 : reference_alias_ptr_type_1 (tree *t)
744 : {
745 1301126438 : tree inner;
746 :
747 : /* Get the base object of the reference. */
748 1301126438 : inner = *t;
749 1753472356 : while (handled_component_p (inner))
750 : {
751 : /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
752 : the type of any component references that wrap it to
753 : determine the alias-set. */
754 452345918 : if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
755 1681990 : *t = TREE_OPERAND (inner, 0);
756 452345918 : inner = TREE_OPERAND (inner, 0);
757 : }
758 :
759 : /* Handle pointer dereferences here, they can override the
760 : alias-set. */
761 1301126438 : if (INDIRECT_REF_P (inner)
762 1301126438 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 0))))
763 0 : return TREE_TYPE (TREE_OPERAND (inner, 0));
764 1301126438 : else if (TREE_CODE (inner) == TARGET_MEM_REF)
765 52367461 : return TREE_TYPE (TMR_OFFSET (inner));
766 1248758977 : else if (TREE_CODE (inner) == MEM_REF
767 1248758977 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 1))))
768 28952217 : return TREE_TYPE (TREE_OPERAND (inner, 1));
769 :
770 : /* If the innermost reference is a MEM_REF that has a
771 : conversion embedded treat it like a VIEW_CONVERT_EXPR above,
772 : using the memory access type for determining the alias-set. */
773 1219806760 : if (view_converted_memref_p (inner))
774 : {
775 123626459 : tree alias_ptrtype = TREE_TYPE (TREE_OPERAND (inner, 1));
776 : /* Unless we have the (aggregate) effective type of the access
777 : somewhere on the access path. If we have for example
778 : (&a->elts[i])->l.len exposed by abstraction we'd see
779 : MEM <A> [(B *)a].elts[i].l.len and we can use the alias set
780 : of 'len' when typeof (MEM <A> [(B *)a].elts[i]) == B for
781 : example. See PR111715. */
782 123626459 : tree inner = *t;
783 123626459 : while (handled_component_p (inner)
784 124358046 : && (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
785 1890737 : != TYPE_MAIN_VARIANT (TREE_TYPE (alias_ptrtype))))
786 731587 : inner = TREE_OPERAND (inner, 0);
787 123626459 : if (TREE_CODE (inner) == MEM_REF)
788 : return alias_ptrtype;
789 : }
790 :
791 : /* Otherwise, pick up the outermost object that we could have
792 : a pointer to. */
793 1097339451 : tree tem = component_uses_parent_alias_set_from (*t);
794 1097339451 : if (tem)
795 15375176 : *t = tem;
796 :
797 : return NULL_TREE;
798 : }
799 :
800 : /* Return the pointer-type relevant for TBAA purposes from the
801 : gimple memory reference tree T. This is the type to be used for
802 : the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
803 : and guarantees that get_alias_set will return the same alias
804 : set for T and the replacement. */
805 :
806 : tree
807 9557122 : reference_alias_ptr_type (tree t)
808 : {
809 : /* If the frontend assigns this alias-set zero, preserve that. */
810 9557122 : if (lang_hooks.get_alias_set (t) == 0)
811 0 : return ptr_type_node;
812 :
813 9557122 : tree ptype = reference_alias_ptr_type_1 (&t);
814 : /* If there is a given pointer type for aliasing purposes, return it. */
815 9557122 : if (ptype != NULL_TREE)
816 : return ptype;
817 :
818 : /* Otherwise build one from the outermost component reference we
819 : may use. */
820 8859566 : if (TREE_CODE (t) == MEM_REF
821 8859566 : || TREE_CODE (t) == TARGET_MEM_REF)
822 1122726 : return TREE_TYPE (TREE_OPERAND (t, 1));
823 : else
824 7736840 : return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t)));
825 : }
826 :
827 : /* Return whether the pointer-types T1 and T2 used to determine
828 : two alias sets of two references will yield the same answer
829 : from get_deref_alias_set. */
830 :
831 : bool
832 15023461 : alias_ptr_types_compatible_p (tree t1, tree t2)
833 : {
834 15023461 : if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
835 : return true;
836 :
837 2365515 : if (ref_all_alias_ptr_type_p (t1)
838 2365515 : || ref_all_alias_ptr_type_p (t2))
839 : return false;
840 :
841 : /* This function originally abstracts from simply comparing
842 : get_deref_alias_set so that we are sure this still computes
843 : the same result after LTO type merging is applied.
844 : When in LTO type merging is done we can actually do this compare.
845 : */
846 2320722 : if (in_lto_p)
847 5616 : return get_deref_alias_set (t1) == get_deref_alias_set (t2);
848 : else
849 2315106 : return (TYPE_MAIN_VARIANT (TREE_TYPE (t1))
850 2315106 : == TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
851 : }
852 :
853 : /* Create emptry alias set entry. */
854 :
855 : alias_set_entry *
856 1264637 : init_alias_set_entry (alias_set_type set)
857 : {
858 1264637 : alias_set_entry *ase = ggc_alloc<alias_set_entry> ();
859 1264637 : ase->alias_set = set;
860 1264637 : ase->children = NULL;
861 1264637 : ase->has_zero_child = false;
862 1264637 : ase->is_pointer = false;
863 1264637 : ase->has_pointer = false;
864 1264637 : gcc_checking_assert (!get_alias_set_entry (set));
865 1264637 : (*alias_sets)[set] = ase;
866 1264637 : return ase;
867 : }
868 :
869 : /* Return the alias set for T, which may be either a type or an
870 : expression. Call language-specific routine for help, if needed. */
871 :
872 : alias_set_type
873 1579019315 : get_alias_set (tree t)
874 : {
875 1579019315 : alias_set_type set;
876 :
877 : /* We cannot give up with -fno-strict-aliasing because we need to build
878 : proper type representations for possible functions which are built with
879 : -fstrict-aliasing. */
880 :
881 : /* return 0 if this or its type is an error. */
882 1579019315 : if (t == error_mark_node
883 1579019315 : || (! TYPE_P (t)
884 1291230610 : && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
885 : return 0;
886 :
887 : /* We can be passed either an expression or a type. This and the
888 : language-specific routine may make mutually-recursive calls to each other
889 : to figure out what to do. At each juncture, we see if this is a tree
890 : that the language may need to handle specially. First handle things that
891 : aren't types. */
892 1579019315 : if (! TYPE_P (t))
893 : {
894 : /* Give the language a chance to do something with this tree
895 : before we look at it. */
896 1291230610 : STRIP_NOPS (t);
897 1291230610 : set = lang_hooks.get_alias_set (t);
898 1291230610 : if (set != -1)
899 : return set;
900 :
901 : /* Get the alias pointer-type to use or the outermost object
902 : that we could have a pointer to. */
903 1291230610 : tree ptype = reference_alias_ptr_type_1 (&t);
904 1291230610 : if (ptype != NULL)
905 203085961 : return get_deref_alias_set (ptype);
906 :
907 : /* If we've already determined the alias set for a decl, just return
908 : it. This is necessary for C++ anonymous unions, whose component
909 : variables don't look like union members (boo!). */
910 1088144649 : if (VAR_P (t)
911 1088144649 : && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
912 160522266 : return MEM_ALIAS_SET (DECL_RTL (t));
913 :
914 : /* Now all we care about is the type. */
915 1007883516 : t = TREE_TYPE (t);
916 : }
917 :
918 : /* Variant qualifiers don't affect the alias set, so get the main
919 : variant. */
920 1295672221 : t = TYPE_MAIN_VARIANT (t);
921 :
922 1295672221 : if (AGGREGATE_TYPE_P (t)
923 1295672221 : && TYPE_TYPELESS_STORAGE (t))
924 : return 0;
925 :
926 : /* Always use the canonical type as well. If this is a type that
927 : requires structural comparisons to identify compatible types
928 : use alias set zero. */
929 1188513005 : if (TYPE_STRUCTURAL_EQUALITY_P (t))
930 : {
931 : /* Allow the language to specify another alias set for this
932 : type. */
933 263378064 : set = lang_hooks.get_alias_set (t);
934 263378064 : if (set != -1)
935 : return set;
936 : /* Handle structure type equality for pointer types, arrays and vectors.
937 : This is easy to do, because the code below ignores canonical types on
938 : these anyway. This is important for LTO, where TYPE_CANONICAL for
939 : pointers cannot be meaningfully computed by the frontend. */
940 262918945 : if (canonical_type_used_p (t))
941 : {
942 : /* In LTO we set canonical types for all types where it makes
943 : sense to do so. Double check we did not miss some type. */
944 179408072 : gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
945 : return 0;
946 : }
947 : }
948 : else
949 : {
950 925134941 : t = TYPE_CANONICAL (t);
951 925134941 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
952 925134941 : if (t != TYPE_MAIN_VARIANT (t))
953 : {
954 2 : t = TYPE_MAIN_VARIANT (t);
955 2 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
956 : }
957 : }
958 :
959 : /* If this is a type with a known alias set, return it. */
960 1008645814 : gcc_checking_assert (t == TYPE_MAIN_VARIANT (t));
961 1008645814 : if (TYPE_ALIAS_SET_KNOWN_P (t))
962 943722382 : return TYPE_ALIAS_SET (t);
963 :
964 : /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
965 64923432 : if (!COMPLETE_TYPE_P (t))
966 : {
967 : /* For arrays with unknown size the conservative answer is the
968 : alias set of the element type. */
969 14222474 : if (TREE_CODE (t) == ARRAY_TYPE)
970 14176207 : return get_alias_set (TREE_TYPE (t));
971 :
972 : /* But return zero as a conservative answer for incomplete types. */
973 : return 0;
974 : }
975 :
976 : /* See if the language has special handling for this type. */
977 50700958 : set = lang_hooks.get_alias_set (t);
978 50700958 : if (set != -1)
979 : return set;
980 :
981 : /* There are no objects of FUNCTION_TYPE, so there's no point in
982 : using up an alias set for them. (There are, of course, pointers
983 : and references to functions, but that's different.) */
984 2597606 : else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
985 : set = 0;
986 :
987 : /* Unless the language specifies otherwise, let vector types alias
988 : their components. This avoids some nasty type punning issues in
989 : normal usage. And indeed lets vectors be treated more like an
990 : array slice. */
991 2593403 : else if (TREE_CODE (t) == VECTOR_TYPE)
992 91949 : set = get_alias_set (TREE_TYPE (t));
993 :
994 : /* Unless the language specifies otherwise, treat array types the
995 : same as their components. This avoids the asymmetry we get
996 : through recording the components. Consider accessing a
997 : character(kind=1) through a reference to a character(kind=1)[1:1].
998 : Or consider if we want to assign integer(kind=4)[0:D.1387] and
999 : integer(kind=4)[4] the same alias set or not.
1000 : Just be pragmatic here and make sure the array and its element
1001 : type get the same alias set assigned. */
1002 2501454 : else if (TREE_CODE (t) == ARRAY_TYPE
1003 2501454 : && (!TYPE_NONALIASED_COMPONENT (t)
1004 0 : || TYPE_STRUCTURAL_EQUALITY_P (t)))
1005 397073 : set = get_alias_set (TREE_TYPE (t));
1006 :
1007 : /* From the former common C and C++ langhook implementation:
1008 :
1009 : Unfortunately, there is no canonical form of a pointer type.
1010 : In particular, if we have `typedef int I', then `int *', and
1011 : `I *' are different types. So, we have to pick a canonical
1012 : representative. We do this below.
1013 :
1014 : Technically, this approach is actually more conservative that
1015 : it needs to be. In particular, `const int *' and `int *'
1016 : should be in different alias sets, according to the C and C++
1017 : standard, since their types are not the same, and so,
1018 : technically, an `int **' and `const int **' cannot point at
1019 : the same thing.
1020 :
1021 : But, the standard is wrong. In particular, this code is
1022 : legal C++:
1023 :
1024 : int *ip;
1025 : int **ipp = &ip;
1026 : const int* const* cipp = ipp;
1027 : And, it doesn't make sense for that to be legal unless you
1028 : can dereference IPP and CIPP. So, we ignore cv-qualifiers on
1029 : the pointed-to types. This issue has been reported to the
1030 : C++ committee.
1031 :
1032 : For this reason go to canonical type of the unqalified pointer type.
1033 : Until GCC 6 this code set all pointers sets to have alias set of
1034 : ptr_type_node but that is a bad idea, because it prevents disabiguations
1035 : in between pointers. For Firefox this accounts about 20% of all
1036 : disambiguations in the program. */
1037 2104381 : else if (POINTER_TYPE_P (t) && t != ptr_type_node)
1038 : {
1039 695178 : tree p;
1040 695178 : auto_vec <bool, 8> reference;
1041 :
1042 : /* Unnest all pointers and references.
1043 : We also want to make pointer to array/vector equivalent to pointer to
1044 : its element (see the reasoning above). Skip all those types, too. */
1045 695178 : for (p = t; POINTER_TYPE_P (p)
1046 760329 : || (TREE_CODE (p) == ARRAY_TYPE
1047 64039 : && (!TYPE_NONALIASED_COMPONENT (p)
1048 0 : || !COMPLETE_TYPE_P (p)
1049 0 : || TYPE_STRUCTURAL_EQUALITY_P (p)))
1050 2225985 : || TREE_CODE (p) == VECTOR_TYPE;
1051 834517 : p = TREE_TYPE (p))
1052 : {
1053 : /* Ada supports recursive pointers. Instead of doing recursion
1054 : check, just give up once the preallocated space of 8 elements
1055 : is up. In this case just punt to void * alias set. */
1056 834584 : if (reference.length () == 8)
1057 : {
1058 67 : p = ptr_type_node;
1059 67 : break;
1060 : }
1061 834517 : if (TREE_CODE (p) == REFERENCE_TYPE)
1062 : /* In LTO we want languages that use references to be compatible
1063 : with languages that use pointers. */
1064 48845 : reference.safe_push (true && !in_lto_p);
1065 834517 : if (TREE_CODE (p) == POINTER_TYPE)
1066 720493 : reference.safe_push (false);
1067 : }
1068 695178 : p = TYPE_MAIN_VARIANT (p);
1069 :
1070 : /* In LTO for C++ programs we can turn incomplete types to complete
1071 : using ODR name lookup. */
1072 695178 : if (in_lto_p && TYPE_STRUCTURAL_EQUALITY_P (p) && odr_type_p (p))
1073 : {
1074 287 : p = prevailing_odr_type (p);
1075 287 : gcc_checking_assert (TYPE_MAIN_VARIANT (p) == p);
1076 : }
1077 :
1078 : /* Make void * compatible with char * and also void **.
1079 : Programs are commonly violating TBAA by this.
1080 :
1081 : We also make void * to conflict with every pointer
1082 : (see record_component_aliases) and thus it is safe it to use it for
1083 : pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
1084 695178 : if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
1085 125721 : set = get_alias_set (ptr_type_node);
1086 : else
1087 : {
1088 : /* Rebuild pointer type starting from canonical types using
1089 : unqualified pointers and references only. This way all such
1090 : pointers will have the same alias set and will conflict with
1091 : each other.
1092 :
1093 : Most of time we already have pointers or references of a given type.
1094 : If not we build new one just to be sure that if someone later
1095 : (probably only middle-end can, as we should assign all alias
1096 : classes only after finishing translation unit) builds the pointer
1097 : type, the canonical type will match. */
1098 569457 : p = TYPE_CANONICAL (p);
1099 1190130 : while (!reference.is_empty ())
1100 : {
1101 620673 : if (reference.pop ())
1102 46899 : p = build_reference_type (p);
1103 : else
1104 573774 : p = build_pointer_type (p);
1105 620673 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1106 : /* build_pointer_type should always return the canonical type.
1107 : For LTO TYPE_CANONICAL may be NULL, because we do not compute
1108 : them. Be sure that frontends do not glob canonical types of
1109 : pointers in unexpected way and that p == TYPE_CANONICAL (p)
1110 : in all other cases. */
1111 620673 : gcc_checking_assert (!TYPE_CANONICAL (p)
1112 : || p == TYPE_CANONICAL (p));
1113 : }
1114 :
1115 : /* Assign the alias set to both p and t.
1116 : We cannot call get_alias_set (p) here as that would trigger
1117 : infinite recursion when p == t. In other cases it would just
1118 : trigger unnecesary legwork of rebuilding the pointer again. */
1119 569457 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1120 569457 : if (TYPE_ALIAS_SET_KNOWN_P (p))
1121 69734 : set = TYPE_ALIAS_SET (p);
1122 : else
1123 : {
1124 499723 : set = new_alias_set ();
1125 499723 : TYPE_ALIAS_SET (p) = set;
1126 : }
1127 : }
1128 695178 : }
1129 : /* Alias set of ptr_type_node is special and serve as universal pointer which
1130 : is TBAA compatible with every other pointer type. Be sure we have the
1131 : alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
1132 : of pointer types NULL. */
1133 1409203 : else if (t == ptr_type_node)
1134 61621 : set = new_alias_set ();
1135 :
1136 : /* Otherwise make a new alias set for this type. */
1137 : else
1138 : {
1139 : /* Each canonical type gets its own alias set, so canonical types
1140 : shouldn't form a tree. It doesn't really matter for types
1141 : we handle specially above, so only check it where it possibly
1142 : would result in a bogus alias set. */
1143 1347582 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
1144 :
1145 1347582 : set = new_alias_set ();
1146 : }
1147 :
1148 2597606 : TYPE_ALIAS_SET (t) = set;
1149 :
1150 : /* If this is an aggregate type or a complex type, we must record any
1151 : component aliasing information. */
1152 2597606 : if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
1153 1194636 : record_component_aliases (t);
1154 :
1155 : /* We treat pointer types specially in alias_set_subset_of. */
1156 2597606 : if (POINTER_TYPE_P (t) && set)
1157 : {
1158 756799 : alias_set_entry *ase = get_alias_set_entry (set);
1159 756799 : if (!ase)
1160 561344 : ase = init_alias_set_entry (set);
1161 756799 : ase->is_pointer = true;
1162 756799 : ase->has_pointer = true;
1163 : }
1164 :
1165 : return set;
1166 : }
1167 :
1168 : /* Return a brand-new alias set. */
1169 :
1170 : alias_set_type
1171 1970105 : new_alias_set (void)
1172 : {
1173 1970105 : if (alias_sets == 0)
1174 205521 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1175 1970105 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1176 1970105 : return alias_sets->length () - 1;
1177 : }
1178 :
1179 : /* Indicate that things in SUBSET can alias things in SUPERSET, but that
1180 : not everything that aliases SUPERSET also aliases SUBSET. For example,
1181 : in C, a store to an `int' can alias a load of a structure containing an
1182 : `int', and vice versa. But it can't alias a load of a 'double' member
1183 : of the same structure. Here, the structure would be the SUPERSET and
1184 : `int' the SUBSET. This relationship is also described in the comment at
1185 : the beginning of this file.
1186 :
1187 : This function should be called only once per SUPERSET/SUBSET pair.
1188 :
1189 : It is illegal for SUPERSET to be zero; everything is implicitly a
1190 : subset of alias set zero. */
1191 :
1192 : void
1193 2093314 : record_alias_subset (alias_set_type superset, alias_set_type subset)
1194 : {
1195 2093314 : alias_set_entry *superset_entry;
1196 2093314 : alias_set_entry *subset_entry;
1197 :
1198 : /* It is possible in complex type situations for both sets to be the same,
1199 : in which case we can ignore this operation. */
1200 2093314 : if (superset == subset)
1201 : return;
1202 :
1203 2093314 : gcc_assert (superset);
1204 :
1205 2093314 : superset_entry = get_alias_set_entry (superset);
1206 2093314 : if (superset_entry == 0)
1207 : {
1208 : /* Create an entry for the SUPERSET, so that we have a place to
1209 : attach the SUBSET. */
1210 703293 : superset_entry = init_alias_set_entry (superset);
1211 : }
1212 :
1213 2093314 : if (subset == 0)
1214 85421 : superset_entry->has_zero_child = 1;
1215 : else
1216 : {
1217 2007893 : if (!superset_entry->children)
1218 692728 : superset_entry->children
1219 692728 : = hash_map<alias_set_hash, int>::create_ggc (64);
1220 :
1221 : /* Enter the SUBSET itself as a child of the SUPERSET. If it was
1222 : already there we're done. */
1223 2007893 : if (superset_entry->children->put (subset, 0))
1224 : return;
1225 :
1226 1267702 : subset_entry = get_alias_set_entry (subset);
1227 : /* If there is an entry for the subset, enter all of its children
1228 : (if they are not already present) as children of the SUPERSET. */
1229 1267702 : if (subset_entry)
1230 : {
1231 759715 : if (subset_entry->has_zero_child)
1232 15608 : superset_entry->has_zero_child = true;
1233 759715 : if (subset_entry->has_pointer)
1234 613209 : superset_entry->has_pointer = true;
1235 :
1236 759715 : if (subset_entry->children)
1237 : {
1238 329290 : hash_map<alias_set_hash, int>::iterator iter
1239 329290 : = subset_entry->children->begin ();
1240 603141220 : for (; iter != subset_entry->children->end (); ++iter)
1241 301076675 : superset_entry->children->put ((*iter).first, (*iter).second);
1242 : }
1243 : }
1244 : }
1245 : }
1246 :
1247 : /* Record that component types of TYPE, if any, are part of SUPERSET for
1248 : aliasing purposes. For record types, we only record component types
1249 : for fields that are not marked non-addressable. For array types, we
1250 : only record the component type if it is not marked non-aliased. */
1251 :
1252 : void
1253 1279977 : record_component_aliases (tree type, alias_set_type superset)
1254 : {
1255 1279977 : tree field;
1256 :
1257 1279977 : if (superset == 0)
1258 : return;
1259 :
1260 1232870 : switch (TREE_CODE (type))
1261 : {
1262 792359 : case RECORD_TYPE:
1263 792359 : case UNION_TYPE:
1264 792359 : case QUAL_UNION_TYPE:
1265 792359 : {
1266 : /* LTO non-ODR type merging does not make any difference between
1267 : component pointer types. We may have
1268 :
1269 : struct foo {int *a;};
1270 :
1271 : as TYPE_CANONICAL of
1272 :
1273 : struct bar {float *a;};
1274 :
1275 : Because accesses to int * and float * do not alias, we would get
1276 : false negative when accessing the same memory location by
1277 : float ** and bar *. We thus record the canonical type as:
1278 :
1279 : struct {void *a;};
1280 :
1281 : void * is special cased and works as a universal pointer type.
1282 : Accesses to it conflicts with accesses to any other pointer
1283 : type. */
1284 792359 : bool void_pointers = in_lto_p
1285 792359 : && (!odr_type_p (type)
1286 6100 : || !odr_based_tbaa_p (type));
1287 14724675 : for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
1288 13932316 : if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
1289 : {
1290 2088094 : tree t = TREE_TYPE (field);
1291 2088094 : if (void_pointers)
1292 : {
1293 : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1294 : element type and that type has to be normalized to void *,
1295 : too, in the case it is a pointer. */
1296 26845 : while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
1297 : {
1298 1791 : gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
1299 1791 : t = TREE_TYPE (t);
1300 : }
1301 23263 : if (POINTER_TYPE_P (t))
1302 6611 : t = ptr_type_node;
1303 16652 : else if (flag_checking)
1304 16652 : gcc_checking_assert (get_alias_set (t)
1305 : == get_alias_set (TREE_TYPE (field)));
1306 : }
1307 :
1308 2088094 : alias_set_type set = get_alias_set (t);
1309 2088094 : record_alias_subset (superset, set);
1310 : /* If the field has alias-set zero make sure to still record
1311 : any componets of it. This makes sure that for
1312 : struct A {
1313 : struct B {
1314 : int i;
1315 : char c[4];
1316 : } b;
1317 : };
1318 : in C++ even though 'B' has alias-set zero because
1319 : TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of
1320 : 'int' as subset. */
1321 2088094 : if (set == 0)
1322 85341 : record_component_aliases (t, superset);
1323 : }
1324 : }
1325 : break;
1326 :
1327 5220 : case COMPLEX_TYPE:
1328 5220 : record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
1329 5220 : break;
1330 :
1331 : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1332 : element type. */
1333 :
1334 : default:
1335 : break;
1336 : }
1337 : }
1338 :
1339 : /* Record that component types of TYPE, if any, are part of that type for
1340 : aliasing purposes. For record types, we only record component types
1341 : for fields that are not marked non-addressable. For array types, we
1342 : only record the component type if it is not marked non-aliased. */
1343 :
1344 : void
1345 1194636 : record_component_aliases (tree type)
1346 : {
1347 1194636 : alias_set_type superset = get_alias_set (type);
1348 1194636 : record_component_aliases (type, superset);
1349 1194636 : }
1350 :
1351 :
1352 : /* Allocate an alias set for use in storing and reading from the varargs
1353 : spill area. */
1354 :
1355 : static GTY(()) alias_set_type varargs_set = -1;
1356 :
1357 : alias_set_type
1358 21078 : get_varargs_alias_set (void)
1359 : {
1360 : #if 1
1361 : /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1362 : varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1363 : consistently use the varargs alias set for loads from the varargs
1364 : area. So don't use it anywhere. */
1365 21078 : return 0;
1366 : #else
1367 : if (varargs_set == -1)
1368 : varargs_set = new_alias_set ();
1369 :
1370 : return varargs_set;
1371 : #endif
1372 : }
1373 :
1374 : /* Likewise, but used for the fixed portions of the frame, e.g., register
1375 : save areas. */
1376 :
1377 : static GTY(()) alias_set_type frame_set = -1;
1378 :
1379 : alias_set_type
1380 1271379 : get_frame_alias_set (void)
1381 : {
1382 1271379 : if (frame_set == -1)
1383 24660 : frame_set = new_alias_set ();
1384 :
1385 1271379 : return frame_set;
1386 : }
1387 :
1388 : /* Create a new, unique base with id ID. */
1389 :
1390 : static rtx
1391 1896334 : unique_base_value (HOST_WIDE_INT id)
1392 : {
1393 1962449 : return gen_rtx_ADDRESS (Pmode, id);
1394 : }
1395 :
1396 : /* Return true if accesses based on any other base value cannot alias
1397 : those based on X. */
1398 :
1399 : static bool
1400 163321208 : unique_base_value_p (rtx x)
1401 : {
1402 190274617 : return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode;
1403 : }
1404 :
1405 : /* Inside SRC, the source of a SET, find a base address. */
1406 :
1407 : static rtx
1408 429407800 : find_base_value (rtx src)
1409 : {
1410 513547097 : unsigned int regno;
1411 513547097 : scalar_int_mode int_mode;
1412 :
1413 : #if defined (FIND_BASE_TERM)
1414 : /* Try machine-dependent ways to find the base term. */
1415 513547097 : src = FIND_BASE_TERM (src);
1416 : #endif
1417 :
1418 513547097 : switch (GET_CODE (src))
1419 : {
1420 : case SYMBOL_REF:
1421 : case LABEL_REF:
1422 : return src;
1423 :
1424 164552832 : case REG:
1425 164552832 : regno = REGNO (src);
1426 : /* At the start of a function, argument registers have known base
1427 : values which may be lost later. Returning an ADDRESS
1428 : expression here allows optimization based on argument values
1429 : even when the argument registers are used for other purposes. */
1430 164552832 : if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1431 18626800 : return new_reg_base_value[regno];
1432 :
1433 : /* If a pseudo has a known base value, return it. Do not do this
1434 : for non-fixed hard regs since it can result in a circular
1435 : dependency chain for registers which have values at function entry.
1436 :
1437 : The test above is not sufficient because the scheduler may move
1438 : a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1439 86083133 : if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1440 118403070 : && regno < vec_safe_length (reg_base_value))
1441 : {
1442 : /* If we're inside init_alias_analysis, use new_reg_base_value
1443 : to reduce the number of relaxation iterations. */
1444 118403070 : if (new_reg_base_value && new_reg_base_value[regno]
1445 78720208 : && DF_REG_DEF_COUNT (regno) == 1)
1446 : return new_reg_base_value[regno];
1447 :
1448 84513218 : if ((*reg_base_value)[regno])
1449 : return (*reg_base_value)[regno];
1450 : }
1451 :
1452 : return 0;
1453 :
1454 101079131 : case MEM:
1455 : /* Check for an argument passed in memory. Only record in the
1456 : copying-arguments block; it is too hard to track changes
1457 : otherwise. */
1458 101079131 : if (copying_arguments
1459 3872088 : && (XEXP (src, 0) == arg_pointer_rtx
1460 2717664 : || (GET_CODE (XEXP (src, 0)) == PLUS
1461 2703533 : && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1462 2809678 : return arg_base_value;
1463 : return 0;
1464 :
1465 985194 : case CONST:
1466 985194 : src = XEXP (src, 0);
1467 985194 : if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1468 : break;
1469 :
1470 : /* fall through */
1471 :
1472 105197489 : case PLUS:
1473 105197489 : case MINUS:
1474 105197489 : {
1475 105197489 : rtx src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1476 :
1477 : /* If either operand is a CONST_INT, then the other is the base. */
1478 105197489 : if (CONST_INT_P (src_1))
1479 : return find_base_value (src_0);
1480 22994114 : else if (CONST_INT_P (src_0))
1481 : return find_base_value (src_1);
1482 :
1483 : return 0;
1484 : }
1485 :
1486 0 : case LO_SUM:
1487 : /* The standard form is (lo_sum reg sym) so look only at the
1488 : second operand. */
1489 0 : return find_base_value (XEXP (src, 1));
1490 :
1491 6130281 : case AND:
1492 : /* Look through aligning ANDs. And AND with zero or one with
1493 : the LSB set isn't one (see for example PR92462). */
1494 6130281 : if (CONST_INT_P (XEXP (src, 1))
1495 4169437 : && INTVAL (XEXP (src, 1)) != 0
1496 4139835 : && (INTVAL (XEXP (src, 1)) & 1) == 0)
1497 1840181 : return find_base_value (XEXP (src, 0));
1498 : return 0;
1499 :
1500 13117 : case TRUNCATE:
1501 : /* As we do not know which address space the pointer is referring to, we can
1502 : handle this only if the target does not support different pointer or
1503 : address modes depending on the address space. */
1504 13117 : if (!target_default_pointer_address_modes_p ())
1505 : break;
1506 13117 : if (!is_a <scalar_int_mode> (GET_MODE (src), &int_mode)
1507 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1508 : break;
1509 : /* Fall through. */
1510 0 : case HIGH:
1511 0 : case PRE_INC:
1512 0 : case PRE_DEC:
1513 0 : case POST_INC:
1514 0 : case POST_DEC:
1515 0 : case PRE_MODIFY:
1516 0 : case POST_MODIFY:
1517 0 : return find_base_value (XEXP (src, 0));
1518 :
1519 11092662 : case ZERO_EXTEND:
1520 11092662 : case SIGN_EXTEND: /* used for NT/Alpha pointers */
1521 : /* As we do not know which address space the pointer is referring to, we can
1522 : handle this only if the target does not support different pointer or
1523 : address modes depending on the address space. */
1524 11092662 : if (!target_default_pointer_address_modes_p ())
1525 : break;
1526 :
1527 11092662 : {
1528 11092662 : rtx temp = find_base_value (XEXP (src, 0));
1529 :
1530 11092662 : if (temp != 0 && CONSTANT_P (temp))
1531 286 : temp = convert_memory_address (Pmode, temp);
1532 :
1533 : return temp;
1534 : }
1535 :
1536 : default:
1537 : break;
1538 : }
1539 :
1540 : return 0;
1541 : }
1542 :
1543 : /* Called from init_alias_analysis indirectly through note_stores,
1544 : or directly if DEST is a register with a REG_NOALIAS note attached.
1545 : SET is null in the latter case. */
1546 :
1547 : /* While scanning insns to find base values, reg_seen[N] is nonzero if
1548 : register N has been set in this function. */
1549 : static sbitmap reg_seen;
1550 :
1551 : static void
1552 1382817526 : record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1553 : {
1554 1382817526 : unsigned regno;
1555 1382817526 : rtx src;
1556 1382817526 : int n;
1557 :
1558 1382817526 : if (!REG_P (dest))
1559 : return;
1560 :
1561 1047732502 : regno = REGNO (dest);
1562 :
1563 1047732502 : gcc_checking_assert (regno < reg_base_value->length ());
1564 :
1565 1047732502 : n = REG_NREGS (dest);
1566 1047732502 : if (n != 1)
1567 : {
1568 15162672 : while (--n >= 0)
1569 : {
1570 10108448 : bitmap_set_bit (reg_seen, regno + n);
1571 10108448 : new_reg_base_value[regno + n] = 0;
1572 : }
1573 : return;
1574 : }
1575 :
1576 1042678278 : if (set)
1577 : {
1578 : /* A CLOBBER wipes out any old value but does not prevent a previously
1579 : unset register from acquiring a base address (i.e. reg_seen is not
1580 : set). */
1581 1041154196 : if (GET_CODE (set) == CLOBBER)
1582 : {
1583 181105488 : new_reg_base_value[regno] = 0;
1584 181105488 : return;
1585 : }
1586 :
1587 860048708 : src = SET_SRC (set);
1588 : }
1589 : else
1590 : {
1591 : /* There's a REG_NOALIAS note against DEST. */
1592 1524082 : if (bitmap_bit_p (reg_seen, regno))
1593 : {
1594 481508 : new_reg_base_value[regno] = 0;
1595 481508 : return;
1596 : }
1597 1042574 : bitmap_set_bit (reg_seen, regno);
1598 1042574 : new_reg_base_value[regno] = unique_base_value (unique_id++);
1599 1042574 : return;
1600 : }
1601 :
1602 : /* If this is not the first set of REGNO, see whether the new value
1603 : is related to the old one. There are two cases of interest:
1604 :
1605 : (1) The register might be assigned an entirely new value
1606 : that has the same base term as the original set.
1607 :
1608 : (2) The set might be a simple self-modification that
1609 : cannot change REGNO's base value.
1610 :
1611 : If neither case holds, reject the original base value as invalid.
1612 : Note that the following situation is not detected:
1613 :
1614 : extern int x, y; int *p = &x; p += (&y-&x);
1615 :
1616 : ANSI C does not allow computing the difference of addresses
1617 : of distinct top level objects. */
1618 860048708 : if (new_reg_base_value[regno] != 0
1619 860048708 : && find_base_value (src) != new_reg_base_value[regno])
1620 75637450 : switch (GET_CODE (src))
1621 : {
1622 456771 : case LO_SUM:
1623 456771 : case MINUS:
1624 456771 : if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1625 64160 : new_reg_base_value[regno] = 0;
1626 : break;
1627 22889541 : case PLUS:
1628 : /* If the value we add in the PLUS is also a valid base value,
1629 : this might be the actual base value, and the original value
1630 : an index. */
1631 22889541 : {
1632 22889541 : rtx other = NULL_RTX;
1633 :
1634 22889541 : if (XEXP (src, 0) == dest)
1635 19853133 : other = XEXP (src, 1);
1636 3036408 : else if (XEXP (src, 1) == dest)
1637 : other = XEXP (src, 0);
1638 :
1639 19938977 : if (! other || find_base_value (other))
1640 2955635 : new_reg_base_value[regno] = 0;
1641 : break;
1642 : }
1643 59698 : case AND:
1644 59698 : if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1645 52961 : new_reg_base_value[regno] = 0;
1646 : break;
1647 52231440 : default:
1648 52231440 : new_reg_base_value[regno] = 0;
1649 52231440 : break;
1650 : }
1651 : /* If this is the first set of a register, record the value. */
1652 460959459 : else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1653 1110582380 : && ! bitmap_bit_p (reg_seen, regno) && new_reg_base_value[regno] == 0)
1654 289452313 : new_reg_base_value[regno] = find_base_value (src);
1655 :
1656 860048708 : bitmap_set_bit (reg_seen, regno);
1657 : }
1658 :
1659 : /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1660 : using hard registers with non-null REG_BASE_VALUE for renaming. */
1661 : rtx
1662 1474 : get_reg_base_value (unsigned int regno)
1663 : {
1664 1474 : return (*reg_base_value)[regno];
1665 : }
1666 :
1667 : /* If a value is known for REGNO, return it. */
1668 :
1669 : rtx
1670 298151621 : get_reg_known_value (unsigned int regno)
1671 : {
1672 298151621 : if (regno >= FIRST_PSEUDO_REGISTER)
1673 : {
1674 282770179 : regno -= FIRST_PSEUDO_REGISTER;
1675 282770179 : if (regno < vec_safe_length (reg_known_value))
1676 263235341 : return (*reg_known_value)[regno];
1677 : }
1678 : return NULL;
1679 : }
1680 :
1681 : /* Set it. */
1682 :
1683 : static void
1684 524017776 : set_reg_known_value (unsigned int regno, rtx val)
1685 : {
1686 524017776 : if (regno >= FIRST_PSEUDO_REGISTER)
1687 : {
1688 524017776 : regno -= FIRST_PSEUDO_REGISTER;
1689 524017776 : if (regno < vec_safe_length (reg_known_value))
1690 524017776 : (*reg_known_value)[regno] = val;
1691 : }
1692 524017776 : }
1693 :
1694 : /* Similarly for reg_known_equiv_p. */
1695 :
1696 : bool
1697 40690 : get_reg_known_equiv_p (unsigned int regno)
1698 : {
1699 40690 : if (regno >= FIRST_PSEUDO_REGISTER)
1700 : {
1701 40690 : regno -= FIRST_PSEUDO_REGISTER;
1702 40690 : if (regno < vec_safe_length (reg_known_value))
1703 40068 : return bitmap_bit_p (reg_known_equiv_p, regno);
1704 : }
1705 : return false;
1706 : }
1707 :
1708 : static void
1709 41068845 : set_reg_known_equiv_p (unsigned int regno, bool val)
1710 : {
1711 41068845 : if (regno >= FIRST_PSEUDO_REGISTER)
1712 : {
1713 41068845 : regno -= FIRST_PSEUDO_REGISTER;
1714 41068845 : if (regno < vec_safe_length (reg_known_value))
1715 : {
1716 41068845 : if (val)
1717 0 : bitmap_set_bit (reg_known_equiv_p, regno);
1718 : else
1719 41068845 : bitmap_clear_bit (reg_known_equiv_p, regno);
1720 : }
1721 : }
1722 41068845 : }
1723 :
1724 :
1725 : /* Returns a canonical version of X, from the point of view alias
1726 : analysis. (For example, if X is a MEM whose address is a register,
1727 : and the register has a known value (say a SYMBOL_REF), then a MEM
1728 : whose address is the SYMBOL_REF is returned.) */
1729 :
1730 : rtx
1731 5529888833 : canon_rtx (rtx x)
1732 : {
1733 : /* Recursively look for equivalences. */
1734 5533960431 : if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1735 : {
1736 254403371 : rtx t = get_reg_known_value (REGNO (x));
1737 254403371 : if (t == x)
1738 : return x;
1739 23606436 : if (t)
1740 : return canon_rtx (t);
1741 : }
1742 :
1743 5299091898 : if (GET_CODE (x) == PLUS)
1744 : {
1745 1549532302 : rtx x0 = canon_rtx (XEXP (x, 0));
1746 1549532302 : rtx x1 = canon_rtx (XEXP (x, 1));
1747 :
1748 1549532302 : if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1749 3192367 : return simplify_gen_binary (PLUS, GET_MODE (x), x0, x1);
1750 : }
1751 :
1752 : /* This gives us much better alias analysis when called from
1753 : the loop optimizer. Note we want to leave the original
1754 : MEM alone, but need to return the canonicalized MEM with
1755 : all the flags with their original values. */
1756 3749559596 : else if (MEM_P (x))
1757 327622247 : x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1758 :
1759 : return x;
1760 : }
1761 :
1762 : /* Return true if X and Y are identical-looking rtx's.
1763 : Expect that X and Y has been already canonicalized.
1764 :
1765 : We use the data in reg_known_value above to see if two registers with
1766 : different numbers are, in fact, equivalent. */
1767 :
1768 : static bool
1769 8799708770 : rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1770 : {
1771 8799807080 : int i;
1772 8799807080 : int j;
1773 8799807080 : enum rtx_code code;
1774 8799807080 : const char *fmt;
1775 :
1776 8799807080 : if (x == 0 && y == 0)
1777 : return true;
1778 8799807080 : if (x == 0 || y == 0)
1779 : return false;
1780 :
1781 8799807080 : if (x == y)
1782 : return true;
1783 :
1784 7089496157 : code = GET_CODE (x);
1785 : /* Rtx's of different codes cannot be equal. */
1786 7089496157 : if (code != GET_CODE (y))
1787 : return false;
1788 :
1789 : /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1790 : (REG:SI x) and (REG:HI x) are NOT equivalent. */
1791 :
1792 4806493911 : if (GET_MODE (x) != GET_MODE (y))
1793 : return false;
1794 :
1795 : /* Some RTL can be compared without a recursive examination. */
1796 4806493651 : switch (code)
1797 : {
1798 253661028 : case REG:
1799 253661028 : return REGNO (x) == REGNO (y);
1800 :
1801 0 : case LABEL_REF:
1802 0 : return label_ref_label (x) == label_ref_label (y);
1803 :
1804 3759615 : case SYMBOL_REF:
1805 3759615 : {
1806 3759615 : HOST_WIDE_INT distance = 0;
1807 3759615 : return (compare_base_symbol_refs (x, y, &distance) == 1
1808 3759615 : && distance == 0);
1809 : }
1810 :
1811 2043844 : case ENTRY_VALUE:
1812 : /* This is magic, don't go through canonicalization et al. */
1813 2043844 : return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1814 :
1815 : case VALUE:
1816 : CASE_CONST_UNIQUE:
1817 : /* Pointer equality guarantees equality for these nodes. */
1818 : return false;
1819 :
1820 1389299993 : default:
1821 1389299993 : break;
1822 : }
1823 :
1824 : /* canon_rtx knows how to handle plus. No need to canonicalize. */
1825 1389299993 : if (code == PLUS)
1826 1365556983 : return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1827 656219309 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1828 2012339861 : || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1829 218791 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1830 : /* For commutative operations, the RTX match if the operand match in any
1831 : order. Also handle the simple binary and unary cases without a loop. */
1832 23743010 : if (COMMUTATIVE_P (x))
1833 : {
1834 4439460 : rtx xop0 = canon_rtx (XEXP (x, 0));
1835 4439460 : rtx yop0 = canon_rtx (XEXP (y, 0));
1836 4439460 : rtx yop1 = canon_rtx (XEXP (y, 1));
1837 :
1838 4439460 : return ((rtx_equal_for_memref_p (xop0, yop0)
1839 1517578 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1840 4566496 : || (rtx_equal_for_memref_p (xop0, yop1)
1841 20 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1842 : }
1843 19303550 : else if (NON_COMMUTATIVE_P (x))
1844 : {
1845 125221 : return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1846 125221 : canon_rtx (XEXP (y, 0)))
1847 163802 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1848 38581 : canon_rtx (XEXP (y, 1))));
1849 : }
1850 19178329 : else if (UNARY_P (x))
1851 98310 : return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1852 196620 : canon_rtx (XEXP (y, 0)));
1853 :
1854 : /* Compare the elements. If any pair of corresponding elements
1855 : fail to match, return false for the whole things.
1856 :
1857 : Limit cases to types which actually appear in addresses. */
1858 :
1859 19080019 : fmt = GET_RTX_FORMAT (code);
1860 26331459 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1861 : {
1862 25760970 : switch (fmt[i])
1863 : {
1864 3414421 : case 'i':
1865 3414421 : if (XINT (x, i) != XINT (y, i))
1866 : return false;
1867 : break;
1868 :
1869 152 : case 'L':
1870 152 : if (XLOC (x, i) != XLOC (y, i))
1871 : return false;
1872 : break;
1873 :
1874 36 : case 'p':
1875 36 : if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1876 : return false;
1877 : break;
1878 :
1879 3414373 : case 'E':
1880 : /* Two vectors must have the same length. */
1881 3414373 : if (XVECLEN (x, i) != XVECLEN (y, i))
1882 : return false;
1883 :
1884 : /* And the corresponding elements must match. */
1885 3680392 : for (j = 0; j < XVECLEN (x, i); j++)
1886 3415296 : if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1887 3415296 : canon_rtx (XVECEXP (y, i, j))) == 0)
1888 : return false;
1889 : break;
1890 :
1891 15753567 : case 'e':
1892 15753567 : if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1893 15753567 : canon_rtx (XEXP (y, i))) == 0)
1894 : return false;
1895 : break;
1896 :
1897 : /* This can happen for asm operands. */
1898 0 : case 's':
1899 0 : if (strcmp (XSTR (x, i), XSTR (y, i)))
1900 : return false;
1901 : break;
1902 :
1903 : /* This can happen for an asm which clobbers memory. */
1904 : case '0':
1905 : break;
1906 :
1907 : /* It is believed that rtx's at this level will never
1908 : contain anything but integers and other rtx's,
1909 : except for within LABEL_REFs and SYMBOL_REFs. */
1910 0 : default:
1911 0 : gcc_unreachable ();
1912 : }
1913 : }
1914 : return true;
1915 : }
1916 :
1917 : static rtx
1918 3251654166 : find_base_term (rtx x, vec<std::pair<cselib_val *,
1919 : struct elt_loc_list *> > &visited_vals)
1920 : {
1921 6142556699 : cselib_val *val;
1922 6142556699 : struct elt_loc_list *l, *f;
1923 6142556699 : rtx ret;
1924 6142556699 : scalar_int_mode int_mode;
1925 :
1926 : #if defined (FIND_BASE_TERM)
1927 : /* Try machine-dependent ways to find the base term. */
1928 6142556699 : x = FIND_BASE_TERM (x);
1929 : #endif
1930 :
1931 6142556699 : switch (GET_CODE (x))
1932 : {
1933 2151349489 : case REG:
1934 2151349489 : return REG_BASE_VALUE (x);
1935 :
1936 0 : case TRUNCATE:
1937 : /* As we do not know which address space the pointer is referring to, we can
1938 : handle this only if the target does not support different pointer or
1939 : address modes depending on the address space. */
1940 0 : if (!target_default_pointer_address_modes_p ())
1941 : return 0;
1942 119303306 : if (!is_a <scalar_int_mode> (GET_MODE (x), &int_mode)
1943 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1944 : return 0;
1945 : /* Fall through. */
1946 42980504 : case HIGH:
1947 42980504 : case PRE_INC:
1948 42980504 : case PRE_DEC:
1949 42980504 : case POST_INC:
1950 42980504 : case POST_DEC:
1951 42980504 : case PRE_MODIFY:
1952 42980504 : case POST_MODIFY:
1953 42980504 : return find_base_term (XEXP (x, 0), visited_vals);
1954 :
1955 482 : case ZERO_EXTEND:
1956 482 : case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1957 : /* As we do not know which address space the pointer is referring to, we can
1958 : handle this only if the target does not support different pointer or
1959 : address modes depending on the address space. */
1960 482 : if (!target_default_pointer_address_modes_p ())
1961 : return 0;
1962 :
1963 482 : {
1964 482 : rtx temp = find_base_term (XEXP (x, 0), visited_vals);
1965 :
1966 482 : if (temp != 0 && CONSTANT_P (temp))
1967 0 : temp = convert_memory_address (Pmode, temp);
1968 :
1969 : return temp;
1970 : }
1971 :
1972 836238435 : case VALUE:
1973 836238435 : val = CSELIB_VAL_PTR (x);
1974 836238435 : ret = NULL_RTX;
1975 :
1976 836238435 : if (!val)
1977 : return ret;
1978 :
1979 836238435 : if (cselib_sp_based_value_p (val))
1980 21617673 : return static_reg_base_value[STACK_POINTER_REGNUM];
1981 :
1982 814620762 : if (visited_vals.length () > (unsigned) param_max_find_base_term_values)
1983 : return ret;
1984 :
1985 812619668 : f = val->locs;
1986 : /* Reset val->locs to avoid infinite recursion. */
1987 812619668 : if (f)
1988 648975277 : visited_vals.safe_push (std::make_pair (val, f));
1989 812619668 : val->locs = NULL;
1990 :
1991 1444879306 : for (l = f; l; l = l->next)
1992 809027244 : if (GET_CODE (l->loc) == VALUE
1993 108476179 : && CSELIB_VAL_PTR (l->loc)->locs
1994 108428957 : && !CSELIB_VAL_PTR (l->loc)->locs->next
1995 108385491 : && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
1996 108385491 : continue;
1997 700641753 : else if ((ret = find_base_term (l->loc, visited_vals)) != 0)
1998 : break;
1999 :
2000 : return ret;
2001 :
2002 0 : case LO_SUM:
2003 : /* The standard form is (lo_sum reg sym) so look only at the
2004 : second operand. */
2005 0 : return find_base_term (XEXP (x, 1), visited_vals);
2006 :
2007 45453160 : case CONST:
2008 45453160 : x = XEXP (x, 0);
2009 45453160 : if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
2010 : return 0;
2011 : /* Fall through. */
2012 2863071514 : case PLUS:
2013 2863071514 : case MINUS:
2014 2863071514 : {
2015 2863071514 : rtx tmp1 = XEXP (x, 0);
2016 2863071514 : rtx tmp2 = XEXP (x, 1);
2017 :
2018 : /* This is a little bit tricky since we have to determine which of
2019 : the two operands represents the real base address. Otherwise this
2020 : routine may return the index register instead of the base register.
2021 :
2022 : That may cause us to believe no aliasing was possible, when in
2023 : fact aliasing is possible.
2024 :
2025 : We use a few simple tests to guess the base register. Additional
2026 : tests can certainly be added. For example, if one of the operands
2027 : is a shift or multiply, then it must be the index register and the
2028 : other operand is the base register. */
2029 :
2030 2863071514 : if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
2031 : return find_base_term (tmp2, visited_vals);
2032 :
2033 2863071510 : if (CONST_INT_P (tmp1))
2034 0 : std::swap (tmp1, tmp2);
2035 :
2036 : /* We can only handle binary operators when one of the operands
2037 : never leads to a base value. */
2038 2863071510 : if (CONST_INT_P (tmp2))
2039 : return find_base_term (tmp1, visited_vals);
2040 :
2041 : /* We could not determine which of the two operands was the
2042 : base register and which was the index. So we can determine
2043 : nothing from the base alias check. */
2044 : return 0;
2045 : }
2046 :
2047 58438776 : case AND:
2048 : /* Look through aligning ANDs. And AND with zero or one with
2049 : the LSB set isn't one (see for example PR92462). */
2050 58438776 : if (CONST_INT_P (XEXP (x, 1))
2051 58438693 : && INTVAL (XEXP (x, 1)) != 0
2052 58438693 : && (INTVAL (XEXP (x, 1)) & 1) == 0)
2053 58438689 : return find_base_term (XEXP (x, 0), visited_vals);
2054 : return 0;
2055 :
2056 : case SYMBOL_REF:
2057 : case LABEL_REF:
2058 : return x;
2059 :
2060 : default:
2061 : return 0;
2062 : }
2063 : }
2064 :
2065 : /* Wrapper around the worker above which removes locs from visited VALUEs
2066 : to avoid visiting them multiple times. We unwind that changes here. */
2067 :
2068 : static rtx
2069 2551011931 : find_base_term (rtx x)
2070 : {
2071 2551011931 : auto_vec<std::pair<cselib_val *, struct elt_loc_list *>, 32> visited_vals;
2072 2551011931 : rtx res = find_base_term (x, visited_vals);
2073 3199987208 : for (unsigned i = 0; i < visited_vals.length (); ++i)
2074 648975277 : visited_vals[i].first->locs = visited_vals[i].second;
2075 2551011931 : return res;
2076 2551011931 : }
2077 :
2078 : /* Return true if accesses to address X may alias accesses based
2079 : on the stack pointer. */
2080 :
2081 : bool
2082 15168272 : may_be_sp_based_p (rtx x)
2083 : {
2084 15168272 : rtx base = find_base_term (x);
2085 15168272 : return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
2086 : }
2087 :
2088 : /* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2089 : if they refer to different objects and -1 if we cannot decide. */
2090 :
2091 : int
2092 1513638161 : compare_base_decls (tree base1, tree base2)
2093 : {
2094 1513638161 : int ret;
2095 1513638161 : gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2096 1513638161 : if (base1 == base2)
2097 : return 1;
2098 :
2099 : /* If we have two register decls with register specification we
2100 : cannot decide unless their assembler names are the same. */
2101 1305962596 : if (VAR_P (base1)
2102 1255503190 : && VAR_P (base2)
2103 1249758478 : && DECL_HARD_REGISTER (base1)
2104 12714 : && DECL_HARD_REGISTER (base2)
2105 12555 : && DECL_ASSEMBLER_NAME_SET_P (base1)
2106 1305975151 : && DECL_ASSEMBLER_NAME_SET_P (base2))
2107 : {
2108 12555 : if (DECL_ASSEMBLER_NAME_RAW (base1) == DECL_ASSEMBLER_NAME_RAW (base2))
2109 : return 1;
2110 12552 : return -1;
2111 : }
2112 :
2113 : /* Declarations of non-automatic variables may have aliases. All other
2114 : decls are unique. */
2115 1305950041 : if (!decl_in_symtab_p (base1)
2116 1305950041 : || !decl_in_symtab_p (base2))
2117 : return 0;
2118 :
2119 : /* Don't cause symbols to be inserted by the act of checking. */
2120 84976354 : symtab_node *node1 = symtab_node::get (base1);
2121 84976354 : if (!node1)
2122 : return 0;
2123 84956928 : symtab_node *node2 = symtab_node::get (base2);
2124 84956928 : if (!node2)
2125 : return 0;
2126 :
2127 84938235 : ret = node1->equal_address_to (node2, true);
2128 84938235 : return ret;
2129 : }
2130 :
2131 : /* Compare SYMBOL_REFs X_BASE and Y_BASE.
2132 :
2133 : - Return 1 if Y_BASE - X_BASE is constant, adding that constant
2134 : to *DISTANCE if DISTANCE is nonnull.
2135 :
2136 : - Return 0 if no accesses based on X_BASE can alias Y_BASE.
2137 :
2138 : - Return -1 if one of the two results applies, but we can't tell
2139 : which at compile time. Update DISTANCE in the same way as
2140 : for a return value of 1, for the case in which that holds. */
2141 :
2142 : static int
2143 23255797 : compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
2144 : HOST_WIDE_INT *distance)
2145 : {
2146 23255797 : tree x_decl = SYMBOL_REF_DECL (x_base);
2147 23255797 : tree y_decl = SYMBOL_REF_DECL (y_base);
2148 23255797 : bool binds_def = true;
2149 23255797 : bool swap = false;
2150 :
2151 23255797 : if (XSTR (x_base, 0) == XSTR (y_base, 0))
2152 : return 1;
2153 22872990 : if (x_decl && y_decl)
2154 22872990 : return compare_base_decls (x_decl, y_decl);
2155 0 : if (x_decl || y_decl)
2156 : {
2157 : if (!x_decl)
2158 : {
2159 : swap = true;
2160 : std::swap (x_decl, y_decl);
2161 : std::swap (x_base, y_base);
2162 : }
2163 : /* We handle specially only section anchors. Other symbols are
2164 : either equal (via aliasing) or refer to different objects. */
2165 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2166 : return -1;
2167 : /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2168 : to ignore CONST_DECLs because they are readonly. */
2169 0 : if (!VAR_P (x_decl)
2170 0 : || (!TREE_STATIC (x_decl) && !TREE_PUBLIC (x_decl)))
2171 : return 0;
2172 :
2173 0 : symtab_node *x_node = symtab_node::get_create (x_decl)
2174 0 : ->ultimate_alias_target ();
2175 : /* External variable cannot be in section anchor. */
2176 0 : if (!x_node->definition)
2177 : return 0;
2178 0 : x_base = XEXP (DECL_RTL (x_node->decl), 0);
2179 : /* If not in anchor, we can disambiguate. */
2180 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base))
2181 : return 0;
2182 :
2183 : /* We have an alias of anchored variable. If it can be interposed;
2184 : we must assume it may or may not alias its anchor. */
2185 0 : binds_def = decl_binds_to_current_def_p (x_decl);
2186 : }
2187 : /* If we have variable in section anchor, we can compare by offset. */
2188 0 : if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base)
2189 0 : && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2190 : {
2191 0 : if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
2192 : return 0;
2193 0 : if (distance)
2194 0 : *distance += (swap ? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base)
2195 0 : - SYMBOL_REF_BLOCK_OFFSET (x_base));
2196 0 : return binds_def ? 1 : -1;
2197 : }
2198 : /* Either the symbols are equal (via aliasing) or they refer to
2199 : different objects. */
2200 : return -1;
2201 : }
2202 :
2203 : /* Return false if the addresses X and Y are known to point to different
2204 : objects, true if they might be pointers to the same object. */
2205 :
2206 : static bool
2207 1267801436 : base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base,
2208 : machine_mode x_mode, machine_mode y_mode)
2209 : {
2210 : /* If the address itself has no known base see if a known equivalent
2211 : value has one. If either address still has no known base, nothing
2212 : is known about aliasing. */
2213 1267801436 : if (x_base == 0)
2214 : {
2215 170467070 : rtx x_c;
2216 :
2217 170467070 : if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
2218 170264470 : return true;
2219 :
2220 202600 : x_base = find_base_term (x_c);
2221 202600 : if (x_base == 0)
2222 : return true;
2223 : }
2224 :
2225 1097336770 : if (y_base == 0)
2226 : {
2227 169393204 : rtx y_c;
2228 169393204 : if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
2229 169356685 : return true;
2230 :
2231 36519 : y_base = find_base_term (y_c);
2232 36519 : if (y_base == 0)
2233 : return true;
2234 : }
2235 :
2236 : /* If the base addresses are equal nothing is known about aliasing. */
2237 927946568 : if (rtx_equal_p (x_base, y_base))
2238 : return true;
2239 :
2240 : /* The base addresses are different expressions. If they are not accessed
2241 : via AND, there is no conflict. We can bring knowledge of object
2242 : alignment into play here. For example, on alpha, "char a, b;" can
2243 : alias one another, though "char a; long b;" cannot. AND addresses may
2244 : implicitly alias surrounding objects; i.e. unaligned access in DImode
2245 : via AND address can alias all surrounding object types except those
2246 : with aligment 8 or higher. */
2247 141051011 : if (GET_CODE (x) == AND && GET_CODE (y) == AND)
2248 : return true;
2249 141051011 : if (GET_CODE (x) == AND
2250 141051011 : && (!CONST_INT_P (XEXP (x, 1))
2251 1979 : || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
2252 : return true;
2253 141049232 : if (GET_CODE (y) == AND
2254 141049232 : && (!CONST_INT_P (XEXP (y, 1))
2255 1980 : || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
2256 : return true;
2257 :
2258 : /* Differing symbols not accessed via AND never alias. */
2259 141047342 : if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF)
2260 18966606 : return compare_base_symbol_refs (x_base, y_base) != 0;
2261 :
2262 122080736 : if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
2263 : return false;
2264 :
2265 132419123 : if (unique_base_value_p (x_base) || unique_base_value_p (y_base))
2266 : return false;
2267 :
2268 : return true;
2269 : }
2270 :
2271 : /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2272 : (or equal to) that of V. */
2273 :
2274 : static bool
2275 214156472 : refs_newer_value_p (const_rtx expr, rtx v)
2276 : {
2277 214156472 : int minuid = CSELIB_VAL_PTR (v)->uid;
2278 214156472 : subrtx_iterator::array_type array;
2279 629260458 : FOR_EACH_SUBRTX (iter, array, expr, NONCONST)
2280 529287820 : if (GET_CODE (*iter) == VALUE && CSELIB_VAL_PTR (*iter)->uid >= minuid)
2281 114183834 : return true;
2282 99972638 : return false;
2283 214156472 : }
2284 :
2285 : /* Convert the address X into something we can use. This is done by returning
2286 : it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2287 : we call cselib to get a more useful rtx. */
2288 :
2289 : rtx
2290 3886152739 : get_addr (rtx x)
2291 : {
2292 3886152739 : cselib_val *v;
2293 3886152739 : struct elt_loc_list *l;
2294 :
2295 3886152739 : if (GET_CODE (x) != VALUE)
2296 : {
2297 2498972843 : if ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
2298 2098218649 : && GET_CODE (XEXP (x, 0)) == VALUE
2299 119232408 : && CONST_SCALAR_INT_P (XEXP (x, 1)))
2300 : {
2301 112037101 : rtx op0 = get_addr (XEXP (x, 0));
2302 112037101 : if (op0 != XEXP (x, 0))
2303 : {
2304 31026816 : poly_int64 c;
2305 31026816 : if (GET_CODE (x) == PLUS
2306 31026816 : && poly_int_rtx_p (XEXP (x, 1), &c))
2307 31026816 : return plus_constant (GET_MODE (x), op0, c);
2308 0 : return simplify_gen_binary (GET_CODE (x), GET_MODE (x),
2309 0 : op0, XEXP (x, 1));
2310 : }
2311 : }
2312 2467946027 : return x;
2313 : }
2314 1387179896 : v = CSELIB_VAL_PTR (x);
2315 1387179896 : if (v)
2316 : {
2317 1387179896 : bool have_equivs = cselib_have_permanent_equivalences ();
2318 1387179896 : if (have_equivs)
2319 333423563 : v = canonical_cselib_val (v);
2320 2673280043 : for (l = v->locs; l; l = l->next)
2321 1313979973 : if (CONSTANT_P (l->loc))
2322 : return l->loc;
2323 1598212286 : for (l = v->locs; l; l = l->next)
2324 1208489621 : if (!REG_P (l->loc) && !MEM_P (l->loc)
2325 : /* Avoid infinite recursion when potentially dealing with
2326 : var-tracking artificial equivalences, by skipping the
2327 : equivalences themselves, and not choosing expressions
2328 : that refer to newer VALUEs. */
2329 2487674753 : && (!have_equivs
2330 254875062 : || (GET_CODE (l->loc) != VALUE
2331 156179882 : && !refs_newer_value_p (l->loc, x))))
2332 1046478319 : return l->loc;
2333 312821751 : if (have_equivs)
2334 : {
2335 341710468 : for (l = v->locs; l; l = l->next)
2336 120606406 : if (REG_P (l->loc)
2337 120606406 : || (GET_CODE (l->loc) != VALUE
2338 57976590 : && !refs_newer_value_p (l->loc, x)))
2339 6615956 : return l->loc;
2340 : /* Return the canonical value. */
2341 221104062 : return v->val_rtx;
2342 : }
2343 85101733 : if (v->locs)
2344 47014310 : return v->locs->loc;
2345 : }
2346 : return x;
2347 : }
2348 :
2349 : /* Return the address of the (N_REFS + 1)th memory reference to ADDR
2350 : where SIZE is the size in bytes of the memory reference. If ADDR
2351 : is not modified by the memory reference then ADDR is returned. */
2352 :
2353 : static rtx
2354 5386368532 : addr_side_effect_eval (rtx addr, poly_int64 size, int n_refs)
2355 : {
2356 5386368532 : poly_int64 offset = 0;
2357 :
2358 5386368532 : switch (GET_CODE (addr))
2359 : {
2360 0 : case PRE_INC:
2361 0 : offset = (n_refs + 1) * size;
2362 0 : break;
2363 22106712 : case PRE_DEC:
2364 22106712 : offset = -(n_refs + 1) * size;
2365 22106712 : break;
2366 : case POST_INC:
2367 499915 : offset = n_refs * size;
2368 499915 : break;
2369 0 : case POST_DEC:
2370 0 : offset = -n_refs * size;
2371 0 : break;
2372 :
2373 : default:
2374 : return addr;
2375 : }
2376 :
2377 22606627 : addr = plus_constant (GET_MODE (addr), XEXP (addr, 0), offset);
2378 22606627 : addr = canon_rtx (addr);
2379 :
2380 22606627 : return addr;
2381 : }
2382 :
2383 : /* Return TRUE if an object X sized at XSIZE bytes and another object
2384 : Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2385 : any of the sizes is zero, assume an overlap, otherwise use the
2386 : absolute value of the sizes as the actual sizes. */
2387 :
2388 : static inline bool
2389 815337941 : offset_overlap_p (poly_int64 c, poly_int64 xsize, poly_int64 ysize)
2390 : {
2391 814710761 : if (known_eq (xsize, 0) || known_eq (ysize, 0))
2392 : return true;
2393 :
2394 811883739 : if (maybe_ge (c, 0))
2395 489993643 : return maybe_gt (maybe_lt (xsize, 0) ? -xsize : xsize, c);
2396 : else
2397 321890096 : return maybe_gt (maybe_lt (ysize, 0) ? -ysize : ysize, -c);
2398 : }
2399 :
2400 : /* Return one if X and Y (memory addresses) reference the
2401 : same location in memory or if the references overlap.
2402 : Return zero if they do not overlap, else return
2403 : minus one in which case they still might reference the same location.
2404 :
2405 : C is an offset accumulator. When
2406 : C is nonzero, we are testing aliases between X and Y + C.
2407 : XSIZE is the size in bytes of the X reference,
2408 : similarly YSIZE is the size in bytes for Y.
2409 : Expect that canon_rtx has been already called for X and Y.
2410 :
2411 : If XSIZE or YSIZE is zero, we do not know the amount of memory being
2412 : referenced (the reference was BLKmode), so make the most pessimistic
2413 : assumptions.
2414 :
2415 : If XSIZE or YSIZE is negative, we may access memory outside the object
2416 : being referenced as a side effect. This can happen when using AND to
2417 : align memory references, as is done on the Alpha.
2418 :
2419 : Nice to notice that varying addresses cannot conflict with fp if no
2420 : local variables had their addresses taken, but that's too hard now.
2421 :
2422 : ??? Contrary to the tree alias oracle this does not return
2423 : one for X + non-constant and Y + non-constant when X and Y are equal.
2424 : If that is fixed the TBAA hack for union type-punning can be removed. */
2425 :
2426 : static int
2427 1871697632 : memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
2428 : poly_int64 c)
2429 : {
2430 2693184266 : if (GET_CODE (x) == VALUE)
2431 : {
2432 725701070 : if (REG_P (y))
2433 : {
2434 275708367 : struct elt_loc_list *l = NULL;
2435 275708367 : if (CSELIB_VAL_PTR (x))
2436 275708367 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs;
2437 501881908 : l; l = l->next)
2438 360316235 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y))
2439 : break;
2440 275708367 : if (l)
2441 : x = y;
2442 : else
2443 141565673 : x = get_addr (x);
2444 : }
2445 : /* Don't call get_addr if y is the same VALUE. */
2446 449992703 : else if (x != y)
2447 449908478 : x = get_addr (x);
2448 : }
2449 2693184266 : if (GET_CODE (y) == VALUE)
2450 : {
2451 421053135 : if (REG_P (x))
2452 : {
2453 13713259 : struct elt_loc_list *l = NULL;
2454 13713259 : if (CSELIB_VAL_PTR (y))
2455 13713259 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs;
2456 16531360 : l; l = l->next)
2457 2837539 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x))
2458 : break;
2459 13713259 : if (l)
2460 : y = x;
2461 : else
2462 13693821 : y = get_addr (y);
2463 : }
2464 : /* Don't call get_addr if x is the same VALUE. */
2465 407339876 : else if (y != x)
2466 407255194 : y = get_addr (y);
2467 : }
2468 2693184266 : if (GET_CODE (x) == HIGH)
2469 0 : x = XEXP (x, 0);
2470 2693184266 : else if (GET_CODE (x) == LO_SUM)
2471 0 : x = XEXP (x, 1);
2472 : else
2473 2693184266 : x = addr_side_effect_eval (x, maybe_lt (xsize, 0) ? -xsize : xsize, 0);
2474 2693184266 : if (GET_CODE (y) == HIGH)
2475 0 : y = XEXP (y, 0);
2476 2693184266 : else if (GET_CODE (y) == LO_SUM)
2477 0 : y = XEXP (y, 1);
2478 : else
2479 2693184266 : y = addr_side_effect_eval (y, maybe_lt (ysize, 0) ? -ysize : ysize, 0);
2480 :
2481 2693184266 : if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
2482 : {
2483 529576 : HOST_WIDE_INT distance = 0;
2484 529576 : int cmp = compare_base_symbol_refs (x, y, &distance);
2485 :
2486 : /* If both decls are the same, decide by offsets. */
2487 529576 : if (cmp == 1)
2488 765507 : return offset_overlap_p (c + distance, xsize, ysize);
2489 : /* Assume a potential overlap for symbolic addresses that went
2490 : through alignment adjustments (i.e., that have negative
2491 : sizes), because we can't know how far they are from each
2492 : other. */
2493 146768 : if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
2494 : return -1;
2495 : /* If decls are different or we know by offsets that there is no overlap,
2496 : we win. */
2497 676344 : if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
2498 146768 : return 0;
2499 : /* Decls may or may not be different and offsets overlap....*/
2500 : return -1;
2501 : }
2502 2692654690 : else if (rtx_equal_for_memref_p (x, y))
2503 : {
2504 292863838 : return offset_overlap_p (c, xsize, ysize);
2505 : }
2506 :
2507 : /* This code used to check for conflicts involving stack references and
2508 : globals but the base address alias code now handles these cases. */
2509 :
2510 2546214677 : if (GET_CODE (x) == PLUS)
2511 : {
2512 : /* The fact that X is canonicalized means that this
2513 : PLUS rtx is canonicalized. */
2514 1516887328 : rtx x0 = XEXP (x, 0);
2515 1516887328 : rtx x1 = XEXP (x, 1);
2516 :
2517 : /* However, VALUEs might end up in different positions even in
2518 : canonical PLUSes. Comparing their addresses is enough. */
2519 1516887328 : if (x0 == y)
2520 25571165 : return memrefs_conflict_p (xsize, x1, ysize, const0_rtx, c);
2521 1491316163 : else if (x1 == y)
2522 338458 : return memrefs_conflict_p (xsize, x0, ysize, const0_rtx, c);
2523 :
2524 1490977705 : poly_int64 cx1, cy1;
2525 1490977705 : if (GET_CODE (y) == PLUS)
2526 : {
2527 : /* The fact that Y is canonicalized means that this
2528 : PLUS rtx is canonicalized. */
2529 1342511739 : rtx y0 = XEXP (y, 0);
2530 1342511739 : rtx y1 = XEXP (y, 1);
2531 :
2532 1342511739 : if (x0 == y1)
2533 : return memrefs_conflict_p (xsize, x1, ysize, y0, c);
2534 1342418117 : if (x1 == y0)
2535 : return memrefs_conflict_p (xsize, x0, ysize, y1, c);
2536 :
2537 1342264392 : if (rtx_equal_for_memref_p (x1, y1))
2538 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2539 1205115523 : if (rtx_equal_for_memref_p (x0, y0))
2540 : return memrefs_conflict_p (xsize, x1, ysize, y1, c);
2541 568028647 : if (poly_int_rtx_p (x1, &cx1))
2542 : {
2543 1097564378 : poly_offset_int co = c;
2544 548782189 : co -= cx1;
2545 548782189 : if (poly_int_rtx_p (y1, &cy1))
2546 : {
2547 540789548 : co += cy1;
2548 540789548 : if (!co.to_shwi (&c))
2549 : return -1;
2550 540785880 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2551 : }
2552 7992641 : else if (!co.to_shwi (&c))
2553 : return -1;
2554 : else
2555 7992641 : return memrefs_conflict_p (xsize, x0, ysize, y, c);
2556 : }
2557 697211907 : else if (poly_int_rtx_p (y1, &cy1))
2558 : {
2559 30067748 : poly_offset_int co = c;
2560 15033874 : co += cy1;
2561 15033874 : if (!co.to_shwi (&c))
2562 : return -1;
2563 15033874 : return memrefs_conflict_p (xsize, x, ysize, y0, c);
2564 : }
2565 :
2566 : return -1;
2567 : }
2568 148465966 : else if (poly_int_rtx_p (x1, &cx1))
2569 : {
2570 228298772 : poly_offset_int co = c;
2571 114149386 : co -= cx1;
2572 114149386 : if (!co.to_shwi (&c))
2573 : return -1;
2574 114149376 : return memrefs_conflict_p (xsize, x0, ysize, y, c);
2575 : }
2576 : }
2577 1029327349 : else if (GET_CODE (y) == PLUS)
2578 : {
2579 : /* The fact that Y is canonicalized means that this
2580 : PLUS rtx is canonicalized. */
2581 83715686 : rtx y0 = XEXP (y, 0);
2582 83715686 : rtx y1 = XEXP (y, 1);
2583 :
2584 83715686 : if (x == y0)
2585 9436418 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y1, c);
2586 74279268 : if (x == y1)
2587 824498 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y0, c);
2588 :
2589 73454770 : poly_int64 cy1;
2590 129869775 : if (poly_int_rtx_p (y1, &cy1))
2591 : {
2592 112830010 : poly_offset_int co = c;
2593 56415005 : co += cy1;
2594 56415005 : if (!co.to_shwi (&c))
2595 : return -1;
2596 56415005 : return memrefs_conflict_p (xsize, x, ysize, y0, c);
2597 : }
2598 : else
2599 : return -1;
2600 : }
2601 :
2602 979928243 : if (GET_CODE (x) == GET_CODE (y))
2603 791709949 : switch (GET_CODE (x))
2604 : {
2605 321485 : case MULT:
2606 321485 : {
2607 : /* Handle cases where we expect the second operands to be the
2608 : same, and check only whether the first operand would conflict
2609 : or not. */
2610 321485 : rtx x0, y0;
2611 321485 : rtx x1 = canon_rtx (XEXP (x, 1));
2612 321485 : rtx y1 = canon_rtx (XEXP (y, 1));
2613 321485 : if (! rtx_equal_for_memref_p (x1, y1))
2614 : return -1;
2615 303602 : x0 = canon_rtx (XEXP (x, 0));
2616 303602 : y0 = canon_rtx (XEXP (y, 0));
2617 303602 : if (rtx_equal_for_memref_p (x0, y0))
2618 0 : return offset_overlap_p (c, xsize, ysize);
2619 :
2620 : /* Can't properly adjust our sizes. */
2621 303602 : poly_int64 c1;
2622 281702878 : if (!poly_int_rtx_p (x1, &c1)
2623 300864 : || !can_div_trunc_p (xsize, c1, &xsize)
2624 300864 : || !can_div_trunc_p (ysize, c1, &ysize)
2625 300864 : || !can_div_trunc_p (c, c1, &c))
2626 : return -1;
2627 300864 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2628 : }
2629 :
2630 : default:
2631 : break;
2632 : }
2633 :
2634 : /* Deal with alignment ANDs by adjusting offset and size so as to
2635 : cover the maximum range, without taking any previously known
2636 : alignment into account. Make a size negative after such an
2637 : adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2638 : assume a potential overlap, because they may end up in contiguous
2639 : memory locations and the stricter-alignment access may span over
2640 : part of both. */
2641 979606758 : if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2642 : {
2643 4133305 : HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
2644 4133305 : unsigned HOST_WIDE_INT uc = sc;
2645 4133305 : if (sc < 0 && pow2_or_zerop (-uc))
2646 : {
2647 4132869 : if (maybe_gt (xsize, 0))
2648 4132661 : xsize = -xsize;
2649 4132869 : if (maybe_ne (xsize, 0))
2650 : {
2651 4132705 : poly_offset_int xsizeo = xsize;
2652 4132705 : xsizeo += sc + 1;
2653 4132705 : if (!xsizeo.to_shwi (&xsize))
2654 0 : return -1;
2655 : }
2656 4132869 : poly_offset_int co = c;
2657 4132869 : co -= sc + 1;
2658 4132869 : if (!co.to_shwi (&c))
2659 : return -1;
2660 4132869 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2661 4132869 : ysize, y, c);
2662 : }
2663 : }
2664 975473889 : if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2665 : {
2666 5454209 : HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
2667 5454209 : unsigned HOST_WIDE_INT uc = sc;
2668 5454209 : if (sc < 0 && pow2_or_zerop (-uc))
2669 : {
2670 5450448 : if (maybe_gt (ysize, 0))
2671 5449985 : ysize = -ysize;
2672 5450448 : if (maybe_ne (ysize, 0))
2673 : {
2674 5450412 : poly_offset_int ysizeo = ysize;
2675 5450412 : ysizeo += sc + 1;
2676 5450412 : if (!ysizeo.to_shwi (&ysize))
2677 0 : return -1;
2678 : }
2679 5450448 : poly_offset_int co = c;
2680 5450448 : co += sc + 1;
2681 5450448 : if (!co.to_shwi (&c))
2682 : return -1;
2683 5450448 : return memrefs_conflict_p (xsize, x,
2684 5450448 : ysize, canon_rtx (XEXP (y, 0)), c);
2685 : }
2686 : }
2687 :
2688 970023441 : if (CONSTANT_P (x))
2689 : {
2690 688642048 : poly_int64 cx, cy;
2691 688642048 : if (poly_int_rtx_p (x, &cx) && poly_int_rtx_p (y, &cy))
2692 : {
2693 2005095915 : poly_offset_int co = c;
2694 668365305 : co += cy;
2695 668365305 : co -= cx;
2696 668365305 : if (!co.to_shwi (&c))
2697 : return -1;
2698 1336119554 : return offset_overlap_p (c, xsize, ysize);
2699 : }
2700 :
2701 20276743 : if (GET_CODE (x) == CONST)
2702 : {
2703 9629609 : if (GET_CODE (y) == CONST)
2704 8458002 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2705 8458002 : ysize, canon_rtx (XEXP (y, 0)), c);
2706 : else
2707 1171607 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2708 1171607 : ysize, y, c);
2709 : }
2710 10647134 : if (GET_CODE (y) == CONST)
2711 902530 : return memrefs_conflict_p (xsize, x, ysize,
2712 902530 : canon_rtx (XEXP (y, 0)), c);
2713 :
2714 : /* Assume a potential overlap for symbolic addresses that went
2715 : through alignment adjustments (i.e., that have negative
2716 : sizes), because we can't know how far they are from each
2717 : other. */
2718 9744604 : if (CONSTANT_P (y))
2719 25982 : return (maybe_lt (xsize, 0)
2720 25982 : || maybe_lt (ysize, 0)
2721 51964 : || offset_overlap_p (c, xsize, ysize));
2722 :
2723 : return -1;
2724 : }
2725 :
2726 : return -1;
2727 : }
2728 :
2729 : /* Functions to compute memory dependencies.
2730 :
2731 : Since we process the insns in execution order, we can build tables
2732 : to keep track of what registers are fixed (and not aliased), what registers
2733 : are varying in known ways, and what registers are varying in unknown
2734 : ways.
2735 :
2736 : If both memory references are volatile, then there must always be a
2737 : dependence between the two references, since their order cannot be
2738 : changed. A volatile and non-volatile reference can be interchanged
2739 : though.
2740 :
2741 : We also must allow AND addresses, because they may generate accesses
2742 : outside the object being referenced. This is used to generate aligned
2743 : addresses from unaligned addresses, for instance, the alpha
2744 : storeqi_unaligned pattern. */
2745 :
2746 : /* Read dependence: X is read after read in MEM takes place. There can
2747 : only be a dependence here if both reads are volatile, or if either is
2748 : an explicit barrier. */
2749 :
2750 : bool
2751 32001736 : read_dependence (const_rtx mem, const_rtx x)
2752 : {
2753 32001736 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2754 : return true;
2755 31496045 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2756 62977239 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2757 23124 : return true;
2758 : return false;
2759 : }
2760 :
2761 : /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2762 :
2763 : static tree
2764 61975516 : decl_for_component_ref (tree x)
2765 : {
2766 82290381 : do
2767 : {
2768 82290381 : x = TREE_OPERAND (x, 0);
2769 : }
2770 82290381 : while (x && TREE_CODE (x) == COMPONENT_REF);
2771 :
2772 61975516 : return x && DECL_P (x) ? x : NULL_TREE;
2773 : }
2774 :
2775 : /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2776 : for the offset of the field reference. *KNOWN_P says whether the
2777 : offset is known. */
2778 :
2779 : static void
2780 9557823 : adjust_offset_for_component_ref (tree x, bool *known_p,
2781 : poly_int64 *offset)
2782 : {
2783 9557823 : if (!*known_p)
2784 : return;
2785 11505480 : do
2786 : {
2787 11505480 : tree xoffset = component_ref_field_offset (x);
2788 11505480 : tree field = TREE_OPERAND (x, 1);
2789 11505480 : if (!poly_int_tree_p (xoffset))
2790 : {
2791 0 : *known_p = false;
2792 0 : return;
2793 : }
2794 :
2795 11505480 : poly_offset_int woffset
2796 11505480 : = (wi::to_poly_offset (xoffset)
2797 11505480 : + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field))
2798 23010960 : >> LOG2_BITS_PER_UNIT)
2799 11505480 : + *offset);
2800 11505480 : if (!woffset.to_shwi (offset))
2801 : {
2802 0 : *known_p = false;
2803 0 : return;
2804 : }
2805 :
2806 11505480 : x = TREE_OPERAND (x, 0);
2807 : }
2808 11505480 : while (x && TREE_CODE (x) == COMPONENT_REF);
2809 : }
2810 :
2811 : /* Return true if we can determine the exprs corresponding to memrefs
2812 : X and Y and they do not overlap.
2813 : If LOOP_VARIANT is set, skip offset-based disambiguation */
2814 :
2815 : bool
2816 249922398 : nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2817 : {
2818 272779324 : tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2819 249922398 : rtx rtlx, rtly;
2820 249922398 : rtx basex, basey;
2821 249922398 : bool moffsetx_known_p, moffsety_known_p;
2822 249922398 : poly_int64 moffsetx = 0, moffsety = 0;
2823 249922398 : poly_int64 offsetx = 0, offsety = 0, sizex, sizey;
2824 :
2825 : /* Unless both have exprs, we can't tell anything. */
2826 249922398 : if (exprx == 0 || expry == 0)
2827 : return false;
2828 :
2829 : /* For spill-slot accesses make sure we have valid offsets. */
2830 204560986 : if ((exprx == get_spill_slot_decl (false)
2831 15896437 : && ! MEM_OFFSET_KNOWN_P (x))
2832 220457423 : || (expry == get_spill_slot_decl (false)
2833 26925118 : && ! MEM_OFFSET_KNOWN_P (y)))
2834 0 : return false;
2835 :
2836 : /* If the field reference test failed, look at the DECLs involved. */
2837 204560986 : moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2838 204560986 : if (moffsetx_known_p)
2839 202162867 : moffsetx = MEM_OFFSET (x);
2840 204560986 : if (TREE_CODE (exprx) == COMPONENT_REF)
2841 : {
2842 36658181 : tree t = decl_for_component_ref (exprx);
2843 36658181 : if (! t)
2844 : return false;
2845 4580867 : adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx);
2846 4580867 : exprx = t;
2847 : }
2848 :
2849 172483672 : moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2850 172483672 : if (moffsety_known_p)
2851 170614114 : moffsety = MEM_OFFSET (y);
2852 172483672 : if (TREE_CODE (expry) == COMPONENT_REF)
2853 : {
2854 25317335 : tree t = decl_for_component_ref (expry);
2855 25317335 : if (! t)
2856 : return false;
2857 4976956 : adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety);
2858 4976956 : expry = t;
2859 : }
2860 :
2861 152143293 : if (! DECL_P (exprx) || ! DECL_P (expry))
2862 : return false;
2863 :
2864 : /* If we refer to different gimple registers, or one gimple register
2865 : and one non-gimple-register, we know they can't overlap. First,
2866 : gimple registers don't have their addresses taken. Now, there
2867 : could be more than one stack slot for (different versions of) the
2868 : same gimple register, but we can presumably tell they don't
2869 : overlap based on offsets from stack base addresses elsewhere.
2870 : It's important that we don't proceed to DECL_RTL, because gimple
2871 : registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2872 : able to do anything about them since no SSA information will have
2873 : remained to guide it. */
2874 13837654 : if (is_gimple_reg (exprx) || is_gimple_reg (expry))
2875 3811135 : return exprx != expry
2876 3811135 : || (moffsetx_known_p && moffsety_known_p
2877 247730 : && MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y)
2878 247730 : && !offset_overlap_p (moffsety - moffsetx,
2879 123865 : MEM_SIZE (x), MEM_SIZE (y)));
2880 :
2881 : /* With invalid code we can end up storing into the constant pool.
2882 : Bail out to avoid ICEing when creating RTL for this.
2883 : See gfortran.dg/lto/20091028-2_0.f90. */
2884 10026519 : if (TREE_CODE (exprx) == CONST_DECL
2885 10026519 : || TREE_CODE (expry) == CONST_DECL)
2886 : return true;
2887 :
2888 : /* If one decl is known to be a function or label in a function and
2889 : the other is some kind of data, they can't overlap. */
2890 10026519 : if ((TREE_CODE (exprx) == FUNCTION_DECL
2891 10026519 : || TREE_CODE (exprx) == LABEL_DECL)
2892 : != (TREE_CODE (expry) == FUNCTION_DECL
2893 10026519 : || TREE_CODE (expry) == LABEL_DECL))
2894 : return true;
2895 :
2896 : /* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2897 : living in multiple places), we can't tell anything. Exception
2898 : are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2899 9846557 : if ((!DECL_RTL_SET_P (exprx) && TREE_CODE (exprx) != FUNCTION_DECL)
2900 19693114 : || (!DECL_RTL_SET_P (expry) && TREE_CODE (expry) != FUNCTION_DECL))
2901 : return false;
2902 :
2903 9846557 : rtlx = DECL_RTL (exprx);
2904 9846557 : rtly = DECL_RTL (expry);
2905 :
2906 : /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2907 : can't overlap unless they are the same because we never reuse that part
2908 : of the stack frame used for locals for spilled pseudos. */
2909 9845997 : if ((!MEM_P (rtlx) || !MEM_P (rtly))
2910 9879683 : && ! rtx_equal_p (rtlx, rtly))
2911 : return true;
2912 :
2913 : /* If we have MEMs referring to different address spaces (which can
2914 : potentially overlap), we cannot easily tell from the addresses
2915 : whether the references overlap. */
2916 9812871 : if (MEM_P (rtlx) && MEM_P (rtly)
2917 19626048 : && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2918 : return false;
2919 :
2920 : /* Get the base and offsets of both decls. If either is a register, we
2921 : know both are and are the same, so use that as the base. The only
2922 : we can avoid overlap is if we can deduce that they are nonoverlapping
2923 : pieces of that decl, which is very rare. */
2924 9813177 : basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2925 9813177 : basex = strip_offset_and_add (basex, &offsetx);
2926 :
2927 9813177 : basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2928 9813177 : basey = strip_offset_and_add (basey, &offsety);
2929 :
2930 : /* If the bases are different, we know they do not overlap if both
2931 : are constants or if one is a constant and the other a pointer into the
2932 : stack frame. Otherwise a different base means we can't tell if they
2933 : overlap or not. */
2934 9813177 : if (compare_base_decls (exprx, expry) == 0)
2935 7004919 : return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2936 2645896 : || (CONSTANT_P (basex) && REG_P (basey)
2937 275398 : && REGNO_PTR_FRAME_P (REGNO (basey)))
2938 11748137 : || (CONSTANT_P (basey) && REG_P (basex)
2939 412468 : && REGNO_PTR_FRAME_P (REGNO (basex))));
2940 :
2941 : /* Offset based disambiguation not appropriate for loop invariant */
2942 437760 : if (loop_invariant)
2943 : return false;
2944 :
2945 : /* Offset based disambiguation is OK even if we do not know that the
2946 : declarations are necessarily different
2947 : (i.e. compare_base_decls (exprx, expry) == -1) */
2948 :
2949 438066 : sizex = (!MEM_P (rtlx) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx)))
2950 437454 : : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2951 : : -1);
2952 438066 : sizey = (!MEM_P (rtly) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly)))
2953 437454 : : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2954 : : -1);
2955 :
2956 : /* If we have an offset for either memref, it can update the values computed
2957 : above. */
2958 437760 : if (moffsetx_known_p)
2959 410964 : offsetx += moffsetx, sizex -= moffsetx;
2960 437760 : if (moffsety_known_p)
2961 372127 : offsety += moffsety, sizey -= moffsety;
2962 :
2963 : /* If a memref has both a size and an offset, we can use the smaller size.
2964 : We can't do this if the offset isn't known because we must view this
2965 : memref as being anywhere inside the DECL's MEM. */
2966 437760 : if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2967 410964 : sizex = MEM_SIZE (x);
2968 437760 : if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2969 372127 : sizey = MEM_SIZE (y);
2970 :
2971 437760 : return !ranges_maybe_overlap_p (offsetx, sizex, offsety, sizey);
2972 : }
2973 :
2974 : /* Helper for true_dependence and canon_true_dependence.
2975 : Checks for true dependence: X is read after store in MEM takes place.
2976 :
2977 : If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2978 : NULL_RTX, and the canonical addresses of MEM and X are both computed
2979 : here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2980 :
2981 : If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2982 :
2983 : Returns true if there is a true dependence, false otherwise. */
2984 :
2985 : static bool
2986 850106852 : true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
2987 : const_rtx x, rtx x_addr, bool mem_canonicalized)
2988 : {
2989 850106852 : rtx true_mem_addr;
2990 850106852 : rtx base;
2991 850106852 : int ret;
2992 :
2993 850106852 : gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2994 : : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2995 :
2996 850106852 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2997 : return true;
2998 :
2999 : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3000 : This is used in epilogue deallocation functions, and in cselib. */
3001 849428533 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3002 : return true;
3003 849408355 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3004 : return true;
3005 843894127 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3006 1687759531 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3007 : return true;
3008 :
3009 840918998 : if (! x_addr)
3010 54677069 : x_addr = XEXP (x, 0);
3011 840918998 : x_addr = get_addr (x_addr);
3012 :
3013 840918998 : if (! mem_addr)
3014 : {
3015 42398422 : mem_addr = XEXP (mem, 0);
3016 42398422 : if (mem_mode == VOIDmode)
3017 23210958 : mem_mode = GET_MODE (mem);
3018 : }
3019 840918998 : true_mem_addr = get_addr (mem_addr);
3020 :
3021 : /* Read-only memory is by definition never modified, and therefore can't
3022 : conflict with anything. However, don't assume anything when AND
3023 : addresses are involved and leave to the code below to determine
3024 : dependence. We don't expect to find read-only set on MEM, but
3025 : stupid user tricks can produce them, so don't die. */
3026 840918998 : if (MEM_READONLY_P (x)
3027 4508810 : && GET_CODE (x_addr) != AND
3028 845427808 : && GET_CODE (true_mem_addr) != AND)
3029 : return false;
3030 :
3031 : /* If we have MEMs referring to different address spaces (which can
3032 : potentially overlap), we cannot easily tell from the addresses
3033 : whether the references overlap. */
3034 893881243 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3035 : return true;
3036 :
3037 836344077 : base = find_base_term (x_addr);
3038 836344077 : if (base && (GET_CODE (base) == LABEL_REF
3039 710805276 : || (GET_CODE (base) == SYMBOL_REF
3040 62797578 : && CONSTANT_POOL_ADDRESS_P (base))))
3041 : return false;
3042 :
3043 836343179 : rtx mem_base = find_base_term (true_mem_addr);
3044 836343179 : if (! base_alias_check (x_addr, base, true_mem_addr, mem_base,
3045 836343179 : GET_MODE (x), mem_mode))
3046 : return false;
3047 :
3048 752643380 : x_addr = canon_rtx (x_addr);
3049 752643380 : if (!mem_canonicalized)
3050 30524460 : mem_addr = canon_rtx (true_mem_addr);
3051 :
3052 752643380 : if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
3053 1505286760 : SIZE_FOR_MODE (x), x_addr, 0)) != -1)
3054 506954752 : return !!ret;
3055 :
3056 245688628 : if (mems_in_disjoint_alias_sets_p (x, mem))
3057 : return false;
3058 :
3059 183234331 : if (nonoverlapping_memrefs_p (mem, x, false))
3060 : return false;
3061 :
3062 174624721 : return rtx_refs_may_alias_p (x, mem, true);
3063 : }
3064 :
3065 : /* True dependence: X is read after store in MEM takes place. */
3066 :
3067 : bool
3068 45144537 : true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x)
3069 : {
3070 45144537 : return true_dependence_1 (mem, mem_mode, NULL_RTX,
3071 45144537 : x, NULL_RTX, /*mem_canonicalized=*/false);
3072 : }
3073 :
3074 : /* Canonical true dependence: X is read after store in MEM takes place.
3075 : Variant of true_dependence which assumes MEM has already been
3076 : canonicalized (hence we no longer do that here).
3077 : The mem_addr argument has been added, since true_dependence_1 computed
3078 : this value prior to canonicalizing. */
3079 :
3080 : bool
3081 804962315 : canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
3082 : const_rtx x, rtx x_addr)
3083 : {
3084 804962315 : return true_dependence_1 (mem, mem_mode, mem_addr,
3085 804962315 : x, x_addr, /*mem_canonicalized=*/true);
3086 : }
3087 :
3088 : /* Returns true if a write to X might alias a previous read from
3089 : (or, if WRITEP is true, a write to) MEM.
3090 : If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3091 : and X_MODE the mode for that access.
3092 : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3093 :
3094 : static bool
3095 471405584 : write_dependence_p (const_rtx mem,
3096 : const_rtx x, machine_mode x_mode, rtx x_addr,
3097 : bool mem_canonicalized, bool x_canonicalized, bool writep)
3098 : {
3099 471405584 : rtx mem_addr;
3100 471405584 : rtx true_mem_addr, true_x_addr;
3101 471405584 : rtx base;
3102 471405584 : int ret;
3103 :
3104 471405584 : gcc_checking_assert (x_canonicalized
3105 : ? (x_addr != NULL_RTX
3106 : && (x_mode != VOIDmode || GET_MODE (x) == VOIDmode))
3107 : : (x_addr == NULL_RTX && x_mode == VOIDmode));
3108 :
3109 471405584 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3110 : return true;
3111 :
3112 : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3113 : This is used in epilogue deallocation functions. */
3114 470817492 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3115 : return true;
3116 444124792 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3117 : return true;
3118 442984020 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3119 885767056 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3120 : return true;
3121 :
3122 442764022 : if (!x_addr)
3123 52175137 : x_addr = XEXP (x, 0);
3124 442764022 : true_x_addr = get_addr (x_addr);
3125 :
3126 442764022 : mem_addr = XEXP (mem, 0);
3127 442764022 : true_mem_addr = get_addr (mem_addr);
3128 :
3129 : /* A read from read-only memory can't conflict with read-write memory.
3130 : Don't assume anything when AND addresses are involved and leave to
3131 : the code below to determine dependence. */
3132 442764022 : if (!writep
3133 409526450 : && MEM_READONLY_P (mem)
3134 11266681 : && GET_CODE (true_x_addr) != AND
3135 454030703 : && GET_CODE (true_mem_addr) != AND)
3136 : return false;
3137 :
3138 : /* If we have MEMs referring to different address spaces (which can
3139 : potentially overlap), we cannot easily tell from the addresses
3140 : whether the references overlap. */
3141 448570283 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3142 : return true;
3143 :
3144 431459027 : base = find_base_term (true_mem_addr);
3145 431459027 : if (! writep
3146 431459027 : && base
3147 431459027 : && (GET_CODE (base) == LABEL_REF
3148 338459490 : || (GET_CODE (base) == SYMBOL_REF
3149 32927734 : && CONSTANT_POOL_ADDRESS_P (base))))
3150 : return false;
3151 :
3152 431458257 : rtx x_base = find_base_term (true_x_addr);
3153 431458257 : if (! base_alias_check (true_x_addr, x_base, true_mem_addr, base,
3154 431458257 : GET_MODE (x), GET_MODE (mem)))
3155 : return false;
3156 :
3157 375094159 : if (!x_canonicalized)
3158 : {
3159 46732715 : x_addr = canon_rtx (true_x_addr);
3160 46732715 : x_mode = GET_MODE (x);
3161 : }
3162 375094159 : if (!mem_canonicalized)
3163 222491164 : mem_addr = canon_rtx (true_mem_addr);
3164 :
3165 1125282477 : if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
3166 375094159 : GET_MODE_SIZE (x_mode), x_addr, 0)) != -1)
3167 308406092 : return !!ret;
3168 :
3169 66688067 : if (nonoverlapping_memrefs_p (x, mem, false))
3170 : return false;
3171 :
3172 63625175 : return rtx_refs_may_alias_p (x, mem, false);
3173 : }
3174 :
3175 : /* Anti dependence: X is written after read in MEM takes place. */
3176 :
3177 : bool
3178 23418427 : anti_dependence (const_rtx mem, const_rtx x)
3179 : {
3180 23418427 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3181 : /*mem_canonicalized=*/false,
3182 23418427 : /*x_canonicalized*/false, /*writep=*/false);
3183 : }
3184 :
3185 : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3186 : Also, consider X in X_MODE (which might be from an enclosing
3187 : STRICT_LOW_PART / ZERO_EXTRACT).
3188 : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3189 :
3190 : bool
3191 412491253 : canon_anti_dependence (const_rtx mem, bool mem_canonicalized,
3192 : const_rtx x, machine_mode x_mode, rtx x_addr)
3193 : {
3194 412491253 : return write_dependence_p (mem, x, x_mode, x_addr,
3195 : mem_canonicalized, /*x_canonicalized=*/true,
3196 412491253 : /*writep=*/false);
3197 : }
3198 :
3199 : /* Output dependence: X is written after store in MEM takes place. */
3200 :
3201 : bool
3202 31962737 : output_dependence (const_rtx mem, const_rtx x)
3203 : {
3204 31962737 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3205 : /*mem_canonicalized=*/false,
3206 31962737 : /*x_canonicalized*/false, /*writep=*/true);
3207 : }
3208 :
3209 : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3210 : Also, consider X in X_MODE (which might be from an enclosing
3211 : STRICT_LOW_PART / ZERO_EXTRACT).
3212 : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3213 :
3214 : bool
3215 3533167 : canon_output_dependence (const_rtx mem, bool mem_canonicalized,
3216 : const_rtx x, machine_mode x_mode, rtx x_addr)
3217 : {
3218 3533167 : return write_dependence_p (mem, x, x_mode, x_addr,
3219 : mem_canonicalized, /*x_canonicalized=*/true,
3220 3533167 : /*writep=*/true);
3221 : }
3222 :
3223 :
3224 :
3225 : /* Check whether X may be aliased with MEM. Don't do offset-based
3226 : memory disambiguation & TBAA. */
3227 : bool
3228 0 : may_alias_p (const_rtx mem, const_rtx x)
3229 : {
3230 0 : rtx x_addr, mem_addr;
3231 :
3232 0 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3233 : return true;
3234 :
3235 : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3236 : This is used in epilogue deallocation functions. */
3237 0 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3238 : return true;
3239 0 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3240 : return true;
3241 0 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3242 0 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3243 : return true;
3244 :
3245 0 : x_addr = XEXP (x, 0);
3246 0 : x_addr = get_addr (x_addr);
3247 :
3248 0 : mem_addr = XEXP (mem, 0);
3249 0 : mem_addr = get_addr (mem_addr);
3250 :
3251 : /* Read-only memory is by definition never modified, and therefore can't
3252 : conflict with anything. However, don't assume anything when AND
3253 : addresses are involved and leave to the code below to determine
3254 : dependence. We don't expect to find read-only set on MEM, but
3255 : stupid user tricks can produce them, so don't die. */
3256 0 : if (MEM_READONLY_P (x)
3257 0 : && GET_CODE (x_addr) != AND
3258 0 : && GET_CODE (mem_addr) != AND)
3259 : return false;
3260 :
3261 : /* If we have MEMs referring to different address spaces (which can
3262 : potentially overlap), we cannot easily tell from the addresses
3263 : whether the references overlap. */
3264 0 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3265 : return true;
3266 :
3267 0 : rtx x_base = find_base_term (x_addr);
3268 0 : rtx mem_base = find_base_term (mem_addr);
3269 0 : if (! base_alias_check (x_addr, x_base, mem_addr, mem_base,
3270 0 : GET_MODE (x), GET_MODE (mem_addr)))
3271 : return false;
3272 :
3273 0 : if (nonoverlapping_memrefs_p (mem, x, true))
3274 : return false;
3275 :
3276 : /* TBAA not valid for loop_invarint */
3277 0 : return rtx_refs_may_alias_p (x, mem, false);
3278 : }
3279 :
3280 : void
3281 213440 : init_alias_target (void)
3282 : {
3283 213440 : int i;
3284 :
3285 213440 : if (!arg_base_value)
3286 209218 : arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
3287 :
3288 213440 : memset (static_reg_base_value, 0, sizeof static_reg_base_value);
3289 :
3290 19849920 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3291 : /* Check whether this register can hold an incoming pointer
3292 : argument. FUNCTION_ARG_REGNO_P tests outgoing register
3293 : numbers, so translate if necessary due to register windows. */
3294 19636480 : if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
3295 19688185 : && targetm.hard_regno_mode_ok (i, Pmode))
3296 3162458 : static_reg_base_value[i] = arg_base_value;
3297 :
3298 : /* RTL code is required to be consistent about whether it uses the
3299 : stack pointer, the frame pointer or the argument pointer to
3300 : access a given area of the frame. We can therefore use the
3301 : base address to distinguish between the different areas. */
3302 213440 : static_reg_base_value[STACK_POINTER_REGNUM]
3303 213440 : = unique_base_value (UNIQUE_BASE_VALUE_SP);
3304 213440 : static_reg_base_value[ARG_POINTER_REGNUM]
3305 213440 : = unique_base_value (UNIQUE_BASE_VALUE_ARGP);
3306 213440 : static_reg_base_value[FRAME_POINTER_REGNUM]
3307 213440 : = unique_base_value (UNIQUE_BASE_VALUE_FP);
3308 :
3309 : /* The above rules extend post-reload, with eliminations applying
3310 : consistently to each of the three pointers. Cope with cases in
3311 : which the frame pointer is eliminated to the hard frame pointer
3312 : rather than the stack pointer. */
3313 213440 : if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3314 213440 : static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
3315 213440 : = unique_base_value (UNIQUE_BASE_VALUE_HFP);
3316 213440 : }
3317 :
3318 : /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3319 : to be memory reference. */
3320 : static bool memory_modified;
3321 : static void
3322 33254451 : memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3323 : {
3324 33254451 : if (MEM_P (x))
3325 : {
3326 2642822 : if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
3327 509475 : memory_modified = true;
3328 : }
3329 33254451 : }
3330 :
3331 :
3332 : /* Return true when INSN possibly modify memory contents of MEM
3333 : (i.e. address can be modified). */
3334 : bool
3335 44864748 : memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
3336 : {
3337 44864748 : if (!INSN_P (insn))
3338 : return false;
3339 : /* Conservatively assume all non-readonly MEMs might be modified in
3340 : calls. */
3341 41983083 : if (CALL_P (insn))
3342 : return true;
3343 41658268 : memory_modified = false;
3344 41658268 : note_stores (as_a<const rtx_insn *> (insn), memory_modified_1,
3345 : const_cast<rtx> (mem));
3346 41658268 : return memory_modified;
3347 : }
3348 :
3349 : /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3350 : array. */
3351 :
3352 : void
3353 9421744 : init_alias_analysis (void)
3354 : {
3355 9421744 : const bool frame_pointer_eliminated
3356 9421744 : = reload_completed
3357 4101863 : && !frame_pointer_needed
3358 13281489 : && targetm.can_eliminate (FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM);
3359 9421744 : unsigned int maxreg = max_reg_num ();
3360 9421744 : bool changed;
3361 9421744 : int pass, i;
3362 9421744 : unsigned int ui;
3363 9421744 : rtx_insn *insn;
3364 9421744 : rtx val;
3365 9421744 : int rpo_cnt;
3366 9421744 : int *rpo;
3367 :
3368 9421744 : timevar_push (TV_ALIAS_ANALYSIS);
3369 :
3370 9421744 : vec_safe_grow_cleared (reg_known_value, maxreg - FIRST_PSEUDO_REGISTER,
3371 : true);
3372 9421744 : reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
3373 9421744 : bitmap_clear (reg_known_equiv_p);
3374 :
3375 : /* If we have memory allocated from the previous run, use it. */
3376 9421744 : if (old_reg_base_value)
3377 9169753 : reg_base_value = old_reg_base_value;
3378 :
3379 9421744 : if (reg_base_value)
3380 9212723 : reg_base_value->truncate (0);
3381 :
3382 9421744 : vec_safe_grow_cleared (reg_base_value, maxreg, true);
3383 :
3384 9421744 : new_reg_base_value = XNEWVEC (rtx, maxreg);
3385 9421744 : reg_seen = sbitmap_alloc (maxreg);
3386 :
3387 : /* The basic idea is that each pass through this loop will use the
3388 : "constant" information from the previous pass to propagate alias
3389 : information through another level of assignments.
3390 :
3391 : The propagation is done on the CFG in reverse post-order, to propagate
3392 : things forward as far as possible in each iteration.
3393 :
3394 : This could get expensive if the assignment chains are long. Maybe
3395 : we should throttle the number of iterations, possibly based on
3396 : the optimization level or flag_expensive_optimizations.
3397 :
3398 : We could propagate more information in the first pass by making use
3399 : of DF_REG_DEF_COUNT to determine immediately that the alias information
3400 : for a pseudo is "constant".
3401 :
3402 : A program with an uninitialized variable can cause an infinite loop
3403 : here. Instead of doing a full dataflow analysis to detect such problems
3404 : we just cap the number of iterations for the loop.
3405 :
3406 : The state of the arrays for the set chain in question does not matter
3407 : since the program has undefined behavior. */
3408 :
3409 9421744 : rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3410 9421744 : rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
3411 :
3412 9421744 : pass = 0;
3413 19111543 : do
3414 : {
3415 : /* Assume nothing will change this iteration of the loop. */
3416 19111543 : changed = false;
3417 :
3418 : /* We want to assign the same IDs each iteration of this loop, so
3419 : start counting from one each iteration of the loop. */
3420 19111543 : unique_id = 1;
3421 :
3422 : /* We're at the start of the function each iteration through the
3423 : loop, so we're copying arguments. */
3424 19111543 : copying_arguments = true;
3425 :
3426 : /* Wipe the potential alias information clean for this pass. */
3427 19111543 : memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
3428 :
3429 : /* Wipe the reg_seen array clean. */
3430 19111543 : bitmap_clear (reg_seen);
3431 :
3432 : /* Initialize the alias information for this pass. */
3433 1796485042 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3434 1758261956 : if (static_reg_base_value[i]
3435 : /* Don't treat the hard frame pointer as special if we
3436 : eliminated the frame pointer to the stack pointer. */
3437 348981118 : && !(i == HARD_FRAME_POINTER_REGNUM && frame_pointer_eliminated))
3438 : {
3439 341240713 : new_reg_base_value[i] = static_reg_base_value[i];
3440 341240713 : bitmap_set_bit (reg_seen, i);
3441 : }
3442 :
3443 : /* Walk the insns adding values to the new_reg_base_value array. */
3444 247641266 : for (i = 0; i < rpo_cnt; i++)
3445 : {
3446 228529723 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
3447 2912640332 : FOR_BB_INSNS (bb, insn)
3448 : {
3449 2684110609 : if (NONDEBUG_INSN_P (insn))
3450 : {
3451 1264270039 : rtx note, set;
3452 :
3453 : /* Treat the hard frame pointer as special unless we
3454 : eliminated the frame pointer to the stack pointer. */
3455 1264644234 : if (!frame_pointer_eliminated
3456 1264270039 : && modified_in_p (hard_frame_pointer_rtx, insn))
3457 374195 : continue;
3458 :
3459 : /* If this insn has a noalias note, process it, Otherwise,
3460 : scan for sets. A simple set will have no side effects
3461 : which could change the base value of any other register. */
3462 1263895844 : if (GET_CODE (PATTERN (insn)) == SET
3463 1011160013 : && REG_NOTES (insn) != 0
3464 1782690369 : && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
3465 1529868 : record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
3466 : else
3467 1262365976 : note_stores (insn, record_set, NULL);
3468 :
3469 1263895844 : set = single_set (insn);
3470 :
3471 1263895844 : if (set != 0
3472 1181038656 : && REG_P (SET_DEST (set))
3473 2112203237 : && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3474 : {
3475 320095898 : unsigned int regno = REGNO (SET_DEST (set));
3476 320095898 : rtx src = SET_SRC (set);
3477 320095898 : rtx t;
3478 :
3479 320095898 : note = find_reg_equal_equiv_note (insn);
3480 320095898 : if (note && REG_NOTE_KIND (note) == REG_EQUAL
3481 18032546 : && DF_REG_DEF_COUNT (regno) != 1)
3482 : note = NULL_RTX;
3483 :
3484 : poly_int64 offset;
3485 : if (note != NULL_RTX
3486 17947864 : && GET_CODE (XEXP (note, 0)) != EXPR_LIST
3487 17947864 : && ! rtx_varies_p (XEXP (note, 0), 1)
3488 7820147 : && ! reg_overlap_mentioned_p (SET_DEST (set),
3489 7820147 : XEXP (note, 0)))
3490 : {
3491 7820147 : set_reg_known_value (regno, XEXP (note, 0));
3492 7820147 : set_reg_known_equiv_p (regno,
3493 7820147 : REG_NOTE_KIND (note) == REG_EQUIV);
3494 : }
3495 312275751 : else if (DF_REG_DEF_COUNT (regno) == 1
3496 237045043 : && GET_CODE (src) == PLUS
3497 44733343 : && REG_P (XEXP (src, 0))
3498 43748244 : && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
3499 313499251 : && poly_int_rtx_p (XEXP (src, 1), &offset))
3500 : {
3501 787277 : t = plus_constant (GET_MODE (src), t, offset);
3502 787277 : set_reg_known_value (regno, t);
3503 787277 : set_reg_known_equiv_p (regno, false);
3504 : }
3505 311488474 : else if (DF_REG_DEF_COUNT (regno) == 1
3506 311488474 : && ! rtx_varies_p (src, 1))
3507 : {
3508 32461421 : set_reg_known_value (regno, src);
3509 32461421 : set_reg_known_equiv_p (regno, false);
3510 : }
3511 : }
3512 : }
3513 1419840570 : else if (NOTE_P (insn)
3514 310374497 : && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
3515 19099819 : copying_arguments = false;
3516 : }
3517 : }
3518 :
3519 : /* Now propagate values from new_reg_base_value to reg_base_value. */
3520 19111543 : gcc_assert (maxreg == (unsigned int) max_reg_num ());
3521 :
3522 2827343065 : for (ui = 0; ui < maxreg; ui++)
3523 : {
3524 2808231522 : if (new_reg_base_value[ui]
3525 334245171 : && new_reg_base_value[ui] != (*reg_base_value)[ui]
3526 2972524356 : && ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui]))
3527 : {
3528 163459035 : (*reg_base_value)[ui] = new_reg_base_value[ui];
3529 163459035 : changed = true;
3530 : }
3531 : }
3532 : }
3533 19111632 : while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
3534 9421744 : XDELETEVEC (rpo);
3535 :
3536 : /* Fill in the remaining entries. */
3537 511044442 : FOR_EACH_VEC_ELT (*reg_known_value, i, val)
3538 : {
3539 501622698 : int regno = i + FIRST_PSEUDO_REGISTER;
3540 501622698 : if (! val)
3541 482948931 : set_reg_known_value (regno, regno_reg_rtx[regno]);
3542 : }
3543 :
3544 : /* Clean up. */
3545 9421744 : free (new_reg_base_value);
3546 9421744 : new_reg_base_value = 0;
3547 9421744 : sbitmap_free (reg_seen);
3548 9421744 : reg_seen = 0;
3549 9421744 : timevar_pop (TV_ALIAS_ANALYSIS);
3550 9421744 : }
3551 :
3552 : /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3553 : Special API for var-tracking pass purposes. */
3554 :
3555 : void
3556 498385 : vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
3557 : {
3558 498385 : (*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2);
3559 498385 : }
3560 :
3561 : void
3562 9421744 : end_alias_analysis (void)
3563 : {
3564 9421744 : old_reg_base_value = reg_base_value;
3565 9421744 : vec_free (reg_known_value);
3566 9421744 : sbitmap_free (reg_known_equiv_p);
3567 9421744 : }
3568 :
3569 : void
3570 0 : dump_alias_stats_in_alias_c (FILE *s)
3571 : {
3572 0 : fprintf (s, " TBAA oracle: %llu disambiguations %llu queries\n"
3573 : " %llu are in alias set 0\n"
3574 : " %llu queries asked about the same object\n"
3575 : " %llu queries asked about the same alias set\n"
3576 : " %llu access volatile\n"
3577 : " %llu are dependent in the DAG\n"
3578 : " %llu are aritificially in conflict with void *\n",
3579 : alias_stats.num_disambiguated,
3580 0 : alias_stats.num_alias_zero + alias_stats.num_same_alias_set
3581 0 : + alias_stats.num_same_objects + alias_stats.num_volatile
3582 0 : + alias_stats.num_dag + alias_stats.num_disambiguated
3583 : + alias_stats.num_universal,
3584 : alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
3585 : alias_stats.num_same_objects, alias_stats.num_volatile,
3586 : alias_stats.num_dag, alias_stats.num_universal);
3587 0 : }
3588 : #include "gt-alias.h"
|
