/* Alias analysis for GNU C
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
- 2007, 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
+ Copyright (C) 1997-2015 Free Software Foundation, Inc.
Contributed by John Carr (jfc@mit.edu).
This file is part of GCC.
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
-#include "tm_p.h"
+#include "fold-const.h"
+#include "varasm.h"
+#include "hard-reg-set.h"
#include "function.h"
-#include "alias.h"
+#include "flags.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
#include "emit-rtl.h"
+#include "stmt.h"
+#include "expr.h"
+#include "tm_p.h"
#include "regs.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
-#include "flags.h"
#include "diagnostic-core.h"
+#include "alloc-pool.h"
#include "cselib.h"
-#include "splay-tree.h"
-#include "ggc.h"
#include "langhooks.h"
#include "timevar.h"
#include "dumpfile.h"
#include "target.h"
-#include "cgraph.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
+#include "predict.h"
+#include "basic-block.h"
#include "df.h"
#include "tree-ssa-alias.h"
-#include "pointer-set.h"
-#include "tree-flow.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "gimple-ssa.h"
+#include "rtl-iter.h"
/* The aliasing API provided here solves related but different problems:
struct Z z2, *pz;
- py = &px1.y1;
+ py = &x1.y1;
px2 = &x1;
Consider the four questions:
Can a store to x1 interfere with px2->y1?
Can a store to x1 interfere with px2->z2?
- (*px2).z2
Can a store to x1 change the value pointed to by with py?
Can a store to x1 change the value pointed to by with pz?
a store through a pointer to an X can overwrite any field that is
contained (recursively) in an X (unless we know that px1 != px2).
- The last two of the questions can be solved in the same way as the
- first two questions but this is too conservative. The observation
- is that in some cases analysis we can know if which (if any) fields
- are addressed and if those addresses are used in bad ways. This
- analysis may be language specific. In C, arbitrary operations may
- be applied to pointers. However, there is some indication that
- this may be too conservative for some C++ types.
+ The last two questions can be solved in the same way as the first
+ two questions but this is too conservative. The observation is
+ that in some cases we can know which (if any) fields are addressed
+ and if those addresses are used in bad ways. This analysis may be
+ language specific. In C, arbitrary operations may be applied to
+ pointers. However, there is some indication that this may be too
+ conservative for some C++ types.
The pass ipa-type-escape does this analysis for the types whose
instances do not escape across the compilation boundary.
Historically in GCC, these two problems were combined and a single
- data structure was used to represent the solution to these
+ data structure that was used to represent the solution to these
problems. We now have two similar but different data structures,
- The data structure to solve the last two question is similar to the
- first, but does not contain have the fields in it whose address are
- never taken. For types that do escape the compilation unit, the
- data structures will have identical information.
+ The data structure to solve the last two questions is similar to
+ the first, but does not contain the fields whose address are never
+ taken. For types that do escape the compilation unit, the data
+ structures will have identical information.
*/
/* The alias sets assigned to MEMs assist the back-end in determining
However, this is no actual entry for alias set zero. It is an
error to attempt to explicitly construct a subset of zero. */
+struct alias_set_hash : int_hash <int, INT_MIN, INT_MIN + 1> {};
+
struct GTY(()) alias_set_entry_d {
/* The alias set number, as stored in MEM_ALIAS_SET. */
alias_set_type alias_set;
- /* Nonzero if would have a child of zero: this effectively makes this
- alias set the same as alias set zero. */
- int has_zero_child;
-
/* The children of the alias set. These are not just the immediate
children, but, in fact, all descendants. So, if we have:
continuing our example above, the children here will be all of
`int', `double', `float', and `struct S'. */
- splay_tree GTY((param1_is (int), param2_is (int))) children;
+ hash_map<alias_set_hash, int> *children;
+
+ /* Nonzero if would have a child of zero: this effectively makes this
+ alias set the same as alias set zero. */
+ bool has_zero_child;
+ /* Nonzero if alias set corresponds to pointer type itself (i.e. not to
+ aggregate contaiing pointer.
+ This is used for a special case where we need an universal pointer type
+ compatible with all other pointer types. */
+ bool is_pointer;
+ /* Nonzero if is_pointer or if one of childs have has_pointer set. */
+ bool has_pointer;
};
typedef struct alias_set_entry_d *alias_set_entry;
static int rtx_equal_for_memref_p (const_rtx, const_rtx);
static int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT);
static void record_set (rtx, const_rtx, void *);
-static int base_alias_check (rtx, rtx, enum machine_mode,
- enum machine_mode);
+static int base_alias_check (rtx, rtx, rtx, rtx, machine_mode,
+ machine_mode);
static rtx find_base_value (rtx);
static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx);
-static int insert_subset_children (splay_tree_node, void*);
static alias_set_entry get_alias_set_entry (alias_set_type);
-static bool nonoverlapping_component_refs_p (const_rtx, const_rtx);
static tree decl_for_component_ref (tree);
-static int write_dependence_p (const_rtx, const_rtx, int);
+static int write_dependence_p (const_rtx,
+ const_rtx, machine_mode, rtx,
+ bool, bool, bool);
static void memory_modified_1 (rtx, const_rtx, void *);
+/* Query statistics for the different low-level disambiguators.
+ A high-level query may trigger multiple of them. */
+
+static struct {
+ unsigned long long num_alias_zero;
+ unsigned long long num_same_alias_set;
+ unsigned long long num_same_objects;
+ unsigned long long num_volatile;
+ unsigned long long num_dag;
+ unsigned long long num_universal;
+ unsigned long long num_disambiguated;
+} alias_stats;
+
+
/* Set up all info needed to perform alias analysis on memory references. */
/* Returns the size in bytes of the mode of X. */
The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to
indicate this. */
-static GTY(()) VEC(rtx,gc) *reg_base_value;
+static GTY(()) vec<rtx, va_gc> *reg_base_value;
static rtx *new_reg_base_value;
/* The single VOIDmode ADDRESS that represents all argument bases.
/* We preserve the copy of old array around to avoid amount of garbage
produced. About 8% of garbage produced were attributed to this
array. */
-static GTY((deletable)) VEC(rtx,gc) *old_reg_base_value;
+static GTY((deletable)) vec<rtx, va_gc> *old_reg_base_value;
/* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special
registers. */
#define static_reg_base_value \
(this_target_rtl->x_static_reg_base_value)
-#define REG_BASE_VALUE(X) \
- (REGNO (X) < VEC_length (rtx, reg_base_value) \
- ? VEC_index (rtx, reg_base_value, REGNO (X)) : 0)
+#define REG_BASE_VALUE(X) \
+ (REGNO (X) < vec_safe_length (reg_base_value) \
+ ? (*reg_base_value)[REGNO (X)] : 0)
/* Vector indexed by N giving the initial (unchanging) value known for
pseudo-register N. This vector is initialized in init_alias_analysis,
and does not change until end_alias_analysis is called. */
-static GTY(()) VEC(rtx,gc) *reg_known_value;
+static GTY(()) vec<rtx, va_gc> *reg_known_value;
/* Vector recording for each reg_known_value whether it is due to a
REG_EQUIV note. Future passes (viz., reload) may replace the
NOTE_INSN_FUNCTION_BEG note. */
static bool copying_arguments;
-DEF_VEC_P(alias_set_entry);
-DEF_VEC_ALLOC_P(alias_set_entry,gc);
/* The splay-tree used to store the various alias set entries. */
-static GTY (()) VEC(alias_set_entry,gc) *alias_sets;
+static GTY (()) vec<alias_set_entry, va_gc> *alias_sets;
\f
/* Build a decomposed reference object for querying the alias-oracle
from the MEM rtx and store it in *REF.
if (base == NULL_TREE)
return false;
- /* The tree oracle doesn't like to have these. */
- if (TREE_CODE (base) == FUNCTION_DECL
- || TREE_CODE (base) == LABEL_DECL)
- return false;
-
- /* If this is a pointer dereference of a non-SSA_NAME punt.
- ??? We could replace it with a pointer to anything. */
- if ((INDIRECT_REF_P (base)
- || TREE_CODE (base) == MEM_REF)
- && TREE_CODE (TREE_OPERAND (base, 0)) != SSA_NAME)
- return false;
- if (TREE_CODE (base) == TARGET_MEM_REF
- && TMR_BASE (base)
- && TREE_CODE (TMR_BASE (base)) != SSA_NAME)
+ /* The tree oracle doesn't like bases that are neither decls
+ nor indirect references of SSA names. */
+ if (!(DECL_P (base)
+ || (TREE_CODE (base) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
+ || (TREE_CODE (base) == TARGET_MEM_REF
+ && TREE_CODE (TMR_BASE (base)) == SSA_NAME)))
return false;
/* If this is a reference based on a partitioned decl replace the
- base with an INDIRECT_REF of the pointer representative we
+ base with a MEM_REF of the pointer representative we
created during stack slot partitioning. */
if (TREE_CODE (base) == VAR_DECL
- && ! TREE_STATIC (base)
+ && ! is_global_var (base)
&& cfun->gimple_df->decls_to_pointers != NULL)
{
- void *namep;
- namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers, base);
- if (namep)
- ref->base = build_simple_mem_ref (*(tree *)namep);
- }
- else if (TREE_CODE (base) == TARGET_MEM_REF
- && TREE_CODE (TMR_BASE (base)) == ADDR_EXPR
- && TREE_CODE (TREE_OPERAND (TMR_BASE (base), 0)) == VAR_DECL
- && ! TREE_STATIC (TREE_OPERAND (TMR_BASE (base), 0))
- && cfun->gimple_df->decls_to_pointers != NULL)
- {
- void *namep;
- namep = pointer_map_contains (cfun->gimple_df->decls_to_pointers,
- TREE_OPERAND (TMR_BASE (base), 0));
+ tree *namep = cfun->gimple_df->decls_to_pointers->get (base);
if (namep)
- ref->base = build_simple_mem_ref (*(tree *)namep);
+ ref->base = build_simple_mem_ref (*namep);
}
ref->ref_alias_set = MEM_ALIAS_SET (mem);
if (MEM_EXPR (mem) != get_spill_slot_decl (false)
&& (ref->offset < 0
|| (DECL_P (ref->base)
- && (!host_integerp (DECL_SIZE (ref->base), 1)
- || (TREE_INT_CST_LOW (DECL_SIZE ((ref->base)))
- < (unsigned HOST_WIDE_INT)(ref->offset + ref->size))))))
+ && (DECL_SIZE (ref->base) == NULL_TREE
+ || TREE_CODE (DECL_SIZE (ref->base)) != INTEGER_CST
+ || wi::ltu_p (wi::to_offset (DECL_SIZE (ref->base)),
+ ref->offset + ref->size)))))
return false;
return true;
static inline alias_set_entry
get_alias_set_entry (alias_set_type alias_set)
{
- return VEC_index (alias_set_entry, alias_sets, alias_set);
+ return (*alias_sets)[alias_set];
}
/* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
static inline int
mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2)
{
-/* Perform a basic sanity check. Namely, that there are no alias sets
- if we're not using strict aliasing. This helps to catch bugs
- whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
- where a MEM is allocated in some way other than by the use of
- gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
- use alias sets to indicate that spilled registers cannot alias each
- other, we might need to remove this check. */
- gcc_assert (flag_strict_aliasing
- || (!MEM_ALIAS_SET (mem1) && !MEM_ALIAS_SET (mem2)));
-
- return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
-}
-
-/* Insert the NODE into the splay tree given by DATA. Used by
- record_alias_subset via splay_tree_foreach. */
-
-static int
-insert_subset_children (splay_tree_node node, void *data)
-{
- splay_tree_insert ((splay_tree) data, node->key, node->value);
-
- return 0;
+ return (flag_strict_aliasing
+ && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1),
+ MEM_ALIAS_SET (mem2)));
}
/* Return true if the first alias set is a subset of the second. */
bool
alias_set_subset_of (alias_set_type set1, alias_set_type set2)
{
- alias_set_entry ase;
+ alias_set_entry ase2;
/* Everything is a subset of the "aliases everything" set. */
if (set2 == 0)
return true;
- /* Otherwise, check if set1 is a subset of set2. */
- ase = get_alias_set_entry (set2);
- if (ase != 0
- && (ase->has_zero_child
- || splay_tree_lookup (ase->children,
- (splay_tree_key) set1)))
+ /* Check if set1 is a subset of set2. */
+ ase2 = get_alias_set_entry (set2);
+ if (ase2 != 0
+ && (ase2->has_zero_child
+ || (ase2->children && ase2->children->get (set1))))
return true;
+
+ /* As a special case we consider alias set of "void *" to be both subset
+ and superset of every alias set of a pointer. This extra symmetry does
+ not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p
+ to return true on the following testcase:
+
+ void *ptr;
+ char **ptr2=(char **)&ptr;
+ *ptr2 = ...
+
+ Additionally if a set contains universal pointer, we consider every pointer
+ to be a subset of it, but we do not represent this explicitely - doing so
+ would require us to update transitive closure each time we introduce new
+ pointer type. This makes aliasing_component_refs_p to return true
+ on the following testcase:
+
+ struct a {void *ptr;}
+ char **ptr = (char **)&a.ptr;
+ ptr = ...
+
+ This makes void * truly universal pointer type. See pointer handling in
+ get_alias_set for more details. */
+ if (ase2 && ase2->has_pointer)
+ {
+ alias_set_entry ase1 = get_alias_set_entry (set1);
+
+ if (ase1 && ase1->is_pointer)
+ {
+ alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
+ /* If one is ptr_type_node and other is pointer, then we consider
+ them subset of each other. */
+ if (set1 == voidptr_set || set2 == voidptr_set)
+ return true;
+ /* If SET2 contains universal pointer's alias set, then we consdier
+ every (non-universal) pointer. */
+ if (ase2->children && set1 != voidptr_set
+ && ase2->children->get (voidptr_set))
+ return true;
+ }
+ }
return false;
}
int
alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
{
- alias_set_entry ase;
+ alias_set_entry ase1;
+ alias_set_entry ase2;
/* The easy case. */
if (alias_sets_must_conflict_p (set1, set2))
return 1;
/* See if the first alias set is a subset of the second. */
- ase = get_alias_set_entry (set1);
- if (ase != 0
- && (ase->has_zero_child
- || splay_tree_lookup (ase->children,
- (splay_tree_key) set2)))
- return 1;
+ ase1 = get_alias_set_entry (set1);
+ if (ase1 != 0
+ && ase1->children && ase1->children->get (set2))
+ {
+ ++alias_stats.num_dag;
+ return 1;
+ }
/* Now do the same, but with the alias sets reversed. */
- ase = get_alias_set_entry (set2);
- if (ase != 0
- && (ase->has_zero_child
- || splay_tree_lookup (ase->children,
- (splay_tree_key) set1)))
- return 1;
+ ase2 = get_alias_set_entry (set2);
+ if (ase2 != 0
+ && ase2->children && ase2->children->get (set1))
+ {
+ ++alias_stats.num_dag;
+ return 1;
+ }
+
+ /* We want void * to be compatible with any other pointer without
+ really dropping it to alias set 0. Doing so would make it
+ compatible with all non-pointer types too.
+
+ This is not strictly necessary by the C/C++ language
+ standards, but avoids common type punning mistakes. In
+ addition to that, we need the existence of such universal
+ pointer to implement Fortran's C_PTR type (which is defined as
+ type compatible with all C pointers). */
+ if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer)
+ {
+ alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
+
+ /* If one of the sets corresponds to universal pointer,
+ we consider it to conflict with anything that is
+ or contains pointer. */
+ if (set1 == voidptr_set || set2 == voidptr_set)
+ {
+ ++alias_stats.num_universal;
+ return true;
+ }
+ /* If one of sets is (non-universal) pointer and the other
+ contains universal pointer, we also get conflict. */
+ if (ase1->is_pointer && set2 != voidptr_set
+ && ase2->children && ase2->children->get (voidptr_set))
+ {
+ ++alias_stats.num_universal;
+ return true;
+ }
+ if (ase2->is_pointer && set1 != voidptr_set
+ && ase1->children && ase1->children->get (voidptr_set))
+ {
+ ++alias_stats.num_universal;
+ return true;
+ }
+ }
+
+ ++alias_stats.num_disambiguated;
/* The two alias sets are distinct and neither one is the
child of the other. Therefore, they cannot conflict. */
int
alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2)
{
- if (set1 == 0 || set2 == 0 || set1 == set2)
- return 1;
+ if (set1 == 0 || set2 == 0)
+ {
+ ++alias_stats.num_alias_zero;
+ return 1;
+ }
+ if (set1 == set2)
+ {
+ ++alias_stats.num_same_alias_set;
+ return 1;
+ }
return 0;
}
return 0;
/* If they are the same type, they must conflict. */
- if (t1 == t2
- /* Likewise if both are volatile. */
- || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)))
- return 1;
+ if (t1 == t2)
+ {
+ ++alias_stats.num_same_objects;
+ return 1;
+ }
+ /* Likewise if both are volatile. */
+ if (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2))
+ {
+ ++alias_stats.num_volatile;
+ return 1;
+ }
set1 = t1 ? get_alias_set (t1) : 0;
set2 = t2 ? get_alias_set (t2) : 0;
return alias_sets_must_conflict_p (set1, set2);
}
\f
-/* Return true if all nested component references handled by
- get_inner_reference in T are such that we should use the alias set
- provided by the object at the heart of T.
-
- This is true for non-addressable components (which don't have their
- own alias set), as well as components of objects in alias set zero.
- This later point is a special case wherein we wish to override the
- alias set used by the component, but we don't have per-FIELD_DECL
- assignable alias sets. */
-
-bool
-component_uses_parent_alias_set (const_tree t)
+/* Return the outermost parent of component present in the chain of
+ component references handled by get_inner_reference in T with the
+ following property:
+ - the component is non-addressable, or
+ - the parent has alias set zero,
+ or NULL_TREE if no such parent exists. In the former cases, the alias
+ set of this parent is the alias set that must be used for T itself. */
+
+tree
+component_uses_parent_alias_set_from (const_tree t)
{
- while (1)
- {
- /* If we're at the end, it vacuously uses its own alias set. */
- if (!handled_component_p (t))
- return false;
+ const_tree found = NULL_TREE;
+ while (handled_component_p (t))
+ {
switch (TREE_CODE (t))
{
case COMPONENT_REF:
if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
- return true;
+ found = t;
break;
case ARRAY_REF:
case ARRAY_RANGE_REF:
if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
- return true;
+ found = t;
break;
case REALPART_EXPR:
case IMAGPART_EXPR:
break;
- default:
+ case BIT_FIELD_REF:
+ case VIEW_CONVERT_EXPR:
/* Bitfields and casts are never addressable. */
- return true;
+ found = t;
+ break;
+
+ default:
+ gcc_unreachable ();
}
+ if (get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) == 0)
+ found = t;
+
t = TREE_OPERAND (t, 0);
- if (get_alias_set (TREE_TYPE (t)) == 0)
- return true;
}
+
+ if (found)
+ return TREE_OPERAND (found, 0);
+
+ return NULL_TREE;
+}
+
+
+/* Return whether the pointer-type T effective for aliasing may
+ access everything and thus the reference has to be assigned
+ alias-set zero. */
+
+static bool
+ref_all_alias_ptr_type_p (const_tree t)
+{
+ return (TREE_CODE (TREE_TYPE (t)) == VOID_TYPE
+ || TYPE_REF_CAN_ALIAS_ALL (t));
}
/* Return the alias set for the memory pointed to by T, which may be
static alias_set_type
get_deref_alias_set_1 (tree t)
{
- /* If we're not doing any alias analysis, just assume everything
- aliases everything else. */
- if (!flag_strict_aliasing)
- return 0;
-
/* All we care about is the type. */
if (! TYPE_P (t))
t = TREE_TYPE (t);
/* If we have an INDIRECT_REF via a void pointer, we don't
know anything about what that might alias. Likewise if the
pointer is marked that way. */
- if (TREE_CODE (TREE_TYPE (t)) == VOID_TYPE
- || TYPE_REF_CAN_ALIAS_ALL (t))
+ if (ref_all_alias_ptr_type_p (t))
return 0;
return -1;
alias_set_type
get_deref_alias_set (tree t)
{
+ /* If we're not doing any alias analysis, just assume everything
+ aliases everything else. */
+ if (!flag_strict_aliasing)
+ return 0;
+
alias_set_type set = get_deref_alias_set_1 (t);
/* Fall back to the alias-set of the pointed-to type. */
return set;
}
+/* Return the pointer-type relevant for TBAA purposes from the
+ memory reference tree *T or NULL_TREE in which case *T is
+ adjusted to point to the outermost component reference that
+ can be used for assigning an alias set. */
+
+static tree
+reference_alias_ptr_type_1 (tree *t)
+{
+ tree inner;
+
+ /* Get the base object of the reference. */
+ inner = *t;
+ while (handled_component_p (inner))
+ {
+ /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
+ the type of any component references that wrap it to
+ determine the alias-set. */
+ if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
+ *t = TREE_OPERAND (inner, 0);
+ inner = TREE_OPERAND (inner, 0);
+ }
+
+ /* Handle pointer dereferences here, they can override the
+ alias-set. */
+ if (INDIRECT_REF_P (inner)
+ && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 0))))
+ return TREE_TYPE (TREE_OPERAND (inner, 0));
+ else if (TREE_CODE (inner) == TARGET_MEM_REF)
+ return TREE_TYPE (TMR_OFFSET (inner));
+ else if (TREE_CODE (inner) == MEM_REF
+ && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 1))))
+ return TREE_TYPE (TREE_OPERAND (inner, 1));
+
+ /* If the innermost reference is a MEM_REF that has a
+ conversion embedded treat it like a VIEW_CONVERT_EXPR above,
+ using the memory access type for determining the alias-set. */
+ if (TREE_CODE (inner) == MEM_REF
+ && (TYPE_MAIN_VARIANT (TREE_TYPE (inner))
+ != TYPE_MAIN_VARIANT
+ (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1))))))
+ return TREE_TYPE (TREE_OPERAND (inner, 1));
+
+ /* Otherwise, pick up the outermost object that we could have
+ a pointer to. */
+ tree tem = component_uses_parent_alias_set_from (*t);
+ if (tem)
+ *t = tem;
+
+ return NULL_TREE;
+}
+
+/* Return the pointer-type relevant for TBAA purposes from the
+ gimple memory reference tree T. This is the type to be used for
+ the offset operand of MEM_REF or TARGET_MEM_REF replacements of T
+ and guarantees that get_alias_set will return the same alias
+ set for T and the replacement. */
+
+tree
+reference_alias_ptr_type (tree t)
+{
+ tree ptype = reference_alias_ptr_type_1 (&t);
+ /* If there is a given pointer type for aliasing purposes, return it. */
+ if (ptype != NULL_TREE)
+ return ptype;
+
+ /* Otherwise build one from the outermost component reference we
+ may use. */
+ if (TREE_CODE (t) == MEM_REF
+ || TREE_CODE (t) == TARGET_MEM_REF)
+ return TREE_TYPE (TREE_OPERAND (t, 1));
+ else
+ return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t)));
+}
+
+/* Return whether the pointer-types T1 and T2 used to determine
+ two alias sets of two references will yield the same answer
+ from get_deref_alias_set. */
+
+bool
+alias_ptr_types_compatible_p (tree t1, tree t2)
+{
+ if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
+ return true;
+
+ if (ref_all_alias_ptr_type_p (t1)
+ || ref_all_alias_ptr_type_p (t2))
+ return false;
+
+ return (TYPE_MAIN_VARIANT (TREE_TYPE (t1))
+ == TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
+}
+
+/* Create emptry alias set entry. */
+
+alias_set_entry
+init_alias_set_entry (alias_set_type set)
+{
+ alias_set_entry ase = ggc_alloc<alias_set_entry_d> ();
+ ase->alias_set = set;
+ ase->children = NULL;
+ ase->has_zero_child = false;
+ ase->is_pointer = false;
+ ase->has_pointer = false;
+ gcc_checking_assert (!get_alias_set_entry (set));
+ (*alias_sets)[set] = ase;
+ return ase;
+}
+
/* Return the alias set for T, which may be either a type or an
expression. Call language-specific routine for help, if needed. */
aren't types. */
if (! TYPE_P (t))
{
- tree inner;
-
/* Give the language a chance to do something with this tree
before we look at it. */
STRIP_NOPS (t);
if (set != -1)
return set;
- /* Get the base object of the reference. */
- inner = t;
- while (handled_component_p (inner))
- {
- /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use
- the type of any component references that wrap it to
- determine the alias-set. */
- if (TREE_CODE (inner) == VIEW_CONVERT_EXPR)
- t = TREE_OPERAND (inner, 0);
- inner = TREE_OPERAND (inner, 0);
- }
-
- /* Handle pointer dereferences here, they can override the
- alias-set. */
- if (INDIRECT_REF_P (inner))
- {
- set = get_deref_alias_set_1 (TREE_OPERAND (inner, 0));
- if (set != -1)
- return set;
- }
- else if (TREE_CODE (inner) == TARGET_MEM_REF)
- return get_deref_alias_set (TMR_OFFSET (inner));
- else if (TREE_CODE (inner) == MEM_REF)
- {
- set = get_deref_alias_set_1 (TREE_OPERAND (inner, 1));
- if (set != -1)
- return set;
- }
-
- /* If the innermost reference is a MEM_REF that has a
- conversion embedded treat it like a VIEW_CONVERT_EXPR above,
- using the memory access type for determining the alias-set. */
- if (TREE_CODE (inner) == MEM_REF
- && TYPE_MAIN_VARIANT (TREE_TYPE (inner))
- != TYPE_MAIN_VARIANT
- (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1)))))
- return get_deref_alias_set (TREE_OPERAND (inner, 1));
-
- /* Otherwise, pick up the outermost object that we could have a pointer
- to, processing conversions as above. */
- while (component_uses_parent_alias_set (t))
- {
- t = TREE_OPERAND (t, 0);
- STRIP_NOPS (t);
- }
+ /* Get the alias pointer-type to use or the outermost object
+ that we could have a pointer to. */
+ tree ptype = reference_alias_ptr_type_1 (&t);
+ if (ptype != NULL)
+ return get_deref_alias_set (ptype);
/* If we've already determined the alias set for a decl, just return
it. This is necessary for C++ anonymous unions, whose component
the pointed-to types. This issue has been reported to the
C++ committee.
- In addition to the above canonicalization issue, with LTO
- we should also canonicalize `T (*)[]' to `T *' avoiding
- alias issues with pointer-to element types and pointer-to
- array types.
-
- Likewise we need to deal with the situation of incomplete
- pointed-to types and make `*(struct X **)&a' and
- `*(struct X {} **)&a' alias. Otherwise we will have to
- guarantee that all pointer-to incomplete type variants
- will be replaced by pointer-to complete type variants if
- they are available.
-
- With LTO the convenient situation of using `void *' to
- access and store any pointer type will also become
- more apparent (and `void *' is just another pointer-to
- incomplete type). Assigning alias-set zero to `void *'
- and all pointer-to incomplete types is a not appealing
- solution. Assigning an effective alias-set zero only
- affecting pointers might be - by recording proper subset
- relationships of all pointer alias-sets.
-
- Pointer-to function types are another grey area which
- needs caution. Globbing them all into one alias-set
- or the above effective zero set would work.
-
- For now just assign the same alias-set to all pointers.
- That's simple and avoids all the above problems. */
+ For this reason go to canonical type of the unqalified pointer type.
+ Until GCC 6 this code set all pointers sets to have alias set of
+ ptr_type_node but that is a bad idea, because it prevents disabiguations
+ in between pointers. For Firefox this accounts about 20% of all
+ disambiguations in the program. */
+ else if (POINTER_TYPE_P (t) && t != ptr_type_node && !in_lto_p)
+ {
+ tree p;
+ auto_vec <bool, 8> reference;
+
+ /* Unnest all pointers and references.
+ We also want to make pointer to array equivalent to pointer to its
+ element. So skip all array types, too. */
+ for (p = t; POINTER_TYPE_P (p)
+ || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
+ p = TREE_TYPE (p))
+ {
+ if (TREE_CODE (p) == REFERENCE_TYPE)
+ reference.safe_push (true);
+ if (TREE_CODE (p) == POINTER_TYPE)
+ reference.safe_push (false);
+ }
+ p = TYPE_MAIN_VARIANT (p);
+
+ /* Make void * compatible with char * and also void **.
+ Programs are commonly violating TBAA by this.
+
+ We also make void * to conflict with every pointer
+ (see record_component_aliases) and thus it is safe it to use it for
+ pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
+ if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
+ set = get_alias_set (ptr_type_node);
+ else
+ {
+ /* Rebuild pointer type from starting from canonical types using
+ unqualified pointers and references only. This way all such
+ pointers will have the same alias set and will conflict with
+ each other.
+
+ Most of time we already have pointers or references of a given type.
+ If not we build new one just to be sure that if someone later
+ (probably only middle-end can, as we should assign all alias
+ classes only after finishing translation unit) builds the pointer
+ type, the canonical type will match. */
+ p = TYPE_CANONICAL (p);
+ while (!reference.is_empty ())
+ {
+ if (reference.pop ())
+ p = build_reference_type (p);
+ else
+ p = build_pointer_type (p);
+ p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
+ }
+ gcc_checking_assert (TYPE_CANONICAL (p) == p);
+
+ /* Assign the alias set to both p and t.
+ We can not call get_alias_set (p) here as that would trigger
+ infinite recursion when p == t. In other cases it would just
+ trigger unnecesary legwork of rebuilding the pointer again. */
+ if (TYPE_ALIAS_SET_KNOWN_P (p))
+ set = TYPE_ALIAS_SET (p);
+ else
+ {
+ set = new_alias_set ();
+ TYPE_ALIAS_SET (p) = set;
+ }
+ }
+ }
+ /* In LTO the rules above needs to be part of canonical type machinery.
+ For now just punt. */
else if (POINTER_TYPE_P (t)
- && t != ptr_type_node)
- set = get_alias_set (ptr_type_node);
+ && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
+ set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
/* Otherwise make a new alias set for this type. */
else
if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
record_component_aliases (t);
+ /* We treat pointer types specially in alias_set_subset_of. */
+ if (POINTER_TYPE_P (t) && set)
+ {
+ alias_set_entry ase = get_alias_set_entry (set);
+ if (!ase)
+ ase = init_alias_set_entry (set);
+ ase->is_pointer = true;
+ ase->has_pointer = true;
+ }
+
return set;
}
if (flag_strict_aliasing)
{
if (alias_sets == 0)
- VEC_safe_push (alias_set_entry, gc, alias_sets, (alias_set_entry) 0);
- VEC_safe_push (alias_set_entry, gc, alias_sets, (alias_set_entry) 0);
- return VEC_length (alias_set_entry, alias_sets) - 1;
+ vec_safe_push (alias_sets, (alias_set_entry) 0);
+ vec_safe_push (alias_sets, (alias_set_entry) 0);
+ return alias_sets->length () - 1;
}
else
return 0;
{
/* Create an entry for the SUPERSET, so that we have a place to
attach the SUBSET. */
- superset_entry = ggc_alloc_cleared_alias_set_entry_d ();
- superset_entry->alias_set = superset;
- superset_entry->children
- = splay_tree_new_ggc (splay_tree_compare_ints,
- ggc_alloc_splay_tree_scalar_scalar_splay_tree_s,
- ggc_alloc_splay_tree_scalar_scalar_splay_tree_node_s);
- superset_entry->has_zero_child = 0;
- VEC_replace (alias_set_entry, alias_sets, superset, superset_entry);
+ superset_entry = init_alias_set_entry (superset);
}
if (subset == 0)
else
{
subset_entry = get_alias_set_entry (subset);
+ if (!superset_entry->children)
+ superset_entry->children
+ = hash_map<alias_set_hash, int>::create_ggc (64);
/* If there is an entry for the subset, enter all of its children
(if they are not already present) as children of the SUPERSET. */
if (subset_entry)
{
if (subset_entry->has_zero_child)
- superset_entry->has_zero_child = 1;
+ superset_entry->has_zero_child = true;
+ if (subset_entry->has_pointer)
+ superset_entry->has_pointer = true;
- splay_tree_foreach (subset_entry->children, insert_subset_children,
- superset_entry->children);
+ if (subset_entry->children)
+ {
+ hash_map<alias_set_hash, int>::iterator iter
+ = subset_entry->children->begin ();
+ for (; iter != subset_entry->children->end (); ++iter)
+ superset_entry->children->put ((*iter).first, (*iter).second);
+ }
}
/* Enter the SUBSET itself as a child of the SUPERSET. */
- splay_tree_insert (superset_entry->children,
- (splay_tree_key) subset, 0);
+ superset_entry->children->put (subset, 0);
}
}
case RECORD_TYPE:
case UNION_TYPE:
case QUAL_UNION_TYPE:
- /* Recursively record aliases for the base classes, if there are any. */
- if (TYPE_BINFO (type))
- {
- int i;
- tree binfo, base_binfo;
-
- for (binfo = TYPE_BINFO (type), i = 0;
- BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
- record_alias_subset (superset,
- get_alias_set (BINFO_TYPE (base_binfo)));
- }
for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
The test above is not sufficient because the scheduler may move
a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
- && regno < VEC_length (rtx, reg_base_value))
+ && regno < vec_safe_length (reg_base_value))
{
/* If we're inside init_alias_analysis, use new_reg_base_value
to reduce the number of relaxation iterations. */
&& DF_REG_DEF_COUNT (regno) == 1)
return new_reg_base_value[regno];
- if (VEC_index (rtx, reg_base_value, regno))
- return VEC_index (rtx, reg_base_value, regno);
+ if ((*reg_base_value)[regno])
+ return (*reg_base_value)[regno];
}
return 0;
/* While scanning insns to find base values, reg_seen[N] is nonzero if
register N has been set in this function. */
-static char *reg_seen;
+static sbitmap reg_seen;
static void
record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED)
regno = REGNO (dest);
- gcc_checking_assert (regno < VEC_length (rtx, reg_base_value));
+ gcc_checking_assert (regno < reg_base_value->length ());
- /* If this spans multiple hard registers, then we must indicate that every
- register has an unusable value. */
- if (regno < FIRST_PSEUDO_REGISTER)
- n = hard_regno_nregs[regno][GET_MODE (dest)];
- else
- n = 1;
+ n = REG_NREGS (dest);
if (n != 1)
{
while (--n >= 0)
{
- reg_seen[regno + n] = 1;
+ bitmap_set_bit (reg_seen, regno + n);
new_reg_base_value[regno + n] = 0;
}
return;
else
{
/* There's a REG_NOALIAS note against DEST. */
- if (reg_seen[regno])
+ if (bitmap_bit_p (reg_seen, regno))
{
new_reg_base_value[regno] = 0;
return;
}
- reg_seen[regno] = 1;
+ bitmap_set_bit (reg_seen, regno);
new_reg_base_value[regno] = unique_base_value (unique_id++);
return;
}
}
/* If this is the first set of a register, record the value. */
else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
- && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
+ && ! bitmap_bit_p (reg_seen, regno) && new_reg_base_value[regno] == 0)
new_reg_base_value[regno] = find_base_value (src);
- reg_seen[regno] = 1;
+ bitmap_set_bit (reg_seen, regno);
}
/* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid
rtx
get_reg_base_value (unsigned int regno)
{
- return VEC_index (rtx, reg_base_value, regno);
+ return (*reg_base_value)[regno];
}
/* If a value is known for REGNO, return it. */
if (regno >= FIRST_PSEUDO_REGISTER)
{
regno -= FIRST_PSEUDO_REGISTER;
- if (regno < VEC_length (rtx, reg_known_value))
- return VEC_index (rtx, reg_known_value, regno);
+ if (regno < vec_safe_length (reg_known_value))
+ return (*reg_known_value)[regno];
}
return NULL;
}
if (regno >= FIRST_PSEUDO_REGISTER)
{
regno -= FIRST_PSEUDO_REGISTER;
- if (regno < VEC_length (rtx, reg_known_value))
- VEC_replace (rtx, reg_known_value, regno, val);
+ if (regno < vec_safe_length (reg_known_value))
+ (*reg_known_value)[regno] = val;
}
}
if (regno >= FIRST_PSEUDO_REGISTER)
{
regno -= FIRST_PSEUDO_REGISTER;
- if (regno < VEC_length (rtx, reg_known_value))
- return TEST_BIT (reg_known_equiv_p, regno);
+ if (regno < vec_safe_length (reg_known_value))
+ return bitmap_bit_p (reg_known_equiv_p, regno);
}
return false;
}
if (regno >= FIRST_PSEUDO_REGISTER)
{
regno -= FIRST_PSEUDO_REGISTER;
- if (regno < VEC_length (rtx, reg_known_value))
+ if (regno < vec_safe_length (reg_known_value))
{
if (val)
- SET_BIT (reg_known_equiv_p, regno);
+ bitmap_set_bit (reg_known_equiv_p, regno);
else
- RESET_BIT (reg_known_equiv_p, regno);
+ bitmap_clear_bit (reg_known_equiv_p, regno);
}
}
}
return REGNO (x) == REGNO (y);
case LABEL_REF:
- return XEXP (x, 0) == XEXP (y, 0);
+ return LABEL_REF_LABEL (x) == LABEL_REF_LABEL (y);
case SYMBOL_REF:
return XSTR (x, 0) == XSTR (y, 0);
+ case ENTRY_VALUE:
+ /* This is magic, don't go through canonicalization et al. */
+ return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
+
case VALUE:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST_FIXED:
- /* There's no need to compare the contents of CONST_DOUBLEs or
- CONST_INTs because pointer equality is a good enough
- comparison for these nodes. */
+ CASE_CONST_UNIQUE:
+ /* Pointer equality guarantees equality for these nodes. */
return 0;
default:
if (!val)
return ret;
+ if (cselib_sp_based_value_p (val))
+ return static_reg_base_value[STACK_POINTER_REGNUM];
+
f = val->locs;
/* Temporarily reset val->locs to avoid infinite recursion. */
val->locs = NULL;
if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2))
return find_base_term (tmp2);
- /* If either operand is known to be a pointer, then use it
+ /* If either operand is known to be a pointer, then prefer it
to determine the base term. */
if (REG_P (tmp1) && REG_POINTER (tmp1))
- {
- rtx base = find_base_term (tmp1);
- if (base)
- return base;
- }
-
- if (REG_P (tmp2) && REG_POINTER (tmp2))
- {
- rtx base = find_base_term (tmp2);
- if (base)
- return base;
- }
-
- /* Neither operand was known to be a pointer. Go ahead and find the
- base term for both operands. */
- tmp1 = find_base_term (tmp1);
- tmp2 = find_base_term (tmp2);
-
- /* If either base term is named object or a special address
+ ;
+ else if (REG_P (tmp2) && REG_POINTER (tmp2))
+ std::swap (tmp1, tmp2);
+ /* If second argument is constant which has base term, prefer it
+ over variable tmp1. See PR64025. */
+ else if (CONSTANT_P (tmp2) && !CONST_INT_P (tmp2))
+ std::swap (tmp1, tmp2);
+
+ /* Go ahead and find the base term for both operands. If either base
+ term is from a pointer or is a named object or a special address
(like an argument or stack reference), then use it for the
base term. */
- if (tmp1 != 0 && known_base_value_p (tmp1))
- return tmp1;
-
- if (tmp2 != 0 && known_base_value_p (tmp2))
- return tmp2;
+ rtx base = find_base_term (tmp1);
+ if (base != NULL_RTX
+ && ((REG_P (tmp1) && REG_POINTER (tmp1))
+ || known_base_value_p (base)))
+ return base;
+ base = find_base_term (tmp2);
+ if (base != NULL_RTX
+ && ((REG_P (tmp2) && REG_POINTER (tmp2))
+ || known_base_value_p (base)))
+ return base;
/* We could not determine which of the two operands was the
base register and which was the index. So we can determine
objects, 1 if they might be pointers to the same object. */
static int
-base_alias_check (rtx x, rtx y, enum machine_mode x_mode,
- enum machine_mode y_mode)
+base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base,
+ machine_mode x_mode, machine_mode y_mode)
{
- rtx x_base = find_base_term (x);
- rtx y_base = find_base_term (y);
-
/* If the address itself has no known base see if a known equivalent
value has one. If either address still has no known base, nothing
is known about aliasing. */
return 1;
}
-/* Callback for for_each_rtx, that returns 1 upon encountering a VALUE
- whose UID is greater than the int uid that D points to. */
-
-static int
-refs_newer_value_cb (rtx *x, void *d)
-{
- if (GET_CODE (*x) == VALUE && CSELIB_VAL_PTR (*x)->uid > *(int *)d)
- return 1;
-
- return 0;
-}
-
/* Return TRUE if EXPR refers to a VALUE whose uid is greater than
that of V. */
static bool
-refs_newer_value_p (rtx expr, rtx v)
+refs_newer_value_p (const_rtx expr, rtx v)
{
int minuid = CSELIB_VAL_PTR (v)->uid;
-
- return for_each_rtx (&expr, refs_newer_value_cb, &minuid);
+ subrtx_iterator::array_type array;
+ FOR_EACH_SUBRTX (iter, array, expr, NONCONST)
+ if (GET_CODE (*iter) == VALUE && CSELIB_VAL_PTR (*iter)->uid > minuid)
+ return true;
+ return false;
}
/* Convert the address X into something we can use. This is done by returning
if (offset)
addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0),
- GEN_INT (offset));
+ gen_int_mode (offset, GET_MODE (addr)));
else
addr = XEXP (addr, 0);
addr = canon_rtx (addr);
return addr;
}
+/* Return TRUE if an object X sized at XSIZE bytes and another object
+ Y sized at YSIZE bytes, starting C bytes after X, may overlap. If
+ any of the sizes is zero, assume an overlap, otherwise use the
+ absolute value of the sizes as the actual sizes. */
+
+static inline bool
+offset_overlap_p (HOST_WIDE_INT c, int xsize, int ysize)
+{
+ return (xsize == 0 || ysize == 0
+ || (c >= 0
+ ? (abs (xsize) > c)
+ : (abs (ysize) > -c)));
+}
+
/* Return one if X and Y (memory addresses) reference the
same location in memory or if the references overlap.
Return zero if they do not overlap, else return
else if (GET_CODE (x) == LO_SUM)
x = XEXP (x, 1);
else
- x = addr_side_effect_eval (x, xsize, 0);
+ x = addr_side_effect_eval (x, abs (xsize), 0);
if (GET_CODE (y) == HIGH)
y = XEXP (y, 0);
else if (GET_CODE (y) == LO_SUM)
y = XEXP (y, 1);
else
- y = addr_side_effect_eval (y, ysize, 0);
+ y = addr_side_effect_eval (y, abs (ysize), 0);
if (rtx_equal_for_memref_p (x, y))
{
- if (xsize <= 0 || ysize <= 0)
- return 1;
- if (c >= 0 && xsize > c)
- return 1;
- if (c < 0 && ysize+c > 0)
- return 1;
- return 0;
+ return offset_overlap_p (c, xsize, ysize);
}
/* This code used to check for conflicts involving stack references and
x0 = canon_rtx (XEXP (x, 0));
y0 = canon_rtx (XEXP (y, 0));
if (rtx_equal_for_memref_p (x0, y0))
- return (xsize == 0 || ysize == 0
- || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
+ return offset_overlap_p (c, xsize, ysize);
/* Can't properly adjust our sizes. */
if (!CONST_INT_P (x1))
/* Deal with alignment ANDs by adjusting offset and size so as to
cover the maximum range, without taking any previously known
- alignment into account. */
+ alignment into account. Make a size negative after such an
+ adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we
+ assume a potential overlap, because they may end up in contiguous
+ memory locations and the stricter-alignment access may span over
+ part of both. */
if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1)))
{
HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
unsigned HOST_WIDE_INT uc = sc;
- if (xsize > 0 && sc < 0 && -uc == (uc & -uc))
+ if (sc < 0 && -uc == (uc & -uc))
{
- xsize -= sc + 1;
+ if (xsize > 0)
+ xsize = -xsize;
+ if (xsize)
+ xsize += sc + 1;
c -= sc + 1;
return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
ysize, y, c);
{
HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
unsigned HOST_WIDE_INT uc = sc;
- if (ysize > 0 && sc < 0 && -uc == (uc & -uc))
+ if (sc < 0 && -uc == (uc & -uc))
{
- ysize -= sc + 1;
+ if (ysize > 0)
+ ysize = -ysize;
+ if (ysize)
+ ysize += sc + 1;
c += sc + 1;
return memrefs_conflict_p (xsize, x,
ysize, canon_rtx (XEXP (y, 0)), c);
if (CONST_INT_P (x) && CONST_INT_P (y))
{
c += (INTVAL (y) - INTVAL (x));
- return (xsize <= 0 || ysize <= 0
- || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
+ return offset_overlap_p (c, xsize, ysize);
}
if (GET_CODE (x) == CONST)
return memrefs_conflict_p (xsize, x, ysize,
canon_rtx (XEXP (y, 0)), c);
+ /* Assume a potential overlap for symbolic addresses that went
+ through alignment adjustments (i.e., that have negative
+ sizes), because we can't know how far they are from each
+ other. */
if (CONSTANT_P (y))
- return (xsize <= 0 || ysize <= 0
- || (rtx_equal_for_memref_p (x, y)
- && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))));
+ return (xsize < 0 || ysize < 0 || offset_overlap_p (c, xsize, ysize));
return -1;
}
storeqi_unaligned pattern. */
/* Read dependence: X is read after read in MEM takes place. There can
- only be a dependence here if both reads are volatile. */
+ only be a dependence here if both reads are volatile, or if either is
+ an explicit barrier. */
int
read_dependence (const_rtx mem, const_rtx x)
{
- return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
-}
-
-/* Return true if we can determine that the fields referenced cannot
- overlap for any pair of objects. */
-
-static bool
-nonoverlapping_component_refs_p (const_rtx rtlx, const_rtx rtly)
-{
- const_tree x = MEM_EXPR (rtlx), y = MEM_EXPR (rtly);
- const_tree fieldx, fieldy, typex, typey, orig_y;
-
- if (!flag_strict_aliasing
- || !x || !y
- || TREE_CODE (x) != COMPONENT_REF
- || TREE_CODE (y) != COMPONENT_REF)
- return false;
-
- do
- {
- /* The comparison has to be done at a common type, since we don't
- know how the inheritance hierarchy works. */
- orig_y = y;
- do
- {
- fieldx = TREE_OPERAND (x, 1);
- typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
-
- y = orig_y;
- do
- {
- fieldy = TREE_OPERAND (y, 1);
- typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
-
- if (typex == typey)
- goto found;
-
- y = TREE_OPERAND (y, 0);
- }
- while (y && TREE_CODE (y) == COMPONENT_REF);
-
- x = TREE_OPERAND (x, 0);
- }
- while (x && TREE_CODE (x) == COMPONENT_REF);
- /* Never found a common type. */
- return false;
-
- found:
- /* If we're left with accessing different fields of a structure,
- then no overlap. */
- if (TREE_CODE (typex) == RECORD_TYPE
- && fieldx != fieldy)
- return true;
-
- /* The comparison on the current field failed. If we're accessing
- a very nested structure, look at the next outer level. */
- x = TREE_OPERAND (x, 0);
- y = TREE_OPERAND (y, 0);
- }
- while (x && y
- && TREE_CODE (x) == COMPONENT_REF
- && TREE_CODE (y) == COMPONENT_REF);
-
+ if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
+ return true;
+ if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
+ || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
+ return true;
return false;
}
{
tree xoffset = component_ref_field_offset (x);
tree field = TREE_OPERAND (x, 1);
+ if (TREE_CODE (xoffset) != INTEGER_CST)
+ {
+ *known_p = false;
+ return;
+ }
- if (! host_integerp (xoffset, 1))
+ offset_int woffset
+ = (wi::to_offset (xoffset)
+ + wi::lrshift (wi::to_offset (DECL_FIELD_BIT_OFFSET (field)),
+ LOG2_BITS_PER_UNIT));
+ if (!wi::fits_uhwi_p (woffset))
{
*known_p = false;
return;
}
- *offset += (tree_low_cst (xoffset, 1)
- + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
- / BITS_PER_UNIT));
+ *offset += woffset.to_uhwi ();
x = TREE_OPERAND (x, 0);
}
Returns 1 if there is a true dependence, 0 otherwise. */
static int
-true_dependence_1 (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
+true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
const_rtx x, rtx x_addr, bool mem_canonicalized)
{
+ rtx true_mem_addr;
rtx base;
int ret;
|| MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
return 1;
- /* Read-only memory is by definition never modified, and therefore can't
- conflict with anything. We don't expect to find read-only set on MEM,
- but stupid user tricks can produce them, so don't die. */
- if (MEM_READONLY_P (x))
- return 0;
-
- /* If we have MEMs referring to different address spaces (which can
- potentially overlap), we cannot easily tell from the addresses
- whether the references overlap. */
- if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
- return 1;
+ if (! x_addr)
+ x_addr = XEXP (x, 0);
+ x_addr = get_addr (x_addr);
if (! mem_addr)
{
if (mem_mode == VOIDmode)
mem_mode = GET_MODE (mem);
}
+ true_mem_addr = get_addr (mem_addr);
- if (! x_addr)
- {
- x_addr = XEXP (x, 0);
- if (!((GET_CODE (x_addr) == VALUE
- && GET_CODE (mem_addr) != VALUE
- && reg_mentioned_p (x_addr, mem_addr))
- || (GET_CODE (x_addr) != VALUE
- && GET_CODE (mem_addr) == VALUE
- && reg_mentioned_p (mem_addr, x_addr))))
- {
- x_addr = get_addr (x_addr);
- if (! mem_canonicalized)
- mem_addr = get_addr (mem_addr);
- }
- }
+ /* Read-only memory is by definition never modified, and therefore can't
+ conflict with anything. However, don't assume anything when AND
+ addresses are involved and leave to the code below to determine
+ dependence. We don't expect to find read-only set on MEM, but
+ stupid user tricks can produce them, so don't die. */
+ if (MEM_READONLY_P (x)
+ && GET_CODE (x_addr) != AND
+ && GET_CODE (true_mem_addr) != AND)
+ return 0;
+
+ /* If we have MEMs referring to different address spaces (which can
+ potentially overlap), we cannot easily tell from the addresses
+ whether the references overlap. */
+ if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
+ return 1;
base = find_base_term (x_addr);
if (base && (GET_CODE (base) == LABEL_REF
&& CONSTANT_POOL_ADDRESS_P (base))))
return 0;
- if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
+ rtx mem_base = find_base_term (true_mem_addr);
+ if (! base_alias_check (x_addr, base, true_mem_addr, mem_base,
+ GET_MODE (x), mem_mode))
return 0;
x_addr = canon_rtx (x_addr);
if (!mem_canonicalized)
- mem_addr = canon_rtx (mem_addr);
+ mem_addr = canon_rtx (true_mem_addr);
if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
SIZE_FOR_MODE (x), x_addr, 0)) != -1)
if (nonoverlapping_memrefs_p (mem, x, false))
return 0;
- if (nonoverlapping_component_refs_p (mem, x))
- return 0;
-
return rtx_refs_may_alias_p (x, mem, true);
}
/* True dependence: X is read after store in MEM takes place. */
int
-true_dependence (const_rtx mem, enum machine_mode mem_mode, const_rtx x)
+true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x)
{
return true_dependence_1 (mem, mem_mode, NULL_RTX,
x, NULL_RTX, /*mem_canonicalized=*/false);
this value prior to canonicalizing. */
int
-canon_true_dependence (const_rtx mem, enum machine_mode mem_mode, rtx mem_addr,
+canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr,
const_rtx x, rtx x_addr)
{
return true_dependence_1 (mem, mem_mode, mem_addr,
}
/* Returns nonzero if a write to X might alias a previous read from
- (or, if WRITEP is nonzero, a write to) MEM. */
+ (or, if WRITEP is true, a write to) MEM.
+ If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X,
+ and X_MODE the mode for that access.
+ If MEM_CANONICALIZED is true, MEM is canonicalized. */
static int
-write_dependence_p (const_rtx mem, const_rtx x, int writep)
+write_dependence_p (const_rtx mem,
+ const_rtx x, machine_mode x_mode, rtx x_addr,
+ bool mem_canonicalized, bool x_canonicalized, bool writep)
{
- rtx x_addr, mem_addr;
+ rtx mem_addr;
+ rtx true_mem_addr, true_x_addr;
rtx base;
int ret;
+ gcc_checking_assert (x_canonicalized
+ ? (x_addr != NULL_RTX && x_mode != VOIDmode)
+ : (x_addr == NULL_RTX && x_mode == VOIDmode));
+
if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
return 1;
|| MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
return 1;
- /* A read from read-only memory can't conflict with read-write memory. */
- if (!writep && MEM_READONLY_P (mem))
+ if (!x_addr)
+ x_addr = XEXP (x, 0);
+ true_x_addr = get_addr (x_addr);
+
+ mem_addr = XEXP (mem, 0);
+ true_mem_addr = get_addr (mem_addr);
+
+ /* A read from read-only memory can't conflict with read-write memory.
+ Don't assume anything when AND addresses are involved and leave to
+ the code below to determine dependence. */
+ if (!writep
+ && MEM_READONLY_P (mem)
+ && GET_CODE (true_x_addr) != AND
+ && GET_CODE (true_mem_addr) != AND)
return 0;
/* If we have MEMs referring to different address spaces (which can
if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
return 1;
- x_addr = XEXP (x, 0);
- mem_addr = XEXP (mem, 0);
- if (!((GET_CODE (x_addr) == VALUE
- && GET_CODE (mem_addr) != VALUE
- && reg_mentioned_p (x_addr, mem_addr))
- || (GET_CODE (x_addr) != VALUE
- && GET_CODE (mem_addr) == VALUE
- && reg_mentioned_p (mem_addr, x_addr))))
- {
- x_addr = get_addr (x_addr);
- mem_addr = get_addr (mem_addr);
- }
-
- if (! writep)
- {
- base = find_base_term (mem_addr);
- if (base && (GET_CODE (base) == LABEL_REF
- || (GET_CODE (base) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (base))))
- return 0;
- }
+ base = find_base_term (true_mem_addr);
+ if (! writep
+ && base
+ && (GET_CODE (base) == LABEL_REF
+ || (GET_CODE (base) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (base))))
+ return 0;
- if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
- GET_MODE (mem)))
+ rtx x_base = find_base_term (true_x_addr);
+ if (! base_alias_check (true_x_addr, x_base, true_mem_addr, base,
+ GET_MODE (x), GET_MODE (mem)))
return 0;
- x_addr = canon_rtx (x_addr);
- mem_addr = canon_rtx (mem_addr);
+ if (!x_canonicalized)
+ {
+ x_addr = canon_rtx (true_x_addr);
+ x_mode = GET_MODE (x);
+ }
+ if (!mem_canonicalized)
+ mem_addr = canon_rtx (true_mem_addr);
if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
- SIZE_FOR_MODE (x), x_addr, 0)) != -1)
+ GET_MODE_SIZE (x_mode), x_addr, 0)) != -1)
return ret;
if (nonoverlapping_memrefs_p (x, mem, false))
int
anti_dependence (const_rtx mem, const_rtx x)
{
- return write_dependence_p (mem, x, /*writep=*/0);
+ return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
+ /*mem_canonicalized=*/false,
+ /*x_canonicalized*/false, /*writep=*/false);
+}
+
+/* Likewise, but we already have a canonicalized MEM, and X_ADDR for X.
+ Also, consider X in X_MODE (which might be from an enclosing
+ STRICT_LOW_PART / ZERO_EXTRACT).
+ If MEM_CANONICALIZED is true, MEM is canonicalized. */
+
+int
+canon_anti_dependence (const_rtx mem, bool mem_canonicalized,
+ const_rtx x, machine_mode x_mode, rtx x_addr)
+{
+ return write_dependence_p (mem, x, x_mode, x_addr,
+ mem_canonicalized, /*x_canonicalized=*/true,
+ /*writep=*/false);
}
/* Output dependence: X is written after store in MEM takes place. */
int
output_dependence (const_rtx mem, const_rtx x)
{
- return write_dependence_p (mem, x, /*writep=*/1);
+ return write_dependence_p (mem, x, VOIDmode, NULL_RTX,
+ /*mem_canonicalized=*/false,
+ /*x_canonicalized*/false, /*writep=*/true);
}
\f
|| MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
return 1;
+ x_addr = XEXP (x, 0);
+ x_addr = get_addr (x_addr);
+
+ mem_addr = XEXP (mem, 0);
+ mem_addr = get_addr (mem_addr);
+
/* Read-only memory is by definition never modified, and therefore can't
- conflict with anything. We don't expect to find read-only set on MEM,
- but stupid user tricks can produce them, so don't die. */
- if (MEM_READONLY_P (x))
+ conflict with anything. However, don't assume anything when AND
+ addresses are involved and leave to the code below to determine
+ dependence. We don't expect to find read-only set on MEM, but
+ stupid user tricks can produce them, so don't die. */
+ if (MEM_READONLY_P (x)
+ && GET_CODE (x_addr) != AND
+ && GET_CODE (mem_addr) != AND)
return 0;
/* If we have MEMs referring to different address spaces (which can
if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
return 1;
- x_addr = XEXP (x, 0);
- mem_addr = XEXP (mem, 0);
- if (!((GET_CODE (x_addr) == VALUE
- && GET_CODE (mem_addr) != VALUE
- && reg_mentioned_p (x_addr, mem_addr))
- || (GET_CODE (x_addr) != VALUE
- && GET_CODE (mem_addr) == VALUE
- && reg_mentioned_p (mem_addr, x_addr))))
- {
- x_addr = get_addr (x_addr);
- mem_addr = get_addr (mem_addr);
- }
-
- if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), GET_MODE (mem_addr)))
+ rtx x_base = find_base_term (x_addr);
+ rtx mem_base = find_base_term (mem_addr);
+ if (! base_alias_check (x_addr, x_base, mem_addr, mem_base,
+ GET_MODE (x), GET_MODE (mem_addr)))
return 0;
- x_addr = canon_rtx (x_addr);
- mem_addr = canon_rtx (mem_addr);
-
if (nonoverlapping_memrefs_p (mem, x, true))
return 0;
= unique_base_value (UNIQUE_BASE_VALUE_ARGP);
static_reg_base_value[FRAME_POINTER_REGNUM]
= unique_base_value (UNIQUE_BASE_VALUE_FP);
-#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
- static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
- = unique_base_value (UNIQUE_BASE_VALUE_HFP);
-#endif
+ if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
+ static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
+ = unique_base_value (UNIQUE_BASE_VALUE_HFP);
}
/* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
return memory_modified;
}
+/* Return TRUE if the destination of a set is rtx identical to
+ ITEM. */
+static inline bool
+set_dest_equal_p (const_rtx set, const_rtx item)
+{
+ rtx dest = SET_DEST (set);
+ return rtx_equal_p (dest, item);
+}
+
+/* Like memory_modified_in_insn_p, but return TRUE if INSN will
+ *DEFINITELY* modify the memory contents of MEM. */
+bool
+memory_must_be_modified_in_insn_p (const_rtx mem, const_rtx insn)
+{
+ if (!INSN_P (insn))
+ return false;
+ insn = PATTERN (insn);
+ if (GET_CODE (insn) == SET)
+ return set_dest_equal_p (insn, mem);
+ else if (GET_CODE (insn) == PARALLEL)
+ {
+ int i;
+ for (i = 0; i < XVECLEN (insn, 0); i++)
+ {
+ rtx sub = XVECEXP (insn, 0, i);
+ if (GET_CODE (sub) == SET
+ && set_dest_equal_p (sub, mem))
+ return true;
+ }
+ }
+ return false;
+}
+
/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
array. */
int changed, pass;
int i;
unsigned int ui;
- rtx insn, val;
+ rtx_insn *insn;
+ rtx val;
int rpo_cnt;
int *rpo;
timevar_push (TV_ALIAS_ANALYSIS);
- reg_known_value = VEC_alloc (rtx, gc, maxreg - FIRST_PSEUDO_REGISTER);
+ vec_safe_grow_cleared (reg_known_value, maxreg - FIRST_PSEUDO_REGISTER);
reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER);
+ bitmap_clear (reg_known_equiv_p);
/* If we have memory allocated from the previous run, use it. */
if (old_reg_base_value)
reg_base_value = old_reg_base_value;
if (reg_base_value)
- VEC_truncate (rtx, reg_base_value, 0);
+ reg_base_value->truncate (0);
- VEC_safe_grow_cleared (rtx, gc, reg_base_value, maxreg);
+ vec_safe_grow_cleared (reg_base_value, maxreg);
new_reg_base_value = XNEWVEC (rtx, maxreg);
- reg_seen = XNEWVEC (char, maxreg);
+ reg_seen = sbitmap_alloc (maxreg);
/* The basic idea is that each pass through this loop will use the
"constant" information from the previous pass to propagate alias
The state of the arrays for the set chain in question does not matter
since the program has undefined behavior. */
- rpo = XNEWVEC (int, n_basic_blocks);
+ rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
pass = 0;
memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
/* Wipe the reg_seen array clean. */
- memset (reg_seen, 0, maxreg);
-
- /* Mark all hard registers which may contain an address.
- The stack, frame and argument pointers may contain an address.
- An argument register which can hold a Pmode value may contain
- an address even if it is not in BASE_REGS.
-
- The address expression is VOIDmode for an argument and
- Pmode for other registers. */
+ bitmap_clear (reg_seen);
- memcpy (new_reg_base_value, static_reg_base_value,
- FIRST_PSEUDO_REGISTER * sizeof (rtx));
+ /* Initialize the alias information for this pass. */
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (static_reg_base_value[i])
+ {
+ new_reg_base_value[i] = static_reg_base_value[i];
+ bitmap_set_bit (reg_seen, i);
+ }
/* Walk the insns adding values to the new_reg_base_value array. */
for (i = 0; i < rpo_cnt; i++)
{
- basic_block bb = BASIC_BLOCK (rpo[i]);
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
FOR_BB_INSNS (bb, insn)
{
if (NONDEBUG_INSN_P (insn))
{
rtx note, set;
-#if defined (HAVE_prologue) || defined (HAVE_epilogue)
+#if defined (HAVE_prologue)
+ static const bool prologue = true;
+#else
+ static const bool prologue = false;
+#endif
+
/* The prologue/epilogue insns are not threaded onto the
insn chain until after reload has completed. Thus,
there is no sense wasting time checking if INSN is in
the prologue/epilogue until after reload has completed. */
- if (reload_completed
+ if ((prologue || HAVE_epilogue) && reload_completed
&& prologue_epilogue_contains (insn))
continue;
-#endif
/* If this insn has a noalias note, process it, Otherwise,
scan for sets. A simple set will have no side effects
for (ui = 0; ui < maxreg; ui++)
{
if (new_reg_base_value[ui]
- && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui)
- && ! rtx_equal_p (new_reg_base_value[ui],
- VEC_index (rtx, reg_base_value, ui)))
+ && new_reg_base_value[ui] != (*reg_base_value)[ui]
+ && ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui]))
{
- VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]);
+ (*reg_base_value)[ui] = new_reg_base_value[ui];
changed = 1;
}
}
XDELETEVEC (rpo);
/* Fill in the remaining entries. */
- FOR_EACH_VEC_ELT (rtx, reg_known_value, i, val)
+ FOR_EACH_VEC_ELT (*reg_known_value, i, val)
{
int regno = i + FIRST_PSEUDO_REGISTER;
if (! val)
/* Clean up. */
free (new_reg_base_value);
new_reg_base_value = 0;
- free (reg_seen);
+ sbitmap_free (reg_seen);
reg_seen = 0;
timevar_pop (TV_ALIAS_ANALYSIS);
}
void
vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2)
{
- VEC_replace (rtx, reg_base_value, REGNO (reg1), REG_BASE_VALUE (reg2));
+ (*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2);
}
void
end_alias_analysis (void)
{
old_reg_base_value = reg_base_value;
- VEC_free (rtx, gc, reg_known_value);
+ vec_free (reg_known_value);
sbitmap_free (reg_known_equiv_p);
}
+void
+dump_alias_stats_in_alias_c (FILE *s)
+{
+ fprintf (s, " TBAA oracle: %llu disambiguations %llu queries\n"
+ " %llu are in alias set 0\n"
+ " %llu queries asked about the same object\n"
+ " %llu queries asked about the same alias set\n"
+ " %llu access volatile\n"
+ " %llu are dependent in the DAG\n"
+ " %llu are aritificially in conflict with void *\n",
+ alias_stats.num_disambiguated,
+ alias_stats.num_alias_zero + alias_stats.num_same_alias_set
+ + alias_stats.num_same_objects + alias_stats.num_volatile
+ + alias_stats.num_dag + alias_stats.num_disambiguated
+ + alias_stats.num_universal,
+ alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
+ alias_stats.num_same_objects, alias_stats.num_volatile,
+ alias_stats.num_dag, alias_stats.num_universal);
+}
#include "gt-alias.h"