[DebugInfo][InstrRef] Use a cache to avoid creating redundant DBG_PHIs

[jmorse]

Summary

In SelectionDAG, DBG_PHI instructions are created to "read" physreg values and give them an instruction number, when they can't be traced back to a defining instruction. The most common scenario is arguments to a function. Unfortunately, if you have 100 inlined methods, each of which has the same "this" pointer, then the 100 dbg.value instructions become 100 DBG_INSTR_REFs and 100 DBG_PHIs, where only one DBG_PHI would suffice.

This patch adds a vreg cache for MachineFunction::salvageCopySSA, if we've already traced a value back to the start of a block and create a DBG_PHI then it allows us to re-use the DBG_PHI, as well as reducing work.

I've added a test with an implicit check-not for DBG_PHIs, which I think is the best way of making sure they aren't over-created in the future, and deserves its own test file.

[Orlando]

Makes sense, LGTM. I've added two tiny suggestions inline but I don't mind if you leave the patch as it is.

llvm/include/llvm/CodeGen/MachineFunction.h

534

I think something like DbgPHICache might be clearer, but this is not a very strong opinion.

llvm/lib/CodeGen/MachineFunction.cpp

1042

Possibly worth adding assert(MI.isCopyLike())? Not a strong opinion.

[jmorse]

llvm/include/llvm/CodeGen/MachineFunction.h

534

Sounds good,

llvm/lib/CodeGen/MachineFunction.cpp

1042

IMHO no, there are assertions down both sides of the branch below that are effectively that assertion.

llvm/include/llvm/CodeGen/MachineFunction.h

public:
   /// while in SSA form. Copies do not actually define values -- they move them
   /// between registers. Labelling a COPY-like instruction with an instruction
   /// number is to be avoided as it makes value numbers non-unique later in
   /// compilation. This method follows the definition chain for any sequence of
   /// COPY-like instructions to find whatever non-COPY-like instruction defines
   /// the copied value; or for parameters, creates a DBG_PHI on entry.
   /// May insert instructions into the entry block!
   /// \p MI The copy-like instruction to salvage.
+  /// \p DbgPHICache A container to cache already-solved COPYs.
   /// \returns An instruction/operand pair identifying the defining value.
-  DebugInstrOperandPair salvageCopySSA(MachineInstr &MI);
+  DebugInstrOperandPair
+  salvageCopySSA(MachineInstr &MI,
+                 DenseMap<Register, DebugInstrOperandPair> &DbgPHICache);
+
+  DebugInstrOperandPair salvageCopySSAImpl(MachineInstr &MI);
 
   /// Finalise any partially emitted debug instructions. These are DBG_INSTR_REF
   /// instructions where we only knew the vreg of the value they use, not the
   /// instruction that defines that vreg. Once isel finishes, we should have
   /// enough information for every DBG_INSTR_REF to point at an instruction
   /// (or DBG_PHI).
   void finalizeDebugInstrRefs();
 

llvm/lib/CodeGen/MachineFunction.cpp

for (unsigned int I = 0; I < MaxOperand; ++I) {
     assert(NewMO.isDef());
 
     unsigned NewInstrNum = New.getDebugInstrNum();
     makeDebugValueSubstitution(std::make_pair(OldInstrNum, I),
                                std::make_pair(NewInstrNum, I));
   }
 }
 
-auto MachineFunction::salvageCopySSA(MachineInstr &MI)
+auto MachineFunction::salvageCopySSA(
+    MachineInstr &MI, DenseMap<Register, DebugInstrOperandPair> &DbgPHICache)
+    -> DebugInstrOperandPair {
+  const TargetInstrInfo &TII = *getSubtarget().getInstrInfo();
+
+  // Check whether this copy-like instruction has already been salvaged into
+  // an operand pair.
+  Register Dest;
+  if (auto CopyDstSrc = TII.isCopyInstr(MI)) {
+    Dest = CopyDstSrc->Destination->getReg();
+  } else {
+    assert(MI.isSubregToReg());
+    Dest = MI.getOperand(0).getReg();
+  }
+
+  auto CacheIt = DbgPHICache.find(Dest);
+  if (CacheIt != DbgPHICache.end())
+    return CacheIt->second;
+
+  // Calculate the instruction number to use, or install a DBG_PHI.
+  auto OperandPair = salvageCopySSAImpl(MI);
+  DbgPHICache.insert({Dest, OperandPair});
+  return OperandPair;
+}
+
+auto MachineFunction::salvageCopySSAImpl(MachineInstr &MI)
     -> DebugInstrOperandPair {
   MachineRegisterInfo &MRI = getRegInfo();
   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
   const TargetInstrInfo &TII = *getSubtarget().getInstrInfo();
 
   // Chase the value read by a copy-like instruction back to the instruction
   // that ultimately _defines_ that value. This may pass:
   //  * Through multiple intermediate copies, including subregister moves /
void MachineFunction::finalizeDebugInstrRefs() {
 
   auto MakeUndefDbgValue = [&](MachineInstr &MI) {
     const MCInstrDesc &RefII = TII->get(TargetOpcode::DBG_VALUE);
     MI.setDesc(RefII);
     MI.getOperand(0).setReg(0);
     MI.getOperand(1).ChangeToRegister(0, false);
   };
 
+  DenseMap<Register, DebugInstrOperandPair> ArgDbgPHIs;
   for (auto &MBB : *this) {
     for (auto &MI : MBB) {
       if (!MI.isDebugRef() || !MI.getOperand(0).isReg())
         continue;
 
       Register Reg = MI.getOperand(0).getReg();
 
       // Some vregs can be deleted as redundant in the meantime. Mark those
       // as DBG_VALUE $noreg. Additionally, some normal instructions are
       // quickly deleted, leaving dangling references to vregs with no def.
       if (Reg == 0 || !RegInfo->hasOneDef(Reg)) {
         MakeUndefDbgValue(MI);
         continue;
       }
 
       assert(Reg.isVirtual());
       MachineInstr &DefMI = *RegInfo->def_instr_begin(Reg);
 
       // If we've found a copy-like instruction, follow it back to the
       // instruction that defines the source value, see salvageCopySSA docs
       // for why this is important.
       if (DefMI.isCopyLike() || TII->isCopyInstr(DefMI)) {
-        auto Result = salvageCopySSA(DefMI);
+        auto Result = salvageCopySSA(DefMI, ArgDbgPHIs);
         MI.getOperand(0).ChangeToImmediate(Result.first);
         MI.getOperand(1).setImm(Result.second);
       } else {
         // Otherwise, identify the operand number that the VReg refers to.
         unsigned OperandIdx = 0;
         for (const auto &MO : DefMI.operands()) {
           if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
             break;

llvm/test/DebugInfo/X86/dbg-value-funcarg.ll

 ; CHECK: DBG_VALUE %0, $noreg, ![[T3A]], !DIExpression(),
 ; CHECK: CALL64pcrel32 @bar,
 ; CHECK: DBG_VALUE %0, $noreg, ![[TMP]], !DIExpression(),
 ; CHECK: DBG_VALUE 123, $noreg, ![[T3A]], !DIExpression(),
 ; CHECK: CALL64pcrel32 @bar,
 ; CHECK: DBG_VALUE %0, $noreg, ![[T3A]], !DIExpression(),
 ; CHECK: TCRETURNdi64 @bar,
 ; INSTRREF-LABEL: name:            foo_same_param
-; INSTRREF: DBG_PHI $edi, 2
 ; INSTRREF: DBG_PHI $edi, 1
 ; INSTRREF: DBG_VALUE $edi, $noreg, ![[T3A]], !DIExpression(),
 ; INSTRREF: CALL64pcrel32 @bar,
 ; INSTRREF: DBG_INSTR_REF 1, 0, ![[TMP]], !DIExpression(),
 ; INSTRREF: DBG_VALUE 123, $noreg, ![[T3A]], !DIExpression(),
 ; INSTRREF: CALL64pcrel32 @bar,
-; INSTRREF: DBG_INSTR_REF 2, 0, ![[T3A]], !DIExpression(),
+; INSTRREF: DBG_INSTR_REF 1, 0, ![[T3A]], !DIExpression(),
 ; INSTRREF: TCRETURNdi64 @bar,
 entry:
   call void @llvm.dbg.value(metadata i32 %t3a, metadata !33, metadata !DIExpression()), !dbg !35
   tail call void @bar(i32 %t3a) #3, !dbg !36
   call void @llvm.dbg.value(metadata i32 %t3a, metadata !34, metadata !DIExpression()), !dbg !37
   call void @llvm.dbg.value(metadata i32 123, metadata !33, metadata !DIExpression()), !dbg !35
   tail call void @bar(i32 123) #3, !dbg !38
   call void @llvm.dbg.value(metadata i32 %t3a, metadata !33, metadata !DIExpression()), !dbg !35

llvm/test/DebugInfo/X86/dbg-value-funcarg4.ll

+; RUN: llc -mtriple=x86_64-unknown-linux-gnu -start-after=codegenprepare -stop-before=finalize-isel -o - %s -experimental-debug-variable-locations=true | FileCheck %s --implicit-check-not=DBG_PHI
+
+; Test that for multiple dbg.values referring to the same argument, we emit a
+; single DBG_PHI and refer to it twice. (Using more than one DBG_PHI is fine,
+; but inefficient).
+
+; CHECK-DAG: ![[LOCAL:.*]] = !DILocalVariable(name: "local"
+; CHECK-DAG: ![[LOCAL2:.*]] = !DILocalVariable(name: "local2"
+
+; CHECK: DBG_PHI $edi, 1
+
+; CHECK: DBG_INSTR_REF 1, 0, ![[LOCAL]], !DIExpression(),
+; CHECK: DBG_INSTR_REF 1, 0, ![[LOCAL2]], !DIExpression(),
+
+declare void @bar(i32)
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+define dso_local void @foo_local(i32 %t1a) local_unnamed_addr !dbg !7 {
+entry:
+  tail call void @bar(i32 %t1a) #3, !dbg !17
+  %bees = add i32 %t1a, 3
+  call void @llvm.dbg.value(metadata i32 %t1a, metadata !13, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.value(metadata i32 %t1a, metadata !19, metadata !DIExpression()), !dbg !14
+  tail call void @bar(i32 %bees) #3, !dbg !17
+  ret void, !dbg !18
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, nameTableKind: None)
+!1 = !DIFile(filename: "foo.c", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang"}
+!7 = distinct !DISubprogram(name: "foo_local", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+!8 = !DISubroutineType(types: !9)
+!9 = !{null, !10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !{!12, !13}
+!12 = !DILocalVariable(name: "t1a", arg: 1, scope: !7, file: !1, line: 3, type: !10)
+!13 = !DILocalVariable(name: "local", scope: !7, file: !1, line: 4, type: !10)
+!14 = !DILocation(line: 3, column: 20, scope: !7)
+!15 = !DILocation(line: 4, column: 7, scope: !7)
+!16 = !DILocation(line: 5, column: 3, scope: !7)
+!17 = !DILocation(line: 7, column: 3, scope: !7)
+!18 = !DILocation(line: 8, column: 1, scope: !7)
+!19 = !DILocalVariable(name: "local2", scope: !7, file: !1, line: 4, type: !10)

llvm/test/DebugInfo/X86/instr-ref-selectiondag.ll

 ; INSTRREF-NEXT: DBG_VALUE $rdi, 0, ![[SOCKS]], !DIExpression(),
 ; INSTRREF-NEXT: %0:gr64 = COPY $rdi
 ; INSTRREF-NEXT: DBG_INSTR_REF 1, 0, ![[KNEES]], !DIExpression(DW_OP_deref),
 
 ; In fast-isel mode, neither variable are hoisted or forwarded to a physreg.
 
 ; FASTISEL-INSTRREF-LABEL: name: qux
 
-; FASTISEL-INSTRREF:      DBG_PHI $rdi, 2
-; FASTISEL-INSTRREF-NEXT: DBG_PHI $rdi, 1
+; FASTISEL-INSTRREF:      DBG_PHI $rdi, 1
 ; FASTISEL-INSTRREF:      DBG_INSTR_REF 1, 0, ![[SOCKS]], !DIExpression(DW_OP_deref),
 
 ; FASTISEL-INSTRREF-LABEL: bb.1.lala:
-; FASTISEL-INSTRREF:      DBG_INSTR_REF 2, 0, ![[KNEES]], !DIExpression(DW_OP_deref),
+; FASTISEL-INSTRREF:      DBG_INSTR_REF 1, 0, ![[KNEES]], !DIExpression(DW_OP_deref),
 declare i64 @cheddar(i32 *%arg)
 
 define void @qux(i32* noalias sret(i32) %agg.result) !dbg !40 {
 entry:
   call void @llvm.dbg.declare(metadata i32 *%agg.result, metadata !41, metadata !DIExpression()), !dbg !42
   %foo = call i64 @cheddar(i32 *%agg.result), !dbg !42
   br label %lala