[PATCH AutoFDO/4]Fix profile count computation/propagation.

[PATCH AutoFDO/4]Fix profile count computation/propagation.

[bin.cheng]

[-- Attachment #1: Type: text/plain, Size: 1769 bytes --]

Hi,
This patch fixes AutoFDO breakage on trunk.  The main reason for breakage is AutoFDO
relies on standalone edge count computing and propagating profile count/probability info
on CFG, but in new infra, edge count is actually computed from probability, which leads
to chicken-egg problem and corrupted profile count.  This patch fixes the issue by using
explicit edge count.

There is another issue not touched yet that, in quite common case, profiled samples are
not enough and profile info computed for lots of blocks is ZERO.  In the future, we may
add some heuristics checking quality of sampled counts and reverting to guessed profile
count if necessary.  I think change made in this patch is also needed for that.

Package mysql server is used in test of this patch set.  It can't be compiled with autofdo
on trunk, even with compilation issues worked-around, there isn't performance improvement.
I local experiments, with this patch set it's improved by 12.3%, 4.3% irrespectively for
read-only/write-heavy benchmarks.  Unfortunately,  this patch set was written against
GCC 8 branch a while ago, improvement gets worse on trunk and I haven't investigated
the reason yet.  I guess there are still other issues which need to be fixed in the future.

Bootstrap and test on x86_64 in patch set.  Is it OK?

Thanks,
bin
2018-10-31  Bin Cheng  <bin.cheng@linux.alibaba.com>

	* auto-profile.c (AFDO_EINFO): New macro.
	(struct edge_info): New structure.
	(is_edge_annotated, set_edge_annotated): Delete.
	(afdo_propagate_edge, afdo_propagate_circuit, afdo_propagate): Remove
	parameter.  Adjust edge count computation and annotation using struct
	edge_info.
	(afdo_calculate_branch_prob): Ditto.
	(afdo_annotate_cfg): Simplify code setting basic block profile count.

[-- Attachment #2: 0004-Fix-AutoFDO-breakage-after-profile-count-rewriting.patch --]
[-- Type: application/octet-stream, Size: 11523 bytes --]

From 6506c12d1b633b6d1bfae839b3633a4f99b3a481 Mon Sep 17 00:00:00 2001
From: chengbin <bin.cheng@linux.alibaba.com>
Date: Mon, 20 Aug 2018 15:25:02 +0800
Subject: [PATCH 4/4] Fix AutoFDO breakage after profile count rewriting.

---
 gcc/auto-profile.c | 190 ++++++++++++++++++++++++++---------------------------
 1 file changed, 95 insertions(+), 95 deletions(-)

diff --git a/gcc/auto-profile.c b/gcc/auto-profile.c
index cde4f41c1d9..ff3ea23d830 100644
--- a/gcc/auto-profile.c
+++ b/gcc/auto-profile.c
@@ -101,6 +101,17 @@ along with GCC; see the file COPYING3.  If not see
 namespace autofdo
 {
 
+/* Intermediate edge info used when propagating AutoFDO profile information.
+   We can't edge->count() directly since it's computed from edge's probability
+   while probability is yet not decided during propagation.  */
+#define AFDO_EINFO(e)                     ((struct edge_info *) e->aux)
+struct edge_info
+{
+  edge_info () : count (profile_count::zero ().afdo ()), annotated_p (false) {}
+  profile_count count;
+  bool annotated_p;
+};
+
 /* Represent a source location: (function_decl, lineno).  */
 typedef std::pair<tree, unsigned> decl_lineno;
 
@@ -1067,18 +1078,6 @@ set_bb_annotated (basic_block bb, bb_set *annotated)
   annotated->insert (bb);
 }
 
-static bool
-is_edge_annotated (const edge e, const edge_set &annotated)
-{
-  return annotated.find (e) != annotated.end ();
-}
-
-static void
-set_edge_annotated (edge e, edge_set *annotated)
-{
-  annotated->insert (e);
-}
-
 /* For a given BB, set its execution count. Attach value profile if a stmt
    is not in PROMOTED, because we only want to promote an indirect call once.
    Return TRUE if BB is annotated.  */
@@ -1188,12 +1187,11 @@ afdo_find_equiv_class (bb_set *annotated_bb)
    edges' counts are known, then the basic block's unknown count can also be
    calculated.
    IS_SUCC is true if out edges of a basic blocks are examined.
-   Update ANNOTATED_BB and ANNOTATED_EDGE accordingly.
+   Update ANNOTATED_BB accordingly.
    Return TRUE if any basic block/edge count is changed.  */
 
 static bool
-afdo_propagate_edge (bool is_succ, bb_set *annotated_bb,
-                     edge_set *annotated_edge)
+afdo_propagate_edge (bool is_succ, bb_set *annotated_bb)
 {
   basic_block bb;
   bool changed = false;
@@ -1206,30 +1204,30 @@ afdo_propagate_edge (bool is_succ, bb_set *annotated_bb,
     profile_count total_known_count = profile_count::zero ().afdo ();
 
     FOR_EACH_EDGE (e, ei, is_succ ? bb->succs : bb->preds)
-      if (!is_edge_annotated (e, *annotated_edge))
-	num_unknown_edge++, unknown_edge = e;
-      else
-	total_known_count += e->count ();
+      {
+	gcc_assert (AFDO_EINFO (e) != NULL);
+	if (! AFDO_EINFO (e)->annotated_p)
+	  num_unknown_edge++, unknown_edge = e;
+	else
+	  total_known_count += AFDO_EINFO (e)->count;
+      }
 
-    if (num_unknown_edge == 0)
+    /* Be careful not to annotate block with no successor in special cases.  */
+    if (num_unknown_edge == 0 && total_known_count > bb->count)
       {
-        if (total_known_count > bb->count)
-          {
-            bb->count = total_known_count;
-            changed = true;
-          }
-        if (!is_bb_annotated (bb, *annotated_bb))
-          {
-            set_bb_annotated (bb, annotated_bb);
-            changed = true;
-          }
+	bb->count = total_known_count;
+	if (!is_bb_annotated (bb, *annotated_bb))
+	  set_bb_annotated (bb, annotated_bb);
+	changed = true;
       }
     else if (num_unknown_edge == 1 && is_bb_annotated (bb, *annotated_bb))
       {
-        unknown_edge->probability
-	  = total_known_count.probability_in (bb->count);
-        set_edge_annotated (unknown_edge, annotated_edge);
-        changed = true;
+	if (bb->count > total_known_count)
+	  AFDO_EINFO (unknown_edge)->count = bb->count - total_known_count;
+	else
+	  AFDO_EINFO (unknown_edge)->count = profile_count::zero ().afdo ();
+	AFDO_EINFO (unknown_edge)->annotated_p = true;
+	changed = true;
       }
   }
   return changed;
@@ -1265,11 +1263,10 @@ afdo_propagate_edge (bool is_succ, bb_set *annotated_bb,
        goto BB3
 
    In this case, we need to propagate through PHI to determine the edge
-   count of BB1->BB.t1, BB.t1->BB.t2.
-   Update ANNOTATED_EDGE accordingly.  */
+   count of BB1->BB.t1, BB.t1->BB.t2.  */
 
 static void
-afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
+afdo_propagate_circuit (const bb_set &annotated_bb)
 {
   basic_block bb;
   FOR_ALL_BB_FN (bb, cfun)
@@ -1308,7 +1305,7 @@ afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
       bool check_value_one = (((integer_onep (cmp_rhs))
                                ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
                               ^ ((e->flags & EDGE_TRUE_VALUE) != 0));
-      if (!is_edge_annotated (e, *annotated_edge))
+      if (! AFDO_EINFO (e)->annotated_p)
         continue;
       for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
         {
@@ -1322,17 +1319,17 @@ afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
             continue;
           total++;
           only_one = ep;
-          if (!e->probability.initialized_p ()
-	      && !is_edge_annotated (ep, *annotated_edge))
+          if (AFDO_EINFO (e)->count == profile_count::zero ()
+	      && ! AFDO_EINFO (ep)->annotated_p)
             {
-              ep->probability = profile_probability::never ().afdo ();
-              set_edge_annotated (ep, annotated_edge);
+              AFDO_EINFO (ep)->count = profile_count::zero ().afdo ();
+	      AFDO_EINFO (ep)->annotated_p = true;
             }
         }
-      if (total == 1 && !is_edge_annotated (only_one, *annotated_edge))
+      if (total == 1 && ! AFDO_EINFO (only_one)->annotated_p)
         {
-          only_one->probability = e->probability;
-          set_edge_annotated (only_one, annotated_edge);
+          AFDO_EINFO (only_one)->count = AFDO_EINFO (e)->count;
+	  AFDO_EINFO (only_one)->annotated_p = true;
         }
     }
   }
@@ -1342,7 +1339,7 @@ afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
    graph. We do the propagation iteratively until stablize.  */
 
 static void
-afdo_propagate (bb_set *annotated_bb, edge_set *annotated_edge)
+afdo_propagate (bb_set *annotated_bb)
 {
   basic_block bb;
   bool changed = true;
@@ -1359,11 +1356,11 @@ afdo_propagate (bb_set *annotated_bb, edge_set *annotated_edge)
     {
       changed = false;
 
-      if (afdo_propagate_edge (true, annotated_bb, annotated_edge))
+      if (afdo_propagate_edge (true, annotated_bb))
         changed = true;
-      if (afdo_propagate_edge (false, annotated_bb, annotated_edge))
+      if (afdo_propagate_edge (false, annotated_bb))
         changed = true;
-      afdo_propagate_circuit (*annotated_bb, annotated_edge);
+      afdo_propagate_circuit (*annotated_bb);
     }
 }
 
@@ -1371,52 +1368,58 @@ afdo_propagate (bb_set *annotated_bb, edge_set *annotated_edge)
    probabilities.  */
 
 static void
-afdo_calculate_branch_prob (bb_set *annotated_bb, edge_set *annotated_edge)
+afdo_calculate_branch_prob (bb_set *annotated_bb)
 {
+  edge e;
+  edge_iterator ei;
   basic_block bb;
-  bool has_sample = false;
-
-  FOR_EACH_BB_FN (bb, cfun)
-  {
-    if (bb->count > profile_count::zero ())
-      {
-	has_sample = true;
-	break;
-      }
-  }
-
-  if (!has_sample)
-    return;
 
   calculate_dominance_info (CDI_POST_DOMINATORS);
   calculate_dominance_info (CDI_DOMINATORS);
   loop_optimizer_init (0);
 
+  FOR_ALL_BB_FN (bb, cfun)
+    {
+      gcc_assert (bb->aux == NULL);
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	{
+	  gcc_assert (e->aux == NULL);
+	  e->aux = new edge_info ();
+	}
+    }
+
   afdo_find_equiv_class (annotated_bb);
-  afdo_propagate (annotated_bb, annotated_edge);
+  afdo_propagate (annotated_bb);
 
   FOR_EACH_BB_FN (bb, cfun)
   {
-    edge e;
-    edge_iterator ei;
     int num_unknown_succ = 0;
     profile_count total_count = profile_count::zero ().afdo ();
 
     FOR_EACH_EDGE (e, ei, bb->succs)
     {
-      if (!is_edge_annotated (e, *annotated_edge))
+      gcc_assert (AFDO_EINFO (e) != NULL);
+      if (! AFDO_EINFO (e)->annotated_p)
         num_unknown_succ++;
       else
-        total_count += e->count ();
+        total_count += AFDO_EINFO (e)->count;
     }
     if (num_unknown_succ == 0 && total_count > profile_count::zero ())
       {
         FOR_EACH_EDGE (e, ei, bb->succs)
-          e->probability = e->count ().probability_in (total_count);
+          e->probability = AFDO_EINFO (e)->count.probability_in (total_count);
       }
   }
   FOR_ALL_BB_FN (bb, cfun)
-    bb->aux = NULL;
+    {
+      bb->aux = NULL;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (AFDO_EINFO (e) != NULL)
+	  {
+	    delete AFDO_EINFO (e);
+	    e->aux = NULL;
+	  }
+    }
 
   loop_optimizer_finalize ();
   free_dominance_info (CDI_DOMINATORS);
@@ -1496,36 +1499,33 @@ afdo_annotate_cfg (const stmt_set &promoted_stmts)
 {
   basic_block bb;
   bb_set annotated_bb;
-  edge_set annotated_edge;
   const function_instance *s
       = afdo_source_profile->get_function_instance_by_decl (
           current_function_decl);
 
   if (s == NULL)
     return;
+
+  profile_count max_count = profile_count::zero ().afdo ();
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      /* As autoFDO uses sampling approach, we have to assume that all
+	 counters are zero when not seen by autoFDO.  */
+      bb->count = profile_count::zero ().afdo ();
+      if (afdo_set_bb_count (bb, promoted_stmts))
+	set_bb_annotated (bb, &annotated_bb);
+      if (bb->count > max_count)
+	max_count = bb->count;
+    }
+  if (max_count == profile_count::zero ())
+    return;
+
   cgraph_node::get (current_function_decl)->count
      = profile_count::from_gcov_type (s->head_count ()).afdo ();
   ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
      = profile_count::from_gcov_type (s->head_count ()).afdo ();
   EXIT_BLOCK_PTR_FOR_FN (cfun)->count = profile_count::zero ().afdo ();
-  profile_count max_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
-
-  FOR_EACH_BB_FN (bb, cfun)
-  {
-    edge e;
-    edge_iterator ei;
-
-    /* As autoFDO uses sampling approach, we have to assume that all
-       counters are zero when not seen by autoFDO.  */
-    bb->count = profile_count::zero ().afdo ();
-    FOR_EACH_EDGE (e, ei, bb->succs)
-      e->probability = profile_probability::uninitialized ();
-
-    if (afdo_set_bb_count (bb, promoted_stmts))
-      set_bb_annotated (bb, &annotated_bb);
-    if (bb->count > max_count)
-      max_count = bb->count;
-  }
   if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
       > ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count)
     {
@@ -1544,12 +1544,12 @@ afdo_annotate_cfg (const stmt_set &promoted_stmts)
       DECL_SOURCE_LOCATION (current_function_decl));
   afdo_source_profile->mark_annotated (cfun->function_start_locus);
   afdo_source_profile->mark_annotated (cfun->function_end_locus);
-  if (max_count > profile_count::zero ())
-    {
-      afdo_calculate_branch_prob (&annotated_bb, &annotated_edge);
-      update_max_bb_count ();
-      profile_status_for_fn (cfun) = PROFILE_READ;
-    }
+
+  /* Calculate, propagate count and probability information on CFG.  */
+  afdo_calculate_branch_prob (&annotated_bb);
+  update_max_bb_count ();
+  profile_status_for_fn (cfun) = PROFILE_READ;
+
   if (flag_value_profile_transformations)
     {
       gimple_value_profile_transformations ();
-- 
2.14.4.44.g2045bb6

Re: [PATCH AutoFDO/4]Fix profile count computation/propagation.

[Jeff Law]

On 10/31/18 12:34 AM, bin.cheng wrote:
> Hi,
> This patch fixes AutoFDO breakage on trunk.  The main reason for breakage is AutoFDO
> relies on standalone edge count computing and propagating profile count/probability info
> on CFG, but in new infra, edge count is actually computed from probability, which leads
> to chicken-egg problem and corrupted profile count.  This patch fixes the issue by using
> explicit edge count.
> 
> There is another issue not touched yet that, in quite common case, profiled samples are
> not enough and profile info computed for lots of blocks is ZERO.  In the future, we may
> add some heuristics checking quality of sampled counts and reverting to guessed profile
> count if necessary.  I think change made in this patch is also needed for that.
> 
> Package mysql server is used in test of this patch set.  It can't be compiled with autofdo
> on trunk, even with compilation issues worked-around, there isn't performance improvement.
> I local experiments, with this patch set it's improved by 12.3%, 4.3% irrespectively for
> read-only/write-heavy benchmarks.  Unfortunately,  this patch set was written against
> GCC 8 branch a while ago, improvement gets worse on trunk and I haven't investigated
> the reason yet.  I guess there are still other issues which need to be fixed in the future.
> 
> Bootstrap and test on x86_64 in patch set.  Is it OK?
> 
> Thanks,
> bin
> 2018-10-31  Bin Cheng  <bin.cheng@linux.alibaba.com>
> 
> 	* auto-profile.c (AFDO_EINFO): New macro.
> 	(struct edge_info): New structure.
> 	(is_edge_annotated, set_edge_annotated): Delete.
> 	(afdo_propagate_edge, afdo_propagate_circuit, afdo_propagate): Remove
> 	parameter.  Adjust edge count computation and annotation using struct
> 	edge_info.
> 	(afdo_calculate_branch_prob): Ditto.
> 	(afdo_annotate_cfg): Simplify code setting basic block profile count.
> 
> 
> 0004-Fix-AutoFDO-breakage-after-profile-count-rewriting.patch
> 
> From 6506c12d1b633b6d1bfae839b3633a4f99b3a481 Mon Sep 17 00:00:00 2001
> From: chengbin <bin.cheng@linux.alibaba.com>
> Date: Mon, 20 Aug 2018 15:25:02 +0800
> Subject: [PATCH 4/4] Fix AutoFDO breakage after profile count rewriting.
> 
> ---
>  gcc/auto-profile.c | 190 ++++++++++++++++++++++++++---------------------------
>  1 file changed, 95 insertions(+), 95 deletions(-)
> 
> diff --git a/gcc/auto-profile.c b/gcc/auto-profile.c
> index cde4f41c1d9..ff3ea23d830 100644
> --- a/gcc/auto-profile.c
> +++ b/gcc/auto-profile.c
> @@ -101,6 +101,17 @@ along with GCC; see the file COPYING3.  If not see
>  namespace autofdo
>  {
>  
> +/* Intermediate edge info used when propagating AutoFDO profile information.
> +   We can't edge->count() directly since it's computed from edge's probability
> +   while probability is yet not decided during propagation.  */
> +#define AFDO_EINFO(e)                     ((struct edge_info *) e->aux)
> +struct edge_info
> +{
> +  edge_info () : count (profile_count::zero ().afdo ()), annotated_p (false) {}
> +  profile_count count;
> +  bool annotated_p;
> +};
edge_info isn't POD, so make it a class rather than a struct.

OK with that change assuming it does not have a hard dependency on prior
patches in this series.

jeff

Re: [PATCH AutoFDO/4]Fix profile count computation/propagation.

[Bin.Cheng]

[-- Attachment #1: Type: text/plain, Size: 4087 bytes --]

On Thu, Nov 8, 2018 at 6:33 AM Jeff Law <law@redhat.com> wrote:
>
> On 10/31/18 12:34 AM, bin.cheng wrote:
> > Hi,
> > This patch fixes AutoFDO breakage on trunk.  The main reason for breakage is AutoFDO
> > relies on standalone edge count computing and propagating profile count/probability info
> > on CFG, but in new infra, edge count is actually computed from probability, which leads
> > to chicken-egg problem and corrupted profile count.  This patch fixes the issue by using
> > explicit edge count.
> >
> > There is another issue not touched yet that, in quite common case, profiled samples are
> > not enough and profile info computed for lots of blocks is ZERO.  In the future, we may
> > add some heuristics checking quality of sampled counts and reverting to guessed profile
> > count if necessary.  I think change made in this patch is also needed for that.
> >
> > Package mysql server is used in test of this patch set.  It can't be compiled with autofdo
> > on trunk, even with compilation issues worked-around, there isn't performance improvement.
> > I local experiments, with this patch set it's improved by 12.3%, 4.3% irrespectively for
> > read-only/write-heavy benchmarks.  Unfortunately,  this patch set was written against
> > GCC 8 branch a while ago, improvement gets worse on trunk and I haven't investigated
> > the reason yet.  I guess there are still other issues which need to be fixed in the future.
> >
> > Bootstrap and test on x86_64 in patch set.  Is it OK?
> >
> > Thanks,
> > bin
> > 2018-10-31  Bin Cheng  <bin.cheng@linux.alibaba.com>
> >
> >       * auto-profile.c (AFDO_EINFO): New macro.
> >       (struct edge_info): New structure.
> >       (is_edge_annotated, set_edge_annotated): Delete.
> >       (afdo_propagate_edge, afdo_propagate_circuit, afdo_propagate): Remove
> >       parameter.  Adjust edge count computation and annotation using struct
> >       edge_info.
> >       (afdo_calculate_branch_prob): Ditto.
> >       (afdo_annotate_cfg): Simplify code setting basic block profile count.
> >
> >
> > 0004-Fix-AutoFDO-breakage-after-profile-count-rewriting.patch
> >
> > From 6506c12d1b633b6d1bfae839b3633a4f99b3a481 Mon Sep 17 00:00:00 2001
> > From: chengbin <bin.cheng@linux.alibaba.com>
> > Date: Mon, 20 Aug 2018 15:25:02 +0800
> > Subject: [PATCH 4/4] Fix AutoFDO breakage after profile count rewriting.
> >
> > ---
> >  gcc/auto-profile.c | 190 ++++++++++++++++++++++++++---------------------------
> >  1 file changed, 95 insertions(+), 95 deletions(-)
> >
> > diff --git a/gcc/auto-profile.c b/gcc/auto-profile.c
> > index cde4f41c1d9..ff3ea23d830 100644
> > --- a/gcc/auto-profile.c
> > +++ b/gcc/auto-profile.c
> > @@ -101,6 +101,17 @@ along with GCC; see the file COPYING3.  If not see
> >  namespace autofdo
> >  {
> >
> > +/* Intermediate edge info used when propagating AutoFDO profile information.
> > +   We can't edge->count() directly since it's computed from edge's probability
> > +   while probability is yet not decided during propagation.  */
> > +#define AFDO_EINFO(e)                     ((struct edge_info *) e->aux)
> > +struct edge_info
> > +{
> > +  edge_info () : count (profile_count::zero ().afdo ()), annotated_p (false) {}
> > +  profile_count count;
> > +  bool annotated_p;
> > +};
> edge_info isn't POD, so make it a class rather than a struct.
>
> OK with that change assuming it does not have a hard dependency on prior
> patches in this series.
Thanks very much for review.  Now that all prerequisite patches are
approved and committed, I update this one by making edge_info a class
as suggested.
Bootstrap and test as before, is it OK?

Thanks,
bin

2018-12-11  Bin Cheng  <bin.cheng@linux.alibaba.com>

        * auto-profile.c (AFDO_EINFO): New macro.
        (class edge_info): New class.
        (is_edge_annotated, set_edge_annotated): Delete.
        (afdo_propagate_edge, afdo_propagate_circuit, afdo_propagate): Remove
        parameter.  Adjust edge count computation and annotation using class
        edge_info.
        (afdo_calculate_branch_prob, afdo_annotate_cfg): Likewise.

[-- Attachment #2: 0003-Fix-AutoFDO-breakage-after-profile-count-rewriting.patch --]
[-- Type: application/octet-stream, Size: 11160 bytes --]

From db60fc862bcc3a30cd8c29cfd2dc0cb806c3b33f Mon Sep 17 00:00:00 2001
From: chengbin <bin.cheng@linux.alibaba.com>
Date: Mon, 20 Aug 2018 15:25:02 +0800
Subject: [PATCH 3/5] Fix AutoFDO breakage after profile count rewriting.

---
 gcc/auto-profile.c | 190 +++++++++++++++++++++++++++--------------------------
 1 file changed, 97 insertions(+), 93 deletions(-)

diff --git a/gcc/auto-profile.c b/gcc/auto-profile.c
index cde4f41c1d9..7e0020bc232 100644
--- a/gcc/auto-profile.c
+++ b/gcc/auto-profile.c
@@ -101,6 +101,23 @@ along with GCC; see the file COPYING3.  If not see
 namespace autofdo
 {
 
+/* Intermediate edge info used when propagating AutoFDO profile information.
+   We can't edge->count() directly since it's computed from edge's probability
+   while probability is yet not decided during propagation.  */
+#define AFDO_EINFO(e)                     ((struct edge_info *) e->aux)
+class edge_info
+{
+public:
+  edge_info () : count_ (profile_count::zero ().afdo ()), annotated_ (false) {}
+  bool is_annotated () const { return annotated_; }
+  void set_annotated () { annotated_ = true; }
+  profile_count get_count () const { return count_; }
+  void set_count (profile_count count) { count_ = count; }
+private:
+  profile_count count_;
+  bool annotated_;
+};
+
 /* Represent a source location: (function_decl, lineno).  */
 typedef std::pair<tree, unsigned> decl_lineno;
 
@@ -1067,18 +1084,6 @@ set_bb_annotated (basic_block bb, bb_set *annotated)
   annotated->insert (bb);
 }
 
-static bool
-is_edge_annotated (const edge e, const edge_set &annotated)
-{
-  return annotated.find (e) != annotated.end ();
-}
-
-static void
-set_edge_annotated (edge e, edge_set *annotated)
-{
-  annotated->insert (e);
-}
-
 /* For a given BB, set its execution count. Attach value profile if a stmt
    is not in PROMOTED, because we only want to promote an indirect call once.
    Return TRUE if BB is annotated.  */
@@ -1188,12 +1193,11 @@ afdo_find_equiv_class (bb_set *annotated_bb)
    edges' counts are known, then the basic block's unknown count can also be
    calculated.
    IS_SUCC is true if out edges of a basic blocks are examined.
-   Update ANNOTATED_BB and ANNOTATED_EDGE accordingly.
+   Update ANNOTATED_BB accordingly.
    Return TRUE if any basic block/edge count is changed.  */
 
 static bool
-afdo_propagate_edge (bool is_succ, bb_set *annotated_bb,
-                     edge_set *annotated_edge)
+afdo_propagate_edge (bool is_succ, bb_set *annotated_bb)
 {
   basic_block bb;
   bool changed = false;
@@ -1206,30 +1210,30 @@ afdo_propagate_edge (bool is_succ, bb_set *annotated_bb,
     profile_count total_known_count = profile_count::zero ().afdo ();
 
     FOR_EACH_EDGE (e, ei, is_succ ? bb->succs : bb->preds)
-      if (!is_edge_annotated (e, *annotated_edge))
-	num_unknown_edge++, unknown_edge = e;
-      else
-	total_known_count += e->count ();
+      {
+	gcc_assert (AFDO_EINFO (e) != NULL);
+	if (! AFDO_EINFO (e)->is_annotated ())
+	  num_unknown_edge++, unknown_edge = e;
+	else
+	  total_known_count += AFDO_EINFO (e)->get_count ();
+      }
 
-    if (num_unknown_edge == 0)
+    /* Be careful not to annotate block with no successor in special cases.  */
+    if (num_unknown_edge == 0 && total_known_count > bb->count)
       {
-        if (total_known_count > bb->count)
-          {
-            bb->count = total_known_count;
-            changed = true;
-          }
-        if (!is_bb_annotated (bb, *annotated_bb))
-          {
-            set_bb_annotated (bb, annotated_bb);
-            changed = true;
-          }
+	bb->count = total_known_count;
+	if (!is_bb_annotated (bb, *annotated_bb))
+	  set_bb_annotated (bb, annotated_bb);
+	changed = true;
       }
     else if (num_unknown_edge == 1 && is_bb_annotated (bb, *annotated_bb))
       {
-        unknown_edge->probability
-	  = total_known_count.probability_in (bb->count);
-        set_edge_annotated (unknown_edge, annotated_edge);
-        changed = true;
+	if (bb->count > total_known_count)
+	  AFDO_EINFO (unknown_edge)->set_count (bb->count - total_known_count);
+	else
+	  AFDO_EINFO (unknown_edge)->set_count (profile_count::zero().afdo ());
+	AFDO_EINFO (unknown_edge)->set_annotated ();
+	changed = true;
       }
   }
   return changed;
@@ -1265,11 +1269,10 @@ afdo_propagate_edge (bool is_succ, bb_set *annotated_bb,
        goto BB3
 
    In this case, we need to propagate through PHI to determine the edge
-   count of BB1->BB.t1, BB.t1->BB.t2.
-   Update ANNOTATED_EDGE accordingly.  */
+   count of BB1->BB.t1, BB.t1->BB.t2.  */
 
 static void
-afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
+afdo_propagate_circuit (const bb_set &annotated_bb)
 {
   basic_block bb;
   FOR_ALL_BB_FN (bb, cfun)
@@ -1308,7 +1311,7 @@ afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
       bool check_value_one = (((integer_onep (cmp_rhs))
                                ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
                               ^ ((e->flags & EDGE_TRUE_VALUE) != 0));
-      if (!is_edge_annotated (e, *annotated_edge))
+      if (! AFDO_EINFO (e)->is_annotated ())
         continue;
       for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
         {
@@ -1322,18 +1325,18 @@ afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
             continue;
           total++;
           only_one = ep;
-          if (!e->probability.initialized_p ()
-	      && !is_edge_annotated (ep, *annotated_edge))
-            {
-              ep->probability = profile_probability::never ().afdo ();
-              set_edge_annotated (ep, annotated_edge);
-            }
-        }
-      if (total == 1 && !is_edge_annotated (only_one, *annotated_edge))
-        {
-          only_one->probability = e->probability;
-          set_edge_annotated (only_one, annotated_edge);
-        }
+          if (! (AFDO_EINFO (e)->get_count ()).nonzero_p ()
+	      && ! AFDO_EINFO (ep)->is_annotated ())
+	    {
+	      AFDO_EINFO (ep)->set_count (profile_count::zero ().afdo ());
+	      AFDO_EINFO (ep)->set_annotated ();
+	    }
+	}
+      if (total == 1 && ! AFDO_EINFO (only_one)->is_annotated ())
+	{
+	  AFDO_EINFO (only_one)->set_count (AFDO_EINFO (e)->get_count ());
+	  AFDO_EINFO (only_one)->set_annotated ();
+	}
     }
   }
 }
@@ -1342,7 +1345,7 @@ afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge)
    graph. We do the propagation iteratively until stablize.  */
 
 static void
-afdo_propagate (bb_set *annotated_bb, edge_set *annotated_edge)
+afdo_propagate (bb_set *annotated_bb)
 {
   basic_block bb;
   bool changed = true;
@@ -1359,11 +1362,11 @@ afdo_propagate (bb_set *annotated_bb, edge_set *annotated_edge)
     {
       changed = false;
 
-      if (afdo_propagate_edge (true, annotated_bb, annotated_edge))
+      if (afdo_propagate_edge (true, annotated_bb))
         changed = true;
-      if (afdo_propagate_edge (false, annotated_bb, annotated_edge))
+      if (afdo_propagate_edge (false, annotated_bb))
         changed = true;
-      afdo_propagate_circuit (*annotated_bb, annotated_edge);
+      afdo_propagate_circuit (*annotated_bb);
     }
 }
 
@@ -1371,52 +1374,59 @@ afdo_propagate (bb_set *annotated_bb, edge_set *annotated_edge)
    probabilities.  */
 
 static void
-afdo_calculate_branch_prob (bb_set *annotated_bb, edge_set *annotated_edge)
+afdo_calculate_branch_prob (bb_set *annotated_bb)
 {
+  edge e;
+  edge_iterator ei;
   basic_block bb;
-  bool has_sample = false;
-
-  FOR_EACH_BB_FN (bb, cfun)
-  {
-    if (bb->count > profile_count::zero ())
-      {
-	has_sample = true;
-	break;
-      }
-  }
-
-  if (!has_sample)
-    return;
 
   calculate_dominance_info (CDI_POST_DOMINATORS);
   calculate_dominance_info (CDI_DOMINATORS);
   loop_optimizer_init (0);
 
+  FOR_ALL_BB_FN (bb, cfun)
+    {
+      gcc_assert (bb->aux == NULL);
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	{
+	  gcc_assert (e->aux == NULL);
+	  e->aux = new edge_info ();
+	}
+    }
+
   afdo_find_equiv_class (annotated_bb);
-  afdo_propagate (annotated_bb, annotated_edge);
+  afdo_propagate (annotated_bb);
 
   FOR_EACH_BB_FN (bb, cfun)
   {
-    edge e;
-    edge_iterator ei;
     int num_unknown_succ = 0;
     profile_count total_count = profile_count::zero ().afdo ();
 
     FOR_EACH_EDGE (e, ei, bb->succs)
     {
-      if (!is_edge_annotated (e, *annotated_edge))
+      gcc_assert (AFDO_EINFO (e) != NULL);
+      if (! AFDO_EINFO (e)->is_annotated ())
         num_unknown_succ++;
       else
-        total_count += e->count ();
+        total_count += AFDO_EINFO (e)->get_count ();
     }
     if (num_unknown_succ == 0 && total_count > profile_count::zero ())
       {
-        FOR_EACH_EDGE (e, ei, bb->succs)
-          e->probability = e->count ().probability_in (total_count);
+	FOR_EACH_EDGE (e, ei, bb->succs)
+	  e->probability
+	    = AFDO_EINFO (e)->get_count ().probability_in (total_count);
       }
   }
   FOR_ALL_BB_FN (bb, cfun)
-    bb->aux = NULL;
+    {
+      bb->aux = NULL;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (AFDO_EINFO (e) != NULL)
+	  {
+	    delete AFDO_EINFO (e);
+	    e->aux = NULL;
+	  }
+    }
 
   loop_optimizer_finalize ();
   free_dominance_info (CDI_DOMINATORS);
@@ -1496,7 +1506,6 @@ afdo_annotate_cfg (const stmt_set &promoted_stmts)
 {
   basic_block bb;
   bb_set annotated_bb;
-  edge_set annotated_edge;
   const function_instance *s
       = afdo_source_profile->get_function_instance_by_decl (
           current_function_decl);
@@ -1511,21 +1520,15 @@ afdo_annotate_cfg (const stmt_set &promoted_stmts)
   profile_count max_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
 
   FOR_EACH_BB_FN (bb, cfun)
-  {
-    edge e;
-    edge_iterator ei;
-
-    /* As autoFDO uses sampling approach, we have to assume that all
-       counters are zero when not seen by autoFDO.  */
-    bb->count = profile_count::zero ().afdo ();
-    FOR_EACH_EDGE (e, ei, bb->succs)
-      e->probability = profile_probability::uninitialized ();
-
-    if (afdo_set_bb_count (bb, promoted_stmts))
-      set_bb_annotated (bb, &annotated_bb);
-    if (bb->count > max_count)
-      max_count = bb->count;
-  }
+    {
+      /* As autoFDO uses sampling approach, we have to assume that all
+	 counters are zero when not seen by autoFDO.  */
+      bb->count = profile_count::zero ().afdo ();
+      if (afdo_set_bb_count (bb, promoted_stmts))
+	set_bb_annotated (bb, &annotated_bb);
+      if (bb->count > max_count)
+	max_count = bb->count;
+    }
   if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count
       > ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count)
     {
@@ -1546,7 +1549,8 @@ afdo_annotate_cfg (const stmt_set &promoted_stmts)
   afdo_source_profile->mark_annotated (cfun->function_end_locus);
   if (max_count > profile_count::zero ())
     {
-      afdo_calculate_branch_prob (&annotated_bb, &annotated_edge);
+      /* Calculate, propagate count and probability information on CFG.  */
+      afdo_calculate_branch_prob (&annotated_bb);
       update_max_bb_count ();
       profile_status_for_fn (cfun) = PROFILE_READ;
     }
-- 
2.14.4.44.g2045bb6

Re: [PATCH AutoFDO/4]Fix profile count computation/propagation.

[Jeff Law]

On 12/10/18 6:36 PM, Bin.Cheng wrote:
> On Thu, Nov 8, 2018 at 6:33 AM Jeff Law <law@redhat.com> wrote:
>> On 10/31/18 12:34 AM, bin.cheng wrote:
>>> Hi,
>>> This patch fixes AutoFDO breakage on trunk.  The main reason for breakage is AutoFDO
>>> relies on standalone edge count computing and propagating profile count/probability info
>>> on CFG, but in new infra, edge count is actually computed from probability, which leads
>>> to chicken-egg problem and corrupted profile count.  This patch fixes the issue by using
>>> explicit edge count.
>>>
>>> There is another issue not touched yet that, in quite common case, profiled samples are
>>> not enough and profile info computed for lots of blocks is ZERO.  In the future, we may
>>> add some heuristics checking quality of sampled counts and reverting to guessed profile
>>> count if necessary.  I think change made in this patch is also needed for that.
>>>
>>> Package mysql server is used in test of this patch set.  It can't be compiled with autofdo
>>> on trunk, even with compilation issues worked-around, there isn't performance improvement.
>>> I local experiments, with this patch set it's improved by 12.3%, 4.3% irrespectively for
>>> read-only/write-heavy benchmarks.  Unfortunately,  this patch set was written against
>>> GCC 8 branch a while ago, improvement gets worse on trunk and I haven't investigated
>>> the reason yet.  I guess there are still other issues which need to be fixed in the future.
>>>
>>> Bootstrap and test on x86_64 in patch set.  Is it OK?
>>>
>>> Thanks,
>>> bin
>>> 2018-10-31  Bin Cheng  <bin.cheng@linux.alibaba.com>
>>>
>>>       * auto-profile.c (AFDO_EINFO): New macro.
>>>       (struct edge_info): New structure.
>>>       (is_edge_annotated, set_edge_annotated): Delete.
>>>       (afdo_propagate_edge, afdo_propagate_circuit, afdo_propagate): Remove
>>>       parameter.  Adjust edge count computation and annotation using struct
>>>       edge_info.
>>>       (afdo_calculate_branch_prob): Ditto.
>>>       (afdo_annotate_cfg): Simplify code setting basic block profile count.
>>>
>>>
>>> 0004-Fix-AutoFDO-breakage-after-profile-count-rewriting.patch
>>>
>>> From 6506c12d1b633b6d1bfae839b3633a4f99b3a481 Mon Sep 17 00:00:00 2001
>>> From: chengbin <bin.cheng@linux.alibaba.com>
>>> Date: Mon, 20 Aug 2018 15:25:02 +0800
>>> Subject: [PATCH 4/4] Fix AutoFDO breakage after profile count rewriting.
>>>
>>> ---
>>>  gcc/auto-profile.c | 190 ++++++++++++++++++++++++++---------------------------
>>>  1 file changed, 95 insertions(+), 95 deletions(-)
>>>
>>> diff --git a/gcc/auto-profile.c b/gcc/auto-profile.c
>>> index cde4f41c1d9..ff3ea23d830 100644
>>> --- a/gcc/auto-profile.c
>>> +++ b/gcc/auto-profile.c
>>> @@ -101,6 +101,17 @@ along with GCC; see the file COPYING3.  If not see
>>>  namespace autofdo
>>>  {
>>>
>>> +/* Intermediate edge info used when propagating AutoFDO profile information.
>>> +   We can't edge->count() directly since it's computed from edge's probability
>>> +   while probability is yet not decided during propagation.  */
>>> +#define AFDO_EINFO(e)                     ((struct edge_info *) e->aux)
>>> +struct edge_info
>>> +{
>>> +  edge_info () : count (profile_count::zero ().afdo ()), annotated_p (false) {}
>>> +  profile_count count;
>>> +  bool annotated_p;
>>> +};
>> edge_info isn't POD, so make it a class rather than a struct.
>>
>> OK with that change assuming it does not have a hard dependency on prior
>> patches in this series.
> Thanks very much for review.  Now that all prerequisite patches are
> approved and committed, I update this one by making edge_info a class
> as suggested.
> Bootstrap and test as before, is it OK?
> 
> Thanks,
> bin
> 
> 2018-12-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
> 
>         * auto-profile.c (AFDO_EINFO): New macro.
>         (class edge_info): New class.
>         (is_edge_annotated, set_edge_annotated): Delete.
>         (afdo_propagate_edge, afdo_propagate_circuit, afdo_propagate): Remove
>         parameter.  Adjust edge count computation and annotation using class
>         edge_info.
>         (afdo_calculate_branch_prob, afdo_annotate_cfg): Likewise.
OK
jeff