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/IRPrintingPasses.h"
  19 #include "llvm/IR/LLVMContext.h"
  20 #include "llvm/IR/OptBisect.h"
  21 #include "llvm/IR/PassManager.h"
  22 #include "llvm/IR/PassTimingInfo.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 this loop appears elsewhere within the queue, we also need to remove it
 146   // there. However, we have to be careful to not remove the back of the queue
 147   // as that is assumed to match the current loop.
 148   assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
 149   LQ.erase(std::remove(LQ.begin(), LQ.end(), &L), LQ.end());
 150
 151   if (&L == CurrentLoop) {
 152     CurrentLoopDeleted = true;
 153     // Add this loop back onto the back of the queue to preserve our invariants.
 154     LQ.push_back(&L);
 155   }
 156 }
 157
 158 /// run - Execute all of the passes scheduled for execution.  Keep track of
 159 /// whether any of the passes modifies the function, and if so, return true.
 160 bool LPPassManager::runOnFunction(Function &F) {
 161   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
 162   LI = &LIWP.getLoopInfo();
 163   Module &M = *F.getParent();
 164 #if 0
 165   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 166 #endif
 167   bool Changed = false;
 168
 169   // Collect inherited analysis from Module level pass manager.
 170   populateInheritedAnalysis(TPM->activeStack);
 171
 172   // Populate the loop queue in reverse program order. There is no clear need to
 173   // process sibling loops in either forward or reverse order. There may be some
 174   // advantage in deleting uses in a later loop before optimizing the
 175   // definitions in an earlier loop. If we find a clear reason to process in
 176   // forward order, then a forward variant of LoopPassManager should be created.
 177   //
 178   // Note that LoopInfo::iterator visits loops in reverse program
 179   // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
 180   // reverses the order a third time by popping from the back.
 181   for (Loop *L : reverse(*LI))
 182     addLoopIntoQueue(L, LQ);
 183
 184   if (LQ.empty()) // No loops, skip calling finalizers
 185     return false;
 186
 187   // Initialization
 188   for (Loop *L : LQ) {
 189     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 190       LoopPass *P = getContainedPass(Index);
 191       Changed |= P->doInitialization(L, *this);
 192     }
 193   }
 194
 195   // Walk Loops
 196   unsigned InstrCount, FunctionSize = 0;
 197   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
 198   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
 199   // Collect the initial size of the module and the function we're looking at.
 200   if (EmitICRemark) {
 201     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
 202     FunctionSize = F.getInstructionCount();
 203   }
 204   while (!LQ.empty()) {
 205     CurrentLoopDeleted = false;
 206     CurrentLoop = LQ.back();
 207
 208     // Run all passes on the current Loop.
 209     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 210       LoopPass *P = getContainedPass(Index);
 211
 212       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
 213                    CurrentLoop->getHeader()->getName());
 214       dumpRequiredSet(P);
 215
 216       initializeAnalysisImpl(P);
 217
 218       bool LocalChanged = false;
 219       {
 220         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
 221         TimeRegion PassTimer(getPassTimer(P));
 222         LocalChanged = P->runOnLoop(CurrentLoop, *this);
 223         Changed |= LocalChanged;
 224         if (EmitICRemark) {
 225           unsigned NewSize = F.getInstructionCount();
 226           // Update the size of the function, emit a remark, and update the
 227           // size of the module.
 228           if (NewSize != FunctionSize) {
 229             int64_t Delta = static_cast<int64_t>(NewSize) -
 230                             static_cast<int64_t>(FunctionSize);
 231             emitInstrCountChangedRemark(P, M, Delta, InstrCount,
 232                                         FunctionToInstrCount, &F);
 233             InstrCount = static_cast<int64_t>(InstrCount) + Delta;
 234             FunctionSize = NewSize;
 235           }
 236         }
 237       }
 238
 239       if (LocalChanged)
 240         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
 241                      CurrentLoopDeleted ? "<deleted loop>"
 242                                         : CurrentLoop->getName());
 243       dumpPreservedSet(P);
 244
 245       if (CurrentLoopDeleted) {
 246         // Notify passes that the loop is being deleted.
 247         deleteSimpleAnalysisLoop(CurrentLoop);
 248       } else {
 249         // Manually check that this loop is still healthy. This is done
 250         // instead of relying on LoopInfo::verifyLoop since LoopInfo
 251         // is a function pass and it's really expensive to verify every
 252         // loop in the function every time. That level of checking can be
 253         // enabled with the -verify-loop-info option.
 254         {
 255           TimeRegion PassTimer(getPassTimer(&LIWP));
 256           CurrentLoop->verifyLoop();
 257         }
 258         // Here we apply same reasoning as in the above case. Only difference
 259         // is that LPPassManager might run passes which do not require LCSSA
 260         // form (LoopPassPrinter for example). We should skip verification for
 261         // such passes.
 262         // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
 263         // verification!
 264 #if 0
 265         if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
 266           assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
 267 #endif
 268
 269         // Then call the regular verifyAnalysis functions.
 270         verifyPreservedAnalysis(P);
 271
 272         F.getContext().yield();
 273       }
 274
 275       removeNotPreservedAnalysis(P);
 276       recordAvailableAnalysis(P);
 277       removeDeadPasses(P,
 278                        CurrentLoopDeleted ? "<deleted>"
 279                                           : CurrentLoop->getHeader()->getName(),
 280                        ON_LOOP_MSG);
 281
 282       if (CurrentLoopDeleted)
 283         // Do not run other passes on this loop.
 284         break;
 285     }
 286
 287     // If the loop was deleted, release all the loop passes. This frees up
 288     // some memory, and avoids trouble with the pass manager trying to call
 289     // verifyAnalysis on them.
 290     if (CurrentLoopDeleted) {
 291       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 292         Pass *P = getContainedPass(Index);
 293         freePass(P, "<deleted>", ON_LOOP_MSG);
 294       }
 295     }
 296
 297     // Pop the loop from queue after running all passes.
 298     LQ.pop_back();
 299   }
 300
 301   // Finalization
 302   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 303     LoopPass *P = getContainedPass(Index);
 304     Changed |= P->doFinalization();
 305   }
 306
 307   return Changed;
 308 }
 309
 310 /// Print passes managed by this manager
 311 void LPPassManager::dumpPassStructure(unsigned Offset) {
 312   errs().indent(Offset*2) << "Loop Pass Manager\n";
 313   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 314     Pass *P = getContainedPass(Index);
 315     P->dumpPassStructure(Offset + 1);
 316     dumpLastUses(P, Offset+1);
 317   }
 318 }
 319
 320
 321 //===----------------------------------------------------------------------===//
 322 // LoopPass
 323
 324 Pass *LoopPass::createPrinterPass(raw_ostream &O,
 325                                   const std::string &Banner) const {
 326   return new PrintLoopPassWrapper(O, Banner);
 327 }
 328
 329 // Check if this pass is suitable for the current LPPassManager, if
 330 // available. This pass P is not suitable for a LPPassManager if P
 331 // is not preserving higher level analysis info used by other
 332 // LPPassManager passes. In such case, pop LPPassManager from the
 333 // stack. This will force assignPassManager() to create new
 334 // LPPassManger as expected.
 335 void LoopPass::preparePassManager(PMStack &PMS) {
 336
 337   // Find LPPassManager
 338   while (!PMS.empty() &&
 339          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 340     PMS.pop();
 341
 342   // If this pass is destroying high level information that is used
 343   // by other passes that are managed by LPM then do not insert
 344   // this pass in current LPM. Use new LPPassManager.
 345   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
 346       !PMS.top()->preserveHigherLevelAnalysis(this))
 347     PMS.pop();
 348 }
 349
 350 /// Assign pass manager to manage this pass.
 351 void LoopPass::assignPassManager(PMStack &PMS,
 352                                  PassManagerType PreferredType) {
 353   // Find LPPassManager
 354   while (!PMS.empty() &&
 355          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 356     PMS.pop();
 357
 358   LPPassManager *LPPM;
 359   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
 360     LPPM = (LPPassManager*)PMS.top();
 361   else {
 362     // Create new Loop Pass Manager if it does not exist.
 363     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
 364     PMDataManager *PMD = PMS.top();
 365
 366     // [1] Create new Loop Pass Manager
 367     LPPM = new LPPassManager();
 368     LPPM->populateInheritedAnalysis(PMS);
 369
 370     // [2] Set up new manager's top level manager
 371     PMTopLevelManager *TPM = PMD->getTopLevelManager();
 372     TPM->addIndirectPassManager(LPPM);
 373
 374     // [3] Assign manager to manage this new manager. This may create
 375     // and push new managers into PMS
 376     Pass *P = LPPM->getAsPass();
 377     TPM->schedulePass(P);
 378
 379     // [4] Push new manager into PMS
 380     PMS.push(LPPM);
 381   }
 382
 383   LPPM->add(this);
 384 }
 385
 386 static std::string getDescription(const Loop &L) {
 387   return "loop";
 388 }
 389
 390 bool LoopPass::skipLoop(const Loop *L) const {
 391   const Function *F = L->getHeader()->getParent();
 392   if (!F)
 393     return false;
 394   // Check the opt bisect limit.
 395   OptPassGate &Gate = F->getContext().getOptPassGate();
 396   if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(*L)))
 397     return true;
 398   // Check for the OptimizeNone attribute.
 399   if (F->hasOptNone()) {
 400     // FIXME: Report this to dbgs() only once per function.
 401     LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
 402                       << F->getName() << "\n");
 403     // FIXME: Delete loop from pass manager's queue?
 404     return true;
 405   }
 406   return false;
 407 }
 408
 409 char LCSSAVerificationPass::ID = 0;
 410 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
 411                 false, false)