Import prebuilt clang toolchain for linux.
diff --git a/linux-x64/clang/include/llvm/IR/ModuleSummaryIndex.h b/linux-x64/clang/include/llvm/IR/ModuleSummaryIndex.h
new file mode 100644
index 0000000..45f8cd7
--- /dev/null
+++ b/linux-x64/clang/include/llvm/IR/ModuleSummaryIndex.h
@@ -0,0 +1,1100 @@
+//===- llvm/ModuleSummaryIndex.h - Module Summary Index ---------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// @file
+/// ModuleSummaryIndex.h This file contains the declarations the classes that
+/// hold the module index and summary for function importing.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_MODULESUMMARYINDEX_H
+#define LLVM_IR_MODULESUMMARYINDEX_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/ScaledNumber.h"
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <map>
+#include <memory>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace llvm {
+
+namespace yaml {
+
+template <typename T> struct MappingTraits;
+
+} // end namespace yaml
+
+/// \brief Class to accumulate and hold information about a callee.
+struct CalleeInfo {
+ enum class HotnessType : uint8_t {
+ Unknown = 0,
+ Cold = 1,
+ None = 2,
+ Hot = 3,
+ Critical = 4
+ };
+
+ // The size of the bit-field might need to be adjusted if more values are
+ // added to HotnessType enum.
+ uint32_t Hotness : 3;
+
+ /// The value stored in RelBlockFreq has to be interpreted as the digits of
+ /// a scaled number with a scale of \p -ScaleShift.
+ uint32_t RelBlockFreq : 29;
+ static constexpr int32_t ScaleShift = 8;
+ static constexpr uint64_t MaxRelBlockFreq = (1 << 29) - 1;
+
+ CalleeInfo()
+ : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {}
+ explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF)
+ : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
+
+ void updateHotness(const HotnessType OtherHotness) {
+ Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
+ }
+
+ HotnessType getHotness() const { return HotnessType(Hotness); }
+
+ /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq
+ ///
+ /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent
+ /// fractional values, the result is represented as a fixed point number with
+ /// scale of -ScaleShift.
+ void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
+ if (EntryFreq == 0)
+ return;
+ using Scaled64 = ScaledNumber<uint64_t>;
+ Scaled64 Temp(BlockFreq, ScaleShift);
+ Temp /= Scaled64::get(EntryFreq);
+
+ uint64_t Sum =
+ SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
+ Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
+ RelBlockFreq = static_cast<uint32_t>(Sum);
+ }
+};
+
+class GlobalValueSummary;
+
+using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
+
+struct GlobalValueSummaryInfo {
+ union NameOrGV {
+ NameOrGV(bool IsAnalysis) {
+ if (IsAnalysis)
+ GV = nullptr;
+ else
+ Name = "";
+ }
+
+ /// The GlobalValue corresponding to this summary. This is only used in
+ /// per-module summaries, when module analysis is being run.
+ const GlobalValue *GV;
+
+ /// Summary string representation. This StringRef points to BC module
+ /// string table and is valid until module data is stored in memory.
+ /// This is guaranteed to happen until runThinLTOBackend function is
+ /// called, so it is safe to use this field during thin link. This field
+ /// is only valid if summary index was loaded from BC file.
+ StringRef Name;
+ } U;
+
+ GlobalValueSummaryInfo(bool IsAnalysis) : U(IsAnalysis) {}
+
+ /// 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.
+ GlobalValueSummaryList SummaryList;
+};
+
+/// Map from global value GUID to corresponding summary structures. Use a
+/// std::map rather than a DenseMap so that pointers to the map's value_type
+/// (which are used by ValueInfo) are not invalidated by insertion. Also it will
+/// likely incur less overhead, as the value type is not very small and the size
+/// of the map is unknown, resulting in inefficiencies due to repeated
+/// insertions and resizing.
+using GlobalValueSummaryMapTy =
+ std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
+
+/// Struct that holds a reference to a particular GUID in a global value
+/// summary.
+struct ValueInfo {
+ PointerIntPair<const GlobalValueSummaryMapTy::value_type *, 1, bool>
+ RefAndFlag;
+
+ ValueInfo() = default;
+ ValueInfo(bool IsAnalysis, const GlobalValueSummaryMapTy::value_type *R) {
+ RefAndFlag.setPointer(R);
+ RefAndFlag.setInt(IsAnalysis);
+ }
+
+ operator bool() const { return getRef(); }
+
+ GlobalValue::GUID getGUID() const { return getRef()->first; }
+ const GlobalValue *getValue() const {
+ assert(isFromAnalysis());
+ return getRef()->second.U.GV;
+ }
+
+ ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
+ return getRef()->second.SummaryList;
+ }
+
+ StringRef name() const {
+ return isFromAnalysis() ? getRef()->second.U.GV->getName()
+ : getRef()->second.U.Name;
+ }
+
+ bool isFromAnalysis() const { return RefAndFlag.getInt(); }
+
+ const GlobalValueSummaryMapTy::value_type *getRef() const {
+ return RefAndFlag.getPointer();
+ }
+
+ bool isDSOLocal() const;
+};
+
+inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
+ assert(A.getRef() && B.getRef() &&
+ "Need ValueInfo with non-null Ref to compare GUIDs");
+ return A.getRef() == B.getRef();
+}
+
+inline bool operator!=(const ValueInfo &A, const ValueInfo &B) {
+ assert(A.getRef() && B.getRef() &&
+ "Need ValueInfo with non-null Ref to compare GUIDs");
+ return A.getGUID() != B.getGUID();
+}
+
+inline bool operator<(const ValueInfo &A, const ValueInfo &B) {
+ assert(A.getRef() && B.getRef() &&
+ "Need ValueInfo with non-null Ref to compare GUIDs");
+ return A.getGUID() < B.getGUID();
+}
+
+template <> struct DenseMapInfo<ValueInfo> {
+ static inline ValueInfo getEmptyKey() {
+ return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
+ }
+
+ static inline ValueInfo getTombstoneKey() {
+ return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16);
+ }
+
+ static inline bool isSpecialKey(ValueInfo V) {
+ return V == getTombstoneKey() || V == getEmptyKey();
+ }
+
+ static bool isEqual(ValueInfo L, ValueInfo R) {
+ // We are not supposed to mix ValueInfo(s) with different analysis flag
+ // in a same container.
+ assert(isSpecialKey(L) || isSpecialKey(R) ||
+ (L.isFromAnalysis() == R.isFromAnalysis()));
+ return L.getRef() == R.getRef();
+ }
+ static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }
+};
+
+/// \brief Function and variable summary information to aid decisions and
+/// implementation of importing.
+class GlobalValueSummary {
+public:
+ /// \brief Sububclass discriminator (for dyn_cast<> et al.)
+ enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
+
+ /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
+ struct GVFlags {
+ /// \brief The linkage type of the associated global value.
+ ///
+ /// One use is to flag values that have local linkage types and need to
+ /// have module identifier appended before placing into the combined
+ /// index, to disambiguate from other values with the same name.
+ /// In the future this will be used to update and optimize linkage
+ /// types based on global summary-based analysis.
+ unsigned Linkage : 4;
+
+ /// Indicate if the global value cannot be imported (e.g. it cannot
+ /// be renamed or references something that can't be renamed).
+ unsigned NotEligibleToImport : 1;
+
+ /// In per-module summary, indicate that the global value must be considered
+ /// a live root for index-based liveness analysis. Used for special LLVM
+ /// values such as llvm.global_ctors that the linker does not know about.
+ ///
+ /// In combined summary, indicate that the global value is live.
+ unsigned Live : 1;
+
+ /// Indicates that the linker resolved the symbol to a definition from
+ /// within the same linkage unit.
+ unsigned DSOLocal : 1;
+
+ /// Convenience Constructors
+ explicit GVFlags(GlobalValue::LinkageTypes Linkage,
+ bool NotEligibleToImport, bool Live, bool IsLocal)
+ : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
+ Live(Live), DSOLocal(IsLocal) {}
+ };
+
+private:
+ /// Kind of summary for use in dyn_cast<> et al.
+ SummaryKind Kind;
+
+ GVFlags Flags;
+
+ /// This is the hash of the name of the symbol in the original file. It is
+ /// identical to the GUID for global symbols, but differs for local since the
+ /// GUID includes the module level id in the hash.
+ GlobalValue::GUID OriginalName = 0;
+
+ /// \brief Path of module IR containing value's definition, used to locate
+ /// module during importing.
+ ///
+ /// This is only used during parsing of the combined index, or when
+ /// parsing the per-module index for creation of the combined summary index,
+ /// not during writing of the per-module index which doesn't contain a
+ /// module path string table.
+ StringRef ModulePath;
+
+ /// List of values referenced by this global value's definition
+ /// (either by the initializer of a global variable, or referenced
+ /// from within a function). This does not include functions called, which
+ /// are listed in the derived FunctionSummary object.
+ std::vector<ValueInfo> RefEdgeList;
+
+protected:
+ GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
+ : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
+ assert((K != AliasKind || Refs.empty()) &&
+ "Expect no references for AliasSummary");
+ }
+
+public:
+ virtual ~GlobalValueSummary() = default;
+
+ /// Returns the hash of the original name, it is identical to the GUID for
+ /// externally visible symbols, but not for local ones.
+ GlobalValue::GUID getOriginalName() { return OriginalName; }
+
+ /// Initialize the original name hash in this summary.
+ void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
+
+ /// Which kind of summary subclass this is.
+ SummaryKind getSummaryKind() const { return Kind; }
+
+ /// Set the path to the module containing this function, for use in
+ /// the combined index.
+ void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
+
+ /// Get the path to the module containing this function.
+ StringRef modulePath() const { return ModulePath; }
+
+ /// Get the flags for this GlobalValue (see \p struct GVFlags).
+ GVFlags flags() { return Flags; }
+
+ /// Return linkage type recorded for this global value.
+ GlobalValue::LinkageTypes linkage() const {
+ return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
+ }
+
+ /// Sets the linkage to the value determined by global summary-based
+ /// optimization. Will be applied in the ThinLTO backends.
+ void setLinkage(GlobalValue::LinkageTypes Linkage) {
+ Flags.Linkage = Linkage;
+ }
+
+ /// Return true if this global value can't be imported.
+ bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
+
+ bool isLive() const { return Flags.Live; }
+
+ void setLive(bool Live) { Flags.Live = Live; }
+
+ void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
+
+ bool isDSOLocal() const { return Flags.DSOLocal; }
+
+ /// Flag that this global value cannot be imported.
+ void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
+
+ /// Return the list of values referenced by this global value definition.
+ ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
+
+ /// If this is an alias summary, returns the summary of the aliased object (a
+ /// global variable or function), otherwise returns itself.
+ GlobalValueSummary *getBaseObject();
+ const GlobalValueSummary *getBaseObject() const;
+
+ friend class ModuleSummaryIndex;
+};
+
+/// \brief Alias summary information.
+class AliasSummary : public GlobalValueSummary {
+ GlobalValueSummary *AliaseeSummary;
+ // AliaseeGUID is only set and accessed when we are building a combined index
+ // via the BitcodeReader.
+ GlobalValue::GUID AliaseeGUID;
+
+public:
+ AliasSummary(GVFlags Flags)
+ : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
+ AliaseeSummary(nullptr), AliaseeGUID(0) {}
+
+ /// Check if this is an alias summary.
+ static bool classof(const GlobalValueSummary *GVS) {
+ return GVS->getSummaryKind() == AliasKind;
+ }
+
+ void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; }
+ void setAliaseeGUID(GlobalValue::GUID GUID) { AliaseeGUID = GUID; }
+
+ const GlobalValueSummary &getAliasee() const {
+ assert(AliaseeSummary && "Unexpected missing aliasee summary");
+ return *AliaseeSummary;
+ }
+
+ GlobalValueSummary &getAliasee() {
+ return const_cast<GlobalValueSummary &>(
+ static_cast<const AliasSummary *>(this)->getAliasee());
+ }
+ const GlobalValue::GUID &getAliaseeGUID() const {
+ assert(AliaseeGUID && "Unexpected missing aliasee GUID");
+ return AliaseeGUID;
+ }
+};
+
+const inline GlobalValueSummary *GlobalValueSummary::getBaseObject() const {
+ if (auto *AS = dyn_cast<AliasSummary>(this))
+ return &AS->getAliasee();
+ return this;
+}
+
+inline GlobalValueSummary *GlobalValueSummary::getBaseObject() {
+ if (auto *AS = dyn_cast<AliasSummary>(this))
+ return &AS->getAliasee();
+ return this;
+}
+
+/// \brief Function summary information to aid decisions and implementation of
+/// importing.
+class FunctionSummary : public GlobalValueSummary {
+public:
+ /// <CalleeValueInfo, CalleeInfo> call edge pair.
+ using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
+
+ /// An "identifier" for a virtual function. This contains the type identifier
+ /// represented as a GUID and the offset from the address point to the virtual
+ /// function pointer, where "address point" is as defined in the Itanium ABI:
+ /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
+ struct VFuncId {
+ GlobalValue::GUID GUID;
+ uint64_t Offset;
+ };
+
+ /// A specification for a virtual function call with all constant integer
+ /// arguments. This is used to perform virtual constant propagation on the
+ /// summary.
+ struct ConstVCall {
+ VFuncId VFunc;
+ std::vector<uint64_t> Args;
+ };
+
+ /// Function attribute flags. Used to track if a function accesses memory,
+ /// recurses or aliases.
+ struct FFlags {
+ unsigned ReadNone : 1;
+ unsigned ReadOnly : 1;
+ unsigned NoRecurse : 1;
+ unsigned ReturnDoesNotAlias : 1;
+ };
+
+ /// Create an empty FunctionSummary (with specified call edges).
+ /// Used to represent external nodes and the dummy root node.
+ static FunctionSummary
+ makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
+ return FunctionSummary(
+ FunctionSummary::GVFlags(
+ GlobalValue::LinkageTypes::AvailableExternallyLinkage,
+ /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false),
+ 0, FunctionSummary::FFlags{}, std::vector<ValueInfo>(),
+ std::move(Edges), std::vector<GlobalValue::GUID>(),
+ std::vector<FunctionSummary::VFuncId>(),
+ std::vector<FunctionSummary::VFuncId>(),
+ std::vector<FunctionSummary::ConstVCall>(),
+ std::vector<FunctionSummary::ConstVCall>());
+ }
+
+ /// A dummy node to reference external functions that aren't in the index
+ static FunctionSummary ExternalNode;
+
+private:
+ /// Number of instructions (ignoring debug instructions, e.g.) computed
+ /// during the initial compile step when the summary index is first built.
+ unsigned InstCount;
+
+ /// Function attribute flags. Used to track if a function accesses memory,
+ /// recurses or aliases.
+ FFlags FunFlags;
+
+ /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
+ std::vector<EdgeTy> CallGraphEdgeList;
+
+ /// All type identifier related information. Because these fields are
+ /// relatively uncommon we only allocate space for them if necessary.
+ struct TypeIdInfo {
+ /// List of type identifiers used by this function in llvm.type.test
+ /// intrinsics other than by an llvm.assume intrinsic, represented as GUIDs.
+ std::vector<GlobalValue::GUID> TypeTests;
+
+ /// List of virtual calls made by this function using (respectively)
+ /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
+ /// not have all constant integer arguments.
+ std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
+
+ /// List of virtual calls made by this function using (respectively)
+ /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
+ /// all constant integer arguments.
+ std::vector<ConstVCall> TypeTestAssumeConstVCalls,
+ TypeCheckedLoadConstVCalls;
+ };
+
+ std::unique_ptr<TypeIdInfo> TIdInfo;
+
+public:
+ FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
+ std::vector<ValueInfo> Refs, std::vector<EdgeTy> CGEdges,
+ std::vector<GlobalValue::GUID> TypeTests,
+ std::vector<VFuncId> TypeTestAssumeVCalls,
+ std::vector<VFuncId> TypeCheckedLoadVCalls,
+ std::vector<ConstVCall> TypeTestAssumeConstVCalls,
+ std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
+ : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
+ InstCount(NumInsts), FunFlags(FunFlags),
+ CallGraphEdgeList(std::move(CGEdges)) {
+ if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
+ !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
+ !TypeCheckedLoadConstVCalls.empty())
+ TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
+ std::move(TypeTests), std::move(TypeTestAssumeVCalls),
+ std::move(TypeCheckedLoadVCalls),
+ std::move(TypeTestAssumeConstVCalls),
+ std::move(TypeCheckedLoadConstVCalls)});
+ }
+
+ /// Check if this is a function summary.
+ static bool classof(const GlobalValueSummary *GVS) {
+ return GVS->getSummaryKind() == FunctionKind;
+ }
+
+ /// Get function attribute flags.
+ FFlags &fflags() { return FunFlags; }
+
+ /// Get the instruction count recorded for this function.
+ unsigned instCount() const { return InstCount; }
+
+ /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
+ ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
+
+ /// Returns the list of type identifiers used by this function in
+ /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
+ /// represented as GUIDs.
+ ArrayRef<GlobalValue::GUID> type_tests() const {
+ if (TIdInfo)
+ return TIdInfo->TypeTests;
+ return {};
+ }
+
+ /// Returns the list of virtual calls made by this function using
+ /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
+ /// integer arguments.
+ ArrayRef<VFuncId> type_test_assume_vcalls() const {
+ if (TIdInfo)
+ return TIdInfo->TypeTestAssumeVCalls;
+ return {};
+ }
+
+ /// Returns the list of virtual calls made by this function using
+ /// llvm.type.checked.load intrinsics that do not have all constant integer
+ /// arguments.
+ ArrayRef<VFuncId> type_checked_load_vcalls() const {
+ if (TIdInfo)
+ return TIdInfo->TypeCheckedLoadVCalls;
+ return {};
+ }
+
+ /// Returns the list of virtual calls made by this function using
+ /// llvm.assume(llvm.type.test) intrinsics with all constant integer
+ /// arguments.
+ ArrayRef<ConstVCall> type_test_assume_const_vcalls() const {
+ if (TIdInfo)
+ return TIdInfo->TypeTestAssumeConstVCalls;
+ return {};
+ }
+
+ /// Returns the list of virtual calls made by this function using
+ /// llvm.type.checked.load intrinsics with all constant integer arguments.
+ ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
+ if (TIdInfo)
+ return TIdInfo->TypeCheckedLoadConstVCalls;
+ return {};
+ }
+
+ /// Add a type test to the summary. This is used by WholeProgramDevirt if we
+ /// were unable to devirtualize a checked call.
+ void addTypeTest(GlobalValue::GUID Guid) {
+ if (!TIdInfo)
+ TIdInfo = llvm::make_unique<TypeIdInfo>();
+ TIdInfo->TypeTests.push_back(Guid);
+ }
+
+ friend struct GraphTraits<ValueInfo>;
+};
+
+template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
+ static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
+
+ static FunctionSummary::VFuncId getTombstoneKey() {
+ return {0, uint64_t(-2)};
+ }
+
+ static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
+ return L.GUID == R.GUID && L.Offset == R.Offset;
+ }
+
+ static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
+};
+
+template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
+ static FunctionSummary::ConstVCall getEmptyKey() {
+ return {{0, uint64_t(-1)}, {}};
+ }
+
+ static FunctionSummary::ConstVCall getTombstoneKey() {
+ return {{0, uint64_t(-2)}, {}};
+ }
+
+ static bool isEqual(FunctionSummary::ConstVCall L,
+ FunctionSummary::ConstVCall R) {
+ return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
+ L.Args == R.Args;
+ }
+
+ static unsigned getHashValue(FunctionSummary::ConstVCall I) {
+ return I.VFunc.GUID;
+ }
+};
+
+/// \brief Global variable summary information to aid decisions and
+/// implementation of importing.
+///
+/// Currently this doesn't add anything to the base \p GlobalValueSummary,
+/// but is a placeholder as additional info may be added to the summary
+/// for variables.
+class GlobalVarSummary : public GlobalValueSummary {
+
+public:
+ GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
+ : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)) {}
+
+ /// Check if this is a global variable summary.
+ static bool classof(const GlobalValueSummary *GVS) {
+ return GVS->getSummaryKind() == GlobalVarKind;
+ }
+};
+
+struct TypeTestResolution {
+ /// Specifies which kind of type check we should emit for this byte array.
+ /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
+ /// details on each kind of check; the enumerators are described with
+ /// reference to that document.
+ enum Kind {
+ Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
+ ByteArray, ///< Test a byte array (first example)
+ Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
+ Single, ///< Single element (last example in "Short Inline Bit Vectors")
+ AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
+ /// All-Ones Bit Vectors")
+ } TheKind = Unsat;
+
+ /// Range of size-1 expressed as a bit width. For example, if the size is in
+ /// range [1,256], this number will be 8. This helps generate the most compact
+ /// instruction sequences.
+ unsigned SizeM1BitWidth = 0;
+
+ // The following fields are only used if the target does not support the use
+ // of absolute symbols to store constants. Their meanings are the same as the
+ // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
+ // LowerTypeTests.cpp.
+
+ uint64_t AlignLog2 = 0;
+ uint64_t SizeM1 = 0;
+ uint8_t BitMask = 0;
+ uint64_t InlineBits = 0;
+};
+
+struct WholeProgramDevirtResolution {
+ enum Kind {
+ Indir, ///< Just do a regular virtual call
+ SingleImpl, ///< Single implementation devirtualization
+ BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
+ ///< that is defined in the merged module. Otherwise same as
+ ///< Indir.
+ } TheKind = Indir;
+
+ std::string SingleImplName;
+
+ struct ByArg {
+ enum Kind {
+ Indir, ///< Just do a regular virtual call
+ UniformRetVal, ///< Uniform return value optimization
+ UniqueRetVal, ///< Unique return value optimization
+ VirtualConstProp, ///< Virtual constant propagation
+ } TheKind = Indir;
+
+ /// Additional information for the resolution:
+ /// - UniformRetVal: the uniform return value.
+ /// - UniqueRetVal: the return value associated with the unique vtable (0 or
+ /// 1).
+ uint64_t Info = 0;
+
+ // The following fields are only used if the target does not support the use
+ // of absolute symbols to store constants.
+
+ uint32_t Byte = 0;
+ uint32_t Bit = 0;
+ };
+
+ /// Resolutions for calls with all constant integer arguments (excluding the
+ /// first argument, "this"), where the key is the argument vector.
+ std::map<std::vector<uint64_t>, ByArg> ResByArg;
+};
+
+struct TypeIdSummary {
+ TypeTestResolution TTRes;
+
+ /// Mapping from byte offset to whole-program devirt resolution for that
+ /// (typeid, byte offset) pair.
+ std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
+};
+
+/// 160 bits SHA1
+using ModuleHash = std::array<uint32_t, 5>;
+
+/// Type used for iterating through the global value summary map.
+using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
+using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
+
+/// String table to hold/own module path strings, which additionally holds the
+/// module ID assigned to each module during the plugin step, as well as a hash
+/// of the module. The StringMap makes a copy of and owns inserted strings.
+using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
+
+/// Map of global value GUID to its summary, used to identify values defined in
+/// a particular module, and provide efficient access to their summary.
+using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
+
+/// Class to hold module path string table and global value map,
+/// and encapsulate methods for operating on them.
+class ModuleSummaryIndex {
+private:
+ /// Map from value name to list of summary instances for values of that
+ /// name (may be duplicates in the COMDAT case, e.g.).
+ GlobalValueSummaryMapTy GlobalValueMap;
+
+ /// Holds strings for combined index, mapping to the corresponding module ID.
+ ModulePathStringTableTy ModulePathStringTable;
+
+ /// Mapping from type identifiers to summary information for that type
+ /// identifier.
+ std::map<std::string, TypeIdSummary> TypeIdMap;
+
+ /// Mapping from original ID to GUID. If original ID can map to multiple
+ /// GUIDs, it will be mapped to 0.
+ std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
+
+ /// Indicates that summary-based GlobalValue GC has run, and values with
+ /// GVFlags::Live==false are really dead. Otherwise, all values must be
+ /// considered live.
+ bool WithGlobalValueDeadStripping = false;
+
+ /// Indicates that distributed backend should skip compilation of the
+ /// module. Flag is suppose to be set by distributed ThinLTO indexing
+ /// when it detected that the module is not needed during the final
+ /// linking. As result distributed backend should just output a minimal
+ /// valid object file.
+ bool SkipModuleByDistributedBackend = false;
+
+ /// If true then we're performing analysis of IR module, filling summary
+ /// accordingly. The value of 'false' means we're reading summary from
+ /// BC or YAML source. Affects the type of value stored in NameOrGV union
+ bool IsAnalysis;
+
+ std::set<std::string> CfiFunctionDefs;
+ std::set<std::string> CfiFunctionDecls;
+
+ // YAML I/O support.
+ friend yaml::MappingTraits<ModuleSummaryIndex>;
+
+ GlobalValueSummaryMapTy::value_type *
+ getOrInsertValuePtr(GlobalValue::GUID GUID) {
+ return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(IsAnalysis)).first;
+ }
+
+public:
+ // See IsAnalysis variable comment.
+ ModuleSummaryIndex(bool IsPerformingAnalysis)
+ : IsAnalysis(IsPerformingAnalysis) {}
+
+ bool isPerformingAnalysis() const { return IsAnalysis; }
+
+ gvsummary_iterator begin() { return GlobalValueMap.begin(); }
+ const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
+ gvsummary_iterator end() { return GlobalValueMap.end(); }
+ const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
+ size_t size() const { return GlobalValueMap.size(); }
+
+ /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
+ /// the FunctionHasParent map.
+ static void discoverNodes(ValueInfo V,
+ std::map<ValueInfo, bool> &FunctionHasParent) {
+ if (!V.getSummaryList().size())
+ return; // skip external functions that don't have summaries
+
+ // Mark discovered if we haven't yet
+ auto S = FunctionHasParent.emplace(V, false);
+
+ // Stop if we've already discovered this node
+ if (!S.second)
+ return;
+
+ FunctionSummary *F =
+ dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
+ assert(F != nullptr && "Expected FunctionSummary node");
+
+ for (auto &C : F->calls()) {
+ // Insert node if necessary
+ auto S = FunctionHasParent.emplace(C.first, true);
+
+ // Skip nodes that we're sure have parents
+ if (!S.second && S.first->second)
+ continue;
+
+ if (S.second)
+ discoverNodes(C.first, FunctionHasParent);
+ else
+ S.first->second = true;
+ }
+ }
+
+ // Calculate the callgraph root
+ FunctionSummary calculateCallGraphRoot() {
+ // Functions that have a parent will be marked in FunctionHasParent pair.
+ // Once we've marked all functions, the functions in the map that are false
+ // have no parent (so they're the roots)
+ std::map<ValueInfo, bool> FunctionHasParent;
+
+ for (auto &S : *this) {
+ // Skip external functions
+ if (!S.second.SummaryList.size() ||
+ !isa<FunctionSummary>(S.second.SummaryList.front().get()))
+ continue;
+ discoverNodes(ValueInfo(IsAnalysis, &S), FunctionHasParent);
+ }
+
+ std::vector<FunctionSummary::EdgeTy> Edges;
+ // create edges to all roots in the Index
+ for (auto &P : FunctionHasParent) {
+ if (P.second)
+ continue; // skip over non-root nodes
+ Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
+ }
+ if (Edges.empty()) {
+ // Failed to find root - return an empty node
+ return FunctionSummary::makeDummyFunctionSummary({});
+ }
+ auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
+ return CallGraphRoot;
+ }
+
+ bool withGlobalValueDeadStripping() const {
+ return WithGlobalValueDeadStripping;
+ }
+ void setWithGlobalValueDeadStripping() {
+ WithGlobalValueDeadStripping = true;
+ }
+
+ bool skipModuleByDistributedBackend() const {
+ return SkipModuleByDistributedBackend;
+ }
+ void setSkipModuleByDistributedBackend() {
+ SkipModuleByDistributedBackend = true;
+ }
+
+ bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
+ return !WithGlobalValueDeadStripping || GVS->isLive();
+ }
+ bool isGUIDLive(GlobalValue::GUID GUID) const;
+
+ /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
+ ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
+ auto I = GlobalValueMap.find(GUID);
+ return ValueInfo(IsAnalysis, I == GlobalValueMap.end() ? nullptr : &*I);
+ }
+
+ /// Return a ValueInfo for \p GUID.
+ ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
+ return ValueInfo(IsAnalysis, getOrInsertValuePtr(GUID));
+ }
+
+ /// Return a ValueInfo for \p GUID setting value \p Name.
+ ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) {
+ assert(!IsAnalysis);
+ auto VP = getOrInsertValuePtr(GUID);
+ VP->second.U.Name = Name;
+ return ValueInfo(IsAnalysis, VP);
+ }
+
+ /// Return a ValueInfo for \p GV and mark it as belonging to GV.
+ ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
+ assert(IsAnalysis);
+ auto VP = getOrInsertValuePtr(GV->getGUID());
+ VP->second.U.GV = GV;
+ return ValueInfo(IsAnalysis, VP);
+ }
+
+ /// Return the GUID for \p OriginalId in the OidGuidMap.
+ GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const {
+ const auto I = OidGuidMap.find(OriginalID);
+ return I == OidGuidMap.end() ? 0 : I->second;
+ }
+
+ std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
+ const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
+
+ std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
+ const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
+
+ /// Add a global value summary for a value of the given name.
+ void addGlobalValueSummary(StringRef ValueName,
+ std::unique_ptr<GlobalValueSummary> Summary) {
+ addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
+ std::move(Summary));
+ }
+
+ /// Add a global value summary for the given ValueInfo.
+ void addGlobalValueSummary(ValueInfo VI,
+ std::unique_ptr<GlobalValueSummary> Summary) {
+ addOriginalName(VI.getGUID(), Summary->getOriginalName());
+ // 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));
+ }
+
+ /// Add an original name for the value of the given GUID.
+ void addOriginalName(GlobalValue::GUID ValueGUID,
+ GlobalValue::GUID OrigGUID) {
+ if (OrigGUID == 0 || ValueGUID == OrigGUID)
+ return;
+ if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
+ OidGuidMap[OrigGUID] = 0;
+ else
+ OidGuidMap[OrigGUID] = ValueGUID;
+ }
+
+ /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
+ /// not found.
+ GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
+ StringRef ModuleId) const {
+ auto CalleeInfo = getValueInfo(ValueGUID);
+ if (!CalleeInfo) {
+ return nullptr; // This function does not have a summary
+ }
+ auto Summary =
+ llvm::find_if(CalleeInfo.getSummaryList(),
+ [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
+ return Summary->modulePath() == ModuleId;
+ });
+ if (Summary == CalleeInfo.getSummaryList().end())
+ return nullptr;
+ return Summary->get();
+ }
+
+ /// Returns the first GlobalValueSummary for \p GV, asserting that there
+ /// is only one if \p PerModuleIndex.
+ GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
+ bool PerModuleIndex = true) const {
+ assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name");
+ return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()),
+ PerModuleIndex);
+ }
+
+ /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
+ /// there
+ /// is only one if \p PerModuleIndex.
+ GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
+ bool PerModuleIndex = true) const;
+
+ /// Table of modules, containing module hash and id.
+ const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
+ return ModulePathStringTable;
+ }
+
+ /// Table of modules, containing hash and id.
+ StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
+ return ModulePathStringTable;
+ }
+
+ /// Get the module ID recorded for the given module path.
+ uint64_t getModuleId(const StringRef ModPath) const {
+ return ModulePathStringTable.lookup(ModPath).first;
+ }
+
+ /// Get the module SHA1 hash recorded for the given module path.
+ const ModuleHash &getModuleHash(const StringRef ModPath) const {
+ auto It = ModulePathStringTable.find(ModPath);
+ assert(It != ModulePathStringTable.end() && "Module not registered");
+ return It->second.second;
+ }
+
+ /// Convenience method for creating a promoted global name
+ /// for the given value name of a local, and its original module's ID.
+ static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
+ SmallString<256> NewName(Name);
+ NewName += ".llvm.";
+ NewName += utostr((uint64_t(ModHash[0]) << 32) |
+ ModHash[1]); // Take the first 64 bits
+ return NewName.str();
+ }
+
+ /// Helper to obtain the unpromoted name for a global value (or the original
+ /// name if not promoted).
+ static StringRef getOriginalNameBeforePromote(StringRef Name) {
+ std::pair<StringRef, StringRef> Pair = Name.split(".llvm.");
+ return Pair.first;
+ }
+
+ typedef ModulePathStringTableTy::value_type ModuleInfo;
+
+ /// Add a new module with the given \p Hash, mapped to the given \p
+ /// ModID, and return a reference to the module.
+ ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
+ ModuleHash Hash = ModuleHash{{0}}) {
+ return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
+ }
+
+ /// Check if the given Module has any functions available for exporting
+ /// in the index. We consider any module present in the ModulePathStringTable
+ /// to have exported functions.
+ bool hasExportedFunctions(const Module &M) const {
+ return ModulePathStringTable.count(M.getModuleIdentifier());
+ }
+
+ const std::map<std::string, TypeIdSummary> &typeIds() const {
+ return TypeIdMap;
+ }
+
+ /// This accessor should only be used when exporting because it can mutate the
+ /// map.
+ TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
+ return TypeIdMap[TypeId];
+ }
+
+ /// This returns either a pointer to the type id summary (if present in the
+ /// summary map) or null (if not present). This may be used when importing.
+ const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
+ auto I = TypeIdMap.find(TypeId);
+ if (I == TypeIdMap.end())
+ return nullptr;
+ return &I->second;
+ }
+
+ /// Collect for the given module the list of function it defines
+ /// (GUID -> Summary).
+ void collectDefinedFunctionsForModule(StringRef ModulePath,
+ GVSummaryMapTy &GVSummaryMap) const;
+
+ /// Collect for each module the list of Summaries it defines (GUID ->
+ /// Summary).
+ void collectDefinedGVSummariesPerModule(
+ StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
+
+ /// Export summary to dot file for GraphViz.
+ void exportToDot(raw_ostream& OS) const;
+
+ /// Print out strongly connected components for debugging.
+ void dumpSCCs(raw_ostream &OS);
+};
+
+/// GraphTraits definition to build SCC for the index
+template <> struct GraphTraits<ValueInfo> {
+ typedef ValueInfo NodeRef;
+
+ static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) {
+ return P.first;
+ }
+ using ChildIteratorType =
+ mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator,
+ decltype(&valueInfoFromEdge)>;
+
+ static NodeRef getEntryNode(ValueInfo V) { return V; }
+
+ static ChildIteratorType child_begin(NodeRef N) {
+ if (!N.getSummaryList().size()) // handle external function
+ return ChildIteratorType(
+ FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
+ &valueInfoFromEdge);
+ FunctionSummary *F =
+ cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
+ return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
+ }
+
+ static ChildIteratorType child_end(NodeRef N) {
+ if (!N.getSummaryList().size()) // handle external function
+ return ChildIteratorType(
+ FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
+ &valueInfoFromEdge);
+ FunctionSummary *F =
+ cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
+ return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
+ }
+};
+
+template <>
+struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> {
+ static NodeRef getEntryNode(ModuleSummaryIndex *I) {
+ std::unique_ptr<GlobalValueSummary> Root =
+ make_unique<FunctionSummary>(I->calculateCallGraphRoot());
+ GlobalValueSummaryInfo G(I->isPerformingAnalysis());
+ G.SummaryList.push_back(std::move(Root));
+ static auto P =
+ GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
+ return ValueInfo(I->isPerformingAnalysis(), &P);
+ }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_IR_MODULESUMMARYINDEX_H