diff mbox series

[RFC] update COUNTs of BB in loop.

Message ID 20200922053747.426770-1-guojiufu@linux.ibm.com
State New
Headers show
Series [RFC] update COUNTs of BB in loop. | expand

Commit Message

Jiufu Guo Sept. 22, 2020, 5:37 a.m. UTC 
Hi,

When investigating the issue from https://gcc.gnu.org/pipermail/gcc-patches/2020-July/549786.html
I find the BB COUNTs of loop seems are not accurate in some case.
For example:

In below figure:


               COUNT:268435456<bb 2>  pre-header
                        |
                        |  .--------------------.
                        |  |                    |
                        V  v                    |
               COUNT:805306369<bb 3>            |
                       / \                      |
                   33%/   \                     |
                     /     \                    |
                    v       v                   |
COUNT:268435456<bb 10>  COUNT:536870911<bb 15>  | 
    exit-edge                 |   latch         |
                              ._________________.

Those COUNTs have below equations:
COUNT of exit-edge:268435456 = COUNT of pre-header:268435456
COUNT of exit-edge:268435456 = COUNT of header:805306369 * 33
COUNT of header:805306369 = COUNT of pre-header:268435456 + COUNT of latch:536870911


While after pcom:

               COUNT:268435456<bb 2>  pre-header
                        |
                        |  .--------------------.
                        |  |                    |
                        V  v                    |
               COUNT:268435456<bb 3>            |
                       / \                      |
                   50%/   \                     |
                     /     \                    |
                    v       v                   |
COUNT:134217728<bb 10>  COUNT:134217728<bb 15>  | 
    exit-edge                 |   latch         |
                              ._________________.

COUNT<bb 3> != COUNT<bb 2> + COUNT<bb 15>

In some cases, the probility of exit-edge is easy to estimate, then
those COUNTs of other BBs in loop can be re-caculated.

Below is a patch to reset COUNTs as above description.

Thanks for comments!!

Jiufu

---
 gcc/cfgloopmanip.c        | 43 +++++++++++++++++++++++++++++++++++++++
 gcc/cfgloopmanip.h        |  2 +-
 gcc/tree-ssa-loop-manip.c | 28 +++----------------------
 3 files changed, 47 insertions(+), 26 deletions(-)

Comments

Martin Liška Sept. 22, 2020, 8:10 a.m. UTC | #1 
On 9/22/20 7:37 AM, guojiufu wrote:
> Thanks for comments!!

Thanks for the patch. I can confirm it is NO-OP for SPEC2006 benchmarks.

Martin
Segher Boessenkool Sept. 22, 2020, 3:46 p.m. UTC | #2 
Hi!

(Just some random things; the change itself looks fine afaics.)

On Tue, Sep 22, 2020 at 01:37:47PM +0800, guojiufu wrote:
> While after pcom:
> 
>                COUNT:268435456<bb 2>  pre-header
>                         |
>                         |  .--------------------.
>                         |  |                    |
>                         V  v                    |
>                COUNT:268435456<bb 3>            |
>                        / \                      |
>                    50%/   \                     |
>                      /     \                    |
>                     v       v                   |
> COUNT:134217728<bb 10>  COUNT:134217728<bb 15>  | 
>     exit-edge                 |   latch         |
>                               ._________________.
> 
> COUNT<bb 3> != COUNT<bb 2> + COUNT<bb 15>

And  COUNT<bb 10> != COUNT<bb2>  which does not make any sense.

> +/* Recacluate the COUNTs of BBs in LOOP, if the probility of exit edge
> +   is NEW_EXIT_P.  */

"Recalculate", "probability".  I would say "where the probability of the
single exit edge is NEW_EXIT_P".  But, _P means this is a predicate, and
it isn't (only function can be predicates, by definition).
"new_exit_prob" maybe?

> +  /* Update BB counts in loop body.
> +     COUNT<exit> = COUNT<pre-header>
> +     COUNT<exit> = COUNT<header> * exit_edge_probility
> +     The COUNT<new_header>=COUNT<old_header> * old_exit_p / new_exit_p.  */

Spaces around the "=" please?


Segher
diff mbox series

Patch

diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 73134a20e33..180916b0974 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -1773,3 +1773,46 @@  loop_version (class loop *loop,
 
   return nloop;
 }
+
+/* Recacluate the COUNTs of BBs in LOOP, if the probility of exit edge
+   is NEW_EXIT_P.  */
+
+bool
+recompute_loop_frequencies (class loop *loop, profile_probability new_exit_p)
+{
+  edge exit = single_exit (loop);
+  if (!exit)
+    return false;
+
+  basic_block * bbs;
+  profile_count exit_count = loop_preheader_edge (loop)->count ();
+  profile_probability exit_p = exit_count.probability_in (loop->header->count);
+  profile_count base_count = loop->header->count;
+  profile_count after_num = base_count.apply_probability (exit_p);
+  profile_count after_den = base_count.apply_probability (new_exit_p);
+
+  /* Update BB counts in loop body.
+     COUNT<exit> = COUNT<pre-header>
+     COUNT<exit> = COUNT<header> * exit_edge_probility
+     The COUNT<new_header>=COUNT<old_header> * old_exit_p / new_exit_p.  */
+  bbs = get_loop_body (loop);
+  scale_bbs_frequencies_profile_count (bbs, loop->num_nodes, after_num,
+						     after_den);
+  free (bbs);
+
+  /* Update probability and count of latch.  */
+  edge new_nonexit = single_pred_edge (loop->latch);
+  new_nonexit->probability = new_exit_p.invert ();
+  loop->latch->count
+    = loop->header->count.apply_probability (new_nonexit->probability);
+
+  /* Update probability and count of exit destination.  */
+  edge e;
+  edge_iterator ei;
+  exit->probability = new_exit_p;
+  exit->dest->count = profile_count::zero ();
+  FOR_EACH_EDGE (e, ei, exit->dest->preds)
+    exit->dest->count += e->src->count.apply_probability (e->probability);
+
+  return true;
+}
diff --git a/gcc/cfgloopmanip.h b/gcc/cfgloopmanip.h
index 7331e574e2f..d55bab17f65 100644
--- a/gcc/cfgloopmanip.h
+++ b/gcc/cfgloopmanip.h
@@ -62,5 +62,5 @@  class loop * loop_version (class loop *, void *,
 			    basic_block *,
 			    profile_probability, profile_probability,
 			    profile_probability, profile_probability, bool);
-
+extern bool recompute_loop_frequencies (class loop *, profile_probability);
 #endif /* GCC_CFGLOOPMANIP_H */
diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index a2717a411a3..4060d601cf8 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -1251,7 +1251,6 @@  tree_transform_and_unroll_loop (class loop *loop, unsigned factor,
   bool ok;
   unsigned i;
   profile_probability prob, prob_entry, scale_unrolled;
-  profile_count freq_e, freq_h;
   gcov_type new_est_niter = niter_for_unrolled_loop (loop, factor);
   unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
   auto_vec<edge> to_remove;
@@ -1393,33 +1392,12 @@  tree_transform_and_unroll_loop (class loop *loop, unsigned factor,
      number of iterations, and change the probability of the new
      exit edge.  */
 
-  freq_h = loop->header->count;
-  freq_e = (loop_preheader_edge (loop))->count ();
-  if (freq_h.nonzero_p ())
-    {
-      /* Avoid dropping loop body profile counter to 0 because of zero count
-	 in loop's preheader.  */
-      if (freq_h.nonzero_p () && !(freq_e == profile_count::zero ()))
-        freq_e = freq_e.force_nonzero ();
-      scale_loop_frequencies (loop, freq_e.probability_in (freq_h));
-    }
-
-  exit_bb = single_pred (loop->latch);
-  new_exit = find_edge (exit_bb, rest);
-  new_exit->probability = profile_probability::always ()
-				.apply_scale (1, new_est_niter + 1);
-
-  rest->count += new_exit->count ();
-
-  new_nonexit = single_pred_edge (loop->latch);
-  prob = new_nonexit->probability;
-  new_nonexit->probability = new_exit->probability.invert ();
-  prob = new_nonexit->probability / prob;
-  if (prob.initialized_p ())
-    scale_bbs_frequencies (&loop->latch, 1, prob);
+  prob = profile_probability::always ().apply_scale (1, new_est_niter + 1);
+  recompute_loop_frequencies (loop, prob);
 
   /* Finally create the new counter for number of iterations and add the new
      exit instruction.  */
+  exit_bb = single_pred (loop->latch);
   bsi = gsi_last_nondebug_bb (exit_bb);
   exit_if = as_a <gcond *> (gsi_stmt (bsi));
   create_iv (exit_base, exit_step, NULL_TREE, loop,