Page MenuHomePhabricator

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute
ClosedPublic

Authored by reames on Jan 17 2021, 8:18 PM.

Details

Summary

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCIish prep work, but the changes are a bit too involved for me to feel comfortable tagging the review that way.

Diff Detail

Event Timeline

reames created this revision.Jan 17 2021, 8:18 PM
reames requested review of this revision.Jan 17 2021, 8:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 17 2021, 8:18 PM
reames updated this revision to Diff 317261.Jan 17 2021, 8:25 PM

Update ascii art to reflect change and clarify a confusing bit in the original.

reames updated this revision to Diff 317262.Jan 17 2021, 8:35 PM

rebase over a landed set of tests

fhahn added a comment.Jan 18 2021, 1:06 PM

This makes sense, but the fact that we need to scatter tests throughout various parts of the code seems unfortunate. I'm planning to take a closer look over the next few days to see if I can provide any ideas on how this could be improved.

Florian, have you had a chance to give thought to alternatives? Given it's been two weeks, unless you have an actionable suggestion, I'd like to move forward with the current patch. I'll emphasize that I'm happy to iterate on the design here, either during review, or after submission if you think of something cleaner.

fhahn accepted this revision.Feb 4 2021, 2:24 PM

Florian, have you had a chance to give thought to alternatives? Given it's been two weeks, unless you have an actionable suggestion, I'd like to move forward with the current patch. I'll emphasize that I'm happy to iterate on the design here, either during review, or after submission if you think of something cleaner.

Unfortunately I did not really have time to think much about better alternatives so far (and it's unlikely I'll get time until end of next week). But I agree, it's not a really big deal and it works well enough for now. Let's tweak it post-commit, should a better alternative presents itself. So for now I just have a few small suggestions, mostly wording related.

LGTM, thanks!

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

This applies for all loops that require scalar epilogues, not just ones with multiple exits, right? If so, it might be better word it in terms of requiring scalar epiloge, rather than multi exits. (perhaps something like An edge from the middle block to the exit block is only added if the scalar epilogue may not be executed. Thus only update the immediate dominators if the scalar epilogue is not required.)

3402

nit: set up a conditional branch from the middle block to the scalar loop pre-header?

3410

Do we need this assert? There's a similar assert just a few lines above. If it's not needed, getting rid of the lambda would make things a bit easier to read IMO (perhaps it could be just BranchInst *BrInst = Cost->requiresScalarEpilogue() ? BranchInst::Create(LoopScalarPreHeader) : BranchInst::Create(LoopExitBlock, LoopScalarPreHeader, Builder.getTrue()))

3524

nit: if we require *a* scalar epilogue .... as we unconditionally branch to *the* scalar preheader?

3667

nit: unrelated whitespace change

This revision is now accepted and ready to land.Feb 4 2021, 2:24 PM