Message ID | CABu31nP0JxH5LgwpjkobK1Ns-mfShghciayacWeXsuTEDbDzmw@mail.gmail.com |
---|---|
State | New |
Headers | show |
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
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)