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