[PATCH] Improve PTA flow-sensitivity (for the return stmt)
Martin Sebor
msebor@gmail.com
Wed Jun 5 13:44:00 GMT 2019
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.
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.
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" } } */
>
>
More information about the Gcc-patches
mailing list