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