Re: [PATCH v2 0/9] Separate shrink-wrapping

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

Thanks for looking at the patches Jeff.

On Thu, Sep 08, 2016 at 10:28:59AM -0600, Jeff Law wrote:
> Right.  Essentially Segher's patch introduces the concept of prologue 
> components that are independent of each other and which can be 
> shrink-wrapped separately.  The degree of independence is highly target 
> specific, of course.

There can be dependencies as well (e.g. a save to the frame requires that
frame to be set up already), but the current patches have no way to
describe such dependencies.  I haven't found a good way to describe the
dependencies yet.  Finding a good balance between general and useful isn't
easy, as usual.

> I think one of the questions (and I haven't looked through the whole 
> thread yet to see if it's answered) is why the basic shrink-wrapping 
> algorithm can't be applied to each of the prologue components -- though 
> you may have answered it with your loop example below.

You get code size explosion with the "basic" algorithm.  And a lot of
that isn't really worth it: avoiding the whole prologue/epilogue is
usually worth copying some blocks for, but avoiding just a single register
save/restore pair?  More doubtful.

> >That includes moving parts of the prologue into loops:
> >
> >int g() {
> >  int sum = 0;
> >  for (int i = 0; i < NUM; i++) {
> >    sum += i;
> >    if (sum >= CUTOFF) {
> >      some_long_winded_expression();
> >      that_eventually_calls_abort();
> >    }
> >  }
> >  return sum;
> >}
> >
> >Here all parts of the prologue that somehow make it possible to call other
> >functions are necessary only when the program will abort eventually: hence
> >is necessary only at one call of g() at most.  Again it's sensible to move
> >those parts inside the unlikely condition, even though it's inside a loop.
> Thanks.  I'd been wondering about when it'd be useful to push prologue 
> code into a loop nest when I saw the patches fly by, but didn't think 
> about it too much.  I haven't looked at the shrink-wrapping literature 
> in years, but I don't recall it having any concept that there were cases 
> where sinking into a loop nest was profitable.

It isn't common, but it does happen.  If you use a proper cost metric
based on executiuon frequency with some algorithm then that algorithm will
naturally avoid placing *logues into loops.


Segher