diff --git a/llvm/include/llvm/Analysis/MemoryBuiltins.h b/llvm/include/llvm/Analysis/MemoryBuiltins.h --- a/llvm/include/llvm/Analysis/MemoryBuiltins.h +++ b/llvm/include/llvm/Analysis/MemoryBuiltins.h @@ -83,6 +83,11 @@ bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast = false); +/// Tests if a value is a call or invoke to a library function that +/// reallocates memory (e.g., realloc). +bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + //===----------------------------------------------------------------------===// // malloc Call Utility Functions. // diff --git a/llvm/include/llvm/IR/Attributes.td b/llvm/include/llvm/IR/Attributes.td --- a/llvm/include/llvm/IR/Attributes.td +++ b/llvm/include/llvm/IR/Attributes.td @@ -202,6 +202,10 @@ /// Zero extended before/after call. def ZExt : EnumAttr<"zeroext">; +/// No Free Call +/// This is an experimental attribute. +def NoFree : StrBoolAttr<"nofree">; + /// Target-independent string attributes. def LessPreciseFPMAD : StrBoolAttr<"less-precise-fpmad">; def NoInfsFPMath : StrBoolAttr<"no-infs-fp-math">; diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -251,7 +251,9 @@ /// various places. void identifyDefaultAbstractAttributes( Function &F, InformationCache &InfoCache, - DenseSet *Whitelist = nullptr); + TargetLibraryInfo & , + DenseSet *Whitelist = nullptr + ); private: /// The set of all abstract attributes. diff --git a/llvm/lib/Analysis/MemoryBuiltins.cpp b/llvm/lib/Analysis/MemoryBuiltins.cpp --- a/llvm/lib/Analysis/MemoryBuiltins.cpp +++ b/llvm/lib/Analysis/MemoryBuiltins.cpp @@ -263,6 +263,13 @@ return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue(); } +/// Tests if a value is a call or invoke to a library function that +/// reallocates memory (e.g., realloc). +bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast) { + return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast).hasValue(); +} + /// extractMallocCall - Returns the corresponding CallInst if the instruction /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we /// ignore InvokeInst here. 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 @@ -21,6 +21,7 @@ #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/InstIterator.h" @@ -50,6 +51,8 @@ STATISTIC(NumFnArgumentReturned, "Number of function arguments marked returned"); +STATISTIC(NumFnNoFree, "Number of function marked nofree"); + // TODO: Determine a good default value. // // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads @@ -179,6 +182,14 @@ if (!AreStatisticsEnabled()) return; + if (Attr.isStringAttribute()) { + auto StringAttr = Attr.getKindAsString(); + if (StringAttr == "nofree") { + NumFnNoFree++; + } + return; + } + if (!Attr.isEnumAttribute()) return; switch (Attr.getKindAsEnum()) { @@ -700,6 +711,106 @@ return Changed; } +/// ------------------------ No-Free Attributes ---------------------------- + +class AANoFreeFunction final : public AbstractAttribute, BooleanState { + TargetLibraryInfo &TLI; + +public: + /// See AbstractAttribute::AbstractAttribute(...). + AANoFreeFunction(Function &F, InformationCache &InfoCache, + TargetLibraryInfo &TLI) + : AbstractAttribute(F, InfoCache), TLI(TLI) {} + + /// 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; + } + virtual const std::string getAsStr() const override { + return getAssumed() ? "nofree" : "may-free"; + } + + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; + + /// Return the deduced attributes in \p Attrs. + virtual void + getDeducedAttributes(SmallVectorImpl &Attrs) const override { + LLVMContext &Ctx = AnchoredVal.getContext(); + Attrs.emplace_back(Attribute::get(Ctx, "nofree")); + } + + virtual Attribute::AttrKind getAttrKind() const override { + return Attribute::None; + } + + // FIXME: I tried ((AttrKind) - 2) for ID but I got exception so I use Attribute::None + 1 for now. + static constexpr Attribute::AttrKind ID = + Attribute::AttrKind(Attribute::None + 1); +}; + +ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) { + Function &F = cast(getAnchoredValue()); + + // The map from instruction opcodes to those instructions in the function. + auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); + + for (unsigned Opcode : + {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, + (unsigned)Instruction::Call}) { + for (Instruction *I : OpcodeInstMap[Opcode]) { + if (isFreeCall(I, &TLI) || isReallocLikeFn(I, &TLI)) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + if (IntrinsicInst *II = dyn_cast(I)) { + switch (II->getIntrinsicID()) { + // TODO: Enumerate all nofree intrinsic functions. + // I think we need to deal with intrinsic function in a more appropriate way. + + case Intrinsic::cos: + 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::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("nofree")) { + auto *NoFreeAA = A.getAAFor(*this, *I); + if (!NoFreeAA || !NoFreeAA->isValidState()) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + } + } + } + indicateOptimisticFixpoint(); + return ChangeStatus::UNCHANGED; + } + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -837,7 +948,7 @@ } void Attributor::identifyDefaultAbstractAttributes( - Function &F, InformationCache &InfoCache, + Function &F, InformationCache &InfoCache, TargetLibraryInfo &TLI, DenseSet *Whitelist) { // Return attributes are only appropriate if the return type is non void. @@ -849,6 +960,9 @@ registerAA(*new AAReturnedValuesImpl(F, InfoCache)); } + // Every function might be "no-free". + registerAA(*new AANoFreeFunction(F, InfoCache, TLI)); + // Walk all instructions to find more attribute opportunities and also // interesting instructions that might be queried by abstract attributes // during their initialization or update. @@ -862,6 +976,9 @@ default: break; case Instruction::Ret: // ReturnInst are interesting for AAReturnedValues. + case Instruction::Call: + case Instruction::CallBr: + case Instruction::Invoke: IsInterestingOpcode = true; } if (IsInterestingOpcode) @@ -912,7 +1029,8 @@ /// Pass (Manager) Boilerplate /// ---------------------------------------------------------------------------- -static bool runAttributorOnSCC(SmallVectorImpl &SCC) { +static bool runAttributorOnSCC(SmallVectorImpl &SCC, + TargetLibraryInfo &TLI) { if (DisableAttributor) return false; @@ -949,15 +1067,15 @@ // Populate the Attributor with abstract attribute opportunities in the // function and the information cache with IR information. - A.identifyDefaultAbstractAttributes(*F, InfoCache); + A.identifyDefaultAbstractAttributes(*F, InfoCache, TLI); } return A.run() == ChangeStatus::CHANGED; } PreservedAnalyses AttributorPass::run(LazyCallGraph::SCC &C, - CGSCCAnalysisManager &, LazyCallGraph &, - CGSCCUpdateResult &) { + CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &) { SmallVector SCCFunctions; for (LazyCallGraph::Node &N : C) { @@ -966,7 +1084,13 @@ SCCFunctions.push_back(&Fn); } - if (runAttributorOnSCC(SCCFunctions)) + const ModuleAnalysisManager &MAM = + AM.getResult(C, CG).getManager(); + assert(C.size() > 0 && "Cannot handle an empty SCC!"); + Module &M = *C.begin()->getFunction().getParent(); + auto &TLI = *MAM.getCachedResult(M); + + if (runAttributorOnSCC(SCCFunctions, TLI)) return PreservedAnalyses::none(); return PreservedAnalyses::all(); } @@ -990,12 +1114,15 @@ if (!Fn->isDeclaration()) SCCFunctions.push_back(Fn); - return runAttributorOnSCC(SCCFunctions); + auto &TLI = getAnalysis().getTLI(); + + return runAttributorOnSCC(SCCFunctions, TLI); } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addPreserved(); + AU.addRequired(); CallGraphSCCPass::getAnalysisUsage(AU); } }; @@ -1007,6 +1134,7 @@ char AttributorLegacyPass::ID = 0; INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor", "Deduce and propagate attributes", false, false) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(AttributorLegacyPass, "attributor", "Deduce and propagate attributes", false, false)