LoopPass.cpp revision 5afdc7d78526622034932e6d07871c7b25d87361
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 return L1->getLoopDepth() > L2->getLoopDepth(); 30 } 31}; 32 33// Loop queue used by Loop Pass Manager. This is a wrapper class 34// that hides implemenation detail (use of priority_queue) inside .cpp file. 35class LoopQueue { 36public: 37 inline void push(Loop *L) { LPQ.push(L); } 38 inline void pop() { LPQ.pop(); } 39 inline Loop *top() { return LPQ.top(); } 40 inline bool empty() { return LPQ.empty(); } 41private: 42 std::priority_queue<Loop *, std::vector<Loop *>, LoopCompare> LPQ; 43}; 44 45} // End of LLVM namespace 46 47//===----------------------------------------------------------------------===// 48// LPPassManager 49// 50/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. 51 52LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { 53 LQ = new LoopQueue(); 54} 55 56LPPassManager::~LPPassManager() { 57 delete LQ; 58} 59 60/// Delete loop from the loop queue. This is used by Loop pass to inform 61/// Loop Pass Manager that it should skip rest of the passes for this loop. 62void LPPassManager::deleteLoopFromQueue(Loop *L) { 63 // Do not pop loop from LQ here. It will be done by runOnFunction while loop. 64 skipThisLoop = true; 65} 66 67// Recurse through all subloops and all loops into LQ. 68static void addLoopIntoQueue(Loop *L, LoopQueue *LQ) { 69 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 70 addLoopIntoQueue(*I, LQ); 71 LQ->push(L); 72} 73 74/// run - Execute all of the passes scheduled for execution. Keep track of 75/// whether any of the passes modifies the function, and if so, return true. 76bool LPPassManager::runOnFunction(Function &F) { 77 LoopInfo &LI = getAnalysis<LoopInfo>(); 78 bool Changed = false; 79 80 // Populate Loop Queue 81 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) 82 addLoopIntoQueue(*I, LQ); 83 84 std::string Msg1 = "Executing Pass '"; 85 std::string Msg3 = "' Made Modification '"; 86 87 // Walk Loops 88 while (!LQ->empty()) { 89 90 Loop *L = LQ->top(); 91 skipThisLoop = false; 92 93 // Run all passes on current SCC 94 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 95 96 Pass *P = getContainedPass(Index); 97 AnalysisUsage AnUsage; 98 P->getAnalysisUsage(AnUsage); 99 100 std::string Msg2 = "' on Loop ...\n'"; 101 dumpPassInfo(P, Msg1, Msg2); 102 dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet()); 103 104 initializeAnalysisImpl(P); 105 106 StartPassTimer(P); 107 LoopPass *LP = dynamic_cast<LoopPass *>(P); 108 assert (LP && "Invalid LPPassManager member"); 109 LP->runOnLoop(*L, *this); 110 StopPassTimer(P); 111 112 if (Changed) 113 dumpPassInfo(P, Msg3, Msg2); 114 dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet()); 115 116 removeNotPreservedAnalysis(P); 117 recordAvailableAnalysis(P); 118 removeDeadPasses(P, Msg2); 119 120 if (skipThisLoop) 121 // Do not run other passes on this loop. 122 break; 123 } 124 125 // Pop the loop from queue after running all passes. 126 LQ->pop(); 127 } 128 129 return Changed; 130} 131 132 133