LoopPass.cpp revision 5ee99979065d75605d150d7e567e4351024aae8f
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 "llvm/Analysis/ScalarEvolutionExpander.h" 18using namespace llvm; 19 20//===----------------------------------------------------------------------===// 21// LPPassManager 22// 23/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. 24 25LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { 26 skipThisLoop = false; 27 redoThisLoop = false; 28 LI = NULL; 29 CurrentLoop = NULL; 30} 31 32/// Delete loop from the loop queue and loop hierarcy (LoopInfo). 33void LPPassManager::deleteLoopFromQueue(Loop *L) { 34 35 if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop. 36 // Reparent all of the blocks in this loop. Since BBLoop had a parent, 37 // they are now all in it. 38 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 39 I != E; ++I) 40 if (LI->getLoopFor(*I) == L) // Don't change blocks in subloops. 41 LI->changeLoopFor(*I, ParentLoop); 42 43 // Remove the loop from its parent loop. 44 for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; 45 ++I) { 46 assert(I != E && "Couldn't find loop"); 47 if (*I == L) { 48 ParentLoop->removeChildLoop(I); 49 break; 50 } 51 } 52 53 // Move all subloops into the parent loop. 54 while (L->begin() != L->end()) 55 ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1)); 56 } else { 57 // Reparent all of the blocks in this loop. Since BBLoop had no parent, 58 // they no longer in a loop at all. 59 60 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 61 // Don't change blocks in subloops. 62 if (LI->getLoopFor(L->getBlocks()[i]) == L) { 63 LI->removeBlock(L->getBlocks()[i]); 64 --i; 65 } 66 } 67 68 // Remove the loop from the top-level LoopInfo object. 69 for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) { 70 assert(I != E && "Couldn't find loop"); 71 if (*I == L) { 72 LI->removeLoop(I); 73 break; 74 } 75 } 76 77 // Move all of the subloops to the top-level. 78 while (L->begin() != L->end()) 79 LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); 80 } 81 82 delete L; 83 84 // If L is current loop then skip rest of the passes and let 85 // runOnFunction remove L from LQ. Otherwise, remove L from LQ now 86 // and continue applying other passes on CurrentLoop. 87 if (CurrentLoop == L) { 88 skipThisLoop = true; 89 return; 90 } 91 92 for (std::deque<Loop *>::iterator I = LQ.begin(), 93 E = LQ.end(); I != E; ++I) { 94 if (*I == L) { 95 LQ.erase(I); 96 break; 97 } 98 } 99} 100 101// Inset loop into loop nest (LoopInfo) and loop queue (LQ). 102void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { 103 104 assert (CurrentLoop != L && "Cannot insert CurrentLoop"); 105 106 // Insert into loop nest 107 if (ParentLoop) 108 ParentLoop->addChildLoop(L); 109 else 110 LI->addTopLevelLoop(L); 111 112 // Insert L into loop queue 113 if (L == CurrentLoop) 114 redoLoop(L); 115 else if (!ParentLoop) 116 // This is top level loop. 117 LQ.push_front(L); 118 else { 119 // Insert L after ParentLoop 120 for (std::deque<Loop *>::iterator I = LQ.begin(), 121 E = LQ.end(); I != E; ++I) { 122 if (*I == ParentLoop) { 123 // deque does not support insert after. 124 ++I; 125 LQ.insert(I, 1, L); 126 break; 127 } 128 } 129 } 130} 131 132// Reoptimize this loop. LPPassManager will re-insert this loop into the 133// queue. This allows LoopPass to change loop nest for the loop. This 134// utility may send LPPassManager into infinite loops so use caution. 135void LPPassManager::redoLoop(Loop *L) { 136 assert (CurrentLoop == L && "Can redo only CurrentLoop"); 137 redoThisLoop = true; 138} 139 140// Recurse through all subloops and all loops into LQ. 141static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { 142 LQ.push_back(L); 143 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 144 addLoopIntoQueue(*I, LQ); 145} 146 147/// Pass Manager itself does not invalidate any analysis info. 148void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { 149 // LPPassManager needs LoopInfo. In the long term LoopInfo class will 150 // become part of LPPassManager. 151 Info.addRequired<LoopInfo>(); 152 // Used by IndVar doInitialization. 153 Info.addRequired<ScalarEvolution>(); 154 Info.setPreservesAll(); 155} 156 157/// run - Execute all of the passes scheduled for execution. Keep track of 158/// whether any of the passes modifies the function, and if so, return true. 159bool LPPassManager::runOnFunction(Function &F) { 160 LI = &getAnalysis<LoopInfo>(); 161 bool Changed = false; 162 163 // Populate Loop Queue 164 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 165 addLoopIntoQueue(*I, LQ); 166 167 // Initialization 168 for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end(); 169 I != E; ++I) { 170 Loop *L = *I; 171 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 172 Pass *P = getContainedPass(Index); 173 LoopPass *LP = dynamic_cast<LoopPass *>(P); 174 if (LP) 175 Changed |= LP->doInitialization(L, *this); 176 } 177 } 178 179 // Walk Loops 180 while (!LQ.empty()) { 181 182 CurrentLoop = LQ.back(); 183 skipThisLoop = false; 184 redoThisLoop = false; 185 186 // Run all passes on current SCC 187 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 188 189 Pass *P = getContainedPass(Index); 190 AnalysisUsage AnUsage; 191 P->getAnalysisUsage(AnUsage); 192 193 dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, ""); 194 dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet()); 195 196 initializeAnalysisImpl(P); 197 198 StartPassTimer(P); 199 LoopPass *LP = dynamic_cast<LoopPass *>(P); 200 assert (LP && "Invalid LPPassManager member"); 201 LP->runOnLoop(CurrentLoop, *this); 202 StopPassTimer(P); 203 204 if (Changed) 205 dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, ""); 206 dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet()); 207 208 removeNotPreservedAnalysis(P); 209 recordAvailableAnalysis(P); 210 removeDeadPasses(P, "", ON_LOOP_MSG); 211 212 if (skipThisLoop) 213 // Do not run other passes on this loop. 214 break; 215 } 216 217 // Pop the loop from queue after running all passes. 218 LQ.pop_back(); 219 220 if (redoThisLoop) 221 LQ.push_back(CurrentLoop); 222 } 223 224 // Finalization 225 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 226 Pass *P = getContainedPass(Index); 227 LoopPass *LP = dynamic_cast <LoopPass *>(P); 228 if (LP) 229 Changed |= LP->doFinalization(); 230 } 231 232 return Changed; 233} 234 235 236//===----------------------------------------------------------------------===// 237// LoopPass 238 239// Check if this pass is suitable for the current LPPassManager, if 240// available. This pass P is not suitable for a LPPassManager if P 241// is not preserving higher level analysis info used by other 242// LPPassManager passes. In such case, pop LPPassManager from the 243// stack. This will force assignPassManager() to create new 244// LPPassManger as expected. 245void LoopPass::preparePassManager(PMStack &PMS) { 246 247 // Find LPPassManager 248 while (!PMS.empty()) { 249 if (PMS.top()->getPassManagerType() > PMT_LoopPassManager) 250 PMS.pop(); 251 else; 252 break; 253 } 254 255 LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 256 257 // If this pass is destroying high level information that is used 258 // by other passes that are managed by LPM then do not insert 259 // this pass in current LPM. Use new LPPassManager. 260 if (LPPM && !LPPM->preserveHigherLevelAnalysis(this)) 261 PMS.pop(); 262} 263 264/// Assign pass manager to manage this pass. 265void LoopPass::assignPassManager(PMStack &PMS, 266 PassManagerType PreferredType) { 267 // Find LPPassManager 268 while (!PMS.empty()) { 269 if (PMS.top()->getPassManagerType() > PMT_LoopPassManager) 270 PMS.pop(); 271 else; 272 break; 273 } 274 275 LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 276 277 // Create new Loop Pass Manager if it does not exist. 278 if (!LPPM) { 279 280 assert (!PMS.empty() && "Unable to create Loop Pass Manager"); 281 PMDataManager *PMD = PMS.top(); 282 283 // [1] Create new Call Graph Pass Manager 284 LPPM = new LPPassManager(PMD->getDepth() + 1); 285 LPPM->populateInheritedAnalysis(PMS); 286 287 // [2] Set up new manager's top level manager 288 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 289 TPM->addIndirectPassManager(LPPM); 290 291 // [3] Assign manager to manage this new manager. This may create 292 // and push new managers into PMS 293 Pass *P = dynamic_cast<Pass *>(LPPM); 294 TPM->schedulePass(P); 295 296 // [4] Push new manager into PMS 297 PMS.push(LPPM); 298 } 299 300 LPPM->add(this); 301} 302 303