LoopPass.cpp revision c7e49c08c22658dd16a5cac1500b0b70047bedc4 
1//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Devang Patel and is distributed under
6// the University of Illinois Open Source 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/ScalarEvolutionExpander.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->begin() != L->end())
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->begin() != L->end())
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      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      if (skipThisLoop)
238        // Do not run other passes on this loop.
239        break;
240    }
241
242    // Pop the loop from queue after running all passes.
243    LQ.pop_back();
244
245    if (redoThisLoop)
246      LQ.push_back(CurrentLoop);
247  }
248
249  // Finalization
250  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
251    Pass *P = getContainedPass(Index);
252    LoopPass *LP = dynamic_cast <LoopPass *>(P);
253    if (LP)
254      Changed |= LP->doFinalization();
255  }
256
257  return Changed;
258}
259
260
261//===----------------------------------------------------------------------===//
262// LoopPass
263
264// Check if this pass is suitable for the current LPPassManager, if
265// available. This pass P is not suitable for a LPPassManager if P
266// is not preserving higher level analysis info used by other
267// LPPassManager passes. In such case, pop LPPassManager from the
268// stack. This will force assignPassManager() to create new
269// LPPassManger as expected.
270void LoopPass::preparePassManager(PMStack &PMS) {
271
272  // Find LPPassManager
273  while (!PMS.empty() &&
274         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
275    PMS.pop();
276
277  LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
278
279  // If this pass is destroying high level information that is used
280  // by other passes that are managed by LPM then do not insert
281  // this pass in current LPM. Use new LPPassManager.
282  if (LPPM && !LPPM->preserveHigherLevelAnalysis(this))
283    PMS.pop();
284}
285
286/// Assign pass manager to manage this pass.
287void LoopPass::assignPassManager(PMStack &PMS,
288                                 PassManagerType PreferredType) {
289  // Find LPPassManager
290  while (!PMS.empty() &&
291         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
292    PMS.pop();
293
294  LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
295
296  // Create new Loop Pass Manager if it does not exist.
297  if (!LPPM) {
298
299    assert (!PMS.empty() && "Unable to create Loop Pass Manager");
300    PMDataManager *PMD = PMS.top();
301
302    // [1] Create new Call Graph Pass Manager
303    LPPM = new LPPassManager(PMD->getDepth() + 1);
304    LPPM->populateInheritedAnalysis(PMS);
305
306    // [2] Set up new manager's top level manager
307    PMTopLevelManager *TPM = PMD->getTopLevelManager();
308    TPM->addIndirectPassManager(LPPM);
309
310    // [3] Assign manager to manage this new manager. This may create
311    // and push new managers into PMS
312    Pass *P = dynamic_cast<Pass *>(LPPM);
313    TPM->schedulePass(P);
314
315    // [4] Push new manager into PMS
316    PMS.push(LPPM);
317  }
318
319  LPPM->add(this);
320}
321