diff options
Diffstat (limited to 'include/llvm/Transforms')
74 files changed, 1441 insertions, 602 deletions
diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h index 39ceb19525b3..ce20a726b783 100644 --- a/include/llvm/Transforms/IPO.h +++ b/include/llvm/Transforms/IPO.h @@ -216,6 +216,10 @@ ModulePass *createMetaRenamerPass(); /// manager. ModulePass *createBarrierNoopPass(); +/// createCalledValuePropagationPass - Attach metadata to indirct call sites +/// indicating the set of functions they may target at run-time. +ModulePass *createCalledValuePropagationPass(); + /// What to do with the summary when running passes that operate on it. enum class PassSummaryAction { None, ///< Do nothing. diff --git a/include/llvm/Transforms/IPO/ArgumentPromotion.h b/include/llvm/Transforms/IPO/ArgumentPromotion.h index 724ff72f3b5a..82ffc69a166e 100644 --- a/include/llvm/Transforms/IPO/ArgumentPromotion.h +++ b/include/llvm/Transforms/IPO/ArgumentPromotion.h @@ -12,6 +12,7 @@ #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/IR/PassManager.h" namespace llvm { @@ -26,6 +27,6 @@ public: LazyCallGraph &CG, CGSCCUpdateResult &UR); }; -} +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_IPO_ARGUMENTPROMOTION_H diff --git a/include/llvm/Transforms/IPO/CalledValuePropagation.h b/include/llvm/Transforms/IPO/CalledValuePropagation.h new file mode 100644 index 000000000000..352bdc7ac17f --- /dev/null +++ b/include/llvm/Transforms/IPO/CalledValuePropagation.h @@ -0,0 +1,35 @@ +//===- CalledValuePropagation.h - Propagate called values -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a transformation that attaches !callees metadata to +// indirect call sites. For a given call site, the metadata, if present, +// indicates the set of functions the call site could possibly target at +// run-time. This metadata is added to indirect call sites when the set of +// possible targets can be determined by analysis and is known to be small. The +// analysis driving the transformation is similar to constant propagation and +// makes uses of the generic sparse propagation solver. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H +#define LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class CalledValuePropagationPass + : public PassInfoMixin<CalledValuePropagationPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; +} // namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H diff --git a/include/llvm/Transforms/IPO/ConstantMerge.h b/include/llvm/Transforms/IPO/ConstantMerge.h index 1d4da43f6a7b..e04d3ae1a40e 100644 --- a/include/llvm/Transforms/IPO/ConstantMerge.h +++ b/include/llvm/Transforms/IPO/ConstantMerge.h @@ -20,16 +20,18 @@ #ifndef LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H #define LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Module; + /// A pass that merges duplicate global constants into a single constant. class ConstantMergePass : public PassInfoMixin<ConstantMergePass> { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H diff --git a/include/llvm/Transforms/IPO/DeadArgumentElimination.h b/include/llvm/Transforms/IPO/DeadArgumentElimination.h index e179afa956f6..ba5666f20a9b 100644 --- a/include/llvm/Transforms/IPO/DeadArgumentElimination.h +++ b/include/llvm/Transforms/IPO/DeadArgumentElimination.h @@ -20,15 +20,21 @@ #ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H #define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H -#include "llvm/IR/Module.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Twine.h" +#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" - #include <map> #include <set> #include <string> +#include <tuple> namespace llvm { +class Module; +class Use; +class Value; + /// Eliminate dead arguments (and return values) from functions. class DeadArgumentEliminationPass : public PassInfoMixin<DeadArgumentEliminationPass> { @@ -37,12 +43,13 @@ public: /// argument. Used so that arguments and return values can be used /// interchangeably. struct RetOrArg { - RetOrArg(const Function *F, unsigned Idx, bool IsArg) - : F(F), Idx(Idx), IsArg(IsArg) {} const Function *F; unsigned Idx; bool IsArg; + RetOrArg(const Function *F, unsigned Idx, bool IsArg) + : F(F), Idx(Idx), IsArg(IsArg) {} + /// Make RetOrArg comparable, so we can put it into a map. bool operator<(const RetOrArg &O) const { return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg); @@ -67,16 +74,23 @@ public: /// thus become dead in the end. enum Liveness { Live, MaybeLive }; + DeadArgumentEliminationPass(bool ShouldHackArguments_ = false) + : ShouldHackArguments(ShouldHackArguments_) {} + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); + /// Convenience wrapper RetOrArg CreateRet(const Function *F, unsigned Idx) { return RetOrArg(F, Idx, false); } + /// Convenience wrapper RetOrArg CreateArg(const Function *F, unsigned Idx) { return RetOrArg(F, Idx, true); } - typedef std::multimap<RetOrArg, RetOrArg> UseMap; + using UseMap = std::multimap<RetOrArg, RetOrArg>; + /// This maps a return value or argument to any MaybeLive return values or /// arguments it uses. This allows the MaybeLive values to be marked live /// when any of its users is marked live. @@ -93,25 +107,21 @@ public: /// directly to F. UseMap Uses; - typedef std::set<RetOrArg> LiveSet; - typedef std::set<const Function *> LiveFuncSet; + using LiveSet = std::set<RetOrArg>; + using LiveFuncSet = std::set<const Function *>; /// This set contains all values that have been determined to be live. LiveSet LiveValues; + /// This set contains all values that are cannot be changed in any way. LiveFuncSet LiveFunctions; - typedef SmallVector<RetOrArg, 5> UseVector; + using UseVector = SmallVector<RetOrArg, 5>; /// This allows this pass to do double-duty as the dead arg hacking pass /// (used only by bugpoint). bool ShouldHackArguments = false; -public: - DeadArgumentEliminationPass(bool ShouldHackArguments_ = false) - : ShouldHackArguments(ShouldHackArguments_) {} - PreservedAnalyses run(Module &M, ModuleAnalysisManager &); - private: Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses, @@ -128,6 +138,7 @@ private: bool DeleteDeadVarargs(Function &Fn); bool RemoveDeadArgumentsFromCallers(Function &Fn); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H diff --git a/include/llvm/Transforms/IPO/ElimAvailExtern.h b/include/llvm/Transforms/IPO/ElimAvailExtern.h index 88a0e9bd8ce0..94cb954fd2d5 100644 --- a/include/llvm/Transforms/IPO/ElimAvailExtern.h +++ b/include/llvm/Transforms/IPO/ElimAvailExtern.h @@ -15,17 +15,19 @@ #ifndef LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H #define LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Module; + /// A pass that transforms external global definitions into declarations. class EliminateAvailableExternallyPass : public PassInfoMixin<EliminateAvailableExternallyPass> { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H diff --git a/include/llvm/Transforms/IPO/FunctionAttrs.h b/include/llvm/Transforms/IPO/FunctionAttrs.h index 36dd06b85b41..dc9f18c79410 100644 --- a/include/llvm/Transforms/IPO/FunctionAttrs.h +++ b/include/llvm/Transforms/IPO/FunctionAttrs.h @@ -1,4 +1,4 @@ -//===-- FunctionAttrs.h - Compute function attrs --------------------------===// +//===- FunctionAttrs.h - Compute function attributes ------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,9 +6,11 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// Provides passes for computing function attributes based on interprocedural /// analyses. +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H @@ -21,6 +23,9 @@ namespace llvm { class AAResults; +class Function; +class Module; +class Pass; /// The three kinds of memory access relevant to 'readonly' and /// 'readnone' attributes. @@ -66,6 +71,7 @@ class ReversePostOrderFunctionAttrsPass public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h index de35cdf052e1..39e5b5c8ae6f 100644 --- a/include/llvm/Transforms/IPO/FunctionImport.h +++ b/include/llvm/Transforms/IPO/FunctionImport.h @@ -7,23 +7,26 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_FUNCTIONIMPORT_H -#define LLVM_FUNCTIONIMPORT_H +#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H +#define LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" #include "llvm/IR/GlobalValue.h" #include "llvm/IR/ModuleSummaryIndex.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/Error.h" - #include <functional> #include <map> +#include <memory> +#include <string> +#include <system_error> #include <unordered_set> #include <utility> namespace llvm { -class LLVMContext; -class GlobalValueSummary; + class Module; /// The function importer is automatically importing function from other modules @@ -34,19 +37,19 @@ public: /// 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. - typedef std::map<GlobalValue::GUID, unsigned> FunctionsToImportTy; + using FunctionsToImportTy = std::map<GlobalValue::GUID, unsigned>; /// 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 /// functions to import. - typedef StringMap<FunctionsToImportTy> ImportMapTy; + using ImportMapTy = StringMap<FunctionsToImportTy>; /// The set contains an entry for every global value the module exports. - typedef std::unordered_set<GlobalValue::GUID> ExportSetTy; + using ExportSetTy = std::unordered_set<GlobalValue::GUID>; /// A function of this type is used to load modules referenced by the index. - typedef std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)> - ModuleLoaderTy; + using ModuleLoaderTy = + std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>; /// Create a Function Importer. FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader) @@ -95,6 +98,15 @@ void ComputeCrossModuleImportForModule( StringRef ModulePath, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportList); +/// Mark all external summaries in \p Index for import into the given module. +/// Used for distributed builds using a distributed index. +/// +/// \p ImportList will be populated with a map that can be passed to +/// FunctionImporter::importFunctions() above (see description there). +void ComputeCrossModuleImportForModuleFromIndex( + StringRef ModulePath, const ModuleSummaryIndex &Index, + FunctionImporter::ImportMapTy &ImportList); + /// 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. @@ -132,6 +144,7 @@ void thinLTOResolveWeakForLinkerModule(Module &TheModule, /// during global summary-based analysis. void thinLTOInternalizeModule(Module &TheModule, const GVSummaryMapTy &DefinedGlobals); -} -#endif // LLVM_FUNCTIONIMPORT_H +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H diff --git a/include/llvm/Transforms/IPO/GlobalDCE.h b/include/llvm/Transforms/IPO/GlobalDCE.h index 9ca939c15b62..7ca241f4645a 100644 --- a/include/llvm/Transforms/IPO/GlobalDCE.h +++ b/include/llvm/Transforms/IPO/GlobalDCE.h @@ -35,7 +35,7 @@ private: SmallPtrSet<GlobalValue*, 32> AliveGlobals; /// Global -> Global that uses this global. - std::unordered_multimap<GlobalValue *, GlobalValue *> GVDependencies; + DenseMap<GlobalValue *, SmallPtrSet<GlobalValue *, 4>> GVDependencies; /// Constant -> Globals that use this global cache. std::unordered_map<Constant *, SmallPtrSet<GlobalValue *, 8>> diff --git a/include/llvm/Transforms/IPO/GlobalOpt.h b/include/llvm/Transforms/IPO/GlobalOpt.h index ab9116810be1..5b4878604eab 100644 --- a/include/llvm/Transforms/IPO/GlobalOpt.h +++ b/include/llvm/Transforms/IPO/GlobalOpt.h @@ -16,17 +16,18 @@ #ifndef LLVM_TRANSFORMS_IPO_GLOBALOPT_H #define LLVM_TRANSFORMS_IPO_GLOBALOPT_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Module; + /// Optimize globals that never have their address taken. class GlobalOptPass : public PassInfoMixin<GlobalOptPass> { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -} +} // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_GLOBALOPT_H diff --git a/include/llvm/Transforms/IPO/GlobalSplit.h b/include/llvm/Transforms/IPO/GlobalSplit.h index fb2c2d27338e..56cefb7886fe 100644 --- a/include/llvm/Transforms/IPO/GlobalSplit.h +++ b/include/llvm/Transforms/IPO/GlobalSplit.h @@ -17,14 +17,18 @@ #ifndef LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H #define LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" namespace llvm { + +class Module; + /// Pass to perform split of global variables. class GlobalSplitPass : public PassInfoMixin<GlobalSplitPass> { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -} + +} // end namespace llvm + #endif // LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H diff --git a/include/llvm/Transforms/IPO/Inliner.h b/include/llvm/Transforms/IPO/Inliner.h index b3ca5156e388..eda8cf462b50 100644 --- a/include/llvm/Transforms/IPO/Inliner.h +++ b/include/llvm/Transforms/IPO/Inliner.h @@ -14,15 +14,15 @@ #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/Analysis/LazyCallGraph.h" -#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/PassManager.h" #include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h" +#include <utility> namespace llvm { + class AssumptionCacheTracker; -class CallSite; -class DataLayout; -class InlineCost; -class OptimizationRemarkEmitter; +class CallGraph; class ProfileSummaryInfo; /// This class contains all of the helper code which is used to perform the @@ -44,6 +44,7 @@ struct LegacyInlinerBase : public CallGraphSCCPass { bool runOnSCC(CallGraphSCC &SCC) override; using llvm::Pass::doFinalization; + /// Remove now-dead linkonce functions at the end of processing to avoid /// breaking the SCC traversal. bool doFinalization(CallGraph &CG) override; @@ -69,7 +70,7 @@ struct LegacyInlinerBase : public CallGraphSCCPass { private: // Insert @llvm.lifetime intrinsics. - bool InsertLifetime; + bool InsertLifetime = true; protected: AssumptionCacheTracker *ACT; @@ -103,6 +104,6 @@ private: InlineParams Params; }; -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_IPO_INLINER_H diff --git a/include/llvm/Transforms/IPO/LowerTypeTests.h b/include/llvm/Transforms/IPO/LowerTypeTests.h index a2b888ce9ffa..3bcfe65df550 100644 --- a/include/llvm/Transforms/IPO/LowerTypeTests.h +++ b/include/llvm/Transforms/IPO/LowerTypeTests.h @@ -16,7 +16,6 @@ #define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H #include "llvm/ADT/SmallVector.h" -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include <cstdint> #include <cstring> @@ -26,6 +25,7 @@ namespace llvm { +class Module; class raw_ostream; namespace lowertypetests { diff --git a/include/llvm/Transforms/IPO/PartialInlining.h b/include/llvm/Transforms/IPO/PartialInlining.h index 15407fc36a22..ec6dd36dae06 100644 --- a/include/llvm/Transforms/IPO/PartialInlining.h +++ b/include/llvm/Transforms/IPO/PartialInlining.h @@ -1,4 +1,4 @@ -//===- PartialInlining.h - Inline parts of functions --------------------===// +//===- PartialInlining.h - Inline parts of functions ------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,15 +15,18 @@ #ifndef LLVM_TRANSFORMS_IPO_PARTIALINLINING_H #define LLVM_TRANSFORMS_IPO_PARTIALINLINING_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Module; + /// Pass to remove unused function declarations. class PartialInlinerPass : public PassInfoMixin<PartialInlinerPass> { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &); }; -} + +} // end namespace llvm + #endif // LLVM_TRANSFORMS_IPO_PARTIALINLINING_H diff --git a/include/llvm/Transforms/IPO/SCCP.h b/include/llvm/Transforms/IPO/SCCP.h index 7082006f14a6..fdb7865fbac3 100644 --- a/include/llvm/Transforms/IPO/SCCP.h +++ b/include/llvm/Transforms/IPO/SCCP.h @@ -21,14 +21,18 @@ #ifndef LLVM_TRANSFORMS_IPO_SCCP_H #define LLVM_TRANSFORMS_IPO_SCCP_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" namespace llvm { + +class Module; + /// Pass to perform interprocedural constant propagation. class IPSCCPPass : public PassInfoMixin<IPSCCPPass> { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -} + +} // end namespace llvm + #endif // LLVM_TRANSFORMS_IPO_SCCP_H diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h index f2fc6dc8dad5..cd6b770f76ac 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -22,24 +22,11 @@ #include <string> #include <vector> -#if defined(__GNUC__) && defined(__linux__) && !defined(ANDROID) -inline void *getDFSanArgTLSPtrForJIT() { - extern __thread __attribute__((tls_model("initial-exec"))) - void *__dfsan_arg_tls; - return (void *)&__dfsan_arg_tls; -} - -inline void *getDFSanRetValTLSPtrForJIT() { - extern __thread __attribute__((tls_model("initial-exec"))) - void *__dfsan_retval_tls; - return (void *)&__dfsan_retval_tls; -} -#endif - namespace llvm { class FunctionPass; class ModulePass; +class OptimizationRemarkEmitter; /// Instrumentation passes often insert conditional checks into entry blocks. /// Call this function before splitting the entry block to move instructions @@ -90,9 +77,12 @@ ModulePass *createPGOIndirectCallPromotionLegacyPass(bool InLTO = false, bool SamplePGO = false); FunctionPass *createPGOMemOPSizeOptLegacyPass(); -// Helper function to check if it is legal to promote indirect call \p Inst -// to a direct call of function \p F. Stores the reason in \p Reason. -bool isLegalToPromote(Instruction *Inst, Function *F, const char **Reason); +// The pgo-specific indirect call promotion function declared below is used by +// the pgo-driven indirect call promotion and sample profile passes. It's a +// wrapper around llvm::promoteCall, et al. that additionally computes !prof +// metadata. We place it in a pgo namespace so it's not confused with the +// generic utilities. +namespace pgo { // Helper function that transforms Inst (either an indirect-call instruction, or // an invoke instruction , to a conditional call to F. This is like: @@ -109,7 +99,9 @@ bool isLegalToPromote(Instruction *Inst, Function *F, const char **Reason); // Returns the promoted direct call instruction. Instruction *promoteIndirectCall(Instruction *Inst, Function *F, uint64_t Count, uint64_t TotalCount, - bool AttachProfToDirectCall); + bool AttachProfToDirectCall, + OptimizationRemarkEmitter *ORE); +} // namespace pgo /// Options for the frontend instrumentation based profiling pass. struct InstrProfOptions { @@ -141,6 +133,8 @@ ModulePass *createAddressSanitizerModulePass(bool CompileKernel = false, FunctionPass *createMemorySanitizerPass(int TrackOrigins = 0, bool Recover = false); +FunctionPass *createHWAddressSanitizerPass(); + // Insert ThreadSanitizer (race detection) instrumentation FunctionPass *createThreadSanitizerPass(); @@ -181,7 +175,9 @@ struct SanitizerCoverageOptions { bool TracePC = false; bool TracePCGuard = false; bool Inline8bitCounters = false; + bool PCTable = false; bool NoPrune = false; + bool StackDepth = false; SanitizerCoverageOptions() = default; }; @@ -190,18 +186,6 @@ struct SanitizerCoverageOptions { ModulePass *createSanitizerCoverageModulePass( const SanitizerCoverageOptions &Options = SanitizerCoverageOptions()); -#if defined(__GNUC__) && defined(__linux__) && !defined(ANDROID) -inline ModulePass *createDataFlowSanitizerPassForJIT( - const std::vector<std::string> &ABIListFiles = std::vector<std::string>()) { - return createDataFlowSanitizerPass(ABIListFiles, getDFSanArgTLSPtrForJIT, - getDFSanRetValTLSPtrForJIT); -} -#endif - -// BoundsChecking - This pass instruments the code to perform run-time bounds -// checking on loads, stores, and other memory intrinsics. -FunctionPass *createBoundsCheckingPass(); - /// \brief Calculate what to divide by to scale counts. /// /// Given the maximum count, calculate a divisor that will scale all the diff --git a/include/llvm/Transforms/Instrumentation/BoundsChecking.h b/include/llvm/Transforms/Instrumentation/BoundsChecking.h new file mode 100644 index 000000000000..3d4f62c121c2 --- /dev/null +++ b/include/llvm/Transforms/Instrumentation/BoundsChecking.h @@ -0,0 +1,29 @@ +//===- BoundsChecking.h - Bounds checking instrumentation -------*- 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_INSTRUMENTATION_BOUNDSCHECKING_H +#define LLVM_TRANSFORMS_INSTRUMENTATION_BOUNDSCHECKING_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A pass to instrument code and perform run-time bounds checking on loads, +/// stores, and other memory intrinsics. +struct BoundsCheckingPass : PassInfoMixin<BoundsCheckingPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + + +/// Legacy pass creation function for the above pass. +FunctionPass *createBoundsCheckingLegacyPass(); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_INSTRUMENTATION_BOUNDSCHECKING_H diff --git a/include/llvm/Transforms/PGOInstrumentation.h b/include/llvm/Transforms/PGOInstrumentation.h index 19263f0f8071..c2cc76c422da 100644 --- a/include/llvm/Transforms/PGOInstrumentation.h +++ b/include/llvm/Transforms/PGOInstrumentation.h @@ -1,4 +1,4 @@ -//===- Transforms/PGOInstrumentation.h - PGO gen/use passes ---*- C++ -*-===// +//===- Transforms/PGOInstrumentation.h - PGO gen/use passes -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,19 +6,27 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// This file provides the interface for IR based instrumentation passes ( /// (profile-gen, and profile-use). +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_PGOINSTRUMENTATION_H #define LLVM_TRANSFORMS_PGOINSTRUMENTATION_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Instrumentation.h" +#include <cstdint> +#include <string> namespace llvm { +class Function; +class Instruction; +class Module; + /// The instrumentation (profile-instr-gen) pass for IR based PGO. class PGOInstrumentationGen : public PassInfoMixin<PGOInstrumentationGen> { public: @@ -28,9 +36,10 @@ public: /// The profile annotation (profile-instr-use) pass for IR based PGO. class PGOInstrumentationUse : public PassInfoMixin<PGOInstrumentationUse> { public: - PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); PGOInstrumentationUse(std::string Filename = ""); + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); + private: std::string ProfileFileName; }; @@ -40,6 +49,7 @@ class PGOIndirectCallPromotion : public PassInfoMixin<PGOIndirectCallPromotion> public: PGOIndirectCallPromotion(bool IsInLTO = false, bool SamplePGO = false) : InLTO(IsInLTO), SamplePGO(SamplePGO) {} + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); private: @@ -50,12 +60,16 @@ private: /// The profile size based optimization pass for memory intrinsics. class PGOMemOPSizeOpt : public PassInfoMixin<PGOMemOPSizeOpt> { public: - PGOMemOPSizeOpt() {} + PGOMemOPSizeOpt() = default; + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; void setProfMetadata(Module *M, Instruction *TI, ArrayRef<uint64_t> EdgeCounts, uint64_t MaxCount); -} // End llvm namespace -#endif +void setIrrLoopHeaderMetadata(Module *M, Instruction *TI, uint64_t Count); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_PGOINSTRUMENTATION_H diff --git a/include/llvm/Transforms/SampleProfile.h b/include/llvm/Transforms/SampleProfile.h index c984fe74ba93..f5a8590e14a1 100644 --- a/include/llvm/Transforms/SampleProfile.h +++ b/include/llvm/Transforms/SampleProfile.h @@ -1,4 +1,4 @@ -//===- Transforms/SampleProfile.h - SamplePGO pass--------------*- C++ -*-===// +//===- Transforms/SampleProfile.h - SamplePGO pass --------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,26 +6,35 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// This file provides the interface for the sampled PGO loader pass. +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SAMPLEPROFILE_H #define LLVM_TRANSFORMS_SAMPLEPROFILE_H #include "llvm/IR/PassManager.h" +#include <string> namespace llvm { +class Module; + /// The sample profiler data loader pass. class SampleProfileLoaderPass : public PassInfoMixin<SampleProfileLoaderPass> { public: + SampleProfileLoaderPass(std::string File = "", bool IsThinLTOPreLink = false) + : ProfileFileName(File), IsThinLTOPreLink(IsThinLTOPreLink) {} + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); - SampleProfileLoaderPass(std::string File = "") : ProfileFileName(File) {} private: std::string ProfileFileName; + bool IsThinLTOPreLink; }; -} // End llvm namespace -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SAMPLEPROFILE_H diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index 1913a9d5da02..49186bc5cd66 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -73,6 +73,14 @@ FunctionPass *createDeadCodeEliminationPass(); // FunctionPass *createDeadStoreEliminationPass(); + +//===----------------------------------------------------------------------===// +// +// CallSiteSplitting - This pass split call-site based on its known argument +// values. +FunctionPass *createCallSiteSplittingPass(); + + //===----------------------------------------------------------------------===// // // AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm. This @@ -184,7 +192,7 @@ Pass *createLoopInstSimplifyPass(); // Pass *createLoopUnrollPass(int OptLevel = 2, int Threshold = -1, int Count = -1, int AllowPartial = -1, int Runtime = -1, - int UpperBound = -1); + int UpperBound = -1, int AllowPeeling = -1); // Create an unrolling pass for full unrolling that uses exact trip count only. Pass *createSimpleLoopUnrollPass(int OptLevel = 2); @@ -255,18 +263,12 @@ FunctionPass *createJumpThreadingPass(int Threshold = -1); //===----------------------------------------------------------------------===// // // CFGSimplification - Merge basic blocks, eliminate unreachable blocks, -// simplify terminator instructions, etc... +// simplify terminator instructions, convert switches to lookup tables, etc. // FunctionPass *createCFGSimplificationPass( - int Threshold = -1, std::function<bool(const Function &)> Ftor = nullptr); - -//===----------------------------------------------------------------------===// -// -// LateCFGSimplification - Like CFGSimplification, but may also -// convert switches to lookup tables. -// -FunctionPass *createLateCFGSimplificationPass( - int Threshold = -1, std::function<bool(const Function &)> Ftor = nullptr); + unsigned Threshold = 1, bool ForwardSwitchCond = false, + bool ConvertSwitch = false, bool KeepLoops = true, bool SinkCommon = false, + std::function<bool(const Function &)> Ftor = nullptr); //===----------------------------------------------------------------------===// // @@ -377,6 +379,12 @@ FunctionPass *createNewGVNPass(); //===----------------------------------------------------------------------===// // +// DivRemPairs - Hoist/decompose integer division and remainder instructions. +// +FunctionPass *createDivRemPairsPass(); + +//===----------------------------------------------------------------------===// +// // MemCpyOpt - This pass performs optimizations related to eliminating memcpy // calls and/or combining multiple stores into memset's. // @@ -422,6 +430,12 @@ Pass *createLowerGuardIntrinsicPass(); //===----------------------------------------------------------------------===// // +// MergeICmps - Merge integer comparison chains into a memcmp +// +Pass *createMergeICmpsPass(); + +//===----------------------------------------------------------------------===// +// // ValuePropagation - Propagate CFG-derived value information // Pass *createCorrelatedValuePropagationPass(); @@ -507,7 +521,7 @@ FunctionPass *createPlaceSafepointsPass(); // RewriteStatepointsForGC - Rewrite any gc.statepoints which do not yet have // explicit relocations to include explicit relocations. // -ModulePass *createRewriteStatepointsForGCPass(); +ModulePass *createRewriteStatepointsForGCLegacyPass(); //===----------------------------------------------------------------------===// // @@ -568,6 +582,16 @@ ModulePass *createNameAnonGlobalPass(); // used. // 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. +// +FunctionPass *createEntryExitInstrumenterPass(); +FunctionPass *createPostInlineEntryExitInstrumenterPass(); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Scalar/ADCE.h b/include/llvm/Transforms/Scalar/ADCE.h index b9b7e1c0c99f..f98af62c1a76 100644 --- a/include/llvm/Transforms/Scalar/ADCE.h +++ b/include/llvm/Transforms/Scalar/ADCE.h @@ -1,4 +1,4 @@ -//===- ADCE.h - Aggressive dead code elimination --------------------------===// +//===- ADCE.h - Aggressive dead code elimination ----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -17,11 +17,12 @@ #ifndef LLVM_TRANSFORMS_SCALAR_ADCE_H #define LLVM_TRANSFORMS_SCALAR_ADCE_H -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Function; + /// A DCE pass that assumes instructions are dead until proven otherwise. /// /// This pass eliminates dead code by optimistically assuming that all @@ -31,6 +32,7 @@ namespace llvm { struct ADCEPass : PassInfoMixin<ADCEPass> { PreservedAnalyses run(Function &F, FunctionAnalysisManager &); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_ADCE_H diff --git a/include/llvm/Transforms/Scalar/CallSiteSplitting.h b/include/llvm/Transforms/Scalar/CallSiteSplitting.h new file mode 100644 index 000000000000..5ab951a49f2c --- /dev/null +++ b/include/llvm/Transforms/Scalar/CallSiteSplitting.h @@ -0,0 +1,29 @@ +//===- CallSiteSplitting..h - Callsite Splitting ------------*- 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_CALLSITESPLITTING__H +#define LLVM_TRANSFORMS_SCALAR_CALLSITESPLITTING__H + +#include "llvm/ADT/SetVector.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/Compiler.h" +#include <vector> + +namespace llvm { + +struct CallSiteSplittingPass : PassInfoMixin<CallSiteSplittingPass> { + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_CALLSITESPLITTING__H diff --git a/include/llvm/Transforms/Scalar/ConstantHoisting.h b/include/llvm/Transforms/Scalar/ConstantHoisting.h index a2a9afc083a0..d3322dc1c414 100644 --- a/include/llvm/Transforms/Scalar/ConstantHoisting.h +++ b/include/llvm/Transforms/Scalar/ConstantHoisting.h @@ -1,4 +1,4 @@ -//===-- ConstantHoisting.h - Prepare code for expensive constants ---------===// +//==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==// // // The LLVM Compiler Infrastructure // @@ -31,41 +31,53 @@ // This optimization is only applied to integer constants in instructions and // simple (this means not nested) constant cast expressions. For example: // %0 = load i64* inttoptr (i64 big_constant to i64*) +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H -#include "llvm/Analysis/BlockFrequencyInfo.h" -#include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/IR/Dominators.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/IR/PassManager.h" +#include <algorithm> +#include <vector> namespace llvm { +class BasicBlock; +class BlockFrequencyInfo; +class Constant; +class ConstantInt; +class DominatorTree; +class Function; +class Instruction; +class TargetTransformInfo; + /// A private "module" namespace for types and utilities used by /// ConstantHoisting. These are implementation details and should not be used by /// clients. namespace consthoist { + /// \brief Keeps track of the user of a constant and the operand index where the /// constant is used. struct ConstantUser { Instruction *Inst; unsigned OpndIdx; - ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { } + ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {} }; -typedef SmallVector<ConstantUser, 8> ConstantUseListType; +using ConstantUseListType = SmallVector<ConstantUser, 8>; /// \brief Keeps track of a constant candidate and its uses. struct ConstantCandidate { ConstantUseListType Uses; ConstantInt *ConstInt; - unsigned CumulativeCost; + unsigned CumulativeCost = 0; - ConstantCandidate(ConstantInt *ConstInt) - : ConstInt(ConstInt), CumulativeCost(0) { } + ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {} /// \brief Add the user to the use list and update the cost. void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { @@ -81,17 +93,18 @@ struct RebasedConstantInfo { Constant *Offset; RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset) - : Uses(std::move(Uses)), Offset(Offset) { } + : Uses(std::move(Uses)), Offset(Offset) {} }; -typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType; +using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>; /// \brief A base constant and all its rebased constants. struct ConstantInfo { ConstantInt *BaseConstant; RebasedConstantListType RebasedConstants; }; -} + +} // end namespace consthoist class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> { public: @@ -108,8 +121,8 @@ public: } private: - typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType; - typedef std::vector<consthoist::ConstantCandidate> ConstCandVecType; + using ConstCandMapType = DenseMap<ConstantInt *, unsigned>; + using ConstCandVecType = std::vector<consthoist::ConstantCandidate>; const TargetTransformInfo *TTI; DominatorTree *DT; @@ -148,6 +161,7 @@ private: void deleteDeadCastInst() const; bool optimizeConstants(Function &Fn); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H diff --git a/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h b/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h index 38816bbed068..20930699b557 100644 --- a/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h +++ b/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h @@ -1,4 +1,4 @@ -//===---- CorrelatedValuePropagation.h --------------------------*- C++ -*-===// +//===- CorrelatedValuePropagation.h -----------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -10,15 +10,17 @@ #ifndef LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H #define LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Function; + struct CorrelatedValuePropagationPass : PassInfoMixin<CorrelatedValuePropagationPass> { PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H diff --git a/include/llvm/Transforms/Scalar/DeadStoreElimination.h b/include/llvm/Transforms/Scalar/DeadStoreElimination.h index 3ae999dfb542..cfeb21814232 100644 --- a/include/llvm/Transforms/Scalar/DeadStoreElimination.h +++ b/include/llvm/Transforms/Scalar/DeadStoreElimination.h @@ -1,4 +1,4 @@ -//===- DeadStoreElimination.h - Fast Dead Store Elimination -------------===// +//===- DeadStoreElimination.h - Fast Dead Store Elimination -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,20 +15,22 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_TRANSFORMS_SCALAR_DSE_H -#define LLVM_TRANSFORMS_SCALAR_DSE_H +#ifndef LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATION_H +#define LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATION_H -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Function; + /// This class implements a trivial dead store elimination. We consider /// only the redundant stores that are local to a single Basic Block. class DSEPass : public PassInfoMixin<DSEPass> { public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); }; -} -#endif // LLVM_TRANSFORMS_SCALAR_DSE_H +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATION_H diff --git a/include/llvm/Transforms/Scalar/DivRemPairs.h b/include/llvm/Transforms/Scalar/DivRemPairs.h new file mode 100644 index 000000000000..0a4346f33b12 --- /dev/null +++ b/include/llvm/Transforms/Scalar/DivRemPairs.h @@ -0,0 +1,31 @@ +//===- DivRemPairs.h - Hoist/decompose integer division and remainder -----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass hoists and/or decomposes integer division and remainder +// instructions to enable CFG improvements and better codegen. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_DIVREMPAIRS_H +#define LLVM_TRANSFORMS_SCALAR_DIVREMPAIRS_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Hoist/decompose integer division and remainder instructions to enable CFG +/// improvements and better codegen. +struct DivRemPairsPass : public PassInfoMixin<DivRemPairsPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &); +}; + +} +#endif // LLVM_TRANSFORMS_SCALAR_DIVREMPAIRS_H + diff --git a/include/llvm/Transforms/Scalar/EarlyCSE.h b/include/llvm/Transforms/Scalar/EarlyCSE.h index 969ab78bfd19..dca3b2dbf04f 100644 --- a/include/llvm/Transforms/Scalar/EarlyCSE.h +++ b/include/llvm/Transforms/Scalar/EarlyCSE.h @@ -6,19 +6,21 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// This file provides the interface for a simple, fast CSE pass. -/// +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SCALAR_EARLYCSE_H #define LLVM_TRANSFORMS_SCALAR_EARLYCSE_H -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Function; + /// \brief A simple and fast domtree-based CSE pass. /// /// This pass does a simple depth-first walk over the dominator tree, @@ -35,6 +37,6 @@ struct EarlyCSEPass : PassInfoMixin<EarlyCSEPass> { bool UseMemorySSA; }; -} +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_SCALAR_EARLYCSE_H diff --git a/include/llvm/Transforms/Scalar/GVN.h b/include/llvm/Transforms/Scalar/GVN.h index f25ab40640df..440d3f67c35a 100644 --- a/include/llvm/Transforms/Scalar/GVN.h +++ b/include/llvm/Transforms/Scalar/GVN.h @@ -18,26 +18,48 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" -#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/IR/Dominators.h" -#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/InstrTypes.h" #include "llvm/IR/PassManager.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Transforms/Utils/OrderedInstructions.h" +#include <cstdint> +#include <utility> +#include <vector> namespace llvm { + +class AssumptionCache; +class BasicBlock; +class BranchInst; +class CallInst; +class Constant; +class ExtractValueInst; +class Function; +class FunctionPass; +class IntrinsicInst; +class LoadInst; +class LoopInfo; class OptimizationRemarkEmitter; +class PHINode; +class TargetLibraryInfo; +class Value; /// A private "module" namespace for types and utilities used by GVN. These /// are implementation details and should not be used by clients. namespace gvn LLVM_LIBRARY_VISIBILITY { + struct AvailableValue; struct AvailableValueInBlock; class GVNLegacyPass; -} + +} // end namespace gvn /// The core GVN pass object. /// @@ -45,6 +67,7 @@ class GVNLegacyPass; /// this particular pass here. class GVN : public PassInfoMixin<GVN> { public: + struct Expression; /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); @@ -60,25 +83,45 @@ public: AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } MemoryDependenceResults &getMemDep() const { return *MD; } - struct Expression; - /// This class holds the mapping between values and value numbers. It is used /// as an efficient mechanism to determine the expression-wise equivalence of /// two values. class ValueTable { DenseMap<Value *, uint32_t> valueNumbering; DenseMap<Expression, uint32_t> expressionNumbering; + + // Expressions is the vector of Expression. ExprIdx is the mapping from + // value number to the index of Expression in Expressions. We use it + // instead of a DenseMap because filling such mapping is faster than + // filling a DenseMap and the compile time is a little better. + uint32_t nextExprNumber; + + std::vector<Expression> Expressions; + std::vector<uint32_t> ExprIdx; + + // Value number to PHINode mapping. Used for phi-translate in scalarpre. + DenseMap<uint32_t, PHINode *> NumberingPhi; + + // Cache for phi-translate in scalarpre. + using PhiTranslateMap = + DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>; + PhiTranslateMap PhiTranslateTable; + AliasAnalysis *AA; MemoryDependenceResults *MD; DominatorTree *DT; - uint32_t nextValueNumber; + uint32_t nextValueNumber = 1; Expression createExpr(Instruction *I); Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS); Expression createExtractvalueExpr(ExtractValueInst *EI); uint32_t lookupOrAddCall(CallInst *C); + uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock, + uint32_t Num, GVN &Gvn); + std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp); + bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn); public: ValueTable(); @@ -87,9 +130,12 @@ public: ~ValueTable(); uint32_t lookupOrAdd(Value *V); - uint32_t lookup(Value *V) const; + uint32_t lookup(Value *V, bool Verify = true) const; uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS); + uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, + uint32_t Num, GVN &Gvn); + void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock); bool exists(Value *V) const; void add(Value *V, uint32_t num); void clear(); @@ -112,7 +158,11 @@ private: AssumptionCache *AC; SetVector<BasicBlock *> DeadBlocks; OptimizationRemarkEmitter *ORE; + // Maps a block to the topmost instruction with implicit control flow in it. + DenseMap<const BasicBlock *, const Instruction *> + FirstImplicitControlFlowInsts; + OrderedInstructions *OI; ValueTable VN; /// A mapping from value numbers to lists of Value*'s that @@ -128,12 +178,16 @@ private: // Block-local map of equivalent values to their leader, does not // propagate to any successors. Entries added mid-block are applied // to the remaining instructions in the block. - SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap; + SmallMapVector<Value *, Constant *, 4> ReplaceWithConstMap; SmallVector<Instruction *, 8> InstrsToErase; - typedef SmallVector<NonLocalDepResult, 64> LoadDepVect; - typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect; - typedef SmallVector<BasicBlock *, 64> UnavailBlkVect; + // Map the block to reversed postorder traversal number. It is used to + // find back edge easily. + DenseMap<const BasicBlock *, uint32_t> BlockRPONumber; + + using LoadDepVect = SmallVector<NonLocalDepResult, 64>; + using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>; + using UnavailBlkVect = SmallVector<BasicBlock *, 64>; bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, const TargetLibraryInfo &RunTLI, AAResults &RunAA, @@ -192,17 +246,20 @@ private: bool processLoad(LoadInst *L); bool processNonLocalLoad(LoadInst *L); bool processAssumeIntrinsic(IntrinsicInst *II); + /// Given a local dependency (Def or Clobber) determine if a value is /// available for the load. Returns true if an value is known to be /// available and populates Res. Returns false otherwise. bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, Value *Address, gvn::AvailableValue &Res); + /// Given a list of non-local dependencies, determine if a value is /// available for the load in each specified block. If it is, add it to /// ValuesPerBlock. If not, add it to UnavailableBlocks. void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks); + bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks); @@ -214,9 +271,10 @@ private: bool performPRE(Function &F); bool performScalarPRE(Instruction *I); bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, - unsigned int ValNo); + BasicBlock *Curr, unsigned int ValNo); Value *findLeader(const BasicBlock *BB, uint32_t num); void cleanupGlobalSets(); + void fillImplicitControlFlowInfo(BasicBlock *BB); void verifyRemoved(const Instruction *I) const; bool splitCriticalEdges(); BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); @@ -226,6 +284,7 @@ private: bool processFoldableCondBr(BranchInst *BI); void addDeadBlock(BasicBlock *BB); void assignValNumForDeadCode(); + void assignBlockRPONumber(Function &F); }; /// Create a legacy GVN pass. This also allows parameterizing whether or not @@ -238,12 +297,14 @@ struct GVNHoistPass : PassInfoMixin<GVNHoistPass> { /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; + /// \brief 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. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_GVN_H diff --git a/include/llvm/Transforms/Scalar/GVNExpression.h b/include/llvm/Transforms/Scalar/GVNExpression.h index f603ebcbca7c..99dae15a3ac0 100644 --- a/include/llvm/Transforms/Scalar/GVNExpression.h +++ b/include/llvm/Transforms/Scalar/GVNExpression.h @@ -1,4 +1,4 @@ -//======- GVNExpression.h - GVN Expression classes --------------*- C++ -*-===// +//===- GVNExpression.h - GVN Expression classes -----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,11 +6,12 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// /// The header file for the GVN pass that contains expression handling /// classes -/// +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H @@ -25,7 +26,7 @@ #include "llvm/Support/Allocator.h" #include "llvm/Support/ArrayRecycler.h" #include "llvm/Support/Casting.h" -#include "llvm/Support/Debug.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> #include <cassert> @@ -34,6 +35,9 @@ namespace llvm { +class BasicBlock; +class Type; + namespace GVNExpression { enum ExpressionType { @@ -58,17 +62,18 @@ class Expression { private: ExpressionType EType; unsigned Opcode; - mutable hash_code HashVal; + mutable hash_code HashVal = 0; public: Expression(ExpressionType ET = ET_Base, unsigned O = ~2U) - : EType(ET), Opcode(O), HashVal(0) {} + : EType(ET), Opcode(O) {} Expression(const Expression &) = delete; Expression &operator=(const Expression &) = delete; virtual ~Expression(); static unsigned getEmptyKey() { return ~0U; } static unsigned getTombstoneKey() { return ~1U; } + bool operator!=(const Expression &Other) const { return !(*this == Other); } bool operator==(const Expression &Other) const { if (getOpcode() != Other.getOpcode()) @@ -83,6 +88,7 @@ public: return equals(Other); } + hash_code getComputedHash() const { // It's theoretically possible for a thing to hash to zero. In that case, // we will just compute the hash a few extra times, which is no worse that @@ -93,6 +99,7 @@ public: } virtual bool equals(const Expression &Other) const { return true; } + // Return true if the two expressions are exactly the same, including the // normally ignored fields. virtual bool exactlyEquals(const Expression &Other) const { @@ -106,9 +113,7 @@ public: // We deliberately leave the expression type out of the hash value. virtual hash_code getHashValue() const { return getOpcode(); } - // // Debugging support - // virtual void printInternal(raw_ostream &OS, bool PrintEType) const { if (PrintEType) OS << "etype = " << getExpressionType() << ","; @@ -131,19 +136,19 @@ inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) { class BasicExpression : public Expression { private: - typedef ArrayRecycler<Value *> RecyclerType; - typedef RecyclerType::Capacity RecyclerCapacity; - Value **Operands; + using RecyclerType = ArrayRecycler<Value *>; + using RecyclerCapacity = RecyclerType::Capacity; + + Value **Operands = nullptr; unsigned MaxOperands; - unsigned NumOperands; - Type *ValueType; + unsigned NumOperands = 0; + Type *ValueType = nullptr; public: BasicExpression(unsigned NumOperands) : BasicExpression(NumOperands, ET_Basic) {} BasicExpression(unsigned NumOperands, ExpressionType ET) - : Expression(ET), Operands(nullptr), MaxOperands(NumOperands), - NumOperands(0), ValueType(nullptr) {} + : Expression(ET), MaxOperands(NumOperands) {} BasicExpression() = delete; BasicExpression(const BasicExpression &) = delete; BasicExpression &operator=(const BasicExpression &) = delete; @@ -174,8 +179,9 @@ public: unsigned getNumOperands() const { return NumOperands; } - typedef Value **op_iterator; - typedef Value *const *const_op_iterator; + using op_iterator = Value **; + using const_op_iterator = Value *const *; + op_iterator op_begin() { return Operands; } op_iterator op_end() { return Operands + NumOperands; } const_op_iterator op_begin() const { return Operands; } @@ -219,9 +225,7 @@ public: hash_combine_range(op_begin(), op_end())); } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeBasic, "; @@ -240,7 +244,8 @@ public: class op_inserter : public std::iterator<std::output_iterator_tag, void, void, void, void> { private: - typedef BasicExpression Container; + using Container = BasicExpression; + Container *BE; public: @@ -263,15 +268,16 @@ private: public: MemoryExpression(unsigned NumOperands, enum ExpressionType EType, const MemoryAccess *MemoryLeader) - : BasicExpression(NumOperands, EType), MemoryLeader(MemoryLeader){}; - + : BasicExpression(NumOperands, EType), MemoryLeader(MemoryLeader) {} MemoryExpression() = delete; MemoryExpression(const MemoryExpression &) = delete; MemoryExpression &operator=(const MemoryExpression &) = delete; + static bool classof(const Expression *EB) { return EB->getExpressionType() > ET_MemoryStart && EB->getExpressionType() < ET_MemoryEnd; } + hash_code getHashValue() const override { return hash_combine(this->BasicExpression::getHashValue(), MemoryLeader); } @@ -305,9 +311,7 @@ public: return EB->getExpressionType() == ET_Call; } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeCall, "; @@ -326,11 +330,13 @@ public: LoadExpression(unsigned NumOperands, LoadInst *L, const MemoryAccess *MemoryLeader) : LoadExpression(ET_Load, NumOperands, L, MemoryLeader) {} + LoadExpression(enum ExpressionType EType, unsigned NumOperands, LoadInst *L, const MemoryAccess *MemoryLeader) : MemoryExpression(NumOperands, EType, MemoryLeader), Load(L) { Alignment = L ? L->getAlignment() : 0; } + LoadExpression() = delete; LoadExpression(const LoadExpression &) = delete; LoadExpression &operator=(const LoadExpression &) = delete; @@ -352,9 +358,7 @@ public: cast<LoadExpression>(Other).getLoadInst() == getLoadInst(); } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeLoad, "; @@ -388,13 +392,13 @@ public: Value *getStoredValue() const { return StoredValue; } bool equals(const Expression &Other) const override; + bool exactlyEquals(const Expression &Other) const override { return Expression::exactlyEquals(Other) && cast<StoreExpression>(Other).getStoreInst() == getStoreInst(); } // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeStore, "; @@ -409,14 +413,13 @@ public: class AggregateValueExpression final : public BasicExpression { private: unsigned MaxIntOperands; - unsigned NumIntOperands; - unsigned *IntOperands; + unsigned NumIntOperands = 0; + unsigned *IntOperands = nullptr; public: AggregateValueExpression(unsigned NumOperands, unsigned NumIntOperands) : BasicExpression(NumOperands, ET_AggregateValue), - MaxIntOperands(NumIntOperands), NumIntOperands(0), - IntOperands(nullptr) {} + MaxIntOperands(NumIntOperands) {} AggregateValueExpression() = delete; AggregateValueExpression(const AggregateValueExpression &) = delete; AggregateValueExpression & @@ -427,8 +430,8 @@ public: return EB->getExpressionType() == ET_AggregateValue; } - typedef unsigned *int_arg_iterator; - typedef const unsigned *const_int_arg_iterator; + using int_arg_iterator = unsigned *; + using const_int_arg_iterator = const unsigned *; int_arg_iterator int_op_begin() { return IntOperands; } int_arg_iterator int_op_end() { return IntOperands + NumIntOperands; } @@ -463,9 +466,7 @@ public: hash_combine_range(int_op_begin(), int_op_end())); } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeAggregateValue, "; @@ -481,7 +482,8 @@ public: class int_op_inserter : public std::iterator<std::output_iterator_tag, void, void, void, void> { private: - typedef AggregateValueExpression Container; + using Container = AggregateValueExpression; + Container *AVE; public: @@ -524,9 +526,7 @@ public: return hash_combine(this->BasicExpression::getHashValue(), BB); } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypePhi, "; @@ -573,9 +573,7 @@ public: VariableValue->getType(), VariableValue); } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeVariable, "; @@ -612,9 +610,7 @@ public: ConstantValue->getType(), ConstantValue); } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeConstant, "; @@ -649,9 +645,7 @@ public: return hash_combine(this->Expression::getHashValue(), Inst); } - // // Debugging support - // void printInternal(raw_ostream &OS, bool PrintEType) const override { if (PrintEType) OS << "ExpressionTypeUnknown, "; diff --git a/include/llvm/Transforms/Scalar/IndVarSimplify.h b/include/llvm/Transforms/Scalar/IndVarSimplify.h index 4a4683f1a07d..e321c8fc6e9c 100644 --- a/include/llvm/Transforms/Scalar/IndVarSimplify.h +++ b/include/llvm/Transforms/Scalar/IndVarSimplify.h @@ -15,17 +15,20 @@ #ifndef LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H #define LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Scalar/LoopPassManager.h" namespace llvm { +class Loop; +class LPMUpdater; + class IndVarSimplifyPass : public PassInfoMixin<IndVarSimplifyPass> { public: PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H diff --git a/include/llvm/Transforms/Scalar/JumpThreading.h b/include/llvm/Transforms/Scalar/JumpThreading.h index 1da86132591b..a9466713b8e6 100644 --- a/include/llvm/Transforms/Scalar/JumpThreading.h +++ b/include/llvm/Transforms/Scalar/JumpThreading.h @@ -6,41 +6,57 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// See the comments on JumpThreadingPass. -/// +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BlockFrequencyInfo.h" -#include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" -#include "llvm/Analysis/LazyValueInfo.h" -#include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/ValueHandle.h" +#include <memory> +#include <utility> namespace llvm { +class BasicBlock; +class BinaryOperator; +class BranchInst; +class CmpInst; +class Constant; +class Function; +class Instruction; +class IntrinsicInst; +class LazyValueInfo; +class LoadInst; +class PHINode; +class TargetLibraryInfo; +class Value; + /// A private "module" namespace for types and utilities used by /// JumpThreading. /// These are implementation details and should not be used by clients. namespace jumpthreading { + // These are at global scope so static functions can use them too. -typedef SmallVectorImpl<std::pair<Constant *, BasicBlock *>> PredValueInfo; -typedef SmallVector<std::pair<Constant *, BasicBlock *>, 8> PredValueInfoTy; +using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>; +using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>; // This is used to keep track of what kind of constant we're currently hoping // to find. enum ConstantPreference { WantInteger, WantBlockAddress }; -} + +} // end namespace jumpthreading /// This pass performs 'jump threading', which looks at blocks that have /// multiple predecessors and multiple successors. If one or more of the @@ -57,7 +73,6 @@ enum ConstantPreference { WantInteger, WantBlockAddress }; /// /// In this case, the unconditional branch at the end of the first if can be /// revectored to the false side of the second if. -/// class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> { TargetLibraryInfo *TLI; LazyValueInfo *LVI; @@ -141,4 +156,4 @@ private: } // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H diff --git a/include/llvm/Transforms/Scalar/LoopDistribute.h b/include/llvm/Transforms/Scalar/LoopDistribute.h index ddde5954c218..2bf1c9d696d5 100644 --- a/include/llvm/Transforms/Scalar/LoopDistribute.h +++ b/include/llvm/Transforms/Scalar/LoopDistribute.h @@ -21,10 +21,13 @@ namespace llvm { +class Function; + class LoopDistributePass : public PassInfoMixin<LoopDistributePass> { public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; + } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPDISTRIBUTE_H diff --git a/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h b/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h index 40349e8f7fe0..7added8d2c61 100644 --- a/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h +++ b/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h @@ -1,4 +1,4 @@ -//===- LoopIdiomRecognize.h - Loop Idiom Recognize Pass -------*- C++ -*-===// +//===- LoopIdiomRecognize.h - Loop Idiom Recognize Pass ---------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -16,18 +16,21 @@ #ifndef LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H #define LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Scalar/LoopPassManager.h" namespace llvm { +class Loop; +class LPMUpdater; + /// Performs Loop Idiom Recognize Pass. class LoopIdiomRecognizePass : public PassInfoMixin<LoopIdiomRecognizePass> { public: PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); }; + } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H diff --git a/include/llvm/Transforms/Scalar/LoopInstSimplify.h b/include/llvm/Transforms/Scalar/LoopInstSimplify.h index bb8bc29577a2..04dc79c3fa57 100644 --- a/include/llvm/Transforms/Scalar/LoopInstSimplify.h +++ b/include/llvm/Transforms/Scalar/LoopInstSimplify.h @@ -1,4 +1,4 @@ -//===- LoopInstSimplify.h - Loop Inst Simplify Pass -------*- C++ -*-===// +//===- LoopInstSimplify.h - Loop Inst Simplify Pass -------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,18 +14,21 @@ #ifndef LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H #define LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Scalar/LoopPassManager.h" namespace llvm { +class Loop; +class LPMUpdater; + /// Performs Loop Inst Simplify Pass. class LoopInstSimplifyPass : public PassInfoMixin<LoopInstSimplifyPass> { public: PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); }; + } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H diff --git a/include/llvm/Transforms/Scalar/LoopLoadElimination.h b/include/llvm/Transforms/Scalar/LoopLoadElimination.h index 7a007a7e822d..b0514a4a7c98 100644 --- a/include/llvm/Transforms/Scalar/LoopLoadElimination.h +++ b/include/llvm/Transforms/Scalar/LoopLoadElimination.h @@ -1,4 +1,4 @@ -//===---- LoopLoadElimination.h ---------------------------------*- C++ -*-===// +//===- LoopLoadElimination.h ------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,11 +6,12 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// This header defines the LoopLoadEliminationPass object. This pass forwards /// loaded values around loop backedges to allow their use in subsequent /// iterations. -/// +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H @@ -20,11 +21,14 @@ namespace llvm { +class Function; + /// Pass to forward loads in a loop around the backedge to subsequent /// iterations. struct LoopLoadEliminationPass : public PassInfoMixin<LoopLoadEliminationPass> { PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H diff --git a/include/llvm/Transforms/Scalar/LoopPassManager.h b/include/llvm/Transforms/Scalar/LoopPassManager.h index 715b11d3d974..473b97dc7e8d 100644 --- a/include/llvm/Transforms/Scalar/LoopPassManager.h +++ b/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -164,10 +164,11 @@ public: /// If this is called for the current loop, in addition to clearing any /// state, this routine will mark that the current loop should be skipped by /// the rest of the pass management infrastructure. - void markLoopAsDeleted(Loop &L) { - LAM.clear(L); - assert(CurrentL->contains(&L) && "Cannot delete a loop outside of the " - "subloop tree currently being processed."); + void markLoopAsDeleted(Loop &L, llvm::StringRef Name) { + LAM.clear(L, Name); + assert((&L == CurrentL || CurrentL->contains(&L)) && + "Cannot delete a loop outside of the " + "subloop tree currently being processed."); if (&L == CurrentL) SkipCurrentLoop = true; } @@ -216,6 +217,19 @@ public: // shouldn't impact anything. } + /// Restart the current loop. + /// + /// Loop passes should call this method to indicate the current loop has been + /// sufficiently changed that it should be re-visited from the begining of + /// the loop pass pipeline rather than continuing. + void revisitCurrentLoop() { + // Tell the currently in-flight pipeline to stop running. + SkipCurrentLoop = true; + + // And insert ourselves back into the worklist. + Worklist.insert(CurrentL); + } + private: template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor; @@ -271,13 +285,17 @@ public: return PA; // Get the analysis results needed by loop passes. + MemorySSA *MSSA = EnableMSSALoopDependency + ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) + : nullptr; LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F), AM.getResult<AssumptionAnalysis>(F), AM.getResult<DominatorTreeAnalysis>(F), AM.getResult<LoopAnalysis>(F), AM.getResult<ScalarEvolutionAnalysis>(F), AM.getResult<TargetLibraryAnalysis>(F), - AM.getResult<TargetIRAnalysis>(F)}; + AM.getResult<TargetIRAnalysis>(F), + MSSA}; // Setup the loop analysis manager from its proxy. It is important that // this is only done when there are loops to process and we have built the @@ -345,6 +363,8 @@ public: PA.preserve<DominatorTreeAnalysis>(); PA.preserve<LoopAnalysis>(); PA.preserve<ScalarEvolutionAnalysis>(); + // FIXME: Uncomment this when all loop passes preserve MemorySSA + // PA.preserve<MemorySSAAnalysis>(); // FIXME: What we really want to do here is preserve an AA category, but // that concept doesn't exist yet. PA.preserve<AAManager>(); diff --git a/include/llvm/Transforms/Scalar/LoopStrengthReduce.h b/include/llvm/Transforms/Scalar/LoopStrengthReduce.h index ebcb32125262..62c038a3857d 100644 --- a/include/llvm/Transforms/Scalar/LoopStrengthReduce.h +++ b/include/llvm/Transforms/Scalar/LoopStrengthReduce.h @@ -1,4 +1,4 @@ -//===- LoopStrengthReduce.h - Loop Strength Reduce Pass -------*- C++ -*-===// +//===- LoopStrengthReduce.h - Loop Strength Reduce Pass ---------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -22,18 +22,21 @@ #ifndef LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H #define LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Scalar/LoopPassManager.h" namespace llvm { +class Loop; +class LPMUpdater; + /// Performs Loop Strength Reduce Pass. class LoopStrengthReducePass : public PassInfoMixin<LoopStrengthReducePass> { public: PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); }; + } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H diff --git a/include/llvm/Transforms/Scalar/LoopUnrollPass.h b/include/llvm/Transforms/Scalar/LoopUnrollPass.h index 7253bd09766e..9848e0d54f2b 100644 --- a/include/llvm/Transforms/Scalar/LoopUnrollPass.h +++ b/include/llvm/Transforms/Scalar/LoopUnrollPass.h @@ -10,40 +10,40 @@ #ifndef LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H #define LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Scalar/LoopPassManager.h" namespace llvm { -class LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> { - const bool AllowPartialUnrolling; +class Function; +class Loop; +class LPMUpdater; + +/// Loop unroll pass that only does full loop unrolling. +class LoopFullUnrollPass : public PassInfoMixin<LoopFullUnrollPass> { const int OptLevel; - explicit LoopUnrollPass(bool AllowPartialUnrolling, int OptLevel) - : AllowPartialUnrolling(AllowPartialUnrolling), OptLevel(OptLevel) {} +public: + explicit LoopFullUnrollPass(int OptLevel = 2) : OptLevel(OptLevel) {} + + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +/// Loop unroll pass that will support both full and partial unrolling. +/// It is a function pass to have access to function and module analyses. +/// It will also put loops into canonical form (simplified and LCSSA). +class LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> { + const int OptLevel; public: - /// Create an instance of the loop unroll pass that will support both full - /// and partial unrolling. - /// /// This uses the target information (or flags) to control the thresholds for /// different unrolling stategies but supports all of them. - static LoopUnrollPass create(int OptLevel = 2) { - return LoopUnrollPass(/*AllowPartialUnrolling*/ true, OptLevel); - } - - /// Create an instance of the loop unroll pass that only does full loop - /// unrolling. - /// - /// This will disable any runtime or partial unrolling. - static LoopUnrollPass createFull(int OptLevel = 2) { - return LoopUnrollPass(/*AllowPartialUnrolling*/ false, OptLevel); - } + explicit LoopUnrollPass(int OptLevel = 2) : OptLevel(OptLevel) {} - PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, - LoopStandardAnalysisResults &AR, LPMUpdater &U); + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; + } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H diff --git a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h index f688e7f19986..ab9dec0311b2 100644 --- a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h +++ b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h @@ -24,7 +24,7 @@ namespace llvm { struct LowerExpectIntrinsicPass : PassInfoMixin<LowerExpectIntrinsicPass> { /// \brief Run the pass over the function. /// - /// This will lower all of th expect intrinsic calls in this function into + /// This will lower all of the expect intrinsic calls in this function into /// branch weight metadata. That metadata will subsequently feed the analysis /// of the probabilities and frequencies of the CFG. After running this pass, /// no more expect intrinsics remain, allowing the rest of the optimizer to diff --git a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h index f52872dd2ea7..046c808bd051 100644 --- a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h +++ b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h @@ -1,4 +1,4 @@ -//===---- MemCpyOptimizer.h - memcpy optimization ---------------*- C++ -*-===// +//===- MemCpyOptimizer.h - memcpy optimization ------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -16,20 +16,27 @@ #define LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/MemoryDependenceAnalysis.h" -#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/PassManager.h" #include <cstdint> #include <functional> namespace llvm { +class AssumptionCache; +class CallInst; +class DominatorTree; +class Function; +class Instruction; +class MemCpyInst; +class MemMoveInst; +class MemoryDependenceResults; +class MemSetInst; +class StoreInst; +class TargetLibraryInfo; +class Value; + class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> { MemoryDependenceResults *MD = nullptr; TargetLibraryInfo *TLI = nullptr; @@ -41,6 +48,7 @@ public: MemCpyOptPass() = default; PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + // Glue for the old PM. bool runImpl(Function &F, MemoryDependenceResults *MD_, TargetLibraryInfo *TLI_, diff --git a/include/llvm/Transforms/Scalar/NaryReassociate.h b/include/llvm/Transforms/Scalar/NaryReassociate.h index f35707eeb3f0..e835bd5f0761 100644 --- a/include/llvm/Transforms/Scalar/NaryReassociate.h +++ b/include/llvm/Transforms/Scalar/NaryReassociate.h @@ -1,4 +1,4 @@ -//===- NaryReassociate.h - Reassociate n-ary expressions ------------------===// +//===- NaryReassociate.h - Reassociate n-ary expressions --------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -81,15 +81,25 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/IR/ValueHandle.h" namespace llvm { + +class AssumptionCache; +class BinaryOperator; +class DataLayout; +class DominatorTree; +class Function; +class GetElementPtrInst; +class Instruction; +class ScalarEvolution; +class SCEV; +class TargetLibraryInfo; +class TargetTransformInfo; +class Type; +class Value; + class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> { public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); @@ -109,6 +119,7 @@ private: // Reassociate GEP for better CSE. Instruction *tryReassociateGEP(GetElementPtrInst *GEP); + // Try splitting GEP at the I-th index and see whether either part can be // CSE'ed. This is a helper function for tryReassociateGEP. // @@ -118,6 +129,7 @@ private: // ..., i-th index). GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP, unsigned I, Type *IndexedType); + // Given GEP's I-th index = LHS + RHS, see whether &Base[..][LHS][..] or // &Base[..][RHS][..] can be CSE'ed and rewrite GEP accordingly. GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP, @@ -146,6 +158,7 @@ private: // \c CandidateExpr. Returns null if not found. Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr, Instruction *Dominatee); + // GetElementPtrInst implicitly sign-extends an index if the index is shorter // than the pointer size. This function returns whether Index is shorter than // GEP's pointer size, i.e., whether Index needs to be sign-extended in order @@ -158,6 +171,7 @@ private: ScalarEvolution *SE; TargetLibraryInfo *TLI; TargetTransformInfo *TTI; + // A lookup table quickly telling which instructions compute the given SCEV. // Note that there can be multiple instructions at different locations // computing to the same SCEV, so we map a SCEV to an instruction list. For @@ -169,6 +183,7 @@ private: // bar(a + b); DenseMap<const SCEV *, SmallVector<WeakTrackingVH, 2>> SeenExprs; }; -} // namespace llvm + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H diff --git a/include/llvm/Transforms/Scalar/NewGVN.h b/include/llvm/Transforms/Scalar/NewGVN.h index d0425aa4345f..05db25502dc3 100644 --- a/include/llvm/Transforms/Scalar/NewGVN.h +++ b/include/llvm/Transforms/Scalar/NewGVN.h @@ -1,4 +1,4 @@ -//===----- NewGVN.h - Global Value Numbering Pass ---------------*- C++ -*-===// +//===- NewGVN.h - Global Value Numbering Pass -------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,9 +6,10 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// /// \file /// This file provides the interface for LLVM's Global Value Numbering pass. -/// +// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SCALAR_NEWGVN_H @@ -17,12 +18,16 @@ #include "llvm/IR/PassManager.h" namespace llvm { + +class Function; + class NewGVNPass : public PassInfoMixin<NewGVNPass> { public: /// \brief Run the pass over the function. PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_NEWGVN_H diff --git a/include/llvm/Transforms/Scalar/Reassociate.h b/include/llvm/Transforms/Scalar/Reassociate.h index a30a7176baa8..9997dfa5b6f3 100644 --- a/include/llvm/Transforms/Scalar/Reassociate.h +++ b/include/llvm/Transforms/Scalar/Reassociate.h @@ -23,22 +23,33 @@ #ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H #define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Operator.h" #include "llvm/IR/PassManager.h" +#include "llvm/IR/ValueHandle.h" namespace llvm { +class APInt; +class BasicBlock; +class BinaryOperator; +class Function; +class Instruction; +class Value; + /// A private "module" namespace for types and utilities used by Reassociate. /// These are implementation details and should not be used by clients. namespace reassociate { + struct ValueEntry { unsigned Rank; Value *Op; + ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} }; + inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. } @@ -48,17 +59,26 @@ inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { struct Factor { Value *Base; unsigned Power; + Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {} }; class XorOpnd; -} + +} // end namespace reassociate /// Reassociate commutative expressions. class ReassociatePass : public PassInfoMixin<ReassociatePass> { DenseMap<BasicBlock *, unsigned> RankMap; DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; SetVector<AssertingVH<Instruction>> RedoInsts; + + // Arbitrary, but prevents quadratic behavior. + static const unsigned GlobalReassociateLimit = 10; + static const unsigned NumBinaryOps = + Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin; + DenseMap<std::pair<Value *, Value *>, unsigned> PairMap[NumBinaryOps]; + bool MadeChange; public: @@ -92,7 +112,9 @@ private: SetVector<AssertingVH<Instruction>> &Insts); void OptimizeInst(Instruction *I); Instruction *canonicalizeNegConstExpr(Instruction *I); + void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H diff --git a/include/llvm/Transforms/Scalar/RewriteStatepointsForGC.h b/include/llvm/Transforms/Scalar/RewriteStatepointsForGC.h new file mode 100644 index 000000000000..128f176f4420 --- /dev/null +++ b/include/llvm/Transforms/Scalar/RewriteStatepointsForGC.h @@ -0,0 +1,39 @@ +//===- RewriteStatepointsForGC.h - ------------------------------*- 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 interface to "Rewrite Statepoints for GC" pass. +// +// This passe rewrites call/invoke instructions so as to make potential +// relocations performed by the garbage collector explicit in the IR. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_REWRITE_STATEPOINTS_FOR_GC_H +#define LLVM_TRANSFORMS_SCALAR_REWRITE_STATEPOINTS_FOR_GC_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class DominatorTree; +class Function; +class Module; +class TargetTransformInfo; +class TargetLibraryInfo; + +struct RewriteStatepointsForGC : public PassInfoMixin<RewriteStatepointsForGC> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); + + bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &, + const TargetLibraryInfo &); +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_REWRITE_STATEPOINTS_FOR_GC_H diff --git a/include/llvm/Transforms/Scalar/SCCP.h b/include/llvm/Transforms/Scalar/SCCP.h index 6e7f77fe2c50..b93287fff907 100644 --- a/include/llvm/Transforms/Scalar/SCCP.h +++ b/include/llvm/Transforms/Scalar/SCCP.h @@ -6,7 +6,8 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -/// \file +// +// \file // This file implements sparse conditional constant propagation and merging: // // Specifically, this: @@ -15,22 +16,23 @@ // * Proves values to be constant, and replaces them with constants // * Proves conditional branches to be unconditional // -/// //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_SCALAR_SCCP_H #define LLVM_TRANSFORMS_SCALAR_SCCP_H -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" namespace llvm { +class Function; + /// This pass performs function-level constant propagation and merging. class SCCPPass : public PassInfoMixin<SCCPPass> { public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -} + +} // 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 3080b75ba894..4a321e75c68b 100644 --- a/include/llvm/Transforms/Scalar/SROA.h +++ b/include/llvm/Transforms/Scalar/SROA.h @@ -17,15 +17,23 @@ #define LLVM_TRANSFORMS_SCALAR_SROA_H #include "llvm/ADT/SetVector.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Function.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/Compiler.h" #include <vector> namespace llvm { +class AllocaInst; +class AssumptionCache; +class DominatorTree; +class Function; +class Instruction; +class LLVMContext; +class PHINode; +class SelectInst; +class Use; + /// A private "module" namespace for types and utilities used by SROA. These /// are implementation details and should not be used by clients. namespace sroa LLVM_LIBRARY_VISIBILITY { @@ -122,7 +130,7 @@ private: bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS); bool runOnAlloca(AllocaInst &AI); void clobberUse(Use &U); - void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas); + bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas); bool promoteAllocas(Function &F); }; diff --git a/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h b/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h index d7282ac6a781..63bfe6373d04 100644 --- a/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h +++ b/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h @@ -36,8 +36,10 @@ namespace llvm { /// of the loop, to make the unswitching opportunity obvious. /// class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> { + bool NonTrivial; + public: - SimpleLoopUnswitchPass() = default; + SimpleLoopUnswitchPass(bool NonTrivial = false) : NonTrivial(NonTrivial) {} PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); @@ -46,7 +48,7 @@ public: /// Create the legacy pass object for the simple loop unswitcher. /// /// See the documentaion for `SimpleLoopUnswitchPass` for details. -Pass *createSimpleLoopUnswitchLegacyPass(); +Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false); } // end namespace llvm diff --git a/include/llvm/Transforms/Scalar/SimplifyCFG.h b/include/llvm/Transforms/Scalar/SimplifyCFG.h index 54b51c405ad4..1afb9c7f954f 100644 --- a/include/llvm/Transforms/Scalar/SimplifyCFG.h +++ b/include/llvm/Transforms/Scalar/SimplifyCFG.h @@ -17,26 +17,34 @@ #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Utils/Local.h" namespace llvm { -/// \brief A pass to simplify and canonicalize the CFG of a function. +/// A pass to simplify and canonicalize the CFG of a function. /// -/// This pass iteratively simplifies the entire CFG of a function, removing -/// unnecessary control flows and bringing it into the canonical form expected -/// by the rest of the mid-level optimizer. +/// This pass iteratively simplifies the entire CFG of a function. It may change +/// or remove control flow to put the CFG into a canonical form expected by +/// other passes of the mid-level optimizer. Depending on the specified options, +/// it may further optimize control-flow to create non-canonical forms. class SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> { - int BonusInstThreshold; - bool LateSimplifyCFG; + SimplifyCFGOptions Options; public: - /// \brief Construct a pass with the default thresholds - /// and switch optimizations. - SimplifyCFGPass(); - - /// \brief Construct a pass with a specific bonus threshold - /// and optional switch optimizations. - SimplifyCFGPass(int BonusInstThreshold, bool LateSimplifyCFG); + /// The default constructor sets the pass options to create canonical IR, + /// rather than optimal IR. That is, by default we bypass transformations that + /// are likely to improve performance but make analysis for other passes more + /// difficult. + SimplifyCFGPass() + : SimplifyCFGPass(SimplifyCFGOptions() + .forwardSwitchCondToPhi(false) + .convertSwitchToLookupTable(false) + .needCanonicalLoops(true) + .sinkCommonInsts(false)) {} + + + /// Construct a pass with optional optimizations. + SimplifyCFGPass(const SimplifyCFGOptions &PassOptions); /// \brief 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 new file mode 100644 index 000000000000..f39e03d22d65 --- /dev/null +++ b/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h @@ -0,0 +1,111 @@ +//===- SpeculateAroundPHIs.h - Speculate around PHIs ------------*- 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_SPECULATEAROUNDPHIS_H +#define LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H + +#include "llvm/ADT/SetVector.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/Compiler.h" +#include <vector> + +namespace llvm { + +/// This pass handles simple speculating of instructions around PHIs when +/// doing so is profitable for a particular target despite duplicated +/// instructions. +/// +/// The motivating example are PHIs of constants which will require +/// materializing the constants along each edge. If the PHI is used by an +/// instruction where the target can materialize the constant as part of the +/// instruction, it is profitable to speculate those instructions around the +/// PHI node. This can reduce dynamic instruction count as well as decrease +/// register pressure. +/// +/// Consider this IR for example: +/// ``` +/// entry: +/// br i1 %flag, label %a, label %b +/// +/// a: +/// br label %exit +/// +/// b: +/// br label %exit +/// +/// exit: +/// %p = phi i32 [ 7, %a ], [ 11, %b ] +/// %sum = add i32 %arg, %p +/// ret i32 %sum +/// ``` +/// To materialize the inputs to this PHI node may require an explicit +/// instruction. For example, on x86 this would turn into something like +/// ``` +/// testq %eax, %eax +/// movl $7, %rNN +/// jne .L +/// movl $11, %rNN +/// .L: +/// addl %edi, %rNN +/// movl %rNN, %eax +/// retq +/// ``` +/// When these constants can be folded directly into another instruction, it +/// would be preferable to avoid the potential for register pressure (above we +/// can easily avoid it, but that isn't always true) and simply duplicate the +/// instruction using the PHI: +/// ``` +/// entry: +/// br i1 %flag, label %a, label %b +/// +/// a: +/// %sum.1 = add i32 %arg, 7 +/// br label %exit +/// +/// b: +/// %sum.2 = add i32 %arg, 11 +/// br label %exit +/// +/// exit: +/// %p = phi i32 [ %sum.1, %a ], [ %sum.2, %b ] +/// ret i32 %p +/// ``` +/// Which will generate something like the following on x86: +/// ``` +/// testq %eax, %eax +/// addl $7, %edi +/// jne .L +/// addl $11, %edi +/// .L: +/// movl %edi, %eax +/// retq +/// ``` +/// +/// It is important to note that this pass is never intended to handle more +/// complex cases where speculating around PHIs allows simplifications of the +/// IR itself or other subsequent optimizations. Those can and should already +/// be handled before this pass is ever run by a more powerful analysis that +/// can reason about equivalences and common subexpressions. Classically, those +/// cases would be handled by a GVN-powered PRE or similar transform. This +/// pass, in contrast, is *only* interested in cases where despite no +/// simplifications to the IR itself, speculation is *faster* to execute. The +/// result of this is that the cost models which are appropriate to consider +/// 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. + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H diff --git a/include/llvm/Transforms/Utils/AddDiscriminators.h b/include/llvm/Transforms/Utils/AddDiscriminators.h index a87758300992..4dad06e6c125 100644 --- a/include/llvm/Transforms/Utils/AddDiscriminators.h +++ b/include/llvm/Transforms/Utils/AddDiscriminators.h @@ -1,4 +1,4 @@ -//===- AddDiscriminators.h -------------------------------------*- C++ -*-===// +//===- AddDiscriminators.h --------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -20,10 +20,13 @@ namespace llvm { +class Function; + class AddDiscriminatorsPass : public PassInfoMixin<AddDiscriminatorsPass> { public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; + } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 85bb053135a6..74f75509f550 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -1,4 +1,4 @@ -//===-- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils ----*- C++ -*-===// +//===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -25,13 +25,17 @@ namespace llvm { -class MemoryDependenceResults; +class BlockFrequencyInfo; +class BranchProbabilityInfo; class DominatorTree; -class LoopInfo; +class Function; class Instruction; +class LoopInfo; class MDNode; +class MemoryDependenceResults; class ReturnInst; class TargetLibraryInfo; +class Value; /// Delete the specified block, which must have no predecessors. void DeleteDeadBlock(BasicBlock *BB); @@ -118,7 +122,6 @@ struct CriticalEdgeSplittingOptions { /// IndirectBrInst. Splitting these edges will almost always create an invalid /// program because the address of the new block won't be the one that is jumped /// to. -/// BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options = CriticalEdgeSplittingOptions()); @@ -194,7 +197,6 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, /// no other analyses. In particular, it does not preserve LoopSimplify /// (because it's complicated to handle the case where one of the edges being /// split is an exit of a loop with other exits). -/// BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, const char *Suffix, DominatorTree *DT = nullptr, @@ -212,7 +214,6 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, /// no other analyses. In particular, it does not preserve LoopSimplify /// (because it's complicated to handle the case where one of the edges being /// split is an exit of a loop with other exits). -/// void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix, const char *Suffix2, @@ -284,6 +285,29 @@ void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse); +// Split critical edges where the source of the edge is an indirectbr +// instruction. This isn't always possible, but we can handle some easy cases. +// This is useful because MI is unable to split such critical edges, +// which means it will not be able to sink instructions along those edges. +// This is especially painful for indirect branches with many successors, where +// we end up having to prepare all outgoing values in the origin block. +// +// Our normal algorithm for splitting critical edges requires us to update +// the outgoing edges of the edge origin block, but for an indirectbr this +// is hard, since it would require finding and updating the block addresses +// the indirect branch uses. But if a block only has a single indirectbr +// predecessor, with the others being regular branches, we can do it in a +// different way. +// Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr. +// We can split D into D0 and D1, where D0 contains only the PHIs from D, +// and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and +// create the following structure: +// A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1 +// If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly. +bool SplitIndirectBrCriticalEdges(Function &F, + BranchProbabilityInfo *BPI = nullptr, + BlockFrequencyInfo *BFI = nullptr); + } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H diff --git a/include/llvm/Transforms/Utils/BypassSlowDivision.h b/include/llvm/Transforms/Utils/BypassSlowDivision.h index af0d60b2625f..6eca5ed2154e 100644 --- a/include/llvm/Transforms/Utils/BypassSlowDivision.h +++ b/include/llvm/Transforms/Utils/BypassSlowDivision.h @@ -1,4 +1,4 @@ -//===- llvm/Transforms/Utils/BypassSlowDivision.h --------------*- C++ -*-===// +//===- llvm/Transforms/Utils/BypassSlowDivision.h ---------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -19,10 +19,44 @@ #define LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H #include "llvm/ADT/DenseMap.h" -#include "llvm/IR/Function.h" +#include "llvm/ADT/DenseMapInfo.h" +#include <cstdint> namespace llvm { +class BasicBlock; +class Value; + +struct DivRemMapKey { + bool SignedOp; + Value *Dividend; + Value *Divisor; + + DivRemMapKey(bool InSignedOp, Value *InDividend, Value *InDivisor) + : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {} +}; + +template <> struct DenseMapInfo<DivRemMapKey> { + static bool isEqual(const DivRemMapKey &Val1, const DivRemMapKey &Val2) { + return Val1.SignedOp == Val2.SignedOp && Val1.Dividend == Val2.Dividend && + Val1.Divisor == Val2.Divisor; + } + + static DivRemMapKey getEmptyKey() { + return DivRemMapKey(false, nullptr, nullptr); + } + + static DivRemMapKey getTombstoneKey() { + return DivRemMapKey(true, nullptr, nullptr); + } + + static unsigned getHashValue(const DivRemMapKey &Val) { + return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^ + reinterpret_cast<uintptr_t>(Val.Divisor)) ^ + (unsigned)Val.SignedOp; + } +}; + /// This optimization identifies DIV instructions in a BB that can be /// profitably bypassed and carried out with a shorter, faster divide. /// @@ -31,6 +65,6 @@ namespace llvm { bool bypassSlowDivision( BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H diff --git a/include/llvm/Transforms/Utils/CallPromotionUtils.h b/include/llvm/Transforms/Utils/CallPromotionUtils.h new file mode 100644 index 000000000000..e0bf85781d81 --- /dev/null +++ b/include/llvm/Transforms/Utils/CallPromotionUtils.h @@ -0,0 +1,44 @@ +//===- CallPromotionUtils.h - Utilities for call promotion ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares utilities useful for promoting indirect call sites to +// direct call sites. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H +#define LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H + +#include "llvm/IR/CallSite.h" + +namespace llvm { + +/// Return true if the given indirect call site can be made to call \p Callee. +/// +/// This function ensures that the number and type of the call site's arguments +/// and return value match those of the given function. If the types do not +/// match exactly, they must at least be bitcast compatible. If \p FailureReason +/// is non-null and the indirect call cannot be promoted, the failure reason +/// will be stored in it. +bool isLegalToPromote(CallSite CS, Function *Callee, + const char **FailureReason = nullptr); + +/// Promote the given indirect call site to conditionally call \p Callee. +/// +/// This function creates an if-then-else structure at the location of the call +/// site. The original call site is promoted and moved into the "then" block. A +/// clone of the indirect call site is placed in the "else" block and returned. +/// If \p BranchWeights is non-null, it will be used to set !prof metadata on +/// the new conditional branch. +Instruction *promoteCallWithIfThenElse(CallSite CS, Function *Callee, + MDNode *BranchWeights = nullptr); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h index 2a8b89d86282..178bae76cef6 100644 --- a/include/llvm/Transforms/Utils/Cloning.h +++ b/include/llvm/Transforms/Utils/Cloning.h @@ -227,12 +227,18 @@ public: /// *inlined* code to minimize the actual inserted code, it must not delete /// code in the caller as users of this routine may have pointers to /// instructions in the caller that need to remain stable. +/// +/// If ForwardVarArgsTo is passed, inlining a function with varargs is allowed +/// and all varargs at the callsite will be passed to any calls to +/// ForwardVarArgsTo. The caller of InlineFunction has to make sure any varargs +/// are only used by ForwardVarArgsTo. bool InlineFunction(CallInst *C, InlineFunctionInfo &IFI, AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); bool InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI, AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI, - AAResults *CalleeAAR = nullptr, bool InsertLifetime = true); + AAResults *CalleeAAR = nullptr, bool InsertLifetime = true, + Function *ForwardVarArgsTo = nullptr); /// \brief Clones a loop \p OrigLoop. Returns the loop and the blocks in \p /// Blocks. diff --git a/include/llvm/Transforms/Utils/CmpInstAnalysis.h b/include/llvm/Transforms/Utils/CmpInstAnalysis.h deleted file mode 100644 index 5ec3888d4538..000000000000 --- a/include/llvm/Transforms/Utils/CmpInstAnalysis.h +++ /dev/null @@ -1,70 +0,0 @@ -//===-- CmpInstAnalysis.h - Utils to help fold compare insts ----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file holds routines to help analyse compare instructions -// and fold them into constants or other compare instructions -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H -#define LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H - -#include "llvm/IR/InstrTypes.h" - -namespace llvm { - class ICmpInst; - class Value; - - /// Encode a icmp predicate into a three bit mask. These bits are carefully - /// arranged to allow folding of expressions such as: - /// - /// (A < B) | (A > B) --> (A != B) - /// - /// Note that this is only valid if the first and second predicates have the - /// same sign. It is illegal to do: (A u< B) | (A s> B) - /// - /// Three bits are used to represent the condition, as follows: - /// 0 A > B - /// 1 A == B - /// 2 A < B - /// - /// <=> Value Definition - /// 000 0 Always false - /// 001 1 A > B - /// 010 2 A == B - /// 011 3 A >= B - /// 100 4 A < B - /// 101 5 A != B - /// 110 6 A <= B - /// 111 7 Always true - /// - unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred = false); - - /// This is the complement of getICmpCode, which turns an opcode and two - /// operands into either a constant true or false, or the predicate for a new - /// ICmp instruction. The sign is passed in to determine which kind of - /// predicate to use in the new icmp instruction. - /// Non-NULL return value will be a true or false constant. - /// NULL return means a new ICmp is needed. The predicate for which is output - /// in NewICmpPred. - Value *getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, - CmpInst::Predicate &NewICmpPred); - - /// Return true if both predicates match sign or if at least one of them is an - /// equality comparison (which is signless). - bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2); - - /// Decompose an icmp into the form ((X & Y) pred Z) if possible. The returned - /// predicate is either == or !=. Returns false if decomposition fails. - bool decomposeBitTestICmp(const ICmpInst *I, CmpInst::Predicate &Pred, - Value *&X, Value *&Y, Value *&Z); - -} // end namespace llvm - -#endif diff --git a/include/llvm/Transforms/Utils/CodeExtractor.h b/include/llvm/Transforms/Utils/CodeExtractor.h index 682b353ab5ae..63d34511102d 100644 --- a/include/llvm/Transforms/Utils/CodeExtractor.h +++ b/include/llvm/Transforms/Utils/CodeExtractor.h @@ -1,4 +1,4 @@ -//===-- Transform/Utils/CodeExtractor.h - Code extraction util --*- C++ -*-===// +//===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,22 +15,24 @@ #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SetVector.h" +#include <limits> namespace llvm { -template <typename T> class ArrayRef; - class BasicBlock; - class BlockFrequency; - class BlockFrequencyInfo; - class BranchProbabilityInfo; - class DominatorTree; - class Function; - class Instruction; - class Loop; - class Module; - class RegionNode; - class Type; - class Value; + +class BasicBlock; +class BlockFrequency; +class BlockFrequencyInfo; +class BranchProbabilityInfo; +class DominatorTree; +class Function; +class Instruction; +class Loop; +class Module; +class Type; +class Value; /// \brief Utility class for extracting code into a new function. /// @@ -46,7 +48,7 @@ template <typename T> class ArrayRef; /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas /// as arguments, and inserting stores to the arguments for any scalars. class CodeExtractor { - typedef SetVector<Value *> ValueSet; + using ValueSet = SetVector<Value *>; // Various bits of state computed on construction. DominatorTree *const DT; @@ -54,27 +56,27 @@ template <typename T> class ArrayRef; BlockFrequencyInfo *BFI; BranchProbabilityInfo *BPI; + // If true, varargs functions can be extracted. + bool AllowVarArgs; + // Bits of intermediate state computed at various phases of extraction. SetVector<BasicBlock *> Blocks; - unsigned NumExitBlocks; + unsigned NumExitBlocks = std::numeric_limits<unsigned>::max(); Type *RetTy; public: - - /// \brief Check to see if a block is valid for extraction. - /// - /// Blocks containing EHPads, allocas, invokes, or vastarts are not valid. - static bool isBlockValidForExtraction(const BasicBlock &BB); - /// \brief Create a code extractor for a sequence of blocks. /// /// Given a sequence of basic blocks where the first block in the sequence /// dominates the rest, prepare a code extractor object for pulling this /// sequence out into its new function. When a DominatorTree is also given, - /// extra checking and transformations are enabled. + /// extra checking and transformations are enabled. If AllowVarArgs is true, + /// vararg functions can be extracted. This is safe, if all vararg handling + /// code is extracted, including vastart. CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, - BranchProbabilityInfo *BPI = nullptr); + BranchProbabilityInfo *BPI = nullptr, + bool AllowVarArgs = false); /// \brief Create a code extractor for a loop body. /// @@ -84,6 +86,14 @@ template <typename T> class ArrayRef; BlockFrequencyInfo *BFI = nullptr, BranchProbabilityInfo *BPI = nullptr); + /// \brief Check to see if a block is valid for extraction. + /// + /// Blocks containing EHPads, allocas and invokes are not valid. If + /// AllowVarArgs is true, blocks with vastart can be extracted. This is + /// safe, if all vararg handling code is extracted, including vastart. + static bool isBlockValidForExtraction(const BasicBlock &BB, + bool AllowVarArgs); + /// \brief Perform the extraction, returning the new function. /// /// Returns zero when called on a CodeExtractor instance where isEligible @@ -112,6 +122,7 @@ template <typename T> class ArrayRef; /// /// Returns true if it is safe to do the code motion. bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const; + /// Find the set of allocas whose life ranges are contained within the /// outlined region. /// @@ -155,6 +166,7 @@ template <typename T> class ArrayRef; ValueSet &inputs, ValueSet &outputs); }; -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H diff --git a/include/llvm/Transforms/Utils/EntryExitInstrumenter.h b/include/llvm/Transforms/Utils/EntryExitInstrumenter.h new file mode 100644 index 000000000000..f50c5c922081 --- /dev/null +++ b/include/llvm/Transforms/Utils/EntryExitInstrumenter.h @@ -0,0 +1,36 @@ +//===- EntryExitInstrumenter.h - Function Entry/Exit Instrumentation ------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// EntryExitInstrumenter pass - Instrument function entry/exit with calls to +// mcount(), @__cyg_profile_func_{enter,exit} and the like. There are two +// variants, intended to run pre- and post-inlining, respectively. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H +#define LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Function; + +struct EntryExitInstrumenterPass + : public PassInfoMixin<EntryExitInstrumenterPass> { + EntryExitInstrumenterPass(bool PostInlining) : PostInlining(PostInlining) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + bool PostInlining; +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H diff --git a/include/llvm/Transforms/Utils/Evaluator.h b/include/llvm/Transforms/Utils/Evaluator.h index 07f12f41b3bc..0e987b93177a 100644 --- a/include/llvm/Transforms/Utils/Evaluator.h +++ b/include/llvm/Transforms/Utils/Evaluator.h @@ -1,4 +1,4 @@ -//===-- Evaluator.h - LLVM IR evaluator -------------------------*- C++ -*-===// +//===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -18,9 +18,10 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Constant.h" #include "llvm/IR/GlobalVariable.h" - +#include "llvm/IR/Value.h" +#include "llvm/Support/Casting.h" +#include <cassert> #include <deque> #include <memory> @@ -114,6 +115,6 @@ private: const TargetLibraryInfo *TLI; }; -} +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H diff --git a/include/llvm/Transforms/Utils/FunctionComparator.h b/include/llvm/Transforms/Utils/FunctionComparator.h index b0f10eafaa95..7698a068717a 100644 --- a/include/llvm/Transforms/Utils/FunctionComparator.h +++ b/include/llvm/Transforms/Utils/FunctionComparator.h @@ -15,10 +15,10 @@ #ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H #define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H -#include "llvm/ADT/APFloat.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringRef.h" -#include "llvm/IR/Function.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" #include "llvm/IR/ValueMap.h" #include "llvm/Support/AtomicOrdering.h" @@ -28,7 +28,17 @@ namespace llvm { -class GetElementPtrInst; +class APFloat; +class APInt; +class BasicBlock; +class Constant; +class Function; +class GlobalValue; +class InlineAsm; +class Instruction; +class MDNode; +class Type; +class Value; /// GlobalNumberState assigns an integer to each global value in the program, /// which is used by the comparison routine to order references to globals. This @@ -43,14 +53,16 @@ class GetElementPtrInst; /// compare those, but this would not work for stripped bitcodes or for those /// few symbols without a name. class GlobalNumberState { - struct Config : ValueMapConfig<GlobalValue*> { + struct Config : ValueMapConfig<GlobalValue *> { enum { FollowRAUW = false }; }; + // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW // occurs, the mapping does not change. Tracking changes is unnecessary, and // also problematic for weak symbols (which may be overwritten). - typedef ValueMap<GlobalValue *, uint64_t, Config> ValueNumberMap; + using ValueNumberMap = ValueMap<GlobalValue *, uint64_t, Config>; ValueNumberMap GlobalNumbers; + // The next unused serial number to assign to a global. uint64_t NextNumber = 0; @@ -66,6 +78,10 @@ public: return MapIter->second; } + void erase(GlobalValue *Global) { + GlobalNumbers.erase(Global); + } + void clear() { GlobalNumbers.clear(); } @@ -83,9 +99,10 @@ public: /// Test whether the two functions have equivalent behaviour. int compare(); + /// Hash a function. Equivalent functions will have the same hash, and unequal /// functions will have different hashes with high probability. - typedef uint64_t FunctionHash; + using FunctionHash = uint64_t; static FunctionHash functionHash(Function &); protected: diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 30b27616cd98..01db88bc15c2 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -1,4 +1,4 @@ -//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===// +//===- Local.h - Functions to perform local transformations -----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,39 +15,95 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H #define LLVM_TRANSFORMS_UTILS_LOCAL_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" -#include "llvm/IR/IRBuilder.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Support/Casting.h" +#include <cstdint> +#include <limits> namespace llvm { -class User; +class AllocaInst; +class AssumptionCache; class BasicBlock; -class Function; class BranchInst; -class Instruction; class CallInst; -class DbgDeclareInst; +class DbgInfoIntrinsic; class DbgValueInst; -class StoreInst; +class DIBuilder; +class Function; +class Instruction; +class LazyValueInfo; class LoadInst; -class Value; +class MDNode; class PHINode; -class AllocaInst; -class AssumptionCache; -class ConstantExpr; -class DataLayout; +class StoreInst; class TargetLibraryInfo; class TargetTransformInfo; -class DIBuilder; -class DominatorTree; -class LazyValueInfo; -template<typename T> class SmallVectorImpl; +/// A set of parameters used to control the transforms in the SimplifyCFG pass. +/// Options may change depending on the position in the optimization pipeline. +/// For example, canonical form that includes switches and branches may later be +/// replaced by lookup tables and selects. +struct SimplifyCFGOptions { + int BonusInstThreshold; + bool ForwardSwitchCondToPhi; + bool ConvertSwitchToLookupTable; + bool NeedCanonicalLoop; + bool SinkCommonInsts; + AssumptionCache *AC; + + SimplifyCFGOptions(unsigned BonusThreshold = 1, + bool ForwardSwitchCond = false, + bool SwitchToLookup = false, bool CanonicalLoops = true, + bool SinkCommon = false, + AssumptionCache *AssumpCache = nullptr) + : BonusInstThreshold(BonusThreshold), + ForwardSwitchCondToPhi(ForwardSwitchCond), + ConvertSwitchToLookupTable(SwitchToLookup), + NeedCanonicalLoop(CanonicalLoops), + SinkCommonInsts(SinkCommon), + AC(AssumpCache) {} + + // Support 'builder' pattern to set members by name at construction time. + SimplifyCFGOptions &bonusInstThreshold(int I) { + BonusInstThreshold = I; + return *this; + } + SimplifyCFGOptions &forwardSwitchCondToPhi(bool B) { + ForwardSwitchCondToPhi = B; + return *this; + } + SimplifyCFGOptions &convertSwitchToLookupTable(bool B) { + ConvertSwitchToLookupTable = B; + return *this; + } + SimplifyCFGOptions &needCanonicalLoops(bool B) { + NeedCanonicalLoop = B; + return *this; + } + SimplifyCFGOptions &sinkCommonInsts(bool B) { + SinkCommonInsts = B; + return *this; + } + SimplifyCFGOptions &setAssumptionCache(AssumptionCache *Cache) { + AC = Cache; + return *this; + } +}; //===----------------------------------------------------------------------===// // Local constant propagation. @@ -133,17 +189,15 @@ bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); /// values, but instcombine orders them so it usually won't matter. bool EliminateDuplicatePHINodes(BasicBlock *BB); -/// This function is used to do simplification of a CFG. For -/// example, it adjusts branches to branches to eliminate the extra hop, it -/// eliminates unreachable basic blocks, and does other "peephole" optimization -/// of the CFG. It returns true if a modification was made, possibly deleting -/// the basic block that was pointed to. LoopHeaders is an optional input -/// parameter, providing the set of loop header that SimplifyCFG should not -/// eliminate. -bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, - SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr, - bool LateSimplifyCFG = false); +/// This function is used to do simplification of a CFG. For example, it +/// adjusts branches to branches to eliminate the extra hop, it eliminates +/// unreachable basic blocks, and does other peephole optimization of the CFG. +/// It returns true if a modification was made, possibly deleting the basic +/// block that was pointed to. LoopHeaders is an optional input parameter +/// providing the set of loop headers that SimplifyCFG should not eliminate. +bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, + const SimplifyCFGOptions &Options = {}, + SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr); /// This function is used to flatten a CFG. For example, it uses parallel-and /// and parallel-or mode to collapse if-conditions and merge if-regions with @@ -185,10 +239,10 @@ unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DominatorTree *DT = nullptr); /// Try to infer an alignment for the specified pointer. -static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, - const Instruction *CxtI = nullptr, - AssumptionCache *AC = nullptr, - const DominatorTree *DT = nullptr) { +inline unsigned getKnownAlignment(Value *V, const DataLayout &DL, + const Instruction *CxtI = nullptr, + AssumptionCache *AC = nullptr, + const DominatorTree *DT = nullptr) { return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT); } @@ -210,7 +264,8 @@ Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, // Build a mask for high order bits. unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth(); - uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth); + uint64_t PtrSizeMask = + std::numeric_limits<uint64_t>::max() >> (64 - IntPtrWidth); gep_type_iterator GTI = gep_type_begin(GEP); for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; @@ -262,46 +317,50 @@ Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, /// /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value -/// that has an associated llvm.dbg.decl intrinsic. -void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, +/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, StoreInst *SI, DIBuilder &Builder); /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value -/// that has an associated llvm.dbg.decl intrinsic. -void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, +/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, LoadInst *LI, DIBuilder &Builder); -/// Inserts a llvm.dbg.value intrinsic after a phi of an alloca'd value -/// that has an associated llvm.dbg.decl intrinsic. -void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, +/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated +/// llvm.dbg.declare or llvm.dbg.addr intrinsic. +void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, PHINode *LI, DIBuilder &Builder); /// Lowers llvm.dbg.declare intrinsics into appropriate set of /// llvm.dbg.value intrinsics. bool LowerDbgDeclare(Function &F); -/// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any. -DbgDeclareInst *FindAllocaDbgDeclare(Value *V); +/// Finds all intrinsics declaring local variables as living in the memory that +/// 'V' points to. This may include a mix of dbg.declare and +/// dbg.addr intrinsics. +TinyPtrVector<DbgInfoIntrinsic *> FindDbgAddrUses(Value *V); /// Finds the llvm.dbg.value intrinsics describing a value. void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V); -/// Replaces llvm.dbg.declare instruction when the address it describes -/// is replaced with a new value. If Deref is true, an additional DW_OP_deref is -/// prepended to the expression. If Offset is non-zero, a constant displacement -/// is added to the expression (after the optional Deref). Offset can be -/// negative. +/// Replaces llvm.dbg.declare instruction when the address it +/// describes is replaced with a new value. If Deref is true, an +/// additional DW_OP_deref is prepended to the expression. If Offset +/// is non-zero, a constant displacement is added to the expression +/// (between the optional Deref operations). Offset can be negative. bool replaceDbgDeclare(Value *Address, Value *NewAddress, Instruction *InsertBefore, DIBuilder &Builder, - bool Deref, int Offset); + bool DerefBefore, int Offset, bool DerefAfter); /// Replaces llvm.dbg.declare instruction when the alloca it describes -/// is replaced with a new value. If Deref is true, an additional DW_OP_deref is -/// prepended to the expression. If Offset is non-zero, a constant displacement -/// is added to the expression (after the optional Deref). Offset can be -/// negative. New llvm.dbg.declare is inserted immediately before AI. +/// is replaced with a new value. If Deref is true, an additional +/// DW_OP_deref is prepended to the expression. If Offset is non-zero, +/// a constant displacement is added to the expression (between the +/// optional Deref operations). Offset can be negative. The new +/// llvm.dbg.declare is inserted immediately before AI. bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, - DIBuilder &Builder, bool Deref, int Offset = 0); + DIBuilder &Builder, bool DerefBefore, + int Offset, bool DerefAfter); /// Replaces multiple llvm.dbg.value instructions when the alloca it describes /// is replaced with a new value. If Offset is non-zero, a constant displacement @@ -369,7 +428,6 @@ unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB); - /// Return true if the CallSite CS calls a gc leaf function. /// /// A leaf function is a function that does not safepoint the thread during its @@ -378,7 +436,7 @@ unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, /// /// Most passes can and should ignore this information, and it is only used /// during lowering by the GC infrastructure. -bool callsGCLeafFunction(ImmutableCallSite CS); +bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI); /// Copy a nonnull metadata node to a new load instruction. /// @@ -397,7 +455,7 @@ void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, // Intrinsic pattern matching // -/// Try and match a bswap or bitreverse idiom. +/// Try to match a bswap or bitreverse idiom. /// /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added /// instructions are returned in \c InsertedInsts. They will all have been added @@ -431,6 +489,6 @@ void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, /// value? bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_LOCAL_H diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 94e20b83754e..750666136507 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -16,6 +16,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" @@ -305,10 +306,13 @@ public: /// induction, the induction descriptor \p D will contain the data describing /// this induction. If by some other means the caller has a better SCEV /// expression for \p Phi than the one returned by the ScalarEvolution - /// analysis, it can be passed through \p Expr. - static bool isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, - InductionDescriptor &D, - const SCEV *Expr = nullptr); + /// analysis, it can be passed through \p Expr. If the def-use chain + /// associated with the phi includes casts (that we know we can ignore + /// under proper runtime checks), they are passed through \p CastsToIgnore. + static bool + isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE, + InductionDescriptor &D, const SCEV *Expr = nullptr, + SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr); /// Returns true if \p Phi is a floating point induction in the loop \p L. /// If \p Phi is an induction, the induction descriptor \p D will contain @@ -330,15 +334,13 @@ public: /// not have the "fast-math" property. Such operation requires a relaxed FP /// mode. bool hasUnsafeAlgebra() { - return InductionBinOp && - !cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra(); + return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast(); } /// Returns induction operator that does not have "fast-math" property /// and requires FP unsafe mode. Instruction *getUnsafeAlgebraInst() { - if (!InductionBinOp || - cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra()) + if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast()) return nullptr; return InductionBinOp; } @@ -349,10 +351,18 @@ public: Instruction::BinaryOpsEnd; } + /// Returns a reference to the type cast instructions in the induction + /// update chain, that are redundant when guarded with a runtime + /// SCEV overflow check. + const SmallVectorImpl<Instruction *> &getCastInsts() const { + return RedundantCasts; + } + private: /// Private constructor - used by \c isInductionPHI. InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step, - BinaryOperator *InductionBinOp = nullptr); + BinaryOperator *InductionBinOp = nullptr, + SmallVectorImpl<Instruction *> *Casts = nullptr); /// Start value. TrackingVH<Value> StartValue; @@ -362,6 +372,9 @@ private: const SCEV *Step = nullptr; // Instruction that advances induction variable. BinaryOperator *InductionBinOp = nullptr; + // Instructions used for type-casts of the induction variable, + // that are redundant when guarded with a runtime SCEV overflow check. + SmallVector<Instruction *, 2> RedundantCasts; }; BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, @@ -423,8 +436,9 @@ bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, /// instructions of the loop and loop safety information as /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, - TargetLibraryInfo *, Loop *, AliasSetTracker *, - LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); + TargetLibraryInfo *, TargetTransformInfo *, Loop *, + AliasSetTracker *, LoopSafetyInfo *, + OptimizationRemarkEmitter *ORE); /// \brief Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -438,21 +452,41 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); +/// This function deletes dead loops. The caller of this function needs to +/// guarantee that the loop is infact dead. +/// The function requires a bunch or prerequisites to be present: +/// - The loop needs to be in LCSSA form +/// - The loop needs to have a Preheader +/// - A unique dedicated exit block must exist +/// +/// This also updates the relevant analysis information in \p DT, \p SE, and \p +/// LI if pointers to those are provided. +/// It also updates the loop PM if an updater struct is provided. + +void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, + LoopInfo *LI); + /// \brief Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over /// the stores in the loop, looking for stores to Must pointers which are -/// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks -/// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop, -/// AliasSet information for all instructions of the loop and loop safety -/// information as arguments. Diagnostics is emitted via \p ORE. It returns -/// changed status. -bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &, +/// loop invariant. It takes a set of must-alias values, Loop exit blocks +/// vector, loop exit blocks insertion point vector, PredIteratorCache, +/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions +/// of the loop and loop safety information as arguments. +/// Diagnostics is emitted via \p ORE. It returns changed status. +bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &, + SmallVectorImpl<BasicBlock *> &, SmallVectorImpl<Instruction *> &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *); +/// Does a BFS from a given node to all of its children inside a given loop. +/// The returned vector of nodes includes the starting point. +SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N, + const Loop *CurLoop); + /// \brief Computes safety information for a loop /// checks loop body & header for the possibility of may throw /// exception, it takes LoopSafetyInfo and loop as argument. diff --git a/include/llvm/Transforms/Utils/LowerMemIntrinsics.h b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h index 4554b5cbc644..2b7d0f67a324 100644 --- a/include/llvm/Transforms/Utils/LowerMemIntrinsics.h +++ b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h @@ -25,12 +25,6 @@ class MemSetInst; class TargetTransformInfo; class Value; -/// Emit a loop implementing the semantics of llvm.memcpy with the equivalent -/// arguments at \p InsertBefore. -void createMemCpyLoop(Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr, - Value *CopyLen, unsigned SrcAlign, unsigned DestAlign, - bool SrcIsVolatile, bool DstIsVolatile); - /// Emit a loop implementing the semantics of llvm.memcpy where the size is not /// a compile-time constant. Loop will be insterted at \p InsertBefore. void createMemCpyLoopUnknownSize(Instruction *InsertBefore, Value *SrcAddr, diff --git a/include/llvm/Transforms/Utils/Mem2Reg.h b/include/llvm/Transforms/Utils/Mem2Reg.h index 1fe186d6c3ad..407684338a3b 100644 --- a/include/llvm/Transforms/Utils/Mem2Reg.h +++ b/include/llvm/Transforms/Utils/Mem2Reg.h @@ -15,14 +15,17 @@ #ifndef LLVM_TRANSFORMS_UTILS_MEM2REG_H #define LLVM_TRANSFORMS_UTILS_MEM2REG_H -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" namespace llvm { + +class Function; + class PromotePass : public PassInfoMixin<PromotePass> { public: PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_MEM2REG_H diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h index e9793fe4b666..4b9bc8293810 100644 --- a/include/llvm/Transforms/Utils/ModuleUtils.h +++ b/include/llvm/Transforms/Utils/ModuleUtils.h @@ -85,7 +85,8 @@ void filterDeadComdatFunctions( Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions); /// \brief Produce a unique identifier for this module by taking the MD5 sum of -/// the names of the module's strong external symbols. +/// the names of the module's strong external symbols that are not comdat +/// members. /// /// This identifier is normally guaranteed to be unique, or the program would /// fail to link due to multiply defined symbols. diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 8cbcdf47156e..6cd9f1539b0b 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -1,4 +1,4 @@ -//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===// +//===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,6 +14,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringRef.h" #include <string> @@ -22,10 +23,9 @@ namespace llvm { class BasicBlock; class Instruction; class LoadInst; -template <typename T> class ArrayRef; +class PHINode; template <typename T> class SmallVectorImpl; template <typename T> class SSAUpdaterTraits; -class PHINode; class Type; class Use; class Value; @@ -42,7 +42,6 @@ class SSAUpdater { private: /// This keeps track of which value to use on a per-block basis. When we /// insert PHI nodes, we keep track of them here. - //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; void *AV = nullptr; /// ProtoType holds the type of the values being rewritten. @@ -53,12 +52,12 @@ private: /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to /// the vector. - SmallVectorImpl<PHINode*> *InsertedPHIs; + SmallVectorImpl<PHINode *> *InsertedPHIs; public: /// If InsertedPHIs is specified, it will be filled /// in with all PHI Nodes created by rewriting. - explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = nullptr); + explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); SSAUpdater(const SSAUpdater &) = delete; SSAUpdater &operator=(const SSAUpdater &) = delete; ~SSAUpdater(); @@ -136,7 +135,7 @@ protected: SSAUpdater &SSA; public: - LoadAndStorePromoter(ArrayRef<const Instruction*> Insts, + LoadAndStorePromoter(ArrayRef<const Instruction *> Insts, SSAUpdater &S, StringRef Name = StringRef()); virtual ~LoadAndStorePromoter() = default; @@ -145,32 +144,28 @@ public: /// Insts is a list of loads and stores to promote, and Name is the basename /// for the PHIs to insert. After this is complete, the loads and stores are /// removed from the code. - void run(const SmallVectorImpl<Instruction*> &Insts) const; + void run(const SmallVectorImpl<Instruction *> &Insts) const; /// \brief Return true if the specified instruction is in the Inst list. /// /// The Insts list is the one passed into the constructor. Clients should /// implement this with a more efficient version if possible. virtual bool isInstInList(Instruction *I, - const SmallVectorImpl<Instruction*> &Insts) const; + const SmallVectorImpl<Instruction *> &Insts) const; /// \brief This hook is invoked after all the stores are found and inserted as /// available values. - virtual void doExtraRewritesBeforeFinalDeletion() const { - } + virtual void doExtraRewritesBeforeFinalDeletion() const {} /// \brief Clients can choose to implement this to get notified right before /// a load is RAUW'd another value. - virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const { - } + virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {} /// \brief Called before each instruction is deleted. - virtual void instructionDeleted(Instruction *I) const { - } + virtual void instructionDeleted(Instruction *I) const {} /// \brief Called to update debug info associated with the instruction. - virtual void updateDebugInfo(Instruction *I) const { - } + virtual void updateDebugInfo(Instruction *I) const {} }; } // end namespace llvm diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h index 2dd205d8b2af..b1611d49a456 100644 --- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -1,4 +1,4 @@ -//===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===// +//===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -17,17 +17,14 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #define DEBUG_TYPE "ssaupdater" namespace llvm { -class CastInst; -class PHINode; template<typename T> class SSAUpdaterTraits; template<typename UpdaterT> @@ -35,51 +32,67 @@ class SSAUpdaterImpl { private: UpdaterT *Updater; - typedef SSAUpdaterTraits<UpdaterT> Traits; - typedef typename Traits::BlkT BlkT; - typedef typename Traits::ValT ValT; - typedef typename Traits::PhiT PhiT; + using Traits = SSAUpdaterTraits<UpdaterT>; + using BlkT = typename Traits::BlkT; + using ValT = typename Traits::ValT; + using PhiT = typename Traits::PhiT; /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl. /// The predecessors of each block are cached here since pred_iterator is /// slow and we need to iterate over the blocks at least a few times. class BBInfo { public: - BlkT *BB; // Back-pointer to the corresponding block. - ValT AvailableVal; // Value to use in this block. - BBInfo *DefBB; // Block that defines the available value. - int BlkNum; // Postorder number. - BBInfo *IDom; // Immediate dominator. - unsigned NumPreds; // Number of predecessor blocks. - BBInfo **Preds; // Array[NumPreds] of predecessor blocks. - PhiT *PHITag; // Marker for existing PHIs that match. + // Back-pointer to the corresponding block. + BlkT *BB; + + // Value to use in this block. + ValT AvailableVal; + + // Block that defines the available value. + BBInfo *DefBB; + + // Postorder number. + int BlkNum = 0; + + // Immediate dominator. + BBInfo *IDom = nullptr; + + // Number of predecessor blocks. + unsigned NumPreds = 0; + + // Array[NumPreds] of predecessor blocks. + BBInfo **Preds = nullptr; + + // Marker for existing PHIs that match. + PhiT *PHITag = nullptr; BBInfo(BlkT *ThisBB, ValT V) - : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr), BlkNum(0), - IDom(nullptr), NumPreds(0), Preds(nullptr), PHITag(nullptr) {} + : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {} }; - typedef DenseMap<BlkT*, ValT> AvailableValsTy; + using AvailableValsTy = DenseMap<BlkT *, ValT>; + AvailableValsTy *AvailableVals; - SmallVectorImpl<PhiT*> *InsertedPHIs; + SmallVectorImpl<PhiT *> *InsertedPHIs; + + using BlockListTy = SmallVectorImpl<BBInfo *>; + using BBMapTy = DenseMap<BlkT *, BBInfo *>; - typedef SmallVectorImpl<BBInfo*> BlockListTy; - typedef DenseMap<BlkT*, BBInfo*> BBMapTy; BBMapTy BBMap; BumpPtrAllocator Allocator; public: explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, - SmallVectorImpl<PhiT*> *Ins) : - Updater(U), AvailableVals(A), InsertedPHIs(Ins) { } + SmallVectorImpl<PhiT *> *Ins) : + Updater(U), AvailableVals(A), InsertedPHIs(Ins) {} /// GetValue - Check to see if AvailableVals has an entry for the specified /// BB and if so, return it. If not, construct SSA form by first /// calculating the required placement of PHIs and then inserting new PHIs /// where needed. ValT GetValue(BlkT *BB) { - SmallVector<BBInfo*, 100> BlockList; + SmallVector<BBInfo *, 100> BlockList; BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList); // Special case: bail out if BB is unreachable. @@ -101,8 +114,8 @@ public: /// Create BBInfo structures for the blocks and append them to the block /// list. BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) { - SmallVector<BBInfo*, 10> RootList; - SmallVector<BBInfo*, 64> WorkList; + SmallVector<BBInfo *, 10> RootList; + SmallVector<BBInfo *, 64> WorkList; BBInfo *Info = new (Allocator) BBInfo(BB, 0); BBMap[BB] = Info; @@ -111,7 +124,7 @@ public: // Search backward from BB, creating BBInfos along the way and stopping // when reaching blocks that define the value. Record those defining // blocks on the RootList. - SmallVector<BlkT*, 10> Preds; + SmallVector<BlkT *, 10> Preds; while (!WorkList.empty()) { Info = WorkList.pop_back_val(); Preds.clear(); @@ -395,7 +408,7 @@ public: /// CheckIfPHIMatches - Check if a PHI node matches the placement and values /// in the BBMap. bool CheckIfPHIMatches(PhiT *PHI) { - SmallVector<PhiT*, 20> WorkList; + SmallVector<PhiT *, 20> WorkList; WorkList.push_back(PHI); // Mark that the block containing this PHI has been visited. @@ -453,7 +466,7 @@ public: } }; -} // end llvm namespace +} // end namespace llvm #undef DEBUG_TYPE // "ssaupdater" diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index 8d50aeb10d6e..a1dfed29a22d 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -26,6 +26,7 @@ class Loop; class LoopInfo; class PHINode; class ScalarEvolution; +class SCEVExpander; /// Interface for visiting interesting IV users that are recognized but not /// simplified by this utility. @@ -47,7 +48,7 @@ public: /// by using ScalarEvolution to analyze the IV's recurrence. bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead, - IVVisitor *V = nullptr); + SCEVExpander &Rewriter, IVVisitor *V = nullptr); /// SimplifyLoopIVs - Simplify users of induction variables within this /// loop. This does not actually change or add IVs. diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h index 6aba9b2298b1..73a62f59203b 100644 --- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -28,6 +28,7 @@ class Instruction; class TargetLibraryInfo; class BasicBlock; class Function; +class OptimizationRemarkEmitter; /// \brief This class implements simplifications for calls to fortified library /// functions (__st*cpy_chk, __memcpy_chk, __memmove_chk, __memset_chk), to, @@ -73,6 +74,7 @@ private: FortifiedLibCallSimplifier FortifiedSimplifier; const DataLayout &DL; const TargetLibraryInfo *TLI; + OptimizationRemarkEmitter &ORE; bool UnsafeFPShrink; function_ref<void(Instruction *, Value *)> Replacer; @@ -87,6 +89,7 @@ private: public: LibCallSimplifier(const DataLayout &DL, const TargetLibraryInfo *TLI, + OptimizationRemarkEmitter &ORE, function_ref<void(Instruction *, Value *)> Replacer = &replaceAllUsesWithDefault); @@ -126,14 +129,19 @@ private: Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B); // Math Library Optimizations + Value *optimizeCAbs(CallInst *CI, IRBuilder<> &B); Value *optimizeCos(CallInst *CI, IRBuilder<> &B); Value *optimizePow(CallInst *CI, IRBuilder<> &B); + Value *replacePowWithSqrt(CallInst *Pow, IRBuilder<> &B); Value *optimizeExp2(CallInst *CI, IRBuilder<> &B); Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B); Value *optimizeLog(CallInst *CI, IRBuilder<> &B); Value *optimizeSqrt(CallInst *CI, IRBuilder<> &B); Value *optimizeSinCosPi(CallInst *CI, IRBuilder<> &B); Value *optimizeTan(CallInst *CI, IRBuilder<> &B); + // Wrapper for all floating point library call optimizations + Value *optimizeFloatingPointLibCall(CallInst *CI, LibFunc Func, + IRBuilder<> &B); // Integer Library Call Optimizations Value *optimizeFFS(CallInst *CI, IRBuilder<> &B); diff --git a/include/llvm/Transforms/Utils/SplitModule.h b/include/llvm/Transforms/Utils/SplitModule.h index b7a3bcf4f86a..d2c31f2701ac 100644 --- a/include/llvm/Transforms/Utils/SplitModule.h +++ b/include/llvm/Transforms/Utils/SplitModule.h @@ -22,7 +22,6 @@ namespace llvm { class Module; -class StringRef; /// Splits the module M into N linkable partitions. The function ModuleCallback /// is called N times passing each individual partition as the MPart argument. @@ -39,6 +38,6 @@ void SplitModule( function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback, bool PreserveLocals = false); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_TRANSFORMS_UTILS_SPLITMODULE_H diff --git a/include/llvm/Transforms/Utils/SymbolRewriter.h b/include/llvm/Transforms/Utils/SymbolRewriter.h index 93658989fba5..e0caf7741ff3 100644 --- a/include/llvm/Transforms/Utils/SymbolRewriter.h +++ b/include/llvm/Transforms/Utils/SymbolRewriter.h @@ -1,4 +1,4 @@ -//===-- SymbolRewriter.h - Symbol Rewriting Pass ----------------*- C++ -*-===// +//===- SymbolRewriter.h - Symbol Rewriting Pass -----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -33,7 +33,6 @@ #ifndef LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H #define LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H -#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include <list> #include <memory> @@ -42,6 +41,8 @@ namespace llvm { class MemoryBuffer; +class Module; +class ModulePass; namespace yaml { @@ -89,7 +90,7 @@ private: const Type Kind; }; -typedef std::list<std::unique_ptr<RewriteDescriptor>> RewriteDescriptorList; +using RewriteDescriptorList = std::list<std::unique_ptr<RewriteDescriptor>>; class RewriteMapParser { public: @@ -120,6 +121,7 @@ ModulePass *createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &); class RewriteSymbolPass : public PassInfoMixin<RewriteSymbolPass> { public: RewriteSymbolPass() { loadAndParseMapFiles(); } + RewriteSymbolPass(SymbolRewriter::RewriteDescriptorList &DL) { Descriptors.splice(Descriptors.begin(), DL); } diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h index a3115ad16914..12aa3bc6e770 100644 --- a/include/llvm/Transforms/Utils/UnrollLoop.h +++ b/include/llvm/Transforms/Utils/UnrollLoop.h @@ -16,40 +16,57 @@ #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H -// Needed because we can't forward-declare the nested struct -// TargetTransformInfo::UnrollingPreferences +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/TargetTransformInfo.h" namespace llvm { -class StringRef; class AssumptionCache; +class BasicBlock; class DominatorTree; class Loop; class LoopInfo; -class LPPassManager; class MDNode; -class Pass; class OptimizationRemarkEmitter; class ScalarEvolution; -typedef SmallDenseMap<const Loop *, Loop *, 4> NewLoopsMap; +using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops); -bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force, - bool AllowRuntime, bool AllowExpensiveTripCount, - bool PreserveCondBr, bool PreserveOnlyFirst, - unsigned TripMultiple, unsigned PeelCount, LoopInfo *LI, - ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, - OptimizationRemarkEmitter *ORE, bool PreserveLCSSA); +/// Represents the result of a \c UnrollLoop invocation. +enum class LoopUnrollResult { + /// The loop was not modified. + Unmodified, + + /// The loop was partially unrolled -- we still have a loop, but with a + /// smaller trip count. We may also have emitted epilogue loop if the loop + /// had a non-constant trip count. + PartiallyUnrolled, + + /// The loop was fully unrolled into straight-line code. We no longer have + /// any back-edges. + FullyUnrolled +}; + +LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, + bool Force, bool AllowRuntime, + bool AllowExpensiveTripCount, bool PreserveCondBr, + bool PreserveOnlyFirst, unsigned TripMultiple, + unsigned PeelCount, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, + OptimizationRemarkEmitter *ORE, bool PreserveLCSSA); bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, - bool UseEpilogRemainder, LoopInfo *LI, + bool UseEpilogRemainder, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC, bool PreserveLCSSA); void computePeelCount(Loop *L, unsigned LoopSize, @@ -60,6 +77,7 @@ bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); -} -#endif +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h index 45ef8246dcd1..4ecb23ea1951 100644 --- a/include/llvm/Transforms/Utils/ValueMapper.h +++ b/include/llvm/Transforms/Utils/ValueMapper.h @@ -21,9 +21,17 @@ namespace llvm { -class Value; +class Constant; +class Function; +class GlobalAlias; +class GlobalVariable; class Instruction; -typedef ValueMap<const Value *, WeakTrackingVH> ValueToValueMapTy; +class MDNode; +class Metadata; +class Type; +class Value; + +using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>; /// This is a class that can be implemented by clients to remap types when /// cloning constants and instructions. @@ -44,10 +52,10 @@ class ValueMaterializer { virtual void anchor(); // Out of line method. protected: - ~ValueMaterializer() = default; ValueMaterializer() = default; ValueMaterializer(const ValueMaterializer &) = default; ValueMaterializer &operator=(const ValueMaterializer &) = default; + ~ValueMaterializer() = default; public: /// This method can be implemented to generate a mapped Value on demand. For @@ -91,7 +99,7 @@ enum RemapFlags { RF_NullMapMissingGlobalValues = 8, }; -static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { +inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { return RemapFlags(unsigned(LHS) | unsigned(RHS)); } diff --git a/include/llvm/Transforms/Vectorize/LoopVectorize.h b/include/llvm/Transforms/Vectorize/LoopVectorize.h index 57d10c4c7473..32b56d372ea1 100644 --- a/include/llvm/Transforms/Vectorize/LoopVectorize.h +++ b/include/llvm/Transforms/Vectorize/LoopVectorize.h @@ -1,4 +1,4 @@ -//===---- LoopVectorize.h ---------------------------------------*- C++ -*-===// +//===- LoopVectorize.h ------------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -49,27 +49,29 @@ #ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H #define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H -#include "llvm/ADT/MapVector.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/BlockFrequencyInfo.h" -#include "llvm/Analysis/DemandedBits.h" -#include "llvm/Analysis/LoopAccessAnalysis.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/OptimizationDiagnosticInfo.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" -#include "llvm/Transforms/Scalar/LoopPassManager.h" #include <functional> namespace llvm { +class AssumptionCache; +class BlockFrequencyInfo; +class DemandedBits; +class DominatorTree; +class Function; +class Loop; +class LoopAccessInfo; +class LoopInfo; +class OptimizationRemarkEmitter; +class ScalarEvolution; +class TargetLibraryInfo; +class TargetTransformInfo; + /// The LoopVectorize Pass. struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> { bool DisableUnrolling = false; + /// If true, consider all loops for vectorization. /// If false, only loops that explicitly request vectorization are /// considered. @@ -99,6 +101,7 @@ struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> { bool processLoop(Loop *L); }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H diff --git a/include/llvm/Transforms/Vectorize/SLPVectorizer.h b/include/llvm/Transforms/Vectorize/SLPVectorizer.h index 6f258191e89e..25f264c4722c 100644 --- a/include/llvm/Transforms/Vectorize/SLPVectorizer.h +++ b/include/llvm/Transforms/Vectorize/SLPVectorizer.h @@ -1,4 +1,4 @@ -//===---- SLPVectorizer.h ---------------------------------------*- C++ -*-===// +//===- SLPVectorizer.h ------------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -19,30 +19,48 @@ #ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H #define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/MapVector.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/DemandedBits.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/OptimizationDiagnosticInfo.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/IR/ValueHandle.h" namespace llvm { +class AssumptionCache; +class BasicBlock; +class CmpInst; +class DataLayout; +class DemandedBits; +class DominatorTree; +class Function; +class InsertElementInst; +class InsertValueInst; +class Instruction; +class LoopInfo; +class OptimizationRemarkEmitter; +class PHINode; +class ScalarEvolution; +class StoreInst; +class TargetLibraryInfo; +class TargetTransformInfo; +class Value; + /// A private "module" namespace for types and utilities used by this pass. /// These are implementation details and should not be used by clients. namespace slpvectorizer { + class BoUpSLP; -} + +} // end namespace slpvectorizer struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> { - typedef SmallVector<StoreInst *, 8> StoreList; - typedef MapVector<Value *, StoreList> StoreListMap; - typedef SmallVector<WeakTrackingVH, 8> WeakTrackingVHList; - typedef MapVector<Value *, WeakTrackingVHList> WeakTrackingVHListMap; + using StoreList = SmallVector<StoreInst *, 8>; + using StoreListMap = MapVector<Value *, StoreList>; + using WeakTrackingVHList = SmallVector<WeakTrackingVH, 8>; + using WeakTrackingVHListMap = MapVector<Value *, WeakTrackingVHList>; ScalarEvolution *SE = nullptr; TargetTransformInfo *TTI = nullptr; @@ -78,14 +96,16 @@ private: /// \brief Try to vectorize a list of operands. /// \@param BuildVector A list of users to ignore for the purpose of - /// scheduling and that don't need extracting. + /// scheduling and cost estimation when NeedExtraction + /// is false. /// \returns true if a value was vectorized. bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, ArrayRef<Value *> BuildVector = None, - bool AllowReorder = false); + bool AllowReorder = false, + bool NeedExtraction = false); - /// \brief Try to vectorize a chain that may start at the operands of \p V. - bool tryToVectorize(BinaryOperator *V, slpvectorizer::BoUpSLP &R); + /// \brief 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. bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); @@ -100,6 +120,22 @@ private: slpvectorizer::BoUpSLP &R, TargetTransformInfo *TTI); + /// Try to vectorize trees that start at insertvalue instructions. + bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB, + slpvectorizer::BoUpSLP &R); + + /// Try to vectorize trees that start at insertelement instructions. + bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB, + slpvectorizer::BoUpSLP &R); + + /// Try to vectorize trees that start at compare instructions. + bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R); + + /// Tries to vectorize constructs started from CmpInst, InsertValueInst or + /// InsertElementInst instructions. + bool vectorizeSimpleInstructions(SmallVectorImpl<WeakVH> &Instructions, + BasicBlock *BB, slpvectorizer::BoUpSLP &R); + /// \brief Scan the basic block and look for patterns that are likely to start /// a vectorization chain. bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); @@ -115,6 +151,7 @@ private: /// The getelementptr instructions in a basic block organized by base pointer. WeakTrackingVHListMap GEPs; }; -} + +} // end namespace llvm #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H |