This is the mail archive of the gcc@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]
Other format: [Raw text]

Re: Incorrect application of loop exit heuristic?


> 
> 
> Pat Haugen <pthaugen@us.ibm.com> wrote on 08/21/2006 01:22:25 PM:
> 
> > Jan Hubicka <hubicka@ucw.cz> wrote on 08/19/2006 07:51:42 PM:
> >
> > > Hi,
> > > this patch at least hides the ugly details within some abstraction so
> we
> > > can eventally go for propagating reliability information across CFG if
> > > we conclude it is important.  How does it work for you?
> > >
> >
> > I like your approach, thanks.  I've confirmed that the generated code no
> > longer contains the mis-predicted branch hints.  Will follow up with
> > results from SPEC run once I get them (hosed things up for myself, so
> > restarting from scratch) :-(
> >
> > -Pat
> >
> 
> The results with your patch mimicked the results of my initial attempt:
> perlbmk improved 7% and a couple others improved a couple percent.

Happy to hear that!  I've comitted the attached patch.
Thank you for tracking this, very interesting, dead end of predictor
machinery.

Honza

Index: ChangeLog
===================================================================
*** ChangeLog	(revision 116357)
--- ChangeLog	(working copy)
***************
*** 1,3 ****
--- 1,15 ----
+ 2006-08-24  Jan Hubicka  <jh@suse.cz>
+ 
+ 	* predict.c (probability_reliable_p): New predicate.
+ 	(edge_probability_reliable_p, br_prob_note_reliable_p): Likewise.
+ 	(predict_loops): Do not predict loop exit with less than 2%
+ 	probability.
+ 	* basic-block.h (edge_probability_reliable_p,
+ 	br_prob_note_reliable_p): Declare.
+ 	* ia64.h (ia64_print_operand): Do not disable on-chip branch
+ 	prediction when static predictor is not reliable.
+ 	* rs6000.c (output_cbranch): Likewise.
+ 
  2006-08-23  Stuart Hastings  <stuart@apple.com>
  
  	PR 28825
Index: predict.c
===================================================================
*** predict.c	(revision 116355)
--- predict.c	(working copy)
*************** tree_predicted_by_p (basic_block bb, enu
*** 178,183 ****
--- 178,222 ----
    return false;
  }
  
+ /* Return true when the probability of edge is reliable.
+   
+    The profile guessing code is good at predicting branch outcome (ie.
+    taken/not taken), that is predicted right slightly over 75% of time.
+    It is however notorously poor on predicting the probability itself.
+    In general the profile appear a lot flatter (with probabilities closer
+    to 50%) than the reality so it is bad idea to use it to drive optimization
+    such as those disabling dynamic branch prediction for well predictable
+    branches.
+ 
+    There are two exceptions - edges leading to noreturn edges and edges
+    predicted by number of iterations heuristics are predicted well.  This macro
+    should be able to distinguish those, but at the moment it simply check for
+    noreturn heuristic that is only one giving probability over 99% or bellow
+    1%.  In future we might want to propagate reliablity information across the
+    CFG if we find this information useful on multiple places.   */
+ static bool
+ probability_reliable_p (int prob)
+ {
+   return (profile_status == PROFILE_READ
+ 	  || (profile_status == PROFILE_GUESSED
+ 	      && (prob <= HITRATE (1) || prob >= HITRATE (99))));
+ }
+ 
+ /* Same predicate as above, working on edges.  */
+ bool
+ edge_probability_reliable_p (edge e)
+ {
+   return probability_reliable_p (e->probability);
+ }
+ 
+ /* Same predicate as edge_probability_reliable_p, working on notes.  */
+ bool
+ br_prob_note_reliable_p (rtx note)
+ {
+   gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
+   return probability_reliable_p (INTVAL (XEXP (note, 0)));
+ }
+ 
  static void
  predict_insn (rtx insn, enum br_predictor predictor, int probability)
  {
*************** predict_loops (struct loops *loops_info,
*** 706,719 ****
  	  /* Loop exit heuristics - predict an edge exiting the loop if the
  	     conditional has no loop header successors as not taken.  */
  	  if (!header_found)
! 	    FOR_EACH_EDGE (e, ei, bb->succs)
! 	      if (e->dest->index < NUM_FIXED_BLOCKS
! 		  || !flow_bb_inside_loop_p (loop, e->dest))
! 		predict_edge
! 		  (e, PRED_LOOP_EXIT,
! 		   (REG_BR_PROB_BASE
! 		    - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
! 		   / n_exits);
  	}
        
        /* Free basic blocks from get_loop_body.  */
--- 745,775 ----
  	  /* Loop exit heuristics - predict an edge exiting the loop if the
  	     conditional has no loop header successors as not taken.  */
  	  if (!header_found)
! 	    {
! 	      /* For loop with many exits we don't want to predict all exits
! 	         with the pretty large probability, because if all exits are
! 		 considered in row, the loop would be predicted to iterate
! 		 almost never.  The code to divide probability by number of
! 		 exits is very rough.  It should compute the number of exits
! 		 taken in each patch through function (not the overall number
! 		 of exits that might be a lot higher for loops with wide switch
! 		 statements in them) and compute n-th square root.
! 
! 		 We limit the minimal probability by 2% to avoid
! 		 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
! 		 as this was causing regression in perl benchmark containing such
! 		 a wide loop.  */
! 	        
! 	      int probability = ((REG_BR_PROB_BASE
! 		                  - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
! 				 / n_exits);
! 	      if (probability < HITRATE (2))
! 		probability = HITRATE (2);
! 	      FOR_EACH_EDGE (e, ei, bb->succs)
! 		if (e->dest->index < NUM_FIXED_BLOCKS
! 		    || !flow_bb_inside_loop_p (loop, e->dest))
! 		  predict_edge (e, PRED_LOOP_EXIT, probability);
! 	    }
  	}
        
        /* Free basic blocks from get_loop_body.  */
Index: basic-block.h
===================================================================
*** basic-block.h	(revision 116355)
--- basic-block.h	(working copy)
*************** extern void rtl_predict_edge (edge, enum
*** 880,885 ****
--- 880,887 ----
  extern void predict_edge_def (edge, enum br_predictor, enum prediction);
  extern void guess_outgoing_edge_probabilities (basic_block);
  extern void remove_predictions_associated_with_edge (edge);
+ extern bool edge_probability_reliable_p (edge);
+ extern bool br_prob_note_reliable_p (rtx);
  
  /* In flow.c */
  extern void init_flow (void);
Index: config/ia64/ia64.c
===================================================================
*** config/ia64/ia64.c	(revision 116355)
--- config/ia64/ia64.c	(working copy)
*************** ia64_print_operand (FILE * file, rtx x, 
*** 4656,4666 ****
  	    int pred_val = INTVAL (XEXP (x, 0));
  
  	    /* Guess top and bottom 10% statically predicted.  */
! 	    if (pred_val < REG_BR_PROB_BASE / 50)
  	      which = ".spnt";
  	    else if (pred_val < REG_BR_PROB_BASE / 2)
  	      which = ".dpnt";
! 	    else if (pred_val < REG_BR_PROB_BASE / 100 * 98)
  	      which = ".dptk";
  	    else
  	      which = ".sptk";
--- 4656,4668 ----
  	    int pred_val = INTVAL (XEXP (x, 0));
  
  	    /* Guess top and bottom 10% statically predicted.  */
! 	    if (pred_val < REG_BR_PROB_BASE / 50
! 		&& br_prob_note_reliable_p (x))
  	      which = ".spnt";
  	    else if (pred_val < REG_BR_PROB_BASE / 2)
  	      which = ".dpnt";
! 	    else if (pred_val < REG_BR_PROB_BASE / 100 * 98
! 		     || !br_prob_note_reliable_p (x))
  	      which = ".dptk";
  	    else
  	      which = ".sptk";
Index: config/rs6000/rs6000.c
===================================================================
*** config/rs6000/rs6000.c	(revision 116355)
--- config/rs6000/rs6000.c	(working copy)
*************** output_cbranch (rtx op, const char *labe
*** 11498,11504 ****
  	 mispredicted taken branch is more expensive than a
  	 mispredicted not-taken branch.  */
        if (rs6000_always_hint
! 	  || abs (prob) > REG_BR_PROB_BASE / 100 * 48)
  	{
  	  if (abs (prob) > REG_BR_PROB_BASE / 20
  	      && ((prob > 0) ^ need_longbranch))
--- 11498,11505 ----
  	 mispredicted taken branch is more expensive than a
  	 mispredicted not-taken branch.  */
        if (rs6000_always_hint
! 	  || (abs (prob) > REG_BR_PROB_BASE / 100 * 48
! 	      && br_prob_note_reliable_p (note)))
  	{
  	  if (abs (prob) > REG_BR_PROB_BASE / 20
  	      && ((prob > 0) ^ need_longbranch))


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