RFA: PR 34415: dbr_schedule vs. uninitialised registers

RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Richard Sandiford]

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:

      EXECUTE_IF_SET_IN_REG_SET (regs_live, FIRST_PSEUDO_REGISTER, i, rsi)
	{
	  if (reg_renumber[i] >= 0)
	    add_to_hard_reg_set (&current_live_regs, PSEUDO_REGNO_MODE (i),
				reg_renumber[i]);
	}

turned into:

      EXECUTE_IF_SET_IN_REG_SET (regs_live, FIRST_PSEUDO_REGISTER, i, rsi)
	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?

Richard


gcc/
	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.

gcc/testsuite/
	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);
 
-      EXECUTE_IF_SET_IN_REG_SET (regs_live, FIRST_PSEUDO_REGISTER, i, rsi)
-	{
-	  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;
 }
 \f
 /* Free up the resources allocated to mark_target_live_regs ().  This
@@ -1209,6 +1217,8 @@ init_resource_info (rtx epilogue_insn)
 void
 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;
 }
 \f
 /* 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;
+}
+
+int
+main (void)
+{
+  const char *input = "Bbb:";
+  return foo (input) != input + 2;
+}

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Eric Botcazou]

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

Isn't it simply the case that we use the wrong DF problem here, namely LIVE 
instead of LR?

;; End of basic block 2 -> ( 3)
;; lr  out 	 4 [$4] 6 [$6] 7 [$7] 8 [$8] 9 [$9] 10 [$10] 28 [$28] 29 [$sp] 31 
[$31]
;; live  out 	 4 [$4] 6 [$6] 7 [$7] 9 [$9] 10 [$10] 31 [$31]

-- 
Eric Botcazou

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> 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.)
>
> Isn't it simply the case that we use the wrong DF problem here, namely LIVE 
> instead of LR?
>
> ;; End of basic block 2 -> ( 3)
> ;; lr  out 	 4 [$4] 6 [$6] 7 [$7] 8 [$8] 9 [$9] 10 [$10] 28 [$28] 29 [$sp] 31 
> [$31]
> ;; live  out 	 4 [$4] 6 [$6] 7 [$7] 9 [$9] 10 [$10] 31 [$31]

Well, that would work too, but would make the register unnecessarily
live in cases where my patch wouldn't (i.e. between the barrier and
the place where the register really does become live).  I'm happy
to do it that way instead if you prefer though.

Richard

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Paolo Bonzini]

>> Isn't it simply the case that we use the wrong DF problem here, namely LIVE 
>> instead of LR?

Indeed, using LR would fix it.  The code was assuming that LIVE OUT is 
the union of the LIVE IN sets (so no register can become live just be 
crossing a BB), but this is true only of LR.  However...

>> ;; End of basic block 2 -> ( 3)
>> ;; lr  out 	 4 [$4] 6 [$6] 7 [$7] 8 [$8] 9 [$9] 10 [$10] 28 [$28] 29 [$sp] 31 
>> [$31]
>> ;; live  out  4 [$4] 6 [$6] 7 [$7] 9 [$9] 10 [$10] 31 [$31]

... you aren't looking at the whole story.  resource.c looks at IN sets, 
not OUT sets, so you should compare LIVE and LR IN for basic block 3.

LIVE is the logical AND of two problems (LR = 
live-or-must-uninitialized, and UR = maybe-initialized).  The keyword is 
"maybe": r28 is initialized in the loop, so it *is* maybe-initialized in 
the loop body.  So, r28 should be(*) LIVE IN for BB 3, and what 
Richard's patch does is to add it back to resource.c's live set.

Paolo

(*)using the conditional only because I haven't the dumps under my eyes

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Eric Botcazou]

> Indeed, using LR would fix it.  The code was assuming that LIVE OUT is
> the union of the LIVE IN sets (so no register can become live just be
> crossing a BB), but this is true only of LR.

OK, that's my understanding too.

> ... you aren't looking at the whole story.  resource.c looks at IN sets,
> not OUT sets, so you should compare LIVE and LR IN for basic block 3.

Basic block 2 if I'm not mistaken:

;; Start of basic block ( 0) -> 2
;; bb 2 artificial_defs: { }
;; bb 2 artificial_uses: { u-1(29){ }}
;; lr  in  	 4 [$4] 8 [$8] 28 [$28] 29 [$sp] 31 [$31]
;; lr  use 	 29 [$sp]
;; lr  def 	 6 [$6] 7 [$7] 9 [$9] 10 [$10]
;; live  in  	 4 [$4] 31 [$31]
;; live  gen 	 6 [$6] 7 [$7] 9 [$9] 10 [$10]
;; live  kill	

> LIVE is the logical AND of two problems (LR =
> live-or-must-uninitialized, and UR = maybe-initialized).  The keyword is
> "maybe": r28 is initialized in the loop, so it *is* maybe-initialized in
> the loop body.

Would you mind enhancing/fixing the documentation of DF?  Currently we have

/*----------------------------------------------------------------------------
   COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.

   First find the set of uses for registers that are reachable from
   the entry block without passing thru a definition.  In and out
   bitvectors are built for each basic block.  The regnum is used to
   index into these sets.  See df.h for details.

   Then the in and out sets here are the anded results of the in and
   out sets from the lr and ur
   problems. 
----------------------------------------------------------------------------*/

But there is no UR problem:

/* Scanning is not really a dataflow problem, but it is useful to have
   the basic block functions in the vector so that things get done in
   a uniform manner.  The first four problems are always defined.  The
   last 5 are optional and can be added or deleted at any time.  */
#define DF_SCAN  0 
#define DF_LR    1      /* Live Registers backward. */
#define DF_LIVE  2      /* Live Registers & Uninitialized Registers */
#define DF_RD    3      /* Reaching Defs. */
#define DF_CHAIN 4      /* Def-Use and/or Use-Def Chains. */
#define DF_NOTE  5      /* REG_DEF and REG_UNUSED notes. */

And, according to the comment, it seems that there are 9 problems.

-- 
Eric Botcazou

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Eric Botcazou]

> Well, that would work too, but would make the register unnecessarily
> live in cases where my patch wouldn't (i.e. between the barrier and
> the place where the register really does become live).  I'm happy
> to do it that way instead if you prefer though.

My understanding is that resource.c was written with the flow.c way of doing 
things in mind (in particular backward propagation) so, barring the scrapping 
of resource.c itself, I think we'd better keep using a backward problem, i.e. 
LR instead of LIVE, for resource.c.

-- 
Eric Botcazou

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Paolo Bonzini]

Eric Botcazou wrote:
>> Indeed, using LR would fix it.  The code was assuming that LIVE OUT is
>> the union of the LIVE IN sets (so no register can become live just be
>> crossing a BB), but this is true only of LR.
> 
> OK, that's my understanding too.
> 
>> ... you aren't looking at the whole story.  resource.c looks at IN sets,
>> not OUT sets, so you should compare LIVE and LR IN for basic block 3.
> 
> Basic block 2 if I'm not mistaken:
> 
> ;; Start of basic block ( 0) -> 2
> ;; bb 2 artificial_defs: { }
> ;; bb 2 artificial_uses: { u-1(29){ }}
> ;; lr  in  	 4 [$4] 8 [$8] 28 [$28] 29 [$sp] 31 [$31]
> ;; lr  use 	 29 [$sp]
> ;; lr  def 	 6 [$6] 7 [$7] 9 [$9] 10 [$10]
> ;; live  in  	 4 [$4] 31 [$31]
> ;; live  gen 	 6 [$6] 7 [$7] 9 [$9] 10 [$10]
> ;; live  kill	

That's the entry of the function.  You have to compare the sets for the 
head of the loop.


> /*----------------------------------------------------------------------------
>    COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
> 
>    First find the set of uses for registers that are reachable from
>    the entry block without passing thru a definition.  In and out
>    bitvectors are built for each basic block.  The regnum is used to
>    index into these sets.  See df.h for details.
> 
>    Then the in and out sets here are the anded results of the in and
>    out sets from the lr and ur
>    problems. 
> ----------------------------------------------------------------------------*/
> 
> But there is no UR problem:

You're right.  In fact, it's not there explicitly, but UR is more or 
less what is described in the first paragraph.  I'll fix the docs.

Paolo

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> Well, that would work too, but would make the register unnecessarily
>> live in cases where my patch wouldn't (i.e. between the barrier and
>> the place where the register really does become live).  I'm happy
>> to do it that way instead if you prefer though.
>
> My understanding is that resource.c was written with the flow.c way of
> doing things in mind (in particular backward propagation) so, barring
> the scrapping of resource.c itself, I think we'd better keep using a
> backward problem, i.e.  LR instead of LIVE, for resource.c.

OK, here's the patch.  Regression-tested on mipsisa64-elfoabi,
OK to install?

Richard


gcc/
	PR rtl-optimization/34415
	* df.h (DF_LR_IN, DF_LR_OUT): Update comments.
	* resource.c (mark_target_live_regs): Use DF_LR_IN rather than
	df_get_live_in.  Don't handle pseudos.

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

Index: gcc/df.h
===================================================================
--- gcc/df.h	2007-12-15 10:23:43.000000000 +0000
+++ gcc/df.h	2007-12-15 10:23:46.000000000 +0000
@@ -559,9 +559,9 @@ #define DF_LIVE_BB_INFO(BB) (df_live_get
 #define DF_LIVE_IN(BB) (DF_LIVE_BB_INFO(BB)->in) 
 #define DF_LIVE_OUT(BB) (DF_LIVE_BB_INFO(BB)->out) 
 
-/* These macros are currently used by only reg-stack since it is not
-   tolerant of uninitialized variables.  This intolerance should be
-   fixed because it causes other problems.  */ 
+/* These macros are used by passes that are not tolerant of
+   uninitialized variables.  This intolerance should eventually
+   be fixed.  */
 #define DF_LR_IN(BB) (DF_LR_BB_INFO(BB)->in) 
 #define DF_LR_OUT(BB) (DF_LR_BB_INFO(BB)->out) 
 
Index: gcc/resource.c
===================================================================
--- gcc/resource.c	2007-12-15 10:23:43.000000000 +0000
+++ gcc/resource.c	2007-12-15 10:57:26.000000000 +0000
@@ -958,9 +958,8 @@ mark_target_live_regs (rtx insns, rtx ta
      TARGET.  Otherwise, we must assume everything is live.  */
   if (b != -1)
     {
-      regset regs_live = df_get_live_in (BASIC_BLOCK (b));
+      regset regs_live = DF_LR_IN (BASIC_BLOCK (b));
       rtx start_insn, stop_insn;
-      reg_set_iterator rsi;
 
       /* Compute hard regs live at start of block -- this is the real hard regs
 	 marked live, plus live pseudo regs that have been renumbered to
@@ -968,13 +967,6 @@ mark_target_live_regs (rtx insns, rtx ta
 
       REG_SET_TO_HARD_REG_SET (current_live_regs, regs_live);
 
-      EXECUTE_IF_SET_IN_REG_SET (regs_live, FIRST_PSEUDO_REGISTER, i, rsi)
-	{
-	  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 ? 
Index: gcc/testsuite/gcc.c-torture/execute/pr34415.c
===================================================================
--- /dev/null	2007-12-15 09:13:22.548096750 +0000
+++ gcc/testsuite/gcc.c-torture/execute/pr34415.c	2007-12-15 10:23:46.000000000 +0000
@@ -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;
+}
+
+int
+main (void)
+{
+  const char *input = "Bbb:";
+  return foo (input) != input + 2;
+}

Re: RFA: PR 34415: dbr_schedule vs. uninitialised registers

[Eric Botcazou]

> gcc/
> 	PR rtl-optimization/34415
> 	* df.h (DF_LR_IN, DF_LR_OUT): Update comments.
> 	* resource.c (mark_target_live_regs): Use DF_LR_IN rather than
> 	df_get_live_in.  Don't handle pseudos.
>
> gcc/testsuite/
> 	PR rtl-optimization/34415
> 	* gcc.c-torture/execute/pr34415.c: New test.

OK, thanks.

-- 
Eric Botcazou