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

[Segher Boessenkool <segher@kernel.crashing.org>]

On Fri, Sep 09, 2016 at 12:19:03PM -0600, Jeff Law wrote:
> >>Does this impact the compile time computation complexity issue that was
> >>raised elsewhere?
> >
> >I'm not sure what you mean here either, sorry.  It is all O(NM) with N
> >the number of BBs and M the number of components (and assuming dom
> >lookups are constant time, as usual).
> You said in a different message that computing optimal placement points 
> for prologue/epilogue components was not computationally feasible.   I'm 
> just trying to figure out if the switch to utilizing block frequencies 
> is a part of what makes solving that problem infeasible.

Ah, I see.  Allowing multiple prologues (and epilogues) is what makes
it infeasible.  If there is just (at most) one prologue (per component),
calculating the optimal placement is of course linear in # BBs, given
that the cost function is O(1) (or sort of kind of; linear in # edges
really, if you have to insist :-) )

If you allow multiple prologues, i.e. allow any combination of blocks
to run with or without some component "active", you get an exponential
number of possible way to place things, and the cost for those combinations
is *not* an ordered function: if all predecessors of a block have some
component active, then this block itself does not need a prologue.

I get around that by making the cost function ordered, that is, possibly
overestimating the cost of nodes that are the dest of a cross-jump; in
the first version of the patch, by always using the execution frequency
of a node (so, not considering that a prologue there does not cost
anything for edges where the predecessor already has that component
active); and in the second version of the patch, that, but do subtract
the cost from backedges (which makes it clearer that loops are handled
correctly, because the loop header generally has lower cost than the
nodes in the loop body).


Segher