[SamplePGO] Fix ICE that callee samples returns null while finding import functions

[wlei]

Summary

We found that in a special condition, the input callee Samples is null for findExternalInlineCandidate, which caused an ICE.

In some rare cases, call instruction could be changed after being pushed into inline candidate queue, this is because earlier inlining may expose constant propagation which can change indirect call to direct call. When this happens, we may fail to find matching function samples for the candidate later(for example if the profile is stale), even if a match was found when the candidate was enqueued.

See this reduced program:

file1.c:

 int bar(int x);

 int(*foo())()  {
  return bar;
 };

void func()
 {
     int (*fptr)(int);
     fptr = foo();
     a +=  (*fptr)(10);
 }

file2.c:

int bar(int x) { return x + 1;}

The two CALL: foo and (*ptr) are pushed into the queue at the beginning, say foo is hotter and popped first for inlining. During the inlining of foo, it performs the constant propagation for the function pointer bar and then changed (*ptr) to a direct call bar(..). Note that at this time, (*ptr)/bar is still in the queue, later while it's popped out for inlining, it use the a different target name(bar) to look for the callee samples. At the same time, if the profile is stale and the new function is different from the old function in the profile, then this led the return of the null callee sample.

[hoy]

Consider changing to title to "[SamplePGO] ..." since this is fixing an issue not specific to CSSPGO.

llvm/lib/Transforms/IPO/SampleProfile.cpp

1083

typo: Replayed

1087

Could mention more in the comment about that this is a problem with a stale profile.

[wlei]

addressing feedback

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

If it's not beneficial to inline/import (i.e. getExternalInlineAdvisorShouldInline returns false), should we just return without adding the callee to import candidate GUID set?

1087

The popped out call instruction is different from what was pushed.
we only push the CALL instruction when we find its callee sample is not null to make sure we get a non-null samples when we pop the CALL.

nit: make it explicit as to push and pop out of what.. here it's the inline candidate queue.

I would say something like this:

In some rare cases, call instruction could be changed after being pushed into inline candidate queue, this is because earlier inlining may expose const-prop which can change indirect call to direct call. When this happens, we may fail to find matching function samples for the candidate later, even if a match was found when the candidate was enqueued.

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Good question.
I'm just reading the code of getExternalInlineAdvisorShouldInline , it looks to me getExternalInlineAdvisorShouldInline return false doesn't mean it's not beneficial to inlining/import, it's only for replay, which is an uncommon situation, so most of time it return false, we still continue the importing.
Say if we ignore the branch(line 1078), the question becomes : should we import a callee whose samples is null?

This actually didn't happen before, that's why there is an assertion. OK. but as this is an assertion, it seems it just means we shouldn't import it.

so the change can be simplified to change the assertion to a return, WDYT?

@hoy I remember we discussed offline, you suggested to import it, otherwise it would miss the inlining opportunity for this call in post-link.

Also the below logic for non-null samples is to import the hot callee, since this is exposed by stale profile, so if the new function is hot, we have to import it.. but we don't know if the new function is hot or not...

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Say bar is just renamed to baz, we actually need to analyze bar's samples to decide the import lists, but it's a function renaming matching which is a big topic.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Lei, I think you're right. Before replay inline was added (D112033), there was only this assertion. I think it makes sense to just return when Samples is null instead of assert non-null, with the explanation of the case we ran into. This should be really rare, so perf wise it probably won't matter import or not.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Importing it is probably not that beneficial but it matches the behavior of in-module inlining.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1083

How about framing the comment like this:

An inline candidate that is originally an indirect call can be optimized to a direct call due to the inlining of other candidates (e.,g constant propagation of the function pointer). This may cause the an lookup error of the candidate samples if the promoted call target doesn't exist in the profile due to profile staleness. Since it's known that the callsite is a good candidate and it should still be good to inline it regardless. This also matches the behavior of in-module inlining.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

it matches the behavior of in-module inlining.

Being in the inline candidate queue doesn't mean it will be inlined if it's not external. It only means it will be evaluated. The actual inline decision is in tryInlineCandidate->shouldInlineCandidate (for direct call), and at this point there is no guarantee that it would be inlined if it's not external.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Right, importing just offers an opportunity for it to be inlined. Both in-module and external inlining have to go through the inliner's cost model once the IR is ready.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

I was just confused by what you meant "matches the behavior of in-module inlining".

For local functions, it's available, and we evaluate every function calls. For external functions, we can't possibly make all functions available like local functions, so we have to choose to import those that are likely to be inlined based on hotness.

If we import everything regardless of hotness, that would "matches the behavior of in-module inlining", but that's not practical, and not what we do today.

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Importing it is probably not that beneficial but it matches the behavior of in-module inlining.

@hoy On a second thought, speaking of "matches the behavior of in-module inlining.", we also don't inline a callee function whose samples is mismatched/null, as this is "sample profile inlining". If it's other inliner(CGSCC) inline it, other inliner should do the importing.

So maybe just returning null make more sense?

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

By matching the behavior of in-module inlining, I mean the case of indirect call promoted to a direct local callee, in which case the promoted callee will be considered inlining without going through a sample lookup:

https://github.com/llvm/clangir/blob/b7d9322b4963e620dfd12246816e6f7b2da5fd88/llvm/lib/Transforms/IPO/SampleProfile.cpp#L1500

In our case, the callee is external. I think it should be imported and go through the same logic above.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Oh, there's a subtle difference here. Even if the callee is imported, it'll still not considered an inline candidate because of the sample lookup error in postlink. If the callsite has branch metadata, the callee may be inlined by postlink CGSCC. But that's not a match of sample profile inliner. So returning null is more reasonable.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

indirect call promoted to a direct local callee, in which case the promoted callee will be considered inlining without going through a sample lookup

This is different - the promoted call still go through hotness evaluation (tryPromoteAndInlineCandidate->tryInlineCandidate->shouldInlineCandidate).

The question is, whether we filter on hotness before we decided to import, the answer is yes, and here we don't have hotness, so we should not import.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

An alternative as discussed offline, place a sample lookup check right after popping an candiate. This should line up in-module and external inlining for our case:

https://github.com/llvm/clangir/blob/b7d9322b4963e620dfd12246816e6f7b2da5fd88/llvm/lib/Transforms/IPO/SampleProfile.cpp#L1443

But it sounds a bit over-engineering as the case isn't common, and matching behavior isn't the demanding.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

matching behavior

I think "sample lookup" is a detail that is not important to match. If we have to match, I'd argue to match the check on hotness before inlining/importing - in which case, we shouldn't import here.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

This is different - the promoted call still go through hotness evaluation (tryPromoteAndInlineCandidate->tryInlineCandidate->shouldInlineCandidate).

I was thinking the imported callee can still go though this but just realized it won't even be considered a candidate as it doesn't have the nested callee profile anywhere.

The question is, whether we filter on hotness before we decided to import, the answer is yes, and here we don't have hotness, so we should not import.

I think given a stale profile, the current behavior is to accidentally trust the hotness in the profile and let it drive the inlining for a promoted icall. If we don't want this, we should consider the alternative above.

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Yeah, bar is changed to baz, ideally we should find the match bar --> baz beforehand, and use bar's hotness to do the importing, right now we don't have the function renaming match yet.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

I'd argue to match the check on hotness before inlining/importing - in which case, we shouldn't import here.

The hotness check is already passed for an inline candidate. But that's a staleness hotness for the old icall targets. If we want to trust it we can do the importing, but as I just realized, it wouldn't help postlink sample loader. If we don't want to trust it, we should consider excluding the in-module case as well.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Something I was thinking as an alternative:

// Perform iterative BFS call site prioritized inlining
  bool Changed = false;
  while (!CQueue.empty() && F.getInstructionCount() < SizeLimit) {
    InlineCandidate Candidate = CQueue.top();
    CQueue.pop();
    CallBase *I = Candidate.CallInstr;

    // The callsite has been transformed and has no samples, thus should be excluded from inlining and importing
    if (findCalleeFunctionSamples(*I))
       continue;

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

The hotness check is already passed for an inline candidate.

Where did it pass the hotness check? we put calls from getInlineCandidate into the candidate queue, and getInlineCandidate doesn't do any hotness check.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Where did it pass the hotness check? we put calls from getInlineCandidate into the candidate queue, and getInlineCandidate doesn't do any hotness check.

Oh I see. There was no hotness check when it was added to the queue.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Where did it pass the hotness check? we put calls from getInlineCandidate into the candidate queue, and getInlineCandidate doesn't do any hotness check.

Oh I see. There was no hotness check when it was added to the queue.

Now, do we all agree that a hotness check should be needed before importing, and since there's no hotness check, let's just return on null samples, without importing?

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Returning null sounds good to me, as this is not a common case perhaps we do not need to be fancy.

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1082–1083

Thanks for the discussion! I will change to return null.

[wlei]

1. change to simply return(not add to the import list)
2. update the comments

[hoy]

LGTM, thanks.

[wenlei]

nit: update the change description too based on the new comment (describing it using push/pop isn't very intuitive). otherwise lgtm.

llvm/lib/Transforms/IPO/SampleProfile.cpp

void SampleProfileLoader::emitOptimizationRemarksForInlineCandidates(
   }
 }
 
 void SampleProfileLoader::findExternalInlineCandidate(
     CallBase *CB, const FunctionSamples *Samples,
     DenseSet<GlobalValue::GUID> &InlinedGUIDs,
     const StringMap<Function *> &SymbolMap, uint64_t Threshold) {
 
-  // If ExternalInlineAdvisor wants to inline an external function
-  // make sure it's imported
+  // If ExternalInlineAdvisor(ReplayInlineAdvisor) wants to inline an external
+  // function make sure it's imported
   if (CB && getExternalInlineAdvisorShouldInline(*CB)) {
     // Samples may not exist for replayed function, if so
     // just add the direct GUID and move on
     if (!Samples) {
       InlinedGUIDs.insert(
           FunctionSamples::getGUID(CB->getCalledFunction()->getName()));
       return;
     }
     // Otherwise, drop the threshold to import everything that we can
     Threshold = 0;
   }
 
-  assert(Samples && "expect non-null caller profile");
+  // In some rare cases, call instruction could be changed after being pushed
+  // into inline candidate queue, this is because earlier inlining may expose
+  // constant propagation which can change indirect call to direct call. When
+  // this happens, we may fail to find matching function samples for the
+  // candidate later, even if a match was found when the candidate was enqueued.
+  if (!Samples)
+    return;
 
   // For AutoFDO profile, retrieve candidate profiles by walking over
   // the nested inlinee profiles.
   if (!FunctionSamples::ProfileIsCS) {
     Samples->findInlinedFunctions(InlinedGUIDs, SymbolMap, Threshold);
     return;
   }
 

llvm/test/Transforms/SampleProfile/Inputs/csspgo-import-list-callee-samples.prof

+main:3040:0
+ 1: 0
+ 2: 510
+ 3: 0
+ 4: 510
+ 5: 510
+ 6: 0
+ 7: 1557 func:1557
+ !CFGChecksum: 281582081721716
+func:2671:1557
+ 1: 1557
+ 2: foo:657
+  1: 657
+  !CFGChecksum: 4294967295
+ 3: baz:557
+  1: 557
+  !CFGChecksum: 4294967295
+ !CFGChecksum: 562954248388607

llvm/test/Transforms/SampleProfile/csspgo-import-list-callee-samples.ll

+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -sample-profile-file=%S/Inputs/csspgo-import-list-callee-samples.prof  -S | FileCheck %s
+
+; Original source code:
+
+; file1.c:
+;
+; int a = 1;
+; int bar(int x);
+;
+; int(*foo())()  {
+;  a++;
+;  return bar;
+; };
+
+; __attribute__((noinline)) void func()
+; {
+;     int (*fptr)(int);
+;     fptr = foo();
+;     a +=  (*fptr)(10);
+; }
+
+; int main() {
+;   for(int i = 0; i < 1000 * 1000; i++)
+;     func();
+; }
+
+; file2.c:
+;
+; int bar(int x) { return x + 1;}
+
+
+
+; GUID for bar is -2012135647395072713, make sure bar is not imported.
+; CHECK: ![[#]] = !{!"function_entry_count", i64 1557}
+; CHECK-NOT: ![[#]] = !{!"function_entry_count", i64 1557, i64 -2012135647395072713}
+
+@a = dso_local global i32 1, align 4
+
+; Function Attrs: nounwind uwtable
+define dso_local ptr @foo() #0 !dbg !11 {
+entry:
+  call void @llvm.pseudoprobe(i64 6699318081062747564, i64 1, i32 0, i64 -1), !dbg !14
+  %0 = load volatile i32, ptr @a, align 4, !dbg !14, !tbaa !15
+  %inc = add nsw i32 %0, 1, !dbg !14
+  store volatile i32 %inc, ptr @a, align 4, !dbg !14, !tbaa !15
+  ret ptr @bar, !dbg !19
+}
+
+declare dso_local i32 @bar(i32 noundef) #1
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local void @func() #2 !dbg !20 {
+entry:
+  call void @llvm.pseudoprobe(i64 7289175272376759421, i64 1, i32 0, i64 -1), !dbg !21
+  %call = call ptr @foo(), !dbg !22
+  %call1 = call i32 %call(i32 noundef 10), !dbg !24
+  %0 = load volatile i32, ptr @a, align 4, !dbg !26, !tbaa !15
+  %add = add nsw i32 %0, %call1, !dbg !26
+  store volatile i32 %add, ptr @a, align 4, !dbg !26, !tbaa !15
+  ret void, !dbg !27
+}
+
+; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
+declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #3
+
+; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
+declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #3
+
+; Function Attrs: nounwind uwtable
+define dso_local i32 @main() #0 !dbg !28 {
+entry:
+  call void @llvm.pseudoprobe(i64 -2624081020897602054, i64 1, i32 0, i64 -1), !dbg !29
+  br label %for.cond, !dbg !30
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ], !dbg !31
+  call void @llvm.pseudoprobe(i64 -2624081020897602054, i64 2, i32 0, i64 -1), !dbg !32
+  %cmp = icmp slt i32 %i.0, 1000000, !dbg !34
+  br i1 %cmp, label %for.body, label %for.cond.cleanup, !dbg !36
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  call void @llvm.pseudoprobe(i64 -2624081020897602054, i64 3, i32 0, i64 -1), !dbg !37
+  call void @llvm.pseudoprobe(i64 -2624081020897602054, i64 6, i32 0, i64 -1), !dbg !38
+  ret i32 0, !dbg !38
+
+for.body:                                         ; preds = %for.cond
+  call void @llvm.pseudoprobe(i64 -2624081020897602054, i64 4, i32 0, i64 -1), !dbg !39
+  call void @func(), !dbg !40
+  call void @llvm.pseudoprobe(i64 -2624081020897602054, i64 5, i32 0, i64 -1), !dbg !42
+  %inc = add nsw i32 %i.0, 1, !dbg !43
+  br label %for.cond, !dbg !45, !llvm.loop !46
+}
+
+; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(inaccessiblemem: readwrite)
+declare void @llvm.pseudoprobe(i64, i64, i32, i64) #4
+
+attributes #0 = { nounwind uwtable "disable-tail-calls"="true" "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "use-sample-profile" }
+attributes #1 = { "disable-tail-calls"="true" "frame-pointer"="all" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #2 = { noinline nounwind uwtable "disable-tail-calls"="true" "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "use-sample-profile" }
+attributes #3 = { mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
+attributes #4 = { mustprogress nocallback nofree nosync nounwind willreturn memory(inaccessiblemem: readwrite) }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3, !4, !5, !6}
+!llvm.ident = !{!7}
+!llvm.pseudo_probe_desc = !{!8, !9, !10}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C11, file: !1, producer: "clang version 17.0.0 ", isOptimized: true, runtimeVersion: 0, emissionKind: NoDebug, splitDebugInlining: false, debugInfoForProfiling: true, nameTableKind: None)
+!1 = !DIFile(filename: "file.c", directory: "/tmp/")
+!2 = !{i32 2, !"Debug Info Version", i32 3}
+!3 = !{i32 1, !"wchar_size", i32 4}
+!4 = !{i32 7, !"uwtable", i32 2}
+!5 = !{i32 7, !"frame-pointer", i32 2}
+!6 = !{i32 1, !"EnableSplitLTOUnit", i32 0}
+!7 = !{!"clang version 17.0.0"}
+!8 = !{i64 6699318081062747564, i64 4294967295, !"foo"}
+!9 = !{i64 7289175272376759421, i64 562954248388607, !"func"}
+!10 = !{i64 -2624081020897602054, i64 281582081721716, !"main"}
+!11 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 6, type: !12, scopeLine: 6, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0)
+!12 = !DISubroutineType(types: !13)
+!13 = !{}
+!14 = !DILocation(line: 7, column: 4, scope: !11)
+!15 = !{!16, !16, i64 0}
+!16 = !{!"int", !17, i64 0}
+!17 = !{!"omnipotent char", !18, i64 0}
+!18 = !{!"Simple C/C++ TBAA"}
+!19 = !DILocation(line: 8, column: 3, scope: !11)
+!20 = distinct !DISubprogram(name: "func", scope: !1, file: !1, line: 11, type: !12, scopeLine: 12, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0)
+!21 = !DILocation(line: 14, column: 12, scope: !20)
+!22 = !DILocation(line: 14, column: 12, scope: !23)
+!23 = !DILexicalBlockFile(scope: !20, file: !1, discriminator: 186646551)
+!24 = !DILocation(line: 15, column: 11, scope: !25)
+!25 = !DILexicalBlockFile(scope: !20, file: !1, discriminator: 119537695)
+!26 = !DILocation(line: 15, column: 7, scope: !20)
+!27 = !DILocation(line: 16, column: 1, scope: !20)
+!28 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 18, type: !12, scopeLine: 18, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0)
+!29 = !DILocation(line: 19, column: 11, scope: !28)
+!30 = !DILocation(line: 19, column: 7, scope: !28)
+!31 = !DILocation(line: 19, scope: !28)
+!32 = !DILocation(line: 19, column: 18, scope: !33)
+!33 = !DILexicalBlockFile(scope: !28, file: !1, discriminator: 0)
+!34 = !DILocation(line: 19, column: 20, scope: !35)
+!35 = !DILexicalBlockFile(scope: !28, file: !1, discriminator: 2)
+!36 = !DILocation(line: 19, column: 3, scope: !35)
+!37 = !DILocation(line: 0, scope: !28)
+!38 = !DILocation(line: 21, column: 1, scope: !28)
+!39 = !DILocation(line: 20, column: 5, scope: !28)
+!40 = !DILocation(line: 20, column: 5, scope: !41)
+!41 = !DILexicalBlockFile(scope: !28, file: !1, discriminator: 186646591)
+!42 = !DILocation(line: 19, column: 36, scope: !33)
+!43 = !DILocation(line: 19, column: 36, scope: !44)
+!44 = !DILexicalBlockFile(scope: !28, file: !1, discriminator: 4)
+!45 = !DILocation(line: 19, column: 3, scope: !44)
+!46 = distinct !{!46, !47, !48, !49}
+!47 = !DILocation(line: 19, column: 3, scope: !28)
+!48 = !DILocation(line: 20, column: 10, scope: !28)
+!49 = !{!"llvm.loop.mustprogress"}