diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -23,6 +23,7 @@ #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/InstIterator.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -43,6 +44,8 @@ STATISTIC(NumAttributesManifested, "Number of abstract attributes manifested in IR"); +STATISTIC(NumFnNoRecurse, "Number of functions marked norecurse"); + // TODO: Determine a good default value. // // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads @@ -86,10 +89,13 @@ if (!Attr.isEnumAttribute()) return; - //switch (Attr.getKindAsEnum()) { - //default: - // return; - //} + switch (Attr.getKindAsEnum()) { + case Attribute::NoRecurse: + NumFnNoRecurse++; + return; + default: + return; + } } /// Helper to identify the correct offset into an attribute list. @@ -241,6 +247,107 @@ return const_cast(this)->getAnchorScope(); } +/// ------------------------ No-Recurse Attributes ---------------------------- + +struct AANoRecurseFunction : public AbstractAttribute, BooleanState { + + /// See AbstractAttribute::AbstractAttribute(...). + AANoRecurseFunction(Function &F, InformationCache &InfoCache) + : AbstractAttribute(F, InfoCache) {} + + /// See AbstractAttribute::getState() + ///{ + AbstractState &getState() override { return *this; } + const AbstractState &getState() const override { return *this; } + ///} + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_FUNCTION; + } + + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; + + /// See AbstractState::getAsStr(). + const std::string getAsStr() const override { + return getAssumed() ? "norecurse" : "may-recurse"; + } + + /// See AbstractAttribute::getAttrKind() + virtual Attribute::AttrKind getAttrKind() const override { return ID; } + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::NoRecurse; +}; + +ChangeStatus AANoRecurseFunction::updateImpl(Attributor &A) { + Function &Fn = getAnchorScope(); + + // The map from instruction opcodes to those instructions in the function. + auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(Fn); + + // Check all "call-like" opcodes. If any call site was found without the + // no-recurse attribute, assume recursion through that call site. + for (unsigned Opcode : + {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, + (unsigned)Instruction::Call}) { + for (Instruction *I : OpcodeInstMap[Opcode]) { + // TODO: This should not be done here but at the intrinsic side! + // See also: https://bugs.llvm.org/show_bug.cgi?id=34696 + // and: + // http://llvm.1065342.n5.nabble.com/llvm-dev-Is-every-intrinsic-norecurse-td109617.html + if (IntrinsicInst *II = dyn_cast(I)) { + switch (II->getIntrinsicID()) { + case Intrinsic::annotation: + case Intrinsic::assume: + case Intrinsic::cos: + case Intrinsic::dbg_addr: + case Intrinsic::dbg_label: + case Intrinsic::dbg_declare: + case Intrinsic::dbg_value: + case Intrinsic::donothing: + case Intrinsic::exp: + case Intrinsic::exp2: + case Intrinsic::expect: + case Intrinsic::fabs: + case Intrinsic::floor: + case Intrinsic::log: + case Intrinsic::log10: + case Intrinsic::log2: + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + case Intrinsic::memset: + case Intrinsic::memcpy: + case Intrinsic::memmove: + case Intrinsic::pow: + case Intrinsic::powi: + case Intrinsic::sin: + case Intrinsic::sqrt: + continue; + default: + break; + } + } + + ImmutableCallSite ICS(I); + assert(ICS && "Found an instruction with call base opcode that did not " + "result in a call site"); + + if (ICS.hasFnAttr(getAttrKind())) + continue; + + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + } + + // This attribute does not rely on other attributes as of now. Consequently, + // there is no need to update the state again. + indicateOptimisticFixpoint(); + return ChangeStatus::UNCHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -383,6 +490,9 @@ Function &F, InformationCache &InfoCache, DenseSet *Whitelist) { + // Every function might be "no-recurse". + registerAA(*new AANoRecurseFunction(F, InfoCache)); + // Walk all instructions to find more attribute opportunities and also // interesting instructions that might be queried by abstract attributes // during their initialization or update. @@ -397,10 +507,25 @@ // to concrete attributes we only cache the ones that are as identified in // the following switch. // Note: There are no concrete attributes now so this is initially empty. - //switch (I.getOpcode()) { - //default: - // break; - //} + switch (I.getOpcode()) { + default: + // The below list of "call-like" opcodes has to be kept in sync with + // CallBase/CallSite and with the abstract attributes using the + // "Attributor::getOpcodeInstMapForFunction(...)" functionality. To verify + // at least the former property we provide an assertion here that should + // immediatly fire once the below list of switch cases is out of sync with + // the call site/base implementation. + assert((!ImmutableCallSite(&I)) && (!isa(&I)) && + "New call site/base instruction type needs to be known in the " + "Attributor!"); + break; + case Instruction::Invoke: + case Instruction::CallBr: + case Instruction::Call: + // Call-like instructions are interesting for AANoRecurseFunction. + IsInterestingOpcode = true; + break; + } if (IsInterestingOpcode) InstOpcodeMap[I.getOpcode()].push_back(&I); if (I.mayReadOrWriteMemory()) diff --git a/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll b/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll --- a/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll +++ b/llvm/test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -tbaa -basicaa -functionattrs -S | FileCheck %s +; RUN: opt < %s -tbaa -basicaa -attributor -attributor-disable=false -functionattrs -S | FileCheck %s ; FunctionAttrs should make use of TBAA. @@ -43,13 +43,13 @@ ; This is unusual, since the function is memcpy, but as above, this ; isn't necessarily invalid. -; CHECK: define void @test2_yes(i8* nocapture %p, i8* nocapture %q, i64 %n) #4 { +; CHECK: define void @test2_yes(i8* nocapture %p, i8* nocapture %q, i64 %n) #0 { define void @test2_yes(i8* %p, i8* %q, i64 %n) nounwind { call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 %n, i1 false), !tbaa !1 ret void } -; CHECK: define void @test2_no(i8* nocapture %p, i8* nocapture readonly %q, i64 %n) #3 { +; CHECK: define void @test2_no(i8* nocapture %p, i8* nocapture readonly %q, i64 %n) #4 { define void @test2_no(i8* %p, i8* %q, i64 %n) nounwind { call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 %n, i1 false), !tbaa !2 ret void @@ -63,7 +63,7 @@ ret i32 %t } -; CHECK: define i32 @test3_no(i8* nocapture %p) #5 { +; CHECK: define i32 @test3_no(i8* nocapture %p) #4 { define i32 @test3_no(i8* %p) nounwind { %t = va_arg i8* %p, i32, !tbaa !2 ret i32 %t @@ -76,9 +76,8 @@ ; CHECK: attributes #1 = { norecurse nounwind writeonly } ; CHECK: attributes #2 = { nounwind readonly } ; CHECK: attributes #3 = { nounwind } -; CHECK: attributes #4 = { nounwind readnone } -; CHECK: attributes #5 = { norecurse nounwind } -; CHECK: attributes #6 = { argmemonly nounwind } +; CHECK: attributes #4 = { norecurse nounwind } +; CHECK: attributes #5 = { argmemonly nounwind } ; Root note. !0 = !{ } diff --git a/llvm/test/Transforms/FunctionAttrs/2010-10-30-volatile.ll b/llvm/test/Transforms/FunctionAttrs/2010-10-30-volatile.ll --- a/llvm/test/Transforms/FunctionAttrs/2010-10-30-volatile.ll +++ b/llvm/test/Transforms/FunctionAttrs/2010-10-30-volatile.ll @@ -1,5 +1,5 @@ -; RUN: opt < %s -functionattrs -S | FileCheck %s -; RUN: opt < %s -passes=function-attrs -S | FileCheck %s +; RUN: opt < %s -attributor -attributor-disable=false -functionattrs -S | FileCheck %s +; RUN: opt < %s -passes='attributor,cgscc(function-attrs)' -attributor-disable=false -S | FileCheck %s ; PR8279 @g = constant i32 1 diff --git a/llvm/test/Transforms/FunctionAttrs/atomic.ll b/llvm/test/Transforms/FunctionAttrs/atomic.ll --- a/llvm/test/Transforms/FunctionAttrs/atomic.ll +++ b/llvm/test/Transforms/FunctionAttrs/atomic.ll @@ -1,5 +1,5 @@ -; RUN: opt -basicaa -functionattrs -S < %s | FileCheck %s -; RUN: opt -aa-pipeline=basic-aa -passes=function-attrs -S < %s | FileCheck %s +; RUN: opt -basicaa -attributor -attributor-disable=false -functionattrs -S < %s | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -passes='attributor,cgscc(function-attrs)' -attributor-disable=false -S < %s | FileCheck %s ; Atomic load/store to local doesn't affect whether a function is ; readnone/readonly. diff --git a/llvm/test/Transforms/FunctionAttrs/norecurse.ll b/llvm/test/Transforms/FunctionAttrs/norecurse.ll --- a/llvm/test/Transforms/FunctionAttrs/norecurse.ll +++ b/llvm/test/Transforms/FunctionAttrs/norecurse.ll @@ -1,5 +1,5 @@ -; 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 -attributor -attributor-disable=false -functionattrs -rpo-functionattrs -S | FileCheck %s +; RUN: opt < %s -aa-pipeline=basic-aa -passes='attributor,cgscc(function-attrs),rpo-functionattrs' -attributor-disable=false -S | FileCheck %s ; CHECK: Function Attrs ; CHECK-SAME: norecurse nounwind readnone @@ -89,3 +89,10 @@ call void @o() ret void } + +; FIXME: This test exposes a bug: https://llvm.org/PR41336 +; CHECK: Function Attrs: norecurse +; CHECK-NEXT: define i32 @leaf_redefinable() +define linkonce_odr i32 @leaf_redefinable() { + ret i32 1 +} diff --git a/llvm/test/Transforms/FunctionAttrs/optnone.ll b/llvm/test/Transforms/FunctionAttrs/optnone.ll --- a/llvm/test/Transforms/FunctionAttrs/optnone.ll +++ b/llvm/test/Transforms/FunctionAttrs/optnone.ll @@ -1,5 +1,5 @@ -; RUN: opt < %s -functionattrs -S | FileCheck %s -; RUN: opt < %s -passes=function-attrs -S | FileCheck %s +; RUN: opt < %s -attributor -attributor-disable=false -functionattrs -S | FileCheck %s +; RUN: opt < %s -passes='attributor,cgscc(function-attrs)' -attributor-disable=false -S | FileCheck %s @x = global i32 0