[Cloning] cloneLoopWithPreheader(): add assert to ensure no sub-loops

[vaivaswatha]

Summary

cloneLoopWithPreheader() does not update LoopInfo for sub-loop of
the original loop being cloned. Add assert to ensure no sub-loops for loop being cloned.

[vaivaswatha]

Ping !

[anemet]

Good point, thanks.

Can you please also add an assert to check that there are no subloops in OrigLoop?

We could also rename the function to cloneInnerLoopWithPreheader?

[vaivaswatha]

Hey sorry I'd forgotten about this patch. I'll work on it and resubmit in a day or two.

[vaivaswatha]

[Cloning] Add assert to ensure no sub-loops for loop being cloned. Also rename
function to reflect its inability to clone sub-loops. (It can clone sub-loops,
but does not correctly update LoopInfo).

1. Updating D15922: [NOP][Cloning] Add comment to cloneLoopWithPreheader() mentioning that it does not update LoopInfo for sub-loops.

[ashutosh.nema]

include/llvm/Transforms/Utils/Cloning.h

224–225

may not => should not

lib/Transforms/Utils/CloneFunction.cpp

705–707

may not => should not

706

cloneInnerLoopWithPreheader looks little confusing, consider L1 { L2{ L3{} } }, L2 is also a inner loop, But here we clone innermost loop only. How about cloneInnermostLoopWithPreheader ?

712

Please assert with some message, i.e. Loop is not innermost

[vaivaswatha]

Updating based on review comments

[ashutosh.nema]

Thanks Vaivaswatha, looks OK to me except the name of function.
As I mentioned earlier ‘cloneInnermostLoopWithPreheader’ looks more intuitive
vs ‘cloneInnerLoopWithPreheader’ because we clone the innermost loop only.

Adam, Hal:
What’s your opinion on this name change ?

[ashutosh.nema]

I see lot of indentation problems here, please correct them.
Try using clang-format its useful.

lib/Transforms/Scalar/LoopDistribute.cpp

125–126

Correct indentation

129–130

Correct indentation

lib/Transforms/Utils/CloneFunction.cpp

706

Correct indentation.

712

Correct indentation.

lib/Transforms/Utils/LoopVersioning.cpp

106

Correct indentation.

[anemet]

In D15922#403741, @ashutosh.nema wrote:

Thanks Vaivaswatha, looks OK to me except the name of function.
As I mentioned earlier ‘cloneInnermostLoopWithPreheader’ looks more intuitive
vs ‘cloneInnerLoopWithPreheader’ because we clone the innermost loop only.

Adam, Hal:
What’s your opinion on this name change ?

Sounds good to me.

[hfinkel]

In D15922#404195, @anemet wrote:

In D15922#403741, @ashutosh.nema wrote:

Thanks Vaivaswatha, looks OK to me except the name of function.
As I mentioned earlier ‘cloneInnermostLoopWithPreheader’ looks more intuitive
vs ‘cloneInnerLoopWithPreheader’ because we clone the innermost loop only.

Adam, Hal:
What’s your opinion on this name change ?

Sounds good to me.

Me too.

[vaivaswatha]

Updating based on review comments

[ashutosh.nema]

Indentation is still not as per llvm coding standard, please run clang-format.
You can specifically run it on the code added by you using below command:

$ clang-format -i -lines=start:end <file>

Refer below page for more details:
http://clang.llvm.org/docs/ClangFormat.html

[hfinkel]

Upon reflection, cloning an outer loop is something we'll want to be able to do at some point. Why don't we just add the assertion for now, and then fix the function once we have a concrete use case?

[vaivaswatha]

In D15922#412417, @hfinkel wrote:

Upon reflection, cloning an outer loop is something we'll want to be able to do at some point. Why don't we just add the assertion for now, and then fix the function once we have a concrete use case?

I agree with this.

[vaivaswatha]

Updating based on review comments.

[hfinkel]

include/llvm/Transforms/Utils/Cloning.h

224

/// Note: Only inner loops are supported.

(TODO comments in header files are discouraged)

lib/Transforms/Utils/CloneFunction.cpp

705

No need to add this here (actually, we shouldn't be duplicating comments like this between header and source files at all).

[vaivaswatha]

Updating based on review comments

[hfinkel]

LGTM.

include/llvm/Transforms/Utils/Cloning.h

 bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
                     AAResults *CalleeAAR = nullptr, bool InsertLifetime = true);
 
 /// \brief Clones a loop \p OrigLoop.  Returns the loop and the blocks in \p
 /// Blocks.
 ///
 /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block
 /// \p LoopDomBB.  Insert the new blocks before block specified in \p Before.
-Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
+/// \p OrigLoop should not have sub-loops.
+Loop *cloneInnermostLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
                              Loop *OrigLoop, ValueToValueMapTy &VMap,
                              const Twine &NameSuffix, LoopInfo *LI,
                              DominatorTree *DT,
                              SmallVectorImpl<BasicBlock *> &Blocks);
 
 /// \brief Remaps instructions in \p Blocks using the mapping in \p VMap.
 void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
                                ValueToValueMapTy &VMap);
 
 } // End llvm namespace
 
 #endif

lib/Transforms/Scalar/LoopDistribute.cpp

while (!Worklist.empty()) {
       }
     }
   }
 
   /// \brief Clones the original loop.
   ///
   /// Updates LoopInfo and DominatorTree using the information that block \p
   /// LoopDomBB dominates the loop.
-  Loop *cloneLoopWithPreheader(BasicBlock *InsertBefore, BasicBlock *LoopDomBB,
+  Loop *cloneInnermostLoopWithPreheader(BasicBlock *InsertBefore,
+                               BasicBlock *LoopDomBB,
                                unsigned Index, LoopInfo *LI,
                                DominatorTree *DT) {
-    ClonedLoop = ::cloneLoopWithPreheader(InsertBefore, LoopDomBB, OrigLoop,
+    ClonedLoop = ::cloneInnermostLoopWithPreheader(InsertBefore, LoopDomBB, 
+                                          OrigLoop,
                                           VMap, Twine(".ldist") + Twine(Index),
                                           LI, DT, ClonedLoopBlocks);
     return ClonedLoop;
   }
 
   /// \brief The cloned loop.  If this partition is mapped to the original loop,
   /// this is null.
   const Loop *getClonedLoop() const { return ClonedLoop; }
void cloneLoops() {
     // update PH to point to the newly added preheader.
     BasicBlock *TopPH = OrigPH;
     unsigned Index = getSize() - 1;
     for (auto I = std::next(PartitionContainer.rbegin()),
               E = PartitionContainer.rend();
          I != E; ++I, --Index, TopPH = NewLoop->getLoopPreheader()) {
       auto *Part = &*I;
 
-      NewLoop = Part->cloneLoopWithPreheader(TopPH, Pred, Index, LI, DT);
+      NewLoop = Part->cloneInnermostLoopWithPreheader
+        (TopPH, Pred, Index, LI, DT);
 
       Part->getVMap()[ExitBlock] = TopPH;
       Part->remapInstructions();
     }
     Pred->getTerminator()->replaceUsesOfWith(OrigPH, TopPH);
 
     // Now go in forward order and update the immediate dominator for the
     // preheaders with the exiting block of the previous loop.  Dominance
-    // within the loop is updated in cloneLoopWithPreheader.
+    // within the loop is updated in cloneInnermostLoopWithPreheader.
     for (auto Curr = PartitionContainer.cbegin(),
               Next = std::next(PartitionContainer.cbegin()),
               E = PartitionContainer.cend();
          Next != E; ++Curr, ++Next)
       DT->changeImmediateDominator(
           Next->getDistributedLoop()->getLoopPreheader(),
           Curr->getDistributedLoop()->getExitingBlock());
   }

lib/Transforms/Utils/CloneFunction.cpp

for (auto &Inst : *BB)
                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
 }
 
 /// \brief Clones a loop \p OrigLoop.  Returns the loop and the blocks in \p
 /// Blocks.
 ///
 /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block
 /// \p LoopDomBB.  Insert the new blocks before block specified in \p Before.
-Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
+/// \p OrigLoop should not have sub-loops.
+Loop *llvm::cloneInnermostLoopWithPreheader(BasicBlock *Before, 
+                                   BasicBlock *LoopDomBB,
                                    Loop *OrigLoop, ValueToValueMapTy &VMap,
                                    const Twine &NameSuffix, LoopInfo *LI,
                                    DominatorTree *DT,
                                    SmallVectorImpl<BasicBlock *> &Blocks) {
+  assert(OrigLoop->getSubLoops().empty() && 
+         "Loop to be cloned cannot have inner loop");
   Function *F = OrigLoop->getHeader()->getParent();
   Loop *ParentLoop = OrigLoop->getParentLoop();
 
   Loop *NewLoop = new Loop();
   if (ParentLoop)
     ParentLoop->addChildLoop(NewLoop);
   else
     LI->addTopLevelLoop(NewLoop);

lib/Transforms/Utils/LoopVersioning.cpp

void LoopVersioning::versionLoop(
   PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
 
   // Clone the loop including the preheader.
   //
   // FIXME: This does not currently preserve SimplifyLoop because the exit
   // block is a join between the two loops.
   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
   NonVersionedLoop =
-      cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
+      cloneInnermostLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
                              ".lver.orig", LI, DT, NonVersionedLoopBlocks);
   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
 
   // Insert the conditional branch based on the result of the memchecks.
   Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
   BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
                      VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
   OrigTerm->eraseFromParent();