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