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