This is an archive of the discontinued LLVM Phabricator instance.

[LV] Don't sink into replication regions
ClosedPublic

Authored by dmgreen on Dec 21 2020, 5:11 AM.

Details

Summary

The new test case here contains a first order recurrences and an instruction that is replicated. The first order recurrence forces an instruction to be sunk _into_, as opposed to after the replication region. That causes several things to go wrong including registering vector instructions multiple times and failing to create dominance relations correctly.

Instead we should be sinking to after the replication region, which is what this patch makes sure happens.

Diff Detail

Event Timeline

dmgreen created this revision.Dec 21 2020, 5:11 AM
dmgreen requested review of this revision.Dec 21 2020, 5:11 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 21 2020, 5:11 AM
fhahn added inline comments.Dec 28 2020, 1:57 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8610

can this just be Sink->moveBefore(NextBlock->getFirstInsertionPt())? With that, Sink->removeFromParent() shouldn't be needed?

llvm/test/Transforms/LoopVectorize/first-order-recurrence.ll
650

It's probably worth to check the IR for the whole vector body for the sink-after case.

664

Can you also add another instruction that will get predicate? I think currently things will work out as expected, because we predicate each instruction separately, but it could lead to problems if we predicate multiple instructions together and cannot sink to the right position. But this will get re-worked as part of the VPlan transition, so I think a test case to catch this should be sufficient.

dmgreen updated this revision to Diff 314090.Dec 30 2020, 3:31 AM

Thanks.

Add a VPRecipeBase::moveBefore and use it and getFirstNonPhi.
Added an extra test with predicated stores and removed some undefs.

fhahn added inline comments.Jan 4 2021, 11:37 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8610

Oh right, moveBefore was still missing. Thanks for adding it. I'm not sure if there's a benefit of having the variant that takes a basic block & an iterator? For consistency with the existing functions, I think it would be slightly better to just have the version that moves before a VPRecipeBase (same as moveAfter)? Those versions are easier & more convenient to use, IMO.

llvm/lib/Transforms/Vectorize/VPlan.h
670 ↗(On Diff #314090)

Could you also add a unit test to VPlanTEst.cpp?

dmgreen updated this revision to Diff 314848.Jan 6 2021, 3:47 AM

Added a unit test, that caught that the Parent was not set correctly.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8610

It was added because the iterator might be end(), in which case it's not possible to tell which block it originally referred to. (The block might be empty, that's why it can't use moveAfter). It is modelled after this equivalent method, from BasicBlock/Instruction: https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/IR/Instruction.h#L142

fhahn accepted this revision.Jan 7 2021, 5:30 AM

Added a unit test, that caught that the Parent was not set correctly.

Great thanks!

LGTM

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8610

oh right, because there are no terminator instructions in a VPlan BB. That's a bit unfortunate but not much we can do in that case. Thanks

This revision is now accepted and ready to land.Jan 7 2021, 5:30 AM

Thanks Florian.

This revision was automatically updated to reflect the committed changes.
Ayal added inline comments.Jan 8 2021, 4:52 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8602

Thanks for fixing!
Note that in general, sinking an instruction more than originally asked for, might place it after its use; in this case, if its use were to belong to the same replication region - potentially possible in the future.
Is it possible for NextBlock to be another replicating Region rather than a BasicBlock?
Going forward, such legality-based scheduling motions should probably be applied earlier, to an initial Region-free VF=UF=1 VPlan.

dmgreen added inline comments.Jan 11 2021, 2:25 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8602

Is it possible for NextBlock to be another replicating Region rather than a BasicBlock?

No, Not currently. There is always an empty VPBasicBlock between one replication region and the next. That is what sink_into_replication_region_multiple is testing, along with the two replication regions not being combined into a single block. We can't (currently) sink past the wrong instruction, as far as I understand, because the replication region is not combined into anything else and we are only sinking past that region, not anything else.