1 | //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===// |
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 LoopPass and LPPassManager. All loop optimization |
10 | // and transformation passes are derived from LoopPass. LPPassManager is |
11 | // responsible for managing LoopPasses. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #include "llvm/Analysis/LoopPass.h" |
16 | #include "llvm/Analysis/LoopInfo.h" |
17 | #include "llvm/IR/Dominators.h" |
18 | #include "llvm/IR/LLVMContext.h" |
19 | #include "llvm/IR/OptBisect.h" |
20 | #include "llvm/IR/PassTimingInfo.h" |
21 | #include "llvm/IR/PrintPasses.h" |
22 | #include "llvm/InitializePasses.h" |
23 | #include "llvm/Support/Debug.h" |
24 | #include "llvm/Support/TimeProfiler.h" |
25 | #include "llvm/Support/Timer.h" |
26 | #include "llvm/Support/raw_ostream.h" |
27 | using namespace llvm; |
28 | |
29 | #define DEBUG_TYPE "loop-pass-manager" |
30 | |
31 | namespace { |
32 | |
33 | /// PrintLoopPass - Print a Function corresponding to a Loop. |
34 | /// |
35 | class PrintLoopPassWrapper : public LoopPass { |
36 | raw_ostream &OS; |
37 | std::string Banner; |
38 | |
39 | public: |
40 | static char ID; |
41 | PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {} |
42 | PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner) |
43 | : LoopPass(ID), OS(OS), Banner(Banner) {} |
44 | |
45 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
46 | AU.setPreservesAll(); |
47 | } |
48 | |
49 | bool runOnLoop(Loop *L, LPPassManager &) override { |
50 | auto BBI = llvm::find_if(Range: L->blocks(), P: [](BasicBlock *BB) { return BB; }); |
51 | if (BBI != L->blocks().end() && |
52 | isFunctionInPrintList(FunctionName: (*BBI)->getParent()->getName())) { |
53 | printLoop(L&: *L, OS, Banner); |
54 | } |
55 | return false; |
56 | } |
57 | |
58 | StringRef getPassName() const override { return "Print Loop IR" ; } |
59 | }; |
60 | |
61 | char PrintLoopPassWrapper::ID = 0; |
62 | } |
63 | |
64 | //===----------------------------------------------------------------------===// |
65 | // LPPassManager |
66 | // |
67 | |
68 | char LPPassManager::ID = 0; |
69 | |
70 | LPPassManager::LPPassManager() : FunctionPass(ID) { |
71 | LI = nullptr; |
72 | CurrentLoop = nullptr; |
73 | } |
74 | |
75 | // Insert loop into loop nest (LoopInfo) and loop queue (LQ). |
76 | void LPPassManager::addLoop(Loop &L) { |
77 | if (L.isOutermost()) { |
78 | // This is the top level loop. |
79 | LQ.push_front(x: &L); |
80 | return; |
81 | } |
82 | |
83 | // Insert L into the loop queue after the parent loop. |
84 | for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) { |
85 | if (*I == L.getParentLoop()) { |
86 | // deque does not support insert after. |
87 | ++I; |
88 | LQ.insert(position: I, n: 1, x: &L); |
89 | return; |
90 | } |
91 | } |
92 | } |
93 | |
94 | // Recurse through all subloops and all loops into LQ. |
95 | static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { |
96 | LQ.push_back(x: L); |
97 | for (Loop *I : reverse(C&: *L)) |
98 | addLoopIntoQueue(L: I, LQ); |
99 | } |
100 | |
101 | /// Pass Manager itself does not invalidate any analysis info. |
102 | void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { |
103 | // LPPassManager needs LoopInfo. In the long term LoopInfo class will |
104 | // become part of LPPassManager. |
105 | Info.addRequired<LoopInfoWrapperPass>(); |
106 | Info.addRequired<DominatorTreeWrapperPass>(); |
107 | Info.setPreservesAll(); |
108 | } |
109 | |
110 | void LPPassManager::markLoopAsDeleted(Loop &L) { |
111 | assert((&L == CurrentLoop || CurrentLoop->contains(&L)) && |
112 | "Must not delete loop outside the current loop tree!" ); |
113 | // If this loop appears elsewhere within the queue, we also need to remove it |
114 | // there. However, we have to be careful to not remove the back of the queue |
115 | // as that is assumed to match the current loop. |
116 | assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!" ); |
117 | llvm::erase(C&: LQ, V: &L); |
118 | |
119 | if (&L == CurrentLoop) { |
120 | CurrentLoopDeleted = true; |
121 | // Add this loop back onto the back of the queue to preserve our invariants. |
122 | LQ.push_back(x: &L); |
123 | } |
124 | } |
125 | |
126 | /// run - Execute all of the passes scheduled for execution. Keep track of |
127 | /// whether any of the passes modifies the function, and if so, return true. |
128 | bool LPPassManager::runOnFunction(Function &F) { |
129 | auto &LIWP = getAnalysis<LoopInfoWrapperPass>(); |
130 | LI = &LIWP.getLoopInfo(); |
131 | Module &M = *F.getParent(); |
132 | #if 0 |
133 | DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
134 | #endif |
135 | bool Changed = false; |
136 | |
137 | // Collect inherited analysis from Module level pass manager. |
138 | populateInheritedAnalysis(PMS&: TPM->activeStack); |
139 | |
140 | // Populate the loop queue in reverse program order. There is no clear need to |
141 | // process sibling loops in either forward or reverse order. There may be some |
142 | // advantage in deleting uses in a later loop before optimizing the |
143 | // definitions in an earlier loop. If we find a clear reason to process in |
144 | // forward order, then a forward variant of LoopPassManager should be created. |
145 | // |
146 | // Note that LoopInfo::iterator visits loops in reverse program |
147 | // order. Here, reverse_iterator gives us a forward order, and the LoopQueue |
148 | // reverses the order a third time by popping from the back. |
149 | for (Loop *L : reverse(C&: *LI)) |
150 | addLoopIntoQueue(L, LQ); |
151 | |
152 | if (LQ.empty()) // No loops, skip calling finalizers |
153 | return false; |
154 | |
155 | // Initialization |
156 | for (Loop *L : LQ) { |
157 | for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { |
158 | LoopPass *P = getContainedPass(N: Index); |
159 | Changed |= P->doInitialization(L, LPM&: *this); |
160 | } |
161 | } |
162 | |
163 | // Walk Loops |
164 | unsigned InstrCount, FunctionSize = 0; |
165 | StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount; |
166 | bool = M.shouldEmitInstrCountChangedRemark(); |
167 | // Collect the initial size of the module and the function we're looking at. |
168 | if (EmitICRemark) { |
169 | InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount); |
170 | FunctionSize = F.getInstructionCount(); |
171 | } |
172 | while (!LQ.empty()) { |
173 | CurrentLoopDeleted = false; |
174 | CurrentLoop = LQ.back(); |
175 | |
176 | // Run all passes on the current Loop. |
177 | for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { |
178 | LoopPass *P = getContainedPass(N: Index); |
179 | |
180 | llvm::TimeTraceScope LoopPassScope("RunLoopPass" , P->getPassName()); |
181 | |
182 | dumpPassInfo(P, S1: EXECUTION_MSG, S2: ON_LOOP_MSG, |
183 | Msg: CurrentLoop->getHeader()->getName()); |
184 | dumpRequiredSet(P); |
185 | |
186 | initializeAnalysisImpl(P); |
187 | |
188 | bool LocalChanged = false; |
189 | { |
190 | PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader()); |
191 | TimeRegion PassTimer(getPassTimer(P)); |
192 | #ifdef EXPENSIVE_CHECKS |
193 | uint64_t RefHash = P->structuralHash(F); |
194 | #endif |
195 | LocalChanged = P->runOnLoop(L: CurrentLoop, LPM&: *this); |
196 | |
197 | #ifdef EXPENSIVE_CHECKS |
198 | if (!LocalChanged && (RefHash != P->structuralHash(F))) { |
199 | llvm::errs() << "Pass modifies its input and doesn't report it: " |
200 | << P->getPassName() << "\n" ; |
201 | llvm_unreachable("Pass modifies its input and doesn't report it" ); |
202 | } |
203 | #endif |
204 | |
205 | Changed |= LocalChanged; |
206 | if (EmitICRemark) { |
207 | unsigned NewSize = F.getInstructionCount(); |
208 | // Update the size of the function, emit a remark, and update the |
209 | // size of the module. |
210 | if (NewSize != FunctionSize) { |
211 | int64_t Delta = static_cast<int64_t>(NewSize) - |
212 | static_cast<int64_t>(FunctionSize); |
213 | emitInstrCountChangedRemark(P, M, Delta, CountBefore: InstrCount, |
214 | FunctionToInstrCount, F: &F); |
215 | InstrCount = static_cast<int64_t>(InstrCount) + Delta; |
216 | FunctionSize = NewSize; |
217 | } |
218 | } |
219 | } |
220 | |
221 | if (LocalChanged) |
222 | dumpPassInfo(P, S1: MODIFICATION_MSG, S2: ON_LOOP_MSG, |
223 | Msg: CurrentLoopDeleted ? "<deleted loop>" |
224 | : CurrentLoop->getName()); |
225 | dumpPreservedSet(P); |
226 | |
227 | if (!CurrentLoopDeleted) { |
228 | // Manually check that this loop is still healthy. This is done |
229 | // instead of relying on LoopInfo::verifyLoop since LoopInfo |
230 | // is a function pass and it's really expensive to verify every |
231 | // loop in the function every time. That level of checking can be |
232 | // enabled with the -verify-loop-info option. |
233 | { |
234 | TimeRegion PassTimer(getPassTimer(&LIWP)); |
235 | CurrentLoop->verifyLoop(); |
236 | } |
237 | // Here we apply same reasoning as in the above case. Only difference |
238 | // is that LPPassManager might run passes which do not require LCSSA |
239 | // form (LoopPassPrinter for example). We should skip verification for |
240 | // such passes. |
241 | // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the |
242 | // verification! |
243 | #if 0 |
244 | if (mustPreserveAnalysisID(LCSSAVerificationPass::ID)) |
245 | assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI)); |
246 | #endif |
247 | |
248 | // Then call the regular verifyAnalysis functions. |
249 | verifyPreservedAnalysis(P); |
250 | |
251 | F.getContext().yield(); |
252 | } |
253 | |
254 | if (LocalChanged) |
255 | removeNotPreservedAnalysis(P); |
256 | recordAvailableAnalysis(P); |
257 | removeDeadPasses(P, |
258 | Msg: CurrentLoopDeleted ? "<deleted>" |
259 | : CurrentLoop->getHeader()->getName(), |
260 | ON_LOOP_MSG); |
261 | |
262 | if (CurrentLoopDeleted) |
263 | // Do not run other passes on this loop. |
264 | break; |
265 | } |
266 | |
267 | // If the loop was deleted, release all the loop passes. This frees up |
268 | // some memory, and avoids trouble with the pass manager trying to call |
269 | // verifyAnalysis on them. |
270 | if (CurrentLoopDeleted) { |
271 | for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { |
272 | Pass *P = getContainedPass(N: Index); |
273 | freePass(P, Msg: "<deleted>" , ON_LOOP_MSG); |
274 | } |
275 | } |
276 | |
277 | // Pop the loop from queue after running all passes. |
278 | LQ.pop_back(); |
279 | } |
280 | |
281 | // Finalization |
282 | for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { |
283 | LoopPass *P = getContainedPass(N: Index); |
284 | Changed |= P->doFinalization(); |
285 | } |
286 | |
287 | return Changed; |
288 | } |
289 | |
290 | /// Print passes managed by this manager |
291 | void LPPassManager::dumpPassStructure(unsigned Offset) { |
292 | errs().indent(NumSpaces: Offset*2) << "Loop Pass Manager\n" ; |
293 | for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { |
294 | Pass *P = getContainedPass(N: Index); |
295 | P->dumpPassStructure(Offset: Offset + 1); |
296 | dumpLastUses(P, Offset: Offset+1); |
297 | } |
298 | } |
299 | |
300 | |
301 | //===----------------------------------------------------------------------===// |
302 | // LoopPass |
303 | |
304 | Pass *LoopPass::createPrinterPass(raw_ostream &O, |
305 | const std::string &Banner) const { |
306 | return new PrintLoopPassWrapper(O, Banner); |
307 | } |
308 | |
309 | // Check if this pass is suitable for the current LPPassManager, if |
310 | // available. This pass P is not suitable for a LPPassManager if P |
311 | // is not preserving higher level analysis info used by other |
312 | // LPPassManager passes. In such case, pop LPPassManager from the |
313 | // stack. This will force assignPassManager() to create new |
314 | // LPPassManger as expected. |
315 | void LoopPass::preparePassManager(PMStack &PMS) { |
316 | |
317 | // Find LPPassManager |
318 | while (!PMS.empty() && |
319 | PMS.top()->getPassManagerType() > PMT_LoopPassManager) |
320 | PMS.pop(); |
321 | |
322 | // If this pass is destroying high level information that is used |
323 | // by other passes that are managed by LPM then do not insert |
324 | // this pass in current LPM. Use new LPPassManager. |
325 | if (PMS.top()->getPassManagerType() == PMT_LoopPassManager && |
326 | !PMS.top()->preserveHigherLevelAnalysis(P: this)) |
327 | PMS.pop(); |
328 | } |
329 | |
330 | /// Assign pass manager to manage this pass. |
331 | void LoopPass::assignPassManager(PMStack &PMS, |
332 | PassManagerType PreferredType) { |
333 | // Find LPPassManager |
334 | while (!PMS.empty() && |
335 | PMS.top()->getPassManagerType() > PMT_LoopPassManager) |
336 | PMS.pop(); |
337 | |
338 | LPPassManager *LPPM; |
339 | if (PMS.top()->getPassManagerType() == PMT_LoopPassManager) |
340 | LPPM = (LPPassManager*)PMS.top(); |
341 | else { |
342 | // Create new Loop Pass Manager if it does not exist. |
343 | assert (!PMS.empty() && "Unable to create Loop Pass Manager" ); |
344 | PMDataManager *PMD = PMS.top(); |
345 | |
346 | // [1] Create new Loop Pass Manager |
347 | LPPM = new LPPassManager(); |
348 | LPPM->populateInheritedAnalysis(PMS); |
349 | |
350 | // [2] Set up new manager's top level manager |
351 | PMTopLevelManager *TPM = PMD->getTopLevelManager(); |
352 | TPM->addIndirectPassManager(Manager: LPPM); |
353 | |
354 | // [3] Assign manager to manage this new manager. This may create |
355 | // and push new managers into PMS |
356 | Pass *P = LPPM->getAsPass(); |
357 | TPM->schedulePass(P); |
358 | |
359 | // [4] Push new manager into PMS |
360 | PMS.push(PM: LPPM); |
361 | } |
362 | |
363 | LPPM->add(P: this); |
364 | } |
365 | |
366 | static std::string getDescription(const Loop &L) { |
367 | return "loop" ; |
368 | } |
369 | |
370 | bool LoopPass::skipLoop(const Loop *L) const { |
371 | const Function *F = L->getHeader()->getParent(); |
372 | if (!F) |
373 | return false; |
374 | // Check the opt bisect limit. |
375 | OptPassGate &Gate = F->getContext().getOptPassGate(); |
376 | if (Gate.isEnabled() && |
377 | !Gate.shouldRunPass(PassName: this->getPassName(), IRDescription: getDescription(L: *L))) |
378 | return true; |
379 | // Check for the OptimizeNone attribute. |
380 | if (F->hasOptNone()) { |
381 | // FIXME: Report this to dbgs() only once per function. |
382 | LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function " |
383 | << F->getName() << "\n" ); |
384 | // FIXME: Delete loop from pass manager's queue? |
385 | return true; |
386 | } |
387 | return false; |
388 | } |
389 | |
390 | LCSSAVerificationPass::LCSSAVerificationPass() : FunctionPass(ID) { |
391 | initializeLCSSAVerificationPassPass(*PassRegistry::getPassRegistry()); |
392 | } |
393 | |
394 | char LCSSAVerificationPass::ID = 0; |
395 | INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification" , "LCSSA Verifier" , |
396 | false, false) |
397 | |