Page MenuHomePhabricator

Keep the order of the basic blocks in the cloned loop as the original loop
ClosedPublic

Authored by Whitney on Jul 4 2019, 3:32 PM.

Details

Summary

Do the cloning in two steps, first allocate all the new loops, then clone the basic blocks in the same order as the original loop.

Diff Detail

Repository
rL LLVM

Event Timeline

Whitney created this revision.Jul 4 2019, 3:32 PM
hfinkel added a subscriber: hfinkel.Jul 5 2019, 6:35 PM

Do you have any kind of test case? I suppose that you can check the output in a test in test/Analysis/LoopInfo to show the ordering?

llvm/lib/Transforms/Utils/CloneFunction.cpp
783

Is this logic equivalent? The original code is going a pre-order traversal, and for each loop, it excludes blocks in an inner loop (when CurLoop != LI->getLoopFor(BB)). Here we're doing something for all blocks in the loop including those also in inner loops?

Whitney marked an inline comment as done.Jul 5 2019, 7:10 PM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CloneFunction.cpp
783

The resulting cloned basic blocks will be the same, which are all the blocks in OrigLoop. The different is the order of the basic block. Example:
Given OrigLoop:

OuterHeader:
  br InnerHeader
InnerHeader:
  br InnerHeader or OuterLatch
OuterLatch:
  br OuterHeader or OuterExit

Output before this change:

ClonedOuterHeader:
  br ClonedInnerHeader
ClonedOuterLatch:
  br ClonedOuterHeader or ClonedOuterExit
ClonedInnerHeader:
  br ClonedInnerHeader or ClonedOuterLatch

Output after this change:

ClonedOuterHeader:
  br ClonedInnerHeader
ClonedInnerHeader:
  br ClonedInnerHeader or ClonedOuterLatch
ClonedOuterLatch:
  br ClonedOuterHeader or ClonedOuterExit

FYI - this function is extended by me in https://reviews.llvm.org/rG7c1deeff4a67296654823a871fea5c1a2aef3b8a to support cloning a loop nest instead of only allow the innermost loop. But I didn't think properly about the ordering of the basic block at that time.

hfinkel added inline comments.Jul 5 2019, 7:29 PM
llvm/lib/Transforms/Utils/CloneFunction.cpp
783

Ah, okay. I see. This loop is not part of the pre-order traversal, it's just cloning all of the blocks in the outer loop in order. That seems fine.

Whitney updated this revision to Diff 208249.Jul 5 2019, 7:34 PM
Whitney marked 2 inline comments as done.

@hfinkel Thanks for the review! I am not sure how to add a test in test/Analysis/LoopInfo, as cloneLoopWithPreheader() is not called by LoopInfo, so I added a test in unittests/Transforms/Utils/CloningTest.cpp instead.

hfinkel accepted this revision.Jul 5 2019, 7:43 PM

LGTM

This revision is now accepted and ready to land.Jul 5 2019, 7:43 PM
fhahn accepted this revision.Jul 9 2019, 8:00 AM

LGTM, thanks. For the commit message, it would be great if you could prefix the area the patch falls in, e.g. [CloneFunction].

Whitney closed this revision.Jul 9 2019, 10:46 AM

Already committed on July 8 (7d8f30e6b2f27d55d4a14392951e4a61d7598767).