From 6e4c46cea5daef8bc807a36ce2ab9bb7f9855b67 Mon Sep 17 00:00:00 2001
From: Evan Cheng <evan.cheng@apple.com>
Date: Thu, 27 Sep 2007 00:25:29 +0000
Subject: [PATCH] Backtracking only when it won't create a cycle.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42384 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../SelectionDAG/ScheduleDAGRRList.cpp        | 58 +++++++++++--------
 1 file changed, 35 insertions(+), 23 deletions(-)

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index 61a005ce10e..aa63e9734f9 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -326,6 +326,40 @@ void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
   AvailableQueue->push(SU);
 }
 
+// FIXME: This is probably too slow!
+static void isReachable(SUnit *SU, SUnit *TargetSU,
+                        SmallPtrSet<SUnit*, 32> &Visited, bool &Reached) {
+  if (Reached) return;
+  if (SU == TargetSU) {
+    Reached = true;
+    return;
+  }
+  if (!Visited.insert(SU)) return;
+
+  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E;
+       ++I)
+    isReachable(I->Dep, TargetSU, Visited, Reached);
+}
+
+static bool isReachable(SUnit *SU, SUnit *TargetSU) {
+  SmallPtrSet<SUnit*, 32> Visited;
+  bool Reached = false;
+  isReachable(SU, TargetSU, Visited, Reached);
+  return Reached;
+}
+
+/// willCreateCycle - Returns true if adding an edge from SU to TargetSU will
+/// create a cycle.
+static bool willCreateCycle(SUnit *SU, SUnit *TargetSU) {
+  if (isReachable(TargetSU, SU))
+    return true;
+  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+       I != E; ++I)
+    if (I->Cost < 0 && isReachable(TargetSU, I->Dep))
+      return true;
+  return false;
+}
+
 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
 /// BTCycle in order to schedule a specific node. Returns the last unscheduled
 /// SUnit. Also returns if a successor is unscheduled in the process.
@@ -469,28 +503,6 @@ static MVT::ValueType getPhysicalRegisterVT(SDNode *N, unsigned Reg,
   return N->getValueType(NumRes);
 }
 
-// FIXME: This is probably too slow!
-static void isReachable(SUnit *SU, SUnit *TargetSU,
-                        SmallPtrSet<SUnit*, 32> &Visited, bool &Reached) {
-  if (Reached) return;
-  if (SU == TargetSU) {
-    Reached = true;
-    return;
-  }
-  if (!Visited.insert(SU)) return;
-
-  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E;
-       ++I)
-    isReachable(I->Dep, TargetSU, Visited, Reached);
-}
-
-static bool isReachable(SUnit *SU, SUnit *TargetSU) {
-  SmallPtrSet<SUnit*, 32> Visited;
-  bool Reached = false;
-  isReachable(SU, TargetSU, Visited, Reached);
-  return Reached;
-}
-
 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
 /// scheduling of the given node to satisfy live physical register dependencies.
 /// If the specific node is the last one that's available to schedule, do
@@ -547,7 +559,7 @@ bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, unsigned &CurCycle){
     }
 
     SUnit *OldSU = Sequence[LiveCycle];
-    if (!isReachable(Sequence[LiveCycle], SU))  {
+    if (!willCreateCycle(SU, OldSU))  {
       // If CycleBound is greater than backtrack cycle, then some of SU
       // successors are going to be unscheduled.
       bool SuccUnsched = SU->CycleBound > LiveCycle;
-- 
2.34.1