Re: [PATCH 8/9] shrink-wrap: shrink-wrapping for separate concerns

[Segher Boessenkool <segher at kernel dot crashing dot org>]

On Mon, Jul 18, 2016 at 07:03:04PM +0200, Bernd Schmidt wrote:
> >>>+  /* The frequency of executing the prologue for this BB and all BBs
> >>>+     dominated by it.  */
> >>>+  gcov_type cost;
> >>
> >>Is this frequency consideration the only thing that attempts to prevent
> >>placing prologue insns into loops?
> >
> >Yes.  The algorithm makes sure the prologues are executed as infrequently
> >as possible.  If a block that would get a prologue has the same frequency
> >as a predecessor does, and that predecessor always has that first block as
> >eventual successor, the prologue is moved to the earlier block (this
> >handles the case where both have a frequency of zero, and other cases
> >where the range of freq is too limited).
> 
> Ugh, that is really scaring me. I'd much prefer a classification of 
> valid blocks based on cfg structure alone - I'll need serious convincing 
> that the frequency data is reliable enough for what you are trying to do.

But you need the profile to make even reasonably good decisions.

The standard example:

   1
  / \
 2   3
  \ /
   4
  / \
 5   6
  \ /
   7

where 3 and 6 need some prologue, the rest do not.
If freq(3) + freq(6) > freq(1), it is better to put the prologue at 1;
if not, it is better to place it at 3 and 6.

If you do not use the profile, you cannot do better than the status quo,
i.e. always place it at 1.

In the general case, you have the choice between putting the prologue at
some basic block X, or at certain blocks dominated by X.  This algorithm
chooses the case that has the prologue executed the least often in total,
and that is really all there is to it.


Yes, our profile data sometimes is, uh, less than optimal.  But:
- All our other passes use it, too;
- What matters most here is comparing the execution frequency locally,
  and that is not usually messed up so badly;
- All our other passes use it, too;
- The important cases (loops, exceptional cases) normally have a pretty
  reasonable profile;
- All our other passes use it, too;
- Benchmarking shows big wins with this patch.


Segher