Index: lib/Analysis/IPA/InlineCost.cpp =================================================================== --- lib/Analysis/IPA/InlineCost.cpp +++ lib/Analysis/IPA/InlineCost.cpp @@ -61,7 +61,6 @@ int Cost; bool IsCallerRecursive; - bool IsRecursiveCall; bool ExposesReturnsTwice; bool HasDynamicAlloca; bool ContainsNoDuplicateCall; @@ -148,7 +147,7 @@ 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), @@ -743,13 +742,6 @@ } } - 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. @@ -918,8 +910,7 @@ 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 @@ -1146,8 +1137,7 @@ // 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 Index: lib/Transforms/IPO/Inliner.cpp =================================================================== --- lib/Transforms/IPO/Inliner.cpp +++ lib/Transforms/IPO/Inliner.cpp @@ -54,13 +54,30 @@ 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 ColdThreshold("inlinecold-threshold", cl::Hidden, cl::init(225), cl::desc("Threshold for inlining functions with cold attribute")); +// This flag puts a limit on the maximum amount of recursion inlining. +// The default is 0, which turns off recursion inlining. +// +// For direct recursion (i.e. A->A or "A calls A"), it bounds the times +// that a function can be inlined into itself. For MaxRecursionInl = 2, +// two inlining steps are performed at most. Step one yields A1 = A+A, +// and step 2 yields A2 = A1+A1 = A+A+A+A. +// +// For indirect recursion (e.g. A->B->A), the first inline step yields +// A1 = A+B and the recursion turns into a direct one: A1->A1. The second +// step yields A2 = A1+A1 = A+B+A+B, with recursion staying as A2->A2. +// Note that the first step will be performed regardless of MaxRecursionInl, +// as inlining B into A does not change recursion. +static cl::opt +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; @@ -429,8 +446,14 @@ /// 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 > &InlineHistory) { + const SmallVectorImpl> &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"); @@ -538,16 +561,17 @@ // 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. Index: test/Transforms/Inline/inline-recursive-fn.ll =================================================================== --- /dev/null +++ test/Transforms/Inline/inline-recursive-fn.ll @@ -0,0 +1,100 @@ +; 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 +} Index: test/Transforms/Inline/noinline-recursive-fn.ll =================================================================== --- test/Transforms/Inline/noinline-recursive-fn.ll +++ test/Transforms/Inline/noinline-recursive-fn.ll @@ -1,6 +1,5 @@ -; 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 @@ -25,16 +24,6 @@ } -;; 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 { Index: test/Transforms/Inline/recursive.ll =================================================================== --- test/Transforms/Inline/recursive.ll +++ test/Transforms/Inline/recursive.ll @@ -1,10 +1,12 @@ ; 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) { @@ -35,4 +37,3 @@ declare void @foo2(i8* %in) declare i32 @foo(i32 %param) -