• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
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 LoopPass and LPPassManager. All loop optimization
11 // and transformation passes are derived from LoopPass. LPPassManager is
12 // responsible for managing LoopPasses.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/LoopPass.h"
17 #include "llvm/DebugInfoProbe.h"
18 #include "llvm/Assembly/PrintModulePass.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/ManagedStatic.h"
21 #include "llvm/Support/Timer.h"
22 using namespace llvm;
23 
24 namespace {
25 
26 /// PrintLoopPass - Print a Function corresponding to a Loop.
27 ///
28 class PrintLoopPass : public LoopPass {
29 private:
30   std::string Banner;
31   raw_ostream &Out;       // raw_ostream to print on.
32 
33 public:
34   static char ID;
PrintLoopPass(const std::string & B,raw_ostream & o)35   PrintLoopPass(const std::string &B, raw_ostream &o)
36       : LoopPass(ID), Banner(B), Out(o) {}
37 
getAnalysisUsage(AnalysisUsage & AU) const38   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
39     AU.setPreservesAll();
40   }
41 
runOnLoop(Loop * L,LPPassManager &)42   bool runOnLoop(Loop *L, LPPassManager &) {
43     Out << Banner;
44     for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
45          b != be;
46          ++b) {
47       (*b)->print(Out);
48     }
49     return false;
50   }
51 };
52 
53 char PrintLoopPass::ID = 0;
54 }
55 
56 //===----------------------------------------------------------------------===//
57 // DebugInfoProbe
58 
59 static DebugInfoProbeInfo *TheDebugProbe;
createDebugInfoProbe()60 static void createDebugInfoProbe() {
61   if (TheDebugProbe) return;
62 
63   // Constructed the first time this is called. This guarantees that the
64   // object will be constructed, if -enable-debug-info-probe is set,
65   // before static globals, thus it will be destroyed before them.
66   static ManagedStatic<DebugInfoProbeInfo> DIP;
67   TheDebugProbe = &*DIP;
68 }
69 
70 //===----------------------------------------------------------------------===//
71 // LPPassManager
72 //
73 
74 char LPPassManager::ID = 0;
75 
LPPassManager()76 LPPassManager::LPPassManager()
77   : FunctionPass(ID), PMDataManager() {
78   skipThisLoop = false;
79   redoThisLoop = false;
80   LI = NULL;
81   CurrentLoop = NULL;
82 }
83 
84 /// Delete loop from the loop queue and loop hierarchy (LoopInfo).
deleteLoopFromQueue(Loop * L)85 void LPPassManager::deleteLoopFromQueue(Loop *L) {
86 
87   LI->updateUnloop(L);
88 
89   // If L is current loop then skip rest of the passes and let
90   // runOnFunction remove L from LQ. Otherwise, remove L from LQ now
91   // and continue applying other passes on CurrentLoop.
92   if (CurrentLoop == L)
93     skipThisLoop = true;
94 
95   delete L;
96 
97   if (skipThisLoop)
98     return;
99 
100   for (std::deque<Loop *>::iterator I = LQ.begin(),
101          E = LQ.end(); I != E; ++I) {
102     if (*I == L) {
103       LQ.erase(I);
104       break;
105     }
106   }
107 }
108 
109 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).
insertLoop(Loop * L,Loop * ParentLoop)110 void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) {
111 
112   assert (CurrentLoop != L && "Cannot insert CurrentLoop");
113 
114   // Insert into loop nest
115   if (ParentLoop)
116     ParentLoop->addChildLoop(L);
117   else
118     LI->addTopLevelLoop(L);
119 
120   insertLoopIntoQueue(L);
121 }
122 
insertLoopIntoQueue(Loop * L)123 void LPPassManager::insertLoopIntoQueue(Loop *L) {
124   // Insert L into loop queue
125   if (L == CurrentLoop)
126     redoLoop(L);
127   else if (!L->getParentLoop())
128     // This is top level loop.
129     LQ.push_front(L);
130   else {
131     // Insert L after the parent loop.
132     for (std::deque<Loop *>::iterator I = LQ.begin(),
133            E = LQ.end(); I != E; ++I) {
134       if (*I == L->getParentLoop()) {
135         // deque does not support insert after.
136         ++I;
137         LQ.insert(I, 1, L);
138         break;
139       }
140     }
141   }
142 }
143 
144 // Reoptimize this loop. LPPassManager will re-insert this loop into the
145 // queue. This allows LoopPass to change loop nest for the loop. This
146 // utility may send LPPassManager into infinite loops so use caution.
redoLoop(Loop * L)147 void LPPassManager::redoLoop(Loop *L) {
148   assert (CurrentLoop == L && "Can redo only CurrentLoop");
149   redoThisLoop = true;
150 }
151 
152 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
153 /// all loop passes.
cloneBasicBlockSimpleAnalysis(BasicBlock * From,BasicBlock * To,Loop * L)154 void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
155                                                   BasicBlock *To, Loop *L) {
156   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
157     LoopPass *LP = getContainedPass(Index);
158     LP->cloneBasicBlockAnalysis(From, To, L);
159   }
160 }
161 
162 /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
deleteSimpleAnalysisValue(Value * V,Loop * L)163 void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
164   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
165     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;
166          ++BI) {
167       Instruction &I = *BI;
168       deleteSimpleAnalysisValue(&I, L);
169     }
170   }
171   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
172     LoopPass *LP = getContainedPass(Index);
173     LP->deleteAnalysisValue(V, L);
174   }
175 }
176 
177 
178 // Recurse through all subloops and all loops  into LQ.
addLoopIntoQueue(Loop * L,std::deque<Loop * > & LQ)179 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
180   LQ.push_back(L);
181   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
182     addLoopIntoQueue(*I, LQ);
183 }
184 
185 /// Pass Manager itself does not invalidate any analysis info.
getAnalysisUsage(AnalysisUsage & Info) const186 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
187   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
188   // become part of LPPassManager.
189   Info.addRequired<LoopInfo>();
190   Info.setPreservesAll();
191 }
192 
193 /// run - Execute all of the passes scheduled for execution.  Keep track of
194 /// whether any of the passes modifies the function, and if so, return true.
runOnFunction(Function & F)195 bool LPPassManager::runOnFunction(Function &F) {
196   LI = &getAnalysis<LoopInfo>();
197   bool Changed = false;
198   createDebugInfoProbe();
199 
200   // Collect inherited analysis from Module level pass manager.
201   populateInheritedAnalysis(TPM->activeStack);
202 
203   // Populate Loop Queue
204   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
205     addLoopIntoQueue(*I, LQ);
206 
207   if (LQ.empty()) // No loops, skip calling finalizers
208     return false;
209 
210   // Initialization
211   for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
212        I != E; ++I) {
213     Loop *L = *I;
214     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
215       LoopPass *P = getContainedPass(Index);
216       Changed |= P->doInitialization(L, *this);
217     }
218   }
219 
220   // Walk Loops
221   while (!LQ.empty()) {
222 
223     CurrentLoop  = LQ.back();
224     skipThisLoop = false;
225     redoThisLoop = false;
226 
227     // Run all passes on the current Loop.
228     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
229       LoopPass *P = getContainedPass(Index);
230       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
231                    CurrentLoop->getHeader()->getName());
232       dumpRequiredSet(P);
233 
234       initializeAnalysisImpl(P);
235       if (TheDebugProbe)
236         TheDebugProbe->initialize(P, F);
237       {
238         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
239         TimeRegion PassTimer(getPassTimer(P));
240 
241         Changed |= P->runOnLoop(CurrentLoop, *this);
242       }
243       if (TheDebugProbe)
244         TheDebugProbe->finalize(P, F);
245 
246       if (Changed)
247         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
248                      skipThisLoop ? "<deleted>" :
249                                     CurrentLoop->getHeader()->getName());
250       dumpPreservedSet(P);
251 
252       if (!skipThisLoop) {
253         // Manually check that this loop is still healthy. This is done
254         // instead of relying on LoopInfo::verifyLoop since LoopInfo
255         // is a function pass and it's really expensive to verify every
256         // loop in the function every time. That level of checking can be
257         // enabled with the -verify-loop-info option.
258         {
259           TimeRegion PassTimer(getPassTimer(LI));
260           CurrentLoop->verifyLoop();
261         }
262 
263         // Then call the regular verifyAnalysis functions.
264         verifyPreservedAnalysis(P);
265       }
266 
267       removeNotPreservedAnalysis(P);
268       recordAvailableAnalysis(P);
269       removeDeadPasses(P,
270                        skipThisLoop ? "<deleted>" :
271                                       CurrentLoop->getHeader()->getName(),
272                        ON_LOOP_MSG);
273 
274       if (skipThisLoop)
275         // Do not run other passes on this loop.
276         break;
277     }
278 
279     // If the loop was deleted, release all the loop passes. This frees up
280     // some memory, and avoids trouble with the pass manager trying to call
281     // verifyAnalysis on them.
282     if (skipThisLoop)
283       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
284         Pass *P = getContainedPass(Index);
285         freePass(P, "<deleted>", ON_LOOP_MSG);
286       }
287 
288     // Pop the loop from queue after running all passes.
289     LQ.pop_back();
290 
291     if (redoThisLoop)
292       LQ.push_back(CurrentLoop);
293   }
294 
295   // Finalization
296   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
297     LoopPass *P = getContainedPass(Index);
298     Changed |= P->doFinalization();
299   }
300 
301   return Changed;
302 }
303 
304 /// Print passes managed by this manager
dumpPassStructure(unsigned Offset)305 void LPPassManager::dumpPassStructure(unsigned Offset) {
306   errs().indent(Offset*2) << "Loop Pass Manager\n";
307   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
308     Pass *P = getContainedPass(Index);
309     P->dumpPassStructure(Offset + 1);
310     dumpLastUses(P, Offset+1);
311   }
312 }
313 
314 
315 //===----------------------------------------------------------------------===//
316 // LoopPass
317 
createPrinterPass(raw_ostream & O,const std::string & Banner) const318 Pass *LoopPass::createPrinterPass(raw_ostream &O,
319                                   const std::string &Banner) const {
320   return new PrintLoopPass(Banner, O);
321 }
322 
323 // Check if this pass is suitable for the current LPPassManager, if
324 // available. This pass P is not suitable for a LPPassManager if P
325 // is not preserving higher level analysis info used by other
326 // LPPassManager passes. In such case, pop LPPassManager from the
327 // stack. This will force assignPassManager() to create new
328 // LPPassManger as expected.
preparePassManager(PMStack & PMS)329 void LoopPass::preparePassManager(PMStack &PMS) {
330 
331   // Find LPPassManager
332   while (!PMS.empty() &&
333          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
334     PMS.pop();
335 
336   // If this pass is destroying high level information that is used
337   // by other passes that are managed by LPM then do not insert
338   // this pass in current LPM. Use new LPPassManager.
339   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
340       !PMS.top()->preserveHigherLevelAnalysis(this))
341     PMS.pop();
342 }
343 
344 /// Assign pass manager to manage this pass.
assignPassManager(PMStack & PMS,PassManagerType PreferredType)345 void LoopPass::assignPassManager(PMStack &PMS,
346                                  PassManagerType PreferredType) {
347   // Find LPPassManager
348   while (!PMS.empty() &&
349          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
350     PMS.pop();
351 
352   LPPassManager *LPPM;
353   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
354     LPPM = (LPPassManager*)PMS.top();
355   else {
356     // Create new Loop Pass Manager if it does not exist.
357     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
358     PMDataManager *PMD = PMS.top();
359 
360     // [1] Create new Loop Pass Manager
361     LPPM = new LPPassManager();
362     LPPM->populateInheritedAnalysis(PMS);
363 
364     // [2] Set up new manager's top level manager
365     PMTopLevelManager *TPM = PMD->getTopLevelManager();
366     TPM->addIndirectPassManager(LPPM);
367 
368     // [3] Assign manager to manage this new manager. This may create
369     // and push new managers into PMS
370     Pass *P = LPPM->getAsPass();
371     TPM->schedulePass(P);
372 
373     // [4] Push new manager into PMS
374     PMS.push(LPPM);
375   }
376 
377   LPPM->add(this);
378 }
379