[PATCH] Improve PTA flow-sensitivity (for the return stmt)

[PATCH] Improve PTA flow-sensitivity (for the return stmt)

[Richard Biener]

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

Re: [PATCH] Improve PTA flow-sensitivity (for the return stmt)

[Martin Sebor]

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

Re: [PATCH] Improve PTA flow-sensitivity (for the return stmt)

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 12259 bytes --]

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)

Re: [PATCH] Improve PTA flow-sensitivity (for the return stmt)

[Jeff Law]

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?
> 
> 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.
It's a fair amount of code for a corner case, _but_ I think it's a step
in the right direction.  I suspect we ought to be using the alias oracle
solutions for more than we are today and improved precision certainly
doesn't hurt.

Jeff

Re: [PATCH] Improve PTA flow-sensitivity (for the return stmt)

[Marc Glisse]

On Wed, 5 Jun 2019, 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.

IIUC, if we did not have IPA and PT was used only to check for potential 
aliasing, we could skip return statements entirely. In that sense, it may 
sound worth working around the penalty imposed by the other uses, although 
after inlining the cases where this matters may be rare.

However, the patch doesn't really seem to disable much of the impact of a 
return statement. If I randomly try

int g;
int*f(int**x){
   int*p=*x;
   int*q=__builtin_malloc(4);
   *p=4;*q=5;g=*p;*p=6;
#ifdef OK
   int volatile i=*q;
   int*volatile v=q;
   return 0;
#else
   return q;
#endif
}

With -DOK, q does not escape, we know that p and q do not alias, and we 
simplify quite a bit. Without -DOK, q does escape, and we simplify 
nothing. Replacing malloc with alloca works, but returning a pointer to a 
local variable is not really an interesting case...

Maintaining 2 escaped sets (with/without returns) would be overkill for 
this, unless it was part of a wider flow-sensitivity strategy.

-- 
Marc Glisse

Re: [PATCH] Improve PTA flow-sensitivity (for the return stmt)

[Richard Biener]

On Mon, 10 Jun 2019, Marc Glisse wrote:

> On Wed, 5 Jun 2019, 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.
> 
> IIUC, if we did not have IPA and PT was used only to check for potential
> aliasing, we could skip return statements entirely. In that sense, it may
> sound worth working around the penalty imposed by the other uses, although
> after inlining the cases where this matters may be rare.
> 
> However, the patch doesn't really seem to disable much of the impact of a
> return statement. If I randomly try
> 
> int g;
> int*f(int**x){
>   int*p=*x;
>   int*q=__builtin_malloc(4);
>   *p=4;*q=5;g=*p;*p=6;
> #ifdef OK
>   int volatile i=*q;
>   int*volatile v=q;
>   return 0;
> #else
>   return q;
> #endif
> }
> 
> With -DOK, q does not escape, we know that p and q do not alias, and we
> simplify quite a bit. Without -DOK, q does escape, and we simplify nothing.
> Replacing malloc with alloca works, but returning a pointer to a local
> variable is not really an interesting case...
> 
> Maintaining 2 escaped sets (with/without returns) would be overkill for this,
> unless it was part of a wider flow-sensitivity strategy.

So even non-IPA needs escapes through return because we started to use
this to track whether allocated storage becomes "global" and thus
DSE needs to preserve stores that end up "used" by the return stmt(s).

The wider issue here is that PTA globs escapes through returns and
escapes through calls.  It somewhat makes sense since there's also
escapes through stores to global memory which means reachability
from both callees and callers.

So for the above example q _does_ escape through return q.

A first step would be to present a separate "escapes from function
invocation" to the PTA users.  Since there's global memory escapes
the optimization effect is probably similarly small as with the
return "enhacement" though.  The return enhancment helps when
local variables "leak" into the points-to sets returned from the
function.

Richard.