#include "tree-dfa.h"
#include "ipa-reference.h"
#include "varasm.h"
+#include "ipa-modref-tree.h"
+#include "ipa-modref.h"
/* Broad overview of how alias analysis on gimple works:
unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_may_alias;
unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_must_overlap;
unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_no_alias;
+ unsigned HOST_WIDE_INT modref_use_may_alias;
+ unsigned HOST_WIDE_INT modref_use_no_alias;
+ unsigned HOST_WIDE_INT modref_clobber_may_alias;
+ unsigned HOST_WIDE_INT modref_clobber_no_alias;
+ unsigned HOST_WIDE_INT modref_tests;
} alias_stats;
void
alias_stats.aliasing_component_refs_p_no_alias
+ alias_stats.aliasing_component_refs_p_may_alias);
dump_alias_stats_in_alias_c (s);
+ fprintf (s, "\nModref stats:\n");
+ fprintf (s, " modref use: "
+ HOST_WIDE_INT_PRINT_DEC" disambiguations, "
+ HOST_WIDE_INT_PRINT_DEC" queries\n",
+ alias_stats.modref_use_no_alias,
+ alias_stats.modref_use_no_alias
+ + alias_stats.modref_use_may_alias);
+ fprintf (s, " modref clobber: "
+ HOST_WIDE_INT_PRINT_DEC" disambiguations, "
+ HOST_WIDE_INT_PRINT_DEC" queries\n "
+ HOST_WIDE_INT_PRINT_DEC" tbaa querries (%f per modref querry)\n",
+ alias_stats.modref_clobber_no_alias,
+ alias_stats.modref_clobber_no_alias
+ + alias_stats.modref_clobber_may_alias,
+ alias_stats.modref_tests,
+ ((double)alias_stats.modref_tests)
+ / (alias_stats.modref_clobber_no_alias
+ + alias_stats.modref_clobber_may_alias));
}
{
if (ref->ref_alias_set != -1)
return ref->ref_alias_set;
+ if (!ref->ref)
+ return 0;
ref->ref_alias_set = get_alias_set (ref->ref);
return ref->ref_alias_set;
}
would mean that conversions between them are useless, whereas they are
not (e.g. type and subtypes can have different modes). So, in the end,
they are only guaranteed to have the same alias set. */
- if (get_alias_set (type1) == get_alias_set (type2))
+ alias_set_type set1 = get_alias_set (type1);
+ alias_set_type set2 = get_alias_set (type2);
+ if (set1 == set2)
+ return -1;
+
+ /* Pointers to void are considered compatible with all other pointers,
+ so for two pointers see what the alias set resolution thinks. */
+ if (POINTER_TYPE_P (type1)
+ && POINTER_TYPE_P (type2)
+ && alias_sets_conflict_p (set1, set2))
return -1;
/* The types are known to be not equal. */
/* MATCH1 and MATCH2 which are part of access path of REF1 and REF2
respectively are either pointing to same address or are completely
- disjoint. If PARITAL_OVERLAP is true, assume that outermost arrays may
+ disjoint. If PARTIAL_OVERLAP is true, assume that outermost arrays may
just partly overlap.
Try to disambiguate using the access path starting from the match
return -1;
}
+/* Consider access path1 base1....ref1 and access path2 base2...ref2.
+ Return true if they can be composed to single access path
+ base1...ref1...base2...ref2.
+
+ REF_TYPE1 if type of REF1. END_STRUCT_PAST_END1 is true if there is
+ a trailing array access after REF1 in the non-TBAA part of the access.
+ REF1_ALIAS_SET is the alias set of REF1.
+
+ BASE_TYPE2 is type of base2. END_STRUCT_REF2 is non-NULL if there is
+ a traling array access in the TBAA part of access path2.
+ BASE2_ALIAS_SET is the alias set of base2. */
+
+bool
+access_path_may_continue_p (tree ref_type1, bool end_struct_past_end1,
+ alias_set_type ref1_alias_set,
+ tree base_type2, tree end_struct_ref2,
+ alias_set_type base2_alias_set)
+{
+ /* Access path can not continue past types with no components. */
+ if (!type_has_components_p (ref_type1))
+ return false;
+
+ /* If first access path ends by too small type to hold base of
+ the second access path, typically paths can not continue.
+
+ Punt if end_struct_past_end1 is true. We want to support arbitrary
+ type puning past first COMPONENT_REF to union because redundant store
+ elimination depends on this, see PR92152. For this reason we can not
+ check size of the reference because types may partially overlap. */
+ if (!end_struct_past_end1)
+ {
+ if (compare_type_sizes (ref_type1, base_type2) < 0)
+ return false;
+ /* If the path2 contains trailing array access we can strenghten the check
+ to verify that also the size of element of the trailing array fits.
+ In fact we could check for offset + type_size, but we do not track
+ offsets and this is quite side case. */
+ if (end_struct_ref2
+ && compare_type_sizes (ref_type1, TREE_TYPE (end_struct_ref2)) < 0)
+ return false;
+ }
+ return (base2_alias_set == ref1_alias_set
+ || alias_set_subset_of (base2_alias_set, ref1_alias_set));
+}
+
/* Determine if the two component references REF1 and REF2 which are
based on access types TYPE1 and TYPE2 and of which at least one is based
on an indirect reference may alias.
tree type1, type2;
bool maybe_match = false;
tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
+ bool end_struct_past_end1 = false;
+ bool end_struct_past_end2 = false;
+
+ /* Choose bases and base types to search for.
+ The access path is as follows:
+ base....end_of_tbaa_ref...actual_ref
+ At one place in the access path may be a reference to zero sized or
+ trailing array.
+
+ We generally discard the segment after end_of_tbaa_ref however
+ we need to be careful in case it contains zero sized or traling array.
+ These may happen after refernce to union and in this case we need to
+ not disambiguate type puning scenarios.
- /* Choose bases and base types to search for. */
+ We set:
+ base1 to point to base
+
+ ref1 to point to end_of_tbaa_ref
+
+ end_struct_ref1 to point the trailing reference (if it exists
+ in range base....end_of_tbaa_ref
+
+ end_struct_past_end1 is true if this traling refernece occurs in
+ end_of_tbaa_ref...actual_ref. */
base1 = ref1;
while (handled_component_p (base1))
{
gcc_checking_assert (!end_struct_ref1);
end_struct_ref1 = base1;
}
- if (TREE_CODE (base1) == VIEW_CONVERT_EXPR
- || TREE_CODE (base1) == BIT_FIELD_REF)
- ref1 = TREE_OPERAND (base1, 0);
+ if (ends_tbaa_access_path_p (base1))
+ {
+ ref1 = TREE_OPERAND (base1, 0);
+ if (end_struct_ref1)
+ {
+ end_struct_past_end1 = true;
+ end_struct_ref1 = NULL;
+ }
+ }
base1 = TREE_OPERAND (base1, 0);
}
type1 = TREE_TYPE (base1);
gcc_checking_assert (!end_struct_ref2);
end_struct_ref2 = base2;
}
- if (TREE_CODE (base2) == VIEW_CONVERT_EXPR
- || TREE_CODE (base2) == BIT_FIELD_REF)
- ref2 = TREE_OPERAND (base2, 0);
+ if (ends_tbaa_access_path_p (base2))
+ {
+ ref2 = TREE_OPERAND (base2, 0);
+ if (end_struct_ref2)
+ {
+ end_struct_past_end2 = true;
+ end_struct_ref2 = NULL;
+ }
+ }
base2 = TREE_OPERAND (base2, 0);
}
type2 = TREE_TYPE (base2);
/* If type2 is big enough to contain type1 walk its access path.
We also need to care of arrays at the end of structs that may extend
- beyond the end of structure. */
+ beyond the end of structure. If this occurs in the TBAA part of the
+ access path, we need to consider the increased type as well. */
if (cmp_outer >= 0
|| (end_struct_ref2
&& compare_type_sizes (TREE_TYPE (end_struct_ref2), type1) >= 0))
return false;
}
- /* If we have two type access paths B1.path1 and B2.path2 they may
- only alias if either B1 is in B2.path2 or B2 is in B1.path1.
- But we can still have a path that goes B1.path1...B2.path2 with
- a part that we do not see. So we can only disambiguate now
- if there is no B2 in the tail of path1 and no B1 on the
- tail of path2. */
- if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0
- && (!end_struct_ref1
- || compare_type_sizes (TREE_TYPE (ref2),
- TREE_TYPE (end_struct_ref1)) >= 0)
- && type_has_components_p (TREE_TYPE (ref2))
- && (base1_alias_set == ref2_alias_set
- || alias_set_subset_of (base1_alias_set, ref2_alias_set)))
- {
- ++alias_stats.aliasing_component_refs_p_may_alias;
- return true;
- }
- /* If this is ptr vs. decl then we know there is no ptr ... decl path. */
- if (compare_type_sizes (TREE_TYPE (ref1), type2) >= 0
- && (!end_struct_ref2
- || compare_type_sizes (TREE_TYPE (ref1),
- TREE_TYPE (end_struct_ref2)) >= 0)
- && type_has_components_p (TREE_TYPE (ref1))
- && (base2_alias_set == ref1_alias_set
- || alias_set_subset_of (base2_alias_set, ref1_alias_set)))
+ if (access_path_may_continue_p (TREE_TYPE (ref1), end_struct_past_end1,
+ ref1_alias_set,
+ type2, end_struct_ref2,
+ base2_alias_set)
+ || access_path_may_continue_p (TREE_TYPE (ref2), end_struct_past_end2,
+ ref2_alias_set,
+ type1, end_struct_ref1,
+ base1_alias_set))
{
++alias_stats.aliasing_component_refs_p_may_alias;
return true;
{
tree index1 = TREE_OPERAND (ref1, 1);
tree index2 = TREE_OPERAND (ref2, 1);
- tree low_bound1 = cheap_array_ref_low_bound(ref1);
- tree low_bound2 = cheap_array_ref_low_bound(ref2);
+ tree low_bound1 = cheap_array_ref_low_bound (ref1);
+ tree low_bound2 = cheap_array_ref_low_bound (ref2);
/* Handle zero offsets first: we do not need to match type size in this
case. */
tree match2, tree ref2,
bool partial_overlap)
{
+ int ntbaa1 = 0, ntbaa2 = 0;
/* Early return if there are no references to match, we do not need
to walk the access paths.
/* Create the stack of handled components for REF1. */
while (handled_component_p (ref1) && ref1 != match1)
{
- if (TREE_CODE (ref1) == VIEW_CONVERT_EXPR
- || TREE_CODE (ref1) == BIT_FIELD_REF)
- component_refs1.truncate (0);
+ /* We use TBAA only to re-synchronize after mismatched refs. So we
+ do not need to truncate access path after TBAA part ends. */
+ if (ends_tbaa_access_path_p (ref1))
+ ntbaa1 = 0;
else
- component_refs1.safe_push (ref1);
+ ntbaa1++;
+ component_refs1.safe_push (ref1);
ref1 = TREE_OPERAND (ref1, 0);
}
/* Create the stack of handled components for REF2. */
while (handled_component_p (ref2) && ref2 != match2)
{
- if (TREE_CODE (ref2) == VIEW_CONVERT_EXPR
- || TREE_CODE (ref2) == BIT_FIELD_REF)
- component_refs2.truncate (0);
+ if (ends_tbaa_access_path_p (ref2))
+ ntbaa2 = 0;
else
- component_refs2.safe_push (ref2);
+ ntbaa2++;
+ component_refs2.safe_push (ref2);
ref2 = TREE_OPERAND (ref2, 0);
}
+ if (!flag_strict_aliasing)
+ {
+ ntbaa1 = 0;
+ ntbaa2 = 0;
+ }
+
bool mem_ref1 = TREE_CODE (ref1) == MEM_REF && ref1 != match1;
bool mem_ref2 = TREE_CODE (ref2) == MEM_REF && ref2 != match2;
for (; narray_refs1 > narray_refs2; narray_refs1--)
{
ref1 = component_refs1.pop ();
+ ntbaa1--;
/* If index is non-zero we need to check whether the reference
does not break the main invariant that bases are either
for (; narray_refs2 > narray_refs1; narray_refs2--)
{
ref2 = component_refs2.pop ();
+ ntbaa2--;
if (!operand_equal_p (TREE_OPERAND (ref2, 1),
cheap_array_ref_low_bound (ref2), 0))
return 0;
{
int cmp = nonoverlapping_array_refs_p (component_refs1.pop (),
component_refs2.pop ());
+ ntbaa1--;
+ ntbaa2--;
if (cmp == 1 && !partial_overlap)
{
++alias_stats
.nonoverlapping_refs_since_match_p_no_alias;
return 1;
}
- partial_overlap = false;
if (cmp == -1)
- seen_unmatched_ref_p = true;
+ {
+ seen_unmatched_ref_p = true;
+ /* We can not maintain the invariant that bases are either
+ same or completely disjoint. However we can still recover
+ from type based alias analysis if we reach referneces to
+ same sizes. We do not attempt to match array sizes, so
+ just finish array walking and look for component refs. */
+ if (ntbaa1 < 0 || ntbaa2 < 0)
+ {
+ ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
+ return -1;
+ }
+ for (i++; i < narray_refs1; i++)
+ {
+ component_refs1.pop ();
+ component_refs2.pop ();
+ ntbaa1--;
+ ntbaa2--;
+ }
+ break;
+ }
+ partial_overlap = false;
}
}
return 0;
}
ref1 = component_refs1.pop ();
+ ntbaa1--;
if (TREE_CODE (ref1) != COMPONENT_REF)
- seen_unmatched_ref_p = true;
+ {
+ seen_unmatched_ref_p = true;
+ if (ntbaa1 < 0 || ntbaa2 < 0)
+ {
+ ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
+ return -1;
+ }
+ }
}
while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
return 0;
}
ref2 = component_refs2.pop ();
+ ntbaa2--;
if (TREE_CODE (ref2) != COMPONENT_REF)
- seen_unmatched_ref_p = true;
+ {
+ if (ntbaa1 < 0 || ntbaa2 < 0)
+ {
+ ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
+ return -1;
+ }
+ seen_unmatched_ref_p = true;
+ }
}
while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
/* If we skipped array refs on type of different sizes, we can
no longer be sure that there are not partial overlaps. */
- if (seen_unmatched_ref_p
+ if (seen_unmatched_ref_p && ntbaa1 >= 0 && ntbaa2 >= 0
&& !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
{
++alias_stats
if (TREE_CODE (type) == RECORD_TYPE)
fieldsx.safe_push (field);
}
- else if (TREE_CODE (x) == VIEW_CONVERT_EXPR
- || TREE_CODE (x) == BIT_FIELD_REF)
+ else if (ends_tbaa_access_path_p (x))
fieldsx.truncate (0);
x = TREE_OPERAND (x, 0);
}
if (TREE_CODE (type) == RECORD_TYPE)
fieldsy.safe_push (TREE_OPERAND (y, 1));
}
- else if (TREE_CODE (y) == VIEW_CONVERT_EXPR
- || TREE_CODE (y) == BIT_FIELD_REF)
+ else if (ends_tbaa_access_path_p (y))
fieldsy.truncate (0);
y = TREE_OPERAND (y, 0);
}
return refs_may_alias_p_1 (&r1, &r2, false);
}
+/* Returns true if and only if REF may alias any access stored in TT.
+ IF TBAA_P is true, use TBAA oracle. */
+
+static bool
+modref_may_conflict (modref_tree <alias_set_type> *tt, ao_ref *ref, bool tbaa_p)
+{
+ alias_set_type base_set, ref_set;
+ modref_base_node <alias_set_type> *base_node;
+ modref_ref_node <alias_set_type> *ref_node;
+ size_t i, j;
+
+ if (tt->every_base)
+ return true;
+
+ base_set = ao_ref_base_alias_set (ref);
+
+ ref_set = ao_ref_alias_set (ref);
+
+ int num_tests = 0, max_tests = param_modref_max_tests;
+ FOR_EACH_VEC_SAFE_ELT (tt->bases, i, base_node)
+ {
+ if (base_node->every_ref)
+ return true;
+
+ if (!base_node->base)
+ return true;
+
+ if (tbaa_p && flag_strict_aliasing)
+ {
+ if (!alias_sets_conflict_p (base_set, base_node->base))
+ continue;
+ alias_stats.modref_tests++;
+ num_tests++;
+ }
+ else
+ return true;
+ if (num_tests >= max_tests)
+ return true;
+
+ FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
+ {
+ /* Do not repeat same test as before. */
+ if (ref_set == base_set && base_node->base == ref_node->ref)
+ return true;
+ if (!flag_strict_aliasing)
+ return true;
+ if (alias_sets_conflict_p (ref_set, ref_node->ref))
+ return true;
+ alias_stats.modref_tests++;
+ num_tests++;
+ if (num_tests >= max_tests)
+ return true;
+ }
+ }
+ return false;
+}
+
/* If the call CALL may use the memory reference REF return true,
otherwise return false. */
&& (flags & (ECF_CONST|ECF_NOVOPS)))
goto process_args;
- base = ao_ref_base (ref);
- if (!base)
- return true;
-
/* A call that is not without side-effects might involve volatile
accesses and thus conflicts with all other volatile accesses. */
if (ref->volatile_p)
return true;
+ callee = gimple_call_fndecl (call);
+
+ if (!gimple_call_chain (call) && callee != NULL_TREE)
+ {
+ struct cgraph_node *node = cgraph_node::get (callee);
+ /* We can not safely optimize based on summary of calle if it does
+ not always bind to current def: it is possible that memory load
+ was optimized out earlier and the interposed variant may not be
+ optimized this way. */
+ if (node && node->binds_to_current_def_p ())
+ {
+ modref_summary *summary = get_modref_function_summary (node);
+ if (summary)
+ {
+ if (!modref_may_conflict (summary->loads, ref, tbaa_p))
+ {
+ alias_stats.modref_use_no_alias++;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "ipa-modref: in %s,"
+ " call to %s does not use ",
+ cgraph_node::get
+ (current_function_decl)->dump_name (),
+ node->dump_name ());
+ print_generic_expr (dump_file, ref->ref);
+ fprintf (dump_file, " %i->%i\n",
+ ao_ref_base_alias_set (ref),
+ ao_ref_alias_set (ref));
+ }
+ goto process_args;
+ }
+ alias_stats.modref_use_may_alias++;
+ }
+ }
+ }
+
+ base = ao_ref_base (ref);
+ if (!base)
+ return true;
+
/* If the reference is based on a decl that is not aliased the call
cannot possibly use it. */
if (DECL_P (base)
&& !is_global_var (base))
goto process_args;
- callee = gimple_call_fndecl (call);
-
/* Handle those builtin functions explicitly that do not act as
escape points. See tree-ssa-structalias.c:find_func_aliases
for the list of builtins we might need to handle here. */
return true, otherwise return false. */
bool
-call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref)
+call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
{
tree base;
tree callee;
break;
}
+ callee = gimple_call_fndecl (call);
+
+ if (callee != NULL_TREE && !ref->volatile_p)
+ {
+ struct cgraph_node *node = cgraph_node::get (callee);
+ if (node)
+ {
+ modref_summary *summary = get_modref_function_summary (node);
+ if (summary)
+ {
+ if (!modref_may_conflict (summary->stores, ref, tbaa_p))
+ {
+ alias_stats.modref_clobber_no_alias++;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "ipa-modref: in %s, "
+ "call to %s does not clobber ",
+ cgraph_node::get
+ (current_function_decl)->dump_name (),
+ node->dump_name ());
+ print_generic_expr (dump_file, ref->ref);
+ fprintf (dump_file, " %i->%i\n",
+ ao_ref_base_alias_set (ref),
+ ao_ref_alias_set (ref));
+ }
+ return false;
+ }
+ alias_stats.modref_clobber_may_alias++;
+ }
+ }
+ }
+
base = ao_ref_base (ref);
if (!base)
return true;
&& SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base, 0)))
return false;
- callee = gimple_call_fndecl (call);
-
/* Handle those builtin functions explicitly that do not act as
escape points. See tree-ssa-structalias.c:find_func_aliases
for the list of builtins we might need to handle here. */
bool res;
ao_ref r;
ao_ref_init (&r, ref);
- res = call_may_clobber_ref_p_1 (call, &r);
+ res = call_may_clobber_ref_p_1 (call, &r, true);
if (res)
++alias_stats.call_may_clobber_ref_p_may_alias;
else
return true;
}
- return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref);
+ return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref, tbaa_p);
}
else if (gimple_assign_single_p (stmt))
{
return false;
dest = gimple_call_lhs (stmt);
+ if (!dest)
+ return false;
len = fold_build2 (MULT_EXPR, TREE_TYPE (arg0), arg0, arg1);
}
else
projects / gcc.git / blobdiff