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