On Fri, 2 Oct 2020, Jan Hubicka wrote:
> 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?
LGTM.
Richard.
> 2020-10-02 Jan Hubicka <hubi...@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 <hubi...@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++;
> }
> }
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imend
