Don't try to rotate a loop more than once - we never do this anyway.

[mzolotukhin]

Summary

I can't find a case where we can rotate a loop more than once, and it looks
like we never do this. To rotate a loop following conditions should be met:

1. its header should be exiting
2. its latch shouldn't be exiting

But after the first rotation the header becomes the new latch, so this
condition can never be true any longer.

Tested on with an assert on LNT testsuite and make check.

[sanjoy]

Is it possible that the new latch, after simplification, ends up being a non-exiting block? If not, might be useful to add an assert(NewLatch is exiting block).

lib/Transforms/Scalar/LoopRotation.cpp

572 ↗

(On Diff #56960)

Fix comment?

585 ↗

(On Diff #56960)

Fix comment?

[mzolotukhin]

Thanks for taking a look, Sanjoy!

Is it possible that the new latch, after simplification, ends up being a non-exiting block? If not, might be useful to add an assert(NewLatch is exiting block).

I haven't managed to find such case, but running testsuite with this assertion sounds like a good idea to me. I'll update the patch when the run finishes.

Thanks,
Michael

lib/Transforms/Scalar/LoopRotation.cpp

572 ↗

(On Diff #56960)

Oops, thanks, will fix!

[mzolotukhin]

• Add assert.
• Fix comments.

[mzolotukhin]

Ping.

[sanjoy]

lgtm

[sebpop]

LGTM.

llvm/trunk/lib/Transforms/Scalar/LoopRotation.cpp

static bool simplifyLoopLatch(Loop *L, LoopInfo *LI, DominatorTree *DT) {
   assert(Latch->empty() && "unable to evacuate Latch");
   LI->removeBlock(Latch);
   if (DT)
     DT->eraseNode(Latch);
   Latch->eraseFromParent();
   return true;
 }
 
-/// Rotate \c L as many times as possible. Return true if the loop is rotated
-/// at least once.
-static bool iterativelyRotateLoop(Loop *L, unsigned MaxHeaderSize, LoopInfo *LI,
-                                  const TargetTransformInfo *TTI,
-                                  AssumptionCache *AC, DominatorTree *DT,
-                                  ScalarEvolution *SE) {
+/// Rotate \c L, and return true if any modification was made.
+static bool processLoop(Loop *L, unsigned MaxHeaderSize, LoopInfo *LI,
+                        const TargetTransformInfo *TTI, AssumptionCache *AC,
+                        DominatorTree *DT, ScalarEvolution *SE) {
   // Save the loop metadata.
   MDNode *LoopMD = L->getLoopID();
 
   // Simplify the loop latch before attempting to rotate the header
   // upward. Rotation may not be needed if the loop tail can be folded into the
   // loop exit.
   bool SimplifiedLatch = simplifyLoopLatch(L, LI, DT);
 
-  // One loop can be rotated multiple times.
-  bool MadeChange = false;
-  while (rotateLoop(L, MaxHeaderSize, LI, TTI, AC, DT, SE, SimplifiedLatch)) {
-    MadeChange = true;
-    SimplifiedLatch = false;
-  }
+  bool MadeChange =
+      rotateLoop(L, MaxHeaderSize, LI, TTI, AC, DT, SE, SimplifiedLatch);
+  assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
+         "Loop latch should be exiting after loop-rotate.");
 
   // Restore the loop metadata.
   // NB! We presume LoopRotation DOESN'T ADD its own metadata.
   if ((MadeChange || SimplifiedLatch) && LoopMD)
     L->setLoopID(LoopMD);
 
   return MadeChange;
 }
 
 LoopRotatePass::LoopRotatePass() : MaxHeaderSize(DefaultRotationThreshold) {}
 
 PreservedAnalyses LoopRotatePass::run(Loop &L, AnalysisManager<Loop> &AM) {
   auto &FAM = AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
   Function *F = L.getHeader()->getParent();
 
   auto *LI = FAM.getCachedResult<LoopAnalysis>(*F);
   const auto *TTI = FAM.getCachedResult<TargetIRAnalysis>(*F);
   auto *AC = FAM.getCachedResult<AssumptionAnalysis>(*F);
   assert((LI && TTI && AC) && "Analyses for loop rotation not available");
 
   // Optional analyses.
   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(*F);
   auto *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(*F);
 
-  bool Changed = iterativelyRotateLoop(&L, MaxHeaderSize, LI, TTI, AC, DT, SE);
+  bool Changed = processLoop(&L, MaxHeaderSize, LI, TTI, AC, DT, SE);
   if (!Changed)
     return PreservedAnalyses::all();
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 
 class LoopRotateLegacyPass : public LoopPass {
bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
     auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
     auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     auto *SE = SEWP ? &SEWP->getSE() : nullptr;
 
-    return iterativelyRotateLoop(L, MaxHeaderSize, LI, TTI, AC, DT, SE);
+    return processLoop(L, MaxHeaderSize, LI, TTI, AC, DT, SE);
   }
 };
 }
 
 char LoopRotateLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                     false, false)
 
 Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
   return new LoopRotateLegacyPass(MaxHeaderSize);
 }