Index: llvm/lib/CodeGen/LiveDebugValues.cpp =================================================================== --- llvm/lib/CodeGen/LiveDebugValues.cpp +++ llvm/lib/CodeGen/LiveDebugValues.cpp @@ -113,6 +113,7 @@ using DefinedRegsSet = SmallSet; class LiveDebugValues : public MachineFunctionPass { + friend class VarSetAdapter; private: const TargetRegisterInfo *TRI; const TargetInstrInfo *TII; @@ -179,14 +180,19 @@ /// The value location. Stored separately to avoid repeatedly /// extracting it from MI. - union { + typedef union { uint64_t RegNo; SpillLoc SpillLocation; uint64_t Hash; int64_t Immediate; const ConstantFP *FPImm; const ConstantInt *CImm; - } Loc; + } LocData; + LocData Loc; + + // Define a type that uniquely identifies a "machine location", i.e., + // where the variable value is stored. + using MachineLocation = std::pair; VarLoc(const MachineInstr &MI, LexicalScopes &LS) : Var(MI.getDebugVariable(), MI.getDebugExpression(), @@ -395,6 +401,11 @@ } #endif + /// Extract a MachineLocation object from this VarLoc. + MachineLocation getMachineLocation() const { + return std::make_pair(Kind, Loc); + } + bool operator==(const VarLoc &Other) const { return Kind == Other.Kind && Var == Other.Var && Loc.Hash == Other.Loc.Hash && Expr == Other.Expr; @@ -406,10 +417,41 @@ std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr); } }; + friend struct llvm::DenseMapInfo; - using VarLocMap = UniqueVector; using VarLocSet = SparseBitVector<>; using VarLocInMBB = SmallDenseMap; + + /// Uniqueify VarLocs by giving them a variable location ID number. In + /// addition, index all locations by their machine location. Ocasionally + /// LiveDebugValues iterates over every variable location to find those + /// that match a specific machine location, which benefits from such an + /// index. + class VarLocMap { + /// Maintain a unique ID number for each VarLoc. + UniqueVector IdxToLoc; + /// A map from machine location to the set of VarLocIDs for that machine + /// location. + DenseMap LocToIdxs; + /// An empty set to provide when there are no locations in this map. + static VarLocSet EmptySet; + + public: + /// Lookup by ID number -> examine the UniqueVector. + const VarLoc &operator[](unsigned ID) const { return IdxToLoc[ID]; } + + /// Insert a new location and produce an ID number. Insert into the + /// machine-location index too. + unsigned insert(const VarLoc &Loc) { + unsigned ID = IdxToLoc.insert(Loc); + LocToIdxs[Loc.getMachineLocation()].set(ID); + return ID; + } + + /// Lookup the set of locations based on the given machine location. + const VarLocSet &getIDsForLocation(const VarLoc::MachineLocation &L); + }; + struct TransferDebugPair { MachineInstr *TransferInst; /// Instruction where this transfer occurs. unsigned LocationID; /// Location number for the transfer dest. @@ -581,8 +623,53 @@ bool runOnMachineFunction(MachineFunction &MF) override; }; +/// An adapter class that takes a VarLocSet (sparse bitvector) and pretends +/// it's a set, which can then be combined with std::inserter. This allows +/// us to store std::algorithm results into VarLocSets without keeping +/// intermediate results somewhere. +class VarSetAdapter { + using VarLocSet = LiveDebugValues::VarLocSet; VarLocSet &Set; + +public: + typedef unsigned *iterator; + typedef unsigned value_type; + + VarSetAdapter(VarLocSet &_Set) : Set(_Set) {} + + iterator insert(iterator it, unsigned ID) { + Set.set(ID); + return it; + } +}; + } // end anonymous namespace +// Hash map boilerplate for VarLoc::MachineLocation. +namespace llvm { + +template <> struct DenseMapInfo { + using VL = LiveDebugValues::VarLoc; + using Loc = VL::MachineLocation; + static inline Loc getEmptyKey() { + VL::LocData LD; + LD.Hash = 0; + return std::make_pair(VL::InvalidKind, LD); + } + static inline Loc getTombstoneKey() { + VL::LocData LD; + LD.Hash = 1; + return std::make_pair(VL::InvalidKind, LD); + } + static inline unsigned getHashValue(const Loc &L) { + return hash_combine(hash_value(L.first), hash_value(L.second.Hash)); + } + static inline bool isEqual(const Loc &A, const Loc &B) { + return A.first == B.first && A.second.Hash == B.second.Hash; + } +}; + +} // end namespace llvm + //===----------------------------------------------------------------------===// // Implementation //===----------------------------------------------------------------------===// @@ -591,6 +678,8 @@ char &llvm::LiveDebugValuesID = LiveDebugValues::ID; +LiveDebugValues::VarLocSet LiveDebugValues::VarLocMap::EmptySet; + INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis", false, false) @@ -606,6 +695,16 @@ MachineFunctionPass::getAnalysisUsage(AU); } +// Return reference to the set of variable locations based on the given +// machine location, or an empty set. +auto LiveDebugValues::VarLocMap::getIDsForLocation( + const VarLoc::MachineLocation &L) -> const VarLocSet & { + auto IDSetIter = LocToIdxs.find(L); + if (IDSetIter == LocToIdxs.end()) + return EmptySet; + return IDSetIter->second; +} + /// Erase a variable from the set of open ranges, and additionally erase any /// fragments that may overlap it. If the VarLoc is a buckup location, erase /// the variable from the EntryValuesBackupVars set, indicating we should stop @@ -939,11 +1038,28 @@ if (MO.isReg() && MO.isDef() && MO.getReg() && Register::isPhysicalRegister(MO.getReg()) && !(MI.isCall() && MO.getReg() == SP)) { - // Remove ranges of all aliased registers. - for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) - for (unsigned ID : OpenRanges.getVarLocs()) - if (VarLocIDs[ID].isDescribedByReg() == *RAI) - KillSet.set(ID); + // Remove ranges of all aliased registers. Rather than iterating over + // every single variable location for every possible register (/and/ + // subregister), query VarLocMaps machine-location index. Furthermore, + // use std::set_intersection to produce locations both live and based on + // the machine locations. + for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); + ++RAI) { + const VarLocSet &OpenLocs = OpenRanges.getVarLocs(); + + // Produce a register MachineLocation. + VarLoc::LocData LD; + LD.RegNo = *RAI; + VarLoc::MachineLocation ML = std::make_pair(VarLoc::RegisterKind, LD); + + // Query for the set of all locations based on that MachineLocation. + const VarLocSet &AllLocationLocs = VarLocIDs.getIDsForLocation(ML); + + VarSetAdapter AddToKill(KillSet); + std::set_intersection(OpenLocs.begin(), OpenLocs.end(), + AllLocationLocs.begin(), AllLocationLocs.end(), + std::inserter(AddToKill, nullptr)); + } } else if (MO.isRegMask()) { // Remove ranges of all clobbered registers. Register masks don't usually // list SP as preserved. While the debug info may be off for an