This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[RFC] Cleaning up reorg.c's mostly_true_jump
- From: Steven Bosscher <stevenb at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: law at redhat dot com, echristo at apple dot com, hp at axis dot com, Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Date: Mon, 12 Dec 2005 16:46:46 +0100
- Subject: [RFC] Cleaning up reorg.c's mostly_true_jump
Hi,
mostly_true_jump in reorg.c is one of the very few places in GCC where
loop notes and LABEL_OUTSIDE_LOOP_P are still used. I wanted to know
how often these pre-historic artefacts still determine the result of
mostly_true_jump, so I built a HPPA-linux compiler to produce coverage
data and I unleashed this compiler on the complete preprocessed sources
of cc1, compiling the .i files with -O3 -funroll-loops.
Here is the interesting part of the results:
-: 954:/* Return truth value of the statement that this branch
-: 955: is mostly taken. If we think that the branch is extremely likely
-: 956: to be taken, we return 2. If the branch is slightly more likely to be
-: 957: taken, return 1. If the branch is slightly less likely to be taken,
-: 958: return 0 and if the branch is highly unlikely to be taken, return -1.
-: 959:
-: 960: CONDITION, if nonzero, is the condition that JUMP_INSN is testing. */
-: 961:
-: 962:static int
-: 963:mostly_true_jump (rtx jump_insn, rtx condition)
1490768: 964:{
1490768: 965: rtx target_label = JUMP_LABEL (jump_insn);
1490768: 966: rtx insn, note;
1490768: 967: int rare_dest = rare_destination (target_label);
1490768: 968: int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
-: 969:
-: 970: /* If branch probabilities are available, then use that number since it
-: 971: always gives a correct answer. */
1490768: 972: note = find_reg_note (jump_insn, REG_BR_PROB, 0);
1490768: 973: if (note)
-: 974: {
1293034: 975: int prob = INTVAL (XEXP (note, 0));
-: 976:
1293034: 977: if (prob >= REG_BR_PROB_BASE * 9 / 10)
98884: 978: return 2;
1194150: 979: else if (prob >= REG_BR_PROB_BASE / 2)
398763: 980: return 1;
795387: 981: else if (prob >= REG_BR_PROB_BASE / 10)
631387: 982: return 0;
-: 983: else
164000: 984: return -1;
-: 985: }
-: 986:
-: 987: /* ??? Ought to use estimate_probability instead. */
-: 988:
-: 989: /* If this is a branch outside a loop, it is highly unlikely. */
197734: 990: if (GET_CODE (PATTERN (jump_insn)) == SET
-: 991: && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
-: 992: && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
#####: 993: && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
-: 994: || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
#####: 995: && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
#####: 996: return -1;
-: 997:
197734: 998: if (target_label)
-: 999: {
-: 1000: /* If this is the test of a loop, it is very likely true. We scan
-: 1001: backwards from the target label. If we find a NOTE_INSN_LOOP_BEG
-: 1002: before the next real insn, we assume the branch is to the top of
-: 1003: the loop. */
224497: 1004: for (insn = PREV_INSN (target_label);
-: 1005: insn && NOTE_P (insn);
-: 1006: insn = PREV_INSN (insn))
41054: 1007: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
14291: 1008: return 2;
-: 1009: }
-: 1010:
-: 1011: /* Look at the relative rarities of the fallthrough and destination. If
-: 1012: they differ, we can predict the branch that way. */
-: 1013:
183443: 1014: switch (rare_fallthrough - rare_dest)
-: 1015: {
-: 1016: case -2:
#####: 1017: return -1;
-: 1018: case -1:
#####: 1019: return 0;
-: 1020: case 0:
#####: 1021: break;
-: 1022: case 1:
#####: 1023: return 1;
-: 1024: case 2:
183443: 1025: return 2;
-: 1026: }
-: 1027:
-: 1028: /* If we couldn't figure out what this jump was, assume it won't be
-: 1029: taken. This should be rare. */
#####: 1030: if (condition == 0)
#####: 1031: return 0;
-: 1032:
-: 1033: /* EQ tests are usually false and NE tests are usually true. Also,
-: 1034: most quantities are positive, so we can make the appropriate guesses
-: 1035: about signed comparisons against zero. */
#####: 1036: switch (GET_CODE (condition))
-: 1037: {
-: 1038: case CONST_INT:
-: 1039: /* Unconditional branch. */
#####: 1040: return 1;
-: 1041: case EQ:
#####: 1042: return 0;
-: 1043: case NE:
#####: 1044: return 1;
-: 1045: case LE:
-: 1046: case LT:
#####: 1047: if (XEXP (condition, 1) == const0_rtx)
#####: 1048: return 0;
#####: 1049: break;
-: 1050: case GE:
-: 1051: case GT:
#####: 1052: if (XEXP (condition, 1) == const0_rtx)
#####: 1053: return 1;
#####: 1054: break;
-: 1055:
-: 1056: default:
#####: 1057: break;
-: 1058: }
-: 1059:
-: 1060: /* Predict backward branches usually take, forward branches usually not. If
-: 1061: we don't know whether this is forward or backward, assume the branch
-: 1062: will be taken, since most are. */
#####: 1063: return (target_label == 0 || INSN_UID (jump_insn) > max_uid
-: 1064: || INSN_UID (target_label) > max_uid
-: 1064: || INSN_UID (target_label) > max_uid
-: 1065: || (uid_to_ruid[INSN_UID (jump_insn)]
-: 1066: > uid_to_ruid[INSN_UID (target_label)]));
-: 1067:}
-: 1068:
Four results stand out:
1) (1490768 - 197734) / 1490768 * 100% = 87% of the times, there is
a REG_BR_PROB note that determines the result of this function.
2) The part of the function that uses LABEL_OUTSIDE_LOOP_P is never
executed at all.
3) Apparently (rare_fallthrough - rare_dest) == 2 always, so the rest
of the function from there on is never executed either.
4) Less than 1% of the results are computed from loop notes.
I can't really explain (3). If you look at rare_destination, also in
reorg.c. The function says it can only return 2 for functions that do
not return, but in mostly_true_jump, we do:
int rare_dest = rare_destination (target_label);
int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
When rare_destination(target_label)==0, and NEXT_INSN (jump_insn) is a
BARRIER, we have (rare_fallthrough - rare_dest) == 2. AFAICT there are
no other situation where we can have this result. We can only have a
BARRIER after a JUMP_INSN for unconditional jumps, which are obviously
always taken. But in that case I would expect rare_dest == 2 and
rare_fallthrough == 0... :-/
Anyway...
* lines 1014-1026 are only ever used to predict unconditional jumps
of some kind...
* lines 987-997 are dead code because we always have a REG_BR_PROB
note to compute a result from.
* lines 1063-1067 looks like a decent fall-back if all else fails.
* loop notes do not significantly contribute to the computation of
the result for mostly_true_jump.
* because flag_guess_branch_prob is set already at -O1, I expect
that we will have REG_BR_PROB notes for almost all jumps even at
-O1 -- I'm now running another test to make sure this is true.
I would like to propose the patch below to clean up mostly_true_jump.
What do you folks think about this? What kind of further testing would
you suggest?
The patch was bootstrapped on hppa-suse-linux-gnu. I also built an
amd64 x mips-elf, and I ran the mips-sim test suite.
Gr.
Steven
* reorg.c (mostly_true_jump): Clean up code depending on
LABEL_OUTSIDE_LOOP_P and loop notes. Remove code doing
poor man's branch prediction, instead rely on REG_BR_PROB
notes to be available.
Index: reorg.c
===================================================================
--- reorg.c (revision 108409)
+++ reorg.c (working copy)
@@ -984,30 +984,6 @@ mostly_true_jump (rtx jump_insn, rtx con
return -1;
}
- /* ??? Ought to use estimate_probability instead. */
-
- /* If this is a branch outside a loop, it is highly unlikely. */
- if (GET_CODE (PATTERN (jump_insn)) == SET
- && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
- && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
- && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
- || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
- && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
- return -1;
-
- if (target_label)
- {
- /* If this is the test of a loop, it is very likely true. We scan
- backwards from the target label. If we find a NOTE_INSN_LOOP_BEG
- before the next real insn, we assume the branch is to the top of
- the loop. */
- for (insn = PREV_INSN (target_label);
- insn && NOTE_P (insn);
- insn = PREV_INSN (insn))
- if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
- return 2;
- }
-
/* Look at the relative rarities of the fallthrough and destination. If
they differ, we can predict the branch that way. */
@@ -1030,33 +1006,6 @@ mostly_true_jump (rtx jump_insn, rtx con
if (condition == 0)
return 0;
- /* EQ tests are usually false and NE tests are usually true. Also,
- most quantities are positive, so we can make the appropriate guesses
- about signed comparisons against zero. */
- switch (GET_CODE (condition))
- {
- case CONST_INT:
- /* Unconditional branch. */
- return 1;
- case EQ:
- return 0;
- case NE:
- return 1;
- case LE:
- case LT:
- if (XEXP (condition, 1) == const0_rtx)
- return 0;
- break;
- case GE:
- case GT:
- if (XEXP (condition, 1) == const0_rtx)
- return 1;
- break;
-
- default:
- break;
- }
-
/* 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. */