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