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]
Other format: [Raw text]

Re: [patch] rtlopt branch merge part 6 - speed improvement of branch predictions


On Mon, Feb 03, 2003 at 11:18:19AM +0100, Josef Zlomek wrote:
> 	* Makefile.in (sreal.o): Added.
> 	(predict.o): Depends on sreal.h instead of real.h.
> 	* sreal.c: New file.
> 	* sreal.h: New file.
> 	* predict.c: Use sreal.c instead of real.c.

I wonder if the following would be better.  Thoughts?


r~



Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.80
diff -c -p -d -r1.80 predict.c
*** predict.c	24 Jan 2003 20:27:02 -0000	1.80
--- predict.c	7 Feb 2003 01:37:46 -0000
*************** Software Foundation, 59 Temple Place - S
*** 48,64 ****
  #include "expr.h"
  #include "predict.h"
  #include "profile.h"
- #include "real.h"
  #include "params.h"
  #include "target.h"
  #include "loop.h"
  #include "cfgloop.h"
  
- /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
- 		   1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX.  */
- static REAL_VALUE_TYPE real_zero, real_one, real_almost_one, real_br_prob_base,
- 		       real_inv_br_prob_base, real_one_half, real_bb_freq_max;
- 
  /* Random guesstimation given names.  */
  #define PROB_VERY_UNLIKELY	(REG_BR_PROB_BASE / 10 - 1)
  #define PROB_EVEN		(REG_BR_PROB_BASE / 2)
--- 48,58 ----
*************** static const struct predictor_info predi
*** 112,118 ****
--- 106,137 ----
    {NULL, 0, 0}
  };
  #undef DEF_PREDICTOR
+ 
+ /* If we use unadulterated fp arithmetic, we may fall into the trap of
+    computing with extra precision, which will result in bootstrap 
+    comparison differences based on the optimization level.  Avoid this
+    by forcing the variables in question through memory.  This will 
+    cause the extra precision to be discarded during the store.  Avoid
+    an optimizing compiler from seeing through this ruse by making the
+    memory volatile.
+ 
+    Note that this is unnecessary if FLT_EVAL_METHOD == {0,1}.  In that
+    case we are assured that no extra precision is used.  We could look
+    for this value in <float.h>, but technically that macro is supposed
+    to be run-time variable.  What we need here is a compile-time value.
+    Since only bootstrapping matters, only look at GCC's internal macro.  */
  
+ #if defined(__GNUC__) && defined(__FLT_EVAL_METHOD__) \
+     && (__FLT_EVAL_METHOD__ == 0 || __FLT_EVAL_METHOD__ == 1)
+ typedef double prob_real;
+ #else
+ typedef volatile double prob_real;
+ #endif
+ 
+ /* Precomputed constants for propagation.  */
+ static const prob_real real_inv_br_prob_base = 1.0 / REG_BR_PROB_BASE;
+ static const prob_real real_almost_one = 1.0 - 1.0 / REG_BR_PROB_BASE;
+ 
  /* Return true in case BB can be CPU intensive and should be optimized
     for maximal performance.  */
  
*************** combine_predictions_for_insn (insn, bb)
*** 359,366 ****
  	  /* If one probability is 0% and one 100%, avoid division by zero.  */
  	  combined_probability = REG_BR_PROB_BASE / 2;
  	else
! 	  combined_probability = (((double) combined_probability) * probability
! 				  * REG_BR_PROB_BASE / d + 0.5);
        }
  
    /* Decide which heuristic to use.  In case we didn't match anything,
--- 378,393 ----
  	  /* If one probability is 0% and one 100%, avoid division by zero.  */
  	  combined_probability = REG_BR_PROB_BASE / 2;
  	else
! 	  {
! 	    prob_real tmp;
! 
! 	    tmp = combined_probability;
! 	    tmp *= probability;
! 	    tmp *= REG_BR_PROB_BASE;
! 	    tmp /= d;
! 	    tmp += 0.5;
! 	    combined_probability = tmp;
! 	  }
        }
  
    /* Decide which heuristic to use.  In case we didn't match anything,
*************** note_prediction_to_br_prob ()
*** 905,911 ****
  typedef struct block_info_def
  {
    /* Estimated frequency of execution of basic_block.  */
!   REAL_VALUE_TYPE frequency;
  
    /* To keep queue of basic blocks to process.  */
    basic_block next;
--- 932,938 ----
  typedef struct block_info_def
  {
    /* Estimated frequency of execution of basic_block.  */
!   prob_real frequency;
  
    /* To keep queue of basic blocks to process.  */
    basic_block next;
*************** typedef struct edge_info_def
*** 923,929 ****
    /* In case edge is an loopback edge, the probability edge will be reached
       in case header is.  Estimated number of iterations of the loop can be
       then computed as 1 / (1 - back_edge_prob).  */
!   REAL_VALUE_TYPE back_edge_prob;
    /* True if the edge is an loopback edge in the natural loop.  */
    int back_edge:1;
  } *edge_info;
--- 950,956 ----
    /* In case edge is an loopback edge, the probability edge will be reached
       in case header is.  Estimated number of iterations of the loop can be
       then computed as 1 / (1 - back_edge_prob).  */
!   prob_real back_edge_prob;
    /* True if the edge is an loopback edge in the natural loop.  */
    int back_edge:1;
  } *edge_info;
*************** propagate_freq (loop)
*** 964,977 ****
  	}
      }
  
!   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
    last = head;
    for (bb = head; bb; bb = nextbb)
      {
!       REAL_VALUE_TYPE cyclic_probability, frequency;
! 
!       memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
!       memcpy (&frequency, &real_zero, sizeof (real_zero));
  
        nextbb = BLOCK_INFO (bb)->next;
        BLOCK_INFO (bb)->next = NULL;
--- 991,1001 ----
  	}
      }
  
!   BLOCK_INFO (head)->frequency = 1;
    last = head;
    for (bb = head; bb; bb = nextbb)
      {
!       prob_real cyclic_probability = 0, frequency = 0;
  
        nextbb = BLOCK_INFO (bb)->next;
        BLOCK_INFO (bb)->next = NULL;
*************** propagate_freq (loop)
*** 987,1027 ****
  
  	  for (e = bb->pred; e; e = e->pred_next)
  	    if (EDGE_INFO (e)->back_edge)
! 	      {
! 		REAL_ARITHMETIC (cyclic_probability, PLUS_EXPR,
! 				 cyclic_probability,
! 				 EDGE_INFO (e)->back_edge_prob);
! 	      }
  	    else if (!(e->flags & EDGE_DFS_BACK))
  	      {
! 		REAL_VALUE_TYPE tmp;
  
! 		/*  frequency += (e->probability
! 				  * BLOCK_INFO (e->src)->frequency /
! 				  REG_BR_PROB_BASE);  */
  
! 		REAL_VALUE_FROM_INT (tmp, e->probability, 0,
! 				     TYPE_MODE (double_type_node));
! 		REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
! 				 BLOCK_INFO (e->src)->frequency);
! 		REAL_ARITHMETIC (tmp, MULT_EXPR, tmp, real_inv_br_prob_base);
! 		REAL_ARITHMETIC (frequency, PLUS_EXPR, frequency, tmp);
  	      }
  
! 	  if (REAL_VALUES_IDENTICAL (cyclic_probability, real_zero))
! 	    memcpy (&BLOCK_INFO (bb)->frequency, &frequency, sizeof (frequency));
  	  else
  	    {
! 	      if (REAL_VALUES_LESS (real_almost_one, cyclic_probability))
! 		memcpy (&cyclic_probability, &real_almost_one, sizeof (real_zero));
! 
! 	      /* BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability)
! 	       */
  
! 	      REAL_ARITHMETIC (cyclic_probability, MINUS_EXPR, real_one,
! 			   cyclic_probability);
! 	      REAL_ARITHMETIC (BLOCK_INFO (bb)->frequency,
! 			       RDIV_EXPR, frequency, cyclic_probability);
  	    }
  	}
  
--- 1011,1041 ----
  
  	  for (e = bb->pred; e; e = e->pred_next)
  	    if (EDGE_INFO (e)->back_edge)
! 	      cyclic_probability = (cyclic_probability
! 				    + EDGE_INFO (e)->back_edge_prob);
  	    else if (!(e->flags & EDGE_DFS_BACK))
  	      {
! 		prob_real tmp;
  
! 		/* frequency += (e->probability
! 				 * BLOCK_INFO (e->src)->frequency /
! 				 REG_BR_PROB_BASE);  */
  
! 		tmp = e->probability;
! 		tmp *= BLOCK_INFO (e->src)->frequency;
! 		tmp *= real_inv_br_prob_base;
! 		frequency += tmp;
  	      }
  
! 	  if (cyclic_probability == 0)
! 	    BLOCK_INFO (bb)->frequency = frequency;
  	  else
  	    {
! 	      if (real_almost_one < cyclic_probability)
! 		cyclic_probability = real_almost_one;
  
! 	      cyclic_probability = 1 - cyclic_probability;
! 	      BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
  	    }
  	}
  
*************** propagate_freq (loop)
*** 1031,1048 ****
        for (e = bb->succ; e; e = e->succ_next)
  	if (e->dest == head)
  	  {
! 	    REAL_VALUE_TYPE tmp;
! 
! 	    /* EDGE_INFO (e)->back_edge_prob
! 		  = ((e->probability * BLOCK_INFO (bb)->frequency)
! 		     / REG_BR_PROB_BASE); */
! 	    REAL_VALUE_FROM_INT (tmp, e->probability, 0,
! 				 TYPE_MODE (double_type_node));
! 	    REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
! 			     BLOCK_INFO (bb)->frequency);
! 	    REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
! 			     MULT_EXPR, tmp, real_inv_br_prob_base);
  
  	  }
  
        /* Propagate to successor blocks.  */
--- 1045,1055 ----
        for (e = bb->succ; e; e = e->succ_next)
  	if (e->dest == head)
  	  {
! 	    prob_real tmp;
  
+ 	    tmp = e->probability;
+ 	    tmp *= BLOCK_INFO (bb)->frequency;
+ 	    EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
  	  }
  
        /* Propagate to successor blocks.  */
*************** estimate_bb_frequencies (loops)
*** 1160,1184 ****
       struct loops *loops;
  {
    basic_block bb;
!   REAL_VALUE_TYPE freq_max;
!   enum machine_mode double_mode = TYPE_MODE (double_type_node);
  
    if (flag_branch_probabilities)
      counts_to_freqs ();
    else
      {
-       REAL_VALUE_FROM_INT (real_zero, 0, 0, double_mode);
-       REAL_VALUE_FROM_INT (real_one, 1, 0, double_mode);
-       REAL_VALUE_FROM_INT (real_br_prob_base, REG_BR_PROB_BASE, 0, double_mode);
-       REAL_VALUE_FROM_INT (real_bb_freq_max, BB_FREQ_MAX, 0, double_mode);
-       REAL_VALUE_FROM_INT (real_one_half, 2, 0, double_mode);
-       REAL_ARITHMETIC (real_one_half, RDIV_EXPR, real_one, real_one_half);
-       REAL_ARITHMETIC (real_inv_br_prob_base, RDIV_EXPR, real_one, real_br_prob_base);
-       REAL_ARITHMETIC (real_almost_one, MINUS_EXPR, real_one, real_inv_br_prob_base);
- 
        mark_dfs_back_edges ();
!       /* Fill in the probability values in flowgraph based on the REG_BR_PROB
!          notes.  */
        FOR_EACH_BB (bb)
  	{
  	  rtx last_insn = bb->end;
--- 1167,1182 ----
       struct loops *loops;
  {
    basic_block bb;
!   prob_real freq_max;
  
    if (flag_branch_probabilities)
      counts_to_freqs ();
    else
      {
        mark_dfs_back_edges ();
! 
!       /* Fill in the probability values in flowgraph based on
! 	 the REG_BR_PROB notes.  */
        FOR_EACH_BB (bb)
  	{
  	  rtx last_insn = bb->end;
*************** estimate_bb_frequencies (loops)
*** 1203,1208 ****
--- 1201,1207 ----
  	    }
  	}
  
+       /* ??? Should handle alternate entry points eventually.   */
        ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
  
        /* Set up block info for each basic block.  */
*************** estimate_bb_frequencies (loops)
*** 1215,1225 ****
  	  BLOCK_INFO (bb)->tovisit = 0;
  	  for (e = bb->succ; e; e = e->succ_next)
  	    {
! 	      REAL_VALUE_FROM_INT (EDGE_INFO (e)->back_edge_prob,
! 				   e->probability, 0, double_mode);
! 	      REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
! 			       MULT_EXPR, EDGE_INFO (e)->back_edge_prob,
! 			       real_inv_br_prob_base);
  	    }
  	}
  
--- 1214,1221 ----
  	  BLOCK_INFO (bb)->tovisit = 0;
  	  for (e = bb->succ; e; e = e->succ_next)
  	    {
! 	      EDGE_INFO (e)->back_edge_prob = e->probability;
! 	      EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
  	    }
  	}
  
*************** estimate_bb_frequencies (loops)
*** 1227,1254 ****
           to outermost to examine probabilities for back edges.  */
        estimate_loops_at_level (loops->tree_root);
  
!       memcpy (&freq_max, &real_zero, sizeof (real_zero));
        FOR_EACH_BB (bb)
! 	if (REAL_VALUES_LESS
! 	    (freq_max, BLOCK_INFO (bb)->frequency))
! 	  memcpy (&freq_max, &BLOCK_INFO (bb)->frequency,
! 		  sizeof (freq_max));
  
!       REAL_ARITHMETIC (freq_max, RDIV_EXPR, real_bb_freq_max, freq_max);
  
        FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
  	{
! 	  REAL_VALUE_TYPE tmp;
  
! 	  REAL_ARITHMETIC (tmp, MULT_EXPR, BLOCK_INFO (bb)->frequency,
! 			   freq_max);
! 	  REAL_ARITHMETIC (tmp, PLUS_EXPR, tmp, real_one_half);
! 	  bb->frequency = REAL_VALUE_UNSIGNED_FIX (tmp);
  	}
  
        free_aux_for_blocks ();
        free_aux_for_edges ();
      }
    compute_function_frequency ();
    if (flag_reorder_functions)
      choose_function_section ();
--- 1223,1248 ----
           to outermost to examine probabilities for back edges.  */
        estimate_loops_at_level (loops->tree_root);
  
!       freq_max = 0;
        FOR_EACH_BB (bb)
! 	if (freq_max < BLOCK_INFO (bb)->frequency)
! 	  freq_max = BLOCK_INFO (bb)->frequency;
  
!       freq_max = BB_FREQ_MAX / freq_max;
  
        FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
  	{
! 	  prob_real tmp;
  
! 	  tmp = BLOCK_INFO (bb)->frequency * freq_max;
! 	  tmp += 0.5;
! 	  bb->frequency = tmp;
  	}
  
        free_aux_for_blocks ();
        free_aux_for_edges ();
      }
+ 
    compute_function_frequency ();
    if (flag_reorder_functions)
      choose_function_section ();


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