diff options
Diffstat (limited to 'include/llvm/Transforms')
25 files changed, 759 insertions, 131 deletions
diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h index 2ea47301bb4c..0c374a070ce8 100644 --- a/include/llvm/Transforms/IPO.h +++ b/include/llvm/Transforms/IPO.h @@ -16,9 +16,11 @@ #define LLVM_TRANSFORMS_IPO_H #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringRef.h" namespace llvm { +class FunctionInfoIndex; class ModulePass; class Pass; class Function; @@ -85,6 +87,10 @@ ModulePass *createGVExtractionPass(std::vector<GlobalValue*>& GVs, bool deleteFn = false); //===----------------------------------------------------------------------===// +/// This pass performs iterative function importing from other modules. +Pass *createFunctionImportPass(const FunctionInfoIndex *Index = nullptr); + +//===----------------------------------------------------------------------===// /// createFunctionInliningPass - Return a new pass object that uses a heuristic /// to inline direct function calls to small functions. /// @@ -209,6 +215,15 @@ ModulePass *createBarrierNoopPass(); /// to bitsets. ModulePass *createLowerBitSetsPass(); +/// \brief This pass export CFI checks for use by external modules. +ModulePass *createCrossDSOCFIPass(); + +//===----------------------------------------------------------------------===// +// SampleProfilePass - Loads sample profile data from disk and generates +// IR metadata to reflect the profile. +ModulePass *createSampleProfileLoaderPass(); +ModulePass *createSampleProfileLoaderPass(StringRef Name); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/IPO/ForceFunctionAttrs.h b/include/llvm/Transforms/IPO/ForceFunctionAttrs.h new file mode 100644 index 000000000000..0ff4afe79b0c --- /dev/null +++ b/include/llvm/Transforms/IPO/ForceFunctionAttrs.h @@ -0,0 +1,35 @@ +//===-- ForceFunctionAttrs.h - Force function attrs for debugging ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// Super simple passes to force specific function attrs from the commandline +/// into the IR for debugging purposes. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_FORCEFUNCTIONATTRS_H +#define LLVM_TRANSFORMS_IPO_FORCEFUNCTIONATTRS_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Pass which forces specific function attributes into the IR, primarily as +/// a debugging tool. +class ForceFunctionAttrsPass { +public: + static StringRef name() { return "ForceFunctionAttrsPass"; } + PreservedAnalyses run(Module &M); +}; + +/// Create a legacy pass manager instance of a pass to force function attrs. +Pass *createForceFunctionAttrsLegacyPass(); + +} + +#endif // LLVM_TRANSFORMS_IPO_FORCEFUNCTIONATTRS_H diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h new file mode 100644 index 000000000000..d7707790a017 --- /dev/null +++ b/include/llvm/Transforms/IPO/FunctionImport.h @@ -0,0 +1,43 @@ +//===- llvm/Transforms/IPO/FunctionImport.h - ThinLTO importing -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUNCTIONIMPORT_H +#define LLVM_FUNCTIONIMPORT_H + +#include "llvm/ADT/StringMap.h" +#include <functional> + +namespace llvm { +class LLVMContext; +class Module; +class FunctionInfoIndex; + +/// The function importer is automatically importing function from other modules +/// based on the provided summary informations. +class FunctionImporter { + + /// The summaries index used to trigger importing. + const FunctionInfoIndex &Index; + + /// Factory function to load a Module for a given identifier + std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader; + +public: + /// Create a Function Importer. + FunctionImporter( + const FunctionInfoIndex &Index, + std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader) + : Index(Index), ModuleLoader(ModuleLoader) {} + + /// Import functions in Module \p M based on the summary informations. + bool importFunctions(Module &M); +}; +} + +#endif // LLVM_FUNCTIONIMPORT_H diff --git a/include/llvm/Transforms/IPO/InferFunctionAttrs.h b/include/llvm/Transforms/IPO/InferFunctionAttrs.h new file mode 100644 index 000000000000..80afc02c62ae --- /dev/null +++ b/include/llvm/Transforms/IPO/InferFunctionAttrs.h @@ -0,0 +1,38 @@ +//===-- InferFunctionAttrs.h - Infer implicit function attributes ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// Interfaces for passes which infer implicit function attributes from the +/// name and signature of function declarations. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INFERFUNCTIONATTRS_H +#define LLVM_TRANSFORMS_IPO_INFERFUNCTIONATTRS_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A pass which infers function attributes from the names and signatures of +/// function declarations in a module. +class InferFunctionAttrsPass { +public: + static StringRef name() { return "InferFunctionAttrsPass"; } + PreservedAnalyses run(Module &M, AnalysisManager<Module> *AM); +}; + +/// Create a legacy pass manager instance of a pass to infer function +/// attributes. +Pass *createInferFunctionAttrsLegacyPass(); + +} + +#endif // LLVM_TRANSFORMS_IPO_INFERFUNCTIONATTRS_H diff --git a/include/llvm/Transforms/IPO/InlinerPass.h b/include/llvm/Transforms/IPO/InlinerPass.h index 6a644ad4a63b..58ef0cbbfb5d 100644 --- a/include/llvm/Transforms/IPO/InlinerPass.h +++ b/include/llvm/Transforms/IPO/InlinerPass.h @@ -20,11 +20,11 @@ #include "llvm/Analysis/CallGraphSCCPass.h" namespace llvm { - class CallSite; - class DataLayout; - class InlineCost; - template<class PtrType, unsigned SmallSize> - class SmallPtrSet; +class AssumptionCacheTracker; +class CallSite; +class DataLayout; +class InlineCost; +template <class PtrType, unsigned SmallSize> class SmallPtrSet; /// Inliner - This class contains all of the helper code which is used to /// perform the inlining operations that do not depend on the policy. @@ -84,6 +84,9 @@ private: /// shouldInline - Return true if the inliner should attempt to /// inline at the given CallSite. bool shouldInline(CallSite CS); + +protected: + AssumptionCacheTracker *ACT; }; } // End llvm namespace diff --git a/include/llvm/Transforms/IPO/LowerBitSets.h b/include/llvm/Transforms/IPO/LowerBitSets.h index 55d7d84560a0..e5fb7b98fcb3 100644 --- a/include/llvm/Transforms/IPO/LowerBitSets.h +++ b/include/llvm/Transforms/IPO/LowerBitSets.h @@ -26,8 +26,9 @@ namespace llvm { class DataLayout; -class GlobalVariable; +class GlobalObject; class Value; +class raw_ostream; struct BitSetInfo { // The indices of the set bits in the bitset. @@ -55,8 +56,10 @@ struct BitSetInfo { bool containsGlobalOffset(uint64_t Offset) const; bool containsValue(const DataLayout &DL, - const DenseMap<GlobalVariable *, uint64_t> &GlobalLayout, + const DenseMap<GlobalObject *, uint64_t> &GlobalLayout, Value *V, uint64_t COffset = 0) const; + + void print(raw_ostream &OS) const; }; struct BitSetBuilder { diff --git a/include/llvm/Transforms/IPO/PassManagerBuilder.h b/include/llvm/Transforms/IPO/PassManagerBuilder.h index 1334dd0da23c..a4e7bce8ef4a 100644 --- a/include/llvm/Transforms/IPO/PassManagerBuilder.h +++ b/include/llvm/Transforms/IPO/PassManagerBuilder.h @@ -15,9 +15,11 @@ #ifndef LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H #define LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H +#include <memory> #include <vector> namespace llvm { +class FunctionInfoIndex; class Pass; class TargetLibraryInfoImpl; class TargetMachine; @@ -81,6 +83,11 @@ public: /// run after everything else. EP_OptimizerLast, + /// EP_VectorizerStart - This extension point allows adding optimization + /// passes before the vectorizer and other highly target specific + /// optimization passes are executed. + EP_VectorizerStart, + /// EP_EnabledOnOptLevel0 - This extension point allows adding passes that /// should not be disabled by O0 optimization level. The passes will be /// inserted after the inlining pass. @@ -109,6 +116,9 @@ public: /// added to the per-module passes. Pass *Inliner; + /// The function summary index to use for function importing. + const FunctionInfoIndex *FunctionIndex; + bool DisableTailCalls; bool DisableUnitAtATime; bool DisableUnrollLoops; diff --git a/include/llvm/Transforms/IPO/StripDeadPrototypes.h b/include/llvm/Transforms/IPO/StripDeadPrototypes.h new file mode 100644 index 000000000000..9dddd12871c4 --- /dev/null +++ b/include/llvm/Transforms/IPO/StripDeadPrototypes.h @@ -0,0 +1,34 @@ +//===-- StripDeadPrototypes.h - Remove unused function declarations -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass loops over all of the functions in the input module, looking for +// dead declarations and removes them. Dead declarations are declarations of +// functions for which no implementation is available (i.e., declarations for +// unused library functions). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_STRIPDEADPROTOTYPES_H +#define LLVM_TRANSFORMS_IPO_STRIPDEADPROTOTYPES_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Pass to remove unused function declarations. +class StripDeadPrototypesPass { +public: + static StringRef name() { return "StripDeadPrototypesPass"; } + PreservedAnalyses run(Module &M); +}; + +} + +#endif // LLVM_TRANSFORMS_IPO_STRIPDEADPROTOTYPES_H diff --git a/include/llvm/Transforms/InstCombine/InstCombineWorklist.h b/include/llvm/Transforms/InstCombine/InstCombineWorklist.h index a6bad343db43..5d2b2d000009 100644 --- a/include/llvm/Transforms/InstCombine/InstCombineWorklist.h +++ b/include/llvm/Transforms/InstCombine/InstCombineWorklist.h @@ -60,13 +60,13 @@ public: /// AddInitialGroup - Add the specified batch of stuff in reverse order. /// which should only be done when the worklist is empty and when the group /// has no duplicates. - void AddInitialGroup(Instruction *const *List, unsigned NumEntries) { + void AddInitialGroup(ArrayRef<Instruction *> List) { assert(Worklist.empty() && "Worklist must be empty to add initial group"); - Worklist.reserve(NumEntries+16); - WorklistMap.resize(NumEntries); - DEBUG(dbgs() << "IC: ADDING: " << NumEntries << " instrs to worklist\n"); - for (unsigned Idx = 0; NumEntries; --NumEntries) { - Instruction *I = List[NumEntries-1]; + Worklist.reserve(List.size()+16); + WorklistMap.resize(List.size()); + DEBUG(dbgs() << "IC: ADDING: " << List.size() << " instrs to worklist\n"); + unsigned Idx = 0; + for (Instruction *I : reverse(List)) { WorklistMap.insert(std::make_pair(I, Idx++)); Worklist.push_back(I); } diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h index 250e3893cb15..38dfeb04ace3 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -15,6 +15,7 @@ #define LLVM_TRANSFORMS_INSTRUMENTATION_H #include "llvm/ADT/StringRef.h" +#include "llvm/IR/BasicBlock.h" #include <vector> #if defined(__GNUC__) && defined(__linux__) && !defined(ANDROID) @@ -33,6 +34,16 @@ inline void *getDFSanRetValTLSPtrForJIT() { namespace llvm { +class TargetMachine; + +/// Instrumentation passes often insert conditional checks into entry blocks. +/// Call this function before splitting the entry block to move instructions +/// that must remain in the entry block up before the split point. Static +/// allocas and llvm.localescape calls, for example, must remain in the entry +/// block. +BasicBlock::iterator PrepareToSplitEntryBlock(BasicBlock &BB, + BasicBlock::iterator IP); + class ModulePass; class FunctionPass; @@ -68,6 +79,11 @@ struct GCOVOptions { ModulePass *createGCOVProfilerPass(const GCOVOptions &Options = GCOVOptions::getDefault()); +// PGO Instrumention +ModulePass *createPGOInstrumentationGenPass(); +ModulePass * +createPGOInstrumentationUsePass(StringRef Filename = StringRef("")); + /// Options for the frontend instrumentation based profiling pass. struct InstrProfOptions { InstrProfOptions() : NoRedZone(false) {} @@ -84,8 +100,10 @@ ModulePass *createInstrProfilingPass( const InstrProfOptions &Options = InstrProfOptions()); // Insert AddressSanitizer (address sanity checking) instrumentation -FunctionPass *createAddressSanitizerFunctionPass(bool CompileKernel = false); -ModulePass *createAddressSanitizerModulePass(bool CompileKernel = false); +FunctionPass *createAddressSanitizerFunctionPass(bool CompileKernel = false, + bool Recover = false); +ModulePass *createAddressSanitizerModulePass(bool CompileKernel = false, + bool Recover = false); // Insert MemorySanitizer instrumentation (detection of uninitialized reads) FunctionPass *createMemorySanitizerPass(int TrackOrigins = 0); @@ -134,7 +152,25 @@ FunctionPass *createBoundsCheckingPass(); /// \brief This pass splits the stack into a safe stack and an unsafe stack to /// protect against stack-based overflow vulnerabilities. -FunctionPass *createSafeStackPass(); +FunctionPass *createSafeStackPass(const TargetMachine *TM = nullptr); + +/// \brief Calculate what to divide by to scale counts. +/// +/// Given the maximum count, calculate a divisor that will scale all the +/// weights to strictly less than UINT32_MAX. +static inline uint64_t calculateCountScale(uint64_t MaxCount) { + return MaxCount < UINT32_MAX ? 1 : MaxCount / UINT32_MAX + 1; +} + +/// \brief Scale an individual branch count. +/// +/// Scale a 64-bit weight down to 32-bits using \c Scale. +/// +static inline uint32_t scaleBranchCount(uint64_t Count, uint64_t Scale) { + uint64_t Scaled = Count / Scale; + assert(Scaled <= UINT32_MAX && "overflow 32-bits"); + return Scaled; +} } // End llvm namespace diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index 4676c95d7cd4..9173de1112f3 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -93,7 +93,7 @@ FunctionPass *createBitTrackingDCEPass(); // // SROA - Replace aggregates or pieces of aggregates with scalar SSA values. // -FunctionPass *createSROAPass(bool RequiresDomTree = true); +FunctionPass *createSROAPass(); //===----------------------------------------------------------------------===// // @@ -161,7 +161,8 @@ Pass *createLoopStrengthReducePass(); // It can also be configured to focus on size optimizations only. // Pass *createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset, - bool OnlyOptimizeForSize = false); + bool OnlyOptimizeForSize = false, + bool MergeExternalByDefault = false); //===----------------------------------------------------------------------===// // @@ -407,13 +408,6 @@ FunctionPass *createPartiallyInlineLibCallsPass(); //===----------------------------------------------------------------------===// // -// SampleProfilePass - Loads sample profile data from disk and generates -// IR metadata to reflect the profile. -FunctionPass *createSampleProfileLoaderPass(); -FunctionPass *createSampleProfileLoaderPass(StringRef Name); - -//===----------------------------------------------------------------------===// -// // ScalarizerPass - Converts vector operations into scalar operations // FunctionPass *createScalarizerPass(); @@ -486,6 +480,12 @@ FunctionPass *createNaryReassociatePass(); // FunctionPass *createLoopDistributePass(); +//===----------------------------------------------------------------------===// +// +// LoopLoadElimination - Perform loop-aware load elimination. +// +FunctionPass *createLoopLoadEliminationPass(); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Scalar/ADCE.h b/include/llvm/Transforms/Scalar/ADCE.h new file mode 100644 index 000000000000..f9bc7b77c14a --- /dev/null +++ b/include/llvm/Transforms/Scalar/ADCE.h @@ -0,0 +1,38 @@ +//===- ADCE.h - Aggressive dead code elimination --------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Aggressive Dead Code Elimination +// pass. This pass optimistically assumes that all instructions are dead until +// proven otherwise, allowing it to eliminate dead computations that other DCE +// passes do not catch, particularly involving loop computations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_ADCE_H +#define LLVM_TRANSFORMS_SCALAR_ADCE_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A DCE pass that assumes instructions are dead until proven otherwise. +/// +/// This pass eliminates dead code by optimistically assuming that all +/// instructions are dead until proven otherwise. This allows it to eliminate +/// dead computations that other DCE passes do not catch, particularly involving +/// loop computations. +class ADCEPass { +public: + static StringRef name() { return "ADCEPass"; } + PreservedAnalyses run(Function &F); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_ADCE_H diff --git a/include/llvm/Transforms/Scalar/SROA.h b/include/llvm/Transforms/Scalar/SROA.h new file mode 100644 index 000000000000..f90cc7b686ba --- /dev/null +++ b/include/llvm/Transforms/Scalar/SROA.h @@ -0,0 +1,129 @@ +//===- SROA.h - Scalar Replacement Of Aggregates ----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file provides the interface for LLVM's Scalar Replacement of +/// Aggregates pass. This pass provides both aggregate splitting and the +/// primary SSA formation used in the compiler. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_SROA_H +#define LLVM_TRANSFORMS_SCALAR_SROA_H + +#include "llvm/ADT/SetVector.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by SROA. These +/// are implementation details and should not be used by clients. +namespace sroa { +class AllocaSliceRewriter; +class AllocaSlices; +class Partition; +class SROALegacyPass; +} + +/// \brief An optimization pass providing Scalar Replacement of Aggregates. +/// +/// This pass takes allocations which can be completely analyzed (that is, they +/// don't escape) and tries to turn them into scalar SSA values. There are +/// a few steps to this process. +/// +/// 1) It takes allocations of aggregates and analyzes the ways in which they +/// are used to try to split them into smaller allocations, ideally of +/// a single scalar data type. It will split up memcpy and memset accesses +/// as necessary and try to isolate individual scalar accesses. +/// 2) It will transform accesses into forms which are suitable for SSA value +/// promotion. This can be replacing a memset with a scalar store of an +/// integer value, or it can involve speculating operations on a PHI or +/// select to be a PHI or select of the results. +/// 3) Finally, this will try to detect a pattern of accesses which map cleanly +/// onto insert and extract operations on a vector value, and convert them to +/// this form. By doing so, it will enable promotion of vector aggregates to +/// SSA vector values. +class SROA { + LLVMContext *C; + DominatorTree *DT; + AssumptionCache *AC; + + /// \brief Worklist of alloca instructions to simplify. + /// + /// Each alloca in the function is added to this. Each new alloca formed gets + /// added to it as well to recursively simplify unless that alloca can be + /// directly promoted. Finally, each time we rewrite a use of an alloca other + /// the one being actively rewritten, we add it back onto the list if not + /// already present to ensure it is re-visited. + SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist; + + /// \brief A collection of instructions to delete. + /// We try to batch deletions to simplify code and make things a bit more + /// efficient. + SetVector<Instruction *, SmallVector<Instruction *, 8>> DeadInsts; + + /// \brief Post-promotion worklist. + /// + /// Sometimes we discover an alloca which has a high probability of becoming + /// viable for SROA after a round of promotion takes place. In those cases, + /// the alloca is enqueued here for re-processing. + /// + /// Note that we have to be very careful to clear allocas out of this list in + /// the event they are deleted. + SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist; + + /// \brief A collection of alloca instructions we can directly promote. + std::vector<AllocaInst *> PromotableAllocas; + + /// \brief A worklist of PHIs to speculate prior to promoting allocas. + /// + /// All of these PHIs have been checked for the safety of speculation and by + /// being speculated will allow promoting allocas currently in the promotable + /// queue. + SetVector<PHINode *, SmallVector<PHINode *, 2>> SpeculatablePHIs; + + /// \brief A worklist of select instructions to speculate prior to promoting + /// allocas. + /// + /// All of these select instructions have been checked for the safety of + /// speculation and by being speculated will allow promoting allocas + /// currently in the promotable queue. + SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects; + +public: + SROA() : C(nullptr), DT(nullptr), AC(nullptr) {} + + static StringRef name() { return "SROA"; } + + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); + +private: + friend class sroa::AllocaSliceRewriter; + friend class sroa::SROALegacyPass; + + /// Helper used by both the public run method and by the legacy pass. + PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT, + AssumptionCache &RunAC); + + bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS); + AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS, + sroa::Partition &P); + bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS); + bool runOnAlloca(AllocaInst &AI); + void clobberUse(Use &U); + void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas); + bool promoteAllocas(Function &F); +}; + +} + +#endif diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 9b919b62ee41..13c856dfdc9a 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -22,7 +22,6 @@ namespace llvm { -class AliasAnalysis; class MemoryDependenceAnalysis; class DominatorTree; class LoopInfo; @@ -40,7 +39,7 @@ void DeleteDeadBlock(BasicBlock *BB); /// 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, AliasAnalysis *AA = nullptr, +void FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceAnalysis *MemDep = nullptr); /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it @@ -54,7 +53,6 @@ bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); /// if possible. The return value indicates success or failure. bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, - AliasAnalysis *AA = nullptr, MemoryDependenceAnalysis *MemDep = nullptr); // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) @@ -82,27 +80,15 @@ void ReplaceInstWithInst(Instruction *From, Instruction *To); /// This provides a builder interface for overriding the default options used /// during critical edge splitting. struct CriticalEdgeSplittingOptions { - AliasAnalysis *AA; DominatorTree *DT; LoopInfo *LI; bool MergeIdenticalEdges; bool DontDeleteUselessPHIs; bool PreserveLCSSA; - CriticalEdgeSplittingOptions() - : AA(nullptr), DT(nullptr), LI(nullptr), MergeIdenticalEdges(false), - DontDeleteUselessPHIs(false), PreserveLCSSA(false) {} - - /// \brief Basic case of setting up all the analysis. - CriticalEdgeSplittingOptions(AliasAnalysis *AA, DominatorTree *DT = nullptr, + CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, LoopInfo *LI = nullptr) - : AA(AA), DT(DT), LI(LI), MergeIdenticalEdges(false), - DontDeleteUselessPHIs(false), PreserveLCSSA(false) {} - - /// \brief A common pattern is to preserve the dominator tree and loop - /// info but not care about AA. - CriticalEdgeSplittingOptions(DominatorTree *DT, LoopInfo *LI) - : AA(nullptr), DT(DT), LI(LI), MergeIdenticalEdges(false), + : DT(DT), LI(LI), MergeIdenticalEdges(false), DontDeleteUselessPHIs(false), PreserveLCSSA(false) {} CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { @@ -214,15 +200,13 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more /// details on this case. /// -/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, -/// DominanceFrontier, 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). +/// 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, - AliasAnalysis *AA = nullptr, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, bool PreserveLCSSA = false); @@ -234,17 +218,15 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, /// 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, AliasAnalysis, DominatorTree, -/// DominanceFrontier, 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). +/// 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, - AliasAnalysis *AA = nullptr, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, bool PreserveLCSSA = false); diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h index 2caa9a2462df..92a1d52f1011 100644 --- a/include/llvm/Transforms/Utils/Cloning.h +++ b/include/llvm/Transforms/Utils/Cloning.h @@ -20,9 +20,11 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Twine.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/ValueHandle.h" #include "llvm/IR/ValueMap.h" #include "llvm/Transforms/Utils/ValueMapper.h" +#include <functional> namespace llvm { @@ -43,14 +45,21 @@ class DataLayout; class Loop; class LoopInfo; class AllocaInst; -class AliasAnalysis; class AssumptionCacheTracker; class DominatorTree; -/// CloneModule - Return an exact copy of the specified module +/// Return an exact copy of the specified module /// -Module *CloneModule(const Module *M); -Module *CloneModule(const Module *M, ValueToValueMapTy &VMap); +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, + std::function<bool(const GlobalValue *)> ShouldCloneDefinition); /// ClonedCodeInfo - This struct can be used to capture information about code /// being cloned, while it is being cloned. @@ -65,6 +74,11 @@ struct ClonedCodeInfo { /// size. bool ContainsDynamicAllocas; + /// All cloned call sites that have operand bundles attached are appended to + /// this vector. This vector may contain nulls or undefs if some of the + /// originally inserted callsites were DCE'ed after they were cloned. + std::vector<WeakVH> OperandBundleCallSites; + ClonedCodeInfo() : ContainsCalls(false), ContainsDynamicAllocas(false) {} }; @@ -193,14 +207,12 @@ void CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc, class InlineFunctionInfo { public: explicit InlineFunctionInfo(CallGraph *cg = nullptr, - AliasAnalysis *AA = nullptr, AssumptionCacheTracker *ACT = nullptr) - : CG(cg), AA(AA), ACT(ACT) {} + : CG(cg), ACT(ACT) {} /// CG - If non-null, InlineFunction will update the callgraph to reflect the /// changes it makes. CallGraph *CG; - AliasAnalysis *AA; AssumptionCacheTracker *ACT; /// StaticAllocas - InlineFunction fills this in with all static allocas that @@ -228,11 +240,11 @@ public: /// function by one level. /// bool InlineFunction(CallInst *C, InlineFunctionInfo &IFI, - bool InsertLifetime = true); + AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); bool InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI, - bool InsertLifetime = true); + AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI, - bool InsertLifetime = true); + AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); /// \brief Clones a loop \p OrigLoop. Returns the loop and the blocks in \p /// Blocks. diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index a1bb367ac7b6..81b376f0c212 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -15,6 +15,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H #define LLVM_TRANSFORMS_UTILS_LOCAL_H +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" @@ -40,7 +41,6 @@ class DataLayout; class TargetLibraryInfo; class TargetTransformInfo; class DIBuilder; -class AliasAnalysis; class DominatorTree; template<typename T> class SmallVectorImpl; @@ -271,11 +271,34 @@ bool LowerDbgDeclare(Function &F); /// an alloca, if any. DbgDeclareInst *FindAllocaDbgDeclare(Value *V); -/// \brief Replaces llvm.dbg.declare instruction when an alloca is replaced with -/// a new value. If Deref is true, tan additional DW_OP_deref is prepended to -/// the expression. +/// \brief 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. +bool replaceDbgDeclare(Value *Address, Value *NewAddress, + Instruction *InsertBefore, DIBuilder &Builder, + bool Deref, int Offset); + +/// \brief Replaces llvm.dbg.declare instruction when the alloca it describes +/// 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. bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, - DIBuilder &Builder, bool Deref); + DIBuilder &Builder, bool Deref, int Offset = 0); + +/// \brief Insert an unreachable instruction before the specified +/// instruction, making it and the rest of the code in the block dead. +void changeToUnreachable(Instruction *I, bool UseLLVMTrap); + +/// 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); /// \brief Remove all blocks that can not be reached from the function's entry. /// @@ -291,6 +314,22 @@ void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> Kn /// the given edge. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge); +/// \brief Replace each use of 'From' with 'To' if that use is dominated by +/// the given BasicBlock. Returns the number of replacements made. +unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, + const BasicBlock *BB); + + +/// \brief Return true if the CallSite CS calls a gc leaf function. +/// +/// A leaf function is a function that does not safepoint the thread during its +/// execution. During a call or invoke to such a function, the callers stack +/// 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(ImmutableCallSite CS); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 15747bc7f1ac..17aaee03e4a8 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -15,11 +15,11 @@ #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H #include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" namespace llvm { -class AliasAnalysis; class AliasSet; class AliasSetTracker; class AssumptionCache; @@ -85,24 +85,35 @@ public: RecurrenceDescriptor() : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence), - MinMaxKind(MRK_Invalid) {} + MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr), + RecurrenceType(nullptr), IsSigned(false) {} RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, - MinMaxRecurrenceKind MK) - : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {} + MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, + bool Signed, SmallPtrSetImpl<Instruction *> &CI) + : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK), + UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) { + CastInsts.insert(CI.begin(), CI.end()); + } /// This POD struct holds information about a potential recurrence operation. class InstDesc { public: - InstDesc(bool IsRecur, Instruction *I) - : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid) {} + InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr) + : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid), + UnsafeAlgebraInst(UAI) {} - InstDesc(Instruction *I, MinMaxRecurrenceKind K) - : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K) {} + InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr) + : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K), + UnsafeAlgebraInst(UAI) {} bool isRecurrence() { return IsRecurrence; } + bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } + + Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } + MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; } Instruction *getPatternInst() { return PatternLastInst; } @@ -115,6 +126,8 @@ public: Instruction *PatternLastInst; // If this is a min/max pattern the comparison predicate. MinMaxRecurrenceKind MinMaxKind; + // Recurrence has unsafe algebra. + Instruction *UnsafeAlgebraInst; }; /// Returns a struct describing if the instruction 'I' can be a recurrence @@ -125,7 +138,7 @@ public: static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, InstDesc &Prev, bool HasFunNoNaNAttr); - /// Returns true if instuction I has multiple uses in Insts + /// Returns true if instruction I has multiple uses in Insts static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl<Instruction *> &Insts); @@ -167,6 +180,51 @@ public: Instruction *getLoopExitInstr() { return LoopExitInstr; } + /// Returns true if the recurrence has unsafe algebra which requires a relaxed + /// floating-point model. + bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } + + /// Returns first unsafe algebra instruction in the PHI node's use-chain. + Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } + + /// Returns true if the recurrence kind is an integer kind. + static bool isIntegerRecurrenceKind(RecurrenceKind Kind); + + /// Returns true if the recurrence kind is a floating point kind. + static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind); + + /// Returns true if the recurrence kind is an arithmetic kind. + static bool isArithmeticRecurrenceKind(RecurrenceKind Kind); + + /// Determines if Phi may have been type-promoted. If Phi has a single user + /// that ANDs the Phi with a type mask, return the user. RT is updated to + /// account for the narrower bit width represented by the mask, and the AND + /// instruction is added to CI. + static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT, + SmallPtrSetImpl<Instruction *> &Visited, + SmallPtrSetImpl<Instruction *> &CI); + + /// Returns true if all the source operands of a recurrence are either + /// SExtInsts or ZExtInsts. This function is intended to be used with + /// lookThroughAnd to determine if the recurrence has been type-promoted. The + /// source operands are added to CI, and IsSigned is updated to indicate if + /// all source operands are SExtInsts. + static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit, + Type *RT, bool &IsSigned, + SmallPtrSetImpl<Instruction *> &Visited, + SmallPtrSetImpl<Instruction *> &CI); + + /// Returns the type of the recurrence. This type can be narrower than the + /// actual type of the Phi if the recurrence has been type-promoted. + Type *getRecurrenceType() { return RecurrenceType; } + + /// Returns a reference to the instructions used for type-promoting the + /// recurrence. + SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; } + + /// Returns true if all source operands of the recurrence are SExtInsts. + bool isSigned() { return IsSigned; } + private: // The starting value of the recurrence. // It does not have to be zero! @@ -177,19 +235,74 @@ private: RecurrenceKind Kind; // If this a min/max recurrence the kind of recurrence. MinMaxRecurrenceKind MinMaxKind; + // First occurance of unasfe algebra in the PHI's use-chain. + Instruction *UnsafeAlgebraInst; + // The type of the recurrence. + Type *RecurrenceType; + // True if all source operands of the recurrence are SExtInsts. + bool IsSigned; + // Instructions used for type-promoting the recurrence. + SmallPtrSet<Instruction *, 8> CastInsts; +}; + +/// A struct for saving information about induction variables. +class InductionDescriptor { +public: + /// This enum represents the kinds of inductions that we support. + enum InductionKind { + IK_NoInduction, ///< Not an induction variable. + IK_IntInduction, ///< Integer induction variable. Step = C. + IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem). + }; + +public: + /// Default constructor - creates an invalid induction. + InductionDescriptor() + : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {} + + /// Get the consecutive direction. Returns: + /// 0 - unknown or non-consecutive. + /// 1 - consecutive and increasing. + /// -1 - consecutive and decreasing. + int getConsecutiveDirection() const; + + /// Compute the transformed value of Index at offset StartValue using step + /// StepValue. + /// For integer induction, returns StartValue + Index * StepValue. + /// For pointer induction, returns StartValue[Index * StepValue]. + /// FIXME: The newly created binary instructions should contain nsw/nuw + /// flags, which can be found from the original scalar operations. + Value *transform(IRBuilder<> &B, Value *Index) const; + + Value *getStartValue() const { return StartValue; } + InductionKind getKind() const { return IK; } + ConstantInt *getStepValue() const { return StepValue; } + + static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE, + InductionDescriptor &D); + +private: + /// Private constructor - used by \c isInductionPHI. + InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step); + + /// Start value. + TrackingVH<Value> StartValue; + /// Induction kind. + InductionKind IK; + /// Step value. + ConstantInt *StepValue; }; -BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P); +BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, + bool PreserveLCSSA); /// \brief Simplify each loop in a loop nest recursively. /// /// This takes a potentially un-simplified loop L (and its children) and turns -/// it into a simplified loop nest with preheaders and single backedges. It -/// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if -/// passed into it. -bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP, - AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr, - AssumptionCache *AC = nullptr); +/// 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); /// \brief Put loop into LCSSA form. /// @@ -203,7 +316,7 @@ bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP, /// /// Returns true if any modifications are made to the loop. bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, - ScalarEvolution *SE = nullptr); + ScalarEvolution *SE); /// \brief Put a loop nest into LCSSA form. /// @@ -215,7 +328,7 @@ bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, /// /// Returns true if any modifications are made to the loop. bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, - ScalarEvolution *SE = nullptr); + ScalarEvolution *SE); /// \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 @@ -242,10 +355,10 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, /// \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 +/// 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 +/// AliasSet information for all instructions of the loop and loop safety /// information as arguments. It returns changed status. bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &, SmallVectorImpl<Instruction*> &, @@ -254,15 +367,13 @@ bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &, LICMSafetyInfo *); /// \brief Computes safety information for a loop -/// checks loop body & header for the possiblity of may throw +/// checks loop body & header for the possibility of may throw /// exception, it takes LICMSafetyInfo and loop as argument. /// Updates safety information in LICMSafetyInfo argument. void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *); -/// \brief Checks if the given PHINode in a loop header is an induction -/// variable. Returns true if this is an induction PHI along with the step -/// value. -bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&); +/// \brief Returns the instructions that use values defined in the loop. +SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); } #endif diff --git a/include/llvm/Transforms/Utils/LoopVersioning.h b/include/llvm/Transforms/Utils/LoopVersioning.h index 009fba48c6a3..3b70594e0b63 100644 --- a/include/llvm/Transforms/Utils/LoopVersioning.h +++ b/include/llvm/Transforms/Utils/LoopVersioning.h @@ -16,13 +16,17 @@ #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/ValueMapper.h" +#include "llvm/Transforms/Utils/LoopUtils.h" namespace llvm { class Loop; class LoopAccessInfo; class LoopInfo; +class ScalarEvolution; /// \brief This class emits a version of the loop where run-time checks ensure /// that may-alias pointers can't overlap. @@ -31,13 +35,13 @@ class LoopInfo; /// already has a preheader. class LoopVersioning { public: + /// \brief 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, - const SmallVector<int, 8> *PtrToPartition = nullptr); - - /// \brief Returns true if we need memchecks to disambiguate may-aliasing - /// accesses. - bool needsRuntimeChecks() const; + DominatorTree *DT, ScalarEvolution *SE, + bool UseLAIChecks = true); /// \brief Performs the CFG manipulation part of versioning the loop including /// the DominatorTree and LoopInfo updates. @@ -52,15 +56,11 @@ public: /// analyze L /// if versioning is necessary version L /// transform L - void versionLoop(Pass *P); + void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); } - /// \brief 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. FIXME: this should be invoked internally - /// by versionLoop and made private. - void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside); + /// \brief 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); /// \brief 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 @@ -71,7 +71,21 @@ public: /// loop may alias (i.e. one of the memchecks failed). Loop *getNonVersionedLoop() { return NonVersionedLoop; } + /// \brief Sets the runtime alias checks for versioning the loop. + void setAliasChecks( + const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); + + /// \brief Sets the runtime SCEV checks for versioning the loop. + void setSCEVChecks(SCEVUnionPredicate Check); + private: + /// \brief 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); + /// \brief The original loop. This becomes the "versioned" one. I.e., /// control flows here if pointers in the loop don't alias. Loop *VersionedLoop; @@ -79,21 +93,21 @@ private: /// loop may alias (memchecks failed). Loop *NonVersionedLoop; - /// \brief For each memory pointer it contains the partitionId it is used in. - /// If nullptr, no partitioning is used. - /// - /// The I-th entry corresponds to I-th entry in LAI.getRuntimePointerCheck(). - /// If the pointer is used in multiple partitions the entry is set to -1. - const SmallVector<int, 8> *PtrToPartition; - /// \brief This maps the instructions from VersionedLoop to their counterpart /// in NonVersionedLoop. ValueToValueMapTy VMap; + /// \brief The set of alias checks that we are versioning for. + SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks; + + /// \brief The set of SCEV checks that we are versioning for. + SCEVUnionPredicate Preds; + /// \brief Analyses used. const LoopAccessInfo &LAI; LoopInfo *LI; DominatorTree *DT; + ScalarEvolution *SE; }; } diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h index 622265bae143..0f23d34de5db 100644 --- a/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/include/llvm/Transforms/Utils/ModuleUtils.h @@ -15,6 +15,7 @@ #define LLVM_TRANSFORMS_UTILS_MODULEUTILS_H #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringRef.h" #include <utility> // for std::pair namespace llvm { @@ -56,7 +57,8 @@ Function *checkSanitizerInterfaceFunction(Constant *FuncOrBitcast); /// respectively. std::pair<Function *, Function *> createSanitizerCtorAndInitFunctions( Module &M, StringRef CtorName, StringRef InitName, - ArrayRef<Type *> InitArgTypes, ArrayRef<Value *> InitArgs); + ArrayRef<Type *> InitArgTypes, ArrayRef<Value *> InitArgs, + StringRef VersionCheckName = StringRef()); } // End llvm namespace #endif // LLVM_TRANSFORMS_UTILS_MODULEUTILS_H diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h index ed0841c46c27..425ecd3cfb5e 100644 --- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -378,7 +378,7 @@ public: void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) { for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end(); BBI != BBE; ++BBI) { - PhiT *SomePHI = Traits::InstrIsPHI(BBI); + PhiT *SomePHI = Traits::InstrIsPHI(&*BBI); if (!SomePHI) break; if (CheckIfPHIMatches(SomePHI)) { diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index dcb1d67cbf75..3c55e64537c7 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -25,7 +25,7 @@ class CastInst; class DominatorTree; class IVUsers; class Loop; -class LPPassManager; +class LoopInfo; class PHINode; class ScalarEvolution; @@ -57,13 +57,14 @@ public: /// simplifyUsersOfIV - Simplify instructions that use this induction variable /// by using ScalarEvolution to analyze the IV's recurrence. -bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM, - SmallVectorImpl<WeakVH> &Dead, IVVisitor *V = nullptr); +bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, + LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead, + 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, LPPassManager *LPM, - SmallVectorImpl<WeakVH> &Dead); +bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, + LoopInfo *LI, SmallVectorImpl<WeakVH> &Dead); } // namespace llvm diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h index 41159603aae5..410a075aeb98 100644 --- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -131,8 +131,11 @@ private: Value *optimizePow(CallInst *CI, IRBuilder<> &B); Value *optimizeExp2(CallInst *CI, IRBuilder<> &B); Value *optimizeFabs(CallInst *CI, IRBuilder<> &B); + Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B); + Value *optimizeLog(CallInst *CI, IRBuilder<> &B); Value *optimizeSqrt(CallInst *CI, IRBuilder<> &B); Value *optimizeSinCosPi(CallInst *CI, IRBuilder<> &B); + Value *optimizeTan(CallInst *CI, 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 new file mode 100644 index 000000000000..7d896d1993d6 --- /dev/null +++ b/include/llvm/Transforms/Utils/SplitModule.h @@ -0,0 +1,43 @@ +//===- SplitModule.h - Split a module into partitions -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the 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 <functional> +#include <memory> + +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. +/// +/// 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, + std::function<void(std::unique_ptr<Module> MPart)> ModuleCallback); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h index 7f2cf8d7f59e..710817cddf6a 100644 --- a/include/llvm/Transforms/Utils/UnrollLoop.h +++ b/include/llvm/Transforms/Utils/UnrollLoop.h @@ -21,20 +21,23 @@ namespace llvm { class AssumptionCache; +class DominatorTree; class Loop; class LoopInfo; class LPPassManager; class MDNode; class Pass; +class ScalarEvolution; bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool AllowRuntime, bool AllowExpensiveTripCount, unsigned TripMultiple, - LoopInfo *LI, Pass *PP, LPPassManager *LPM, - AssumptionCache *AC); + LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC, bool PreserveLCSSA); bool UnrollRuntimeLoopProlog(Loop *L, unsigned Count, bool AllowExpensiveTripCount, LoopInfo *LI, - LPPassManager *LPM); + ScalarEvolution *SE, DominatorTree *DT, + bool PreserveLCSSA); MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); } diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h index 047ab818711b..469022f34c56 100644 --- a/include/llvm/Transforms/Utils/ValueMapper.h +++ b/include/llvm/Transforms/Utils/ValueMapper.h @@ -38,13 +38,34 @@ namespace llvm { /// to materialize Values on demand. class ValueMaterializer { virtual void anchor(); // Out of line method. + + protected: + ~ValueMaterializer() = default; + ValueMaterializer() = default; + ValueMaterializer(const ValueMaterializer&) = default; + ValueMaterializer &operator=(const ValueMaterializer&) = default; + public: - virtual ~ValueMaterializer() {} + /// The client should implement this method if they want to generate a + /// mapped Value on demand. For example, if linking lazily. + virtual Value *materializeDeclFor(Value *V) = 0; + + /// If the data being mapped is recursive, the above function can map + /// just the declaration and this is called to compute the initializer. + /// It is called after the mapping is recorded, so it doesn't need to worry + /// about recursion. + virtual void materializeInitFor(GlobalValue *New, GlobalValue *Old); + + /// If the client needs to handle temporary metadata it must implement + /// these methods. + virtual Metadata *mapTemporaryMetadata(Metadata *MD) { return nullptr; } + virtual void replaceTemporaryMetadata(const Metadata *OrigMD, + Metadata *NewMD) {} - /// materializeValueFor - The client should implement this method if they - /// want to generate a mapped Value on demand. For example, if linking - /// lazily. - virtual Value *materializeValueFor(Value *V) = 0; + /// The client should implement this method if some metadata need + /// not be mapped, for example DISubprogram metadata for functions not + /// linked into the destination module. + virtual bool isMetadataNeeded(Metadata *MD) { return true; } }; /// RemapFlags - These are flags that the value mapping APIs allow. @@ -59,7 +80,20 @@ namespace llvm { /// RF_IgnoreMissingEntries - If this flag is set, the remapper ignores /// entries that are not in the value map. If it is unset, it aborts if an /// operand is asked to be remapped which doesn't exist in the mapping. - RF_IgnoreMissingEntries = 2 + RF_IgnoreMissingEntries = 2, + + /// Instruct the remapper to move distinct metadata instead of duplicating + /// it when there are module-level changes. + RF_MoveDistinctMDs = 4, + + /// Any global values not in value map are mapped to null instead of + /// mapping to self. Illegal if RF_IgnoreMissingEntries is also set. + RF_NullMapMissingGlobalValues = 8, + + /// Set when there is still temporary metadata that must be handled, + /// such as when we are doing function importing and will materialize + /// and link metadata as a postpass. + RF_HaveUnmaterializedMetadata = 16, }; static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { |