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 REG_BASE_VALUE(X) \
236 : (REGNO (X) < vec_safe_length (reg_base_value) \
237 : ? (*reg_base_value)[REGNO (X)] : 0)
238 :
239 : /* Vector indexed by N giving the initial (unchanging) value known for
240 : pseudo-register N. This vector is initialized in init_alias_analysis,
241 : and does not change until end_alias_analysis is called. */
242 : static GTY(()) vec<rtx, va_gc> *reg_known_value;
243 :
244 : /* Vector recording for each reg_known_value whether it is due to a
245 : REG_EQUIV note. Future passes (viz., reload) may replace the
246 : pseudo with the equivalent expression and so we account for the
247 : dependences that would be introduced if that happens.
248 :
249 : The REG_EQUIV notes created in assign_parms may mention the arg
250 : pointer, and there are explicit insns in the RTL that modify the
251 : arg pointer. Thus we must ensure that such insns don't get
252 : scheduled across each other because that would invalidate the
253 : REG_EQUIV notes. One could argue that the REG_EQUIV notes are
254 : wrong, but solving the problem in the scheduler will likely give
255 : better code, so we do it here. */
256 : static sbitmap reg_known_equiv_p;
257 :
258 : /* True when scanning insns from the start of the rtl to the
259 : NOTE_INSN_FUNCTION_BEG note. */
260 : static bool copying_arguments;
261 :
262 :
263 : /* The splay-tree used to store the various alias set entries. */
264 : static GTY (()) vec<alias_set_entry *, va_gc> *alias_sets;
265 :
266 : /* Build a decomposed reference object for querying the alias-oracle
267 : from the MEM rtx and store it in *REF.
268 : Returns false if MEM is not suitable for the alias-oracle. */
269 :
270 : static bool
271 455797298 : ao_ref_from_mem (ao_ref *ref, const_rtx mem)
272 : {
273 455797298 : tree expr = MEM_EXPR (mem);
274 455797298 : tree base;
275 :
276 455797298 : if (!expr)
277 : return false;
278 :
279 414496403 : ao_ref_init (ref, expr);
280 :
281 : /* Get the base of the reference and see if we have to reject or
282 : adjust it. */
283 414496403 : base = ao_ref_base (ref);
284 414496403 : if (base == NULL_TREE)
285 : return false;
286 :
287 : /* The tree oracle doesn't like bases that are neither decls
288 : nor indirect references of SSA names. */
289 447787675 : if (!(DECL_P (base)
290 226264853 : || (TREE_CODE (base) == MEM_REF
291 193142133 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
292 : || (TREE_CODE (base) == TARGET_MEM_REF
293 33093106 : && TREE_CODE (TMR_BASE (base)) == SSA_NAME)))
294 : return false;
295 :
296 414297324 : ref->ref_alias_set = MEM_ALIAS_SET (mem);
297 :
298 : /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
299 : is conservative, so trust it. */
300 414297324 : if (!MEM_OFFSET_KNOWN_P (mem)
301 414297324 : || !MEM_SIZE_KNOWN_P (mem))
302 : return true;
303 :
304 : /* If MEM_OFFSET/MEM_SIZE get us outside of ref->offset/ref->max_size
305 : drop ref->ref. */
306 405083224 : if (maybe_lt (MEM_OFFSET (mem), 0)
307 405083224 : || (ref->max_size_known_p ()
308 361243501 : && maybe_gt ((MEM_OFFSET (mem) + MEM_SIZE (mem)) * BITS_PER_UNIT,
309 : ref->max_size)))
310 41508771 : ref->ref = NULL_TREE;
311 :
312 : /* Refine size and offset we got from analyzing MEM_EXPR by using
313 : MEM_SIZE and MEM_OFFSET. */
314 :
315 405083224 : ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
316 405083224 : ref->size = MEM_SIZE (mem) * BITS_PER_UNIT;
317 :
318 : /* The MEM may extend into adjacent fields, so adjust max_size if
319 : necessary. */
320 405083224 : if (ref->max_size_known_p ())
321 361243546 : ref->max_size = upper_bound (ref->max_size, ref->size);
322 :
323 : /* If MEM_OFFSET and MEM_SIZE might get us outside of the base object of
324 : the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
325 405083224 : if (MEM_EXPR (mem) != get_spill_slot_decl (false)
326 405083224 : && (maybe_lt (ref->offset, 0)
327 363678758 : || (DECL_P (ref->base)
328 138358687 : && (DECL_SIZE (ref->base) == NULL_TREE
329 138239950 : || !poly_int_tree_p (DECL_SIZE (ref->base))
330 138239900 : || maybe_lt (wi::to_poly_offset (DECL_SIZE (ref->base)),
331 543195303 : ref->offset + ref->size)))))
332 127821 : return false;
333 :
334 : return true;
335 : }
336 :
337 : /* Query the alias-oracle on whether the two memory rtx X and MEM may
338 : alias. If TBAA_P is set also apply TBAA. Returns true if the
339 : two rtxen may alias, false otherwise. */
340 :
341 : static bool
342 238687250 : rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
343 : {
344 238687250 : ao_ref ref1, ref2;
345 :
346 238687250 : if (!ao_ref_from_mem (&ref1, x)
347 238687250 : || !ao_ref_from_mem (&ref2, mem))
348 41627795 : return true;
349 :
350 197059455 : return refs_may_alias_p_1 (&ref1, &ref2,
351 : tbaa_p
352 145145260 : && MEM_ALIAS_SET (x) != 0
353 481831295 : && MEM_ALIAS_SET (mem) != 0);
354 : }
355 :
356 : /* Return true if the ref EARLIER behaves the same as LATER with respect
357 : to TBAA for every memory reference that might follow LATER. */
358 :
359 : bool
360 273737 : refs_same_for_tbaa_p (tree earlier, tree later)
361 : {
362 273737 : ao_ref earlier_ref, later_ref;
363 273737 : ao_ref_init (&earlier_ref, earlier);
364 273737 : ao_ref_init (&later_ref, later);
365 273737 : alias_set_type earlier_set = ao_ref_alias_set (&earlier_ref);
366 273737 : alias_set_type later_set = ao_ref_alias_set (&later_ref);
367 331705 : if (!(earlier_set == later_set
368 57968 : || alias_set_subset_of (later_set, earlier_set)))
369 : return false;
370 269496 : alias_set_type later_base_set = ao_ref_base_alias_set (&later_ref);
371 269496 : alias_set_type earlier_base_set = ao_ref_base_alias_set (&earlier_ref);
372 269496 : return (earlier_base_set == later_base_set
373 269496 : || alias_set_subset_of (later_base_set, earlier_base_set));
374 : }
375 :
376 : /* Similar to refs_same_for_tbaa_p() but for use on MEM rtxs. */
377 : bool
378 140321 : mems_same_for_tbaa_p (rtx earlier, rtx later)
379 : {
380 140321 : gcc_assert (MEM_P (earlier));
381 140321 : gcc_assert (MEM_P (later));
382 :
383 140322 : return ((MEM_ALIAS_SET (earlier) == MEM_ALIAS_SET (later)
384 47749 : || alias_set_subset_of (MEM_ALIAS_SET (later),
385 47749 : MEM_ALIAS_SET (earlier)))
386 277683 : && (!MEM_EXPR (earlier)
387 130541 : || refs_same_for_tbaa_p (MEM_EXPR (earlier), MEM_EXPR (later))));
388 : }
389 :
390 : /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
391 : such an entry, or NULL otherwise. */
392 :
393 : static inline alias_set_entry *
394 273300254 : get_alias_set_entry (alias_set_type alias_set)
395 : {
396 546600508 : return (*alias_sets)[alias_set];
397 : }
398 :
399 : /* Returns true if the alias sets for MEM1 and MEM2 are such that
400 : the two MEMs cannot alias each other. */
401 :
402 : static inline bool
403 245266861 : mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
404 : {
405 245266861 : return (flag_strict_aliasing
406 399796149 : && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1),
407 154529288 : MEM_ALIAS_SET (mem2)));
408 : }
409 :
410 : /* Return true if the first alias set is a subset of the second. */
411 :
412 : bool
413 400242 : alias_set_subset_of (alias_set_type set1, alias_set_type set2)
414 : {
415 400242 : alias_set_entry *ase2;
416 :
417 : /* Disable TBAA oracle with !flag_strict_aliasing. */
418 400242 : if (!flag_strict_aliasing)
419 : return true;
420 :
421 : /* Everything is a subset of the "aliases everything" set. */
422 332106 : if (set2 == 0)
423 : return true;
424 :
425 : /* Check if set1 is a subset of set2. */
426 260630 : ase2 = get_alias_set_entry (set2);
427 260630 : if (ase2 != 0
428 260630 : && (ase2->has_zero_child
429 235760 : || (ase2->children && ase2->children->get (set1))))
430 209983 : return true;
431 :
432 : /* As a special case we consider alias set of "void *" to be both subset
433 : and superset of every alias set of a pointer. This extra symmetry does
434 : not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p
435 : to return true on the following testcase:
436 :
437 : void *ptr;
438 : char **ptr2=(char **)&ptr;
439 : *ptr2 = ...
440 :
441 : Additionally if a set contains universal pointer, we consider every pointer
442 : to be a subset of it, but we do not represent this explicitly - doing so
443 : would require us to update transitive closure each time we introduce new
444 : pointer type. This makes aliasing_component_refs_p to return true
445 : on the following testcase:
446 :
447 : struct a {void *ptr;}
448 : char **ptr = (char **)&a.ptr;
449 : ptr = ...
450 :
451 : This makes void * truly universal pointer type. See pointer handling in
452 : get_alias_set for more details. */
453 50647 : if (ase2 && ase2->has_pointer)
454 : {
455 35877 : alias_set_entry *ase1 = get_alias_set_entry (set1);
456 :
457 35877 : if (ase1 && ase1->is_pointer)
458 : {
459 5791 : alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
460 : /* If one is ptr_type_node and other is pointer, then we consider
461 : them subset of each other. */
462 5791 : if (set1 == voidptr_set || set2 == voidptr_set)
463 5630 : return true;
464 : /* If SET2 contains universal pointer's alias set, then we consider
465 : every (non-universal) pointer. */
466 5186 : if (ase2->children && set1 != voidptr_set
467 5186 : && ase2->children->get (voidptr_set))
468 : return true;
469 : }
470 : }
471 : return false;
472 : }
473 :
474 : /* Return true if the two specified alias sets may conflict. */
475 :
476 : bool
477 321501392 : alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
478 : {
479 321501392 : alias_set_entry *ase1;
480 321501392 : alias_set_entry *ase2;
481 :
482 : /* The easy case. */
483 321501392 : if (alias_sets_must_conflict_p (set1, set2))
484 : return true;
485 :
486 : /* See if the first alias set is a subset of the second. */
487 137498242 : ase1 = get_alias_set_entry (set1);
488 137498242 : if (ase1 != 0
489 137498242 : && ase1->children && ase1->children->get (set2))
490 : {
491 7355736 : ++alias_stats.num_dag;
492 7355736 : return true;
493 : }
494 :
495 : /* Now do the same, but with the alias sets reversed. */
496 130142506 : ase2 = get_alias_set_entry (set2);
497 130142506 : if (ase2 != 0
498 130142506 : && ase2->children && ase2->children->get (set1))
499 : {
500 7093961 : ++alias_stats.num_dag;
501 7093961 : return true;
502 : }
503 :
504 : /* We want void * to be compatible with any other pointer without
505 : really dropping it to alias set 0. Doing so would make it
506 : compatible with all non-pointer types too.
507 :
508 : This is not strictly necessary by the C/C++ language
509 : standards, but avoids common type punning mistakes. In
510 : addition to that, we need the existence of such universal
511 : pointer to implement Fortran's C_PTR type (which is defined as
512 : type compatible with all C pointers). */
513 123048545 : if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer)
514 : {
515 17906562 : alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
516 :
517 : /* If one of the sets corresponds to universal pointer,
518 : we consider it to conflict with anything that is
519 : or contains pointer. */
520 17906562 : if (set1 == voidptr_set || set2 == voidptr_set)
521 : {
522 3548698 : ++alias_stats.num_universal;
523 4550021 : return true;
524 : }
525 : /* If one of sets is (non-universal) pointer and the other
526 : contains universal pointer, we also get conflict. */
527 14357864 : if (ase1->is_pointer && set2 != voidptr_set
528 14357864 : && ase2->children && ase2->children->get (voidptr_set))
529 : {
530 726538 : ++alias_stats.num_universal;
531 726538 : return true;
532 : }
533 13631326 : if (ase2->is_pointer && set1 != voidptr_set
534 13631326 : && ase1->children && ase1->children->get (voidptr_set))
535 : {
536 274785 : ++alias_stats.num_universal;
537 274785 : return true;
538 : }
539 : }
540 :
541 118498524 : ++alias_stats.num_disambiguated;
542 :
543 : /* The two alias sets are distinct and neither one is the
544 : child of the other. Therefore, they cannot conflict. */
545 118498524 : return false;
546 : }
547 :
548 : /* Return true if the two specified alias sets will always conflict. */
549 :
550 : bool
551 321517545 : alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
552 : {
553 : /* Disable TBAA oracle with !flag_strict_aliasing. */
554 321517545 : if (!flag_strict_aliasing)
555 : return true;
556 316764881 : if (set1 == 0 || set2 == 0)
557 : {
558 108401101 : ++alias_stats.num_alias_zero;
559 108401101 : return true;
560 : }
561 208363780 : if (set1 == set2)
562 : {
563 70864894 : ++alias_stats.num_same_alias_set;
564 70864894 : return true;
565 : }
566 :
567 : return false;
568 : }
569 :
570 : /* Return true if any MEM object of type T1 will always conflict (using the
571 : dependency routines in this file) with any MEM object of type T2.
572 : This is used when allocating temporary storage. If T1 and/or T2 are
573 : NULL_TREE, it means we know nothing about the storage. */
574 :
575 : bool
576 10238338 : objects_must_conflict_p (tree t1, tree t2)
577 : {
578 10238338 : alias_set_type set1, set2;
579 :
580 : /* If neither has a type specified, we don't know if they'll conflict
581 : because we may be using them to store objects of various types, for
582 : example the argument and local variables areas of inlined functions. */
583 10238338 : if (t1 == 0 && t2 == 0)
584 : return false;
585 :
586 : /* If they are the same type, they must conflict. */
587 64748 : if (t1 == t2)
588 : {
589 48625 : ++alias_stats.num_same_objects;
590 48625 : return true;
591 : }
592 : /* Likewise if both are volatile. */
593 16123 : if (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2))
594 : {
595 0 : ++alias_stats.num_volatile;
596 0 : return true;
597 : }
598 :
599 16123 : set1 = t1 ? get_alias_set (t1) : 0;
600 16123 : set2 = t2 ? get_alias_set (t2) : 0;
601 :
602 : /* We can't use alias_sets_conflict_p because we must make sure
603 : that every subtype of t1 will conflict with every subtype of
604 : t2 for which a pair of subobjects of these respective subtypes
605 : overlaps on the stack. */
606 16123 : return alias_sets_must_conflict_p (set1, set2);
607 : }
608 :
609 : /* Return true if T is an end of the access path which can be used
610 : by type based alias oracle. */
611 :
612 : bool
613 511413173 : ends_tbaa_access_path_p (const_tree t)
614 : {
615 511413173 : switch (TREE_CODE (t))
616 : {
617 379992900 : case COMPONENT_REF:
618 379992900 : if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
619 : return true;
620 : /* Permit type-punning when accessing a union, provided the access
621 : is directly through the union. For example, this code does not
622 : permit taking the address of a union member and then storing
623 : through it. Even the type-punning allowed here is a GCC
624 : extension, albeit a common and useful one; the C standard says
625 : that such accesses have implementation-defined behavior. */
626 376498974 : else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE)
627 : return true;
628 : break;
629 :
630 126213044 : case ARRAY_REF:
631 126213044 : case ARRAY_RANGE_REF:
632 126213044 : if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
633 : return true;
634 : break;
635 :
636 : case REALPART_EXPR:
637 : case IMAGPART_EXPR:
638 : break;
639 :
640 : case BIT_FIELD_REF:
641 : case VIEW_CONVERT_EXPR:
642 : /* Bitfields and casts are never addressable. */
643 : return true;
644 0 : break;
645 :
646 0 : default:
647 0 : gcc_unreachable ();
648 : }
649 : return false;
650 : }
651 :
652 : /* Return the outermost parent of component present in the chain of
653 : component references handled by get_inner_reference in T with the
654 : following property:
655 : - the component is non-addressable
656 : or NULL_TREE if no such parent exists. In the former cases, the alias
657 : set of this parent is the alias set that must be used for T itself. */
658 :
659 : tree
660 1160374347 : component_uses_parent_alias_set_from (const_tree t)
661 : {
662 1160374347 : const_tree found = NULL_TREE;
663 :
664 1639677662 : while (handled_component_p (t))
665 : {
666 479303315 : if (ends_tbaa_access_path_p (t))
667 15088028 : found = t;
668 :
669 479303315 : t = TREE_OPERAND (t, 0);
670 : }
671 :
672 1160374347 : if (found)
673 14864102 : return TREE_OPERAND (found, 0);
674 :
675 : return NULL_TREE;
676 : }
677 :
678 :
679 : /* Return whether the pointer-type T effective for aliasing may
680 : access everything and thus the reference has to be assigned
681 : alias-set zero. */
682 :
683 : static bool
684 1023494525 : ref_all_alias_ptr_type_p (const_tree t)
685 : {
686 1023494525 : return (VOID_TYPE_P (TREE_TYPE (t))
687 1023494525 : || TYPE_REF_CAN_ALIAS_ALL (t));
688 : }
689 :
690 : /* Return the alias set for the memory pointed to by T, which may be
691 : either a type or an expression. Return -1 if there is nothing
692 : special about dereferencing T. */
693 :
694 : static alias_set_type
695 143678945 : get_deref_alias_set_1 (tree t)
696 : {
697 : /* All we care about is the type. */
698 143678945 : if (! TYPE_P (t))
699 14 : t = TREE_TYPE (t);
700 :
701 : /* If we have an INDIRECT_REF via a void pointer, we don't
702 : know anything about what that might alias. Likewise if the
703 : pointer is marked that way. */
704 143678945 : if (ref_all_alias_ptr_type_p (t))
705 28210073 : return 0;
706 :
707 : return -1;
708 : }
709 :
710 : /* Return the alias set for the memory pointed to by T, which may be
711 : either a type or an expression. */
712 :
713 : alias_set_type
714 216218907 : get_deref_alias_set (tree t)
715 : {
716 : /* If we're not doing any alias analysis, just assume everything
717 : aliases everything else. */
718 216218907 : if (!flag_strict_aliasing)
719 : return 0;
720 :
721 143678945 : alias_set_type set = get_deref_alias_set_1 (t);
722 :
723 : /* Fall back to the alias-set of the pointed-to type. */
724 143678945 : if (set == -1)
725 : {
726 115468872 : if (! TYPE_P (t))
727 14 : t = TREE_TYPE (t);
728 115468872 : set = get_alias_set (TREE_TYPE (t));
729 : }
730 :
731 : return set;
732 : }
733 :
734 : /* Return the pointer-type relevant for TBAA purposes from the
735 : memory reference tree *T or NULL_TREE in which case *T is
736 : adjusted to point to the outermost component reference that
737 : can be used for assigning an alias set. */
738 :
739 : tree
740 1345370351 : reference_alias_ptr_type_1 (tree *t)
741 : {
742 1345370351 : tree inner;
743 :
744 : /* Get the base object of the reference. */
745 1345370351 : inner = *t;
746 1811186024 : while (handled_component_p (inner))
747 : {
748 : /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
749 : the type of any component references that wrap it to
750 : determine the alias-set. */
751 465815673 : if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
752 1636859 : *t = TREE_OPERAND (inner, 0);
753 465815673 : inner = TREE_OPERAND (inner, 0);
754 : }
755 :
756 : /* Handle pointer dereferences here, they can override the
757 : alias-set. */
758 1345370351 : if (INDIRECT_REF_P (inner)
759 1345370351 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 0))))
760 0 : return TREE_TYPE (TREE_OPERAND (inner, 0));
761 1345370351 : else if (TREE_CODE (inner) == TARGET_MEM_REF)
762 55989254 : return TREE_TYPE (TMR_OFFSET (inner));
763 1289381097 : else if (TREE_CODE (inner) == MEM_REF
764 1289381097 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 1))))
765 30581101 : return TREE_TYPE (TREE_OPERAND (inner, 1));
766 :
767 : /* If the innermost reference is a MEM_REF that has a
768 : conversion embedded treat it like a VIEW_CONVERT_EXPR above,
769 : using the memory access type for determining the alias-set. */
770 1258799996 : if (view_converted_memref_p (inner))
771 : {
772 129678554 : tree alias_ptrtype = TREE_TYPE (TREE_OPERAND (inner, 1));
773 : /* Unless we have the (aggregate) effective type of the access
774 : somewhere on the access path. If we have for example
775 : (&a->elts[i])->l.len exposed by abstraction we'd see
776 : MEM <A> [(B *)a].elts[i].l.len and we can use the alias set
777 : of 'len' when typeof (MEM <A> [(B *)a].elts[i]) == B for
778 : example. See PR111715. */
779 129678554 : tree inner = *t;
780 129678554 : while (handled_component_p (inner)
781 130492155 : && (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
782 2118699 : != TYPE_MAIN_VARIANT (TREE_TYPE (alias_ptrtype))))
783 813601 : inner = TREE_OPERAND (inner, 0);
784 129678554 : if (TREE_CODE (inner) == MEM_REF)
785 : return alias_ptrtype;
786 : }
787 :
788 : /* Otherwise, pick up the outermost object that we could have
789 : a pointer to. */
790 1130426540 : tree tem = component_uses_parent_alias_set_from (*t);
791 1130426540 : if (tem)
792 13688960 : *t = tem;
793 :
794 : return NULL_TREE;
795 : }
796 :
797 : /* Return the pointer-type relevant for TBAA purposes from the
798 : gimple memory reference tree T. This is the type to be used for
799 : the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
800 : and guarantees that get_alias_set will return the same alias
801 : set for T and the replacement. */
802 :
803 : tree
804 9880977 : reference_alias_ptr_type (tree t)
805 : {
806 : /* If the frontend assigns this alias-set zero, preserve that. */
807 9880977 : if (lang_hooks.get_alias_set (t) == 0)
808 0 : return ptr_type_node;
809 :
810 9880977 : tree ptype = reference_alias_ptr_type_1 (&t);
811 : /* If there is a given pointer type for aliasing purposes, return it. */
812 9880977 : if (ptype != NULL_TREE)
813 : return ptype;
814 :
815 : /* Otherwise build one from the outermost component reference we
816 : may use. */
817 9132987 : if (TREE_CODE (t) == MEM_REF
818 9132987 : || TREE_CODE (t) == TARGET_MEM_REF)
819 1194900 : return TREE_TYPE (TREE_OPERAND (t, 1));
820 : else
821 7938087 : return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t)));
822 : }
823 :
824 : /* Return whether the pointer-types T1 and T2 used to determine
825 : two alias sets of two references will yield the same answer
826 : from get_deref_alias_set. */
827 :
828 : bool
829 15646646 : alias_ptr_types_compatible_p (tree t1, tree t2)
830 : {
831 15646646 : if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
832 : return true;
833 :
834 2466707 : if (ref_all_alias_ptr_type_p (t1)
835 2466707 : || ref_all_alias_ptr_type_p (t2))
836 : return false;
837 :
838 : /* This function originally abstracts from simply comparing
839 : get_deref_alias_set so that we are sure this still computes
840 : the same result after LTO type merging is applied.
841 : When in LTO type merging is done we can actually do this compare.
842 : */
843 2395297 : if (in_lto_p)
844 5413 : return get_deref_alias_set (t1) == get_deref_alias_set (t2);
845 : else
846 2389884 : return (TYPE_MAIN_VARIANT (TREE_TYPE (t1))
847 2389884 : == TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
848 : }
849 :
850 : /* Create empty alias set entry. */
851 :
852 : alias_set_entry *
853 1249464 : init_alias_set_entry (alias_set_type set)
854 : {
855 1249464 : alias_set_entry *ase = ggc_alloc<alias_set_entry> ();
856 1249464 : ase->alias_set = set;
857 1249464 : ase->children = NULL;
858 1249464 : ase->has_zero_child = false;
859 1249464 : ase->is_pointer = false;
860 1249464 : ase->has_pointer = false;
861 1249464 : gcc_checking_assert (!get_alias_set_entry (set));
862 1249464 : (*alias_sets)[set] = ase;
863 1249464 : return ase;
864 : }
865 :
866 : /* Return the alias set for T, which may be either a type or an
867 : expression. Call language-specific routine for help, if needed. */
868 :
869 : alias_set_type
870 1646698728 : get_alias_set (tree t)
871 : {
872 1646698728 : alias_set_type set;
873 :
874 : /* We cannot give up with -fno-strict-aliasing because we need to build
875 : proper type representations for possible functions which are built with
876 : -fstrict-aliasing. */
877 :
878 : /* return 0 if this or its type is an error. */
879 1646698728 : if (t == error_mark_node
880 1646698728 : || (! TYPE_P (t)
881 1335148162 : && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
882 : return 0;
883 :
884 : /* We can be passed either an expression or a type. This and the
885 : language-specific routine may make mutually-recursive calls to each other
886 : to figure out what to do. At each juncture, we see if this is a tree
887 : that the language may need to handle specially. First handle things that
888 : aren't types. */
889 1646698728 : if (! TYPE_P (t))
890 : {
891 : /* Give the language a chance to do something with this tree
892 : before we look at it. */
893 1335148162 : STRIP_NOPS (t);
894 1335148162 : set = lang_hooks.get_alias_set (t);
895 1335148162 : if (set != -1)
896 : return set;
897 :
898 : /* Get the alias pointer-type to use or the outermost object
899 : that we could have a pointer to. */
900 1335148162 : tree ptype = reference_alias_ptr_type_1 (&t);
901 1335148162 : if (ptype != NULL)
902 214191760 : return get_deref_alias_set (ptype);
903 :
904 : /* If we've already determined the alias set for a decl, just return
905 : it. This is necessary for C++ anonymous unions, whose component
906 : variables don't look like union members (boo!). */
907 1120956402 : if (VAR_P (t)
908 1120956402 : && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
909 161462764 : return MEM_ALIAS_SET (DECL_RTL (t));
910 :
911 : /* Now all we care about is the type. */
912 1040225020 : t = TREE_TYPE (t);
913 : }
914 :
915 : /* Variant qualifiers don't affect the alias set, so get the main
916 : variant. */
917 1351775586 : t = TYPE_MAIN_VARIANT (t);
918 :
919 1351775586 : if (AGGREGATE_TYPE_P (t)
920 1351775586 : && TYPE_TYPELESS_STORAGE (t))
921 : return 0;
922 :
923 : /* Always use the canonical type as well. If this is a type that
924 : requires structural comparisons to identify compatible types
925 : use alias set zero. */
926 1236933713 : if (TYPE_STRUCTURAL_EQUALITY_P (t))
927 : {
928 : /* Allow the language to specify another alias set for this
929 : type. */
930 262552644 : set = lang_hooks.get_alias_set (t);
931 262552644 : if (set != -1)
932 : return set;
933 : /* Handle structure type equality for pointer types, arrays and vectors.
934 : This is easy to do, because the code below ignores canonical types on
935 : these anyway. This is important for LTO, where TYPE_CANONICAL for
936 : pointers cannot be meaningfully computed by the frontend. */
937 262089483 : if (canonical_type_used_p (t))
938 : {
939 : /* In LTO we set canonical types for all types where it makes
940 : sense to do so. Double check we did not miss some type. */
941 178778108 : gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
942 : return 0;
943 : }
944 : }
945 : else
946 : {
947 974381069 : t = TYPE_CANONICAL (t);
948 974381069 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
949 974381069 : if (t != TYPE_MAIN_VARIANT (t))
950 : {
951 2 : t = TYPE_MAIN_VARIANT (t);
952 2 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
953 : }
954 : }
955 :
956 : /* If this is a type with a known alias set, return it. */
957 1057692444 : gcc_checking_assert (t == TYPE_MAIN_VARIANT (t));
958 1057692444 : if (TYPE_ALIAS_SET_KNOWN_P (t))
959 989813816 : return TYPE_ALIAS_SET (t);
960 :
961 : /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
962 67878628 : if (!COMPLETE_TYPE_P (t))
963 : {
964 : /* For arrays with unknown size the conservative answer is the
965 : alias set of the element type. */
966 15649449 : if (TREE_CODE (t) == ARRAY_TYPE)
967 15601348 : return get_alias_set (TREE_TYPE (t));
968 :
969 : /* But return zero as a conservative answer for incomplete types. */
970 : return 0;
971 : }
972 :
973 : /* See if the language has special handling for this type. */
974 52229179 : set = lang_hooks.get_alias_set (t);
975 52229179 : if (set != -1)
976 : return set;
977 :
978 : /* There are no objects of FUNCTION_TYPE, so there's no point in
979 : using up an alias set for them. (There are, of course, pointers
980 : and references to functions, but that's different.) */
981 2638953 : else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
982 : set = 0;
983 :
984 : /* Unless the language specifies otherwise, let vector types alias
985 : their components. This avoids some nasty type punning issues in
986 : normal usage. And indeed lets vectors be treated more like an
987 : array slice. */
988 2634685 : else if (TREE_CODE (t) == VECTOR_TYPE)
989 94778 : set = get_alias_set (TREE_TYPE (t));
990 :
991 : /* Unless the language specifies otherwise, treat array types the
992 : same as their components. This avoids the asymmetry we get
993 : through recording the components. Consider accessing a
994 : character(kind=1) through a reference to a character(kind=1)[1:1].
995 : Or consider if we want to assign integer(kind=4)[0:D.1387] and
996 : integer(kind=4)[4] the same alias set or not.
997 : Just be pragmatic here and make sure the array and its element
998 : type get the same alias set assigned. */
999 2539907 : else if (TREE_CODE (t) == ARRAY_TYPE
1000 2539907 : && (!TYPE_NONALIASED_COMPONENT (t)
1001 0 : || TYPE_STRUCTURAL_EQUALITY_P (t)))
1002 404310 : set = get_alias_set (TREE_TYPE (t));
1003 :
1004 : /* From the former common C and C++ langhook implementation:
1005 :
1006 : Unfortunately, there is no canonical form of a pointer type.
1007 : In particular, if we have `typedef int I', then `int *', and
1008 : `I *' are different types. So, we have to pick a canonical
1009 : representative. We do this below.
1010 :
1011 : Technically, this approach is actually more conservative that
1012 : it needs to be. In particular, `const int *' and `int *'
1013 : should be in different alias sets, according to the C and C++
1014 : standard, since their types are not the same, and so,
1015 : technically, an `int **' and `const int **' cannot point at
1016 : the same thing.
1017 :
1018 : But, the standard is wrong. In particular, this code is
1019 : legal C++:
1020 :
1021 : int *ip;
1022 : int **ipp = &ip;
1023 : const int* const* cipp = ipp;
1024 : And, it doesn't make sense for that to be legal unless you
1025 : can dereference IPP and CIPP. So, we ignore cv-qualifiers on
1026 : the pointed-to types. This issue has been reported to the
1027 : C++ committee.
1028 :
1029 : For this reason go to canonical type of the unqalified pointer type.
1030 : Until GCC 6 this code set all pointers sets to have alias set of
1031 : ptr_type_node but that is a bad idea, because it prevents disabiguations
1032 : in between pointers. For Firefox this accounts about 20% of all
1033 : disambiguations in the program. */
1034 2135597 : else if (POINTER_TYPE_P (t) && t != ptr_type_node)
1035 : {
1036 692058 : tree p;
1037 692058 : auto_vec <bool, 8> reference;
1038 :
1039 : /* Unnest all pointers and references.
1040 : We also want to make pointer to array/vector equivalent to pointer to
1041 : its element (see the reasoning above). Skip all those types, too. */
1042 692058 : for (p = t; POINTER_TYPE_P (p)
1043 759186 : || (TREE_CODE (p) == ARRAY_TYPE
1044 65853 : && (!TYPE_NONALIASED_COMPONENT (p)
1045 0 : || !COMPLETE_TYPE_P (p)
1046 0 : || TYPE_STRUCTURAL_EQUALITY_P (p)))
1047 2222300 : || TREE_CODE (p) == VECTOR_TYPE;
1048 836909 : p = TREE_TYPE (p))
1049 : {
1050 : /* Ada supports recursive pointers. Instead of doing recursion
1051 : check, just give up once the preallocated space of 8 elements
1052 : is up. In this case just punt to void * alias set. */
1053 836976 : if (reference.length () == 8)
1054 : {
1055 67 : p = ptr_type_node;
1056 67 : break;
1057 : }
1058 836909 : if (TREE_CODE (p) == REFERENCE_TYPE)
1059 : /* In LTO we want languages that use references to be compatible
1060 : with languages that use pointers. */
1061 52427 : reference.safe_push (true && !in_lto_p);
1062 836909 : if (TREE_CODE (p) == POINTER_TYPE)
1063 717326 : reference.safe_push (false);
1064 : }
1065 692058 : p = TYPE_MAIN_VARIANT (p);
1066 :
1067 : /* In LTO for C++ programs we can turn incomplete types to complete
1068 : using ODR name lookup. */
1069 692058 : if (in_lto_p && TYPE_STRUCTURAL_EQUALITY_P (p) && odr_type_p (p))
1070 : {
1071 296 : p = prevailing_odr_type (p);
1072 296 : gcc_checking_assert (TYPE_MAIN_VARIANT (p) == p);
1073 : }
1074 :
1075 : /* Make void * compatible with char * and also void **.
1076 : Programs are commonly violating TBAA by this.
1077 :
1078 : We also make void * to conflict with every pointer
1079 : (see record_component_aliases) and thus it is safe it to use it for
1080 : pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
1081 692058 : if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
1082 135609 : set = get_alias_set (ptr_type_node);
1083 : else
1084 : {
1085 : /* Rebuild pointer type starting from canonical types using
1086 : unqualified pointers and references only. This way all such
1087 : pointers will have the same alias set and will conflict with
1088 : each other.
1089 :
1090 : Most of time we already have pointers or references of a given type.
1091 : If not we build new one just to be sure that if someone later
1092 : (probably only middle-end can, as we should assign all alias
1093 : classes only after finishing translation unit) builds the pointer
1094 : type, the canonical type will match. */
1095 556449 : p = TYPE_CANONICAL (p);
1096 1165530 : while (!reference.is_empty ())
1097 : {
1098 609081 : if (reference.pop ())
1099 50416 : p = build_reference_type (p);
1100 : else
1101 558665 : p = build_pointer_type (p);
1102 609081 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1103 : /* build_pointer_type should always return the canonical type.
1104 : For LTO TYPE_CANONICAL may be NULL, because we do not compute
1105 : them. Be sure that frontends do not glob canonical types of
1106 : pointers in unexpected way and that p == TYPE_CANONICAL (p)
1107 : in all other cases. */
1108 609081 : gcc_checking_assert (!TYPE_CANONICAL (p)
1109 : || p == TYPE_CANONICAL (p));
1110 : }
1111 :
1112 : /* Assign the alias set to both p and t.
1113 : We cannot call get_alias_set (p) here as that would trigger
1114 : infinite recursion when p == t. In other cases it would just
1115 : trigger unnecessary legwork of rebuilding the pointer again. */
1116 556449 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1117 556449 : if (TYPE_ALIAS_SET_KNOWN_P (p))
1118 72362 : set = TYPE_ALIAS_SET (p);
1119 : else
1120 : {
1121 484087 : set = new_alias_set ();
1122 484087 : TYPE_ALIAS_SET (p) = set;
1123 : }
1124 : }
1125 692058 : }
1126 : /* Alias set of ptr_type_node is special and serve as universal pointer which
1127 : is TBAA compatible with every other pointer type. Be sure we have the
1128 : alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
1129 : of pointer types NULL. */
1130 1443539 : else if (t == ptr_type_node)
1131 65849 : set = new_alias_set ();
1132 :
1133 : /* Otherwise make a new alias set for this type. */
1134 : else
1135 : {
1136 : /* Each canonical type gets its own alias set, so canonical types
1137 : shouldn't form a tree. It doesn't really matter for types
1138 : we handle specially above, so only check it where it possibly
1139 : would result in a bogus alias set. */
1140 1377690 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
1141 :
1142 1377690 : set = new_alias_set ();
1143 : }
1144 :
1145 2638953 : TYPE_ALIAS_SET (t) = set;
1146 :
1147 : /* If this is an aggregate type or a complex type, we must record any
1148 : component aliasing information. */
1149 2638953 : if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
1150 1203731 : record_component_aliases (t);
1151 :
1152 : /* We treat pointer types specially in alias_set_subset_of. */
1153 2638953 : if (POINTER_TYPE_P (t) && set)
1154 : {
1155 757907 : alias_set_entry *ase = get_alias_set_entry (set);
1156 757907 : if (!ase)
1157 549936 : ase = init_alias_set_entry (set);
1158 757907 : ase->is_pointer = true;
1159 757907 : ase->has_pointer = true;
1160 : }
1161 :
1162 : return set;
1163 : }
1164 :
1165 : /* Return a brand-new alias set. */
1166 :
1167 : alias_set_type
1168 1989874 : new_alias_set (void)
1169 : {
1170 1989874 : if (alias_sets == 0)
1171 211079 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1172 1989874 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1173 1989874 : return alias_sets->length () - 1;
1174 : }
1175 :
1176 : /* Indicate that things in SUBSET can alias things in SUPERSET, but that
1177 : not everything that aliases SUPERSET also aliases SUBSET. For example,
1178 : in C, a store to an `int' can alias a load of a structure containing an
1179 : `int', and vice versa. But it can't alias a load of a 'double' member
1180 : of the same structure. Here, the structure would be the SUPERSET and
1181 : `int' the SUBSET. This relationship is also described in the comment at
1182 : the beginning of this file.
1183 :
1184 : This function should be called only once per SUPERSET/SUBSET pair.
1185 :
1186 : It is illegal for SUPERSET to be zero; everything is implicitly a
1187 : subset of alias set zero. */
1188 :
1189 : void
1190 2089753 : record_alias_subset (alias_set_type superset, alias_set_type subset)
1191 : {
1192 2089753 : alias_set_entry *superset_entry;
1193 2089753 : alias_set_entry *subset_entry;
1194 :
1195 : /* It is possible in complex type situations for both sets to be the same,
1196 : in which case we can ignore this operation. */
1197 2089753 : if (superset == subset)
1198 : return;
1199 :
1200 2089753 : gcc_assert (superset);
1201 :
1202 2089753 : superset_entry = get_alias_set_entry (superset);
1203 2089753 : if (superset_entry == 0)
1204 : {
1205 : /* Create an entry for the SUPERSET, so that we have a place to
1206 : attach the SUBSET. */
1207 699528 : superset_entry = init_alias_set_entry (superset);
1208 : }
1209 :
1210 2089753 : if (subset == 0)
1211 86039 : superset_entry->has_zero_child = 1;
1212 : else
1213 : {
1214 2003714 : if (!superset_entry->children)
1215 688863 : superset_entry->children
1216 688863 : = hash_map<alias_set_hash, int>::create_ggc (64);
1217 :
1218 : /* Enter the SUBSET itself as a child of the SUPERSET. If it was
1219 : already there we're done. */
1220 2003714 : if (superset_entry->children->put (subset, 0))
1221 : return;
1222 :
1223 1265875 : subset_entry = get_alias_set_entry (subset);
1224 : /* If there is an entry for the subset, enter all of its children
1225 : (if they are not already present) as children of the SUPERSET. */
1226 1265875 : if (subset_entry)
1227 : {
1228 746462 : if (subset_entry->has_zero_child)
1229 16845 : superset_entry->has_zero_child = true;
1230 746462 : if (subset_entry->has_pointer)
1231 592365 : superset_entry->has_pointer = true;
1232 :
1233 746462 : if (subset_entry->children)
1234 : {
1235 326428 : hash_map<alias_set_hash, int>::iterator iter
1236 326428 : = subset_entry->children->begin ();
1237 603181816 : for (; iter != subset_entry->children->end (); ++iter)
1238 301101266 : superset_entry->children->put ((*iter).first, (*iter).second);
1239 : }
1240 : }
1241 : }
1242 : }
1243 :
1244 : /* Record that component types of TYPE, if any, are part of SUPERSET for
1245 : aliasing purposes. For record types, we only record component types
1246 : for fields that are not marked non-addressable. For array types, we
1247 : only record the component type if it is not marked non-aliased. */
1248 :
1249 : void
1250 1289689 : record_component_aliases (tree type, alias_set_type superset)
1251 : {
1252 1289689 : tree field;
1253 :
1254 1289689 : if (superset == 0)
1255 : return;
1256 :
1257 1242385 : switch (TREE_CODE (type))
1258 : {
1259 794136 : case RECORD_TYPE:
1260 794136 : case UNION_TYPE:
1261 794136 : case QUAL_UNION_TYPE:
1262 794136 : {
1263 : /* LTO non-ODR type merging does not make any difference between
1264 : component pointer types. We may have
1265 :
1266 : struct foo {int *a;};
1267 :
1268 : as TYPE_CANONICAL of
1269 :
1270 : struct bar {float *a;};
1271 :
1272 : Because accesses to int * and float * do not alias, we would get
1273 : false negative when accessing the same memory location by
1274 : float ** and bar *. We thus record the canonical type as:
1275 :
1276 : struct {void *a;};
1277 :
1278 : void * is special cased and works as a universal pointer type.
1279 : Accesses to it conflicts with accesses to any other pointer
1280 : type. */
1281 794136 : bool void_pointers = in_lto_p
1282 794136 : && (!odr_type_p (type)
1283 6423 : || !odr_based_tbaa_p (type));
1284 15121349 : for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
1285 14327213 : if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
1286 : {
1287 2084452 : tree t = TREE_TYPE (field);
1288 2084452 : if (void_pointers)
1289 : {
1290 : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1291 : element type and that type has to be normalized to void *,
1292 : too, in the case it is a pointer. */
1293 27314 : while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
1294 : {
1295 1795 : gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
1296 1795 : t = TREE_TYPE (t);
1297 : }
1298 23724 : if (POINTER_TYPE_P (t))
1299 6800 : t = ptr_type_node;
1300 16924 : else if (flag_checking)
1301 16924 : gcc_checking_assert (get_alias_set (t)
1302 : == get_alias_set (TREE_TYPE (field)));
1303 : }
1304 :
1305 2084452 : alias_set_type set = get_alias_set (t);
1306 2084452 : record_alias_subset (superset, set);
1307 : /* If the field has alias-set zero make sure to still record
1308 : any components of it. This makes sure that for
1309 : struct A {
1310 : struct B {
1311 : int i;
1312 : char c[4];
1313 : } b;
1314 : };
1315 : in C++ even though 'B' has alias-set zero because
1316 : TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of
1317 : 'int' as subset. */
1318 2084452 : if (set == 0)
1319 85958 : record_component_aliases (t, superset);
1320 : }
1321 : }
1322 : break;
1323 :
1324 5301 : case COMPLEX_TYPE:
1325 5301 : record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
1326 5301 : break;
1327 :
1328 : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1329 : element type. */
1330 :
1331 : default:
1332 : break;
1333 : }
1334 : }
1335 :
1336 : /* Record that component types of TYPE, if any, are part of that type for
1337 : aliasing purposes. For record types, we only record component types
1338 : for fields that are not marked non-addressable. For array types, we
1339 : only record the component type if it is not marked non-aliased. */
1340 :
1341 : void
1342 1203731 : record_component_aliases (tree type)
1343 : {
1344 1203731 : alias_set_type superset = get_alias_set (type);
1345 1203731 : record_component_aliases (type, superset);
1346 1203731 : }
1347 :
1348 :
1349 : /* Allocate an alias set for use in storing and reading from the varargs
1350 : spill area. */
1351 :
1352 : static GTY(()) alias_set_type varargs_set = -1;
1353 :
1354 : alias_set_type
1355 21143 : get_varargs_alias_set (void)
1356 : {
1357 : #if 1
1358 : /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1359 : varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1360 : consistently use the varargs alias set for loads from the varargs
1361 : area. So don't use it anywhere. */
1362 21143 : return 0;
1363 : #else
1364 : if (varargs_set == -1)
1365 : varargs_set = new_alias_set ();
1366 :
1367 : return varargs_set;
1368 : #endif
1369 : }
1370 :
1371 : /* Likewise, but used for the fixed portions of the frame, e.g., register
1372 : save areas. */
1373 :
1374 : static GTY(()) alias_set_type frame_set = -1;
1375 :
1376 : alias_set_type
1377 1251412 : get_frame_alias_set (void)
1378 : {
1379 1251412 : if (frame_set == -1)
1380 24996 : frame_set = new_alias_set ();
1381 :
1382 1251412 : return frame_set;
1383 : }
1384 :
1385 : /* Create a new, unique base with id ID. */
1386 :
1387 : static rtx
1388 1972335 : unique_base_value (HOST_WIDE_INT id)
1389 : {
1390 2039145 : return gen_rtx_ADDRESS (Pmode, id);
1391 : }
1392 :
1393 : /* Return true if accesses based on any other base value cannot alias
1394 : those based on X. */
1395 :
1396 : static bool
1397 168862996 : unique_base_value_p (rtx x)
1398 : {
1399 195468058 : return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode;
1400 : }
1401 :
1402 : /* Inside SRC, the source of a SET, find a base address. */
1403 :
1404 : static rtx
1405 454854683 : find_base_value (rtx src)
1406 : {
1407 544426440 : unsigned int regno;
1408 544426440 : scalar_int_mode int_mode;
1409 :
1410 : #if defined (FIND_BASE_TERM)
1411 : /* Try machine-dependent ways to find the base term. */
1412 544426440 : src = FIND_BASE_TERM (src);
1413 : #endif
1414 :
1415 544426440 : switch (GET_CODE (src))
1416 : {
1417 : case SYMBOL_REF:
1418 : case LABEL_REF:
1419 : return src;
1420 :
1421 174635099 : case REG:
1422 174635099 : regno = REGNO (src);
1423 : /* At the start of a function, argument registers have known base
1424 : values which may be lost later. Returning an ADDRESS
1425 : expression here allows optimization based on argument values
1426 : even when the argument registers are used for other purposes. */
1427 174635099 : if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1428 19721559 : return new_reg_base_value[regno];
1429 :
1430 : /* If a pseudo has a known base value, return it. Do not do this
1431 : for non-fixed hard regs since it can result in a circular
1432 : dependency chain for registers which have values at function entry.
1433 :
1434 : The test above is not sufficient because the scheduler may move
1435 : a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1436 95531869 : if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1437 123708069 : && regno < vec_safe_length (reg_base_value))
1438 : {
1439 : /* If we're inside init_alias_analysis, use new_reg_base_value
1440 : to reduce the number of relaxation iterations. */
1441 123708069 : if (new_reg_base_value && new_reg_base_value[regno]
1442 84783582 : && DF_REG_DEF_COUNT (regno) == 1)
1443 : return new_reg_base_value[regno];
1444 :
1445 88509160 : if ((*reg_base_value)[regno])
1446 : return (*reg_base_value)[regno];
1447 : }
1448 :
1449 : return 0;
1450 :
1451 105992854 : case MEM:
1452 : /* Check for an argument passed in memory. Only record in the
1453 : copying-arguments block; it is too hard to track changes
1454 : otherwise. */
1455 105992854 : if (copying_arguments
1456 4160804 : && (XEXP (src, 0) == arg_pointer_rtx
1457 3001881 : || (GET_CODE (XEXP (src, 0)) == PLUS
1458 2985784 : && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1459 2827230 : return arg_base_value;
1460 : return 0;
1461 :
1462 1025579 : case CONST:
1463 1025579 : src = XEXP (src, 0);
1464 1025579 : if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1465 : break;
1466 :
1467 : /* fall through */
1468 :
1469 111510353 : case PLUS:
1470 111510353 : case MINUS:
1471 111510353 : {
1472 111510353 : rtx src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1473 :
1474 : /* If either operand is a CONST_INT, then the other is the base. */
1475 111510353 : if (CONST_INT_P (src_1))
1476 : return find_base_value (src_0);
1477 23359290 : else if (CONST_INT_P (src_0))
1478 : return find_base_value (src_1);
1479 :
1480 : return 0;
1481 : }
1482 :
1483 0 : case LO_SUM:
1484 : /* The standard form is (lo_sum reg sym) so look only at the
1485 : second operand. */
1486 0 : return find_base_value (XEXP (src, 1));
1487 :
1488 5568238 : case AND:
1489 : /* Look through aligning ANDs. And AND with zero or one with
1490 : the LSB set isn't one (see for example PR92462). */
1491 5568238 : if (CONST_INT_P (XEXP (src, 1))
1492 3533428 : && INTVAL (XEXP (src, 1)) != 0
1493 3502770 : && (INTVAL (XEXP (src, 1)) & 1) == 0)
1494 1343827 : return find_base_value (XEXP (src, 0));
1495 : return 0;
1496 :
1497 13935 : case TRUNCATE:
1498 : /* As we do not know which address space the pointer is referring to, we can
1499 : handle this only if the target does not support different pointer or
1500 : address modes depending on the address space. */
1501 13935 : if (!target_default_pointer_address_modes_p ())
1502 : break;
1503 13935 : if (!is_a <scalar_int_mode> (GET_MODE (src), &int_mode)
1504 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1505 : break;
1506 : /* Fall through. */
1507 0 : case HIGH:
1508 0 : case PRE_INC:
1509 0 : case PRE_DEC:
1510 0 : case POST_INC:
1511 0 : case POST_DEC:
1512 0 : case PRE_MODIFY:
1513 0 : case POST_MODIFY:
1514 0 : return find_base_value (XEXP (src, 0));
1515 :
1516 11154706 : case ZERO_EXTEND:
1517 11154706 : case SIGN_EXTEND: /* used for NT/Alpha pointers */
1518 : /* As we do not know which address space the pointer is referring to, we can
1519 : handle this only if the target does not support different pointer or
1520 : address modes depending on the address space. */
1521 11154706 : if (!target_default_pointer_address_modes_p ())
1522 : break;
1523 :
1524 11154706 : {
1525 11154706 : rtx temp = find_base_value (XEXP (src, 0));
1526 :
1527 11154706 : if (temp != 0 && CONSTANT_P (temp))
1528 302 : temp = convert_memory_address (Pmode, temp);
1529 :
1530 : return temp;
1531 : }
1532 :
1533 : default:
1534 : break;
1535 : }
1536 :
1537 : return 0;
1538 : }
1539 :
1540 : /* Called from init_alias_analysis indirectly through note_stores,
1541 : or directly if DEST is a register with a REG_NOALIAS note attached.
1542 : SET is null in the latter case. */
1543 :
1544 : /* While scanning insns to find base values, reg_seen[N] is nonzero if
1545 : register N has been set in this function. */
1546 : static sbitmap reg_seen;
1547 :
1548 : static void
1549 1570496833 : record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1550 : {
1551 1570496833 : unsigned regno;
1552 1570496833 : rtx src;
1553 1570496833 : int n;
1554 :
1555 1570496833 : if (!REG_P (dest))
1556 : return;
1557 :
1558 1182969572 : regno = REGNO (dest);
1559 :
1560 1182969572 : gcc_checking_assert (regno < reg_base_value->length ());
1561 :
1562 1182969572 : n = REG_NREGS (dest);
1563 1182969572 : if (n != 1)
1564 : {
1565 21119439 : while (--n >= 0)
1566 : {
1567 14079626 : bitmap_set_bit (reg_seen, regno + n);
1568 14079626 : new_reg_base_value[regno + n] = 0;
1569 : }
1570 : return;
1571 : }
1572 :
1573 1175929759 : if (set)
1574 : {
1575 : /* A CLOBBER wipes out any old value but does not prevent a previously
1576 : unset register from acquiring a base address (i.e. reg_seen is not
1577 : set). */
1578 1174273411 : if (GET_CODE (set) == CLOBBER)
1579 : {
1580 193459816 : new_reg_base_value[regno] = 0;
1581 193459816 : return;
1582 : }
1583 :
1584 980813595 : src = SET_SRC (set);
1585 : }
1586 : else
1587 : {
1588 : /* There's a REG_NOALIAS note against DEST. */
1589 1656348 : if (bitmap_bit_p (reg_seen, regno))
1590 : {
1591 559169 : new_reg_base_value[regno] = 0;
1592 559169 : return;
1593 : }
1594 1097179 : bitmap_set_bit (reg_seen, regno);
1595 1097179 : new_reg_base_value[regno] = unique_base_value (unique_id++);
1596 1097179 : return;
1597 : }
1598 :
1599 : /* If this is not the first set of REGNO, see whether the new value
1600 : is related to the old one. There are two cases of interest:
1601 :
1602 : (1) The register might be assigned an entirely new value
1603 : that has the same base term as the original set.
1604 :
1605 : (2) The set might be a simple self-modification that
1606 : cannot change REGNO's base value.
1607 :
1608 : If neither case holds, reject the original base value as invalid.
1609 : Note that the following situation is not detected:
1610 :
1611 : extern int x, y; int *p = &x; p += (&y-&x);
1612 :
1613 : ANSI C does not allow computing the difference of addresses
1614 : of distinct top level objects. */
1615 980813595 : if (new_reg_base_value[regno] != 0
1616 980813595 : && find_base_value (src) != new_reg_base_value[regno])
1617 89641117 : switch (GET_CODE (src))
1618 : {
1619 522106 : case LO_SUM:
1620 522106 : case MINUS:
1621 522106 : if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1622 77612 : new_reg_base_value[regno] = 0;
1623 : break;
1624 25918931 : case PLUS:
1625 : /* If the value we add in the PLUS is also a valid base value,
1626 : this might be the actual base value, and the original value
1627 : an index. */
1628 25918931 : {
1629 25918931 : rtx other = NULL_RTX;
1630 :
1631 25918931 : if (XEXP (src, 0) == dest)
1632 22088228 : other = XEXP (src, 1);
1633 3830703 : else if (XEXP (src, 1) == dest)
1634 : other = XEXP (src, 0);
1635 :
1636 22193779 : if (! other || find_base_value (other))
1637 3730275 : new_reg_base_value[regno] = 0;
1638 : break;
1639 : }
1640 75411 : case AND:
1641 75411 : if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1642 67471 : new_reg_base_value[regno] = 0;
1643 : break;
1644 63124669 : default:
1645 63124669 : new_reg_base_value[regno] = 0;
1646 63124669 : break;
1647 : }
1648 : /* If this is the first set of a register, record the value. */
1649 565132179 : else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1650 1303965323 : && ! bitmap_bit_p (reg_seen, regno) && new_reg_base_value[regno] == 0)
1651 295779734 : new_reg_base_value[regno] = find_base_value (src);
1652 :
1653 980813595 : bitmap_set_bit (reg_seen, regno);
1654 : }
1655 :
1656 : /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1657 : using hard registers with non-null REG_BASE_VALUE for renaming. */
1658 : rtx
1659 1505 : get_reg_base_value (unsigned int regno)
1660 : {
1661 1505 : return (*reg_base_value)[regno];
1662 : }
1663 :
1664 : /* If a value is known for REGNO, return it. */
1665 :
1666 : rtx
1667 291582577 : get_reg_known_value (unsigned int regno)
1668 : {
1669 291582577 : if (regno >= FIRST_PSEUDO_REGISTER)
1670 : {
1671 275575289 : regno -= FIRST_PSEUDO_REGISTER;
1672 275575289 : if (regno < vec_safe_length (reg_known_value))
1673 256063498 : return (*reg_known_value)[regno];
1674 : }
1675 : return NULL;
1676 : }
1677 :
1678 : /* Set it. */
1679 :
1680 : static void
1681 612648544 : set_reg_known_value (unsigned int regno, rtx val)
1682 : {
1683 612648544 : if (regno >= FIRST_PSEUDO_REGISTER)
1684 : {
1685 612648544 : regno -= FIRST_PSEUDO_REGISTER;
1686 612648544 : if (regno < vec_safe_length (reg_known_value))
1687 612648544 : (*reg_known_value)[regno] = val;
1688 : }
1689 612648544 : }
1690 :
1691 : /* Similarly for reg_known_equiv_p. */
1692 :
1693 : bool
1694 39751 : get_reg_known_equiv_p (unsigned int regno)
1695 : {
1696 39751 : if (regno >= FIRST_PSEUDO_REGISTER)
1697 : {
1698 39751 : regno -= FIRST_PSEUDO_REGISTER;
1699 39751 : if (regno < vec_safe_length (reg_known_value))
1700 39129 : return bitmap_bit_p (reg_known_equiv_p, regno);
1701 : }
1702 : return false;
1703 : }
1704 :
1705 : static void
1706 42125912 : set_reg_known_equiv_p (unsigned int regno, bool val)
1707 : {
1708 42125912 : if (regno >= FIRST_PSEUDO_REGISTER)
1709 : {
1710 42125912 : regno -= FIRST_PSEUDO_REGISTER;
1711 42125912 : if (regno < vec_safe_length (reg_known_value))
1712 : {
1713 42125912 : if (val)
1714 0 : bitmap_set_bit (reg_known_equiv_p, regno);
1715 : else
1716 42125912 : bitmap_clear_bit (reg_known_equiv_p, regno);
1717 : }
1718 : }
1719 42125912 : }
1720 :
1721 :
1722 : /* Returns a canonical version of X, from the point of view alias
1723 : analysis. (For example, if X is a MEM whose address is a register,
1724 : and the register has a known value (say a SYMBOL_REF), then a MEM
1725 : whose address is the SYMBOL_REF is returned.) */
1726 :
1727 : rtx
1728 5533779930 : canon_rtx (rtx x)
1729 : {
1730 : /* Recursively look for equivalences. */
1731 5537963401 : if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1732 : {
1733 247580944 : rtx t = get_reg_known_value (REGNO (x));
1734 247580944 : if (t == x)
1735 : return x;
1736 23695262 : if (t)
1737 : return canon_rtx (t);
1738 : }
1739 :
1740 5309894248 : if (GET_CODE (x) == PLUS)
1741 : {
1742 1546920846 : rtx x0 = canon_rtx (XEXP (x, 0));
1743 1546920846 : rtx x1 = canon_rtx (XEXP (x, 1));
1744 :
1745 1546920846 : if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1746 3155002 : return simplify_gen_binary (PLUS, GET_MODE (x), x0, x1);
1747 : }
1748 :
1749 : /* This gives us much better alias analysis when called from
1750 : the loop optimizer. Note we want to leave the original
1751 : MEM alone, but need to return the canonicalized MEM with
1752 : all the flags with their original values. */
1753 3762973402 : else if (MEM_P (x))
1754 331002274 : x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1755 :
1756 : return x;
1757 : }
1758 :
1759 : /* Return true if X and Y are identical-looking rtx's.
1760 : Expect that X and Y has been already canonicalized.
1761 :
1762 : We use the data in reg_known_value above to see if two registers with
1763 : different numbers are, in fact, equivalent. */
1764 :
1765 : static bool
1766 8854985005 : rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1767 : {
1768 8855078276 : int i;
1769 8855078276 : int j;
1770 8855078276 : enum rtx_code code;
1771 8855078276 : const char *fmt;
1772 :
1773 8855078276 : if (x == 0 && y == 0)
1774 : return true;
1775 8855078276 : if (x == 0 || y == 0)
1776 : return false;
1777 :
1778 8855078276 : if (x == y)
1779 : return true;
1780 :
1781 7128204009 : code = GET_CODE (x);
1782 : /* Rtx's of different codes cannot be equal. */
1783 7128204009 : if (code != GET_CODE (y))
1784 : return false;
1785 :
1786 : /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1787 : (REG:SI x) and (REG:HI x) are NOT equivalent. */
1788 :
1789 4833934151 : if (GET_MODE (x) != GET_MODE (y))
1790 : return false;
1791 :
1792 : /* Some RTL can be compared without a recursive examination. */
1793 4833933894 : switch (code)
1794 : {
1795 253077419 : case REG:
1796 253077419 : return REGNO (x) == REGNO (y);
1797 :
1798 0 : case LABEL_REF:
1799 0 : return label_ref_label (x) == label_ref_label (y);
1800 :
1801 3892818 : case SYMBOL_REF:
1802 3892818 : {
1803 3892818 : HOST_WIDE_INT distance = 0;
1804 3892818 : return (compare_base_symbol_refs (x, y, &distance) == 1
1805 3892818 : && distance == 0);
1806 : }
1807 :
1808 2149023 : case ENTRY_VALUE:
1809 : /* This is magic, don't go through canonicalization et al. */
1810 2149023 : return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1811 :
1812 : case VALUE:
1813 : CASE_CONST_UNIQUE:
1814 : /* Pointer equality guarantees equality for these nodes. */
1815 : return false;
1816 :
1817 1392079770 : default:
1818 1392079770 : break;
1819 : }
1820 :
1821 : /* canon_rtx knows how to handle plus. No need to canonicalize. */
1822 1392079770 : if (code == PLUS)
1823 1370926444 : return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1824 661246053 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1825 2023097119 : || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1826 213241 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1827 : /* For commutative operations, the RTX match if the operand match in any
1828 : order. Also handle the simple binary and unary cases without a loop. */
1829 21153326 : if (COMMUTATIVE_P (x))
1830 : {
1831 4467659 : rtx xop0 = canon_rtx (XEXP (x, 0));
1832 4467659 : rtx yop0 = canon_rtx (XEXP (y, 0));
1833 4467659 : rtx yop1 = canon_rtx (XEXP (y, 1));
1834 :
1835 4467659 : return ((rtx_equal_for_memref_p (xop0, yop0)
1836 1554967 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1837 4608020 : || (rtx_equal_for_memref_p (xop0, yop1)
1838 30 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1839 : }
1840 16685667 : else if (NON_COMMUTATIVE_P (x))
1841 : {
1842 125110 : return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1843 125110 : canon_rtx (XEXP (y, 0)))
1844 162461 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1845 37351 : canon_rtx (XEXP (y, 1))));
1846 : }
1847 16560557 : else if (UNARY_P (x))
1848 93271 : return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1849 186542 : canon_rtx (XEXP (y, 0)));
1850 :
1851 : /* Compare the elements. If any pair of corresponding elements
1852 : fail to match, return false for the whole things.
1853 :
1854 : Limit cases to types which actually appear in addresses. */
1855 :
1856 16467286 : fmt = GET_RTX_FORMAT (code);
1857 23737177 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1858 : {
1859 23149411 : switch (fmt[i])
1860 : {
1861 3412750 : case 'i':
1862 3412750 : if (XINT (x, i) != XINT (y, i))
1863 : return false;
1864 : break;
1865 :
1866 152 : case 'L':
1867 152 : if (XLOC (x, i) != XLOC (y, i))
1868 : return false;
1869 : break;
1870 :
1871 54 : case 'p':
1872 54 : if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1873 : return false;
1874 : break;
1875 :
1876 3412702 : case 'E':
1877 : /* Two vectors must have the same length. */
1878 3412702 : if (XVECLEN (x, i) != XVECLEN (y, i))
1879 : return false;
1880 :
1881 : /* And the corresponding elements must match. */
1882 3675768 : for (j = 0; j < XVECLEN (x, i); j++)
1883 3413623 : if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1884 3413623 : canon_rtx (XVECEXP (y, i, j))) == 0)
1885 : return false;
1886 : break;
1887 :
1888 13143426 : case 'e':
1889 13143426 : if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1890 13143426 : canon_rtx (XEXP (y, i))) == 0)
1891 : return false;
1892 : break;
1893 :
1894 : /* This can happen for asm operands. */
1895 0 : case 's':
1896 0 : if (strcmp (XSTR (x, i), XSTR (y, i)))
1897 : return false;
1898 : break;
1899 :
1900 : /* This can happen for an asm which clobbers memory. */
1901 : case '0':
1902 : break;
1903 :
1904 : /* It is believed that rtx's at this level will never
1905 : contain anything but integers and other rtx's,
1906 : except for within LABEL_REFs and SYMBOL_REFs. */
1907 0 : default:
1908 0 : gcc_unreachable ();
1909 : }
1910 : }
1911 : return true;
1912 : }
1913 :
1914 : static rtx
1915 3284150934 : find_base_term (rtx x, vec<std::pair<cselib_val *,
1916 : struct elt_loc_list *> > &visited_vals)
1917 : {
1918 6209294954 : cselib_val *val;
1919 6209294954 : struct elt_loc_list *l, *f;
1920 6209294954 : rtx ret;
1921 6209294954 : scalar_int_mode int_mode;
1922 :
1923 : #if defined (FIND_BASE_TERM)
1924 : /* Try machine-dependent ways to find the base term. */
1925 6209294954 : x = FIND_BASE_TERM (x);
1926 : #endif
1927 :
1928 6209294954 : switch (GET_CODE (x))
1929 : {
1930 2185799483 : case REG:
1931 2185799483 : return REG_BASE_VALUE (x);
1932 :
1933 0 : case TRUNCATE:
1934 : /* As we do not know which address space the pointer is referring to, we can
1935 : handle this only if the target does not support different pointer or
1936 : address modes depending on the address space. */
1937 0 : if (!target_default_pointer_address_modes_p ())
1938 : return 0;
1939 115835595 : if (!is_a <scalar_int_mode> (GET_MODE (x), &int_mode)
1940 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1941 : return 0;
1942 : /* Fall through. */
1943 43467772 : case HIGH:
1944 43467772 : case PRE_INC:
1945 43467772 : case PRE_DEC:
1946 43467772 : case POST_INC:
1947 43467772 : case POST_DEC:
1948 43467772 : case PRE_MODIFY:
1949 43467772 : case POST_MODIFY:
1950 43467772 : return find_base_term (XEXP (x, 0), visited_vals);
1951 :
1952 482 : case ZERO_EXTEND:
1953 482 : case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1954 : /* As we do not know which address space the pointer is referring to, we can
1955 : handle this only if the target does not support different pointer or
1956 : address modes depending on the address space. */
1957 482 : if (!target_default_pointer_address_modes_p ())
1958 : return 0;
1959 :
1960 482 : {
1961 482 : rtx temp = find_base_term (XEXP (x, 0), visited_vals);
1962 :
1963 482 : if (temp != 0 && CONSTANT_P (temp))
1964 0 : temp = convert_memory_address (Pmode, temp);
1965 :
1966 : return temp;
1967 : }
1968 :
1969 838835003 : case VALUE:
1970 838835003 : val = CSELIB_VAL_PTR (x);
1971 838835003 : ret = NULL_RTX;
1972 :
1973 838835003 : if (!val)
1974 : return ret;
1975 :
1976 838835003 : if (cselib_sp_based_value_p (val))
1977 21732880 : return static_reg_base_value[STACK_POINTER_REGNUM];
1978 :
1979 817102123 : if (visited_vals.length () > (unsigned) param_max_find_base_term_values)
1980 : return ret;
1981 :
1982 815100838 : f = val->locs;
1983 : /* Reset val->locs to avoid infinite recursion. */
1984 815100838 : if (f)
1985 650550958 : visited_vals.safe_push (std::make_pair (val, f));
1986 815100838 : val->locs = NULL;
1987 :
1988 1444646958 : for (l = f; l; l = l->next)
1989 809344578 : if (GET_CODE (l->loc) == VALUE
1990 108309403 : && CSELIB_VAL_PTR (l->loc)->locs
1991 108261866 : && !CSELIB_VAL_PTR (l->loc)->locs->next
1992 108217188 : && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
1993 108217188 : continue;
1994 701127390 : else if ((ret = find_base_term (l->loc, visited_vals)) != 0)
1995 : break;
1996 :
1997 : return ret;
1998 :
1999 0 : case LO_SUM:
2000 : /* The standard form is (lo_sum reg sym) so look only at the
2001 : second operand. */
2002 0 : return find_base_term (XEXP (x, 1), visited_vals);
2003 :
2004 43248476 : case CONST:
2005 43248476 : x = XEXP (x, 0);
2006 43248476 : if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
2007 : return 0;
2008 : /* Fall through. */
2009 2889919633 : case PLUS:
2010 2889919633 : case MINUS:
2011 2889919633 : {
2012 2889919633 : rtx tmp1 = XEXP (x, 0);
2013 2889919633 : rtx tmp2 = XEXP (x, 1);
2014 :
2015 : /* This is a little bit tricky since we have to determine which of
2016 : the two operands represents the real base address. Otherwise this
2017 : routine may return the index register instead of the base register.
2018 :
2019 : That may cause us to believe no aliasing was possible, when in
2020 : fact aliasing is possible.
2021 :
2022 : We use a few simple tests to guess the base register. Additional
2023 : tests can certainly be added. For example, if one of the operands
2024 : is a shift or multiply, then it must be the index register and the
2025 : other operand is the base register. */
2026 :
2027 2889919633 : if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
2028 : return find_base_term (tmp2, visited_vals);
2029 :
2030 2889919405 : if (CONST_INT_P (tmp1))
2031 0 : std::swap (tmp1, tmp2);
2032 :
2033 : /* We can only handle binary operators when one of the operands
2034 : never leads to a base value. */
2035 2889919405 : if (CONST_INT_P (tmp2))
2036 : return find_base_term (tmp1, visited_vals);
2037 :
2038 : /* We could not determine which of the two operands was the
2039 : base register and which was the index. So we can determine
2040 : nothing from the base alias check. */
2041 : return 0;
2042 : }
2043 :
2044 61181212 : case AND:
2045 : /* Look through aligning ANDs. And AND with zero or one with
2046 : the LSB set isn't one (see for example PR92462). */
2047 61181212 : if (CONST_INT_P (XEXP (x, 1))
2048 61181129 : && INTVAL (XEXP (x, 1)) != 0
2049 61181129 : && (INTVAL (XEXP (x, 1)) & 1) == 0)
2050 61181125 : return find_base_term (XEXP (x, 0), visited_vals);
2051 : return 0;
2052 :
2053 : case SYMBOL_REF:
2054 : case LABEL_REF:
2055 : return x;
2056 :
2057 : default:
2058 : return 0;
2059 : }
2060 : }
2061 :
2062 : /* Wrapper around the worker above which removes locs from visited VALUEs
2063 : to avoid visiting them multiple times. We unwind that changes here. */
2064 :
2065 : rtx
2066 2583023062 : find_base_term (rtx x)
2067 : {
2068 2583023062 : auto_vec<std::pair<cselib_val *, struct elt_loc_list *>, 32> visited_vals;
2069 2583023062 : rtx res = find_base_term (x, visited_vals);
2070 3233574020 : for (unsigned i = 0; i < visited_vals.length (); ++i)
2071 650550958 : visited_vals[i].first->locs = visited_vals[i].second;
2072 2583023062 : return res;
2073 2583023062 : }
2074 :
2075 : /* Return true if accesses to address X may alias accesses based
2076 : on the stack pointer. */
2077 :
2078 : bool
2079 15248947 : may_be_sp_based_p (rtx x)
2080 : {
2081 15248947 : rtx base = find_base_term (x);
2082 15248947 : return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
2083 : }
2084 :
2085 : /* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2086 : if they refer to different objects and -1 if we cannot decide. */
2087 :
2088 : int
2089 1585534613 : compare_base_decls (tree base1, tree base2)
2090 : {
2091 1585534613 : int ret;
2092 1585534613 : gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2093 1585534613 : if (base1 == base2)
2094 : return 1;
2095 :
2096 : /* If we have two register decls with register specification we
2097 : cannot decide unless their assembler names are the same. */
2098 1376010704 : if (VAR_P (base1)
2099 1324176546 : && VAR_P (base2)
2100 1318375878 : && DECL_HARD_REGISTER (base1)
2101 12714 : && DECL_HARD_REGISTER (base2)
2102 12555 : && DECL_ASSEMBLER_NAME_SET_P (base1)
2103 1376023259 : && DECL_ASSEMBLER_NAME_SET_P (base2))
2104 : {
2105 12555 : if (DECL_ASSEMBLER_NAME_RAW (base1) == DECL_ASSEMBLER_NAME_RAW (base2))
2106 : return 1;
2107 12552 : return -1;
2108 : }
2109 :
2110 : /* Declarations of non-automatic variables may have aliases. All other
2111 : decls are unique. */
2112 1375998149 : if (!decl_in_symtab_p (base1)
2113 1375998149 : || !decl_in_symtab_p (base2))
2114 : return 0;
2115 :
2116 : /* Don't cause symbols to be inserted by the act of checking. */
2117 86945447 : symtab_node *node1 = symtab_node::get (base1);
2118 86945447 : if (!node1)
2119 : return 0;
2120 86925886 : symtab_node *node2 = symtab_node::get (base2);
2121 86925886 : if (!node2)
2122 : return 0;
2123 :
2124 86907158 : ret = node1->equal_address_to (node2, true);
2125 86907158 : return ret;
2126 : }
2127 :
2128 : /* Compare SYMBOL_REFs X_BASE and Y_BASE.
2129 :
2130 : - Return 1 if Y_BASE - X_BASE is constant, adding that constant
2131 : to *DISTANCE if DISTANCE is nonnull.
2132 :
2133 : - Return 0 if no accesses based on X_BASE can alias Y_BASE.
2134 :
2135 : - Return -1 if one of the two results applies, but we can't tell
2136 : which at compile time. Update DISTANCE in the same way as
2137 : for a return value of 1, for the case in which that holds. */
2138 :
2139 : static int
2140 24199167 : compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
2141 : HOST_WIDE_INT *distance)
2142 : {
2143 24199167 : tree x_decl = SYMBOL_REF_DECL (x_base);
2144 24199167 : tree y_decl = SYMBOL_REF_DECL (y_base);
2145 24199167 : bool binds_def = true;
2146 24199167 : bool swap = false;
2147 :
2148 24199167 : if (XSTR (x_base, 0) == XSTR (y_base, 0))
2149 : return 1;
2150 23751162 : if (x_decl && y_decl)
2151 23751162 : return compare_base_decls (x_decl, y_decl);
2152 0 : if (x_decl || y_decl)
2153 : {
2154 : if (!x_decl)
2155 : {
2156 : swap = true;
2157 : std::swap (x_decl, y_decl);
2158 : std::swap (x_base, y_base);
2159 : }
2160 : /* We handle specially only section anchors. Other symbols are
2161 : either equal (via aliasing) or refer to different objects. */
2162 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2163 : return -1;
2164 : /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2165 : to ignore CONST_DECLs because they are readonly. */
2166 0 : if (!VAR_P (x_decl)
2167 0 : || (!TREE_STATIC (x_decl) && !TREE_PUBLIC (x_decl)))
2168 : return 0;
2169 :
2170 0 : symtab_node *x_node = symtab_node::get_create (x_decl)
2171 0 : ->ultimate_alias_target ();
2172 : /* External variable cannot be in section anchor. */
2173 0 : if (!x_node->definition)
2174 : return 0;
2175 0 : x_base = XEXP (DECL_RTL (x_node->decl), 0);
2176 : /* If not in anchor, we can disambiguate. */
2177 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base))
2178 : return 0;
2179 :
2180 : /* We have an alias of anchored variable. If it can be interposed;
2181 : we must assume it may or may not alias its anchor. */
2182 0 : binds_def = decl_binds_to_current_def_p (x_decl);
2183 : }
2184 : /* If we have variable in section anchor, we can compare by offset. */
2185 0 : if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base)
2186 0 : && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2187 : {
2188 0 : if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
2189 : return 0;
2190 0 : if (distance)
2191 0 : *distance += (swap ? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base)
2192 0 : - SYMBOL_REF_BLOCK_OFFSET (x_base));
2193 0 : return binds_def ? 1 : -1;
2194 : }
2195 : /* Either the symbols are equal (via aliasing) or they refer to
2196 : different objects. */
2197 : return -1;
2198 : }
2199 :
2200 : /* Return false if the addresses X and Y are known to point to different
2201 : objects, true if they might be pointers to the same object. */
2202 :
2203 : static bool
2204 1283626904 : base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base,
2205 : machine_mode x_mode, machine_mode y_mode)
2206 : {
2207 : /* If the address itself has no known base see if a known equivalent
2208 : value has one. If either address still has no known base, nothing
2209 : is known about aliasing. */
2210 1283626904 : if (x_base == 0)
2211 : {
2212 168665656 : rtx x_c;
2213 :
2214 168665656 : if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
2215 168481610 : return true;
2216 :
2217 184046 : x_base = find_base_term (x_c);
2218 184046 : if (x_base == 0)
2219 : return true;
2220 : }
2221 :
2222 1114963436 : if (y_base == 0)
2223 : {
2224 170067329 : rtx y_c;
2225 170067329 : if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
2226 170019952 : return true;
2227 :
2228 47377 : y_base = find_base_term (y_c);
2229 47377 : if (y_base == 0)
2230 : return true;
2231 : }
2232 :
2233 : /* If the base addresses are equal nothing is known about aliasing. */
2234 944899037 : if (rtx_equal_p (x_base, y_base))
2235 : return true;
2236 :
2237 : /* The base addresses are different expressions. If they are not accessed
2238 : via AND, there is no conflict. We can bring knowledge of object
2239 : alignment into play here. For example, on alpha, "char a, b;" can
2240 : alias one another, though "char a; long b;" cannot. AND addresses may
2241 : implicitly alias surrounding objects; i.e. unaligned access in DImode
2242 : via AND address can alias all surrounding object types except those
2243 : with alignment 8 or higher. */
2244 145300912 : if (GET_CODE (x) == AND && GET_CODE (y) == AND)
2245 : return true;
2246 145300912 : if (GET_CODE (x) == AND
2247 145300912 : && (!CONST_INT_P (XEXP (x, 1))
2248 2368 : || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
2249 : return true;
2250 145298744 : if (GET_CODE (y) == AND
2251 145298744 : && (!CONST_INT_P (XEXP (y, 1))
2252 1963 : || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
2253 : return true;
2254 :
2255 : /* Differing symbols not accessed via AND never alias. */
2256 145296871 : if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF)
2257 19698456 : return compare_base_symbol_refs (x_base, y_base) != 0;
2258 :
2259 125598415 : if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
2260 : return false;
2261 :
2262 137472242 : if (unique_base_value_p (x_base) || unique_base_value_p (y_base))
2263 : return false;
2264 :
2265 : return true;
2266 : }
2267 :
2268 : /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2269 : (or equal to) that of V. */
2270 :
2271 : static bool
2272 209622202 : refs_newer_value_p (const_rtx expr, rtx v)
2273 : {
2274 209622202 : int minuid = CSELIB_VAL_UID (v);
2275 209622202 : subrtx_iterator::array_type array;
2276 622688535 : FOR_EACH_SUBRTX (iter, array, expr, NONCONST)
2277 521349202 : if (GET_CODE (*iter) == VALUE && CSELIB_VAL_UID (*iter) >= minuid)
2278 108282869 : return true;
2279 101339333 : return false;
2280 209622202 : }
2281 :
2282 : /* Convert the address X into something we can use. This is done by returning
2283 : it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2284 : we call cselib to get a more useful rtx. */
2285 :
2286 : rtx
2287 3924392101 : get_addr (rtx x)
2288 : {
2289 3924392101 : cselib_val *v;
2290 3924392101 : struct elt_loc_list *l;
2291 :
2292 3924392101 : if (GET_CODE (x) != VALUE)
2293 : {
2294 2530986273 : if ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
2295 2127904494 : && GET_CODE (XEXP (x, 0)) == VALUE
2296 120123900 : && CONST_SCALAR_INT_P (XEXP (x, 1)))
2297 : {
2298 113523970 : rtx op0 = get_addr (XEXP (x, 0));
2299 113523970 : if (op0 != XEXP (x, 0))
2300 : {
2301 31267599 : poly_int64 c;
2302 31267599 : if (GET_CODE (x) == PLUS
2303 31267599 : && poly_int_rtx_p (XEXP (x, 1), &c))
2304 31267599 : return plus_constant (GET_MODE (x), op0, c);
2305 0 : return simplify_gen_binary (GET_CODE (x), GET_MODE (x),
2306 0 : op0, XEXP (x, 1));
2307 : }
2308 : }
2309 2499718674 : return x;
2310 : }
2311 1393405828 : v = CSELIB_VAL_PTR (x);
2312 1393405828 : if (v)
2313 : {
2314 1393405828 : bool have_equivs = cselib_have_permanent_equivalences ();
2315 1393405828 : if (have_equivs)
2316 337356894 : v = canonical_cselib_val (v);
2317 2678045044 : for (l = v->locs; l; l = l->next)
2318 1311562989 : if (CONSTANT_P (l->loc))
2319 : return l->loc;
2320 1601160707 : for (l = v->locs; l; l = l->next)
2321 1206422306 : if (!REG_P (l->loc) && !MEM_P (l->loc)
2322 : /* Avoid infinite recursion when potentially dealing with
2323 : var-tracking artificial equivalences, by skipping the
2324 : equivalences themselves, and not choosing expressions
2325 : that refer to newer VALUEs. */
2326 2484423713 : && (!have_equivs
2327 251064760 : || (GET_CODE (l->loc) != VALUE
2328 154600660 : && !refs_newer_value_p (l->loc, x))))
2329 1049558455 : return l->loc;
2330 316923600 : if (have_equivs)
2331 : {
2332 338739875 : for (l = v->locs; l; l = l->next)
2333 114802943 : if (REG_P (l->loc)
2334 114802943 : || (GET_CODE (l->loc) != VALUE
2335 55021542 : && !refs_newer_value_p (l->loc, x)))
2336 6717081 : return l->loc;
2337 : /* Return the canonical value. */
2338 223936932 : return v->val_rtx;
2339 : }
2340 86269587 : if (v->locs)
2341 47743669 : return v->locs->loc;
2342 : }
2343 : return x;
2344 : }
2345 :
2346 : /* Return the address of the (N_REFS + 1)th memory reference to ADDR
2347 : where SIZE is the size in bytes of the memory reference. If ADDR
2348 : is not modified by the memory reference then ADDR is returned. */
2349 :
2350 : static rtx
2351 5426360404 : addr_side_effect_eval (rtx addr, poly_int64 size, int n_refs)
2352 : {
2353 5426360404 : poly_int64 offset = 0;
2354 :
2355 5426360404 : switch (GET_CODE (addr))
2356 : {
2357 0 : case PRE_INC:
2358 0 : offset = (n_refs + 1) * size;
2359 0 : break;
2360 22337047 : case PRE_DEC:
2361 22337047 : offset = -(n_refs + 1) * size;
2362 22337047 : break;
2363 : case POST_INC:
2364 505696 : offset = n_refs * size;
2365 505696 : break;
2366 0 : case POST_DEC:
2367 0 : offset = -n_refs * size;
2368 0 : break;
2369 :
2370 : default:
2371 : return addr;
2372 : }
2373 :
2374 22842743 : addr = plus_constant (GET_MODE (addr), XEXP (addr, 0), offset);
2375 22842743 : addr = canon_rtx (addr);
2376 :
2377 22842743 : return addr;
2378 : }
2379 :
2380 : /* Return TRUE if an object X sized at XSIZE bytes and another object
2381 : Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2382 : any of the sizes is zero, assume an overlap, otherwise use the
2383 : absolute value of the sizes as the actual sizes. */
2384 :
2385 : static inline bool
2386 826049228 : offset_overlap_p (poly_int64 c, poly_int64 xsize, poly_int64 ysize)
2387 : {
2388 825409905 : if (known_eq (xsize, 0) || known_eq (ysize, 0))
2389 : return true;
2390 :
2391 822541858 : if (maybe_ge (c, 0))
2392 495080935 : return maybe_gt (maybe_lt (xsize, 0) ? -xsize : xsize, c);
2393 : else
2394 327460923 : return maybe_gt (maybe_lt (ysize, 0) ? -ysize : ysize, -c);
2395 : }
2396 :
2397 : /* Return one if X and Y (memory addresses) reference the
2398 : same location in memory or if the references overlap.
2399 : Return zero if they do not overlap, else return
2400 : minus one in which case they still might reference the same location.
2401 :
2402 : C is an offset accumulator. When
2403 : C is nonzero, we are testing aliases between X and Y + C.
2404 : XSIZE is the size in bytes of the X reference,
2405 : similarly YSIZE is the size in bytes for Y.
2406 : Expect that canon_rtx has been already called for X and Y.
2407 :
2408 : If XSIZE or YSIZE is zero, we do not know the amount of memory being
2409 : referenced (the reference was BLKmode), so make the most pessimistic
2410 : assumptions.
2411 :
2412 : If XSIZE or YSIZE is negative, we may access memory outside the object
2413 : being referenced as a side effect. This can happen when using AND to
2414 : align memory references, as is done on the Alpha.
2415 :
2416 : Nice to notice that varying addresses cannot conflict with fp if no
2417 : local variables had their addresses taken, but that's too hard now.
2418 :
2419 : ??? Contrary to the tree alias oracle this does not return
2420 : one for X + non-constant and Y + non-constant when X and Y are equal.
2421 : If that is fixed the TBAA hack for union type-punning can be removed. */
2422 :
2423 : static int
2424 1886798883 : memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
2425 : poly_int64 c)
2426 : {
2427 2713180202 : if (GET_CODE (x) == VALUE)
2428 : {
2429 730483304 : if (REG_P (y))
2430 : {
2431 279802013 : struct elt_loc_list *l = NULL;
2432 279802013 : if (CSELIB_VAL_PTR (x))
2433 279802013 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs;
2434 507430365 : l; l = l->next)
2435 363779908 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y))
2436 : break;
2437 279802013 : if (l)
2438 : x = y;
2439 : else
2440 143650457 : x = get_addr (x);
2441 : }
2442 : /* Don't call get_addr if y is the same VALUE. */
2443 450681291 : else if (x != y)
2444 450582112 : x = get_addr (x);
2445 : }
2446 2713180202 : if (GET_CODE (y) == VALUE)
2447 : {
2448 420743297 : if (REG_P (x))
2449 : {
2450 13742984 : struct elt_loc_list *l = NULL;
2451 13742984 : if (CSELIB_VAL_PTR (y))
2452 13742984 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs;
2453 16609880 : l; l = l->next)
2454 2888334 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x))
2455 : break;
2456 13742984 : if (l)
2457 : y = x;
2458 : else
2459 13721546 : y = get_addr (y);
2460 : }
2461 : /* Don't call get_addr if x is the same VALUE. */
2462 407000313 : else if (y != x)
2463 406900496 : y = get_addr (y);
2464 : }
2465 2713180202 : if (GET_CODE (x) == HIGH)
2466 0 : x = XEXP (x, 0);
2467 2713180202 : else if (GET_CODE (x) == LO_SUM)
2468 0 : x = XEXP (x, 1);
2469 : else
2470 2713180202 : x = addr_side_effect_eval (x, maybe_lt (xsize, 0) ? -xsize : xsize, 0);
2471 2713180202 : if (GET_CODE (y) == HIGH)
2472 0 : y = XEXP (y, 0);
2473 2713180202 : else if (GET_CODE (y) == LO_SUM)
2474 0 : y = XEXP (y, 1);
2475 : else
2476 2713180202 : y = addr_side_effect_eval (y, maybe_lt (ysize, 0) ? -ysize : ysize, 0);
2477 :
2478 2713180202 : if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
2479 : {
2480 607893 : HOST_WIDE_INT distance = 0;
2481 607893 : int cmp = compare_base_symbol_refs (x, y, &distance);
2482 :
2483 : /* If both decls are the same, decide by offsets. */
2484 607893 : if (cmp == 1)
2485 895892 : return offset_overlap_p (c + distance, xsize, ysize);
2486 : /* Assume a potential overlap for symbolic addresses that went
2487 : through alignment adjustments (i.e., that have negative
2488 : sizes), because we can't know how far they are from each
2489 : other. */
2490 159887 : if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
2491 : return -1;
2492 : /* If decls are different or we know by offsets that there is no overlap,
2493 : we win. */
2494 767780 : if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
2495 159887 : return 0;
2496 : /* Decls may or may not be different and offsets overlap....*/
2497 : return -1;
2498 : }
2499 2712572309 : else if (rtx_equal_for_memref_p (x, y))
2500 : {
2501 296913555 : return offset_overlap_p (c, xsize, ysize);
2502 : }
2503 :
2504 : /* This code used to check for conflicts involving stack references and
2505 : globals but the base address alias code now handles these cases. */
2506 :
2507 2564105322 : if (GET_CODE (x) == PLUS)
2508 : {
2509 : /* The fact that X is canonicalized means that this
2510 : PLUS rtx is canonicalized. */
2511 1526327245 : rtx x0 = XEXP (x, 0);
2512 1526327245 : rtx x1 = XEXP (x, 1);
2513 :
2514 : /* However, VALUEs might end up in different positions even in
2515 : canonical PLUSes. Comparing their addresses is enough. */
2516 1526327245 : if (x0 == y)
2517 25635045 : return memrefs_conflict_p (xsize, x1, ysize, const0_rtx, c);
2518 1500692200 : else if (x1 == y)
2519 344415 : return memrefs_conflict_p (xsize, x0, ysize, const0_rtx, c);
2520 :
2521 1500347785 : poly_int64 cx1, cy1;
2522 1500347785 : if (GET_CODE (y) == PLUS)
2523 : {
2524 : /* The fact that Y is canonicalized means that this
2525 : PLUS rtx is canonicalized. */
2526 1351586572 : rtx y0 = XEXP (y, 0);
2527 1351586572 : rtx y1 = XEXP (y, 1);
2528 :
2529 1351586572 : if (x0 == y1)
2530 : return memrefs_conflict_p (xsize, x1, ysize, y0, c);
2531 1351482546 : if (x1 == y0)
2532 : return memrefs_conflict_p (xsize, x0, ysize, y1, c);
2533 :
2534 1351411904 : if (rtx_equal_for_memref_p (x1, y1))
2535 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2536 1215273600 : if (rtx_equal_for_memref_p (x0, y0))
2537 : return memrefs_conflict_p (xsize, x1, ysize, y1, c);
2538 569942703 : if (poly_int_rtx_p (x1, &cx1))
2539 : {
2540 1102961120 : poly_offset_int co = c;
2541 551480560 : co -= cx1;
2542 551480560 : if (poly_int_rtx_p (y1, &cy1))
2543 : {
2544 543912104 : co += cy1;
2545 543912104 : if (!co.to_shwi (&c))
2546 : return -1;
2547 543908345 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2548 : }
2549 7568456 : else if (!co.to_shwi (&c))
2550 : return -1;
2551 : else
2552 7568456 : return memrefs_conflict_p (xsize, x0, ysize, y, c);
2553 : }
2554 699638466 : else if (poly_int_rtx_p (y1, &cy1))
2555 : {
2556 28988656 : poly_offset_int co = c;
2557 14494328 : co += cy1;
2558 14494328 : if (!co.to_shwi (&c))
2559 : return -1;
2560 14494328 : return memrefs_conflict_p (xsize, x, ysize, y0, c);
2561 : }
2562 :
2563 : return -1;
2564 : }
2565 148761213 : else if (poly_int_rtx_p (x1, &cx1))
2566 : {
2567 230402870 : poly_offset_int co = c;
2568 115201435 : co -= cx1;
2569 115201435 : if (!co.to_shwi (&c))
2570 : return -1;
2571 115201426 : return memrefs_conflict_p (xsize, x0, ysize, y, c);
2572 : }
2573 : }
2574 1037778077 : else if (GET_CODE (y) == PLUS)
2575 : {
2576 : /* The fact that Y is canonicalized means that this
2577 : PLUS rtx is canonicalized. */
2578 83712122 : rtx y0 = XEXP (y, 0);
2579 83712122 : rtx y1 = XEXP (y, 1);
2580 :
2581 83712122 : if (x == y0)
2582 9439623 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y1, c);
2583 74272499 : if (x == y1)
2584 825152 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y0, c);
2585 :
2586 73447347 : poly_int64 cy1;
2587 130192496 : if (poly_int_rtx_p (y1, &cy1))
2588 : {
2589 113490298 : poly_offset_int co = c;
2590 56745149 : co += cy1;
2591 56745149 : if (!co.to_shwi (&c))
2592 : return -1;
2593 56745149 : return memrefs_conflict_p (xsize, x, ysize, y0, c);
2594 : }
2595 : else
2596 : return -1;
2597 : }
2598 :
2599 987625733 : if (GET_CODE (x) == GET_CODE (y))
2600 798330731 : switch (GET_CODE (x))
2601 : {
2602 306049 : case MULT:
2603 306049 : {
2604 : /* Handle cases where we expect the second operands to be the
2605 : same, and check only whether the first operand would conflict
2606 : or not. */
2607 306049 : rtx x0, y0;
2608 306049 : rtx x1 = canon_rtx (XEXP (x, 1));
2609 306049 : rtx y1 = canon_rtx (XEXP (y, 1));
2610 306049 : if (! rtx_equal_for_memref_p (x1, y1))
2611 : return -1;
2612 287441 : x0 = canon_rtx (XEXP (x, 0));
2613 287441 : y0 = canon_rtx (XEXP (y, 0));
2614 287441 : if (rtx_equal_for_memref_p (x0, y0))
2615 0 : return offset_overlap_p (c, xsize, ysize);
2616 :
2617 : /* Can't properly adjust our sizes. */
2618 287441 : poly_int64 c1;
2619 283011528 : if (!poly_int_rtx_p (x1, &c1)
2620 284530 : || !can_div_trunc_p (xsize, c1, &xsize)
2621 284530 : || !can_div_trunc_p (ysize, c1, &ysize)
2622 284530 : || !can_div_trunc_p (c, c1, &c))
2623 : return -1;
2624 284530 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2625 : }
2626 :
2627 : default:
2628 : break;
2629 : }
2630 :
2631 : /* Deal with alignment ANDs by adjusting offset and size so as to
2632 : cover the maximum range, without taking any previously known
2633 : alignment into account. Make a size negative after such an
2634 : adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2635 : assume a potential overlap, because they may end up in contiguous
2636 : memory locations and the stricter-alignment access may span over
2637 : part of both. */
2638 987319684 : if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2639 : {
2640 4030738 : HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
2641 4030738 : unsigned HOST_WIDE_INT uc = sc;
2642 4030738 : if (sc < 0 && pow2_or_zerop (-uc))
2643 : {
2644 4030298 : if (maybe_gt (xsize, 0))
2645 4029990 : xsize = -xsize;
2646 4030298 : if (maybe_ne (xsize, 0))
2647 : {
2648 4030112 : poly_offset_int xsizeo = xsize;
2649 4030112 : xsizeo += sc + 1;
2650 4030112 : if (!xsizeo.to_shwi (&xsize))
2651 0 : return -1;
2652 : }
2653 4030298 : poly_offset_int co = c;
2654 4030298 : co -= sc + 1;
2655 4030298 : if (!co.to_shwi (&c))
2656 : return -1;
2657 4030298 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2658 4030298 : ysize, y, c);
2659 : }
2660 : }
2661 983289386 : if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2662 : {
2663 5508263 : HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
2664 5508263 : unsigned HOST_WIDE_INT uc = sc;
2665 5508263 : if (sc < 0 && pow2_or_zerop (-uc))
2666 : {
2667 5507032 : if (maybe_gt (ysize, 0))
2668 5505397 : ysize = -ysize;
2669 5507032 : if (maybe_ne (ysize, 0))
2670 : {
2671 5506996 : poly_offset_int ysizeo = ysize;
2672 5506996 : ysizeo += sc + 1;
2673 5506996 : if (!ysizeo.to_shwi (&ysize))
2674 0 : return -1;
2675 : }
2676 5507032 : poly_offset_int co = c;
2677 5507032 : co += sc + 1;
2678 5507032 : if (!co.to_shwi (&c))
2679 : return -1;
2680 5507032 : return memrefs_conflict_p (xsize, x,
2681 5507032 : ysize, canon_rtx (XEXP (y, 0)), c);
2682 : }
2683 : }
2684 :
2685 977782354 : if (CONSTANT_P (x))
2686 : {
2687 695076875 : poly_int64 cx, cy;
2688 695076875 : if (poly_int_rtx_p (x, &cx) && poly_int_rtx_p (y, &cy))
2689 : {
2690 2030951409 : poly_offset_int co = c;
2691 676983803 : co += cy;
2692 676983803 : co -= cx;
2693 676983803 : if (!co.to_shwi (&c))
2694 : return -1;
2695 1353348638 : return offset_overlap_p (c, xsize, ysize);
2696 : }
2697 :
2698 18093072 : if (GET_CODE (x) == CONST)
2699 : {
2700 7312099 : if (GET_CODE (y) == CONST)
2701 5901384 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2702 5901384 : ysize, canon_rtx (XEXP (y, 0)), c);
2703 : else
2704 1410715 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2705 1410715 : ysize, y, c);
2706 : }
2707 10780973 : if (GET_CODE (y) == CONST)
2708 896586 : return memrefs_conflict_p (xsize, x, ysize,
2709 896586 : canon_rtx (XEXP (y, 0)), c);
2710 :
2711 : /* Assume a potential overlap for symbolic addresses that went
2712 : through alignment adjustments (i.e., that have negative
2713 : sizes), because we can't know how far they are from each
2714 : other. */
2715 9884387 : if (CONSTANT_P (y))
2716 27106 : return (maybe_lt (xsize, 0)
2717 27106 : || maybe_lt (ysize, 0)
2718 54212 : || offset_overlap_p (c, xsize, ysize));
2719 :
2720 : return -1;
2721 : }
2722 :
2723 : return -1;
2724 : }
2725 :
2726 : /* Functions to compute memory dependencies.
2727 :
2728 : Since we process the insns in execution order, we can build tables
2729 : to keep track of what registers are fixed (and not aliased), what registers
2730 : are varying in known ways, and what registers are varying in unknown
2731 : ways.
2732 :
2733 : If both memory references are volatile, then there must always be a
2734 : dependence between the two references, since their order cannot be
2735 : changed. A volatile and non-volatile reference can be interchanged
2736 : though.
2737 :
2738 : We also must allow AND addresses, because they may generate accesses
2739 : outside the object being referenced. This is used to generate aligned
2740 : addresses from unaligned addresses, for instance, the alpha
2741 : storeqi_unaligned pattern. */
2742 :
2743 : /* Read dependence: X is read after read in MEM takes place. There can
2744 : only be a dependence here if both reads are volatile, or if either is
2745 : an explicit barrier. */
2746 :
2747 : bool
2748 32182207 : read_dependence (const_rtx mem, const_rtx x)
2749 : {
2750 32182207 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2751 : return true;
2752 31675405 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2753 63335713 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2754 23244 : return true;
2755 : return false;
2756 : }
2757 :
2758 : /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2759 :
2760 : static tree
2761 63095642 : decl_for_component_ref (tree x)
2762 : {
2763 83060009 : do
2764 : {
2765 83060009 : x = TREE_OPERAND (x, 0);
2766 : }
2767 83060009 : while (x && TREE_CODE (x) == COMPONENT_REF);
2768 :
2769 63095642 : return x && DECL_P (x) ? x : NULL_TREE;
2770 : }
2771 :
2772 : /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2773 : for the offset of the field reference. *KNOWN_P says whether the
2774 : offset is known. */
2775 :
2776 : static void
2777 9536981 : adjust_offset_for_component_ref (tree x, bool *known_p,
2778 : poly_int64 *offset)
2779 : {
2780 9536981 : if (!*known_p)
2781 : return;
2782 11480663 : do
2783 : {
2784 11480663 : tree xoffset = component_ref_field_offset (x);
2785 11480663 : tree field = TREE_OPERAND (x, 1);
2786 11480663 : if (!poly_int_tree_p (xoffset))
2787 : {
2788 0 : *known_p = false;
2789 0 : return;
2790 : }
2791 :
2792 11480663 : poly_offset_int woffset
2793 11480663 : = (wi::to_poly_offset (xoffset)
2794 11480663 : + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field))
2795 22961326 : >> LOG2_BITS_PER_UNIT)
2796 11480663 : + *offset);
2797 11480663 : if (!woffset.to_shwi (offset))
2798 : {
2799 0 : *known_p = false;
2800 0 : return;
2801 : }
2802 :
2803 11480663 : x = TREE_OPERAND (x, 0);
2804 : }
2805 11480663 : while (x && TREE_CODE (x) == COMPONENT_REF);
2806 : }
2807 :
2808 : /* Return true if we can determine the exprs corresponding to memrefs
2809 : X and Y and they do not overlap.
2810 : If LOOP_VARIANT is set, skip offset-based disambiguation */
2811 :
2812 : bool
2813 250372215 : nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2814 : {
2815 269903598 : tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2816 250372215 : rtx rtlx, rtly;
2817 250372215 : rtx basex, basey;
2818 250372215 : bool moffsetx_known_p, moffsety_known_p;
2819 250372215 : poly_int64 moffsetx = 0, moffsety = 0;
2820 250372215 : poly_int64 offsetx = 0, offsety = 0, sizex, sizey;
2821 :
2822 : /* Unless both have exprs, we can't tell anything. */
2823 250372215 : if (exprx == 0 || expry == 0)
2824 : return false;
2825 :
2826 : /* For spill-slot accesses make sure we have valid offsets. */
2827 209011064 : if ((exprx == get_spill_slot_decl (false)
2828 15934612 : && ! MEM_OFFSET_KNOWN_P (x))
2829 224945676 : || (expry == get_spill_slot_decl (false)
2830 27318544 : && ! MEM_OFFSET_KNOWN_P (y)))
2831 0 : return false;
2832 :
2833 : /* If the field reference test failed, look at the DECLs involved. */
2834 209011064 : moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2835 209011064 : if (moffsetx_known_p)
2836 206491450 : moffsetx = MEM_OFFSET (x);
2837 209011064 : if (TREE_CODE (exprx) == COMPONENT_REF)
2838 : {
2839 37505482 : tree t = decl_for_component_ref (exprx);
2840 37505482 : if (! t)
2841 : return false;
2842 4598888 : adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx);
2843 4598888 : exprx = t;
2844 : }
2845 :
2846 176104470 : moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2847 176104470 : if (moffsety_known_p)
2848 173976632 : moffsety = MEM_OFFSET (y);
2849 176104470 : if (TREE_CODE (expry) == COMPONENT_REF)
2850 : {
2851 25590160 : tree t = decl_for_component_ref (expry);
2852 25590160 : if (! t)
2853 : return false;
2854 4938093 : adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety);
2855 4938093 : expry = t;
2856 : }
2857 :
2858 155452403 : if (! DECL_P (exprx) || ! DECL_P (expry))
2859 : return false;
2860 :
2861 : /* If we refer to different gimple registers, or one gimple register
2862 : and one non-gimple-register, we know they can't overlap. First,
2863 : gimple registers don't have their addresses taken. Now, there
2864 : could be more than one stack slot for (different versions of) the
2865 : same gimple register, but we can presumably tell they don't
2866 : overlap based on offsets from stack base addresses elsewhere.
2867 : It's important that we don't proceed to DECL_RTL, because gimple
2868 : registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2869 : able to do anything about them since no SSA information will have
2870 : remained to guide it. */
2871 13859428 : if (is_gimple_reg (exprx) || is_gimple_reg (expry))
2872 3815248 : return exprx != expry
2873 3815248 : || (moffsetx_known_p && moffsety_known_p
2874 246716 : && MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y)
2875 246716 : && !offset_overlap_p (moffsety - moffsetx,
2876 123358 : MEM_SIZE (x), MEM_SIZE (y)));
2877 :
2878 : /* With invalid code we can end up storing into the constant pool.
2879 : Bail out to avoid ICEing when creating RTL for this.
2880 : See gfortran.dg/lto/20091028-2_0.f90. */
2881 10044180 : if (TREE_CODE (exprx) == CONST_DECL
2882 10044180 : || TREE_CODE (expry) == CONST_DECL)
2883 : return true;
2884 :
2885 : /* If one decl is known to be a function or label in a function and
2886 : the other is some kind of data, they can't overlap. */
2887 10044180 : if ((TREE_CODE (exprx) == FUNCTION_DECL
2888 10044180 : || TREE_CODE (exprx) == LABEL_DECL)
2889 : != (TREE_CODE (expry) == FUNCTION_DECL
2890 10044180 : || TREE_CODE (expry) == LABEL_DECL))
2891 : return true;
2892 :
2893 : /* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2894 : living in multiple places), we can't tell anything. Exception
2895 : are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2896 9859402 : if ((!DECL_RTL_SET_P (exprx) && TREE_CODE (exprx) != FUNCTION_DECL)
2897 19718804 : || (!DECL_RTL_SET_P (expry) && TREE_CODE (expry) != FUNCTION_DECL))
2898 : return false;
2899 :
2900 9859402 : rtlx = DECL_RTL (exprx);
2901 9859402 : rtly = DECL_RTL (expry);
2902 :
2903 : /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2904 : can't overlap unless they are the same because we never reuse that part
2905 : of the stack frame used for locals for spilled pseudos. */
2906 9858873 : if ((!MEM_P (rtlx) || !MEM_P (rtly))
2907 9892074 : && ! rtx_equal_p (rtlx, rtly))
2908 : return true;
2909 :
2910 : /* If we have MEMs referring to different address spaces (which can
2911 : potentially overlap), we cannot easily tell from the addresses
2912 : whether the references overlap. */
2913 9826201 : if (MEM_P (rtlx) && MEM_P (rtly)
2914 19652701 : && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2915 : return false;
2916 :
2917 : /* Get the base and offsets of both decls. If either is a register, we
2918 : know both are and are the same, so use that as the base. The only
2919 : we can avoid overlap is if we can deduce that they are nonoverlapping
2920 : pieces of that decl, which is very rare. */
2921 9826500 : basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2922 9826500 : basex = strip_offset_and_add (basex, &offsetx);
2923 :
2924 9826500 : basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2925 9826500 : basey = strip_offset_and_add (basey, &offsety);
2926 :
2927 : /* If the bases are different, we know they do not overlap if both
2928 : are constants or if one is a constant and the other a pointer into the
2929 : stack frame. Otherwise a different base means we can't tell if they
2930 : overlap or not. */
2931 9826500 : if (compare_base_decls (exprx, expry) == 0)
2932 7006025 : return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2933 2656692 : || (CONSTANT_P (basex) && REG_P (basey)
2934 276161 : && REGNO_PTR_FRAME_P (REGNO (basey)))
2935 11769368 : || (CONSTANT_P (basey) && REG_P (basex)
2936 421387 : && REGNO_PTR_FRAME_P (REGNO (basex))));
2937 :
2938 : /* Offset based disambiguation not appropriate for loop invariant */
2939 439944 : if (loop_invariant)
2940 : return false;
2941 :
2942 : /* Offset based disambiguation is OK even if we do not know that the
2943 : declarations are necessarily different
2944 : (i.e. compare_base_decls (exprx, expry) == -1) */
2945 :
2946 440243 : sizex = (!MEM_P (rtlx) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx)))
2947 439645 : : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2948 : : -1);
2949 440243 : sizey = (!MEM_P (rtly) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly)))
2950 439645 : : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2951 : : -1);
2952 :
2953 : /* If we have an offset for either memref, it can update the values computed
2954 : above. */
2955 439944 : if (moffsetx_known_p)
2956 413219 : offsetx += moffsetx, sizex -= moffsetx;
2957 439944 : if (moffsety_known_p)
2958 374360 : offsety += moffsety, sizey -= moffsety;
2959 :
2960 : /* If a memref has both a size and an offset, we can use the smaller size.
2961 : We can't do this if the offset isn't known because we must view this
2962 : memref as being anywhere inside the DECL's MEM. */
2963 439944 : if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2964 413219 : sizex = MEM_SIZE (x);
2965 439944 : if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2966 374360 : sizey = MEM_SIZE (y);
2967 :
2968 439944 : return !ranges_maybe_overlap_p (offsetx, sizex, offsety, sizey);
2969 : }
2970 :
2971 : /* Helper for true_dependence and canon_true_dependence.
2972 : Checks for true dependence: X is read after store in MEM takes place.
2973 :
2974 : If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2975 : NULL_RTX, and the canonical addresses of MEM and X are both computed
2976 : here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2977 :
2978 : If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2979 :
2980 : Returns true if there is a true dependence, false otherwise. */
2981 :
2982 : static bool
2983 859350671 : true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
2984 : const_rtx x, rtx x_addr, bool mem_canonicalized)
2985 : {
2986 859350671 : rtx true_mem_addr;
2987 859350671 : rtx base;
2988 859350671 : int ret;
2989 :
2990 859350671 : gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2991 : : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2992 :
2993 859350671 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2994 : return true;
2995 :
2996 : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2997 : This is used in epilogue deallocation functions, and in cselib. */
2998 858670592 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2999 : return true;
3000 858650177 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3001 : return true;
3002 853140998 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3003 1706252969 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3004 : return true;
3005 :
3006 850188294 : if (! x_addr)
3007 54898725 : x_addr = XEXP (x, 0);
3008 850188294 : x_addr = get_addr (x_addr);
3009 :
3010 850188294 : if (! mem_addr)
3011 : {
3012 42648424 : mem_addr = XEXP (mem, 0);
3013 42648424 : if (mem_mode == VOIDmode)
3014 23436132 : mem_mode = GET_MODE (mem);
3015 : }
3016 850188294 : true_mem_addr = get_addr (mem_addr);
3017 :
3018 : /* Read-only memory is by definition never modified, and therefore can't
3019 : conflict with anything. However, don't assume anything when AND
3020 : addresses are involved and leave to the code below to determine
3021 : dependence. We don't expect to find read-only set on MEM, but
3022 : stupid user tricks can produce them, so don't die. */
3023 850188294 : if (MEM_READONLY_P (x)
3024 4530868 : && GET_CODE (x_addr) != AND
3025 854719162 : && GET_CODE (true_mem_addr) != AND)
3026 : return false;
3027 :
3028 : /* If we have MEMs referring to different address spaces (which can
3029 : potentially overlap), we cannot easily tell from the addresses
3030 : whether the references overlap. */
3031 896568391 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3032 : return true;
3033 :
3034 845591215 : base = find_base_term (x_addr);
3035 845591215 : if (base && (GET_CODE (base) == LABEL_REF
3036 721662273 : || (GET_CODE (base) == SYMBOL_REF
3037 63444525 : && CONSTANT_POOL_ADDRESS_P (base))))
3038 : return false;
3039 :
3040 845590317 : rtx mem_base = find_base_term (true_mem_addr);
3041 845590317 : if (! base_alias_check (x_addr, base, true_mem_addr, mem_base,
3042 845590317 : GET_MODE (x), mem_mode))
3043 : return false;
3044 :
3045 759588609 : x_addr = canon_rtx (x_addr);
3046 759588609 : if (!mem_canonicalized)
3047 30700815 : mem_addr = canon_rtx (true_mem_addr);
3048 :
3049 759588609 : if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
3050 1519177218 : SIZE_FOR_MODE (x), x_addr, 0)) != -1)
3051 514321748 : return !!ret;
3052 :
3053 245266861 : if (mems_in_disjoint_alias_sets_p (x, mem))
3054 : return false;
3055 :
3056 182380984 : if (nonoverlapping_memrefs_p (mem, x, false))
3057 : return false;
3058 :
3059 173759828 : return rtx_refs_may_alias_p (x, mem, true);
3060 : }
3061 :
3062 : /* True dependence: X is read after store in MEM takes place. */
3063 :
3064 : bool
3065 45434409 : true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x)
3066 : {
3067 45434409 : return true_dependence_1 (mem, mem_mode, NULL_RTX,
3068 45434409 : x, NULL_RTX, /*mem_canonicalized=*/false);
3069 : }
3070 :
3071 : /* Canonical true dependence: X is read after store in MEM takes place.
3072 : Variant of true_dependence which assumes MEM has already been
3073 : canonicalized (hence we no longer do that here).
3074 : The mem_addr argument has been added, since true_dependence_1 computed
3075 : this value prior to canonicalizing. */
3076 :
3077 : bool
3078 813916262 : canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
3079 : const_rtx x, rtx x_addr)
3080 : {
3081 813916262 : return true_dependence_1 (mem, mem_mode, mem_addr,
3082 813916262 : x, x_addr, /*mem_canonicalized=*/true);
3083 : }
3084 :
3085 : /* Returns true if a write to X might alias a previous read from
3086 : (or, if WRITEP is true, a write to) MEM.
3087 : If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3088 : and X_MODE the mode for that access.
3089 : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3090 :
3091 : static bool
3092 478442733 : write_dependence_p (const_rtx mem,
3093 : const_rtx x, machine_mode x_mode, rtx x_addr,
3094 : bool mem_canonicalized, bool x_canonicalized, bool writep)
3095 : {
3096 478442733 : rtx mem_addr;
3097 478442733 : rtx true_mem_addr, true_x_addr;
3098 478442733 : rtx base;
3099 478442733 : int ret;
3100 :
3101 478442733 : gcc_checking_assert (x_canonicalized
3102 : ? (x_addr != NULL_RTX
3103 : && (x_mode != VOIDmode || GET_MODE (x) == VOIDmode))
3104 : : (x_addr == NULL_RTX && x_mode == VOIDmode));
3105 :
3106 478442733 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3107 : return true;
3108 :
3109 : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3110 : This is used in epilogue deallocation functions. */
3111 477852388 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3112 : return true;
3113 450706530 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3114 : return true;
3115 449552736 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3116 898905132 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3117 : return true;
3118 :
3119 449333444 : if (!x_addr)
3120 53022064 : x_addr = XEXP (x, 0);
3121 449333444 : true_x_addr = get_addr (x_addr);
3122 :
3123 449333444 : mem_addr = XEXP (mem, 0);
3124 449333444 : true_mem_addr = get_addr (mem_addr);
3125 :
3126 : /* A read from read-only memory can't conflict with read-write memory.
3127 : Don't assume anything when AND addresses are involved and leave to
3128 : the code below to determine dependence. */
3129 449333444 : if (!writep
3130 415399360 : && MEM_READONLY_P (mem)
3131 11257656 : && GET_CODE (true_x_addr) != AND
3132 460591100 : && GET_CODE (true_mem_addr) != AND)
3133 : return false;
3134 :
3135 : /* If we have MEMs referring to different address spaces (which can
3136 : potentially overlap), we cannot easily tell from the addresses
3137 : whether the references overlap. */
3138 453833229 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3139 : return true;
3140 :
3141 438037357 : base = find_base_term (true_mem_addr);
3142 438037357 : if (! writep
3143 438037357 : && base
3144 438037357 : && (GET_CODE (base) == LABEL_REF
3145 344251992 : || (GET_CODE (base) == SYMBOL_REF
3146 31683339 : && CONSTANT_POOL_ADDRESS_P (base))))
3147 : return false;
3148 :
3149 438036587 : rtx x_base = find_base_term (true_x_addr);
3150 438036587 : if (! base_alias_check (true_x_addr, x_base, true_mem_addr, base,
3151 438036587 : GET_MODE (x), GET_MODE (mem)))
3152 : return false;
3153 :
3154 379755240 : if (!x_canonicalized)
3155 : {
3156 47469208 : x_addr = canon_rtx (true_x_addr);
3157 47469208 : x_mode = GET_MODE (x);
3158 : }
3159 379755240 : if (!mem_canonicalized)
3160 224574517 : mem_addr = canon_rtx (true_mem_addr);
3161 :
3162 1139265720 : if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
3163 379755240 : GET_MODE_SIZE (x_mode), x_addr, 0)) != -1)
3164 311764009 : return !!ret;
3165 :
3166 67991231 : if (nonoverlapping_memrefs_p (x, mem, false))
3167 : return false;
3168 :
3169 64927422 : return rtx_refs_may_alias_p (x, mem, false);
3170 : }
3171 :
3172 : /* Anti dependence: X is written after read in MEM takes place. */
3173 :
3174 : bool
3175 23834983 : anti_dependence (const_rtx mem, const_rtx x)
3176 : {
3177 23834983 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3178 : /*mem_canonicalized=*/false,
3179 23834983 : /*x_canonicalized*/false, /*writep=*/false);
3180 : }
3181 :
3182 : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3183 : Also, consider X in X_MODE (which might be from an enclosing
3184 : STRICT_LOW_PART / ZERO_EXTRACT).
3185 : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3186 :
3187 : bool
3188 418381283 : canon_anti_dependence (const_rtx mem, bool mem_canonicalized,
3189 : const_rtx x, machine_mode x_mode, rtx x_addr)
3190 : {
3191 418381283 : return write_dependence_p (mem, x, x_mode, x_addr,
3192 : mem_canonicalized, /*x_canonicalized=*/true,
3193 418381283 : /*writep=*/false);
3194 : }
3195 :
3196 : /* Output dependence: X is written after store in MEM takes place. */
3197 :
3198 : bool
3199 32427022 : output_dependence (const_rtx mem, const_rtx x)
3200 : {
3201 32427022 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3202 : /*mem_canonicalized=*/false,
3203 32427022 : /*x_canonicalized*/false, /*writep=*/true);
3204 : }
3205 :
3206 : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3207 : Also, consider X in X_MODE (which might be from an enclosing
3208 : STRICT_LOW_PART / ZERO_EXTRACT).
3209 : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3210 :
3211 : bool
3212 3799445 : canon_output_dependence (const_rtx mem, bool mem_canonicalized,
3213 : const_rtx x, machine_mode x_mode, rtx x_addr)
3214 : {
3215 3799445 : return write_dependence_p (mem, x, x_mode, x_addr,
3216 : mem_canonicalized, /*x_canonicalized=*/true,
3217 3799445 : /*writep=*/true);
3218 : }
3219 :
3220 :
3221 :
3222 : /* Check whether X may be aliased with MEM. Don't do offset-based
3223 : memory disambiguation & TBAA. */
3224 : bool
3225 0 : may_alias_p (const_rtx mem, const_rtx x)
3226 : {
3227 0 : rtx x_addr, mem_addr;
3228 :
3229 0 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3230 : return true;
3231 :
3232 : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3233 : This is used in epilogue deallocation functions. */
3234 0 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3235 : return true;
3236 0 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3237 : return true;
3238 0 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3239 0 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3240 : return true;
3241 :
3242 0 : x_addr = XEXP (x, 0);
3243 0 : x_addr = get_addr (x_addr);
3244 :
3245 0 : mem_addr = XEXP (mem, 0);
3246 0 : mem_addr = get_addr (mem_addr);
3247 :
3248 : /* Read-only memory is by definition never modified, and therefore can't
3249 : conflict with anything. However, don't assume anything when AND
3250 : addresses are involved and leave to the code below to determine
3251 : dependence. We don't expect to find read-only set on MEM, but
3252 : stupid user tricks can produce them, so don't die. */
3253 0 : if (MEM_READONLY_P (x)
3254 0 : && GET_CODE (x_addr) != AND
3255 0 : && GET_CODE (mem_addr) != AND)
3256 : return false;
3257 :
3258 : /* If we have MEMs referring to different address spaces (which can
3259 : potentially overlap), we cannot easily tell from the addresses
3260 : whether the references overlap. */
3261 0 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3262 : return true;
3263 :
3264 0 : rtx x_base = find_base_term (x_addr);
3265 0 : rtx mem_base = find_base_term (mem_addr);
3266 0 : if (! base_alias_check (x_addr, x_base, mem_addr, mem_base,
3267 0 : GET_MODE (x), GET_MODE (mem_addr)))
3268 : return false;
3269 :
3270 0 : if (nonoverlapping_memrefs_p (mem, x, true))
3271 : return false;
3272 :
3273 : /* TBAA not valid for loop_invarint */
3274 0 : return rtx_refs_may_alias_p (x, mem, false);
3275 : }
3276 :
3277 : void
3278 218789 : init_alias_target (void)
3279 : {
3280 218789 : int i;
3281 :
3282 218789 : if (!arg_base_value)
3283 214556 : arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
3284 :
3285 218789 : memset (static_reg_base_value, 0, sizeof static_reg_base_value);
3286 :
3287 20347377 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3288 : /* Check whether this register can hold an incoming pointer
3289 : argument. FUNCTION_ARG_REGNO_P tests outgoing register
3290 : numbers, so translate if necessary due to register windows. */
3291 20128588 : if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
3292 20180341 : && targetm.hard_regno_mode_ok (i, Pmode))
3293 3242388 : static_reg_base_value[i] = arg_base_value;
3294 :
3295 : /* RTL code is required to be consistent about whether it uses the
3296 : stack pointer, the frame pointer or the argument pointer to
3297 : access a given area of the frame. We can therefore use the
3298 : base address to distinguish between the different areas. */
3299 218789 : static_reg_base_value[STACK_POINTER_REGNUM]
3300 218789 : = unique_base_value (UNIQUE_BASE_VALUE_SP);
3301 218789 : static_reg_base_value[ARG_POINTER_REGNUM]
3302 218789 : = unique_base_value (UNIQUE_BASE_VALUE_ARGP);
3303 218789 : static_reg_base_value[FRAME_POINTER_REGNUM]
3304 218789 : = unique_base_value (UNIQUE_BASE_VALUE_FP);
3305 :
3306 : /* The above rules extend post-reload, with eliminations applying
3307 : consistently to each of the three pointers. Cope with cases in
3308 : which the frame pointer is eliminated to the hard frame pointer
3309 : rather than the stack pointer. */
3310 218789 : if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3311 218789 : static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
3312 218789 : = unique_base_value (UNIQUE_BASE_VALUE_HFP);
3313 218789 : }
3314 :
3315 : /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3316 : to be memory reference. */
3317 : static bool memory_modified;
3318 : static void
3319 33992709 : memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3320 : {
3321 33992709 : if (MEM_P (x))
3322 : {
3323 2846316 : if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
3324 576249 : memory_modified = true;
3325 : }
3326 33992709 : }
3327 :
3328 :
3329 : /* Return true when INSN possibly modify memory contents of MEM
3330 : (i.e. address can be modified). */
3331 : bool
3332 45868510 : memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
3333 : {
3334 45868510 : if (!INSN_P (insn))
3335 : return false;
3336 : /* Conservatively assume all non-readonly MEMs might be modified in
3337 : calls. */
3338 42943004 : if (CALL_P (insn))
3339 : return true;
3340 42622294 : memory_modified = false;
3341 42622294 : note_stores (as_a<const rtx_insn *> (insn), memory_modified_1,
3342 : const_cast<rtx> (mem));
3343 42622294 : return memory_modified;
3344 : }
3345 :
3346 : /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3347 : array. */
3348 :
3349 : void
3350 11061255 : init_alias_analysis (void)
3351 : {
3352 11061255 : const bool frame_pointer_eliminated
3353 11061255 : = reload_completed
3354 5660572 : && !frame_pointer_needed
3355 15954289 : && targetm.can_eliminate (FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM);
3356 11061255 : unsigned int maxreg = max_reg_num ();
3357 11061255 : bool changed;
3358 11061255 : int pass, i;
3359 11061255 : unsigned int ui;
3360 11061255 : rtx_insn *insn;
3361 11061255 : rtx val;
3362 11061255 : int rpo_cnt;
3363 11061255 : int *rpo;
3364 :
3365 11061255 : timevar_push (TV_ALIAS_ANALYSIS);
3366 :
3367 11061255 : vec_safe_grow_cleared (reg_known_value, maxreg - FIRST_PSEUDO_REGISTER,
3368 : true);
3369 11061255 : reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
3370 11061255 : bitmap_clear (reg_known_equiv_p);
3371 :
3372 : /* If we have memory allocated from the previous run, use it. */
3373 11061255 : if (old_reg_base_value)
3374 10795433 : reg_base_value = old_reg_base_value;
3375 :
3376 11061255 : if (reg_base_value)
3377 10846892 : reg_base_value->truncate (0);
3378 :
3379 11061255 : vec_safe_grow_cleared (reg_base_value, maxreg, true);
3380 :
3381 11061255 : new_reg_base_value = XNEWVEC (rtx, maxreg);
3382 11061255 : reg_seen = sbitmap_alloc (maxreg);
3383 :
3384 : /* The basic idea is that each pass through this loop will use the
3385 : "constant" information from the previous pass to propagate alias
3386 : information through another level of assignments.
3387 :
3388 : The propagation is done on the CFG in reverse post-order, to propagate
3389 : things forward as far as possible in each iteration.
3390 :
3391 : This could get expensive if the assignment chains are long. Maybe
3392 : we should throttle the number of iterations, possibly based on
3393 : the optimization level or flag_expensive_optimizations.
3394 :
3395 : We could propagate more information in the first pass by making use
3396 : of DF_REG_DEF_COUNT to determine immediately that the alias information
3397 : for a pseudo is "constant".
3398 :
3399 : A program with an uninitialized variable can cause an infinite loop
3400 : here. Instead of doing a full dataflow analysis to detect such problems
3401 : we just cap the number of iterations for the loop.
3402 :
3403 : The state of the arrays for the set chain in question does not matter
3404 : since the program has undefined behavior. */
3405 :
3406 11061255 : rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3407 11061255 : rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
3408 :
3409 11061255 : pass = 0;
3410 22395664 : do
3411 : {
3412 : /* Assume nothing will change this iteration of the loop. */
3413 22395664 : changed = false;
3414 :
3415 : /* We want to assign the same IDs each iteration of this loop, so
3416 : start counting from one each iteration of the loop. */
3417 22395664 : unique_id = 1;
3418 :
3419 : /* We're at the start of the function each iteration through the
3420 : loop, so we're copying arguments. */
3421 22395664 : copying_arguments = true;
3422 :
3423 : /* Wipe the potential alias information clean for this pass. */
3424 22395664 : memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
3425 :
3426 : /* Wipe the reg_seen array clean. */
3427 22395664 : bitmap_clear (reg_seen);
3428 :
3429 : /* Initialize the alias information for this pass. */
3430 2105192416 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3431 2060401088 : if (static_reg_base_value[i]
3432 : /* Don't treat the hard frame pointer as special if we
3433 : eliminated the frame pointer to the stack pointer. */
3434 409716321 : && !(i == HARD_FRAME_POINTER_REGNUM && frame_pointer_eliminated))
3435 : {
3436 399900226 : new_reg_base_value[i] = static_reg_base_value[i];
3437 399900226 : bitmap_set_bit (reg_seen, i);
3438 : }
3439 :
3440 : /* Walk the insns adding values to the new_reg_base_value array. */
3441 282608696 : for (i = 0; i < rpo_cnt; i++)
3442 : {
3443 260213032 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
3444 3353553462 : FOR_BB_INSNS (bb, insn)
3445 : {
3446 3093340430 : if (NONDEBUG_INSN_P (insn))
3447 : {
3448 1449547150 : rtx note, set;
3449 :
3450 : /* Treat the hard frame pointer as special unless we
3451 : eliminated the frame pointer to the stack pointer. */
3452 1449923797 : if (!frame_pointer_eliminated
3453 1449547150 : && modified_in_p (hard_frame_pointer_rtx, insn))
3454 376647 : continue;
3455 :
3456 : /* If this insn has a noalias note, process it, Otherwise,
3457 : scan for sets. A simple set will have no side effects
3458 : which could change the base value of any other register. */
3459 1449170503 : if (GET_CODE (PATTERN (insn)) == SET
3460 1163843844 : && REG_NOTES (insn) != 0
3461 2003028222 : && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
3462 1664452 : record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
3463 : else
3464 1447506051 : note_stores (insn, record_set, NULL);
3465 :
3466 1449170503 : set = single_set (insn);
3467 :
3468 1449170503 : if (set != 0
3469 1353073671 : && REG_P (SET_DEST (set))
3470 2417110668 : && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3471 : {
3472 322163268 : unsigned int regno = REGNO (SET_DEST (set));
3473 322163268 : rtx src = SET_SRC (set);
3474 322163268 : rtx t;
3475 :
3476 322163268 : note = find_reg_equal_equiv_note (insn);
3477 322163268 : if (note && REG_NOTE_KIND (note) == REG_EQUAL
3478 18383932 : && DF_REG_DEF_COUNT (regno) != 1)
3479 : note = NULL_RTX;
3480 :
3481 : poly_int64 offset;
3482 : if (note != NULL_RTX
3483 18382641 : && GET_CODE (XEXP (note, 0)) != EXPR_LIST
3484 18382641 : && ! rtx_varies_p (XEXP (note, 0), 1)
3485 7870450 : && ! reg_overlap_mentioned_p (SET_DEST (set),
3486 7870450 : XEXP (note, 0)))
3487 : {
3488 7870450 : set_reg_known_value (regno, XEXP (note, 0));
3489 7870450 : set_reg_known_equiv_p (regno,
3490 7870450 : REG_NOTE_KIND (note) == REG_EQUIV);
3491 : }
3492 314292818 : else if (DF_REG_DEF_COUNT (regno) == 1
3493 240059356 : && GET_CODE (src) == PLUS
3494 44919190 : && REG_P (XEXP (src, 0))
3495 44001627 : && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
3496 315623579 : && poly_int_rtx_p (XEXP (src, 1), &offset))
3497 : {
3498 820819 : t = plus_constant (GET_MODE (src), t, offset);
3499 820819 : set_reg_known_value (regno, t);
3500 820819 : set_reg_known_equiv_p (regno, false);
3501 : }
3502 313471999 : else if (DF_REG_DEF_COUNT (regno) == 1
3503 313471999 : && ! rtx_varies_p (src, 1))
3504 : {
3505 33434643 : set_reg_known_value (regno, src);
3506 33434643 : set_reg_known_equiv_p (regno, false);
3507 : }
3508 : }
3509 : }
3510 1643793280 : else if (NOTE_P (insn)
3511 357944265 : && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
3512 22380746 : copying_arguments = false;
3513 : }
3514 : }
3515 :
3516 : /* Now propagate values from new_reg_base_value to reg_base_value. */
3517 22395664 : gcc_assert (maxreg == (unsigned int) max_reg_num ());
3518 :
3519 3309241983 : for (ui = 0; ui < maxreg; ui++)
3520 : {
3521 3286846319 : if (new_reg_base_value[ui]
3522 383840298 : && new_reg_base_value[ui] != (*reg_base_value)[ui]
3523 3475924123 : && ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui]))
3524 : {
3525 188198230 : (*reg_base_value)[ui] = new_reg_base_value[ui];
3526 188198230 : changed = true;
3527 : }
3528 : }
3529 : }
3530 22395753 : while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
3531 11061255 : XDELETEVEC (rpo);
3532 :
3533 : /* Fill in the remaining entries. */
3534 600769342 : FOR_EACH_VEC_ELT (*reg_known_value, i, val)
3535 : {
3536 589708087 : int regno = i + FIRST_PSEUDO_REGISTER;
3537 589708087 : if (! val)
3538 570522632 : set_reg_known_value (regno, regno_reg_rtx[regno]);
3539 : }
3540 :
3541 : /* Clean up. */
3542 11061255 : free (new_reg_base_value);
3543 11061255 : new_reg_base_value = 0;
3544 11061255 : sbitmap_free (reg_seen);
3545 11061255 : reg_seen = 0;
3546 11061255 : timevar_pop (TV_ALIAS_ANALYSIS);
3547 11061255 : }
3548 :
3549 : /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3550 : Special API for var-tracking pass purposes. */
3551 :
3552 : void
3553 506958 : vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
3554 : {
3555 506958 : (*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2);
3556 506958 : }
3557 :
3558 : void
3559 11061255 : end_alias_analysis (void)
3560 : {
3561 11061255 : old_reg_base_value = reg_base_value;
3562 11061255 : vec_free (reg_known_value);
3563 11061255 : sbitmap_free (reg_known_equiv_p);
3564 11061255 : }
3565 :
3566 : void
3567 0 : dump_alias_stats_in_alias_c (FILE *s)
3568 : {
3569 0 : fprintf (s, " TBAA oracle: %llu disambiguations %llu queries\n"
3570 : " %llu are in alias set 0\n"
3571 : " %llu queries asked about the same object\n"
3572 : " %llu queries asked about the same alias set\n"
3573 : " %llu access volatile\n"
3574 : " %llu are dependent in the DAG\n"
3575 : " %llu are aritificially in conflict with void *\n",
3576 : alias_stats.num_disambiguated,
3577 0 : alias_stats.num_alias_zero + alias_stats.num_same_alias_set
3578 0 : + alias_stats.num_same_objects + alias_stats.num_volatile
3579 0 : + alias_stats.num_dag + alias_stats.num_disambiguated
3580 : + alias_stats.num_universal,
3581 : alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
3582 : alias_stats.num_same_objects, alias_stats.num_volatile,
3583 : alias_stats.num_dag, alias_stats.num_universal);
3584 0 : }
3585 : #include "gt-alias.h"
|
