This is an archive of the discontinued LLVM Phabricator instance.

[LV] Never widen an induction variable.
ClosedPublic

Authored by jmolloy on Aug 24 2015, 9:01 AM.

Details

Summary

There's no need to widen canonical induction variables. It's just as efficient to create a *new*, wide, induction variable.

Consider, if we widen an indvar, then we'll have to truncate it before its uses anyway (1 trunc). If we create a new indvar instead, we'll have to truncate that instead (1 trunc) [besides which IndVars should go and clean up our mess after us anyway on principle].

This lets us remove a ton of special-casing code.

Diff Detail

Repository
rL LLVM

Event Timeline

jmolloy updated this revision to Diff 32964.Aug 24 2015, 9:01 AM
jmolloy retitled this revision from to [LV] Never widen an induction variable..
jmolloy updated this object.
jmolloy added reviewers: anemet, mzolotukhin.
jmolloy set the repository for this revision to rL LLVM.
jmolloy added a subscriber: llvm-commits.
anemet edited edge metadata.Aug 28 2015, 10:02 AM

Please upload with full context. Because it's on top of the previous patch, I tried to review this but it's basically impossible.

I have a few early comments/questions though:

lib/Transforms/Vectorize/LoopVectorize.cpp
2683–2692

Is this becoming dead as a consequence of not widening indvars or was this code dead even before? I *think* it's the latter in which case it should be a separate patch to minimize confusion.

3416–3417

These steps seem unnecessary if P == OldInduction, no?

jmolloy updated this revision to Diff 33525.Aug 30 2015, 3:07 AM
jmolloy edited edge metadata.

Hi Adam,

Rebased and uploaded with full context, with some of your comments addressed.

You mentioned the removal of ExtendedIdx in D12285 - actually it's this revision that makes ExtendedIdx redundant, not D12285. Accordingly I've squashed its removal into this patch now.

Cheers,

James

jmolloy added inline comments.Aug 30 2015, 3:10 AM
lib/Transforms/Vectorize/LoopVectorize.cpp
2683–2692

(now refers to L2174)

This is becoming dead as part of this patch. This is the patch that enforces that IdxTy is no different from Induction->getType(). The previous patch only enforced that Induction->getStart() == 0.

3416–3417

(Now refers to L3477)

Yes, it does. It's harmless, and I sometimes prefer to remove special-cases when they make no difference, but I've added the if back in because I think you're right, it makes the flow more obvious in this case.

anemet added inline comments.Aug 31 2015, 5:02 PM
lib/Transforms/Vectorize/LoopVectorize.cpp
471–472

It's pretty strange to store the start idx when it's always zero...

2618–2620

This logic belongs to LoopVectorizationLegality::canVectorizeInstrs together with all the other conditions.

2683–2692

I don't think so. Count is derived from this:

const SCEV *BackedgeTakeCount = SE->getNoopOrZeroExtend(ExitCount, IdxTy);

What worries me that if this code weren't dead and this comment was true:

// The exit count can be of pointer type. Convert it to the correct
// integer type.

then the code after the patch wouldn't handle this case.

3494

Aren't we subtracting zero here now?

Does this mean that we don't need to stash StartIdx?

jmolloy added inline comments.Sep 1 2015, 7:33 AM
lib/Transforms/Vectorize/LoopVectorize.cpp
2683–2692

Hi Adam,

This was a very good catch. It turns out there are no regression tests that can trigger this code, but 3 tests in the test-suite do.

It's possible for Count to have pointer type. But in fact, we calculate exactly the same value above (ExitCountValue) and test that for pointer-typedness. "Count" isn't needed.

So i'll remove this code, use ExitCountValue instead of Count and I'll also add a new testcase to make sure this case is triggered.

jmolloy updated this revision to Diff 33697.Sep 1 2015, 8:30 AM

Hi Adam,

All your comments should be fixed now. I've also added a test (which asserted when I ran it against my original patch).

Thanks!

James

jmolloy marked 3 inline comments as done.Sep 1 2015, 8:31 AM
anemet accepted this revision.Sep 2 2015, 12:11 AM
anemet edited edge metadata.

LGTM with some changes below.

Thanks for your patience!

lib/Transforms/Vectorize/LoopVectorize.cpp
2683–2692

Great!

Also just to note what I missed about getNoopOrZeroExtend: it returns the original type (e.g. pointer type) if IdxTy and the original types have the same size. The function comment is misleading in SCEV. I'll fix this later.

test/Transforms/LoopVectorize/ptr-induction.ll
1–3 ↗(On Diff #33697)

Doesn't this test need a datalayout to ensure that pointers are 64-bit?

3–6 ↗(On Diff #33697)

So I guess you're checking here that we have converted this into an integer induction variable? Perhaps a comment would be good.

17 ↗(On Diff #33697)

When I tried this with my not completely up-to-date sources, vectorization failed with:

LV: Found an unidentified PHI. %acc.07 = phi i32 [ %add, %while.body ], [ 0, %while.body.preheader ]

I think we should just remove this and its uses further down.

This revision is now accepted and ready to land.Sep 2 2015, 12:11 AM
jmolloy closed this revision.Sep 2 2015, 4:55 AM
jmolloy marked 2 inline comments as done.

Committed r246631. Thanks!

test/Transforms/LoopVectorize/ptr-induction.ll
17 ↗(On Diff #33697)

It's the "and i32 %acc.07, 255" that's causing it. I'll remove that particular instruction, but reductions with ANDs in them are only just analyzable very recently.