Re: Propagate profile counts during switch expansion

[Easwaran Raman <eraman at google dot com>]

Hi Honza,
 I am addressing some of the questions you raise here. Will send an
updated patch later.


On Thu, Oct 4, 2012 at 6:19 AM, Jan Hubicka <hubicka@ucw.cz> wrote:

> > @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b)
> >    return;
> >   }
> >      }
> > -
> >    if (single_succ_p (b))
> >      {
> >        e = single_succ_edge (b);
> > @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b)
> >        e->count = b->count;
> >        return;
> >      }
> > -  guess_outgoing_edge_probabilities (b);
> > +  else if (!gen_probabilities_from_existing_counts (b->succs)){
> > +    /* All outgoing edges of B have zero count. Guess probabilities.  */
> > +    guess_outgoing_edge_probabilities (b);
> > +  }
>
> Hmm, I do not quite follow logic here.
> basic block B is one of many basic blocks that the original BB was split from.
> It is possible that B may have some of original edges, but there may be new ones.
> How you can guess the outgoing probabilitie shere.  Do you have an example?

The code reaches here only when the BB has more than two successor. I
assume that this happens only when the BB is terminated by a switch
statement. During conversion to RTL, the outgoing edges of this BB and
their counts ar untouched. So I am just using those counts to compute
the edge probabilities.

> Also gen_probabilities_from_existing_counts could probably also work based
> on original edge frequencies.

Just to be clear I understand it right, you want me to use the
frequency instead of count since the frequency is derived from the
counts in profile use builds?

>
> > +
> > +  default_edge->count = default_count;
> > +  if (count)
> > +    {
> > +      edge e;
> > +      edge_iterator ei;
> > +      FOR_EACH_EDGE (e, ei, stmt_bb->succs)
> > +        e->probability = e->count * REG_BR_PROB_BASE / count;
> > +    }
>
> Hmm, this updates origina BB containing the switch statement?
The out_edges of the original BB.
> Of course,
> modulo roundoff errors, this should hold.  I wonder where did you got the
> diferences and why do you need this?

Originally, I obtained e->probability as e->count * REG_BR_PROB_BASE /
bb->count. During profile bootstrap, I noticed BBs whose sum of
outgoing edge counts exceeded the BB's count and hence I normalized
with the sum of edge counts.

> You are going to output new control flow
> and find_many_sub_basic_blocks will recompute all the counts/frequencies inside
> anyway?
Sorry, I am lost here. I am just updating the probability of
stmt_bb->succs right?


>
> > @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt
> >   unsignedp),
> >         GT, NULL_RTX, mode, unsignedp,
> >         label_rtx (node->right->code_label));
> > -      emit_case_nodes (index, node->left, default_label, index_type);
> > +              probability = case_probability (node->right->count,
> > +                                              subtree_count + default_count);
> > +              add_prob_note_to_last_insn (probability);
> > +      emit_case_nodes (index, node->left, default_label, default_count,
> > +                               index_type);
>
> Hmm, here you seem to be distributing the probabilities of the counts reached.
> What happens in the case when the edge probability needs to be distributed across
> nodes of the decision tree. I.e. in
> t(int a)
> {
>   switch (a)
>    {
>      case 100:
>      case 200:
>      case 300:
>      case 400:
>      case 500:
>      case 600:
>      case 700:
>      case 800:
>      case 900:
>        t();
>      case 101:
>      case 202:
>      case 303:
>      case 404:
>      case 505:
>      case 606:
>      case 707:
>      case 808:
>      case 909:
>        q();
>    }
> }
>
Ok, that's a bug in my patch. In the above example, there are two
outgoing edges from the BB containing switch but many case nodes. I
would end up multiplying the counts by the number of cases that lead
to a label. If I divide the counts of each case_node by the number of
case nodes that jump to the same label, will that be reasonable? In
the above case, if t() is called 900 times, I will assume that each of
the 9 cases contribute a count of 100.

Thanks,
Easwaran