[PATCH] Fix shrink-wrap bug with anticipating into loops (PR67778, PR68634)

[Segher Boessenkool]

On Thu, Dec 03, 2015 at 12:31:53PM +0100, Bernd Schmidt wrote:
> On 12/02/2015 07:21 PM, Segher Boessenkool wrote:
> >After shrink-wrapping has found the "tightest fit" for where to place
> >the prologue, it tries move it earlier (so that frame saves are run
> >earlier) -- but without copying any more basic blocks.
> >
> >Unfortunately a candidate block we select can be inside a loop, and we
> >will still allow it (because the loop always exits via our previously
> >chosen block).
> 
> >So we need to detect this situation.  We can place the prologue at a
> >previous block PRE only if PRE dominates every block reachable from
> >it.  This is a bit hard / expensive to compute, so instead this patch
> >allows a block PRE only if PRE does not post-dominate any of its
> >successors (other than itself).
> 
> Are the two conditions equivalent though?

They are not, one is a subset of the other.  By construction, the block
PRE (the new candidate for getting the prologue) dominates PRO (the
original block to get the prologue), and PRO post-dominates PRE.  Now,
PRE is only suitable if it dominates every block reachable from it,
since otherwise putting the prologue on PRE instead of on PRO requires
duplicating more blocks.

Hrm.  A successor block of PRE could loop back to PRE conditionally,
and go to PRO otherwise.  Rats, what was I thinking.  Thanks for catching
it; I'll have to think of something better.  A bit more factoring will
probably help, we'll see.

> I think I agree with Jakub that we don't want to do unnecessary work in 
> this piece of code.

I agree as well.

> >    /* If we can move PRO back without having to duplicate more blocks, do 
> >    so.
> >       We can move back to a block PRE if every path from PRE will 
> >       eventually
> >-     need a prologue, that is, PRO is a post-dominator of PRE.  */
> >+     need a prologue, that is, PRO is a post-dominator of PRE.  We might
> >+     need to duplicate PRE if there is any path from a successor of PRE 
> >back
> >+     to PRE, so don't allow that either (but self-loops are fine, as are 
> >any
> >+     other loops entirely dominated by PRE; this in general seems too
> >+     expensive to check for, for such an uncommon case).  */
> 
> The last comment is unclear and I don't know what it wants to tell me.

Yeah, sorry.  Writing text is hard :-)


Segher