diff options
Diffstat (limited to 'include/llvm/Transforms/Utils')
25 files changed, 2063 insertions, 413 deletions
diff --git a/include/llvm/Transforms/Utils/AddDiscriminators.h b/include/llvm/Transforms/Utils/AddDiscriminators.h new file mode 100644 index 000000000000..0b3a8add6278 --- /dev/null +++ b/include/llvm/Transforms/Utils/AddDiscriminators.h @@ -0,0 +1,29 @@ +//===- AddDiscriminators.h -------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass adds DWARF discriminators to the IR. Path discriminators are used +// to decide what CFG path was taken inside sub-graphs whose instructions share +// the same line and column number information. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H +#define LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class AddDiscriminatorsPass : public PassInfoMixin<AddDiscriminatorsPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 13c856dfdc9a..37fd20925cba 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -22,7 +22,7 @@ namespace llvm { -class MemoryDependenceAnalysis; +class MemoryDependenceResults; class DominatorTree; class LoopInfo; class Instruction; @@ -31,51 +31,45 @@ class ReturnInst; class TargetLibraryInfo; class TerminatorInst; -/// DeleteDeadBlock - Delete the specified block, which must have no -/// predecessors. +/// Delete the specified block, which must have no predecessors. void DeleteDeadBlock(BasicBlock *BB); -/// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are -/// any single-entry PHI nodes in it, fold them away. This handles the case -/// when all entries to the PHI nodes in a block are guaranteed equal, such as -/// when the block has exactly one predecessor. +/// We know that BB has one predecessor. If there are any single-entry PHI nodes +/// in it, fold them away. This handles the case when all entries to the PHI +/// nodes in a block are guaranteed equal, such as when the block has exactly +/// one predecessor. void FoldSingleEntryPHINodes(BasicBlock *BB, - MemoryDependenceAnalysis *MemDep = nullptr); + MemoryDependenceResults *MemDep = nullptr); -/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it -/// is dead. Also recursively delete any operands that become dead as -/// a result. This includes tracing the def-use list from the PHI to see if -/// it is ultimately unused or if it reaches an unused cycle. Return true -/// if any PHIs were deleted. +/// Examine each PHI in the given block and delete it if it is dead. Also +/// recursively delete any operands that become dead as a result. This includes +/// tracing the def-use list from the PHI to see if it is ultimately unused or +/// if it reaches an unused cycle. Return true if any PHIs were deleted. bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); -/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, -/// if possible. The return value indicates success or failure. +/// Attempts to merge a block into its predecessor, if possible. The return +/// value indicates success or failure. bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, - MemoryDependenceAnalysis *MemDep = nullptr); + MemoryDependenceResults *MemDep = nullptr); -// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) -// with a value, then remove and delete the original instruction. -// +/// Replace all uses of an instruction (specified by BI) with a value, then +/// remove and delete the original instruction. void ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V); -// ReplaceInstWithInst - Replace the instruction specified by BI with the -// instruction specified by I. Copies DebugLoc from BI to I, if I doesn't -// already have a DebugLoc. The original instruction is deleted and BI is -// updated to point to the new instruction. -// +/// Replace the instruction specified by BI with the instruction specified by I. +/// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The +/// original instruction is deleted and BI is updated to point to the new +/// instruction. void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I); -// ReplaceInstWithInst - Replace the instruction specified by From with the -// instruction specified by To. Copies DebugLoc from BI to I, if I doesn't -// already have a DebugLoc. -// +/// Replace the instruction specified by From with the instruction specified by +/// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. void ReplaceInstWithInst(Instruction *From, Instruction *To); -/// \brief Option class for critical edge splitting. +/// Option class for critical edge splitting. /// /// This provides a builder interface for overriding the default options used /// during critical edge splitting. @@ -107,10 +101,9 @@ struct CriticalEdgeSplittingOptions { } }; -/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to -/// split the critical edge. This will update the analyses passed in through -/// the option struct. This returns the new block if the edge was split, null -/// otherwise. +/// If this edge is a critical edge, insert a new node to split the critical +/// edge. This will update the analyses passed in through the option struct. +/// This returns the new block if the edge was split, null otherwise. /// /// If MergeIdenticalEdges in the options struct is true (not the default), /// *all* edges from TI to the specified successor will be merged into the same @@ -137,11 +130,10 @@ SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Options); } -/// SplitCriticalEdge - If the edge from *PI to BB is not critical, return -/// false. Otherwise, split all edges between the two blocks and return true. -/// This updates all of the same analyses as the other SplitCriticalEdge -/// function. If P is specified, it updates the analyses -/// described above. +/// If the edge from *PI to BB is not critical, return false. Otherwise, split +/// all edges between the two blocks and return true. This updates all of the +/// same analyses as the other SplitCriticalEdge function. If P is specified, it +/// updates the analyses described above. inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, const CriticalEdgeSplittingOptions &Options = CriticalEdgeSplittingOptions()) { @@ -153,10 +145,9 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, return MadeChange; } -/// SplitCriticalEdge - If an edge from Src to Dst is critical, split the edge -/// and return true, otherwise return false. This method requires that there be -/// an edge between the two blocks. It updates the analyses -/// passed in the options struct +/// If an edge from Src to Dst is critical, split the edge and return true, +/// otherwise return false. This method requires that there be an edge between +/// the two blocks. It updates the analyses passed in the options struct inline BasicBlock * SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, const CriticalEdgeSplittingOptions &Options = @@ -171,30 +162,28 @@ SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, } } -// SplitAllCriticalEdges - Loop over all of the edges in the CFG, -// breaking critical edges as they are found. -// Returns the number of broken edges. +/// Loop over all of the edges in the CFG, breaking critical edges as they are +/// found. Returns the number of broken edges. unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options = CriticalEdgeSplittingOptions()); -/// SplitEdge - Split the edge connecting specified block. +/// Split the edge connecting specified block. BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); -/// SplitBlock - Split the specified block at the specified instruction - every -/// thing before SplitPt stays in Old and everything starting with SplitPt moves -/// to a new block. The two blocks are joined by an unconditional branch and -/// the loop info is updated. -/// +/// Split the specified block at the specified instruction - everything before +/// SplitPt stays in Old and everything starting with SplitPt moves to a new +/// block. The two blocks are joined by an unconditional branch and the loop +/// info is updated. BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); -/// SplitBlockPredecessors - This method introduces at least one new basic block -/// into the function and moves some of the predecessors of BB to be -/// predecessors of the new block. The new predecessors are indicated by the -/// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic -/// block to which predecessors from Preds are now pointing. +/// This method introduces at least one new basic block into the function and +/// moves some of the predecessors of BB to be predecessors of the new block. +/// The new predecessors are indicated by the Preds array. The new block is +/// given a suffix of 'Suffix'. Returns new basic block to which predecessors +/// from Preds are now pointing. /// /// If BB is a landingpad block then additional basicblock might be introduced. /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more @@ -211,12 +200,12 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, LoopInfo *LI = nullptr, bool PreserveLCSSA = false); -/// SplitLandingPadPredecessors - This method transforms the landing pad, -/// OrigBB, by introducing two new basic blocks into the function. One of those -/// new basic blocks gets the predecessors listed in Preds. The other basic -/// block gets the remaining predecessors of OrigBB. The landingpad instruction -/// OrigBB is clone into both of the new basic blocks. The new blocks are given -/// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector. +/// This method transforms the landing pad, OrigBB, by introducing two new basic +/// blocks into the function. One of those new basic blocks gets the +/// predecessors listed in Preds. The other basic block gets the remaining +/// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both +/// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and +/// 'Suffix2', and are returned in the NewBBs vector. /// /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but /// no other analyses. In particular, it does not preserve LoopSimplify @@ -231,19 +220,17 @@ void SplitLandingPadPredecessors(BasicBlock *OrigBB, LoopInfo *LI = nullptr, bool PreserveLCSSA = false); -/// FoldReturnIntoUncondBranch - This method duplicates the specified return -/// instruction into a predecessor which ends in an unconditional branch. If -/// the return instruction returns a value defined by a PHI, propagate the -/// right value into the return. It returns the new return instruction in the -/// predecessor. +/// This method duplicates the specified return instruction into a predecessor +/// which ends in an unconditional branch. If the return instruction returns a +/// value defined by a PHI, propagate the right value into the return. It +/// returns the new return instruction in the predecessor. ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred); -/// SplitBlockAndInsertIfThen - Split the containing block at the -/// specified instruction - everything before and including SplitBefore stays -/// in the old basic block, and everything after SplitBefore is moved to a -/// new block. The two blocks are connected by a conditional branch -/// (with value of Cmp being the condition). +/// Split the containing block at the specified instruction - everything before +/// and including SplitBefore stays in the old basic block, and everything after +/// SplitBefore is moved to a new block. The two blocks are connected by a +/// conditional branch (with value of Cmp being the condition). /// Before: /// Head /// SplitBefore @@ -259,11 +246,12 @@ ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, /// UnreachableInst, otherwise it branches to Tail. /// Returns the NewBasicBlock's terminator. /// -/// Updates DT if given. +/// Updates DT and LI if given. TerminatorInst *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights = nullptr, - DominatorTree *DT = nullptr); + DominatorTree *DT = nullptr, + LoopInfo *LI = nullptr); /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, /// but also creates the ElseBlock. @@ -284,12 +272,14 @@ void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, TerminatorInst **ElseTerm, MDNode *BranchWeights = nullptr); -/// -/// GetIfCondition - Check whether BB is the merge point of a if-region. +/// Check whether BB is the merge point of a if-region. /// If so, return the boolean condition that determines which entry into /// BB will be taken. Also, return by references the block that will be /// entered from if the condition is true, and the block that will be /// entered if the condition is false. +/// +/// This does no checking to see if the true/false blocks have large or unsavory +/// instructions in them. Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse); } // End llvm namespace diff --git a/include/llvm/Transforms/Utils/BuildLibCalls.h b/include/llvm/Transforms/Utils/BuildLibCalls.h index 879f295caf0c..2d2a85905d0e 100644 --- a/include/llvm/Transforms/Utils/BuildLibCalls.h +++ b/include/llvm/Transforms/Utils/BuildLibCalls.h @@ -22,94 +22,96 @@ namespace llvm { class DataLayout; class TargetLibraryInfo; - /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*. - Value *CastToCStr(Value *V, IRBuilder<> &B); - - /// EmitStrLen - Emit a call to the strlen function to the builder, for the - /// specified pointer. Ptr is required to be some pointer type, and the - /// return value has 'intptr_t' type. - Value *EmitStrLen(Value *Ptr, IRBuilder<> &B, const DataLayout &DL, + /// Analyze the name and prototype of the given function and set any + /// applicable attributes. + /// If the library function is unavailable, this doesn't modify it. + /// + /// Returns true if any attributes were set and false otherwise. + bool inferLibFuncAttributes(Function &F, const TargetLibraryInfo &TLI); + + /// Return V if it is an i8*, otherwise cast it to i8*. + Value *castToCStr(Value *V, IRBuilder<> &B); + + /// Emit a call to the strlen function to the builder, for the specified + /// pointer. Ptr is required to be some pointer type, and the return value has + /// 'intptr_t' type. + Value *emitStrLen(Value *Ptr, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitStrNLen - Emit a call to the strnlen function to the builder, for the - /// specified pointer. Ptr is required to be some pointer type, MaxLen must - /// be of size_t type, and the return value has 'intptr_t' type. - Value *EmitStrNLen(Value *Ptr, Value *MaxLen, IRBuilder<> &B, + /// Emit a call to the strnlen function to the builder, for the specified + /// pointer. Ptr is required to be some pointer type, MaxLen must be of size_t + /// type, and the return value has 'intptr_t' type. + Value *emitStrNLen(Value *Ptr, Value *MaxLen, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitStrChr - Emit a call to the strchr function to the builder, for the - /// specified pointer and character. Ptr is required to be some pointer type, - /// and the return value has 'i8*' type. - Value *EmitStrChr(Value *Ptr, char C, IRBuilder<> &B, + /// Emit a call to the strchr function to the builder, for the specified + /// pointer and character. Ptr is required to be some pointer type, and the + /// return value has 'i8*' type. + Value *emitStrChr(Value *Ptr, char C, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitStrNCmp - Emit a call to the strncmp function to the builder. - Value *EmitStrNCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, + /// Emit a call to the strncmp function to the builder. + Value *emitStrNCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitStrCpy - Emit a call to the strcpy function to the builder, for the - /// specified pointer arguments. - Value *EmitStrCpy(Value *Dst, Value *Src, IRBuilder<> &B, + /// Emit a call to the strcpy function to the builder, for the specified + /// pointer arguments. + Value *emitStrCpy(Value *Dst, Value *Src, IRBuilder<> &B, const TargetLibraryInfo *TLI, StringRef Name = "strcpy"); - /// EmitStrNCpy - Emit a call to the strncpy function to the builder, for the - /// specified pointer arguments and length. - Value *EmitStrNCpy(Value *Dst, Value *Src, Value *Len, IRBuilder<> &B, + /// Emit a call to the strncpy function to the builder, for the specified + /// pointer arguments and length. + Value *emitStrNCpy(Value *Dst, Value *Src, Value *Len, IRBuilder<> &B, const TargetLibraryInfo *TLI, StringRef Name = "strncpy"); - /// EmitMemCpyChk - Emit a call to the __memcpy_chk function to the builder. - /// This expects that the Len and ObjSize have type 'intptr_t' and Dst/Src - /// are pointers. - Value *EmitMemCpyChk(Value *Dst, Value *Src, Value *Len, Value *ObjSize, + /// Emit a call to the __memcpy_chk function to the builder. This expects that + /// the Len and ObjSize have type 'intptr_t' and Dst/Src are pointers. + Value *emitMemCpyChk(Value *Dst, Value *Src, Value *Len, Value *ObjSize, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitMemChr - Emit a call to the memchr function. This assumes that Ptr is - /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value. - Value *EmitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B, + /// Emit a call to the memchr function. This assumes that Ptr is a pointer, + /// Val is an i32 value, and Len is an 'intptr_t' value. + Value *emitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitMemCmp - Emit a call to the memcmp function. - Value *EmitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, + /// Emit a call to the memcmp function. + Value *emitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); - /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' - /// (e.g. 'floor'). This function is known to take a single of type matching - /// 'Op' and returns one value with the same type. If 'Op' is a long double, - /// 'l' is added as the suffix of name, if 'Op' is a float, we add a 'f' - /// suffix. - Value *EmitUnaryFloatFnCall(Value *Op, StringRef Name, IRBuilder<> &B, + /// Emit a call to the unary function named 'Name' (e.g. 'floor'). This + /// function is known to take a single of type matching 'Op' and returns one + /// value with the same type. If 'Op' is a long double, 'l' is added as the + /// suffix of name, if 'Op' is a float, we add a 'f' suffix. + Value *emitUnaryFloatFnCall(Value *Op, StringRef Name, IRBuilder<> &B, const AttributeSet &Attrs); - /// EmitUnaryFloatFnCall - Emit a call to the binary function named 'Name' - /// (e.g. 'fmin'). This function is known to take type matching 'Op1' and - /// 'Op2' and return one value with the same type. If 'Op1/Op2' are long - /// double, 'l' is added as the suffix of name, if 'Op1/Op2' are float, we - /// add a 'f' suffix. - Value *EmitBinaryFloatFnCall(Value *Op1, Value *Op2, StringRef Name, + /// Emit a call to the binary function named 'Name' (e.g. 'fmin'). This + /// function is known to take type matching 'Op1' and 'Op2' and return one + /// value with the same type. If 'Op1/Op2' are long double, 'l' is added as + /// the suffix of name, if 'Op1/Op2' are float, we add a 'f' suffix. + Value *emitBinaryFloatFnCall(Value *Op1, Value *Op2, StringRef Name, IRBuilder<> &B, const AttributeSet &Attrs); - /// EmitPutChar - Emit a call to the putchar function. This assumes that Char - /// is an integer. - Value *EmitPutChar(Value *Char, IRBuilder<> &B, const TargetLibraryInfo *TLI); + /// Emit a call to the putchar function. This assumes that Char is an integer. + Value *emitPutChar(Value *Char, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitPutS - Emit a call to the puts function. This assumes that Str is - /// some pointer. - Value *EmitPutS(Value *Str, IRBuilder<> &B, const TargetLibraryInfo *TLI); + /// Emit a call to the puts function. This assumes that Str is some pointer. + Value *emitPutS(Value *Str, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitFPutC - Emit a call to the fputc function. This assumes that Char is - /// an i32, and File is a pointer to FILE. - Value *EmitFPutC(Value *Char, Value *File, IRBuilder<> &B, + /// Emit a call to the fputc function. This assumes that Char is an i32, and + /// File is a pointer to FILE. + Value *emitFPutC(Value *Char, Value *File, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitFPutS - Emit a call to the puts function. Str is required to be a - /// pointer and File is a pointer to FILE. - Value *EmitFPutS(Value *Str, Value *File, IRBuilder<> &B, + /// Emit a call to the puts function. Str is required to be a pointer and + /// File is a pointer to FILE. + Value *emitFPutS(Value *Str, Value *File, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// EmitFWrite - Emit a call to the fwrite function. This assumes that Ptr is - /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE. - Value *EmitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B, + /// Emit a call to the fwrite function. This assumes that Ptr is a pointer, + /// Size is an 'intptr_t', and File is a pointer to FILE. + Value *emitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); } diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h index 4f006f2adeef..c5fb37007090 100644 --- a/include/llvm/Transforms/Utils/Cloning.h +++ b/include/llvm/Transforms/Utils/Cloning.h @@ -59,7 +59,7 @@ std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap); /// in place of the global definition. std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap, - std::function<bool(const GlobalValue *)> ShouldCloneDefinition); + function_ref<bool(const GlobalValue *)> ShouldCloneDefinition); /// ClonedCodeInfo - This struct can be used to capture information about code /// being cloned, while it is being cloned. @@ -114,20 +114,19 @@ BasicBlock *CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix = "", Function *F = nullptr, ClonedCodeInfo *CodeInfo = nullptr); -/// CloneFunction - Return a copy of the specified function, but without -/// embedding the function into another module. Also, any references specified -/// in the VMap are changed to refer to their mapped value instead of the -/// original one. If any of the arguments to the function are in the VMap, -/// the arguments are deleted from the resultant function. The VMap is -/// updated to include mappings from all of the instructions and basicblocks in -/// the function from their old to new values. The final argument captures -/// information about the cloned code if non-null. +/// CloneFunction - Return a copy of the specified function and add it to that +/// function's module. Also, any references specified in the VMap are changed +/// to refer to their mapped value instead of the original one. If any of the +/// arguments to the function are in the VMap, the arguments are deleted from +/// the resultant function. The VMap is updated to include mappings from all of +/// the instructions and basicblocks in the function from their old to new +/// values. The final argument captures information about the cloned code if +/// non-null. /// -/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue -/// mappings, and debug info metadata will not be cloned. +/// VMap contains no non-identity GlobalValue mappings and debug info metadata +/// will not be cloned. /// -Function *CloneFunction(const Function *F, ValueToValueMapTy &VMap, - bool ModuleLevelChanges, +Function *CloneFunction(Function *F, ValueToValueMapTy &VMap, ClonedCodeInfo *CodeInfo = nullptr); /// Clone OldFunc into NewFunc, transforming the old arguments into references @@ -221,6 +220,7 @@ bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI, /// /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block /// \p LoopDomBB. Insert the new blocks before block specified in \p Before. +/// Note: Only innermost loops are supported. Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, diff --git a/include/llvm/Transforms/Utils/CodeExtractor.h b/include/llvm/Transforms/Utils/CodeExtractor.h index 3a96d955cac2..30dafd045f23 100644 --- a/include/llvm/Transforms/Utils/CodeExtractor.h +++ b/include/llvm/Transforms/Utils/CodeExtractor.h @@ -15,10 +15,10 @@ #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H -#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SetVector.h" namespace llvm { +template <typename T> class ArrayRef; class BasicBlock; class DominatorTree; class Function; diff --git a/include/llvm/Transforms/Utils/Evaluator.h b/include/llvm/Transforms/Utils/Evaluator.h new file mode 100644 index 000000000000..07f12f41b3bc --- /dev/null +++ b/include/llvm/Transforms/Utils/Evaluator.h @@ -0,0 +1,119 @@ +//===-- Evaluator.h - LLVM IR evaluator -------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Function evaluator for LLVM IR. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H +#define LLVM_TRANSFORMS_UTILS_EVALUATOR_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/GlobalVariable.h" + +#include <deque> +#include <memory> + +namespace llvm { + +class DataLayout; +class Function; +class TargetLibraryInfo; + +/// This class evaluates LLVM IR, producing the Constant representing each SSA +/// instruction. Changes to global variables are stored in a mapping that can +/// be iterated over after the evaluation is complete. Once an evaluation call +/// fails, the evaluation object should not be reused. +class Evaluator { +public: + Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI) + : DL(DL), TLI(TLI) { + ValueStack.emplace_back(); + } + + ~Evaluator() { + for (auto &Tmp : AllocaTmps) + // If there are still users of the alloca, the program is doing something + // silly, e.g. storing the address of the alloca somewhere and using it + // later. Since this is undefined, we'll just make it be null. + if (!Tmp->use_empty()) + Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); + } + + /// Evaluate a call to function F, returning true if successful, false if we + /// can't evaluate it. ActualArgs contains the formal arguments for the + /// function. + bool EvaluateFunction(Function *F, Constant *&RetVal, + const SmallVectorImpl<Constant*> &ActualArgs); + + /// Evaluate all instructions in block BB, returning true if successful, false + /// if we can't evaluate it. NewBB returns the next BB that control flows + /// into, or null upon return. + bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB); + + Constant *getVal(Value *V) { + if (Constant *CV = dyn_cast<Constant>(V)) return CV; + Constant *R = ValueStack.back().lookup(V); + assert(R && "Reference to an uncomputed value!"); + return R; + } + + void setVal(Value *V, Constant *C) { + ValueStack.back()[V] = C; + } + + const DenseMap<Constant*, Constant*> &getMutatedMemory() const { + return MutatedMemory; + } + + const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const { + return Invariants; + } + +private: + Constant *ComputeLoadResult(Constant *P); + + /// As we compute SSA register values, we store their contents here. The back + /// of the deque contains the current function and the stack contains the + /// values in the calling frames. + std::deque<DenseMap<Value*, Constant*>> ValueStack; + + /// This is used to detect recursion. In pathological situations we could hit + /// exponential behavior, but at least there is nothing unbounded. + SmallVector<Function*, 4> CallStack; + + /// For each store we execute, we update this map. Loads check this to get + /// the most up-to-date value. If evaluation is successful, this state is + /// committed to the process. + DenseMap<Constant*, Constant*> MutatedMemory; + + /// To 'execute' an alloca, we create a temporary global variable to represent + /// its body. This vector is needed so we can delete the temporary globals + /// when we are done. + SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps; + + /// These global variables have been marked invariant by the static + /// constructor. + SmallPtrSet<GlobalVariable*, 8> Invariants; + + /// These are constants we have checked and know to be simple enough to live + /// in a static initializer of a global. + SmallPtrSet<Constant*, 8> SimpleConstants; + + const DataLayout &DL; + const TargetLibraryInfo *TLI; +}; + +} + +#endif diff --git a/include/llvm/Transforms/Utils/FunctionImportUtils.h b/include/llvm/Transforms/Utils/FunctionImportUtils.h new file mode 100644 index 000000000000..3b94ef60be5d --- /dev/null +++ b/include/llvm/Transforms/Utils/FunctionImportUtils.h @@ -0,0 +1,100 @@ +//===- FunctionImportUtils.h - Importing support utilities -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the FunctionImportGlobalProcessing class which is used +// to perform the necessary global value handling for function importing. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONIMPORTUTILS_H +#define LLVM_TRANSFORMS_UTILS_FUNCTIONIMPORTUTILS_H + +#include "llvm/ADT/SetVector.h" +#include "llvm/IR/ModuleSummaryIndex.h" + +namespace llvm { +class Module; + +/// Class to handle necessary GlobalValue changes required by ThinLTO +/// function importing, including linkage changes and any necessary renaming. +class FunctionImportGlobalProcessing { + /// The Module which we are exporting or importing functions from. + Module &M; + + /// Module summary index passed in for function importing/exporting handling. + const ModuleSummaryIndex &ImportIndex; + + /// Globals to import from this module, all other functions will be + /// imported as declarations instead of definitions. + DenseSet<const GlobalValue *> *GlobalsToImport; + + /// Set to true if the given ModuleSummaryIndex contains any functions + /// from this source module, in which case we must conservatively assume + /// that any of its functions may be imported into another module + /// as part of a different backend compilation process. + bool HasExportedFunctions = false; + + /// Check if we should promote the given local value to global scope. + bool doPromoteLocalToGlobal(const GlobalValue *SGV); + + /// Helper methods to check if we are importing from or potentially + /// exporting from the current source module. + bool isPerformingImport() const { return GlobalsToImport != nullptr; } + bool isModuleExporting() const { return HasExportedFunctions; } + + /// If we are importing from the source module, checks if we should + /// import SGV as a definition, otherwise import as a declaration. + bool doImportAsDefinition(const GlobalValue *SGV); + + /// Get the name for SGV that should be used in the linked destination + /// module. Specifically, this handles the case where we need to rename + /// a local that is being promoted to global scope. + std::string getName(const GlobalValue *SGV); + + /// Process globals so that they can be used in ThinLTO. This includes + /// promoting local variables so that they can be reference externally by + /// thin lto imported globals and converting strong external globals to + /// available_externally. + void processGlobalsForThinLTO(); + void processGlobalForThinLTO(GlobalValue &GV); + + /// Get the new linkage for SGV that should be used in the linked destination + /// module. Specifically, for ThinLTO importing or exporting it may need + /// to be adjusted. + GlobalValue::LinkageTypes getLinkage(const GlobalValue *SGV); + +public: + FunctionImportGlobalProcessing( + Module &M, const ModuleSummaryIndex &Index, + DenseSet<const GlobalValue *> *GlobalsToImport = nullptr) + : M(M), ImportIndex(Index), GlobalsToImport(GlobalsToImport) { + // If we have a ModuleSummaryIndex but no function to import, + // then this is the primary module being compiled in a ThinLTO + // backend compilation, and we need to see if it has functions that + // may be exported to another backend compilation. + if (!GlobalsToImport) + HasExportedFunctions = ImportIndex.hasExportedFunctions(M); + } + + bool run(); + + static bool + doImportAsDefinition(const GlobalValue *SGV, + DenseSet<const GlobalValue *> *GlobalsToImport); +}; + +/// Perform in-place global value handling on the given Module for +/// exported local functions renamed and promoted for ThinLTO. +bool renameModuleForThinLTO( + Module &M, const ModuleSummaryIndex &Index, + DenseSet<const GlobalValue *> *GlobalsToImport = nullptr); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Transforms/Utils/LCSSA.h b/include/llvm/Transforms/Utils/LCSSA.h new file mode 100644 index 000000000000..f0277d021541 --- /dev/null +++ b/include/llvm/Transforms/Utils/LCSSA.h @@ -0,0 +1,44 @@ +//===- LCSSA.h - Loop-closed SSA transform Pass -----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass transforms loops by placing phi nodes at the end of the loops for +// all values that are live across the loop boundary. For example, it turns +// the left into the right code: +// +// for (...) for (...) +// if (c) if (c) +// X1 = ... X1 = ... +// else else +// X2 = ... X2 = ... +// X3 = phi(X1, X2) X3 = phi(X1, X2) +// ... = X3 + 4 X4 = phi(X3) +// ... = X4 + 4 +// +// This is still valid LLVM; the extra phi nodes are purely redundant, and will +// be trivially eliminated by InstCombine. The major benefit of this +// transformation is that it makes many other loop optimizations, such as +// LoopUnswitching, simpler. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LCSSA_H +#define LLVM_TRANSFORMS_UTILS_LCSSA_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Converts loops into loop-closed SSA form. +class LCSSAPass : public PassInfoMixin<LCSSAPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LCSSA_H diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 3ae01657a2ec..43b376cf8068 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -21,6 +21,7 @@ #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Operator.h" +#include "llvm/ADT/SmallPtrSet.h" namespace llvm { @@ -29,6 +30,7 @@ class BasicBlock; class Function; class BranchInst; class Instruction; +class CallInst; class DbgDeclareInst; class StoreInst; class LoadInst; @@ -50,10 +52,10 @@ template<typename T> class SmallVectorImpl; // Local constant propagation. // -/// ConstantFoldTerminator - If a terminator instruction is predicated on a -/// constant value, convert it into an unconditional branch to the constant -/// destination. This is a nontrivial operation because the successors of this -/// basic block must have their PHI nodes updated. +/// If a terminator instruction is predicated on a constant value, convert it +/// into an unconditional branch to the constant destination. +/// This is a nontrivial operation because the successors of this basic block +/// must have their PHI nodes updated. /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. @@ -64,29 +66,27 @@ bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, // Local dead code elimination. // -/// isInstructionTriviallyDead - Return true if the result produced by the -/// instruction is not used, and the instruction has no side effects. -/// +/// Return true if the result produced by the instruction is not used, and the +/// instruction has no side effects. bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI = nullptr); -/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a -/// trivially dead instruction, delete it. If that makes any of its operands -/// trivially dead, delete them too, recursively. Return true if any -/// instructions were deleted. +/// If the specified value is a trivially dead instruction, delete it. +/// If that makes any of its operands trivially dead, delete them too, +/// recursively. Return true if any instructions were deleted. bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI = nullptr); -/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively -/// dead PHI node, due to being a def-use chain of single-use nodes that -/// either forms a cycle or is terminated by a trivially dead instruction, -/// delete it. If that makes any of its operands trivially dead, delete them -/// too, recursively. Return true if a change was made. +/// If the specified value is an effectively dead PHI node, due to being a +/// def-use chain of single-use nodes that either forms a cycle or is terminated +/// by a trivially dead instruction, delete it. If that makes any of its +/// operands trivially dead, delete them too, recursively. Return true if a +/// change was made. bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI = nullptr); -/// SimplifyInstructionsInBlock - Scan the specified basic block and try to -/// simplify any instructions in it and recursively delete dead instructions. +/// Scan the specified basic block and try to simplify any instructions in it +/// and recursively delete dead instructions. /// /// This returns true if it changed the code, note that it can delete /// instructions in other blocks as well in this block. @@ -97,9 +97,9 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB, // Control Flow Graph Restructuring. // -/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this -/// method is called when we're about to delete Pred as a predecessor of BB. If -/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. +/// Like BasicBlock::removePredecessor, this method is called when we're about +/// to delete Pred as a predecessor of BB. If BB contains any PHI nodes, this +/// drops the entries in the PHI nodes for Pred. /// /// Unlike the removePredecessor method, this attempts to simplify uses of PHI /// nodes that collapse into identity values. For example, if we have: @@ -110,74 +110,68 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB, /// recursively fold the 'and' to 0. void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred); -/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its -/// predecessor is known to have one successor (BB!). Eliminate the edge -/// between them, moving the instructions in the predecessor into BB. This -/// deletes the predecessor block. -/// +/// BB is a block with one predecessor and its predecessor is known to have one +/// successor (BB!). Eliminate the edge between them, moving the instructions in +/// the predecessor into BB. This deletes the predecessor block. void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr); -/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an -/// unconditional branch, and contains no instructions other than PHI nodes, -/// potential debug intrinsics and the branch. If possible, eliminate BB by -/// rewriting all the predecessors to branch to the successor block and return -/// true. If we can't transform, return false. +/// BB is known to contain an unconditional branch, and contains no instructions +/// other than PHI nodes, potential debug intrinsics and the branch. If +/// possible, eliminate BB by rewriting all the predecessors to branch to the +/// successor block and return true. If we can't transform, return false. bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); -/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI -/// nodes in this block. This doesn't try to be clever about PHI nodes -/// which differ only in the order of the incoming values, but instcombine -/// orders them so it usually won't matter. -/// +/// Check for and eliminate duplicate PHI nodes in this block. This doesn't try +/// to be clever about PHI nodes which differ only in the order of the incoming +/// values, but instcombine orders them so it usually won't matter. bool EliminateDuplicatePHINodes(BasicBlock *BB); -/// SimplifyCFG - This function is used to do simplification of a CFG. For +/// This function is used to do simplification of a CFG. For /// example, it adjusts branches to branches to eliminate the extra hop, it /// eliminates unreachable basic blocks, and does other "peephole" optimization /// of the CFG. It returns true if a modification was made, possibly deleting -/// the basic block that was pointed to. -/// +/// the basic block that was pointed to. LoopHeaders is an optional input +/// parameter, providing the set of loop header that SimplifyCFG should not +/// eliminate. bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC = nullptr); + unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, + SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr); -/// FlatternCFG - This function is used to flatten a CFG. For -/// example, it uses parallel-and and parallel-or mode to collapse -// if-conditions and merge if-regions with identical statements. -/// +/// This function is used to flatten a CFG. For example, it uses parallel-and +/// and parallel-or mode to collapse if-conditions and merge if-regions with +/// identical statements. bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr); -/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, -/// and if a predecessor branches to us and one of our successors, fold the -/// setcc into the predecessor and use logical operations to pick the right -/// destination. +/// If this basic block is ONLY a setcc and a branch, and if a predecessor +/// branches to us and one of our successors, fold the setcc into the +/// predecessor and use logical operations to pick the right destination. bool FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold = 1); -/// DemoteRegToStack - This function takes a virtual register computed by an -/// Instruction and replaces it with a slot in the stack frame, allocated via -/// alloca. This allows the CFG to be changed around without fear of -/// invalidating the SSA information for the value. It returns the pointer to -/// the alloca inserted to create a stack slot for X. -/// +/// This function takes a virtual register computed by an Instruction and +/// replaces it with a slot in the stack frame, allocated via alloca. +/// This allows the CFG to be changed around without fear of invalidating the +/// SSA information for the value. It returns the pointer to the alloca inserted +/// to create a stack slot for X. AllocaInst *DemoteRegToStack(Instruction &X, bool VolatileLoads = false, Instruction *AllocaPoint = nullptr); -/// DemotePHIToStack - This function takes a virtual register computed by a phi -/// node and replaces it with a slot in the stack frame, allocated via alloca. -/// The phi node is deleted and it returns the pointer to the alloca inserted. +/// This function takes a virtual register computed by a phi node and replaces +/// it with a slot in the stack frame, allocated via alloca. The phi node is +/// deleted and it returns the pointer to the alloca inserted. AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); -/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that -/// we can determine, return it, otherwise return 0. If PrefAlign is specified, -/// and it is more than the alignment of the ultimate object, see if we can -/// increase the alignment of the ultimate object, making this check succeed. +/// If the specified pointer has an alignment that we can determine, return it, +/// otherwise return 0. If PrefAlign is specified, and it is more than the +/// alignment of the ultimate object, see if we can increase the alignment of +/// the ultimate object, making this check succeed. unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr); -/// getKnownAlignment - Try to infer an alignment for the specified pointer. +/// Try to infer an alignment for the specified pointer. static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI = nullptr, AssumptionCache *AC = nullptr, @@ -185,9 +179,9 @@ static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); } -/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the -/// code necessary to compute the offset from the base pointer (without adding -/// in the base pointer). Return the result as a signed integer of intptr size. +/// Given a getelementptr instruction/constantexpr, emit the code necessary to +/// compute the offset from the base pointer (without adding in the base +/// pointer). Return the result as a signed integer of intptr size. /// When NoAssumptions is true, no assumptions about index computation not /// overflowing is made. template <typename IRBuilderTy> @@ -264,15 +258,14 @@ bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, LoadInst *LI, DIBuilder &Builder); -/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set -/// of llvm.dbg.value intrinsics. +/// Lowers llvm.dbg.declare intrinsics into appropriate set of +/// llvm.dbg.value intrinsics. bool LowerDbgDeclare(Function &F); -/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic corresponding to -/// an alloca, if any. +/// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any. DbgDeclareInst *FindAllocaDbgDeclare(Value *V); -/// \brief Replaces llvm.dbg.declare instruction when the address it describes +/// Replaces llvm.dbg.declare instruction when the address it describes /// is replaced with a new value. If Deref is true, an additional DW_OP_deref is /// prepended to the expression. If Offset is non-zero, a constant displacement /// is added to the expression (after the optional Deref). Offset can be @@ -281,7 +274,7 @@ bool replaceDbgDeclare(Value *Address, Value *NewAddress, Instruction *InsertBefore, DIBuilder &Builder, bool Deref, int Offset); -/// \brief Replaces llvm.dbg.declare instruction when the alloca it describes +/// Replaces llvm.dbg.declare instruction when the alloca it describes /// is replaced with a new value. If Deref is true, an additional DW_OP_deref is /// prepended to the expression. If Offset is non-zero, a constant displacement /// is added to the expression (after the optional Deref). Offset can be @@ -289,39 +282,51 @@ bool replaceDbgDeclare(Value *Address, Value *NewAddress, bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool Deref, int Offset = 0); -/// \brief Insert an unreachable instruction before the specified +/// Replaces multiple llvm.dbg.value instructions when the alloca it describes +/// is replaced with a new value. If Offset is non-zero, a constant displacement +/// is added to the expression (after the mandatory Deref). Offset can be +/// negative. New llvm.dbg.value instructions are inserted at the locations of +/// the instructions they replace. +void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, + DIBuilder &Builder, int Offset = 0); + +/// Remove all instructions from a basic block other than it's terminator +/// and any present EH pad instructions. +unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); + +/// Insert an unreachable instruction before the specified /// instruction, making it and the rest of the code in the block dead. -void changeToUnreachable(Instruction *I, bool UseLLVMTrap); +unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap); /// Replace 'BB's terminator with one that does not have an unwind successor -/// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind +/// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind /// successor. /// /// \param BB Block whose terminator will be replaced. Its terminator must /// have an unwind successor. void removeUnwindEdge(BasicBlock *BB); -/// \brief Remove all blocks that can not be reached from the function's entry. +/// Remove all blocks that can not be reached from the function's entry. /// /// Returns true if any basic block was removed. bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr); -/// \brief Combine the metadata of two instructions so that K can replace J +/// Combine the metadata of two instructions so that K can replace J /// /// Metadata not listed as known via KnownIDs is removed void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs); -/// \brief Replace each use of 'From' with 'To' if that use is dominated by +/// Replace each use of 'From' with 'To' if that use is dominated by /// the given edge. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge); -/// \brief Replace each use of 'From' with 'To' if that use is dominated by -/// the given BasicBlock. Returns the number of replacements made. +/// Replace each use of 'From' with 'To' if that use is dominated by +/// the end of the given BasicBlock. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB); -/// \brief Return true if the CallSite CS calls a gc leaf function. +/// Return true if the CallSite CS calls a gc leaf function. /// /// A leaf function is a function that does not safepoint the thread during its /// execution. During a call or invoke to such a function, the callers stack @@ -335,7 +340,7 @@ bool callsGCLeafFunction(ImmutableCallSite CS); // Intrinsic pattern matching // -/// Try and match a bitreverse or bswap idiom. +/// Try and match a bswap or bitreverse idiom. /// /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added /// instructions are returned in \c InsertedInsts. They will all have been added @@ -346,10 +351,21 @@ bool callsGCLeafFunction(ImmutableCallSite CS); /// to BW / 4 nodes to be searched, so is significantly faster. /// /// This function returns true on a successful match or false otherwise. -bool recognizeBitReverseOrBSwapIdiom( +bool recognizeBSwapOrBitReverseIdiom( Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl<Instruction *> &InsertedInsts); +//===----------------------------------------------------------------------===// +// Sanitizer utilities +// + +/// Given a CallInst, check if it calls a string function known to CodeGen, +/// and mark it with NoBuiltin if so. To be used by sanitizers that intend +/// to intercept string functions and want to avoid converting them to target +/// specific instructions. +void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, + const TargetLibraryInfo *TLI); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Utils/LoopSimplify.h b/include/llvm/Transforms/Utils/LoopSimplify.h new file mode 100644 index 000000000000..7cf89eaeb939 --- /dev/null +++ b/include/llvm/Transforms/Utils/LoopSimplify.h @@ -0,0 +1,65 @@ +//===- LoopSimplify.h - Loop Canonicalization Pass --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs several transformations to transform natural loops into a +// simpler form, which makes subsequent analyses and transformations simpler and +// more effective. +// +// Loop pre-header insertion guarantees that there is a single, non-critical +// entry edge from outside of the loop to the loop header. This simplifies a +// number of analyses and transformations, such as LICM. +// +// Loop exit-block insertion guarantees that all exit blocks from the loop +// (blocks which are outside of the loop that have predecessors inside of the +// loop) only have predecessors from inside of the loop (and are thus dominated +// by the loop header). This simplifies transformations such as store-sinking +// that are built into LICM. +// +// This pass also guarantees that loops will have exactly one backedge. +// +// Indirectbr instructions introduce several complications. If the loop +// contains or is entered by an indirectbr instruction, it may not be possible +// to transform the loop and make these guarantees. Client code should check +// that these conditions are true before relying on them. +// +// Note that the simplifycfg pass will clean up blocks which are split out but +// end up being unnecessary, so usage of this pass should not pessimize +// generated code. +// +// This pass obviously modifies the CFG, but updates loop information and +// dominator information. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H +#define LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H + +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// This pass is responsible for loop canonicalization. +class LoopSimplifyPass : public PassInfoMixin<LoopSimplifyPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Simplify each loop in a loop nest recursively. +/// +/// This takes a potentially un-simplified loop L (and its children) and turns +/// it into a simplified loop nest with preheaders and single backedges. It will +/// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. +bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, + AssumptionCache *AC, bool PreserveLCSSA); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 2cfacb650ff5..89fea10f818a 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -30,20 +30,21 @@ class DominatorTree; class Loop; class LoopInfo; class Pass; +class PredicatedScalarEvolution; class PredIteratorCache; class ScalarEvolution; +class SCEV; class TargetLibraryInfo; /// \brief Captures loop safety information. /// It keep information for loop & its header may throw exception. -struct LICMSafetyInfo { - bool MayThrow; // The current loop contains an instruction which - // may throw. - bool HeaderMayThrow; // Same as previous, but specific to loop header +struct LoopSafetyInfo { + bool MayThrow; // The current loop contains an instruction which + // may throw. + bool HeaderMayThrow; // Same as previous, but specific to loop header // Used to update funclet bundle operands. DenseMap<BasicBlock *, ColorVector> BlockColors; - LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false) - {} + LoopSafetyInfo() : MayThrow(false), HeaderMayThrow(false) {} }; /// The RecurrenceDescriptor is used to identify recurrences variables in a @@ -175,6 +176,13 @@ public: static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes); + /// Returns true if Phi is a first-order recurrence. A first-order recurrence + /// is a non-reduction recurrence relation in which the value of the + /// recurrence in the current loop iteration equals a value defined in the + /// previous iteration. + static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, + DominatorTree *DT); + RecurrenceKind getRecurrenceKind() { return Kind; } MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } @@ -261,7 +269,7 @@ public: public: /// Default constructor - creates an invalid induction. InductionDescriptor() - : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {} + : StartValue(nullptr), IK(IK_NoInduction), Step(nullptr) {} /// Get the consecutive direction. Returns: /// 0 - unknown or non-consecutive. @@ -275,37 +283,59 @@ public: /// For pointer induction, returns StartValue[Index * StepValue]. /// FIXME: The newly created binary instructions should contain nsw/nuw /// flags, which can be found from the original scalar operations. - Value *transform(IRBuilder<> &B, Value *Index) const; + Value *transform(IRBuilder<> &B, Value *Index, ScalarEvolution *SE, + const DataLayout& DL) const; Value *getStartValue() const { return StartValue; } InductionKind getKind() const { return IK; } - ConstantInt *getStepValue() const { return StepValue; } - + const SCEV *getStep() const { return Step; } + ConstantInt *getConstIntStepValue() const; + + /// Returns true if \p Phi is an induction. If \p Phi is an induction, + /// the induction descriptor \p D will contain the data describing this + /// induction. If by some other means the caller has a better SCEV + /// expression for \p Phi than the one returned by the ScalarEvolution + /// analysis, it can be passed through \p Expr. static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE, - InductionDescriptor &D); + InductionDescriptor &D, + const SCEV *Expr = nullptr); + + /// Returns true if \p Phi is an induction, in the context associated with + /// the run-time predicate of PSE. If \p Assume is true, this can add further + /// SCEV predicates to \p PSE in order to prove that \p Phi is an induction. + /// If \p Phi is an induction, \p D will contain the data describing this + /// induction. + static bool isInductionPHI(PHINode *Phi, PredicatedScalarEvolution &PSE, + InductionDescriptor &D, bool Assume = false); private: /// Private constructor - used by \c isInductionPHI. - InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step); + InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step); /// Start value. TrackingVH<Value> StartValue; /// Induction kind. InductionKind IK; /// Step value. - ConstantInt *StepValue; + const SCEV *Step; }; BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA); -/// \brief Simplify each loop in a loop nest recursively. +/// Ensures LCSSA form for every instruction from the Worklist in the scope of +/// innermost containing loop. +/// +/// For the given instruction which have uses outside of the loop, an LCSSA PHI +/// node is inserted and the uses outside the loop are rewritten to use this +/// node. +/// +/// LoopInfo and DominatorTree are required and, since the routine makes no +/// changes to CFG, preserved. /// -/// This takes a potentially un-simplified loop L (and its children) and turns -/// it into a simplified loop nest with preheaders and single backedges. It will -/// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. -bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, - AssumptionCache *AC, bool PreserveLCSSA); +/// Returns true if any modifications are made. +bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, + DominatorTree &DT, LoopInfo &LI); /// \brief Put loop into LCSSA form. /// @@ -318,8 +348,7 @@ bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, /// If ScalarEvolution is passed in, it will be preserved. /// /// Returns true if any modifications are made to the loop. -bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, - ScalarEvolution *SE); +bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); /// \brief Put a loop nest into LCSSA form. /// @@ -343,7 +372,7 @@ bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, /// It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LoopSafetyInfo *); /// \brief Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -354,7 +383,7 @@ bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, /// loop and loop safety information as arguments. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + LoopSafetyInfo *); /// \brief Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over @@ -363,20 +392,45 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop, /// AliasSet information for all instructions of the loop and loop safety /// information as arguments. It returns changed status. -bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &, - SmallVectorImpl<Instruction*> &, +bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &, + SmallVectorImpl<Instruction *> &, PredIteratorCache &, LoopInfo *, - DominatorTree *, Loop *, AliasSetTracker *, - LICMSafetyInfo *); + DominatorTree *, const TargetLibraryInfo *, + Loop *, AliasSetTracker *, LoopSafetyInfo *); /// \brief Computes safety information for a loop /// checks loop body & header for the possibility of may throw -/// exception, it takes LICMSafetyInfo and loop as argument. -/// Updates safety information in LICMSafetyInfo argument. -void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *); +/// exception, it takes LoopSafetyInfo and loop as argument. +/// Updates safety information in LoopSafetyInfo argument. +void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); + +/// Returns true if the instruction in a loop is guaranteed to execute at least +/// once. +bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, + const Loop *CurLoop, + const LoopSafetyInfo *SafetyInfo); /// \brief Returns the instructions that use values defined in the loop. SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); + +/// \brief Find string metadata for loop +/// +/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an +/// operand or null otherwise. If the string metadata is not found return +/// Optional's not-a-value. +Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop, + StringRef Name); + +/// \brief Set input string into loop metadata by keeping other values intact. +void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, + unsigned V = 0); + +/// Helper to consistently add the set of standard passes to a loop pass's \c +/// AnalysisUsage. +/// +/// All loop passes should call this as part of implementing their \c +/// getAnalysisUsage. +void getLoopAnalysisUsage(AnalysisUsage &AU); } #endif diff --git a/include/llvm/Transforms/Utils/LoopVersioning.h b/include/llvm/Transforms/Utils/LoopVersioning.h index 3b70594e0b63..0d345a972e10 100644 --- a/include/llvm/Transforms/Utils/LoopVersioning.h +++ b/include/llvm/Transforms/Utils/LoopVersioning.h @@ -73,11 +73,30 @@ public: /// \brief Sets the runtime alias checks for versioning the loop. void setAliasChecks( - const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); + SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); /// \brief Sets the runtime SCEV checks for versioning the loop. void setSCEVChecks(SCEVUnionPredicate Check); + /// \brief Annotate memory instructions in the versioned loop with no-alias + /// metadata based on the memchecks issued. + /// + /// This is just wrapper that calls prepareNoAliasMetadata and + /// annotateInstWithNoAlias on the instructions of the versioned loop. + void annotateLoopWithNoAlias(); + + /// \brief Set up the aliasing scopes based on the memchecks. This needs to + /// be called before the first call to annotateInstWithNoAlias. + void prepareNoAliasMetadata(); + + /// \brief Add the noalias annotations to \p VersionedInst. + /// + /// \p OrigInst is the instruction corresponding to \p VersionedInst in the + /// original loop. Initialize the aliasing scopes with + /// prepareNoAliasMetadata once before this can be called. + void annotateInstWithNoAlias(Instruction *VersionedInst, + const Instruction *OrigInst); + private: /// \brief Adds the necessary PHI nodes for the versioned loops based on the /// loop-defined values used outside of the loop. @@ -86,6 +105,12 @@ private: /// that are used outside the loop. void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside); + /// \brief Add the noalias annotations to \p I. Initialize the aliasing + /// scopes with prepareNoAliasMetadata once before this can be called. + void annotateInstWithNoAlias(Instruction *I) { + annotateInstWithNoAlias(I, I); + } + /// \brief The original loop. This becomes the "versioned" one. I.e., /// control flows here if pointers in the loop don't alias. Loop *VersionedLoop; @@ -103,6 +128,19 @@ private: /// \brief The set of SCEV checks that we are versioning for. SCEVUnionPredicate Preds; + /// \brief Maps a pointer to the pointer checking group that the pointer + /// belongs to. + DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *> + PtrToGroup; + + /// \brief The alias scope corresponding to a pointer checking group. + DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> + GroupToScope; + + /// \brief The list of alias scopes that a pointer checking group can't alias. + DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> + GroupToNonAliasingScopeList; + /// \brief Analyses used. const LoopAccessInfo &LAI; LoopInfo *LI; diff --git a/include/llvm/Transforms/Utils/Mem2Reg.h b/include/llvm/Transforms/Utils/Mem2Reg.h new file mode 100644 index 000000000000..f3c80edf544d --- /dev/null +++ b/include/llvm/Transforms/Utils/Mem2Reg.h @@ -0,0 +1,28 @@ +//===- Mem2Reg.h - The -mem2reg pass, a wrapper around the Utils lib ------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass is a simple pass wrapper around the PromoteMemToReg function call +// exposed by the Utils library. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_MEM2REG_H +#define LLVM_TRANSFORMS_UTILS_MEM2REG_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class PromotePass : public PassInfoMixin<PromotePass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} + +#endif // LLVM_TRANSFORMS_UTILS_MEM2REG_H
\ No newline at end of file diff --git a/include/llvm/Transforms/Utils/MemorySSA.h b/include/llvm/Transforms/Utils/MemorySSA.h new file mode 100644 index 000000000000..befc34cb80fc --- /dev/null +++ b/include/llvm/Transforms/Utils/MemorySSA.h @@ -0,0 +1,949 @@ +//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// \file +// \brief This file exposes an interface to building/using memory SSA to +// walk memory instructions using a use/def graph. +// +// Memory SSA class builds an SSA form that links together memory access +// instructions such as loads, stores, atomics, and calls. Additionally, it does +// a trivial form of "heap versioning" Every time the memory state changes in +// the program, we generate a new heap version. It generates MemoryDef/Uses/Phis +// that are overlayed on top of the existing instructions. +// +// As a trivial example, +// define i32 @main() #0 { +// entry: +// %call = call noalias i8* @_Znwm(i64 4) #2 +// %0 = bitcast i8* %call to i32* +// %call1 = call noalias i8* @_Znwm(i64 4) #2 +// %1 = bitcast i8* %call1 to i32* +// store i32 5, i32* %0, align 4 +// store i32 7, i32* %1, align 4 +// %2 = load i32* %0, align 4 +// %3 = load i32* %1, align 4 +// %add = add nsw i32 %2, %3 +// ret i32 %add +// } +// +// Will become +// define i32 @main() #0 { +// entry: +// ; 1 = MemoryDef(0) +// %call = call noalias i8* @_Znwm(i64 4) #3 +// %2 = bitcast i8* %call to i32* +// ; 2 = MemoryDef(1) +// %call1 = call noalias i8* @_Znwm(i64 4) #3 +// %4 = bitcast i8* %call1 to i32* +// ; 3 = MemoryDef(2) +// store i32 5, i32* %2, align 4 +// ; 4 = MemoryDef(3) +// store i32 7, i32* %4, align 4 +// ; MemoryUse(3) +// %7 = load i32* %2, align 4 +// ; MemoryUse(4) +// %8 = load i32* %4, align 4 +// %add = add nsw i32 %7, %8 +// ret i32 %add +// } +// +// Given this form, all the stores that could ever effect the load at %8 can be +// gotten by using the MemoryUse associated with it, and walking from use to def +// until you hit the top of the function. +// +// Each def also has a list of users associated with it, so you can walk from +// both def to users, and users to defs. Note that we disambiguate MemoryUses, +// but not the RHS of MemoryDefs. You can see this above at %7, which would +// otherwise be a MemoryUse(4). Being disambiguated means that for a given +// store, all the MemoryUses on its use lists are may-aliases of that store (but +// the MemoryDefs on its use list may not be). +// +// MemoryDefs are not disambiguated because it would require multiple reaching +// definitions, which would require multiple phis, and multiple memoryaccesses +// per instruction. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H +#define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/iterator.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/OperandTraits.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" +#include "llvm/PassAnalysisSupport.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <iterator> +#include <memory> +#include <utility> + +namespace llvm { + +class DominatorTree; +class Function; +class Instruction; +class MemoryAccess; +class LLVMContext; +class raw_ostream; + +template <class T> class memoryaccess_def_iterator_base; +using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>; +using const_memoryaccess_def_iterator = + memoryaccess_def_iterator_base<const MemoryAccess>; + +// \brief The base for all memory accesses. All memory accesses in a block are +// linked together using an intrusive list. +class MemoryAccess : public User, public ilist_node<MemoryAccess> { + void *operator new(size_t, unsigned) = delete; + void *operator new(size_t) = delete; + +public: + // Methods for support type inquiry through isa, cast, and + // dyn_cast + static inline bool classof(const MemoryAccess *) { return true; } + static inline bool classof(const Value *V) { + unsigned ID = V->getValueID(); + return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal; + } + + ~MemoryAccess() override; + + BasicBlock *getBlock() const { return Block; } + + virtual void print(raw_ostream &OS) const = 0; + virtual void dump() const; + + /// \brief The user iterators for a memory access + typedef user_iterator iterator; + typedef const_user_iterator const_iterator; + + /// \brief This iterator walks over all of the defs in a given + /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For + /// MemoryUse/MemoryDef, this walks the defining access. + memoryaccess_def_iterator defs_begin(); + const_memoryaccess_def_iterator defs_begin() const; + memoryaccess_def_iterator defs_end(); + const_memoryaccess_def_iterator defs_end() const; + +protected: + friend class MemorySSA; + friend class MemoryUseOrDef; + friend class MemoryUse; + friend class MemoryDef; + friend class MemoryPhi; + + /// \brief Used internally to give IDs to MemoryAccesses for printing + virtual unsigned getID() const = 0; + + MemoryAccess(LLVMContext &C, unsigned Vty, BasicBlock *BB, + unsigned NumOperands) + : User(Type::getVoidTy(C), Vty, nullptr, NumOperands), Block(BB) {} + +private: + MemoryAccess(const MemoryAccess &); + void operator=(const MemoryAccess &); + BasicBlock *Block; +}; + +template <> +struct ilist_traits<MemoryAccess> : public ilist_default_traits<MemoryAccess> { + /// See details of the instruction class for why this trick works + // FIXME: This downcast is UB. See llvm.org/PR26753. + LLVM_NO_SANITIZE("object-size") + MemoryAccess *createSentinel() const { + return static_cast<MemoryAccess *>(&Sentinel); + } + + static void destroySentinel(MemoryAccess *) {} + + MemoryAccess *provideInitialHead() const { return createSentinel(); } + MemoryAccess *ensureHead(MemoryAccess *) const { return createSentinel(); } + static void noteHead(MemoryAccess *, MemoryAccess *) {} + +private: + mutable ilist_half_node<MemoryAccess> Sentinel; +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) { + MA.print(OS); + return OS; +} + +/// \brief Class that has the common methods + fields of memory uses/defs. It's +/// a little awkward to have, but there are many cases where we want either a +/// use or def, and there are many cases where uses are needed (defs aren't +/// acceptable), and vice-versa. +/// +/// This class should never be instantiated directly; make a MemoryUse or +/// MemoryDef instead. +class MemoryUseOrDef : public MemoryAccess { + void *operator new(size_t, unsigned) = delete; + void *operator new(size_t) = delete; + +public: + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + /// \brief Get the instruction that this MemoryUse represents. + Instruction *getMemoryInst() const { return MemoryInst; } + + /// \brief Get the access that produces the memory state used by this Use. + MemoryAccess *getDefiningAccess() const { return getOperand(0); } + + static inline bool classof(const MemoryUseOrDef *) { return true; } + static inline bool classof(const Value *MA) { + return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal; + } + +protected: + friend class MemorySSA; + + MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty, + Instruction *MI, BasicBlock *BB) + : MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) { + setDefiningAccess(DMA); + } + + void setDefiningAccess(MemoryAccess *DMA) { setOperand(0, DMA); } + +private: + Instruction *MemoryInst; +}; + +template <> +struct OperandTraits<MemoryUseOrDef> + : public FixedNumOperandTraits<MemoryUseOrDef, 1> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess) + +/// \brief Represents read-only accesses to memory +/// +/// In particular, the set of Instructions that will be represented by +/// MemoryUse's is exactly the set of Instructions for which +/// AliasAnalysis::getModRefInfo returns "Ref". +class MemoryUse final : public MemoryUseOrDef { + void *operator new(size_t, unsigned) = delete; + +public: + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + // allocate space for exactly one operand + void *operator new(size_t s) { return User::operator new(s, 1); } + + MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB) + : MemoryUseOrDef(C, DMA, MemoryUseVal, MI, BB) {} + + static inline bool classof(const MemoryUse *) { return true; } + static inline bool classof(const Value *MA) { + return MA->getValueID() == MemoryUseVal; + } + + void print(raw_ostream &OS) const override; + +protected: + friend class MemorySSA; + + unsigned getID() const override { + llvm_unreachable("MemoryUses do not have IDs"); + } +}; + +template <> +struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess) + +/// \brief Represents a read-write access to memory, whether it is a must-alias, +/// or a may-alias. +/// +/// In particular, the set of Instructions that will be represented by +/// MemoryDef's is exactly the set of Instructions for which +/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef". +/// Note that, in order to provide def-def chains, all defs also have a use +/// associated with them. This use points to the nearest reaching +/// MemoryDef/MemoryPhi. +class MemoryDef final : public MemoryUseOrDef { + void *operator new(size_t, unsigned) = delete; + +public: + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + // allocate space for exactly one operand + void *operator new(size_t s) { return User::operator new(s, 1); } + + MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, + unsigned Ver) + : MemoryUseOrDef(C, DMA, MemoryDefVal, MI, BB), ID(Ver) {} + + static inline bool classof(const MemoryDef *) { return true; } + static inline bool classof(const Value *MA) { + return MA->getValueID() == MemoryDefVal; + } + + void print(raw_ostream &OS) const override; + +protected: + friend class MemorySSA; + + // For debugging only. This gets used to give memory accesses pretty numbers + // when printing them out + unsigned getID() const override { return ID; } + +private: + const unsigned ID; +}; + +template <> +struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 1> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess) + +/// \brief Represents phi nodes for memory accesses. +/// +/// These have the same semantic as regular phi nodes, with the exception that +/// only one phi will ever exist in a given basic block. +/// Guaranteeing one phi per block means guaranteeing there is only ever one +/// valid reaching MemoryDef/MemoryPHI along each path to the phi node. +/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or +/// a MemoryPhi's operands. +/// That is, given +/// if (a) { +/// store %a +/// store %b +/// } +/// it *must* be transformed into +/// if (a) { +/// 1 = MemoryDef(liveOnEntry) +/// store %a +/// 2 = MemoryDef(1) +/// store %b +/// } +/// and *not* +/// if (a) { +/// 1 = MemoryDef(liveOnEntry) +/// store %a +/// 2 = MemoryDef(liveOnEntry) +/// store %b +/// } +/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the +/// end of the branch, and if there are not two phi nodes, one will be +/// disconnected completely from the SSA graph below that point. +/// Because MemoryUse's do not generate new definitions, they do not have this +/// issue. +class MemoryPhi final : public MemoryAccess { + void *operator new(size_t, unsigned) = delete; + // allocate space for exactly zero operands + void *operator new(size_t s) { return User::operator new(s); } + +public: + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess); + + MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0) + : MemoryAccess(C, MemoryPhiVal, BB, 0), ID(Ver), ReservedSpace(NumPreds) { + allocHungoffUses(ReservedSpace); + } + + // Block iterator interface. This provides access to the list of incoming + // basic blocks, which parallels the list of incoming values. + typedef BasicBlock **block_iterator; + typedef BasicBlock *const *const_block_iterator; + + block_iterator block_begin() { + auto *Ref = reinterpret_cast<Use::UserRef *>(op_begin() + ReservedSpace); + return reinterpret_cast<block_iterator>(Ref + 1); + } + + const_block_iterator block_begin() const { + const auto *Ref = + reinterpret_cast<const Use::UserRef *>(op_begin() + ReservedSpace); + return reinterpret_cast<const_block_iterator>(Ref + 1); + } + + block_iterator block_end() { return block_begin() + getNumOperands(); } + + const_block_iterator block_end() const { + return block_begin() + getNumOperands(); + } + + op_range incoming_values() { return operands(); } + + const_op_range incoming_values() const { return operands(); } + + /// \brief Return the number of incoming edges + unsigned getNumIncomingValues() const { return getNumOperands(); } + + /// \brief Return incoming value number x + MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); } + void setIncomingValue(unsigned I, MemoryAccess *V) { + assert(V && "PHI node got a null value!"); + setOperand(I, V); + } + static unsigned getOperandNumForIncomingValue(unsigned I) { return I; } + static unsigned getIncomingValueNumForOperand(unsigned I) { return I; } + + /// \brief Return incoming basic block number @p i. + BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; } + + /// \brief Return incoming basic block corresponding + /// to an operand of the PHI. + BasicBlock *getIncomingBlock(const Use &U) const { + assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?"); + return getIncomingBlock(unsigned(&U - op_begin())); + } + + /// \brief Return incoming basic block corresponding + /// to value use iterator. + BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const { + return getIncomingBlock(I.getUse()); + } + + void setIncomingBlock(unsigned I, BasicBlock *BB) { + assert(BB && "PHI node got a null basic block!"); + block_begin()[I] = BB; + } + + /// \brief Add an incoming value to the end of the PHI list + void addIncoming(MemoryAccess *V, BasicBlock *BB) { + if (getNumOperands() == ReservedSpace) + growOperands(); // Get more space! + // Initialize some new operands. + setNumHungOffUseOperands(getNumOperands() + 1); + setIncomingValue(getNumOperands() - 1, V); + setIncomingBlock(getNumOperands() - 1, BB); + } + + /// \brief Return the first index of the specified basic + /// block in the value list for this PHI. Returns -1 if no instance. + int getBasicBlockIndex(const BasicBlock *BB) const { + for (unsigned I = 0, E = getNumOperands(); I != E; ++I) + if (block_begin()[I] == BB) + return I; + return -1; + } + + Value *getIncomingValueForBlock(const BasicBlock *BB) const { + int Idx = getBasicBlockIndex(BB); + assert(Idx >= 0 && "Invalid basic block argument!"); + return getIncomingValue(Idx); + } + + static inline bool classof(const MemoryPhi *) { return true; } + static inline bool classof(const Value *V) { + return V->getValueID() == MemoryPhiVal; + } + + void print(raw_ostream &OS) const override; + +protected: + friend class MemorySSA; + /// \brief this is more complicated than the generic + /// User::allocHungoffUses, because we have to allocate Uses for the incoming + /// values and pointers to the incoming blocks, all in one allocation. + void allocHungoffUses(unsigned N) { + User::allocHungoffUses(N, /* IsPhi */ true); + } + + /// For debugging only. This gets used to give memory accesses pretty numbers + /// when printing them out + unsigned getID() const final { return ID; } + +private: + // For debugging only + const unsigned ID; + unsigned ReservedSpace; + + /// \brief This grows the operand list in response to a push_back style of + /// operation. This grows the number of ops by 1.5 times. + void growOperands() { + unsigned E = getNumOperands(); + // 2 op PHI nodes are VERY common, so reserve at least enough for that. + ReservedSpace = std::max(E + E / 2, 2u); + growHungoffUses(ReservedSpace, /* IsPhi */ true); + } +}; + +template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {}; +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess) + +class MemorySSAWalker; + +/// \brief Encapsulates MemorySSA, including all data associated with memory +/// accesses. +class MemorySSA { +public: + MemorySSA(Function &, AliasAnalysis *, DominatorTree *); + MemorySSA(MemorySSA &&); + ~MemorySSA(); + + MemorySSAWalker *getWalker(); + + /// \brief Given a memory Mod/Ref'ing instruction, get the MemorySSA + /// access associated with it. If passed a basic block gets the memory phi + /// node that exists for that block, if there is one. Otherwise, this will get + /// a MemoryUseOrDef. + MemoryAccess *getMemoryAccess(const Value *) const; + MemoryPhi *getMemoryAccess(const BasicBlock *BB) const; + + void dump() const; + void print(raw_ostream &) const; + + /// \brief Return true if \p MA represents the live on entry value + /// + /// Loads and stores from pointer arguments and other global values may be + /// defined by memory operations that do not occur in the current function, so + /// they may be live on entry to the function. MemorySSA represents such + /// memory state by the live on entry definition, which is guaranteed to occur + /// before any other memory access in the function. + inline bool isLiveOnEntryDef(const MemoryAccess *MA) const { + return MA == LiveOnEntryDef.get(); + } + + inline MemoryAccess *getLiveOnEntryDef() const { + return LiveOnEntryDef.get(); + } + + using AccessList = iplist<MemoryAccess>; + + /// \brief Return the list of MemoryAccess's for a given basic block. + /// + /// This list is not modifiable by the user. + const AccessList *getBlockAccesses(const BasicBlock *BB) const { + auto It = PerBlockAccesses.find(BB); + return It == PerBlockAccesses.end() ? nullptr : It->second.get(); + } + + /// \brief Create an empty MemoryPhi in MemorySSA + MemoryPhi *createMemoryPhi(BasicBlock *BB); + + enum InsertionPlace { Beginning, End }; + + /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block, + /// with a specified clobbering definition. + /// + /// Returns the new MemoryAccess. + /// This should be called when a memory instruction is created that is being + /// used to replace an existing memory instruction. It will *not* create PHI + /// nodes, or verify the clobbering definition. The insertion place is used + /// solely to determine where in the memoryssa access lists the instruction + /// will be placed. The caller is expected to keep ordering the same as + /// instructions. + /// It will return the new MemoryAccess. + MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, + const BasicBlock *BB, + InsertionPlace Point); + /// \brief Create a MemoryAccess in MemorySSA before or after an existing + /// MemoryAccess. + /// + /// Returns the new MemoryAccess. + /// This should be called when a memory instruction is created that is being + /// used to replace an existing memory instruction. It will *not* create PHI + /// nodes, or verify the clobbering definition. The clobbering definition + /// must be non-null. + MemoryAccess *createMemoryAccessBefore(Instruction *I, + MemoryAccess *Definition, + MemoryAccess *InsertPt); + MemoryAccess *createMemoryAccessAfter(Instruction *I, + MemoryAccess *Definition, + MemoryAccess *InsertPt); + + /// \brief Remove a MemoryAccess from MemorySSA, including updating all + /// definitions and uses. + /// This should be called when a memory instruction that has a MemoryAccess + /// associated with it is erased from the program. For example, if a store or + /// load is simply erased (not replaced), removeMemoryAccess should be called + /// on the MemoryAccess for that store/load. + void removeMemoryAccess(MemoryAccess *); + + /// \brief Given two memory accesses in the same basic block, determine + /// whether MemoryAccess \p A dominates MemoryAccess \p B. + bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const; + + /// \brief Verify that MemorySSA is self consistent (IE definitions dominate + /// all uses, uses appear in the right places). This is used by unit tests. + void verifyMemorySSA() const; + +protected: + // Used by Memory SSA annotater, dumpers, and wrapper pass + friend class MemorySSAAnnotatedWriter; + friend class MemorySSAPrinterLegacyPass; + void verifyDefUses(Function &F) const; + void verifyDomination(Function &F) const; + void verifyOrdering(Function &F) const; + +private: + class CachingWalker; + void buildMemorySSA(); + void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const; + using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>; + + void + determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks); + void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels); + void markUnreachableAsLiveOnEntry(BasicBlock *BB); + bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const; + MemoryUseOrDef *createNewAccess(Instruction *); + MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); + MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); + void removeFromLookups(MemoryAccess *); + + MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *); + void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, + SmallPtrSet<BasicBlock *, 16> &Visited); + AccessList *getOrCreateAccessList(const BasicBlock *); + AliasAnalysis *AA; + DominatorTree *DT; + Function &F; + + // Memory SSA mappings + DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess; + AccessMap PerBlockAccesses; + std::unique_ptr<MemoryAccess> LiveOnEntryDef; + + // Memory SSA building info + std::unique_ptr<CachingWalker> Walker; + unsigned NextID; +}; + +// This pass does eager building and then printing of MemorySSA. It is used by +// the tests to be able to build, dump, and verify Memory SSA. +class MemorySSAPrinterLegacyPass : public FunctionPass { +public: + MemorySSAPrinterLegacyPass(); + + static char ID; + bool runOnFunction(Function &) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +/// An analysis that produces \c MemorySSA for a function. +/// +class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> { + friend AnalysisInfoMixin<MemorySSAAnalysis>; + static char PassID; + +public: + typedef MemorySSA Result; + + MemorySSA run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Printer pass for \c MemorySSA. +class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> { + raw_ostream &OS; + +public: + explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Verifier pass for \c MemorySSA. +struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> { + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; + +/// \brief Legacy analysis pass which computes \c MemorySSA. +class MemorySSAWrapperPass : public FunctionPass { +public: + MemorySSAWrapperPass(); + + static char ID; + bool runOnFunction(Function &) override; + void releaseMemory() override; + MemorySSA &getMSSA() { return *MSSA; } + const MemorySSA &getMSSA() const { return *MSSA; } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + void verifyAnalysis() const override; + void print(raw_ostream &OS, const Module *M = nullptr) const override; + +private: + std::unique_ptr<MemorySSA> MSSA; +}; + +/// \brief This is the generic walker interface for walkers of MemorySSA. +/// Walkers are used to be able to further disambiguate the def-use chains +/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives +/// you. +/// In particular, while the def-use chains provide basic information, and are +/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a +/// MemoryUse as AliasAnalysis considers it, a user mant want better or other +/// information. In particular, they may want to use SCEV info to further +/// disambiguate memory accesses, or they may want the nearest dominating +/// may-aliasing MemoryDef for a call or a store. This API enables a +/// standardized interface to getting and using that info. +class MemorySSAWalker { +public: + MemorySSAWalker(MemorySSA *); + virtual ~MemorySSAWalker() {} + + using MemoryAccessSet = SmallVector<MemoryAccess *, 8>; + + /// \brief Given a memory Mod/Ref/ModRef'ing instruction, calling this + /// will give you the nearest dominating MemoryAccess that Mod's the location + /// the instruction accesses (by skipping any def which AA can prove does not + /// alias the location(s) accessed by the instruction given). + /// + /// Note that this will return a single access, and it must dominate the + /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction, + /// this will return the MemoryPhi, not the operand. This means that + /// given: + /// if (a) { + /// 1 = MemoryDef(liveOnEntry) + /// store %a + /// } else { + /// 2 = MemoryDef(liveOnEntry) + /// store %b + /// } + /// 3 = MemoryPhi(2, 1) + /// MemoryUse(3) + /// load %a + /// + /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef + /// in the if (a) branch. + virtual MemoryAccess *getClobberingMemoryAccess(const Instruction *) = 0; + + /// \brief Given a potentially clobbering memory access and a new location, + /// calling this will give you the nearest dominating clobbering MemoryAccess + /// (by skipping non-aliasing def links). + /// + /// This version of the function is mainly used to disambiguate phi translated + /// pointers, where the value of a pointer may have changed from the initial + /// memory access. Note that this expects to be handed either a MemoryUse, + /// or an already potentially clobbering access. Unlike the above API, if + /// given a MemoryDef that clobbers the pointer as the starting access, it + /// will return that MemoryDef, whereas the above would return the clobber + /// starting from the use side of the memory def. + virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + MemoryLocation &) = 0; + + /// \brief Given a memory access, invalidate anything this walker knows about + /// that access. + /// This API is used by walkers that store information to perform basic cache + /// invalidation. This will be called by MemorySSA at appropriate times for + /// the walker it uses or returns. + virtual void invalidateInfo(MemoryAccess *) {} + +protected: + friend class MemorySSA; // For updating MSSA pointer in MemorySSA move + // constructor. + MemorySSA *MSSA; +}; + +/// \brief A MemorySSAWalker that does no alias queries, or anything else. It +/// simply returns the links as they were constructed by the builder. +class DoNothingMemorySSAWalker final : public MemorySSAWalker { +public: + MemoryAccess *getClobberingMemoryAccess(const Instruction *) override; + MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + MemoryLocation &) override; +}; + +using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>; +using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>; + +/// \brief Iterator base class used to implement const and non-const iterators +/// over the defining accesses of a MemoryAccess. +template <class T> +class memoryaccess_def_iterator_base + : public iterator_facade_base<memoryaccess_def_iterator_base<T>, + std::forward_iterator_tag, T, ptrdiff_t, T *, + T *> { + using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base; + +public: + memoryaccess_def_iterator_base(T *Start) : Access(Start), ArgNo(0) {} + memoryaccess_def_iterator_base() : Access(nullptr), ArgNo(0) {} + bool operator==(const memoryaccess_def_iterator_base &Other) const { + return Access == Other.Access && (!Access || ArgNo == Other.ArgNo); + } + + // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the + // block from the operand in constant time (In a PHINode, the uselist has + // both, so it's just subtraction). We provide it as part of the + // iterator to avoid callers having to linear walk to get the block. + // If the operation becomes constant time on MemoryPHI's, this bit of + // abstraction breaking should be removed. + BasicBlock *getPhiArgBlock() const { + MemoryPhi *MP = dyn_cast<MemoryPhi>(Access); + assert(MP && "Tried to get phi arg block when not iterating over a PHI"); + return MP->getIncomingBlock(ArgNo); + } + typename BaseT::iterator::pointer operator*() const { + assert(Access && "Tried to access past the end of our iterator"); + // Go to the first argument for phis, and the defining access for everything + // else. + if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) + return MP->getIncomingValue(ArgNo); + return cast<MemoryUseOrDef>(Access)->getDefiningAccess(); + } + using BaseT::operator++; + memoryaccess_def_iterator &operator++() { + assert(Access && "Hit end of iterator"); + if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) { + if (++ArgNo >= MP->getNumIncomingValues()) { + ArgNo = 0; + Access = nullptr; + } + } else { + Access = nullptr; + } + return *this; + } + +private: + T *Access; + unsigned ArgNo; +}; + +inline memoryaccess_def_iterator MemoryAccess::defs_begin() { + return memoryaccess_def_iterator(this); +} + +inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const { + return const_memoryaccess_def_iterator(this); +} + +inline memoryaccess_def_iterator MemoryAccess::defs_end() { + return memoryaccess_def_iterator(); +} + +inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const { + return const_memoryaccess_def_iterator(); +} + +/// \brief GraphTraits for a MemoryAccess, which walks defs in the normal case, +/// and uses in the inverse case. +template <> struct GraphTraits<MemoryAccess *> { + using NodeType = MemoryAccess; + using ChildIteratorType = memoryaccess_def_iterator; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->defs_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->defs_end(); + } +}; + +template <> struct GraphTraits<Inverse<MemoryAccess *>> { + using NodeType = MemoryAccess; + using ChildIteratorType = MemoryAccess::iterator; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->user_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->user_end(); + } +}; + +/// \brief Provide an iterator that walks defs, giving both the memory access, +/// and the current pointer location, updating the pointer location as it +/// changes due to phi node translation. +/// +/// This iterator, while somewhat specialized, is what most clients actually +/// want when walking upwards through MemorySSA def chains. It takes a pair of +/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the +/// memory location through phi nodes for the user. +class upward_defs_iterator + : public iterator_facade_base<upward_defs_iterator, + std::forward_iterator_tag, + const MemoryAccessPair> { + using BaseT = upward_defs_iterator::iterator_facade_base; + +public: + upward_defs_iterator(const MemoryAccessPair &Info) + : DefIterator(Info.first), Location(Info.second), + OriginalAccess(Info.first) { + CurrentPair.first = nullptr; + + WalkingPhi = Info.first && isa<MemoryPhi>(Info.first); + fillInCurrentPair(); + } + + upward_defs_iterator() + : DefIterator(), Location(), OriginalAccess(), WalkingPhi(false) { + CurrentPair.first = nullptr; + } + + bool operator==(const upward_defs_iterator &Other) const { + return DefIterator == Other.DefIterator; + } + + BaseT::iterator::reference operator*() const { + assert(DefIterator != OriginalAccess->defs_end() && + "Tried to access past the end of our iterator"); + return CurrentPair; + } + + using BaseT::operator++; + upward_defs_iterator &operator++() { + assert(DefIterator != OriginalAccess->defs_end() && + "Tried to access past the end of the iterator"); + ++DefIterator; + if (DefIterator != OriginalAccess->defs_end()) + fillInCurrentPair(); + return *this; + } + + BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); } + +private: + void fillInCurrentPair() { + CurrentPair.first = *DefIterator; + if (WalkingPhi && Location.Ptr) { + PHITransAddr Translator( + const_cast<Value *>(Location.Ptr), + OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr); + if (!Translator.PHITranslateValue(OriginalAccess->getBlock(), + DefIterator.getPhiArgBlock(), nullptr, + false)) + if (Translator.getAddr() != Location.Ptr) { + CurrentPair.second = Location.getWithNewPtr(Translator.getAddr()); + return; + } + } + CurrentPair.second = Location; + } + + MemoryAccessPair CurrentPair; + memoryaccess_def_iterator DefIterator; + MemoryLocation Location; + MemoryAccess *OriginalAccess; + bool WalkingPhi; +}; + +inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) { + return upward_defs_iterator(Pair); +} + +inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); } + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_MEMORYSSA_H diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h index 0f23d34de5db..2eb2b1363b0b 100644 --- a/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/include/llvm/Transforms/Utils/ModuleUtils.h @@ -14,12 +14,12 @@ #ifndef LLVM_TRANSFORMS_UTILS_MODULEUTILS_H #define LLVM_TRANSFORMS_UTILS_MODULEUTILS_H -#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringRef.h" #include <utility> // for std::pair namespace llvm { +template <typename T> class ArrayRef; class Module; class Function; class GlobalValue; @@ -28,22 +28,17 @@ class Constant; class StringRef; class Value; class Type; -template <class PtrType> class SmallPtrSetImpl; /// Append F to the list of global ctors of module M with the given Priority. /// This wraps the function in the appropriate structure and stores it along /// side other global constructors. For details see /// http://llvm.org/docs/LangRef.html#intg_global_ctors -void appendToGlobalCtors(Module &M, Function *F, int Priority); +void appendToGlobalCtors(Module &M, Function *F, int Priority, + Constant *Data = nullptr); /// Same as appendToGlobalCtors(), but for global dtors. -void appendToGlobalDtors(Module &M, Function *F, int Priority); - -/// \brief Given "llvm.used" or "llvm.compiler.used" as a global name, collect -/// the initializer elements of that global in Set and return the global itself. -GlobalVariable *collectUsedGlobalVariables(Module &M, - SmallPtrSetImpl<GlobalValue *> &Set, - bool CompilerUsed); +void appendToGlobalDtors(Module &M, Function *F, int Priority, + Constant *Data = nullptr); // Validate the result of Module::getOrInsertFunction called for an interface // function of given sanitizer. If the instrumented module defines a function @@ -59,6 +54,11 @@ std::pair<Function *, Function *> createSanitizerCtorAndInitFunctions( Module &M, StringRef CtorName, StringRef InitName, ArrayRef<Type *> InitArgTypes, ArrayRef<Value *> InitArgs, StringRef VersionCheckName = StringRef()); + +/// Rename all the anon functions in the module using a hash computed from +/// the list of public globals in the module. +bool nameUnamedFunctions(Module &M); + } // End llvm namespace #endif // LLVM_TRANSFORMS_UTILS_MODULEUTILS_H diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h index d0602bf47c92..b548072c413e 100644 --- a/include/llvm/Transforms/Utils/PromoteMemToReg.h +++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h @@ -15,10 +15,9 @@ #ifndef LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H #define LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H -#include "llvm/ADT/ArrayRef.h" - namespace llvm { +template <typename T> class ArrayRef; class AllocaInst; class DominatorTree; class AliasSetTracker; diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 1c7b2c587a36..9f98bac22dc9 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -14,7 +14,6 @@ #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H -#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/Compiler.h" @@ -22,8 +21,9 @@ namespace llvm { class BasicBlock; class Instruction; class LoadInst; - template<typename T> class SmallVectorImpl; - template<typename T> class SSAUpdaterTraits; + template <typename T> class ArrayRef; + template <typename T> class SmallVectorImpl; + template <typename T> class SSAUpdaterTraits; class PHINode; class Type; class Use; diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h index 425ecd3cfb5e..b5f4ac82b605 100644 --- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -17,6 +17,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" diff --git a/include/llvm/Transforms/Utils/SanitizerStats.h b/include/llvm/Transforms/Utils/SanitizerStats.h new file mode 100644 index 000000000000..d36e34258a3f --- /dev/null +++ b/include/llvm/Transforms/Utils/SanitizerStats.h @@ -0,0 +1,56 @@ +//===- SanitizerStats.h - Sanitizer statistics gathering -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Declares functions and data structures for sanitizer statistics gathering. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SANITIZERSTATS_H +#define LLVM_TRANSFORMS_UTILS_SANITIZERSTATS_H + +#include "llvm/IR/IRBuilder.h" + +namespace llvm { + +// Number of bits in data that are used for the sanitizer kind. Needs to match +// __sanitizer::kKindBits in compiler-rt/lib/stats/stats.h +enum { kSanitizerStatKindBits = 3 }; + +enum SanitizerStatKind { + SanStat_CFI_VCall, + SanStat_CFI_NVCall, + SanStat_CFI_DerivedCast, + SanStat_CFI_UnrelatedCast, + SanStat_CFI_ICall, +}; + +struct SanitizerStatReport { + SanitizerStatReport(Module *M); + + /// Generates code into B that increments a location-specific counter tagged + /// with the given sanitizer kind SK. + void create(IRBuilder<> &B, SanitizerStatKind SK); + + /// Finalize module stats array and add global constructor to register it. + void finish(); + +private: + Module *M; + GlobalVariable *ModuleStatsGV; + ArrayType *StatTy; + StructType *EmptyModuleStatsTy; + + std::vector<Constant *> Inits; + ArrayType *makeModuleStatsArrayTy(); + StructType *makeModuleStatsTy(); +}; + +} + +#endif diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index 3c55e64537c7..90438ee699fe 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -17,7 +17,6 @@ #define LLVM_TRANSFORMS_UTILS_SIMPLIFYINDVAR_H #include "llvm/IR/ValueHandle.h" -#include "llvm/Support/CommandLine.h" namespace llvm { @@ -34,24 +33,14 @@ class ScalarEvolution; class IVVisitor { protected: const DominatorTree *DT; - bool ShouldSplitOverflowIntrinsics; virtual void anchor(); public: - IVVisitor(): DT(nullptr), ShouldSplitOverflowIntrinsics(false) {} + IVVisitor() : DT(nullptr) {} virtual ~IVVisitor() {} const DominatorTree *getDomTree() const { return DT; } - - bool shouldSplitOverflowInstrinsics() const { - return ShouldSplitOverflowIntrinsics; - } - void setSplitOverflowIntrinsics() { - ShouldSplitOverflowIntrinsics = true; - assert(DT && "Splitting overflow intrinsics requires a DomTree."); - } - virtual void visitCast(CastInst *Cast) = 0; }; diff --git a/include/llvm/Transforms/Utils/SimplifyInstructions.h b/include/llvm/Transforms/Utils/SimplifyInstructions.h new file mode 100644 index 000000000000..ea491dc50587 --- /dev/null +++ b/include/llvm/Transforms/Utils/SimplifyInstructions.h @@ -0,0 +1,31 @@ +//===- SimplifyInstructions.h - Remove redundant instructions ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This is a utility pass used for testing the InstructionSimplify analysis. +// The analysis is applied to every instruction, and if it simplifies then the +// instruction is replaced by the simplification. If you are looking for a pass +// that performs serious instruction folding, use the instcombine pass instead. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H +#define LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// This pass removes redundant instructions. +class InstSimplifierPass : public PassInfoMixin<InstSimplifierPass> { +public: + PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h index fc34f49a1255..92ee24633950 100644 --- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -16,11 +16,11 @@ #define LLVM_TRANSFORMS_UTILS_SIMPLIFYLIBCALLS_H #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/IRBuilder.h" namespace llvm { +class StringRef; class Value; class CallInst; class DataLayout; @@ -154,7 +154,7 @@ private: // Helper methods Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B); - void classifyArgUse(Value *Val, BasicBlock *BB, bool IsFloat, + void classifyArgUse(Value *Val, Function *F, bool IsFloat, SmallVectorImpl<CallInst *> &SinCalls, SmallVectorImpl<CallInst *> &CosCalls, SmallVectorImpl<CallInst *> &SinCosCalls); diff --git a/include/llvm/Transforms/Utils/SplitModule.h b/include/llvm/Transforms/Utils/SplitModule.h index 7d896d1993d6..b7a3bcf4f86a 100644 --- a/include/llvm/Transforms/Utils/SplitModule.h +++ b/include/llvm/Transforms/Utils/SplitModule.h @@ -16,7 +16,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_SPLITMODULE_H #define LLVM_TRANSFORMS_UTILS_SPLITMODULE_H -#include <functional> +#include "llvm/ADT/STLExtras.h" #include <memory> namespace llvm { @@ -36,7 +36,8 @@ class StringRef; /// each partition. void SplitModule( std::unique_ptr<Module> M, unsigned N, - std::function<void(std::unique_ptr<Module> MPart)> ModuleCallback); + function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback, + bool PreserveLocals = false); } // End llvm namespace diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h index 710817cddf6a..4d370407591d 100644 --- a/include/llvm/Transforms/Utils/UnrollLoop.h +++ b/include/llvm/Transforms/Utils/UnrollLoop.h @@ -16,10 +16,10 @@ #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H -#include "llvm/ADT/StringRef.h" namespace llvm { +class StringRef; class AssumptionCache; class DominatorTree; class Loop; @@ -29,15 +29,16 @@ class MDNode; class Pass; class ScalarEvolution; -bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool AllowRuntime, - bool AllowExpensiveTripCount, unsigned TripMultiple, - LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, - AssumptionCache *AC, bool PreserveLCSSA); +bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force, + bool AllowRuntime, bool AllowExpensiveTripCount, + unsigned TripMultiple, LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); -bool UnrollRuntimeLoopProlog(Loop *L, unsigned Count, - bool AllowExpensiveTripCount, LoopInfo *LI, - ScalarEvolution *SE, DominatorTree *DT, - bool PreserveLCSSA); +bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, + bool AllowExpensiveTripCount, + bool UseEpilogRemainder, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + bool PreserveLCSSA); MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); } diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h index 469022f34c56..de649009612c 100644 --- a/include/llvm/Transforms/Utils/ValueMapper.h +++ b/include/llvm/Transforms/Utils/ValueMapper.h @@ -18,117 +18,255 @@ #include "llvm/IR/ValueMap.h" namespace llvm { - class Value; - class Instruction; - typedef ValueMap<const Value *, WeakVH> ValueToValueMapTy; - - /// ValueMapTypeRemapper - This is a class that can be implemented by clients - /// to remap types when cloning constants and instructions. - class ValueMapTypeRemapper { - virtual void anchor(); // Out of line method. - public: - virtual ~ValueMapTypeRemapper() {} - - /// remapType - The client should implement this method if they want to - /// remap types while mapping values. - virtual Type *remapType(Type *SrcTy) = 0; - }; - - /// ValueMaterializer - This is a class that can be implemented by clients - /// to materialize Values on demand. - class ValueMaterializer { - virtual void anchor(); // Out of line method. - - protected: - ~ValueMaterializer() = default; - ValueMaterializer() = default; - ValueMaterializer(const ValueMaterializer&) = default; - ValueMaterializer &operator=(const ValueMaterializer&) = default; - - public: - /// The client should implement this method if they want to generate a - /// mapped Value on demand. For example, if linking lazily. - virtual Value *materializeDeclFor(Value *V) = 0; - - /// If the data being mapped is recursive, the above function can map - /// just the declaration and this is called to compute the initializer. - /// It is called after the mapping is recorded, so it doesn't need to worry - /// about recursion. - virtual void materializeInitFor(GlobalValue *New, GlobalValue *Old); - - /// If the client needs to handle temporary metadata it must implement - /// these methods. - virtual Metadata *mapTemporaryMetadata(Metadata *MD) { return nullptr; } - virtual void replaceTemporaryMetadata(const Metadata *OrigMD, - Metadata *NewMD) {} - - /// The client should implement this method if some metadata need - /// not be mapped, for example DISubprogram metadata for functions not - /// linked into the destination module. - virtual bool isMetadataNeeded(Metadata *MD) { return true; } - }; - - /// RemapFlags - These are flags that the value mapping APIs allow. - enum RemapFlags { - RF_None = 0, - - /// RF_NoModuleLevelChanges - If this flag is set, the remapper knows that - /// only local values within a function (such as an instruction or argument) - /// are mapped, not global values like functions and global metadata. - RF_NoModuleLevelChanges = 1, - - /// RF_IgnoreMissingEntries - If this flag is set, the remapper ignores - /// entries that are not in the value map. If it is unset, it aborts if an - /// operand is asked to be remapped which doesn't exist in the mapping. - RF_IgnoreMissingEntries = 2, - - /// Instruct the remapper to move distinct metadata instead of duplicating - /// it when there are module-level changes. - RF_MoveDistinctMDs = 4, - - /// Any global values not in value map are mapped to null instead of - /// mapping to self. Illegal if RF_IgnoreMissingEntries is also set. - RF_NullMapMissingGlobalValues = 8, - - /// Set when there is still temporary metadata that must be handled, - /// such as when we are doing function importing and will materialize - /// and link metadata as a postpass. - RF_HaveUnmaterializedMetadata = 16, - }; - - static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { - return RemapFlags(unsigned(LHS)|unsigned(RHS)); - } - - Value *MapValue(const Value *V, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - Metadata *MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - /// MapMetadata - provide versions that preserve type safety for MDNodes. - MDNode *MapMetadata(const MDNode *MD, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr); - - /// MapValue - provide versions that preserve type safety for Constants. - inline Constant *MapValue(const Constant *V, ValueToValueMapTy &VM, - RemapFlags Flags = RF_None, - ValueMapTypeRemapper *TypeMapper = nullptr, - ValueMaterializer *Materializer = nullptr) { - return cast<Constant>(MapValue((const Value*)V, VM, Flags, TypeMapper, - Materializer)); - } + +class Value; +class Instruction; +typedef ValueMap<const Value *, WeakVH> ValueToValueMapTy; + +/// This is a class that can be implemented by clients to remap types when +/// cloning constants and instructions. +class ValueMapTypeRemapper { + virtual void anchor(); // Out of line method. +public: + virtual ~ValueMapTypeRemapper() {} + + /// The client should implement this method if they want to remap types while + /// mapping values. + virtual Type *remapType(Type *SrcTy) = 0; +}; + +/// This is a class that can be implemented by clients to materialize Values on +/// demand. +class ValueMaterializer { + virtual void anchor(); // Out of line method. + +protected: + ~ValueMaterializer() = default; + ValueMaterializer() = default; + ValueMaterializer(const ValueMaterializer &) = default; + ValueMaterializer &operator=(const ValueMaterializer &) = default; + +public: + /// This method can be implemented to generate a mapped Value on demand. For + /// example, if linking lazily. Returns null if the value is not materialized. + virtual Value *materialize(Value *V) = 0; +}; + +/// These are flags that the value mapping APIs allow. +enum RemapFlags { + RF_None = 0, + + /// If this flag is set, the remapper knows that only local values within a + /// function (such as an instruction or argument) are mapped, not global + /// values like functions and global metadata. + RF_NoModuleLevelChanges = 1, + + /// If this flag is set, the remapper ignores missing function-local entries + /// (Argument, Instruction, BasicBlock) that are not in the value map. If it + /// is unset, it aborts if an operand is asked to be remapped which doesn't + /// exist in the mapping. + /// + /// There are no such assertions in MapValue(), whose results are almost + /// unchanged by this flag. This flag mainly changes the assertion behaviour + /// in RemapInstruction(). + /// + /// Since an Instruction's metadata operands (even that point to SSA values) + /// aren't guaranteed to be dominated by their definitions, MapMetadata will + /// return "!{}" instead of "null" for \a LocalAsMetadata instances whose SSA + /// values are unmapped when this flag is set. Otherwise, \a MapValue() + /// completely ignores this flag. + /// + /// \a MapMetadata() always ignores this flag. + RF_IgnoreMissingLocals = 2, + + /// Instruct the remapper to move distinct metadata instead of duplicating it + /// when there are module-level changes. + RF_MoveDistinctMDs = 4, + + /// Any global values not in value map are mapped to null instead of mapping + /// to self. Illegal if RF_IgnoreMissingLocals is also set. + RF_NullMapMissingGlobalValues = 8, +}; + +static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { + return RemapFlags(unsigned(LHS) | unsigned(RHS)); +} + +class ValueMapperImpl; + +/// Context for (re-)mapping values (and metadata). +/// +/// A shared context used for mapping and remapping of Value and Metadata +/// instances using \a ValueToValueMapTy, \a RemapFlags, \a +/// ValueMapTypeRemapper, and \a ValueMaterializer. +/// +/// There are a number of top-level entry points: +/// - \a mapValue() (and \a mapConstant()); +/// - \a mapMetadata() (and \a mapMDNode()); +/// - \a remapInstruction(); and +/// - \a remapFunction(). +/// +/// The \a ValueMaterializer can be used as a callback, but cannot invoke any +/// of these top-level functions recursively. Instead, callbacks should use +/// one of the following to schedule work lazily in the \a ValueMapper +/// instance: +/// - \a scheduleMapGlobalInitializer() +/// - \a scheduleMapAppendingVariable() +/// - \a scheduleMapGlobalAliasee() +/// - \a scheduleRemapFunction() +/// +/// Sometimes a callback needs a diferent mapping context. Such a context can +/// be registered using \a registerAlternateMappingContext(), which takes an +/// alternate \a ValueToValueMapTy and \a ValueMaterializer and returns a ID to +/// pass into the schedule*() functions. +/// +/// TODO: lib/Linker really doesn't need the \a ValueHandle in the \a +/// ValueToValueMapTy. We should template \a ValueMapper (and its +/// implementation classes), and explicitly instantiate on two concrete +/// instances of \a ValueMap (one as \a ValueToValueMap, and one with raw \a +/// Value pointers). It may be viable to do away with \a TrackingMDRef in the +/// \a Metadata side map for the lib/Linker case as well, in which case we'll +/// need a new template parameter on \a ValueMap. +/// +/// TODO: Update callers of \a RemapInstruction() and \a MapValue() (etc.) to +/// use \a ValueMapper directly. +class ValueMapper { + void *pImpl; + + ValueMapper(ValueMapper &&) = delete; + ValueMapper(const ValueMapper &) = delete; + ValueMapper &operator=(ValueMapper &&) = delete; + ValueMapper &operator=(const ValueMapper &) = delete; + +public: + ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr); + ~ValueMapper(); + + /// Register an alternate mapping context. + /// + /// Returns a MappingContextID that can be used with the various schedule*() + /// API to switch in a different value map on-the-fly. + unsigned + registerAlternateMappingContext(ValueToValueMapTy &VM, + ValueMaterializer *Materializer = nullptr); + + /// Add to the current \a RemapFlags. + /// + /// \note Like the top-level mapping functions, \a addFlags() must be called + /// at the top level, not during a callback in a \a ValueMaterializer. + void addFlags(RemapFlags Flags); + + Metadata *mapMetadata(const Metadata &MD); + MDNode *mapMDNode(const MDNode &N); + + Value *mapValue(const Value &V); + Constant *mapConstant(const Constant &C); + + void remapInstruction(Instruction &I); + void remapFunction(Function &F); + + void scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init, + unsigned MappingContextID = 0); + void scheduleMapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix, + bool IsOldCtorDtor, + ArrayRef<Constant *> NewMembers, + unsigned MappingContextID = 0); + void scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee, + unsigned MappingContextID = 0); + void scheduleRemapFunction(Function &F, unsigned MappingContextID = 0); +}; + +/// Look up or compute a value in the value map. +/// +/// Return a mapped value for a function-local value (Argument, Instruction, +/// BasicBlock), or compute and memoize a value for a Constant. +/// +/// 1. If \c V is in VM, return the result. +/// 2. Else if \c V can be materialized with \c Materializer, do so, memoize +/// it in \c VM, and return it. +/// 3. Else if \c V is a function-local value, return nullptr. +/// 4. Else if \c V is a \a GlobalValue, return \c nullptr or \c V depending +/// on \a RF_NullMapMissingGlobalValues. +/// 5. Else if \c V is a \a MetadataAsValue wrapping a LocalAsMetadata, +/// recurse on the local SSA value, and return nullptr or "metadata !{}" on +/// missing depending on RF_IgnoreMissingValues. +/// 6. Else if \c V is a \a MetadataAsValue, rewrap the return of \a +/// MapMetadata(). +/// 7. Else, compute the equivalent constant, and return it. +inline Value *MapValue(const Value *V, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapValue(*V); +} + +/// Lookup or compute a mapping for a piece of metadata. +/// +/// Compute and memoize a mapping for \c MD. +/// +/// 1. If \c MD is mapped, return it. +/// 2. Else if \a RF_NoModuleLevelChanges or \c MD is an \a MDString, return +/// \c MD. +/// 3. Else if \c MD is a \a ConstantAsMetadata, call \a MapValue() and +/// re-wrap its return (returning nullptr on nullptr). +/// 4. Else, \c MD is an \a MDNode. These are remapped, along with their +/// transitive operands. Distinct nodes are duplicated or moved depending +/// on \a RF_MoveDistinctNodes. Uniqued nodes are remapped like constants. +/// +/// \note \a LocalAsMetadata is completely unsupported by \a MapMetadata. +/// Instead, use \a MapValue() with its wrapping \a MetadataAsValue instance. +inline Metadata *MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapMetadata(*MD); +} + +/// Version of MapMetadata with type safety for MDNode. +inline MDNode *MapMetadata(const MDNode *MD, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapMDNode(*MD); +} + +/// Convert the instruction operands from referencing the current values into +/// those specified by VM. +/// +/// If \a RF_IgnoreMissingLocals is set and an operand can't be found via \a +/// MapValue(), use the old value. Otherwise assert that this doesn't happen. +/// +/// Note that \a MapValue() only returns \c nullptr for SSA values missing from +/// \c VM. +inline void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + ValueMapper(VM, Flags, TypeMapper, Materializer).remapInstruction(*I); +} + +/// Remap the operands, metadata, arguments, and instructions of a function. +/// +/// Calls \a MapValue() on prefix data, prologue data, and personality +/// function; calls \a MapMetadata() on each attached MDNode; remaps the +/// argument types using the provided \c TypeMapper; and calls \a +/// RemapInstruction() on every instruction. +inline void RemapFunction(Function &F, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + ValueMapper(VM, Flags, TypeMapper, Materializer).remapFunction(F); +} + +/// Version of MapValue with type safety for Constant. +inline Constant *MapValue(const Constant *V, ValueToValueMapTy &VM, + RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr) { + return ValueMapper(VM, Flags, TypeMapper, Materializer).mapConstant(*V); +} } // End llvm namespace |