llvm/lib/Analysis/LoopPass.cpp

   1 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements LoopPass and LPPassManager. All loop optimization
  10 // and transformation passes are derived from LoopPass. LPPassManager is
  11 // responsible for managing LoopPasses.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/LoopPass.h"
  16 #include "llvm/Analysis/LoopAnalysisManager.h"
  17 #include "llvm/IR/Dominators.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "llvm/IR/OptBisect.h"
  20 #include "llvm/IR/PassManager.h"
  21 #include "llvm/IR/PassTimingInfo.h"
  22 #include "llvm/IR/PrintPasses.h"
  23 #include "llvm/IR/StructuralHash.h"
  24 #include "llvm/InitializePasses.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/TimeProfiler.h"
  27 #include "llvm/Support/Timer.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 using namespace llvm;
  30
  31 #define DEBUG_TYPE "loop-pass-manager"
  32
  33 namespace {
  34
  35 /// PrintLoopPass - Print a Function corresponding to a Loop.
  36 ///
  37 class PrintLoopPassWrapper : public LoopPass {
  38   raw_ostream &OS;
  39   std::string Banner;
  40
  41 public:
  42   static char ID;
  43   PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}
  44   PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
  45       : LoopPass(ID), OS(OS), Banner(Banner) {}
  46
  47   void getAnalysisUsage(AnalysisUsage &AU) const override {
  48     AU.setPreservesAll();
  49   }
  50
  51   bool runOnLoop(Loop *L, LPPassManager &) override {
  52     auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; });
  53     if (BBI != L->blocks().end() &&
  54         isFunctionInPrintList((*BBI)->getParent()->getName())) {
  55       printLoop(*L, OS, Banner);
  56     }
  57     return false;
  58   }
  59
  60   StringRef getPassName() const override { return "Print Loop IR"; }
  61 };
  62
  63 char PrintLoopPassWrapper::ID = 0;
  64 }
  65
  66 //===----------------------------------------------------------------------===//
  67 // LPPassManager
  68 //
  69
  70 char LPPassManager::ID = 0;
  71
  72 LPPassManager::LPPassManager()
  73   : FunctionPass(ID), PMDataManager() {
  74   LI = nullptr;
  75   CurrentLoop = nullptr;
  76 }
  77
  78 // Insert loop into loop nest (LoopInfo) and loop queue (LQ).
  79 void LPPassManager::addLoop(Loop &L) {
  80   if (L.isOutermost()) {
  81     // This is the top level loop.
  82     LQ.push_front(&L);
  83     return;
  84   }
  85
  86   // Insert L into the loop queue after the parent loop.
  87   for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
  88     if (*I == L.getParentLoop()) {
  89       // deque does not support insert after.
  90       ++I;
  91       LQ.insert(I, 1, &L);
  92       return;
  93     }
  94   }
  95 }
  96
  97 // Recurse through all subloops and all loops  into LQ.
  98 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
  99   LQ.push_back(L);
 100   for (Loop *I : reverse(*L))
 101     addLoopIntoQueue(I, LQ);
 102 }
 103
 104 /// Pass Manager itself does not invalidate any analysis info.
 105 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
 106   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
 107   // become part of LPPassManager.
 108   Info.addRequired<LoopInfoWrapperPass>();
 109   Info.addRequired<DominatorTreeWrapperPass>();
 110   Info.setPreservesAll();
 111 }
 112
 113 void LPPassManager::markLoopAsDeleted(Loop &L) {
 114   assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&
 115          "Must not delete loop outside the current loop tree!");
 116   // If this loop appears elsewhere within the queue, we also need to remove it
 117   // there. However, we have to be careful to not remove the back of the queue
 118   // as that is assumed to match the current loop.
 119   assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
 120   llvm::erase_value(LQ, &L);
 121
 122   if (&L == CurrentLoop) {
 123     CurrentLoopDeleted = true;
 124     // Add this loop back onto the back of the queue to preserve our invariants.
 125     LQ.push_back(&L);
 126   }
 127 }
 128
 129 /// run - Execute all of the passes scheduled for execution.  Keep track of
 130 /// whether any of the passes modifies the function, and if so, return true.
 131 bool LPPassManager::runOnFunction(Function &F) {
 132   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
 133   LI = &LIWP.getLoopInfo();
 134   Module &M = *F.getParent();
 135 #if 0
 136   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 137 #endif
 138   bool Changed = false;
 139
 140   // Collect inherited analysis from Module level pass manager.
 141   populateInheritedAnalysis(TPM->activeStack);
 142
 143   // Populate the loop queue in reverse program order. There is no clear need to
 144   // process sibling loops in either forward or reverse order. There may be some
 145   // advantage in deleting uses in a later loop before optimizing the
 146   // definitions in an earlier loop. If we find a clear reason to process in
 147   // forward order, then a forward variant of LoopPassManager should be created.
 148   //
 149   // Note that LoopInfo::iterator visits loops in reverse program
 150   // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
 151   // reverses the order a third time by popping from the back.
 152   for (Loop *L : reverse(*LI))
 153     addLoopIntoQueue(L, LQ);
 154
 155   if (LQ.empty()) // No loops, skip calling finalizers
 156     return false;
 157
 158   // Initialization
 159   for (Loop *L : LQ) {
 160     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 161       LoopPass *P = getContainedPass(Index);
 162       Changed |= P->doInitialization(L, *this);
 163     }
 164   }
 165
 166   // Walk Loops
 167   unsigned InstrCount, FunctionSize = 0;
 168   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
 169   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
 170   // Collect the initial size of the module and the function we're looking at.
 171   if (EmitICRemark) {
 172     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
 173     FunctionSize = F.getInstructionCount();
 174   }
 175   while (!LQ.empty()) {
 176     CurrentLoopDeleted = false;
 177     CurrentLoop = LQ.back();
 178
 179     // Run all passes on the current Loop.
 180     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 181       LoopPass *P = getContainedPass(Index);
 182
 183       llvm::TimeTraceScope LoopPassScope("RunLoopPass", P->getPassName());
 184
 185       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
 186                    CurrentLoop->getHeader()->getName());
 187       dumpRequiredSet(P);
 188
 189       initializeAnalysisImpl(P);
 190
 191       bool LocalChanged = false;
 192       {
 193         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
 194         TimeRegion PassTimer(getPassTimer(P));
 195 #ifdef EXPENSIVE_CHECKS
 196         uint64_t RefHash = StructuralHash(F);
 197 #endif
 198         LocalChanged = P->runOnLoop(CurrentLoop, *this);
 199
 200 #ifdef EXPENSIVE_CHECKS
 201         if (!LocalChanged && (RefHash != StructuralHash(F))) {
 202           llvm::errs() << "Pass modifies its input and doesn't report it: "
 203                        << P->getPassName() << "\n";
 204           llvm_unreachable("Pass modifies its input and doesn't report it");
 205         }
 206 #endif
 207
 208         Changed |= LocalChanged;
 209         if (EmitICRemark) {
 210           unsigned NewSize = F.getInstructionCount();
 211           // Update the size of the function, emit a remark, and update the
 212           // size of the module.
 213           if (NewSize != FunctionSize) {
 214             int64_t Delta = static_cast<int64_t>(NewSize) -
 215                             static_cast<int64_t>(FunctionSize);
 216             emitInstrCountChangedRemark(P, M, Delta, InstrCount,
 217                                         FunctionToInstrCount, &F);
 218             InstrCount = static_cast<int64_t>(InstrCount) + Delta;
 219             FunctionSize = NewSize;
 220           }
 221         }
 222       }
 223
 224       if (LocalChanged)
 225         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
 226                      CurrentLoopDeleted ? "<deleted loop>"
 227                                         : CurrentLoop->getName());
 228       dumpPreservedSet(P);
 229
 230       if (!CurrentLoopDeleted) {
 231         // Manually check that this loop is still healthy. This is done
 232         // instead of relying on LoopInfo::verifyLoop since LoopInfo
 233         // is a function pass and it's really expensive to verify every
 234         // loop in the function every time. That level of checking can be
 235         // enabled with the -verify-loop-info option.
 236         {
 237           TimeRegion PassTimer(getPassTimer(&LIWP));
 238           CurrentLoop->verifyLoop();
 239         }
 240         // Here we apply same reasoning as in the above case. Only difference
 241         // is that LPPassManager might run passes which do not require LCSSA
 242         // form (LoopPassPrinter for example). We should skip verification for
 243         // such passes.
 244         // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
 245         // verification!
 246 #if 0
 247         if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
 248           assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
 249 #endif
 250
 251         // Then call the regular verifyAnalysis functions.
 252         verifyPreservedAnalysis(P);
 253
 254         F.getContext().yield();
 255       }
 256
 257       if (LocalChanged)
 258         removeNotPreservedAnalysis(P);
 259       recordAvailableAnalysis(P);
 260       removeDeadPasses(P,
 261                        CurrentLoopDeleted ? "<deleted>"
 262                                           : CurrentLoop->getHeader()->getName(),
 263                        ON_LOOP_MSG);
 264
 265       if (CurrentLoopDeleted)
 266         // Do not run other passes on this loop.
 267         break;
 268     }
 269
 270     // If the loop was deleted, release all the loop passes. This frees up
 271     // some memory, and avoids trouble with the pass manager trying to call
 272     // verifyAnalysis on them.
 273     if (CurrentLoopDeleted) {
 274       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 275         Pass *P = getContainedPass(Index);
 276         freePass(P, "<deleted>", ON_LOOP_MSG);
 277       }
 278     }
 279
 280     // Pop the loop from queue after running all passes.
 281     LQ.pop_back();
 282   }
 283
 284   // Finalization
 285   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 286     LoopPass *P = getContainedPass(Index);
 287     Changed |= P->doFinalization();
 288   }
 289
 290   return Changed;
 291 }
 292
 293 /// Print passes managed by this manager
 294 void LPPassManager::dumpPassStructure(unsigned Offset) {
 295   errs().indent(Offset*2) << "Loop Pass Manager\n";
 296   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 297     Pass *P = getContainedPass(Index);
 298     P->dumpPassStructure(Offset + 1);
 299     dumpLastUses(P, Offset+1);
 300   }
 301 }
 302
 303
 304 //===----------------------------------------------------------------------===//
 305 // LoopPass
 306
 307 Pass *LoopPass::createPrinterPass(raw_ostream &O,
 308                                   const std::string &Banner) const {
 309   return new PrintLoopPassWrapper(O, Banner);
 310 }
 311
 312 // Check if this pass is suitable for the current LPPassManager, if
 313 // available. This pass P is not suitable for a LPPassManager if P
 314 // is not preserving higher level analysis info used by other
 315 // LPPassManager passes. In such case, pop LPPassManager from the
 316 // stack. This will force assignPassManager() to create new
 317 // LPPassManger as expected.
 318 void LoopPass::preparePassManager(PMStack &PMS) {
 319
 320   // Find LPPassManager
 321   while (!PMS.empty() &&
 322          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 323     PMS.pop();
 324
 325   // If this pass is destroying high level information that is used
 326   // by other passes that are managed by LPM then do not insert
 327   // this pass in current LPM. Use new LPPassManager.
 328   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
 329       !PMS.top()->preserveHigherLevelAnalysis(this))
 330     PMS.pop();
 331 }
 332
 333 /// Assign pass manager to manage this pass.
 334 void LoopPass::assignPassManager(PMStack &PMS,
 335                                  PassManagerType PreferredType) {
 336   // Find LPPassManager
 337   while (!PMS.empty() &&
 338          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 339     PMS.pop();
 340
 341   LPPassManager *LPPM;
 342   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
 343     LPPM = (LPPassManager*)PMS.top();
 344   else {
 345     // Create new Loop Pass Manager if it does not exist.
 346     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
 347     PMDataManager *PMD = PMS.top();
 348
 349     // [1] Create new Loop Pass Manager
 350     LPPM = new LPPassManager();
 351     LPPM->populateInheritedAnalysis(PMS);
 352
 353     // [2] Set up new manager's top level manager
 354     PMTopLevelManager *TPM = PMD->getTopLevelManager();
 355     TPM->addIndirectPassManager(LPPM);
 356
 357     // [3] Assign manager to manage this new manager. This may create
 358     // and push new managers into PMS
 359     Pass *P = LPPM->getAsPass();
 360     TPM->schedulePass(P);
 361
 362     // [4] Push new manager into PMS
 363     PMS.push(LPPM);
 364   }
 365
 366   LPPM->add(this);
 367 }
 368
 369 static std::string getDescription(const Loop &L) {
 370   return "loop";
 371 }
 372
 373 bool LoopPass::skipLoop(const Loop *L) const {
 374   const Function *F = L->getHeader()->getParent();
 375   if (!F)
 376     return false;
 377   // Check the opt bisect limit.
 378   OptPassGate &Gate = F->getContext().getOptPassGate();
 379   if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(*L)))
 380     return true;
 381   // Check for the OptimizeNone attribute.
 382   if (F->hasOptNone()) {
 383     // FIXME: Report this to dbgs() only once per function.
 384     LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
 385                       << F->getName() << "\n");
 386     // FIXME: Delete loop from pass manager's queue?
 387     return true;
 388   }
 389   return false;
 390 }
 391
 392 LCSSAVerificationPass::LCSSAVerificationPass() : FunctionPass(ID) {
 393   initializeLCSSAVerificationPassPass(*PassRegistry::getPassRegistry());
 394 }
 395
 396 char LCSSAVerificationPass::ID = 0;
 397 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
 398                 false, false)