LoopRotation: remove iterative calls to rotateLoops

[sebpop]

Summary

Loops should be rotated only once. Passes regression test and llvm test-suite.

Patch wrote by Aditya Kumar and Sebastian Pop.

[• dberlin]

What's the reasoning/justification for the original vs the change?

[sanjoy]

I thought @mzolotukhin had done this already?

[sebpop]

In D21237#454988, @dberlin wrote:

What's the reasoning/justification for the original vs the change?

As the code is written, the function rotateLoop only execute once.

// Rotate if either the loop latch does *not* exit the loop, or if the loop
// latch was just simplified.
if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch)
  return false;

Furthermore a testcase that contains more than 1 loop exit does not get rotated correctly: only the first condition gets rotated.

void foo (int *p, int a, int b) {

while (a % b && b / a) {
  *p = a++;
  p++;
}

}

We are working on fixing the rotation of this loop in a separate patch.

[mzolotukhin]

@sanjoy: yeah, that's my patch D20181. I missed your LGTM, so I haven't committed it though.

@sebpop: it's interesting, I'm working on that too actually. How do you plan to handle that and how far have you progressed with it? I hope to get something working soonish.

@dberlin: it's kind of a cleanup. We don't call it more than once anyway, so this is just unnecessary complication in the code.

[• dberlin]

@mzolotukhin, yeah, i was added as a reviewer, but had no context, so just
trying to figure out what's up :)

[sebpop]

Thanks for your patch: it looks similar, so you have one more LGTM ;-)
Could you please commit?

In D21237#455028, @mzolotukhin wrote:

@sebpop: it's interesting, I'm working on that too actually. How do you plan to handle that and how far have you progressed with it? I hope to get something working soonish.

We haven't got very far: we just have seen this oddity today.
We were also thinking to remove the corner cases of code hoisting from loop rotation (it is not the place to do these cleanups.)
And then we would simplify the code copying with a plain BB->copy().
We need to keep copying BBs as far as we have not reached the loop latch and still under some budget in terms of number of copied instructions.

[sebpop]

Duplicate of D20181.

[mzolotukhin]

I committed D20181 in r272439.

We were also thinking to remove the corner cases of code hoisting from loop rotation (it is not the place to do these cleanups.)

Yeah, these clean-ups are always getting in the way. I really think we should improve LoopSimplifyCFG and introduce LoopInstSimplify that would take care of that (I have that on my todo list, but I'm not sure if I can make it in a near future).

And then we would simplify the code copying with a plain BB->copy().
We need to keep copying BBs as far as we have not reached the loop latch and still under some budget in terms of number of copied instructions.

Right, my idea was to make loop-rotation more generic, thus enabling it on more complicated loops. It has some interesting corner cases though: for instance you can end up with several nested loops after rotating a single loop, but that's details, which we'll figure out in the process:)

[llvm-commits]

Right, my idea was to make loop-rotation more generic, thus enabling it on more complicated loops. It has some interesting corner cases though: for instance you can end up with several nested loops after rotating a single loop, but that's details, which we'll figure out in the process:)

I discussed about this with Aditya, and we think that a better idea is
to make jump-threading handle the loop rotation: there is no reason to
have rotation as a separate pass when jump-threading is already
(supposed to) do the same transform.

---

llvm-commits mailing list
[e-mail]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

[mzolotukhin]

Can you please elaborate how jump-threading can handle loop-rotation? Are you talking about some particular case, or in general?

Michael

[eli.friedman]

In general, loop rotation is just "split the header block into two versions", which is precisely the sort of transform jump threading does. Actually, the only reason JumpThreading doesn't rotate loops at the moment is that it's explicitly suppressed for loop headers.

[atrick]

Of course loop rotation and jump threading are both forms of tail-duplication. So what! That doesn't mean they should be the same pass. These things are done for different reasons. Loop rotation's job is to put loops into a canonical form for the sake of all other downstream loop passes.

When two passes share common transformations, they should share a utility. They should not be combined into one pass unless they
(a) are driven be the same analysis
(b) have the same pass ordering dependencies

It is very likely that LLVM clients who care about compile time will run -loop-rotate, and not -jump-threading.
(They will also likely want a light-weight "tail duplication" which we unfortunately don't provide)

[sebpop]

In D21237#457089, @atrick wrote:

When two passes share common transformations, they should share a utility. They should not be combined into one pass unless they
(a) are driven be the same analysis
(b) have the same pass ordering dependencies

I stand corrected: loop-rotation and jump-thread should remain in separate passes.

Maybe we can improve the current code by using the same code generation functionality:
I see that currently there is no function to duplicate a single entry multiple exits (SEME) path
needed for both loop-rotation and jump-threading.

llvm/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,
+/// Rotate loop L.  Return true if the loop is rotated.
+static bool rotateLoop(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);
 
   // 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 = rotateLoop(&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 rotateLoop(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);
 }