[InlineCost] Fix infinite loop in indirect call evaluation

[ekatz]

Summary

Currently every time we encounter an indirect call of a known function, we try to evaluate the inline cost of that function. In case of a recursion, that evaluation never stops.

The solution I propose is to evaluate only the indirect call of the function, while any further indirect calls (of a known function) will be treated just as direct function calls, which, actually, never tries to evaluate the call.

Fix PR35469.

[ekatz]

Ping

[ekatz]

Ping

[fedor.sergeev]

llvm/lib/Analysis/InlineCost.cpp

1268–1269

Please, add assert here on F, e.g.:

assert(F && "call to known function expected here")

[fedor.sergeev]

llvm/lib/Analysis/InlineCost.cpp

1321

& -> && ?

[fedor.sergeev]

Can you add a test similar to what you have here that excercises indirect call through a parameter?
Say, do

define void @func1() {
  %t = bitcast void ()* @func3 to void ()*
  tail call void @func2(void()* %t)
  ret void
}
define void @func2(void()* %f) {
  tail call void %f()
  ret void
}

and then......

define void @func6() {
  %t2 = bitcast void (void()*)* @func2 to void (void()*)* 
  %t3 = bitcast void ()* @func3 to void ()*
  tail call void %t2(void()* %t3)
  ret void
}

This results in recursive call to func2+ and your fix should handle it just right.

[fedor.sergeev]

llvm/test/Transforms/Inline/pr35469.ll

btw, I would rather have this test named by its functionality and not by PR number.

[ekatz]

In D69349#1742057, @fedor.sergeev wrote:

Can you add a test similar to what you have here that excercises indirect call through a parameter?
Say, do

define void @func1() {
  %t = bitcast void ()* @func3 to void ()*
  tail call void @func2(void()* %t)
  ret void
}
define void @func2(void()* %f) {
  tail call void %f()
  ret void
}

and then......

define void @func6() {
  %t2 = bitcast void (void()*)* @func2 to void (void()*)* 
  %t3 = bitcast void ()* @func3 to void ()*
  tail call void %t2(void()* %t3)
  ret void
}

This results in recursive call to func2+ and your fix should handle it just right.

The change you suggest, doesn't cause the crash.

llvm/lib/Analysis/InlineCost.cpp

1268–1269

Done

1321

Not a mistake, though the compiler will probably lower the later to just a simple "AND" (because they are both booleans), so I guess the later form is clearer.

[ekatz]

Done requested changes.

[fedor.sergeev]

The change you suggest, doesn't cause the crash.

would you mind to add that test here?
It should exercise a path of logic where argument comes through SimplifiedValues, so it is worth having it.

Anyway, LGTM.

[ekatz]

Added a test for passing a function pointer as an argument.

[ekatz]

Remove applying of call penalty in new places.

This broke some tests.

llvm/lib/Analysis/InlineCost.cpp

 
 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
 
 static cl::opt<int> InlineThreshold(
     "inline-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore,
     cl::desc("Control the amount of inlining to perform (default = 225)"));
 
 static cl::opt<int> HintThreshold(
-    "inlinehint-threshold", cl::Hidden, cl::init(325), cl::ZeroOrMore, 
+    "inlinehint-threshold", cl::Hidden, cl::init(325), cl::ZeroOrMore,
     cl::desc("Threshold for inlining functions with inline hint"));
 
 static cl::opt<int>
     ColdCallSiteThreshold("inline-cold-callsite-threshold", cl::Hidden,
                           cl::init(45), cl::ZeroOrMore,
                           cl::desc("Threshold for inlining cold callsites"));
 
 // We introduce this threshold to help performance of instrumentation based
 // PGO before we actually hook up inliner with analysis passes such as BPI and
 // BFI.
 static cl::opt<int> ColdThreshold(
-    "inlinecold-threshold", cl::Hidden, cl::init(45), cl::ZeroOrMore, 
+    "inlinecold-threshold", cl::Hidden, cl::init(45), cl::ZeroOrMore,
     cl::desc("Threshold for inlining functions with cold attribute"));
 
 static cl::opt<int>
     HotCallSiteThreshold("hot-callsite-threshold", cl::Hidden, cl::init(3000),
                          cl::ZeroOrMore,
                          cl::desc("Threshold for hot callsites "));
 
 static cl::opt<int> LocallyHotCallSiteThreshold(
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool ExposesReturnsTwice = false;
   bool HasDynamicAlloca = false;
   bool ContainsNoDuplicateCall = false;
   bool HasReturn = false;
   bool HasIndirectBr = false;
   bool HasUninlineableIntrinsic = false;
   bool InitsVargArgs = false;
 
+  /// Attempt to evaluate indirect calls to boost its inline cost.
+  bool BoostIndirectCalls;
+
   /// Number of bytes allocated statically by the callee.
   uint64_t AllocatedSize = 0;
   unsigned NumInstructions = 0;
   unsigned NumVectorInstructions = 0;
 
   /// Bonus to be applied when percentage of vector instructions in callee is
   /// high (see more details in updateThreshold).
   int VectorBonus = 0;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitCatchReturnInst(CatchReturnInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
 
 public:
   CallAnalyzer(const TargetTransformInfo &TTI,
                std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
                Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI,
                ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE,
-               Function &Callee, CallBase &Call, const InlineParams &Params)
+               Function &Callee, CallBase &Call, const InlineParams &Params,
+               bool BoostIndirect = true)
       : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
         PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()), ORE(ORE),
         CandidateCall(Call), Params(Params), Threshold(Params.DefaultThreshold),
         ComputeFullInlineCost(OptComputeFullInlineCost ||
                               Params.ComputeFullInlineCost || ORE),
-        EnableLoadElimination(true) {}
+        BoostIndirectCalls(BoostIndirect), EnableLoadElimination(true) {}
 
   InlineResult analyzeCall(CallBase &Call);
 
   int getThreshold() { return Threshold; }
   int getCost() { return Cost; }
 
   // Keep a bunch of stats about the cost savings found so we can print them
   // out when debugging.

 /// Use TTI to check whether a GEP is free.
 ///
 /// Respects any simplified values known during the analysis of this callsite.
 bool CallAnalyzer::isGEPFree(GetElementPtrInst &GEP) {
   SmallVector<Value *, 4> Operands;
   Operands.push_back(GEP.getOperand(0));
   for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
     if (Constant *SimpleOp = SimplifiedValues.lookup(*I))
-       Operands.push_back(SimpleOp);
-     else
-       Operands.push_back(*I);
   return TargetTransformInfo::TCC_Free == TTI.getUserCost(&GEP, Operands);
 }
 
 bool CallAnalyzer::visitAlloca(AllocaInst &I) {
   // Check whether inlining will turn a dynamic alloca into a static
   // alloca and handle that case.
   if (I.isArrayAllocation()) {
     Constant *Size = SimplifiedValues.lookup(I.getArraySize());
if (Call.hasFnAttr(Attribute::ReturnsTwice) &&
       !F.hasFnAttribute(Attribute::ReturnsTwice)) {
     // This aborts the entire analysis.
     ExposesReturnsTwice = true;
     return false;
   }
   if (isa<CallInst>(Call) && cast<CallInst>(Call).cannotDuplicate())
     ContainsNoDuplicateCall = true;
 
-  if (Function *F = Call.getCalledFunction()) {
-    // When we have a concrete function, first try to simplify it directly.
-    if (simplifyCallSite(F, Call))
-      return true;
+  Value *Callee = Call.getCalledOperand();
+  Function *F = dyn_cast_or_null<Function>(Callee);
+  bool IsIndirectCall = !F;
+  if (IsIndirectCall) {
+    // Check if this happens to be an indirect function call to a known function
+    // in this inline context. If not, we've done all we can.
+    F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
+    if (!F) {
+      // Pay the price of the argument setup. We account for the average 1
+      // instruction per call argument setup here.
+      addCost(Call.arg_size() * InlineConstants::InstrCost);
+
+      // Everything other than inline ASM will also have a significant cost
+      // merely from making the call.
+      if (!isa<InlineAsm>(Callee))
+        addCost(InlineConstants::CallPenalty);
+
+      if (!Call.onlyReadsMemory())
+        disableLoadElimination();
+      return Base::visitCallBase(Call);
+    }
+  }
+
+  assert(F && "Expected a call to a known function");
+
 
-    // Next check if it is an intrinsic we know about.
-    // FIXME: Lift this into part of the InstVisitor.
-    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&Call)) {
-      switch (II->getIntrinsicID()) {
-      default:
-        if (!Call.onlyReadsMemory() && !isAssumeLikeIntrinsic(II))
-          disableLoadElimination();
-        return Base::visitCallBase(Call);
 
-      case Intrinsic::load_relative:
-        // This is normally lowered to 4 LLVM instructions.
-        addCost(3 * InlineConstants::InstrCost);
-        return false;
 
-      case Intrinsic::memset:
-      case Intrinsic::memcpy:
-      case Intrinsic::memmove:
-        disableLoadElimination();
-        // SROA can usually chew through these intrinsics, but they aren't free.
-        return false;
-      case Intrinsic::icall_branch_funnel:
-      case Intrinsic::localescape:
-        HasUninlineableIntrinsic = true;
-        return false;
-      case Intrinsic::vastart:
-        InitsVargArgs = true;
-        return false;
-      }
-    }
 
-    if (F == Call.getFunction()) {
-      // This flag will fully abort the analysis, so don't bother with anything
-      // else.
-      IsRecursiveCall = true;
-      return false;
-    }
 
-    if (TTI.isLoweredToCall(F)) {
-      // We account for the average 1 instruction per call argument setup
-      // here.
-      addCost(Call.arg_size() * InlineConstants::InstrCost);
-
-      // Everything other than inline ASM will also have a significant cost
-      // merely from making the call.
-      if (!isa<InlineAsm>(Call.getCalledValue()))
-        addCost(InlineConstants::CallPenalty);
-    }
-
-    if (!Call.onlyReadsMemory())
-      disableLoadElimination();
-    return Base::visitCallBase(Call);
-  }
-
-  // Otherwise we're in a very special case -- an indirect function call. See
-  // if we can be particularly clever about this.
-  Value *Callee = Call.getCalledValue();
-
-  // First, pay the price of the argument setup. We account for the average
-  // 1 instruction per call argument setup here.
+    // We account for the average 1 instruction per call argument setup here.
     addCost(Call.arg_size() * InlineConstants::InstrCost);
 
-  // Next, check if this happens to be an indirect function call to a known
-  // function in this inline context. If not, we've done all we can.
-  Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
-  if (!F) {
-    if (!Call.onlyReadsMemory())
-      disableLoadElimination();
-    return Base::visitCallBase(Call);
-  }
-
     // If we have a constant that we are calling as a function, we can peer
     // through it and see the function target. This happens not infrequently
     // during devirtualization and so we want to give it a hefty bonus for
-  // inlining, but cap that bonus in the event that inlining wouldn't pan
-  // out. Pretend to inline the function, with a custom threshold.
+    // inlining, but cap that bonus in the event that inlining wouldn't pan out.
+    // Pretend to inline the function, with a custom threshold.
+    if (IsIndirectCall && BoostIndirectCalls) {
       auto IndirectCallParams = Params;
-  IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold;
+      IndirectCallParams.DefaultThreshold =
+          InlineConstants::IndirectCallThreshold;
       CallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, ORE, *F, Call,
-                  IndirectCallParams);
+                      IndirectCallParams, false);
       if (CA.analyzeCall(Call)) {
         // We were able to inline the indirect call! Subtract the cost from the
         // threshold to get the bonus we want to apply, but don't go below zero.
         Cost -= std::max(0, CA.getThreshold() - CA.getCost());
+      } else
+        // Otherwise simply add the cost for merely making the call.
+        addCost(InlineConstants::CallPenalty);
+    } else
+      // Otherwise simply add the cost for merely making the call.
+      addCost(InlineConstants::CallPenalty);
   }
 
-  if (!F->onlyReadsMemory())
+  if (!Call.onlyReadsMemory() || (IsIndirectCall && !F->onlyReadsMemory()))
     disableLoadElimination();
   return Base::visitCallBase(Call);
 }
 
 bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
   // At least one return instruction will be free after inlining.
   bool Free = !HasReturn;
   HasReturn = true;
bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
   if (NumCaseCluster <= 3) {
     // Suppose a comparison includes one compare and one conditional branch.
     addCost(NumCaseCluster * 2 * InlineConstants::InstrCost);
     return false;
   }
 
   int64_t ExpectedNumberOfCompare = 3 * (int64_t)NumCaseCluster / 2 - 1;
   int64_t SwitchCost =
-      ExpectedNumberOfCompare * 2 * InlineConstants::InstrCost;
 
   addCost(SwitchCost, (int64_t)CostUpperBound);
   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

llvm/test/Transforms/Inline/inline-indirect-chain.ll

+; RUN: opt -inline -early-cse < %s
+; This test used to crash (PR35469).
+
+define void @func1() {
+  %t = bitcast void ()* @func2 to void ()*
+  tail call void %t()
+  ret void
+}
+
+define void @func2() {
+  %t = bitcast void ()* @func3 to void ()*
+  tail call void %t()
+  ret void
+}
+
+define void @func3() {
+  %t = bitcast void ()* @func4 to void ()*
+  tail call void %t()
+  ret void
+}
+
+define void @func4() {
+  br i1 undef, label %left, label %right
+
+left:
+  %t = bitcast void ()* @func5 to void ()*
+  tail call void %t()
+  ret void
+
+right:
+  ret void
+}
+
+define void @func5() {
+  %t = bitcast void ()* @func6 to void ()*
+  tail call void %t()
+  ret void
+}
+
+define void @func6() {
+  %t = bitcast void ()* @func2 to void ()*
+  tail call void %t()
+  ret void
+}
+
+define void @func7() {
+  %t = bitcast void ()* @func3 to void ()*
+  tail call void @func8(void()* %t)
+  ret void
+}
+
+define void @func8(void()* %f) {
+  tail call void %f()
+  ret void
+}