[2/2] Rename across ebbs

[Bernd Schmidt <bernds@codesourcery.com>]

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

This patch contains the actual changes for renaming across extended
basic blocks (where ebb here is a tree where each basic block except the
root has exactly one predecessor).

All we really have to do is reconstruct some information when starting
to scan a different bb; the open_chains list can be rebuilt from the
open_chains_set bitmap.


Bernd


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

	* regrename.c (build_def_use): Return bool, true if we produced
	a valid set of chains.  All callers and	declaration changed.
	Rely on the caller to initialize global state.
	(closed_chains): Remove variable.
	(dump_def_use_chain): Take no arg.  All callers changed.  Use
	the id_to_chain vector as a source of things to print.
	(rename_chains): Replace argument with a bitmap of chains that
	cannot be renamed.  All callers changed.  Use the id_to_chain
	vector to find candidate chains for renaming.
	(struct bb_rename_info): New structure.
	(init_rename_info, save_rename_info, restore_rename_info): New
	static functions.
	(regrename_optimize): Use them to process ebbs rather than single
	basic blocks and to initialize global state for build_def_use.
	(scan_rtx_reg): Don't update closed_chains.

Index: trunk/gcc/regrename.c
===================================================================
--- trunk.orig/gcc/regrename.c
+++ trunk/gcc/regrename.c
@@ -144,8 +144,7 @@ static void scan_rtx_address (rtx, rtx *
 			      enum scan_actions, enum machine_mode);
 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
 		      enum op_type);
-static struct du_head *build_def_use (basic_block);
-static void dump_def_use_chain (struct du_head *);
+static bool build_def_use (basic_block);
 
 typedef struct du_head *du_head_p;
 DEF_VEC_P (du_head_p);
@@ -157,9 +156,8 @@ 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.  */
+/* List of currently open chains.  */
 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.  */
@@ -175,9 +173,11 @@ 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)
+dump_def_use_chain (void)
 {
-  while (head)
+  du_head_p head;
+  int i;
+  FOR_EACH_VEC_ELT (du_head_p, id_to_chain, i, head)
     {
       struct du_chain *this_du = head->first;
       fprintf (dump_file, "Register %s (%d):",
@@ -269,13 +269,16 @@ check_new_reg_p (int reg ATTRIBUTE_UNUSE
   return true;
 }
 
-/* Process the closed chains starting with ALL_CHAINS and rename
-   registers if possible.  */
+/* Process the chains found in id_to_chain and rename registers if
+   possible.  CANNOT_RENAME_CHAINS is a bitmap containing chains
+   that cannot be renamed for some reason.  */
+
 static void
-rename_chains (du_head_p all_chains)
+rename_chains (bitmap cannot_rename_chains)
 {
   HARD_REG_SET unavailable;
-
+  du_head_p this_head;
+  int i;
 
   CLEAR_HARD_REG_SET (unavailable);
   /* Don't clobber traceback for noreturn functions.  */
@@ -287,11 +290,10 @@ rename_chains (du_head_p all_chains)
 #endif
     }
 
-  while (all_chains)
+  FOR_EACH_VEC_ELT (du_head_p, id_to_chain, i, this_head)
     {
       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;
@@ -300,9 +302,8 @@ rename_chains (du_head_p all_chains)
       enum reg_class preferred_class;
       bool has_preferred_class;
 
-      all_chains = this_head->next_chain;
-
-      if (this_head->cannot_rename)
+      if (this_head->cannot_rename
+	  || bitmap_bit_p (cannot_rename_chains, this_head->id))
 	continue;
 
       best_new_reg = reg;
@@ -418,13 +419,100 @@ rename_chains (du_head_p all_chains)
     }
 }
 
+/* A structure recording information about each basic block.  It is saved
+   and restored around basic block boundaries.  */
+struct bb_rename_info
+{
+  /* The basic block corresponding to this structure.  */
+  basic_block bb;
+  /* Copies of the global information.  */
+  bitmap_head open_chains_set;
+  HARD_REG_SET live_in_chains;
+  HARD_REG_SET live_hard_regs;
+};
+
+/* Initialize a rename_info structure P for basic block BB, which starts a new
+   scan.  */
+static void
+init_rename_info (struct bb_rename_info *p, basic_block bb)
+{
+  df_ref *def_rec;
+
+  p->bb = bb;
+  bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack);
+
+  CLEAR_HARD_REG_SET (p->live_in_chains);
+  REG_SET_TO_HARD_REG_SET (p->live_hard_regs, df_get_live_in (bb));
+  for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+	SET_HARD_REG_BIT (p->live_hard_regs, DF_REF_REGNO (def));
+    }
+
+}
+
+/* Save current rename info data into structure P, which will be restored later
+   to continue scanning at basic block BB.  OPEN_SET is the set of open chains
+   at the start of BB.  */
+static void
+save_rename_info (struct bb_rename_info *p, basic_block bb, bitmap open_set)
+{
+  HARD_REG_SET live;
+
+  p->bb = bb;
+
+  bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack);
+  bitmap_copy (&p->open_chains_set, open_set);
+
+  REG_SET_TO_HARD_REG_SET (live, df_get_live_in (bb));
+
+  COPY_HARD_REG_SET (p->live_in_chains, live_in_chains);
+  COPY_HARD_REG_SET (p->live_hard_regs, live_hard_regs);
+  AND_HARD_REG_SET (p->live_in_chains, live);
+  AND_HARD_REG_SET (p->live_hard_regs, live);
+}
+
+/* Restore global state from the rename info structure P.  Recompute the
+   open_chains list and the live_in_chains set from the bitmap stored in P.
+   This function frees the bitmap data associated with P.  */
+static void
+restore_rename_info (struct bb_rename_info *p)
+{
+  bitmap_iterator bi;
+  unsigned int i;
+
+  open_chains = NULL;
+  bitmap_copy (&open_chains_set, &p->open_chains_set);
+  bitmap_clear (&p->open_chains_set);
+
+  CLEAR_HARD_REG_SET (live_in_chains);
+  EXECUTE_IF_SET_IN_BITMAP (&open_chains_set, 0, i, bi)
+    {
+      struct du_head *this_chain = VEC_index (du_head_p, id_to_chain,
+					      i);
+
+      this_chain->next_chain = open_chains;
+      open_chains = this_chain;
+      if (dump_file)
+	fprintf (dump_file, "  reopening %s (chain %d)\n",
+		 reg_names[this_chain->regno], this_chain->id);
+    }
+  COPY_HARD_REG_SET (live_hard_regs, p->live_hard_regs);
+  COPY_HARD_REG_SET (live_in_chains, p->live_in_chains);
+}
+
 /* Perform register renaming on the current function.  */
 
 static unsigned int
 regrename_optimize (void)
 {
+  struct bb_rename_info *rename_info;
+  int ri_index;
   basic_block bb;
   char *first_obj;
+  bitmap_head processed_bbs;
+  bitmap_initialize (&processed_bbs, &bitmap_default_obstack);
 
   df_set_flags (DF_LR_RUN_DCE);
   df_note_add_problem ();
@@ -436,21 +524,99 @@ regrename_optimize (void)
   gcc_obstack_init (&rename_obstack);
   first_obj = XOBNEWVAR (&rename_obstack, char, 0);
 
+  rename_info = XNEWVEC (struct bb_rename_info, n_basic_blocks);
   FOR_EACH_BB (bb)
     {
-      struct du_head *all_chains = 0;
+      VEC (int, heap) *bb_queue;
+      edge e;
+      edge_iterator ei;
+      bitmap_head chains_open_at_end;
+      bitmap_head tmp_chains;
+      bool fail = false;
 
+      if (!bitmap_set_bit (&processed_bbs, bb->index))
+	continue;
+
+      ri_index = 0;
+      current_id = 0;
       id_to_chain = VEC_alloc (du_head_p, heap, 0);
+      bb_queue = VEC_alloc (int, heap, 0);
+
+      VEC_safe_push (int, heap, bb_queue, ri_index);
+      init_rename_info (rename_info + ri_index, bb);
+      ri_index++;
 
       if (dump_file)
 	fprintf (dump_file, "\nBasic block %d:\n", bb->index);
 
-      all_chains = build_def_use (bb);
+      bitmap_initialize (&chains_open_at_end, &bitmap_default_obstack);
+      bitmap_initialize (&tmp_chains, &bitmap_default_obstack);
+
+      while (!VEC_empty (int, bb_queue))
+	{
+	  int this_index = VEC_pop (int, bb_queue);
+	  struct bb_rename_info *this_info = rename_info + this_index;
+	  basic_block bb1 = this_info->bb;
+
+	  if (dump_file)
+	    fprintf (dump_file, "processing block %d:\n", bb1->index);
+	  bitmap_set_bit (&processed_bbs, bb1->index);
+
+	  restore_rename_info (this_info);
+
+	  if (!build_def_use (this_info->bb))
+	    {
+	      fail = true;
+	      break;
+	    }
+
+	  FOR_EACH_EDGE (e, ei, bb1->succs)
+	    {
+	      struct du_head *chain;
+	      regset live = df_get_live_in (e->dest);
+	      if (dump_file)
+		fprintf (dump_file, "successor block %d: live regs", e->dest->index);
+	      for (chain = open_chains; chain; chain = chain->next_chain)
+		{
+		  int nregs = chain->nregs;
+		  while (nregs-- > 0)
+		    {
+		      if (REGNO_REG_SET_P (live, chain->regno + nregs))
+			{
+			  bitmap_set_bit (&tmp_chains, chain->id);
+			  if (dump_file)
+			    fprintf (dump_file, " %s (%d)",
+				     reg_names[chain->regno], chain->id);
+			  break;
+			}
+		    }
+		}
+	      if (dump_file)
+		fprintf (dump_file, "\n");
+	      if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) != 0
+		  || EDGE_COUNT (e->dest->preds) > 1
+		  || e->dest == EXIT_BLOCK_PTR
+		  || bitmap_bit_p (&processed_bbs, e->dest->index))
+		{
+		  if (dump_file)
+		    fprintf (dump_file, "  no further processing\n");
+		  bitmap_ior_into (&chains_open_at_end, &tmp_chains);
+		}
+	      else
+		{
+		  VEC_safe_push (int, heap, bb_queue, ri_index);
+		  save_rename_info (rename_info + ri_index, e->dest, &tmp_chains);
+		  ri_index++;
+		}
+	      bitmap_clear (&tmp_chains);
+	    }
+	}
 
       if (dump_file)
-	dump_def_use_chain (all_chains);
+	dump_def_use_chain ();
 
-      rename_chains (all_chains);
+      if (!fail)
+	rename_chains (&chains_open_at_end);
 
       free_chain_data ();
       obstack_free (&rename_obstack, first_obj);
@@ -775,8 +941,6 @@ scan_rtx_reg (rtx insn, rtx *loc, enum r
 	{
 	  unsigned nregs;
 
-	  head->next_chain = closed_chains;
-	  closed_chains = head;
 	  bitmap_clear_bit (&open_chains_set, head->id);
 
 	  nregs = head->nregs;
@@ -1155,28 +1319,14 @@ record_out_operands (rtx insn, bool earl
 
 /* Build def/use chain.  */
 
-static struct du_head *
+static bool
 build_def_use (basic_block bb)
 {
   rtx insn;
-  df_ref *def_rec;
   unsigned HOST_WIDE_INT untracked_operands;
 
-  open_chains = closed_chains = NULL;
-
   fail_current_block = false;
 
-  current_id = 0;
-  bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
-  CLEAR_HARD_REG_SET (live_in_chains);
-  REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
-  for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
-    {
-      df_ref def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-	SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
-    }
-
   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
     {
       if (NONDEBUG_INSN_P (insn))
@@ -1418,11 +1568,9 @@ build_def_use (basic_block bb)
   bitmap_clear (&open_chains_set);
 
   if (fail_current_block)
-    return NULL;
+    return false;
 
-  /* Since we close every chain when we find a REG_DEAD note, anything that
-     is still open lives past the basic block, so it can't be renamed.  */
-  return closed_chains;
+  return true;
 }
 \f
 static bool