diff options
Diffstat (limited to 'include/llvm/Analysis')
32 files changed, 2741 insertions, 750 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 9bfa045..763f372 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -502,7 +502,7 @@ public: /// /// canBasicBlockModify - Return true if it is possible for execution of the - /// specified basic block to modify the value pointed to by Ptr. + /// specified basic block to modify the location Loc. bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc); /// canBasicBlockModify - A convenience wrapper. @@ -510,17 +510,20 @@ public: return canBasicBlockModify(BB, Location(P, Size)); } - /// canInstructionRangeModify - Return true if it is possible for the - /// execution of the specified instructions to modify the value pointed to by - /// Ptr. The instructions to consider are all of the instructions in the - /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. - bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, - const Location &Loc); - - /// canInstructionRangeModify - A convenience wrapper. - bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, - const Value *Ptr, uint64_t Size) { - return canInstructionRangeModify(I1, I2, Location(Ptr, Size)); + /// canInstructionRangeModRef - Return true if it is possible for the + /// execution of the specified instructions to mod\ref (according to the + /// mode) the location Loc. The instructions to consider are all + /// of the instructions in the range of [I1,I2] INCLUSIVE. + /// I1 and I2 must be in the same basic block. + bool canInstructionRangeModRef(const Instruction &I1, + const Instruction &I2, const Location &Loc, + const ModRefResult Mode); + + /// canInstructionRangeModRef - A convenience wrapper. + bool canInstructionRangeModRef(const Instruction &I1, + const Instruction &I2, const Value *Ptr, + uint64_t Size, const ModRefResult Mode) { + return canInstructionRangeModRef(I1, I2, Location(Ptr, Size), Mode); } //===--------------------------------------------------------------------===// diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 036d58d..afa7e6f 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -226,8 +226,8 @@ private: AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { } - AliasSet(const AliasSet &AS) LLVM_DELETED_FUNCTION; - void operator=(const AliasSet &AS) LLVM_DELETED_FUNCTION; + AliasSet(const AliasSet &AS) = delete; + void operator=(const AliasSet &AS) = delete; PointerRec *getSomePointer() const { return PtrList; diff --git a/include/llvm/Analysis/AssumptionCache.h b/include/llvm/Analysis/AssumptionCache.h new file mode 100644 index 0000000..fc1393f --- /dev/null +++ b/include/llvm/Analysis/AssumptionCache.h @@ -0,0 +1,183 @@ +//===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains a pass that keeps track of @llvm.assume intrinsics in +// the functions of a module (allowing assumptions within any function to be +// found cheaply by other parts of the optimizer). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H +#define LLVM_ANALYSIS_ASSUMPTIONCACHE_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" +#include <memory> + +namespace llvm { + +// FIXME: Replace this brittle forward declaration with the include of the new +// PassManager.h when doing so doesn't break the PassManagerBuilder. +template <typename IRUnitT> class AnalysisManager; +class PreservedAnalyses; + +/// \brief A cache of @llvm.assume calls within a function. +/// +/// This cache provides fast lookup of assumptions within a function by caching +/// them and amortizing the cost of scanning for them across all queries. The +/// cache is also conservatively self-updating so that it will never return +/// incorrect results about a function even as the function is being mutated. +/// However, flushing the cache and rebuilding it (or explicitly updating it) +/// may allow it to discover new assumptions. +class AssumptionCache { + /// \brief The function for which this cache is handling assumptions. + /// + /// We track this to lazily populate our assumptions. + Function &F; + + /// \brief Vector of weak value handles to calls of the @llvm.assume + /// intrinsic. + SmallVector<WeakVH, 4> AssumeHandles; + + /// \brief Flag tracking whether we have scanned the function yet. + /// + /// We want to be as lazy about this as possible, and so we scan the function + /// at the last moment. + bool Scanned; + + /// \brief Scan the function for assumptions and add them to the cache. + void scanFunction(); + +public: + /// \brief Construct an AssumptionCache from a function by scanning all of + /// its instructions. + AssumptionCache(Function &F) : F(F), Scanned(false) {} + + /// \brief Add an @llvm.assume intrinsic to this function's cache. + /// + /// The call passed in must be an instruction within this fuction and must + /// not already be in the cache. + void registerAssumption(CallInst *CI); + + /// \brief Clear the cache of @llvm.assume intrinsics for a function. + /// + /// It will be re-scanned the next time it is requested. + void clear() { + AssumeHandles.clear(); + Scanned = false; + } + + /// \brief Access the list of assumption handles currently tracked for this + /// fuction. + /// + /// Note that these produce weak handles that may be null. The caller must + /// handle that case. + /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>> + /// when we can write that to filter out the null values. Then caller code + /// will become simpler. + MutableArrayRef<WeakVH> assumptions() { + if (!Scanned) + scanFunction(); + return AssumeHandles; + } +}; + +/// \brief A function analysis which provides an \c AssumptionCache. +/// +/// This analysis is intended for use with the new pass manager and will vend +/// assumption caches for a given function. +class AssumptionAnalysis { + static char PassID; + +public: + typedef AssumptionCache Result; + + /// \brief Opaque, unique identifier for this analysis pass. + static void *ID() { return (void *)&PassID; } + + /// \brief Provide a name for the analysis for debugging and logging. + static StringRef name() { return "AssumptionAnalysis"; } + + AssumptionAnalysis() {} + AssumptionAnalysis(const AssumptionAnalysis &Arg) {} + AssumptionAnalysis(AssumptionAnalysis &&Arg) {} + AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; } + AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; } + + AssumptionCache run(Function &F) { return AssumptionCache(F); } +}; + +/// \brief Printer pass for the \c AssumptionAnalysis results. +class AssumptionPrinterPass { + raw_ostream &OS; + +public: + explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); + + static StringRef name() { return "AssumptionPrinterPass"; } +}; + +/// \brief An immutable pass that tracks lazily created \c AssumptionCache +/// objects. +/// +/// This is essentially a workaround for the legacy pass manager's weaknesses +/// which associates each assumption cache with Function and clears it if the +/// function is deleted. The nature of the AssumptionCache is that it is not +/// invalidated by any changes to the function body and so this is sufficient +/// to be conservatively correct. +class AssumptionCacheTracker : public ImmutablePass { + /// A callback value handle applied to function objects, which we use to + /// delete our cache of intrinsics for a function when it is deleted. + class FunctionCallbackVH : public CallbackVH { + AssumptionCacheTracker *ACT; + void deleted() override; + + public: + typedef DenseMapInfo<Value *> DMI; + + FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr) + : CallbackVH(V), ACT(ACT) {} + }; + + friend FunctionCallbackVH; + + typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>, + FunctionCallbackVH::DMI> FunctionCallsMap; + FunctionCallsMap AssumptionCaches; + +public: + /// \brief Get the cached assumptions for a function. + /// + /// If no assumptions are cached, this will scan the function. Otherwise, the + /// existing cache will be returned. + AssumptionCache &getAssumptionCache(Function &F); + + AssumptionCacheTracker(); + ~AssumptionCacheTracker(); + + void releaseMemory() override { AssumptionCaches.shrink_and_clear(); } + + void verifyAnalysis() const override; + bool doFinalization(Module &) override { + verifyAnalysis(); + return false; + } + + static char ID; // Pass identification, replacement for typeid +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/Analysis/AssumptionTracker.h b/include/llvm/Analysis/AssumptionTracker.h deleted file mode 100644 index 5a050a8..0000000 --- a/include/llvm/Analysis/AssumptionTracker.h +++ /dev/null @@ -1,128 +0,0 @@ -//===- llvm/Analysis/AssumptionTracker.h - Track @llvm.assume ---*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file contains a pass that keeps track of @llvm.assume intrinsics in -// the functions of a module (allowing assumptions within any function to be -// found cheaply by other parts of the optimizer). -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_ASSUMPTIONTRACKER_H -#define LLVM_ANALYSIS_ASSUMPTIONTRACKER_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/ValueHandle.h" -#include "llvm/Pass.h" -#include <memory> - -namespace llvm { - -/// An immutable pass that tracks @llvm.assume intrinsics in a module. -class AssumptionTracker : public ImmutablePass { - /// A callback value handle applied to function objects, which we use to - /// delete our cache of intrinsics for a function when it is deleted. - class FunctionCallbackVH : public CallbackVH { - AssumptionTracker *AT; - void deleted() override; - - public: - typedef DenseMapInfo<Value *> DMI; - - FunctionCallbackVH(Value *V, AssumptionTracker *AT = nullptr) - : CallbackVH(V), AT(AT) {} - }; - - /// A callback value handle applied to call instructions, which keeps - /// track of the call's parent function so that we can remove a - /// assumption intrinsic call from our cache when the instruction is - /// deleted. - class CallCallbackVH : public CallbackVH { - AssumptionTracker *AT; - void deleted() override; - - // We store the function here because we need it to lookup the set - // containing this handle when the underlying CallInst is being deleted. - Function *F; - - public: - typedef DenseMapInfo<Instruction *> DMI; - - CallCallbackVH(Instruction *I, AssumptionTracker *AT = nullptr) - : CallbackVH(I), AT(AT), F(nullptr) { - if (I != DMI::getEmptyKey() && I != DMI::getTombstoneKey()) - F = I->getParent()->getParent(); - } - - operator CallInst*() const { - Value *V = getValPtr(); - if (V == DMI::getEmptyKey() || V == DMI::getTombstoneKey()) - return reinterpret_cast<CallInst*>(V); - - return cast<CallInst>(V); - } - - CallInst *operator->() const { return cast<CallInst>(getValPtr()); } - CallInst &operator*() const { return *cast<CallInst>(getValPtr()); } - }; - - friend FunctionCallbackVH; - friend CallCallbackVH; - - // FIXME: SmallSet might be better here, but it currently has no iterators. - typedef DenseSet<CallCallbackVH, CallCallbackVH::DMI> CallHandleSet; - typedef DenseMap<FunctionCallbackVH, std::unique_ptr<CallHandleSet>, - FunctionCallbackVH::DMI> FunctionCallsMap; - FunctionCallsMap CachedAssumeCalls; - - /// Scan the provided function for @llvm.assume intrinsic calls. Returns an - /// iterator to the set for this function in the CachedAssumeCalls map. - FunctionCallsMap::iterator scanFunction(Function *F); - -public: - /// Remove the cache of @llvm.assume intrinsics for the given function. - void forgetCachedAssumptions(Function *F); - - /// Add an @llvm.assume intrinsic to the cache for its parent function. - void registerAssumption(CallInst *CI); - - typedef CallHandleSet::iterator assumption_iterator; - typedef iterator_range<assumption_iterator> assumption_range; - - inline assumption_range assumptions(Function *F) { - FunctionCallsMap::iterator I = CachedAssumeCalls.find_as(F); - if (I == CachedAssumeCalls.end()) { - I = scanFunction(F); - } - - return assumption_range(I->second->begin(), I->second->end()); - } - - AssumptionTracker(); - ~AssumptionTracker(); - - void releaseMemory() override { - CachedAssumeCalls.shrink_and_clear(); - } - - void verifyAnalysis() const override; - bool doFinalization(Module &) override { - verifyAnalysis(); - return false; - } - - static char ID; // Pass identification, replacement for typeid -}; - -} // end namespace llvm - -#endif diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 4414c84..89eef68 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -111,6 +111,10 @@ public: void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors, uint32_t Weight); + static uint32_t getBranchWeightStackProtector(bool IsLikely) { + return IsLikely ? (1u << 20) - 1 : 1; + } + private: // Since we allow duplicate edges from one basic block to another, we use // a pair (PredBlock and an index in the successors) to specify an edge. diff --git a/include/llvm/Analysis/CGSCCPassManager.h b/include/llvm/Analysis/CGSCCPassManager.h index 1533b36..0d4fe93 100644 --- a/include/llvm/Analysis/CGSCCPassManager.h +++ b/include/llvm/Analysis/CGSCCPassManager.h @@ -21,135 +21,25 @@ #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H -#include "llvm/IR/PassManager.h" #include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/IR/PassManager.h" namespace llvm { -class CGSCCAnalysisManager; - -class CGSCCPassManager { -public: - // We have to explicitly define all the special member functions because MSVC - // refuses to generate them. - CGSCCPassManager() {} - CGSCCPassManager(CGSCCPassManager &&Arg) : Passes(std::move(Arg.Passes)) {} - CGSCCPassManager &operator=(CGSCCPassManager &&RHS) { - Passes = std::move(RHS.Passes); - return *this; - } - - /// \brief Run all of the CGSCC passes in this pass manager over a SCC. - PreservedAnalyses run(LazyCallGraph::SCC *C, - CGSCCAnalysisManager *AM = nullptr); - - template <typename CGSCCPassT> void addPass(CGSCCPassT Pass) { - Passes.emplace_back(new CGSCCPassModel<CGSCCPassT>(std::move(Pass))); - } - - static StringRef name() { return "CGSCCPassManager"; } - -private: - // Pull in the concept type and model template specialized for SCCs. - typedef detail::PassConcept<LazyCallGraph::SCC *, CGSCCAnalysisManager> - CGSCCPassConcept; - template <typename PassT> - struct CGSCCPassModel - : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT> { - CGSCCPassModel(PassT Pass) - : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT>( - std::move(Pass)) {} - }; - - CGSCCPassManager(const CGSCCPassManager &) LLVM_DELETED_FUNCTION; - CGSCCPassManager &operator=(const CGSCCPassManager &) LLVM_DELETED_FUNCTION; - - std::vector<std::unique_ptr<CGSCCPassConcept>> Passes; -}; - -/// \brief A function analysis manager to coordinate and cache analyses run over -/// a module. -class CGSCCAnalysisManager : public detail::AnalysisManagerBase< - CGSCCAnalysisManager, LazyCallGraph::SCC *> { - friend class detail::AnalysisManagerBase<CGSCCAnalysisManager, - LazyCallGraph::SCC *>; - typedef detail::AnalysisManagerBase<CGSCCAnalysisManager, - LazyCallGraph::SCC *> BaseT; - typedef BaseT::ResultConceptT ResultConceptT; - typedef BaseT::PassConceptT PassConceptT; - -public: - // Most public APIs are inherited from the CRTP base class. - - // We have to explicitly define all the special member functions because MSVC - // refuses to generate them. - CGSCCAnalysisManager() {} - CGSCCAnalysisManager(CGSCCAnalysisManager &&Arg) - : BaseT(std::move(static_cast<BaseT &>(Arg))), - CGSCCAnalysisResults(std::move(Arg.CGSCCAnalysisResults)) {} - CGSCCAnalysisManager &operator=(CGSCCAnalysisManager &&RHS) { - BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); - CGSCCAnalysisResults = std::move(RHS.CGSCCAnalysisResults); - return *this; - } - - /// \brief Returns true if the analysis manager has an empty results cache. - bool empty() const; - - /// \brief Clear the function analysis result cache. - /// - /// This routine allows cleaning up when the set of functions itself has - /// potentially changed, and thus we can't even look up a a result and - /// invalidate it directly. Notably, this does *not* call invalidate - /// functions as there is nothing to be done for them. - void clear(); - -private: - CGSCCAnalysisManager(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION; - CGSCCAnalysisManager & - operator=(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION; - - /// \brief Get a function pass result, running the pass if necessary. - ResultConceptT &getResultImpl(void *PassID, LazyCallGraph::SCC *C); - - /// \brief Get a cached function pass result or return null. - ResultConceptT *getCachedResultImpl(void *PassID, - LazyCallGraph::SCC *C) const; - - /// \brief Invalidate a function pass result. - void invalidateImpl(void *PassID, LazyCallGraph::SCC *C); - - /// \brief Invalidate the results for a function.. - void invalidateImpl(LazyCallGraph::SCC *C, const PreservedAnalyses &PA); +/// \brief The CGSCC pass manager. +/// +/// See the documentation for the PassManager template for details. It runs +/// a sequency of SCC passes over each SCC that the manager is run over. This +/// typedef serves as a convenient way to refer to this construct. +typedef PassManager<LazyCallGraph::SCC> CGSCCPassManager; - /// \brief List of function analysis pass IDs and associated concept pointers. - /// - /// Requires iterators to be valid across appending new entries and arbitrary - /// erases. Provides both the pass ID and concept pointer such that it is - /// half of a bijection and provides storage for the actual result concept. - typedef std::list< - std::pair<void *, std::unique_ptr<detail::AnalysisResultConcept< - LazyCallGraph::SCC *>>>> CGSCCAnalysisResultListT; - - /// \brief Map type from function pointer to our custom list type. - typedef DenseMap<LazyCallGraph::SCC *, CGSCCAnalysisResultListT> - CGSCCAnalysisResultListMapT; - - /// \brief Map from function to a list of function analysis results. - /// - /// Provides linear time removal of all analysis results for a function and - /// the ultimate storage for a particular cached analysis result. - CGSCCAnalysisResultListMapT CGSCCAnalysisResultLists; - - /// \brief Map type from a pair of analysis ID and function pointer to an - /// iterator into a particular result list. - typedef DenseMap<std::pair<void *, LazyCallGraph::SCC *>, - CGSCCAnalysisResultListT::iterator> CGSCCAnalysisResultMapT; - - /// \brief Map from an analysis ID and function to a particular cached - /// analysis result. - CGSCCAnalysisResultMapT CGSCCAnalysisResults; -}; +/// \brief The CGSCC analysis manager. +/// +/// See the documentation for the AnalysisManager template for detail +/// documentation. This typedef serves as a convenient way to refer to this +/// construct in the adaptors and proxies used to integrate this into the larger +/// pass manager infrastructure. +typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager; /// \brief A module analysis which acts as a proxy for a CGSCC analysis /// manager. @@ -187,7 +77,7 @@ public: /// Regardless of whether this analysis is marked as preserved, all of the /// analyses in the \c CGSCCAnalysisManager are potentially invalidated /// based on the set of preserved analyses. - bool invalidate(Module *M, const PreservedAnalyses &PA); + bool invalidate(Module &M, const PreservedAnalyses &PA); private: CGSCCAnalysisManager *CGAM; @@ -195,12 +85,13 @@ public: static void *ID() { return (void *)&PassID; } + static StringRef name() { return "CGSCCAnalysisManagerModuleProxy"; } + explicit CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {} // We have to explicitly define all the special member functions because MSVC // refuses to generate them. - CGSCCAnalysisManagerModuleProxy( - const CGSCCAnalysisManagerModuleProxy &Arg) + CGSCCAnalysisManagerModuleProxy(const CGSCCAnalysisManagerModuleProxy &Arg) : CGAM(Arg.CGAM) {} CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManagerModuleProxy &&Arg) : CGAM(std::move(Arg.CGAM)) {} @@ -219,7 +110,7 @@ public: /// In debug builds, it will also assert that the analysis manager is empty /// as no queries should arrive at the CGSCC analysis manager prior to /// this analysis being requested. - Result run(Module *M); + Result run(Module &M); private: static char PassID; @@ -257,7 +148,7 @@ public: const ModuleAnalysisManager &getManager() const { return *MAM; } /// \brief Handle invalidation by ignoring it, this pass is immutable. - bool invalidate(LazyCallGraph::SCC *) { return false; } + bool invalidate(LazyCallGraph::SCC &) { return false; } private: const ModuleAnalysisManager *MAM; @@ -265,12 +156,13 @@ public: static void *ID() { return (void *)&PassID; } + static StringRef name() { return "ModuleAnalysisManagerCGSCCProxy"; } + ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManager &MAM) : MAM(&MAM) {} // We have to explicitly define all the special member functions because MSVC // refuses to generate them. - ModuleAnalysisManagerCGSCCProxy( - const ModuleAnalysisManagerCGSCCProxy &Arg) + ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManagerCGSCCProxy &Arg) : MAM(Arg.MAM) {} ModuleAnalysisManagerCGSCCProxy(ModuleAnalysisManagerCGSCCProxy &&Arg) : MAM(std::move(Arg.MAM)) {} @@ -283,7 +175,7 @@ public: /// \brief Run the analysis pass and create our proxy result object. /// Nothing to see here, it just forwards the \c MAM reference into the /// result. - Result run(LazyCallGraph::SCC *) { return Result(*MAM); } + Result run(LazyCallGraph::SCC &) { return Result(*MAM); } private: static char PassID; @@ -323,7 +215,7 @@ public: } /// \brief Runs the CGSCC pass across every SCC in the module. - PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM) { + PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) { assert(AM && "We need analyses to compute the call graph!"); // Setup the CGSCC analysis manager from its proxy. @@ -335,15 +227,17 @@ public: PreservedAnalyses PA = PreservedAnalyses::all(); for (LazyCallGraph::SCC &C : CG.postorder_sccs()) { - PreservedAnalyses PassPA = Pass.run(&C, &CGAM); + PreservedAnalyses PassPA = Pass.run(C, &CGAM); // We know that the CGSCC pass couldn't have invalidated any other // SCC's analyses (that's the contract of a CGSCC pass), so - // directly handle the CGSCC analysis manager's invalidation here. + // directly handle the CGSCC analysis manager's invalidation here. We + // also update the preserved set of analyses to reflect that invalidated + // analyses are now safe to preserve. // FIXME: This isn't quite correct. We need to handle the case where the // pass updated the CG, particularly some child of the current SCC, and // invalidate its analyses. - CGAM.invalidate(&C, PassPA); + PassPA = CGAM.invalidate(C, std::move(PassPA)); // Then intersect the preserved set so that invalidation of module // analyses will eventually occur when the module pass completes. @@ -409,7 +303,7 @@ public: /// Regardless of whether this analysis is marked as preserved, all of the /// analyses in the \c FunctionAnalysisManager are potentially invalidated /// based on the set of preserved analyses. - bool invalidate(LazyCallGraph::SCC *C, const PreservedAnalyses &PA); + bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA); private: FunctionAnalysisManager *FAM; @@ -417,6 +311,8 @@ public: static void *ID() { return (void *)&PassID; } + static StringRef name() { return "FunctionAnalysisManagerCGSCCProxy"; } + explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM) : FAM(&FAM) {} // We have to explicitly define all the special member functions because MSVC @@ -441,7 +337,7 @@ public: /// In debug builds, it will also assert that the analysis manager is empty /// as no queries should arrive at the function analysis manager prior to /// this analysis being requested. - Result run(LazyCallGraph::SCC *C); + Result run(LazyCallGraph::SCC &C); private: static char PassID; @@ -479,7 +375,7 @@ public: const CGSCCAnalysisManager &getManager() const { return *CGAM; } /// \brief Handle invalidation by ignoring it, this pass is immutable. - bool invalidate(Function *) { return false; } + bool invalidate(Function &) { return false; } private: const CGSCCAnalysisManager *CGAM; @@ -487,6 +383,8 @@ public: static void *ID() { return (void *)&PassID; } + static StringRef name() { return "CGSCCAnalysisManagerFunctionProxy"; } + CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {} // We have to explicitly define all the special member functions because MSVC @@ -505,7 +403,7 @@ public: /// \brief Run the analysis pass and create our proxy result object. /// Nothing to see here, it just forwards the \c CGAM reference into the /// result. - Result run(Function *) { return Result(*CGAM); } + Result run(Function &) { return Result(*CGAM); } private: static char PassID; @@ -531,7 +429,8 @@ public: : Pass(Arg.Pass) {} CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg) : Pass(std::move(Arg.Pass)) {} - friend void swap(CGSCCToFunctionPassAdaptor &LHS, CGSCCToFunctionPassAdaptor &RHS) { + friend void swap(CGSCCToFunctionPassAdaptor &LHS, + CGSCCToFunctionPassAdaptor &RHS) { using std::swap; swap(LHS.Pass, RHS.Pass); } @@ -541,21 +440,23 @@ public: } /// \brief Runs the function pass across every function in the module. - PreservedAnalyses run(LazyCallGraph::SCC *C, CGSCCAnalysisManager *AM) { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager *AM) { FunctionAnalysisManager *FAM = nullptr; if (AM) // Setup the function analysis manager from its proxy. FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager(); PreservedAnalyses PA = PreservedAnalyses::all(); - for (LazyCallGraph::Node *N : *C) { - PreservedAnalyses PassPA = Pass.run(&N->getFunction(), FAM); + for (LazyCallGraph::Node *N : C) { + PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM); // We know that the function pass couldn't have invalidated any other // function's analyses (that's the contract of a function pass), so // directly handle the function analysis manager's invalidation here. + // Also, update the preserved analyses to reflect that once invalidated + // these can again be preserved. if (FAM) - FAM->invalidate(&N->getFunction(), PassPA); + PassPA = FAM->invalidate(N->getFunction(), std::move(PassPA)); // Then intersect the preserved set so that invalidation of module // analyses will eventually occur when the module pass completes. @@ -585,7 +486,6 @@ CGSCCToFunctionPassAdaptor<FunctionPassT> createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) { return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass))); } - } #endif diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index 76d9073..64d288a 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -273,8 +273,8 @@ private: /// CalledFunctions array of this or other CallGraphNodes. unsigned NumReferences; - CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION; - void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION; + CallGraphNode(const CallGraphNode &) = delete; + void operator=(const CallGraphNode &) = delete; void DropRef() { --NumReferences; } void AddRef() { ++NumReferences; } diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h index 59502df..2f59691 100644 --- a/include/llvm/Analysis/CodeMetrics.h +++ b/include/llvm/Analysis/CodeMetrics.h @@ -20,7 +20,7 @@ #include "llvm/IR/CallSite.h" namespace llvm { -class AssumptionTracker; +class AssumptionCache; class BasicBlock; class Loop; class Function; @@ -93,13 +93,13 @@ struct CodeMetrics { /// \brief Collect a loop's ephemeral values (those used only by an assume /// or similar intrinsics in the loop). - static void collectEphemeralValues(const Loop *L, AssumptionTracker *AT, - SmallPtrSetImpl<const Value*> &EphValues); + static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, + SmallPtrSetImpl<const Value *> &EphValues); /// \brief Collect a functions's ephemeral values (those used only by an /// assume or similar intrinsics in the function). - static void collectEphemeralValues(const Function *L, AssumptionTracker *AT, - SmallPtrSetImpl<const Value*> &EphValues); + static void collectEphemeralValues(const Function *L, AssumptionCache *AC, + SmallPtrSetImpl<const Value *> &EphValues); }; } diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h index 1041e3f..e01aa54 100644 --- a/include/llvm/Analysis/DependenceAnalysis.h +++ b/include/llvm/Analysis/DependenceAnalysis.h @@ -278,8 +278,8 @@ namespace llvm { /// DependenceAnalysis - This class is the main dependence-analysis driver. /// class DependenceAnalysis : public FunctionPass { - void operator=(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; - DependenceAnalysis(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; + void operator=(const DependenceAnalysis &) = delete; + DependenceAnalysis(const DependenceAnalysis &) = delete; public: /// depends - Tests for a dependence between the Src and Dst instructions. /// Returns NULL if no dependence; otherwise, returns a Dependence (or a diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h deleted file mode 100644 index 574c947..0000000 --- a/include/llvm/Analysis/FindUsedTypes.h +++ /dev/null @@ -1,66 +0,0 @@ -//===- llvm/Analysis/FindUsedTypes.h - Find all Types in use ----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass is used to seek out all of the types in use by the program. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_FINDUSEDTYPES_H -#define LLVM_ANALYSIS_FINDUSEDTYPES_H - -#include "llvm/ADT/SetVector.h" -#include "llvm/Pass.h" - -namespace llvm { - -class Type; -class Value; - -class FindUsedTypes : public ModulePass { - SetVector<Type *> UsedTypes; -public: - static char ID; // Pass identification, replacement for typeid - FindUsedTypes() : ModulePass(ID) { - initializeFindUsedTypesPass(*PassRegistry::getPassRegistry()); - } - - /// getTypes - After the pass has been run, return the set containing all of - /// the types used in the module. - /// - const SetVector<Type *> &getTypes() const { return UsedTypes; } - - /// Print the types found in the module. If the optional Module parameter is - /// passed in, then the types are printed symbolically if possible, using the - /// symbol table from the module. - /// - void print(raw_ostream &o, const Module *M) const override; - -private: - /// IncorporateType - Incorporate one type and all of its subtypes into the - /// collection of used types. - /// - void IncorporateType(Type *Ty); - - /// IncorporateValue - Incorporate all of the types used by this value. - /// - void IncorporateValue(const Value *V); - -public: - /// run - This incorporates all types used by the specified module - bool runOnModule(Module &M) override; - - /// getAnalysisUsage - We do not modify anything. - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesAll(); - } -}; - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/FunctionTargetTransformInfo.h b/include/llvm/Analysis/FunctionTargetTransformInfo.h deleted file mode 100644 index c1654cc..0000000 --- a/include/llvm/Analysis/FunctionTargetTransformInfo.h +++ /dev/null @@ -1,49 +0,0 @@ -//===- llvm/Analysis/FunctionTargetTransformInfo.h --------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass wraps a TargetTransformInfo in a FunctionPass so that it can -// forward along the current Function so that we can make target specific -// decisions based on the particular subtarget specified for each Function. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_FUNCTIONTARGETTRANSFORMINFO_H -#define LLVM_ANALYSIS_FUNCTIONTARGETTRANSFORMINFO_H - -#include "llvm/Pass.h" -#include "TargetTransformInfo.h" - -namespace llvm { -class FunctionTargetTransformInfo final : public FunctionPass { -private: - const Function *Fn; - const TargetTransformInfo *TTI; - - FunctionTargetTransformInfo(const FunctionTargetTransformInfo &) - LLVM_DELETED_FUNCTION; - void operator=(const FunctionTargetTransformInfo &) LLVM_DELETED_FUNCTION; - -public: - static char ID; - FunctionTargetTransformInfo(); - - // Implementation boilerplate. - void getAnalysisUsage(AnalysisUsage &AU) const override; - void releaseMemory() override; - bool runOnFunction(Function &F) override; - - // Shimmed functions from TargetTransformInfo. - void - getUnrollingPreferences(Loop *L, - TargetTransformInfo::UnrollingPreferences &UP) const { - TTI->getUnrollingPreferences(Fn, L, UP); - } -}; -} -#endif diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index 81795ba..fdee9f8 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -19,11 +19,11 @@ #include <climits> namespace llvm { -class AssumptionTracker; +class AssumptionCacheTracker; class CallSite; class DataLayout; class Function; -class TargetTransformInfo; +class TargetTransformInfoWrapperPass; namespace InlineConstants { // Various magic constants used to adjust heuristics. @@ -77,7 +77,7 @@ public: } /// \brief Test whether the inline cost is low enough for inlining. - LLVM_EXPLICIT operator bool() const { + explicit operator bool() const { return Cost < Threshold; } @@ -100,8 +100,8 @@ public: /// \brief Cost analyzer used by inliner. class InlineCostAnalysis : public CallGraphSCCPass { - const TargetTransformInfo *TTI; - AssumptionTracker *AT; + TargetTransformInfoWrapperPass *TTIWP; + AssumptionCacheTracker *ACT; public: static char ID; diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index 51f6e85..1ebf981 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -37,7 +37,7 @@ namespace llvm { template<typename T> class ArrayRef; - class AssumptionTracker; + class AssumptionCache; class DominatorTree; class Instruction; class DataLayout; @@ -52,7 +52,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifySubInst - Given operands for a Sub, see if we can @@ -61,35 +61,34 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// Given operands for an FAdd, see if we can fold the result. If not, this /// returns null. Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF, - const DataLayout *TD = nullptr, - const TargetLibraryInfo *TLI = nullptr, - const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, - const Instruction *CxtI = nullptr); + const DataLayout *TD = nullptr, + const TargetLibraryInfo *TLI = nullptr, + const DominatorTree *DT = nullptr, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr); /// Given operands for an FSub, see if we can fold the result. If not, this /// returns null. Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF, - const DataLayout *TD = nullptr, - const TargetLibraryInfo *TLI = nullptr, - const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, - const Instruction *CxtI = nullptr); + const DataLayout *TD = nullptr, + const TargetLibraryInfo *TLI = nullptr, + const DominatorTree *DT = nullptr, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr); /// Given operands for an FMul, see if we can fold the result. If not, this /// returns null. - Value *SimplifyFMulInst(Value *LHS, Value *RHS, - FastMathFlags FMF, + Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyMulInst - Given operands for a Mul, see if we can @@ -97,7 +96,7 @@ namespace llvm { Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifySDivInst - Given operands for an SDiv, see if we can @@ -106,7 +105,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyUDivInst - Given operands for a UDiv, see if we can @@ -115,16 +114,16 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyFDivInst - Given operands for an FDiv, see if we can /// fold the result. If not, this returns null. - Value *SimplifyFDivInst(Value *LHS, Value *RHS, + Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifySRemInst - Given operands for an SRem, see if we can @@ -133,7 +132,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyURemInst - Given operands for a URem, see if we can @@ -142,16 +141,16 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyFRemInst - Given operands for an FRem, see if we can /// fold the result. If not, this returns null. - Value *SimplifyFRemInst(Value *LHS, Value *RHS, + Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyShlInst - Given operands for a Shl, see if we can @@ -160,7 +159,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyLShrInst - Given operands for a LShr, see if we can @@ -169,7 +168,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyAShrInst - Given operands for a AShr, see if we can @@ -178,7 +177,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyAndInst - Given operands for an And, see if we can @@ -186,7 +185,7 @@ namespace llvm { Value *SimplifyAndInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyOrInst - Given operands for an Or, see if we can @@ -194,7 +193,7 @@ namespace llvm { Value *SimplifyOrInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyXorInst - Given operands for a Xor, see if we can @@ -202,7 +201,7 @@ namespace llvm { Value *SimplifyXorInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can @@ -211,7 +210,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, Instruction *CxtI = nullptr); /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can @@ -220,7 +219,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold @@ -229,7 +228,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can @@ -237,7 +236,7 @@ namespace llvm { Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we @@ -247,7 +246,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyTruncInst - Given operands for an TruncInst, see if we can fold @@ -255,7 +254,7 @@ namespace llvm { Value *SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); //=== Helper functions for higher up the class hierarchy. @@ -267,7 +266,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can @@ -276,8 +275,19 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); + /// SimplifyFPBinOp - Given operands for a BinaryOperator, see if we can + /// fold the result. If not, this returns null. + /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the + /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp. + Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, + const FastMathFlags &FMF, + const DataLayout *TD = nullptr, + const TargetLibraryInfo *TLI = nullptr, + const DominatorTree *DT = nullptr, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr); /// \brief Given a function and iterators over arguments, see if we can fold /// the result. @@ -287,7 +297,7 @@ namespace llvm { User::op_iterator ArgEnd, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// \brief Given a function and set of arguments, see if we can fold the @@ -298,7 +308,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr); /// SimplifyInstruction - See if we can compute a simplified version of this @@ -306,8 +316,7 @@ namespace llvm { Value *SimplifyInstruction(Instruction *I, const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr); - + AssumptionCache *AC = nullptr); /// \brief Replace all uses of 'I' with 'SimpleV' and simplify the uses /// recursively. @@ -321,7 +330,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr); + AssumptionCache *AC = nullptr); /// \brief Recursively attempt to simplify an instruction. /// @@ -333,7 +342,7 @@ namespace llvm { const DataLayout *TD = nullptr, const TargetLibraryInfo *TLI = nullptr, const DominatorTree *DT = nullptr, - AssumptionTracker *AT = nullptr); + AssumptionCache *AC = nullptr); } // end namespace llvm #endif diff --git a/include/llvm/Analysis/JumpInstrTableInfo.h b/include/llvm/Analysis/JumpInstrTableInfo.h index 5b0176c..591e794 100644 --- a/include/llvm/Analysis/JumpInstrTableInfo.h +++ b/include/llvm/Analysis/JumpInstrTableInfo.h @@ -16,7 +16,6 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/Pass.h" - #include <vector> namespace llvm { diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h index 9a59844..b0b9068 100644 --- a/include/llvm/Analysis/LazyCallGraph.h +++ b/include/llvm/Analysis/LazyCallGraph.h @@ -46,11 +46,11 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Function.h" #include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" #include <iterator> namespace llvm { -class ModuleAnalysisManager; class PreservedAnalyses; class raw_ostream; @@ -252,6 +252,12 @@ public: /// \brief Test if this SCC is a descendant of \a C. bool isDescendantOf(const SCC &C) const; + /// \brief Short name useful for debugging or logging. + /// + /// We use the name of the first function in the SCC to name the SCC for + /// the purposes of debugging and logging. + StringRef getName() const { return (*begin())->getFunction().getName(); } + ///@{ /// \name Mutation API /// @@ -537,11 +543,13 @@ public: static void *ID() { return (void *)&PassID; } + static StringRef name() { return "Lazy CallGraph Analysis"; } + /// \brief Compute the \c LazyCallGraph for the module \c M. /// /// This just builds the set of entry points to the call graph. The rest is /// built lazily as it is walked. - LazyCallGraph run(Module *M) { return LazyCallGraph(*M); } + LazyCallGraph run(Module &M) { return LazyCallGraph(M); } private: static char PassID; @@ -556,7 +564,7 @@ class LazyCallGraphPrinterPass { public: explicit LazyCallGraphPrinterPass(raw_ostream &OS); - PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM); + PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM); static StringRef name() { return "LazyCallGraphPrinterPass"; } }; diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h index 52cc0d1..51f6b0c 100644 --- a/include/llvm/Analysis/LazyValueInfo.h +++ b/include/llvm/Analysis/LazyValueInfo.h @@ -18,7 +18,7 @@ #include "llvm/Pass.h" namespace llvm { - class AssumptionTracker; + class AssumptionCache; class Constant; class DataLayout; class DominatorTree; @@ -26,16 +26,15 @@ namespace llvm { class TargetLibraryInfo; class Value; -/// LazyValueInfo - This pass computes, caches, and vends lazy value constraint -/// information. +/// This pass computes, caches, and vends lazy value constraint information. class LazyValueInfo : public FunctionPass { - AssumptionTracker *AT; + AssumptionCache *AC; const DataLayout *DL; class TargetLibraryInfo *TLI; DominatorTree *DT; void *PImpl; - LazyValueInfo(const LazyValueInfo&) LLVM_DELETED_FUNCTION; - void operator=(const LazyValueInfo&) LLVM_DELETED_FUNCTION; + LazyValueInfo(const LazyValueInfo&) = delete; + void operator=(const LazyValueInfo&) = delete; public: static char ID; LazyValueInfo() : FunctionPass(ID), PImpl(nullptr) { @@ -43,7 +42,7 @@ public: } ~LazyValueInfo() { assert(!PImpl && "releaseMemory not called"); } - /// Tristate - This is used to return true/false/dunno results. + /// This is used to return true/false/dunno results. enum Tristate { Unknown = -1, False = 0, True = 1 }; @@ -51,33 +50,33 @@ public: // Public query interface. - /// getPredicateOnEdge - Determine whether the specified value comparison - /// with a constant is known to be true or false on the specified CFG edge. + /// Determine whether the specified value comparison with a constant is known + /// to be true or false on the specified CFG edge. /// Pred is a CmpInst predicate. Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI = nullptr); - /// getPredicateAt - Determine whether the specified value comparison - /// with a constant is known to be true or false at the specified instruction + /// Determine whether the specified value comparison with a constant is known + /// to be true or false at the specified instruction /// (from an assume intrinsic). Pred is a CmpInst predicate. Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI); - /// getConstant - Determine whether the specified value is known to be a + /// Determine whether the specified value is known to be a /// constant at the end of the specified block. Return null if not. Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr); - /// getConstantOnEdge - Determine whether the specified value is known to be a + /// Determine whether the specified value is known to be a /// constant on the specified edge. Return null if not. Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI = nullptr); - /// threadEdge - Inform the analysis cache that we have threaded an edge from + /// Inform the analysis cache that we have threaded an edge from /// PredBB to OldSucc to be from PredBB to NewSucc instead. void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc); - /// eraseBlock - Inform the analysis cache that we have erased a block. + /// Inform the analysis cache that we have erased a block. void eraseBlock(BasicBlock *BB); // Implementation boilerplate. diff --git a/include/llvm/Analysis/LibCallSemantics.h b/include/llvm/Analysis/LibCallSemantics.h index 8bd747f..e6427a4 100644 --- a/include/llvm/Analysis/LibCallSemantics.h +++ b/include/llvm/Analysis/LibCallSemantics.h @@ -18,6 +18,7 @@ #include "llvm/Analysis/AliasAnalysis.h" namespace llvm { +class InvokeInst; /// LibCallLocationInfo - This struct describes a set of memory locations that /// are accessed by libcalls. Identification of a location is doing with a @@ -162,6 +163,28 @@ namespace llvm { virtual const LibCallFunctionInfo *getFunctionInfoArray() const = 0; }; + enum class EHPersonality { + Unknown, + GNU_Ada, + GNU_C, + GNU_CXX, + GNU_ObjC, + MSVC_X86SEH, + MSVC_Win64SEH, + MSVC_CXX, + }; + + /// \brief See if the given exception handling personality function is one + /// that we understand. If so, return a description of it; otherwise return + /// Unknown. + EHPersonality classifyEHPersonality(const Value *Pers); + + /// \brief Returns true if this personality function catches asynchronous + /// exceptions. + bool isAsynchronousEHPersonality(EHPersonality Pers); + + bool canSimplifyInvokeNoUnwind(const InvokeInst *II); + } // end namespace llvm #endif diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h new file mode 100644 index 0000000..323af98 --- /dev/null +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -0,0 +1,290 @@ +//===- llvm/Analysis/LoopAccessAnalysis.h -----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the interface for the loop memory dependence framework that +// was originally developed for the Loop Vectorizer. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H +#define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H + +#include "llvm/ADT/EquivalenceClasses.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AliasSetTracker.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" +#include "llvm/Support/raw_ostream.h" + +namespace llvm { + +class Value; +class DataLayout; +class AliasAnalysis; +class ScalarEvolution; +class Loop; +class SCEV; + +/// Optimization analysis message produced during vectorization. Messages inform +/// the user why vectorization did not occur. +class LoopAccessReport { + std::string Message; + const Instruction *Instr; + +protected: + LoopAccessReport(const Twine &Message, const Instruction *I) + : Message(Message.str()), Instr(I) {} + +public: + LoopAccessReport(const Instruction *I = nullptr) : Instr(I) {} + + template <typename A> LoopAccessReport &operator<<(const A &Value) { + raw_string_ostream Out(Message); + Out << Value; + return *this; + } + + const Instruction *getInstr() const { return Instr; } + + std::string &str() { return Message; } + const std::string &str() const { return Message; } + operator Twine() { return Message; } + + /// \brief Emit an analysis note for \p PassName with the debug location from + /// the instruction in \p Message if available. Otherwise use the location of + /// \p TheLoop. + static void emitAnalysis(const LoopAccessReport &Message, + const Function *TheFunction, + const Loop *TheLoop, + const char *PassName); +}; + +/// \brief Collection of parameters shared beetween the Loop Vectorizer and the +/// Loop Access Analysis. +struct VectorizerParams { + /// \brief Maximum SIMD width. + static const unsigned MaxVectorWidth; + + /// \brief VF as overridden by the user. + static unsigned VectorizationFactor; + /// \brief Interleave factor as overridden by the user. + static unsigned VectorizationInterleave; + /// \brief True if force-vector-interleave was specified by the user. + static bool isInterleaveForced(); + + /// \\brief When performing memory disambiguation checks at runtime do not + /// make more than this number of comparisons. + static unsigned RuntimeMemoryCheckThreshold; +}; + +/// \brief Drive the analysis of memory accesses in the loop +/// +/// This class is responsible for analyzing the memory accesses of a loop. It +/// collects the accesses and then its main helper the AccessAnalysis class +/// finds and categorizes the dependences in buildDependenceSets. +/// +/// For memory dependences that can be analyzed at compile time, it determines +/// whether the dependence is part of cycle inhibiting vectorization. This work +/// is delegated to the MemoryDepChecker class. +/// +/// For memory dependences that cannot be determined at compile time, it +/// generates run-time checks to prove independence. This is done by +/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the +/// RuntimePointerCheck class. +class LoopAccessInfo { +public: + /// This struct holds information about the memory runtime legality check that + /// a group of pointers do not overlap. + struct RuntimePointerCheck { + RuntimePointerCheck() : Need(false) {} + + /// Reset the state of the pointer runtime information. + void reset() { + Need = false; + Pointers.clear(); + Starts.clear(); + Ends.clear(); + IsWritePtr.clear(); + DependencySetId.clear(); + AliasSetId.clear(); + } + + /// Insert a pointer and calculate the start and end SCEVs. + void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, + unsigned DepSetId, unsigned ASId, + const ValueToValueMap &Strides); + + /// \brief No run-time memory checking is necessary. + bool empty() const { return Pointers.empty(); } + + /// \brief Decide whether we need to issue a run-time check for pointer at + /// index \p I and \p J to prove their independence. + bool needsChecking(unsigned I, unsigned J) const; + + /// \brief Print the list run-time memory checks necessary. + void print(raw_ostream &OS, unsigned Depth = 0) const; + + /// This flag indicates if we need to add the runtime check. + bool Need; + /// Holds the pointers that we need to check. + SmallVector<TrackingVH<Value>, 2> Pointers; + /// Holds the pointer value at the beginning of the loop. + SmallVector<const SCEV*, 2> Starts; + /// Holds the pointer value at the end of the loop. + SmallVector<const SCEV*, 2> Ends; + /// Holds the information if this pointer is used for writing to memory. + SmallVector<bool, 2> IsWritePtr; + /// Holds the id of the set of pointers that could be dependent because of a + /// shared underlying object. + SmallVector<unsigned, 2> DependencySetId; + /// Holds the id of the disjoint alias set to which this pointer belongs. + SmallVector<unsigned, 2> AliasSetId; + }; + + LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout *DL, + const TargetLibraryInfo *TLI, AliasAnalysis *AA, + DominatorTree *DT, const ValueToValueMap &Strides); + + /// Return true we can analyze the memory accesses in the loop and there are + /// no memory dependence cycles. + bool canVectorizeMemory() const { return CanVecMem; } + + const RuntimePointerCheck *getRuntimePointerCheck() const { + return &PtrRtCheck; + } + + /// Return true if the block BB needs to be predicated in order for the loop + /// to be vectorized. + static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, + DominatorTree *DT); + + /// Returns true if the value V is uniform within the loop. + bool isUniform(Value *V) const; + + unsigned getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; } + unsigned getNumStores() const { return NumStores; } + unsigned getNumLoads() const { return NumLoads;} + + /// \brief Add code that checks at runtime if the accessed arrays overlap. + /// + /// Returns a pair of instructions where the first element is the first + /// instruction generated in possibly a sequence of instructions and the + /// second value is the final comparator value or NULL if no check is needed. + std::pair<Instruction *, Instruction *> + addRuntimeCheck(Instruction *Loc) const; + + /// \brief The diagnostics report generated for the analysis. E.g. why we + /// couldn't analyze the loop. + const Optional<LoopAccessReport> &getReport() const { return Report; } + + /// \brief Print the information about the memory accesses in the loop. + void print(raw_ostream &OS, unsigned Depth = 0) const; + + /// \brief Used to ensure that if the analysis was run with speculating the + /// value of symbolic strides, the client queries it with the same assumption. + /// Only used in DEBUG build but we don't want NDEBUG-dependent ABI. + unsigned NumSymbolicStrides; + +private: + /// \brief Analyze the loop. Substitute symbolic strides using Strides. + void analyzeLoop(const ValueToValueMap &Strides); + + /// \brief Check if the structure of the loop allows it to be analyzed by this + /// pass. + bool canAnalyzeLoop(); + + void emitAnalysis(LoopAccessReport &Message); + + /// We need to check that all of the pointers in this list are disjoint + /// at runtime. + RuntimePointerCheck PtrRtCheck; + Loop *TheLoop; + ScalarEvolution *SE; + const DataLayout *DL; + const TargetLibraryInfo *TLI; + AliasAnalysis *AA; + DominatorTree *DT; + + unsigned NumLoads; + unsigned NumStores; + + unsigned MaxSafeDepDistBytes; + + /// \brief Cache the result of analyzeLoop. + bool CanVecMem; + + /// \brief The diagnostics report generated for the analysis. E.g. why we + /// couldn't analyze the loop. + Optional<LoopAccessReport> Report; +}; + +Value *stripIntegerCast(Value *V); + +///\brief Return the SCEV corresponding to a pointer with the symbolic stride +///replaced with constant one. +/// +/// If \p OrigPtr is not null, use it to look up the stride value instead of \p +/// Ptr. \p PtrToStride provides the mapping between the pointer value and its +/// stride as collected by LoopVectorizationLegality::collectStridedAccess. +const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE, + const ValueToValueMap &PtrToStride, + Value *Ptr, Value *OrigPtr = nullptr); + +/// \brief This analysis provides dependence information for the memory accesses +/// of a loop. +/// +/// It runs the analysis for a loop on demand. This can be initiated by +/// querying the loop access info via LAA::getInfo. getInfo return a +/// LoopAccessInfo object. See this class for the specifics of what information +/// is provided. +class LoopAccessAnalysis : public FunctionPass { +public: + static char ID; + + LoopAccessAnalysis() : FunctionPass(ID) { + initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override; + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + /// \brief Query the result of the loop access information for the loop \p L. + /// + /// If the client speculates (and then issues run-time checks) for the values + /// of symbolic strides, \p Strides provides the mapping (see + /// replaceSymbolicStrideSCEV). If there is no cached result available run + /// the analysis. + const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides); + + void releaseMemory() override { + // Invalidate the cache when the pass is freed. + LoopAccessInfoMap.clear(); + } + + /// \brief Print the result of the analysis when invoked with -analyze. + void print(raw_ostream &OS, const Module *M = nullptr) const override; + +private: + /// \brief The cache. + DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap; + + // The used analysis passes. + ScalarEvolution *SE; + const DataLayout *DL; + const TargetLibraryInfo *TLI; + AliasAnalysis *AA; + DominatorTree *DT; +}; +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index bef03e9..85c2da7 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -42,6 +42,11 @@ namespace llvm { +// FIXME: Replace this brittle forward declaration with the include of the new +// PassManager.h when doing so doesn't break the PassManagerBuilder. +template <typename IRUnitT> class AnalysisManager; +class PreservedAnalyses; + template<typename T> inline void RemoveFromVector(std::vector<T*> &V, T *N) { typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N); @@ -74,9 +79,9 @@ class LoopBase { SmallPtrSet<const BlockT*, 8> DenseBlockSet; - LoopBase(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION; + LoopBase(const LoopBase<BlockT, LoopT> &) = delete; const LoopBase<BlockT, LoopT>& - operator=(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION; + operator=(const LoopBase<BlockT, LoopT> &) = delete; public: /// Loop ctor - This creates an empty loop. LoopBase() : ParentLoop(nullptr) {} @@ -496,18 +501,33 @@ class LoopInfoBase { friend class LoopBase<BlockT, LoopT>; friend class LoopInfo; - void operator=(const LoopInfoBase &) LLVM_DELETED_FUNCTION; - LoopInfoBase(const LoopInfo &) LLVM_DELETED_FUNCTION; + void operator=(const LoopInfoBase &) = delete; + LoopInfoBase(const LoopInfoBase &) = delete; public: LoopInfoBase() { } ~LoopInfoBase() { releaseMemory(); } + LoopInfoBase(LoopInfoBase &&Arg) + : BBMap(std::move(Arg.BBMap)), + TopLevelLoops(std::move(Arg.TopLevelLoops)) { + // We have to clear the arguments top level loops as we've taken ownership. + Arg.TopLevelLoops.clear(); + } + LoopInfoBase &operator=(LoopInfoBase &&RHS) { + BBMap = std::move(RHS.BBMap); + + for (auto *L : TopLevelLoops) + delete L; + TopLevelLoops = std::move(RHS.TopLevelLoops); + RHS.TopLevelLoops.clear(); + return *this; + } + void releaseMemory() { - for (typename std::vector<LoopT *>::iterator I = - TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I) - delete *I; // Delete all of the loops... + BBMap.clear(); - BBMap.clear(); // Reset internal state of analysis + for (auto *L : TopLevelLoops) + delete L; TopLevelLoops.clear(); } @@ -576,8 +596,7 @@ public: /// list with the indicated loop. void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) { - typename std::vector<LoopT *>::iterator I = - std::find(TopLevelLoops.begin(), TopLevelLoops.end(), OldLoop); + auto I = std::find(TopLevelLoops.begin(), TopLevelLoops.end(), OldLoop); assert(I != TopLevelLoops.end() && "Old loop not at top level!"); *I = NewLoop; assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop && @@ -595,7 +614,7 @@ public: /// including all of the Loop objects it is nested in and our mapping from /// BasicBlocks to loops. void removeBlock(BlockT *BB) { - typename DenseMap<BlockT *, LoopT *>::iterator I = BBMap.find(BB); + auto I = BBMap.find(BB); if (I != BBMap.end()) { for (LoopT *L = I->second; L; L = L->getParentLoop()) L->removeBlockFromLoop(BB); @@ -617,8 +636,9 @@ public: void Analyze(DominatorTreeBase<BlockT> &DomTree); // Debugging - void print(raw_ostream &OS) const; + + void verify() const; }; // Implementation in LoopInfoImpl.h @@ -626,99 +646,23 @@ public: __extension__ extern template class LoopInfoBase<BasicBlock, Loop>; #endif -class LoopInfo : public FunctionPass { - LoopInfoBase<BasicBlock, Loop> LI; +class LoopInfo : public LoopInfoBase<BasicBlock, Loop> { + typedef LoopInfoBase<BasicBlock, Loop> BaseT; + friend class LoopBase<BasicBlock, Loop>; - void operator=(const LoopInfo &) LLVM_DELETED_FUNCTION; - LoopInfo(const LoopInfo &) LLVM_DELETED_FUNCTION; + void operator=(const LoopInfo &) = delete; + LoopInfo(const LoopInfo &) = delete; public: - static char ID; // Pass identification, replacement for typeid - - LoopInfo() : FunctionPass(ID) { - initializeLoopInfoPass(*PassRegistry::getPassRegistry()); - } - - LoopInfoBase<BasicBlock, Loop>& getBase() { return LI; } + LoopInfo() {} - /// iterator/begin/end - The interface to the top-level loops in the current - /// function. - /// - typedef LoopInfoBase<BasicBlock, Loop>::iterator iterator; - typedef LoopInfoBase<BasicBlock, Loop>::reverse_iterator reverse_iterator; - inline iterator begin() const { return LI.begin(); } - inline iterator end() const { return LI.end(); } - inline reverse_iterator rbegin() const { return LI.rbegin(); } - inline reverse_iterator rend() const { return LI.rend(); } - bool empty() const { return LI.empty(); } - - /// getLoopFor - Return the inner most loop that BB lives in. If a basic - /// block is in no loop (for example the entry node), null is returned. - /// - inline Loop *getLoopFor(const BasicBlock *BB) const { - return LI.getLoopFor(BB); + LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {} + LoopInfo &operator=(LoopInfo &&RHS) { + BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); + return *this; } - /// operator[] - same as getLoopFor... - /// - inline const Loop *operator[](const BasicBlock *BB) const { - return LI.getLoopFor(BB); - } - - /// getLoopDepth - Return the loop nesting level of the specified block. A - /// depth of 0 means the block is not inside any loop. - /// - inline unsigned getLoopDepth(const BasicBlock *BB) const { - return LI.getLoopDepth(BB); - } - - // isLoopHeader - True if the block is a loop header node - inline bool isLoopHeader(BasicBlock *BB) const { - return LI.isLoopHeader(BB); - } - - /// runOnFunction - Calculate the natural loop information. - /// - bool runOnFunction(Function &F) override; - - void verifyAnalysis() const override; - - void releaseMemory() override { LI.releaseMemory(); } - - void print(raw_ostream &O, const Module* M = nullptr) const override; - - void getAnalysisUsage(AnalysisUsage &AU) const override; - - /// removeLoop - This removes the specified top-level loop from this loop info - /// object. The loop is not deleted, as it will presumably be inserted into - /// another loop. - inline Loop *removeLoop(iterator I) { return LI.removeLoop(I); } - - /// changeLoopFor - Change the top-level loop that contains BB to the - /// specified loop. This should be used by transformations that restructure - /// the loop hierarchy tree. - inline void changeLoopFor(BasicBlock *BB, Loop *L) { - LI.changeLoopFor(BB, L); - } - - /// changeTopLevelLoop - Replace the specified loop in the top-level loops - /// list with the indicated loop. - inline void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) { - LI.changeTopLevelLoop(OldLoop, NewLoop); - } - - /// addTopLevelLoop - This adds the specified loop to the collection of - /// top-level loops. - inline void addTopLevelLoop(Loop *New) { - LI.addTopLevelLoop(New); - } - - /// removeBlock - This method completely removes BB from all data structures, - /// including all of the Loop objects it is nested in and our mapping from - /// BasicBlocks to loops. - void removeBlock(BasicBlock *BB) { - LI.removeBlock(BB); - } + // Most of the public interface is provided via LoopInfoBase. /// updateUnloop - Update LoopInfo after removing the last backedge from a /// loop--now the "unloop". This updates the loop forest and parent loops for @@ -748,7 +692,6 @@ public: } }; - // Allow clients to walk the list of nested loops... template <> struct GraphTraits<const Loop*> { typedef const Loop NodeType; @@ -776,6 +719,65 @@ template <> struct GraphTraits<Loop*> { } }; +/// \brief Analysis pass that exposes the \c LoopInfo for a function. +class LoopAnalysis { + static char PassID; + +public: + typedef LoopInfo Result; + + /// \brief Opaque, unique identifier for this analysis pass. + static void *ID() { return (void *)&PassID; } + + /// \brief Provide a name for the analysis for debugging and logging. + static StringRef name() { return "LoopAnalysis"; } + + LoopAnalysis() {} + LoopAnalysis(const LoopAnalysis &Arg) {} + LoopAnalysis(LoopAnalysis &&Arg) {} + LoopAnalysis &operator=(const LoopAnalysis &RHS) { return *this; } + LoopAnalysis &operator=(LoopAnalysis &&RHS) { return *this; } + + LoopInfo run(Function &F, AnalysisManager<Function> *AM); +}; + +/// \brief Printer pass for the \c LoopAnalysis results. +class LoopPrinterPass { + raw_ostream &OS; + +public: + explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); + + static StringRef name() { return "LoopPrinterPass"; } +}; + +/// \brief The legacy pass manager's analysis pass to compute loop information. +class LoopInfoWrapperPass : public FunctionPass { + LoopInfo LI; + +public: + static char ID; // Pass identification, replacement for typeid + + LoopInfoWrapperPass() : FunctionPass(ID) { + initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); + } + + LoopInfo &getLoopInfo() { return LI; } + const LoopInfo &getLoopInfo() const { return LI; } + + /// \brief Calculate the natural loop information for a given function. + bool runOnFunction(Function &F) override; + + void verifyAnalysis() const override; + + void releaseMemory() override { LI.releaseMemory(); } + + void print(raw_ostream &O, const Module *M = nullptr) const override; + + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + } // End llvm namespace #endif diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index 948be0f..3321f39 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -545,6 +545,25 @@ void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { #endif } +template<class BlockT, class LoopT> +void LoopInfoBase<BlockT, LoopT>::verify() const { + DenseSet<const LoopT*> Loops; + for (iterator I = begin(), E = end(); I != E; ++I) { + assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); + (*I)->verifyLoopNest(&Loops); + } + + // Verify that blocks are mapped to valid loops. +#ifndef NDEBUG + for (auto &Entry : BBMap) { + BlockT *BB = Entry.first; + LoopT *L = Entry.second; + assert(Loops.count(L) && "orphaned loop"); + assert(L->contains(BB) && "orphaned block"); + } +#endif +} + } // End llvm namespace #endif diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 4d315d1..77610b3 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -28,7 +28,7 @@ namespace llvm { class Instruction; class CallSite; class AliasAnalysis; - class AssumptionTracker; + class AssumptionCache; class DataLayout; class MemoryDependenceAnalysis; class PredIteratorCache; @@ -326,7 +326,7 @@ namespace llvm { AliasAnalysis *AA; const DataLayout *DL; DominatorTree *DT; - AssumptionTracker *AT; + AssumptionCache *AC; std::unique_ptr<PredIteratorCache> PredCache; public: @@ -366,12 +366,16 @@ namespace llvm { /// getNonLocalPointerDependency - Perform a full dependency query for an - /// access to the specified (non-volatile) memory location, returning the - /// set of instructions that either define or clobber the value. + /// access to the QueryInst's specified memory location, returning the set + /// of instructions that either define or clobber the value. /// - /// This method assumes the pointer has a "NonLocal" dependency within BB. - void getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, - bool isLoad, BasicBlock *BB, + /// Warning: For a volatile query instruction, the dependencies will be + /// accurate, and thus usable for reordering, but it is never legal to + /// remove the query instruction. + /// + /// This method assumes the pointer has a "NonLocal" dependency within + /// QueryInst's parent basic block. + void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result); /// removeInstruction - Remove an instruction from the dependence analysis, @@ -424,13 +428,15 @@ namespace llvm { MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, BasicBlock::iterator ScanIt, BasicBlock *BB); - bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, + bool getNonLocalPointerDepFromBB(Instruction *QueryInst, + const PHITransAddr &Pointer, const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, SmallVectorImpl<NonLocalDepResult> &Result, DenseMap<BasicBlock*, Value*> &Visited, bool SkipFirstBlock = false); - MemDepResult GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, + MemDepResult GetNonLocalInfoForBlock(Instruction *QueryInst, + const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries); diff --git a/include/llvm/Analysis/PHITransAddr.h b/include/llvm/Analysis/PHITransAddr.h index 0790e97..38730d8 100644 --- a/include/llvm/Analysis/PHITransAddr.h +++ b/include/llvm/Analysis/PHITransAddr.h @@ -18,7 +18,7 @@ #include "llvm/IR/Instruction.h" namespace llvm { - class AssumptionTracker; + class AssumptionCache; class DominatorTree; class DataLayout; class TargetLibraryInfo; @@ -44,13 +44,13 @@ class PHITransAddr { const TargetLibraryInfo *TLI; /// A cache of @llvm.assume calls used by SimplifyInstruction. - AssumptionTracker *AT; - + AssumptionCache *AC; + /// InstInputs - The inputs for our symbolic address. SmallVector<Instruction*, 4> InstInputs; public: - PHITransAddr(Value *addr, const DataLayout *DL, AssumptionTracker *AT) - : Addr(addr), DL(DL), TLI(nullptr), AT(AT) { + PHITransAddr(Value *addr, const DataLayout *DL, AssumptionCache *AC) + : Addr(addr), DL(DL), TLI(nullptr), AC(AC) { // If the address is an instruction, the whole thing is considered an input. if (Instruction *I = dyn_cast<Instruction>(Addr)) InstInputs.push_back(I); diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 10a5605..530faa7 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -162,6 +162,14 @@ namespace llvm { // createJumpInstrTableInfoPass - This creates a pass that stores information // about the jump tables created by JumpInstrTables ImmutablePass *createJumpInstrTableInfoPass(); + + //===--------------------------------------------------------------------===// + // + // createMemDerefPrinter - This pass collects memory dereferenceability + // information and prints it with -analyze. + // + FunctionPass *createMemDerefPrinter(); + } #endif diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index 6ff7f97..1c7f4d3 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -115,8 +115,8 @@ public: typedef typename Tr::RegionT RegionT; private: - RegionNodeBase(const RegionNodeBase &) LLVM_DELETED_FUNCTION; - const RegionNodeBase &operator=(const RegionNodeBase &) LLVM_DELETED_FUNCTION; + RegionNodeBase(const RegionNodeBase &) = delete; + const RegionNodeBase &operator=(const RegionNodeBase &) = delete; /// This is the entry basic block that starts this region node. If this is a /// BasicBlock RegionNode, then entry is just the basic block, that this @@ -261,8 +261,8 @@ class RegionBase : public RegionNodeBase<Tr> { typedef typename InvBlockTraits::ChildIteratorType PredIterTy; friend class RegionInfoBase<Tr>; - RegionBase(const RegionBase &) LLVM_DELETED_FUNCTION; - const RegionBase &operator=(const RegionBase &) LLVM_DELETED_FUNCTION; + RegionBase(const RegionBase &) = delete; + const RegionBase &operator=(const RegionBase &) = delete; // Information necessary to manage this Region. RegionInfoT *RI; @@ -674,8 +674,8 @@ class RegionInfoBase { RegionInfoBase(); virtual ~RegionInfoBase(); - RegionInfoBase(const RegionInfoBase &) LLVM_DELETED_FUNCTION; - const RegionInfoBase &operator=(const RegionInfoBase &) LLVM_DELETED_FUNCTION; + RegionInfoBase(const RegionInfoBase &) = delete; + const RegionInfoBase &operator=(const RegionInfoBase &) = delete; DomTreeT *DT; PostDomTreeT *PDT; diff --git a/include/llvm/Analysis/RegionInfoImpl.h b/include/llvm/Analysis/RegionInfoImpl.h index b5d0bb3..b0dc263 100644 --- a/include/llvm/Analysis/RegionInfoImpl.h +++ b/include/llvm/Analysis/RegionInfoImpl.h @@ -12,11 +12,11 @@ #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H #define LLVM_ANALYSIS_REGIONINFOIMPL_H -#include "llvm/Analysis/RegionInfo.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/PostDominators.h" +#include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/RegionIterator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 893402e..c60cea9 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -35,7 +35,7 @@ namespace llvm { class APInt; - class AssumptionTracker; + class AssumptionCache; class Constant; class ConstantInt; class DominatorTree; @@ -71,8 +71,8 @@ namespace llvm { unsigned short SubclassData; private: - SCEV(const SCEV &) LLVM_DELETED_FUNCTION; - void operator=(const SCEV &) LLVM_DELETED_FUNCTION; + SCEV(const SCEV &) = delete; + void operator=(const SCEV &) = delete; public: /// NoWrapFlags are bitfield indices into SubclassData. @@ -82,12 +82,13 @@ namespace llvm { /// operator. NSW is a misnomer that we use to mean no signed overflow or /// underflow. /// - /// AddRec expression may have a no-self-wraparound <NW> property if the - /// result can never reach the start value. This property is independent of - /// the actual start value and step direction. Self-wraparound is defined - /// purely in terms of the recurrence's loop, step size, and - /// bitwidth. Formally, a recurrence with no self-wraparound satisfies: - /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). + /// AddRec expressions may have a no-self-wraparound <NW> property if, in + /// the integer domain, abs(step) * max-iteration(loop) <= + /// unsigned-max(bitwidth). This means that the recurrence will never reach + /// its start value if the step is non-zero. Computing the same value on + /// each iteration is not considered wrapping, and recurrences with step = 0 + /// are trivially <NW>. <NW> is independent of the sign of step and the + /// value the add recurrence starts with. /// /// Note that NUW and NSW are also valid properties of a recurrence, and /// either implies NW. For convenience, NW will be set for a recurrence @@ -225,7 +226,7 @@ namespace llvm { Function *F; /// The tracker for @llvm.assume intrinsics in this function. - AssumptionTracker *AT; + AssumptionCache *AC; /// LI - The loop information for the function we are currently analyzing. /// @@ -372,14 +373,17 @@ namespace llvm { /// LoopDispositions - Memoized computeLoopDisposition results. DenseMap<const SCEV *, - SmallVector<std::pair<const Loop *, LoopDisposition>, 2> > LoopDispositions; + SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>> + LoopDispositions; /// computeLoopDisposition - Compute a LoopDisposition value. LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); /// BlockDispositions - Memoized computeBlockDisposition results. - DenseMap<const SCEV *, - SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> > BlockDispositions; + DenseMap< + const SCEV *, + SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>> + BlockDispositions; /// computeBlockDisposition - Compute a BlockDisposition value. BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 94e665f..ff82db1 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -14,8 +14,8 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H -#include "llvm/ADT/iterator_range.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/ErrorHandling.h" diff --git a/include/llvm/Analysis/SparsePropagation.h b/include/llvm/Analysis/SparsePropagation.h index 65ff2f6..9ccae5f 100644 --- a/include/llvm/Analysis/SparsePropagation.h +++ b/include/llvm/Analysis/SparsePropagation.h @@ -131,8 +131,8 @@ class SparseSolver { typedef std::pair<BasicBlock*,BasicBlock*> Edge; std::set<Edge> KnownFeasibleEdges; - SparseSolver(const SparseSolver&) LLVM_DELETED_FUNCTION; - void operator=(const SparseSolver&) LLVM_DELETED_FUNCTION; + SparseSolver(const SparseSolver&) = delete; + void operator=(const SparseSolver&) = delete; public: explicit SparseSolver(AbstractLatticeFunction *Lattice) : LatticeFunc(Lattice) {} diff --git a/include/llvm/Analysis/TargetLibraryInfo.h b/include/llvm/Analysis/TargetLibraryInfo.h new file mode 100644 index 0000000..5c6f364 --- /dev/null +++ b/include/llvm/Analysis/TargetLibraryInfo.h @@ -0,0 +1,935 @@ +//===-- TargetLibraryInfo.h - Library information ---------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_TARGETLIBRARYINFO_H +#define LLVM_ANALYSIS_TARGETLIBRARYINFO_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/Triple.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" + +// BEGIN ANDROID-SPECIFIC +#ifdef WIN32 +#ifdef fseeko +#undef fseeko +#endif +#ifdef ftello +#undef ftello +#endif +#endif // WIN32 +// END ANDROID-SPECIFIC + +namespace llvm { +class PreservedAnalyses; + + namespace LibFunc { + enum Func { + /// int _IO_getc(_IO_FILE * __fp); + under_IO_getc, + /// int _IO_putc(int __c, _IO_FILE * __fp); + under_IO_putc, + /// void operator delete[](void*); + ZdaPv, + /// void operator delete[](void*, nothrow); + ZdaPvRKSt9nothrow_t, + /// void operator delete[](void*, unsigned int); + ZdaPvj, + /// void operator delete[](void*, unsigned long); + ZdaPvm, + /// void operator delete(void*); + ZdlPv, + /// void operator delete(void*, nothrow); + ZdlPvRKSt9nothrow_t, + /// void operator delete(void*, unsigned int); + ZdlPvj, + /// void operator delete(void*, unsigned long); + ZdlPvm, + /// void *new[](unsigned int); + Znaj, + /// void *new[](unsigned int, nothrow); + ZnajRKSt9nothrow_t, + /// void *new[](unsigned long); + Znam, + /// void *new[](unsigned long, nothrow); + ZnamRKSt9nothrow_t, + /// void *new(unsigned int); + Znwj, + /// void *new(unsigned int, nothrow); + ZnwjRKSt9nothrow_t, + /// void *new(unsigned long); + Znwm, + /// void *new(unsigned long, nothrow); + ZnwmRKSt9nothrow_t, + /// double __cospi(double x); + cospi, + /// float __cospif(float x); + cospif, + /// int __cxa_atexit(void (*f)(void *), void *p, void *d); + cxa_atexit, + /// void __cxa_guard_abort(guard_t *guard); + /// guard_t is int64_t in Itanium ABI or int32_t on ARM eabi. + cxa_guard_abort, + /// int __cxa_guard_acquire(guard_t *guard); + cxa_guard_acquire, + /// void __cxa_guard_release(guard_t *guard); + cxa_guard_release, + /// int __isoc99_scanf (const char *format, ...) + dunder_isoc99_scanf, + /// int __isoc99_sscanf(const char *s, const char *format, ...) + dunder_isoc99_sscanf, + /// void *__memcpy_chk(void *s1, const void *s2, size_t n, size_t s1size); + memcpy_chk, + /// void *__memmove_chk(void *s1, const void *s2, size_t n, + /// size_t s1size); + memmove_chk, + /// void *__memset_chk(void *s, char v, size_t n, size_t s1size); + memset_chk, + /// double __sincospi_stret(double x); + sincospi_stret, + /// float __sincospif_stret(float x); + sincospif_stret, + /// double __sinpi(double x); + sinpi, + /// float __sinpif(float x); + sinpif, + /// double __sqrt_finite(double x); + sqrt_finite, + /// float __sqrt_finite(float x); + sqrtf_finite, + /// long double __sqrt_finite(long double x); + sqrtl_finite, + /// char *__stpcpy_chk(char *s1, const char *s2, size_t s1size); + stpcpy_chk, + /// char *__stpncpy_chk(char *s1, const char *s2, size_t n, + /// size_t s1size); + stpncpy_chk, + /// char *__strcpy_chk(char *s1, const char *s2, size_t s1size); + strcpy_chk, + /// char * __strdup(const char *s); + dunder_strdup, + /// char *__strncpy_chk(char *s1, const char *s2, size_t n, + /// size_t s1size); + strncpy_chk, + /// char *__strndup(const char *s, size_t n); + dunder_strndup, + /// char * __strtok_r(char *s, const char *delim, char **save_ptr); + dunder_strtok_r, + /// int abs(int j); + abs, + /// int access(const char *path, int amode); + access, + /// double acos(double x); + acos, + /// float acosf(float x); + acosf, + /// double acosh(double x); + acosh, + /// float acoshf(float x); + acoshf, + /// long double acoshl(long double x); + acoshl, + /// long double acosl(long double x); + acosl, + /// double asin(double x); + asin, + /// float asinf(float x); + asinf, + /// double asinh(double x); + asinh, + /// float asinhf(float x); + asinhf, + /// long double asinhl(long double x); + asinhl, + /// long double asinl(long double x); + asinl, + /// double atan(double x); + atan, + /// double atan2(double y, double x); + atan2, + /// float atan2f(float y, float x); + atan2f, + /// long double atan2l(long double y, long double x); + atan2l, + /// float atanf(float x); + atanf, + /// double atanh(double x); + atanh, + /// float atanhf(float x); + atanhf, + /// long double atanhl(long double x); + atanhl, + /// long double atanl(long double x); + atanl, + /// double atof(const char *str); + atof, + /// int atoi(const char *str); + atoi, + /// long atol(const char *str); + atol, + /// long long atoll(const char *nptr); + atoll, + /// int bcmp(const void *s1, const void *s2, size_t n); + bcmp, + /// void bcopy(const void *s1, void *s2, size_t n); + bcopy, + /// void bzero(void *s, size_t n); + bzero, + /// void *calloc(size_t count, size_t size); + calloc, + /// double cbrt(double x); + cbrt, + /// float cbrtf(float x); + cbrtf, + /// long double cbrtl(long double x); + cbrtl, + /// double ceil(double x); + ceil, + /// float ceilf(float x); + ceilf, + /// long double ceill(long double x); + ceill, + /// int chmod(const char *path, mode_t mode); + chmod, + /// int chown(const char *path, uid_t owner, gid_t group); + chown, + /// void clearerr(FILE *stream); + clearerr, + /// int closedir(DIR *dirp); + closedir, + /// double copysign(double x, double y); + copysign, + /// float copysignf(float x, float y); + copysignf, + /// long double copysignl(long double x, long double y); + copysignl, + /// double cos(double x); + cos, + /// float cosf(float x); + cosf, + /// double cosh(double x); + cosh, + /// float coshf(float x); + coshf, + /// long double coshl(long double x); + coshl, + /// long double cosl(long double x); + cosl, + /// char *ctermid(char *s); + ctermid, + /// double exp(double x); + exp, + /// double exp10(double x); + exp10, + /// float exp10f(float x); + exp10f, + /// long double exp10l(long double x); + exp10l, + /// double exp2(double x); + exp2, + /// float exp2f(float x); + exp2f, + /// long double exp2l(long double x); + exp2l, + /// float expf(float x); + expf, + /// long double expl(long double x); + expl, + /// double expm1(double x); + expm1, + /// float expm1f(float x); + expm1f, + /// long double expm1l(long double x); + expm1l, + /// double fabs(double x); + fabs, + /// float fabsf(float x); + fabsf, + /// long double fabsl(long double x); + fabsl, + /// int fclose(FILE *stream); + fclose, + /// FILE *fdopen(int fildes, const char *mode); + fdopen, + /// int feof(FILE *stream); + feof, + /// int ferror(FILE *stream); + ferror, + /// int fflush(FILE *stream); + fflush, + /// int ffs(int i); + ffs, + /// int ffsl(long int i); + ffsl, + /// int ffsll(long long int i); + ffsll, + /// int fgetc(FILE *stream); + fgetc, + /// int fgetpos(FILE *stream, fpos_t *pos); + fgetpos, + /// char *fgets(char *s, int n, FILE *stream); + fgets, + /// int fileno(FILE *stream); + fileno, + /// int fiprintf(FILE *stream, const char *format, ...); + fiprintf, + /// void flockfile(FILE *file); + flockfile, + /// double floor(double x); + floor, + /// float floorf(float x); + floorf, + /// long double floorl(long double x); + floorl, + /// double fmax(double x, double y); + fmax, + /// float fmaxf(float x, float y); + fmaxf, + /// long double fmaxl(long double x, long double y); + fmaxl, + /// double fmin(double x, double y); + fmin, + /// float fminf(float x, float y); + fminf, + /// long double fminl(long double x, long double y); + fminl, + /// double fmod(double x, double y); + fmod, + /// float fmodf(float x, float y); + fmodf, + /// long double fmodl(long double x, long double y); + fmodl, + /// FILE *fopen(const char *filename, const char *mode); + fopen, + /// FILE *fopen64(const char *filename, const char *opentype) + fopen64, + /// int fprintf(FILE *stream, const char *format, ...); + fprintf, + /// int fputc(int c, FILE *stream); + fputc, + /// int fputs(const char *s, FILE *stream); + fputs, + /// size_t fread(void *ptr, size_t size, size_t nitems, FILE *stream); + fread, + /// void free(void *ptr); + free, + /// double frexp(double num, int *exp); + frexp, + /// float frexpf(float num, int *exp); + frexpf, + /// long double frexpl(long double num, int *exp); + frexpl, + /// int fscanf(FILE *stream, const char *format, ... ); + fscanf, + /// int fseek(FILE *stream, long offset, int whence); + fseek, + /// int fseeko(FILE *stream, off_t offset, int whence); + fseeko, + /// int fseeko64(FILE *stream, off64_t offset, int whence) + fseeko64, + /// int fsetpos(FILE *stream, const fpos_t *pos); + fsetpos, + /// int fstat(int fildes, struct stat *buf); + fstat, + /// int fstat64(int filedes, struct stat64 *buf) + fstat64, + /// int fstatvfs(int fildes, struct statvfs *buf); + fstatvfs, + /// int fstatvfs64(int fildes, struct statvfs64 *buf); + fstatvfs64, + /// long ftell(FILE *stream); + ftell, + /// off_t ftello(FILE *stream); + ftello, + /// off64_t ftello64(FILE *stream) + ftello64, + /// int ftrylockfile(FILE *file); + ftrylockfile, + /// void funlockfile(FILE *file); + funlockfile, + /// size_t fwrite(const void *ptr, size_t size, size_t nitems, + /// FILE *stream); + fwrite, + /// int getc(FILE *stream); + getc, + /// int getc_unlocked(FILE *stream); + getc_unlocked, + /// int getchar(void); + getchar, + /// char *getenv(const char *name); + getenv, + /// int getitimer(int which, struct itimerval *value); + getitimer, + /// int getlogin_r(char *name, size_t namesize); + getlogin_r, + /// struct passwd *getpwnam(const char *name); + getpwnam, + /// char *gets(char *s); + gets, + /// int gettimeofday(struct timeval *tp, void *tzp); + gettimeofday, + /// uint32_t htonl(uint32_t hostlong); + htonl, + /// uint16_t htons(uint16_t hostshort); + htons, + /// int iprintf(const char *format, ...); + iprintf, + /// int isascii(int c); + isascii, + /// int isdigit(int c); + isdigit, + /// long int labs(long int j); + labs, + /// int lchown(const char *path, uid_t owner, gid_t group); + lchown, + /// double ldexp(double x, int n); + ldexp, + /// float ldexpf(float x, int n); + ldexpf, + /// long double ldexpl(long double x, int n); + ldexpl, + /// long long int llabs(long long int j); + llabs, + /// double log(double x); + log, + /// double log10(double x); + log10, + /// float log10f(float x); + log10f, + /// long double log10l(long double x); + log10l, + /// double log1p(double x); + log1p, + /// float log1pf(float x); + log1pf, + /// long double log1pl(long double x); + log1pl, + /// double log2(double x); + log2, + /// float log2f(float x); + log2f, + /// double long double log2l(long double x); + log2l, + /// double logb(double x); + logb, + /// float logbf(float x); + logbf, + /// long double logbl(long double x); + logbl, + /// float logf(float x); + logf, + /// long double logl(long double x); + logl, + /// int lstat(const char *path, struct stat *buf); + lstat, + /// int lstat64(const char *path, struct stat64 *buf); + lstat64, + /// void *malloc(size_t size); + malloc, + /// void *memalign(size_t boundary, size_t size); + memalign, + /// void *memccpy(void *s1, const void *s2, int c, size_t n); + memccpy, + /// void *memchr(const void *s, int c, size_t n); + memchr, + /// int memcmp(const void *s1, const void *s2, size_t n); + memcmp, + /// void *memcpy(void *s1, const void *s2, size_t n); + memcpy, + /// void *memmove(void *s1, const void *s2, size_t n); + memmove, + // void *memrchr(const void *s, int c, size_t n); + memrchr, + /// void *memset(void *b, int c, size_t len); + memset, + /// void memset_pattern16(void *b, const void *pattern16, size_t len); + memset_pattern16, + /// int mkdir(const char *path, mode_t mode); + mkdir, + /// time_t mktime(struct tm *timeptr); + mktime, + /// double modf(double x, double *iptr); + modf, + /// float modff(float, float *iptr); + modff, + /// long double modfl(long double value, long double *iptr); + modfl, + /// double nearbyint(double x); + nearbyint, + /// float nearbyintf(float x); + nearbyintf, + /// long double nearbyintl(long double x); + nearbyintl, + /// uint32_t ntohl(uint32_t netlong); + ntohl, + /// uint16_t ntohs(uint16_t netshort); + ntohs, + /// int open(const char *path, int oflag, ... ); + open, + /// int open64(const char *filename, int flags[, mode_t mode]) + open64, + /// DIR *opendir(const char *dirname); + opendir, + /// int pclose(FILE *stream); + pclose, + /// void perror(const char *s); + perror, + /// FILE *popen(const char *command, const char *mode); + popen, + /// int posix_memalign(void **memptr, size_t alignment, size_t size); + posix_memalign, + /// double pow(double x, double y); + pow, + /// float powf(float x, float y); + powf, + /// long double powl(long double x, long double y); + powl, + /// ssize_t pread(int fildes, void *buf, size_t nbyte, off_t offset); + pread, + /// int printf(const char *format, ...); + printf, + /// int putc(int c, FILE *stream); + putc, + /// int putchar(int c); + putchar, + /// int puts(const char *s); + puts, + /// ssize_t pwrite(int fildes, const void *buf, size_t nbyte, + /// off_t offset); + pwrite, + /// void qsort(void *base, size_t nel, size_t width, + /// int (*compar)(const void *, const void *)); + qsort, + /// ssize_t read(int fildes, void *buf, size_t nbyte); + read, + /// ssize_t readlink(const char *path, char *buf, size_t bufsize); + readlink, + /// void *realloc(void *ptr, size_t size); + realloc, + /// void *reallocf(void *ptr, size_t size); + reallocf, + /// char *realpath(const char *file_name, char *resolved_name); + realpath, + /// int remove(const char *path); + remove, + /// int rename(const char *old, const char *new); + rename, + /// void rewind(FILE *stream); + rewind, + /// double rint(double x); + rint, + /// float rintf(float x); + rintf, + /// long double rintl(long double x); + rintl, + /// int rmdir(const char *path); + rmdir, + /// double round(double x); + round, + /// float roundf(float x); + roundf, + /// long double roundl(long double x); + roundl, + /// int scanf(const char *restrict format, ... ); + scanf, + /// void setbuf(FILE *stream, char *buf); + setbuf, + /// int setitimer(int which, const struct itimerval *value, + /// struct itimerval *ovalue); + setitimer, + /// int setvbuf(FILE *stream, char *buf, int type, size_t size); + setvbuf, + /// double sin(double x); + sin, + /// float sinf(float x); + sinf, + /// double sinh(double x); + sinh, + /// float sinhf(float x); + sinhf, + /// long double sinhl(long double x); + sinhl, + /// long double sinl(long double x); + sinl, + /// int siprintf(char *str, const char *format, ...); + siprintf, + /// int snprintf(char *s, size_t n, const char *format, ...); + snprintf, + /// int sprintf(char *str, const char *format, ...); + sprintf, + /// double sqrt(double x); + sqrt, + /// float sqrtf(float x); + sqrtf, + /// long double sqrtl(long double x); + sqrtl, + /// int sscanf(const char *s, const char *format, ... ); + sscanf, + /// int stat(const char *path, struct stat *buf); + stat, + /// int stat64(const char *path, struct stat64 *buf); + stat64, + /// int statvfs(const char *path, struct statvfs *buf); + statvfs, + /// int statvfs64(const char *path, struct statvfs64 *buf) + statvfs64, + /// char *stpcpy(char *s1, const char *s2); + stpcpy, + /// char *stpncpy(char *s1, const char *s2, size_t n); + stpncpy, + /// int strcasecmp(const char *s1, const char *s2); + strcasecmp, + /// char *strcat(char *s1, const char *s2); + strcat, + /// char *strchr(const char *s, int c); + strchr, + /// int strcmp(const char *s1, const char *s2); + strcmp, + /// int strcoll(const char *s1, const char *s2); + strcoll, + /// char *strcpy(char *s1, const char *s2); + strcpy, + /// size_t strcspn(const char *s1, const char *s2); + strcspn, + /// char *strdup(const char *s1); + strdup, + /// size_t strlen(const char *s); + strlen, + /// int strncasecmp(const char *s1, const char *s2, size_t n); + strncasecmp, + /// char *strncat(char *s1, const char *s2, size_t n); + strncat, + /// int strncmp(const char *s1, const char *s2, size_t n); + strncmp, + /// char *strncpy(char *s1, const char *s2, size_t n); + strncpy, + /// char *strndup(const char *s1, size_t n); + strndup, + /// size_t strnlen(const char *s, size_t maxlen); + strnlen, + /// char *strpbrk(const char *s1, const char *s2); + strpbrk, + /// char *strrchr(const char *s, int c); + strrchr, + /// size_t strspn(const char *s1, const char *s2); + strspn, + /// char *strstr(const char *s1, const char *s2); + strstr, + /// double strtod(const char *nptr, char **endptr); + strtod, + /// float strtof(const char *nptr, char **endptr); + strtof, + // char *strtok(char *s1, const char *s2); + strtok, + // char *strtok_r(char *s, const char *sep, char **lasts); + strtok_r, + /// long int strtol(const char *nptr, char **endptr, int base); + strtol, + /// long double strtold(const char *nptr, char **endptr); + strtold, + /// long long int strtoll(const char *nptr, char **endptr, int base); + strtoll, + /// unsigned long int strtoul(const char *nptr, char **endptr, int base); + strtoul, + /// unsigned long long int strtoull(const char *nptr, char **endptr, + /// int base); + strtoull, + /// size_t strxfrm(char *s1, const char *s2, size_t n); + strxfrm, + /// int system(const char *command); + system, + /// double tan(double x); + tan, + /// float tanf(float x); + tanf, + /// double tanh(double x); + tanh, + /// float tanhf(float x); + tanhf, + /// long double tanhl(long double x); + tanhl, + /// long double tanl(long double x); + tanl, + /// clock_t times(struct tms *buffer); + times, + /// FILE *tmpfile(void); + tmpfile, + /// FILE *tmpfile64(void) + tmpfile64, + /// int toascii(int c); + toascii, + /// double trunc(double x); + trunc, + /// float truncf(float x); + truncf, + /// long double truncl(long double x); + truncl, + /// int uname(struct utsname *name); + uname, + /// int ungetc(int c, FILE *stream); + ungetc, + /// int unlink(const char *path); + unlink, + /// int unsetenv(const char *name); + unsetenv, + /// int utime(const char *path, const struct utimbuf *times); + utime, + /// int utimes(const char *path, const struct timeval times[2]); + utimes, + /// void *valloc(size_t size); + valloc, + /// int vfprintf(FILE *stream, const char *format, va_list ap); + vfprintf, + /// int vfscanf(FILE *stream, const char *format, va_list arg); + vfscanf, + /// int vprintf(const char *restrict format, va_list ap); + vprintf, + /// int vscanf(const char *format, va_list arg); + vscanf, + /// int vsnprintf(char *s, size_t n, const char *format, va_list ap); + vsnprintf, + /// int vsprintf(char *s, const char *format, va_list ap); + vsprintf, + /// int vsscanf(const char *s, const char *format, va_list arg); + vsscanf, + /// ssize_t write(int fildes, const void *buf, size_t nbyte); + write, + + NumLibFuncs + }; + } + +/// \brief Implementation of the target library information. +/// +/// This class constructs tables that hold the target library information and +/// make it available. However, it is somewhat expensive to compute and only +/// depends on the triple. So users typicaly interact with the \c +/// TargetLibraryInfo wrapper below. +class TargetLibraryInfoImpl { + friend class TargetLibraryInfo; + + unsigned char AvailableArray[(LibFunc::NumLibFuncs+3)/4]; + llvm::DenseMap<unsigned, std::string> CustomNames; + static const char* StandardNames[LibFunc::NumLibFuncs]; + + enum AvailabilityState { + StandardName = 3, // (memset to all ones) + CustomName = 1, + Unavailable = 0 // (memset to all zeros) + }; + void setState(LibFunc::Func F, AvailabilityState State) { + AvailableArray[F/4] &= ~(3 << 2*(F&3)); + AvailableArray[F/4] |= State << 2*(F&3); + } + AvailabilityState getState(LibFunc::Func F) const { + return static_cast<AvailabilityState>((AvailableArray[F/4] >> 2*(F&3)) & 3); + } + +public: + TargetLibraryInfoImpl(); + explicit TargetLibraryInfoImpl(const Triple &T); + + // Provide value semantics. + TargetLibraryInfoImpl(const TargetLibraryInfoImpl &TLI); + TargetLibraryInfoImpl(TargetLibraryInfoImpl &&TLI); + TargetLibraryInfoImpl &operator=(const TargetLibraryInfoImpl &TLI); + TargetLibraryInfoImpl &operator=(TargetLibraryInfoImpl &&TLI); + + /// \brief Searches for a particular function name. + /// + /// If it is one of the known library functions, return true and set F to the + /// corresponding value. + bool getLibFunc(StringRef funcName, LibFunc::Func &F) const; + + /// \brief Forces a function to be marked as unavailable. + void setUnavailable(LibFunc::Func F) { + setState(F, Unavailable); + } + + /// \brief Forces a function to be marked as available. + void setAvailable(LibFunc::Func F) { + setState(F, StandardName); + } + + /// \brief Forces a function to be marked as available and provide an + /// alternate name that must be used. + void setAvailableWithName(LibFunc::Func F, StringRef Name) { + if (StandardNames[F] != Name) { + setState(F, CustomName); + CustomNames[F] = Name; + assert(CustomNames.find(F) != CustomNames.end()); + } else { + setState(F, StandardName); + } + } + + /// \brief Disables all builtins. + /// + /// This can be used for options like -fno-builtin. + void disableAllFunctions(); +}; + +/// \brief Provides information about what library functions are available for +/// the current target. +/// +/// This both allows optimizations to handle them specially and frontends to +/// disable such optimizations through -fno-builtin etc. +class TargetLibraryInfo { + friend class TargetLibraryAnalysis; + friend class TargetLibraryInfoWrapperPass; + + const TargetLibraryInfoImpl *Impl; + +public: + explicit TargetLibraryInfo(const TargetLibraryInfoImpl &Impl) : Impl(&Impl) {} + + // Provide value semantics. + TargetLibraryInfo(const TargetLibraryInfo &TLI) : Impl(TLI.Impl) {} + TargetLibraryInfo(TargetLibraryInfo &&TLI) : Impl(TLI.Impl) {} + TargetLibraryInfo &operator=(const TargetLibraryInfo &TLI) { + Impl = TLI.Impl; + return *this; + } + TargetLibraryInfo &operator=(TargetLibraryInfo &&TLI) { + Impl = TLI.Impl; + return *this; + } + + /// \brief Searches for a particular function name. + /// + /// If it is one of the known library functions, return true and set F to the + /// corresponding value. + bool getLibFunc(StringRef funcName, LibFunc::Func &F) const { + return Impl->getLibFunc(funcName, F); + } + + /// \brief Tests wether a library function is available. + bool has(LibFunc::Func F) const { + return Impl->getState(F) != TargetLibraryInfoImpl::Unavailable; + } + + /// \brief Tests if the function is both available and a candidate for + /// optimized code generation. + bool hasOptimizedCodeGen(LibFunc::Func F) const { + if (Impl->getState(F) == TargetLibraryInfoImpl::Unavailable) + return false; + switch (F) { + default: break; + case LibFunc::copysign: case LibFunc::copysignf: case LibFunc::copysignl: + case LibFunc::fabs: case LibFunc::fabsf: case LibFunc::fabsl: + case LibFunc::sin: case LibFunc::sinf: case LibFunc::sinl: + case LibFunc::cos: case LibFunc::cosf: case LibFunc::cosl: + case LibFunc::sqrt: case LibFunc::sqrtf: case LibFunc::sqrtl: + case LibFunc::sqrt_finite: case LibFunc::sqrtf_finite: + case LibFunc::sqrtl_finite: + case LibFunc::fmax: case LibFunc::fmaxf: case LibFunc::fmaxl: + case LibFunc::fmin: case LibFunc::fminf: case LibFunc::fminl: + case LibFunc::floor: case LibFunc::floorf: case LibFunc::floorl: + case LibFunc::nearbyint: case LibFunc::nearbyintf: case LibFunc::nearbyintl: + case LibFunc::ceil: case LibFunc::ceilf: case LibFunc::ceill: + case LibFunc::rint: case LibFunc::rintf: case LibFunc::rintl: + case LibFunc::round: case LibFunc::roundf: case LibFunc::roundl: + case LibFunc::trunc: case LibFunc::truncf: case LibFunc::truncl: + case LibFunc::log2: case LibFunc::log2f: case LibFunc::log2l: + case LibFunc::exp2: case LibFunc::exp2f: case LibFunc::exp2l: + case LibFunc::memcmp: case LibFunc::strcmp: case LibFunc::strcpy: + case LibFunc::stpcpy: case LibFunc::strlen: case LibFunc::strnlen: + case LibFunc::memchr: + return true; + } + return false; + } + + StringRef getName(LibFunc::Func F) const { + auto State = Impl->getState(F); + if (State == TargetLibraryInfoImpl::Unavailable) + return StringRef(); + if (State == TargetLibraryInfoImpl::StandardName) + return Impl->StandardNames[F]; + assert(State == TargetLibraryInfoImpl::CustomName); + return Impl->CustomNames.find(F)->second; + } + + /// \brief Handle invalidation from the pass manager. + /// + /// If we try to invalidate this info, just return false. It cannot become + /// invalid even if the module changes. + bool invalidate(Module &, const PreservedAnalyses &) { return false; } +}; + +/// \brief Analysis pass providing the \c TargetLibraryInfo. +/// +/// Note that this pass's result cannot be invalidated, it is immutable for the +/// life of the module. +class TargetLibraryAnalysis { +public: + typedef TargetLibraryInfo Result; + + /// \brief Opaque, unique identifier for this analysis pass. + static void *ID() { return (void *)&PassID; } + + /// \brief Default construct the library analysis. + /// + /// This will use the module's triple to construct the library info for that + /// module. + TargetLibraryAnalysis() {} + + /// \brief Construct a library analysis with preset info. + /// + /// This will directly copy the preset info into the result without + /// consulting the module's triple. + TargetLibraryAnalysis(TargetLibraryInfoImpl PresetInfoImpl) + : PresetInfoImpl(std::move(PresetInfoImpl)) {} + + // Move semantics. We spell out the constructors for MSVC. + TargetLibraryAnalysis(TargetLibraryAnalysis &&Arg) + : PresetInfoImpl(std::move(Arg.PresetInfoImpl)), Impls(std::move(Arg.Impls)) {} + TargetLibraryAnalysis &operator=(TargetLibraryAnalysis &&RHS) { + PresetInfoImpl = std::move(RHS.PresetInfoImpl); + Impls = std::move(RHS.Impls); + return *this; + } + + TargetLibraryInfo run(Module &M); + TargetLibraryInfo run(Function &F); + + /// \brief Provide access to a name for this pass for debugging purposes. + static StringRef name() { return "TargetLibraryAnalysis"; } + +private: + static char PassID; + + Optional<TargetLibraryInfoImpl> PresetInfoImpl; + + StringMap<std::unique_ptr<TargetLibraryInfoImpl>> Impls; + + TargetLibraryInfoImpl &lookupInfoImpl(Triple T); +}; + +class TargetLibraryInfoWrapperPass : public ImmutablePass { + TargetLibraryInfoImpl TLIImpl; + TargetLibraryInfo TLI; + + virtual void anchor(); + +public: + static char ID; + TargetLibraryInfoWrapperPass(); + explicit TargetLibraryInfoWrapperPass(const Triple &T); + explicit TargetLibraryInfoWrapperPass(const TargetLibraryInfoImpl &TLI); + + TargetLibraryInfo &getTLI() { return TLI; } + const TargetLibraryInfo &getTLI() const { return TLI; } +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h index 9acaaa6..4998141 100644 --- a/include/llvm/Analysis/TargetTransformInfo.h +++ b/include/llvm/Analysis/TargetTransformInfo.h @@ -1,4 +1,4 @@ -//===- llvm/Analysis/TargetTransformInfo.h ----------------------*- C++ -*-===// +//===- TargetTransformInfo.h ------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,22 +6,24 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This pass exposes codegen information to IR-level passes. Every -// transformation that uses codegen information is broken into three parts: -// 1. The IR-level analysis pass. -// 2. The IR-level transformation interface which provides the needed -// information. -// 3. Codegen-level implementation which uses target-specific hooks. -// -// This file defines #2, which is the interface that IR-level transformations -// use for querying the codegen. -// +/// \file +/// This pass exposes codegen information to IR-level passes. Every +/// transformation that uses codegen information is broken into three parts: +/// 1. The IR-level analysis pass. +/// 2. The IR-level transformation interface which provides the needed +/// information. +/// 3. Codegen-level implementation which uses target-specific hooks. +/// +/// This file defines #2, which is the interface that IR-level transformations +/// use for querying the codegen. +/// //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_TARGETTRANSFORMINFO_H #define LLVM_ANALYSIS_TARGETTRANSFORMINFO_H +#include "llvm/ADT/Optional.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/Pass.h" #include "llvm/Support/DataTypes.h" @@ -31,41 +33,61 @@ namespace llvm { class Function; class GlobalValue; class Loop; +class PreservedAnalyses; class Type; class User; class Value; -/// TargetTransformInfo - This pass provides access to the codegen -/// interfaces that are needed for IR-level transformations. +/// \brief Information about a load/store intrinsic defined by the target. +struct MemIntrinsicInfo { + MemIntrinsicInfo() + : ReadMem(false), WriteMem(false), Vol(false), MatchingId(0), + NumMemRefs(0), PtrVal(nullptr) {} + bool ReadMem; + bool WriteMem; + bool Vol; + // Same Id is set by the target for corresponding load/store intrinsics. + unsigned short MatchingId; + int NumMemRefs; + Value *PtrVal; +}; + +/// \brief This pass provides access to the codegen interfaces that are needed +/// for IR-level transformations. class TargetTransformInfo { -protected: - /// \brief The TTI instance one level down the stack. +public: + /// \brief Construct a TTI object using a type implementing the \c Concept + /// API below. /// - /// This is used to implement the default behavior all of the methods which - /// is to delegate up through the stack of TTIs until one can answer the - /// query. - TargetTransformInfo *PrevTTI; + /// This is used by targets to construct a TTI wrapping their target-specific + /// implementaion that encodes appropriate costs for their target. + template <typename T> TargetTransformInfo(T Impl); - /// \brief The top of the stack of TTI analyses available. + /// \brief Construct a baseline TTI object using a minimal implementation of + /// the \c Concept API below. /// - /// This is a convenience routine maintained as TTI analyses become available - /// that complements the PrevTTI delegation chain. When one part of an - /// analysis pass wants to query another part of the analysis pass it can use - /// this to start back at the top of the stack. - TargetTransformInfo *TopTTI; + /// The TTI implementation will reflect the information in the DataLayout + /// provided if non-null. + explicit TargetTransformInfo(const DataLayout *DL); - /// All pass subclasses must in their initializePass routine call - /// pushTTIStack with themselves to update the pointers tracking the previous - /// TTI instance in the analysis group's stack, and the top of the analysis - /// group's stack. - void pushTTIStack(Pass *P); + // Provide move semantics. + TargetTransformInfo(TargetTransformInfo &&Arg); + TargetTransformInfo &operator=(TargetTransformInfo &&RHS); - /// All pass subclasses must call TargetTransformInfo::getAnalysisUsage. - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + // We need to define the destructor out-of-line to define our sub-classes + // out-of-line. + ~TargetTransformInfo(); -public: - /// This class is intended to be subclassed by real implementations. - virtual ~TargetTransformInfo() = 0; + /// \brief Handle the invalidation of this information. + /// + /// When used as a result of \c TargetIRAnalysis this method will be called + /// when the function this was computed for changes. When it returns false, + /// the information is preserved across those changes. + bool invalidate(Function &, const PreservedAnalyses &) { + // FIXME: We should probably in some way ensure that the subtarget + // information for a function hasn't changed. + return false; + } /// \name Generic Target Information /// @{ @@ -86,9 +108,9 @@ public: /// skipped by renaming the registers in the CPU, but they still are encoded /// and thus wouldn't be considered 'free' here. enum TargetCostConstants { - TCC_Free = 0, ///< Expected to fold away in lowering. - TCC_Basic = 1, ///< The cost of a typical 'add' instruction. - TCC_Expensive = 4 ///< The cost of a 'div' instruction on x86. + TCC_Free = 0, ///< Expected to fold away in lowering. + TCC_Basic = 1, ///< The cost of a typical 'add' instruction. + TCC_Expensive = 4 ///< The cost of a 'div' instruction on x86. }; /// \brief Estimate the cost of a specific operation when lowered. @@ -105,16 +127,15 @@ public: /// /// The returned cost is defined in terms of \c TargetCostConstants, see its /// comments for a detailed explanation of the cost values. - virtual unsigned getOperationCost(unsigned Opcode, Type *Ty, - Type *OpTy = nullptr) const; + unsigned getOperationCost(unsigned Opcode, Type *Ty, + Type *OpTy = nullptr) const; /// \brief Estimate the cost of a GEP operation when lowered. /// /// The contract for this function is the same as \c getOperationCost except /// that it supports an interface that provides extra information specific to /// the GEP operation. - virtual unsigned getGEPCost(const Value *Ptr, - ArrayRef<const Value *> Operands) const; + unsigned getGEPCost(const Value *Ptr, ArrayRef<const Value *> Operands) const; /// \brief Estimate the cost of a function call when lowered. /// @@ -125,31 +146,31 @@ public: /// This is the most basic query for estimating call cost: it only knows the /// function type and (potentially) the number of arguments at the call site. /// The latter is only interesting for varargs function types. - virtual unsigned getCallCost(FunctionType *FTy, int NumArgs = -1) const; + unsigned getCallCost(FunctionType *FTy, int NumArgs = -1) const; /// \brief Estimate the cost of calling a specific function when lowered. /// /// This overload adds the ability to reason about the particular function /// being called in the event it is a library call with special lowering. - virtual unsigned getCallCost(const Function *F, int NumArgs = -1) const; + unsigned getCallCost(const Function *F, int NumArgs = -1) const; /// \brief Estimate the cost of calling a specific function when lowered. /// /// This overload allows specifying a set of candidate argument values. - virtual unsigned getCallCost(const Function *F, - ArrayRef<const Value *> Arguments) const; + unsigned getCallCost(const Function *F, + ArrayRef<const Value *> Arguments) const; /// \brief Estimate the cost of an intrinsic when lowered. /// /// Mirrors the \c getCallCost method but uses an intrinsic identifier. - virtual unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, - ArrayRef<Type *> ParamTys) const; + unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<Type *> ParamTys) const; /// \brief Estimate the cost of an intrinsic when lowered. /// /// Mirrors the \c getCallCost method but uses an intrinsic identifier. - virtual unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, - ArrayRef<const Value *> Arguments) const; + unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<const Value *> Arguments) const; /// \brief Estimate the cost of a given IR user when lowered. /// @@ -166,13 +187,13 @@ public: /// /// The returned cost is defined in terms of \c TargetCostConstants, see its /// comments for a detailed explanation of the cost values. - virtual unsigned getUserCost(const User *U) const; + unsigned getUserCost(const User *U) const; /// \brief hasBranchDivergence - Return true if branch divergence exists. /// Branch divergence has a significantly negative impact on GPU performance /// when threads in the same wavefront take different paths due to conditional /// branches. - virtual bool hasBranchDivergence() const; + bool hasBranchDivergence() const; /// \brief Test whether calls to a function lower to actual program function /// calls. @@ -186,7 +207,7 @@ public: /// and execution-speed costs. This would allow modelling the core of this /// query more accurately as a call is a single small instruction, but /// incurs significant execution cost. - virtual bool isLoweredToCall(const Function *F) const; + bool isLoweredToCall(const Function *F) const; /// Parameters that control the generic loop unrolling transformation. struct UnrollingPreferences { @@ -196,6 +217,13 @@ public: /// exceed this cost. Set this to UINT_MAX to disable the loop body cost /// restriction. unsigned Threshold; + /// If complete unrolling could help other optimizations (e.g. InstSimplify) + /// to remove N% of instructions, then we can go beyond unroll threshold. + /// This value set the minimal percent for allowing that. + unsigned MinPercentOfOptimized; + /// The absolute cost threshold. We won't go beyond this even if complete + /// unrolling could result in optimizing out 90% of instructions. + unsigned AbsoluteThreshold; /// The cost threshold for the unrolled loop when optimizing for size (set /// to UINT_MAX to disable). unsigned OptSizeThreshold; @@ -203,8 +231,8 @@ public: /// for partial/runtime unrolling (set to UINT_MAX to disable). unsigned PartialThreshold; /// The cost threshold for the unrolled loop when optimizing for size, like - /// OptSizeThreshold, but used for partial/runtime unrolling (set to UINT_MAX - /// to disable). + /// OptSizeThreshold, but used for partial/runtime unrolling (set to + /// UINT_MAX to disable). unsigned PartialOptSizeThreshold; /// A forced unrolling factor (the number of concatenated bodies of the /// original loop in the unrolled loop body). When set to 0, the unrolling @@ -218,18 +246,17 @@ public: unsigned MaxCount; /// Allow partial unrolling (unrolling of loops to expand the size of the /// loop body, not only to eliminate small constant-trip-count loops). - bool Partial; + bool Partial; /// Allow runtime unrolling (unrolling of loops to expand the size of the - /// loop body even when the number of loop iterations is not known at compile - /// time). - bool Runtime; + /// loop body even when the number of loop iterations is not known at + /// compile time). + bool Runtime; }; /// \brief Get target-customized preferences for the generic loop unrolling /// transformation. The caller will initialize UP with the current /// target-independent defaults. - virtual void getUnrollingPreferences(const Function *F, Loop *L, - UnrollingPreferences &UP) const; + void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) const; /// @} @@ -244,31 +271,33 @@ public: /// support is considered as "Fast" if it can outperform, or is on a par /// with, SW implementation when the population is sparse; otherwise, it is /// considered as "Slow". - enum PopcntSupportKind { - PSK_Software, - PSK_SlowHardware, - PSK_FastHardware - }; + enum PopcntSupportKind { PSK_Software, PSK_SlowHardware, PSK_FastHardware }; /// \brief Return true if the specified immediate is legal add immediate, that /// is the target has add instructions which can add a register with the /// immediate without having to materialize the immediate into a register. - virtual bool isLegalAddImmediate(int64_t Imm) const; + bool isLegalAddImmediate(int64_t Imm) const; /// \brief Return true if the specified immediate is legal icmp immediate, /// that is the target has icmp instructions which can compare a register /// against the immediate without having to materialize the immediate into a /// register. - virtual bool isLegalICmpImmediate(int64_t Imm) const; + bool isLegalICmpImmediate(int64_t Imm) const; /// \brief Return true if the addressing mode represented by AM is legal for /// this target, for a load/store of the specified type. /// The type may be VoidTy, in which case only return true if the addressing /// mode is legal for a load/store of any legal type. /// TODO: Handle pre/postinc as well. - virtual bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, - int64_t BaseOffset, bool HasBaseReg, - int64_t Scale) const; + bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, + bool HasBaseReg, int64_t Scale) const; + + /// \brief Return true if the target works with masked instruction + /// AVX2 allows masks for consecutive load and store for i32 and i64 elements. + /// AVX-512 architecture will also allow masks for non-consecutive memory + /// accesses. + bool isLegalMaskedStore(Type *DataType, int Consecutive) const; + bool isLegalMaskedLoad(Type *DataType, int Consecutive) const; /// \brief Return the cost of the scaling factor used in the addressing /// mode represented by AM for this target, for a load/store @@ -276,45 +305,52 @@ public: /// If the AM is supported, the return value must be >= 0. /// If the AM is not supported, it returns a negative value. /// TODO: Handle pre/postinc as well. - virtual int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, - int64_t BaseOffset, bool HasBaseReg, - int64_t Scale) const; + int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, + bool HasBaseReg, int64_t Scale) const; /// \brief Return true if it's free to truncate a value of type Ty1 to type /// Ty2. e.g. On x86 it's free to truncate a i32 value in register EAX to i16 /// by referencing its sub-register AX. - virtual bool isTruncateFree(Type *Ty1, Type *Ty2) const; + bool isTruncateFree(Type *Ty1, Type *Ty2) const; + + /// \brief Return true if it is profitable to hoist instruction in the + /// then/else to before if. + bool isProfitableToHoist(Instruction *I) const; /// \brief Return true if this type is legal. - virtual bool isTypeLegal(Type *Ty) const; + bool isTypeLegal(Type *Ty) const; /// \brief Returns the target's jmp_buf alignment in bytes. - virtual unsigned getJumpBufAlignment() const; + unsigned getJumpBufAlignment() const; /// \brief Returns the target's jmp_buf size in bytes. - virtual unsigned getJumpBufSize() const; + unsigned getJumpBufSize() const; /// \brief Return true if switches should be turned into lookup tables for the /// target. - virtual bool shouldBuildLookupTables() const; + bool shouldBuildLookupTables() const; /// \brief Return hardware support for population count. - virtual PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) const; + PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) const; /// \brief Return true if the hardware has a fast square-root instruction. - virtual bool haveFastSqrt(Type *Ty) const; + bool haveFastSqrt(Type *Ty) const; + + /// \brief Return the expected cost of supporting the floating point operation + /// of the specified type. + unsigned getFPOpCost(Type *Ty) const; /// \brief Return the expected cost of materializing for the given integer /// immediate of the specified type. - virtual unsigned getIntImmCost(const APInt &Imm, Type *Ty) const; + unsigned getIntImmCost(const APInt &Imm, Type *Ty) const; /// \brief Return the expected cost of materialization for the given integer /// immediate of the specified type for a given instruction. The cost can be /// zero if the immediate can be folded into the specified instruction. - virtual unsigned getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm, - Type *Ty) const; - virtual unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, - const APInt &Imm, Type *Ty) const; + unsigned getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm, + Type *Ty) const; + unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, + Type *Ty) const; /// @} /// \name Vector Target Information @@ -331,10 +367,10 @@ public: /// \brief Additional information about an operand's possible values. enum OperandValueKind { - OK_AnyValue, // Operand can have any value. - OK_UniformValue, // Operand is uniform (splat of a value). - OK_UniformConstantValue, // Operand is uniform constant. - OK_NonUniformConstantValue // Operand is a non uniform constant value. + OK_AnyValue, // Operand can have any value. + OK_UniformValue, // Operand is uniform (splat of a value). + OK_UniformConstantValue, // Operand is uniform constant. + OK_NonUniformConstantValue // Operand is a non uniform constant value. }; /// \brief Additional properties of an operand's values. @@ -343,18 +379,18 @@ public: /// \return The number of scalar or vector registers that the target has. /// If 'Vectors' is true, it returns the number of vector registers. If it is /// set to false, it returns the number of scalar registers. - virtual unsigned getNumberOfRegisters(bool Vector) const; + unsigned getNumberOfRegisters(bool Vector) const; /// \return The width of the largest scalar or vector register type. - virtual unsigned getRegisterBitWidth(bool Vector) const; + unsigned getRegisterBitWidth(bool Vector) const; /// \return The maximum interleave factor that any transform should try to /// perform for this target. This number depends on the level of parallelism /// and the number of execution units in the CPU. - virtual unsigned getMaxInterleaveFactor() const; + unsigned getMaxInterleaveFactor() const; /// \return The expected cost of arithmetic ops, such as mul, xor, fsub, etc. - virtual unsigned + unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info = OK_AnyValue, OperandValueKind Opd2Info = OK_AnyValue, @@ -364,31 +400,33 @@ public: /// \return The cost of a shuffle instruction of kind Kind and of type Tp. /// The index and subtype parameters are used by the subvector insertion and /// extraction shuffle kinds. - virtual unsigned getShuffleCost(ShuffleKind Kind, Type *Tp, int Index = 0, - Type *SubTp = nullptr) const; + unsigned getShuffleCost(ShuffleKind Kind, Type *Tp, int Index = 0, + Type *SubTp = nullptr) const; /// \return The expected cost of cast instructions, such as bitcast, trunc, /// zext, etc. - virtual unsigned getCastInstrCost(unsigned Opcode, Type *Dst, - Type *Src) const; + unsigned getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src) const; /// \return The expected cost of control-flow related instructions such as /// Phi, Ret, Br. - virtual unsigned getCFInstrCost(unsigned Opcode) const; + unsigned getCFInstrCost(unsigned Opcode) const; /// \returns The expected cost of compare and select instructions. - virtual unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy, - Type *CondTy = nullptr) const; + unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy, + Type *CondTy = nullptr) const; /// \return The expected cost of vector Insert and Extract. /// Use -1 to indicate that there is no information on the index value. - virtual unsigned getVectorInstrCost(unsigned Opcode, Type *Val, - unsigned Index = -1) const; + unsigned getVectorInstrCost(unsigned Opcode, Type *Val, + unsigned Index = -1) const; /// \return The cost of Load and Store instructions. - virtual unsigned getMemoryOpCost(unsigned Opcode, Type *Src, - unsigned Alignment, - unsigned AddressSpace) const; + unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment, + unsigned AddressSpace) const; + + /// \return The cost of masked Load and Store instructions. + unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment, + unsigned AddressSpace) const; /// \brief Calculate the cost of performing a vector reduction. /// @@ -403,16 +441,16 @@ public: /// Split: /// (v0, v1, v2, v3) /// ((v0+v2), (v1+v3), undef, undef) - virtual unsigned getReductionCost(unsigned Opcode, Type *Ty, - bool IsPairwiseForm) const; + unsigned getReductionCost(unsigned Opcode, Type *Ty, + bool IsPairwiseForm) const; /// \returns The cost of Intrinsic instructions. - virtual unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, - ArrayRef<Type *> Tys) const; + unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, + ArrayRef<Type *> Tys) const; /// \returns The number of pieces into which the provided type must be /// split during legalization. Zero is returned when the answer is unknown. - virtual unsigned getNumberOfParts(Type *Tp) const; + unsigned getNumberOfParts(Type *Tp) const; /// \returns The cost of the address computation. For most targets this can be /// merged into the instruction indexing mode. Some targets might want to @@ -421,28 +459,385 @@ public: /// The 'IsComplex' parameter is a hint that the address computation is likely /// to involve multiple instructions and as such unlikely to be merged into /// the address indexing mode. - virtual unsigned getAddressComputationCost(Type *Ty, - bool IsComplex = false) const; + unsigned getAddressComputationCost(Type *Ty, bool IsComplex = false) const; /// \returns The cost, if any, of keeping values of the given types alive /// over a callsite. /// /// Some types may require the use of register classes that do not have /// any callee-saved registers, so would require a spill and fill. - virtual unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type*> Tys) const; + unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) const; + + /// \returns True if the intrinsic is a supported memory intrinsic. Info + /// will contain additional information - whether the intrinsic may write + /// or read to memory, volatility and the pointer. Info is undefined + /// if false is returned. + bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const; + + /// \returns A value which is the result of the given memory intrinsic. New + /// instructions may be created to extract the result from the given intrinsic + /// memory operation. Returns nullptr if the target cannot create a result + /// from the given intrinsic. + Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst, + Type *ExpectedType) const; /// @} - /// Analysis group identification. +private: + /// \brief The abstract base class used to type erase specific TTI + /// implementations. + class Concept; + + /// \brief The template model for the base class which wraps a concrete + /// implementation in a type erased interface. + template <typename T> class Model; + + std::unique_ptr<Concept> TTIImpl; +}; + +class TargetTransformInfo::Concept { +public: + virtual ~Concept() = 0; + + virtual unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) = 0; + virtual unsigned getGEPCost(const Value *Ptr, + ArrayRef<const Value *> Operands) = 0; + virtual unsigned getCallCost(FunctionType *FTy, int NumArgs) = 0; + virtual unsigned getCallCost(const Function *F, int NumArgs) = 0; + virtual unsigned getCallCost(const Function *F, + ArrayRef<const Value *> Arguments) = 0; + virtual unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<Type *> ParamTys) = 0; + virtual unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<const Value *> Arguments) = 0; + virtual unsigned getUserCost(const User *U) = 0; + virtual bool hasBranchDivergence() = 0; + virtual bool isLoweredToCall(const Function *F) = 0; + virtual void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) = 0; + virtual bool isLegalAddImmediate(int64_t Imm) = 0; + virtual bool isLegalICmpImmediate(int64_t Imm) = 0; + virtual bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, + int64_t BaseOffset, bool HasBaseReg, + int64_t Scale) = 0; + virtual bool isLegalMaskedStore(Type *DataType, int Consecutive) = 0; + virtual bool isLegalMaskedLoad(Type *DataType, int Consecutive) = 0; + virtual int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, + int64_t BaseOffset, bool HasBaseReg, + int64_t Scale) = 0; + virtual bool isTruncateFree(Type *Ty1, Type *Ty2) = 0; + virtual bool isProfitableToHoist(Instruction *I) = 0; + virtual bool isTypeLegal(Type *Ty) = 0; + virtual unsigned getJumpBufAlignment() = 0; + virtual unsigned getJumpBufSize() = 0; + virtual bool shouldBuildLookupTables() = 0; + virtual PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) = 0; + virtual bool haveFastSqrt(Type *Ty) = 0; + virtual unsigned getFPOpCost(Type *Ty) = 0; + virtual unsigned getIntImmCost(const APInt &Imm, Type *Ty) = 0; + virtual unsigned getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm, + Type *Ty) = 0; + virtual unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, + const APInt &Imm, Type *Ty) = 0; + virtual unsigned getNumberOfRegisters(bool Vector) = 0; + virtual unsigned getRegisterBitWidth(bool Vector) = 0; + virtual unsigned getMaxInterleaveFactor() = 0; + virtual unsigned + getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info, + OperandValueKind Opd2Info, + OperandValueProperties Opd1PropInfo, + OperandValueProperties Opd2PropInfo) = 0; + virtual unsigned getShuffleCost(ShuffleKind Kind, Type *Tp, int Index, + Type *SubTp) = 0; + virtual unsigned getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src) = 0; + virtual unsigned getCFInstrCost(unsigned Opcode) = 0; + virtual unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy, + Type *CondTy) = 0; + virtual unsigned getVectorInstrCost(unsigned Opcode, Type *Val, + unsigned Index) = 0; + virtual unsigned getMemoryOpCost(unsigned Opcode, Type *Src, + unsigned Alignment, + unsigned AddressSpace) = 0; + virtual unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, + unsigned Alignment, + unsigned AddressSpace) = 0; + virtual unsigned getReductionCost(unsigned Opcode, Type *Ty, + bool IsPairwiseForm) = 0; + virtual unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, + ArrayRef<Type *> Tys) = 0; + virtual unsigned getNumberOfParts(Type *Tp) = 0; + virtual unsigned getAddressComputationCost(Type *Ty, bool IsComplex) = 0; + virtual unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) = 0; + virtual bool getTgtMemIntrinsic(IntrinsicInst *Inst, + MemIntrinsicInfo &Info) = 0; + virtual Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst, + Type *ExpectedType) = 0; +}; + +template <typename T> +class TargetTransformInfo::Model final : public TargetTransformInfo::Concept { + T Impl; + +public: + Model(T Impl) : Impl(std::move(Impl)) {} + ~Model() override {} + + unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) override { + return Impl.getOperationCost(Opcode, Ty, OpTy); + } + unsigned getGEPCost(const Value *Ptr, + ArrayRef<const Value *> Operands) override { + return Impl.getGEPCost(Ptr, Operands); + } + unsigned getCallCost(FunctionType *FTy, int NumArgs) override { + return Impl.getCallCost(FTy, NumArgs); + } + unsigned getCallCost(const Function *F, int NumArgs) override { + return Impl.getCallCost(F, NumArgs); + } + unsigned getCallCost(const Function *F, + ArrayRef<const Value *> Arguments) override { + return Impl.getCallCost(F, Arguments); + } + unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<Type *> ParamTys) override { + return Impl.getIntrinsicCost(IID, RetTy, ParamTys); + } + unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<const Value *> Arguments) override { + return Impl.getIntrinsicCost(IID, RetTy, Arguments); + } + unsigned getUserCost(const User *U) override { return Impl.getUserCost(U); } + bool hasBranchDivergence() override { return Impl.hasBranchDivergence(); } + bool isLoweredToCall(const Function *F) override { + return Impl.isLoweredToCall(F); + } + void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) override { + return Impl.getUnrollingPreferences(L, UP); + } + bool isLegalAddImmediate(int64_t Imm) override { + return Impl.isLegalAddImmediate(Imm); + } + bool isLegalICmpImmediate(int64_t Imm) override { + return Impl.isLegalICmpImmediate(Imm); + } + bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, + bool HasBaseReg, int64_t Scale) override { + return Impl.isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg, + Scale); + } + bool isLegalMaskedStore(Type *DataType, int Consecutive) override { + return Impl.isLegalMaskedStore(DataType, Consecutive); + } + bool isLegalMaskedLoad(Type *DataType, int Consecutive) override { + return Impl.isLegalMaskedLoad(DataType, Consecutive); + } + int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, + bool HasBaseReg, int64_t Scale) override { + return Impl.getScalingFactorCost(Ty, BaseGV, BaseOffset, HasBaseReg, Scale); + } + bool isTruncateFree(Type *Ty1, Type *Ty2) override { + return Impl.isTruncateFree(Ty1, Ty2); + } + bool isProfitableToHoist(Instruction *I) override { + return Impl.isProfitableToHoist(I); + } + bool isTypeLegal(Type *Ty) override { return Impl.isTypeLegal(Ty); } + unsigned getJumpBufAlignment() override { return Impl.getJumpBufAlignment(); } + unsigned getJumpBufSize() override { return Impl.getJumpBufSize(); } + bool shouldBuildLookupTables() override { + return Impl.shouldBuildLookupTables(); + } + PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) override { + return Impl.getPopcntSupport(IntTyWidthInBit); + } + bool haveFastSqrt(Type *Ty) override { return Impl.haveFastSqrt(Ty); } + + unsigned getFPOpCost(Type *Ty) override { + return Impl.getFPOpCost(Ty); + } + + unsigned getIntImmCost(const APInt &Imm, Type *Ty) override { + return Impl.getIntImmCost(Imm, Ty); + } + unsigned getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm, + Type *Ty) override { + return Impl.getIntImmCost(Opc, Idx, Imm, Ty); + } + unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, + Type *Ty) override { + return Impl.getIntImmCost(IID, Idx, Imm, Ty); + } + unsigned getNumberOfRegisters(bool Vector) override { + return Impl.getNumberOfRegisters(Vector); + } + unsigned getRegisterBitWidth(bool Vector) override { + return Impl.getRegisterBitWidth(Vector); + } + unsigned getMaxInterleaveFactor() override { + return Impl.getMaxInterleaveFactor(); + } + unsigned + getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info, + OperandValueKind Opd2Info, + OperandValueProperties Opd1PropInfo, + OperandValueProperties Opd2PropInfo) override { + return Impl.getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info, + Opd1PropInfo, Opd2PropInfo); + } + unsigned getShuffleCost(ShuffleKind Kind, Type *Tp, int Index, + Type *SubTp) override { + return Impl.getShuffleCost(Kind, Tp, Index, SubTp); + } + unsigned getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src) override { + return Impl.getCastInstrCost(Opcode, Dst, Src); + } + unsigned getCFInstrCost(unsigned Opcode) override { + return Impl.getCFInstrCost(Opcode); + } + unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy, + Type *CondTy) override { + return Impl.getCmpSelInstrCost(Opcode, ValTy, CondTy); + } + unsigned getVectorInstrCost(unsigned Opcode, Type *Val, + unsigned Index) override { + return Impl.getVectorInstrCost(Opcode, Val, Index); + } + unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment, + unsigned AddressSpace) override { + return Impl.getMemoryOpCost(Opcode, Src, Alignment, AddressSpace); + } + unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment, + unsigned AddressSpace) override { + return Impl.getMaskedMemoryOpCost(Opcode, Src, Alignment, AddressSpace); + } + unsigned getReductionCost(unsigned Opcode, Type *Ty, + bool IsPairwiseForm) override { + return Impl.getReductionCost(Opcode, Ty, IsPairwiseForm); + } + unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, + ArrayRef<Type *> Tys) override { + return Impl.getIntrinsicInstrCost(ID, RetTy, Tys); + } + unsigned getNumberOfParts(Type *Tp) override { + return Impl.getNumberOfParts(Tp); + } + unsigned getAddressComputationCost(Type *Ty, bool IsComplex) override { + return Impl.getAddressComputationCost(Ty, IsComplex); + } + unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) override { + return Impl.getCostOfKeepingLiveOverCall(Tys); + } + bool getTgtMemIntrinsic(IntrinsicInst *Inst, + MemIntrinsicInfo &Info) override { + return Impl.getTgtMemIntrinsic(Inst, Info); + } + Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst, + Type *ExpectedType) override { + return Impl.getOrCreateResultFromMemIntrinsic(Inst, ExpectedType); + } +}; + +template <typename T> +TargetTransformInfo::TargetTransformInfo(T Impl) + : TTIImpl(new Model<T>(Impl)) {} + +/// \brief Analysis pass providing the \c TargetTransformInfo. +/// +/// The core idea of the TargetIRAnalysis is to expose an interface through +/// which LLVM targets can analyze and provide information about the middle +/// end's target-independent IR. This supports use cases such as target-aware +/// cost modeling of IR constructs. +/// +/// This is a function analysis because much of the cost modeling for targets +/// is done in a subtarget specific way and LLVM supports compiling different +/// functions targeting different subtargets in order to support runtime +/// dispatch according to the observed subtarget. +class TargetIRAnalysis { +public: + typedef TargetTransformInfo Result; + + /// \brief Opaque, unique identifier for this analysis pass. + static void *ID() { return (void *)&PassID; } + + /// \brief Provide access to a name for this pass for debugging purposes. + static StringRef name() { return "TargetIRAnalysis"; } + + /// \brief Default construct a target IR analysis. + /// + /// This will use the module's datalayout to construct a baseline + /// conservative TTI result. + TargetIRAnalysis(); + + /// \brief Construct an IR analysis pass around a target-provide callback. + /// + /// The callback will be called with a particular function for which the TTI + /// is needed and must return a TTI object for that function. + TargetIRAnalysis(std::function<Result(Function &)> TTICallback); + + // Value semantics. We spell out the constructors for MSVC. + TargetIRAnalysis(const TargetIRAnalysis &Arg) + : TTICallback(Arg.TTICallback) {} + TargetIRAnalysis(TargetIRAnalysis &&Arg) + : TTICallback(std::move(Arg.TTICallback)) {} + TargetIRAnalysis &operator=(const TargetIRAnalysis &RHS) { + TTICallback = RHS.TTICallback; + return *this; + } + TargetIRAnalysis &operator=(TargetIRAnalysis &&RHS) { + TTICallback = std::move(RHS.TTICallback); + return *this; + } + + Result run(Function &F); + +private: + static char PassID; + + /// \brief The callback used to produce a result. + /// + /// We use a completely opaque callback so that targets can provide whatever + /// mechanism they desire for constructing the TTI for a given function. + /// + /// FIXME: Should we really use std::function? It's relatively inefficient. + /// It might be possible to arrange for even stateful callbacks to outlive + /// the analysis and thus use a function_ref which would be lighter weight. + /// This may also be less error prone as the callback is likely to reference + /// the external TargetMachine, and that reference needs to never dangle. + std::function<Result(Function &)> TTICallback; + + /// \brief Helper function used as the callback in the default constructor. + static Result getDefaultTTI(Function &F); +}; + +/// \brief Wrapper pass for TargetTransformInfo. +/// +/// This pass can be constructed from a TTI object which it stores internally +/// and is queried by passes. +class TargetTransformInfoWrapperPass : public ImmutablePass { + TargetIRAnalysis TIRA; + Optional<TargetTransformInfo> TTI; + + virtual void anchor(); + +public: static char ID; + + /// \brief We must provide a default constructor for the pass but it should + /// never be used. + /// + /// Use the constructor below or call one of the creation routines. + TargetTransformInfoWrapperPass(); + + explicit TargetTransformInfoWrapperPass(TargetIRAnalysis TIRA); + + TargetTransformInfo &getTTI(Function &F); }; -/// \brief Create the base case instance of a pass in the TTI analysis group. +/// \brief Create an analysis pass wrapper around a TTI object. /// -/// This class provides the base case for the stack of TTI analyzes. It doesn't -/// delegate to anything and uses the STTI and VTTI objects passed in to -/// satisfy the queries. -ImmutablePass *createNoTargetTransformInfoPass(); +/// This analysis pass just holds the TTI instance and makes it available to +/// clients. +ImmutablePass *createTargetTransformInfoWrapperPass(TargetIRAnalysis TIRA); } // End llvm namespace diff --git a/include/llvm/Analysis/TargetTransformInfoImpl.h b/include/llvm/Analysis/TargetTransformInfoImpl.h new file mode 100644 index 0000000..3e02c0c --- /dev/null +++ b/include/llvm/Analysis/TargetTransformInfoImpl.h @@ -0,0 +1,433 @@ +//===- TargetTransformInfoImpl.h --------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file provides helpers for the implementation of +/// a TargetTransformInfo-conforming class. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_TARGETTRANSFORMINFOIMPL_H +#define LLVM_ANALYSIS_TARGETTRANSFORMINFOIMPL_H + +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/Type.h" + +namespace llvm { + +/// \brief Base class for use as a mix-in that aids implementing +/// a TargetTransformInfo-compatible class. +class TargetTransformInfoImplBase { +protected: + typedef TargetTransformInfo TTI; + + const DataLayout *DL; + + explicit TargetTransformInfoImplBase(const DataLayout *DL) + : DL(DL) {} + +public: + // Provide value semantics. MSVC requires that we spell all of these out. + TargetTransformInfoImplBase(const TargetTransformInfoImplBase &Arg) + : DL(Arg.DL) {} + TargetTransformInfoImplBase(TargetTransformInfoImplBase &&Arg) + : DL(std::move(Arg.DL)) {} + TargetTransformInfoImplBase & + operator=(const TargetTransformInfoImplBase &RHS) { + DL = RHS.DL; + return *this; + } + TargetTransformInfoImplBase &operator=(TargetTransformInfoImplBase &&RHS) { + DL = std::move(RHS.DL); + return *this; + } + + unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) { + switch (Opcode) { + default: + // By default, just classify everything as 'basic'. + return TTI::TCC_Basic; + + case Instruction::GetElementPtr: + llvm_unreachable("Use getGEPCost for GEP operations!"); + + case Instruction::BitCast: + assert(OpTy && "Cast instructions must provide the operand type"); + if (Ty == OpTy || (Ty->isPointerTy() && OpTy->isPointerTy())) + // Identity and pointer-to-pointer casts are free. + return TTI::TCC_Free; + + // Otherwise, the default basic cost is used. + return TTI::TCC_Basic; + + case Instruction::IntToPtr: { + if (!DL) + return TTI::TCC_Basic; + + // An inttoptr cast is free so long as the input is a legal integer type + // which doesn't contain values outside the range of a pointer. + unsigned OpSize = OpTy->getScalarSizeInBits(); + if (DL->isLegalInteger(OpSize) && + OpSize <= DL->getPointerTypeSizeInBits(Ty)) + return TTI::TCC_Free; + + // Otherwise it's not a no-op. + return TTI::TCC_Basic; + } + case Instruction::PtrToInt: { + if (!DL) + return TTI::TCC_Basic; + + // A ptrtoint cast is free so long as the result is large enough to store + // the pointer, and a legal integer type. + unsigned DestSize = Ty->getScalarSizeInBits(); + if (DL->isLegalInteger(DestSize) && + DestSize >= DL->getPointerTypeSizeInBits(OpTy)) + return TTI::TCC_Free; + + // Otherwise it's not a no-op. + return TTI::TCC_Basic; + } + case Instruction::Trunc: + // trunc to a native type is free (assuming the target has compare and + // shift-right of the same width). + if (DL && DL->isLegalInteger(DL->getTypeSizeInBits(Ty))) + return TTI::TCC_Free; + + return TTI::TCC_Basic; + } + } + + unsigned getGEPCost(const Value *Ptr, ArrayRef<const Value *> Operands) { + // In the basic model, we just assume that all-constant GEPs will be folded + // into their uses via addressing modes. + for (unsigned Idx = 0, Size = Operands.size(); Idx != Size; ++Idx) + if (!isa<Constant>(Operands[Idx])) + return TTI::TCC_Basic; + + return TTI::TCC_Free; + } + + unsigned getCallCost(FunctionType *FTy, int NumArgs) { + assert(FTy && "FunctionType must be provided to this routine."); + + // The target-independent implementation just measures the size of the + // function by approximating that each argument will take on average one + // instruction to prepare. + + if (NumArgs < 0) + // Set the argument number to the number of explicit arguments in the + // function. + NumArgs = FTy->getNumParams(); + + return TTI::TCC_Basic * (NumArgs + 1); + } + + unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<Type *> ParamTys) { + switch (IID) { + default: + // Intrinsics rarely (if ever) have normal argument setup constraints. + // Model them as having a basic instruction cost. + // FIXME: This is wrong for libc intrinsics. + return TTI::TCC_Basic; + + case Intrinsic::annotation: + case Intrinsic::assume: + case Intrinsic::dbg_declare: + case Intrinsic::dbg_value: + case Intrinsic::invariant_start: + case Intrinsic::invariant_end: + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + case Intrinsic::objectsize: + case Intrinsic::ptr_annotation: + case Intrinsic::var_annotation: + case Intrinsic::experimental_gc_result_int: + case Intrinsic::experimental_gc_result_float: + case Intrinsic::experimental_gc_result_ptr: + case Intrinsic::experimental_gc_result: + case Intrinsic::experimental_gc_relocate: + // These intrinsics don't actually represent code after lowering. + return TTI::TCC_Free; + } + } + + bool hasBranchDivergence() { return false; } + + bool isLoweredToCall(const Function *F) { + // FIXME: These should almost certainly not be handled here, and instead + // handled with the help of TLI or the target itself. This was largely + // ported from existing analysis heuristics here so that such refactorings + // can take place in the future. + + if (F->isIntrinsic()) + return false; + + if (F->hasLocalLinkage() || !F->hasName()) + return true; + + StringRef Name = F->getName(); + + // These will all likely lower to a single selection DAG node. + if (Name == "copysign" || Name == "copysignf" || Name == "copysignl" || + Name == "fabs" || Name == "fabsf" || Name == "fabsl" || Name == "sin" || + Name == "fmin" || Name == "fminf" || Name == "fminl" || + Name == "fmax" || Name == "fmaxf" || Name == "fmaxl" || + Name == "sinf" || Name == "sinl" || Name == "cos" || Name == "cosf" || + Name == "cosl" || Name == "sqrt" || Name == "sqrtf" || Name == "sqrtl") + return false; + + // These are all likely to be optimized into something smaller. + if (Name == "pow" || Name == "powf" || Name == "powl" || Name == "exp2" || + Name == "exp2l" || Name == "exp2f" || Name == "floor" || + Name == "floorf" || Name == "ceil" || Name == "round" || + Name == "ffs" || Name == "ffsl" || Name == "abs" || Name == "labs" || + Name == "llabs") + return false; + + return true; + } + + void getUnrollingPreferences(Loop *, TTI::UnrollingPreferences &) {} + + bool isLegalAddImmediate(int64_t Imm) { return false; } + + bool isLegalICmpImmediate(int64_t Imm) { return false; } + + bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, + bool HasBaseReg, int64_t Scale) { + // Guess that reg+reg addressing is allowed. This heuristic is taken from + // the implementation of LSR. + return !BaseGV && BaseOffset == 0 && Scale <= 1; + } + + bool isLegalMaskedStore(Type *DataType, int Consecutive) { return false; } + + bool isLegalMaskedLoad(Type *DataType, int Consecutive) { return false; } + + int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, + bool HasBaseReg, int64_t Scale) { + // Guess that all legal addressing mode are free. + if (isLegalAddressingMode(Ty, BaseGV, BaseOffset, HasBaseReg, Scale)) + return 0; + return -1; + } + + bool isTruncateFree(Type *Ty1, Type *Ty2) { return false; } + + bool isProfitableToHoist(Instruction *I) { return true; } + + bool isTypeLegal(Type *Ty) { return false; } + + unsigned getJumpBufAlignment() { return 0; } + + unsigned getJumpBufSize() { return 0; } + + bool shouldBuildLookupTables() { return true; } + + TTI::PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) { + return TTI::PSK_Software; + } + + bool haveFastSqrt(Type *Ty) { return false; } + + unsigned getFPOpCost(Type *Ty) { return TargetTransformInfo::TCC_Basic; } + + unsigned getIntImmCost(const APInt &Imm, Type *Ty) { return TTI::TCC_Basic; } + + unsigned getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, + Type *Ty) { + return TTI::TCC_Free; + } + + unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, + Type *Ty) { + return TTI::TCC_Free; + } + + unsigned getNumberOfRegisters(bool Vector) { return 8; } + + unsigned getRegisterBitWidth(bool Vector) { return 32; } + + unsigned getMaxInterleaveFactor() { return 1; } + + unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty, + TTI::OperandValueKind Opd1Info, + TTI::OperandValueKind Opd2Info, + TTI::OperandValueProperties Opd1PropInfo, + TTI::OperandValueProperties Opd2PropInfo) { + return 1; + } + + unsigned getShuffleCost(TTI::ShuffleKind Kind, Type *Ty, int Index, + Type *SubTp) { + return 1; + } + + unsigned getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src) { return 1; } + + unsigned getCFInstrCost(unsigned Opcode) { return 1; } + + unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy) { + return 1; + } + + unsigned getVectorInstrCost(unsigned Opcode, Type *Val, unsigned Index) { + return 1; + } + + unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment, + unsigned AddressSpace) { + return 1; + } + + unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment, + unsigned AddressSpace) { + return 1; + } + + unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, + ArrayRef<Type *> Tys) { + return 1; + } + + unsigned getNumberOfParts(Type *Tp) { return 0; } + + unsigned getAddressComputationCost(Type *Tp, bool) { return 0; } + + unsigned getReductionCost(unsigned, Type *, bool) { return 1; } + + unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) { return 0; } + + bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) { + return false; + } + + Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst, + Type *ExpectedType) { + return nullptr; + } +}; + +/// \brief CRTP base class for use as a mix-in that aids implementing +/// a TargetTransformInfo-compatible class. +template <typename T> +class TargetTransformInfoImplCRTPBase : public TargetTransformInfoImplBase { +private: + typedef TargetTransformInfoImplBase BaseT; + +protected: + explicit TargetTransformInfoImplCRTPBase(const DataLayout *DL) + : BaseT(DL) {} + +public: + // Provide value semantics. MSVC requires that we spell all of these out. + TargetTransformInfoImplCRTPBase(const TargetTransformInfoImplCRTPBase &Arg) + : BaseT(static_cast<const BaseT &>(Arg)) {} + TargetTransformInfoImplCRTPBase(TargetTransformInfoImplCRTPBase &&Arg) + : BaseT(std::move(static_cast<BaseT &>(Arg))) {} + TargetTransformInfoImplCRTPBase & + operator=(const TargetTransformInfoImplCRTPBase &RHS) { + BaseT::operator=(static_cast<const BaseT &>(RHS)); + return *this; + } + TargetTransformInfoImplCRTPBase & + operator=(TargetTransformInfoImplCRTPBase &&RHS) { + BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); + return *this; + } + + using BaseT::getCallCost; + + unsigned getCallCost(const Function *F, int NumArgs) { + assert(F && "A concrete function must be provided to this routine."); + + if (NumArgs < 0) + // Set the argument number to the number of explicit arguments in the + // function. + NumArgs = F->arg_size(); + + if (Intrinsic::ID IID = (Intrinsic::ID)F->getIntrinsicID()) { + FunctionType *FTy = F->getFunctionType(); + SmallVector<Type *, 8> ParamTys(FTy->param_begin(), FTy->param_end()); + return static_cast<T *>(this) + ->getIntrinsicCost(IID, FTy->getReturnType(), ParamTys); + } + + if (!static_cast<T *>(this)->isLoweredToCall(F)) + return TTI::TCC_Basic; // Give a basic cost if it will be lowered + // directly. + + return static_cast<T *>(this)->getCallCost(F->getFunctionType(), NumArgs); + } + + unsigned getCallCost(const Function *F, ArrayRef<const Value *> Arguments) { + // Simply delegate to generic handling of the call. + // FIXME: We should use instsimplify or something else to catch calls which + // will constant fold with these arguments. + return static_cast<T *>(this)->getCallCost(F, Arguments.size()); + } + + using BaseT::getIntrinsicCost; + + unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<const Value *> Arguments) { + // Delegate to the generic intrinsic handling code. This mostly provides an + // opportunity for targets to (for example) special case the cost of + // certain intrinsics based on constants used as arguments. + SmallVector<Type *, 8> ParamTys; + ParamTys.reserve(Arguments.size()); + for (unsigned Idx = 0, Size = Arguments.size(); Idx != Size; ++Idx) + ParamTys.push_back(Arguments[Idx]->getType()); + return static_cast<T *>(this)->getIntrinsicCost(IID, RetTy, ParamTys); + } + + unsigned getUserCost(const User *U) { + if (isa<PHINode>(U)) + return TTI::TCC_Free; // Model all PHI nodes as free. + + if (const GEPOperator *GEP = dyn_cast<GEPOperator>(U)) { + SmallVector<const Value *, 4> Indices(GEP->idx_begin(), GEP->idx_end()); + return static_cast<T *>(this) + ->getGEPCost(GEP->getPointerOperand(), Indices); + } + + if (ImmutableCallSite CS = U) { + const Function *F = CS.getCalledFunction(); + if (!F) { + // Just use the called value type. + Type *FTy = CS.getCalledValue()->getType()->getPointerElementType(); + return static_cast<T *>(this) + ->getCallCost(cast<FunctionType>(FTy), CS.arg_size()); + } + + SmallVector<const Value *, 8> Arguments(CS.arg_begin(), CS.arg_end()); + return static_cast<T *>(this)->getCallCost(F, Arguments); + } + + if (const CastInst *CI = dyn_cast<CastInst>(U)) { + // Result of a cmp instruction is often extended (to be used by other + // cmp instructions, logical or return instructions). These are usually + // nop on most sane targets. + if (isa<CmpInst>(CI->getOperand(0))) + return TTI::TCC_Free; + } + + return static_cast<T *>(this)->getOperationCost( + Operator::getOpcode(U), U->getType(), + U->getNumOperands() == 1 ? U->getOperand(0)->getType() : nullptr); + } +}; +} + +#endif diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 6bbf4f4..ac8c3b7 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -25,7 +25,7 @@ namespace llvm { class DataLayout; class StringRef; class MDNode; - class AssumptionTracker; + class AssumptionCache; class DominatorTree; class TargetLibraryInfo; @@ -37,9 +37,9 @@ namespace llvm { /// where V is a vector, the known zero and known one values are the /// same width as the vector element, and the bit is set only if it is true /// for all of the elements in the vector. - void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, + void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, const DataLayout *TD = nullptr, unsigned Depth = 0, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); /// Compute known bits from the range metadata. @@ -51,7 +51,7 @@ namespace llvm { /// one. Convenience wrapper around computeKnownBits. void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, const DataLayout *TD = nullptr, unsigned Depth = 0, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); @@ -61,7 +61,7 @@ namespace llvm { /// integer or pointer type and vectors of integers. If 'OrZero' is set then /// returns true if the given value is either a power of two or zero. bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero = false, unsigned Depth = 0, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); @@ -70,7 +70,7 @@ namespace llvm { /// non-zero when defined. Supports values with integer or pointer type and /// vectors of integers. bool isKnownNonZero(Value *V, const DataLayout *TD = nullptr, - unsigned Depth = 0, AssumptionTracker *AT = nullptr, + unsigned Depth = 0, AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); @@ -83,13 +83,12 @@ namespace llvm { /// where V is a vector, the mask, known zero, and known one values are the /// same width as the vector element, and the bit is set only if it is true /// for all of the elements in the vector. - bool MaskedValueIsZero(Value *V, const APInt &Mask, + bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout *TD = nullptr, unsigned Depth = 0, - AssumptionTracker *AT = nullptr, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); - /// ComputeNumSignBits - Return the number of times the sign bit of the /// register is replicated into the other bits. We know that at least 1 bit /// is always equal to the sign bit (itself), but other cases can give us @@ -99,8 +98,7 @@ namespace llvm { /// 'Op' must have a scalar integer type. /// unsigned ComputeNumSignBits(Value *Op, const DataLayout *TD = nullptr, - unsigned Depth = 0, - AssumptionTracker *AT = nullptr, + unsigned Depth = 0, AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); @@ -118,6 +116,11 @@ namespace llvm { /// bool CannotBeNegativeZero(const Value *V, unsigned Depth = 0); + /// CannotBeOrderedLessThanZero - Return true if we can prove that the + /// specified FP value is either a NaN or never less than 0.0. + /// + bool CannotBeOrderedLessThanZero(const Value *V, unsigned Depth = 0); + /// isBytewiseValue - If the specified value can be set by repeating the same /// byte in memory, return the i8 value that it is represented with. This is /// true for all i8 values obviously, but is also true for i32 0, i32 -1, @@ -217,6 +220,17 @@ namespace llvm { const DataLayout *DL = nullptr, const DominatorTree *DT = nullptr); + enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows }; + OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS, + const DataLayout *DL, + AssumptionCache *AC, + const Instruction *CxtI, + const DominatorTree *DT); + OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS, + const DataLayout *DL, + AssumptionCache *AC, + const Instruction *CxtI, + const DominatorTree *DT); } // end namespace llvm #endif |