[MachinePipeliner] Fix incorrect handlings of unpipelineable insts (#126057)

There was a case where `normalizeNonPipelinedInstructions` didn't
schedule unpipelineable instructions correctly, which could generate
illegal code. This patch fixes this issue by rejecting the schedule if
we fail to insert the unpipelineable instructions at stage 0.

Here is a part of the debug output for `sms-unpipeline-insts3.mir`
before applying this patch.

```
SU(0):   %27:gpr32 = PHI %21:gpr32all, %bb.3, %28:gpr32all, %bb.4
  Successors:
    SU(14): Data Latency=0 Reg=%27
    SU(15): Anti Latency=1

...

SU(14):   %41:gpr32 = ADDWrr %27:gpr32, %12:gpr32common
  Predecessors:
    SU(0): Data Latency=0 Reg=%27
    SU(16): Ord  Latency=0 Artificial
  Successors:
    SU(15): Data Latency=1 Reg=%41
SU(15):   %28:gpr32all = COPY %41:gpr32
  Predecessors:
    SU(14): Data Latency=1 Reg=%41
    SU(0): Anti Latency=1
SU(16):   %30:ppr = WHILELO_PWW_S %27:gpr32, %15:gpr32, implicit-def $nzcv
  Predecessors:
    SU(0): Data Latency=0 Reg=%27
  Successors:
    SU(14): Ord  Latency=0 Artificial

...

Do not pipeline SU(16)
Do not pipeline SU(1)
Do not pipeline SU(0)
Do not pipeline SU(15)
Do not pipeline SU(14)
SU(0) is not pipelined; moving from cycle 19 to 0 Instr: ...
SU(1) is not pipelined; moving from cycle 10 to 0 Instr: ...
SU(15) is not pipelined; moving from cycle 28 to 19 Instr: ...
SU(16) is not pipelined; moving from cycle 19 to 0 Instr: ...
Schedule Found? 1 (II=10)

...

cycle 9 (1) (14) %41:gpr32 = ADDWrr %27:gpr32, %12:gpr32common

cycle 9 (1) (15) %28:gpr32all = COPY %41:gpr32
```

The SUs are traversed in the order of the original basic block, so in
this case a new cycle of each instruction is determined in the order of
`SU(0)`, `SU(1)`, `SU(14)`, `SU(15)`, `SU(16)`. Since there is an
artificial dependence from `SU(16)` to `SU(14)`, which is contradict to
the original SU order, the new cycle of `SU(14)` must be greater than or
equal to the cycle of `SU(16)` at that time. This results in the failure
of scheduling `SU(14)` at stage 0. For now, we reject the schedule for
such cases.

1 files changed, 26 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/MachinePipeliner.cpp b/llvm/lib/CodeGen/MachinePipeliner.cpp
index 9bd07da..99d582c 100644
--- a/llvm/lib/CodeGen/MachinePipeliner.cpp
+++ b/llvm/lib/CodeGen/MachinePipeliner.cpp
@@ -3297,6 +3297,32 @@ bool SMSchedule::normalizeNonPipelinedInstructions(
                         << ") is not pipelined; moving from cycle " << OldCycle
                         << " to " << NewCycle << " Instr:" << *SU.getInstr());
     }
+
+    // We traverse the SUs in the order of the original basic block. Computing
+    // NewCycle in this order normally works fine because all dependencies
+    // (except for loop-carried dependencies) don't violate the original order.
+    // However, an artificial dependency (e.g., added by CopyToPhiMutation) can
+    // break it. That is, there may be exist an artificial dependency from
+    // bottom to top. In such a case, NewCycle may become too large to be
+    // scheduled in Stage 0. For example, assume that Inst0 is in DNP in the
+    // following case:
+    //
+    //             |  Inst0  <-+
+    //   SU order  |           | artificial dep
+    //             |  Inst1  --+
+    //             v
+    //
+    // If Inst1 is scheduled at cycle N and is not at Stage 0, then NewCycle of
+    // Inst0 must be greater than or equal to N so that Inst0 is not be
+    // scheduled at Stage 0. In such cases, we reject this schedule at this
+    // time.
+    // FIXME: The reason for this is the existence of artificial dependencies
+    // that are contradict to the original SU order. If ignoring artificial
+    // dependencies does not affect correctness, then it is better to ignore
+    // them.
+    if (FirstCycle + InitiationInterval <= NewCycle)
+      return false;
+
     NewLastCycle = std::max(NewLastCycle, NewCycle);
   }
   LastCycle = NewLastCycle;