[DebugInfo][DAG] Either salvage dangling debug info or emit Undef DBG_VALUEs

[jmorse]

Summary

In this patch SelectionDAG tries to salvage any dbg.values that are going to be dropped, in case they can be recovered from Values in the current BB. It also strengthens SelectionDAGs handling of dangling debug data, so that dbg.values are *always* emitted (as Undef or otherwise) instead of dangling forever.

The motivation behind this patch exists in the new test case: a memory address (here a bitcast and GEP) exist in one basic block, and a dbg.value referring to the address is left in the 'next' block. The base pointer is live across all basic blocks. In current llvm trunk the dbg.value cannot be encoded, and it isn't even emitted as an Undef DBG_VALUE.

Note at this point that this change depends on two NFC refactors; I'll edit their phab-diff numbers in here when they're up in a moment. One refactors the dbg_value-to-SDDbgValue functionality into a utility method (handleDebugValue), the other refactors salvageDebugInfo to allow salvaging things that aren't necessarily DbgValueInsts (salvageDebugInfoImpl).

The change is simply: if we're definitely going to drop a dbg.value, repeatedly apply salvageDebugInfo to its operand until either we find something that can be encoded, or we can't salvage any further in which case we produce an Undef DBG_VALUE. To know when we're "definitely going to drop a dbg.value", SelectionDAG signals SelectionDAGBuilder when all IR instructions have been encoded to force salvaging. This ensures that any dbg.value that's dangling after DAG creation will have a corresponding DBG_VALUE encoded. (There's a FIXME about this in the dbg_value intrinsic handler).

The sdag-dangling-dbgvalue.ll test changes and gets some new Undef DBG_VALUEs: each time it's because there's a dbg.value of an unseen SDNode, immediately followed by a dbg.value for the same variable of a null constant. IMO this is expected: the dbg.values with unseen operands were previously silently dropped, emitting Undefs is better. The fact that there are two in a row for the same variable is because that's what's in the test input.

Finally some clang-3.4 debuginfo statistics: I've used D57584 as a base because this patch depends on it, and measure variables-with-location coverage and bytes-in-scope coverage. I've also measured four flavours of this patch:

• as-is (plain)
• no force-salvage signal from SelectionDAG
• no new Undef DBG_VALUE generation.
• Neither Undef nor force-salvage

        |  Pct var cov | Pct scope-bytes |
+-----------------------------------------
D57584  |     75.4     |       46.9      |
Plain   |     75.2     |       47.8      |
No-force|     75.4     |       47.0      |
No-undef|     75.7     |       48.3      |
No-undef|              |                 |
 and no |              |                 |
 force  |     75.4     |       46.9      |

The headline figures for "plain" is that there's an almost-1% improvement in scope-bytes coverage; but a 0.2% drop in percent variables covered. My interpretation is that forcing salvaging is good (No-undef has good numbers), and the reduction in variable coverage comes from the new Undef DBG_VALUEs are being generated where they weren't before. Which IMO is an accuracy improvement.

The reason for more Undefs reducing percent variable coverage is partially due to there being more source-variables in the output binaries as a result. Speculation: I reckon some of this reduction is because we sometimes hoist dbg.values outside of their lexical scopes (due to our old friend placeDbgValues) and now that we correctly terminate dangling dbg.values, we find that some of their ranges are no longer anywhere in their lexical scopes, leading to no location at all.

[aprantl]

Looks mostly good!

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1195 ↗

(On Diff #185066)

That comment should be in the function body or in the header.

Perhaps rename the function so it contains the word salvage?

1200 ↗

(On Diff #185066)

variable name & explicit type?

1221 ↗

(On Diff #185066)

!NewExpr

1239 ↗

(On Diff #185066)

Great!

1240 ↗

(On Diff #185066)

Shouldn't we better use the type that was in the dbg.value for consistency? It makes no semantic difference, but it makes the IR less confusing to read.

1244 ↗

(On Diff #185066)

debug location is usually used to refer to DILocation. Perhaps just say "debug value" instead?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

678 ↗

(On Diff #185066)

found a typo in the context

688 ↗

(On Diff #185066)

///

[jmorse]

Address comments; also re-instate and revise the 'TODO' comment I was deleting. After reading it again, I think it's not referring to the problem that this patch solves.

[aprantl]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

682 ↗

(On Diff #185086)

Please drop the resolveDanglingDebugInfo -

test/DebugInfo/X86/sdag-ir-salvage.ll

5 ↗

(On Diff #185086)

can you add a check for the next: label, too?

[srhines]

This patch appears to generate non-reproducible builds in some cases. I can craft a more minimal test case, but the following link (https://godbolt.org/z/sWucUZ) is what I have been using. If I run Clang multiple times, the output eventually swaps the order of some undef DEBUG_VALUE's. I am just passing "-O1 -g" with that .ii file. It isn't obvious to me yet what is causing this to be unordered/non-deterministic.

[lebedev.ri]

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1351

/// Keeps track of dbg_values for which we have not yet seen the referent.
/// We defer handling these until we do see it.
DenseMap<const Value*, DanglingDebugInfoVector> DanglingDebugInfoMap;

I don't think DenseMap iteration order is guaranteed, unlike std::map?

[jmorse]

In D57694#1440571, @srhines wrote:

This patch appears to generate non-reproducible builds in some cases. I can craft a more minimal test case, but the following link (https://godbolt.org/z/sWucUZ) is what I have been using. If I run Clang multiple times, the output eventually swaps the order of some undef DEBUG_VALUE's. I am just passing "-O1 -g" with that .ii file. It isn't obvious to me yet what is causing this to be unordered/non-deterministic.

Curses; you're correct, and Roman seems to have pinned down where it comes from. I'll generate a patch shortly, many thanks for reducing and reporting this!

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1351

I believe you're right -- and the order in which salvageUnresolvedDbgValue is called can be preserved in a vector further into SelectionDAG.

[srhines]

Switching it to a MapVector makes it deterministic. I was just struggling late last night to try to reduce the .ll file down to something worth checking in! If you want to take over to minimize the test case, that would be much appreciated. Let me know so I can continue doing that if needed. Thanks.

[jmorse]

In D57694#1441530, @srhines wrote:

Switching it to a MapVector makes it deterministic. I was just struggling late last night to try to reduce the .ll file down to something worth checking in! If you want to take over to minimize the test case, that would be much appreciated. Let me know so I can continue doing that if needed. Thanks.

Hmm, what kind of requirements are there for tests for nondeterminism? Just a high probability of triggering the existing fault/variation? This is interesting as unreliable compilation presumably means the test can't be reliable either.

[probinson]

In D57694#1441561, @jmorse wrote:

In D57694#1441530, @srhines wrote:

Switching it to a MapVector makes it deterministic. I was just struggling late last night to try to reduce the .ll file down to something worth checking in! If you want to take over to minimize the test case, that would be much appreciated. Let me know so I can continue doing that if needed. Thanks.

Hmm, what kind of requirements are there for tests for nondeterminism? Just a high probability of triggering the existing fault/variation? This is interesting as unreliable compilation presumably means the test can't be reliable either.

First thing I'd try is the reverse-iteration stuff. If you can get an existing test to fail reliably with that, you're done.

[srhines]

https://reviews.llvm.org/D59807 has the fix for the nondeterminism. Thanks for the hints about the reverse iteration order. That helps make it more likely to fail deterministically, but it still runs a small chance of "passing" if the fix isn't there.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

public:
   SDValue getCopyFromRegs(const Value *V, Type *Ty);
 
   /// If we have dangling debug info that describes \p Variable, or an
   /// overlapping part of variable considering the \p Expr, then this method
   /// will drop that debug info as it isn't valid any longer.
   void dropDanglingDebugInfo(const DILocalVariable *Variable,
                              const DIExpression *Expr);
 
-  // If we saw an earlier dbg_value referring to V, generate the debug data
-  // structures now that we've seen its definition.
+  /// If we saw an earlier dbg_value referring to V, generate the debug data
+  /// structures now that we've seen its definition.
   void resolveDanglingDebugInfo(const Value *V, SDValue Val);
 
-  // For a given Value, attempt to create and record a SDDbgValue in the
-  // SelectionDAG.
+  /// For the given dangling debuginfo record, perform last-ditch efforts to
+  /// resolve the debuginfo to something that is represented in this DAG. If
+  /// this cannot be done, produce an Undef debug value record.
+  void salvageUnresolvedDbgValue(DanglingDebugInfo &DDI);
+
+  /// For a given Value, attempt to create and record a SDDbgValue in the
+  /// SelectionDAG.
   bool handleDebugValue(const Value *V, DILocalVariable *Var,
                         DIExpression *Expr, DebugLoc CurDL,
                         DebugLoc InstDL, unsigned Order);
 
+  /// Evict any dangling debug information, attempting to salvage it first.
+  void resolveOrClearDbgInfo();
+
   SDValue getValue(const Value *V);
   bool findValue(const Value *V) const;
 
   /// Return the SDNode for the specified IR value if it exists.
   SDNode *getNodeForIRValue(const Value *V) {
     if (NodeMap.find(V) == NodeMap.end())
       return nullptr;
     return NodeMap[V].getNode();

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MachineValueType.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetIntrinsicInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <cstring>
 #include <iterator>
 #include <limits>
 #include <numeric>
if (DanglingVariable == Variable && Expr->fragmentsOverlap(DanglingExpr)) {
       LLVM_DEBUG(dbgs() << "Dropping dangling debug info for " << *DI << "\n");
       return true;
     }
     return false;
   };
 
   for (auto &DDIMI : DanglingDebugInfoMap) {
     DanglingDebugInfoVector &DDIV = DDIMI.second;
+
+    // If debug info is to be dropped, run it through final checks to see
+    // whether it can be salvaged.
+    for (auto &DDI : DDIV)
+      if (isMatchingDbgValue(DDI))
+        salvageUnresolvedDbgValue(DDI);
+
     DDIV.erase(remove_if(DDIV, isMatchingDbgValue), DDIV.end());
   }
 }
 
 // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
 // generate the debug data structures now that we've seen its definition.
 void SelectionDAGBuilder::resolveDanglingDebugInfo(const Value *V,
                                                    SDValue Val) {
if (Val.getNode()) {
                    << "changing SDNodeOrder from " << DbgSDNodeOrder << " to "
                    << ValSDNodeOrder << "\n");
         SDV = getDbgValue(Val, Variable, Expr, dl,
                           std::max(DbgSDNodeOrder, ValSDNodeOrder));
         DAG.AddDbgValue(SDV, Val.getNode(), false);
       } else
         LLVM_DEBUG(dbgs() << "Resolved dangling debug info for " << *DI
                           << "in EmitFuncArgumentDbgValue\n");
-    } else
+    } else {
       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
+      auto Undef =
+          UndefValue::get(DDI.getDI()->getVariableLocation()->getType());
+      auto SDV =
+          DAG.getConstantDbgValue(Variable, Expr, Undef, dl, DbgSDNodeOrder);
+      DAG.AddDbgValue(SDV, nullptr, false);
+    }
   }
   DDIV.clear();
 }
 
+void SelectionDAGBuilder::salvageUnresolvedDbgValue(DanglingDebugInfo &DDI) {
+  Value *V = DDI.getDI()->getValue();
+  DILocalVariable *Var = DDI.getDI()->getVariable();
+  DIExpression *Expr = DDI.getDI()->getExpression();
+  DebugLoc DL = DDI.getdl();
+  DebugLoc InstDL = DDI.getDI()->getDebugLoc();
+  unsigned SDOrder = DDI.getSDNodeOrder();
+
+  // Currently we consider only dbg.value intrinsics -- we tell the salvager
+  // that DW_OP_stack_value is desired.
+  assert(isa<DbgValueInst>(DDI.getDI()));
+  bool StackValue = true;
+
+  // Can this Value can be encoded without any further work?
+  if (handleDebugValue(V, Var, Expr, DL, InstDL, SDOrder))
+    return;
+
+  // Attempt to salvage back through as many instructions as possible. Bail if
+  // a non-instruction is seen, such as a constant expression or global
+  // variable. FIXME: Further work could recover those too.
+  while (isa<Instruction>(V)) {
+    Instruction &VAsInst = *cast<Instruction>(V);
+    DIExpression *NewExpr = salvageDebugInfoImpl(VAsInst, Expr, StackValue);
+
+    // If we cannot salvage any further, and haven't yet found a suitable debug
+    // expression, bail out.
+    if (!NewExpr)
+      break;
+
+    // New value and expr now represent this debuginfo.
+    V = VAsInst.getOperand(0);
+    Expr = NewExpr;
+
+    // Some kind of simplification occurred: check whether the operand of the
+    // salvaged debug expression can be encoded in this DAG.
+    if (handleDebugValue(V, Var, Expr, DL, InstDL, SDOrder)) {
+      LLVM_DEBUG(dbgs() << "Salvaged debug location info for:\n  "
+                        << DDI.getDI() << "\nBy stripping back to:\n  " << V);
+      return;
+    }
+  }
+
+  // This was the final opportunity to salvage this debug information, and it
+  // couldn't be done. Place an undef DBG_VALUE at this location to terminate
+  // any earlier variable location.
+  auto Undef = UndefValue::get(DDI.getDI()->getVariableLocation()->getType());
+  auto SDV = DAG.getConstantDbgValue(Var, Expr, Undef, DL, SDNodeOrder);
+  DAG.AddDbgValue(SDV, nullptr, false);
+
+  LLVM_DEBUG(dbgs() << "Dropping debug value info for:\n  " << DDI.getDI()
+                    << "\n");
+  LLVM_DEBUG(dbgs() << "  Last seen at:\n    " << *DDI.getDI()->getOperand(0)
+                    << "\n");
+}
+
 bool SelectionDAGBuilder::handleDebugValue(const Value *V, DILocalVariable *Var,
                                            DIExpression *Expr, DebugLoc dl,
                                            DebugLoc InstDL, unsigned Order) {
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   SDDbgValue *SDV;
   if (isa<ConstantInt>(V) || isa<ConstantFP>(V) || isa<UndefValue>(V) ||
       isa<ConstantPointerNull>(V)) {
     SDV = DAG.getConstantDbgValue(Var, Expr, V, dl, SDNodeOrder);
if (VMI != FuncInfo.ValueMap.end()) {
       }
       return true;
     }
   }
 
   return false;
 }
 
+void SelectionDAGBuilder::resolveOrClearDbgInfo() {
+  // Try to fixup any remaining dangling debug info -- and drop it if we can't.
+  for (auto &Pair : DanglingDebugInfoMap)
+    for (auto &DDI : Pair.getSecond())
+      salvageUnresolvedDbgValue(DDI);
+  clearDanglingDebugInfo();
+}
+
 /// getCopyFromRegs - If there was virtual register allocated for the value V
 /// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
 SDValue SelectionDAGBuilder::getCopyFromRegs(const Value *V, Type *Ty) {
   DenseMap<const Value *, unsigned>::iterator It = FuncInfo.ValueMap.find(V);
   SDValue Result;
 
   if (It != FuncInfo.ValueMap.end()) {
     unsigned InReg = It->second;
case Intrinsic::dbg_value: {
     const Value *V = DI.getValue();
     if (!V)
       return nullptr;
 
     if (handleDebugValue(V, Variable, Expression, DI.getDebugLoc(), dl,
         SDNodeOrder))
       return nullptr;
 
-    // TODO: When we get here we will either drop the dbg.value completely, or
-    // we try to move it forward by letting it dangle for awhile. So we should
-    // probably add an extra DbgValue to the DAG here, with a reference to
-    // "noreg", to indicate that we have lost the debug location for the
-    // variable.
-
-    if (!V->use_empty() ) {
-      // Do not call getValue(V) yet, as we don't want to generate code.
-      // Remember it for later.
-      DanglingDebugInfoMap[V].emplace_back(&DI, dl, SDNodeOrder);
-      return nullptr;
-    }
+    // TODO: Dangling debug info will eventually either be resolved or produce
+    // an Undef DBG_VALUE. However in the resolution case, a gap may appear
+    // between the original dbg.value location and its resolved DBG_VALUE, which
+    // we should ideally fill with an extra Undef DBG_VALUE.
 
-    LLVM_DEBUG(dbgs() << "Dropping debug location info for:\n  " << DI << "\n");
-    LLVM_DEBUG(dbgs() << "  Last seen at:\n    " << *V << "\n");
+    DanglingDebugInfoMap[V].emplace_back(&DI, dl, SDNodeOrder);
     return nullptr;
   }
 
   case Intrinsic::eh_typeid_for: {
     // Find the type id for the given typeinfo.
     GlobalValue *GV = ExtractTypeInfo(I.getArgOperand(0));
     unsigned TypeID = DAG.getMachineFunction().getTypeIDFor(GV);
     Res = DAG.getConstant(TypeID, sdl, MVT::i32);

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
   for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
     if (!ElidedArgCopyInstrs.count(&*I))
       SDB->visit(*I);
   }
 
   // Make sure the root of the DAG is up-to-date.
   CurDAG->setRoot(SDB->getControlRoot());
   HadTailCall = SDB->HasTailCall;
+  SDB->resolveOrClearDbgInfo();
   SDB->clear();
 
   // Final step, emit the lowered DAG as machine code.
   CodeGenAndEmitDAG();
 }
 
 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
   SmallPtrSet<SDNode*, 16> VisitedNodes;

llvm/trunk/test/DebugInfo/X86/sdag-dangling-dbgvalue.ll

entry3:
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !36, metadata !DIExpression()), !dbg !38
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !35, metadata !DIExpression()), !dbg !37
   ret i32 add (i32 ptrtoint (%struct.SS* @S to i32), i32 ptrtoint (%struct.SS* @S to i32)), !dbg !39
 }
 
 ; Verify that the def comes before the for bar4.
 define i32 @test4() local_unnamed_addr #0 !dbg !40 {
 ; CHECK-LABEL: bb.0.entry4
+; CHECK-NEXT:    DBG_VALUE $noreg, $noreg, ![[FOO4]], !DIExpression()
 ; CHECK-NEXT:    DBG_VALUE 0, $noreg, ![[FOO4]], !DIExpression()
 ; CHECK-NEXT:    [[REG4:%[0-9]+]]:gr64 =
 ; CHECK-NEXT:    DBG_VALUE [[REG4]], $noreg, ![[BAR4]], !DIExpression()
 entry4:
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !42, metadata !DIExpression()), !dbg !44
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !43, metadata !DIExpression()), !dbg !45
   call void @llvm.dbg.value(metadata %struct.SS* null, metadata !42, metadata !DIExpression()), !dbg !44
   ret i32 ptrtoint (%struct.SS* @S to i32), !dbg !46
 }
 
 ; Verify that we do not get a DBG_VALUE that maps foo5 to @S here.
 define i32 @test5() local_unnamed_addr #0 !dbg !47 {
 ; CHECK-LABEL: bb.0.entry5:
+; CHECK-NEXT:    DBG_VALUE $noreg, $noreg, ![[FOO5]], !DIExpression()
 ; CHECK-NEXT:    DBG_VALUE 0, $noreg, ![[FOO5]], !DIExpression()
 ; CHECK-NEXT:    [[REG5:%[0-9]+]]:gr64 =
 ; CHECK-NEXT:    DBG_VALUE [[REG5]], $noreg, ![[BAR5]], !DIExpression()
 ; CHECK-NOT:     DBG_VALUE [[REG5]], $noreg, ![[FOO5]], !DIExpression()
 ; CHECK:         RET
 entry5:
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !49, metadata !DIExpression()), !dbg !51
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !50, metadata !DIExpression()), !dbg !52

llvm/trunk/test/DebugInfo/X86/sdag-ir-salvage.ll

+; RUN: llc -mtriple=x86_64-unknown-unknown -start-after=codegenprepare -stop-before expand-isel-pseudos %s -o -  | FileCheck %s
+
+; Test that the dbg.value for %baz, which doesn't exist in the 'next' bb,
+; can be salvaged back to the underlying argument vreg.
+
+; CHECK:       ![[AAAVAR:.*]] = !DILocalVariable(name: "aaa",
+; CHECK-LABEL: bb.1.next:
+; CHECK:       DBG_VALUE %{{[0-9]+}}, $noreg, ![[AAAVAR]]
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-linux-gnu"
+
+define i8 @f(i32* %foo) local_unnamed_addr !dbg !6 {
+entry:
+  %bar = getelementptr i32, i32* %foo, i32 4
+  %baz = bitcast i32* %bar to i8*
+  %quux = load i8, i8* %baz
+  br label %next
+
+next:                                             ; preds = %entry
+  tail call void @llvm.dbg.value(metadata i8* %baz, metadata !15, metadata !DIExpression()), !dbg !30
+  %xyzzy = add i8 %quux, 123
+  br label %fin
+
+fin:                                              ; preds = %next
+  %trains = getelementptr i32, i32* %foo, i32 3
+  %planes = bitcast i32* %trains to i8*
+  %cars = load i8, i8* %planes
+  %ret = add i8 %xyzzy, %cars
+  ret i8 %ret
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+attributes #0 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!25, !26, !27, !28}
+!llvm.ident = !{!29}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "test.c", directory: ".")
+!2 = !{}
+!6 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 18, type: !7, scopeLine: 19, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !14)
+!7 = !DISubroutineType(types: !8)
+!8 = !{!13}
+!13 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_unsigned)
+!14 = !{!15}
+!15 = !DILocalVariable(name: "aaa", scope: !6, file: !1, line: 18, type: !13)
+!25 = !{i32 2, !"Dwarf Version", i32 4}
+!26 = !{i32 2, !"Debug Info Version", i32 3}
+!27 = !{i32 1, !"wchar_size", i32 4}
+!28 = !{i32 7, !"PIC Level", i32 2}
+!29 = !{!"clang"}
+!30 = !DILocation(line: 18, column: 14, scope: !6)