Branch data Line data Source code
1 : : /* Alias analysis for GNU C
2 : : Copyright (C) 1997-2025 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 : 407750827 : ao_ref_from_mem (ao_ref *ref, const_rtx mem)
275 : : {
276 : 407750827 : tree expr = MEM_EXPR (mem);
277 : 407750827 : tree base;
278 : :
279 : 407750827 : if (!expr)
280 : : return false;
281 : :
282 : 379558357 : 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 : 379558357 : base = ao_ref_base (ref);
287 : 379558357 : 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 : 405482598 : if (!(DECL_P (base)
293 : 207370271 : || (TREE_CODE (base) == MEM_REF
294 : 181576279 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
295 : : || (TREE_CODE (base) == TARGET_MEM_REF
296 : 25763971 : && TREE_CODE (TMR_BASE (base)) == SSA_NAME)))
297 : : return false;
298 : :
299 : 379397384 : 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 : 379397384 : if (!MEM_OFFSET_KNOWN_P (mem)
304 : 379397384 : || !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 : 373254655 : if (maybe_lt (MEM_OFFSET (mem), 0)
310 : 373254655 : || (ref->max_size_known_p ()
311 : 334783643 : && maybe_gt ((MEM_OFFSET (mem) + MEM_SIZE (mem)) * BITS_PER_UNIT,
312 : : ref->max_size)))
313 : 36229796 : 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 : 373254655 : ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
319 : 373254655 : 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 : 373254655 : if (ref->max_size_known_p ())
324 : 334783688 : 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 : 373254655 : if (MEM_EXPR (mem) != get_spill_slot_decl (false)
329 : 373254655 : && (maybe_lt (ref->offset, 0)
330 : 337120815 : || (DECL_P (ref->base)
331 : 130694529 : && (DECL_SIZE (ref->base) == NULL_TREE
332 : 130584238 : || !poly_int_tree_p (DECL_SIZE (ref->base))
333 : 130584188 : || maybe_lt (wi::to_poly_offset (DECL_SIZE (ref->base)),
334 : 503714878 : ref->offset + ref->size)))))
335 : 123965 : 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 : 210582489 : rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p)
346 : : {
347 : 210582489 : ao_ref ref1, ref2;
348 : :
349 : 210582489 : if (!ao_ref_from_mem (&ref1, x)
350 : 210582489 : || !ao_ref_from_mem (&ref2, mem))
351 : 28477408 : return true;
352 : :
353 : 182105081 : return refs_may_alias_p_1 (&ref1, &ref2,
354 : : tbaa_p
355 : 133410573 : && MEM_ALIAS_SET (x) != 0
356 : 446652603 : && 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 : 207349 : refs_same_for_tbaa_p (tree earlier, tree later)
364 : : {
365 : 207349 : ao_ref earlier_ref, later_ref;
366 : 207349 : ao_ref_init (&earlier_ref, earlier);
367 : 207349 : ao_ref_init (&later_ref, later);
368 : 207349 : alias_set_type earlier_set = ao_ref_alias_set (&earlier_ref);
369 : 207349 : alias_set_type later_set = ao_ref_alias_set (&later_ref);
370 : 246636 : if (!(earlier_set == later_set
371 : 39287 : || alias_set_subset_of (later_set, earlier_set)))
372 : : return false;
373 : 206920 : alias_set_type later_base_set = ao_ref_base_alias_set (&later_ref);
374 : 206920 : alias_set_type earlier_base_set = ao_ref_base_alias_set (&earlier_ref);
375 : 206920 : return (earlier_base_set == later_base_set
376 : 206920 : || 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 : 119812 : mems_same_for_tbaa_p (rtx earlier, rtx later)
382 : : {
383 : 119812 : gcc_assert (MEM_P (earlier));
384 : 119812 : gcc_assert (MEM_P (later));
385 : :
386 : 119813 : return ((MEM_ALIAS_SET (earlier) == MEM_ALIAS_SET (later)
387 : 38264 : || alias_set_subset_of (MEM_ALIAS_SET (later),
388 : 38264 : MEM_ALIAS_SET (earlier)))
389 : 237927 : && (!MEM_EXPR (earlier)
390 : 117491 : || 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 : 243682218 : get_alias_set_entry (alias_set_type alias_set)
398 : : {
399 : 487364436 : 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 : 216888525 : mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
407 : : {
408 : 216888525 : return (flag_strict_aliasing
409 : 350785456 : && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1),
410 : 133896931 : MEM_ALIAS_SET (mem2)));
411 : : }
412 : :
413 : : /* Return true if the first alias set is a subset of the second. */
414 : :
415 : : bool
416 : 302328 : alias_set_subset_of (alias_set_type set1, alias_set_type set2)
417 : : {
418 : 302328 : alias_set_entry *ase2;
419 : :
420 : : /* Disable TBAA oracle with !flag_strict_aliasing. */
421 : 302328 : if (!flag_strict_aliasing)
422 : : return true;
423 : :
424 : : /* Everything is a subset of the "aliases everything" set. */
425 : 217676 : if (set2 == 0)
426 : : return true;
427 : :
428 : : /* Check if set1 is a subset of set2. */
429 : 191998 : ase2 = get_alias_set_entry (set2);
430 : 191998 : if (ase2 != 0
431 : 191998 : && (ase2->has_zero_child
432 : 165576 : || (ase2->children && ase2->children->get (set1))))
433 : 153779 : 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 : 38219 : if (ase2 && ase2->has_pointer)
457 : : {
458 : 26508 : alias_set_entry *ase1 = get_alias_set_entry (set1);
459 : :
460 : 26508 : if (ase1 && ase1->is_pointer)
461 : : {
462 : 10466 : 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 : 10466 : if (set1 == voidptr_set || set2 == voidptr_set)
466 : 10172 : return true;
467 : : /* If SET2 contains universal pointer's alias set, then we consdier
468 : : every (non-universal) pointer. */
469 : 10027 : if (ase2->children && set1 != voidptr_set
470 : 10027 : && 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 : 273029371 : alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
481 : : {
482 : 273029371 : alias_set_entry *ase1;
483 : 273029371 : alias_set_entry *ase2;
484 : :
485 : : /* The easy case. */
486 : 273029371 : 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 : 122279647 : ase1 = get_alias_set_entry (set1);
491 : 122279647 : if (ase1 != 0
492 : 122279647 : && ase1->children && ase1->children->get (set2))
493 : : {
494 : 5996140 : ++alias_stats.num_dag;
495 : 5996140 : return true;
496 : : }
497 : :
498 : : /* Now do the same, but with the alias sets reversed. */
499 : 116283507 : ase2 = get_alias_set_entry (set2);
500 : 116283507 : if (ase2 != 0
501 : 116283507 : && ase2->children && ase2->children->get (set1))
502 : : {
503 : 6553187 : ++alias_stats.num_dag;
504 : 6553187 : 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 : 109730320 : if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer)
517 : : {
518 : 15105604 : 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 : 15105604 : if (set1 == voidptr_set || set2 == voidptr_set)
524 : : {
525 : 3424146 : ++alias_stats.num_universal;
526 : 4033768 : return true;
527 : : }
528 : : /* If one of sets is (non-universal) pointer and the other
529 : : contains universal pointer, we also get conflict. */
530 : 11681458 : if (ase1->is_pointer && set2 != voidptr_set
531 : 11681458 : && ase2->children && ase2->children->get (voidptr_set))
532 : : {
533 : 487422 : ++alias_stats.num_universal;
534 : 487422 : return true;
535 : : }
536 : 11194036 : if (ase2->is_pointer && set1 != voidptr_set
537 : 11194036 : && ase1->children && ase1->children->get (voidptr_set))
538 : : {
539 : 122200 : ++alias_stats.num_universal;
540 : 122200 : return true;
541 : : }
542 : : }
543 : :
544 : 105696552 : ++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 : 105696552 : return false;
549 : : }
550 : :
551 : : /* Return true if the two specified alias sets will always conflict. */
552 : :
553 : : bool
554 : 273045350 : alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
555 : : {
556 : : /* Disable TBAA oracle with !flag_strict_aliasing. */
557 : 273045350 : if (!flag_strict_aliasing)
558 : : return true;
559 : 268296626 : if (set1 == 0 || set2 == 0)
560 : : {
561 : 86918199 : ++alias_stats.num_alias_zero;
562 : 86918199 : return true;
563 : : }
564 : 181378427 : if (set1 == set2)
565 : : {
566 : 59098256 : ++alias_stats.num_same_alias_set;
567 : 59098256 : 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 : 10285182 : objects_must_conflict_p (tree t1, tree t2)
580 : : {
581 : 10285182 : 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 : 10285182 : if (t1 == 0 && t2 == 0)
587 : : return false;
588 : :
589 : : /* If they are the same type, they must conflict. */
590 : 64012 : if (t1 == t2)
591 : : {
592 : 48063 : ++alias_stats.num_same_objects;
593 : 48063 : return true;
594 : : }
595 : : /* Likewise if both are volatile. */
596 : 15949 : 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 : 15949 : set1 = t1 ? get_alias_set (t1) : 0;
603 : 15949 : 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 : 15949 : 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 : 487487745 : ends_tbaa_access_path_p (const_tree t)
617 : : {
618 : 487487745 : switch (TREE_CODE (t))
619 : : {
620 : 360600693 : case COMPONENT_REF:
621 : 360600693 : 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 : 357196668 : else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE)
630 : : return true;
631 : : break;
632 : :
633 : 121791086 : case ARRAY_REF:
634 : 121791086 : case ARRAY_RANGE_REF:
635 : 121791086 : 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 : 1090710539 : component_uses_parent_alias_set_from (const_tree t)
664 : : {
665 : 1090710539 : const_tree found = NULL_TREE;
666 : :
667 : 1544430625 : while (handled_component_p (t))
668 : : {
669 : 453720086 : if (ends_tbaa_access_path_p (t))
670 : 12177853 : found = t;
671 : :
672 : 453720086 : t = TREE_OPERAND (t, 0);
673 : : }
674 : :
675 : 1090710539 : if (found)
676 : 12007200 : 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 : 856991566 : ref_all_alias_ptr_type_p (const_tree t)
688 : : {
689 : 856991566 : return (VOID_TYPE_P (TREE_TYPE (t))
690 : 856991566 : || 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 : 98437075 : get_deref_alias_set_1 (tree t)
699 : : {
700 : : /* All we care about is the type. */
701 : 98437075 : if (! TYPE_P (t))
702 : 18 : 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 : 98437075 : if (ref_all_alias_ptr_type_p (t))
708 : 20861869 : 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 : 137170560 : get_deref_alias_set (tree t)
718 : : {
719 : : /* If we're not doing any alias analysis, just assume everything
720 : : aliases everything else. */
721 : 137170560 : if (!flag_strict_aliasing)
722 : : return 0;
723 : :
724 : 98437075 : alias_set_type set = get_deref_alias_set_1 (t);
725 : :
726 : : /* Fall back to the alias-set of the pointed-to type. */
727 : 98437075 : if (set == -1)
728 : : {
729 : 77575206 : if (! TYPE_P (t))
730 : 18 : t = TREE_TYPE (t);
731 : 77575206 : 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 : 1200188415 : reference_alias_ptr_type_1 (tree *t)
744 : : {
745 : 1200188415 : tree inner;
746 : :
747 : : /* Get the base object of the reference. */
748 : 1200188415 : inner = *t;
749 : 1641265090 : 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 : 441076675 : if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
755 : 1739842 : *t = TREE_OPERAND (inner, 0);
756 : 441076675 : inner = TREE_OPERAND (inner, 0);
757 : : }
758 : :
759 : : /* Handle pointer dereferences here, they can override the
760 : : alias-set. */
761 : 1200188415 : if (INDIRECT_REF_P (inner)
762 : 1200188415 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 0))))
763 : 0 : return TREE_TYPE (TREE_OPERAND (inner, 0));
764 : 1200188415 : else if (TREE_CODE (inner) == TARGET_MEM_REF)
765 : 45109878 : return TREE_TYPE (TMR_OFFSET (inner));
766 : 1155078537 : else if (TREE_CODE (inner) == MEM_REF
767 : 1155078537 : && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 1))))
768 : 21799719 : 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 : 1133278818 : if (view_converted_memref_p (inner))
774 : : {
775 : 71009092 : tree alias_ptrtype = TREE_TYPE (TREE_OPERAND (inner, 1));
776 : : /* Unless we have the (aggregate) effective type of the access
777 : : somewhere on the access path. If we have for example
778 : : (&a->elts[i])->l.len exposed by abstraction we'd see
779 : : MEM <A> [(B *)a].elts[i].l.len and we can use the alias set
780 : : of 'len' when typeof (MEM <A> [(B *)a].elts[i]) == B for
781 : : example. See PR111715. */
782 : 71009092 : tree inner = *t;
783 : 71009092 : while (handled_component_p (inner)
784 : 71650982 : && (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
785 : 1497975 : != TYPE_MAIN_VARIANT (TREE_TYPE (alias_ptrtype))))
786 : 641890 : inner = TREE_OPERAND (inner, 0);
787 : 71009092 : if (TREE_CODE (inner) == MEM_REF)
788 : : return alias_ptrtype;
789 : : }
790 : :
791 : : /* Otherwise, pick up the outermost object that we could have
792 : : a pointer to. */
793 : 1063125811 : tree tem = component_uses_parent_alias_set_from (*t);
794 : 1063125811 : if (tem)
795 : 10972642 : *t = tem;
796 : :
797 : : return NULL_TREE;
798 : : }
799 : :
800 : : /* Return the pointer-type relevant for TBAA purposes from the
801 : : gimple memory reference tree T. This is the type to be used for
802 : : the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
803 : : and guarantees that get_alias_set will return the same alias
804 : : set for T and the replacement. */
805 : :
806 : : tree
807 : 8312359 : reference_alias_ptr_type (tree t)
808 : : {
809 : : /* If the frontend assigns this alias-set zero, preserve that. */
810 : 8312359 : if (lang_hooks.get_alias_set (t) == 0)
811 : 0 : return ptr_type_node;
812 : :
813 : 8312359 : tree ptype = reference_alias_ptr_type_1 (&t);
814 : : /* If there is a given pointer type for aliasing purposes, return it. */
815 : 8312359 : if (ptype != NULL_TREE)
816 : : return ptype;
817 : :
818 : : /* Otherwise build one from the outermost component reference we
819 : : may use. */
820 : 7885883 : if (TREE_CODE (t) == MEM_REF
821 : 7885883 : || TREE_CODE (t) == TARGET_MEM_REF)
822 : 890377 : return TREE_TYPE (TREE_OPERAND (t, 1));
823 : : else
824 : 6995506 : return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t)));
825 : : }
826 : :
827 : : /* Return whether the pointer-types T1 and T2 used to determine
828 : : two alias sets of two references will yield the same answer
829 : : from get_deref_alias_set. */
830 : :
831 : : bool
832 : 13406855 : alias_ptr_types_compatible_p (tree t1, tree t2)
833 : : {
834 : 13406855 : if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
835 : : return true;
836 : :
837 : 2066459 : if (ref_all_alias_ptr_type_p (t1)
838 : 2066459 : || ref_all_alias_ptr_type_p (t2))
839 : : return false;
840 : :
841 : : /* This function originally abstracts from simply comparing
842 : : get_deref_alias_set so that we are sure this still computes
843 : : the same result after LTO type merging is applied.
844 : : When in LTO type merging is done we can actually do this compare.
845 : : */
846 : 2039221 : if (in_lto_p)
847 : 5288 : return get_deref_alias_set (t1) == get_deref_alias_set (t2);
848 : : else
849 : 2033933 : return (TYPE_MAIN_VARIANT (TREE_TYPE (t1))
850 : 2033933 : == TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
851 : : }
852 : :
853 : : /* Create emptry alias set entry. */
854 : :
855 : : alias_set_entry *
856 : 1144999 : init_alias_set_entry (alias_set_type set)
857 : : {
858 : 1144999 : alias_set_entry *ase = ggc_alloc<alias_set_entry> ();
859 : 1144999 : ase->alias_set = set;
860 : 1144999 : ase->children = NULL;
861 : 1144999 : ase->has_zero_child = false;
862 : 1144999 : ase->is_pointer = false;
863 : 1144999 : ase->has_pointer = false;
864 : 1144999 : gcc_checking_assert (!get_alias_set_entry (set));
865 : 1144999 : (*alias_sets)[set] = ase;
866 : 1144999 : return ase;
867 : : }
868 : :
869 : : /* Return the alias set for T, which may be either a type or an
870 : : expression. Call language-specific routine for help, if needed. */
871 : :
872 : : alias_set_type
873 : 1455995914 : get_alias_set (tree t)
874 : : {
875 : 1455995914 : alias_set_type set;
876 : :
877 : : /* We cannot give up with -fno-strict-aliasing because we need to build
878 : : proper type representations for possible functions which are built with
879 : : -fstrict-aliasing. */
880 : :
881 : : /* return 0 if this or its type is an error. */
882 : 1455995914 : if (t == error_mark_node
883 : 1455995914 : || (! TYPE_P (t)
884 : 1191549588 : && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
885 : : return 0;
886 : :
887 : : /* We can be passed either an expression or a type. This and the
888 : : language-specific routine may make mutually-recursive calls to each other
889 : : to figure out what to do. At each juncture, we see if this is a tree
890 : : that the language may need to handle specially. First handle things that
891 : : aren't types. */
892 : 1455995914 : if (! TYPE_P (t))
893 : : {
894 : : /* Give the language a chance to do something with this tree
895 : : before we look at it. */
896 : 1191549588 : STRIP_NOPS (t);
897 : 1191549588 : set = lang_hooks.get_alias_set (t);
898 : 1191549588 : if (set != -1)
899 : : return set;
900 : :
901 : : /* Get the alias pointer-type to use or the outermost object
902 : : that we could have a pointer to. */
903 : 1191549588 : tree ptype = reference_alias_ptr_type_1 (&t);
904 : 1191549588 : if (ptype != NULL)
905 : 136633448 : return get_deref_alias_set (ptype);
906 : :
907 : : /* If we've already determined the alias set for a decl, just return
908 : : it. This is necessary for C++ anonymous unions, whose component
909 : : variables don't look like union members (boo!). */
910 : 1054916140 : if (VAR_P (t)
911 : 1054916140 : && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t)))
912 : 166238816 : return MEM_ALIAS_SET (DECL_RTL (t));
913 : :
914 : : /* Now all we care about is the type. */
915 : 971796732 : t = TREE_TYPE (t);
916 : : }
917 : :
918 : : /* Variant qualifiers don't affect the alias set, so get the main
919 : : variant. */
920 : 1236243058 : t = TYPE_MAIN_VARIANT (t);
921 : :
922 : 1236243058 : if (AGGREGATE_TYPE_P (t)
923 : 1236243058 : && TYPE_TYPELESS_STORAGE (t))
924 : : return 0;
925 : :
926 : : /* Always use the canonical type as well. If this is a type that
927 : : requires structural comparisons to identify compatible types
928 : : use alias set zero. */
929 : 1162908398 : if (TYPE_STRUCTURAL_EQUALITY_P (t))
930 : : {
931 : : /* Allow the language to specify another alias set for this
932 : : type. */
933 : 274302844 : set = lang_hooks.get_alias_set (t);
934 : 274302844 : if (set != -1)
935 : : return set;
936 : : /* Handle structure type equality for pointer types, arrays and vectors.
937 : : This is easy to do, because the code below ignores canonical types on
938 : : these anyway. This is important for LTO, where TYPE_CANONICAL for
939 : : pointers cannot be meaningfully computed by the frontend. */
940 : 273857406 : if (canonical_type_used_p (t))
941 : : {
942 : : /* In LTO we set canonical types for all types where it makes
943 : : sense to do so. Double check we did not miss some type. */
944 : 189514043 : gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
945 : : return 0;
946 : : }
947 : : }
948 : : else
949 : : {
950 : 888605554 : t = TYPE_CANONICAL (t);
951 : 888605554 : gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
952 : : }
953 : :
954 : : /* If this is a type with a known alias set, return it. */
955 : 972948917 : gcc_checking_assert (t == TYPE_MAIN_VARIANT (t));
956 : 972948917 : if (TYPE_ALIAS_SET_KNOWN_P (t))
957 : 865042861 : return TYPE_ALIAS_SET (t);
958 : :
959 : : /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
960 : 107906056 : if (!COMPLETE_TYPE_P (t))
961 : : {
962 : : /* For arrays with unknown size the conservative answer is the
963 : : alias set of the element type. */
964 : 14450871 : if (TREE_CODE (t) == ARRAY_TYPE)
965 : 14419258 : return get_alias_set (TREE_TYPE (t));
966 : :
967 : : /* But return zero as a conservative answer for incomplete types. */
968 : : return 0;
969 : : }
970 : :
971 : : /* See if the language has special handling for this type. */
972 : 93455185 : set = lang_hooks.get_alias_set (t);
973 : 93455185 : if (set != -1)
974 : : return set;
975 : :
976 : : /* There are no objects of FUNCTION_TYPE, so there's no point in
977 : : using up an alias set for them. (There are, of course, pointers
978 : : and references to functions, but that's different.) */
979 : 2416679 : else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE)
980 : : set = 0;
981 : :
982 : : /* Unless the language specifies otherwise, let vector types alias
983 : : their components. This avoids some nasty type punning issues in
984 : : normal usage. And indeed lets vectors be treated more like an
985 : : array slice. */
986 : 2412368 : else if (TREE_CODE (t) == VECTOR_TYPE)
987 : 88747 : set = get_alias_set (TREE_TYPE (t));
988 : :
989 : : /* Unless the language specifies otherwise, treat array types the
990 : : same as their components. This avoids the asymmetry we get
991 : : through recording the components. Consider accessing a
992 : : character(kind=1) through a reference to a character(kind=1)[1:1].
993 : : Or consider if we want to assign integer(kind=4)[0:D.1387] and
994 : : integer(kind=4)[4] the same alias set or not.
995 : : Just be pragmatic here and make sure the array and its element
996 : : type get the same alias set assigned. */
997 : 2323621 : else if (TREE_CODE (t) == ARRAY_TYPE
998 : 2323621 : && (!TYPE_NONALIASED_COMPONENT (t)
999 : 0 : || TYPE_STRUCTURAL_EQUALITY_P (t)))
1000 : 387241 : set = get_alias_set (TREE_TYPE (t));
1001 : :
1002 : : /* From the former common C and C++ langhook implementation:
1003 : :
1004 : : Unfortunately, there is no canonical form of a pointer type.
1005 : : In particular, if we have `typedef int I', then `int *', and
1006 : : `I *' are different types. So, we have to pick a canonical
1007 : : representative. We do this below.
1008 : :
1009 : : Technically, this approach is actually more conservative that
1010 : : it needs to be. In particular, `const int *' and `int *'
1011 : : should be in different alias sets, according to the C and C++
1012 : : standard, since their types are not the same, and so,
1013 : : technically, an `int **' and `const int **' cannot point at
1014 : : the same thing.
1015 : :
1016 : : But, the standard is wrong. In particular, this code is
1017 : : legal C++:
1018 : :
1019 : : int *ip;
1020 : : int **ipp = &ip;
1021 : : const int* const* cipp = ipp;
1022 : : And, it doesn't make sense for that to be legal unless you
1023 : : can dereference IPP and CIPP. So, we ignore cv-qualifiers on
1024 : : the pointed-to types. This issue has been reported to the
1025 : : C++ committee.
1026 : :
1027 : : For this reason go to canonical type of the unqalified pointer type.
1028 : : Until GCC 6 this code set all pointers sets to have alias set of
1029 : : ptr_type_node but that is a bad idea, because it prevents disabiguations
1030 : : in between pointers. For Firefox this accounts about 20% of all
1031 : : disambiguations in the program. */
1032 : 1936380 : else if (POINTER_TYPE_P (t) && t != ptr_type_node)
1033 : : {
1034 : 656593 : tree p;
1035 : 656593 : auto_vec <bool, 8> reference;
1036 : :
1037 : : /* Unnest all pointers and references.
1038 : : We also want to make pointer to array/vector equivalent to pointer to
1039 : : its element (see the reasoning above). Skip all those types, too. */
1040 : 656593 : for (p = t; POINTER_TYPE_P (p)
1041 : 718753 : || (TREE_CODE (p) == ARRAY_TYPE
1042 : 61098 : && (!TYPE_NONALIASED_COMPONENT (p)
1043 : 0 : || !COMPLETE_TYPE_P (p)
1044 : 0 : || TYPE_STRUCTURAL_EQUALITY_P (p)))
1045 : 2105407 : || TREE_CODE (p) == VECTOR_TYPE;
1046 : 791159 : p = TREE_TYPE (p))
1047 : : {
1048 : : /* Ada supports recursive pointers. Instead of doing recursion
1049 : : check, just give up once the preallocated space of 8 elements
1050 : : is up. In this case just punt to void * alias set. */
1051 : 791226 : if (reference.length () == 8)
1052 : : {
1053 : 67 : p = ptr_type_node;
1054 : 67 : break;
1055 : : }
1056 : 791159 : if (TREE_CODE (p) == REFERENCE_TYPE)
1057 : : /* In LTO we want languages that use references to be compatible
1058 : : with languages that use pointers. */
1059 : 46251 : reference.safe_push (true && !in_lto_p);
1060 : 791159 : if (TREE_CODE (p) == POINTER_TYPE)
1061 : 682720 : reference.safe_push (false);
1062 : : }
1063 : 656593 : p = TYPE_MAIN_VARIANT (p);
1064 : :
1065 : : /* In LTO for C++ programs we can turn incomplete types to complete
1066 : : using ODR name lookup. */
1067 : 656593 : if (in_lto_p && TYPE_STRUCTURAL_EQUALITY_P (p) && odr_type_p (p))
1068 : : {
1069 : 270 : p = prevailing_odr_type (p);
1070 : 270 : gcc_checking_assert (TYPE_MAIN_VARIANT (p) == p);
1071 : : }
1072 : :
1073 : : /* Make void * compatible with char * and also void **.
1074 : : Programs are commonly violating TBAA by this.
1075 : :
1076 : : We also make void * to conflict with every pointer
1077 : : (see record_component_aliases) and thus it is safe it to use it for
1078 : : pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
1079 : 656593 : if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
1080 : 124829 : set = get_alias_set (ptr_type_node);
1081 : : else
1082 : : {
1083 : : /* Rebuild pointer type starting from canonical types using
1084 : : unqualified pointers and references only. This way all such
1085 : : pointers will have the same alias set and will conflict with
1086 : : each other.
1087 : :
1088 : : Most of time we already have pointers or references of a given type.
1089 : : If not we build new one just to be sure that if someone later
1090 : : (probably only middle-end can, as we should assign all alias
1091 : : classes only after finishing translation unit) builds the pointer
1092 : : type, the canonical type will match. */
1093 : 531764 : p = TYPE_CANONICAL (p);
1094 : 1113748 : while (!reference.is_empty ())
1095 : : {
1096 : 581984 : if (reference.pop ())
1097 : 44407 : p = build_reference_type (p);
1098 : : else
1099 : 537577 : p = build_pointer_type (p);
1100 : 581984 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1101 : : /* build_pointer_type should always return the canonical type.
1102 : : For LTO TYPE_CANOINCAL may be NULL, because we do not compute
1103 : : them. Be sure that frontends do not glob canonical types of
1104 : : pointers in unexpected way and that p == TYPE_CANONICAL (p)
1105 : : in all other cases. */
1106 : 581984 : gcc_checking_assert (!TYPE_CANONICAL (p)
1107 : : || p == TYPE_CANONICAL (p));
1108 : : }
1109 : :
1110 : : /* Assign the alias set to both p and t.
1111 : : We cannot call get_alias_set (p) here as that would trigger
1112 : : infinite recursion when p == t. In other cases it would just
1113 : : trigger unnecesary legwork of rebuilding the pointer again. */
1114 : 531764 : gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
1115 : 531764 : if (TYPE_ALIAS_SET_KNOWN_P (p))
1116 : 68486 : set = TYPE_ALIAS_SET (p);
1117 : : else
1118 : : {
1119 : 463278 : set = new_alias_set ();
1120 : 463278 : TYPE_ALIAS_SET (p) = set;
1121 : : }
1122 : : }
1123 : 656593 : }
1124 : : /* Alias set of ptr_type_node is special and serve as universal pointer which
1125 : : is TBAA compatible with every other pointer type. Be sure we have the
1126 : : alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
1127 : : of pointer types NULL. */
1128 : 1279787 : else if (t == ptr_type_node)
1129 : 60277 : set = new_alias_set ();
1130 : :
1131 : : /* Otherwise make a new alias set for this type. */
1132 : : else
1133 : : {
1134 : : /* Each canonical type gets its own alias set, so canonical types
1135 : : shouldn't form a tree. It doesn't really matter for types
1136 : : we handle specially above, so only check it where it possibly
1137 : : would result in a bogus alias set. */
1138 : 1219510 : gcc_checking_assert (TYPE_CANONICAL (t) == t);
1139 : :
1140 : 1219510 : set = new_alias_set ();
1141 : : }
1142 : :
1143 : 2416679 : TYPE_ALIAS_SET (t) = set;
1144 : :
1145 : : /* If this is an aggregate type or a complex type, we must record any
1146 : : component aliasing information. */
1147 : 2416679 : if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
1148 : 1087275 : record_component_aliases (t);
1149 : :
1150 : : /* We treat pointer types specially in alias_set_subset_of. */
1151 : 2416679 : if (POINTER_TYPE_P (t) && set)
1152 : : {
1153 : 716870 : alias_set_entry *ase = get_alias_set_entry (set);
1154 : 716870 : if (!ase)
1155 : 523555 : ase = init_alias_set_entry (set);
1156 : 716870 : ase->is_pointer = true;
1157 : 716870 : ase->has_pointer = true;
1158 : : }
1159 : :
1160 : : return set;
1161 : : }
1162 : :
1163 : : /* Return a brand-new alias set. */
1164 : :
1165 : : alias_set_type
1166 : 1790798 : new_alias_set (void)
1167 : : {
1168 : 1790798 : if (alias_sets == 0)
1169 : 202225 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1170 : 1790798 : vec_safe_push (alias_sets, (alias_set_entry *) NULL);
1171 : 1790798 : return alias_sets->length () - 1;
1172 : : }
1173 : :
1174 : : /* Indicate that things in SUBSET can alias things in SUPERSET, but that
1175 : : not everything that aliases SUPERSET also aliases SUBSET. For example,
1176 : : in C, a store to an `int' can alias a load of a structure containing an
1177 : : `int', and vice versa. But it can't alias a load of a 'double' member
1178 : : of the same structure. Here, the structure would be the SUPERSET and
1179 : : `int' the SUBSET. This relationship is also described in the comment at
1180 : : the beginning of this file.
1181 : :
1182 : : This function should be called only once per SUPERSET/SUBSET pair.
1183 : :
1184 : : It is illegal for SUPERSET to be zero; everything is implicitly a
1185 : : subset of alias set zero. */
1186 : :
1187 : : void
1188 : 1919142 : record_alias_subset (alias_set_type superset, alias_set_type subset)
1189 : : {
1190 : 1919142 : alias_set_entry *superset_entry;
1191 : 1919142 : alias_set_entry *subset_entry;
1192 : :
1193 : : /* It is possible in complex type situations for both sets to be the same,
1194 : : in which case we can ignore this operation. */
1195 : 1919142 : if (superset == subset)
1196 : : return;
1197 : :
1198 : 1919142 : gcc_assert (superset);
1199 : :
1200 : 1919142 : superset_entry = get_alias_set_entry (superset);
1201 : 1919142 : if (superset_entry == 0)
1202 : : {
1203 : : /* Create an entry for the SUPERSET, so that we have a place to
1204 : : attach the SUBSET. */
1205 : 621444 : superset_entry = init_alias_set_entry (superset);
1206 : : }
1207 : :
1208 : 1919142 : if (subset == 0)
1209 : 84683 : superset_entry->has_zero_child = 1;
1210 : : else
1211 : : {
1212 : 1834459 : if (!superset_entry->children)
1213 : 611030 : superset_entry->children
1214 : 611030 : = hash_map<alias_set_hash, int>::create_ggc (64);
1215 : :
1216 : : /* Enter the SUBSET itself as a child of the SUPERSET. If it was
1217 : : already there we're done. */
1218 : 1834459 : if (superset_entry->children->put (subset, 0))
1219 : : return;
1220 : :
1221 : 1119547 : subset_entry = get_alias_set_entry (subset);
1222 : : /* If there is an entry for the subset, enter all of its children
1223 : : (if they are not already present) as children of the SUPERSET. */
1224 : 1119547 : if (subset_entry)
1225 : : {
1226 : 689340 : if (subset_entry->has_zero_child)
1227 : 16033 : superset_entry->has_zero_child = true;
1228 : 689340 : if (subset_entry->has_pointer)
1229 : 546204 : superset_entry->has_pointer = true;
1230 : :
1231 : 689340 : if (subset_entry->children)
1232 : : {
1233 : 305627 : hash_map<alias_set_hash, int>::iterator iter
1234 : 305627 : = subset_entry->children->begin ();
1235 : 602932741 : for (; iter != subset_entry->children->end (); ++iter)
1236 : 301007930 : superset_entry->children->put ((*iter).first, (*iter).second);
1237 : : }
1238 : : }
1239 : : }
1240 : : }
1241 : :
1242 : : /* Record that component types of TYPE, if any, are part of SUPERSET for
1243 : : aliasing purposes. For record types, we only record component types
1244 : : for fields that are not marked non-addressable. For array types, we
1245 : : only record the component type if it is not marked non-aliased. */
1246 : :
1247 : : void
1248 : 1171880 : record_component_aliases (tree type, alias_set_type superset)
1249 : : {
1250 : 1171880 : tree field;
1251 : :
1252 : 1171880 : if (superset == 0)
1253 : : return;
1254 : :
1255 : 1125053 : switch (TREE_CODE (type))
1256 : : {
1257 : 695270 : case RECORD_TYPE:
1258 : 695270 : case UNION_TYPE:
1259 : 695270 : case QUAL_UNION_TYPE:
1260 : 695270 : {
1261 : : /* LTO non-ODR type merging does not make any difference between
1262 : : component pointer types. We may have
1263 : :
1264 : : struct foo {int *a;};
1265 : :
1266 : : as TYPE_CANONICAL of
1267 : :
1268 : : struct bar {float *a;};
1269 : :
1270 : : Because accesses to int * and float * do not alias, we would get
1271 : : false negative when accessing the same memory location by
1272 : : float ** and bar *. We thus record the canonical type as:
1273 : :
1274 : : struct {void *a;};
1275 : :
1276 : : void * is special cased and works as a universal pointer type.
1277 : : Accesses to it conflicts with accesses to any other pointer
1278 : : type. */
1279 : 695270 : bool void_pointers = in_lto_p
1280 : 695270 : && (!odr_type_p (type)
1281 : 5929 : || !odr_based_tbaa_p (type));
1282 : 12599429 : for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
1283 : 11904159 : if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
1284 : : {
1285 : 1914001 : tree t = TREE_TYPE (field);
1286 : 1914001 : if (void_pointers)
1287 : : {
1288 : : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1289 : : element type and that type has to be normalized to void *,
1290 : : too, in the case it is a pointer. */
1291 : 25667 : while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
1292 : : {
1293 : 1736 : gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
1294 : 1736 : t = TREE_TYPE (t);
1295 : : }
1296 : 22195 : if (POINTER_TYPE_P (t))
1297 : 6379 : t = ptr_type_node;
1298 : 15816 : else if (flag_checking)
1299 : 15816 : gcc_checking_assert (get_alias_set (t)
1300 : : == get_alias_set (TREE_TYPE (field)));
1301 : : }
1302 : :
1303 : 1914001 : alias_set_type set = get_alias_set (t);
1304 : 1914001 : record_alias_subset (superset, set);
1305 : : /* If the field has alias-set zero make sure to still record
1306 : : any componets of it. This makes sure that for
1307 : : struct A {
1308 : : struct B {
1309 : : int i;
1310 : : char c[4];
1311 : : } b;
1312 : : };
1313 : : in C++ even though 'B' has alias-set zero because
1314 : : TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of
1315 : : 'int' as subset. */
1316 : 1914001 : if (set == 0)
1317 : 84605 : record_component_aliases (t, superset);
1318 : : }
1319 : : }
1320 : : break;
1321 : :
1322 : 5141 : case COMPLEX_TYPE:
1323 : 5141 : record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
1324 : 5141 : break;
1325 : :
1326 : : /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1327 : : element type. */
1328 : :
1329 : : default:
1330 : : break;
1331 : : }
1332 : : }
1333 : :
1334 : : /* Record that component types of TYPE, if any, are part of that type for
1335 : : aliasing purposes. For record types, we only record component types
1336 : : for fields that are not marked non-addressable. For array types, we
1337 : : only record the component type if it is not marked non-aliased. */
1338 : :
1339 : : void
1340 : 1087275 : record_component_aliases (tree type)
1341 : : {
1342 : 1087275 : alias_set_type superset = get_alias_set (type);
1343 : 1087275 : record_component_aliases (type, superset);
1344 : 1087275 : }
1345 : :
1346 : :
1347 : : /* Allocate an alias set for use in storing and reading from the varargs
1348 : : spill area. */
1349 : :
1350 : : static GTY(()) alias_set_type varargs_set = -1;
1351 : :
1352 : : alias_set_type
1353 : 20839 : get_varargs_alias_set (void)
1354 : : {
1355 : : #if 1
1356 : : /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1357 : : varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1358 : : consistently use the varargs alias set for loads from the varargs
1359 : : area. So don't use it anywhere. */
1360 : 20839 : return 0;
1361 : : #else
1362 : : if (varargs_set == -1)
1363 : : varargs_set = new_alias_set ();
1364 : :
1365 : : return varargs_set;
1366 : : #endif
1367 : : }
1368 : :
1369 : : /* Likewise, but used for the fixed portions of the frame, e.g., register
1370 : : save areas. */
1371 : :
1372 : : static GTY(()) alias_set_type frame_set = -1;
1373 : :
1374 : : alias_set_type
1375 : 609634 : get_frame_alias_set (void)
1376 : : {
1377 : 609634 : if (frame_set == -1)
1378 : 12288 : frame_set = new_alias_set ();
1379 : :
1380 : 609634 : return frame_set;
1381 : : }
1382 : :
1383 : : /* Create a new, unique base with id ID. */
1384 : :
1385 : : static rtx
1386 : 1651536 : unique_base_value (HOST_WIDE_INT id)
1387 : : {
1388 : 1651536 : return gen_rtx_ADDRESS (Pmode, id);
1389 : : }
1390 : :
1391 : : /* Return true if accesses based on any other base value cannot alias
1392 : : those based on X. */
1393 : :
1394 : : static bool
1395 : 152414020 : unique_base_value_p (rtx x)
1396 : : {
1397 : 122719004 : return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode;
1398 : : }
1399 : :
1400 : : /* Inside SRC, the source of a SET, find a base address. */
1401 : :
1402 : : static rtx
1403 : 412729886 : find_base_value (rtx src)
1404 : : {
1405 : 494327492 : unsigned int regno;
1406 : 494327492 : scalar_int_mode int_mode;
1407 : :
1408 : : #if defined (FIND_BASE_TERM)
1409 : : /* Try machine-dependent ways to find the base term. */
1410 : 494327492 : src = FIND_BASE_TERM (src);
1411 : : #endif
1412 : :
1413 : 494327492 : switch (GET_CODE (src))
1414 : : {
1415 : : case SYMBOL_REF:
1416 : : case LABEL_REF:
1417 : : return src;
1418 : :
1419 : 159092966 : case REG:
1420 : 159092966 : regno = REGNO (src);
1421 : : /* At the start of a function, argument registers have known base
1422 : : values which may be lost later. Returning an ADDRESS
1423 : : expression here allows optimization based on argument values
1424 : : even when the argument registers are used for other purposes. */
1425 : 159092966 : if (regno < FIRST_PSEUDO_REGISTER && copying_arguments)
1426 : 18121221 : return new_reg_base_value[regno];
1427 : :
1428 : : /* If a pseudo has a known base value, return it. Do not do this
1429 : : for non-fixed hard regs since it can result in a circular
1430 : : dependency chain for registers which have values at function entry.
1431 : :
1432 : : The test above is not sufficient because the scheduler may move
1433 : : a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1434 : 85027017 : if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
1435 : 113869762 : && regno < vec_safe_length (reg_base_value))
1436 : : {
1437 : : /* If we're inside init_alias_analysis, use new_reg_base_value
1438 : : to reduce the number of relaxation iterations. */
1439 : 113869762 : if (new_reg_base_value && new_reg_base_value[regno]
1440 : 76720319 : && DF_REG_DEF_COUNT (regno) == 1)
1441 : : return new_reg_base_value[regno];
1442 : :
1443 : 81303171 : if ((*reg_base_value)[regno])
1444 : : return (*reg_base_value)[regno];
1445 : : }
1446 : :
1447 : : return 0;
1448 : :
1449 : 96506917 : case MEM:
1450 : : /* Check for an argument passed in memory. Only record in the
1451 : : copying-arguments block; it is too hard to track changes
1452 : : otherwise. */
1453 : 96506917 : if (copying_arguments
1454 : 3870378 : && (XEXP (src, 0) == arg_pointer_rtx
1455 : 2729220 : || (GET_CODE (XEXP (src, 0)) == PLUS
1456 : 2715793 : && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx)))
1457 : 2783060 : return arg_base_value;
1458 : : return 0;
1459 : :
1460 : 929503 : case CONST:
1461 : 929503 : src = XEXP (src, 0);
1462 : 929503 : if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS)
1463 : : break;
1464 : :
1465 : : /* fall through */
1466 : :
1467 : 101305499 : case PLUS:
1468 : 101305499 : case MINUS:
1469 : 101305499 : {
1470 : 101305499 : rtx src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
1471 : :
1472 : : /* If either operand is a CONST_INT, then the other is the base. */
1473 : 101305499 : if (CONST_INT_P (src_1))
1474 : : return find_base_value (src_0);
1475 : 21573797 : else if (CONST_INT_P (src_0))
1476 : : return find_base_value (src_1);
1477 : :
1478 : : return 0;
1479 : : }
1480 : :
1481 : 0 : case LO_SUM:
1482 : : /* The standard form is (lo_sum reg sym) so look only at the
1483 : : second operand. */
1484 : 0 : return find_base_value (XEXP (src, 1));
1485 : :
1486 : 5838769 : case AND:
1487 : : /* Look through aligning ANDs. And AND with zero or one with
1488 : : the LSB set isn't one (see for example PR92462). */
1489 : 5838769 : if (CONST_INT_P (XEXP (src, 1))
1490 : 4056472 : && INTVAL (XEXP (src, 1)) != 0
1491 : 4021557 : && (INTVAL (XEXP (src, 1)) & 1) == 0)
1492 : 1763775 : return find_base_value (XEXP (src, 0));
1493 : : return 0;
1494 : :
1495 : 12492 : case TRUNCATE:
1496 : : /* As we do not know which address space the pointer is referring to, we can
1497 : : handle this only if the target does not support different pointer or
1498 : : address modes depending on the address space. */
1499 : 12492 : if (!target_default_pointer_address_modes_p ())
1500 : : break;
1501 : 12492 : if (!is_a <scalar_int_mode> (GET_MODE (src), &int_mode)
1502 : 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1503 : : break;
1504 : : /* Fall through. */
1505 : 0 : case HIGH:
1506 : 0 : case PRE_INC:
1507 : 0 : case PRE_DEC:
1508 : 0 : case POST_INC:
1509 : 0 : case POST_DEC:
1510 : 0 : case PRE_MODIFY:
1511 : 0 : case POST_MODIFY:
1512 : 0 : return find_base_value (XEXP (src, 0));
1513 : :
1514 : 9984466 : case ZERO_EXTEND:
1515 : 9984466 : case SIGN_EXTEND: /* used for NT/Alpha pointers */
1516 : : /* As we do not know which address space the pointer is referring to, we can
1517 : : handle this only if the target does not support different pointer or
1518 : : address modes depending on the address space. */
1519 : 9984466 : if (!target_default_pointer_address_modes_p ())
1520 : : break;
1521 : :
1522 : 9984466 : {
1523 : 9984466 : rtx temp = find_base_value (XEXP (src, 0));
1524 : :
1525 : 9984466 : if (temp != 0 && CONSTANT_P (temp))
1526 : 174 : temp = convert_memory_address (Pmode, temp);
1527 : :
1528 : : return temp;
1529 : : }
1530 : :
1531 : : default:
1532 : : break;
1533 : : }
1534 : :
1535 : : return 0;
1536 : : }
1537 : :
1538 : : /* Called from init_alias_analysis indirectly through note_stores,
1539 : : or directly if DEST is a register with a REG_NOALIAS note attached.
1540 : : SET is null in the latter case. */
1541 : :
1542 : : /* While scanning insns to find base values, reg_seen[N] is nonzero if
1543 : : register N has been set in this function. */
1544 : : static sbitmap reg_seen;
1545 : :
1546 : : static void
1547 : 1315114900 : record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
1548 : : {
1549 : 1315114900 : unsigned regno;
1550 : 1315114900 : rtx src;
1551 : 1315114900 : int n;
1552 : :
1553 : 1315114900 : if (!REG_P (dest))
1554 : : return;
1555 : :
1556 : 1003247457 : regno = REGNO (dest);
1557 : :
1558 : 1003247457 : gcc_checking_assert (regno < reg_base_value->length ());
1559 : :
1560 : 1003247457 : n = REG_NREGS (dest);
1561 : 1003247457 : if (n != 1)
1562 : : {
1563 : 15348717 : while (--n >= 0)
1564 : : {
1565 : 10232478 : bitmap_set_bit (reg_seen, regno + n);
1566 : 10232478 : new_reg_base_value[regno + n] = 0;
1567 : : }
1568 : : return;
1569 : : }
1570 : :
1571 : 998131218 : if (set)
1572 : : {
1573 : : /* A CLOBBER wipes out any old value but does not prevent a previously
1574 : : unset register from acquiring a base address (i.e. reg_seen is not
1575 : : set). */
1576 : 997075857 : if (GET_CODE (set) == CLOBBER)
1577 : : {
1578 : 173486577 : new_reg_base_value[regno] = 0;
1579 : 173486577 : return;
1580 : : }
1581 : :
1582 : 823589280 : src = SET_SRC (set);
1583 : : }
1584 : : else
1585 : : {
1586 : : /* There's a REG_NOALIAS note against DEST. */
1587 : 1055361 : if (bitmap_bit_p (reg_seen, regno))
1588 : : {
1589 : 245209 : new_reg_base_value[regno] = 0;
1590 : 245209 : return;
1591 : : }
1592 : 810152 : bitmap_set_bit (reg_seen, regno);
1593 : 810152 : new_reg_base_value[regno] = unique_base_value (unique_id++);
1594 : 810152 : return;
1595 : : }
1596 : :
1597 : : /* If this is not the first set of REGNO, see whether the new value
1598 : : is related to the old one. There are two cases of interest:
1599 : :
1600 : : (1) The register might be assigned an entirely new value
1601 : : that has the same base term as the original set.
1602 : :
1603 : : (2) The set might be a simple self-modification that
1604 : : cannot change REGNO's base value.
1605 : :
1606 : : If neither case holds, reject the original base value as invalid.
1607 : : Note that the following situation is not detected:
1608 : :
1609 : : extern int x, y; int *p = &x; p += (&y-&x);
1610 : :
1611 : : ANSI C does not allow computing the difference of addresses
1612 : : of distinct top level objects. */
1613 : 823589280 : if (new_reg_base_value[regno] != 0
1614 : 823589280 : && find_base_value (src) != new_reg_base_value[regno])
1615 : 73530606 : switch (GET_CODE (src))
1616 : : {
1617 : 431140 : case LO_SUM:
1618 : 431140 : case MINUS:
1619 : 431140 : if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
1620 : 69682 : new_reg_base_value[regno] = 0;
1621 : : break;
1622 : 22659811 : case PLUS:
1623 : : /* If the value we add in the PLUS is also a valid base value,
1624 : : this might be the actual base value, and the original value
1625 : : an index. */
1626 : 22659811 : {
1627 : 22659811 : rtx other = NULL_RTX;
1628 : :
1629 : 22659811 : if (XEXP (src, 0) == dest)
1630 : 19489889 : other = XEXP (src, 1);
1631 : 3169922 : else if (XEXP (src, 1) == dest)
1632 : : other = XEXP (src, 0);
1633 : :
1634 : 19800074 : if (! other || find_base_value (other))
1635 : 2864961 : new_reg_base_value[regno] = 0;
1636 : : break;
1637 : : }
1638 : 67656 : case AND:
1639 : 67656 : if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1)))
1640 : 46882 : new_reg_base_value[regno] = 0;
1641 : : break;
1642 : 50371999 : default:
1643 : 50371999 : new_reg_base_value[regno] = 0;
1644 : 50371999 : break;
1645 : : }
1646 : : /* If this is the first set of a register, record the value. */
1647 : 440612910 : else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
1648 : 1064196259 : && ! bitmap_bit_p (reg_seen, regno) && new_reg_base_value[regno] == 0)
1649 : 276708605 : new_reg_base_value[regno] = find_base_value (src);
1650 : :
1651 : 823589280 : bitmap_set_bit (reg_seen, regno);
1652 : : }
1653 : :
1654 : : /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1655 : : using hard registers with non-null REG_BASE_VALUE for renaming. */
1656 : : rtx
1657 : 1277 : get_reg_base_value (unsigned int regno)
1658 : : {
1659 : 1277 : return (*reg_base_value)[regno];
1660 : : }
1661 : :
1662 : : /* If a value is known for REGNO, return it. */
1663 : :
1664 : : rtx
1665 : 244314153 : get_reg_known_value (unsigned int regno)
1666 : : {
1667 : 244314153 : if (regno >= FIRST_PSEUDO_REGISTER)
1668 : : {
1669 : 229413405 : regno -= FIRST_PSEUDO_REGISTER;
1670 : 229413405 : if (regno < vec_safe_length (reg_known_value))
1671 : 213750488 : return (*reg_known_value)[regno];
1672 : : }
1673 : : return NULL;
1674 : : }
1675 : :
1676 : : /* Set it. */
1677 : :
1678 : : static void
1679 : 499697254 : set_reg_known_value (unsigned int regno, rtx val)
1680 : : {
1681 : 499697254 : if (regno >= FIRST_PSEUDO_REGISTER)
1682 : : {
1683 : 499697254 : regno -= FIRST_PSEUDO_REGISTER;
1684 : 499697254 : if (regno < vec_safe_length (reg_known_value))
1685 : 499697254 : (*reg_known_value)[regno] = val;
1686 : : }
1687 : 499697254 : }
1688 : :
1689 : : /* Similarly for reg_known_equiv_p. */
1690 : :
1691 : : bool
1692 : 27562 : get_reg_known_equiv_p (unsigned int regno)
1693 : : {
1694 : 27562 : if (regno >= FIRST_PSEUDO_REGISTER)
1695 : : {
1696 : 27562 : regno -= FIRST_PSEUDO_REGISTER;
1697 : 27562 : if (regno < vec_safe_length (reg_known_value))
1698 : 26792 : return bitmap_bit_p (reg_known_equiv_p, regno);
1699 : : }
1700 : : return false;
1701 : : }
1702 : :
1703 : : static void
1704 : 39402410 : set_reg_known_equiv_p (unsigned int regno, bool val)
1705 : : {
1706 : 39402410 : if (regno >= FIRST_PSEUDO_REGISTER)
1707 : : {
1708 : 39402410 : regno -= FIRST_PSEUDO_REGISTER;
1709 : 39402410 : if (regno < vec_safe_length (reg_known_value))
1710 : : {
1711 : 39402410 : if (val)
1712 : 0 : bitmap_set_bit (reg_known_equiv_p, regno);
1713 : : else
1714 : 39402410 : bitmap_clear_bit (reg_known_equiv_p, regno);
1715 : : }
1716 : : }
1717 : 39402410 : }
1718 : :
1719 : :
1720 : : /* Returns a canonical version of X, from the point of view alias
1721 : : analysis. (For example, if X is a MEM whose address is a register,
1722 : : and the register has a known value (say a SYMBOL_REF), then a MEM
1723 : : whose address is the SYMBOL_REF is returned.) */
1724 : :
1725 : : rtx
1726 : 5053568844 : canon_rtx (rtx x)
1727 : : {
1728 : : /* Recursively look for equivalences. */
1729 : 5056907284 : if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1730 : : {
1731 : 203556387 : rtx t = get_reg_known_value (REGNO (x));
1732 : 203556387 : if (t == x)
1733 : : return x;
1734 : 19001357 : if (t)
1735 : : return canon_rtx (t);
1736 : : }
1737 : :
1738 : 4869013814 : if (GET_CODE (x) == PLUS)
1739 : : {
1740 : 1404751216 : rtx x0 = canon_rtx (XEXP (x, 0));
1741 : 1404751216 : rtx x1 = canon_rtx (XEXP (x, 1));
1742 : :
1743 : 1404751216 : if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
1744 : 2218491 : return simplify_gen_binary (PLUS, GET_MODE (x), x0, x1);
1745 : : }
1746 : :
1747 : : /* This gives us much better alias analysis when called from
1748 : : the loop optimizer. Note we want to leave the original
1749 : : MEM alone, but need to return the canonicalized MEM with
1750 : : all the flags with their original values. */
1751 : 3464262598 : else if (MEM_P (x))
1752 : 305568592 : x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0)));
1753 : :
1754 : : return x;
1755 : : }
1756 : :
1757 : : /* Return true if X and Y are identical-looking rtx's.
1758 : : Expect that X and Y has been already canonicalized.
1759 : :
1760 : : We use the data in reg_known_value above to see if two registers with
1761 : : different numbers are, in fact, equivalent. */
1762 : :
1763 : : static bool
1764 : 8404073245 : rtx_equal_for_memref_p (const_rtx x, const_rtx y)
1765 : : {
1766 : 8404092840 : int i;
1767 : 8404092840 : int j;
1768 : 8404092840 : enum rtx_code code;
1769 : 8404092840 : const char *fmt;
1770 : :
1771 : 8404092840 : if (x == 0 && y == 0)
1772 : : return true;
1773 : 8404092840 : if (x == 0 || y == 0)
1774 : : return false;
1775 : :
1776 : 8404092840 : if (x == y)
1777 : : return true;
1778 : :
1779 : 6758950055 : code = GET_CODE (x);
1780 : : /* Rtx's of different codes cannot be equal. */
1781 : 6758950055 : if (code != GET_CODE (y))
1782 : : return false;
1783 : :
1784 : : /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1785 : : (REG:SI x) and (REG:HI x) are NOT equivalent. */
1786 : :
1787 : 4597212294 : if (GET_MODE (x) != GET_MODE (y))
1788 : : return false;
1789 : :
1790 : : /* Some RTL can be compared without a recursive examination. */
1791 : 4597212143 : switch (code)
1792 : : {
1793 : 215289452 : case REG:
1794 : 215289452 : return REGNO (x) == REGNO (y);
1795 : :
1796 : 0 : case LABEL_REF:
1797 : 0 : return label_ref_label (x) == label_ref_label (y);
1798 : :
1799 : 3719980 : case SYMBOL_REF:
1800 : 3719980 : {
1801 : 3719980 : HOST_WIDE_INT distance = 0;
1802 : 3719980 : return (compare_base_symbol_refs (x, y, &distance) == 1
1803 : 3719980 : && distance == 0);
1804 : : }
1805 : :
1806 : 1994434 : case ENTRY_VALUE:
1807 : : /* This is magic, don't go through canonicalization et al. */
1808 : 1994434 : return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1809 : :
1810 : : case VALUE:
1811 : : CASE_CONST_UNIQUE:
1812 : : /* Pointer equality guarantees equality for these nodes. */
1813 : : return false;
1814 : :
1815 : 1322604478 : default:
1816 : 1322604478 : break;
1817 : : }
1818 : :
1819 : : /* canon_rtx knows how to handle plus. No need to canonicalize. */
1820 : 1322604478 : if (code == PLUS)
1821 : 1304793862 : return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))
1822 : 623930479 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1)))
1823 : 1921234332 : || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1))
1824 : 137804 : && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0))));
1825 : : /* For commutative operations, the RTX match if the operand match in any
1826 : : order. Also handle the simple binary and unary cases without a loop. */
1827 : 17810616 : if (COMMUTATIVE_P (x))
1828 : : {
1829 : 4185871 : rtx xop0 = canon_rtx (XEXP (x, 0));
1830 : 4185871 : rtx yop0 = canon_rtx (XEXP (y, 0));
1831 : 4185871 : rtx yop1 = canon_rtx (XEXP (y, 1));
1832 : :
1833 : 4185871 : return ((rtx_equal_for_memref_p (xop0, yop0)
1834 : 1423435 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1))
1835 : 4295586 : || (rtx_equal_for_memref_p (xop0, yop1)
1836 : 30 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0)));
1837 : : }
1838 : 13624745 : else if (NON_COMMUTATIVE_P (x))
1839 : : {
1840 : 120860 : return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1841 : 120860 : canon_rtx (XEXP (y, 0)))
1842 : 162652 : && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)),
1843 : 41792 : canon_rtx (XEXP (y, 1))));
1844 : : }
1845 : 13503885 : else if (UNARY_P (x))
1846 : 19595 : return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)),
1847 : 39190 : canon_rtx (XEXP (y, 0)));
1848 : :
1849 : : /* Compare the elements. If any pair of corresponding elements
1850 : : fail to match, return false for the whole things.
1851 : :
1852 : : Limit cases to types which actually appear in addresses. */
1853 : :
1854 : 13484290 : fmt = GET_RTX_FORMAT (code);
1855 : 20688070 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1856 : : {
1857 : 20141041 : switch (fmt[i])
1858 : : {
1859 : 3393895 : case 'i':
1860 : 3393895 : if (XINT (x, i) != XINT (y, i))
1861 : : return false;
1862 : : break;
1863 : :
1864 : 152 : case 'L':
1865 : 152 : if (XLOC (x, i) != XLOC (y, i))
1866 : : return false;
1867 : : break;
1868 : :
1869 : 48 : case 'p':
1870 : 48 : if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1871 : : return false;
1872 : : break;
1873 : :
1874 : 3393847 : case 'E':
1875 : : /* Two vectors must have the same length. */
1876 : 3393847 : if (XVECLEN (x, i) != XVECLEN (y, i))
1877 : : return false;
1878 : :
1879 : : /* And the corresponding elements must match. */
1880 : 3644530 : for (j = 0; j < XVECLEN (x, i); j++)
1881 : 3394871 : if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)),
1882 : 3394871 : canon_rtx (XVECEXP (y, i, j))) == 0)
1883 : : return false;
1884 : : break;
1885 : :
1886 : 10179315 : case 'e':
1887 : 10179315 : if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)),
1888 : 10179315 : canon_rtx (XEXP (y, i))) == 0)
1889 : : return false;
1890 : : break;
1891 : :
1892 : : /* This can happen for asm operands. */
1893 : 0 : case 's':
1894 : 0 : if (strcmp (XSTR (x, i), XSTR (y, i)))
1895 : : return false;
1896 : : break;
1897 : :
1898 : : /* This can happen for an asm which clobbers memory. */
1899 : : case '0':
1900 : : break;
1901 : :
1902 : : /* It is believed that rtx's at this level will never
1903 : : contain anything but integers and other rtx's,
1904 : : except for within LABEL_REFs and SYMBOL_REFs. */
1905 : 0 : default:
1906 : 0 : gcc_unreachable ();
1907 : : }
1908 : : }
1909 : : return true;
1910 : : }
1911 : :
1912 : : static rtx
1913 : 3098323930 : find_base_term (rtx x, vec<std::pair<cselib_val *,
1914 : : struct elt_loc_list *> > &visited_vals)
1915 : : {
1916 : 5864630183 : cselib_val *val;
1917 : 5864630183 : struct elt_loc_list *l, *f;
1918 : 5864630183 : rtx ret;
1919 : 5864630183 : scalar_int_mode int_mode;
1920 : :
1921 : : #if defined (FIND_BASE_TERM)
1922 : : /* Try machine-dependent ways to find the base term. */
1923 : 5864630183 : x = FIND_BASE_TERM (x);
1924 : : #endif
1925 : :
1926 : 5864630183 : switch (GET_CODE (x))
1927 : : {
1928 : 2049418193 : case REG:
1929 : 2049418193 : return REG_BASE_VALUE (x);
1930 : :
1931 : 0 : case TRUNCATE:
1932 : : /* As we do not know which address space the pointer is referring to, we can
1933 : : handle this only if the target does not support different pointer or
1934 : : address modes depending on the address space. */
1935 : 0 : if (!target_default_pointer_address_modes_p ())
1936 : : return 0;
1937 : 96236615 : if (!is_a <scalar_int_mode> (GET_MODE (x), &int_mode)
1938 : 0 : || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode))
1939 : : return 0;
1940 : : /* Fall through. */
1941 : 42012956 : case HIGH:
1942 : 42012956 : case PRE_INC:
1943 : 42012956 : case PRE_DEC:
1944 : 42012956 : case POST_INC:
1945 : 42012956 : case POST_DEC:
1946 : 42012956 : case PRE_MODIFY:
1947 : 42012956 : case POST_MODIFY:
1948 : 42012956 : return find_base_term (XEXP (x, 0), visited_vals);
1949 : :
1950 : 414 : case ZERO_EXTEND:
1951 : 414 : case SIGN_EXTEND: /* Used for Alpha/NT pointers */
1952 : : /* As we do not know which address space the pointer is referring to, we can
1953 : : handle this only if the target does not support different pointer or
1954 : : address modes depending on the address space. */
1955 : 414 : if (!target_default_pointer_address_modes_p ())
1956 : : return 0;
1957 : :
1958 : 414 : {
1959 : 414 : rtx temp = find_base_term (XEXP (x, 0), visited_vals);
1960 : :
1961 : 414 : if (temp != 0 && CONSTANT_P (temp))
1962 : 0 : temp = convert_memory_address (Pmode, temp);
1963 : :
1964 : : return temp;
1965 : : }
1966 : :
1967 : 825626654 : case VALUE:
1968 : 825626654 : val = CSELIB_VAL_PTR (x);
1969 : 825626654 : ret = NULL_RTX;
1970 : :
1971 : 825626654 : if (!val)
1972 : : return ret;
1973 : :
1974 : 825626654 : if (cselib_sp_based_value_p (val))
1975 : 18939376 : return static_reg_base_value[STACK_POINTER_REGNUM];
1976 : :
1977 : 806687278 : if (visited_vals.length () > (unsigned) param_max_find_base_term_values)
1978 : : return ret;
1979 : :
1980 : 804686227 : f = val->locs;
1981 : : /* Reset val->locs to avoid infinite recursion. */
1982 : 804686227 : if (f)
1983 : 643785173 : visited_vals.safe_push (std::make_pair (val, f));
1984 : 804686227 : val->locs = NULL;
1985 : :
1986 : 1436034241 : for (l = f; l; l = l->next)
1987 : 804084850 : if (GET_CODE (l->loc) == VALUE
1988 : 107928890 : && CSELIB_VAL_PTR (l->loc)->locs
1989 : 107886112 : && !CSELIB_VAL_PTR (l->loc)->locs->next
1990 : 107846929 : && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
1991 : 107846929 : continue;
1992 : 696237921 : else if ((ret = find_base_term (l->loc, visited_vals)) != 0)
1993 : : break;
1994 : :
1995 : : return ret;
1996 : :
1997 : 0 : case LO_SUM:
1998 : : /* The standard form is (lo_sum reg sym) so look only at the
1999 : : second operand. */
2000 : 0 : return find_base_term (XEXP (x, 1), visited_vals);
2001 : :
2002 : 31832316 : case CONST:
2003 : 31832316 : x = XEXP (x, 0);
2004 : 31832316 : if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
2005 : : return 0;
2006 : : /* Fall through. */
2007 : 2721559639 : case PLUS:
2008 : 2721559639 : case MINUS:
2009 : 2721559639 : {
2010 : 2721559639 : rtx tmp1 = XEXP (x, 0);
2011 : 2721559639 : rtx tmp2 = XEXP (x, 1);
2012 : :
2013 : : /* This is a little bit tricky since we have to determine which of
2014 : : the two operands represents the real base address. Otherwise this
2015 : : routine may return the index register instead of the base register.
2016 : :
2017 : : That may cause us to believe no aliasing was possible, when in
2018 : : fact aliasing is possible.
2019 : :
2020 : : We use a few simple tests to guess the base register. Additional
2021 : : tests can certainly be added. For example, if one of the operands
2022 : : is a shift or multiply, then it must be the index register and the
2023 : : other operand is the base register. */
2024 : :
2025 : 2721559639 : if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
2026 : : return find_base_term (tmp2, visited_vals);
2027 : :
2028 : 2721559635 : if (CONST_INT_P (tmp1))
2029 : 0 : std::swap (tmp1, tmp2);
2030 : :
2031 : : /* We can only handle binary operators when one of the operands
2032 : : never leads to a base value. */
2033 : 2721559635 : if (CONST_INT_P (tmp2))
2034 : : return find_base_term (tmp1, visited_vals);
2035 : :
2036 : : /* We could not determine which of the two operands was the
2037 : : base register and which was the index. So we can determine
2038 : : nothing from the base alias check. */
2039 : : return 0;
2040 : : }
2041 : :
2042 : 56412712 : case AND:
2043 : : /* Look through aligning ANDs. And AND with zero or one with
2044 : : the LSB set isn't one (see for example PR92462). */
2045 : 56412712 : if (CONST_INT_P (XEXP (x, 1))
2046 : 56412635 : && INTVAL (XEXP (x, 1)) != 0
2047 : 56412635 : && (INTVAL (XEXP (x, 1)) & 1) == 0)
2048 : 56412628 : return find_base_term (XEXP (x, 0), visited_vals);
2049 : : return 0;
2050 : :
2051 : : case SYMBOL_REF:
2052 : : case LABEL_REF:
2053 : : return x;
2054 : :
2055 : : default:
2056 : : return 0;
2057 : : }
2058 : : }
2059 : :
2060 : : /* Wrapper around the worker above which removes locs from visited VALUEs
2061 : : to avoid visiting them multiple times. We unwind that changes here. */
2062 : :
2063 : : static rtx
2064 : 2402085595 : find_base_term (rtx x)
2065 : : {
2066 : 2402085595 : auto_vec<std::pair<cselib_val *, struct elt_loc_list *>, 32> visited_vals;
2067 : 2402085595 : rtx res = find_base_term (x, visited_vals);
2068 : 3045870768 : for (unsigned i = 0; i < visited_vals.length (); ++i)
2069 : 643785173 : visited_vals[i].first->locs = visited_vals[i].second;
2070 : 2402085595 : return res;
2071 : 2402085595 : }
2072 : :
2073 : : /* Return true if accesses to address X may alias accesses based
2074 : : on the stack pointer. */
2075 : :
2076 : : bool
2077 : 14010021 : may_be_sp_based_p (rtx x)
2078 : : {
2079 : 14010021 : rtx base = find_base_term (x);
2080 : 14010021 : return !base || base == static_reg_base_value[STACK_POINTER_REGNUM];
2081 : : }
2082 : :
2083 : : /* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0
2084 : : if they refer to different objects and -1 if we cannot decide. */
2085 : :
2086 : : int
2087 : 1361137565 : compare_base_decls (tree base1, tree base2)
2088 : : {
2089 : 1361137565 : int ret;
2090 : 1361137565 : gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
2091 : 1361137565 : if (base1 == base2)
2092 : : return 1;
2093 : :
2094 : : /* If we have two register decls with register specification we
2095 : : cannot decide unless their assembler names are the same. */
2096 : 1179002900 : if (VAR_P (base1)
2097 : 1131818634 : && VAR_P (base2)
2098 : 1127109793 : && DECL_HARD_REGISTER (base1)
2099 : 12419 : && DECL_HARD_REGISTER (base2)
2100 : 12262 : && DECL_ASSEMBLER_NAME_SET_P (base1)
2101 : 1179015162 : && DECL_ASSEMBLER_NAME_SET_P (base2))
2102 : : {
2103 : 12262 : if (DECL_ASSEMBLER_NAME_RAW (base1) == DECL_ASSEMBLER_NAME_RAW (base2))
2104 : : return 1;
2105 : 12262 : return -1;
2106 : : }
2107 : :
2108 : : /* Declarations of non-automatic variables may have aliases. All other
2109 : : decls are unique. */
2110 : 1178990638 : if (!decl_in_symtab_p (base1)
2111 : 1178990638 : || !decl_in_symtab_p (base2))
2112 : : return 0;
2113 : :
2114 : : /* Don't cause symbols to be inserted by the act of checking. */
2115 : 84225613 : symtab_node *node1 = symtab_node::get (base1);
2116 : 84225613 : if (!node1)
2117 : : return 0;
2118 : 84210458 : symtab_node *node2 = symtab_node::get (base2);
2119 : 84210458 : if (!node2)
2120 : : return 0;
2121 : :
2122 : 84191760 : ret = node1->equal_address_to (node2, true);
2123 : 84191760 : return ret;
2124 : : }
2125 : :
2126 : : /* Compare SYMBOL_REFs X_BASE and Y_BASE.
2127 : :
2128 : : - Return 1 if Y_BASE - X_BASE is constant, adding that constant
2129 : : to *DISTANCE if DISTANCE is nonnull.
2130 : :
2131 : : - Return 0 if no accesses based on X_BASE can alias Y_BASE.
2132 : :
2133 : : - Return -1 if one of the two results applies, but we can't tell
2134 : : which at compile time. Update DISTANCE in the same way as
2135 : : for a return value of 1, for the case in which that holds. */
2136 : :
2137 : : static int
2138 : 22674205 : compare_base_symbol_refs (const_rtx x_base, const_rtx y_base,
2139 : : HOST_WIDE_INT *distance)
2140 : : {
2141 : 22674205 : tree x_decl = SYMBOL_REF_DECL (x_base);
2142 : 22674205 : tree y_decl = SYMBOL_REF_DECL (y_base);
2143 : 22674205 : bool binds_def = true;
2144 : 22674205 : bool swap = false;
2145 : :
2146 : 22674205 : if (XSTR (x_base, 0) == XSTR (y_base, 0))
2147 : : return 1;
2148 : 22319236 : if (x_decl && y_decl)
2149 : 22319236 : return compare_base_decls (x_decl, y_decl);
2150 : 0 : if (x_decl || y_decl)
2151 : : {
2152 : : if (!x_decl)
2153 : : {
2154 : : swap = true;
2155 : : std::swap (x_decl, y_decl);
2156 : : std::swap (x_base, y_base);
2157 : : }
2158 : : /* We handle specially only section anchors. Other symbols are
2159 : : either equal (via aliasing) or refer to different objects. */
2160 : 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2161 : : return -1;
2162 : : /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe
2163 : : to ignore CONST_DECLs because they are readonly. */
2164 : 0 : if (!VAR_P (x_decl)
2165 : 0 : || (!TREE_STATIC (x_decl) && !TREE_PUBLIC (x_decl)))
2166 : : return 0;
2167 : :
2168 : 0 : symtab_node *x_node = symtab_node::get_create (x_decl)
2169 : 0 : ->ultimate_alias_target ();
2170 : : /* External variable cannot be in section anchor. */
2171 : 0 : if (!x_node->definition)
2172 : : return 0;
2173 : 0 : x_base = XEXP (DECL_RTL (x_node->decl), 0);
2174 : : /* If not in anchor, we can disambiguate. */
2175 : 0 : if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base))
2176 : : return 0;
2177 : :
2178 : : /* We have an alias of anchored variable. If it can be interposed;
2179 : : we must assume it may or may not alias its anchor. */
2180 : 0 : binds_def = decl_binds_to_current_def_p (x_decl);
2181 : : }
2182 : : /* If we have variable in section anchor, we can compare by offset. */
2183 : 0 : if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base)
2184 : 0 : && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base))
2185 : : {
2186 : 0 : if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base))
2187 : : return 0;
2188 : 0 : if (distance)
2189 : 0 : *distance += (swap ? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base)
2190 : 0 : - SYMBOL_REF_BLOCK_OFFSET (x_base));
2191 : 0 : return binds_def ? 1 : -1;
2192 : : }
2193 : : /* Either the symbols are equal (via aliasing) or they refer to
2194 : : different objects. */
2195 : : return -1;
2196 : : }
2197 : :
2198 : : /* Return false if the addresses X and Y are known to point to different
2199 : : objects, true if they might be pointers to the same object. */
2200 : :
2201 : : static bool
2202 : 1193944883 : base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base,
2203 : : machine_mode x_mode, machine_mode y_mode)
2204 : : {
2205 : : /* If the address itself has no known base see if a known equivalent
2206 : : value has one. If either address still has no known base, nothing
2207 : : is known about aliasing. */
2208 : 1193944883 : if (x_base == 0)
2209 : : {
2210 : 144855357 : rtx x_c;
2211 : :
2212 : 144855357 : if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x)
2213 : 144704458 : return true;
2214 : :
2215 : 150899 : x_base = find_base_term (x_c);
2216 : 150899 : if (x_base == 0)
2217 : : return true;
2218 : : }
2219 : :
2220 : 1049091461 : if (y_base == 0)
2221 : : {
2222 : 158720271 : rtx y_c;
2223 : 158720271 : if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y)
2224 : 158687012 : return true;
2225 : :
2226 : 33259 : y_base = find_base_term (y_c);
2227 : 33259 : if (y_base == 0)
2228 : : return true;
2229 : : }
2230 : :
2231 : : /* If the base addresses are equal nothing is known about aliasing. */
2232 : 890373951 : if (rtx_equal_p (x_base, y_base))
2233 : : return true;
2234 : :
2235 : : /* The base addresses are different expressions. If they are not accessed
2236 : : via AND, there is no conflict. We can bring knowledge of object
2237 : : alignment into play here. For example, on alpha, "char a, b;" can
2238 : : alias one another, though "char a; long b;" cannot. AND addresses may
2239 : : implicitly alias surrounding objects; i.e. unaligned access in DImode
2240 : : via AND address can alias all surrounding object types except those
2241 : : with aligment 8 or higher. */
2242 : 131265435 : if (GET_CODE (x) == AND && GET_CODE (y) == AND)
2243 : : return true;
2244 : 131265435 : if (GET_CODE (x) == AND
2245 : 131265435 : && (!CONST_INT_P (XEXP (x, 1))
2246 : 1945 : || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
2247 : : return true;
2248 : 131263658 : if (GET_CODE (y) == AND
2249 : 131263658 : && (!CONST_INT_P (XEXP (y, 1))
2250 : 1903 : || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
2251 : : return true;
2252 : :
2253 : : /* Differing symbols not accessed via AND never alias. */
2254 : 131261844 : if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF)
2255 : 18460902 : return compare_base_symbol_refs (x_base, y_base) != 0;
2256 : :
2257 : 112800942 : if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
2258 : : return false;
2259 : :
2260 : 123037830 : if (unique_base_value_p (x_base) || unique_base_value_p (y_base))
2261 : : return false;
2262 : :
2263 : : return true;
2264 : : }
2265 : :
2266 : : /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
2267 : : (or equal to) that of V. */
2268 : :
2269 : : static bool
2270 : 216753347 : refs_newer_value_p (const_rtx expr, rtx v)
2271 : : {
2272 : 216753347 : int minuid = CSELIB_VAL_PTR (v)->uid;
2273 : 216753347 : subrtx_iterator::array_type array;
2274 : 627215899 : FOR_EACH_SUBRTX (iter, array, expr, NONCONST)
2275 : 530601840 : if (GET_CODE (*iter) == VALUE && CSELIB_VAL_PTR (*iter)->uid >= minuid)
2276 : 120139288 : return true;
2277 : 96614059 : return false;
2278 : 216753347 : }
2279 : :
2280 : : /* Convert the address X into something we can use. This is done by returning
2281 : : it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE
2282 : : we call cselib to get a more useful rtx. */
2283 : :
2284 : : rtx
2285 : 3712348624 : get_addr (rtx x)
2286 : : {
2287 : 3712348624 : cselib_val *v;
2288 : 3712348624 : struct elt_loc_list *l;
2289 : :
2290 : 3712348624 : if (GET_CODE (x) != VALUE)
2291 : : {
2292 : 2348955231 : if ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
2293 : 1986120789 : && GET_CODE (XEXP (x, 0)) == VALUE
2294 : 112852684 : && CONST_SCALAR_INT_P (XEXP (x, 1)))
2295 : : {
2296 : 106906742 : rtx op0 = get_addr (XEXP (x, 0));
2297 : 106906742 : if (op0 != XEXP (x, 0))
2298 : : {
2299 : 31005856 : poly_int64 c;
2300 : 31005856 : if (GET_CODE (x) == PLUS
2301 : 31005856 : && poly_int_rtx_p (XEXP (x, 1), &c))
2302 : 31005856 : return plus_constant (GET_MODE (x), op0, c);
2303 : 0 : return simplify_gen_binary (GET_CODE (x), GET_MODE (x),
2304 : 0 : op0, XEXP (x, 1));
2305 : : }
2306 : : }
2307 : 2317949375 : return x;
2308 : : }
2309 : 1363393393 : v = CSELIB_VAL_PTR (x);
2310 : 1363393393 : if (v)
2311 : : {
2312 : 1363393393 : bool have_equivs = cselib_have_permanent_equivalences ();
2313 : 1363393393 : if (have_equivs)
2314 : 318369141 : v = canonical_cselib_val (v);
2315 : 2641164511 : for (l = v->locs; l; l = l->next)
2316 : 1303154770 : if (CONSTANT_P (l->loc))
2317 : : return l->loc;
2318 : 1578272886 : for (l = v->locs; l; l = l->next)
2319 : 1203906416 : if (!REG_P (l->loc) && !MEM_P (l->loc)
2320 : : /* Avoid infinite recursion when potentially dealing with
2321 : : var-tracking artificial equivalences, by skipping the
2322 : : equivalences themselves, and not choosing expressions
2323 : : that refer to newer VALUEs. */
2324 : 2475551346 : && (!have_equivs
2325 : 256790682 : || (GET_CODE (l->loc) != VALUE
2326 : 155898283 : && !refs_newer_value_p (l->loc, x))))
2327 : 1037152048 : return l->loc;
2328 : 300857693 : if (have_equivs)
2329 : : {
2330 : 336719737 : for (l = v->locs; l; l = l->next)
2331 : 126205803 : if (REG_P (l->loc)
2332 : 126205803 : || (GET_CODE (l->loc) != VALUE
2333 : 60855064 : && !refs_newer_value_p (l->loc, x)))
2334 : 6247376 : return l->loc;
2335 : : /* Return the canonical value. */
2336 : 210513934 : return v->val_rtx;
2337 : : }
2338 : 84096383 : if (v->locs)
2339 : 46632665 : return v->locs->loc;
2340 : : }
2341 : : return x;
2342 : : }
2343 : :
2344 : : /* Return the address of the (N_REFS + 1)th memory reference to ADDR
2345 : : where SIZE is the size in bytes of the memory reference. If ADDR
2346 : : is not modified by the memory reference then ADDR is returned. */
2347 : :
2348 : : static rtx
2349 : 5115558560 : addr_side_effect_eval (rtx addr, poly_int64 size, int n_refs)
2350 : : {
2351 : 5115558560 : poly_int64 offset = 0;
2352 : :
2353 : 5115558560 : switch (GET_CODE (addr))
2354 : : {
2355 : 0 : case PRE_INC:
2356 : 0 : offset = (n_refs + 1) * size;
2357 : 0 : break;
2358 : 21159815 : case PRE_DEC:
2359 : 21159815 : offset = -(n_refs + 1) * size;
2360 : 21159815 : break;
2361 : : case POST_INC:
2362 : 568174 : offset = n_refs * size;
2363 : 568174 : break;
2364 : 0 : case POST_DEC:
2365 : 0 : offset = -n_refs * size;
2366 : 0 : break;
2367 : :
2368 : : default:
2369 : : return addr;
2370 : : }
2371 : :
2372 : 21727989 : addr = plus_constant (GET_MODE (addr), XEXP (addr, 0), offset);
2373 : 21727989 : addr = canon_rtx (addr);
2374 : :
2375 : 21727989 : return addr;
2376 : : }
2377 : :
2378 : : /* Return TRUE if an object X sized at XSIZE bytes and another object
2379 : : Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
2380 : : any of the sizes is zero, assume an overlap, otherwise use the
2381 : : absolute value of the sizes as the actual sizes. */
2382 : :
2383 : : static inline bool
2384 : 783778574 : offset_overlap_p (poly_int64 c, poly_int64 xsize, poly_int64 ysize)
2385 : : {
2386 : 783117690 : if (known_eq (xsize, 0) || known_eq (ysize, 0))
2387 : : return true;
2388 : :
2389 : 782992435 : if (maybe_ge (c, 0))
2390 : 473562801 : return maybe_gt (maybe_lt (xsize, 0) ? -xsize : xsize, c);
2391 : : else
2392 : 309429634 : return maybe_gt (maybe_lt (ysize, 0) ? -ysize : ysize, -c);
2393 : : }
2394 : :
2395 : : /* Return one if X and Y (memory addresses) reference the
2396 : : same location in memory or if the references overlap.
2397 : : Return zero if they do not overlap, else return
2398 : : minus one in which case they still might reference the same location.
2399 : :
2400 : : C is an offset accumulator. When
2401 : : C is nonzero, we are testing aliases between X and Y + C.
2402 : : XSIZE is the size in bytes of the X reference,
2403 : : similarly YSIZE is the size in bytes for Y.
2404 : : Expect that canon_rtx has been already called for X and Y.
2405 : :
2406 : : If XSIZE or YSIZE is zero, we do not know the amount of memory being
2407 : : referenced (the reference was BLKmode), so make the most pessimistic
2408 : : assumptions.
2409 : :
2410 : : If XSIZE or YSIZE is negative, we may access memory outside the object
2411 : : being referenced as a side effect. This can happen when using AND to
2412 : : align memory references, as is done on the Alpha.
2413 : :
2414 : : Nice to notice that varying addresses cannot conflict with fp if no
2415 : : local variables had their addresses taken, but that's too hard now.
2416 : :
2417 : : ??? Contrary to the tree alias oracle this does not return
2418 : : one for X + non-constant and Y + non-constant when X and Y are equal.
2419 : : If that is fixed the TBAA hack for union type-punning can be removed. */
2420 : :
2421 : : static int
2422 : 1774018913 : memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y,
2423 : : poly_int64 c)
2424 : : {
2425 : 2557779280 : if (GET_CODE (x) == VALUE)
2426 : : {
2427 : 719030597 : if (REG_P (y))
2428 : : {
2429 : 271307528 : struct elt_loc_list *l = NULL;
2430 : 271307528 : if (CSELIB_VAL_PTR (x))
2431 : 271307528 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs;
2432 : 500433137 : l; l = l->next)
2433 : 360264325 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y))
2434 : : break;
2435 : 271307528 : if (l)
2436 : : x = y;
2437 : : else
2438 : 140168812 : x = get_addr (x);
2439 : : }
2440 : : /* Don't call get_addr if y is the same VALUE. */
2441 : 447723069 : else if (x != y)
2442 : 447649349 : x = get_addr (x);
2443 : : }
2444 : 2557779280 : if (GET_CODE (y) == VALUE)
2445 : : {
2446 : 418588644 : if (REG_P (x))
2447 : : {
2448 : 12918777 : struct elt_loc_list *l = NULL;
2449 : 12918777 : if (CSELIB_VAL_PTR (y))
2450 : 12918777 : for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs;
2451 : 15053352 : l; l = l->next)
2452 : 2147901 : if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x))
2453 : : break;
2454 : 12918777 : if (l)
2455 : : y = x;
2456 : : else
2457 : 12905451 : y = get_addr (y);
2458 : : }
2459 : : /* Don't call get_addr if x is the same VALUE. */
2460 : 405669867 : else if (y != x)
2461 : 405595685 : y = get_addr (y);
2462 : : }
2463 : 2557779280 : if (GET_CODE (x) == HIGH)
2464 : 0 : x = XEXP (x, 0);
2465 : 2557779280 : else if (GET_CODE (x) == LO_SUM)
2466 : 0 : x = XEXP (x, 1);
2467 : : else
2468 : 2557779280 : x = addr_side_effect_eval (x, maybe_lt (xsize, 0) ? -xsize : xsize, 0);
2469 : 2557779280 : if (GET_CODE (y) == HIGH)
2470 : 0 : y = XEXP (y, 0);
2471 : 2557779280 : else if (GET_CODE (y) == LO_SUM)
2472 : 0 : y = XEXP (y, 1);
2473 : : else
2474 : 2557779280 : y = addr_side_effect_eval (y, maybe_lt (ysize, 0) ? -ysize : ysize, 0);
2475 : :
2476 : 2557779280 : if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF)
2477 : : {
2478 : 493323 : HOST_WIDE_INT distance = 0;
2479 : 493323 : int cmp = compare_base_symbol_refs (x, y, &distance);
2480 : :
2481 : : /* If both decls are the same, decide by offsets. */
2482 : 493323 : if (cmp == 1)
2483 : 709747 : return offset_overlap_p (c + distance, xsize, ysize);
2484 : : /* Assume a potential overlap for symbolic addresses that went
2485 : : through alignment adjustments (i.e., that have negative
2486 : : sizes), because we can't know how far they are from each
2487 : : other. */
2488 : 138353 : if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0))
2489 : : return -1;
2490 : : /* If decls are different or we know by offsets that there is no overlap,
2491 : : we win. */
2492 : 631676 : if (!cmp || !offset_overlap_p (c + distance, xsize, ysize))
2493 : 138353 : return 0;
2494 : : /* Decls may or may not be different and offsets overlap....*/
2495 : : return -1;
2496 : : }
2497 : 2557285957 : else if (rtx_equal_for_memref_p (x, y))
2498 : : {
2499 : 284930734 : return offset_overlap_p (c, xsize, ysize);
2500 : : }
2501 : :
2502 : : /* This code used to check for conflicts involving stack references and
2503 : : globals but the base address alias code now handles these cases. */
2504 : :
2505 : 2414799249 : if (GET_CODE (x) == PLUS)
2506 : : {
2507 : : /* The fact that X is canonicalized means that this
2508 : : PLUS rtx is canonicalized. */
2509 : 1447816073 : rtx x0 = XEXP (x, 0);
2510 : 1447816073 : rtx x1 = XEXP (x, 1);
2511 : :
2512 : : /* However, VALUEs might end up in different positions even in
2513 : : canonical PLUSes. Comparing their addresses is enough. */
2514 : 1447816073 : if (x0 == y)
2515 : 21548885 : return memrefs_conflict_p (xsize, x1, ysize, const0_rtx, c);
2516 : 1426267188 : else if (x1 == y)
2517 : 315864 : return memrefs_conflict_p (xsize, x0, ysize, const0_rtx, c);
2518 : :
2519 : 1425951324 : poly_int64 cx1, cy1;
2520 : 1425951324 : if (GET_CODE (y) == PLUS)
2521 : : {
2522 : : /* The fact that Y is canonicalized means that this
2523 : : PLUS rtx is canonicalized. */
2524 : 1291884107 : rtx y0 = XEXP (y, 0);
2525 : 1291884107 : rtx y1 = XEXP (y, 1);
2526 : :
2527 : 1291884107 : if (x0 == y1)
2528 : : return memrefs_conflict_p (xsize, x1, ysize, y0, c);
2529 : 1291833597 : if (x1 == y0)
2530 : : return memrefs_conflict_p (xsize, x0, ysize, y1, c);
2531 : :
2532 : 1291782459 : if (rtx_equal_for_memref_p (x1, y1))
2533 : : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2534 : 1156708502 : if (rtx_equal_for_memref_p (x0, y0))
2535 : : return memrefs_conflict_p (xsize, x1, ysize, y1, c);
2536 : 543874438 : if (poly_int_rtx_p (x1, &cx1))
2537 : : {
2538 : 1055466440 : poly_offset_int co = c;
2539 : 527733220 : co -= cx1;
2540 : 527733220 : if (poly_int_rtx_p (y1, &cy1))
2541 : : {
2542 : 520551748 : co += cy1;
2543 : 520551748 : if (!co.to_shwi (&c))
2544 : : return -1;
2545 : 520548837 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2546 : : }
2547 : 7181472 : else if (!co.to_shwi (&c))
2548 : : return -1;
2549 : : else
2550 : 7181472 : return memrefs_conflict_p (xsize, x0, ysize, y, c);
2551 : : }
2552 : 664282469 : else if (poly_int_rtx_p (y1, &cy1))
2553 : : {
2554 : 26232958 : poly_offset_int co = c;
2555 : 13116479 : co += cy1;
2556 : 13116479 : if (!co.to_shwi (&c))
2557 : : return -1;
2558 : 13116479 : return memrefs_conflict_p (xsize, x, ysize, y0, c);
2559 : : }
2560 : :
2561 : : return -1;
2562 : : }
2563 : 134067217 : else if (poly_int_rtx_p (x1, &cx1))
2564 : : {
2565 : 214583104 : poly_offset_int co = c;
2566 : 107291552 : co -= cx1;
2567 : 107291552 : if (!co.to_shwi (&c))
2568 : : return -1;
2569 : 107291543 : return memrefs_conflict_p (xsize, x0, ysize, y, c);
2570 : : }
2571 : : }
2572 : 966983176 : else if (GET_CODE (y) == PLUS)
2573 : : {
2574 : : /* The fact that Y is canonicalized means that this
2575 : : PLUS rtx is canonicalized. */
2576 : 75931236 : rtx y0 = XEXP (y, 0);
2577 : 75931236 : rtx y1 = XEXP (y, 1);
2578 : :
2579 : 75931236 : if (x == y0)
2580 : 8052116 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y1, c);
2581 : 67879120 : if (x == y1)
2582 : 774960 : return memrefs_conflict_p (xsize, const0_rtx, ysize, y0, c);
2583 : :
2584 : 67104160 : poly_int64 cy1;
2585 : 120238086 : if (poly_int_rtx_p (y1, &cy1))
2586 : : {
2587 : 106267852 : poly_offset_int co = c;
2588 : 53133926 : co += cy1;
2589 : 53133926 : if (!co.to_shwi (&c))
2590 : : return -1;
2591 : 53133926 : return memrefs_conflict_p (xsize, x, ysize, y0, c);
2592 : : }
2593 : : else
2594 : : return -1;
2595 : : }
2596 : :
2597 : 917827605 : if (GET_CODE (x) == GET_CODE (y))
2598 : 744477539 : switch (GET_CODE (x))
2599 : : {
2600 : 305788 : case MULT:
2601 : 305788 : {
2602 : : /* Handle cases where we expect the second operands to be the
2603 : : same, and check only whether the first operand would conflict
2604 : : or not. */
2605 : 305788 : rtx x0, y0;
2606 : 305788 : rtx x1 = canon_rtx (XEXP (x, 1));
2607 : 305788 : rtx y1 = canon_rtx (XEXP (y, 1));
2608 : 305788 : if (! rtx_equal_for_memref_p (x1, y1))
2609 : : return -1;
2610 : 288725 : x0 = canon_rtx (XEXP (x, 0));
2611 : 288725 : y0 = canon_rtx (XEXP (y, 0));
2612 : 288725 : if (rtx_equal_for_memref_p (x0, y0))
2613 : 0 : return offset_overlap_p (c, xsize, ysize);
2614 : :
2615 : : /* Can't properly adjust our sizes. */
2616 : 288725 : poly_int64 c1;
2617 : 254619342 : if (!poly_int_rtx_p (x1, &c1)
2618 : 285989 : || !can_div_trunc_p (xsize, c1, &xsize)
2619 : 285989 : || !can_div_trunc_p (ysize, c1, &ysize)
2620 : 285989 : || !can_div_trunc_p (c, c1, &c))
2621 : : return -1;
2622 : 285989 : return memrefs_conflict_p (xsize, x0, ysize, y0, c);
2623 : : }
2624 : :
2625 : : default:
2626 : : break;
2627 : : }
2628 : :
2629 : : /* Deal with alignment ANDs by adjusting offset and size so as to
2630 : : cover the maximum range, without taking any previously known
2631 : : alignment into account. Make a size negative after such an
2632 : : adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2633 : : assume a potential overlap, because they may end up in contiguous
2634 : : memory locations and the stricter-alignment access may span over
2635 : : part of both. */
2636 : 917521817 : if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
2637 : : {
2638 : 4044323 : HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
2639 : 4044323 : unsigned HOST_WIDE_INT uc = sc;
2640 : 4044323 : if (sc < 0 && pow2_or_zerop (-uc))
2641 : : {
2642 : 4043905 : if (maybe_gt (xsize, 0))
2643 : 4042976 : xsize = -xsize;
2644 : 4043905 : if (maybe_ne (xsize, 0))
2645 : : {
2646 : 4043020 : poly_offset_int xsizeo = xsize;
2647 : 4043020 : xsizeo += sc + 1;
2648 : 4043020 : if (!xsizeo.to_shwi (&xsize))
2649 : 0 : return -1;
2650 : : }
2651 : 4043905 : poly_offset_int co = c;
2652 : 4043905 : co -= sc + 1;
2653 : 4043905 : if (!co.to_shwi (&c))
2654 : : return -1;
2655 : 4043905 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2656 : 4043905 : ysize, y, c);
2657 : : }
2658 : : }
2659 : 913477912 : if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
2660 : : {
2661 : 5130316 : HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
2662 : 5130316 : unsigned HOST_WIDE_INT uc = sc;
2663 : 5130316 : if (sc < 0 && pow2_or_zerop (-uc))
2664 : : {
2665 : 5127196 : if (maybe_gt (ysize, 0))
2666 : 5127050 : ysize = -ysize;
2667 : 5127196 : if (maybe_ne (ysize, 0))
2668 : : {
2669 : 5127163 : poly_offset_int ysizeo = ysize;
2670 : 5127163 : ysizeo += sc + 1;
2671 : 5127163 : if (!ysizeo.to_shwi (&ysize))
2672 : 0 : return -1;
2673 : : }
2674 : 5127196 : poly_offset_int co = c;
2675 : 5127196 : co += sc + 1;
2676 : 5127196 : if (!co.to_shwi (&c))
2677 : : return -1;
2678 : 5127196 : return memrefs_conflict_p (xsize, x,
2679 : 5127196 : ysize, canon_rtx (XEXP (y, 0)), c);
2680 : : }
2681 : : }
2682 : :
2683 : 908350716 : if (CONSTANT_P (x))
2684 : : {
2685 : 654037162 : poly_int64 cx, cy;
2686 : 654037162 : if (poly_int_rtx_p (x, &cx) && poly_int_rtx_p (y, &cy))
2687 : : {
2688 : 1922339958 : poly_offset_int co = c;
2689 : 640779986 : co += cy;
2690 : 640779986 : co -= cx;
2691 : 640779986 : if (!co.to_shwi (&c))
2692 : : return -1;
2693 : 1280941706 : return offset_overlap_p (c, xsize, ysize);
2694 : : }
2695 : :
2696 : 13257176 : if (GET_CODE (x) == CONST)
2697 : : {
2698 : 4054459 : if (GET_CODE (y) == CONST)
2699 : 3186503 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2700 : 3186503 : ysize, canon_rtx (XEXP (y, 0)), c);
2701 : : else
2702 : 867956 : return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
2703 : 867956 : ysize, y, c);
2704 : : }
2705 : 9202717 : if (GET_CODE (y) == CONST)
2706 : 718425 : return memrefs_conflict_p (xsize, x, ysize,
2707 : 718425 : canon_rtx (XEXP (y, 0)), c);
2708 : :
2709 : : /* Assume a potential overlap for symbolic addresses that went
2710 : : through alignment adjustments (i.e., that have negative
2711 : : sizes), because we can't know how far they are from each
2712 : : other. */
2713 : 8484292 : if (CONSTANT_P (y))
2714 : 11127 : return (maybe_lt (xsize, 0)
2715 : 11127 : || maybe_lt (ysize, 0)
2716 : 22254 : || offset_overlap_p (c, xsize, ysize));
2717 : :
2718 : : return -1;
2719 : : }
2720 : :
2721 : : return -1;
2722 : : }
2723 : :
2724 : : /* Functions to compute memory dependencies.
2725 : :
2726 : : Since we process the insns in execution order, we can build tables
2727 : : to keep track of what registers are fixed (and not aliased), what registers
2728 : : are varying in known ways, and what registers are varying in unknown
2729 : : ways.
2730 : :
2731 : : If both memory references are volatile, then there must always be a
2732 : : dependence between the two references, since their order cannot be
2733 : : changed. A volatile and non-volatile reference can be interchanged
2734 : : though.
2735 : :
2736 : : We also must allow AND addresses, because they may generate accesses
2737 : : outside the object being referenced. This is used to generate aligned
2738 : : addresses from unaligned addresses, for instance, the alpha
2739 : : storeqi_unaligned pattern. */
2740 : :
2741 : : /* Read dependence: X is read after read in MEM takes place. There can
2742 : : only be a dependence here if both reads are volatile, or if either is
2743 : : an explicit barrier. */
2744 : :
2745 : : bool
2746 : 29041387 : read_dependence (const_rtx mem, const_rtx x)
2747 : : {
2748 : 29041387 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2749 : : return true;
2750 : 28554926 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
2751 : 57095940 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2752 : 21457 : return true;
2753 : : return false;
2754 : : }
2755 : :
2756 : : /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2757 : :
2758 : : static tree
2759 : 64325150 : decl_for_component_ref (tree x)
2760 : : {
2761 : 87799603 : do
2762 : : {
2763 : 87799603 : x = TREE_OPERAND (x, 0);
2764 : : }
2765 : 87799603 : while (x && TREE_CODE (x) == COMPONENT_REF);
2766 : :
2767 : 64325150 : return x && DECL_P (x) ? x : NULL_TREE;
2768 : : }
2769 : :
2770 : : /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2771 : : for the offset of the field reference. *KNOWN_P says whether the
2772 : : offset is known. */
2773 : :
2774 : : static void
2775 : 12483951 : adjust_offset_for_component_ref (tree x, bool *known_p,
2776 : : poly_int64 *offset)
2777 : : {
2778 : 12483951 : if (!*known_p)
2779 : : return;
2780 : 16343629 : do
2781 : : {
2782 : 16343629 : tree xoffset = component_ref_field_offset (x);
2783 : 16343629 : tree field = TREE_OPERAND (x, 1);
2784 : 16343629 : if (!poly_int_tree_p (xoffset))
2785 : : {
2786 : 0 : *known_p = false;
2787 : 0 : return;
2788 : : }
2789 : :
2790 : 16343629 : poly_offset_int woffset
2791 : 16343629 : = (wi::to_poly_offset (xoffset)
2792 : 16343629 : + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field))
2793 : 32687258 : >> LOG2_BITS_PER_UNIT)
2794 : 16343629 : + *offset);
2795 : 16343629 : if (!woffset.to_shwi (offset))
2796 : : {
2797 : 0 : *known_p = false;
2798 : 0 : return;
2799 : : }
2800 : :
2801 : 16343629 : x = TREE_OPERAND (x, 0);
2802 : : }
2803 : 16343629 : while (x && TREE_CODE (x) == COMPONENT_REF);
2804 : : }
2805 : :
2806 : : /* Return true if we can determine the exprs corresponding to memrefs
2807 : : X and Y and they do not overlap.
2808 : : If LOOP_VARIANT is set, skip offset-based disambiguation */
2809 : :
2810 : : bool
2811 : 222064073 : nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant)
2812 : : {
2813 : 230472465 : tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y);
2814 : 222064073 : rtx rtlx, rtly;
2815 : 222064073 : rtx basex, basey;
2816 : 222064073 : bool moffsetx_known_p, moffsety_known_p;
2817 : 222064073 : poly_int64 moffsetx = 0, moffsety = 0;
2818 : 222064073 : poly_int64 offsetx = 0, offsety = 0, sizex, sizey;
2819 : :
2820 : : /* Unless both have exprs, we can't tell anything. */
2821 : 222064073 : if (exprx == 0 || expry == 0)
2822 : : return false;
2823 : :
2824 : : /* For spill-slot accesses make sure we have valid offsets. */
2825 : 193822222 : if ((exprx == get_spill_slot_decl (false)
2826 : 14866479 : && ! MEM_OFFSET_KNOWN_P (x))
2827 : 208688701 : || (expry == get_spill_slot_decl (false)
2828 : 23820189 : && ! MEM_OFFSET_KNOWN_P (y)))
2829 : 0 : return false;
2830 : :
2831 : : /* If the field reference test failed, look at the DECLs involved. */
2832 : 193822222 : moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
2833 : 193822222 : if (moffsetx_known_p)
2834 : 193574341 : moffsetx = MEM_OFFSET (x);
2835 : 193822222 : if (TREE_CODE (exprx) == COMPONENT_REF)
2836 : : {
2837 : 37975935 : tree t = decl_for_component_ref (exprx);
2838 : 37975935 : if (! t)
2839 : : return false;
2840 : 5256102 : adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx);
2841 : 5256102 : exprx = t;
2842 : : }
2843 : :
2844 : 161102389 : moffsety_known_p = MEM_OFFSET_KNOWN_P (y);
2845 : 161102389 : if (moffsety_known_p)
2846 : 159903305 : moffsety = MEM_OFFSET (y);
2847 : 161102389 : if (TREE_CODE (expry) == COMPONENT_REF)
2848 : : {
2849 : 26349215 : tree t = decl_for_component_ref (expry);
2850 : 26349215 : if (! t)
2851 : : return false;
2852 : 7227849 : adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety);
2853 : 7227849 : expry = t;
2854 : : }
2855 : :
2856 : 141981023 : if (! DECL_P (exprx) || ! DECL_P (expry))
2857 : : return false;
2858 : :
2859 : : /* If we refer to different gimple registers, or one gimple register
2860 : : and one non-gimple-register, we know they can't overlap. First,
2861 : : gimple registers don't have their addresses taken. Now, there
2862 : : could be more than one stack slot for (different versions of) the
2863 : : same gimple register, but we can presumably tell they don't
2864 : : overlap based on offsets from stack base addresses elsewhere.
2865 : : It's important that we don't proceed to DECL_RTL, because gimple
2866 : : registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be
2867 : : able to do anything about them since no SSA information will have
2868 : : remained to guide it. */
2869 : 13145902 : if (is_gimple_reg (exprx) || is_gimple_reg (expry))
2870 : 3872244 : return exprx != expry
2871 : 3872244 : || (moffsetx_known_p && moffsety_known_p
2872 : 291630 : && MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y)
2873 : 291630 : && !offset_overlap_p (moffsety - moffsetx,
2874 : 145815 : MEM_SIZE (x), MEM_SIZE (y)));
2875 : :
2876 : : /* With invalid code we can end up storing into the constant pool.
2877 : : Bail out to avoid ICEing when creating RTL for this.
2878 : : See gfortran.dg/lto/20091028-2_0.f90. */
2879 : 9273658 : if (TREE_CODE (exprx) == CONST_DECL
2880 : 9273658 : || TREE_CODE (expry) == CONST_DECL)
2881 : : return true;
2882 : :
2883 : : /* If one decl is known to be a function or label in a function and
2884 : : the other is some kind of data, they can't overlap. */
2885 : 9273658 : if ((TREE_CODE (exprx) == FUNCTION_DECL
2886 : 9273658 : || TREE_CODE (exprx) == LABEL_DECL)
2887 : : != (TREE_CODE (expry) == FUNCTION_DECL
2888 : 9273658 : || TREE_CODE (expry) == LABEL_DECL))
2889 : : return true;
2890 : :
2891 : : /* If either of the decls doesn't have DECL_RTL set (e.g. marked as
2892 : : living in multiple places), we can't tell anything. Exception
2893 : : are FUNCTION_DECLs for which we can create DECL_RTL on demand. */
2894 : 9101040 : if ((!DECL_RTL_SET_P (exprx) && TREE_CODE (exprx) != FUNCTION_DECL)
2895 : 18202080 : || (!DECL_RTL_SET_P (expry) && TREE_CODE (expry) != FUNCTION_DECL))
2896 : : return false;
2897 : :
2898 : 9101040 : rtlx = DECL_RTL (exprx);
2899 : 9101040 : rtly = DECL_RTL (expry);
2900 : :
2901 : : /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2902 : : can't overlap unless they are the same because we never reuse that part
2903 : : of the stack frame used for locals for spilled pseudos. */
2904 : 9100132 : if ((!MEM_P (rtlx) || !MEM_P (rtly))
2905 : 9138049 : && ! rtx_equal_p (rtlx, rtly))
2906 : : return true;
2907 : :
2908 : : /* If we have MEMs referring to different address spaces (which can
2909 : : potentially overlap), we cannot easily tell from the addresses
2910 : : whether the references overlap. */
2911 : 9063123 : if (MEM_P (rtlx) && MEM_P (rtly)
2912 : 18126581 : && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly))
2913 : : return false;
2914 : :
2915 : : /* Get the base and offsets of both decls. If either is a register, we
2916 : : know both are and are the same, so use that as the base. The only
2917 : : we can avoid overlap is if we can deduce that they are nonoverlapping
2918 : : pieces of that decl, which is very rare. */
2919 : 9063458 : basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx;
2920 : 9063458 : basex = strip_offset_and_add (basex, &offsetx);
2921 : :
2922 : 9063458 : basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly;
2923 : 9063458 : basey = strip_offset_and_add (basey, &offsety);
2924 : :
2925 : : /* If the bases are different, we know they do not overlap if both
2926 : : are constants or if one is a constant and the other a pointer into the
2927 : : stack frame. Otherwise a different base means we can't tell if they
2928 : : overlap or not. */
2929 : 9063458 : if (compare_base_decls (exprx, expry) == 0)
2930 : 7039960 : return ((CONSTANT_P (basex) && CONSTANT_P (basey))
2931 : 1945826 : || (CONSTANT_P (basex) && REG_P (basey)
2932 : 275635 : && REGNO_PTR_FRAME_P (REGNO (basey)))
2933 : 10382680 : || (CONSTANT_P (basey) && REG_P (basex)
2934 : 114308 : && REGNO_PTR_FRAME_P (REGNO (basex))));
2935 : :
2936 : : /* Offset based disambiguation not appropriate for loop invariant */
2937 : 353307 : if (loop_invariant)
2938 : : return false;
2939 : :
2940 : : /* Offset based disambiguation is OK even if we do not know that the
2941 : : declarations are necessarily different
2942 : : (i.e. compare_base_decls (exprx, expry) == -1) */
2943 : :
2944 : 353642 : sizex = (!MEM_P (rtlx) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx)))
2945 : 352972 : : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx)
2946 : : : -1);
2947 : 353642 : sizey = (!MEM_P (rtly) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly)))
2948 : 352972 : : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly)
2949 : : : -1);
2950 : :
2951 : : /* If we have an offset for either memref, it can update the values computed
2952 : : above. */
2953 : 353307 : if (moffsetx_known_p)
2954 : 353301 : offsetx += moffsetx, sizex -= moffsetx;
2955 : 353307 : if (moffsety_known_p)
2956 : 353291 : offsety += moffsety, sizey -= moffsety;
2957 : :
2958 : : /* If a memref has both a size and an offset, we can use the smaller size.
2959 : : We can't do this if the offset isn't known because we must view this
2960 : : memref as being anywhere inside the DECL's MEM. */
2961 : 353307 : if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p)
2962 : 353301 : sizex = MEM_SIZE (x);
2963 : 353307 : if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p)
2964 : 353291 : sizey = MEM_SIZE (y);
2965 : :
2966 : 353307 : return !ranges_maybe_overlap_p (offsetx, sizex, offsety, sizey);
2967 : : }
2968 : :
2969 : : /* Helper for true_dependence and canon_true_dependence.
2970 : : Checks for true dependence: X is read after store in MEM takes place.
2971 : :
2972 : : If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2973 : : NULL_RTX, and the canonical addresses of MEM and X are both computed
2974 : : here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2975 : :
2976 : : If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2977 : :
2978 : : Returns true if there is a true dependence, false otherwise. */
2979 : :
2980 : : static bool
2981 : 795091716 : true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
2982 : : const_rtx x, rtx x_addr, bool mem_canonicalized)
2983 : : {
2984 : 795091716 : rtx true_mem_addr;
2985 : 795091716 : rtx base;
2986 : 795091716 : int ret;
2987 : :
2988 : 795091716 : gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX)
2989 : : : (mem_addr == NULL_RTX && x_addr == NULL_RTX));
2990 : :
2991 : 795091716 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
2992 : : return true;
2993 : :
2994 : : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2995 : : This is used in epilogue deallocation functions, and in cselib. */
2996 : 794427315 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
2997 : : return true;
2998 : 794406334 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
2999 : : return true;
3000 : 788870429 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3001 : 1577714177 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3002 : : return true;
3003 : :
3004 : 785912429 : if (! x_addr)
3005 : 47092218 : x_addr = XEXP (x, 0);
3006 : 785912429 : x_addr = get_addr (x_addr);
3007 : :
3008 : 785912429 : if (! mem_addr)
3009 : : {
3010 : 38569582 : mem_addr = XEXP (mem, 0);
3011 : 38569582 : if (mem_mode == VOIDmode)
3012 : 19787210 : mem_mode = GET_MODE (mem);
3013 : : }
3014 : 785912429 : true_mem_addr = get_addr (mem_addr);
3015 : :
3016 : : /* Read-only memory is by definition never modified, and therefore can't
3017 : : conflict with anything. However, don't assume anything when AND
3018 : : addresses are involved and leave to the code below to determine
3019 : : dependence. We don't expect to find read-only set on MEM, but
3020 : : stupid user tricks can produce them, so don't die. */
3021 : 785912429 : if (MEM_READONLY_P (x)
3022 : 4156421 : && GET_CODE (x_addr) != AND
3023 : 790068850 : && GET_CODE (true_mem_addr) != AND)
3024 : : return false;
3025 : :
3026 : : /* If we have MEMs referring to different address spaces (which can
3027 : : potentially overlap), we cannot easily tell from the addresses
3028 : : whether the references overlap. */
3029 : 815110077 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3030 : : return true;
3031 : :
3032 : 781688518 : base = find_base_term (x_addr);
3033 : 781688518 : if (base && (GET_CODE (base) == LABEL_REF
3034 : 676925238 : || (GET_CODE (base) == SYMBOL_REF
3035 : 58550760 : && CONSTANT_POOL_ADDRESS_P (base))))
3036 : : return false;
3037 : :
3038 : 781687626 : rtx mem_base = find_base_term (true_mem_addr);
3039 : 781687626 : if (! base_alias_check (x_addr, base, true_mem_addr, mem_base,
3040 : 781687626 : GET_MODE (x), mem_mode))
3041 : : return false;
3042 : :
3043 : 706024585 : x_addr = canon_rtx (x_addr);
3044 : 706024585 : if (!mem_canonicalized)
3045 : 27078974 : mem_addr = canon_rtx (true_mem_addr);
3046 : :
3047 : 1412049170 : if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
3048 : 1412049170 : SIZE_FOR_MODE (x), x_addr, 0)) != -1)
3049 : 489136060 : return !!ret;
3050 : :
3051 : 216888525 : if (mems_in_disjoint_alias_sets_p (x, mem))
3052 : : return false;
3053 : :
3054 : 159148155 : if (nonoverlapping_memrefs_p (mem, x, false))
3055 : : return false;
3056 : :
3057 : 150826261 : return rtx_refs_may_alias_p (x, mem, true);
3058 : : }
3059 : :
3060 : : /* True dependence: X is read after store in MEM takes place. */
3061 : :
3062 : : bool
3063 : 41366164 : true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x)
3064 : : {
3065 : 41366164 : return true_dependence_1 (mem, mem_mode, NULL_RTX,
3066 : 41366164 : x, NULL_RTX, /*mem_canonicalized=*/false);
3067 : : }
3068 : :
3069 : : /* Canonical true dependence: X is read after store in MEM takes place.
3070 : : Variant of true_dependence which assumes MEM has already been
3071 : : canonicalized (hence we no longer do that here).
3072 : : The mem_addr argument has been added, since true_dependence_1 computed
3073 : : this value prior to canonicalizing. */
3074 : :
3075 : : bool
3076 : 753725552 : canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
3077 : : const_rtx x, rtx x_addr)
3078 : : {
3079 : 753725552 : return true_dependence_1 (mem, mem_mode, mem_addr,
3080 : 753725552 : x, x_addr, /*mem_canonicalized=*/true);
3081 : : }
3082 : :
3083 : : /* Returns true if a write to X might alias a previous read from
3084 : : (or, if WRITEP is true, a write to) MEM.
3085 : : If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
3086 : : and X_MODE the mode for that access.
3087 : : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3088 : :
3089 : : static bool
3090 : 450751360 : write_dependence_p (const_rtx mem,
3091 : : const_rtx x, machine_mode x_mode, rtx x_addr,
3092 : : bool mem_canonicalized, bool x_canonicalized, bool writep)
3093 : : {
3094 : 450751360 : rtx mem_addr;
3095 : 450751360 : rtx true_mem_addr, true_x_addr;
3096 : 450751360 : rtx base;
3097 : 450751360 : int ret;
3098 : :
3099 : 450751360 : gcc_checking_assert (x_canonicalized
3100 : : ? (x_addr != NULL_RTX
3101 : : && (x_mode != VOIDmode || GET_MODE (x) == VOIDmode))
3102 : : : (x_addr == NULL_RTX && x_mode == VOIDmode));
3103 : :
3104 : 450751360 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3105 : : return true;
3106 : :
3107 : : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3108 : : This is used in epilogue deallocation functions. */
3109 : 450190383 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3110 : : return true;
3111 : 424855785 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3112 : : return true;
3113 : 423834906 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3114 : 847464248 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3115 : : return true;
3116 : :
3117 : 423610382 : if (!x_addr)
3118 : 49111658 : x_addr = XEXP (x, 0);
3119 : 423610382 : true_x_addr = get_addr (x_addr);
3120 : :
3121 : 423610382 : mem_addr = XEXP (mem, 0);
3122 : 423610382 : true_mem_addr = get_addr (mem_addr);
3123 : :
3124 : : /* A read from read-only memory can't conflict with read-write memory.
3125 : : Don't assume anything when AND addresses are involved and leave to
3126 : : the code below to determine dependence. */
3127 : 423610382 : if (!writep
3128 : 392390136 : && MEM_READONLY_P (mem)
3129 : 11319781 : && GET_CODE (true_x_addr) != AND
3130 : 434930163 : && GET_CODE (true_mem_addr) != AND)
3131 : : return false;
3132 : :
3133 : : /* If we have MEMs referring to different address spaces (which can
3134 : : potentially overlap), we cannot easily tell from the addresses
3135 : : whether the references overlap. */
3136 : 423815870 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3137 : : return true;
3138 : :
3139 : 412258015 : base = find_base_term (true_mem_addr);
3140 : 412258015 : if (! writep
3141 : 412258015 : && base
3142 : 412258015 : && (GET_CODE (base) == LABEL_REF
3143 : 327088656 : || (GET_CODE (base) == SYMBOL_REF
3144 : 28530692 : && CONSTANT_POOL_ADDRESS_P (base))))
3145 : : return false;
3146 : :
3147 : 412257257 : rtx x_base = find_base_term (true_x_addr);
3148 : 412257257 : if (! base_alias_check (true_x_addr, x_base, true_mem_addr, base,
3149 : 412257257 : GET_MODE (x), GET_MODE (mem)))
3150 : : return false;
3151 : :
3152 : 357550970 : if (!x_canonicalized)
3153 : : {
3154 : 43722762 : x_addr = canon_rtx (true_x_addr);
3155 : 43722762 : x_mode = GET_MODE (x);
3156 : : }
3157 : 357550970 : if (!mem_canonicalized)
3158 : 211643085 : mem_addr = canon_rtx (true_mem_addr);
3159 : :
3160 : 715101940 : if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
3161 : 715101940 : GET_MODE_SIZE (x_mode), x_addr, 0)) != -1)
3162 : 294635052 : return !!ret;
3163 : :
3164 : 62915918 : if (nonoverlapping_memrefs_p (x, mem, false))
3165 : : return false;
3166 : :
3167 : 59756228 : return rtx_refs_may_alias_p (x, mem, false);
3168 : : }
3169 : :
3170 : : /* Anti dependence: X is written after read in MEM takes place. */
3171 : :
3172 : : bool
3173 : 21902650 : anti_dependence (const_rtx mem, const_rtx x)
3174 : : {
3175 : 21902650 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3176 : : /*mem_canonicalized=*/false,
3177 : 21902650 : /*x_canonicalized*/false, /*writep=*/false);
3178 : : }
3179 : :
3180 : : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3181 : : Also, consider X in X_MODE (which might be from an enclosing
3182 : : STRICT_LOW_PART / ZERO_EXTRACT).
3183 : : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3184 : :
3185 : : bool
3186 : 395370181 : canon_anti_dependence (const_rtx mem, bool mem_canonicalized,
3187 : : const_rtx x, machine_mode x_mode, rtx x_addr)
3188 : : {
3189 : 395370181 : return write_dependence_p (mem, x, x_mode, x_addr,
3190 : : mem_canonicalized, /*x_canonicalized=*/true,
3191 : 395370181 : /*writep=*/false);
3192 : : }
3193 : :
3194 : : /* Output dependence: X is written after store in MEM takes place. */
3195 : :
3196 : : bool
3197 : 30280584 : output_dependence (const_rtx mem, const_rtx x)
3198 : : {
3199 : 30280584 : return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
3200 : : /*mem_canonicalized=*/false,
3201 : 30280584 : /*x_canonicalized*/false, /*writep=*/true);
3202 : : }
3203 : :
3204 : : /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
3205 : : Also, consider X in X_MODE (which might be from an enclosing
3206 : : STRICT_LOW_PART / ZERO_EXTRACT).
3207 : : If MEM_CANONICALIZED is true, MEM is canonicalized. */
3208 : :
3209 : : bool
3210 : 3197945 : canon_output_dependence (const_rtx mem, bool mem_canonicalized,
3211 : : const_rtx x, machine_mode x_mode, rtx x_addr)
3212 : : {
3213 : 3197945 : return write_dependence_p (mem, x, x_mode, x_addr,
3214 : : mem_canonicalized, /*x_canonicalized=*/true,
3215 : 3197945 : /*writep=*/true);
3216 : : }
3217 : :
3218 : :
3219 : :
3220 : : /* Check whether X may be aliased with MEM. Don't do offset-based
3221 : : memory disambiguation & TBAA. */
3222 : : bool
3223 : 0 : may_alias_p (const_rtx mem, const_rtx x)
3224 : : {
3225 : 0 : rtx x_addr, mem_addr;
3226 : :
3227 : 0 : if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
3228 : : return true;
3229 : :
3230 : : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
3231 : : This is used in epilogue deallocation functions. */
3232 : 0 : if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
3233 : : return true;
3234 : 0 : if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
3235 : : return true;
3236 : 0 : if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
3237 : 0 : || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
3238 : : return true;
3239 : :
3240 : 0 : x_addr = XEXP (x, 0);
3241 : 0 : x_addr = get_addr (x_addr);
3242 : :
3243 : 0 : mem_addr = XEXP (mem, 0);
3244 : 0 : mem_addr = get_addr (mem_addr);
3245 : :
3246 : : /* Read-only memory is by definition never modified, and therefore can't
3247 : : conflict with anything. However, don't assume anything when AND
3248 : : addresses are involved and leave to the code below to determine
3249 : : dependence. We don't expect to find read-only set on MEM, but
3250 : : stupid user tricks can produce them, so don't die. */
3251 : 0 : if (MEM_READONLY_P (x)
3252 : 0 : && GET_CODE (x_addr) != AND
3253 : 0 : && GET_CODE (mem_addr) != AND)
3254 : : return false;
3255 : :
3256 : : /* If we have MEMs referring to different address spaces (which can
3257 : : potentially overlap), we cannot easily tell from the addresses
3258 : : whether the references overlap. */
3259 : 0 : if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
3260 : : return true;
3261 : :
3262 : 0 : rtx x_base = find_base_term (x_addr);
3263 : 0 : rtx mem_base = find_base_term (mem_addr);
3264 : 0 : if (! base_alias_check (x_addr, x_base, mem_addr, mem_base,
3265 : 0 : GET_MODE (x), GET_MODE (mem_addr)))
3266 : : return false;
3267 : :
3268 : 0 : if (nonoverlapping_memrefs_p (mem, x, true))
3269 : : return false;
3270 : :
3271 : : /* TBAA not valid for loop_invarint */
3272 : 0 : return rtx_refs_may_alias_p (x, mem, false);
3273 : : }
3274 : :
3275 : : void
3276 : 210346 : init_alias_target (void)
3277 : : {
3278 : 210346 : int i;
3279 : :
3280 : 210346 : if (!arg_base_value)
3281 : 206001 : arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0);
3282 : :
3283 : 210346 : memset (static_reg_base_value, 0, sizeof static_reg_base_value);
3284 : :
3285 : 19562178 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3286 : : /* Check whether this register can hold an incoming pointer
3287 : : argument. FUNCTION_ARG_REGNO_P tests outgoing register
3288 : : numbers, so translate if necessary due to register windows. */
3289 : 19351832 : if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
3290 : 19351832 : && targetm.hard_regno_mode_ok (i, Pmode))
3291 : 3116783 : static_reg_base_value[i] = arg_base_value;
3292 : :
3293 : : /* RTL code is required to be consistent about whether it uses the
3294 : : stack pointer, the frame pointer or the argument pointer to
3295 : : access a given area of the frame. We can therefore use the
3296 : : base address to distinguish between the different areas. */
3297 : 210346 : static_reg_base_value[STACK_POINTER_REGNUM]
3298 : 210346 : = unique_base_value (UNIQUE_BASE_VALUE_SP);
3299 : 210346 : static_reg_base_value[ARG_POINTER_REGNUM]
3300 : 210346 : = unique_base_value (UNIQUE_BASE_VALUE_ARGP);
3301 : 210346 : static_reg_base_value[FRAME_POINTER_REGNUM]
3302 : 210346 : = unique_base_value (UNIQUE_BASE_VALUE_FP);
3303 : :
3304 : : /* The above rules extend post-reload, with eliminations applying
3305 : : consistently to each of the three pointers. Cope with cases in
3306 : : which the frame pointer is eliminated to the hard frame pointer
3307 : : rather than the stack pointer. */
3308 : 210346 : if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3309 : 210346 : static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
3310 : 210346 : = unique_base_value (UNIQUE_BASE_VALUE_HFP);
3311 : 210346 : }
3312 : :
3313 : : /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
3314 : : to be memory reference. */
3315 : : static bool memory_modified;
3316 : : static void
3317 : 31731355 : memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3318 : : {
3319 : 31731355 : if (MEM_P (x))
3320 : : {
3321 : 2501208 : if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data))
3322 : 434924 : memory_modified = true;
3323 : : }
3324 : 31731355 : }
3325 : :
3326 : :
3327 : : /* Return true when INSN possibly modify memory contents of MEM
3328 : : (i.e. address can be modified). */
3329 : : bool
3330 : 42668761 : memory_modified_in_insn_p (const_rtx mem, const_rtx insn)
3331 : : {
3332 : 42668761 : if (!INSN_P (insn))
3333 : : return false;
3334 : : /* Conservatively assume all non-readonly MEMs might be modified in
3335 : : calls. */
3336 : 40103519 : if (CALL_P (insn))
3337 : : return true;
3338 : 39787249 : memory_modified = false;
3339 : 39787249 : note_stores (as_a<const rtx_insn *> (insn), memory_modified_1,
3340 : : CONST_CAST_RTX(mem));
3341 : 39787249 : return memory_modified;
3342 : : }
3343 : :
3344 : : /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
3345 : : array. */
3346 : :
3347 : : void
3348 : 9118535 : init_alias_analysis (void)
3349 : : {
3350 : 9118535 : const bool frame_pointer_eliminated
3351 : 9118535 : = reload_completed
3352 : 3963461 : && !frame_pointer_needed
3353 : 12843904 : && targetm.can_eliminate (FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM);
3354 : 9118535 : unsigned int maxreg = max_reg_num ();
3355 : 9118535 : bool changed;
3356 : 9118535 : int pass, i;
3357 : 9118535 : unsigned int ui;
3358 : 9118535 : rtx_insn *insn;
3359 : 9118535 : rtx val;
3360 : 9118535 : int rpo_cnt;
3361 : 9118535 : int *rpo;
3362 : :
3363 : 9118535 : timevar_push (TV_ALIAS_ANALYSIS);
3364 : :
3365 : 9118535 : vec_safe_grow_cleared (reg_known_value, maxreg - FIRST_PSEUDO_REGISTER,
3366 : : true);
3367 : 9118535 : reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
3368 : 9118535 : bitmap_clear (reg_known_equiv_p);
3369 : :
3370 : : /* If we have memory allocated from the previous run, use it. */
3371 : 9118535 : if (old_reg_base_value)
3372 : 8870872 : reg_base_value = old_reg_base_value;
3373 : :
3374 : 9118535 : if (reg_base_value)
3375 : 8912720 : reg_base_value->truncate (0);
3376 : :
3377 : 9118535 : vec_safe_grow_cleared (reg_base_value, maxreg, true);
3378 : :
3379 : 9118535 : new_reg_base_value = XNEWVEC (rtx, maxreg);
3380 : 9118535 : reg_seen = sbitmap_alloc (maxreg);
3381 : :
3382 : : /* The basic idea is that each pass through this loop will use the
3383 : : "constant" information from the previous pass to propagate alias
3384 : : information through another level of assignments.
3385 : :
3386 : : The propagation is done on the CFG in reverse post-order, to propagate
3387 : : things forward as far as possible in each iteration.
3388 : :
3389 : : This could get expensive if the assignment chains are long. Maybe
3390 : : we should throttle the number of iterations, possibly based on
3391 : : the optimization level or flag_expensive_optimizations.
3392 : :
3393 : : We could propagate more information in the first pass by making use
3394 : : of DF_REG_DEF_COUNT to determine immediately that the alias information
3395 : : for a pseudo is "constant".
3396 : :
3397 : : A program with an uninitialized variable can cause an infinite loop
3398 : : here. Instead of doing a full dataflow analysis to detect such problems
3399 : : we just cap the number of iterations for the loop.
3400 : :
3401 : : The state of the arrays for the set chain in question does not matter
3402 : : since the program has undefined behavior. */
3403 : :
3404 : 9118535 : rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3405 : 9118535 : rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
3406 : :
3407 : 9118535 : pass = 0;
3408 : 18494206 : do
3409 : : {
3410 : : /* Assume nothing will change this iteration of the loop. */
3411 : 18494206 : changed = false;
3412 : :
3413 : : /* We want to assign the same IDs each iteration of this loop, so
3414 : : start counting from one each iteration of the loop. */
3415 : 18494206 : unique_id = 1;
3416 : :
3417 : : /* We're at the start of the function each iteration through the
3418 : : loop, so we're copying arguments. */
3419 : 18494206 : copying_arguments = true;
3420 : :
3421 : : /* Wipe the potential alias information clean for this pass. */
3422 : 18494206 : memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
3423 : :
3424 : : /* Wipe the reg_seen array clean. */
3425 : 18494206 : bitmap_clear (reg_seen);
3426 : :
3427 : : /* Initialize the alias information for this pass. */
3428 : 1738455364 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3429 : 1701466952 : if (static_reg_base_value[i]
3430 : : /* Don't treat the hard frame pointer as special if we
3431 : : eliminated the frame pointer to the stack pointer. */
3432 : 337363047 : && !(i == HARD_FRAME_POINTER_REGNUM && frame_pointer_eliminated))
3433 : : {
3434 : 329889962 : new_reg_base_value[i] = static_reg_base_value[i];
3435 : 329889962 : bitmap_set_bit (reg_seen, i);
3436 : : }
3437 : :
3438 : : /* Walk the insns adding values to the new_reg_base_value array. */
3439 : 233327866 : for (i = 0; i < rpo_cnt; i++)
3440 : : {
3441 : 214833660 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
3442 : 2671471105 : FOR_BB_INSNS (bb, insn)
3443 : : {
3444 : 2456637445 : if (NONDEBUG_INSN_P (insn))
3445 : : {
3446 : 1201935263 : rtx note, set;
3447 : :
3448 : : /* Treat the hard frame pointer as special unless we
3449 : : eliminated the frame pointer to the stack pointer. */
3450 : 1202296592 : if (!frame_pointer_eliminated
3451 : 1201935263 : && modified_in_p (hard_frame_pointer_rtx, insn))
3452 : 361329 : continue;
3453 : :
3454 : : /* If this insn has a noalias note, process it, Otherwise,
3455 : : scan for sets. A simple set will have no side effects
3456 : : which could change the base value of any other register. */
3457 : 1201573934 : if (GET_CODE (PATTERN (insn)) == SET
3458 : 958333363 : && REG_NOTES (insn) != 0
3459 : 1696476335 : && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
3460 : 1062393 : record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
3461 : : else
3462 : 1200511541 : note_stores (insn, record_set, NULL);
3463 : :
3464 : 1201573934 : set = single_set (insn);
3465 : :
3466 : 1201573934 : if (set != 0
3467 : 1120993624 : && REG_P (SET_DEST (set))
3468 : 2012824189 : && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3469 : : {
3470 : 305295432 : unsigned int regno = REGNO (SET_DEST (set));
3471 : 305295432 : rtx src = SET_SRC (set);
3472 : 305295432 : rtx t;
3473 : :
3474 : 305295432 : note = find_reg_equal_equiv_note (insn);
3475 : 305295432 : if (note && REG_NOTE_KIND (note) == REG_EQUAL
3476 : 17503383 : && DF_REG_DEF_COUNT (regno) != 1)
3477 : : note = NULL_RTX;
3478 : :
3479 : : poly_int64 offset;
3480 : : if (note != NULL_RTX
3481 : 17280303 : && GET_CODE (XEXP (note, 0)) != EXPR_LIST
3482 : 17280303 : && ! rtx_varies_p (XEXP (note, 0), 1)
3483 : 7590056 : && ! reg_overlap_mentioned_p (SET_DEST (set),
3484 : 7590056 : XEXP (note, 0)))
3485 : : {
3486 : 7590056 : set_reg_known_value (regno, XEXP (note, 0));
3487 : 7590056 : set_reg_known_equiv_p (regno,
3488 : 7590056 : REG_NOTE_KIND (note) == REG_EQUIV);
3489 : : }
3490 : 297705376 : else if (DF_REG_DEF_COUNT (regno) == 1
3491 : 225536392 : && GET_CODE (src) == PLUS
3492 : 41612160 : && REG_P (XEXP (src, 0))
3493 : 40757759 : && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
3494 : 298852419 : && poly_int_rtx_p (XEXP (src, 1), &offset))
3495 : : {
3496 : 758901 : t = plus_constant (GET_MODE (src), t, offset);
3497 : 758901 : set_reg_known_value (regno, t);
3498 : 758901 : set_reg_known_equiv_p (regno, false);
3499 : : }
3500 : 296946475 : else if (DF_REG_DEF_COUNT (regno) == 1
3501 : 296946475 : && ! rtx_varies_p (src, 1))
3502 : : {
3503 : 31053453 : set_reg_known_value (regno, src);
3504 : 31053453 : set_reg_known_equiv_p (regno, false);
3505 : : }
3506 : : }
3507 : : }
3508 : 1254702182 : else if (NOTE_P (insn)
3509 : 292466637 : && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
3510 : 18483002 : copying_arguments = false;
3511 : : }
3512 : : }
3513 : :
3514 : : /* Now propagate values from new_reg_base_value to reg_base_value. */
3515 : 18494206 : gcc_assert (maxreg == (unsigned int) max_reg_num ());
3516 : :
3517 : 2719978190 : for (ui = 0; ui < maxreg; ui++)
3518 : : {
3519 : 2701483984 : if (new_reg_base_value[ui]
3520 : 322817970 : && new_reg_base_value[ui] != (*reg_base_value)[ui]
3521 : 2860102930 : && ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui]))
3522 : : {
3523 : 157940607 : (*reg_base_value)[ui] = new_reg_base_value[ui];
3524 : 157940607 : changed = true;
3525 : : }
3526 : : }
3527 : : }
3528 : 18494275 : while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
3529 : 9118535 : XDELETEVEC (rpo);
3530 : :
3531 : : /* Fill in the remaining entries. */
3532 : 487344656 : FOR_EACH_VEC_ELT (*reg_known_value, i, val)
3533 : : {
3534 : 478226121 : int regno = i + FIRST_PSEUDO_REGISTER;
3535 : 478226121 : if (! val)
3536 : 460294844 : set_reg_known_value (regno, regno_reg_rtx[regno]);
3537 : : }
3538 : :
3539 : : /* Clean up. */
3540 : 9118535 : free (new_reg_base_value);
3541 : 9118535 : new_reg_base_value = 0;
3542 : 9118535 : sbitmap_free (reg_seen);
3543 : 9118535 : reg_seen = 0;
3544 : 9118535 : timevar_pop (TV_ALIAS_ANALYSIS);
3545 : 9118535 : }
3546 : :
3547 : : /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3548 : : Special API for var-tracking pass purposes. */
3549 : :
3550 : : void
3551 : 480176 : vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
3552 : : {
3553 : 480176 : (*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2);
3554 : 480176 : }
3555 : :
3556 : : void
3557 : 9118535 : end_alias_analysis (void)
3558 : : {
3559 : 9118535 : old_reg_base_value = reg_base_value;
3560 : 9118535 : vec_free (reg_known_value);
3561 : 9118535 : sbitmap_free (reg_known_equiv_p);
3562 : 9118535 : }
3563 : :
3564 : : void
3565 : 0 : dump_alias_stats_in_alias_c (FILE *s)
3566 : : {
3567 : 0 : fprintf (s, " TBAA oracle: %llu disambiguations %llu queries\n"
3568 : : " %llu are in alias set 0\n"
3569 : : " %llu queries asked about the same object\n"
3570 : : " %llu queries asked about the same alias set\n"
3571 : : " %llu access volatile\n"
3572 : : " %llu are dependent in the DAG\n"
3573 : : " %llu are aritificially in conflict with void *\n",
3574 : : alias_stats.num_disambiguated,
3575 : 0 : alias_stats.num_alias_zero + alias_stats.num_same_alias_set
3576 : 0 : + alias_stats.num_same_objects + alias_stats.num_volatile
3577 : 0 : + alias_stats.num_dag + alias_stats.num_disambiguated
3578 : : + alias_stats.num_universal,
3579 : : alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
3580 : : alias_stats.num_same_objects, alias_stats.num_volatile,
3581 : : alias_stats.num_dag, alias_stats.num_universal);
3582 : 0 : }
3583 : : #include "gt-alias.h"
|
