Enable inlining of recursive functions.

[pbarrio]

Summary

Add functionality to be able to inline recursive functions. Both direct and indirect (mutual) recursion are considered for inlining. The default behavior is still not to inline, but this can be changed by setting flag -max-recursion-inline to a value higher than 0.

This is intended as a previous step to optimized recursion inlining. Therefore, the heuristics are not tuned up for performance, and recursion inlining is not part of -Ox optimizations.

The patch slightly changes -O3 behavior. Inlining recursive functions into functions external to their SCC is allowed even if recursion inlining is not turned on (see regression test 2 below). Before, it was considered part of the recursion and therefore was marked as "never" inline. This change has been tested for correctness and performance with several benchmarks (LLVM test-suite included) and on two platforms, one aarch64 and one x86.

SUMMARY OF CHANGES:

"IsRecursiveCall" checks are removed in the inline cost calculator. The only inline recursion checks are now done in the Inliner with the help of function InlineHistoryIncludes(). That function now allows skipping part of the inline history (the recursion levels) to allow functions to be inlined into themselves or into members of their SCC.

Regression tests for recursion inlining:

1. Add checks for a function that calls itself (direct recursion) and for a SCC of size 2 (indirect recursion).

2. Removed a test checking that, if A is recursive and called by B, A is never inlined into B. Note that B is not necessarily part of A's SCC. Now, the calls to A from callers external to A's SCC are treated as any other function call.

3. Removed triple from a previous unit test, and added comments.

[jmolloy]

Hi Pablo,

Thanks for working on this! I have comments inline. But in general, it looks like this patch just allows recursive functions to be inlined, it doesn't change the heuristic calculation for them.

My impression from previous threads (Chandler will vociferiously declaim me if I misremember, I'm sure) is that Chandler expressed a wish that recursive inlining be treated heuristically more like loop unrolling, as they are somewhat equivalent. Do you have a comment on that?

Cheers,

James

lib/Analysis/IPA/InlineCost.cpp

912–913

The continuation line can now fit on one line.

1139–1140

Remove line break

lib/Transforms/IPO/Inliner.cpp

64

Could you please be more explicit about what exactly this knob does?

• What does "levels" mean? for example: B -> C -> B -> C - is that 2 levels or 4 levels?
• Explicitly put the default in the description message
• I assume this doesn't alter heuristics at all?

445

What exactly are you trying to do here? You haven't modified the doc comment with the intention.

What does "allowAtLeast" do? it has "at least" in it but it appears to slurp the first N entries regardless. Also there are coding style violations:

• Don't need (and please don't put) brackets around comparison expressions. !=/== binds tighter than &&.
• Please don't use iHungarianNotation. "I" or "Skip" would do.
• Variables should be UpperCamelCase.

560

Won't this only affect direct recursion? if A -> B -> A, Callee will never equal Caller, right?

[pbarrio]

James, thank you for the review,

I uploaded the required changes to the patch with some verbose inlined comments. I could not find more succinct explanations, sorry about that. Also, forcing me to find an explanation about the inline levels made me realize that I was inlining one more time than expected (3 times for a maximum level of 2). Code and regression test fixed.

About treating recursion inlining as loop unrolling, it makes sense. Here I deliberately stayed away from the InlineCost analysis, so the heuristics have not been changed at all. However, it is certainly something that we want to model in the cost analysis.

[yinma]

I looked your code, you removed the check in call analyzer and MaxRecursionInl is about inlining history. I would like to know if you set MaxRecursionInl is 0, the inliner will behave exactly like the before without your code?

And MaxRecursionInl is to control the number of history skipped. A different name may be more suitable?

[pbarrio]

Hello Yin, thank you very much for looking at the code.

When MaxRecursionInl is 0, the code behaves differently at -O3, as stated in paragraph 3 of the Summary. I have benchmarked the patch and it does show some performance improvements/regressions, but overall the change is beneficial. The compile time does not seem to be affected and the code size is only slightly affected.

Also, I chose the name of MaxRecursionInl because it maps directly to the amount of recursion inline that is allowed. Now it is implemented as skipping part of the inline history, but it could be implemented in another way and the same flag should be valid.

lib/Transforms/IPO/Inliner.cpp

445

I have added a comment about what "allowAtLeast" (now called SkipFirst) does. The real explanation why I do this is in lines 558-560 of the new patch. This is only a helper function.

560

Correct. All other cases are handled by InlineHistoryIncludes(). This function cannot handle the case of direct recursion disabled because, in the first level of recursion inlining, the inline history is empty. Therefore, InlineHistoryIncludes() would not encounter any previous inline of the callee and the first level would be inlined.

[jmolloy]

lib/Transforms/IPO/Inliner.cpp

64

This comment does give the information needed, but is fairly difficult to parse. Could you please make it better formatted and elaborate?

For example, I didn't understand what "A1", "A2" etc were until my third reading.

[pbarrio]

Thank you James,

Comment about MaxRecursionInl changed. I hope that this one makes a better explanation.

[chandlerc]

Marking this as needing changes still based on the new direction we discussed of eliminating recursion to expose the desired optimizations.

[pbarrio]

Work discontinued.

lib/Analysis/IPA/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
 
   // The called function.
   Function &F;
 
   int Threshold;
   int Cost;
 
   bool IsCallerRecursive;
-  bool IsRecursiveCall;
   bool ExposesReturnsTwice;
   bool HasDynamicAlloca;
   bool ContainsNoDuplicateCall;
   bool HasReturn;
   bool HasIndirectBr;
 
   /// Number of bytes allocated statically by the callee.
   uint64_t AllocatedSize;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitIndirectBrInst(IndirectBrInst &IBI);
   bool visitResumeInst(ResumeInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
 
 public:
   CallAnalyzer(const DataLayout *DL, const TargetTransformInfo &TTI,
                AssumptionCache &AC, Function &Callee, int Threshold)
       : DL(DL), TTI(TTI), AC(AC), F(Callee), Threshold(Threshold), Cost(0),
-        IsCallerRecursive(false), IsRecursiveCall(false),
+        IsCallerRecursive(false),
         ExposesReturnsTwice(false), HasDynamicAlloca(false),
         ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
         AllocatedSize(0), NumInstructions(0), NumVectorInstructions(0),
         FiftyPercentVectorBonus(0), TenPercentVectorBonus(0), VectorBonus(0),
         NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
         NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
         NumInstructionsSimplified(0), SROACostSavings(0),
         SROACostSavingsLost(0) {}
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
       case Intrinsic::memset:
       case Intrinsic::memcpy:
       case Intrinsic::memmove:
         // SROA can usually chew through these intrinsics, but they aren't free.
         return false;
       }
     }
 
-    if (F == CS.getInstruction()->getParent()->getParent()) {
-      // 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.
       Cost += CS.arg_size() * InlineConstants::InstrCost;
 
       // Everything other than inline ASM will also have a significant cost
       // merely from making the call.
       if (!isa<InlineAsm>(CS.getCalledValue()))
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     // all of the per-instruction logic. The visit tree returns true if we
     // consumed the instruction in any way, and false if the instruction's base
     // cost should count against inlining.
     if (Base::visit(I))
       ++NumInstructionsSimplified;
     else
       Cost += InlineConstants::InstrCost;
 
     // If the visit this instruction detected an uninlinable pattern, abort.
-    if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
-        HasIndirectBr)
+    if (ExposesReturnsTwice || HasDynamicAlloca || HasIndirectBr)
       return false;
 
     // If the caller is a recursive function then we don't want to inline
     // functions which allocate a lot of stack space because it would increase
     // the caller stack usage dramatically.
     if (IsCallerRecursive &&
         AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
       return false;
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     // see an indirect branch that ends up being dead code at a particular call
     // site. If the blockaddress escapes the function, e.g., via a global
     // variable, inlining may lead to an invalid cross-function reference.
     if (BB->hasAddressTaken())
       return false;
 
     // Analyze the cost of this block. If we blow through the threshold, this
     // returns false, and we can bail on out.
     if (!analyzeBlock(BB, EphValues)) {
-      if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
-          HasIndirectBr)
+      if (ExposesReturnsTwice || HasDynamicAlloca || HasIndirectBr)
         return false;
 
       // If the caller is a recursive function then we don't want to inline
       // functions which allocate a lot of stack space because it would increase
       // the caller stack usage dramatically.
       if (IsCallerRecursive &&
           AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
         return false;

lib/Transforms/IPO/Inliner.cpp

 static cl::opt<int>
 InlineLimit("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::desc("Threshold for inlining functions with inline hint"));
 
-// We instroduce this threshold to help performance of instrumentation based
+// 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(225),
               cl::desc("Threshold for inlining functions with cold attribute"));
 
+// This threshold controls the maximum amount of recursion inlining. Default = 0
+// For direct recursion, this controls the inline levels: if
+// max-recursion-inline=2 and A->A, then A1 = AA and A2 = A1A1 = AAAA.
+// For indirect recursion: if A->B->C->A, then A1 = AB->C->A1, A2 = ABC->A2,
+// A3 = ABCABC->A3... Steps A1 and A2 of inlining occur regardless of the
+// threshold, because no recursion was encountered. However, step A3 will only
+// happen if max-recursion-inline >= 3. See implementation of
+// InlineHistoryIncludes() to see why.
+static cl::opt<int>
+MaxRecursionInl("max-recursion-inline", cl::Hidden, cl::ZeroOrMore, cl::init(0),
+                cl::desc("Control the maximum levels of recursion inlining"));
+
 // Threshold to use when optsize is specified (and there is no -inline-limit).
 const int OptSizeThreshold = 75;
 
 Inliner::Inliner(char &ID) 
   : CallGraphSCCPass(ID), InlineThreshold(InlineLimit), InsertLifetime(true) {}
 
 Inliner::Inliner(char &ID, int Threshold, bool InsertLifetime)
   : CallGraphSCCPass(ID), InlineThreshold(InlineLimit.getNumOccurrences() > 0 ?
emitAnalysis(
       CS, CS.getCalledFunction()->getName() + Twine(" can be inlined into ") +
               CS.getCaller()->getName() + " with cost=" + Twine(IC.getCost()) +
               " (threshold=" + Twine(IC.getCostDelta() + IC.getCost()) + ")");
   return true;
 }
 
 /// InlineHistoryIncludes - Return true if the specified inline history ID
 /// indicates an inline history that includes the specified function.
+/// SkipFirst allows to skip the check for the first items of the list.
 static bool InlineHistoryIncludes(Function *F, int InlineHistoryID,
-            const SmallVectorImpl<std::pair<Function*, int> > &InlineHistory) {
+                                  const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory,
+                                  int SkipFirst) {
+
+  for (int I = 0; InlineHistoryID != -1 && I < SkipFirst; ++I)
+    InlineHistoryID = InlineHistory[InlineHistoryID].second;
+
   while (InlineHistoryID != -1) {
     assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
            "Invalid inline history ID");
     if (InlineHistory[InlineHistoryID].first == F)
       return true;
     InlineHistoryID = InlineHistory[InlineHistoryID].second;
   }
   return false;
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
         // Update the call graph by deleting the edge from Callee to Caller.
         CG[Caller]->removeCallEdgeFor(CS);
         CS.getInstruction()->eraseFromParent();
         ++NumCallsDeleted;
       } else {
         // We can only inline direct calls to non-declarations.
         if (!Callee || Callee->isDeclaration()) continue;
       
-        // If this call site was obtained by inlining another function, verify
-        // that the include path for the function did not include the callee
-        // itself.  If so, we'd be recursively inlining the same function,
-        // which would provide the same callsites, which would cause us to
-        // infinitely inline.
+        // Check that recursive functions do not surpass the maximum
+        // recursion inlining level: if we find this function inlined
+        // beyond that level in the inline history, abort inlining.
+        if ((MaxRecursionInl == 0) && (Callee == Caller))
+          continue;
         int InlineHistoryID = CallSites[CSi].second;
-        if (InlineHistoryID != -1 &&
-            InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory))
+        if ((InlineHistoryID != -1) &&
+            InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory,
+                                  MaxRecursionInl - 1))
           continue;
-        
         LLVMContext &CallerCtx = Caller->getContext();
 
         // Get DebugLoc to report. CS will be invalid after Inliner.
         DebugLoc DLoc = CS.getInstruction()->getDebugLoc();
 
         // If the policy determines that we should inline this function,
         // try to do so.
         if (!shouldInline(CS)) {

test/Transforms/Inline/inline-recursive-fn.ll

+; RUN: opt -inline -max-recursion-inline=3 -S < %s | FileCheck %s
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
+
+declare void @foo2(i8* %in)
+
+declare i32 @foo(i32 %param)
+
+;--- Check direct recursion
+
+; CHECK-LABEL: define i32 @caller(
+; CHECK-NEXT: entry:
+; CHECK-NOT: alloca
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @foo(i32
+; CHECK-NOT: call i32 @foo(i32
+; CHECK: call i32 @caller(i32
+; CHECK: ret
+define i32 @caller(i32 %param) {
+entry:
+  %t = call i32 @foo(i32 %param)
+  %cmp = icmp eq i32 %t, -1
+  br i1 %cmp, label %exit, label %cont
+
+cont:
+  %r = call i32 @caller(i32 %t)
+  br label %cont
+exit:
+  ret i32 4
+}
+
+
+;--- Check indirect recursion on an SCC of size 2
+
+declare i32 @bar(i32 %param)
+
+; CHECK-LABEL: define void @sccEntry(
+define void @sccEntry(i32 %param) {
+entry:
+  call void @scc1(i32 %param)
+  ret void
+}
+
+
+; CHECK-LABEL: define void @scc1(
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @bar(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @bar(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @bar(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @bar(i32
+; CHECK-NOT: call i32 @foo(i32
+; CHECK-NOT: call i32 @bar(i32
+define void @scc1(i32 %param) {
+entry:
+  %call = call i32 @foo(i32 %param)
+  %cmp = icmp sgt i32 %param, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  call void @scc2(i32 %param)
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+
+; CHECK-LABEL: define void @scc2(
+; CHECK: call i32 @bar(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @bar(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @bar(i32
+; CHECK: call i32 @foo(i32
+; CHECK: call i32 @bar(i32
+; CHECK-NOT: call i32 @foo(i32
+; CHECK-NOT: call i32 @bar(i32
+define void @scc2(i32 %param) {
+entry:
+  %call = call i32 @bar(i32 %param)
+  %cmp = icmp sgt i32 %param, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  %dec = add nsw i32 %param, -1
+  tail call void @scc1(i32 %dec)
+  br label %if.end
+
+if.end:
+  ret void
+}

test/Transforms/Inline/noinline-recursive-fn.ll

-; The inliner should never inline recursive functions into other functions.
-; This effectively is just peeling off the first iteration of a loop, and the
-; inliner heuristics are not set up for this.
+; Check that recursion inlining does not kick in if it is not enabled
+; with -max-recursion-inline
 
 ; RUN: opt -inline -S < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin10.3"
 
 @g = common global i32 0                          ; <i32*> [#uses=1]
 
 define internal void @foo(i32 %x) nounwind ssp {
 entry:
   %0 = icmp slt i32 %x, 0                         ; <i1> [#uses=1]
   br i1 %0, label %return, label %bb
 
 bb:                                               ; preds = %entry
   %1 = sub nsw i32 %x, 1                          ; <i32> [#uses=1]
   call void @foo(i32 %1) nounwind ssp
   store volatile i32 1, i32* @g, align 4
   ret void
 
 return:                                           ; preds = %entry
   ret void
 }
 
 
-;; CHECK-LABEL: @bonk(
-;; CHECK: call void @foo(i32 42)
-define void @bonk() nounwind ssp {
-entry:
-  call void @foo(i32 42) nounwind ssp
-  ret void
-}
-
-
-
 ;; Here is an indirect case that should not be infinitely inlined.
 
 define internal void @f1(i32 %x, i8* %Foo, i8* %Bar) nounwind ssp {
 entry:
   %0 = bitcast i8* %Bar to void (i32, i8*, i8*)*
   %1 = sub nsw i32 %x, 1
   call void %0(i32 %1, i8* %Foo, i8* %Bar) nounwind
   store volatile i32 42, i32* @g, align 4

test/Transforms/Inline/recursive.ll

 ; RUN: opt -inline -S < %s | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
-target triple = "i386-apple-darwin10.0"
 
 ; rdar://10853263
 
+; Check that callees that make use of a big stack size
+; do not get inlined into recursive callers.
+
 ; Make sure that the callee is still here.
 ; CHECK-LABEL: define i32 @callee(
 define i32 @callee(i32 %param) {
  %yyy = alloca [100000 x i8]
  %r = bitcast [100000 x i8]* %yyy to i8*
  call void @foo2(i8* %r)
  ret i32 4
 }
cont:
   br label %cont
 exit:
   ret i32 4
 }
 
 declare void @foo2(i8* %in)
 
 declare i32 @foo(i32 %param)
-