lib/Analysis/LoopPass.cpp

   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 using namespace llvm;
  18
  19 //===----------------------------------------------------------------------===//
  20 // LPPassManager
  21 //
  22 /// LPPassManager manages FPPassManagers and CalLGraphSCCPasses.
  23
  24 LPPassManager::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.
  31 void 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.
  39 void LPPassManager::redoLoop(Loop *L) {
  40   redoThisLoop = true;
  41 }
  42
  43 // Recurse through all subloops and all loops  into LQ.
  44 static 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.
  52 bool 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 // Check if this pass is suitable for the current LPPassManager, if
 133 // available. This pass P is not suitable for a LPPassManager if P
 134 // is not preserving higher level analysis info used by other
 135 // LPPassManager passes. In such case, pop LPPassManager from the
 136 // stack. This will force assignPassManager() to create new
 137 // LPPassManger as expected.
 138 void LoopPass::preparePassManager(PMStack &PMS) {
 139
 140   // Find LPPassManager
 141   while (!PMS.empty()) {
 142     if (PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 143       PMS.pop();
 144     else;
 145     break;
 146   }
 147
 148   LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
 149
 150   // If this pass is destroying high level information that is used
 151   // by other passes that are managed by LPM then do not insert
 152   // this pass in current LPM. Use new LPPassManager.
 153   if (LPPM && !LPPM->preserveHigherLevelAnalysis(this))
 154     PMS.pop();
 155 }
 156
 157 /// Assign pass manager to manage this pass.
 158 void LoopPass::assignPassManager(PMStack &PMS,
 159                                  PassManagerType PreferredType) {
 160   // Find LPPassManager
 161   while (!PMS.empty()) {
 162     if (PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 163       PMS.pop();
 164     else;
 165     break;
 166   }
 167
 168   LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
 169
 170   // Create new Loop Pass Manager if it does not exist.
 171   if (!LPPM) {
 172
 173     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
 174     PMDataManager *PMD = PMS.top();
 175
 176     // [1] Create new Call Graph Pass Manager
 177     LPPM = new LPPassManager(PMD->getDepth() + 1);
 178
 179     // [2] Set up new manager's top level manager
 180     PMTopLevelManager *TPM = PMD->getTopLevelManager();
 181     TPM->addIndirectPassManager(LPPM);
 182
 183     // [3] Assign manager to manage this new manager. This may create
 184     // and push new managers into PMS
 185     Pass *P = dynamic_cast<Pass *>(LPPM);
 186     P->assignPassManager(PMS);
 187
 188     // [4] Push new manager into PMS
 189     PMS.push(LPPM);
 190   }
 191
 192   LPPM->add(this);
 193 }
 194