diff options
| author | Andrew Trick <atrick@apple.com> | 2011-05-06 17:09:08 +0000 |
|---|---|---|
| committer | Andrew Trick <atrick@apple.com> | 2011-05-06 17:09:08 +0000 |
| commit | 15ab3594eba495ffd1f070207a4aceeae9492c11 (patch) | |
| tree | 2ce0d9f956969a17120d21bf33f816a9d47f39f8 /lib/CodeGen/PostRASchedulerList.cpp | |
| parent | 31c5d05a26b5b9eec88558d34e9c20d12e0d53d7 (diff) | |
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 <rdar://problem/9044332> 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
Diffstat (limited to 'lib/CodeGen/PostRASchedulerList.cpp')
| -rw-r--r-- | lib/CodeGen/PostRASchedulerList.cpp | 14 |
1 files changed, 10 insertions, 4 deletions
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. |