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
