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