[DAG] Don't increase SDNodeOrder for dbg.value/declare.

[uabelho]

Summary

The SDNodeOrder is saved in the IROrder field in the SDNode, and this
field may affects scheduling. Thus, letting dbg.value/declare increase
the order numbers may in turn affect scheduling.

Because of this change we also need to update the code deciding when
dbg values should be output, in ScheduleDAGSDNodes.cpp/ProcessSDDbgValues.

Dbg values now have the same order as the SDNode they are connected to,
not the following orders.

Test cases provided by Florian Hahn.

[uabelho]

Ping. Anyone has an opinion about this?

I suppose everyone agrees that dbg.values shouldn't affect code generation?

[probinson]

In D25318#568938, @uabelho wrote:

Ping. Anyone has an opinion about this?

I suppose everyone agrees that dbg.values shouldn't affect code generation?

Unquestionably, debug info should have no effect on code generation.
The question is who feels comfortable enough with SelectionDAG to have an informed opinion about fiddling with this Order stuff. Not me, that's for sure.

[MatzeB]

Yes the presence or absence of DbgValues should not affect the generated (assembly) code.

Do you have any idea why numbering the DbgValues affects the schedule? At a first glance I only found the node order used in comparisons and sorting which shouldn't be affected whether you count the DbgValues or not.

[uabelho]

In D25318#569595, @MatzeB wrote:

Yes the presence or absence of DbgValues should not affect the generated (assembly) code.

Do you have any idea why numbering the DbgValues affects the schedule? At a first glance I only found the node order used in comparisons and sorting which shouldn't be affected whether you count the DbgValues or not.

What I saw when I debugged this in my out-of-tree target was that in ScheduleDAGRRList.cpp, the IROrder is used e.g via bu_ls_rr_sort::operator() (via BURRSort, via SPQ->getNodeOrdering), affecting the order in which the instructions were placed in the final schedule, which in turn affected register allocation.

Turning on -debug printouts when compiling the example in the patch you can see that the result of the scheduler is different when the dbg.value is present.

[probinson]

Could you provide a small C/C++ source that demonstrates the problem using an in-tree target? That is, something where the generated code is different with and without -g, but applying your patch makes the difference go away. It is disappointing but not really surprising that no existing tests are affected.

[uabelho]

In D25318#570397, @probinson wrote:

Could you provide a small C/C++ source that demonstrates the problem using an in-tree target? That is, something where the generated code is different with and without -g, but applying your patch makes the difference go away. It is disappointing but not really surprising that no existing tests are affected.

I can try, but to be honest I think it's demonstrated by the two functions in the ll-file already.
By only adding a dbg.value the resulting code gets different and the difference goes away when applying the patch.

Ideally the whole output of the two functions should be compared though and not just the first pushq.

[fhahn]

I've tested your change and it solves my test case in D27261 as well. This patch is slightly nicer then mine (D27261) imo.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

977 ↗

(On Diff #73776)

I think you could use if (!isa<DbgInfoIntrinsic>(I)) here.

[aprantl]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

976 ↗

(On Diff #73776)

and a . at the end of the comment ;-)

977 ↗

(On Diff #73776)

This would be not just shorter but also more future-proof.

test/DebugInfo/Generic/selectiondag-order.ll

5 ↗

(On Diff #73776)

Is there a good reason for this? Does it make the testcase more stable?
If we only check the first instruction, sh/could we simplify the IR?

[uabelho]

Glad to see someone else also noticing this problem! :)

We've been running with this patch on our out-of-tree target for two months now without seeing
any problems with it.

I completely agree with the first two comments. I'm not sure what to do with the test case.
Any suggestions? Maybe just use the tests in https://reviews.llvm.org/D27261 instead?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

976 ↗

(On Diff #73776)

Ok!

977 ↗

(On Diff #73776)

Good point, I agree!

test/DebugInfo/Generic/selectiondag-order.ll

5 ↗

(On Diff #73776)

I simply didn't know how to write the test in the best way. I would like to check that the generated instructions are completely identical in the two cases since they only differ in a dbg.value in the input.

Now it's been a while since I saw this problem but I think I tried to reduce more but couldn't if I stil lwanted to see the diff in the output. Someone else might of course be more succesful though.

[uabelho]

Fixed the first two comments. Test case is still the same.

[fhahn]

I've uploaded two test cases in D27261, one with checks for AArch64 and one with checks for X86. I think it would be good to use those, as the test code in this review wasn't problementic on Aarch64. ideally we would have a general test that checks that all produced assembler instructions are equal, but I don't think there's a way to do that with FileCheck (and without pulling in other tools as dependency for the test).

[uabelho]

In D25318#611529, @fhahn wrote:

I've uploaded two test cases in D27261, one with checks for AArch64 and one with checks for X86. I think it would be good to use those, as the test code in this review wasn't problementic on Aarch64.

Sure! Should I simply remove "my" test and add "your" tests in this patch or how do we do it?

ideally we would have a general test that checks that all produced assembler instructions are equal, but I don't think there's a way to do that with FileCheck (and without pulling in other tools as dependency for the test).

Yep! That's kind of how we do it for our out-of-tree target and that's how I found this bug. We compile random C-programs with and without -g and verify that the .text sections in the object files are identical but of course it then pulls in other tools to be able to do that. :/

[fhahn]

In D25318#611530, @uabelho wrote:

In D25318#611529, @fhahn wrote:

I've uploaded two test cases in D27261, one with checks for AArch64 and one with checks for X86. I think it would be good to use those, as the test code in this review wasn't problementic on Aarch64.

Sure! Should I simply remove "my" test and add "your" tests in this patch or how do we do it?

Yes I think the easiest thing would be for you to just add my tests to your review.

ideally we would have a general test that checks that all produced assembler instructions are equal, but I don't think there's a way to do that with FileCheck (and without pulling in other tools as dependency for the test).

Yep! That's kind of how we do it for our out-of-tree target and that's how I found this bug. We compile random C-programs with and without -g and verify that the .text sections in the object files are identical but of course it then pulls in other tools to be able to do that. :/

There's a utility in the clang repo (clang/utils/check_cfc), but I don't think it's used in any tests and we should have CodGen tests for the patch in llvm anyways.

[uabelho]

Used the test cases from https://reviews.llvm.org/D27261

[fhahn]

Ping. Do you think the updated test cases are sufficient or would it help to provide a C example? I have one lying around somewhere, but the test case is quite ugly.

The patch only changes the Order value for debug intrinsics, so that the Order of debug intrinsics is equal to the previous non-debug instruction. The order of non-debug instructions is not affected by the change (as far as I can tell), because all non-debug instruction still have distinct Order values.

The order of debug instructions between two non-debug instructions could change though, because their order now relies on the order returned by DAG->GetDbgValues(N), but this shouldn't be a problem, right?

[fhahn]

Ping. The patch still applies to recent master and fixes a bunch of codegen inconsistencies for the LLVM test-suite. My previous comment gives some details why I think this change should be save to add

[atrick]

In principle this makes sense to me. Go ahead if there are no objections from @bogner or @aprantl.

[uabelho]

Thank you @atrick!

So, @bogner and @aprantl, no objections?

[fhahn]

Awesome, thanks for taking time to review the patch! And thanks @uabelho for your patience :)

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

 /// ProcessSDDbgValues - Process SDDbgValues associated with this node.
 static void
 ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
                    SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
                    DenseMap<SDValue, unsigned> &VRBaseMap, unsigned Order) {
   if (!N->getHasDebugValue())
     return;
 
-  // Opportunistically insert immediate dbg_value uses, i.e. those with source
-  // order number right after the N.
+  // Opportunistically insert immediate dbg_value uses, i.e. those with the same
+  // source order number as N.
   MachineBasicBlock *BB = Emitter.getBlock();
   MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
   ArrayRef<SDDbgValue*> DVs = DAG->GetDbgValues(N);
   for (unsigned i = 0, e = DVs.size(); i != e; ++i) {
     if (DVs[i]->isInvalidated())
       continue;
     unsigned DVOrder = DVs[i]->getOrder();
-    if (!Order || DVOrder == ++Order) {
+    if (!Order || DVOrder == Order) {
       MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap);
       if (DbgMI) {
         Orders.push_back(std::make_pair(DVOrder, DbgMI));
         BB->insert(InsertPos, DbgMI);
       }
       DVs[i]->setIsInvalidated();
     }
   }

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

 }
 
 void SelectionDAGBuilder::visit(const Instruction &I) {
   // Set up outgoing PHI node register values before emitting the terminator.
   if (isa<TerminatorInst>(&I)) {
     HandlePHINodesInSuccessorBlocks(I.getParent());
   }
 
+  // Increase the SDNodeOrder if dealing with a non-debug instruction.
+  if (!isa<DbgInfoIntrinsic>(I))
     ++SDNodeOrder;
 
   CurInst = &I;
 
   visit(I.getOpcode(), I);
 
   if (!isa<TerminatorInst>(&I) && !HasTailCall &&
       !isStatepoint(&I)) // statepoints handle their exports internally
     CopyToExportRegsIfNeeded(&I);

llvm/trunk/test/CodeGen/AArch64/selectiondag-order.ll

+; Check that debug intrinsics do not affect code generation.
+
+; RUN: llc < %s -mtriple=aarch64-unknown-unknown -mattr=+avx | FileCheck --check-prefix=AARCH64-CHECK %s
+
+define i64 @simulate(<2 x i32> %a) {
+entry:
+  %rand = tail call i64 @lrand48()
+  br label %body
+
+body:                                        ; preds = %body, %entry
+  %0 = phi <2 x i32> [ %add, %body ], [ zeroinitializer, %entry ]
+  %add = add <2 x i32> %0, %a
+  %rand1 = tail call i64 @lrand48() #3
+  %cmp = icmp eq i64 %rand1, 0
+  br i1 %cmp, label %end, label %body
+
+end:                                        ; preds = %body
+  %c = bitcast <2 x i32> %add to i64
+  %res = add i64 %rand, %c
+  ret i64 %res
+}
+
+; AARCH64-CHECK: simulate:
+; AARCH64-CHECK: movi d9, #0000000000000000
+; AARCH64-CHECK: bl lrand48
+; AARCH64-CHECK: mov x19, x0
+; AARCH64-CHECK: BB0_1:
+
+
+define i64 @simulateWithDebugIntrinsic(<2 x i32> %a) local_unnamed_addr  {
+entry:
+  %rand = tail call i64 @lrand48() #3
+  tail call void @llvm.dbg.value(metadata i64 %rand, i64 0, metadata !6, metadata !7), !dbg !8
+  br label %body
+
+body:                                        ; preds = %body, %entry
+  %0 = phi <2 x i32> [ %add, %body ], [ zeroinitializer, %entry ]
+  %add = add <2 x i32> %0, %a
+  %rand1 = tail call i64 @lrand48() #3
+  %cmp = icmp eq i64 %rand1, 0
+  br i1 %cmp, label %end, label %body
+
+end:                                        ; preds = %body
+  %c = bitcast <2 x i32> %add to i64
+  %res = add i64 %rand, %c
+  ret i64 %res
+}
+
+; AARCH64-CHECK: simulateWithDebugIntrinsic
+; AARCH64-CHECK: movi d9, #0000000000000000
+; AARCH64-CHECK: bl lrand48
+; AARCH64-CHECK: mov x19, x0
+; AARCH64-CHECK: BB1_1:
+
+
+define i64 @simulateWithDbgDeclare(<2 x i32> %a) local_unnamed_addr  {
+entry:
+  %rand = tail call i64 @lrand48() #3
+  tail call void @llvm.dbg.declare(metadata i64 %rand, metadata !6, metadata !7), !dbg !8
+  br label %body
+
+body:                                        ; preds = %body, %entry
+  %0 = phi <2 x i32> [ %add, %body ], [ zeroinitializer, %entry ]
+  %add = add <2 x i32> %0, %a
+  %rand1 = tail call i64 @lrand48() #3
+  %cmp = icmp eq i64 %rand1, 0
+  br i1 %cmp, label %end, label %body
+
+end:                                        ; preds = %body
+  %c = bitcast <2 x i32> %add to i64
+  %res = add i64 %rand, %c
+  ret i64 %res
+}
+
+; AARCH64-CHECK: simulateWithDbgDeclare:
+; AARCH64-CHECK: movi d9, #0000000000000000
+; AARCH64-CHECK: bl lrand48
+; AARCH64-CHECK: mov x19, x0
+; AARCH64-CHECK: BB2_1:
+
+declare i64 @lrand48()
+
+declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!3, !4}
+
+!1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, runtimeVersion: 0, emissionKind: FullDebug)
+!2 = !DIFile(filename: "test.ll", directory: ".")
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = distinct !DISubprogram(name: "simulateWithDebugIntrinsic", scope: !2, file: !2, line: 64, isLocal: false, isDefinition: true, scopeLine: 65, unit: !1)
+!6 = !DILocalVariable(name: "randv", scope: !5, file: !2, line: 69)
+!7 = !DIExpression()
+!8 = !DILocation(line: 132, column: 2, scope: !5)

llvm/trunk/test/CodeGen/X86/selectiondag-order.ll

+; Check that debug intrinsics do not affect code generation.
+
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx | FileCheck --check-prefix=X86-CHECK %s
+
+define i64 @simulate(<2 x i32> %a) {
+entry:
+  %rand = tail call i64 @lrand48()
+  br label %body
+
+body:                                        ; preds = %body, %entry
+  %0 = phi <2 x i32> [ %add, %body ], [ zeroinitializer, %entry ]
+  %add = add <2 x i32> %0, %a
+  %rand1 = tail call i64 @lrand48() #3
+  %cmp = icmp eq i64 %rand1, 0
+  br i1 %cmp, label %end, label %body
+
+end:                                        ; preds = %body
+  %c = bitcast <2 x i32> %add to i64
+  %res = add i64 %rand, %c
+  ret i64 %res
+}
+
+; X86-CHECK: simulate:
+; X86-CHECK: movdqa  %xmm0, 16(%rsp)
+; X86-CHECK: pxor  %xmm0, %xmm0
+; X86-CHECK: movdqa  %xmm0, (%rsp)
+; X86-CHECK: callq  lrand48
+; X86-CHECK: movq  %rax, %rbx
+
+define i64 @simulateWithDebugIntrinsic(<2 x i32> %a) local_unnamed_addr  {
+entry:
+  %rand = tail call i64 @lrand48() #3
+  tail call void @llvm.dbg.value(metadata i64 %rand, i64 0, metadata !6, metadata !7), !dbg !8
+  br label %body
+
+body:                                        ; preds = %body, %entry
+  %0 = phi <2 x i32> [ %add, %body ], [ zeroinitializer, %entry ]
+  %add = add <2 x i32> %0, %a
+  %rand1 = tail call i64 @lrand48() #3
+  %cmp = icmp eq i64 %rand1, 0
+  br i1 %cmp, label %end, label %body
+
+end:                                        ; preds = %body
+  %c = bitcast <2 x i32> %add to i64
+  %res = add i64 %rand, %c
+  ret i64 %res
+}
+
+; X86-CHECK: simulateWithDebugIntrinsic:
+; X86-CHECK: movdqa  %xmm0, 16(%rsp)
+; X86-CHECK: pxor  %xmm0, %xmm0
+; X86-CHECK: movdqa  %xmm0, (%rsp)
+; X86-CHECK: callq  lrand48
+; X86-CHECK: movq  %rax, %rbx
+
+define i64 @simulateWithDbgDeclare(<2 x i32> %a) local_unnamed_addr  {
+entry:
+  %rand = tail call i64 @lrand48() #3
+  tail call void @llvm.dbg.declare(metadata i64 %rand, metadata !6, metadata !7), !dbg !8
+  br label %body
+
+body:                                        ; preds = %body, %entry
+  %0 = phi <2 x i32> [ %add, %body ], [ zeroinitializer, %entry ]
+  %add = add <2 x i32> %0, %a
+  %rand1 = tail call i64 @lrand48() #3
+  %cmp = icmp eq i64 %rand1, 0
+  br i1 %cmp, label %end, label %body
+
+end:                                        ; preds = %body
+  %c = bitcast <2 x i32> %add to i64
+  %res = add i64 %rand, %c
+  ret i64 %res
+}
+
+; X86-CHECK: simulateWithDbgDeclare:
+; X86-CHECK: movdqa  %xmm0, 16(%rsp)
+; X86-CHECK: pxor  %xmm0, %xmm0
+; X86-CHECK: movdqa  %xmm0, (%rsp)
+; X86-CHECK: callq  lrand48
+; X86-CHECK: movq  %rax, %rbx
+
+declare i64 @lrand48()
+
+declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!3, !4}
+
+!1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, runtimeVersion: 0, emissionKind: FullDebug)
+!2 = !DIFile(filename: "test.ll", directory: ".")
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = distinct !DISubprogram(name: "simulateWithDebugIntrinsic", scope: !2, file: !2, line: 64, isLocal: false, isDefinition: true, scopeLine: 65, unit: !1)
+!6 = !DILocalVariable(name: "randv", scope: !5, file: !2, line: 69)
+!7 = !DIExpression()
+!8 = !DILocation(line: 132, column: 2, scope: !5)