MachineScheduler: Limit the size of the ready list.

[MatzeB]

Summary

Avoid quadratic complexity in unusually large basic blocks by limiting
the size of the ready lists.

Measuring llvm test-suite for SPEC2000 shows that the ready queue size never exceed 200 on X86 and only exceeds the 256 limit 3 times on AArch64 (with benign/no changes).

[atrick]

I really think you need to do this in releasePending too.

[nhaehnle]

This likely affects AMDGPU in some cases, since shaders often have very large basic blocks as well. However, a test run on the external shader-db showed no notable changes, so no objections from that side.

[MatzeB]

Thanks for the review! The new version check the limit in releasePending() as well.

[MatzeB]

In D19349#408034, @nhaehnle wrote:

This likely affects AMDGPU in some cases, since shaders often have very large basic blocks as well. However, a test run on the external shader-db showed no notable changes, so no objections from that side.

While you obviously cannot get huge ready queues in small blocks, most large basic blocks still don't lead to situations in which several hundred values are ready at the same time.

[atrick]

LGTM

lib/CodeGen/MachineScheduler.cpp

 static bool ViewMISchedDAGs = false;
 #endif // NDEBUG
 
+/// Avoid quadratic complexity in unusually large basic blocks by limiting the
+/// size of the ready lists.
+static cl::opt<unsigned> ReadyListLimit("misched-limit", cl::Hidden,
+  cl::desc("Limit ready list to N instructions"), cl::init(256));
+
 static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,
   cl::desc("Enable register pressure scheduling."), cl::init(true));
 

   // Check for interlocks first. For the purpose of other heuristics, an
   // instruction that cannot issue appears as if it's not in the ReadyQueue.
   bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
-  if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU))
+  if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU) ||
+      Available.size() >= ReadyListLimit)
     Pending.push(SU);
   else
     Available.push(SU);

     if (checkHazard(SU))
       continue;
 
+    if (Available.size() >= ReadyListLimit)
+      break;
+
     Available.push(SU);
     Pending.remove(Pending.begin()+i);
     --i; --e;

test/CodeGen/AArch64/arm64-misched-basic-A53.ll

 ; REQUIRES: asserts
 ; RUN: llc < %s -mtriple=arm64-linux-gnu -mcpu=cortex-a53 -pre-RA-sched=source -enable-misched -verify-misched -debug-only=misched -o - 2>&1 > /dev/null | FileCheck %s
+; RUN: llc < %s -mtriple=arm64-linux-gnu -mcpu=cortex-a53 -pre-RA-sched=source -enable-misched -verify-misched -debug-only=misched -o - -misched-limit=2 2>&1 > /dev/null | FileCheck %s
 ;
 ; The Cortex-A53 machine model will cause the MADD instruction to be scheduled
 ; much higher than the ADD instructions in order to hide latency. When not