This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
loop unrolling branch predictor
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com, patches at x86-64 dot org
- Subject: loop unrolling branch predictor
- From: Jan Hubicka <jh at suse dot cz>
- Date: Tue, 12 Jun 2001 19:06:50 +0200
Hi,
the loop unrolling code emits few conditionals, that gets misspredicted
by default predictors. Easy trick is to add the prediction there, as
we know more about the probabilities.
Similar thing may be possible for expand_case as well.
Honza
Tue Jun 12 18:53:37 CEST 2001 Jan Hubicka <jh@suse.cz>
* unroll.c: Include predict.h.
(unroll_loop): Drop prediction notes on preconditioning.
* predict.def (PRED_LOOP_PRECONDITIONG, PRED_LOOP_CONDITION):
New; add comments on the others.
* Makefile.in: (unroll.o): Add dependancy on predict.h.
Index: unroll.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/unroll.c,v
retrieving revision 1.129
diff -c -3 -p -r1.129 unroll.c
*** unroll.c 2001/06/12 04:42:09 1.129
--- unroll.c 2001/06/12 16:51:55
*************** enum unroll_types
*** 167,172 ****
--- 167,173 ----
#include "toplev.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+ #include "predict.h"
/* This controls which loops are unrolled, and by how much we unroll
them. */
*************** unroll_loop (loop, insn_count, strength_
*** 962,967 ****
--- 963,969 ----
emit_cmp_and_jump_insns (initial_value, final_value,
neg_inc ? LE : GE,
NULL_RTX, mode, 0, 0, labels[1]);
+ predict_insn_def (get_last_insn (), PRED_LOOP_CONDITION, NOT_TAKEN);
JUMP_LABEL (get_last_insn ()) = labels[1];
LABEL_NUSES (labels[1])++;
}
*************** unroll_loop (loop, insn_count, strength_
*** 1007,1012 ****
--- 1009,1016 ----
labels[i]);
JUMP_LABEL (get_last_insn ()) = labels[i];
LABEL_NUSES (labels[i])++;
+ predict_insn (get_last_insn (), PRED_LOOP_PRECONDITIONING,
+ REG_BR_PROB_BASE / unroll_number);
}
/* If the increment is greater than one, then we need another branch,
Index: predict.def
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.def,v
retrieving revision 1.4
diff -c -3 -p -r1.4 predict.def
*** predict.def 2001/06/12 10:22:22 1.4
--- predict.def 2001/06/12 16:51:55
*************** Boston, MA 02111-1307, USA. */
*** 36,50 ****
--- 36,69 ----
REG_BR_PROB_BASE / 2). */
+ /* An combined heuristics using probability determined by first
+ matching heuristics from this list. */
DEF_PREDICTOR (PRED_FIRST_MATCH, "first match", PROB_ALWAYS)
+ /* Mark unconditional jump as taken. */
DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS)
+ /* Use number of loop iterations determined by loop unroller to set
+ probability. */
DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS)
+ /* Hints dropped by user via __builtin_expect feature. */
DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY)
+ /* Branch to basic block containing call marked by noreturn attribute. */
DEF_PREDICTOR (PRED_NORETURN, "noreturn call", PROB_ALWAYS)
+ /* Loopback edge is taken. */
DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", PROB_VERY_LIKELY)
+ /* Edge causing loop to terminate is probably not taken. */
DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", PROB_LIKELY)
+ /* Condition emitted by preconditiong code to ensure that variable
+ setting number of iterations is greater than initial value of iterator. */
+ DEF_PREDICTOR (PRED_LOOP_CONDITION, "loop condition", PROB_VERY_LIKELY)
+ /* Preconditioning makes linear list of branches. */
+ DEF_PREDICTOR (PRED_LOOP_PRECONDITIONING, "loop preconditioning", PROB_VERY_LIKELY)
+ /* Copied condition for the first iteration of loop is probably true. */
DEF_PREDICTOR (PRED_LOOP_HEADER, "loop header", PROB_LIKELY)
+ /* Pointers are usually not NULL. */
DEF_PREDICTOR (PRED_POINTER, "pointer", PROB_LIKELY)
+ /* NE is probable, EQ not etc... */
DEF_PREDICTOR (PRED_OPCODE, "opcode", PROB_LIKELY)
+ /* Branch guarding call is probably taken. */
DEF_PREDICTOR (PRED_CALL, "call", PROB_LIKELY)
+ /* Branch causing function to terminate is probably not taken. */
DEF_PREDICTOR (PRED_ERROR_RETURN, "error return", PROB_LIKELY)
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.675
diff -c -3 -p -r1.675 Makefile.in
*** Makefile.in 2001/06/12 10:22:22 1.675
--- Makefile.in 2001/06/12 16:51:59
*************** doloop.o : doloop.c $(CONFIG_H) $(SYSTEM
*** 1444,1450 ****
$(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) toplev.h
unroll.o : unroll.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) insn-config.h function.h \
$(INTEGRATE_H) $(REGS_H) $(RECOG_H) flags.h $(EXPR_H) $(LOOP_H) toplev.h \
! hard-reg-set.h varray.h $(BASIC_BLOCK_H) $(TM_P_H)
flow.o : flow.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(EXPR_H) ssa.h $(GGC_H) $(TM_P_H)
--- 1444,1450 ----
$(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) toplev.h
unroll.o : unroll.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) insn-config.h function.h \
$(INTEGRATE_H) $(REGS_H) $(RECOG_H) flags.h $(EXPR_H) $(LOOP_H) toplev.h \
! hard-reg-set.h varray.h $(BASIC_BLOCK_H) $(TM_P_H) $(PREDICT_H)
flow.o : flow.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(EXPR_H) ssa.h $(GGC_H) $(TM_P_H)