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?
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"
} } */
