/* Alias analysis for trees.
- Copyright (C) 2004-2019 Free Software Foundation, Inc.
+ Copyright (C) 2004-2020 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
#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:
this file. Low-level disambiguators dealing with points-to
information are in tree-ssa-structalias.c. */
-static int nonoverlapping_component_refs_since_match_p (tree, tree, tree, tree);
+static int nonoverlapping_refs_since_match_p (tree, tree, tree, tree, bool);
static bool nonoverlapping_component_refs_p (const_tree, const_tree);
/* Query statistics for the different low-level disambiguators.
unsigned HOST_WIDE_INT aliasing_component_refs_p_no_alias;
unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_may_alias;
unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_no_alias;
- unsigned HOST_WIDE_INT nonoverlapping_component_refs_since_match_p_may_alias;
- unsigned HOST_WIDE_INT nonoverlapping_component_refs_since_match_p_must_overlap;
- unsigned HOST_WIDE_INT nonoverlapping_component_refs_since_match_p_no_alias;
+ 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.nonoverlapping_component_refs_p_no_alias,
alias_stats.nonoverlapping_component_refs_p_no_alias
+ alias_stats.nonoverlapping_component_refs_p_may_alias);
- fprintf (s, " nonoverlapping_component_refs_since_match_p: "
+ fprintf (s, " nonoverlapping_refs_since_match_p: "
HOST_WIDE_INT_PRINT_DEC" disambiguations, "
HOST_WIDE_INT_PRINT_DEC" must overlaps, "
HOST_WIDE_INT_PRINT_DEC" queries\n",
- alias_stats.nonoverlapping_component_refs_since_match_p_no_alias,
- alias_stats.nonoverlapping_component_refs_since_match_p_must_overlap,
- alias_stats.nonoverlapping_component_refs_since_match_p_no_alias
- + alias_stats.nonoverlapping_component_refs_since_match_p_may_alias
- + alias_stats.nonoverlapping_component_refs_since_match_p_must_overlap);
+ alias_stats.nonoverlapping_refs_since_match_p_no_alias,
+ alias_stats.nonoverlapping_refs_since_match_p_must_overlap,
+ alias_stats.nonoverlapping_refs_since_match_p_no_alias
+ + alias_stats.nonoverlapping_refs_since_match_p_may_alias
+ + alias_stats.nonoverlapping_refs_since_match_p_must_overlap);
fprintf (s, " aliasing_component_refs_p: "
HOST_WIDE_INT_PRINT_DEC" disambiguations, "
HOST_WIDE_INT_PRINT_DEC" queries\n",
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.
+ 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
and return false if there is no conflict.
aliasing_matching_component_refs_p (tree match1, tree ref1,
poly_int64 offset1, poly_int64 max_size1,
tree match2, tree ref2,
- poly_int64 offset2, poly_int64 max_size2)
+ poly_int64 offset2, poly_int64 max_size2,
+ bool partial_overlap)
{
poly_int64 offadj, sztmp, msztmp;
bool reverse;
-
- get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse);
- offset2 -= offadj;
- get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse);
- offset1 -= offadj;
- if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+ if (!partial_overlap)
{
- ++alias_stats.aliasing_component_refs_p_no_alias;
- return false;
+ get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse);
+ offset2 -= offadj;
+ get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse);
+ offset1 -= offadj;
+ if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+ {
+ ++alias_stats.aliasing_component_refs_p_no_alias;
+ return false;
+ }
}
- int cmp = nonoverlapping_component_refs_since_match_p (match1, ref1,
- match2, ref2);
+ int cmp = nonoverlapping_refs_since_match_p (match1, ref1, match2, ref2,
+ partial_overlap);
if (cmp == 1
|| (cmp == -1 && nonoverlapping_component_refs_p (ref1, ref2)))
{
}
if (same_p == 1)
{
+ bool partial_overlap = false;
+
/* We assume that arrays can overlap by multiple of their elements
size as tested in gcc.dg/torture/alias-2.c.
This partial overlap happen only when both arrays are bases of
&& (!TYPE_SIZE (TREE_TYPE (base1))
|| TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST
|| ref == base2))
- /* Setting maybe_match to true triggers
- nonoverlapping_component_refs_p test later that still may do
- useful disambiguation. */
- *maybe_match = true;
- else
- return aliasing_matching_component_refs_p (base1, ref1,
- offset1, max_size1,
- ref, ref2,
- offset2, max_size2);
+ {
+ /* Setting maybe_match to true triggers
+ nonoverlapping_component_refs_p test later that still may do
+ useful disambiguation. */
+ *maybe_match = true;
+ partial_overlap = true;
+ }
+ return aliasing_matching_component_refs_p (base1, ref1,
+ offset1, max_size1,
+ ref, ref2,
+ offset2, max_size2,
+ partial_overlap);
}
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;
return -1;
}
+/* Return low bound of array. Do not produce new trees
+ and thus do not care about particular type of integer constant
+ and placeholder exprs. */
+
+static tree
+cheap_array_ref_low_bound (tree ref)
+{
+ tree domain_type = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (ref, 0)));
+
+ /* Avoid expensive array_ref_low_bound.
+ low bound is either stored in operand2, or it is TYPE_MIN_VALUE of domain
+ type or it is zero. */
+ if (TREE_OPERAND (ref, 2))
+ return TREE_OPERAND (ref, 2);
+ else if (domain_type && TYPE_MIN_VALUE (domain_type))
+ return TYPE_MIN_VALUE (domain_type);
+ else
+ return integer_zero_node;
+}
+
+/* REF1 and REF2 are ARRAY_REFs with either same base address or which are
+ completely disjoint.
+
+ Return 1 if the refs are non-overlapping.
+ Return 0 if they are possibly overlapping but if so the overlap again
+ starts on the same address.
+ Return -1 otherwise. */
+
+int
+nonoverlapping_array_refs_p (tree ref1, tree ref2)
+{
+ 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);
+
+ /* Handle zero offsets first: we do not need to match type size in this
+ case. */
+ if (operand_equal_p (index1, low_bound1, 0)
+ && operand_equal_p (index2, low_bound2, 0))
+ return 0;
+
+ /* If type sizes are different, give up.
+
+ Avoid expensive array_ref_element_size.
+ If operand 3 is present it denotes size in the alignmnet units.
+ Otherwise size is TYPE_SIZE of the element type.
+ Handle only common cases where types are of the same "kind". */
+ if ((TREE_OPERAND (ref1, 3) == NULL) != (TREE_OPERAND (ref2, 3) == NULL))
+ return -1;
+
+ tree elmt_type1 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref1, 0)));
+ tree elmt_type2 = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref2, 0)));
+
+ if (TREE_OPERAND (ref1, 3))
+ {
+ if (TYPE_ALIGN (elmt_type1) != TYPE_ALIGN (elmt_type2)
+ || !operand_equal_p (TREE_OPERAND (ref1, 3),
+ TREE_OPERAND (ref2, 3), 0))
+ return -1;
+ }
+ else
+ {
+ if (!operand_equal_p (TYPE_SIZE_UNIT (elmt_type1),
+ TYPE_SIZE_UNIT (elmt_type2), 0))
+ return -1;
+ }
+
+ /* Since we know that type sizes are the same, there is no need to return
+ -1 after this point. Partial overlap can not be introduced. */
+
+ /* We may need to fold trees in this case.
+ TODO: Handle integer constant case at least. */
+ if (!operand_equal_p (low_bound1, low_bound2, 0))
+ return 0;
+
+ if (TREE_CODE (index1) == INTEGER_CST && TREE_CODE (index2) == INTEGER_CST)
+ {
+ if (tree_int_cst_equal (index1, index2))
+ return 0;
+ return 1;
+ }
+ /* TODO: We can use VRP to further disambiguate here. */
+ return 0;
+}
+
/* Try to disambiguate REF1 and REF2 under the assumption that MATCH1 and
MATCH2 either point to the same address or are disjoint.
MATCH1 and MATCH2 are assumed to be ref in the access path of REF1 and REF2
respectively or NULL in the case we established equivalence of bases.
+ If PARTIAL_OVERLAP is true assume that the toplevel arrays may actually
+ overlap by exact multiply of their element size.
This test works by matching the initial segment of the access path
and does not rely on TBAA thus is safe for !flag_strict_aliasing if
oracles. */
static int
-nonoverlapping_component_refs_since_match_p (tree match1, tree ref1,
- tree match2, tree ref2)
+nonoverlapping_refs_since_match_p (tree match1, tree ref1,
+ 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;
&& !tree_int_cst_equal (TREE_OPERAND (ref1, 1),
TREE_OPERAND (ref2, 1))))
{
- ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias;
+ ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
return -1;
}
case the return value will precisely be false. */
while (true)
{
- bool seen_noncomponent_ref_p = false;
+ /* Track if we seen unmatched ref with non-zero offset. In this case
+ we must look for partial overlaps. */
+ bool seen_unmatched_ref_p = false;
+
+ /* First match ARRAY_REFs an try to disambiguate. */
+ if (!component_refs1.is_empty ()
+ && !component_refs2.is_empty ())
+ {
+ unsigned int narray_refs1=0, narray_refs2=0;
+
+ /* We generally assume that both access paths starts by same sequence
+ of refs. However if number of array refs is not in sync, try
+ to recover and pop elts until number match. This helps the case
+ where one access path starts by array and other by element. */
+ for (narray_refs1 = 0; narray_refs1 < component_refs1.length ();
+ narray_refs1++)
+ if (TREE_CODE (component_refs1 [component_refs1.length()
+ - 1 - narray_refs1]) != ARRAY_REF)
+ break;
+
+ for (narray_refs2 = 0; narray_refs2 < component_refs2.length ();
+ narray_refs2++)
+ if (TREE_CODE (component_refs2 [component_refs2.length()
+ - 1 - narray_refs2]) != ARRAY_REF)
+ break;
+ 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
+ disjoint or equal. Consider the example:
+
+ unsigned char out[][1];
+ out[1]="a";
+ out[i][0];
+
+ Here bases out and out are same, but after removing the
+ [i] index, this invariant no longer holds, because
+ out[i] points to the middle of array out.
+
+ TODO: If size of type of the skipped reference is an integer
+ multiply of the size of type of the other reference this
+ invariant can be verified, but even then it is not completely
+ safe with !flag_strict_aliasing if the other reference contains
+ unbounded array accesses.
+ See */
+
+ if (!operand_equal_p (TREE_OPERAND (ref1, 1),
+ cheap_array_ref_low_bound (ref1), 0))
+ return 0;
+ }
+ 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;
+ }
+ /* Try to disambiguate matched arrays. */
+ for (unsigned int i = 0; i < narray_refs1; i++)
+ {
+ 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;
+ }
+ if (cmp == -1)
+ {
+ 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;
+ }
+ }
+
+ /* Next look for component_refs. */
do
{
if (component_refs1.is_empty ())
{
++alias_stats
- .nonoverlapping_component_refs_since_match_p_must_overlap;
+ .nonoverlapping_refs_since_match_p_must_overlap;
return 0;
}
ref1 = component_refs1.pop ();
+ ntbaa1--;
if (TREE_CODE (ref1) != COMPONENT_REF)
- seen_noncomponent_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))));
if (component_refs2.is_empty ())
{
++alias_stats
- .nonoverlapping_component_refs_since_match_p_must_overlap;
+ .nonoverlapping_refs_since_match_p_must_overlap;
return 0;
}
ref2 = component_refs2.pop ();
+ ntbaa2--;
if (TREE_CODE (ref2) != COMPONENT_REF)
- seen_noncomponent_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))));
tree type1 = DECL_CONTEXT (field1);
tree type2 = DECL_CONTEXT (field2);
+ partial_overlap = false;
+
/* If we skipped array refs on type of different sizes, we can
no longer be sure that there are not partial overlaps. */
- if (seen_noncomponent_ref_p
+ if (seen_unmatched_ref_p && ntbaa1 >= 0 && ntbaa2 >= 0
&& !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
{
++alias_stats
- .nonoverlapping_component_refs_since_match_p_may_alias;
+ .nonoverlapping_refs_since_match_p_may_alias;
return -1;
}
if (cmp == -1)
{
++alias_stats
- .nonoverlapping_component_refs_since_match_p_may_alias;
+ .nonoverlapping_refs_since_match_p_may_alias;
return -1;
}
else if (cmp == 1)
{
++alias_stats
- .nonoverlapping_component_refs_since_match_p_no_alias;
+ .nonoverlapping_refs_since_match_p_no_alias;
return 1;
}
}
- ++alias_stats.nonoverlapping_component_refs_since_match_p_must_overlap;
+ ++alias_stats.nonoverlapping_refs_since_match_p_must_overlap;
return 0;
}
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);
}
so we disambiguate component references manually. */
if (ref1 && ref2
&& handled_component_p (ref1) && handled_component_p (ref2)
- && nonoverlapping_component_refs_since_match_p (NULL, ref1,
- NULL, ref2) == 1)
+ && nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2, false) == 1)
return false;
return true;
|| (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
&& (TREE_CODE (dbase2) != TARGET_MEM_REF
|| (!TMR_INDEX (dbase2) && !TMR_INDEX2 (dbase2))))
- && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1
- && (TREE_CODE (TREE_TYPE (base1)) != ARRAY_TYPE
- || (TYPE_SIZE (TREE_TYPE (base1))
- && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) == INTEGER_CST)))
+ && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
{
- if (!ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2))
+ bool partial_overlap = (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
+ && (TYPE_SIZE (TREE_TYPE (base1))
+ && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1)))
+ != INTEGER_CST));
+ if (!partial_overlap
+ && !ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2))
return false;
if (!ref1 || !ref2
/* If there is must alias, there is no use disambiguating further. */
- || (known_eq (size1, max_size1) && known_eq (size2, max_size2)))
+ || (!partial_overlap
+ && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
return true;
- int res = nonoverlapping_component_refs_since_match_p (base1, ref1,
- base2, ref2);
+ int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
+ partial_overlap);
if (res == -1)
return !nonoverlapping_component_refs_p (ref1, ref2);
return !res;
return true;
if (ref1 && ref2)
{
- int res = nonoverlapping_component_refs_since_match_p (NULL, ref1,
- NULL, ref2);
+ int res = nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2,
+ false);
if (res != -1)
return !res;
}
&& (TREE_CODE (base2) != TARGET_MEM_REF
|| (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
&& same_type_for_tbaa (TREE_TYPE (ptrtype1),
- TREE_TYPE (ptrtype2)) == 1
+ TREE_TYPE (ptrtype2)) == 1)
+ {
/* But avoid treating arrays as "objects", instead assume they
can overlap by an exact multiple of their element size.
See gcc.dg/torture/alias-2.c. */
- && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE)
- {
- if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
+ bool partial_overlap = TREE_CODE (TREE_TYPE (ptrtype1)) == ARRAY_TYPE;
+
+ if (!partial_overlap
+ && !ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
return false;
if (!ref1 || !ref2
- || (known_eq (size1, max_size1) && known_eq (size2, max_size2)))
+ || (!partial_overlap
+ && known_eq (size1, max_size1) && known_eq (size2, max_size2)))
return true;
- int res = nonoverlapping_component_refs_since_match_p (base1, ref1,
- base2, ref2);
+ int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2,
+ partial_overlap);
if (res == -1)
return !nonoverlapping_component_refs_p (ref1, ref2);
return !res;
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. */
if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
{
struct cgraph_node *node = cgraph_node::get (callee);
- bitmap not_read;
+ bitmap read;
+ int id;
/* FIXME: Callee can be an OMP builtin that does not have a call graph
node yet. We should enforce that there are nodes for all decls in the
IL and remove this check instead. */
if (node
- && (not_read = ipa_reference_get_not_read_global (node))
- && bitmap_bit_p (not_read, ipa_reference_var_uid (base)))
+ && (id = ipa_reference_var_uid (base)) != -1
+ && (read = ipa_reference_get_read_global (node))
+ && !bitmap_bit_p (read, id))
goto process_args;
}
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. */
if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
{
struct cgraph_node *node = cgraph_node::get (callee);
- bitmap not_written;
+ bitmap written;
+ int id;
if (node
- && (not_written = ipa_reference_get_not_written_global (node))
- && bitmap_bit_p (not_written, ipa_reference_var_uid (base)))
+ && (id = ipa_reference_var_uid (base)) != -1
+ && (written = ipa_reference_get_written_global (node))
+ && !bitmap_bit_p (written, id))
return false;
}
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
maybe_skip_until (gimple *phi, tree &target, basic_block target_bb,
ao_ref *ref, tree vuse, bool tbaa_p, unsigned int &limit,
bitmap *visited, bool abort_on_visited,
- void *(*translate)(ao_ref *, tree, void *, bool *),
+ void *(*translate)(ao_ref *, tree, void *, translate_flags *),
+ translate_flags disambiguate_only,
void *data)
{
basic_block bb = gimple_bb (phi);
return !abort_on_visited;
vuse = get_continuation_for_phi (def_stmt, ref, tbaa_p, limit,
visited, abort_on_visited,
- translate, data);
+ translate, data, disambiguate_only);
if (!vuse)
return false;
continue;
--limit;
if (stmt_may_clobber_ref_p_1 (def_stmt, ref, tbaa_p))
{
- bool disambiguate_only = true;
+ translate_flags tf = disambiguate_only;
if (translate
- && (*translate) (ref, vuse, data, &disambiguate_only) == NULL)
+ && (*translate) (ref, vuse, data, &tf) == NULL)
;
else
return false;
get_continuation_for_phi (gimple *phi, ao_ref *ref, bool tbaa_p,
unsigned int &limit, bitmap *visited,
bool abort_on_visited,
- void *(*translate)(ao_ref *, tree, void *, bool *),
- void *data)
+ void *(*translate)(ao_ref *, tree, void *,
+ translate_flags *),
+ void *data,
+ translate_flags disambiguate_only)
{
unsigned nargs = gimple_phi_num_args (phi);
else if (! maybe_skip_until (phi, arg0, dom, ref, arg1, tbaa_p,
limit, visited,
abort_on_visited,
- /* Do not translate when walking over
+ translate,
+ /* Do not valueize when walking over
backedges. */
dominated_by_p
(CDI_DOMINATORS,
gimple_bb (SSA_NAME_DEF_STMT (arg1)),
phi_bb)
- ? NULL : translate, data))
+ ? TR_DISAMBIGUATE
+ : disambiguate_only, data))
return NULL_TREE;
}
void *
walk_non_aliased_vuses (ao_ref *ref, tree vuse, bool tbaa_p,
void *(*walker)(ao_ref *, tree, void *),
- void *(*translate)(ao_ref *, tree, void *, bool *),
+ void *(*translate)(ao_ref *, tree, void *,
+ translate_flags *),
tree (*valueize)(tree),
unsigned &limit, void *data)
{
{
if (!translate)
break;
- bool disambiguate_only = false;
+ translate_flags disambiguate_only = TR_TRANSLATE;
res = (*translate) (ref, vuse, data, &disambiguate_only);
/* Failed lookup and translation. */
if (res == (void *)-1)
else if (res != NULL)
break;
/* Translation succeeded, continue walking. */
- translated = translated || !disambiguate_only;
+ translated = translated || disambiguate_only == TR_TRANSLATE;
}
vuse = gimple_vuse (def_stmt);
}
projects / gcc.git / blobdiff