[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–480

I guess we need to update this comment as well.

480–484

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 {
+      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;
+  /// 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<DebugSubstitution, 8> 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,
   auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
   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));
-  // 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<unsigned, 4> 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 <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);
+
+#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
 /// 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());
   MachineModuleSlotTracker MST(&MF);
   MST.incorporateFunction(MF.getFunction());
   convert(MST, YamlMF.FrameInfo, MF.getFrameInfo());
   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);
   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)