public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [1/2] Rename across ebbs
@ 2011-05-27 20:10 Bernd Schmidt
  2011-05-27 20:20 ` [2/2] " Bernd Schmidt
  2011-08-24 11:21 ` [1/2] " Richard Sandiford
  0 siblings, 2 replies; 3+ messages in thread
From: Bernd Schmidt @ 2011-05-27 20:10 UTC (permalink / raw)
  To: GCC Patches

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

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

[-- Attachment #2: rnreg-prelim.diff --]
[-- Type: text/plain, Size: 15866 bytes --]

	* 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.

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;
-    }
-}
-
 \f
 static bool
 gate_handle_regrename (void)

^ permalink raw reply	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2011-08-24 10:12 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-05-27 20:10 [1/2] Rename across ebbs Bernd Schmidt
2011-05-27 20:20 ` [2/2] " Bernd Schmidt
2011-08-24 11:21 ` [1/2] " Richard Sandiford

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).