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 <rguent...@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 <rguent...@suse.de> SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)