contrib/llvm/lib/Analysis/LoopPass.cpp

   1 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/LoopPassManager.h"
  18 #include "llvm/IR/Dominators.h"
  19 #include "llvm/IR/IRPrintingPasses.h"
  20 #include "llvm/IR/LLVMContext.h"
  21 #include "llvm/IR/OptBisect.h"
  22 #include "llvm/IR/PassManager.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/Timer.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 using namespace llvm;
  27
  28 #define DEBUG_TYPE "loop-pass-manager"
  29
  30 namespace {
  31
  32 /// PrintLoopPass - Print a Function corresponding to a Loop.
  33 ///
  34 class PrintLoopPassWrapper : public LoopPass {
  35   PrintLoopPass P;
  36
  37 public:
  38   static char ID;
  39   PrintLoopPassWrapper() : LoopPass(ID) {}
  40   PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
  41       : LoopPass(ID), P(OS, Banner) {}
  42
  43   void getAnalysisUsage(AnalysisUsage &AU) const override {
  44     AU.setPreservesAll();
  45   }
  46
  47   bool runOnLoop(Loop *L, LPPassManager &) override {
  48     auto BBI = find_if(L->blocks().begin(), L->blocks().end(),
  49                        [](BasicBlock *BB) { return BB; });
  50     if (BBI != L->blocks().end() &&
  51         isFunctionInPrintList((*BBI)->getParent()->getName())) {
  52       LoopAnalysisManager DummyLAM;
  53       P.run(*L, DummyLAM);
  54     }
  55     return false;
  56   }
  57 };
  58
  59 char PrintLoopPassWrapper::ID = 0;
  60 }
  61
  62 //===----------------------------------------------------------------------===//
  63 // LPPassManager
  64 //
  65
  66 char LPPassManager::ID = 0;
  67
  68 LPPassManager::LPPassManager()
  69   : FunctionPass(ID), PMDataManager() {
  70   LI = nullptr;
  71   CurrentLoop = nullptr;
  72 }
  73
  74 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).
  75 Loop &LPPassManager::addLoop(Loop *ParentLoop) {
  76   // Create a new loop. LI will take ownership.
  77   Loop *L = new Loop();
  78
  79   // Insert into the loop nest and the loop queue.
  80   if (!ParentLoop) {
  81     // This is the top level loop.
  82     LI->addTopLevelLoop(L);
  83     LQ.push_front(L);
  84     return *L;
  85   }
  86
  87   ParentLoop->addChildLoop(L);
  88   // Insert L into the loop queue after the parent loop.
  89   for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
  90     if (*I == L->getParentLoop()) {
  91       // deque does not support insert after.
  92       ++I;
  93       LQ.insert(I, 1, L);
  94       break;
  95     }
  96   }
  97   return *L;
  98 }
  99
 100 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
 101 /// all loop passes.
 102 void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
 103                                                   BasicBlock *To, Loop *L) {
 104   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 105     LoopPass *LP = getContainedPass(Index);
 106     LP->cloneBasicBlockAnalysis(From, To, L);
 107   }
 108 }
 109
 110 /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
 111 void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
 112   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
 113     for (Instruction &I : *BB) {
 114       deleteSimpleAnalysisValue(&I, L);
 115     }
 116   }
 117   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 118     LoopPass *LP = getContainedPass(Index);
 119     LP->deleteAnalysisValue(V, L);
 120   }
 121 }
 122
 123 /// Invoke deleteAnalysisLoop hook for all passes.
 124 void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
 125   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 126     LoopPass *LP = getContainedPass(Index);
 127     LP->deleteAnalysisLoop(L);
 128   }
 129 }
 130
 131
 132 // Recurse through all subloops and all loops  into LQ.
 133 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
 134   LQ.push_back(L);
 135   for (Loop *I : reverse(*L))
 136     addLoopIntoQueue(I, LQ);
 137 }
 138
 139 /// Pass Manager itself does not invalidate any analysis info.
 140 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
 141   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
 142   // become part of LPPassManager.
 143   Info.addRequired<LoopInfoWrapperPass>();
 144   Info.addRequired<DominatorTreeWrapperPass>();
 145   Info.setPreservesAll();
 146 }
 147
 148 /// run - Execute all of the passes scheduled for execution.  Keep track of
 149 /// whether any of the passes modifies the function, and if so, return true.
 150 bool LPPassManager::runOnFunction(Function &F) {
 151   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
 152   LI = &LIWP.getLoopInfo();
 153   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 154   bool Changed = false;
 155
 156   // Collect inherited analysis from Module level pass manager.
 157   populateInheritedAnalysis(TPM->activeStack);
 158
 159   // Populate the loop queue in reverse program order. There is no clear need to
 160   // process sibling loops in either forward or reverse order. There may be some
 161   // advantage in deleting uses in a later loop before optimizing the
 162   // definitions in an earlier loop. If we find a clear reason to process in
 163   // forward order, then a forward variant of LoopPassManager should be created.
 164   //
 165   // Note that LoopInfo::iterator visits loops in reverse program
 166   // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
 167   // reverses the order a third time by popping from the back.
 168   for (Loop *L : reverse(*LI))
 169     addLoopIntoQueue(L, LQ);
 170
 171   if (LQ.empty()) // No loops, skip calling finalizers
 172     return false;
 173
 174   // Initialization
 175   for (Loop *L : LQ) {
 176     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 177       LoopPass *P = getContainedPass(Index);
 178       Changed |= P->doInitialization(L, *this);
 179     }
 180   }
 181
 182   // Walk Loops
 183   while (!LQ.empty()) {
 184     bool LoopWasDeleted = false;
 185     CurrentLoop = LQ.back();
 186
 187     // Run all passes on the current Loop.
 188     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 189       LoopPass *P = getContainedPass(Index);
 190
 191       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
 192                    CurrentLoop->getHeader()->getName());
 193       dumpRequiredSet(P);
 194
 195       initializeAnalysisImpl(P);
 196
 197       {
 198         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
 199         TimeRegion PassTimer(getPassTimer(P));
 200
 201         Changed |= P->runOnLoop(CurrentLoop, *this);
 202       }
 203       LoopWasDeleted = CurrentLoop->isInvalid();
 204
 205       if (Changed)
 206         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
 207                      LoopWasDeleted ? "<deleted>"
 208                                     : CurrentLoop->getHeader()->getName());
 209       dumpPreservedSet(P);
 210
 211       if (LoopWasDeleted) {
 212         // Notify passes that the loop is being deleted.
 213         deleteSimpleAnalysisLoop(CurrentLoop);
 214       } else {
 215         // Manually check that this loop is still healthy. This is done
 216         // instead of relying on LoopInfo::verifyLoop since LoopInfo
 217         // is a function pass and it's really expensive to verify every
 218         // loop in the function every time. That level of checking can be
 219         // enabled with the -verify-loop-info option.
 220         {
 221           TimeRegion PassTimer(getPassTimer(&LIWP));
 222           CurrentLoop->verifyLoop();
 223         }
 224         // Here we apply same reasoning as in the above case. Only difference
 225         // is that LPPassManager might run passes which do not require LCSSA
 226         // form (LoopPassPrinter for example). We should skip verification for
 227         // such passes.
 228         if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
 229           CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI);
 230
 231         // Then call the regular verifyAnalysis functions.
 232         verifyPreservedAnalysis(P);
 233
 234         F.getContext().yield();
 235       }
 236
 237       removeNotPreservedAnalysis(P);
 238       recordAvailableAnalysis(P);
 239       removeDeadPasses(P, LoopWasDeleted ? "<deleted>"
 240                                          : CurrentLoop->getHeader()->getName(),
 241                        ON_LOOP_MSG);
 242
 243       if (LoopWasDeleted)
 244         // Do not run other passes on this loop.
 245         break;
 246     }
 247
 248     // If the loop was deleted, release all the loop passes. This frees up
 249     // some memory, and avoids trouble with the pass manager trying to call
 250     // verifyAnalysis on them.
 251     if (LoopWasDeleted) {
 252       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 253         Pass *P = getContainedPass(Index);
 254         freePass(P, "<deleted>", ON_LOOP_MSG);
 255       }
 256     }
 257
 258     // Pop the loop from queue after running all passes.
 259     LQ.pop_back();
 260   }
 261
 262   // Finalization
 263   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 264     LoopPass *P = getContainedPass(Index);
 265     Changed |= P->doFinalization();
 266   }
 267
 268   return Changed;
 269 }
 270
 271 /// Print passes managed by this manager
 272 void LPPassManager::dumpPassStructure(unsigned Offset) {
 273   errs().indent(Offset*2) << "Loop Pass Manager\n";
 274   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 275     Pass *P = getContainedPass(Index);
 276     P->dumpPassStructure(Offset + 1);
 277     dumpLastUses(P, Offset+1);
 278   }
 279 }
 280
 281
 282 //===----------------------------------------------------------------------===//
 283 // LoopPass
 284
 285 Pass *LoopPass::createPrinterPass(raw_ostream &O,
 286                                   const std::string &Banner) const {
 287   return new PrintLoopPassWrapper(O, Banner);
 288 }
 289
 290 // Check if this pass is suitable for the current LPPassManager, if
 291 // available. This pass P is not suitable for a LPPassManager if P
 292 // is not preserving higher level analysis info used by other
 293 // LPPassManager passes. In such case, pop LPPassManager from the
 294 // stack. This will force assignPassManager() to create new
 295 // LPPassManger as expected.
 296 void LoopPass::preparePassManager(PMStack &PMS) {
 297
 298   // Find LPPassManager
 299   while (!PMS.empty() &&
 300          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 301     PMS.pop();
 302
 303   // If this pass is destroying high level information that is used
 304   // by other passes that are managed by LPM then do not insert
 305   // this pass in current LPM. Use new LPPassManager.
 306   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
 307       !PMS.top()->preserveHigherLevelAnalysis(this))
 308     PMS.pop();
 309 }
 310
 311 /// Assign pass manager to manage this pass.
 312 void LoopPass::assignPassManager(PMStack &PMS,
 313                                  PassManagerType PreferredType) {
 314   // Find LPPassManager
 315   while (!PMS.empty() &&
 316          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 317     PMS.pop();
 318
 319   LPPassManager *LPPM;
 320   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
 321     LPPM = (LPPassManager*)PMS.top();
 322   else {
 323     // Create new Loop Pass Manager if it does not exist.
 324     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
 325     PMDataManager *PMD = PMS.top();
 326
 327     // [1] Create new Loop Pass Manager
 328     LPPM = new LPPassManager();
 329     LPPM->populateInheritedAnalysis(PMS);
 330
 331     // [2] Set up new manager's top level manager
 332     PMTopLevelManager *TPM = PMD->getTopLevelManager();
 333     TPM->addIndirectPassManager(LPPM);
 334
 335     // [3] Assign manager to manage this new manager. This may create
 336     // and push new managers into PMS
 337     Pass *P = LPPM->getAsPass();
 338     TPM->schedulePass(P);
 339
 340     // [4] Push new manager into PMS
 341     PMS.push(LPPM);
 342   }
 343
 344   LPPM->add(this);
 345 }
 346
 347 bool LoopPass::skipLoop(const Loop *L) const {
 348   const Function *F = L->getHeader()->getParent();
 349   if (!F)
 350     return false;
 351   // Check the opt bisect limit.
 352   LLVMContext &Context = F->getContext();
 353   if (!Context.getOptBisect().shouldRunPass(this, *L))
 354     return true;
 355   // Check for the OptimizeNone attribute.
 356   if (F->hasFnAttribute(Attribute::OptimizeNone)) {
 357     // FIXME: Report this to dbgs() only once per function.
 358     DEBUG(dbgs() << "Skipping pass '" << getPassName()
 359           << "' in function " << F->getName() << "\n");
 360     // FIXME: Delete loop from pass manager's queue?
 361     return true;
 362   }
 363   return false;
 364 }
 365
 366 char LCSSAVerificationPass::ID = 0;
 367 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
 368                 false, false)
 369