[InlineCost] Check if caller formulates indirect recursion.

[twoh]

Summary

If a function uses stack heavily, the function shouldn't be inlined if the
caller can be recursively invoked, because it may lead stack size explosion.
Current inliner implemention only checks for self-recursion, but indirectely
recursive function has the same risk, and that actually happens with MySQL5.6+LTO.

To overcome this limitation, this diff adds a knob that can control the
"degree" of indirect recursion that the inliner attempts to detect. The default
value is 1 which means that it only checks for self-recursion, and wouldn't
change the current behavior.. MySQL issue can be addressed by setting the flag
to 2.

[lebedev.ri]

llvm/test/Transforms/Inline/recursive.ll

70

Can you also add a test to show what happens if @large_stack_callee is not called?
It should then be inlined?
Or is the intention to completely prohibit inlining of recursive calls?

[twoh]

llvm/test/Transforms/Inline/recursive.ll

70

No https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/InlineCost.cpp#L1607 is the only place where IsCallerRecursive is effective, so it only matters when AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller.

llvm/lib/Analysis/InlineCost.cpp

cl::desc("Minimum block frequency, expressed as a multiple of caller's "
              "entry frequency, for a callsite to be hot in the absence of "
              "profile information."));
 
 static cl::opt<bool> OptComputeFullInlineCost(
     "inline-cost-full", cl::Hidden, cl::init(false), cl::ZeroOrMore,
     cl::desc("Compute the full inline cost of a call site even when the cost "
              "exceeds the threshold."));
 
+static cl::opt<unsigned> RecursiveCallerSearchDepth(
+    "inline-recursion-search-depth", cl::Hidden, cl::init(1), cl::ZeroOrMore,
+    cl::desc("Check if the caller is recursive, up to the level specified "
+             "with this flag. Default is 1, which means checking "
+             "self-recursion only."));
+
 namespace {
 
 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   typedef InstVisitor<CallAnalyzer, bool> Base;
   friend class InstVisitor<CallAnalyzer, bool>;
 
   /// The TargetTransformInfo available for this compilation.
   const TargetTransformInfo &TTI;
InlineResult CallAnalyzer::analyzeCall(CallBase &Call) {
   // Check if we're done. This can happen due to bonuses and penalties.
   if (Cost >= Threshold && !ComputeFullInlineCost)
     return "high cost";
 
   if (F.empty())
     return true;
 
   Function *Caller = Call.getFunction();
-  // Check if the caller function is recursive itself.
-  for (User *U : Caller->users()) {
+  std::function<bool(Function *, Function *, unsigned)> RecursionFindingHelper;
+  RecursionFindingHelper = [&RecursionFindingHelper](Function *A, Function *B,
+                                                     unsigned Depth) -> bool {
+    if (Depth == 0)
+      return false;
+    for (User *U : A->users()) {
       CallBase *Call = dyn_cast<CallBase>(U);
-    if (Call && Call->getFunction() == Caller) {
-      IsCallerRecursive = true;
-      break;
-    }
+      if (!Call)
+        continue;
+      Function *CSF = Call->getFunction();
+      if (CSF == B || RecursionFindingHelper(CSF, B, Depth - 1))
+        return true;
     }
+    return false;
+  };
+  // Check if the caller function is recursive.
+  IsCallerRecursive =
+      RecursionFindingHelper(Caller, Caller, RecursiveCallerSearchDepth);
 
   // Populate our simplified values by mapping from function arguments to call
   // arguments with known important simplifications.
   auto CAI = Call.arg_begin();
   for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
        FAI != FAE; ++FAI, ++CAI) {
     assert(CAI != Call.arg_end());
     if (Constant *C = dyn_cast<Constant>(CAI))

llvm/test/Transforms/Inline/recursive.ll

 ; Inlining in the presence of recursion presents special challenges that we
 ; test here.
 ;
 ; RUN: opt -inline -S < %s | FileCheck %s
 ; RUN: opt -passes='cgscc(inline)' -S < %s | FileCheck %s
+; RUN: opt -inline -S -inline-recursion-search-depth=2 < %s | FileCheck --check-prefix=CHECK-INDIRECT %s
+; RUN: opt -passes='cgscc(inline)' -S -inline-recursion-search-depth=2 < %s | FileCheck --check-prefix=CHECK-INDIRECT %s
+; RUN: opt -inline -S < %s | FileCheck --check-prefix=CHECK-INDIRECT-NOFLAG %s
+; RUN: opt -passes='cgscc(inline)' -S < %s | FileCheck --check-prefix=CHECK-INDIRECT-NOFLAG %s
 
 define i32 @large_stack_callee(i32 %param) {
 ; CHECK-LABEL: define i32 @large_stack_callee(
 entry:
  %yyy = alloca [100000 x i8]
  %r = bitcast [100000 x i8]* %yyy to i8*
  call void @bar(i8* %r)
  ret i32 4
; CHECK: call i32 @large_stack_recursive_caller
   %f = call i32 @large_stack_callee(i32 %r)
 ; CHECK: call i32 @large_stack_callee
   br label %exit
 
 exit:
   ret i32 4
 }
 
+define i32 @recursive_callee(i32 %v) {
+entry:
+  %c = call i32 @large_stack_indirect_recursive_caller(i32 %v)
+  %r = sub i32 %c, 1
+  ret i32 %r
+}
+
+; Test an indirectly recursive function which calls another function with a
+; large stack. If '-inline-recursion-search-depth' is set to greater than 2,
+; inliner should refuse to inline the large stack allocation into an indirectly
+; recursive frame.
+
+define i32 @large_stack_indirect_recursive_caller(i32 %param) #0 {
+; CHECK-INDIRECT-LABEL: define i32 @large_stack_indirect_recursive_caller(
+; CHECK-INDIRECT-NOFLAG-LABEL: define i32 @large_stack_indirect_recursive_caller(
+entry:
+; CHECK-INDIRECT-NEXT: entry:
+; CHECK-INDIRECT-NOFLAG-NEXT: entry:
+; CHECK-INDIRECT-NOT: alloca
+; CHECK-INDIRECT-NOFLAG: alloca
+  %t = call i32 @foo(i32 %param)
+  %cmp = icmp eq i32 %t, -1
+  br i1 %cmp, label %exit, label %cont
+
+cont:
+  %r = call i32 @recursive_callee(i32 %t)
+; CHECK-INDIRECT: call i32 @large_stack_indirect_recursive_caller
+  %f = call i32 @large_stack_callee(i32 %r)
+; CHECK-INDIRECT: call i32 @large_stack_callee
+; CHECK-INDIRECT-NOFLAG-NOT: call i32 @large_stack_callee
+  br label %exit
+
+exit:
+  ret i32 4
+}
+
+
 declare void @bar(i8* %in)
 
 declare i32 @foo(i32 %param)
 
 ; Check that when inlining a non-recursive path into a function's own body that
 ; we get the re-mapping of instructions correct.
 define i32 @test_recursive_inlining_remapping(i1 %init, i8* %addr) {
 ; CHECK-LABEL: define i32 @test_recursive_inlining_remapping(

 ;
 ; CHECK-NOT:     call
 
 load:
   %castback = bitcast i8* %addr to i32*
   %n.load = load i32, i32* %castback
   ret i32 %n.load
 }
+
+attributes #0 = {noinline}