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