LoopPass.cpp revision 193323 
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  if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
156    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;
157         ++BI) {
158      Instruction &I = *BI;
159      deleteSimpleAnalysisValue(&I, L);
160    }
161  }
162  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
163    Pass *P = getContainedPass(Index);
164    LoopPass *LP = dynamic_cast<LoopPass *>(P);
165    LP->deleteAnalysisValue(V, L);
166  }
167}
168
169
170// Recurse through all subloops and all loops  into LQ.
171static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
172  LQ.push_back(L);
173  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
174    addLoopIntoQueue(*I, LQ);
175}
176
177/// Pass Manager itself does not invalidate any analysis info.
178void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
179  // LPPassManager needs LoopInfo. In the long term LoopInfo class will
180  // become part of LPPassManager.
181  Info.addRequired<LoopInfo>();
182  Info.setPreservesAll();
183}
184
185/// run - Execute all of the passes scheduled for execution.  Keep track of
186/// whether any of the passes modifies the function, and if so, return true.
187bool LPPassManager::runOnFunction(Function &F) {
188  LI = &getAnalysis<LoopInfo>();
189  bool Changed = false;
190
191  // Collect inherited analysis from Module level pass manager.
192  populateInheritedAnalysis(TPM->activeStack);
193
194  // Populate Loop Queue
195  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
196    addLoopIntoQueue(*I, LQ);
197
198  // Initialization
199  for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
200       I != E; ++I) {
201    Loop *L = *I;
202    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
203      Pass *P = getContainedPass(Index);
204      LoopPass *LP = dynamic_cast<LoopPass *>(P);
205      if (LP)
206        Changed |= LP->doInitialization(L, *this);
207    }
208  }
209
210  // Walk Loops
211  while (!LQ.empty()) {
212
213    CurrentLoop  = LQ.back();
214    skipThisLoop = false;
215    redoThisLoop = false;
216
217    // Run all passes on current SCC
218    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
219      Pass *P = getContainedPass(Index);
220
221      dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, "");
222      dumpRequiredSet(P);
223
224      initializeAnalysisImpl(P);
225
226      LoopPass *LP = dynamic_cast<LoopPass *>(P);
227      {
228        PassManagerPrettyStackEntry X(LP, *CurrentLoop->getHeader());
229        StartPassTimer(P);
230        assert(LP && "Invalid LPPassManager member");
231        Changed |= LP->runOnLoop(CurrentLoop, *this);
232        StopPassTimer(P);
233      }
234
235      if (Changed)
236        dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, "");
237      dumpPreservedSet(P);
238
239      verifyPreservedAnalysis(LP);
240      removeNotPreservedAnalysis(P);
241      recordAvailableAnalysis(P);
242      removeDeadPasses(P, "", ON_LOOP_MSG);
243
244      // If dominator information is available then verify the info if requested.
245      verifyDomInfo(*LP, F);
246
247      if (skipThisLoop)
248        // Do not run other passes on this loop.
249        break;
250    }
251
252    // Pop the loop from queue after running all passes.
253    LQ.pop_back();
254
255    if (redoThisLoop)
256      LQ.push_back(CurrentLoop);
257  }
258
259  // Finalization
260  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
261    Pass *P = getContainedPass(Index);
262    LoopPass *LP = dynamic_cast <LoopPass *>(P);
263    if (LP)
264      Changed |= LP->doFinalization();
265  }
266
267  return Changed;
268}
269
270/// Print passes managed by this manager
271void LPPassManager::dumpPassStructure(unsigned Offset) {
272  llvm::cerr << std::string(Offset*2, ' ') << "Loop Pass Manager\n";
273  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
274    Pass *P = getContainedPass(Index);
275    P->dumpPassStructure(Offset + 1);
276    dumpLastUses(P, Offset+1);
277  }
278}
279
280
281//===----------------------------------------------------------------------===//
282// LoopPass
283
284// Check if this pass is suitable for the current LPPassManager, if
285// available. This pass P is not suitable for a LPPassManager if P
286// is not preserving higher level analysis info used by other
287// LPPassManager passes. In such case, pop LPPassManager from the
288// stack. This will force assignPassManager() to create new
289// LPPassManger as expected.
290void LoopPass::preparePassManager(PMStack &PMS) {
291
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  // If this pass is destroying high level information that is used
300  // by other passes that are managed by LPM then do not insert
301  // this pass in current LPM. Use new LPPassManager.
302  if (LPPM && !LPPM->preserveHigherLevelAnalysis(this))
303    PMS.pop();
304}
305
306/// Assign pass manager to manage this pass.
307void LoopPass::assignPassManager(PMStack &PMS,
308                                 PassManagerType PreferredType) {
309  // Find LPPassManager
310  while (!PMS.empty() &&
311         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
312    PMS.pop();
313
314  LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
315
316  // Create new Loop Pass Manager if it does not exist.
317  if (!LPPM) {
318
319    assert (!PMS.empty() && "Unable to create Loop Pass Manager");
320    PMDataManager *PMD = PMS.top();
321
322    // [1] Create new Call Graph Pass Manager
323    LPPM = new LPPassManager(PMD->getDepth() + 1);
324    LPPM->populateInheritedAnalysis(PMS);
325
326    // [2] Set up new manager's top level manager
327    PMTopLevelManager *TPM = PMD->getTopLevelManager();
328    TPM->addIndirectPassManager(LPPM);
329
330    // [3] Assign manager to manage this new manager. This may create
331    // and push new managers into PMS
332    Pass *P = dynamic_cast<Pass *>(LPPM);
333    TPM->schedulePass(P);
334
335    // [4] Push new manager into PMS
336    PMS.push(LPPM);
337  }
338
339  LPPM->add(this);
340}
341