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