LLVM API Documentation

LoopPass.cpp
Go to the documentation of this file.
00001 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements LoopPass and LPPassManager. All loop optimization
00011 // and transformation passes are derived from LoopPass. LPPassManager is
00012 // responsible for managing LoopPasses.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Analysis/LoopPass.h"
00017 #include "llvm/IR/IRPrintingPasses.h"
00018 #include "llvm/Support/Debug.h"
00019 #include "llvm/Support/Timer.h"
00020 using namespace llvm;
00021 
00022 namespace {
00023 
00024 /// PrintLoopPass - Print a Function corresponding to a Loop.
00025 ///
00026 class PrintLoopPass : public LoopPass {
00027 private:
00028   std::string Banner;
00029   raw_ostream &Out;       // raw_ostream to print on.
00030 
00031 public:
00032   static char ID;
00033   PrintLoopPass(const std::string &B, raw_ostream &o)
00034       : LoopPass(ID), Banner(B), Out(o) {}
00035 
00036   void getAnalysisUsage(AnalysisUsage &AU) const override {
00037     AU.setPreservesAll();
00038   }
00039 
00040   bool runOnLoop(Loop *L, LPPassManager &) override {
00041     Out << Banner;
00042     for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
00043          b != be;
00044          ++b) {
00045       (*b)->print(Out);
00046     }
00047     return false;
00048   }
00049 };
00050 
00051 char PrintLoopPass::ID = 0;
00052 }
00053 
00054 //===----------------------------------------------------------------------===//
00055 // LPPassManager
00056 //
00057 
00058 char LPPassManager::ID = 0;
00059 
00060 LPPassManager::LPPassManager()
00061   : FunctionPass(ID), PMDataManager() {
00062   skipThisLoop = false;
00063   redoThisLoop = false;
00064   LI = nullptr;
00065   CurrentLoop = nullptr;
00066 }
00067 
00068 /// Delete loop from the loop queue and loop hierarchy (LoopInfo).
00069 void LPPassManager::deleteLoopFromQueue(Loop *L) {
00070 
00071   LI->updateUnloop(L);
00072 
00073   // If L is current loop then skip rest of the passes and let
00074   // runOnFunction remove L from LQ. Otherwise, remove L from LQ now
00075   // and continue applying other passes on CurrentLoop.
00076   if (CurrentLoop == L)
00077     skipThisLoop = true;
00078 
00079   delete L;
00080 
00081   if (skipThisLoop)
00082     return;
00083 
00084   for (std::deque<Loop *>::iterator I = LQ.begin(),
00085          E = LQ.end(); I != E; ++I) {
00086     if (*I == L) {
00087       LQ.erase(I);
00088       break;
00089     }
00090   }
00091 }
00092 
00093 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).
00094 void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) {
00095 
00096   assert (CurrentLoop != L && "Cannot insert CurrentLoop");
00097 
00098   // Insert into loop nest
00099   if (ParentLoop)
00100     ParentLoop->addChildLoop(L);
00101   else
00102     LI->addTopLevelLoop(L);
00103 
00104   insertLoopIntoQueue(L);
00105 }
00106 
00107 void LPPassManager::insertLoopIntoQueue(Loop *L) {
00108   // Insert L into loop queue
00109   if (L == CurrentLoop)
00110     redoLoop(L);
00111   else if (!L->getParentLoop())
00112     // This is top level loop.
00113     LQ.push_front(L);
00114   else {
00115     // Insert L after the parent loop.
00116     for (std::deque<Loop *>::iterator I = LQ.begin(),
00117            E = LQ.end(); I != E; ++I) {
00118       if (*I == L->getParentLoop()) {
00119         // deque does not support insert after.
00120         ++I;
00121         LQ.insert(I, 1, L);
00122         break;
00123       }
00124     }
00125   }
00126 }
00127 
00128 // Reoptimize this loop. LPPassManager will re-insert this loop into the
00129 // queue. This allows LoopPass to change loop nest for the loop. This
00130 // utility may send LPPassManager into infinite loops so use caution.
00131 void LPPassManager::redoLoop(Loop *L) {
00132   assert (CurrentLoop == L && "Can redo only CurrentLoop");
00133   redoThisLoop = true;
00134 }
00135 
00136 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
00137 /// all loop passes.
00138 void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
00139                                                   BasicBlock *To, Loop *L) {
00140   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00141     LoopPass *LP = getContainedPass(Index);
00142     LP->cloneBasicBlockAnalysis(From, To, L);
00143   }
00144 }
00145 
00146 /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
00147 void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
00148   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
00149     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;
00150          ++BI) {
00151       Instruction &I = *BI;
00152       deleteSimpleAnalysisValue(&I, L);
00153     }
00154   }
00155   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00156     LoopPass *LP = getContainedPass(Index);
00157     LP->deleteAnalysisValue(V, L);
00158   }
00159 }
00160 
00161 
00162 // Recurse through all subloops and all loops  into LQ.
00163 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
00164   LQ.push_back(L);
00165   for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I)
00166     addLoopIntoQueue(*I, LQ);
00167 }
00168 
00169 /// Pass Manager itself does not invalidate any analysis info.
00170 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
00171   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
00172   // become part of LPPassManager.
00173   Info.addRequired<LoopInfo>();
00174   Info.setPreservesAll();
00175 }
00176 
00177 /// run - Execute all of the passes scheduled for execution.  Keep track of
00178 /// whether any of the passes modifies the function, and if so, return true.
00179 bool LPPassManager::runOnFunction(Function &F) {
00180   LI = &getAnalysis<LoopInfo>();
00181   bool Changed = false;
00182 
00183   // Collect inherited analysis from Module level pass manager.
00184   populateInheritedAnalysis(TPM->activeStack);
00185 
00186   // Populate the loop queue in reverse program order. There is no clear need to
00187   // process sibling loops in either forward or reverse order. There may be some
00188   // advantage in deleting uses in a later loop before optimizing the
00189   // definitions in an earlier loop. If we find a clear reason to process in
00190   // forward order, then a forward variant of LoopPassManager should be created.
00191   //
00192   // Note that LoopInfo::iterator visits loops in reverse program
00193   // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
00194   // reverses the order a third time by popping from the back.
00195   for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I)
00196     addLoopIntoQueue(*I, LQ);
00197 
00198   if (LQ.empty()) // No loops, skip calling finalizers
00199     return false;
00200 
00201   // Initialization
00202   for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
00203        I != E; ++I) {
00204     Loop *L = *I;
00205     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00206       LoopPass *P = getContainedPass(Index);
00207       Changed |= P->doInitialization(L, *this);
00208     }
00209   }
00210 
00211   // Walk Loops
00212   while (!LQ.empty()) {
00213 
00214     CurrentLoop  = LQ.back();
00215     skipThisLoop = false;
00216     redoThisLoop = false;
00217 
00218     // Run all passes on the current Loop.
00219     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00220       LoopPass *P = getContainedPass(Index);
00221 
00222       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
00223                    CurrentLoop->getHeader()->getName());
00224       dumpRequiredSet(P);
00225 
00226       initializeAnalysisImpl(P);
00227 
00228       {
00229         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
00230         TimeRegion PassTimer(getPassTimer(P));
00231 
00232         Changed |= P->runOnLoop(CurrentLoop, *this);
00233       }
00234 
00235       if (Changed)
00236         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
00237                      skipThisLoop ? "<deleted>" :
00238                                     CurrentLoop->getHeader()->getName());
00239       dumpPreservedSet(P);
00240 
00241       if (!skipThisLoop) {
00242         // Manually check that this loop is still healthy. This is done
00243         // instead of relying on LoopInfo::verifyLoop since LoopInfo
00244         // is a function pass and it's really expensive to verify every
00245         // loop in the function every time. That level of checking can be
00246         // enabled with the -verify-loop-info option.
00247         {
00248           TimeRegion PassTimer(getPassTimer(LI));
00249           CurrentLoop->verifyLoop();
00250         }
00251 
00252         // Then call the regular verifyAnalysis functions.
00253         verifyPreservedAnalysis(P);
00254       }
00255 
00256       removeNotPreservedAnalysis(P);
00257       recordAvailableAnalysis(P);
00258       removeDeadPasses(P,
00259                        skipThisLoop ? "<deleted>" :
00260                                       CurrentLoop->getHeader()->getName(),
00261                        ON_LOOP_MSG);
00262 
00263       if (skipThisLoop)
00264         // Do not run other passes on this loop.
00265         break;
00266     }
00267 
00268     // If the loop was deleted, release all the loop passes. This frees up
00269     // some memory, and avoids trouble with the pass manager trying to call
00270     // verifyAnalysis on them.
00271     if (skipThisLoop)
00272       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00273         Pass *P = getContainedPass(Index);
00274         freePass(P, "<deleted>", ON_LOOP_MSG);
00275       }
00276 
00277     // Pop the loop from queue after running all passes.
00278     LQ.pop_back();
00279 
00280     if (redoThisLoop)
00281       LQ.push_back(CurrentLoop);
00282   }
00283 
00284   // Finalization
00285   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00286     LoopPass *P = getContainedPass(Index);
00287     Changed |= P->doFinalization();
00288   }
00289 
00290   return Changed;
00291 }
00292 
00293 /// Print passes managed by this manager
00294 void LPPassManager::dumpPassStructure(unsigned Offset) {
00295   errs().indent(Offset*2) << "Loop Pass Manager\n";
00296   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00297     Pass *P = getContainedPass(Index);
00298     P->dumpPassStructure(Offset + 1);
00299     dumpLastUses(P, Offset+1);
00300   }
00301 }
00302 
00303 
00304 //===----------------------------------------------------------------------===//
00305 // LoopPass
00306 
00307 Pass *LoopPass::createPrinterPass(raw_ostream &O,
00308                                   const std::string &Banner) const {
00309   return new PrintLoopPass(Banner, O);
00310 }
00311 
00312 // Check if this pass is suitable for the current LPPassManager, if
00313 // available. This pass P is not suitable for a LPPassManager if P
00314 // is not preserving higher level analysis info used by other
00315 // LPPassManager passes. In such case, pop LPPassManager from the
00316 // stack. This will force assignPassManager() to create new
00317 // LPPassManger as expected.
00318 void LoopPass::preparePassManager(PMStack &PMS) {
00319 
00320   // Find LPPassManager
00321   while (!PMS.empty() &&
00322          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
00323     PMS.pop();
00324 
00325   // If this pass is destroying high level information that is used
00326   // by other passes that are managed by LPM then do not insert
00327   // this pass in current LPM. Use new LPPassManager.
00328   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
00329       !PMS.top()->preserveHigherLevelAnalysis(this))
00330     PMS.pop();
00331 }
00332 
00333 /// Assign pass manager to manage this pass.
00334 void LoopPass::assignPassManager(PMStack &PMS,
00335                                  PassManagerType PreferredType) {
00336   // Find LPPassManager
00337   while (!PMS.empty() &&
00338          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
00339     PMS.pop();
00340 
00341   LPPassManager *LPPM;
00342   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
00343     LPPM = (LPPassManager*)PMS.top();
00344   else {
00345     // Create new Loop Pass Manager if it does not exist.
00346     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
00347     PMDataManager *PMD = PMS.top();
00348 
00349     // [1] Create new Loop Pass Manager
00350     LPPM = new LPPassManager();
00351     LPPM->populateInheritedAnalysis(PMS);
00352 
00353     // [2] Set up new manager's top level manager
00354     PMTopLevelManager *TPM = PMD->getTopLevelManager();
00355     TPM->addIndirectPassManager(LPPM);
00356 
00357     // [3] Assign manager to manage this new manager. This may create
00358     // and push new managers into PMS
00359     Pass *P = LPPM->getAsPass();
00360     TPM->schedulePass(P);
00361 
00362     // [4] Push new manager into PMS
00363     PMS.push(LPPM);
00364   }
00365 
00366   LPPM->add(this);
00367 }
00368 
00369 // Containing function has Attribute::OptimizeNone and transformation
00370 // passes should skip it.
00371 bool LoopPass::skipOptnoneFunction(const Loop *L) const {
00372   const Function *F = L->getHeader()->getParent();
00373   if (F && F->hasFnAttribute(Attribute::OptimizeNone)) {
00374     // FIXME: Report this to dbgs() only once per function.
00375     DEBUG(dbgs() << "Skipping pass '" << getPassName()
00376           << "' in function " << F->getName() << "\n");
00377     // FIXME: Delete loop from pass manager's queue?
00378     return true;
00379   }
00380   return false;
00381 }