LoopPass.cpp revision 622adea47feebbab6119e7863475b479880d70ba
12faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===// 22faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// 32faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// The LLVM Compiler Infrastructure 42faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// 52faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// This file was developed by Devang Patel and is distributed under 62faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// the University of Illinois Open Source License. See LICENSE.TXT for details. 72faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// 82faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes//===----------------------------------------------------------------------===// 92faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// 102faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// This file implements LoopPass and LPPassManager. All loop optimization 112faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// and transformation passes are derived from LoopPass. LPPassManager is 122faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// responsible for managing LoopPasses. 132faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes// 142faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes//===----------------------------------------------------------------------===// 152faa5f1271587cda765f26bcf2951065300a01ffElliott Hughes 16e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom#include "llvm/Analysis/LoopPass.h" 17e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstromusing namespace llvm; 18e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom 19700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom//===----------------------------------------------------------------------===// 204e1d579d6401fef2dd57b16f8d406e33221a69d9Calin Juravle// LPPassManager 2106d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko// 22daab38ca60c5b91787e29c87a161a2bb8c1b6f11Andreas Gampe/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. 23700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom 247848da48a0a4241dedc1cc83ac4931e61575eb92Andreas GampeLPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { 251baabf0726eb285284e0c908ccba9f209b399faeDavid Srbecky skipThisLoop = false; 261baabf0726eb285284e0c908ccba9f209b399faeDavid Srbecky redoThisLoop = false; 271baabf0726eb285284e0c908ccba9f209b399faeDavid Srbecky LI = NULL; 28e5fed03772144595c0904faf3d6974cc55214c8cRichard Uhler CurrentLoop = NULL; 29e5fed03772144595c0904faf3d6974cc55214c8cRichard Uhler} 30fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe 31bb661c0f0cb72d4bbfc2e251f6ded6949a713292Bilyan Borisov/// Delete loop from the loop queue and loop hierarcy (LoopInfo). 32fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampevoid LPPassManager::deleteLoopFromQueue(Loop *L) { 33fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe 34fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop. 3546ee31b67d7ee1bd085fbc240502053caa3cf8faAndreas Gampe // Reparent all of the blocks in this loop. Since BBLoop had a parent, 3646ee31b67d7ee1bd085fbc240502053caa3cf8faAndreas Gampe // they are now all in it. 37c6ea7d00ad069a2736f603daa3d8eaa9a1f8ea11Andreas Gampe for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 38ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom I != E; ++I) 39542451cc546779f5c67840e105c51205a1b0a8fdAndreas Gampe if (LI->getLoopFor(*I) == L) // Don't change blocks in subloops. 401aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes LI->changeLoopFor(*I, ParentLoop); 4132ce2adefb8a3d0eda59a29f5e87c1eb43eef796Mathieu Chartier 42761600567d73b23324ae0251e871c15d6849ffd8Elliott Hughes // Remove the loop from its parent loop. 43a5b09a67034e57a6e10231dd4bd92f4cb50b824cAndreas Gampe for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; 44700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom ++I) { 4584d7605f93f1e6e86a16e02017e305c90e93117aAlex Light assert(I != E && "Couldn't find loop"); 46aad75c6d5bfab2dc8e30fc99fafe8cd2dc8b74d8Vladimir Marko if (*I == L) { 47700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom ParentLoop->removeChildLoop(I); 481baabf0726eb285284e0c908ccba9f209b399faeDavid Srbecky break; 492dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers } 504f6ad8ab428038129b2d0d6c40b7fd625cca15e1Ian Rogers } 51c04c800e7bda94abfadc8c2d30f58c50b261b612Nicolas Geoffray 52f9c6fc610b27887f832e453a0da1789187293408Mathieu Chartier // Move all subloops into the parent loop. 53e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom while (L->begin() != L->end()) 5422f8e5c82d12951be38cd893426e13bee33fd69dAndreas Gampe ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1)); 559bdf108885a27ba05fae8501725649574d7c491bVladimir Marko } else { 569aa352e92b6ca0f2250cb7f54dfbf4b1be714c19David Sehr // Reparent all of the blocks in this loop. Since BBLoop had no parent, 572dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers // they no longer in a loop at all. 5809d0943f5efe92c1f3a6b9dbdf255adb0f960a22Vladimir Marko 5997d7e1cd7f733cb33a0e238bec6d7ed525638cd1Vladimir Marko for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 60e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom // Don't change blocks in subloops. 61e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom if (LI->getLoopFor(L->getBlocks()[i]) == L) { 62e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom LI->removeBlock(L->getBlocks()[i]); 6346ee31b67d7ee1bd085fbc240502053caa3cf8faAndreas Gampe --i; 6446ee31b67d7ee1bd085fbc240502053caa3cf8faAndreas Gampe } 65049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 661baabf0726eb285284e0c908ccba9f209b399faeDavid Srbecky 67fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe // Remove the loop from the top-level LoopInfo object. 68049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) { 69fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe assert(I != E && "Couldn't find loop"); 70fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe if (*I == L) { 71fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe LI->removeLoop(I); 721baabf0726eb285284e0c908ccba9f209b399faeDavid Srbecky break; 73fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe } 74fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe } 75fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe 76fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe // Move all of the subloops to the top-level. 77049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe while (L->begin() != L->end()) 78049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); 79049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 80049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 81049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe delete L; 82049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 83049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // If L is current loop then skip rest of the passes and let 84049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // runOnFunction remove L from LQ. Otherwise, remove L from LQ now 85049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // and continue applying other passes on CurrentLoop. 86049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe if (CurrentLoop == L) { 87049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe skipThisLoop = true; 88049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe return; 89049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 90049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 91049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe for (std::deque<Loop *>::iterator I = LQ.begin(), 92049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe E = LQ.end(); I != E; ++I) { 93049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe if (*I == L) { 947b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil LQ.erase(I); 957b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil break; 9684d7605f93f1e6e86a16e02017e305c90e93117aAlex Light } 97049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 98049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe} 99049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 100049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe// Inset loop into loop nest (LoopInfo) and loop queue (LQ). 1010b4cbd0c2a75b47ae09d21e5d73d2b1709cb5b9eMathieu Chartiervoid LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { 102e5fed03772144595c0904faf3d6974cc55214c8cRichard Uhler 103049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe assert (CurrentLoop != L && "Cannot insert CurrentLoop"); 104fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe 105049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Insert into loop nest 106049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe if (ParentLoop) 107fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe ParentLoop->addChildLoop(L); 108049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe else 109049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe LI->addTopLevelLoop(L); 110956af0f0cb05422e38c1d22cbef309d16b8a1a12Elliott Hughes 1114075f830c58e38f1ac88a6b3c663fafefdb4b414Andreas Gampe // Insert L into loop queue 1124075f830c58e38f1ac88a6b3c663fafefdb4b414Andreas Gampe if (L == CurrentLoop) 1137b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil redoLoop(L); 1147b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil else if (!ParentLoop) 1157b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil // This is top level loop. 1167b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil LQ.push_front(L); 1177b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil else { 118049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Insert L after ParentLoop 119049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe for (std::deque<Loop *>::iterator I = LQ.begin(), 120049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe E = LQ.end(); I != E; ++I) { 121049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe if (*I == ParentLoop) { 1220b4cbd0c2a75b47ae09d21e5d73d2b1709cb5b9eMathieu Chartier // deque does not support insert after. 123049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe ++I; 124e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom LQ.insert(I, 1, L); 125049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe break; 126049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 127049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 128700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom } 129049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe} 130a59dd80f9f48cb750d329d4d4af2d99d72b484d1Alex Light 131049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe// Reoptimize this loop. LPPassManager will re-insert this loop into the 132fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe// queue. This allows LoopPass to change loop nest for the loop. This 133049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe// utility may send LPPassManager into infinite loops so use caution. 134e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstromvoid LPPassManager::redoLoop(Loop *L) { 135049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe assert (CurrentLoop != L && "Can redo only CurrentLoop"); 136049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe redoThisLoop = true; 137e58991b3b2282b5761f1a6023a16c803e1c4eb45Mathieu Chartier} 138e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom 139049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe// Recurse through all subloops and all loops into LQ. 140049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampestatic void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { 141700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom LQ.push_back(L); 142e24fa61603a60ade3797e4a0c8b3fccb346cb048Brian Carlstrom for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 143c93b3be140f6a57a572f2a4cdaf46aba87235a02David Brazdil addLoopIntoQueue(*I, LQ); 144c93b3be140f6a57a572f2a4cdaf46aba87235a02David Brazdil} 145c93b3be140f6a57a572f2a4cdaf46aba87235a02David Brazdil 146c93b3be140f6a57a572f2a4cdaf46aba87235a02David Brazdil/// Pass Manager itself does not invalidate any analysis info. 147049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampevoid LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { 148049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // LPPassManager needs LoopInfo. In the long term LoopInfo class will 149049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // become part of LPPassManager. 150049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe Info.addRequired<LoopInfo>(); 151049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe Info.setPreservesAll(); 1527b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil} 1537b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil 154049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe/// run - Execute all of the passes scheduled for execution. Keep track of 155049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe/// whether any of the passes modifies the function, and if so, return true. 156049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampebool LPPassManager::runOnFunction(Function &F) { 157049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe LI = &getAnalysis<LoopInfo>(); 158049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe bool Changed = false; 1590b4cbd0c2a75b47ae09d21e5d73d2b1709cb5b9eMathieu Chartier 160049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Populate Loop Queue 161049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 162049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe addLoopIntoQueue(*I, LQ); 1634075f830c58e38f1ac88a6b3c663fafefdb4b414Andreas Gampe 1644075f830c58e38f1ac88a6b3c663fafefdb4b414Andreas Gampe // Initialization 1654075f830c58e38f1ac88a6b3c663fafefdb4b414Andreas Gampe for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end(); 1667b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil I != E; ++I) { 1677b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil Loop *L = *I; 1687b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1697b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil Pass *P = getContainedPass(Index); 170049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe LoopPass *LP = dynamic_cast<LoopPass *>(P); 171049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe if (LP) 172049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe Changed |= LP->doInitialization(L, *this); 173049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 1740b4cbd0c2a75b47ae09d21e5d73d2b1709cb5b9eMathieu Chartier } 175049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 176049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Walk Loops 177fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe while (!LQ.empty()) { 178fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe 179049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe CurrentLoop = LQ.back(); 180049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe skipThisLoop = false; 181fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe redoThisLoop = false; 1824075f830c58e38f1ac88a6b3c663fafefdb4b414Andreas Gampe 183049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Run all passes on current SCC 1841baabf0726eb285284e0c908ccba9f209b399faeDavid Srbecky for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 185049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 186049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe Pass *P = getContainedPass(Index); 1875dedb808acf84712daf7dee3cf8137d4e34b4b78David Srbecky AnalysisUsage AnUsage; 1885dedb808acf84712daf7dee3cf8137d4e34b4b78David Srbecky P->getAnalysisUsage(AnUsage); 189049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 190fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, ""); 191fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet()); 1927b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil 1937b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil initializeAnalysisImpl(P); 1947b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil 1957b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil StartPassTimer(P); 1964e868fa7b8c47600695ff92deeb373674956a67dNicolas Geoffray LoopPass *LP = dynamic_cast<LoopPass *>(P); 1977b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil assert (LP && "Invalid LPPassManager member"); 1987b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil LP->runOnLoop(CurrentLoop, *this); 1997b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil StopPassTimer(P); 2007b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil 2017b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil if (Changed) 2027b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, ""); 2037b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet()); 2047b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil 2057b49e6cade09bc65b3b5f22d45fc9d0a7184e4f2David Brazdil removeNotPreservedAnalysis(P); 206049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe recordAvailableAnalysis(P); 207049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe removeDeadPasses(P, "", ON_LOOP_MSG); 208049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 209049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe if (skipThisLoop) 210049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Do not run other passes on this loop. 211fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe break; 212049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 213049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 214049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Pop the loop from queue after running all passes. 215700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom LQ.pop_back(); 216700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom 217fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe if (redoThisLoop) 218f97cf2a7d8089ca74a4920a5e0c351e070cc6e60Nicolas Geoffray LQ.push_back(CurrentLoop); 2197ec0904eac1d799d3443b4c5e83545b72eae9ad3Andreas Gampe } 220f97cf2a7d8089ca74a4920a5e0c351e070cc6e60Nicolas Geoffray 221f97cf2a7d8089ca74a4920a5e0c351e070cc6e60Nicolas Geoffray // Finalization 2228d31bbd3d6536de12bc20e3d29cfe03fe848f9daIan Rogers for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 223049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe Pass *P = getContainedPass(Index); 224049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe LoopPass *LP = dynamic_cast <LoopPass *>(P); 225700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom if (LP) 226700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom Changed |= LP->doFinalization(); 227049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe } 228fa8429b967fe2260ece572337534c9dda6c50d8aAndreas Gampe 229049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe return Changed; 230049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe} 231049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe 232700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom 233700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom//===----------------------------------------------------------------------===// 234700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom// LoopPass 235700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom 2365c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko// Check if this pass is suitable for the current LPPassManager, if 237049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe// available. This pass P is not suitable for a LPPassManager if P 2385c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko// is not preserving higher level analysis info used by other 239049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe// LPPassManager passes. In such case, pop LPPassManager from the 2405c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko// stack. This will force assignPassManager() to create new 2415c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko// LPPassManger as expected. 242049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampevoid LoopPass::preparePassManager(PMStack &PMS) { 2435c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko 244049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // Find LPPassManager 2455c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko while (!PMS.empty()) { 2465c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko if (PMS.top()->getPassManagerType() > PMT_LoopPassManager) 2475c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko PMS.pop(); 2485c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko else; 2490eb882bfc5d260e8014c26adfda11602065aa5d8Vladimir Marko break; 2500eb882bfc5d260e8014c26adfda11602065aa5d8Vladimir Marko } 2510eb882bfc5d260e8014c26adfda11602065aa5d8Vladimir Marko 252aad75c6d5bfab2dc8e30fc99fafe8cd2dc8b74d8Vladimir Marko LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 253aad75c6d5bfab2dc8e30fc99fafe8cd2dc8b74d8Vladimir Marko 2545c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko // If this pass is destroying high level information that is used 2555c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko // by other passes that are managed by LPM then do not insert 256049cff0ed5e28aa17a17e456efe3121b6d58910fAndreas Gampe // this pass in current LPM. Use new LPPassManager. 257700c8d31733534a3d978b75a03f6f7e177dc7e81Brian Carlstrom if (LPPM && !LPPM->preserveHigherLevelAnalysis(this)) 2586e3b1d900cc456a2717944f1f562a2f4df000705Brian Carlstrom PMS.pop(); 25906d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko} 26006d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko 26106d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko/// Assign pass manager to manage this pass. 26206d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Markovoid LoopPass::assignPassManager(PMStack &PMS, 263722fa98e0ed3796575930eb8e3d5fc89046f01ccVladimir Marko PassManagerType PreferredType) { 264722fa98e0ed3796575930eb8e3d5fc89046f01ccVladimir Marko // Find LPPassManager 265722fa98e0ed3796575930eb8e3d5fc89046f01ccVladimir Marko while (!PMS.empty()) { 26606d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko if (PMS.top()->getPassManagerType() > PMT_LoopPassManager) 26706d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko PMS.pop(); 26806d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko else; 26906d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko break; 27006d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko } 27106d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko 27206d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 27306d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko 27406d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko // Create new Loop Pass Manager if it does not exist. 27506d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko if (!LPPM) { 27606d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko 27706d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko assert (!PMS.empty() && "Unable to create Loop Pass Manager"); 27806d7aaa75f3d6d21fe904d54208b28e486673d97Vladimir Marko PMDataManager *PMD = PMS.top(); 279c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson 280c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson // [1] Create new Call Graph Pass Manager 281c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson LPPM = new LPPassManager(PMD->getDepth() + 1); 282c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson 283c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson // [2] Set up new manager's top level manager 284c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson PMTopLevelManager *TPM = PMD->getTopLevelManager(); 285c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson TPM->addIndirectPassManager(LPPM); 286c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson 287c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson // [3] Assign manager to manage this new manager. This may create 288c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson // and push new managers into PMS 289c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson Pass *P = dynamic_cast<Pass *>(LPPM); 290c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson TPM->schedulePass(P); 291c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson 292c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson // [4] Push new manager into PMS 293c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson PMS.push(LPPM); 294c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson } 295c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson 296c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson LPPM->add(this); 297c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson} 298c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson 299c069a30d42aefd902c20e8bc09dfad1683f07dedOrion Hodson