Avoid the propagation of debug locations in SelectionDAG via CSE

[wolfgangp]

Summary

When SelectionDAG performs CSE it is possible that the context's source location is different from that of the selected node. This can lead to incorrect line number records. This patch proposes to update the debug location to the one that occurs earlier in the instruction sequence. This is in order to address PR21006 (oscillating line number records due to CSE performed on constant pool loads).

[sdmitrouk]

Hi,

Are there any reasons to implement the check in separate function instead of
changing 3-argument overload of SelectionDAG::FindNodeOrInsertPos to handle
nodes of all kinds (that would require updating its comment a bit)? If I
counted correctly, the changes cover 20 of 27 uses of that overload and it might
make sense to keep debug location erasure in one place to make it less
error-prone, unless there are reasons not to do this.

Regards,
Sergey

[wolfgangp]

In D12094#226510, @sdmitrouk wrote:

Hi,

Are there any reasons to implement the check in separate function instead of
changing 3-argument overload of SelectionDAG::FindNodeOrInsertPos to handle
nodes of all kinds (that would require updating its comment a bit)? If I
counted correctly, the changes cover 20 of 27 uses of that overload and it might
make sense to keep debug location erasure in one place to make it less
error-prone, unless there are reasons not to do this.

Regards,
Sergey

This is what I intended to do at first, but there are several contexts where the call to FindNodeOrInsertPos() is used as a query rather than with an intent to eliminate common subexpressions (e.g. all 3 versions of FindModifiedNodeSlot(), and getNodeIfExists()). It would be undesirable to possibly null out the debugLoc in those contexts, and indeed one llvm test broke by degrading the line number info when I did it this way.
That's not to say filtering the debugLoc couldn't be centralized but it would probably require some rework of the Constant node handling as well. I'm certainly open to that.

The other reason is more stylistic. I'm uncomfortable with having a function called "FindNodeOrInsertPos()", which is meant to retrieve something, have a significant side effect such as nulling out the debug location, when it's not well-defined inside the function how the result is used.

[sdmitrouk]

In D12094#226720, @wolfgangp wrote:

This is what I intended to do at first, but there are several contexts where the call to FindNodeOrInsertPos() is used as a query rather than with an intent to eliminate common subexpressions (e.g. all 3 versions of FindModifiedNodeSlot(), and getNodeIfExists()). It would be undesirable to possibly null out the debugLoc in those contexts, and indeed one llvm test broke by degrading the line number info when I did it this way.
That's not to say filtering the debugLoc couldn't be centralized but it would probably require some rework of the Constant node handling as well. I'm certainly open to that.

Not sure about getNodeIfExists(), here is part of DAGCombiner:

if (const auto *BinNode = dyn_cast<BinaryWithFlagsSDNode>(N)) {
  CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), Ops,
                                &BinNode->Flags);
} else {
  CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), Ops);
}

Regarding FindModifiedNodeSlot():

// See if the modified node already exists.
void *InsertPos = nullptr;
if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
  return Existing;

So, if new node already exists, reuse it in different place. Looks like we need to drop old debug location here as well.

I guess the rest are from functions that create constant nodes.

As for the failing test, maybe it's relying on something it shouldn't? In general, cached nodes are queried for reuse, I'm not sure there are other valid cases, that's why I'm a bit suspicious about leaving some cases unhandled.

The other reason is more stylistic. I'm uncomfortable with having a function called "FindNodeOrInsertPos()", which is meant to retrieve something, have a significant side effect such as nulling out the debug location, when it's not well-defined inside the function how the result is used.

I agree, changing naming shouldn't be a problem, if you have something suitable on your mind. The interface will differ a bit for different queries, but that's not an issue as for me.

[wolfgangp]

Thank you for your comments, Sergey. If find that if I outfit getIfExists() with a debugLoc() parameter and pass it through, the failure goes away, so I have revised the patch to update the node from within the FindNode helper, dispensing with the FilterDebugLoc() routine. I've renamed the helper routine to reflect that it updates the node and took the liberty to adjust the comment a bit.

[sdmitrouk]

Thanks for the update, LGTM with returned first line of SelectionDAG.cpp.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

1

You probably removed this by accident.

[wolfgangp]

Added back the first line of SelectionDAG.cpp, which was accidentally removed.

[wolfgangp]

In D12094#229846, @sdmitrouk wrote:

Thanks for the update, LGTM with returned first line of SelectionDAG.cpp.

Oops, thank you for noticing that and thank you for the review.

Would it be possible for you to commit this change for me? I don't have commit access yet.

[echristo]

I've made an inline comment on this, if you could reply that would be good. Please don't commit this yet.

Thanks!

-eric

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

997–1001

This is an interesting perspective. I'm not sure I agree though. Things like CSE'ing of nodes can cause attribution of expressions to a line that does an equivalent computation, but this change is going to associate the expression to a line that doesn't do the expression at all in the general case. How is this better than the current status quo?

[wolfgangp]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

997–1001

I have to agree that it's not a good solution, and the only reason I prefer it over the status quo is that I haven't been able to come up with a case where an expression is actually attributed to a line that doesn't compute it (likely the preceding line), whereas there's at least one case that suffers from the status quo (PR21006). Anecdotal evidence, I know.

[wolfgangp]

Given the concerns about nulling out the debug location here is a different attempt: We determine from the context whether the place where the node is reused is located earlier in the sequence of instructions. To this end we're using the SDNodes' IROrder which reflects the sequence of IR instructions. This required adjustment of the interface of FindNodeOrInsertPos() because we need an SDLoc instead of just a DebugLoc.

Sergey, I wasn't sure if we can subsume Constant nodes under this change, but it seemed that it's still better to null out the DebugLocation in those cases.

[sdmitrouk]

In D12094#238549, @wolfgangp wrote:

We determine from the context whether the place where the node is reused is located earlier in the sequence of instructions.

So basically among all uses of the same CSEed node this picks debug location from the earliest one? And original issue could be rephrased as: debug location of CSEed nodes is picked non-deterministically. If that's the case, this seems to be really nice change.

Sergey, I wasn't sure if we can subsume Constant nodes under this change, but it seemed that it's still better to null out the DebugLocation in those cases.

I agree, and it's safer to leave it as is, at least until counter example is provided.

[wolfgangp]

Ping...

[wolfgangp]

Ping...

Updated the test case to catch up with recent IR changes.

[echristo]

Could you do an upload with full context please? It's a bit hard to pick out bits of the selection dag changes. In general I think the idea is fine, but the default: case could use a comment while you're at it.

Thanks!

-eric

[wolfgangp]

Thanks, Eric. Uploaded full diff and added a comment to the default: case.

[echristo]

One inline comment.

Thanks!

-eric

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

853

I'm unclear why we have a default SDLoc here?

[wolfgangp]

Adressed review comment on default SDLoc() in getNodeIfExists(). This routine is used in an attempt to take advantage of existing commutative binary nodes by the DAG combiner. No reason to not update the debug location if the node is reused.

[wolfgangp]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

853

I didn't author the original code, but I see no reason to not update the DebugLoc. This routine is called from DAGCombine in an attempt to reuse a binary commutative node. Thanks for pointing this out.

[wolfgangp]

Updated diff against r265709. No additional functional changes. There is no need to patch DAGCombiner.cpp any more because of an interface change to getNodeIfExists(). Apologies for leaving this dormant for a while.

[wolfgangp]

Ping...

[echristo]

LGTM. Thanks!

-eric

include/llvm/CodeGen/SelectionDAG.h

   SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
                                void *&InsertPos);
   SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
+  static SDNode *FilterDebugLoc(SDNode *N, DebugLoc loc);
 
   void DeleteNodeNotInCSEMaps(SDNode *N);
   void DeallocateNode(SDNode *N);

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

   ID.AddInteger(GV->getType()->getAddressSpace());
   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, DL.getDebugLoc()), 0);
 
   SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
                                                       DL.getDebugLoc(), GV, VT,

 
   void* IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
 
   // Allocate the mask array for the node out of the BumpPtrAllocator, since
   // SDNode doesn't have access to it.  This memory will be "leaked" when

   AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
   void* IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
 
   CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
                                                            dl.getDebugLoc(),

 
   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
 
   SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
                                                       dl.getDebugLoc(),

   AddNodeIDNode(ID, Opcode, getVTList(VT), None);
   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, DL.getDebugLoc()), 0);
 
   SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
                                          DL.getDebugLoc(), getVTList(VT));

     AddNodeIDNode(ID, Opcode, VTs, Ops);
     void *IP = nullptr;
     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
-      return SDValue(E, 0);
+      return SDValue(FilterDebugLoc(E, DL.getDebugLoc()), 0);
 
     N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
                                         DL.getDebugLoc(), VTs, Operand);

     AddNodeIDFlags(ID, Opcode, Flags);
     void *IP = nullptr;
     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
-      return SDValue(E, 0);
+      return SDValue(FilterDebugLoc(E, DL.getDebugLoc()), 0);
 
     N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
 

     AddNodeIDNode(ID, Opcode, VTs, Ops);
     void *IP = nullptr;
     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
-      return SDValue(E, 0);
+      return SDValue(FilterDebugLoc(E, DL.getDebugLoc()), 0);
 
     N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
                                           DL.getDebugLoc(), VTs, N1, N2, N3);

   void* IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<AtomicSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
 
   // Allocate the operands array for the node out of the BumpPtrAllocator, since

     void *IP = nullptr;
     if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
       cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
-      return SDValue(E, 0);
+      return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
     }
 
     N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),

   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<LoadSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
   SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
                                              dl.getDebugLoc(), VTs, AM, ExtType,

   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<StoreSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
                                               dl.getDebugLoc(), VTs,

   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<StoreSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
                                               dl.getDebugLoc(), VTs,

   ID.AddInteger(ST->getPointerInfo().getAddrSpace());
   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
 
   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
                                               dl.getDebugLoc(), VTs, AM,

   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
   SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
                                              dl.getDebugLoc(), Ops, 4, VTs,

   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
   SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
                                                     dl.getDebugLoc(), Ops, 4,

   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
   MaskedGatherSDNode *N = 
     new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),

   void *IP = nullptr;
   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
     cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
-    return SDValue(E, 0);
+    return SDValue(FilterDebugLoc(E, dl.getDebugLoc()), 0);
   }
   SDNode *N =
     new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),

     void *IP = nullptr;
 
     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
-      return SDValue(E, 0);
+      return SDValue(FilterDebugLoc(E, DL.getDebugLoc()), 0);
 
     N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
                                    VTs, Ops);

     AddNodeIDNode(ID, Opcode, VTList, Ops);
     void *IP = nullptr;
     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
-      return SDValue(E, 0);
+      return SDValue(FilterDebugLoc(E, DL.getDebugLoc()), 0);
 
     if (NumOps == 1) {
       N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),

   return N;
 }
 
+SDNode *SelectionDAG::FilterDebugLoc(SDNode *N, DebugLoc Loc)
+{
+  if (N->getDebugLoc() != Loc)
+    N->setDebugLoc(DebugLoc());
+  return N;
+}
+
 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
 /// the line number information on the merged node since it is not possible to
 /// preserve the information that operation is associated with multiple lines.

test/DebugInfo/isel-cse-line.ll

+; RUN: llc -filetype=asm -fast-isel=false -O0 < %s | FileCheck %s
+;
+; Generated by:
+; clang -emit-llvm -S -g test.cpp
+
+; typedef double         fp_t;
+; typedef unsigned long  int_t;
+;
+; int_t glb_start      = 17;
+; int_t glb_end        = 42;
+; 
+; int main()
+; {
+;   int_t start = glb_start;
+;   int_t end   = glb_end;
+; 
+;   fp_t dbl_start = (fp_t) start;
+;   fp_t dbl_end   = (fp_t) end;
+; 
+;   return 0;
+; }
+
+; SelectionDAG performs CSE on constant pool loads. Make sure line numbers
+; from such nodes are not propagated. Doing so results in oscillating line numbers.
+
+; CHECK: .loc 1 12
+; CHECK: .loc 1 13
+; CHECK-NOT: .loc 1 12
+ 
+; ModuleID = 't.cpp'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@glb_start = global i64 17, align 8
+@glb_end = global i64 42, align 8
+
+; Function Attrs: nounwind uwtable
+define i32 @main() {
+  %1 = alloca i32, align 4
+  %start = alloca i64, align 8
+  %end = alloca i64, align 8
+  %dbl_start = alloca double, align 8
+  %dbl_end = alloca double, align 8
+  store i32 0, i32* %1
+  call void @llvm.dbg.declare(metadata i64* %start, metadata !19, metadata !20), !dbg !21
+  %2 = load i64, i64* @glb_start, align 8, !dbg !22
+  store i64 %2, i64* %start, align 8, !dbg !21
+  call void @llvm.dbg.declare(metadata i64* %end, metadata !23, metadata !20), !dbg !24
+  %3 = load i64, i64* @glb_end, align 8, !dbg !25
+  store i64 %3, i64* %end, align 8, !dbg !24
+  call void @llvm.dbg.declare(metadata double* %dbl_start, metadata !26, metadata !20), !dbg !27
+  %4 = load i64, i64* %start, align 8, !dbg !28
+  %5 = uitofp i64 %4 to double, !dbg !28
+  store double %5, double* %dbl_start, align 8, !dbg !27
+  call void @llvm.dbg.declare(metadata double* %dbl_end, metadata !29, metadata !20), !dbg !30
+  %6 = load i64, i64* %end, align 8, !dbg !31
+  %7 = uitofp i64 %6 to double, !dbg !31
+  store double %7, double* %dbl_end, align 8, !dbg !30
+  ret i32 0, !dbg !32
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!16, !17}
+!llvm.ident = !{!18}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.8.0 (trunk 244974)", isOptimized: false, runtimeVersion: 0, emissionKind: 1, enums: !2, retainedTypes: !3, subprograms: !6, globals: !11)
+!1 = !DIFile(filename: "t.cpp", directory: "/home/user")
+!2 = !{}
+!3 = !{!4}
+!4 = !DIDerivedType(tag: DW_TAG_typedef, name: "fp_t", file: !1, line: 1, baseType: !5)
+!5 = !DIBasicType(name: "double", size: 64, align: 64, encoding: DW_ATE_float)
+!6 = !{!7}
+!7 = !DISubprogram(name: "main", scope: !1, file: !1, line: 7, type: !8, isLocal: false, isDefinition: true, scopeLine: 8, flags: DIFlagPrototyped, isOptimized: false, function: i32 ()* @main, variables: !2)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10}
+!10 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!11 = !{!12, !15}
+!12 = !DIGlobalVariable(name: "glb_start", scope: !0, file: !1, line: 4, type: !13, isLocal: false, isDefinition: true, variable: i64* @glb_start)
+!13 = !DIDerivedType(tag: DW_TAG_typedef, name: "int_t", file: !1, line: 2, baseType: !14)
+!14 = !DIBasicType(name: "long unsigned int", size: 64, align: 64, encoding: DW_ATE_unsigned)
+!15 = !DIGlobalVariable(name: "glb_end", scope: !0, file: !1, line: 5, type: !13, isLocal: false, isDefinition: true, variable: i64* @glb_end)
+!16 = !{i32 2, !"Dwarf Version", i32 4}
+!17 = !{i32 2, !"Debug Info Version", i32 3}
+!18 = !{!"clang version 3.8.0 (trunk 244974)"}
+!19 = !DILocalVariable(name: "start", scope: !7, file: !1, line: 9, type: !13)
+!20 = !DIExpression()
+!21 = !DILocation(line: 9, column: 9, scope: !7)
+!22 = !DILocation(line: 9, column: 17, scope: !7)
+!23 = !DILocalVariable(name: "end", scope: !7, file: !1, line: 10, type: !13)
+!24 = !DILocation(line: 10, column: 9, scope: !7)
+!25 = !DILocation(line: 10, column: 17, scope: !7)
+!26 = !DILocalVariable(name: "dbl_start", scope: !7, file: !1, line: 12, type: !4)
+!27 = !DILocation(line: 12, column: 8, scope: !7)
+!28 = !DILocation(line: 12, column: 27, scope: !7)
+!29 = !DILocalVariable(name: "dbl_end", scope: !7, file: !1, line: 13, type: !4)
+!30 = !DILocation(line: 13, column: 8, scope: !7)
+!31 = !DILocation(line: 13, column: 27, scope: !7)
+!32 = !DILocation(line: 15, column: 3, scope: !7)