Index: include/llvm/Analysis/CGSCCPassManager.h =================================================================== --- include/llvm/Analysis/CGSCCPassManager.h +++ include/llvm/Analysis/CGSCCPassManager.h @@ -89,7 +89,10 @@ #include "llvm/ADT/PriorityWorklist.h" #include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/InstIterator.h" #include "llvm/IR/PassManager.h" +#include "llvm/IR/ValueHandle.h" namespace llvm { @@ -453,6 +456,145 @@ return CGSCCToFunctionPassAdaptor(std::move(Pass), DebugLogging); } + +/// A helper that iterates an SCC pass each time an indirect call is refined to +/// a direct call. +/// +/// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they +/// change shape, we may also want to iterate an SCC pass if it simply refines +/// an indirect call to a direct call, even if doing so does not alter the +/// shape of the graph. +/// +/// This iteration has the potential to be very large however, as each +/// iteration might refine a single call site. As a consequence, in practice we +/// use a simple upper bound to limit things. +template +class DevirtIteratingWrapper + : public PassInfoMixin> { +public: + explicit DevirtIteratingWrapper(PassT Pass, int MaxIterations, + bool DebugLogging = false) + : Pass(std::move(Pass)), MaxIterations(MaxIterations), + DebugLogging(DebugLogging) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + DevirtIteratingWrapper(const DevirtIteratingWrapper &Arg) + : Pass(Arg.Pass), MaxIterations(Arg.MaxIterations), + DebugLogging(Arg.DebugLogging) {} + DevirtIteratingWrapper(DevirtIteratingWrapper &&Arg) + : Pass(std::move(Arg.Pass)), MaxIterations(Arg.MaxIterations), + DebugLogging(Arg.DebugLogging) {} + friend void swap(DevirtIteratingWrapper &LHS, + DevirtIteratingWrapper &RHS) { + using std::swap; + swap(LHS.Pass, RHS.Pass); + swap(LHS.MaxIterations, RHS.MaxIterations); + swap(LHS.DebugLogging, RHS.DebugLogging); + } + DevirtIteratingWrapper &operator=(DevirtIteratingWrapper RHS) { + swap(*this, RHS); + return *this; + } + + /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating + /// whenever an indirect call is refined. + PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR) { + PreservedAnalyses PA = PreservedAnalyses::all(); + + // 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; + + // Collect value handles for all of the indirect call sites. + SmallVector CallHandles; + SmallPtrSet CallSet; + + for (int Iterations = 1;; ++Iterations) { + // Collect handles for all indirect calls in the SCC. + assert(CallHandles.empty() && "Must start with a clear set of handles."); + for (LazyCallGraph::Node &N : *C) { + CallSet.clear(); + for (Instruction &I : instructions(N.getFunction())) + if (auto CS = CallSite(&I)) + if (!CS.getCalledFunction()) + if (CallSet.insert(&I).second) + CallHandles.push_back(WeakVH(&I)); + } + + PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR); + + // Update the SCC if necessary. + C = UR.UpdatedC ? UR.UpdatedC : C; + + // 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!"); + + // Update the analysis manager with each iteration and intersect the + // total set of preserved analyses. + PassPA = AM.invalidate(*C, std::move(PassPA)); + PA.intersect(std::move(PassPA)); + + + // Check whether any of the handles were devirtualized. + bool Devirt = false; + for (WeakVH &CallH : CallHandles) { + if (!CallH) + continue; + auto CS = CallSite(CallH); + if (!CS) + continue; + + // If the call is still indirect, leave it alone. + Function *F = CS.getCalledFunction(); + if (!F) + continue; + + // Otherwise, we no longer track it, but if it is + // not an intrinsic, we've actually devirtualized + // something. + if (!F->isIntrinsic()) { + Devirt = true; + break; + } + } + CallHandles.clear(); + // If nothing got devirtualized, we're done. + if (!Devirt) + break; + // Otherwise, if we've already hit our max, we're done. + if (Iterations >= MaxIterations) { + if (DebugLogging) + dbgs() << "Found another devirtualization after hitting the max " + "number of iterations (" + << MaxIterations << ") on SCC: " << *C << "\n"; + break; + } + + if (DebugLogging) + dbgs() << "Iterating an SCC pass after finding a devirtualization in: " + << *C << "\n"; + } + + return PA; + } + +private: + PassT Pass; + int MaxIterations; + bool DebugLogging; +}; + +/// \brief A function to deduce a function pass type and wrap it in the +/// templated adaptor. +template +DevirtIteratingWrapper +createDevirtIteratingWrapper(PassT Pass, int MaxIterations, + bool DebugLogging = false) { + return DevirtIteratingWrapper(std::move(Pass), MaxIterations, + DebugLogging); +} } #endif Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -284,6 +284,15 @@ return Count; } +static Optional parseDevirtPassName(StringRef Name) { + if (!Name.consume_front("devirt<") || !Name.consume_back(">")) + return None; + int Count; + if (Name.getAsInteger(0, Count) || Count <= 0) + return None; + return Count; +} + static bool isModulePassName(StringRef Name) { // Manually handle aliases for pre-configured pipeline fragments. if (Name.startswith("default") || Name.startswith("lto")) @@ -322,6 +331,8 @@ // Explicitly handle custom-parsed pass names. if (parseRepeatPassName(Name)) return true; + if (parseDevirtPassName(Name)) + return true; #define CGSCC_PASS(NAME, CREATE_PASS) \ if (Name == NAME) \ @@ -562,6 +573,15 @@ CGPM.addPass(createRepeatingPassWrapper(*Count, std::move(NestedCGPM))); return true; } + if (auto MaxIterations = parseDevirtPassName(Name)) { + CGSCCPassManager NestedCGPM(DebugLogging); + if (!parseCGSCCPassPipeline(NestedCGPM, InnerPipeline, VerifyEachPass, + DebugLogging)) + return false; + CGPM.addPass(createDevirtIteratingWrapper(std::move(NestedCGPM), + *MaxIterations, DebugLogging)); + return true; + } // Normal passes can't have pipelines. return false; } Index: test/Other/cgscc-observe-devirt.ll =================================================================== --- test/Other/cgscc-observe-devirt.ll +++ test/Other/cgscc-observe-devirt.ll @@ -1,9 +1,5 @@ ; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs)' -S < %s | FileCheck %s --check-prefix=BEFORE -; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(gvn))' -S < %s | FileCheck %s --check-prefix=AFTER -; -; Also check that adding an extra CGSCC pass after the function update but -; without requiring the outer manager to iterate doesn't break any invariant. -; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(gvn),function-attrs)' -S < %s | FileCheck %s --check-prefix=AFTER2 +; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(devirt<4>(function-attrs,function(gvn)))' -S < %s | FileCheck %s --check-prefix=AFTER declare void @readnone() readnone declare void @unknown() @@ -11,12 +7,9 @@ ; The @test1_* functions check that when we refine an indirect call to a direct ; call, even if it doesn't change the call graph structure, we revisit the SCC ; passes to reflect the more precise information. -; FIXME: Currently, this isn't implemented in the new pass manager and so we -; only get this with AFTER2, not with AFTER. ; BEFORE: define void @test1_a() { ; AFTER: define void @test1_a() { -; AFTER2: define void @test1_a() { define void @test1_a() { %fptr = alloca void()* store void()* @unknown, void()** %fptr @@ -26,8 +19,7 @@ } ; BEFORE: define void @test1_b() { -; AFTER: define void @test1_b() { -; AFTER2: define void @test1_b() #0 { +; AFTER: define void @test1_b() #0 { define void @test1_b() { %fptr = alloca void()* store void()* @readnone, void()** %fptr @@ -42,7 +34,6 @@ ; BEFORE: define void @test2_a1() { ; AFTER: define void @test2_a1() { -; AFTER2: define void @test2_a1() { define void @test2_a1() { %fptr = alloca void()* store void()* @test2_b2, void()** %fptr @@ -54,7 +45,6 @@ ; BEFORE: define void @test2_b1() { ; AFTER: define void @test2_b1() { -; AFTER2: define void @test2_b1() { define void @test2_b1() { call void @unknown() call void @test2_a1() @@ -63,7 +53,6 @@ ; BEFORE: define void @test2_a2() { ; AFTER: define void @test2_a2() #0 { -; AFTER2: define void @test2_a2() #0 { define void @test2_a2() { %fptr = alloca void()* store void()* @test2_b1, void()** %fptr @@ -75,7 +64,6 @@ ; BEFORE: define void @test2_b2() { ; AFTER: define void @test2_b2() #0 { -; AFTER2: define void @test2_b2() #0 { define void @test2_b2() { call void @readnone() call void @test2_a2()