Patchwork Profile housekeeping 4/n (scale_loop_profile cleanup)

login
register
mail settings
Submitter Jan Hubicka
Date Sept. 30, 2012, 3:35 p.m.
Message ID <20120930153549.GA17664@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/188169/
State New
Headers show

Comments

Jan Hubicka - Sept. 30, 2012, 3:35 p.m.
Hi,
when writting scale_loop_profile I forgot about scale_loop_frequency that
already sits in the tree for few years. The functions are slightly different.
While scale_loop_frequency only cales frequency of each BB in the loop,
scale_loop_profile takes care of reducing iteration count to known bound.

For this reason I kept them both, and I am not really able to think of better
names for them.  I moved them to same place.  I also simplified
cale_loop_profile to call scale_loop_frequency to take care of the final
update.

Honza

	* cfgloop.c (scale_loop_profile): Move to...
	* cfgloopmanip.c (scale_loop_profile): .. here; use
	scale_loop_frequencies.
	(loopify): Use RDIV.

Patch

Index: cfgloop.c
===================================================================
--- cfgloop.c	(revision 191850)
+++ cfgloop.c	(working copy)
@@ -1666,121 +1666,3 @@  loop_exits_from_bb_p (struct loop *loop,
 
   return false;
 }
-
-/* Scale the profile estiamte within loop by SCALE.
-   If ITERATION_BOUND is non-zero, scale even further if loop is predicted
-   to iterate too many times.  */
-void
-scale_loop_profile (struct loop *loop, int scale, int iteration_bound)
-{
-  gcov_type iterations = expected_loop_iterations_unbounded (loop);
-  basic_block *bbs;
-  unsigned int i;
-  edge e;
-  edge_iterator ei;
-
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, ";; Scaling loop %i with scale %f, "
-	     "bounding iterations to %i from guessed %i\n",
-	     loop->num, (double)scale / REG_BR_PROB_BASE,
-	     iteration_bound, (int)iterations);
-
-  /* See if loop is predicted to iterate too many times.  */
-  if (iteration_bound && iterations > 0
-      && RDIV (iterations * scale, REG_BR_PROB_BASE) > iteration_bound)
-    {
-      /* Fixing loop profile for different trip count is not trivial; the exit
-	 probabilities has to be updated to match and frequencies propagated down
-	 to the loop body.
-
-	 We fully update only the simple case of loop with single exit that is
-	 either from the latch or BB just before latch and leads from BB with
-	 simple conditional jump.   This is OK for use in vectorizer.  */
-      e = single_exit (loop);
-      if (e)
-	{
-	  edge other_e;
-	  int freq_delta;
-	  gcov_type count_delta;
-
-          FOR_EACH_EDGE (other_e, ei, e->src->succs)
-	    if (!(other_e->flags & (EDGE_ABNORMAL | EDGE_FAKE))
-		&& e != other_e)
-	      break;
-
-	  /* Probability of exit must be 1/iterations.  */
-	  freq_delta = EDGE_FREQUENCY (e);
-	  e->probability = REG_BR_PROB_BASE / iteration_bound;
-	  other_e->probability = inverse_probability (e->probability);
-	  freq_delta -= EDGE_FREQUENCY (e);
-
-	  /* Adjust counts accordingly.  */
-	  count_delta = e->count;
-	  e->count = apply_probability (e->src->count, e->probability);
-	  other_e->count = apply_probability (e->src->count, other_e->probability);
-	  count_delta -= e->count;
-
-	  /* If latch exists, change its frequency and count, since we changed
-	     probability of exit.  Theoretically we should update everything from
-	     source of exit edge to latch, but for vectorizer this is enough.  */
-	  if (loop->latch
-	      && loop->latch != e->src)
-	    {
-	      loop->latch->frequency += freq_delta;
-	      if (loop->latch->frequency < 0)
-		loop->latch->frequency = 0;
-	      loop->latch->count += count_delta;
-	      if (loop->latch->count < 0)
-		loop->latch->count = 0;
-	    }
-	}
-
-      /* Roughly speaking we want to reduce the loop body profile by the
-	 the difference of loop iterations.  We however can do better if
-	 we look at the actual profile, if it is available.  */
-      scale = RDIV (iteration_bound * scale, iterations);
-      if (loop->header->count)
-	{
-	  gcov_type count_in = 0;
-
-	  FOR_EACH_EDGE (e, ei, loop->header->preds)
-	    if (e->src != loop->latch)
-	      count_in += e->count;
-
-	  if (count_in != 0)
-	    scale = RDIV (count_in * iteration_bound * REG_BR_PROB_BASE, loop->header->count);
-	}
-      else if (loop->header->frequency)
-	{
-	  int freq_in = 0;
-
-	  FOR_EACH_EDGE (e, ei, loop->header->preds)
-	    if (e->src != loop->latch)
-	      freq_in += EDGE_FREQUENCY (e);
-
-	  if (freq_in != 0)
-	    scale = RDIV (freq_in * iteration_bound * REG_BR_PROB_BASE, loop->header->frequency);
-	}
-      if (!scale)
-	scale = 1;
-    }
-
-  if (scale == REG_BR_PROB_BASE)
-    return;
-
-  /* Scale the actual probabilities.  */
-  bbs = get_loop_body (loop);
-  for (i = 0; i < loop->num_nodes; i++)
-    {
-      basic_block bb = bbs[i];
-
-      bb->count = RDIV (bb->count * scale, REG_BR_PROB_BASE);
-      bb->frequency = RDIV (bb->frequency * scale, REG_BR_PROB_BASE);
-      FOR_EACH_EDGE (e, ei, bb->succs)
-	e->count = RDIV (e->count * scale, REG_BR_PROB_BASE);
-    }
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, ";; guessed iterations are now %i\n",
-	     (int)expected_loop_iterations_unbounded (loop));
-  free (bbs);
-}
Index: cfgloopmanip.c
===================================================================
--- cfgloopmanip.c	(revision 191850)
+++ cfgloopmanip.c	(working copy)
@@ -39,8 +39,6 @@  static bool fix_bb_placement (basic_bloc
 static void fix_bb_placements (basic_block, bool *);
 static void unloop (struct loop *, bool *);
 
-#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
-
 /* Checks whether basic block BB is dominated by DATA.  */
 static bool
 rpe_enum_p (const_basic_block bb, const void *data)
@@ -462,6 +460,7 @@  add_loop (struct loop *loop, struct loop
 }
 
 /* Multiply all frequencies in LOOP by NUM/DEN.  */
+
 void
 scale_loop_frequencies (struct loop *loop, int num, int den)
 {
@@ -472,6 +471,113 @@  scale_loop_frequencies (struct loop *loo
   free (bbs);
 }
 
+/* Multiply all frequencies in LOOP by SCALE/REG_BR_PROB_BASE.
+   If ITERATION_BOUND is non-zero, scale even further if loop is predicted
+   to iterate too many times.  */
+
+void
+scale_loop_profile (struct loop *loop, int scale, int iteration_bound)
+{
+  gcov_type iterations = expected_loop_iterations_unbounded (loop);
+  edge e;
+  edge_iterator ei;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, ";; Scaling loop %i with scale %f, "
+	     "bounding iterations to %i from guessed %i\n",
+	     loop->num, (double)scale / REG_BR_PROB_BASE,
+	     iteration_bound, (int)iterations);
+
+  /* See if loop is predicted to iterate too many times.  */
+  if (iteration_bound && iterations > 0
+      && RDIV (iterations * scale, REG_BR_PROB_BASE) > iteration_bound)
+    {
+      /* Fixing loop profile for different trip count is not trivial; the exit
+	 probabilities has to be updated to match and frequencies propagated down
+	 to the loop body.
+
+	 We fully update only the simple case of loop with single exit that is
+	 either from the latch or BB just before latch and leads from BB with
+	 simple conditional jump.   This is OK for use in vectorizer.  */
+      e = single_exit (loop);
+      if (e)
+	{
+	  edge other_e;
+	  int freq_delta;
+	  gcov_type count_delta;
+
+          FOR_EACH_EDGE (other_e, ei, e->src->succs)
+	    if (!(other_e->flags & (EDGE_ABNORMAL | EDGE_FAKE))
+		&& e != other_e)
+	      break;
+
+	  /* Probability of exit must be 1/iterations.  */
+	  freq_delta = EDGE_FREQUENCY (e);
+	  e->probability = REG_BR_PROB_BASE / iteration_bound;
+	  other_e->probability = inverse_probability (e->probability);
+	  freq_delta -= EDGE_FREQUENCY (e);
+
+	  /* Adjust counts accordingly.  */
+	  count_delta = e->count;
+	  e->count = apply_probability (e->src->count, e->probability);
+	  other_e->count = apply_probability (e->src->count, other_e->probability);
+	  count_delta -= e->count;
+
+	  /* If latch exists, change its frequency and count, since we changed
+	     probability of exit.  Theoretically we should update everything from
+	     source of exit edge to latch, but for vectorizer this is enough.  */
+	  if (loop->latch
+	      && loop->latch != e->src)
+	    {
+	      loop->latch->frequency += freq_delta;
+	      if (loop->latch->frequency < 0)
+		loop->latch->frequency = 0;
+	      loop->latch->count += count_delta;
+	      if (loop->latch->count < 0)
+		loop->latch->count = 0;
+	    }
+	}
+
+      /* Roughly speaking we want to reduce the loop body profile by the
+	 the difference of loop iterations.  We however can do better if
+	 we look at the actual profile, if it is available.  */
+      scale = RDIV (iteration_bound * scale, iterations);
+      if (loop->header->count)
+	{
+	  gcov_type count_in = 0;
+
+	  FOR_EACH_EDGE (e, ei, loop->header->preds)
+	    if (e->src != loop->latch)
+	      count_in += e->count;
+
+	  if (count_in != 0)
+	    scale = RDIV (count_in * iteration_bound * REG_BR_PROB_BASE, loop->header->count);
+	}
+      else if (loop->header->frequency)
+	{
+	  int freq_in = 0;
+
+	  FOR_EACH_EDGE (e, ei, loop->header->preds)
+	    if (e->src != loop->latch)
+	      freq_in += EDGE_FREQUENCY (e);
+
+	  if (freq_in != 0)
+	    scale = RDIV (freq_in * iteration_bound * REG_BR_PROB_BASE, loop->header->frequency);
+	}
+      if (!scale)
+	scale = 1;
+    }
+
+  if (scale == REG_BR_PROB_BASE)
+    return;
+
+  /* Scale the actual probabilities.  */
+  scale_loop_frequencies (loop, scale, REG_BR_PROB_BASE);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, ";; guessed iterations are now %i\n",
+	     (int)expected_loop_iterations_unbounded (loop));
+}
+
 /* Recompute dominance information for basic blocks outside LOOP.  */
 
 static void
@@ -772,7 +878,7 @@  loopify (edge latch_edge, edge header_ed
       switch_bb->count = cnt;
       FOR_EACH_EDGE (e, ei, switch_bb->succs)
 	{
-	  e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
+	  e->count = RDIV (switch_bb->count * e->probability, REG_BR_PROB_BASE);
 	}
     }
   scale_loop_frequencies (loop, false_scale, REG_BR_PROB_BASE);