loop unroller and br_pred take 2

[Jan Hubicka]

Hi
I've found minor problems in the previous patch. Basically the probability
of branching has been computed incorrectly.
This patch has much better coverage, and slightly improves byte benchmark,
as the precondtiioning is not misspredicted.

But more important IMO is that now I can track down where the branches in code
come from, so I would like to tag the other sources of branches 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/14 10:53:26
*************** 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 - i));
  	    }
  
  	  /* 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/14 10:53:26
*************** Boston, MA 02111-1307, USA.  */
*** 36,50 ****
--- 36,82 ----
     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)