LoopPass.cpp revision a5057d02c05efc0ead8787c76a012382ef675b03 
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"
17using namespace llvm;
18
19//===----------------------------------------------------------------------===//
20// LPPassManager
21//
22/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses.
23
24LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) {
25  skipThisLoop = false;
26  redoThisLoop = false;
27}
28
29/// Delete loop from the loop queue. This is used by Loop pass to inform
30/// Loop Pass Manager that it should skip rest of the passes for this loop.
31void LPPassManager::deleteLoopFromQueue(Loop *L) {
32  // Do not pop loop from LQ here. It will be done by runOnFunction while loop.
33  skipThisLoop = true;
34}
35
36// Reoptimize this loop. LPPassManager will re-insert this loop into the
37// queue. This allows LoopPass to change loop nest for the loop. This
38// utility may send LPPassManager into infinite loops so use caution.
39void LPPassManager::redoLoop(Loop *L) {
40  redoThisLoop = true;
41}
42
43// Recurse through all subloops and all loops  into LQ.
44static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
45  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
46    addLoopIntoQueue(*I, LQ);
47  LQ.push_back(L);
48}
49
50/// run - Execute all of the passes scheduled for execution.  Keep track of
51/// whether any of the passes modifies the function, and if so, return true.
52bool LPPassManager::runOnFunction(Function &F) {
53  LoopInfo &LI = getAnalysis<LoopInfo>();
54  bool Changed = false;
55
56  // Populate Loop Queue
57  for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
58    addLoopIntoQueue(*I, LQ);
59
60  // Initialization
61  for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
62       I != E; ++I) {
63    Loop *L = *I;
64    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
65      Pass *P = getContainedPass(Index);
66      LoopPass *LP = dynamic_cast<LoopPass *>(P);
67      if (LP)
68        Changed |= LP->doInitialization(L, *this);
69    }
70  }
71
72  // Walk Loops
73  while (!LQ.empty()) {
74
75    Loop *L  = LQ.back();
76    skipThisLoop = false;
77    redoThisLoop = false;
78
79    // Run all passes on current SCC
80    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
81
82      Pass *P = getContainedPass(Index);
83      AnalysisUsage AnUsage;
84      P->getAnalysisUsage(AnUsage);
85
86      dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, "");
87      dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet());
88
89      initializeAnalysisImpl(P);
90
91      StartPassTimer(P);
92      LoopPass *LP = dynamic_cast<LoopPass *>(P);
93      assert (LP && "Invalid LPPassManager member");
94      LP->runOnLoop(L, *this);
95      StopPassTimer(P);
96
97      if (Changed)
98        dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, "");
99      dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet());
100
101      removeNotPreservedAnalysis(P);
102      recordAvailableAnalysis(P);
103      removeDeadPasses(P, "", ON_LOOP_MSG);
104
105      if (skipThisLoop)
106        // Do not run other passes on this loop.
107        break;
108    }
109
110    // Pop the loop from queue after running all passes.
111    LQ.pop_back();
112
113    if (redoThisLoop)
114      LQ.push_back(L);
115  }
116
117  // Finalization
118  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
119    Pass *P = getContainedPass(Index);
120    LoopPass *LP = dynamic_cast <LoopPass *>(P);
121    if (LP)
122      Changed |= LP->doFinalization();
123  }
124
125  return Changed;
126}
127
128
129//===----------------------------------------------------------------------===//
130// LoopPass
131
132/// Assign pass manager to manage this pass.
133void LoopPass::assignPassManager(PMStack &PMS,
134                                 PassManagerType PreferredType) {
135  // Find LPPassManager
136  while (!PMS.empty()) {
137    if (PMS.top()->getPassManagerType() > PMT_LoopPassManager)
138      PMS.pop();
139    else;
140    break;
141  }
142
143  LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
144
145  // Create new Loop Pass Manager if it does not exist.
146  if (!LPPM) {
147
148    assert (!PMS.empty() && "Unable to create Loop Pass Manager");
149    PMDataManager *PMD = PMS.top();
150
151    // [1] Create new Call Graph Pass Manager
152    LPPM = new LPPassManager(PMD->getDepth() + 1);
153
154    // [2] Set up new manager's top level manager
155    PMTopLevelManager *TPM = PMD->getTopLevelManager();
156    TPM->addIndirectPassManager(LPPM);
157
158    // [3] Assign manager to manage this new manager. This may create
159    // and push new managers into PMS
160    Pass *P = dynamic_cast<Pass *>(LPPM);
161    P->assignPassManager(PMS);
162
163    // [4] Push new manager into PMS
164    PMS.push(LPPM);
165  }
166
167  LPPM->add(this);
168}
169
170