Index: llvm/trunk/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO/Attributor.h +++ llvm/trunk/include/llvm/Transforms/IPO/Attributor.h @@ -96,10 +96,12 @@ #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/ADT/MapVector.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/PassManager.h" @@ -524,15 +526,25 @@ struct AnalysisGetter { template typename Analysis::Result *getAnalysis(const Function &F) { - if (!FAM) + if (!MAM || !F.getParent()) + return nullptr; + auto &FAM = MAM->getResult( + const_cast(*F.getParent())) + .getManager(); + return &FAM.getResult(const_cast(F)); + } + + template + typename Analysis::Result *getAnalysis(const Module &M) { + if (!MAM) return nullptr; - return &FAM->getResult(const_cast(F)); + return &MAM->getResult(const_cast(M)); } - AnalysisGetter(FunctionAnalysisManager &FAM) : FAM(&FAM) {} + AnalysisGetter(ModuleAnalysisManager &MAM) : MAM(&MAM) {} AnalysisGetter() {} private: - FunctionAnalysisManager *FAM = nullptr; + ModuleAnalysisManager *MAM = nullptr; }; /// Data structure to hold cached (LLVM-IR) information. @@ -548,7 +560,20 @@ /// reusable, it is advised to inherit from the InformationCache and cast the /// instance down in the abstract attributes. struct InformationCache { - InformationCache(const DataLayout &DL, AnalysisGetter &AG) : DL(DL), AG(AG) {} + InformationCache(const Module &M, AnalysisGetter &AG) + : DL(M.getDataLayout()), AG(AG) { + + CallGraph *CG = AG.getAnalysis(M); + if (!CG) + return; + + DenseMap SccSize; + for (scc_iterator I = scc_begin(CG); !I.isAtEnd(); ++I) { + for (CallGraphNode *Node : *I) + SccSize[Node->getFunction()] = I->size(); + } + SccSizeOpt = std::move(SccSize); + } /// A map type from opcodes to instructions with this opcode. using OpcodeInstMapTy = DenseMap>; @@ -577,6 +602,13 @@ return AG.getAnalysis(F); } + /// Return SCC size on call graph for function \p F. + unsigned getSccSize(const Function &F) { + if (!SccSizeOpt.hasValue()) + return 0; + return (SccSizeOpt.getValue())[&F]; + } + /// Return datalayout used in the module. const DataLayout &getDL() { return DL; } @@ -594,14 +626,15 @@ /// A map from functions to their instructions that may read or write memory. FuncRWInstsMapTy FuncRWInstsMap; - /// A map from functions to their TLI. - /// The datalayout used in the module. const DataLayout &DL; /// Getters for analysis. AnalysisGetter &AG; + /// Cache result for scc size in the call graph + Optional> SccSizeOpt; + /// Give the Attributor access to the members so /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them. friend struct Attributor; Index: llvm/trunk/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/Attributor.cpp +++ llvm/trunk/lib/Transforms/IPO/Attributor.cpp @@ -1530,10 +1530,38 @@ struct AANoRecurseFunction final : AANoRecurseImpl { AANoRecurseFunction(const IRPosition &IRP) : AANoRecurseImpl(IRP) {} + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AANoRecurseImpl::initialize(A); + if (const Function *F = getAnchorScope()) + if (A.getInfoCache().getSccSize(*F) == 1) + return; + indicatePessimisticFixpoint(); + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { - // TODO: Implement this. - return indicatePessimisticFixpoint(); + + auto CheckForNoRecurse = [&](Instruction &I) { + ImmutableCallSite ICS(&I); + if (ICS.hasFnAttr(Attribute::NoRecurse)) + return true; + + const auto &NoRecurseAA = + A.getAAFor(*this, IRPosition::callsite_function(ICS)); + if (!NoRecurseAA.isAssumedNoRecurse()) + return false; + + // Recursion to the same function + if (ICS.getCalledFunction() == getAnchorScope()) + return false; + + return true; + }; + + if (!A.checkForAllCallLikeInstructions(CheckForNoRecurse, *this)) + return indicatePessimisticFixpoint(); + return ChangeStatus::UNCHANGED; } void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) } @@ -3934,6 +3962,9 @@ // Every function might be "no-return". getOrCreateAAFor(FPos); + // Every function might be "no-recurse". + getOrCreateAAFor(FPos); + // Every function might be applicable for Heap-To-Stack conversion. if (EnableHeapToStack) getOrCreateAAFor(FPos); @@ -4113,7 +4144,7 @@ // Create an Attributor and initially empty information cache that is filled // while we identify default attribute opportunities. - InformationCache InfoCache(M.getDataLayout(), AG); + InformationCache InfoCache(M, AG); Attributor A(InfoCache, DepRecInterval); for (Function &F : M) @@ -4149,9 +4180,7 @@ } PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { - auto &FAM = AM.getResult(M).getManager(); - - AnalysisGetter AG(FAM); + AnalysisGetter AG(AM); if (runAttributorOnModule(M, AG)) { // FIXME: Think about passes we will preserve and add them here. return PreservedAnalyses::none(); Index: llvm/trunk/test/Transforms/FunctionAttrs/norecurse.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/norecurse.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/norecurse.ll @@ -1,81 +1,88 @@ -; RUN: opt < %s -basicaa -functionattrs -rpo-functionattrs -S | FileCheck %s -; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs),rpo-functionattrs' -S | FileCheck %s +; RUN: opt < %s -basicaa -functionattrs -rpo-functionattrs -S | FileCheck %s --check-prefixes=CHECK,BOTH +; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs),rpo-functionattrs' -S | FileCheck %s --check-prefixes=CHECK,BOTH +; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR,BOTH ; CHECK: Function Attrs ; CHECK-SAME: norecurse nounwind readnone -; CHECK-NEXT: define i32 @leaf() +; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind willreturn +; BOTH-NEXT: define i32 @leaf() define i32 @leaf() { ret i32 1 } -; CHECK: Function Attrs +; BOTH: Function Attrs ; CHECK-SAME: readnone -; CHECK-NOT: norecurse -; CHECK-NEXT: define i32 @self_rec() +; BOTH-NOT: norecurse +; BOTH-NEXT: define i32 @self_rec() define i32 @self_rec() { %a = call i32 @self_rec() ret i32 4 } -; CHECK: Function Attrs +; BOTH: Function Attrs ; CHECK-SAME: readnone -; CHECK-NOT: norecurse -; CHECK-NEXT: define i32 @indirect_rec() +; BOTH-NOT: norecurse +; BOTH-NEXT: define i32 @indirect_rec() define i32 @indirect_rec() { %a = call i32 @indirect_rec2() ret i32 %a } -; CHECK: Function Attrs +; BOTH: Function Attrs ; CHECK-SAME: readnone -; CHECK-NOT: norecurse -; CHECK-NEXT: define i32 @indirect_rec2() +; BOTH-NOT: norecurse +; BOTH-NEXT: define i32 @indirect_rec2() define i32 @indirect_rec2() { %a = call i32 @indirect_rec() ret i32 %a } -; CHECK: Function Attrs +; BOTH: Function Attrs ; CHECK-SAME: readnone -; CHECK-NOT: norecurse -; CHECK-NEXT: define i32 @extern() +; BOTH-NOT: norecurse +; BOTH-NEXT: define i32 @extern() define i32 @extern() { %a = call i32 @k() ret i32 %a } -; CHECK: Function Attrs -; CHECK-NEXT: declare i32 @k() +; BOTH: Function Attrs +; BOTH-NEXT: declare i32 @k() declare i32 @k() readnone -; CHECK: Function Attrs +; BOTH: Function Attrs ; CHECK-SAME: nounwind -; CHECK-NOT: norecurse +; BOTH-NOT: norecurse ; CHECK-NEXT: define void @intrinsic(i8* nocapture %dest, i8* nocapture readonly %src, i32 %len) +; ATTRIBUTOR-NEXT: define void @intrinsic(i8* nocapture %dest, i8* nocapture %src, i32 %len) define void @intrinsic(i8* %dest, i8* %src, i32 %len) { call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 %len, i1 false) ret void } -; CHECK: Function Attrs -; CHECK-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32 +; BOTH: Function Attrs +; BOTH-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32 declare void @llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i1) -; CHECK: Function Attrs +; BOTH: Function Attrs ; CHECK-SAME: norecurse readnone +; FIXME: missing "norecurse" +; ATTRIBUTOR-SAME: nosync ; CHECK-NEXT: define internal i32 @called_by_norecurse() define internal i32 @called_by_norecurse() { %a = call i32 @k() ret i32 %a } -; CHECK: Function Attrs -; CHECK-NEXT: define void @m() +; BOTH: Function Attrs +; BOTH-NEXT: define void @m() define void @m() norecurse { %a = call i32 @called_by_norecurse() ret void } -; CHECK: Function Attrs +; BOTH: Function Attrs ; CHECK-SAME: norecurse readnone +; FIXME: missing "norecurse" +; ATTRIBUTOR-SAME: nosync ; CHECK-NEXT: define internal i32 @called_by_norecurse_indirectly() define internal i32 @called_by_norecurse_indirectly() { %a = call i32 @k() @@ -89,3 +96,54 @@ call void @o() ret void } + +; ATTRIBUTOR: Function Attrs: nofree nosync nounwind +; ATTRIBUTOR-NEXT: define void @f(i32 %x) +define void @f(i32 %x) { +entry: + %x.addr = alloca i32, align 4 + store i32 %x, i32* %x.addr, align 4 + %0 = load i32, i32* %x.addr, align 4 + %tobool = icmp ne i32 %0, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: + call void @g() norecurse + br label %if.end + +if.end: + ret void +} + +; BOTH: define void @g() +define void @g() norecurse { +entry: + call void @f(i32 0) + ret void +} + +; ATTRIBUTOR-NOT: Function Attrs +; ATTRIBUTOR: define linkonce_odr i32 @leaf_redefinable() +define linkonce_odr i32 @leaf_redefinable() { + ret i32 1 +} + +; Call through a function pointer +; ATTRIBUTOR-NOT: Function Attrs +; ATTRIBUTOR: define i32 @eval_func(i32 (i32)* nocapture %0, i32 %1) +define i32 @eval_func(i32 (i32)* , i32) local_unnamed_addr { + %3 = tail call i32 %0(i32 %1) #2 + ret i32 %3 +} + +declare void @unknown() +; Call an unknown function in a dead block. +; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind willreturn +; ATTRIBUTOR: define i32 @call_unknown_in_dead_block() +define i32 @call_unknown_in_dead_block() local_unnamed_addr { + ret i32 0 +Dead: + tail call void @unknown() + ret i32 1 +} + Index: llvm/trunk/test/Transforms/FunctionAttrs/willreturn.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/willreturn.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/willreturn.ll @@ -1,5 +1,5 @@ ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR -; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR +; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" @@ -11,7 +11,7 @@ ; TEST 1 (positive case) ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NEXT: define void @only_return() -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable willreturn +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable willreturn ; ATTRIBUTOR-NEXT: define void @only_return() define void @only_return() #0 { ret void @@ -59,7 +59,7 @@ ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NOT: willreturn ; FNATTR-NEXT: define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable ; ATTRIBUTOR-NOT: willreturn ; ATTRIBUTOR-NEXT: define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr #0 { @@ -95,7 +95,7 @@ ; FIXME: missing willreturn ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NEXT: define i32 @fact_loop(i32 %0) -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable ; ATTRIBUTOR-NEXT: define i32 @fact_loop(i32 %0) local_unnamed_addr define i32 @fact_loop(i32 %0) local_unnamed_addr #0 { %2 = icmp slt i32 %0, 1 @@ -253,27 +253,24 @@ ; TEST 8 (positive case) ; Check propagation. -; FNATTR: Function Attrs: willreturn +; FNATTR: Function Attrs: norecurse willreturn ; FNATTR-NEXT: declare void @will_return() -; ATTRIBUTOR: Function Attrs: willreturn +; ATTRIBUTOR: Function Attrs: norecurse willreturn ; ATTRIBUTOR-NEXT: declare void @will_return() -declare void @will_return() willreturn +declare void @will_return() willreturn norecurse -; FIXME: missing willreturn -; FNATTR: Function Attrs: noinline nounwind uwtable +; FNATTR: Function Attrs: noinline norecurse nounwind uwtable ; FNATTR-NEXT: define void @f1() -; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn ; ATTRIBUTOR-NEXT: define void @f1() define void @f1() #0 { tail call void @will_return() ret void } -; FIXME: missing willreturn -; FNATTR: Function Attrs: noinline nounwind uwtable +; FNATTR: Function Attrs: noinline norecurse nounwind uwtable ; FNATTR-NEXT: define void @f2() -; FIXME: missing willreturn -; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn ; ATTRIBUTOR-NEXT: define void @f2() define void @f2() #0 { tail call void @f1() @@ -284,10 +281,10 @@ ; TEST 9 (negative case) ; call willreturn function in endless loop. -; FNATTR: Function Attrs: noinline nounwind uwtable +; FNATTR: Function Attrs: noinline norecurse nounwind uwtable ; FNATTR-NOT: willreturn ; FNATTR-NEXT: define void @call_will_return_but_has_loop() -; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable +; ATTRIBUTOR: Function Attrs: noinline norecurse noreturn nounwind uwtable ; ATTRIBUTOR-NOT: willreturn ; ATTRIBUTOR-NEXT: define void @call_will_return_but_has_loop() define void @call_will_return_but_has_loop() #0 { @@ -340,7 +337,7 @@ ; FIXME: missing willreturn ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable ; FNATTR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly %0) -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable ; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly %0) define i32 @loop_constant_trip_count(i32* nocapture readonly %0) #0 { br label %3 @@ -373,7 +370,7 @@ ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable ; FNATTR-NOT: willreturn ; FNATTR-NEXT: define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable ; ATTRIBUTOR-NOT: willreturn ; ATTRIBUTOR-NEXT: define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr #0 { @@ -411,7 +408,7 @@ ; FIXME: missing willreturn ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable ; FNATTR-NEXT: define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable ; ATTRIBUTOR-NEXT: define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr #0 { @@ -442,7 +439,7 @@ ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable ; FNATTR-NEXT: define i32 @multiple_return(i32 %a) -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable willreturn +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable willreturn ; ATTRIBUTOR-NEXT: define i32 @multiple_return(i32 %a) define i32 @multiple_return(i32 %a) #0 { %b = icmp eq i32 %a, 0 @@ -460,7 +457,7 @@ ; 15.1 (positive case) ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define void @unreachable_exit_positive1() -; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable willreturn +; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn ; ATTRIBUTOR-NEXT: define void @unreachable_exit_positive1() define void @unreachable_exit_positive1() #0 { tail call void @will_return() @@ -474,7 +471,7 @@ ; FIXME: missing willreturn ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define i32 @unreachable_exit_positive2(i32 %0) -; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable ; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32 %0) define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #0 { %2 = icmp slt i32 %0, 1 @@ -518,7 +515,7 @@ ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: willreturn ; FNATTR-NEXT: define void @unreachable_exit_negative2() -; ATTRIBUTOR: Function Attrs: nofree noinline noreturn nosync nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline norecurse noreturn nosync nounwind uwtable ; ATTRIBUTOR-NOT: willreturn ; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative2() define void @unreachable_exit_negative2() #0 {