PATCH: Use edge probabilities in interblock and ebb schedulers

[Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>]

Hi,

As it seems that patch by Peter Steinmetz was never applied, here is its
fixed version (we could have got division by zero in sched-rgn.c:
compute_trg_info() if probability of a parent block is zero).

This is the link to the original patch:
http://gcc.gnu.org/ml/gcc-patches/2005-09/msg00370.html

Also, please find attached patch that similarly computes basic block
probability information in sched-ebb.c.  Currently it is possible
that CFG has wrong values in bb->frequency fields of some basic blocks.
The proposed patch calculates basic block frequencies for each EBB
separately relying on edge probabilities information. It does not
correct frequency values in CFG.

SPECCPU2000 shows 2 improvements when compiled with gcc -O2 with both of
these patches: 181.mcf: +4.19%, 188.ammp: 11.37%. And several
regressions: 197.parser: -1.25%, 300.twolf: -1.67%, 179.art: -1.41%. But
still, the patches do more good than bad: SPECint_base: +0.14%,
SPECfp_base: +0.72%.

Both patches were bootstraped and regtested on ia64-unknown-linux-gnu on
mainline weekly snapshot 20060107 (as all later snapshots, including
trunk, fail to compile because of libgomp).

--
Maxim


2006-01-31  Pete Steinmetz  <steinmtz@us.ibm.com>

        * sched-rgn.c (compute_dom_prob_ps): Eradicate use of float in
	probability computations.  Use edge probabilities in place of
	statically computed probabilities.
	(min_spec_prob): New static variable.
	(GET_SRC_PROB): Removed.
	* doc/invoke.texi (min-sched-prob): Renamed to min-spec-prob.

2005-01-31  Maxim Kuvyrkov <mkuvyrkov@ispras.ru>

        * sched-ebb.c (freq): New static variable.
	(calc_freqs): New static function.
	(rank): Use freq.
	(schedule_ebb): Call calc_freqs.
	(schedule_ebbs): Init/free freq.


Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(.../mainline)	(revision 2301)
+++ gcc/doc/invoke.texi	(.../prob)	(revision 2301)
@@ -6110,7 +6110,7 @@ interblock scheduling.  The default valu
 The maximum number of insns in a region to be considered for
 interblock scheduling.  The default value is 100.
 
-@item min-sched-prob
+@item min-spec-prob
 The minimum probability of reaching a source block for interblock
 speculative scheduling.  The default value is 40.
 
Index: gcc/sched-rgn.c
===================================================================
--- gcc/sched-rgn.c	(.../mainline)	(revision 2301)
+++ gcc/sched-rgn.c	(.../prob)	(revision 2301)
@@ -119,6 +119,8 @@ static int *block_to_bb;
 /* The number of the region containing a block.  */
 static int *containing_rgn;
 
+static int min_spec_prob;
+
 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
 #define BLOCK_TO_BB(block) (block_to_bb[block])
@@ -211,15 +213,9 @@ static sbitmap *dom;
 #define IS_DOMINATED(bb_src, bb_trg)                                 \
 ( TEST_BIT (dom[bb_src], bb_trg) )
 
-/* Probability: Prob[i] is a float in [0, 1] which is the probability
-   of bb i relative to the region entry.  */
-static float *prob;
-
-/* The probability of bb_src, relative to bb_trg.  Note, that while the
-   'prob[bb]' is a float in [0, 1], this macro returns an integer
-   in [0, 100].  */
-#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
-						      prob[bb_trg])))
+/* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
+   the probability of bb i relative to the region entry.  */
+static int *prob;
 
 /* Bit-set of edges, where bit i stands for edge i.  */
 typedef sbitmap edgeset;
@@ -898,24 +894,27 @@ find_rgns (void)
 static void
 compute_dom_prob_ps (int bb)
 {
-  int pred_bb;
-  int nr_out_edges, nr_rgn_out_edges;
-  edge_iterator in_ei, out_ei;
-  edge in_edge, out_edge;
+  edge_iterator in_ei;
+  edge in_edge;
 
-  prob[bb] = 0.0;
   if (IS_RGN_ENTRY (bb))
     {
       SET_BIT (dom[bb], 0);
-      prob[bb] = 1.0;
+      prob[bb] = REG_BR_PROB_BASE;
       return;
     }
 
+  prob[bb] = 0;
+
   /* Initialize dom[bb] to '111..1'.  */
   sbitmap_ones (dom[bb]);
 
   FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
     {
+      int pred_bb;
+      edge out_edge;
+      edge_iterator out_ei;
+
       if (in_edge->src == ENTRY_BLOCK_PTR)
 	continue;
 
@@ -928,30 +927,10 @@ compute_dom_prob_ps (int bb)
 
       sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
 
-      nr_out_edges = 0;
-      nr_rgn_out_edges = 0;
-
       FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
-	{
-	  ++nr_out_edges;
+	SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
 
-	  /* The successor doesn't belong in the region?  */
-	  if (out_edge->dest != EXIT_BLOCK_PTR
-	      && CONTAINING_RGN (out_edge->dest->index)
-		 != CONTAINING_RGN (BB_TO_BLOCK (bb)))
-	    ++nr_rgn_out_edges;
-
-	  SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
-	}
-
-      /* Now nr_rgn_out_edges is the number of region-exit edges from
-         pred, and nr_out_edges will be the number of pred out edges
-         not leaving the region.  */
-      nr_out_edges -= nr_rgn_out_edges;
-      if (nr_rgn_out_edges > 0)
-	prob[bb] += 0.9 * prob[pred_bb] / nr_out_edges;
-      else
-	prob[bb] += prob[pred_bb] / nr_out_edges;
+      prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE);
     }
 
   SET_BIT (dom[bb], bb);
@@ -959,7 +938,7 @@ compute_dom_prob_ps (int bb)
 
   if (sched_verbose >= 2)
     fprintf (sched_dump, ";;  bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
-	     (int) (100.0 * prob[bb]));
+	     (100 * prob[bb]) / REG_BR_PROB_BASE);
 }
 
 /* Functions for target info.  */
@@ -997,7 +976,7 @@ compute_trg_info (int trg)
   sp = candidate_table + trg;
   sp->is_valid = 1;
   sp->is_speculative = 0;
-  sp->src_prob = 100;
+  sp->src_prob = REG_BR_PROB_BASE;
 
   visited = sbitmap_alloc (last_basic_block);
 
@@ -1008,8 +987,10 @@ compute_trg_info (int trg)
       sp->is_valid = IS_DOMINATED (i, trg);
       if (sp->is_valid)
 	{
-	  sp->src_prob = GET_SRC_PROB (i, trg);
-	  sp->is_valid = (sp->src_prob >= PARAM_VALUE (PARAM_MIN_SPEC_PROB));
+	  int tf = prob[trg], cf = prob[i];
+
+	  sp->src_prob = (cf ? ((cf * REG_BR_PROB_BASE) / tf) : 0);
+	  sp->is_valid = (sp->src_prob >= min_spec_prob);
 	}
 
       if (sp->is_valid)
@@ -2308,7 +2289,7 @@ schedule_region (int rgn)
   /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
   if (current_nr_blocks > 1)
     {
-      prob = xmalloc ((current_nr_blocks) * sizeof (float));
+      prob = xmalloc ((current_nr_blocks) * sizeof (*prob));
 
       dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
       sbitmap_vector_zero (dom, current_nr_blocks);
@@ -2531,6 +2512,9 @@ schedule_insns (FILE *dump_file)
   nr_spec = 0;
   sched_init (dump_file);
 
+  min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
+		    / 100);
+
   init_regions ();
 
   current_sched_info = &region_sched_info;

Index: gcc/sched-ebb.c
===================================================================
--- gcc/sched-ebb.c	(.../mainline)	(revision 2299)
+++ gcc/sched-ebb.c	(.../prob)	(revision 2299)
@@ -47,6 +47,8 @@ static int target_n_insns;
 /* The number of insns scheduled so far.  */
 static int sched_n_insns;
 
+static int *freq;
+
 /* Implementations of the sched_info functions for region scheduling.  */
 static void init_ready_list (struct ready_list *);
 static int can_schedule_ready_p (rtx);
@@ -62,6 +64,7 @@ static basic_block schedule_ebb (rtx, rt
 static basic_block fix_basic_block_boundaries (basic_block, basic_block, rtx,
 					       rtx);
 static void add_missing_bbs (rtx, basic_block, basic_block);
+static void calc_freqs (basic_block, basic_block);
 
 /* Return nonzero if there are more insns that should be scheduled.  */
 
@@ -144,10 +147,10 @@ rank (rtx insn1, rtx insn2)
   basic_block bb2 = BLOCK_FOR_INSN (insn2);
 
   if (bb1->count > bb2->count
-      || bb1->frequency > bb2->frequency)
+      || freq[bb1->index] > freq[bb2->index])
     return -1;
   if (bb1->count < bb2->count
-      || bb1->frequency < bb2->frequency)
+      || freq[bb1->index] < freq[bb2->index])
     return 1;
   return 0;
 }
@@ -505,6 +508,8 @@ schedule_ebb (rtx head, rtx tail)
   /* Set priorities.  */
   n_insns = set_priorities (head, tail);
 
+  calc_freqs (first_bb, last_bb);
+
   current_sched_info->prev_head = PREV_INSN (head);
   current_sched_info->next_tail = NEXT_INSN (tail);
 
@@ -577,6 +582,8 @@ schedule_ebbs (FILE *dump_file)
 
   compute_bb_for_insn ();
 
+  freq = xmalloc (last_basic_block * sizeof (*freq));
+
   /* Schedule every region in the subroutine.  */
   FOR_EACH_BB (bb)
     {
@@ -617,6 +624,7 @@ schedule_ebbs (FILE *dump_file)
 
       bb = schedule_ebb (head, tail);
     }
+  free (freq);
 
   /* Updating life info can be done by local propagation over the modified
      superblocks.  */
@@ -631,3 +639,26 @@ schedule_ebbs (FILE *dump_file)
 
   sched_finish ();
 }
+
+static void
+calc_freqs (basic_block first_bb, basic_block last_bb)
+{
+  int f;
+  
+  freq[first_bb->index] = f = REG_BR_PROB_BASE;
+  
+  if (first_bb != last_bb)
+    {
+      basic_block bb = first_bb;
+
+      do
+	{
+	  edge e;
+
+	  e = FALLTHRU_EDGE (bb);
+	  bb = bb->next_bb;
+	  freq[bb->index] = f = (f * e->probability) / REG_BR_PROB_BASE;
+	}
+      while (bb != last_bb);
+    }
+}