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 @@ -25,6 +25,7 @@ #include "llvm/IR/Attributes.h" #include "llvm/IR/CFG.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" @@ -52,6 +53,8 @@ STATISTIC(NumFnNoReturn, "Number of functions marked noreturn"); +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 @@ -182,6 +185,9 @@ case Attribute::NoReturn: NumFnNoReturn++; return; + case Attribute::NoRecurse: + NumFnNoRecurse++; + return; default: return; } @@ -839,6 +845,101 @@ } }; +/// ------------------------ No-Recurse Attributes ---------------------------- + +struct AANoRecurseFunction : public AbstractAttribute, BooleanState { + + /// See AbstractAttribute::AbstractAttribute(...). + AANoRecurseFunction(Function &F) : AbstractAttribute(F) {} + + /// 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() ? "no-recurse" : "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 = cast(getAnchoredValue()); + + // The map from instruction opcodes to those instructions in the function. + auto &OpcodeInstMap = A.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); + if (!ICS.hasFnAttr(getAttrKind())) { + indicateFixpoint(/* Optimistic */ false); + return ChangeStatus::CHANGED; + } + } + } + + indicateFixpoint(/* Optimistic */ true); + return ChangeStatus::UNCHANGED; +} + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -1028,6 +1129,9 @@ registerAA(*new AAReturnedValuesImpl(F)); } + // Every function might be "no-recurse". + registerAA(*new AANoRecurseFunction(F)); + // Every function might be "no-return". registerAA(*new AANoReturnFunction(F)); @@ -1042,6 +1146,21 @@ switch (I.getOpcode()) { default: + // The below list of "call-lile" 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; case Instruction::Ret: // ReturnInst are interesting for AAReturnedValues. IsInterestingOpcode = true; diff --git a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll @@ -362,7 +362,7 @@ ; } ; ; FNATTR: define dso_local double @select_and_phi(double %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] -; ATTRIBUTOR: define dso_local double @select_and_phi(double returned %b) [[NoInlineNoUnwindUwtable]] +; ATTRIBUTOR: define dso_local double @select_and_phi(double returned %b) [[NoInlineNoRecurseNoUnwindUwtable:#[0-9]*]] ; define dso_local double @select_and_phi(double %b) #0 { entry: @@ -417,7 +417,7 @@ ; } ; ; FNATTR: define dso_local double* @bitcast(i32* readnone %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] -; ATTRIBUTOR: define dso_local double* @bitcast(i32* returned %b) [[NoInlineNoUnwindUwtable]] +; ATTRIBUTOR: define dso_local double* @bitcast(i32* returned %b) [[NoInlineNoRecurseNoUnwindUwtable]] ; BOTH: define dso_local double* @bitcast(i32* readnone returned %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] ; define dso_local double* @bitcast(i32* %b) #0 { @@ -437,7 +437,7 @@ ; } ; ; FNATTR: define dso_local double* @bitcasts_select_and_phi(i32* readnone %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] -; ATTRIBUTOR: define dso_local double* @bitcasts_select_and_phi(i32* returned %b) [[NoInlineNoUnwindUwtable]] +; ATTRIBUTOR: define dso_local double* @bitcasts_select_and_phi(i32* returned %b) [[NoInlineNoRecurseNoUnwindUwtable]] ; BOTH: define dso_local double* @bitcasts_select_and_phi(i32* readnone returned %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] ; define dso_local double* @bitcasts_select_and_phi(i32* %b) #0 { @@ -472,7 +472,7 @@ ; } ; ; FNATTR: define dso_local double* @ret_arg_arg_undef(i32* readnone %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] -; ATTRIBUTOR: define dso_local double* @ret_arg_arg_undef(i32* returned %b) [[NoInlineNoUnwindUwtable]] +; ATTRIBUTOR: define dso_local double* @ret_arg_arg_undef(i32* returned %b) [[NoInlineNoRecurseNoUnwindUwtable]] ; BOTH: define dso_local double* @ret_arg_arg_undef(i32* readnone returned %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] ; define dso_local double* @ret_arg_arg_undef(i32* %b) #0 { @@ -507,7 +507,7 @@ ; } ; ; FNATTR: define dso_local double* @ret_undef_arg_arg(i32* readnone %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] -; ATTRIBUTOR: define dso_local double* @ret_undef_arg_arg(i32* returned %b) [[NoInlineNoUnwindUwtable]] +; ATTRIBUTOR: define dso_local double* @ret_undef_arg_arg(i32* returned %b) [[NoInlineNoRecurseNoUnwindUwtable]] ; BOTH: define dso_local double* @ret_undef_arg_arg(i32* readnone returned %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] ; define dso_local double* @ret_undef_arg_arg(i32* %b) #0 { @@ -542,7 +542,7 @@ ; } ; ; FNATTR: define dso_local double* @ret_undef_arg_undef(i32* readnone %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] -; ATTRIBUTOR: define dso_local double* @ret_undef_arg_undef(i32* returned %b) [[NoInlineNoUnwindUwtable]] +; ATTRIBUTOR: define dso_local double* @ret_undef_arg_undef(i32* returned %b) [[NoInlineNoRecurseNoUnwindUwtable]] ; BOTH: define dso_local double* @ret_undef_arg_undef(i32* readnone returned %b) [[NoInlineNoRecurseNoUnwindReadnoneUwtable]] ; define dso_local double* @ret_undef_arg_undef(i32* %b) #0 { 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 @@ -89,3 +89,12 @@ call void @o() ret void } + +; CHECK: Function Attrs +; CHECK-NOT: norecurse +; CHECK-SAME: nounwind readnone +; CHECK-NOT: norecurse +; CHECK-NEXT: define i32 @leaf_redefinable() +define linkonce_odr i32 @leaf_redefinable() { + ret i32 1 +}