PR tree-optimization/38074

[Jan Hubicka]

Hi,
as discussed in audit trail, the hot loop of polyhedron benchmark gets
predicted as unlikely, because noreturn heuristic produce erratic
results on functions that never returns.

This patch fixes 3 quite independent problems: noreturn heuristic is
disabled for functions with all noreturn paths, confused first match
heuristics are ignored and cgraph frequency code is updated to give more
consistent values for functions with zero frequency of entry block.

With these changes, internal loop gets frequency of 6 that is not very
high value but enough to get things working.

Bootstrapped/regtested i686-linux, comitted.

2008-12-06  Jan Hubicka  <jh@suse.cz>
	    Jakub Jelinek <jakub@redhat.com>

	PR tree-optimization/38074
	* cgraphbuild.c (compute_call_stmt_bb_frequency): Fix handling of 0
	entry frequency.
	* predict.c (combine_predictions_for_bb): Ignore predictor predicting
	in both dirrection for first match heuristics.
	(tree_bb_level_predictions): Disable noreturn heuristic when there
	is no returning path.
Index: cgraphbuild.c
===================================================================
*** cgraphbuild.c	(revision 141929)
--- cgraphbuild.c	(working copy)
*************** int
*** 109,121 ****
  compute_call_stmt_bb_frequency (basic_block bb)
  {
    int entry_freq = ENTRY_BLOCK_PTR->frequency;
!   int freq;
  
    if (!entry_freq)
!     entry_freq = 1;
  
!   freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
! 	      : bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
    if (freq > CGRAPH_FREQ_MAX)
      freq = CGRAPH_FREQ_MAX;
  
--- 109,120 ----
  compute_call_stmt_bb_frequency (basic_block bb)
  {
    int entry_freq = ENTRY_BLOCK_PTR->frequency;
!   int freq = bb->frequency;
  
    if (!entry_freq)
!     entry_freq = 1, freq++;
  
!   freq = freq * CGRAPH_FREQ_BASE / entry_freq;
    if (freq > CGRAPH_FREQ_MAX)
      freq = CGRAPH_FREQ_MAX;
  
Index: predict.c
===================================================================
*** predict.c	(revision 141929)
--- predict.c	(working copy)
*************** combine_predictions_for_bb (basic_block 
*** 820,827 ****
  	    probability = REG_BR_PROB_BASE - probability;
  
  	  found = true;
  	  if (best_predictor > predictor)
! 	    best_probability = probability, best_predictor = predictor;
  
  	  d = (combined_probability * probability
  	       + (REG_BR_PROB_BASE - combined_probability)
--- 820,852 ----
  	    probability = REG_BR_PROB_BASE - probability;
  
  	  found = true;
+ 	  /* First match heuristics would be widly confused if we predicted
+ 	     both directions.  */
  	  if (best_predictor > predictor)
! 	    {
!               struct edge_prediction *pred2;
! 	      int prob = probability;
! 
!               for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
! 	       if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
! 	         {
! 	           int probability2 = pred->ep_probability;
! 
! 		   if (pred2->ep_edge != first)
! 		     probability2 = REG_BR_PROB_BASE - probability2;
! 
! 		   if ((probability < REG_BR_PROB_BASE / 2) != 
! 		       (probability2 < REG_BR_PROB_BASE / 2))
! 		     break;
! 
! 		   /* If the same predictor later gave better result, go for it! */
! 		   if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
! 		       || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
! 		     prob = probability2;
! 		 }
! 	      if (!pred2)
! 	        best_probability = prob, best_predictor = predictor;
! 	    }
  
  	  d = (combined_probability * probability
  	       + (REG_BR_PROB_BASE - combined_probability)
*************** static void
*** 1521,1526 ****
--- 1546,1561 ----
  tree_bb_level_predictions (void)
  {
    basic_block bb;
+   bool has_return_edges = false;
+   edge e;
+   edge_iterator ei;
+ 
+   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+     if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
+       {
+         has_return_edges = true;
+ 	break;
+       }
  
    apply_return_prediction ();
  
*************** tree_bb_level_predictions (void)
*** 1535,1541 ****
  
  	  if (is_gimple_call (stmt))
  	    {
! 	      if (gimple_call_flags (stmt) & ECF_NORETURN)
  		predict_paths_leading_to (bb, PRED_NORETURN,
  					  NOT_TAKEN);
  	      decl = gimple_call_fndecl (stmt);
--- 1570,1577 ----
  
  	  if (is_gimple_call (stmt))
  	    {
! 	      if ((gimple_call_flags (stmt) & ECF_NORETURN)
! 	          && has_return_edges)
  		predict_paths_leading_to (bb, PRED_NORETURN,
  					  NOT_TAKEN);
  	      decl = gimple_call_fndecl (stmt);