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