predict.def update

Jan Hubicka jh@suse.cz
Wed Aug 15 02:48:00 GMT 2001


Hi,
I've got new results of branch predictions after updating the debug output:

HEURISTICS                  BRANCHES  (REL)  HITRATE             COVERAGE  (REL)
DS theory                      63321  75.4%  64.34%/ 90.51%  15090165860  45.7%
combined                       83992 100.0%  75.99%/ 92.28%  33015790078 100.0%
opcode                         57334  68.3%  55.70%/ 90.22%  12440263702  37.7%
error return                    4367   5.2%  52.22%/ 88.38%   1705579705   5.2%
no prediction                   6078   7.2%  64.41%/ 90.32%   3349863123  10.1%
call                           24565  29.2%  70.82%/ 94.40%   5403503921  16.4%
first match                    14593  17.4%  90.72%/ 94.55%  14575761095  44.1%
loop branch                     7122   8.5%  89.06%/ 93.27%   7863772647  23.8%
loop header                     7524   9.0%  64.14%/ 89.67%   1772455895   5.4%
loop exit                      10358  12.3%  90.33%/ 95.63%   6670644284  20.2%
loop iterations                  584   0.7%  99.52%/ 99.52%    363026369   1.1%
pointer                         4767   5.7%  83.70%/ 93.57%    901090974   2.7%
noreturn call                   1181   1.4%  99.99%/ 99.99%    231734365   0.7%

They say that we predict properly roughly 76% of jumps (6% better than reported
by B&L paper, 1% better than reported by the other paper with machine learning,
4% worse than reported by another paper using value range propagation).
Interesting is, that first_match heuristics predicts roughly half of branches
with 90% precision - just 4% worse than perfect predictor.

Perhaps it can make sense to add an information about how reliable the
prediction is, so we emit the hardware hints only for instructions, where we
are likely correct.

As I've hoped for, the hitrate of most heuristics improved, when I study them only
in case they are not obsoletted by better one.  Opcode heuristics is still low.
I am sending updated patch with more explanation and numbers in separate email.

Interesting is also the "no prediction", that covers about 10% of branches.
Results claims, that average unpredicted branch is 60% taken.  Most of spec2000
tests expose the strong oposite (as also suggested by some papers and CPUs that
predict non-backward branches as not taken).  The value is due to bzip
benchmark, that does have huge amount of unpredicted branches taken with the
probability of 90%.

I am commiting following update.
Honza

Wed Aug 15 11:39:56 CEST 2001  Jan Hubicka  <jh@suse.cz>

	* predict.def: Update hitrates.

Index: predict.def
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.def,v
retrieving revision 1.9
diff -c -3 -p -r1.9 predict.def
*** predict.def	2001/08/13 14:32:06	1.9
--- predict.def	2001/08/15 09:37:24
*************** DEF_PREDICTOR (PRED_NORETURN, "noreturn 
*** 68,78 ****
  	       PRED_FLAG_FIRST_MATCH)
  
  /* Loopback edge is taken.  */
! DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", HITRATE (88),
  	       PRED_FLAG_FIRST_MATCH)
  
  /* Edge causing loop to terminate is probably not taken. */
! DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE (92),
  	       PRED_FLAG_FIRST_MATCH)
  
  /* Condition emitted by preconditiong code to ensure that variable
--- 68,78 ----
  	       PRED_FLAG_FIRST_MATCH)
  
  /* Loopback edge is taken.  */
! DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", HITRATE (89),
  	       PRED_FLAG_FIRST_MATCH)
  
  /* Edge causing loop to terminate is probably not taken. */
! DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE (90),
  	       PRED_FLAG_FIRST_MATCH)
  
  /* Condition emitted by preconditiong code to ensure that variable
*************** DEF_PREDICTOR (PRED_LOOP_CONDITION, "loo
*** 83,98 ****
  DEF_PREDICTOR (PRED_LOOP_PRECONDITIONING, "loop preconditioning", PROB_VERY_LIKELY, 0)
  
  /* Copied condition for the first iteration of loop is probably true.  */
! DEF_PREDICTOR (PRED_LOOP_HEADER, "loop header", HITRATE (60), 0)
  
  /* Pointers are usually not NULL.  */
! DEF_PREDICTOR (PRED_POINTER, "pointer", HITRATE (75), 0)
  
  /* NE is probable, EQ not etc...  */
! DEF_PREDICTOR (PRED_OPCODE, "opcode", HITRATE (53), 0)
  
  /* Branch guarding call is probably taken.  */
! DEF_PREDICTOR (PRED_CALL, "call", HITRATE (66), 0)
  
  /* Branch causing function to terminate is probably not taken.  */
  DEF_PREDICTOR (PRED_ERROR_RETURN, "error return", PROB_LIKELY, 0)
--- 83,98 ----
  DEF_PREDICTOR (PRED_LOOP_PRECONDITIONING, "loop preconditioning", PROB_VERY_LIKELY, 0)
  
  /* Copied condition for the first iteration of loop is probably true.  */
! DEF_PREDICTOR (PRED_LOOP_HEADER, "loop header", HITRATE (64), 0)
  
  /* Pointers are usually not NULL.  */
! DEF_PREDICTOR (PRED_POINTER, "pointer", HITRATE (83), 0)
  
  /* NE is probable, EQ not etc...  */
! DEF_PREDICTOR (PRED_OPCODE, "opcode", HITRATE (55), 0)
  
  /* Branch guarding call is probably taken.  */
! DEF_PREDICTOR (PRED_CALL, "call", HITRATE (70), 0)
  
  /* Branch causing function to terminate is probably not taken.  */
  DEF_PREDICTOR (PRED_ERROR_RETURN, "error return", PROB_LIKELY, 0)



More information about the Gcc-patches mailing list