Branch data Line data Source code
1 : : /* Alias analysis for GNU C
2 : : Copyright (C) 1997-2024 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 : 409888004 : ao_ref_from_mem (ao_ref *ref, const_rtx mem)
275 : : {
276 : 409888004 : tree expr = MEM_EXPR (mem);
277 : 409888004 : tree base;
278 : :
279 : 409888004 : if (!expr)
280 : : return false;
281 : :
282 : 381045404 : 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 : 381045404 : base = ao_ref_base (ref);
287 : 381045404 : 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 : 407008682 : if (!(DECL_P (base)
293 : 205335146 : || (TREE_CODE (base) == MEM_REF
294 : 179487420 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
295 : : || (TREE_CODE (base) == TARGET_MEM_REF
296 : 25817646 : && TREE_CODE (TMR_BASE (base)) == SSA_NAME)))
297 : : return false;
298 : :
299 : 380899339 : 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 : 380899339 : if (!MEM_OFFSET_KNOWN_P (mem)
304 : 380899339 : || !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 : 374589418 : if (maybe_lt (MEM_OFFSET (mem), 0)
310 : 374589418 : || (ref->max_size_known_p ()
311 : 336390473 : && maybe_gt ((MEM_OFFSET (mem) + MEM_SIZE (mem)) * BITS_PER_UNIT,
312 : : ref->max_size)))
313 : 36333373 : 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 : 374589418 : ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
319 : 374589418 : 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 : 374589418 : if (ref->max_size_known_p ())
324 : 336390518 : 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 : 374589418 : if (MEM_EXPR (mem) != get_spill_slot_decl (false)
329 : 374589418 : && (maybe_lt (ref->offset, 0)
330 : 338328189 : || (DECL_P (ref->base)
331 : 134084070 : && (DECL_SIZE (ref->base) == NULL_TREE
332 : 133970416 : || !poly_int_tree_p (DECL_SIZE (ref->base))
333 : 133970366 : || maybe_lt (wi::to_poly_offset (DECL_SIZE (ref->base)),
334 : 508434570 : ref->offset + ref->size)))))
335 : 125214 : 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 : 211813680 : rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
346 : : {
347 : 211813680 : ao_ref ref1, ref2;
348 : :
349 : 211813680 : if (!ao_ref_from_mem (&ref1, x)
350 : 211813680 : || !ao_ref_from_mem (&ref2, mem))
351 : 29113879 : return true;
352 : :
353 : 182699801 : return refs_may_alias_p_1 (&ref1, &ref2,
354 : : tbaa_p
355 : 134515094 : && MEM_ALIAS_SET (x) != 0
356 : 447497775 : && 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 : 176994 : refs_same_for_tbaa_p (tree earlier, tree later)
364 : : {
365 : 176994 : ao_ref earlier_ref, later_ref;
366 : 176994 : ao_ref_init (&earlier_ref, earlier);
367 : 176994 : ao_ref_init (&later_ref, later);
368 : 176994 : alias_set_type earlier_set = ao_ref_alias_set (&earlier_ref);
369 : 176994 : alias_set_type later_set = ao_ref_alias_set (&later_ref);
370 : 214544 : if (!(earlier_set == later_set
371 : 37550 : || alias_set_subset_of (later_set, earlier_set)))
372 : : return false;
373 : 176654 : alias_set_type later_base_set = ao_ref_base_alias_set (&later_ref);
374 : 176654 : alias_set_type earlier_base_set = ao_ref_base_alias_set (&earlier_ref);
375 : 176654 : return (earlier_base_set == later_base_set
376 : 176654 : || 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 : 107678 : mems_same_for_tbaa_p (rtx earlier, rtx later)
382 : : {
383 : 107678 : gcc_assert (MEM_P (earlier));
384 : 107678 : gcc_assert (MEM_P (later));
385 : :
386 : 107679 : return ((MEM_ALIAS_SET (earlier) == MEM_ALIAS_SET (later)
387 : 36628 : || alias_set_subset_of (MEM_ALIAS_SET (later),
388 : 36628 : MEM_ALIAS_SET (earlier)))
389 : 213760 : && (!MEM_EXPR (earlier)
390 : 105388 : || 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 : 225886140 : get_alias_set_entry (alias_set_type alias_set)
398 : : {
399 : 451772280 : 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 : 217050697 : mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
407 : : {
408 : 217050697 : return (flag_strict_aliasing
409 : 347078452 : && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1),
410 : 130027755 : MEM_ALIAS_SET (mem2)));
411 : : }
412 : :
413 : : /* Return true if the first alias set is a subset of the second. */
414 : :
415 : : bool
416 : 291156 : alias_set_subset_of (alias_set_type set1, alias_set_type set2)
417 : : {
418 : 291156 : alias_set_entry *ase2;
419 : :
420 : : /* Disable TBAA oracle with !flag_strict_aliasing. */
421 : 291156 : if (!flag_strict_aliasing)
422 : : return true;
423 : :
424 : : /* Everything is a subset of the "aliases everything" set. */
425 : 203024 : if (set2 == 0)
426 : : return true;
427 : :
428 : : /* Check if set1 is a subset of set2. */
429 : 180685 : ase2 = get_alias_set_entry (set2);
430 : 180685 : if (ase2 != 0
431 : 180685 : && (ase2->has_zero_child
432 : 143936 : || (ase2->children && ase2->children->get (set1))))
433 : 145110 : 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 explicitely - 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 : 35575 : if (ase2 && ase2->has_pointer)
457 : : {
458 : 25251 : alias_set_entry *ase1 = get_alias_set_entry (set1);
459 : :
460 : 25251 : if (ase1 && ase1->is_pointer)
461 : : {
462 : 10191 : 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 : 10191 : if (set1 == voidptr_set || set2 == voidptr_set)
466 : 9897 : return true;
467 : : /* If SET2 contains universal pointer's alias set, then we consdier
468 : : every (non-universal) pointer. */
469 : 9644 : if (ase2->children && set1 != voidptr_set
470 : 9644 : && 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 : 252179029 : alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
481 : : {
482 : 252179029 : alias_set_entry *ase1;
483 : 252179029 : alias_set_entry *ase2;
484 : :
485 : : /* The easy case. */
486 : 252179029 : 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 : 112845195 : ase1 = get_alias_set_entry (set1);
491 : 112845195 : if (ase1 != 0
492 : 112845195 : && ase1->children && ase1->children->get (set2))
493 : : {
494 : 4915101 : ++alias_stats.num_dag;
495 : 4915101 : return true;
496 : : }
497 : :
498 : : /* Now do the same, but with the alias sets reversed. */
499 : 107930094 : ase2 = get_alias_set_entry (set2);
500 : 107930094 : if (ase2 != 0
501 : 107930094 : && ase2->children && ase2->children->get (set1))
502 : : {
503 : 6349113 : ++alias_stats.num_dag;
504 : 6349113 : 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 : 101580981 : if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer)
517 : : {
518 : 14440128 : 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 : 14440128 : if (set1 == voidptr_set || set2 == voidptr_set)
524 : : {
525 : 3403764 : ++alias_stats.num_universal;
526 : 4011411 : return true;
527 : : }
528 : : /* If one of sets is (non-universal) pointer and the other
529 : : contains universal pointer, we also get conflict. */
530 : 11036364 : if (ase1->is_pointer && set2 != voidptr_set
531 : 11036364 : && ase2->children && ase2->children->get (voidptr_set))
532 : : {
533 : 482359 : ++alias_stats.num_universal;
534 : 482359 : return true;
535 : : }
536 : 10554005 : if (ase2->is_pointer && set1 != voidptr_set
537 : 10554005 : && ase1->children && ase1->children->get (voidptr_set))
538 : : {
539 : 125288 : ++alias_stats.num_universal;
540 : 125288 : return true;
541 : : }
542 : : }
543 : :
544 : 97569570 : ++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 : 97569570 : return false;
549 : : }
550 : :
551 : : /* Return true if the two specified alias sets will always conflict. */
552 : :
553 : : bool
554 : 252194725 : alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
555 : : {
556 : : /* Disable TBAA oracle with !flag_strict_aliasing. */
557 : 252194725 : if (!flag_strict_aliasing)
558 : : return true;
559 : 247391791 : if (set1 == 0 || set2 == 0)
560 : : {
561 : 82048514 : ++alias_stats.num_alias_zero;
562 : 82048514 : return true;
563 : : }
564 : 165343277 : if (set1 == set2)
565 : : {
566 : 52497126 : ++alias_stats.num_same_alias_set;
567 : 52497126 : 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 : 226693 : objects_must_conflict_p (tree t1, tree t2)
580 : : {
581 : 226693 : 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 : 226693 : if (t1 == 0 && t2 == 0)
587 : : return false;
588 : :
589 : : /* If they are the same type, they must conflict. */
590 : 59693 : if (t1 == t2)
591 : : {
592 : 44030 : ++alias_stats.num_same_objects;
593 : 44030 : return true;
594 : : }
595 : : /* Likewise if both are volatile. */
596 : 15663 : 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 : 15663 : set1 = t1 ? get_alias_set (t1) : 0;
603 : 15663 : 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 : 15663 : 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 : 450625650 : ends_tbaa_access_path_p (const_tree t)
617 : : {
618 : 450625650 : switch (TREE_CODE (t))
619 : : {
620 : 336527411 : case COMPONENT_REF:
621 : 336527411 : 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 : 333386207 : else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE)
630 : : return true;
631 : : break;
632 : :
633 : 109448930 : case ARRAY_REF:
634 : 109448930 : case ARRAY_RANGE_REF:
635 : 109448930 : 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 : 1047883972 : component_uses_parent_alias_set_from (const_tree t)
664 : : {
665 : 1047883972 : const_tree found = NULL_TREE;
666 : :
667 : 1468512326 : while (handled_component_p (t))
668 : : {
669 : 420628354 : if (ends_tbaa_access_path_p (t))
670 : 12022194 : found = t;
671 : :
672 : 420628354 : t = TREE_OPERAND (t, 0);
673 : : }
674 : :
675 : 1047883972 : if (found)
676 : 11777195 : 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 : 808936416 : ref_all_alias_ptr_type_p (const_tree t)
688 : : {
689 : 808936416 : return (VOID_TYPE_P (TREE_TYPE (t))
690 : 808936416 : || 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 : 86083482 : get_deref_alias_set_1 (tree t)
699 : : {
700 : : /* All we care about is the type. */
701 : 86083482 : if (! TYPE_P (t))
702 : 20 : 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 : 86083482 : if (ref_all_alias_ptr_type_p (t))
708 : 16980742 : 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 : 127836423 : get_deref_alias_set (tree t)
718 : : {
719 : : /* If we're not doing any alias analysis, just assume everything
720 : : aliases everything else. */
721 : 127836423 : if (!flag_strict_aliasing)
722 : : return 0;
723 : :
724 : 86083482 : alias_set_type set = get_deref_alias_set_1 (t);
725 : :
726 : : /* Fall back to the alias-set of the pointed-to type. */
727 : 86083482 : if (set == -1)
728 : : {
729 : 69102740 : if (! TYPE_P (t))
730 : 20 : t = TREE_TYPE (t);
731 : 69102740 : 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 : 1148827299 : reference_alias_ptr_type_1 (tree *t)
744 : : {
745 : 1148827299 : tree inner;
746 : :
747 : : /* Get the base object of the reference. */
748 : 1148827299 : inner = *t;
749 : 1558136010 : 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 : 409308711 : if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
755 : 1900605 : *t = TREE_OPERAND (inner, 0);
756 : 409308711 : inner = TREE_OPERAND (inner, 0);
757 : : }
758 : :
759 : : /* Handle pointer dereferences here, they can override the
760 : : alias-set. */
761 : 1148827299 : if (INDIRECT_REF_P (inner)
762 : 1148827299 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 0))))
763 : 0 : return TREE_TYPE (TREE_OPERAND (inner, 0));
764 : 1148827299 : else if (TREE_CODE (inner) == TARGET_MEM_REF)
765 : 42107561 : return TREE_TYPE (TMR_OFFSET (inner));
766 : 1106719738 : else if (TREE_CODE (inner) == MEM_REF
767 : 1106719738 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 1))))
768 : 18611224 : 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 : 1088108514 : if (TREE_CODE (inner) == MEM_REF
774 : 1088108514 : && (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
775 : 699364921 : != TYPE_MAIN_VARIANT
776 : : (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1))))))
777 : : {
778 : 67690312 : tree alias_ptrtype = TREE_TYPE (TREE_OPERAND (inner, 1));
779 : : /* Unless we have the (aggregate) effective type of the access
780 : : somewhere on the access path. If we have for example
781 : : (&a->elts[i])->l.len exposed by abstraction we'd see
782 : : MEM <A> [(B *)a].elts[i].l.len and we can use the alias set
783 : : of 'len' when typeof (MEM <A> [(B *)a].elts[i]) == B for
784 : : example. See PR111715. */
785 : 67690312 : tree inner = *t;
786 : 67690312 : while (handled_component_p (inner)
787 : 68663261 : && (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
788 : 1676016 : != TYPE_MAIN_VARIANT (TREE_TYPE (alias_ptrtype))))
789 : 972949 : inner = TREE_OPERAND (inner, 0);
790 : 67690312 : if (TREE_CODE (inner) == MEM_REF)
791 : : return alias_ptrtype;
792 : : }
793 : :
794 : : /* Otherwise, pick up the outermost object that we could have
795 : : a pointer to. */
796 : 1021121269 : tree tem = component_uses_parent_alias_set_from (*t);
797 : 1021121269 : if (tem)
798 : 10744266 : *t = tem;
799 : :
800 : : return NULL_TREE;
801 : : }
802 : :
803 : : /* Return the pointer-type relevant for TBAA purposes from the
804 : : gimple memory reference tree T. This is the type to be used for
805 : : the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
806 : : and guarantees that get_alias_set will return the same alias
807 : : set for T and the replacement. */
808 : :
809 : : tree
810 : 7837283 : reference_alias_ptr_type (tree t)
811 : : {
812 : : /* If the frontend assigns this alias-set zero, preserve that. */
813 : 7837283 : if (lang_hooks.get_alias_set (t) == 0)
814 : 0 : return ptr_type_node;
815 : :
816 : 7837283 : tree ptype = reference_alias_ptr_type_1 (&t);
817 : : /* If there is a given pointer type for aliasing purposes, return it. */
818 : 7837283 : if (ptype != NULL_TREE)
819 : : return ptype;
820 : :
821 : : /* Otherwise build one from the outermost component reference we
822 : : may use. */
823 : 7442118 : if (TREE_CODE (t) == MEM_REF
824 : 7442118 : || TREE_CODE (t) == TARGET_MEM_REF)
825 : 837946 : return TREE_TYPE (TREE_OPERAND (t, 1));
826 : : else
827 : 6604172 : return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t)));
828 : : }
829 : :
830 : : /* Return whether the pointer-types T1 and T2 used to determine
831 : : two alias sets of two references will yield the same answer
832 : : from get_deref_alias_set. */
833 : :
834 : : bool
835 : 13082636 : alias_ptr_types_compatible_p (tree t1, tree t2)
836 : : {
837 : 13082636 : if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
838 : : return true;
839 : :
840 : 2156297 : if (ref_all_alias_ptr_type_p (t1)
841 : 2156297 : || ref_all_alias_ptr_type_p (t2))
842 : : return false;
843 : :
844 : : /* This function originally abstracts from simply comparing
845 : : get_deref_alias_set so that we are sure this still computes
846 : : the same result after LTO type merging is applied.
847 : : When in LTO type merging is done we can actually do this compare.
848 : : */
849 : 2133734 : if (in_lto_p)
850 : 3788 : return get_deref_alias_set (t1) == get_deref_alias_set (t2);
851 : : else
852 : 2129946 : return (TYPE_MAIN_VARIANT (TREE_TYPE (t1))
853 : 2129946 : == TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
854 : : }
855 : :
856 : : /* Create emptry alias set entry. */
857 : :
858 : : alias_set_entry *
859 : 1150410 : init_alias_set_entry (alias_set_type set)
860 : : {
861 : 1150410 : alias_set_entry *ase = ggc_alloc<alias_set_entry> ();
862 : 1150410 : ase->alias_set = set;
863 : 1150410 : ase->children = NULL;
864 : 1150410 : ase->has_zero_child = false;
865 : 1150410 : ase->is_pointer = false;
866 : 1150410 : ase->has_pointer = false;
867 : 1150410 : gcc_checking_assert (!get_alias_set_entry (set));
868 : 1150410 : (*alias_sets)[set] = ase;
869 : 1150410 : return ase;
870 : : }
871 : :
872 : : /* Return the alias set for T, which may be either a type or an
873 : : expression. Call language-specific routine for help, if needed. */
874 : :
875 : : alias_set_type
876 : 1279803171 : get_alias_set (tree t)
877 : : {
878 : 1279803171 : alias_set_type set;
879 : :
880 : : /* We cannot give up with -fno-strict-aliasing because we need to build
881 : : proper type representations for possible functions which are built with
882 : : -fstrict-aliasing. */
883 : :
884 : : /* return 0 if this or its type is an error. */
885 : 1279803171 : if (t == error_mark_node
886 : 1279803171 : || (! TYPE_P (t)
887 : 1140671136 : && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
888 : : return 0;
889 : :
890 : : /* We can be passed either an expression or a type. This and the
891 : : language-specific routine may make mutually-recursive calls to each other
892 : : to figure out what to do. At each juncture, we see if this is a tree
893 : : that the language may need to handle specially. First handle things that
894 : : aren't types. */
895 : 1279803171 : if (! TYPE_P (t))
896 : : {
897 : : /* Give the language a chance to do something with this tree
898 : : before we look at it. */
899 : 1140671136 : STRIP_NOPS (t);
900 : 1140671136 : set = lang_hooks.get_alias_set (t);
901 : 1140671136 : if (set != -1)
902 : : return set;
903 : :
904 : : /* Get the alias pointer-type to use or the outermost object
905 : : that we could have a pointer to. */
906 : 1140671136 : tree ptype = reference_alias_ptr_type_1 (&t);
907 : 1140671136 : if (ptype != NULL)
908 : 127308279 : return get_deref_alias_set (ptype);
909 : :
910 : : /* If we've already determined the alias set for a decl, just return
911 : : it. This is necessary for C++ anonymous unions, whose component
912 : : variables don't look like union members (boo!). */
913 : 1013362857 : if (VAR_P (t)
914 : 1013362857 : && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
915 : 170404946 : return MEM_ALIAS_SET (DECL_RTL (t));
916 : :
917 : : /* Now all we care about is the type. */
918 : 928160384 : t = TREE_TYPE (t);
919 : : }
920 : :
921 : : /* Variant qualifiers don't affect the alias set, so get the main
922 : : variant. */
923 : 1067292419 : t = TYPE_MAIN_VARIANT (t);
924 : :
925 : 1067292419 : if (AGGREGATE_TYPE_P (t)
926 : 1067292419 : && TYPE_TYPELESS_STORAGE (t))
927 : : return 0;
928 : :
929 : : /* Always use the canonical type as well. If this is a type that
930 : : requires structural comparisons to identify compatible types
931 : : use alias set zero. */
932 : 1002442668 : if (TYPE_STRUCTURAL_EQUALITY_P (t))
933 : : {
934 : : /* Allow the language to specify another alias set for this
935 : : type. */
936 : 282402696 : set = lang_hooks.get_alias_set (t);
937 : 282402696 : if (set != -1)
938 : : return set;
939 : : /* Handle structure type equality for pointer types, arrays and vectors.
940 : : This is easy to do, because the code below ignores canonical types on
941 : : these anyway. This is important for LTO, where TYPE_CANONICAL for
942 : : pointers cannot be meaningfully computed by the frontend. */
943 : 281990195 : if (canonical_type_used_p (t))
944 : : {
945 : : /* In LTO we set canonical types for all types where it makes
946 : : sense to do so. Double check we did not miss some type. */
947 : 197747034 : gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
948 : : return 0;
949 : : }
950 : : }
951 : : else
952 : : {
953 : 720039972 : t = TYPE_CANONICAL (t);
954 : 720039972 : gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
955 : : }
956 : :
957 : : /* If this is a type with a known alias set, return it. */
958 : 804283133 : gcc_checking_assert (t == TYPE_MAIN_VARIANT (t));
959 : 804283133 : if (TYPE_ALIAS_SET_KNOWN_P (t))
960 : 717248830 : return TYPE_ALIAS_SET (t);
961 : :
962 : : /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
963 : 87034303 : if (!COMPLETE_TYPE_P (t))
964 : : {
965 : : /* For arrays with unknown size the conservative answer is the
966 : : alias set of the element type. */
967 : 9709337 : if (TREE_CODE (t) == ARRAY_TYPE)
968 : 9681826 : return get_alias_set (TREE_TYPE (t));
969 : :
970 : : /* But return zero as a conservative answer for incomplete types. */
971 : : return 0;
972 : : }
973 : :
974 : : /* See if the language has special handling for this type. */
975 : 77324966 : set = lang_hooks.get_alias_set (t);
976 : 77324966 : if (set != -1)
977 : : return set;
978 : :
979 : : /* There are no objects of FUNCTION_TYPE, so there's no point in
980 : : using up an alias set for them. (There are, of course, pointers
981 : : and references to functions, but that's different.) */
982 : 2404554 : else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
983 : : set = 0;
984 : :
985 : : /* Unless the language specifies otherwise, let vector types alias
986 : : their components. This avoids some nasty type punning issues in
987 : : normal usage. And indeed lets vectors be treated more like an
988 : : array slice. */
989 : 2401092 : else if (TREE_CODE (t) == VECTOR_TYPE)
990 : 85604 : set = get_alias_set (TREE_TYPE (t));
991 : :
992 : : /* Unless the language specifies otherwise, treat array types the
993 : : same as their components. This avoids the asymmetry we get
994 : : through recording the components. Consider accessing a
995 : : character(kind=1) through a reference to a character(kind=1)[1:1].
996 : : Or consider if we want to assign integer(kind=4)[0:D.1387] and
997 : : integer(kind=4)[4] the same alias set or not.
998 : : Just be pragmatic here and make sure the array and its element
999 : : type get the same alias set assigned. */
1000 : 2315488 : else if (TREE_CODE (t) == ARRAY_TYPE
1001 : 2315488 : && (!TYPE_NONALIASED_COMPONENT (t)
1002 : 0 : || TYPE_STRUCTURAL_EQUALITY_P (t)))
1003 : 393520 : set = get_alias_set (TREE_TYPE (t));
1004 : :
1005 : : /* From the former common C and C++ langhook implementation:
1006 : :
1007 : : Unfortunately, there is no canonical form of a pointer type.
1008 : : In particular, if we have `typedef int I', then `int *', and
1009 : : `I *' are different types. So, we have to pick a canonical
1010 : : representative. We do this below.
1011 : :
1012 : : Technically, this approach is actually more conservative that
1013 : : it needs to be. In particular, `const int *' and `int *'
1014 : : should be in different alias sets, according to the C and C++
1015 : : standard, since their types are not the same, and so,
1016 : : technically, an `int **' and `const int **' cannot point at
1017 : : the same thing.
1018 : :
1019 : : But, the standard is wrong. In particular, this code is
1020 : : legal C++:
1021 : :
1022 : : int *ip;
1023 : : int **ipp = &ip;
1024 : : const int* const* cipp = ipp;
1025 : : And, it doesn't make sense for that to be legal unless you
1026 : : can dereference IPP and CIPP. So, we ignore cv-qualifiers on
1027 : : the pointed-to types. This issue has been reported to the
1028 : : C++ committee.
1029 : :
1030 : : For this reason go to canonical type of the unqalified pointer type.
1031 : : Until GCC 6 this code set all pointers sets to have alias set of
1032 : : ptr_type_node but that is a bad idea, because it prevents disabiguations
1033 : : in between pointers. For Firefox this accounts about 20% of all
1034 : : disambiguations in the program. */
1035 : 1921968 : else if (POINTER_TYPE_P (t) && t != ptr_type_node)
1036 : : {
1037 : 652792 : tree p;
1038 : 652792 : auto_vec <bool, 8> reference;
1039 : :
1040 : : /* Unnest all pointers and references.
1041 : : We also want to make pointer to array/vector equivalent to pointer to
1042 : : its element (see the reasoning above). Skip all those types, too. */
1043 : 652792 : for (p = t; POINTER_TYPE_P (p)
1044 : 710909 : || (TREE_CODE (p) == ARRAY_TYPE
1045 : 56940 : && (!TYPE_NONALIASED_COMPONENT (p)
1046 : 0 : || !COMPLETE_TYPE_P (p)
1047 : 0 : || TYPE_STRUCTURAL_EQUALITY_P (p)))
1048 : 2089968 : || TREE_CODE (p) == VECTOR_TYPE;
1049 : 783207 : p = TREE_TYPE (p))
1050 : : {
1051 : : /* Ada supports recursive pointers. Instead of doing recursion
1052 : : check, just give up once the preallocated space of 8 elements
1053 : : is up. In this case just punt to void * alias set. */
1054 : 783274 : if (reference.length () == 8)
1055 : : {
1056 : 67 : p = ptr_type_node;
1057 : 67 : break;
1058 : : }
1059 : 783207 : if (TREE_CODE (p) == REFERENCE_TYPE)
1060 : : /* In LTO we want languages that use references to be compatible
1061 : : with languages that use pointers. */
1062 : 46553 : reference.safe_push (true && !in_lto_p);
1063 : 783207 : if (TREE_CODE (p) == POINTER_TYPE)
1064 : 678509 : reference.safe_push (false);
1065 : : }
1066 : 652792 : p = TYPE_MAIN_VARIANT (p);
1067 : :
1068 : : /* In LTO for C++ programs we can turn incomplete types to complete
1069 : : using ODR name lookup. */
1070 : 652792 : if (in_lto_p && TYPE_STRUCTURAL_EQUALITY_P (p) && odr_type_p (p))
1071 : : {
1072 : 268 : p = prevailing_odr_type (p);
1073 : 268 : gcc_checking_assert (TYPE_MAIN_VARIANT (p) == p);
1074 : : }
1075 : :
1076 : : /* Make void * compatible with char * and also void **.
1077 : : Programs are commonly violating TBAA by this.
1078 : :
1079 : : We also make void * to conflict with every pointer
1080 : : (see record_component_aliases) and thus it is safe it to use it for
1081 : : pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
1082 : 652792 : if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
1083 : 120294 : set = get_alias_set (ptr_type_node);
1084 : : else
1085 : : {
1086 : : /* Rebuild pointer type starting from canonical types using
1087 : : unqualified pointers and references only. This way all such
1088 : : pointers will have the same alias set and will conflict with
1089 : : each other.
1090 : :
1091 : : Most of time we already have pointers or references of a given type.
1092 : : If not we build new one just to be sure that if someone later
1093 : : (probably only middle-end can, as we should assign all alias
1094 : : classes only after finishing translation unit) builds the pointer
1095 : : type, the canonical type will match. */
1096 : 532498 : p = TYPE_CANONICAL (p);
1097 : 1116621 : while (!reference.is_empty ())
1098 : : {
1099 : 584123 : if (reference.pop ())
1100 : 44903 : p = build_reference_type (p);
1101 : : else
1102 : 539220 : p = build_pointer_type (p);
1103 : 584123 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1104 : : /* build_pointer_type should always return the canonical type.
1105 : : For LTO TYPE_CANOINCAL may be NULL, because we do not compute
1106 : : them. Be sure that frontends do not glob canonical types of
1107 : : pointers in unexpected way and that p == TYPE_CANONICAL (p)
1108 : : in all other cases. */
1109 : 584123 : gcc_checking_assert (!TYPE_CANONICAL (p)
1110 : : || p == TYPE_CANONICAL (p));
1111 : : }
1112 : :
1113 : : /* Assign the alias set to both p and t.
1114 : : We cannot call get_alias_set (p) here as that would trigger
1115 : : infinite recursion when p == t. In other cases it would just
1116 : : trigger unnecesary legwork of rebuilding the pointer again. */
1117 : 532498 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1118 : 532498 : if (TYPE_ALIAS_SET_KNOWN_P (p))
1119 : 65671 : set = TYPE_ALIAS_SET (p);
1120 : : else
1121 : : {
1122 : 466827 : set = new_alias_set ();
1123 : 466827 : TYPE_ALIAS_SET (p) = set;
1124 : : }
1125 : : }
1126 : 652792 : }
1127 : : /* Alias set of ptr_type_node is special and serve as universal pointer which
1128 : : is TBAA compatible with every other pointer type. Be sure we have the
1129 : : alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
1130 : : of pointer types NULL. */
1131 : 1269176 : else if (t == ptr_type_node)
1132 : 61405 : set = new_alias_set ();
1133 : :
1134 : : /* Otherwise make a new alias set for this type. */
1135 : : else
1136 : : {
1137 : : /* Each canonical type gets its own alias set, so canonical types
1138 : : shouldn't form a tree. It doesn't really matter for types
1139 : : we handle specially above, so only check it where it possibly
1140 : : would result in a bogus alias set. */
1141 : 1207771 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
1142 : :
1143 : 1207771 : set = new_alias_set ();
1144 : : }
1145 : :
1146 : 2404554 : TYPE_ALIAS_SET (t) = set;
1147 : :
1148 : : /* If this is an aggregate type or a complex type, we must record any
1149 : : component aliasing information. */
1150 : 2404554 : if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
1151 : 1094326 : record_component_aliases (t);
1152 : :
1153 : : /* We treat pointer types specially in alias_set_subset_of. */
1154 : 2404554 : if (POINTER_TYPE_P (t) && set)
1155 : : {
1156 : 714197 : alias_set_entry *ase = get_alias_set_entry (set);
1157 : 714197 : if (!ase)
1158 : 528232 : ase = init_alias_set_entry (set);
1159 : 714197 : ase->is_pointer = true;
1160 : 714197 : ase->has_pointer = true;
1161 : : }
1162 : :
1163 : : return set;
1164 : : }
1165 : :
1166 : : /* Return a brand-new alias set. */
1167 : :
1168 : : alias_set_type
1169 : 1779829 : new_alias_set (void)
1170 : : {
1171 : 1779829 : if (alias_sets == 0)
1172 : 203093 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1173 : 1779829 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1174 : 1779829 : return alias_sets->length () - 1;
1175 : : }
1176 : :
1177 : : /* Indicate that things in SUBSET can alias things in SUPERSET, but that
1178 : : not everything that aliases SUPERSET also aliases SUBSET. For example,
1179 : : in C, a store to an `int' can alias a load of a structure containing an
1180 : : `int', and vice versa. But it can't alias a load of a 'double' member
1181 : : of the same structure. Here, the structure would be the SUPERSET and
1182 : : `int' the SUBSET. This relationship is also described in the comment at
1183 : : the beginning of this file.
1184 : :
1185 : : This function should be called only once per SUPERSET/SUBSET pair.
1186 : :
1187 : : It is illegal for SUPERSET to be zero; everything is implicitly a
1188 : : subset of alias set zero. */
1189 : :
1190 : : void
1191 : 1921623 : record_alias_subset (alias_set_type superset, alias_set_type subset)
1192 : : {
1193 : 1921623 : alias_set_entry *superset_entry;
1194 : 1921623 : alias_set_entry *subset_entry;
1195 : :
1196 : : /* It is possible in complex type situations for both sets to be the same,
1197 : : in which case we can ignore this operation. */
1198 : 1921623 : if (superset == subset)
1199 : : return;
1200 : :
1201 : 1921623 : gcc_assert (superset);
1202 : :
1203 : 1921623 : superset_entry = get_alias_set_entry (superset);
1204 : 1921623 : if (superset_entry == 0)
1205 : : {
1206 : : /* Create an entry for the SUPERSET, so that we have a place to
1207 : : attach the SUBSET. */
1208 : 622178 : superset_entry = init_alias_set_entry (superset);
1209 : : }
1210 : :
1211 : 1921623 : if (subset == 0)
1212 : 91940 : superset_entry->has_zero_child = 1;
1213 : : else
1214 : : {
1215 : 1829683 : if (!superset_entry->children)
1216 : 608670 : superset_entry->children
1217 : 608670 : = hash_map<alias_set_hash, int>::create_ggc (64);
1218 : :
1219 : : /* Enter the SUBSET itself as a child of the SUPERSET. If it was
1220 : : already there we're done. */
1221 : 1829683 : if (superset_entry->children->put (subset, 0))
1222 : : return;
1223 : :
1224 : 1118685 : subset_entry = get_alias_set_entry (subset);
1225 : : /* If there is an entry for the subset, enter all of its children
1226 : : (if they are not already present) as children of the SUPERSET. */
1227 : 1118685 : if (subset_entry)
1228 : : {
1229 : 688735 : if (subset_entry->has_zero_child)
1230 : 15615 : superset_entry->has_zero_child = true;
1231 : 688735 : if (subset_entry->has_pointer)
1232 : 542977 : superset_entry->has_pointer = true;
1233 : :
1234 : 688735 : if (subset_entry->children)
1235 : : {
1236 : 308120 : hash_map<alias_set_hash, int>::iterator iter
1237 : 308120 : = subset_entry->children->begin ();
1238 : 603102922 : for (; iter != subset_entry->children->end (); ++iter)
1239 : 301089281 : superset_entry->children->put ((*iter).first, (*iter).second);
1240 : : }
1241 : : }
1242 : : }
1243 : : }
1244 : :
1245 : : /* Record that component types of TYPE, if any, are part of SUPERSET for
1246 : : aliasing purposes. For record types, we only record component types
1247 : : for fields that are not marked non-addressable. For array types, we
1248 : : only record the component type if it is not marked non-aliased. */
1249 : :
1250 : : void
1251 : 1186195 : record_component_aliases (tree type, alias_set_type superset)
1252 : : {
1253 : 1186195 : tree field;
1254 : :
1255 : 1186195 : if (superset == 0)
1256 : : return;
1257 : :
1258 : 1124721 : switch (TREE_CODE (type))
1259 : : {
1260 : 696135 : case RECORD_TYPE:
1261 : 696135 : case UNION_TYPE:
1262 : 696135 : case QUAL_UNION_TYPE:
1263 : 696135 : {
1264 : : /* LTO non-ODR type merging does not make any difference between
1265 : : component pointer types. We may have
1266 : :
1267 : : struct foo {int *a;};
1268 : :
1269 : : as TYPE_CANONICAL of
1270 : :
1271 : : struct bar {float *a;};
1272 : :
1273 : : Because accesses to int * and float * do not alias, we would get
1274 : : false negative when accessing the same memory location by
1275 : : float ** and bar *. We thus record the canonical type as:
1276 : :
1277 : : struct {void *a;};
1278 : :
1279 : : void * is special cased and works as a universal pointer type.
1280 : : Accesses to it conflicts with accesses to any other pointer
1281 : : type. */
1282 : 696135 : bool void_pointers = in_lto_p
1283 : 696135 : && (!odr_type_p (type)
1284 : 5572 : || !odr_based_tbaa_p (type));
1285 : 12286395 : for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
1286 : 11590260 : if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
1287 : : {
1288 : 1916551 : tree t = TREE_TYPE (field);
1289 : 1916551 : if (void_pointers)
1290 : : {
1291 : : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1292 : : element type and that type has to be normalized to void *,
1293 : : too, in the case it is a pointer. */
1294 : 26987 : while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
1295 : : {
1296 : 2157 : gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
1297 : 2157 : t = TREE_TYPE (t);
1298 : : }
1299 : 22673 : if (POINTER_TYPE_P (t))
1300 : 6388 : t = ptr_type_node;
1301 : 16285 : else if (flag_checking)
1302 : 16285 : gcc_checking_assert (get_alias_set (t)
1303 : : == get_alias_set (TREE_TYPE (field)));
1304 : : }
1305 : :
1306 : 1916551 : alias_set_type set = get_alias_set (t);
1307 : 1916551 : record_alias_subset (superset, set);
1308 : : /* If the field has alias-set zero make sure to still record
1309 : : any componets of it. This makes sure that for
1310 : : struct A {
1311 : : struct B {
1312 : : int i;
1313 : : char c[4];
1314 : : } b;
1315 : : };
1316 : : in C++ even though 'B' has alias-set zero because
1317 : : TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of
1318 : : 'int' as subset. */
1319 : 1916551 : if (set == 0)
1320 : 91869 : record_component_aliases (t, superset);
1321 : : }
1322 : : }
1323 : : break;
1324 : :
1325 : 5072 : case COMPLEX_TYPE:
1326 : 5072 : record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
1327 : 5072 : break;
1328 : :
1329 : : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1330 : : element type. */
1331 : :
1332 : : default:
1333 : : break;
1334 : : }
1335 : : }
1336 : :
1337 : : /* Record that component types of TYPE, if any, are part of that type for
1338 : : aliasing purposes. For record types, we only record component types
1339 : : for fields that are not marked non-addressable. For array types, we
1340 : : only record the component type if it is not marked non-aliased. */
1341 : :
1342 : : void
1343 : 1094326 : record_component_aliases (tree type)
1344 : : {
1345 : 1094326 : alias_set_type superset = get_alias_set (type);
1346 : 1094326 : record_component_aliases (type, superset);
1347 : 1094326 : }
1348 : :
1349 : :
1350 : : /* Allocate an alias set for use in storing and reading from the varargs
1351 : : spill area. */
1352 : :
1353 : : static GTY(()) alias_set_type varargs_set = -1;
1354 : :
1355 : : alias_set_type
1356 : 20786 : get_varargs_alias_set (void)
1357 : : {
1358 : : #if 1
1359 : : /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1360 : : varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1361 : : consistently use the varargs alias set for loads from the varargs
1362 : : area. So don't use it anywhere. */
1363 : 20786 : return 0;
1364 : : #else
1365 : : if (varargs_set == -1)
1366 : : varargs_set = new_alias_set ();
1367 : :
1368 : : return varargs_set;
1369 : : #endif
1370 : : }
1371 : :
1372 : : /* Likewise, but used for the fixed portions of the frame, e.g., register
1373 : : save areas. */
1374 : :
1375 : : static GTY(()) alias_set_type frame_set = -1;
1376 : :
1377 : : alias_set_type
1378 : 615970 : get_frame_alias_set (void)
1379 : : {
1380 : 615970 : if (frame_set == -1)
1381 : 12648 : frame_set = new_alias_set ();
1382 : :
1383 : 615970 : return frame_set;
1384 : : }
1385 : :
1386 : : /* Create a new, unique base with id ID. */
1387 : :
1388 : : static rtx
1389 : 1790035 : unique_base_value (HOST_WIDE_INT id)
1390 : : {
1391 : 1790035 : return gen_rtx_ADDRESS (Pmode, id);
1392 : : }
1393 : :
1394 : : /* Return true if accesses based on any other base value cannot alias
1395 : : those based on X. */
1396 : :
1397 : : static bool
1398 : 151318751 : unique_base_value_p (rtx x)
1399 : : {
1400 : 122278662 : return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode;
1401 : : }
1402 : :
1403 : : /* Inside SRC, the source of a SET, find a base address. */
1404 : :
1405 : : static rtx
1406 : 405230683 : find_base_value (rtx src)
1407 : : {
1408 : 484850984 : unsigned int regno;
1409 : 484850984 : scalar_int_mode int_mode;
1410 : :
1411 : : #if defined (FIND_BASE_TERM)
1412 : : /* Try machine-dependent ways to find the base term. */
1413 : 484850984 : src = FIND_BASE_TERM (src);
1414 : : #endif
1415 : :
1416 : 484850984 : switch (GET_CODE (src))
1417 : : {
1418 : : case SYMBOL_REF:
1419 : : case LABEL_REF:
1420 : : return src;
1421 : :
1422 : 158920964 : case REG:
1423 : 158920964 : regno = REGNO (src);
1424 : : /* At the start of a function, argument registers have known base
1425 : : values which may be lost later. Returning an ADDRESS
1426 : : expression here allows optimization based on argument values
1427 : : even when the argument registers are used for other purposes. */
1428 : 158920964 : if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1429 : 17962915 : return new_reg_base_value[regno];
1430 : :
1431 : : /* If a pseudo has a known base value, return it. Do not do this
1432 : : for non-fixed hard regs since it can result in a circular
1433 : : dependency chain for registers which have values at function entry.
1434 : :
1435 : : The test above is not sufficient because the scheduler may move
1436 : : a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1437 : 84357768 : if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1438 : 113932875 : && regno < vec_safe_length (reg_base_value))
1439 : : {
1440 : : /* If we're inside init_alias_analysis, use new_reg_base_value
1441 : : to reduce the number of relaxation iterations. */
1442 : 113932875 : if (new_reg_base_value && new_reg_base_value[regno]
1443 : 76576685 : && DF_REG_DEF_COUNT (regno) == 1)
1444 : : return new_reg_base_value[regno];
1445 : :
1446 : 80946625 : if ((*reg_base_value)[regno])
1447 : : return (*reg_base_value)[regno];
1448 : : }
1449 : :
1450 : : return 0;
1451 : :
1452 : 95270477 : case MEM:
1453 : : /* Check for an argument passed in memory. Only record in the
1454 : : copying-arguments block; it is too hard to track changes
1455 : : otherwise. */
1456 : 95270477 : if (copying_arguments
1457 : 3915806 : && (XEXP (src, 0) == arg_pointer_rtx
1458 : 2783372 : || (GET_CODE (XEXP (src, 0)) == PLUS
1459 : 2770121 : && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1460 : 2756542 : return arg_base_value;
1461 : : return 0;
1462 : :
1463 : 942123 : case CONST:
1464 : 942123 : src = XEXP (src, 0);
1465 : 942123 : if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1466 : : break;
1467 : :
1468 : : /* fall through */
1469 : :
1470 : 98399928 : case PLUS:
1471 : 98399928 : case MINUS:
1472 : 98399928 : {
1473 : 98399928 : rtx src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1474 : :
1475 : : /* If either operand is a CONST_INT, then the other is the base. */
1476 : 98399928 : if (CONST_INT_P (src_1))
1477 : : return find_base_value (src_0);
1478 : 20584445 : else if (CONST_INT_P (src_0))
1479 : : return find_base_value (src_1);
1480 : :
1481 : : return 0;
1482 : : }
1483 : :
1484 : 0 : case LO_SUM:
1485 : : /* The standard form is (lo_sum reg sym) so look only at the
1486 : : second operand. */
1487 : 0 : return find_base_value (XEXP (src, 1));
1488 : :
1489 : 5523625 : case AND:
1490 : : /* Look through aligning ANDs. And AND with zero or one with
1491 : : the LSB set isn't one (see for example PR92462). */
1492 : 5523625 : if (CONST_INT_P (XEXP (src, 1))
1493 : 3826945 : && INTVAL (XEXP (src, 1)) != 0
1494 : 3795554 : && (INTVAL (XEXP (src, 1)) & 1) == 0)
1495 : 1704450 : return find_base_value (XEXP (src, 0));
1496 : : return 0;
1497 : :
1498 : 11885 : case TRUNCATE:
1499 : : /* As we do not know which address space the pointer is referring to, we can
1500 : : handle this only if the target does not support different pointer or
1501 : : address modes depending on the address space. */
1502 : 11885 : if (!target_default_pointer_address_modes_p ())
1503 : : break;
1504 : 11885 : if (!is_a <scalar_int_mode> (GET_MODE (src), &int_mode)
1505 : 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1506 : : break;
1507 : : /* Fall through. */
1508 : 0 : case HIGH:
1509 : 0 : case PRE_INC:
1510 : 0 : case PRE_DEC:
1511 : 0 : case POST_INC:
1512 : 0 : case POST_DEC:
1513 : 0 : case PRE_MODIFY:
1514 : 0 : case POST_MODIFY:
1515 : 0 : return find_base_value (XEXP (src, 0));
1516 : :
1517 : 9589567 : case ZERO_EXTEND:
1518 : 9589567 : case SIGN_EXTEND: /* used for NT/Alpha pointers */
1519 : : /* As we do not know which address space the pointer is referring to, we can
1520 : : handle this only if the target does not support different pointer or
1521 : : address modes depending on the address space. */
1522 : 9589567 : if (!target_default_pointer_address_modes_p ())
1523 : : break;
1524 : :
1525 : 9589567 : {
1526 : 9589567 : rtx temp = find_base_value (XEXP (src, 0));
1527 : :
1528 : 9589567 : if (temp != 0 && CONSTANT_P (temp))
1529 : 104 : temp = convert_memory_address (Pmode, temp);
1530 : :
1531 : : return temp;
1532 : : }
1533 : :
1534 : : default:
1535 : : break;
1536 : : }
1537 : :
1538 : : return 0;
1539 : : }
1540 : :
1541 : : /* Called from init_alias_analysis indirectly through note_stores,
1542 : : or directly if DEST is a register with a REG_NOALIAS note attached.
1543 : : SET is null in the latter case. */
1544 : :
1545 : : /* While scanning insns to find base values, reg_seen[N] is nonzero if
1546 : : register N has been set in this function. */
1547 : : static sbitmap reg_seen;
1548 : :
1549 : : static void
1550 : 1271788799 : record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1551 : : {
1552 : 1271788799 : unsigned regno;
1553 : 1271788799 : rtx src;
1554 : 1271788799 : int n;
1555 : :
1556 : 1271788799 : if (!REG_P (dest))
1557 : : return;
1558 : :
1559 : 970143059 : regno = REGNO (dest);
1560 : :
1561 : 970143059 : gcc_checking_assert (regno < reg_base_value->length ());
1562 : :
1563 : 970143059 : n = REG_NREGS (dest);
1564 : 970143059 : if (n != 1)
1565 : : {
1566 : 14735838 : while (--n >= 0)
1567 : : {
1568 : 9824300 : bitmap_set_bit (reg_seen, regno + n);
1569 : 9824300 : new_reg_base_value[regno + n] = 0;
1570 : : }
1571 : : return;
1572 : : }
1573 : :
1574 : 965231521 : if (set)
1575 : : {
1576 : : /* A CLOBBER wipes out any old value but does not prevent a previously
1577 : : unset register from acquiring a base address (i.e. reg_seen is not
1578 : : set). */
1579 : 963878676 : if (GET_CODE (set) == CLOBBER)
1580 : : {
1581 : 166946668 : new_reg_base_value[regno] = 0;
1582 : 166946668 : return;
1583 : : }
1584 : :
1585 : 796932008 : src = SET_SRC (set);
1586 : : }
1587 : : else
1588 : : {
1589 : : /* There's a REG_NOALIAS note against DEST. */
1590 : 1352845 : if (bitmap_bit_p (reg_seen, regno))
1591 : : {
1592 : 402562 : new_reg_base_value[regno] = 0;
1593 : 402562 : return;
1594 : : }
1595 : 950283 : bitmap_set_bit (reg_seen, regno);
1596 : 950283 : new_reg_base_value[regno] = unique_base_value (unique_id++);
1597 : 950283 : return;
1598 : : }
1599 : :
1600 : : /* If this is not the first set of REGNO, see whether the new value
1601 : : is related to the old one. There are two cases of interest:
1602 : :
1603 : : (1) The register might be assigned an entirely new value
1604 : : that has the same base term as the original set.
1605 : :
1606 : : (2) The set might be a simple self-modification that
1607 : : cannot change REGNO's base value.
1608 : :
1609 : : If neither case holds, reject the original base value as invalid.
1610 : : Note that the following situation is not detected:
1611 : :
1612 : : extern int x, y; int *p = &x; p += (&y-&x);
1613 : :
1614 : : ANSI C does not allow computing the difference of addresses
1615 : : of distinct top level objects. */
1616 : 796932008 : if (new_reg_base_value[regno] != 0
1617 : 796932008 : && find_base_value (src) != new_reg_base_value[regno])
1618 : 72159534 : switch (GET_CODE (src))
1619 : : {
1620 : 434343 : case LO_SUM:
1621 : 434343 : case MINUS:
1622 : 434343 : if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1623 : 75811 : new_reg_base_value[regno] = 0;
1624 : : break;
1625 : 22059653 : case PLUS:
1626 : : /* If the value we add in the PLUS is also a valid base value,
1627 : : this might be the actual base value, and the original value
1628 : : an index. */
1629 : 22059653 : {
1630 : 22059653 : rtx other = NULL_RTX;
1631 : :
1632 : 22059653 : if (XEXP (src, 0) == dest)
1633 : 19207179 : other = XEXP (src, 1);
1634 : 2852474 : else if (XEXP (src, 1) == dest)
1635 : : other = XEXP (src, 0);
1636 : :
1637 : 19495536 : if (! other || find_base_value (other))
1638 : 2569061 : new_reg_base_value[regno] = 0;
1639 : : break;
1640 : : }
1641 : 70412 : case AND:
1642 : 70412 : if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1643 : 53045 : new_reg_base_value[regno] = 0;
1644 : : break;
1645 : 49595126 : default:
1646 : 49595126 : new_reg_base_value[regno] = 0;
1647 : 49595126 : break;
1648 : : }
1649 : : /* If this is the first set of a register, record the value. */
1650 : 425103800 : else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1651 : 1028894940 : && ! bitmap_bit_p (reg_seen, regno) && new_reg_base_value[regno] == 0)
1652 : 271601852 : new_reg_base_value[regno] = find_base_value (src);
1653 : :
1654 : 796932008 : bitmap_set_bit (reg_seen, regno);
1655 : : }
1656 : :
1657 : : /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1658 : : using hard registers with non-null REG_BASE_VALUE for renaming. */
1659 : : rtx
1660 : 1532 : get_reg_base_value (unsigned int regno)
1661 : : {
1662 : 1532 : return (*reg_base_value)[regno];
1663 : : }
1664 : :
1665 : : /* If a value is known for REGNO, return it. */
1666 : :
1667 : : rtx
1668 : 240558663 : get_reg_known_value (unsigned int regno)
1669 : : {
1670 : 240558663 : if (regno >= FIRST_PSEUDO_REGISTER)
1671 : : {
1672 : 226135450 : regno -= FIRST_PSEUDO_REGISTER;
1673 : 437274400 : if (regno < vec_safe_length (reg_known_value))
1674 : 211138950 : return (*reg_known_value)[regno];
1675 : : }
1676 : : return NULL;
1677 : : }
1678 : :
1679 : : /* Set it. */
1680 : :
1681 : : static void
1682 : 479582249 : set_reg_known_value (unsigned int regno, rtx val)
1683 : : {
1684 : 479582249 : if (regno >= FIRST_PSEUDO_REGISTER)
1685 : : {
1686 : 479582249 : regno -= FIRST_PSEUDO_REGISTER;
1687 : 959164498 : if (regno < vec_safe_length (reg_known_value))
1688 : 479582249 : (*reg_known_value)[regno] = val;
1689 : : }
1690 : 479582249 : }
1691 : :
1692 : : /* Similarly for reg_known_equiv_p. */
1693 : :
1694 : : bool
1695 : 43936 : get_reg_known_equiv_p (unsigned int regno)
1696 : : {
1697 : 43936 : if (regno >= FIRST_PSEUDO_REGISTER)
1698 : : {
1699 : 43936 : regno -= FIRST_PSEUDO_REGISTER;
1700 : 87872 : if (regno < vec_safe_length (reg_known_value))
1701 : 43166 : return bitmap_bit_p (reg_known_equiv_p, regno);
1702 : : }
1703 : : return false;
1704 : : }
1705 : :
1706 : : static void
1707 : 38100954 : set_reg_known_equiv_p (unsigned int regno, bool val)
1708 : : {
1709 : 38100954 : if (regno >= FIRST_PSEUDO_REGISTER)
1710 : : {
1711 : 38100954 : regno -= FIRST_PSEUDO_REGISTER;
1712 : 76201908 : if (regno < vec_safe_length (reg_known_value))
1713 : : {
1714 : 38100954 : if (val)
1715 : 0 : bitmap_set_bit (reg_known_equiv_p, regno);
1716 : : else
1717 : 38100954 : bitmap_clear_bit (reg_known_equiv_p, regno);
1718 : : }
1719 : : }
1720 : 38100954 : }
1721 : :
1722 : :
1723 : : /* Returns a canonical version of X, from the point of view alias
1724 : : analysis. (For example, if X is a MEM whose address is a register,
1725 : : and the register has a known value (say a SYMBOL_REF), then a MEM
1726 : : whose address is the SYMBOL_REF is returned.) */
1727 : :
1728 : : rtx
1729 : 5037544644 : canon_rtx (rtx x)
1730 : : {
1731 : : /* Recursively look for equivalences. */
1732 : 5040910245 : if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1733 : : {
1734 : 201106046 : rtx t = get_reg_known_value (REGNO (x));
1735 : 201106046 : if (t == x)
1736 : : return x;
1737 : 18362101 : if (t)
1738 : : return canon_rtx (t);
1739 : : }
1740 : :
1741 : 4854800699 : if (GET_CODE (x) == PLUS)
1742 : : {
1743 : 1403724620 : rtx x0 = canon_rtx (XEXP (x, 0));
1744 : 1403724620 : rtx x1 = canon_rtx (XEXP (x, 1));
1745 : :
1746 : 1403724620 : if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1747 : 2267611 : return simplify_gen_binary (PLUS, GET_MODE (x), x0, x1);
1748 : : }
1749 : :
1750 : : /* This gives us much better alias analysis when called from
1751 : : the loop optimizer. Note we want to leave the original
1752 : : MEM alone, but need to return the canonicalized MEM with
1753 : : all the flags with their original values. */
1754 : 3451076079 : else if (MEM_P (x))
1755 : 297893825 : x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1756 : :
1757 : : return x;
1758 : : }
1759 : :
1760 : : /* Return true if X and Y are identical-looking rtx's.
1761 : : Expect that X and Y has been already canonicalized.
1762 : :
1763 : : We use the data in reg_known_value above to see if two registers with
1764 : : different numbers are, in fact, equivalent. */
1765 : :
1766 : : static bool
1767 : 8474521345 : rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1768 : : {
1769 : 8474537698 : int i;
1770 : 8474537698 : int j;
1771 : 8474537698 : enum rtx_code code;
1772 : 8474537698 : const char *fmt;
1773 : :
1774 : 8474537698 : if (x == 0 && y == 0)
1775 : : return true;
1776 : 8474537698 : if (x == 0 || y == 0)
1777 : : return false;
1778 : :
1779 : 8474537698 : if (x == y)
1780 : : return true;
1781 : :
1782 : 6818755882 : code = GET_CODE (x);
1783 : : /* Rtx's of different codes cannot be equal. */
1784 : 6818755882 : if (code != GET_CODE (y))
1785 : : return false;
1786 : :
1787 : : /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1788 : : (REG:SI x) and (REG:HI x) are NOT equivalent. */
1789 : :
1790 : 4650041655 : if (GET_MODE (x) != GET_MODE (y))
1791 : : return false;
1792 : :
1793 : : /* Some RTL can be compared without a recursive examination. */
1794 : 4650041504 : switch (code)
1795 : : {
1796 : 215001615 : case REG:
1797 : 215001615 : return REGNO (x) == REGNO (y);
1798 : :
1799 : 0 : case LABEL_REF:
1800 : 0 : return label_ref_label (x) == label_ref_label (y);
1801 : :
1802 : 3717486 : case SYMBOL_REF:
1803 : 3717486 : {
1804 : 3717486 : HOST_WIDE_INT distance = 0;
1805 : 3717486 : return (compare_base_symbol_refs (x, y, &distance) == 1
1806 : 3717486 : && distance == 0);
1807 : : }
1808 : :
1809 : 1965173 : case ENTRY_VALUE:
1810 : : /* This is magic, don't go through canonicalization et al. */
1811 : 1965173 : return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1812 : :
1813 : : case VALUE:
1814 : : CASE_CONST_UNIQUE:
1815 : : /* Pointer equality guarantees equality for these nodes. */
1816 : : return false;
1817 : :
1818 : 1333916144 : default:
1819 : 1333916144 : break;
1820 : : }
1821 : :
1822 : : /* canon_rtx knows how to handle plus. No need to canonicalize. */
1823 : 1333916144 : if (code == PLUS)
1824 : 1317024319 : return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1825 : 634208941 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1826 : 1943926883 : || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1827 : 136625 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1828 : : /* For commutative operations, the RTX match if the operand match in any
1829 : : order. Also handle the simple binary and unary cases without a loop. */
1830 : 16891825 : if (COMMUTATIVE_P (x))
1831 : : {
1832 : 3601930 : rtx xop0 = canon_rtx (XEXP (x, 0));
1833 : 3601930 : rtx yop0 = canon_rtx (XEXP (y, 0));
1834 : 3601930 : rtx yop1 = canon_rtx (XEXP (y, 1));
1835 : :
1836 : 3601930 : return ((rtx_equal_for_memref_p (xop0, yop0)
1837 : 1260684 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1838 : 3711886 : || (rtx_equal_for_memref_p (xop0, yop1)
1839 : 18 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1840 : : }
1841 : 13289895 : else if (NON_COMMUTATIVE_P (x))
1842 : : {
1843 : 143046 : return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1844 : 143046 : canon_rtx (XEXP (y, 0)))
1845 : 196548 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1846 : 53502 : canon_rtx (XEXP (y, 1))));
1847 : : }
1848 : 13146849 : else if (UNARY_P (x))
1849 : 16353 : return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1850 : 32706 : canon_rtx (XEXP (y, 0)));
1851 : :
1852 : : /* Compare the elements. If any pair of corresponding elements
1853 : : fail to match, return false for the whole things.
1854 : :
1855 : : Limit cases to types which actually appear in addresses. */
1856 : :
1857 : 13130496 : fmt = GET_RTX_FORMAT (code);
1858 : 20315121 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1859 : : {
1860 : 19778720 : switch (fmt[i])
1861 : : {
1862 : 3386928 : case 'i':
1863 : 3386928 : if (XINT (x, i) != XINT (y, i))
1864 : : return false;
1865 : : break;
1866 : :
1867 : 66 : case 'p':
1868 : 66 : if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1869 : : return false;
1870 : : break;
1871 : :
1872 : 3386736 : case 'E':
1873 : : /* Two vectors must have the same length. */
1874 : 3386736 : if (XVECLEN (x, i) != XVECLEN (y, i))
1875 : : return false;
1876 : :
1877 : : /* And the corresponding elements must match. */
1878 : 3633163 : for (j = 0; j < XVECLEN (x, i); j++)
1879 : 3387777 : if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1880 : 3387777 : canon_rtx (XVECEXP (y, i, j))) == 0)
1881 : : return false;
1882 : : break;
1883 : :
1884 : 9833852 : case 'e':
1885 : 9833852 : if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1886 : 9833852 : canon_rtx (XEXP (y, i))) == 0)
1887 : : return false;
1888 : : break;
1889 : :
1890 : : /* This can happen for asm operands. */
1891 : 0 : case 's':
1892 : 0 : if (strcmp (XSTR (x, i), XSTR (y, i)))
1893 : : return false;
1894 : : break;
1895 : :
1896 : : /* This can happen for an asm which clobbers memory. */
1897 : : case '0':
1898 : : break;
1899 : :
1900 : : /* It is believed that rtx's at this level will never
1901 : : contain anything but integers and other rtx's,
1902 : : except for within LABEL_REFs and SYMBOL_REFs. */
1903 : 0 : default:
1904 : 0 : gcc_unreachable ();
1905 : : }
1906 : : }
1907 : : return true;
1908 : : }
1909 : :
1910 : : static rtx
1911 : 3106392753 : find_base_term (rtx x, vec<std::pair<cselib_val *,
1912 : : struct elt_loc_list *> > &visited_vals)
1913 : : {
1914 : 5920766137 : cselib_val *val;
1915 : 5920766137 : struct elt_loc_list *l, *f;
1916 : 5920766137 : rtx ret;
1917 : 5920766137 : scalar_int_mode int_mode;
1918 : :
1919 : : #if defined (FIND_BASE_TERM)
1920 : : /* Try machine-dependent ways to find the base term. */
1921 : 5920766137 : x = FIND_BASE_TERM (x);
1922 : : #endif
1923 : :
1924 : 5920766137 : switch (GET_CODE (x))
1925 : : {
1926 : 2057978756 : case REG:
1927 : 2057978756 : return REG_BASE_VALUE (x);
1928 : :
1929 : 0 : case TRUNCATE:
1930 : : /* As we do not know which address space the pointer is referring to, we can
1931 : : handle this only if the target does not support different pointer or
1932 : : address modes depending on the address space. */
1933 : 0 : if (!target_default_pointer_address_modes_p ())
1934 : : return 0;
1935 : 93653139 : if (!is_a <scalar_int_mode> (GET_MODE (x), &int_mode)
1936 : 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1937 : : return 0;
1938 : : /* Fall through. */
1939 : 43108753 : case HIGH:
1940 : 43108753 : case PRE_INC:
1941 : 43108753 : case PRE_DEC:
1942 : 43108753 : case POST_INC:
1943 : 43108753 : case POST_DEC:
1944 : 43108753 : case PRE_MODIFY:
1945 : 43108753 : case POST_MODIFY:
1946 : 43108753 : return find_base_term (XEXP (x, 0), visited_vals);
1947 : :
1948 : 397 : case ZERO_EXTEND:
1949 : 397 : case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1950 : : /* As we do not know which address space the pointer is referring to, we can
1951 : : handle this only if the target does not support different pointer or
1952 : : address modes depending on the address space. */
1953 : 397 : if (!target_default_pointer_address_modes_p ())
1954 : : return 0;
1955 : :
1956 : 397 : {
1957 : 397 : rtx temp = find_base_term (XEXP (x, 0), visited_vals);
1958 : :
1959 : 397 : if (temp != 0 && CONSTANT_P (temp))
1960 : 0 : temp = convert_memory_address (Pmode, temp);
1961 : :
1962 : : return temp;
1963 : : }
1964 : :
1965 : 830203477 : case VALUE:
1966 : 830203477 : val = CSELIB_VAL_PTR (x);
1967 : 830203477 : ret = NULL_RTX;
1968 : :
1969 : 830203477 : if (!val)
1970 : : return ret;
1971 : :
1972 : 830203477 : if (cselib_sp_based_value_p (val))
1973 : 19313714 : return static_reg_base_value[STACK_POINTER_REGNUM];
1974 : :
1975 : 1621779526 : if (visited_vals.length () > (unsigned) param_max_find_base_term_values)
1976 : : return ret;
1977 : :
1978 : 808887834 : f = val->locs;
1979 : : /* Reset val->locs to avoid infinite recursion. */
1980 : 808887834 : if (f)
1981 : 643765796 : visited_vals.safe_push (std::make_pair (val, f));
1982 : 808887834 : val->locs = NULL;
1983 : :
1984 : 1451880618 : for (l = f; l; l = l->next)
1985 : 809224848 : if (GET_CODE (l->loc) == VALUE
1986 : 111730449 : && CSELIB_VAL_PTR (l->loc)->locs
1987 : 111722344 : && !CSELIB_VAL_PTR (l->loc)->locs->next
1988 : 111718071 : && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
1989 : 111718071 : continue;
1990 : 697506777 : else if ((ret = find_base_term (l->loc, visited_vals)) != 0)
1991 : : break;
1992 : :
1993 : : return ret;
1994 : :
1995 : 0 : case LO_SUM:
1996 : : /* The standard form is (lo_sum reg sym) so look only at the
1997 : : second operand. */
1998 : 0 : return find_base_term (XEXP (x, 1), visited_vals);
1999 : :
2000 : 30407114 : case CONST:
2001 : 30407114 : x = XEXP (x, 0);
2002 : 30407114 : if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
2003 : : return 0;
2004 : : /* Fall through. */
2005 : 2753263519 : case PLUS:
2006 : 2753263519 : case MINUS:
2007 : 2753263519 : {
2008 : 2753263519 : rtx tmp1 = XEXP (x, 0);
2009 : 2753263519 : rtx tmp2 = XEXP (x, 1);
2010 : :
2011 : : /* This is a little bit tricky since we have to determine which of
2012 : : the two operands represents the real base address. Otherwise this
2013 : : routine may return the index register instead of the base register.
2014 : :
2015 : : That may cause us to believe no aliasing was possible, when in
2016 : : fact aliasing is possible.
2017 : :
2018 : : We use a few simple tests to guess the base register. Additional
2019 : : tests can certainly be added. For example, if one of the operands
2020 : : is a shift or multiply, then it must be the index register and the
2021 : : other operand is the base register. */
2022 : :
2023 : 2753263519 : if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
2024 : : return find_base_term (tmp2, visited_vals);
2025 : :
2026 : 2753263515 : if (CONST_INT_P (tmp1))
2027 : 0 : std::swap (tmp1, tmp2);
2028 : :
2029 : : /* We can only handle binary operators when one of the operands
2030 : : never leads to a base value. */
2031 : 2753263515 : if (CONST_INT_P (tmp2))
2032 : : return find_base_term (tmp1, visited_vals);
2033 : :
2034 : : /* We could not determine which of the two operands was the
2035 : : base register and which was the index. So we can determine
2036 : : nothing from the base alias check. */
2037 : : return 0;
2038 : : }
2039 : :
2040 : 70499905 : case AND:
2041 : : /* Look through aligning ANDs. And AND with zero or one with
2042 : : the LSB set isn't one (see for example PR92462). */
2043 : 70499905 : if (CONST_INT_P (XEXP (x, 1))
2044 : 70499856 : && INTVAL (XEXP (x, 1)) != 0
2045 : 70499856 : && (INTVAL (XEXP (x, 1)) & 1) == 0)
2046 : 70499852 : return find_base_term (XEXP (x, 0), visited_vals);
2047 : : return 0;
2048 : :
2049 : : case SYMBOL_REF:
2050 : : case LABEL_REF:
2051 : : return x;
2052 : :
2053 : : default:
2054 : : return 0;
2055 : : }
2056 : : }
2057 : :
2058 : : /* Wrapper around the worker above which removes locs from visited VALUEs
2059 : : to avoid visiting them multiple times. We unwind that changes here. */
2060 : :
2061 : : static rtx
2062 : 2408885579 : find_base_term (rtx x)
2063 : : {
2064 : 2408885579 : auto_vec<std::pair<cselib_val *, struct elt_loc_list *>, 32> visited_vals;
2065 : 2408885579 : rtx res = find_base_term (x, visited_vals);
2066 : 6105302750 : for (unsigned i = 0; i < visited_vals.length (); ++i)
2067 : 643765796 : visited_vals[i].first->locs = visited_vals[i].second;
2068 : 2408885579 : return res;
2069 : 2408885579 : }
2070 : :
2071 : : /* Return true if accesses to address X may alias accesses based
2072 : : on the stack pointer. */
2073 : :
2074 : : bool
2075 : 13665583 : may_be_sp_based_p (rtx x)
2076 : : {
2077 : 13665583 : rtx base = find_base_term (x);
2078 : 13665583 : return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
2079 : : }
2080 : :
2081 : : /* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2082 : : if they refer to different objects and -1 if we cannot decide. */
2083 : :
2084 : : int
2085 : 1339965503 : compare_base_decls (tree base1, tree base2)
2086 : : {
2087 : 1339965503 : int ret;
2088 : 1339965503 : gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2089 : 1339965503 : if (base1 == base2)
2090 : : return 1;
2091 : :
2092 : : /* If we have two register decls with register specification we
2093 : : cannot decide unless their assembler names are the same. */
2094 : 1165760717 : if (VAR_P (base1)
2095 : 1118483067 : && VAR_P (base2)
2096 : 1113991095 : && DECL_HARD_REGISTER (base1)
2097 : 13209 : && DECL_HARD_REGISTER (base2)
2098 : 12742 : && DECL_ASSEMBLER_NAME_SET_P (base1)
2099 : 1165773459 : && DECL_ASSEMBLER_NAME_SET_P (base2))
2100 : : {
2101 : 12742 : if (DECL_ASSEMBLER_NAME_RAW (base1) == DECL_ASSEMBLER_NAME_RAW (base2))
2102 : : return 1;
2103 : 12730 : return -1;
2104 : : }
2105 : :
2106 : : /* Declarations of non-automatic variables may have aliases. All other
2107 : : decls are unique. */
2108 : 1165747975 : if (!decl_in_symtab_p (base1)
2109 : 1165747975 : || !decl_in_symtab_p (base2))
2110 : : return 0;
2111 : :
2112 : : /* Don't cause symbols to be inserted by the act of checking. */
2113 : 83069162 : symtab_node *node1 = symtab_node::get (base1);
2114 : 83069162 : if (!node1)
2115 : : return 0;
2116 : 83053849 : symtab_node *node2 = symtab_node::get (base2);
2117 : 83053849 : if (!node2)
2118 : : return 0;
2119 : :
2120 : 83035113 : ret = node1->equal_address_to (node2, true);
2121 : 83035113 : return ret;
2122 : : }
2123 : :
2124 : : /* Compare SYMBOL_REFs X_BASE and Y_BASE.
2125 : :
2126 : : - Return 1 if Y_BASE - X_BASE is constant, adding that constant
2127 : : to *DISTANCE if DISTANCE is nonnull.
2128 : :
2129 : : - Return 0 if no accesses based on X_BASE can alias Y_BASE.
2130 : :
2131 : : - Return -1 if one of the two results applies, but we can't tell
2132 : : which at compile time. Update DISTANCE in the same way as
2133 : : for a return value of 1, for the case in which that holds. */
2134 : :
2135 : : static int
2136 : 22325704 : compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
2137 : : HOST_WIDE_INT *distance)
2138 : : {
2139 : 22325704 : tree x_decl = SYMBOL_REF_DECL (x_base);
2140 : 22325704 : tree y_decl = SYMBOL_REF_DECL (y_base);
2141 : 22325704 : bool binds_def = true;
2142 : 22325704 : bool swap = false;
2143 : :
2144 : 22325704 : if (XSTR (x_base, 0) == XSTR (y_base, 0))
2145 : : return 1;
2146 : 21971170 : if (x_decl && y_decl)
2147 : 21971170 : return compare_base_decls (x_decl, y_decl);
2148 : 0 : if (x_decl || y_decl)
2149 : : {
2150 : : if (!x_decl)
2151 : : {
2152 : : swap = true;
2153 : : std::swap (x_decl, y_decl);
2154 : : std::swap (x_base, y_base);
2155 : : }
2156 : : /* We handle specially only section anchors. Other symbols are
2157 : : either equal (via aliasing) or refer to different objects. */
2158 : 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2159 : : return -1;
2160 : : /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2161 : : to ignore CONST_DECLs because they are readonly. */
2162 : 0 : if (!VAR_P (x_decl)
2163 : 0 : || (!TREE_STATIC (x_decl) && !TREE_PUBLIC (x_decl)))
2164 : : return 0;
2165 : :
2166 : 0 : symtab_node *x_node = symtab_node::get_create (x_decl)
2167 : 0 : ->ultimate_alias_target ();
2168 : : /* External variable cannot be in section anchor. */
2169 : 0 : if (!x_node->definition)
2170 : : return 0;
2171 : 0 : x_base = XEXP (DECL_RTL (x_node->decl), 0);
2172 : : /* If not in anchor, we can disambiguate. */
2173 : 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base))
2174 : : return 0;
2175 : :
2176 : : /* We have an alias of anchored variable. If it can be interposed;
2177 : : we must assume it may or may not alias its anchor. */
2178 : 0 : binds_def = decl_binds_to_current_def_p (x_decl);
2179 : : }
2180 : : /* If we have variable in section anchor, we can compare by offset. */
2181 : 0 : if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base)
2182 : 0 : && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2183 : : {
2184 : 0 : if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
2185 : : return 0;
2186 : 0 : if (distance)
2187 : 0 : *distance += (swap ? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base)
2188 : 0 : - SYMBOL_REF_BLOCK_OFFSET (x_base));
2189 : 0 : return binds_def ? 1 : -1;
2190 : : }
2191 : : /* Either the symbols are equal (via aliasing) or they refer to
2192 : : different objects. */
2193 : : return -1;
2194 : : }
2195 : :
2196 : : /* Return false if the addresses X and Y are known to point to different
2197 : : objects, true if they might be pointers to the same object. */
2198 : :
2199 : : static bool
2200 : 1197516428 : base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base,
2201 : : machine_mode x_mode, machine_mode y_mode)
2202 : : {
2203 : : /* If the address itself has no known base see if a known equivalent
2204 : : value has one. If either address still has no known base, nothing
2205 : : is known about aliasing. */
2206 : 1197516428 : if (x_base == 0)
2207 : : {
2208 : 143552185 : rtx x_c;
2209 : :
2210 : 143552185 : if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
2211 : 143397323 : return true;
2212 : :
2213 : 154862 : x_base = find_base_term (x_c);
2214 : 154862 : if (x_base == 0)
2215 : : return true;
2216 : : }
2217 : :
2218 : 1053966238 : if (y_base == 0)
2219 : : {
2220 : 160627384 : rtx y_c;
2221 : 160627384 : if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
2222 : 160596756 : return true;
2223 : :
2224 : 30628 : y_base = find_base_term (y_c);
2225 : 30628 : if (y_base == 0)
2226 : : return true;
2227 : : }
2228 : :
2229 : : /* If the base addresses are equal nothing is known about aliasing. */
2230 : 893341390 : if (rtx_equal_p (x_base, y_base))
2231 : : return true;
2232 : :
2233 : : /* The base addresses are different expressions. If they are not accessed
2234 : : via AND, there is no conflict. We can bring knowledge of object
2235 : : alignment into play here. For example, on alpha, "char a, b;" can
2236 : : alias one another, though "char a; long b;" cannot. AND addresses may
2237 : : implicitly alias surrounding objects; i.e. unaligned access in DImode
2238 : : via AND address can alias all surrounding object types except those
2239 : : with aligment 8 or higher. */
2240 : 130575072 : if (GET_CODE (x) == AND && GET_CODE (y) == AND)
2241 : : return true;
2242 : 130575072 : if (GET_CODE (x) == AND
2243 : 130575072 : && (!CONST_INT_P (XEXP (x, 1))
2244 : 2940 : || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
2245 : : return true;
2246 : 130572302 : if (GET_CODE (y) == AND
2247 : 130572302 : && (!CONST_INT_P (XEXP (y, 1))
2248 : 2511 : || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
2249 : : return true;
2250 : :
2251 : : /* Differing symbols not accessed via AND never alias. */
2252 : 130569900 : if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF)
2253 : 18115559 : return compare_base_symbol_refs (x_base, y_base) != 0;
2254 : :
2255 : 112454341 : if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
2256 : : return false;
2257 : :
2258 : 122602789 : if (unique_base_value_p (x_base) || unique_base_value_p (y_base))
2259 : : return false;
2260 : :
2261 : : return true;
2262 : : }
2263 : :
2264 : : /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2265 : : (or equal to) that of V. */
2266 : :
2267 : : static bool
2268 : 237566909 : refs_newer_value_p (const_rtx expr, rtx v)
2269 : : {
2270 : 237566909 : int minuid = CSELIB_VAL_PTR (v)->uid;
2271 : 237566909 : subrtx_iterator::array_type array;
2272 : 668700254 : FOR_EACH_SUBRTX (iter, array, expr, NONCONST)
2273 : 572176206 : if (GET_CODE (*iter) == VALUE && CSELIB_VAL_PTR (*iter)->uid >= minuid)
2274 : 141042861 : return true;
2275 : 96524048 : return false;
2276 : 237566909 : }
2277 : :
2278 : : /* Convert the address X into something we can use. This is done by returning
2279 : : it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2280 : : we call cselib to get a more useful rtx. */
2281 : :
2282 : : rtx
2283 : 3728992909 : get_addr (rtx x)
2284 : : {
2285 : 3728992909 : cselib_val *v;
2286 : 3728992909 : struct elt_loc_list *l;
2287 : :
2288 : 3728992909 : if (GET_CODE (x) != VALUE)
2289 : : {
2290 : 2355182568 : if ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
2291 : 1997939310 : && GET_CODE (XEXP (x, 0)) == VALUE
2292 : 114156309 : && CONST_SCALAR_INT_P (XEXP (x, 1)))
2293 : : {
2294 : 107977849 : rtx op0 = get_addr (XEXP (x, 0));
2295 : 107977849 : if (op0 != XEXP (x, 0))
2296 : : {
2297 : 29447014 : poly_int64 c;
2298 : 29447014 : if (GET_CODE (x) == PLUS
2299 : 29447014 : && poly_int_rtx_p (XEXP (x, 1), &c))
2300 : 29447014 : return plus_constant (GET_MODE (x), op0, c);
2301 : 0 : return simplify_gen_binary (GET_CODE (x), GET_MODE (x),
2302 : 0 : op0, XEXP (x, 1));
2303 : : }
2304 : : }
2305 : 2325735554 : return x;
2306 : : }
2307 : 1373810341 : v = CSELIB_VAL_PTR (x);
2308 : 1373810341 : if (v)
2309 : : {
2310 : 1373810341 : bool have_equivs = cselib_have_permanent_equivalences ();
2311 : 1373810341 : if (have_equivs)
2312 : 327267362 : v = canonical_cselib_val (v);
2313 : 2675514822 : for (l = v->locs; l; l = l->next)
2314 : 1326274524 : if (CONSTANT_P (l->loc))
2315 : 24570043 : return l->loc;
2316 : 1608301914 : for (l = v->locs; l; l = l->next)
2317 : 1229828173 : if (!REG_P (l->loc) && !MEM_P (l->loc)
2318 : : /* Avoid infinite recursion when potentially dealing with
2319 : : var-tracking artificial equivalences, by skipping the
2320 : : equivalences themselves, and not choosing expressions
2321 : : that refer to newer VALUEs. */
2322 : 2525644944 : && (!have_equivs
2323 : 277420594 : || (GET_CODE (l->loc) != VALUE
2324 : 166251437 : && !refs_newer_value_p (l->loc, x))))
2325 : 1042431745 : return l->loc;
2326 : 306808553 : if (have_equivs)
2327 : : {
2328 : 366653249 : for (l = v->locs; l; l = l->next)
2329 : 147088675 : if (REG_P (l->loc)
2330 : 147088675 : || (GET_CODE (l->loc) != VALUE
2331 : 71315472 : && !refs_newer_value_p (l->loc, x)))
2332 : 6233119 : return l->loc;
2333 : : /* Return the canonical value. */
2334 : 219564574 : return v->val_rtx;
2335 : : }
2336 : 81010860 : if (v->locs)
2337 : 44184760 : return v->locs->loc;
2338 : : }
2339 : : return x;
2340 : : }
2341 : :
2342 : : /* Return the address of the (N_REFS + 1)th memory reference to ADDR
2343 : : where SIZE is the size in bytes of the memory reference. If ADDR
2344 : : is not modified by the memory reference then ADDR is returned. */
2345 : :
2346 : : static rtx
2347 : 5154419204 : addr_side_effect_eval (rtx addr, poly_int64 size, int n_refs)
2348 : : {
2349 : 5154419204 : poly_int64 offset = 0;
2350 : :
2351 : 5154419204 : switch (GET_CODE (addr))
2352 : : {
2353 : 0 : case PRE_INC:
2354 : 0 : offset = (n_refs + 1) * size;
2355 : 0 : break;
2356 : 22038054 : case PRE_DEC:
2357 : 22038054 : offset = -(n_refs + 1) * size;
2358 : 22038054 : break;
2359 : : case POST_INC:
2360 : 617234 : offset = n_refs * size;
2361 : 617234 : break;
2362 : 0 : case POST_DEC:
2363 : 0 : offset = -n_refs * size;
2364 : 0 : break;
2365 : :
2366 : : default:
2367 : : return addr;
2368 : : }
2369 : :
2370 : 22655288 : addr = plus_constant (GET_MODE (addr), XEXP (addr, 0), offset);
2371 : 22655288 : addr = canon_rtx (addr);
2372 : :
2373 : 22655288 : return addr;
2374 : : }
2375 : :
2376 : : /* Return TRUE if an object X sized at XSIZE bytes and another object
2377 : : Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2378 : : any of the sizes is zero, assume an overlap, otherwise use the
2379 : : absolute value of the sizes as the actual sizes. */
2380 : :
2381 : : static inline bool
2382 : 788284894 : offset_overlap_p (poly_int64 c, poly_int64 xsize, poly_int64 ysize)
2383 : : {
2384 : 787992617 : if (known_eq (xsize, 0) || known_eq (ysize, 0))
2385 : : return true;
2386 : :
2387 : 787885695 : if (maybe_ge (c, 0))
2388 : 473491360 : return maybe_gt (maybe_lt (xsize, 0) ? -xsize : xsize, c);
2389 : : else
2390 : 314394335 : return maybe_gt (maybe_lt (ysize, 0) ? -ysize : ysize, -c);
2391 : : }
2392 : :
2393 : : /* Return one if X and Y (memory addresses) reference the
2394 : : same location in memory or if the references overlap.
2395 : : Return zero if they do not overlap, else return
2396 : : minus one in which case they still might reference the same location.
2397 : :
2398 : : C is an offset accumulator. When
2399 : : C is nonzero, we are testing aliases between X and Y + C.
2400 : : XSIZE is the size in bytes of the X reference,
2401 : : similarly YSIZE is the size in bytes for Y.
2402 : : Expect that canon_rtx has been already called for X and Y.
2403 : :
2404 : : If XSIZE or YSIZE is zero, we do not know the amount of memory being
2405 : : referenced (the reference was BLKmode), so make the most pessimistic
2406 : : assumptions.
2407 : :
2408 : : If XSIZE or YSIZE is negative, we may access memory outside the object
2409 : : being referenced as a side effect. This can happen when using AND to
2410 : : align memory references, as is done on the Alpha.
2411 : :
2412 : : Nice to notice that varying addresses cannot conflict with fp if no
2413 : : local variables had their addresses taken, but that's too hard now.
2414 : :
2415 : : ??? Contrary to the tree alias oracle this does not return
2416 : : one for X + non-constant and Y + non-constant when X and Y are equal.
2417 : : If that is fixed the TBAA hack for union type-punning can be removed. */
2418 : :
2419 : : static int
2420 : 1770684491 : memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
2421 : : poly_int64 c)
2422 : : {
2423 : 2577209602 : if (GET_CODE (x) == VALUE)
2424 : : {
2425 : 723978000 : if (REG_P (y))
2426 : : {
2427 : 267027527 : struct elt_loc_list *l = NULL;
2428 : 267027527 : if (CSELIB_VAL_PTR (x))
2429 : 267027527 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs;
2430 : 500046932 : l; l = l->next)
2431 : 358413290 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y))
2432 : : break;
2433 : 267027527 : if (l)
2434 : : x = y;
2435 : : else
2436 : 141633642 : x = get_addr (x);
2437 : : }
2438 : : /* Don't call get_addr if y is the same VALUE. */
2439 : 456950473 : else if (x != y)
2440 : 456883130 : x = get_addr (x);
2441 : : }
2442 : 2577209602 : if (GET_CODE (y) == VALUE)
2443 : : {
2444 : 424737448 : if (REG_P (x))
2445 : : {
2446 : 12953819 : struct elt_loc_list *l = NULL;
2447 : 12953819 : if (CSELIB_VAL_PTR (y))
2448 : 12953819 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs;
2449 : 14814499 : l; l = l->next)
2450 : 1874269 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x))
2451 : : break;
2452 : 12953819 : if (l)
2453 : : y = x;
2454 : : else
2455 : 12940230 : y = get_addr (y);
2456 : : }
2457 : : /* Don't call get_addr if x is the same VALUE. */
2458 : 411783629 : else if (y != x)
2459 : 411716286 : y = get_addr (y);
2460 : : }
2461 : 2577209602 : if (GET_CODE (x) == HIGH)
2462 : 0 : x = XEXP (x, 0);
2463 : 2577209602 : else if (GET_CODE (x) == LO_SUM)
2464 : 0 : x = XEXP (x, 1);
2465 : : else
2466 : 2577209602 : x = addr_side_effect_eval (x, maybe_lt (xsize, 0) ? -xsize : xsize, 0);
2467 : 2577209602 : if (GET_CODE (y) == HIGH)
2468 : 0 : y = XEXP (y, 0);
2469 : 2577209602 : else if (GET_CODE (y) == LO_SUM)
2470 : 0 : y = XEXP (y, 1);
2471 : : else
2472 : 2577209602 : y = addr_side_effect_eval (y, maybe_lt (ysize, 0) ? -ysize : ysize, 0);
2473 : :
2474 : 2577209602 : if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
2475 : : {
2476 : 492659 : HOST_WIDE_INT distance = 0;
2477 : 492659 : int cmp = compare_base_symbol_refs (x, y, &distance);
2478 : :
2479 : : /* If both decls are the same, decide by offsets. */
2480 : 492659 : if (cmp == 1)
2481 : 708853 : return offset_overlap_p (c + distance, xsize, ysize);
2482 : : /* Assume a potential overlap for symbolic addresses that went
2483 : : through alignment adjustments (i.e., that have negative
2484 : : sizes), because we can't know how far they are from each
2485 : : other. */
2486 : 138124 : if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
2487 : : return -1;
2488 : : /* If decls are different or we know by offsets that there is no overlap,
2489 : : we win. */
2490 : 630783 : if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
2491 : 138124 : return 0;
2492 : : /* Decls may or may not be different and offsets overlap....*/
2493 : : return -1;
2494 : : }
2495 : 2576716943 : else if (rtx_equal_for_memref_p (x, y))
2496 : : {
2497 : 273228550 : return offset_overlap_p (c, xsize, ysize);
2498 : : }
2499 : :
2500 : : /* This code used to check for conflicts involving stack references and
2501 : : globals but the base address alias code now handles these cases. */
2502 : :
2503 : 2440080386 : if (GET_CODE (x) == PLUS)
2504 : : {
2505 : : /* The fact that X is canonicalized means that this
2506 : : PLUS rtx is canonicalized. */
2507 : 1459219073 : rtx x0 = XEXP (x, 0);
2508 : 1459219073 : rtx x1 = XEXP (x, 1);
2509 : :
2510 : : /* However, VALUEs might end up in different positions even in
2511 : : canonical PLUSes. Comparing their addresses is enough. */
2512 : 1459219073 : if (x0 == y)
2513 : 21515492 : return memrefs_conflict_p (xsize, x1, ysize, const0_rtx, c);
2514 : 1437703581 : else if (x1 == y)
2515 : 275068 : return memrefs_conflict_p (xsize, x0, ysize, const0_rtx, c);
2516 : :
2517 : 1437428513 : poly_int64 cx1, cy1;
2518 : 1437428513 : if (GET_CODE (y) == PLUS)
2519 : : {
2520 : : /* The fact that Y is canonicalized means that this
2521 : : PLUS rtx is canonicalized. */
2522 : 1304743551 : rtx y0 = XEXP (y, 0);
2523 : 1304743551 : rtx y1 = XEXP (y, 1);
2524 : :
2525 : 1304743551 : if (x0 == y1)
2526 : : return memrefs_conflict_p (xsize, x1, ysize, y0, c);
2527 : 1304701361 : if (x1 == y0)
2528 : : return memrefs_conflict_p (xsize, x0, ysize, y1, c);
2529 : :
2530 : 1304650654 : if (rtx_equal_for_memref_p (x1, y1))
2531 : : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2532 : 1168059361 : if (rtx_equal_for_memref_p (x0, y0))
2533 : : return memrefs_conflict_p (xsize, x1, ysize, y1, c);
2534 : 544424499 : if (poly_int_rtx_p (x1, &cx1))
2535 : : {
2536 : 1049670421 : if (poly_int_rtx_p (y1, &cy1))
2537 : 521139404 : return memrefs_conflict_p (xsize, x0, ysize, y0,
2538 : 521139404 : c - cx1 + cy1);
2539 : : else
2540 : 7391613 : return memrefs_conflict_p (xsize, x0, ysize, y, c - cx1);
2541 : : }
2542 : 15893482 : else if (poly_int_rtx_p (y1, &cy1))
2543 : 13115450 : return memrefs_conflict_p (xsize, x, ysize, y0, c + cy1);
2544 : :
2545 : : return -1;
2546 : : }
2547 : 132684962 : else if (poly_int_rtx_p (x1, &cx1))
2548 : 106261003 : return memrefs_conflict_p (xsize, x0, ysize, y, c - cx1);
2549 : : }
2550 : 980861313 : else if (GET_CODE (y) == PLUS)
2551 : : {
2552 : : /* The fact that Y is canonicalized means that this
2553 : : PLUS rtx is canonicalized. */
2554 : 77779529 : rtx y0 = XEXP (y, 0);
2555 : 77779529 : rtx y1 = XEXP (y, 1);
2556 : :
2557 : 77779529 : if (x == y0)
2558 : 7654076 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y1, c);
2559 : 70125453 : if (x == y1)
2560 : 666210 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y0, c);
2561 : :
2562 : 69459243 : poly_int64 cy1;
2563 : 69459243 : if (poly_int_rtx_p (y1, &cy1))
2564 : 54942279 : return memrefs_conflict_p (xsize, x, ysize, y0, c + cy1);
2565 : : else
2566 : : return -1;
2567 : : }
2568 : :
2569 : 929505743 : if (GET_CODE (x) == GET_CODE (y))
2570 : 753219199 : switch (GET_CODE (x))
2571 : : {
2572 : 260884 : case MULT:
2573 : 260884 : {
2574 : : /* Handle cases where we expect the second operands to be the
2575 : : same, and check only whether the first operand would conflict
2576 : : or not. */
2577 : 260884 : rtx x0, y0;
2578 : 260884 : rtx x1 = canon_rtx (XEXP (x, 1));
2579 : 260884 : rtx y1 = canon_rtx (XEXP (y, 1));
2580 : 260884 : if (! rtx_equal_for_memref_p (x1, y1))
2581 : : return -1;
2582 : 245494 : x0 = canon_rtx (XEXP (x, 0));
2583 : 245494 : y0 = canon_rtx (XEXP (y, 0));
2584 : 245494 : if (rtx_equal_for_memref_p (x0, y0))
2585 : 0 : return offset_overlap_p (c, xsize, ysize);
2586 : :
2587 : : /* Can't properly adjust our sizes. */
2588 : 245494 : poly_int64 c1;
2589 : 279803703 : if (!poly_int_rtx_p (x1, &c1)
2590 : 244878 : || !can_div_trunc_p (xsize, c1, &xsize)
2591 : 244878 : || !can_div_trunc_p (ysize, c1, &ysize)
2592 : 244878 : || !can_div_trunc_p (c, c1, &c))
2593 : : return -1;
2594 : 244878 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2595 : : }
2596 : :
2597 : : default:
2598 : : break;
2599 : : }
2600 : :
2601 : : /* Deal with alignment ANDs by adjusting offset and size so as to
2602 : : cover the maximum range, without taking any previously known
2603 : : alignment into account. Make a size negative after such an
2604 : : adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2605 : : assume a potential overlap, because they may end up in contiguous
2606 : : memory locations and the stricter-alignment access may span over
2607 : : part of both. */
2608 : 929244859 : if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2609 : : {
2610 : 4349904 : HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
2611 : 4349904 : unsigned HOST_WIDE_INT uc = sc;
2612 : 4349904 : if (sc < 0 && pow2_or_zerop (-uc))
2613 : : {
2614 : 4349480 : if (maybe_gt (xsize, 0))
2615 : 4348590 : xsize = -xsize;
2616 : 4349480 : if (maybe_ne (xsize, 0))
2617 : 4348634 : xsize += sc + 1;
2618 : 4349480 : c -= sc + 1;
2619 : 4349480 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2620 : 4349480 : ysize, y, c);
2621 : : }
2622 : : }
2623 : 924895379 : if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2624 : : {
2625 : 7076222 : HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
2626 : 7076222 : unsigned HOST_WIDE_INT uc = sc;
2627 : 7076222 : if (sc < 0 && pow2_or_zerop (-uc))
2628 : : {
2629 : 7073100 : if (maybe_gt (ysize, 0))
2630 : 7072950 : ysize = -ysize;
2631 : 7073100 : if (maybe_ne (ysize, 0))
2632 : 7073063 : ysize += sc + 1;
2633 : 7073100 : c += sc + 1;
2634 : 7073100 : return memrefs_conflict_p (xsize, x,
2635 : 7073100 : ysize, canon_rtx (XEXP (y, 0)), c);
2636 : : }
2637 : : }
2638 : :
2639 : 917822279 : if (CONSTANT_P (x))
2640 : : {
2641 : 663930613 : poly_int64 cx, cy;
2642 : 663930613 : if (poly_int_rtx_p (x, &cx) && poly_int_rtx_p (y, &cy))
2643 : : {
2644 : 651137436 : c += cy - cx;
2645 : 1302027159 : return offset_overlap_p (c, xsize, ysize);
2646 : : }
2647 : :
2648 : 12793177 : if (GET_CODE (x) == CONST)
2649 : : {
2650 : 3738212 : if (GET_CODE (y) == CONST)
2651 : 2851022 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2652 : 2851022 : ysize, canon_rtx (XEXP (y, 0)), c);
2653 : : else
2654 : 887190 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2655 : 887190 : ysize, y, c);
2656 : : }
2657 : 9054965 : if (GET_CODE (y) == CONST)
2658 : 689543 : return memrefs_conflict_p (xsize, x, ysize,
2659 : 689543 : canon_rtx (XEXP (y, 0)), c);
2660 : :
2661 : : /* Assume a potential overlap for symbolic addresses that went
2662 : : through alignment adjustments (i.e., that have negative
2663 : : sizes), because we can't know how far they are from each
2664 : : other. */
2665 : 8365422 : if (CONSTANT_P (y))
2666 : 9265 : return (maybe_lt (xsize, 0)
2667 : 9265 : || maybe_lt (ysize, 0)
2668 : 18530 : || offset_overlap_p (c, xsize, ysize));
2669 : :
2670 : : return -1;
2671 : : }
2672 : :
2673 : : return -1;
2674 : : }
2675 : :
2676 : : /* Functions to compute memory dependencies.
2677 : :
2678 : : Since we process the insns in execution order, we can build tables
2679 : : to keep track of what registers are fixed (and not aliased), what registers
2680 : : are varying in known ways, and what registers are varying in unknown
2681 : : ways.
2682 : :
2683 : : If both memory references are volatile, then there must always be a
2684 : : dependence between the two references, since their order cannot be
2685 : : changed. A volatile and non-volatile reference can be interchanged
2686 : : though.
2687 : :
2688 : : We also must allow AND addresses, because they may generate accesses
2689 : : outside the object being referenced. This is used to generate aligned
2690 : : addresses from unaligned addresses, for instance, the alpha
2691 : : storeqi_unaligned pattern. */
2692 : :
2693 : : /* Read dependence: X is read after read in MEM takes place. There can
2694 : : only be a dependence here if both reads are volatile, or if either is
2695 : : an explicit barrier. */
2696 : :
2697 : : bool
2698 : 28879689 : read_dependence (const_rtx mem, const_rtx x)
2699 : : {
2700 : 28879689 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2701 : : return true;
2702 : 28430194 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2703 : 56852221 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2704 : 12343 : return true;
2705 : : return false;
2706 : : }
2707 : :
2708 : : /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2709 : :
2710 : : static tree
2711 : 63979320 : decl_for_component_ref (tree x)
2712 : : {
2713 : 87086898 : do
2714 : : {
2715 : 87086898 : x = TREE_OPERAND (x, 0);
2716 : : }
2717 : 87086898 : while (x && TREE_CODE (x) == COMPONENT_REF);
2718 : :
2719 : 63979320 : return x && DECL_P (x) ? x : NULL_TREE;
2720 : : }
2721 : :
2722 : : /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2723 : : for the offset of the field reference. *KNOWN_P says whether the
2724 : : offset is known. */
2725 : :
2726 : : static void
2727 : 11719494 : adjust_offset_for_component_ref (tree x, bool *known_p,
2728 : : poly_int64 *offset)
2729 : : {
2730 : 11719494 : if (!*known_p)
2731 : : return;
2732 : 15417807 : do
2733 : : {
2734 : 15417807 : tree xoffset = component_ref_field_offset (x);
2735 : 15417807 : tree field = TREE_OPERAND (x, 1);
2736 : 15417807 : if (!poly_int_tree_p (xoffset))
2737 : : {
2738 : 0 : *known_p = false;
2739 : 0 : return;
2740 : : }
2741 : :
2742 : 15417807 : poly_offset_int woffset
2743 : 15417807 : = (wi::to_poly_offset (xoffset)
2744 : 15417807 : + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field))
2745 : 30835614 : >> LOG2_BITS_PER_UNIT)
2746 : 15417807 : + *offset);
2747 : 15417807 : if (!woffset.to_shwi (offset))
2748 : : {
2749 : 0 : *known_p = false;
2750 : 0 : return;
2751 : : }
2752 : :
2753 : 15417807 : x = TREE_OPERAND (x, 0);
2754 : : }
2755 : 15417807 : while (x && TREE_CODE (x) == COMPONENT_REF);
2756 : : }
2757 : :
2758 : : /* Return true if we can determine the exprs corresponding to memrefs
2759 : : X and Y and they do not overlap.
2760 : : If LOOP_VARIANT is set, skip offset-based disambiguation */
2761 : :
2762 : : bool
2763 : 222994309 : nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2764 : : {
2765 : 231565805 : tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2766 : 222994309 : rtx rtlx, rtly;
2767 : 222994309 : rtx basex, basey;
2768 : 222994309 : bool moffsetx_known_p, moffsety_known_p;
2769 : 222994309 : poly_int64 moffsetx = 0, moffsety = 0;
2770 : 222994309 : poly_int64 offsetx = 0, offsety = 0, sizex, sizey;
2771 : :
2772 : : /* Unless both have exprs, we can't tell anything. */
2773 : 222994309 : if (exprx == 0 || expry == 0)
2774 : : return false;
2775 : :
2776 : : /* For spill-slot accesses make sure we have valid offsets. */
2777 : 194104641 : if ((exprx == get_spill_slot_decl (false)
2778 : 14213299 : && ! MEM_OFFSET_KNOWN_P (x))
2779 : 208317940 : || (expry == get_spill_slot_decl (false)
2780 : 24464075 : && ! MEM_OFFSET_KNOWN_P (y)))
2781 : 0 : return false;
2782 : :
2783 : : /* If the field reference test failed, look at the DECLs involved. */
2784 : 194104641 : moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2785 : 194104641 : if (moffsetx_known_p)
2786 : 193746721 : moffsetx = MEM_OFFSET (x);
2787 : 194104641 : if (TREE_CODE (exprx) == COMPONENT_REF)
2788 : : {
2789 : 37494028 : tree t = decl_for_component_ref (exprx);
2790 : 37494028 : if (! t)
2791 : : return false;
2792 : 4825656 : adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx);
2793 : 4825656 : exprx = t;
2794 : : }
2795 : :
2796 : 161436269 : moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2797 : 161436269 : if (moffsety_known_p)
2798 : 160270166 : moffsety = MEM_OFFSET (y);
2799 : 161436269 : if (TREE_CODE (expry) == COMPONENT_REF)
2800 : : {
2801 : 26485292 : tree t = decl_for_component_ref (expry);
2802 : 26485292 : if (! t)
2803 : : return false;
2804 : 6893838 : adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety);
2805 : 6893838 : expry = t;
2806 : : }
2807 : :
2808 : 141844815 : if (! DECL_P (exprx) || ! DECL_P (expry))
2809 : : return false;
2810 : :
2811 : : /* If we refer to different gimple registers, or one gimple register
2812 : : and one non-gimple-register, we know they can't overlap. First,
2813 : : gimple registers don't have their addresses taken. Now, there
2814 : : could be more than one stack slot for (different versions of) the
2815 : : same gimple register, but we can presumably tell they don't
2816 : : overlap based on offsets from stack base addresses elsewhere.
2817 : : It's important that we don't proceed to DECL_RTL, because gimple
2818 : : registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2819 : : able to do anything about them since no SSA information will have
2820 : : remained to guide it. */
2821 : 12767062 : if (is_gimple_reg (exprx) || is_gimple_reg (expry))
2822 : 3586018 : return exprx != expry
2823 : 3586018 : || (moffsetx_known_p && moffsety_known_p
2824 : 294202 : && MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y)
2825 : 294202 : && !offset_overlap_p (moffsety - moffsetx,
2826 : 147101 : MEM_SIZE (x), MEM_SIZE (y)));
2827 : :
2828 : : /* With invalid code we can end up storing into the constant pool.
2829 : : Bail out to avoid ICEing when creating RTL for this.
2830 : : See gfortran.dg/lto/20091028-2_0.f90. */
2831 : 9181044 : if (TREE_CODE (exprx) == CONST_DECL
2832 : 9181044 : || TREE_CODE (expry) == CONST_DECL)
2833 : : return true;
2834 : :
2835 : : /* If one decl is known to be a function or label in a function and
2836 : : the other is some kind of data, they can't overlap. */
2837 : 9181044 : if ((TREE_CODE (exprx) == FUNCTION_DECL
2838 : 9181044 : || TREE_CODE (exprx) == LABEL_DECL)
2839 : : != (TREE_CODE (expry) == FUNCTION_DECL
2840 : 9181044 : || TREE_CODE (expry) == LABEL_DECL))
2841 : : return true;
2842 : :
2843 : : /* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2844 : : living in multiple places), we can't tell anything. Exception
2845 : : are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2846 : 9008849 : if ((!DECL_RTL_SET_P (exprx) && TREE_CODE (exprx) != FUNCTION_DECL)
2847 : 18017698 : || (!DECL_RTL_SET_P (expry) && TREE_CODE (expry) != FUNCTION_DECL))
2848 : : return false;
2849 : :
2850 : 9008849 : rtlx = DECL_RTL (exprx);
2851 : 9008849 : rtly = DECL_RTL (expry);
2852 : :
2853 : : /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2854 : : can't overlap unless they are the same because we never reuse that part
2855 : : of the stack frame used for locals for spilled pseudos. */
2856 : 9008254 : if ((!MEM_P (rtlx) || !MEM_P (rtly))
2857 : 9033999 : && ! rtx_equal_p (rtlx, rtly))
2858 : : return true;
2859 : :
2860 : : /* If we have MEMs referring to different address spaces (which can
2861 : : potentially overlap), we cannot easily tell from the addresses
2862 : : whether the references overlap. */
2863 : 8983104 : if (MEM_P (rtlx) && MEM_P (rtly)
2864 : 17966298 : && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2865 : : return false;
2866 : :
2867 : : /* Get the base and offsets of both decls. If either is a register, we
2868 : : know both are and are the same, so use that as the base. The only
2869 : : we can avoid overlap is if we can deduce that they are nonoverlapping
2870 : : pieces of that decl, which is very rare. */
2871 : 8983194 : basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2872 : 8983194 : basex = strip_offset_and_add (basex, &offsetx);
2873 : :
2874 : 8983194 : basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2875 : 8983194 : basey = strip_offset_and_add (basey, &offsety);
2876 : :
2877 : : /* If the bases are different, we know they do not overlap if both
2878 : : are constants or if one is a constant and the other a pointer into the
2879 : : stack frame. Otherwise a different base means we can't tell if they
2880 : : overlap or not. */
2881 : 8983194 : if (compare_base_decls (exprx, expry) == 0)
2882 : 7038760 : return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2883 : 1860650 : || (CONSTANT_P (basex) && REG_P (basey)
2884 : 273502 : && REGNO_PTR_FRAME_P (REGNO (basey)))
2885 : 10215284 : || (CONSTANT_P (basey) && REG_P (basex)
2886 : 110430 : && REGNO_PTR_FRAME_P (REGNO (basex))));
2887 : :
2888 : : /* Offset based disambiguation not appropriate for loop invariant */
2889 : 357286 : if (loop_invariant)
2890 : : return false;
2891 : :
2892 : : /* Offset based disambiguation is OK even if we do not know that the
2893 : : declarations are necessarily different
2894 : : (i.e. compare_base_decls (exprx, expry) == -1) */
2895 : :
2896 : 357376 : sizex = (!MEM_P (rtlx) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx)))
2897 : 357196 : : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2898 : : : -1);
2899 : 357376 : sizey = (!MEM_P (rtly) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly)))
2900 : 357196 : : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2901 : : : -1);
2902 : :
2903 : : /* If we have an offset for either memref, it can update the values computed
2904 : : above. */
2905 : 357286 : if (moffsetx_known_p)
2906 : 357280 : offsetx += moffsetx, sizex -= moffsetx;
2907 : 357286 : if (moffsety_known_p)
2908 : 357270 : offsety += moffsety, sizey -= moffsety;
2909 : :
2910 : : /* If a memref has both a size and an offset, we can use the smaller size.
2911 : : We can't do this if the offset isn't known because we must view this
2912 : : memref as being anywhere inside the DECL's MEM. */
2913 : 357286 : if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2914 : 357280 : sizex = MEM_SIZE (x);
2915 : 357286 : if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2916 : 357270 : sizey = MEM_SIZE (y);
2917 : :
2918 : 357286 : return !ranges_maybe_overlap_p (offsetx, sizex, offsety, sizey);
2919 : : }
2920 : :
2921 : : /* Helper for true_dependence and canon_true_dependence.
2922 : : Checks for true dependence: X is read after store in MEM takes place.
2923 : :
2924 : : If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2925 : : NULL_RTX, and the canonical addresses of MEM and X are both computed
2926 : : here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2927 : :
2928 : : If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2929 : :
2930 : : Returns true if there is a true dependence, false otherwise. */
2931 : :
2932 : : static bool
2933 : 807671649 : true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
2934 : : const_rtx x, rtx x_addr, bool mem_canonicalized)
2935 : : {
2936 : 807671649 : rtx true_mem_addr;
2937 : 807671649 : rtx base;
2938 : 807671649 : int ret;
2939 : :
2940 : 807671649 : gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2941 : : : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2942 : :
2943 : 807671649 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2944 : : return true;
2945 : :
2946 : : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2947 : : This is used in epilogue deallocation functions, and in cselib. */
2948 : 807024652 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2949 : : return true;
2950 : 807002279 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2951 : : return true;
2952 : 803026499 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2953 : 1606030096 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2954 : : return true;
2955 : :
2956 : 801552350 : if (! x_addr)
2957 : 47382047 : x_addr = XEXP (x, 0);
2958 : 801552350 : x_addr = get_addr (x_addr);
2959 : :
2960 : 801552350 : if (! mem_addr)
2961 : : {
2962 : 38766615 : mem_addr = XEXP (mem, 0);
2963 : 38766615 : if (mem_mode == VOIDmode)
2964 : 19708779 : mem_mode = GET_MODE (mem);
2965 : : }
2966 : 801552350 : true_mem_addr = get_addr (mem_addr);
2967 : :
2968 : : /* Read-only memory is by definition never modified, and therefore can't
2969 : : conflict with anything. However, don't assume anything when AND
2970 : : addresses are involved and leave to the code below to determine
2971 : : dependence. We don't expect to find read-only set on MEM, but
2972 : : stupid user tricks can produce them, so don't die. */
2973 : 801552350 : if (MEM_READONLY_P (x)
2974 : 3960819 : && GET_CODE (x_addr) != AND
2975 : 805513169 : && GET_CODE (true_mem_addr) != AND)
2976 : : return false;
2977 : :
2978 : : /* If we have MEMs referring to different address spaces (which can
2979 : : potentially overlap), we cannot easily tell from the addresses
2980 : : whether the references overlap. */
2981 : 831944157 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
2982 : : return true;
2983 : :
2984 : 797519140 : base = find_base_term (x_addr);
2985 : 797519140 : if (base && (GET_CODE (base) == LABEL_REF
2986 : 692701411 : || (GET_CODE (base) == SYMBOL_REF
2987 : 57592445 : && CONSTANT_POOL_ADDRESS_P (base))))
2988 : : return false;
2989 : :
2990 : 797518248 : rtx mem_base = find_base_term (true_mem_addr);
2991 : 797518248 : if (! base_alias_check (x_addr, base, true_mem_addr, mem_base,
2992 : 797518248 : GET_MODE (x), mem_mode))
2993 : : return false;
2994 : :
2995 : 721947743 : x_addr = canon_rtx (x_addr);
2996 : 721947743 : if (!mem_canonicalized)
2997 : 27554784 : mem_addr = canon_rtx (true_mem_addr);
2998 : :
2999 : 1443895486 : if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
3000 : 1443895486 : SIZE_FOR_MODE (x), x_addr, 0)) != -1)
3001 : 504897046 : return !!ret;
3002 : :
3003 : 217050697 : if (mems_in_disjoint_alias_sets_p (x, mem))
3004 : : return false;
3005 : :
3006 : 160486181 : if (nonoverlapping_memrefs_p (mem, x, false))
3007 : : return false;
3008 : :
3009 : 152450026 : return rtx_refs_may_alias_p (x, mem, true);
3010 : : }
3011 : :
3012 : : /* True dependence: X is read after store in MEM takes place. */
3013 : :
3014 : : bool
3015 : 41632840 : true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x)
3016 : : {
3017 : 41632840 : return true_dependence_1 (mem, mem_mode, NULL_RTX,
3018 : 41632840 : x, NULL_RTX, /*mem_canonicalized=*/false);
3019 : : }
3020 : :
3021 : : /* Canonical true dependence: X is read after store in MEM takes place.
3022 : : Variant of true_dependence which assumes MEM has already been
3023 : : canonicalized (hence we no longer do that here).
3024 : : The mem_addr argument has been added, since true_dependence_1 computed
3025 : : this value prior to canonicalizing. */
3026 : :
3027 : : bool
3028 : 766038809 : canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
3029 : : const_rtx x, rtx x_addr)
3030 : : {
3031 : 766038809 : return true_dependence_1 (mem, mem_mode, mem_addr,
3032 : 766038809 : x, x_addr, /*mem_canonicalized=*/true);
3033 : : }
3034 : :
3035 : : /* Returns true if a write to X might alias a previous read from
3036 : : (or, if WRITEP is true, a write to) MEM.
3037 : : If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3038 : : and X_MODE the mode for that access.
3039 : : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3040 : :
3041 : : static bool
3042 : 436796056 : write_dependence_p (const_rtx mem,
3043 : : const_rtx x, machine_mode x_mode, rtx x_addr,
3044 : : bool mem_canonicalized, bool x_canonicalized, bool writep)
3045 : : {
3046 : 436796056 : rtx mem_addr;
3047 : 436796056 : rtx true_mem_addr, true_x_addr;
3048 : 436796056 : rtx base;
3049 : 436796056 : int ret;
3050 : :
3051 : 436796056 : gcc_checking_assert (x_canonicalized
3052 : : ? (x_addr != NULL_RTX
3053 : : && (x_mode != VOIDmode || GET_MODE (x) == VOIDmode))
3054 : : : (x_addr == NULL_RTX && x_mode == VOIDmode));
3055 : :
3056 : 436796056 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3057 : : return true;
3058 : :
3059 : : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3060 : : This is used in epilogue deallocation functions. */
3061 : 436262178 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3062 : : return true;
3063 : 411831782 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3064 : : return true;
3065 : 410845664 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3066 : 821495532 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3067 : : return true;
3068 : :
3069 : 410633901 : if (!x_addr)
3070 : 47704286 : x_addr = XEXP (x, 0);
3071 : 410633901 : true_x_addr = get_addr (x_addr);
3072 : :
3073 : 410633901 : mem_addr = XEXP (mem, 0);
3074 : 410633901 : true_mem_addr = get_addr (mem_addr);
3075 : :
3076 : : /* A read from read-only memory can't conflict with read-write memory.
3077 : : Don't assume anything when AND addresses are involved and leave to
3078 : : the code below to determine dependence. */
3079 : 410633901 : if (!writep
3080 : 380113413 : && MEM_READONLY_P (mem)
3081 : 10602057 : && GET_CODE (true_x_addr) != AND
3082 : 421235958 : && GET_CODE (true_mem_addr) != AND)
3083 : : return false;
3084 : :
3085 : : /* If we have MEMs referring to different address spaces (which can
3086 : : potentially overlap), we cannot easily tell from the addresses
3087 : : whether the references overlap. */
3088 : 412751050 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3089 : : return true;
3090 : :
3091 : 399998938 : base = find_base_term (true_mem_addr);
3092 : 399998938 : if (! writep
3093 : 399998938 : && base
3094 : 399998938 : && (GET_CODE (base) == LABEL_REF
3095 : 315812737 : || (GET_CODE (base) == SYMBOL_REF
3096 : 27948938 : && CONSTANT_POOL_ADDRESS_P (base))))
3097 : : return false;
3098 : :
3099 : 399998180 : rtx x_base = find_base_term (true_x_addr);
3100 : 399998180 : if (! base_alias_check (true_x_addr, x_base, true_mem_addr, base,
3101 : 399998180 : GET_MODE (x), GET_MODE (mem)))
3102 : : return false;
3103 : :
3104 : 345886999 : if (!x_canonicalized)
3105 : : {
3106 : 42541478 : x_addr = canon_rtx (true_x_addr);
3107 : 42541478 : x_mode = GET_MODE (x);
3108 : : }
3109 : 345886999 : if (!mem_canonicalized)
3110 : 204463847 : mem_addr = canon_rtx (true_mem_addr);
3111 : :
3112 : 691773998 : if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
3113 : 691773998 : GET_MODE_SIZE (x_mode), x_addr, 0)) != -1)
3114 : 283378871 : return !!ret;
3115 : :
3116 : 62508128 : if (nonoverlapping_memrefs_p (x, mem, false))
3117 : : return false;
3118 : :
3119 : 59363654 : return rtx_refs_may_alias_p (x, mem, false);
3120 : : }
3121 : :
3122 : : /* Anti dependence: X is written after read in MEM takes place. */
3123 : :
3124 : : bool
3125 : 21137184 : anti_dependence (const_rtx mem, const_rtx x)
3126 : : {
3127 : 21137184 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3128 : : /*mem_canonicalized=*/false,
3129 : 21137184 : /*x_canonicalized*/false, /*writep=*/false);
3130 : : }
3131 : :
3132 : : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3133 : : Also, consider X in X_MODE (which might be from an enclosing
3134 : : STRICT_LOW_PART / ZERO_EXTRACT).
3135 : : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3136 : :
3137 : : bool
3138 : 382847616 : canon_anti_dependence (const_rtx mem, bool mem_canonicalized,
3139 : : const_rtx x, machine_mode x_mode, rtx x_addr)
3140 : : {
3141 : 382847616 : return write_dependence_p (mem, x, x_mode, x_addr,
3142 : : mem_canonicalized, /*x_canonicalized=*/true,
3143 : 382847616 : /*writep=*/false);
3144 : : }
3145 : :
3146 : : /* Output dependence: X is written after store in MEM takes place. */
3147 : :
3148 : : bool
3149 : 29625609 : output_dependence (const_rtx mem, const_rtx x)
3150 : : {
3151 : 29625609 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3152 : : /*mem_canonicalized=*/false,
3153 : 29625609 : /*x_canonicalized*/false, /*writep=*/true);
3154 : : }
3155 : :
3156 : : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3157 : : Also, consider X in X_MODE (which might be from an enclosing
3158 : : STRICT_LOW_PART / ZERO_EXTRACT).
3159 : : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3160 : :
3161 : : bool
3162 : 3185647 : canon_output_dependence (const_rtx mem, bool mem_canonicalized,
3163 : : const_rtx x, machine_mode x_mode, rtx x_addr)
3164 : : {
3165 : 3185647 : return write_dependence_p (mem, x, x_mode, x_addr,
3166 : : mem_canonicalized, /*x_canonicalized=*/true,
3167 : 3185647 : /*writep=*/true);
3168 : : }
3169 : :
3170 : :
3171 : :
3172 : : /* Check whether X may be aliased with MEM. Don't do offset-based
3173 : : memory disambiguation & TBAA. */
3174 : : bool
3175 : 0 : may_alias_p (const_rtx mem, const_rtx x)
3176 : : {
3177 : 0 : rtx x_addr, mem_addr;
3178 : :
3179 : 0 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3180 : : return true;
3181 : :
3182 : : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3183 : : This is used in epilogue deallocation functions. */
3184 : 0 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3185 : : return true;
3186 : 0 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3187 : : return true;
3188 : 0 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3189 : 0 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3190 : : return true;
3191 : :
3192 : 0 : x_addr = XEXP (x, 0);
3193 : 0 : x_addr = get_addr (x_addr);
3194 : :
3195 : 0 : mem_addr = XEXP (mem, 0);
3196 : 0 : mem_addr = get_addr (mem_addr);
3197 : :
3198 : : /* Read-only memory is by definition never modified, and therefore can't
3199 : : conflict with anything. However, don't assume anything when AND
3200 : : addresses are involved and leave to the code below to determine
3201 : : dependence. We don't expect to find read-only set on MEM, but
3202 : : stupid user tricks can produce them, so don't die. */
3203 : 0 : if (MEM_READONLY_P (x)
3204 : 0 : && GET_CODE (x_addr) != AND
3205 : 0 : && GET_CODE (mem_addr) != AND)
3206 : : return false;
3207 : :
3208 : : /* If we have MEMs referring to different address spaces (which can
3209 : : potentially overlap), we cannot easily tell from the addresses
3210 : : whether the references overlap. */
3211 : 0 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3212 : : return true;
3213 : :
3214 : 0 : rtx x_base = find_base_term (x_addr);
3215 : 0 : rtx mem_base = find_base_term (mem_addr);
3216 : 0 : if (! base_alias_check (x_addr, x_base, mem_addr, mem_base,
3217 : 0 : GET_MODE (x), GET_MODE (mem_addr)))
3218 : : return false;
3219 : :
3220 : 0 : if (nonoverlapping_memrefs_p (mem, x, true))
3221 : : return false;
3222 : :
3223 : : /* TBAA not valid for loop_invarint */
3224 : 0 : return rtx_refs_may_alias_p (x, mem, false);
3225 : : }
3226 : :
3227 : : void
3228 : 209938 : init_alias_target (void)
3229 : : {
3230 : 209938 : int i;
3231 : :
3232 : 209938 : if (!arg_base_value)
3233 : 206833 : arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
3234 : :
3235 : 209938 : memset (static_reg_base_value, 0, sizeof static_reg_base_value);
3236 : :
3237 : 19524234 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3238 : : /* Check whether this register can hold an incoming pointer
3239 : : argument. FUNCTION_ARG_REGNO_P tests outgoing register
3240 : : numbers, so translate if necessary due to register windows. */
3241 : 19314296 : if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
3242 : 19314296 : && targetm.hard_regno_mode_ok (i, Pmode))
3243 : 3111343 : static_reg_base_value[i] = arg_base_value;
3244 : :
3245 : : /* RTL code is required to be consistent about whether it uses the
3246 : : stack pointer, the frame pointer or the argument pointer to
3247 : : access a given area of the frame. We can therefore use the
3248 : : base address to distinguish between the different areas. */
3249 : 209938 : static_reg_base_value[STACK_POINTER_REGNUM]
3250 : 209938 : = unique_base_value (UNIQUE_BASE_VALUE_SP);
3251 : 209938 : static_reg_base_value[ARG_POINTER_REGNUM]
3252 : 209938 : = unique_base_value (UNIQUE_BASE_VALUE_ARGP);
3253 : 209938 : static_reg_base_value[FRAME_POINTER_REGNUM]
3254 : 209938 : = unique_base_value (UNIQUE_BASE_VALUE_FP);
3255 : :
3256 : : /* The above rules extend post-reload, with eliminations applying
3257 : : consistently to each of the three pointers. Cope with cases in
3258 : : which the frame pointer is eliminated to the hard frame pointer
3259 : : rather than the stack pointer. */
3260 : 209938 : if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3261 : 209938 : static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
3262 : 209938 : = unique_base_value (UNIQUE_BASE_VALUE_HFP);
3263 : 209938 : }
3264 : :
3265 : : /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3266 : : to be memory reference. */
3267 : : static bool memory_modified;
3268 : : static void
3269 : 30119199 : memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3270 : : {
3271 : 30119199 : if (MEM_P (x))
3272 : : {
3273 : 2193952 : if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
3274 : 439424 : memory_modified = true;
3275 : : }
3276 : 30119199 : }
3277 : :
3278 : :
3279 : : /* Return true when INSN possibly modify memory contents of MEM
3280 : : (i.e. address can be modified). */
3281 : : bool
3282 : 38812668 : memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
3283 : : {
3284 : 38812668 : if (!INSN_P (insn))
3285 : : return false;
3286 : : /* Conservatively assume all non-readonly MEMs might be modified in
3287 : : calls. */
3288 : 36505644 : if (CALL_P (insn))
3289 : : return true;
3290 : 36205856 : memory_modified = false;
3291 : 36205856 : note_stores (as_a<const rtx_insn *> (insn), memory_modified_1,
3292 : : CONST_CAST_RTX(mem));
3293 : 36205856 : return memory_modified;
3294 : : }
3295 : :
3296 : : /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3297 : : array. */
3298 : :
3299 : : void
3300 : 8947473 : init_alias_analysis (void)
3301 : : {
3302 : 8947473 : const bool frame_pointer_eliminated
3303 : 8947473 : = reload_completed
3304 : 3881213 : && !frame_pointer_needed
3305 : 12605706 : && targetm.can_eliminate (FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM);
3306 : 8947473 : unsigned int maxreg = max_reg_num ();
3307 : 8947473 : bool changed;
3308 : 8947473 : int pass, i;
3309 : 8947473 : unsigned int ui;
3310 : 8947473 : rtx_insn *insn;
3311 : 8947473 : rtx val;
3312 : 8947473 : int rpo_cnt;
3313 : 8947473 : int *rpo;
3314 : :
3315 : 8947473 : timevar_push (TV_ALIAS_ANALYSIS);
3316 : :
3317 : 8947473 : vec_safe_grow_cleared (reg_known_value, maxreg - FIRST_PSEUDO_REGISTER,
3318 : : true);
3319 : 8947473 : reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
3320 : 8947473 : bitmap_clear (reg_known_equiv_p);
3321 : :
3322 : : /* If we have memory allocated from the previous run, use it. */
3323 : 8947473 : if (old_reg_base_value)
3324 : 8702799 : reg_base_value = old_reg_base_value;
3325 : :
3326 : 8947473 : if (reg_base_value)
3327 : 8740825 : reg_base_value->truncate (0);
3328 : :
3329 : 8947473 : vec_safe_grow_cleared (reg_base_value, maxreg, true);
3330 : :
3331 : 8947473 : new_reg_base_value = XNEWVEC (rtx, maxreg);
3332 : 8947473 : reg_seen = sbitmap_alloc (maxreg);
3333 : :
3334 : : /* The basic idea is that each pass through this loop will use the
3335 : : "constant" information from the previous pass to propagate alias
3336 : : information through another level of assignments.
3337 : :
3338 : : The propagation is done on the CFG in reverse post-order, to propagate
3339 : : things forward as far as possible in each iteration.
3340 : :
3341 : : This could get expensive if the assignment chains are long. Maybe
3342 : : we should throttle the number of iterations, possibly based on
3343 : : the optimization level or flag_expensive_optimizations.
3344 : :
3345 : : We could propagate more information in the first pass by making use
3346 : : of DF_REG_DEF_COUNT to determine immediately that the alias information
3347 : : for a pseudo is "constant".
3348 : :
3349 : : A program with an uninitialized variable can cause an infinite loop
3350 : : here. Instead of doing a full dataflow analysis to detect such problems
3351 : : we just cap the number of iterations for the loop.
3352 : :
3353 : : The state of the arrays for the set chain in question does not matter
3354 : : since the program has undefined behavior. */
3355 : :
3356 : 8947473 : rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3357 : 8947473 : rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
3358 : :
3359 : 8947473 : pass = 0;
3360 : 18150373 : do
3361 : : {
3362 : : /* Assume nothing will change this iteration of the loop. */
3363 : 18150373 : changed = false;
3364 : :
3365 : : /* We want to assign the same IDs each iteration of this loop, so
3366 : : start counting from one each iteration of the loop. */
3367 : 18150373 : unique_id = 1;
3368 : :
3369 : : /* We're at the start of the function each iteration through the
3370 : : loop, so we're copying arguments. */
3371 : 18150373 : copying_arguments = true;
3372 : :
3373 : : /* Wipe the potential alias information clean for this pass. */
3374 : 18150373 : memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
3375 : :
3376 : : /* Wipe the reg_seen array clean. */
3377 : 18150373 : bitmap_clear (reg_seen);
3378 : :
3379 : : /* Initialize the alias information for this pass. */
3380 : 1706135062 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3381 : 1669834316 : if (static_reg_base_value[i]
3382 : : /* Don't treat the hard frame pointer as special if we
3383 : : eliminated the frame pointer to the stack pointer. */
3384 : 330880379 : && !(i == HARD_FRAME_POINTER_REGNUM && frame_pointer_eliminated))
3385 : : {
3386 : 323531096 : new_reg_base_value[i] = static_reg_base_value[i];
3387 : 323531096 : bitmap_set_bit (reg_seen, i);
3388 : : }
3389 : :
3390 : : /* Walk the insns adding values to the new_reg_base_value array. */
3391 : 223538774 : for (i = 0; i < rpo_cnt; i++)
3392 : : {
3393 : 205388401 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
3394 : 2527525006 : FOR_BB_INSNS (bb, insn)
3395 : : {
3396 : 2322136605 : if (NONDEBUG_INSN_P (insn))
3397 : : {
3398 : 1164481621 : rtx note, set;
3399 : :
3400 : : /* Treat the hard frame pointer as special unless we
3401 : : eliminated the frame pointer to the stack pointer. */
3402 : 1164841638 : if (!frame_pointer_eliminated
3403 : 1164481621 : && modified_in_p (hard_frame_pointer_rtx, insn))
3404 : 360017 : continue;
3405 : :
3406 : : /* If this insn has a noalias note, process it, Otherwise,
3407 : : scan for sets. A simple set will have no side effects
3408 : : which could change the base value of any other register. */
3409 : 1164121604 : if (GET_CODE (PATTERN (insn)) == SET
3410 : 928599007 : && REG_NOTES (insn) != 0
3411 : 1652599758 : && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
3412 : 1361974 : record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
3413 : : else
3414 : 1162759630 : note_stores (insn, record_set, NULL);
3415 : :
3416 : 1164121604 : set = single_set (insn);
3417 : :
3418 : 1164121604 : if (set != 0
3419 : 1084297107 : && REG_P (SET_DEST (set))
3420 : 1948946313 : && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3421 : : {
3422 : 295447361 : unsigned int regno = REGNO (SET_DEST (set));
3423 : 295447361 : rtx src = SET_SRC (set);
3424 : 295447361 : rtx t;
3425 : :
3426 : 295447361 : note = find_reg_equal_equiv_note (insn);
3427 : 295447361 : if (note && REG_NOTE_KIND (note) == REG_EQUAL
3428 : 16668200 : && DF_REG_DEF_COUNT (regno) != 1)
3429 : : note = NULL_RTX;
3430 : :
3431 : : poly_int64 offset;
3432 : : if (note != NULL_RTX
3433 : 16547677 : && GET_CODE (XEXP (note, 0)) != EXPR_LIST
3434 : 16547677 : && ! rtx_varies_p (XEXP (note, 0), 1)
3435 : 7260786 : && ! reg_overlap_mentioned_p (SET_DEST (set),
3436 : 7260786 : XEXP (note, 0)))
3437 : : {
3438 : 7260786 : set_reg_known_value (regno, XEXP (note, 0));
3439 : 7260786 : set_reg_known_equiv_p (regno,
3440 : 7260786 : REG_NOTE_KIND (note) == REG_EQUIV);
3441 : : }
3442 : 288186575 : else if (DF_REG_DEF_COUNT (regno) == 1
3443 : 222097024 : && GET_CODE (src) == PLUS
3444 : 40248748 : && REG_P (XEXP (src, 0))
3445 : 39452611 : && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
3446 : 289312540 : && poly_int_rtx_p (XEXP (src, 1), &offset))
3447 : : {
3448 : 760858 : t = plus_constant (GET_MODE (src), t, offset);
3449 : 760858 : set_reg_known_value (regno, t);
3450 : 760858 : set_reg_known_equiv_p (regno, false);
3451 : : }
3452 : 287425717 : else if (DF_REG_DEF_COUNT (regno) == 1
3453 : 287425717 : && ! rtx_varies_p (src, 1))
3454 : : {
3455 : 30079310 : set_reg_known_value (regno, src);
3456 : 30079310 : set_reg_known_equiv_p (regno, false);
3457 : : }
3458 : : }
3459 : : }
3460 : 1157654984 : else if (NOTE_P (insn)
3461 : 279335039 : && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
3462 : 18139567 : copying_arguments = false;
3463 : : }
3464 : : }
3465 : :
3466 : : /* Now propagate values from new_reg_base_value to reg_base_value. */
3467 : 18150373 : gcc_assert (maxreg == (unsigned int) max_reg_num ());
3468 : :
3469 : 2647866649 : for (ui = 0; ui < maxreg; ui++)
3470 : : {
3471 : 2629716276 : if (new_reg_base_value[ui]
3472 : 318104407 : && new_reg_base_value[ui] != (*reg_base_value)[ui]
3473 : 2786134792 : && ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui]))
3474 : : {
3475 : 155752548 : (*reg_base_value)[ui] = new_reg_base_value[ui];
3476 : 155752548 : changed = true;
3477 : : }
3478 : : }
3479 : : }
3480 : 18150451 : while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
3481 : 8947473 : XDELETEVEC (rpo);
3482 : :
3483 : : /* Fill in the remaining entries. */
3484 : 467836235 : FOR_EACH_VEC_ELT (*reg_known_value, i, val)
3485 : : {
3486 : 458888762 : int regno = i + FIRST_PSEUDO_REGISTER;
3487 : 458888762 : if (! val)
3488 : 441481295 : set_reg_known_value (regno, regno_reg_rtx[regno]);
3489 : : }
3490 : :
3491 : : /* Clean up. */
3492 : 8947473 : free (new_reg_base_value);
3493 : 8947473 : new_reg_base_value = 0;
3494 : 8947473 : sbitmap_free (reg_seen);
3495 : 8947473 : reg_seen = 0;
3496 : 8947473 : timevar_pop (TV_ALIAS_ANALYSIS);
3497 : 8947473 : }
3498 : :
3499 : : /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3500 : : Special API for var-tracking pass purposes. */
3501 : :
3502 : : void
3503 : 477786 : vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
3504 : : {
3505 : 477786 : (*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2);
3506 : 477786 : }
3507 : :
3508 : : void
3509 : 8947473 : end_alias_analysis (void)
3510 : : {
3511 : 8947473 : old_reg_base_value = reg_base_value;
3512 : 8947473 : vec_free (reg_known_value);
3513 : 8947473 : sbitmap_free (reg_known_equiv_p);
3514 : 8947473 : }
3515 : :
3516 : : void
3517 : 0 : dump_alias_stats_in_alias_c (FILE *s)
3518 : : {
3519 : 0 : fprintf (s, " TBAA oracle: %llu disambiguations %llu queries\n"
3520 : : " %llu are in alias set 0\n"
3521 : : " %llu queries asked about the same object\n"
3522 : : " %llu queries asked about the same alias set\n"
3523 : : " %llu access volatile\n"
3524 : : " %llu are dependent in the DAG\n"
3525 : : " %llu are aritificially in conflict with void *\n",
3526 : : alias_stats.num_disambiguated,
3527 : 0 : alias_stats.num_alias_zero + alias_stats.num_same_alias_set
3528 : 0 : + alias_stats.num_same_objects + alias_stats.num_volatile
3529 : 0 : + alias_stats.num_dag + alias_stats.num_disambiguated
3530 : : + alias_stats.num_universal,
3531 : : alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
3532 : : alias_stats.num_same_objects, alias_stats.num_volatile,
3533 : : alias_stats.num_dag, alias_stats.num_universal);
3534 : 0 : }
3535 : : #include "gt-alias.h"
|
