1 //===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements Loop Rotation Pass. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Transforms/Scalar/LoopRotation.h" 14 #include "llvm/ADT/Statistic.h" 15 #include "llvm/Analysis/InstructionSimplify.h" 16 #include "llvm/Analysis/LoopPass.h" 17 #include "llvm/Analysis/MemorySSA.h" 18 #include "llvm/Analysis/MemorySSAUpdater.h" 19 #include "llvm/Analysis/ScalarEvolution.h" 20 #include "llvm/Analysis/TargetTransformInfo.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Transforms/Scalar.h" 23 #include "llvm/Transforms/Scalar/LoopPassManager.h" 24 #include "llvm/Transforms/Utils/LoopRotationUtils.h" 25 #include "llvm/Transforms/Utils/LoopUtils.h" 26 using namespace llvm; 27 28 #define DEBUG_TYPE "loop-rotate" 29 30 static cl::opt<unsigned> DefaultRotationThreshold( 31 "rotation-max-header-size", cl::init(16), cl::Hidden, 32 cl::desc("The default maximum header size for automatic loop rotation")); 33 34 LoopRotatePass::LoopRotatePass(bool EnableHeaderDuplication) 35 : EnableHeaderDuplication(EnableHeaderDuplication) {} 36 37 PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM, 38 LoopStandardAnalysisResults &AR, 39 LPMUpdater &) { 40 int Threshold = EnableHeaderDuplication ? DefaultRotationThreshold : 0; 41 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout(); 42 const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL); 43 44 Optional<MemorySSAUpdater> MSSAU; 45 if (AR.MSSA) 46 MSSAU = MemorySSAUpdater(AR.MSSA); 47 bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE, 48 MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, 49 SQ, false, Threshold, false); 50 51 if (!Changed) 52 return PreservedAnalyses::all(); 53 54 if (AR.MSSA && VerifyMemorySSA) 55 AR.MSSA->verifyMemorySSA(); 56 57 auto PA = getLoopPassPreservedAnalyses(); 58 if (EnableMSSALoopDependency) 59 PA.preserve<MemorySSAAnalysis>(); 60 return PA; 61 } 62 63 namespace { 64 65 class LoopRotateLegacyPass : public LoopPass { 66 unsigned MaxHeaderSize; 67 68 public: 69 static char ID; // Pass ID, replacement for typeid 70 LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) { 71 initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry()); 72 if (SpecifiedMaxHeaderSize == -1) 73 MaxHeaderSize = DefaultRotationThreshold; 74 else 75 MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize); 76 } 77 78 // LCSSA form makes instruction renaming easier. 79 void getAnalysisUsage(AnalysisUsage &AU) const override { 80 AU.addRequired<AssumptionCacheTracker>(); 81 AU.addRequired<TargetTransformInfoWrapperPass>(); 82 if (EnableMSSALoopDependency) { 83 AU.addRequired<MemorySSAWrapperPass>(); 84 AU.addPreserved<MemorySSAWrapperPass>(); 85 } 86 getLoopAnalysisUsage(AU); 87 } 88 89 bool runOnLoop(Loop *L, LPPassManager &LPM) override { 90 if (skipLoop(L)) 91 return false; 92 Function &F = *L->getHeader()->getParent(); 93 94 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 95 const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 96 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 97 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 98 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; 99 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 100 auto *SE = SEWP ? &SEWP->getSE() : nullptr; 101 const SimplifyQuery SQ = getBestSimplifyQuery(*this, F); 102 Optional<MemorySSAUpdater> MSSAU; 103 if (EnableMSSALoopDependency) { 104 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA(); 105 MSSAU = MemorySSAUpdater(MSSA); 106 } 107 return LoopRotation(L, LI, TTI, AC, DT, SE, 108 MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ, 109 false, MaxHeaderSize, false); 110 } 111 }; 112 } 113 114 char LoopRotateLegacyPass::ID = 0; 115 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", 116 false, false) 117 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 118 INITIALIZE_PASS_DEPENDENCY(LoopPass) 119 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 120 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) 121 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false, 122 false) 123 124 Pass *llvm::createLoopRotatePass(int MaxHeaderSize) { 125 return new LoopRotateLegacyPass(MaxHeaderSize); 126 } 127