[PATCH] Track pure function call uses separately

[Richard Guenther]

On Fri, 27 Jun 2008, Richard Guenther wrote:

> On Thu, 26 Jun 2008, Daniel Berlin wrote:
>
>> On Thu, Jun 26, 2008 at 12:34 PM, Richard Guenther <rguenther@suse.de> 
>> wrote:
>>> 
>>> This adds the ability (on top of
>>> http://gcc.gnu.org/ml/gcc-patches/2008-06/msg01432.html - PING for that)
>> 
>> I thought I okayed that one on IRC.
>> I will do so explicitly in a moment.
>
> We have one "little" problem.  If we re-enable field-sensitive PTA
> then the transitive closure we use for computing the ESCAPED set
> is no longer equivalent to the reachability, which we really need
> to compute.  Consider
>
> struct Foo {
>  int *p;
>  int *q;
> };
>
> void __attribute__((noinline))
> bar (int **x)
> {
>  struct Foo *f = (struct Foo *)x;
>  *(f->q) = 0;
> }
>
> int foo(void)
> {
>  struct Foo f;
>  int i = 1, j = 2;
>  f.p = &i;
>  f.q = &j;
>  bar(&f.p);
>  return j;
> }
>
> extern void abort (void);
> int main()
> {
>  if (foo () != 0)
>    abort ();
> }
>
> where in foo we end up with
>
> ESCAPED = *ESCAPED
> derefaddrtmp.30 = &ESCAPED
> *ESCAPED = derefaddrtmp.30
> derefaddrtmp.31 = &NONLOCAL
> *ESCAPED = derefaddrtmp.31
> f = &i
> f.q = &j
> ESCAPED = &f
>
> and the solution
>
> ESCAPED = { ESCAPED NONLOCAL f i }
> f = { ESCAPED NONLOCAL i }
> f.q = { j }
>
> while f.q and j should also be escaped and f.q pointing to
> ESCAPED NONLOCAL as well.
>
> So what we would need here is a special deref constraint that
> dereferences all subvars and use that for the ESCAPED = *ESCAPED
> constraint.  Where can this be implemented?  I guess the solver
> itself doesn't know about subvariables, but at constraint generation
> time we cannot fix this either.  Computing the reachability after
> PTA does also not work because then the PTA results would be wrong
> again.
>
> Ideas?  It looks like we would need to add constraints on-the-fly
> during solving - is this possible at all?  (can you hint me at
> where I would need to add those?)

Ok, I have it "working" with something like the following.

Basically we need to treat 'reachability vars' specially, for
ESCAPED this is constraints of the form

  ESCAPED = x

(in the solution propagation propagate using set_union_all_fields)

  ESCAPED = &x

initially add all fields of x to ESCAPED.  Probably better done by
collapsing x - the solution of x will get all of ESCAPED through
the *ESCAPED = ESCAPED constraint anyway, so no point in processing
the fields of x separately.  (Ideally we would collapse during
solving, but that doesn't look easily doable(?))

  ESCAPED = *ESCAPED

I hacked do_sd_constraint to handle this special case - we need
to add all fields the solution in ESCAPED can reach.

So, it gets somewhat ugly, and of course I am not sure that
variable unification will not get in our way ... (when exactly
are two variables unified?)

Thanks,
Richard.


Index: trunk/gcc/tree-ssa-structalias.c
===================================================================
--- trunk.orig/gcc/tree-ssa-structalias.c	2008-06-27 14:32:22.000000000 +0200
+++ trunk/gcc/tree-ssa-structalias.c	2008-06-27 14:24:27.000000000 +0200
@@ -262,6 +262,7 @@ struct variable_info
  typedef struct variable_info *varinfo_t;

  static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
+static varinfo_t lookup_vi_for_tree (tree);

  /* Pool of variable info structures.  */
  static alloc_pool variable_info_pool;
@@ -1114,7 +1115,18 @@ build_succ_graph (void)
  	  /* x = &y */
  	  gcc_assert (find (get_varinfo_fc (rhs.var)->id)
  		      == get_varinfo_fc (rhs.var)->id);
-	  bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
+	  if (lhs.var == escaped_id)
+	    {
+	      /* We might want to simply collapse the rhs variable at this
+	         point.
+		 ???  This would need to happen at the point we generate
+		 the constraint.  */
+	      varinfo_t vi = lookup_vi_for_tree (get_varinfo_fc (rhs.var)->decl);
+	      for (; vi != NULL; vi = vi->next)
+		bitmap_set_bit (get_varinfo (lhsvar)->solution, vi->id);
+	    }
+	  else
+	    bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
  	}
        else if (lhsvar > anything_id
  	       && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
@@ -1400,13 +1412,45 @@ do_sd_constraint (constraint_graph_t gra
    unsigned int j;
    bitmap_iterator bi;

- if (bitmap_bit_p (delta, anything_id))
-   {
-     flag = !bitmap_bit_p (sol, anything_id);
-     if (flag)
-       bitmap_set_bit (sol, anything_id);
-     goto done;
-   }
+  if (bitmap_bit_p (delta, anything_id))
+    {
+      flag = !bitmap_bit_p (sol, anything_id);
+      if (flag)
+	bitmap_set_bit (sol, anything_id);
+      goto done;
+    }
+
+  /* For x = *ESCAPED we interpret the deref as dereferencing all fields
+     of the ESCAPED solution variables.
+     ???  The question is if this works reliably if subvars are
+     collapsed.  We might not see the original variable in delta and thus
+     not reach other fields.  */
+  if (c->rhs.var == escaped_id)
+    {
+      EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
+	{
+	  varinfo_t v = lookup_vi_for_tree (get_varinfo (j)->decl);
+
+	  /* Only process one field as representative.  */
+	  if (v != get_varinfo (j)
+	      && bitmap_bit_p (delta, v->id))
+	    continue;
+
+	  for (; v != NULL; v = v->next)
+	    {
+	      unsigned int t = find (v->id);
+ 
+	      /* Adding edges from the special vars is pointless.
+		 They don't have sets that can change.  */
+	      if (get_varinfo (t)->is_special_var)
+		flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+	      else if (add_graph_edge (graph, lhs, t))
+		flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+	    }
+	}
+      goto done;
+    }
+
    /* For each variable j in delta (Sol(y)), add
       an edge in the graph from j to x, and union Sol(j) into Sol(x).  */
    EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
@@ -1564,6 +1608,30 @@ do_complex_constraint (constraint_graph_
      }
  }

+static bool
+set_union_all_fields (bitmap tmp, bitmap pts)
+{
+  bitmap_iterator bi;
+  unsigned i;
+  bool flag = false;
+
+  /* For each variable in pts add all its decls variables to tmp.  */
+  EXECUTE_IF_SET_IN_BITMAP (pts, 0, i, bi)
+    {
+      varinfo_t vi = lookup_vi_for_tree (get_varinfo (i)->decl);
+      if (vi != get_varinfo (i)
+	  && bitmap_bit_p (pts, vi->id))
+	continue;
+      for (; vi != NULL; vi = vi->next)
+	{
+	  flag |= bitmap_bit_p (tmp, vi->id);
+	  bitmap_set_bit (tmp, vi->id);
+	}
+    }
+
+  return flag;
+}
+
  /* Initialize and return a new SCC info structure.  */

  static struct scc_info *
@@ -2378,7 +2446,12 @@ solve_graph (constraint_graph_t graph)
  		      if (to == i)
  			continue;

-		      flag = set_union_with_increment (tmp, pts, 0);
+		      /* If this is a copy to the reachability set
+		         ESCAPED, process it specially.  */
+		      if (to == escaped_id)
+			flag = set_union_all_fields (tmp, pts);
+		      else
+			flag = set_union_with_increment (tmp, pts, 0);

  		      if (flag)
  			{