Re: [PATCH] Remove some restrictions on loop shape in tree-if-conv.c

[Alan Lawrence <alan dot lawrence at arm dot com>]

Richard Biener wrote:
> On Tue, Apr 28, 2015 at 3:55 PM, Alan Lawrence <alan.lawrence@arm.com> wrote:
> > Tree if-conversion currently bails out for loops that (a) contain nested
> > loops; (b) have more than one exit; (c) where the exit block (source of the
> > exit edge) does not dominate the loop latch; (d) where the exit block is the
> > loop header, or there are statements after the exit.
> >
> > This patch removes restrictions (c) and (d). The intuition is that, for (c),
> > "if (P) {... if (Q) break;}" is equivalent to "if (P) {...}; if (P&&Q)
> > break;" and this is mostly handled by existing code for propagating
> > conditions. For (d), "if (P) break; stmts" is equivalent to "if (!P) stmts;
> > if (P) break;" - this requires inserting the predicated stmts before the
> > branch rather than after.
>
> Hum - so you empty the latch by conditionalizing code on the exit condition?

Well, !(exit condition), but yes.

> So you still restrict loop form to two blocks - just the latch may now be
> non-empty?  Thus I'd say keeping the existing check but amending it by
> && bb != loop->latch would be better.

The idea was to try to end up with a loop with exactly two blocks, a main block 
with a condition at the end, and an empty latch; but to convert more 
bad-loop-form loops into this form.

> Otherwise the patch looks good to me.
>
> Can you please add at least one testcase for c) and d) where we now
> vectorize something after the patch but not before?

So I think I have made an inconsistency, by changing the logic for 
dominance-of-latch to postdominance-of-header, in one place but not another 
(where it deals with conditional stores) - but I haven't managed to tickle that yet.

However, I'm struggling to find a case where this patch enables vectorization; 
the fancy if-converted loops tend to have other problems preventing 
vectorization, e.g. location of PHI nodes. In contrast, your suggestion of 
putting in another loop-header-copying pass, enables both if-conversion (with 
the existing tree-if-conv.c) and vectorization of a bunch of things (including 
the example I posted of this patch if-converting but still not vectorizing). So 
(short of massive changes to the vectorizer) that approach now feels more 
promising, although there are a good bunch of scan-tree-dump test failures that 
I need to look into...

Where (something like) this patch might be useful, could be as a first step to 
handling loops with multiple exits, that is, changing

for (;;)
{
 S1;
 if (P) break;
 S2;
 if (Q) break;
 S3;
}

into the equivalent of

for (;;)
{
  S1;
  if (!P) S2;
  if (!P && !Q) S3;
  if (P || Q) break;
}

But that's more work, and another patch, and I'm not yet clear how many loops of 
that form the vectorizer would do anything with anyway (let alone profitably!)...

Cheers, Alan