diff options
Diffstat (limited to 'include/llvm/Transforms')
46 files changed, 1231 insertions, 1426 deletions
diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h index dd55062e56f1a..39ceb19525b3c 100644 --- a/include/llvm/Transforms/IPO.h +++ b/include/llvm/Transforms/IPO.h @@ -50,12 +50,12 @@ ModulePass *createStripNonLineTableDebugInfoPass(); //===----------------------------------------------------------------------===// // -// These pass removes llvm.dbg.declare intrinsics. +// This pass removes llvm.dbg.declare intrinsics. ModulePass *createStripDebugDeclarePass(); //===----------------------------------------------------------------------===// // -// These pass removes unused symbols' debug info. +// This pass removes unused symbols' debug info. ModulePass *createStripDeadDebugInfoPass(); //===----------------------------------------------------------------------===// @@ -108,7 +108,8 @@ Pass *createFunctionImportPass(); /// threshold given here. Pass *createFunctionInliningPass(); Pass *createFunctionInliningPass(int Threshold); -Pass *createFunctionInliningPass(unsigned OptLevel, unsigned SizeOptLevel); +Pass *createFunctionInliningPass(unsigned OptLevel, unsigned SizeOptLevel, + bool DisableInlineHotCallSite); Pass *createFunctionInliningPass(InlineParams &Params); //===----------------------------------------------------------------------===// @@ -215,27 +216,42 @@ ModulePass *createMetaRenamerPass(); /// manager. ModulePass *createBarrierNoopPass(); -/// What to do with the summary when running the LowerTypeTests pass. -enum class LowerTypeTestsSummaryAction { +/// What to do with the summary when running passes that operate on it. +enum class PassSummaryAction { None, ///< Do nothing. - Import, ///< Import typeid resolutions from summary and globals. - Export, ///< Export typeid resolutions to summary and globals. + Import, ///< Import information from summary. + Export, ///< Export information to summary. }; /// \brief This pass lowers type metadata and the llvm.type.test intrinsic to /// bitsets. -/// \param Action What to do with the summary passed as Index. -/// \param Index The summary to use for importing or exporting, this can be null -/// when Action is None. -ModulePass *createLowerTypeTestsPass(LowerTypeTestsSummaryAction Action, - ModuleSummaryIndex *Index); +/// +/// The behavior depends on the summary arguments: +/// - If ExportSummary is non-null, this pass will export type identifiers to +/// the given summary. +/// - Otherwise, if ImportSummary is non-null, this pass will import type +/// identifiers from the given summary. +/// - Otherwise it does neither. +/// It is invalid for both ExportSummary and ImportSummary to be non-null. +ModulePass *createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, + const ModuleSummaryIndex *ImportSummary); /// \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(); +/// +/// The behavior depends on the summary arguments: +/// - If ExportSummary is non-null, this pass will export type identifiers to +/// the given summary. +/// - Otherwise, if ImportSummary is non-null, this pass will import type +/// identifiers from the given summary. +/// - Otherwise it does neither. +/// It is invalid for both ExportSummary and ImportSummary to be non-null. +ModulePass * +createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, + const ModuleSummaryIndex *ImportSummary); /// This pass splits globals into pieces for the benefit of whole-program /// devirtualization and control-flow integrity. @@ -248,7 +264,8 @@ ModulePass *createSampleProfileLoaderPass(); ModulePass *createSampleProfileLoaderPass(StringRef Name); /// Write ThinLTO-ready bitcode to Str. -ModulePass *createWriteThinLTOBitcodePass(raw_ostream &Str); +ModulePass *createWriteThinLTOBitcodePass(raw_ostream &Str, + raw_ostream *ThinLinkOS = nullptr); } // End llvm namespace diff --git a/include/llvm/Transforms/IPO/ArgumentPromotion.h b/include/llvm/Transforms/IPO/ArgumentPromotion.h new file mode 100644 index 0000000000000..724ff72f3b5a1 --- /dev/null +++ b/include/llvm/Transforms/IPO/ArgumentPromotion.h @@ -0,0 +1,31 @@ +//===- ArgumentPromotion.h - Promote by-reference arguments -----*- 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_IPO_ARGUMENTPROMOTION_H +#define LLVM_TRANSFORMS_IPO_ARGUMENTPROMOTION_H + +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LazyCallGraph.h" + +namespace llvm { + +/// Argument promotion pass. +/// +/// This pass walks the functions in each SCC and for each one tries to +/// transform it and all of its callers to replace indirect arguments with +/// direct (by-value) arguments. +class ArgumentPromotionPass : public PassInfoMixin<ArgumentPromotionPass> { +public: + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR); +}; + +} + +#endif diff --git a/include/llvm/Transforms/IPO/FunctionAttrs.h b/include/llvm/Transforms/IPO/FunctionAttrs.h index ee45f35bf11b2..85d6364c8bbc9 100644 --- a/include/llvm/Transforms/IPO/FunctionAttrs.h +++ b/include/llvm/Transforms/IPO/FunctionAttrs.h @@ -20,6 +20,19 @@ namespace llvm { +class AAResults; + +/// The three kinds of memory access relevant to 'readonly' and +/// 'readnone' attributes. +enum MemoryAccessKind { + MAK_ReadNone = 0, + MAK_ReadOnly = 1, + MAK_MayWrite = 2 +}; + +/// Returns the memory access properties of this copy of the function. +MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR); + /// Computes function attributes in post-order over the call graph. /// /// By operating in post-order, this pass computes precise attributes for @@ -43,7 +56,7 @@ Pass *createPostOrderFunctionAttrsLegacyPass(); /// 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 +/// provides the complement 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 diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h index eaea092c91795..ed5742ab8b564 100644 --- a/include/llvm/Transforms/IPO/FunctionImport.h +++ b/include/llvm/Transforms/IPO/FunctionImport.h @@ -53,12 +53,8 @@ public: : 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. Expected<bool> - importFunctions(Module &M, const ImportMapTy &ImportList, - bool ForceImportReferencedDiscardableSymbols = false); + importFunctions(Module &M, const ImportMapTy &ImportList); private: /// The summaries index used to trigger importing. diff --git a/include/llvm/Transforms/IPO/GlobalDCE.h b/include/llvm/Transforms/IPO/GlobalDCE.h index 57e174c2a37fe..9ca939c15b62e 100644 --- a/include/llvm/Transforms/IPO/GlobalDCE.h +++ b/include/llvm/Transforms/IPO/GlobalDCE.h @@ -18,6 +18,8 @@ #ifndef LLVM_TRANSFORMS_IPO_GLOBALDCE_H #define LLVM_TRANSFORMS_IPO_GLOBALDCE_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include <unordered_map> @@ -31,14 +33,23 @@ public: private: SmallPtrSet<GlobalValue*, 32> AliveGlobals; - SmallPtrSet<Constant *, 8> SeenConstants; + + /// Global -> Global that uses this global. + std::unordered_multimap<GlobalValue *, GlobalValue *> GVDependencies; + + /// Constant -> Globals that use this global cache. + std::unordered_map<Constant *, SmallPtrSet<GlobalValue *, 8>> + ConstantDependenciesCache; + + /// Comdat -> Globals in that Comdat section. 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); + void UpdateGVDependencies(GlobalValue &GV); + void MarkLive(GlobalValue &GV, + SmallVectorImpl<GlobalValue *> *Updates = nullptr); bool RemoveUnusedGlobalValue(GlobalValue &GV); + + void ComputeDependencies(Value *V, SmallPtrSetImpl<GlobalValue *> &U); }; } diff --git a/include/llvm/Transforms/IPO/LowerTypeTests.h b/include/llvm/Transforms/IPO/LowerTypeTests.h index ca6e1b878dff0..a2b888ce9ffa3 100644 --- a/include/llvm/Transforms/IPO/LowerTypeTests.h +++ b/include/llvm/Transforms/IPO/LowerTypeTests.h @@ -15,11 +15,9 @@ #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 <cstdint> #include <cstring> #include <limits> @@ -28,9 +26,6 @@ namespace llvm { -class DataLayout; -class GlobalObject; -class Value; class raw_ostream; namespace lowertypetests { @@ -65,9 +60,10 @@ struct BitSetInfo { struct BitSetBuilder { SmallVector<uint64_t, 16> Offsets; - uint64_t Min, Max; + uint64_t Min = std::numeric_limits<uint64_t>::max(); + uint64_t Max = 0; - BitSetBuilder() : Min(std::numeric_limits<uint64_t>::max()), Max(0) {} + BitSetBuilder() = default; void addOffset(uint64_t Offset) { if (Min > Offset) diff --git a/include/llvm/Transforms/IPO/PassManagerBuilder.h b/include/llvm/Transforms/IPO/PassManagerBuilder.h index abfb24f0fe509..247382c35eebf 100644 --- a/include/llvm/Transforms/IPO/PassManagerBuilder.h +++ b/include/llvm/Transforms/IPO/PassManagerBuilder.h @@ -21,6 +21,7 @@ #include <vector> namespace llvm { +class ModuleSummaryIndex; class Pass; class TargetLibraryInfoImpl; class TargetMachine; @@ -100,6 +101,14 @@ public: /// will be inserted after each instance of the instruction combiner pass. EP_Peephole, + /// EP_LateLoopOptimizations - This extension point allows adding late loop + /// canonicalization and simplification passes. This is the last point in + /// the loop optimization pipeline before loop deletion. Each pass added + /// here must be an instance of LoopPass. + /// This is the place to add passes that can remove loops, such as target- + /// specific loop idiom recognition. + EP_LateLoopOptimizations, + /// EP_CGSCCOptimizerLate - This extension point allows adding CallGraphSCC /// passes at the end of the main CallGraphSCC passes and before any /// function simplification passes run by CGPassManager. @@ -123,6 +132,16 @@ public: /// added to the per-module passes. Pass *Inliner; + /// The module summary index to use for exporting information from the + /// regular LTO phase, for example for the CFI and devirtualization type + /// tests. + ModuleSummaryIndex *ExportSummary = nullptr; + + /// The module summary index to use for importing information to the + /// thin LTO backends, for example for the CFI and devirtualization type + /// tests. + const ModuleSummaryIndex *ImportSummary = nullptr; + bool DisableTailCalls; bool DisableUnitAtATime; bool DisableUnrollLoops; @@ -139,6 +158,7 @@ public: bool PrepareForLTO; bool PrepareForThinLTO; bool PerformThinLTO; + bool DivergentTarget; /// Enable profile instrumentation pass. bool EnablePGOInstrGen; diff --git a/include/llvm/Transforms/InstrProfiling.h b/include/llvm/Transforms/InstrProfiling.h index b7c2935f4d841..65e69761baddd 100644 --- a/include/llvm/Transforms/InstrProfiling.h +++ b/include/llvm/Transforms/InstrProfiling.h @@ -1,4 +1,4 @@ -//===- Transforms/InstrProfiling.h - Instrumentation passes ---*- C++ -*-===// +//===- Transforms/InstrProfiling.h - Instrumentation passes -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,10 +14,16 @@ #ifndef LLVM_TRANSFORMS_INSTRPROFILING_H #define LLVM_TRANSFORMS_INSTRPROFILING_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringRef.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/PassManager.h" #include "llvm/ProfileData/InstrProf.h" #include "llvm/Transforms/Instrumentation.h" +#include <cstddef> +#include <cstdint> +#include <cstring> +#include <vector> namespace llvm { @@ -28,7 +34,7 @@ class TargetLibraryInfo; /// instrumentation pass. class InstrProfiling : public PassInfoMixin<InstrProfiling> { public: - InstrProfiling() {} + InstrProfiling() = default; InstrProfiling(const InstrProfOptions &Options) : Options(Options) {} PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); @@ -37,12 +43,14 @@ public: private: InstrProfOptions Options; Module *M; + Triple TT; const TargetLibraryInfo *TLI; struct PerFunctionProfileData { uint32_t NumValueSites[IPVK_Last + 1]; - GlobalVariable *RegionCounters; - GlobalVariable *DataVar; - PerFunctionProfileData() : RegionCounters(nullptr), DataVar(nullptr) { + GlobalVariable *RegionCounters = nullptr; + GlobalVariable *DataVar = nullptr; + + PerFunctionProfileData() { memset(NumValueSites, 0, sizeof(uint32_t) * (IPVK_Last + 1)); } }; @@ -52,19 +60,10 @@ private: 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; + // The start value of precise value profile range for memory intrinsic sizes. + int64_t MemOPSizeRangeStart; + // The end value of precise value profile range for memory intrinsic sizes. + int64_t MemOPSizeRangeLast; /// Count the number of instrumented value sites for the function. void computeNumValueSiteCounts(InstrProfValueProfileInst *Ins); @@ -104,5 +103,6 @@ private: void emitInitialization(); }; -} // End llvm namespace -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_INSTRPROFILING_H diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h index 7fb9a54420815..01a3975a4f2cc 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -16,6 +16,10 @@ #include "llvm/ADT/StringRef.h" #include "llvm/IR/BasicBlock.h" +#include <cassert> +#include <cstdint> +#include <limits> +#include <string> #include <vector> #if defined(__GNUC__) && defined(__linux__) && !defined(ANDROID) @@ -34,7 +38,8 @@ inline void *getDFSanRetValTLSPtrForJIT() { namespace llvm { -class TargetMachine; +class FunctionPass; +class ModulePass; /// Instrumentation passes often insert conditional checks into entry blocks. /// Call this function before splitting the entry block to move instructions @@ -44,9 +49,6 @@ class TargetMachine; BasicBlock::iterator PrepareToSplitEntryBlock(BasicBlock &BB, BasicBlock::iterator IP); -class ModulePass; -class FunctionPass; - // Insert GCOV profiling instrumentation struct GCOVOptions { static GCOVOptions getDefault(); @@ -76,6 +78,7 @@ struct GCOVOptions { // all of the function body's blocks. bool ExitBlockBeforeBody; }; + ModulePass *createGCOVProfilerPass(const GCOVOptions &Options = GCOVOptions::getDefault()); @@ -83,17 +86,40 @@ ModulePass *createGCOVProfilerPass(const GCOVOptions &Options = ModulePass *createPGOInstrumentationGenLegacyPass(); ModulePass * createPGOInstrumentationUseLegacyPass(StringRef Filename = StringRef("")); -ModulePass *createPGOIndirectCallPromotionLegacyPass(bool InLTO = false); +ModulePass *createPGOIndirectCallPromotionLegacyPass(bool InLTO = false, + bool SamplePGO = false); +FunctionPass *createPGOMemOPSizeOptLegacyPass(); + +// Helper function to check if it is legal to promote indirect call \p Inst +// to a direct call of function \p F. Stores the reason in \p Reason. +bool isLegalToPromote(Instruction *Inst, Function *F, const char **Reason); + +// Helper function that transforms Inst (either an indirect-call instruction, or +// an invoke instruction , to a conditional call to F. This is like: +// if (Inst.CalledValue == F) +// F(...); +// else +// Inst(...); +// end +// TotalCount is the profile count value that the instruction executes. +// Count is the profile count value that F is the target function. +// These two values are used to update the branch weight. +// If \p AttachProfToDirectCall is true, a prof metadata is attached to the +// new direct call to contain \p Count. +// Returns the promoted direct call instruction. +Instruction *promoteIndirectCall(Instruction *Inst, Function *F, uint64_t Count, + uint64_t TotalCount, + bool AttachProfToDirectCall); /// Options for the frontend instrumentation based profiling pass. struct InstrProfOptions { - InstrProfOptions() : NoRedZone(false) {} - // Add the 'noredzone' attribute to added runtime library calls. - bool NoRedZone; + bool NoRedZone = false; // Name of the profile file to use as output std::string InstrProfileOutput; + + InstrProfOptions() = default; }; /// Insert frontend instrumentation based profiling. @@ -121,12 +147,13 @@ ModulePass *createDataFlowSanitizerPass( // Options for EfficiencySanitizer sub-tools. struct EfficiencySanitizerOptions { - EfficiencySanitizerOptions() : ToolType(ESAN_None) {} enum Type { ESAN_None = 0, ESAN_CacheFrag, ESAN_WorkingSet, - } ToolType; + } ToolType = ESAN_None; + + EfficiencySanitizerOptions() = default; }; // Insert EfficiencySanitizer instrumentation. @@ -135,25 +162,22 @@ ModulePass *createEfficiencySanitizerPass( // Options for sanitizer coverage instrumentation. struct SanitizerCoverageOptions { - SanitizerCoverageOptions() - : CoverageType(SCK_None), IndirectCalls(false), TraceBB(false), - TraceCmp(false), TraceDiv(false), TraceGep(false), - Use8bitCounters(false), TracePC(false), TracePCGuard(false) {} - enum Type { SCK_None = 0, SCK_Function, SCK_BB, SCK_Edge - } CoverageType; - bool IndirectCalls; - bool TraceBB; - bool TraceCmp; - bool TraceDiv; - bool TraceGep; - bool Use8bitCounters; - bool TracePC; - bool TracePCGuard; + } CoverageType = SCK_None; + bool IndirectCalls = false; + bool TraceBB = false; + bool TraceCmp = false; + bool TraceDiv = false; + bool TraceGep = false; + bool Use8bitCounters = false; + bool TracePC = false; + bool TracePCGuard = false; + + SanitizerCoverageOptions() = default; }; // Insert SanitizerCoverage instrumentation. @@ -175,9 +199,11 @@ FunctionPass *createBoundsCheckingPass(); /// \brief Calculate what to divide by to scale counts. /// /// Given the maximum count, calculate a divisor that will scale all the -/// weights to strictly less than UINT32_MAX. +/// weights to strictly less than std::numeric_limits<uint32_t>::max(). static inline uint64_t calculateCountScale(uint64_t MaxCount) { - return MaxCount < UINT32_MAX ? 1 : MaxCount / UINT32_MAX + 1; + return MaxCount < std::numeric_limits<uint32_t>::max() + ? 1 + : MaxCount / std::numeric_limits<uint32_t>::max() + 1; } /// \brief Scale an individual branch count. @@ -186,10 +212,10 @@ static inline uint64_t calculateCountScale(uint64_t MaxCount) { /// static inline uint32_t scaleBranchCount(uint64_t Count, uint64_t Scale) { uint64_t Scaled = Count / Scale; - assert(Scaled <= UINT32_MAX && "overflow 32-bits"); + assert(Scaled <= std::numeric_limits<uint32_t>::max() && "overflow 32-bits"); return Scaled; } -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_INSTRUMENTATION_H diff --git a/include/llvm/Transforms/PGOInstrumentation.h b/include/llvm/Transforms/PGOInstrumentation.h index 1b449c9abdc27..19263f0f8071d 100644 --- a/include/llvm/Transforms/PGOInstrumentation.h +++ b/include/llvm/Transforms/PGOInstrumentation.h @@ -38,11 +38,24 @@ private: /// The indirect function call promotion pass. class PGOIndirectCallPromotion : public PassInfoMixin<PGOIndirectCallPromotion> { public: - PGOIndirectCallPromotion(bool IsInLTO = false) : InLTO(IsInLTO) {} + PGOIndirectCallPromotion(bool IsInLTO = false, bool SamplePGO = false) + : InLTO(IsInLTO), SamplePGO(SamplePGO) {} PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); + private: bool InLTO; + bool SamplePGO; }; +/// The profile size based optimization pass for memory intrinsics. +class PGOMemOPSizeOpt : public PassInfoMixin<PGOMemOPSizeOpt> { +public: + PGOMemOPSizeOpt() {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +void setProfMetadata(Module *M, Instruction *TI, ArrayRef<uint64_t> EdgeCounts, + uint64_t MaxCount); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index 92558937d0476..ba0a3ee1287a4 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -147,6 +147,12 @@ Pass *createLoopSinkPass(); //===----------------------------------------------------------------------===// // +// LoopPredication - This pass does loop predication on guards. +// +Pass *createLoopPredicationPass(); + +//===----------------------------------------------------------------------===// +// // LoopInterchange - This pass interchanges loops to provide a more // cache-friendly memory access patterns. // @@ -163,7 +169,8 @@ Pass *createLoopStrengthReducePass(); // // LoopUnswitch - This pass is a simple loop unswitching pass. // -Pass *createLoopUnswitchPass(bool OptimizeForSize = false); +Pass *createLoopUnswitchPass(bool OptimizeForSize = false, + bool hasBranchDivergence = false); //===----------------------------------------------------------------------===// // @@ -175,11 +182,11 @@ Pass *createLoopInstSimplifyPass(); // // LoopUnroll - This pass is a simple loop unrolling pass. // -Pass *createLoopUnrollPass(int Threshold = -1, int Count = -1, +Pass *createLoopUnrollPass(int OptLevel = 2, int Threshold = -1, int Count = -1, int AllowPartial = -1, int Runtime = -1, int UpperBound = -1); // Create an unrolling pass for full unrolling that uses exact trip count only. -Pass *createSimpleLoopUnrollPass(); +Pass *createSimpleLoopUnrollPass(int OptLevel = 2); //===----------------------------------------------------------------------===// // @@ -255,6 +262,14 @@ FunctionPass *createCFGSimplificationPass( //===----------------------------------------------------------------------===// // +// LateCFGSimplification - Like CFGSimplification, but may also +// convert switches to lookup tables. +// +FunctionPass *createLateCFGSimplificationPass( + int Threshold = -1, std::function<bool(const Function &)> Ftor = nullptr); + +//===----------------------------------------------------------------------===// +// // FlattenCFG - flatten CFG, reduce number of conditional branches by using // parallel-and and parallel-or mode, etc... // @@ -406,6 +421,15 @@ Pass *createCorrelatedValuePropagationPass(); //===----------------------------------------------------------------------===// // +// InferAddressSpaces - Modify users of addrspacecast instructions with values +// in the source address space if using the destination address space is slower +// on the target. +// +FunctionPass *createInferAddressSpacesPass(); +extern char &InferAddressSpacesID; + +//===----------------------------------------------------------------------===// +// // InstructionSimplifier - Remove redundant instructions. // FunctionPass *createInstructionSimplifierPass(); diff --git a/include/llvm/Transforms/Scalar/GVNExpression.h b/include/llvm/Transforms/Scalar/GVNExpression.h index 3458696e0687a..2670a0c1a5339 100644 --- a/include/llvm/Transforms/Scalar/GVNExpression.h +++ b/include/llvm/Transforms/Scalar/GVNExpression.h @@ -1,4 +1,4 @@ -//======- GVNExpression.h - GVN Expression classes -------*- C++ -*-==-------=// +//======- GVNExpression.h - GVN Expression classes --------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -17,18 +17,22 @@ #define LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H #include "llvm/ADT/Hashing.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Analysis/MemorySSA.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Value.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/ArrayRecycler.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/MemorySSA.h" #include <algorithm> +#include <cassert> +#include <iterator> +#include <utility> namespace llvm { -class MemoryAccess; namespace GVNExpression { @@ -39,11 +43,13 @@ enum ExpressionType { ET_Unknown, ET_BasicStart, ET_Basic, - ET_Call, ET_AggregateValue, ET_Phi, + ET_MemoryStart, + ET_Call, ET_Load, ET_Store, + ET_MemoryEnd, ET_BasicEnd }; @@ -53,23 +59,22 @@ private: unsigned Opcode; public: - Expression(const Expression &) = delete; Expression(ExpressionType ET = ET_Base, unsigned O = ~2U) : EType(ET), Opcode(O) {} - void operator=(const Expression &) = delete; + Expression(const Expression &) = delete; + Expression &operator=(const Expression &) = delete; virtual ~Expression(); static unsigned getEmptyKey() { return ~0U; } static unsigned getTombstoneKey() { return ~1U; } - + bool operator!=(const Expression &Other) const { return !(*this == Other); } bool operator==(const Expression &Other) const { if (getOpcode() != Other.getOpcode()) return false; if (getOpcode() == getEmptyKey() || getOpcode() == getTombstoneKey()) return true; // Compare the expression type for anything but load and store. - // For load and store we set the opcode to zero. - // This is needed for load coercion. + // For load and store we set the opcode to zero to make them equal. if (getExpressionType() != ET_Load && getExpressionType() != ET_Store && getExpressionType() != Other.getExpressionType()) return false; @@ -83,9 +88,8 @@ public: void setOpcode(unsigned opcode) { Opcode = opcode; } ExpressionType getExpressionType() const { return EType; } - virtual hash_code getHashValue() const { - return hash_combine(getExpressionType(), getOpcode()); - } + // We deliberately leave the expression type out of the hash value. + virtual hash_code getHashValue() const { return getOpcode(); } // // Debugging support @@ -101,7 +105,11 @@ public: printInternal(OS, true); OS << "}"; } - void dump() const { print(dbgs()); } + + LLVM_DUMP_METHOD void dump() const { + print(dbgs()); + dbgs() << "\n"; + } }; inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) { @@ -119,20 +127,20 @@ private: Type *ValueType; public: - static bool classof(const Expression *EB) { - ExpressionType ET = EB->getExpressionType(); - return ET > ET_BasicStart && ET < ET_BasicEnd; - } - BasicExpression(unsigned NumOperands) : BasicExpression(NumOperands, ET_Basic) {} BasicExpression(unsigned NumOperands, ExpressionType ET) : Expression(ET), Operands(nullptr), MaxOperands(NumOperands), NumOperands(0), ValueType(nullptr) {} - virtual ~BasicExpression() override; - void operator=(const BasicExpression &) = delete; - BasicExpression(const BasicExpression &) = delete; BasicExpression() = delete; + BasicExpression(const BasicExpression &) = delete; + BasicExpression &operator=(const BasicExpression &) = delete; + ~BasicExpression() override; + + static bool classof(const Expression *EB) { + ExpressionType ET = EB->getExpressionType(); + return ET > ET_BasicStart && ET < ET_BasicEnd; + } /// \brief Swap two operands. Used during GVN to put commutative operands in /// order. @@ -185,7 +193,7 @@ public: void setType(Type *T) { ValueType = T; } Type *getType() const { return ValueType; } - virtual bool equals(const Expression &Other) const override { + bool equals(const Expression &Other) const override { if (getOpcode() != Other.getOpcode()) return false; @@ -194,15 +202,15 @@ public: std::equal(op_begin(), op_end(), OE.op_begin()); } - virtual hash_code getHashValue() const override { - return hash_combine(getExpressionType(), getOpcode(), ValueType, + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), ValueType, hash_combine_range(op_begin(), op_end())); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeBasic, "; @@ -216,6 +224,7 @@ public: OS << "} "; } }; + class op_inserter : public std::iterator<std::output_iterator_tag, void, void, void, void> { private: @@ -235,131 +244,143 @@ public: op_inserter &operator++(int) { return *this; } }; -class CallExpression final : public BasicExpression { +class MemoryExpression : public BasicExpression { private: - CallInst *Call; - MemoryAccess *DefiningAccess; + const MemoryAccess *MemoryLeader; public: + MemoryExpression(unsigned NumOperands, enum ExpressionType EType, + const MemoryAccess *MemoryLeader) + : BasicExpression(NumOperands, EType), MemoryLeader(MemoryLeader){}; + + MemoryExpression() = delete; + MemoryExpression(const MemoryExpression &) = delete; + MemoryExpression &operator=(const MemoryExpression &) = delete; static bool classof(const Expression *EB) { - return EB->getExpressionType() == ET_Call; + return EB->getExpressionType() > ET_MemoryStart && + EB->getExpressionType() < ET_MemoryEnd; + } + hash_code getHashValue() const override { + return hash_combine(this->BasicExpression::getHashValue(), MemoryLeader); } - CallExpression(unsigned NumOperands, CallInst *C, MemoryAccess *DA) - : BasicExpression(NumOperands, ET_Call), Call(C), DefiningAccess(DA) {} - void operator=(const CallExpression &) = delete; - CallExpression(const CallExpression &) = delete; - CallExpression() = delete; - virtual ~CallExpression() override; - - virtual bool equals(const Expression &Other) const override { + bool equals(const Expression &Other) const override { if (!this->BasicExpression::equals(Other)) return false; - const auto &OE = cast<CallExpression>(Other); - return DefiningAccess == OE.DefiningAccess; + const MemoryExpression &OtherMCE = cast<MemoryExpression>(Other); + + return MemoryLeader == OtherMCE.MemoryLeader; } - virtual hash_code getHashValue() const override { - return hash_combine(this->BasicExpression::getHashValue(), DefiningAccess); + const MemoryAccess *getMemoryLeader() const { return MemoryLeader; } + void setMemoryLeader(const MemoryAccess *ML) { MemoryLeader = ML; } +}; + +class CallExpression final : public MemoryExpression { +private: + CallInst *Call; + +public: + CallExpression(unsigned NumOperands, CallInst *C, + const MemoryAccess *MemoryLeader) + : MemoryExpression(NumOperands, ET_Call, MemoryLeader), Call(C) {} + CallExpression() = delete; + CallExpression(const CallExpression &) = delete; + CallExpression &operator=(const CallExpression &) = delete; + ~CallExpression() override; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Call; } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeCall, "; this->BasicExpression::printInternal(OS, false); - OS << " represents call at " << Call; + OS << " represents call at "; + Call->printAsOperand(OS); } }; -class LoadExpression final : public BasicExpression { +class LoadExpression final : public MemoryExpression { private: LoadInst *Load; - MemoryAccess *DefiningAccess; unsigned Alignment; public: - static bool classof(const Expression *EB) { - return EB->getExpressionType() == ET_Load; - } - - LoadExpression(unsigned NumOperands, LoadInst *L, MemoryAccess *DA) - : LoadExpression(ET_Load, NumOperands, L, DA) {} + LoadExpression(unsigned NumOperands, LoadInst *L, + const MemoryAccess *MemoryLeader) + : LoadExpression(ET_Load, NumOperands, L, MemoryLeader) {} LoadExpression(enum ExpressionType EType, unsigned NumOperands, LoadInst *L, - MemoryAccess *DA) - : BasicExpression(NumOperands, EType), Load(L), DefiningAccess(DA) { + const MemoryAccess *MemoryLeader) + : MemoryExpression(NumOperands, EType, MemoryLeader), Load(L) { Alignment = L ? L->getAlignment() : 0; } - void operator=(const LoadExpression &) = delete; - LoadExpression(const LoadExpression &) = delete; LoadExpression() = delete; - virtual ~LoadExpression() override; + LoadExpression(const LoadExpression &) = delete; + LoadExpression &operator=(const LoadExpression &) = delete; + ~LoadExpression() override; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Load; + } LoadInst *getLoadInst() const { return Load; } void setLoadInst(LoadInst *L) { Load = L; } - MemoryAccess *getDefiningAccess() const { return DefiningAccess; } - void setDefiningAccess(MemoryAccess *MA) { DefiningAccess = MA; } unsigned getAlignment() const { return Alignment; } void setAlignment(unsigned Align) { Alignment = Align; } - virtual bool equals(const Expression &Other) const override; - - virtual hash_code getHashValue() const override { - return hash_combine(getOpcode(), getType(), DefiningAccess, - hash_combine_range(op_begin(), op_end())); - } + bool equals(const Expression &Other) const override; // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeLoad, "; this->BasicExpression::printInternal(OS, false); - OS << " represents Load at " << Load; - OS << " with DefiningAccess " << *DefiningAccess; + OS << " represents Load at "; + Load->printAsOperand(OS); + OS << " with MemoryLeader " << *getMemoryLeader(); } }; -class StoreExpression final : public BasicExpression { +class StoreExpression final : public MemoryExpression { private: StoreInst *Store; - MemoryAccess *DefiningAccess; + Value *StoredValue; public: + StoreExpression(unsigned NumOperands, StoreInst *S, Value *StoredValue, + const MemoryAccess *MemoryLeader) + : MemoryExpression(NumOperands, ET_Store, MemoryLeader), Store(S), + StoredValue(StoredValue) {} + StoreExpression() = delete; + StoreExpression(const StoreExpression &) = delete; + StoreExpression &operator=(const StoreExpression &) = delete; + ~StoreExpression() override; + static bool classof(const Expression *EB) { return EB->getExpressionType() == ET_Store; } - StoreExpression(unsigned NumOperands, StoreInst *S, MemoryAccess *DA) - : BasicExpression(NumOperands, ET_Store), Store(S), DefiningAccess(DA) {} - void operator=(const StoreExpression &) = delete; - StoreExpression(const StoreExpression &) = delete; - StoreExpression() = delete; - virtual ~StoreExpression() override; - StoreInst *getStoreInst() const { return Store; } - MemoryAccess *getDefiningAccess() const { return DefiningAccess; } + Value *getStoredValue() const { return StoredValue; } - virtual bool equals(const Expression &Other) const override; + bool equals(const Expression &Other) const override; - virtual hash_code getHashValue() const override { - return hash_combine(getOpcode(), getType(), DefiningAccess, - hash_combine_range(op_begin(), op_end())); - } - - // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeStore, "; this->BasicExpression::printInternal(OS, false); - OS << " represents Store at " << Store; - OS << " with DefiningAccess " << *DefiningAccess; + OS << " represents Store " << *Store; + OS << " with MemoryLeader " << *getMemoryLeader(); } }; @@ -370,19 +391,19 @@ private: unsigned *IntOperands; public: - static bool classof(const Expression *EB) { - return EB->getExpressionType() == ET_AggregateValue; - } - AggregateValueExpression(unsigned NumOperands, unsigned NumIntOperands) : BasicExpression(NumOperands, ET_AggregateValue), MaxIntOperands(NumIntOperands), NumIntOperands(0), IntOperands(nullptr) {} - - void operator=(const AggregateValueExpression &) = delete; - AggregateValueExpression(const AggregateValueExpression &) = delete; AggregateValueExpression() = delete; - virtual ~AggregateValueExpression() override; + AggregateValueExpression(const AggregateValueExpression &) = delete; + AggregateValueExpression & + operator=(const AggregateValueExpression &) = delete; + ~AggregateValueExpression() override; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_AggregateValue; + } typedef unsigned *int_arg_iterator; typedef const unsigned *const_int_arg_iterator; @@ -407,7 +428,7 @@ public: IntOperands = Allocator.Allocate<unsigned>(MaxIntOperands); } - virtual bool equals(const Expression &Other) const override { + bool equals(const Expression &Other) const override { if (!this->BasicExpression::equals(Other)) return false; const AggregateValueExpression &OE = cast<AggregateValueExpression>(Other); @@ -415,7 +436,7 @@ public: std::equal(int_op_begin(), int_op_end(), OE.int_op_begin()); } - virtual hash_code getHashValue() const override { + hash_code getHashValue() const override { return hash_combine(this->BasicExpression::getHashValue(), hash_combine_range(int_op_begin(), int_op_end())); } @@ -423,7 +444,7 @@ public: // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeAggregateValue, "; this->BasicExpression::printInternal(OS, false); @@ -434,6 +455,7 @@ public: OS << "}"; } }; + class int_op_inserter : public std::iterator<std::output_iterator_tag, void, void, void, void> { private: @@ -443,6 +465,7 @@ private: public: explicit int_op_inserter(AggregateValueExpression &E) : AVE(&E) {} explicit int_op_inserter(AggregateValueExpression *E) : AVE(E) {} + int_op_inserter &operator=(unsigned int val) { AVE->int_op_push_back(val); return *this; @@ -457,32 +480,32 @@ private: BasicBlock *BB; public: - static bool classof(const Expression *EB) { - return EB->getExpressionType() == ET_Phi; - } - PHIExpression(unsigned NumOperands, BasicBlock *B) : BasicExpression(NumOperands, ET_Phi), BB(B) {} - void operator=(const PHIExpression &) = delete; - PHIExpression(const PHIExpression &) = delete; PHIExpression() = delete; - virtual ~PHIExpression() override; + PHIExpression(const PHIExpression &) = delete; + PHIExpression &operator=(const PHIExpression &) = delete; + ~PHIExpression() override; - virtual bool equals(const Expression &Other) const override { + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Phi; + } + + bool equals(const Expression &Other) const override { if (!this->BasicExpression::equals(Other)) return false; const PHIExpression &OE = cast<PHIExpression>(Other); return BB == OE.BB; } - virtual hash_code getHashValue() const override { + hash_code getHashValue() const override { return hash_combine(this->BasicExpression::getHashValue(), BB); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypePhi, "; this->BasicExpression::printInternal(OS, false); @@ -495,31 +518,32 @@ private: Value *VariableValue; public: + VariableExpression(Value *V) : Expression(ET_Variable), VariableValue(V) {} + VariableExpression() = delete; + VariableExpression(const VariableExpression &) = delete; + VariableExpression &operator=(const VariableExpression &) = delete; + static bool classof(const Expression *EB) { return EB->getExpressionType() == ET_Variable; } - VariableExpression(Value *V) : Expression(ET_Variable), VariableValue(V) {} - void operator=(const VariableExpression &) = delete; - VariableExpression(const VariableExpression &) = delete; - VariableExpression() = delete; - Value *getVariableValue() const { return VariableValue; } void setVariableValue(Value *V) { VariableValue = V; } - virtual bool equals(const Expression &Other) const override { + + bool equals(const Expression &Other) const override { const VariableExpression &OC = cast<VariableExpression>(Other); return VariableValue == OC.VariableValue; } - virtual hash_code getHashValue() const override { - return hash_combine(getExpressionType(), VariableValue->getType(), - VariableValue); + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), + VariableValue->getType(), VariableValue); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeVariable, "; this->Expression::printInternal(OS, false); @@ -529,36 +553,36 @@ public: class ConstantExpression final : public Expression { private: - Constant *ConstantValue; + Constant *ConstantValue = nullptr; public: - static bool classof(const Expression *EB) { - return EB->getExpressionType() == ET_Constant; - } - - ConstantExpression() : Expression(ET_Constant), ConstantValue(NULL) {} + ConstantExpression() : Expression(ET_Constant) {} ConstantExpression(Constant *constantValue) : Expression(ET_Constant), ConstantValue(constantValue) {} - void operator=(const ConstantExpression &) = delete; ConstantExpression(const ConstantExpression &) = delete; + ConstantExpression &operator=(const ConstantExpression &) = delete; + + static bool classof(const Expression *EB) { + return EB->getExpressionType() == ET_Constant; + } Constant *getConstantValue() const { return ConstantValue; } void setConstantValue(Constant *V) { ConstantValue = V; } - virtual bool equals(const Expression &Other) const override { + bool equals(const Expression &Other) const override { const ConstantExpression &OC = cast<ConstantExpression>(Other); return ConstantValue == OC.ConstantValue; } - virtual hash_code getHashValue() const override { - return hash_combine(getExpressionType(), ConstantValue->getType(), - ConstantValue); + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), + ConstantValue->getType(), ConstantValue); } // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeConstant, "; this->Expression::printInternal(OS, false); @@ -571,35 +595,40 @@ private: Instruction *Inst; public: + UnknownExpression(Instruction *I) : Expression(ET_Unknown), Inst(I) {} + UnknownExpression() = delete; + UnknownExpression(const UnknownExpression &) = delete; + UnknownExpression &operator=(const UnknownExpression &) = delete; + static bool classof(const Expression *EB) { return EB->getExpressionType() == ET_Unknown; } - UnknownExpression(Instruction *I) : Expression(ET_Unknown), Inst(I) {} - void operator=(const UnknownExpression &) = delete; - UnknownExpression(const UnknownExpression &) = delete; - UnknownExpression() = delete; - Instruction *getInstruction() const { return Inst; } void setInstruction(Instruction *I) { Inst = I; } - virtual bool equals(const Expression &Other) const override { + + bool equals(const Expression &Other) const override { const auto &OU = cast<UnknownExpression>(Other); return Inst == OU.Inst; } - virtual hash_code getHashValue() const override { - return hash_combine(getExpressionType(), Inst); + + hash_code getHashValue() const override { + return hash_combine(this->Expression::getHashValue(), Inst); } + // // Debugging support // - virtual void printInternal(raw_ostream &OS, bool PrintEType) const override { + void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeUnknown, "; this->Expression::printInternal(OS, false); OS << " inst = " << *Inst; } }; -} -} -#endif +} // end namespace GVNExpression + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H diff --git a/include/llvm/Transforms/Scalar/JumpThreading.h b/include/llvm/Transforms/Scalar/JumpThreading.h index f96741c0127d8..1da86132591b7 100644 --- a/include/llvm/Transforms/Scalar/JumpThreading.h +++ b/include/llvm/Transforms/Scalar/JumpThreading.h @@ -17,12 +17,14 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/Analysis/AliasAnalysis.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/IntrinsicInst.h" #include "llvm/IR/ValueHandle.h" namespace llvm { @@ -59,9 +61,11 @@ enum ConstantPreference { WantInteger, WantBlockAddress }; class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { TargetLibraryInfo *TLI; LazyValueInfo *LVI; + AliasAnalysis *AA; std::unique_ptr<BlockFrequencyInfo> BFI; std::unique_ptr<BranchProbabilityInfo> BPI; bool HasProfileData = false; + bool HasGuards = false; #ifdef NDEBUG SmallPtrSet<const BasicBlock *, 16> LoopHeaders; #else @@ -88,7 +92,8 @@ public: // Glue for old PM. bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, - bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, + AliasAnalysis *AA_, bool HasProfileData_, + std::unique_ptr<BlockFrequencyInfo> BFI_, std::unique_ptr<BranchProbabilityInfo> BPI_); PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); @@ -122,6 +127,9 @@ public: bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); + bool ProcessGuards(BasicBlock *BB); + bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI); + private: BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, const char *Suffix); diff --git a/include/llvm/Transforms/Scalar/LoopDataPrefetch.h b/include/llvm/Transforms/Scalar/LoopDataPrefetch.h index 114d1bad17a5c..12c7a030ff8b7 100644 --- a/include/llvm/Transforms/Scalar/LoopDataPrefetch.h +++ b/include/llvm/Transforms/Scalar/LoopDataPrefetch.h @@ -22,10 +22,12 @@ namespace llvm { /// An optimization pass inserting data prefetches in loops. class LoopDataPrefetchPass : public PassInfoMixin<LoopDataPrefetchPass> { public: - LoopDataPrefetchPass() {} + LoopDataPrefetchPass() = default; + /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPDATAPREFETCH_H diff --git a/include/llvm/Transforms/Scalar/LoopDeletion.h b/include/llvm/Transforms/Scalar/LoopDeletion.h index b44f823a82cac..7b8cb1e115c97 100644 --- a/include/llvm/Transforms/Scalar/LoopDeletion.h +++ b/include/llvm/Transforms/Scalar/LoopDeletion.h @@ -1,4 +1,4 @@ -//===- LoopDeletion.h - Loop Deletion -------------------------------------===// +//===- LoopDeletion.h - Loop Deletion ---------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,6 +14,7 @@ #ifndef LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H #define LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H +#include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/IR/PassManager.h" @@ -23,18 +24,12 @@ namespace llvm { class LoopDeletionPass : public PassInfoMixin<LoopDeletionPass> { public: - LoopDeletionPass() {} + LoopDeletionPass() = default; + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); - 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); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPDELETION_H diff --git a/include/llvm/Transforms/Scalar/LoopLoadElimination.h b/include/llvm/Transforms/Scalar/LoopLoadElimination.h new file mode 100644 index 0000000000000..7a007a7e822d2 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopLoadElimination.h @@ -0,0 +1,30 @@ +//===---- LoopLoadElimination.h ---------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This header defines the LoopLoadEliminationPass object. This pass forwards +/// loaded values around loop backedges to allow their use in subsequent +/// iterations. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H +#define LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Pass to forward loads in a loop around the backedge to subsequent +/// iterations. +struct LoopLoadEliminationPass : public PassInfoMixin<LoopLoadEliminationPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H diff --git a/include/llvm/Transforms/Scalar/LoopPassManager.h b/include/llvm/Transforms/Scalar/LoopPassManager.h index b0e6dd6f4c081..715b11d3d9749 100644 --- a/include/llvm/Transforms/Scalar/LoopPassManager.h +++ b/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -51,6 +51,8 @@ #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Utils/LCSSA.h" +#include "llvm/Transforms/Utils/LoopSimplify.h" namespace llvm { @@ -248,19 +250,25 @@ template <typename LoopPassT> class FunctionToLoopPassAdaptor : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> { public: - explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {} + explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) { + LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); + LoopCanonicalizationFPM.addPass(LCSSAPass()); + } /// \brief Runs the loop passes across every loop in the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { - // Setup the loop analysis manager from its proxy. - LoopAnalysisManager &LAM = - AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager(); + // Before we even compute any loop analyses, first run a miniature function + // pass pipeline to put loops into their canonical form. Note that we can + // directly build up function analyses after this as the function pass + // manager handles all the invalidation at that layer. + PreservedAnalyses PA = LoopCanonicalizationFPM.run(F, AM); + // Get the loop structure for this function LoopInfo &LI = AM.getResult<LoopAnalysis>(F); // If there are no loops, there is nothing to do here. if (LI.empty()) - return PreservedAnalyses::all(); + return PA; // Get the analysis results needed by loop passes. LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F), @@ -271,7 +279,13 @@ public: AM.getResult<TargetLibraryAnalysis>(F), AM.getResult<TargetIRAnalysis>(F)}; - PreservedAnalyses PA = PreservedAnalyses::all(); + // Setup the loop analysis manager from its proxy. It is important that + // this is only done when there are loops to process and we have built the + // LoopStandardAnalysisResults object. The loop analyses cached in this + // manager have access to those analysis results and so it must invalidate + // itself when they go away. + LoopAnalysisManager &LAM = + AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager(); // A postorder worklist of loops to process. SmallPriorityWorklist<Loop *, 4> Worklist; @@ -294,8 +308,15 @@ public: // Reset the update structure for this loop. Updater.CurrentL = L; Updater.SkipCurrentLoop = false; + #ifndef NDEBUG + // Save a parent loop pointer for asserts. Updater.ParentL = L->getParentLoop(); + + // Verify the loop structure and LCSSA form before visiting the loop. + L->verifyLoop(); + assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) && + "Loops must remain in LCSSA form!"); #endif PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater); @@ -321,7 +342,6 @@ public: PA.preserveSet<AllAnalysesOn<Loop>>(); PA.preserve<LoopAnalysisManagerFunctionProxy>(); // We also preserve the set of standard analyses. - PA.preserve<AssumptionAnalysis>(); PA.preserve<DominatorTreeAnalysis>(); PA.preserve<LoopAnalysis>(); PA.preserve<ScalarEvolutionAnalysis>(); @@ -336,6 +356,8 @@ public: private: LoopPassT Pass; + + FunctionPassManager LoopCanonicalizationFPM; }; /// \brief A function to deduce a loop pass type and wrap it in the templated diff --git a/include/llvm/Transforms/Scalar/LoopPredication.h b/include/llvm/Transforms/Scalar/LoopPredication.h new file mode 100644 index 0000000000000..57398bdb6bd1c --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopPredication.h @@ -0,0 +1,32 @@ +//===- LoopPredication.h - Guard based loop predication 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 tries to convert loop variant range checks to loop invariant by +// widening checks across loop iterations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPPREDICATION_H +#define LLVM_TRANSFORMS_SCALAR_LOOPPREDICATION_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +/// Performs Loop Predication Pass. +class LoopPredicationPass : public PassInfoMixin<LoopPredicationPass> { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPPREDICATION_H diff --git a/include/llvm/Transforms/Scalar/LoopSink.h b/include/llvm/Transforms/Scalar/LoopSink.h new file mode 100644 index 0000000000000..371a7c8d2c446 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopSink.h @@ -0,0 +1,40 @@ +//===- LoopSink.h - Loop Sink 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 provides the interface for the Loop Sink pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPSINK_H +#define LLVM_TRANSFORMS_SCALAR_LOOPSINK_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +/// A pass that does profile-guided sinking of instructions into loops. +/// +/// This is a function pass as it shouldn't be composed into any kind of +/// unified loop pass pipeline. The goal of it is to sink code into loops that +/// is loop invariant but only required within the loop body when doing so +/// reduces the global expected dynamic frequency with which it executes. +/// A classic example is an extremely cold branch within a loop body. +/// +/// We do this as a separate pass so that during normal optimization all +/// invariant operations can be held outside the loop body to simplify +/// fundamental analyses and transforms of the loop. +class LoopSinkPass : public PassInfoMixin<LoopSinkPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPSINK_H diff --git a/include/llvm/Transforms/Scalar/LoopUnrollPass.h b/include/llvm/Transforms/Scalar/LoopUnrollPass.h index 9da95ef81fad4..7253bd09766ef 100644 --- a/include/llvm/Transforms/Scalar/LoopUnrollPass.h +++ b/include/llvm/Transforms/Scalar/LoopUnrollPass.h @@ -16,12 +16,30 @@ namespace llvm { -struct LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> { - Optional<unsigned> ProvidedCount; - Optional<unsigned> ProvidedThreshold; - Optional<bool> ProvidedAllowPartial; - Optional<bool> ProvidedRuntime; - Optional<bool> ProvidedUpperBound; +class LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> { + const bool AllowPartialUnrolling; + const int OptLevel; + + explicit LoopUnrollPass(bool AllowPartialUnrolling, int OptLevel) + : AllowPartialUnrolling(AllowPartialUnrolling), OptLevel(OptLevel) {} + +public: + /// Create an instance of the loop unroll pass that will support both full + /// and partial unrolling. + /// + /// This uses the target information (or flags) to control the thresholds for + /// different unrolling stategies but supports all of them. + static LoopUnrollPass create(int OptLevel = 2) { + return LoopUnrollPass(/*AllowPartialUnrolling*/ true, OptLevel); + } + + /// Create an instance of the loop unroll pass that only does full loop + /// unrolling. + /// + /// This will disable any runtime or partial unrolling. + static LoopUnrollPass createFull(int OptLevel = 2) { + return LoopUnrollPass(/*AllowPartialUnrolling*/ false, OptLevel); + } PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); diff --git a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h index 4308e44e7c4bd..f52872dd2ea78 100644 --- a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h +++ b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h @@ -15,17 +15,18 @@ #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/BasicBlock.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" +#include <cstdint> +#include <functional> namespace llvm { @@ -37,7 +38,8 @@ class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> { std::function<DominatorTree &()> LookupDomTree; public: - MemCpyOptPass() {} + MemCpyOptPass() = default; + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); // Glue for the old PM. bool runImpl(Function &F, MemoryDependenceResults *MD_, @@ -63,6 +65,7 @@ private: bool iterateOnFunction(Function &F); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H diff --git a/include/llvm/Transforms/Scalar/SROA.h b/include/llvm/Transforms/Scalar/SROA.h index 3e93f46dd4e50..3080b75ba8949 100644 --- a/include/llvm/Transforms/Scalar/SROA.h +++ b/include/llvm/Transforms/Scalar/SROA.h @@ -21,17 +21,21 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/Support/Compiler.h" +#include <vector> 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 LLVM_LIBRARY_VISIBILITY { + class AllocaSliceRewriter; class AllocaSlices; class Partition; class SROALegacyPass; -} + +} // end namespace sroa /// \brief An optimization pass providing Scalar Replacement of Aggregates. /// @@ -52,9 +56,9 @@ class SROALegacyPass; /// this form. By doing so, it will enable promotion of vector aggregates to /// SSA vector values. class SROA : public PassInfoMixin<SROA> { - LLVMContext *C; - DominatorTree *DT; - AssumptionCache *AC; + LLVMContext *C = nullptr; + DominatorTree *DT = nullptr; + AssumptionCache *AC = nullptr; /// \brief Worklist of alloca instructions to simplify. /// @@ -99,7 +103,7 @@ class SROA : public PassInfoMixin<SROA> { SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects; public: - SROA() : C(nullptr), DT(nullptr), AC(nullptr) {} + SROA() = default; /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); @@ -122,6 +126,6 @@ private: bool promoteAllocas(Function &F); }; -} +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_SCALAR_SROA_H diff --git a/include/llvm/Transforms/Scalar/SimplifyCFG.h b/include/llvm/Transforms/Scalar/SimplifyCFG.h index 96e1658c00b0e..54b51c405ad41 100644 --- a/include/llvm/Transforms/Scalar/SimplifyCFG.h +++ b/include/llvm/Transforms/Scalar/SimplifyCFG.h @@ -27,13 +27,16 @@ namespace llvm { /// by the rest of the mid-level optimizer. class SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> { int BonusInstThreshold; + bool LateSimplifyCFG; public: - /// \brief Construct a pass with the default thresholds. + /// \brief Construct a pass with the default thresholds + /// and switch optimizations. SimplifyCFGPass(); - /// \brief Construct a pass with a specific bonus threshold. - SimplifyCFGPass(int BonusInstThreshold); + /// \brief Construct a pass with a specific bonus threshold + /// and optional switch optimizations. + SimplifyCFGPass(int BonusInstThreshold, bool LateSimplifyCFG); /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 3d41dbe2b9547..85bb053135a65 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -78,14 +78,13 @@ void ReplaceInstWithInst(Instruction *From, Instruction *To); struct CriticalEdgeSplittingOptions { DominatorTree *DT; LoopInfo *LI; - bool MergeIdenticalEdges; - bool DontDeleteUselessPHIs; - bool PreserveLCSSA; + bool MergeIdenticalEdges = false; + bool DontDeleteUselessPHIs = false; + bool PreserveLCSSA = false; CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, LoopInfo *LI = nullptr) - : DT(DT), LI(LI), MergeIdenticalEdges(false), - DontDeleteUselessPHIs(false), PreserveLCSSA(false) {} + : DT(DT), LI(LI) {} CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { MergeIdenticalEdges = true; diff --git a/include/llvm/Transforms/Utils/BuildLibCalls.h b/include/llvm/Transforms/Utils/BuildLibCalls.h index 2d2a85905d0ea..a067a685b8372 100644 --- a/include/llvm/Transforms/Utils/BuildLibCalls.h +++ b/include/llvm/Transforms/Utils/BuildLibCalls.h @@ -84,14 +84,14 @@ namespace llvm { /// 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); + const AttributeList &Attrs); /// 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); + IRBuilder<> &B, const AttributeList &Attrs); /// Emit a call to the putchar function. This assumes that Char is an integer. Value *emitPutChar(Value *Char, IRBuilder<> &B, const TargetLibraryInfo *TLI); diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h index 5eeb8cf30695c..337305a0a82ce 100644 --- a/include/llvm/Transforms/Utils/Cloning.h +++ b/include/llvm/Transforms/Utils/Cloning.h @@ -22,32 +22,28 @@ #include "llvm/ADT/Twine.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/ValueHandle.h" -#include "llvm/IR/ValueMap.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include <functional> +#include <memory> +#include <vector> namespace llvm { -class Module; -class Function; -class Instruction; -class Pass; -class LPPassManager; +class AllocaInst; class BasicBlock; -class Value; +class BlockFrequencyInfo; class CallInst; -class InvokeInst; -class ReturnInst; -class CallSite; -class Trace; class CallGraph; -class DataLayout; +class DominatorTree; +class Function; +class Instruction; +class InvokeInst; class Loop; class LoopInfo; -class AllocaInst; -class AssumptionCacheTracker; -class DominatorTree; +class Module; +class ReturnInst; /// Return an exact copy of the specified module /// @@ -67,20 +63,20 @@ CloneModule(const Module *M, ValueToValueMapTy &VMap, struct ClonedCodeInfo { /// ContainsCalls - This is set to true if the cloned code contains a normal /// call instruction. - bool ContainsCalls; + bool ContainsCalls = false; /// ContainsDynamicAllocas - This is set to true if the cloned code contains /// a 'dynamic' alloca. Dynamic allocas are allocas that are either not in /// the entry block or they are in the entry block but are not a constant /// size. - bool ContainsDynamicAllocas; + bool ContainsDynamicAllocas = false; /// All cloned call sites that have operand bundles attached are appended to /// this vector. This vector may contain nulls or undefs if some of the /// originally inserted callsites were DCE'ed after they were cloned. std::vector<WeakVH> OperandBundleCallSites; - ClonedCodeInfo() : ContainsCalls(false), ContainsDynamicAllocas(false) {} + ClonedCodeInfo() = default; }; /// CloneBasicBlock - Return a copy of the specified basic block, but without @@ -178,13 +174,17 @@ class InlineFunctionInfo { public: explicit InlineFunctionInfo(CallGraph *cg = nullptr, std::function<AssumptionCache &(Function &)> - *GetAssumptionCache = nullptr) - : CG(cg), GetAssumptionCache(GetAssumptionCache) {} + *GetAssumptionCache = nullptr, + BlockFrequencyInfo *CallerBFI = nullptr, + BlockFrequencyInfo *CalleeBFI = nullptr) + : CG(cg), GetAssumptionCache(GetAssumptionCache), CallerBFI(CallerBFI), + CalleeBFI(CalleeBFI) {} /// CG - If non-null, InlineFunction will update the callgraph to reflect the /// changes it makes. CallGraph *CG; std::function<AssumptionCache &(Function &)> *GetAssumptionCache; + BlockFrequencyInfo *CallerBFI, *CalleeBFI; /// StaticAllocas - InlineFunction fills this in with all static allocas that /// get copied into the caller. @@ -245,6 +245,16 @@ Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks, ValueToValueMapTy &VMap); -} // End llvm namespace +/// Split edge between BB and PredBB and duplicate all non-Phi instructions +/// from BB between its beginning and the StopAt instruction into the split +/// block. Phi nodes are not duplicated, but their uses are handled correctly: +/// we replace them with the uses of corresponding Phi inputs. ValueMapping +/// is used to map the original instructions from BB to their newly-created +/// copies. Returns the split block. +BasicBlock * +DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, + Instruction *StopAt, + ValueToValueMapTy &ValueMapping); +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_CLONING_H diff --git a/include/llvm/Transforms/Utils/FunctionComparator.h b/include/llvm/Transforms/Utils/FunctionComparator.h index a613fc31a5e30..ee58d1d138f74 100644 --- a/include/llvm/Transforms/Utils/FunctionComparator.h +++ b/include/llvm/Transforms/Utils/FunctionComparator.h @@ -314,7 +314,7 @@ protected: private: int cmpOrderings(AtomicOrdering L, AtomicOrdering R) const; int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const; - int cmpAttrs(const AttributeSet L, const AttributeSet R) const; + int cmpAttrs(const AttributeList L, const AttributeList R) const; int cmpRangeMetadata(const MDNode *L, const MDNode *R) const; int cmpOperandBundlesSchema(const Instruction *L, const Instruction *R) const; diff --git a/include/llvm/Transforms/Utils/FunctionImportUtils.h b/include/llvm/Transforms/Utils/FunctionImportUtils.h index f18cd92310b4a..b9fbef04cdc3d 100644 --- a/include/llvm/Transforms/Utils/FunctionImportUtils.h +++ b/include/llvm/Transforms/Utils/FunctionImportUtils.h @@ -32,7 +32,7 @@ class FunctionImportGlobalProcessing { /// Globals to import from this module, all other functions will be /// imported as declarations instead of definitions. - DenseSet<const GlobalValue *> *GlobalsToImport; + SetVector<GlobalValue *> *GlobalsToImport; /// Set to true if the given ModuleSummaryIndex contains any functions /// from this source module, in which case we must conservatively assume @@ -85,7 +85,7 @@ class FunctionImportGlobalProcessing { public: FunctionImportGlobalProcessing( Module &M, const ModuleSummaryIndex &Index, - DenseSet<const GlobalValue *> *GlobalsToImport = nullptr) + SetVector<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 @@ -104,16 +104,15 @@ public: bool run(); - static bool - doImportAsDefinition(const GlobalValue *SGV, - DenseSet<const GlobalValue *> *GlobalsToImport); + static bool doImportAsDefinition(const GlobalValue *SGV, + SetVector<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); + SetVector<GlobalValue *> *GlobalsToImport = nullptr); } // End llvm namespace diff --git a/include/llvm/Transforms/Utils/GlobalStatus.h b/include/llvm/Transforms/Utils/GlobalStatus.h index c36609508808d..8cc265bdf81d2 100644 --- a/include/llvm/Transforms/Utils/GlobalStatus.h +++ b/include/llvm/Transforms/Utils/GlobalStatus.h @@ -10,11 +10,13 @@ #ifndef LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H #define LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H -#include "llvm/IR/Instructions.h" +#include "llvm/Support/AtomicOrdering.h" namespace llvm { -class Value; + +class Constant; class Function; +class Value; /// It is safe to destroy a constant iff it is only used by constants itself. /// Note that constants cannot be cyclic, so this test is pretty easy to @@ -27,11 +29,11 @@ bool isSafeToDestroyConstant(const Constant *C); /// accurate. struct GlobalStatus { /// True if the global's address is used in a comparison. - bool IsCompared; + bool IsCompared = false; /// True if the global is ever loaded. If the global isn't ever loaded it /// can be deleted. - bool IsLoaded; + bool IsLoaded = false; /// Keep track of what stores to the global look like. enum StoredType { @@ -51,32 +53,33 @@ struct GlobalStatus { /// This global is stored to by multiple values or something else that we /// cannot track. Stored - } StoredType; + } StoredType = NotStored; /// If only one value (besides the initializer constant) is ever stored to /// this global, keep track of what value it is. - Value *StoredOnceValue; + Value *StoredOnceValue = nullptr; /// These start out null/false. When the first accessing function is noticed, /// it is recorded. When a second different accessing function is noticed, /// HasMultipleAccessingFunctions is set to true. - const Function *AccessingFunction; - bool HasMultipleAccessingFunctions; + const Function *AccessingFunction = nullptr; + bool HasMultipleAccessingFunctions = false; /// Set to true if this global has a user that is not an instruction (e.g. a /// constant expr or GV initializer). - bool HasNonInstructionUser; + bool HasNonInstructionUser = false; /// Set to the strongest atomic ordering requirement. - AtomicOrdering Ordering; + AtomicOrdering Ordering = AtomicOrdering::NotAtomic; + + GlobalStatus(); /// Look at all uses of the global and fill in the GlobalStatus structure. If /// the global has its address taken, return true to indicate we can't do /// anything with it. static bool analyzeGlobal(const Value *V, GlobalStatus &GS); - - GlobalStatus(); }; -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 490a765c3fabc..4933712fb8adc 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -49,8 +49,6 @@ class LazyValueInfo; template<typename T> class SmallVectorImpl; -typedef SmallVector<DbgValueInst *, 1> DbgValueList; - //===----------------------------------------------------------------------===// // Local constant propagation. // @@ -74,6 +72,12 @@ bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI = nullptr); +/// Return true if the result produced by the instruction would have no side +/// effects if it was not used. This is equivalent to checking whether +/// isInstructionTriviallyDead would be true if the use count was 0. +bool wouldInstructionBeTriviallyDead(Instruction *I, + const TargetLibraryInfo *TLI = nullptr); + /// 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. @@ -138,7 +142,8 @@ bool EliminateDuplicatePHINodes(BasicBlock *BB); /// eliminate. bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, - SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr); + SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr, + bool LateSimplifyCFG = false); /// 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 @@ -278,8 +283,11 @@ bool LowerDbgDeclare(Function &F); /// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any. DbgDeclareInst *FindAllocaDbgDeclare(Value *V); -/// Finds the llvm.dbg.value intrinsics corresponding to an alloca, if any. -void FindAllocaDbgValues(DbgValueList &DbgValues, Value *V); +/// Finds the llvm.dbg.value intrinsics describing a value. +void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V); + +/// Constants for \p replaceDbgDeclare and friends. +enum { NoDeref = false, WithDeref = true }; /// 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 @@ -306,6 +314,11 @@ bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, int Offset = 0); +/// Assuming the instruction \p I is going to be deleted, attempt to salvage any +/// dbg.value intrinsics referring to \p I by rewriting its effect into a +/// DIExpression. +void salvageDebugInfo(Instruction &I); + /// Remove all instructions from a basic block other than it's terminator /// and any present EH pad instructions. unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 27b45c4fa9416..a1cf41d6f931a 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -1,4 +1,4 @@ -//===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- C++ -*-=========// +//===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,23 +14,29 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/Casting.h" namespace llvm { + class AliasSet; class AliasSetTracker; -class AssumptionCache; class BasicBlock; class DataLayout; -class DominatorTree; class Loop; class LoopInfo; class OptimizationRemarkEmitter; -class Pass; class PredicatedScalarEvolution; class PredIteratorCache; class ScalarEvolution; @@ -40,12 +46,13 @@ class TargetLibraryInfo; /// \brief Captures loop safety information. /// It keep information for loop & its header may throw exception. struct LoopSafetyInfo { - bool MayThrow; // The current loop contains an instruction which - // may throw. - bool HeaderMayThrow; // Same as previous, but specific to loop header + bool MayThrow = false; // The current loop contains an instruction which + // may throw. + bool HeaderMayThrow = false; // Same as previous, but specific to loop header // Used to update funclet bundle operands. DenseMap<BasicBlock *, ColorVector> BlockColors; - LoopSafetyInfo() : MayThrow(false), HeaderMayThrow(false) {} + + LoopSafetyInfo() = default; }; /// The RecurrenceDescriptor is used to identify recurrences variables in a @@ -61,7 +68,6 @@ struct LoopSafetyInfo { /// This struct holds information about recurrence variables. class RecurrenceDescriptor { - public: /// This enum represents the kinds of recurrences that we support. enum RecurrenceKind { @@ -88,10 +94,7 @@ public: MRK_FloatMax }; - RecurrenceDescriptor() - : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence), - MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr), - RecurrenceType(nullptr), IsSigned(false) {} + RecurrenceDescriptor() = default; RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, @@ -103,7 +106,6 @@ public: /// This POD struct holds information about a potential recurrence operation. class InstDesc { - public: InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr) : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid), @@ -242,17 +244,17 @@ private: // It does not have to be zero! TrackingVH<Value> StartValue; // The instruction who's value is used outside the loop. - Instruction *LoopExitInstr; + Instruction *LoopExitInstr = nullptr; // The kind of the recurrence. - RecurrenceKind Kind; + RecurrenceKind Kind = RK_NoRecurrence; // If this a min/max recurrence the kind of recurrence. - MinMaxRecurrenceKind MinMaxKind; + MinMaxRecurrenceKind MinMaxKind = MRK_Invalid; // First occurrence of unasfe algebra in the PHI's use-chain. - Instruction *UnsafeAlgebraInst; + Instruction *UnsafeAlgebraInst = nullptr; // The type of the recurrence. - Type *RecurrenceType; + Type *RecurrenceType = nullptr; // True if all source operands of the recurrence are SExtInsts. - bool IsSigned; + bool IsSigned = false; // Instructions used for type-promoting the recurrence. SmallPtrSet<Instruction *, 8> CastInsts; }; @@ -270,9 +272,7 @@ public: public: /// Default constructor - creates an invalid induction. - InductionDescriptor() - : StartValue(nullptr), IK(IK_NoInduction), Step(nullptr), - InductionBinOp(nullptr) {} + InductionDescriptor() = default; /// Get the consecutive direction. Returns: /// 0 - unknown or non-consecutive. @@ -350,11 +350,11 @@ private: /// Start value. TrackingVH<Value> StartValue; /// Induction kind. - InductionKind IK; + InductionKind IK = IK_NoInduction; /// Step value. - const SCEV *Step; + const SCEV *Step = nullptr; // Instruction that advances induction variable. - BinaryOperator *InductionBinOp; + BinaryOperator *InductionBinOp = nullptr; }; BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, @@ -488,6 +488,7 @@ bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE = nullptr); -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H diff --git a/include/llvm/Transforms/Utils/LowerMemIntrinsics.h b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h new file mode 100644 index 0000000000000..e4906b709e4bf --- /dev/null +++ b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h @@ -0,0 +1,44 @@ +//===- llvm/Transforms/Utils/LowerMemintrinsics.h ---------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Lower memset, memcpy, memmov intrinsics to loops (e.g. for targets without +// library support). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOWERMEMINTRINSICS_H +#define LLVM_TRANSFORMS_UTILS_LOWERMEMINTRINSICS_H + +namespace llvm { + +class Instruction; +class MemCpyInst; +class MemMoveInst; +class MemSetInst; +class Value; + +/// Emit a loop implementing the semantics of llvm.memcpy with the equivalent +/// arguments at \p InsertBefore. +void createMemCpyLoop(Instruction *InsertBefore, + Value *SrcAddr, Value *DstAddr, Value *CopyLen, + unsigned SrcAlign, unsigned DestAlign, + bool SrcIsVolatile, bool DstIsVolatile); + +/// Expand \p MemCpy as a loop. \p MemCpy is not deleted. +void expandMemCpyAsLoop(MemCpyInst *MemCpy); + +/// Expand \p MemMove as a loop. \p MemMove is not deleted. +void expandMemMoveAsLoop(MemMoveInst *MemMove); + +/// Expand \p MemSet as a loop. \p MemSet is not deleted. +void expandMemSetAsLoop(MemSetInst *MemSet); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Transforms/Utils/MemorySSA.h b/include/llvm/Transforms/Utils/MemorySSA.h deleted file mode 100644 index 408c6a157cd01..0000000000000 --- a/include/llvm/Transforms/Utils/MemorySSA.h +++ /dev/null @@ -1,1014 +0,0 @@ -//===- 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; -enum { - // Used to signify what the default invalid ID is for MemoryAccess's - // getID() - INVALID_MEMORYACCESS_ID = 0 -}; - -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 for debugging and tracking things about MemoryAccesses. - /// Guaranteed unique among MemoryAccesses, no guarantees otherwise. - 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; -}; - -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), OptimizedID(0) {} - - 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; - void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) { - if (Optimized) - OptimizedID = DMA->getID(); - MemoryUseOrDef::setDefiningAccess(DMA); - } - bool isOptimized() const { - return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID(); - } - /// \brief Reset the ID of what this MemoryUse was optimized to, causing it to - /// be rewalked by the walker if necessary. - /// This really should only be called by tests. - void resetOptimized() { OptimizedID = INVALID_MEMORYACCESS_ID; } - -protected: - friend class MemorySSA; - - unsigned getID() const override { - llvm_unreachable("MemoryUses do not have IDs"); - } - -private: - unsigned int OptimizedID; -}; - -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; - - 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(); - } - - iterator_range<block_iterator> blocks() { - return make_range(block_begin(), block_end()); - } - - iterator_range<const_block_iterator> blocks() const { - return make_range(block_begin(), block_end()); - } - - 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); - } - - 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(); - - 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. - MemoryUseOrDef *getMemoryAccess(const Instruction *) 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 { - return getWritableBlockAccesses(BB); - } - - /// \brief Create an empty MemoryPhi in MemorySSA for a given basic block. - /// Only one MemoryPhi for a block exists at a time, so this function will - /// assert if you try to create one where it already exists. - 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. - /// Note: If a MemoryAccess already exists for I, this function will make it - /// inaccessible and it *must* have removeMemoryAccess called on it. - 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. - /// Note: If a MemoryAccess already exists for I, this function will make it - /// inaccessible and it *must* have removeMemoryAccess called on it. - MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, - MemoryAccess *Definition, - MemoryUseOrDef *InsertPt); - MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, - MemoryAccess *Definition, - MemoryAccess *InsertPt); - - // \brief Splice \p What to just before \p Where. - // - // In order to be efficient, the following conditions must be met: - // - \p Where dominates \p What, - // - All memory accesses in [\p Where, \p What) are no-alias with \p What. - // - // TODO: relax the MemoryDef requirement on Where. - void spliceMemoryAccessAbove(MemoryDef *Where, MemoryUseOrDef *What); - - /// \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 Given two memory accesses in potentially different blocks, - /// determine whether MemoryAccess \p A dominates MemoryAccess \p B. - bool dominates(const MemoryAccess *A, const MemoryAccess *B) const; - - /// \brief Given a MemoryAccess and a Use, determine whether MemoryAccess \p A - /// dominates Use \p B. - bool dominates(const MemoryAccess *A, const Use &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; - - // This is used by the use optimizer class - AccessList *getWritableBlockAccesses(const BasicBlock *BB) const { - auto It = PerBlockAccesses.find(BB); - return It == PerBlockAccesses.end() ? nullptr : It->second.get(); - } - -private: - class CachingWalker; - class OptimizeUses; - - CachingWalker *getWalkerImpl(); - void buildMemorySSA(); - void optimizeUses(); - - 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 *); - - void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &, - const DenseMap<const BasicBlock *, unsigned int> &); - MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *); - void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, - SmallPtrSet<BasicBlock *, 16> &Visited); - AccessList *getOrCreateAccessList(const BasicBlock *); - void renumberBlock(const BasicBlock *) const; - - AliasAnalysis *AA; - DominatorTree *DT; - Function &F; - - // Memory SSA mappings - DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess; - AccessMap PerBlockAccesses; - std::unique_ptr<MemoryAccess> LiveOnEntryDef; - - // Domination mappings - // Note that the numbering is local to a block, even though the map is - // global. - mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid; - mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering; - - // 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 AnalysisKey Key; - -public: - // Wrap MemorySSA result to ensure address stability of internal MemorySSA - // pointers after construction. Use a wrapper class instead of plain - // unique_ptr<MemorySSA> to avoid build breakage on MSVC. - struct Result { - Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {} - MemorySSA &getMSSA() { return *MSSA.get(); } - - std::unique_ptr<MemorySSA> MSSA; - }; - - Result run(Function &F, FunctionAnalysisManager &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, FunctionAnalysisManager &AM); -}; - -/// \brief Verifier pass for \c MemorySSA. -struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> { - PreservedAnalyses run(Function &F, FunctionAnalysisManager &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. - MemoryAccess *getClobberingMemoryAccess(const Instruction *I) { - MemoryAccess *MA = MSSA->getMemoryAccess(I); - assert(MA && "Handed an instruction that MemorySSA doesn't recognize?"); - return getClobberingMemoryAccess(MA); - } - - /// Does the same thing as getClobberingMemoryAccess(const Instruction *I), - /// but takes a MemoryAccess instead of an Instruction. - virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 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 *, - const 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 *) {} - - virtual void verify(const MemorySSA *MSSA) { assert(MSSA == this->MSSA); } - -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: - // Keep the overrides below from hiding the Instruction overload of - // getClobberingMemoryAccess. - using MemorySSAWalker::getClobberingMemoryAccess; - MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override; - MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, - const 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 NodeRef = MemoryAccess *; - using ChildIteratorType = memoryaccess_def_iterator; - - static NodeRef getEntryNode(NodeRef N) { return N; } - static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); } - static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); } -}; - -template <> struct GraphTraits<Inverse<MemoryAccess *>> { - using NodeRef = MemoryAccess *; - using ChildIteratorType = MemoryAccess::iterator; - - static NodeRef getEntryNode(NodeRef N) { return N; } - static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); } - static ChildIteratorType child_end(NodeRef 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(); } - -// Return true when MD may alias MU, return false otherwise. -bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, - AliasAnalysis &AA); - -} // 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 27508799f8e0f..f5e843e2e8b55 100644 --- a/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/include/llvm/Transforms/Utils/ModuleUtils.h @@ -46,6 +46,9 @@ void appendToGlobalDtors(Module &M, Function *F, int Priority, // getOrInsertFunction returns a bitcast. Function *checkSanitizerInterfaceFunction(Constant *FuncOrBitcast); +Function *declareSanitizerInitFunction(Module &M, StringRef InitName, + ArrayRef<Type *> InitArgTypes); + /// \brief Creates sanitizer constructor function, and calls sanitizer's init /// function from it. /// \return Returns pair of pointers to constructor, and init functions diff --git a/include/llvm/Transforms/Utils/NameAnonGlobals.h b/include/llvm/Transforms/Utils/NameAnonGlobals.h index 4bec361674bb4..17fc902eebf88 100644 --- a/include/llvm/Transforms/Utils/NameAnonGlobals.h +++ b/include/llvm/Transforms/Utils/NameAnonGlobals.h @@ -1,4 +1,4 @@ -//===-- NameAnonGlobals.h - Anonymous Global Naming Pass ----*- C++ -*-=======// +//===-- NameAnonGlobals.h - Anonymous Global Naming Pass --------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -23,9 +23,11 @@ namespace llvm { /// Simple pass that provides a name to every anonymous globals. class NameAnonGlobalPass : public PassInfoMixin<NameAnonGlobalPass> { public: - NameAnonGlobalPass() {} + NameAnonGlobalPass() = default; + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_NAMEANONGLOBALS_H diff --git a/include/llvm/Transforms/Utils/PredicateInfo.h b/include/llvm/Transforms/Utils/PredicateInfo.h new file mode 100644 index 0000000000000..1322c686eb900 --- /dev/null +++ b/include/llvm/Transforms/Utils/PredicateInfo.h @@ -0,0 +1,295 @@ +//===- PredicateInfo.h - Build PredicateInfo ----------------------*-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 implements the PredicateInfo analysis, which creates an Extended +/// SSA form for operations used in branch comparisons and llvm.assume +/// comparisons. +/// +/// Copies of these operations are inserted into the true/false edge (and after +/// assumes), and information attached to the copies. All uses of the original +/// operation in blocks dominated by the true/false edge (and assume), are +/// replaced with uses of the copies. This enables passes to easily and sparsely +/// propagate condition based info into the operations that may be affected. +/// +/// Example: +/// %cmp = icmp eq i32 %x, 50 +/// br i1 %cmp, label %true, label %false +/// true: +/// ret i32 %x +/// false: +/// ret i32 1 +/// +/// will become +/// +/// %cmp = icmp eq i32, %x, 50 +/// br i1 %cmp, label %true, label %false +/// true: +/// %x.0 = call @llvm.ssa_copy.i32(i32 %x) +/// ret i32 %x.0 +/// false: +/// ret i32 1 +/// +/// Using getPredicateInfoFor on x.0 will give you the comparison it is +/// dominated by (the icmp), and that you are located in the true edge of that +/// comparison, which tells you x.0 is 50. +/// +/// In order to reduce the number of copies inserted, predicateinfo is only +/// inserted where it would actually be live. This means if there are no uses of +/// an operation dominated by the branch edges, or by an assume, the associated +/// predicate info is never inserted. +/// +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H +#define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.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/AssumptionCache.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.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; +class OrderedBasicBlock; + +enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; + +// Base class for all predicate information we provide. +// All of our predicate information has at least a comparison. +class PredicateBase : public ilist_node<PredicateBase> { +public: + PredicateType Type; + // The original operand before we renamed it. + // This can be use by passes, when destroying predicateinfo, to know + // whether they can just drop the intrinsic, or have to merge metadata. + Value *OriginalOp; + PredicateBase(const PredicateBase &) = delete; + PredicateBase &operator=(const PredicateBase &) = delete; + PredicateBase() = delete; + virtual ~PredicateBase() = default; + +protected: + PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {} +}; + +class PredicateWithCondition : public PredicateBase { +public: + Value *Condition; + static inline bool classof(const PredicateBase *PB) { + return PB->Type == PT_Assume || PB->Type == PT_Branch || PB->Type == PT_Switch; + } + +protected: + PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition) + : PredicateBase(PT, Op), Condition(Condition) {} +}; + +// Provides predicate information for assumes. Since assumes are always true, +// we simply provide the assume instruction, so you can tell your relative +// position to it. +class PredicateAssume : public PredicateWithCondition { +public: + IntrinsicInst *AssumeInst; + PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) + : PredicateWithCondition(PT_Assume, Op, Condition), + AssumeInst(AssumeInst) {} + PredicateAssume() = delete; + static inline bool classof(const PredicateBase *PB) { + return PB->Type == PT_Assume; + } +}; + +// Mixin class for edge predicates. The FROM block is the block where the +// predicate originates, and the TO block is the block where the predicate is +// valid. +class PredicateWithEdge : public PredicateWithCondition { +public: + BasicBlock *From; + BasicBlock *To; + PredicateWithEdge() = delete; + static inline bool classof(const PredicateBase *PB) { + return PB->Type == PT_Branch || PB->Type == PT_Switch; + } + +protected: + PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, + BasicBlock *To, Value *Cond) + : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {} +}; + +// Provides predicate information for branches. +class PredicateBranch : public PredicateWithEdge { +public: + // If true, SplitBB is the true successor, otherwise it's the false successor. + bool TrueEdge; + PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, + Value *Condition, bool TakenEdge) + : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition), + TrueEdge(TakenEdge) {} + PredicateBranch() = delete; + static inline bool classof(const PredicateBase *PB) { + return PB->Type == PT_Branch; + } +}; + +class PredicateSwitch : public PredicateWithEdge { +public: + Value *CaseValue; + // This is the switch instruction. + SwitchInst *Switch; + PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, + Value *CaseValue, SwitchInst *SI) + : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB, + SI->getCondition()), + CaseValue(CaseValue), Switch(SI) {} + PredicateSwitch() = delete; + static inline bool classof(const PredicateBase *PB) { + return PB->Type == PT_Switch; + } +}; + +// This name is used in a few places, so kick it into their own namespace +namespace PredicateInfoClasses { +struct ValueDFS; +} + +/// \brief Encapsulates PredicateInfo, including all data associated with memory +/// accesses. +class PredicateInfo { +private: + // Used to store information about each value we might rename. + struct ValueInfo { + // Information about each possible copy. During processing, this is each + // inserted info. After processing, we move the uninserted ones to the + // uninserted vector. + SmallVector<PredicateBase *, 4> Infos; + SmallVector<PredicateBase *, 4> UninsertedInfos; + }; + // This owns the all the predicate infos in the function, placed or not. + iplist<PredicateBase> AllInfos; + +public: + PredicateInfo(Function &, DominatorTree &, AssumptionCache &); + ~PredicateInfo(); + + void verifyPredicateInfo() const; + + void dump() const; + void print(raw_ostream &) const; + + const PredicateBase *getPredicateInfoFor(const Value *V) const { + return PredicateMap.lookup(V); + } + +protected: + // Used by PredicateInfo annotater, dumpers, and wrapper pass. + friend class PredicateInfoAnnotatedWriter; + friend class PredicateInfoPrinterLegacyPass; + +private: + void buildPredicateInfo(); + void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); + void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); + void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); + void renameUses(SmallPtrSetImpl<Value *> &); + using ValueDFS = PredicateInfoClasses::ValueDFS; + typedef SmallVectorImpl<ValueDFS> ValueDFSStack; + void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &); + Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); + bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; + void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); + ValueInfo &getOrCreateValueInfo(Value *); + void addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op, + PredicateBase *PB); + const ValueInfo &getValueInfo(Value *) const; + Function &F; + DominatorTree &DT; + AssumptionCache &AC; + // This maps from copy operands to Predicate Info. Note that it does not own + // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos + // vector. + DenseMap<const Value *, const PredicateBase *> PredicateMap; + // This stores info about each operand or comparison result we make copies + // of. The real ValueInfos start at index 1, index 0 is unused so that we can + // more easily detect invalid indexing. + SmallVector<ValueInfo, 32> ValueInfos; + // This gives the index into the ValueInfos array for a given Value. Because + // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell + // whether it returned a valid result. + DenseMap<Value *, unsigned int> ValueInfoNums; + // OrderedBasicBlocks used during sorting uses + DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> OBBMap; + // The set of edges along which we can only handle phi uses, due to critical + // edges. + DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly; +}; + +// This pass does eager building and then printing of PredicateInfo. It is used +// by +// the tests to be able to build, dump, and verify PredicateInfo. +class PredicateInfoPrinterLegacyPass : public FunctionPass { +public: + PredicateInfoPrinterLegacyPass(); + + static char ID; + bool runOnFunction(Function &) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +/// \brief Printer pass for \c PredicateInfo. +class PredicateInfoPrinterPass + : public PassInfoMixin<PredicateInfoPrinterPass> { + raw_ostream &OS; + +public: + explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +/// \brief Verifier pass for \c PredicateInfo. +struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h index b548072c413ea..bb8a61a474f20 100644 --- a/include/llvm/Transforms/Utils/PromoteMemToReg.h +++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h @@ -38,10 +38,7 @@ bool isAllocaPromotable(const AllocaInst *AI); /// does not modify the CFG of the function at all. All allocas must be from /// the same function. /// -/// If AST is specified, the specified tracker is updated to reflect changes -/// made to the IR. void PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT, - AliasSetTracker *AST = nullptr, AssumptionCache *AC = nullptr); } // End llvm namespace diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 9f98bac22dc91..8cbcdf47156ea 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -15,19 +15,20 @@ #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H #include "llvm/ADT/StringRef.h" -#include "llvm/Support/Compiler.h" +#include <string> namespace llvm { - class BasicBlock; - class Instruction; - class LoadInst; - template <typename T> class ArrayRef; - template <typename T> class SmallVectorImpl; - template <typename T> class SSAUpdaterTraits; - class PHINode; - class Type; - class Use; - class Value; + +class BasicBlock; +class Instruction; +class LoadInst; +template <typename T> class ArrayRef; +template <typename T> class SmallVectorImpl; +template <typename T> class SSAUpdaterTraits; +class PHINode; +class Type; +class Use; +class Value; /// \brief Helper class for SSA formation on a set of values defined in /// multiple blocks. @@ -42,10 +43,10 @@ private: /// This keeps track of which value to use on a per-block basis. When we /// insert PHI nodes, we keep track of them here. //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; - void *AV; + void *AV = nullptr; /// ProtoType holds the type of the values being rewritten. - Type *ProtoType; + Type *ProtoType = nullptr; /// PHI nodes are given a name based on ProtoName. std::string ProtoName; @@ -58,6 +59,8 @@ public: /// If InsertedPHIs is specified, it will be filled /// in with all PHI Nodes created by rewriting. explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = nullptr); + SSAUpdater(const SSAUpdater &) = delete; + SSAUpdater &operator=(const SSAUpdater &) = delete; ~SSAUpdater(); /// \brief Reset this object to get ready for a new set of SSA updates with @@ -118,9 +121,6 @@ public: private: Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); - - void operator=(const SSAUpdater&) = delete; - SSAUpdater(const SSAUpdater&) = delete; }; /// \brief Helper class for promoting a collection of loads and stores into SSA @@ -138,7 +138,7 @@ protected: public: LoadAndStorePromoter(ArrayRef<const Instruction*> Insts, SSAUpdater &S, StringRef Name = StringRef()); - virtual ~LoadAndStorePromoter() {} + virtual ~LoadAndStorePromoter() = default; /// \brief This does the promotion. /// @@ -173,6 +173,6 @@ public: } }; -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index 90438ee699fe1..6cdeeeb60a65b 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -22,7 +22,6 @@ namespace llvm { class CastInst; class DominatorTree; -class IVUsers; class Loop; class LoopInfo; class PHINode; @@ -32,13 +31,13 @@ class ScalarEvolution; /// simplified by this utility. class IVVisitor { protected: - const DominatorTree *DT; + const DominatorTree *DT = nullptr; virtual void anchor(); public: - IVVisitor() : DT(nullptr) {} - virtual ~IVVisitor() {} + IVVisitor() = default; + virtual ~IVVisitor() = default; const DominatorTree *getDomTree() const { return DT; } virtual void visitCast(CastInst *Cast) = 0; @@ -55,6 +54,6 @@ bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead); -} // namespace llvm +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_SIMPLIFYINDVAR_H diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h index 5e217adf19873..665dd6f4b2579 100644 --- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -56,8 +56,8 @@ private: Value *optimizeMemSetChk(CallInst *CI, IRBuilder<> &B); // Str/Stp cpy are similar enough to be handled in the same functions. - Value *optimizeStrpCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc::Func Func); - Value *optimizeStrpNCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc::Func Func); + Value *optimizeStrpCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func); + Value *optimizeStrpNCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func); /// \brief Checks whether the call \p CI to a fortified libcall is foldable /// to the non-fortified version. @@ -128,7 +128,6 @@ private: Value *optimizeCos(CallInst *CI, IRBuilder<> &B); Value *optimizePow(CallInst *CI, IRBuilder<> &B); Value *optimizeExp2(CallInst *CI, IRBuilder<> &B); - Value *optimizeFabs(CallInst *CI, IRBuilder<> &B); Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B); Value *optimizeLog(CallInst *CI, IRBuilder<> &B); Value *optimizeSqrt(CallInst *CI, IRBuilder<> &B); diff --git a/include/llvm/Transforms/Utils/SymbolRewriter.h b/include/llvm/Transforms/Utils/SymbolRewriter.h index ff995173e1263..93658989fba57 100644 --- a/include/llvm/Transforms/Utils/SymbolRewriter.h +++ b/include/llvm/Transforms/Utils/SymbolRewriter.h @@ -36,18 +36,24 @@ #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include <list> +#include <memory> +#include <string> namespace llvm { + class MemoryBuffer; namespace yaml { + class KeyValueNode; class MappingNode; class ScalarNode; class Stream; -} + +} // end namespace yaml namespace SymbolRewriter { + /// The basic entity representing a rewrite operation. It serves as the base /// class for any rewrite descriptor. It has a certain set of specializations /// which describe a particular rewrite. @@ -60,11 +66,6 @@ namespace SymbolRewriter { /// select the symbols to rewrite. This descriptor list is passed to the /// SymbolRewriter pass. class RewriteDescriptor { - RewriteDescriptor(const RewriteDescriptor &) = delete; - - const RewriteDescriptor & - operator=(const RewriteDescriptor &) = delete; - public: enum class Type { Invalid, /// invalid @@ -73,7 +74,9 @@ public: NamedAlias, /// named alias - descriptor rewrites a global alias }; - virtual ~RewriteDescriptor() {} + RewriteDescriptor(const RewriteDescriptor &) = delete; + RewriteDescriptor &operator=(const RewriteDescriptor &) = delete; + virtual ~RewriteDescriptor() = default; Type getType() const { return Kind; } @@ -108,7 +111,8 @@ private: yaml::MappingNode *V, RewriteDescriptorList *DL); }; -} + +} // end namespace SymbolRewriter ModulePass *createRewriteSymbolsPass(); ModulePass *createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &); @@ -130,6 +134,7 @@ private: SymbolRewriter::RewriteDescriptorList Descriptors; }; -} + +} // end namespace llvm #endif //LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H diff --git a/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h b/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h index 550292f6b7a3b..222c601ad6084 100644 --- a/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h +++ b/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h @@ -19,16 +19,18 @@ #define LLVM_TRANSFORMS_UTILS_UNIFYFUNCTIONEXITNODES_H #include "llvm/Pass.h" +#include "llvm/PassRegistry.h" namespace llvm { struct UnifyFunctionExitNodes : public FunctionPass { - BasicBlock *ReturnBlock, *UnwindBlock, *UnreachableBlock; + BasicBlock *ReturnBlock = nullptr; + BasicBlock *UnwindBlock = nullptr; + BasicBlock *UnreachableBlock; public: static char ID; // Pass identification, replacement for typeid - UnifyFunctionExitNodes() : FunctionPass(ID), - ReturnBlock(nullptr), UnwindBlock(nullptr) { + UnifyFunctionExitNodes() : FunctionPass(ID) { initializeUnifyFunctionExitNodesPass(*PassRegistry::getPassRegistry()); } @@ -47,6 +49,6 @@ public: Pass *createUnifyFunctionExitNodesPass(); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_UNIFYFUNCTIONEXITNODES_H diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h index f322bea7aa2e8..a3115ad16914d 100644 --- a/include/llvm/Transforms/Utils/UnrollLoop.h +++ b/include/llvm/Transforms/Utils/UnrollLoop.h @@ -53,10 +53,11 @@ bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool PreserveLCSSA); void computePeelCount(Loop *L, unsigned LoopSize, - TargetTransformInfo::UnrollingPreferences &UP); + TargetTransformInfo::UnrollingPreferences &UP, + unsigned &TripCount); bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, - DominatorTree *DT, bool PreserveLCSSA); + DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); } diff --git a/include/llvm/Transforms/Utils/VNCoercion.h b/include/llvm/Transforms/Utils/VNCoercion.h new file mode 100644 index 0000000000000..1baa9b66e4919 --- /dev/null +++ b/include/llvm/Transforms/Utils/VNCoercion.h @@ -0,0 +1,108 @@ +//===- VNCoercion.h - Value Numbering Coercion Utilities --------*- 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 routines used by LLVM's value numbering passes to +/// perform various forms of value extraction from memory when the types are not +/// identical. For example, given +/// +/// store i32 8, i32 *%foo +/// %a = bitcast i32 *%foo to i16 +/// %val = load i16, i16 *%a +/// +/// It possible to extract the value of the load of %a from the store to %foo. +/// These routines know how to tell whether they can do that (the analyze* +/// routines), and can also insert the necessary IR to do it (the get* +/// routines). + +#ifndef LLVM_TRANSFORMS_UTILS_VNCOERCION_H +#define LLVM_TRANSFORMS_UTILS_VNCOERCION_H +#include "llvm/IR/IRBuilder.h" + +namespace llvm { +class Function; +class StoreInst; +class LoadInst; +class MemIntrinsic; +class Instruction; +class Value; +class Type; +class DataLayout; +namespace VNCoercion { +/// Return true if CoerceAvailableValueToLoadType would succeed if it was +/// called. +bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy, + const DataLayout &DL); + +/// If we saw a store of a value to memory, and then a load from a must-aliased +/// pointer of a different type, try to coerce the stored value to the loaded +/// type. LoadedTy is the type of the load we want to replace. IRB is +/// IRBuilder used to insert new instructions. +/// +/// If we can't do it, return null. +Value *coerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy, + IRBuilder<> &IRB, const DataLayout &DL); + +/// This function determines whether a value for the pointer LoadPtr can be +/// extracted from the store at DepSI. +/// +/// On success, it returns the offset into DepSI that extraction would start. +/// On failure, it returns -1. +int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, + StoreInst *DepSI, const DataLayout &DL); + +/// This function determines whether a value for the pointer LoadPtr can be +/// extracted from the load at DepLI. +/// +/// On success, it returns the offset into DepLI that extraction would start. +/// On failure, it returns -1. +int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, + const DataLayout &DL); + +/// This function determines whether a value for the pointer LoadPtr can be +/// extracted from the memory intrinsic at DepMI. +/// +/// On success, it returns the offset into DepMI that extraction would start. +/// On failure, it returns -1. +int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, + MemIntrinsic *DepMI, const DataLayout &DL); + +/// If analyzeLoadFromClobberingStore returned an offset, this function can be +/// used to actually perform the extraction of the bits from the store. It +/// inserts instructions to do so at InsertPt, and returns the extracted value. +Value *getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, + Instruction *InsertPt, const DataLayout &DL); +// This is the same as getStoreValueForLoad, except it performs no insertion +// It only allows constant inputs. +Constant *getConstantStoreValueForLoad(Constant *SrcVal, unsigned Offset, + Type *LoadTy, const DataLayout &DL); + +/// If analyzeLoadFromClobberingLoad returned an offset, this function can be +/// used to actually perform the extraction of the bits from the load, including +/// any necessary load widening. It inserts instructions to do so at InsertPt, +/// and returns the extracted value. +Value *getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy, + Instruction *InsertPt, const DataLayout &DL); +// This is the same as getLoadValueForLoad, except it is given the load value as +// a constant. It returns nullptr if it would require widening the load. +Constant *getConstantLoadValueForLoad(Constant *SrcVal, unsigned Offset, + Type *LoadTy, const DataLayout &DL); + +/// If analyzeLoadFromClobberingMemInst returned an offset, this function can be +/// used to actually perform the extraction of the bits from the memory +/// intrinsic. It inserts instructions to do so at InsertPt, and returns the +/// extracted value. +Value *getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, + Type *LoadTy, Instruction *InsertPt, + const DataLayout &DL); +// This is the same as getStoreValueForLoad, except it performs no insertion. +// It returns nullptr if it cannot produce a constant. +Constant *getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, + Type *LoadTy, const DataLayout &DL); +} +} +#endif diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h index de649009612cb..950ad92afcd74 100644 --- a/include/llvm/Transforms/Utils/ValueMapper.h +++ b/include/llvm/Transforms/Utils/ValueMapper.h @@ -15,7 +15,9 @@ #ifndef LLVM_TRANSFORMS_UTILS_VALUEMAPPER_H #define LLVM_TRANSFORMS_UTILS_VALUEMAPPER_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/IR/ValueMap.h" +#include "llvm/IR/ValueHandle.h" namespace llvm { @@ -27,8 +29,9 @@ typedef ValueMap<const Value *, WeakVH> ValueToValueMapTy; /// cloning constants and instructions. class ValueMapTypeRemapper { virtual void anchor(); // Out of line method. + public: - virtual ~ValueMapTypeRemapper() {} + virtual ~ValueMapTypeRemapper() = default; /// The client should implement this method if they want to remap types while /// mapping values. @@ -92,8 +95,6 @@ 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 @@ -133,15 +134,14 @@ class ValueMapperImpl; 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(ValueMapper &&) = delete; + ValueMapper(const ValueMapper &) = delete; + ValueMapper &operator=(ValueMapper &&) = delete; + ValueMapper &operator=(const ValueMapper &) = delete; ~ValueMapper(); /// Register an alternate mapping context. @@ -268,6 +268,6 @@ inline Constant *MapValue(const Constant *V, ValueToValueMapTy &VM, return ValueMapper(VM, Flags, TypeMapper, Materializer).mapConstant(*V); } -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_VALUEMAPPER_H diff --git a/include/llvm/Transforms/Vectorize/SLPVectorizer.h b/include/llvm/Transforms/Vectorize/SLPVectorizer.h index 4886700774ca8..d669a8e5b615c 100644 --- a/include/llvm/Transforms/Vectorize/SLPVectorizer.h +++ b/include/llvm/Transforms/Vectorize/SLPVectorizer.h @@ -92,6 +92,12 @@ private: /// collected in GEPs. bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); + /// Try to find horizontal reduction or otherwise vectorize a chain of binary + /// operators. + bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB, + slpvectorizer::BoUpSLP &R, + TargetTransformInfo *TTI); + /// \brief Scan the basic block and look for patterns that are likely to start /// a vectorization chain. bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); |