diff options
Diffstat (limited to 'include/llvm/Transforms')
67 files changed, 1494 insertions, 521 deletions
diff --git a/include/llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h b/include/llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h new file mode 100644 index 000000000000..f970acdc741f --- /dev/null +++ b/include/llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h @@ -0,0 +1,41 @@ +//===- AggressiveInstCombine.h - AggressiveInstCombine pass -----*- 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 primary interface to the aggressive instcombine pass. +/// This pass is suitable for use in the new pass manager. For a pass that works +/// with the legacy pass manager, please use +/// \c createAggressiveInstCombinerPass(). +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_AGGRESSIVE_INSTCOMBINE_INSTCOMBINE_H +#define LLVM_TRANSFORMS_AGGRESSIVE_INSTCOMBINE_INSTCOMBINE_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class AggressiveInstCombinePass + : public PassInfoMixin<AggressiveInstCombinePass> { + +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +//===----------------------------------------------------------------------===// +// +// AggressiveInstCombiner - Combine expression patterns to form expressions with +// fewer, simple instructions. This pass does not modify the CFG. +// +FunctionPass *createAggressiveInstCombinerPass(); +} + +#endif diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h index ce20a726b783..ebc76bf82118 100644 --- a/include/llvm/Transforms/IPO.h +++ b/include/llvm/Transforms/IPO.h @@ -15,6 +15,7 @@ #ifndef LLVM_TRANSFORMS_IPO_H #define LLVM_TRANSFORMS_IPO_H +#include "llvm/ADT/SmallVector.h" #include <functional> #include <vector> @@ -44,10 +45,6 @@ ModulePass *createStripSymbolsPass(bool OnlyDebugInfo = false); // ModulePass *createStripNonDebugSymbolsPass(); -/// This function returns a new pass that downgrades the debug info in the -/// module to line tables only. -ModulePass *createStripNonLineTableDebugInfoPass(); - //===----------------------------------------------------------------------===// // // This pass removes llvm.dbg.declare intrinsics. @@ -179,10 +176,13 @@ Pass *createLoopExtractorPass(); /// Pass *createSingleLoopExtractorPass(); -/// createBlockExtractorPass - This pass extracts all blocks (except those -/// specified in the argument list) from the functions in the module. +/// createBlockExtractorPass - This pass extracts all the specified blocks +/// from the functions in the module. /// ModulePass *createBlockExtractorPass(); +ModulePass * +createBlockExtractorPass(const SmallVectorImpl<BasicBlock *> &BlocksToExtract, + bool EraseFunctions); /// createStripDeadPrototypesPass - This pass removes any function declarations /// (prototypes) that are not used. @@ -207,11 +207,6 @@ ModulePass *createMergeFunctionsPass(); ModulePass *createPartialInliningPass(); //===----------------------------------------------------------------------===// -// createMetaRenamerPass - Rename everything with metasyntatic names. -// -ModulePass *createMetaRenamerPass(); - -//===----------------------------------------------------------------------===// /// createBarrierNoopPass - This pass is purely a module pass barrier in a pass /// manager. ModulePass *createBarrierNoopPass(); @@ -227,7 +222,7 @@ enum class PassSummaryAction { Export, ///< Export information to summary. }; -/// \brief This pass lowers type metadata and the llvm.type.test intrinsic to +/// This pass lowers type metadata and the llvm.type.test intrinsic to /// bitsets. /// /// The behavior depends on the summary arguments: @@ -240,10 +235,10 @@ enum class PassSummaryAction { ModulePass *createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary); -/// \brief This pass export CFI checks for use by external modules. +/// This pass export CFI checks for use by external modules. ModulePass *createCrossDSOCFIPass(); -/// \brief This pass implements whole-program devirtualization using type +/// This pass implements whole-program devirtualization using type /// metadata. /// /// The behavior depends on the summary arguments: diff --git a/include/llvm/Transforms/IPO/AlwaysInliner.h b/include/llvm/Transforms/IPO/AlwaysInliner.h index 15c80357e4a8..b52c0fdbd2c9 100644 --- a/include/llvm/Transforms/IPO/AlwaysInliner.h +++ b/include/llvm/Transforms/IPO/AlwaysInliner.h @@ -27,7 +27,13 @@ namespace llvm { /// be the simplest possible pass to remove always_inline function definitions' /// uses by inlining them. The \c GlobalDCE pass can be used to remove these /// functions once all users are gone. -struct AlwaysInlinerPass : PassInfoMixin<AlwaysInlinerPass> { +class AlwaysInlinerPass : public PassInfoMixin<AlwaysInlinerPass> { + bool InsertLifetime; + +public: + AlwaysInlinerPass(bool InsertLifetime = true) + : InsertLifetime(InsertLifetime) {} + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); }; diff --git a/include/llvm/Transforms/IPO/ArgumentPromotion.h b/include/llvm/Transforms/IPO/ArgumentPromotion.h index 82ffc69a166e..49ca6cc73393 100644 --- a/include/llvm/Transforms/IPO/ArgumentPromotion.h +++ b/include/llvm/Transforms/IPO/ArgumentPromotion.h @@ -22,7 +22,11 @@ namespace llvm { /// transform it and all of its callers to replace indirect arguments with /// direct (by-value) arguments. class ArgumentPromotionPass : public PassInfoMixin<ArgumentPromotionPass> { + unsigned MaxElements; + public: + ArgumentPromotionPass(unsigned MaxElements = 3u) : MaxElements(MaxElements) {} + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR); }; diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h index 39e5b5c8ae6f..120a34e15933 100644 --- a/include/llvm/Transforms/IPO/FunctionImport.h +++ b/include/llvm/Transforms/IPO/FunctionImport.h @@ -33,11 +33,17 @@ class Module; /// based on the provided summary informations. class FunctionImporter { public: - /// Set of functions to import from a source module. Each entry is a map - /// containing all the functions to import for a source module. - /// The keys is the GUID identifying a function to import, and the value - /// is the threshold applied when deciding to import it. - using FunctionsToImportTy = std::map<GlobalValue::GUID, unsigned>; + /// Set of functions to import from a source module. Each entry is a set + /// containing all the GUIDs of all functions to import for a source module. + using FunctionsToImportTy = std::unordered_set<GlobalValue::GUID>; + + /// Map of callee GUID considered for import into a given module to a pair + /// consisting of the largest threshold applied when deciding whether to + /// import it and, if we decided to import, a pointer to the summary instance + /// imported. If we decided not to import, the summary will be nullptr. + using ImportThresholdsTy = + DenseMap<GlobalValue::GUID, + std::pair<unsigned, const GlobalValueSummary *>>; /// The map contains an entry for every module to import from, the key being /// the module identifier to pass to the ModuleLoader. The value is the set of @@ -107,12 +113,24 @@ void ComputeCrossModuleImportForModuleFromIndex( StringRef ModulePath, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportList); +/// PrevailingType enum used as a return type of callback passed +/// to computeDeadSymbols. Yes and No values used when status explicitly +/// set by symbols resolution, otherwise status is Unknown. +enum class PrevailingType { Yes, No, Unknown }; + /// Compute all the symbols that are "dead": i.e these that can't be reached /// in the graph from any of the given symbols listed in -/// \p GUIDPreservedSymbols. +/// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a +/// prevailing copy anywhere in IR and are normally dead, \p isPrevailing +/// predicate returns status of symbol. void computeDeadSymbols( ModuleSummaryIndex &Index, - const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols); + const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols, + function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing); + +/// Converts value \p GV to declaration, or replaces with a declaration if +/// it is an alias. Returns true if converted, false if replaced. +bool convertToDeclaration(GlobalValue &GV); /// Compute the set of summaries needed for a ThinLTO backend compilation of /// \p ModulePath. @@ -131,9 +149,9 @@ void gatherImportedSummariesForModule( std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); /// Emit into \p OutputFilename the files module \p ModulePath will import from. -std::error_code -EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename, - const FunctionImporter::ImportMapTy &ModuleImports); +std::error_code EmitImportsFiles( + StringRef ModulePath, StringRef OutputFilename, + const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); /// Resolve WeakForLinker values in \p TheModule based on the information /// recorded in the summaries during global summary-based analysis. diff --git a/include/llvm/Transforms/IPO/Inliner.h b/include/llvm/Transforms/IPO/Inliner.h index eda8cf462b50..610e4500e4b1 100644 --- a/include/llvm/Transforms/IPO/Inliner.h +++ b/include/llvm/Transforms/IPO/Inliner.h @@ -96,12 +96,17 @@ class InlinerPass : public PassInfoMixin<InlinerPass> { public: InlinerPass(InlineParams Params = getInlineParams()) : Params(std::move(Params)) {} + ~InlinerPass(); + InlinerPass(InlinerPass &&Arg) + : Params(std::move(Arg.Params)), + ImportedFunctionsStats(std::move(Arg.ImportedFunctionsStats)) {} PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR); private: InlineParams Params; + std::unique_ptr<ImportedFunctionsInliningStatistics> ImportedFunctionsStats; }; } // end namespace llvm diff --git a/include/llvm/Transforms/IPO/LowerTypeTests.h b/include/llvm/Transforms/IPO/LowerTypeTests.h index 3bcfe65df550..bc448386b63d 100644 --- a/include/llvm/Transforms/IPO/LowerTypeTests.h +++ b/include/llvm/Transforms/IPO/LowerTypeTests.h @@ -26,6 +26,7 @@ namespace llvm { class Module; +class ModuleSummaryIndex; class raw_ostream; namespace lowertypetests { @@ -197,6 +198,11 @@ struct ByteArrayBuilder { class LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> { public: + ModuleSummaryIndex *ExportSummary; + const ModuleSummaryIndex *ImportSummary; + LowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, + const ModuleSummaryIndex *ImportSummary) + : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {} PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; diff --git a/include/llvm/Transforms/SampleProfile.h b/include/llvm/Transforms/IPO/SampleProfile.h index f5a8590e14a1..cd5a0563898e 100644 --- a/include/llvm/Transforms/SampleProfile.h +++ b/include/llvm/Transforms/IPO/SampleProfile.h @@ -1,4 +1,4 @@ -//===- Transforms/SampleProfile.h - SamplePGO pass --------------*- C++ -*-===// +//===- SampleProfile.h - SamplePGO pass ---------- --------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_TRANSFORMS_SAMPLEPROFILE_H -#define LLVM_TRANSFORMS_SAMPLEPROFILE_H +#ifndef LLVM_TRANSFORMS_IPO_SAMPLEPROFILE_H +#define LLVM_TRANSFORMS_IPO_SAMPLEPROFILE_H #include "llvm/IR/PassManager.h" #include <string> diff --git a/include/llvm/Transforms/IPO/SyntheticCountsPropagation.h b/include/llvm/Transforms/IPO/SyntheticCountsPropagation.h new file mode 100644 index 000000000000..0b3ba86bc9e4 --- /dev/null +++ b/include/llvm/Transforms/IPO/SyntheticCountsPropagation.h @@ -0,0 +1,19 @@ +#ifndef LLVM_TRANSFORMS_IPO_SYNTHETIC_COUNTS_PROPAGATION_H +#define LLVM_TRANSFORMS_IPO_SYNTHETIC_COUNTS_PROPAGATION_H + +#include "llvm/ADT/STLExtras.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/ScaledNumber.h" + +namespace llvm { +class Function; +class Module; + +class SyntheticCountsPropagation + : public PassInfoMixin<SyntheticCountsPropagation> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM); +}; +} // namespace llvm +#endif diff --git a/include/llvm/Transforms/IPO/WholeProgramDevirt.h b/include/llvm/Transforms/IPO/WholeProgramDevirt.h index 1aa4c6f4f559..bf2c79b0751e 100644 --- a/include/llvm/Transforms/IPO/WholeProgramDevirt.h +++ b/include/llvm/Transforms/IPO/WholeProgramDevirt.h @@ -28,6 +28,7 @@ template <typename T> class ArrayRef; template <typename T> class MutableArrayRef; class Function; class GlobalVariable; +class ModuleSummaryIndex; namespace wholeprogramdevirt { @@ -218,6 +219,13 @@ void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets, } // end namespace wholeprogramdevirt struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> { + ModuleSummaryIndex *ExportSummary; + const ModuleSummaryIndex *ImportSummary; + WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, + const ModuleSummaryIndex *ImportSummary) + : ExportSummary(ExportSummary), ImportSummary(ImportSummary) { + assert(!(ExportSummary && ImportSummary)); + } PreservedAnalyses run(Module &M, ModuleAnalysisManager &); }; diff --git a/include/llvm/Transforms/InstCombine/InstCombine.h b/include/llvm/Transforms/InstCombine/InstCombine.h index 6bd22dc46255..ab25fe08553a 100644 --- a/include/llvm/Transforms/InstCombine/InstCombine.h +++ b/include/llvm/Transforms/InstCombine/InstCombine.h @@ -10,8 +10,7 @@ /// /// This file provides the primary interface to the instcombine pass. This pass /// is suitable for use in the new pass manager. For a pass that works with the -/// legacy pass manager, please look for \c createInstructionCombiningPass() in -/// Scalar.h. +/// legacy pass manager, use \c createInstructionCombiningPass(). /// //===----------------------------------------------------------------------===// @@ -37,7 +36,7 @@ public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -/// \brief The legacy pass manager's instcombine pass. +/// The legacy pass manager's instcombine pass. /// /// This is a basic whole-function wrapper around the instcombine utility. It /// will try to combine all instructions in the function. @@ -56,6 +55,20 @@ public: void getAnalysisUsage(AnalysisUsage &AU) const override; bool runOnFunction(Function &F) override; }; + +//===----------------------------------------------------------------------===// +// +// InstructionCombining - Combine instructions to form fewer, simple +// instructions. This pass does not modify the CFG, and has a tendency to make +// instructions dead, so a subsequent DCE pass is useful. +// +// This pass combines things like: +// %Y = add int 1, %X +// %Z = add int 1, %Y +// into: +// %Z = add int 2, %X +// +FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines = true); } #endif diff --git a/include/llvm/Transforms/InstCombine/InstCombineWorklist.h b/include/llvm/Transforms/InstCombine/InstCombineWorklist.h index 271e891bb45e..f860b4b86555 100644 --- a/include/llvm/Transforms/InstCombine/InstCombineWorklist.h +++ b/include/llvm/Transforms/InstCombine/InstCombineWorklist.h @@ -40,7 +40,7 @@ public: /// in it. void Add(Instruction *I) { if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) { - DEBUG(dbgs() << "IC: ADD: " << *I << '\n'); + LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n'); Worklist.push_back(I); } } @@ -57,7 +57,8 @@ public: assert(Worklist.empty() && "Worklist must be empty to add initial group"); Worklist.reserve(List.size()+16); WorklistMap.reserve(List.size()); - DEBUG(dbgs() << "IC: ADDING: " << List.size() << " instrs to worklist\n"); + LLVM_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++)); diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h index b1e13f17aef1..4a346c8d7450 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -133,7 +133,8 @@ ModulePass *createAddressSanitizerModulePass(bool CompileKernel = false, FunctionPass *createMemorySanitizerPass(int TrackOrigins = 0, bool Recover = false); -FunctionPass *createHWAddressSanitizerPass(bool Recover = false); +FunctionPass *createHWAddressSanitizerPass(bool CompileKernel = false, + bool Recover = false); // Insert ThreadSanitizer (race detection) instrumentation FunctionPass *createThreadSanitizerPass(); @@ -186,7 +187,7 @@ struct SanitizerCoverageOptions { ModulePass *createSanitizerCoverageModulePass( const SanitizerCoverageOptions &Options = SanitizerCoverageOptions()); -/// \brief Calculate what to divide by to scale counts. +/// 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 std::numeric_limits<uint32_t>::max(). @@ -196,7 +197,7 @@ static inline uint64_t calculateCountScale(uint64_t MaxCount) { : MaxCount / std::numeric_limits<uint32_t>::max() + 1; } -/// \brief Scale an individual branch count. +/// Scale an individual branch count. /// /// Scale a 64-bit weight down to 32-bits using \c Scale. /// diff --git a/include/llvm/Transforms/Instrumentation/CGProfile.h b/include/llvm/Transforms/Instrumentation/CGProfile.h new file mode 100644 index 000000000000..c06c1a28715e --- /dev/null +++ b/include/llvm/Transforms/Instrumentation/CGProfile.h @@ -0,0 +1,31 @@ +//===- Transforms/Instrumentation/CGProfile.h -------------------*- 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 Call Graph Profile pass. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_CGPROFILE_H +#define LLVM_TRANSFORMS_CGPROFILE_H + +#include "llvm/ADT/MapVector.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class CGProfilePass : public PassInfoMixin<CGProfilePass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); + +private: + void addModuleFlags( + Module &M, + MapVector<std::pair<Function *, Function *>, uint64_t> &Counts) const; +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_CGPROFILE_H diff --git a/include/llvm/Transforms/GCOVProfiler.h b/include/llvm/Transforms/Instrumentation/GCOVProfiler.h index 66bd75c88e24..dd55fbe29eed 100644 --- a/include/llvm/Transforms/GCOVProfiler.h +++ b/include/llvm/Transforms/Instrumentation/GCOVProfiler.h @@ -1,4 +1,4 @@ -//===- Transforms/GCOVProfiler.h - GCOVProfiler pass ----------*- C++ -*-===// +//===- Transforms/Instrumentation/GCOVProfiler.h ----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // diff --git a/include/llvm/Transforms/InstrProfiling.h b/include/llvm/Transforms/Instrumentation/InstrProfiling.h index 0fe6ad5eeac7..13fb3db4ae6f 100644 --- a/include/llvm/Transforms/InstrProfiling.h +++ b/include/llvm/Transforms/Instrumentation/InstrProfiling.h @@ -1,4 +1,4 @@ -//===- Transforms/InstrProfiling.h - Instrumentation passes -----*- C++ -*-===// +//===- Transforms/Instrumentation/InstrProfiling.h --------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -109,7 +109,8 @@ private: void emitRegistration(); /// Emit the necessary plumbing to pull in the runtime initialization. - void emitRuntimeHook(); + /// Returns true if a change was made. + bool emitRuntimeHook(); /// Add uses of our data variables and runtime hook. void emitUses(); diff --git a/include/llvm/Transforms/PGOInstrumentation.h b/include/llvm/Transforms/Instrumentation/PGOInstrumentation.h index c2cc76c422da..c0b37c470b74 100644 --- a/include/llvm/Transforms/PGOInstrumentation.h +++ b/include/llvm/Transforms/Instrumentation/PGOInstrumentation.h @@ -1,4 +1,4 @@ -//===- Transforms/PGOInstrumentation.h - PGO gen/use passes -----*- C++ -*-===// +//===- Transforms/Instrumentation/PGOInstrumentation.h ----------*- C++ -*-===// // // The LLVM Compiler Infrastructure // diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index 49186bc5cd66..9491e1bbac93 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -80,7 +80,6 @@ FunctionPass *createDeadStoreEliminationPass(); // values. FunctionPass *createCallSiteSplittingPass(); - //===----------------------------------------------------------------------===// // // AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm. This @@ -89,7 +88,6 @@ FunctionPass *createCallSiteSplittingPass(); // FunctionPass *createAggressiveDCEPass(); - //===----------------------------------------------------------------------===// // // GuardWidening - An optimization over the @llvm.experimental.guard intrinsic @@ -101,6 +99,16 @@ FunctionPass *createGuardWideningPass(); //===----------------------------------------------------------------------===// // +// LoopGuardWidening - Analogous to the GuardWidening pass, but restricted to a +// single loop at a time for use within a LoopPassManager. Desired effect is +// to widen guards into preheader or a single guard within loop if that's not +// possible. +// +Pass *createLoopGuardWideningPass(); + + +//===----------------------------------------------------------------------===// +// // BitTrackingDCE - This pass uses a bit-tracking DCE algorithm in order to // remove computations of dead bits. // @@ -128,20 +136,6 @@ Pass *createIndVarSimplifyPass(); //===----------------------------------------------------------------------===// // -// InstructionCombining - Combine instructions to form fewer, simple -// instructions. This pass does not modify the CFG, and has a tendency to make -// instructions dead, so a subsequent DCE pass is useful. -// -// This pass combines things like: -// %Y = add int 1, %X -// %Z = add int 1, %Y -// into: -// %Z = add int 2, %X -// -FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines = true); - -//===----------------------------------------------------------------------===// -// // LICM - This pass is a loop invariant code motion and memory promotion pass. // Pass *createLICMPass(); @@ -198,6 +192,12 @@ Pass *createSimpleLoopUnrollPass(int OptLevel = 2); //===----------------------------------------------------------------------===// // +// LoopUnrollAndJam - This pass is a simple loop unroll and jam pass. +// +Pass *createLoopUnrollAndJamPass(int OptLevel = 2); + +//===----------------------------------------------------------------------===// +// // LoopReroll - This pass is a simple loop rerolling pass. // Pass *createLoopRerollPass(); @@ -222,20 +222,6 @@ Pass *createLoopVersioningLICMPass(); //===----------------------------------------------------------------------===// // -// PromoteMemoryToRegister - This pass is used to promote memory references to -// be register references. A simple example of the transformation performed by -// this pass is: -// -// FROM CODE TO CODE -// %X = alloca i32, i32 1 ret i32 42 -// store i32 42, i32 *%X -// %Y = load i32* %X -// ret i32 %Y -// -FunctionPass *createPromoteMemoryToRegisterPass(); - -//===----------------------------------------------------------------------===// -// // DemoteRegisterToMemoryPass - This pass is used to demote registers to memory // references. In basically undoes the PromoteMemoryToRegister pass to make cfg // hacking easier. @@ -288,31 +274,6 @@ Pass *createStructurizeCFGPass(bool SkipUniformRegions = false); //===----------------------------------------------------------------------===// // -// BreakCriticalEdges - Break all of the critical edges in the CFG by inserting -// a dummy basic block. This pass may be "required" by passes that cannot deal -// with critical edges. For this usage, a pass must call: -// -// AU.addRequiredID(BreakCriticalEdgesID); -// -// This pass obviously invalidates the CFG, but can update forward dominator -// (set, immediate dominators, tree, and frontier) information. -// -FunctionPass *createBreakCriticalEdgesPass(); -extern char &BreakCriticalEdgesID; - -//===----------------------------------------------------------------------===// -// -// LoopSimplify - Insert Pre-header blocks into the CFG for every function in -// the module. This pass updates dominator information, loop information, and -// does not add critical edges to the CFG. -// -// AU.addRequiredID(LoopSimplifyID); -// -Pass *createLoopSimplifyPass(); -extern char &LoopSimplifyID; - -//===----------------------------------------------------------------------===// -// // TailCallElimination - This pass eliminates call instructions to the current // function which occur immediately before return instructions. // @@ -320,30 +281,6 @@ FunctionPass *createTailCallEliminationPass(); //===----------------------------------------------------------------------===// // -// LowerSwitch - This pass converts SwitchInst instructions into a sequence of -// chained binary branch instructions. -// -FunctionPass *createLowerSwitchPass(); -extern char &LowerSwitchID; - -//===----------------------------------------------------------------------===// -// -// LowerInvoke - This pass removes invoke instructions, converting them to call -// instructions. -// -FunctionPass *createLowerInvokePass(); -extern char &LowerInvokePassID; - -//===----------------------------------------------------------------------===// -// -// LCSSA - This pass inserts phi nodes at loop boundaries to simplify other loop -// optimizations. -// -Pass *createLCSSAPass(); -extern char &LCSSAID; - -//===----------------------------------------------------------------------===// -// // EarlyCSE - This pass performs a simple and fast CSE pass over the dominator // tree. // @@ -405,13 +342,6 @@ FunctionPass *createConstantHoistingPass(); //===----------------------------------------------------------------------===// // -// InstructionNamer - Give any unnamed non-void instructions "tmp" names. -// -FunctionPass *createInstructionNamerPass(); -extern char &InstructionNamerID; - -//===----------------------------------------------------------------------===// -// // Sink - Code Sinking // FunctionPass *createSinkingPass(); @@ -451,13 +381,6 @@ extern char &InferAddressSpacesID; //===----------------------------------------------------------------------===// // -// InstructionSimplifier - Remove redundant instructions. -// -FunctionPass *createInstructionSimplifierPass(); -extern char &InstructionSimplifierID; - -//===----------------------------------------------------------------------===// -// // LowerExpectIntrinsics - Removes llvm.expect intrinsics and creates // "block_weights" metadata. FunctionPass *createLowerExpectIntrinsicPass(); @@ -477,16 +400,9 @@ FunctionPass *createScalarizerPass(); //===----------------------------------------------------------------------===// // -// AddDiscriminators - Add DWARF path discriminators to the IR. -FunctionPass *createAddDiscriminatorsPass(); - -//===----------------------------------------------------------------------===// -// // SeparateConstOffsetFromGEP - Split GEPs for better CSE // -FunctionPass * -createSeparateConstOffsetFromGEPPass(const TargetMachine *TM = nullptr, - bool LowerGEP = false); +FunctionPass *createSeparateConstOffsetFromGEPPass(bool LowerGEP = false); //===----------------------------------------------------------------------===// // @@ -525,13 +441,6 @@ ModulePass *createRewriteStatepointsForGCLegacyPass(); //===----------------------------------------------------------------------===// // -// StripGCRelocates - Remove GC relocates that have been inserted by -// RewriteStatepointsForGC. The resulting IR is incorrect, but this is useful -// for manual inspection. -FunctionPass *createStripGCRelocatesPass(); - -//===----------------------------------------------------------------------===// -// // Float2Int - Demote floats to ints where possible. // FunctionPass *createFloat2IntPass(); @@ -556,13 +465,6 @@ FunctionPass *createLoopLoadEliminationPass(); //===----------------------------------------------------------------------===// // -// LoopSimplifyCFG - This pass performs basic CFG simplification on loops, -// primarily to help other loop passes. -// -Pass *createLoopSimplifyCFGPass(); - -//===----------------------------------------------------------------------===// -// // LoopVersioning - Perform loop multi-versioning. // FunctionPass *createLoopVersioningPass(); @@ -585,13 +487,10 @@ FunctionPass *createLibCallsShrinkWrapPass(); //===----------------------------------------------------------------------===// // -// 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. +// LoopSimplifyCFG - This pass performs basic CFG simplification on loops, +// primarily to help other loop passes. // -FunctionPass *createEntryExitInstrumenterPass(); -FunctionPass *createPostInlineEntryExitInstrumenterPass(); - +Pass *createLoopSimplifyCFGPass(); } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Scalar/AlignmentFromAssumptions.h b/include/llvm/Transforms/Scalar/AlignmentFromAssumptions.h index f75dc4dc331d..61975036e9ff 100644 --- a/include/llvm/Transforms/Scalar/AlignmentFromAssumptions.h +++ b/include/llvm/Transforms/Scalar/AlignmentFromAssumptions.h @@ -33,12 +33,6 @@ struct AlignmentFromAssumptionsPass bool runImpl(Function &F, AssumptionCache &AC, ScalarEvolution *SE_, DominatorTree *DT_); - // For memory transfers, we need a common alignment for both the source and - // destination. If we have a new alignment for only one operand of a transfer - // instruction, save it in these maps. If we reach the other operand through - // another assumption later, then we may change the alignment at that point. - DenseMap<MemTransferInst *, unsigned> NewDestAlignments, NewSrcAlignments; - ScalarEvolution *SE = nullptr; DominatorTree *DT = nullptr; diff --git a/include/llvm/Transforms/Scalar/CallSiteSplitting.h b/include/llvm/Transforms/Scalar/CallSiteSplitting.h index 5ab951a49f2c..b2ca2a1c09ae 100644 --- a/include/llvm/Transforms/Scalar/CallSiteSplitting.h +++ b/include/llvm/Transforms/Scalar/CallSiteSplitting.h @@ -21,7 +21,7 @@ namespace llvm { struct CallSiteSplittingPass : PassInfoMixin<CallSiteSplittingPass> { - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; } // end namespace llvm diff --git a/include/llvm/Transforms/Scalar/ConstantHoisting.h b/include/llvm/Transforms/Scalar/ConstantHoisting.h index d3322dc1c414..84589bf4db99 100644 --- a/include/llvm/Transforms/Scalar/ConstantHoisting.h +++ b/include/llvm/Transforms/Scalar/ConstantHoisting.h @@ -60,7 +60,7 @@ class TargetTransformInfo; /// clients. namespace consthoist { -/// \brief Keeps track of the user of a constant and the operand index where the +/// Keeps track of the user of a constant and the operand index where the /// constant is used. struct ConstantUser { Instruction *Inst; @@ -71,7 +71,7 @@ struct ConstantUser { using ConstantUseListType = SmallVector<ConstantUser, 8>; -/// \brief Keeps track of a constant candidate and its uses. +/// Keeps track of a constant candidate and its uses. struct ConstantCandidate { ConstantUseListType Uses; ConstantInt *ConstInt; @@ -79,14 +79,14 @@ struct ConstantCandidate { ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {} - /// \brief Add the user to the use list and update the cost. + /// Add the user to the use list and update the cost. void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { CumulativeCost += Cost; Uses.push_back(ConstantUser(Inst, Idx)); } }; -/// \brief This represents a constant that has been rebased with respect to a +/// This represents a constant that has been rebased with respect to a /// base constant. The difference to the base constant is recorded in Offset. struct RebasedConstantInfo { ConstantUseListType Uses; @@ -98,7 +98,7 @@ struct RebasedConstantInfo { using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>; -/// \brief A base constant and all its rebased constants. +/// A base constant and all its rebased constants. struct ConstantInfo { ConstantInt *BaseConstant; RebasedConstantListType RebasedConstants; diff --git a/include/llvm/Transforms/Scalar/EarlyCSE.h b/include/llvm/Transforms/Scalar/EarlyCSE.h index dca3b2dbf04f..faf03a4ec489 100644 --- a/include/llvm/Transforms/Scalar/EarlyCSE.h +++ b/include/llvm/Transforms/Scalar/EarlyCSE.h @@ -21,7 +21,7 @@ namespace llvm { class Function; -/// \brief A simple and fast domtree-based CSE pass. +/// A simple and fast domtree-based CSE pass. /// /// This pass does a simple depth-first walk over the dominator tree, /// eliminating trivially redundant instructions and using instsimplify to @@ -31,7 +31,7 @@ class Function; struct EarlyCSEPass : PassInfoMixin<EarlyCSEPass> { EarlyCSEPass(bool UseMemorySSA = false) : UseMemorySSA(UseMemorySSA) {} - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); bool UseMemorySSA; diff --git a/include/llvm/Transforms/Scalar/GVN.h b/include/llvm/Transforms/Scalar/GVN.h index 440d3f67c35a..b9de07ec9279 100644 --- a/include/llvm/Transforms/Scalar/GVN.h +++ b/include/llvm/Transforms/Scalar/GVN.h @@ -69,7 +69,7 @@ class GVN : public PassInfoMixin<GVN> { public: struct Expression; - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); /// This removes the specified instruction from @@ -291,17 +291,17 @@ private: /// loads are eliminated by the pass. FunctionPass *createGVNPass(bool NoLoads = false); -/// \brief A simple and fast domtree-based GVN pass to hoist common expressions +/// A simple and fast domtree-based GVN pass to hoist common expressions /// from sibling branches. struct GVNHoistPass : PassInfoMixin<GVNHoistPass> { - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -/// \brief Uses an "inverted" value numbering to decide the similarity of +/// Uses an "inverted" value numbering to decide the similarity of /// expressions and sinks similar expressions into successors. struct GVNSinkPass : PassInfoMixin<GVNSinkPass> { - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; diff --git a/include/llvm/Transforms/Scalar/GVNExpression.h b/include/llvm/Transforms/Scalar/GVNExpression.h index 99dae15a3ac0..8b346969b1e9 100644 --- a/include/llvm/Transforms/Scalar/GVNExpression.h +++ b/include/llvm/Transforms/Scalar/GVNExpression.h @@ -159,7 +159,7 @@ public: return ET > ET_BasicStart && ET < ET_BasicEnd; } - /// \brief Swap two operands. Used during GVN to put commutative operands in + /// Swap two operands. Used during GVN to put commutative operands in /// order. void swapOperands(unsigned First, unsigned Second) { std::swap(Operands[First], Operands[Second]); diff --git a/include/llvm/Transforms/Scalar/InductiveRangeCheckElimination.h b/include/llvm/Transforms/Scalar/InductiveRangeCheckElimination.h new file mode 100644 index 000000000000..311c549b8326 --- /dev/null +++ b/include/llvm/Transforms/Scalar/InductiveRangeCheckElimination.h @@ -0,0 +1,31 @@ +//===- InductiveRangeCheckElimination.h - IRCE ------------------*- C++ -*-===// +// +// 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 Inductive Range Check Elimination +// loop pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_INDUCTIVERANGECHECKELIMINATION_H +#define LLVM_TRANSFORMS_SCALAR_INDUCTIVERANGECHECKELIMINATION_H + +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +class IRCEPass : public PassInfoMixin<IRCEPass> { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_INDUCTIVERANGECHECKELIMINATION_H diff --git a/include/llvm/Transforms/Scalar/InstSimplifyPass.h b/include/llvm/Transforms/Scalar/InstSimplifyPass.h new file mode 100644 index 000000000000..da79a13eb7cf --- /dev/null +++ b/include/llvm/Transforms/Scalar/InstSimplifyPass.h @@ -0,0 +1,46 @@ +//===- InstSimplifyPass.h ---------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// Defines passes for running instruction simplification across chunks of IR. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_INSTSIMPLIFYPASS_H +#define LLVM_TRANSFORMS_UTILS_INSTSIMPLIFYPASS_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class FunctionPass; + +/// Run instruction simplification across each instruction in the function. +/// +/// Instruction simplification has useful constraints in some contexts: +/// - It will never introduce *new* instructions. +/// - There is no need to iterate to a fixed point. +/// +/// Many passes use instruction simplification as a library facility, but it may +/// also be useful (in tests and other contexts) to have access to this very +/// restricted transform at a pass granularity. However, for a much more +/// powerful and comprehensive peephole optimization engine, see the +/// `instcombine` pass instead. +class InstSimplifyPass : public PassInfoMixin<InstSimplifyPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +/// Create a legacy pass that does instruction simplification on each +/// instruction in a function. +FunctionPass *createInstSimplifyLegacyPass(); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_INSTSIMPLIFYPASS_H diff --git a/include/llvm/Transforms/Scalar/JumpThreading.h b/include/llvm/Transforms/Scalar/JumpThreading.h index a9466713b8e6..b3493a292498 100644 --- a/include/llvm/Transforms/Scalar/JumpThreading.h +++ b/include/llvm/Transforms/Scalar/JumpThreading.h @@ -34,6 +34,7 @@ class BinaryOperator; class BranchInst; class CmpInst; class Constant; +class DeferredDominance; class Function; class Instruction; class IntrinsicInst; @@ -77,6 +78,7 @@ class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { TargetLibraryInfo *TLI; LazyValueInfo *LVI; AliasAnalysis *AA; + DeferredDominance *DDT; std::unique_ptr<BlockFrequencyInfo> BFI; std::unique_ptr<BranchProbabilityInfo> BPI; bool HasProfileData = false; @@ -107,8 +109,8 @@ public: // Glue for old PM. bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_, - AliasAnalysis *AA_, bool HasProfileData_, - std::unique_ptr<BlockFrequencyInfo> BFI_, + AliasAnalysis *AA_, DeferredDominance *DDT_, + bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_, std::unique_ptr<BranchProbabilityInfo> BPI_); PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); diff --git a/include/llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h b/include/llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h index 5eddd5fdc7e7..e1b33799578b 100644 --- a/include/llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h +++ b/include/llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h @@ -15,7 +15,7 @@ namespace llvm { -/// \brief Printer pass for the \c LoopAccessInfo results. +/// Printer pass for the \c LoopAccessInfo results. class LoopAccessInfoPrinterPass : public PassInfoMixin<LoopAccessInfoPrinterPass> { raw_ostream &OS; diff --git a/include/llvm/Transforms/Scalar/LoopDataPrefetch.h b/include/llvm/Transforms/Scalar/LoopDataPrefetch.h index 12c7a030ff8b..e1ad67ac6fff 100644 --- a/include/llvm/Transforms/Scalar/LoopDataPrefetch.h +++ b/include/llvm/Transforms/Scalar/LoopDataPrefetch.h @@ -24,7 +24,7 @@ class LoopDataPrefetchPass : public PassInfoMixin<LoopDataPrefetchPass> { public: LoopDataPrefetchPass() = default; - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; diff --git a/include/llvm/Transforms/Scalar/LoopPassManager.h b/include/llvm/Transforms/Scalar/LoopPassManager.h index 473b97dc7e8d..5f61c39b5530 100644 --- a/include/llvm/Transforms/Scalar/LoopPassManager.h +++ b/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -71,7 +71,7 @@ PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, extern template class PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, LPMUpdater &>; -/// \brief The Loop pass manager. +/// The Loop pass manager. /// /// See the documentation for the PassManager template for details. It runs /// a sequence of Loop passes over each Loop that the manager is run over. This @@ -253,7 +253,7 @@ private: : Worklist(Worklist), LAM(LAM) {} }; -/// \brief Adaptor that maps from a function to its loops. +/// Adaptor that maps from a function to its loops. /// /// Designed to allow composition of a LoopPass(Manager) and a /// FunctionPassManager. Note that if this pass is constructed with a \c @@ -264,12 +264,13 @@ template <typename LoopPassT> class FunctionToLoopPassAdaptor : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> { public: - explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) { + explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false) + : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging) { LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); LoopCanonicalizationFPM.addPass(LCSSAPass()); } - /// \brief Runs the loop passes across every loop in the function. + /// Runs the loop passes across every loop in the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { // Before we even compute any loop analyses, first run a miniature function // pass pipeline to put loops into their canonical form. Note that we can @@ -380,15 +381,15 @@ private: FunctionPassManager LoopCanonicalizationFPM; }; -/// \brief A function to deduce a loop pass type and wrap it in the templated +/// A function to deduce a loop pass type and wrap it in the templated /// adaptor. template <typename LoopPassT> FunctionToLoopPassAdaptor<LoopPassT> -createFunctionToLoopPassAdaptor(LoopPassT Pass) { - return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass)); +createFunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false) { + return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), DebugLogging); } -/// \brief Pass for printing a loop's contents as textual IR. +/// Pass for printing a loop's contents as textual IR. class PrintLoopPass : public PassInfoMixin<PrintLoopPass> { raw_ostream &OS; std::string Banner; diff --git a/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h b/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h new file mode 100644 index 000000000000..fc69aa361059 --- /dev/null +++ b/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h @@ -0,0 +1,35 @@ +//===- LoopUnrollAndJamPass.h -----------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H +#define LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H + +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Loop; +struct LoopStandardAnalysisResults; +class LPMUpdater; + +/// A simple loop rotation transformation. +class LoopUnrollAndJamPass : public PassInfoMixin<LoopUnrollAndJamPass> { + const int OptLevel; + +public: + explicit LoopUnrollAndJamPass(int OptLevel = 2) : OptLevel(OptLevel) {} + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPUNROLLANDJAMPASS_H diff --git a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h index ab9dec0311b2..b6ee6523697c 100644 --- a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h +++ b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h @@ -22,7 +22,7 @@ namespace llvm { struct LowerExpectIntrinsicPass : PassInfoMixin<LowerExpectIntrinsicPass> { - /// \brief Run the pass over the function. + /// Run the pass over the function. /// /// This will lower all of the expect intrinsic calls in this function into /// branch weight metadata. That metadata will subsequently feed the analysis diff --git a/include/llvm/Transforms/Scalar/MergedLoadStoreMotion.h b/include/llvm/Transforms/Scalar/MergedLoadStoreMotion.h index 3cad7bb070d0..48df09cdec9e 100644 --- a/include/llvm/Transforms/Scalar/MergedLoadStoreMotion.h +++ b/include/llvm/Transforms/Scalar/MergedLoadStoreMotion.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// // //! \file -//! \brief This pass performs merges of loads and stores on both sides of a +//! This pass performs merges of loads and stores on both sides of a // diamond (hammock). It hoists the loads and sinks the stores. // // The algorithm iteratively hoists two loads to the same address out of a diff --git a/include/llvm/Transforms/Scalar/NewGVN.h b/include/llvm/Transforms/Scalar/NewGVN.h index 05db25502dc3..3f7541863a19 100644 --- a/include/llvm/Transforms/Scalar/NewGVN.h +++ b/include/llvm/Transforms/Scalar/NewGVN.h @@ -23,7 +23,7 @@ class Function; class NewGVNPass : public PassInfoMixin<NewGVNPass> { public: - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); }; diff --git a/include/llvm/Transforms/Scalar/Reassociate.h b/include/llvm/Transforms/Scalar/Reassociate.h index 9997dfa5b6f3..ba7586dffd9d 100644 --- a/include/llvm/Transforms/Scalar/Reassociate.h +++ b/include/llvm/Transforms/Scalar/Reassociate.h @@ -29,6 +29,7 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/ValueHandle.h" +#include <deque> namespace llvm { @@ -54,7 +55,7 @@ inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. } -/// \brief Utility class representing a base and exponent pair which form one +/// Utility class representing a base and exponent pair which form one /// factor of some product. struct Factor { Value *Base; @@ -69,9 +70,14 @@ class XorOpnd; /// Reassociate commutative expressions. class ReassociatePass : public PassInfoMixin<ReassociatePass> { +public: + using OrderedSet = + SetVector<AssertingVH<Instruction>, std::deque<AssertingVH<Instruction>>>; + +protected: DenseMap<BasicBlock *, unsigned> RankMap; DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; - SetVector<AssertingVH<Instruction>> RedoInsts; + OrderedSet RedoInsts; // Arbitrary, but prevents quadratic behavior. static const unsigned GlobalReassociateLimit = 10; @@ -108,8 +114,7 @@ private: SmallVectorImpl<reassociate::ValueEntry> &Ops); Value *RemoveFactorFromExpression(Value *V, Value *Factor); void EraseInst(Instruction *I); - void RecursivelyEraseDeadInsts(Instruction *I, - SetVector<AssertingVH<Instruction>> &Insts); + void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts); void OptimizeInst(Instruction *I); Instruction *canonicalizeNegConstExpr(Instruction *I); void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT); diff --git a/include/llvm/Transforms/Scalar/SCCP.h b/include/llvm/Transforms/Scalar/SCCP.h index b93287fff907..2a294c95a17b 100644 --- a/include/llvm/Transforms/Scalar/SCCP.h +++ b/include/llvm/Transforms/Scalar/SCCP.h @@ -21,6 +21,10 @@ #ifndef LLVM_TRANSFORMS_SCALAR_SCCP_H #define LLVM_TRANSFORMS_SCALAR_SCCP_H +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" namespace llvm { @@ -33,6 +37,7 @@ public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; +bool runIPSCCP(Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI); } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_SCCP_H diff --git a/include/llvm/Transforms/Scalar/SROA.h b/include/llvm/Transforms/Scalar/SROA.h index 4a321e75c68b..b36c6f492be1 100644 --- a/include/llvm/Transforms/Scalar/SROA.h +++ b/include/llvm/Transforms/Scalar/SROA.h @@ -45,7 +45,7 @@ class SROALegacyPass; } // end namespace sroa -/// \brief An optimization pass providing Scalar Replacement of Aggregates. +/// 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 @@ -68,7 +68,7 @@ class SROA : public PassInfoMixin<SROA> { DominatorTree *DT = nullptr; AssumptionCache *AC = nullptr; - /// \brief Worklist of alloca instructions to simplify. + /// 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 @@ -77,12 +77,12 @@ class SROA : public PassInfoMixin<SROA> { /// already present to ensure it is re-visited. SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist; - /// \brief A collection of instructions to delete. + /// 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. + /// 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, @@ -92,17 +92,17 @@ class SROA : public PassInfoMixin<SROA> { /// the event they are deleted. SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist; - /// \brief A collection of alloca instructions we can directly promote. + /// A collection of alloca instructions we can directly promote. std::vector<AllocaInst *> PromotableAllocas; - /// \brief A worklist of PHIs to speculate prior to promoting allocas. + /// 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 + /// A worklist of select instructions to speculate prior to promoting /// allocas. /// /// All of these select instructions have been checked for the safety of @@ -113,7 +113,7 @@ class SROA : public PassInfoMixin<SROA> { public: SROA() = default; - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); private: diff --git a/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h b/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h index 63bfe6373d04..eed50ec96161 100644 --- a/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h +++ b/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h @@ -17,9 +17,9 @@ namespace llvm { -/// This pass transforms loops that contain branches on loop-invariant -/// conditions to have multiple loops. For example, it turns the left into the -/// right code: +/// This pass transforms loops that contain branches or switches on loop- +/// invariant conditions to have multiple loops. For example, it turns the left +/// into the right code: /// /// for (...) if (lic) /// A for (...) @@ -35,6 +35,31 @@ namespace llvm { /// This pass expects LICM to be run before it to hoist invariant conditions out /// of the loop, to make the unswitching opportunity obvious. /// +/// There is a taxonomy of unswitching that we use to classify different forms +/// of this transformaiton: +/// +/// - Trival unswitching: this is when the condition can be unswitched without +/// cloning any code from inside the loop. A non-trivial unswitch requires +/// code duplication. +/// +/// - Full unswitching: this is when the branch or switch is completely moved +/// from inside the loop to outside the loop. Partial unswitching removes the +/// branch from the clone of the loop but must leave a (somewhat simplified) +/// branch in the original loop. While theoretically partial unswitching can +/// be done for switches, the requirements are extreme - we need the loop +/// invariant input to the switch to be sufficient to collapse to a single +/// successor in each clone. +/// +/// This pass always does trivial, full unswitching for both branches and +/// switches. For branches, it also always does trivial, partial unswitching. +/// +/// If enabled (via the constructor's `NonTrivial` parameter), this pass will +/// additionally do non-trivial, full unswitching for branches and switches, and +/// will do non-trivial, partial unswitching for branches. +/// +/// Because partial unswitching of switches is extremely unlikely to be possible +/// in practice and significantly complicates the implementation, this pass does +/// not currently implement that in any mode. class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> { bool NonTrivial; diff --git a/include/llvm/Transforms/Scalar/SimplifyCFG.h b/include/llvm/Transforms/Scalar/SimplifyCFG.h index 1afb9c7f954f..ce0a35fc06bd 100644 --- a/include/llvm/Transforms/Scalar/SimplifyCFG.h +++ b/include/llvm/Transforms/Scalar/SimplifyCFG.h @@ -15,9 +15,9 @@ #ifndef LLVM_TRANSFORMS_SCALAR_SIMPLIFYCFG_H #define LLVM_TRANSFORMS_SCALAR_SIMPLIFYCFG_H +#include "llvm/Transforms/Utils/Local.h" #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Utils/Local.h" namespace llvm { @@ -46,7 +46,7 @@ public: /// Construct a pass with optional optimizations. SimplifyCFGPass(const SimplifyCFGOptions &PassOptions); - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; diff --git a/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h b/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h index f39e03d22d65..4a0bfd754723 100644 --- a/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h +++ b/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h @@ -102,7 +102,7 @@ namespace llvm { /// here are relatively simple ones around execution and codesize cost, without /// any need to consider simplifications or other transformations. struct SpeculateAroundPHIsPass : PassInfoMixin<SpeculateAroundPHIsPass> { - /// \brief Run the pass over the function. + /// Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; diff --git a/include/llvm/Transforms/Utils.h b/include/llvm/Transforms/Utils.h new file mode 100644 index 000000000000..0d997ce17b83 --- /dev/null +++ b/include/llvm/Transforms/Utils.h @@ -0,0 +1,118 @@ +//===- llvm/Transforms/Utils.h - Utility Transformations --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This header file defines prototypes for accessor functions that expose passes +// in the Utils transformations library. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_H +#define LLVM_TRANSFORMS_UTILS_H + +namespace llvm { + +class ModulePass; +class FunctionPass; +class Pass; + +//===----------------------------------------------------------------------===// +// createMetaRenamerPass - Rename everything with metasyntatic names. +// +ModulePass *createMetaRenamerPass(); + +//===----------------------------------------------------------------------===// +// +// LowerInvoke - This pass removes invoke instructions, converting them to call +// instructions. +// +FunctionPass *createLowerInvokePass(); +extern char &LowerInvokePassID; + +//===----------------------------------------------------------------------===// +// +// InstructionNamer - Give any unnamed non-void instructions "tmp" names. +// +FunctionPass *createInstructionNamerPass(); +extern char &InstructionNamerID; + +//===----------------------------------------------------------------------===// +// +// LowerSwitch - This pass converts SwitchInst instructions into a sequence of +// chained binary branch instructions. +// +FunctionPass *createLowerSwitchPass(); +extern char &LowerSwitchID; + +//===----------------------------------------------------------------------===// +// +// 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. +// +FunctionPass *createEntryExitInstrumenterPass(); +FunctionPass *createPostInlineEntryExitInstrumenterPass(); + +//===----------------------------------------------------------------------===// +// +// BreakCriticalEdges - Break all of the critical edges in the CFG by inserting +// a dummy basic block. This pass may be "required" by passes that cannot deal +// with critical edges. For this usage, a pass must call: +// +// AU.addRequiredID(BreakCriticalEdgesID); +// +// This pass obviously invalidates the CFG, but can update forward dominator +// (set, immediate dominators, tree, and frontier) information. +// +FunctionPass *createBreakCriticalEdgesPass(); +extern char &BreakCriticalEdgesID; + +//===----------------------------------------------------------------------===// +// +// LCSSA - This pass inserts phi nodes at loop boundaries to simplify other loop +// optimizations. +// +Pass *createLCSSAPass(); +extern char &LCSSAID; + +//===----------------------------------------------------------------------===// +// +// AddDiscriminators - Add DWARF path discriminators to the IR. +FunctionPass *createAddDiscriminatorsPass(); + +//===----------------------------------------------------------------------===// +// +// PromoteMemoryToRegister - This pass is used to promote memory references to +// be register references. A simple example of the transformation performed by +// this pass is: +// +// FROM CODE TO CODE +// %X = alloca i32, i32 1 ret i32 42 +// store i32 42, i32 *%X +// %Y = load i32* %X +// ret i32 %Y +// +FunctionPass *createPromoteMemoryToRegisterPass(); + +//===----------------------------------------------------------------------===// +// +// LoopSimplify - Insert Pre-header blocks into the CFG for every function in +// the module. This pass updates dominator information, loop information, and +// does not add critical edges to the CFG. +// +// AU.addRequiredID(LoopSimplifyID); +// +Pass *createLoopSimplifyPass(); +extern char &LoopSimplifyID; + +/// This function returns a new pass that downgrades the debug info in the +/// module to line tables only. +ModulePass *createStripNonLineTableDebugInfoPass(); +} + +#endif diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 74f75509f550..3dfc73b64842 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -27,6 +27,7 @@ namespace llvm { class BlockFrequencyInfo; class BranchProbabilityInfo; +class DeferredDominance; class DominatorTree; class Function; class Instruction; @@ -38,7 +39,7 @@ class TargetLibraryInfo; class Value; /// Delete the specified block, which must have no predecessors. -void DeleteDeadBlock(BasicBlock *BB); +void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT = nullptr); /// We know that BB has one predecessor. If there are any single-entry PHI nodes /// in it, fold them away. This handles the case when all entries to the PHI @@ -57,7 +58,8 @@ bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); /// value indicates success or failure. bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, - MemoryDependenceResults *MemDep = nullptr); + MemoryDependenceResults *MemDep = nullptr, + DeferredDominance *DDT = nullptr); /// Replace all uses of an instruction (specified by BI) with a value, then /// remove and delete the original instruction. diff --git a/include/llvm/Transforms/Utils/BuildLibCalls.h b/include/llvm/Transforms/Utils/BuildLibCalls.h index a067a685b837..bdcdf6f361f2 100644 --- a/include/llvm/Transforms/Utils/BuildLibCalls.h +++ b/include/llvm/Transforms/Utils/BuildLibCalls.h @@ -15,6 +15,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H #define LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/IRBuilder.h" namespace llvm { @@ -29,6 +30,12 @@ namespace llvm { /// Returns true if any attributes were set and false otherwise. bool inferLibFuncAttributes(Function &F, const TargetLibraryInfo &TLI); + /// Check whether the overloaded unary floating point function + /// corresponding to \a Ty is available. + bool hasUnaryFloatFn(const TargetLibraryInfo *TLI, Type *Ty, + LibFunc DoubleFn, LibFunc FloatFn, + LibFunc LongDoubleFn); + /// Return V if it is an i8*, otherwise cast it to i8*. Value *castToCStr(Value *V, IRBuilder<> &B); @@ -104,15 +111,54 @@ namespace llvm { Value *emitFPutC(Value *Char, Value *File, IRBuilder<> &B, const TargetLibraryInfo *TLI); - /// Emit a call to the puts function. Str is required to be a pointer and + /// Emit a call to the fputc_unlocked function. This assumes that Char is an + /// i32, and File is a pointer to FILE. + Value *emitFPutCUnlocked(Value *Char, Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fputs function. Str is required to be a pointer and /// File is a pointer to FILE. Value *emitFPutS(Value *Str, Value *File, IRBuilder<> &B, const TargetLibraryInfo *TLI); + /// Emit a call to the fputs_unlocked function. Str is required to be a + /// pointer and File is a pointer to FILE. + Value *emitFPutSUnlocked(Value *Str, Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + /// Emit a call to the fwrite function. This assumes that Ptr is a pointer, /// Size is an 'intptr_t', and File is a pointer to FILE. Value *emitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI); + + /// Emit a call to the malloc function. + Value *emitMalloc(Value *Num, IRBuilder<> &B, const DataLayout &DL, + const TargetLibraryInfo *TLI); + + /// Emit a call to the calloc function. + Value *emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs, + IRBuilder<> &B, const TargetLibraryInfo &TLI); + + /// Emit a call to the fwrite_unlocked function. This assumes that Ptr is a + /// pointer, Size is an 'intptr_t', N is nmemb and File is a pointer to FILE. + Value *emitFWriteUnlocked(Value *Ptr, Value *Size, Value *N, Value *File, + IRBuilder<> &B, const DataLayout &DL, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fgetc_unlocked function. File is a pointer to FILE. + Value *emitFGetCUnlocked(Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fgets_unlocked function. Str is required to be a + /// pointer, Size is an i32 and File is a pointer to FILE. + Value *emitFGetSUnlocked(Value *Str, Value *Size, Value *File, IRBuilder<> &B, + const TargetLibraryInfo *TLI); + + /// Emit a call to the fread_unlocked function. This assumes that Ptr is a + /// pointer, Size is an 'intptr_t', N is nmemb and File is a pointer to FILE. + Value *emitFReadUnlocked(Value *Ptr, Value *Size, Value *N, Value *File, + IRBuilder<> &B, const DataLayout &DL, + const TargetLibraryInfo *TLI); } #endif diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h index 178bae76cef6..7531fb2d69b3 100644 --- a/include/llvm/Transforms/Utils/Cloning.h +++ b/include/llvm/Transforms/Utils/Cloning.h @@ -49,15 +49,15 @@ class ReturnInst; /// Return an exact copy of the specified module /// -std::unique_ptr<Module> CloneModule(const Module *M); -std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap); +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, +CloneModule(const Module &M, ValueToValueMapTy &VMap, function_ref<bool(const GlobalValue *)> ShouldCloneDefinition); /// ClonedCodeInfo - This struct can be used to capture information about code @@ -240,7 +240,7 @@ bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI, AAResults *CalleeAAR = nullptr, bool InsertLifetime = true, Function *ForwardVarArgsTo = nullptr); -/// \brief Clones a loop \p OrigLoop. Returns the loop and the blocks in \p +/// Clones a loop \p OrigLoop. Returns the loop and the blocks in \p /// Blocks. /// /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block @@ -252,7 +252,7 @@ Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, DominatorTree *DT, SmallVectorImpl<BasicBlock *> &Blocks); -/// \brief Remaps instructions in \p Blocks using the mapping in \p VMap. +/// Remaps instructions in \p Blocks using the mapping in \p VMap. void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks, ValueToValueMapTy &VMap); @@ -265,7 +265,8 @@ void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks, BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, - ValueToValueMapTy &ValueMapping); + ValueToValueMapTy &ValueMapping, + DominatorTree *DT = nullptr); } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_CLONING_H diff --git a/include/llvm/Transforms/Utils/CodeExtractor.h b/include/llvm/Transforms/Utils/CodeExtractor.h index 63d34511102d..fab8334d4c66 100644 --- a/include/llvm/Transforms/Utils/CodeExtractor.h +++ b/include/llvm/Transforms/Utils/CodeExtractor.h @@ -34,7 +34,7 @@ class Module; class Type; class Value; - /// \brief Utility class for extracting code into a new function. + /// Utility class for extracting code into a new function. /// /// This utility provides a simple interface for extracting some sequence of /// code into its own function, replacing it with a call to that function. It @@ -65,20 +65,22 @@ class Value; Type *RetTy; public: - /// \brief Create a code extractor for a sequence of blocks. + /// Create a code extractor for a sequence of blocks. /// /// Given a sequence of basic blocks where the first block in the sequence /// dominates the rest, prepare a code extractor object for pulling this /// sequence out into its new function. When a DominatorTree is also given, /// extra checking and transformations are enabled. If AllowVarArgs is true, /// vararg functions can be extracted. This is safe, if all vararg handling - /// code is extracted, including vastart. + /// code is extracted, including vastart. If AllowAlloca is true, then + /// extraction of blocks containing alloca instructions would be possible, + /// however code extractor won't validate whether extraction is legal. CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, BranchProbabilityInfo *BPI = nullptr, - bool AllowVarArgs = false); + bool AllowVarArgs = false, bool AllowAlloca = false); - /// \brief Create a code extractor for a loop body. + /// Create a code extractor for a loop body. /// /// Behaves just like the generic code sequence constructor, but uses the /// block sequence of the loop. @@ -86,27 +88,19 @@ class Value; 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. + /// Perform the extraction, returning the new function. /// /// Returns zero when called on a CodeExtractor instance where isEligible /// returns false. Function *extractCodeRegion(); - /// \brief Test whether this code extractor is eligible. + /// Test whether this code extractor is eligible. /// /// Based on the blocks used when constructing the code extractor, /// determine whether it is eligible for extraction. bool isEligible() const { return !Blocks.empty(); } - /// \brief Compute the set of input values and output values for the code. + /// Compute the set of input values and output values for the code. /// /// These can be used either when performing the extraction or to evaluate /// the expected size of a call to the extracted function. Note that this diff --git a/include/llvm/Transforms/Utils/Evaluator.h b/include/llvm/Transforms/Utils/Evaluator.h index 0e987b93177a..9908ae6fd393 100644 --- a/include/llvm/Transforms/Utils/Evaluator.h +++ b/include/llvm/Transforms/Utils/Evaluator.h @@ -18,6 +18,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" @@ -73,6 +74,18 @@ public: ValueStack.back()[V] = C; } + /// Given call site return callee and list of its formal arguments + Function *getCalleeWithFormalArgs(CallSite &CS, + SmallVector<Constant *, 8> &Formals); + + /// Given call site and callee returns list of callee formal argument + /// values converting them when necessary + bool getFormalParams(CallSite &CS, Function *F, + SmallVector<Constant *, 8> &Formals); + + /// Casts call result to a type of bitcast call expression + Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV); + const DenseMap<Constant*, Constant*> &getMutatedMemory() const { return MutatedMemory; } diff --git a/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h b/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h index b7a3d130aa11..b55a9893bcf7 100644 --- a/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h +++ b/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h @@ -22,7 +22,7 @@ namespace llvm { class Module; class Function; -/// \brief Calculate and dump ThinLTO specific inliner stats. +/// Calculate and dump ThinLTO specific inliner stats. /// The main statistics are: /// (1) Number of inlined imported functions, /// (2) Number of imported functions inlined into importing module (indirect), diff --git a/include/llvm/Transforms/Utils/IntegerDivision.h b/include/llvm/Transforms/Utils/IntegerDivision.h index 0ec3321b9cf8..5d9927eb51b2 100644 --- a/include/llvm/Transforms/Utils/IntegerDivision.h +++ b/include/llvm/Transforms/Utils/IntegerDivision.h @@ -29,7 +29,7 @@ namespace llvm { /// e.g. when more information about the operands are known. Implements both /// 32bit and 64bit scalar division. /// - /// @brief Replace Rem with generated code. + /// Replace Rem with generated code. bool expandRemainder(BinaryOperator *Rem); /// Generate code to divide two integers, replacing Div with the generated @@ -38,7 +38,7 @@ namespace llvm { /// when more information about the operands are known. Implements both /// 32bit and 64bit scalar division. /// - /// @brief Replace Div with generated code. + /// Replace Div with generated code. bool expandDivision(BinaryOperator* Div); /// Generate code to calculate the remainder of two integers, replacing Rem @@ -46,26 +46,26 @@ namespace llvm { /// makes it useful for targets with little or no support for less than /// 32 bit arithmetic. /// - /// @brief Replace Rem with generated code. + /// Replace Rem with generated code. bool expandRemainderUpTo32Bits(BinaryOperator *Rem); /// Generate code to calculate the remainder of two integers, replacing Rem /// with the generated code. Uses ExpandReminder with a 64bit Rem. /// - /// @brief Replace Rem with generated code. + /// Replace Rem with generated code. bool expandRemainderUpTo64Bits(BinaryOperator *Rem); /// Generate code to divide two integers, replacing Div with the generated /// code. Uses ExpandDivision with a 32bit Div which makes it useful for /// targets with little or no support for less than 32 bit arithmetic. /// - /// @brief Replace Rem with generated code. + /// Replace Rem with generated code. bool expandDivisionUpTo32Bits(BinaryOperator *Div); /// Generate code to divide two integers, replacing Div with the generated /// code. Uses ExpandDivision with a 64bit Div. /// - /// @brief Replace Rem with generated code. + /// Replace Rem with generated code. bool expandDivisionUpTo64Bits(BinaryOperator *Div); } // End llvm namespace diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 01db88bc15c2..b8df32565723 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -16,10 +16,12 @@ #define LLVM_TRANSFORMS_UTILS_LOCAL_H #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/Utils/Local.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" @@ -117,7 +119,8 @@ struct SimplifyCFGOptions { /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, - const TargetLibraryInfo *TLI = nullptr); + const TargetLibraryInfo *TLI = nullptr, + DeferredDominance *DDT = nullptr); //===----------------------------------------------------------------------===// // Local dead code elimination. @@ -140,6 +143,18 @@ bool wouldInstructionBeTriviallyDead(Instruction *I, bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI = nullptr); +/// Delete all of the instructions in `DeadInsts`, and all other instructions +/// that deleting these in turn causes to be trivially dead. +/// +/// The initial instructions in the provided vector must all have empty use +/// lists and satisfy `isInstructionTriviallyDead`. +/// +/// `DeadInsts` will be used as scratch storage for this routine and will be +/// empty afterward. +void RecursivelyDeleteTriviallyDeadInstructions( + SmallVectorImpl<Instruction *> &DeadInsts, + const TargetLibraryInfo *TLI = nullptr); + /// If the specified value is an effectively dead PHI node, due to being a /// def-use chain of single-use nodes that either forms a cycle or is terminated /// by a trivially dead instruction, delete it. If that makes any of its @@ -171,18 +186,21 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB, /// /// .. and delete the predecessor corresponding to the '1', this will attempt to /// recursively fold the 'and' to 0. -void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred); +void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, + DeferredDominance *DDT = nullptr); /// BB is a block with one predecessor and its predecessor is known to have one /// successor (BB!). Eliminate the edge between them, moving the instructions in /// the predecessor into BB. This deletes the predecessor block. -void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr); +void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr, + DeferredDominance *DDT = nullptr); /// BB is known to contain an unconditional branch, and contains no instructions /// other than PHI nodes, potential debug intrinsics and the branch. If /// possible, eliminate BB by rewriting all the predecessors to branch to the /// successor block and return true. If we can't transform, return false. -bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); +bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, + DeferredDominance *DDT = nullptr); /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try /// to be clever about PHI nodes which differ only in the order of the incoming @@ -246,72 +264,6 @@ inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); } -/// Given a getelementptr instruction/constantexpr, emit the code necessary to -/// compute the offset from the base pointer (without adding in the base -/// pointer). Return the result as a signed integer of intptr size. -/// When NoAssumptions is true, no assumptions about index computation not -/// overflowing is made. -template <typename IRBuilderTy> -Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, - bool NoAssumptions = false) { - GEPOperator *GEPOp = cast<GEPOperator>(GEP); - Type *IntPtrTy = DL.getIntPtrType(GEP->getType()); - Value *Result = Constant::getNullValue(IntPtrTy); - - // If the GEP is inbounds, we know that none of the addressing operations will - // overflow in an unsigned sense. - bool isInBounds = GEPOp->isInBounds() && !NoAssumptions; - - // Build a mask for high order bits. - unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth(); - 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; - ++i, ++GTI) { - Value *Op = *i; - uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask; - if (Constant *OpC = dyn_cast<Constant>(Op)) { - if (OpC->isZeroValue()) - continue; - - // Handle a struct index, which adds its field offset to the pointer. - if (StructType *STy = GTI.getStructTypeOrNull()) { - if (OpC->getType()->isVectorTy()) - OpC = OpC->getSplatValue(); - - uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue(); - Size = DL.getStructLayout(STy)->getElementOffset(OpValue); - - if (Size) - Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size), - GEP->getName()+".offs"); - continue; - } - - Constant *Scale = ConstantInt::get(IntPtrTy, Size); - Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); - Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/); - // Emit an add instruction. - Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); - continue; - } - // Convert to correct type. - if (Op->getType() != IntPtrTy) - Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); - if (Size != 1) { - // We'll let instcombine(mul) convert this to a shl if possible. - Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size), - GEP->getName()+".idx", isInBounds /*NUW*/); - } - - // Emit an add instruction. - Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); - } - return Result; -} - ///===---------------------------------------------------------------------===// /// Dbg Intrinsic utilities /// @@ -335,6 +287,10 @@ void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, /// llvm.dbg.value intrinsics. bool LowerDbgDeclare(Function &F); +/// Propagate dbg.value intrinsics through the newly inserted PHIs. +void insertDebugValuesForPHIs(BasicBlock *BB, + SmallVectorImpl<PHINode *> &InsertedPHIs); + /// Finds all intrinsics declaring local variables as living in the memory that /// 'V' points to. This may include a mix of dbg.declare and /// dbg.addr intrinsics. @@ -343,6 +299,9 @@ TinyPtrVector<DbgInfoIntrinsic *> FindDbgAddrUses(Value *V); /// Finds the llvm.dbg.value intrinsics describing a value. void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V); +/// Finds the debug info intrinsics describing a value. +void findDbgUsers(SmallVectorImpl<DbgInfoIntrinsic *> &DbgInsts, Value *V); + /// Replaces llvm.dbg.declare instruction when the address it /// describes is replaced with a new value. If Deref is true, an /// additional DW_OP_deref is prepended to the expression. If Offset @@ -357,7 +316,7 @@ bool replaceDbgDeclare(Value *Address, Value *NewAddress, /// 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. +/// llvm.dbg.declare is inserted immediately after AI. bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool DerefBefore, int Offset, bool DerefAfter); @@ -370,10 +329,27 @@ bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, int Offset = 0); -/// Assuming the instruction \p I is going to be deleted, attempt to salvage any -/// dbg.value intrinsics referring to \p I by rewriting its effect into a -/// DIExpression. -void salvageDebugInfo(Instruction &I); +/// Assuming the instruction \p I is going to be deleted, attempt to salvage +/// debug users of \p I by writing the effect of \p I in a DIExpression. +/// Returns true if any debug users were updated. +bool salvageDebugInfo(Instruction &I); + +/// Point debug users of \p From to \p To or salvage them. Use this function +/// only when replacing all uses of \p From with \p To, with a guarantee that +/// \p From is going to be deleted. +/// +/// Follow these rules to prevent use-before-def of \p To: +/// . If \p To is a linked Instruction, set \p DomPoint to \p To. +/// . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction +/// \p To will be inserted after. +/// . If \p To is not an Instruction (e.g a Constant), the choice of +/// \p DomPoint is arbitrary. Pick \p From for simplicity. +/// +/// If a debug user cannot be preserved without reordering variable updates or +/// introducing a use-before-def, it is either salvaged (\ref salvageDebugInfo) +/// or deleted. Returns true if any debug users were updated. +bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, + DominatorTree &DT); /// Remove all instructions from a basic block other than it's terminator /// and any present EH pad instructions. @@ -382,7 +358,8 @@ unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB); /// Insert an unreachable instruction before the specified /// instruction, making it and the rest of the code in the block dead. unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, - bool PreserveLCSSA = false); + bool PreserveLCSSA = false, + DeferredDominance *DDT = nullptr); /// Convert the CallInst to InvokeInst with the specified unwind edge basic /// block. This also splits the basic block where CI is located, because @@ -397,12 +374,13 @@ BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI, /// /// \param BB Block whose terminator will be replaced. Its terminator must /// have an unwind successor. -void removeUnwindEdge(BasicBlock *BB); +void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = nullptr); /// Remove all blocks that can not be reached from the function's entry. /// /// Returns true if any basic block was removed. -bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr); +bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr, + DeferredDominance *DDT = nullptr); /// Combine the metadata of two instructions so that K can replace J /// diff --git a/include/llvm/Transforms/Utils/LoopRotationUtils.h b/include/llvm/Transforms/Utils/LoopRotationUtils.h new file mode 100644 index 000000000000..231e5bbb6dee --- /dev/null +++ b/include/llvm/Transforms/Utils/LoopRotationUtils.h @@ -0,0 +1,40 @@ +//===- LoopRotationUtils.h - Utilities to perform loop rotation -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides utilities to convert a loop into a loop with bottom test. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOOPROTATIONUTILS_H +#define LLVM_TRANSFORMS_UTILS_LOOPROTATIONUTILS_H + +namespace llvm { + +class AssumptionCache; +class DominatorTree; +class Loop; +class LoopInfo; +class ScalarEvolution; +struct SimplifyQuery; +class TargetTransformInfo; + +/// Convert a loop into a loop with bottom test. It may +/// perform loop latch simplication as well if the flag RotationOnly +/// is false. The flag Threshold represents the size threshold of the loop +/// header. If the loop header's size exceeds the threshold, the loop rotation +/// will give up. The flag IsUtilMode controls the heuristic used in the +/// LoopRotation. If it is true, the profitability heuristic will be ignored. +bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, + AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, + const SimplifyQuery &SQ, bool RotationOnly, + unsigned Threshold, bool IsUtilMode); + +} // namespace llvm + +#endif diff --git a/include/llvm/Transforms/Utils/LoopSimplify.h b/include/llvm/Transforms/Utils/LoopSimplify.h index f3828bc16e2f..166da2738ffd 100644 --- a/include/llvm/Transforms/Utils/LoopSimplify.h +++ b/include/llvm/Transforms/Utils/LoopSimplify.h @@ -52,7 +52,7 @@ public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -/// \brief Simplify each loop in a loop nest recursively. +/// 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 diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 750666136507..eb4c99102a63 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -21,7 +21,9 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/DemandedBits.h" #include "llvm/Analysis/EHPersonalities.h" +#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" @@ -46,17 +48,6 @@ class SCEV; class TargetLibraryInfo; class TargetTransformInfo; -/// \brief Captures loop safety information. -/// It keep information for loop & its header may throw exception. -struct LoopSafetyInfo { - bool MayThrow = false; // The current loop contains an instruction which - // may throw. - bool HeaderMayThrow = false; // Same as previous, but specific to loop header - // Used to update funclet bundle operands. - DenseMap<BasicBlock *, ColorVector> BlockColors; - - LoopSafetyInfo() = default; -}; /// The RecurrenceDescriptor is used to identify recurrences variables in a /// loop. Reduction is a special case of recurrence that has uses of the @@ -172,15 +163,25 @@ public: Value *Left, Value *Right); /// Returns true if Phi is a reduction of type Kind and adds it to the - /// RecurrenceDescriptor. + /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are + /// non-null, the minimal bit width needed to compute the reduction will be + /// computed. static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, bool HasFunNoNaNAttr, - RecurrenceDescriptor &RedDes); - - /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is - /// returned in RedDes. + RecurrenceDescriptor &RedDes, + DemandedBits *DB = nullptr, + AssumptionCache *AC = nullptr, + DominatorTree *DT = nullptr); + + /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor + /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are + /// non-null, the minimal bit width needed to compute the reduction will be + /// computed. static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, - RecurrenceDescriptor &RedDes); + RecurrenceDescriptor &RedDes, + DemandedBits *DB = nullptr, + AssumptionCache *AC = nullptr, + DominatorTree *DT = nullptr); /// Returns true if Phi is a first-order recurrence. A first-order recurrence /// is a non-reduction recurrence relation in which the value of the @@ -218,24 +219,6 @@ public: /// 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; } @@ -306,16 +289,16 @@ 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. If the def-use chain + /// 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 + 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 + /// If \p Phi is an induction, the induction descriptor \p D will contain /// the data describing this induction. static bool isFPInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, InductionDescriptor &D); @@ -351,11 +334,11 @@ public: Instruction::BinaryOpsEnd; } - /// Returns a reference to the type cast instructions in the induction + /// 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; + const SmallVectorImpl<Instruction *> &getCastInsts() const { + return RedundantCasts; } private: @@ -402,7 +385,7 @@ bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, DominatorTree &DT, LoopInfo &LI); -/// \brief Put loop into LCSSA form. +/// Put loop into LCSSA form. /// /// Looks at all instructions in the loop which have uses outside of the /// current loop. For each, an LCSSA PHI node is inserted and the uses outside @@ -415,7 +398,7 @@ bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, /// Returns true if any modifications are made to the loop. bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); -/// \brief Put a loop nest into LCSSA form. +/// Put a loop nest into LCSSA form. /// /// This recursively forms LCSSA for a loop nest. /// @@ -427,7 +410,7 @@ bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); -/// \brief Walk the specified region of the CFG (defined by all blocks +/// Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in /// reverse depth first order w.r.t the DominatorTree. This allows us to visit /// uses before definitions, allowing us to sink a loop body in one pass without @@ -440,7 +423,7 @@ bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); -/// \brief Walk the specified region of the CFG (defined by all blocks +/// Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth /// first order w.r.t the DominatorTree. This allows us to visit definitions /// before uses, allowing us to hoist a loop body in one pass without iteration. @@ -466,7 +449,7 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI); -/// \brief Try to promote memory values to scalars by sinking stores out of +/// Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over /// the stores in the loop, looking for stores to Must pointers which are /// loop invariant. It takes a set of must-alias values, Loop exit blocks @@ -487,22 +470,10 @@ bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &, 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. -/// Updates safety information in LoopSafetyInfo argument. -void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); - -/// Returns true if the instruction in a loop is guaranteed to execute at least -/// once. -bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, - const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo); - -/// \brief Returns the instructions that use values defined in the loop. +/// Returns the instructions that use values defined in the loop. SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); -/// \brief Find string metadata for loop +/// Find string metadata for loop /// /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an /// operand or null otherwise. If the string metadata is not found return @@ -510,11 +481,11 @@ SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop, StringRef Name); -/// \brief Set input string into loop metadata by keeping other values intact. +/// Set input string into loop metadata by keeping other values intact. void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V = 0); -/// \brief Get a loop's estimated trip count based on branch weight metadata. +/// Get a loop's estimated trip count based on branch weight metadata. /// Returns 0 when the count is estimated to be 0, or None when a meaningful /// estimate can not be made. Optional<unsigned> getLoopEstimatedTripCount(Loop *L); @@ -538,11 +509,18 @@ bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE = nullptr); +/// Generates an ordered vector reduction using extracts to reduce the value. +Value * +getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, + RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind = + RecurrenceDescriptor::MRK_Invalid, + ArrayRef<Value *> RedOps = None); + /// Generates a vector reduction using shufflevectors to reduce the value. Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind = RecurrenceDescriptor::MRK_Invalid, - ArrayRef<Value *> RedOps = ArrayRef<Value *>()); + ArrayRef<Value *> RedOps = None); /// Create a target reduction of the given vector. The reduction operation /// is described by the \p Opcode parameter. min/max reductions require @@ -554,7 +532,7 @@ createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags = TargetTransformInfo::ReductionFlags(), - ArrayRef<Value *> RedOps = ArrayRef<Value *>()); + ArrayRef<Value *> RedOps = None); /// Create a generic target reduction using a recurrence descriptor \p Desc /// The target is queried to determine if intrinsics or shuffle sequences are diff --git a/include/llvm/Transforms/Utils/LoopVersioning.h b/include/llvm/Transforms/Utils/LoopVersioning.h index fa5d7845d080..fcd734b37a1f 100644 --- a/include/llvm/Transforms/Utils/LoopVersioning.h +++ b/include/llvm/Transforms/Utils/LoopVersioning.h @@ -28,14 +28,14 @@ class LoopAccessInfo; class LoopInfo; class ScalarEvolution; -/// \brief This class emits a version of the loop where run-time checks ensure +/// This class emits a version of the loop where run-time checks ensure /// that may-alias pointers can't overlap. /// /// It currently only supports single-exit loops and assumes that the loop /// already has a preheader. class LoopVersioning { public: - /// \brief Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input. + /// 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. @@ -43,7 +43,7 @@ public: DominatorTree *DT, ScalarEvolution *SE, bool UseLAIChecks = true); - /// \brief Performs the CFG manipulation part of versioning the loop including + /// Performs the CFG manipulation part of versioning the loop including /// the DominatorTree and LoopInfo updates. /// /// The loop that was used to construct the class will be the "versioned" loop @@ -58,38 +58,38 @@ public: /// transform L void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); } - /// \brief Same but if the client has already precomputed the set of values + /// 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 + /// Returns the versioned loop. Control flows here if pointers in the /// loop don't alias (i.e. all memchecks passed). (This loop is actually the /// same as the original loop that we got constructed with.) Loop *getVersionedLoop() { return VersionedLoop; } - /// \brief Returns the fall-back loop. Control flows here if pointers in the + /// Returns the fall-back loop. Control flows here if pointers in the /// loop may alias (i.e. one of the memchecks failed). Loop *getNonVersionedLoop() { return NonVersionedLoop; } - /// \brief Sets the runtime alias checks for versioning the loop. + /// Sets the runtime alias checks for versioning the loop. void setAliasChecks( SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks); - /// \brief Sets the runtime SCEV checks for versioning the loop. + /// Sets the runtime SCEV checks for versioning the loop. void setSCEVChecks(SCEVUnionPredicate Check); - /// \brief Annotate memory instructions in the versioned loop with no-alias + /// Annotate memory instructions in the versioned loop with no-alias /// metadata based on the memchecks issued. /// /// This is just wrapper that calls prepareNoAliasMetadata and /// annotateInstWithNoAlias on the instructions of the versioned loop. void annotateLoopWithNoAlias(); - /// \brief Set up the aliasing scopes based on the memchecks. This needs to + /// Set up the aliasing scopes based on the memchecks. This needs to /// be called before the first call to annotateInstWithNoAlias. void prepareNoAliasMetadata(); - /// \brief Add the noalias annotations to \p VersionedInst. + /// Add the noalias annotations to \p VersionedInst. /// /// \p OrigInst is the instruction corresponding to \p VersionedInst in the /// original loop. Initialize the aliasing scopes with @@ -98,50 +98,50 @@ public: const Instruction *OrigInst); private: - /// \brief Adds the necessary PHI nodes for the versioned loops based on the + /// 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 Add the noalias annotations to \p I. Initialize the aliasing + /// Add the noalias annotations to \p I. Initialize the aliasing /// scopes with prepareNoAliasMetadata once before this can be called. void annotateInstWithNoAlias(Instruction *I) { annotateInstWithNoAlias(I, I); } - /// \brief The original loop. This becomes the "versioned" one. I.e., + /// The original loop. This becomes the "versioned" one. I.e., /// control flows here if pointers in the loop don't alias. Loop *VersionedLoop; - /// \brief The fall-back loop. I.e. control flows here if pointers in the + /// The fall-back loop. I.e. control flows here if pointers in the /// loop may alias (memchecks failed). Loop *NonVersionedLoop; - /// \brief This maps the instructions from VersionedLoop to their counterpart + /// This maps the instructions from VersionedLoop to their counterpart /// in NonVersionedLoop. ValueToValueMapTy VMap; - /// \brief The set of alias checks that we are versioning for. + /// 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. + /// The set of SCEV checks that we are versioning for. SCEVUnionPredicate Preds; - /// \brief Maps a pointer to the pointer checking group that the pointer + /// Maps a pointer to the pointer checking group that the pointer /// belongs to. DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *> PtrToGroup; - /// \brief The alias scope corresponding to a pointer checking group. + /// The alias scope corresponding to a pointer checking group. DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> GroupToScope; - /// \brief The list of alias scopes that a pointer checking group can't alias. + /// The list of alias scopes that a pointer checking group can't alias. DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *> GroupToNonAliasingScopeList; - /// \brief Analyses used. + /// Analyses used. const LoopAccessInfo &LAI; LoopInfo *LI; DominatorTree *DT; diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h index 4b9bc8293810..14615c25d093 100644 --- a/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/include/llvm/Transforms/Utils/ModuleUtils.h @@ -49,7 +49,7 @@ Function *checkSanitizerInterfaceFunction(Constant *FuncOrBitcast); Function *declareSanitizerInitFunction(Module &M, StringRef InitName, ArrayRef<Type *> InitArgTypes); -/// \brief Creates sanitizer constructor function, and calls sanitizer's init +/// Creates sanitizer constructor function, and calls sanitizer's init /// function from it. /// \return Returns pair of pointers to constructor, and init functions /// respectively. @@ -62,10 +62,10 @@ std::pair<Function *, Function *> createSanitizerCtorAndInitFunctions( /// the list of public globals in the module. bool nameUnamedGlobals(Module &M); -/// \brief Adds global values to the llvm.used list. +/// Adds global values to the llvm.used list. void appendToUsed(Module &M, ArrayRef<GlobalValue *> Values); -/// \brief Adds global values to the llvm.compiler.used list. +/// Adds global values to the llvm.compiler.used list. void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values); /// Filter out potentially dead comdat functions where other entries keep the @@ -84,7 +84,7 @@ void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values); void filterDeadComdatFunctions( Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions); -/// \brief Produce a unique identifier for this module by taking the MD5 sum of +/// Produce a unique identifier for this module by taking the MD5 sum of /// the names of the module's strong external symbols that are not comdat /// members. /// diff --git a/include/llvm/Transforms/Utils/OrderedInstructions.h b/include/llvm/Transforms/Utils/OrderedInstructions.h index 165d4bdaa6d4..7f57fde638b8 100644 --- a/include/llvm/Transforms/Utils/OrderedInstructions.h +++ b/include/llvm/Transforms/Utils/OrderedInstructions.h @@ -35,6 +35,11 @@ class OrderedInstructions { /// The dominator tree of the parent function. DominatorTree *DT; + /// Return true if the first instruction comes before the second in the + /// same basic block. It will create an ordered basic block, if it does + /// not yet exist in OBBMap. + bool localDominates(const Instruction *, const Instruction *) const; + public: /// Constructor. OrderedInstructions(DominatorTree *DT) : DT(DT) {} @@ -42,6 +47,12 @@ public: /// Return true if first instruction dominates the second. bool dominates(const Instruction *, const Instruction *) const; + /// Return true if the first instruction comes before the second in the + /// dominator tree DFS traversal if they are in different basic blocks, + /// or if the first instruction comes before the second in the same basic + /// block. + bool dfsBefore(const Instruction *, const Instruction *) const; + /// Invalidate the OrderedBasicBlock cache when its basic block changes. /// i.e. If an instruction is deleted or added to the basic block, the user /// should call this function to invalidate the OrderedBasicBlock cache for diff --git a/include/llvm/Transforms/Utils/PredicateInfo.h b/include/llvm/Transforms/Utils/PredicateInfo.h index 8150f1528397..b53eda7e5a42 100644 --- a/include/llvm/Transforms/Utils/PredicateInfo.h +++ b/include/llvm/Transforms/Utils/PredicateInfo.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// /// /// \file -/// \brief This file implements the PredicateInfo analysis, which creates an Extended +/// This file implements the PredicateInfo analysis, which creates an Extended /// SSA form for operations used in branch comparisons and llvm.assume /// comparisons. /// @@ -31,7 +31,7 @@ /// %cmp = icmp eq i32, %x, 50 /// br i1 %cmp, label %true, label %false /// true: -/// %x.0 = call @llvm.ssa_copy.i32(i32 %x) +/// %x.0 = call \@llvm.ssa_copy.i32(i32 %x) /// ret i32 %x.0 /// false: /// ret i32 1 @@ -54,6 +54,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" @@ -69,6 +70,7 @@ #include "llvm/IR/Use.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" #include "llvm/PassAnalysisSupport.h" #include "llvm/Support/Casting.h" @@ -193,7 +195,7 @@ namespace PredicateInfoClasses { struct ValueDFS; } -/// \brief Encapsulates PredicateInfo, including all data associated with memory +/// Encapsulates PredicateInfo, including all data associated with memory /// accesses. class PredicateInfo { private: @@ -261,6 +263,8 @@ private: // The set of edges along which we can only handle phi uses, due to critical // edges. DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly; + // The set of ssa_copy declarations we created with our custom mangling. + SmallSet<AssertingVH<Function>, 20> CreatedDeclarations; }; // This pass does eager building and then printing of PredicateInfo. It is used @@ -275,7 +279,7 @@ public: void getAnalysisUsage(AnalysisUsage &AU) const override; }; -/// \brief Printer pass for \c PredicateInfo. +/// Printer pass for \c PredicateInfo. class PredicateInfoPrinterPass : public PassInfoMixin<PredicateInfoPrinterPass> { raw_ostream &OS; @@ -285,7 +289,7 @@ public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -/// \brief Verifier pass for \c PredicateInfo. +/// Verifier pass for \c PredicateInfo. struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> { PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h index bb8a61a474f2..5ddfbe2bf058 100644 --- a/include/llvm/Transforms/Utils/PromoteMemToReg.h +++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h @@ -23,7 +23,7 @@ class DominatorTree; class AliasSetTracker; class AssumptionCache; -/// \brief Return true if this alloca is legal for promotion. +/// Return true if this alloca is legal for promotion. /// /// This is true if there are only loads, stores, and lifetime markers /// (transitively) using this alloca. This also enforces that there is only @@ -31,7 +31,7 @@ class AssumptionCache; /// markers. bool isAllocaPromotable(const AllocaInst *AI); -/// \brief Promote the specified list of alloca instructions into scalar +/// Promote the specified list of alloca instructions into scalar /// registers, inserting PHI nodes as appropriate. /// /// This function makes use of DominanceFrontier information. This function diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 6cd9f1539b0b..4a7911662990 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -30,7 +30,7 @@ class Type; class Use; class Value; -/// \brief Helper class for SSA formation on a set of values defined in +/// Helper class for SSA formation on a set of values defined in /// multiple blocks. /// /// This is used when code duplication or another unstructured @@ -62,25 +62,25 @@ public: SSAUpdater &operator=(const SSAUpdater &) = delete; ~SSAUpdater(); - /// \brief Reset this object to get ready for a new set of SSA updates with + /// Reset this object to get ready for a new set of SSA updates with /// type 'Ty'. /// /// PHI nodes get a name based on 'Name'. void Initialize(Type *Ty, StringRef Name); - /// \brief Indicate that a rewritten value is available in the specified block + /// Indicate that a rewritten value is available in the specified block /// with the specified value. void AddAvailableValue(BasicBlock *BB, Value *V); - /// \brief Return true if the SSAUpdater already has a value for the specified + /// Return true if the SSAUpdater already has a value for the specified /// block. bool HasValueForBlock(BasicBlock *BB) const; - /// \brief Construct SSA form, materializing a value that is live at the end + /// Construct SSA form, materializing a value that is live at the end /// of the specified block. Value *GetValueAtEndOfBlock(BasicBlock *BB); - /// \brief Construct SSA form, materializing a value that is live in the + /// Construct SSA form, materializing a value that is live in the /// middle of the specified block. /// /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except @@ -102,7 +102,7 @@ public: /// merge the appropriate values, and this value isn't live out of the block. Value *GetValueInMiddleOfBlock(BasicBlock *BB); - /// \brief Rewrite a use of the symbolic value. + /// Rewrite a use of the symbolic value. /// /// This handles PHI nodes, which use their value in the corresponding /// predecessor. Note that this will not work if the use is supposed to be @@ -111,7 +111,7 @@ public: /// be below it. void RewriteUse(Use &U); - /// \brief Rewrite a use like \c RewriteUse but handling in-block definitions. + /// Rewrite a use like \c RewriteUse but handling in-block definitions. /// /// This version of the method can rewrite uses in the same block as /// a definition, because it assumes that all uses of a value are below any @@ -122,7 +122,7 @@ private: Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); }; -/// \brief Helper class for promoting a collection of loads and stores into SSA +/// Helper class for promoting a collection of loads and stores into SSA /// Form using the SSAUpdater. /// /// This handles complexities that SSAUpdater doesn't, such as multiple loads @@ -139,32 +139,32 @@ public: SSAUpdater &S, StringRef Name = StringRef()); virtual ~LoadAndStorePromoter() = default; - /// \brief This does the promotion. + /// This does the promotion. /// /// Insts is a list of loads and stores to promote, and Name is the basename /// for the PHIs to insert. After this is complete, the loads and stores are /// removed from the code. void run(const SmallVectorImpl<Instruction *> &Insts) const; - /// \brief Return true if the specified instruction is in the Inst list. + /// 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; - /// \brief This hook is invoked after all the stores are found and inserted as + /// This hook is invoked after all the stores are found and inserted as /// available values. virtual void doExtraRewritesBeforeFinalDeletion() const {} - /// \brief Clients can choose to implement this to get notified right before + /// 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 {} - /// \brief Called before each instruction is deleted. + /// Called before each instruction is deleted. virtual void instructionDeleted(Instruction *I) const {} - /// \brief Called to update debug info associated with the instruction. + /// Called to update debug info associated with the instruction. virtual void updateDebugInfo(Instruction *I) const {} }; diff --git a/include/llvm/Transforms/Utils/SSAUpdaterBulk.h b/include/llvm/Transforms/Utils/SSAUpdaterBulk.h new file mode 100644 index 000000000000..53a608f01804 --- /dev/null +++ b/include/llvm/Transforms/Utils/SSAUpdaterBulk.h @@ -0,0 +1,92 @@ +//===- SSAUpdaterBulk.h - Unstructured SSA Update Tool ----------*- 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 the SSAUpdaterBulk class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/IR/PredIteratorCache.h" + +namespace llvm { + +class BasicBlock; +class PHINode; +template <typename T> class SmallVectorImpl; +class Type; +class Use; +class Value; +class DominatorTree; + +/// Helper class for SSA formation on a set of values defined in multiple +/// blocks. +/// +/// This is used when code duplication or another unstructured transformation +/// wants to rewrite a set of uses of one value with uses of a set of values. +/// The update is done only when RewriteAllUses is called, all other methods are +/// used for book-keeping. That helps to share some common computations between +/// updates of different uses (which is not the case when traditional SSAUpdater +/// is used). +class SSAUpdaterBulk { + struct RewriteInfo { + DenseMap<BasicBlock *, Value *> Defines; + SmallVector<Use *, 4> Uses; + StringRef Name; + Type *Ty; + RewriteInfo(){}; + RewriteInfo(StringRef &N, Type *T) : Name(N), Ty(T){}; + }; + SmallVector<RewriteInfo, 4> Rewrites; + + PredIteratorCache PredCache; + + Value *computeValueAt(BasicBlock *BB, RewriteInfo &R, DominatorTree *DT); + +public: + explicit SSAUpdaterBulk(){}; + SSAUpdaterBulk(const SSAUpdaterBulk &) = delete; + SSAUpdaterBulk &operator=(const SSAUpdaterBulk &) = delete; + ~SSAUpdaterBulk(){}; + + /// Add a new variable to the SSA rewriter. This needs to be called before + /// AddAvailableValue or AddUse calls. The return value is the variable ID, + /// which needs to be passed to AddAvailableValue and AddUse. + unsigned AddVariable(StringRef Name, Type *Ty); + + /// Indicate that a rewritten value is available in the specified block with + /// the specified value. + void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V); + + /// Record a use of the symbolic value. This use will be updated with a + /// rewritten value when RewriteAllUses is called. + void AddUse(unsigned Var, Use *U); + + /// Return true if the SSAUpdater already has a value for the specified + /// variable in the specified block. + bool HasValueForBlock(unsigned Var, BasicBlock *BB); + + /// Perform all the necessary updates, including new PHI-nodes insertion and + /// the requested uses update. + /// + /// The function requires dominator tree DT, which is used for computing + /// locations for new phi-nodes insertions. If a nonnull pointer to a vector + /// InsertedPHIs is passed, all the new phi-nodes will be added to this + /// vector. + void RewriteAllUses(DominatorTree *DT, + SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h index b1611d49a456..b7649ba88334 100644 --- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -379,7 +379,7 @@ public: Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred); } - DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n"); + LLVM_DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n"); // If the client wants to know about all new instructions, tell it. if (InsertedPHIs) InsertedPHIs->push_back(PHI); @@ -389,12 +389,8 @@ public: /// FindExistingPHI - Look through the PHI nodes in a block to see if any of /// them match what is needed. void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) { - for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end(); - BBI != BBE; ++BBI) { - PhiT *SomePHI = Traits::InstrIsPHI(&*BBI); - if (!SomePHI) - break; - if (CheckIfPHIMatches(SomePHI)) { + for (auto &SomePHI : BB->phis()) { + if (CheckIfPHIMatches(&SomePHI)) { RecordMatchingPHIs(BlockList); break; } diff --git a/include/llvm/Transforms/Utils/SimplifyInstructions.h b/include/llvm/Transforms/Utils/SimplifyInstructions.h deleted file mode 100644 index 3f838611626f..000000000000 --- a/include/llvm/Transforms/Utils/SimplifyInstructions.h +++ /dev/null @@ -1,31 +0,0 @@ -//===- SimplifyInstructions.h - Remove redundant instructions ---*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This is a utility pass used for testing the InstructionSimplify analysis. -// The analysis is applied to every instruction, and if it simplifies then the -// instruction is replaced by the simplification. If you are looking for a pass -// that performs serious instruction folding, use the instcombine pass instead. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H -#define LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H - -#include "llvm/IR/PassManager.h" - -namespace llvm { - -/// This pass removes redundant instructions. -class InstSimplifierPass : public PassInfoMixin<InstSimplifierPass> { -public: - PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); -}; -} // end namespace llvm - -#endif // LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h index 73a62f59203b..d007f909c6a4 100644 --- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -30,7 +30,7 @@ class BasicBlock; class Function; class OptimizationRemarkEmitter; -/// \brief This class implements simplifications for calls to fortified library +/// This class implements simplifications for calls to fortified library /// functions (__st*cpy_chk, __memcpy_chk, __memmove_chk, __memset_chk), to, /// when possible, replace them with their non-checking counterparts. /// Other optimizations can also be done, but it's possible to disable them and @@ -45,7 +45,7 @@ public: FortifiedLibCallSimplifier(const TargetLibraryInfo *TLI, bool OnlyLowerUnknownSize = false); - /// \brief Take the given call instruction and return a more + /// Take the given call instruction and return a more /// optimal value to replace the instruction with or 0 if a more /// optimal form can't be found. /// The call must not be an indirect call. @@ -60,7 +60,7 @@ private: Value *optimizeStrpCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func); Value *optimizeStrpNCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func); - /// \brief Checks whether the call \p CI to a fortified libcall is foldable + /// Checks whether the call \p CI to a fortified libcall is foldable /// to the non-fortified version. bool isFortifiedCallFoldable(CallInst *CI, unsigned ObjSizeOp, unsigned SizeOp, bool isString); @@ -78,13 +78,13 @@ private: bool UnsafeFPShrink; function_ref<void(Instruction *, Value *)> Replacer; - /// \brief Internal wrapper for RAUW that is the default implementation. + /// Internal wrapper for RAUW that is the default implementation. /// /// Other users may provide an alternate function with this signature instead /// of this one. static void replaceAllUsesWithDefault(Instruction *I, Value *With); - /// \brief Replace an instruction's uses with a value using our replacer. + /// Replace an instruction's uses with a value using our replacer. void replaceAllUsesWith(Instruction *I, Value *With); public: @@ -124,6 +124,7 @@ private: Value *optimizeMemCpy(CallInst *CI, IRBuilder<> &B); Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B); Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B); + Value *optimizeRealloc(CallInst *CI, IRBuilder<> &B); Value *optimizeWcslen(CallInst *CI, IRBuilder<> &B); // Wrapper for all String/Memory Library Call Optimizations Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B); @@ -150,15 +151,22 @@ private: Value *optimizeIsDigit(CallInst *CI, IRBuilder<> &B); Value *optimizeIsAscii(CallInst *CI, IRBuilder<> &B); Value *optimizeToAscii(CallInst *CI, IRBuilder<> &B); + Value *optimizeAtoi(CallInst *CI, IRBuilder<> &B); + Value *optimizeStrtol(CallInst *CI, IRBuilder<> &B); // Formatting and IO Library Call Optimizations Value *optimizeErrorReporting(CallInst *CI, IRBuilder<> &B, int StreamArg = -1); Value *optimizePrintF(CallInst *CI, IRBuilder<> &B); Value *optimizeSPrintF(CallInst *CI, IRBuilder<> &B); + Value *optimizeSnPrintF(CallInst *CI, IRBuilder<> &B); Value *optimizeFPrintF(CallInst *CI, IRBuilder<> &B); Value *optimizeFWrite(CallInst *CI, IRBuilder<> &B); + Value *optimizeFRead(CallInst *CI, IRBuilder<> &B); Value *optimizeFPuts(CallInst *CI, IRBuilder<> &B); + Value *optimizeFGets(CallInst *CI, IRBuilder<> &B); + Value *optimizeFPutc(CallInst *CI, IRBuilder<> &B); + Value *optimizeFGetc(CallInst *CI, IRBuilder<> &B); Value *optimizePuts(CallInst *CI, IRBuilder<> &B); // Helper methods @@ -169,6 +177,7 @@ private: SmallVectorImpl<CallInst *> &SinCosCalls); Value *optimizePrintFString(CallInst *CI, IRBuilder<> &B); Value *optimizeSPrintFString(CallInst *CI, IRBuilder<> &B); + Value *optimizeSnPrintFString(CallInst *CI, IRBuilder<> &B); Value *optimizeFPrintFString(CallInst *CI, IRBuilder<> &B); /// hasFloatVersion - Checks if there is a float version of the specified diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h index 12aa3bc6e770..a6b84af068a5 100644 --- a/include/llvm/Transforms/Utils/UnrollLoop.h +++ b/include/llvm/Transforms/Utils/UnrollLoop.h @@ -19,11 +19,13 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Transforms/Utils/ValueMapper.h" namespace llvm { class AssumptionCache; class BasicBlock; +class DependenceInfo; class DominatorTree; class Loop; class LoopInfo; @@ -71,13 +73,54 @@ bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP, - unsigned &TripCount); + unsigned &TripCount, ScalarEvolution &SE); + +bool canPeel(Loop *L); bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); +LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, + unsigned TripMultiple, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, + OptimizationRemarkEmitter *ORE); + +bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, + DependenceInfo &DI); + +bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, + DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, + const SmallPtrSetImpl<const Value *> &EphValues, + OptimizationRemarkEmitter *ORE, unsigned &TripCount, + unsigned MaxTripCount, unsigned &TripMultiple, + unsigned LoopSize, + TargetTransformInfo::UnrollingPreferences &UP, + bool &UseUpperBound); + +BasicBlock *foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT); + +void remapInstruction(Instruction *I, ValueToValueMapTy &VMap); + +void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC); + MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); +TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( + Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel, + Optional<unsigned> UserThreshold, Optional<unsigned> UserCount, + Optional<bool> UserAllowPartial, Optional<bool> UserRuntime, + Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling); + +unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, + bool &NotDuplicatable, bool &Convergent, + const TargetTransformInfo &TTI, + const SmallPtrSetImpl<const Value *> &EphValues, + unsigned BEInsns); + } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H diff --git a/include/llvm/Transforms/Vectorize.h b/include/llvm/Transforms/Vectorize.h index 19845e471e48..950af7ffe05f 100644 --- a/include/llvm/Transforms/Vectorize.h +++ b/include/llvm/Transforms/Vectorize.h @@ -21,88 +21,88 @@ class BasicBlockPass; class Pass; //===----------------------------------------------------------------------===// -/// @brief Vectorize configuration. +/// Vectorize configuration. struct VectorizeConfig { //===--------------------------------------------------------------------===// // Target architecture related parameters - /// @brief The size of the native vector registers. + /// The size of the native vector registers. unsigned VectorBits; - /// @brief Vectorize boolean values. + /// Vectorize boolean values. bool VectorizeBools; - /// @brief Vectorize integer values. + /// Vectorize integer values. bool VectorizeInts; - /// @brief Vectorize floating-point values. + /// Vectorize floating-point values. bool VectorizeFloats; - /// @brief Vectorize pointer values. + /// Vectorize pointer values. bool VectorizePointers; - /// @brief Vectorize casting (conversion) operations. + /// Vectorize casting (conversion) operations. bool VectorizeCasts; - /// @brief Vectorize floating-point math intrinsics. + /// Vectorize floating-point math intrinsics. bool VectorizeMath; - /// @brief Vectorize bit intrinsics. + /// Vectorize bit intrinsics. bool VectorizeBitManipulations; - /// @brief Vectorize the fused-multiply-add intrinsic. + /// Vectorize the fused-multiply-add intrinsic. bool VectorizeFMA; - /// @brief Vectorize select instructions. + /// Vectorize select instructions. bool VectorizeSelect; - /// @brief Vectorize comparison instructions. + /// Vectorize comparison instructions. bool VectorizeCmp; - /// @brief Vectorize getelementptr instructions. + /// Vectorize getelementptr instructions. bool VectorizeGEP; - /// @brief Vectorize loads and stores. + /// Vectorize loads and stores. bool VectorizeMemOps; - /// @brief Only generate aligned loads and stores. + /// Only generate aligned loads and stores. bool AlignedOnly; //===--------------------------------------------------------------------===// // Misc parameters - /// @brief The required chain depth for vectorization. + /// The required chain depth for vectorization. unsigned ReqChainDepth; - /// @brief The maximum search distance for instruction pairs. + /// The maximum search distance for instruction pairs. unsigned SearchLimit; - /// @brief The maximum number of candidate pairs with which to use a full + /// The maximum number of candidate pairs with which to use a full /// cycle check. unsigned MaxCandPairsForCycleCheck; - /// @brief Replicating one element to a pair breaks the chain. + /// Replicating one element to a pair breaks the chain. bool SplatBreaksChain; - /// @brief The maximum number of pairable instructions per group. + /// The maximum number of pairable instructions per group. unsigned MaxInsts; - /// @brief The maximum number of candidate instruction pairs per group. + /// The maximum number of candidate instruction pairs per group. unsigned MaxPairs; - /// @brief The maximum number of pairing iterations. + /// The maximum number of pairing iterations. unsigned MaxIter; - /// @brief Don't try to form odd-length vectors. + /// Don't try to form odd-length vectors. bool Pow2LenOnly; - /// @brief Don't boost the chain-depth contribution of loads and stores. + /// Don't boost the chain-depth contribution of loads and stores. bool NoMemOpBoost; - /// @brief Use a fast instruction dependency analysis. + /// Use a fast instruction dependency analysis. bool FastDep; - /// @brief Initialize the VectorizeConfig from command line options. + /// Initialize the VectorizeConfig from command line options. VectorizeConfig(); }; @@ -120,7 +120,7 @@ Pass *createLoopVectorizePass(bool NoUnrolling = false, Pass *createSLPVectorizerPass(); //===----------------------------------------------------------------------===// -/// @brief Vectorize the BasicBlock. +/// Vectorize the BasicBlock. /// /// @param BB The BasicBlock to be vectorized /// @param P The current running pass, should require AliasAnalysis and diff --git a/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h b/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h new file mode 100644 index 000000000000..224879cdba52 --- /dev/null +++ b/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h @@ -0,0 +1,482 @@ +//===- llvm/Transforms/Vectorize/LoopVectorizationLegality.h ----*- 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 defines the LoopVectorizationLegality class. Original code +/// in Loop Vectorizer has been moved out to its own file for modularity +/// and reusability. +/// +/// Currently, it works for innermost loop vectorization. Extending this to +/// outer loop vectorization is a TODO item. +/// +/// Also provides: +/// 1) LoopVectorizeHints class which keeps a number of loop annotations +/// locally for easy look up. It has the ability to write them back as +/// loop metadata, upon request. +/// 2) LoopVectorizationRequirements class for lazy bail out for the purpose +/// of reporting useful failure to vectorize message. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H +#define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H + +#include "llvm/ADT/MapVector.h" +#include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Transforms/Utils/LoopUtils.h" + +namespace llvm { + +/// Create an analysis remark that explains why vectorization failed +/// +/// \p PassName is the name of the pass (e.g. can be AlwaysPrint). \p +/// RemarkName is the identifier for the remark. If \p I is passed it is an +/// instruction that prevents vectorization. Otherwise \p TheLoop is used for +/// the location of the remark. \return the remark object that can be +/// streamed to. +OptimizationRemarkAnalysis createLVMissedAnalysis(const char *PassName, + StringRef RemarkName, + Loop *TheLoop, + Instruction *I = nullptr); + +/// Utility class for getting and setting loop vectorizer hints in the form +/// of loop metadata. +/// This class keeps a number of loop annotations locally (as member variables) +/// and can, upon request, write them back as metadata on the loop. It will +/// initially scan the loop for existing metadata, and will update the local +/// values based on information in the loop. +/// We cannot write all values to metadata, as the mere presence of some info, +/// for example 'force', means a decision has been made. So, we need to be +/// careful NOT to add them if the user hasn't specifically asked so. +class LoopVectorizeHints { + enum HintKind { HK_WIDTH, HK_UNROLL, HK_FORCE, HK_ISVECTORIZED }; + + /// Hint - associates name and validation with the hint value. + struct Hint { + const char *Name; + unsigned Value; // This may have to change for non-numeric values. + HintKind Kind; + + Hint(const char *Name, unsigned Value, HintKind Kind) + : Name(Name), Value(Value), Kind(Kind) {} + + bool validate(unsigned Val); + }; + + /// Vectorization width. + Hint Width; + + /// Vectorization interleave factor. + Hint Interleave; + + /// Vectorization forced + Hint Force; + + /// Already Vectorized + Hint IsVectorized; + + /// Return the loop metadata prefix. + static StringRef Prefix() { return "llvm.loop."; } + + /// True if there is any unsafe math in the loop. + bool PotentiallyUnsafe = false; + +public: + enum ForceKind { + FK_Undefined = -1, ///< Not selected. + FK_Disabled = 0, ///< Forcing disabled. + FK_Enabled = 1, ///< Forcing enabled. + }; + + LoopVectorizeHints(const Loop *L, bool DisableInterleaving, + OptimizationRemarkEmitter &ORE); + + /// Mark the loop L as already vectorized by setting the width to 1. + void setAlreadyVectorized() { + IsVectorized.Value = 1; + Hint Hints[] = {IsVectorized}; + writeHintsToMetadata(Hints); + } + + bool allowVectorization(Function *F, Loop *L, bool AlwaysVectorize) const; + + /// Dumps all the hint information. + void emitRemarkWithHints() const; + + unsigned getWidth() const { return Width.Value; } + unsigned getInterleave() const { return Interleave.Value; } + unsigned getIsVectorized() const { return IsVectorized.Value; } + enum ForceKind getForce() const { return (ForceKind)Force.Value; } + + /// If hints are provided that force vectorization, use the AlwaysPrint + /// pass name to force the frontend to print the diagnostic. + const char *vectorizeAnalysisPassName() const; + + bool allowReordering() const { + // When enabling loop hints are provided we allow the vectorizer to change + // the order of operations that is given by the scalar loop. This is not + // enabled by default because can be unsafe or inefficient. For example, + // reordering floating-point operations will change the way round-off + // error accumulates in the loop. + return getForce() == LoopVectorizeHints::FK_Enabled || getWidth() > 1; + } + + bool isPotentiallyUnsafe() const { + // Avoid FP vectorization if the target is unsure about proper support. + // This may be related to the SIMD unit in the target not handling + // IEEE 754 FP ops properly, or bad single-to-double promotions. + // Otherwise, a sequence of vectorized loops, even without reduction, + // could lead to different end results on the destination vectors. + return getForce() != LoopVectorizeHints::FK_Enabled && PotentiallyUnsafe; + } + + void setPotentiallyUnsafe() { PotentiallyUnsafe = true; } + +private: + /// Find hints specified in the loop metadata and update local values. + void getHintsFromMetadata(); + + /// Checks string hint with one operand and set value if valid. + void setHint(StringRef Name, Metadata *Arg); + + /// Create a new hint from name / value pair. + MDNode *createHintMetadata(StringRef Name, unsigned V) const; + + /// Matches metadata with hint name. + bool matchesHintMetadataName(MDNode *Node, ArrayRef<Hint> HintTypes); + + /// Sets current hints into loop metadata, keeping other values intact. + void writeHintsToMetadata(ArrayRef<Hint> HintTypes); + + /// The loop these hints belong to. + const Loop *TheLoop; + + /// Interface to emit optimization remarks. + OptimizationRemarkEmitter &ORE; +}; + +/// This holds vectorization requirements that must be verified late in +/// the process. The requirements are set by legalize and costmodel. Once +/// vectorization has been determined to be possible and profitable the +/// requirements can be verified by looking for metadata or compiler options. +/// For example, some loops require FP commutativity which is only allowed if +/// vectorization is explicitly specified or if the fast-math compiler option +/// has been provided. +/// Late evaluation of these requirements allows helpful diagnostics to be +/// composed that tells the user what need to be done to vectorize the loop. For +/// example, by specifying #pragma clang loop vectorize or -ffast-math. Late +/// evaluation should be used only when diagnostics can generated that can be +/// followed by a non-expert user. +class LoopVectorizationRequirements { +public: + LoopVectorizationRequirements(OptimizationRemarkEmitter &ORE) : ORE(ORE) {} + + void addUnsafeAlgebraInst(Instruction *I) { + // First unsafe algebra instruction. + if (!UnsafeAlgebraInst) + UnsafeAlgebraInst = I; + } + + void addRuntimePointerChecks(unsigned Num) { NumRuntimePointerChecks = Num; } + + bool doesNotMeet(Function *F, Loop *L, const LoopVectorizeHints &Hints); + +private: + unsigned NumRuntimePointerChecks = 0; + Instruction *UnsafeAlgebraInst = nullptr; + + /// Interface to emit optimization remarks. + OptimizationRemarkEmitter &ORE; +}; + +/// LoopVectorizationLegality checks if it is legal to vectorize a loop, and +/// to what vectorization factor. +/// This class does not look at the profitability of vectorization, only the +/// legality. This class has two main kinds of checks: +/// * Memory checks - The code in canVectorizeMemory checks if vectorization +/// will change the order of memory accesses in a way that will change the +/// correctness of the program. +/// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory +/// checks for a number of different conditions, such as the availability of a +/// single induction variable, that all types are supported and vectorize-able, +/// etc. This code reflects the capabilities of InnerLoopVectorizer. +/// This class is also used by InnerLoopVectorizer for identifying +/// induction variable and the different reduction variables. +class LoopVectorizationLegality { +public: + LoopVectorizationLegality( + Loop *L, PredicatedScalarEvolution &PSE, DominatorTree *DT, + TargetLibraryInfo *TLI, AliasAnalysis *AA, Function *F, + std::function<const LoopAccessInfo &(Loop &)> *GetLAA, LoopInfo *LI, + OptimizationRemarkEmitter *ORE, LoopVectorizationRequirements *R, + LoopVectorizeHints *H, DemandedBits *DB, AssumptionCache *AC) + : TheLoop(L), LI(LI), PSE(PSE), TLI(TLI), DT(DT), GetLAA(GetLAA), + ORE(ORE), Requirements(R), Hints(H), DB(DB), AC(AC) {} + + /// ReductionList contains the reduction descriptors for all + /// of the reductions that were found in the loop. + using ReductionList = DenseMap<PHINode *, RecurrenceDescriptor>; + + /// InductionList saves induction variables and maps them to the + /// induction descriptor. + using InductionList = MapVector<PHINode *, InductionDescriptor>; + + /// RecurrenceSet contains the phi nodes that are recurrences other than + /// inductions and reductions. + using RecurrenceSet = SmallPtrSet<const PHINode *, 8>; + + /// Returns true if it is legal to vectorize this loop. + /// This does not mean that it is profitable to vectorize this + /// loop, only that it is legal to do so. + /// Temporarily taking UseVPlanNativePath parameter. If true, take + /// the new code path being implemented for outer loop vectorization + /// (should be functional for inner loop vectorization) based on VPlan. + /// If false, good old LV code. + bool canVectorize(bool UseVPlanNativePath); + + /// Returns the primary induction variable. + PHINode *getPrimaryInduction() { return PrimaryInduction; } + + /// Returns the reduction variables found in the loop. + ReductionList *getReductionVars() { return &Reductions; } + + /// Returns the induction variables found in the loop. + InductionList *getInductionVars() { return &Inductions; } + + /// Return the first-order recurrences found in the loop. + RecurrenceSet *getFirstOrderRecurrences() { return &FirstOrderRecurrences; } + + /// Return the set of instructions to sink to handle first-order recurrences. + DenseMap<Instruction *, Instruction *> &getSinkAfter() { return SinkAfter; } + + /// Returns the widest induction type. + Type *getWidestInductionType() { return WidestIndTy; } + + /// Returns True if V is a Phi node of an induction variable in this loop. + bool isInductionPhi(const Value *V); + + /// Returns True if V is a cast that is part of an induction def-use chain, + /// and had been proven to be redundant under a runtime guard (in other + /// words, the cast has the same SCEV expression as the induction phi). + bool isCastedInductionVariable(const Value *V); + + /// Returns True if V can be considered as an induction variable in this + /// loop. V can be the induction phi, or some redundant cast in the def-use + /// chain of the inducion phi. + bool isInductionVariable(const Value *V); + + /// Returns True if PN is a reduction variable in this loop. + bool isReductionVariable(PHINode *PN) { return Reductions.count(PN); } + + /// Returns True if Phi is a first-order recurrence in this loop. + bool isFirstOrderRecurrence(const PHINode *Phi); + + /// Return true if the block BB needs to be predicated in order for the loop + /// to be vectorized. + bool blockNeedsPredication(BasicBlock *BB); + + /// Check if this pointer is consecutive when vectorizing. This happens + /// when the last index of the GEP is the induction variable, or that the + /// pointer itself is an induction variable. + /// This check allows us to vectorize A[idx] into a wide load/store. + /// Returns: + /// 0 - Stride is unknown or non-consecutive. + /// 1 - Address is consecutive. + /// -1 - Address is consecutive, and decreasing. + /// NOTE: This method must only be used before modifying the original scalar + /// loop. Do not use after invoking 'createVectorizedLoopSkeleton' (PR34965). + int isConsecutivePtr(Value *Ptr); + + /// Returns true if the value V is uniform within the loop. + bool isUniform(Value *V); + + /// Returns the information that we collected about runtime memory check. + const RuntimePointerChecking *getRuntimePointerChecking() const { + return LAI->getRuntimePointerChecking(); + } + + const LoopAccessInfo *getLAI() const { return LAI; } + + unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); } + + uint64_t getMaxSafeRegisterWidth() const { + return LAI->getDepChecker().getMaxSafeRegisterWidth(); + } + + bool hasStride(Value *V) { return LAI->hasStride(V); } + + /// Returns true if vector representation of the instruction \p I + /// requires mask. + bool isMaskRequired(const Instruction *I) { return (MaskedOp.count(I) != 0); } + + unsigned getNumStores() const { return LAI->getNumStores(); } + unsigned getNumLoads() const { return LAI->getNumLoads(); } + + // Returns true if the NoNaN attribute is set on the function. + bool hasFunNoNaNAttr() const { return HasFunNoNaNAttr; } + +private: + /// Return true if the pre-header, exiting and latch blocks of \p Lp and all + /// its nested loops are considered legal for vectorization. These legal + /// checks are common for inner and outer loop vectorization. + /// Temporarily taking UseVPlanNativePath parameter. If true, take + /// the new code path being implemented for outer loop vectorization + /// (should be functional for inner loop vectorization) based on VPlan. + /// If false, good old LV code. + bool canVectorizeLoopNestCFG(Loop *Lp, bool UseVPlanNativePath); + + /// Return true if the pre-header, exiting and latch blocks of \p Lp + /// (non-recursive) are considered legal for vectorization. + /// Temporarily taking UseVPlanNativePath parameter. If true, take + /// the new code path being implemented for outer loop vectorization + /// (should be functional for inner loop vectorization) based on VPlan. + /// If false, good old LV code. + bool canVectorizeLoopCFG(Loop *Lp, bool UseVPlanNativePath); + + /// Check if a single basic block loop is vectorizable. + /// At this point we know that this is a loop with a constant trip count + /// and we only need to check individual instructions. + bool canVectorizeInstrs(); + + /// When we vectorize loops we may change the order in which + /// we read and write from memory. This method checks if it is + /// legal to vectorize the code, considering only memory constrains. + /// Returns true if the loop is vectorizable + bool canVectorizeMemory(); + + /// Return true if we can vectorize this loop using the IF-conversion + /// transformation. + bool canVectorizeWithIfConvert(); + + /// Return true if we can vectorize this outer loop. The method performs + /// specific checks for outer loop vectorization. + bool canVectorizeOuterLoop(); + + /// Return true if all of the instructions in the block can be speculatively + /// executed. \p SafePtrs is a list of addresses that are known to be legal + /// and we know that we can read from them without segfault. + bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs); + + /// Updates the vectorization state by adding \p Phi to the inductions list. + /// This can set \p Phi as the main induction of the loop if \p Phi is a + /// better choice for the main induction than the existing one. + void addInductionPhi(PHINode *Phi, const InductionDescriptor &ID, + SmallPtrSetImpl<Value *> &AllowedExit); + + /// Create an analysis remark that explains why vectorization failed + /// + /// \p RemarkName is the identifier for the remark. If \p I is passed it is + /// an instruction that prevents vectorization. Otherwise the loop is used + /// for the location of the remark. \return the remark object that can be + /// streamed to. + OptimizationRemarkAnalysis + createMissedAnalysis(StringRef RemarkName, Instruction *I = nullptr) const { + return createLVMissedAnalysis(Hints->vectorizeAnalysisPassName(), + RemarkName, TheLoop, I); + } + + /// If an access has a symbolic strides, this maps the pointer value to + /// the stride symbol. + const ValueToValueMap *getSymbolicStrides() { + // FIXME: Currently, the set of symbolic strides is sometimes queried before + // it's collected. This happens from canVectorizeWithIfConvert, when the + // pointer is checked to reference consecutive elements suitable for a + // masked access. + return LAI ? &LAI->getSymbolicStrides() : nullptr; + } + + /// The loop that we evaluate. + Loop *TheLoop; + + /// Loop Info analysis. + LoopInfo *LI; + + /// A wrapper around ScalarEvolution used to add runtime SCEV checks. + /// Applies dynamic knowledge to simplify SCEV expressions in the context + /// of existing SCEV assumptions. The analysis will also add a minimal set + /// of new predicates if this is required to enable vectorization and + /// unrolling. + PredicatedScalarEvolution &PSE; + + /// Target Library Info. + TargetLibraryInfo *TLI; + + /// Dominator Tree. + DominatorTree *DT; + + // LoopAccess analysis. + std::function<const LoopAccessInfo &(Loop &)> *GetLAA; + + // And the loop-accesses info corresponding to this loop. This pointer is + // null until canVectorizeMemory sets it up. + const LoopAccessInfo *LAI = nullptr; + + /// Interface to emit optimization remarks. + OptimizationRemarkEmitter *ORE; + + // --- vectorization state --- // + + /// Holds the primary induction variable. This is the counter of the + /// loop. + PHINode *PrimaryInduction = nullptr; + + /// Holds the reduction variables. + ReductionList Reductions; + + /// Holds all of the induction variables that we found in the loop. + /// Notice that inductions don't need to start at zero and that induction + /// variables can be pointers. + InductionList Inductions; + + /// Holds all the casts that participate in the update chain of the induction + /// variables, and that have been proven to be redundant (possibly under a + /// runtime guard). These casts can be ignored when creating the vectorized + /// loop body. + SmallPtrSet<Instruction *, 4> InductionCastsToIgnore; + + /// Holds the phi nodes that are first-order recurrences. + RecurrenceSet FirstOrderRecurrences; + + /// Holds instructions that need to sink past other instructions to handle + /// first-order recurrences. + DenseMap<Instruction *, Instruction *> SinkAfter; + + /// Holds the widest induction type encountered. + Type *WidestIndTy = nullptr; + + /// Allowed outside users. This holds the induction and reduction + /// vars which can be accessed from outside the loop. + SmallPtrSet<Value *, 4> AllowedExit; + + /// Can we assume the absence of NaNs. + bool HasFunNoNaNAttr = false; + + /// Vectorization requirements that will go through late-evaluation. + LoopVectorizationRequirements *Requirements; + + /// Used to emit an analysis of any legality issues. + LoopVectorizeHints *Hints; + + /// The demanded bits analsyis is used to compute the minimum type size in + /// which a reduction can be computed. + DemandedBits *DB; + + /// The assumption cache analysis is used to compute the minimum type size in + /// which a reduction can be computed. + AssumptionCache *AC; + + /// While vectorizing these instructions we have to generate a + /// call to the appropriate masked intrinsic + SmallPtrSet<const Instruction *, 8> MaskedOp; +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H diff --git a/include/llvm/Transforms/Vectorize/LoopVectorize.h b/include/llvm/Transforms/Vectorize/LoopVectorize.h index 32b56d372ea1..d79d84691803 100644 --- a/include/llvm/Transforms/Vectorize/LoopVectorize.h +++ b/include/llvm/Transforms/Vectorize/LoopVectorize.h @@ -26,6 +26,14 @@ // of vectorization. It decides on the optimal vector width, which // can be one, if vectorization is not profitable. // +// There is a development effort going on to migrate loop vectorizer to the +// VPlan infrastructure and to introduce outer loop vectorization support (see +// docs/Proposal/VectorizationPlan.rst and +// http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html). For this +// purpose, we temporarily introduced the VPlan-native vectorization path: an +// alternative vectorization path that is natively implemented on top of the +// VPlan infrastructure. See EnableVPlanNativePath for enabling. +// //===----------------------------------------------------------------------===// // // The reduction-variable vectorization is based on the paper: diff --git a/include/llvm/Transforms/Vectorize/SLPVectorizer.h b/include/llvm/Transforms/Vectorize/SLPVectorizer.h index 25f264c4722c..3152e8192fc5 100644 --- a/include/llvm/Transforms/Vectorize/SLPVectorizer.h +++ b/include/llvm/Transforms/Vectorize/SLPVectorizer.h @@ -82,7 +82,7 @@ public: OptimizationRemarkEmitter *ORE_); private: - /// \brief Collect store and getelementptr instructions and organize them + /// Collect store and getelementptr instructions and organize them /// according to the underlying object of their pointer operands. We sort the /// instructions by their underlying objects to reduce the cost of /// consecutive access queries. @@ -91,26 +91,23 @@ private: /// every time we run into a memory barrier. void collectSeedInstructions(BasicBlock *BB); - /// \brief Try to vectorize a chain that starts at two arithmetic instrs. + /// Try to vectorize a chain that starts at two arithmetic instrs. bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R); - /// \brief Try to vectorize a list of operands. - /// \@param BuildVector A list of users to ignore for the purpose of - /// scheduling and cost estimation when NeedExtraction - /// is false. + /// Try to vectorize a list of operands. + /// \param UserCost Cost of the user operations of \p VL if they may affect + /// the cost of the vectorization. /// \returns true if a value was vectorized. bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, - ArrayRef<Value *> BuildVector = None, - bool AllowReorder = false, - bool NeedExtraction = false); + int UserCost = 0, bool AllowReorder = false); - /// \brief Try to vectorize a chain that may start at the operands of \p I. + /// Try to vectorize a chain that may start at the operands of \p I. bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R); - /// \brief Vectorize the store instructions collected in Stores. + /// Vectorize the store instructions collected in Stores. bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); - /// \brief Vectorize the index computations of the getelementptr instructions + /// Vectorize the index computations of the getelementptr instructions /// collected in GEPs. bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); @@ -136,7 +133,7 @@ private: bool vectorizeSimpleInstructions(SmallVectorImpl<WeakVH> &Instructions, BasicBlock *BB, slpvectorizer::BoUpSLP &R); - /// \brief Scan the basic block and look for patterns that are likely to start + /// Scan the basic block and look for patterns that are likely to start /// a vectorization chain. bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); |