Index: lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/FunctionAttrs.cpp +++ lib/Transforms/IPO/FunctionAttrs.cpp @@ -50,6 +50,7 @@ STATISTIC(NumNoAlias, "Number of function returns marked noalias"); STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull"); STATISTIC(NumAnnotated, "Number of attributes added to library functions"); +STATISTIC(NumNoRecurse, "Number of functions marked as norecurse"); namespace { typedef SmallSetVector SCCNodeSet; @@ -63,7 +64,12 @@ } bool runOnSCC(CallGraphSCC &SCC) override; - + bool doInitialization(CallGraph &CG) override { + Revisit.clear(); + return false; + } + bool doFinalization(CallGraph &CG) override; + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); @@ -73,6 +79,7 @@ private: TargetLibraryInfo *TLI; + SmallVector Revisit; }; } @@ -943,6 +950,14 @@ } } +static bool setDoesNotRecurse(Function &F) { + if (F.doesNotRecurse()) + return false; + F.setDoesNotRecurse(); + ++NumNoRecurse; + return true; +} + /// Analyze the name and prototype of the given function and set any applicable /// attributes. /// @@ -1746,6 +1761,55 @@ return true; } +static bool addNoRecurseAttrs(const CallGraphSCC &SCC, + SmallVectorImpl &Revisit) { + // Try and identify functions that do not recurse. + + // If the SCC contains multiple nodes we know for sure there is recursion. + if (!SCC.isSingular()) + return false; + + const CallGraphNode *CGN = *SCC.begin(); + Function *F = CGN->getFunction(); + if (!F || F->isDeclaration() || F->doesNotRecurse()) + return false; + + // If all of the calls in F are identifiable and are to norecurse functions, F + // is norecurse. This check also detects self-recursion as F is not currently + // marked norecurse, so any called from F to F will not be marked norecurse. + if (std::all_of(CGN->begin(), CGN->end(), + [](const CallGraphNode::CallRecord &CR) { + Function *F = CR.second->getFunction(); + return F && F->doesNotRecurse(); + })) + // Function calls a potentially recursive function. + return setDoesNotRecurse(*F); + + // We know that F is not obviously recursive, but we haven't been able to + // prove that it doesn't actually recurse. Add it to the Revisit list to try + // again top-down later. + Revisit.push_back(F); + return false; +} + +static bool addNoRecurseAttrsTopDownOnly(Function *F) { + // If F is internal and all uses are in norecurse functions, then F is also + // norecurse. + if (F->doesNotRecurse()) + return false; + if (F->hasInternalLinkage()) { + for (auto *U : F->users()) + if (auto *I = dyn_cast(U)) { + if (!I->getParent()->getParent()->doesNotRecurse()) + return false; + } else { + return false; + } + return setDoesNotRecurse(*F); + } + return false; +} + bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { TLI = &getAnalysis().getTLI(); bool Changed = false; @@ -1793,6 +1857,19 @@ Changed |= addNoAliasAttrs(SCCNodes); Changed |= addNonNullAttrs(SCCNodes, *TLI); } + + Changed |= addNoRecurseAttrs(SCC, Revisit); + return Changed; +} +bool FunctionAttrs::doFinalization(CallGraph &CG) { + bool Changed = false; + // When iterating over SCCs we visit functions in a bottom-up fashion. Some of + // the rules we have for identifying norecurse functions work best with a + // top-down walk, so look again at all the functions we previously marked as + // worth revisiting, in top-down order. + for (auto &F : reverse(Revisit)) + if (F) + Changed |= addNoRecurseAttrsTopDownOnly(cast((Value*)F)); return Changed; } Index: test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll =================================================================== --- test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll +++ test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll @@ -30,7 +30,7 @@ ret void } -; CHECK: define void @test1_no(i32* %p) #1 { +; CHECK: define void @test1_no(i32* %p) #3 { define void @test1_no(i32* %p) nounwind { call void @callee(i32* %p), !tbaa !2 ret void @@ -72,9 +72,11 @@ declare void @callee(i32* %p) nounwind declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1) nounwind -; CHECK: attributes #0 = { nounwind readnone } -; CHECK: attributes #1 = { nounwind } +; CHECK: attributes #0 = { norecurse nounwind readnone } +; CHECK: attributes #1 = { norecurse nounwind } ; CHECK: attributes #2 = { nounwind readonly } +; CHECK: attributes #3 = { nounwind } +; CHECK: attributes #4 = { nounwind argmemonly } ; Root note. !0 = !{ } Index: test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll =================================================================== --- test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll +++ test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll @@ -10,15 +10,16 @@ ret i32 %tmp } -; CHECK: define i32 @g() #0 +; CHECK: define i32 @g() #1 define i32 @g() readonly { ret i32 0 } -; CHECK: define i32 @h() #0 +; CHECK: define i32 @h() #1 define i32 @h() readnone { %tmp = load i32, i32* @x ; [#uses=1] ret i32 %tmp } ; CHECK: attributes #0 = { readnone } +; CHECK: attributes #1 = { norecurse readnone } Index: test/Transforms/FunctionAttrs/2010-10-30-volatile.ll =================================================================== --- test/Transforms/FunctionAttrs/2010-10-30-volatile.ll +++ test/Transforms/FunctionAttrs/2010-10-30-volatile.ll @@ -4,7 +4,9 @@ @g = constant i32 1 define void @foo() { -; CHECK: void @foo() { +; CHECK: void @foo() #0 { %tmp = load volatile i32, i32* @g ret void } + +; CHECK: attributes #0 = { norecurse } Index: test/Transforms/FunctionAttrs/atomic.ll =================================================================== --- test/Transforms/FunctionAttrs/atomic.ll +++ test/Transforms/FunctionAttrs/atomic.ll @@ -19,5 +19,5 @@ ret i32 %r } -; CHECK: attributes #0 = { readnone ssp uwtable } -; CHECK: attributes #1 = { ssp uwtable } +; CHECK: attributes #0 = { norecurse readnone ssp uwtable } +; CHECK: attributes #1 = { norecurse ssp uwtable } Index: test/Transforms/FunctionAttrs/norecurse.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/norecurse.ll @@ -0,0 +1,57 @@ +; RUN: opt < %s -basicaa -functionattrs -S | FileCheck %s + +; CHECK: define i32 @leaf() #0 +define i32 @leaf() { + ret i32 1 +} + +; CHECK: define i32 @self_rec() #1 +define i32 @self_rec() { + %a = call i32 @self_rec() + ret i32 4 +} + +; CHECK: define i32 @indirect_rec() #1 +define i32 @indirect_rec() { + %a = call i32 @indirect_rec2() + ret i32 %a +} +; CHECK: define i32 @indirect_rec2() #1 +define i32 @indirect_rec2() { + %a = call i32 @indirect_rec() + ret i32 %a +} + +; CHECK: define i32 @extern() #1 +define i32 @extern() { + %a = call i32 @k() + ret i32 %a +} +declare i32 @k() readnone + +; CHECK: define internal i32 @called_by_norecurse() #0 +define internal i32 @called_by_norecurse() { + %a = call i32 @k() + ret i32 %a +} +define void @m() norecurse { + %a = call i32 @called_by_norecurse() + ret void +} + +; CHECK: define internal i32 @called_by_norecurse_indirectly() #0 +define internal i32 @called_by_norecurse_indirectly() { + %a = call i32 @k() + ret i32 %a +} +define internal void @o() { + %a = call i32 @called_by_norecurse_indirectly() + ret void +} +define void @p() norecurse { + call void @o() + ret void +} + +; CHECK: attributes #0 = { norecurse readnone } +; CHECK: attributes #1 = { readnone } Index: test/Transforms/FunctionAttrs/optnone.ll =================================================================== --- test/Transforms/FunctionAttrs/optnone.ll +++ test/Transforms/FunctionAttrs/optnone.ll @@ -16,9 +16,11 @@ declare i8 @strlen(i8*) noinline optnone ; CHECK-LABEL: @strlen -; CHECK: (i8*) #1 +; CHECK: (i8*) #2 ; CHECK-LABEL: attributes #0 -; CHECK: = { readnone } +; CHECK: = { norecurse readnone } ; CHECK-LABEL: attributes #1 +; CHECK: = { noinline norecurse optnone } +; CHECK-LABEL: attributes #2 ; CHECK: = { noinline optnone }