Slow profile updating (pr 15524)

Slow profile updating (pr 15524)

[Jeffrey A Law]

Believe it or not we're at a point where updating of the profile in
response to a jump thread is the most expensive routine in the 
compiler for PR 15524.


If we look up update_bb_profile_for_threading we see one loop of
significance:

  else
    FOR_EACH_EDGE (c, ei, bb->succs)
      c->probability = ((c->probability * REG_BR_PROB_BASE) / (double)
prob);


So anytime we thread through some block BB, we have to walk through
all its successors to rescale their probabilities.  Needless to say
that gets rather expensive, especially if BB has a large switch
statement and several of its incoming edges are threadable.

Is it the case that the computation of c->probability actually
has to happen in the order you specified via the parenthesis?  If
not, then we could precompute REG_BR_PROB_BASE / (double) prob
outside the loop which would result in a loop like

    tmp = REG_BR_PROB_BASE / (double) prob;
    FOR_EACH_EDGE (c, ei, bb->succs)
      c->probability *= tmp;

Which would probably provide a reasonable improvement.

And if that's safe, then we'd probably want to rewrite it like

  else if (prob != REG_BR_PROB_BASE)
    {
      double tmp = REG_BR_PROB_BASE / (double) prob;
      FOR_EACH_EDGE 9c, ei, bb->succs)
        c->probability *= tmp;
    }

Which avoids the loop completely if nothing is going to change (as is
the case for pr15524).

Doing something like this would give us a net improvement of 15-20% on
PR 15524.

Alternately we might want to look at whether or not we can rescale the
successor blocks en-masse after all the redirections for a particular
block are complete.

Thoughts?

jeff

Re: Slow profile updating (pr 15524)

[Jan Hubicka]

> 
> Believe it or not we're at a point where updating of the profile in
> response to a jump thread is the most expensive routine in the 
> compiler for PR 15524.
> 
> 
> If we look up update_bb_profile_for_threading we see one loop of
> significance:
> 
>   else
>     FOR_EACH_EDGE (c, ei, bb->succs)
>       c->probability = ((c->probability * REG_BR_PROB_BASE) / (double)
> prob);
> 
> 
> So anytime we thread through some block BB, we have to walk through
> all its successors to rescale their probabilities.  Needless to say
> that gets rather expensive, especially if BB has a large switch
> statement and several of its incoming edges are threadable.
> 
> Is it the case that the computation of c->probability actually
> has to happen in the order you specified via the parenthesis?  If
> not, then we could precompute REG_BR_PROB_BASE / (double) prob
> outside the loop which would result in a loop like
> 
>     tmp = REG_BR_PROB_BASE / (double) prob;
>     FOR_EACH_EDGE (c, ei, bb->succs)
>       c->probability *= tmp;
> 
> Which would probably provide a reasonable improvement.

It is just rescaling.  I think the (double) cast is actually redundant
here, but if we want to go into double precision we might lift the
division out as you sugest.
> 
> And if that's safe, then we'd probably want to rewrite it like
> 
>   else if (prob != REG_BR_PROB_BASE)
>     {
>       double tmp = REG_BR_PROB_BASE / (double) prob;
>       FOR_EACH_EDGE 9c, ei, bb->succs)
>         c->probability *= tmp;
>     }
> 
> Which avoids the loop completely if nothing is going to change (as is
> the case for pr15524).

Yep, that would be fine too ;)
> 
> Doing something like this would give us a net improvement of 15-20% on
> PR 15524.
> 
> Alternately we might want to look at whether or not we can rescale the
> successor blocks en-masse after all the redirections for a particular
> block are complete.

This might be good idea too, but we need to be careful that we won't
confuse ourselves while doing the other updates, so it is rather
fragile...

Honza
> 
> Thoughts?
> 
> jeff
>