Patchwork reorg.c janitor patch 3: remove rare_destination()

login
register
mail settings
Submitter Steven Bosscher
Date Nov. 25, 2012, 1:44 p.m.
Message ID <CABu31nP0JxH5LgwpjkobK1Ns-mfShghciayacWeXsuTEDbDzmw@mail.gmail.com>
Download mbox | patch
Permalink /patch/201545/
State New
Headers show

Comments

Steven Bosscher - Nov. 25, 2012, 1:44 p.m.
Hello,

reorg.c:rare_destination() tries to determine whether a given insn is
a likely destination of a branch. To make this determination, it walks
the insns chain from insn and stops at barriers, labels, return insns,
or if more than 10 jumps have been followed.

The function is supposed to return 2 for noreturn calls, 1 for return,
and 0 otherwise. But a quick experiment shows that the function
doesn't work that way at all:

1. for all non-label, non-jump, non-barrier insns the function reaches
the default case of the loop, which results in "return 1".

2. for labels, the function returns 0.

3. for most jump insns, the function returns 0, predicting
jumps-to-jumps as likely -- but cfgcleanup has almost always already
cleaned up such cases and the remaining jumps-to-jumps are usually not
likely.

4. The combination of the above 3 points results in the fall-through
path being predicted as a rare destination and the branch path as a
more likely destination. It should be the other way around, if basic
block reordering has done its job properly.

5. the only case that does work is the no-return call case, where the
function stops at a BARRIER which must be for a no-return call because
the function doesn't scan past jump insn (it follows jumps instead).
However, this case is already handled in mostly_true_jump when it
looks at REG_BR_PROB (which is a more reliable source of branch
probabilities for all other cases as well).


Given its apparent broken state and the better results reorg almost
always gets in mostly_true_jump() from REG_BR_PROB or from determining
that a jump goes forward or backward, I propose to remove
rare_destination().

Built&tested a cross to mips-elf. OK for trunk?

Ciao!
Steven
Richard Sandiford - Nov. 25, 2012, 5:13 p.m.
Steven Bosscher <stevenb.gcc@gmail.com> writes:
> Hello,
>
> reorg.c:rare_destination() tries to determine whether a given insn is
> a likely destination of a branch. To make this determination, it walks
> the insns chain from insn and stops at barriers, labels, return insns,
> or if more than 10 jumps have been followed.
>
> The function is supposed to return 2 for noreturn calls, 1 for return,
> and 0 otherwise. But a quick experiment shows that the function
> doesn't work that way at all:
>
> 1. for all non-label, non-jump, non-barrier insns the function reaches
> the default case of the loop, which results in "return 1".

I might be misunderstanding what you mean, but the structure is:

  for (; insn && !ANY_RETURN_P (insn); insn = next)
    {
      ...
      next = NEXT_INSN (insn);
      switch (GET_CODE (insn))
	{
        ...
	default:
	  break;
	}
    }

So we skip those instructions and go on to the next.  The function
doesn't look quite as broken as all that.

Still, I agree that returning 0 for all conditional jumps is a pretty
big hole that could make them seem more likely than they should:

> 4. The combination of the above 3 points results in the fall-through
> path being predicted as a rare destination and the branch path as a
> more likely destination. It should be the other way around, if basic
> block reordering has done its job properly.

and that REG_BB_PROB should be a more reliable indicator:

> 5. the only case that does work is the no-return call case, where the
> function stops at a BARRIER which must be for a no-return call because
> the function doesn't scan past jump insn (it follows jumps instead).
> However, this case is already handled in mostly_true_jump when it
> looks at REG_BR_PROB (which is a more reliable source of branch
> probabilities for all other cases as well).

But removing the function seems to put more weight on:

  /* Predict backward branches usually take, forward branches usually not.  If
     we don't know whether this is forward or backward, assume the branch
     will be taken, since most are.  */

which doesn't seem any more reliable.  I think your point is that we
should assume most branches _aren't_ taken.

Thanks,
Richard
Steven Bosscher - Nov. 25, 2012, 5:42 p.m.
On Sun, Nov 25, 2012 at 6:13 PM, Richard Sandiford wrote:
> Steven Bosscher writes:
>> Hello,
>>
>> reorg.c:rare_destination() tries to determine whether a given insn is
>> a likely destination of a branch. To make this determination, it walks
>> the insns chain from insn and stops at barriers, labels, return insns,
>> or if more than 10 jumps have been followed.
>>
>> The function is supposed to return 2 for noreturn calls, 1 for return,
>> and 0 otherwise. But a quick experiment shows that the function
>> doesn't work that way at all:
>>
>> 1. for all non-label, non-jump, non-barrier insns the function reaches
>> the default case of the loop, which results in "return 1".
>
> I might be misunderstanding what you mean, but the structure is:
>
>   for (; insn && !ANY_RETURN_P (insn); insn = next)
>     {
>       ...
>       next = NEXT_INSN (insn);
>       switch (GET_CODE (insn))
>         {
>         ...
>         default:
>           break;
>         }
>     }
>
> So we skip those instructions and go on to the next.  The function
> doesn't look quite as broken as all that.

Right, I mis-read the break as exiting the for-loop, but of course it
only exists the switch.


> Still, I agree that returning 0 for all conditional jumps is a pretty
> big hole that could make them seem more likely than they should:
>
>> 4. The combination of the above 3 points results in the fall-through
>> path being predicted as a rare destination and the branch path as a
>> more likely destination. It should be the other way around, if basic
>> block reordering has done its job properly.
>
> and that REG_BB_PROB should be a more reliable indicator:
>
>> 5. the only case that does work is the no-return call case, where the
>> function stops at a BARRIER which must be for a no-return call because
>> the function doesn't scan past jump insn (it follows jumps instead).
>> However, this case is already handled in mostly_true_jump when it
>> looks at REG_BR_PROB (which is a more reliable source of branch
>> probabilities for all other cases as well).
>
> But removing the function seems to put more weight on:
>
>   /* Predict backward branches usually take, forward branches usually not.  If
>      we don't know whether this is forward or backward, assume the branch
>      will be taken, since most are.  */
>
> which doesn't seem any more reliable.
>
>  I think your point is that we
> should assume most branches _aren't_ taken.

That's the assumption I'm making, yes. The way basic block reordering
works, is to try and make the most likely trace consist of
fall-through paths.

FWIW, the vast majority of condjumps have a REG_BR_PROB note so the
part of mostly_true_jump that handles the jumps without a REG_BR_PROB
note is itself a rare_destination :-) GCC is very careful about
preserving the notes. Perhaps all that code should just be removed.

Ciao!
Steven
Richard Sandiford - Nov. 25, 2012, 6:30 p.m.
Steven Bosscher <stevenb.gcc@gmail.com> writes:
> On Sun, Nov 25, 2012 at 6:13 PM, Richard Sandiford wrote:
>> Steven Bosscher writes:
>>> Hello,
>>>
>>> reorg.c:rare_destination() tries to determine whether a given insn is
>>> a likely destination of a branch. To make this determination, it walks
>>> the insns chain from insn and stops at barriers, labels, return insns,
>>> or if more than 10 jumps have been followed.
>>>
>>> The function is supposed to return 2 for noreturn calls, 1 for return,
>>> and 0 otherwise. But a quick experiment shows that the function
>>> doesn't work that way at all:
>>>
>>> 1. for all non-label, non-jump, non-barrier insns the function reaches
>>> the default case of the loop, which results in "return 1".
>>
>> I might be misunderstanding what you mean, but the structure is:
>>
>>   for (; insn && !ANY_RETURN_P (insn); insn = next)
>>     {
>>       ...
>>       next = NEXT_INSN (insn);
>>       switch (GET_CODE (insn))
>>         {
>>         ...
>>         default:
>>           break;
>>         }
>>     }
>>
>> So we skip those instructions and go on to the next.  The function
>> doesn't look quite as broken as all that.
>
> Right, I mis-read the break as exiting the for-loop, but of course it
> only exists the switch.
>
>
>> Still, I agree that returning 0 for all conditional jumps is a pretty
>> big hole that could make them seem more likely than they should:
>>
>>> 4. The combination of the above 3 points results in the fall-through
>>> path being predicted as a rare destination and the branch path as a
>>> more likely destination. It should be the other way around, if basic
>>> block reordering has done its job properly.
>>
>> and that REG_BB_PROB should be a more reliable indicator:
>>
>>> 5. the only case that does work is the no-return call case, where the
>>> function stops at a BARRIER which must be for a no-return call because
>>> the function doesn't scan past jump insn (it follows jumps instead).
>>> However, this case is already handled in mostly_true_jump when it
>>> looks at REG_BR_PROB (which is a more reliable source of branch
>>> probabilities for all other cases as well).
>>
>> But removing the function seems to put more weight on:
>>
>>   /* Predict backward branches usually take, forward branches usually not.  If
>>      we don't know whether this is forward or backward, assume the branch
>>      will be taken, since most are.  */
>>
>> which doesn't seem any more reliable.
>>
>>  I think your point is that we
>> should assume most branches _aren't_ taken.
>
> That's the assumption I'm making, yes. The way basic block reordering
> works, is to try and make the most likely trace consist of
> fall-through paths.
>
> FWIW, the vast majority of condjumps have a REG_BR_PROB note so the
> part of mostly_true_jump that handles the jumps without a REG_BR_PROB
> note is itself a rare_destination :-) GCC is very careful about
> preserving the notes. Perhaps all that code should just be removed.

Yeah, just returning 0 if there's no note sounds good.  Preapproved if
noone objects in 24 hours.

Thanks,
Richard
Jeff Law - Nov. 26, 2012, 1:56 p.m.
On 11/25/2012 11:30 AM, Richard Sandiford wrote:
>> FWIW, the vast majority of condjumps have a REG_BR_PROB note so the
>> part of mostly_true_jump that handles the jumps without a REG_BR_PROB
>> note is itself a rare_destination :-) GCC is very careful about
>> preserving the notes. Perhaps all that code should just be removed.
>
> Yeah, just returning 0 if there's no note sounds good.  Preapproved if
> noone objects in 24 hours.
Fine with me -- all the branch prediction code in reorg.c pre-dates the 
branch prediction notes and information we carry around these days.

I wouldn't lose any sleep if all the reorg.c bits were converted to use 
the existing notes and the now redundant bits removed.

jeff

Patch

Index: reorg.c
===================================================================
--- reorg.c	(revision 193787)
+++ reorg.c	(working copy)
@@ -187,7 +187,6 @@  static void note_delay_statistics (int, int);
 static rtx optimize_skip (rtx);
 #endif
 static int get_jump_flags (rtx, rtx);
-static int rare_destination (rtx);
 static int mostly_true_jump (rtx, rtx);
 static rtx get_branch_condition (rtx, rtx);
 static int condition_dominates_p (rtx, rtx);
@@ -905,54 +904,6 @@  get_jump_flags (rtx insn, rtx label)
   return flags;
 }

-/* Return 1 if INSN is a destination that will be branched to rarely (the
-   return point of a function); return 2 if DEST will be branched to very
-   rarely (a call to a function that doesn't return).  Otherwise,
-   return 0.  */
-
-static int
-rare_destination (rtx insn)
-{
-  int jump_count = 0;
-  rtx next;
-
-  for (; insn && !ANY_RETURN_P (insn); insn = next)
-    {
-      if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE)
-	insn = XVECEXP (PATTERN (insn), 0, 0);
-
-      next = NEXT_INSN (insn);
-
-      switch (GET_CODE (insn))
-	{
-	case CODE_LABEL:
-	  return 0;
-	case BARRIER:
-	  /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN.  We
-	     don't scan past JUMP_INSNs, so any barrier we find here must
-	     have been after a CALL_INSN and hence mean the call doesn't
-	     return.  */
-	  return 2;
-	case JUMP_INSN:
-	  if (ANY_RETURN_P (PATTERN (insn)))
-	    return 1;
-	  else if (simplejump_p (insn)
-		   && jump_count++ < 10)
-	    next = JUMP_LABEL (insn);
-	  else
-	    return 0;
-
-	default:
-	  break;
-	}
-    }
-
-  /* If we got here it means we hit the end of the function.  So this
-     is an unlikely destination.  */
-
-  return 1;
-}
-
 /* Return truth value of the statement that this branch
    is mostly taken.  If we think that the branch is extremely likely
    to be taken, we return 2.  If the branch is slightly more likely to be
@@ -966,7 +918,6 @@  mostly_true_jump (rtx jump_insn, rtx condition)
 {
   rtx target_label = JUMP_LABEL (jump_insn);
   rtx note;
-  int rare_dest, rare_fallthrough;

   /* If branch probabilities are available, then use that number since it
      always gives a correct answer.  */
@@ -985,25 +936,6 @@  mostly_true_jump (rtx jump_insn, rtx condition)
 	return -1;
     }

-  /* Look at the relative rarities of the fallthrough and destination.  If
-     they differ, we can predict the branch that way.  */
-  rare_dest = rare_destination (target_label);
-  rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
-
-  switch (rare_fallthrough - rare_dest)
-    {
-    case -2:
-      return -1;
-    case -1:
-      return 0;
-    case 0:
-      break;
-    case 1:
-      return 1;
-    case 2:
-      return 2;
-    }
-
   /* If we couldn't figure out what this jump was, assume it won't be
      taken.  This should be rare.  */
   if (condition == 0)