[InlineCost] Do not take INT_MAX when Cost is negative

[junbuml]

Summary

visitSwitchInst should not take INT_MAX when Cost is negative. Instead of INT_MAX , we also use a valid upperbound cost when overflow occurs in Cost.

[dmgreen]

Thanks for the fix. Much appreciated.

I was hoping to take another look at getting you a better test case, but it looks like you came up with something good.

This fixes the differences we were seeing, so LGTM. Cheers.

lib/Analysis/InlineCost.cpp

bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
   // of jump table/bit test/binary search tree. The cost of the switch is
   // proportional to the size of the tree or the size of jump table range.
   //
   // NB: We convert large switches which are just used to initialize large phi
   // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent
   // inlining those. It will prevent inlining in cases where the optimization
   // does not (yet) fire.
 
+  // Maximum valid cost increased in this function.
+  int CostUpperBound = INT_MAX - InlineConstants::InstrCost - 1;
+
   // Exit early for a large switch, assuming one case needs at least one
   // instruction.
   // FIXME: This is not true for a bit test, but ignore such case for now to
   // save compile-time.
   int64_t CostLowerBound =
-      std::min((int64_t)INT_MAX,
+      std::min((int64_t)CostUpperBound,
                (int64_t)SI.getNumCases() * InlineConstants::InstrCost + Cost);
 
   if (CostLowerBound > Threshold) {
     Cost = CostLowerBound;
     return false;
   }
 
   unsigned JumpTableSize = 0;
   unsigned NumCaseCluster =
       TTI.getEstimatedNumberOfCaseClusters(SI, JumpTableSize);
 
   // If suitable for a jump table, consider the cost for the table size and
   // branch to destination.
   if (JumpTableSize) {
     int64_t JTCost = (int64_t)JumpTableSize * InlineConstants::InstrCost +
                      4 * InlineConstants::InstrCost;
-    Cost = std::min((int64_t)INT_MAX, JTCost + Cost);
+
+    Cost = std::min((int64_t)CostUpperBound, JTCost + Cost);
     return false;
   }
 
   // Considering forming a binary search, we should find the number of nodes
   // which is same as the number of comparisons when lowered. For a given
   // number of clusters, n, we can define a recursive function, f(n), to find
   // the number of nodes in the tree. The recursion is :
   // f(n) = 1 + f(n/2) + f (n - n/2), when n > 3,
   // and f(n) = n, when n <= 3.
   // This will lead a binary tree where the leaf should be either f(2) or f(3)
   // when n > 3.  So, the number of comparisons from leaves should be n, while
   // the number of non-leaf should be :
   //   2^(log2(n) - 1) - 1
   //   = 2^log2(n) * 2^-1 - 1
   //   = n / 2 - 1.
   // Considering comparisons from leaf and non-leaf nodes, we can estimate the
   // number of comparisons in a simple closed form :
   //   n + n / 2 - 1 = n * 3 / 2 - 1
   if (NumCaseCluster <= 3) {
     // Suppose a comparison includes one compare and one conditional branch.
     Cost += NumCaseCluster * 2 * InlineConstants::InstrCost;
     return false;
   }
-  int64_t ExpectedNumberOfCompare = 3 * (uint64_t)NumCaseCluster / 2 - 1;
-  uint64_t SwitchCost =
+
+  int64_t ExpectedNumberOfCompare = 3 * (int64_t)NumCaseCluster / 2 - 1;
+  int64_t SwitchCost =
       ExpectedNumberOfCompare * 2 * InlineConstants::InstrCost;
-  Cost = std::min((uint64_t)INT_MAX, SwitchCost + Cost);
+
+  Cost = std::min((int64_t)CostUpperBound, SwitchCost + Cost);
   return false;
 }
 
 bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
   // We never want to inline functions that contain an indirectbr.  This is
   // incorrect because all the blockaddress's (in static global initializers
   // for example) would be referring to the original function, and this
   // indirect jump would jump from the inlined copy of the function into the

test/Transforms/Inline/AArch64/switch.ll

 
 define i32 @caller_jumptable(i32 %a, i32 %b, i32* %P) {
 ; CHECK-LABEL: @caller_jumptable(
 ; CHECK: call i32 @callee_jumptable
   %r = call i32 @callee_jumptable(i32 %b, i32* %P)
   ret i32 %r
 }
 
+
+define internal i32 @callee_negativeCost(i32 %t)  {
+entry:
+  switch i32 %t, label %sw.default [
+    i32 1, label %sw.bb
+    i32 0, label %sw.bb1
+    i32 42, label %sw.bb2
+    i32 43, label %sw.bb3
+  ]
+
+sw.bb:                                            ; preds = %entry
+  br label %cleanup
+
+sw.bb1:                                           ; preds = %entry
+  br label %cleanup
+
+sw.bb2:                                           ; preds = %entry
+  br label %cleanup
+
+sw.bb3:                                           ; preds = %entry
+  br label %cleanup
+
+sw.default:                                       ; preds = %entry
+  br label %cleanup
+
+cleanup:                                          ; preds = %sw.default, %sw.bb3, %sw.bb2, %sw.bb1, %sw.bb
+  %retval.0 = phi i32 [ 1, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 0, %sw.bb1 ], [ 0, %sw.bb ]
+  ret i32 %retval.0
+}
+
+define i32 @caller_negativeCost(i32 %t) {
+; CHECK-LABEL: @caller_negativeCost(
+; CHECK-NOT: call i32 @callee_negativeCost
+entry:
+  %call = call i32 @callee_negativeCost(i32 %t)
+  ret i32 %call
+}