From a5a73ad15905c18843a8312bb3f20f5c501744de Mon Sep 17 00:00:00 2001
From: Andrew Trick <atrick@apple.com>
Date: Fri, 25 Jan 2013 06:52:30 +0000
Subject: [PATCH] ScheduleDAG: Added isBoundaryNode to conveniently detect a
 common corner case.

This fixes DAG subtree analysis at the boundary.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173427 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/CodeGen/ScheduleDAG.h | 13 ++++++++++++-
 lib/CodeGen/ScheduleDAGInstrs.cpp  | 26 +++++++++++++++++++-------
 2 files changed, 31 insertions(+), 8 deletions(-)

diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index 9f4f66f860e..18bef1c4028 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -258,6 +258,8 @@ namespace llvm {
   /// SUnit - Scheduling unit. This is a node in the scheduling DAG.
   class SUnit {
   private:
+    enum { BoundaryID = ~0u };
+
     SDNode *Node;                       // Representative node.
     MachineInstr *Instr;                // Alternatively, a MachineInstr.
   public:
@@ -343,7 +345,7 @@ namespace llvm {
 
     /// SUnit - Construct a placeholder SUnit.
     SUnit()
-      : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(~0u),
+      : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(BoundaryID),
         NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
         NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0),
         Latency(0), isVRegCycle(false), isCall(false), isCallOp(false),
@@ -354,6 +356,15 @@ namespace llvm {
         isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
         TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
 
+    /// \brief Boundary nodes are placeholders for the boundary of the
+    /// scheduling region.
+    ///
+    /// BoundaryNodes can have DAG edges, including Data edges, but they do not
+    /// correspond to schedulable entities (e.g. instructions) and do not have a
+    /// valid ID. Consequently, always check for boundary nodes before accessing
+    /// an assoicative data structure keyed on node ID.
+    bool isBoundaryNode() const { return NodeNum == BoundaryID; };
+
     /// setNode - Assign the representative SDNode for this SUnit.
     /// This may be used during pre-regalloc scheduling.
     void setNode(SDNode *N) {
diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp
index ef504067d11..f27b970aff1 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -1078,9 +1078,17 @@ public:
         joinPredSubtree(*PI, SU, /*CheckLimit=*/false);
 
       // Either link or merge the TreeData entry from the child to the parent.
-      if (R.DFSNodeData[PredNum].SubtreeID == PredNum)
-        RootSet[PredNum].ParentNodeID = SU->NodeNum;
-      else {
+      if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
+        // If the predecessor's parent is invalid, this is a tree edge and the
+        // current node is the parent.
+        if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
+          RootSet[PredNum].ParentNodeID = SU->NodeNum;
+      }
+      else if (RootSet.count(PredNum)) {
+        // The predecessor is not a root, but is still in the root set. This
+        // must be the new parent that it was just joined to. Note that
+        // RootSet[PredNum].ParentNodeID may either be invalid or may still be
+        // set to the original parent.
         RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
         RootSet.erase(PredNum);
       }
@@ -1115,8 +1123,10 @@ public:
       if (RI->ParentNodeID != SchedDFSResult::InvalidSubtreeID)
         R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[RI->ParentNodeID];
       R.DFSTreeData[TreeID].SubInstrCount = RI->SubInstrCount;
-      assert(RI->SubInstrCount <= R.DFSNodeData[RI->NodeID].InstrCount &&
-             "Bad SubInstrCount");
+      // Note that SubInstrCount may be greater than InstrCount if we joined
+      // subtrees across a cross edge. InstrCount will be attributed to the
+      // original parent, while SubInstrCount will be attributed to the joined
+      // parent.
     }
     R.SubtreeConnections.resize(SubtreeClasses.getNumClasses());
     R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses());
@@ -1221,7 +1231,7 @@ public:
 static bool hasDataSucc(const SUnit *SU) {
   for (SUnit::const_succ_iterator
          SI = SU->Succs.begin(), SE = SU->Succs.end(); SI != SE; ++SI) {
-    if (SI->getKind() == SDep::Data)
+    if (SI->getKind() == SDep::Data && !SI->getSUnit()->isBoundaryNode())
       return true;
   }
   return false;
@@ -1249,8 +1259,10 @@ void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) {
         const SDep &PredDep = *DFS.getPred();
         DFS.advance();
         // Ignore non-data edges.
-        if (PredDep.getKind() != SDep::Data)
+        if (PredDep.getKind() != SDep::Data
+            || PredDep.getSUnit()->isBoundaryNode()) {
           continue;
+        }
         // An already visited edge is a cross edge, assuming an acyclic DAG.
         if (Impl.isVisited(PredDep.getSUnit())) {
           Impl.visitCrossEdge(PredDep, DFS.getCurr());
-- 
2.11.0