[Inliner] Tweak the condition for determining cold callsites.

[eraman]

Summary

This addresses the following issue. Consider a call chain A->B->C, where
the B->C callsite is guarded by an if with builtin_expect (cond, 0).
When BFI is computed for B, it essentially gives a non-zero value to the
coldest reachable block and scales all blocks including the entry based
on that. The inliner then skips B-> callsite since it is cold and then,
let us assume, inlines B into A. Now, we incrementally updates A's BFI
by including the newly cloned blocks. This incremental update doesn't
update the entry BFI of A (since we only want to update the frequencies
of newly cloned blocks). As a result, we have A's entry having some low
block frequency and B->C clone has a frequency of 0. This results in
CallSiteFreq < CallerEntryFreq * ColdProb to evaluate to false since
both LHS and RHS are 0. This tweak ensures that the cloned callsite is
still 0. An alterantive is to explicitly check if CallSiteFreq is 0.

[eraman]

Thinking about this a little more, this will end up treating non-cold callsites as cold. As an exmple, consider bar gets inlined to foo. Let entry_freq(foo) = 8, entry_freq(bar) = 8, callsite_freq(foo->bar) = 7. Now, any block in bar with freq == 1 will end up with a frequency of 0 after cloning and will be treated as cold even it's frequency relative to foo's entry is 1/7 which is not cold for the default value of cold-callsite-rel-freq (1/50). Rouding the freuenies while scaling will mitigate this a little bit, but still not sufficient. Need to think more.

[chandlerc]

In D36976#850558, @eraman wrote:

Thinking about this a little more, this will end up treating non-cold callsites as cold. As an exmple, consider bar gets inlined to foo. Let entry_freq(foo) = 8, entry_freq(bar) = 8, callsite_freq(foo->bar) = 7. Now, any block in bar with freq == 1 will end up with a frequency of 0 after cloning and will be treated as cold even it's frequency relative to foo's entry is 1/7 which is not cold for the default value of cold-callsite-rel-freq (1/50). Rouding the freuenies while scaling will mitigate this a little bit, but still not sufficient. Need to think more.

I think you'll need to saturate at 1, and if necessary to preserve precision scale the caller up.

[eraman]

In D36976#850579, @chandlerc wrote:

In D36976#850558, @eraman wrote:

Thinking about this a little more, this will end up treating non-cold callsites as cold. As an exmple, consider bar gets inlined to foo. Let entry_freq(foo) = 8, entry_freq(bar) = 8, callsite_freq(foo->bar) = 7. Now, any block in bar with freq == 1 will end up with a frequency of 0 after cloning and will be treated as cold even it's frequency relative to foo's entry is 1/7 which is not cold for the default value of cold-callsite-rel-freq (1/50). Rouding the freuenies while scaling will mitigate this a little bit, but still not sufficient. Need to think more.

I think you'll need to saturate at 1, and if necessary to preserve precision scale the caller up.

Scaling the caller up pretty much defeats the purpose of incremental BFI updates and we no longer have the property that cost of a single inlining is constant.

[eraman]

In D36976#850603, @eraman wrote:

In D36976#850579, @chandlerc wrote:

In D36976#850558, @eraman wrote:

Thinking about this a little more, this will end up treating non-cold callsites as cold. As an exmple, consider bar gets inlined to foo. Let entry_freq(foo) = 8, entry_freq(bar) = 8, callsite_freq(foo->bar) = 7. Now, any block in bar with freq == 1 will end up with a frequency of 0 after cloning and will be treated as cold even it's frequency relative to foo's entry is 1/7 which is not cold for the default value of cold-callsite-rel-freq (1/50). Rouding the freuenies while scaling will mitigate this a little bit, but still not sufficient. Need to think more.

I think you'll need to saturate at 1, and if necessary to preserve precision scale the caller up.

Scaling the caller up pretty much defeats the purpose of incremental BFI updates and we no longer have the property that cost of a single inlining is constant.

We only need the block frequencies of blocks containing callsites. We already maintain the list of callsites including those obtained by inlining. We could keep track of the relative (to the entry of the caller) block frequencies as a ScaledNumber and use this in InlineCost and in InlineFunction.cpp (to update the profile counts). Thoughts?

lib/Analysis/InlineCost.cpp

bool CallAnalyzer::isColdCallSite(CallSite CS, BlockFrequencyInfo *CallerBFI) {
   // potentially cache the computation of scaled entry frequency, but the added
   // complexity is not worth it unless this scaling shows up high in the
   // profiles.
   const BranchProbability ColdProb(ColdCallSiteRelFreq, 100);
   auto CallSiteBB = CS.getInstruction()->getParent();
   auto CallSiteFreq = CallerBFI->getBlockFreq(CallSiteBB);
   auto CallerEntryFreq =
       CallerBFI->getBlockFreq(&(CS.getCaller()->getEntryBlock()));
-  return CallSiteFreq < CallerEntryFreq * ColdProb;
+  return CallSiteFreq <= CallerEntryFreq * ColdProb;
 }
 
 Optional<int>
 CallAnalyzer::getHotCallSiteThreshold(CallSite CS,
                                       BlockFrequencyInfo *CallerBFI) {
 
   // If global profile summary is available, then callsite's hotness is
   // determined based on that.

test/Transforms/Inline/inline-cold-callsite2.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -inline-cold-callsite-threshold=0 -S | FileCheck %s
+define void @bar(i32 %a) local_unnamed_addr {
+entry:
+  tail call void @baz(i32 %a)
+  tail call void @baz(i32 %a)
+  tail call void @baz(i32 %a)
+  ret void
+}
+
+declare void @baz(i32) local_unnamed_addr
+
+define void @foo(i32 %a) local_unnamed_addr {
+entry:
+  %cmp = icmp slt i32 %a, 10
+  br i1 %cmp, label %if.then, label %if.end, !prof !2
+
+if.then:                                          ; preds = %entry
+  call void @bar(i32 %a)
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  ret void
+}
+
+; CHECK-LABEL: @foobar
+define void @foobar(i32 %a) local_unnamed_addr {
+entry:
+  %mul = shl nsw i32 %a, 1
+; CHECK-NOT: call void @foo
+; CHECK: call void @bar
+  call void @foo(i32 %mul)
+  ret void
+}
+
+!2 = !{!"branch_weights", i32 1, i32 2000}