diff --git a/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h b/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
--- a/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
+++ b/llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
@@ -346,6 +346,7 @@
     /// True if an edge can be added from PredSU to SuccSU without creating
     /// a cycle.
     bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
+    void MarkDirty() { Topo.MarkDirty(); }
 
     /// Add a DAG edge to the given SU with the given predecessor
     /// dependence data.
diff --git a/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp b/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
--- a/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -969,7 +969,7 @@
   CurrentVRegDefs.clear();
   CurrentVRegUses.clear();
 
-  Topo.InitDAGTopologicalSorting();
+  Topo.MarkDirty();
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) {
@@ -1158,7 +1158,7 @@
     // If Pred is reachable from Succ, then the edge creates a cycle.
     if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
       return false;
-    Topo.AddPred(SuccSU, PredDep.getSUnit());
+    Topo.AddPredQueued(SuccSU, PredDep.getSUnit());
   }
   SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
   // Return true regardless of whether a new edge needed to be inserted.