Index: llvm/trunk/include/llvm/Transforms/Scalar/LoopRotation.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar/LoopRotation.h +++ llvm/trunk/include/llvm/Transforms/Scalar/LoopRotation.h @@ -21,10 +21,8 @@ /// A simple loop rotation transformation. class LoopRotatePass : public PassInfoMixin { - unsigned MaxHeaderSize; public: LoopRotatePass(); - LoopRotatePass(unsigned MaxHeaderSize) : MaxHeaderSize(MaxHeaderSize) {} PreservedAnalyses run(Loop &L, AnalysisManager &AM); }; } Index: llvm/trunk/lib/Transforms/Scalar/LoopRotation.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopRotation.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopRotation.cpp @@ -43,12 +43,34 @@ #define DEBUG_TYPE "loop-rotate" -static cl::opt -DefaultRotationThreshold("rotation-max-header-size", cl::init(16), cl::Hidden, - cl::desc("The default maximum header size for automatic loop rotation")); +static cl::opt DefaultRotationThreshold( + "rotation-max-header-size", cl::init(16), cl::Hidden, + cl::desc("The default maximum header size for automatic loop rotation")); 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 @@ -82,7 +104,8 @@ // 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; @@ -117,12 +140,13 @@ 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(U.getUser()); - if (!UserInst) continue; + if (!UserInst) + continue; // The original users in the OrigHeader are already using the original // definitions. @@ -158,10 +182,7 @@ /// 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; @@ -199,12 +220,14 @@ 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) @@ -267,10 +290,9 @@ // 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(Inst) && !isa(Inst) && - !isa(Inst)) { + if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() && + !Inst->mayWriteToMemory() && !isa(Inst) && + !isa(Inst) && !isa(Inst)) { Inst->moveBefore(LoopEntryBranch); continue; } @@ -322,7 +344,6 @@ 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 @@ -333,8 +354,8 @@ BranchInst *PHBI = cast(OrigPreheader->getTerminator()); assert(PHBI->isConditional() && "Should be clone of BI condbr!"); if (!isa(PHBI->getCondition()) || - PHBI->getSuccessor(cast(PHBI->getCondition())->isZero()) - != NewHeader) { + PHBI->getSuccessor(cast(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. @@ -426,8 +447,8 @@ } } - // If the dominator changed, this may have an effect on other - // predecessors, continue until we reach a fixpoint. + // If the dominator changed, this may have an effect on other + // predecessors, continue until we reach a fixpoint. } while (Changed); } } @@ -474,7 +495,7 @@ // GEPs are cheap if all indices are constant. if (!cast(I)->hasAllConstantIndices()) return false; - // fall-thru to increment case + // fall-thru to increment case case Instruction::Add: case Instruction::Sub: case Instruction::And: @@ -483,11 +504,10 @@ case Instruction::Shl: case Instruction::LShr: case Instruction::AShr: { - Value *IVOpnd = !isa(I->getOperand(0)) - ? I->getOperand(0) - : !isa(I->getOperand(1)) - ? I->getOperand(1) - : nullptr; + Value *IVOpnd = + !isa(I->getOperand(0)) + ? I->getOperand(0) + : !isa(I->getOperand(1)) ? I->getOperand(1) : nullptr; if (!IVOpnd) return false; @@ -524,7 +544,7 @@ /// 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; @@ -545,7 +565,7 @@ return false; DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into " - << LastExit->getName() << "\n"); + << LastExit->getName() << "\n"); // Hoist the instructions from Latch into LastExit. LastExit->getInstList().splice(BI->getIterator(), Latch->getInstList(), @@ -570,19 +590,16 @@ } /// 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."); @@ -594,7 +611,7 @@ return MadeChange; } -LoopRotatePass::LoopRotatePass() : MaxHeaderSize(DefaultRotationThreshold) {} +LoopRotatePass::LoopRotatePass() {} PreservedAnalyses LoopRotatePass::run(Loop &L, AnalysisManager &AM) { auto &FAM = AM.getResult(L).getManager(); @@ -608,8 +625,9 @@ // Optional analyses. auto *DT = FAM.getCachedResult(*F); auto *SE = FAM.getCachedResult(*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(); @@ -649,8 +667,8 @@ auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; auto *SEWP = getAnalysisIfAvailable(); 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); } }; } @@ -661,8 +679,8 @@ 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);