diff --git a/llvm/include/llvm/Analysis/InlineAdvisor.h b/llvm/include/llvm/Analysis/InlineAdvisor.h --- a/llvm/include/llvm/Analysis/InlineAdvisor.h +++ b/llvm/include/llvm/Analysis/InlineAdvisor.h @@ -181,7 +181,7 @@ /// This must be called when the Inliner pass is entered, to allow the /// InlineAdvisor update internal state, as result of function passes run /// between Inliner pass runs (for the same module). - virtual void onPassEntry() {} + virtual void onPassEntry(LazyCallGraph::SCC *SCC = nullptr) {} /// This must be called when the Inliner pass is exited, as function passes /// may be run subsequently. This allows an implementation of InlineAdvisor diff --git a/llvm/include/llvm/Analysis/MLInlineAdvisor.h b/llvm/include/llvm/Analysis/MLInlineAdvisor.h --- a/llvm/include/llvm/Analysis/MLInlineAdvisor.h +++ b/llvm/include/llvm/Analysis/MLInlineAdvisor.h @@ -31,7 +31,7 @@ virtual ~MLInlineAdvisor() = default; - void onPassEntry() override; + void onPassEntry(LazyCallGraph::SCC *SCC) override; void onPassExit(LazyCallGraph::SCC *SCC) override; int64_t getIRSize(Function &F) const { @@ -79,7 +79,7 @@ std::map FunctionLevels; const int32_t InitialIRSize = 0; int32_t CurrentIRSize = 0; - std::deque NodesInLastSCC; + llvm::SmallPtrSet NodesInLastSCC; DenseSet AllNodes; bool ForceStop = false; }; diff --git a/llvm/lib/Analysis/MLInlineAdvisor.cpp b/llvm/lib/Analysis/MLInlineAdvisor.cpp --- a/llvm/lib/Analysis/MLInlineAdvisor.cpp +++ b/llvm/lib/Analysis/MLInlineAdvisor.cpp @@ -139,8 +139,8 @@ return CG.lookup(F) ? FunctionLevels.at(CG.lookup(F)) : 0; } -void MLInlineAdvisor::onPassEntry() { - if (ForceStop) +void MLInlineAdvisor::onPassEntry(LazyCallGraph::SCC *LastSCC) { + if (!LastSCC || ForceStop) return; FPICache.clear(); // Function passes executed between InlinerPass runs may have changed the @@ -158,8 +158,8 @@ // care about the nature of the Edge (call or ref). NodeCount -= static_cast(NodesInLastSCC.size()); while (!NodesInLastSCC.empty()) { - const auto *N = NodesInLastSCC.front(); - NodesInLastSCC.pop_front(); + const auto *N = *NodesInLastSCC.begin(); + NodesInLastSCC.erase(N); // The Function wrapped by N could have been deleted since we last saw it. if (N->isDead()) { assert(!N->getFunction().isDeclaration()); @@ -172,12 +172,18 @@ assert(!AdjNode->isDead() && !AdjNode->getFunction().isDeclaration()); auto I = AllNodes.insert(AdjNode); if (I.second) - NodesInLastSCC.push_back(AdjNode); + NodesInLastSCC.insert(AdjNode); } } EdgeCount -= EdgesOfLastSeenNodes; EdgesOfLastSeenNodes = 0; + + // (Re)use NodesInLastSCC to remember the nodes in the SCC right now, + // in case the SCC is split before onPassExit and some nodes are split out + assert(NodesInLastSCC.empty()); + for (const auto &N : *LastSCC) + NodesInLastSCC.insert(&N); } void MLInlineAdvisor::onPassExit(LazyCallGraph::SCC *LastSCC) { @@ -189,14 +195,24 @@ // Keep track of the nodes and edges we last saw. Then, in onPassEntry, // we update the node count and edge count from the subset of these nodes that // survived. - assert(NodesInLastSCC.empty()); - assert(NodeCount >= LastSCC->size()); EdgesOfLastSeenNodes = 0; + + // Check on nodes that were in SCC onPassEntry + for (auto I = NodesInLastSCC.begin(); I != NodesInLastSCC.end();) { + if ((*I)->isDead()) + NodesInLastSCC.erase(*I++); + else + EdgesOfLastSeenNodes += getLocalCalls((*I++)->getFunction()); + } + + // Check on nodes that may have got added to SCC for (const auto &N : *LastSCC) { assert(!N.isDead()); - EdgesOfLastSeenNodes += getLocalCalls(N.getFunction()); - NodesInLastSCC.push_back(&N); + auto I = NodesInLastSCC.insert(&N); + if (I.second) + EdgesOfLastSeenNodes += getLocalCalls(N.getFunction()); } + assert(NodeCount >= NodesInLastSCC.size()); assert(EdgeCount >= EdgesOfLastSeenNodes); } @@ -380,7 +396,7 @@ void MLInlineAdvisor::print(raw_ostream &OS) const { OS << "[MLInlineAdvisor] Nodes: " << NodeCount << " Edges: " << EdgeCount - << "\n"; + << " EdgesOfLastSeenNodes: " << EdgesOfLastSeenNodes << "\n"; OS << "[MLInlineAdvisor] FPI:\n"; for (auto I : FPICache) { OS << I.getFirst()->getName() << ":\n"; diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -67,6 +67,7 @@ MODULE_PASS("hotcoldsplit", HotColdSplittingPass()) MODULE_PASS("inferattrs", InferFunctionAttrsPass()) MODULE_PASS("inliner-wrapper", ModuleInlinerWrapperPass()) +MODULE_PASS("inliner-ml-advisor-release", ModuleInlinerWrapperPass(getInlineParams(), true, InliningAdvisorMode::Release, 0)) MODULE_PASS("print", InlineAdvisorAnalysisPrinterPass(dbgs())) MODULE_PASS("inliner-wrapper-no-mandatory-first", ModuleInlinerWrapperPass( getInlineParams(), diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp --- a/llvm/lib/Transforms/IPO/Inliner.cpp +++ b/llvm/lib/Transforms/IPO/Inliner.cpp @@ -753,7 +753,7 @@ .getManager(); InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M); - Advisor.onPassEntry(); + Advisor.onPassEntry(&InitialC); auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(&InitialC); }); diff --git a/llvm/test/Transforms/Inline/ML/scc-dead-accounting.ll b/llvm/test/Transforms/Inline/ML/scc-dead-accounting.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/Inline/ML/scc-dead-accounting.ll @@ -0,0 +1,73 @@ +; MRE for SCC splitting causing MLInlineAdvisor to lose track of edges +; foo and bar both call inlineme; inlineme calls only foo and bar +; when the foo-bar-inlineme SCC reaches the inliner, foo-bar will be split out +; leaving inlineme in the SCC. inlineme is dead, so it gets removed from the SCC +; However, MLInlineAdvisor should still track the edges of foo and bar onPassExit +; as the foo-bar SCC will be passed on to the next SCC pass in the pipeline +; and as a result could gain/lose edges before the inliner sees it again + +; In this example if loop-unroll is ran after a mandatory inlining CGSCC pass, +; edges would increase but wouldn't be tracked + +; REQUIRES: llvm_inliner_model_autogenerated + +; RUN: opt -enable-ml-inliner=release -passes=inliner-ml-advisor-release \ +; RUN: -keep-inline-advisor-for-printing \ +; RUN: -enable-scc-inline-advisor-printing -S < %s 2>&1 | FileCheck %s + +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define internal void @_Z8inlinemei() inlinehint alwaysinline { +entry: + %call2 = call noundef i32 @_Z3bari(i32 noundef 12321) + %call3 = call noundef i32 @_Z3fooi(i32 noundef 12321) + ret void +} + +define dso_local noundef i32 @_Z3bari(i32 noundef %y) { +entry: + call void @_Z8inlinemei() + ret i32 %y +} + +define dso_local noundef i32 @main(i32 noundef %argc, ptr noundef %argv) { +entry: + %call = call noundef i32 @_Z3fooi(i32 noundef %argc) + ret i32 %call +} + +define dso_local noundef i32 @_Z3fooi(i32 noundef %z) { +entry: + %a = alloca i32, align 4 + br label %for.body + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4 + %inc = add nsw i32 %0, 1 + store i32 %inc, i32* %arrayidx, align 4 + call void @_Z8inlinemei() + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 10 + br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !5 + +for.end: + ret i32 %z +} + +!llvm.module.flags = !{!0, !1, !2, !3, !4} + +!0 = !{i32 1, !"wchar_size", i32 4} +!1 = !{i32 7, !"PIC Level", i32 2} +!2 = !{i32 7, !"PIE Level", i32 2} +!3 = !{i32 7, !"uwtable", i32 2} +!4 = !{i32 7, !"frame-pointer", i32 2} +!5 = !{!5, !{!"llvm.loop.disable_nonforced"}, !{!"llvm.loop.unroll.enable"}} + +; CHECK: [MLInlineAdvisor] Nodes: 3 Edges: 5 EdgesOfLastSeenNodes: 4 +; CHECK: [MLInlineAdvisor] Nodes: 3 Edges: 5 EdgesOfLastSeenNodes: 4 +; CHECK: [MLInlineAdvisor] Nodes: 3 Edges: 5 EdgesOfLastSeenNodes: 4 +; CHECK: [MLInlineAdvisor] Nodes: 3 Edges: 5 EdgesOfLastSeenNodes: 4 +; CHECK: [MLInlineAdvisor] Nodes: 3 Edges: 5 EdgesOfLastSeenNodes: 1