[tree-ssa][PATCH]: Alias stats

[Daniel Berlin <dberlin at dberlin dot org>]

Now that i'm done with finals (I have a paper due sunday that i'm 
basically done with), i'm working on aliasing some more.

First up is to actually generate alias statistics.

I bootstrapped this patch on both i686-pc-linux-gnu, and 
powerpc-darwin, and regtested it on i686-pc-linux-gnu.

Diego, if you've got a better named than "ptr tbaa", i'd love to hear 
it. I just gave it a different stat because it's not really a direct 
tbaa query (not the same cost as calling alias_sets_conflict_p)

Okay to commit?

The total stats (over a gcc bootstrap) are still being crunched (IE i'm 
working out percentages).

The high mark in terms of alias queries looks like this:

Total alias queries:    4773
Total alias mayalias results:   481
Total alias noalias results:    4292
Total simple queries:   4773
Total simple resolved:  39
Total pointer TBAA queries:     1300
Total pointer TBAA resolved:    28
Total TBAA queries:     4706
Total TBAA resolved:    2327
Total PTA queries:      2379
Total PTA resolved:     1898


The numbers for pointer TBAA (or whatever we call it) are weird because 
unlike the other queries, it's not called all the time.

But in terms of percentages, the queries vs resolved of each alias info 
provider here are average for the bootstrap of gcc (IE pta resolves 
about 80% of queries thrown at it, tbaa, about 50% thrown at it).

I'll be working the PTA results into other info soon (like using PTA to 
determine if a variable accesses global memory, or is actually call 
clobbered), which hopefully should increase our spec scores some.


2003-12-19  Daniel Berlin  <dberlin@dberlin.org>

	* tree-dfa.c (alias_stats_d): New structure.
	(alias_stats): New variable.
	(find_referenced_vars): Zero out alias_stats.
	(dump_alias_stats): New function.
	(compute_alias_sets): Call it if TDF_STATS is set.
	(may_alias_p): Collect the various statistics.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.204
diff -u -3 -p -r1.1.4.204 tree-dfa.c
--- tree-dfa.c	18 Dec 2003 19:14:26 -0000	1.1.4.204
+++ tree-dfa.c	19 Dec 2003 04:49:22 -0000
@@ -61,6 +61,21 @@ struct dfa_stats_d
   long num_vuses;
 };

+struct alias_stats_d
+{
+  unsigned int alias_queries;
+  unsigned int alias_mayalias;
+  unsigned int alias_noalias;
+  unsigned int simple_queries;
+  unsigned int simple_resolved;
+  unsigned int ptr_tbaa_queries;
+  unsigned int ptr_tbaa_resolved;
+  unsigned int tbaa_queries;
+  unsigned int tbaa_resolved;
+  unsigned int pta_queries;
+  unsigned int pta_resolved;
+};
+
 /* Tuple to map a variable to its alias set.  Used to cache the 
results of
    calls to get_alias_set().  */
 struct GTY(()) alias_map_d
@@ -108,11 +123,13 @@ static int dump_flags;
 /* Data and functions shared with tree-ssa.c.  */
 struct dfa_stats_d dfa_stats;

+struct alias_stats_d alias_stats;

 /* Local functions.  */
 static void collect_dfa_stats (struct dfa_stats_d *);
 static tree collect_dfa_stats_r (tree *, int *, void *);
 static void compute_alias_sets (void);
+static void dump_alias_stats (FILE *);
 static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT);
 static bool may_access_global_mem_p (tree);
 static void add_immediate_use (tree, tree);
@@ -792,7 +809,7 @@ find_referenced_vars (tree fndecl)

   VARRAY_GENERIC_PTR_INIT (addressable_vars, 20, "addressable_vars");
   VARRAY_GENERIC_PTR_INIT (pointers, 20, "pointers");
-
+  memset (&alias_stats, 0, sizeof (alias_stats));
   if (flag_tree_points_to != PTA_NONE)
     {
       timevar_push (TV_TREE_PTA);
@@ -1031,6 +1048,9 @@ compute_alias_sets (void)
   dump_file = dump_begin (TDI_alias, &dump_flags);
   if (dump_file)
     {
+      if (dump_flags & TDF_STATS)
+	dump_alias_stats (dump_file);
+
       dump_alias_info (dump_file);
       dump_referenced_vars (dump_file);
       dump_function_to_file (current_function_decl, dump_file, 
dump_flags);
@@ -1056,10 +1076,15 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem
   var_ann_t v_ann, m_ann;

   mem = var_ann (ptr)->mem_tag;
-
+  alias_stats.alias_queries++;
+  alias_stats.simple_queries++;
   /* By convention, a variable cannot alias itself.  */
   if (mem == var)
-    return false;
+    {
+      alias_stats.alias_noalias++;
+      alias_stats.simple_resolved++;
+      return false;
+    }

   v_ann = var_ann (var);
   m_ann = var_ann (mem);
@@ -1077,11 +1102,15 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem
       && var_alias_set != 0)
     {
       HOST_WIDE_INT ptr_alias_set = get_alias_set (ptr);
+      alias_stats.ptr_tbaa_queries++;
       if (ptr_alias_set == var_alias_set)
-	return false;
+	{
+	  alias_stats.alias_noalias++;
+	  alias_stats.ptr_tbaa_resolved++;
+	  return false;
+	}
     }
-
-
+  alias_stats.tbaa_queries++;
   /* If the alias sets don't conflict then MEM cannot alias VAR.  */
   if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
     {
@@ -1110,24 +1139,43 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem

 	  /* If no pointer-to VAR exists, then MEM can't alias VAR.  */
 	  if (ptr_to_var == NULL_TREE)
-	    return false;
+	    {
+	      alias_stats.alias_noalias++;
+	      alias_stats.tbaa_resolved++;
+	      return false;
+	    }

 	  /* If MEM doesn't alias a pointer to VAR and VAR doesn't alias
 	     PTR, then PTR can't alias VAR.  */
 	  if (!alias_sets_conflict_p (mem_alias_set, get_alias_set 
(ptr_to_var))
 	      && !alias_sets_conflict_p (var_alias_set, get_alias_set (ptr)))
-	    return false;
+	    {
+	      alias_stats.alias_noalias++;
+	      alias_stats.tbaa_resolved++;
+	      return false;
+	    }
 	}
       else
-	return false;
+	{
+	  alias_stats.alias_noalias++;
+	  alias_stats.tbaa_resolved++;
+	  return false;
+	}
     }

+  if (flag_tree_points_to != PTA_NONE)
+      alias_stats.pta_queries++;
+
   /* If -ftree-points-to is given, check if PTR may point to VAR.  */
   if (flag_tree_points_to != PTA_NONE
       && !ptr_may_alias_var (ptr, var))
-    return false;
-
+    {
+      alias_stats.alias_noalias++;
+      alias_stats.pta_resolved++;
+      return false;
+    }

+  alias_stats.alias_mayalias++;
   return true;
 }

@@ -1167,6 +1215,35 @@ add_may_alias (tree var, tree alias)
 }


+static void
+dump_alias_stats (FILE *file)
+{
+  const char *funcname
+    = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
+  fprintf (file, "\nAlias statistics for %s\n\n", funcname);
+  fprintf (file, "Total alias queries:\t%u\n", 
alias_stats.alias_queries);
+  fprintf (file, "Total alias mayalias results:\t%u\n",
+	   alias_stats.alias_mayalias);
+  fprintf (file, "Total alias noalias results:\t%u\n",
+	   alias_stats.alias_noalias);
+  fprintf (file, "Total simple queries:\t%u\n",
+	   alias_stats.simple_queries);
+  fprintf (file, "Total simple resolved:\t%u\n",
+	   alias_stats.simple_resolved);
+  fprintf (file, "Total pointer TBAA queries:\t%u\n",
+	   alias_stats.ptr_tbaa_queries);
+  fprintf (file, "Total pointer TBAA resolved:\t%u\n",
+	   alias_stats.ptr_tbaa_resolved);
+  fprintf (file, "Total TBAA queries:\t%u\n",
+	   alias_stats.tbaa_queries);
+  fprintf (file, "Total TBAA resolved:\t%u\n",
+	   alias_stats.tbaa_resolved);
+  fprintf (file, "Total PTA queries:\t%u\n",
+	   alias_stats.pta_queries);
+  fprintf (file, "Total PTA resolved:\t%u\n",
+	   alias_stats.pta_resolved);
+}
+
 /* Dump alias information on FILE.  */

 void