This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

loop unrolling branch predictor


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)


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]