[PATCH]: Add new heuristic for structure aliasing, don't createduplicate SFT's

[Daniel Berlin <dberlin at dberlin dot org>]

This patch does two things:

1. Avoids creating duplicate subvars for fields that have the same
offset, size (IE what often happens in unions) since we can't tell the
difference between them anyway.

IE previously, given

union
{
	int a;
	int b;
};

we would create two subvars, when now, we will create 1, since both
fields are at the same offset and have the same size.

Given something like

union
{
	int a;
	short b;
};

we will still create 2 subvars, as before  (assuming sizeof(short) !=
sizeof(int))

2.   Adds a new heuristic to attempt to avoid useless subvar creation.

libjava has a penchant for doing thinks like this:

  D.7318 = _Jv_AllocObject (&_ZN4java3net15SocketException6class
$ED.7310);

Where this is a variable with 38 fields.
Nowhere does the function explicitly set any field in this variable, or
anything we can easily optimize.

However, currently we'll still create subvars for it, because you've
"used" it.

The new heuristic differentiates between explicit uses and defs of
portions of structures, and implicit uses and defs (like taking the
address of the whole thing, or conservative estimates of what part of
the structure you are touching).

For variables with explicit uses, or < SALIAS_MAX_IMPLICIT_FIELDS, we'll
still create subvars anyway.
For variables *without* any explicit use, and >
SALIAS_MAX_IMPLICIT_FIELDS, we won't.

I've currently chosen the number 5 out of thin air as the default for
SALIAS_MAX_IMPLICIT_FIELDS.

In reality, there are a small number of cases we will miss creating
SFT's for under this heuristic, which look like:


int foo()
{
	largestruct bob;
	largestruct *foo;
	foo = &bob;
	foo->a = 5;
}


If we created structure vars after propagation, we would create subvars
for the def'd portion of bob and be able to optimize this case better.
We'd also create subvars it if you wrote it like so:

int foo()
{
	largestruct bob;
	largestruct *foo;
	bob.a = 5;
	foo = &bob;
}


I'll play with doing that after i submit the struct aliasing part 2
work.
I don't think not creating subvars when we need to should be the answer
for things taking more time than they should (which is currently the
case for some optimziations), even if we do have 100 virtual ops on a
statement, but there are definitely cases where we create subvars and
can prove we won't get anything out of it, and tihs heuristic should
catch most of those with only a little lossage on the other side.

Bootstrapped and regtested on i686-pc-linux-gnu and powerpc-linux-gnu
with the previously posted verification patch on as well.
No regressions.

Okay for mainline?
--Dan


2005-03-29  Daniel Berlin  <dberlin@dberlin.org>

	* params.def (PARAM_SALIAS_MAX_IMPLICIT_FIELDS): New
	* params.h (SALIAS_MAX_IMPLICIT_FIELDS): New
	* doc/invoke.texi: Documnet salias-max-implicit-fields.
	* tree-ssa-alias.c (struct used_part): Add implicit_uses and
	explicit_uses members.
	(get_or_create_used_part_for): Initialize new fields.
	(fieldoff_compare): New function.
	(create_overlap_variables_for): Count number of fields, use
	heuristic to determine whether to create subvars for vars with
	only implicit uses.
	Sort the field list by offset and avoid creating duplicate SFT's.
	
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.56
diff -u -p -r1.56 params.def
--- params.def	23 Mar 2005 19:09:57 -0000	1.56
+++ params.def	29 Mar 2005 23:44:28 -0000
@@ -35,6 +35,14 @@ Software Foundation, 59 Temple Place - S
 
    Be sure to add an entry to invoke.texi summarizing the parameter.  */
 
+/* The maximum number of fields in a variable with only implicit uses
+   for which structure aliasing will consider trying to track each
+   field.  The default is 5.  */
+DEFPARAM (PARAM_SALIAS_MAX_IMPLICIT_FIELDS,
+	  "salias-max-implicit-fields",
+	  "The maximum number of fields in an implicitly used variable that GCC will attempt to track separately",
+	  5, 0, 0)
+   
 /* The maximum structure size at which the scalar replacement of
    aggregates (SRA) pass will perform block copies.  The default
    value, 0, implies that GCC will select the most appropriate size
Index: params.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.h,v
retrieving revision 1.28
diff -u -p -r1.28 params.h
--- params.h	23 Jan 2005 15:05:31 -0000	1.28
+++ params.h	29 Mar 2005 23:44:28 -0000
@@ -89,6 +89,8 @@ typedef enum compiler_param
   (compiler_params[(int) ENUM].value)
 
 /* Macros for the various parameters.  */
+#define SALIAS_MAX_IMPLICIT_FIELDS \
+  PARAM_VALUE (PARAM_SALIAS_MAX_IMPLICIT_FIELDS)
 #define SRA_MAX_STRUCTURE_SIZE \
   PARAM_VALUE (PARAM_SRA_MAX_STRUCTURE_SIZE)
 #define SRA_FIELD_STRUCTURE_RATIO \
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.76
diff -u -p -r2.76 tree-ssa-alias.c
--- tree-ssa-alias.c	21 Mar 2005 19:26:59 -0000	2.76
+++ tree-ssa-alias.c	29 Mar 2005 23:44:29 -0000
@@ -2757,6 +2768,13 @@ typedef struct used_part
 {
   HOST_WIDE_INT minused;
   HOST_WIDE_INT maxused;
+  /* True if we have an explicit use/def of some portion of this variable,
+     even if it is all of it. i.e. a.b = 5 or temp = a.b.  */
+  bool explicit_uses;
+  /* True if we have an implicit use/def of some portion of this
+     variable.  Implicit uses occur when we can't tell what part we
+     are referencing, and have to make conservative assumptions.  */
+  bool implicit_uses;
 } *used_part_t;
 
 /* An array of used_part structures, indexed by variable uid.  */
@@ -2775,14 +2793,32 @@ get_or_create_used_part_for (size_t uid)
       up = xcalloc (1, sizeof (struct used_part));
       up->minused = INT_MAX;
       up->maxused = 0;
+      up->explicit_uses = false;
+      up->implicit_uses = false;
     }
   else
     up = used_portions[uid];
   return up;
 }
 
-	    
-  
+/* qsort comparison function for two fieldoff_t's PA and PB */
+
+static int 
+fieldoff_compare (const void *pa, const void *pb)
+{
+  const fieldoff_t foa = *(fieldoff_t *)pa;
+  const fieldoff_t fob = *(fieldoff_t *)pb;
+  HOST_WIDE_INT foasize, fobsize;
+  if (foa->offset != fob->offset)
+    return foa->offset - fob->offset;
+
+  foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
+  fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
+  if (foasize != fobsize)
+    return foasize - fobsize;
+  return 0;
+}
+
 /* Given an aggregate VAR, create the subvariables that represent its
    fields.  */
 
@@ -2796,13 +2832,17 @@ create_overlap_variables_for (tree var)
   if (used_portions[uid] == NULL)
     return;
 
+  up = used_portions[uid];
   push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0);
   if (VEC_length (fieldoff_t, fieldstack) != 0)
     {
       subvar_t *subvars;
       fieldoff_t fo;
       bool notokay = false;
+      int fieldcount = 0;
       int i;
+      HOST_WIDE_INT lastfooffset = -1;
+      HOST_WIDE_INT lastfosize = -1;
 
       /* Not all fields have DECL_SIZE set, and those that don't, we don't
 	 know their size, and thus, can't handle.
@@ -2823,7 +2863,34 @@ create_overlap_variables_for (tree var)
 	      notokay = true;
 	      break;
 	    }
+          fieldcount++;
 	}
+
+      /* The current heuristic we use is as follows:
+	 If the variable has no used portions in this function, no
+	 structure vars are created for it.
+	 Otherwise,
+         If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
+	 we always create structure vars for them.
+	 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
+	 some explicit uses, we create structure vars for them.
+	 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
+	 no explicit uses, we do not create structure vars for them.
+      */
+      
+      if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS
+	  && !up->explicit_uses)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Variable ");
+	      print_generic_expr (dump_file, var, 0);
+	      fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
+	    }
+	  notokay = true;
+	}
+      
+    
       /* Cleanup after ourselves if we can't create overlap variables.  */
       if (notokay)
 	{
@@ -2837,25 +2904,35 @@ create_overlap_variables_for (tree var)
 	}
       /* Otherwise, create the variables.  */
       subvars = lookup_subvars_for_var (var);
-      up = used_portions[uid];
       
+      qsort (VEC_address (fieldoff_t, fieldstack), 
+	     VEC_length (fieldoff_t, fieldstack), 
+	     sizeof (fieldoff_t),
+	     fieldoff_compare);
+
       while (VEC_length (fieldoff_t, fieldstack) != 0)
 	{
-	  subvar_t sv = ggc_alloc (sizeof (struct subvar));
+	  subvar_t sv;
 	  HOST_WIDE_INT fosize;
 	  var_ann_t ann;
 
 	  fo = VEC_pop (fieldoff_t, fieldstack);	  
 	  fosize = TREE_INT_CST_LOW (DECL_SIZE (fo->field));
 
-	  if ((fo->offset <= up->minused
-	       && fo->offset + fosize <= up->minused)
-	      || fo->offset >= up->maxused)
+	  /* If this field isn't in the used portion,
+	     or it has the exact same offset and size as the last
+	     field, skip it.  */
+
+	  if (((fo->offset <= up->minused
+		&& fo->offset + fosize <= up->minused)
+	       || fo->offset >= up->maxused)
+	      || (fo->offset == lastfooffset
+		  && fosize == lastfosize))
 	    {
 	      free (fo);
 	      continue;
 	    }
-
+	  sv = ggc_alloc (sizeof (struct subvar));
 	  sv->offset = fo->offset;
 	  sv->size = fosize;
 	  sv->next = *subvars;
@@ -2891,6 +2968,8 @@ create_overlap_variables_for (tree var)
 	  ann->type_mem_tag = NULL;  	
 	  add_referenced_tmp_var (sv->var);
 	    
+	  lastfooffset = fo->offset;
+	  lastfosize = fosize;
 	  *subvars = sv;
 	  free (fo);
 	}
@@ -2935,6 +3024,7 @@ find_used_portions (tree *tp, int *walk_
 	    if ((bitpos + bitsize >= up->maxused))
 	      up->maxused = bitpos + bitsize;	    
 
+	    up->explicit_uses = true;
 	    used_portions[uid] = up;
 
 	    *walk_subtrees = 0;
@@ -2954,6 +3044,8 @@ find_used_portions (tree *tp, int *walk_
 		up->minused = 0;
 		up->maxused = TREE_INT_CST_LOW (DECL_SIZE (ref));
 
+		up->implicit_uses = true;
+
 		used_portions[uid] = up;
 
 		*walk_subtrees = 0;
@@ -2977,6 +3069,7 @@ find_used_portions (tree *tp, int *walk_
  
 	    up->minused = 0;
 	    up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
+	    up->implicit_uses = true;
 
 	    used_portions[uid] = up;
 	    *walk_subtrees = 0;
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.594
diff -u -p -r1.594 invoke.texi
--- doc/invoke.texi	23 Mar 2005 19:10:01 -0000	1.594
+++ doc/invoke.texi	29 Mar 2005 23:44:35 -0000
@@ -5447,6 +5447,11 @@ In each case, the @var{value} is an inte
 @var{name} are given in the following table:
 
 @table @gcctabopt
+@item salias-max-implicit-fields
+The maximum number of fields in a variable with only implicit uses
+for which structure aliasing will consider trying to track each
+field.  The default is 5
+
 @item sra-max-structure-size
 The maximum structure size, in bytes, at which the scalar replacement
 of aggregates (SRA) optimization will perform block copies.  The