MachineScheduler: Limit the size of the ready list.
Avoid quadratic complexity in unusually large basic blocks by limiting
the size of the ready lists.
Differential Revision: http://reviews.llvm.org/D19349
llvm-svn: 267189
diff --git a/llvm/lib/CodeGen/MachineScheduler.cpp b/llvm/lib/CodeGen/MachineScheduler.cpp
index e4d1c3c..927a036 100644
--- a/llvm/lib/CodeGen/MachineScheduler.cpp
+++ b/llvm/lib/CodeGen/MachineScheduler.cpp
@@ -64,6 +64,11 @@
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));
@@ -1956,7 +1961,8 @@
// 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);
@@ -2211,6 +2217,9 @@
if (checkHazard(SU))
continue;
+ if (Available.size() >= ReadyListLimit)
+ break;
+
Available.push(SU);
Pending.remove(Pending.begin()+i);
--i; --e;