RFA: PR 34415: dbr_schedule vs. uninitialised registers

Richard Sandiford rsandifo@nildram.co.uk
Tue Dec 11 10:06:00 GMT 2007

dbr_schedule is the only user of resource.c, which is based
on this horrible hack of assuming that, although the basic block
information is no longer up-to-date, we can still rely on the live
register sets before BARRIERs.  We also assume that we can rely on
REG_DEAD notes to some extent: if a register is marked dead by a
REG_DEAD note, and isn't set again before the next label, we assume
it really is dead at the label.  (We assume that we can't rely on
the notes beyond that.)

So, the current approach to deciding what registers are live at point X
is to search back from X to the first BARRIER (or to the start of the
function), take the set of the live registers from the following label's
basic block, and assume that anything that dies before X without being
set again really is dead.

This doesn't work when the fallthrough entry to a loop leaves a register
R uninitialised.  Suppose X is in the loop, but before the first set of
R, and that the liveness computation starts outside the loop.  In this
situation, we won't notice that R is live, and so we might decide that
it is safe to put a set of R in the delay slot of a conditional branch.
(This didn't used to be a problem, because we'd make R live from the
start of the function to the start of the loop.  We're more accurate
now though, and that's obviously a good thing.)

That's what happens on the testcase below.  "end" is uninitialised
on entry to the loop, and we decide to put the first assignment to
"end" in the delay slot of the "c == 'B'" branch.  This means that
even the "break" case assigns to "end", and thus foo() returns
input + 3 rather than input + 2.

The reasons for resource.c's assumptions are all historical, and include
things like the basic block information being computed before reload and
not being updated by it.  Being a beginning-to-end insn walk rather than
a "proper" bb-based algorithm, reload inheritance crosses labels on
fallthrough, but not otherwise.  However, I don't think it's safe even
now to rely on the stale basic block info completely.  I expect some
targets' md_reorgs (for example) could invalidate the liveness info
to some extent.  Then there are the effects of dbr_schedule itself.

Obviously the best thing would be keep tye bb info up to date until
the end, and preferably to fold dbr_schedule into the main schedulers.
But both are big projects, and certainly not suitable for stage 3.

For now, I think the best we can do is as follows: when
mark_target_live_regs sees a label that it can associate with an old
basic block, it assumes that all registers that used to be live then
still are.  It doesn't use this information to _kill_ any registers,
so the new function should be strictly more conservative than the old.

BLOCK_FOR_INSN is not available at this stage, so find_basic_block
currently loops over every basic block whenever it wants to find
the one associated with a label:

  for (insn = next_nonnote_insn (insn);
       insn && LABEL_P (insn);
       insn = next_nonnote_insn (insn))
      FOR_EACH_BB (bb)
	if (insn == BB_HEAD (bb))
	  return bb->index;

It would be really expensive to do that in mark_target_live_regs
as well, so I think init_resource_info should set up BLOCK_FOR_INSN
for BB_HEAD labels.  I think the conservative thing is to clear
them again afterwards; although that might not be needed, I think
we're so far down hack creek that we'd better make the state
consistent between dbr_schedule and non-dbr_schedule modes and targets.

I ran CSiBE on mips-linux-gnu to see what effect this had there,
and there were no changes.  I also regression-tested with:

	  if (reg_renumber[i] >= 0)
	    add_to_hard_reg_set (&current_live_regs, PSEUDO_REGNO_MODE (i),

turned into:

	gcc_unreachable ();

and, as expected, there were no differences.  The patch therefore removes
this code.  (I thought I'd better do that at the same time for consistency
with the new code, which doesn't handle pseudo registers either.)

Regression-tested on mips-linux-gnu.  OK to install?


	PR rtl-optimization/34415
	* resource.c (find_basic_block): Use BLOCK_FOR_INSN to look up
	a label's basic block.
	(mark_target_live_regs): Remove handling of pseudo registers.
	If a label started a basic block, assume that all registers
	that used to be live then still are.
	(init_resource_info): If a label starts a basic block, set its
	BLOCK_FOR_INSN accordingly.
	(fini_resource_info): Undo the setting of BLOCK_FOR_INSN.

	PR rtl-optimization/34415
	* gcc.c-torture/execute/pr34415.c: New test.

Index: gcc/resource.c
--- gcc/resource.c	(revision 130741)
+++ gcc/resource.c	(working copy)
@@ -135,8 +135,6 @@ update_live_status (rtx dest, const_rtx 
 static int
 find_basic_block (rtx insn, int search_limit)
-  basic_block bb;
   /* Scan backwards to the previous BARRIER.  Then see if we can find a
      label that starts a basic block.  Return the basic block number.  */
   for (insn = prev_nonnote_insn (insn);
@@ -157,11 +155,8 @@ find_basic_block (rtx insn, int search_l
   for (insn = next_nonnote_insn (insn);
        insn && LABEL_P (insn);
        insn = next_nonnote_insn (insn))
-    {
-      FOR_EACH_BB (bb)
-	if (insn == BB_HEAD (bb))
-	  return bb->index;
-    }
+    if (BLOCK_FOR_INSN (insn))
+      return BLOCK_FOR_INSN (insn)->index;
   return -1;
@@ -968,13 +963,6 @@ mark_target_live_regs (rtx insns, rtx ta
       REG_SET_TO_HARD_REG_SET (current_live_regs, regs_live);
-	{
-	  if (reg_renumber[i] >= 0)
-	    add_to_hard_reg_set (&current_live_regs, PSEUDO_REGNO_MODE (i),
-				reg_renumber[i]);
-	}
       /* Get starting and ending insn, handling the case where each might
 	 be a SEQUENCE.  */
       start_insn = (b == ENTRY_BLOCK_PTR->next_bb->index ? 
@@ -1058,10 +1046,24 @@ mark_target_live_regs (rtx insns, rtx ta
 	  else if (LABEL_P (real_insn))
+	      basic_block bb;
 	      /* A label clobbers the pending dead registers since neither
 		 reload nor jump will propagate a value across a label.  */
 	      AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
 	      CLEAR_HARD_REG_SET (pending_dead_regs);
+	      /* We must conservatively assume that all registers that used
+		 to be live here still are.  The fallthrough edge may have
+		 left a live register uninitialized.  */
+	      bb = BLOCK_FOR_INSN (real_insn);
+	      if (bb)
+		{
+		  HARD_REG_SET extra_live;
+		  REG_SET_TO_HARD_REG_SET (extra_live, df_get_live_in (bb));
+		  IOR_HARD_REG_SET (current_live_regs, extra_live);
+		}
 	  /* The beginning of the epilogue corresponds to the end of the
@@ -1133,6 +1135,7 @@ mark_target_live_regs (rtx insns, rtx ta
 init_resource_info (rtx epilogue_insn)
   int i;
+  basic_block bb;
   /* Indicate what resources are required to be valid at the end of the current
      function.  The condition code never is and memory always is.  If the
@@ -1201,6 +1204,11 @@ init_resource_info (rtx epilogue_insn)
   /* Allocate and initialize the tables used by mark_target_live_regs.  */
   target_hash_table = XCNEWVEC (struct target_info *, TARGET_HASH_PRIME);
   bb_ticks = XCNEWVEC (int, last_basic_block);
+  /* Set the BLOCK_FOR_INSN of each label that starts a basic block.  */
+  FOR_EACH_BB (bb)
+    if (LABEL_P (BB_HEAD (bb)))
+      BLOCK_FOR_INSN (BB_HEAD (bb)) = bb;
 /* Free up the resources allocated to mark_target_live_regs ().  This
@@ -1209,6 +1217,8 @@ init_resource_info (rtx epilogue_insn)
 free_resource_info (void)
+  basic_block bb;
   if (target_hash_table != NULL)
       int i;
@@ -1234,6 +1244,10 @@ free_resource_info (void)
       free (bb_ticks);
       bb_ticks = NULL;
+  FOR_EACH_BB (bb)
+    if (LABEL_P (BB_HEAD (bb)))
+      BLOCK_FOR_INSN (BB_HEAD (bb)) = NULL;
 /* Clear any hashed information that we have stored for INSN.  */
Index: gcc/testsuite/gcc.c-torture/execute/pr34415.c
--- gcc/testsuite/gcc.c-torture/execute/pr34415.c	(revision 0)
+++ gcc/testsuite/gcc.c-torture/execute/pr34415.c	(revision 0)
@@ -0,0 +1,34 @@
+const char *__attribute__((noinline))
+foo (const char *p)
+  const char *end;
+  int len = 1;
+  for (;;)
+    {
+      int c = *p;
+      c = (c >= 'a' && c <= 'z' ? c - 'a' + 'A' : c);
+      if (c == 'B')
+	end = p;
+      else if (c == 'A')
+	{
+	  end = p;
+	  do
+	    p++;
+	  while (*p == '+');
+	}
+      else
+	break;
+      p++;
+      len++;
+    }
+  if (len > 2 && *p == ':')
+    p = end;
+  return p;
+main (void)
+  const char *input = "Bbb:";
+  return foo (input) != input + 2;

More information about the Gcc-patches mailing list