diff mbox

[1/2] Rename across ebbs

Message ID 4DDFF6F9.3090605@codesourcery.com
State New
Headers show

Commit Message

Bernd Schmidt May 27, 2011, 7:09 p.m. UTC 
While working on a C6X scheduling patch, I found myself wondering - what
would be involved in making the register renamer operate on extended
basic blocks rather than simple bbs? Somewhat surprisingly, the answer
turns out to be "not much". After the last rewrite, all the conflict
tests are based on id numbers and bitmaps, not live ranges.

The following two patches add support for saving and restoring renamer
state at basic block boundaries. Below is the initial patch, which just
reorders the code a little without changing functionality. Besides
moving and splitting out functions, I've only removed one redundant
structure field and some #if 0'ed code.

Bootstrapped and regression tested (with both patches applied) on
i686-linux, with

@@ -5106,6 +5106,9 @@ static const struct default_options ix86
+#ifdef INSN_SCHEDULING
+    { OPT_LEVELS_2_PLUS, OPT_frename_registers, NULL, 1 },
+#endif

to ensure it gets tested. Also tested with a 4.5 c6x-elf toolchain,
which has -frename-registers enabled by default. With a few other
changes to make full use of it, I get up to 10% speedup on certain
testcases on c6x. It would be nice if someone could run benchmarks on
other targets where this could affect performance. I may or may not
manage an i686 SPEC run over the weekend; it's unlikely to be affected
much due to not using sched_ebb.


Bernd
* regrename.c (struct du_head): Remove member terminated.
	(create_new_chain): Don't initialize it.
	(scan_rtx_reg): Don't set or test it, test the open_chains_set
	bitmap instead.
	(tick, this_tick): New global variables, moved out of
	regrename_optimize.
	(current_id, open_chains, closed_chains, open_chains_set,
	live_in_chains, live_hard_regs): Reorder declarations.
	(dump_def_use_chain): Move function earlier in the file.
	(rename_chains): New static function, broken out of
	regrename_optimize.
	(regrename_optimize): Use it.  Remove #if 0'ed code.

Comments

Richard Sandiford Aug. 24, 2011, 10:11 a.m. UTC | #1 
Bernd Schmidt <bernds@codesourcery.com> writes:
> 	* regrename.c (struct du_head): Remove member terminated.
> 	(create_new_chain): Don't initialize it.
> 	(scan_rtx_reg): Don't set or test it, test the open_chains_set
> 	bitmap instead.
> 	(tick, this_tick): New global variables, moved out of
> 	regrename_optimize.
> 	(current_id, open_chains, closed_chains, open_chains_set,
> 	live_in_chains, live_hard_regs): Reorder declarations.
> 	(dump_def_use_chain): Move function earlier in the file.
> 	(rename_chains): New static function, broken out of
> 	regrename_optimize.
> 	(regrename_optimize): Use it.  Remove #if 0'ed code.

The reindent operation seems to have introduced some weird formatting
(due in some cases to the existing code not really following the rules).
So:

> +/* Process the closed chains starting with ALL_CHAINS and rename
> +   registers if possible.  */
> +static void
> +rename_chains (du_head_p all_chains)
> +{
> +  HARD_REG_SET unavailable;
> +
> +

excess whitespace here.

> +      /* Iterate over elements in the chain in order to:
> +	 1. Count number of uses, and narrow the set of registers we can
> +	 use for renaming.
> +	 2. Compute the superunion of register classes in this chain.  */

original formatting was better:

      /* Iterate over elements in the chain in order to:
	 1. Count number of uses, and narrow the set of registers we can
	    use for renaming.
	 2. Compute the superunion of register classes in this chain.  */

> +	      if (has_preferred_class
> +		  && (pass == 0)
> +		  != TEST_HARD_REG_BIT
> +		  (reg_class_contents[preferred_class], new_reg))
> +		continue;

The last two lines of the condition aren't indented properly.
(I checked it wasn't just a diff artefact.)

> +		  && ((pass == 0
> +		       && !TEST_HARD_REG_BIT
> +		       (reg_class_contents[preferred_class],
> +			best_new_reg))
> +		      || tick[best_new_reg] > tick[new_reg]))

Same thing with the TEST_HARD_REG_BIT argument here.

OK otherwise, thanks.  I suppose removing the terminated field is a
(very) slight compile-time pessimisation in itself.  We only set it
when we were modifying the chain anyway, so there should be no cache
pollution problems.  And calling bitmap_bit_p is more expensive than
a bitfield test on a structure that we're already looking at.

The difference is nothing like enough to be a problem though, especially
if it makes the other patch easier.  Just saying in case anyone thought
it wasn't being considered...

Richard
diff mbox

Patch

Index: gcc/regrename.c
===================================================================
--- gcc/regrename.c.orig
+++ gcc/regrename.c
@@ -85,8 +85,6 @@  struct du_head
   /* Conflicts with untracked hard registers.  */
   HARD_REG_SET hard_conflicts;
 
-  /* Nonzero if the chain is finished; zero if it is still open.  */
-  unsigned int terminated:1;
   /* Nonzero if the chain crosses a call.  */
   unsigned int need_caller_save_reg:1;
   /* Nonzero if the register is used in a way that prevents renaming,
@@ -132,6 +130,11 @@  static const char * const scan_actions_n
   "mark_access"
 };
 
+/* TICK and THIS_TICK are used to record the last time we saw each
+   register.  */
+static int tick[FIRST_PSEUDO_REGISTER];
+static int this_tick = 0;
+
 static struct obstack rename_obstack;
 
 static void do_replace (struct du_head *, int);
@@ -147,8 +150,49 @@  static void dump_def_use_chain (struct d
 typedef struct du_head *du_head_p;
 DEF_VEC_P (du_head_p);
 DEF_VEC_ALLOC_P (du_head_p, heap);
+
+/* The id to be given to the next opened chain.  */
+static unsigned current_id;
+
+/* A mapping of unique id numbers to chains.  */
 static VEC(du_head_p, heap) *id_to_chain;
 
+/* List of currently open chains, and closed chains that can be renamed.  */
+static struct du_head *open_chains;
+static struct du_head *closed_chains;
+
+/* Bitmap of open chains.  The bits set always match the list found in
+   open_chains.  */
+static bitmap_head open_chains_set;
+
+/* Record the registers being tracked in open_chains.  */
+static HARD_REG_SET live_in_chains;
+
+/* Record the registers that are live but not tracked.  The intersection
+   between this and live_in_chains is empty.  */
+static HARD_REG_SET live_hard_regs;
+
+/* Dump all def/use chains in CHAINS to DUMP_FILE.  */
+
+static void
+dump_def_use_chain (struct du_head *head)
+{
+  while (head)
+    {
+      struct du_chain *this_du = head->first;
+      fprintf (dump_file, "Register %s (%d):",
+	       reg_names[head->regno], head->nregs);
+      while (this_du)
+	{
+	  fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
+		   reg_class_names[this_du->cl]);
+	  this_du = this_du->next_use;
+	}
+      fprintf (dump_file, "\n");
+      head = head->next_chain;
+    }
+}
+
 static void
 free_chain_data (void)
 {
@@ -225,13 +269,160 @@  check_new_reg_p (int reg ATTRIBUTE_UNUSE
   return true;
 }
 
+/* Process the closed chains starting with ALL_CHAINS and rename
+   registers if possible.  */
+static void
+rename_chains (du_head_p all_chains)
+{
+  HARD_REG_SET unavailable;
+
+
+  CLEAR_HARD_REG_SET (unavailable);
+  /* Don't clobber traceback for noreturn functions.  */
+  if (frame_pointer_needed)
+    {
+      add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
+#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
+      add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
+#endif
+    }
+
+  while (all_chains)
+    {
+      int new_reg, best_new_reg, best_nregs;
+      int n_uses;
+      struct du_head *this_head = all_chains;
+      struct du_chain *tmp;
+      HARD_REG_SET this_unavailable;
+      int reg = this_head->regno;
+      int pass;
+      enum reg_class super_class = NO_REGS;
+      enum reg_class preferred_class;
+      bool has_preferred_class;
+
+      all_chains = this_head->next_chain;
+
+      if (this_head->cannot_rename)
+	continue;
+
+      best_new_reg = reg;
+      best_nregs = this_head->nregs;
+
+      if (fixed_regs[reg] || global_regs[reg]
+#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
+	  || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
+#else
+	  || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
+#endif
+	  )
+	continue;
+
+      COPY_HARD_REG_SET (this_unavailable, unavailable);
+
+      /* Iterate over elements in the chain in order to:
+	 1. Count number of uses, and narrow the set of registers we can
+	 use for renaming.
+	 2. Compute the superunion of register classes in this chain.  */
+      n_uses = 0;
+      super_class = NO_REGS;
+      for (tmp = this_head->first; tmp; tmp = tmp->next_use)
+	{
+	  if (DEBUG_INSN_P (tmp->insn))
+	    continue;
+	  n_uses++;
+	  IOR_COMPL_HARD_REG_SET (this_unavailable,
+				  reg_class_contents[tmp->cl]);
+	  super_class
+	    = reg_class_superunion[(int) super_class][(int) tmp->cl];
+	}
+
+      if (n_uses < 2)
+	continue;
+
+      /* Further narrow the set of registers we can use for renaming.
+	 If the chain needs a call-saved register, mark the call-used
+	 registers as unavailable.  */
+      if (this_head->need_caller_save_reg)
+	IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
+
+      /* And mark registers that overlap its lifetime as unavailable.  */
+      merge_overlapping_regs (&this_unavailable, this_head);
+
+      /* Compute preferred rename class of super union of all the classes
+	 in the chain.  */
+      preferred_class
+	= (enum reg_class) targetm.preferred_rename_class (super_class);
+
+      /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
+	 over registers that belong to PREFERRED_CLASS and try to find the
+	 best register within the class.  If that failed, we iterate in
+	 the second pass over registers that don't belong to the class.
+	 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
+	 ascending order without any preference.  */
+      has_preferred_class = (preferred_class != NO_REGS);
+      for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
+	{
+	  for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
+	    {
+	      if (has_preferred_class
+		  && (pass == 0)
+		  != TEST_HARD_REG_BIT
+		  (reg_class_contents[preferred_class], new_reg))
+		continue;
+
+	      /* In the first pass, we force the renaming of registers that
+		 don't belong to PREFERRED_CLASS to registers that do, even
+		 though the latters were used not very long ago.  */
+	      if (check_new_reg_p (reg, new_reg, this_head,
+				   this_unavailable)
+		  && ((pass == 0
+		       && !TEST_HARD_REG_BIT
+		       (reg_class_contents[preferred_class],
+			best_new_reg))
+		      || tick[best_new_reg] > tick[new_reg]))
+		{
+		  enum machine_mode mode
+		    = GET_MODE (*this_head->first->loc);
+		  best_new_reg = new_reg;
+		  best_nregs = hard_regno_nregs[new_reg][mode];
+		}
+	    }
+	  if (pass == 0 && best_new_reg != reg)
+	    break;
+	}
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "Register %s in insn %d",
+		   reg_names[reg], INSN_UID (this_head->first->insn));
+	  if (this_head->need_caller_save_reg)
+	    fprintf (dump_file, " crosses a call");
+	}
+
+      if (best_new_reg == reg)
+	{
+	  tick[reg] = ++this_tick;
+	  if (dump_file)
+	    fprintf (dump_file, "; no available better choice\n");
+	  continue;
+	}
+
+      if (dump_file)
+	fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
+
+      do_replace (this_head, best_new_reg);
+      this_head->regno = best_new_reg;
+      this_head->nregs = best_nregs;
+      tick[best_new_reg] = ++this_tick;
+      df_set_regs_ever_live (best_new_reg, true);
+    }
+}
+
 /* Perform register renaming on the current function.  */
 
 static unsigned int
 regrename_optimize (void)
 {
-  int tick[FIRST_PSEUDO_REGISTER];
-  int this_tick = 0;
   basic_block bb;
   char *first_obj;
 
@@ -248,16 +439,9 @@  regrename_optimize (void)
   FOR_EACH_BB (bb)
     {
       struct du_head *all_chains = 0;
-      HARD_REG_SET unavailable;
-#if 0
-      HARD_REG_SET regs_seen;
-      CLEAR_HARD_REG_SET (regs_seen);
-#endif
 
       id_to_chain = VEC_alloc (du_head_p, heap, 0);
 
-      CLEAR_HARD_REG_SET (unavailable);
-
       if (dump_file)
 	fprintf (dump_file, "\nBasic block %d:\n", bb->index);
 
@@ -266,154 +450,7 @@  regrename_optimize (void)
       if (dump_file)
 	dump_def_use_chain (all_chains);
 
-      CLEAR_HARD_REG_SET (unavailable);
-      /* Don't clobber traceback for noreturn functions.  */
-      if (frame_pointer_needed)
-	{
-	  add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
-#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
-	  add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
-#endif
-	}
-
-      while (all_chains)
-	{
-	  int new_reg, best_new_reg, best_nregs;
-	  int n_uses;
-	  struct du_head *this_head = all_chains;
-	  struct du_chain *tmp;
-	  HARD_REG_SET this_unavailable;
-	  int reg = this_head->regno;
-	  int pass;
-	  enum reg_class super_class = NO_REGS;
-	  enum reg_class preferred_class;
-	  bool has_preferred_class;
-
-	  all_chains = this_head->next_chain;
-
-	  if (this_head->cannot_rename)
-	    continue;
-
-	  best_new_reg = reg;
-	  best_nregs = this_head->nregs;
-
-#if 0 /* This just disables optimization opportunities.  */
-	  /* Only rename once we've seen the reg more than once.  */
-	  if (! TEST_HARD_REG_BIT (regs_seen, reg))
-	    {
-	      SET_HARD_REG_BIT (regs_seen, reg);
-	      continue;
-	    }
-#endif
-
-	  if (fixed_regs[reg] || global_regs[reg]
-#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
-	      || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
-#else
-	      || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
-#endif
-	      )
-	    continue;
-
-	  COPY_HARD_REG_SET (this_unavailable, unavailable);
-
-	  /* Iterate over elements in the chain in order to:
-	     1. Count number of uses, and narrow the set of registers we can
-		use for renaming.
-	     2. Compute the superunion of register classes in this chain.  */
-	  n_uses = 0;
-	  super_class = NO_REGS;
-	  for (tmp = this_head->first; tmp; tmp = tmp->next_use)
-	    {
-	      if (DEBUG_INSN_P (tmp->insn))
-		continue;
-	      n_uses++;
-	      IOR_COMPL_HARD_REG_SET (this_unavailable,
-				      reg_class_contents[tmp->cl]);
-	      super_class
-		= reg_class_superunion[(int) super_class][(int) tmp->cl];
-	    }
-
-	  if (n_uses < 2)
-	    continue;
-
-	  /* Further narrow the set of registers we can use for renaming.
-	     If the chain needs a call-saved register, mark the call-used
-	     registers as unavailable.  */
-	  if (this_head->need_caller_save_reg)
-	    IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
-
-	  /* And mark registers that overlap its lifetime as unavailable.  */
-	  merge_overlapping_regs (&this_unavailable, this_head);
-
-	  /* Compute preferred rename class of super union of all the classes
-	     in the chain.  */
-	  preferred_class
-	    = (enum reg_class) targetm.preferred_rename_class (super_class);
-
-	  /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
-	     over registers that belong to PREFERRED_CLASS and try to find the
-	     best register within the class.  If that failed, we iterate in
-	     the second pass over registers that don't belong to the class.
-	     If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
-	     ascending order without any preference.  */
-	  has_preferred_class = (preferred_class != NO_REGS);
-	  for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
-	    {
-	      for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
-		{
-		  if (has_preferred_class
-		      && (pass == 0)
-			 != TEST_HARD_REG_BIT
-			    (reg_class_contents[preferred_class], new_reg))
-		    continue;
-
-		  /* In the first pass, we force the renaming of registers that
-		     don't belong to PREFERRED_CLASS to registers that do, even
-		     though the latters were used not very long ago.  */
-		  if (check_new_reg_p (reg, new_reg, this_head,
-				       this_unavailable)
-		      && ((pass == 0
-			   && !TEST_HARD_REG_BIT
-			       (reg_class_contents[preferred_class],
-			        best_new_reg))
-			  || tick[best_new_reg] > tick[new_reg]))
-		    {
-		      enum machine_mode mode
-			= GET_MODE (*this_head->first->loc);
-		      best_new_reg = new_reg;
-		      best_nregs = hard_regno_nregs[new_reg][mode];
-		    }
-		}
-	      if (pass == 0 && best_new_reg != reg)
-		break;
-	    }
-
-	  if (dump_file)
-	    {
-	      fprintf (dump_file, "Register %s in insn %d",
-		       reg_names[reg], INSN_UID (this_head->first->insn));
-	      if (this_head->need_caller_save_reg)
-		fprintf (dump_file, " crosses a call");
-	    }
-
-	  if (best_new_reg == reg)
-	    {
-	      tick[reg] = ++this_tick;
-	      if (dump_file)
-		fprintf (dump_file, "; no available better choice\n");
-	      continue;
-	    }
-
-	  if (dump_file)
-	    fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
-
-	  do_replace (this_head, best_new_reg);
-	  this_head->regno = best_new_reg;
-	  this_head->nregs = best_nregs;
-	  tick[best_new_reg] = ++this_tick;
-	  df_set_regs_ever_live (best_new_reg, true);
-	}
+      rename_chains (all_chains);
 
       free_chain_data ();
       obstack_free (&rename_obstack, first_obj);
@@ -507,24 +544,6 @@  mark_conflict (struct du_head *chains, u
    without renaming.  */
 static bool fail_current_block;
 
-/* The id to be given to the next opened chain.  */
-static unsigned current_id;
-
-/* List of currently open chains, and closed chains that can be renamed.  */
-static struct du_head *open_chains;
-static struct du_head *closed_chains;
-
-/* Bitmap of open chains.  The bits set always match the list found in
-   open_chains.  */
-static bitmap_head open_chains_set;
-
-/* Record the registers being tracked in open_chains.  */
-static HARD_REG_SET live_in_chains;
-
-/* Record the registers that are live but not tracked.  The intersection
-   between this and live_in_chains is empty.  */
-static HARD_REG_SET live_hard_regs;
-
 /* Return true if OP is a reg for which all bits are set in PSET, false
    if all bits are clear.
    In other cases, set fail_current_block and return false.  */
@@ -603,7 +622,6 @@  create_new_chain (unsigned this_regno, u
   head->nregs = this_nregs;
   head->need_caller_save_reg = 0;
   head->cannot_rename = 0;
-  head->terminated = 0;
 
   VEC_safe_push (du_head_p, heap, id_to_chain, head);
   head->id = current_id++;
@@ -682,7 +700,7 @@  scan_rtx_reg (rtx insn, rtx *loc, enum r
       int subset = (this_regno >= head->regno
 		      && this_regno + this_nregs <= head->regno + head->nregs);
 
-      if (head->terminated
+      if (!bitmap_bit_p (&open_chains_set, head->id)
 	  || head->regno + head->nregs <= this_regno
 	  || this_regno + this_nregs <= head->regno)
 	{
@@ -757,7 +775,6 @@  scan_rtx_reg (rtx insn, rtx *loc, enum r
 	{
 	  unsigned nregs;
 
-	  head->terminated = 1;
 	  head->next_chain = closed_chains;
 	  closed_chains = head;
 	  bitmap_clear_bit (&open_chains_set, head->id);
@@ -1407,29 +1424,6 @@  build_def_use (basic_block bb)
      is still open lives past the basic block, so it can't be renamed.  */
   return closed_chains;
 }
-
-/* Dump all def/use chains in CHAINS to DUMP_FILE.  They are
-   printed in reverse order as that's how we build them.  */
-
-static void
-dump_def_use_chain (struct du_head *head)
-{
-  while (head)
-    {
-      struct du_chain *this_du = head->first;
-      fprintf (dump_file, "Register %s (%d):",
-	       reg_names[head->regno], head->nregs);
-      while (this_du)
-	{
-	  fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
-		   reg_class_names[this_du->cl]);
-	  this_du = this_du->next_use;
-	}
-      fprintf (dump_file, "\n");
-      head = head->next_chain;
-    }
-}
-
 
 static bool
 gate_handle_regrename (void)