MachineScheduler/ScheduleDAG: Add support for GetSubGraph

[axeldavy]

Summary

GetSubGraph is a new ScheduleDAG function to get the
subgraph of nodes between two SUs.

[axeldavy]

I'm closing to open again, in order to have the patch in llvm-commits.

include/llvm/CodeGen/ScheduleDAG.h

     /// ordering from the DAG to be scheduled.
     void InitDAGTopologicalSorting();
 
+    /// GetSubGraph - Returns an array of SUs that are both in the successor
+    /// subtree of StartSU and in the predecessor subtree of TargetSU.
+    /// StartSU and TargetSU are not in the array.
+    /// Success is false if TargetSU is not in the successor subtree of
+    /// StartSU, else it is true.
+    std::vector<int> GetSubGraph(const SUnit *StartSU, const SUnit *TargetSU,
+                                 bool &Success);
+
     /// IsReachable - Checks if SU is reachable from TargetSU.
     bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
 

lib/CodeGen/ScheduleDAG.cpp

   } while (!WorkList.empty());
 }
 
+/// GetSubGraph - Returns an array of SUs that are both in the successor
+/// subtree of StartSU and in the predecessor subtree of TargetSU.
+/// StartSU and TargetSU are not in the array.
+/// Success is false if TargetSU is not in the successor subtree of
+/// StartSU, else it is true.
+std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit *StartSU,
+                                                         const SUnit *TargetSU,
+                                                         bool &Success) {
+  std::vector<const SUnit*> WorkList;
+  int LowerBound = Node2Index[StartSU->NodeNum];
+  int UpperBound = Node2Index[TargetSU->NodeNum];
+  bool Found = false;
+  BitVector VisitedBack;
+  std::vector<int> Nodes;
+
+  if (LowerBound > UpperBound) {
+    Success = false;
+    return Nodes;
+  }
+
+  WorkList.reserve(SUnits.size());
+  Visited.reset();
+
+  // Starting from StartSU, visit all successors up
+  // to UpperBound.
+  WorkList.push_back(StartSU);
+  do {
+    const SUnit *SU = WorkList.back();
+    WorkList.pop_back();
+    Visited.set(SU->NodeNum);
+    for (int I = SU->Succs.size()-1; I >= 0; --I) {
+      unsigned s = SU->Succs[I].getSUnit()->NodeNum;
+      // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
+      if (s >= Node2Index.size())
+        continue;
+      if (Node2Index[s] == UpperBound) {
+        Found = true;
+        continue;
+      }
+      // Visit successors if not already and in affected region.
+      if (!Visited.test(s) && Node2Index[s] < UpperBound)
+        WorkList.push_back(SU->Succs[I].getSUnit());
+    }
+  } while (!WorkList.empty());
+
+  if (!Found) {
+    Success = false;
+    return Nodes;
+  }
+
+  WorkList.clear();
+  VisitedBack.resize(SUnits.size());
+  Found = false;
+
+  // Starting from TargetSU, visit all predecessors up
+  // to LowerBound. SUs that are visited by the two
+  // passes are added to Path.
+  WorkList.push_back(TargetSU);
+  do {
+    const SUnit *SU = WorkList.back();
+    WorkList.pop_back();
+    VisitedBack.set(SU->NodeNum);
+    for (int I = SU->Preds.size()-1; I >= 0; --I) {
+      unsigned s = SU->Preds[I].getSUnit()->NodeNum;
+      // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
+      if (s >= Node2Index.size())
+        continue;
+      if (Node2Index[s] == LowerBound) {
+        Found = true;
+        continue;
+      }
+      if (!VisitedBack.test(s) && Visited.test(s)) {
+        WorkList.push_back(SU->Preds[I].getSUnit());
+        Nodes.push_back(s);
+      }
+    }
+  } while (!WorkList.empty());
+
+  assert(Found);
+  Success = true;
+  return Nodes;
+}
+
 /// Shift - Renumber the nodes so that the topological ordering is
 /// preserved.
 void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,