[DebugInfo] Pre-RA MachineSink: sink DBG_VALUEs that don't immediately follow the sunk instruction too

[jmorse]

Summary

This patch improves the pre-register-allocation portions of MachineSink. Two things happen here -- firstly we collect DBG_VALUEs seen when walking through a machine basic block and record their virtual-register uses, so that it's easy to determine what debuginfo to sink when an instruction sinks. This avoids relying on the unsound collectDebugValues function, and so will collect DBG_VALUEs that don't immediately follow the sunk instruction.

Secondly, debug users of what an instruction defines may no longer be dominated after that instruction sinks (see: the added test case). It's possible to salvage some of these debug users if the sunk instruction was a copy (which can be propagated), and I've added a function to do this.

On a clang-3.4 build we save a fractional number of variable locations and increase covered scope-bytes by ~0.5%.

The copy-propagation to no-longer-dominated instructions makes zero contribution to that coverage improvement -- it's there mostly to ease some test failures that occur when CodeGenPrepare::placeDbgValues is deleted, a patch I will totally upload this week. If the copy-prop part of this patch is dubious, I can fold it into that later patch, where it's easier to see what's going on.

[aprantl]

test/DebugInfo/MIR/X86/machinesink.mir

28 ↗

(On Diff #187361)

do you need all these attributes? They are usually a pain to upgrade in testcases.

58 ↗

(On Diff #187361)

Do you need the TBAA analysis results?

[jmorse]

Refresh this patch:

• Rebase it onto the current open stack
• Remove a bunch of needless attributes and metadata

There's a minor test change too: one of the parent patches now no longer marks DBG_VALUEs undef where it can recover them by copy-propagating. This isn't a behaviour that this patch tests for, so I've updated the checks for the first DBG_VALUE in the test to not be marked "undef".

[aprantl]

lib/CodeGen/MachineSink.cpp

164 ↗

(On Diff #209442)

doxygen comment?

407 ↗

(On Diff #209442)

assert, since we already checked this above?

952 ↗

(On Diff #209442)

this looks very similar to the body of ProcessDbgInst...

998 ↗

(On Diff #209442)

, -> . ?

1002 ↗

(On Diff #209442)

&& "???"

[jmorse]

Revise some comments & assertions.

Apologies for the long latency involved in getting this turned around.

[jmorse]

lib/CodeGen/MachineSink.cpp

952 ↗

(On Diff #209442)

It's sort-of it's compliment, ProcessDbgInst builds up the contents of SeenDbgUsers as we walk backwards through a block spotting DBG_VALUEs, while this portion of code is detecting vreg defs that are going to be sunk and collecting those seen debug insts into one vector.

The common code would be "return the SeenDbgUsers element corresponding to this operand or nullptr", for me this is a sufficiently small similarity that duplication is OK, YMMV.

llvm/lib/CodeGen/MachineSink.cpp

class MachineSinking : public MachineFunctionPass {
     // will be split.
     SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
 
     SparseBitVector<> RegsToClearKillFlags;
 
     using AllSuccsCache =
         std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
 
+    // Remember debug uses of vregs seen, so we know what to sink out of blocks.
+    DenseMap<unsigned, TinyPtrVector<MachineInstr *>> SeenDbgUsers;
+
   public:
     static char ID; // Pass identification
 
     MachineSinking() : MachineFunctionPass(ID) {
       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
public:
     }
 
     void releaseMemory() override {
       CEBCandidates.clear();
     }
 
   private:
     bool ProcessBlock(MachineBasicBlock &MBB);
+    void ProcessDbgInst(MachineInstr &MI);
     bool isWorthBreakingCriticalEdge(MachineInstr &MI,
                                      MachineBasicBlock *From,
                                      MachineBasicBlock *To);
 
     /// Postpone the splitting of the given critical
     /// edge (\p From, \p To).
     ///
     /// We do not split the edges on the fly. Indeed, this invalidates
     /// the dominance information and thus triggers a lot of updates
     /// of that information underneath.
     /// Instead, we postpone all the splits after each iteration of
     /// the main loop. That way, the information is at least valid
     /// for the lifetime of an iteration.
     ///
     /// \return True if the edge is marked as toSplit, false otherwise.
     /// False can be returned if, for instance, this is not profitable.
     bool PostponeSplitCriticalEdge(MachineInstr &MI,
                                    MachineBasicBlock *From,
                                    MachineBasicBlock *To,
                                    bool BreakPHIEdge);
     bool SinkInstruction(MachineInstr &MI, bool &SawStore,
-
                          AllSuccsCache &AllSuccessors);
+
+    /// If we sink a COPY inst, some debug users of it's destination may no
+    /// longer be dominated by the COPY, and will eventually be dropped.
+    /// This is easily rectified by forwarding the non-dominated debug uses
+    /// to the copy source.
+    void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
+                                       MachineBasicBlock *TargetBlock);
     bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
                                  MachineBasicBlock *DefMBB,
                                  bool &BreakPHIEdge, bool &LocalUse) const;
     MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
                bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
     bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
                               MachineBasicBlock *MBB,
                               MachineBasicBlock *SuccToSinkTo,
do {
     MachineInstr &MI = *I;  // The instruction to sink.
 
     // Predecrement I (if it's not begin) so that it isn't invalidated by
     // sinking.
     ProcessedBegin = I == MBB.begin();
     if (!ProcessedBegin)
       --I;
 
-    if (MI.isDebugInstr())
+    if (MI.isDebugInstr()) {
+      if (MI.isDebugValue())
+        ProcessDbgInst(MI);
       continue;
+    }
 
     bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
     if (Joined) {
       MadeChange = true;
       continue;
     }
 
     if (SinkInstruction(MI, SawStore, AllSuccessors)) {
       ++NumSunk;
       MadeChange = true;
     }
 
     // If we just processed the first instruction in the block, we're done.
   } while (!ProcessedBegin);
 
+  SeenDbgUsers.clear();
+
   return MadeChange;
 }
 
+void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
+  // When we see DBG_VALUEs for registers, record any vreg it reads, so that
+  // we know what to sink if the vreg def sinks.
+  assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
+
+  MachineOperand &MO = MI.getOperand(0);
+  if (!MO.isReg() || !MO.getReg().isVirtual())
+    return;
+
+  SeenDbgUsers[MO.getReg()].push_back(&MI);
+}
+
 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
                                                  MachineBasicBlock *From,
                                                  MachineBasicBlock *To) {
   // FIXME: Need much better heuristics.
 
   // If the pass has already considered breaking this edge (during this pass
   // through the function), then let's go ahead and break it. This means
   // sinking multiple "cheap" instructions into the same block.
if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
     return false;
 
   return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
          (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
           MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
          MBP.LHS.getReg() == BaseOp->getReg();
 }
 
-/// Sink an instruction and its associated debug instructions. If the debug
-/// instructions to be sunk are already known, they can be provided in DbgVals.
+/// Sink an instruction and its associated debug instructions.
 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
                         MachineBasicBlock::iterator InsertPos,
-                        SmallVectorImpl<MachineInstr *> *DbgVals = nullptr) {
+                        SmallVectorImpl<MachineInstr *> &DbgValuesToSink) {
   const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
   const TargetInstrInfo &TII = *MI.getMF()->getSubtarget().getInstrInfo();
 
-  // If debug values are provided use those, otherwise call collectDebugValues.
-  SmallVector<MachineInstr *, 2> DbgValuesToSink;
-  if (DbgVals)
-    DbgValuesToSink.insert(DbgValuesToSink.begin(),
-                           DbgVals->begin(), DbgVals->end());
-  else
-    MI.collectDebugValues(DbgValuesToSink);
-
   // If we cannot find a location to use (merge with), then we erase the debug
   // location to prevent debug-info driven tools from potentially reporting
   // wrong location information.
   if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
     MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
                                                  InsertPos->getDebugLoc()));
   else
     MI.setDebugLoc(DebugLoc());
if (BreakPHIEdge) {
     return false;
   }
 
   // Determine where to insert into. Skip phi nodes.
   MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
   while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
     ++InsertPos;
 
-  performSink(MI, *SuccToSinkTo, InsertPos);
+  // Collect debug users of any vreg that this inst defines.
+  SmallVector<MachineInstr *, 4> DbgUsersToSink;
+  for (auto &MO : MI.operands()) {
+    if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
+      continue;
+    if (!SeenDbgUsers.count(MO.getReg()))
+      continue;
+
+    auto &Users = SeenDbgUsers[MO.getReg()];
+    DbgUsersToSink.insert(DbgUsersToSink.end(), Users.begin(), Users.end());
+  }
+
+  // After sinking, some debug users may not be dominated any more. If possible,
+  // copy-propagate their operands. As it's expensive, don't do this if there's
+  // no debuginfo in the program.
+  if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
+    SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);
+
+  performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);
 
   // Conservatively, clear any kill flags, since it's possible that they are no
   // longer correct.
   // Note that we have to clear the kill flags for any register this instruction
   // uses as we may sink over another instruction which currently kills the
   // used registers.
   for (MachineOperand &MO : MI.operands()) {
     if (MO.isReg() && MO.isUse())
       RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
   }
 
   return true;
 }
 
+void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
+    MachineInstr &MI, MachineBasicBlock *TargetBlock) {
+  assert(MI.isCopy());
+  assert(MI.getOperand(1).isReg());
+
+  // Enumerate all users of vreg operands that are def'd. Skip those that will
+  // be sunk. For the rest, if they are not dominated by the block we will sink
+  // MI into, propagate the copy source to them.
+  SmallVector<MachineInstr *, 4> DbgDefUsers;
+  const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
+  for (auto &MO : MI.operands()) {
+    if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
+      continue;
+    for (auto &User : MRI.use_instructions(MO.getReg())) {
+      if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent()))
+        continue;
+
+      // If is in same block, will either sink or be use-before-def.
+      if (User.getParent() == MI.getParent())
+        continue;
+
+      assert(User.getOperand(0).isReg() &&
+             "DBG_VALUE user of vreg, but non reg operand?");
+      DbgDefUsers.push_back(&User);
+    }
+  }
+
+  // Point the users of this copy that are no longer dominated, at the source
+  // of the copy.
+  for (auto *User : DbgDefUsers) {
+    User->getOperand(0).setReg(MI.getOperand(1).getReg());
+    User->getOperand(0).setSubReg(MI.getOperand(1).getSubReg());
+  }
+}
+
 //===----------------------------------------------------------------------===//
 // This pass is not intended to be a replacement or a complete alternative
 // for the pre-ra machine sink pass. It is only designed to sink COPY
 // instructions which should be handled after RA.
 //
 // This pass sinks COPY instructions into a successor block, if the COPY is not
 // used in the current block and the COPY is live-in to a single successor
 // (i.e., doesn't require the COPY to be duplicated).  This avoids executing the
for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
     }
     DbgValsToSink.insert(DbgValsToSink.begin(), DbgValsToSinkSet.begin(),
                          DbgValsToSinkSet.end());
 
     // Clear the kill flag if SrcReg is killed between MI and the end of the
     // block.
     clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
     MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
-    performSink(*MI, *SuccBB, InsertPos, &DbgValsToSink);
+    performSink(*MI, *SuccBB, InsertPos, DbgValsToSink);
     updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
 
     Changed = true;
     ++NumPostRACopySink;
   }
   return Changed;
 }
 

llvm/test/DebugInfo/MIR/X86/machinesink.mir

+# RUN: llc -mtriple=x86_64-unknown-unknown -run-pass=machine-sink -o - %s | FileCheck %s
+# Check various things when we sink machine instructions:
+#   a) DBG_VALUEs should sink with defs
+#   b) Undefs should be left behind
+#   c) DBG_VALUEs not immediately following the defining inst should sink too
+#   d) If we generate debug-use-before-defs through sinking, and can copy
+#      propagate to a different value, we should do that.
+--- |
+  target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+
+  @x = common local_unnamed_addr global i32 0, align 4, !dbg !0
+
+  ; Function Attrs: noreturn nounwind uwtable
+  define void @Process(i32* nocapture readonly %p) local_unnamed_addr !dbg !9 {
+  ; Stripped
+  entry:
+    br label %nou
+  nou:
+    br label %exit
+  exit:
+    ret void
+  }
+
+  ; Function Attrs: nounwind readnone
+  declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
+
+  !llvm.dbg.cu = !{!1}
+  !llvm.module.flags = !{!6, !7}
+  !llvm.ident = !{!8}
+
+  !0 = !DIGlobalVariableExpression(var: !DIGlobalVariable(name: "x", scope: !1, file: !2, line: 1, type: !5, isLocal: false, isDefinition: true), expr: !DIExpression())
+  !1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !3, globals: !4)
+  !2 = !DIFile(filename: "t.c", directory: "")
+  !3 = !{}
+  !4 = !{!0}
+  !5 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !6 = !{i32 2, !"Dwarf Version", i32 4}
+  !7 = !{i32 2, !"Debug Info Version", i32 3}
+  !8 = !{!"clang version 4.0.0 "}
+  !9 = distinct !DISubprogram(name: "Process", scope: !2, file: !2, line: 2, type: !10, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !1, retainedNodes: !15)
+  !10 = !DISubroutineType(types: !11)
+  !11 = !{null, !12}
+  !12 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !13, size: 64)
+  !13 = !DIDerivedType(tag: DW_TAG_const_type, baseType: !14)
+  !14 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
+  !15 = !{!16}
+  !16 = !DILocalVariable(name: "p", arg: 1, scope: !9, file: !2, line: 2, type: !12)
+  !17 = !DIExpression()
+  !18 = !DILocation(line: 2, column: 34, scope: !9)
+  !28 = !DILexicalBlockFile(scope: !9, file: !2, discriminator: 1)
+
+  ; CHECK: [[VARNUM:![0-9]+]] = !DILocalVariable(name: "p",
+
+...
+---
+name:            Process
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+  - { reg: '$rsi', virtual-reg: '%2' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1.nou(0x80000000), %bb.2.exit
+    liveins: $rdi, $esi
+
+    ; This block should have the vreg copy sunk from it, the DBG_VALUE with it,
+    ; and a copy-prop'd DBG_VALUE left over.
+    ; CHECK-LABEL: bb.0.entry:
+    ; CHECK:       [[ARG0VREG:%[0-9]+]]:gr64 = COPY $rdi
+    ; CHECK-NEXT:  CMP32ri $esi, 0
+    ; CHECK-NEXT:  DBG_VALUE [[ARG0VREG]], $noreg, [[VARNUM]]
+    ; CHECK-NEXT:  JCC_1 %bb.1, 4
+    ; CHECK-NEXT:  JMP_1
+
+    %2:gr64 = COPY $rdi
+    %5:gr64 = COPY %2
+    CMP32ri $esi, 0, implicit-def $eflags
+    DBG_VALUE %5, $noreg, !16, !17, debug-location !18
+    JCC_1 %bb.1.nou, 4, implicit $eflags
+    JMP_1 %bb.2.exit
+
+  bb.1.nou:
+    successors: %bb.2.exit(0x80000000)
+
+    ; This block should receive the sunk copy and DBG_VALUE
+    ; CHECK-LABEL: bb.1.nou:
+    ; CHECK:       [[SUNKVREG:%[0-9]+]]:gr64 = COPY [[ARG0VREG]]
+    ; CHECK-NEXT:  DBG_VALUE [[SUNKVREG]], $noreg, [[VARNUM]]
+    ; CHECK-NEXT:  ADD64ri8
+    ; CHECK-NEXT:  JMP_1
+    %1:gr64 = ADD64ri8 %5, 4, implicit-def dead $eflags
+    JMP_1 %bb.2.exit
+
+  bb.2.exit:
+    ; The DBG_VALUE below should have its operand copy-propagated after
+    ; the copy to %5 is sunk.
+    ; CHECK-LABEL: bb.2.exit:
+    ; CHECK:       DBG_VALUE [[ARG0VREG]], $noreg, [[VARNUM]]
+    ; CHECK-NEXT:  $rax = MOV64rr [[ARG0VREG]]
+    ; CHECK-NEXT:  RET 0
+    DBG_VALUE %5, _, !16, !17, debug-location !18
+    $rax = MOV64rr %2
+    RET 0
+...