[InlineAdvisor] Allow replay of inline decisions for the CGSCC inliner from optimization remarks

[modimo]

Summary

This change leverages the work done in D83743 to replay in the SampleProfile inliner to also be used in the CGSCC inliner. NOTE: currently restricted to non-ML advisors only.

The added switch -cgscc-inline-replay=<remarks file> will replay the inlining decisions in that file where the remarks file is generated via -Rpass=inline. The aim here is to make it easier to analyze changes that would modify inlining heuristics to be separated from this behavior. Doing so allows easier examination of assembly and runtime behavior compared to the baseline rather than trying to dig through the large churn caused by inlining.

In LTO compilation, since inlining is done twice you can separately specify replay by passing the flag to the FE (-cgscc-inline-replay=) and to the linker (-Wl,cgscc-inline-replay=) with the remarks generated from their respective places.

Testing on mysqld by comparing the inline decisions between base (generates remarks.txt) and diff (replay using identical input/tools with remarks.txt) and examining the inlining sites with diff shows 14,000 mismatches out of 247,341 for a ~94% replay accuracy. I believe this gap can be narrowed further though for the general case we may never achieve full accuracy. For my personal use, this is close enough to be representative: I set the baseline as the one generated by the replay on identical input/toolset and compare that to my modified input/toolset using the same replay.

Testing:
ninja check-llvm
newly added test correctly replays CGSCC inlining decisions

[wenlei]

llvm/lib/Analysis/ReplayInlineAdvisor.cpp

58 ↗

(On Diff #315490)

This looks redundant/similar to DefaultInlineAdvice, is that just for controlling EmitRemarks? ORE should be able to handle remark printing (or not) correctly without extra guard.

[mtrofin]

llvm/lib/Analysis/ReplayInlineAdvisor.cpp

58 ↗

(On Diff #315490)

Along the same lines as @wenlei 's comment - if the Advisor can both generate and digest the trace of decisions, why rely on ORE and not, instead, use a more structured format that wouldn't need parsing like ReplayInlineAdvisor.cpp:43?

Also (if using ORE is desirable, case in which I share @wenlei's question), I think there's a yaml output format ORE generates, perhaps requiring that as input would also simplify ingestion?

[modimo]

Move the ReplayInlineAdvisor.cpp/h and SampleProfile.cpp files to D94333 as they need to be atomic with the remarks format change.

[modimo]

llvm/lib/Analysis/ReplayInlineAdvisor.cpp

58 ↗

(On Diff #315490)

I've moved this section to D94333 since the replay mechanism change to consume the new line:col.discriminator format needed to be together with format change. I've folded ReplayInlineAdvice back into DefaultInlineAdvice with the additional features I need. The extra guard is needed because the SampleProfile inliner uses the "legacy PM" mechanism of inline printing rather than bundling it with InlineAdvice calls. Since the use of InlineAdvice in SampleProfile is purely to support replay right now I'm leaving that refactoring (if we want to go after it) for the future.

As far as using yaml I like how condensed the format is in remarks form. Something that's a single line in remarks ends up as 24 lines (like in llvm/test/Transforms/Inline/optimization-remarks-passed-yaml.ll) which makes manual reading and modification tedious especially on larger binaries. The current text processing is also fairly simple as is which makes a change here less pressing.

That being said I'm not against using the yaml file as the official/supported format. A nice advantage there is that if we wanted to add more replay data (say negative inline decisions) it'll be smoother in yaml than adding new parsing of the text remark.

[wenlei]

llvm/lib/Transforms/IPO/Inliner.cpp

669

Plug in replay inline advisor here isn't extensible. In the future we want to be able to use inline replay only for a specific function, or enforce/prevent certain inlining at particular callsite, and fall back to regular advisor for the rest (see comments in D83743).

That means we would need to be able to fall back from replay advisor to default advisor (or whatever main advisor being used) when replay advisor doesn't have info. For that cascaded model, we would need inline advise to have something like hasInlineRecommendation in addition to isInliningRecommended. We should probably still record inlining on each advice, but don't want to emit duplicated remarks from each advice. These changes can come later, but current change better offer that flexibility - we don't to stick to replay advisor for the entire module inliner pass.

llvm/test/Transforms/Inline/cgscc-inline-replay.ll

4

Better verify inline decision without replay first, to make sure the replay has visible impact on inlining. See DEFAULT and REPLAY check for SampleProfile/inline-replay.ll.

[modimo]

llvm/lib/Transforms/IPO/Inliner.cpp

669

I think your suggested change is to initialize both Advisors and allow fallback if we defer on one. With how the current scheme is setup up though advisors are single entities and we only ask it once:
auto Advice = Advisor.getAdvice(*CB);
A proven approach to doing something like this is with alias analysis where we query AA in a specific order until we hit a real recommendation. That would cause a rehaul of this function rather than a small tweak so I don't see a good intermediate step to take for this patch. Let me know if you think there's something to do here now for it.

llvm/test/Transforms/Inline/cgscc-inline-replay.ll

4

Makes sense, added.

[modimo]

Add DEFAULT testing to make sure baseline inlining differs from replay. Fix copy-paste error in flag description for -cgscc-inline-replay

[modimo]

llvm/lib/Analysis/ReplayInlineAdvisor.cpp

58 ↗

(On Diff #315490)

Along the same lines as @wenlei 's comment - if the Advisor can both generate and digest the trace of decisions, why rely on ORE and not, instead, use a more structured format that wouldn't need parsing like ReplayInlineAdvisor.cpp:43?

@mtrofin I very much agree on this point. Personal front-runners for me is a CSV file which gives you line density but makes parsing easy or a tree format based on what @wenlei shows in D82213:

Inlinees for main
[P]  _ZN15largesolidarrayIP6regobjEixEi @ 369
[P]  _Z7random1i @ 363
[C]    _Z8myrandomv @ 2
[P]  _Z7random1i @ 364
[C]    _Z8myrandomv @ 2
[P]  _ZN15largesolidarrayIP6regobjEixEi @ 366
[P]  _ZN6wayobj9createwayEiiiiRP8point16tRi @ 327
[P]    _ZN6wayobj11createwayarEiiRP8point16tRi @ 37.1
[P]      _ZN6wayobj5indexEii @ 143
[P]      _ZN6wayobj5indexEii @ 130
[P]      _ZN6wayobj6indexxEi @ 31
[P]      _ZN6wayobj6indexyEi @ 32
[C]      _ZN8point16tC2Ess @ 2
[C]      _ZN8point16tC2Ess @ 2.1

I do want to see what users think about the current flow that's currently the same between CGSCC and sample inliner because there's definitely more refinements (additional replay accuracy, more logging, global allow-list/block-list etc.) that can be pursued but which I don't have a sense of value/priority for. I'm hoping that'll give us more information on what path to pursue here.

[wenlei]

llvm/lib/Transforms/IPO/Inliner.cpp

669

Well, we don't have to have everything setup for the cascaded query like how AA works, but something more flexible than having entire inliner sticking to one advisor would be good (and does not seem like a significant change)

What I was thinking about is that the main advisor can still go through getAdvisor interface, then for inline replay, we can just let ModuleInlinerWrapperPass own an ExternalInlineAdvisor just like how SampleProfileLoader owns one. Then it can be passed to InlinerPass and serve as a short-circuit look up or side look up when available in addition to the main advisor from getAdvisor.

The changes to add hasInlineRecommendation etc are not what I'm suggesting for this patch though I don't think these are significant either. It can evolve into cascaded advice support in the framework if needed, but if replay inline advice is the only case needing that support, generalizing it doesn't not seem like a must do.

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

669

+1 to what @wenlei said - you can wrap advisors in advisors, basically. There may be some helper utilities that we may need factored in InlineAdvisor, and I was at a point thinking of doing that, but the motivating scenario at the time ended up not really needing that. If this turns out to be that scenario, I'd be happy to help!

[modimo]

Wrap ReplayInlineAdvisor into InlineAdvisor so that we can fall back to the original Advisor if we don't want to follow the replay. I think the composition of advisors here makes sense but I'm not sure so I'm very open to different approaches.

[wenlei]

llvm/include/llvm/Analysis/InlineAdvisor.h

201 ↗

(On Diff #318339)

By adding a ReplayAdvisor field into every InlineAdvisor, we're allowing advisors to be chained. It'd be weird if a replay advisor itself has a non-empty replay advisor though the current implementation doesn't prohibit that. However if we change the names to be like a fall back advisor, and let replay advisor be just a use case of the fall back chain, I think that would be more reasonable.

[mtrofin]

llvm/include/llvm/Analysis/InlineAdvisor.h

201 ↗

(On Diff #318339)

Instead of all advisors knowing about replay, why not doing it vice-versa: Replay wraps other advisors. Then, in InlineAdvisorAnalysis::Result::tryCreate (in InlineAdvisor.cpp), you see if replaying is requested, and build the ReplayInlineAdvisor wrapping the advisor requested initially - something like adding, right before return:

if (ReplayRequired)

Advisor = std::make_unique<ReplayInlineAdvisor>(<params>, std::move(Advisor))

I believe this keeps the concerns (replaying vs regular advising) separated, while also allowing future usecases where the the replay advisor can delegate to some other advisor, generically.

Note: I think you'd also need to have a ReplayInlineAdvice wrapping the InlineAdvice coming from the contained InlineAdvisor.

[modimo]

Nest original advisors in ReplayInlineAdvisor rather than the other way around.

[mtrofin]

Nice! LGTM (assuming comment in tryCreate is addressed)

llvm/lib/Analysis/InlineAdvisor.cpp

186 ↗

(On Diff #318639)

Probably best to check first if Advisor isn't null before line 180, then not bother making a replay advisor if the underlying one can't be made in the first place (and just return false)

[modimo]

llvm/include/llvm/Analysis/InlineAdvisor.h

201 ↗

(On Diff #318339)

However if we change the names to be like a fall back advisor, and let replay advisor be just a use case of the fall back chain, I think that would be more reasonable.

Fall back would be better wording for it, agreed.

Instead of all advisors knowing about replay, why not doing it vice-versa: Replay wraps other advisors.

I like it, knowing about tryCreate makes it easier than I first thought given it's a centralizing creation point where we can wrap.

Note: I think you'd also need to have a ReplayInlineAdvice wrapping the InlineAdvice coming from the contained InlineAdvisor.

Can you elaborate on what would go into ReplayInlineAdvice? My thinking is that if the ReplayInlineAdvisor::getAdviceImpl declines to offer advice then we go to OriginalAdvisor->getAdvice(CB) so wrapping doesn't seem needed.

[mtrofin]

llvm/include/llvm/Analysis/InlineAdvisor.h

201 ↗

(On Diff #318339)

TL;DR; right now it's probably fine.

Longer story: the ML advisors are stateful - they track module-wide changes. So *if* we wanted to combine replaying with one of those, then the replayer would always have to get an advice from the underlying advisor, so it'd be able to notify back through it on what actually happened.

But the motivation for that scenario is kind of tenuous, I think, and it'd complicate the design unnecessarily. May be better to just disallow replaying with anything else other than the default advisor and we can add there a comment as to why.

[modimo]

Restrict replay to default advisor only

[wenlei]

Looks great, thanks!

llvm/include/llvm/Transforms/IPO/Inliner.h

 //===- Inliner.h - Inliner pass and infrastructure --------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_INLINER_H
 #define LLVM_TRANSFORMS_IPO_INLINER_H
 
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/InlineAdvisor.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/Analysis/ReplayInlineAdvisor.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
 #include <utility>
 
 namespace llvm {
 
 class AssumptionCacheTracker;
 class CallGraph;
public:
   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                         LazyCallGraph &CG, CGSCCUpdateResult &UR);
 
 private:
   InlineAdvisor &getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM,
                             FunctionAnalysisManager &FAM, Module &M);
   std::unique_ptr<ImportedFunctionsInliningStatistics> ImportedFunctionsStats;
   Optional<DefaultInlineAdvisor> OwnedDefaultAdvisor;
+  // External inline advisor used to replay inline decision from remarks.
+  Optional<ReplayInlineAdvisor> ReplayAdvisor;
 };
 
 /// Module pass, wrapping the inliner pass. This works in conjunction with the
 /// InlineAdvisorAnalysis to facilitate inlining decisions taking into account
 /// module-wide state, that need to keep track of inter-inliner pass runs, for
 /// a given module. An InlineAdvisor is configured and kept alive for the
 /// duration of the ModuleInlinerWrapperPass::run.
 class ModuleInlinerWrapperPass

llvm/lib/Transforms/IPO/Inliner.cpp

 /// prior to LLVM's code generator having support for stack coloring based on
 /// lifetime markers. It is now in the process of being removed. To experiment
 /// with disabling it and relying fully on lifetime marker based stack
 /// coloring, you can pass this flag to LLVM.
 static cl::opt<bool>
     DisableInlinedAllocaMerging("disable-inlined-alloca-merging",
                                 cl::init(false), cl::Hidden);
 
+static cl::opt<std::string> CGSCCInlineReplayFile(
+    "cgscc-inline-replay", cl::init(""), cl::value_desc("filename"),
+    cl::desc(
+        "Optimization remarks file containing inline remarks to be replayed "
+        "by inlining from sample profile loader."),
+    cl::Hidden);
+
 namespace {
 
 enum class InlinerFunctionImportStatsOpts {
   No = 0,
   Basic = 1,
   Verbose = 2,
 };
 
if (ImportedFunctionsStats) {
     ImportedFunctionsStats->dump(InlinerFunctionImportStats ==
                                  InlinerFunctionImportStatsOpts::Verbose);
   }
 }
 
 InlineAdvisor &
 InlinerPass::getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM,
                         FunctionAnalysisManager &FAM, Module &M) {
+
+  if (!CGSCCInlineReplayFile.empty()) {
+    if (!ReplayAdvisor)
+      ReplayAdvisor.emplace(FAM, M.getContext(), CGSCCInlineReplayFile,
+                            /* EmitRemarks =*/true);
+
+    return *ReplayAdvisor;
+  }
+
   auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M);
   if (!IAA) {
     // It should still be possible to run the inliner as a stand-alone SCC pass,
     // for test scenarios. In that case, we default to the
     // DefaultInlineAdvisor, which doesn't need to keep state between SCC pass
     // runs. It also uses just the default InlineParams.
     // In this case, we need to use the provided FAM, which is valid for the
     // duration of the inliner pass, and thus the lifetime of the owned advisor.

llvm/test/Transforms/Inline/Inputs/cgscc-inline-replay.txt

+remark: calls.cc:10:0: _Z3sumii inlined into main with (cost=45, threshold=337) at callsite main:3:0.1;
+remark: calls.cc:4:0: _Z3subii inlined into main with (cost=-5, threshold=337) at callsite _Z3sumii:1:0 @ main:3:0.1;

llvm/test/Transforms/Inline/cgscc-inline-replay.ll

+;; Note that this needs new pass manager for now. Passing `-cgscc-inline-replay` to legacy pass manager is a no-op.
+
+;; Check replay inline decisions
+; RUN: opt < %s -passes=inline -cgscc-inline-replay=%S/Inputs/cgscc-inline-replay.txt -pass-remarks=inline -S 2>&1 | FileCheck -check-prefix=REPLAY %s
+
+@.str = private unnamed_addr constant [11 x i8] c"sum is %d\0A\00", align 1
+
+define i32 @_Z3sumii(i32 %x, i32 %y) #0 !dbg !6 {
+entry:
+  %x.addr = alloca i32, align 4
+  %y.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  store i32 %y, i32* %y.addr, align 4
+  %tmp = load i32, i32* %x.addr, align 4, !dbg !8
+  %tmp1 = load i32, i32* %y.addr, align 4, !dbg !8
+  %add = add nsw i32 %tmp, %tmp1, !dbg !8
+  %tmp2 = load i32, i32* %x.addr, align 4, !dbg !8
+  %tmp3 = load i32, i32* %y.addr, align 4, !dbg !8
+  %call = call i32 @_Z3subii(i32 %tmp2, i32 %tmp3), !dbg !8
+  ret i32 %add, !dbg !8
+}
+
+define i32 @_Z3subii(i32 %x, i32 %y) #0 !dbg !9 {
+entry:
+  %x.addr = alloca i32, align 4
+  %y.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  store i32 %y, i32* %y.addr, align 4
+  %tmp = load i32, i32* %x.addr, align 4, !dbg !10
+  %tmp1 = load i32, i32* %y.addr, align 4, !dbg !10
+  %add = sub nsw i32 %tmp, %tmp1, !dbg !10
+  ret i32 %add, !dbg !11
+}
+
+define i32 @main() #0 !dbg !12 {
+entry:
+  %retval = alloca i32, align 4
+  %s = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32 0, i32* %retval
+  store i32 0, i32* %i, align 4, !dbg !13
+  br label %while.cond, !dbg !14
+
+while.cond:                                       ; preds = %if.end, %entry
+  %tmp = load i32, i32* %i, align 4, !dbg !15
+  %inc = add nsw i32 %tmp, 1, !dbg !15
+  store i32 %inc, i32* %i, align 4, !dbg !15
+  %cmp = icmp slt i32 %tmp, 400000000, !dbg !15
+  br i1 %cmp, label %while.body, label %while.end, !dbg !15
+
+while.body:                                       ; preds = %while.cond
+  %tmp1 = load i32, i32* %i, align 4, !dbg !17
+  %cmp1 = icmp ne i32 %tmp1, 100, !dbg !17
+  br i1 %cmp1, label %if.then, label %if.else, !dbg !17
+
+if.then:                                          ; preds = %while.body
+  %tmp2 = load i32, i32* %i, align 4, !dbg !19
+  %tmp3 = load i32, i32* %s, align 4, !dbg !19
+  %call = call i32 @_Z3sumii(i32 %tmp2, i32 %tmp3), !dbg !19
+  store i32 %call, i32* %s, align 4, !dbg !19
+  br label %if.end, !dbg !19
+
+if.else:                                          ; preds = %while.body
+  store i32 30, i32* %s, align 4, !dbg !21
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %while.cond, !dbg !23
+
+while.end:                                        ; preds = %while.cond
+  %tmp4 = load i32, i32* %s, align 4, !dbg !25
+  %call2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str, i32 0, i32 0), i32 %tmp4), !dbg !25
+  ret i32 0, !dbg !26
+}
+
+declare i32 @printf(i8*, ...)
+
+attributes #0 = { "use-sample-profile" }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.5 ", isOptimized: false, runtimeVersion: 0, emissionKind: NoDebug, enums: !2, retainedTypes: !2, globals: !2, imports: !2)
+!1 = !DIFile(filename: "calls.cc", directory: ".")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 1, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 3.5 "}
+!6 = distinct !DISubprogram(name: "sum", linkageName: "_Z3sumii", scope: !1, file: !1, line: 3, type: !7, scopeLine: 3, virtualIndex: 6, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!7 = !DISubroutineType(types: !2)
+!8 = !DILocation(line: 4, scope: !6)
+!9 = distinct !DISubprogram(name: "sub", linkageName: "_Z3subii", scope: !1, file: !1, line: 20, type: !7, scopeLine: 20, virtualIndex: 6, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!10 = !DILocation(line: 20, scope: !9)
+!11 = !DILocation(line: 21, scope: !9)
+!12 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 7, type: !7, scopeLine: 7, virtualIndex: 6, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!13 = !DILocation(line: 8, scope: !12)
+!14 = !DILocation(line: 9, scope: !12)
+!15 = !DILocation(line: 9, scope: !16)
+!16 = !DILexicalBlockFile(scope: !12, file: !1, discriminator: 2)
+!17 = !DILocation(line: 10, scope: !18)
+!18 = distinct !DILexicalBlock(scope: !12, file: !1, line: 10)
+!19 = !DILocation(line: 10, scope: !20)
+!20 = !DILexicalBlockFile(scope: !18, file: !1, discriminator: 2)
+!21 = !DILocation(line: 10, scope: !22)
+!22 = !DILexicalBlockFile(scope: !18, file: !1, discriminator: 4)
+!23 = !DILocation(line: 10, scope: !24)
+!24 = !DILexicalBlockFile(scope: !18, file: !1, discriminator: 6)
+!25 = !DILocation(line: 11, scope: !12)
+!26 = !DILocation(line: 12, scope: !12)
+
+; REPLAY: _Z3sumii inlined into main
+; REPLAY: _Z3subii inlined into main
+; REPLAY-NOT: _Z3subii inlined into _Z3sumii