[MISched] Use StartAtCycle in trace dumps.

[fpetrogalli]

Summary

This commit re-work the methods that dump traces with resource usage to take into account the StartAtCycle value added by https://reviews.llvm.org/D150310.

For each i, the values of the lists StartAtCycle and ReservedCycles is are printed with the interval [StartAtCycle[i], ReservedCycles[i])

... | StartAtCycle[i] | ... | ReservedCycles[i] - 1 | ReservedCycles[i] | ...
    | xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx |                   |

[andreadb]

llvm/lib/CodeGen/MachineScheduler.cpp

164

s/respource/resource

1008–1013

What if you use a SmallVector here?
I may remember it wrongly, but I think that there is a constructor which would allow you to pass an iterator range.

1028

Can this assert ever trigger in practice? I thought it was already tested by your logic from D150310.

[RKSimon]

llvm/lib/CodeGen/MachineScheduler.cpp

165

Add test coverage for this switch?

1029

(style)

for (unsigned I = 0, E = PI->Cycles - PI->StartAtCycle; I != E; ++i, ++C)

1099

use llvm::sort

1109

(style)

for (unsigned I = 0, E = PI->Cycles - PI->StartAtCycle; I != E; ++I, --C)

[RKSimon]

Also - please add a summary to the patch

[fpetrogalli]

Address code review.

[fpetrogalli]

Gentle ping.

[andreadb]

LGTM

[fpetrogalli]

Added early exit from the methods if there is no scheduling model attached to the CPU.

[RKSimon]

@fpetrogalli We're seeing build failures on EXPENSIVE_CHECKS builds due to the llvm::sort calls: https://lab.llvm.org/buildbot/#/builders/16/builds/49592 - you might be better off using llvm::stable_sort

[fpetrogalli]

In D150311#4416848, @RKSimon wrote:

@fpetrogalli We're seeing build failures on EXPENSIVE_CHECKS builds due to the llvm::sort calls: https://lab.llvm.org/buildbot/#/builders/16/builds/49592 - you might be better off using llvm::stable_sort

Thank you for the heads up. This should fix it D152800.

llvm/lib/CodeGen/MachineScheduler.cpp

static cl::opt<unsigned>
     HeaderColWidth("misched-dump-schedule-trace-col-header-width", cl::Hidden,
                    cl::desc("Set width of the columns with "
                             "the resources and schedule units"),
                    cl::init(19));
 static cl::opt<unsigned>
     ColWidth("misched-dump-schedule-trace-col-width", cl::Hidden,
              cl::desc("Set width of the columns showing resource booking."),
              cl::init(5));
+static cl::opt<bool> MISchedSortResourcesInTrace(
+    "misched-sort-resources-in-trace", cl::Hidden, cl::init(true),
+    cl::desc("Sort the resources printed in the dump trace"));
 #endif
 
 static cl::opt<unsigned>
     MIResourceCutOff("misched-resource-cutoff", cl::Hidden,
                      cl::desc("Number of intervals to track"), cl::init(10));
 
 // DAG subtrees must have at least this many nodes.
 static const unsigned MinSubtreeSize = 8;
if (RegionEnd != BB->end() && OrigPrevMI == &*RegionEnd)
       RegionEnd = DbgValue;
   }
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 static const char *scheduleTableLegend = "  i: issue\n  x: resource booked";
 
 LLVM_DUMP_METHOD void ScheduleDAGMI::dumpScheduleTraceTopDown() const {
+  // Bail off when there is no schedule model to query.
+  if (!SchedModel.hasInstrSchedModel())
+    return;
+
   //  Nothing to show if there is no or just one instruction.
   if (BB->size() < 2)
     return;
 
   dbgs() << " * Schedule table (TopDown):\n";
   dbgs() << scheduleTableLegend << "\n";
   const unsigned FirstCycle = getSUnit(&*(std::begin(*this)))->TopReadyCycle;
   unsigned LastCycle = getSUnit(&*(std::prev(std::end(*this))))->TopReadyCycle;
for (MachineInstr &MI : *this) {
     for (; C <= LastCycle; ++C) {
       if (C == SU->TopReadyCycle)
         dbgs() << llvm::left_justify("| i", ColWidth);
       else
         dbgs() << llvm::left_justify("|", ColWidth);
     }
     dbgs() << "|\n";
     const MCSchedClassDesc *SC = getSchedClass(SU);
-    for (TargetSchedModel::ProcResIter PI = SchedModel.getWriteProcResBegin(SC),
-                                       PE = SchedModel.getWriteProcResEnd(SC);
-         PI != PE; ++PI) {
+
+    SmallVector<MCWriteProcResEntry, 4> ResourcesIt(
+        make_range(SchedModel.getWriteProcResBegin(SC),
+                   SchedModel.getWriteProcResEnd(SC)));
+
+    if (MISchedSortResourcesInTrace)
+      llvm::sort(ResourcesIt.begin(), ResourcesIt.end(),
+                 [](const MCWriteProcResEntry &LHS,
+                    const MCWriteProcResEntry &RHS) -> bool {
+                   return LHS.StartAtCycle < RHS.StartAtCycle ||
+                          (LHS.StartAtCycle == RHS.StartAtCycle &&
+                           LHS.Cycles < RHS.Cycles);
+                 });
+    for (const MCWriteProcResEntry &PI : ResourcesIt) {
       C = FirstCycle;
       const std::string ResName =
-          SchedModel.getResourceName(PI->ProcResourceIdx);
-      dbgs() << llvm::left_justify(ResName, HeaderColWidth);
-      for (; C < SU->TopReadyCycle; ++C) {
+          SchedModel.getResourceName(PI.ProcResourceIdx);
+      dbgs() << llvm::right_justify(ResName + " ", HeaderColWidth);
+      for (; C < SU->TopReadyCycle + PI.StartAtCycle; ++C) {
         dbgs() << llvm::left_justify("|", ColWidth);
       }
-      for (unsigned i = 0; i < PI->Cycles; ++i, ++C)
+      for (unsigned I = 0, E = PI.Cycles - PI.StartAtCycle; I != E; ++I, ++C)
         dbgs() << llvm::left_justify("| x", ColWidth);
       while (C++ <= LastCycle)
         dbgs() << llvm::left_justify("|", ColWidth);
       // Place end char
       dbgs() << "| \n";
     }
   }
 }
 
 LLVM_DUMP_METHOD void ScheduleDAGMI::dumpScheduleTraceBottomUp() const {
+  // Bail off when there is no schedule model to query.
+  if (!SchedModel.hasInstrSchedModel())
+    return;
+
   //  Nothing to show if there is no or just one instruction.
   if (BB->size() < 2)
     return;
 
   dbgs() << " * Schedule table (BottomUp):\n";
   dbgs() << scheduleTableLegend << "\n";
 
   const int FirstCycle = getSUnit(&*(std::begin(*this)))->BotReadyCycle;
for (MachineInstr &MI : *this) {
     for (; C >= LastCycle; --C) {
       if (C == (int)SU->BotReadyCycle)
         dbgs() << llvm::left_justify("| i", ColWidth);
       else
         dbgs() << llvm::left_justify("|", ColWidth);
     }
     dbgs() << "|\n";
     const MCSchedClassDesc *SC = getSchedClass(SU);
-    for (TargetSchedModel::ProcResIter PI = SchedModel.getWriteProcResBegin(SC),
-                                       PE = SchedModel.getWriteProcResEnd(SC);
-         PI != PE; ++PI) {
+    SmallVector<MCWriteProcResEntry, 4> ResourcesIt(
+        make_range(SchedModel.getWriteProcResBegin(SC),
+                   SchedModel.getWriteProcResEnd(SC)));
+
+    if (MISchedSortResourcesInTrace)
+      llvm::sort(ResourcesIt.begin(), ResourcesIt.end(),
+                 [](const MCWriteProcResEntry &LHS,
+                    const MCWriteProcResEntry &RHS) -> bool {
+                   return LHS.StartAtCycle < RHS.StartAtCycle ||
+                          (LHS.StartAtCycle == RHS.StartAtCycle &&
+                           LHS.Cycles < RHS.Cycles);
+                 });
+    for (const MCWriteProcResEntry &PI : ResourcesIt) {
       C = FirstCycle;
       const std::string ResName =
-          SchedModel.getResourceName(PI->ProcResourceIdx);
-      dbgs() << llvm::left_justify(ResName, HeaderColWidth);
-      for (; C > (int)SU->BotReadyCycle; --C) {
+          SchedModel.getResourceName(PI.ProcResourceIdx);
+      dbgs() << llvm::right_justify(ResName + " ", HeaderColWidth);
+      for (; C > ((int)SU->BotReadyCycle - (int)PI.StartAtCycle); --C) {
         dbgs() << llvm::left_justify("|", ColWidth);
       }
-      for (unsigned i = 0; i < PI->Cycles; ++i, --C)
+      for (unsigned I = 0, E = PI.Cycles - PI.StartAtCycle; I != E; ++I, --C)
         dbgs() << llvm::left_justify("| x", ColWidth);
       while (C-- >= LastCycle)
         dbgs() << llvm::left_justify("|", ColWidth);
       // Place end char
       dbgs() << "| \n";
     }
   }
 }
 #endif

llvm/test/CodeGen/AArch64/dump-schedule-trace.mir

bb.0:
     $x7 = ADDXrr $x6, $x6
 
 # TOP-LABEL: *** Final schedule for %bb.0 ***
 # TOP-NEXT:  * Schedule table (TopDown):
 # TOP-NEXT:   i: issue
 # TOP-NEXT:   x: resource booked
 # TOP-NEXT: Cycle                | 0  | 1  | 2  |
 # TOP-NEXT: SU(0)                | i  |    |    |
-# TOP-NEXT: CortexA55UnitFPALU   | x  | x  |    |
+# TOP-NEXT:   CortexA55UnitFPALU | x  | x  |    |
 # TOP-NEXT: SU(1)                | i  |    |    |
-# TOP-NEXT: CortexA55UnitALU     | x  |    |    |
+# TOP-NEXT:     CortexA55UnitALU | x  |    |    |
 # TOP-NEXT: SU(2)                |    | i  |    |
-# TOP-NEXT: CortexA55UnitALU     |    | x  |    |
+# TOP-NEXT:     CortexA55UnitALU |    | x  |    |
 # TOP-NEXT: SU(3)                |    | i  |    |
-# TOP-NEXT: CortexA55UnitALU     |    | x  |    |
+# TOP-NEXT:     CortexA55UnitALU |    | x  |    |
 # TOP-NEXT: SU(4)                |    |    | i  |
-# TOP-NEXT: CortexA55UnitALU     |    |    | x  |
+# TOP-NEXT:     CortexA55UnitALU |    |    | x  |
 # TOP-NEXT: SU(0) [TopReadyCycle = 0, BottomReadyCycle = 3]:   dead %0:fpr128 = EXTv16i8 $q0, $q0, 8
 # TOP-NEXT: SU(1) [TopReadyCycle = 0, BottomReadyCycle = 0]:   $x3 = ADDXrr $x0, $x0
 # TOP-NEXT: SU(2) [TopReadyCycle = 1, BottomReadyCycle = 0]:   $x4 = ADDXrr $x1, $x1
 # TOP-NEXT: SU(3) [TopReadyCycle = 1, BottomReadyCycle = 0]:   $x5 = ADDXrr $x2, $x2
 # TOP-NEXT: SU(4) [TopReadyCycle = 2, BottomReadyCycle = 0]:   $x7 = ADDXrr $x6, $x6
 
 # BOTTOM-LABEL: *** Final schedule for %bb.0 ***
 # BOTTOM-NEXT:  * Schedule table (BottomUp):
 # BOTTOM-NEXT:   i: issue
 # BOTTOM-NEXT:   x: resource booked
 # BOTTOM-NEXT: Cycle              | 3 | 2 | 1 | 0 |
 # BOTTOM-NEXT: SU(0)              | i |   |   |   |
 # BOTTOM-NEXT: CortexA55UnitFPALU | x | x |   |   |
 # BOTTOM-NEXT: SU(1)              |   |   | i |   |
-# BOTTOM-NEXT: CortexA55UnitALU   |   |   | x |   |
+# BOTTOM-NEXT:   CortexA55UnitALU |   |   | x |   |
 # BOTTOM-NEXT: SU(2)              |   |   | i |   |
-# BOTTOM-NEXT: CortexA55UnitALU   |   |   | x |   |
+# BOTTOM-NEXT:   CortexA55UnitALU |   |   | x |   |
 # BOTTOM-NEXT: SU(3)              |   |   |   | i |
-# BOTTOM-NEXT: CortexA55UnitALU   |   |   |   | x |
+# BOTTOM-NEXT:   CortexA55UnitALU |   |   |   | x |
 # BOTTOM-NEXT: SU(4)              |   |   |   | i |
-# BOTTOM-NEXT: CortexA55UnitALU   |   |   |   | x |
+# BOTTOM-NEXT:   CortexA55UnitALU |   |   |   | x |
 # BOTTOM-NEXT: SU(0) [TopReadyCycle = 0, BottomReadyCycle = 3]:   dead %0:fpr128 = EXTv16i8 $q0, $q0, 8
 # BOTTOM-NEXT: SU(1) [TopReadyCycle = 0, BottomReadyCycle = 1]:   $x3 = ADDXrr $x0, $x0
 # BOTTOM-NEXT: SU(2) [TopReadyCycle = 0, BottomReadyCycle = 1]:   $x4 = ADDXrr $x1, $x1
 # BOTTOM-NEXT: SU(3) [TopReadyCycle = 0, BottomReadyCycle = 0]:   $x5 = ADDXrr $x2, $x2
 # BOTTOM-NEXT: SU(4) [TopReadyCycle = 0, BottomReadyCycle = 0]:   $x7 = ADDXrr $x6, $x6
 
 # This test shows that at the moment we cannot generate the trace of
 # bidirectional scheduling as the values of TopReadyCycle and

llvm/test/CodeGen/AArch64/misched-sort-resource-in-trace.mir

+# RUN: llc -mtriple=aarch64-none-linux-gnu -mcpu=exynos-m3 -verify-machineinstrs \
+# RUN: -run-pass=machine-scheduler -debug-only=machine-scheduler -o - %s \
+# RUN:  -misched-topdown=true -sched-print-cycles=true \
+# RUN:  -misched-dump-schedule-trace=true --misched-sort-resources-in-trace=true 2>&1 | FileCheck --check-prefix=SORTED %s
+
+# RUN: llc -mtriple=aarch64-none-linux-gnu -mcpu=exynos-m3 -verify-machineinstrs \
+# RUN: -run-pass=machine-scheduler -debug-only=machine-scheduler -o - %s \
+# RUN:  -misched-topdown=true -sched-print-cycles=true \
+# RUN:  -misched-dump-schedule-trace=true --misched-sort-resources-in-trace=false 2>&1 | FileCheck --check-prefix=UNSORTED %s
+
+---
+name: test
+tracksRegLiveness: true
+body:             |
+  bb.0:
+  liveins: $x0, $x1, $x3, $x4, $q2
+  $x0, $q2 = LD1i32_POST $q2, 0, $x0, $x0 :: ("aarch64-strided-access" load (s32))
+  $x1, $q2 = LD1i32_POST $q2, 0, $x1, $x1 :: ("aarch64-strided-access" load (s32))
+...
+
+
+# SORTED-LABEL: *** Final schedule for %bb.0 ***
+# SORTED-NEXT:  * Schedule table (TopDown):
+# SORTED-NEXT:   i: issue
+# SORTED-NEXT:   x: resource booked
+# SORTED-NEXT: Cycle              | 0  | 1  | 2  |
+# SORTED-NEXT: SU(0)              | i  |    |    |
+# SORTED-NEXT:          M3UnitALU | x  |    |    |
+# SORTED-NEXT:         M3UnitNALU | x  |    |    |
+# SORTED-NEXT:            M3UnitL | x  | x  |    |
+# SORTED-NEXT: SU(1)              |    | i  |    |
+# SORTED-NEXT:          M3UnitALU |    | x  |    |
+# SORTED-NEXT:         M3UnitNALU |    | x  |    |
+# SORTED-NEXT:            M3UnitL |    | x  | x  |
+# SORTED-NEXT: SU(0) [TopReadyCycle = 0, BottomReadyCycle = 0]: $x0, $q2 = LD1i32_POST $q2(tied-def 1), 0, $x0(tied-def 0), $x0 :: ("aarch64-strided-access" load (s32))
+# SORTED-NEXT: SU(1) [TopReadyCycle = 1, BottomReadyCycle = 6]:   $x1, $q2 = LD1i32_POST $q2(tied-def 1), 0, $x1(tied-def 0), $x1 :: ("aarch64-strided-access" load (s32))
+
+# UNSORTED-LABEL: *** Final schedule for %bb.0 ***
+# UNSORTED-NEXT:  * Schedule table (TopDown):
+# UNSORTED-NEXT:   i: issue
+# UNSORTED-NEXT:   x: resource booked
+# UNSORTED-NEXT: Cycle              | 0  | 1  | 2  |
+# UNSORTED-NEXT: SU(0)              | i  |    |    |
+# UNSORTED-NEXT:          M3UnitALU | x  |    |    |
+# UNSORTED-NEXT:            M3UnitL | x  | x  |    |
+# UNSORTED-NEXT:         M3UnitNALU | x  |    |    |
+# UNSORTED-NEXT: SU(1)              |    | i  |    |
+# UNSORTED-NEXT:          M3UnitALU |    | x  |    |
+# UNSORTED-NEXT:            M3UnitL |    | x  | x  |
+# UNSORTED-NEXT:         M3UnitNALU |    | x  |    |
+# UNSORTED-NEXT: SU(0) [TopReadyCycle = 0, BottomReadyCycle = 0]: $x0, $q2 = LD1i32_POST $q2(tied-def 1), 0, $x0(tied-def 0), $x0 :: ("aarch64-strided-access" load (s32))
+# UNSORTED-NEXT: SU(1) [TopReadyCycle = 1, BottomReadyCycle = 6]:   $x1, $q2 = LD1i32_POST $q2(tied-def 1), 0, $x1(tied-def 0), $x1 :: ("aarch64-strided-access" load (s32))