[SelectionDAG] Do not increment SDNodeOrder for debug intrinsics.

[fhahn]

Summary

Some parts of CodeGen rely on the IR order (e.g. ScheduleDAGRRList)
and debug intrinsics previously affected the ordering.

This problem was found using check_cfc.py. With this patch, the build
failures for llvm's test-suite with check_cfc.py go from 113 down to 77
in x86_64.

[MatzeB]

Adding aprantl for debug info stuff.

[MatzeB]

The description sounds similar to https://reviews.llvm.org/D25318

[aprantl]

Can't say that I fully understand the implication of this (I don't know what the node order is used for), but given your explanation this appears to be fine.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

4975

Extra whitespace :-)

[aprantl]

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

877

Any way the purpose of this condition could be documented?

[fhahn]

Thanks @MatzeB I wasn't aware of this review! It looks like it addresses a similar problem, but the test case is different. I'll test my change with the test case from the D25318.

[fhahn]

Added a comment and removed stray line.

[fhahn]

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

877

I hope my comment change makes is clearer.

[fhahn]

After having a closer look at D25318 I think it solves the problem in a slightly better way.

[fhahn]

Upload 2 test cases for use with D25318

[fhahn]

Abandoned, because merged in rL292485

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

if (HasDbg) {
 
     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;
+      // Insert all SDDbgValue's whose order(s) are before the current and after
+      // the previous machine instruction. A SDDbgValue's order is
+      // 1 + (order of previous machine instruction), which means a SDDbgValue
+      // is before the current machine instruction if its order is less than or
+      // equal to the order of the current machine instruction ("Order").
       for (; DI != DE &&
-             (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) {
+             (*DI)->getOrder() > LastOrder && (*DI)->getOrder() <= Order; ++DI) {
         if ((*DI)->isInvalidated())
           continue;
         MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
         if (DbgMI) {
           if (!LastOrder)
             // Insert to start of the BB (after PHIs).
             BB->insert(BBBegin, DbgMI);
           else {

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());
   }
 
+  // Do not increment SDNodeOrder for debug intrinsics, because some parts
+  // of CodeGen rely on the node order (e.g. ScheduleDAGRRList).
+  // Debug nodes created use SDNodeOrder+1 to ensure they are placed after
+  // the previous 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);
if (N.getNode()) {
       if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Address))
         Address = BCI->getOperand(0);
       // Parameters are handled specially.
       bool isParameter = Variable->isParameter() || isa<Argument>(Address);
       auto FINode = dyn_cast<FrameIndexSDNode>(N.getNode());
       if (isParameter && FINode) {
         // Byval parameter. We have a frame index at this point.
         SDV = DAG.getFrameIndexDbgValue(Variable, Expression,
-                                        FINode->getIndex(), 0, dl, SDNodeOrder);
+                                        FINode->getIndex(), 0, dl, SDNodeOrder+1);
       } else if (isa<Argument>(Address)) {
         // Address is an argument, so try to emit its dbg value using
         // virtual register info from the FuncInfo.ValueMap.
         EmitFuncArgumentDbgValue(Address, Variable, Expression, dl, 0, false,
                                  N);
         return nullptr;
       } else {
         SDV = DAG.getDbgValue(Variable, Expression, N.getNode(), N.getResNo(),
-                              true, 0, dl, SDNodeOrder);
+                              true, 0, dl, SDNodeOrder+1);
       }
       DAG.AddDbgValue(SDV, N.getNode(), isParameter);
     } else {
       // If Address is an argument then try to emit its dbg value using
       // virtual register info from the FuncInfo.ValueMap.
       if (!EmitFuncArgumentDbgValue(Address, Variable, Expression, dl, 0, false,
                                     N)) {
         // If variable is pinned by a alloca in dominating bb then
         // use StaticAllocaMap.
         if (const AllocaInst *AI = dyn_cast<AllocaInst>(Address)) {
           if (AI->getParent() != DI.getParent()) {
             DenseMap<const AllocaInst*, int>::iterator SI =
               FuncInfo.StaticAllocaMap.find(AI);
             if (SI != FuncInfo.StaticAllocaMap.end()) {
               SDV = DAG.getFrameIndexDbgValue(Variable, Expression, SI->second,
-                                              0, dl, SDNodeOrder);
+                                              0, dl, SDNodeOrder+1);
               DAG.AddDbgValue(SDV, nullptr, false);
               return nullptr;
             }
           }
         }
         DEBUG(dbgs() << "Dropping debug info for " << DI << "\n");
       }
     }
     return nullptr;
   }
   case Intrinsic::dbg_value: {
     const DbgValueInst &DI = cast<DbgValueInst>(I);
     assert(DI.getVariable() && "Missing variable");
 
     DILocalVariable *Variable = DI.getVariable();
     DIExpression *Expression = DI.getExpression();
     uint64_t Offset = DI.getOffset();
     const Value *V = DI.getValue();
     if (!V)
       return nullptr;
 
     SDDbgValue *SDV;
     if (isa<ConstantInt>(V) || isa<ConstantFP>(V) || isa<UndefValue>(V)) {
       SDV = DAG.getConstantDbgValue(Variable, Expression, V, Offset, dl,
-                                    SDNodeOrder);
+                                    SDNodeOrder+1);
       DAG.AddDbgValue(SDV, nullptr, false);
     } else {
       // Do not use getValue() in here; we don't want to generate code at
       // this point if it hasn't been done yet.
       SDValue N = NodeMap[V];
       if (!N.getNode() && isa<Argument>(V))
         // Check unused arguments map.
         N = UnusedArgNodeMap[V];
       if (N.getNode()) {
         if (!EmitFuncArgumentDbgValue(V, Variable, Expression, dl, Offset,
                                       false, N)) {
-          SDV = getDbgValue(N, Variable, Expression, Offset, dl, SDNodeOrder);
+          SDV = getDbgValue(N, Variable, Expression, Offset, dl, SDNodeOrder+1);
           DAG.AddDbgValue(SDV, N.getNode(), false);
         }
       } else 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);
+        DanglingDebugInfo DDI(&DI, dl, SDNodeOrder+1);
         DanglingDebugInfoMap[V] = DDI;
       } else {
         // We may expand this to cover more cases.  One case where we have no
         // data available is an unreferenced parameter.
         DEBUG(dbgs() << "Dropping debug info for " << DI << "\n");
       }
     }
 

test/CodeGen/X86/dbg_intrinsic_cfc.ll

+; Check that debug intrinsics do not affect code generation.
+
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx | FileCheck %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
+}
+
+; CHECK: simulate:
+; CHECK: movdqa %xmm0, 16(%rsp)
+; CHECK: pxor %xmm0, %xmm0
+; CHECK: movdqa  %xmm0, (%rsp)
+; CHECK: callq  lrand48
+; 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
+}
+
+; CHECK: simulateWithDebugIntrinsic:
+; CHECK: movdqa %xmm0, 16(%rsp)
+; CHECK: pxor %xmm0, %xmm0
+; CHECK: movdqa  %xmm0, (%rsp)
+; CHECK: callq  lrand48
+; 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
+}
+
+; CHECK: simulateWithDbgDeclare:
+; CHECK: movdqa %xmm0, 16(%rsp)
+; CHECK: pxor %xmm0, %xmm0
+; CHECK: movdqa  %xmm0, (%rsp)
+; CHECK: callq  lrand48
+; 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)

test/DebugInfo/X86/dbg-value-dag-combine.ll

 ; RUN: llc < %s | FileCheck %s
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:32"
 target triple = "i686-apple-darwin"
 ; PR 9817
 
 ; There should be a DEBUG_VALUE for each call to llvm.dbg.value
 
 ; CHECK:  ##DEBUG_VALUE: __OpenCL_test_kernel:ip <- 
-; CHECK:  ##DEBUG_VALUE: xxx <- 0
 ; CHECK:  ##DEBUG_VALUE: gid <- %E{{..$}}
+; CHECK:  ##DEBUG_VALUE: xxx <- 0
 ; CHECK:  ##DEBUG_VALUE: idx <- %E{{..$}}
 ; CHECK-NOT:  ##DEBUG_VALUE:
 
 declare <4 x i32> @__amdil_get_global_id_int()
 declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
 define void @__OpenCL_test_kernel(i32 addrspace(1)* %ip) nounwind !dbg !0 {
 entry:
   call void @llvm.dbg.value(metadata i32 addrspace(1)* %ip, i64 0, metadata !7, metadata !DIExpression()), !dbg !8

test/DebugInfo/X86/pieces-4.ll

 ;   asm volatile("" : : : "rax", "rbx", "rcx", "rdx", "rsi", "rdi", "rbp",
 ;                "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15");
 ;   return o.x;
 ; }
 
 ; CHECK-LABEL: bitpiece_spill:                         # @bitpiece_spill
 ; CHECK:               callq   g
 ; CHECK:               movl    %eax, [[offs:[0-9]+]](%rsp)          # 4-byte Spill
-; CHECK:               #DEBUG_VALUE: bitpiece_spill:o [bit_piece offset=32 size=32] <- 0
 ; CHECK:               #DEBUG_VALUE: bitpiece_spill:o [bit_piece offset=0 size=32] <- [%RSP+[[offs]]]
+; CHECK:               #DEBUG_VALUE: bitpiece_spill:o [bit_piece offset=32 size=32] <- 0
 ; CHECK:               #APP
 ; CHECK:               #NO_APP
 ; CHECK:               movl    [[offs]](%rsp), %eax          # 4-byte Reload
 ; CHECK:               retq
 
 ; ModuleID = 't.c'
 source_filename = "t.c"
 target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"