[df-scan.c] Optimise DF_REFs ordering in collection_rec, use HARD_REG_SETs instead of bitmaps

[Dimitrios Apostolou <jimis@gmx.net>]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 786 bytes --]

Hello list,

The attached patch does two things for df_get_call_refs():
* First it uses HARD_REG_SETs for defs_generated and 
regs_invalidated_by_call, instead of bitmaps. Replacing in total more 
than 400K calls (for my testcase) to bitmap_bit_p() with the much faster 
TEST_HARD_REG_BIT, reduces the total instruction count from about 13M to 
1.5M.
* Second it produces the REFs in REGNO order, which is important to keep 
the collection_rec sorted most times, and avoid expensive calls to 
qsort(). Thanks to Paolo Bonzini for idea and mentoring.

The second part makes a big difference if accompanied with another patch 
in df_insn_refs_collect(). I'll post a followup patch, that is 
unfortunately unstable for some of my tests, so I'd appreciate any 
comments.


Thanks,
Dimitris

[-- Attachment #2: Type: TEXT/plain, Size: 4342 bytes --]

=== modified file 'gcc/df-scan.c'
--- gcc/df-scan.c	2011-02-02 20:08:06 +0000
+++ gcc/df-scan.c	2011-07-08 01:28:55 +0000
@@ -3317,20 +3317,56 @@
                   int flags)
 {
   rtx note;
-  bitmap_iterator bi;
-  unsigned int ui;
   bool is_sibling_call;
   unsigned int i;
   df_ref def;
-  bitmap_head defs_generated;
+  HARD_REG_SET defs_generated;
 
-  bitmap_initialize (&defs_generated, &df_bitmap_obstack);
+  CLEAR_HARD_REG_SET(defs_generated);
 
   /* Do not generate clobbers for registers that are the result of the
      call.  This causes ordering problems in the chain building code
      depending on which def is seen first.  */
   FOR_EACH_VEC_ELT (df_ref, collection_rec->def_vec, i, def)
-    bitmap_set_bit (&defs_generated, DF_REF_REGNO (def));
+    SET_HARD_REG_BIT (defs_generated, DF_REF_REGNO (def));
+
+  is_sibling_call = SIBLING_CALL_P (insn_info->insn);
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    {
+      if (i == STACK_POINTER_REGNUM)
+	/* The stack ptr is used (honorarily) by a CALL insn.  */
+	df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
+		       NULL, bb, insn_info, DF_REF_REG_USE,
+		       DF_REF_CALL_STACK_USAGE | flags);
+      else if (global_regs[i])
+	{
+	  /* Calls to const functions cannot access any global registers and
+	     calls to pure functions cannot set them.  All other calls may
+	     reference any of the global registers, so they are recorded as
+	     used. */
+	  if (!RTL_CONST_CALL_P (insn_info->insn))
+	    {
+	      df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
+			     NULL, bb, insn_info, DF_REF_REG_USE, flags);
+	      if (!RTL_PURE_CALL_P (insn_info->insn))
+		df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
+			       NULL, bb, insn_info, DF_REF_REG_DEF, flags);
+	    }
+	}
+      /* TODO HARD_REG_SET set intersection! */
+      else			/* !global_regs[i] */
+	/* track Caller-Saved registers */
+	if (TEST_HARD_REG_BIT(regs_invalidated_by_call, i)
+	    && !TEST_HARD_REG_BIT (defs_generated, i)
+	    && (!is_sibling_call
+		|| !bitmap_bit_p (df->exit_block_uses, i)
+		|| refers_to_regno_p (i, i+1,
+				      crtl->return_rtx, NULL)))
+	  df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
+			 NULL, bb, insn_info, DF_REF_REG_DEF,
+			 DF_REF_MAY_CLOBBER | flags);
+    }
 
   /* Record the registers used to pass arguments, and explicitly
      noted as clobbered.  */
@@ -3345,7 +3381,7 @@
 	  if (REG_P (XEXP (XEXP (note, 0), 0)))
 	    {
 	      unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
-	      if (!bitmap_bit_p (&defs_generated, regno))
+	      if (!TEST_HARD_REG_BIT (defs_generated, regno))
 		df_defs_record (collection_rec, XEXP (note, 0), bb,
 				insn_info, flags);
 	    }
@@ -3355,40 +3391,6 @@
 	}
     }
 
-  /* The stack ptr is used (honorarily) by a CALL insn.  */
-  df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[STACK_POINTER_REGNUM],
-		 NULL, bb, insn_info, DF_REF_REG_USE,
-		 DF_REF_CALL_STACK_USAGE | flags);
-
-  /* Calls to const functions cannot access any global registers and calls to
-     pure functions cannot set them.  All other calls may reference any of the
-     global registers, so they are recorded as used.  */
-  if (!RTL_CONST_CALL_P (insn_info->insn))
-    for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
-      if (global_regs[i])
-	{
-	  df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
-			 NULL, bb, insn_info, DF_REF_REG_USE, flags);
-	  if (!RTL_PURE_CALL_P (insn_info->insn))
-	    df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
-			   NULL, bb, insn_info, DF_REF_REG_DEF, flags);
-	}
-
-  is_sibling_call = SIBLING_CALL_P (insn_info->insn);
-  EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, ui, bi)
-    {
-      if (!global_regs[ui]
-	  && (!bitmap_bit_p (&defs_generated, ui))
-	  && (!is_sibling_call
-	      || !bitmap_bit_p (df->exit_block_uses, ui)
-	      || refers_to_regno_p (ui, ui+1,
-				    crtl->return_rtx, NULL)))
-        df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[ui],
-		       NULL, bb, insn_info, DF_REF_REG_DEF,
-		       DF_REF_MAY_CLOBBER | flags);
-    }
-
-  bitmap_clear (&defs_generated);
   return;
 }