| //===- llvm/ModuleSummaryIndex.h - Module Summary Index ---------*- 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 |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| /// @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/ConstantRange.h" |
| #include "llvm/IR/GlobalValue.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/Support/Allocator.h" |
| #include "llvm/Support/MathExtras.h" |
| #include "llvm/Support/ScaledNumber.h" |
| #include "llvm/Support/StringSaver.h" |
| #include "llvm/Support/raw_ostream.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 { |
| |
| template <class GraphType> struct GraphTraits; |
| |
| namespace yaml { |
| |
| template <typename T> struct MappingTraits; |
| |
| } // end namespace yaml |
| |
| /// 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); |
| } |
| }; |
| |
| inline const char *getHotnessName(CalleeInfo::HotnessType HT) { |
| switch (HT) { |
| case CalleeInfo::HotnessType::Unknown: |
| return "unknown"; |
| case CalleeInfo::HotnessType::Cold: |
| return "cold"; |
| case CalleeInfo::HotnessType::None: |
| return "none"; |
| case CalleeInfo::HotnessType::Hot: |
| return "hot"; |
| case CalleeInfo::HotnessType::Critical: |
| return "critical"; |
| } |
| llvm_unreachable("invalid hotness"); |
| } |
| |
| class GlobalValueSummary; |
| |
| using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>; |
| |
| struct alignas(8) GlobalValueSummaryInfo { |
| union NameOrGV { |
| NameOrGV(bool HaveGVs) { |
| if (HaveGVs) |
| GV = nullptr; |
| else |
| Name = ""; |
| } |
| |
| /// The GlobalValue corresponding to this summary. This is only used in |
| /// per-module summaries and when the IR is available. E.g. when module |
| /// analysis is being run, or when parsing both the IR and the summary |
| /// from assembly. |
| 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 HaveGVs) : U(HaveGVs) {} |
| |
| /// 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 { |
| enum Flags { HaveGV = 1, ReadOnly = 2, WriteOnly = 4 }; |
| PointerIntPair<const GlobalValueSummaryMapTy::value_type *, 3, int> |
| RefAndFlags; |
| |
| ValueInfo() = default; |
| ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R) { |
| RefAndFlags.setPointer(R); |
| RefAndFlags.setInt(HaveGVs); |
| } |
| |
| explicit operator bool() const { return getRef(); } |
| |
| GlobalValue::GUID getGUID() const { return getRef()->first; } |
| const GlobalValue *getValue() const { |
| assert(haveGVs()); |
| return getRef()->second.U.GV; |
| } |
| |
| ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const { |
| return getRef()->second.SummaryList; |
| } |
| |
| StringRef name() const { |
| return haveGVs() ? getRef()->second.U.GV->getName() |
| : getRef()->second.U.Name; |
| } |
| |
| bool haveGVs() const { return RefAndFlags.getInt() & HaveGV; } |
| bool isReadOnly() const { |
| assert(isValidAccessSpecifier()); |
| return RefAndFlags.getInt() & ReadOnly; |
| } |
| bool isWriteOnly() const { |
| assert(isValidAccessSpecifier()); |
| return RefAndFlags.getInt() & WriteOnly; |
| } |
| unsigned getAccessSpecifier() const { |
| assert(isValidAccessSpecifier()); |
| return RefAndFlags.getInt() & (ReadOnly | WriteOnly); |
| } |
| bool isValidAccessSpecifier() const { |
| unsigned BadAccessMask = ReadOnly | WriteOnly; |
| return (RefAndFlags.getInt() & BadAccessMask) != BadAccessMask; |
| } |
| void setReadOnly() { |
| // We expect ro/wo attribute to set only once during |
| // ValueInfo lifetime. |
| assert(getAccessSpecifier() == 0); |
| RefAndFlags.setInt(RefAndFlags.getInt() | ReadOnly); |
| } |
| void setWriteOnly() { |
| assert(getAccessSpecifier() == 0); |
| RefAndFlags.setInt(RefAndFlags.getInt() | WriteOnly); |
| } |
| |
| const GlobalValueSummaryMapTy::value_type *getRef() const { |
| return RefAndFlags.getPointer(); |
| } |
| |
| /// Returns the most constraining visibility among summaries. The |
| /// visibilities, ordered from least to most constraining, are: default, |
| /// protected and hidden. |
| GlobalValue::VisibilityTypes getELFVisibility() const; |
| |
| /// Checks if all summaries are DSO local (have the flag set). When DSOLocal |
| /// propagation has been done, set the parameter to enable fast check. |
| bool isDSOLocal(bool WithDSOLocalPropagation = false) const; |
| |
| /// Checks if all copies are eligible for auto-hiding (have flag set). |
| bool canAutoHide() const; |
| }; |
| |
| inline raw_ostream &operator<<(raw_ostream &OS, const ValueInfo &VI) { |
| OS << VI.getGUID(); |
| if (!VI.name().empty()) |
| OS << " (" << VI.name() << ")"; |
| return OS; |
| } |
| |
| inline bool operator==(const ValueInfo &A, const ValueInfo &B) { |
| assert(A.getRef() && B.getRef() && |
| "Need ValueInfo with non-null Ref for comparison"); |
| 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 for comparison"); |
| 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(); |
| } |
| |
| 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 HaveGVs flag |
| // in a same container. |
| assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs())); |
| return L.getRef() == R.getRef(); |
| } |
| static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); } |
| }; |
| |
| /// Function and variable summary information to aid decisions and |
| /// implementation of importing. |
| class GlobalValueSummary { |
| public: |
| /// Sububclass discriminator (for dyn_cast<> et al.) |
| enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind }; |
| |
| /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield. |
| struct GVFlags { |
| /// 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; |
| |
| /// Indicates the visibility. |
| unsigned Visibility : 2; |
| |
| /// 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; |
| |
| /// In the per-module summary, indicates that the global value is |
| /// linkonce_odr and global unnamed addr (so eligible for auto-hiding |
| /// via hidden visibility). In the combined summary, indicates that the |
| /// prevailing linkonce_odr copy can be auto-hidden via hidden visibility |
| /// when it is upgraded to weak_odr in the backend. This is legal when |
| /// all copies are eligible for auto-hiding (i.e. all copies were |
| /// linkonce_odr global unnamed addr. If any copy is not (e.g. it was |
| /// originally weak_odr, we cannot auto-hide the prevailing copy as it |
| /// means the symbol was externally visible. |
| unsigned CanAutoHide : 1; |
| |
| /// Convenience Constructors |
| explicit GVFlags(GlobalValue::LinkageTypes Linkage, |
| GlobalValue::VisibilityTypes Visibility, |
| bool NotEligibleToImport, bool Live, bool IsLocal, |
| bool CanAutoHide) |
| : Linkage(Linkage), Visibility(Visibility), |
| NotEligibleToImport(NotEligibleToImport), Live(Live), |
| DSOLocal(IsLocal), CanAutoHide(CanAutoHide) {} |
| }; |
| |
| 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; |
| |
| /// 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() const { 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() const { 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; } |
| |
| void setCanAutoHide(bool CanAutoHide) { Flags.CanAutoHide = CanAutoHide; } |
| |
| bool canAutoHide() const { return Flags.CanAutoHide; } |
| |
| GlobalValue::VisibilityTypes getVisibility() const { |
| return (GlobalValue::VisibilityTypes)Flags.Visibility; |
| } |
| void setVisibility(GlobalValue::VisibilityTypes Vis) { |
| Flags.Visibility = (unsigned)Vis; |
| } |
| |
| /// 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; |
| }; |
| |
| /// Alias summary information. |
| class AliasSummary : public GlobalValueSummary { |
| ValueInfo AliaseeValueInfo; |
| |
| /// This is the Aliasee in the same module as alias (could get from VI, trades |
| /// memory for time). Note that this pointer may be null (and the value info |
| /// empty) when we have a distributed index where the alias is being imported |
| /// (as a copy of the aliasee), but the aliasee is not. |
| GlobalValueSummary *AliaseeSummary; |
| |
| public: |
| AliasSummary(GVFlags Flags) |
| : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}), |
| AliaseeSummary(nullptr) {} |
| |
| /// Check if this is an alias summary. |
| static bool classof(const GlobalValueSummary *GVS) { |
| return GVS->getSummaryKind() == AliasKind; |
| } |
| |
| void setAliasee(ValueInfo &AliaseeVI, GlobalValueSummary *Aliasee) { |
| AliaseeValueInfo = AliaseeVI; |
| AliaseeSummary = Aliasee; |
| } |
| |
| bool hasAliasee() const { |
| assert(!!AliaseeSummary == (AliaseeValueInfo && |
| !AliaseeValueInfo.getSummaryList().empty()) && |
| "Expect to have both aliasee summary and summary list or neither"); |
| return !!AliaseeSummary; |
| } |
| |
| const GlobalValueSummary &getAliasee() const { |
| assert(AliaseeSummary && "Unexpected missing aliasee summary"); |
| return *AliaseeSummary; |
| } |
| |
| GlobalValueSummary &getAliasee() { |
| return const_cast<GlobalValueSummary &>( |
| static_cast<const AliasSummary *>(this)->getAliasee()); |
| } |
| ValueInfo getAliaseeVI() const { |
| assert(AliaseeValueInfo && "Unexpected missing aliasee"); |
| return AliaseeValueInfo; |
| } |
| GlobalValue::GUID getAliaseeGUID() const { |
| assert(AliaseeValueInfo && "Unexpected missing aliasee"); |
| return AliaseeValueInfo.getGUID(); |
| } |
| }; |
| |
| 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; |
| } |
| |
| /// 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>; |
| |
| /// Types for -force-summary-edges-cold debugging option. |
| enum ForceSummaryHotnessType : unsigned { |
| FSHT_None, |
| FSHT_AllNonCritical, |
| FSHT_All |
| }; |
| |
| /// 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; |
| }; |
| |
| /// 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 referenced by something other than 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; |
| }; |
| |
| /// Flags specific to function summaries. |
| struct FFlags { |
| // Function attribute flags. Used to track if a function accesses memory, |
| // recurses or aliases. |
| unsigned ReadNone : 1; |
| unsigned ReadOnly : 1; |
| unsigned NoRecurse : 1; |
| unsigned ReturnDoesNotAlias : 1; |
| |
| // Indicate if the global value cannot be inlined. |
| unsigned NoInline : 1; |
| // Indicate if function should be always inlined. |
| unsigned AlwaysInline : 1; |
| // Indicate if function never raises an exception. Can be modified during |
| // thinlink function attribute propagation |
| unsigned NoUnwind : 1; |
| // Indicate if function contains instructions that mayThrow |
| unsigned MayThrow : 1; |
| |
| // If there are calls to unknown targets (e.g. indirect) |
| unsigned HasUnknownCall : 1; |
| |
| // Indicate if a function must be an unreachable function. |
| // |
| // This bit is sufficient but not necessary; |
| // if this bit is on, the function must be regarded as unreachable; |
| // if this bit is off, the function might be reachable or unreachable. |
| unsigned MustBeUnreachable : 1; |
| |
| FFlags &operator&=(const FFlags &RHS) { |
| this->ReadNone &= RHS.ReadNone; |
| this->ReadOnly &= RHS.ReadOnly; |
| this->NoRecurse &= RHS.NoRecurse; |
| this->ReturnDoesNotAlias &= RHS.ReturnDoesNotAlias; |
| this->NoInline &= RHS.NoInline; |
| this->AlwaysInline &= RHS.AlwaysInline; |
| this->NoUnwind &= RHS.NoUnwind; |
| this->MayThrow &= RHS.MayThrow; |
| this->HasUnknownCall &= RHS.HasUnknownCall; |
| this->MustBeUnreachable &= RHS.MustBeUnreachable; |
| return *this; |
| } |
| |
| bool anyFlagSet() { |
| return this->ReadNone | this->ReadOnly | this->NoRecurse | |
| this->ReturnDoesNotAlias | this->NoInline | this->AlwaysInline | |
| this->NoUnwind | this->MayThrow | this->HasUnknownCall | |
| this->MustBeUnreachable; |
| } |
| |
| operator std::string() { |
| std::string Output; |
| raw_string_ostream OS(Output); |
| OS << "funcFlags: ("; |
| OS << "readNone: " << this->ReadNone; |
| OS << ", readOnly: " << this->ReadOnly; |
| OS << ", noRecurse: " << this->NoRecurse; |
| OS << ", returnDoesNotAlias: " << this->ReturnDoesNotAlias; |
| OS << ", noInline: " << this->NoInline; |
| OS << ", alwaysInline: " << this->AlwaysInline; |
| OS << ", noUnwind: " << this->NoUnwind; |
| OS << ", mayThrow: " << this->MayThrow; |
| OS << ", hasUnknownCall: " << this->HasUnknownCall; |
| OS << ", mustBeUnreachable: " << this->MustBeUnreachable; |
| OS << ")"; |
| return OS.str(); |
| } |
| }; |
| |
| /// Describes the uses of a parameter by the function. |
| struct ParamAccess { |
| static constexpr uint32_t RangeWidth = 64; |
| |
| /// Describes the use of a value in a call instruction, specifying the |
| /// call's target, the value's parameter number, and the possible range of |
| /// offsets from the beginning of the value that are passed. |
| struct Call { |
| uint64_t ParamNo = 0; |
| ValueInfo Callee; |
| ConstantRange Offsets{/*BitWidth=*/RangeWidth, /*isFullSet=*/true}; |
| |
| Call() = default; |
| Call(uint64_t ParamNo, ValueInfo Callee, const ConstantRange &Offsets) |
| : ParamNo(ParamNo), Callee(Callee), Offsets(Offsets) {} |
| }; |
| |
| uint64_t ParamNo = 0; |
| /// The range contains byte offsets from the parameter pointer which |
| /// accessed by the function. In the per-module summary, it only includes |
| /// accesses made by the function instructions. In the combined summary, it |
| /// also includes accesses by nested function calls. |
| ConstantRange Use{/*BitWidth=*/RangeWidth, /*isFullSet=*/true}; |
| /// In the per-module summary, it summarizes the byte offset applied to each |
| /// pointer parameter before passing to each corresponding callee. |
| /// In the combined summary, it's empty and information is propagated by |
| /// inter-procedural analysis and applied to the Use field. |
| std::vector<Call> Calls; |
| |
| ParamAccess() = default; |
| ParamAccess(uint64_t ParamNo, const ConstantRange &Use) |
| : ParamNo(ParamNo), Use(Use) {} |
| }; |
| |
| /// 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, |
| GlobalValue::DefaultVisibility, |
| /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false, |
| /*CanAutoHide=*/false), |
| /*NumInsts=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0, |
| 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>(), |
| std::vector<FunctionSummary::ParamAccess>()); |
| } |
| |
| /// 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 summary specific flags. |
| FFlags FunFlags; |
| |
| /// The synthesized entry count of the function. |
| /// This is only populated during ThinLink phase and remains unused while |
| /// generating per-module summaries. |
| uint64_t EntryCount = 0; |
| |
| /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function. |
| std::vector<EdgeTy> CallGraphEdgeList; |
| |
| std::unique_ptr<TypeIdInfo> TIdInfo; |
| |
| /// Uses for every parameter to this function. |
| using ParamAccessesTy = std::vector<ParamAccess>; |
| std::unique_ptr<ParamAccessesTy> ParamAccesses; |
| |
| public: |
| FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags, |
| uint64_t EntryCount, 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, |
| std::vector<ParamAccess> Params) |
| : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)), |
| InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount), |
| CallGraphEdgeList(std::move(CGEdges)) { |
| if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() || |
| !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() || |
| !TypeCheckedLoadConstVCalls.empty()) |
| TIdInfo = std::make_unique<TypeIdInfo>( |
| TypeIdInfo{std::move(TypeTests), std::move(TypeTestAssumeVCalls), |
| std::move(TypeCheckedLoadVCalls), |
| std::move(TypeTestAssumeConstVCalls), |
| std::move(TypeCheckedLoadConstVCalls)}); |
| if (!Params.empty()) |
| ParamAccesses = std::make_unique<ParamAccessesTy>(std::move(Params)); |
| } |
| // Gets the number of readonly and writeonly refs in RefEdgeList |
| std::pair<unsigned, unsigned> specialRefCounts() const; |
| |
| /// Check if this is a function summary. |
| static bool classof(const GlobalValueSummary *GVS) { |
| return GVS->getSummaryKind() == FunctionKind; |
| } |
| |
| /// Get function summary flags. |
| FFlags fflags() const { return FunFlags; } |
| |
| void setNoRecurse() { FunFlags.NoRecurse = true; } |
| |
| void setNoUnwind() { FunFlags.NoUnwind = true; } |
| |
| /// Get the instruction count recorded for this function. |
| unsigned instCount() const { return InstCount; } |
| |
| /// Get the synthetic entry count for this function. |
| uint64_t entryCount() const { return EntryCount; } |
| |
| /// Set the synthetic entry count for this function. |
| void setEntryCount(uint64_t EC) { EntryCount = EC; } |
| |
| /// Return the list of <CalleeValueInfo, CalleeInfo> pairs. |
| ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; } |
| |
| std::vector<EdgeTy> &mutableCalls() { return CallGraphEdgeList; } |
| |
| void addCall(EdgeTy E) { CallGraphEdgeList.push_back(E); } |
| |
| /// 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 {}; |
| } |
| |
| /// Returns the list of known uses of pointer parameters. |
| ArrayRef<ParamAccess> paramAccesses() const { |
| if (ParamAccesses) |
| return *ParamAccesses; |
| return {}; |
| } |
| |
| /// Sets the list of known uses of pointer parameters. |
| void setParamAccesses(std::vector<ParamAccess> NewParams) { |
| if (NewParams.empty()) |
| ParamAccesses.reset(); |
| else if (ParamAccesses) |
| *ParamAccesses = std::move(NewParams); |
| else |
| ParamAccesses = std::make_unique<ParamAccessesTy>(std::move(NewParams)); |
| } |
| |
| /// 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 = std::make_unique<TypeIdInfo>(); |
| TIdInfo->TypeTests.push_back(Guid); |
| } |
| |
| const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); }; |
| |
| 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; |
| } |
| }; |
| |
| /// The ValueInfo and offset for a function within a vtable definition |
| /// initializer array. |
| struct VirtFuncOffset { |
| VirtFuncOffset(ValueInfo VI, uint64_t Offset) |
| : FuncVI(VI), VTableOffset(Offset) {} |
| |
| ValueInfo FuncVI; |
| uint64_t VTableOffset; |
| }; |
| /// List of functions referenced by a particular vtable definition. |
| using VTableFuncList = std::vector<VirtFuncOffset>; |
| |
| /// Global variable summary information to aid decisions and |
| /// implementation of importing. |
| /// |
| /// Global variable summary has two extra flag, telling if it is |
| /// readonly or writeonly. Both readonly and writeonly variables |
| /// can be optimized in the backed: readonly variables can be |
| /// const-folded, while writeonly vars can be completely eliminated |
| /// together with corresponding stores. We let both things happen |
| /// by means of internalizing such variables after ThinLTO import. |
| class GlobalVarSummary : public GlobalValueSummary { |
| private: |
| /// For vtable definitions this holds the list of functions and |
| /// their corresponding offsets within the initializer array. |
| std::unique_ptr<VTableFuncList> VTableFuncs; |
| |
| public: |
| struct GVarFlags { |
| GVarFlags(bool ReadOnly, bool WriteOnly, bool Constant, |
| GlobalObject::VCallVisibility Vis) |
| : MaybeReadOnly(ReadOnly), MaybeWriteOnly(WriteOnly), |
| Constant(Constant), VCallVisibility(Vis) {} |
| |
| // If true indicates that this global variable might be accessed |
| // purely by non-volatile load instructions. This in turn means |
| // it can be internalized in source and destination modules during |
| // thin LTO import because it neither modified nor its address |
| // is taken. |
| unsigned MaybeReadOnly : 1; |
| // If true indicates that variable is possibly only written to, so |
| // its value isn't loaded and its address isn't taken anywhere. |
| // False, when 'Constant' attribute is set. |
| unsigned MaybeWriteOnly : 1; |
| // Indicates that value is a compile-time constant. Global variable |
| // can be 'Constant' while not being 'ReadOnly' on several occasions: |
| // - it is volatile, (e.g mapped device address) |
| // - its address is taken, meaning that unlike 'ReadOnly' vars we can't |
| // internalize it. |
| // Constant variables are always imported thus giving compiler an |
| // opportunity to make some extra optimizations. Readonly constants |
| // are also internalized. |
| unsigned Constant : 1; |
| // Set from metadata on vtable definitions during the module summary |
| // analysis. |
| unsigned VCallVisibility : 2; |
| } VarFlags; |
| |
| GlobalVarSummary(GVFlags Flags, GVarFlags VarFlags, |
| std::vector<ValueInfo> Refs) |
| : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)), |
| VarFlags(VarFlags) {} |
| |
| /// Check if this is a global variable summary. |
| static bool classof(const GlobalValueSummary *GVS) { |
| return GVS->getSummaryKind() == GlobalVarKind; |
| } |
| |
| GVarFlags varflags() const { return VarFlags; } |
| void setReadOnly(bool RO) { VarFlags.MaybeReadOnly = RO; } |
| void setWriteOnly(bool WO) { VarFlags.MaybeWriteOnly = WO; } |
| bool maybeReadOnly() const { return VarFlags.MaybeReadOnly; } |
| bool maybeWriteOnly() const { return VarFlags.MaybeWriteOnly; } |
| bool isConstant() const { return VarFlags.Constant; } |
| void setVCallVisibility(GlobalObject::VCallVisibility Vis) { |
| VarFlags.VCallVisibility = Vis; |
| } |
| GlobalObject::VCallVisibility getVCallVisibility() const { |
| return (GlobalObject::VCallVisibility)VarFlags.VCallVisibility; |
| } |
| |
| void setVTableFuncs(VTableFuncList Funcs) { |
| assert(!VTableFuncs); |
| VTableFuncs = std::make_unique<VTableFuncList>(std::move(Funcs)); |
| } |
| |
| ArrayRef<VirtFuncOffset> vTableFuncs() const { |
| if (VTableFuncs) |
| return *VTableFuncs; |
| return {}; |
| } |
| }; |
| |
| 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") |
| Unknown, ///< Unknown (analysis not performed, don't lower) |
| } TheKind = Unknown; |
| |
| /// 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 *>; |
| |
| /// Map of a type GUID to type id string and summary (multimap used |
| /// in case of GUID conflicts). |
| using TypeIdSummaryMapTy = |
| std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>; |
| |
| /// The following data structures summarize type metadata information. |
| /// For type metadata overview see https://llvm.org/docs/TypeMetadata.html. |
| /// Each type metadata includes both the type identifier and the offset of |
| /// the address point of the type (the address held by objects of that type |
| /// which may not be the beginning of the virtual table). Vtable definitions |
| /// are decorated with type metadata for the types they are compatible with. |
| /// |
| /// Holds information about vtable definitions decorated with type metadata: |
| /// the vtable definition value and its address point offset in a type |
| /// identifier metadata it is decorated (compatible) with. |
| struct TypeIdOffsetVtableInfo { |
| TypeIdOffsetVtableInfo(uint64_t Offset, ValueInfo VI) |
| : AddressPointOffset(Offset), VTableVI(VI) {} |
| |
| uint64_t AddressPointOffset; |
| ValueInfo VTableVI; |
| }; |
| /// List of vtable definitions decorated by a particular type identifier, |
| /// and their corresponding offsets in that type identifier's metadata. |
| /// Note that each type identifier may be compatible with multiple vtables, due |
| /// to inheritance, which is why this is a vector. |
| using TypeIdCompatibleVtableInfo = std::vector<TypeIdOffsetVtableInfo>; |
| |
| /// 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 identifier GUIDs to type identifier and its summary |
| /// information. Produced by thin link. |
| TypeIdSummaryMapTy TypeIdMap; |
| |
| /// Mapping from type identifier to information about vtables decorated |
| /// with that type identifier's metadata. Produced by per module summary |
| /// analysis and consumed by thin link. For more information, see description |
| /// above where TypeIdCompatibleVtableInfo is defined. |
| std::map<std::string, TypeIdCompatibleVtableInfo, std::less<>> |
| TypeIdCompatibleVtableMap; |
| |
| /// 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 summary-based attribute propagation has run and |
| /// GVarFlags::MaybeReadonly / GVarFlags::MaybeWriteonly are really |
| /// read/write only. |
| bool WithAttributePropagation = false; |
| |
| /// Indicates that summary-based DSOLocal propagation has run and the flag in |
| /// every summary of a GV is synchronized. |
| bool WithDSOLocalPropagation = false; |
| |
| /// Indicates that summary-based synthetic entry count propagation has run |
| bool HasSyntheticEntryCounts = 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, or parsing along with |
| /// the IR from assembly. The value of 'false' means we're reading summary |
| /// from BC or YAML source. Affects the type of value stored in NameOrGV |
| /// union. |
| bool HaveGVs; |
| |
| // True if the index was created for a module compiled with -fsplit-lto-unit. |
| bool EnableSplitLTOUnit; |
| |
| // True if some of the modules were compiled with -fsplit-lto-unit and |
| // some were not. Set when the combined index is created during the thin link. |
| bool PartiallySplitLTOUnits = false; |
| |
| /// True if some of the FunctionSummary contains a ParamAccess. |
| bool HasParamAccess = false; |
| |
| std::set<std::string> CfiFunctionDefs; |
| std::set<std::string> CfiFunctionDecls; |
| |
| // Used in cases where we want to record the name of a global, but |
| // don't have the string owned elsewhere (e.g. the Strtab on a module). |
| StringSaver Saver; |
| BumpPtrAllocator Alloc; |
| |
| // The total number of basic blocks in the module in the per-module summary or |
| // the total number of basic blocks in the LTO unit in the combined index. |
| uint64_t BlockCount; |
| |
| // YAML I/O support. |
| friend yaml::MappingTraits<ModuleSummaryIndex>; |
| |
| GlobalValueSummaryMapTy::value_type * |
| getOrInsertValuePtr(GlobalValue::GUID GUID) { |
| return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs)) |
| .first; |
| } |
| |
| public: |
| // See HaveGVs variable comment. |
| ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false) |
| : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc), |
| BlockCount(0) {} |
| |
| // Current version for the module summary in bitcode files. |
| // The BitcodeSummaryVersion should be bumped whenever we introduce changes |
| // in the way some record are interpreted, like flags for instance. |
| // Note that incrementing this may require changes in both BitcodeReader.cpp |
| // and BitcodeWriter.cpp. |
| static constexpr uint64_t BitcodeSummaryVersion = 9; |
| |
| // Regular LTO module name for ASM writer |
| static constexpr const char *getRegularLTOModuleName() { |
| return "[Regular LTO]"; |
| } |
| |
| bool haveGVs() const { return HaveGVs; } |
| |
| uint64_t getFlags() const; |
| void setFlags(uint64_t Flags); |
| |
| uint64_t getBlockCount() const { return BlockCount; } |
| void addBlockCount(uint64_t C) { BlockCount += C; } |
| void setBlockCount(uint64_t C) { BlockCount = C; } |
| |
| 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(HaveGVs, &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 withAttributePropagation() const { return WithAttributePropagation; } |
| void setWithAttributePropagation() { |
| WithAttributePropagation = true; |
| } |
| |
| bool withDSOLocalPropagation() const { return WithDSOLocalPropagation; } |
| void setWithDSOLocalPropagation() { WithDSOLocalPropagation = true; } |
| |
| bool isReadOnly(const GlobalVarSummary *GVS) const { |
| return WithAttributePropagation && GVS->maybeReadOnly(); |
| } |
| bool isWriteOnly(const GlobalVarSummary *GVS) const { |
| return WithAttributePropagation && GVS->maybeWriteOnly(); |
| } |
| |
| bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; } |
| void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; } |
| |
| bool skipModuleByDistributedBackend() const { |
| return SkipModuleByDistributedBackend; |
| } |
| void setSkipModuleByDistributedBackend() { |
| SkipModuleByDistributedBackend = true; |
| } |
| |
| bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; } |
| void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; } |
| |
| bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; } |
| void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; } |
| |
| bool hasParamAccess() const { return HasParamAccess; } |
| |
| bool isGlobalValueLive(const GlobalValueSummary *GVS) const { |
| return !WithGlobalValueDeadStripping || GVS->isLive(); |
| } |
| bool isGUIDLive(GlobalValue::GUID GUID) const; |
| |
| /// Return a ValueInfo for the index value_type (convenient when iterating |
| /// index). |
| ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const { |
| return ValueInfo(HaveGVs, &R); |
| } |
| |
| /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo(). |
| ValueInfo getValueInfo(GlobalValue::GUID GUID) const { |
| auto I = GlobalValueMap.find(GUID); |
| return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I); |
| } |
| |
| /// Return a ValueInfo for \p GUID. |
| ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) { |
| return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID)); |
| } |
| |
| // Save a string in the Index. Use before passing Name to |
| // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the |
| // module's Strtab). |
| StringRef saveString(StringRef String) { return Saver.save(String); } |
| |
| /// Return a ValueInfo for \p GUID setting value \p Name. |
| ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) { |
| assert(!HaveGVs); |
| auto VP = getOrInsertValuePtr(GUID); |
| VP->second.U.Name = Name; |
| return ValueInfo(HaveGVs, VP); |
| } |
| |
| /// Return a ValueInfo for \p GV and mark it as belonging to GV. |
| ValueInfo getOrInsertValueInfo(const GlobalValue *GV) { |
| assert(HaveGVs); |
| auto VP = getOrInsertValuePtr(GV->getGUID()); |
| VP->second.U.GV = GV; |
| return ValueInfo(HaveGVs, 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. |
| void addGlobalValueSummary(const GlobalValue &GV, |
| std::unique_ptr<GlobalValueSummary> Summary) { |
| addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary)); |
| } |
| |
| /// 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) { |
| if (const FunctionSummary *FS = dyn_cast<FunctionSummary>(Summary.get())) |
| HasParamAccess |= !FS->paramAccesses().empty(); |
| 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 ValueInfo \p VI in module \p ModuleId, or nullptr if |
| /// not found. |
| GlobalValueSummary *findSummaryInModule(ValueInfo VI, StringRef ModuleId) const { |
| auto SummaryList = VI.getSummaryList(); |
| auto Summary = |
| llvm::find_if(SummaryList, |
| [&](const std::unique_ptr<GlobalValueSummary> &Summary) { |
| return Summary->modulePath() == ModuleId; |
| }); |
| if (Summary == SummaryList.end()) |
| return nullptr; |
| return Summary->get(); |
| } |
| |
| /// 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 |
| return findSummaryInModule(CalleeInfo, ModuleId); |
| } |
| |
| /// 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(GV.getGUID(), 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 std::string(NewName.str()); |
| } |
| |
| /// Helper to obtain the unpromoted name for a global value (or the original |
| /// name if not promoted). Split off the rightmost ".llvm.${hash}" suffix, |
| /// because it is possible in certain clients (not clang at the moment) for |
| /// two rounds of ThinLTO optimization and therefore promotion to occur. |
| static StringRef getOriginalNameBeforePromote(StringRef Name) { |
| std::pair<StringRef, StringRef> Pair = Name.rsplit(".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; |
| } |
| |
| /// Return module entry for module with the given \p ModPath. |
| ModuleInfo *getModule(StringRef ModPath) { |
| auto It = ModulePathStringTable.find(ModPath); |
| assert(It != ModulePathStringTable.end() && "Module not registered"); |
| return &*It; |
| } |
| |
| /// 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 TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; } |
| |
| /// Return an existing or new TypeIdSummary entry for \p TypeId. |
| /// This accessor can mutate the map and therefore should not be used in |
| /// the ThinLTO backends. |
| TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) { |
| auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId)); |
| for (auto It = TidIter.first; It != TidIter.second; ++It) |
| if (It->second.first == TypeId) |
| return It->second.second; |
| auto It = TypeIdMap.insert( |
| {GlobalValue::getGUID(TypeId), {std::string(TypeId), TypeIdSummary()}}); |
| return It->second.second; |
| } |
| |
| /// 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 TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId)); |
| for (auto It = TidIter.first; It != TidIter.second; ++It) |
| if (It->second.first == TypeId) |
| return &It->second.second; |
| return nullptr; |
| } |
| |
| TypeIdSummary *getTypeIdSummary(StringRef TypeId) { |
| return const_cast<TypeIdSummary *>( |
| static_cast<const ModuleSummaryIndex *>(this)->getTypeIdSummary( |
| TypeId)); |
| } |
| |
| const auto &typeIdCompatibleVtableMap() const { |
| return TypeIdCompatibleVtableMap; |
| } |
| |
| /// Return an existing or new TypeIdCompatibleVtableMap entry for \p TypeId. |
| /// This accessor can mutate the map and therefore should not be used in |
| /// the ThinLTO backends. |
| TypeIdCompatibleVtableInfo & |
| getOrInsertTypeIdCompatibleVtableSummary(StringRef TypeId) { |
| return TypeIdCompatibleVtableMap[std::string(TypeId)]; |
| } |
| |
| /// For the given \p TypeId, this returns the TypeIdCompatibleVtableMap |
| /// entry if present in the summary map. This may be used when importing. |
| Optional<TypeIdCompatibleVtableInfo> |
| getTypeIdCompatibleVtableSummary(StringRef TypeId) const { |
| auto I = TypeIdCompatibleVtableMap.find(TypeId); |
| if (I == TypeIdCompatibleVtableMap.end()) |
| return None; |
| return I->second; |
| } |
| |
| /// Collect for the given module the list of functions it defines |
| /// (GUID -> Summary). |
| void collectDefinedFunctionsForModule(StringRef ModulePath, |
| GVSummaryMapTy &GVSummaryMap) const; |
| |
| /// Collect for each module the list of Summaries it defines (GUID -> |
| /// Summary). |
| template <class Map> |
| void |
| collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const { |
| for (auto &GlobalList : *this) { |
| auto GUID = GlobalList.first; |
| for (auto &Summary : GlobalList.second.SummaryList) { |
| ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get(); |
| } |
| } |
| } |
| |
| /// Print to an output stream. |
| void print(raw_ostream &OS, bool IsForDebug = false) const; |
| |
| /// Dump to stderr (for debugging). |
| void dump() const; |
| |
| /// Export summary to dot file for GraphViz. |
| void |
| exportToDot(raw_ostream &OS, |
| const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) const; |
| |
| /// Print out strongly connected components for debugging. |
| void dumpSCCs(raw_ostream &OS); |
| |
| /// Do the access attribute and DSOLocal propagation in combined index. |
| void propagateAttributes(const DenseSet<GlobalValue::GUID> &PreservedSymbols); |
| |
| /// Checks if we can import global variable from another module. |
| bool canImportGlobalVar(GlobalValueSummary *S, bool AnalyzeRefs) const; |
| }; |
| |
| /// GraphTraits definition to build SCC for the index |
| template <> struct GraphTraits<ValueInfo> { |
| typedef ValueInfo NodeRef; |
| using EdgeRef = FunctionSummary::EdgeTy &; |
| |
| static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) { |
| return P.first; |
| } |
| using ChildIteratorType = |
| mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator, |
| decltype(&valueInfoFromEdge)>; |
| |
| using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator; |
| |
| 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); |
| } |
| |
| static ChildEdgeIteratorType child_edge_begin(NodeRef N) { |
| if (!N.getSummaryList().size()) // handle external function |
| return FunctionSummary::ExternalNode.CallGraphEdgeList.begin(); |
| |
| FunctionSummary *F = |
| cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); |
| return F->CallGraphEdgeList.begin(); |
| } |
| |
| static ChildEdgeIteratorType child_edge_end(NodeRef N) { |
| if (!N.getSummaryList().size()) // handle external function |
| return FunctionSummary::ExternalNode.CallGraphEdgeList.end(); |
| |
| FunctionSummary *F = |
| cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); |
| return F->CallGraphEdgeList.end(); |
| } |
| |
| static NodeRef edge_dest(EdgeRef E) { return E.first; } |
| }; |
| |
| template <> |
| struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> { |
| static NodeRef getEntryNode(ModuleSummaryIndex *I) { |
| std::unique_ptr<GlobalValueSummary> Root = |
| std::make_unique<FunctionSummary>(I->calculateCallGraphRoot()); |
| GlobalValueSummaryInfo G(I->haveGVs()); |
| G.SummaryList.push_back(std::move(Root)); |
| static auto P = |
| GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G)); |
| return ValueInfo(I->haveGVs(), &P); |
| } |
| }; |
| } // end namespace llvm |
| |
| #endif // LLVM_IR_MODULESUMMARYINDEX_H |