Track access ranges in ipa-modref
Jan Hubicka
hubicka@ucw.cz
Fri Oct 2 08:37:49 GMT 2020
Hi,
this patch implements tracking of access ranges. This is only applied when
base pointer is an arugment. Incrementally i will extend it to also track
TBAA basetype so we can disambiguate ranges for accesses to same basetype
(which makes is quite bit more effective). For this reason i track the access
offset separately from parameter offset (the second track combined adjustments
to the parameter). This is I think last feature I would like to add to the
memory access summary this stage1.
Further work will be needed to opitmize the summary and merge adjacent
range/make collapsing more intelingent (so we do not lose track that often),
but I wanted to keep basic patch simple.
According to the cc1plus stats:
Alias oracle query stats:
refs_may_alias_p: 64108082 disambiguations, 74386675 queries
ref_maybe_used_by_call_p: 142319 disambiguations, 65004781 queries
call_may_clobber_ref_p: 23587 disambiguations, 29420 queries
nonoverlapping_component_refs_p: 0 disambiguations, 38117 queries
nonoverlapping_refs_since_match_p: 19489 disambiguations, 55748 must overlaps, 76044 queries
aliasing_component_refs_p: 54763 disambiguations, 755876 queries
TBAA oracle: 24184658 disambiguations 56823187 queries
16260329 are in alias set 0
10617146 queries asked about the same object
125 queries asked about the same alias set
0 access volatile
3960555 are dependent in the DAG
1800374 are aritificially in conflict with void *
Modref stats:
modref use: 10656 disambiguations, 47037 queries
modref clobber: 1473322 disambiguations, 1961464 queries
5027242 tbaa queries (2.563005 per modref query)
649087 base compares (0.330920 per modref query)
PTA query stats:
pt_solution_includes: 977385 disambiguations, 13609749 queries
pt_solutions_intersect: 1032703 disambiguations, 13187507 queries
Which should still compare with
https://gcc.gnu.org/pipermail/gcc-patches/2020-September/554930.html
there is about 2% more load disambiguations and 3.6% more store that is not
great, but the TBAA part helps noticeably more and also this should help
with -fno-strict-aliasing.
I plan to work on improving param tracking too.
Bootstrapped/regtested x86_64-linux with the other changes, OK?
2020-10-02 Jan Hubicka <hubicka@ucw.cz>
* ipa-modref-tree.c (test_insert_search_collapse): Update andling
of accesses.
(test_merge): Likewise.
* ipa-modref-tree.h (struct modref_access_node): Add offset, size,
max_size, parm_offset and parm_offset_known.
(modref_access_node::useful_p): Constify.
(modref_access_node::range_info_useful_p): New predicate.
(modref_access_node::operator==): New.
(struct modref_parm_map): New structure.
(modref_tree::merge): Update for racking parameters)
* ipa-modref.c (dump_access): Dump new fields.
(get_access): Fill in new fields.
(merge_call_side_effects): Update handling of parm map.
(write_modref_records): Stream new fields.
(read_modref_records): Stream new fields.
(compute_parm_map): Update for new parm map.
(ipa_merge_modref_summary_after_inlining): Update.
(modref_propagate_in_scc): Update.
* tree-ssa-alias.c (modref_may_conflict): Handle known ranges.
gcc/testsuite/ChangeLog:
2020-10-02 Jan Hubicka <hubicka@ucw.cz>
* gcc.dg/tree-ssa/modref-3.c: New test.
diff --git a/gcc/ipa-modref-tree.c b/gcc/ipa-modref-tree.c
index 499dc60b75e..1a595090b6c 100644
--- a/gcc/ipa-modref-tree.c
+++ b/gcc/ipa-modref-tree.c
@@ -35,7 +35,7 @@ test_insert_search_collapse ()
{
modref_base_node<alias_set_type> *base_node;
modref_ref_node<alias_set_type> *ref_node;
- modref_access_node a = { -1 };
+ modref_access_node a = unspecified_modref_access_node;
modref_tree<alias_set_type> *t = new modref_tree<alias_set_type>(1, 2, 2);
ASSERT_FALSE (t->every_base);
@@ -118,7 +118,7 @@ test_merge ()
{
modref_tree<alias_set_type> *t1, *t2;
modref_base_node<alias_set_type> *base_node;
- modref_access_node a = { -1 };
+ modref_access_node a = unspecified_modref_access_node;
t1 = new modref_tree<alias_set_type>(3, 4, 1);
t1->insert (1, 1, a);
diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h
index abf3fc18b05..b37280d18c7 100644
--- a/gcc/ipa-modref-tree.h
+++ b/gcc/ipa-modref-tree.h
@@ -44,17 +44,56 @@ struct ipa_modref_summary;
/* Memory access. */
struct GTY(()) modref_access_node
{
+
+ /* Access range information (in bits). */
+ poly_int64 offset;
+ poly_int64 size;
+ poly_int64 max_size;
+
+ /* Offset from parmeter pointer to the base of the access (in bytes). */
+ poly_int64 parm_offset;
+
/* Index of parameter which specifies the base of access. -1 if base is not
a function parameter. */
int parm_index;
+ bool parm_offset_known;
/* Return true if access node holds no useful info. */
- bool useful_p ()
+ bool useful_p () const
{
return parm_index != -1;
}
+ /* Return true if range info is useful. */
+ bool range_info_useful_p () const
+ {
+ return parm_index != -1 && parm_offset_known;
+ }
+ /* Return true if both accesses are the same. */
+ bool operator == (modref_access_node &a) const
+ {
+ if (parm_index != a.parm_index)
+ return false;
+ if (parm_index >= 0)
+ {
+ if (parm_offset_known != a.parm_offset_known)
+ return false;
+ if (parm_offset_known
+ && !known_eq (parm_offset, a.parm_offset))
+ return false;
+ }
+ if (range_info_useful_p ()
+ && (!known_eq (a.offset, offset)
+ || !known_eq (a.size, size)
+ || !known_eq (a.max_size, max_size)))
+ return false;
+ return true;
+ }
};
+/* Access node specifying no useful info. */
+const modref_access_node unspecified_modref_access_node
+ = {0, -1, -1, 0, -1, false};
+
template <typename T>
struct GTY((user)) modref_ref_node
{
@@ -74,7 +113,7 @@ struct GTY((user)) modref_ref_node
size_t i;
modref_access_node *a;
FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
- if (a->parm_index == access.parm_index)
+ if (*a == access)
return a;
return NULL;
}
@@ -195,6 +234,19 @@ struct GTY((user)) modref_base_node
}
};
+/* Map translating parameters across function call. */
+
+struct modref_parm_map
+{
+ /* Index of parameter we translate to.
+ -1 indicates that parameter is unknown
+ -2 indicates that parmaeter points to local memory and access can be
+ discarded. */
+ int parm_index;
+ bool parm_offset_known;
+ poly_int64 parm_offset;
+};
+
/* Access tree for a single function. */
template <typename T>
struct GTY((user)) modref_tree
@@ -363,7 +415,7 @@ struct GTY((user)) modref_tree
PARM_MAP, if non-NULL, maps parm indexes of callee to caller. -2 is used
to signalize that parameter is local and does not need to be tracked.
Return true if something has changed. */
- bool merge (modref_tree <T> *other, vec <int> *parm_map)
+ bool merge (modref_tree <T> *other, vec <modref_parm_map> *parm_map)
{
if (!other || every_base)
return false;
@@ -406,21 +458,31 @@ struct GTY((user)) modref_tree
{
if (ref_node->every_access)
{
- modref_access_node a = {-1};
- changed |= insert (base_node->base, ref_node->ref, a);
+ changed |= insert (base_node->base,
+ ref_node->ref,
+ unspecified_modref_access_node);
}
else
FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
{
modref_access_node a = *access_node;
+
if (a.parm_index != -1 && parm_map)
{
if (a.parm_index >= (int)parm_map->length ())
a.parm_index = -1;
- else if ((*parm_map) [a.parm_index] == -2)
+ else if ((*parm_map) [a.parm_index].parm_index == -2)
continue;
else
- a.parm_index = (*parm_map) [a.parm_index];
+ {
+ a.parm_offset
+ += (*parm_map) [a.parm_index].parm_offset;
+ a.parm_offset_known
+ &= (*parm_map)
+ [a.parm_index].parm_offset_known;
+ a.parm_index
+ = (*parm_map) [a.parm_index].parm_index;
+ }
}
changed |= insert (base_node->base, ref_node->ref, a);
}
diff --git a/gcc/ipa-modref.c b/gcc/ipa-modref.c
index 71a79553953..a5fa33a35de 100644
--- a/gcc/ipa-modref.c
+++ b/gcc/ipa-modref.c
@@ -143,7 +143,26 @@ modref_summary::useful_p (int ecf_flags)
static void
dump_access (modref_access_node *a, FILE *out)
{
- fprintf (out, " Parm %i\n", a->parm_index);
+ fprintf (out, " access:");
+ if (a->parm_index != -1)
+ {
+ fprintf (out, " Parm %i", a->parm_index);
+ if (a->parm_offset_known)
+ {
+ fprintf (out, " param offset:");
+ print_dec ((poly_int64_pod)a->parm_offset, out, SIGNED);
+ }
+ }
+ if (a->range_info_useful_p ())
+ {
+ fprintf (out, " offset:");
+ print_dec ((poly_int64_pod)a->offset, out, SIGNED);
+ fprintf (out, " size:");
+ print_dec ((poly_int64_pod)a->size, out, SIGNED);
+ fprintf (out, " max_size:");
+ print_dec ((poly_int64_pod)a->max_size, out, SIGNED);
+ }
+ fprintf (out, "\n");
}
/* Dump records TT to OUT. */
@@ -292,14 +311,15 @@ get_modref_function_summary (cgraph_node *func)
static modref_access_node
get_access (ao_ref *ref)
{
- modref_access_node a;
tree base;
- base = ref->ref;
- while (handled_component_p (base))
- base = TREE_OPERAND (base, 0);
+ base = ao_ref_base (ref);
+ modref_access_node a = {ref->offset, ref->size, ref->max_size,
+ 0, -1, false};
if (TREE_CODE (base) == MEM_REF || TREE_CODE (base) == TARGET_MEM_REF)
{
+ tree offset = TREE_CODE (base) == MEM_REF
+ ? TREE_OPERAND (base, 1) : NULL_TREE;
base = TREE_OPERAND (base, 0);
if (TREE_CODE (base) == SSA_NAME
&& SSA_NAME_IS_DEFAULT_DEF (base)
@@ -316,6 +336,8 @@ get_access (ao_ref *ref)
}
a.parm_index++;
}
+ a.parm_offset_known
+ = offset && wi::to_poly_offset (offset).to_shwi (&a.parm_offset);
}
else
a.parm_index = -1;
@@ -446,7 +468,7 @@ merge_call_side_effects (modref_summary *cur_summary,
gimple *stmt, modref_summary *callee_summary,
bool ignore_stores)
{
- auto_vec <int, 32> parm_map;
+ auto_vec <modref_parm_map, 32> parm_map;
bool changed = false;
parm_map.safe_grow (gimple_call_num_args (stmt));
@@ -469,12 +491,14 @@ merge_call_side_effects (modref_summary *cur_summary,
}
index++;
}
- parm_map[i] = index;
+ parm_map[i].parm_index = index;
+ parm_map[i].parm_offset_known = true;
+ parm_map[i].parm_offset = 0;
}
else if (points_to_local_or_readonly_memory_p (op))
- parm_map[i] = -2;
+ parm_map[i].parm_index = -2;
else
- parm_map[i] = -1;
+ parm_map[i].parm_index = -1;
}
/* Merge with callee's summary. */
@@ -970,7 +994,20 @@ write_modref_records (modref_records_lto *tt, struct output_block *ob)
size_t k;
modref_access_node *access_node;
FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
- streamer_write_uhwi (ob, access_node->parm_index);
+ {
+ streamer_write_uhwi (ob, access_node->parm_index);
+ if (access_node->parm_index != -1)
+ {
+ streamer_write_uhwi (ob, access_node->parm_offset_known);
+ if (access_node->parm_offset_known)
+ {
+ streamer_write_poly_int64 (ob, access_node->parm_offset);
+ streamer_write_poly_int64 (ob, access_node->offset);
+ streamer_write_poly_int64 (ob, access_node->size);
+ streamer_write_poly_int64 (ob, access_node->max_size);
+ }
+ }
+ }
}
}
}
@@ -1084,7 +1121,25 @@ read_modref_records (lto_input_block *ib, struct data_in *data_in,
for (size_t k = 0; k < naccesses; k++)
{
int parm_index = streamer_read_uhwi (ib);
- modref_access_node a = {parm_index};
+ bool parm_offset_known = false;
+ poly_int64 parm_offset = 0;
+ poly_int64 offset = 0;
+ poly_int64 size = -1;
+ poly_int64 max_size = -1;
+
+ if (parm_index != -1)
+ {
+ parm_offset_known = streamer_read_uhwi (ib);
+ if (parm_offset_known)
+ {
+ parm_offset = streamer_read_poly_int64 (ib);
+ offset = streamer_read_poly_int64 (ib);
+ size = streamer_read_poly_int64 (ib);
+ max_size = streamer_read_poly_int64 (ib);
+ }
+ }
+ modref_access_node a = {offset, size, max_size, parm_offset,
+ parm_index, parm_offset_known};
if (nolto_ref_node)
nolto_ref_node->insert_access (a, max_accesses);
if (lto_ref_node)
@@ -1331,7 +1386,7 @@ ignore_edge (struct cgraph_edge *e)
/* Compute parm_map for CALLE_EDGE. */
static void
-compute_parm_map (cgraph_edge *callee_edge, vec<int> *parm_map)
+compute_parm_map (cgraph_edge *callee_edge, vec<modref_parm_map> *parm_map)
{
class ipa_edge_args *args;
if (ipa_node_params_sum
@@ -1357,7 +1412,7 @@ compute_parm_map (cgraph_edge *callee_edge, vec<int> *parm_map)
{
if (es && es->param[i].points_to_local_or_readonly_memory)
{
- (*parm_map)[i] = -2;
+ (*parm_map)[i].parm_index = -2;
continue;
}
@@ -1371,26 +1426,33 @@ compute_parm_map (cgraph_edge *callee_edge, vec<int> *parm_map)
(callee_pi, i));
if (cst && points_to_local_or_readonly_memory_p (cst))
{
- (*parm_map)[i] = -2;
+ (*parm_map)[i].parm_index = -2;
continue;
}
}
if (jf && jf->type == IPA_JF_PASS_THROUGH)
{
- (*parm_map)[i]
+ (*parm_map)[i].parm_index
= ipa_get_jf_pass_through_formal_id (jf);
+ (*parm_map)[i].parm_offset_known
+ = ipa_get_jf_pass_through_operation (jf) == NOP_EXPR;
+ (*parm_map)[i].parm_offset = 0;
continue;
}
if (jf && jf->type == IPA_JF_ANCESTOR)
- (*parm_map)[i] = ipa_get_jf_ancestor_formal_id (jf);
+ {
+ (*parm_map)[i].parm_index = ipa_get_jf_ancestor_formal_id (jf);
+ (*parm_map)[i].parm_offset_known = true;
+ (*parm_map)[i].parm_offset = ipa_get_jf_ancestor_offset (jf);
+ }
else
- (*parm_map)[i] = -1;
+ (*parm_map)[i].parm_index = -1;
}
if (dump_file)
{
fprintf (dump_file, " Parm map: ");
for (i = 0; i < count; i++)
- fprintf (dump_file, " %i", (*parm_map)[i]);
+ fprintf (dump_file, " %i", (*parm_map)[i].parm_index);
fprintf (dump_file, "\n");
}
}
@@ -1432,7 +1494,7 @@ ipa_merge_modref_summary_after_inlining (cgraph_edge *edge)
}
else
{
- auto_vec <int, 32> parm_map;
+ auto_vec <modref_parm_map, 32> parm_map;
compute_parm_map (edge, &parm_map);
@@ -1598,7 +1660,7 @@ modref_propagate_in_scc (cgraph_node *component_node)
}
- auto_vec <int, 32> parm_map;
+ auto_vec <modref_parm_map, 32> parm_map;
compute_parm_map (callee_edge, &parm_map);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-3.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-3.c
new file mode 100644
index 00000000000..668c6c28831
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-3.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+struct a
+{
+ int b;
+ int c;
+};
+
+__attribute__ ((noclone, noinline))
+void
+test (struct a *a)
+{
+ a->b = 2;
+}
+int
+foo ()
+{
+ struct a a = {113,114};
+ test (&a);
+ return a.c;
+}
+int
+foo2 (struct a *a)
+{
+ a->b = 123;
+ a->c = 124;
+ test (a);
+ return a->c;
+}
+/* { dg-final { scan-tree-dump "return 114" "optimized"} } */
+/* { dg-final { scan-tree-dump "return 124" "optimized"} } */
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index fe390d4ffbe..1b83749f989 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -2475,8 +2505,8 @@ modref_may_conflict (const gimple *stmt,
}
/* TBAA checks did not disambiguate, try to use base pointer, for
- that we however need to have ref->ref. */
- if (ref_node->every_access || !ref->ref)
+ that we however need to have ref->ref or ref->base. */
+ if (ref_node->every_access || (!ref->ref && !ref->base))
return true;
modref_access_node *access_node;
@@ -2490,12 +2520,40 @@ modref_may_conflict (const gimple *stmt,
>= gimple_call_num_args (stmt))
return true;
-
alias_stats.modref_baseptr_tests++;
- if (ptr_deref_may_alias_ref_p_1
- (gimple_call_arg (stmt, access_node->parm_index), ref))
+ tree arg = gimple_call_arg (stmt, access_node->parm_index);
+
+ if (integer_zerop (arg) && flag_delete_null_pointer_checks)
+ continue;
+
+ if (!POINTER_TYPE_P (TREE_TYPE (arg)))
return true;
+
+ /* ao_ref_init_from_ptr_and_range assumes that memory access
+ starts by the pointed to location. If we did not track the
+ offset it is possible that it starts before the actual
+ pointer. */
+ if (!access_node->parm_offset_known)
+ {
+ if (ptr_deref_may_alias_ref_p_1 (arg, ref))
+ return true;
+ }
+ else
+ {
+ ao_ref ref2;
+
+ ao_ref_init_from_ptr_and_range
+ (&ref2, arg, true,
+ access_node->offset
+ + (access_node->parm_offset
+ << LOG2_BITS_PER_UNIT), access_node->size,
+ access_node->max_size);
+ ref2.ref_alias_set = ref_set;
+ ref2.base_alias_set = base_set;
+ if (refs_may_alias_p_1 (&ref2, ref, tbaa_p))
+ return true;
+ }
num_tests++;
}
}
More information about the Gcc-patches
mailing list