Patchwork Fix a dbr_schedule vs. delete_related_insns liveness bug

login
register
mail settings
Submitter Richard Sandiford
Date Jan. 15, 2014, 7:27 p.m.
Message ID <87eh49nizr.fsf@talisman.default>
Download mbox | patch
Permalink /patch/311249/
State New
Headers show

Comments

Richard Sandiford - Jan. 15, 2014, 7:27 p.m.
Two patches in a week about dbr_schedule and redundant insns.  This one
fixes a miscompilation of libgcov-driver.c for n32 and n64 MIPS.
It's independent of (and predates) the 59137 patch.

We had:

       barrier
    L1:
C:     $r1 = ...
D:     $r2 = ...
       ...
A:     if ... goto L1
B:     if ... goto L1

where these are the only two uses of L1.  First we filled A's delay slot
with C:

       barrier
    L1:
C:     $r1 = ...
    L2:
D:     $r2 = ...
       ...
A:     if ... goto L2
C':	 $r1 = ...
B:     if ... goto L1

Now B is the only user of L1 so it "owns" the target thread.  When
looking for a delay slot, we realise that C is redundant with C',
so delete it and go on to D.  We call update_block to record the
old C as a (use (insn)):

       barrier
    L1:
C'':   (use ($r1 = ...))
    L2:
D:     $r2 = ...
    L3:
       ...
A:     if ... goto L2
C':	 $r1 = ...
B:     if ... goto L3
D':      $r2 = ...

So far so good.  The problem is that redirecting B to L3 makes L1 unreachable,
so reorg_redirect_jump=>redirect_jump (..., 1)=>delete_related_insns deletes
it.  Then C'' is unreachable and d_r_i deletes that too:

       barrier
    L2:
D:     $r2 = ...
    L3:
       ...
A:     if ... goto L2
C':	 $r1 = ...
B:     if ... goto L3
D':      $r2 = ...

So now, when we try to calculate the liveness beyond D, we go back to the
barrier but have no indication that $r1 is live.

I wondered about several ways of fixing this.

* Back in the day, we just deleted the label and not related instructions.
  I don't think that's something we should return to though.  If we delete
  all uses of:

           barrier
      L1:
           insn
           goto L2

  to get:

           barrier
      L1:
           (use (insn))
           goto L2

  then we should definitely remove the branch to L2.

* Deferring deleting labels until the end of dbr_schedule.  On its own
  this would pessimise the rest of dbr_schedule, e.g. a jump only "owns"
  a thread until the next label.  We would need to spinkle in a few checks
  for the usage count being nonzero.

* Deferring deleting labels that fit the problem pattern.  Having two
  forms of redirect would make things even more complicated though.
  And I don't think it would be robust in cases like the "goto L2" above.
  If we delete a "goto L2" that is the last use of L2, we delete L2 too,
  which in turn could be a label-after-barrier.  So reorg would have to
  predict what the recursive calls to delete_related_insns would do.

* Add the liveness information to the basic block info and let the
  (use (insn))s be deleted.  I started down that path but it soon got
  very convoluted.  Also:

     We used to try to update the live status of registers if WHERE is at
     the start of a basic block, but that can't work since we may remove a
     BARRIER in relax_delay_slots.  */

  suggests that this has already been tried and it wasn't robust.

So in the end I just taught delete_related_insns to keep (use (insn)),
which AFAIK is a pattern that only dbr_schedule could generate.

Tested on mips64-linux-gnu.  OK to install?

Thanks,
Richard


gcc/
	* jump.c (delete_related_insns): Keep (use (insn))s.
	* reorg.c (redundant_insn): Check for barriers too.
Jeff Law - Jan. 15, 2014, 9:31 p.m.
On 01/15/14 12:27, Richard Sandiford wrote:
[ snip ]
>
>         barrier
>      L1:
> C'':   (use ($r1 = ...))
>      L2:
> D:     $r2 = ...
>      L3:
>         ...
> A:     if ... goto L2
> C':	 $r1 = ...
> B:     if ... goto L3
> D':      $r2 = ...
>
> So far so good.  The problem is that redirecting B to L3 makes L1 unreachable,
> so reorg_redirect_jump=>redirect_jump (..., 1)=>delete_related_insns deletes
> it.  Then C'' is unreachable and d_r_i deletes that too:
>
>         barrier
>      L2:
> D:     $r2 = ...
>      L3:
>         ...
> A:     if ... goto L2
> C':	 $r1 = ...
> B:     if ... goto L3
> D':      $r2 = ...
>
> So now, when we try to calculate the liveness beyond D, we go back to the
> barrier but have no indication that $r1 is live.
Ugh.  Every time I ponder the wacko way we get live information in reorg 
I just want to cry.  Thankfully I haven't had to really look at that 
code in over 10 years.

This just reminded me that if Steven goes forward with his "remove 
barriers" proposal post-4.9, reorg will need some surgery.



>
> I wondered about several ways of fixing this.
>
> * Back in the day, we just deleted the label and not related instructions.
>    I don't think that's something we should return to though.  If we delete
>    all uses of:
Certainly wouldn't be my first choice either.

>
> * Deferring deleting labels until the end of dbr_schedule.  On its own
>    this would pessimise the rest of dbr_schedule, e.g. a jump only "owns"
>    a thread until the next label.  We would need to spinkle in a few checks
>    for the usage count being nonzero.
Right.  I don't particularly like this either.  But it's worth 
remembering that if this stuff ultimately gets too painful we can fall 
back to something like this.

>
> * Deferring deleting labels that fit the problem pattern.  Having two
>    forms of redirect would make things even more complicated though.
>    And I don't think it would be robust in cases like the "goto L2" above.
>    If we delete a "goto L2" that is the last use of L2, we delete L2 too,
>    which in turn could be a label-after-barrier.  So reorg would have to
>    predict what the recursive calls to delete_related_insns would do.
Ick.  Don't like this at all.

>
> * Add the liveness information to the basic block info and let the
>    (use (insn))s be deleted.  I started down that path but it soon got
>    very convoluted.  Also:
Yes, keeping live info correct in this code is painful, in large part 
because this code is cfg-unaware and mucks it up in painful ways.

Making the code cfg-aware is probably the first step in really cleaning 
up the mess that is reorg.c.  Once we've got a correct cfg at each 
transformation we can probably tackle liveness.


>
>       We used to try to update the live status of registers if WHERE is at
>       the start of a basic block, but that can't work since we may remove a
>       BARRIER in relax_delay_slots.  */
>
>    suggests that this has already been tried and it wasn't robust.
It would have been pre-cfg as this comment comes from Kenner in '92.

>
> So in the end I just taught delete_related_insns to keep (use (insn)),
> which AFAIK is a pattern that only dbr_schedule could generate.
Seems reasonable given the current state of affairs.  The (use (insn)) 
idiom is only used by reorg to the best of my knowledge.

> Tested on mips64-linux-gnu.  OK to install?
>
> Thanks,
> Richard
>
>
> gcc/
> 	* jump.c (delete_related_insns): Keep (use (insn))s.
> 	* reorg.c (redundant_insn): Check for barriers too.
OK.  Any chance you've got a testcase you can add to the suite?  ISTM 
it's potentially valuable given the plan to remove barriers and the 
implications that has for reorg.c liveness tracking.


jeff
Richard Sandiford - Jan. 18, 2014, 10:12 a.m.
Jeff Law <law@redhat.com> writes:
>> gcc/
>> 	* jump.c (delete_related_insns): Keep (use (insn))s.
>> 	* reorg.c (redundant_insn): Check for barriers too.
> OK.  Any chance you've got a testcase you can add to the suite?  ISTM 
> it's potentially valuable given the plan to remove barriers and the 
> implications that has for reorg.c liveness tracking.

Applied, thanks.  I spent a few hours trying to reduce the testcase
to something that was likely to show the problem reliably, but it looks
like a lot of things have to happen in just the right (or wrong) way.

One of the problems is that if we have:

         barrier
    L1:
         A
         B

and turn it into:

         barrier
    L2:
         B

find_basic_block will not have a basic block for the new label L2
and we won't get a liveness set at all.  So we need a case where we've
cached the find_basic_block result from before the transformation.
This happens in the original testcase because we only introduce the
label during the second reorg pass, but I'm finding it hard to force
cases that can only trigger during the second pass.

The original problem showed up as the tree-prof failures here:

    http://gcc.gnu.org/ml/gcc-testresults/2014-01/msg00633.html

but unfortunately that needs a mips64-linux-gnu rather than gdbsim
environment to reproduce.

Thanks,
Richard
Jeff Law - Jan. 21, 2014, 4:41 p.m.
On 01/18/14 03:12, Richard Sandiford wrote:
> Jeff Law <law@redhat.com> writes:
>>> gcc/
>>> 	* jump.c (delete_related_insns): Keep (use (insn))s.
>>> 	* reorg.c (redundant_insn): Check for barriers too.
>> OK.  Any chance you've got a testcase you can add to the suite?  ISTM
>> it's potentially valuable given the plan to remove barriers and the
>> implications that has for reorg.c liveness tracking.
>
> Applied, thanks.  I spent a few hours trying to reduce the testcase
> to something that was likely to show the problem reliably, but it looks
> like a lot of things have to happen in just the right (or wrong) way.
>
> One of the problems is that if we have:
>
>           barrier
>      L1:
>           A
>           B
>
> and turn it into:
>
>           barrier
>      L2:
>           B
>
> find_basic_block will not have a basic block for the new label L2
> and we won't get a liveness set at all.  So we need a case where we've
> cached the find_basic_block result from before the transformation.
> This happens in the original testcase because we only introduce the
> label during the second reorg pass, but I'm finding it hard to force
> cases that can only trigger during the second pass.
>
> The original problem showed up as the tree-prof failures here:
>
>      http://gcc.gnu.org/ml/gcc-testresults/2014-01/msg00633.html
>
> but unfortunately that needs a mips64-linux-gnu rather than gdbsim
> environment to reproduce.
Thanks for taking the time to try and pull something together.   I've 
certainly got no objections to this going forward without a regression test.

Thanks,
Jeff

Patch

Index: gcc/jump.c
===================================================================
--- gcc/jump.c	2014-01-14 14:40:05.179783568 +0000
+++ gcc/jump.c	2014-01-14 19:10:18.392192242 +0000
@@ -1355,6 +1355,13 @@  delete_related_insns (rtx insn)
 	  /* Keep going past other deleted labels to delete what follows.  */
 	  else if (code == CODE_LABEL && INSN_DELETED_P (next))
 	    next = NEXT_INSN (next);
+	  /* Keep the (use (insn))s created by dbr_schedule, which needs
+	     them in order to track liveness relative to a previous
+	     barrier.  */
+	  else if (INSN_P (next)
+		   && GET_CODE (PATTERN (next)) == USE
+		   && INSN_P (XEXP (PATTERN (next), 0)))
+	    next = NEXT_INSN (next);
 	  else if (code == BARRIER || INSN_P (next))
 	    /* Note: if this deletes a jump, it can cause more
 	       deletion of unreachable code, after a different label.
Index: gcc/reorg.c
===================================================================
--- gcc/reorg.c	2014-01-14 14:40:05.179783568 +0000
+++ gcc/reorg.c	2014-01-14 19:11:49.487961664 +0000
@@ -1512,7 +1512,10 @@  redundant_insn (rtx insn, rtx target, rt
        trial && insns_to_search > 0;
        trial = PREV_INSN (trial))
     {
-      if (LABEL_P (trial))
+      /* (use (insn))s can come immediately after a barrier if the
+	 label that used to precede them has been deleted as dead.
+	 See delete_related_insns.  */
+      if (LABEL_P (trial) || BARRIER_P (trial))
 	return 0;
 
       if (!INSN_P (trial))