From f551fb96c7fbe38628f049bfe0e48a6943ee341f Mon Sep 17 00:00:00 2001 From: Jeremy Morse Date: Fri, 9 Jul 2021 15:32:30 +0100 Subject: [PATCH] [Debug-info][InstrRef] Avoid an unnecessary map ordering We keep a record of substitutions between debug value numbers post-isel, however we never actually look them up until the end of compilation. As a result, there's nothing gained by the collection being a std::map. This patch downgrades it to being a vector, that's then sorted at the end of compilation in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D105029 --- llvm/include/llvm/CodeGen/MachineFunction.h | 39 ++++++++++++++-------- .../CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp | 37 +++++++++++++++----- llvm/lib/CodeGen/MIRPrinter.cpp | 10 +++--- llvm/lib/CodeGen/MachineFunction.cpp | 4 +-- 4 files changed, 61 insertions(+), 29 deletions(-) diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h index f7e9421..786fe90 100644 --- a/llvm/include/llvm/CodeGen/MachineFunction.h +++ b/llvm/include/llvm/CodeGen/MachineFunction.h @@ -451,24 +451,37 @@ public: /// Pair of instruction number and operand number. using DebugInstrOperandPair = std::pair; - /// Replacement definition for a debug instruction reference. Made up of an - /// instruction / operand pair, and a qualifying subregister indicating what - /// bits in the operand make up the substitution. For example, a debug user + /// Replacement definition for a debug instruction reference. Made up of a + /// source instruction / operand pair, destination pair, and a qualifying + /// subregister indicating what bits in the operand make up the substitution. + // For example, a debug user /// of %1: - /// %0:gr32 = someinst, debug-instr-number 2 - /// %1:gr16 = %0.some_16_bit_subreg - /// Would receive the substitution {{2, 0}, $subreg}, where $subreg is the - /// subregister number for some_16_bit_subreg. - struct DebugSubstitution { + /// %0:gr32 = someinst, debug-instr-number 1 + /// %1:gr16 = %0.some_16_bit_subreg, debug-instr-number 2 + /// Would receive the substitution {{2, 0}, {1, 0}, $subreg}, where $subreg is + /// the subregister number for some_16_bit_subreg. + class DebugSubstitution { + public: + DebugInstrOperandPair Src; ///< Source instruction / operand pair. DebugInstrOperandPair Dest; ///< Replacement instruction / operand pair. unsigned Subreg; ///< Qualifier for which part of Dest is read. + + DebugSubstitution(const DebugInstrOperandPair &Src, + const DebugInstrOperandPair &Dest, unsigned Subreg) + : Src(Src), Dest(Dest), Subreg(Subreg) {} + + /// Order only by source instruction / operand pair: there should never + /// be duplicate entries for the same source in any collection. + bool operator<(const DebugSubstitution &Other) const { + return Src < Other.Src; + } }; - /// Substitution map: from one pair identifying a value, - /// to a DebugSubstitution identifying another. Used to record changes in - /// where a value is defined, so that debug variable locations can find it - /// later. - std::map DebugValueSubstitutions; + /// Debug value substitutions: a collection of DebugSubstitution objects, + /// recording changes in where a value is defined. For example, when one + /// instruction is substituted for another. Keeping a record allows recovery + /// of variable locations after compilation finishes. + SmallVector DebugValueSubstitutions; /// Location of a PHI instruction that is also a debug-info variable value, /// for the duration of register allocation. Loaded by the PHI-elimination diff --git a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp index b8fa028..af760c2 100644 --- a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp +++ b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp @@ -1827,16 +1827,22 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI, // Various optimizations may have happened to the value during codegen, // recorded in the value substitution table. Apply any substitutions to - // the instruction / operand number in this DBG_INSTR_REF. - auto Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo)); - // Collect any subregister extractions performed during optimization. + // the instruction / operand number in this DBG_INSTR_REF, and collect + // any subregister extractions performed during optimization. + + // Create dummy substitution with Src set, for lookup. + auto SoughtSub = + MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0); + SmallVector SeenSubregs; - while (Sub != MF.DebugValueSubstitutions.end()) { - std::tie(InstNo, OpNo) = Sub->second.Dest; - unsigned Subreg = Sub->second.Subreg; - if (Subreg) + auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); + while (LowerBoundIt != MF.DebugValueSubstitutions.end() && + LowerBoundIt->Src == SoughtSub.Src) { + std::tie(InstNo, OpNo) = LowerBoundIt->Dest; + SoughtSub.Src = LowerBoundIt->Dest; + if (unsigned Subreg = LowerBoundIt->Subreg) SeenSubregs.push_back(Subreg); - Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo)); + LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); } // Default machine value number is -- if no instruction defines @@ -3542,6 +3548,21 @@ void InstrRefBasedLDV::initialSetup(MachineFunction &MF) { BBNumToRPO[MBB->getNumber()] = RPONumber; ++RPONumber; } + + // Order value substitutions by their "source" operand pair, for quick lookup. + llvm::sort(MF.DebugValueSubstitutions); + +#ifdef EXPENSIVE_CHECKS + // As an expensive check, test whether there are any duplicate substitution + // sources in the collection. + if (MF.DebugValueSubstitutions.size() > 2) { + for (auto It = MF.DebugValueSubstitutions.begin(); + It != std::prev(MF.DebugValueSubstitutions.end()); ++It) { + assert(It->Src != std::next(It)->Src && "Duplicate variable location " + "substitution seen"); + } + } +#endif } /// Calculate the liveness information for the given machine function and diff --git a/llvm/lib/CodeGen/MIRPrinter.cpp b/llvm/lib/CodeGen/MIRPrinter.cpp index 0c8da19..2a78bb6 100644 --- a/llvm/lib/CodeGen/MIRPrinter.cpp +++ b/llvm/lib/CodeGen/MIRPrinter.cpp @@ -225,12 +225,12 @@ void MIRPrinter::print(const MachineFunction &MF) { convertStackObjects(YamlMF, MF, MST); convertCallSiteObjects(YamlMF, MF, MST); for (const auto &Sub : MF.DebugValueSubstitutions) { - auto &SubSrc = Sub.first; - const MachineFunction::DebugSubstitution &SubDest = Sub.second; + const auto &SubSrc = Sub.Src; + const auto &SubDest = Sub.Dest; YamlMF.DebugValueSubstitutions.push_back({SubSrc.first, SubSrc.second, - SubDest.Dest.first, - SubDest.Dest.second, - SubDest.Subreg}); + SubDest.first, + SubDest.second, + Sub.Subreg}); } if (const auto *ConstantPool = MF.getConstantPool()) convert(YamlMF, *ConstantPool); diff --git a/llvm/lib/CodeGen/MachineFunction.cpp b/llvm/lib/CodeGen/MachineFunction.cpp index 7cb7d089..d26f581 100644 --- a/llvm/lib/CodeGen/MachineFunction.cpp +++ b/llvm/lib/CodeGen/MachineFunction.cpp @@ -973,9 +973,7 @@ void MachineFunction::makeDebugValueSubstitution(DebugInstrOperandPair A, unsigned Subreg) { // Catch any accidental self-loops. assert(A.first != B.first); - auto Result = DebugValueSubstitutions.insert({A, {B, Subreg}}); - (void)Result; - assert(Result.second && "Substitution for an already substituted value?"); + DebugValueSubstitutions.push_back({A, B, Subreg}); } void MachineFunction::substituteDebugValuesForInst(const MachineInstr &Old, -- 2.7.4