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/Analysis/AssumptionCache.h" |
15 | #include "llvm/Analysis/InstructionSimplify.h" |
16 | #include "llvm/Analysis/LazyBlockFrequencyInfo.h" |
17 | #include "llvm/Analysis/LoopInfo.h" |
18 | #include "llvm/Analysis/LoopPass.h" |
19 | #include "llvm/Analysis/MemorySSA.h" |
20 | #include "llvm/Analysis/MemorySSAUpdater.h" |
21 | #include "llvm/Analysis/ScalarEvolution.h" |
22 | #include "llvm/Analysis/TargetTransformInfo.h" |
23 | #include "llvm/InitializePasses.h" |
24 | #include "llvm/Support/CommandLine.h" |
25 | #include "llvm/Transforms/Scalar.h" |
26 | #include "llvm/Transforms/Utils/LoopRotationUtils.h" |
27 | #include "llvm/Transforms/Utils/LoopUtils.h" |
28 | #include <optional> |
29 | using namespace llvm; |
30 | |
31 | #define DEBUG_TYPE "loop-rotate" |
32 | |
33 | static cl::opt<unsigned> DefaultRotationThreshold( |
34 | "rotation-max-header-size" , cl::init(Val: 16), cl::Hidden, |
35 | cl::desc("The default maximum header size for automatic loop rotation" )); |
36 | |
37 | static cl::opt<bool> PrepareForLTOOption( |
38 | "rotation-prepare-for-lto" , cl::init(Val: false), cl::Hidden, |
39 | cl::desc("Run loop-rotation in the prepare-for-lto stage. This option " |
40 | "should be used for testing only." )); |
41 | |
42 | LoopRotatePass::LoopRotatePass(bool , bool PrepareForLTO) |
43 | : EnableHeaderDuplication(EnableHeaderDuplication), |
44 | PrepareForLTO(PrepareForLTO) {} |
45 | |
46 | void LoopRotatePass::printPipeline( |
47 | raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { |
48 | static_cast<PassInfoMixin<LoopRotatePass> *>(this)->printPipeline( |
49 | OS, MapClassName2PassName); |
50 | OS << "<" ; |
51 | if (!EnableHeaderDuplication) |
52 | OS << "no-" ; |
53 | OS << "header-duplication;" ; |
54 | |
55 | if (!PrepareForLTO) |
56 | OS << "no-" ; |
57 | OS << "prepare-for-lto" ; |
58 | OS << ">" ; |
59 | } |
60 | |
61 | PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM, |
62 | LoopStandardAnalysisResults &AR, |
63 | LPMUpdater &) { |
64 | // Vectorization requires loop-rotation. Use default threshold for loops the |
65 | // user explicitly marked for vectorization, even when header duplication is |
66 | // disabled. |
67 | int Threshold = EnableHeaderDuplication || |
68 | hasVectorizeTransformation(L: &L) == TM_ForcedByUser |
69 | ? DefaultRotationThreshold |
70 | : 0; |
71 | const DataLayout &DL = L.getHeader()->getModule()->getDataLayout(); |
72 | const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL); |
73 | |
74 | std::optional<MemorySSAUpdater> MSSAU; |
75 | if (AR.MSSA) |
76 | MSSAU = MemorySSAUpdater(AR.MSSA); |
77 | bool Changed = LoopRotation(L: &L, LI: &AR.LI, TTI: &AR.TTI, AC: &AR.AC, DT: &AR.DT, SE: &AR.SE, |
78 | MSSAU: MSSAU ? &*MSSAU : nullptr, SQ, RotationOnly: false, Threshold, |
79 | IsUtilMode: false, PrepareForLTO: PrepareForLTO || PrepareForLTOOption); |
80 | |
81 | if (!Changed) |
82 | return PreservedAnalyses::all(); |
83 | |
84 | if (AR.MSSA && VerifyMemorySSA) |
85 | AR.MSSA->verifyMemorySSA(); |
86 | |
87 | auto PA = getLoopPassPreservedAnalyses(); |
88 | if (AR.MSSA) |
89 | PA.preserve<MemorySSAAnalysis>(); |
90 | return PA; |
91 | } |
92 | |
93 | namespace { |
94 | |
95 | class LoopRotateLegacyPass : public LoopPass { |
96 | unsigned ; |
97 | bool PrepareForLTO; |
98 | |
99 | public: |
100 | static char ID; // Pass ID, replacement for typeid |
101 | LoopRotateLegacyPass(int = -1, |
102 | bool PrepareForLTO = false) |
103 | : LoopPass(ID), PrepareForLTO(PrepareForLTO) { |
104 | initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry()); |
105 | if (SpecifiedMaxHeaderSize == -1) |
106 | MaxHeaderSize = DefaultRotationThreshold; |
107 | else |
108 | MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize); |
109 | } |
110 | |
111 | // LCSSA form makes instruction renaming easier. |
112 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
113 | AU.addRequired<AssumptionCacheTracker>(); |
114 | AU.addRequired<TargetTransformInfoWrapperPass>(); |
115 | AU.addPreserved<MemorySSAWrapperPass>(); |
116 | getLoopAnalysisUsage(AU); |
117 | |
118 | // Lazy BFI and BPI are marked as preserved here so LoopRotate |
119 | // can remain part of the same loop pass manager as LICM. |
120 | AU.addPreserved<LazyBlockFrequencyInfoPass>(); |
121 | AU.addPreserved<LazyBranchProbabilityInfoPass>(); |
122 | } |
123 | |
124 | bool runOnLoop(Loop *L, LPPassManager &LPM) override { |
125 | if (skipLoop(L)) |
126 | return false; |
127 | Function &F = *L->getHeader()->getParent(); |
128 | |
129 | auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
130 | const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); |
131 | auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); |
132 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
133 | auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
134 | const SimplifyQuery SQ = getBestSimplifyQuery(*this, F); |
135 | std::optional<MemorySSAUpdater> MSSAU; |
136 | // Not requiring MemorySSA and getting it only if available will split |
137 | // the loop pass pipeline when LoopRotate is being run first. |
138 | auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>(); |
139 | if (MSSAA) |
140 | MSSAU = MemorySSAUpdater(&MSSAA->getMSSA()); |
141 | // Vectorization requires loop-rotation. Use default threshold for loops the |
142 | // user explicitly marked for vectorization, even when header duplication is |
143 | // disabled. |
144 | int Threshold = hasVectorizeTransformation(L) == TM_ForcedByUser |
145 | ? DefaultRotationThreshold |
146 | : MaxHeaderSize; |
147 | |
148 | return LoopRotation(L, LI, TTI, AC, DT: &DT, SE: &SE, MSSAU: MSSAU ? &*MSSAU : nullptr, SQ, |
149 | RotationOnly: false, Threshold, IsUtilMode: false, |
150 | PrepareForLTO: PrepareForLTO || PrepareForLTOOption); |
151 | } |
152 | }; |
153 | } // end namespace |
154 | |
155 | char LoopRotateLegacyPass::ID = 0; |
156 | INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate" , "Rotate Loops" , |
157 | false, false) |
158 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) |
159 | INITIALIZE_PASS_DEPENDENCY(LoopPass) |
160 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) |
161 | INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) |
162 | INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate" , "Rotate Loops" , false, |
163 | false) |
164 | |
165 | Pass *llvm::createLoopRotatePass(int , bool PrepareForLTO) { |
166 | return new LoopRotateLegacyPass(MaxHeaderSize, PrepareForLTO); |
167 | } |
168 | |