[PATCH] Improve PTA flow-sensitivity (for the return stmt)
Richard Biener
rguenther@suse.de
Wed Jun 5 13:53:00 GMT 2019
On Wed, 5 Jun 2019, Martin Sebor wrote:
> On 6/5/19 6:51 AM, Richard Biener wrote:
> >
> > The following was inspired by Marins work on escapes of locals
> > and the discussion there. It teaches points-to analysis that
> > the point of function return is special and thus escapes through
> > that a) do not influence other points-to solutions, b) can be
> > pruned of all locals.
> >
> > This is one example of reasonably simple "post-processing".
> >
> > The effects are small, I've done statistics, counting the number
> > of variables we do not mark escaped only after this patch. This
> > number is usually zero, sometimes one and a few cases more
> > (but never more than 11) during bootstrap:
> >
> > 0 95830
> > 1 19268
> > 2 19
> > 3 2
> > 5 2
> > 6 1
> > 8 1
> > 11 1
> >
> > so not sure if it is worth all the effort. It does allow us
> > to do more DSE but that requires the accesses to be indirect
> > which is not often true for locals.
> >
> > Bootstrapped / tested on x86_64-unknown-linux-gnu.
> >
> > Martin, does this help you at all? Anybody thinks this is
> > worth the trouble?
>
> IIUC, it would help with only one aspect of what I'm doing:
> distinguish alloca/VLAs from heap memory. I don't think it
> would make it any easier to track down the actual allocations.
> In my prototype (using the oracle) I would find the variables
> whose address is being returned by iterating over local DECLs
> and matching those against the vars bitmap. But unless there's
> a way to include the alloca statements in that traversal I don't
> see how to find those.
Btw, you could gather alloca "bits" up-front in a similar
way fold_builtin_alloca_with_align gets at them. The
singleton ID can then be used to check points-to solutions.
But of course points-to solutions are conservative, so
a return p; might just point to all locals (in fact after
this patch it won't point to _any_ locals anymore which
probably defeats using the oracle for the purpose of finding
escaped locals).
> That said, I'd say the improved accuracy the patch gives us
> certainly makes it worth keeping. There might be other
> solutions besides what I'm doing where distinguishing alloca
> from malloc will be important and where tracking down
> the allocations won't be an issue.
OK.
Thanks,
Richard.
> Thanks for working on this!
>
> Martin
>
> >
> > Thanks,
> > Richard.
> >
> > 2019-06-05 Richard Biener <rguenther@suse.de>
> >
> > * tree-ssa-structalias.c: Include tree-cfg.h.
> > (make_heapvar): Do not make heap vars artificial.
> > (find_func_aliases_for_builtin_call): Handle stack allocation
> > functions.
> > (find_func_aliases): Delay processing of simple enough returns
> > in non-IPA mode.
> > (set_uids_in_ptset): Adjust.
> > (find_what_var_points_to): Likewise.
> > (solve_constraints): Do not dump points-to sets here.
> > (compute_points_to_sets): Post-process return statements,
> > amending the escaped solution. Dump points-to sets afterwards.
> > (ipa_pta_execute): Dump points-to sets.
> >
> > * gcc.dg/tree-ssa/alias-37.c: New testcase.
> > * gcc.dg/torture/20190604-1.c: Likewise.
> > * gcc.dg/tree-ssa/pta-callused.c: Adjust.
> >
> > Index: gcc/tree-ssa-structalias.c
> > ===================================================================
> > --- gcc/tree-ssa-structalias.c (revision 271951)
> > +++ gcc/tree-ssa-structalias.c (working copy)
> > @@ -43,6 +43,7 @@
> > #include "stringpool.h"
> > #include "attribs.h"
> > #include "tree-ssa.h"
> > +#include "tree-cfg.h"
> > /* The idea behind this analyzer is to generate set constraints from the
> > program, then solve the resulting constraints in order to generate the
> > @@ -3854,7 +3855,6 @@ make_heapvar (const char *name, bool add
> > DECL_EXTERNAL (heapvar) = 1;
> > vi = new_var_info (heapvar, name, add_id);
> > - vi->is_artificial_var = true;
> > vi->is_heap_var = true;
> > vi->is_unknown_size_var = true;
> > vi->offset = 0;
> > @@ -4409,6 +4409,32 @@ find_func_aliases_for_builtin_call (stru
> > process_constraint (new_constraint (*lhsp, ac));
> > return true;
> > }
> > + case BUILT_IN_STACK_SAVE:
> > + case BUILT_IN_STACK_RESTORE:
> > + /* Nothing interesting happens. */
> > + return true;
> > + case BUILT_IN_ALLOCA:
> > + case BUILT_IN_ALLOCA_WITH_ALIGN:
> > + case BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX:
> > + {
> > + tree ptr = gimple_call_lhs (t);
> > + if (ptr == NULL_TREE)
> > + return true;
> > + get_constraint_for (ptr, &lhsc);
> > + varinfo_t vi = make_heapvar ("HEAP", true);
> > + /* Alloca storage is never global. To exempt it from escaped
> > + handling make it a non-heap var. */
> > + DECL_EXTERNAL (vi->decl) = 0;
> > + vi->is_global_var = 0;
> > + vi->is_heap_var = 0;
> > + struct constraint_expr tmpc;
> > + tmpc.var = vi->id;
> > + tmpc.offset = 0;
> > + tmpc.type = ADDRESSOF;
> > + rhsc.safe_push (tmpc);
> > + process_all_all_constraints (lhsc, rhsc);
> > + return true;
> > + }
> > case BUILT_IN_POSIX_MEMALIGN:
> > {
> > tree ptrptr = gimple_call_arg (t, 0);
> > @@ -4976,7 +5002,12 @@ find_func_aliases (struct function *fn,
> > greturn *return_stmt = as_a <greturn *> (t);
> > fi = NULL;
> > if (!in_ipa_mode
> > - || !(fi = get_vi_for_tree (fn->decl)))
> > + && SSA_VAR_P (gimple_return_retval (return_stmt)))
> > + {
> > + /* We handle simple returns by post-processing the solutions. */
> > + ;
> > + }
> > + if (!(fi = get_vi_for_tree (fn->decl)))
> > make_escape_constraint (gimple_return_retval (return_stmt));
> > else if (in_ipa_mode)
> > {
> > @@ -6422,9 +6453,7 @@ set_uids_in_ptset (bitmap into, bitmap f
> > {
> > varinfo_t vi = get_varinfo (i);
> > - /* The only artificial variables that are allowed in a may-alias
> > - set are heap variables. */
> > - if (vi->is_artificial_var && !vi->is_heap_var)
> > + if (vi->is_artificial_var)
> > continue;
> > if (everything_escaped
> > @@ -6544,9 +6573,6 @@ find_what_var_points_to (tree fndecl, va
> > }
> > else if (vi->id == nonlocal_id)
> > pt->nonlocal = 1;
> > - else if (vi->is_heap_var)
> > - /* We represent heapvars in the points-to set properly. */
> > - ;
> > else if (vi->id == string_id)
> > /* Nobody cares - STRING_CSTs are read-only entities. */
> > ;
> > @@ -7254,9 +7280,6 @@ solve_constraints (void)
> > dump_constraint_graph (dump_file);
> > fprintf (dump_file, "\n\n");
> > }
> > -
> > - if (dump_file)
> > - dump_sa_points_to_info (dump_file);
> > }
> > /* Create points-to sets for the current function. See the comments
> > @@ -7304,6 +7327,73 @@ compute_points_to_sets (void)
> > /* From the constraints compute the points-to sets. */
> > solve_constraints ();
> > + /* Post-process solutions for escapes through returns. */
> > + edge_iterator ei;
> > + edge e;
> > + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
> > + if (greturn *ret = safe_dyn_cast <greturn *> (last_stmt (e->src)))
> > + {
> > + tree val = gimple_return_retval (ret);
> > + /* ??? Easy to handle simple indirections with some work.
> > + Arbitrary references like foo.bar.baz are more difficult
> > + (but conservatively easy enough with just looking at the base).
> > + Mind to fixup find_func_aliases as well. */
> > + if (!val || !SSA_VAR_P (val))
> > + continue;
> > + /* returns happen last in non-IPA so they only influence
> > + the ESCAPED solution and we can filter local variables. */
> > + varinfo_t escaped_vi = get_varinfo (find (escaped_id));
> > + varinfo_t vi = lookup_vi_for_tree (val);
> > + bitmap delta = BITMAP_ALLOC (&pta_obstack);
> > + bitmap_iterator bi;
> > + unsigned i;
> > + for (; vi; vi = vi_next (vi))
> > + {
> > + varinfo_t part_vi = get_varinfo (find (vi->id));
> > + EXECUTE_IF_AND_COMPL_IN_BITMAP (part_vi->solution,
> > + escaped_vi->solution, 0, i, bi)
> > + {
> > + varinfo_t pointed_to_vi = get_varinfo (i);
> > + if (pointed_to_vi->is_global_var
> > + /* We delay marking of heap memory as global. */
> > + || pointed_to_vi->is_heap_var)
> > + bitmap_set_bit (delta, i);
> > + }
> > + }
> > +
> > + /* Now compute the transitive closure. */
> > + bitmap_ior_into (escaped_vi->solution, delta);
> > + bitmap new_delta = BITMAP_ALLOC (&pta_obstack);
> > + while (!bitmap_empty_p (delta))
> > + {
> > + EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
> > + {
> > + varinfo_t pointed_to_vi = get_varinfo (i);
> > + pointed_to_vi = get_varinfo (find (pointed_to_vi->id));
> > + unsigned j;
> > + bitmap_iterator bi2;
> > + EXECUTE_IF_AND_COMPL_IN_BITMAP (pointed_to_vi->solution,
> > + escaped_vi->solution,
> > + 0, j, bi2)
> > + {
> > + varinfo_t pointed_to_vi2 = get_varinfo (j);
> > + if (pointed_to_vi2->is_global_var
> > + /* We delay marking of heap memory as global. */
> > + || pointed_to_vi2->is_heap_var)
> > + bitmap_set_bit (new_delta, j);
> > + }
> > + }
> > + bitmap_ior_into (escaped_vi->solution, new_delta);
> > + bitmap_clear (delta);
> > + std::swap (delta, new_delta);
> > + }
> > + BITMAP_FREE (delta);
> > + BITMAP_FREE (new_delta);
> > + }
> > +
> > + if (dump_file)
> > + dump_sa_points_to_info (dump_file);
> > +
> > /* Compute the points-to set for ESCAPED used for call-clobber analysis.
> > */
> > cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl,
> > get_varinfo
> > (escaped_id));
> > @@ -8109,6 +8199,9 @@ ipa_pta_execute (void)
> > /* From the constraints compute the points-to sets. */
> > solve_constraints ();
> > + if (dump_file)
> > + dump_sa_points_to_info (dump_file);
> > +
> > /* Now post-process solutions to handle locals from different
> > runtime instantiations coming in through recursive invocations. */
> > unsigned shadow_var_cnt = 0;
> > Index: gcc/testsuite/gcc.dg/tree-ssa/alias-37.c
> > ===================================================================
> > --- gcc/testsuite/gcc.dg/tree-ssa/alias-37.c (nonexistent)
> > +++ gcc/testsuite/gcc.dg/tree-ssa/alias-37.c (working copy)
> > @@ -0,0 +1,17 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-dse1-details" } */
> > +
> > +int i;
> > +int *foo (int bogus, int n)
> > +{
> > + int a[n];
> > + a[2] = bogus; /* Should elide this store since a cannot escape. */
> > + int *p;
> > + if (bogus)
> > + p = &a[2];
> > + else
> > + p = &i;
> > + return p;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump "Deleted dead store" "dse1" } } */
> > Index: gcc/testsuite/gcc.dg/torture/20190604-1.c
> > ===================================================================
> > --- gcc/testsuite/gcc.dg/torture/20190604-1.c (nonexistent)
> > +++ gcc/testsuite/gcc.dg/torture/20190604-1.c (working copy)
> > @@ -0,0 +1,21 @@
> > +/* { dg-do run } */
> > +
> > +struct S { int *mem; };
> > +
> > +struct S * __attribute__((noinline,noipa))
> > +foo ()
> > +{
> > + struct S *s = __builtin_malloc (sizeof (struct S));
> > + s->mem = __builtin_malloc (sizeof (int));
> > + s->mem[0] = 1;
> > + return s;
> > +}
> > +
> > +int
> > +main()
> > +{
> > + struct S *s = foo();
> > + if (s->mem[0] != 1)
> > + __builtin_abort ();
> > + return 0;
> > +}
> > Index: gcc/testsuite/gcc.dg/tree-ssa/pta-callused.c
> > ===================================================================
> > --- gcc/testsuite/gcc.dg/tree-ssa/pta-callused.c (revision 271951)
> > +++ gcc/testsuite/gcc.dg/tree-ssa/pta-callused.c (working copy)
> > @@ -22,5 +22,5 @@ int bar (int b)
> > return *foo (&q);
> > }
> > -/* { dg-final { scan-tree-dump "CALLUSED\\(\[0-9\]+\\) = { ESCAPED
> > NONLOCAL f.* i q }" "alias" } } */
> > +/* { dg-final { scan-tree-dump "CALLUSED\\(\[0-9\]+\\) = { f.* i q }"
> > "alias" } } */
> >
>
>
--
Richard Biener <rguenther@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
More information about the Gcc-patches
mailing list