[ScheduleDAG] When a node is cloned, add an edge between the nodes.

[efriedma]

Summary

InstrEmitter's virtual register handling assumes that clones are emitted after the cloned node. Make sure this assumption actually holds.

Fixes a "Node emitted out of order - early" assertion on the testcase.

This is probably a very rare case to actually hit in practice; even without the explicit edge, the scheduler will usually end up scheduling the nodes in the expected order due to other constraints.

[rogfer01]

Thanks @efriedma LGTM

Now that you're at it, could you also update the doxygen comments in ScheduleDAGRRList::{AddPredQueued, AddPred, RemovePred} because they don't return a boolean now.

[fhahn]

LGTM, thanks.

test/CodeGen/Thumb/scheduler-clone-cpsr-def.ll

2

I think we could instead check the MIR after SelDAG, which would potentially make the test case a bit more independent of other changes in the backend,

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
   LLVM_DEBUG(dbgs() << "    Duplicating SU #" << SU->NodeNum << "\n");
   NewSU = CreateClone(SU);
 
   // New SUnit has the exact same predecessors.
   for (SDep &Pred : SU->Preds)
     if (!Pred.isArtificial())
       AddPredQueued(NewSU, Pred);
 
+  // Make sure the clone comes after the original. (InstrEmitter assumes
+  // this ordering.)
+  AddPredQueued(NewSU, SDep(SU, SDep::Artificial));
+
   // Only copy scheduled successors. Cut them from old node's successor
   // list and move them over.
   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
   for (SDep &Succ : SU->Succs) {
     if (Succ.isArtificial())
       continue;
     SUnit *SuccSU = Succ.getSUnit();
     if (SuccSU->isScheduled) {

test/CodeGen/Thumb/scheduler-clone-cpsr-def.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=thumbv6-linux-gnueabi < %s | FileCheck %s
+
+; After various DAGCombine optimizations, we end up with an sbcs with
+; multiple uses of the cpsr def, and we therefore clone the subs/sbcs.
+; Make sure this doesn't crash.
+;
+; The output here might change at some point in the future, and no
+; longer clone the operations; if that happens, there probably isn't any
+; straightforward way to fix the test.
+define i64 @f(i64 %x2, i32 %z) {
+; CHECK-LABEL: f:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    .save {r4, r5, r7, lr}
+; CHECK-NEXT:    push {r4, r5, r7, lr}
+; CHECK-NEXT:    movs r2, #0
+; CHECK-NEXT:    subs r3, r0, #1
+; CHECK-NEXT:    mov r3, r1
+; CHECK-NEXT:    sbcs r3, r2
+; CHECK-NEXT:    mov r3, r2
+; CHECK-NEXT:    adcs r3, r2
+; CHECK-NEXT:    movs r4, #30
+; CHECK-NEXT:    subs r5, r0, #1
+; CHECK-NEXT:    mov r5, r1
+; CHECK-NEXT:    sbcs r5, r2
+; CHECK-NEXT:    adcs r4, r2
+; CHECK-NEXT:    lsls r2, r1, #1
+; CHECK-NEXT:    lsls r2, r4
+; CHECK-NEXT:    movs r4, #1
+; CHECK-NEXT:    eors r4, r3
+; CHECK-NEXT:    lsrs r0, r4
+; CHECK-NEXT:    orrs r0, r2
+; CHECK-NEXT:    lsrs r1, r4
+; CHECK-NEXT:    pop {r4, r5, r7, pc}
+  %x3 = add nsw i64 %x2, -1
+  %x8 = icmp ne i64 %x2, 0
+  %x9 = xor i1 %x8, true
+  %x10 = zext i1 %x9 to i64
+  %x11 = lshr i64 %x2, %x10
+  ret i64 %x11
+}