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
