[Debug-info][InstrRef] Avoid un-necessary ordering in debug value-substitution records

[jmorse]

Summary

As suggested by @djtodoro in https://reviews.llvm.org/D88891#2843425 , there's a std::map in MachineFunction that doesn't need to be ordered through most of compilation, only at the end. It can be replaced with a vector that gets ordered when needed, which is what this patch does.

NFCI, and only affects the experimental instruction-referencing work that's currently hidden behind a flag.

[djtodoro]

@jmorse Thanks!

llvm/include/llvm/CodeGen/MachineFunction.h

469

I guess this needs clang-format

479

I guess we need to update this comment as well.

483

Can we use SmallVector instead?

[jmorse]

Use SmallVector over std::vector, apply some clang-formatting and comment adjusting.

[jmorse]

Thanks for the review; I found at the last minute that the assertion I'd put in MachineFunction.h for detecting duplicate sources in substitutions wasn't going to work: it would also fire when doing lookups. Checking for duplicates needs to be done explicitly; and it's moderately expensive, so I've downgraded it to an EXPENSIVE_CHECK in InstrRefBasedLDV::initialSetup.

llvm/include/llvm/CodeGen/MachineFunction.h

public:
 
   /// Set value of DebugInstrNumberingCount field. Avoid using this unless
   /// you're deserializing this data.
   void setDebugInstrNumberingCount(unsigned Num);
 
   /// Pair of instruction number and operand number.
   using DebugInstrOperandPair = std::pair<unsigned, unsigned>;
 
-  /// 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 {
+      assert(Src != Other.Src && "Duplicate substitution seen?");
+      return Src < Other.Src;
+    }
   };
 
   /// Substitution map: from one <inst,operand> 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<DebugInstrOperandPair, DebugSubstitution> DebugValueSubstitutions;
+  std::vector<DebugSubstitution> 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
   /// pass, and emitted as DBG_PHI instructions during VirtRegRewriter, with
   /// maintenance applied by intermediate passes that edit registers (such as
   /// coalescing and the allocator passes).
   class DebugPHIRegallocPos {
   public:

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
   if (Scope == nullptr)
     return true; // Handled by doing nothing. This variable is never in scope.
 
   const MachineFunction &MF = *MI.getParent()->getParent();
 
   // 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));
-  while (Sub != MF.DebugValueSubstitutions.end()) {
-    InstNo = Sub->second.first;
-    OpNo = Sub->second.second;
-    Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
+  // Create dummy substitution with Src set, for lookup.
+  auto SoughtSub = MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
+  auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
+  while (LowerBoundIt != MF.DebugValueSubstitutions.end() && LowerBoundIt->Src == SoughtSub.Src) {
+    InstNo = LowerBoundIt->Dest.first;
+    OpNo = LowerBoundIt->Dest.second;
+    SoughtSub.Src = {InstNo, OpNo};
+    LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
   }
 
   // Default machine value number is <None> -- if no instruction defines
   // the corresponding value, it must have been optimized out.
   Optional<ValueIDNum> NewID = None;
 
   // Try to lookup the instruction number, and find the machine value number
   // that it defines. It could be an instruction, or a PHI.
void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   unsigned int RPONumber = 0;
   for (MachineBasicBlock *MBB : RPOT) {
     OrderToBB[RPONumber] = MBB;
     BBToOrder[MBB] = RPONumber;
     BBNumToRPO[MBB->getNumber()] = RPONumber;
     ++RPONumber;
   }
+
+  // Order value substitutions by their "source" operand pair, for quick lookup.
+  llvm::sort(MF.DebugValueSubstitutions);
 }
 
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
                                     TargetPassConfig *TPC) {
   // No subprogram means this function contains no debuginfo.
   if (!MF.getFunction().getSubprogram())

llvm/lib/CodeGen/MIRPrinter.cpp

void MIRPrinter::print(const MachineFunction &MF) {
 
   convert(YamlMF, MF.getRegInfo(), MF.getSubtarget().getRegisterInfo());
   ModuleSlotTracker MST(MF.getFunction().getParent());
   MST.incorporateFunction(MF.getFunction());
   convert(MST, YamlMF.FrameInfo, MF.getFrameInfo());
   convertStackObjects(YamlMF, MF, MST);
   convertCallSiteObjects(YamlMF, MF, MST);
   for (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);
   if (const auto *JumpTableInfo = MF.getJumpTableInfo())
     convert(MST, YamlMF.JumpTableInfo, *JumpTableInfo);
 
   const TargetMachine &TM = MF.getTarget();
   YamlMF.MachineFuncInfo =

llvm/lib/CodeGen/MachineFunction.cpp

void MachineFunction::setDebugInstrNumberingCount(unsigned Num) {
   DebugInstrNumberingCount = Num;
 }
 
 void MachineFunction::makeDebugValueSubstitution(DebugInstrOperandPair A,
                                                  DebugInstrOperandPair B,
                                                  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,
                                                    MachineInstr &New,
                                                    unsigned MaxOperand) {
   // If the Old instruction wasn't tracked at all, there is no work to do.
   unsigned OldInstrNum = Old.peekDebugInstrNum();
   if (!OldInstrNum)