diff options
Diffstat (limited to 'clang-r353983e/include/llvm/Transforms/Utils')
46 files changed, 5917 insertions, 0 deletions
diff --git a/clang-r353983e/include/llvm/Transforms/Utils/ASanStackFrameLayout.h b/clang-r353983e/include/llvm/Transforms/Utils/ASanStackFrameLayout.h new file mode 100644 index 00000000..0b570c0d --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/ASanStackFrameLayout.h @@ -0,0 +1,80 @@ +//===- ASanStackFrameLayout.h - ComputeASanStackFrameLayout -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This header defines ComputeASanStackFrameLayout and auxiliary data structs. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_TRANSFORMS_UTILS_ASANSTACKFRAMELAYOUT_H +#define LLVM_TRANSFORMS_UTILS_ASANSTACKFRAMELAYOUT_H +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" + +namespace llvm { + +class AllocaInst; + +// These magic constants should be the same as in +// in asan_internal.h from ASan runtime in compiler-rt. +static const int kAsanStackLeftRedzoneMagic = 0xf1; +static const int kAsanStackMidRedzoneMagic = 0xf2; +static const int kAsanStackRightRedzoneMagic = 0xf3; +static const int kAsanStackUseAfterReturnMagic = 0xf5; +static const int kAsanStackUseAfterScopeMagic = 0xf8; + +// Input/output data struct for ComputeASanStackFrameLayout. +struct ASanStackVariableDescription { + const char *Name; // Name of the variable that will be displayed by asan + // if a stack-related bug is reported. + uint64_t Size; // Size of the variable in bytes. + size_t LifetimeSize; // Size in bytes to use for lifetime analysis check. + // Will be rounded up to Granularity. + size_t Alignment; // Alignment of the variable (power of 2). + AllocaInst *AI; // The actual AllocaInst. + size_t Offset; // Offset from the beginning of the frame; + // set by ComputeASanStackFrameLayout. + unsigned Line; // Line number. +}; + +// Output data struct for ComputeASanStackFrameLayout. +struct ASanStackFrameLayout { + size_t Granularity; // Shadow granularity. + size_t FrameAlignment; // Alignment for the entire frame. + size_t FrameSize; // Size of the frame in bytes. +}; + +ASanStackFrameLayout ComputeASanStackFrameLayout( + // The array of stack variables. The elements may get reordered and changed. + SmallVectorImpl<ASanStackVariableDescription> &Vars, + // AddressSanitizer's shadow granularity. Usually 8, may also be 16, 32, 64. + size_t Granularity, + // The minimal size of the left-most redzone (header). + // At least 4 pointer sizes, power of 2, and >= Granularity. + // The resulting FrameSize should be multiple of MinHeaderSize. + size_t MinHeaderSize); + +// Compute frame description, see DescribeAddressIfStack in ASan runtime. +SmallString<64> ComputeASanStackFrameDescription( + const SmallVectorImpl<ASanStackVariableDescription> &Vars); + +// Returns shadow bytes with marked red zones. This shadow represents the state +// if the stack frame when all local variables are inside of the own scope. +SmallVector<uint8_t, 64> +GetShadowBytes(const SmallVectorImpl<ASanStackVariableDescription> &Vars, + const ASanStackFrameLayout &Layout); + +// Returns shadow bytes with marked red zones and after scope. This shadow +// represents the state if the stack frame when all local variables are outside +// of the own scope. +SmallVector<uint8_t, 64> GetShadowBytesAfterScope( + // The array of stack variables. The elements may get reordered and changed. + const SmallVectorImpl<ASanStackVariableDescription> &Vars, + const ASanStackFrameLayout &Layout); + +} // llvm namespace + +#endif // LLVM_TRANSFORMS_UTILS_ASANSTACKFRAMELAYOUT_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/AddDiscriminators.h b/clang-r353983e/include/llvm/Transforms/Utils/AddDiscriminators.h new file mode 100644 index 00000000..f512c6c0 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/AddDiscriminators.h @@ -0,0 +1,31 @@ +//===- AddDiscriminators.h --------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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 Function; + +class AddDiscriminatorsPass : public PassInfoMixin<AddDiscriminatorsPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/BasicBlockUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/BasicBlockUtils.h new file mode 100644 index 00000000..4e763289 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -0,0 +1,339 @@ +//===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This family of functions perform manipulations on basic blocks, and +// instructions contained within basic blocks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H +#define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H + +// FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Analysis/DomTreeUpdater.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/InstrTypes.h" +#include <cassert> + +namespace llvm { + +class BlockFrequencyInfo; +class BranchProbabilityInfo; +class DominatorTree; +class DomTreeUpdater; +class Function; +class Instruction; +class LoopInfo; +class MDNode; +class MemoryDependenceResults; +class MemorySSAUpdater; +class ReturnInst; +class TargetLibraryInfo; +class Value; + +/// Replace contents of every block in \p BBs with single unreachable +/// instruction. If \p Updates is specified, collect all necessary DT updates +/// into this vector. If \p KeepOneInputPHIs is true, one-input Phis in +/// successors of blocks being deleted will be preserved. +void DetatchDeadBlocks(ArrayRef <BasicBlock *> BBs, + SmallVectorImpl<DominatorTree::UpdateType> *Updates, + bool KeepOneInputPHIs = false); + +/// Delete the specified block, which must have no predecessors. +void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, + bool KeepOneInputPHIs = false); + +/// Delete the specified blocks from \p BB. The set of deleted blocks must have +/// no predecessors that are not being deleted themselves. \p BBs must have no +/// duplicating blocks. If there are loops among this set of blocks, all +/// relevant loop info updates should be done before this function is called. +/// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks +/// being deleted will be preserved. +void DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, + DomTreeUpdater *DTU = nullptr, + bool KeepOneInputPHIs = false); + +/// 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, + MemoryDependenceResults *MemDep = nullptr); + +/// 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); + +/// Attempts to merge a block into its predecessor, if possible. The return +/// value indicates success or failure. +bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, + LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr, + MemoryDependenceResults *MemDep = nullptr); + +/// 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); + +/// 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); + +/// 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); + +/// Option class for critical edge splitting. +/// +/// This provides a builder interface for overriding the default options used +/// during critical edge splitting. +struct CriticalEdgeSplittingOptions { + DominatorTree *DT; + LoopInfo *LI; + MemorySSAUpdater *MSSAU; + bool MergeIdenticalEdges = false; + bool KeepOneInputPHIs = false; + bool PreserveLCSSA = false; + + CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, + LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr) + : DT(DT), LI(LI), MSSAU(MSSAU) {} + + CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { + MergeIdenticalEdges = true; + return *this; + } + + CriticalEdgeSplittingOptions &setKeepOneInputPHIs() { + KeepOneInputPHIs = true; + return *this; + } + + CriticalEdgeSplittingOptions &setPreserveLCSSA() { + PreserveLCSSA = true; + return *this; + } +}; + +/// 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 +/// critical edge block. This is most commonly interesting with switch +/// instructions, which may have many edges to any one destination. This +/// ensures that all edges to that dest go to one block instead of each going +/// to a different block, but isn't the standard definition of a "critical +/// edge". +/// +/// It is invalid to call this function on a critical edge that starts at an +/// IndirectBrInst. Splitting these edges will almost always create an invalid +/// program because the address of the new block won't be the one that is jumped +/// to. +BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum, + const CriticalEdgeSplittingOptions &Options = + CriticalEdgeSplittingOptions()); + +inline BasicBlock * +SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, + const CriticalEdgeSplittingOptions &Options = + CriticalEdgeSplittingOptions()) { + return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), + Options); +} + +/// 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()) { + bool MadeChange = false; + Instruction *TI = (*PI)->getTerminator(); + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + if (TI->getSuccessor(i) == Succ) + MadeChange |= !!SplitCriticalEdge(TI, i, Options); + return MadeChange; +} + +/// 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 = + CriticalEdgeSplittingOptions()) { + Instruction *TI = Src->getTerminator(); + unsigned i = 0; + while (true) { + assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); + if (TI->getSuccessor(i) == Dst) + return SplitCriticalEdge(TI, i, Options); + ++i; + } +} + +/// 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()); + +/// Split the edge connecting specified block. +BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr); + +/// 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, + MemorySSAUpdater *MSSAU = nullptr); + +/// 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 +/// details on this case. +/// +/// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but +/// no other analyses. In particular, it does not preserve LoopSimplify +/// (because it's complicated to handle the case where one of the edges being +/// split is an exit of a loop with other exits). +BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, + const char *Suffix, + DominatorTree *DT = nullptr, + LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr, + bool PreserveLCSSA = false); + +/// 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 +/// (because it's complicated to handle the case where one of the edges being +/// split is an exit of a loop with other exits). +void SplitLandingPadPredecessors( + BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix, + const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false); + +/// 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, + DomTreeUpdater *DTU = nullptr); + +/// Split the containing block at the specified instruction - everything before +/// SplitBefore stays in the old basic block, and the rest of the instructions +/// in the BB are moved to a new block. The two blocks are connected by a +/// conditional branch (with value of Cmp being the condition). +/// Before: +/// Head +/// SplitBefore +/// Tail +/// After: +/// Head +/// if (Cond) +/// ThenBlock +/// SplitBefore +/// Tail +/// +/// If Unreachable is true, then ThenBlock ends with +/// UnreachableInst, otherwise it branches to Tail. +/// Returns the NewBasicBlock's terminator. +/// +/// Updates DT and LI if given. +Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, + bool Unreachable, + MDNode *BranchWeights = nullptr, + DominatorTree *DT = nullptr, + LoopInfo *LI = nullptr); + +/// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, +/// but also creates the ElseBlock. +/// Before: +/// Head +/// SplitBefore +/// Tail +/// After: +/// Head +/// if (Cond) +/// ThenBlock +/// else +/// ElseBlock +/// SplitBefore +/// Tail +void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, + Instruction **ThenTerm, + Instruction **ElseTerm, + MDNode *BranchWeights = nullptr); + +/// 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); + +// Split critical edges where the source of the edge is an indirectbr +// instruction. This isn't always possible, but we can handle some easy cases. +// This is useful because MI is unable to split such critical edges, +// which means it will not be able to sink instructions along those edges. +// This is especially painful for indirect branches with many successors, where +// we end up having to prepare all outgoing values in the origin block. +// +// Our normal algorithm for splitting critical edges requires us to update +// the outgoing edges of the edge origin block, but for an indirectbr this +// is hard, since it would require finding and updating the block addresses +// the indirect branch uses. But if a block only has a single indirectbr +// predecessor, with the others being regular branches, we can do it in a +// different way. +// Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr. +// We can split D into D0 and D1, where D0 contains only the PHIs from D, +// and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and +// create the following structure: +// A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1 +// If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly. +bool SplitIndirectBrCriticalEdges(Function &F, + BranchProbabilityInfo *BPI = nullptr, + BlockFrequencyInfo *BFI = nullptr); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/BreakCriticalEdges.h b/clang-r353983e/include/llvm/Transforms/Utils/BreakCriticalEdges.h new file mode 100644 index 00000000..3644f1ed --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/BreakCriticalEdges.h @@ -0,0 +1,28 @@ +//===- BreakCriticalEdges.h - Critical Edge Elimination Pass --------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// BreakCriticalEdges pass - Break all of the critical edges in the CFG by +// inserting a dummy basic block. This pass may be "required" by passes that +// cannot deal with critical edges. For this usage, the structure type is +// forward declared. This pass obviously invalidates the CFG, but can update +// dominator trees. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_BREAKCRITICALEDGES_H +#define LLVM_TRANSFORMS_UTILS_BREAKCRITICALEDGES_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +struct BreakCriticalEdgesPass : public PassInfoMixin<BreakCriticalEdgesPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} // namespace llvm +#endif // LLVM_TRANSFORMS_UTILS_BREAKCRITICALEDGES_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/BuildLibCalls.h b/clang-r353983e/include/llvm/Transforms/Utils/BuildLibCalls.h new file mode 100644 index 00000000..6c61cbeb --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/BuildLibCalls.h @@ -0,0 +1,177 @@ +//===- BuildLibCalls.h - Utility builder for libcalls -----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file exposes an interface to build some C language libcalls for +// optimization passes that need to call the various functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H +#define LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H + +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/IRBuilder.h" + +namespace llvm { + class Value; + class DataLayout; + class TargetLibraryInfo; + + /// 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); + bool inferLibFuncAttributes(Module *M, StringRef Name, const TargetLibraryInfo &TLI); + + /// Check whether the overloaded unary floating point function + /// corresponding to \a Ty is available. + bool hasUnaryFloatFn(const TargetLibraryInfo *TLI, Type *Ty, + LibFunc DoubleFn, LibFunc FloatFn, + LibFunc LongDoubleFn); + + /// Get the name of the overloaded unary floating point function + /// corresponding to \a Ty. + StringRef getUnaryFloatFn(const TargetLibraryInfo *TLI, Type *Ty, + LibFunc DoubleFn, LibFunc FloatFn, + LibFunc LongDoubleFn); + + /// 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); + + /// 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); + + /// 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); + + /// 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); + + /// 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"); + + /// 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"); + + /// 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); + + /// 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); + + /// Emit a call to the memcmp function. + Value *emitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, + const DataLayout &DL, const TargetLibraryInfo *TLI); + + /// 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 AttributeList &Attrs); + + /// Emit a call to the unary function DoubleFn, FloatFn or LongDoubleFn, + /// depending of the type of Op. + Value *emitUnaryFloatFnCall(Value *Op, const TargetLibraryInfo *TLI, + LibFunc DoubleFn, LibFunc FloatFn, + LibFunc LongDoubleFn, IRBuilder<> &B, + const AttributeList &Attrs); + + /// Emit a call to the binary function named 'Name' (e.g. 'fmin'). This + /// function is known to take type matching 'Op1' and 'Op2' and return one + /// value with the same type. If 'Op1/Op2' are long double, 'l' is added as + /// the suffix of name, if 'Op1/Op2' are float, we add a 'f' suffix. + Value *emitBinaryFloatFnCall(Value *Op1, Value *Op2, StringRef Name, + IRBuilder<> &B, const AttributeList &Attrs); + + /// Emit a call to the putchar function. This assumes that Char is an integer. + Value *emitPutChar(Value *Char, IRBuilder<> &B, const TargetLibraryInfo *TLI); + + /// 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 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); + + /// Emit a call to the fputc_unlocked function. This assumes that Char is an + /// i32, and File is a pointer to FILE. + Value *emitFPutCUnlocked(Value *Char, Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fputs 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); + + /// Emit a call to the fputs_unlocked function. Str is required to be a + /// pointer and File is a pointer to FILE. + Value *emitFPutSUnlocked(Value *Str, Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + + /// 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); + + /// Emit a call to the malloc function. + Value *emitMalloc(Value *Num, IRBuilder<> &B, const DataLayout &DL, + const TargetLibraryInfo *TLI); + + /// Emit a call to the calloc function. + Value *emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs, + IRBuilder<> &B, const TargetLibraryInfo &TLI); + + /// Emit a call to the fwrite_unlocked function. This assumes that Ptr is a + /// pointer, Size is an 'intptr_t', N is nmemb and File is a pointer to FILE. + Value *emitFWriteUnlocked(Value *Ptr, Value *Size, Value *N, Value *File, + IRBuilder<> &B, const DataLayout &DL, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fgetc_unlocked function. File is a pointer to FILE. + Value *emitFGetCUnlocked(Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fgets_unlocked function. Str is required to be a + /// pointer, Size is an i32 and File is a pointer to FILE. + Value *emitFGetSUnlocked(Value *Str, Value *Size, Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fread_unlocked function. This assumes that Ptr is a + /// pointer, Size is an 'intptr_t', N is nmemb and File is a pointer to FILE. + Value *emitFReadUnlocked(Value *Ptr, Value *Size, Value *N, Value *File, + IRBuilder<> &B, const DataLayout &DL, + const TargetLibraryInfo *TLI); +} + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/BypassSlowDivision.h b/clang-r353983e/include/llvm/Transforms/Utils/BypassSlowDivision.h new file mode 100644 index 00000000..47105592 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/BypassSlowDivision.h @@ -0,0 +1,69 @@ +//===- llvm/Transforms/Utils/BypassSlowDivision.h ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains an optimization for div and rem on architectures that +// execute short instructions significantly faster than longer instructions. +// For example, on Intel Atom 32-bit divides are slow enough that during +// runtime it is profitable to check the value of the operands, and if they are +// positive and less than 256 use an unsigned 8-bit divide. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H +#define LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseMapInfo.h" +#include <cstdint> + +namespace llvm { + +class BasicBlock; +class Value; + +struct DivRemMapKey { + bool SignedOp; + Value *Dividend; + Value *Divisor; + + DivRemMapKey(bool InSignedOp, Value *InDividend, Value *InDivisor) + : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {} +}; + +template <> struct DenseMapInfo<DivRemMapKey> { + static bool isEqual(const DivRemMapKey &Val1, const DivRemMapKey &Val2) { + return Val1.SignedOp == Val2.SignedOp && Val1.Dividend == Val2.Dividend && + Val1.Divisor == Val2.Divisor; + } + + static DivRemMapKey getEmptyKey() { + return DivRemMapKey(false, nullptr, nullptr); + } + + static DivRemMapKey getTombstoneKey() { + return DivRemMapKey(true, nullptr, nullptr); + } + + static unsigned getHashValue(const DivRemMapKey &Val) { + return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^ + reinterpret_cast<uintptr_t>(Val.Divisor)) ^ + (unsigned)Val.SignedOp; + } +}; + +/// This optimization identifies DIV instructions in a BB that can be +/// profitably bypassed and carried out with a shorter, faster divide. +/// +/// This optimization may add basic blocks immediately after BB; for obvious +/// reasons, you shouldn't pass those blocks to bypassSlowDivision. +bool bypassSlowDivision( + BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/CallPromotionUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/CallPromotionUtils.h new file mode 100644 index 00000000..d9d171c6 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/CallPromotionUtils.h @@ -0,0 +1,53 @@ +//===- CallPromotionUtils.h - Utilities for call promotion ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file declares utilities useful for promoting indirect call sites to +// direct call sites. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H +#define LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H + +#include "llvm/IR/CallSite.h" + +namespace llvm { + +/// Return true if the given indirect call site can be made to call \p Callee. +/// +/// This function ensures that the number and type of the call site's arguments +/// and return value match those of the given function. If the types do not +/// match exactly, they must at least be bitcast compatible. If \p FailureReason +/// is non-null and the indirect call cannot be promoted, the failure reason +/// will be stored in it. +bool isLegalToPromote(CallSite CS, Function *Callee, + const char **FailureReason = nullptr); + +/// Promote the given indirect call site to unconditionally call \p Callee. +/// +/// This function promotes the given call site, returning the direct call or +/// invoke instruction. If the function type of the call site doesn't match that +/// of the callee, bitcast instructions are inserted where appropriate. If \p +/// RetBitCast is non-null, it will be used to store the return value bitcast, +/// if created. +Instruction *promoteCall(CallSite CS, Function *Callee, + CastInst **RetBitCast = nullptr); + +/// Promote the given indirect call site to conditionally call \p Callee. +/// +/// This function creates an if-then-else structure at the location of the call +/// site. The original call site is moved into the "else" block. A clone of the +/// indirect call site is promoted, placed in the "then" block, and returned. If +/// \p BranchWeights is non-null, it will be used to set !prof metadata on the +/// new conditional branch. +Instruction *promoteCallWithIfThenElse(CallSite CS, Function *Callee, + MDNode *BranchWeights = nullptr); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/CanonicalizeAliases.h b/clang-r353983e/include/llvm/Transforms/Utils/CanonicalizeAliases.h new file mode 100644 index 00000000..8f23a041 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/CanonicalizeAliases.h @@ -0,0 +1,31 @@ +//===-- CanonicalizeAliases.h - Alias Canonicalization Pass -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file canonicalizes aliases. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_CANONICALIZE_ALIASES_H +#define LLVM_TRANSFORMS_UTILS_CANONICALIZE_ALIASES_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Simple pass that canonicalizes aliases. +class CanonicalizeAliasesPass : public PassInfoMixin<CanonicalizeAliasesPass> { +public: + CanonicalizeAliasesPass() = default; + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CANONICALIZE_ALIASESH diff --git a/clang-r353983e/include/llvm/Transforms/Utils/Cloning.h b/clang-r353983e/include/llvm/Transforms/Utils/Cloning.h new file mode 100644 index 00000000..86775b1a --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/Cloning.h @@ -0,0 +1,280 @@ +//===- Cloning.h - Clone various parts of LLVM programs ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines various functions that are used to clone chunks of LLVM +// code for various purposes. This varies from copying whole modules into new +// modules, to cloning functions with different arguments, to inlining +// functions, to copying basic blocks to support loop unrolling or superblock +// formation, etc. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_CLONING_H +#define LLVM_TRANSFORMS_UTILS_CLONING_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Twine.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/InlineCost.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Transforms/Utils/ValueMapper.h" +#include <functional> +#include <memory> +#include <vector> + +namespace llvm { + +class AllocaInst; +class BasicBlock; +class BlockFrequencyInfo; +class CallInst; +class CallGraph; +class DebugInfoFinder; +class DominatorTree; +class Function; +class Instruction; +class InvokeInst; +class Loop; +class LoopInfo; +class Module; +class ProfileSummaryInfo; +class ReturnInst; +class DomTreeUpdater; + +/// Return an exact copy of the specified module +std::unique_ptr<Module> CloneModule(const Module &M); +std::unique_ptr<Module> CloneModule(const Module &M, ValueToValueMapTy &VMap); + +/// Return a copy of the specified module. The ShouldCloneDefinition function +/// controls whether a specific GlobalValue's definition is cloned. If the +/// function returns false, the module copy will contain an external reference +/// in place of the global definition. +std::unique_ptr<Module> +CloneModule(const Module &M, ValueToValueMapTy &VMap, + function_ref<bool(const GlobalValue *)> ShouldCloneDefinition); + +/// This struct can be used to capture information about code +/// being cloned, while it is being cloned. +struct ClonedCodeInfo { + /// This is set to true if the cloned code contains a normal call instruction. + bool ContainsCalls = false; + + /// This is set to true if the cloned code contains a 'dynamic' alloca. + /// Dynamic allocas are allocas that are either not in the entry block or they + /// are in the entry block but are not a constant size. + bool ContainsDynamicAllocas = false; + + /// All cloned call sites that have operand bundles attached are appended to + /// this vector. This vector may contain nulls or undefs if some of the + /// originally inserted callsites were DCE'ed after they were cloned. + std::vector<WeakTrackingVH> OperandBundleCallSites; + + ClonedCodeInfo() = default; +}; + +/// Return a copy of the specified basic block, but without +/// embedding the block into a particular function. The block returned is an +/// exact copy of the specified basic block, without any remapping having been +/// performed. Because of this, this is only suitable for applications where +/// the basic block will be inserted into the same function that it was cloned +/// from (loop unrolling would use this, for example). +/// +/// Also, note that this function makes a direct copy of the basic block, and +/// can thus produce illegal LLVM code. In particular, it will copy any PHI +/// nodes from the original block, even though there are no predecessors for the +/// newly cloned block (thus, phi nodes will have to be updated). Also, this +/// block will branch to the old successors of the original block: these +/// successors will have to have any PHI nodes updated to account for the new +/// incoming edges. +/// +/// The correlation between instructions in the source and result basic blocks +/// is recorded in the VMap map. +/// +/// If you have a particular suffix you'd like to use to add to any cloned +/// names, specify it as the optional third parameter. +/// +/// If you would like the basic block to be auto-inserted into the end of a +/// function, you can specify it as the optional fourth parameter. +/// +/// If you would like to collect additional information about the cloned +/// function, you can specify a ClonedCodeInfo object with the optional fifth +/// parameter. +BasicBlock *CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, + const Twine &NameSuffix = "", Function *F = nullptr, + ClonedCodeInfo *CodeInfo = nullptr, + DebugInfoFinder *DIFinder = nullptr); + +/// 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. +/// +/// VMap contains no non-identity GlobalValue mappings and debug info metadata +/// will not be cloned. +/// +Function *CloneFunction(Function *F, ValueToValueMapTy &VMap, + ClonedCodeInfo *CodeInfo = nullptr); + +/// Clone OldFunc into NewFunc, transforming the old arguments into references +/// to VMap values. Note that if NewFunc already has basic blocks, the ones +/// cloned into it will be added to the end of the function. This function +/// fills in a list of return instructions, and can optionally remap types +/// and/or append the specified suffix to all values cloned. +/// +/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue +/// mappings. +/// +void CloneFunctionInto(Function *NewFunc, const Function *OldFunc, + ValueToValueMapTy &VMap, bool ModuleLevelChanges, + SmallVectorImpl<ReturnInst*> &Returns, + const char *NameSuffix = "", + ClonedCodeInfo *CodeInfo = nullptr, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr); + +void CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc, + const Instruction *StartingInst, + ValueToValueMapTy &VMap, bool ModuleLevelChanges, + SmallVectorImpl<ReturnInst *> &Returns, + const char *NameSuffix = "", + ClonedCodeInfo *CodeInfo = nullptr); + +/// This works exactly like CloneFunctionInto, +/// except that it does some simple constant prop and DCE on the fly. The +/// effect of this is to copy significantly less code in cases where (for +/// example) a function call with constant arguments is inlined, and those +/// constant arguments cause a significant amount of code in the callee to be +/// dead. Since this doesn't produce an exactly copy of the input, it can't be +/// used for things like CloneFunction or CloneModule. +/// +/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue +/// mappings. +/// +void CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, + ValueToValueMapTy &VMap, bool ModuleLevelChanges, + SmallVectorImpl<ReturnInst*> &Returns, + const char *NameSuffix = "", + ClonedCodeInfo *CodeInfo = nullptr, + Instruction *TheCall = nullptr); + +/// This class captures the data input to the InlineFunction call, and records +/// the auxiliary results produced by it. +class InlineFunctionInfo { +public: + explicit InlineFunctionInfo(CallGraph *cg = nullptr, + std::function<AssumptionCache &(Function &)> + *GetAssumptionCache = nullptr, + ProfileSummaryInfo *PSI = nullptr, + BlockFrequencyInfo *CallerBFI = nullptr, + BlockFrequencyInfo *CalleeBFI = nullptr) + : CG(cg), GetAssumptionCache(GetAssumptionCache), PSI(PSI), + CallerBFI(CallerBFI), CalleeBFI(CalleeBFI) {} + + /// If non-null, InlineFunction will update the callgraph to reflect the + /// changes it makes. + CallGraph *CG; + std::function<AssumptionCache &(Function &)> *GetAssumptionCache; + ProfileSummaryInfo *PSI; + BlockFrequencyInfo *CallerBFI, *CalleeBFI; + + /// InlineFunction fills this in with all static allocas that get copied into + /// the caller. + SmallVector<AllocaInst *, 4> StaticAllocas; + + /// InlineFunction fills this in with callsites that were inlined from the + /// callee. This is only filled in if CG is non-null. + SmallVector<WeakTrackingVH, 8> InlinedCalls; + + /// All of the new call sites inlined into the caller. + /// + /// 'InlineFunction' fills this in by scanning the inlined instructions, and + /// only if CG is null. If CG is non-null, instead the value handle + /// `InlinedCalls` above is used. + SmallVector<CallSite, 8> InlinedCallSites; + + void reset() { + StaticAllocas.clear(); + InlinedCalls.clear(); + InlinedCallSites.clear(); + } +}; + +/// This function inlines the called function into the basic +/// block of the caller. This returns false if it is not possible to inline +/// this call. The program is still in a well defined state if this occurs +/// though. +/// +/// Note that this only does one level of inlining. For example, if the +/// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now +/// exists in the instruction stream. Similarly this will inline a recursive +/// function by one level. +/// +/// Note that while this routine is allowed to cleanup and optimize the +/// *inlined* code to minimize the actual inserted code, it must not delete +/// code in the caller as users of this routine may have pointers to +/// instructions in the caller that need to remain stable. +/// +/// If ForwardVarArgsTo is passed, inlining a function with varargs is allowed +/// and all varargs at the callsite will be passed to any calls to +/// ForwardVarArgsTo. The caller of InlineFunction has to make sure any varargs +/// are only used by ForwardVarArgsTo. +InlineResult InlineFunction(CallInst *C, InlineFunctionInfo &IFI, + AAResults *CalleeAAR = nullptr, + bool InsertLifetime = true); +InlineResult InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI, + AAResults *CalleeAAR = nullptr, + bool InsertLifetime = true); +InlineResult InlineFunction(CallSite CS, InlineFunctionInfo &IFI, + AAResults *CalleeAAR = nullptr, + bool InsertLifetime = true, + Function *ForwardVarArgsTo = nullptr); + +/// Clones a loop \p OrigLoop. Returns the loop and the blocks in \p +/// Blocks. +/// +/// 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, + DominatorTree *DT, + SmallVectorImpl<BasicBlock *> &Blocks); + +/// Remaps instructions in \p Blocks using the mapping in \p VMap. +void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks, + ValueToValueMapTy &VMap); + +/// Split edge between BB and PredBB and duplicate all non-Phi instructions +/// from BB between its beginning and the StopAt instruction into the split +/// block. Phi nodes are not duplicated, but their uses are handled correctly: +/// we replace them with the uses of corresponding Phi inputs. ValueMapping +/// is used to map the original instructions from BB to their newly-created +/// copies. Returns the split block. +BasicBlock *DuplicateInstructionsInSplitBetween(BasicBlock *BB, + BasicBlock *PredBB, + Instruction *StopAt, + ValueToValueMapTy &ValueMapping, + DomTreeUpdater &DTU); + +/// Updates profile information by adjusting the entry count by adding +/// entryDelta then scaling callsite information by the new count divided by the +/// old count. VMap is used during inlinng to also update the new clone +void updateProfileCallee( + Function *Callee, int64_t entryDelta, + const ValueMap<const Value *, WeakTrackingVH> *VMap = nullptr); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CLONING_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/CodeExtractor.h b/clang-r353983e/include/llvm/Transforms/Utils/CodeExtractor.h new file mode 100644 index 00000000..becbf0ea --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/CodeExtractor.h @@ -0,0 +1,178 @@ +//===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// A utility to support extracting code from one function into its own +// stand-alone function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H +#define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include <limits> + +namespace llvm { + +class BasicBlock; +class BlockFrequency; +class BlockFrequencyInfo; +class BranchProbabilityInfo; +class AssumptionCache; +class CallInst; +class DominatorTree; +class Function; +class Instruction; +class Loop; +class Module; +class Type; +class Value; + + /// Utility class for extracting code into a new function. + /// + /// This utility provides a simple interface for extracting some sequence of + /// code into its own function, replacing it with a call to that function. It + /// also provides various methods to query about the nature and result of + /// such a transformation. + /// + /// The rough algorithm used is: + /// 1) Find both the inputs and outputs for the extracted region. + /// 2) Pass the inputs as arguments, remapping them within the extracted + /// function to arguments. + /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas + /// as arguments, and inserting stores to the arguments for any scalars. + class CodeExtractor { + using ValueSet = SetVector<Value *>; + + // Various bits of state computed on construction. + DominatorTree *const DT; + const bool AggregateArgs; + BlockFrequencyInfo *BFI; + BranchProbabilityInfo *BPI; + AssumptionCache *AC; + + // If true, varargs functions can be extracted. + bool AllowVarArgs; + + // Bits of intermediate state computed at various phases of extraction. + SetVector<BasicBlock *> Blocks; + unsigned NumExitBlocks = std::numeric_limits<unsigned>::max(); + Type *RetTy; + + // Suffix to use when creating extracted function (appended to the original + // function name + "."). If empty, the default is to use the entry block + // label, if non-empty, otherwise "extracted". + std::string Suffix; + + public: + /// Create a code extractor for a sequence of blocks. + /// + /// Given a sequence of basic blocks where the first block in the sequence + /// dominates the rest, prepare a code extractor object for pulling this + /// sequence out into its new function. When a DominatorTree is also given, + /// extra checking and transformations are enabled. If AllowVarArgs is true, + /// vararg functions can be extracted. This is safe, if all vararg handling + /// code is extracted, including vastart. If AllowAlloca is true, then + /// extraction of blocks containing alloca instructions would be possible, + /// however code extractor won't validate whether extraction is legal. + CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, + bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, + BranchProbabilityInfo *BPI = nullptr, + AssumptionCache *AC = nullptr, + bool AllowVarArgs = false, bool AllowAlloca = false, + std::string Suffix = ""); + + /// Create a code extractor for a loop body. + /// + /// Behaves just like the generic code sequence constructor, but uses the + /// block sequence of the loop. + CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false, + BlockFrequencyInfo *BFI = nullptr, + BranchProbabilityInfo *BPI = nullptr, + AssumptionCache *AC = nullptr, + std::string Suffix = ""); + + /// Perform the extraction, returning the new function. + /// + /// Returns zero when called on a CodeExtractor instance where isEligible + /// returns false. + Function *extractCodeRegion(); + + /// Test whether this code extractor is eligible. + /// + /// Based on the blocks used when constructing the code extractor, + /// determine whether it is eligible for extraction. + bool isEligible() const { return !Blocks.empty(); } + + /// Compute the set of input values and output values for the code. + /// + /// These can be used either when performing the extraction or to evaluate + /// the expected size of a call to the extracted function. Note that this + /// work cannot be cached between the two as once we decide to extract + /// a code sequence, that sequence is modified, including changing these + /// sets, before extraction occurs. These modifications won't have any + /// significant impact on the cost however. + void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, + const ValueSet &Allocas) const; + + /// Check if life time marker nodes can be hoisted/sunk into the outline + /// region. + /// + /// Returns true if it is safe to do the code motion. + bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const; + + /// Find the set of allocas whose life ranges are contained within the + /// outlined region. + /// + /// Allocas which have life_time markers contained in the outlined region + /// should be pushed to the outlined function. The address bitcasts that + /// are used by the lifetime markers are also candidates for shrink- + /// wrapping. The instructions that need to be sunk are collected in + /// 'Allocas'. + void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, + BasicBlock *&ExitBlock) const; + + /// Find or create a block within the outline region for placing hoisted + /// code. + /// + /// CommonExitBlock is block outside the outline region. It is the common + /// successor of blocks inside the region. If there exists a single block + /// inside the region that is the predecessor of CommonExitBlock, that block + /// will be returned. Otherwise CommonExitBlock will be split and the + /// original block will be added to the outline region. + BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock); + + private: + void severSplitPHINodesOfEntry(BasicBlock *&Header); + void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits); + void splitReturnBlocks(); + + Function *constructFunction(const ValueSet &inputs, + const ValueSet &outputs, + BasicBlock *header, + BasicBlock *newRootNode, BasicBlock *newHeader, + Function *oldFunction, Module *M); + + void moveCodeToFunction(Function *newFunction); + + void calculateNewCallTerminatorWeights( + BasicBlock *CodeReplacer, + DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, + BranchProbabilityInfo *BPI); + + CallInst *emitCallAndSwitchStatement(Function *newFunction, + BasicBlock *newHeader, + ValueSet &inputs, ValueSet &outputs); + }; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/CtorUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/CtorUtils.h new file mode 100644 index 00000000..3625ee66 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/CtorUtils.h @@ -0,0 +1,31 @@ +//===- CtorUtils.h - Helpers for working with global_ctors ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines functions that are used to process llvm.global_ctors. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_CTORUTILS_H +#define LLVM_TRANSFORMS_UTILS_CTORUTILS_H + +#include "llvm/ADT/STLExtras.h" + +namespace llvm { + +class GlobalVariable; +class Function; +class Module; + +/// Call "ShouldRemove" for every entry in M's global_ctor list and remove the +/// entries for which it returns true. Return true if anything changed. +bool optimizeGlobalCtorsList(Module &M, + function_ref<bool(Function *)> ShouldRemove); + +} // End llvm namespace + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/EntryExitInstrumenter.h b/clang-r353983e/include/llvm/Transforms/Utils/EntryExitInstrumenter.h new file mode 100644 index 00000000..3913693a --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/EntryExitInstrumenter.h @@ -0,0 +1,35 @@ +//===- EntryExitInstrumenter.h - Function Entry/Exit Instrumentation ------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// EntryExitInstrumenter pass - Instrument function entry/exit with calls to +// mcount(), @__cyg_profile_func_{enter,exit} and the like. There are two +// variants, intended to run pre- and post-inlining, respectively. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H +#define LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Function; + +struct EntryExitInstrumenterPass + : public PassInfoMixin<EntryExitInstrumenterPass> { + EntryExitInstrumenterPass(bool PostInlining) : PostInlining(PostInlining) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + bool PostInlining; +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/EscapeEnumerator.h b/clang-r353983e/include/llvm/Transforms/Utils/EscapeEnumerator.h new file mode 100644 index 00000000..e667796c --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/EscapeEnumerator.h @@ -0,0 +1,48 @@ +//===-- EscapeEnumerator.h --------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines a helper class that enumerates all possible exits from a function, +// including exception handling. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_ESCAPEENUMERATOR_H +#define LLVM_TRANSFORMS_UTILS_ESCAPEENUMERATOR_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" + +namespace llvm { + +/// EscapeEnumerator - This is a little algorithm to find all escape points +/// from a function so that "finally"-style code can be inserted. In addition +/// to finding the existing return and unwind instructions, it also (if +/// necessary) transforms any call instructions into invokes and sends them to +/// a landing pad. +class EscapeEnumerator { + Function &F; + const char *CleanupBBName; + + Function::iterator StateBB, StateE; + IRBuilder<> Builder; + bool Done; + bool HandleExceptions; + +public: + EscapeEnumerator(Function &F, const char *N = "cleanup", + bool HandleExceptions = true) + : F(F), CleanupBBName(N), StateBB(F.begin()), StateE(F.end()), + Builder(F.getContext()), Done(false), + HandleExceptions(HandleExceptions) {} + + IRBuilder<> *Next(); +}; + +} + +#endif // LLVM_TRANSFORMS_UTILS_ESCAPEENUMERATOR_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/Evaluator.h b/clang-r353983e/include/llvm/Transforms/Utils/Evaluator.h new file mode 100644 index 00000000..bffd65f7 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/Evaluator.h @@ -0,0 +1,132 @@ +//===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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/CallSite.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/Value.h" +#include "llvm/Support/Casting.h" +#include <cassert> +#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; + } + + /// Given call site return callee and list of its formal arguments + Function *getCalleeWithFormalArgs(CallSite &CS, + SmallVector<Constant *, 8> &Formals); + + /// Given call site and callee returns list of callee formal argument + /// values converting them when necessary + bool getFormalParams(CallSite &CS, Function *F, + SmallVector<Constant *, 8> &Formals); + + /// Casts call result to a type of bitcast call expression + Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV); + + 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; +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/FunctionComparator.h b/clang-r353983e/include/llvm/Transforms/Utils/FunctionComparator.h new file mode 100644 index 00000000..4e2571b1 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/FunctionComparator.h @@ -0,0 +1,392 @@ +//===- FunctionComparator.h - Function Comparator ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the FunctionComparator and GlobalNumberState classes which +// are used by the MergeFunctions pass for comparing functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H +#define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/ValueMap.h" +#include "llvm/Support/AtomicOrdering.h" +#include "llvm/Support/Casting.h" +#include <cstdint> +#include <tuple> + +namespace llvm { + +class APFloat; +class APInt; +class BasicBlock; +class Constant; +class Function; +class GlobalValue; +class InlineAsm; +class Instruction; +class MDNode; +class Type; +class Value; + +/// GlobalNumberState assigns an integer to each global value in the program, +/// which is used by the comparison routine to order references to globals. This +/// state must be preserved throughout the pass, because Functions and other +/// globals need to maintain their relative order. Globals are assigned a number +/// when they are first visited. This order is deterministic, and so the +/// assigned numbers are as well. When two functions are merged, neither number +/// is updated. If the symbols are weak, this would be incorrect. If they are +/// strong, then one will be replaced at all references to the other, and so +/// direct callsites will now see one or the other symbol, and no update is +/// necessary. Note that if we were guaranteed unique names, we could just +/// compare those, but this would not work for stripped bitcodes or for those +/// few symbols without a name. +class GlobalNumberState { + struct Config : ValueMapConfig<GlobalValue *> { + enum { FollowRAUW = false }; + }; + + // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW + // occurs, the mapping does not change. Tracking changes is unnecessary, and + // also problematic for weak symbols (which may be overwritten). + using ValueNumberMap = ValueMap<GlobalValue *, uint64_t, Config>; + ValueNumberMap GlobalNumbers; + + // The next unused serial number to assign to a global. + uint64_t NextNumber = 0; + +public: + GlobalNumberState() = default; + + uint64_t getNumber(GlobalValue* Global) { + ValueNumberMap::iterator MapIter; + bool Inserted; + std::tie(MapIter, Inserted) = GlobalNumbers.insert({Global, NextNumber}); + if (Inserted) + NextNumber++; + return MapIter->second; + } + + void erase(GlobalValue *Global) { + GlobalNumbers.erase(Global); + } + + void clear() { + GlobalNumbers.clear(); + } +}; + +/// FunctionComparator - Compares two functions to determine whether or not +/// they will generate machine code with the same behaviour. DataLayout is +/// used if available. The comparator always fails conservatively (erring on the +/// side of claiming that two functions are different). +class FunctionComparator { +public: + FunctionComparator(const Function *F1, const Function *F2, + GlobalNumberState* GN) + : FnL(F1), FnR(F2), GlobalNumbers(GN) {} + + /// Test whether the two functions have equivalent behaviour. + int compare(); + + /// Hash a function. Equivalent functions will have the same hash, and unequal + /// functions will have different hashes with high probability. + using FunctionHash = uint64_t; + static FunctionHash functionHash(Function &); + +protected: + /// Start the comparison. + void beginCompare() { + sn_mapL.clear(); + sn_mapR.clear(); + } + + /// Compares the signature and other general attributes of the two functions. + int compareSignature() const; + + /// Test whether two basic blocks have equivalent behaviour. + int cmpBasicBlocks(const BasicBlock *BBL, const BasicBlock *BBR) const; + + /// Constants comparison. + /// Its analog to lexicographical comparison between hypothetical numbers + /// of next format: + /// <bitcastability-trait><raw-bit-contents> + /// + /// 1. Bitcastability. + /// Check whether L's type could be losslessly bitcasted to R's type. + /// On this stage method, in case when lossless bitcast is not possible + /// method returns -1 or 1, thus also defining which type is greater in + /// context of bitcastability. + /// Stage 0: If types are equal in terms of cmpTypes, then we can go straight + /// to the contents comparison. + /// If types differ, remember types comparison result and check + /// whether we still can bitcast types. + /// Stage 1: Types that satisfies isFirstClassType conditions are always + /// greater then others. + /// Stage 2: Vector is greater then non-vector. + /// If both types are vectors, then vector with greater bitwidth is + /// greater. + /// If both types are vectors with the same bitwidth, then types + /// are bitcastable, and we can skip other stages, and go to contents + /// comparison. + /// Stage 3: Pointer types are greater than non-pointers. If both types are + /// pointers of the same address space - go to contents comparison. + /// Different address spaces: pointer with greater address space is + /// greater. + /// Stage 4: Types are neither vectors, nor pointers. And they differ. + /// We don't know how to bitcast them. So, we better don't do it, + /// and return types comparison result (so it determines the + /// relationship among constants we don't know how to bitcast). + /// + /// Just for clearance, let's see how the set of constants could look + /// on single dimension axis: + /// + /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors] + /// Where: NFCT - Not a FirstClassType + /// FCT - FirstClassTyp: + /// + /// 2. Compare raw contents. + /// It ignores types on this stage and only compares bits from L and R. + /// Returns 0, if L and R has equivalent contents. + /// -1 or 1 if values are different. + /// Pretty trivial: + /// 2.1. If contents are numbers, compare numbers. + /// Ints with greater bitwidth are greater. Ints with same bitwidths + /// compared by their contents. + /// 2.2. "And so on". Just to avoid discrepancies with comments + /// perhaps it would be better to read the implementation itself. + /// 3. And again about overall picture. Let's look back at how the ordered set + /// of constants will look like: + /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors] + /// + /// Now look, what could be inside [FCT, "others"], for example: + /// [FCT, "others"] = + /// [ + /// [double 0.1], [double 1.23], + /// [i32 1], [i32 2], + /// { double 1.0 }, ; StructTyID, NumElements = 1 + /// { i32 1 }, ; StructTyID, NumElements = 1 + /// { double 1, i32 1 }, ; StructTyID, NumElements = 2 + /// { i32 1, double 1 } ; StructTyID, NumElements = 2 + /// ] + /// + /// Let's explain the order. Float numbers will be less than integers, just + /// because of cmpType terms: FloatTyID < IntegerTyID. + /// Floats (with same fltSemantics) are sorted according to their value. + /// Then you can see integers, and they are, like a floats, + /// could be easy sorted among each others. + /// The structures. Structures are grouped at the tail, again because of their + /// TypeID: StructTyID > IntegerTyID > FloatTyID. + /// Structures with greater number of elements are greater. Structures with + /// greater elements going first are greater. + /// The same logic with vectors, arrays and other possible complex types. + /// + /// Bitcastable constants. + /// Let's assume, that some constant, belongs to some group of + /// "so-called-equal" values with different types, and at the same time + /// belongs to another group of constants with equal types + /// and "really" equal values. + /// + /// Now, prove that this is impossible: + /// + /// If constant A with type TyA is bitcastable to B with type TyB, then: + /// 1. All constants with equal types to TyA, are bitcastable to B. Since + /// those should be vectors (if TyA is vector), pointers + /// (if TyA is pointer), or else (if TyA equal to TyB), those types should + /// be equal to TyB. + /// 2. All constants with non-equal, but bitcastable types to TyA, are + /// bitcastable to B. + /// Once again, just because we allow it to vectors and pointers only. + /// This statement could be expanded as below: + /// 2.1. All vectors with equal bitwidth to vector A, has equal bitwidth to + /// vector B, and thus bitcastable to B as well. + /// 2.2. All pointers of the same address space, no matter what they point to, + /// bitcastable. So if C is pointer, it could be bitcasted to A and to B. + /// So any constant equal or bitcastable to A is equal or bitcastable to B. + /// QED. + /// + /// In another words, for pointers and vectors, we ignore top-level type and + /// look at their particular properties (bit-width for vectors, and + /// address space for pointers). + /// If these properties are equal - compare their contents. + int cmpConstants(const Constant *L, const Constant *R) const; + + /// Compares two global values by number. Uses the GlobalNumbersState to + /// identify the same gobals across function calls. + int cmpGlobalValues(GlobalValue *L, GlobalValue *R) const; + + /// Assign or look up previously assigned numbers for the two values, and + /// return whether the numbers are equal. Numbers are assigned in the order + /// visited. + /// Comparison order: + /// Stage 0: Value that is function itself is always greater then others. + /// If left and right values are references to their functions, then + /// they are equal. + /// Stage 1: Constants are greater than non-constants. + /// If both left and right are constants, then the result of + /// cmpConstants is used as cmpValues result. + /// Stage 2: InlineAsm instances are greater than others. If both left and + /// right are InlineAsm instances, InlineAsm* pointers casted to + /// integers and compared as numbers. + /// Stage 3: For all other cases we compare order we meet these values in + /// their functions. If right value was met first during scanning, + /// then left value is greater. + /// In another words, we compare serial numbers, for more details + /// see comments for sn_mapL and sn_mapR. + int cmpValues(const Value *L, const Value *R) const; + + /// Compare two Instructions for equivalence, similar to + /// Instruction::isSameOperationAs. + /// + /// Stages are listed in "most significant stage first" order: + /// On each stage below, we do comparison between some left and right + /// operation parts. If parts are non-equal, we assign parts comparison + /// result to the operation comparison result and exit from method. + /// Otherwise we proceed to the next stage. + /// Stages: + /// 1. Operations opcodes. Compared as numbers. + /// 2. Number of operands. + /// 3. Operation types. Compared with cmpType method. + /// 4. Compare operation subclass optional data as stream of bytes: + /// just convert it to integers and call cmpNumbers. + /// 5. Compare in operation operand types with cmpType in + /// most significant operand first order. + /// 6. Last stage. Check operations for some specific attributes. + /// For example, for Load it would be: + /// 6.1.Load: volatile (as boolean flag) + /// 6.2.Load: alignment (as integer numbers) + /// 6.3.Load: ordering (as underlying enum class value) + /// 6.4.Load: synch-scope (as integer numbers) + /// 6.5.Load: range metadata (as integer ranges) + /// On this stage its better to see the code, since its not more than 10-15 + /// strings for particular instruction, and could change sometimes. + /// + /// Sets \p needToCmpOperands to true if the operands of the instructions + /// still must be compared afterwards. In this case it's already guaranteed + /// that both instructions have the same number of operands. + int cmpOperations(const Instruction *L, const Instruction *R, + bool &needToCmpOperands) const; + + /// cmpType - compares two types, + /// defines total ordering among the types set. + /// + /// Return values: + /// 0 if types are equal, + /// -1 if Left is less than Right, + /// +1 if Left is greater than Right. + /// + /// Description: + /// Comparison is broken onto stages. Like in lexicographical comparison + /// stage coming first has higher priority. + /// On each explanation stage keep in mind total ordering properties. + /// + /// 0. Before comparison we coerce pointer types of 0 address space to + /// integer. + /// We also don't bother with same type at left and right, so + /// just return 0 in this case. + /// + /// 1. If types are of different kind (different type IDs). + /// Return result of type IDs comparison, treating them as numbers. + /// 2. If types are integers, check that they have the same width. If they + /// are vectors, check that they have the same count and subtype. + /// 3. Types have the same ID, so check whether they are one of: + /// * Void + /// * Float + /// * Double + /// * X86_FP80 + /// * FP128 + /// * PPC_FP128 + /// * Label + /// * Metadata + /// We can treat these types as equal whenever their IDs are same. + /// 4. If Left and Right are pointers, return result of address space + /// comparison (numbers comparison). We can treat pointer types of same + /// address space as equal. + /// 5. If types are complex. + /// Then both Left and Right are to be expanded and their element types will + /// be checked with the same way. If we get Res != 0 on some stage, return it. + /// Otherwise return 0. + /// 6. For all other cases put llvm_unreachable. + int cmpTypes(Type *TyL, Type *TyR) const; + + int cmpNumbers(uint64_t L, uint64_t R) const; + int cmpAPInts(const APInt &L, const APInt &R) const; + int cmpAPFloats(const APFloat &L, const APFloat &R) const; + int cmpMem(StringRef L, StringRef R) const; + + // The two functions undergoing comparison. + const Function *FnL, *FnR; + +private: + int cmpOrderings(AtomicOrdering L, AtomicOrdering R) const; + int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const; + int cmpAttrs(const AttributeList L, const AttributeList R) const; + int cmpRangeMetadata(const MDNode *L, const MDNode *R) const; + int cmpOperandBundlesSchema(const Instruction *L, const Instruction *R) const; + + /// Compare two GEPs for equivalent pointer arithmetic. + /// Parts to be compared for each comparison stage, + /// most significant stage first: + /// 1. Address space. As numbers. + /// 2. Constant offset, (using GEPOperator::accumulateConstantOffset method). + /// 3. Pointer operand type (using cmpType method). + /// 4. Number of operands. + /// 5. Compare operands, using cmpValues method. + int cmpGEPs(const GEPOperator *GEPL, const GEPOperator *GEPR) const; + int cmpGEPs(const GetElementPtrInst *GEPL, + const GetElementPtrInst *GEPR) const { + return cmpGEPs(cast<GEPOperator>(GEPL), cast<GEPOperator>(GEPR)); + } + + /// Assign serial numbers to values from left function, and values from + /// right function. + /// Explanation: + /// Being comparing functions we need to compare values we meet at left and + /// right sides. + /// Its easy to sort things out for external values. It just should be + /// the same value at left and right. + /// But for local values (those were introduced inside function body) + /// we have to ensure they were introduced at exactly the same place, + /// and plays the same role. + /// Let's assign serial number to each value when we meet it first time. + /// Values that were met at same place will be with same serial numbers. + /// In this case it would be good to explain few points about values assigned + /// to BBs and other ways of implementation (see below). + /// + /// 1. Safety of BB reordering. + /// It's safe to change the order of BasicBlocks in function. + /// Relationship with other functions and serial numbering will not be + /// changed in this case. + /// As follows from FunctionComparator::compare(), we do CFG walk: we start + /// from the entry, and then take each terminator. So it doesn't matter how in + /// fact BBs are ordered in function. And since cmpValues are called during + /// this walk, the numbering depends only on how BBs located inside the CFG. + /// So the answer is - yes. We will get the same numbering. + /// + /// 2. Impossibility to use dominance properties of values. + /// If we compare two instruction operands: first is usage of local + /// variable AL from function FL, and second is usage of local variable AR + /// from FR, we could compare their origins and check whether they are + /// defined at the same place. + /// But, we are still not able to compare operands of PHI nodes, since those + /// could be operands from further BBs we didn't scan yet. + /// So it's impossible to use dominance properties in general. + mutable DenseMap<const Value*, int> sn_mapL, sn_mapR; + + // The global state we will use + GlobalNumberState* GlobalNumbers; +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/FunctionImportUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/FunctionImportUtils.h new file mode 100644 index 00000000..9c2a9ea5 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/FunctionImportUtils.h @@ -0,0 +1,126 @@ +//===- FunctionImportUtils.h - Importing support utilities -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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. + SetVector<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; + + /// Set of llvm.*used values, in order to validate that we don't try + /// to promote any non-renamable values. + SmallPtrSet<GlobalValue *, 8> Used; + + /// Keep track of any COMDATs that require renaming (because COMDAT + /// leader was promoted and renamed). Maps from original COMDAT to one + /// with new name. + DenseMap<const Comdat *, Comdat *> RenamedComdats; + + /// Check if we should promote the given local value to global scope. + bool shouldPromoteLocalToGlobal(const GlobalValue *SGV); + +#ifndef NDEBUG + /// Check if the given value is a local that can't be renamed (promoted). + /// Only used in assertion checking, and disabled under NDEBUG since the Used + /// set will not be populated. + bool isNonRenamableLocal(const GlobalValue &GV) const; +#endif + + /// 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, which it will always + /// do when \p DoPromote is true (or when importing a local). + std::string getName(const GlobalValue *SGV, bool DoPromote); + + /// 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. When \p DoPromote is true then we must adjust the + /// linkage for a required promotion of a local to global scope. + GlobalValue::LinkageTypes getLinkage(const GlobalValue *SGV, bool DoPromote); + +public: + FunctionImportGlobalProcessing( + Module &M, const ModuleSummaryIndex &Index, + SetVector<GlobalValue *> *GlobalsToImport = nullptr) + : M(M), ImportIndex(Index), GlobalsToImport(GlobalsToImport) { + // If we have a ModuleSummaryIndex but no function to import, + // then this is the primary module being compiled in a ThinLTO + // 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); + +#ifndef NDEBUG + // First collect those in the llvm.used set. + collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); + // Next collect those in the llvm.compiler.used set. + collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true); +#endif + } + + bool run(); + + static bool doImportAsDefinition(const GlobalValue *SGV, + SetVector<GlobalValue *> *GlobalsToImport); +}; + +/// Perform in-place global value handling on the given Module for +/// exported local functions renamed and promoted for ThinLTO. +bool renameModuleForThinLTO( + Module &M, const ModuleSummaryIndex &Index, + SetVector<GlobalValue *> *GlobalsToImport = nullptr); + +/// Compute synthetic function entry counts. +void computeSyntheticCounts(ModuleSummaryIndex &Index); + +} // End llvm namespace + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/GlobalStatus.h b/clang-r353983e/include/llvm/Transforms/Utils/GlobalStatus.h new file mode 100644 index 00000000..519593c9 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/GlobalStatus.h @@ -0,0 +1,84 @@ +//===- GlobalStatus.h - Compute status info for globals ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H +#define LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H + +#include "llvm/Support/AtomicOrdering.h" + +namespace llvm { + +class Constant; +class Function; +class Value; + +/// It is safe to destroy a constant iff it is only used by constants itself. +/// Note that constants cannot be cyclic, so this test is pretty easy to +/// implement recursively. +/// +bool isSafeToDestroyConstant(const Constant *C); + +/// As we analyze each global, keep track of some information about it. If we +/// find out that the address of the global is taken, none of this info will be +/// accurate. +struct GlobalStatus { + /// True if the global's address is used in a comparison. + bool IsCompared = false; + + /// True if the global is ever loaded. If the global isn't ever loaded it + /// can be deleted. + bool IsLoaded = false; + + /// Keep track of what stores to the global look like. + enum StoredType { + /// There is no store to this global. It can thus be marked constant. + NotStored, + + /// This global is stored to, but the only thing stored is the constant it + /// was initialized with. This is only tracked for scalar globals. + InitializerStored, + + /// This global is stored to, but only its initializer and one other value + /// is ever stored to it. If this global isStoredOnce, we track the value + /// stored to it in StoredOnceValue below. This is only tracked for scalar + /// globals. + StoredOnce, + + /// This global is stored to by multiple values or something else that we + /// cannot track. + Stored + } StoredType = NotStored; + + /// If only one value (besides the initializer constant) is ever stored to + /// this global, keep track of what value it is. + Value *StoredOnceValue = nullptr; + + /// These start out null/false. When the first accessing function is noticed, + /// it is recorded. When a second different accessing function is noticed, + /// HasMultipleAccessingFunctions is set to true. + const Function *AccessingFunction = nullptr; + bool HasMultipleAccessingFunctions = false; + + /// Set to true if this global has a user that is not an instruction (e.g. a + /// constant expr or GV initializer). + bool HasNonInstructionUser = false; + + /// Set to the strongest atomic ordering requirement. + AtomicOrdering Ordering = AtomicOrdering::NotAtomic; + + GlobalStatus(); + + /// Look at all uses of the global and fill in the GlobalStatus structure. If + /// the global has its address taken, return true to indicate we can't do + /// anything with it. + static bool analyzeGlobal(const Value *V, GlobalStatus &GS); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/GuardUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/GuardUtils.h new file mode 100644 index 00000000..3b365c56 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/GuardUtils.h @@ -0,0 +1,29 @@ +//===-- GuardUtils.h - Utils for work with guards ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Utils that are used to perform transformations related to guards and their +// conditions. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_GUARDUTILS_H +#define LLVM_TRANSFORMS_UTILS_GUARDUTILS_H + +namespace llvm { + +class CallInst; +class Function; + +/// Splits control flow at point of \p Guard, replacing it with explicit branch +/// by the condition of guard's first argument. The taken branch then goes to +/// the block that contains \p Guard's successors, and the non-taken branch +/// goes to a newly-created deopt block that contains a sole call of the +/// deoptimize function \p DeoptIntrinsic. +void makeGuardControlFlowExplicit(Function *DeoptIntrinsic, CallInst *Guard); + +} // llvm + +#endif // LLVM_TRANSFORMS_UTILS_GUARDUTILS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h b/clang-r353983e/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h new file mode 100644 index 00000000..033ea05b --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h @@ -0,0 +1,106 @@ +//===-- ImportedFunctionsInliningStatistics.h -------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Generating inliner statistics for imported functions, mostly useful for +// ThinLTO. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H +#define LLVM_TRANSFORMS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include <string> +#include <vector> + +namespace llvm { +class Module; +class Function; +/// Calculate and dump ThinLTO specific inliner stats. +/// The main statistics are: +/// (1) Number of inlined imported functions, +/// (2) Number of imported functions inlined into importing module (indirect), +/// (3) Number of non imported functions inlined into importing module +/// (indirect). +/// The difference between first and the second is that first stat counts +/// all performed inlines on imported functions, but the second one only the +/// functions that have been eventually inlined to a function in the importing +/// module (by a chain of inlines). Because llvm uses bottom-up inliner, it is +/// possible to e.g. import function `A`, `B` and then inline `B` to `A`, +/// and after this `A` might be too big to be inlined into some other function +/// that calls it. It calculates this statistic by building graph, where +/// the nodes are functions, and edges are performed inlines and then by marking +/// the edges starting from not imported function. +/// +/// If `Verbose` is set to true, then it also dumps statistics +/// per each inlined function, sorted by the greatest inlines count like +/// - number of performed inlines +/// - number of performed inlines to importing module +class ImportedFunctionsInliningStatistics { +private: + /// InlineGraphNode represents node in graph of inlined functions. + struct InlineGraphNode { + // Default-constructible and movable. + InlineGraphNode() = default; + InlineGraphNode(InlineGraphNode &&) = default; + InlineGraphNode &operator=(InlineGraphNode &&) = default; + + llvm::SmallVector<InlineGraphNode *, 8> InlinedCallees; + /// Incremented every direct inline. + int32_t NumberOfInlines = 0; + /// Number of inlines into non imported function (possibly indirect via + /// intermediate inlines). Computed based on graph search. + int32_t NumberOfRealInlines = 0; + bool Imported = false; + bool Visited = false; + }; + +public: + ImportedFunctionsInliningStatistics() = default; + ImportedFunctionsInliningStatistics( + const ImportedFunctionsInliningStatistics &) = delete; + + /// Set information like AllFunctions, ImportedFunctions, ModuleName. + void setModuleInfo(const Module &M); + /// Record inline of @param Callee to @param Caller for statistis. + void recordInline(const Function &Caller, const Function &Callee); + /// Dump stats computed with InlinerStatistics class. + /// If @param Verbose is true then separate statistics for every inlined + /// function will be printed. + void dump(bool Verbose); + +private: + /// Creates new Node in NodeMap and sets attributes, or returns existed one. + InlineGraphNode &createInlineGraphNode(const Function &); + void calculateRealInlines(); + void dfs(InlineGraphNode &GraphNode); + + using NodesMapTy = + llvm::StringMap<std::unique_ptr<InlineGraphNode>>; + using SortedNodesTy = + std::vector<const NodesMapTy::MapEntryTy*>; + /// Returns vector of elements sorted by + /// (-NumberOfInlines, -NumberOfRealInlines, FunctionName). + SortedNodesTy getSortedNodes(); + +private: + /// This map manage life of all InlineGraphNodes. Unique pointer to + /// InlineGraphNode used since the node pointers are also saved in the + /// InlinedCallees vector. If it would store InlineGraphNode instead then the + /// address of the node would not be invariant. + NodesMapTy NodesMap; + /// Non external functions that have some other function inlined inside. + std::vector<StringRef> NonImportedCallers; + int AllFunctions = 0; + int ImportedFunctions = 0; + StringRef ModuleName; +}; + +} // llvm + +#endif // LLVM_TRANSFORMS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/IntegerDivision.h b/clang-r353983e/include/llvm/Transforms/Utils/IntegerDivision.h new file mode 100644 index 00000000..35cae9aa --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/IntegerDivision.h @@ -0,0 +1,72 @@ +//===- llvm/Transforms/Utils/IntegerDivision.h ------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains an implementation of 32bit and 64bit scalar integer +// division for targets that don't have native support. It's largely derived +// from compiler-rt's implementations of __udivsi3 and __udivmoddi4, +// but hand-tuned for targets that prefer less control flow. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_INTEGERDIVISION_H +#define LLVM_TRANSFORMS_UTILS_INTEGERDIVISION_H + +namespace llvm { + class BinaryOperator; +} + +namespace llvm { + + /// Generate code to calculate the remainder of two integers, replacing Rem + /// with the generated code. This currently generates code using the udiv + /// expansion, but future work includes generating more specialized code, + /// e.g. when more information about the operands are known. Implements both + /// 32bit and 64bit scalar division. + /// + /// Replace Rem with generated code. + bool expandRemainder(BinaryOperator *Rem); + + /// Generate code to divide two integers, replacing Div with the generated + /// code. This currently generates code similarly to compiler-rt's + /// implementations, but future work includes generating more specialized code + /// when more information about the operands are known. Implements both + /// 32bit and 64bit scalar division. + /// + /// Replace Div with generated code. + bool expandDivision(BinaryOperator* Div); + + /// Generate code to calculate the remainder of two integers, replacing Rem + /// with the generated code. Uses ExpandReminder with a 32bit Rem which + /// makes it useful for targets with little or no support for less than + /// 32 bit arithmetic. + /// + /// Replace Rem with generated code. + bool expandRemainderUpTo32Bits(BinaryOperator *Rem); + + /// Generate code to calculate the remainder of two integers, replacing Rem + /// with the generated code. Uses ExpandReminder with a 64bit Rem. + /// + /// Replace Rem with generated code. + bool expandRemainderUpTo64Bits(BinaryOperator *Rem); + + /// Generate code to divide two integers, replacing Div with the generated + /// code. Uses ExpandDivision with a 32bit Div which makes it useful for + /// targets with little or no support for less than 32 bit arithmetic. + /// + /// Replace Rem with generated code. + bool expandDivisionUpTo32Bits(BinaryOperator *Div); + + /// Generate code to divide two integers, replacing Div with the generated + /// code. Uses ExpandDivision with a 64bit Div. + /// + /// Replace Rem with generated code. + bool expandDivisionUpTo64Bits(BinaryOperator *Div); + +} // End llvm namespace + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/LCSSA.h b/clang-r353983e/include/llvm/Transforms/Utils/LCSSA.h new file mode 100644 index 00000000..b01c8022 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LCSSA.h @@ -0,0 +1,43 @@ +//===- LCSSA.h - Loop-closed SSA transform Pass -----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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, FunctionAnalysisManager &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LCSSA_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/LibCallsShrinkWrap.h b/clang-r353983e/include/llvm/Transforms/Utils/LibCallsShrinkWrap.h new file mode 100644 index 00000000..ff1537ac --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LibCallsShrinkWrap.h @@ -0,0 +1,26 @@ +//===- LibCallsShrinkWrap.h - Shrink Wrap Library Calls -------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LIBCALLSSHRINKWRAP_H +#define LLVM_TRANSFORMS_UTILS_LIBCALLSSHRINKWRAP_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LibCallsShrinkWrapPass : public PassInfoMixin<LibCallsShrinkWrapPass> { +public: + static StringRef name() { return "LibCallsShrinkWrapPass"; } + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LIBCALLSSHRINKWRAP_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/Local.h b/clang-r353983e/include/llvm/Transforms/Utils/Local.h new file mode 100644 index 00000000..641b6458 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/Local.h @@ -0,0 +1,513 @@ +//===- Local.h - Functions to perform local transformations -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This family of functions perform various local transformations to the +// program. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H +#define LLVM_TRANSFORMS_UTILS_LOCAL_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/DomTreeUpdater.h" +#include "llvm/Analysis/Utils/Local.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/GetElementPtrTypeIterator.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Support/Casting.h" +#include <cstdint> +#include <limits> + +namespace llvm { + +class AllocaInst; +class AssumptionCache; +class BasicBlock; +class BranchInst; +class CallInst; +class DbgVariableIntrinsic; +class DbgValueInst; +class DIBuilder; +class Function; +class Instruction; +class LazyValueInfo; +class LoadInst; +class MDNode; +class MemorySSAUpdater; +class PHINode; +class StoreInst; +class TargetLibraryInfo; +class TargetTransformInfo; + +/// A set of parameters used to control the transforms in the SimplifyCFG pass. +/// Options may change depending on the position in the optimization pipeline. +/// For example, canonical form that includes switches and branches may later be +/// replaced by lookup tables and selects. +struct SimplifyCFGOptions { + int BonusInstThreshold; + bool ForwardSwitchCondToPhi; + bool ConvertSwitchToLookupTable; + bool NeedCanonicalLoop; + bool SinkCommonInsts; + AssumptionCache *AC; + + SimplifyCFGOptions(unsigned BonusThreshold = 1, + bool ForwardSwitchCond = false, + bool SwitchToLookup = false, bool CanonicalLoops = true, + bool SinkCommon = false, + AssumptionCache *AssumpCache = nullptr) + : BonusInstThreshold(BonusThreshold), + ForwardSwitchCondToPhi(ForwardSwitchCond), + ConvertSwitchToLookupTable(SwitchToLookup), + NeedCanonicalLoop(CanonicalLoops), + SinkCommonInsts(SinkCommon), + AC(AssumpCache) {} + + // Support 'builder' pattern to set members by name at construction time. + SimplifyCFGOptions &bonusInstThreshold(int I) { + BonusInstThreshold = I; + return *this; + } + SimplifyCFGOptions &forwardSwitchCondToPhi(bool B) { + ForwardSwitchCondToPhi = B; + return *this; + } + SimplifyCFGOptions &convertSwitchToLookupTable(bool B) { + ConvertSwitchToLookupTable = B; + return *this; + } + SimplifyCFGOptions &needCanonicalLoops(bool B) { + NeedCanonicalLoop = B; + return *this; + } + SimplifyCFGOptions &sinkCommonInsts(bool B) { + SinkCommonInsts = B; + return *this; + } + SimplifyCFGOptions &setAssumptionCache(AssumptionCache *Cache) { + AC = Cache; + return *this; + } +}; + +//===----------------------------------------------------------------------===// +// Local constant propagation. +// + +/// 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. +bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, + const TargetLibraryInfo *TLI = nullptr, + DomTreeUpdater *DTU = nullptr); + +//===----------------------------------------------------------------------===// +// Local dead code elimination. +// + +/// 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); + +/// Return true if the result produced by the instruction would have no side +/// effects if it was not used. This is equivalent to checking whether +/// isInstructionTriviallyDead would be true if the use count was 0. +bool wouldInstructionBeTriviallyDead(Instruction *I, + const TargetLibraryInfo *TLI = nullptr); + +/// If the specified value is a trivially dead instruction, delete it. +/// If that makes any of its operands trivially dead, delete them too, +/// recursively. Return true if any instructions were deleted. +bool RecursivelyDeleteTriviallyDeadInstructions( + Value *V, const TargetLibraryInfo *TLI = nullptr, + MemorySSAUpdater *MSSAU = nullptr); + +/// Delete all of the instructions in `DeadInsts`, and all other instructions +/// that deleting these in turn causes to be trivially dead. +/// +/// The initial instructions in the provided vector must all have empty use +/// lists and satisfy `isInstructionTriviallyDead`. +/// +/// `DeadInsts` will be used as scratch storage for this routine and will be +/// empty afterward. +void RecursivelyDeleteTriviallyDeadInstructions( + SmallVectorImpl<Instruction *> &DeadInsts, + const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr); + +/// 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); + +/// 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. +bool SimplifyInstructionsInBlock(BasicBlock *BB, + const TargetLibraryInfo *TLI = nullptr); + +/// Replace all the uses of an SSA value in @llvm.dbg intrinsics with +/// undef. This is useful for signaling that a variable, e.g. has been +/// found dead and hence it's unavailable at a given program point. +/// Returns true if the dbg values have been changed. +bool replaceDbgUsesWithUndef(Instruction *I); + +//===----------------------------------------------------------------------===// +// Control Flow Graph Restructuring. +// + +/// 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: +/// x = phi(1, 0, 0, 0) +/// y = and x, z +/// +/// .. and delete the predecessor corresponding to the '1', this will attempt to +/// recursively fold the 'and' to 0. +void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, + DomTreeUpdater *DTU = nullptr); + +/// 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, DomTreeUpdater *DTU = nullptr); + +/// 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, + DomTreeUpdater *DTU = nullptr); + +/// 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); + +/// 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. LoopHeaders is an optional input parameter +/// providing the set of loop headers that SimplifyCFG should not eliminate. +bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, + const SimplifyCFGOptions &Options = {}, + SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr); + +/// 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); + +/// 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); + +/// 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); + +/// 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); + +/// Try to ensure that the alignment of \p V is at least \p PrefAlign bytes. If +/// the owning object can be modified and has an alignment less than \p +/// PrefAlign, it will be increased and \p PrefAlign returned. If the alignment +/// cannot be increased, the known alignment of the value is returned. +/// +/// It is not always possible to modify the alignment of the underlying object, +/// so if alignment is important, a more reliable approach is to simply align +/// all global variables and allocation instructions to their preferred +/// alignment from the beginning. +unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, + const DataLayout &DL, + const Instruction *CxtI = nullptr, + AssumptionCache *AC = nullptr, + const DominatorTree *DT = nullptr); + +/// Try to infer an alignment for the specified pointer. +inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, + const Instruction *CxtI = nullptr, + AssumptionCache *AC = nullptr, + const DominatorTree *DT = nullptr) { + return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); +} + +///===---------------------------------------------------------------------===// +/// Dbg Intrinsic utilities +/// + +/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value +/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, + StoreInst *SI, DIBuilder &Builder); + +/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value +/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, + LoadInst *LI, DIBuilder &Builder); + +/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated +/// llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, + PHINode *LI, DIBuilder &Builder); + +/// Lowers llvm.dbg.declare intrinsics into appropriate set of +/// llvm.dbg.value intrinsics. +bool LowerDbgDeclare(Function &F); + +/// Propagate dbg.value intrinsics through the newly inserted PHIs. +void insertDebugValuesForPHIs(BasicBlock *BB, + SmallVectorImpl<PHINode *> &InsertedPHIs); + +/// Finds all intrinsics declaring local variables as living in the memory that +/// 'V' points to. This may include a mix of dbg.declare and +/// dbg.addr intrinsics. +TinyPtrVector<DbgVariableIntrinsic *> FindDbgAddrUses(Value *V); + +/// Finds the llvm.dbg.value intrinsics describing a value. +void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V); + +/// Finds the debug info intrinsics describing a value. +void findDbgUsers(SmallVectorImpl<DbgVariableIntrinsic *> &DbgInsts, Value *V); + +/// 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 +/// (between the optional Deref operations). Offset can be negative. +bool replaceDbgDeclare(Value *Address, Value *NewAddress, + Instruction *InsertBefore, DIBuilder &Builder, + bool DerefBefore, int Offset, bool DerefAfter); + +/// 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 (between the +/// optional Deref operations). Offset can be negative. The new +/// llvm.dbg.declare is inserted immediately after AI. +bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, + DIBuilder &Builder, bool DerefBefore, + int Offset, bool DerefAfter); + +/// 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); + +/// Assuming the instruction \p I is going to be deleted, attempt to salvage +/// debug users of \p I by writing the effect of \p I in a DIExpression. +/// Returns true if any debug users were updated. +bool salvageDebugInfo(Instruction &I); + +/// Implementation of salvageDebugInfo, applying only to instructions in +/// \p Insns, rather than all debug users of \p I. +bool salvageDebugInfoForDbgValues(Instruction &I, + ArrayRef<DbgVariableIntrinsic *> Insns); + +/// Given an instruction \p I and DIExpression \p DIExpr operating on it, write +/// the effects of \p I into the returned DIExpression, or return nullptr if +/// it cannot be salvaged. \p StackVal: whether DW_OP_stack_value should be +/// appended to the expression. +DIExpression *salvageDebugInfoImpl(Instruction &I, DIExpression *DIExpr, + bool StackVal); + +/// Point debug users of \p From to \p To or salvage them. Use this function +/// only when replacing all uses of \p From with \p To, with a guarantee that +/// \p From is going to be deleted. +/// +/// Follow these rules to prevent use-before-def of \p To: +/// . If \p To is a linked Instruction, set \p DomPoint to \p To. +/// . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction +/// \p To will be inserted after. +/// . If \p To is not an Instruction (e.g a Constant), the choice of +/// \p DomPoint is arbitrary. Pick \p From for simplicity. +/// +/// If a debug user cannot be preserved without reordering variable updates or +/// introducing a use-before-def, it is either salvaged (\ref salvageDebugInfo) +/// or deleted. Returns true if any debug users were updated. +bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, + DominatorTree &DT); + +/// 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. +unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, + bool PreserveLCSSA = false, + DomTreeUpdater *DTU = nullptr); + +/// Convert the CallInst to InvokeInst with the specified unwind edge basic +/// block. This also splits the basic block where CI is located, because +/// InvokeInst is a terminator instruction. Returns the newly split basic +/// block. +BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI, + BasicBlock *UnwindEdge); + +/// Replace 'BB's terminator with one that does not have an unwind successor +/// 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, DomTreeUpdater *DTU = nullptr); + +/// 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, + DomTreeUpdater *DTU = nullptr, + MemorySSAUpdater *MSSAU = nullptr); + +/// Combine the metadata of two instructions so that K can replace J. Some +/// metadata kinds can only be kept if K does not move, meaning it dominated +/// J in the original IR. +/// +/// Metadata not listed as known via KnownIDs is removed +void combineMetadata(Instruction *K, const Instruction *J, + ArrayRef<unsigned> KnownIDs, bool DoesKMove); + +/// Combine the metadata of two instructions so that K can replace J. This +/// specifically handles the case of CSE-like transformations. Some +/// metadata can only be kept if K dominates J. For this to be correct, +/// K cannot be hoisted. +/// +/// Unknown metadata is removed. +void combineMetadataForCSE(Instruction *K, const Instruction *J, + bool DoesKMove); + +/// Patch the replacement so that it is not more restrictive than the value +/// being replaced. It assumes that the replacement does not get moved from +/// its original position. +void patchReplacementInstruction(Instruction *I, Value *Repl); + +// Replace each use of 'From' with 'To', if that use does not belong to basic +// block where 'From' is defined. Returns the number of replacements made. +unsigned replaceNonLocalUsesWith(Instruction *From, Value *To); + +/// 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); +/// 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); + +/// Return true if this call 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 +/// does not have to be made parseable. +/// +/// Most passes can and should ignore this information, and it is only used +/// during lowering by the GC infrastructure. +bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI); + +/// Copy a nonnull metadata node to a new load instruction. +/// +/// This handles mapping it to range metadata if the new load is an integer +/// load instead of a pointer load. +void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI); + +/// Copy a range metadata node to a new load instruction. +/// +/// This handles mapping it to nonnull metadata if the new load is a pointer +/// load instead of an integer load and the range doesn't cover null. +void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, + LoadInst &NewLI); + +/// Remove the debug intrinsic instructions for the given instruction. +void dropDebugUsers(Instruction &I); + +/// Hoist all of the instructions in the \p IfBlock to the dominant block +/// \p DomBlock, by moving its instructions to the insertion point \p InsertPt. +/// +/// The moved instructions receive the insertion point debug location values +/// (DILocations) and their debug intrinsic instructions are removed. +void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, + BasicBlock *BB); + +//===----------------------------------------------------------------------===// +// Intrinsic pattern matching +// + +/// Try to 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 +/// to a basic block. +/// +/// A bitreverse idiom normally requires around 2*BW nodes to be searched (where +/// BW is the bitwidth of the integer type). A bswap idiom requires anywhere up +/// to BW / 4 nodes to be searched, so is significantly faster. +/// +/// This function returns true on a successful match or false otherwise. +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); + +//===----------------------------------------------------------------------===// +// Transform predicates +// + +/// Given an instruction, is it legal to set operand OpIdx to a non-constant +/// value? +bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LOCAL_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/LoopRotationUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/LoopRotationUtils.h new file mode 100644 index 00000000..1e80722e --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LoopRotationUtils.h @@ -0,0 +1,40 @@ +//===- LoopRotationUtils.h - Utilities to perform loop rotation -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file provides utilities to convert a loop into a loop with bottom test. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOOPROTATIONUTILS_H +#define LLVM_TRANSFORMS_UTILS_LOOPROTATIONUTILS_H + +namespace llvm { + +class AssumptionCache; +class DominatorTree; +class Loop; +class LoopInfo; +class MemorySSAUpdater; +class ScalarEvolution; +struct SimplifyQuery; +class TargetTransformInfo; + +/// Convert a loop into a loop with bottom test. It may +/// perform loop latch simplication as well if the flag RotationOnly +/// is false. The flag Threshold represents the size threshold of the loop +/// header. If the loop header's size exceeds the threshold, the loop rotation +/// will give up. The flag IsUtilMode controls the heuristic used in the +/// LoopRotation. If it is true, the profitability heuristic will be ignored. +bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, + AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, + MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, + bool RotationOnly, unsigned Threshold, bool IsUtilMode); + +} // namespace llvm + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/LoopSimplify.h b/clang-r353983e/include/llvm/Transforms/Utils/LoopSimplify.h new file mode 100644 index 00000000..938e46da --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LoopSimplify.h @@ -0,0 +1,64 @@ +//===- LoopSimplify.h - Loop Canonicalization Pass --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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, FunctionAnalysisManager &AM); +}; + +/// 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/clang-r353983e/include/llvm/Transforms/Utils/LoopUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/LoopUtils.h new file mode 100644 index 00000000..a5883ac7 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LoopUtils.h @@ -0,0 +1,346 @@ +//===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines some loop transformation utilities. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H +#define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/DemandedBits.h" +#include "llvm/Analysis/EHPersonalities.h" +#include "llvm/Analysis/IVDescriptors.h" +#include "llvm/Analysis/MustExecute.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/Casting.h" + +namespace llvm { + +class AliasSet; +class AliasSetTracker; +class BasicBlock; +class DataLayout; +class Loop; +class LoopInfo; +class MemoryAccess; +class MemorySSAUpdater; +class OptimizationRemarkEmitter; +class PredicatedScalarEvolution; +class PredIteratorCache; +class ScalarEvolution; +class SCEV; +class TargetLibraryInfo; +class TargetTransformInfo; + +BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, + bool PreserveLCSSA); + +/// Ensure that all exit blocks of the loop are dedicated exits. +/// +/// For any loop exit block with non-loop predecessors, we split the loop +/// predecessors to use a dedicated loop exit block. We update the dominator +/// tree and loop info if provided, and will preserve LCSSA if requested. +bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, + bool PreserveLCSSA); + +/// 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. +/// +/// Returns true if any modifications are made. +bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, + DominatorTree &DT, LoopInfo &LI); + +/// Put loop into LCSSA form. +/// +/// Looks at all instructions in the loop which have uses outside of the +/// current loop. For each, an LCSSA PHI node is inserted and the uses outside +/// the loop are rewritten to use this node. Sub-loops must be in LCSSA form +/// already. +/// +/// LoopInfo and DominatorTree are required and preserved. +/// +/// 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); + +/// Put a loop nest into LCSSA form. +/// +/// This recursively forms LCSSA for a loop nest. +/// +/// LoopInfo and DominatorTree are required and preserved. +/// +/// If ScalarEvolution is passed in, it will be preserved. +/// +/// Returns true if any modifications are made to the loop. +bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, + ScalarEvolution *SE); + +/// Walk the specified region of the CFG (defined by all blocks +/// dominated by the specified block, and that are in the current loop) in +/// reverse depth first order w.r.t the DominatorTree. This allows us to visit +/// uses before definitions, allowing us to sink a loop body in one pass without +/// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, +/// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all +/// instructions of the loop and loop safety information as +/// arguments. Diagnostics is emitted via \p ORE. It returns changed status. +bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, + TargetLibraryInfo *, TargetTransformInfo *, Loop *, + AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, + bool, int &, OptimizationRemarkEmitter *); + +/// 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 +/// first order w.r.t the DominatorTree. This allows us to visit definitions +/// before uses, allowing us to hoist a loop body in one pass without iteration. +/// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout, +/// TargetLibraryInfo, Loop, AliasSet information for all instructions of the +/// loop and loop safety information as arguments. Diagnostics is emitted via \p +/// ORE. It returns changed status. +bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, + TargetLibraryInfo *, Loop *, AliasSetTracker *, + MemorySSAUpdater *, ICFLoopSafetyInfo *, bool, int &, + OptimizationRemarkEmitter *); + +/// This function deletes dead loops. The caller of this function needs to +/// guarantee that the loop is infact dead. +/// The function requires a bunch or prerequisites to be present: +/// - The loop needs to be in LCSSA form +/// - The loop needs to have a Preheader +/// - A unique dedicated exit block must exist +/// +/// This also updates the relevant analysis information in \p DT, \p SE, and \p +/// LI if pointers to those are provided. +/// It also updates the loop PM if an updater struct is provided. + +void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, + LoopInfo *LI); + +/// 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 +/// the stores in the loop, looking for stores to Must pointers which are +/// loop invariant. It takes a set of must-alias values, Loop exit blocks +/// vector, loop exit blocks insertion point vector, PredIteratorCache, +/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions +/// of the loop and loop safety information as arguments. +/// Diagnostics is emitted via \p ORE. It returns changed status. +bool promoteLoopAccessesToScalars( + const SmallSetVector<Value *, 8> &, SmallVectorImpl<BasicBlock *> &, + SmallVectorImpl<Instruction *> &, SmallVectorImpl<MemoryAccess *> &, + PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, + Loop *, AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, + OptimizationRemarkEmitter *); + +/// Does a BFS from a given node to all of its children inside a given loop. +/// The returned vector of nodes includes the starting point. +SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N, + const Loop *CurLoop); + +/// Returns the instructions that use values defined in the loop. +SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); + +/// 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(const Loop *TheLoop, + StringRef Name); + +/// Find named metadata for a loop with an integer value. +llvm::Optional<int> getOptionalIntLoopAttribute(Loop *TheLoop, StringRef Name); + +/// Create a new loop identifier for a loop created from a loop transformation. +/// +/// @param OrigLoopID The loop ID of the loop before the transformation. +/// @param FollowupAttrs List of attribute names that contain attributes to be +/// added to the new loop ID. +/// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited +/// from the original loop. The following values +/// are considered: +/// nullptr : Inherit all attributes from @p OrigLoopID. +/// "" : Do not inherit any attribute from @p OrigLoopID; only use +/// those specified by a followup attribute. +/// "<prefix>": Inherit all attributes except those which start with +/// <prefix>; commonly used to remove metadata for the +/// applied transformation. +/// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return +/// None. +/// +/// @return The loop ID for the after-transformation loop. The following values +/// can be returned: +/// None : No followup attribute was found; it is up to the +/// transformation to choose attributes that make sense. +/// @p OrigLoopID: The original identifier can be reused. +/// nullptr : The new loop has no attributes. +/// MDNode* : A new unique loop identifier. +Optional<MDNode *> +makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs, + const char *InheritOptionsAttrsPrefix = "", + bool AlwaysNew = false); + +/// Look for the loop attribute that disables all transformation heuristic. +bool hasDisableAllTransformsHint(const Loop *L); + +/// The mode sets how eager a transformation should be applied. +enum TransformationMode { + /// The pass can use heuristics to determine whether a transformation should + /// be applied. + TM_Unspecified, + + /// The transformation should be applied without considering a cost model. + TM_Enable, + + /// The transformation should not be applied. + TM_Disable, + + /// Force is a flag and should not be used alone. + TM_Force = 0x04, + + /// The transformation was directed by the user, e.g. by a #pragma in + /// the source code. If the transformation could not be applied, a + /// warning should be emitted. + TM_ForcedByUser = TM_Enable | TM_Force, + + /// The transformation must not be applied. For instance, `#pragma clang loop + /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike + /// general loop metadata, it must not be dropped. Most passes should not + /// behave differently under TM_Disable and TM_SuppressedByUser. + TM_SuppressedByUser = TM_Disable | TM_Force +}; + +/// @{ +/// Get the mode for LLVM's supported loop transformations. +TransformationMode hasUnrollTransformation(Loop *L); +TransformationMode hasUnrollAndJamTransformation(Loop *L); +TransformationMode hasVectorizeTransformation(Loop *L); +TransformationMode hasDistributeTransformation(Loop *L); +TransformationMode hasLICMVersioningTransformation(Loop *L); +/// @} + +/// Set input string into loop metadata by keeping other values intact. +void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, + unsigned V = 0); + +/// Get a loop's estimated trip count based on branch weight metadata. +/// Returns 0 when the count is estimated to be 0, or None when a meaningful +/// estimate can not be made. +Optional<unsigned> getLoopEstimatedTripCount(Loop *L); + +/// Check inner loop (L) backedge count is known to be invariant on all +/// iterations of its outer loop. If the loop has no parent, this is trivially +/// true. +bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE); + +/// 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); + +/// Returns true if is legal to hoist or sink this instruction disregarding the +/// possible introduction of faults. Reasoning about potential faulting +/// instructions is the responsibility of the caller since it is challenging to +/// do efficiently from within this routine. +/// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the +/// target executes at most once per execution of the loop body. This is used +/// to assess the legality of duplicating atomic loads. Generally, this is +/// true when moving out of loop and not true when moving into loops. +/// If \p ORE is set use it to emit optimization remarks. +bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, + Loop *CurLoop, AliasSetTracker *CurAST, + MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop, + bool NoOfMemAccessesTooLarge, + int *LicmMssaOptCap = nullptr, + OptimizationRemarkEmitter *ORE = nullptr); + +/// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. +Value *createMinMaxOp(IRBuilder<> &Builder, + RecurrenceDescriptor::MinMaxRecurrenceKind RK, + Value *Left, Value *Right); + +/// Generates an ordered vector reduction using extracts to reduce the value. +Value * +getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, + RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind = + RecurrenceDescriptor::MRK_Invalid, + ArrayRef<Value *> RedOps = None); + +/// Generates a vector reduction using shufflevectors to reduce the value. +Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, + RecurrenceDescriptor::MinMaxRecurrenceKind + MinMaxKind = RecurrenceDescriptor::MRK_Invalid, + ArrayRef<Value *> RedOps = None); + +/// Create a target reduction of the given vector. The reduction operation +/// is described by the \p Opcode parameter. min/max reductions require +/// additional information supplied in \p Flags. +/// The target is queried to determine if intrinsics or shuffle sequences are +/// required to implement the reduction. +Value *createSimpleTargetReduction(IRBuilder<> &B, + const TargetTransformInfo *TTI, + unsigned Opcode, Value *Src, + TargetTransformInfo::ReductionFlags Flags = + TargetTransformInfo::ReductionFlags(), + ArrayRef<Value *> RedOps = None); + +/// Create a generic target reduction using a recurrence descriptor \p Desc +/// The target is queried to determine if intrinsics or shuffle sequences are +/// required to implement the reduction. +Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, + RecurrenceDescriptor &Desc, Value *Src, + bool NoNaN = false); + +/// Get the intersection (logical and) of all of the potential IR flags +/// of each scalar operation (VL) that will be converted into a vector (I). +/// If OpValue is non-null, we only consider operations similar to OpValue +/// when intersecting. +/// Flag set: NSW, NUW, exact, and all of fast-math. +void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr); + +/// Returns true if we can prove that \p S is defined and always negative in +/// loop \p L. +bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE); + +/// Returns true if we can prove that \p S is defined and always non-negative in +/// loop \p L. +bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, + ScalarEvolution &SE); + +/// Returns true if \p S is defined and never is equal to signed/unsigned max. +bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, + bool Signed); + +/// Returns true if \p S is defined and never is equal to signed/unsigned min. +bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, + bool Signed); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/LoopVersioning.h b/clang-r353983e/include/llvm/Transforms/Utils/LoopVersioning.h new file mode 100644 index 00000000..355c4d7d --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LoopVersioning.h @@ -0,0 +1,151 @@ +//===- LoopVersioning.h - Utility to version a loop -------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines a utility class to perform loop versioning. The versioned +// loop speculates that otherwise may-aliasing memory accesses don't overlap and +// emits checks to prove this. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H +#define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H + +#include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Utils/ValueMapper.h" + +namespace llvm { + +class Loop; +class LoopAccessInfo; +class LoopInfo; +class ScalarEvolution; + +/// This class emits a version of the loop where run-time checks ensure +/// that may-alias pointers can't overlap. +/// +/// It currently only supports single-exit loops and assumes that the loop +/// already has a preheader. +class LoopVersioning { +public: + /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input. + /// It uses runtime check provided by the user. If \p UseLAIChecks is true, + /// we will retain the default checks made by LAI. Otherwise, construct an + /// object having no checks and we expect the user to add them. + LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, + DominatorTree *DT, ScalarEvolution *SE, + bool UseLAIChecks = true); + + /// Performs the CFG manipulation part of versioning the loop including + /// the DominatorTree and LoopInfo updates. + /// + /// The loop that was used to construct the class will be the "versioned" loop + /// i.e. the loop that will receive control if all the memchecks pass. + /// + /// This allows the loop transform pass to operate on the same loop regardless + /// of whether versioning was necessary or not: + /// + /// for each loop L: + /// analyze L + /// if versioning is necessary version L + /// transform L + void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); } + + /// Same but if the client has already precomputed the set of values + /// used outside the loop, this API will allows passing that. + void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside); + + /// Returns the versioned loop. Control flows here if pointers in the + /// loop don't alias (i.e. all memchecks passed). (This loop is actually the + /// same as the original loop that we got constructed with.) + Loop *getVersionedLoop() { return VersionedLoop; } + + /// Returns the fall-back loop. Control flows here if pointers in the + /// loop may alias (i.e. one of the memchecks failed). + Loop *getNonVersionedLoop() { return NonVersionedLoop; } + + /// Sets the runtime alias checks for versioning the loop. + void setAliasChecks( + SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); + + /// Sets the runtime SCEV checks for versioning the loop. + void setSCEVChecks(SCEVUnionPredicate Check); + + /// 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(); + + /// Set up the aliasing scopes based on the memchecks. This needs to + /// be called before the first call to annotateInstWithNoAlias. + void prepareNoAliasMetadata(); + + /// 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: + /// Adds the necessary PHI nodes for the versioned loops based on the + /// loop-defined values used outside of the loop. + /// + /// This needs to be called after versionLoop if there are defs in the loop + /// that are used outside the loop. + void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside); + + /// 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); + } + + /// The original loop. This becomes the "versioned" one. I.e., + /// control flows here if pointers in the loop don't alias. + Loop *VersionedLoop; + /// The fall-back loop. I.e. control flows here if pointers in the + /// loop may alias (memchecks failed). + Loop *NonVersionedLoop; + + /// This maps the instructions from VersionedLoop to their counterpart + /// in NonVersionedLoop. + ValueToValueMapTy VMap; + + /// The set of alias checks that we are versioning for. + SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks; + + /// The set of SCEV checks that we are versioning for. + SCEVUnionPredicate Preds; + + /// Maps a pointer to the pointer checking group that the pointer + /// belongs to. + DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *> + PtrToGroup; + + /// The alias scope corresponding to a pointer checking group. + DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> + GroupToScope; + + /// The list of alias scopes that a pointer checking group can't alias. + DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> + GroupToNonAliasingScopeList; + + /// Analyses used. + const LoopAccessInfo &LAI; + LoopInfo *LI; + DominatorTree *DT; + ScalarEvolution *SE; +}; +} + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/LowerInvoke.h b/clang-r353983e/include/llvm/Transforms/Utils/LowerInvoke.h new file mode 100644 index 00000000..c1198b08 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LowerInvoke.h @@ -0,0 +1,29 @@ +//===- LowerInvoke.h - Eliminate Invoke instructions ----------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This transformation is designed for use by code generators which do not yet +// support stack unwinding. This pass converts 'invoke' instructions to 'call' +// instructions, so that any exception-handling 'landingpad' blocks become dead +// code (which can be removed by running the '-simplifycfg' pass afterwards). +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_TRANSFORMS_UTILS_LOWERINVOKE_H +#define LLVM_TRANSFORMS_UTILS_LOWERINVOKE_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LowerInvokePass : public PassInfoMixin<LowerInvokePass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} + +#endif // LLVM_TRANSFORMS_UTILS_LOWERINVOKE_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/LowerMemIntrinsics.h b/clang-r353983e/include/llvm/Transforms/Utils/LowerMemIntrinsics.h new file mode 100644 index 00000000..8e9d7b52 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/LowerMemIntrinsics.h @@ -0,0 +1,55 @@ +//===- llvm/Transforms/Utils/LowerMemIntrinsics.h ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Lower memset, memcpy, memmov intrinsics to loops (e.g. for targets without +// library support). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOWERMEMINTRINSICS_H +#define LLVM_TRANSFORMS_UTILS_LOWERMEMINTRINSICS_H + +namespace llvm { + +class ConstantInt; +class Instruction; +class MemCpyInst; +class MemMoveInst; +class MemSetInst; +class TargetTransformInfo; +class Value; + +/// Emit a loop implementing the semantics of llvm.memcpy where the size is not +/// a compile-time constant. Loop will be insterted at \p InsertBefore. +void createMemCpyLoopUnknownSize(Instruction *InsertBefore, Value *SrcAddr, + Value *DstAddr, Value *CopyLen, + unsigned SrcAlign, unsigned DestAlign, + bool SrcIsVolatile, bool DstIsVolatile, + const TargetTransformInfo &TTI); + +/// Emit a loop implementing the semantics of an llvm.memcpy whose size is a +/// compile time constant. Loop is inserted at \p InsertBefore. +void createMemCpyLoopKnownSize(Instruction *InsertBefore, Value *SrcAddr, + Value *DstAddr, ConstantInt *CopyLen, + unsigned SrcAlign, unsigned DestAlign, + bool SrcIsVolatile, bool DstIsVolatile, + const TargetTransformInfo &TTI); + + +/// Expand \p MemCpy as a loop. \p MemCpy is not deleted. +void expandMemCpyAsLoop(MemCpyInst *MemCpy, const TargetTransformInfo &TTI); + +/// Expand \p MemMove as a loop. \p MemMove is not deleted. +void expandMemMoveAsLoop(MemMoveInst *MemMove); + +/// Expand \p MemSet as a loop. \p MemSet is not deleted. +void expandMemSetAsLoop(MemSetInst *MemSet); + +} // End llvm namespace + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/Mem2Reg.h b/clang-r353983e/include/llvm/Transforms/Utils/Mem2Reg.h new file mode 100644 index 00000000..76c1c2c5 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/Mem2Reg.h @@ -0,0 +1,30 @@ +//===- Mem2Reg.h - The -mem2reg pass, a wrapper around the Utils lib ------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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/PassManager.h" + +namespace llvm { + +class Function; + +class PromotePass : public PassInfoMixin<PromotePass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_MEM2REG_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/ModuleUtils.h b/clang-r353983e/include/llvm/Transforms/Utils/ModuleUtils.h new file mode 100644 index 00000000..c69af558 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/ModuleUtils.h @@ -0,0 +1,113 @@ +//===-- ModuleUtils.h - Functions to manipulate Modules ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This family of functions perform manipulations on Modules. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_MODULEUTILS_H +#define LLVM_TRANSFORMS_UTILS_MODULEUTILS_H + +#include "llvm/ADT/StringRef.h" +#include <utility> // for std::pair + +namespace llvm { + +template <typename T> class ArrayRef; +class Module; +class Function; +class FunctionCallee; +class GlobalValue; +class GlobalVariable; +class Constant; +class StringRef; +class Value; +class Type; + +/// 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, + Constant *Data = nullptr); + +/// Same as appendToGlobalCtors(), but for global dtors. +void appendToGlobalDtors(Module &M, Function *F, int Priority, + Constant *Data = nullptr); + +FunctionCallee declareSanitizerInitFunction(Module &M, StringRef InitName, + ArrayRef<Type *> InitArgTypes); + +/// Creates sanitizer constructor function, and calls sanitizer's init +/// function from it. +/// \return Returns pair of pointers to constructor, and init functions +/// respectively. +std::pair<Function *, FunctionCallee> createSanitizerCtorAndInitFunctions( + Module &M, StringRef CtorName, StringRef InitName, + ArrayRef<Type *> InitArgTypes, ArrayRef<Value *> InitArgs, + StringRef VersionCheckName = StringRef()); + +/// Creates sanitizer constructor function lazily. If a constructor and init +/// function already exist, this function returns it. Otherwise it calls \c +/// createSanitizerCtorAndInitFunctions. The FunctionsCreatedCallback is invoked +/// in that case, passing the new Ctor and Init function. +/// +/// \return Returns pair of pointers to constructor, and init functions +/// respectively. +std::pair<Function *, FunctionCallee> getOrCreateSanitizerCtorAndInitFunctions( + Module &M, StringRef CtorName, StringRef InitName, + ArrayRef<Type *> InitArgTypes, ArrayRef<Value *> InitArgs, + function_ref<void(Function *, FunctionCallee)> FunctionsCreatedCallback, + StringRef VersionCheckName = StringRef()); + +// Creates and returns a sanitizer init function without argument if it doesn't +// exist, and adds it to the global constructors list. Otherwise it returns the +// existing function. +Function *getOrCreateInitFunction(Module &M, StringRef Name); + +/// Rename all the anon globals in the module using a hash computed from +/// the list of public globals in the module. +bool nameUnamedGlobals(Module &M); + +/// Adds global values to the llvm.used list. +void appendToUsed(Module &M, ArrayRef<GlobalValue *> Values); + +/// Adds global values to the llvm.compiler.used list. +void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values); + +/// Filter out potentially dead comdat functions where other entries keep the +/// entire comdat group alive. +/// +/// This is designed for cases where functions appear to become dead but remain +/// alive due to other live entries in their comdat group. +/// +/// The \p DeadComdatFunctions container should only have pointers to +/// `Function`s which are members of a comdat group and are believed to be +/// dead. +/// +/// After this routine finishes, the only remaining `Function`s in \p +/// DeadComdatFunctions are those where every member of the comdat is listed +/// and thus removing them is safe (provided *all* are removed). +void filterDeadComdatFunctions( + Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions); + +/// Produce a unique identifier for this module by taking the MD5 sum of +/// the names of the module's strong external symbols that are not comdat +/// members. +/// +/// This identifier is normally guaranteed to be unique, or the program would +/// fail to link due to multiply defined symbols. +/// +/// If the module has no strong external symbols (such a module may still have a +/// semantic effect if it performs global initialization), we cannot produce a +/// unique identifier for this module, so we return the empty string. +std::string getUniqueModuleId(Module *M); + +} // End llvm namespace + +#endif // LLVM_TRANSFORMS_UTILS_MODULEUTILS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/NameAnonGlobals.h b/clang-r353983e/include/llvm/Transforms/Utils/NameAnonGlobals.h new file mode 100644 index 00000000..659ebe33 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/NameAnonGlobals.h @@ -0,0 +1,32 @@ +//===-- NameAnonGlobals.h - Anonymous Global Naming Pass --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements naming anonymous globals to make sure they can be +// referred to by ThinLTO. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_NAMEANONGLOBALSS_H +#define LLVM_TRANSFORMS_UTILS_NAMEANONGLOBALSS_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Simple pass that provides a name to every anonymous globals. +class NameAnonGlobalPass : public PassInfoMixin<NameAnonGlobalPass> { +public: + NameAnonGlobalPass() = default; + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_NAMEANONGLOBALS_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/PredicateInfo.h b/clang-r353983e/include/llvm/Transforms/Utils/PredicateInfo.h new file mode 100644 index 00000000..da4a5dcc --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/PredicateInfo.h @@ -0,0 +1,298 @@ +//===- PredicateInfo.h - Build PredicateInfo ----------------------*-C++-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file implements the PredicateInfo analysis, which creates an Extended +/// SSA form for operations used in branch comparisons and llvm.assume +/// comparisons. +/// +/// Copies of these operations are inserted into the true/false edge (and after +/// assumes), and information attached to the copies. All uses of the original +/// operation in blocks dominated by the true/false edge (and assume), are +/// replaced with uses of the copies. This enables passes to easily and sparsely +/// propagate condition based info into the operations that may be affected. +/// +/// Example: +/// %cmp = icmp eq i32 %x, 50 +/// br i1 %cmp, label %true, label %false +/// true: +/// ret i32 %x +/// false: +/// ret i32 1 +/// +/// will become +/// +/// %cmp = icmp eq i32, %x, 50 +/// br i1 %cmp, label %true, label %false +/// true: +/// %x.0 = call \@llvm.ssa_copy.i32(i32 %x) +/// ret i32 %x.0 +/// false: +/// ret i32 1 +/// +/// Using getPredicateInfoFor on x.0 will give you the comparison it is +/// dominated by (the icmp), and that you are located in the true edge of that +/// comparison, which tells you x.0 is 50. +/// +/// In order to reduce the number of copies inserted, predicateinfo is only +/// inserted where it would actually be live. This means if there are no uses of +/// an operation dominated by the branch edges, or by an assume, the associated +/// predicate info is never inserted. +/// +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H +#define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/iterator.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/OrderedInstructions.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/OperandTraits.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" +#include "llvm/PassAnalysisSupport.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <iterator> +#include <memory> +#include <utility> + +namespace llvm { + +class DominatorTree; +class Function; +class Instruction; +class MemoryAccess; +class LLVMContext; +class raw_ostream; + +enum PredicateType { PT_Branch, PT_Assume, PT_Switch }; + +// Base class for all predicate information we provide. +// All of our predicate information has at least a comparison. +class PredicateBase : public ilist_node<PredicateBase> { +public: + PredicateType Type; + // The original operand before we renamed it. + // This can be use by passes, when destroying predicateinfo, to know + // whether they can just drop the intrinsic, or have to merge metadata. + Value *OriginalOp; + PredicateBase(const PredicateBase &) = delete; + PredicateBase &operator=(const PredicateBase &) = delete; + PredicateBase() = delete; + virtual ~PredicateBase() = default; + +protected: + PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {} +}; + +class PredicateWithCondition : public PredicateBase { +public: + Value *Condition; + static bool classof(const PredicateBase *PB) { + return PB->Type == PT_Assume || PB->Type == PT_Branch || + PB->Type == PT_Switch; + } + +protected: + PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition) + : PredicateBase(PT, Op), Condition(Condition) {} +}; + +// Provides predicate information for assumes. Since assumes are always true, +// we simply provide the assume instruction, so you can tell your relative +// position to it. +class PredicateAssume : public PredicateWithCondition { +public: + IntrinsicInst *AssumeInst; + PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition) + : PredicateWithCondition(PT_Assume, Op, Condition), + AssumeInst(AssumeInst) {} + PredicateAssume() = delete; + static bool classof(const PredicateBase *PB) { + return PB->Type == PT_Assume; + } +}; + +// Mixin class for edge predicates. The FROM block is the block where the +// predicate originates, and the TO block is the block where the predicate is +// valid. +class PredicateWithEdge : public PredicateWithCondition { +public: + BasicBlock *From; + BasicBlock *To; + PredicateWithEdge() = delete; + static bool classof(const PredicateBase *PB) { + return PB->Type == PT_Branch || PB->Type == PT_Switch; + } + +protected: + PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From, + BasicBlock *To, Value *Cond) + : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {} +}; + +// Provides predicate information for branches. +class PredicateBranch : public PredicateWithEdge { +public: + // If true, SplitBB is the true successor, otherwise it's the false successor. + bool TrueEdge; + PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB, + Value *Condition, bool TakenEdge) + : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition), + TrueEdge(TakenEdge) {} + PredicateBranch() = delete; + static bool classof(const PredicateBase *PB) { + return PB->Type == PT_Branch; + } +}; + +class PredicateSwitch : public PredicateWithEdge { +public: + Value *CaseValue; + // This is the switch instruction. + SwitchInst *Switch; + PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB, + Value *CaseValue, SwitchInst *SI) + : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB, + SI->getCondition()), + CaseValue(CaseValue), Switch(SI) {} + PredicateSwitch() = delete; + static bool classof(const PredicateBase *PB) { + return PB->Type == PT_Switch; + } +}; + +// This name is used in a few places, so kick it into their own namespace +namespace PredicateInfoClasses { +struct ValueDFS; +} + +/// Encapsulates PredicateInfo, including all data associated with memory +/// accesses. +class PredicateInfo { +private: + // Used to store information about each value we might rename. + struct ValueInfo { + // Information about each possible copy. During processing, this is each + // inserted info. After processing, we move the uninserted ones to the + // uninserted vector. + SmallVector<PredicateBase *, 4> Infos; + SmallVector<PredicateBase *, 4> UninsertedInfos; + }; + // This owns the all the predicate infos in the function, placed or not. + iplist<PredicateBase> AllInfos; + +public: + PredicateInfo(Function &, DominatorTree &, AssumptionCache &); + ~PredicateInfo(); + + void verifyPredicateInfo() const; + + void dump() const; + void print(raw_ostream &) const; + + const PredicateBase *getPredicateInfoFor(const Value *V) const { + return PredicateMap.lookup(V); + } + +protected: + // Used by PredicateInfo annotater, dumpers, and wrapper pass. + friend class PredicateInfoAnnotatedWriter; + friend class PredicateInfoPrinterLegacyPass; + +private: + void buildPredicateInfo(); + void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); + void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); + void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &); + void renameUses(SmallPtrSetImpl<Value *> &); + using ValueDFS = PredicateInfoClasses::ValueDFS; + typedef SmallVectorImpl<ValueDFS> ValueDFSStack; + void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &); + Value *materializeStack(unsigned int &, ValueDFSStack &, Value *); + bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const; + void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &); + ValueInfo &getOrCreateValueInfo(Value *); + void addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op, + PredicateBase *PB); + const ValueInfo &getValueInfo(Value *) const; + Function &F; + DominatorTree &DT; + AssumptionCache &AC; + OrderedInstructions OI; + // This maps from copy operands to Predicate Info. Note that it does not own + // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos + // vector. + DenseMap<const Value *, const PredicateBase *> PredicateMap; + // This stores info about each operand or comparison result we make copies + // of. The real ValueInfos start at index 1, index 0 is unused so that we can + // more easily detect invalid indexing. + SmallVector<ValueInfo, 32> ValueInfos; + // This gives the index into the ValueInfos array for a given Value. Because + // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell + // whether it returned a valid result. + DenseMap<Value *, unsigned int> ValueInfoNums; + // The set of edges along which we can only handle phi uses, due to critical + // edges. + DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly; + // The set of ssa_copy declarations we created with our custom mangling. + SmallSet<AssertingVH<Function>, 20> CreatedDeclarations; +}; + +// This pass does eager building and then printing of PredicateInfo. It is used +// by +// the tests to be able to build, dump, and verify PredicateInfo. +class PredicateInfoPrinterLegacyPass : public FunctionPass { +public: + PredicateInfoPrinterLegacyPass(); + + static char ID; + bool runOnFunction(Function &) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +/// Printer pass for \c PredicateInfo. +class PredicateInfoPrinterPass + : public PassInfoMixin<PredicateInfoPrinterPass> { + raw_ostream &OS; + +public: + explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +/// Verifier pass for \c PredicateInfo. +struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/PromoteMemToReg.h b/clang-r353983e/include/llvm/Transforms/Utils/PromoteMemToReg.h new file mode 100644 index 00000000..b2b4507b --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/PromoteMemToReg.h @@ -0,0 +1,45 @@ +//===- PromoteMemToReg.h - Promote Allocas to Scalars -----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file exposes an interface to promote alloca instructions to SSA +// registers, by using the SSA construction algorithm. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H +#define LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H + +namespace llvm { + +template <typename T> class ArrayRef; +class AllocaInst; +class DominatorTree; +class AliasSetTracker; +class AssumptionCache; + +/// Return true if this alloca is legal for promotion. +/// +/// This is true if there are only loads, stores, and lifetime markers +/// (transitively) using this alloca. This also enforces that there is only +/// ever one layer of bitcasts or GEPs between the alloca and the lifetime +/// markers. +bool isAllocaPromotable(const AllocaInst *AI); + +/// Promote the specified list of alloca instructions into scalar +/// registers, inserting PHI nodes as appropriate. +/// +/// This function makes use of DominanceFrontier information. This function +/// does not modify the CFG of the function at all. All allocas must be from +/// the same function. +/// +void PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT, + AssumptionCache *AC = nullptr); + +} // End llvm namespace + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdater.h b/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdater.h new file mode 100644 index 00000000..22b2295c --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdater.h @@ -0,0 +1,176 @@ +//===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file declares the SSAUpdater class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringRef.h" +#include <string> + +namespace llvm { + +class BasicBlock; +class Instruction; +class LoadInst; +class PHINode; +template <typename T> class SmallVectorImpl; +template <typename T> class SSAUpdaterTraits; +class Type; +class Use; +class Value; + +/// Helper class for SSA formation on a set of values defined in +/// multiple blocks. +/// +/// This is used when code duplication or another unstructured +/// transformation wants to rewrite a set of uses of one value with uses of a +/// set of values. +class SSAUpdater { + friend class SSAUpdaterTraits<SSAUpdater>; + +private: + /// This keeps track of which value to use on a per-block basis. When we + /// insert PHI nodes, we keep track of them here. + void *AV = nullptr; + + /// ProtoType holds the type of the values being rewritten. + Type *ProtoType = nullptr; + + /// PHI nodes are given a name based on ProtoName. + std::string ProtoName; + + /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to + /// the vector. + SmallVectorImpl<PHINode *> *InsertedPHIs; + +public: + /// If InsertedPHIs is specified, it will be filled + /// in with all PHI Nodes created by rewriting. + explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); + SSAUpdater(const SSAUpdater &) = delete; + SSAUpdater &operator=(const SSAUpdater &) = delete; + ~SSAUpdater(); + + /// Reset this object to get ready for a new set of SSA updates with + /// type 'Ty'. + /// + /// PHI nodes get a name based on 'Name'. + void Initialize(Type *Ty, StringRef Name); + + /// Indicate that a rewritten value is available in the specified block + /// with the specified value. + void AddAvailableValue(BasicBlock *BB, Value *V); + + /// Return true if the SSAUpdater already has a value for the specified + /// block. + bool HasValueForBlock(BasicBlock *BB) const; + + /// Return the value for the specified block if the SSAUpdater has one, + /// otherwise return nullptr. + Value *FindValueForBlock(BasicBlock *BB) const; + + /// Construct SSA form, materializing a value that is live at the end + /// of the specified block. + Value *GetValueAtEndOfBlock(BasicBlock *BB); + + /// Construct SSA form, materializing a value that is live in the + /// middle of the specified block. + /// + /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except + /// in one important case: if there is a definition of the rewritten value + /// after the 'use' in BB. Consider code like this: + /// + /// \code + /// X1 = ... + /// SomeBB: + /// use(X) + /// X2 = ... + /// br Cond, SomeBB, OutBB + /// \endcode + /// + /// In this case, there are two values (X1 and X2) added to the AvailableVals + /// set by the client of the rewriter, and those values are both live out of + /// their respective blocks. However, the use of X happens in the *middle* of + /// a block. Because of this, we need to insert a new PHI node in SomeBB to + /// merge the appropriate values, and this value isn't live out of the block. + Value *GetValueInMiddleOfBlock(BasicBlock *BB); + + /// Rewrite a use of the symbolic value. + /// + /// This handles PHI nodes, which use their value in the corresponding + /// predecessor. Note that this will not work if the use is supposed to be + /// rewritten to a value defined in the same block as the use, but above it. + /// Any 'AddAvailableValue's added for the use's block will be considered to + /// be below it. + void RewriteUse(Use &U); + + /// Rewrite a use like \c RewriteUse but handling in-block definitions. + /// + /// This version of the method can rewrite uses in the same block as + /// a definition, because it assumes that all uses of a value are below any + /// inserted values. + void RewriteUseAfterInsertions(Use &U); + +private: + Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); +}; + +/// Helper class for promoting a collection of loads and stores into SSA +/// Form using the SSAUpdater. +/// +/// This handles complexities that SSAUpdater doesn't, such as multiple loads +/// and stores in one block. +/// +/// Clients of this class are expected to subclass this and implement the +/// virtual methods. +class LoadAndStorePromoter { +protected: + SSAUpdater &SSA; + +public: + LoadAndStorePromoter(ArrayRef<const Instruction *> Insts, + SSAUpdater &S, StringRef Name = StringRef()); + virtual ~LoadAndStorePromoter() = default; + + /// This does the promotion. + /// + /// Insts is a list of loads and stores to promote, and Name is the basename + /// for the PHIs to insert. After this is complete, the loads and stores are + /// removed from the code. + void run(const SmallVectorImpl<Instruction *> &Insts); + + /// Return true if the specified instruction is in the Inst list. + /// + /// The Insts list is the one passed into the constructor. Clients should + /// implement this with a more efficient version if possible. + virtual bool isInstInList(Instruction *I, + const SmallVectorImpl<Instruction *> &Insts) const; + + /// This hook is invoked after all the stores are found and inserted as + /// available values. + virtual void doExtraRewritesBeforeFinalDeletion() {} + + /// Clients can choose to implement this to get notified right before + /// a load is RAUW'd another value. + virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {} + + /// Called before each instruction is deleted. + virtual void instructionDeleted(Instruction *I) const {} + + /// Called to update debug info associated with the instruction. + virtual void updateDebugInfo(Instruction *I) const {} +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdaterBulk.h b/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdaterBulk.h new file mode 100644 index 00000000..5d17d6f3 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdaterBulk.h @@ -0,0 +1,91 @@ +//===- SSAUpdaterBulk.h - Unstructured SSA Update Tool ----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file declares the SSAUpdaterBulk class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/IR/PredIteratorCache.h" + +namespace llvm { + +class BasicBlock; +class PHINode; +template <typename T> class SmallVectorImpl; +class Type; +class Use; +class Value; +class DominatorTree; + +/// Helper class for SSA formation on a set of values defined in multiple +/// blocks. +/// +/// This is used when code duplication or another unstructured transformation +/// wants to rewrite a set of uses of one value with uses of a set of values. +/// The update is done only when RewriteAllUses is called, all other methods are +/// used for book-keeping. That helps to share some common computations between +/// updates of different uses (which is not the case when traditional SSAUpdater +/// is used). +class SSAUpdaterBulk { + struct RewriteInfo { + DenseMap<BasicBlock *, Value *> Defines; + SmallVector<Use *, 4> Uses; + StringRef Name; + Type *Ty; + RewriteInfo(){}; + RewriteInfo(StringRef &N, Type *T) : Name(N), Ty(T){}; + }; + SmallVector<RewriteInfo, 4> Rewrites; + + PredIteratorCache PredCache; + + Value *computeValueAt(BasicBlock *BB, RewriteInfo &R, DominatorTree *DT); + +public: + explicit SSAUpdaterBulk(){}; + SSAUpdaterBulk(const SSAUpdaterBulk &) = delete; + SSAUpdaterBulk &operator=(const SSAUpdaterBulk &) = delete; + ~SSAUpdaterBulk(){}; + + /// Add a new variable to the SSA rewriter. This needs to be called before + /// AddAvailableValue or AddUse calls. The return value is the variable ID, + /// which needs to be passed to AddAvailableValue and AddUse. + unsigned AddVariable(StringRef Name, Type *Ty); + + /// Indicate that a rewritten value is available in the specified block with + /// the specified value. + void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V); + + /// Record a use of the symbolic value. This use will be updated with a + /// rewritten value when RewriteAllUses is called. + void AddUse(unsigned Var, Use *U); + + /// Return true if the SSAUpdater already has a value for the specified + /// variable in the specified block. + bool HasValueForBlock(unsigned Var, BasicBlock *BB); + + /// Perform all the necessary updates, including new PHI-nodes insertion and + /// the requested uses update. + /// + /// The function requires dominator tree DT, which is used for computing + /// locations for new phi-nodes insertions. If a nonnull pointer to a vector + /// InsertedPHIs is passed, all the new phi-nodes will be added to this + /// vector. + void RewriteAllUses(DominatorTree *DT, + SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdaterImpl.h new file mode 100644 index 00000000..ee06893c --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -0,0 +1,467 @@ +//===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file provides a template that implements the core algorithm for the +// SSAUpdater and MachineSSAUpdater. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +#define DEBUG_TYPE "ssaupdater" + +namespace llvm { + +template<typename T> class SSAUpdaterTraits; + +template<typename UpdaterT> +class SSAUpdaterImpl { +private: + UpdaterT *Updater; + + using Traits = SSAUpdaterTraits<UpdaterT>; + using BlkT = typename Traits::BlkT; + using ValT = typename Traits::ValT; + using PhiT = typename Traits::PhiT; + + /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl. + /// The predecessors of each block are cached here since pred_iterator is + /// slow and we need to iterate over the blocks at least a few times. + class BBInfo { + public: + // Back-pointer to the corresponding block. + BlkT *BB; + + // Value to use in this block. + ValT AvailableVal; + + // Block that defines the available value. + BBInfo *DefBB; + + // Postorder number. + int BlkNum = 0; + + // Immediate dominator. + BBInfo *IDom = nullptr; + + // Number of predecessor blocks. + unsigned NumPreds = 0; + + // Array[NumPreds] of predecessor blocks. + BBInfo **Preds = nullptr; + + // Marker for existing PHIs that match. + PhiT *PHITag = nullptr; + + BBInfo(BlkT *ThisBB, ValT V) + : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {} + }; + + using AvailableValsTy = DenseMap<BlkT *, ValT>; + + AvailableValsTy *AvailableVals; + + SmallVectorImpl<PhiT *> *InsertedPHIs; + + using BlockListTy = SmallVectorImpl<BBInfo *>; + using BBMapTy = DenseMap<BlkT *, BBInfo *>; + + BBMapTy BBMap; + BumpPtrAllocator Allocator; + +public: + explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, + SmallVectorImpl<PhiT *> *Ins) : + Updater(U), AvailableVals(A), InsertedPHIs(Ins) {} + + /// GetValue - Check to see if AvailableVals has an entry for the specified + /// BB and if so, return it. If not, construct SSA form by first + /// calculating the required placement of PHIs and then inserting new PHIs + /// where needed. + ValT GetValue(BlkT *BB) { + SmallVector<BBInfo *, 100> BlockList; + BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList); + + // Special case: bail out if BB is unreachable. + if (BlockList.size() == 0) { + ValT V = Traits::GetUndefVal(BB, Updater); + (*AvailableVals)[BB] = V; + return V; + } + + FindDominators(&BlockList, PseudoEntry); + FindPHIPlacement(&BlockList); + FindAvailableVals(&BlockList); + + return BBMap[BB]->DefBB->AvailableVal; + } + + /// BuildBlockList - Starting from the specified basic block, traverse back + /// through its predecessors until reaching blocks with known values. + /// Create BBInfo structures for the blocks and append them to the block + /// list. + BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) { + SmallVector<BBInfo *, 10> RootList; + SmallVector<BBInfo *, 64> WorkList; + + BBInfo *Info = new (Allocator) BBInfo(BB, 0); + BBMap[BB] = Info; + WorkList.push_back(Info); + + // Search backward from BB, creating BBInfos along the way and stopping + // when reaching blocks that define the value. Record those defining + // blocks on the RootList. + SmallVector<BlkT *, 10> Preds; + while (!WorkList.empty()) { + Info = WorkList.pop_back_val(); + Preds.clear(); + Traits::FindPredecessorBlocks(Info->BB, &Preds); + Info->NumPreds = Preds.size(); + if (Info->NumPreds == 0) + Info->Preds = nullptr; + else + Info->Preds = static_cast<BBInfo **>(Allocator.Allocate( + Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *))); + + for (unsigned p = 0; p != Info->NumPreds; ++p) { + BlkT *Pred = Preds[p]; + // Check if BBMap already has a BBInfo for the predecessor block. + typename BBMapTy::value_type &BBMapBucket = + BBMap.FindAndConstruct(Pred); + if (BBMapBucket.second) { + Info->Preds[p] = BBMapBucket.second; + continue; + } + + // Create a new BBInfo for the predecessor. + ValT PredVal = AvailableVals->lookup(Pred); + BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal); + BBMapBucket.second = PredInfo; + Info->Preds[p] = PredInfo; + + if (PredInfo->AvailableVal) { + RootList.push_back(PredInfo); + continue; + } + WorkList.push_back(PredInfo); + } + } + + // Now that we know what blocks are backwards-reachable from the starting + // block, do a forward depth-first traversal to assign postorder numbers + // to those blocks. + BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0); + unsigned BlkNum = 1; + + // Initialize the worklist with the roots from the backward traversal. + while (!RootList.empty()) { + Info = RootList.pop_back_val(); + Info->IDom = PseudoEntry; + Info->BlkNum = -1; + WorkList.push_back(Info); + } + + while (!WorkList.empty()) { + Info = WorkList.back(); + + if (Info->BlkNum == -2) { + // All the successors have been handled; assign the postorder number. + Info->BlkNum = BlkNum++; + // If not a root, put it on the BlockList. + if (!Info->AvailableVal) + BlockList->push_back(Info); + WorkList.pop_back(); + continue; + } + + // Leave this entry on the worklist, but set its BlkNum to mark that its + // successors have been put on the worklist. When it returns to the top + // the list, after handling its successors, it will be assigned a + // number. + Info->BlkNum = -2; + + // Add unvisited successors to the work list. + for (typename Traits::BlkSucc_iterator SI = + Traits::BlkSucc_begin(Info->BB), + E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) { + BBInfo *SuccInfo = BBMap[*SI]; + if (!SuccInfo || SuccInfo->BlkNum) + continue; + SuccInfo->BlkNum = -1; + WorkList.push_back(SuccInfo); + } + } + PseudoEntry->BlkNum = BlkNum; + return PseudoEntry; + } + + /// IntersectDominators - This is the dataflow lattice "meet" operation for + /// finding dominators. Given two basic blocks, it walks up the dominator + /// tree until it finds a common dominator of both. It uses the postorder + /// number of the blocks to determine how to do that. + BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) { + while (Blk1 != Blk2) { + while (Blk1->BlkNum < Blk2->BlkNum) { + Blk1 = Blk1->IDom; + if (!Blk1) + return Blk2; + } + while (Blk2->BlkNum < Blk1->BlkNum) { + Blk2 = Blk2->IDom; + if (!Blk2) + return Blk1; + } + } + return Blk1; + } + + /// FindDominators - Calculate the dominator tree for the subset of the CFG + /// corresponding to the basic blocks on the BlockList. This uses the + /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey + /// and Kennedy, published in Software--Practice and Experience, 2001, + /// 4:1-10. Because the CFG subset does not include any edges leading into + /// blocks that define the value, the results are not the usual dominator + /// tree. The CFG subset has a single pseudo-entry node with edges to a set + /// of root nodes for blocks that define the value. The dominators for this + /// subset CFG are not the standard dominators but they are adequate for + /// placing PHIs within the subset CFG. + void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) { + bool Changed; + do { + Changed = false; + // Iterate over the list in reverse order, i.e., forward on CFG edges. + for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), + E = BlockList->rend(); I != E; ++I) { + BBInfo *Info = *I; + BBInfo *NewIDom = nullptr; + + // Iterate through the block's predecessors. + for (unsigned p = 0; p != Info->NumPreds; ++p) { + BBInfo *Pred = Info->Preds[p]; + + // Treat an unreachable predecessor as a definition with 'undef'. + if (Pred->BlkNum == 0) { + Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater); + (*AvailableVals)[Pred->BB] = Pred->AvailableVal; + Pred->DefBB = Pred; + Pred->BlkNum = PseudoEntry->BlkNum; + PseudoEntry->BlkNum++; + } + + if (!NewIDom) + NewIDom = Pred; + else + NewIDom = IntersectDominators(NewIDom, Pred); + } + + // Check if the IDom value has changed. + if (NewIDom && NewIDom != Info->IDom) { + Info->IDom = NewIDom; + Changed = true; + } + } + } while (Changed); + } + + /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for + /// any blocks containing definitions of the value. If one is found, then + /// the successor of Pred is in the dominance frontier for the definition, + /// and this function returns true. + bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) { + for (; Pred != IDom; Pred = Pred->IDom) { + if (Pred->DefBB == Pred) + return true; + } + return false; + } + + /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers + /// of the known definitions. Iteratively add PHIs in the dom frontiers + /// until nothing changes. Along the way, keep track of the nearest + /// dominating definitions for non-PHI blocks. + void FindPHIPlacement(BlockListTy *BlockList) { + bool Changed; + do { + Changed = false; + // Iterate over the list in reverse order, i.e., forward on CFG edges. + for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), + E = BlockList->rend(); I != E; ++I) { + BBInfo *Info = *I; + + // If this block already needs a PHI, there is nothing to do here. + if (Info->DefBB == Info) + continue; + + // Default to use the same def as the immediate dominator. + BBInfo *NewDefBB = Info->IDom->DefBB; + for (unsigned p = 0; p != Info->NumPreds; ++p) { + if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) { + // Need a PHI here. + NewDefBB = Info; + break; + } + } + + // Check if anything changed. + if (NewDefBB != Info->DefBB) { + Info->DefBB = NewDefBB; + Changed = true; + } + } + } while (Changed); + } + + /// FindAvailableVal - If this block requires a PHI, first check if an + /// existing PHI matches the PHI placement and reaching definitions computed + /// earlier, and if not, create a new PHI. Visit all the block's + /// predecessors to calculate the available value for each one and fill in + /// the incoming values for a new PHI. + void FindAvailableVals(BlockListTy *BlockList) { + // Go through the worklist in forward order (i.e., backward through the CFG) + // and check if existing PHIs can be used. If not, create empty PHIs where + // they are needed. + for (typename BlockListTy::iterator I = BlockList->begin(), + E = BlockList->end(); I != E; ++I) { + BBInfo *Info = *I; + // Check if there needs to be a PHI in BB. + if (Info->DefBB != Info) + continue; + + // Look for an existing PHI. + FindExistingPHI(Info->BB, BlockList); + if (Info->AvailableVal) + continue; + + ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater); + Info->AvailableVal = PHI; + (*AvailableVals)[Info->BB] = PHI; + } + + // Now go back through the worklist in reverse order to fill in the + // arguments for any new PHIs added in the forward traversal. + for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), + E = BlockList->rend(); I != E; ++I) { + BBInfo *Info = *I; + + if (Info->DefBB != Info) { + // Record the available value to speed up subsequent uses of this + // SSAUpdater for the same value. + (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal; + continue; + } + + // Check if this block contains a newly added PHI. + PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater); + if (!PHI) + continue; + + // Iterate through the block's predecessors. + for (unsigned p = 0; p != Info->NumPreds; ++p) { + BBInfo *PredInfo = Info->Preds[p]; + BlkT *Pred = PredInfo->BB; + // Skip to the nearest preceding definition. + if (PredInfo->DefBB != PredInfo) + PredInfo = PredInfo->DefBB; + Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred); + } + + LLVM_DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n"); + + // If the client wants to know about all new instructions, tell it. + if (InsertedPHIs) InsertedPHIs->push_back(PHI); + } + } + + /// FindExistingPHI - Look through the PHI nodes in a block to see if any of + /// them match what is needed. + void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) { + for (auto &SomePHI : BB->phis()) { + if (CheckIfPHIMatches(&SomePHI)) { + RecordMatchingPHIs(BlockList); + break; + } + // Match failed: clear all the PHITag values. + for (typename BlockListTy::iterator I = BlockList->begin(), + E = BlockList->end(); I != E; ++I) + (*I)->PHITag = nullptr; + } + } + + /// CheckIfPHIMatches - Check if a PHI node matches the placement and values + /// in the BBMap. + bool CheckIfPHIMatches(PhiT *PHI) { + SmallVector<PhiT *, 20> WorkList; + WorkList.push_back(PHI); + + // Mark that the block containing this PHI has been visited. + BBMap[PHI->getParent()]->PHITag = PHI; + + while (!WorkList.empty()) { + PHI = WorkList.pop_back_val(); + + // Iterate through the PHI's incoming values. + for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI), + E = Traits::PHI_end(PHI); I != E; ++I) { + ValT IncomingVal = I.getIncomingValue(); + BBInfo *PredInfo = BBMap[I.getIncomingBlock()]; + // Skip to the nearest preceding definition. + if (PredInfo->DefBB != PredInfo) + PredInfo = PredInfo->DefBB; + + // Check if it matches the expected value. + if (PredInfo->AvailableVal) { + if (IncomingVal == PredInfo->AvailableVal) + continue; + return false; + } + + // Check if the value is a PHI in the correct block. + PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater); + if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB) + return false; + + // If this block has already been visited, check if this PHI matches. + if (PredInfo->PHITag) { + if (IncomingPHIVal == PredInfo->PHITag) + continue; + return false; + } + PredInfo->PHITag = IncomingPHIVal; + + WorkList.push_back(IncomingPHIVal); + } + } + return true; + } + + /// RecordMatchingPHIs - For each PHI node that matches, record it in both + /// the BBMap and the AvailableVals mapping. + void RecordMatchingPHIs(BlockListTy *BlockList) { + for (typename BlockListTy::iterator I = BlockList->begin(), + E = BlockList->end(); I != E; ++I) + if (PhiT *PHI = (*I)->PHITag) { + BlkT *BB = PHI->getParent(); + ValT PHIVal = Traits::GetPHIValue(PHI); + (*AvailableVals)[BB] = PHIVal; + BBMap[BB]->AvailableVal = PHIVal; + } + } +}; + +} // end namespace llvm + +#undef DEBUG_TYPE // "ssaupdater" + +#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/SanitizerStats.h b/clang-r353983e/include/llvm/Transforms/Utils/SanitizerStats.h new file mode 100644 index 00000000..14e8ae04 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SanitizerStats.h @@ -0,0 +1,55 @@ +//===- SanitizerStats.h - Sanitizer statistics gathering -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// 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/clang-r353983e/include/llvm/Transforms/Utils/SimplifyIndVar.h b/clang-r353983e/include/llvm/Transforms/Utils/SimplifyIndVar.h new file mode 100644 index 00000000..dec73ef0 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -0,0 +1,59 @@ +//===-- llvm/Transforms/Utils/SimplifyIndVar.h - Indvar Utils ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines in interface for induction variable simplification. It does +// not define any actual pass or policy, but provides a single function to +// simplify a loop's induction variables based on ScalarEvolution. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SIMPLIFYINDVAR_H +#define LLVM_TRANSFORMS_UTILS_SIMPLIFYINDVAR_H + +#include "llvm/IR/ValueHandle.h" + +namespace llvm { + +class CastInst; +class DominatorTree; +class Loop; +class LoopInfo; +class PHINode; +class ScalarEvolution; +class SCEVExpander; + +/// Interface for visiting interesting IV users that are recognized but not +/// simplified by this utility. +class IVVisitor { +protected: + const DominatorTree *DT = nullptr; + + virtual void anchor(); + +public: + IVVisitor() = default; + virtual ~IVVisitor() = default; + + const DominatorTree *getDomTree() const { return DT; } + virtual void visitCast(CastInst *Cast) = 0; +}; + +/// simplifyUsersOfIV - Simplify instructions that use this induction variable +/// by using ScalarEvolution to analyze the IV's recurrence. +bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, + LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead, + SCEVExpander &Rewriter, IVVisitor *V = nullptr); + +/// SimplifyLoopIVs - Simplify users of induction variables within this +/// loop. This does not actually change or add IVs. +bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, + LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SIMPLIFYINDVAR_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/clang-r353983e/include/llvm/Transforms/Utils/SimplifyLibCalls.h new file mode 100644 index 00000000..44eef091 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -0,0 +1,204 @@ +//===- SimplifyLibCalls.h - Library call simplifier -------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file exposes an interface to build some C language libcalls for +// optimization passes that need to call the various functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SIMPLIFYLIBCALLS_H +#define LLVM_TRANSFORMS_UTILS_SIMPLIFYLIBCALLS_H + +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/IRBuilder.h" + +namespace llvm { +class StringRef; +class Value; +class CallInst; +class DataLayout; +class Instruction; +class TargetLibraryInfo; +class BasicBlock; +class Function; +class OptimizationRemarkEmitter; + +/// This class implements simplifications for calls to fortified library +/// functions (__st*cpy_chk, __memcpy_chk, __memmove_chk, __memset_chk), to, +/// when possible, replace them with their non-checking counterparts. +/// Other optimizations can also be done, but it's possible to disable them and +/// only simplify needless use of the checking versions (when the object size +/// is unknown) by passing true for OnlyLowerUnknownSize. +class FortifiedLibCallSimplifier { +private: + const TargetLibraryInfo *TLI; + bool OnlyLowerUnknownSize; + +public: + FortifiedLibCallSimplifier(const TargetLibraryInfo *TLI, + bool OnlyLowerUnknownSize = false); + + /// Take the given call instruction and return a more + /// optimal value to replace the instruction with or 0 if a more + /// optimal form can't be found. + /// The call must not be an indirect call. + Value *optimizeCall(CallInst *CI); + +private: + Value *optimizeMemCpyChk(CallInst *CI, IRBuilder<> &B); + Value *optimizeMemMoveChk(CallInst *CI, IRBuilder<> &B); + Value *optimizeMemSetChk(CallInst *CI, IRBuilder<> &B); + + // Str/Stp cpy are similar enough to be handled in the same functions. + Value *optimizeStrpCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func); + Value *optimizeStrpNCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func); + + /// Checks whether the call \p CI to a fortified libcall is foldable + /// to the non-fortified version. + bool isFortifiedCallFoldable(CallInst *CI, unsigned ObjSizeOp, + unsigned SizeOp, bool isString); +}; + +/// LibCallSimplifier - This class implements a collection of optimizations +/// that replace well formed calls to library functions with a more optimal +/// form. For example, replacing 'printf("Hello!")' with 'puts("Hello!")'. +class LibCallSimplifier { +private: + FortifiedLibCallSimplifier FortifiedSimplifier; + const DataLayout &DL; + const TargetLibraryInfo *TLI; + OptimizationRemarkEmitter &ORE; + bool UnsafeFPShrink; + function_ref<void(Instruction *, Value *)> Replacer; + function_ref<void(Instruction *)> Eraser; + + /// Internal wrapper for RAUW that is the default implementation. + /// + /// Other users may provide an alternate function with this signature instead + /// of this one. + static void replaceAllUsesWithDefault(Instruction *I, Value *With) { + I->replaceAllUsesWith(With); + } + + /// Internal wrapper for eraseFromParent that is the default implementation. + static void eraseFromParentDefault(Instruction *I) { I->eraseFromParent(); } + + /// Replace an instruction's uses with a value using our replacer. + void replaceAllUsesWith(Instruction *I, Value *With); + + /// Erase an instruction from its parent with our eraser. + void eraseFromParent(Instruction *I); + + Value *foldMallocMemset(CallInst *Memset, IRBuilder<> &B); + +public: + LibCallSimplifier( + const DataLayout &DL, const TargetLibraryInfo *TLI, + OptimizationRemarkEmitter &ORE, + function_ref<void(Instruction *, Value *)> Replacer = + &replaceAllUsesWithDefault, + function_ref<void(Instruction *)> Eraser = &eraseFromParentDefault); + + /// optimizeCall - Take the given call instruction and return a more + /// optimal value to replace the instruction with or 0 if a more + /// optimal form can't be found. Note that the returned value may + /// be equal to the instruction being optimized. In this case all + /// other instructions that use the given instruction were modified + /// and the given instruction is dead. + /// The call must not be an indirect call. + Value *optimizeCall(CallInst *CI); + +private: + // String and Memory Library Call Optimizations + Value *optimizeStrCat(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrNCat(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrChr(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrRChr(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrCmp(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrNCmp(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrCpy(CallInst *CI, IRBuilder<> &B); + Value *optimizeStpCpy(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrNCpy(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrLen(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrPBrk(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrTo(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrSpn(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrCSpn(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrStr(CallInst *CI, IRBuilder<> &B); + Value *optimizeMemChr(CallInst *CI, IRBuilder<> &B); + Value *optimizeMemCmp(CallInst *CI, IRBuilder<> &B); + Value *optimizeMemCpy(CallInst *CI, IRBuilder<> &B); + Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B); + Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B); + Value *optimizeRealloc(CallInst *CI, IRBuilder<> &B); + Value *optimizeWcslen(CallInst *CI, IRBuilder<> &B); + // Wrapper for all String/Memory Library Call Optimizations + Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B); + + // Math Library Optimizations + Value *optimizeCAbs(CallInst *CI, IRBuilder<> &B); + Value *optimizePow(CallInst *CI, IRBuilder<> &B); + Value *replacePowWithExp(CallInst *Pow, IRBuilder<> &B); + Value *replacePowWithSqrt(CallInst *Pow, IRBuilder<> &B); + Value *optimizeExp2(CallInst *CI, IRBuilder<> &B); + Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B); + Value *optimizeLog(CallInst *CI, IRBuilder<> &B); + Value *optimizeSqrt(CallInst *CI, IRBuilder<> &B); + Value *optimizeSinCosPi(CallInst *CI, IRBuilder<> &B); + Value *optimizeTan(CallInst *CI, IRBuilder<> &B); + // Wrapper for all floating point library call optimizations + Value *optimizeFloatingPointLibCall(CallInst *CI, LibFunc Func, + IRBuilder<> &B); + + // Integer Library Call Optimizations + Value *optimizeFFS(CallInst *CI, IRBuilder<> &B); + Value *optimizeFls(CallInst *CI, IRBuilder<> &B); + Value *optimizeAbs(CallInst *CI, IRBuilder<> &B); + Value *optimizeIsDigit(CallInst *CI, IRBuilder<> &B); + Value *optimizeIsAscii(CallInst *CI, IRBuilder<> &B); + Value *optimizeToAscii(CallInst *CI, IRBuilder<> &B); + Value *optimizeAtoi(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrtol(CallInst *CI, IRBuilder<> &B); + + // Formatting and IO Library Call Optimizations + Value *optimizeErrorReporting(CallInst *CI, IRBuilder<> &B, + int StreamArg = -1); + Value *optimizePrintF(CallInst *CI, IRBuilder<> &B); + Value *optimizeSPrintF(CallInst *CI, IRBuilder<> &B); + Value *optimizeSnPrintF(CallInst *CI, IRBuilder<> &B); + Value *optimizeFPrintF(CallInst *CI, IRBuilder<> &B); + Value *optimizeFWrite(CallInst *CI, IRBuilder<> &B); + Value *optimizeFRead(CallInst *CI, IRBuilder<> &B); + Value *optimizeFPuts(CallInst *CI, IRBuilder<> &B); + Value *optimizeFGets(CallInst *CI, IRBuilder<> &B); + Value *optimizeFPutc(CallInst *CI, IRBuilder<> &B); + Value *optimizeFGetc(CallInst *CI, IRBuilder<> &B); + Value *optimizePuts(CallInst *CI, IRBuilder<> &B); + + // Helper methods + Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B); + void classifyArgUse(Value *Val, Function *F, bool IsFloat, + SmallVectorImpl<CallInst *> &SinCalls, + SmallVectorImpl<CallInst *> &CosCalls, + SmallVectorImpl<CallInst *> &SinCosCalls); + Value *optimizePrintFString(CallInst *CI, IRBuilder<> &B); + Value *optimizeSPrintFString(CallInst *CI, IRBuilder<> &B); + Value *optimizeSnPrintFString(CallInst *CI, IRBuilder<> &B); + Value *optimizeFPrintFString(CallInst *CI, IRBuilder<> &B); + + /// hasFloatVersion - Checks if there is a float version of the specified + /// function by checking for an existing function with name FuncName + f + bool hasFloatVersion(StringRef FuncName); + + /// Shared code to optimize strlen+wcslen. + Value *optimizeStringLength(CallInst *CI, IRBuilder<> &B, unsigned CharSize); +}; +} // End llvm namespace + +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/SplitModule.h b/clang-r353983e/include/llvm/Transforms/Utils/SplitModule.h new file mode 100644 index 00000000..7839c5d9 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SplitModule.h @@ -0,0 +1,42 @@ +//===- SplitModule.h - Split a module into partitions -----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the function llvm::SplitModule, which splits a module +// into multiple linkable partitions. It can be used to implement parallel code +// generation for link-time optimization. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SPLITMODULE_H +#define LLVM_TRANSFORMS_UTILS_SPLITMODULE_H + +#include "llvm/ADT/STLExtras.h" +#include <memory> + +namespace llvm { + +class Module; + +/// Splits the module M into N linkable partitions. The function ModuleCallback +/// is called N times passing each individual partition as the MPart argument. +/// +/// FIXME: This function does not deal with the somewhat subtle symbol +/// visibility issues around module splitting, including (but not limited to): +/// +/// - Internal symbols should not collide with symbols defined outside the +/// module. +/// - Internal symbols defined in module-level inline asm should be visible to +/// each partition. +void SplitModule( + std::unique_ptr<Module> M, unsigned N, + function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback, + bool PreserveLocals = false); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SPLITMODULE_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/SymbolRewriter.h b/clang-r353983e/include/llvm/Transforms/Utils/SymbolRewriter.h new file mode 100644 index 00000000..ce9dcaf2 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/SymbolRewriter.h @@ -0,0 +1,141 @@ +//===- SymbolRewriter.h - Symbol Rewriting Pass -----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file provides the prototypes and definitions related to the Symbol +// Rewriter pass. +// +// The Symbol Rewriter pass takes a set of rewrite descriptors which define +// transformations for symbol names. These can be either single name to name +// trnsformation or more broad regular expression based transformations. +// +// All the functions are re-written at the IR level. The Symbol Rewriter itself +// is exposed as a module level pass. All symbols at the module level are +// iterated. For any matching symbol, the requested transformation is applied, +// updating references to it as well (a la RAUW). The resulting binary will +// only contain the rewritten symbols. +// +// By performing this operation in the compiler, we are able to catch symbols +// that would otherwise not be possible to catch (e.g. inlined symbols). +// +// This makes it possible to cleanly transform symbols without resorting to +// overly-complex macro tricks and the pre-processor. An example of where this +// is useful is the sanitizers where we would like to intercept a well-defined +// set of functions across the module. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H +#define LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H + +#include "llvm/IR/PassManager.h" +#include <list> +#include <memory> +#include <string> + +namespace llvm { + +class MemoryBuffer; +class Module; +class ModulePass; + +namespace yaml { + +class KeyValueNode; +class MappingNode; +class ScalarNode; +class Stream; + +} // end namespace yaml + +namespace SymbolRewriter { + +/// The basic entity representing a rewrite operation. It serves as the base +/// class for any rewrite descriptor. It has a certain set of specializations +/// which describe a particular rewrite. +/// +/// The RewriteMapParser can be used to parse a mapping file that provides the +/// mapping for rewriting the symbols. The descriptors individually describe +/// whether to rewrite a function, global variable, or global alias. Each of +/// these can be selected either by explicitly providing a name for the ones to +/// be rewritten or providing a (posix compatible) regular expression that will +/// select the symbols to rewrite. This descriptor list is passed to the +/// SymbolRewriter pass. +class RewriteDescriptor { +public: + enum class Type { + Invalid, /// invalid + Function, /// function - descriptor rewrites a function + GlobalVariable, /// global variable - descriptor rewrites a global variable + NamedAlias, /// named alias - descriptor rewrites a global alias + }; + + RewriteDescriptor(const RewriteDescriptor &) = delete; + RewriteDescriptor &operator=(const RewriteDescriptor &) = delete; + virtual ~RewriteDescriptor() = default; + + Type getType() const { return Kind; } + + virtual bool performOnModule(Module &M) = 0; + +protected: + explicit RewriteDescriptor(Type T) : Kind(T) {} + +private: + const Type Kind; +}; + +using RewriteDescriptorList = std::list<std::unique_ptr<RewriteDescriptor>>; + +class RewriteMapParser { +public: + bool parse(const std::string &MapFile, RewriteDescriptorList *Descriptors); + +private: + bool parse(std::unique_ptr<MemoryBuffer> &MapFile, RewriteDescriptorList *DL); + bool parseEntry(yaml::Stream &Stream, yaml::KeyValueNode &Entry, + RewriteDescriptorList *DL); + bool parseRewriteFunctionDescriptor(yaml::Stream &Stream, + yaml::ScalarNode *Key, + yaml::MappingNode *Value, + RewriteDescriptorList *DL); + bool parseRewriteGlobalVariableDescriptor(yaml::Stream &Stream, + yaml::ScalarNode *Key, + yaml::MappingNode *Value, + RewriteDescriptorList *DL); + bool parseRewriteGlobalAliasDescriptor(yaml::Stream &YS, yaml::ScalarNode *K, + yaml::MappingNode *V, + RewriteDescriptorList *DL); +}; + +} // end namespace SymbolRewriter + +ModulePass *createRewriteSymbolsPass(); +ModulePass *createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &); + +class RewriteSymbolPass : public PassInfoMixin<RewriteSymbolPass> { +public: + RewriteSymbolPass() { loadAndParseMapFiles(); } + + RewriteSymbolPass(SymbolRewriter::RewriteDescriptorList &DL) { + Descriptors.splice(Descriptors.begin(), DL); + } + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); + + // Glue for old PM + bool runImpl(Module &M); + +private: + void loadAndParseMapFiles(); + + SymbolRewriter::RewriteDescriptorList Descriptors; +}; + +} // end namespace llvm + +#endif //LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h b/clang-r353983e/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h new file mode 100644 index 00000000..f68534ec --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h @@ -0,0 +1,53 @@ +//===-- UnifyFunctionExitNodes.h - Ensure fn's have one return --*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This pass is used to ensure that functions have at most one return and one +// unwind instruction in them. Additionally, it keeps track of which node is +// the new exit node of the CFG. If there are no return or unwind instructions +// in the function, the getReturnBlock/getUnwindBlock methods will return a null +// pointer. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_UNIFYFUNCTIONEXITNODES_H +#define LLVM_TRANSFORMS_UTILS_UNIFYFUNCTIONEXITNODES_H + +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" + +namespace llvm { + +struct UnifyFunctionExitNodes : public FunctionPass { + BasicBlock *ReturnBlock = nullptr; + BasicBlock *UnwindBlock = nullptr; + BasicBlock *UnreachableBlock; + +public: + static char ID; // Pass identification, replacement for typeid + UnifyFunctionExitNodes() : FunctionPass(ID) { + initializeUnifyFunctionExitNodesPass(*PassRegistry::getPassRegistry()); + } + + // We can preserve non-critical-edgeness when we unify function exit nodes + void getAnalysisUsage(AnalysisUsage &AU) const override; + + // getReturn|Unwind|UnreachableBlock - Return the new single (or nonexistent) + // return, unwind, or unreachable basic blocks in the CFG. + // + BasicBlock *getReturnBlock() const { return ReturnBlock; } + BasicBlock *getUnwindBlock() const { return UnwindBlock; } + BasicBlock *getUnreachableBlock() const { return UnreachableBlock; } + + bool runOnFunction(Function &F) override; +}; + +Pass *createUnifyFunctionExitNodesPass(); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_UNIFYFUNCTIONEXITNODES_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/UnrollLoop.h b/clang-r353983e/include/llvm/Transforms/Utils/UnrollLoop.h new file mode 100644 index 00000000..8f3824e1 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/UnrollLoop.h @@ -0,0 +1,136 @@ +//===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines some loop unrolling utilities. It does not define any +// actual pass or policy, but provides a single function to perform loop +// unrolling. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H +#define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Transforms/Utils/ValueMapper.h" + +namespace llvm { + +class AssumptionCache; +class BasicBlock; +class DependenceInfo; +class DominatorTree; +class Loop; +class LoopInfo; +class MDNode; +class OptimizationRemarkEmitter; +class ScalarEvolution; + +using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; + +/// @{ +/// Metadata attribute names +const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all"; +const char *const LLVMLoopUnrollFollowupUnrolled = + "llvm.loop.unroll.followup_unrolled"; +const char *const LLVMLoopUnrollFollowupRemainder = + "llvm.loop.unroll.followup_remainder"; +/// @} + +const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB, + BasicBlock *ClonedBB, LoopInfo *LI, + NewLoopsMap &NewLoops); + +/// Represents the result of a \c UnrollLoop invocation. +enum class LoopUnrollResult { + /// The loop was not modified. + Unmodified, + + /// The loop was partially unrolled -- we still have a loop, but with a + /// smaller trip count. We may also have emitted epilogue loop if the loop + /// had a non-constant trip count. + PartiallyUnrolled, + + /// The loop was fully unrolled into straight-line code. We no longer have + /// any back-edges. + FullyUnrolled +}; + +LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, + bool Force, bool AllowRuntime, + bool AllowExpensiveTripCount, bool PreserveCondBr, + bool PreserveOnlyFirst, unsigned TripMultiple, + unsigned PeelCount, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, + OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, + Loop **RemainderLoop = nullptr); + +bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, + bool AllowExpensiveTripCount, + bool UseEpilogRemainder, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, + bool PreserveLCSSA, + Loop **ResultLoop = nullptr); + +void computePeelCount(Loop *L, unsigned LoopSize, + TargetTransformInfo::UnrollingPreferences &UP, + unsigned &TripCount, ScalarEvolution &SE); + +bool canPeel(Loop *L); + +bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); + +LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, + unsigned TripMultiple, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, + OptimizationRemarkEmitter *ORE, + Loop **EpilogueLoop = nullptr); + +bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, + DependenceInfo &DI); + +bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, + DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, + const SmallPtrSetImpl<const Value *> &EphValues, + OptimizationRemarkEmitter *ORE, unsigned &TripCount, + unsigned MaxTripCount, unsigned &TripMultiple, + unsigned LoopSize, + TargetTransformInfo::UnrollingPreferences &UP, + bool &UseUpperBound); + +BasicBlock *foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT); + +void remapInstruction(Instruction *I, ValueToValueMapTy &VMap); + +void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC); + +MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); + +TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( + Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel, + Optional<unsigned> UserThreshold, Optional<unsigned> UserCount, + Optional<bool> UserAllowPartial, Optional<bool> UserRuntime, + Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling); + +unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, + bool &NotDuplicatable, bool &Convergent, + const TargetTransformInfo &TTI, + const SmallPtrSetImpl<const Value *> &EphValues, + unsigned BEInsns); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H diff --git a/clang-r353983e/include/llvm/Transforms/Utils/VNCoercion.h b/clang-r353983e/include/llvm/Transforms/Utils/VNCoercion.h new file mode 100644 index 00000000..f67b9ed0 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/VNCoercion.h @@ -0,0 +1,107 @@ +//===- VNCoercion.h - Value Numbering Coercion Utilities --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file / This file provides routines used by LLVM's value numbering passes to +/// perform various forms of value extraction from memory when the types are not +/// identical. For example, given +/// +/// store i32 8, i32 *%foo +/// %a = bitcast i32 *%foo to i16 +/// %val = load i16, i16 *%a +/// +/// It possible to extract the value of the load of %a from the store to %foo. +/// These routines know how to tell whether they can do that (the analyze* +/// routines), and can also insert the necessary IR to do it (the get* +/// routines). + +#ifndef LLVM_TRANSFORMS_UTILS_VNCOERCION_H +#define LLVM_TRANSFORMS_UTILS_VNCOERCION_H +#include "llvm/IR/IRBuilder.h" + +namespace llvm { +class Function; +class StoreInst; +class LoadInst; +class MemIntrinsic; +class Instruction; +class Value; +class Type; +class DataLayout; +namespace VNCoercion { +/// Return true if CoerceAvailableValueToLoadType would succeed if it was +/// called. +bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy, + const DataLayout &DL); + +/// If we saw a store of a value to memory, and then a load from a must-aliased +/// pointer of a different type, try to coerce the stored value to the loaded +/// type. LoadedTy is the type of the load we want to replace. IRB is +/// IRBuilder used to insert new instructions. +/// +/// If we can't do it, return null. +Value *coerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy, + IRBuilder<> &IRB, const DataLayout &DL); + +/// This function determines whether a value for the pointer LoadPtr can be +/// extracted from the store at DepSI. +/// +/// On success, it returns the offset into DepSI that extraction would start. +/// On failure, it returns -1. +int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, + StoreInst *DepSI, const DataLayout &DL); + +/// This function determines whether a value for the pointer LoadPtr can be +/// extracted from the load at DepLI. +/// +/// On success, it returns the offset into DepLI that extraction would start. +/// On failure, it returns -1. +int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, + const DataLayout &DL); + +/// This function determines whether a value for the pointer LoadPtr can be +/// extracted from the memory intrinsic at DepMI. +/// +/// On success, it returns the offset into DepMI that extraction would start. +/// On failure, it returns -1. +int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, + MemIntrinsic *DepMI, const DataLayout &DL); + +/// If analyzeLoadFromClobberingStore returned an offset, this function can be +/// used to actually perform the extraction of the bits from the store. It +/// inserts instructions to do so at InsertPt, and returns the extracted value. +Value *getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, + Instruction *InsertPt, const DataLayout &DL); +// This is the same as getStoreValueForLoad, except it performs no insertion +// It only allows constant inputs. +Constant *getConstantStoreValueForLoad(Constant *SrcVal, unsigned Offset, + Type *LoadTy, const DataLayout &DL); + +/// If analyzeLoadFromClobberingLoad returned an offset, this function can be +/// used to actually perform the extraction of the bits from the load, including +/// any necessary load widening. It inserts instructions to do so at InsertPt, +/// and returns the extracted value. +Value *getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy, + Instruction *InsertPt, const DataLayout &DL); +// This is the same as getLoadValueForLoad, except it is given the load value as +// a constant. It returns nullptr if it would require widening the load. +Constant *getConstantLoadValueForLoad(Constant *SrcVal, unsigned Offset, + Type *LoadTy, const DataLayout &DL); + +/// If analyzeLoadFromClobberingMemInst returned an offset, this function can be +/// used to actually perform the extraction of the bits from the memory +/// intrinsic. It inserts instructions to do so at InsertPt, and returns the +/// extracted value. +Value *getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, + Type *LoadTy, Instruction *InsertPt, + const DataLayout &DL); +// This is the same as getStoreValueForLoad, except it performs no insertion. +// It returns nullptr if it cannot produce a constant. +Constant *getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, + Type *LoadTy, const DataLayout &DL); +} +} +#endif diff --git a/clang-r353983e/include/llvm/Transforms/Utils/ValueMapper.h b/clang-r353983e/include/llvm/Transforms/Utils/ValueMapper.h new file mode 100644 index 00000000..1952a210 --- /dev/null +++ b/clang-r353983e/include/llvm/Transforms/Utils/ValueMapper.h @@ -0,0 +1,280 @@ +//===- ValueMapper.h - Remapping for constants and metadata -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the MapValue interface which is used by various parts of +// the Transforms/Utils library to implement cloning and linking facilities. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_VALUEMAPPER_H +#define LLVM_TRANSFORMS_UTILS_VALUEMAPPER_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/IR/ValueMap.h" + +namespace llvm { + +class Constant; +class Function; +class GlobalAlias; +class GlobalVariable; +class Instruction; +class MDNode; +class Metadata; +class Type; +class Value; + +using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>; + +/// 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() = default; + + /// 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(const ValueMaterializer &) = default; + ValueMaterializer &operator=(const ValueMaterializer &) = default; + ~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, +}; + +inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { + return RemapFlags(unsigned(LHS) | unsigned(RHS)); +} + +/// 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 different 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; + +public: + ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags = RF_None, + ValueMapTypeRemapper *TypeMapper = nullptr, + ValueMaterializer *Materializer = nullptr); + ValueMapper(ValueMapper &&) = delete; + ValueMapper(const ValueMapper &) = delete; + ValueMapper &operator=(ValueMapper &&) = delete; + ValueMapper &operator=(const ValueMapper &) = delete; + ~ValueMapper(); + + /// Register an alternate mapping context. + /// + /// 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 namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_VALUEMAPPER_H |