Page MenuHomePhabricator

Preserve domtree and loop-simplify for runtime unrolling.
ClosedPublic

Authored by efriedma on Dec 22 2016, 6:41 PM.

Details

Summary

Mostly straightforward changes; we just didn't do the computation before. One sort of interesting change in LoopUnroll.cpp: we weren't handling dominance for children of the loop latch correctly, but foldBlockIntoPredecessor hid the problem for complete unrolling.

Currently punting on loop peeling; made some minor changes to isolate that problem to LoopUnrollPeel.cpp.

Adds a flag -unroll-verify-domtree; this is on by default for +Asserts builds.

Diff Detail

Repository
rL LLVM

Event Timeline

efriedma updated this revision to Diff 82393.Dec 22 2016, 6:41 PM
efriedma retitled this revision from to Preserve domtree and loop-simplify for runtime unrolling..
efriedma updated this object.
efriedma set the repository for this revision to rL LLVM.
efriedma added a subscriber: llvm-commits.
mkuper added inline comments.Dec 27 2016, 11:33 AM
lib/Transforms/Utils/LoopUnroll.cpp
55 ↗(On Diff #82393)

We want to enforce this being on in new tests too, I assume?

619 ↗(On Diff #82393)

Isn't it the case that when the latch ends with an unconditional branch, that branch is towards the header block?
If so, we should not have any children outside the loop.

efriedma added inline comments.Dec 27 2016, 11:40 AM
lib/Transforms/Utils/LoopUnroll.cpp
55 ↗(On Diff #82393)

We probably want this on in new tests, yes, but I have no idea how we would enforce it.

619 ↗(On Diff #82393)

Maybe this is more clear? "The latch is special because we can emit an unconditional branch in the unrolled loop even if the original latch block ends in a conditional branch."

mkuper added inline comments.Dec 27 2016, 1:18 PM
lib/Transforms/Utils/LoopUnroll.cpp
55 ↗(On Diff #82393)

In code review, I meant. :-)

619 ↗(On Diff #82393)

Ah, ok, this makes sense.
This still looks a bit weird to me, though. Any chance you can give an example of when this ends up different than the nearest common dominator with Latches[0]?

(Feel free to ignore me - I'm not sure I understand this enough to LGTM it anyway. :-) )

mzolotukhin added inline comments.Dec 28 2016, 12:30 PM
lib/Transforms/Utils/LoopUnroll.cpp
55 ↗(On Diff #82393)

Can we make the default value true for debug builds (it will match the existing behavior)?

619 ↗(On Diff #82393)

I'm also curious about an example.

Also, this part is not clear to me: "Since the latch is always at the bottom of the loop, new dominator must also be a latch." Why can't a mid-block from the body be a dominator of a cloned latch?

639–642 ↗(On Diff #82393)

Thanks for fixing this!

644–646 ↗(On Diff #82393)

Do I understand it correctly that using -verify-dom-info wasn't sufficient because of foldBlockIntoPredecessor, and that's why we're now introducing unroll-verify-domtree?

700–701 ↗(On Diff #82393)

Why can we remove this?

efriedma added inline comments.Jan 3 2017, 6:50 PM
lib/Transforms/Utils/LoopUnroll.cpp
55 ↗(On Diff #82393)

Okay. (I initially didn't do this because it's O(N^2) in theory, but it turns out it doesn't really matter that much.)

619 ↗(On Diff #82393)

This shows up for example, if you completely unroll a single-block loop with a constant trip count; the immediate dominator of the exit is the last iteration of the loop, not the first iteration. (foldBlockIntoPredecessor hides this problem because the block in question gets folded away when a loop is completely unrolled.)

Why can't a mid-block from the body be a dominator of a cloned latch?

I'm not sure what you're asking here. ChildrenToUpdate is the set of loop exit blocks which are dominated by BB, so this code only touches the idom for blocks outside the loop. The latch's idom isn't relevant.

644–646 ↗(On Diff #82393)

Yes... we want to verify at this point to try and catch as many mistakes as possible.

700–701 ↗(On Diff #82393)

There are three possibilities for unrolling: we could be completely unrolling a loop, we could be runtime unrolling a loop, or we could be peeling a loop. If we're completely unrolling, these lines are a no-op. If we're runtime unrolling, we now correctly preserve LoopSimplify for L (and we don't break it for any loop outside of L). If we're peeling, we explicitly recreate LoopSimplify earlier.

mzolotukhin added inline comments.Jan 6 2017, 2:58 PM
lib/Transforms/Utils/LoopUnroll.cpp
55 ↗(On Diff #82393)

Thanks! Also, if you change it to true, then changes in the tests are no longer needed.

619 ↗(On Diff #82393)

I've just understood what the problem is, thanks! Yes, it all makes sense now.

625–631 ↗(On Diff #82393)

I think we should be able to tell which latch ends with a conditional. It should be either the first one (if all latches end with conditional branches), or the last one. Does it make sense? If so, can we remove this loop?

700–701 ↗(On Diff #82393)

But isn't it also used for LCSSA? Maybe I'm missing something, but it's still not obvious to me that we can remove it.

efriedma added inline comments.Jan 6 2017, 3:12 PM
lib/Transforms/Utils/LoopUnroll.cpp
700–701 ↗(On Diff #82393)

!CompletelyUnroll implies !NeedToFixLCSSA.

mzolotukhin added inline comments.Jan 6 2017, 3:19 PM
lib/Transforms/Utils/LoopUnroll.cpp
700–701 ↗(On Diff #82393)

Ah, right!

efriedma added inline comments.Jan 9 2017, 4:10 PM
lib/Transforms/Utils/LoopUnroll.cpp
625–631 ↗(On Diff #82393)

The actual conditional is complicated... if we're completely unrolling, it's either the first one or the last one, depending on PreserveCondBr. If we're using a remainder loop, it's always the last one. If we're partially unrolling without a remainder loop, it might not be the first or last one; there's a complicated conditional involving BreakingTrip and TripMultiple. Anyway, this is much more straightforward than trying to duplicate the NeedConditional logic.

efriedma updated this revision to Diff 83730.Jan 9 2017, 4:13 PM
efriedma updated this object.
efriedma edited edge metadata.

Verify domtree by default in +Asserts mode. Clarify comments.

mzolotukhin accepted this revision.Jan 10 2017, 12:26 PM
mzolotukhin edited edge metadata.

Looks good to me, thanks!

Michael

lib/Transforms/Utils/LoopUnroll.cpp
625–631 ↗(On Diff #82393)

Makes sense.

This revision is now accepted and ready to land.Jan 10 2017, 12:26 PM
This revision was automatically updated to reflect the committed changes.