xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/LoopPass.cpp (revision ec0ea6efa1ad229d75c394c1a9b9cac33af2b1d3)
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;
43   PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}
44   PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
45       : LoopPass(ID), OS(OS), Banner(Banner) {}
46 
47   void getAnalysisUsage(AnalysisUsage &AU) const override {
48     AU.setPreservesAll();
49   }
50 
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 
60   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 
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).
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.
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.
105 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 
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.
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
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 
307 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.
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.
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 
369 static std::string getDescription(const Loop &L) {
370   return "loop";
371 }
372 
373 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 
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