diff options
Diffstat (limited to 'include/llvm/Transforms/Utils')
23 files changed, 517 insertions, 276 deletions
diff --git a/include/llvm/Transforms/Utils/AddDiscriminators.h b/include/llvm/Transforms/Utils/AddDiscriminators.h index a877583009922..4dad06e6c1254 100644 --- a/include/llvm/Transforms/Utils/AddDiscriminators.h +++ b/include/llvm/Transforms/Utils/AddDiscriminators.h @@ -1,4 +1,4 @@ -//===- AddDiscriminators.h -------------------------------------*- C++ -*-===// +//===- AddDiscriminators.h --------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -20,10 +20,13 @@ 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/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 85bb053135a65..74f75509f550e 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -1,4 +1,4 @@ -//===-- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils ----*- C++ -*-===// +//===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -25,13 +25,17 @@ namespace llvm { -class MemoryDependenceResults; +class BlockFrequencyInfo; +class BranchProbabilityInfo; class DominatorTree; -class LoopInfo; +class Function; class Instruction; +class LoopInfo; class MDNode; +class MemoryDependenceResults; class ReturnInst; class TargetLibraryInfo; +class Value; /// Delete the specified block, which must have no predecessors. void DeleteDeadBlock(BasicBlock *BB); @@ -118,7 +122,6 @@ struct CriticalEdgeSplittingOptions { /// 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(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options = CriticalEdgeSplittingOptions()); @@ -194,7 +197,6 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, /// 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, @@ -212,7 +214,6 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, /// 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, @@ -284,6 +285,29 @@ void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 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/include/llvm/Transforms/Utils/BypassSlowDivision.h b/include/llvm/Transforms/Utils/BypassSlowDivision.h index af0d60b2625f7..6eca5ed2154e2 100644 --- a/include/llvm/Transforms/Utils/BypassSlowDivision.h +++ b/include/llvm/Transforms/Utils/BypassSlowDivision.h @@ -1,4 +1,4 @@ -//===- llvm/Transforms/Utils/BypassSlowDivision.h --------------*- C++ -*-===// +//===- llvm/Transforms/Utils/BypassSlowDivision.h ---------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -19,10 +19,44 @@ #define LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H #include "llvm/ADT/DenseMap.h" -#include "llvm/IR/Function.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. /// @@ -31,6 +65,6 @@ namespace llvm { bool bypassSlowDivision( BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H diff --git a/include/llvm/Transforms/Utils/CallPromotionUtils.h b/include/llvm/Transforms/Utils/CallPromotionUtils.h new file mode 100644 index 0000000000000..e0bf85781d811 --- /dev/null +++ b/include/llvm/Transforms/Utils/CallPromotionUtils.h @@ -0,0 +1,44 @@ +//===- CallPromotionUtils.h - Utilities for call promotion ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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 conditionally call \p Callee. +/// +/// This function creates an if-then-else structure at the location of the call +/// site. The original call site is promoted and moved into the "then" block. A +/// clone of the indirect call site is placed in the "else" 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/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h index 2a8b89d862821..178bae76cef64 100644 --- a/include/llvm/Transforms/Utils/Cloning.h +++ b/include/llvm/Transforms/Utils/Cloning.h @@ -227,12 +227,18 @@ public: /// *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. bool InlineFunction(CallInst *C, InlineFunctionInfo &IFI, AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); bool InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI, AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI, - AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); + AAResults *CalleeAAR = nullptr, bool InsertLifetime = true, + Function *ForwardVarArgsTo = nullptr); /// \brief Clones a loop \p OrigLoop. Returns the loop and the blocks in \p /// Blocks. diff --git a/include/llvm/Transforms/Utils/CmpInstAnalysis.h b/include/llvm/Transforms/Utils/CmpInstAnalysis.h deleted file mode 100644 index 5ec3888d4538c..0000000000000 --- a/include/llvm/Transforms/Utils/CmpInstAnalysis.h +++ /dev/null @@ -1,70 +0,0 @@ -//===-- CmpInstAnalysis.h - Utils to help fold compare insts ----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file holds routines to help analyse compare instructions -// and fold them into constants or other compare instructions -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H -#define LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H - -#include "llvm/IR/InstrTypes.h" - -namespace llvm { - class ICmpInst; - class Value; - - /// Encode a icmp predicate into a three bit mask. These bits are carefully - /// arranged to allow folding of expressions such as: - /// - /// (A < B) | (A > B) --> (A != B) - /// - /// Note that this is only valid if the first and second predicates have the - /// same sign. It is illegal to do: (A u< B) | (A s> B) - /// - /// Three bits are used to represent the condition, as follows: - /// 0 A > B - /// 1 A == B - /// 2 A < B - /// - /// <=> Value Definition - /// 000 0 Always false - /// 001 1 A > B - /// 010 2 A == B - /// 011 3 A >= B - /// 100 4 A < B - /// 101 5 A != B - /// 110 6 A <= B - /// 111 7 Always true - /// - unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred = false); - - /// This is the complement of getICmpCode, which turns an opcode and two - /// operands into either a constant true or false, or the predicate for a new - /// ICmp instruction. The sign is passed in to determine which kind of - /// predicate to use in the new icmp instruction. - /// Non-NULL return value will be a true or false constant. - /// NULL return means a new ICmp is needed. The predicate for which is output - /// in NewICmpPred. - Value *getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, - CmpInst::Predicate &NewICmpPred); - - /// Return true if both predicates match sign or if at least one of them is an - /// equality comparison (which is signless). - bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2); - - /// Decompose an icmp into the form ((X & Y) pred Z) if possible. The returned - /// predicate is either == or !=. Returns false if decomposition fails. - bool decomposeBitTestICmp(const ICmpInst *I, CmpInst::Predicate &Pred, - Value *&X, Value *&Y, Value *&Z); - -} // end namespace llvm - -#endif diff --git a/include/llvm/Transforms/Utils/CodeExtractor.h b/include/llvm/Transforms/Utils/CodeExtractor.h index 682b353ab5ae8..63d34511102dc 100644 --- a/include/llvm/Transforms/Utils/CodeExtractor.h +++ b/include/llvm/Transforms/Utils/CodeExtractor.h @@ -1,4 +1,4 @@ -//===-- Transform/Utils/CodeExtractor.h - Code extraction util --*- C++ -*-===// +//===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,22 +15,24 @@ #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 <limits> namespace llvm { -template <typename T> class ArrayRef; - class BasicBlock; - class BlockFrequency; - class BlockFrequencyInfo; - class BranchProbabilityInfo; - class DominatorTree; - class Function; - class Instruction; - class Loop; - class Module; - class RegionNode; - class Type; - class Value; + +class BasicBlock; +class BlockFrequency; +class BlockFrequencyInfo; +class BranchProbabilityInfo; +class DominatorTree; +class Function; +class Instruction; +class Loop; +class Module; +class Type; +class Value; /// \brief Utility class for extracting code into a new function. /// @@ -46,7 +48,7 @@ template <typename T> class ArrayRef; /// 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 { - typedef SetVector<Value *> ValueSet; + using ValueSet = SetVector<Value *>; // Various bits of state computed on construction. DominatorTree *const DT; @@ -54,27 +56,27 @@ template <typename T> class ArrayRef; BlockFrequencyInfo *BFI; BranchProbabilityInfo *BPI; + // If true, varargs functions can be extracted. + bool AllowVarArgs; + // Bits of intermediate state computed at various phases of extraction. SetVector<BasicBlock *> Blocks; - unsigned NumExitBlocks; + unsigned NumExitBlocks = std::numeric_limits<unsigned>::max(); Type *RetTy; public: - - /// \brief Check to see if a block is valid for extraction. - /// - /// Blocks containing EHPads, allocas, invokes, or vastarts are not valid. - static bool isBlockValidForExtraction(const BasicBlock &BB); - /// \brief 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. + /// 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. CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, - BranchProbabilityInfo *BPI = nullptr); + BranchProbabilityInfo *BPI = nullptr, + bool AllowVarArgs = false); /// \brief Create a code extractor for a loop body. /// @@ -84,6 +86,14 @@ template <typename T> class ArrayRef; BlockFrequencyInfo *BFI = nullptr, BranchProbabilityInfo *BPI = nullptr); + /// \brief Check to see if a block is valid for extraction. + /// + /// Blocks containing EHPads, allocas and invokes are not valid. If + /// AllowVarArgs is true, blocks with vastart can be extracted. This is + /// safe, if all vararg handling code is extracted, including vastart. + static bool isBlockValidForExtraction(const BasicBlock &BB, + bool AllowVarArgs); + /// \brief Perform the extraction, returning the new function. /// /// Returns zero when called on a CodeExtractor instance where isEligible @@ -112,6 +122,7 @@ template <typename T> class ArrayRef; /// /// 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. /// @@ -155,6 +166,7 @@ template <typename T> class ArrayRef; ValueSet &inputs, ValueSet &outputs); }; -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H diff --git a/include/llvm/Transforms/Utils/EntryExitInstrumenter.h b/include/llvm/Transforms/Utils/EntryExitInstrumenter.h new file mode 100644 index 0000000000000..f50c5c9220816 --- /dev/null +++ b/include/llvm/Transforms/Utils/EntryExitInstrumenter.h @@ -0,0 +1,36 @@ +//===- EntryExitInstrumenter.h - Function Entry/Exit Instrumentation ------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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/include/llvm/Transforms/Utils/Evaluator.h b/include/llvm/Transforms/Utils/Evaluator.h index 07f12f41b3bcd..0e987b93177aa 100644 --- a/include/llvm/Transforms/Utils/Evaluator.h +++ b/include/llvm/Transforms/Utils/Evaluator.h @@ -1,4 +1,4 @@ -//===-- Evaluator.h - LLVM IR evaluator -------------------------*- C++ -*-===// +//===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -18,9 +18,10 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Constant.h" #include "llvm/IR/GlobalVariable.h" - +#include "llvm/IR/Value.h" +#include "llvm/Support/Casting.h" +#include <cassert> #include <deque> #include <memory> @@ -114,6 +115,6 @@ private: const TargetLibraryInfo *TLI; }; -} +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H diff --git a/include/llvm/Transforms/Utils/FunctionComparator.h b/include/llvm/Transforms/Utils/FunctionComparator.h index b0f10eafaa95f..7698a068717a9 100644 --- a/include/llvm/Transforms/Utils/FunctionComparator.h +++ b/include/llvm/Transforms/Utils/FunctionComparator.h @@ -15,10 +15,10 @@ #ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H #define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H -#include "llvm/ADT/APFloat.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringRef.h" -#include "llvm/IR/Function.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" @@ -28,7 +28,17 @@ namespace llvm { -class GetElementPtrInst; +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 @@ -43,14 +53,16 @@ class GetElementPtrInst; /// compare those, but this would not work for stripped bitcodes or for those /// few symbols without a name. class GlobalNumberState { - struct Config : ValueMapConfig<GlobalValue*> { + 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). - typedef ValueMap<GlobalValue *, uint64_t, Config> ValueNumberMap; + using ValueNumberMap = ValueMap<GlobalValue *, uint64_t, Config>; ValueNumberMap GlobalNumbers; + // The next unused serial number to assign to a global. uint64_t NextNumber = 0; @@ -66,6 +78,10 @@ public: return MapIter->second; } + void erase(GlobalValue *Global) { + GlobalNumbers.erase(Global); + } + void clear() { GlobalNumbers.clear(); } @@ -83,9 +99,10 @@ public: /// 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. - typedef uint64_t FunctionHash; + using FunctionHash = uint64_t; static FunctionHash functionHash(Function &); protected: diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 30b27616cd982..01db88bc15c2f 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -1,4 +1,4 @@ -//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===// +//===- Local.h - Functions to perform local transformations -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,39 +15,95 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H #define LLVM_TRANSFORMS_UTILS_LOCAL_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/CallSite.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/IRBuilder.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 User; +class AllocaInst; +class AssumptionCache; class BasicBlock; -class Function; class BranchInst; -class Instruction; class CallInst; -class DbgDeclareInst; +class DbgInfoIntrinsic; class DbgValueInst; -class StoreInst; +class DIBuilder; +class Function; +class Instruction; +class LazyValueInfo; class LoadInst; -class Value; +class MDNode; class PHINode; -class AllocaInst; -class AssumptionCache; -class ConstantExpr; -class DataLayout; +class StoreInst; class TargetLibraryInfo; class TargetTransformInfo; -class DIBuilder; -class DominatorTree; -class LazyValueInfo; -template<typename T> class SmallVectorImpl; +/// 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. @@ -133,17 +189,15 @@ bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); /// 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 header that SimplifyCFG should not -/// eliminate. -bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, - SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr, - bool LateSimplifyCFG = false); +/// 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 @@ -185,10 +239,10 @@ unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DominatorTree *DT = nullptr); /// Try to infer an alignment for the specified pointer. -static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, - const Instruction *CxtI = nullptr, - AssumptionCache *AC = nullptr, - const DominatorTree *DT = nullptr) { +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); } @@ -210,7 +264,8 @@ Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, // Build a mask for high order bits. unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth(); - uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth); + uint64_t PtrSizeMask = + std::numeric_limits<uint64_t>::max() >> (64 - IntPtrWidth); gep_type_iterator GTI = gep_type_begin(GEP); for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; @@ -262,46 +317,50 @@ Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, /// /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value -/// that has an associated llvm.dbg.decl intrinsic. -void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, +/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *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.decl intrinsic. -void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, +/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, LoadInst *LI, DIBuilder &Builder); -/// Inserts a llvm.dbg.value intrinsic after a phi of an alloca'd value -/// that has an associated llvm.dbg.decl intrinsic. -void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, +/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated +/// llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, PHINode *LI, DIBuilder &Builder); /// Lowers llvm.dbg.declare intrinsics into appropriate set of /// llvm.dbg.value intrinsics. bool LowerDbgDeclare(Function &F); -/// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any. -DbgDeclareInst *FindAllocaDbgDeclare(Value *V); +/// 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<DbgInfoIntrinsic *> FindDbgAddrUses(Value *V); /// Finds the llvm.dbg.value intrinsics describing a value. void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, 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 (after the optional Deref). Offset can be -/// negative. +/// 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 Deref, int Offset); + 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 (after the optional Deref). Offset can be -/// negative. New llvm.dbg.declare is inserted immediately before AI. +/// 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 before AI. bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, - DIBuilder &Builder, bool Deref, int Offset = 0); + 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 @@ -369,7 +428,6 @@ unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB); - /// Return true if the CallSite CS calls a gc leaf function. /// /// A leaf function is a function that does not safepoint the thread during its @@ -378,7 +436,7 @@ unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, /// /// Most passes can and should ignore this information, and it is only used /// during lowering by the GC infrastructure. -bool callsGCLeafFunction(ImmutableCallSite CS); +bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI); /// Copy a nonnull metadata node to a new load instruction. /// @@ -397,7 +455,7 @@ void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, // Intrinsic pattern matching // -/// Try and match a bswap or bitreverse idiom. +/// 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 @@ -431,6 +489,6 @@ void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, /// value? bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_LOCAL_H diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 94e20b83754e7..7506661365070 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -16,6 +16,7 @@ #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" @@ -305,10 +306,13 @@ public: /// induction, the induction descriptor \p D will contain the data describing /// this induction. If by some other means the caller has a better SCEV /// expression for \p Phi than the one returned by the ScalarEvolution - /// analysis, it can be passed through \p Expr. - static bool isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, - InductionDescriptor &D, - const SCEV *Expr = nullptr); + /// analysis, it can be passed through \p Expr. If the def-use chain + /// associated with the phi includes casts (that we know we can ignore + /// under proper runtime checks), they are passed through \p CastsToIgnore. + static bool + isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, + InductionDescriptor &D, const SCEV *Expr = nullptr, + SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr); /// Returns true if \p Phi is a floating point induction in the loop \p L. /// If \p Phi is an induction, the induction descriptor \p D will contain @@ -330,15 +334,13 @@ public: /// not have the "fast-math" property. Such operation requires a relaxed FP /// mode. bool hasUnsafeAlgebra() { - return InductionBinOp && - !cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra(); + return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast(); } /// Returns induction operator that does not have "fast-math" property /// and requires FP unsafe mode. Instruction *getUnsafeAlgebraInst() { - if (!InductionBinOp || - cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra()) + if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast()) return nullptr; return InductionBinOp; } @@ -349,10 +351,18 @@ public: Instruction::BinaryOpsEnd; } + /// Returns a reference to the type cast instructions in the induction + /// update chain, that are redundant when guarded with a runtime + /// SCEV overflow check. + const SmallVectorImpl<Instruction *> &getCastInsts() const { + return RedundantCasts; + } + private: /// Private constructor - used by \c isInductionPHI. InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step, - BinaryOperator *InductionBinOp = nullptr); + BinaryOperator *InductionBinOp = nullptr, + SmallVectorImpl<Instruction *> *Casts = nullptr); /// Start value. TrackingVH<Value> StartValue; @@ -362,6 +372,9 @@ private: const SCEV *Step = nullptr; // Instruction that advances induction variable. BinaryOperator *InductionBinOp = nullptr; + // Instructions used for type-casts of the induction variable, + // that are redundant when guarded with a runtime SCEV overflow check. + SmallVector<Instruction *, 2> RedundantCasts; }; BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, @@ -423,8 +436,9 @@ bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, /// 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 *, Loop *, AliasSetTracker *, - LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); + TargetLibraryInfo *, TargetTransformInfo *, Loop *, + AliasSetTracker *, LoopSafetyInfo *, + OptimizationRemarkEmitter *ORE); /// \brief Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -438,21 +452,41 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); +/// 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); + /// \brief Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over /// the stores in the loop, looking for stores to Must pointers which are -/// loop invariant. It takes AliasSet, 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(AliasSet &, SmallVectorImpl<BasicBlock *> &, +/// 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 *> &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, 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); + /// \brief Computes safety information for a loop /// checks loop body & header for the possibility of may throw /// exception, it takes LoopSafetyInfo and loop as argument. diff --git a/include/llvm/Transforms/Utils/LowerMemIntrinsics.h b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h index 4554b5cbc6440..2b7d0f67a3245 100644 --- a/include/llvm/Transforms/Utils/LowerMemIntrinsics.h +++ b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h @@ -25,12 +25,6 @@ class MemSetInst; class TargetTransformInfo; class Value; -/// Emit a loop implementing the semantics of llvm.memcpy with the equivalent -/// arguments at \p InsertBefore. -void createMemCpyLoop(Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr, - Value *CopyLen, unsigned SrcAlign, unsigned DestAlign, - bool SrcIsVolatile, bool DstIsVolatile); - /// 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, diff --git a/include/llvm/Transforms/Utils/Mem2Reg.h b/include/llvm/Transforms/Utils/Mem2Reg.h index 1fe186d6c3ad9..407684338a3b7 100644 --- a/include/llvm/Transforms/Utils/Mem2Reg.h +++ b/include/llvm/Transforms/Utils/Mem2Reg.h @@ -15,14 +15,17 @@ #ifndef LLVM_TRANSFORMS_UTILS_MEM2REG_H #define LLVM_TRANSFORMS_UTILS_MEM2REG_H -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" namespace llvm { + +class 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/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h index e9793fe4b6666..4b9bc82938106 100644 --- a/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/include/llvm/Transforms/Utils/ModuleUtils.h @@ -85,7 +85,8 @@ void filterDeadComdatFunctions( Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions); /// \brief Produce a unique identifier for this module by taking the MD5 sum of -/// the names of the module's strong external symbols. +/// 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. diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 8cbcdf47156ea..6cd9f1539b0b3 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -1,4 +1,4 @@ -//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===// +//===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,6 +14,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringRef.h" #include <string> @@ -22,10 +23,9 @@ namespace llvm { class BasicBlock; class Instruction; class LoadInst; -template <typename T> class ArrayRef; +class PHINode; template <typename T> class SmallVectorImpl; template <typename T> class SSAUpdaterTraits; -class PHINode; class Type; class Use; class Value; @@ -42,7 +42,6 @@ class 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. - //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; void *AV = nullptr; /// ProtoType holds the type of the values being rewritten. @@ -53,12 +52,12 @@ private: /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to /// the vector. - SmallVectorImpl<PHINode*> *InsertedPHIs; + 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); + explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); SSAUpdater(const SSAUpdater &) = delete; SSAUpdater &operator=(const SSAUpdater &) = delete; ~SSAUpdater(); @@ -136,7 +135,7 @@ protected: SSAUpdater &SSA; public: - LoadAndStorePromoter(ArrayRef<const Instruction*> Insts, + LoadAndStorePromoter(ArrayRef<const Instruction *> Insts, SSAUpdater &S, StringRef Name = StringRef()); virtual ~LoadAndStorePromoter() = default; @@ -145,32 +144,28 @@ public: /// 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) const; + void run(const SmallVectorImpl<Instruction *> &Insts) const; /// \brief 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; + const SmallVectorImpl<Instruction *> &Insts) const; /// \brief This hook is invoked after all the stores are found and inserted as /// available values. - virtual void doExtraRewritesBeforeFinalDeletion() const { - } + virtual void doExtraRewritesBeforeFinalDeletion() const {} /// \brief 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 { - } + virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {} /// \brief Called before each instruction is deleted. - virtual void instructionDeleted(Instruction *I) const { - } + virtual void instructionDeleted(Instruction *I) const {} /// \brief Called to update debug info associated with the instruction. - virtual void updateDebugInfo(Instruction *I) const { - } + virtual void updateDebugInfo(Instruction *I) const {} }; } // end namespace llvm diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h index 2dd205d8b2af2..b1611d49a456e 100644 --- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -1,4 +1,4 @@ -//===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===// +//===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -17,17 +17,14 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #define DEBUG_TYPE "ssaupdater" namespace llvm { -class CastInst; -class PHINode; template<typename T> class SSAUpdaterTraits; template<typename UpdaterT> @@ -35,51 +32,67 @@ class SSAUpdaterImpl { private: UpdaterT *Updater; - typedef SSAUpdaterTraits<UpdaterT> Traits; - typedef typename Traits::BlkT BlkT; - typedef typename Traits::ValT ValT; - typedef typename Traits::PhiT PhiT; + 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: - BlkT *BB; // Back-pointer to the corresponding block. - ValT AvailableVal; // Value to use in this block. - BBInfo *DefBB; // Block that defines the available value. - int BlkNum; // Postorder number. - BBInfo *IDom; // Immediate dominator. - unsigned NumPreds; // Number of predecessor blocks. - BBInfo **Preds; // Array[NumPreds] of predecessor blocks. - PhiT *PHITag; // Marker for existing PHIs that match. + // 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), BlkNum(0), - IDom(nullptr), NumPreds(0), Preds(nullptr), PHITag(nullptr) {} + : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {} }; - typedef DenseMap<BlkT*, ValT> AvailableValsTy; + using AvailableValsTy = DenseMap<BlkT *, ValT>; + AvailableValsTy *AvailableVals; - SmallVectorImpl<PhiT*> *InsertedPHIs; + SmallVectorImpl<PhiT *> *InsertedPHIs; + + using BlockListTy = SmallVectorImpl<BBInfo *>; + using BBMapTy = DenseMap<BlkT *, BBInfo *>; - typedef SmallVectorImpl<BBInfo*> BlockListTy; - typedef DenseMap<BlkT*, BBInfo*> BBMapTy; BBMapTy BBMap; BumpPtrAllocator Allocator; public: explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, - SmallVectorImpl<PhiT*> *Ins) : - Updater(U), AvailableVals(A), InsertedPHIs(Ins) { } + 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; + SmallVector<BBInfo *, 100> BlockList; BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList); // Special case: bail out if BB is unreachable. @@ -101,8 +114,8 @@ public: /// 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; + SmallVector<BBInfo *, 10> RootList; + SmallVector<BBInfo *, 64> WorkList; BBInfo *Info = new (Allocator) BBInfo(BB, 0); BBMap[BB] = Info; @@ -111,7 +124,7 @@ public: // 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; + SmallVector<BlkT *, 10> Preds; while (!WorkList.empty()) { Info = WorkList.pop_back_val(); Preds.clear(); @@ -395,7 +408,7 @@ public: /// CheckIfPHIMatches - Check if a PHI node matches the placement and values /// in the BBMap. bool CheckIfPHIMatches(PhiT *PHI) { - SmallVector<PhiT*, 20> WorkList; + SmallVector<PhiT *, 20> WorkList; WorkList.push_back(PHI); // Mark that the block containing this PHI has been visited. @@ -453,7 +466,7 @@ public: } }; -} // end llvm namespace +} // end namespace llvm #undef DEBUG_TYPE // "ssaupdater" diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index 8d50aeb10d6eb..a1dfed29a22d3 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -26,6 +26,7 @@ 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. @@ -47,7 +48,7 @@ public: /// by using ScalarEvolution to analyze the IV's recurrence. bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead, - IVVisitor *V = nullptr); + SCEVExpander &Rewriter, IVVisitor *V = nullptr); /// SimplifyLoopIVs - Simplify users of induction variables within this /// loop. This does not actually change or add IVs. diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h index 6aba9b2298b10..73a62f59203b4 100644 --- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -28,6 +28,7 @@ class Instruction; class TargetLibraryInfo; class BasicBlock; class Function; +class OptimizationRemarkEmitter; /// \brief This class implements simplifications for calls to fortified library /// functions (__st*cpy_chk, __memcpy_chk, __memmove_chk, __memset_chk), to, @@ -73,6 +74,7 @@ private: FortifiedLibCallSimplifier FortifiedSimplifier; const DataLayout &DL; const TargetLibraryInfo *TLI; + OptimizationRemarkEmitter &ORE; bool UnsafeFPShrink; function_ref<void(Instruction *, Value *)> Replacer; @@ -87,6 +89,7 @@ private: public: LibCallSimplifier(const DataLayout &DL, const TargetLibraryInfo *TLI, + OptimizationRemarkEmitter &ORE, function_ref<void(Instruction *, Value *)> Replacer = &replaceAllUsesWithDefault); @@ -126,14 +129,19 @@ private: Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B); // Math Library Optimizations + Value *optimizeCAbs(CallInst *CI, IRBuilder<> &B); Value *optimizeCos(CallInst *CI, IRBuilder<> &B); Value *optimizePow(CallInst *CI, 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); diff --git a/include/llvm/Transforms/Utils/SplitModule.h b/include/llvm/Transforms/Utils/SplitModule.h index b7a3bcf4f86a5..d2c31f2701acc 100644 --- a/include/llvm/Transforms/Utils/SplitModule.h +++ b/include/llvm/Transforms/Utils/SplitModule.h @@ -22,7 +22,6 @@ namespace llvm { class Module; -class StringRef; /// Splits the module M into N linkable partitions. The function ModuleCallback /// is called N times passing each individual partition as the MPart argument. @@ -39,6 +38,6 @@ void SplitModule( function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback, bool PreserveLocals = false); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_SPLITMODULE_H diff --git a/include/llvm/Transforms/Utils/SymbolRewriter.h b/include/llvm/Transforms/Utils/SymbolRewriter.h index 93658989fba57..e0caf7741ff39 100644 --- a/include/llvm/Transforms/Utils/SymbolRewriter.h +++ b/include/llvm/Transforms/Utils/SymbolRewriter.h @@ -1,4 +1,4 @@ -//===-- SymbolRewriter.h - Symbol Rewriting Pass ----------------*- C++ -*-===// +//===- SymbolRewriter.h - Symbol Rewriting Pass -----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -33,7 +33,6 @@ #ifndef LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H #define LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include <list> #include <memory> @@ -42,6 +41,8 @@ namespace llvm { class MemoryBuffer; +class Module; +class ModulePass; namespace yaml { @@ -89,7 +90,7 @@ private: const Type Kind; }; -typedef std::list<std::unique_ptr<RewriteDescriptor>> RewriteDescriptorList; +using RewriteDescriptorList = std::list<std::unique_ptr<RewriteDescriptor>>; class RewriteMapParser { public: @@ -120,6 +121,7 @@ ModulePass *createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &); class RewriteSymbolPass : public PassInfoMixin<RewriteSymbolPass> { public: RewriteSymbolPass() { loadAndParseMapFiles(); } + RewriteSymbolPass(SymbolRewriter::RewriteDescriptorList &DL) { Descriptors.splice(Descriptors.begin(), DL); } diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h index a3115ad16914d..12aa3bc6e7709 100644 --- a/include/llvm/Transforms/Utils/UnrollLoop.h +++ b/include/llvm/Transforms/Utils/UnrollLoop.h @@ -16,40 +16,57 @@ #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H -// Needed because we can't forward-declare the nested struct -// TargetTransformInfo::UnrollingPreferences +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/TargetTransformInfo.h" namespace llvm { -class StringRef; class AssumptionCache; +class BasicBlock; class DominatorTree; class Loop; class LoopInfo; -class LPPassManager; class MDNode; -class Pass; class OptimizationRemarkEmitter; class ScalarEvolution; -typedef SmallDenseMap<const Loop *, Loop *, 4> NewLoopsMap; +using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops); -bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force, - bool AllowRuntime, bool AllowExpensiveTripCount, - bool PreserveCondBr, bool PreserveOnlyFirst, - unsigned TripMultiple, unsigned PeelCount, LoopInfo *LI, - ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, - OptimizationRemarkEmitter *ORE, bool PreserveLCSSA); +/// 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); bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, - bool UseEpilogRemainder, LoopInfo *LI, + bool UseEpilogRemainder, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC, bool PreserveLCSSA); void computePeelCount(Loop *L, unsigned LoopSize, @@ -60,6 +77,7 @@ bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h index 45ef8246dcd16..4ecb23ea19518 100644 --- a/include/llvm/Transforms/Utils/ValueMapper.h +++ b/include/llvm/Transforms/Utils/ValueMapper.h @@ -21,9 +21,17 @@ namespace llvm { -class Value; +class Constant; +class Function; +class GlobalAlias; +class GlobalVariable; class Instruction; -typedef ValueMap<const Value *, WeakTrackingVH> ValueToValueMapTy; +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. @@ -44,10 +52,10 @@ class ValueMaterializer { virtual void anchor(); // Out of line method. protected: - ~ValueMaterializer() = default; 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 @@ -91,7 +99,7 @@ enum RemapFlags { RF_NullMapMissingGlobalValues = 8, }; -static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { +inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { return RemapFlags(unsigned(LHS) | unsigned(RHS)); } |