MachineScheduler/ScheduleDAG: Add support for GetSubGraph

[axeldavy]

Summary

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

[axeldavy]

This patch is required for https://reviews.llvm.org/D30152

I don't know who should be reviewer for this code. Anyone ?

[axeldavy]

Rebased on master.

[axeldavy]

ping.

[hfinkel]

Can you please post this patch with full context? See http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface for instructions.

[atrick]

This seems reasonable to me. Hopefully the linker will strip utilities like this for build targets that don't need them.

[axeldavy]

Added full context

[MatzeB]

include/llvm/CodeGen/ScheduleDAG.h

718 ↗

(On Diff #91058)

Do not repeat the function name in the doxygen comment.

723–724 ↗

(On Diff #91058)

Use references instead of pointers for things that cannot be nullptr.

lib/CodeGen/ScheduleDAG.cpp

579 ↗

(On Diff #91058)

Better use SUnit::isBoundaryNode()

587 ↗

(On Diff #91058)

Isn't there a mismatch here? I would assume you either test+set visited at the beginning of the loop or you do both when inserting into the worklist.

Testing before insertion but only setting the visited flag when pulling out of the worklist can lead to situations in which elements are pulled out multiple times.

611 ↗

(On Diff #91058)

Better use SUnit::isBoundaryNode()

[hfinkel]

In D30626#700951, @axeldavy wrote:

Added full context

Small comment about the assert, but otherwise LGTM too.

lib/CodeGen/ScheduleDAG.cpp

624 ↗

(On Diff #91769)

This assert should have a comment, but instead of tracking Found again, maybe it would be even better to do this:

assert(VisitedBack.size() == Visited.size() && "Did not collect all subgraph nodes?");

[axeldavy]

lib/CodeGen/ScheduleDAG.cpp

624 ↗

(On Diff #91769)

Thanks, I add a comment in the assert.

However please note that VisitedBack and Visited likely don't have the same size.
Visited can contain more elements.

579 ↗

(On Diff #91058)

Thanks, I update the diff with that.

587 ↗

(On Diff #91058)

Right, it sounds better to set Visited directly there.

It may be possible without it items get added several times to the WorkList, though the second time the items would be pulled, the operation would be noop.

[axeldavy]

Updated according to the review comments.

[MatzeB]

LGTM

[axeldavy]

The Visited set was incorrectly set in the previous diff.

[vpykhtin]

include/llvm/CodeGen/ScheduleDAG.h

723 ↗

(On Diff #91778)

Isn't it enough to return empty vector on failure, without error flag?

[axeldavy]

include/llvm/CodeGen/ScheduleDAG.h

723 ↗

(On Diff #91778)

Empty vector currently means that TargetSU is a direct successor for StartSU.

If we don't have error flag and say that a failure return empty vector,
we have to check if TargetSU is in StartSU's Succs.

I think it's better having directly an error flag.

llvm/trunk/include/llvm/CodeGen/ScheduleDAG.h

class ScheduleDAGTopologicalSort {
     void Allocate(int n, int index);
 
   public:
     ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
 
     /// Creates the initial topological ordering from the DAG to be scheduled.
     void InitDAGTopologicalSorting();
 
+    /// 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);
+
     /// Checks if \p SU is reachable from \p TargetSU.
     bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
 
     /// Returns true if addPred(TargetSU, SU) creates a cycle.
     bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
 
     /// \brief Updates the topological ordering to accommodate an edge to be
     /// added from SUnit \p X to SUnit \p Y.

llvm/trunk/lib/CodeGen/ScheduleDAG.cpp

for (const SDep &SuccDep
       // Visit successors if not already and in affected region.
       if (!Visited.test(s) && Node2Index[s] < UpperBound) {
         WorkList.push_back(SuccDep.getSUnit());
       }
     }
   } while (!WorkList.empty());
 }
 
+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();
+    for (int I = SU->Succs.size()-1; I >= 0; --I) {
+      const SUnit *Succ = SU->Succs[I].getSUnit();
+      unsigned s = Succ->NodeNum;
+      // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
+      if (Succ->isBoundaryNode())
+        continue;
+      if (Node2Index[s] == UpperBound) {
+        Found = true;
+        continue;
+      }
+      // Visit successors if not already and in affected region.
+      if (!Visited.test(s) && Node2Index[s] < UpperBound) {
+        Visited.set(s);
+        WorkList.push_back(Succ);
+      }
+    }
+  } 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 Nodes.
+  WorkList.push_back(&TargetSU);
+  do {
+    const SUnit *SU = WorkList.back();
+    WorkList.pop_back();
+    for (int I = SU->Preds.size()-1; I >= 0; --I) {
+      const SUnit *Pred = SU->Preds[I].getSUnit();
+      unsigned s = Pred->NodeNum;
+      // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
+      if (Pred->isBoundaryNode())
+        continue;
+      if (Node2Index[s] == LowerBound) {
+        Found = true;
+        continue;
+      }
+      if (!VisitedBack.test(s) && Visited.test(s)) {
+        VisitedBack.set(s);
+        WorkList.push_back(Pred);
+        Nodes.push_back(s);
+      }
+    }
+  } while (!WorkList.empty());
+
+  assert(Found && "Error in SUnit Graph!");
+  Success = true;
+  return Nodes;
+}
+
 void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
                                        int UpperBound) {
   std::vector<int> L;
   int shift = 0;
   int i;
 
   for (i = LowerBound; i <= UpperBound; ++i) {
     // w is node at topological index i.