This is an archive of the discontinued LLVM Phabricator instance.

Differential D92616

[NewPM] Make pass adaptors less templatey
ClosedPublic

Authored by aeubanks on Dec 3 2020, 3:48 PM.

Details

Reviewers
asbirlea
ychen
rnk
thakis
dexonsmith
Commits
rG7f6f9f4cf966: [NewPM] Make pass adaptors less templatey
Summary

Currently PassBuilder.cpp is by far the file that takes longest to
compile. This is due to tons of templates being instantiated per pass.

Follow PassManager by using wrappers around passes to avoid making
the adaptors templated on the pass type. This allows us to move various
adaptors' run methods into .cpp files.

This reduces the compile time of PassBuilder.cpp on my machine from 66
to 39 seconds. It also reduces the size of opt from 685M to 676M.

Diff Detail

Event Timeline

aeubanks created this revision.Dec 3 2020, 3:48 PM
Herald added subscribers: dexonsmith, hiraditya. · View Herald TranscriptDec 3 2020, 3:48 PM
aeubanks requested review of this revision.Dec 3 2020, 3:48 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 3 2020, 3:48 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Harbormaster completed remote builds in B81031: Diff 309392.Dec 3 2020, 4:40 PM
aeubanks updated this revision to Diff 309405.Dec 3 2020, 4:50 PM

add missed references

aeubanks added reviewers: asbirlea, ychen, rnk, thakis.Dec 3 2020, 4:57 PM
Harbormaster completed remote builds in B81039: Diff 309405.Dec 3 2020, 5:18 PM
dexonsmith added a comment.Dec 3 2020, 5:25 PM

This seems like a great improvement!

llvm/lib/Passes/StandardInstrumentations.cpp
476 ↗(On Diff #309405)

Could / should these changes to use isIgnored be committed separately / ahead of time?

llvm/lib/Transforms/Scalar/LoopPassManager.cpp
89

Can adding this comment be pulled out to a separate commit? It seems unrelated to this change.

aeubanks mentioned this in D92625: Use isIgnored instead of checking pass name.Dec 3 2020, 5:44 PM
aeubanks marked an inline comment as done.Dec 3 2020, 6:14 PM
aeubanks added inline comments.
llvm/lib/Passes/StandardInstrumentations.cpp
476 ↗(On Diff #309405)

it is related to this change but can be done ahead of time: https://reviews.llvm.org/D92625

llvm/lib/Transforms/Scalar/LoopPassManager.cpp
89

this seems fairly benign to me, but sure

dexonsmith accepted this revision.Dec 3 2020, 6:32 PM

Once you've rebased on the other changes this LGTM.

llvm/lib/Passes/StandardInstrumentations.cpp
476 ↗(On Diff #309405)

Thanks!

llvm/lib/Transforms/Scalar/LoopPassManager.cpp
89

Thanks, I don't think it needs review or anything, but I had to stare at the diff for a while to see what had happened to the braces... if you commit unrelated comment / whitespace changes separately then later when people look at the log / blame / etc. it'll be a bit cleaner (in this chunk, the "new" brace will be the closing one for FunctionToLoopPassAdaptor::run instead of this one here)

This revision is now accepted and ready to land.Dec 3 2020, 6:32 PM
aeubanks mentioned this in rG0173eb0faf7b: Use isIgnored instead of checking pass name.Dec 3 2020, 6:38 PM
aeubanks updated this revision to Diff 309436.Dec 3 2020, 6:39 PM
aeubanks marked an inline comment as done.

rebase

Harbormaster completed remote builds in B81050: Diff 309436.Dec 3 2020, 8:02 PM
Closed by commit rG7f6f9f4cf966: [NewPM] Make pass adaptors less templatey (authored by aeubanks). · Explain WhyDec 4 2020, 8:43 AM
This revision was automatically updated to reflect the committed changes.
aeubanks added a commit: rG7f6f9f4cf966: [NewPM] Make pass adaptors less templatey.
rnk added a comment.Dec 7 2020, 12:27 PM

Just paged through this. Nice!

Revision Contents

PathSize
llvm/
include/
llvm/
Analysis/
518 lines
IR/
65 lines
Transforms/
Scalar/
173 lines
lib/
Analysis/
445 lines
IR/
48 lines
Transforms/
Scalar/
146 lines
test/
Other/
4 lines
20 lines

Diff 309545

llvm/include/llvm/Analysis/CGSCCPassManager.h

Show First 20 Lines • Show All 330 Lines • ▼ Show 20 Lines
/// runs a CGSCC pass over each one. /// runs a CGSCC pass over each one.
/// ///
/// Designed to allow composition of a CGSCCPass(Manager) and /// Designed to allow composition of a CGSCCPass(Manager) and
/// a ModulePassManager. Note that this pass must be run with a module analysis /// a ModulePassManager. Note that this pass must be run with a module analysis
/// manager as it uses the LazyCallGraph analysis. It will also run the /// manager as it uses the LazyCallGraph analysis. It will also run the
/// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
/// pass over the module to enable a \c FunctionAnalysisManager to be used /// pass over the module to enable a \c FunctionAnalysisManager to be used
/// within this run safely. /// within this run safely.
template <typename CGSCCPassT>
class ModuleToPostOrderCGSCCPassAdaptor class ModuleToPostOrderCGSCCPassAdaptor
: public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> { : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor> {
public: public:
explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) using PassConceptT =
: Pass(std::move(Pass)) {} detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager,
LazyCallGraph &, CGSCCUpdateResult &>;
// We have to explicitly define all the special member functions because MSVC explicit ModuleToPostOrderCGSCCPassAdaptor(std::unique_ptr<PassConceptT> Pass)
// refuses to generate them. : Pass(std::move(Pass)) {}
ModuleToPostOrderCGSCCPassAdaptor(
const ModuleToPostOrderCGSCCPassAdaptor &Arg)
: Pass(Arg.Pass) {}
ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg) ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
: Pass(std::move(Arg.Pass)) {} : Pass(std::move(Arg.Pass)) {}
friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS, friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
ModuleToPostOrderCGSCCPassAdaptor &RHS) { ModuleToPostOrderCGSCCPassAdaptor &RHS) {
std::swap(LHS.Pass, RHS.Pass); std::swap(LHS.Pass, RHS.Pass);
} }
ModuleToPostOrderCGSCCPassAdaptor & ModuleToPostOrderCGSCCPassAdaptor &
operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) { operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
swap(*this, RHS); swap(*this, RHS);
return *this; return *this;
} }
/// Runs the CGSCC pass across every SCC in the module. /// Runs the CGSCC pass across every SCC in the module.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
static bool isRequired() { return true; } static bool isRequired() { return true; }
private: private:
CGSCCPassT Pass; std::unique_ptr<PassConceptT> Pass;
}; };
/// A function to deduce a function pass type and wrap it in the /// A function to deduce a function pass type and wrap it in the
/// templated adaptor. /// templated adaptor.
template <typename CGSCCPassT> template <typename CGSCCPassT>
ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT> ModuleToPostOrderCGSCCPassAdaptor
createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) { createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass)); using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
PreservedAnalyses, CGSCCAnalysisManager,
LazyCallGraph &, CGSCCUpdateResult &>;
return ModuleToPostOrderCGSCCPassAdaptor(
std::make_unique<PassModelT>(std::move(Pass)));
} }
/// A proxy from a \c FunctionAnalysisManager to an \c SCC. /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
/// ///
/// When a module pass runs and triggers invalidation, both the CGSCC and /// When a module pass runs and triggers invalidation, both the CGSCC and
/// Function analysis manager proxies on the module get an invalidation event. /// Function analysis manager proxies on the module get an invalidation event.
/// We don't want to fully duplicate responsibility for most of the /// We don't want to fully duplicate responsibility for most of the
/// invalidation logic. Instead, this layer is only responsible for SCC-local /// invalidation logic. Instead, this layer is only responsible for SCC-local
▲ Show 20 Lines • Show All 61 Lines • ▼ Show 20 Lines
/// Adaptor that maps from a SCC to its functions. /// Adaptor that maps from a SCC to its functions.
/// ///
/// Designed to allow composition of a FunctionPass(Manager) and /// Designed to allow composition of a FunctionPass(Manager) and
/// a CGSCCPassManager. Note that if this pass is constructed with a pointer /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
/// to a \c CGSCCAnalysisManager it will run the /// to a \c CGSCCAnalysisManager it will run the
/// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
/// pass over the SCC to enable a \c FunctionAnalysisManager to be used /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
/// within this run safely. /// within this run safely.
template <typename FunctionPassT>
class CGSCCToFunctionPassAdaptor class CGSCCToFunctionPassAdaptor
: public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> { : public PassInfoMixin<CGSCCToFunctionPassAdaptor> {
public: public:
explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass) using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>;
: Pass(std::move(Pass)) {}
// We have to explicitly define all the special member functions because MSVC explicit CGSCCToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass)
// refuses to generate them. : Pass(std::move(Pass)) {}
CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
: Pass(Arg.Pass) {}
CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg) CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
: Pass(std::move(Arg.Pass)) {} : Pass(std::move(Arg.Pass)) {}
friend void swap(CGSCCToFunctionPassAdaptor &LHS, friend void swap(CGSCCToFunctionPassAdaptor &LHS,
CGSCCToFunctionPassAdaptor &RHS) { CGSCCToFunctionPassAdaptor &RHS) {
std::swap(LHS.Pass, RHS.Pass); std::swap(LHS.Pass, RHS.Pass);
} }
CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) { CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
swap(*this, RHS); swap(*this, RHS);
return *this; return *this;
} }
/// Runs the function pass across every function in the module. /// Runs the function pass across every function in the module.
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
LazyCallGraph &CG, CGSCCUpdateResult &UR) { LazyCallGraph &CG, CGSCCUpdateResult &UR);
// Setup the function analysis manager from its proxy.
FunctionAnalysisManager &FAM =
AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
SmallVector<LazyCallGraph::Node *, 4> Nodes;
for (LazyCallGraph::Node &N : C)
Nodes.push_back(&N);
// The SCC may get split while we are optimizing functions due to deleting
// edges. If this happens, the current SCC can shift, so keep track of
// a pointer we can overwrite.
LazyCallGraph::SCC *CurrentC = &C;
LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
<< "\n");
PreservedAnalyses PA = PreservedAnalyses::all();
for (LazyCallGraph::Node *N : Nodes) {
// Skip nodes from other SCCs. These may have been split out during
// processing. We'll eventually visit those SCCs and pick up the nodes
// there.
if (CG.lookupSCC(*N) != CurrentC)
continue;
Function &F = N->getFunction();
PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
if (!PI.runBeforePass<Function>(Pass, F))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass.name());
PassPA = Pass.run(F, FAM);
}
PI.runAfterPass<Function>(Pass, F, PassPA);
// We know that the function pass couldn't have invalidated any other
// function's analyses (that's the contract of a function pass), so
// directly handle the function analysis manager's invalidation here.
FAM.invalidate(F, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
PA.intersect(std::move(PassPA));
// If the call graph hasn't been preserved, update it based on this
// function pass. This may also update the current SCC to point to
// a smaller, more refined SCC.
auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
AM, UR, FAM);
assert(
CG.lookupSCC(*N) == CurrentC &&
"Current SCC not updated to the SCC containing the current node!");
}
}
// By definition we preserve the proxy. And we preserve all analyses on
// Functions. This precludes *any* invalidation of function analyses by the
// proxy, but that's OK because we've taken care to invalidate analyses in
// the function analysis manager incrementally above.
PA.preserveSet<AllAnalysesOn<Function>>();
PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
// We've also ensured that we updated the call graph along the way.
PA.preserve<LazyCallGraphAnalysis>();
return PA;
}
static bool isRequired() { return true; } static bool isRequired() { return true; }
private: private:
FunctionPassT Pass; std::unique_ptr<PassConceptT> Pass;
}; };
/// A function to deduce a function pass type and wrap it in the /// A function to deduce a function pass type and wrap it in the
/// templated adaptor. /// templated adaptor.
template <typename FunctionPassT> template <typename FunctionPassT>
CGSCCToFunctionPassAdaptor<FunctionPassT> CGSCCToFunctionPassAdaptor
createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) { createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)); using PassModelT =
detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
FunctionAnalysisManager>;
return CGSCCToFunctionPassAdaptor(
std::make_unique<PassModelT>(std::move(Pass)));
} }
/// Checks -abort-on-max-devirt-iterations-reached to see if we should report an /// Checks -abort-on-max-devirt-iterations-reached to see if we should report an
/// error. /// error.
void maxDevirtIterationsReached(); void maxDevirtIterationsReached();
/// A helper that repeats an SCC pass each time an indirect call is refined to /// A helper that repeats an SCC pass each time an indirect call is refined to
/// a direct call by that pass. /// a direct call by that pass.
/// ///
/// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
/// change shape, we may also want to repeat an SCC pass if it simply refines /// change shape, we may also want to repeat an SCC pass if it simply refines
/// an indirect call to a direct call, even if doing so does not alter the /// an indirect call to a direct call, even if doing so does not alter the
/// shape of the graph. Note that this only pertains to direct calls to /// shape of the graph. Note that this only pertains to direct calls to
/// functions where IPO across the SCC may be able to compute more precise /// functions where IPO across the SCC may be able to compute more precise
/// results. For intrinsics, we assume scalar optimizations already can fully /// results. For intrinsics, we assume scalar optimizations already can fully
/// reason about them. /// reason about them.
/// ///
/// This repetition has the potential to be very large however, as each one /// This repetition has the potential to be very large however, as each one
/// might refine a single call site. As a consequence, in practice we use an /// might refine a single call site. As a consequence, in practice we use an
/// upper bound on the number of repetitions to limit things. /// upper bound on the number of repetitions to limit things.
template <typename PassT> class DevirtSCCRepeatedPass : public PassInfoMixin<DevirtSCCRepeatedPass> {
class DevirtSCCRepeatedPass
: public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
public: public:
explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations) using PassConceptT =
detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager,
LazyCallGraph &, CGSCCUpdateResult &>;
explicit DevirtSCCRepeatedPass(std::unique_ptr<PassConceptT> Pass,
int MaxIterations)
: Pass(std::move(Pass)), MaxIterations(MaxIterations) {} : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
/// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
/// whenever an indirect call is refined. /// whenever an indirect call is refined.
PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM, PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
LazyCallGraph &CG, CGSCCUpdateResult &UR) { LazyCallGraph &CG, CGSCCUpdateResult &UR);
PreservedAnalyses PA = PreservedAnalyses::all();
PassInstrumentation PI =
AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
// The SCC may be refined while we are running passes over it, so set up
// a pointer that we can update.
LazyCallGraph::SCC *C = &InitialC;
// Struct to track the counts of direct and indirect calls in each function
// of the SCC.
struct CallCount {
int Direct;
int Indirect;
};
// Put value handles on all of the indirect calls and return the number of
// direct calls for each function in the SCC.
auto ScanSCC =
[](LazyCallGraph::SCC &C,
SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {
assert(CallHandles.empty() &&
"Must start with a clear set of handles.");
SmallDenseMap<Function *, CallCount> CallCounts;
CallCount CountLocal = {0, 0};
for (LazyCallGraph::Node &N : C) {
CallCount &Count =
CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
.first->second;
for (Instruction &I : instructions(N.getFunction()))
if (auto *CB = dyn_cast<CallBase>(&I)) {
if (CB->getCalledFunction()) {
++Count.Direct;
} else {
++Count.Indirect;
CallHandles.insert({CB, WeakTrackingVH(CB)});
}
}
}
return CallCounts;
};
UR.IndirectVHs.clear();
// Populate the initial call handles and get the initial call counts.
auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
for (int Iteration = 0;; ++Iteration) {
if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
continue;
PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
if (UR.InvalidatedSCCs.count(C))
PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass, PassPA);
else
PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C, PassPA);
// If the SCC structure has changed, bail immediately and let the outer
// CGSCC layer handle any iteration to reflect the refined structure.
if (UR.UpdatedC && UR.UpdatedC != C) {
PA.intersect(std::move(PassPA));
break;
}
// Check that we didn't miss any update scenario.
assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
assert(C->begin() != C->end() && "Cannot have an empty SCC!");
// Check whether any of the handles were devirtualized.
bool Devirt = llvm::any_of(UR.IndirectVHs, [](auto &P) -> bool {
if (P.second) {
if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
if (CB->getCalledFunction()) {
LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");
return true;
}
}
}
return false;
});
// Rescan to build up a new set of handles and count how many direct
// calls remain. If we decide to iterate, this also sets up the input to
// the next iteration.
UR.IndirectVHs.clear();
auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);
// If we haven't found an explicit devirtualization already see if we
// have decreased the number of indirect calls and increased the number
// of direct calls for any function in the SCC. This can be fooled by all
// manner of transformations such as DCE and other things, but seems to
// work well in practice.
if (!Devirt)
// Iterate over the keys in NewCallCounts, if Function also exists in
// CallCounts, make the check below.
for (auto &Pair : NewCallCounts) {
auto &CallCountNew = Pair.second;
auto CountIt = CallCounts.find(Pair.first);
if (CountIt != CallCounts.end()) {
const auto &CallCountOld = CountIt->second;
if (CallCountOld.Indirect > CallCountNew.Indirect &&
CallCountOld.Direct < CallCountNew.Direct) {
Devirt = true;
break;
}
}
}
if (!Devirt) {
PA.intersect(std::move(PassPA));
break;
}
// Otherwise, if we've already hit our max, we're done.
if (Iteration >= MaxIterations) {
maxDevirtIterationsReached();
LLVM_DEBUG(
dbgs() << "Found another devirtualization after hitting the max "
"number of repetitions ("
<< MaxIterations << ") on SCC: " << *C << "\n");
PA.intersect(std::move(PassPA));
break;
}
LLVM_DEBUG(
dbgs()
<< "Repeating an SCC pass after finding a devirtualization in: " << *C
<< "\n");
// Move over the new call counts in preparation for iterating.
CallCounts = std::move(NewCallCounts);
// Update the analysis manager with each run and intersect the total set
// of preserved analyses so we're ready to iterate.
AM.invalidate(*C, PassPA);
PA.intersect(std::move(PassPA));
}
// Note that we don't add any preserved entries here unlike a more normal
// "pass manager" because we only handle invalidation *between* iterations,
// not after the last iteration.
return PA;
}
private: private:
PassT Pass; std::unique_ptr<PassConceptT> Pass;
int MaxIterations; int MaxIterations;
}; };
/// A function to deduce a function pass type and wrap it in the /// A function to deduce a function pass type and wrap it in the
/// templated adaptor. /// templated adaptor.
template <typename PassT>
DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
int MaxIterations) {
return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
}
// Out-of-line implementation details for templates below this point.
template <typename CGSCCPassT> template <typename CGSCCPassT>
PreservedAnalyses DevirtSCCRepeatedPass createDevirtSCCRepeatedPass(CGSCCPassT Pass,
ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::run(Module &M, int MaxIterations) {
ModuleAnalysisManager &AM) { using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
// Setup the CGSCC analysis manager from its proxy. PreservedAnalyses, CGSCCAnalysisManager,
CGSCCAnalysisManager &CGAM = LazyCallGraph &, CGSCCUpdateResult &>;
AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager(); return DevirtSCCRepeatedPass(std::make_unique<PassModelT>(std::move(Pass)),
MaxIterations);
// Get the call graph for this module.
LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
// Get Function analysis manager from its proxy.
FunctionAnalysisManager &FAM =
AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M)->getManager();
// We keep worklists to allow us to push more work onto the pass manager as
// the passes are run.
SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
// Keep sets for invalidated SCCs and RefSCCs that should be skipped when
// iterating off the worklists.
SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
InlinedInternalEdges;
CGSCCUpdateResult UR = {
RCWorklist, CWorklist, InvalidRefSCCSet, InvalidSCCSet,
nullptr, nullptr, PreservedAnalyses::all(), InlinedInternalEdges,
{}};
// Request PassInstrumentation from analysis manager, will use it to run
// instrumenting callbacks for the passes later.
PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
PreservedAnalyses PA = PreservedAnalyses::all();
CG.buildRefSCCs();
for (auto RCI = CG.postorder_ref_scc_begin(),
RCE = CG.postorder_ref_scc_end();
RCI != RCE;) {
assert(RCWorklist.empty() &&
"Should always start with an empty RefSCC worklist");
// The postorder_ref_sccs range we are walking is lazily constructed, so
// we only push the first one onto the worklist. The worklist allows us
// to capture *new* RefSCCs created during transformations.
//
// We really want to form RefSCCs lazily because that makes them cheaper
// to update as the program is simplified and allows us to have greater
// cache locality as forming a RefSCC touches all the parts of all the
// functions within that RefSCC.
//
// We also eagerly increment the iterator to the next position because
// the CGSCC passes below may delete the current RefSCC.
RCWorklist.insert(&*RCI++);
do {
LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
if (InvalidRefSCCSet.count(RC)) {
LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
continue;
}
assert(CWorklist.empty() &&
"Should always start with an empty SCC worklist");
LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
<< "\n");
// The top of the worklist may *also* be the same SCC we just ran over
// (and invalidated for). Keep track of that last SCC we processed due
// to SCC update to avoid redundant processing when an SCC is both just
// updated itself and at the top of the worklist.
LazyCallGraph::SCC *LastUpdatedC = nullptr;
// Push the initial SCCs in reverse post-order as we'll pop off the
// back and so see this in post-order.
for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
CWorklist.insert(&C);
do {
LazyCallGraph::SCC *C = CWorklist.pop_back_val();
// Due to call graph mutations, we may have invalid SCCs or SCCs from
// other RefSCCs in the worklist. The invalid ones are dead and the
// other RefSCCs should be queued above, so we just need to skip both
// scenarios here.
if (InvalidSCCSet.count(C)) {
LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
continue;
}
if (LastUpdatedC == C) {
LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
continue;
}
if (&C->getOuterRefSCC() != RC) {
LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
"RefSCC...\n");
continue;
}
// Ensure we can proxy analysis updates from the CGSCC analysis manager
// into the the Function analysis manager by getting a proxy here.
// This also needs to update the FunctionAnalysisManager, as this may be
// the first time we see this SCC.
CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
FAM);
// Each time we visit a new SCC pulled off the worklist,
// a transformation of a child SCC may have also modified this parent
// and invalidated analyses. So we invalidate using the update record's
// cross-SCC preserved set. This preserved set is intersected by any
// CGSCC pass that handles invalidation (primarily pass managers) prior
// to marking its SCC as preserved. That lets us track everything that
// might need invalidation across SCCs without excessive invalidations
// on a single SCC.
//
// This essentially allows SCC passes to freely invalidate analyses
// of any ancestor SCC. If this becomes detrimental to successfully
// caching analyses, we could force each SCC pass to manually
// invalidate the analyses for any SCCs other than themselves which
// are mutated. However, that seems to lose the robustness of the
// pass-manager driven invalidation scheme.
CGAM.invalidate(*C, UR.CrossSCCPA);
do {
// Check that we didn't miss any update scenario.
assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
assert(C->begin() != C->end() && "Cannot have an empty SCC!");
assert(&C->getOuterRefSCC() == RC &&
"Processing an SCC in a different RefSCC!");
LastUpdatedC = UR.UpdatedC;
UR.UpdatedRC = nullptr;
UR.UpdatedC = nullptr;
// Check the PassInstrumentation's BeforePass callbacks before
// running the pass, skip its execution completely if asked to
// (callback returns false).
if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass.name());
PassPA = Pass.run(*C, CGAM, CG, UR);
}
if (UR.InvalidatedSCCs.count(C))
PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass, PassPA);
else
PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C, PassPA);
// Update the SCC and RefSCC if necessary.
C = UR.UpdatedC ? UR.UpdatedC : C;
RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
if (UR.UpdatedC) {
// If we're updating the SCC, also update the FAM inside the proxy's
// result.
CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
FAM);
}
// If the CGSCC pass wasn't able to provide a valid updated SCC,
// the current SCC may simply need to be skipped if invalid.
if (UR.InvalidatedSCCs.count(C)) {
LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
break;
}
// Check that we didn't miss any update scenario.
assert(C->begin() != C->end() && "Cannot have an empty SCC!");
// We handle invalidating the CGSCC analysis manager's information
// for the (potentially updated) SCC here. Note that any other SCCs
// whose structure has changed should have been invalidated by
// whatever was updating the call graph. This SCC gets invalidated
// late as it contains the nodes that were actively being
// processed.
CGAM.invalidate(*C, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
// Also intersect with the cross-SCC preserved set to capture any
// cross-SCC invalidation.
UR.CrossSCCPA.intersect(PassPA);
PA.intersect(std::move(PassPA));
// The pass may have restructured the call graph and refined the
// current SCC and/or RefSCC. We need to update our current SCC and
// RefSCC pointers to follow these. Also, when the current SCC is
// refined, re-run the SCC pass over the newly refined SCC in order
// to observe the most precise SCC model available. This inherently
// cannot cycle excessively as it only happens when we split SCCs
// apart, at most converging on a DAG of single nodes.
// FIXME: If we ever start having RefSCC passes, we'll want to
// iterate there too.
if (UR.UpdatedC)
LLVM_DEBUG(dbgs()
<< "Re-running SCC passes after a refinement of the "
"current SCC: "
<< *UR.UpdatedC << "\n");
// Note that both `C` and `RC` may at this point refer to deleted,
// invalid SCC and RefSCCs respectively. But we will short circuit
// the processing when we check them in the loop above.
} while (UR.UpdatedC);
} while (!CWorklist.empty());
// We only need to keep internal inlined edge information within
// a RefSCC, clear it to save on space and let the next time we visit
// any of these functions have a fresh start.
InlinedInternalEdges.clear();
} while (!RCWorklist.empty());
}
// By definition we preserve the call garph, all SCC analyses, and the
// analysis proxies by handling them above and in any nested pass managers.
PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
PA.preserve<LazyCallGraphAnalysis>();
PA.preserve<CGSCCAnalysisManagerModuleProxy>();
PA.preserve<FunctionAnalysisManagerModuleProxy>();
return PA;
} }
// Clear out the debug logging macro. // Clear out the debug logging macro.
#undef DEBUG_TYPE #undef DEBUG_TYPE
} // end namespace llvm } // end namespace llvm
#endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H

llvm/include/llvm/IR/PassManager.h

Show First 20 Lines • Show All 1,222 Lines • ▼ Show 20 Lines
/// For example, a function pass is not permitted to add functions to the /// For example, a function pass is not permitted to add functions to the
/// module. /// module.
/// FIXME: Make the above true for all of LLVM's actual passes, some still /// FIXME: Make the above true for all of LLVM's actual passes, some still
/// violate this principle. /// violate this principle.
/// ///
/// Note that although function passes can access module analyses, module /// Note that although function passes can access module analyses, module
/// analyses are not invalidated while the function passes are running, so they /// analyses are not invalidated while the function passes are running, so they
/// may be stale. Function analyses will not be stale. /// may be stale. Function analyses will not be stale.
template <typename FunctionPassT>
class ModuleToFunctionPassAdaptor class ModuleToFunctionPassAdaptor
: public PassInfoMixin<ModuleToFunctionPassAdaptor<FunctionPassT>> { : public PassInfoMixin<ModuleToFunctionPassAdaptor> {
public: public:
explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass) using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>;
explicit ModuleToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass)
: Pass(std::move(Pass)) {} : Pass(std::move(Pass)) {}
/// Runs the function pass across every function in the module. /// Runs the function pass across every function in the module.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) { PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
FunctionAnalysisManager &FAM =
AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
// Request PassInstrumentation from analysis manager, will use it to run
// instrumenting callbacks for the passes later.
PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
PreservedAnalyses PA = PreservedAnalyses::all();
for (Function &F : M) {
if (F.isDeclaration())
continue;
// Check the PassInstrumentation's BeforePass callbacks before running the
// pass, skip its execution completely if asked to (callback returns
// false).
if (!PI.runBeforePass<Function>(Pass, F))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass.name(), F.getName());
PassPA = Pass.run(F, FAM);
}
PI.runAfterPass(Pass, F, PassPA);
// We know that the function pass couldn't have invalidated any other
// function's analyses (that's the contract of a function pass), so
// directly handle the function analysis manager's invalidation here.
FAM.invalidate(F, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
PA.intersect(std::move(PassPA));
}
// The FunctionAnalysisManagerModuleProxy is preserved because (we assume)
// the function passes we ran didn't add or remove any functions.
//
// We also preserve all analyses on Functions, because we did all the
// invalidation we needed to do above.
PA.preserveSet<AllAnalysesOn<Function>>();
PA.preserve<FunctionAnalysisManagerModuleProxy>();
return PA;
}
static bool isRequired() { return true; } static bool isRequired() { return true; }
private: private:
FunctionPassT Pass; std::unique_ptr<PassConceptT> Pass;
}; };
/// A function to deduce a function pass type and wrap it in the /// A function to deduce a function pass type and wrap it in the
/// templated adaptor. /// templated adaptor.
template <typename FunctionPassT> template <typename FunctionPassT>
ModuleToFunctionPassAdaptor<FunctionPassT> ModuleToFunctionPassAdaptor
createModuleToFunctionPassAdaptor(FunctionPassT Pass) { createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
return ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)); using PassModelT =
detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
FunctionAnalysisManager>;
return ModuleToFunctionPassAdaptor(
std::make_unique<PassModelT>(std::move(Pass)));
} }
/// A utility pass template to force an analysis result to be available. /// A utility pass template to force an analysis result to be available.
/// ///
/// If there are extra arguments at the pass's run level there may also be /// If there are extra arguments at the pass's run level there may also be
/// extra arguments to the analysis manager's \c getResult routine. We can't /// extra arguments to the analysis manager's \c getResult routine. We can't
/// guess how to effectively map the arguments from one to the other, and so /// guess how to effectively map the arguments from one to the other, and so
/// this specialization just ignores them. /// this specialization just ignores them.
▲ Show 20 Lines • Show All 103 Lines • Show Last 20 Lines

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

Show First 20 Lines • Show All 50 Lines • ▼ Show 20 Lines
#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Dominators.h" #include "llvm/IR/Dominators.h"
#include "llvm/IR/PassInstrumentation.h" #include "llvm/IR/PassInstrumentation.h"
#include "llvm/IR/PassManager.h" #include "llvm/IR/PassManager.h"
#include "llvm/Transforms/Utils/LCSSA.h" #include "llvm/Transforms/Utils/LCSSA.h"
#include "llvm/Transforms/Utils/LoopSimplify.h" #include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/LoopUtils.h"
#include <memory>
namespace llvm { namespace llvm {
// Forward declarations of an update tracking API used in the pass manager. // Forward declarations of an update tracking API used in the pass manager.
class LPMUpdater; class LPMUpdater;
// Explicit specialization and instantiation declarations for the pass manager. // Explicit specialization and instantiation declarations for the pass manager.
// See the comments on the definition of the specialization for details on how // See the comments on the definition of the specialization for details on how
Show All 33 Lines
}; };
/// An alias template to easily name a require analysis loop pass. /// An alias template to easily name a require analysis loop pass.
template <typename AnalysisT> template <typename AnalysisT>
using RequireAnalysisLoopPass = using RequireAnalysisLoopPass =
RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
LoopStandardAnalysisResults &, LPMUpdater &>; LoopStandardAnalysisResults &, LPMUpdater &>;
template <typename LoopPassT> class FunctionToLoopPassAdaptor; class FunctionToLoopPassAdaptor;
/// This class provides an interface for updating the loop pass manager based /// This class provides an interface for updating the loop pass manager based
/// on mutations to the loop nest. /// on mutations to the loop nest.
/// ///
/// A reference to an instance of this class is passed as an argument to each /// A reference to an instance of this class is passed as an argument to each
/// Loop pass, and Loop passes should use it to update LPM infrastructure if /// Loop pass, and Loop passes should use it to update LPM infrastructure if
/// they modify the loop nest structure. /// they modify the loop nest structure.
class LPMUpdater { class LPMUpdater {
▲ Show 20 Lines • Show All 78 Lines • ▼ Show 20 Lines void revisitCurrentLoop() {
// Tell the currently in-flight pipeline to stop running. // Tell the currently in-flight pipeline to stop running.
SkipCurrentLoop = true; SkipCurrentLoop = true;
// And insert ourselves back into the worklist. // And insert ourselves back into the worklist.
Worklist.insert(CurrentL); Worklist.insert(CurrentL);
} }
private: private:
template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor; friend class llvm::FunctionToLoopPassAdaptor;
/// The \c FunctionToLoopPassAdaptor's worklist of loops to process. /// The \c FunctionToLoopPassAdaptor's worklist of loops to process.
SmallPriorityWorklist<Loop *, 4> &Worklist; SmallPriorityWorklist<Loop *, 4> &Worklist;
/// The analysis manager for use in the current loop nest. /// The analysis manager for use in the current loop nest.
LoopAnalysisManager &LAM; LoopAnalysisManager &LAM;
Loop *CurrentL; Loop *CurrentL;
Show All 12 Lines
/// Adaptor that maps from a function to its loops. /// Adaptor that maps from a function to its loops.
/// ///
/// Designed to allow composition of a LoopPass(Manager) and a /// Designed to allow composition of a LoopPass(Manager) and a
/// FunctionPassManager. Note that if this pass is constructed with a \c /// FunctionPassManager. Note that if this pass is constructed with a \c
/// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
/// analysis prior to running the loop passes over the function to enable a \c /// analysis prior to running the loop passes over the function to enable a \c
/// LoopAnalysisManager to be used within this run safely. /// LoopAnalysisManager to be used within this run safely.
template <typename LoopPassT>
class FunctionToLoopPassAdaptor class FunctionToLoopPassAdaptor
: public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> { : public PassInfoMixin<FunctionToLoopPassAdaptor> {
public: public:
explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false, using PassConceptT =
detail::PassConcept<Loop, LoopAnalysisManager,
LoopStandardAnalysisResults &, LPMUpdater &>;
explicit FunctionToLoopPassAdaptor(std::unique_ptr<PassConceptT> Pass,
bool UseMemorySSA = false,
bool UseBlockFrequencyInfo = false, bool UseBlockFrequencyInfo = false,
bool DebugLogging = false) bool DebugLogging = false)
: Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging), : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging),
UseMemorySSA(UseMemorySSA), UseMemorySSA(UseMemorySSA),
UseBlockFrequencyInfo(UseBlockFrequencyInfo) { UseBlockFrequencyInfo(UseBlockFrequencyInfo) {
LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
LoopCanonicalizationFPM.addPass(LCSSAPass()); LoopCanonicalizationFPM.addPass(LCSSAPass());
} }
/// Runs the loop passes across every loop in the function. /// Runs the loop passes across every loop in the function.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
// Before we even compute any loop analyses, first run a miniature function
// pass pipeline to put loops into their canonical form. Note that we can
// directly build up function analyses after this as the function pass
// manager handles all the invalidation at that layer.
PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
PreservedAnalyses PA = PreservedAnalyses::all();
// Check the PassInstrumentation's BeforePass callbacks before running the
// canonicalization pipeline.
if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
PA = LoopCanonicalizationFPM.run(F, AM);
PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
}
// Get the loop structure for this function
LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
// If there are no loops, there is nothing to do here.
if (LI.empty())
return PA;
// Get the analysis results needed by loop passes.
MemorySSA *MSSA = UseMemorySSA
? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
: nullptr;
BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
? (&AM.getResult<BlockFrequencyAnalysis>(F))
: nullptr;
LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
AM.getResult<AssumptionAnalysis>(F),
AM.getResult<DominatorTreeAnalysis>(F),
AM.getResult<LoopAnalysis>(F),
AM.getResult<ScalarEvolutionAnalysis>(F),
AM.getResult<TargetLibraryAnalysis>(F),
AM.getResult<TargetIRAnalysis>(F),
BFI,
MSSA};
// Setup the loop analysis manager from its proxy. It is important that
// this is only done when there are loops to process and we have built the
// LoopStandardAnalysisResults object. The loop analyses cached in this
// manager have access to those analysis results and so it must invalidate
// itself when they go away.
auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
if (UseMemorySSA)
LAMFP.markMSSAUsed();
LoopAnalysisManager &LAM = LAMFP.getManager();
// A postorder worklist of loops to process.
SmallPriorityWorklist<Loop *, 4> Worklist;
// Register the worklist and loop analysis manager so that loop passes can
// update them when they mutate the loop nest structure.
LPMUpdater Updater(Worklist, LAM);
// Add the loop nests in the reverse order of LoopInfo. See method
// declaration.
appendLoopsToWorklist(LI, Worklist);
#ifndef NDEBUG
PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
if (isSpecialPass(PassID, {"PassManager"}))
return;
assert(any_isa<const Loop *>(IR));
const Loop *L = any_cast<const Loop *>(IR);
assert(L && "Loop should be valid for printing");
// Verify the loop structure and LCSSA form before visiting the loop.
L->verifyLoop();
assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
"Loops must remain in LCSSA form!");
});
#endif
do {
Loop *L = Worklist.pop_back_val();
// Reset the update structure for this loop.
Updater.CurrentL = L;
Updater.SkipCurrentLoop = false;
#ifndef NDEBUG
// Save a parent loop pointer for asserts.
Updater.ParentL = L->getParentLoop();
#endif
// Check the PassInstrumentation's BeforePass callbacks before running the
// pass, skip its execution completely if asked to (callback returns
// false).
if (!PI.runBeforePass<Loop>(Pass, *L))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass.name());
PassPA = Pass.run(*L, LAM, LAR, Updater);
}
// Do not pass deleted Loop into the instrumentation.
if (Updater.skipCurrentLoop())
PI.runAfterPassInvalidated<Loop>(Pass, PassPA);
else
PI.runAfterPass<Loop>(Pass, *L, PassPA);
// FIXME: We should verify the set of analyses relevant to Loop passes
// are preserved.
// If the loop hasn't been deleted, we need to handle invalidation here.
if (!Updater.skipCurrentLoop())
// We know that the loop pass couldn't have invalidated any other
// loop's analyses (that's the contract of a loop pass), so directly
// handle the loop analysis manager's invalidation here.
LAM.invalidate(*L, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
PA.intersect(std::move(PassPA));
} while (!Worklist.empty());
#ifndef NDEBUG
PI.popBeforeNonSkippedPassCallback();
#endif
// By definition we preserve the proxy. We also preserve all analyses on
// Loops. This precludes *any* invalidation of loop analyses by the proxy,
// but that's OK because we've taken care to invalidate analyses in the
// loop analysis manager incrementally above.
PA.preserveSet<AllAnalysesOn<Loop>>();
PA.preserve<LoopAnalysisManagerFunctionProxy>();
// We also preserve the set of standard analyses.
PA.preserve<DominatorTreeAnalysis>();
PA.preserve<LoopAnalysis>();
PA.preserve<ScalarEvolutionAnalysis>();
if (UseBlockFrequencyInfo && F.hasProfileData())
PA.preserve<BlockFrequencyAnalysis>();
if (UseMemorySSA)
PA.preserve<MemorySSAAnalysis>();
// FIXME: What we really want to do here is preserve an AA category, but
// that concept doesn't exist yet.
PA.preserve<AAManager>();
PA.preserve<BasicAA>();
PA.preserve<GlobalsAA>();
PA.preserve<SCEVAA>();
return PA;
}
static bool isRequired() { return true; } static bool isRequired() { return true; }
private: private:
LoopPassT Pass; std::unique_ptr<PassConceptT> Pass;
FunctionPassManager LoopCanonicalizationFPM; FunctionPassManager LoopCanonicalizationFPM;
bool UseMemorySSA = false; bool UseMemorySSA = false;
bool UseBlockFrequencyInfo = false; bool UseBlockFrequencyInfo = false;
}; };
/// A function to deduce a loop pass type and wrap it in the templated /// A function to deduce a loop pass type and wrap it in the templated
/// adaptor. /// adaptor.
template <typename LoopPassT> template <typename LoopPassT>
FunctionToLoopPassAdaptor<LoopPassT> FunctionToLoopPassAdaptor
createFunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false, createFunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false,
bool UseBlockFrequencyInfo = false, bool UseBlockFrequencyInfo = false,
bool DebugLogging = false) { bool DebugLogging = false) {
return FunctionToLoopPassAdaptor<LoopPassT>( using PassModelT =
std::move(Pass), UseMemorySSA, UseBlockFrequencyInfo, DebugLogging); detail::PassModel<Loop, LoopPassT, PreservedAnalyses, LoopAnalysisManager,
LoopStandardAnalysisResults &, LPMUpdater &>;
return FunctionToLoopPassAdaptor(
std::make_unique<PassModelT>(std::move(Pass)), UseMemorySSA,
UseBlockFrequencyInfo, DebugLogging);
} }
/// Pass for printing a loop's contents as textual IR. /// Pass for printing a loop's contents as textual IR.
class PrintLoopPass : public PassInfoMixin<PrintLoopPass> { class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
raw_ostream &OS; raw_ostream &OS;
std::string Banner; std::string Banner;
public: public:
Show All 9 Lines

llvm/lib/Analysis/CGSCCPassManager.cpp

Show First 20 Lines • Show All 142 Lines • ▼ Show 20 LinesPassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>(); PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
if (DebugLogging) if (DebugLogging)
dbgs() << "Finished CGSCC pass manager run.\n"; dbgs() << "Finished CGSCC pass manager run.\n";
return PA; return PA;
} }
PreservedAnalyses
ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, ModuleAnalysisManager &AM) {
// Setup the CGSCC analysis manager from its proxy.
CGSCCAnalysisManager &CGAM =
AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
// Get the call graph for this module.
LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
// Get Function analysis manager from its proxy.
FunctionAnalysisManager &FAM =
AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M)->getManager();
// We keep worklists to allow us to push more work onto the pass manager as
// the passes are run.
SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
// Keep sets for invalidated SCCs and RefSCCs that should be skipped when
// iterating off the worklists.
SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
InlinedInternalEdges;
CGSCCUpdateResult UR = {
RCWorklist, CWorklist, InvalidRefSCCSet, InvalidSCCSet,
nullptr, nullptr, PreservedAnalyses::all(), InlinedInternalEdges,
{}};
// Request PassInstrumentation from analysis manager, will use it to run
// instrumenting callbacks for the passes later.
PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
PreservedAnalyses PA = PreservedAnalyses::all();
CG.buildRefSCCs();
for (auto RCI = CG.postorder_ref_scc_begin(),
RCE = CG.postorder_ref_scc_end();
RCI != RCE;) {
assert(RCWorklist.empty() &&
"Should always start with an empty RefSCC worklist");
// The postorder_ref_sccs range we are walking is lazily constructed, so
// we only push the first one onto the worklist. The worklist allows us
// to capture *new* RefSCCs created during transformations.
//
// We really want to form RefSCCs lazily because that makes them cheaper
// to update as the program is simplified and allows us to have greater
// cache locality as forming a RefSCC touches all the parts of all the
// functions within that RefSCC.
//
// We also eagerly increment the iterator to the next position because
// the CGSCC passes below may delete the current RefSCC.
RCWorklist.insert(&*RCI++);
do {
LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
if (InvalidRefSCCSet.count(RC)) {
LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
continue;
}
assert(CWorklist.empty() &&
"Should always start with an empty SCC worklist");
LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
<< "\n");
// The top of the worklist may *also* be the same SCC we just ran over
// (and invalidated for). Keep track of that last SCC we processed due
// to SCC update to avoid redundant processing when an SCC is both just
// updated itself and at the top of the worklist.
LazyCallGraph::SCC *LastUpdatedC = nullptr;
// Push the initial SCCs in reverse post-order as we'll pop off the
// back and so see this in post-order.
for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
CWorklist.insert(&C);
do {
LazyCallGraph::SCC *C = CWorklist.pop_back_val();
// Due to call graph mutations, we may have invalid SCCs or SCCs from
// other RefSCCs in the worklist. The invalid ones are dead and the
// other RefSCCs should be queued above, so we just need to skip both
// scenarios here.
if (InvalidSCCSet.count(C)) {
LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
continue;
}
if (LastUpdatedC == C) {
LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
continue;
}
if (&C->getOuterRefSCC() != RC) {
LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
"RefSCC...\n");
continue;
}
// Ensure we can proxy analysis updates from the CGSCC analysis manager
// into the the Function analysis manager by getting a proxy here.
// This also needs to update the FunctionAnalysisManager, as this may be
// the first time we see this SCC.
CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
FAM);
// Each time we visit a new SCC pulled off the worklist,
// a transformation of a child SCC may have also modified this parent
// and invalidated analyses. So we invalidate using the update record's
// cross-SCC preserved set. This preserved set is intersected by any
// CGSCC pass that handles invalidation (primarily pass managers) prior
// to marking its SCC as preserved. That lets us track everything that
// might need invalidation across SCCs without excessive invalidations
// on a single SCC.
//
// This essentially allows SCC passes to freely invalidate analyses
// of any ancestor SCC. If this becomes detrimental to successfully
// caching analyses, we could force each SCC pass to manually
// invalidate the analyses for any SCCs other than themselves which
// are mutated. However, that seems to lose the robustness of the
// pass-manager driven invalidation scheme.
CGAM.invalidate(*C, UR.CrossSCCPA);
do {
// Check that we didn't miss any update scenario.
assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
assert(C->begin() != C->end() && "Cannot have an empty SCC!");
assert(&C->getOuterRefSCC() == RC &&
"Processing an SCC in a different RefSCC!");
LastUpdatedC = UR.UpdatedC;
UR.UpdatedRC = nullptr;
UR.UpdatedC = nullptr;
// Check the PassInstrumentation's BeforePass callbacks before
// running the pass, skip its execution completely if asked to
// (callback returns false).
if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass->name());
PassPA = Pass->run(*C, CGAM, CG, UR);
}
if (UR.InvalidatedSCCs.count(C))
PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
else
PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
// Update the SCC and RefSCC if necessary.
C = UR.UpdatedC ? UR.UpdatedC : C;
RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
if (UR.UpdatedC) {
// If we're updating the SCC, also update the FAM inside the proxy's
// result.
CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
FAM);
}
// If the CGSCC pass wasn't able to provide a valid updated SCC,
// the current SCC may simply need to be skipped if invalid.
if (UR.InvalidatedSCCs.count(C)) {
LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
break;
}
// Check that we didn't miss any update scenario.
assert(C->begin() != C->end() && "Cannot have an empty SCC!");
// We handle invalidating the CGSCC analysis manager's information
// for the (potentially updated) SCC here. Note that any other SCCs
// whose structure has changed should have been invalidated by
// whatever was updating the call graph. This SCC gets invalidated
// late as it contains the nodes that were actively being
// processed.
CGAM.invalidate(*C, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
// Also intersect with the cross-SCC preserved set to capture any
// cross-SCC invalidation.
UR.CrossSCCPA.intersect(PassPA);
PA.intersect(std::move(PassPA));
// The pass may have restructured the call graph and refined the
// current SCC and/or RefSCC. We need to update our current SCC and
// RefSCC pointers to follow these. Also, when the current SCC is
// refined, re-run the SCC pass over the newly refined SCC in order
// to observe the most precise SCC model available. This inherently
// cannot cycle excessively as it only happens when we split SCCs
// apart, at most converging on a DAG of single nodes.
// FIXME: If we ever start having RefSCC passes, we'll want to
// iterate there too.
if (UR.UpdatedC)
LLVM_DEBUG(dbgs()
<< "Re-running SCC passes after a refinement of the "
"current SCC: "
<< *UR.UpdatedC << "\n");
// Note that both `C` and `RC` may at this point refer to deleted,
// invalid SCC and RefSCCs respectively. But we will short circuit
// the processing when we check them in the loop above.
} while (UR.UpdatedC);
} while (!CWorklist.empty());
// We only need to keep internal inlined edge information within
// a RefSCC, clear it to save on space and let the next time we visit
// any of these functions have a fresh start.
InlinedInternalEdges.clear();
} while (!RCWorklist.empty());
}
// By definition we preserve the call garph, all SCC analyses, and the
// analysis proxies by handling them above and in any nested pass managers.
PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
PA.preserve<LazyCallGraphAnalysis>();
PA.preserve<CGSCCAnalysisManagerModuleProxy>();
PA.preserve<FunctionAnalysisManagerModuleProxy>();
return PA;
}
PreservedAnalyses DevirtSCCRepeatedPass::run(LazyCallGraph::SCC &InitialC,
CGSCCAnalysisManager &AM,
LazyCallGraph &CG,
CGSCCUpdateResult &UR) {
PreservedAnalyses PA = PreservedAnalyses::all();
PassInstrumentation PI =
AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
// The SCC may be refined while we are running passes over it, so set up
// a pointer that we can update.
LazyCallGraph::SCC *C = &InitialC;
// Struct to track the counts of direct and indirect calls in each function
// of the SCC.
struct CallCount {
int Direct;
int Indirect;
};
// Put value handles on all of the indirect calls and return the number of
// direct calls for each function in the SCC.
auto ScanSCC = [](LazyCallGraph::SCC &C,
SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {
assert(CallHandles.empty() && "Must start with a clear set of handles.");
SmallDenseMap<Function *, CallCount> CallCounts;
CallCount CountLocal = {0, 0};
for (LazyCallGraph::Node &N : C) {
CallCount &Count =
CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
.first->second;
for (Instruction &I : instructions(N.getFunction()))
if (auto *CB = dyn_cast<CallBase>(&I)) {
if (CB->getCalledFunction()) {
++Count.Direct;
} else {
++Count.Indirect;
CallHandles.insert({CB, WeakTrackingVH(CB)});
}
}
}
return CallCounts;
};
UR.IndirectVHs.clear();
// Populate the initial call handles and get the initial call counts.
auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
for (int Iteration = 0;; ++Iteration) {
if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
continue;
PreservedAnalyses PassPA = Pass->run(*C, AM, CG, UR);
if (UR.InvalidatedSCCs.count(C))
PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
else
PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
// If the SCC structure has changed, bail immediately and let the outer
// CGSCC layer handle any iteration to reflect the refined structure.
if (UR.UpdatedC && UR.UpdatedC != C) {
PA.intersect(std::move(PassPA));
break;
}
// Check that we didn't miss any update scenario.
assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
assert(C->begin() != C->end() && "Cannot have an empty SCC!");
// Check whether any of the handles were devirtualized.
bool Devirt = llvm::any_of(UR.IndirectVHs, [](auto &P) -> bool {
if (P.second) {
if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
if (CB->getCalledFunction()) {
LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");
return true;
}
}
}
return false;
});
// Rescan to build up a new set of handles and count how many direct
// calls remain. If we decide to iterate, this also sets up the input to
// the next iteration.
UR.IndirectVHs.clear();
auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);
// If we haven't found an explicit devirtualization already see if we
// have decreased the number of indirect calls and increased the number
// of direct calls for any function in the SCC. This can be fooled by all
// manner of transformations such as DCE and other things, but seems to
// work well in practice.
if (!Devirt)
// Iterate over the keys in NewCallCounts, if Function also exists in
// CallCounts, make the check below.
for (auto &Pair : NewCallCounts) {
auto &CallCountNew = Pair.second;
auto CountIt = CallCounts.find(Pair.first);
if (CountIt != CallCounts.end()) {
const auto &CallCountOld = CountIt->second;
if (CallCountOld.Indirect > CallCountNew.Indirect &&
CallCountOld.Direct < CallCountNew.Direct) {
Devirt = true;
break;
}
}
}
if (!Devirt) {
PA.intersect(std::move(PassPA));
break;
}
// Otherwise, if we've already hit our max, we're done.
if (Iteration >= MaxIterations) {
maxDevirtIterationsReached();
LLVM_DEBUG(
dbgs() << "Found another devirtualization after hitting the max "
"number of repetitions ("
<< MaxIterations << ") on SCC: " << *C << "\n");
PA.intersect(std::move(PassPA));
break;
}
LLVM_DEBUG(
dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
<< *C << "\n");
// Move over the new call counts in preparation for iterating.
CallCounts = std::move(NewCallCounts);
// Update the analysis manager with each run and intersect the total set
// of preserved analyses so we're ready to iterate.
AM.invalidate(*C, PassPA);
PA.intersect(std::move(PassPA));
}
// Note that we don't add any preserved entries here unlike a more normal
// "pass manager" because we only handle invalidation *between* iterations,
// not after the last iteration.
return PA;
}
PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,
CGSCCAnalysisManager &AM,
LazyCallGraph &CG,
CGSCCUpdateResult &UR) {
// Setup the function analysis manager from its proxy.
FunctionAnalysisManager &FAM =
AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
SmallVector<LazyCallGraph::Node *, 4> Nodes;
for (LazyCallGraph::Node &N : C)
Nodes.push_back(&N);
// The SCC may get split while we are optimizing functions due to deleting
// edges. If this happens, the current SCC can shift, so keep track of
// a pointer we can overwrite.
LazyCallGraph::SCC *CurrentC = &C;
LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n");
PreservedAnalyses PA = PreservedAnalyses::all();
for (LazyCallGraph::Node *N : Nodes) {
// Skip nodes from other SCCs. These may have been split out during
// processing. We'll eventually visit those SCCs and pick up the nodes
// there.
if (CG.lookupSCC(*N) != CurrentC)
continue;
Function &F = N->getFunction();
PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
if (!PI.runBeforePass<Function>(*Pass, F))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass->name());
PassPA = Pass->run(F, FAM);
}
PI.runAfterPass<Function>(*Pass, F, PassPA);
// We know that the function pass couldn't have invalidated any other
// function's analyses (that's the contract of a function pass), so
// directly handle the function analysis manager's invalidation here.
FAM.invalidate(F, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
PA.intersect(std::move(PassPA));
// If the call graph hasn't been preserved, update it based on this
// function pass. This may also update the current SCC to point to
// a smaller, more refined SCC.
auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
AM, UR, FAM);
assert(CG.lookupSCC(*N) == CurrentC &&
"Current SCC not updated to the SCC containing the current node!");
}
}
// By definition we preserve the proxy. And we preserve all analyses on
// Functions. This precludes *any* invalidation of function analyses by the
// proxy, but that's OK because we've taken care to invalidate analyses in
// the function analysis manager incrementally above.
PA.preserveSet<AllAnalysesOn<Function>>();
PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
// We've also ensured that we updated the call graph along the way.
PA.preserve<LazyCallGraphAnalysis>();
return PA;
}
bool CGSCCAnalysisManagerModuleProxy::Result::invalidate( bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
Module &M, const PreservedAnalyses &PA, Module &M, const PreservedAnalyses &PA,
ModuleAnalysisManager::Invalidator &Inv) { ModuleAnalysisManager::Invalidator &Inv) {
// If literally everything is preserved, we're done. // If literally everything is preserved, we're done.
if (PA.areAllPreserved()) if (PA.areAllPreserved())
return false; // This is still a valid proxy. return false; // This is still a valid proxy.
// If this proxy or the call graph is going to be invalidated, we also need // If this proxy or the call graph is going to be invalidated, we also need
▲ Show 20 Lines • Show All 646 Lines • Show Last 20 Lines

llvm/lib/IR/PassManager.cpp

Show First 20 Lines • Show All 85 Lines • ▼ Show 20 Lines if (!AreFunctionAnalysesPreserved)
InnerAM->invalidate(F, PA); InnerAM->invalidate(F, PA);
} }
// Return false to indicate that this result is still a valid proxy. // Return false to indicate that this result is still a valid proxy.
return false; return false;
} }
} // namespace llvm } // namespace llvm
PreservedAnalyses ModuleToFunctionPassAdaptor::run(Module &M,
ModuleAnalysisManager &AM) {
FunctionAnalysisManager &FAM =
AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
// Request PassInstrumentation from analysis manager, will use it to run
// instrumenting callbacks for the passes later.
PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
PreservedAnalyses PA = PreservedAnalyses::all();
for (Function &F : M) {
if (F.isDeclaration())
continue;
// Check the PassInstrumentation's BeforePass callbacks before running the
// pass, skip its execution completely if asked to (callback returns
// false).
if (!PI.runBeforePass<Function>(*Pass, F))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass->name(), F.getName());
PassPA = Pass->run(F, FAM);
}
PI.runAfterPass(*Pass, F, PassPA);
// We know that the function pass couldn't have invalidated any other
// function's analyses (that's the contract of a function pass), so
// directly handle the function analysis manager's invalidation here.
FAM.invalidate(F, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
PA.intersect(std::move(PassPA));
}
// The FunctionAnalysisManagerModuleProxy is preserved because (we assume)
// the function passes we ran didn't add or remove any functions.
//
// We also preserve all analyses on Functions, because we did all the
// invalidation we needed to do above.
PA.preserveSet<AllAnalysesOn<Function>>();
PA.preserve<FunctionAnalysisManagerModuleProxy>();
return PA;
}
AnalysisSetKey CFGAnalyses::SetKey; AnalysisSetKey CFGAnalyses::SetKey;
AnalysisSetKey PreservedAnalyses::AllAnalysesKey; AnalysisSetKey PreservedAnalyses::AllAnalysesKey;

llvm/lib/Transforms/Scalar/LoopPassManager.cpp

Show First 20 Lines • Show All 80 Lines • ▼ Show 20 LinesPassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
// be preserved, but unrolling should invalidate the parent loop's analyses. // be preserved, but unrolling should invalidate the parent loop's analyses.
PA.preserveSet<AllAnalysesOn<Loop>>(); PA.preserveSet<AllAnalysesOn<Loop>>();
if (DebugLogging) if (DebugLogging)
dbgs() << "Finished Loop pass manager run.\n"; dbgs() << "Finished Loop pass manager run.\n";
return PA; return PA;
} }
} }
dexonsmithUnsubmitted
Done
ReplyInline Actions

Can adding this comment be pulled out to a separate commit? It seems unrelated to this change.

dexonsmith: Can adding this comment be pulled out to a separate commit? It seems unrelated to this change.
aeubanksAuthorUnsubmitted
Done
ReplyInline Actions

this seems fairly benign to me, but sure

aeubanks: this seems fairly benign to me, but sure
dexonsmithUnsubmitted
Not Done
ReplyInline Actions

Thanks, I don't think it needs review or anything, but I had to stare at the diff for a while to see what had happened to the braces... if you commit unrelated comment / whitespace changes separately then later when people look at the log / blame / etc. it'll be a bit cleaner (in this chunk, the "new" brace will be the closing one for FunctionToLoopPassAdaptor::run instead of this one here)

dexonsmith: Thanks, I don't think it needs review or anything, but I had to stare at the diff for a while…
PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
FunctionAnalysisManager &AM) {
// Before we even compute any loop analyses, first run a miniature function
// pass pipeline to put loops into their canonical form. Note that we can
// directly build up function analyses after this as the function pass
// manager handles all the invalidation at that layer.
PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
PreservedAnalyses PA = PreservedAnalyses::all();
// Check the PassInstrumentation's BeforePass callbacks before running the
// canonicalization pipeline.
if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
PA = LoopCanonicalizationFPM.run(F, AM);
PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
}
// Get the loop structure for this function
LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
// If there are no loops, there is nothing to do here.
if (LI.empty())
return PA;
// Get the analysis results needed by loop passes.
MemorySSA *MSSA =
UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) : nullptr;
BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
? (&AM.getResult<BlockFrequencyAnalysis>(F))
: nullptr;
LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
AM.getResult<AssumptionAnalysis>(F),
AM.getResult<DominatorTreeAnalysis>(F),
AM.getResult<LoopAnalysis>(F),
AM.getResult<ScalarEvolutionAnalysis>(F),
AM.getResult<TargetLibraryAnalysis>(F),
AM.getResult<TargetIRAnalysis>(F),
BFI,
MSSA};
// Setup the loop analysis manager from its proxy. It is important that
// this is only done when there are loops to process and we have built the
// LoopStandardAnalysisResults object. The loop analyses cached in this
// manager have access to those analysis results and so it must invalidate
// itself when they go away.
auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
if (UseMemorySSA)
LAMFP.markMSSAUsed();
LoopAnalysisManager &LAM = LAMFP.getManager();
// A postorder worklist of loops to process.
SmallPriorityWorklist<Loop *, 4> Worklist;
// Register the worklist and loop analysis manager so that loop passes can
// update them when they mutate the loop nest structure.
LPMUpdater Updater(Worklist, LAM);
// Add the loop nests in the reverse order of LoopInfo. See method
// declaration.
appendLoopsToWorklist(LI, Worklist);
#ifndef NDEBUG
PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
if (isSpecialPass(PassID, {"PassManager"}))
return;
assert(any_isa<const Loop *>(IR));
const Loop *L = any_cast<const Loop *>(IR);
assert(L && "Loop should be valid for printing");
// Verify the loop structure and LCSSA form before visiting the loop.
L->verifyLoop();
assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
"Loops must remain in LCSSA form!");
});
#endif
do {
Loop *L = Worklist.pop_back_val();
// Reset the update structure for this loop.
Updater.CurrentL = L;
Updater.SkipCurrentLoop = false;
#ifndef NDEBUG
// Save a parent loop pointer for asserts.
Updater.ParentL = L->getParentLoop();
#endif
// Check the PassInstrumentation's BeforePass callbacks before running the
// pass, skip its execution completely if asked to (callback returns
// false).
if (!PI.runBeforePass<Loop>(*Pass, *L))
continue;
PreservedAnalyses PassPA;
{
TimeTraceScope TimeScope(Pass->name());
PassPA = Pass->run(*L, LAM, LAR, Updater);
}
// Do not pass deleted Loop into the instrumentation.
if (Updater.skipCurrentLoop())
PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
else
PI.runAfterPass<Loop>(*Pass, *L, PassPA);
// FIXME: We should verify the set of analyses relevant to Loop passes
// are preserved.
// If the loop hasn't been deleted, we need to handle invalidation here.
if (!Updater.skipCurrentLoop())
// We know that the loop pass couldn't have invalidated any other
// loop's analyses (that's the contract of a loop pass), so directly
// handle the loop analysis manager's invalidation here.
LAM.invalidate(*L, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
PA.intersect(std::move(PassPA));
} while (!Worklist.empty());
#ifndef NDEBUG
PI.popBeforeNonSkippedPassCallback();
#endif
// By definition we preserve the proxy. We also preserve all analyses on
// Loops. This precludes *any* invalidation of loop analyses by the proxy,
// but that's OK because we've taken care to invalidate analyses in the
// loop analysis manager incrementally above.
PA.preserveSet<AllAnalysesOn<Loop>>();
PA.preserve<LoopAnalysisManagerFunctionProxy>();
// We also preserve the set of standard analyses.
PA.preserve<DominatorTreeAnalysis>();
PA.preserve<LoopAnalysis>();
PA.preserve<ScalarEvolutionAnalysis>();
if (UseBlockFrequencyInfo && F.hasProfileData())
PA.preserve<BlockFrequencyAnalysis>();
if (UseMemorySSA)
PA.preserve<MemorySSAAnalysis>();
// FIXME: What we really want to do here is preserve an AA category, but
// that concept doesn't exist yet.
PA.preserve<AAManager>();
PA.preserve<BasicAA>();
PA.preserve<GlobalsAA>();
PA.preserve<SCEVAA>();
return PA;
}
PrintLoopPass::PrintLoopPass() : OS(dbgs()) {} PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner) PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
: OS(OS), Banner(Banner) {} : OS(OS), Banner(Banner) {}
PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &, PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &,
LoopStandardAnalysisResults &, LoopStandardAnalysisResults &,
LPMUpdater &) { LPMUpdater &) {
printLoop(L, OS, Banner); printLoop(L, OS, Banner);
return PreservedAnalyses::all(); return PreservedAnalyses::all();
} }

llvm/test/Other/change-printer.ll

Show First 20 Lines • Show All 60 Lines • ▼ Show 20 Lines
; CHECK-SIMPLE-NEXT: ; ModuleID = {{.+}} ; CHECK-SIMPLE-NEXT: ; ModuleID = {{.+}}
; CHECK-SIMPLE: *** IR Dump After VerifierPass (module) omitted because no change *** ; CHECK-SIMPLE: *** IR Dump After VerifierPass (module) omitted because no change ***
; CHECK-SIMPLE: *** IR Dump After InstSimplifyPass *** (function: g) ; CHECK-SIMPLE: *** IR Dump After InstSimplifyPass *** (function: g)
; CHECK-SIMPLE-NEXT: define i32 @g() ; CHECK-SIMPLE-NEXT: define i32 @g()
; CHECK-SIMPLE: *** IR Pass PassManager{{.*}} (function: g) ignored *** ; CHECK-SIMPLE: *** IR Pass PassManager{{.*}} (function: g) ignored ***
; CHECK-SIMPLE: *** IR Dump After InstSimplifyPass *** (function: f) ; CHECK-SIMPLE: *** IR Dump After InstSimplifyPass *** (function: f)
; CHECK-SIMPLE-NEXT: define i32 @f() ; CHECK-SIMPLE-NEXT: define i32 @f()
; CHECK-SIMPLE: *** IR Pass PassManager{{.*}} (function: f) ignored *** ; CHECK-SIMPLE: *** IR Pass PassManager{{.*}} (function: f) ignored ***
; CHECK-SIMPLE: *** IR Pass ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}> (module) ignored *** ; CHECK-SIMPLE: *** IR Pass ModuleToFunctionPassAdaptor (module) ignored ***
; CHECK-SIMPLE: *** IR Dump After VerifierPass (module) omitted because no change *** ; CHECK-SIMPLE: *** IR Dump After VerifierPass (module) omitted because no change ***
; CHECK-SIMPLE: *** IR Dump After PrintModulePass (module) omitted because no change *** ; CHECK-SIMPLE: *** IR Dump After PrintModulePass (module) omitted because no change ***
; CHECK-SIMPLE-NOT: *** IR ; CHECK-SIMPLE-NOT: *** IR
; CHECK-FUNC-FILTER: *** IR Dump At Start: *** ; CHECK-FUNC-FILTER: *** IR Dump At Start: ***
; CHECK-FUNC-FILTER-NEXT: ; ModuleID = {{.+}} ; CHECK-FUNC-FILTER-NEXT: ; ModuleID = {{.+}}
; CHECK-FUNC-FILTER: *** IR Dump After InstSimplifyPass (function: g) filtered out *** ; CHECK-FUNC-FILTER: *** IR Dump After InstSimplifyPass (function: g) filtered out ***
; CHECK-FUNC-FILTER: *** IR Dump After InstSimplifyPass *** (function: f) ; CHECK-FUNC-FILTER: *** IR Dump After InstSimplifyPass *** (function: f)
▲ Show 20 Lines • Show All 67 Lines • ▼ Show 20 Lines
; CHECK-SIMPLE-BEFORE: *** IR Dump After InstSimplifyPass *** (function: g) ; CHECK-SIMPLE-BEFORE: *** IR Dump After InstSimplifyPass *** (function: g)
; CHECK-SIMPLE-BEFORE-NEXT: define i32 @g() ; CHECK-SIMPLE-BEFORE-NEXT: define i32 @g()
; CHECK-SIMPLE-BEFORE: *** IR Pass PassManager{{.*}} (function: g) ignored *** ; CHECK-SIMPLE-BEFORE: *** IR Pass PassManager{{.*}} (function: g) ignored ***
; CHECK-SIMPLE-BEFORE: *** IR Dump Before InstSimplifyPass *** (function: f) ; CHECK-SIMPLE-BEFORE: *** IR Dump Before InstSimplifyPass *** (function: f)
; CHECK-SIMPLE-BEFORE-NEXT: define i32 @f() ; CHECK-SIMPLE-BEFORE-NEXT: define i32 @f()
; CHECK-SIMPLE-BEFORE: *** IR Dump After InstSimplifyPass *** (function: f) ; CHECK-SIMPLE-BEFORE: *** IR Dump After InstSimplifyPass *** (function: f)
; CHECK-SIMPLE-BEFORE-NEXT: define i32 @f() ; CHECK-SIMPLE-BEFORE-NEXT: define i32 @f()
; CHECK-SIMPLE-BEFORE: *** IR Pass PassManager{{.*}} (function: f) ignored *** ; CHECK-SIMPLE-BEFORE: *** IR Pass PassManager{{.*}} (function: f) ignored ***
; CHECK-SIMPLE-BEFORE: *** IR Pass ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}> (module) ignored *** ; CHECK-SIMPLE-BEFORE: *** IR Pass ModuleToFunctionPassAdaptor (module) ignored ***
; CHECK-SIMPLE-BEFORE: *** IR Dump After VerifierPass (module) omitted because no change *** ; CHECK-SIMPLE-BEFORE: *** IR Dump After VerifierPass (module) omitted because no change ***
; CHECK-SIMPLE-BEFORE: *** IR Dump After PrintModulePass (module) omitted because no change *** ; CHECK-SIMPLE-BEFORE: *** IR Dump After PrintModulePass (module) omitted because no change ***
; CHECK-SIMPLE-BEFORE-NOT: *** IR ; CHECK-SIMPLE-BEFORE-NOT: *** IR
; CHECK-FUNC-FILTER-BEFORE: *** IR Dump At Start: *** ; CHECK-FUNC-FILTER-BEFORE: *** IR Dump At Start: ***
; CHECK-FUNC-FILTER-BEFORE-NEXT: ; ModuleID = {{.+}} ; CHECK-FUNC-FILTER-BEFORE-NEXT: ; ModuleID = {{.+}}
; CHECK-FUNC-FILTER-BEFORE: *** IR Dump After InstSimplifyPass (function: g) filtered out *** ; CHECK-FUNC-FILTER-BEFORE: *** IR Dump After InstSimplifyPass (function: g) filtered out ***
; CHECK-FUNC-FILTER-BEFORE: *** IR Dump Before InstSimplifyPass *** (function: f) ; CHECK-FUNC-FILTER-BEFORE: *** IR Dump Before InstSimplifyPass *** (function: f)
Show All 14 Lines

llvm/test/Other/pass-pipeline-parsing.ll

Show First 20 Lines • Show All 155 Lines • ▼ Show 20 Lines
; CHECK-NESTED-FP-LP: Finished Loop pass manager run ; CHECK-NESTED-FP-LP: Finished Loop pass manager run
; CHECK-NESTED-FP-LP: Finished llvm::Function pass manager run ; CHECK-NESTED-FP-LP: Finished llvm::Function pass manager run
; CHECK-NESTED-FP-LP: Finished llvm::Module pass manager run ; CHECK-NESTED-FP-LP: Finished llvm::Module pass manager run
; RUN: opt -disable-output -debug-pass-manager -debug-pass-manager-verbose \ ; RUN: opt -disable-output -debug-pass-manager -debug-pass-manager-verbose \
; RUN: -passes='module(no-op-function,no-op-loop,no-op-cgscc,cgscc(no-op-function,no-op-loop),function(no-op-loop))' %s 2>&1 \ ; RUN: -passes='module(no-op-function,no-op-loop,no-op-cgscc,cgscc(no-op-function,no-op-loop),function(no-op-loop))' %s 2>&1 \
; RUN: | FileCheck %s --check-prefix=CHECK-ADAPTORS ; RUN: | FileCheck %s --check-prefix=CHECK-ADAPTORS
; CHECK-ADAPTORS: Starting llvm::Module pass manager run ; CHECK-ADAPTORS: Starting llvm::Module pass manager run
; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor<{{.*}}NoOpFunctionPass> ; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor
; CHECK-ADAPTORS: Running pass: NoOpFunctionPass ; CHECK-ADAPTORS: Running pass: NoOpFunctionPass
; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor<{{.*}}FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass>{{.*}}> ; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor
; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass> ; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor
; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop ; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop
; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}NoOpCGSCCPass> ; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor
; CHECK-ADAPTORS: Running pass: NoOpCGSCCPass ; CHECK-ADAPTORS: Running pass: NoOpCGSCCPass
; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}LazyCallGraph{{.*}}> ; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor
; CHECK-ADAPTORS: Starting CGSCC pass manager run ; CHECK-ADAPTORS: Starting CGSCC pass manager run
; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}NoOpFunctionPass> ; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor
; CHECK-ADAPTORS: Running pass: NoOpFunctionPass ; CHECK-ADAPTORS: Running pass: NoOpFunctionPass
; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass>{{.*}}> ; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor
; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass> ; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor
; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop ; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop
; CHECK-ADAPTORS: Finished CGSCC pass manager run ; CHECK-ADAPTORS: Finished CGSCC pass manager run
; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}> ; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor
; CHECK-ADAPTORS: Starting llvm::Function pass manager run ; CHECK-ADAPTORS: Starting llvm::Function pass manager run
; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass> ; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor
; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop ; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop
; CHECK-ADAPTORS: Finished llvm::Function pass manager run ; CHECK-ADAPTORS: Finished llvm::Function pass manager run
; CHECK-ADAPTORS: Finished llvm::Module pass manager run ; CHECK-ADAPTORS: Finished llvm::Module pass manager run
; RUN: opt -disable-output -debug-pass-manager \ ; RUN: opt -disable-output -debug-pass-manager \
; RUN: -passes='cgscc(print)' %s 2>&1 \ ; RUN: -passes='cgscc(print)' %s 2>&1 \
; RUN: | FileCheck %s --check-prefix=CHECK-PRINT-IN-CGSCC ; RUN: | FileCheck %s --check-prefix=CHECK-PRINT-IN-CGSCC
; CHECK-PRINT-IN-CGSCC: Starting llvm::Module pass manager run ; CHECK-PRINT-IN-CGSCC: Starting llvm::Module pass manager run
▲ Show 20 Lines • Show All 99 Lines • Show Last 20 Lines