From 15ab3594eba495ffd1f070207a4aceeae9492c11 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Fri, 6 May 2011 17:09:08 +0000 Subject: Post-RA scheduler compile time fix. Quadratic computation of DAG node depth. The post-ra scheduler was explicitly updating the depth of a node's successors after scheduling it, regardless of whether the successor was ready. This is quadratic for DAGs with transitively redundant edges. I simply removed the useless update of depth, which is lazilly computed later. Fixes compiler takes way too long to build TextInput. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130992 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/PostRASchedulerList.cpp | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'lib/CodeGen/PostRASchedulerList.cpp') diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index 60c24b7107..848af2a6c3 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -540,10 +540,16 @@ void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { #endif --SuccSU->NumPredsLeft; - // Compute how many cycles it will be before this actually becomes - // available. This is the max of the start time of all predecessors plus - // their latencies. - SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); + // Standard scheduler algorithms will recomute the depth of the successor + // here as such: + // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); + // + // However, we lazily compute node depth instead. Note that + // ScheduleNodeTopDown has already updated the depth of this node which causes + // all descendents to be marked dirty. Setting the successor depth explicitly + // here would cause depth to be recomputed for all its ancestors. If the + // successor is not yet ready (because of a transitively redundant edge) then + // this causes depth computation to be quadratic in the size of the DAG. // If all the node's predecessors are scheduled, this node is ready // to be scheduled. Ignore the special ExitSU node. -- cgit v1.2.3