Page MenuHomePhabricator

[RuntimeLoopUnrolling] Update DomTree correctly when exit blocks have successors
ClosedPublic

Authored by anna on Jul 12 2017, 6:55 AM.

Details

Summary

When we runtime unroll with multiple exit blocks, we also need to update the
immediate dominators of the immediate successors of the exit blocks.

Diff Detail

Repository
rL LLVM

Event Timeline

anna created this revision.Jul 12 2017, 6:55 AM
davide added a subscriber: davide.Jul 12 2017, 8:12 AM
anna added inline comments.Jul 12 2017, 12:53 PM
lib/Transforms/Utils/LoopUnrollRuntime.cpp
764 ↗(On Diff #106200)

nit: s/dominate/update
Comment should read as "we should not incorrectly *update* "

mzolotukhin edited edge metadata.Jul 12 2017, 1:51 PM

Don't we break critical edges before unrolling? If so, then I think this situation should never happen (and if it does, we need to understand why).

Michael

anna added a comment.Jul 12 2017, 2:17 PM

Hi Michael,

Don't we break critical edges before unrolling? If so, then I think this situation should never happen (and if it does, we need to understand why).

Michael

As part of support for runtime unrolling in presence of multiple exit blocks (functionality was added in rL306846), when we have multiple exits in a loop, we generate edges from both the main loop and the remainder loop to the main loop's exit block (this is the structure after cloneLoopBlocks). This was to avoid cloning of these multiple exit blocks. After this is done, there are three cleanup steps done:

  1. update the phi nodes in the exit blocks.
  2. update the immediate dominator of these exit blocks
  3. preserve the hasDedicatedExits property for both main and remainder loop: see lines 848-856.

Does this answer your question? Thanks.

mzolotukhin accepted this revision.Jul 12 2017, 2:52 PM

Does this answer your question?

Yes, thank you for the detailed answer. The patch looks good to me then (please also find some minor comments/suggestions inline).

Thanks,
Michael

lib/Transforms/Utils/LoopUnrollRuntime.cpp
768–773 ↗(On Diff #106200)

Are there any other situations where we might want to check this property? It might make sense to check it even before we checked if DT is available (under #ifdef EXPENSIVE_CHECKS of course).

test/Transforms/LoopUnroll/runtime-loop-multiexit-dom-verify.ll
8–10 ↗(On Diff #106200)

This wording seems a bit strange. Is one of them a leftover from some editing?

23 ↗(On Diff #106200)

I'd prefer to simplify br i1 true to unconditional branch or introduce a function parameter if you really need this branch to be conditional. Same applies to undefs used later in other places.

25 ↗(On Diff #106200)

Redundant empty line.

83–85 ↗(On Diff #106200)

Could you please rearrange blocks, so that they stay in a (topo)logical order (like entry, preheader, header, latch, exit1, exit2, mergedexit)?

131 ↗(On Diff #106200)

Do we really need the shift in this test?

This revision is now accepted and ready to land.Jul 12 2017, 2:52 PM
anna marked 6 inline comments as done.Jul 13 2017, 5:57 AM
anna added inline comments.
lib/Transforms/Utils/LoopUnrollRuntime.cpp
768–773 ↗(On Diff #106200)

While running this through make-check, I realized the assertion should be the inverse: if the LHS fails, then we trip on the assert. Just like the assert on line 775 :)

assert(!(any_of(OtherExits,
                     [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
                SuccBB == LatchExit) &&
              "Breaks the definition of dedicated exits!");

I couldn't think of any other situations where we need to check this property about successors of the exit blocks (intent is clearer within this context). Still this is a valid property outside of DT, so moved it outside of DT.

test/Transforms/LoopUnroll/runtime-loop-multiexit-dom-verify.ll
8–10 ↗(On Diff #106200)

yes, thanks!

83–85 ↗(On Diff #106200)

yes, done for all test cases.

131 ↗(On Diff #106200)

It can be any other operation. It's used to show the phi in the latchexit.

This revision was automatically updated to reflect the committed changes.