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