This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH]: Add new heuristic for structure aliasing, don'tcreate duplicate SFT's


On Tue, 2005-03-29 at 19:09 -0500, Daniel Berlin wrote:
> 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);
> 


Dale Johannesen pointed out this might not be safe when the fields are
different types, and after significant thinking, i'm pretty sure he's
right.

Thus, i've changed the patch to only eliminate SFT's when the field type
is the same as well.

The new patch is attached.  
It's currently being bootstrapped on i686-pc-linux-gnu and
powerpc-linux.
Okay for mainline if it succeeds?

--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,18 @@ 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;
+      tree lastfotype = NULL_TREE;
 
       /* 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,36 @@ 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
+		  && currfotype == lastfotype))
 	    {
 	      free (fo);
 	      continue;
 	    }
-
+	  sv = ggc_alloc (sizeof (struct subvar));
 	  sv->offset = fo->offset;
 	  sv->size = fosize;
 	  sv->next = *subvars;
@@ -2891,2 +2968,2 @@ create_overlap_variables_for (tree var)
 	  ann->type_mem_tag = NULL;  	
 	  add_referenced_tmp_var (sv->var);

+	  lastfotype = currfotype; 	    
+	  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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]