[SelectionDAG] Support multiple dangling debug info for one value

[bjope]

Summary

When building the selection DAG we sometimes need to postpone
the handling of a dbg.value until the value it should refer to
is created. This is done by using the DanglingDebugInfoMap.
In the past this map has been limited to hold one dangling
dbg.value per value. This patch removes that restriction.

[rnk]

Thanks, this seems like an important fix. :) Tons of dbg.values for redundant inlined copies of this use the same base value.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

120 ↗

(On Diff #138861)

Embedding SmallVector in DenseMap is usually an efficiency trap. DenseMap stores keys and values in the table, not in separate allocations, so the value of every unfilled hashtable entry is wasted. Even then, filled slots typically have one dbg.value.

TinyPtrVector was created for this use case, but it looks like the elements are not pointers so it will not work.

I guess I'd suggest using std::vector or SmallVector<DangingDebugInfo, 0> to minimize wasted inline storage.

[aprantl]

Thanks! LGTM with Reid's comment addressed.

[bjope]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

120 ↗

(On Diff #138861)

Thanks a lot for the feedback. I was a little bit worried about this part. I haven't spent any time on optimizing it really, and this first draft was aiming at getting it working in some simple way.

Now when I got the feedback that this patch is on track regarding the functionality I will go on doing some tests regarding impact on compile speed/memory consumption. After all, these problems were seen when analysing https://bugs.llvm.org/show_bug.cgi?id=36417, so it would be a pity if we end up with bad compilation performance again when solving this problem.

[rnk]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

120 ↗

(On Diff #138861)

That's always possible, but I suspect any perf degradation will come from the extra DBG_VALUE MachineInstrs inserted after this pass, and not this data structure. Anyway, SmallVector 0 is three pointers big, and DanglingDbgInfo is three, so in the common case, there's not much change.

One way to build confidence that this isn't introducing a major regression is to measure the time to compile the optimized sqlite3.c amalgamation with debug info before and after your change. You can use perf -r 5 on Linux to get error bars to get a sense of how precise your comparison is, and whether it's in the noise or not.

[bjope]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

120 ↗

(On Diff #138861)

std:vector seems to use less heap (compared to SmallVector) when running the small test/DebugInfo/X86/sdag-dangling-dbgvalue.ll test case.

The sqlite3.c test does not seem to result in any dangling debug info during the initial SDAG build, so this patch has no impact really.

When considering C++ and this pointers, as mentioned earlier by someone, we do not get any dangling debug info afaict. The this pointer will be an input arguement to the function, so the value is selected before any dbg.value instructions that reference it.

Normally the amount of dangling debug info should be quite small (there could be some nasty code out there so you never now for the general case). I do not think memory consumption should be a problem. The costly part (CPU wise) is probably the linear search in SelectionDAGBuilder::dropDanglingDebugInfo to find all dangling debug info that needs to be dropped. Now we can have more dangling debug info nodes to inspect, although the complexity is the same.

I'll will replace the the SmallVector by a std::vector and then I assume that I can land this.

[bjope]

DanglingDebugInfoVector is not a std::vector.
Rebased to latest on trunk.

[aprantl]

To see any difference you probably need to compile a heavily templated C++ program with lots of inlining. That said, I don't think that this patch will have a huge performance impact even there, since we don't propagate dbg.values beyond basic blocks outside of their lexical scopes.

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

public:
     DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO)
         : DI(di), dl(std::move(DL)), SDNodeOrder(SDNO) {}
 
     const DbgValueInst* getDI() { return DI; }
     DebugLoc getdl() { return dl; }
     unsigned getSDNodeOrder() { return SDNodeOrder; }
   };
 
+  /// DanglingDebugInfoVector - Helper type for DanglingDebugInfoMap.
+  typedef std::vector<DanglingDebugInfo> DanglingDebugInfoVector;
+
   /// DanglingDebugInfoMap - 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*, DanglingDebugInfo> DanglingDebugInfoMap;
+  DenseMap<const Value*, DanglingDebugInfoVector> DanglingDebugInfoMap;
 
 public:
   /// PendingLoads - Loads are not emitted to the program immediately.  We bunch
   /// them up and then emit token factor nodes when possible.  This allows us to
   /// get simple disambiguation between loads without worrying about alias
   /// analysis.
   SmallVector<SDValue, 8> PendingLoads;
 

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

 #define HANDLE_INST(NUM, OPCODE, CLASS) \
     case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break;
 #include "llvm/IR/Instruction.def"
   }
 }
 
 void SelectionDAGBuilder::dropDanglingDebugInfo(const DILocalVariable *Variable,
                                                 const DIExpression *Expr) {
-  SmallVector<const Value *, 4> ToRemove;
-  for (auto &DMI : DanglingDebugInfoMap) {
-    DanglingDebugInfo &DDI = DMI.second;
+  for (auto &DDIMI : DanglingDebugInfoMap)
+    for (auto &DDI : DDIMI.second)
       if (DDI.getDI()) {
         const DbgValueInst *DI = DDI.getDI();
         DIVariable *DanglingVariable = DI->getVariable();
         DIExpression *DanglingExpr = DI->getExpression();
         if (DanglingVariable == Variable &&
             Expr->fragmentsOverlap(DanglingExpr)) {
           DEBUG(dbgs() << "Dropping dangling debug info for " << *DI << "\n");
-        ToRemove.push_back(DMI.first);
+          DDI = DanglingDebugInfo();
         }
       }
-  }
 
-  for (auto V : ToRemove)
-    DanglingDebugInfoMap[V] = DanglingDebugInfo();
-}
-
 // 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) {
-  DanglingDebugInfo &DDI = DanglingDebugInfoMap[V];
+  DanglingDebugInfoVector &DDIV = DanglingDebugInfoMap[V];
+  for (auto &DDI : DDIV) {
     if (!DDI.getDI())
-    return;
+      continue;
     const DbgValueInst *DI = DDI.getDI();
     DebugLoc dl = DDI.getdl();
     unsigned ValSDNodeOrder = Val.getNode()->getIROrder();
     unsigned DbgSDNodeOrder = DDI.getSDNodeOrder();
     DILocalVariable *Variable = DI->getVariable();
     DIExpression *Expr = DI->getExpression();
     assert(Variable->isValidLocationForIntrinsic(dl) &&
            "Expected inlined-at fields to agree");
     SDDbgValue *SDV;
     if (Val.getNode()) {
       if (!EmitFuncArgumentDbgValue(V, Variable, Expr, dl, false, Val)) {
         DEBUG(dbgs() << "Resolve dangling debug info [order=" << DbgSDNodeOrder
               << "] for:\n  " << *DI << "\n");
         DEBUG(dbgs() << "  By mapping to:\n    "; Val.dump());
         // Increase the SDNodeOrder for the DbgValue here to make sure it is
         // inserted after the definition of Val when emitting the instructions
         // after ISel. An alternative could be to teach
         // ScheduleDAGSDNodes::EmitSchedule to delay the insertion properly.
         DEBUG(if (ValSDNodeOrder > DbgSDNodeOrder)
                 dbgs() << "changing SDNodeOrder from " << DbgSDNodeOrder
                        << " to " << ValSDNodeOrder << "\n");
         SDV = getDbgValue(Val, Variable, Expr, dl,
                           std::max(DbgSDNodeOrder, ValSDNodeOrder));
         DAG.AddDbgValue(SDV, Val.getNode(), false);
       } else
         DEBUG(dbgs() << "Resolved dangling debug info for " << *DI
               << "in EmitFuncArgumentDbgValue\n");
     } else
       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
-  DanglingDebugInfoMap[V] = DanglingDebugInfo();
+  }
+  DanglingDebugInfoMap[V].clear();
 }
 
 /// 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;
 
case Intrinsic::dbg_value: {
     // 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.
       DanglingDebugInfo DDI(&DI, dl, SDNodeOrder);
-      DanglingDebugInfoMap[V] = DDI;
+      DanglingDebugInfoMap[V].push_back(DDI);
       return nullptr;
     }
 
     DEBUG(dbgs() << "Dropping debug location info for:\n  " << DI << "\n");
     DEBUG(dbgs() << "  Last seen at:\n    " << *V << "\n");
     return nullptr;
   }
 

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

 ; CHECK:  ![[FOO1:.*]] = !DILocalVariable(name: "foo1"
 ; CHECK:  ![[BAR1:.*]] = !DILocalVariable(name: "bar1"
 ; CHECK:  ![[FOO2:.*]] = !DILocalVariable(name: "foo2"
 ; CHECK:  ![[BAR2:.*]] = !DILocalVariable(name: "bar2"
 ; CHECK:  ![[FOO3:.*]] = !DILocalVariable(name: "bar3"
 ; CHECK:  ![[BAR3:.*]] = !DILocalVariable(name: "foo3"
 ; CHECK:  ![[FOO4:.*]] = !DILocalVariable(name: "foo4"
 ; CHECK:  ![[BAR4:.*]] = !DILocalVariable(name: "bar4"
-; CHECK:  ![[FOO5:.*]] = !DILocalVariable(name: "bar5"
-; CHECK:  ![[BAR5:.*]] = !DILocalVariable(name: "foo5"
+; CHECK:  ![[BAR5:.*]] = !DILocalVariable(name: "bar5"
+; CHECK:  ![[FOO5:.*]] = !DILocalVariable(name: "foo5"
 
 
 source_filename = "sdag-dangling-dbgvalue.c"
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.4.0"
 
 %struct.SS = type { i32, i32 }
 
 @S = global %struct.SS { i32 23, i32 -17 }, align 4, !dbg !0
 
 ; Verify that the def comes before the debug-use for foo1.
 ; TODO: Currently dbg.value for bar1 is dropped(?), is that expected?
 define i32 @test1() local_unnamed_addr #0 !dbg !17 {
 ; CHECK-LABEL: bb.0.entry1
 ; CHECK-NEXT:    [[REG1:%[0-9]+]]:gr64 =
 ; CHECK-NEXT:    DBG_VALUE debug-use [[REG1]], debug-use $noreg, ![[FOO1]], !DIExpression()
 entry1:
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !20, metadata !DIExpression()), !dbg !23
   call void @llvm.dbg.value(metadata %struct.SS* null, metadata !22, metadata !DIExpression()), !dbg !24
   ret i32 ptrtoint (%struct.SS* @S to i32), !dbg !25
 }
 
-; Verify that the def comes before the debug-use for bar2.
-; TODO: Currently dbg.value for foo2 is dropped. Seems to be a bug. The
-;       SelectionDAGBuilder should support several dangling dbg.value for the
-;       same value.
+; Verify that the def comes before the debug-use for foo2 and bar2.
 define i32 @test2() local_unnamed_addr #0 !dbg !26 {
 ; CHECK-LABEL: bb.0.entry2
 ; CHECK-NEXT:    [[REG2:%[0-9]+]]:gr64 =
+; CHECK-NEXT:    DBG_VALUE debug-use [[REG2]], debug-use $noreg, ![[FOO2]], !DIExpression()
 ; CHECK-NEXT:    DBG_VALUE debug-use [[REG2]], debug-use $noreg, ![[BAR2]], !DIExpression()
 entry2:
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !28, metadata !DIExpression()), !dbg !30
   call void @llvm.dbg.value(metadata %struct.SS* @S, metadata !29, metadata !DIExpression()), !dbg !31
   ret i32 add (i32 ptrtoint (%struct.SS* @S to i32), i32 ptrtoint (%struct.SS* @S to i32)), !dbg !32
 }
 
-; Verify that the def comes before the debug-use for foo3.
-; TODO: Currently dbg.value for bar3 is dropped. Seems to be a bug. The
-;       SelectionDAGBuilder should support several dangling dbg.value for the
-;       same value.
+; Verify that the def comes before the debug-use for foo3 and bar3.
 define i32 @test3() local_unnamed_addr #0 !dbg !33 {
 ; CHECK-LABEL: bb.0.entry3
 ; CHECK-NEXT:    [[REG3:%[0-9]+]]:gr64 =
+; CHECK-NEXT:    DBG_VALUE debug-use [[REG3]], debug-use $noreg, ![[BAR3]], !DIExpression()
 ; CHECK-NEXT:    DBG_VALUE debug-use [[REG3]], debug-use $noreg, ![[FOO3]], !DIExpression()
 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 debug-use for bar4.
 ; TODO: Currently dbg.value for foo4 is dropped. It is set to null and not
 ;       used. Just like in test1 it can be discussed if there should be a
 ;       DBG_VALUE for foo4 here.
 define i32 @test4() local_unnamed_addr #0 !dbg !40 {
 ; CHECK-LABEL: bb.0.entry4
 ; CHECK-NEXT:    [[REG4:%[0-9]+]]:gr64 =
 ; CHECK-NEXT:    DBG_VALUE debug-use [[REG4]], debug-use $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.
-; TODO: At the moment we do not get any DBG_VALUE at all here. If
-;       SelectionDAGBuilder should support several dangling dbg.value for the
-;       same value it would be possible to at least get a DBG_VALUE for
-;       bar5.
 ; TODO: foo5 is set to null, and it is not really used. Just like in test1 it
 ;       can be discussed if there should be a DBG_VALUE for foo5 here.
 define i32 @test5() local_unnamed_addr #0 !dbg !47 {
 ; CHECK-LABEL: bb.0.entry5:
-; CHECK-NOT:     DBG_VALUE
+; CHECK-NEXT:    [[REG5:%[0-9]+]]:gr64 =
+; CHECK-NEXT:    DBG_VALUE debug-use [[REG5]], debug-use $noreg, ![[BAR5]], !DIExpression()
+; CHECK-NOT:     DBG_VALUE debug-use [[REG5]], debug-use $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
   call void @llvm.dbg.value(metadata %struct.SS* null, metadata !50, metadata !DIExpression()), !dbg !52
   ret i32 ptrtoint (%struct.SS* @S to i32), !dbg !53
 }