[4.2 only] RFA: PR 33848: reload rematerialisation of labels

[4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

PR 33848, a 4.2 regression on MIPS, is about cases in which we have
a branch like:

    if (foo == &&bar)

and in which the register that holds &&bar is not allocated a hard register.
Reload rematerialises the load of &&bar, first replacing the pseudo register
with the label, then replacing the label with a reload register.  The
second step triggers the following code in reload.c:subst_reloads:

	  /* If we're replacing a LABEL_REF with a register, add a
	     REG_LABEL note to indicate to flow which label this
	     register refers to.  */
	  if (GET_CODE (*r->where) == LABEL_REF
	      && JUMP_P (insn))
	    {
	      REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
						    XEXP (*r->where, 0),
						    REG_NOTES (insn));
	      JUMP_LABEL (insn) = XEXP (*r->where, 0);
	   }

So we end up replacing the jump's real JUMP_LABEL with bar, and
cfgcleanup later deletes the real target as dead.

H-P fixed this properly on mainline by splitting REG_LABEL into
REG_LABEL_OPERAND and REG_LABEL_TARGET.  Unfortunately, I think that's
too invasive to backport.  As H-P said in his original posting:

    http://gcc.gnu.org/ml/gcc/2005-12/msg00279.html

it isn't possible in the 4.2 scheme for a jump to have both a target
LABEL_REF and a non-target LABEL_REF, hence his split.  And since
JUMP_LABEL should now always be valid before reload, I think we should
only add a REG_LABEL note when the label is the same as the current
JUMP_LABEL.  Calling rebuild_jump_labels immediately after reload
would then be a no-op for this particular insn, just as it should be.

I put the testcase in gcc.dg/torture rather than gcc.target/mips because
this could happen for any target with "branch on equal registers"
instructions.  I also used a brute-force test; the one in the PR
happened to pass after the %call16 backport.

Regression-tested on mips-linux-gnu.  OK for 4.2?  If so, should I install
the testcase on mainline too?

Richard


gcc/
	PR rtl-optimization/33848
	* reload.c (subst_reloads): When replacing a LABEL_REF with a
	register, only add a REG_LABEL note if the label is the target
	of the jump.

gcc/testsuite/
	PR rtl-optimization/33848
	* gcc.dg/torture/pr33848.c: New test.

Index: gcc/reload.c
===================================================================
--- gcc/reload.c	2007-10-23 11:04:20.000000000 +0100
+++ gcc/reload.c	2007-10-23 11:58:46.000000000 +0100
@@ -6158,17 +6158,16 @@ #define CHECK_MODF(ARRAY)						\
 	    }
 #endif /* ENABLE_CHECKING */
 
-	  /* If we're replacing a LABEL_REF with a register, add a
-	     REG_LABEL note to indicate to flow which label this
+	  /* If we're replacing a LABEL_REF jump target with a register,
+	     add a REG_LABEL note to indicate to flow which label this
 	     register refers to.  */
 	  if (GET_CODE (*r->where) == LABEL_REF
-	      && JUMP_P (insn))
-	    {
-	      REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
-						    XEXP (*r->where, 0),
-						    REG_NOTES (insn));
-	      JUMP_LABEL (insn) = XEXP (*r->where, 0);
-	   }
+	      && JUMP_P (insn)
+	      && JUMP_LABEL (insn) == XEXP (*r->where, 0)
+	      && !find_reg_note (insn, REG_LABEL, XEXP (*r->where, 0)))
+	    REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
+						  XEXP (*r->where, 0),
+						  REG_NOTES (insn));
 
 	  /* Encapsulate RELOADREG so its machine mode matches what
 	     used to be there.  Note that gen_lowpart_common will
Index: gcc/testsuite/gcc.dg/torture/pr33848.c
===================================================================
--- /dev/null	2007-10-23 10:23:31.552097000 +0100
+++ gcc/testsuite/gcc.dg/torture/pr33848.c	2007-10-23 11:58:07.000000000 +0100
@@ -0,0 +1,43 @@
+/* &&foo should be hoisted, but on most targets, excess register pressure
+   forces it to be rematerialized before "data != &&foo".  On targets that
+   have a "branch if registers are equal" instruction, this leads to the
+   branch having two LABEL_REFs: one for the branch target and one for
+   &&foo.  When reloading &&foo into a register, reload would wrongly
+   say that &&foo was the target of the branch, and the real target would
+   then be removed as dead.  */
+/* { dg-do link } */
+#define NVARS 30
+#define MULTI(X) \
+  X( 0), X( 1), X( 2), X( 3), X( 4), X( 5), X( 6), X( 7), X( 8), X( 9), \
+  X(10), X(11), X(12), X(13), X(14), X(15), X(16), X(17), X(18), X(19), \
+  X(20), X(21), X(22), X(23), X(24), X(25), X(26), X(27), X(28), X(29)
+
+#define DECLARE(INDEX) i##INDEX = gv[INDEX]
+#define COPY(INDEX) gv[INDEX] = i##INDEX
+
+volatile int gv[NVARS];
+void *volatile data;
+
+int
+main (void)
+{
+  __label__ foo;
+
+  if (gv[0] == 1)
+    goto foo;
+  data = &&foo;
+  do
+    {
+      int MULTI (DECLARE);
+      MULTI (COPY);
+      MULTI (COPY);
+      MULTI (COPY);
+      if (data != &&foo)
+	gv[0] = 1;
+      else
+	gv[1] = 2;
+    }
+  while (gv[0] > 0);
+ foo:
+  return 0;
+}

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Eric Botcazou]

> PR 33848, a 4.2 regression on MIPS, is about cases in which we have
> a branch like:
>
>     if (foo == &&bar)
>
> and in which the register that holds &&bar is not allocated a hard
> register. Reload rematerialises the load of &&bar, first replacing the
> pseudo register with the label, then replacing the label with a reload
> register.  The second step triggers the following code in
> reload.c:subst_reloads:
>
> 	  /* If we're replacing a LABEL_REF with a register, add a
> 	     REG_LABEL note to indicate to flow which label this
> 	     register refers to.  */
> 	  if (GET_CODE (*r->where) == LABEL_REF
> 	      && JUMP_P (insn))
> 	    {
> 	      REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
> 						    XEXP (*r->where, 0),
> 						    REG_NOTES (insn));
> 	      JUMP_LABEL (insn) = XEXP (*r->where, 0);
> 	   }
>
> So we end up replacing the jump's real JUMP_LABEL with bar, and
> cfgcleanup later deletes the real target as dead.

Yes, this is relatively recent, the original code didn't modify JUMP_LABEL.

> H-P fixed this properly on mainline by splitting REG_LABEL into
> REG_LABEL_OPERAND and REG_LABEL_TARGET.  Unfortunately, I think that's
> too invasive to backport.

Agreed.  Moreover H-P's patch still has unresolved issues.

> And since JUMP_LABEL should now always be valid before reload, I think we
> should only add a REG_LABEL note when the label is the same as the current
> JUMP_LABEL.  Calling rebuild_jump_labels immediately after reload
> would then be a no-op for this particular insn, just as it should be.

Can't we nevertheless imagine a JUMP_P insn reaching here without JUMP_LABEL?

> If so, should I install the testcase on mainline too?

I think that the testsuite should increase monotically.

-- 
Eric Botcazou

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> And since JUMP_LABEL should now always be valid before reload, I think we
>> should only add a REG_LABEL note when the label is the same as the current
>> JUMP_LABEL.  Calling rebuild_jump_labels immediately after reload
>> would then be a no-op for this particular insn, just as it should be.
>
> Can't we nevertheless imagine a JUMP_P insn reaching here without JUMP_LABEL?

Well, we build jump labels immediately after expanding, and try to keep
them up-to-date when changing jumps later.  Not keeping them up-to-date
would be a bug.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Eric Botcazou]

> Well, we build jump labels immediately after expanding, and try to keep
> them up-to-date when changing jumps later.  Not keeping them up-to-date
> would be a bug.

It's 4.2.x so we have to be conservative and avoid pulling too long a string,
that's why I would go for a very safe change in this case.

The original code was:

+	  /* If we're replacing a LABEL_REF with a register, add a
+	     REG_LABEL note to indicate to flow which label this
+	     register refers to.  */
+	  if (GET_CODE (*r->where) == LABEL_REF
+	      && GET_CODE (insn) == JUMP_INSN)
+	    REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL,
+						  XEXP (*r->where, 0),
+						  REG_NOTES (insn));

Then it was modified as follows

@@ -6033,9 +6033,12 @@ subst_reloads (rtx insn)
 	     register refers to.  */
 	  if (GET_CODE (*r->where) == LABEL_REF
 	      && JUMP_P (insn))
-	    REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
-						  XEXP (*r->where, 0),
-						  REG_NOTES (insn));
+	    {
+	      REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
+						    XEXP (*r->where, 0),
+						    REG_NOTES (insn));
+	      JUMP_LABEL (insn) = XEXP (*r->where, 0);
+	   }
 
 	  /* Encapsulate RELOADREG so its machine mode matches what
 	     used to be there.  Note that gen_lowpart_common will


I'm afraid your change would void the original intent in the name of fixing 
the subsequent modification.  Couldn't we find a middle-ground instead?

-- 
Eric Botcazou

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> Well, we build jump labels immediately after expanding, and try to keep
>> them up-to-date when changing jumps later.  Not keeping them up-to-date
>> would be a bug.
>
> It's 4.2.x so we have to be conservative and avoid pulling too long a string,
> that's why I would go for a very safe change in this case.
>
> The original code was:
>
> +	  /* If we're replacing a LABEL_REF with a register, add a
> +	     REG_LABEL note to indicate to flow which label this
> +	     register refers to.  */
> +	  if (GET_CODE (*r->where) == LABEL_REF
> +	      && GET_CODE (insn) == JUMP_INSN)
> +	    REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL,
> +						  XEXP (*r->where, 0),
> +						  REG_NOTES (insn));
>
> Then it was modified as follows
>
> @@ -6033,9 +6033,12 @@ subst_reloads (rtx insn)
>  	     register refers to.  */
>  	  if (GET_CODE (*r->where) == LABEL_REF
>  	      && JUMP_P (insn))
> -	    REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
> -						  XEXP (*r->where, 0),
> -						  REG_NOTES (insn));
> +	    {
> +	      REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL,
> +						    XEXP (*r->where, 0),
> +						    REG_NOTES (insn));
> +	      JUMP_LABEL (insn) = XEXP (*r->where, 0);
> +	   }
>  
>  	  /* Encapsulate RELOADREG so its machine mode matches what
>  	     used to be there.  Note that gen_lowpart_common will
>
>
> I'm afraid your change would void the original intent in the name of fixing 
> the subsequent modification.  Couldn't we find a middle-ground instead?

I don't think it would reopen the original wound.  The change was for
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20606, and as Andrew says
in comment #3:

------------------------------------------------------------------------
(In reply to comment #2)
> Why is computed_jump_p (insn) not returning true?
Actually it is the following insn:
(jump_insn 169 222 170 19 (set (pc)
        (reg:DI 0 ax)) 515 {*indirect_jump_rtx64} (nil)
    (insn_list:REG_LABEL 172 (nil)))

Which is a computed goto but at this point we have a REG_LABEL which
causes computed_jump_p to return false
------------------------------------------------------------------------

In other words, by unconditionally adding a REG_LABEL note, regardless
of whether there was a JUMP_LABEL, reload was turning something that
satisfied computed_jump_p into something that was neither a computed
jump nor a correct register-indirect jump to a known target.

My patch fixes the same bug by making sure that we only attach
a REG_LABEL note to jumps that already have a known target.
So with my patch, the jump in the testcase would still satsify
computed_jump_p after reload.  And I think it's a valid fix.
While turning a computed jump into a jump to a known target
is an interesting optimisation, this is not the place to do it.
Reload only sees a LABEL_REF here because the original pseudo
did not get allocated a hard register, and the transformation
from a computed jump to a jump to a known target should not
depend on register allocation failure.  The code above is purely
book keeping; the net effect of reload doesn't change the form
of the instruction, which is register-indirect both before and
after register allocation.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Eric Botcazou]

> I don't think it would reopen the original wound.  The change was for
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20606, and as Andrew says
> in comment #3:
>
> ------------------------------------------------------------------------
> (In reply to comment #2)
>
> > Why is computed_jump_p (insn) not returning true?
>
> Actually it is the following insn:
> (jump_insn 169 222 170 19 (set (pc)
>         (reg:DI 0 ax)) 515 {*indirect_jump_rtx64} (nil)
>     (insn_list:REG_LABEL 172 (nil)))
>
> Which is a computed goto but at this point we have a REG_LABEL which
> causes computed_jump_p to return false
> ------------------------------------------------------------------------
>
> In other words, by unconditionally adding a REG_LABEL note, regardless
> of whether there was a JUMP_LABEL, reload was turning something that
> satisfied computed_jump_p into something that was neither a computed
> jump nor a correct register-indirect jump to a known target.

I'm not so concerned about computed_jump_p as about the original intent of the 
code, which was added by Alexandre for SH5:
  http://gcc.gnu.org/ml/gcc-patches/2005-10/msg00176.html

> My patch fixes the same bug by making sure that we only attach
> a REG_LABEL note to jumps that already have a known target.

But what's the point in attaching a REG_LABEL note if JUMP_LABEL already 
points to the same label?  My understanding is that Alexandre's change was 
meant to add the note on jumps without JUMP_LABEL.

-- 
Eric Botcazou

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> I don't think it would reopen the original wound.  The change was for
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20606, and as Andrew says
>> in comment #3:
>>
>> ------------------------------------------------------------------------
>> (In reply to comment #2)
>>
>> > Why is computed_jump_p (insn) not returning true?
>>
>> Actually it is the following insn:
>> (jump_insn 169 222 170 19 (set (pc)
>>         (reg:DI 0 ax)) 515 {*indirect_jump_rtx64} (nil)
>>     (insn_list:REG_LABEL 172 (nil)))
>>
>> Which is a computed goto but at this point we have a REG_LABEL which
>> causes computed_jump_p to return false
>> ------------------------------------------------------------------------
>>
>> In other words, by unconditionally adding a REG_LABEL note, regardless
>> of whether there was a JUMP_LABEL, reload was turning something that
>> satisfied computed_jump_p into something that was neither a computed
>> jump nor a correct register-indirect jump to a known target.
>
> I'm not so concerned about computed_jump_p as about the original intent of the 
> code, which was added by Alexandre for SH5:
>   http://gcc.gnu.org/ml/gcc-patches/2005-10/msg00176.html
>
>> My patch fixes the same bug by making sure that we only attach
>> a REG_LABEL note to jumps that already have a known target.
>
> But what's the point in attaching a REG_LABEL note if JUMP_LABEL already 
> points to the same label?  My understanding is that Alexandre's change was 
> meant to add the note on jumps without JUMP_LABEL.

Because (a) reload can turn a direct jump into an indirect jump with
a known target and (b) JUMP_LABEL should always be recomputable from
other information (as done by rebuild_jump_labels).  Without the note,
later passes would not be able to recompute the correct JUMP_LABEL.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Eric Botcazou]

> Because (a) reload can turn a direct jump into an indirect jump with
> a known target and (b) JUMP_LABEL should always be recomputable from
> other information (as done by rebuild_jump_labels).  Without the note,
> later passes would not be able to recompute the correct JUMP_LABEL.

Agreed.  But what about jumps without JUMP_LABEL?  Your patch will change the 
behavior for them.

-- 
Eric Botcazou

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> Because (a) reload can turn a direct jump into an indirect jump with
>> a known target and (b) JUMP_LABEL should always be recomputable from
>> other information (as done by rebuild_jump_labels).  Without the note,
>> later passes would not be able to recompute the correct JUMP_LABEL.
>
> Agreed.  But what about jumps without JUMP_LABEL?  Your patch will
> change the behavior for them.

But that's the whole idea.  There should be no cases in which register
allocation (viewed as a black box) changes the JUMP_LABEL.  The only
reason we have this code is that, because of the direct->indirect change,
we can have insns whose patterns explicitly refer to the JUMP_LABEL
before reload but don't after it.  We then need to add a note so that
the insn still references the JUMP_LABEL in some form.

I'm struggling to understand what your objection is.  Could you give
me an example of the type of jump you think will be mishandled?
E.g. are you thinking of direct jumps, indirect jumps to known targets,
computed jumps, table jumps, or nonlocal jumps?

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Eric Botcazou]

> But that's the whole idea.  There should be no cases in which register
> allocation (viewed as a black box) changes the JUMP_LABEL.

What do you mean by 'should'?  'Cannot but I'm not sure', 'Cannot modulo 
bugs'?  Because Andrew's change precisely does that and was OKed by RTH.

> I'm struggling to understand what your objection is.

My objection is that your patch is not the minimal one to fix the problem.
More specifically, I don't see the need for changing the code when the jump 
has no JUMP_LABEL.

-- 
Eric Botcazou

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> But that's the whole idea.  There should be no cases in which register
>> allocation (viewed as a black box) changes the JUMP_LABEL.
>
> What do you mean by 'should'?  'Cannot but I'm not sure', 'Cannot modulo 
> bugs'?  Because Andrew's change precisely does that and was OKed by RTH.

Cannot modulo bugs.  I've already explained why I think my patch solves
Andrew's bug too.  It sounds like you think I'm reverting to the situation
before Andrew's patch, but I'm not really.  Before Andrew's patch, we dealt
incorrectly with the case where the JUMP_LABEL is not the LABEL_REF we're
replacing:

  (a) If the JUMP_LABEL was null, we could turn a computed jump into
      something that neither a computed jump (because of the REG_LABEL
      note) nor an indirect jump with a known target (because of the
      null JUMP_LABEL).  This led to an ICE in cfgbuild.

      For avoidance of doubt, this case arose when we had a computed
      jump whose target didn't get allocated a hard register, but that
      was known to be equivalent to a LABEL_REF.  We'd replace the
      target with the LABEL_REF and reload it, and we'd then hit this
      REG_LABEL code when replacing the LABEL_REF with the reload register.

  (b) If the JUMP_LABEL was some other label, we'd make the JUMP_LABEL
      inconsistent with the REG_LABEL, thus potentially changing the
      JUMP_LABEL when rebuild_jump_labels is next called.

So Andrew's patch and mine are dealing with the same case: where the
LABEL_REF we're replacing is not the JUMP_LABEL.  Andrew's PR was an
example of (a) and mine is an example of (b).  Andrew's patch fixed
(a) by making the LABEL_REF the JUMP_LABEL too, thus transforming a
computed jump into an indirect jump with a known target.  My patch
fixes (a) by stopping us from adding the note in that case, so that
the jump in Andrew's PR remains a computed jump.  As I said before,
transforming a computed jump into an indirect jump to a known target,
as Andrew did, is a nice CFG optimisation, but not one we should do here.
It certainly shouldn't be conditional on the register allocators failing
to find a home for the jump target register (as was the case in Andrew's PR).

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Richard Sandiford <rsandifo@nildram.co.uk> writes:
> Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>>> But that's the whole idea.  There should be no cases in which register
>>> allocation (viewed as a black box) changes the JUMP_LABEL.
>>
>> What do you mean by 'should'?  'Cannot but I'm not sure', 'Cannot modulo 
>> bugs'?  Because Andrew's change precisely does that and was OKed by RTH.
>
> Cannot modulo bugs.  I've already explained why I think my patch solves
> Andrew's bug too.  It sounds like you think I'm reverting to the situation
> before Andrew's patch, but I'm not really.  Before Andrew's patch, we dealt
> incorrectly with the case where the JUMP_LABEL is not the LABEL_REF we're
> replacing:
>
>   (a) If the JUMP_LABEL was null, we could turn a computed jump into
>       something that neither a computed jump (because of the REG_LABEL
>       note) nor an indirect jump with a known target (because of the
>       null JUMP_LABEL).  This led to an ICE in cfgbuild.
>
>       For avoidance of doubt, this case arose when we had a computed
>       jump whose target didn't get allocated a hard register, but that
>       was known to be equivalent to a LABEL_REF.  We'd replace the
>       target with the LABEL_REF and reload it, and we'd then hit this
>       REG_LABEL code when replacing the LABEL_REF with the reload register.
>
>   (b) If the JUMP_LABEL was some other label, we'd make the JUMP_LABEL
>       inconsistent with the REG_LABEL, thus potentially changing the
>       JUMP_LABEL when rebuild_jump_labels is next called.
>
> So Andrew's patch and mine are dealing with the same case: where the
> LABEL_REF we're replacing is not the JUMP_LABEL.  Andrew's PR was an
> example of (a) and mine is an example of (b).  Andrew's patch fixed
> (a) by making the LABEL_REF the JUMP_LABEL too, thus transforming a
> computed jump into an indirect jump with a known target.  My patch
> fixes (a) by stopping us from adding the note in that case, so that
> the jump in Andrew's PR remains a computed jump.  As I said before,
> transforming a computed jump into an indirect jump to a known target,
> as Andrew did, is a nice CFG optimisation, but not one we should do here.
> It certainly shouldn't be conditional on the register allocators failing
> to find a home for the jump target register (as was the case in Andrew's PR).

BTW, I understand that you want to be conservative here.  It's just that,
from my perspective, keeping the same JUMP_LABEL is more defensive than
changing it.  We're doing no analysis of the instruction pattern here,
so we seem to be changing the JUMP_LABEL on very flimsy evidence.
And, as this PR shows, changing the JUMP_LABEL to an incorrect value
can lead to wrong code.  I think it is much safer to assume that the
pre-reload code has got the JUMP_LABEL right and that reload's job is
simply to preserve this information.  (And from my reading, that's what
the original REG_LABEL code was trying to do.)

The only motivating case we have for changing the JUMP_LABEL is the one
in Andrew's PR, and if we agree that my patch also fixes that case (in
an arguably more conservative way, because it doesn't change the CFG),
then we have no motivating example left.  If your concern is that there
might be examples we haven't considered, either in the discussion of
this patch or of Andrew's, then like I say, I'd argue that keeping the
same JUMP_LABEL is more defensive than changing it.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Eric Botcazou]

> Cannot modulo bugs.  I've already explained why I think my patch solves
> Andrew's bug too.  It sounds like you think I'm reverting to the situation
> before Andrew's patch, but I'm not really. 

No, I think that (because of bugs) you could be reverting to the situation 
before Alexandre's patch.

> So Andrew's patch and mine are dealing with the same case: where the
> LABEL_REF we're replacing is not the JUMP_LABEL.  Andrew's PR was an
> example of (a) and mine is an example of (b).  Andrew's patch fixed
> (a) by making the LABEL_REF the JUMP_LABEL too, thus transforming a
> computed jump into an indirect jump with a known target.  My patch
> fixes (a) by stopping us from adding the note in that case, so that
> the jump in Andrew's PR remains a computed jump. 

I agree with this.

> As I said before, transforming a computed jump into an indirect jump to a
> known target, as Andrew did, is a nice CFG optimisation, but not one we
> should do here. 

OK, but I fear that you could be throwing the baby (a needed note) with the 
bathwater (the new JUMP_LABEL).

Sorry, I don't seem to be able to make up my mind about this affair or clearly 
formulate what I'm afraid of.  The thing is, it's reload and I'll never feel 
comfortable with patching it on a release branch.  So I'd suggest to run this 
by some other maintainer (RTH?), setting aside the current thread.

-- 
Eric Botcazou

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Eric Botcazou <ebotcazou@libertysurf.fr> writes:
> Sorry, I don't seem to be able to make up my mind about this affair or
> clearly formulate what I'm afraid of.  The thing is, it's reload and
> I'll never feel comfortable with patching it on a release branch.  So
> I'd suggest to run this by some other maintainer (RTH?), setting aside
> the current thread.

Understood, thanks.  I'll probably wait a few days to see if anyone
volunteers before I pick a victim.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Eric Botcazou]

> Understood, thanks.  I'll probably wait a few days to see if anyone
> volunteers before I pick a victim.

OK.  Thanks for having very clearly explained your position.

-- 
Eric Botcazou

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Mark Mitchell]

Richard Sandiford wrote:
> Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> Sorry, I don't seem to be able to make up my mind about this affair or
>> clearly formulate what I'm afraid of.  The thing is, it's reload and
>> I'll never feel comfortable with patching it on a release branch.  So
>> I'd suggest to run this by some other maintainer (RTH?), setting aside
>> the current thread.
> 
> Understood, thanks.  I'll probably wait a few days to see if anyone
> volunteers before I pick a victim.

Let me know if you need help finding a victim.  I will try to help,
either by reviewing the change, or by helping you to bully someone else
into doing it.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Mark Mitchell <mark@codesourcery.com> writes:
> Richard Sandiford wrote:
>> Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>>> Sorry, I don't seem to be able to make up my mind about this affair or
>>> clearly formulate what I'm afraid of.  The thing is, it's reload and
>>> I'll never feel comfortable with patching it on a release branch.  So
>>> I'd suggest to run this by some other maintainer (RTH?), setting aside
>>> the current thread.
>> 
>> Understood, thanks.  I'll probably wait a few days to see if anyone
>> volunteers before I pick a victim.
>
> Let me know if you need help finding a victim.  I will try to help,
> either by reviewing the change, or by helping you to bully someone else
> into doing it.

Thanks.  I've drawn a blank so far, so if you could do that,
that'd be great.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Ulrich Weigand]

Richard Sandiford wrote:
> Eric Botcazou <ebotcazou@libertysurf.fr> writes:
> > Sorry, I don't seem to be able to make up my mind about this affair or
> > clearly formulate what I'm afraid of.  The thing is, it's reload and
> > I'll never feel comfortable with patching it on a release branch.  So
> > I'd suggest to run this by some other maintainer (RTH?), setting aside
> > the current thread.
> 
> Understood, thanks.  I'll probably wait a few days to see if anyone
> volunteers before I pick a victim.

Richard asked me to have at look at this issue.  Unfortunately, I don't
see any real solution either (except back-porting the full H-P patch).

Looking at the problem from the perspective of finding the most
conservative change, I can see a number of things we should clearly
*not* do:

- Change a non-NULL JUMP_LABEL to something else.
  (Reload must never actually change control flow.)

- Create a jump_insn with REG_LABEL but NULL JUMP_LABEL.
  (This is inconsistent, as Richard points out.)

- More generally, create an insn that a future run of
  rebuild_jump_labels would modify.

But we also should not simply remove an explicit reference to
a label *without* adding a REG_LABEL note, as this could screw
up reference counting on the label and potentially cause it to
be deleted (even though it is still referenced) -- e.g. if the
label has been pushed into the literal pool.


So, ideally, I think we should add the REG_LABEL note and then
recompute the JUMP_LABEL field just like a future run of
rebuild_jump_labels would do.

Now, what value would a future run of rebuild_jump_label create?
Either the label we just added as REG_LABEL, or some other label
(certainly never NULL).  The only reason we might get some other
label is if that label is already mentioned in the insn.  In that
case, we should have already seen a non-NULL JUMP_LABEL prior to 
reload, and reload should not change it.

(However, in the situation where we have a label in the insn that
we are replacing, we should in fact *never* have a non-NULL
JUMP_LABEL -- but apparently we do sometimes ...)


Getting back to the question of what the most conservative fix
for the branch would be, I therefore think it should be something
along the lines of:
- continue to always add the REG_LABEL if we replace a label
- continue to change a NULL JUMP_LABEL to the replaced label
- do *not* change any pre-existing non-NULL JUMP_LABEL

This change should fix the regression in 33848, and it should not
make any other case worse -- it will only change the behaviour of
reload in cases are are obviously broken today ...

Any comments?   Am I overlooking something here?

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  GNU Toolchain for Linux on System z and Cell BE
  Ulrich.Weigand@de.ibm.com

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

Thanks for looking at this.  (Sorry Mark: my message and Ulrich's crossed.)

"Ulrich Weigand" <uweigand@de.ibm.com> writes:
> Richard Sandiford wrote:
>> Eric Botcazou <ebotcazou@libertysurf.fr> writes:
>> > Sorry, I don't seem to be able to make up my mind about this affair or
>> > clearly formulate what I'm afraid of.  The thing is, it's reload and
>> > I'll never feel comfortable with patching it on a release branch.  So
>> > I'd suggest to run this by some other maintainer (RTH?), setting aside
>> > the current thread.
>> 
>> Understood, thanks.  I'll probably wait a few days to see if anyone
>> volunteers before I pick a victim.
>
> Richard asked me to have at look at this issue.  Unfortunately, I don't
> see any real solution either (except back-porting the full H-P patch).
>
> Looking at the problem from the perspective of finding the most
> conservative change, I can see a number of things we should clearly
> *not* do:
>
> - Change a non-NULL JUMP_LABEL to something else.
>   (Reload must never actually change control flow.)
>
> - Create a jump_insn with REG_LABEL but NULL JUMP_LABEL.
>   (This is inconsistent, as Richard points out.)
>
> - More generally, create an insn that a future run of
>   rebuild_jump_labels would modify.
>
> But we also should not simply remove an explicit reference to
> a label *without* adding a REG_LABEL note, as this could screw
> up reference counting on the label and potentially cause it to
> be deleted (even though it is still referenced) -- e.g. if the
> label has been pushed into the literal pool.

I don't think this can happen.  The LABEL_N_USES count isn't affected
by reload's substitution, so that count should stay accurate until
the next call to rebuild_jump_labels.  Before that call, we should
never (modulo bugs) reach a situation in which LABEL_N_USES becomes
zero and in which this insn still needs it.

rebuid_jump_labels deletes all existing non-jump REG_LABELs and rebuilds
them from scratch.  It also recalculates LABEL_N_USES from scratch.
It never looks at pre-existing REG_LABEL notes when recalculating
the new value of LABEL_N_USES.  Instead, it relies on every label
reference being in the insn patterns in some form, either directly,
or through a literal pool access (which it then dereferences).

So in the particular example you give, we would reference-count
the label by looking through the literal pool MEM, and this would
be unaffected by any REG_LABEL note.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Ulrich Weigand]

Richard Sandiford wrote:

> "Ulrich Weigand" <uweigand@de.ibm.com> writes:
> > But we also should not simply remove an explicit reference to
> > a label *without* adding a REG_LABEL note, as this could screw
> > up reference counting on the label and potentially cause it to
> > be deleted (even though it is still referenced) -- e.g. if the
> > label has been pushed into the literal pool.
> 
> I don't think this can happen.  The LABEL_N_USES count isn't affected
> by reload's substitution, so that count should stay accurate until
> the next call to rebuild_jump_labels.  Before that call, we should
> never (modulo bugs) reach a situation in which LABEL_N_USES becomes
> zero and in which this insn still needs it.

Hmm, you're right; the count cannot reach zero when it shouldn't.
However, the reverse can occur: if delete_insn is called on that
insn after it was modified by reload, LABEL_N_USES will *not* be
decremented, even though it should have been, and thus the label
might not get removed even though it should be ...

This doesn't seem as serious as the reverse problem; but I think
we've seen actual bugs in the past due to labels that were not
deleted.

In any case, it just seems more conservative to me to add the note.
It keeps holding the (existing) LABEL_N_USES count; and it is what
the code is currently doing.

I'm not sure I've really understood why you're opposed to adding the
note; would you mind explaining again what your concerns are?

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  GNU Toolchain for Linux on System z and Cell BE
  Ulrich.Weigand@de.ibm.com

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

"Ulrich Weigand" <uweigand@de.ibm.com> writes:
> Richard Sandiford wrote:
>> "Ulrich Weigand" <uweigand@de.ibm.com> writes:
>> > But we also should not simply remove an explicit reference to
>> > a label *without* adding a REG_LABEL note, as this could screw
>> > up reference counting on the label and potentially cause it to
>> > be deleted (even though it is still referenced) -- e.g. if the
>> > label has been pushed into the literal pool.
>> 
>> I don't think this can happen.  The LABEL_N_USES count isn't affected
>> by reload's substitution, so that count should stay accurate until
>> the next call to rebuild_jump_labels.  Before that call, we should
>> never (modulo bugs) reach a situation in which LABEL_N_USES becomes
>> zero and in which this insn still needs it.
>
> Hmm, you're right; the count cannot reach zero when it shouldn't.
> However, the reverse can occur: if delete_insn is called on that
> insn after it was modified by reload, LABEL_N_USES will *not* be
> decremented, even though it should have been, and thus the label
> might not get removed even though it should be ...
>
> This doesn't seem as serious as the reverse problem; but I think
> we've seen actual bugs in the past due to labels that were not
> deleted.

I don't think adding a REG_LABEL note would make any difference as
far as that's concerned either, at least not in the situations we
care about.  Looking at the only deletion routines that handle
REG_LABEL notes:

- cfgrtl.c:delete_insn

  Doesn't consider notes if the jump has a JUMP_LABEL, and we're only
  considering cases where the jump _does_ have a jump label:

  /* If deleting a jump, decrement the use count of the label.  Deleting
     the label itself should happen in the normal course of block merging.  */
  if (JUMP_P (insn)
      && JUMP_LABEL (insn)
      && LABEL_P (JUMP_LABEL (insn)))
    LABEL_NUSES (JUMP_LABEL (insn))--;

  /* Also if deleting an insn that references a label.  */
  else
    {
      while ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
	     && LABEL_P (XEXP (note, 0)))
	{
	  LABEL_NUSES (XEXP (note, 0))--;
	  remove_note (insn, note);

	}
    }

- flow.c:propagate_block_delete_insn

  Not used for jumps; insn_dead_p doesn't (and shouldn't!) consider sets
  of (pc) to be dead.

- jump.c:delete_related_insns

  The REG_LABEL code isn't executed for jumps:

  /* Likewise for an ordinary INSN / CALL_INSN with a REG_LABEL note.  */
  if (NONJUMP_INSN_P (insn) || CALL_P (insn))
    for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
      if (REG_NOTE_KIND (note) == REG_LABEL
	  /* This could also be a NOTE_INSN_DELETED_LABEL note.  */
	  && LABEL_P (XEXP (note, 0)))
	if (LABEL_NUSES (XEXP (note, 0)) == 0)
	  delete_related_insns (XEXP (note, 0));

> In any case, it just seems more conservative to me to add the note.
> It keeps holding the (existing) LABEL_N_USES count; and it is what
> the code is currently doing.
>
> I'm not sure I've really understood why you're opposed to adding the
> note; would you mind explaining again what your concerns are?

Because it would then have a dual meaning, which is exactly the problem
that H-P was fixing.  H-P's motivating example was a cbranch insn with a
target label operand and a non-target label operand; i.e. one where the
JUMP_LABEL is evident from the jump pattern itself:

    http://gcc.gnu.org/ml/gcc/2005-12/msg00279.html

I'm very reluctant to believe that the 4.2 infrastructure handles this
situation correctly.

As I see it, 4.2 effectively uses label notes on jumps only for encoding
the target, so adding a note for something that isn't the target seems
inherently dangerous.  It's what bit us in this PR.  I'm afraid that
if we keep the note in any other case, we won't actually have a good
theoretical bases for doing it, and the same sort of bug could resurface
in other situations.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Ulrich Weigand]

Richard Sandiford wrote:

> I don't think adding a REG_LABEL note would make any difference as
> far as that's concerned either, at least not in the situations we
> care about.

Hmmm, right.  I think that means refcounting is probably wrong, but
it would be wrong no matter whether we add the REG_LABEL or not ...

OK, I guess you've convinced me that the presence or absence of a
REG_LABEL note on a jump with JUMP_LABEL only ever affects the return
value of computed_jump_p on that insn.

(There is one remaining use of REG_LABEL that I'm not 100% certain of,
and that is the one in reorg.c:emit_delay_sequence.  I think jumps 
like that probably are not eligible to be in delay slots, but I'm
not completely certain about that ...)

> As I see it, 4.2 effectively uses label notes on jumps only for encoding
> the target, so adding a note for something that isn't the target seems
> inherently dangerous.  It's what bit us in this PR.  I'm afraid that
> if we keep the note in any other case, we won't actually have a good
> theoretical bases for doing it, and the same sort of bug could resurface
> in other situations.

Right.  If computed_jump_p is indeed the only difference, I agree it
would be more conservative to *not* add the REG_LABEL; better if the
jump is considered computed even though it always goes to the same
target, than if the jump is considered to have a target that might
actually be incorrect.

Thanks for your explanations; the patch looks OK to me now.

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  GNU Toolchain for Linux on System z and Cell BE
  Ulrich.Weigand@de.ibm.com

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

"Ulrich Weigand" <uweigand@de.ibm.com> writes:
> Richard Sandiford wrote:
>> I don't think adding a REG_LABEL note would make any difference as
>> far as that's concerned either, at least not in the situations we
>> care about.
>
> Hmmm, right.  I think that means refcounting is probably wrong, but
> it would be wrong no matter whether we add the REG_LABEL or not ...
>
> OK, I guess you've convinced me that the presence or absence of a
> REG_LABEL note on a jump with JUMP_LABEL only ever affects the return
> value of computed_jump_p on that insn.
>
> (There is one remaining use of REG_LABEL that I'm not 100% certain of,
> and that is the one in reorg.c:emit_delay_sequence.  I think jumps 
> like that probably are not eligible to be in delay slots, but I'm
> not completely certain about that ...)

I'm not completely certain whether jumps like that can appear or
not either, but I don't think it matters.  The code you mention is
incrementing the label count in cases where we've copied an insn.
If that insn is the type of jump we're considering, we already know
that the deletion routines will not decrement the label count for
REG_LABEL notes.  So if a label is referenced in the way we're
considering, the count can never become zero before the next call
to rebuild_jump_labels.

Likewise, while the label is also the target of another jump,
the count can never become 1 before the next call to rebuild_jump_labels.
Checks of the form "LABEL_NUSES (JUMP_LABEL (foo)) == 1" will therefore
always be false.

Is that convincing enough?  I.e. does...

> Thanks for your explanations; the patch looks OK to me now.

...this still hold?

(I'm not guaranteeing that this isn't going to tickle latent problems.
I'm just arguing that it's more conservative than the alternative.)

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Ulrich Weigand]

Richard Sandiford wrote:
> "Ulrich Weigand" <uweigand@de.ibm.com> writes:
> > Richard Sandiford wrote:
> >> I don't think adding a REG_LABEL note would make any difference as
> >> far as that's concerned either, at least not in the situations we
> >> care about.
> >
> > Hmmm, right.  I think that means refcounting is probably wrong, but
> > it would be wrong no matter whether we add the REG_LABEL or not ...
> >
> > OK, I guess you've convinced me that the presence or absence of a
> > REG_LABEL note on a jump with JUMP_LABEL only ever affects the return
> > value of computed_jump_p on that insn.
> >
> > (There is one remaining use of REG_LABEL that I'm not 100% certain of,
> > and that is the one in reorg.c:emit_delay_sequence.  I think jumps 
> > like that probably are not eligible to be in delay slots, but I'm
> > not completely certain about that ...)
> 
> I'm not completely certain whether jumps like that can appear or
> not either, but I don't think it matters.  The code you mention is
> incrementing the label count in cases where we've copied an insn.
> If that insn is the type of jump we're considering, we already know
> that the deletion routines will not decrement the label count for
> REG_LABEL notes.  So if a label is referenced in the way we're
> considering, the count can never become zero before the next call
> to rebuild_jump_labels.
> 
> Likewise, while the label is also the target of another jump,
> the count can never become 1 before the next call to rebuild_jump_labels.
> Checks of the form "LABEL_NUSES (JUMP_LABEL (foo)) == 1" will therefore
> always be false.

OK, I see.

> Is that convincing enough?  I.e. does...
> 
> > Thanks for your explanations; the patch looks OK to me now.
> 
> ...this still hold?

Yes, it does.   The patch is OK.


Thanks,
Ulrich

-- 
  Dr. Ulrich Weigand
  GNU Toolchain for Linux on System z and Cell BE
  Ulrich.Weigand@de.ibm.com

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

"Ulrich Weigand" <uweigand@de.ibm.com> writes:
>> Is that convincing enough?  I.e. does...
>> 
>> > Thanks for your explanations; the patch looks OK to me now.
>> 
>> ...this still hold?
>
> Yes, it does.   The patch is OK.

Thanks, now applied.  And thanks again for working through this.

Richard

Re: [4.2 only] RFA: PR 33848: reload rematerialisation of labels

[Richard Sandiford]

"Ulrich Weigand" <uweigand@de.ibm.com> writes:
>> Is that convincing enough?  I.e. does...
>> 
>> > Thanks for your explanations; the patch looks OK to me now.
>> 
>> ...this still hold?
>
> Yes, it does.   The patch is OK.

Thanks, now applied.  And thanks again for working through this.

Richard