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