diff options
Diffstat (limited to 'include/llvm/Transforms')
86 files changed, 4970 insertions, 552 deletions
diff --git a/include/llvm/Transforms/GCOVProfiler.h b/include/llvm/Transforms/GCOVProfiler.h new file mode 100644 index 000000000000..f6521901a33e --- /dev/null +++ b/include/llvm/Transforms/GCOVProfiler.h @@ -0,0 +1,31 @@ +//===- Transforms/GCOVProfiler.h - GCOVProfiler pass ----------*- 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 the interface for the GCOV style profiler pass. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_GCOVPROFILER_H +#define LLVM_TRANSFORMS_GCOVPROFILER_H + +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Instrumentation.h" + +namespace llvm { +/// The gcov-style instrumentation pass +class GCOVProfilerPass : public PassInfoMixin<GCOVProfilerPass> { +public: + GCOVProfilerPass(const GCOVOptions &Options = GCOVOptions::getDefault()) : GCOVOpts(Options) { } + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); + +private: + GCOVOptions GCOVOpts; +}; + +} // End llvm namespace +#endif diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h index 78d2fadc5190..f6731884870c 100644 --- a/include/llvm/Transforms/IPO.h +++ b/include/llvm/Transforms/IPO.h @@ -15,12 +15,13 @@ #ifndef LLVM_TRANSFORMS_IPO_H #define LLVM_TRANSFORMS_IPO_H -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/StringRef.h" +#include <functional> +#include <vector> namespace llvm { -class FunctionInfoIndex; +class StringRef; +class ModuleSummaryIndex; class ModulePass; class Pass; class Function; @@ -88,7 +89,7 @@ ModulePass *createGVExtractionPass(std::vector<GlobalValue*>& GVs, bool //===----------------------------------------------------------------------===// /// This pass performs iterative function importing from other modules. -Pass *createFunctionImportPass(const FunctionInfoIndex *Index = nullptr); +Pass *createFunctionImportPass(const ModuleSummaryIndex *Index = nullptr); //===----------------------------------------------------------------------===// /// createFunctionInliningPass - Return a new pass object that uses a heuristic @@ -119,14 +120,17 @@ Pass *createPruneEHPass(); /// createInternalizePass - This pass loops over all of the functions in the /// input module, internalizing all globals (functions and variables) it can. //// -/// The symbols in \p ExportList are never internalized. +/// Before internalizing a symbol, the callback \p MustPreserveGV is invoked and +/// gives to the client the ability to prevent internalizing specific symbols. /// /// The symbol in DSOList are internalized if it is safe to drop them from /// the symbol table. /// /// Note that commandline options that are used with the above function are not /// used now! -ModulePass *createInternalizePass(ArrayRef<const char *> ExportList); +ModulePass * +createInternalizePass(std::function<bool(const GlobalValue &)> MustPreserveGV); + /// createInternalizePass - Same as above, but with an empty exportList. ModulePass *createInternalizePass(); @@ -183,15 +187,6 @@ ModulePass *createBlockExtractorPass(); ModulePass *createStripDeadPrototypesPass(); //===----------------------------------------------------------------------===// -/// createPostOrderFunctionAttrsPass - This pass walks SCCs of the call graph -/// in post-order to deduce and propagate function attributes. It can discover -/// functions that do not access memory, or only read memory, and give them the -/// readnone/readonly attribute. It also discovers function arguments that are -/// not captured by the function and marks them with the nocapture attribute. -/// -Pass *createPostOrderFunctionAttrsPass(); - -//===----------------------------------------------------------------------===// /// createReversePostOrderFunctionAttrsPass - This pass walks SCCs of the call /// graph in RPO to deduce and propagate function attributes. Currently it /// only handles synthesizing norecurse attributes. @@ -219,13 +214,17 @@ ModulePass *createMetaRenamerPass(); /// manager. ModulePass *createBarrierNoopPass(); -/// \brief This pass lowers bitset metadata and the llvm.bitset.test intrinsic -/// to bitsets. -ModulePass *createLowerBitSetsPass(); +/// \brief This pass lowers type metadata and the llvm.type.test intrinsic to +/// bitsets. +ModulePass *createLowerTypeTestsPass(); /// \brief This pass export CFI checks for use by external modules. ModulePass *createCrossDSOCFIPass(); +/// \brief This pass implements whole-program devirtualization using type +/// metadata. +ModulePass *createWholeProgramDevirtPass(); + //===----------------------------------------------------------------------===// // SampleProfilePass - Loads sample profile data from disk and generates // IR metadata to reflect the profile. diff --git a/include/llvm/Transforms/IPO/ConstantMerge.h b/include/llvm/Transforms/IPO/ConstantMerge.h new file mode 100644 index 000000000000..1d4da43f6a7b --- /dev/null +++ b/include/llvm/Transforms/IPO/ConstantMerge.h @@ -0,0 +1,35 @@ +//===- ConstantMerge.h - Merge duplicate global constants -------*- 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 to a pass that merges duplicate global +// constants together into a single constant that is shared. This is useful +// because some passes (ie TraceValues) insert a lot of string constants into +// the program, regardless of whether or not an existing string is available. +// +// Algorithm: ConstantMerge is designed to build up a map of available constants +// and eliminate duplicates when it is initialized. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H +#define LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A pass that merges duplicate global constants into a single constant. +class ConstantMergePass : public PassInfoMixin<ConstantMergePass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; +} + +#endif // LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H diff --git a/include/llvm/Transforms/IPO/CrossDSOCFI.h b/include/llvm/Transforms/IPO/CrossDSOCFI.h new file mode 100644 index 000000000000..409604a7f330 --- /dev/null +++ b/include/llvm/Transforms/IPO/CrossDSOCFI.h @@ -0,0 +1,28 @@ +//===-- CrossDSOCFI.cpp - Externalize this module's CFI checks --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass exports all llvm.bitset's found in the module in the form of a +// __cfi_check function, which can be used to verify cross-DSO call targets. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H +#define LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class CrossDSOCFIPass : public PassInfoMixin<CrossDSOCFIPass> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; +} +#endif // LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H + diff --git a/include/llvm/Transforms/IPO/DeadArgumentElimination.h b/include/llvm/Transforms/IPO/DeadArgumentElimination.h new file mode 100644 index 000000000000..e179afa956f6 --- /dev/null +++ b/include/llvm/Transforms/IPO/DeadArgumentElimination.h @@ -0,0 +1,133 @@ +//===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass deletes dead arguments from internal functions. Dead argument +// elimination removes arguments which are directly dead, as well as arguments +// only passed into function calls as dead arguments of other functions. This +// pass also deletes dead return values in a similar way. +// +// This pass is often useful as a cleanup pass to run after aggressive +// interprocedural passes, which add possibly-dead arguments or return values. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H +#define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +#include <map> +#include <set> +#include <string> + +namespace llvm { + +/// Eliminate dead arguments (and return values) from functions. +class DeadArgumentEliminationPass + : public PassInfoMixin<DeadArgumentEliminationPass> { +public: + /// Struct that represents (part of) either a return value or a function + /// argument. Used so that arguments and return values can be used + /// interchangeably. + struct RetOrArg { + RetOrArg(const Function *F, unsigned Idx, bool IsArg) + : F(F), Idx(Idx), IsArg(IsArg) {} + const Function *F; + unsigned Idx; + bool IsArg; + + /// Make RetOrArg comparable, so we can put it into a map. + bool operator<(const RetOrArg &O) const { + return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg); + } + + /// Make RetOrArg comparable, so we can easily iterate the multimap. + bool operator==(const RetOrArg &O) const { + return F == O.F && Idx == O.Idx && IsArg == O.IsArg; + } + + std::string getDescription() const { + return (Twine(IsArg ? "Argument #" : "Return value #") + Twine(Idx) + + " of function " + F->getName()) + .str(); + } + }; + + /// Liveness enum - During our initial pass over the program, we determine + /// that things are either alive or maybe alive. We don't mark anything + /// explicitly dead (even if we know they are), since anything not alive + /// with no registered uses (in Uses) will never be marked alive and will + /// thus become dead in the end. + enum Liveness { Live, MaybeLive }; + + /// Convenience wrapper + RetOrArg CreateRet(const Function *F, unsigned Idx) { + return RetOrArg(F, Idx, false); + } + /// Convenience wrapper + RetOrArg CreateArg(const Function *F, unsigned Idx) { + return RetOrArg(F, Idx, true); + } + + typedef std::multimap<RetOrArg, RetOrArg> UseMap; + /// This maps a return value or argument to any MaybeLive return values or + /// arguments it uses. This allows the MaybeLive values to be marked live + /// when any of its users is marked live. + /// For example (indices are left out for clarity): + /// - Uses[ret F] = ret G + /// This means that F calls G, and F returns the value returned by G. + /// - Uses[arg F] = ret G + /// This means that some function calls G and passes its result as an + /// argument to F. + /// - Uses[ret F] = arg F + /// This means that F returns one of its own arguments. + /// - Uses[arg F] = arg G + /// This means that G calls F and passes one of its own (G's) arguments + /// directly to F. + UseMap Uses; + + typedef std::set<RetOrArg> LiveSet; + typedef std::set<const Function *> LiveFuncSet; + + /// This set contains all values that have been determined to be live. + LiveSet LiveValues; + /// This set contains all values that are cannot be changed in any way. + LiveFuncSet LiveFunctions; + + typedef SmallVector<RetOrArg, 5> UseVector; + + /// This allows this pass to do double-duty as the dead arg hacking pass + /// (used only by bugpoint). + bool ShouldHackArguments = false; + +public: + DeadArgumentEliminationPass(bool ShouldHackArguments_ = false) + : ShouldHackArguments(ShouldHackArguments_) {} + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); + +private: + Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); + Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses, + unsigned RetValNum = -1U); + Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); + + void SurveyFunction(const Function &F); + void MarkValue(const RetOrArg &RA, Liveness L, + const UseVector &MaybeLiveUses); + void MarkLive(const RetOrArg &RA); + void MarkLive(const Function &F); + void PropagateLiveness(const RetOrArg &RA); + bool RemoveDeadStuffFromFunction(Function *F); + bool DeleteDeadVarargs(Function &Fn); + bool RemoveDeadArgumentsFromCallers(Function &Fn); +}; +} + +#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H diff --git a/include/llvm/Transforms/IPO/ElimAvailExtern.h b/include/llvm/Transforms/IPO/ElimAvailExtern.h new file mode 100644 index 000000000000..88a0e9bd8ce0 --- /dev/null +++ b/include/llvm/Transforms/IPO/ElimAvailExtern.h @@ -0,0 +1,31 @@ +//===- ElimAvailExtern.h - Optimize Global Variables ------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This transform is designed to eliminate available external global +// definitions from the program, turning them into declarations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H +#define LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A pass that transforms external global definitions into declarations. +class EliminateAvailableExternallyPass + : public PassInfoMixin<EliminateAvailableExternallyPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; +} + +#endif // LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H diff --git a/include/llvm/Transforms/IPO/ForceFunctionAttrs.h b/include/llvm/Transforms/IPO/ForceFunctionAttrs.h index 0ff4afe79b0c..ff8a6546f059 100644 --- a/include/llvm/Transforms/IPO/ForceFunctionAttrs.h +++ b/include/llvm/Transforms/IPO/ForceFunctionAttrs.h @@ -21,10 +21,8 @@ namespace llvm { /// Pass which forces specific function attributes into the IR, primarily as /// a debugging tool. -class ForceFunctionAttrsPass { -public: - static StringRef name() { return "ForceFunctionAttrsPass"; } - PreservedAnalyses run(Module &M); +struct ForceFunctionAttrsPass : PassInfoMixin<ForceFunctionAttrsPass> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); }; /// Create a legacy pass manager instance of a pass to force function attrs. diff --git a/include/llvm/Transforms/IPO/FunctionAttrs.h b/include/llvm/Transforms/IPO/FunctionAttrs.h new file mode 100644 index 000000000000..c44cc43fc0f6 --- /dev/null +++ b/include/llvm/Transforms/IPO/FunctionAttrs.h @@ -0,0 +1,57 @@ +//===-- FunctionAttrs.h - Compute function attrs --------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// Provides passes for computing function attributes based on interprocedural +/// analyses. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H +#define LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H + +#include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Computes function attributes in post-order over the call graph. +/// +/// By operating in post-order, this pass computes precise attributes for +/// called functions prior to processsing their callers. This "bottom-up" +/// approach allows powerful interprocedural inference of function attributes +/// like memory access patterns, etc. It can discover functions that do not +/// access memory, or only read memory, and give them the readnone/readonly +/// attribute. It also discovers function arguments that are not captured by +/// the function and marks them with the nocapture attribute. +struct PostOrderFunctionAttrsPass : PassInfoMixin<PostOrderFunctionAttrsPass> { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM); +}; + +/// Create a legacy pass manager instance of a pass to compute function attrs +/// in post-order. +Pass *createPostOrderFunctionAttrsLegacyPass(); + +/// A pass to do RPO deduction and propagation of function attributes. +/// +/// This pass provides a general RPO or "top down" propagation of +/// function attributes. For a few (rare) cases, we can deduce significantly +/// more about function attributes by working in RPO, so this pass +/// provides the compliment to the post-order pass above where the majority of +/// deduction is performed. +// FIXME: Currently there is no RPO CGSCC pass structure to slide into and so +// this is a boring module pass, but eventually it should be an RPO CGSCC pass +// when such infrastructure is available. +class ReversePostOrderFunctionAttrsPass + : public PassInfoMixin<ReversePostOrderFunctionAttrsPass> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h index d7707790a017..ba5db2b5c739 100644 --- a/include/llvm/Transforms/IPO/FunctionImport.h +++ b/include/llvm/Transforms/IPO/FunctionImport.h @@ -11,33 +11,113 @@ #define LLVM_FUNCTIONIMPORT_H #include "llvm/ADT/StringMap.h" +#include "llvm/IR/GlobalValue.h" +#include "llvm/IR/ModuleSummaryIndex.h" + #include <functional> +#include <map> +#include <unordered_set> +#include <utility> namespace llvm { class LLVMContext; +class GlobalValueSummary; class Module; -class FunctionInfoIndex; /// The function importer is automatically importing function from other modules /// based on the provided summary informations. class FunctionImporter { +public: + /// Set of functions to import from a source module. Each entry is a map + /// containing all the functions to import for a source module. + /// The keys is the GUID identifying a function to import, and the value + /// is the threshold applied when deciding to import it. + typedef std::map<GlobalValue::GUID, unsigned> FunctionsToImportTy; - /// The summaries index used to trigger importing. - const FunctionInfoIndex &Index; + /// The map contains an entry for every module to import from, the key being + /// the module identifier to pass to the ModuleLoader. The value is the set of + /// functions to import. + typedef StringMap<FunctionsToImportTy> ImportMapTy; - /// Factory function to load a Module for a given identifier - std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader; + /// The set contains an entry for every global value the module exports. + typedef std::unordered_set<GlobalValue::GUID> ExportSetTy; -public: /// Create a Function Importer. FunctionImporter( - const FunctionInfoIndex &Index, + const ModuleSummaryIndex &Index, std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader) - : Index(Index), ModuleLoader(ModuleLoader) {} + : Index(Index), ModuleLoader(std::move(ModuleLoader)) {} + + /// Import functions in Module \p M based on the supplied import list. + /// \p ForceImportReferencedDiscardableSymbols will set the ModuleLinker in + /// a mode where referenced discarable symbols in the source modules will be + /// imported as well even if they are not present in the ImportList. + bool importFunctions(Module &M, const ImportMapTy &ImportList, + bool ForceImportReferencedDiscardableSymbols = false); - /// Import functions in Module \p M based on the summary informations. - bool importFunctions(Module &M); +private: + /// The summaries index used to trigger importing. + const ModuleSummaryIndex &Index; + + /// Factory function to load a Module for a given identifier + std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader; }; + +/// Compute all the imports and exports for every module in the Index. +/// +/// \p ModuleToDefinedGVSummaries contains for each Module a map +/// (GUID -> Summary) for every global defined in the module. +/// +/// \p ImportLists will be populated with an entry for every Module we are +/// importing into. This entry is itself a map that can be passed to +/// FunctionImporter::importFunctions() above (see description there). +/// +/// \p ExportLists contains for each Module the set of globals (GUID) that will +/// be imported by another module, or referenced by such a function. I.e. this +/// is the set of globals that need to be promoted/renamed appropriately. +void ComputeCrossModuleImport( + const ModuleSummaryIndex &Index, + const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, + StringMap<FunctionImporter::ImportMapTy> &ImportLists, + StringMap<FunctionImporter::ExportSetTy> &ExportLists); + +/// Compute all the imports for the given module using the Index. +/// +/// \p ImportList will be populated with a map that can be passed to +/// FunctionImporter::importFunctions() above (see description there). +void ComputeCrossModuleImportForModule( + StringRef ModulePath, const ModuleSummaryIndex &Index, + FunctionImporter::ImportMapTy &ImportList); + +/// Compute the set of summaries needed for a ThinLTO backend compilation of +/// \p ModulePath. +// +/// This includes summaries from that module (in case any global summary based +/// optimizations were recorded) and from any definitions in other modules that +/// should be imported. +// +/// \p ModuleToSummariesForIndex will be populated with the needed summaries +/// from each required module path. Use a std::map instead of StringMap to get +/// stable order for bitcode emission. +void gatherImportedSummariesForModule( + StringRef ModulePath, + const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, + const StringMap<FunctionImporter::ImportMapTy> &ImportLists, + std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); + +std::error_code +EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename, + const StringMap<FunctionImporter::ImportMapTy> &ImportLists); + +/// Resolve WeakForLinker values in \p TheModule based on the information +/// recorded in the summaries during global summary-based analysis. +void thinLTOResolveWeakForLinkerModule(Module &TheModule, + const GVSummaryMapTy &DefinedGlobals); + +/// Internalize \p TheModule based on the information recorded in the summaries +/// during global summary-based analysis. +void thinLTOInternalizeModule(Module &TheModule, + const GVSummaryMapTy &DefinedGlobals); } #endif // LLVM_FUNCTIONIMPORT_H diff --git a/include/llvm/Transforms/IPO/GlobalDCE.h b/include/llvm/Transforms/IPO/GlobalDCE.h new file mode 100644 index 000000000000..57e174c2a37f --- /dev/null +++ b/include/llvm/Transforms/IPO/GlobalDCE.h @@ -0,0 +1,46 @@ +//===-- GlobalDCE.h - DCE unreachable internal functions ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This transform is designed to eliminate unreachable internal globals from the +// program. It uses an aggressive algorithm, searching out globals that are +// known to be alive. After it finds all of the globals which are needed, it +// deletes whatever is left over. This allows it to delete recursive chunks of +// the program which are unreachable. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_GLOBALDCE_H +#define LLVM_TRANSFORMS_IPO_GLOBALDCE_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" +#include <unordered_map> + +namespace llvm { + +/// Pass to remove unused function declarations. +class GlobalDCEPass : public PassInfoMixin<GlobalDCEPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); + +private: + SmallPtrSet<GlobalValue*, 32> AliveGlobals; + SmallPtrSet<Constant *, 8> SeenConstants; + std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers; + + /// Mark the specific global value as needed, and + /// recursively mark anything that it uses as also needed. + void GlobalIsNeeded(GlobalValue *GV); + void MarkUsedGlobalsAsNeeded(Constant *C); + bool RemoveUnusedGlobalValue(GlobalValue &GV); +}; + +} + +#endif // LLVM_TRANSFORMS_IPO_GLOBALDCE_H diff --git a/include/llvm/Transforms/IPO/GlobalOpt.h b/include/llvm/Transforms/IPO/GlobalOpt.h new file mode 100644 index 000000000000..5a25a6db4390 --- /dev/null +++ b/include/llvm/Transforms/IPO/GlobalOpt.h @@ -0,0 +1,32 @@ +//===- GlobalOpt.h - Optimize Global Variables ------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass transforms simple global variables that never have their address +// taken. If obviously true, it marks read/write globals as constant, deletes +// variables only stored to, etc. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_GLOBALOPT_H +#define LLVM_TRANSFORMS_IPO_GLOBALOPT_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Optimize globals that never have their address taken. +class GlobalOptPass : public PassInfoMixin<GlobalOptPass> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; + +} + +#endif // LLVM_TRANSFORMS_IPO_GLOBALOPT_H diff --git a/include/llvm/Transforms/IPO/InferFunctionAttrs.h b/include/llvm/Transforms/IPO/InferFunctionAttrs.h index 80afc02c62ae..f5cbf9eb0613 100644 --- a/include/llvm/Transforms/IPO/InferFunctionAttrs.h +++ b/include/llvm/Transforms/IPO/InferFunctionAttrs.h @@ -23,10 +23,8 @@ namespace llvm { /// A pass which infers function attributes from the names and signatures of /// function declarations in a module. -class InferFunctionAttrsPass { -public: - static StringRef name() { return "InferFunctionAttrsPass"; } - PreservedAnalyses run(Module &M, AnalysisManager<Module> *AM); +struct InferFunctionAttrsPass : PassInfoMixin<InferFunctionAttrsPass> { + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); }; /// Create a legacy pass manager instance of a pass to infer function diff --git a/include/llvm/Transforms/IPO/InlinerPass.h b/include/llvm/Transforms/IPO/InlinerPass.h index 58ef0cbbfb5d..59e10608a9ba 100644 --- a/include/llvm/Transforms/IPO/InlinerPass.h +++ b/include/llvm/Transforms/IPO/InlinerPass.h @@ -24,6 +24,7 @@ class AssumptionCacheTracker; class CallSite; class DataLayout; class InlineCost; +class ProfileSummaryInfo; template <class PtrType, unsigned SmallSize> class SmallPtrSet; /// Inliner - This class contains all of the helper code which is used to @@ -31,7 +32,7 @@ template <class PtrType, unsigned SmallSize> class SmallPtrSet; /// struct Inliner : public CallGraphSCCPass { explicit Inliner(char &ID); - explicit Inliner(char &ID, int Threshold, bool InsertLifetime); + explicit Inliner(char &ID, bool InsertLifetime); /// getAnalysisUsage - For this class, we declare that we require and preserve /// the call graph. If the derived class implements this method, it should @@ -47,18 +48,6 @@ struct Inliner : public CallGraphSCCPass { // processing to avoid breaking the SCC traversal. bool doFinalization(CallGraph &CG) override; - /// This method returns the value specified by the -inline-threshold value, - /// specified on the command line. This is typically not directly needed. - /// - unsigned getInlineThreshold() const { return InlineThreshold; } - - /// Calculate the inline threshold for given Caller. This threshold is lower - /// if the caller is marked with OptimizeForSize and -inline-threshold is not - /// given on the comand line. It is higher if the callee is marked with the - /// inlinehint attribute. - /// - unsigned getInlineThreshold(CallSite CS) const; - /// getInlineCost - This method must be implemented by the subclass to /// determine the cost of inlining the specified call site. If the cost /// returned is greater than the current inline threshold, the call site is @@ -74,19 +63,30 @@ struct Inliner : public CallGraphSCCPass { /// deal with that subset of the functions. bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly = false); -private: - // InlineThreshold - Cache the value here for easy access. - unsigned InlineThreshold; + /// This function performs the main work of the pass. The default + /// of Inlinter::runOnSCC() calls skipSCC() before calling this method, but + /// derived classes which cannot be skipped can override that method and + /// call this function unconditionally. + bool inlineCalls(CallGraphSCC &SCC); +private: // InsertLifetime - Insert @llvm.lifetime intrinsics. bool InsertLifetime; /// shouldInline - Return true if the inliner should attempt to /// inline at the given CallSite. bool shouldInline(CallSite CS); + /// Return true if inlining of CS can block the caller from being + /// inlined which is proved to be more beneficial. \p IC is the + /// estimated inline cost associated with callsite \p CS. + /// \p TotalAltCost will be set to the estimated cost of inlining the caller + /// if \p CS is suppressed for inlining. + bool shouldBeDeferred(Function *Caller, CallSite CS, InlineCost IC, + int &TotalAltCost); protected: AssumptionCacheTracker *ACT; + ProfileSummaryInfo *PSI; }; } // End llvm namespace diff --git a/include/llvm/Transforms/IPO/Internalize.h b/include/llvm/Transforms/IPO/Internalize.h new file mode 100644 index 000000000000..ba1b06877d3a --- /dev/null +++ b/include/llvm/Transforms/IPO/Internalize.h @@ -0,0 +1,79 @@ +//====- Internalize.h - Internalization API ---------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass loops over all of the functions and variables in the input module. +// If the function or variable does not need to be preserved according to the +// client supplied callback, it is marked as internal. +// +// This transformation would not be legal in a regular compilation, but it gets +// extra information from the linker about what is safe. +// +// For example: Internalizing a function with external linkage. Only if we are +// told it is only used from within this module, it is safe to do it. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INTERNALIZE_H +#define LLVM_TRANSFORMS_IPO_INTERNALIZE_H + +#include "llvm/ADT/StringSet.h" +#include "llvm/IR/GlobalValue.h" +#include "llvm/IR/PassManager.h" +#include <functional> +#include <set> + +namespace llvm { +class Module; +class CallGraph; + +/// A pass that internalizes all functions and variables other than those that +/// must be preserved according to \c MustPreserveGV. +class InternalizePass : public PassInfoMixin<InternalizePass> { + /// Client supplied callback to control wheter a symbol must be preserved. + const std::function<bool(const GlobalValue &)> MustPreserveGV; + /// Set of symbols private to the compiler that this pass should not touch. + StringSet<> AlwaysPreserved; + + /// Return false if we're allowed to internalize this GV. + bool shouldPreserveGV(const GlobalValue &GV); + /// Internalize GV if it is possible to do so, i.e. it is not externally + /// visible and is not a member of an externally visible comdat. + bool maybeInternalize(GlobalValue &GV, + const std::set<const Comdat *> &ExternalComdats); + /// If GV is part of a comdat and is externally visible, keep track of its + /// comdat so that we don't internalize any of its members. + void checkComdatVisibility(GlobalValue &GV, + std::set<const Comdat *> &ExternalComdats); + +public: + InternalizePass(); + InternalizePass(std::function<bool(const GlobalValue &)> MustPreserveGV) + : MustPreserveGV(std::move(MustPreserveGV)) {} + + /// Run the internalizer on \p TheModule, returns true if any changes was + /// made. + /// + /// If the CallGraph \p CG is supplied, it will be updated when + /// internalizing a function (by removing any edge from the "external node") + bool internalizeModule(Module &TheModule, CallGraph *CG = nullptr); + + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; + +/// Helper function to internalize functions and variables in a Module. +inline bool +internalizeModule(Module &TheModule, + std::function<bool(const GlobalValue &)> MustPreserveGV, + CallGraph *CG = nullptr) { + return InternalizePass(std::move(MustPreserveGV)) + .internalizeModule(TheModule, CG); +} +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_INTERNALIZE_H diff --git a/include/llvm/Transforms/IPO/LowerBitSets.h b/include/llvm/Transforms/IPO/LowerTypeTests.h index e5fb7b98fcb3..93d4fb94e2c4 100644 --- a/include/llvm/Transforms/IPO/LowerBitSets.h +++ b/include/llvm/Transforms/IPO/LowerTypeTests.h @@ -1,4 +1,4 @@ -//===- LowerBitSets.h - Bitset lowering pass --------------------*- C++ -*-===// +//===- LowerTypeTests.h - type metadata lowering pass -----------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -7,18 +7,21 @@ // //===----------------------------------------------------------------------===// // -// This file defines parts of the bitset lowering pass implementation that may -// be usefully unit tested. +// This file defines parts of the type test lowering pass implementation that +// may be usefully unit tested. // //===----------------------------------------------------------------------===// -#ifndef LLVM_TRANSFORMS_IPO_LOWERBITSETS_H -#define LLVM_TRANSFORMS_IPO_LOWERBITSETS_H +#ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H +#define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" -#include <stdint.h> +#include <cstdint> +#include <cstring> #include <limits> #include <set> #include <vector> @@ -30,6 +33,8 @@ class GlobalObject; class Value; class raw_ostream; +namespace lowertypetests { + struct BitSetInfo { // The indices of the set bits in the bitset. std::set<uint64_t> Bits; @@ -196,6 +201,13 @@ struct ByteArrayBuilder { uint64_t &AllocByteOffset, uint8_t &AllocMask); }; -} // namespace llvm +} // end namespace lowertypetests + +class LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; + +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H diff --git a/include/llvm/Transforms/IPO/PartialInlining.h b/include/llvm/Transforms/IPO/PartialInlining.h new file mode 100644 index 000000000000..48eb1e30a191 --- /dev/null +++ b/include/llvm/Transforms/IPO/PartialInlining.h @@ -0,0 +1,32 @@ +//===- PartialInlining.h - Inline parts of functions --------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs partial inlining, typically by inlining an if statement +// that surrounds the body of the function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_PARTIALINLINING_H +#define LLVM_TRANSFORMS_IPO_PARTIALINLINING_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Pass to remove unused function declarations. +class PartialInlinerPass : public PassInfoMixin<PartialInlinerPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); + +private: + Function *unswitchFunction(Function *F); +}; +} +#endif // LLVM_TRANSFORMS_IPO_PARTIALINLINING_H diff --git a/include/llvm/Transforms/IPO/PassManagerBuilder.h b/include/llvm/Transforms/IPO/PassManagerBuilder.h index a4e7bce8ef4a..4f483deeefe5 100644 --- a/include/llvm/Transforms/IPO/PassManagerBuilder.h +++ b/include/llvm/Transforms/IPO/PassManagerBuilder.h @@ -15,11 +15,13 @@ #ifndef LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H #define LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H +#include <functional> #include <memory> +#include <string> #include <vector> namespace llvm { -class FunctionInfoIndex; +class ModuleSummaryIndex; class Pass; class TargetLibraryInfoImpl; class TargetMachine; @@ -58,8 +60,9 @@ class PassManagerBuilder { public: /// Extensions are passed the builder itself (so they can see how it is /// configured) as well as the pass manager to add stuff to. - typedef void (*ExtensionFn)(const PassManagerBuilder &Builder, - legacy::PassManagerBase &PM); + typedef std::function<void(const PassManagerBuilder &Builder, + legacy::PassManagerBase &PM)> + ExtensionFn; enum ExtensionPointTy { /// EP_EarlyAsPossible - This extension point allows adding passes before /// any other transformations, allowing them to see the code as it is coming @@ -116,8 +119,8 @@ public: /// added to the per-module passes. Pass *Inliner; - /// The function summary index to use for function importing. - const FunctionInfoIndex *FunctionIndex; + /// The module summary index to use for function importing. + const ModuleSummaryIndex *ModuleSummary; bool DisableTailCalls; bool DisableUnitAtATime; @@ -132,10 +135,17 @@ public: bool VerifyOutput; bool MergeFunctions; bool PrepareForLTO; + bool PrepareForThinLTO; + bool PerformThinLTO; + + /// Profile data file name that the instrumentation will be written to. + std::string PGOInstrGen; + /// Path of the profile data file. + std::string PGOInstrUse; private: /// ExtensionList - This is list of all of the extensions that are registered. - std::vector<std::pair<ExtensionPointTy, ExtensionFn> > Extensions; + std::vector<std::pair<ExtensionPointTy, ExtensionFn>> Extensions; public: PassManagerBuilder(); @@ -152,6 +162,9 @@ private: void addInitialAliasAnalysisPasses(legacy::PassManagerBase &PM) const; void addLTOOptimizationPasses(legacy::PassManagerBase &PM); void addLateLTOOptimizationPasses(legacy::PassManagerBase &PM); + void addPGOInstrPasses(legacy::PassManagerBase &MPM); + void addFunctionSimplificationPasses(legacy::PassManagerBase &MPM); + void addInstructionCombiningPass(legacy::PassManagerBase &MPM) const; public: /// populateFunctionPassManager - This fills in the function pass manager, @@ -162,6 +175,7 @@ public: /// populateModulePassManager - This sets up the primary pass manager. void populateModulePassManager(legacy::PassManagerBase &MPM); void populateLTOPassManager(legacy::PassManagerBase &PM); + void populateThinLTOPassManager(legacy::PassManagerBase &PM); }; /// Registers a function for adding a standard set of passes. This should be @@ -171,7 +185,7 @@ public: struct RegisterStandardPasses { RegisterStandardPasses(PassManagerBuilder::ExtensionPointTy Ty, PassManagerBuilder::ExtensionFn Fn) { - PassManagerBuilder::addGlobalExtension(Ty, Fn); + PassManagerBuilder::addGlobalExtension(Ty, std::move(Fn)); } }; diff --git a/include/llvm/Transforms/IPO/SCCP.h b/include/llvm/Transforms/IPO/SCCP.h new file mode 100644 index 000000000000..fab731342144 --- /dev/null +++ b/include/llvm/Transforms/IPO/SCCP.h @@ -0,0 +1,34 @@ +//===- SCCP.h - Sparse Conditional Constant Propagation ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass implements interprocedural sparse conditional constant +// propagation and merging. +// +// Specifically, this: +// * Assumes values are constant unless proven otherwise +// * Assumes BasicBlocks are dead unless proven otherwise +// * Proves values to be constant, and replaces them with constants +// * Proves conditional branches to be unconditional +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_SCCP_H +#define LLVM_TRANSFORMS_IPO_SCCP_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +/// Pass to perform interprocedural constant propagation. +class IPSCCPPass : public PassInfoMixin<IPSCCPPass> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; +} +#endif // LLVM_TRANSFORMS_IPO_SCCP_H diff --git a/include/llvm/Transforms/IPO/StripDeadPrototypes.h b/include/llvm/Transforms/IPO/StripDeadPrototypes.h index 9dddd12871c4..5a05cd75c9d5 100644 --- a/include/llvm/Transforms/IPO/StripDeadPrototypes.h +++ b/include/llvm/Transforms/IPO/StripDeadPrototypes.h @@ -23,10 +23,8 @@ namespace llvm { /// Pass to remove unused function declarations. -class StripDeadPrototypesPass { -public: - static StringRef name() { return "StripDeadPrototypesPass"; } - PreservedAnalyses run(Module &M); +struct StripDeadPrototypesPass : PassInfoMixin<StripDeadPrototypesPass> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); }; } diff --git a/include/llvm/Transforms/IPO/WholeProgramDevirt.h b/include/llvm/Transforms/IPO/WholeProgramDevirt.h new file mode 100644 index 000000000000..2bd20c95702c --- /dev/null +++ b/include/llvm/Transforms/IPO/WholeProgramDevirt.h @@ -0,0 +1,223 @@ +//===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- 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 parts of the whole-program devirtualization pass +// implementation that may be usefully unit tested. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H +#define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" +#include <cassert> +#include <cstdint> +#include <utility> +#include <vector> + +namespace llvm { + +template <typename T> class ArrayRef; +template <typename T> class MutableArrayRef; +class Function; +class GlobalVariable; + +namespace wholeprogramdevirt { + +// A bit vector that keeps track of which bits are used. We use this to +// pack constant values compactly before and after each virtual table. +struct AccumBitVector { + std::vector<uint8_t> Bytes; + + // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not. + std::vector<uint8_t> BytesUsed; + + std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) { + if (Bytes.size() < Pos + Size) { + Bytes.resize(Pos + Size); + BytesUsed.resize(Pos + Size); + } + return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos); + } + + // Set little-endian value Val with size Size at bit position Pos, + // and mark bytes as used. + void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) { + assert(Pos % 8 == 0); + auto DataUsed = getPtrToData(Pos / 8, Size); + for (unsigned I = 0; I != Size; ++I) { + DataUsed.first[I] = Val >> (I * 8); + assert(!DataUsed.second[I]); + DataUsed.second[I] = 0xff; + } + } + + // Set big-endian value Val with size Size at bit position Pos, + // and mark bytes as used. + void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) { + assert(Pos % 8 == 0); + auto DataUsed = getPtrToData(Pos / 8, Size); + for (unsigned I = 0; I != Size; ++I) { + DataUsed.first[Size - I - 1] = Val >> (I * 8); + assert(!DataUsed.second[Size - I - 1]); + DataUsed.second[Size - I - 1] = 0xff; + } + } + + // Set bit at bit position Pos to b and mark bit as used. + void setBit(uint64_t Pos, bool b) { + auto DataUsed = getPtrToData(Pos / 8, 1); + if (b) + *DataUsed.first |= 1 << (Pos % 8); + assert(!(*DataUsed.second & (1 << Pos % 8))); + *DataUsed.second |= 1 << (Pos % 8); + } +}; + +// The bits that will be stored before and after a particular vtable. +struct VTableBits { + // The vtable global. + GlobalVariable *GV; + + // Cache of the vtable's size in bytes. + uint64_t ObjectSize = 0; + + // The bit vector that will be laid out before the vtable. Note that these + // bytes are stored in reverse order until the globals are rebuilt. This means + // that any values in the array must be stored using the opposite endianness + // from the target. + AccumBitVector Before; + + // The bit vector that will be laid out after the vtable. + AccumBitVector After; +}; + +// Information about a member of a particular type identifier. +struct TypeMemberInfo { + // The VTableBits for the vtable. + VTableBits *Bits; + + // The offset in bytes from the start of the vtable (i.e. the address point). + uint64_t Offset; + + bool operator<(const TypeMemberInfo &other) const { + return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset); + } +}; + +// A virtual call target, i.e. an entry in a particular vtable. +struct VirtualCallTarget { + VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM); + + // For testing only. + VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian) + : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian) {} + + // The function stored in the vtable. + Function *Fn; + + // A pointer to the type identifier member through which the pointer to Fn is + // accessed. + const TypeMemberInfo *TM; + + // When doing virtual constant propagation, this stores the return value for + // the function when passed the currently considered argument list. + uint64_t RetVal; + + // Whether the target is big endian. + bool IsBigEndian; + + // The minimum byte offset before the address point. This covers the bytes in + // the vtable object before the address point (e.g. RTTI, access-to-top, + // vtables for other base classes) and is equal to the offset from the start + // of the vtable object to the address point. + uint64_t minBeforeBytes() const { return TM->Offset; } + + // The minimum byte offset after the address point. This covers the bytes in + // the vtable object after the address point (e.g. the vtable for the current + // class and any later base classes) and is equal to the size of the vtable + // object minus the offset from the start of the vtable object to the address + // point. + uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; } + + // The number of bytes allocated (for the vtable plus the byte array) before + // the address point. + uint64_t allocatedBeforeBytes() const { + return minBeforeBytes() + TM->Bits->Before.Bytes.size(); + } + + // The number of bytes allocated (for the vtable plus the byte array) after + // the address point. + uint64_t allocatedAfterBytes() const { + return minAfterBytes() + TM->Bits->After.Bytes.size(); + } + + // Set the bit at position Pos before the address point to RetVal. + void setBeforeBit(uint64_t Pos) { + assert(Pos >= 8 * minBeforeBytes()); + TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal); + } + + // Set the bit at position Pos after the address point to RetVal. + void setAfterBit(uint64_t Pos) { + assert(Pos >= 8 * minAfterBytes()); + TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal); + } + + // Set the bytes at position Pos before the address point to RetVal. + // Because the bytes in Before are stored in reverse order, we use the + // opposite endianness to the target. + void setBeforeBytes(uint64_t Pos, uint8_t Size) { + assert(Pos >= 8 * minBeforeBytes()); + if (IsBigEndian) + TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size); + else + TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size); + } + + // Set the bytes at position Pos after the address point to RetVal. + void setAfterBytes(uint64_t Pos, uint8_t Size) { + assert(Pos >= 8 * minAfterBytes()); + if (IsBigEndian) + TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size); + else + TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size); + } +}; + +// Find the minimum offset that we may store a value of size Size bits at. If +// IsAfter is set, look for an offset before the object, otherwise look for an +// offset after the object. +uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter, + uint64_t Size); + +// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the +// given allocation offset before the vtable address. Stores the computed +// byte/bit offset to OffsetByte/OffsetBit. +void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets, + uint64_t AllocBefore, unsigned BitWidth, + int64_t &OffsetByte, uint64_t &OffsetBit); + +// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the +// given allocation offset after the vtable address. Stores the computed +// byte/bit offset to OffsetByte/OffsetBit. +void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets, + uint64_t AllocAfter, unsigned BitWidth, + int64_t &OffsetByte, uint64_t &OffsetBit); + +} // end namespace wholeprogramdevirt + +struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H diff --git a/include/llvm/Transforms/InstCombine/InstCombine.h b/include/llvm/Transforms/InstCombine/InstCombine.h index f48ec13107bc..d70b847c6892 100644 --- a/include/llvm/Transforms/InstCombine/InstCombine.h +++ b/include/llvm/Transforms/InstCombine/InstCombine.h @@ -24,23 +24,47 @@ namespace llvm { -class InstCombinePass { +class InstCombinePass : public PassInfoMixin<InstCombinePass> { InstCombineWorklist Worklist; + bool ExpensiveCombines; public: static StringRef name() { return "InstCombinePass"; } // Explicitly define constructors for MSVC. - InstCombinePass() {} - InstCombinePass(InstCombinePass &&Arg) : Worklist(std::move(Arg.Worklist)) {} + InstCombinePass(bool ExpensiveCombines = true) + : ExpensiveCombines(ExpensiveCombines) {} + InstCombinePass(InstCombinePass &&Arg) + : Worklist(std::move(Arg.Worklist)), + ExpensiveCombines(Arg.ExpensiveCombines) {} InstCombinePass &operator=(InstCombinePass &&RHS) { Worklist = std::move(RHS.Worklist); + ExpensiveCombines = RHS.ExpensiveCombines; return *this; } - PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); }; +/// \brief The legacy pass manager's instcombine pass. +/// +/// This is a basic whole-function wrapper around the instcombine utility. It +/// will try to combine all instructions in the function. +class InstructionCombiningPass : public FunctionPass { + InstCombineWorklist Worklist; + const bool ExpensiveCombines; + +public: + static char ID; // Pass identification, replacement for typeid + + InstructionCombiningPass(bool ExpensiveCombines = true) + : FunctionPass(ID), ExpensiveCombines(ExpensiveCombines) { + initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; +}; } #endif diff --git a/include/llvm/Transforms/InstCombine/InstCombineWorklist.h b/include/llvm/Transforms/InstCombine/InstCombineWorklist.h index 5d2b2d000009..32af035d07d4 100644 --- a/include/llvm/Transforms/InstCombine/InstCombineWorklist.h +++ b/include/llvm/Transforms/InstCombine/InstCombineWorklist.h @@ -11,6 +11,7 @@ #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/Instruction.h" #include "llvm/Support/Compiler.h" @@ -63,7 +64,7 @@ public: void AddInitialGroup(ArrayRef<Instruction *> List) { assert(Worklist.empty() && "Worklist must be empty to add initial group"); Worklist.reserve(List.size()+16); - WorklistMap.resize(List.size()); + WorklistMap.reserve(List.size()); DEBUG(dbgs() << "IC: ADDING: " << List.size() << " instrs to worklist\n"); unsigned Idx = 0; for (Instruction *I : reverse(List)) { diff --git a/include/llvm/Transforms/InstrProfiling.h b/include/llvm/Transforms/InstrProfiling.h new file mode 100644 index 000000000000..9ac6d63b96ae --- /dev/null +++ b/include/llvm/Transforms/InstrProfiling.h @@ -0,0 +1,105 @@ +//===- Transforms/InstrProfiling.h - Instrumentation passes ---*- 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 the interface for LLVM's PGO Instrumentation lowering +/// pass. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_INSTRPROFILING_H +#define LLVM_TRANSFORMS_INSTRPROFILING_H + +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/PassManager.h" +#include "llvm/ProfileData/InstrProf.h" +#include "llvm/Transforms/Instrumentation.h" + +namespace llvm { + +/// Instrumenation based profiling lowering pass. This pass lowers +/// the profile instrumented code generated by FE or the IR based +/// instrumentation pass. +class InstrProfiling : public PassInfoMixin<InstrProfiling> { +public: + InstrProfiling() {} + InstrProfiling(const InstrProfOptions &Options) : Options(Options) {} + + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); + bool run(Module &M); + +private: + InstrProfOptions Options; + Module *M; + struct PerFunctionProfileData { + uint32_t NumValueSites[IPVK_Last + 1]; + GlobalVariable *RegionCounters; + GlobalVariable *DataVar; + PerFunctionProfileData() : RegionCounters(nullptr), DataVar(nullptr) { + memset(NumValueSites, 0, sizeof(uint32_t) * (IPVK_Last + 1)); + } + }; + DenseMap<GlobalVariable *, PerFunctionProfileData> ProfileDataMap; + std::vector<Value *> UsedVars; + std::vector<GlobalVariable *> ReferencedNames; + GlobalVariable *NamesVar; + size_t NamesSize; + + bool isMachO() const; + + /// Get the section name for the counter variables. + StringRef getCountersSection() const; + + /// Get the section name for the name variables. + StringRef getNameSection() const; + + /// Get the section name for the profile data variables. + StringRef getDataSection() const; + + /// Get the section name for the coverage mapping data. + StringRef getCoverageSection() const; + + /// Count the number of instrumented value sites for the function. + void computeNumValueSiteCounts(InstrProfValueProfileInst *Ins); + + /// Replace instrprof_value_profile with a call to runtime library. + void lowerValueProfileInst(InstrProfValueProfileInst *Ins); + + /// Replace instrprof_increment with an increment of the appropriate value. + void lowerIncrement(InstrProfIncrementInst *Inc); + + /// Force emitting of name vars for unused functions. + void lowerCoverageData(GlobalVariable *CoverageNamesVar); + + /// Get the region counters for an increment, creating them if necessary. + /// + /// If the counter array doesn't yet exist, the profile data variables + /// referring to them will also be created. + GlobalVariable *getOrCreateRegionCounters(InstrProfIncrementInst *Inc); + + /// Emit the section with compressed function names. + void emitNameData(); + + /// Emit value nodes section for value profiling. + void emitVNodes(); + + /// Emit runtime registration functions for each profile data variable. + void emitRegistration(); + + /// Emit the necessary plumbing to pull in the runtime initialization. + void emitRuntimeHook(); + + /// Add uses of our data variables and runtime hook. + void emitUses(); + + /// Create a static initializer for our data, on platforms that need it, + /// and for any profile output file that was specified. + void emitInitialization(); +}; + +} // End llvm namespace +#endif diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h index 38dfeb04ace3..09eef7e0750e 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -80,9 +80,10 @@ ModulePass *createGCOVProfilerPass(const GCOVOptions &Options = GCOVOptions::getDefault()); // PGO Instrumention -ModulePass *createPGOInstrumentationGenPass(); +ModulePass *createPGOInstrumentationGenLegacyPass(); ModulePass * -createPGOInstrumentationUsePass(StringRef Filename = StringRef("")); +createPGOInstrumentationUseLegacyPass(StringRef Filename = StringRef("")); +ModulePass *createPGOIndirectCallPromotionLegacyPass(bool InLTO = false); /// Options for the frontend instrumentation based profiling pass. struct InstrProfOptions { @@ -96,12 +97,13 @@ struct InstrProfOptions { }; /// Insert frontend instrumentation based profiling. -ModulePass *createInstrProfilingPass( +ModulePass *createInstrProfilingLegacyPass( const InstrProfOptions &Options = InstrProfOptions()); // Insert AddressSanitizer (address sanity checking) instrumentation FunctionPass *createAddressSanitizerFunctionPass(bool CompileKernel = false, - bool Recover = false); + bool Recover = false, + bool UseAfterScope = false); ModulePass *createAddressSanitizerModulePass(bool CompileKernel = false, bool Recover = false); @@ -116,11 +118,25 @@ ModulePass *createDataFlowSanitizerPass( const std::vector<std::string> &ABIListFiles = std::vector<std::string>(), void *(*getArgTLS)() = nullptr, void *(*getRetValTLS)() = nullptr); +// Options for EfficiencySanitizer sub-tools. +struct EfficiencySanitizerOptions { + EfficiencySanitizerOptions() : ToolType(ESAN_None) {} + enum Type { + ESAN_None = 0, + ESAN_CacheFrag, + ESAN_WorkingSet, + } ToolType; +}; + +// Insert EfficiencySanitizer instrumentation. +ModulePass *createEfficiencySanitizerPass( + const EfficiencySanitizerOptions &Options = EfficiencySanitizerOptions()); + // Options for sanitizer coverage instrumentation. struct SanitizerCoverageOptions { SanitizerCoverageOptions() : CoverageType(SCK_None), IndirectCalls(false), TraceBB(false), - TraceCmp(false), Use8bitCounters(false) {} + TraceCmp(false), Use8bitCounters(false), TracePC(false) {} enum Type { SCK_None = 0, @@ -132,6 +148,7 @@ struct SanitizerCoverageOptions { bool TraceBB; bool TraceCmp; bool Use8bitCounters; + bool TracePC; }; // Insert SanitizerCoverage instrumentation. @@ -150,10 +167,6 @@ inline ModulePass *createDataFlowSanitizerPassForJIT( // checking on loads, stores, and other memory intrinsics. FunctionPass *createBoundsCheckingPass(); -/// \brief This pass splits the stack into a safe stack and an unsafe stack to -/// protect against stack-based overflow vulnerabilities. -FunctionPass *createSafeStackPass(const TargetMachine *TM = nullptr); - /// \brief Calculate what to divide by to scale counts. /// /// Given the maximum count, calculate a divisor that will scale all the diff --git a/include/llvm/Transforms/PGOInstrumentation.h b/include/llvm/Transforms/PGOInstrumentation.h new file mode 100644 index 000000000000..f6b5639e5aad --- /dev/null +++ b/include/llvm/Transforms/PGOInstrumentation.h @@ -0,0 +1,48 @@ +//===- Transforms/PGOInstrumentation.h - PGO gen/use passes ---*- 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 the interface for IR based instrumentation passes ( +/// (profile-gen, and profile-use). +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_PGOINSTRUMENTATION_H +#define LLVM_TRANSFORMS_PGOINSTRUMENTATION_H + +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Instrumentation.h" + +namespace llvm { + +/// The instrumentation (profile-instr-gen) pass for IR based PGO. +class PGOInstrumentationGen : public PassInfoMixin<PGOInstrumentationGen> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; + +/// The profile annotation (profile-instr-use) pass for IR based PGO. +class PGOInstrumentationUse : public PassInfoMixin<PGOInstrumentationUse> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); + PGOInstrumentationUse(std::string Filename = ""); + +private: + std::string ProfileFileName; +}; + +/// The indirect function call promotion pass. +class PGOIndirectCallPromotion : public PassInfoMixin<PGOIndirectCallPromotion> { +public: + PGOIndirectCallPromotion(bool IsInLTO = false) : InLTO(IsInLTO) {} + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +private: + bool InLTO; +}; + +} // End llvm namespace +#endif diff --git a/include/llvm/Transforms/SampleProfile.h b/include/llvm/Transforms/SampleProfile.h new file mode 100644 index 000000000000..0fdfa2f85e54 --- /dev/null +++ b/include/llvm/Transforms/SampleProfile.h @@ -0,0 +1,27 @@ +//===- Transforms/SampleProfile.h - SamplePGO pass--------------*- 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 the interface for the sampled PGO loader pass. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SAMPLEPROFILE_H +#define LLVM_TRANSFORMS_SAMPLEPROFILE_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// The sample profiler data loader pass. +class SampleProfileLoaderPass : public PassInfoMixin<SampleProfileLoaderPass> { +public: + PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM); +}; + +} // End llvm namespace +#endif diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index 9173de1112f3..167cc94ec81f 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -15,7 +15,6 @@ #ifndef LLVM_TRANSFORMS_SCALAR_H #define LLVM_TRANSFORMS_SCALAR_H -#include "llvm/ADT/StringRef.h" #include <functional> namespace llvm { @@ -82,6 +81,16 @@ FunctionPass *createDeadStoreEliminationPass(); // FunctionPass *createAggressiveDCEPass(); + +//===----------------------------------------------------------------------===// +// +// GuardWidening - An optimization over the @llvm.experimental.guard intrinsic +// that (optimistically) combines multiple guards into one to have fewer checks +// at runtime. +// +FunctionPass *createGuardWideningPass(); + + //===----------------------------------------------------------------------===// // // BitTrackingDCE - This pass uses a bit-tracking DCE algorithm in order to @@ -97,17 +106,6 @@ FunctionPass *createSROAPass(); //===----------------------------------------------------------------------===// // -// ScalarReplAggregates - Break up alloca's of aggregates into multiple allocas -// if possible. -// -FunctionPass *createScalarReplAggregatesPass(signed Threshold = -1, - bool UseDomTree = true, - signed StructMemberThreshold = -1, - signed ArrayElementThreshold = -1, - signed ScalarLoadThreshold = -1); - -//===----------------------------------------------------------------------===// -// // InductiveRangeCheckElimination - Transform loops to elide range checks on // linear functions of the induction variable. // @@ -132,7 +130,7 @@ Pass *createIndVarSimplifyPass(); // into: // %Z = add int 2, %X // -FunctionPass *createInstructionCombiningPass(); +FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines = true); //===----------------------------------------------------------------------===// // @@ -156,16 +154,6 @@ Pass *createLoopStrengthReducePass(); //===----------------------------------------------------------------------===// // -// GlobalMerge - This pass merges internal (by default) globals into structs -// to enable reuse of a base pointer by indexed addressing modes. -// It can also be configured to focus on size optimizations only. -// -Pass *createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset, - bool OnlyOptimizeForSize = false, - bool MergeExternalByDefault = false); - -//===----------------------------------------------------------------------===// -// // LoopUnswitch - This pass is a simple loop unswitching pass. // Pass *createLoopUnswitchPass(bool OptimizeForSize = false); @@ -205,6 +193,12 @@ Pass *createLoopIdiomPass(); //===----------------------------------------------------------------------===// // +// LoopVersioningLICM - This pass is a loop versioning pass for LICM. +// +Pass *createLoopVersioningLICMPass(); + +//===----------------------------------------------------------------------===// +// // PromoteMemoryToRegister - This pass is used to promote memory references to // be register references. A simple example of the transformation performed by // this pass is: @@ -262,7 +256,10 @@ FunctionPass *createFlattenCFGPass(); // // CFG Structurization - Remove irreducible control flow // -Pass *createStructurizeCFGPass(); +/// +/// When \p SkipUniformRegions is true the structizer will not structurize +/// regions that only contain uniform branches. +Pass *createStructurizeCFGPass(bool SkipUniformRegions = false); //===----------------------------------------------------------------------===// // @@ -329,17 +326,17 @@ FunctionPass *createEarlyCSEPass(); //===----------------------------------------------------------------------===// // -// MergedLoadStoreMotion - This pass merges loads and stores in diamonds. Loads -// are hoisted into the header, while stores sink into the footer. +// GVNHoist - This pass performs a simple and fast GVN pass over the dominator +// tree to hoist common expressions from sibling branches. // -FunctionPass *createMergedLoadStoreMotionPass(); +FunctionPass *createGVNHoistPass(); //===----------------------------------------------------------------------===// // -// GVN - This pass performs global value numbering and redundant load -// elimination cotemporaneously. +// MergedLoadStoreMotion - This pass merges loads and stores in diamonds. Loads +// are hoisted into the header, while stores sink into the footer. // -FunctionPass *createGVNPass(bool NoLoads = false); +FunctionPass *createMergedLoadStoreMotionPass(); //===----------------------------------------------------------------------===// // @@ -382,6 +379,12 @@ Pass *createLowerAtomicPass(); //===----------------------------------------------------------------------===// // +// LowerGuardIntrinsic - Lower guard intrinsics to normal control flow. +// +Pass *createLowerGuardIntrinsicPass(); + +//===----------------------------------------------------------------------===// +// // ValuePropagation - Propagate CFG-derived value information // Pass *createCorrelatedValuePropagationPass(); @@ -432,6 +435,10 @@ createSeparateConstOffsetFromGEPPass(const TargetMachine *TM = nullptr, // FunctionPass *createSpeculativeExecutionPass(); +// Same as createSpeculativeExecutionPass, but does nothing unless +// TargetTransformInfo::hasBranchDivergence() is true. +FunctionPass *createSpeculativeExecutionIfHasBranchDivergencePass(); + //===----------------------------------------------------------------------===// // // LoadCombine - Combine loads into bigger loads. @@ -478,7 +485,10 @@ FunctionPass *createNaryReassociatePass(); // // LoopDistribute - Distribute loops. // -FunctionPass *createLoopDistributePass(); +// ProcessAllLoopsByDefault instructs the pass to look for distribution +// opportunities in all loops unless -enable-loop-distribute or the +// llvm.loop.distribute.enable metadata data override this default. +FunctionPass *createLoopDistributePass(bool ProcessAllLoopsByDefault); //===----------------------------------------------------------------------===// // @@ -486,6 +496,28 @@ FunctionPass *createLoopDistributePass(); // FunctionPass *createLoopLoadEliminationPass(); +//===----------------------------------------------------------------------===// +// +// LoopSimplifyCFG - This pass performs basic CFG simplification on loops, +// primarily to help other loop passes. +// +Pass *createLoopSimplifyCFGPass(); + +//===----------------------------------------------------------------------===// +// +// LoopVersioning - Perform loop multi-versioning. +// +FunctionPass *createLoopVersioningPass(); + +//===----------------------------------------------------------------------===// +// +// LoopDataPrefetch - Perform data prefetching in loops. +// +FunctionPass *createLoopDataPrefetchPass(); + +///===---------------------------------------------------------------------===// +ModulePass *createNameAnonFunctionPass(); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Scalar/ADCE.h b/include/llvm/Transforms/Scalar/ADCE.h index f9bc7b77c14a..b9b7e1c0c99f 100644 --- a/include/llvm/Transforms/Scalar/ADCE.h +++ b/include/llvm/Transforms/Scalar/ADCE.h @@ -28,10 +28,8 @@ namespace llvm { /// instructions are dead until proven otherwise. This allows it to eliminate /// dead computations that other DCE passes do not catch, particularly involving /// loop computations. -class ADCEPass { -public: - static StringRef name() { return "ADCEPass"; } - PreservedAnalyses run(Function &F); +struct ADCEPass : PassInfoMixin<ADCEPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &); }; } diff --git a/include/llvm/Transforms/Scalar/AlignmentFromAssumptions.h b/include/llvm/Transforms/Scalar/AlignmentFromAssumptions.h new file mode 100644 index 000000000000..f75dc4dc331d --- /dev/null +++ b/include/llvm/Transforms/Scalar/AlignmentFromAssumptions.h @@ -0,0 +1,51 @@ +//===---- AlignmentFromAssumptions.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 implements a ScalarEvolution-based transformation to set +// the alignments of load, stores and memory intrinsics based on the truth +// expressions of assume intrinsics. The primary motivation is to handle +// complex alignment assumptions that apply to vector loads and stores that +// appear after vectorization and unrolling. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_ALIGNMENTFROMASSUMPTIONS_H +#define LLVM_TRANSFORMS_SCALAR_ALIGNMENTFROMASSUMPTIONS_H + +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +struct AlignmentFromAssumptionsPass + : public PassInfoMixin<AlignmentFromAssumptionsPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + // Glue for old PM. + bool runImpl(Function &F, AssumptionCache &AC, ScalarEvolution *SE_, + DominatorTree *DT_); + + // For memory transfers, we need a common alignment for both the source and + // destination. If we have a new alignment for only one operand of a transfer + // instruction, save it in these maps. If we reach the other operand through + // another assumption later, then we may change the alignment at that point. + DenseMap<MemTransferInst *, unsigned> NewDestAlignments, NewSrcAlignments; + + ScalarEvolution *SE = nullptr; + DominatorTree *DT = nullptr; + + bool extractAlignmentInfo(CallInst *I, Value *&AAPtr, const SCEV *&AlignSCEV, + const SCEV *&OffSCEV); + bool processAssumption(CallInst *I); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_ALIGNMENTFROMASSUMPTIONS_H diff --git a/include/llvm/Transforms/Scalar/BDCE.h b/include/llvm/Transforms/Scalar/BDCE.h new file mode 100644 index 000000000000..d7d2730a8033 --- /dev/null +++ b/include/llvm/Transforms/Scalar/BDCE.h @@ -0,0 +1,31 @@ +//===---- BDCE.cpp - Bit-tracking dead code elimination ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the Bit-Tracking Dead Code Elimination pass. Some +// instructions (shifts, some ands, ors, etc.) kill some of their input bits. +// We track these dead bits and remove instructions that compute only these +// dead bits. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_BDCE_H +#define LLVM_TRANSFORMS_SCALAR_BDCE_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +// The Bit-Tracking Dead Code Elimination pass. +struct BDCEPass : PassInfoMixin<BDCEPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_BDCE_H diff --git a/include/llvm/Transforms/Scalar/ConstantHoisting.h b/include/llvm/Transforms/Scalar/ConstantHoisting.h new file mode 100644 index 000000000000..3e2b3327a9fe --- /dev/null +++ b/include/llvm/Transforms/Scalar/ConstantHoisting.h @@ -0,0 +1,149 @@ +//===-- ConstantHoisting.h - Prepare code for expensive constants ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass identifies expensive constants to hoist and coalesces them to +// better prepare it for SelectionDAG-based code generation. This works around +// the limitations of the basic-block-at-a-time approach. +// +// First it scans all instructions for integer constants and calculates its +// cost. If the constant can be folded into the instruction (the cost is +// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't +// consider it expensive and leave it alone. This is the default behavior and +// the default implementation of getIntImmCost will always return TCC_Free. +// +// If the cost is more than TCC_BASIC, then the integer constant can't be folded +// into the instruction and it might be beneficial to hoist the constant. +// Similar constants are coalesced to reduce register pressure and +// materialization code. +// +// When a constant is hoisted, it is also hidden behind a bitcast to force it to +// be live-out of the basic block. Otherwise the constant would be just +// duplicated and each basic block would have its own copy in the SelectionDAG. +// The SelectionDAG recognizes such constants as opaque and doesn't perform +// certain transformations on them, which would create a new expensive constant. +// +// This optimization is only applied to integer constants in instructions and +// simple (this means not nested) constant cast expressions. For example: +// %0 = load i64* inttoptr (i64 big_constant to i64*) +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H +#define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H + +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by +/// ConstantHoisting. These are implementation details and should not be used by +/// clients. +namespace consthoist { +/// \brief Keeps track of the user of a constant and the operand index where the +/// constant is used. +struct ConstantUser { + Instruction *Inst; + unsigned OpndIdx; + + ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { } +}; + +typedef SmallVector<ConstantUser, 8> ConstantUseListType; + +/// \brief Keeps track of a constant candidate and its uses. +struct ConstantCandidate { + ConstantUseListType Uses; + ConstantInt *ConstInt; + unsigned CumulativeCost; + + ConstantCandidate(ConstantInt *ConstInt) + : ConstInt(ConstInt), CumulativeCost(0) { } + + /// \brief Add the user to the use list and update the cost. + void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { + CumulativeCost += Cost; + Uses.push_back(ConstantUser(Inst, Idx)); + } +}; + +/// \brief This represents a constant that has been rebased with respect to a +/// base constant. The difference to the base constant is recorded in Offset. +struct RebasedConstantInfo { + ConstantUseListType Uses; + Constant *Offset; + + RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset) + : Uses(std::move(Uses)), Offset(Offset) { } +}; + +typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType; + +/// \brief A base constant and all its rebased constants. +struct ConstantInfo { + ConstantInt *BaseConstant; + RebasedConstantListType RebasedConstants; +}; +} + +class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + // Glue for old PM. + bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, + BasicBlock &Entry); + + void releaseMemory() { + ConstantVec.clear(); + ClonedCastMap.clear(); + ConstCandVec.clear(); + } + +private: + typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType; + typedef std::vector<consthoist::ConstantCandidate> ConstCandVecType; + + const TargetTransformInfo *TTI; + DominatorTree *DT; + BasicBlock *Entry; + + /// Keeps track of constant candidates found in the function. + ConstCandVecType ConstCandVec; + + /// Keep track of cast instructions we already cloned. + SmallDenseMap<Instruction *, Instruction *> ClonedCastMap; + + /// These are the final constants we decided to hoist. + SmallVector<consthoist::ConstantInfo, 8> ConstantVec; + + Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; + Instruction *findConstantInsertionPoint( + const consthoist::ConstantInfo &ConstInfo) const; + void collectConstantCandidates(ConstCandMapType &ConstCandMap, + Instruction *Inst, unsigned Idx, + ConstantInt *ConstInt); + void collectConstantCandidates(ConstCandMapType &ConstCandMap, + Instruction *Inst); + void collectConstantCandidates(Function &Fn); + void findAndMakeBaseConstant(ConstCandVecType::iterator S, + ConstCandVecType::iterator E); + unsigned maximizeConstantsInRange(ConstCandVecType::iterator S, + ConstCandVecType::iterator E, + ConstCandVecType::iterator &MaxCostItr); + void findBaseConstants(); + void emitBaseConstants(Instruction *Base, Constant *Offset, + const consthoist::ConstantUser &ConstUser); + bool emitBaseConstants(); + void deleteDeadCastInst() const; + bool optimizeConstants(Function &Fn); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H diff --git a/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h b/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h new file mode 100644 index 000000000000..38816bbed068 --- /dev/null +++ b/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h @@ -0,0 +1,24 @@ +//===---- CorrelatedValuePropagation.h --------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H +#define LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +struct CorrelatedValuePropagationPass + : PassInfoMixin<CorrelatedValuePropagationPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H diff --git a/include/llvm/Transforms/Scalar/DCE.h b/include/llvm/Transforms/Scalar/DCE.h new file mode 100644 index 000000000000..d9f921e1e7c1 --- /dev/null +++ b/include/llvm/Transforms/Scalar/DCE.h @@ -0,0 +1,29 @@ +//===- DCE.h - Dead code elimination ----------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Dead Code Elimination pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_DCE_H +#define LLVM_TRANSFORMS_SCALAR_DCE_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Basic Dead Code Elimination pass. +class DCEPass : public PassInfoMixin<DCEPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_DCE_H diff --git a/include/llvm/Transforms/Scalar/DeadStoreElimination.h b/include/llvm/Transforms/Scalar/DeadStoreElimination.h new file mode 100644 index 000000000000..7826e29f178e --- /dev/null +++ b/include/llvm/Transforms/Scalar/DeadStoreElimination.h @@ -0,0 +1,34 @@ +//===- DeadStoreElimination.h - Fast Dead Store Elimination -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a trivial dead store elimination that only considers +// basic-block local redundant stores. +// +// FIXME: This should eventually be extended to be a post-dominator tree +// traversal. Doing so would be pretty trivial. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_DSE_H +#define LLVM_TRANSFORMS_SCALAR_DSE_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// This class implements a trivial dead store elimination. We consider +/// only the redundant stores that are local to a single Basic Block. +class DSEPass : public PassInfoMixin<DSEPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &FAM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_DSE_H diff --git a/include/llvm/Transforms/Scalar/EarlyCSE.h b/include/llvm/Transforms/Scalar/EarlyCSE.h index e3dd3c050df6..80e3c602a2b8 100644 --- a/include/llvm/Transforms/Scalar/EarlyCSE.h +++ b/include/llvm/Transforms/Scalar/EarlyCSE.h @@ -26,12 +26,9 @@ namespace llvm { /// canonicalize things as it goes. It is intended to be fast and catch obvious /// cases so that instcombine and other passes are more effective. It is /// expected that a later pass of GVN will catch the interesting/hard cases. -class EarlyCSEPass { -public: - static StringRef name() { return "EarlyCSEPass"; } - +struct EarlyCSEPass : PassInfoMixin<EarlyCSEPass> { /// \brief Run the pass over the function. - PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); }; } diff --git a/include/llvm/Transforms/Scalar/Float2Int.h b/include/llvm/Transforms/Scalar/Float2Int.h new file mode 100644 index 000000000000..a8042399fb08 --- /dev/null +++ b/include/llvm/Transforms/Scalar/Float2Int.h @@ -0,0 +1,51 @@ +//===-- Float2Int.h - Demote floating point ops to work on integers -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the Float2Int pass, which aims to demote floating +// point operations to work on integers, where that is losslessly possible. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_FLOAT2INT_H +#define LLVM_TRANSFORMS_SCALAR_FLOAT2INT_H + +#include "llvm/ADT/EquivalenceClasses.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class Float2IntPass : public PassInfoMixin<Float2IntPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + // Glue for old PM. + bool runImpl(Function &F); + +private: + void findRoots(Function &F, SmallPtrSet<Instruction *, 8> &Roots); + ConstantRange seen(Instruction *I, ConstantRange R); + ConstantRange badRange(); + ConstantRange unknownRange(); + ConstantRange validateRange(ConstantRange R); + void walkBackwards(const SmallPtrSetImpl<Instruction *> &Roots); + void walkForwards(); + bool validateAndTransform(); + Value *convert(Instruction *I, Type *ToTy); + void cleanup(); + + MapVector<Instruction *, ConstantRange> SeenInsts; + SmallPtrSet<Instruction *, 8> Roots; + EquivalenceClasses<Instruction *> ECs; + MapVector<Instruction *, Value *> ConvertedInsts; + LLVMContext *Ctx; +}; +} +#endif // LLVM_TRANSFORMS_SCALAR_FLOAT2INT_H diff --git a/include/llvm/Transforms/Scalar/GVN.h b/include/llvm/Transforms/Scalar/GVN.h new file mode 100644 index 000000000000..3bb5ec392272 --- /dev/null +++ b/include/llvm/Transforms/Scalar/GVN.h @@ -0,0 +1,240 @@ +//===- GVN.h - Eliminate redundant values and loads -------------*- 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 the interface for LLVM's Global Value Numbering pass +/// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc +/// PRE and dead load elimination. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H +#define LLVM_TRANSFORMS_SCALAR_GVN_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by GVN. These +/// are implementation details and should not be used by clients. +namespace gvn LLVM_LIBRARY_VISIBILITY { +struct AvailableValue; +struct AvailableValueInBlock; +class GVNLegacyPass; +} + +/// The core GVN pass object. +/// +/// FIXME: We should have a good summary of the GVN algorithm implemented by +/// this particular pass here. +class GVN : public PassInfoMixin<GVN> { +public: + + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); + + /// This removes the specified instruction from + /// our various maps and marks it for deletion. + void markInstructionForDeletion(Instruction *I) { + VN.erase(I); + InstrsToErase.push_back(I); + } + + DominatorTree &getDominatorTree() const { return *DT; } + AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } + MemoryDependenceResults &getMemDep() const { return *MD; } + + struct Expression; + + /// This class holds the mapping between values and value numbers. It is used + /// as an efficient mechanism to determine the expression-wise equivalence of + /// two values. + class ValueTable { + DenseMap<Value *, uint32_t> valueNumbering; + DenseMap<Expression, uint32_t> expressionNumbering; + AliasAnalysis *AA; + MemoryDependenceResults *MD; + DominatorTree *DT; + + uint32_t nextValueNumber; + + Expression createExpr(Instruction *I); + Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, + Value *LHS, Value *RHS); + Expression createExtractvalueExpr(ExtractValueInst *EI); + uint32_t lookupOrAddCall(CallInst *C); + + public: + ValueTable(); + ValueTable(const ValueTable &Arg); + ValueTable(ValueTable &&Arg); + ~ValueTable(); + + uint32_t lookupOrAdd(Value *V); + uint32_t lookup(Value *V) const; + uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, + Value *LHS, Value *RHS); + bool exists(Value *V) const; + void add(Value *V, uint32_t num); + void clear(); + void erase(Value *v); + void setAliasAnalysis(AliasAnalysis *A) { AA = A; } + AliasAnalysis *getAliasAnalysis() const { return AA; } + void setMemDep(MemoryDependenceResults *M) { MD = M; } + void setDomTree(DominatorTree *D) { DT = D; } + uint32_t getNextUnusedValueNumber() { return nextValueNumber; } + void verifyRemoved(const Value *) const; + }; + +private: + friend class gvn::GVNLegacyPass; + friend struct DenseMapInfo<Expression>; + + MemoryDependenceResults *MD; + DominatorTree *DT; + const TargetLibraryInfo *TLI; + AssumptionCache *AC; + SetVector<BasicBlock *> DeadBlocks; + + ValueTable VN; + + /// A mapping from value numbers to lists of Value*'s that + /// have that value number. Use findLeader to query it. + struct LeaderTableEntry { + Value *Val; + const BasicBlock *BB; + LeaderTableEntry *Next; + }; + DenseMap<uint32_t, LeaderTableEntry> LeaderTable; + BumpPtrAllocator TableAllocator; + + // Block-local map of equivalent values to their leader, does not + // propagate to any successors. Entries added mid-block are applied + // to the remaining instructions in the block. + SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap; + SmallVector<Instruction *, 8> InstrsToErase; + + typedef SmallVector<NonLocalDepResult, 64> LoadDepVect; + typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect; + typedef SmallVector<BasicBlock *, 64> UnavailBlkVect; + + bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, + const TargetLibraryInfo &RunTLI, AAResults &RunAA, + MemoryDependenceResults *RunMD); + + /// Push a new Value to the LeaderTable onto the list for its value number. + void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { + LeaderTableEntry &Curr = LeaderTable[N]; + if (!Curr.Val) { + Curr.Val = V; + Curr.BB = BB; + return; + } + + LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>(); + Node->Val = V; + Node->BB = BB; + Node->Next = Curr.Next; + Curr.Next = Node; + } + + /// Scan the list of values corresponding to a given + /// value number, and remove the given instruction if encountered. + void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { + LeaderTableEntry *Prev = nullptr; + LeaderTableEntry *Curr = &LeaderTable[N]; + + while (Curr && (Curr->Val != I || Curr->BB != BB)) { + Prev = Curr; + Curr = Curr->Next; + } + + if (!Curr) + return; + + if (Prev) { + Prev->Next = Curr->Next; + } else { + if (!Curr->Next) { + Curr->Val = nullptr; + Curr->BB = nullptr; + } else { + LeaderTableEntry *Next = Curr->Next; + Curr->Val = Next->Val; + Curr->BB = Next->BB; + Curr->Next = Next->Next; + } + } + } + + // List of critical edges to be split between iterations. + SmallVector<std::pair<TerminatorInst *, unsigned>, 4> toSplit; + + // Helper functions of redundant load elimination + bool processLoad(LoadInst *L); + bool processNonLocalLoad(LoadInst *L); + bool processAssumeIntrinsic(IntrinsicInst *II); + /// Given a local dependency (Def or Clobber) determine if a value is + /// available for the load. Returns true if an value is known to be + /// available and populates Res. Returns false otherwise. + bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, + Value *Address, gvn::AvailableValue &Res); + /// Given a list of non-local dependencies, determine if a value is + /// available for the load in each specified block. If it is, add it to + /// ValuesPerBlock. If not, add it to UnavailableBlocks. + void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, + AvailValInBlkVect &ValuesPerBlock, + UnavailBlkVect &UnavailableBlocks); + bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, + UnavailBlkVect &UnavailableBlocks); + + // Other helper routines + bool processInstruction(Instruction *I); + bool processBlock(BasicBlock *BB); + void dump(DenseMap<uint32_t, Value *> &d); + bool iterateOnFunction(Function &F); + bool performPRE(Function &F); + bool performScalarPRE(Instruction *I); + bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, + unsigned int ValNo); + Value *findLeader(const BasicBlock *BB, uint32_t num); + void cleanupGlobalSets(); + void verifyRemoved(const Instruction *I) const; + bool splitCriticalEdges(); + BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); + bool replaceOperandsWithConsts(Instruction *I) const; + bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, + bool DominatesByEdge); + bool processFoldableCondBr(BranchInst *BI); + void addDeadBlock(BasicBlock *BB); + void assignValNumForDeadCode(); +}; + +/// Create a legacy GVN pass. This also allows parameterizing whether or not +/// loads are eliminated by the pass. +FunctionPass *createGVNPass(bool NoLoads = false); + +/// \brief A simple and fast domtree-based GVN pass to hoist common expressions +/// from sibling branches. +struct GVNHoistPass : PassInfoMixin<GVNHoistPass> { + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +} + +#endif diff --git a/include/llvm/Transforms/Scalar/GuardWidening.h b/include/llvm/Transforms/Scalar/GuardWidening.h new file mode 100644 index 000000000000..201065cbdfb5 --- /dev/null +++ b/include/llvm/Transforms/Scalar/GuardWidening.h @@ -0,0 +1,32 @@ +//===- GuardWidening.h - ----------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Guard widening is an optimization over the @llvm.experimental.guard intrinsic +// that (optimistically) combines multiple guards into one to have fewer checks +// at runtime. +// +//===----------------------------------------------------------------------===// + + +#ifndef LLVM_TRANSFORMS_SCALAR_GUARD_WIDENING_H +#define LLVM_TRANSFORMS_SCALAR_GUARD_WIDENING_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Function; + +struct GuardWideningPass : public PassInfoMixin<GuardWideningPass> { + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + + +#endif // LLVM_TRANSFORMS_SCALAR_GUARD_WIDENING_H diff --git a/include/llvm/Transforms/Scalar/IndVarSimplify.h b/include/llvm/Transforms/Scalar/IndVarSimplify.h new file mode 100644 index 000000000000..325bcc7bed8f --- /dev/null +++ b/include/llvm/Transforms/Scalar/IndVarSimplify.h @@ -0,0 +1,29 @@ +//===- IndVarSimplify.h - Induction Variable Simplification -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Induction Variable +// Simplification pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H +#define LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class IndVarSimplifyPass : public PassInfoMixin<IndVarSimplifyPass> { +public: + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H diff --git a/include/llvm/Transforms/Scalar/JumpThreading.h b/include/llvm/Transforms/Scalar/JumpThreading.h new file mode 100644 index 000000000000..e38bdd03ac06 --- /dev/null +++ b/include/llvm/Transforms/Scalar/JumpThreading.h @@ -0,0 +1,141 @@ +//===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// See the comments on JumpThreadingPass. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H +#define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H + +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/BlockFrequencyInfoImpl.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/LazyValueInfo.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/ValueHandle.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by +/// JumpThreading. +/// These are implementation details and should not be used by clients. +namespace jumpthreading { +// These are at global scope so static functions can use them too. +typedef SmallVectorImpl<std::pair<Constant *, BasicBlock *>> PredValueInfo; +typedef SmallVector<std::pair<Constant *, BasicBlock *>, 8> PredValueInfoTy; + +// This is used to keep track of what kind of constant we're currently hoping +// to find. +enum ConstantPreference { WantInteger, WantBlockAddress }; +} + +/// This pass performs 'jump threading', which looks at blocks that have +/// multiple predecessors and multiple successors. If one or more of the +/// predecessors of the block can be proven to always jump to one of the +/// successors, we forward the edge from the predecessor to the successor by +/// duplicating the contents of this block. +/// +/// An example of when this can occur is code like this: +/// +/// if () { ... +/// X = 4; +/// } +/// if (X < 3) { +/// +/// In this case, the unconditional branch at the end of the first if can be +/// revectored to the false side of the second if. +/// +class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { + TargetLibraryInfo *TLI; + LazyValueInfo *LVI; + std::unique_ptr<BlockFrequencyInfo> BFI; + std::unique_ptr<BranchProbabilityInfo> BPI; + bool HasProfileData = false; +#ifdef NDEBUG + SmallPtrSet<const BasicBlock *, 16> LoopHeaders; +#else + SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders; +#endif + DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet; + + unsigned BBDupThreshold; + + // RAII helper for updating the recursion stack. + struct RecursionSetRemover { + DenseSet<std::pair<Value *, BasicBlock *>> &TheSet; + std::pair<Value *, BasicBlock *> ThePair; + + RecursionSetRemover(DenseSet<std::pair<Value *, BasicBlock *>> &S, + std::pair<Value *, BasicBlock *> P) + : TheSet(S), ThePair(P) {} + + ~RecursionSetRemover() { TheSet.erase(ThePair); } + }; + +public: + JumpThreadingPass(int T = -1); + // Hack for MSVC 2013 which seems like it can't synthesize this. + JumpThreadingPass(JumpThreadingPass &&Other) + : TLI(Other.TLI), LVI(Other.LVI), BFI(std::move(Other.BFI)), + BPI(std::move(Other.BPI)), HasProfileData(Other.HasProfileData), + LoopHeaders(std::move(Other.LoopHeaders)), + RecursionSet(std::move(Other.RecursionSet)), + BBDupThreshold(Other.BBDupThreshold) {} + + // Glue for old PM. + bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, + bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, + std::unique_ptr<BranchProbabilityInfo> BPI_); + + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); + + void releaseMemory() { + BFI.reset(); + BPI.reset(); + } + + void FindLoopHeaders(Function &F); + bool ProcessBlock(BasicBlock *BB); + bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, + BasicBlock *SuccBB); + bool DuplicateCondBranchOnPHIIntoPred( + BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); + + bool + ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, + jumpthreading::PredValueInfo &Result, + jumpthreading::ConstantPreference Preference, + Instruction *CxtI = nullptr); + bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, + jumpthreading::ConstantPreference Preference, + Instruction *CxtI = nullptr); + + bool ProcessBranchOnPHI(PHINode *PN); + bool ProcessBranchOnXOR(BinaryOperator *BO); + bool ProcessImpliedCondition(BasicBlock *BB); + + bool SimplifyPartiallyRedundantLoad(LoadInst *LI); + bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); + bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); + +private: + BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, + const char *Suffix); + void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB, + BasicBlock *NewBB, BasicBlock *SuccBB); +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/Transforms/Scalar/LICM.h b/include/llvm/Transforms/Scalar/LICM.h new file mode 100644 index 000000000000..a050a43d6179 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LICM.h @@ -0,0 +1,48 @@ +//===- LICM.h - Loop Invariant Code Motion Pass -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs loop invariant code motion, attempting to remove as much +// code from the body of a loop as possible. It does this by either hoisting +// code into the preheader block, or by sinking code to the exit blocks if it is +// safe. This pass also promotes must-aliased memory locations in the loop to +// live in registers, thus hoisting and sinking "invariant" loads and stores. +// +// This pass uses alias analysis for two purposes: +// +// 1. Moving loop invariant loads and calls out of loops. If we can determine +// that a load or call inside of a loop never aliases anything stored to, +// we can hoist it or sink it like any other instruction. +// 2. Scalar Promotion of Memory - If there is a store instruction inside of +// the loop, we try to move the store to happen AFTER the loop instead of +// inside of the loop. This can only happen if a few conditions are true: +// A. The pointer stored through is loop invariant +// B. There are no stores or loads in the loop which _may_ alias the +// pointer. There are no calls in the loop which mod/ref the pointer. +// If these conditions are true, we can promote the loads and stores in the +// loop of the pointer to use a temporary alloca'd variable. We then use +// the SSAUpdater to construct the appropriate SSA form for the value. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LICM_H +#define LLVM_TRANSFORMS_SCALAR_LICM_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Performs Loop Invariant Code Motion Pass. +class LICMPass : public PassInfoMixin<LICMPass> { +public: + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LICM_H diff --git a/include/llvm/Transforms/Scalar/LoopDeletion.h b/include/llvm/Transforms/Scalar/LoopDeletion.h new file mode 100644 index 000000000000..ed5a9833e572 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopDeletion.h @@ -0,0 +1,38 @@ +//===- LoopDeletion.h - Loop Deletion -------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Loop Deletion Pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H +#define LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LoopDeletionPass : public PassInfoMixin<LoopDeletionPass> { +public: + LoopDeletionPass() {} + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); + bool runImpl(Loop *L, DominatorTree &DT, ScalarEvolution &SE, + LoopInfo &loopInfo); + +private: + bool isLoopDead(Loop *L, ScalarEvolution &SE, + SmallVectorImpl<BasicBlock *> &exitingBlocks, + SmallVectorImpl<BasicBlock *> &exitBlocks, bool &Changed, + BasicBlock *Preheader); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H diff --git a/include/llvm/Transforms/Scalar/LoopDistribute.h b/include/llvm/Transforms/Scalar/LoopDistribute.h new file mode 100644 index 000000000000..ddde5954c218 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopDistribute.h @@ -0,0 +1,30 @@ +//===- LoopDistribute.cpp - Loop Distribution Pass --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the Loop Distribution Pass. Its main focus is to +// distribute loops that cannot be vectorized due to dependence cycles. It +// tries to isolate the offending dependences into a new loop allowing +// vectorization of the remaining parts. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPDISTRIBUTE_H +#define LLVM_TRANSFORMS_SCALAR_LOOPDISTRIBUTE_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LoopDistributePass : public PassInfoMixin<LoopDistributePass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPDISTRIBUTE_H diff --git a/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h b/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h new file mode 100644 index 000000000000..cc66156fba8a --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h @@ -0,0 +1,31 @@ +//===- LoopIdiomRecognize.h - Loop Idiom Recognize Pass -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass implements an idiom recognizer that transforms simple loops into a +// non-loop form. In cases that this kicks in, it can be a significant +// performance win. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H +#define LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Performs Loop Idiom Recognize Pass. +class LoopIdiomRecognizePass : public PassInfoMixin<LoopIdiomRecognizePass> { +public: + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H diff --git a/include/llvm/Transforms/Scalar/LoopInstSimplify.h b/include/llvm/Transforms/Scalar/LoopInstSimplify.h new file mode 100644 index 000000000000..f67343f40a7c --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopInstSimplify.h @@ -0,0 +1,29 @@ +//===- LoopInstSimplify.h - Loop Inst Simplify Pass -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs lightweight instruction simplification on loop bodies. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H +#define LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Performs Loop Inst Simplify Pass. +class LoopInstSimplifyPass : public PassInfoMixin<LoopInstSimplifyPass> { +public: + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H diff --git a/include/llvm/Transforms/Scalar/LoopRotation.h b/include/llvm/Transforms/Scalar/LoopRotation.h new file mode 100644 index 000000000000..b21c7313dc4b --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopRotation.h @@ -0,0 +1,30 @@ +//===- LoopRotation.h - Loop Rotation -------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Loop Rotation pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPROTATION_H +#define LLVM_TRANSFORMS_SCALAR_LOOPROTATION_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A simple loop rotation transformation. +class LoopRotatePass : public PassInfoMixin<LoopRotatePass> { +public: + LoopRotatePass(); + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPROTATION_H diff --git a/include/llvm/Transforms/Scalar/LoopSimplifyCFG.h b/include/llvm/Transforms/Scalar/LoopSimplifyCFG.h new file mode 100644 index 000000000000..7609bb26a1a0 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopSimplifyCFG.h @@ -0,0 +1,32 @@ +//===- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the Loop SimplifyCFG Pass. This pass is responsible for +// basic loop CFG cleanup, primarily to assist other loop passes. If you +// encounter a noncanonical CFG construct that causes another loop pass to +// perform suboptimally, this is the place to fix it up. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPSIMPLIFYCFG_H +#define LLVM_TRANSFORMS_SCALAR_LOOPSIMPLIFYCFG_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Performs basic CFG simplifications to assist other loop passes. +class LoopSimplifyCFGPass : public PassInfoMixin<LoopSimplifyCFGPass> { +public: + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPSIMPLIFYCFG_H diff --git a/include/llvm/Transforms/Scalar/LowerAtomic.h b/include/llvm/Transforms/Scalar/LowerAtomic.h new file mode 100644 index 000000000000..a4a2e7aafe44 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LowerAtomic.h @@ -0,0 +1,29 @@ +//===- LowerAtomic.cpp - Lower atomic intrinsics ----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +// This pass lowers atomic intrinsics to non-atomic form for use in a known +// non-preemptible environment. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOWERATOMIC_H +#define LLVM_TRANSFORMS_SCALAR_LOWERATOMIC_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A pass that lowers atomic intrinsic into non-atomic intrinsics. +class LowerAtomicPass : public PassInfoMixin<LowerAtomicPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOWERATOMIC_H diff --git a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h index 40283203f3a3..f688e7f19986 100644 --- a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h +++ b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h @@ -21,10 +21,7 @@ namespace llvm { -class LowerExpectIntrinsicPass { -public: - static StringRef name() { return "LowerExpectIntrinsicPass"; } - +struct LowerExpectIntrinsicPass : PassInfoMixin<LowerExpectIntrinsicPass> { /// \brief Run the pass over the function. /// /// This will lower all of th expect intrinsic calls in this function into @@ -32,7 +29,7 @@ public: /// of the probabilities and frequencies of the CFG. After running this pass, /// no more expect intrinsics remain, allowing the rest of the optimizer to /// ignore them. - PreservedAnalyses run(Function &F); + PreservedAnalyses run(Function &F, FunctionAnalysisManager &); }; } diff --git a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h new file mode 100644 index 000000000000..4308e44e7c4b --- /dev/null +++ b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h @@ -0,0 +1,68 @@ +//===---- MemCpyOptimizer.h - memcpy optimization ---------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs various transformations related to eliminating memcpy +// calls, or transforming sets of stores into memset's. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H +#define LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H + +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> { + MemoryDependenceResults *MD = nullptr; + TargetLibraryInfo *TLI = nullptr; + std::function<AliasAnalysis &()> LookupAliasAnalysis; + std::function<AssumptionCache &()> LookupAssumptionCache; + std::function<DominatorTree &()> LookupDomTree; + +public: + MemCpyOptPass() {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + // Glue for the old PM. + bool runImpl(Function &F, MemoryDependenceResults *MD_, + TargetLibraryInfo *TLI_, + std::function<AliasAnalysis &()> LookupAliasAnalysis_, + std::function<AssumptionCache &()> LookupAssumptionCache_, + std::function<DominatorTree &()> LookupDomTree_); + +private: + // Helper functions + bool processStore(StoreInst *SI, BasicBlock::iterator &BBI); + bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI); + bool processMemCpy(MemCpyInst *M); + bool processMemMove(MemMoveInst *M); + bool performCallSlotOptzn(Instruction *cpy, Value *cpyDst, Value *cpySrc, + uint64_t cpyLen, unsigned cpyAlign, CallInst *C); + bool processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep); + bool processMemSetMemCpyDependence(MemCpyInst *M, MemSetInst *MDep); + bool performMemCpyToMemSetOptzn(MemCpyInst *M, MemSetInst *MDep); + bool processByValArgument(CallSite CS, unsigned ArgNo); + Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr, + Value *ByteVal); + + bool iterateOnFunction(Function &F); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H diff --git a/include/llvm/Transforms/Scalar/MergedLoadStoreMotion.h b/include/llvm/Transforms/Scalar/MergedLoadStoreMotion.h new file mode 100644 index 000000000000..47cfea489243 --- /dev/null +++ b/include/llvm/Transforms/Scalar/MergedLoadStoreMotion.h @@ -0,0 +1,39 @@ +//===- MergedLoadStoreMotion.h - merge and hoist/sink load/stores ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +//! \file +//! \brief This pass performs merges of loads and stores on both sides of a +// diamond (hammock). It hoists the loads and sinks the stores. +// +// The algorithm iteratively hoists two loads to the same address out of a +// diamond (hammock) and merges them into a single load in the header. Similar +// it sinks and merges two stores to the tail block (footer). The algorithm +// iterates over the instructions of one side of the diamond and attempts to +// find a matching load/store on the other side. It hoists / sinks when it +// thinks it safe to do so. This optimization helps with eg. hiding load +// latencies, triggering if-conversion, and reducing static code size. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_MERGEDLOADSTOREMOTION_H +#define LLVM_TRANSFORMS_SCALAR_MERGEDLOADSTOREMOTION_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class MergedLoadStoreMotionPass + : public PassInfoMixin<MergedLoadStoreMotionPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +} + +#endif // LLVM_TRANSFORMS_SCALAR_MERGEDLOADSTOREMOTION_H diff --git a/include/llvm/Transforms/Scalar/PartiallyInlineLibCalls.h b/include/llvm/Transforms/Scalar/PartiallyInlineLibCalls.h new file mode 100644 index 000000000000..385bbb40db3f --- /dev/null +++ b/include/llvm/Transforms/Scalar/PartiallyInlineLibCalls.h @@ -0,0 +1,30 @@ +//===--- PartiallyInlineLibCalls.h - Partially inline libcalls --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass tries to partially inline the fast path of well-known library +// functions, such as using square-root instructions for cases where sqrt() +// does not need to set errno. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_PARTIALLYINLINELIBCALLS_H +#define LLVM_TRANSFORMS_SCALAR_PARTIALLYINLINELIBCALLS_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class PartiallyInlineLibCallsPass + : public PassInfoMixin<PartiallyInlineLibCallsPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_PARTIALLYINLINELIBCALLS_H diff --git a/include/llvm/Transforms/Scalar/Reassociate.h b/include/llvm/Transforms/Scalar/Reassociate.h new file mode 100644 index 000000000000..7b68b4489306 --- /dev/null +++ b/include/llvm/Transforms/Scalar/Reassociate.h @@ -0,0 +1,100 @@ +//===- Reassociate.h - Reassociate binary expressions -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass reassociates commutative expressions in an order that is designed +// to promote better constant propagation, GCSE, LICM, PRE, etc. +// +// For example: 4 + (x + 5) -> x + (4 + 5) +// +// In the implementation of this algorithm, constants are assigned rank = 0, +// function arguments are rank = 1, and other values are assigned ranks +// corresponding to the reverse post order traversal of current function +// (starting at 2), which effectively gives values in deep loops higher rank +// than values not in loops. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H +#define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H + +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by Reassociate. +/// These are implementation details and should not be used by clients. +namespace reassociate { +struct ValueEntry { + unsigned Rank; + Value *Op; + ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} +}; +inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { + return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. +} + +/// \brief Utility class representing a base and exponent pair which form one +/// factor of some product. +struct Factor { + Value *Base; + unsigned Power; + Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {} +}; + +class XorOpnd; +} + +/// Reassociate commutative expressions. +class ReassociatePass : public PassInfoMixin<ReassociatePass> { + DenseMap<BasicBlock *, unsigned> RankMap; + DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; + SetVector<AssertingVH<Instruction>> RedoInsts; + bool MadeChange; + +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &); + +private: + void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT); + unsigned getRank(Value *V); + void canonicalizeOperands(Instruction *I); + void ReassociateExpression(BinaryOperator *I); + void RewriteExprTree(BinaryOperator *I, + SmallVectorImpl<reassociate::ValueEntry> &Ops); + Value *OptimizeExpression(BinaryOperator *I, + SmallVectorImpl<reassociate::ValueEntry> &Ops); + Value *OptimizeAdd(Instruction *I, + SmallVectorImpl<reassociate::ValueEntry> &Ops); + Value *OptimizeXor(Instruction *I, + SmallVectorImpl<reassociate::ValueEntry> &Ops); + bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1, + APInt &ConstOpnd, Value *&Res); + bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1, + reassociate::XorOpnd *Opnd2, APInt &ConstOpnd, + Value *&Res); + bool collectMultiplyFactors(SmallVectorImpl<reassociate::ValueEntry> &Ops, + SmallVectorImpl<reassociate::Factor> &Factors); + Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder, + SmallVectorImpl<reassociate::Factor> &Factors); + Value *OptimizeMul(BinaryOperator *I, + SmallVectorImpl<reassociate::ValueEntry> &Ops); + Value *RemoveFactorFromExpression(Value *V, Value *Factor); + void EraseInst(Instruction *I); + void RecursivelyEraseDeadInsts(Instruction *I, + SetVector<AssertingVH<Instruction>> &Insts); + void OptimizeInst(Instruction *I); + Instruction *canonicalizeNegConstExpr(Instruction *I); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H diff --git a/include/llvm/Transforms/Scalar/SCCP.h b/include/llvm/Transforms/Scalar/SCCP.h new file mode 100644 index 000000000000..0dd90ecbedec --- /dev/null +++ b/include/llvm/Transforms/Scalar/SCCP.h @@ -0,0 +1,36 @@ +//===- SCCP.cpp - Sparse Conditional Constant Propagation -------*- 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 implements sparse conditional constant propagation and merging: +// +// Specifically, this: +// * Assumes values are constant unless proven otherwise +// * Assumes BasicBlocks are dead unless proven otherwise +// * Proves values to be constant, and replaces them with constants +// * Proves conditional branches to be unconditional +// +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_SCCP_H +#define LLVM_TRANSFORMS_SCALAR_SCCP_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// This pass performs function-level constant propagation and merging. +class SCCPPass : public PassInfoMixin<SCCPPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_SCCP_H diff --git a/include/llvm/Transforms/Scalar/SROA.h b/include/llvm/Transforms/Scalar/SROA.h index f90cc7b686ba..72e7d63d4df6 100644 --- a/include/llvm/Transforms/Scalar/SROA.h +++ b/include/llvm/Transforms/Scalar/SROA.h @@ -26,7 +26,7 @@ namespace llvm { /// A private "module" namespace for types and utilities used by SROA. These /// are implementation details and should not be used by clients. -namespace sroa { +namespace sroa LLVM_LIBRARY_VISIBILITY { class AllocaSliceRewriter; class AllocaSlices; class Partition; @@ -51,7 +51,7 @@ class SROALegacyPass; /// onto insert and extract operations on a vector value, and convert them to /// this form. By doing so, it will enable promotion of vector aggregates to /// SSA vector values. -class SROA { +class SROA : public PassInfoMixin<SROA> { LLVMContext *C; DominatorTree *DT; AssumptionCache *AC; @@ -101,10 +101,8 @@ class SROA { public: SROA() : C(nullptr), DT(nullptr), AC(nullptr) {} - static StringRef name() { return "SROA"; } - /// \brief Run the pass over the function. - PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); private: friend class sroa::AllocaSliceRewriter; diff --git a/include/llvm/Transforms/Scalar/SimplifyCFG.h b/include/llvm/Transforms/Scalar/SimplifyCFG.h index ef28e0f78a4c..53f427a7d19a 100644 --- a/include/llvm/Transforms/Scalar/SimplifyCFG.h +++ b/include/llvm/Transforms/Scalar/SimplifyCFG.h @@ -25,12 +25,10 @@ namespace llvm { /// This pass iteratively simplifies the entire CFG of a function, removing /// unnecessary control flows and bringing it into the canonical form expected /// by the rest of the mid-level optimizer. -class SimplifyCFGPass { +class SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> { int BonusInstThreshold; public: - static StringRef name() { return "SimplifyCFGPass"; } - /// \brief Construct a pass with the default thresholds. SimplifyCFGPass(); @@ -38,7 +36,7 @@ public: SimplifyCFGPass(int BonusInstThreshold); /// \brief Run the pass over the function. - PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); }; } diff --git a/include/llvm/Transforms/Scalar/Sink.h b/include/llvm/Transforms/Scalar/Sink.h new file mode 100644 index 000000000000..1144c62fb20c --- /dev/null +++ b/include/llvm/Transforms/Scalar/Sink.h @@ -0,0 +1,30 @@ +//===-- Sink.h - Code Sinking -----------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass moves instructions into successor blocks, when possible, so that +// they aren't executed on paths where their results aren't needed. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_SINK_H +#define LLVM_TRANSFORMS_SCALAR_SINK_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Move instructions into successor blocks when possible. +class SinkingPass : public PassInfoMixin<SinkingPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_SINK_H diff --git a/include/llvm/Transforms/Scalar/TailRecursionElimination.h b/include/llvm/Transforms/Scalar/TailRecursionElimination.h new file mode 100644 index 000000000000..793f9bc152ed --- /dev/null +++ b/include/llvm/Transforms/Scalar/TailRecursionElimination.h @@ -0,0 +1,66 @@ +//===---- TailRecursionElimination.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 transforms calls of the current function (self recursion) followed +// by a return instruction with a branch to the entry of the function, creating +// a loop. This pass also implements the following extensions to the basic +// algorithm: +// +// 1. Trivial instructions between the call and return do not prevent the +// transformation from taking place, though currently the analysis cannot +// support moving any really useful instructions (only dead ones). +// 2. This pass transforms functions that are prevented from being tail +// recursive by an associative and commutative expression to use an +// accumulator variable, thus compiling the typical naive factorial or +// 'fib' implementation into efficient code. +// 3. TRE is performed if the function returns void, if the return +// returns the result returned by the call, or if the function returns a +// run-time constant on all exits from the function. It is possible, though +// unlikely, that the return returns something else (like constant 0), and +// can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in +// the function return the exact same value. +// 4. If it can prove that callees do not access their caller stack frame, +// they are marked as eligible for tail call elimination (by the code +// generator). +// +// There are several improvements that could be made: +// +// 1. If the function has any alloca instructions, these instructions will be +// moved out of the entry block of the function, causing them to be +// evaluated each time through the tail recursion. Safely keeping allocas +// in the entry block requires analysis to proves that the tail-called +// function does not read or write the stack object. +// 2. Tail recursion is only performed if the call immediately precedes the +// return instruction. It's possible that there could be a jump between +// the call and the return. +// 3. There can be intervening operations between the call and the return that +// prevent the TRE from occurring. For example, there could be GEP's and +// stores to memory that will not be read or written by the call. This +// requires some substantial analysis (such as with DSA) to prove safe to +// move ahead of the call, but doing so could allow many more TREs to be +// performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark. +// 4. The algorithm we use to detect if callees access their caller stack +// frames is very primitive. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H +#define LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +struct TailCallElimPass : PassInfoMixin<TailCallElimPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H diff --git a/include/llvm/Transforms/Utils/AddDiscriminators.h b/include/llvm/Transforms/Utils/AddDiscriminators.h new file mode 100644 index 000000000000..0b3a8add6278 --- /dev/null +++ b/include/llvm/Transforms/Utils/AddDiscriminators.h @@ -0,0 +1,29 @@ +//===- AddDiscriminators.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 adds DWARF discriminators to the IR. Path discriminators are used +// to decide what CFG path was taken inside sub-graphs whose instructions share +// the same line and column number information. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H +#define LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class AddDiscriminatorsPass : public PassInfoMixin<AddDiscriminatorsPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 13c856dfdc9a..37fd20925cba 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -22,7 +22,7 @@ namespace llvm { -class MemoryDependenceAnalysis; +class MemoryDependenceResults; class DominatorTree; class LoopInfo; class Instruction; @@ -31,51 +31,45 @@ class ReturnInst; class TargetLibraryInfo; class TerminatorInst; -/// DeleteDeadBlock - Delete the specified block, which must have no -/// predecessors. +/// Delete the specified block, which must have no predecessors. void DeleteDeadBlock(BasicBlock *BB); -/// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are -/// any single-entry PHI nodes in it, fold them away. This handles the case -/// when all entries to the PHI nodes in a block are guaranteed equal, such as -/// when the block has exactly one predecessor. +/// We know that BB has one predecessor. If there are any single-entry PHI nodes +/// in it, fold them away. This handles the case when all entries to the PHI +/// nodes in a block are guaranteed equal, such as when the block has exactly +/// one predecessor. void FoldSingleEntryPHINodes(BasicBlock *BB, - MemoryDependenceAnalysis *MemDep = nullptr); + MemoryDependenceResults *MemDep = nullptr); -/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it -/// is dead. Also recursively delete any operands that become dead as -/// a result. This includes tracing the def-use list from the PHI to see if -/// it is ultimately unused or if it reaches an unused cycle. Return true -/// if any PHIs were deleted. +/// Examine each PHI in the given block and delete it if it is dead. Also +/// recursively delete any operands that become dead as a result. This includes +/// tracing the def-use list from the PHI to see if it is ultimately unused or +/// if it reaches an unused cycle. Return true if any PHIs were deleted. bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); -/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, -/// if possible. The return value indicates success or failure. +/// Attempts to merge a block into its predecessor, if possible. The return +/// value indicates success or failure. bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, - MemoryDependenceAnalysis *MemDep = nullptr); + MemoryDependenceResults *MemDep = nullptr); -// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) -// with a value, then remove and delete the original instruction. -// +/// Replace all uses of an instruction (specified by BI) with a value, then +/// remove and delete the original instruction. void ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V); -// ReplaceInstWithInst - Replace the instruction specified by BI with the -// instruction specified by I. Copies DebugLoc from BI to I, if I doesn't -// already have a DebugLoc. The original instruction is deleted and BI is -// updated to point to the new instruction. -// +/// Replace the instruction specified by BI with the instruction specified by I. +/// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The +/// original instruction is deleted and BI is updated to point to the new +/// instruction. void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I); -// ReplaceInstWithInst - Replace the instruction specified by From with the -// instruction specified by To. Copies DebugLoc from BI to I, if I doesn't -// already have a DebugLoc. -// +/// Replace the instruction specified by From with the instruction specified by +/// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. void ReplaceInstWithInst(Instruction *From, Instruction *To); -/// \brief Option class for critical edge splitting. +/// Option class for critical edge splitting. /// /// This provides a builder interface for overriding the default options used /// during critical edge splitting. @@ -107,10 +101,9 @@ struct CriticalEdgeSplittingOptions { } }; -/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to -/// split the critical edge. This will update the analyses passed in through -/// the option struct. This returns the new block if the edge was split, null -/// otherwise. +/// If this edge is a critical edge, insert a new node to split the critical +/// edge. This will update the analyses passed in through the option struct. +/// This returns the new block if the edge was split, null otherwise. /// /// If MergeIdenticalEdges in the options struct is true (not the default), /// *all* edges from TI to the specified successor will be merged into the same @@ -137,11 +130,10 @@ SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Options); } -/// SplitCriticalEdge - If the edge from *PI to BB is not critical, return -/// false. Otherwise, split all edges between the two blocks and return true. -/// This updates all of the same analyses as the other SplitCriticalEdge -/// function. If P is specified, it updates the analyses -/// described above. +/// If the edge from *PI to BB is not critical, return false. Otherwise, split +/// all edges between the two blocks and return true. This updates all of the +/// same analyses as the other SplitCriticalEdge function. If P is specified, it +/// updates the analyses described above. inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, const CriticalEdgeSplittingOptions &Options = CriticalEdgeSplittingOptions()) { @@ -153,10 +145,9 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, return MadeChange; } -/// SplitCriticalEdge - If an edge from Src to Dst is critical, split the edge -/// and return true, otherwise return false. This method requires that there be -/// an edge between the two blocks. It updates the analyses -/// passed in the options struct +/// If an edge from Src to Dst is critical, split the edge and return true, +/// otherwise return false. This method requires that there be an edge between +/// the two blocks. It updates the analyses passed in the options struct inline BasicBlock * SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, const CriticalEdgeSplittingOptions &Options = @@ -171,30 +162,28 @@ SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, } } -// SplitAllCriticalEdges - Loop over all of the edges in the CFG, -// breaking critical edges as they are found. -// Returns the number of broken edges. +/// Loop over all of the edges in the CFG, breaking critical edges as they are +/// found. Returns the number of broken edges. unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options = CriticalEdgeSplittingOptions()); -/// SplitEdge - Split the edge connecting specified block. +/// Split the edge connecting specified block. BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); -/// SplitBlock - Split the specified block at the specified instruction - every -/// thing before SplitPt stays in Old and everything starting with SplitPt moves -/// to a new block. The two blocks are joined by an unconditional branch and -/// the loop info is updated. -/// +/// Split the specified block at the specified instruction - everything before +/// SplitPt stays in Old and everything starting with SplitPt moves to a new +/// block. The two blocks are joined by an unconditional branch and the loop +/// info is updated. BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); -/// SplitBlockPredecessors - This method introduces at least one new basic block -/// into the function and moves some of the predecessors of BB to be -/// predecessors of the new block. The new predecessors are indicated by the -/// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic -/// block to which predecessors from Preds are now pointing. +/// This method introduces at least one new basic block into the function and +/// moves some of the predecessors of BB to be predecessors of the new block. +/// The new predecessors are indicated by the Preds array. The new block is +/// given a suffix of 'Suffix'. Returns new basic block to which predecessors +/// from Preds are now pointing. /// /// If BB is a landingpad block then additional basicblock might be introduced. /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more @@ -211,12 +200,12 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, LoopInfo *LI = nullptr, bool PreserveLCSSA = false); -/// SplitLandingPadPredecessors - This method transforms the landing pad, -/// OrigBB, by introducing two new basic blocks into the function. One of those -/// new basic blocks gets the predecessors listed in Preds. The other basic -/// block gets the remaining predecessors of OrigBB. The landingpad instruction -/// OrigBB is clone into both of the new basic blocks. The new blocks are given -/// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector. +/// This method transforms the landing pad, OrigBB, by introducing two new basic +/// blocks into the function. One of those new basic blocks gets the +/// predecessors listed in Preds. The other basic block gets the remaining +/// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both +/// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and +/// 'Suffix2', and are returned in the NewBBs vector. /// /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but /// no other analyses. In particular, it does not preserve LoopSimplify @@ -231,19 +220,17 @@ void SplitLandingPadPredecessors(BasicBlock *OrigBB, LoopInfo *LI = nullptr, bool PreserveLCSSA = false); -/// FoldReturnIntoUncondBranch - This method duplicates the specified return -/// instruction into a predecessor which ends in an unconditional branch. If -/// the return instruction returns a value defined by a PHI, propagate the -/// right value into the return. It returns the new return instruction in the -/// predecessor. +/// This method duplicates the specified return instruction into a predecessor +/// which ends in an unconditional branch. If the return instruction returns a +/// value defined by a PHI, propagate the right value into the return. It +/// returns the new return instruction in the predecessor. ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred); -/// SplitBlockAndInsertIfThen - Split the containing block at the -/// specified instruction - everything before and including SplitBefore stays -/// in the old basic block, and everything after SplitBefore is moved to a -/// new block. The two blocks are connected by a conditional branch -/// (with value of Cmp being the condition). +/// Split the containing block at the specified instruction - everything before +/// and including SplitBefore stays in the old basic block, and everything after +/// SplitBefore is moved to a new block. The two blocks are connected by a +/// conditional branch (with value of Cmp being the condition). /// Before: /// Head /// SplitBefore @@ -259,11 +246,12 @@ ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, /// UnreachableInst, otherwise it branches to Tail. /// Returns the NewBasicBlock's terminator. /// -/// Updates DT if given. +/// Updates DT and LI if given. TerminatorInst *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights = nullptr, - DominatorTree *DT = nullptr); + DominatorTree *DT = nullptr, + LoopInfo *LI = nullptr); /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, /// but also creates the ElseBlock. @@ -284,12 +272,14 @@ void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, TerminatorInst **ElseTerm, MDNode *BranchWeights = nullptr); -/// -/// GetIfCondition - Check whether BB is the merge point of a if-region. +/// Check whether BB is the merge point of a if-region. /// If so, return the boolean condition that determines which entry into /// BB will be taken. Also, return by references the block that will be /// entered from if the condition is true, and the block that will be /// entered if the condition is false. +/// +/// This does no checking to see if the true/false blocks have large or unsavory +/// instructions in them. Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse); } // End llvm namespace diff --git a/include/llvm/Transforms/Utils/BuildLibCalls.h b/include/llvm/Transforms/Utils/BuildLibCalls.h index 879f295caf0c..2d2a85905d0e 100644 --- a/include/llvm/Transforms/Utils/BuildLibCalls.h +++ b/include/llvm/Transforms/Utils/BuildLibCalls.h @@ -22,94 +22,96 @@ namespace llvm { class DataLayout; class TargetLibraryInfo; - /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*. - Value *CastToCStr(Value *V, IRBuilder<> &B); - - /// EmitStrLen - Emit a call to the strlen function to the builder, for the - /// specified pointer. Ptr is required to be some pointer type, and the - /// return value has 'intptr_t' type. - Value *EmitStrLen(Value *Ptr, IRBuilder<> &B, const DataLayout &DL, + /// Analyze the name and prototype of the given function and set any + /// applicable attributes. + /// If the library function is unavailable, this doesn't modify it. + /// + /// Returns true if any attributes were set and false otherwise. + bool inferLibFuncAttributes(Function &F, const TargetLibraryInfo &TLI); + + /// Return V if it is an i8*, otherwise cast it to i8*. + Value *castToCStr(Value *V, IRBuilder<> &B); + + /// Emit a call to the strlen function to the builder, for the specified + /// pointer. Ptr is required to be some pointer type, and the return value has + /// 'intptr_t' type. + Value *emitStrLen(Value *Ptr, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitStrNLen - Emit a call to the strnlen function to the builder, for the - /// specified pointer. Ptr is required to be some pointer type, MaxLen must - /// be of size_t type, and the return value has 'intptr_t' type. - Value *EmitStrNLen(Value *Ptr, Value *MaxLen, IRBuilder<> &B, + /// Emit a call to the strnlen function to the builder, for the specified + /// pointer. Ptr is required to be some pointer type, MaxLen must be of size_t + /// type, and the return value has 'intptr_t' type. + Value *emitStrNLen(Value *Ptr, Value *MaxLen, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitStrChr - Emit a call to the strchr function to the builder, for the - /// specified pointer and character. Ptr is required to be some pointer type, - /// and the return value has 'i8*' type. - Value *EmitStrChr(Value *Ptr, char C, IRBuilder<> &B, + /// Emit a call to the strchr function to the builder, for the specified + /// pointer and character. Ptr is required to be some pointer type, and the + /// return value has 'i8*' type. + Value *emitStrChr(Value *Ptr, char C, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitStrNCmp - Emit a call to the strncmp function to the builder. - Value *EmitStrNCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, + /// Emit a call to the strncmp function to the builder. + Value *emitStrNCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitStrCpy - Emit a call to the strcpy function to the builder, for the - /// specified pointer arguments. - Value *EmitStrCpy(Value *Dst, Value *Src, IRBuilder<> &B, + /// Emit a call to the strcpy function to the builder, for the specified + /// pointer arguments. + Value *emitStrCpy(Value *Dst, Value *Src, IRBuilder<> &B, const TargetLibraryInfo *TLI, StringRef Name = "strcpy"); - /// EmitStrNCpy - Emit a call to the strncpy function to the builder, for the - /// specified pointer arguments and length. - Value *EmitStrNCpy(Value *Dst, Value *Src, Value *Len, IRBuilder<> &B, + /// Emit a call to the strncpy function to the builder, for the specified + /// pointer arguments and length. + Value *emitStrNCpy(Value *Dst, Value *Src, Value *Len, IRBuilder<> &B, const TargetLibraryInfo *TLI, StringRef Name = "strncpy"); - /// EmitMemCpyChk - Emit a call to the __memcpy_chk function to the builder. - /// This expects that the Len and ObjSize have type 'intptr_t' and Dst/Src - /// are pointers. - Value *EmitMemCpyChk(Value *Dst, Value *Src, Value *Len, Value *ObjSize, + /// Emit a call to the __memcpy_chk function to the builder. This expects that + /// the Len and ObjSize have type 'intptr_t' and Dst/Src are pointers. + Value *emitMemCpyChk(Value *Dst, Value *Src, Value *Len, Value *ObjSize, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitMemChr - Emit a call to the memchr function. This assumes that Ptr is - /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value. - Value *EmitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B, + /// Emit a call to the memchr function. This assumes that Ptr is a pointer, + /// Val is an i32 value, and Len is an 'intptr_t' value. + Value *emitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitMemCmp - Emit a call to the memcmp function. - Value *EmitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, + /// Emit a call to the memcmp function. + Value *emitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' - /// (e.g. 'floor'). This function is known to take a single of type matching - /// 'Op' and returns one value with the same type. If 'Op' is a long double, - /// 'l' is added as the suffix of name, if 'Op' is a float, we add a 'f' - /// suffix. - Value *EmitUnaryFloatFnCall(Value *Op, StringRef Name, IRBuilder<> &B, + /// Emit a call to the unary function named 'Name' (e.g. 'floor'). This + /// function is known to take a single of type matching 'Op' and returns one + /// value with the same type. If 'Op' is a long double, 'l' is added as the + /// suffix of name, if 'Op' is a float, we add a 'f' suffix. + Value *emitUnaryFloatFnCall(Value *Op, StringRef Name, IRBuilder<> &B, const AttributeSet &Attrs); - /// EmitUnaryFloatFnCall - Emit a call to the binary function named 'Name' - /// (e.g. 'fmin'). This function is known to take type matching 'Op1' and - /// 'Op2' and return one value with the same type. If 'Op1/Op2' are long - /// double, 'l' is added as the suffix of name, if 'Op1/Op2' are float, we - /// add a 'f' suffix. - Value *EmitBinaryFloatFnCall(Value *Op1, Value *Op2, StringRef Name, + /// Emit a call to the binary function named 'Name' (e.g. 'fmin'). This + /// function is known to take type matching 'Op1' and 'Op2' and return one + /// value with the same type. If 'Op1/Op2' are long double, 'l' is added as + /// the suffix of name, if 'Op1/Op2' are float, we add a 'f' suffix. + Value *emitBinaryFloatFnCall(Value *Op1, Value *Op2, StringRef Name, IRBuilder<> &B, const AttributeSet &Attrs); - /// EmitPutChar - Emit a call to the putchar function. This assumes that Char - /// is an integer. - Value *EmitPutChar(Value *Char, IRBuilder<> &B, const TargetLibraryInfo *TLI); + /// Emit a call to the putchar function. This assumes that Char is an integer. + Value *emitPutChar(Value *Char, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitPutS - Emit a call to the puts function. This assumes that Str is - /// some pointer. - Value *EmitPutS(Value *Str, IRBuilder<> &B, const TargetLibraryInfo *TLI); + /// Emit a call to the puts function. This assumes that Str is some pointer. + Value *emitPutS(Value *Str, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitFPutC - Emit a call to the fputc function. This assumes that Char is - /// an i32, and File is a pointer to FILE. - Value *EmitFPutC(Value *Char, Value *File, IRBuilder<> &B, + /// Emit a call to the fputc function. This assumes that Char is an i32, and + /// File is a pointer to FILE. + Value *emitFPutC(Value *Char, Value *File, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitFPutS - Emit a call to the puts function. Str is required to be a - /// pointer and File is a pointer to FILE. - Value *EmitFPutS(Value *Str, Value *File, IRBuilder<> &B, + /// Emit a call to the puts function. Str is required to be a pointer and + /// File is a pointer to FILE. + Value *emitFPutS(Value *Str, Value *File, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitFWrite - Emit a call to the fwrite function. This assumes that Ptr is - /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE. - Value *EmitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B, + /// Emit a call to the fwrite function. This assumes that Ptr is a pointer, + /// Size is an 'intptr_t', and File is a pointer to FILE. + Value *emitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); } diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h index 4f006f2adeef..c5fb37007090 100644 --- a/include/llvm/Transforms/Utils/Cloning.h +++ b/include/llvm/Transforms/Utils/Cloning.h @@ -59,7 +59,7 @@ std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap); /// in place of the global definition. std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap, - std::function<bool(const GlobalValue *)> ShouldCloneDefinition); + function_ref<bool(const GlobalValue *)> ShouldCloneDefinition); /// ClonedCodeInfo - This struct can be used to capture information about code /// being cloned, while it is being cloned. @@ -114,20 +114,19 @@ BasicBlock *CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix = "", Function *F = nullptr, ClonedCodeInfo *CodeInfo = nullptr); -/// CloneFunction - Return a copy of the specified function, but without -/// embedding the function into another module. Also, any references specified -/// in the VMap are changed to refer to their mapped value instead of the -/// original one. If any of the arguments to the function are in the VMap, -/// the arguments are deleted from the resultant function. The VMap is -/// updated to include mappings from all of the instructions and basicblocks in -/// the function from their old to new values. The final argument captures -/// information about the cloned code if non-null. +/// CloneFunction - Return a copy of the specified function and add it to that +/// function's module. Also, any references specified in the VMap are changed +/// to refer to their mapped value instead of the original one. If any of the +/// arguments to the function are in the VMap, the arguments are deleted from +/// the resultant function. The VMap is updated to include mappings from all of +/// the instructions and basicblocks in the function from their old to new +/// values. The final argument captures information about the cloned code if +/// non-null. /// -/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue -/// mappings, and debug info metadata will not be cloned. +/// VMap contains no non-identity GlobalValue mappings and debug info metadata +/// will not be cloned. /// -Function *CloneFunction(const Function *F, ValueToValueMapTy &VMap, - bool ModuleLevelChanges, +Function *CloneFunction(Function *F, ValueToValueMapTy &VMap, ClonedCodeInfo *CodeInfo = nullptr); /// Clone OldFunc into NewFunc, transforming the old arguments into references @@ -221,6 +220,7 @@ bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI, /// /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block /// \p LoopDomBB. Insert the new blocks before block specified in \p Before. +/// Note: Only innermost loops are supported. Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, diff --git a/include/llvm/Transforms/Utils/CodeExtractor.h b/include/llvm/Transforms/Utils/CodeExtractor.h index 3a96d955cac2..30dafd045f23 100644 --- a/include/llvm/Transforms/Utils/CodeExtractor.h +++ b/include/llvm/Transforms/Utils/CodeExtractor.h @@ -15,10 +15,10 @@ #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H -#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SetVector.h" namespace llvm { +template <typename T> class ArrayRef; class BasicBlock; class DominatorTree; class Function; diff --git a/include/llvm/Transforms/Utils/Evaluator.h b/include/llvm/Transforms/Utils/Evaluator.h new file mode 100644 index 000000000000..07f12f41b3bc --- /dev/null +++ b/include/llvm/Transforms/Utils/Evaluator.h @@ -0,0 +1,119 @@ +//===-- Evaluator.h - LLVM IR evaluator -------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Function evaluator for LLVM IR. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H +#define LLVM_TRANSFORMS_UTILS_EVALUATOR_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/GlobalVariable.h" + +#include <deque> +#include <memory> + +namespace llvm { + +class DataLayout; +class Function; +class TargetLibraryInfo; + +/// This class evaluates LLVM IR, producing the Constant representing each SSA +/// instruction. Changes to global variables are stored in a mapping that can +/// be iterated over after the evaluation is complete. Once an evaluation call +/// fails, the evaluation object should not be reused. +class Evaluator { +public: + Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI) + : DL(DL), TLI(TLI) { + ValueStack.emplace_back(); + } + + ~Evaluator() { + for (auto &Tmp : AllocaTmps) + // If there are still users of the alloca, the program is doing something + // silly, e.g. storing the address of the alloca somewhere and using it + // later. Since this is undefined, we'll just make it be null. + if (!Tmp->use_empty()) + Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); + } + + /// Evaluate a call to function F, returning true if successful, false if we + /// can't evaluate it. ActualArgs contains the formal arguments for the + /// function. + bool EvaluateFunction(Function *F, Constant *&RetVal, + const SmallVectorImpl<Constant*> &ActualArgs); + + /// Evaluate all instructions in block BB, returning true if successful, false + /// if we can't evaluate it. NewBB returns the next BB that control flows + /// into, or null upon return. + bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB); + + Constant *getVal(Value *V) { + if (Constant *CV = dyn_cast<Constant>(V)) return CV; + Constant *R = ValueStack.back().lookup(V); + assert(R && "Reference to an uncomputed value!"); + return R; + } + + void setVal(Value *V, Constant *C) { + ValueStack.back()[V] = C; + } + + const DenseMap<Constant*, Constant*> &getMutatedMemory() const { + return MutatedMemory; + } + + const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const { + return Invariants; + } + +private: + Constant *ComputeLoadResult(Constant *P); + + /// As we compute SSA register values, we store their contents here. The back + /// of the deque contains the current function and the stack contains the + /// values in the calling frames. + std::deque<DenseMap<Value*, Constant*>> ValueStack; + + /// This is used to detect recursion. In pathological situations we could hit + /// exponential behavior, but at least there is nothing unbounded. + SmallVector<Function*, 4> CallStack; + + /// For each store we execute, we update this map. Loads check this to get + /// the most up-to-date value. If evaluation is successful, this state is + /// committed to the process. + DenseMap<Constant*, Constant*> MutatedMemory; + + /// To 'execute' an alloca, we create a temporary global variable to represent + /// its body. This vector is needed so we can delete the temporary globals + /// when we are done. + SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps; + + /// These global variables have been marked invariant by the static + /// constructor. + SmallPtrSet<GlobalVariable*, 8> Invariants; + + /// These are constants we have checked and know to be simple enough to live + /// in a static initializer of a global. + SmallPtrSet<Constant*, 8> SimpleConstants; + + const DataLayout &DL; + const TargetLibraryInfo *TLI; +}; + +} + +#endif diff --git a/include/llvm/Transforms/Utils/FunctionImportUtils.h b/include/llvm/Transforms/Utils/FunctionImportUtils.h new file mode 100644 index 000000000000..3b94ef60be5d --- /dev/null +++ b/include/llvm/Transforms/Utils/FunctionImportUtils.h @@ -0,0 +1,100 @@ +//===- FunctionImportUtils.h - Importing support utilities -----*- 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 FunctionImportGlobalProcessing class which is used +// to perform the necessary global value handling for function importing. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONIMPORTUTILS_H +#define LLVM_TRANSFORMS_UTILS_FUNCTIONIMPORTUTILS_H + +#include "llvm/ADT/SetVector.h" +#include "llvm/IR/ModuleSummaryIndex.h" + +namespace llvm { +class Module; + +/// Class to handle necessary GlobalValue changes required by ThinLTO +/// function importing, including linkage changes and any necessary renaming. +class FunctionImportGlobalProcessing { + /// The Module which we are exporting or importing functions from. + Module &M; + + /// Module summary index passed in for function importing/exporting handling. + const ModuleSummaryIndex &ImportIndex; + + /// Globals to import from this module, all other functions will be + /// imported as declarations instead of definitions. + DenseSet<const GlobalValue *> *GlobalsToImport; + + /// Set to true if the given ModuleSummaryIndex contains any functions + /// from this source module, in which case we must conservatively assume + /// that any of its functions may be imported into another module + /// as part of a different backend compilation process. + bool HasExportedFunctions = false; + + /// Check if we should promote the given local value to global scope. + bool doPromoteLocalToGlobal(const GlobalValue *SGV); + + /// Helper methods to check if we are importing from or potentially + /// exporting from the current source module. + bool isPerformingImport() const { return GlobalsToImport != nullptr; } + bool isModuleExporting() const { return HasExportedFunctions; } + + /// If we are importing from the source module, checks if we should + /// import SGV as a definition, otherwise import as a declaration. + bool doImportAsDefinition(const GlobalValue *SGV); + + /// Get the name for SGV that should be used in the linked destination + /// module. Specifically, this handles the case where we need to rename + /// a local that is being promoted to global scope. + std::string getName(const GlobalValue *SGV); + + /// Process globals so that they can be used in ThinLTO. This includes + /// promoting local variables so that they can be reference externally by + /// thin lto imported globals and converting strong external globals to + /// available_externally. + void processGlobalsForThinLTO(); + void processGlobalForThinLTO(GlobalValue &GV); + + /// Get the new linkage for SGV that should be used in the linked destination + /// module. Specifically, for ThinLTO importing or exporting it may need + /// to be adjusted. + GlobalValue::LinkageTypes getLinkage(const GlobalValue *SGV); + +public: + FunctionImportGlobalProcessing( + Module &M, const ModuleSummaryIndex &Index, + DenseSet<const GlobalValue *> *GlobalsToImport = nullptr) + : M(M), ImportIndex(Index), GlobalsToImport(GlobalsToImport) { + // If we have a ModuleSummaryIndex but no function to import, + // then this is the primary module being compiled in a ThinLTO + // backend compilation, and we need to see if it has functions that + // may be exported to another backend compilation. + if (!GlobalsToImport) + HasExportedFunctions = ImportIndex.hasExportedFunctions(M); + } + + bool run(); + + static bool + doImportAsDefinition(const GlobalValue *SGV, + DenseSet<const GlobalValue *> *GlobalsToImport); +}; + +/// Perform in-place global value handling on the given Module for +/// exported local functions renamed and promoted for ThinLTO. +bool renameModuleForThinLTO( + Module &M, const ModuleSummaryIndex &Index, + DenseSet<const GlobalValue *> *GlobalsToImport = nullptr); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Transforms/Utils/LCSSA.h b/include/llvm/Transforms/Utils/LCSSA.h new file mode 100644 index 000000000000..f0277d021541 --- /dev/null +++ b/include/llvm/Transforms/Utils/LCSSA.h @@ -0,0 +1,44 @@ +//===- LCSSA.h - Loop-closed SSA transform Pass -----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass transforms loops by placing phi nodes at the end of the loops for +// all values that are live across the loop boundary. For example, it turns +// the left into the right code: +// +// for (...) for (...) +// if (c) if (c) +// X1 = ... X1 = ... +// else else +// X2 = ... X2 = ... +// X3 = phi(X1, X2) X3 = phi(X1, X2) +// ... = X3 + 4 X4 = phi(X3) +// ... = X4 + 4 +// +// This is still valid LLVM; the extra phi nodes are purely redundant, and will +// be trivially eliminated by InstCombine. The major benefit of this +// transformation is that it makes many other loop optimizations, such as +// LoopUnswitching, simpler. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LCSSA_H +#define LLVM_TRANSFORMS_UTILS_LCSSA_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Converts loops into loop-closed SSA form. +class LCSSAPass : public PassInfoMixin<LCSSAPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LCSSA_H diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 3ae01657a2ec..43b376cf8068 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -21,6 +21,7 @@ #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Operator.h" +#include "llvm/ADT/SmallPtrSet.h" namespace llvm { @@ -29,6 +30,7 @@ class BasicBlock; class Function; class BranchInst; class Instruction; +class CallInst; class DbgDeclareInst; class StoreInst; class LoadInst; @@ -50,10 +52,10 @@ template<typename T> class SmallVectorImpl; // Local constant propagation. // -/// ConstantFoldTerminator - If a terminator instruction is predicated on a -/// constant value, convert it into an unconditional branch to the constant -/// destination. This is a nontrivial operation because the successors of this -/// basic block must have their PHI nodes updated. +/// If a terminator instruction is predicated on a constant value, convert it +/// into an unconditional branch to the constant destination. +/// This is a nontrivial operation because the successors of this basic block +/// must have their PHI nodes updated. /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. @@ -64,29 +66,27 @@ bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, // Local dead code elimination. // -/// isInstructionTriviallyDead - Return true if the result produced by the -/// instruction is not used, and the instruction has no side effects. -/// +/// Return true if the result produced by the instruction is not used, and the +/// instruction has no side effects. bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI = nullptr); -/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a -/// trivially dead instruction, delete it. If that makes any of its operands -/// trivially dead, delete them too, recursively. Return true if any -/// instructions were deleted. +/// If the specified value is a trivially dead instruction, delete it. +/// If that makes any of its operands trivially dead, delete them too, +/// recursively. Return true if any instructions were deleted. bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI = nullptr); -/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively -/// dead PHI node, due to being a def-use chain of single-use nodes that -/// either forms a cycle or is terminated by a trivially dead instruction, -/// delete it. If that makes any of its operands trivially dead, delete them -/// too, recursively. Return true if a change was made. +/// If the specified value is an effectively dead PHI node, due to being a +/// def-use chain of single-use nodes that either forms a cycle or is terminated +/// by a trivially dead instruction, delete it. If that makes any of its +/// operands trivially dead, delete them too, recursively. Return true if a +/// change was made. bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI = nullptr); -/// SimplifyInstructionsInBlock - Scan the specified basic block and try to -/// simplify any instructions in it and recursively delete dead instructions. +/// Scan the specified basic block and try to simplify any instructions in it +/// and recursively delete dead instructions. /// /// This returns true if it changed the code, note that it can delete /// instructions in other blocks as well in this block. @@ -97,9 +97,9 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB, // Control Flow Graph Restructuring. // -/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this -/// method is called when we're about to delete Pred as a predecessor of BB. If -/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. +/// Like BasicBlock::removePredecessor, this method is called when we're about +/// to delete Pred as a predecessor of BB. If BB contains any PHI nodes, this +/// drops the entries in the PHI nodes for Pred. /// /// Unlike the removePredecessor method, this attempts to simplify uses of PHI /// nodes that collapse into identity values. For example, if we have: @@ -110,74 +110,68 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB, /// recursively fold the 'and' to 0. void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred); -/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its -/// predecessor is known to have one successor (BB!). Eliminate the edge -/// between them, moving the instructions in the predecessor into BB. This -/// deletes the predecessor block. -/// +/// BB is a block with one predecessor and its predecessor is known to have one +/// successor (BB!). Eliminate the edge between them, moving the instructions in +/// the predecessor into BB. This deletes the predecessor block. void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr); -/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an -/// unconditional branch, and contains no instructions other than PHI nodes, -/// potential debug intrinsics and the branch. If possible, eliminate BB by -/// rewriting all the predecessors to branch to the successor block and return -/// true. If we can't transform, return false. +/// BB is known to contain an unconditional branch, and contains no instructions +/// other than PHI nodes, potential debug intrinsics and the branch. If +/// possible, eliminate BB by rewriting all the predecessors to branch to the +/// successor block and return true. If we can't transform, return false. bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); -/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI -/// nodes in this block. This doesn't try to be clever about PHI nodes -/// which differ only in the order of the incoming values, but instcombine -/// orders them so it usually won't matter. -/// +/// Check for and eliminate duplicate PHI nodes in this block. This doesn't try +/// to be clever about PHI nodes which differ only in the order of the incoming +/// values, but instcombine orders them so it usually won't matter. bool EliminateDuplicatePHINodes(BasicBlock *BB); -/// SimplifyCFG - This function is used to do simplification of a CFG. For +/// This function is used to do simplification of a CFG. For /// example, it adjusts branches to branches to eliminate the extra hop, it /// eliminates unreachable basic blocks, and does other "peephole" optimization /// of the CFG. It returns true if a modification was made, possibly deleting -/// the basic block that was pointed to. -/// +/// the basic block that was pointed to. LoopHeaders is an optional input +/// parameter, providing the set of loop header that SimplifyCFG should not +/// eliminate. bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC = nullptr); + unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, + SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr); -/// FlatternCFG - This function is used to flatten a CFG. For -/// example, it uses parallel-and and parallel-or mode to collapse -// if-conditions and merge if-regions with identical statements. -/// +/// This function is used to flatten a CFG. For example, it uses parallel-and +/// and parallel-or mode to collapse if-conditions and merge if-regions with +/// identical statements. bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr); -/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, -/// and if a predecessor branches to us and one of our successors, fold the -/// setcc into the predecessor and use logical operations to pick the right -/// destination. +/// If this basic block is ONLY a setcc and a branch, and if a predecessor +/// branches to us and one of our successors, fold the setcc into the +/// predecessor and use logical operations to pick the right destination. bool FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold = 1); -/// DemoteRegToStack - This function takes a virtual register computed by an -/// Instruction and replaces it with a slot in the stack frame, allocated via -/// alloca. This allows the CFG to be changed around without fear of -/// invalidating the SSA information for the value. It returns the pointer to -/// the alloca inserted to create a stack slot for X. -/// +/// This function takes a virtual register computed by an Instruction and +/// replaces it with a slot in the stack frame, allocated via alloca. +/// This allows the CFG to be changed around without fear of invalidating the +/// SSA information for the value. It returns the pointer to the alloca inserted +/// to create a stack slot for X. AllocaInst *DemoteRegToStack(Instruction &X, bool VolatileLoads = false, Instruction *AllocaPoint = nullptr); -/// DemotePHIToStack - This function takes a virtual register computed by a phi -/// node and replaces it with a slot in the stack frame, allocated via alloca. -/// The phi node is deleted and it returns the pointer to the alloca inserted. +/// This function takes a virtual register computed by a phi node and replaces +/// it with a slot in the stack frame, allocated via alloca. The phi node is +/// deleted and it returns the pointer to the alloca inserted. AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); -/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that -/// we can determine, return it, otherwise return 0. If PrefAlign is specified, -/// and it is more than the alignment of the ultimate object, see if we can -/// increase the alignment of the ultimate object, making this check succeed. +/// If the specified pointer has an alignment that we can determine, return it, +/// otherwise return 0. If PrefAlign is specified, and it is more than the +/// alignment of the ultimate object, see if we can increase the alignment of +/// the ultimate object, making this check succeed. unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr); -/// getKnownAlignment - Try to infer an alignment for the specified pointer. +/// Try to infer an alignment for the specified pointer. static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, @@ -185,9 +179,9 @@ static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); } -/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the -/// code necessary to compute the offset from the base pointer (without adding -/// in the base pointer). Return the result as a signed integer of intptr size. +/// Given a getelementptr instruction/constantexpr, emit the code necessary to +/// compute the offset from the base pointer (without adding in the base +/// pointer). Return the result as a signed integer of intptr size. /// When NoAssumptions is true, no assumptions about index computation not /// overflowing is made. template <typename IRBuilderTy> @@ -264,15 +258,14 @@ bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, LoadInst *LI, DIBuilder &Builder); -/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set -/// of llvm.dbg.value intrinsics. +/// Lowers llvm.dbg.declare intrinsics into appropriate set of +/// llvm.dbg.value intrinsics. bool LowerDbgDeclare(Function &F); -/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic corresponding to -/// an alloca, if any. +/// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any. DbgDeclareInst *FindAllocaDbgDeclare(Value *V); -/// \brief Replaces llvm.dbg.declare instruction when the address it describes +/// Replaces llvm.dbg.declare instruction when the address it describes /// is replaced with a new value. If Deref is true, an additional DW_OP_deref is /// prepended to the expression. If Offset is non-zero, a constant displacement /// is added to the expression (after the optional Deref). Offset can be @@ -281,7 +274,7 @@ bool replaceDbgDeclare(Value *Address, Value *NewAddress, Instruction *InsertBefore, DIBuilder &Builder, bool Deref, int Offset); -/// \brief Replaces llvm.dbg.declare instruction when the alloca it describes +/// Replaces llvm.dbg.declare instruction when the alloca it describes /// is replaced with a new value. If Deref is true, an additional DW_OP_deref is /// prepended to the expression. If Offset is non-zero, a constant displacement /// is added to the expression (after the optional Deref). Offset can be @@ -289,39 +282,51 @@ bool replaceDbgDeclare(Value *Address, Value *NewAddress, bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool Deref, int Offset = 0); -/// \brief Insert an unreachable instruction before the specified +/// Replaces multiple llvm.dbg.value instructions when the alloca it describes +/// is replaced with a new value. If Offset is non-zero, a constant displacement +/// is added to the expression (after the mandatory Deref). Offset can be +/// negative. New llvm.dbg.value instructions are inserted at the locations of +/// the instructions they replace. +void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, + DIBuilder &Builder, int Offset = 0); + +/// Remove all instructions from a basic block other than it's terminator +/// and any present EH pad instructions. +unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); + +/// Insert an unreachable instruction before the specified /// instruction, making it and the rest of the code in the block dead. -void changeToUnreachable(Instruction *I, bool UseLLVMTrap); +unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap); /// Replace 'BB's terminator with one that does not have an unwind successor -/// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind +/// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind /// successor. /// /// \param BB Block whose terminator will be replaced. Its terminator must /// have an unwind successor. void removeUnwindEdge(BasicBlock *BB); -/// \brief Remove all blocks that can not be reached from the function's entry. +/// Remove all blocks that can not be reached from the function's entry. /// /// Returns true if any basic block was removed. bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr); -/// \brief Combine the metadata of two instructions so that K can replace J +/// Combine the metadata of two instructions so that K can replace J /// /// Metadata not listed as known via KnownIDs is removed void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs); -/// \brief Replace each use of 'From' with 'To' if that use is dominated by +/// Replace each use of 'From' with 'To' if that use is dominated by /// the given edge. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge); -/// \brief Replace each use of 'From' with 'To' if that use is dominated by -/// the given BasicBlock. Returns the number of replacements made. +/// Replace each use of 'From' with 'To' if that use is dominated by +/// the end of the given BasicBlock. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB); -/// \brief Return true if the CallSite CS calls a gc leaf function. +/// Return true if the CallSite CS calls a gc leaf function. /// /// A leaf function is a function that does not safepoint the thread during its /// execution. During a call or invoke to such a function, the callers stack @@ -335,7 +340,7 @@ bool callsGCLeafFunction(ImmutableCallSite CS); // Intrinsic pattern matching // -/// Try and match a bitreverse or bswap idiom. +/// Try and match a bswap or bitreverse idiom. /// /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added /// instructions are returned in \c InsertedInsts. They will all have been added @@ -346,10 +351,21 @@ bool callsGCLeafFunction(ImmutableCallSite CS); /// to BW / 4 nodes to be searched, so is significantly faster. /// /// This function returns true on a successful match or false otherwise. -bool recognizeBitReverseOrBSwapIdiom( +bool recognizeBSwapOrBitReverseIdiom( Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl<Instruction *> &InsertedInsts); +//===----------------------------------------------------------------------===// +// Sanitizer utilities +// + +/// Given a CallInst, check if it calls a string function known to CodeGen, +/// and mark it with NoBuiltin if so. To be used by sanitizers that intend +/// to intercept string functions and want to avoid converting them to target +/// specific instructions. +void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, + const TargetLibraryInfo *TLI); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Utils/LoopSimplify.h b/include/llvm/Transforms/Utils/LoopSimplify.h new file mode 100644 index 000000000000..7cf89eaeb939 --- /dev/null +++ b/include/llvm/Transforms/Utils/LoopSimplify.h @@ -0,0 +1,65 @@ +//===- LoopSimplify.h - Loop Canonicalization Pass --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs several transformations to transform natural loops into a +// simpler form, which makes subsequent analyses and transformations simpler and +// more effective. +// +// Loop pre-header insertion guarantees that there is a single, non-critical +// entry edge from outside of the loop to the loop header. This simplifies a +// number of analyses and transformations, such as LICM. +// +// Loop exit-block insertion guarantees that all exit blocks from the loop +// (blocks which are outside of the loop that have predecessors inside of the +// loop) only have predecessors from inside of the loop (and are thus dominated +// by the loop header). This simplifies transformations such as store-sinking +// that are built into LICM. +// +// This pass also guarantees that loops will have exactly one backedge. +// +// Indirectbr instructions introduce several complications. If the loop +// contains or is entered by an indirectbr instruction, it may not be possible +// to transform the loop and make these guarantees. Client code should check +// that these conditions are true before relying on them. +// +// Note that the simplifycfg pass will clean up blocks which are split out but +// end up being unnecessary, so usage of this pass should not pessimize +// generated code. +// +// This pass obviously modifies the CFG, but updates loop information and +// dominator information. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H +#define LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H + +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// This pass is responsible for loop canonicalization. +class LoopSimplifyPass : public PassInfoMixin<LoopSimplifyPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Simplify each loop in a loop nest recursively. +/// +/// This takes a potentially un-simplified loop L (and its children) and turns +/// it into a simplified loop nest with preheaders and single backedges. It will +/// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. +bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, + AssumptionCache *AC, bool PreserveLCSSA); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 2cfacb650ff5..89fea10f818a 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -30,20 +30,21 @@ class DominatorTree; class Loop; class LoopInfo; class Pass; +class PredicatedScalarEvolution; class PredIteratorCache; class ScalarEvolution; +class SCEV; class TargetLibraryInfo; /// \brief Captures loop safety information. /// It keep information for loop & its header may throw exception. -struct LICMSafetyInfo { - bool MayThrow; // The current loop contains an instruction which - // may throw. - bool HeaderMayThrow; // Same as previous, but specific to loop header +struct LoopSafetyInfo { + bool MayThrow; // The current loop contains an instruction which + // may throw. + bool HeaderMayThrow; // Same as previous, but specific to loop header // Used to update funclet bundle operands. DenseMap<BasicBlock *, ColorVector> BlockColors; - LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false) - {} + LoopSafetyInfo() : MayThrow(false), HeaderMayThrow(false) {} }; /// The RecurrenceDescriptor is used to identify recurrences variables in a @@ -175,6 +176,13 @@ public: static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes); + /// Returns true if Phi is a first-order recurrence. A first-order recurrence + /// is a non-reduction recurrence relation in which the value of the + /// recurrence in the current loop iteration equals a value defined in the + /// previous iteration. + static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, + DominatorTree *DT); + RecurrenceKind getRecurrenceKind() { return Kind; } MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } @@ -261,7 +269,7 @@ public: public: /// Default constructor - creates an invalid induction. InductionDescriptor() - : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {} + : StartValue(nullptr), IK(IK_NoInduction), Step(nullptr) {} /// Get the consecutive direction. Returns: /// 0 - unknown or non-consecutive. @@ -275,37 +283,59 @@ public: /// For pointer induction, returns StartValue[Index * StepValue]. /// FIXME: The newly created binary instructions should contain nsw/nuw /// flags, which can be found from the original scalar operations. - Value *transform(IRBuilder<> &B, Value *Index) const; + Value *transform(IRBuilder<> &B, Value *Index, ScalarEvolution *SE, + const DataLayout& DL) const; Value *getStartValue() const { return StartValue; } InductionKind getKind() const { return IK; } - ConstantInt *getStepValue() const { return StepValue; } - + const SCEV *getStep() const { return Step; } + ConstantInt *getConstIntStepValue() const; + + /// Returns true if \p Phi is an induction. If \p Phi is an induction, + /// the induction descriptor \p D will contain the data describing this + /// induction. If by some other means the caller has a better SCEV + /// expression for \p Phi than the one returned by the ScalarEvolution + /// analysis, it can be passed through \p Expr. static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE, - InductionDescriptor &D); + InductionDescriptor &D, + const SCEV *Expr = nullptr); + + /// Returns true if \p Phi is an induction, in the context associated with + /// the run-time predicate of PSE. If \p Assume is true, this can add further + /// SCEV predicates to \p PSE in order to prove that \p Phi is an induction. + /// If \p Phi is an induction, \p D will contain the data describing this + /// induction. + static bool isInductionPHI(PHINode *Phi, PredicatedScalarEvolution &PSE, + InductionDescriptor &D, bool Assume = false); private: /// Private constructor - used by \c isInductionPHI. - InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step); + InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step); /// Start value. TrackingVH<Value> StartValue; /// Induction kind. InductionKind IK; /// Step value. - ConstantInt *StepValue; + const SCEV *Step; }; BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA); -/// \brief Simplify each loop in a loop nest recursively. +/// Ensures LCSSA form for every instruction from the Worklist in the scope of +/// innermost containing loop. +/// +/// For the given instruction which have uses outside of the loop, an LCSSA PHI +/// node is inserted and the uses outside the loop are rewritten to use this +/// node. +/// +/// LoopInfo and DominatorTree are required and, since the routine makes no +/// changes to CFG, preserved. /// -/// This takes a potentially un-simplified loop L (and its children) and turns -/// it into a simplified loop nest with preheaders and single backedges. It will -/// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. -bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, - AssumptionCache *AC, bool PreserveLCSSA); +/// Returns true if any modifications are made. +bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, + DominatorTree &DT, LoopInfo &LI); /// \brief Put loop into LCSSA form. /// @@ -318,8 +348,7 @@ bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, /// If ScalarEvolution is passed in, it will be preserved. /// /// Returns true if any modifications are made to the loop. -bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, - ScalarEvolution *SE); +bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); /// \brief Put a loop nest into LCSSA form. /// @@ -343,7 +372,7 @@ bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, /// It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LoopSafetyInfo *); /// \brief Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -354,7 +383,7 @@ bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, /// loop and loop safety information as arguments. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LoopSafetyInfo *); /// \brief Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over @@ -363,20 +392,45 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop, /// AliasSet information for all instructions of the loop and loop safety /// information as arguments. It returns changed status. -bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &, - SmallVectorImpl<Instruction*> &, +bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &, + SmallVectorImpl<Instruction *> &, PredIteratorCache &, LoopInfo *, - DominatorTree *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + DominatorTree *, const TargetLibraryInfo *, + Loop *, AliasSetTracker *, LoopSafetyInfo *); /// \brief Computes safety information for a loop /// checks loop body & header for the possibility of may throw -/// exception, it takes LICMSafetyInfo and loop as argument. -/// Updates safety information in LICMSafetyInfo argument. -void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *); +/// exception, it takes LoopSafetyInfo and loop as argument. +/// Updates safety information in LoopSafetyInfo argument. +void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); + +/// Returns true if the instruction in a loop is guaranteed to execute at least +/// once. +bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, + const Loop *CurLoop, + const LoopSafetyInfo *SafetyInfo); /// \brief Returns the instructions that use values defined in the loop. SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); + +/// \brief Find string metadata for loop +/// +/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an +/// operand or null otherwise. If the string metadata is not found return +/// Optional's not-a-value. +Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop, + StringRef Name); + +/// \brief Set input string into loop metadata by keeping other values intact. +void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, + unsigned V = 0); + +/// Helper to consistently add the set of standard passes to a loop pass's \c +/// AnalysisUsage. +/// +/// All loop passes should call this as part of implementing their \c +/// getAnalysisUsage. +void getLoopAnalysisUsage(AnalysisUsage &AU); } #endif diff --git a/include/llvm/Transforms/Utils/LoopVersioning.h b/include/llvm/Transforms/Utils/LoopVersioning.h index 3b70594e0b63..0d345a972e10 100644 --- a/include/llvm/Transforms/Utils/LoopVersioning.h +++ b/include/llvm/Transforms/Utils/LoopVersioning.h @@ -73,11 +73,30 @@ public: /// \brief Sets the runtime alias checks for versioning the loop. void setAliasChecks( - const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); + SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); /// \brief Sets the runtime SCEV checks for versioning the loop. void setSCEVChecks(SCEVUnionPredicate Check); + /// \brief Annotate memory instructions in the versioned loop with no-alias + /// metadata based on the memchecks issued. + /// + /// This is just wrapper that calls prepareNoAliasMetadata and + /// annotateInstWithNoAlias on the instructions of the versioned loop. + void annotateLoopWithNoAlias(); + + /// \brief Set up the aliasing scopes based on the memchecks. This needs to + /// be called before the first call to annotateInstWithNoAlias. + void prepareNoAliasMetadata(); + + /// \brief Add the noalias annotations to \p VersionedInst. + /// + /// \p OrigInst is the instruction corresponding to \p VersionedInst in the + /// original loop. Initialize the aliasing scopes with + /// prepareNoAliasMetadata once before this can be called. + void annotateInstWithNoAlias(Instruction *VersionedInst, + const Instruction *OrigInst); + private: /// \brief Adds the necessary PHI nodes for the versioned loops based on the /// loop-defined values used outside of the loop. @@ -86,6 +105,12 @@ private: /// that are used outside the loop. void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside); + /// \brief Add the noalias annotations to \p I. Initialize the aliasing + /// scopes with prepareNoAliasMetadata once before this can be called. + void annotateInstWithNoAlias(Instruction *I) { + annotateInstWithNoAlias(I, I); + } + /// \brief The original loop. This becomes the "versioned" one. I.e., /// control flows here if pointers in the loop don't alias. Loop *VersionedLoop; @@ -103,6 +128,19 @@ private: /// \brief The set of SCEV checks that we are versioning for. SCEVUnionPredicate Preds; + /// \brief Maps a pointer to the pointer checking group that the pointer + /// belongs to. + DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *> + PtrToGroup; + + /// \brief The alias scope corresponding to a pointer checking group. + DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> + GroupToScope; + + /// \brief The list of alias scopes that a pointer checking group can't alias. + DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> + GroupToNonAliasingScopeList; + /// \brief Analyses used. const LoopAccessInfo &LAI; LoopInfo *LI; diff --git a/include/llvm/Transforms/Utils/Mem2Reg.h b/include/llvm/Transforms/Utils/Mem2Reg.h new file mode 100644 index 000000000000..f3c80edf544d --- /dev/null +++ b/include/llvm/Transforms/Utils/Mem2Reg.h @@ -0,0 +1,28 @@ +//===- Mem2Reg.h - The -mem2reg pass, a wrapper around the Utils lib ------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass is a simple pass wrapper around the PromoteMemToReg function call +// exposed by the Utils library. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_MEM2REG_H +#define LLVM_TRANSFORMS_UTILS_MEM2REG_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class PromotePass : public PassInfoMixin<PromotePass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_UTILS_MEM2REG_H
\ No newline at end of file diff --git a/include/llvm/Transforms/Utils/MemorySSA.h b/include/llvm/Transforms/Utils/MemorySSA.h new file mode 100644 index 000000000000..befc34cb80fc --- /dev/null +++ b/include/llvm/Transforms/Utils/MemorySSA.h @@ -0,0 +1,949 @@ +//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// \file +// \brief This file exposes an interface to building/using memory SSA to +// walk memory instructions using a use/def graph. +// +// Memory SSA class builds an SSA form that links together memory access +// instructions such as loads, stores, atomics, and calls. Additionally, it does +// a trivial form of "heap versioning" Every time the memory state changes in +// the program, we generate a new heap version. It generates MemoryDef/Uses/Phis +// that are overlayed on top of the existing instructions. +// +// As a trivial example, +// define i32 @main() #0 { +// entry: +// %call = call noalias i8* @_Znwm(i64 4) #2 +// %0 = bitcast i8* %call to i32* +// %call1 = call noalias i8* @_Znwm(i64 4) #2 +// %1 = bitcast i8* %call1 to i32* +// store i32 5, i32* %0, align 4 +// store i32 7, i32* %1, align 4 +// %2 = load i32* %0, align 4 +// %3 = load i32* %1, align 4 +// %add = add nsw i32 %2, %3 +// ret i32 %add +// } +// +// Will become +// define i32 @main() #0 { +// entry: +// ; 1 = MemoryDef(0) +// %call = call noalias i8* @_Znwm(i64 4) #3 +// %2 = bitcast i8* %call to i32* +// ; 2 = MemoryDef(1) +// %call1 = call noalias i8* @_Znwm(i64 4) #3 +// %4 = bitcast i8* %call1 to i32* +// ; 3 = MemoryDef(2) +// store i32 5, i32* %2, align 4 +// ; 4 = MemoryDef(3) +// store i32 7, i32* %4, align 4 +// ; MemoryUse(3) +// %7 = load i32* %2, align 4 +// ; MemoryUse(4) +// %8 = load i32* %4, align 4 +// %add = add nsw i32 %7, %8 +// ret i32 %add +// } +// +// Given this form, all the stores that could ever effect the load at %8 can be +// gotten by using the MemoryUse associated with it, and walking from use to def +// until you hit the top of the function. +// +// Each def also has a list of users associated with it, so you can walk from +// both def to users, and users to defs. Note that we disambiguate MemoryUses, +// but not the RHS of MemoryDefs. You can see this above at %7, which would +// otherwise be a MemoryUse(4). Being disambiguated means that for a given +// store, all the MemoryUses on its use lists are may-aliases of that store (but +// the MemoryDefs on its use list may not be). +// +// MemoryDefs are not disambiguated because it would require multiple reaching +// definitions, which would require multiple phis, and multiple memoryaccesses +// per instruction. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H +#define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/iterator.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/OperandTraits.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" +#include "llvm/PassAnalysisSupport.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <iterator> +#include <memory> +#include <utility> + +namespace llvm { + +class DominatorTree; +class Function; +class Instruction; +class MemoryAccess; +class LLVMContext; +class raw_ostream; + +template <class T> class memoryaccess_def_iterator_base; +using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>; +using const_memoryaccess_def_iterator = + memoryaccess_def_iterator_base<const MemoryAccess>; + +// \brief The base for all memory accesses. All memory accesses in a block are +// linked together using an intrusive list. +class MemoryAccess : public User, public ilist_node<MemoryAccess> { + void *operator new(size_t, unsigned) = delete; + void *operator new(size_t) = delete; + +public: + // Methods for support type inquiry through isa, cast, and + // dyn_cast + static inline bool classof(const MemoryAccess *) { return true; } + static inline bool classof(const Value *V) { + unsigned ID = V->getValueID(); + return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal; + } + + ~MemoryAccess() override; + + BasicBlock *getBlock() const { return Block; } + + virtual void print(raw_ostream &OS) const = 0; + virtual void dump() const; + + /// \brief The user iterators for a memory access + typedef user_iterator iterator; + typedef const_user_iterator const_iterator; + + /// \brief This iterator walks over all of the defs in a given + /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For + /// MemoryUse/MemoryDef, this walks the defining access. + memoryaccess_def_iterator defs_begin(); + const_memoryaccess_def_iterator defs_begin() const; + memoryaccess_def_iterator defs_end(); + const_memoryaccess_def_iterator defs_end() const; + +protected: + friend class MemorySSA; + friend class MemoryUseOrDef; + friend class MemoryUse; + friend class MemoryDef; + friend class MemoryPhi; + + /// \brief Used internally to give IDs to MemoryAccesses for printing + virtual unsigned getID() const = 0; + + MemoryAccess(LLVMContext &C, unsigned Vty, BasicBlock *BB, + unsigned NumOperands) + : User(Type::getVoidTy(C), Vty, nullptr, NumOperands), Block(BB) {} + +private: + MemoryAccess(const MemoryAccess &); + void operator=(const MemoryAccess &); + BasicBlock *Block; +}; + +template <> +struct ilist_traits<MemoryAccess> : public ilist_default_traits<MemoryAccess> { + /// See details of the instruction class for why this trick works + // FIXME: This downcast is UB. See llvm.org/PR26753. + LLVM_NO_SANITIZE("object-size") + MemoryAccess *createSentinel() const { + return static_cast<MemoryAccess *>(&Sentinel); + } + + static void destroySentinel(MemoryAccess *) {} + + MemoryAccess *provideInitialHead() const { return createSentinel(); } + MemoryAccess *ensureHead(MemoryAccess *) const { return createSentinel(); } + static void noteHead(MemoryAccess *, MemoryAccess *) {} + +private: + mutable ilist_half_node<MemoryAccess> Sentinel; +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) { + MA.print(OS); + return OS; +} + +/// \brief Class that has the common methods + fields of memory uses/defs. It's +/// a little awkward to have, but there are many cases where we want either a +/// use or def, and there are many cases where uses are needed (defs aren't +/// acceptable), and vice-versa. +/// +/// This class should never be instantiated directly; make a MemoryUse or +/// MemoryDef instead. +class MemoryUseOrDef : public MemoryAccess { + void *operator new(size_t, unsigned) = delete; + void *operator new(size_t) = delete; + +public: + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + /// \brief Get the instruction that this MemoryUse represents. + Instruction *getMemoryInst() const { return MemoryInst; } + + /// \brief Get the access that produces the memory state used by this Use. + MemoryAccess *getDefiningAccess() const { return getOperand(0); } + + static inline bool classof(const MemoryUseOrDef *) { return true; } + static inline bool classof(const Value *MA) { + return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal; + } + +protected: + friend class MemorySSA; + + MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty, + Instruction *MI, BasicBlock *BB) + : MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) { + setDefiningAccess(DMA); + } + + void setDefiningAccess(MemoryAccess *DMA) { setOperand(0, DMA); } + +private: + Instruction *MemoryInst; +}; + +template <> +struct OperandTraits<MemoryUseOrDef> + : public FixedNumOperandTraits<MemoryUseOrDef, 1> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess) + +/// \brief Represents read-only accesses to memory +/// +/// In particular, the set of Instructions that will be represented by +/// MemoryUse's is exactly the set of Instructions for which +/// AliasAnalysis::getModRefInfo returns "Ref". +class MemoryUse final : public MemoryUseOrDef { + void *operator new(size_t, unsigned) = delete; + +public: + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + // allocate space for exactly one operand + void *operator new(size_t s) { return User::operator new(s, 1); } + + MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB) + : MemoryUseOrDef(C, DMA, MemoryUseVal, MI, BB) {} + + static inline bool classof(const MemoryUse *) { return true; } + static inline bool classof(const Value *MA) { + return MA->getValueID() == MemoryUseVal; + } + + void print(raw_ostream &OS) const override; + +protected: + friend class MemorySSA; + + unsigned getID() const override { + llvm_unreachable("MemoryUses do not have IDs"); + } +}; + +template <> +struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess) + +/// \brief Represents a read-write access to memory, whether it is a must-alias, +/// or a may-alias. +/// +/// In particular, the set of Instructions that will be represented by +/// MemoryDef's is exactly the set of Instructions for which +/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef". +/// Note that, in order to provide def-def chains, all defs also have a use +/// associated with them. This use points to the nearest reaching +/// MemoryDef/MemoryPhi. +class MemoryDef final : public MemoryUseOrDef { + void *operator new(size_t, unsigned) = delete; + +public: + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + // allocate space for exactly one operand + void *operator new(size_t s) { return User::operator new(s, 1); } + + MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, + unsigned Ver) + : MemoryUseOrDef(C, DMA, MemoryDefVal, MI, BB), ID(Ver) {} + + static inline bool classof(const MemoryDef *) { return true; } + static inline bool classof(const Value *MA) { + return MA->getValueID() == MemoryDefVal; + } + + void print(raw_ostream &OS) const override; + +protected: + friend class MemorySSA; + + // For debugging only. This gets used to give memory accesses pretty numbers + // when printing them out + unsigned getID() const override { return ID; } + +private: + const unsigned ID; +}; + +template <> +struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 1> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess) + +/// \brief Represents phi nodes for memory accesses. +/// +/// These have the same semantic as regular phi nodes, with the exception that +/// only one phi will ever exist in a given basic block. +/// Guaranteeing one phi per block means guaranteeing there is only ever one +/// valid reaching MemoryDef/MemoryPHI along each path to the phi node. +/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or +/// a MemoryPhi's operands. +/// That is, given +/// if (a) { +/// store %a +/// store %b +/// } +/// it *must* be transformed into +/// if (a) { +/// 1 = MemoryDef(liveOnEntry) +/// store %a +/// 2 = MemoryDef(1) +/// store %b +/// } +/// and *not* +/// if (a) { +/// 1 = MemoryDef(liveOnEntry) +/// store %a +/// 2 = MemoryDef(liveOnEntry) +/// store %b +/// } +/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the +/// end of the branch, and if there are not two phi nodes, one will be +/// disconnected completely from the SSA graph below that point. +/// Because MemoryUse's do not generate new definitions, they do not have this +/// issue. +class MemoryPhi final : public MemoryAccess { + void *operator new(size_t, unsigned) = delete; + // allocate space for exactly zero operands + void *operator new(size_t s) { return User::operator new(s); } + +public: + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0) + : MemoryAccess(C, MemoryPhiVal, BB, 0), ID(Ver), ReservedSpace(NumPreds) { + allocHungoffUses(ReservedSpace); + } + + // Block iterator interface. This provides access to the list of incoming + // basic blocks, which parallels the list of incoming values. + typedef BasicBlock **block_iterator; + typedef BasicBlock *const *const_block_iterator; + + block_iterator block_begin() { + auto *Ref = reinterpret_cast<Use::UserRef *>(op_begin() + ReservedSpace); + return reinterpret_cast<block_iterator>(Ref + 1); + } + + const_block_iterator block_begin() const { + const auto *Ref = + reinterpret_cast<const Use::UserRef *>(op_begin() + ReservedSpace); + return reinterpret_cast<const_block_iterator>(Ref + 1); + } + + block_iterator block_end() { return block_begin() + getNumOperands(); } + + const_block_iterator block_end() const { + return block_begin() + getNumOperands(); + } + + op_range incoming_values() { return operands(); } + + const_op_range incoming_values() const { return operands(); } + + /// \brief Return the number of incoming edges + unsigned getNumIncomingValues() const { return getNumOperands(); } + + /// \brief Return incoming value number x + MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); } + void setIncomingValue(unsigned I, MemoryAccess *V) { + assert(V && "PHI node got a null value!"); + setOperand(I, V); + } + static unsigned getOperandNumForIncomingValue(unsigned I) { return I; } + static unsigned getIncomingValueNumForOperand(unsigned I) { return I; } + + /// \brief Return incoming basic block number @p i. + BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; } + + /// \brief Return incoming basic block corresponding + /// to an operand of the PHI. + BasicBlock *getIncomingBlock(const Use &U) const { + assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?"); + return getIncomingBlock(unsigned(&U - op_begin())); + } + + /// \brief Return incoming basic block corresponding + /// to value use iterator. + BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const { + return getIncomingBlock(I.getUse()); + } + + void setIncomingBlock(unsigned I, BasicBlock *BB) { + assert(BB && "PHI node got a null basic block!"); + block_begin()[I] = BB; + } + + /// \brief Add an incoming value to the end of the PHI list + void addIncoming(MemoryAccess *V, BasicBlock *BB) { + if (getNumOperands() == ReservedSpace) + growOperands(); // Get more space! + // Initialize some new operands. + setNumHungOffUseOperands(getNumOperands() + 1); + setIncomingValue(getNumOperands() - 1, V); + setIncomingBlock(getNumOperands() - 1, BB); + } + + /// \brief Return the first index of the specified basic + /// block in the value list for this PHI. Returns -1 if no instance. + int getBasicBlockIndex(const BasicBlock *BB) const { + for (unsigned I = 0, E = getNumOperands(); I != E; ++I) + if (block_begin()[I] == BB) + return I; + return -1; + } + + Value *getIncomingValueForBlock(const BasicBlock *BB) const { + int Idx = getBasicBlockIndex(BB); + assert(Idx >= 0 && "Invalid basic block argument!"); + return getIncomingValue(Idx); + } + + static inline bool classof(const MemoryPhi *) { return true; } + static inline bool classof(const Value *V) { + return V->getValueID() == MemoryPhiVal; + } + + void print(raw_ostream &OS) const override; + +protected: + friend class MemorySSA; + /// \brief this is more complicated than the generic + /// User::allocHungoffUses, because we have to allocate Uses for the incoming + /// values and pointers to the incoming blocks, all in one allocation. + void allocHungoffUses(unsigned N) { + User::allocHungoffUses(N, /* IsPhi */ true); + } + + /// For debugging only. This gets used to give memory accesses pretty numbers + /// when printing them out + unsigned getID() const final { return ID; } + +private: + // For debugging only + const unsigned ID; + unsigned ReservedSpace; + + /// \brief This grows the operand list in response to a push_back style of + /// operation. This grows the number of ops by 1.5 times. + void growOperands() { + unsigned E = getNumOperands(); + // 2 op PHI nodes are VERY common, so reserve at least enough for that. + ReservedSpace = std::max(E + E / 2, 2u); + growHungoffUses(ReservedSpace, /* IsPhi */ true); + } +}; + +template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess) + +class MemorySSAWalker; + +/// \brief Encapsulates MemorySSA, including all data associated with memory +/// accesses. +class MemorySSA { +public: + MemorySSA(Function &, AliasAnalysis *, DominatorTree *); + MemorySSA(MemorySSA &&); + ~MemorySSA(); + + MemorySSAWalker *getWalker(); + + /// \brief Given a memory Mod/Ref'ing instruction, get the MemorySSA + /// access associated with it. If passed a basic block gets the memory phi + /// node that exists for that block, if there is one. Otherwise, this will get + /// a MemoryUseOrDef. + MemoryAccess *getMemoryAccess(const Value *) const; + MemoryPhi *getMemoryAccess(const BasicBlock *BB) const; + + void dump() const; + void print(raw_ostream &) const; + + /// \brief Return true if \p MA represents the live on entry value + /// + /// Loads and stores from pointer arguments and other global values may be + /// defined by memory operations that do not occur in the current function, so + /// they may be live on entry to the function. MemorySSA represents such + /// memory state by the live on entry definition, which is guaranteed to occur + /// before any other memory access in the function. + inline bool isLiveOnEntryDef(const MemoryAccess *MA) const { + return MA == LiveOnEntryDef.get(); + } + + inline MemoryAccess *getLiveOnEntryDef() const { + return LiveOnEntryDef.get(); + } + + using AccessList = iplist<MemoryAccess>; + + /// \brief Return the list of MemoryAccess's for a given basic block. + /// + /// This list is not modifiable by the user. + const AccessList *getBlockAccesses(const BasicBlock *BB) const { + auto It = PerBlockAccesses.find(BB); + return It == PerBlockAccesses.end() ? nullptr : It->second.get(); + } + + /// \brief Create an empty MemoryPhi in MemorySSA + MemoryPhi *createMemoryPhi(BasicBlock *BB); + + enum InsertionPlace { Beginning, End }; + + /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block, + /// with a specified clobbering definition. + /// + /// Returns the new MemoryAccess. + /// This should be called when a memory instruction is created that is being + /// used to replace an existing memory instruction. It will *not* create PHI + /// nodes, or verify the clobbering definition. The insertion place is used + /// solely to determine where in the memoryssa access lists the instruction + /// will be placed. The caller is expected to keep ordering the same as + /// instructions. + /// It will return the new MemoryAccess. + MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, + const BasicBlock *BB, + InsertionPlace Point); + /// \brief Create a MemoryAccess in MemorySSA before or after an existing + /// MemoryAccess. + /// + /// Returns the new MemoryAccess. + /// This should be called when a memory instruction is created that is being + /// used to replace an existing memory instruction. It will *not* create PHI + /// nodes, or verify the clobbering definition. The clobbering definition + /// must be non-null. + MemoryAccess *createMemoryAccessBefore(Instruction *I, + MemoryAccess *Definition, + MemoryAccess *InsertPt); + MemoryAccess *createMemoryAccessAfter(Instruction *I, + MemoryAccess *Definition, + MemoryAccess *InsertPt); + + /// \brief Remove a MemoryAccess from MemorySSA, including updating all + /// definitions and uses. + /// This should be called when a memory instruction that has a MemoryAccess + /// associated with it is erased from the program. For example, if a store or + /// load is simply erased (not replaced), removeMemoryAccess should be called + /// on the MemoryAccess for that store/load. + void removeMemoryAccess(MemoryAccess *); + + /// \brief Given two memory accesses in the same basic block, determine + /// whether MemoryAccess \p A dominates MemoryAccess \p B. + bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const; + + /// \brief Verify that MemorySSA is self consistent (IE definitions dominate + /// all uses, uses appear in the right places). This is used by unit tests. + void verifyMemorySSA() const; + +protected: + // Used by Memory SSA annotater, dumpers, and wrapper pass + friend class MemorySSAAnnotatedWriter; + friend class MemorySSAPrinterLegacyPass; + void verifyDefUses(Function &F) const; + void verifyDomination(Function &F) const; + void verifyOrdering(Function &F) const; + +private: + class CachingWalker; + void buildMemorySSA(); + void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const; + using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>; + + void + determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks); + void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels); + void markUnreachableAsLiveOnEntry(BasicBlock *BB); + bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const; + MemoryUseOrDef *createNewAccess(Instruction *); + MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); + MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); + void removeFromLookups(MemoryAccess *); + + MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *); + void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, + SmallPtrSet<BasicBlock *, 16> &Visited); + AccessList *getOrCreateAccessList(const BasicBlock *); + AliasAnalysis *AA; + DominatorTree *DT; + Function &F; + + // Memory SSA mappings + DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess; + AccessMap PerBlockAccesses; + std::unique_ptr<MemoryAccess> LiveOnEntryDef; + + // Memory SSA building info + std::unique_ptr<CachingWalker> Walker; + unsigned NextID; +}; + +// This pass does eager building and then printing of MemorySSA. It is used by +// the tests to be able to build, dump, and verify Memory SSA. +class MemorySSAPrinterLegacyPass : public FunctionPass { +public: + MemorySSAPrinterLegacyPass(); + + static char ID; + bool runOnFunction(Function &) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +/// An analysis that produces \c MemorySSA for a function. +/// +class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> { + friend AnalysisInfoMixin<MemorySSAAnalysis>; + static char PassID; + +public: + typedef MemorySSA Result; + + MemorySSA run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Printer pass for \c MemorySSA. +class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> { + raw_ostream &OS; + +public: + explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Verifier pass for \c MemorySSA. +struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> { + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Legacy analysis pass which computes \c MemorySSA. +class MemorySSAWrapperPass : public FunctionPass { +public: + MemorySSAWrapperPass(); + + static char ID; + bool runOnFunction(Function &) override; + void releaseMemory() override; + MemorySSA &getMSSA() { return *MSSA; } + const MemorySSA &getMSSA() const { return *MSSA; } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + void verifyAnalysis() const override; + void print(raw_ostream &OS, const Module *M = nullptr) const override; + +private: + std::unique_ptr<MemorySSA> MSSA; +}; + +/// \brief This is the generic walker interface for walkers of MemorySSA. +/// Walkers are used to be able to further disambiguate the def-use chains +/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives +/// you. +/// In particular, while the def-use chains provide basic information, and are +/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a +/// MemoryUse as AliasAnalysis considers it, a user mant want better or other +/// information. In particular, they may want to use SCEV info to further +/// disambiguate memory accesses, or they may want the nearest dominating +/// may-aliasing MemoryDef for a call or a store. This API enables a +/// standardized interface to getting and using that info. +class MemorySSAWalker { +public: + MemorySSAWalker(MemorySSA *); + virtual ~MemorySSAWalker() {} + + using MemoryAccessSet = SmallVector<MemoryAccess *, 8>; + + /// \brief Given a memory Mod/Ref/ModRef'ing instruction, calling this + /// will give you the nearest dominating MemoryAccess that Mod's the location + /// the instruction accesses (by skipping any def which AA can prove does not + /// alias the location(s) accessed by the instruction given). + /// + /// Note that this will return a single access, and it must dominate the + /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction, + /// this will return the MemoryPhi, not the operand. This means that + /// given: + /// if (a) { + /// 1 = MemoryDef(liveOnEntry) + /// store %a + /// } else { + /// 2 = MemoryDef(liveOnEntry) + /// store %b + /// } + /// 3 = MemoryPhi(2, 1) + /// MemoryUse(3) + /// load %a + /// + /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef + /// in the if (a) branch. + virtual MemoryAccess *getClobberingMemoryAccess(const Instruction *) = 0; + + /// \brief Given a potentially clobbering memory access and a new location, + /// calling this will give you the nearest dominating clobbering MemoryAccess + /// (by skipping non-aliasing def links). + /// + /// This version of the function is mainly used to disambiguate phi translated + /// pointers, where the value of a pointer may have changed from the initial + /// memory access. Note that this expects to be handed either a MemoryUse, + /// or an already potentially clobbering access. Unlike the above API, if + /// given a MemoryDef that clobbers the pointer as the starting access, it + /// will return that MemoryDef, whereas the above would return the clobber + /// starting from the use side of the memory def. + virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + MemoryLocation &) = 0; + + /// \brief Given a memory access, invalidate anything this walker knows about + /// that access. + /// This API is used by walkers that store information to perform basic cache + /// invalidation. This will be called by MemorySSA at appropriate times for + /// the walker it uses or returns. + virtual void invalidateInfo(MemoryAccess *) {} + +protected: + friend class MemorySSA; // For updating MSSA pointer in MemorySSA move + // constructor. + MemorySSA *MSSA; +}; + +/// \brief A MemorySSAWalker that does no alias queries, or anything else. It +/// simply returns the links as they were constructed by the builder. +class DoNothingMemorySSAWalker final : public MemorySSAWalker { +public: + MemoryAccess *getClobberingMemoryAccess(const Instruction *) override; + MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + MemoryLocation &) override; +}; + +using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>; +using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>; + +/// \brief Iterator base class used to implement const and non-const iterators +/// over the defining accesses of a MemoryAccess. +template <class T> +class memoryaccess_def_iterator_base + : public iterator_facade_base<memoryaccess_def_iterator_base<T>, + std::forward_iterator_tag, T, ptrdiff_t, T *, + T *> { + using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base; + +public: + memoryaccess_def_iterator_base(T *Start) : Access(Start), ArgNo(0) {} + memoryaccess_def_iterator_base() : Access(nullptr), ArgNo(0) {} + bool operator==(const memoryaccess_def_iterator_base &Other) const { + return Access == Other.Access && (!Access || ArgNo == Other.ArgNo); + } + + // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the + // block from the operand in constant time (In a PHINode, the uselist has + // both, so it's just subtraction). We provide it as part of the + // iterator to avoid callers having to linear walk to get the block. + // If the operation becomes constant time on MemoryPHI's, this bit of + // abstraction breaking should be removed. + BasicBlock *getPhiArgBlock() const { + MemoryPhi *MP = dyn_cast<MemoryPhi>(Access); + assert(MP && "Tried to get phi arg block when not iterating over a PHI"); + return MP->getIncomingBlock(ArgNo); + } + typename BaseT::iterator::pointer operator*() const { + assert(Access && "Tried to access past the end of our iterator"); + // Go to the first argument for phis, and the defining access for everything + // else. + if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) + return MP->getIncomingValue(ArgNo); + return cast<MemoryUseOrDef>(Access)->getDefiningAccess(); + } + using BaseT::operator++; + memoryaccess_def_iterator &operator++() { + assert(Access && "Hit end of iterator"); + if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) { + if (++ArgNo >= MP->getNumIncomingValues()) { + ArgNo = 0; + Access = nullptr; + } + } else { + Access = nullptr; + } + return *this; + } + +private: + T *Access; + unsigned ArgNo; +}; + +inline memoryaccess_def_iterator MemoryAccess::defs_begin() { + return memoryaccess_def_iterator(this); +} + +inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const { + return const_memoryaccess_def_iterator(this); +} + +inline memoryaccess_def_iterator MemoryAccess::defs_end() { + return memoryaccess_def_iterator(); +} + +inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const { + return const_memoryaccess_def_iterator(); +} + +/// \brief GraphTraits for a MemoryAccess, which walks defs in the normal case, +/// and uses in the inverse case. +template <> struct GraphTraits<MemoryAccess *> { + using NodeType = MemoryAccess; + using ChildIteratorType = memoryaccess_def_iterator; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->defs_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->defs_end(); + } +}; + +template <> struct GraphTraits<Inverse<MemoryAccess *>> { + using NodeType = MemoryAccess; + using ChildIteratorType = MemoryAccess::iterator; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->user_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->user_end(); + } +}; + +/// \brief Provide an iterator that walks defs, giving both the memory access, +/// and the current pointer location, updating the pointer location as it +/// changes due to phi node translation. +/// +/// This iterator, while somewhat specialized, is what most clients actually +/// want when walking upwards through MemorySSA def chains. It takes a pair of +/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the +/// memory location through phi nodes for the user. +class upward_defs_iterator + : public iterator_facade_base<upward_defs_iterator, + std::forward_iterator_tag, + const MemoryAccessPair> { + using BaseT = upward_defs_iterator::iterator_facade_base; + +public: + upward_defs_iterator(const MemoryAccessPair &Info) + : DefIterator(Info.first), Location(Info.second), + OriginalAccess(Info.first) { + CurrentPair.first = nullptr; + + WalkingPhi = Info.first && isa<MemoryPhi>(Info.first); + fillInCurrentPair(); + } + + upward_defs_iterator() + : DefIterator(), Location(), OriginalAccess(), WalkingPhi(false) { + CurrentPair.first = nullptr; + } + + bool operator==(const upward_defs_iterator &Other) const { + return DefIterator == Other.DefIterator; + } + + BaseT::iterator::reference operator*() const { + assert(DefIterator != OriginalAccess->defs_end() && + "Tried to access past the end of our iterator"); + return CurrentPair; + } + + using BaseT::operator++; + upward_defs_iterator &operator++() { + assert(DefIterator != OriginalAccess->defs_end() && + "Tried to access past the end of the iterator"); + ++DefIterator; + if (DefIterator != OriginalAccess->defs_end()) + fillInCurrentPair(); + return *this; + } + + BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); } + +private: + void fillInCurrentPair() { + CurrentPair.first = *DefIterator; + if (WalkingPhi && Location.Ptr) { + PHITransAddr Translator( + const_cast<Value *>(Location.Ptr), + OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr); + if (!Translator.PHITranslateValue(OriginalAccess->getBlock(), + DefIterator.getPhiArgBlock(), nullptr, + false)) + if (Translator.getAddr() != Location.Ptr) { + CurrentPair.second = Location.getWithNewPtr(Translator.getAddr()); + return; + } + } + CurrentPair.second = Location; + } + + MemoryAccessPair CurrentPair; + memoryaccess_def_iterator DefIterator; + MemoryLocation Location; + MemoryAccess *OriginalAccess; + bool WalkingPhi; +}; + +inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) { + return upward_defs_iterator(Pair); +} + +inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); } + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_MEMORYSSA_H diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h index 0f23d34de5db..2eb2b1363b0b 100644 --- a/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/include/llvm/Transforms/Utils/ModuleUtils.h @@ -14,12 +14,12 @@ #ifndef LLVM_TRANSFORMS_UTILS_MODULEUTILS_H #define LLVM_TRANSFORMS_UTILS_MODULEUTILS_H -#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringRef.h" #include <utility> // for std::pair namespace llvm { +template <typename T> class ArrayRef; class Module; class Function; class GlobalValue; @@ -28,22 +28,17 @@ class Constant; class StringRef; class Value; class Type; -template <class PtrType> class SmallPtrSetImpl; /// Append F to the list of global ctors of module M with the given Priority. /// This wraps the function in the appropriate structure and stores it along /// side other global constructors. For details see /// http://llvm.org/docs/LangRef.html#intg_global_ctors -void appendToGlobalCtors(Module &M, Function *F, int Priority); +void appendToGlobalCtors(Module &M, Function *F, int Priority, + Constant *Data = nullptr); /// Same as appendToGlobalCtors(), but for global dtors. -void appendToGlobalDtors(Module &M, Function *F, int Priority); - -/// \brief Given "llvm.used" or "llvm.compiler.used" as a global name, collect -/// the initializer elements of that global in Set and return the global itself. -GlobalVariable *collectUsedGlobalVariables(Module &M, - SmallPtrSetImpl<GlobalValue *> &Set, - bool CompilerUsed); +void appendToGlobalDtors(Module &M, Function *F, int Priority, + Constant *Data = nullptr); // Validate the result of Module::getOrInsertFunction called for an interface // function of given sanitizer. If the instrumented module defines a function @@ -59,6 +54,11 @@ std::pair<Function *, Function *> createSanitizerCtorAndInitFunctions( Module &M, StringRef CtorName, StringRef InitName, ArrayRef<Type *> InitArgTypes, ArrayRef<Value *> InitArgs, StringRef VersionCheckName = StringRef()); + +/// Rename all the anon functions in the module using a hash computed from +/// the list of public globals in the module. +bool nameUnamedFunctions(Module &M); + } // End llvm namespace #endif // LLVM_TRANSFORMS_UTILS_MODULEUTILS_H diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h index d0602bf47c92..b548072c413e 100644 --- a/include/llvm/Transforms/Utils/PromoteMemToReg.h +++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h @@ -15,10 +15,9 @@ #ifndef LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H #define LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H -#include "llvm/ADT/ArrayRef.h" - namespace llvm { +template <typename T> class ArrayRef; class AllocaInst; class DominatorTree; class AliasSetTracker; diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 1c7b2c587a36..9f98bac22dc9 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -14,7 +14,6 @@ #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H -#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/Compiler.h" @@ -22,8 +21,9 @@ namespace llvm { class BasicBlock; class Instruction; class LoadInst; - template<typename T> class SmallVectorImpl; - template<typename T> class SSAUpdaterTraits; + template <typename T> class ArrayRef; + template <typename T> class SmallVectorImpl; + template <typename T> class SSAUpdaterTraits; class PHINode; class Type; class Use; diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h index 425ecd3cfb5e..b5f4ac82b605 100644 --- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -17,6 +17,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" diff --git a/include/llvm/Transforms/Utils/SanitizerStats.h b/include/llvm/Transforms/Utils/SanitizerStats.h new file mode 100644 index 000000000000..d36e34258a3f --- /dev/null +++ b/include/llvm/Transforms/Utils/SanitizerStats.h @@ -0,0 +1,56 @@ +//===- SanitizerStats.h - Sanitizer statistics gathering -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Declares functions and data structures for sanitizer statistics gathering. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SANITIZERSTATS_H +#define LLVM_TRANSFORMS_UTILS_SANITIZERSTATS_H + +#include "llvm/IR/IRBuilder.h" + +namespace llvm { + +// Number of bits in data that are used for the sanitizer kind. Needs to match +// __sanitizer::kKindBits in compiler-rt/lib/stats/stats.h +enum { kSanitizerStatKindBits = 3 }; + +enum SanitizerStatKind { + SanStat_CFI_VCall, + SanStat_CFI_NVCall, + SanStat_CFI_DerivedCast, + SanStat_CFI_UnrelatedCast, + SanStat_CFI_ICall, +}; + +struct SanitizerStatReport { + SanitizerStatReport(Module *M); + + /// Generates code into B that increments a location-specific counter tagged + /// with the given sanitizer kind SK. + void create(IRBuilder<> &B, SanitizerStatKind SK); + + /// Finalize module stats array and add global constructor to register it. + void finish(); + +private: + Module *M; + GlobalVariable *ModuleStatsGV; + ArrayType *StatTy; + StructType *EmptyModuleStatsTy; + + std::vector<Constant *> Inits; + ArrayType *makeModuleStatsArrayTy(); + StructType *makeModuleStatsTy(); +}; + +} + +#endif diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index 3c55e64537c7..90438ee699fe 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -17,7 +17,6 @@ #define LLVM_TRANSFORMS_UTILS_SIMPLIFYINDVAR_H #include "llvm/IR/ValueHandle.h" -#include "llvm/Support/CommandLine.h" namespace llvm { @@ -34,24 +33,14 @@ class ScalarEvolution; class IVVisitor { protected: const DominatorTree *DT; - bool ShouldSplitOverflowIntrinsics; virtual void anchor(); public: - IVVisitor(): DT(nullptr), ShouldSplitOverflowIntrinsics(false) {} + IVVisitor() : DT(nullptr) {} virtual ~IVVisitor() {} const DominatorTree *getDomTree() const { return DT; } - - bool shouldSplitOverflowInstrinsics() const { - return ShouldSplitOverflowIntrinsics; - } - void setSplitOverflowIntrinsics() { - ShouldSplitOverflowIntrinsics = true; - assert(DT && "Splitting overflow intrinsics requires a DomTree."); - } - virtual void visitCast(CastInst *Cast) = 0; }; diff --git a/include/llvm/Transforms/Utils/SimplifyInstructions.h b/include/llvm/Transforms/Utils/SimplifyInstructions.h new file mode 100644 index 000000000000..ea491dc50587 --- /dev/null +++ b/include/llvm/Transforms/Utils/SimplifyInstructions.h @@ -0,0 +1,31 @@ +//===- SimplifyInstructions.h - Remove redundant instructions ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This is a utility pass used for testing the InstructionSimplify analysis. +// The analysis is applied to every instruction, and if it simplifies then the +// instruction is replaced by the simplification. If you are looking for a pass +// that performs serious instruction folding, use the instcombine pass instead. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H +#define LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// This pass removes redundant instructions. +class InstSimplifierPass : public PassInfoMixin<InstSimplifierPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h index fc34f49a1255..92ee24633950 100644 --- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -16,11 +16,11 @@ #define LLVM_TRANSFORMS_UTILS_SIMPLIFYLIBCALLS_H #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/IRBuilder.h" namespace llvm { +class StringRef; class Value; class CallInst; class DataLayout; @@ -154,7 +154,7 @@ private: // Helper methods Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B); - void classifyArgUse(Value *Val, BasicBlock *BB, bool IsFloat, + void classifyArgUse(Value *Val, Function *F, bool IsFloat, SmallVectorImpl<CallInst *> &SinCalls, SmallVectorImpl<CallInst *> &CosCalls, SmallVectorImpl<CallInst *> &SinCosCalls); diff --git a/include/llvm/Transforms/Utils/SplitModule.h b/include/llvm/Transforms/Utils/SplitModule.h index 7d896d1993d6..b7a3bcf4f86a 100644 --- a/include/llvm/Transforms/Utils/SplitModule.h +++ b/include/llvm/Transforms/Utils/SplitModule.h @@ -16,7 +16,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_SPLITMODULE_H #define LLVM_TRANSFORMS_UTILS_SPLITMODULE_H -#include <functional> +#include "llvm/ADT/STLExtras.h" #include <memory> namespace llvm { @@ -36,7 +36,8 @@ class StringRef; /// each partition. void SplitModule( std::unique_ptr<Module> M, unsigned N, - std::function<void(std::unique_ptr<Module> MPart)> ModuleCallback); + function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback, + bool PreserveLocals = false); } // End llvm namespace diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h index 710817cddf6a..4d370407591d 100644 --- a/include/llvm/Transforms/Utils/UnrollLoop.h +++ b/include/llvm/Transforms/Utils/UnrollLoop.h @@ -16,10 +16,10 @@ #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H -#include "llvm/ADT/StringRef.h" namespace llvm { +class StringRef; class AssumptionCache; class DominatorTree; class Loop; @@ -29,15 +29,16 @@ class MDNode; class Pass; class ScalarEvolution; -bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool AllowRuntime, - bool AllowExpensiveTripCount, unsigned TripMultiple, - LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, - AssumptionCache *AC, bool PreserveLCSSA); +bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force, + bool AllowRuntime, bool AllowExpensiveTripCount, + unsigned TripMultiple, LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); -bool UnrollRuntimeLoopProlog(Loop *L, unsigned Count, - bool AllowExpensiveTripCount, LoopInfo *LI, - ScalarEvolution *SE, DominatorTree *DT, - bool PreserveLCSSA); +bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, + bool AllowExpensiveTripCount, + bool UseEpilogRemainder, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + bool PreserveLCSSA); MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); } diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h index 469022f34c56..de649009612c 100644 --- a/include/llvm/Transforms/Utils/ValueMapper.h +++ b/include/llvm/Transforms/Utils/ValueMapper.h @@ -18,117 +18,255 @@ #include "llvm/IR/ValueMap.h" namespace llvm { - class Value; - class Instruction; - typedef ValueMap<const Value *, WeakVH> ValueToValueMapTy; - - /// ValueMapTypeRemapper - This is a class that can be implemented by clients - /// to remap types when cloning constants and instructions. - class ValueMapTypeRemapper { - virtual void anchor(); // Out of line method. - public: - virtual ~ValueMapTypeRemapper() {} - - /// remapType - The client should implement this method if they want to - /// remap types while mapping values. - virtual Type *remapType(Type *SrcTy) = 0; - }; - - /// ValueMaterializer - This is a class that can be implemented by clients - /// to materialize Values on demand. - class ValueMaterializer { - virtual void anchor(); // Out of line method. - - protected: - ~ValueMaterializer() = default; - ValueMaterializer() = default; - ValueMaterializer(const ValueMaterializer&) = default; - ValueMaterializer &operator=(const ValueMaterializer&) = default; - - public: - /// The client should implement this method if they want to generate a - /// mapped Value on demand. For example, if linking lazily. - virtual Value *materializeDeclFor(Value *V) = 0; - - /// If the data being mapped is recursive, the above function can map - /// just the declaration and this is called to compute the initializer. - /// It is called after the mapping is recorded, so it doesn't need to worry - /// about recursion. - virtual void materializeInitFor(GlobalValue *New, GlobalValue *Old); - - /// If the client needs to handle temporary metadata it must implement - /// these methods. - virtual Metadata *mapTemporaryMetadata(Metadata *MD) { return nullptr; } - virtual void replaceTemporaryMetadata(const Metadata *OrigMD, - Metadata *NewMD) {} - - /// The client should implement this method if some metadata need - /// not be mapped, for example DISubprogram metadata for functions not - /// linked into the destination module. - virtual bool isMetadataNeeded(Metadata *MD) { return true; } - }; - - /// RemapFlags - These are flags that the value mapping APIs allow. - enum RemapFlags { - RF_None = 0, - - /// RF_NoModuleLevelChanges - If this flag is set, the remapper knows that - /// only local values within a function (such as an instruction or argument) - /// are mapped, not global values like functions and global metadata. - RF_NoModuleLevelChanges = 1, - - /// RF_IgnoreMissingEntries - If this flag is set, the remapper ignores - /// entries that are not in the value map. If it is unset, it aborts if an - /// operand is asked to be remapped which doesn't exist in the mapping. - RF_IgnoreMissingEntries = 2, - - /// Instruct the remapper to move distinct metadata instead of duplicating - /// it when there are module-level changes. - RF_MoveDistinctMDs = 4, - - /// Any global values not in value map are mapped to null instead of - /// mapping to self. Illegal if RF_IgnoreMissingEntries is also set. - RF_NullMapMissingGlobalValues = 8, - - /// Set when there is still temporary metadata that must be handled, - /// such as when we are doing function importing and will materialize - /// and link metadata as a postpass. - RF_HaveUnmaterializedMetadata = 16, - }; - - static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { - return RemapFlags(unsigned(LHS)|unsigned(RHS)); - } - - Value *MapValue(const Value *V, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - Metadata *MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - /// MapMetadata - provide versions that preserve type safety for MDNodes. - MDNode *MapMetadata(const MDNode *MD, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - /// MapValue - provide versions that preserve type safety for Constants. - inline Constant *MapValue(const Constant *V, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr) { - return cast<Constant>(MapValue((const Value*)V, VM, Flags, TypeMapper, - Materializer)); - } + +class Value; +class Instruction; +typedef ValueMap<const Value *, WeakVH> ValueToValueMapTy; + +/// This is a class that can be implemented by clients to remap types when +/// cloning constants and instructions. +class ValueMapTypeRemapper { + virtual void anchor(); // Out of line method. +public: + virtual ~ValueMapTypeRemapper() {} + + /// The client should implement this method if they want to remap types while + /// mapping values. + virtual Type *remapType(Type *SrcTy) = 0; +}; + +/// This is a class that can be implemented by clients to materialize Values on +/// demand. +class ValueMaterializer { + virtual void anchor(); // Out of line method. + +protected: + ~ValueMaterializer() = default; + ValueMaterializer() = default; + ValueMaterializer(const ValueMaterializer &) = default; + ValueMaterializer &operator=(const ValueMaterializer &) = default; + +public: + /// This method can be implemented to generate a mapped Value on demand. For + /// example, if linking lazily. Returns null if the value is not materialized. + virtual Value *materialize(Value *V) = 0; +}; + +/// These are flags that the value mapping APIs allow. +enum RemapFlags { + RF_None = 0, + + /// If this flag is set, the remapper knows that only local values within a + /// function (such as an instruction or argument) are mapped, not global + /// values like functions and global metadata. + RF_NoModuleLevelChanges = 1, + + /// If this flag is set, the remapper ignores missing function-local entries + /// (Argument, Instruction, BasicBlock) that are not in the value map. If it + /// is unset, it aborts if an operand is asked to be remapped which doesn't + /// exist in the mapping. + /// + /// There are no such assertions in MapValue(), whose results are almost + /// unchanged by this flag. This flag mainly changes the assertion behaviour + /// in RemapInstruction(). + /// + /// Since an Instruction's metadata operands (even that point to SSA values) + /// aren't guaranteed to be dominated by their definitions, MapMetadata will + /// return "!{}" instead of "null" for \a LocalAsMetadata instances whose SSA + /// values are unmapped when this flag is set. Otherwise, \a MapValue() + /// completely ignores this flag. + /// + /// \a MapMetadata() always ignores this flag. + RF_IgnoreMissingLocals = 2, + + /// Instruct the remapper to move distinct metadata instead of duplicating it + /// when there are module-level changes. + RF_MoveDistinctMDs = 4, + + /// Any global values not in value map are mapped to null instead of mapping + /// to self. Illegal if RF_IgnoreMissingLocals is also set. + RF_NullMapMissingGlobalValues = 8, +}; + +static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { + return RemapFlags(unsigned(LHS) | unsigned(RHS)); +} + +class ValueMapperImpl; + +/// Context for (re-)mapping values (and metadata). +/// +/// A shared context used for mapping and remapping of Value and Metadata +/// instances using \a ValueToValueMapTy, \a RemapFlags, \a +/// ValueMapTypeRemapper, and \a ValueMaterializer. +/// +/// There are a number of top-level entry points: +/// - \a mapValue() (and \a mapConstant()); +/// - \a mapMetadata() (and \a mapMDNode()); +/// - \a remapInstruction(); and +/// - \a remapFunction(). +/// +/// The \a ValueMaterializer can be used as a callback, but cannot invoke any +/// of these top-level functions recursively. Instead, callbacks should use +/// one of the following to schedule work lazily in the \a ValueMapper +/// instance: +/// - \a scheduleMapGlobalInitializer() +/// - \a scheduleMapAppendingVariable() +/// - \a scheduleMapGlobalAliasee() +/// - \a scheduleRemapFunction() +/// +/// Sometimes a callback needs a diferent mapping context. Such a context can +/// be registered using \a registerAlternateMappingContext(), which takes an +/// alternate \a ValueToValueMapTy and \a ValueMaterializer and returns a ID to +/// pass into the schedule*() functions. +/// +/// TODO: lib/Linker really doesn't need the \a ValueHandle in the \a +/// ValueToValueMapTy. We should template \a ValueMapper (and its +/// implementation classes), and explicitly instantiate on two concrete +/// instances of \a ValueMap (one as \a ValueToValueMap, and one with raw \a +/// Value pointers). It may be viable to do away with \a TrackingMDRef in the +/// \a Metadata side map for the lib/Linker case as well, in which case we'll +/// need a new template parameter on \a ValueMap. +/// +/// TODO: Update callers of \a RemapInstruction() and \a MapValue() (etc.) to +/// use \a ValueMapper directly. +class ValueMapper { + void *pImpl; + + ValueMapper(ValueMapper &&) = delete; + ValueMapper(const ValueMapper &) = delete; + ValueMapper &operator=(ValueMapper &&) = delete; + ValueMapper &operator=(const ValueMapper &) = delete; + +public: + ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr); + ~ValueMapper(); + + /// Register an alternate mapping context. + /// + /// Returns a MappingContextID that can be used with the various schedule*() + /// API to switch in a different value map on-the-fly. + unsigned + registerAlternateMappingContext(ValueToValueMapTy &VM, + ValueMaterializer *Materializer = nullptr); + + /// Add to the current \a RemapFlags. + /// + /// \note Like the top-level mapping functions, \a addFlags() must be called + /// at the top level, not during a callback in a \a ValueMaterializer. + void addFlags(RemapFlags Flags); + + Metadata *mapMetadata(const Metadata &MD); + MDNode *mapMDNode(const MDNode &N); + + Value *mapValue(const Value &V); + Constant *mapConstant(const Constant &C); + + void remapInstruction(Instruction &I); + void remapFunction(Function &F); + + void scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init, + unsigned MappingContextID = 0); + void scheduleMapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix, + bool IsOldCtorDtor, + ArrayRef<Constant *> NewMembers, + unsigned MappingContextID = 0); + void scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee, + unsigned MappingContextID = 0); + void scheduleRemapFunction(Function &F, unsigned MappingContextID = 0); +}; + +/// Look up or compute a value in the value map. +/// +/// Return a mapped value for a function-local value (Argument, Instruction, +/// BasicBlock), or compute and memoize a value for a Constant. +/// +/// 1. If \c V is in VM, return the result. +/// 2. Else if \c V can be materialized with \c Materializer, do so, memoize +/// it in \c VM, and return it. +/// 3. Else if \c V is a function-local value, return nullptr. +/// 4. Else if \c V is a \a GlobalValue, return \c nullptr or \c V depending +/// on \a RF_NullMapMissingGlobalValues. +/// 5. Else if \c V is a \a MetadataAsValue wrapping a LocalAsMetadata, +/// recurse on the local SSA value, and return nullptr or "metadata !{}" on +/// missing depending on RF_IgnoreMissingValues. +/// 6. Else if \c V is a \a MetadataAsValue, rewrap the return of \a +/// MapMetadata(). +/// 7. Else, compute the equivalent constant, and return it. +inline Value *MapValue(const Value *V, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapValue(*V); +} + +/// Lookup or compute a mapping for a piece of metadata. +/// +/// Compute and memoize a mapping for \c MD. +/// +/// 1. If \c MD is mapped, return it. +/// 2. Else if \a RF_NoModuleLevelChanges or \c MD is an \a MDString, return +/// \c MD. +/// 3. Else if \c MD is a \a ConstantAsMetadata, call \a MapValue() and +/// re-wrap its return (returning nullptr on nullptr). +/// 4. Else, \c MD is an \a MDNode. These are remapped, along with their +/// transitive operands. Distinct nodes are duplicated or moved depending +/// on \a RF_MoveDistinctNodes. Uniqued nodes are remapped like constants. +/// +/// \note \a LocalAsMetadata is completely unsupported by \a MapMetadata. +/// Instead, use \a MapValue() with its wrapping \a MetadataAsValue instance. +inline Metadata *MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapMetadata(*MD); +} + +/// Version of MapMetadata with type safety for MDNode. +inline MDNode *MapMetadata(const MDNode *MD, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapMDNode(*MD); +} + +/// Convert the instruction operands from referencing the current values into +/// those specified by VM. +/// +/// If \a RF_IgnoreMissingLocals is set and an operand can't be found via \a +/// MapValue(), use the old value. Otherwise assert that this doesn't happen. +/// +/// Note that \a MapValue() only returns \c nullptr for SSA values missing from +/// \c VM. +inline void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + ValueMapper(VM, Flags, TypeMapper, Materializer).remapInstruction(*I); +} + +/// Remap the operands, metadata, arguments, and instructions of a function. +/// +/// Calls \a MapValue() on prefix data, prologue data, and personality +/// function; calls \a MapMetadata() on each attached MDNode; remaps the +/// argument types using the provided \c TypeMapper; and calls \a +/// RemapInstruction() on every instruction. +inline void RemapFunction(Function &F, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + ValueMapper(VM, Flags, TypeMapper, Materializer).remapFunction(F); +} + +/// Version of MapValue with type safety for Constant. +inline Constant *MapValue(const Constant *V, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapConstant(*V); +} } // End llvm namespace diff --git a/include/llvm/Transforms/Vectorize.h b/include/llvm/Transforms/Vectorize.h index aec3993d68fc..f734e299c6e9 100644 --- a/include/llvm/Transforms/Vectorize.h +++ b/include/llvm/Transforms/Vectorize.h @@ -139,6 +139,13 @@ Pass *createSLPVectorizerPass(); bool vectorizeBasicBlock(Pass *P, BasicBlock &BB, const VectorizeConfig &C = VectorizeConfig()); +//===----------------------------------------------------------------------===// +// +// LoadStoreVectorizer - Create vector loads and stores, but leave scalar +// operations. +// +Pass *createLoadStoreVectorizerPass(); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Vectorize/LoopVectorize.h b/include/llvm/Transforms/Vectorize/LoopVectorize.h new file mode 100644 index 000000000000..e6d3e8353307 --- /dev/null +++ b/include/llvm/Transforms/Vectorize/LoopVectorize.h @@ -0,0 +1,103 @@ +//===---- LoopVectorize.h ---------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops +// and generates target-independent LLVM-IR. +// The vectorizer uses the TargetTransformInfo analysis to estimate the costs +// of instructions in order to estimate the profitability of vectorization. +// +// The loop vectorizer combines consecutive loop iterations into a single +// 'wide' iteration. After this transformation the index is incremented +// by the SIMD vector width, and not by one. +// +// This pass has three parts: +// 1. The main loop pass that drives the different parts. +// 2. LoopVectorizationLegality - A unit that checks for the legality +// of the vectorization. +// 3. InnerLoopVectorizer - A unit that performs the actual +// widening of instructions. +// 4. LoopVectorizationCostModel - A unit that checks for the profitability +// of vectorization. It decides on the optimal vector width, which +// can be one, if vectorization is not profitable. +// +//===----------------------------------------------------------------------===// +// +// The reduction-variable vectorization is based on the paper: +// D. Nuzman and R. Henderson. Multi-platform Auto-vectorization. +// +// Variable uniformity checks are inspired by: +// Karrenberg, R. and Hack, S. Whole Function Vectorization. +// +// The interleaved access vectorization is based on the paper: +// Dorit Nuzman, Ira Rosen and Ayal Zaks. Auto-Vectorization of Interleaved +// Data for SIMD +// +// Other ideas/concepts are from: +// A. Zaks and D. Nuzman. Autovectorization in GCC-two years later. +// +// S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua. An Evaluation of +// Vectorizing Compilers. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H +#define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H + +#include "llvm/ADT/MapVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/DemandedBits.h" +#include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPassManager.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" +#include <functional> + +namespace llvm { + +/// The LoopVectorize Pass. +struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> { + bool DisableUnrolling = false; + /// If true, consider all loops for vectorization. + /// If false, only loops that explicitly request vectorization are + /// considered. + bool AlwaysVectorize = true; + + ScalarEvolution *SE; + LoopInfo *LI; + TargetTransformInfo *TTI; + DominatorTree *DT; + BlockFrequencyInfo *BFI; + TargetLibraryInfo *TLI; + DemandedBits *DB; + AliasAnalysis *AA; + AssumptionCache *AC; + std::function<const LoopAccessInfo &(Loop &)> *GetLAA; + + BlockFrequency ColdEntryFreq; + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + // Shim for old PM. + bool runImpl(Function &F, ScalarEvolution &SE_, LoopInfo &LI_, + TargetTransformInfo &TTI_, DominatorTree &DT_, + BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_, + DemandedBits &DB_, AliasAnalysis &AA_, AssumptionCache &AC_, + std::function<const LoopAccessInfo &(Loop &)> &GetLAA_); + + bool processLoop(Loop *L); +}; +} + +#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H diff --git a/include/llvm/Transforms/Vectorize/SLPVectorizer.h b/include/llvm/Transforms/Vectorize/SLPVectorizer.h new file mode 100644 index 000000000000..3a5b42411d35 --- /dev/null +++ b/include/llvm/Transforms/Vectorize/SLPVectorizer.h @@ -0,0 +1,113 @@ +//===---- SLPVectorizer.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 implements the Bottom Up SLP vectorizer. It detects consecutive +// stores that can be put together into vector-stores. Next, it attempts to +// construct vectorizable tree using the use-def chains. If a profitable tree +// was found, the SLP vectorizer performs vectorization on the tree. +// +// The pass is inspired by the work described in the paper: +// "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H +#define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H + +#include "llvm/ADT/MapVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/DemandedBits.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by this pass. +/// These are implementation details and should not be used by clients. +namespace slpvectorizer { +class BoUpSLP; +} + +struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> { + typedef SmallVector<StoreInst *, 8> StoreList; + typedef MapVector<Value *, StoreList> StoreListMap; + typedef SmallVector<WeakVH, 8> WeakVHList; + typedef MapVector<Value *, WeakVHList> WeakVHListMap; + + ScalarEvolution *SE = nullptr; + TargetTransformInfo *TTI = nullptr; + TargetLibraryInfo *TLI = nullptr; + AliasAnalysis *AA = nullptr; + LoopInfo *LI = nullptr; + DominatorTree *DT = nullptr; + AssumptionCache *AC = nullptr; + DemandedBits *DB = nullptr; + const DataLayout *DL = nullptr; + +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + // Glue for old PM. + bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_, + TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_, + DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_); + +private: + /// \brief Collect store and getelementptr instructions and organize them + /// according to the underlying object of their pointer operands. We sort the + /// instructions by their underlying objects to reduce the cost of + /// consecutive access queries. + /// + /// TODO: We can further reduce this cost if we flush the chain creation + /// every time we run into a memory barrier. + void collectSeedInstructions(BasicBlock *BB); + + /// \brief Try to vectorize a chain that starts at two arithmetic instrs. + bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R); + + /// \brief Try to vectorize a list of operands. + /// \@param BuildVector A list of users to ignore for the purpose of + /// scheduling and that don't need extracting. + /// \returns true if a value was vectorized. + bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, + ArrayRef<Value *> BuildVector = None, + bool allowReorder = false); + + /// \brief Try to vectorize a chain that may start at the operands of \V; + bool tryToVectorize(BinaryOperator *V, slpvectorizer::BoUpSLP &R); + + /// \brief Vectorize the store instructions collected in Stores. + bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); + + /// \brief Vectorize the index computations of the getelementptr instructions + /// collected in GEPs. + bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); + + /// \brief Scan the basic block and look for patterns that are likely to start + /// a vectorization chain. + bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); + + bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold, + slpvectorizer::BoUpSLP &R, unsigned VecRegSize); + + bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold, + slpvectorizer::BoUpSLP &R); + + /// The store instructions in a basic block organized by base pointer. + StoreListMap Stores; + + /// The getelementptr instructions in a basic block organized by base pointer. + WeakVHListMap GEPs; +}; +} + +#endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H |