[gcc r14-2855] Cleanup profile updating code in unrolling and splitting

[gcc r14-2855] Cleanup profile updating code in unrolling and splitting

[Jan Hubicka]

https://gcc.gnu.org/g:88618fa0211d77d91b70f7af9b02e08a34b57912

commit r14-2855-g88618fa0211d77d91b70f7af9b02e08a34b57912
Author: Honza <jh@ryzen4.suse.cz>
Date:   Fri Jul 28 19:39:19 2023 +0200

    Cleanup profile updating code in unrolling and splitting
    
    I have noticed that for all these three cases I need same update of
    loop exit probability.  While my earlier patch unified it for unrollers,
    this patch makes it more general and also simplifies
    tree-ssa-loop-split.cc.
    
    I also refactored the code, since with all the special cases for
    corrupted profile it gets relatively long.
    I now also handle multiple loop exits in RTL unroller.
    
    Bootstrapped/regtested x86_64-linux, comitted.
    gcc/ChangeLog:
    
            * cfgloopmanip.cc (loop_count_in): Break out from ...
            (loop_exit_for_scaling): Break out from ...
            (update_loop_exit_probability_scale_dom_bbs): Break out from ...;
            add more sanity check and debug info.
            (scale_loop_profile): ... here.
            (create_empty_loop_on_edge): Fix whitespac.
            * cfgloopmanip.h (update_loop_exit_probability_scale_dom_bbs): Declare.
            * loop-unroll.cc (unroll_loop_constant_iterations): Use
            update_loop_exit_probability_scale_dom_bbs.
            * tree-ssa-loop-manip.cc (update_exit_probability_after_unrolling): Remove.
            (tree_transform_and_unroll_loop): Use
            update_loop_exit_probability_scale_dom_bbs.
            * tree-ssa-loop-split.cc (split_loop): Use
            update_loop_exit_probability_scale_dom_bbs.

Diff:
---
 gcc/cfgloopmanip.cc        | 276 ++++++++++++++++++++++++++++++---------------
 gcc/cfgloopmanip.h         |   3 +
 gcc/loop-unroll.cc         |   8 +-
 gcc/tree-ssa-loop-manip.cc |  30 +----
 gcc/tree-ssa-loop-split.cc |  45 +-------
 5 files changed, 199 insertions(+), 163 deletions(-)

diff --git a/gcc/cfgloopmanip.cc b/gcc/cfgloopmanip.cc
index c3d292d0dd4..fe452ecf60f 100644
--- a/gcc/cfgloopmanip.cc
+++ b/gcc/cfgloopmanip.cc
@@ -525,6 +525,184 @@ scale_dominated_blocks_in_loop (class loop *loop, basic_block bb,
       }
 }
 
+/* Compute how many times loop is entered.  */
+
+profile_count
+loop_count_in (class loop *loop)
+{
+  /* Compute number of invocations of the loop.  */
+  profile_count count_in = profile_count::zero ();
+  edge e;
+  edge_iterator ei;
+  bool found_latch = false;
+
+  if (loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES))
+    FOR_EACH_EDGE (e, ei, loop->header->preds)
+      if (!flow_bb_inside_loop_p (loop, e->src))
+	count_in += e->count ();
+      else
+	found_latch = true;
+  else
+    FOR_EACH_EDGE (e, ei, loop->header->preds)
+      if (e->src != loop->latch)
+	count_in += e->count ();
+      else
+	found_latch = true;
+  gcc_checking_assert (found_latch);
+  return count_in;
+}
+
+/* Return exit that suitable for update when loop iterations
+   changed.  */
+
+static edge
+loop_exit_for_scaling (class loop *loop)
+{
+  edge exit_edge = single_exit (loop);
+  if (!exit_edge)
+    {
+      auto_vec<edge> exits = get_loop_exit_edges  (loop);
+      exit_edge = single_likely_exit (loop, exits);
+    }
+  return exit_edge;
+}
+
+/* Assume that loop's entry count and profile up to a given EXIT_EDGE is
+   consistent. Update exit probability so loop exists with PROFILE_COUNT
+   and rescale profile of basic blocks inside loop dominated by EXIT_EDGE->src.
+
+   This is useful after number of iteraitons of loop has changed.
+   If EXIT_EDGE is NULL, the function will try to identify suitable exit.
+   If DESIRED_COUNT is NULL, loop entry count will be used.
+   In consistent profile usually loop exists as many times as it is entred.
+
+   Return updated exit if successfull and NULL otherwise. */
+
+edge
+update_loop_exit_probability_scale_dom_bbs (class loop *loop,
+					    edge exit_edge,
+					    profile_count desired_count)
+{
+  if (!exit_edge)
+    exit_edge = loop_exit_for_scaling (loop);
+  if (!exit_edge)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, ";; Not updating exit probability of loop %i;"
+		   " it has no single exit\n",
+		   loop->num);
+	}
+      return NULL;
+    }
+  /* If exit is inside another loop, adjusting its probability will also
+     adjust number of the inner loop iterations.  Just do noting for now.  */
+  if (!just_once_each_iteration_p (loop, exit_edge->src))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, ";; Not updating exit probability of loop %i;"
+		   " exit is inside inner loop\n",
+		   loop->num);
+	}
+      return NULL;
+    }
+  /* Normal loops exit as many times as they are entered.  */
+  if (!desired_count.initialized_p ())
+    desired_count = loop_count_in (loop);
+  /* See if everything is already perfect.  */
+  if (desired_count == exit_edge->count ())
+    return exit_edge;
+  profile_count old_exit_count = exit_edge->count ();
+  /* See if update is possible.
+     Avoid turning probability to 0 or 1 just trying to reach impossible
+     value.
+
+     Natural profile update after some loop will happily scale header count to
+     be less than count of entering the loop.  This is bad idea and they should
+     special case maybe_flat_loop_profile.
+
+     It may also happen that the source basic block of the exit edge is
+     inside in-loop condition:
+
+	  +-> header
+	  |    |
+	  |   B1
+	  |  /  \
+	  | |   B2--exit_edge-->
+	  |  \  /
+	  |   B3
+	  +__/
+
+      If B2 count is smaller than desired exit edge count
+      the profile was inconsistent with the newly discovered upper bound.
+      Probablity of edge B1->B2 is too low.  We do not attempt to fix
+      that (as it is hard in general).  */
+  if (desired_count > exit_edge->src->count
+      && exit_edge->src->count.differs_from_p (desired_count))
+    {
+      if (dump_file)
+	{
+	  fprintf (dump_file, ";; Source bb of loop %i has count ",
+		   loop->num);
+	  exit_edge->src->count.dump (dump_file, cfun);
+	  fprintf (dump_file,
+		   " which is smaller then desired count of exitting loop ");
+	  desired_count.dump (dump_file, cfun);
+	  fprintf (dump_file, ". Profile update is impossible.\n");
+	}
+      /* Drop quality of probability since we know it likely
+	 bad.  */
+      exit_edge->probability = exit_edge->probability.guessed ();
+      return NULL;
+    }
+  if (!exit_edge->src->count.nonzero_p ())
+    {
+      if (dump_file)
+	{
+	  fprintf (dump_file, ";; Not updating exit edge probability"
+		   " in loop %i since profile is zero ",
+		   loop->num);
+	}
+      return NULL;
+    }
+  set_edge_probability_and_rescale_others
+    (exit_edge, desired_count.probability_in (exit_edge->src->count));
+  /* Rescale the remaining edge probabilities and see if there is only
+     one.  */
+  edge other_edge = NULL;
+  bool found = false;
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, exit_edge->src->succs)
+    if (!(e->flags & EDGE_FAKE)
+	&& !loop_exit_edge_p (loop, e))
+      {
+	if (found)
+	  {
+	    other_edge = NULL;
+	    break;
+	  }
+	other_edge = e;
+	found = true;
+      }
+  /* If there is only loop latch after other edge,
+     update its profile.  This is tiny bit more precise
+     than scaling.  */
+  if (other_edge && other_edge->dest == loop->latch)
+    {
+      if (single_pred_p (loop->latch))
+	loop->latch->count = loop->latch->count
+			     + old_exit_count - exit_edge->count ();
+    }
+  else
+    /* If there are multple blocks, just scale.  */
+    scale_dominated_blocks_in_loop (loop, exit_edge->src,
+				    exit_edge->src->count - exit_edge->count (),
+				    exit_edge->src->count - old_exit_count);
+  return exit_edge;
+}
+
 /* Scale profile in LOOP by P.
    If ITERATION_BOUND is not -1, scale even further if loop is predicted
    to iterate too many times.
@@ -571,17 +749,7 @@ scale_loop_profile (class loop *loop, profile_probability p,
   if (iterations <= iteration_bound)
     return;
 
-  /* Compute number of invocations of the loop.  */
-  profile_count count_in = profile_count::zero ();
-  edge e;
-  edge_iterator ei;
-  bool found_latch = false;
-  FOR_EACH_EDGE (e, ei, loop->header->preds)
-    if (e->src != loop->latch)
-      count_in += e->count ();
-    else
-      found_latch = true;
-  gcc_checking_assert (found_latch);
+  profile_count count_in = loop_count_in (loop);
 
   /* Now scale the loop body so header count is
      count_in * (iteration_bound + 1)  */
@@ -596,8 +764,7 @@ scale_loop_profile (class loop *loop, profile_probability p,
 	       (int)iteration_bound);
     }
   /* Finally attempt to fix exit edge probability.  */
-  auto_vec<edge> exits = get_loop_exit_edges  (loop);
-  edge exit_edge = single_likely_exit (loop, exits);
+  edge exit_edge = loop_exit_for_scaling (loop);
 
   /* In a consistent profile unadjusted_exit_count should be same as count_in,
      however to preserve as much of the original info, avoid recomputing
@@ -606,85 +773,8 @@ scale_loop_profile (class loop *loop, profile_probability p,
   if (exit_edge)
     unadjusted_exit_count = exit_edge->count ();
   scale_loop_frequencies (loop, scale_prob);
-
-  if (exit_edge && exit_edge->src->loop_father != loop)
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file,
-		 ";; Loop exit is in inner loop;"
-		 " will leave exit probabilities inconsistent\n");
-    }
-  else if (exit_edge)
-    {
-      profile_count old_exit_count = exit_edge->count ();
-      profile_probability new_probability;
-      if (iteration_bound > 0)
-	{
-	  /* It may happen that the source basic block of the exit edge is
-	     inside in-loop condition:
-
-		+-> header
-		|    |
-		|   B1
-		|  /  \
-		| |   B2--exit_edge-->
-		|  \  /
-		|   B3
-		+__/
-
-	      If B2 count is smaller than desired exit edge count
-	      the profile was inconsistent with the newly discovered upper bound.
-	      Probablity of edge B1->B2 is too low.  We do not attempt to fix
-	      that (as it is hard in general) but we want to avoid dropping
-	      count of edge B2->B3 to zero may confuse later optimizations.  */
-	  if (unadjusted_exit_count.apply_scale (7, 8) > exit_edge->src->count)
-	    {
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		fprintf (dump_file,
-			 ";; Source basic block of loop exit count is too small;"
-			 " will leave exit probabilities inconsistent\n");
-	      exit_edge->probability = exit_edge->probability.guessed ();
-	      return;
-	    }
-	  new_probability
-	    = unadjusted_exit_count.probability_in (exit_edge->src->count);
-	}
-      else
-	new_probability = profile_probability::always ();
-      set_edge_probability_and_rescale_others (exit_edge, new_probability);
-      profile_count new_exit_count = exit_edge->count ();
-
-      /* Rescale the remaining edge probabilities and see if there is only
-	 one.  */
-      edge other_edge = NULL;
-      bool found = false;
-      FOR_EACH_EDGE (e, ei, exit_edge->src->succs)
-	if (!(e->flags & EDGE_FAKE)
-	    && !loop_exit_edge_p (loop, e))
-	  {
-	    if (found)
-	      {
-		other_edge = NULL;
-		break;
-	      }
-	    other_edge = e;
-	    found = true;
-	  }
-      /* If there is only loop latch after other edge,
-	 update its profile.  */
-      if (other_edge && other_edge->dest == loop->latch)
-	loop->latch->count -= new_exit_count - old_exit_count;
-      else
-	scale_dominated_blocks_in_loop (loop, exit_edge->src,
-					exit_edge->src->count - new_exit_count,
-					exit_edge->src->count - old_exit_count);
-    }
-  else if (dump_file && (dump_flags & TDF_DETAILS))
-    {
-      fprintf (dump_file,
-	       ";; Loop has mulitple exits;"
-	       " will leave exit probabilities inconsistent\n");
-    }
+  update_loop_exit_probability_scale_dom_bbs (loop, exit_edge,
+					      unadjusted_exit_count);
 }
 
 /* Recompute dominance information for basic blocks outside LOOP.  */
@@ -924,7 +1014,7 @@ create_empty_loop_on_edge (edge entry_edge,
    have no successor, which caller is expected to fix somehow.
 
    If this may cause the information about irreducible regions to become
-   invalid, IRRED_INVALIDATED is set to true.  
+   invalid, IRRED_INVALIDATED is set to true.
 
    LOOP_CLOSED_SSA_INVALIDATED, if non-NULL, is a bitmap where we store
    basic blocks that had non-trivial update on their loop_father.*/
diff --git a/gcc/cfgloopmanip.h b/gcc/cfgloopmanip.h
index dab7b31c1e7..2dda5040823 100644
--- a/gcc/cfgloopmanip.h
+++ b/gcc/cfgloopmanip.h
@@ -68,6 +68,9 @@ class loop * loop_version (class loop *, void *,
 void adjust_loop_info_after_peeling (class loop *loop, int npeel, bool precise);
 void scale_dominated_blocks_in_loop (class loop *loop, basic_block bb,
 				     profile_count num, profile_count den);
+edge update_loop_exit_probability_scale_dom_bbs
+		(class loop *loop, edge exit_edge = NULL,
+		 profile_count desired_count = profile_count::uninitialized ());
 void update_exit_probability_after_unrolling (class loop *loop, edge new_exit);
 
 #endif /* GCC_CFGLOOPMANIP_H */
diff --git a/gcc/loop-unroll.cc b/gcc/loop-unroll.cc
index bbfa6ccc770..1df8e6cd4ef 100644
--- a/gcc/loop-unroll.cc
+++ b/gcc/loop-unroll.cc
@@ -488,6 +488,7 @@ unroll_loop_constant_iterations (class loop *loop)
   struct opt_info *opt_info = NULL;
   bool ok;
   bool flat = maybe_flat_loop_profile (loop);
+  profile_count orig_exit_count = desc->out_edge->count ();
 
   niter = desc->niter;
 
@@ -608,9 +609,10 @@ unroll_loop_constant_iterations (class loop *loop)
     | (flat ? DLTHE_FLAG_FLAT_PROFILE : 0));
   gcc_assert (ok);
 
-  edge new_exit = single_dom_exit (loop);
-  if (new_exit)
-    update_exit_probability_after_unrolling (loop, new_exit);
+  edge exit = update_loop_exit_probability_scale_dom_bbs
+	  (loop, desc->out_edge, orig_exit_count);
+  if (exit)
+    update_br_prob_note (exit->src);
 
   if (opt_info)
     {
diff --git a/gcc/tree-ssa-loop-manip.cc b/gcc/tree-ssa-loop-manip.cc
index e58892e235c..e7436915e01 100644
--- a/gcc/tree-ssa-loop-manip.cc
+++ b/gcc/tree-ssa-loop-manip.cc
@@ -1040,29 +1040,6 @@ determine_exit_conditions (class loop *loop, class tree_niter_desc *desc,
   *exit_bound = bound;
 }
 
-/* Updat NEW_EXIT probability after loop has been unrolled.  */
-
-void
-update_exit_probability_after_unrolling (class loop *loop, edge new_exit)
-{
-  /* gimple_duplicate_loop_body_to_header_edge depending on
-     DLTHE_FLAG_UPDATE_FREQ either keeps original frequency of the loop header
-     or scales it down accordingly.
-     However exit edge probability is kept as original.  Fix it if needed
-     and compensate.  */
-  profile_probability new_prob
-	  = loop_preheader_edge
-		  (loop)->count ().probability_in (new_exit->src->count);
-  if (!(new_prob == new_exit->probability))
-    {
-      profile_count old_count = new_exit->src->count - new_exit->count ();
-      set_edge_probability_and_rescale_others (new_exit, new_prob);
-      profile_count new_count = new_exit->src->count - new_exit->count ();
-      scale_dominated_blocks_in_loop (loop, new_exit->src,
-				      new_count, old_count);
-    }
-}
-
 /* Unroll LOOP FACTOR times.  LOOP is known to have a single exit edge
    whose source block dominates the latch.  DESC describes the number of
    iterations of LOOP.
@@ -1289,7 +1266,12 @@ tree_transform_and_unroll_loop (class loop *loop, unsigned factor,
   update_ssa (TODO_update_ssa);
 
   new_exit = single_dom_exit (loop);
-  update_exit_probability_after_unrolling (loop, new_exit);
+  /* gimple_duplicate_loop_body_to_header_edge depending on
+     DLTHE_FLAG_UPDATE_FREQ either keeps original frequency of the loop header
+     or scales it down accordingly.
+     However exit edge probability is kept as original.  Fix it if needed
+     and compensate.  */
+  update_loop_exit_probability_scale_dom_bbs (loop, new_exit);
   if (!single_loop_p)
     {
       /* Finally create the new counter for number of iterations and add
diff --git a/gcc/tree-ssa-loop-split.cc b/gcc/tree-ssa-loop-split.cc
index 641346cba70..923e49e716d 100644
--- a/gcc/tree-ssa-loop-split.cc
+++ b/gcc/tree-ssa-loop-split.cc
@@ -610,7 +610,6 @@ split_loop (class loop *loop1)
   for (i = 0; i < loop1->num_nodes; i++)
     if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv, &guard_code)))
       {
-	profile_count entry_count = loop_preheader_edge (loop1)->count ();
 	/* Handling opposite steps is not implemented yet.  Neither
 	   is handling different step sizes.  */
 	if ((tree_int_cst_sign_bit (iv.step)
@@ -692,48 +691,8 @@ split_loop (class loop *loop1)
 			= loop1_prob.invert ();
 
 	fix_loop_bb_probability (loop1, loop2, true_edge, false_edge);
-
-	/* Fix loop's exit probability after scaling.  */
-
-	if (entry_count.initialized_p () && entry_count.nonzero_p ())
-	  {
-	    edge exit_to_latch1;
-	    if (EDGE_SUCC (exit1->src, 0) == exit1)
-	      exit_to_latch1 = EDGE_SUCC (exit1->src, 1);
-	    else
-	      exit_to_latch1 = EDGE_SUCC (exit1->src, 0);
-	    if (exit1->src->count.nonzero_p ())
-	      {
-		/* First loop is entered loop1_prob * entry_count times
-		   and it needs to exit the same number of times.  */
-		exit1->probability
-			= entry_count.apply_probability
-				(loop1_prob).probability_in (exit1->src->count);
-		exit_to_latch1->probability = exit1->probability.invert ();
-		scale_dominated_blocks_in_loop (loop1, exit1->src,
-						exit_to_latch1->count (),
-						exit_to_latch1->dest->count);
-	      }
-
-	    edge exit_to_latch2, exit2 = single_exit (loop2);
-	    if (EDGE_SUCC (exit2->src, 0) == exit2)
-	      exit_to_latch2 = EDGE_SUCC (exit2->src, 1);
-	    else
-	      exit_to_latch2 = EDGE_SUCC (exit2->src, 0);
-	    if (exit2->src->count.nonzero_p ())
-	      {
-		/* Second loop is entered very_likely * entry_count times
-		   and it needs to exit the same number of times.  */
-		exit2->probability
-			= entry_count.apply_probability
-				(profile_probability::very_likely ())
-				.probability_in (exit2->src->count);
-		exit_to_latch2->probability = exit2->probability.invert ();
-		scale_dominated_blocks_in_loop (loop2, exit2->src,
-						exit_to_latch2->count (),
-						exit_to_latch2->dest->count);
-	      }
-	  }
+	update_loop_exit_probability_scale_dom_bbs (loop1);
+	update_loop_exit_probability_scale_dom_bbs (loop2);
 
 	edge new_e = connect_loops (loop1, loop2);
 	connect_loop_phis (loop1, loop2, new_e);