Do not apply redundant LastCallToStaticBonus

[twoh]

Summary

As written in the comments above, LastCallToStaticBonus is already applied to
the cost if Caller has only one user, so it is redundant to reapply the bonus
here.

If the only user is not a caller, TotalSecondaryCost will not be adjusted
anyway because callerWillBeRemoved is false. If there's no caller at all, we
don't need to care about TotalSecondaryCost because
inliningPreventsSomeOuterInline is false.

[davide]

Is it possible to add a testcase? Thanks.

[twoh]

Test case added. As InlineConstants::LastCallToStaticBonus has a massive value,
I use the loop unrolling pass with a big threshold to preprocess the test.

Without the patch, the cost of inlining 'bar' into 'foo' is largely undervalued
because LastCallToStaticBonus is applied twice. This prevents the inlining of
'baz' into 'bar', as inliner thinks that inlining 'bar' into 'foo' is more
beneficial (and inlining 'baz' into 'bar' will prevent the inlining of 'bar'
into 'foo'). Later, inliner inlines 'bar' into 'foo', then 'baz' into 'foo' as
well. Therefore, there's only 'foo' left in the end.

With the patch, inliner precisely computes the cost of inlining 'bar' into
'foo', and let 'baz' inlined into 'bar'. This prevents the inlining of 'bar'
into 'foo' by increasing the inlining cost of 'bar'.

[eraman]

The change looks fine, but this is an instance where fixing a bug causes a regression :( See my comments in a different bug at https://reviews.llvm.org/D21405#461421 . Could you do size comparison with this patch on some benchmarks and post it here for reference?

test/Transforms/Inline/last-call-bonus.ll

1 ↗

(On Diff #86015)

Leave a comment on why you are doing the unrolling with high unroll factor

[twoh]

@eraman Thank you for the comments. I evaluated the size with spec2006 c/c++ benchmarks, and only 401.bzip2 is affected by this patch. Below is the result for -O2 and -O3. 'Binary' is for the entire binary size and 'Text' is for the text section size.

-O3 result:

                                     Binary                         Text
                   before      after   diff     before      after   diff
 400.perlbench  1,244,288  1,244,288  0.00%  1,124,296  1,124,296  0.00%
     401.bzip2     94,320     98,392  4.32%     77,951     81,247  4.23%
       403.gcc  3,832,632  3,832,632  0.00%  3,569,708  3,569,708  0.00%
       429.mcf     23,088     23,088  0.00%     13,682     13,682  0.00%
      433.milc    156,768    156,768  0.00%    132,977    132,977  0.00%
      444.namd    382,464    382,464  0.00%    343,740    343,740  0.00%
     445.gobmk  3,982,344  3,982,344  0.00%  1,467,536  1,467,536  0.00%
    447.dealII  5,003,664  5,003,664  0.00%  3,846,935  3,846,935  0.00%
    450.soplex  1,178,304  1,178,304  0.00%    873,994    873,994  0.00%
    453.povray  1,356,640  1,356,640  0.00%  1,167,752  1,167,752  0.00%
     456.hmmer    348,072    348,072  0.00%    312,659    312,659  0.00%
     458.sjeng    156,088    156,088  0.00%    132,903    132,903  0.00%
462.libquantum     55,608     55,608  0.00%     43,694     43,694  0.00%
   464.h264ref    710,960    710,960  0.00%    642,200    642,200  0.00%
       470.lbm     22,392     22,392  0.00%     13,593     13,593  0.00%
   471.omnetpp  1,561,704  1,561,704  0.00%  1,136,964  1,136,964  0.00%
     473.astar    125,504    125,504  0.00%     96,129     96,129  0.00%
   482.sphinx3    214,280    214,280  0.00%    186,181    186,181  0.00%
 483.xalancbmk  6,977,136  6,977,136  0.00%  4,762,598  4,762,598  0.00%
  999.specrand      8,696      8,696  0.00%      1,870      1,870  0.00%

-O2 result:

                                     Binary                         Text
                   before      after   diff     before      after   diff
 400.perlbench  1,207,504  1,207,504  0.00%  1,085,608  1,085,608  0.00%
     401.bzip2     94,320     94,296 -0.03%     76,831     79,967  4.08%
       403.gcc  3,772,152  3,772,152  0.00%  3,508,612  3,508,612  0.00%
       429.mcf     23,088     23,088  0.00%     13,490     13,490  0.00%
      433.milc    148,576    148,576  0.00%    125,633    125,633  0.00%
      444.namd    382,464    382,464  0.00%    343,388    343,388  0.00%
     445.gobmk  3,953,920  3,953,920  0.00%  1,440,448  1,440,448  0.00%
    447.dealII  4,958,384  4,958,384  0.00%  3,795,567  3,795,567  0.00%
    450.soplex  1,170,464  1,170,464  0.00%    867,618    867,618  0.00%
    453.povray  1,335,872  1,335,872  0.00%  1,149,056  1,149,056  0.00%
     456.hmmer    340,088    340,088  0.00%    305,427    305,427  0.00%
     458.sjeng    156,088    156,088  0.00%    132,199    132,199  0.00%
462.libquantum     55,608     55,608  0.00%     42,094     42,094  0.00%
   464.h264ref    686,464    686,464  0.00%    621,280    621,280  0.00%
       470.lbm     22,392     22,392  0.00%     13,177     13,177  0.00%
   471.omnetpp  1,558,112  1,558,112  0.00%  1,131,296  1,131,296  0.00%
     473.astar    125,504    125,504  0.00%     95,241     95,241  0.00%
   482.sphinx3    210,184    210,184  0.00%    182,541    182,541  0.00%
 483.xalancbmk  6,937,672  6,937,672  0.00%  4,710,754  4,710,754  0.00%
  999.specrand      8,696      8,696  0.00%      1,870      1,870  0.00%

[twoh]

Add comments to the test

[haicheng]

lib/Transforms/IPO/Inliner.cpp

329 ↗

(On Diff #86124)

Did you upload the wrong patch?

[twoh]

lib/Transforms/IPO/Inliner.cpp

329 ↗

(On Diff #86124)

Oops, my bad. I forgot to revert it back after the evaluation. Will update it shortly. Thanks!

[twoh]

Previous one was the wrong patch.

[twoh]

Friendly ping :)

[eraman]

Sorry about the delay. The patch itself is straightforward and fixes an obvious error. Before I LGTM, do you see any size/performance improvement as the result of this?

test/Transforms/Inline/last-call-bonus.ll

1 ↗

(On Diff #86127)

nit: Make it clear that this checks that LastCallToStaticBonus is applied correctly while deciding inline deferral (since it has nothing to do with application of LastCallBonus in InlineCost.cpp)

[twoh]

Make it clear that the test is for inline deferral decision.

[twoh]

@eraman Not at all. Thank you for your comments. I didn't see any improvement with this fix, but as this is an obvious bug, I think it is better to fix it sooner than later.

[eraman]

LGTM.

I'm generally wary of fixes that cause regression without providing any benefits and it is preferable that the root cause of the regression is addressed before fixing the bug.  But in this case the conditions that trigger size regression are not going to be commonplace and fixing the root cause (huge size increases when multiple callsites get inlined into a single function) does not have an easy fix, so I'm fine with the patch. However, wait to see if Chandler has a different opinion in which case I'll defer to him.

[twoh]

Thanks @eraman! I'll wait for @chandlerc for a week and commit the patch if there's no reply from him.

llvm/trunk/lib/Transforms/IPO/Inliner.cpp

if (IC2.getCostDelta() <= CandidateCost) {
       inliningPreventsSomeOuterInline = true;
       TotalSecondaryCost += IC2.getCost();
     }
   }
   // If all outer calls to Caller would get inlined, the cost for the last
   // one is set very low by getInlineCost, in anticipation that Caller will
   // be removed entirely.  We did not account for this above unless there
   // is only one caller of Caller.
-  if (callerWillBeRemoved && !Caller->use_empty())
+  if (callerWillBeRemoved && !Caller->hasOneUse())
     TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
 
   if (inliningPreventsSomeOuterInline && TotalSecondaryCost < IC.getCost())
     return true;
 
   return false;
 }
 

llvm/trunk/test/Transforms/Inline/last-call-bonus.ll

+; The goal of this test is checking if LastCallToStaticBonus is applied
+; correctly while deciding inline deferral. For the test code below, when
+; inliner evaluates the callsite of bar->baz, it checks if inlining of bar->baz
+; prevents ininling of foo->bar, even when foo->bar inlining is more beneficial
+; than bar->baz inlining. As LastCallToStaticBonus has a massive value, and
+; both baz and bar has only one caller, the cost of foo->bar inlining and
+; bar->baz inlining should be non-trivial for inliner to compute that bar->baz
+; inlining can actaully prevent foo->bar inlining. To make the cost of these
+; callsites big enough, loop unrolling pass with very high threshold is used to
+; preprocess the test.
+
+; RUN: opt < %s -loop-unroll -inline -unroll-threshold=15000 -inline-threshold=250 -S | FileCheck %s
+; CHECK-LABEL: define internal i32 @bar()
+
+define internal i32 @baz() {
+entry:
+  br label %bb1
+
+bb1:
+  %ind = phi i32 [ 0, %entry ], [ %inc, %bb1 ]
+  call void @extern()
+  %inc = add nsw i32 %ind, 1
+  %cmp = icmp sgt i32 %inc, 510
+  br i1 %cmp, label %ret, label %bb1
+
+ret:
+  ret i32 0
+}
+
+define internal i32 @bar() {
+entry:
+  br label %bb1
+
+bb1:
+  %ind = phi i32 [ 0, %entry ], [ %inc, %bb1 ]
+  call void @extern()
+  %inc = add nsw i32 %ind, 1
+  %cmp = icmp sgt i32 %inc, 510
+  br i1 %cmp, label %ret, label %bb1
+
+ret:
+  call i32 @baz()
+  ret i32 0
+}
+
+define i32 @foo() {
+entry:
+  call i32 @bar()
+  ret i32 0
+}
+
+declare void @extern()