public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH 1/2] correct BB frequencies after loop changed
@ 2020-10-09 10:12 guojiufu
  2020-10-09 10:12 ` [PATCH 2/2] reset edge probibility and BB-count for peeled/unrolled loop guojiufu
  2020-11-17 22:07 ` [PATCH 1/2] correct BB frequencies after loop changed Jeff Law
  0 siblings, 2 replies; 20+ messages in thread
From: guojiufu @ 2020-10-09 10:12 UTC (permalink / raw)
  To: gcc-patches; +Cc: guojiufu, wschmidt, segher, dje.gcc

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>
COUNT<bb 10> != COUNT<bb2>

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

Bootstrap and regtest pass on ppc64le. Is this ok for trunk?

Jiufu

gcc/ChangeLog:
2020-10-09  Jiufu Guo   <guojiufu@linux.ibm.com>

	* cfgloopmanip.h (recompute_loop_frequencies): New function.
	* cfgloopmanip.c (recompute_loop_frequencies): New implementation.
	* tree-ssa-loop-manip.c (tree_transform_and_unroll_loop): Call
	recompute_loop_frequencies.

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

diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 73134a20e33..b0ca82a67fd 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -31,6 +31,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimplify-me.h"
 #include "tree-ssa-loop-manip.h"
 #include "dumpfile.h"
+#include "cfgrtl.h"
 
 static void copy_loops_to (class loop **, int,
 			   class loop *);
@@ -1773,3 +1774,55 @@ loop_version (class loop *loop,
 
   return nloop;
 }
+
+/* Recalculate the COUNTs of BBs in LOOP, if the probability of exit edge
+   is NEW_PROB.  */
+
+bool
+recompute_loop_frequencies (class loop *loop, profile_probability new_prob)
+{
+  edge exit = single_exit (loop);
+  if (!exit)
+    return false;
+
+  edge e;
+  edge_iterator ei;
+  edge non_exit;
+  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_prob);
+
+  /* Update BB counts in loop body.
+     COUNT<exit> = COUNT<preheader>
+     COUNT<exit> = COUNT<header> * exit_edge_probility
+     The COUNT<new_header> = COUNT<old_header> * old_exit_p / new_prob.  */
+  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 the BB besides exit edge (maybe latch).  */
+  FOR_EACH_EDGE (e, ei, exit->src->succs)
+    if (e != exit)
+      break;
+  non_exit = e;
+
+  non_exit->probability = new_prob.invert ();
+  non_exit->dest->count = profile_count::zero ();
+  FOR_EACH_EDGE (e, ei, non_exit->dest->preds)
+    non_exit->dest->count += e->src->count.apply_probability (e->probability);
+
+  /* Update probability and count of exit destination.  */
+  exit->probability = new_prob;
+  exit->dest->count = profile_count::zero ();
+  FOR_EACH_EDGE (e, ei, exit->dest->preds)
+    exit->dest->count += e->src->count.apply_probability (e->probability);
+
+  if (current_ir_type () != IR_GIMPLE)
+    update_br_prob_note (exit->src);
+
+  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,
-- 
2.25.1


^ permalink raw reply	[flat|nested] 20+ messages in thread
* Re: Ping: [PATCH 1/2] correct BB frequencies after loop changed
@ 2021-06-17  2:36 guojiufu
  0 siblings, 0 replies; 20+ messages in thread
From: guojiufu @ 2021-06-17  2:36 UTC (permalink / raw)
  To: Jan Hubicka
  Cc: Jan Hubicka, Richard Biener, segher, gcc-patches, Jeff Law,
	wschmidt, Jan Hubicka, dje.gcc, Gcc-patches

On 2021-06-15 12:57, guojiufu via Gcc-patches wrote:
> On 2021-06-14 17:16, Jan Hubicka wrote:
>>> 
>>> 
>>> On 5/6/2021 8:36 PM, guojiufu via Gcc-patches wrote:
>>> > Gentle ping.
>>> >
>>> > Original message:
>>> > https://gcc.gnu.org/pipermail/gcc-patches/2020-October/555871.html
>>> I think you need a more aggressive ping  :-)
>>> 
>>> OK for the trunk.  Sorry for the long delay.  I kept hoping someone 
>>> else
>>> would step in and look at it.
>> Sorry, the patch was on my todo list to think through for a while :(
>> It seems to me that both old and new code needs bit more work.  First
>> the exit loop frequency is set to
>> 
>>  prob = profile_probability::always ().apply_scale (1, new_est_niter + 
>> 1);
>> 
>> which is only correct if the estimated number of iterations is 
>> accurate.
>> If we do not have profile feedback and trip count is not known 
>> precisely
>> in most cases it won't be.  We estimate loops to iterate about 3 times
>> and then niter_for_unrolled_loop will apply the capping to 5 
>> iterations
>> that is completely arbitrary.
>> 
>> Forcing exit probability to precise may then disable futher loop
>> optimizations since after the change we will think we know the loop
>> iterates 5 times and thus it is not worthy for loop opt (which is 
>> quite
>> oposite with the fact that we are just unrolling it thinking it is 
>> hot).
> 
> Thanks, understand your concern, both new and old code are assuming the
> the number of iterations is accurate.
> Maybe we could add code to reset exit probability for the case
> where "!count_in.reliable_p ()".
> 
>> 
>> Old code does
>>  1) scale body down so only one iteration is done
>>  2) set exit edge probability to be 1/(new_est_iter+1)
>>     precisely
>>  3) scale up accoring to the 1/new_nonexit_prob
>>     which would be correct if the nonexit probability was updated to
>>     1-exit_probability but that does not seem to happen.
>> 
>> New code does
> Yes, this is intended: we know that the enter-count should be
> equal to the exit-count of one loop, and then the
> "loop-body-count * exit-probability = exit-count".
> Also, the entry count of the loop would not be changed before and after
> one optimization (or slightly change,e.g. peeling count).
> 
> Based on this, we could adjust the loop body count according to
> exit-count (or say enter-count) and exit-probability, when the
> exit-probability is easy to estimate.
> 
>>  1) give up when there are multiple exits.
>>     I wonder how common this is - we do outer loop vectorizaiton
> 
> The computation in the new code is based on a single exit. This is
> also a requirement of old code, and it would be true when run to here.

To support multiple exits, I'm thinking about the way to calculate the
count/probability for each basic_block and each exit edge.  While it 
seems
the count/prob may not scale up on the same ratio.  This is another 
reason
I give up these cases with multi-exits.

Any suggestions about supporting these cases?


BR,
Jiufu Guo

> 
>>  2) adjust loop body count according to the exit
>>  3) updat profile of BB after the exit edge.
>> 
> 
> 
>> Why do you need:
>> +  if (current_ir_type () != IR_GIMPLE)
>> +    update_br_prob_note (exit->src);
>> 
>> It is tree_transform_and_unroll_loop, so I think we should always have
>> IR_GIMPLE?
> 
> These two lines are added to "recompute_loop_frequencies" which can be 
> used
> in rtl, like the second patch of this:
> https://gcc.gnu.org/pipermail/gcc-patches/2020-October/555872.html
> Oh, maybe these two lines code would be put to 
> tree_transform_and_unroll_loop
> instead of common code recompute_loop_frequencies.
> 
> Thanks a lot for the review in your busy time!
> 
> BR.
> Jiufu Guo
>> 
>> Honza
>>> 
>>> jeff

^ permalink raw reply	[flat|nested] 20+ messages in thread
end of thread, other threads:[~2021-07-05  3:13 UTC | newest]

Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-09 10:12 [PATCH 1/2] correct BB frequencies after loop changed guojiufu
2020-10-09 10:12 ` [PATCH 2/2] reset edge probibility and BB-count for peeled/unrolled loop guojiufu
2020-11-12  3:03   ` Jiufu Guo
2020-12-02  5:26   ` Jeff Law
2020-11-17 22:07 ` [PATCH 1/2] correct BB frequencies after loop changed Jeff Law
2020-11-18  7:28   ` Richard Biener
2020-11-18 23:45     ` Jeff Law
2020-11-24  5:44       ` Jiufu Guo
2020-12-04  3:05         ` Jiufu Guo
2020-12-04  6:17           ` Jiufu Guo
2020-12-04  6:59             ` Martin Liška
2021-05-07  2:36               ` Ping: " guojiufu
2021-05-20  7:19                 ` Ping^1: " guojiufu
2021-06-07  2:37                   ` Ping^2: " guojiufu
2021-06-14  2:38                 ` Ping: " Jeff Law
2021-06-14  9:16                   ` Jan Hubicka
2021-06-15  4:57                     ` guojiufu
2021-06-18  8:24                       ` guojiufu
2021-07-05  3:13                         ` guojiufu
2021-06-17  2:36 guojiufu

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).