Do not early-inline recursive calls in sample profile loader.

[danielcdh]

Summary

Early-inlining of recursive call makes the code size bloat exponentially. We should not disable it.

[iteratee]

It doesn't have to blow it up exponentially. Can we clone the function to be inlined, re-writing the recursive calls to call the clone, and then inline that? Similar to a worker-wrapper transformation

[danielcdh]

In D34017#775712, @iteratee wrote:

It doesn't have to blow it up exponentially. Can we clone the function to be inlined, re-writing the recursive calls to call the clone, and then inline that? Similar to a worker-wrapper transformation

You mean clone the caller before any inlining, and inline that copy instead of the caller itself in early inlining? Yes we could do that, but that adds unnecessary copy overhead for every caller (which could be large). As llvm does not do recursive inlining anyway, this only solves cases where profile is collected from gcc binary, which should be temporary. So I guess it's not worth the effort to special-handle recursive early inlining.

[davidxl]

Does it miss opportunities to profile annotate inline instance of indirect target?

[danielcdh]

In D34017#775716, @davidxl wrote:

Does it miss opportunities to profile annotate inline instance of indirect target?

For indirect recursive-call, yes. But those calls will not be by llvm inlined anyway. So promote to direct call does not help much.

[davidxl]

So the profile is from GCC built binary ?

[iteratee]

In D34017#775713, @danielcdh wrote:

In D34017#775712, @iteratee wrote:

It doesn't have to blow it up exponentially. Can we clone the function to be inlined, re-writing the recursive calls to call the clone, and then inline that? Similar to a worker-wrapper transformation

You mean clone the caller before any inlining, and inline that copy instead of the caller itself in early inlining? Yes we could do that, but that adds unnecessary copy overhead for every caller (which could be large). As llvm does not do recursive inlining anyway, this only solves cases where profile is collected from gcc binary, which should be temporary. So I guess it's not worth the effort to special-handle recursive early inlining.

I meant to do it only if the inline is recursive. The overhead should be much lower in that case.
Clone the function, make the recursive calls call the clone, inline the clone. Repeat until you no longer want to inline any more, then take the remaining calls to the clone, and change them back. GC the clone. You could think of it as a kind of loop unrolling.

[iteratee]

lib/Transforms/IPO/SampleProfile.cpp

698

Add a comment?

[danielcdh]

In D34017#775722, @davidxl wrote:

So the profile is from GCC built binary ?

yes, we need to make sure it does not cause build breakage.

In D34017#775723, @iteratee wrote:

In D34017#775713, @danielcdh wrote:

In D34017#775712, @iteratee wrote:

It doesn't have to blow it up exponentially. Can we clone the function to be inlined, re-writing the recursive calls to call the clone, and then inline that? Similar to a worker-wrapper transformation

You mean clone the caller before any inlining, and inline that copy instead of the caller itself in early inlining? Yes we could do that, but that adds unnecessary copy overhead for every caller (which could be large). As llvm does not do recursive inlining anyway, this only solves cases where profile is collected from gcc binary, which should be temporary. So I guess it's not worth the effort to special-handle recursive early inlining.

I meant to do it only if the inline is recursive. The overhead should be much lower in that case.
Clone the function, make the recursive calls call the clone, inline the clone. Repeat until you no longer want to inline any more, then take the remaining calls to the clone, and change them back. GC the clone. You could think of it as a kind of loop unrolling.

This is still not-optimal. e.g.

foo() {

if (a)
  bar_large();
foo();

}

Suppose we first process bar_large() and inlined it. Then we start process foo and found it's recursive call, then we clone the foo body (with bar_large inlined). Then we recursively inline foo_clone into foo. But foo_clone already have bar_large(), which may not necessarily be cloned multiple times. A better solution would be

for (callsite cs : caller.callsites())

if (cs is recursive)
  clone caller

for (callsite cs : caller.callsites())

if (should early inline)
  if (cs is recursive)
    inline caller_clone into caller
  else
    inline callee into caller

But this is still not enough, as we may have foo calls bar, bar calls foo(). Which cannot be detected by the above algorithm. Of cause, we can process the SCC to find if caller could be early-inlined to be recursive, but that may be expensive, or make the logic complex.

[danielcdh]

add comments

lib/Transforms/IPO/SampleProfile.cpp

while (true) {
     for (auto I : CIS) {
       InlineFunctionInfo IFI(nullptr, ACT ? &GetAssumptionCache : nullptr);
       Function *CalledFunction = CallSite(I).getCalledFunction();
       Instruction *DI = I;
       if (!CalledFunction && !PromotedInsns.count(I) &&
           CallSite(I).isIndirectCall())
         for (const auto *FS : findIndirectCallFunctionSamples(*I)) {
           auto CalleeFunctionName = FS->getName();
+          // If it is a recursive call, we do not inline it as it could bloat
+          // the code exponentially. There is way to better handle this, e.g.
+          // clone the caller first, and inline the cloned caller if it is
+          // recursive. As llvm does not inline recursive calls, we will simply
+          // ignore it instead of handling it explicitly.
+          if (CalleeFunctionName == F.getName())
+            continue;
           const char *Reason = "Callee function not available";
           auto R = SymbolMap.find(CalleeFunctionName);
           if (R == SymbolMap.end())
             continue;
           CalledFunction = R->getValue();
           if (CalledFunction && isLegalToPromote(I, CalledFunction, &Reason)) {
             // The indirect target was promoted and inlined in the profile, as a
             // result, we do not have profile info for the branch probability.

test/Transforms/SampleProfile/Inputs/indirect-call.prof

  1: foo_direct:3000
   21: 3000
 test_inline_strip:3000:0
  1: foo_inline_strip:3000
   1: 3000
 test_inline_strip_conflict:3000:0
  1: foo_inline_strip_conflict:3000
   1: 3000
+test_norecursive_inline:3000:0
+ 1: test_norecursive_inline:3000
+  20: 3000

test/Transforms/SampleProfile/indirect-call.ll

define void @test_noinline(void ()*) !dbg !12 {
   store void ()* %0, void ()** %2
   %3 = load void ()*, void ()** %2
 ; CHECK-NOT: icmp
 ; CHECK: call
   call void %3(), !dbg !13
   ret void
 }
 
+; CHECK-LABEL: @test_norecursive_inline
+; If the indirect call target is the caller, we should not promote it.
+define void @test_norecursive_inline() !dbg !24 {
+; CHECK-NOT: icmp
+; CHECK: call
+  %1 = load void ()*, void ()** @y, align 8
+  call void %1(), !dbg !25
+  ret void
+}
+
 @x = global i32 0, align 4
+@y = global void ()* null, align 8
 
 define i32* @foo_inline1(i32* %x) !dbg !14 {
   ret i32* %x
 }
 
 define i32* @foo_inline_strip.suffix(i32* %x) !dbg !15 {
   ret i32* %x
 }

 !16 = distinct !DISubprogram(name: "foo_inline_strip_conflict.suffix1", scope: !1, file: !1, line: 1, unit: !0)
 !17 = distinct !DISubprogram(name: "foo_inline_strip_conflict.suffix2", scope: !1, file: !1, line: 1, unit: !0)
 !18 = distinct !DISubprogram(name: "foo_inline_strip_conflict.suffix3", scope: !1, file: !1, line: 1, unit: !0)
 !19 = distinct !DISubprogram(name: "foo_inline2", scope: !1, file: !1, line: 19, unit: !0)
 !20 = distinct !DISubprogram(name: "foo_noinline", scope: !1, file: !1, line: 20, unit: !0)
 !21 = distinct !DISubprogram(name: "foo_direct", scope: !1, file: !1, line: 21, unit: !0)
 !22 = distinct !DISubprogram(name: "test_direct", scope: !1, file: !1, line: 22, unit: !0)
 !23 = !DILocation(line: 23, scope: !22)
+!24 = distinct !DISubprogram(name: "test_norecursive_inline", scope: !1, file: !1, line: 12, unit: !0)
+!25 = !DILocation(line: 13, scope: !24)