On Thu, Apr 30, 2015 at 12:34 PM, Alan Lawrence <alan.lawre...@arm.com> wrote:
> Richard Biener wrote:
>>
>> On Tue, Apr 28, 2015 at 3:55 PM, Alan Lawrence <alan.lawre...@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...
Heh. I would have said the loop header copying could be done by the
vectorizer itself when it detects the non-empty latch simply call a factored
function from loop header copying that forcefully duplicates the header
(well, or simply inline the short relevant portion).
We'd eventually want to undo this if vectorization fails but that's possibly
a secondary concern.
Another possibility is to piggy-back that onto the if-conversion pass and
force the use of versioning for that.
Moving the CH pass is sth entirely different and I'd rather not do that.
Richard.
> 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
>
