LoopRotate: restructure code to simplify functions

[sebpop]

Summary

We move the loop rotate functions in a separate class to avoid passing multiple parameters to each function.
This cleanup will help for further development of loop rotation.
NFC.

Patch written by Aditya Kumar and Sebastian Pop.

[sanjoy]

lgtm with nits

llvm/lib/Transforms/Scalar/LoopRotation.cpp

54 ↗

(On Diff #60618)

How about const unsigned MaxHeaderSize?

68 ↗

(On Diff #60618)

Looks like only the constructor and processLoop need to be public?

llvm/trunk/include/llvm/Transforms/Scalar/LoopRotation.h

 
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 /// A simple loop rotation transformation.
 class LoopRotatePass : public PassInfoMixin<LoopRotatePass> {
-  unsigned MaxHeaderSize;
 public:
   LoopRotatePass();
-  LoopRotatePass(unsigned MaxHeaderSize) : MaxHeaderSize(MaxHeaderSize) {}
   PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM);
 };
 }
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPROTATION_H

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

 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-rotate"
 
-static cl::opt<unsigned>
-DefaultRotationThreshold("rotation-max-header-size", cl::init(16), cl::Hidden,
-       cl::desc("The default maximum header size for automatic loop rotation"));
+static cl::opt<unsigned> DefaultRotationThreshold(
+    "rotation-max-header-size", cl::init(16), cl::Hidden,
 
 STATISTIC(NumRotated, "Number of loops rotated");
 
+/// A simple loop rotation transformation.
+class LoopRotate {
+  const unsigned MaxHeaderSize;
+  LoopInfo *LI;
+  const TargetTransformInfo *TTI;
+  AssumptionCache *AC;
+  DominatorTree *DT;
+  ScalarEvolution *SE;
+
+public:
+  LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
+             const TargetTransformInfo *TTI, AssumptionCache *AC,
+             DominatorTree *DT, ScalarEvolution *SE)
+      : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE) {
+  }
+  bool processLoop(Loop *L);
+
+private:
+  bool rotateLoop(Loop *L, bool SimplifiedLatch);
+  bool simplifyLoopLatch(Loop *L);
+};
+
 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
 /// old header into the preheader.  If there were uses of the values produced by
 /// these instruction that were outside of the loop, we have to insert PHI nodes
 /// to merge the two values.  Do this now.
 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
                                             BasicBlock *OrigPreheader,
                                             ValueToValueMapTy &ValueMap) {
   // Remove PHI node entries that are no longer live.
for (I = OrigHeader->begin(); I != E; ++I) {
     // The value now exits in two versions: the initial value in the preheader
     // and the loop "next" value in the original header.
     SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
     SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
     SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
 
     // Visit each use of the OrigHeader instruction.
     for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
-         UE = OrigHeaderVal->use_end(); UI != UE; ) {
+                             UE = OrigHeaderVal->use_end();
+         UI != UE;) {
       // Grab the use before incrementing the iterator.
       Use &U = *UI;
 
       // Increment the iterator before removing the use from the list.
       ++UI;
 
       // SSAUpdater can't handle a non-PHI use in the same block as an
       // earlier def. We can easily handle those cases manually.
for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
       SSA.RewriteUse(U);
     }
 
     // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
     // intrinsics.
     LLVMContext &C = OrigHeader->getContext();
     if (auto *VAM = ValueAsMetadata::getIfExists(OrigHeaderVal)) {
       if (auto *MAV = MetadataAsValue::getIfExists(C, VAM)) {
-        for (auto UI = MAV->use_begin(), E = MAV->use_end(); UI != E; ) {
+        for (auto UI = MAV->use_begin(), E = MAV->use_end(); UI != E;) {
           // Grab the use before incrementing the iterator. Otherwise, altering
           // the Use will invalidate the iterator.
           Use &U = *UI++;
           DbgInfoIntrinsic *UserInst = dyn_cast<DbgInfoIntrinsic>(U.getUser());
-          if (!UserInst) continue;
+          if (!UserInst)
+            continue;
 
           // The original users in the OrigHeader are already using the original
           // definitions.
           BasicBlock *UserBB = UserInst->getParent();
           if (UserBB == OrigHeader)
             continue;
 
           // Users in the OrigPreHeader need to use the value to which the

 /// \param SimplifiedLatch is true if the latch was just folded into the final
 /// loop exit. In this case we may want to rotate even though the new latch is
 /// now an exiting branch. This rotation would have happened had the latch not
 /// been simplified. However, if SimplifiedLatch is false, then we avoid
 /// rotating loops in which the latch exits to avoid excessive or endless
 /// rotation. LoopRotate should be repeatable and converge to a canonical
 /// form. This property is satisfied because simplifying the loop latch can only
 /// happen once across multiple invocations of the LoopRotate pass.
-static bool rotateLoop(Loop *L, unsigned MaxHeaderSize, LoopInfo *LI,
-                       const TargetTransformInfo *TTI, AssumptionCache *AC,
-                       DominatorTree *DT, ScalarEvolution *SE,
-                       bool SimplifiedLatch) {
+bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   // If the loop has only one block then there is not much to rotate.
   if (L->getBlocks().size() == 1)
     return false;
 
   BasicBlock *OrigHeader = L->getHeader();
   BasicBlock *OrigLatch = L->getLoopLatch();
 
   BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   {
     SmallPtrSet<const Value *, 32> EphValues;
     CodeMetrics::collectEphemeralValues(L, AC, EphValues);
 
     CodeMetrics Metrics;
     Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues);
     if (Metrics.notDuplicatable) {
       DEBUG(dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"
-            << " instructions: "; L->dump());
+                   << " instructions: ";
+            L->dump());
       return false;
     }
     if (Metrics.convergent) {
       DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
-                      "instructions: "; L->dump());
+                      "instructions: ";
+            L->dump());
       return false;
     }
     if (Metrics.NumInsts > MaxHeaderSize)
       return false;
   }
 
   // Now, this loop is suitable for rotation.
   BasicBlock *OrigPreheader = L->getLoopPreheader();
while (I != E) {
     Instruction *Inst = &*I++;
 
     // If the instruction's operands are invariant and it doesn't read or write
     // memory, then it is safe to hoist.  Doing this doesn't change the order of
     // execution in the preheader, but does prevent the instruction from
     // executing in each iteration of the loop.  This means it is safe to hoist
     // something that might trap, but isn't safe to hoist something that reads
     // memory (without proving that the loop doesn't write).
-    if (L->hasLoopInvariantOperands(Inst) &&
-        !Inst->mayReadFromMemory() && !Inst->mayWriteToMemory() &&
-        !isa<TerminatorInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst) &&
-        !isa<AllocaInst>(Inst)) {
+    if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&
+        !Inst->mayWriteToMemory() && !isa<TerminatorInst>(Inst) &&
+        !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) {
       Inst->moveBefore(LoopEntryBranch);
       continue;
     }
 
     // Otherwise, create a duplicate of the instruction.
     Instruction *C = Inst->clone();
 
     // Eagerly remap the operands of the instruction.
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   // If there were any uses of instructions in the duplicated block outside the
   // loop, update them, inserting PHI nodes as required
   RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap);
 
   // NewHeader is now the header of the loop.
   L->moveToHeader(NewHeader);
   assert(L->getHeader() == NewHeader && "Latch block is our new header");
 
-
   // At this point, we've finished our major CFG changes.  As part of cloning
   // the loop into the preheader we've simplified instructions and the
   // duplicated conditional branch may now be branching on a constant.  If it is
   // branching on a constant and if that constant means that we enter the loop,
   // then we fold away the cond branch to an uncond branch.  This simplifies the
   // loop in cases important for nested loops, and it also means we don't have
   // to split as many edges.
   BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
   assert(PHBI->isConditional() && "Should be clone of BI condbr!");
   if (!isa<ConstantInt>(PHBI->getCondition()) ||
-      PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero())
-          != NewHeader) {
+      PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
+          NewHeader) {
     // The conditional branch can't be folded, handle the general case.
     // Update DominatorTree to reflect the CFG change we just made.  Then split
     // edges as necessary to preserve LoopSimplify form.
     if (DT) {
       // Everything that was dominated by the old loop header is now dominated
       // by the original loop preheader. Conceptually the header was merged
       // into the preheader, even though we reuse the actual block as a new
       // loop latch.
if (DT) {
 
           // Remember if this changes the DomTree.
           if (Node->getIDom()->getBlock() != NearestDom) {
             DT->changeImmediateDominator(BB, NearestDom);
             Changed = true;
           }
         }
 
         // If the dominator changed, this may have an effect on other
         // predecessors, continue until we reach a fixpoint.
       } while (Changed);
     }
   }
 
   assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
   assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
 
   // Now that the CFG and DomTree are in a consistent state again, try to merge
for (BasicBlock::iterator I = Begin; I != End; ++I) {
 
     switch (I->getOpcode()) {
     default:
       return false;
     case Instruction::GetElementPtr:
       // GEPs are cheap if all indices are constant.
       if (!cast<GEPOperator>(I)->hasAllConstantIndices())
         return false;
-      // fall-thru to increment case
     case Instruction::Add:
     case Instruction::Sub:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor:
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr: {
-      Value *IVOpnd = !isa<Constant>(I->getOperand(0))
-                          ? I->getOperand(0)
-                          : !isa<Constant>(I->getOperand(1))
-                                ? I->getOperand(1)
-                                : nullptr;
+      Value *IVOpnd =
+          !isa<Constant>(I->getOperand(0))
+              : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr;
       if (!IVOpnd)
         return false;
 
       // If increment operand is used outside of the loop, this speculation
       // could cause extra live range interference.
       if (MultiExitLoop) {
         for (User *UseI : IVOpnd->users()) {
           auto *UserInst = cast<Instruction>(UseI);

 /// Fold the loop tail into the loop exit by speculating the loop tail
 /// instructions. Typically, this is a single post-increment. In the case of a
 /// simple 2-block loop, hoisting the increment can be much better than
 /// duplicating the entire loop header. In the case of loops with early exits,
 /// rotation will not work anyway, but simplifyLoopLatch will put the loop in
 /// canonical form so downstream passes can handle it.
 ///
 /// I don't believe this invalidates SCEV.
-static bool simplifyLoopLatch(Loop *L, LoopInfo *LI, DominatorTree *DT) {
+bool LoopRotate::simplifyLoopLatch(Loop *L) {
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch || Latch->hasAddressTaken())
     return false;
 
   BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
   if (!Jmp || !Jmp->isUnconditional())
     return false;
 
   BasicBlock *LastExit = Latch->getSinglePredecessor();
   if (!LastExit || !L->isLoopExiting(LastExit))
     return false;
 
   BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
   if (!BI)
     return false;
 
   if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
     return false;
 
   DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
                << LastExit->getName() << "\n");
 
   // Hoist the instructions from Latch into LastExit.
   LastExit->getInstList().splice(BI->getIterator(), Latch->getInstList(),
                                  Latch->begin(), Jmp->getIterator());
 
   unsigned FallThruPath = BI->getSuccessor(0) == Latch ? 0 : 1;
   BasicBlock *Header = Jmp->getSuccessor(0);
   assert(Header == L->getHeader() && "expected a backward branch");
 
   // Remove Latch from the CFG so that LastExit becomes the new Latch.
   BI->setSuccessor(FallThruPath, Header);
   Latch->replaceSuccessorsPhiUsesWith(LastExit);
   Jmp->eraseFromParent();
 
   // Nuke the Latch block.
   assert(Latch->empty() && "unable to evacuate Latch");
   LI->removeBlock(Latch);
   if (DT)
     DT->eraseNode(Latch);
   Latch->eraseFromParent();
   return true;
 }
 
 /// 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) {
+bool LoopRotate::processLoop(Loop *L) {
   // 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);
+  bool SimplifiedLatch = simplifyLoopLatch(L);
 
-  bool MadeChange =
-      rotateLoop(L, MaxHeaderSize, LI, TTI, AC, DT, SE, SimplifiedLatch);
+  bool MadeChange = rotateLoop(L, 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) {}
+LoopRotatePass::LoopRotatePass() {}
 
 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);
+  LoopRotate LR(DefaultRotationThreshold, LI, TTI, AC, DT, SE);
 
-  bool Changed = processLoop(&L, MaxHeaderSize, LI, TTI, AC, DT, SE);
+  bool Changed = LR.processLoop(&L);
   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 processLoop(L, MaxHeaderSize, LI, TTI, AC, DT, SE);
+    LoopRotate LR(MaxHeaderSize, LI, TTI, AC, DT, SE);
+    return LR.processLoop(L);
   }
 };
 }
 
 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)
+INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
+                    false)
 
 Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
   return new LoopRotateLegacyPass(MaxHeaderSize);
 }