diff options
Diffstat (limited to 'llvm/include')
30 files changed, 947 insertions, 106 deletions
diff --git a/llvm/include/llvm/ADT/STLForwardCompat.h b/llvm/include/llvm/ADT/STLForwardCompat.h index 0e9bd2d..9c81981 100644 --- a/llvm/include/llvm/ADT/STLForwardCompat.h +++ b/llvm/include/llvm/ADT/STLForwardCompat.h @@ -115,6 +115,13 @@ struct detector<std::void_t<Op<Args...>>, Op, Args...> { /// using has_copy_assign_t = decltype(std::declval<T&>() /// = std::declval<const T&>()); /// bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value; +/// +/// NOTE: The C++20 standard has adopted concepts and requires clauses as a +/// superior alternative to std::is_detected. +/// +/// This utility is placed in STLForwardCompat.h as a reminder +/// to migrate usages of llvm::is_detected to concepts and 'requires' +/// clauses when the codebase adopts C++20. template <template <class...> class Op, class... Args> using is_detected = typename detail::detector<void, Op, Args...>::value_t; diff --git a/llvm/include/llvm/ADT/SparseMultiSet.h b/llvm/include/llvm/ADT/SparseMultiSet.h index 0aa7edbc..5e4e170 100644 --- a/llvm/include/llvm/ADT/SparseMultiSet.h +++ b/llvm/include/llvm/ADT/SparseMultiSet.h @@ -21,9 +21,9 @@ #ifndef LLVM_ADT_SPARSEMULTISET_H #define LLVM_ADT_SPARSEMULTISET_H +#include "llvm/ADT/STLForwardCompat.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SparseSet.h" -#include "llvm/ADT/identity.h" #include <cassert> #include <cstdint> #include <cstdlib> @@ -77,11 +77,12 @@ namespace llvm { /// intuitive and fast removal. /// /// @tparam ValueT The type of objects in the set. +/// @tparam KeyT The type of the key that identifies objects in the set. /// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT. /// @tparam SparseT An unsigned integer type. See above. /// -template <typename ValueT, typename KeyFunctorT = identity<unsigned>, - typename SparseT = uint8_t> +template <typename ValueT, typename KeyT = unsigned, + typename KeyFunctorT = identity_cxx20, typename SparseT = uint8_t> class SparseMultiSet { static_assert(std::is_unsigned_v<SparseT>, "SparseT must be an unsigned integer type"); @@ -112,7 +113,6 @@ class SparseMultiSet { bool isValid() const { return Prev != INVALID; } }; - using KeyT = typename KeyFunctorT::argument_type; using DenseT = SmallVector<SMSNode, 8>; DenseT Dense; SparseT *Sparse = nullptr; diff --git a/llvm/include/llvm/ADT/SparseSet.h b/llvm/include/llvm/ADT/SparseSet.h index 9783301..4697de09 100644 --- a/llvm/include/llvm/ADT/SparseSet.h +++ b/llvm/include/llvm/ADT/SparseSet.h @@ -20,8 +20,8 @@ #ifndef LLVM_ADT_SPARSESET_H #define LLVM_ADT_SPARSESET_H +#include "llvm/ADT/STLForwardCompat.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/identity.h" #include "llvm/Support/AllocatorBase.h" #include <cassert> #include <cstdint> @@ -112,16 +112,16 @@ struct SparseSetValFunctor<KeyT, KeyT, KeyFunctorT> { /// uint16_t or uint32_t. /// /// @tparam ValueT The type of objects in the set. +/// @tparam KeyT The type of the key, which is passed to the key functor. /// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT. /// @tparam SparseT An unsigned integer type. See above. /// -template <typename ValueT, typename KeyFunctorT = identity<unsigned>, - typename SparseT = uint8_t> +template <typename ValueT, typename KeyT = unsigned, + typename KeyFunctorT = identity_cxx20, typename SparseT = uint8_t> class SparseSet { static_assert(std::is_unsigned_v<SparseT>, "SparseT must be an unsigned integer type"); - using KeyT = typename KeyFunctorT::argument_type; using DenseT = SmallVector<ValueT, 8>; using size_type = unsigned; DenseT Dense; diff --git a/llvm/include/llvm/ADT/Twine.h b/llvm/include/llvm/ADT/Twine.h index d9f9c0f..e3b4d5e 100644 --- a/llvm/include/llvm/ADT/Twine.h +++ b/llvm/include/llvm/ADT/Twine.h @@ -285,7 +285,7 @@ public: } /// Construct from a StringRef. - /*implicit*/ Twine(const StringRef &Str) : LHSKind(PtrAndLengthKind) { + /*implicit*/ Twine(StringRef Str) : LHSKind(PtrAndLengthKind) { LHS.ptrAndLength.ptr = Str.data(); LHS.ptrAndLength.length = Str.size(); assert(isValid() && "Invalid twine!"); @@ -352,7 +352,7 @@ public: // right thing. Yet. /// Construct as the concatenation of a C string and a StringRef. - /*implicit*/ Twine(const char *LHS, const StringRef &RHS) + /*implicit*/ Twine(const char *LHS, StringRef RHS) : LHSKind(CStringKind), RHSKind(PtrAndLengthKind) { this->LHS.cString = LHS; this->RHS.ptrAndLength.ptr = RHS.data(); @@ -361,7 +361,7 @@ public: } /// Construct as the concatenation of a StringRef and a C string. - /*implicit*/ Twine(const StringRef &LHS, const char *RHS) + /*implicit*/ Twine(StringRef LHS, const char *RHS) : LHSKind(PtrAndLengthKind), RHSKind(CStringKind) { this->LHS.ptrAndLength.ptr = LHS.data(); this->LHS.ptrAndLength.length = LHS.size(); @@ -530,14 +530,14 @@ inline Twine operator+(const Twine &LHS, const Twine &RHS) { /// Additional overload to guarantee simplified codegen; this is equivalent to /// concat(). -inline Twine operator+(const char *LHS, const StringRef &RHS) { +inline Twine operator+(const char *LHS, StringRef RHS) { return Twine(LHS, RHS); } /// Additional overload to guarantee simplified codegen; this is equivalent to /// concat(). -inline Twine operator+(const StringRef &LHS, const char *RHS) { +inline Twine operator+(StringRef LHS, const char *RHS) { return Twine(LHS, RHS); } diff --git a/llvm/include/llvm/CAS/FileOffset.h b/llvm/include/llvm/CAS/FileOffset.h index 21d045e..a3dc06b 100644 --- a/llvm/include/llvm/CAS/FileOffset.h +++ b/llvm/include/llvm/CAS/FileOffset.h @@ -15,7 +15,7 @@ #ifndef LLVM_CAS_FILEOFFSET_H #define LLVM_CAS_FILEOFFSET_H -#include <cstdlib> +#include <cstdint> namespace llvm::cas { diff --git a/llvm/include/llvm/CAS/OnDiskGraphDB.h b/llvm/include/llvm/CAS/OnDiskGraphDB.h index 83017a6..5f0ee0e 100644 --- a/llvm/include/llvm/CAS/OnDiskGraphDB.h +++ b/llvm/include/llvm/CAS/OnDiskGraphDB.h @@ -380,6 +380,7 @@ private: case ObjectPresence::OnlyInUpstreamDB: return true; } + llvm_unreachable("Unknown ObjectPresence enum"); } /// When \p load is called for a node that doesn't exist, this function tries diff --git a/llvm/include/llvm/CodeGen/CommandFlags.h b/llvm/include/llvm/CodeGen/CommandFlags.h index 39c5a8d..af66f2d 100644 --- a/llvm/include/llvm/CodeGen/CommandFlags.h +++ b/llvm/include/llvm/CodeGen/CommandFlags.h @@ -58,8 +58,6 @@ LLVM_ABI CodeGenFileType getFileType(); LLVM_ABI FramePointerKind getFramePointerUsage(); -LLVM_ABI bool getEnableUnsafeFPMath(); - LLVM_ABI bool getEnableNoInfsFPMath(); LLVM_ABI bool getEnableNoNaNsFPMath(); diff --git a/llvm/include/llvm/CodeGen/GlobalISel/MIPatternMatch.h b/llvm/include/llvm/CodeGen/GlobalISel/MIPatternMatch.h index b7ccfbb..8db99ba 100644 --- a/llvm/include/llvm/CodeGen/GlobalISel/MIPatternMatch.h +++ b/llvm/include/llvm/CodeGen/GlobalISel/MIPatternMatch.h @@ -210,8 +210,8 @@ struct SpecificConstantMatch { }; /// Matches a constant equal to \p RequestedValue. -inline SpecificConstantMatch m_SpecificICst(APInt RequestedValue) { - return SpecificConstantMatch(std::move(RequestedValue)); +inline SpecificConstantMatch m_SpecificICst(const APInt &RequestedValue) { + return SpecificConstantMatch(RequestedValue); } inline SpecificConstantMatch m_SpecificICst(int64_t RequestedValue) { @@ -221,7 +221,7 @@ inline SpecificConstantMatch m_SpecificICst(int64_t RequestedValue) { /// Matcher for a specific constant splat. struct SpecificConstantSplatMatch { APInt RequestedVal; - SpecificConstantSplatMatch(const APInt RequestedVal) + SpecificConstantSplatMatch(const APInt &RequestedVal) : RequestedVal(RequestedVal) {} bool match(const MachineRegisterInfo &MRI, Register Reg) { return isBuildVectorConstantSplat(Reg, MRI, RequestedVal, @@ -230,8 +230,9 @@ struct SpecificConstantSplatMatch { }; /// Matches a constant splat of \p RequestedValue. -inline SpecificConstantSplatMatch m_SpecificICstSplat(APInt RequestedValue) { - return SpecificConstantSplatMatch(std::move(RequestedValue)); +inline SpecificConstantSplatMatch +m_SpecificICstSplat(const APInt &RequestedValue) { + return SpecificConstantSplatMatch(RequestedValue); } inline SpecificConstantSplatMatch m_SpecificICstSplat(int64_t RequestedValue) { @@ -242,7 +243,7 @@ inline SpecificConstantSplatMatch m_SpecificICstSplat(int64_t RequestedValue) { /// Matcher for a specific constant or constant splat. struct SpecificConstantOrSplatMatch { APInt RequestedVal; - SpecificConstantOrSplatMatch(const APInt RequestedVal) + SpecificConstantOrSplatMatch(const APInt &RequestedVal) : RequestedVal(RequestedVal) {} bool match(const MachineRegisterInfo &MRI, Register Reg) { APInt MatchedVal; @@ -263,8 +264,8 @@ struct SpecificConstantOrSplatMatch { /// Matches a \p RequestedValue constant or a constant splat of \p /// RequestedValue. inline SpecificConstantOrSplatMatch -m_SpecificICstOrSplat(APInt RequestedValue) { - return SpecificConstantOrSplatMatch(std::move(RequestedValue)); +m_SpecificICstOrSplat(const APInt &RequestedValue) { + return SpecificConstantOrSplatMatch(RequestedValue); } inline SpecificConstantOrSplatMatch diff --git a/llvm/include/llvm/CodeGen/LivePhysRegs.h b/llvm/include/llvm/CodeGen/LivePhysRegs.h index 4af5b00..a76b7f9 100644 --- a/llvm/include/llvm/CodeGen/LivePhysRegs.h +++ b/llvm/include/llvm/CodeGen/LivePhysRegs.h @@ -51,7 +51,7 @@ class raw_ostream; /// when walking backward/forward through a basic block. class LivePhysRegs { const TargetRegisterInfo *TRI = nullptr; - using RegisterSet = SparseSet<MCPhysReg, identity<MCPhysReg>>; + using RegisterSet = SparseSet<MCPhysReg, MCPhysReg>; RegisterSet LiveRegs; public: diff --git a/llvm/include/llvm/CodeGen/MIR2Vec.h b/llvm/include/llvm/CodeGen/MIR2Vec.h index 7b1b5d9..f6b0571 100644 --- a/llvm/include/llvm/CodeGen/MIR2Vec.h +++ b/llvm/include/llvm/CodeGen/MIR2Vec.h @@ -52,11 +52,21 @@ class LLVMContext; class MIR2VecVocabLegacyAnalysis; class TargetInstrInfo; +enum class MIR2VecKind { Symbolic }; + namespace mir2vec { + +// Forward declarations +class MIREmbedder; +class SymbolicMIREmbedder; + extern llvm::cl::OptionCategory MIR2VecCategory; extern cl::opt<float> OpcWeight; using Embedding = ir2vec::Embedding; +using MachineInstEmbeddingsMap = DenseMap<const MachineInstr *, Embedding>; +using MachineBlockEmbeddingsMap = + DenseMap<const MachineBasicBlock *, Embedding>; /// Class for storing and accessing the MIR2Vec vocabulary. /// The MIRVocabulary class manages seed embeddings for LLVM Machine IR @@ -107,19 +117,91 @@ public: const_iterator end() const { return Storage.end(); } - /// Total number of entries in the vocabulary - size_t getCanonicalSize() const { return Storage.size(); } - MIRVocabulary() = delete; /// Factory method to create MIRVocabulary from vocabulary map static Expected<MIRVocabulary> create(VocabMap &&Entries, const TargetInstrInfo &TII); + /// Create a dummy vocabulary for testing purposes. + static Expected<MIRVocabulary> + createDummyVocabForTest(const TargetInstrInfo &TII, unsigned Dim = 1); + + /// Total number of entries in the vocabulary + size_t getCanonicalSize() const { return Storage.size(); } + private: MIRVocabulary(VocabMap &&Entries, const TargetInstrInfo &TII); }; +/// Base class for MIR embedders +class MIREmbedder { +protected: + const MachineFunction &MF; + const MIRVocabulary &Vocab; + + /// Dimension of the embeddings; Captured from the vocabulary + const unsigned Dimension; + + /// Weight for opcode embeddings + const float OpcWeight; + + MIREmbedder(const MachineFunction &MF, const MIRVocabulary &Vocab) + : MF(MF), Vocab(Vocab), Dimension(Vocab.getDimension()), + OpcWeight(mir2vec::OpcWeight) {} + + /// Function to compute embeddings. + Embedding computeEmbeddings() const; + + /// Function to compute the embedding for a given machine basic block. + Embedding computeEmbeddings(const MachineBasicBlock &MBB) const; + + /// Function to compute the embedding for a given machine instruction. + /// Specific to the kind of embeddings being computed. + virtual Embedding computeEmbeddings(const MachineInstr &MI) const = 0; + +public: + virtual ~MIREmbedder() = default; + + /// Factory method to create an Embedder object of the specified kind + /// Returns nullptr if the requested kind is not supported. + static std::unique_ptr<MIREmbedder> create(MIR2VecKind Mode, + const MachineFunction &MF, + const MIRVocabulary &Vocab); + + /// Computes and returns the embedding for a given machine instruction MI in + /// the machine function MF. + Embedding getMInstVector(const MachineInstr &MI) const { + return computeEmbeddings(MI); + } + + /// Computes and returns the embedding for a given machine basic block in the + /// machine function MF. + Embedding getMBBVector(const MachineBasicBlock &MBB) const { + return computeEmbeddings(MBB); + } + + /// Computes and returns the embedding for the current machine function. + Embedding getMFunctionVector() const { + // Currently, we always (re)compute the embeddings for the function. This is + // cheaper than caching the vector. + return computeEmbeddings(); + } +}; + +/// Class for computing Symbolic embeddings +/// Symbolic embeddings are constructed based on the entity-level +/// representations obtained from the MIR Vocabulary. +class SymbolicMIREmbedder : public MIREmbedder { +private: + Embedding computeEmbeddings(const MachineInstr &MI) const override; + +public: + SymbolicMIREmbedder(const MachineFunction &F, const MIRVocabulary &Vocab); + static std::unique_ptr<SymbolicMIREmbedder> + create(const MachineFunction &MF, const MIRVocabulary &Vocab); +}; + } // namespace mir2vec /// Pass to analyze and populate MIR2Vec vocabulary from a module @@ -166,6 +248,31 @@ public: } }; +/// This pass prints the MIR2Vec embeddings for machine functions, basic blocks, +/// and instructions +class MIR2VecPrinterLegacyPass : public MachineFunctionPass { + raw_ostream &OS; + +public: + static char ID; + explicit MIR2VecPrinterLegacyPass(raw_ostream &OS) + : MachineFunctionPass(ID), OS(OS) {} + + bool runOnMachineFunction(MachineFunction &MF) override; + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<MIR2VecVocabLegacyAnalysis>(); + AU.setPreservesAll(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + StringRef getPassName() const override { + return "MIR2Vec Embedder Printer Pass"; + } +}; + +/// Create a machine pass that prints MIR2Vec embeddings +MachineFunctionPass *createMIR2VecPrinterLegacyPass(raw_ostream &OS); + } // namespace llvm #endif // LLVM_CODEGEN_MIR2VEC_H
\ No newline at end of file diff --git a/llvm/include/llvm/CodeGen/MIRFSDiscriminatorOptions.h b/llvm/include/llvm/CodeGen/MIRFSDiscriminatorOptions.h new file mode 100644 index 0000000..672a6b3 --- /dev/null +++ b/llvm/include/llvm/CodeGen/MIRFSDiscriminatorOptions.h @@ -0,0 +1,22 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Command line options for MIR Flow Sensitive discriminators. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MIRFSDISCRIMINATOR_OPTIONS_H +#define LLVM_CODEGEN_MIRFSDISCRIMINATOR_OPTIONS_H + +#include "llvm/Support/CommandLine.h" + +namespace llvm { +extern cl::opt<bool> ImprovedFSDiscriminator; +} // namespace llvm + +#endif // LLVM_CODEGEN_MIRFSDISCRIMINATOR_OPTIONS_H diff --git a/llvm/include/llvm/CodeGen/Passes.h b/llvm/include/llvm/CodeGen/Passes.h index 272b4ac..7fae550 100644 --- a/llvm/include/llvm/CodeGen/Passes.h +++ b/llvm/include/llvm/CodeGen/Passes.h @@ -93,6 +93,10 @@ createMachineFunctionPrinterPass(raw_ostream &OS, LLVM_ABI MachineFunctionPass * createMIR2VecVocabPrinterLegacyPass(raw_ostream &OS); +/// MIR2VecPrinter pass - This pass prints out the MIR2Vec embeddings for +/// machine functions, basic blocks and instructions. +LLVM_ABI MachineFunctionPass *createMIR2VecPrinterLegacyPass(raw_ostream &OS); + /// StackFramePrinter pass - This pass prints out the machine function's /// stack frame to the given stream as a debugging tool. LLVM_ABI MachineFunctionPass *createStackFrameLayoutAnalysisPass(); diff --git a/llvm/include/llvm/CodeGen/RegisterPressure.h b/llvm/include/llvm/CodeGen/RegisterPressure.h index 6d69092..261e5b0 100644 --- a/llvm/include/llvm/CodeGen/RegisterPressure.h +++ b/llvm/include/llvm/CodeGen/RegisterPressure.h @@ -393,7 +393,7 @@ class RegPressureTracker { LiveRegSet LiveRegs; /// Set of vreg defs that start a live range. - SparseSet<Register, VirtReg2IndexFunctor> UntiedDefs; + SparseSet<Register, Register, VirtReg2IndexFunctor> UntiedDefs; /// Live-through pressure. std::vector<unsigned> LiveThruPressure; diff --git a/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h b/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h index ba5b2da..4eacbdc 100644 --- a/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ b/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -90,15 +90,16 @@ namespace llvm { /// allocated once for the pass. It can be cleared in constant time and reused /// without any frees. using RegUnit2SUnitsMap = - SparseMultiSet<PhysRegSUOper, identity<unsigned>, uint16_t>; + SparseMultiSet<PhysRegSUOper, unsigned, identity_cxx20, uint16_t>; /// Track local uses of virtual registers. These uses are gathered by the DAG /// builder and may be consulted by the scheduler to avoid iterating an entire /// vreg use list. - using VReg2SUnitMultiMap = SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor>; + using VReg2SUnitMultiMap = + SparseMultiSet<VReg2SUnit, Register, VirtReg2IndexFunctor>; using VReg2SUnitOperIdxMultiMap = - SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>; + SparseMultiSet<VReg2SUnitOperIdx, Register, VirtReg2IndexFunctor>; using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>; diff --git a/llvm/include/llvm/CodeGen/TargetLowering.h b/llvm/include/llvm/CodeGen/TargetLowering.h index 73f2c55..64a7563 100644 --- a/llvm/include/llvm/CodeGen/TargetLowering.h +++ b/llvm/include/llvm/CodeGen/TargetLowering.h @@ -2459,6 +2459,12 @@ public: return ISD::ANY_EXTEND; } + /// Returns how the platform's atomic rmw operations expect their input + /// argument to be extended (ZERO_EXTEND, SIGN_EXTEND, or ANY_EXTEND). + virtual ISD::NodeType getExtendForAtomicRMWArg(unsigned Op) const { + return ISD::ANY_EXTEND; + } + /// @} /// Returns true if we should normalize diff --git a/llvm/include/llvm/ExecutionEngine/Orc/Core.h b/llvm/include/llvm/ExecutionEngine/Orc/Core.h index f407b56..8613ddd 100644 --- a/llvm/include/llvm/ExecutionEngine/Orc/Core.h +++ b/llvm/include/llvm/ExecutionEngine/Orc/Core.h @@ -26,6 +26,7 @@ #include "llvm/ExecutionEngine/Orc/Shared/ExecutorSymbolDef.h" #include "llvm/ExecutionEngine/Orc/Shared/WrapperFunctionUtils.h" #include "llvm/ExecutionEngine/Orc/TaskDispatch.h" +#include "llvm/ExecutionEngine/Orc/WaitingOnGraph.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ExtensibleRTTI.h" @@ -49,6 +50,9 @@ class InProgressLookupState; enum class SymbolState : uint8_t; +using WaitingOnGraph = + detail::WaitingOnGraph<JITDylib *, NonOwningSymbolStringPtr>; + using ResourceTrackerSP = IntrusiveRefCntPtr<ResourceTracker>; using JITDylibSP = IntrusiveRefCntPtr<JITDylib>; @@ -1131,20 +1135,6 @@ private: using UnmaterializedInfosList = std::vector<std::shared_ptr<UnmaterializedInfo>>; - struct EmissionDepUnit { - EmissionDepUnit(JITDylib &JD) : JD(&JD) {} - - JITDylib *JD = nullptr; - DenseMap<NonOwningSymbolStringPtr, JITSymbolFlags> Symbols; - DenseMap<JITDylib *, DenseSet<NonOwningSymbolStringPtr>> Dependencies; - }; - - struct EmissionDepUnitInfo { - std::shared_ptr<EmissionDepUnit> EDU; - DenseSet<EmissionDepUnit *> IntraEmitUsers; - DenseMap<JITDylib *, DenseSet<NonOwningSymbolStringPtr>> NewDeps; - }; - // Information about not-yet-ready symbol. // * DefiningEDU will point to the EmissionDepUnit that defines the symbol. // * DependantEDUs will hold pointers to any EmissionDepUnits currently @@ -1154,9 +1144,6 @@ private: struct MaterializingInfo { friend class ExecutionSession; - std::shared_ptr<EmissionDepUnit> DefiningEDU; - DenseSet<EmissionDepUnit *> DependantEDUs; - LLVM_ABI void addQuery(std::shared_ptr<AsynchronousSymbolQuery> Q); LLVM_ABI void removeQuery(const AsynchronousSymbolQuery &Q); LLVM_ABI AsynchronousSymbolQueryList @@ -1778,30 +1765,26 @@ private: LLVM_ABI Error OL_notifyResolved(MaterializationResponsibility &MR, const SymbolMap &Symbols); - using EDUInfosMap = - DenseMap<JITDylib::EmissionDepUnit *, JITDylib::EmissionDepUnitInfo>; - - template <typename HandleNewDepFn> - void propagateExtraEmitDeps(std::deque<JITDylib::EmissionDepUnit *> Worklist, - EDUInfosMap &EDUInfos, - HandleNewDepFn HandleNewDep); - EDUInfosMap simplifyDepGroups(MaterializationResponsibility &MR, - ArrayRef<SymbolDependenceGroup> EmittedDeps); - void IL_makeEDUReady(std::shared_ptr<JITDylib::EmissionDepUnit> EDU, - JITDylib::AsynchronousSymbolQuerySet &Queries); - void IL_makeEDUEmitted(std::shared_ptr<JITDylib::EmissionDepUnit> EDU, - JITDylib::AsynchronousSymbolQuerySet &Queries); - bool IL_removeEDUDependence(JITDylib::EmissionDepUnit &EDU, JITDylib &DepJD, - NonOwningSymbolStringPtr DepSym, - EDUInfosMap &EDUInfos); - - static Error makeJDClosedError(JITDylib::EmissionDepUnit &EDU, - JITDylib &ClosedJD); - static Error makeUnsatisfiedDepsError(JITDylib::EmissionDepUnit &EDU, - JITDylib &BadJD, SymbolNameSet BadDeps); - - Expected<JITDylib::AsynchronousSymbolQuerySet> - IL_emit(MaterializationResponsibility &MR, EDUInfosMap EDUInfos); + // FIXME: We should be able to derive FailedSymsForQuery from each query once + // we fix how the detach operation works. + struct EmitQueries { + JITDylib::AsynchronousSymbolQuerySet Updated; + JITDylib::AsynchronousSymbolQuerySet Failed; + DenseMap<AsynchronousSymbolQuery *, std::shared_ptr<SymbolDependenceMap>> + FailedSymsForQuery; + }; + + WaitingOnGraph::ExternalState + IL_getSymbolState(JITDylib *JD, NonOwningSymbolStringPtr Name); + + template <typename UpdateSymbolFn, typename UpdateQueryFn> + void IL_collectQueries(JITDylib::AsynchronousSymbolQuerySet &Qs, + WaitingOnGraph::ContainerElementsMap &QualifiedSymbols, + UpdateSymbolFn &&UpdateSymbol, + UpdateQueryFn &&UpdateQuery); + + Expected<EmitQueries> IL_emit(MaterializationResponsibility &MR, + WaitingOnGraph::SimplifyResult SR); LLVM_ABI Error OL_notifyEmitted(MaterializationResponsibility &MR, ArrayRef<SymbolDependenceGroup> EmittedDeps); @@ -1830,6 +1813,7 @@ private: std::vector<ResourceManager *> ResourceManagers; std::vector<JITDylibSP> JDs; + WaitingOnGraph G; // FIXME: Remove this (and runOutstandingMUs) once the linking layer works // with callbacks from asynchronous queries. diff --git a/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorAddress.h b/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorAddress.h index a5f6c4f..4a32113b 100644 --- a/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorAddress.h +++ b/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorAddress.h @@ -14,7 +14,7 @@ #define LLVM_EXECUTIONENGINE_ORC_SHARED_EXECUTORADDRESS_H #include "llvm/ADT/DenseMapInfo.h" -#include "llvm/ADT/identity.h" +#include "llvm/ADT/STLForwardCompat.h" #include "llvm/ExecutionEngine/Orc/Shared/SimplePackedSerialization.h" #include "llvm/Support/FormatVariadic.h" #include "llvm/Support/raw_ostream.h" @@ -34,7 +34,7 @@ using ExecutorAddrDiff = uint64_t; class ExecutorAddr { public: /// A wrap/unwrap function that leaves pointers unmodified. - template <typename T> using rawPtr = llvm::identity<T *>; + using rawPtr = llvm::identity_cxx20; #if __has_feature(ptrauth_calls) template <typename T> class PtrauthSignDefault { @@ -63,10 +63,10 @@ public: #else /// Default wrap function to use on this host. - template <typename T> using defaultWrap = rawPtr<T>; + template <typename T> using defaultWrap = rawPtr; /// Default unwrap function to use on this host. - template <typename T> using defaultUnwrap = rawPtr<T>; + template <typename T> using defaultUnwrap = rawPtr; #endif diff --git a/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorSymbolDef.h b/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorSymbolDef.h index 0756ab5..9ad2934 100644 --- a/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorSymbolDef.h +++ b/llvm/include/llvm/ExecutionEngine/Orc/Shared/ExecutorSymbolDef.h @@ -33,8 +33,8 @@ public: JITSymbolFlags Flags = BaseFlags; if (std::is_function_v<T>) Flags |= JITSymbolFlags::Callable; - return ExecutorSymbolDef( - ExecutorAddr::fromPtr(UP, ExecutorAddr::rawPtr<T>()), Flags); + return ExecutorSymbolDef(ExecutorAddr::fromPtr(UP, ExecutorAddr::rawPtr()), + Flags); } /// Cast this ExecutorSymbolDef to a pointer of the given type. diff --git a/llvm/include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h b/llvm/include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h new file mode 100644 index 0000000..45834f1 --- /dev/null +++ b/llvm/include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h @@ -0,0 +1,623 @@ +//===------ WaitingOnGraph.h - ORC symbol dependence graph ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines WaitingOnGraph and related utilities. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_EXECUTIONENGINE_ORC_WAITINGONGRAPH_H +#define LLVM_EXECUTIONENGINE_ORC_WAITINGONGRAPH_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/raw_ostream.h" + +#include <algorithm> +#include <vector> + +namespace llvm::orc::detail { + +class WaitingOnGraphTest; + +/// WaitingOnGraph class template. +/// +/// This type is intended to provide efficient dependence tracking for Symbols +/// in an ORC program. +/// +/// WaitingOnGraph models a directed graph with four partitions: +/// 1. Not-yet-emitted nodes: Nodes identified as waited-on in an emit +/// operation. +/// 2. Emitted nodes: Nodes emitted and waiting on some non-empty set of +/// other nodes. +/// 3. Ready nodes: Nodes emitted and not waiting on any other nodes +/// (either because they weren't waiting on any nodes when they were +/// emitted, or because all transitively waited-on nodes have since +/// been emitted). +/// 4. Failed nodes: Nodes that have been marked as failed-to-emit, and +/// nodes that were found to transitively wait-on some failed node. +/// +/// Nodes are added to the graph by *emit* and *fail* operations. +/// +/// The *emit* operation takes a bipartite *local dependence graph* as an +/// argument and returns... +/// a. the set of nodes (both existing and newly added from the local +/// dependence graph) whose waiting-on set is the empty set, and... +/// b. the set of newly added nodes that are found to depend on failed +/// nodes. +/// +/// The *fail* operation takes a set of failed nodes and returns the set of +/// Emitted nodes that were waiting on the failed nodes. +/// +/// The concrete representation adopts several approaches for efficiency: +/// +/// 1. Only *Emitted* and *Not-yet-emitted* nodes are represented explicitly. +/// *Ready* and *Failed* nodes are represented by the values returned by the +/// GetExternalStateFn argument to *emit*. +/// +/// 2. Labels are (*Container*, *Element*) pairs that are intended to represent +/// ORC symbols (ORC uses types Container = JITDylib, +/// Element = NonOwningSymbolStringPtr). The internal representation of the +/// graph is optimized on the assumption that there are many more Elements +/// (symbol names) than Containers (JITDylibs) used to construct the labels. +/// (Consider for example the common case where most JIT'd code is placed in +/// a single "main" JITDylib). +/// +/// 3. The data structure stores *SuperNodes* which have multiple labels. This +/// reduces the number of nodes and edges in the graph in the common case +/// where many JIT symbols have the same set of dependencies. SuperNodes are +/// coalesced when their dependence sets become equal. +/// +/// 4. The *simplify* method can be applied to an initial *local dependence +/// graph* (as a list of SuperNodes) to eliminate any internal dependence +/// relationships that would have to be propagated internally by *emit*. +/// Access to the WaitingOnGraph is assumed to be guarded by a mutex (ORC +/// will access it from multiple threads) so this allows some pre-processing +/// to be performed outside the mutex. +template <typename ContainerIdT, typename ElementIdT> class WaitingOnGraph { + friend class WaitingOnGraphTest; + +public: + using ContainerId = ContainerIdT; + using ElementId = ElementIdT; + using ElementSet = DenseSet<ElementId>; + using ContainerElementsMap = DenseMap<ContainerId, ElementSet>; + + class SuperNode { + friend class WaitingOnGraph; + friend class WaitingOnGraphTest; + + public: + SuperNode(ContainerElementsMap Defs, ContainerElementsMap Deps) + : Defs(std::move(Defs)), Deps(std::move(Deps)) {} + ContainerElementsMap &defs() { return Defs; } + const ContainerElementsMap &defs() const { return Defs; } + ContainerElementsMap &deps() { return Deps; } + const ContainerElementsMap &deps() const { return Deps; } + + private: + ContainerElementsMap Defs; + ContainerElementsMap Deps; + }; + +private: + using ElemToSuperNodeMap = + DenseMap<ContainerId, DenseMap<ElementId, SuperNode *>>; + + using SuperNodeDepsMap = DenseMap<SuperNode *, DenseSet<SuperNode *>>; + + class Coalescer { + public: + std::unique_ptr<SuperNode> addOrCreateSuperNode(ContainerElementsMap Defs, + ContainerElementsMap Deps) { + auto H = getHash(Deps); + if (auto *ExistingSN = findCanonicalSuperNode(H, Deps)) { + for (auto &[Container, Elems] : Defs) { + auto &DstCElems = ExistingSN->Defs[Container]; + [[maybe_unused]] size_t ExpectedSize = + DstCElems.size() + Elems.size(); + DstCElems.insert(Elems.begin(), Elems.end()); + assert(DstCElems.size() == ExpectedSize); + } + return nullptr; + } + + auto NewSN = + std::make_unique<SuperNode>(std::move(Defs), std::move(Deps)); + CanonicalSNs[H].push_back(NewSN.get()); + return NewSN; + } + + void coalesce(std::vector<std::unique_ptr<SuperNode>> &SNs, + ElemToSuperNodeMap &ElemToSN) { + for (size_t I = 0; I != SNs.size();) { + auto &SN = SNs[I]; + auto H = getHash(SN->Deps); + if (auto *CanonicalSN = findCanonicalSuperNode(H, SN->Deps)) { + for (auto &[Container, Elems] : SN->Defs) { + CanonicalSN->Defs[Container].insert(Elems.begin(), Elems.end()); + auto &ContainerElemToSN = ElemToSN[Container]; + for (auto &Elem : Elems) + ContainerElemToSN[Elem] = CanonicalSN; + } + std::swap(SN, SNs.back()); + SNs.pop_back(); + } else { + CanonicalSNs[H].push_back(SN.get()); + ++I; + } + } + } + + template <typename Pred> void remove(Pred &&Remove) { + for (auto &[Hash, SNs] : CanonicalSNs) { + bool Found = false; + for (size_t I = 0; I != SNs.size(); ++I) { + if (Remove(SNs[I])) { + std::swap(SNs[I], SNs.back()); + SNs.pop_back(); + Found = true; + break; + } + } + if (Found) { + if (SNs.empty()) + CanonicalSNs.erase(Hash); + break; + } + } + } + + private: + hash_code getHash(const ContainerElementsMap &M) { + SmallVector<ContainerId> SortedContainers; + SortedContainers.reserve(M.size()); + for (auto &[Container, Elems] : M) + SortedContainers.push_back(Container); + llvm::sort(SortedContainers); + hash_code Hash(0); + for (auto &Container : SortedContainers) { + auto &ContainerElems = M.at(Container); + SmallVector<ElementId> SortedElems(ContainerElems.begin(), + ContainerElems.end()); + llvm::sort(SortedElems); + Hash = hash_combine( + Hash, Container, + hash_combine_range(SortedElems.begin(), SortedElems.end())); + } + return Hash; + } + + SuperNode *findCanonicalSuperNode(hash_code H, + const ContainerElementsMap &M) { + for (auto *SN : CanonicalSNs[H]) + if (SN->Deps == M) + return SN; + return nullptr; + } + + DenseMap<hash_code, SmallVector<SuperNode *>> CanonicalSNs; + }; + +public: + /// Build SuperNodes from (definition-set, dependence-set) pairs. + /// + /// Coalesces definition-sets with identical dependence-sets. + class SuperNodeBuilder { + public: + void add(ContainerElementsMap Defs, ContainerElementsMap Deps) { + if (Defs.empty()) + return; + // Remove any self-reference. + SmallVector<ContainerId> ToRemove; + for (auto &[Container, Elems] : Defs) { + assert(!Elems.empty() && "Defs for container must not be empty"); + auto I = Deps.find(Container); + if (I == Deps.end()) + continue; + auto &DepsForContainer = I->second; + for (auto &Elem : Elems) + DepsForContainer.erase(Elem); + if (DepsForContainer.empty()) + ToRemove.push_back(Container); + } + for (auto &Container : ToRemove) + Deps.erase(Container); + if (auto SN = C.addOrCreateSuperNode(std::move(Defs), std::move(Deps))) + SNs.push_back(std::move(SN)); + } + std::vector<std::unique_ptr<SuperNode>> takeSuperNodes() { + return std::move(SNs); + } + + private: + Coalescer C; + std::vector<std::unique_ptr<SuperNode>> SNs; + }; + + class SimplifyResult { + friend class WaitingOnGraph; + friend class WaitingOnGraphTest; + + public: + const std::vector<std::unique_ptr<SuperNode>> &superNodes() const { + return SNs; + } + + private: + SimplifyResult(std::vector<std::unique_ptr<SuperNode>> SNs, + ElemToSuperNodeMap ElemToSN) + : SNs(std::move(SNs)), ElemToSN(std::move(ElemToSN)) {} + std::vector<std::unique_ptr<SuperNode>> SNs; + ElemToSuperNodeMap ElemToSN; + }; + + /// Preprocess a list of SuperNodes to remove all intra-SN dependencies. + static SimplifyResult simplify(std::vector<std::unique_ptr<SuperNode>> SNs) { + // Build ElemToSN map. + ElemToSuperNodeMap ElemToSN; + for (auto &SN : SNs) { + for (auto &[Container, Elements] : SN->Defs) { + auto &ContainerElemToSN = ElemToSN[Container]; + for (auto &E : Elements) + ContainerElemToSN[E] = SN.get(); + } + } + + SuperNodeDepsMap SuperNodeDeps; + hoistDeps(SuperNodeDeps, SNs, ElemToSN); + propagateSuperNodeDeps(SuperNodeDeps); + sinkDeps(SNs, SuperNodeDeps); + + // Pre-coalesce nodes. + Coalescer().coalesce(SNs, ElemToSN); + + return {std::move(SNs), std::move(ElemToSN)}; + } + + struct EmitResult { + std::vector<std::unique_ptr<SuperNode>> Ready; + std::vector<std::unique_ptr<SuperNode>> Failed; + }; + + enum class ExternalState { None, Ready, Failed }; + + /// Add the given SuperNodes to the graph, returning any SuperNodes that + /// move to the Ready or Failed states as a result. + /// The GetExternalState function is used to represent SuperNodes that have + /// already become Ready or Failed (since such nodes are not explicitly + /// represented in the graph). + template <typename GetExternalStateFn> + EmitResult emit(SimplifyResult SR, GetExternalStateFn &&GetExternalState) { + auto NewSNs = std::move(SR.SNs); + auto ElemToNewSN = std::move(SR.ElemToSN); + + // First process any dependencies on nodes with external state. + auto FailedSNs = processExternalDeps(NewSNs, GetExternalState); + + // Collect the PendingSNs whose dep sets are about to be modified. + std::vector<std::unique_ptr<SuperNode>> ModifiedPendingSNs; + for (size_t I = 0; I != PendingSNs.size();) { + auto &SN = PendingSNs[I]; + bool Remove = false; + for (auto &[Container, Elems] : SN->Deps) { + auto I = ElemToNewSN.find(Container); + if (I == ElemToNewSN.end()) + continue; + for (auto Elem : Elems) { + if (I->second.contains(Elem)) { + Remove = true; + break; + } + } + if (Remove) + break; + } + if (Remove) { + ModifiedPendingSNs.push_back(std::move(SN)); + std::swap(SN, PendingSNs.back()); + PendingSNs.pop_back(); + } else + ++I; + } + + // Remove cycles from the graphs. + SuperNodeDepsMap SuperNodeDeps; + hoistDeps(SuperNodeDeps, ModifiedPendingSNs, ElemToNewSN); + + CoalesceToPendingSNs.remove( + [&](SuperNode *SN) { return SuperNodeDeps.count(SN); }); + + hoistDeps(SuperNodeDeps, NewSNs, ElemToPendingSN); + propagateSuperNodeDeps(SuperNodeDeps); + sinkDeps(NewSNs, SuperNodeDeps); + sinkDeps(ModifiedPendingSNs, SuperNodeDeps); + + // Process supernodes. Pending first, since we'll update PendingSNs when we + // incorporate NewSNs. + std::vector<std::unique_ptr<SuperNode>> ReadyNodes, FailedNodes; + processReadyOrFailed(ModifiedPendingSNs, ReadyNodes, FailedNodes, + SuperNodeDeps, ElemToPendingSN, FailedSNs); + processReadyOrFailed(NewSNs, ReadyNodes, FailedNodes, SuperNodeDeps, + ElemToNewSN, FailedSNs); + + CoalesceToPendingSNs.coalesce(ModifiedPendingSNs, ElemToPendingSN); + CoalesceToPendingSNs.coalesce(NewSNs, ElemToPendingSN); + + // Integrate remaining ModifiedPendingSNs and NewSNs into PendingSNs. + for (auto &SN : ModifiedPendingSNs) + PendingSNs.push_back(std::move(SN)); + + // Update ElemToPendingSN for the remaining elements. + for (auto &SN : NewSNs) { + for (auto &[Container, Elems] : SN->Defs) { + auto &Row = ElemToPendingSN[Container]; + for (auto &Elem : Elems) + Row[Elem] = SN.get(); + } + PendingSNs.push_back(std::move(SN)); + } + + return {std::move(ReadyNodes), std::move(FailedNodes)}; + } + + /// Identify the given symbols as Failed. + /// The elements of the Failed map will not be included in the returned + /// result, so clients should take whatever actions are needed to mark + /// this as failed in their external representation. + std::vector<std::unique_ptr<SuperNode>> + fail(const ContainerElementsMap &Failed) { + std::vector<std::unique_ptr<SuperNode>> FailedSNs; + + for (size_t I = 0; I != PendingSNs.size();) { + auto &PendingSN = PendingSNs[I]; + bool FailPendingSN = false; + for (auto &[Container, Elems] : PendingSN->Deps) { + if (FailPendingSN) + break; + auto I = Failed.find(Container); + if (I == Failed.end()) + continue; + for (auto &Elem : Elems) { + if (I->second.count(Elem)) { + FailPendingSN = true; + break; + } + } + } + if (FailPendingSN) { + FailedSNs.push_back(std::move(PendingSN)); + PendingSN = std::move(PendingSNs.back()); + PendingSNs.pop_back(); + } else + ++I; + } + + for (auto &SN : FailedSNs) { + CoalesceToPendingSNs.remove( + [&](SuperNode *SNC) { return SNC == SN.get(); }); + for (auto &[Container, Elems] : SN->Defs) { + assert(ElemToPendingSN.count(Container)); + auto &CElems = ElemToPendingSN[Container]; + for (auto &Elem : Elems) + CElems.erase(Elem); + if (CElems.empty()) + ElemToPendingSN.erase(Container); + } + } + + return FailedSNs; + } + + bool validate(raw_ostream &Log) { + bool AllGood = true; + auto ErrLog = [&]() -> raw_ostream & { + AllGood = false; + return Log; + }; + + size_t DefCount = 0; + for (auto &PendingSN : PendingSNs) { + if (PendingSN->Deps.empty()) + ErrLog() << "Pending SN " << PendingSN.get() << " has empty dep set.\n"; + else { + bool BadElem = false; + for (auto &[Container, Elems] : PendingSN->Deps) { + auto I = ElemToPendingSN.find(Container); + if (I == ElemToPendingSN.end()) + continue; + if (Elems.empty()) + ErrLog() << "Pending SN " << PendingSN.get() + << " has dependence map entry for " << Container + << " with empty element set.\n"; + for (auto &Elem : Elems) { + if (I->second.count(Elem)) { + ErrLog() << "Pending SN " << PendingSN.get() + << " has dependence on emitted element ( " << Container + << ", " << Elem << ")\n"; + BadElem = true; + break; + } + } + if (BadElem) + break; + } + } + + for (auto &[Container, Elems] : PendingSN->Defs) { + if (Elems.empty()) + ErrLog() << "Pending SN " << PendingSN.get() + << " has def map entry for " << Container + << " with empty element set.\n"; + DefCount += Elems.size(); + auto I = ElemToPendingSN.find(Container); + if (I == ElemToPendingSN.end()) + ErrLog() << "Pending SN " << PendingSN.get() << " has " + << Elems.size() << " defs in container " << Container + << " not covered by ElemsToPendingSN.\n"; + else { + for (auto &Elem : Elems) { + auto J = I->second.find(Elem); + if (J == I->second.end()) + ErrLog() << "Pending SN " << PendingSN.get() << " has element (" + << Container << ", " << Elem + << ") not covered by ElemsToPendingSN.\n"; + else if (J->second != PendingSN.get()) + ErrLog() << "ElemToPendingSN value invalid for (" << Container + << ", " << Elem << ")\n"; + } + } + } + } + + size_t DefCount2 = 0; + for (auto &[Container, Elems] : ElemToPendingSN) + DefCount2 += Elems.size(); + + assert(DefCount2 >= DefCount); + if (DefCount2 != DefCount) + ErrLog() << "ElemToPendingSN contains extra elements.\n"; + + return AllGood; + } + +private: + // Replace individual dependencies with supernode dependencies. + // + // For all dependencies in SNs, if the corresponding node is defined in + // ElemToSN then remove the individual dependency and add the record the + // dependency on the corresponding supernode in SuperNodeDeps. + static void hoistDeps(SuperNodeDepsMap &SuperNodeDeps, + std::vector<std::unique_ptr<SuperNode>> &SNs, + ElemToSuperNodeMap &ElemToSN) { + for (auto &SN : SNs) { + auto &SNDeps = SuperNodeDeps[SN.get()]; + for (auto &[DefContainer, DefElems] : ElemToSN) { + auto I = SN->Deps.find(DefContainer); + if (I == SN->Deps.end()) + continue; + for (auto &[DefElem, DefSN] : DefElems) + if (I->second.erase(DefElem)) + SNDeps.insert(DefSN); + if (I->second.empty()) + SN->Deps.erase(I); + } + } + } + + // Compute transitive closure of deps for each node. + static void propagateSuperNodeDeps(SuperNodeDepsMap &SuperNodeDeps) { + for (auto &[SN, Deps] : SuperNodeDeps) { + DenseSet<SuperNode *> Reachable({SN}); + SmallVector<SuperNode *> Worklist(Deps.begin(), Deps.end()); + + while (!Worklist.empty()) { + auto *DepSN = Worklist.pop_back_val(); + if (!Reachable.insert(DepSN).second) + continue; + auto I = SuperNodeDeps.find(DepSN); + if (I == SuperNodeDeps.end()) + continue; + for (auto *DepSNDep : I->second) + Worklist.push_back(DepSNDep); + } + + Deps = std::move(Reachable); + } + } + + // Sink SuperNode dependencies back to dependencies on individual nodes. + static void sinkDeps(std::vector<std::unique_ptr<SuperNode>> &SNs, + SuperNodeDepsMap &SuperNodeDeps) { + for (auto &SN : SNs) { + auto I = SuperNodeDeps.find(SN.get()); + if (I == SuperNodeDeps.end()) + continue; + + for (auto *DepSN : I->second) + for (auto &[Container, Elems] : DepSN->Deps) + SN->Deps[Container].insert(Elems.begin(), Elems.end()); + } + } + + template <typename GetExternalStateFn> + static std::vector<SuperNode *> + processExternalDeps(std::vector<std::unique_ptr<SuperNode>> &SNs, + GetExternalStateFn &GetExternalState) { + std::vector<SuperNode *> FailedSNs; + for (auto &SN : SNs) { + bool SNHasError = false; + SmallVector<ContainerId> ContainersToRemove; + for (auto &[Container, Elems] : SN->Deps) { + SmallVector<ElementId> ElemToRemove; + for (auto &Elem : Elems) { + switch (GetExternalState(Container, Elem)) { + case ExternalState::None: + break; + case ExternalState::Ready: + ElemToRemove.push_back(Elem); + break; + case ExternalState::Failed: + ElemToRemove.push_back(Elem); + SNHasError = true; + break; + } + } + for (auto &Elem : ElemToRemove) + Elems.erase(Elem); + if (Elems.empty()) + ContainersToRemove.push_back(Container); + } + for (auto &Container : ContainersToRemove) + SN->Deps.erase(Container); + if (SNHasError) + FailedSNs.push_back(SN.get()); + } + + return FailedSNs; + } + + void processReadyOrFailed(std::vector<std::unique_ptr<SuperNode>> &SNs, + std::vector<std::unique_ptr<SuperNode>> &Ready, + std::vector<std::unique_ptr<SuperNode>> &Failed, + SuperNodeDepsMap &SuperNodeDeps, + ElemToSuperNodeMap &ElemToSNs, + std::vector<SuperNode *> FailedSNs) { + for (size_t I = 0; I != SNs.size();) { + auto &SN = SNs[I]; + + bool SNFailed = false; + assert(SuperNodeDeps.count(SN.get())); + auto &SNSuperNodeDeps = SuperNodeDeps[SN.get()]; + for (auto *FailedSN : FailedSNs) { + if (FailedSN == SN.get() || SNSuperNodeDeps.count(FailedSN)) { + SNFailed = true; + break; + } + } + + bool SNReady = SN->Deps.empty(); + + if (SNReady || SNFailed) { + auto &NodeList = SNFailed ? Failed : Ready; + NodeList.push_back(std::move(SN)); + std::swap(SN, SNs.back()); + SNs.pop_back(); + } else + ++I; + } + } + + std::vector<std::unique_ptr<SuperNode>> PendingSNs; + ElemToSuperNodeMap ElemToPendingSN; + Coalescer CoalesceToPendingSNs; +}; + +} // namespace llvm::orc::detail + +#endif // LLVM_EXECUTIONENGINE_ORC_WAITINGONGRAPH_H diff --git a/llvm/include/llvm/IR/Attributes.td b/llvm/include/llvm/IR/Attributes.td index 8e7d9dc..8ce2b1b 100644 --- a/llvm/include/llvm/IR/Attributes.td +++ b/llvm/include/llvm/IR/Attributes.td @@ -410,7 +410,6 @@ def LessPreciseFPMAD : StrBoolAttr<"less-precise-fpmad">; def NoInfsFPMath : StrBoolAttr<"no-infs-fp-math">; def NoNansFPMath : StrBoolAttr<"no-nans-fp-math">; def NoSignedZerosFPMath : StrBoolAttr<"no-signed-zeros-fp-math">; -def UnsafeFPMath : StrBoolAttr<"unsafe-fp-math">; def NoJumpTables : StrBoolAttr<"no-jump-tables">; def NoInlineLineTables : StrBoolAttr<"no-inline-line-tables">; def ProfileSampleAccurate : StrBoolAttr<"profile-sample-accurate">; @@ -474,7 +473,6 @@ def : MergeRule<"setAND<LessPreciseFPMADAttr>">; def : MergeRule<"setAND<NoInfsFPMathAttr>">; def : MergeRule<"setAND<NoNansFPMathAttr>">; def : MergeRule<"setAND<NoSignedZerosFPMathAttr>">; -def : MergeRule<"setAND<UnsafeFPMathAttr>">; def : MergeRule<"setOR<NoImplicitFloatAttr>">; def : MergeRule<"setOR<NoJumpTablesAttr>">; def : MergeRule<"setOR<ProfileSampleAccurateAttr>">; diff --git a/llvm/include/llvm/IR/AutoUpgrade.h b/llvm/include/llvm/IR/AutoUpgrade.h index 31096e8..540d60a 100644 --- a/llvm/include/llvm/IR/AutoUpgrade.h +++ b/llvm/include/llvm/IR/AutoUpgrade.h @@ -96,6 +96,16 @@ namespace llvm { /// info. Return true if module is modified. LLVM_ABI bool UpgradeDebugInfo(Module &M); + /// Copies module attributes to the functions in the module. + /// Currently only effects ARM, Thumb and AArch64 targets. + /// Supported attributes: + /// - branch-target-enforcement + /// - branch-protection-pauth-lr + /// - guarded-control-stack + /// - sign-return-address + /// - sign-return-address-with-bkey + void copyModuleAttrToFunctions(Module &M); + /// Check whether a string looks like an old loop attachment tag. inline bool mayBeOldLoopAttachmentTag(StringRef Name) { return Name.starts_with("llvm.vectorizer."); diff --git a/llvm/include/llvm/IR/Intrinsics.td b/llvm/include/llvm/IR/Intrinsics.td index 12d1c25..e6cce9a4 100644 --- a/llvm/include/llvm/IR/Intrinsics.td +++ b/llvm/include/llvm/IR/Intrinsics.td @@ -2851,7 +2851,15 @@ def int_ptrauth_blend : def int_ptrauth_sign_generic : DefaultAttrsIntrinsic<[llvm_i64_ty], [llvm_i64_ty, llvm_i64_ty], [IntrNoMem]>; +//===----------------- AllocToken Intrinsics ------------------------------===// + +// Return the token ID for the given !alloc_token metadata. +def int_alloc_token_id : + DefaultAttrsIntrinsic<[llvm_anyint_ty], [llvm_metadata_ty], + [IntrNoMem, NoUndef<RetIndex>]>; + //===----------------------------------------------------------------------===// + //===------- Convergence Intrinsics ---------------------------------------===// def int_experimental_convergence_entry diff --git a/llvm/include/llvm/IR/ModuleSummaryIndex.h b/llvm/include/llvm/IR/ModuleSummaryIndex.h index ac79d91..0062cec 100644 --- a/llvm/include/llvm/IR/ModuleSummaryIndex.h +++ b/llvm/include/llvm/IR/ModuleSummaryIndex.h @@ -164,9 +164,24 @@ struct alignas(8) GlobalValueSummaryInfo { inline GlobalValueSummaryInfo(bool HaveGVs); + /// Access a read-only list of global value summary structures for a + /// particular value held in the GlobalValueMap. + ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const { + return SummaryList; + } + + /// Add a summary corresponding to a global value definition in a module with + /// the corresponding GUID. + void addSummary(std::unique_ptr<GlobalValueSummary> Summary) { + return SummaryList.push_back(std::move(Summary)); + } + +private: /// List of global value summary structures for a particular value held /// in the GlobalValueMap. Requires a vector in the case of multiple - /// COMDAT values of the same name. + /// COMDAT values of the same name, weak symbols, locals of the same name when + /// compiling without sufficient distinguishing path, or (theoretically) hash + /// collisions. Each summary is from a different module. GlobalValueSummaryList SummaryList; }; @@ -201,7 +216,7 @@ struct ValueInfo { } ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const { - return getRef()->second.SummaryList; + return getRef()->second.getSummaryList(); } // Even if the index is built with GVs available, we may not have one for @@ -1607,8 +1622,8 @@ public: for (auto &S : *this) { // Skip external functions - if (!S.second.SummaryList.size() || - !isa<FunctionSummary>(S.second.SummaryList.front().get())) + if (!S.second.getSummaryList().size() || + !isa<FunctionSummary>(S.second.getSummaryList().front().get())) continue; discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent); } @@ -1748,7 +1763,7 @@ public: // Here we have a notionally const VI, but the value it points to is owned // by the non-const *this. const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef()) - ->second.SummaryList.push_back(std::move(Summary)); + ->second.addSummary(std::move(Summary)); } /// Add an original name for the value of the given GUID. @@ -1937,7 +1952,7 @@ public: collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const { for (const auto &GlobalList : *this) { auto GUID = GlobalList.first; - for (const auto &Summary : GlobalList.second.SummaryList) { + for (const auto &Summary : GlobalList.second.getSummaryList()) { ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get(); } } @@ -2035,7 +2050,7 @@ struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> { std::unique_ptr<GlobalValueSummary> Root = std::make_unique<FunctionSummary>(I->calculateCallGraphRoot()); GlobalValueSummaryInfo G(I->haveGVs()); - G.SummaryList.push_back(std::move(Root)); + G.addSummary(std::move(Root)); static auto P = GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G)); return ValueInfo(I->haveGVs(), &P); diff --git a/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h b/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h index 531de51..3381e17 100644 --- a/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h +++ b/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h @@ -237,7 +237,7 @@ template <> struct CustomMappingTraits<GlobalValueSummaryMapTy> { // This is done in fixAliaseeLinks() which is called in // MappingTraits<ModuleSummaryIndex>::mapping(). ASum->setAliasee(AliaseeVI, /*Aliasee=*/nullptr); - Elem.SummaryList.push_back(std::move(ASum)); + Elem.addSummary(std::move(ASum)); continue; } SmallVector<ValueInfo, 0> Refs; @@ -246,7 +246,7 @@ template <> struct CustomMappingTraits<GlobalValueSummaryMapTy> { auto It = V.try_emplace(RefGUID, /*IsAnalysis=*/false).first; Refs.push_back(ValueInfo(/*IsAnalysis=*/false, &*It)); } - Elem.SummaryList.push_back(std::make_unique<FunctionSummary>( + Elem.addSummary(std::make_unique<FunctionSummary>( GVFlags, /*NumInsts=*/0, FunctionSummary::FFlags{}, std::move(Refs), SmallVector<FunctionSummary::EdgeTy, 0>{}, std::move(GVSum.TypeTests), std::move(GVSum.TypeTestAssumeVCalls), @@ -260,7 +260,7 @@ template <> struct CustomMappingTraits<GlobalValueSummaryMapTy> { static void output(IO &io, GlobalValueSummaryMapTy &V) { for (auto &P : V) { std::vector<GlobalValueSummaryYaml> GVSums; - for (auto &Sum : P.second.SummaryList) { + for (auto &Sum : P.second.getSummaryList()) { if (auto *FSum = dyn_cast<FunctionSummary>(Sum.get())) { std::vector<uint64_t> Refs; Refs.reserve(FSum->refs().size()); @@ -295,7 +295,7 @@ template <> struct CustomMappingTraits<GlobalValueSummaryMapTy> { } static void fixAliaseeLinks(GlobalValueSummaryMapTy &V) { for (auto &P : V) { - for (auto &Sum : P.second.SummaryList) { + for (auto &Sum : P.second.getSummaryList()) { if (auto *Alias = dyn_cast<AliasSummary>(Sum.get())) { ValueInfo AliaseeVI = Alias->getAliaseeVI(); auto AliaseeSL = AliaseeVI.getSummaryList(); diff --git a/llvm/include/llvm/IR/RuntimeLibcalls.h b/llvm/include/llvm/IR/RuntimeLibcalls.h index 307cc66..0135989 100644 --- a/llvm/include/llvm/IR/RuntimeLibcalls.h +++ b/llvm/include/llvm/IR/RuntimeLibcalls.h @@ -31,7 +31,6 @@ /// implementation, which includes a name and type signature. #define GET_RUNTIME_LIBCALL_ENUM #include "llvm/IR/RuntimeLibcalls.inc" -#undef GET_RUNTIME_LIBCALL_ENUM namespace llvm { @@ -170,7 +169,6 @@ public: // querying a real set of symbols #define GET_LOOKUP_LIBCALL_IMPL_NAME_BODY #include "llvm/IR/RuntimeLibcalls.inc" -#undef GET_LOOKUP_LIBCALL_IMPL_NAME_BODY } /// Check if this is valid libcall for the current module, otherwise @@ -238,7 +236,7 @@ private: static bool hasAEABILibcalls(const Triple &TT) { return TT.isTargetAEABI() || TT.isTargetGNUAEABI() || - TT.isTargetMuslAEABI() || TT.isAndroid(); + TT.isTargetMuslAEABI() || TT.isOSFuchsia() || TT.isAndroid(); } LLVM_READONLY diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index cd774e7..d507ba2 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -222,6 +222,7 @@ LLVM_ABI void initializeMachineSanitizerBinaryMetadataLegacyPass(PassRegistry &); LLVM_ABI void initializeMIR2VecVocabLegacyAnalysisPass(PassRegistry &); LLVM_ABI void initializeMIR2VecVocabPrinterLegacyPassPass(PassRegistry &); +LLVM_ABI void initializeMIR2VecPrinterLegacyPassPass(PassRegistry &); LLVM_ABI void initializeMachineSchedulerLegacyPass(PassRegistry &); LLVM_ABI void initializeMachineSinkingLegacyPass(PassRegistry &); LLVM_ABI void initializeMachineTraceMetricsWrapperPassPass(PassRegistry &); diff --git a/llvm/include/llvm/Support/AllocToken.h b/llvm/include/llvm/Support/AllocToken.h new file mode 100644 index 0000000..8d82670 --- /dev/null +++ b/llvm/include/llvm/Support/AllocToken.h @@ -0,0 +1,58 @@ +//===- llvm/Support/AllocToken.h - Allocation Token Calculation -----*- C++ -*// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Definition of AllocToken modes and shared calculation of stateless token IDs. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_ALLOCTOKEN_H +#define LLVM_SUPPORT_ALLOCTOKEN_H + +#include "llvm/ADT/SmallString.h" +#include <cstdint> +#include <optional> + +namespace llvm { + +/// Modes for generating allocation token IDs. +enum class AllocTokenMode { + /// Incrementally increasing token ID. + Increment, + + /// Simple mode that returns a statically-assigned random token ID. + Random, + + /// Token ID based on allocated type hash. + TypeHash, + + /// Token ID based on allocated type hash, where the top half ID-space is + /// reserved for types that contain pointers and the bottom half for types + /// that do not contain pointers. + TypeHashPointerSplit, +}; + +/// Metadata about an allocation used to generate a token ID. +struct AllocTokenMetadata { + SmallString<64> TypeName; + bool ContainsPointer; +}; + +/// Calculates stable allocation token ID. Returns std::nullopt for stateful +/// modes that are only available in the AllocToken pass. +/// +/// \param Mode The token generation mode. +/// \param Metadata The metadata about the allocation. +/// \param MaxTokens The maximum number of tokens (must not be 0) +/// \return The calculated allocation token ID, or std::nullopt. +LLVM_ABI std::optional<uint64_t> +getAllocToken(AllocTokenMode Mode, const AllocTokenMetadata &Metadata, + uint64_t MaxTokens); + +} // end namespace llvm + +#endif // LLVM_SUPPORT_ALLOCTOKEN_H diff --git a/llvm/include/llvm/Support/Timer.h b/llvm/include/llvm/Support/Timer.h index a4ed712..6a44758 100644 --- a/llvm/include/llvm/Support/Timer.h +++ b/llvm/include/llvm/Support/Timer.h @@ -66,6 +66,12 @@ public: MemUsed -= RHS.MemUsed; InstructionsExecuted -= RHS.InstructionsExecuted; } + TimeRecord operator-(const TimeRecord &RHS) const { + TimeRecord R = *this; + R -= RHS; + return R; + } + // Feel free to add operator+ if you need it /// Print the current time record to \p OS, with a breakdown showing /// contributions to the \p Total time record. diff --git a/llvm/include/llvm/Target/TargetOptions.h b/llvm/include/llvm/Target/TargetOptions.h index 2c2122a..bfd2817 100644 --- a/llvm/include/llvm/Target/TargetOptions.h +++ b/llvm/include/llvm/Target/TargetOptions.h @@ -118,9 +118,8 @@ enum CodeObjectVersionKind { class TargetOptions { public: TargetOptions() - : UnsafeFPMath(false), NoInfsFPMath(false), NoNaNsFPMath(false), - NoTrappingFPMath(true), NoSignedZerosFPMath(false), - EnableAIXExtendedAltivecABI(false), + : NoInfsFPMath(false), NoNaNsFPMath(false), NoTrappingFPMath(true), + NoSignedZerosFPMath(false), EnableAIXExtendedAltivecABI(false), HonorSignDependentRoundingFPMathOption(false), NoZerosInBSS(false), GuaranteedTailCallOpt(false), StackSymbolOrdering(true), EnableFastISel(false), EnableGlobalISel(false), UseInitArray(false), @@ -156,13 +155,6 @@ public: /// MCAsmInfo::BinutilsVersion. std::pair<int, int> BinutilsVersion{0, 0}; - /// UnsafeFPMath - This flag is enabled when the - /// -enable-unsafe-fp-math flag is specified on the command line. When - /// this flag is off (the default), the code generator is not allowed to - /// produce results that are "less precise" than IEEE allows. This includes - /// use of X86 instructions like FSIN and FCOS instead of libcalls. - unsigned UnsafeFPMath : 1; - /// NoInfsFPMath - This flag is enabled when the /// -enable-no-infs-fp-math flag is specified on the command line. When /// this flag is off (the default), the code generator is not allowed to diff --git a/llvm/include/llvm/TargetParser/Triple.h b/llvm/include/llvm/TargetParser/Triple.h index dc8cd86d..5e43444 100644 --- a/llvm/include/llvm/TargetParser/Triple.h +++ b/llvm/include/llvm/TargetParser/Triple.h @@ -935,7 +935,8 @@ public: getEnvironment() == Triple::GNUEABIHF || getEnvironment() == Triple::GNUEABIHFT64 || getEnvironment() == Triple::OpenHOS || - getEnvironment() == Triple::MuslEABIHF || isAndroid()) && + getEnvironment() == Triple::MuslEABIHF || isOSFuchsia() || + isAndroid()) && isOSBinFormatELF() && !isOSNetBSD(); } |