reorg.c janitor patch 3: remove rare_destination()

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

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

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

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

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