[Inline-cost] Teach cost function to account for accumulative code-size growth

[dnsampaio]

Summary

The current Inline-cost function does not take into account the accumulative code size growth of inlining calls to the same function multiple times.
If N function calls to a function are inlined, each increasing size by I, the accumulative code growth is N * I.
If the callee has local linkage, then we give it a bonus, as the function can be eliminated by the number of instruction in the function.

[lebedev.ri]

test/Transforms/Inline/InlineGrowthCost.ll

2–3

Can't you just use FileCheck?

[dnsampaio]

Using FileCheck in test file.

[greened]

lib/Analysis/InlineCost.cpp

1908

S - (N*X) doesn't match what the comment message says and doesn't make sense to me in this context. If N is large enough, this says the growth could become negative.

1913

This assumes all uses are inlined. That seems overly pessimistic. I'm not sure it's wise to predict what the inliner will do in the cost model. It seems like an incremental cost would be better. The inliner would then do the cost analysis for each inlining opportunity and decide on a case-by-case basis whether to inline or not. As written, this seems to have the cost model driving inline decisions (inline everything or nothing) rather than the inliner using cost information to make decisions.

[dnsampaio]

lib/Analysis/InlineCost.cpp

1908

Indeed the comment wrong. It should be (N*X). Will fix it.

The stipulated growth is N * (NumberOfInstrucions - NumberOfSimplifiedInstructions), where the last is expected, due the previous analysis. Yes, it is a pessimistic assumption, but with such a small threshold, is quite effective.

If the function has local linkage, then the expected growth might be negative, as the function will be eliminated, and the cost would actually be (N*X)-S.

1913

The cost-function analysis using -Oz are not that complex. It only considers each of the instructions (if they can be simplified if inlined), arguments passed and a constant cost for the call site. And see that it is incremental already. The additional cost decreases each time the function is inlined, that is, N reduces. The first one has the higher penalty, the last ones the higher benefit. Not counting the last one that gains huge bonus already.

[dnsampaio]

Fixed comment explaining the elaborated growth cost-function.

[eraman]

lib/Analysis/InlineCost.cpp

286

Turning on ComputeFullInlineCost can lead to excessive compile time for pathological cases. It changes the cost to analyze a function F from O(1) [the constant here depends on inline threshold] to O(size of F) and will particularly be bad for Oz because the threshold is low to start with.

1913

The cost of a callee depends on the callsite so multiplying the cost for one callsite by number of uses is not very meaningful.

[greened]

lib/Analysis/InlineCost.cpp

1913

It seems weird to have the cost decrease as inlining is done. I understand that's what happens given the current formulation, but I'm not sure the current formulation is correct. The cost of a single inline operation isn't N*X but rather X. By calculating the cost as N*X the code is assuming all calls to the function are inlined.

include/llvm/Analysis/InlineCost.h

 class Function;
 class ProfileSummaryInfo;
 class TargetTransformInfo;
 
 namespace InlineConstants {
 // Various thresholds used by inline cost analysis.
 /// Use when optsize (-Os) is specified.
 const int OptSizeThreshold = 50;
-
 /// Use when minsize (-Oz) is specified.
 const int OptMinSizeThreshold = 5;
+const int OptMinSizeGrowthPenalty = 1;
 
 /// Use when -O3 is specified.
 const int OptAggressiveThreshold = 250;
 
 // Various magic constants used to adjust heuristics.
 const int InstrCost = 5;
 const int IndirectCallThreshold = 100;
 const int CallPenalty = 25;

lib/Analysis/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   /// Return a higher threshold if \p CS is a hot callsite.
   Optional<int> getHotCallSiteThreshold(CallSite CS,
                                         BlockFrequencyInfo *CallerBFI);
 
   // Custom analysis routines.
   InlineResult analyzeBlock(BasicBlock *BB,
                             SmallPtrSetImpl<const Value *> &EphValues);
 
+  /// Cost growth analysis
+  int getGrowthCost();
+
   // Disable several entry points to the visitor so we don't accidentally use
   // them by declaring but not defining them here.
   void visit(Module *);
   void visit(Module &);
   void visit(Function *);
   void visit(Function &);
   void visit(BasicBlock *);
   void visit(BasicBlock &);
CallAnalyzer(const TargetTransformInfo &TTI,
                std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
                Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI,
                ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE,
                Function &Callee, CallSite CSArg, const InlineParams &Params)
       : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
         PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()), ORE(ORE),
         CandidateCS(CSArg), Params(Params), Threshold(Params.DefaultThreshold),
         Cost(0), ComputeFullInlineCost(OptComputeFullInlineCost ||
-                                       Params.ComputeFullInlineCost || ORE),
+                                       Params.ComputeFullInlineCost || ORE ||
+                                       F.optForMinSize()),
         IsCallerRecursive(false), IsRecursiveCall(false),
         ExposesReturnsTwice(false), HasDynamicAlloca(false),
         ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
         HasUninlineableIntrinsic(false), UsesVarArgs(false), AllocatedSize(0),
         NumInstructions(0), NumVectorInstructions(0), VectorBonus(0),
         SingleBBBonus(0), EnableLoadElimination(true), LoadEliminationCost(0),
         NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
         NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
if (SingleBB && TI->getNumSuccessors() > 1) {
       // Take off the bonus we applied to the threshold.
       Threshold -= SingleBBBonus;
       SingleBB = false;
     }
   }
 
   bool OnlyOneCallAndLocalLinkage =
       F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction();
+
+  Cost += getGrowthCost();
   // If this is a noduplicate call, we can still inline as long as
   // inlining this would cause the removal of the caller (so the instruction
   // is not actually duplicated, just moved).
   if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
     return "noduplicate";
 
   // We applied the maximum possible vector bonus at the beginning. Now,
   // subtract the excess bonus, if any, from the Threshold before
   // comparing against Cost.
   if (NumVectorInstructions <= NumInstructions / 10)
     Threshold -= VectorBonus;
   else if (NumVectorInstructions <= NumInstructions / 2)
     Threshold -= VectorBonus/2;
 
   return Cost < std::max(1, Threshold);
 }
 
+int CallAnalyzer::getGrowthCost() {
+  // If the function of size S is called N times and each inlining cause a
+  // code growth of X. The expected growth for inlining it N times is
+  // N * X.
+  // If the function has local linkage, then the cost would actually be
+  // (N * X) - S, as the function would be eliminated.
+  // The expected Growth lowers each time the function is inlined, as N
+  // reduces as well.
+  if (!F.optForMinSize())
+    return 0;
+
+  int Growth = (NumInstructions - NumInstructionsSimplified) * F.getNumUses();
+
+  // Test that we can eliminate the function, and give a bonus
+  // TODO: Perhaps we could add smaller bonus if the function can
+  // isDiscardableIfUnused()
+  if (F.hasLocalLinkage())
+    Growth -= NumInstructions;
+
+  return Growth * InlineConstants::OptMinSizeGrowthPenalty;
+}
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 /// Dump stats about this call's analysis.
 LLVM_DUMP_METHOD void CallAnalyzer::dump() {
 #define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"
   DEBUG_PRINT_STAT(NumConstantArgs);
   DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
   DEBUG_PRINT_STAT(NumAllocaArgs);
   DEBUG_PRINT_STAT(NumConstantPtrCmps);

test/Transforms/Inline/InlineGrowthCost.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -inline %s -o - | FileCheck %s --implicit-check-not "@DoInline"
+define dso_local i8* @ShouldNotInlined(i8* returned %dest, i8* nocapture readonly %source, i32 %num) #0 {
+entry:
+  br label %while.cond
+while.cond:
+  %num.addr.0 = phi i32 [ %num, %entry ], [ %dec, %while.body ]
+  %p_dest.0 = phi i8* [ %dest, %entry ], [ %incdec.ptr2, %while.body ]
+  %p_source.0 = phi i8* [ %source, %entry ], [ %incdec.ptr, %while.body ]
+  %cmp = icmp eq i32 %num.addr.0, 0
+  br i1 %cmp, label %while.end, label %while.body
+while.body:
+  %incdec.ptr = getelementptr inbounds i8, i8* %p_source.0, i32 1
+  %0 = load i8, i8* %p_source.0, align 1
+  %1 = trunc i32 %num.addr.0 to i8
+  %conv1 = sub i8 %1, %0
+  %incdec.ptr2 = getelementptr inbounds i8, i8* %p_dest.0, i32 1
+  store i8 %conv1, i8* %p_dest.0, align 1
+  %dec = add i32 %num.addr.0, -1
+  br label %while.cond
+while.end:
+  ret i8* %dest
+}
+define dso_local void @Caller(i8* %p1, i8* nocapture %p2, i32 %n) #0 {
+; CHECK-LABEL: @Caller(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[N:%.*]], 1
+; CHECK-NEXT:    tail call fastcc void @DoNotInline(i8* [[P1:%.*]], i8* [[P2:%.*]], i32 [[DIV]]) #0
+; CHECK-NEXT:    [[DIV1:%.*]] = lshr i32 [[N]], 2
+; CHECK-NEXT:    tail call fastcc void @DoNotInline(i8* [[P2]], i8* [[P1]], i32 [[DIV1]]) #0
+; CHECK-NEXT:    [[DIV3:%.*]] = lshr i32 [[N]], 3
+; CHECK-NEXT:    tail call fastcc void @DoNotInline(i8* [[P1]], i8* [[P2]], i32 [[DIV3]]) #0
+; CHECK-NEXT:    [[DIV5:%.*]] = lshr i32 [[N]], 4
+; CHECK-NEXT:    tail call fastcc void @DoNotInline(i8* [[P2]], i8* [[P1]], i32 [[DIV5]]) #0
+; CHECK-NEXT:    [[DIV7:%.*]] = lshr i32 [[N]], 5
+; CHECK-NEXT:    tail call fastcc void @DoNotInline(i8* [[P1]], i8* [[P2]], i32 [[DIV7]]) #0
+; CHECK-NEXT:    [[DIV9:%.*]] = lshr i32 [[N]], 6
+; CHECK-NEXT:    br label [[WHILE_COND_I:%.*]]
+; CHECK:       while.cond.i:
+; CHECK-NEXT:    [[NUM_ADDR_0_I:%.*]] = phi i32 [ [[DIV9]], [[ENTRY:%.*]] ], [ [[DEC_I:%.*]], [[WHILE_BODY_I:%.*]] ]
+; CHECK-NEXT:    [[P_DEST_0_I:%.*]] = phi i8* [ [[P2]], [[ENTRY]] ], [ [[INCDEC_PTR2_I:%.*]], [[WHILE_BODY_I]] ]
+; CHECK-NEXT:    [[P_SOURCE_0_I:%.*]] = phi i8* [ [[P1]], [[ENTRY]] ], [ [[INCDEC_PTR_I:%.*]], [[WHILE_BODY_I]] ]
+; CHECK-NEXT:    [[CMP_I:%.*]] = icmp eq i32 [[NUM_ADDR_0_I]], 0
+; CHECK-NEXT:    br i1 [[CMP_I]], label [[DOINLINE_EXIT:%.*]], label [[WHILE_BODY_I]]
+; CHECK:       while.body.i:
+; CHECK-NEXT:    [[INCDEC_PTR_I]] = getelementptr inbounds i8, i8* [[P_SOURCE_0_I]], i32 1
+; CHECK-NEXT:    [[TMP0:%.*]] = load i8, i8* [[P_SOURCE_0_I]], align 1
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[NUM_ADDR_0_I]] to i8
+; CHECK-NEXT:    [[CONV1_I:%.*]] = sub i8 [[TMP1]], [[TMP0]]
+; CHECK-NEXT:    [[INCDEC_PTR2_I]] = getelementptr inbounds i8, i8* [[P_DEST_0_I]], i32 1
+; CHECK-NEXT:    store i8 [[CONV1_I]], i8* [[P_DEST_0_I]], align 1
+; CHECK-NEXT:    [[DEC_I]] = add i32 [[NUM_ADDR_0_I]], -1
+; CHECK-NEXT:    br label [[WHILE_COND_I]]
+; CHECK:       DoInline.exit:
+; CHECK-NEXT:    [[DIV11:%.*]] = lshr i32 [[N]], 7
+; CHECK-NEXT:    br label [[WHILE_COND_I15:%.*]]
+; CHECK:       while.cond.i15:
+; CHECK-NEXT:    [[NUM_ADDR_0_I11:%.*]] = phi i32 [ [[DIV11]], [[DOINLINE_EXIT]] ], [ [[DEC_I19:%.*]], [[WHILE_BODY_I20:%.*]] ]
+; CHECK-NEXT:    [[P_DEST_0_I12:%.*]] = phi i8* [ [[P2]], [[DOINLINE_EXIT]] ], [ [[INCDEC_PTR2_I18:%.*]], [[WHILE_BODY_I20]] ]
+; CHECK-NEXT:    [[P_SOURCE_0_I13:%.*]] = phi i8* [ [[P1]], [[DOINLINE_EXIT]] ], [ [[INCDEC_PTR_I16:%.*]], [[WHILE_BODY_I20]] ]
+; CHECK-NEXT:    [[CMP_I14:%.*]] = icmp eq i32 [[NUM_ADDR_0_I11]], 0
+; CHECK-NEXT:    br i1 [[CMP_I14]], label [[DOINLINE_EXIT21:%.*]], label [[WHILE_BODY_I20]]
+; CHECK:       while.body.i20:
+; CHECK-NEXT:    [[INCDEC_PTR_I16]] = getelementptr inbounds i8, i8* [[P_SOURCE_0_I13]], i32 1
+; CHECK-NEXT:    [[TMP2:%.*]] = load i8, i8* [[P_SOURCE_0_I13]], align 1
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i32 [[NUM_ADDR_0_I11]] to i8
+; CHECK-NEXT:    [[CONV1_I17:%.*]] = sub i8 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    [[INCDEC_PTR2_I18]] = getelementptr inbounds i8, i8* [[P_DEST_0_I12]], i32 1
+; CHECK-NEXT:    store i8 [[CONV1_I17]], i8* [[P_DEST_0_I12]], align 1
+; CHECK-NEXT:    [[DEC_I19]] = add i32 [[NUM_ADDR_0_I11]], -1
+; CHECK-NEXT:    br label [[WHILE_COND_I15]]
+; CHECK:       DoInline.exit21:
+; CHECK-NEXT:    br label [[WHILE_COND_I5:%.*]]
+; CHECK:       while.cond.i5:
+; CHECK-NEXT:    [[NUM_ADDR_0_I1:%.*]] = phi i32 [ [[N]], [[DOINLINE_EXIT21]] ], [ [[DEC_I9:%.*]], [[WHILE_BODY_I10:%.*]] ]
+; CHECK-NEXT:    [[P_DEST_0_I2:%.*]] = phi i8* [ [[P1]], [[DOINLINE_EXIT21]] ], [ [[INCDEC_PTR2_I8:%.*]], [[WHILE_BODY_I10]] ]
+; CHECK-NEXT:    [[P_SOURCE_0_I3:%.*]] = phi i8* [ [[P2]], [[DOINLINE_EXIT21]] ], [ [[INCDEC_PTR_I6:%.*]], [[WHILE_BODY_I10]] ]
+; CHECK-NEXT:    [[CMP_I4:%.*]] = icmp eq i32 [[NUM_ADDR_0_I1]], 0
+; CHECK-NEXT:    br i1 [[CMP_I4]], label [[SHOULDNOTINLINED_EXIT:%.*]], label [[WHILE_BODY_I10]]
+; CHECK:       while.body.i10:
+; CHECK-NEXT:    [[INCDEC_PTR_I6]] = getelementptr inbounds i8, i8* [[P_SOURCE_0_I3]], i32 1
+; CHECK-NEXT:    [[TMP4:%.*]] = load i8, i8* [[P_SOURCE_0_I3]], align 1
+; CHECK-NEXT:    [[TMP5:%.*]] = trunc i32 [[NUM_ADDR_0_I1]] to i8
+; CHECK-NEXT:    [[CONV1_I7:%.*]] = sub i8 [[TMP5]], [[TMP4]]
+; CHECK-NEXT:    [[INCDEC_PTR2_I8]] = getelementptr inbounds i8, i8* [[P_DEST_0_I2]], i32 1
+; CHECK-NEXT:    store i8 [[CONV1_I7]], i8* [[P_DEST_0_I2]], align 1
+; CHECK-NEXT:    [[DEC_I9]] = add i32 [[NUM_ADDR_0_I1]], -1
+; CHECK-NEXT:    br label [[WHILE_COND_I5]]
+; CHECK:       ShouldNotInlined.exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %div = lshr i32 %n, 1
+  tail call fastcc void @DoNotInline(i8* %p1, i8* %p2, i32 %div) #0
+  %div1 = lshr i32 %n, 2
+  tail call fastcc void @DoNotInline(i8* %p2, i8* %p1, i32 %div1) #0
+  %div3 = lshr i32 %n, 3
+  tail call fastcc void @DoNotInline(i8* %p1, i8* %p2, i32 %div3) #0
+  %div5 = lshr i32 %n, 4
+  tail call fastcc void @DoNotInline(i8* %p2, i8* %p1, i32 %div5) #0
+  %div7 = lshr i32 %n, 5
+  tail call fastcc void @DoNotInline(i8* %p1, i8* %p2, i32 %div7) #0
+  %div9 = lshr i32 %n, 6
+  tail call fastcc void @DoInline(i8* %p2, i8* %p1, i32 %div9) #0
+  %div11 = lshr i32 %n, 7
+  tail call fastcc void @DoInline(i8* %p2, i8* %p1, i32 %div11) #0
+  %call13 = tail call i8* @ShouldNotInlined(i8* %p1, i8* %p2, i32 %n) #0
+  ret void
+}
+define internal fastcc void @DoNotInline(i8* nocapture %dest, i8* nocapture readonly %source, i32 %num) #0 {
+entry:
+  br label %while.cond
+while.cond:
+  %num.addr.0 = phi i32 [ %num, %entry ], [ %dec, %while.body ]
+  %p_dest.0 = phi i8* [ %dest, %entry ], [ %incdec.ptr2, %while.body ]
+  %p_source.0 = phi i8* [ %source, %entry ], [ %incdec.ptr, %while.body ]
+  %cmp = icmp eq i32 %num.addr.0, 0
+  br i1 %cmp, label %while.end, label %while.body
+while.body:
+  %incdec.ptr = getelementptr inbounds i8, i8* %p_source.0, i32 1
+  %0 = load i8, i8* %p_source.0, align 1
+  %1 = trunc i32 %num.addr.0 to i8
+  %conv1 = add i8 %0, %1
+  %incdec.ptr2 = getelementptr inbounds i8, i8* %p_dest.0, i32 1
+  store i8 %conv1, i8* %p_dest.0, align 1
+  %dec = add i32 %num.addr.0, -1
+  br label %while.cond
+while.end:
+  ret void
+}
+define internal fastcc void @DoInline(i8* nocapture %dest, i8* nocapture readonly %source, i32 %num) #0 {
+; CHECK-NOT-LABEL: @DoInline
+entry:
+  br label %while.cond
+while.cond:
+  %num.addr.0 = phi i32 [ %num, %entry ], [ %dec, %while.body ]
+  %p_dest.0 = phi i8* [ %dest, %entry ], [ %incdec.ptr2, %while.body ]
+  %p_source.0 = phi i8* [ %source, %entry ], [ %incdec.ptr, %while.body ]
+  %cmp = icmp eq i32 %num.addr.0, 0
+  br i1 %cmp, label %while.end, label %while.body
+while.body:
+  %incdec.ptr = getelementptr inbounds i8, i8* %p_source.0, i32 1
+  %0 = load i8, i8* %p_source.0, align 1
+  %1 = trunc i32 %num.addr.0 to i8
+  %conv1 = sub i8 %1, %0
+  %incdec.ptr2 = getelementptr inbounds i8, i8* %p_dest.0, i32 1
+  store i8 %conv1, i8* %p_dest.0, align 1
+  %dec = add i32 %num.addr.0, -1
+  br label %while.cond
+while.end:
+  ret void
+}
+attributes #0 = { minsize optsize }