/* 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 "tree-pass.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 int aliases_everything_p (const_rtx);
-static bool nonoverlapping_component_refs_p (const_tree, const_tree);
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. */
#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
-/* Returns nonzero if MEM1 and MEM2 do not alias because they are in
- different alias sets. We ignore alias sets in functions making use
- of variable arguments because the va_arg macros on some systems are
- not legal ANSI C. */
-#define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
- mems_in_disjoint_alias_sets_p (MEM1, MEM2)
-
/* Cap the number of passes we make over the insns propagating alias
- information through set chains. 10 is a completely arbitrary choice. */
+ information through set chains.
+ ??? 10 is a completely arbitrary choice. This should be based on the
+ maximum loop depth in the CFG, but we do not have this information
+ available (even if current_loops _is_ available). */
#define MAX_ALIAS_LOOP_PASSES 10
/* reg_base_value[N] gives an address to which register N is related.
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_OFFSET or MEM_SIZE are unknown we have to punt.
- Keep points-to related information though. */
+ /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR
+ is conservative, so trust it. */
if (!MEM_OFFSET_KNOWN_P (mem)
|| !MEM_SIZE_KNOWN_P (mem))
- {
- ref->ref = NULL_TREE;
- ref->offset = 0;
- ref->size = -1;
- ref->max_size = -1;
- return true;
- }
+ return true;
/* If the base decl is a parameter we can have negative MEM_OFFSET in
case of promoted subregs on bigendian targets. Trust the MEM_EXPR
&& (MEM_SIZE (mem) + MEM_OFFSET (mem)) * BITS_PER_UNIT == ref->size)
return true;
+ /* Otherwise continue and refine size and offset we got from analyzing
+ MEM_EXPR by using MEM_SIZE and MEM_OFFSET. */
+
ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT;
ref->size = MEM_SIZE (mem) * BITS_PER_UNIT;
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, 0);
- VEC_safe_push (alias_set_entry, gc, alias_sets, 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))
break;
}
- /* Treat an access through an AND (e.g. a subword access on an Alpha)
- as an access with indeterminate size. Assume that references
- besides AND are aligned, so if the size of the other reference is
- at least as large as the alignment, assume no other overlap. */
+ /* Deal with alignment ANDs by adjusting offset and size so as to
+ cover the maximum range, without taking any previously known
+ 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)))
{
- if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1)))
- xsize = -1;
- return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c);
+ HOST_WIDE_INT sc = INTVAL (XEXP (x, 1));
+ unsigned HOST_WIDE_INT uc = sc;
+ if (sc < 0 && -uc == (uc & -uc))
+ {
+ 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);
+ }
}
if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1)))
{
- /* ??? If we are indexing far enough into the array/structure, we
- may yet be able to determine that we can not overlap. But we
- also need to that we are far enough from the end not to overlap
- a following reference, so we do nothing with that for now. */
- if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1)))
- ysize = -1;
- return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c);
+ HOST_WIDE_INT sc = INTVAL (XEXP (y, 1));
+ unsigned HOST_WIDE_INT uc = sc;
+ if (sc < 0 && -uc == (uc & -uc))
+ {
+ 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 (CONSTANT_P (x))
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);
-}
-
-/* Returns nonzero if something about the mode or address format MEM1
- indicates that it might well alias *anything*. */
-
-static int
-aliases_everything_p (const_rtx mem)
-{
- if (GET_CODE (XEXP (mem, 0)) == AND)
- /* If the address is an AND, it's very hard to know at what it is
- actually pointing. */
- return 1;
-
- return 0;
-}
-
-/* Return true if we can determine that the fields referenced cannot
- overlap for any pair of objects. */
-
-static bool
-nonoverlapping_component_refs_p (const_tree x, const_tree y)
-{
- const_tree fieldx, fieldy, typex, typey, orig_y;
-
- if (!flag_strict_aliasing)
- 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);
}
&& ! MEM_OFFSET_KNOWN_P (y)))
return 0;
- /* If both are field references, we may be able to determine something. */
- if (TREE_CODE (exprx) == COMPONENT_REF
- && TREE_CODE (expry) == COMPONENT_REF
- && nonoverlapping_component_refs_p (exprx, expry))
- return 1;
-
-
/* If the field reference test failed, look at the DECLs involved. */
moffsetx_known_p = MEM_OFFSET_KNOWN_P (x);
if (moffsetx_known_p)
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)
return ret;
- if (DIFFERENT_ALIAS_SETS_P (x, mem))
+ if (mems_in_disjoint_alias_sets_p (x, mem))
return 0;
if (nonoverlapping_memrefs_p (mem, x, false))
return 0;
- if (aliases_everything_p (x))
- return 1;
-
- /* We cannot use aliases_everything_p to test MEM, since we must look
- at MEM_ADDR, rather than XEXP (mem, 0). */
- if (GET_CODE (mem_addr) == AND)
- return 1;
-
- /* ??? In true_dependence we also allow BLKmode to alias anything. Why
- don't we do this in anti_dependence and output_dependence? */
- if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
- return 1;
-
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
if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
return 1;
- /* ??? In true_dependence we also allow BLKmode to alias anything. */
- if (GET_MODE (mem) == BLKmode || GET_MODE (x) == BLKmode)
+ /* (mem:BLK (scratch)) is a special mechanism to conflict with everything.
+ This is used in epilogue deallocation functions. */
+ if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH)
+ return 1;
+ if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH)
return 1;
-
if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER
|| 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;
- if (aliases_everything_p (x))
- return 1;
-
- /* We cannot use aliases_everything_p to test MEM, since we must look
- at MEM_ADDR, rather than XEXP (mem, 0). */
- if (GET_CODE (mem_addr) == AND)
- return 1;
-
/* TBAA not valid for loop_invarint */
return rtx_refs_may_alias_p (x, mem, false);
}
= 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
information through another level of assignments.
+ The propagation is done on the CFG in reverse post-order, to propagate
+ things forward as far as possible in each iteration.
+
This could get expensive if the assignment chains are long. Maybe
we should throttle the number of iterations, possibly based on
the optimization level or flag_expensive_optimizations.
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_for_fn (cfun));
+ rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
+
pass = 0;
do
{
memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
/* Wipe the reg_seen array clean. */
- memset (reg_seen, 0, maxreg);
+ bitmap_clear (reg_seen);
- /* 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. */
-
- 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 (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ for (i = 0; i < rpo_cnt; i++)
{
- if (INSN_P (insn))
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
+ FOR_BB_INSNS (bb, insn)
{
- rtx note, set;
-
-#if defined (HAVE_prologue) || defined (HAVE_epilogue)
- /* 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
- && 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
- which could change the base value of any other register. */
-
- if (GET_CODE (PATTERN (insn)) == SET
- && REG_NOTES (insn) != 0
- && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
- record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
- else
- note_stores (PATTERN (insn), record_set, NULL);
+ if (NONDEBUG_INSN_P (insn))
+ {
+ rtx note, set;
- set = single_set (insn);
+#if defined (HAVE_prologue)
+ static const bool prologue = true;
+#else
+ static const bool prologue = false;
+#endif
- if (set != 0
- && REG_P (SET_DEST (set))
- && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
- {
- unsigned int regno = REGNO (SET_DEST (set));
- rtx src = SET_SRC (set);
- rtx t;
-
- note = find_reg_equal_equiv_note (insn);
- if (note && REG_NOTE_KIND (note) == REG_EQUAL
- && DF_REG_DEF_COUNT (regno) != 1)
- note = NULL_RTX;
-
- if (note != NULL_RTX
- && GET_CODE (XEXP (note, 0)) != EXPR_LIST
- && ! rtx_varies_p (XEXP (note, 0), 1)
- && ! reg_overlap_mentioned_p (SET_DEST (set),
- XEXP (note, 0)))
- {
- set_reg_known_value (regno, XEXP (note, 0));
- set_reg_known_equiv_p (regno,
- REG_NOTE_KIND (note) == REG_EQUIV);
- }
- else if (DF_REG_DEF_COUNT (regno) == 1
- && GET_CODE (src) == PLUS
- && REG_P (XEXP (src, 0))
- && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
- && CONST_INT_P (XEXP (src, 1)))
+ /* 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 ((prologue || HAVE_epilogue) && reload_completed
+ && prologue_epilogue_contains (insn))
+ continue;
+
+ /* If this insn has a noalias note, process it, Otherwise,
+ scan for sets. A simple set will have no side effects
+ which could change the base value of any other register. */
+
+ if (GET_CODE (PATTERN (insn)) == SET
+ && REG_NOTES (insn) != 0
+ && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
+ record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
+ else
+ note_stores (PATTERN (insn), record_set, NULL);
+
+ set = single_set (insn);
+
+ if (set != 0
+ && REG_P (SET_DEST (set))
+ && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
{
- t = plus_constant (GET_MODE (src), t,
- INTVAL (XEXP (src, 1)));
- set_reg_known_value (regno, t);
- set_reg_known_equiv_p (regno, false);
- }
- else if (DF_REG_DEF_COUNT (regno) == 1
- && ! rtx_varies_p (src, 1))
- {
- set_reg_known_value (regno, src);
- set_reg_known_equiv_p (regno, false);
+ unsigned int regno = REGNO (SET_DEST (set));
+ rtx src = SET_SRC (set);
+ rtx t;
+
+ note = find_reg_equal_equiv_note (insn);
+ if (note && REG_NOTE_KIND (note) == REG_EQUAL
+ && DF_REG_DEF_COUNT (regno) != 1)
+ note = NULL_RTX;
+
+ if (note != NULL_RTX
+ && GET_CODE (XEXP (note, 0)) != EXPR_LIST
+ && ! rtx_varies_p (XEXP (note, 0), 1)
+ && ! reg_overlap_mentioned_p (SET_DEST (set),
+ XEXP (note, 0)))
+ {
+ set_reg_known_value (regno, XEXP (note, 0));
+ set_reg_known_equiv_p (regno,
+ REG_NOTE_KIND (note) == REG_EQUIV);
+ }
+ else if (DF_REG_DEF_COUNT (regno) == 1
+ && GET_CODE (src) == PLUS
+ && REG_P (XEXP (src, 0))
+ && (t = get_reg_known_value (REGNO (XEXP (src, 0))))
+ && CONST_INT_P (XEXP (src, 1)))
+ {
+ t = plus_constant (GET_MODE (src), t,
+ INTVAL (XEXP (src, 1)));
+ set_reg_known_value (regno, t);
+ set_reg_known_equiv_p (regno, false);
+ }
+ else if (DF_REG_DEF_COUNT (regno) == 1
+ && ! rtx_varies_p (src, 1))
+ {
+ set_reg_known_value (regno, src);
+ set_reg_known_equiv_p (regno, false);
+ }
}
}
+ else if (NOTE_P (insn)
+ && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
+ copying_arguments = false;
}
- else if (NOTE_P (insn)
- && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG)
- copying_arguments = false;
}
/* Now propagate values from new_reg_base_value to reg_base_value. */
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;
}
}
}
while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
+ 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"