diff options
Diffstat (limited to 'include/llvm/Transforms/Utils')
22 files changed, 623 insertions, 1157 deletions
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 3d41dbe2b954..85bb053135a6 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 2d2a85905d0e..a067a685b837 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 5eeb8cf30695..337305a0a82c 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 a613fc31a5e3..ee58d1d138f7 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 f18cd92310b4..b9fbef04cdc3 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 c36609508808..8cc265bdf81d 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 490a765c3fab..4933712fb8ad 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 27b45c4fa941..a1cf41d6f931 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 000000000000..e4906b709e4b --- /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 408c6a157cd0..000000000000 --- 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 27508799f8e0..f5e843e2e8b5 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 4bec361674bb..17fc902eebf8 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 000000000000..1322c686eb90 --- /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 b548072c413e..bb8a61a474f2 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 9f98bac22dc9..8cbcdf47156e 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 90438ee699fe..6cdeeeb60a65 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 5e217adf1987..665dd6f4b257 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 ff995173e126..93658989fba5 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 550292f6b7a3..222c601ad608 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 f322bea7aa2e..a3115ad16914 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 000000000000..1baa9b66e491 --- /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 de649009612c..950ad92afcd7 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 |