1 /* Alias analysis for GNU C
2 Copyright (C) 1997-2014 Free Software Foundation, Inc.
3 Contributed by John Carr (jfc@mit.edu).
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
34 #include "hard-reg-set.h"
41 #include "diagnostic-core.h"
44 #include "langhooks.h"
48 #include "dominance.h"
52 #include "basic-block.h"
54 #include "tree-ssa-alias.h"
55 #include "internal-fn.h"
56 #include "gimple-expr.h"
59 #include "gimple-ssa.h"
62 /* The aliasing API provided here solves related but different problems:
64 Say there exists (in c)
78 Consider the four questions:
80 Can a store to x1 interfere with px2->y1?
81 Can a store to x1 interfere with px2->z2?
82 Can a store to x1 change the value pointed to by with py?
83 Can a store to x1 change the value pointed to by with pz?
85 The answer to these questions can be yes, yes, yes, and maybe.
87 The first two questions can be answered with a simple examination
88 of the type system. If structure X contains a field of type Y then
89 a store through a pointer to an X can overwrite any field that is
90 contained (recursively) in an X (unless we know that px1 != px2).
92 The last two questions can be solved in the same way as the first
93 two questions but this is too conservative. The observation is
94 that in some cases we can know which (if any) fields are addressed
95 and if those addresses are used in bad ways. This analysis may be
96 language specific. In C, arbitrary operations may be applied to
97 pointers. However, there is some indication that this may be too
98 conservative for some C++ types.
100 The pass ipa-type-escape does this analysis for the types whose
101 instances do not escape across the compilation boundary.
103 Historically in GCC, these two problems were combined and a single
104 data structure that was used to represent the solution to these
105 problems. We now have two similar but different data structures,
106 The data structure to solve the last two questions is similar to
107 the first, but does not contain the fields whose address are never
108 taken. For types that do escape the compilation unit, the data
109 structures will have identical information.
112 /* The alias sets assigned to MEMs assist the back-end in determining
113 which MEMs can alias which other MEMs. In general, two MEMs in
114 different alias sets cannot alias each other, with one important
115 exception. Consider something like:
117 struct S { int i; double d; };
119 a store to an `S' can alias something of either type `int' or type
120 `double'. (However, a store to an `int' cannot alias a `double'
121 and vice versa.) We indicate this via a tree structure that looks
129 (The arrows are directed and point downwards.)
130 In this situation we say the alias set for `struct S' is the
131 `superset' and that those for `int' and `double' are `subsets'.
133 To see whether two alias sets can point to the same memory, we must
134 see if either alias set is a subset of the other. We need not trace
135 past immediate descendants, however, since we propagate all
136 grandchildren up one level.
138 Alias set zero is implicitly a superset of all other alias sets.
139 However, this is no actual entry for alias set zero. It is an
140 error to attempt to explicitly construct a subset of zero. */
142 struct alias_set_traits
: default_hashmap_traits
148 return e
.m_key
== INT_MIN
;
155 return e
.m_key
== (INT_MIN
+ 1);
158 template<typename T
> static void mark_empty (T
&e
) { e
.m_key
= INT_MIN
; }
164 e
.m_key
= INT_MIN
+ 1;
168 struct GTY(()) alias_set_entry_d
{
169 /* The alias set number, as stored in MEM_ALIAS_SET. */
170 alias_set_type alias_set
;
172 /* Nonzero if would have a child of zero: this effectively makes this
173 alias set the same as alias set zero. */
176 /* The children of the alias set. These are not just the immediate
177 children, but, in fact, all descendants. So, if we have:
179 struct T { struct S s; float f; }
181 continuing our example above, the children here will be all of
182 `int', `double', `float', and `struct S'. */
183 hash_map
<int, int, alias_set_traits
> *children
;
185 typedef struct alias_set_entry_d
*alias_set_entry
;
187 static int rtx_equal_for_memref_p (const_rtx
, const_rtx
);
188 static int memrefs_conflict_p (int, rtx
, int, rtx
, HOST_WIDE_INT
);
189 static void record_set (rtx
, const_rtx
, void *);
190 static int base_alias_check (rtx
, rtx
, rtx
, rtx
, machine_mode
,
192 static rtx
find_base_value (rtx
);
193 static int mems_in_disjoint_alias_sets_p (const_rtx
, const_rtx
);
194 static alias_set_entry
get_alias_set_entry (alias_set_type
);
195 static tree
decl_for_component_ref (tree
);
196 static int write_dependence_p (const_rtx
,
197 const_rtx
, machine_mode
, rtx
,
200 static void memory_modified_1 (rtx
, const_rtx
, void *);
202 /* Set up all info needed to perform alias analysis on memory references. */
204 /* Returns the size in bytes of the mode of X. */
205 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
207 /* Cap the number of passes we make over the insns propagating alias
208 information through set chains.
209 ??? 10 is a completely arbitrary choice. This should be based on the
210 maximum loop depth in the CFG, but we do not have this information
211 available (even if current_loops _is_ available). */
212 #define MAX_ALIAS_LOOP_PASSES 10
214 /* reg_base_value[N] gives an address to which register N is related.
215 If all sets after the first add or subtract to the current value
216 or otherwise modify it so it does not point to a different top level
217 object, reg_base_value[N] is equal to the address part of the source
220 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS
221 expressions represent three types of base:
223 1. incoming arguments. There is just one ADDRESS to represent all
224 arguments, since we do not know at this level whether accesses
225 based on different arguments can alias. The ADDRESS has id 0.
227 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx
228 (if distinct from frame_pointer_rtx) and arg_pointer_rtx.
229 Each of these rtxes has a separate ADDRESS associated with it,
230 each with a negative id.
232 GCC is (and is required to be) precise in which register it
233 chooses to access a particular region of stack. We can therefore
234 assume that accesses based on one of these rtxes do not alias
235 accesses based on another of these rtxes.
237 3. bases that are derived from malloc()ed memory (REG_NOALIAS).
238 Each such piece of memory has a separate ADDRESS associated
239 with it, each with an id greater than 0.
241 Accesses based on one ADDRESS do not alias accesses based on other
242 ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not
243 alias globals either; the ADDRESSes have Pmode to indicate this.
244 The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
247 static GTY(()) vec
<rtx
, va_gc
> *reg_base_value
;
248 static rtx
*new_reg_base_value
;
250 /* The single VOIDmode ADDRESS that represents all argument bases.
252 static GTY(()) rtx arg_base_value
;
254 /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */
255 static int unique_id
;
257 /* We preserve the copy of old array around to avoid amount of garbage
258 produced. About 8% of garbage produced were attributed to this
260 static GTY((deletable
)) vec
<rtx
, va_gc
> *old_reg_base_value
;
262 /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
264 #define UNIQUE_BASE_VALUE_SP -1
265 #define UNIQUE_BASE_VALUE_ARGP -2
266 #define UNIQUE_BASE_VALUE_FP -3
267 #define UNIQUE_BASE_VALUE_HFP -4
269 #define static_reg_base_value \
270 (this_target_rtl->x_static_reg_base_value)
272 #define REG_BASE_VALUE(X) \
273 (REGNO (X) < vec_safe_length (reg_base_value) \
274 ? (*reg_base_value)[REGNO (X)] : 0)
276 /* Vector indexed by N giving the initial (unchanging) value known for
277 pseudo-register N. This vector is initialized in init_alias_analysis,
278 and does not change until end_alias_analysis is called. */
279 static GTY(()) vec
<rtx
, va_gc
> *reg_known_value
;
281 /* Vector recording for each reg_known_value whether it is due to a
282 REG_EQUIV note. Future passes (viz., reload) may replace the
283 pseudo with the equivalent expression and so we account for the
284 dependences that would be introduced if that happens.
286 The REG_EQUIV notes created in assign_parms may mention the arg
287 pointer, and there are explicit insns in the RTL that modify the
288 arg pointer. Thus we must ensure that such insns don't get
289 scheduled across each other because that would invalidate the
290 REG_EQUIV notes. One could argue that the REG_EQUIV notes are
291 wrong, but solving the problem in the scheduler will likely give
292 better code, so we do it here. */
293 static sbitmap reg_known_equiv_p
;
295 /* True when scanning insns from the start of the rtl to the
296 NOTE_INSN_FUNCTION_BEG note. */
297 static bool copying_arguments
;
300 /* The splay-tree used to store the various alias set entries. */
301 static GTY (()) vec
<alias_set_entry
, va_gc
> *alias_sets
;
303 /* Build a decomposed reference object for querying the alias-oracle
304 from the MEM rtx and store it in *REF.
305 Returns false if MEM is not suitable for the alias-oracle. */
308 ao_ref_from_mem (ao_ref
*ref
, const_rtx mem
)
310 tree expr
= MEM_EXPR (mem
);
316 ao_ref_init (ref
, expr
);
318 /* Get the base of the reference and see if we have to reject or
320 base
= ao_ref_base (ref
);
321 if (base
== NULL_TREE
)
324 /* The tree oracle doesn't like bases that are neither decls
325 nor indirect references of SSA names. */
327 || (TREE_CODE (base
) == MEM_REF
328 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
329 || (TREE_CODE (base
) == TARGET_MEM_REF
330 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)))
333 /* If this is a reference based on a partitioned decl replace the
334 base with a MEM_REF of the pointer representative we
335 created during stack slot partitioning. */
336 if (TREE_CODE (base
) == VAR_DECL
337 && ! is_global_var (base
)
338 && cfun
->gimple_df
->decls_to_pointers
!= NULL
)
340 tree
*namep
= cfun
->gimple_df
->decls_to_pointers
->get (base
);
342 ref
->base
= build_simple_mem_ref (*namep
);
345 ref
->ref_alias_set
= MEM_ALIAS_SET (mem
);
347 /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
348 is conservative, so trust it. */
349 if (!MEM_OFFSET_KNOWN_P (mem
)
350 || !MEM_SIZE_KNOWN_P (mem
))
353 /* If the base decl is a parameter we can have negative MEM_OFFSET in
354 case of promoted subregs on bigendian targets. Trust the MEM_EXPR
356 if (MEM_OFFSET (mem
) < 0
357 && (MEM_SIZE (mem
) + MEM_OFFSET (mem
)) * BITS_PER_UNIT
== ref
->size
)
360 /* Otherwise continue and refine size and offset we got from analyzing
361 MEM_EXPR by using MEM_SIZE and MEM_OFFSET. */
363 ref
->offset
+= MEM_OFFSET (mem
) * BITS_PER_UNIT
;
364 ref
->size
= MEM_SIZE (mem
) * BITS_PER_UNIT
;
366 /* The MEM may extend into adjacent fields, so adjust max_size if
368 if (ref
->max_size
!= -1
369 && ref
->size
> ref
->max_size
)
370 ref
->max_size
= ref
->size
;
372 /* If MEM_OFFSET and MEM_SIZE get us outside of the base object of
373 the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */
374 if (MEM_EXPR (mem
) != get_spill_slot_decl (false)
376 || (DECL_P (ref
->base
)
377 && (DECL_SIZE (ref
->base
) == NULL_TREE
378 || TREE_CODE (DECL_SIZE (ref
->base
)) != INTEGER_CST
379 || wi::ltu_p (wi::to_offset (DECL_SIZE (ref
->base
)),
380 ref
->offset
+ ref
->size
)))))
386 /* Query the alias-oracle on whether the two memory rtx X and MEM may
387 alias. If TBAA_P is set also apply TBAA. Returns true if the
388 two rtxen may alias, false otherwise. */
391 rtx_refs_may_alias_p (const_rtx x
, const_rtx mem
, bool tbaa_p
)
395 if (!ao_ref_from_mem (&ref1
, x
)
396 || !ao_ref_from_mem (&ref2
, mem
))
399 return refs_may_alias_p_1 (&ref1
, &ref2
,
401 && MEM_ALIAS_SET (x
) != 0
402 && MEM_ALIAS_SET (mem
) != 0);
405 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is
406 such an entry, or NULL otherwise. */
408 static inline alias_set_entry
409 get_alias_set_entry (alias_set_type alias_set
)
411 return (*alias_sets
)[alias_set
];
414 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
415 the two MEMs cannot alias each other. */
418 mems_in_disjoint_alias_sets_p (const_rtx mem1
, const_rtx mem2
)
420 return (flag_strict_aliasing
421 && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1
),
422 MEM_ALIAS_SET (mem2
)));
425 /* Return true if the first alias set is a subset of the second. */
428 alias_set_subset_of (alias_set_type set1
, alias_set_type set2
)
432 /* Everything is a subset of the "aliases everything" set. */
436 /* Otherwise, check if set1 is a subset of set2. */
437 ase
= get_alias_set_entry (set2
);
439 && (ase
->has_zero_child
440 || ase
->children
->get (set1
)))
445 /* Return 1 if the two specified alias sets may conflict. */
448 alias_sets_conflict_p (alias_set_type set1
, alias_set_type set2
)
453 if (alias_sets_must_conflict_p (set1
, set2
))
456 /* See if the first alias set is a subset of the second. */
457 ase
= get_alias_set_entry (set1
);
459 && (ase
->has_zero_child
460 || ase
->children
->get (set2
)))
463 /* Now do the same, but with the alias sets reversed. */
464 ase
= get_alias_set_entry (set2
);
466 && (ase
->has_zero_child
467 || ase
->children
->get (set1
)))
470 /* The two alias sets are distinct and neither one is the
471 child of the other. Therefore, they cannot conflict. */
475 /* Return 1 if the two specified alias sets will always conflict. */
478 alias_sets_must_conflict_p (alias_set_type set1
, alias_set_type set2
)
480 if (set1
== 0 || set2
== 0 || set1
== set2
)
486 /* Return 1 if any MEM object of type T1 will always conflict (using the
487 dependency routines in this file) with any MEM object of type T2.
488 This is used when allocating temporary storage. If T1 and/or T2 are
489 NULL_TREE, it means we know nothing about the storage. */
492 objects_must_conflict_p (tree t1
, tree t2
)
494 alias_set_type set1
, set2
;
496 /* If neither has a type specified, we don't know if they'll conflict
497 because we may be using them to store objects of various types, for
498 example the argument and local variables areas of inlined functions. */
499 if (t1
== 0 && t2
== 0)
502 /* If they are the same type, they must conflict. */
504 /* Likewise if both are volatile. */
505 || (t1
!= 0 && TYPE_VOLATILE (t1
) && t2
!= 0 && TYPE_VOLATILE (t2
)))
508 set1
= t1
? get_alias_set (t1
) : 0;
509 set2
= t2
? get_alias_set (t2
) : 0;
511 /* We can't use alias_sets_conflict_p because we must make sure
512 that every subtype of t1 will conflict with every subtype of
513 t2 for which a pair of subobjects of these respective subtypes
514 overlaps on the stack. */
515 return alias_sets_must_conflict_p (set1
, set2
);
518 /* Return the outermost parent of component present in the chain of
519 component references handled by get_inner_reference in T with the
521 - the component is non-addressable, or
522 - the parent has alias set zero,
523 or NULL_TREE if no such parent exists. In the former cases, the alias
524 set of this parent is the alias set that must be used for T itself. */
527 component_uses_parent_alias_set_from (const_tree t
)
529 const_tree found
= NULL_TREE
;
531 while (handled_component_p (t
))
533 switch (TREE_CODE (t
))
536 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t
, 1)))
541 case ARRAY_RANGE_REF
:
542 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t
, 0))))
551 case VIEW_CONVERT_EXPR
:
552 /* Bitfields and casts are never addressable. */
560 if (get_alias_set (TREE_TYPE (TREE_OPERAND (t
, 0))) == 0)
563 t
= TREE_OPERAND (t
, 0);
567 return TREE_OPERAND (found
, 0);
573 /* Return whether the pointer-type T effective for aliasing may
574 access everything and thus the reference has to be assigned
578 ref_all_alias_ptr_type_p (const_tree t
)
580 return (TREE_CODE (TREE_TYPE (t
)) == VOID_TYPE
581 || TYPE_REF_CAN_ALIAS_ALL (t
));
584 /* Return the alias set for the memory pointed to by T, which may be
585 either a type or an expression. Return -1 if there is nothing
586 special about dereferencing T. */
588 static alias_set_type
589 get_deref_alias_set_1 (tree t
)
591 /* All we care about is the type. */
595 /* If we have an INDIRECT_REF via a void pointer, we don't
596 know anything about what that might alias. Likewise if the
597 pointer is marked that way. */
598 if (ref_all_alias_ptr_type_p (t
))
604 /* Return the alias set for the memory pointed to by T, which may be
605 either a type or an expression. */
608 get_deref_alias_set (tree t
)
610 /* If we're not doing any alias analysis, just assume everything
611 aliases everything else. */
612 if (!flag_strict_aliasing
)
615 alias_set_type set
= get_deref_alias_set_1 (t
);
617 /* Fall back to the alias-set of the pointed-to type. */
622 set
= get_alias_set (TREE_TYPE (t
));
628 /* Return the pointer-type relevant for TBAA purposes from the
629 memory reference tree *T or NULL_TREE in which case *T is
630 adjusted to point to the outermost component reference that
631 can be used for assigning an alias set. */
634 reference_alias_ptr_type_1 (tree
*t
)
638 /* Get the base object of the reference. */
640 while (handled_component_p (inner
))
642 /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
643 the type of any component references that wrap it to
644 determine the alias-set. */
645 if (TREE_CODE (inner
) == VIEW_CONVERT_EXPR
)
646 *t
= TREE_OPERAND (inner
, 0);
647 inner
= TREE_OPERAND (inner
, 0);
650 /* Handle pointer dereferences here, they can override the
652 if (INDIRECT_REF_P (inner
)
653 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner
, 0))))
654 return TREE_TYPE (TREE_OPERAND (inner
, 0));
655 else if (TREE_CODE (inner
) == TARGET_MEM_REF
)
656 return TREE_TYPE (TMR_OFFSET (inner
));
657 else if (TREE_CODE (inner
) == MEM_REF
658 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner
, 1))))
659 return TREE_TYPE (TREE_OPERAND (inner
, 1));
661 /* If the innermost reference is a MEM_REF that has a
662 conversion embedded treat it like a VIEW_CONVERT_EXPR above,
663 using the memory access type for determining the alias-set. */
664 if (TREE_CODE (inner
) == MEM_REF
665 && (TYPE_MAIN_VARIANT (TREE_TYPE (inner
))
667 (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner
, 1))))))
668 return TREE_TYPE (TREE_OPERAND (inner
, 1));
670 /* Otherwise, pick up the outermost object that we could have
672 tree tem
= component_uses_parent_alias_set_from (*t
);
679 /* Return the pointer-type relevant for TBAA purposes from the
680 gimple memory reference tree T. This is the type to be used for
681 the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
682 and guarantees that get_alias_set will return the same alias
683 set for T and the replacement. */
686 reference_alias_ptr_type (tree t
)
688 tree ptype
= reference_alias_ptr_type_1 (&t
);
689 /* If there is a given pointer type for aliasing purposes, return it. */
690 if (ptype
!= NULL_TREE
)
693 /* Otherwise build one from the outermost component reference we
695 if (TREE_CODE (t
) == MEM_REF
696 || TREE_CODE (t
) == TARGET_MEM_REF
)
697 return TREE_TYPE (TREE_OPERAND (t
, 1));
699 return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t
)));
702 /* Return whether the pointer-types T1 and T2 used to determine
703 two alias sets of two references will yield the same answer
704 from get_deref_alias_set. */
707 alias_ptr_types_compatible_p (tree t1
, tree t2
)
709 if (TYPE_MAIN_VARIANT (t1
) == TYPE_MAIN_VARIANT (t2
))
712 if (ref_all_alias_ptr_type_p (t1
)
713 || ref_all_alias_ptr_type_p (t2
))
716 return (TYPE_MAIN_VARIANT (TREE_TYPE (t1
))
717 == TYPE_MAIN_VARIANT (TREE_TYPE (t2
)));
720 /* Return the alias set for T, which may be either a type or an
721 expression. Call language-specific routine for help, if needed. */
724 get_alias_set (tree t
)
728 /* If we're not doing any alias analysis, just assume everything
729 aliases everything else. Also return 0 if this or its type is
731 if (! flag_strict_aliasing
|| t
== error_mark_node
733 && (TREE_TYPE (t
) == 0 || TREE_TYPE (t
) == error_mark_node
)))
736 /* We can be passed either an expression or a type. This and the
737 language-specific routine may make mutually-recursive calls to each other
738 to figure out what to do. At each juncture, we see if this is a tree
739 that the language may need to handle specially. First handle things that
743 /* Give the language a chance to do something with this tree
744 before we look at it. */
746 set
= lang_hooks
.get_alias_set (t
);
750 /* Get the alias pointer-type to use or the outermost object
751 that we could have a pointer to. */
752 tree ptype
= reference_alias_ptr_type_1 (&t
);
754 return get_deref_alias_set (ptype
);
756 /* If we've already determined the alias set for a decl, just return
757 it. This is necessary for C++ anonymous unions, whose component
758 variables don't look like union members (boo!). */
759 if (TREE_CODE (t
) == VAR_DECL
760 && DECL_RTL_SET_P (t
) && MEM_P (DECL_RTL (t
)))
761 return MEM_ALIAS_SET (DECL_RTL (t
));
763 /* Now all we care about is the type. */
767 /* Variant qualifiers don't affect the alias set, so get the main
769 t
= TYPE_MAIN_VARIANT (t
);
771 /* Always use the canonical type as well. If this is a type that
772 requires structural comparisons to identify compatible types
773 use alias set zero. */
774 if (TYPE_STRUCTURAL_EQUALITY_P (t
))
776 /* Allow the language to specify another alias set for this
778 set
= lang_hooks
.get_alias_set (t
);
784 t
= TYPE_CANONICAL (t
);
786 /* The canonical type should not require structural equality checks. */
787 gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t
));
789 /* If this is a type with a known alias set, return it. */
790 if (TYPE_ALIAS_SET_KNOWN_P (t
))
791 return TYPE_ALIAS_SET (t
);
793 /* We don't want to set TYPE_ALIAS_SET for incomplete types. */
794 if (!COMPLETE_TYPE_P (t
))
796 /* For arrays with unknown size the conservative answer is the
797 alias set of the element type. */
798 if (TREE_CODE (t
) == ARRAY_TYPE
)
799 return get_alias_set (TREE_TYPE (t
));
801 /* But return zero as a conservative answer for incomplete types. */
805 /* See if the language has special handling for this type. */
806 set
= lang_hooks
.get_alias_set (t
);
810 /* There are no objects of FUNCTION_TYPE, so there's no point in
811 using up an alias set for them. (There are, of course, pointers
812 and references to functions, but that's different.) */
813 else if (TREE_CODE (t
) == FUNCTION_TYPE
|| TREE_CODE (t
) == METHOD_TYPE
)
816 /* Unless the language specifies otherwise, let vector types alias
817 their components. This avoids some nasty type punning issues in
818 normal usage. And indeed lets vectors be treated more like an
820 else if (TREE_CODE (t
) == VECTOR_TYPE
)
821 set
= get_alias_set (TREE_TYPE (t
));
823 /* Unless the language specifies otherwise, treat array types the
824 same as their components. This avoids the asymmetry we get
825 through recording the components. Consider accessing a
826 character(kind=1) through a reference to a character(kind=1)[1:1].
827 Or consider if we want to assign integer(kind=4)[0:D.1387] and
828 integer(kind=4)[4] the same alias set or not.
829 Just be pragmatic here and make sure the array and its element
830 type get the same alias set assigned. */
831 else if (TREE_CODE (t
) == ARRAY_TYPE
&& !TYPE_NONALIASED_COMPONENT (t
))
832 set
= get_alias_set (TREE_TYPE (t
));
834 /* From the former common C and C++ langhook implementation:
836 Unfortunately, there is no canonical form of a pointer type.
837 In particular, if we have `typedef int I', then `int *', and
838 `I *' are different types. So, we have to pick a canonical
839 representative. We do this below.
841 Technically, this approach is actually more conservative that
842 it needs to be. In particular, `const int *' and `int *'
843 should be in different alias sets, according to the C and C++
844 standard, since their types are not the same, and so,
845 technically, an `int **' and `const int **' cannot point at
848 But, the standard is wrong. In particular, this code is
853 const int* const* cipp = ipp;
854 And, it doesn't make sense for that to be legal unless you
855 can dereference IPP and CIPP. So, we ignore cv-qualifiers on
856 the pointed-to types. This issue has been reported to the
859 In addition to the above canonicalization issue, with LTO
860 we should also canonicalize `T (*)[]' to `T *' avoiding
861 alias issues with pointer-to element types and pointer-to
864 Likewise we need to deal with the situation of incomplete
865 pointed-to types and make `*(struct X **)&a' and
866 `*(struct X {} **)&a' alias. Otherwise we will have to
867 guarantee that all pointer-to incomplete type variants
868 will be replaced by pointer-to complete type variants if
871 With LTO the convenient situation of using `void *' to
872 access and store any pointer type will also become
873 more apparent (and `void *' is just another pointer-to
874 incomplete type). Assigning alias-set zero to `void *'
875 and all pointer-to incomplete types is a not appealing
876 solution. Assigning an effective alias-set zero only
877 affecting pointers might be - by recording proper subset
878 relationships of all pointer alias-sets.
880 Pointer-to function types are another grey area which
881 needs caution. Globbing them all into one alias-set
882 or the above effective zero set would work.
884 For now just assign the same alias-set to all pointers.
885 That's simple and avoids all the above problems. */
886 else if (POINTER_TYPE_P (t
)
887 && t
!= ptr_type_node
)
888 set
= get_alias_set (ptr_type_node
);
890 /* Otherwise make a new alias set for this type. */
893 /* Each canonical type gets its own alias set, so canonical types
894 shouldn't form a tree. It doesn't really matter for types
895 we handle specially above, so only check it where it possibly
896 would result in a bogus alias set. */
897 gcc_checking_assert (TYPE_CANONICAL (t
) == t
);
899 set
= new_alias_set ();
902 TYPE_ALIAS_SET (t
) = set
;
904 /* If this is an aggregate type or a complex type, we must record any
905 component aliasing information. */
906 if (AGGREGATE_TYPE_P (t
) || TREE_CODE (t
) == COMPLEX_TYPE
)
907 record_component_aliases (t
);
912 /* Return a brand-new alias set. */
917 if (flag_strict_aliasing
)
920 vec_safe_push (alias_sets
, (alias_set_entry
) 0);
921 vec_safe_push (alias_sets
, (alias_set_entry
) 0);
922 return alias_sets
->length () - 1;
928 /* Indicate that things in SUBSET can alias things in SUPERSET, but that
929 not everything that aliases SUPERSET also aliases SUBSET. For example,
930 in C, a store to an `int' can alias a load of a structure containing an
931 `int', and vice versa. But it can't alias a load of a 'double' member
932 of the same structure. Here, the structure would be the SUPERSET and
933 `int' the SUBSET. This relationship is also described in the comment at
934 the beginning of this file.
936 This function should be called only once per SUPERSET/SUBSET pair.
938 It is illegal for SUPERSET to be zero; everything is implicitly a
939 subset of alias set zero. */
942 record_alias_subset (alias_set_type superset
, alias_set_type subset
)
944 alias_set_entry superset_entry
;
945 alias_set_entry subset_entry
;
947 /* It is possible in complex type situations for both sets to be the same,
948 in which case we can ignore this operation. */
949 if (superset
== subset
)
952 gcc_assert (superset
);
954 superset_entry
= get_alias_set_entry (superset
);
955 if (superset_entry
== 0)
957 /* Create an entry for the SUPERSET, so that we have a place to
958 attach the SUBSET. */
959 superset_entry
= ggc_cleared_alloc
<alias_set_entry_d
> ();
960 superset_entry
->alias_set
= superset
;
961 superset_entry
->children
962 = hash_map
<int, int, alias_set_traits
>::create_ggc (64);
963 superset_entry
->has_zero_child
= 0;
964 (*alias_sets
)[superset
] = superset_entry
;
968 superset_entry
->has_zero_child
= 1;
971 subset_entry
= get_alias_set_entry (subset
);
972 /* If there is an entry for the subset, enter all of its children
973 (if they are not already present) as children of the SUPERSET. */
976 if (subset_entry
->has_zero_child
)
977 superset_entry
->has_zero_child
= 1;
979 hash_map
<int, int, alias_set_traits
>::iterator iter
980 = subset_entry
->children
->begin ();
981 for (; iter
!= subset_entry
->children
->end (); ++iter
)
982 superset_entry
->children
->put ((*iter
).first
, (*iter
).second
);
985 /* Enter the SUBSET itself as a child of the SUPERSET. */
986 superset_entry
->children
->put (subset
, 0);
990 /* Record that component types of TYPE, if any, are part of that type for
991 aliasing purposes. For record types, we only record component types
992 for fields that are not marked non-addressable. For array types, we
993 only record the component type if it is not marked non-aliased. */
996 record_component_aliases (tree type
)
998 alias_set_type superset
= get_alias_set (type
);
1004 switch (TREE_CODE (type
))
1008 case QUAL_UNION_TYPE
:
1009 for (field
= TYPE_FIELDS (type
); field
!= 0; field
= DECL_CHAIN (field
))
1010 if (TREE_CODE (field
) == FIELD_DECL
&& !DECL_NONADDRESSABLE_P (field
))
1011 record_alias_subset (superset
, get_alias_set (TREE_TYPE (field
)));
1015 record_alias_subset (superset
, get_alias_set (TREE_TYPE (type
)));
1018 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
1026 /* Allocate an alias set for use in storing and reading from the varargs
1029 static GTY(()) alias_set_type varargs_set
= -1;
1032 get_varargs_alias_set (void)
1035 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the
1036 varargs alias set to an INDIRECT_REF (FIXME!), so we can't
1037 consistently use the varargs alias set for loads from the varargs
1038 area. So don't use it anywhere. */
1041 if (varargs_set
== -1)
1042 varargs_set
= new_alias_set ();
1048 /* Likewise, but used for the fixed portions of the frame, e.g., register
1051 static GTY(()) alias_set_type frame_set
= -1;
1054 get_frame_alias_set (void)
1056 if (frame_set
== -1)
1057 frame_set
= new_alias_set ();
1062 /* Create a new, unique base with id ID. */
1065 unique_base_value (HOST_WIDE_INT id
)
1067 return gen_rtx_ADDRESS (Pmode
, id
);
1070 /* Return true if accesses based on any other base value cannot alias
1071 those based on X. */
1074 unique_base_value_p (rtx x
)
1076 return GET_CODE (x
) == ADDRESS
&& GET_MODE (x
) == Pmode
;
1079 /* Return true if X is known to be a base value. */
1082 known_base_value_p (rtx x
)
1084 switch (GET_CODE (x
))
1091 /* Arguments may or may not be bases; we don't know for sure. */
1092 return GET_MODE (x
) != VOIDmode
;
1099 /* Inside SRC, the source of a SET, find a base address. */
1102 find_base_value (rtx src
)
1106 #if defined (FIND_BASE_TERM)
1107 /* Try machine-dependent ways to find the base term. */
1108 src
= FIND_BASE_TERM (src
);
1111 switch (GET_CODE (src
))
1118 regno
= REGNO (src
);
1119 /* At the start of a function, argument registers have known base
1120 values which may be lost later. Returning an ADDRESS
1121 expression here allows optimization based on argument values
1122 even when the argument registers are used for other purposes. */
1123 if (regno
< FIRST_PSEUDO_REGISTER
&& copying_arguments
)
1124 return new_reg_base_value
[regno
];
1126 /* If a pseudo has a known base value, return it. Do not do this
1127 for non-fixed hard regs since it can result in a circular
1128 dependency chain for registers which have values at function entry.
1130 The test above is not sufficient because the scheduler may move
1131 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
1132 if ((regno
>= FIRST_PSEUDO_REGISTER
|| fixed_regs
[regno
])
1133 && regno
< vec_safe_length (reg_base_value
))
1135 /* If we're inside init_alias_analysis, use new_reg_base_value
1136 to reduce the number of relaxation iterations. */
1137 if (new_reg_base_value
&& new_reg_base_value
[regno
]
1138 && DF_REG_DEF_COUNT (regno
) == 1)
1139 return new_reg_base_value
[regno
];
1141 if ((*reg_base_value
)[regno
])
1142 return (*reg_base_value
)[regno
];
1148 /* Check for an argument passed in memory. Only record in the
1149 copying-arguments block; it is too hard to track changes
1151 if (copying_arguments
1152 && (XEXP (src
, 0) == arg_pointer_rtx
1153 || (GET_CODE (XEXP (src
, 0)) == PLUS
1154 && XEXP (XEXP (src
, 0), 0) == arg_pointer_rtx
)))
1155 return arg_base_value
;
1159 src
= XEXP (src
, 0);
1160 if (GET_CODE (src
) != PLUS
&& GET_CODE (src
) != MINUS
)
1163 /* ... fall through ... */
1168 rtx temp
, src_0
= XEXP (src
, 0), src_1
= XEXP (src
, 1);
1170 /* If either operand is a REG that is a known pointer, then it
1172 if (REG_P (src_0
) && REG_POINTER (src_0
))
1173 return find_base_value (src_0
);
1174 if (REG_P (src_1
) && REG_POINTER (src_1
))
1175 return find_base_value (src_1
);
1177 /* If either operand is a REG, then see if we already have
1178 a known value for it. */
1181 temp
= find_base_value (src_0
);
1188 temp
= find_base_value (src_1
);
1193 /* If either base is named object or a special address
1194 (like an argument or stack reference), then use it for the
1196 if (src_0
!= 0 && known_base_value_p (src_0
))
1199 if (src_1
!= 0 && known_base_value_p (src_1
))
1202 /* Guess which operand is the base address:
1203 If either operand is a symbol, then it is the base. If
1204 either operand is a CONST_INT, then the other is the base. */
1205 if (CONST_INT_P (src_1
) || CONSTANT_P (src_0
))
1206 return find_base_value (src_0
);
1207 else if (CONST_INT_P (src_0
) || CONSTANT_P (src_1
))
1208 return find_base_value (src_1
);
1214 /* The standard form is (lo_sum reg sym) so look only at the
1216 return find_base_value (XEXP (src
, 1));
1219 /* If the second operand is constant set the base
1220 address to the first operand. */
1221 if (CONST_INT_P (XEXP (src
, 1)) && INTVAL (XEXP (src
, 1)) != 0)
1222 return find_base_value (XEXP (src
, 0));
1226 /* As we do not know which address space the pointer is referring to, we can
1227 handle this only if the target does not support different pointer or
1228 address modes depending on the address space. */
1229 if (!target_default_pointer_address_modes_p ())
1231 if (GET_MODE_SIZE (GET_MODE (src
)) < GET_MODE_SIZE (Pmode
))
1241 return find_base_value (XEXP (src
, 0));
1244 case SIGN_EXTEND
: /* used for NT/Alpha pointers */
1245 /* As we do not know which address space the pointer is referring to, we can
1246 handle this only if the target does not support different pointer or
1247 address modes depending on the address space. */
1248 if (!target_default_pointer_address_modes_p ())
1252 rtx temp
= find_base_value (XEXP (src
, 0));
1254 if (temp
!= 0 && CONSTANT_P (temp
))
1255 temp
= convert_memory_address (Pmode
, temp
);
1267 /* Called from init_alias_analysis indirectly through note_stores,
1268 or directly if DEST is a register with a REG_NOALIAS note attached.
1269 SET is null in the latter case. */
1271 /* While scanning insns to find base values, reg_seen[N] is nonzero if
1272 register N has been set in this function. */
1273 static sbitmap reg_seen
;
1276 record_set (rtx dest
, const_rtx set
, void *data ATTRIBUTE_UNUSED
)
1285 regno
= REGNO (dest
);
1287 gcc_checking_assert (regno
< reg_base_value
->length ());
1289 /* If this spans multiple hard registers, then we must indicate that every
1290 register has an unusable value. */
1291 if (regno
< FIRST_PSEUDO_REGISTER
)
1292 n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
1299 bitmap_set_bit (reg_seen
, regno
+ n
);
1300 new_reg_base_value
[regno
+ n
] = 0;
1307 /* A CLOBBER wipes out any old value but does not prevent a previously
1308 unset register from acquiring a base address (i.e. reg_seen is not
1310 if (GET_CODE (set
) == CLOBBER
)
1312 new_reg_base_value
[regno
] = 0;
1315 src
= SET_SRC (set
);
1319 /* There's a REG_NOALIAS note against DEST. */
1320 if (bitmap_bit_p (reg_seen
, regno
))
1322 new_reg_base_value
[regno
] = 0;
1325 bitmap_set_bit (reg_seen
, regno
);
1326 new_reg_base_value
[regno
] = unique_base_value (unique_id
++);
1330 /* If this is not the first set of REGNO, see whether the new value
1331 is related to the old one. There are two cases of interest:
1333 (1) The register might be assigned an entirely new value
1334 that has the same base term as the original set.
1336 (2) The set might be a simple self-modification that
1337 cannot change REGNO's base value.
1339 If neither case holds, reject the original base value as invalid.
1340 Note that the following situation is not detected:
1342 extern int x, y; int *p = &x; p += (&y-&x);
1344 ANSI C does not allow computing the difference of addresses
1345 of distinct top level objects. */
1346 if (new_reg_base_value
[regno
] != 0
1347 && find_base_value (src
) != new_reg_base_value
[regno
])
1348 switch (GET_CODE (src
))
1352 if (XEXP (src
, 0) != dest
&& XEXP (src
, 1) != dest
)
1353 new_reg_base_value
[regno
] = 0;
1356 /* If the value we add in the PLUS is also a valid base value,
1357 this might be the actual base value, and the original value
1360 rtx other
= NULL_RTX
;
1362 if (XEXP (src
, 0) == dest
)
1363 other
= XEXP (src
, 1);
1364 else if (XEXP (src
, 1) == dest
)
1365 other
= XEXP (src
, 0);
1367 if (! other
|| find_base_value (other
))
1368 new_reg_base_value
[regno
] = 0;
1372 if (XEXP (src
, 0) != dest
|| !CONST_INT_P (XEXP (src
, 1)))
1373 new_reg_base_value
[regno
] = 0;
1376 new_reg_base_value
[regno
] = 0;
1379 /* If this is the first set of a register, record the value. */
1380 else if ((regno
>= FIRST_PSEUDO_REGISTER
|| ! fixed_regs
[regno
])
1381 && ! bitmap_bit_p (reg_seen
, regno
) && new_reg_base_value
[regno
] == 0)
1382 new_reg_base_value
[regno
] = find_base_value (src
);
1384 bitmap_set_bit (reg_seen
, regno
);
1387 /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
1388 using hard registers with non-null REG_BASE_VALUE for renaming. */
1390 get_reg_base_value (unsigned int regno
)
1392 return (*reg_base_value
)[regno
];
1395 /* If a value is known for REGNO, return it. */
1398 get_reg_known_value (unsigned int regno
)
1400 if (regno
>= FIRST_PSEUDO_REGISTER
)
1402 regno
-= FIRST_PSEUDO_REGISTER
;
1403 if (regno
< vec_safe_length (reg_known_value
))
1404 return (*reg_known_value
)[regno
];
1412 set_reg_known_value (unsigned int regno
, rtx val
)
1414 if (regno
>= FIRST_PSEUDO_REGISTER
)
1416 regno
-= FIRST_PSEUDO_REGISTER
;
1417 if (regno
< vec_safe_length (reg_known_value
))
1418 (*reg_known_value
)[regno
] = val
;
1422 /* Similarly for reg_known_equiv_p. */
1425 get_reg_known_equiv_p (unsigned int regno
)
1427 if (regno
>= FIRST_PSEUDO_REGISTER
)
1429 regno
-= FIRST_PSEUDO_REGISTER
;
1430 if (regno
< vec_safe_length (reg_known_value
))
1431 return bitmap_bit_p (reg_known_equiv_p
, regno
);
1437 set_reg_known_equiv_p (unsigned int regno
, bool val
)
1439 if (regno
>= FIRST_PSEUDO_REGISTER
)
1441 regno
-= FIRST_PSEUDO_REGISTER
;
1442 if (regno
< vec_safe_length (reg_known_value
))
1445 bitmap_set_bit (reg_known_equiv_p
, regno
);
1447 bitmap_clear_bit (reg_known_equiv_p
, regno
);
1453 /* Returns a canonical version of X, from the point of view alias
1454 analysis. (For example, if X is a MEM whose address is a register,
1455 and the register has a known value (say a SYMBOL_REF), then a MEM
1456 whose address is the SYMBOL_REF is returned.) */
1461 /* Recursively look for equivalences. */
1462 if (REG_P (x
) && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1464 rtx t
= get_reg_known_value (REGNO (x
));
1468 return canon_rtx (t
);
1471 if (GET_CODE (x
) == PLUS
)
1473 rtx x0
= canon_rtx (XEXP (x
, 0));
1474 rtx x1
= canon_rtx (XEXP (x
, 1));
1476 if (x0
!= XEXP (x
, 0) || x1
!= XEXP (x
, 1))
1478 if (CONST_INT_P (x0
))
1479 return plus_constant (GET_MODE (x
), x1
, INTVAL (x0
));
1480 else if (CONST_INT_P (x1
))
1481 return plus_constant (GET_MODE (x
), x0
, INTVAL (x1
));
1482 return gen_rtx_PLUS (GET_MODE (x
), x0
, x1
);
1486 /* This gives us much better alias analysis when called from
1487 the loop optimizer. Note we want to leave the original
1488 MEM alone, but need to return the canonicalized MEM with
1489 all the flags with their original values. */
1491 x
= replace_equiv_address_nv (x
, canon_rtx (XEXP (x
, 0)));
1496 /* Return 1 if X and Y are identical-looking rtx's.
1497 Expect that X and Y has been already canonicalized.
1499 We use the data in reg_known_value above to see if two registers with
1500 different numbers are, in fact, equivalent. */
1503 rtx_equal_for_memref_p (const_rtx x
, const_rtx y
)
1510 if (x
== 0 && y
== 0)
1512 if (x
== 0 || y
== 0)
1518 code
= GET_CODE (x
);
1519 /* Rtx's of different codes cannot be equal. */
1520 if (code
!= GET_CODE (y
))
1523 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
1524 (REG:SI x) and (REG:HI x) are NOT equivalent. */
1526 if (GET_MODE (x
) != GET_MODE (y
))
1529 /* Some RTL can be compared without a recursive examination. */
1533 return REGNO (x
) == REGNO (y
);
1536 return LABEL_REF_LABEL (x
) == LABEL_REF_LABEL (y
);
1539 return XSTR (x
, 0) == XSTR (y
, 0);
1542 /* This is magic, don't go through canonicalization et al. */
1543 return rtx_equal_p (ENTRY_VALUE_EXP (x
), ENTRY_VALUE_EXP (y
));
1547 /* Pointer equality guarantees equality for these nodes. */
1554 /* canon_rtx knows how to handle plus. No need to canonicalize. */
1556 return ((rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 0))
1557 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 1)))
1558 || (rtx_equal_for_memref_p (XEXP (x
, 0), XEXP (y
, 1))
1559 && rtx_equal_for_memref_p (XEXP (x
, 1), XEXP (y
, 0))));
1560 /* For commutative operations, the RTX match if the operand match in any
1561 order. Also handle the simple binary and unary cases without a loop. */
1562 if (COMMUTATIVE_P (x
))
1564 rtx xop0
= canon_rtx (XEXP (x
, 0));
1565 rtx yop0
= canon_rtx (XEXP (y
, 0));
1566 rtx yop1
= canon_rtx (XEXP (y
, 1));
1568 return ((rtx_equal_for_memref_p (xop0
, yop0
)
1569 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop1
))
1570 || (rtx_equal_for_memref_p (xop0
, yop1
)
1571 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)), yop0
)));
1573 else if (NON_COMMUTATIVE_P (x
))
1575 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1576 canon_rtx (XEXP (y
, 0)))
1577 && rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 1)),
1578 canon_rtx (XEXP (y
, 1))));
1580 else if (UNARY_P (x
))
1581 return rtx_equal_for_memref_p (canon_rtx (XEXP (x
, 0)),
1582 canon_rtx (XEXP (y
, 0)));
1584 /* Compare the elements. If any pair of corresponding elements
1585 fail to match, return 0 for the whole things.
1587 Limit cases to types which actually appear in addresses. */
1589 fmt
= GET_RTX_FORMAT (code
);
1590 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1595 if (XINT (x
, i
) != XINT (y
, i
))
1600 /* Two vectors must have the same length. */
1601 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1604 /* And the corresponding elements must match. */
1605 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1606 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x
, i
, j
)),
1607 canon_rtx (XVECEXP (y
, i
, j
))) == 0)
1612 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x
, i
)),
1613 canon_rtx (XEXP (y
, i
))) == 0)
1617 /* This can happen for asm operands. */
1619 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1623 /* This can happen for an asm which clobbers memory. */
1627 /* It is believed that rtx's at this level will never
1628 contain anything but integers and other rtx's,
1629 except for within LABEL_REFs and SYMBOL_REFs. */
1638 find_base_term (rtx x
)
1641 struct elt_loc_list
*l
, *f
;
1644 #if defined (FIND_BASE_TERM)
1645 /* Try machine-dependent ways to find the base term. */
1646 x
= FIND_BASE_TERM (x
);
1649 switch (GET_CODE (x
))
1652 return REG_BASE_VALUE (x
);
1655 /* As we do not know which address space the pointer is referring to, we can
1656 handle this only if the target does not support different pointer or
1657 address modes depending on the address space. */
1658 if (!target_default_pointer_address_modes_p ())
1660 if (GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (Pmode
))
1670 return find_base_term (XEXP (x
, 0));
1673 case SIGN_EXTEND
: /* Used for Alpha/NT pointers */
1674 /* As we do not know which address space the pointer is referring to, we can
1675 handle this only if the target does not support different pointer or
1676 address modes depending on the address space. */
1677 if (!target_default_pointer_address_modes_p ())
1681 rtx temp
= find_base_term (XEXP (x
, 0));
1683 if (temp
!= 0 && CONSTANT_P (temp
))
1684 temp
= convert_memory_address (Pmode
, temp
);
1690 val
= CSELIB_VAL_PTR (x
);
1696 if (cselib_sp_based_value_p (val
))
1697 return static_reg_base_value
[STACK_POINTER_REGNUM
];
1700 /* Temporarily reset val->locs to avoid infinite recursion. */
1703 for (l
= f
; l
; l
= l
->next
)
1704 if (GET_CODE (l
->loc
) == VALUE
1705 && CSELIB_VAL_PTR (l
->loc
)->locs
1706 && !CSELIB_VAL_PTR (l
->loc
)->locs
->next
1707 && CSELIB_VAL_PTR (l
->loc
)->locs
->loc
== x
)
1709 else if ((ret
= find_base_term (l
->loc
)) != 0)
1716 /* The standard form is (lo_sum reg sym) so look only at the
1718 return find_base_term (XEXP (x
, 1));
1722 if (GET_CODE (x
) != PLUS
&& GET_CODE (x
) != MINUS
)
1728 rtx tmp1
= XEXP (x
, 0);
1729 rtx tmp2
= XEXP (x
, 1);
1731 /* This is a little bit tricky since we have to determine which of
1732 the two operands represents the real base address. Otherwise this
1733 routine may return the index register instead of the base register.
1735 That may cause us to believe no aliasing was possible, when in
1736 fact aliasing is possible.
1738 We use a few simple tests to guess the base register. Additional
1739 tests can certainly be added. For example, if one of the operands
1740 is a shift or multiply, then it must be the index register and the
1741 other operand is the base register. */
1743 if (tmp1
== pic_offset_table_rtx
&& CONSTANT_P (tmp2
))
1744 return find_base_term (tmp2
);
1746 /* If either operand is known to be a pointer, then prefer it
1747 to determine the base term. */
1748 if (REG_P (tmp1
) && REG_POINTER (tmp1
))
1750 else if (REG_P (tmp2
) && REG_POINTER (tmp2
))
1757 /* Go ahead and find the base term for both operands. If either base
1758 term is from a pointer or is a named object or a special address
1759 (like an argument or stack reference), then use it for the
1761 rtx base
= find_base_term (tmp1
);
1762 if (base
!= NULL_RTX
1763 && ((REG_P (tmp1
) && REG_POINTER (tmp1
))
1764 || known_base_value_p (base
)))
1766 base
= find_base_term (tmp2
);
1767 if (base
!= NULL_RTX
1768 && ((REG_P (tmp2
) && REG_POINTER (tmp2
))
1769 || known_base_value_p (base
)))
1772 /* We could not determine which of the two operands was the
1773 base register and which was the index. So we can determine
1774 nothing from the base alias check. */
1779 if (CONST_INT_P (XEXP (x
, 1)) && INTVAL (XEXP (x
, 1)) != 0)
1780 return find_base_term (XEXP (x
, 0));
1792 /* Return true if accesses to address X may alias accesses based
1793 on the stack pointer. */
1796 may_be_sp_based_p (rtx x
)
1798 rtx base
= find_base_term (x
);
1799 return !base
|| base
== static_reg_base_value
[STACK_POINTER_REGNUM
];
1802 /* Return 0 if the addresses X and Y are known to point to different
1803 objects, 1 if they might be pointers to the same object. */
1806 base_alias_check (rtx x
, rtx x_base
, rtx y
, rtx y_base
,
1807 machine_mode x_mode
, machine_mode y_mode
)
1809 /* If the address itself has no known base see if a known equivalent
1810 value has one. If either address still has no known base, nothing
1811 is known about aliasing. */
1816 if (! flag_expensive_optimizations
|| (x_c
= canon_rtx (x
)) == x
)
1819 x_base
= find_base_term (x_c
);
1827 if (! flag_expensive_optimizations
|| (y_c
= canon_rtx (y
)) == y
)
1830 y_base
= find_base_term (y_c
);
1835 /* If the base addresses are equal nothing is known about aliasing. */
1836 if (rtx_equal_p (x_base
, y_base
))
1839 /* The base addresses are different expressions. If they are not accessed
1840 via AND, there is no conflict. We can bring knowledge of object
1841 alignment into play here. For example, on alpha, "char a, b;" can
1842 alias one another, though "char a; long b;" cannot. AND addesses may
1843 implicitly alias surrounding objects; i.e. unaligned access in DImode
1844 via AND address can alias all surrounding object types except those
1845 with aligment 8 or higher. */
1846 if (GET_CODE (x
) == AND
&& GET_CODE (y
) == AND
)
1848 if (GET_CODE (x
) == AND
1849 && (!CONST_INT_P (XEXP (x
, 1))
1850 || (int) GET_MODE_UNIT_SIZE (y_mode
) < -INTVAL (XEXP (x
, 1))))
1852 if (GET_CODE (y
) == AND
1853 && (!CONST_INT_P (XEXP (y
, 1))
1854 || (int) GET_MODE_UNIT_SIZE (x_mode
) < -INTVAL (XEXP (y
, 1))))
1857 /* Differing symbols not accessed via AND never alias. */
1858 if (GET_CODE (x_base
) != ADDRESS
&& GET_CODE (y_base
) != ADDRESS
)
1861 if (unique_base_value_p (x_base
) || unique_base_value_p (y_base
))
1867 /* Return TRUE if EXPR refers to a VALUE whose uid is greater than
1871 refs_newer_value_p (const_rtx expr
, rtx v
)
1873 int minuid
= CSELIB_VAL_PTR (v
)->uid
;
1874 subrtx_iterator::array_type array
;
1875 FOR_EACH_SUBRTX (iter
, array
, expr
, NONCONST
)
1876 if (GET_CODE (*iter
) == VALUE
&& CSELIB_VAL_PTR (*iter
)->uid
> minuid
)
1881 /* Convert the address X into something we can use. This is done by returning
1882 it unchanged unless it is a value; in the latter case we call cselib to get
1883 a more useful rtx. */
1889 struct elt_loc_list
*l
;
1891 if (GET_CODE (x
) != VALUE
)
1893 v
= CSELIB_VAL_PTR (x
);
1896 bool have_equivs
= cselib_have_permanent_equivalences ();
1898 v
= canonical_cselib_val (v
);
1899 for (l
= v
->locs
; l
; l
= l
->next
)
1900 if (CONSTANT_P (l
->loc
))
1902 for (l
= v
->locs
; l
; l
= l
->next
)
1903 if (!REG_P (l
->loc
) && !MEM_P (l
->loc
)
1904 /* Avoid infinite recursion when potentially dealing with
1905 var-tracking artificial equivalences, by skipping the
1906 equivalences themselves, and not choosing expressions
1907 that refer to newer VALUEs. */
1909 || (GET_CODE (l
->loc
) != VALUE
1910 && !refs_newer_value_p (l
->loc
, x
))))
1914 for (l
= v
->locs
; l
; l
= l
->next
)
1916 || (GET_CODE (l
->loc
) != VALUE
1917 && !refs_newer_value_p (l
->loc
, x
)))
1919 /* Return the canonical value. */
1923 return v
->locs
->loc
;
1928 /* Return the address of the (N_REFS + 1)th memory reference to ADDR
1929 where SIZE is the size in bytes of the memory reference. If ADDR
1930 is not modified by the memory reference then ADDR is returned. */
1933 addr_side_effect_eval (rtx addr
, int size
, int n_refs
)
1937 switch (GET_CODE (addr
))
1940 offset
= (n_refs
+ 1) * size
;
1943 offset
= -(n_refs
+ 1) * size
;
1946 offset
= n_refs
* size
;
1949 offset
= -n_refs
* size
;
1957 addr
= gen_rtx_PLUS (GET_MODE (addr
), XEXP (addr
, 0),
1958 gen_int_mode (offset
, GET_MODE (addr
)));
1960 addr
= XEXP (addr
, 0);
1961 addr
= canon_rtx (addr
);
1966 /* Return TRUE if an object X sized at XSIZE bytes and another object
1967 Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
1968 any of the sizes is zero, assume an overlap, otherwise use the
1969 absolute value of the sizes as the actual sizes. */
1972 offset_overlap_p (HOST_WIDE_INT c
, int xsize
, int ysize
)
1974 return (xsize
== 0 || ysize
== 0
1977 : (abs (ysize
) > -c
)));
1980 /* Return one if X and Y (memory addresses) reference the
1981 same location in memory or if the references overlap.
1982 Return zero if they do not overlap, else return
1983 minus one in which case they still might reference the same location.
1985 C is an offset accumulator. When
1986 C is nonzero, we are testing aliases between X and Y + C.
1987 XSIZE is the size in bytes of the X reference,
1988 similarly YSIZE is the size in bytes for Y.
1989 Expect that canon_rtx has been already called for X and Y.
1991 If XSIZE or YSIZE is zero, we do not know the amount of memory being
1992 referenced (the reference was BLKmode), so make the most pessimistic
1995 If XSIZE or YSIZE is negative, we may access memory outside the object
1996 being referenced as a side effect. This can happen when using AND to
1997 align memory references, as is done on the Alpha.
1999 Nice to notice that varying addresses cannot conflict with fp if no
2000 local variables had their addresses taken, but that's too hard now.
2002 ??? Contrary to the tree alias oracle this does not return
2003 one for X + non-constant and Y + non-constant when X and Y are equal.
2004 If that is fixed the TBAA hack for union type-punning can be removed. */
2007 memrefs_conflict_p (int xsize
, rtx x
, int ysize
, rtx y
, HOST_WIDE_INT c
)
2009 if (GET_CODE (x
) == VALUE
)
2013 struct elt_loc_list
*l
= NULL
;
2014 if (CSELIB_VAL_PTR (x
))
2015 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (x
))->locs
;
2017 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, y
))
2024 /* Don't call get_addr if y is the same VALUE. */
2028 if (GET_CODE (y
) == VALUE
)
2032 struct elt_loc_list
*l
= NULL
;
2033 if (CSELIB_VAL_PTR (y
))
2034 for (l
= canonical_cselib_val (CSELIB_VAL_PTR (y
))->locs
;
2036 if (REG_P (l
->loc
) && rtx_equal_for_memref_p (l
->loc
, x
))
2043 /* Don't call get_addr if x is the same VALUE. */
2047 if (GET_CODE (x
) == HIGH
)
2049 else if (GET_CODE (x
) == LO_SUM
)
2052 x
= addr_side_effect_eval (x
, abs (xsize
), 0);
2053 if (GET_CODE (y
) == HIGH
)
2055 else if (GET_CODE (y
) == LO_SUM
)
2058 y
= addr_side_effect_eval (y
, abs (ysize
), 0);
2060 if (rtx_equal_for_memref_p (x
, y
))
2062 return offset_overlap_p (c
, xsize
, ysize
);
2065 /* This code used to check for conflicts involving stack references and
2066 globals but the base address alias code now handles these cases. */
2068 if (GET_CODE (x
) == PLUS
)
2070 /* The fact that X is canonicalized means that this
2071 PLUS rtx is canonicalized. */
2072 rtx x0
= XEXP (x
, 0);
2073 rtx x1
= XEXP (x
, 1);
2075 if (GET_CODE (y
) == PLUS
)
2077 /* The fact that Y is canonicalized means that this
2078 PLUS rtx is canonicalized. */
2079 rtx y0
= XEXP (y
, 0);
2080 rtx y1
= XEXP (y
, 1);
2082 if (rtx_equal_for_memref_p (x1
, y1
))
2083 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2084 if (rtx_equal_for_memref_p (x0
, y0
))
2085 return memrefs_conflict_p (xsize
, x1
, ysize
, y1
, c
);
2086 if (CONST_INT_P (x1
))
2088 if (CONST_INT_P (y1
))
2089 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
,
2090 c
- INTVAL (x1
) + INTVAL (y1
));
2092 return memrefs_conflict_p (xsize
, x0
, ysize
, y
,
2095 else if (CONST_INT_P (y1
))
2096 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
2100 else if (CONST_INT_P (x1
))
2101 return memrefs_conflict_p (xsize
, x0
, ysize
, y
, c
- INTVAL (x1
));
2103 else if (GET_CODE (y
) == PLUS
)
2105 /* The fact that Y is canonicalized means that this
2106 PLUS rtx is canonicalized. */
2107 rtx y0
= XEXP (y
, 0);
2108 rtx y1
= XEXP (y
, 1);
2110 if (CONST_INT_P (y1
))
2111 return memrefs_conflict_p (xsize
, x
, ysize
, y0
, c
+ INTVAL (y1
));
2116 if (GET_CODE (x
) == GET_CODE (y
))
2117 switch (GET_CODE (x
))
2121 /* Handle cases where we expect the second operands to be the
2122 same, and check only whether the first operand would conflict
2125 rtx x1
= canon_rtx (XEXP (x
, 1));
2126 rtx y1
= canon_rtx (XEXP (y
, 1));
2127 if (! rtx_equal_for_memref_p (x1
, y1
))
2129 x0
= canon_rtx (XEXP (x
, 0));
2130 y0
= canon_rtx (XEXP (y
, 0));
2131 if (rtx_equal_for_memref_p (x0
, y0
))
2132 return offset_overlap_p (c
, xsize
, ysize
);
2134 /* Can't properly adjust our sizes. */
2135 if (!CONST_INT_P (x1
))
2137 xsize
/= INTVAL (x1
);
2138 ysize
/= INTVAL (x1
);
2140 return memrefs_conflict_p (xsize
, x0
, ysize
, y0
, c
);
2147 /* Deal with alignment ANDs by adjusting offset and size so as to
2148 cover the maximum range, without taking any previously known
2149 alignment into account. Make a size negative after such an
2150 adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
2151 assume a potential overlap, because they may end up in contiguous
2152 memory locations and the stricter-alignment access may span over
2154 if (GET_CODE (x
) == AND
&& CONST_INT_P (XEXP (x
, 1)))
2156 HOST_WIDE_INT sc
= INTVAL (XEXP (x
, 1));
2157 unsigned HOST_WIDE_INT uc
= sc
;
2158 if (sc
< 0 && -uc
== (uc
& -uc
))
2165 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2169 if (GET_CODE (y
) == AND
&& CONST_INT_P (XEXP (y
, 1)))
2171 HOST_WIDE_INT sc
= INTVAL (XEXP (y
, 1));
2172 unsigned HOST_WIDE_INT uc
= sc
;
2173 if (sc
< 0 && -uc
== (uc
& -uc
))
2180 return memrefs_conflict_p (xsize
, x
,
2181 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2187 if (CONST_INT_P (x
) && CONST_INT_P (y
))
2189 c
+= (INTVAL (y
) - INTVAL (x
));
2190 return offset_overlap_p (c
, xsize
, ysize
);
2193 if (GET_CODE (x
) == CONST
)
2195 if (GET_CODE (y
) == CONST
)
2196 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2197 ysize
, canon_rtx (XEXP (y
, 0)), c
);
2199 return memrefs_conflict_p (xsize
, canon_rtx (XEXP (x
, 0)),
2202 if (GET_CODE (y
) == CONST
)
2203 return memrefs_conflict_p (xsize
, x
, ysize
,
2204 canon_rtx (XEXP (y
, 0)), c
);
2206 /* Assume a potential overlap for symbolic addresses that went
2207 through alignment adjustments (i.e., that have negative
2208 sizes), because we can't know how far they are from each
2211 return (xsize
< 0 || ysize
< 0 || offset_overlap_p (c
, xsize
, ysize
));
2219 /* Functions to compute memory dependencies.
2221 Since we process the insns in execution order, we can build tables
2222 to keep track of what registers are fixed (and not aliased), what registers
2223 are varying in known ways, and what registers are varying in unknown
2226 If both memory references are volatile, then there must always be a
2227 dependence between the two references, since their order can not be
2228 changed. A volatile and non-volatile reference can be interchanged
2231 We also must allow AND addresses, because they may generate accesses
2232 outside the object being referenced. This is used to generate aligned
2233 addresses from unaligned addresses, for instance, the alpha
2234 storeqi_unaligned pattern. */
2236 /* Read dependence: X is read after read in MEM takes place. There can
2237 only be a dependence here if both reads are volatile, or if either is
2238 an explicit barrier. */
2241 read_dependence (const_rtx mem
, const_rtx x
)
2243 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2245 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2246 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2251 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */
2254 decl_for_component_ref (tree x
)
2258 x
= TREE_OPERAND (x
, 0);
2260 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2262 return x
&& DECL_P (x
) ? x
: NULL_TREE
;
2265 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate
2266 for the offset of the field reference. *KNOWN_P says whether the
2270 adjust_offset_for_component_ref (tree x
, bool *known_p
,
2271 HOST_WIDE_INT
*offset
)
2277 tree xoffset
= component_ref_field_offset (x
);
2278 tree field
= TREE_OPERAND (x
, 1);
2279 if (TREE_CODE (xoffset
) != INTEGER_CST
)
2286 = (wi::to_offset (xoffset
)
2287 + wi::lrshift (wi::to_offset (DECL_FIELD_BIT_OFFSET (field
)),
2288 LOG2_BITS_PER_UNIT
));
2289 if (!wi::fits_uhwi_p (woffset
))
2294 *offset
+= woffset
.to_uhwi ();
2296 x
= TREE_OPERAND (x
, 0);
2298 while (x
&& TREE_CODE (x
) == COMPONENT_REF
);
2301 /* Return nonzero if we can determine the exprs corresponding to memrefs
2302 X and Y and they do not overlap.
2303 If LOOP_VARIANT is set, skip offset-based disambiguation */
2306 nonoverlapping_memrefs_p (const_rtx x
, const_rtx y
, bool loop_invariant
)
2308 tree exprx
= MEM_EXPR (x
), expry
= MEM_EXPR (y
);
2311 bool moffsetx_known_p
, moffsety_known_p
;
2312 HOST_WIDE_INT moffsetx
= 0, moffsety
= 0;
2313 HOST_WIDE_INT offsetx
= 0, offsety
= 0, sizex
, sizey
, tem
;
2315 /* Unless both have exprs, we can't tell anything. */
2316 if (exprx
== 0 || expry
== 0)
2319 /* For spill-slot accesses make sure we have valid offsets. */
2320 if ((exprx
== get_spill_slot_decl (false)
2321 && ! MEM_OFFSET_KNOWN_P (x
))
2322 || (expry
== get_spill_slot_decl (false)
2323 && ! MEM_OFFSET_KNOWN_P (y
)))
2326 /* If the field reference test failed, look at the DECLs involved. */
2327 moffsetx_known_p
= MEM_OFFSET_KNOWN_P (x
);
2328 if (moffsetx_known_p
)
2329 moffsetx
= MEM_OFFSET (x
);
2330 if (TREE_CODE (exprx
) == COMPONENT_REF
)
2332 tree t
= decl_for_component_ref (exprx
);
2335 adjust_offset_for_component_ref (exprx
, &moffsetx_known_p
, &moffsetx
);
2339 moffsety_known_p
= MEM_OFFSET_KNOWN_P (y
);
2340 if (moffsety_known_p
)
2341 moffsety
= MEM_OFFSET (y
);
2342 if (TREE_CODE (expry
) == COMPONENT_REF
)
2344 tree t
= decl_for_component_ref (expry
);
2347 adjust_offset_for_component_ref (expry
, &moffsety_known_p
, &moffsety
);
2351 if (! DECL_P (exprx
) || ! DECL_P (expry
))
2354 /* With invalid code we can end up storing into the constant pool.
2355 Bail out to avoid ICEing when creating RTL for this.
2356 See gfortran.dg/lto/20091028-2_0.f90. */
2357 if (TREE_CODE (exprx
) == CONST_DECL
2358 || TREE_CODE (expry
) == CONST_DECL
)
2361 rtlx
= DECL_RTL (exprx
);
2362 rtly
= DECL_RTL (expry
);
2364 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they
2365 can't overlap unless they are the same because we never reuse that part
2366 of the stack frame used for locals for spilled pseudos. */
2367 if ((!MEM_P (rtlx
) || !MEM_P (rtly
))
2368 && ! rtx_equal_p (rtlx
, rtly
))
2371 /* If we have MEMs referring to different address spaces (which can
2372 potentially overlap), we cannot easily tell from the addresses
2373 whether the references overlap. */
2374 if (MEM_P (rtlx
) && MEM_P (rtly
)
2375 && MEM_ADDR_SPACE (rtlx
) != MEM_ADDR_SPACE (rtly
))
2378 /* Get the base and offsets of both decls. If either is a register, we
2379 know both are and are the same, so use that as the base. The only
2380 we can avoid overlap is if we can deduce that they are nonoverlapping
2381 pieces of that decl, which is very rare. */
2382 basex
= MEM_P (rtlx
) ? XEXP (rtlx
, 0) : rtlx
;
2383 if (GET_CODE (basex
) == PLUS
&& CONST_INT_P (XEXP (basex
, 1)))
2384 offsetx
= INTVAL (XEXP (basex
, 1)), basex
= XEXP (basex
, 0);
2386 basey
= MEM_P (rtly
) ? XEXP (rtly
, 0) : rtly
;
2387 if (GET_CODE (basey
) == PLUS
&& CONST_INT_P (XEXP (basey
, 1)))
2388 offsety
= INTVAL (XEXP (basey
, 1)), basey
= XEXP (basey
, 0);
2390 /* If the bases are different, we know they do not overlap if both
2391 are constants or if one is a constant and the other a pointer into the
2392 stack frame. Otherwise a different base means we can't tell if they
2394 if (! rtx_equal_p (basex
, basey
))
2395 return ((CONSTANT_P (basex
) && CONSTANT_P (basey
))
2396 || (CONSTANT_P (basex
) && REG_P (basey
)
2397 && REGNO_PTR_FRAME_P (REGNO (basey
)))
2398 || (CONSTANT_P (basey
) && REG_P (basex
)
2399 && REGNO_PTR_FRAME_P (REGNO (basex
))));
2401 /* Offset based disambiguation not appropriate for loop invariant */
2405 sizex
= (!MEM_P (rtlx
) ? (int) GET_MODE_SIZE (GET_MODE (rtlx
))
2406 : MEM_SIZE_KNOWN_P (rtlx
) ? MEM_SIZE (rtlx
)
2408 sizey
= (!MEM_P (rtly
) ? (int) GET_MODE_SIZE (GET_MODE (rtly
))
2409 : MEM_SIZE_KNOWN_P (rtly
) ? MEM_SIZE (rtly
)
2412 /* If we have an offset for either memref, it can update the values computed
2414 if (moffsetx_known_p
)
2415 offsetx
+= moffsetx
, sizex
-= moffsetx
;
2416 if (moffsety_known_p
)
2417 offsety
+= moffsety
, sizey
-= moffsety
;
2419 /* If a memref has both a size and an offset, we can use the smaller size.
2420 We can't do this if the offset isn't known because we must view this
2421 memref as being anywhere inside the DECL's MEM. */
2422 if (MEM_SIZE_KNOWN_P (x
) && moffsetx_known_p
)
2423 sizex
= MEM_SIZE (x
);
2424 if (MEM_SIZE_KNOWN_P (y
) && moffsety_known_p
)
2425 sizey
= MEM_SIZE (y
);
2427 /* Put the values of the memref with the lower offset in X's values. */
2428 if (offsetx
> offsety
)
2430 tem
= offsetx
, offsetx
= offsety
, offsety
= tem
;
2431 tem
= sizex
, sizex
= sizey
, sizey
= tem
;
2434 /* If we don't know the size of the lower-offset value, we can't tell
2435 if they conflict. Otherwise, we do the test. */
2436 return sizex
>= 0 && offsety
>= offsetx
+ sizex
;
2439 /* Helper for true_dependence and canon_true_dependence.
2440 Checks for true dependence: X is read after store in MEM takes place.
2442 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be
2443 NULL_RTX, and the canonical addresses of MEM and X are both computed
2444 here. If MEM_CANONICALIZED, then MEM must be already canonicalized.
2446 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0).
2448 Returns 1 if there is a true dependence, 0 otherwise. */
2451 true_dependence_1 (const_rtx mem
, machine_mode mem_mode
, rtx mem_addr
,
2452 const_rtx x
, rtx x_addr
, bool mem_canonicalized
)
2458 gcc_checking_assert (mem_canonicalized
? (mem_addr
!= NULL_RTX
)
2459 : (mem_addr
== NULL_RTX
&& x_addr
== NULL_RTX
));
2461 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2464 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2465 This is used in epilogue deallocation functions, and in cselib. */
2466 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2468 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2470 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2471 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2475 x_addr
= XEXP (x
, 0);
2476 x_addr
= get_addr (x_addr
);
2480 mem_addr
= XEXP (mem
, 0);
2481 if (mem_mode
== VOIDmode
)
2482 mem_mode
= GET_MODE (mem
);
2484 true_mem_addr
= get_addr (mem_addr
);
2486 /* Read-only memory is by definition never modified, and therefore can't
2487 conflict with anything. However, don't assume anything when AND
2488 addresses are involved and leave to the code below to determine
2489 dependence. We don't expect to find read-only set on MEM, but
2490 stupid user tricks can produce them, so don't die. */
2491 if (MEM_READONLY_P (x
)
2492 && GET_CODE (x_addr
) != AND
2493 && GET_CODE (true_mem_addr
) != AND
)
2496 /* If we have MEMs referring to different address spaces (which can
2497 potentially overlap), we cannot easily tell from the addresses
2498 whether the references overlap. */
2499 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2502 base
= find_base_term (x_addr
);
2503 if (base
&& (GET_CODE (base
) == LABEL_REF
2504 || (GET_CODE (base
) == SYMBOL_REF
2505 && CONSTANT_POOL_ADDRESS_P (base
))))
2508 rtx mem_base
= find_base_term (true_mem_addr
);
2509 if (! base_alias_check (x_addr
, base
, true_mem_addr
, mem_base
,
2510 GET_MODE (x
), mem_mode
))
2513 x_addr
= canon_rtx (x_addr
);
2514 if (!mem_canonicalized
)
2515 mem_addr
= canon_rtx (true_mem_addr
);
2517 if ((ret
= memrefs_conflict_p (GET_MODE_SIZE (mem_mode
), mem_addr
,
2518 SIZE_FOR_MODE (x
), x_addr
, 0)) != -1)
2521 if (mems_in_disjoint_alias_sets_p (x
, mem
))
2524 if (nonoverlapping_memrefs_p (mem
, x
, false))
2527 return rtx_refs_may_alias_p (x
, mem
, true);
2530 /* True dependence: X is read after store in MEM takes place. */
2533 true_dependence (const_rtx mem
, machine_mode mem_mode
, const_rtx x
)
2535 return true_dependence_1 (mem
, mem_mode
, NULL_RTX
,
2536 x
, NULL_RTX
, /*mem_canonicalized=*/false);
2539 /* Canonical true dependence: X is read after store in MEM takes place.
2540 Variant of true_dependence which assumes MEM has already been
2541 canonicalized (hence we no longer do that here).
2542 The mem_addr argument has been added, since true_dependence_1 computed
2543 this value prior to canonicalizing. */
2546 canon_true_dependence (const_rtx mem
, machine_mode mem_mode
, rtx mem_addr
,
2547 const_rtx x
, rtx x_addr
)
2549 return true_dependence_1 (mem
, mem_mode
, mem_addr
,
2550 x
, x_addr
, /*mem_canonicalized=*/true);
2553 /* Returns nonzero if a write to X might alias a previous read from
2554 (or, if WRITEP is true, a write to) MEM.
2555 If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
2556 and X_MODE the mode for that access.
2557 If MEM_CANONICALIZED is true, MEM is canonicalized. */
2560 write_dependence_p (const_rtx mem
,
2561 const_rtx x
, machine_mode x_mode
, rtx x_addr
,
2562 bool mem_canonicalized
, bool x_canonicalized
, bool writep
)
2565 rtx true_mem_addr
, true_x_addr
;
2569 gcc_checking_assert (x_canonicalized
2570 ? (x_addr
!= NULL_RTX
&& x_mode
!= VOIDmode
)
2571 : (x_addr
== NULL_RTX
&& x_mode
== VOIDmode
));
2573 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2576 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2577 This is used in epilogue deallocation functions. */
2578 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2580 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2582 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2583 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2587 x_addr
= XEXP (x
, 0);
2588 true_x_addr
= get_addr (x_addr
);
2590 mem_addr
= XEXP (mem
, 0);
2591 true_mem_addr
= get_addr (mem_addr
);
2593 /* A read from read-only memory can't conflict with read-write memory.
2594 Don't assume anything when AND addresses are involved and leave to
2595 the code below to determine dependence. */
2597 && MEM_READONLY_P (mem
)
2598 && GET_CODE (true_x_addr
) != AND
2599 && GET_CODE (true_mem_addr
) != AND
)
2602 /* If we have MEMs referring to different address spaces (which can
2603 potentially overlap), we cannot easily tell from the addresses
2604 whether the references overlap. */
2605 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2608 base
= find_base_term (true_mem_addr
);
2611 && (GET_CODE (base
) == LABEL_REF
2612 || (GET_CODE (base
) == SYMBOL_REF
2613 && CONSTANT_POOL_ADDRESS_P (base
))))
2616 rtx x_base
= find_base_term (true_x_addr
);
2617 if (! base_alias_check (true_x_addr
, x_base
, true_mem_addr
, base
,
2618 GET_MODE (x
), GET_MODE (mem
)))
2621 if (!x_canonicalized
)
2623 x_addr
= canon_rtx (true_x_addr
);
2624 x_mode
= GET_MODE (x
);
2626 if (!mem_canonicalized
)
2627 mem_addr
= canon_rtx (true_mem_addr
);
2629 if ((ret
= memrefs_conflict_p (SIZE_FOR_MODE (mem
), mem_addr
,
2630 GET_MODE_SIZE (x_mode
), x_addr
, 0)) != -1)
2633 if (nonoverlapping_memrefs_p (x
, mem
, false))
2636 return rtx_refs_may_alias_p (x
, mem
, false);
2639 /* Anti dependence: X is written after read in MEM takes place. */
2642 anti_dependence (const_rtx mem
, const_rtx x
)
2644 return write_dependence_p (mem
, x
, VOIDmode
, NULL_RTX
,
2645 /*mem_canonicalized=*/false,
2646 /*x_canonicalized*/false, /*writep=*/false);
2649 /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
2650 Also, consider X in X_MODE (which might be from an enclosing
2651 STRICT_LOW_PART / ZERO_EXTRACT).
2652 If MEM_CANONICALIZED is true, MEM is canonicalized. */
2655 canon_anti_dependence (const_rtx mem
, bool mem_canonicalized
,
2656 const_rtx x
, machine_mode x_mode
, rtx x_addr
)
2658 return write_dependence_p (mem
, x
, x_mode
, x_addr
,
2659 mem_canonicalized
, /*x_canonicalized=*/true,
2663 /* Output dependence: X is written after store in MEM takes place. */
2666 output_dependence (const_rtx mem
, const_rtx x
)
2668 return write_dependence_p (mem
, x
, VOIDmode
, NULL_RTX
,
2669 /*mem_canonicalized=*/false,
2670 /*x_canonicalized*/false, /*writep=*/true);
2675 /* Check whether X may be aliased with MEM. Don't do offset-based
2676 memory disambiguation & TBAA. */
2678 may_alias_p (const_rtx mem
, const_rtx x
)
2680 rtx x_addr
, mem_addr
;
2682 if (MEM_VOLATILE_P (x
) && MEM_VOLATILE_P (mem
))
2685 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
2686 This is used in epilogue deallocation functions. */
2687 if (GET_MODE (x
) == BLKmode
&& GET_CODE (XEXP (x
, 0)) == SCRATCH
)
2689 if (GET_MODE (mem
) == BLKmode
&& GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
2691 if (MEM_ALIAS_SET (x
) == ALIAS_SET_MEMORY_BARRIER
2692 || MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2695 x_addr
= XEXP (x
, 0);
2696 x_addr
= get_addr (x_addr
);
2698 mem_addr
= XEXP (mem
, 0);
2699 mem_addr
= get_addr (mem_addr
);
2701 /* Read-only memory is by definition never modified, and therefore can't
2702 conflict with anything. However, don't assume anything when AND
2703 addresses are involved and leave to the code below to determine
2704 dependence. We don't expect to find read-only set on MEM, but
2705 stupid user tricks can produce them, so don't die. */
2706 if (MEM_READONLY_P (x
)
2707 && GET_CODE (x_addr
) != AND
2708 && GET_CODE (mem_addr
) != AND
)
2711 /* If we have MEMs referring to different address spaces (which can
2712 potentially overlap), we cannot easily tell from the addresses
2713 whether the references overlap. */
2714 if (MEM_ADDR_SPACE (mem
) != MEM_ADDR_SPACE (x
))
2717 rtx x_base
= find_base_term (x_addr
);
2718 rtx mem_base
= find_base_term (mem_addr
);
2719 if (! base_alias_check (x_addr
, x_base
, mem_addr
, mem_base
,
2720 GET_MODE (x
), GET_MODE (mem_addr
)))
2723 if (nonoverlapping_memrefs_p (mem
, x
, true))
2726 /* TBAA not valid for loop_invarint */
2727 return rtx_refs_may_alias_p (x
, mem
, false);
2731 init_alias_target (void)
2735 if (!arg_base_value
)
2736 arg_base_value
= gen_rtx_ADDRESS (VOIDmode
, 0);
2738 memset (static_reg_base_value
, 0, sizeof static_reg_base_value
);
2740 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2741 /* Check whether this register can hold an incoming pointer
2742 argument. FUNCTION_ARG_REGNO_P tests outgoing register
2743 numbers, so translate if necessary due to register windows. */
2744 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i
))
2745 && HARD_REGNO_MODE_OK (i
, Pmode
))
2746 static_reg_base_value
[i
] = arg_base_value
;
2748 static_reg_base_value
[STACK_POINTER_REGNUM
]
2749 = unique_base_value (UNIQUE_BASE_VALUE_SP
);
2750 static_reg_base_value
[ARG_POINTER_REGNUM
]
2751 = unique_base_value (UNIQUE_BASE_VALUE_ARGP
);
2752 static_reg_base_value
[FRAME_POINTER_REGNUM
]
2753 = unique_base_value (UNIQUE_BASE_VALUE_FP
);
2754 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2755 static_reg_base_value
[HARD_FRAME_POINTER_REGNUM
]
2756 = unique_base_value (UNIQUE_BASE_VALUE_HFP
);
2760 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
2761 to be memory reference. */
2762 static bool memory_modified
;
2764 memory_modified_1 (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
2768 if (anti_dependence (x
, (const_rtx
)data
) || output_dependence (x
, (const_rtx
)data
))
2769 memory_modified
= true;
2774 /* Return true when INSN possibly modify memory contents of MEM
2775 (i.e. address can be modified). */
2777 memory_modified_in_insn_p (const_rtx mem
, const_rtx insn
)
2781 memory_modified
= false;
2782 note_stores (PATTERN (insn
), memory_modified_1
, CONST_CAST_RTX(mem
));
2783 return memory_modified
;
2786 /* Return TRUE if the destination of a set is rtx identical to
2789 set_dest_equal_p (const_rtx set
, const_rtx item
)
2791 rtx dest
= SET_DEST (set
);
2792 return rtx_equal_p (dest
, item
);
2795 /* Like memory_modified_in_insn_p, but return TRUE if INSN will
2796 *DEFINITELY* modify the memory contents of MEM. */
2798 memory_must_be_modified_in_insn_p (const_rtx mem
, const_rtx insn
)
2802 insn
= PATTERN (insn
);
2803 if (GET_CODE (insn
) == SET
)
2804 return set_dest_equal_p (insn
, mem
);
2805 else if (GET_CODE (insn
) == PARALLEL
)
2808 for (i
= 0; i
< XVECLEN (insn
, 0); i
++)
2810 rtx sub
= XVECEXP (insn
, 0, i
);
2811 if (GET_CODE (sub
) == SET
2812 && set_dest_equal_p (sub
, mem
))
2819 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
2823 init_alias_analysis (void)
2825 unsigned int maxreg
= max_reg_num ();
2834 timevar_push (TV_ALIAS_ANALYSIS
);
2836 vec_safe_grow_cleared (reg_known_value
, maxreg
- FIRST_PSEUDO_REGISTER
);
2837 reg_known_equiv_p
= sbitmap_alloc (maxreg
- FIRST_PSEUDO_REGISTER
);
2838 bitmap_clear (reg_known_equiv_p
);
2840 /* If we have memory allocated from the previous run, use it. */
2841 if (old_reg_base_value
)
2842 reg_base_value
= old_reg_base_value
;
2845 reg_base_value
->truncate (0);
2847 vec_safe_grow_cleared (reg_base_value
, maxreg
);
2849 new_reg_base_value
= XNEWVEC (rtx
, maxreg
);
2850 reg_seen
= sbitmap_alloc (maxreg
);
2852 /* The basic idea is that each pass through this loop will use the
2853 "constant" information from the previous pass to propagate alias
2854 information through another level of assignments.
2856 The propagation is done on the CFG in reverse post-order, to propagate
2857 things forward as far as possible in each iteration.
2859 This could get expensive if the assignment chains are long. Maybe
2860 we should throttle the number of iterations, possibly based on
2861 the optimization level or flag_expensive_optimizations.
2863 We could propagate more information in the first pass by making use
2864 of DF_REG_DEF_COUNT to determine immediately that the alias information
2865 for a pseudo is "constant".
2867 A program with an uninitialized variable can cause an infinite loop
2868 here. Instead of doing a full dataflow analysis to detect such problems
2869 we just cap the number of iterations for the loop.
2871 The state of the arrays for the set chain in question does not matter
2872 since the program has undefined behavior. */
2874 rpo
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2875 rpo_cnt
= pre_and_rev_post_order_compute (NULL
, rpo
, false);
2880 /* Assume nothing will change this iteration of the loop. */
2883 /* We want to assign the same IDs each iteration of this loop, so
2884 start counting from one each iteration of the loop. */
2887 /* We're at the start of the function each iteration through the
2888 loop, so we're copying arguments. */
2889 copying_arguments
= true;
2891 /* Wipe the potential alias information clean for this pass. */
2892 memset (new_reg_base_value
, 0, maxreg
* sizeof (rtx
));
2894 /* Wipe the reg_seen array clean. */
2895 bitmap_clear (reg_seen
);
2897 /* Initialize the alias information for this pass. */
2898 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2899 if (static_reg_base_value
[i
])
2901 new_reg_base_value
[i
] = static_reg_base_value
[i
];
2902 bitmap_set_bit (reg_seen
, i
);
2905 /* Walk the insns adding values to the new_reg_base_value array. */
2906 for (i
= 0; i
< rpo_cnt
; i
++)
2908 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, rpo
[i
]);
2909 FOR_BB_INSNS (bb
, insn
)
2911 if (NONDEBUG_INSN_P (insn
))
2915 #if defined (HAVE_prologue) || defined (HAVE_epilogue)
2916 /* The prologue/epilogue insns are not threaded onto the
2917 insn chain until after reload has completed. Thus,
2918 there is no sense wasting time checking if INSN is in
2919 the prologue/epilogue until after reload has completed. */
2920 if (reload_completed
2921 && prologue_epilogue_contains (insn
))
2925 /* If this insn has a noalias note, process it, Otherwise,
2926 scan for sets. A simple set will have no side effects
2927 which could change the base value of any other register. */
2929 if (GET_CODE (PATTERN (insn
)) == SET
2930 && REG_NOTES (insn
) != 0
2931 && find_reg_note (insn
, REG_NOALIAS
, NULL_RTX
))
2932 record_set (SET_DEST (PATTERN (insn
)), NULL_RTX
, NULL
);
2934 note_stores (PATTERN (insn
), record_set
, NULL
);
2936 set
= single_set (insn
);
2939 && REG_P (SET_DEST (set
))
2940 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
2942 unsigned int regno
= REGNO (SET_DEST (set
));
2943 rtx src
= SET_SRC (set
);
2946 note
= find_reg_equal_equiv_note (insn
);
2947 if (note
&& REG_NOTE_KIND (note
) == REG_EQUAL
2948 && DF_REG_DEF_COUNT (regno
) != 1)
2951 if (note
!= NULL_RTX
2952 && GET_CODE (XEXP (note
, 0)) != EXPR_LIST
2953 && ! rtx_varies_p (XEXP (note
, 0), 1)
2954 && ! reg_overlap_mentioned_p (SET_DEST (set
),
2957 set_reg_known_value (regno
, XEXP (note
, 0));
2958 set_reg_known_equiv_p (regno
,
2959 REG_NOTE_KIND (note
) == REG_EQUIV
);
2961 else if (DF_REG_DEF_COUNT (regno
) == 1
2962 && GET_CODE (src
) == PLUS
2963 && REG_P (XEXP (src
, 0))
2964 && (t
= get_reg_known_value (REGNO (XEXP (src
, 0))))
2965 && CONST_INT_P (XEXP (src
, 1)))
2967 t
= plus_constant (GET_MODE (src
), t
,
2968 INTVAL (XEXP (src
, 1)));
2969 set_reg_known_value (regno
, t
);
2970 set_reg_known_equiv_p (regno
, false);
2972 else if (DF_REG_DEF_COUNT (regno
) == 1
2973 && ! rtx_varies_p (src
, 1))
2975 set_reg_known_value (regno
, src
);
2976 set_reg_known_equiv_p (regno
, false);
2980 else if (NOTE_P (insn
)
2981 && NOTE_KIND (insn
) == NOTE_INSN_FUNCTION_BEG
)
2982 copying_arguments
= false;
2986 /* Now propagate values from new_reg_base_value to reg_base_value. */
2987 gcc_assert (maxreg
== (unsigned int) max_reg_num ());
2989 for (ui
= 0; ui
< maxreg
; ui
++)
2991 if (new_reg_base_value
[ui
]
2992 && new_reg_base_value
[ui
] != (*reg_base_value
)[ui
]
2993 && ! rtx_equal_p (new_reg_base_value
[ui
], (*reg_base_value
)[ui
]))
2995 (*reg_base_value
)[ui
] = new_reg_base_value
[ui
];
3000 while (changed
&& ++pass
< MAX_ALIAS_LOOP_PASSES
);
3003 /* Fill in the remaining entries. */
3004 FOR_EACH_VEC_ELT (*reg_known_value
, i
, val
)
3006 int regno
= i
+ FIRST_PSEUDO_REGISTER
;
3008 set_reg_known_value (regno
, regno_reg_rtx
[regno
]);
3012 free (new_reg_base_value
);
3013 new_reg_base_value
= 0;
3014 sbitmap_free (reg_seen
);
3016 timevar_pop (TV_ALIAS_ANALYSIS
);
3019 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2).
3020 Special API for var-tracking pass purposes. */
3023 vt_equate_reg_base_value (const_rtx reg1
, const_rtx reg2
)
3025 (*reg_base_value
)[REGNO (reg1
)] = REG_BASE_VALUE (reg2
);
3029 end_alias_analysis (void)
3031 old_reg_base_value
= reg_base_value
;
3032 vec_free (reg_known_value
);
3033 sbitmap_free (reg_known_equiv_p
);
3036 #include "gt-alias.h"