[DebugInfo][DAG] PR40427: Avoid accidentally re-ordering DBG_VALUEs due to assumptions about inst creation

[jmorse]

Summary

This patch improves the placement of DBG_VALUEs when created by SelectionDAG by collecting more precise placement information. As documented in PR40427 [0] SelectionDAGs currently muddles which MIR instructions correspond to which IR instructions, leading to off-by-ones and debug-use-before-defs. At the core of this is ProcessSourceNode, which assumes the last instruction in a BB is the start of the last processed IR instruction, which isn't always true.

The 'Orders' mapping in EmitSchedule is supposed to (AFAICT) identify the first MIR instruction of an IR instruction. This patch adds an EmitNode helper that explicitly collects this information, by:

• Storing the last instruction in the BB,
• Emitting the designated SDNode,
• Comparing the last-instruction-in-bb after emission, to what it was before,
• Returning the first of any new instructions.

This is an awkwardly verbose way of finding the first instruction that an SDNode produces, however I'm not aware of any facility in InstrEmitter that provides this information, thus it must be determined by observation.

This patch also adjusts ProcessSourceNode: it no longer always records an IR instruction (identified by Order number) as having been seen whenever an SDNode is lowered, it now only does it if a MIR instruction is generated too. We also don't enter 'nullptr' records for SDNodes at the start of the function: the debuginfo code at the end of EmitSchedule is already designed to cope with missing IR Order numbers, rely on that rather than trying to second guess it.

With a stage2 build of llvm/clang 3.4 we get a fractional tick up in variable locations, and a fractional tick down in bytes coverage. This is probably due to a few use-before-defs being eliminated, and the combined effect of many DBG_VALUEs no longer being off-by-one'd.

The NVPTX test change is because a DBG_VALUE shifts down one instruction, creating a new local label in the output file, re-numbering others. pr40427.ll tests for regression and has some useful ordering properties. Three DBG_VALUE orders change in sdag-dbgvalue-phi-use-2.ll, happily all originally marked with 'XXX' comments indicating the order was wrong. One 'XXX' remains: IMO this is because of the first conditional block in ProcessSourceNode bypassing various checks by passing in a zero order number. I haven't investigated this matter though.

[0] https://bugs.llvm.org/show_bug.cgi?id=40427

[aprantl]

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

823

if BB->begin() == BB->end() doesn't that imply I == BB->begin(), too?

844

early return instead?

[jmorse]

Refactor EmitNode helper to early-return if no insts inserted

[jmorse]

Simplify condition testing for existence of earlier iterators

[uabelho]

I don't know this code at all.

[aprantl]

I think I could convince myself that this change is correct. Thanks!

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

746

if (!Order || Seen.count(Order)) {

[rogfer01]

@jmorse pr40427.ll uses x86-specific bits in the CHECK lines and is causing failures in builds that do not target by default x86 (e.g. http://lab.llvm.org:8011/builders/clang-ppc64le-linux-lnt/builds/16847 )

Would it be possible to add a target triple = "x86_64-unknown-linux-gnu" line in the testcase?

Thanks!

[jmorse]

Hi Roger

In D57163#1375031, @rogfer01 wrote:

@jmorse pr40427.ll uses x86-specific bits in the CHECK lines and is causing failures in builds that do not target by default x86 (e.g. http://lab.llvm.org:8011/builders/clang-ppc64le-linux-lnt/builds/16847 )

Hopefully fixed in r352460, sorry for the bother and thanks for the heads-up. I'd incorrectly assumed being in the X86 directory was a sufficient filter.

Curiously I didn't get a buildbot email related to this, but that's probably because they were down for much of yesterday.

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

 }
 
 // ProcessSourceNode - Process nodes with source order numbers. These are added
 // to a vector which EmitSchedule uses to determine how to insert dbg_value
 // instructions in the right order.
 static void
 ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
                   DenseMap<SDValue, unsigned> &VRBaseMap,
-                  SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
-                  SmallSet<unsigned, 8> &Seen) {
+                  SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,
+                  SmallSet<unsigned, 8> &Seen, MachineInstr *NewInsn) {
   unsigned Order = N->getIROrder();
-  if (!Order || !Seen.insert(Order).second) {
+  if (!Order || Seen.count(Order) != 0) {
     // Process any valid SDDbgValues even if node does not have any order
     // assigned.
     ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
     return;
   }
 
-  MachineBasicBlock *BB = Emitter.getBlock();
-  auto IP = Emitter.getInsertPos();
-  if (IP == BB->begin() || BB->back().isPHI() ||
-      // Fast-isel may have inserted some instructions, in which case the
-      // BB->back().isPHI() test will not fire when we want it to.
-      std::prev(IP)->isPHI()) {
-    // Did not insert any instruction.
-    Orders.push_back({Order, (MachineInstr *)nullptr});
-    return;
+  // If a new instruction was generated for this Order number, record it.
+  // Otherwise, leave this order number unseen: we will either find later
+  // instructions for it, or leave it unseen if there were no instructions at
+  // all.
+  if (NewInsn) {
+    Seen.insert(Order);
+    Orders.push_back({Order, NewInsn});
   }
 
-  Orders.push_back({Order, &*std::prev(IP)});
+  // Even if no instruction was generated, a Value may have become defined via
+  // earlier nodes. Try to process them now.
   ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
 }
 
 void ScheduleDAGSDNodes::
 EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap,
                 MachineBasicBlock::iterator InsertPos) {
   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {

 EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
   InstrEmitter Emitter(BB, InsertPos);
   DenseMap<SDValue, unsigned> VRBaseMap;
   DenseMap<SUnit*, unsigned> CopyVRBaseMap;
   SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders;
   SmallSet<unsigned, 8> Seen;
   bool HasDbg = DAG->hasDebugValues();
 
+  // Emit a node, and determine where its first instruction is for debuginfo.
+  // Zero, one, or multiple instructions can be created when emitting a node.
+  auto EmitNode =
+      [&](SDNode *Node, bool IsClone, bool IsCloned,
+          DenseMap<SDValue, unsigned> &VRBaseMap) -> MachineInstr * {
+    // Fetch instruction prior to this, or end() if nonexistant.
+    auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
+      bool BadPos = BB->begin() == BB->end() || I == BB->begin();
+      if (BadPos)
+        return BB->end();
+      else
+        return std::prev(Emitter.getInsertPos());
+    };
+
+    MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
+    Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
+    MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());
+
+    // If the iterator changed, at least one instruction was inserted.
+    if (Before != After) {
+      if (Before == BB->end()) {
+        // There were no prior instructions; the new ones must start at the
+        // beginning of the block.
+        return &Emitter.getBlock()->instr_front();
+      } else {
+        // Return first instruction after the pre-existing instructions.
+        return &*std::next(Before);
+      }
+    } else {
+      // No new instruction.
+      return nullptr;
+    }
+  };
+
   // If this is the first BB, emit byval parameter dbg_value's.
   if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
     SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
     SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
     for (; PDI != PDE; ++PDI) {
       MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
       if (DbgMI) {
         BB->insert(InsertPos, DbgMI);
if (!SU->getNode()) {
       continue;
     }
 
     SmallVector<SDNode *, 4> GluedNodes;
     for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
       GluedNodes.push_back(N);
     while (!GluedNodes.empty()) {
       SDNode *N = GluedNodes.back();
-      Emitter.EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
+      auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
       // Remember the source order of the inserted instruction.
       if (HasDbg)
-        ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen);
+        ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
       GluedNodes.pop_back();
     }
-    Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned,
-                     VRBaseMap);
+    auto NewInsn =
+        EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
     // Remember the source order of the inserted instruction.
     if (HasDbg)
-      ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders,
-                        Seen);
+      ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
+                        NewInsn);
   }
 
   // Insert all the dbg_values which have not already been inserted in source
   // order sequence.
   if (HasDbg) {
     MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
 
     // Sort the source order instructions and use the order to insert debug
     // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
     // regardless of the host's implementation fo std::sort.
     std::stable_sort(Orders.begin(), Orders.end(), less_first());
     std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
                      [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
                        return LHS->getOrder() < RHS->getOrder();
                      });
 
     SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
     SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
     // Now emit the rest according to source order.
     unsigned LastOrder = 0;
     for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
       unsigned Order = Orders[i].first;
       MachineInstr *MI = Orders[i].second;
       // Insert all SDDbgValue's whose order(s) are before "Order".
-      if (!MI)
-        continue;
+      assert(MI);
       for (; DI != DE; ++DI) {
         if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
           break;
         if ((*DI)->isEmitted())
           continue;
 
         MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
         if (DbgMI) {

test/DebugInfo/NVPTX/debug-info.ll

 ; CHECK-NEXT: .b8 42                               // Abbrev [42] 0x26f7:0x17 DW_TAG_inlined_subroutine
 ; CHECK-NEXT: .b32 9785                            // DW_AT_abstract_origin
 ; CHECK-NEXT: .b64 Ltmp2                           // DW_AT_low_pc
 ; CHECK-NEXT: .b64 Ltmp3                           // DW_AT_high_pc
 ; CHECK-NEXT: .b8 12                               // DW_AT_call_file
 ; CHECK-NEXT: .b8 6                                // DW_AT_call_line
 ; CHECK-NEXT: .b8 43                               // Abbrev [43] 0x270e:0x22 DW_TAG_inlined_subroutine
 ; CHECK-NEXT: .b32 9791                            // DW_AT_abstract_origin
-; CHECK-NEXT: .b64 Ltmp8                           // DW_AT_low_pc
-; CHECK-NEXT: .b64 Ltmp9                           // DW_AT_high_pc
+; CHECK-NEXT: .b64 Ltmp9                           // DW_AT_low_pc
+; CHECK-NEXT: .b64 Ltmp10                          // DW_AT_high_pc
 ; CHECK-NEXT: .b8 12                               // DW_AT_call_file
 ; CHECK-NEXT: .b8 8                                // DW_AT_call_line
 ; CHECK-NEXT: .b8 44                               // Abbrev [44] 0x2725:0x5 DW_TAG_formal_parameter
 ; CHECK-NEXT: .b32 9811                            // DW_AT_abstract_origin
 ; CHECK-NEXT: .b8 44                               // Abbrev [44] 0x272a:0x5 DW_TAG_formal_parameter
 ; CHECK-NEXT: .b32 9820                            // DW_AT_abstract_origin
 ; CHECK-NEXT: .b8 0                                // End Of Children Mark
 ; CHECK-NEXT: .b8 0                                // End Of Children Mark

test/DebugInfo/X86/pr40427.ll

+; RUN: llc -start-after=codegenprepare -stop-before=expand-isel-pseudos -o - < %s | FileCheck %s
+; Test for correct placement of DBG_VALUE, which in PR40427 is placed before
+; the load instruction it refers to. The circumstance replicated here is where
+; two instructions in a row, trunc and add, begin with no-op Copy{To,From}Reg
+; SDNodes that produce no instructions.
+; The DBG_VALUE instruction should come immediately after the load instruction
+; because the truncate is optimised out, and the DBG_VALUE should be placed
+; in front of the first instruction that occurs after the dbg.value.
+
+; CHECK: ![[DBGVAR:[0-9]+]] = !DILocalVariable(name: "bees",
+
+define i16 @lolwat(i1 %spoons, i64 *%bees, i16 %yellow, i64 *%more) {
+entry:
+  br i1 %spoons, label %trueb, label %falseb
+trueb:
+  br label %block
+falseb:
+  br label %block
+block:
+; CHECK:      [[PHIREG:%[0-9]+]]:gr64 = PHI %6, %bb.2, %4, %bb.1
+; CHECK-NEXT: [[LOADR:%[0-9]+]]:gr16 = MOV16rm %0
+; CHECK-NEXT: DBG_VALUE [[LOADR]], $noreg, ![[DBGVAR]]
+; CHECK-NEXT: %{{[0-9]+}}:gr32 = IMPLICIT_DEF
+  %foo = phi i64 *[%bees, %trueb], [%more, %falseb]
+  %forks = bitcast i64 *%foo to i32 *
+  %ret = load i32, i32 *%forks, !dbg !6
+  %cast = trunc i32 %ret to i16, !dbg !6
+  call void @llvm.dbg.value(metadata i16 %cast, metadata !1, metadata !DIExpression()), !dbg !6
+  %orly2 = add i16 %yellow, 1
+  br label %bb1
+bb1:
+  %cheese = add i16 %orly2, %cast
+  ret i16 %cheese, !dbg !6
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.module.flags = !{!4}
+!llvm.dbg.cu = !{!2}
+!1 = !DILocalVariable(name: "bees", scope: !5, type: null)
+!2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "beards", isOptimized: true, runtimeVersion: 4, emissionKind: FullDebug)
+!3 = !DIFile(filename: "bees.cpp", directory: "")
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = distinct !DISubprogram(name: "nope", scope: !2, file: !3, line: 1, unit: !2)
+!6 = !DILocation(line: 0, scope: !5)
+!7 = !DILocalVariable(name: "flannel", scope: !5, type: null)

test/DebugInfo/X86/sdag-dbgvalue-phi-use-2.ll

 
 for.body:                                         ; preds = %for.body.lr.ph, %for.body
 ; CHECK-LABEL: bb.{{.*}}.for.body:
 ; CHECK:      [[REG2:%[0-9]+]]:gr32 = PHI
 ; CHECK-NEXT: [[REG3:%[0-9]+]]:gr32 = PHI
 ; CHECK-NEXT: [[REG4:%[0-9]+]]:gr32 = PHI
 ; CHECK-NEXT: DBG_VALUE [[REG3]], $noreg, !16
 ; CHECK-NEXT: DBG_VALUE 555, $noreg, !17
-; XXX: Shouldn't the following DBG_VALUE be placed after the add (ADD32rr).
+; CHECK-NEXT: [[ADDREG:%[0-9]+]]:gr32 = nuw nsw ADD32rr
 ; CHECK-NEXT: DBG_VALUE [[REG2]], $noreg, !17
-; CHECK-NEXT: ADD32rr
-; XXX: Shouldn't the following DBG_VALUE be placed after the mul (LEA etc).
+; CHECK:      [[MULREG:%[0-9]+]]:gr32 = LEA64_32r
 ; CHECK-NEXT: DBG_VALUE 777, $noreg, !17
-; CHECK:      INC32r
-; XXX: Shouldn't the following DBG_VALUE be placed after the icmp (the non-dead implicit def of $eflags)
-; CHECK:      DBG_VALUE [[REG4]]
-; CHECK-NEXT: implicit-def $eflags
+; XXX: The following DBG_VALUE should have stayed below the INC32r
+; CHECK-NEXT: DBG_VALUE [[MULREG]], $noreg, !16
+; CHECK-NEXT: [[INCREG:%[0-9]+]]:gr32 = nuw nsw INC32r
+; CHECK-NEXT: DBG_VALUE [[INCREG]], $noreg, !17
+; CHECK-NEXT: DBG_VALUE [[ADDREG]], $noreg, !15
+; CHECK-NEXT: implicit-def $eflags,
+; CHECK-NEXT: DBG_VALUE [[REG4]]
   %u.023 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
   %y.022 = phi i32 [ 13, %for.body.lr.ph ], [ %mul, %for.body ]
   %x.021 = phi i32 [ 9, %for.body.lr.ph ], [ %add, %for.body ]
   call void @llvm.dbg.value(metadata i32 %y.022, metadata !16, metadata !DIExpression()), !dbg !27
   ; This dbg.value has been manually added compared to dbg_value_phi_isel1.ll
   call void @llvm.dbg.value(metadata i32 555, metadata !17, metadata !DIExpression()), !dbg !28
   %add = add nuw nsw i32 %y.022, %x.021, !dbg !41
   ; This dbg.value has been manually moved compared to dbg_value_phi_isel1.ll