1//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===// 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 7//===----------------------------------------------------------------------===// 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. 13//===----------------------------------------------------------------------===// 30#define DEBUG_TYPE "loop-pass-manager" 34/// PrintLoopPass - Print a Function corresponding to a Loop. 36classPrintLoopPassWrapper :
publicLoopPass {
43 PrintLoopPassWrapper(
raw_ostream &
OS,
const std::string &Banner)
52if (BBI != L->blocks().end() &&
62char PrintLoopPassWrapper::ID = 0;
65//===----------------------------------------------------------------------===// 76// Insert loop into loop nest (LoopInfo) and loop queue (LQ). 79// This is the top level loop. 84// Insert L into the loop queue after the parent loop. 85for (
autoI = LQ.begin(), E = LQ.end();
I != E; ++
I) {
86if (*
I == L.getParentLoop()) {
87// deque does not support insert after. 95// Recurse through all subloops and all loops into LQ. 102/// Pass Manager itself does not invalidate any analysis info. 104// LPPassManager needs LoopInfo. In the long term LoopInfo class will 105// become part of LPPassManager. 108Info.setPreservesAll();
113"Must not delete loop outside the current loop tree!");
114// If this loop appears elsewhere within the queue, we also need to remove it 115// there. However, we have to be careful to not remove the back of the queue 116// as that is assumed to match the current loop. 117assert(LQ.back() == CurrentLoop &&
"Loop queue back isn't the current loop!");
120if (&L == CurrentLoop) {
121 CurrentLoopDeleted =
true;
122// Add this loop back onto the back of the queue to preserve our invariants. 127/// run - Execute all of the passes scheduled for execution. Keep track of 128/// whether any of the passes modifies the function, and if so, return true. 130auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
131 LI = &LIWP.getLoopInfo();
134DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
138// Collect inherited analysis from Module level pass manager. 141// Populate the loop queue in reverse program order. There is no clear need to 142// process sibling loops in either forward or reverse order. There may be some 143// advantage in deleting uses in a later loop before optimizing the 144// definitions in an earlier loop. If we find a clear reason to process in 145// forward order, then a forward variant of LoopPassManager should be created. 147// Note that LoopInfo::iterator visits loops in reverse program 148// order. Here, reverse_iterator gives us a forward order, and the LoopQueue 149// reverses the order a third time by popping from the back. 153if (LQ.empty())
// No loops, skip calling finalizers 160 Changed |=
P->doInitialization(L, *
this);
167bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
168// Collect the initial size of the module and the function we're looking at. 171 FunctionSize =
F.getInstructionCount();
174 CurrentLoopDeleted =
false;
175 CurrentLoop = LQ.back();
177// Run all passes on the current Loop. 189bool LocalChanged =
false;
193#ifdef EXPENSIVE_CHECKS 196 LocalChanged =
P->runOnLoop(CurrentLoop, *
this);
198#ifdef EXPENSIVE_CHECKS 199if (!LocalChanged && (RefHash !=
P->structuralHash(
F))) {
200llvm::errs() <<
"Pass modifies its input and doesn't report it: " 201 <<
P->getPassName() <<
"\n";
206 Changed |= LocalChanged;
208unsigned NewSize =
F.getInstructionCount();
209// Update the size of the function, emit a remark, and update the 210// size of the module. 211if (NewSize != FunctionSize) {
212 int64_t Delta =
static_cast<int64_t
>(NewSize) -
213static_cast<int64_t
>(FunctionSize);
215 FunctionToInstrCount, &
F);
217 FunctionSize = NewSize;
224 CurrentLoopDeleted ?
"<deleted loop>" 228if (!CurrentLoopDeleted) {
229// Manually check that this loop is still healthy. This is done 230// instead of relying on LoopInfo::verifyLoop since LoopInfo 231// is a function pass and it's really expensive to verify every 232// loop in the function every time. That level of checking can be 233// enabled with the -verify-loop-info option. 238// Here we apply same reasoning as in the above case. Only difference 239// is that LPPassManager might run passes which do not require LCSSA 240// form (LoopPassPrinter for example). We should skip verification for 242// FIXME: Loop-sink currently break LCSSA. Fix it and reenable the 249// Then call the regular verifyAnalysis functions. 252F.getContext().yield();
259 CurrentLoopDeleted ?
"<deleted>" 263if (CurrentLoopDeleted)
264// Do not run other passes on this loop. 268// If the loop was deleted, release all the loop passes. This frees up 269// some memory, and avoids trouble with the pass manager trying to call 270// verifyAnalysis on them. 271if (CurrentLoopDeleted) {
278// Pop the loop from queue after running all passes. 285 Changed |=
P->doFinalization();
291/// Print passes managed by this manager 296P->dumpPassStructure(
Offset + 1);
302//===----------------------------------------------------------------------===// 306const std::string &Banner)
const{
307returnnew PrintLoopPassWrapper(O, Banner);
310// Check if this pass is suitable for the current LPPassManager, if 311// available. This pass P is not suitable for a LPPassManager if P 312// is not preserving higher level analysis info used by other 313// LPPassManager passes. In such case, pop LPPassManager from the 314// stack. This will force assignPassManager() to create new 315// LPPassManger as expected. 319while (!PMS.
empty() &&
323// If this pass is destroying high level information that is used 324// by other passes that are managed by LPM then do not insert 325// this pass in current LPM. Use new LPPassManager. 331/// Assign pass manager to manage this pass. 335while (!PMS.
empty() &&
343// Create new Loop Pass Manager if it does not exist. 344assert (!PMS.
empty() &&
"Unable to create Loop Pass Manager");
347// [1] Create new Loop Pass Manager 351// [2] Set up new manager's top level manager 355// [3] Assign manager to manage this new manager. This may create 356// and push new managers into PMS 360// [4] Push new manager into PMS 372constFunction *
F = L->getHeader()->getParent();
375// Check the opt bisect limit. 380// Check for the OptimizeNone attribute. 381if (
F->hasOptNone()) {
382// FIXME: Report this to dbgs() only once per function. 384 <<
F->getName() <<
"\n");
385// FIXME: Delete loop from pass manager's queue? Analysis containing CSE Info
static std::string getDescription(const CallGraphSCC &SCC)
static unsigned InstrCount
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Module.h This file contains the declarations for the Module class.
static void addLoopIntoQueue(Loop *L, std::deque< Loop * > &LQ)
This file declares the interface for bisecting optimizations.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
This header defines classes/functions to handle pass execution timing information with interfaces for...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
bool runOnFunction(Function &F) override
run - Execute all of the passes scheduled for execution.
Pass * getAsPass() override
void dumpPassStructure(unsigned Offset) override
Print passes managed by this manager.
void markLoopAsDeleted(Loop &L)
LoopPass * getContainedPass(unsigned N)
void getAnalysisUsage(AnalysisUsage &Info) const override
Pass Manager itself does not invalidate any analysis info.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
void verifyLoop() const
Verify loop structure.
BlockT * getHeader() const
The legacy pass manager's analysis pass to compute loop information.
void preparePassManager(PMStack &PMS) override
Check if available pass managers are suitable for this pass or not.
Pass * createPrinterPass(raw_ostream &O, const std::string &Banner) const override
getPrinterPass - Get a pass to print the function corresponding to a Loop.
virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0
void assignPassManager(PMStack &PMS, PassManagerType PMT) override
Assign pass manager to manage this pass.
bool skipLoop(const Loop *L) const
Optional passes call this function to check whether the pass should be skipped.
Represents a single loop in the control flow graph.
StringRef getName() const
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, bool IgnoreTokens=true) const
Return true if this Loop and all inner subloops are in LCSSA form.
A Module instance is used to store all the information related to an LLVM module.
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
virtual bool shouldRunPass(const StringRef PassName, StringRef IRDescription)
IRDescription is a textual description of the IR unit the pass is running over.
PMDataManager provides the common place to manage the analysis data used by pass managers.
void removeDeadPasses(Pass *P, StringRef Msg, enum PassDebuggingString)
Remove dead passes used by P.
void dumpLastUses(Pass *P, unsigned Offset) const
void recordAvailableAnalysis(Pass *P)
Augment AvailableAnalysis by adding analysis made available by pass P.
PMTopLevelManager * getTopLevelManager()
unsigned initSizeRemarkInfo(Module &M, StringMap< std::pair< unsigned, unsigned > > &FunctionToInstrCount)
Set the initial size of the module if the user has specified that they want remarks for size.
void dumpRequiredSet(const Pass *P) const
void initializeAnalysisImpl(Pass *P)
All Required analyses should be available to the pass as it runs! Here we fill in the AnalysisImpls m...
void verifyPreservedAnalysis(Pass *P)
verifyPreservedAnalysis – Verify analysis presreved by pass P.
void freePass(Pass *P, StringRef Msg, enum PassDebuggingString)
Remove P.
bool preserveHigherLevelAnalysis(Pass *P)
unsigned getNumContainedPasses() const
virtual PassManagerType getPassManagerType() const
void emitInstrCountChangedRemark(Pass *P, Module &M, int64_t Delta, unsigned CountBefore, StringMap< std::pair< unsigned, unsigned > > &FunctionToInstrCount, Function *F=nullptr)
Emit a remark signifying that the number of IR instructions in the module changed.
void add(Pass *P, bool ProcessAnalysis=true)
Add pass P into the PassVector.
void populateInheritedAnalysis(PMStack &PMS)
void dumpPreservedSet(const Pass *P) const
void removeNotPreservedAnalysis(Pass *P)
Remove Analysis that is not preserved by the pass.
void dumpPassInfo(Pass *P, enum PassDebuggingString S1, enum PassDebuggingString S2, StringRef Msg)
PMStack - This class implements a stack data structure of PMDataManager pointers.
PMDataManager * top() const
void push(PMDataManager *PM)
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
void addIndirectPassManager(PMDataManager *Manager)
void schedulePass(Pass *P)
Schedule pass P for execution.
PassManagerPrettyStackEntry - This is used to print informative information about what pass is runnin...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
bool mustPreserveAnalysisID(char &AID) const
mustPreserveAnalysisID - This method serves the same function as getAnalysisIfAvailable,...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
StringRef - Represent a constant reference to a string, i.e.
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
The TimeTraceScope is a helper class to call the begin and end functions of the time trace profiler.
StringRef getName() const
Return a constant reference to the value's name.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
void initializeLCSSAVerificationPassPass(PassRegistry &)
PassManagerType
Different types of internal pass managers.
@ PMT_LoopPassManager
LPPassManager.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isFunctionInPrintList(StringRef FunctionName)
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop's contents as LLVM's text IR assembly.
