[ScheduleDAG] Avoid unnecessary recomputation of topological order.

[fhahn]

Summary

In some cases ScheduleDAGRRList has to add new nodes to resolve problems
with interfering physical registers. When new nodes are added, it
completely re-computes the topological order, which can take a long
time, but is unnecessary. We only add nodes one by one, and initially
they do not have any predecessors. So we can just insert them at the end
of the vector. Later we add predecessors, but the helper function
properly updates the topological order much more efficiently. With this
change, the compile time for the program below drops from 300s to 30s on
my machine.

define i11129 @test1() {
  %L1 = load i11129, i11129* undef
  %B30 = ashr i11129 %L1, %L1
  store i11129 %B30, i11129* undef
  ret i11129 %L1
}

This should be generally beneficial, as we can skip a large amount of
work. Theoretically there are some scenarios where we might not safe
much, e.g. when we add a dependency between the first and last node.
Then we would have to shift all nodes. But we still do not have to spend
the time re-computing the initial order.

[paquette]

LGTM

Out of curiosity, do you have any numbers for how this impacts compile time on, say, CTMark? What percentage of an improvement can we expect from this?

[fhahn]

In D59722#1440346, @paquette wrote:

LGTM

Out of curiosity, do you have any numbers for how this impacts compile time on, say, CTMark? What percentage of an improvement can we expect from this?

I ran CTmark in a few configurations on X86 (-O3 X86, -O0 X86, -O3 + LTO ARM64) and overall it seems neutral: some gains and losses up to 0.5%, but that's also the run-to-run difference on some runs on my machine.

[fhahn]

After a bit more benchmarking, I think this patch makes things slightly worse in the general case. I've put up a patch that updates ScheduleDAGRRList to update the topological order on demand, D60125, which gives small, but stable improvements on CTMark. I have to revisit this patch and see how we can deal with extreme cases, without making things worse in the general case.

[fhahn]

In D59722#1451350, @fhahn wrote:

After a bit more benchmarking, I think this patch makes things slightly worse in the general case. I've put up a patch that updates ScheduleDAGRRList to update the topological order on demand, D60125, which gives small, but stable improvements on CTMark. I have to revisit this patch and see how we can deal with extreme cases, without making things worse in the general case.

Just benchmark again, it looks like currently there are a few clear improvements and no real regressions: http://llvm-compile-time-tracker.com/compare.php?from=7873376bb36b4f9646fbc26d6da88e2edbf796e4&to=d44cb1460dd6ccad74ea96ce295d804f9e291bf3&stat=instructions

I'll land the patch shortly.

llvm/include/llvm/CodeGen/ScheduleDAG.h

class ScheduleDAGTopologicalSort {
     /// Fix the ordering, by either recomputing from scratch or by applying
     /// any outstanding updates. Uses a heuristic to estimate what will be
     /// cheaper.
     void FixOrder();
 
   public:
     ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
 
+    /// Add a SUnit without predecessors to the end of the topological order. It
+    /// also must be the first new node added to the DAG.
+    void AddSUnitWithoutPredecessors(const SUnit *SU);
+
     /// 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.

llvm/lib/CodeGen/ScheduleDAG.cpp

if (IsReachable(SU, TargetSU))
     return true;
   for (const SDep &PredDep : TargetSU->Preds)
     if (PredDep.isAssignedRegDep() &&
         IsReachable(SU, PredDep.getSUnit()))
       return true;
   return false;
 }
 
+void ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors(const SUnit *SU) {
+  assert(SU->NodeNum == Index2Node.size() && "Node cannot be added at the end");
+  assert(SU->NumPreds == 0 && "Can only add SU's with no predecessors");
+  Node2Index.push_back(Index2Node.size());
+  Index2Node.push_back(SU->NodeNum);
+  Visited.resize(Node2Index.size());
+}
+
 bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
                                              const SUnit *TargetSU) {
   FixOrder();
   // If insertion of the edge SU->TargetSU would create a cycle
   // then there is a path from TargetSU to SU.
   int UpperBound, LowerBound;
   LowerBound = Node2Index[TargetSU->NodeNum];
   UpperBound = Node2Index[SU->NodeNum];

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

private:
   void ListScheduleBottomUp();
 
   /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
   SUnit *CreateNewSUnit(SDNode *N) {
     unsigned NumSUnits = SUnits.size();
     SUnit *NewNode = newSUnit(N);
     // Update the topological ordering.
     if (NewNode->NodeNum >= NumSUnits)
-      Topo.MarkDirty();
+      Topo.AddSUnitWithoutPredecessors(NewNode);
     return NewNode;
   }
 
   /// CreateClone - Creates a new SUnit from an existing one.
   SUnit *CreateClone(SUnit *N) {
     unsigned NumSUnits = SUnits.size();
     SUnit *NewNode = Clone(N);
     // Update the topological ordering.
     if (NewNode->NodeNum >= NumSUnits)
-      Topo.MarkDirty();
+      Topo.AddSUnitWithoutPredecessors(NewNode);
     return NewNode;
   }
 
   /// forceUnitLatencies - Register-pressure-reducing scheduling doesn't
   /// need actual latency information but the hybrid scheduler does.
   bool forceUnitLatencies() const override {
     return !NeedLatency;
   }