[PATCH] Fix and re-enable field-sensitive PTA

Richard Guenther rguenther@suse.de
Wed Jul 2 14:14:00 GMT 2008


This patch fixes the call-clobbering code if you enable
field-sensitive PTA.  The issue is that for computing of the
ESCAPED and the CALLUSED sets we need to compute reachability.
With field-sensitive PTA this is no longer equivalent to
transitively closing the PTA solution.

Consider a struct with fields f.a and f.b.  With a call foo (&f)
you end up with the constraint

   ESCAPED = &f.a

but foo can also reach f.b through the pointer.  The fix is to
treat all variables as un-split during solving of the

   ESCAPED = *ESCAPED

constraint, thus adding all sub-fields to the solution whenever
at least one sub-field of the variable appears in the solution.

This is what the patch does.  It also re-enables field-sensitive PTA
at -O2 and higher, the behavior being on-par with the 4.3 branch now.

With some followups (or before this dependent on timing) I'll
shrink the variable_info struct somewhat and reduce the amount of
uninteresting fields generated, so we might be able to shrink the
100 in max-fields-for-field-sensitive somewhat.

Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?

Thanks,
Richard.

2008-07-02  Richard Guenther  <rguenther@suse.de>

 	* tree-ssa-structalias.c (lookup_vi_for_tree): Declare.
 	(do_sd_constraint): Handle a dereference of ESCAPED and CALLUSED
 	properly to compute the reachability set if we do field-sensitive PTA.
 	* invoke.texi (max-fields-for-field-sensitive): Document default.
 	* opts.c (decode_options): Set max-fields-for-field-sensitive to
 	100 for optimize >= 2.

 	* gcc.dg/tree-ssa/pta-callused.c: New testcase.

Index: trunk/gcc/tree-ssa-structalias.c
===================================================================
*** trunk.orig/gcc/tree-ssa-structalias.c	2008-07-02 13:24:11.000000000 +0200
--- trunk/gcc/tree-ssa-structalias.c	2008-07-02 13:32:41.000000000 +0200
*************** struct variable_info
*** 262,267 ****
--- 262,268 ----
   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;
*************** do_sd_constraint (constraint_graph_t gra
*** 1406,1411 ****
--- 1407,1453 ----
         goto done;
       }

+   /* For x = *ESCAPED and x = *CALLUSED we want to compute the
+      reachability set of the rhs var.  As a pointer to a sub-field
+      of a variable can also reach all other fields of the variable
+      we simply have to expand the solution to contain all sub-fields
+      if one sub-field is contained.  */
+   if (c->rhs.var == escaped_id
+       || c->rhs.var == callused_id)
+     {
+       bitmap vars = NULL;
+       /* In a first pass record all variables we need to add all
+          sub-fields off.  This avoids quadratic behavior.  */
+       EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
+ 	{
+ 	  varinfo_t v = lookup_vi_for_tree (get_varinfo (j)->decl);
+ 	  if (v->next != NULL)
+ 	    {
+ 	      if (vars == NULL)
+ 		vars = BITMAP_ALLOC (NULL);
+ 	      bitmap_set_bit (vars, v->id);
+ 	    }
+ 	}
+       /* In the second pass now do the addition to the solution and
+          to speed up solving add it to the delta as well.  */
+       if (vars != NULL)
+ 	{
+ 	  EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
+ 	    {
+ 	      varinfo_t v = get_varinfo (j);
+ 	      for (; v != NULL; v = v->next)
+ 		{
+ 		  if (bitmap_set_bit (sol, v->id))
+ 		    {
+ 		      flag = true;
+ 		      bitmap_set_bit (delta, v->id);
+ 		    }
+ 		}
+ 	    }
+ 	  BITMAP_FREE (vars);
+ 	}
+     }
+
     /* 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)
Index: trunk/gcc/doc/invoke.texi
===================================================================
*** trunk.orig/gcc/doc/invoke.texi	2008-07-02 13:24:20.000000000 +0200
--- trunk/gcc/doc/invoke.texi	2008-07-02 13:25:40.000000000 +0200
*************** duplicated when threading jumps.
*** 7323,7329 ****

   @item max-fields-for-field-sensitive
   Maximum number of fields in a structure we will treat in
! a field sensitive manner during pointer analysis.

   @item prefetch-latency
   Estimate on average number of instructions that are executed before
--- 7323,7330 ----

   @item max-fields-for-field-sensitive
   Maximum number of fields in a structure we will treat in
! a field sensitive manner during pointer analysis.  The default is zero
! for -O0, and -O1 and 100 for -Os, -O2, and -O3.

   @item prefetch-latency
   Estimate on average number of instructions that are executed before
Index: trunk/gcc/opts.c
===================================================================
*** trunk.orig/gcc/opts.c	2008-07-02 13:24:11.000000000 +0200
--- trunk/gcc/opts.c	2008-07-02 13:25:40.000000000 +0200
*************** decode_options (unsigned int argc, const
*** 903,908 ****
--- 903,911 ----

         /* Allow more virtual operators to increase alias precision.  */
         set_param_value ("max-aliased-vops", 500);
+ 
+       /* Track fields in field-sensitive alias analysis.  */
+       set_param_value ("max-fields-for-field-sensitive", 100);
       }

     if (optimize >= 3)
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/pta-callused.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/pta-callused.c	2008-07-02 13:25:40.000000000 +0200
***************
*** 0 ****
--- 1,27 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 --param max-fields-for-field-sensitive=2 -fdump-tree-alias" } */
+ 
+ struct Foo {
+   int *p, *q;
+ };
+ 
+ int foo (int ***x) __attribute__((pure));
+ 
+ int bar (int b)
+ {
+   int i;
+   struct Foo f;
+   int *p, **q;
+   p = &i;
+   f.p = &i;
+   f.q = f.p;
+   if (b)
+     q = &f.p;
+   else
+     q = &f.q;
+   return foo (&q);
+ }
+ 
+ /* { dg-final { scan-tree-dump "CALLUSED = { f f.q i q }" "alias" } } */
+ /* { dg-final { cleanup-tree-dump "alias" } } */
+



More information about the Gcc-patches mailing list