MachineScheduler/ScheduleDAG: Add support for getSUTopoIndex

[axeldavy]

Summary

Add support for getSUTopoIndex to ScheduleDAGTopologicalSort.
Node2Index is a topological sort on the SUs.
getSUTopoIndex returns Node2Index[SU->NodeNum] (when not boundary SU),
which is the topological index in the topological sort of ScheduleDAGTopologicalSort.

I would like to use Node2Index in my updated register tracking for D31124.

[MatzeB]

• Choose a better function name!
• Now that the function is public you should also document some facts about it like what to use as index into the vector or the range of indizes coming out of it.
• Instead of returning const vector<int>& better use ArrayRef<int> as that gives less constraints on the internal implementation.
• Is it necessary to return the array as a whole or would a simpler function suffice that takes a single const SUnit& and returns the index into the corresponding topological ordering?

[axeldavy]

In D31587#716821, @MatzeB wrote:

• Choose a better function name!

getTopoIndexes ?

• Now that the function is public you should also document some facts about it like what to use as index into the vector or the range of indizes coming out of it.

What about:
/ / / Node2Index[SU->NodeNum] (when not boundary SU) gives the topological index in the topological sort of ScheduleDAGTopologicalSort.
/ / / The index is contained between 0 and SUnits.count()-1

• Instead of returning const vector<int>& better use ArrayRef<int> as that gives less constraints on the internal implementation.

Ok

• Is it necessary to return the array as a whole or would a simpler function suffice that takes a single const SUnit& and returns the index into the corresponding topological ordering?

No, I'd be fine with a function returning Node2Index[SU->NodeNum]. Do you think a function would be preferable ?
One worry is that if we write a function that takes SU and returns the index, it'd likely have to check for boundaries every call.

[MatzeB]

In D31587#717117, @axeldavy wrote:

In D31587#716821, @MatzeB wrote:

• Choose a better function name!

getTopoIndexes ?

• Now that the function is public you should also document some facts about it like what to use as index into the vector or the range of indizes coming out of it.

What about:
/ / / Node2Index[SU->NodeNum] (when not boundary SU) gives the topological index in the topological sort of ScheduleDAGTopologicalSort.
/ / / The index is contained between 0 and SUnits.count()-1

• Instead of returning const vector<int>& better use ArrayRef<int> as that gives less constraints on the internal implementation.

Ok

• Is it necessary to return the array as a whole or would a simpler function suffice that takes a single const SUnit& and returns the index into the corresponding topological ordering?

No, I'd be fine with a function returning Node2Index[SU->NodeNum]. Do you think a function would be preferable ?
One worry is that if we write a function that takes SU and returns the index, it'd likely have to check for boundaries every call.

The function would not expose the fact that we currently have an underlying std::vector to the API (ArrayRef makes it slightly better but it still forces the implementation to use some form of array). So if the function works as well I would prefer that.

As for performance you would perform the bound checks in an assert() so they are not present in a release compiler.

[MatzeB]

In D31587#717117, @axeldavy wrote:

In D31587#716821, @MatzeB wrote:

• Choose a better function name!

getTopoIndexes ?

that sounds better.

• Now that the function is public you should also document some facts about it like what to use as index into the vector or the range of indizes coming out of it.

What about:
/ / / Node2Index[SU->NodeNum] (when not boundary SU) gives the topological index in the topological sort of ScheduleDAGTopologicalSort.
/ / / The index is contained between 0 and SUnits.count()-1

Maybe "Maps an SUnit node number to indexes of a topological ordering. The index is between 0 and SUnits.count()-1. Boundary SUnits are not mapped."

• Instead of returning const vector<int>& better use ArrayRef<int> as that gives less constraints on the internal implementation.

Ok

• Is it necessary to return the array as a whole or would a simpler function suffice that takes a single const SUnit& and returns the index into the corresponding topological ordering?

No, I'd be fine with a function returning Node2Index[SU->NodeNum]. Do you think a function would be preferable ?
One worry is that if we write a function that takes SU and returns the index, it'd likely have to check for boundaries every call.

[axeldavy]

Replaced getNode2Index by getSUTopoIndex, and completed documentation.

[axeldavy]

Bad diff uploaded. This is the correct diff.

[axeldavy]

I made the input const.
Should the result be const as well ?

[MatzeB]

LGTM.

Should the result be const as well ?

The result is passed by value so no need for const (it wouldn't change anything). You should make the getSUTopoIndex() method const though.

[vpykhtin]

LGTM.

include/llvm/CodeGen/ScheduleDAG.h

public:
     /// added from SUnit \p X to SUnit \p Y.
     void AddPred(SUnit *Y, SUnit *X);
 
     /// \brief Updates the topological ordering to accommodate an an edge to be
     /// removed from the specified node \p N from the predecessors of the
     /// current node \p M.
     void RemovePred(SUnit *M, SUnit *N);
 
+    /// Maps SUnits to indexes of a topological ordering.
+    /// The index is between 0 and SUnits.count()-1.
+    /// Boundary SUnits are not mapped.
+    int getSUTopoIndex(const SUnit &SU);
+
     typedef std::vector<int>::iterator iterator;
     typedef std::vector<int>::const_iterator const_iterator;
     iterator begin() { return Index2Node.begin(); }
     const_iterator begin() const { return Index2Node.begin(); }
     iterator end() { return Index2Node.end(); }
     const_iterator end() const { return Index2Node.end(); }
 
     typedef std::vector<int>::reverse_iterator reverse_iterator;

lib/CodeGen/ScheduleDAG.cpp

bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
   if (LowerBound < UpperBound) {
     Visited.reset();
     // There may be a path from TargetSU to SU. Check for it.
     DFS(TargetSU, UpperBound, HasLoop);
   }
   return HasLoop;
 }
 
+int ScheduleDAGTopologicalSort::getSUTopoIndex(const SUnit &SU)
+{
+  assert(!SU.isBoundaryNode());
+  return Node2Index[SU.NodeNum];
+}
+
 void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
   Node2Index[n] = index;
   Index2Node[index] = n;
 }
 
 ScheduleDAGTopologicalSort::
 ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
   : SUnits(sunits), ExitSU(exitsu) {}
 
 ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;