Fix latent aliasing bug

Fix latent aliasing bug

[Diego Novillo]

[-- Attachment #1: Type: text/plain, Size: 1440 bytes --]

This bug was found trying to build glibc 2.3.5 with a recent trunk. The
problem is the following:

- When we compute aliasing information, the memory tags created for
pointers are marked for SSA renaming.

- If a pointer P had a previous tag and it receives a new tag, both the
new and old tag are marked for SSA renaming.

- However, when an SSA pointer disappears from the IL because of
optimizations, its associated name tag is not always marked for SSA
renaming.  In general this is not a problem as name tags are frequently
shared and one way or another the tags end up in the set of symbols to
rename.

In this particular case, we were removing the very last pointer that had
a particular tag T as its name tag.  Therefore, T was never marked for
renaming.  Again, this may not be a problem, if all we have around are
PHI nodes, the next pass that cleans them up will cause the stale name
tag to disappear.

But in this test case the name tag was also call-clobbered, and before
the alias pass we had a single definition site for it in a call site.
This definition disappeared but since the tag had not been marked for
renaming, there was a single reference to it in an argument to a PHI node.

This was causing the SSA verifier to fail.  The fix is to recognize
these stale names and mark them early so that they can be cleaned up
without causing the SSA verifier to fail.

Bootstrapped and tested on x86_64.  Committed to mainline.

[-- Attachment #2: 20070815-fix-stale-NMT.diff --]
[-- Type: text/x-patch, Size: 9686 bytes --]

2007-08-15  Diego Novillo  <dnovillo@google.com>

	* tree-ssa-alias.c (compute_memory_partitions): Use
	alias_bitmap_obstack to allocate bitmaps.
	(reset_alias_info): Factor out of init_alias_info.
	Mark all name tags not associated to an SSA name for renaming.
	(init_alias_info): Call it.
	(create_name_tags): Tidy.  Add comments.
	(dump_points_to_info_for): Do not call get_mem_sym_stats_for.

testsuite/ChangeLog:

	gcc.dg/tree-ssa/20070815.c: New test.

Index: testsuite/gcc.dg/tree-ssa/20070815.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/20070815.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/20070815.c	(revision 0)
@@ -0,0 +1,60 @@
+/* { dg-do compile } */
+/* { dg-options "-O -w" } */
+
+/* This code snippet from glibc 2.3.5 was causing an ICE during
+   optimization because we were failing to update the SSA form for
+   stale name tags.  These are tags that are associated with SSA pointers
+   that have been removed from the IL.  This was causing the SSA
+   verifier to fail before we had a chance to run the cleanup pass that
+   finally removes all the remaining PHI nodes for the stale name tag.  */
+struct _IO_wide_data
+{
+};
+struct _IO_FILE {
+};
+typedef struct _IO_FILE _IO_FILE;
+struct _IO_jump_t
+{
+};
+struct _IO_FILE_plus
+{
+  _IO_FILE file;
+};
+extern const struct _IO_jump_t _IO_file_jumps_maybe_mmap ;
+extern const struct _IO_jump_t _IO_wfile_jumps;
+extern const struct _IO_jump_t _IO_wfile_jumps_maybe_mmap ;
+
+_IO_new_fdopen (fd, mode)
+     const char *mode;
+{
+  int read_write;
+  int posix_mode = 0;
+  struct locked_FILE
+  {
+    struct _IO_FILE_plus fp;
+    struct _IO_wide_data wd;
+  } *new_f;
+  int fd_flags;
+  int use_mmap = 0;
+    {
+  }
+    {
+      switch (*++mode)
+ {
+ case '\0':
+   use_mmap = 1;
+ }
+    }
+  if (((fd_flags & 0003) == 00 && !(read_write & 8))
+      || ((fd_flags & 0003) == 01 && !(read_write & 4)))
+    {
+    }
+  if ((posix_mode & 02000) && !(fd_flags & 02000))
+    return ((void *)0);
+  _IO_no_init (&new_f->fp.file, 0, 0, &new_f->wd,
+        (use_mmap && (read_write & 8))
+        ? &_IO_wfile_jumps_maybe_mmap :
+        &_IO_wfile_jumps);
+    (use_mmap && (read_write & 8)) ? &_IO_file_jumps_maybe_mmap :
+  _IO_file_init (&new_f->fp);
+}
Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 127515)
+++ tree-ssa-alias.c	(working copy)
@@ -1497,7 +1497,7 @@ compute_memory_partitions (void)
      virtual operands.  However, by reducing the size of the alias
      sets to be scanned, the work needed inside the operand scanner is
      significantly reduced.  */
-  new_aliases = BITMAP_ALLOC (NULL);
+  new_aliases = BITMAP_ALLOC (&alias_bitmap_obstack);
 
   for (i = 0; VEC_iterate (tree, tags, i, tag); i++)
     {
@@ -1891,6 +1891,103 @@ init_mem_ref_stats (void)
 }
 
 
+/* Helper for init_alias_info.  Reset existing aliasing information.  */
+
+static void
+reset_alias_info (void)
+{
+  referenced_var_iterator rvi;
+  tree var;
+  unsigned i;
+  bitmap active_nmts, all_nmts;
+
+  /* Clear the set of addressable variables.  We do not need to clear
+     the TREE_ADDRESSABLE bit on every symbol because we are going to
+     re-compute addressability here.  */
+  bitmap_clear (gimple_addressable_vars (cfun));
+
+  active_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
+  all_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
+
+  /* Clear flow-insensitive alias information from each symbol.  */
+  FOR_EACH_REFERENCED_VAR (var, rvi)
+    {
+      if (is_gimple_reg (var))
+	continue;
+
+      if (MTAG_P (var))
+	MTAG_ALIASES (var) = NULL;
+
+      /* Memory partition information will be computed from scratch.  */
+      if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
+	MPT_SYMBOLS (var) = NULL;
+
+      /* Collect all the name tags to determine if we have any
+	 orphaned that need to be removed from the IL.  A name tag
+	 will be orphaned if it is not associated with any active SSA
+	 name.  */
+      if (TREE_CODE (var) == NAME_MEMORY_TAG)
+	bitmap_set_bit (all_nmts, DECL_UID (var));
+
+      /* Since we are about to re-discover call-clobbered
+	 variables, clear the call-clobbered flag.  Variables that
+	 are intrinsically call-clobbered (globals, local statics,
+	 etc) will not be marked by the aliasing code, so we can't
+	 remove them from CALL_CLOBBERED_VARS.  
+
+	 NB: STRUCT_FIELDS are still call clobbered if they are for a
+	 global variable, so we *don't* clear their call clobberedness
+	 just because they are tags, though we will clear it if they
+	 aren't for global variables.  */
+      if (TREE_CODE (var) == NAME_MEMORY_TAG
+	  || TREE_CODE (var) == SYMBOL_MEMORY_TAG
+	  || TREE_CODE (var) == MEMORY_PARTITION_TAG
+	  || !is_global_var (var))
+	clear_call_clobbered (var);
+    }
+
+  /* Clear flow-sensitive points-to information from each SSA name.  */
+  for (i = 1; i < num_ssa_names; i++)
+    {
+      tree name = ssa_name (i);
+
+      if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
+	continue;
+
+      if (SSA_NAME_PTR_INFO (name))
+	{
+	  struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
+
+	  /* Clear all the flags but keep the name tag to
+	     avoid creating new temporaries unnecessarily.  If
+	     this pointer is found to point to a subset or
+	     superset of its former points-to set, then a new
+	     tag will need to be created in create_name_tags.  */
+	  pi->pt_anything = 0;
+	  pi->pt_null = 0;
+	  pi->value_escapes_p = 0;
+	  pi->is_dereferenced = 0;
+	  if (pi->pt_vars)
+	    bitmap_clear (pi->pt_vars);
+
+	  /* Add NAME's name tag to the set of active tags.  */
+	  if (pi->name_mem_tag)
+	    bitmap_set_bit (active_nmts, DECL_UID (pi->name_mem_tag));
+	}
+    }
+
+  /* Name memory tags that are no longer associated with an SSA name
+     are considered stale and should be removed from the IL.  All the
+     name tags that are in the set ALL_NMTS but not in ACTIVE_NMTS are
+     considered stale and marked for renaming.  */
+  bitmap_and_compl_into (all_nmts, active_nmts);
+  mark_set_for_renaming (all_nmts);
+
+  BITMAP_FREE (all_nmts);
+  BITMAP_FREE (active_nmts);
+}
+
+
 /* Initialize the data structures used for alias analysis.  */
 
 static struct alias_info *
@@ -1913,70 +2010,7 @@ init_alias_info (void)
 
   /* If aliases have been computed before, clear existing information.  */
   if (gimple_aliases_computed_p (cfun))
-    {
-      unsigned i;
-      
-      /* Similarly, clear the set of addressable variables.  In this
-	 case, we can just clear the set because addressability is
-	 only computed here.  */
-      bitmap_clear (gimple_addressable_vars (cfun));
-
-      /* Clear flow-insensitive alias information from each symbol.  */
-      FOR_EACH_REFERENCED_VAR (var, rvi)
-	{
-	  if (is_gimple_reg (var))
-	    continue;
-
-	  if (MTAG_P (var))
-	    MTAG_ALIASES (var) = NULL;
-
-	  /* Memory partition information will be computed from scratch.  */
-	  if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
-	    MPT_SYMBOLS (var) = NULL;
-
-	  /* Since we are about to re-discover call-clobbered
-	     variables, clear the call-clobbered flag.  Variables that
-	     are intrinsically call-clobbered (globals, local statics,
-	     etc) will not be marked by the aliasing code, so we can't
-	     remove them from CALL_CLOBBERED_VARS.  
-
-	     NB: STRUCT_FIELDS are still call clobbered if they are
-	     for a global variable, so we *don't* clear their call
-	     clobberedness just because they are tags, though we will
-	     clear it if they aren't for global variables.  */
-	  if (TREE_CODE (var) == NAME_MEMORY_TAG
-	      || TREE_CODE (var) == SYMBOL_MEMORY_TAG
-	      || TREE_CODE (var) == MEMORY_PARTITION_TAG
-	      || !is_global_var (var))
-	    clear_call_clobbered (var);
-	}
-
-      /* Clear flow-sensitive points-to information from each SSA name.  */
-      for (i = 1; i < num_ssa_names; i++)
-	{
-	  tree name = ssa_name (i);
-
-	  if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
-	    continue;
-
-	  if (SSA_NAME_PTR_INFO (name))
-	    {
-	      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
-
-	      /* Clear all the flags but keep the name tag to
-		 avoid creating new temporaries unnecessarily.  If
-		 this pointer is found to point to a subset or
-		 superset of its former points-to set, then a new
-		 tag will need to be created in create_name_tags.  */
-	      pi->pt_anything = 0;
-	      pi->pt_null = 0;
-	      pi->value_escapes_p = 0;
-	      pi->is_dereferenced = 0;
-	      if (pi->pt_vars)
-		bitmap_clear (pi->pt_vars);
-	    }
-	}
-    }
+    reset_alias_info ();
   else
     {
       /* If this is the first time we compute aliasing information,
@@ -2123,6 +2157,7 @@ create_name_tags (void)
       else
 	{
 	  *slot = pi;
+
 	  /* If we didn't find a pointer with the same points-to set
 	     as PTR, create a new name tag if needed.  */
 	  if (pi->name_mem_tag == NULL_TREE)
@@ -2135,7 +2170,8 @@ create_name_tags (void)
 	 renaming.  */
       if (old_name_tag && old_name_tag != pi->name_mem_tag)
 	mark_sym_for_renaming (old_name_tag);
-      
+
+      /* Inherit volatility from the pointed-to type.  */
       TREE_THIS_VOLATILE (pi->name_mem_tag)
 	|= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
       
@@ -3215,9 +3251,7 @@ dump_points_to_info_for (FILE *file, tre
 	}
 
       if (pi->is_dereferenced)
-	fprintf (file, ", is dereferenced (R=%ld, W=%ld)",
-		 get_mem_sym_stats_for (ptr)->num_direct_reads,
-		 get_mem_sym_stats_for (ptr)->num_direct_writes);
+	fprintf (file, ", is dereferenced");
 
       if (pi->value_escapes_p)
 	fprintf (file, ", its value escapes");