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