[PR42631] merge uninitialized refs into a single web

[Alexandre Oliva <aoliva at redhat dot com>]

Web doesn't combine references to uninitialized registers into a single
web, introducing a new pseudo for each such reference.  This can be
wasteful (imagine multiple such references, each getting its own
register or stack slot!), and it also causes -fcompare-debug failures,
because uninitialized references may show up in debug insns, getting
registers out of sync, possibly causing codegen differences.

The reason web doesn't combine references is that DF doesn't make them
part of the same UD chain.  This could be fixed in DF, introducing
artificial DEFs for registers used uninitialized, but since we're
talking about undefined behavior here, it's probably better to limit the
cost of dealing with this issue, taking care of it on an as-needed
basis.

This patch fixes web.c so as to combine chain-less webs, avoiding the
waste and the -fcompare-debug failure.

Ok to install if it regstraps?

for  gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR debug/42631
	* df.h (unionfind_root, unionfind_union, union_defs): Removed.
	(struct web_entry): Moved...
	* web.c: ... here.
	(unionfind_root, unionfind_union): Turned static.
	(union_defs): Likewise.  Add used argument, to combine uses of
	uninitialized regs.
	(entry_register): Adjust type and tests of used argument.
	(web_main): Widen used for new use.  Pass it to union_defs.
	
for  gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR debug/42631
	* gcc.dg/pr42631.c: New.
	
Index: gcc/df.h
===================================================================
--- gcc/df.h.orig	2010-01-08 06:16:47.000000000 -0200
+++ gcc/df.h	2010-01-08 06:21:42.000000000 -0200
@@ -1100,23 +1100,4 @@ df_get_artificial_uses (unsigned int bb_
   return df_scan_get_bb_info (bb_index)->artificial_uses;
 }
 
-
-/* web */
-
-/* This entry is allocated for each reference in the insn stream.  */
-struct web_entry
-{
-  /* Pointer to the parent in the union/find tree.  */
-  struct web_entry *pred;
-  /* Newly assigned register to the entry.  Set only for roots.  */
-  rtx reg;
-  void* extra_info;
-};
-
-extern struct web_entry *unionfind_root (struct web_entry *);
-extern bool unionfind_union (struct web_entry *, struct web_entry *);
-extern void union_defs (df_ref,
-                        struct web_entry *, struct web_entry *,
-			bool (*fun) (struct web_entry *, struct web_entry *));
-
 #endif /* GCC_DF_H */
Index: gcc/web.c
===================================================================
--- gcc/web.c.orig	2010-01-08 05:43:11.000000000 -0200
+++ gcc/web.c	2010-01-08 06:50:47.000000000 -0200
@@ -59,13 +59,21 @@ along with GCC; see the file COPYING3.  
 #include "timevar.h"
 #include "tree-pass.h"
 
+/* web */
 
-static rtx entry_register (struct web_entry *, df_ref, char *);
-static void replace_ref (df_ref, rtx);
+/* This entry is allocated for each reference in the insn stream.  */
+struct web_entry
+{
+  /* Pointer to the parent in the union/find tree.  */
+  struct web_entry *pred;
+  /* Newly assigned register to the entry.  Set only for roots.  */
+  rtx reg;
+  void* extra_info;
+};
 
 /* Find the root of unionfind tree (the representative of set).  */
 
-struct web_entry *
+static struct web_entry *
 unionfind_root (struct web_entry *element)
 {
   struct web_entry *element1 = element, *element2;
@@ -85,7 +93,7 @@ unionfind_root (struct web_entry *elemen
    Return true if FIRST and SECOND points to the same web entry structure and
    nothing is done.  Otherwise, return false.  */
 
-bool
+static bool
 unionfind_union (struct web_entry *first, struct web_entry *second)
 {
   first = unionfind_root (first);
@@ -98,11 +106,16 @@ unionfind_union (struct web_entry *first
 
 /* For each use, all possible defs reaching it must come in the same
    register, union them.
-   FUN is the function that does the union.  */
+   FUN is the function that does the union.
 
-void
+   In USED, we keep the DF_REF_ID of the first uninitialized uses of a
+   register, so that all uninitialized uses of the register can be
+   combined into a single web.  We actually offset it by 2, because
+   the values 0 and 1 are reserved for use by entry_register.  */
+
+static void
 union_defs (df_ref use, struct web_entry *def_entry,
- 	    struct web_entry *use_entry,
+	    unsigned int *used, struct web_entry *use_entry,
  	    bool (*fun) (struct web_entry *, struct web_entry *))
 {
   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
@@ -169,6 +182,22 @@ union_defs (df_ref use, struct web_entry
 	    def_link++;
 	  }
     }
+
+  /* UD chains of uninitialized REGs are empty.  Keeping all uses of
+     the same uninitialized REG in a single web is not necessary for
+     correctness, since the uses are undefined, but it's wasteful to
+     allocate one register or slot for each reference.  Furthermore,
+     creating new pseudos for uninitialized references in debug insns
+     (see PR 42631) causes -fcompare-debug failures.  */
+  if (!link)
+    {
+      int regno = REGNO (DF_REF_REAL_REG (use));
+      if (used[regno])
+	(*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
+      else
+	used[regno] = DF_REF_ID (use) + 2;
+    }
+
   while (link)
     {
       (*fun) (use_entry + DF_REF_ID (use),
@@ -201,7 +230,7 @@ union_defs (df_ref use, struct web_entry
 /* Find the corresponding register for the given entry.  */
 
 static rtx
-entry_register (struct web_entry *entry, df_ref ref, char *used)
+entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
 {
   struct web_entry *root;
   rtx reg, newreg;
@@ -214,17 +243,14 @@ entry_register (struct web_entry *entry,
   /* We are seeing this web for the first time, do the assignment.  */
   reg = DF_REF_REAL_REG (ref);
 
-  /* In case the original register is already assigned, generate new one.  */
-  if (!used[REGNO (reg)])
+  /* In case the original register is already assigned, generate new
+     one.  Since we use USED to merge uninitialized refs into a single
+     web, we might found an element to be nonzero without our having
+     used it.  Test for 1, because union_defs saves it for our use,
+     and there won't be any use for the other values when we get to
+     this point.  */
+  if (used[REGNO (reg)] != 1)
     newreg = reg, used[REGNO (reg)] = 1;
-  else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
-    {
-      newreg = reg;
-      if (dump_file)
-	fprintf (dump_file,
-		 "New web forced to keep reg=%i (user variable)\n",
-		 REGNO (reg));
-    }
   else
     {
       newreg = gen_reg_rtx (GET_MODE (reg));
@@ -273,7 +299,7 @@ web_main (void)
   struct web_entry *def_entry;
   struct web_entry *use_entry;
   unsigned int max = max_reg_num ();
-  char *used;
+  unsigned int *used;
   basic_block bb;
   unsigned int uses_num = 0;
   rtx insn;
@@ -308,7 +334,7 @@ web_main (void)
 
   /* Record the number of uses and defs at the beginning of the optimization.  */
   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
-  used = XCNEWVEC (char, max);
+  used = XCNEWVEC (unsigned, max);
   use_entry = XCNEWVEC (struct web_entry, uses_num);
 
   /* Produce the web.  */
@@ -323,13 +349,13 @@ web_main (void)
 	    {
 	      df_ref use = *use_rec;
 	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
-		union_defs (use, def_entry, use_entry, unionfind_union);
+		union_defs (use, def_entry, used, use_entry, unionfind_union);
 	    }
 	  for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 	    {
 	      df_ref use = *use_rec;
 	      if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
-		union_defs (use, def_entry, use_entry, unionfind_union);
+		union_defs (use, def_entry, used, use_entry, unionfind_union);
 	    }
 	}
     }
Index: gcc/testsuite/gcc.dg/pr42631.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/testsuite/gcc.dg/pr42631.c	2010-01-08 06:43:18.000000000 -0200
@@ -0,0 +1,23 @@
+/* The function below expands to a loop whose latch block starts with
+   a PHI node and the corresponding debug stmt.  In RTL, there are no
+   PHI nodes, but the debug insn that references the incoming k
+   remains, even though one of the incoming edges has it
+   uninitialized.  After unrolling, however, the debug insn becomes
+   unconditional, and this exposed a problem in the webizer.  Because
+   DF doesn't combine the uses of an uninitialized pseudo into a
+   single UD chain, we created a separate web for each use.
+   Allocating separate registers or stack slots for each uninitialized
+   use is wasteful, but the problem became more apparent in
+   -fcompare-debug tests: register numbers went out of sync, and could
+   have caused codegen differences depending on whether or not the
+   debug insns were present.  The fix was to arrange for web to
+   combine uninitialized uses into a single web.  */
+
+/* { dg-do compile } */
+/* { dg-options "-g -O1 -funroll-loops -fcompare-debug" } */
+
+void foo()
+{
+  unsigned k;
+  while (--k > 0);
+}

-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer