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