[ScheduleDAGRRList] Recompute topological ordering on demand.

[fhahn]

Summary

Currently there is a single point in ScheduleDAGRRList, where we
actually query the topological order (besides init code). Currently we
are recomputing the order after adding a node (which does not have
predecessors) and then we add predecessors edge-by-edge.

We can avoid adding edges one-by-one after we added a new node. In that case, we can
just rebuild the order from scratch after adding the edges to the DAG
and avoid all the updates to the ordering.

Also, we can delay updating the DAG until we query the DAG, if we keep a
list of added edges. Depending on the number of updates, we can either
apply them when needed or recompute the order from scratch.

This brings down the geomean compile time for of CTMark with -O1 down 0.2% on X86,
with no regressions.

[efriedma]

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

1488 ↗

(On Diff #193275)

Where exactly do we query the topological order relative to this call to fixOrder()? Do we need to fixOrder() inside the loop?

[fhahn]

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

1488 ↗

(On Diff #193275)

We only query it in the loop below (WillCreateCycle call). In case we add new predecessors, we also exit the loop. And we only enter the loop, if there are some interferences. Maybe it's worth adding a comment here?

[efriedma]

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

1488 ↗

(On Diff #193275)

Probably worth adding a comment, yes.

By the way, how frequently do we hit this case in practice?

[fhahn]

Add comment and make even lazier.

[fhahn]

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

1488 ↗

(On Diff #193275)

By the way, how frequently do we hit this case in practice?

I haven't looked at this call here in isolation, but I gather statistics on the impact of the number of InitDAGTopologicalSorting and AddPred calls.

Number of InitDAGTopologicalSorting calls for CTMark, X86, -O1

patch          base

CTMark/kimwitu++/kc.test 25671.0 46740.0
CTMark/Bullet/bullet.test 16228.0 36873.0
CTMark/mafft/pairlocalalign.test 14290.0 28695.0
CTMark/lencod/lencod.test 19006.0 37880.0
CTMark/sqlite3/sqlite3.test 22447.0 49409.0
CTMark/ClamAV/clamscan.test 23087.0. 48369.0
CTMark/7zip/7zip-benchmark.test 41045.0 98737.0
CTMark/tramp3d-v4/tramp3d-v4.test 22057.0 49214.0
CTMark/SPASS/SPASS.test 19596.0 40652.0
CTMark/consumer-typeset/consumer-typeset.test 16567.0 33208.0

Number of AddPred calls for CTMark, X86, -O1

patch       base

CTMark/kimwitu++/kc.test 2645.0 2702.0
CTMark/Bullet/bullet.test 3619.0 3643.0
CTMark/mafft/pairlocalalign.test 3427.0 3455.0
CTMark/lencod/lencod.test 3902.0 4108.0
CTMark/sqlite3/sqlite3.test 3147.0 3179.0
CTMark/ClamAV/clamscan.test 3764.0 3821.0
CTMark/7zip/7zip-benchmark.test 7308.0 7393.0
CTMark/tramp3d-v4/tramp3d-v4.test 4311.0 4315.0
CTMark/SPASS/SPASS.test 4512.0 4577.0
CTMark/consumer-typeset/consumer-typeset.test 3695.0 3734.0

Also, the latest version of the patch improves compile-time on CTMark X86, -O1 a bit more: negative diff means a reduction in compile time.
Program diff
test-suite...ark/tramp3d-v4/tramp3d-v4.test -0.6%
test-suite :: CTMark/Bullet/bullet.test -0.4%
test-suite...:: CTMark/sqlite3/sqlite3.test -0.4%
test-suite :: CTMark/kimwitu++/kc.test -0.4%
test-suite...TMark/7zip/7zip-benchmark.test -0.3%
test-suite :: CTMark/lencod/lencod.test -0.3%
test-suite :: CTMark/SPASS/SPASS.test -0.3%
test-suite...-typeset/consumer-typeset.test -0.3%
test-suite...:: CTMark/ClamAV/clamscan.test -0.2%
test-suite...Mark/mafft/pairlocalalign.test 0.0%
Geomean difference -0.3%

[efriedma]

llvm/lib/CodeGen/ScheduleDAG.cpp

716 ↗

(On Diff #193451)

How terrible would it be to just call fixOrder from here, instead of making the callers check? That makes it impossible for callers to mess up, and the check should be cheap.

I guess it also might be possible to add some cheap checks here to avoid calling fixOrder; for example, if TargetSU has no successors.

[fhahn]

llvm/lib/CodeGen/ScheduleDAG.cpp

716 ↗

(On Diff #193451)

I guess the impact would not be too big, in fact that was what I initially had. I'll measure it and get back. I think it would be OK to push responsibility to the caller in a way and the assertion should catch any errors (the message should probably point to fixOrder()).

[fhahn]

Fix order whenever it is queried.

[fhahn]

llvm/lib/CodeGen/ScheduleDAG.cpp

716 ↗

(On Diff #193451)

I gathered numbers with having FixOrder() in IsReachable & WillCreateCycle. The numbers shifted a bit, but we still have roughly the same overall gain. It seems in some cases one approach is slightly better and for some cases the other one. I guess we should go for the safer one for now?

[efriedma]

LGTM

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

#endif
   /// methods for dynamically updating the ordering as new edges are added.
   ///
   /// This allows a very fast implementation of IsReachable, for example.
   class ScheduleDAGTopologicalSort {
     /// A reference to the ScheduleDAG's SUnits.
     std::vector<SUnit> &SUnits;
     SUnit *ExitSU;
 
+    // Have any new nodes been added?
+    bool Dirty = false;
+
+    // Outstanding added edges, that have not been applied to the ordering.
+    SmallVector<std::pair<SUnit *, SUnit *>, 16> Updates;
+
     /// Maps topological index to the node number.
     std::vector<int> Index2Node;
     /// Maps the node number to its topological index.
     std::vector<int> Node2Index;
     /// a set of nodes visited during a DFS traversal.
     BitVector Visited;
 
     /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
     /// These nodes will later get new topological indexes by means of the Shift
     /// method.
     void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
 
     /// Reassigns topological indexes for the nodes in the DAG to
     /// preserve the topological ordering.
     void Shift(BitVector& Visited, int LowerBound, int UpperBound);
 
     /// Assigns the topological index to the node n.
     void Allocate(int n, int index);
 
+    /// 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);
 
     /// 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);
 
     /// Updates the topological ordering to accommodate an edge to be
     /// added from SUnit \p X to SUnit \p Y.
     void AddPred(SUnit *Y, SUnit *X);
 
+    /// Queues an update to the topological ordering to accommodate an edge to
+    /// be added from SUnit \p X to SUnit \p Y.
+    void AddPredQueued(SUnit *Y, SUnit *X);
+
     /// 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);
 
+    /// Mark the ordering as temporarily broken, after a new node has been
+    /// added.
+    void MarkDirty() { Dirty = true; }
+
     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;

llvm/trunk/lib/CodeGen/ScheduleDAG.cpp

void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
   //
   // The algorithm first computes a topological ordering for the DAG by
   // initializing the Index2Node and Node2Index arrays and then tries to keep
   // the ordering up-to-date after edge insertions by reordering the DAG.
   //
   // On insertion of the edge X->Y, the algorithm first marks by calling DFS
   // the nodes reachable from Y, and then shifts them using Shift to lie
   // immediately after X in Index2Node.
+
+  // Cancel pending updates, mark as valid.
+  Dirty = false;
+  Updates.clear();
+
   unsigned DAGSize = SUnits.size();
   std::vector<SUnit*> WorkList;
   WorkList.reserve(DAGSize);
 
   Index2Node.resize(DAGSize);
   Node2Index.resize(DAGSize);
 
   // Initialize the data structures.
for (SUnit &SU : SUnits)  {
     for (const SDep &PD : SU.Preds) {
       assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&
       "Wrong topological sorting");
     }
   }
 #endif
 }
 
+void ScheduleDAGTopologicalSort::FixOrder() {
+  // Recompute from scratch after new nodes have been added.
+  if (Dirty) {
+    InitDAGTopologicalSorting();
+    return;
+  }
+
+  // Otherwise apply updates one-by-one.
+  for (auto &U : Updates)
+    AddPred(U.first, U.second);
+  Updates.clear();
+}
+
+void ScheduleDAGTopologicalSort::AddPredQueued(SUnit *Y, SUnit *X) {
+  // Recomputing the order from scratch is likely more efficient than applying
+  // updates one-by-one for too many updates. The current cut-off is arbitrarily
+  // chosen.
+  Dirty = Dirty || Updates.size() > 10;
+
+  if (Dirty)
+    return;
+
+  Updates.emplace_back(Y, X);
+}
+
 void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {
   int UpperBound, LowerBound;
   LowerBound = Node2Index[Y->NodeNum];
   UpperBound = Node2Index[X->NodeNum];
   bool HasLoop = false;
   // Is Ord(X) < Ord(Y) ?
   if (LowerBound < UpperBound) {
     // Update the topological order.
void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
 
   for (unsigned LI : L) {
     Allocate(LI, i - shift);
     i = i + 1;
   }
 }
 
 bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {
+  FixOrder();
   // Is SU reachable from TargetSU via successor edges?
   if (IsReachable(SU, TargetSU))
     return true;
   for (const SDep &PredDep : TargetSU->Preds)
     if (PredDep.isAssignedRegDep() &&
         IsReachable(SU, PredDep.getSUnit()))
       return true;
   return false;
 }
 
 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];
   bool HasLoop = false;
   // Is Ord(TargetSU) < Ord(SU) ?
   if (LowerBound < UpperBound) {

llvm/trunk/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

public:
   }
 
   /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
   /// create a cycle.
   bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
     return Topo.WillCreateCycle(SU, TargetSU);
   }
 
+  /// AddPredQueued - Queues and update to add a predecessor edge to SUnit SU.
+  /// This returns true if this is a new predecessor.
+  /// Does *NOT* update the topological ordering! It just queues an update.
+  void AddPredQueued(SUnit *SU, const SDep &D) {
+    Topo.AddPredQueued(SU, D.getSUnit());
+    SU->addPred(D);
+  }
+
   /// AddPred - adds a predecessor edge to SUnit SU.
   /// This returns true if this is a new predecessor.
   /// Updates the topological ordering if required.
   void AddPred(SUnit *SU, const SDep &D) {
     Topo.AddPred(SU, D.getSUnit());
     SU->addPred(D);
   }
 
private:
   bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
 
   void releaseInterferences(unsigned Reg = 0);
 
   SUnit *PickNodeToScheduleBottomUp();
   void ListScheduleBottomUp();
 
   /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
-  /// Updates the topological ordering if required.
   SUnit *CreateNewSUnit(SDNode *N) {
     unsigned NumSUnits = SUnits.size();
     SUnit *NewNode = newSUnit(N);
     // Update the topological ordering.
     if (NewNode->NodeNum >= NumSUnits)
-      Topo.InitDAGTopologicalSorting();
+      Topo.MarkDirty();
     return NewNode;
   }
 
   /// CreateClone - Creates a new SUnit from an existing one.
-  /// Updates the topological ordering if required.
   SUnit *CreateClone(SUnit *N) {
     unsigned NumSUnits = SUnits.size();
     SUnit *NewNode = Clone(N);
     // Update the topological ordering.
     if (NewNode->NodeNum >= NumSUnits)
-      Topo.InitDAGTopologicalSorting();
+      Topo.MarkDirty();
     return NewNode;
   }
 
   /// forceUnitLatencies - Register-pressure-reducing scheduling doesn't
   /// need actual latency information but the hybrid scheduler does.
   bool forceUnitLatencies() const override {
     return !NeedLatency;
   }
void ScheduleDAGRRList::Schedule() {
   LiveRegGens.reset(new SUnit*[TRI->getNumRegs() + 1]());
   CallSeqEndForStart.clear();
   assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
 
   // Build the scheduling graph.
   BuildSchedGraph(nullptr);
 
   LLVM_DEBUG(dump());
-  Topo.InitDAGTopologicalSorting();
+  Topo.MarkDirty();
 
   AvailableQueue->initNodes(SUnits);
 
   HazardRec->Reset();
 
   // Execute the actual scheduling loop.
   ListScheduleBottomUp();
 
SUnit *ScheduleDAGRRList::TryUnfoldSU(SUnit *SU) {
 
   bool isNewN = true;
   SUnit *NewSU;
   // This can only happen when isNewLoad is false.
   if (N->getNodeId() != -1) {
     NewSU = &SUnits[N->getNodeId()];
     // If NewSU has already been scheduled, we need to clone it, but this
     // negates the benefit to unfolding so just return SU.
-    if (NewSU->isScheduled)
+    if (NewSU->isScheduled) {
       return SU;
+    }
     isNewN = false;
   } else {
     NewSU = CreateNewSUnit(N);
     N->setNodeId(NewSU->NodeNum);
 
     const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
     for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
       if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
for (SDep &Succ : SU->Succs) {
     else
       NodeSuccs.push_back(Succ);
   }
 
   // Now assign edges to the newly-created nodes.
   for (const SDep &Pred : ChainPreds) {
     RemovePred(SU, Pred);
     if (isNewLoad)
-      AddPred(LoadSU, Pred);
+      AddPredQueued(LoadSU, Pred);
   }
   for (const SDep &Pred : LoadPreds) {
     RemovePred(SU, Pred);
     if (isNewLoad)
-      AddPred(LoadSU, Pred);
+      AddPredQueued(LoadSU, Pred);
   }
   for (const SDep &Pred : NodePreds) {
     RemovePred(SU, Pred);
-    AddPred(NewSU, Pred);
+    AddPredQueued(NewSU, Pred);
   }
   for (SDep D : NodeSuccs) {
     SUnit *SuccDep = D.getSUnit();
     D.setSUnit(SU);
     RemovePred(SuccDep, D);
     D.setSUnit(NewSU);
-    AddPred(SuccDep, D);
+    AddPredQueued(SuccDep, D);
     // Balance register pressure.
     if (AvailableQueue->tracksRegPressure() && SuccDep->isScheduled &&
         !D.isCtrl() && NewSU->NumRegDefsLeft > 0)
       --NewSU->NumRegDefsLeft;
   }
   for (SDep D : ChainSuccs) {
     SUnit *SuccDep = D.getSUnit();
     D.setSUnit(SU);
     RemovePred(SuccDep, D);
     if (isNewLoad) {
       D.setSUnit(LoadSU);
-      AddPred(SuccDep, D);
+      AddPredQueued(SuccDep, D);
     }
   }
 
   // Add a data dependency to reflect that NewSU reads the value defined
   // by LoadSU.
   SDep D(LoadSU, SDep::Data, 0);
   D.setLatency(LoadSU->Latency);
-  AddPred(NewSU, D);
+  AddPredQueued(NewSU, D);
 
   if (isNewLoad)
     AvailableQueue->addNode(LoadSU);
   if (isNewN)
     AvailableQueue->addNode(NewSU);
 
   ++NumUnfolds;
 
SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
   }
 
   LLVM_DEBUG(dbgs() << "    Duplicating SU #" << SU->NodeNum << "\n");
   NewSU = CreateClone(SU);
 
   // New SUnit has the exact same predecessors.
   for (SDep &Pred : SU->Preds)
     if (!Pred.isArtificial())
-      AddPred(NewSU, Pred);
+      AddPredQueued(NewSU, Pred);
 
   // Only copy scheduled successors. Cut them from old node's successor
   // list and move them over.
   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
   for (SDep &Succ : SU->Succs) {
     if (Succ.isArtificial())
       continue;
     SUnit *SuccSU = Succ.getSUnit();
     if (SuccSU->isScheduled) {
       SDep D = Succ;
       D.setSUnit(NewSU);
-      AddPred(SuccSU, D);
+      AddPredQueued(SuccSU, D);
       D.setSUnit(SU);
       DelDeps.push_back(std::make_pair(SuccSU, D));
     }
   }
   for (auto &DelDep : DelDeps)
     RemovePred(DelDep.first, DelDep.second);
 
   AvailableQueue->updateNode(SU);
void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
   for (SDep &Succ : SU->Succs) {
     if (Succ.isArtificial())
       continue;
     SUnit *SuccSU = Succ.getSUnit();
     if (SuccSU->isScheduled) {
       SDep D = Succ;
       D.setSUnit(CopyToSU);
-      AddPred(SuccSU, D);
+      AddPredQueued(SuccSU, D);
       DelDeps.push_back(std::make_pair(SuccSU, Succ));
     }
     else {
       // Avoid scheduling the def-side copy before other successors. Otherwise
       // we could introduce another physreg interference on the copy and
       // continue inserting copies indefinitely.
-      AddPred(SuccSU, SDep(CopyFromSU, SDep::Artificial));
+      AddPredQueued(SuccSU, SDep(CopyFromSU, SDep::Artificial));
     }
   }
   for (auto &DelDep : DelDeps)
     RemovePred(DelDep.first, DelDep.second);
 
   SDep FromDep(SU, SDep::Data, Reg);
   FromDep.setLatency(SU->Latency);
-  AddPred(CopyFromSU, FromDep);
+  AddPredQueued(CopyFromSU, FromDep);
   SDep ToDep(CopyFromSU, SDep::Data, 0);
   ToDep.setLatency(CopyFromSU->Latency);
-  AddPred(CopyToSU, ToDep);
+  AddPredQueued(CopyToSU, ToDep);
 
   AvailableQueue->updateNode(SU);
   AvailableQueue->addNode(CopyFromSU);
   AvailableQueue->addNode(CopyToSU);
   Copies.push_back(CopyFromSU);
   Copies.push_back(CopyToSU);
 
   ++NumPRCopies;
while (CurSU) {
       }
       CurSU = AvailableQueue->pop();
     }
   };
   FindAvailableNode();
   if (CurSU)
     return CurSU;
 
+  // We query the topological order in the loop body, so make sure outstanding
+  // updates are applied before entering it (we only enter the loop if there
+  // are some interferences). If we make changes to the ordering, we exit
+  // the loop.
+
   // All candidates are delayed due to live physical reg dependencies.
   // Try backtracking, code duplication, or inserting cross class copies
   // to resolve it.
   for (SUnit *TrySU : Interferences) {
     SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
 
     // Try unscheduling up to the point where it's safe to schedule
     // this node.
if (!WillCreateCycle(TrySU, BtSU))  {
       // requires the physical reg dep.
       if (BtSU->isAvailable) {
         BtSU->isAvailable = false;
         if (!BtSU->isPending)
           AvailableQueue->remove(BtSU);
       }
       LLVM_DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum
                         << ") to SU(" << TrySU->NodeNum << ")\n");
-      AddPred(TrySU, SDep(BtSU, SDep::Artificial));
+      AddPredQueued(TrySU, SDep(BtSU, SDep::Artificial));
 
       // If one or more successors has been unscheduled, then the current
       // node is no longer available.
       if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
         LLVM_DEBUG(dbgs() << "TrySU not available; choosing node from queue\n");
         CurSU = AvailableQueue->pop();
       } else {
         LLVM_DEBUG(dbgs() << "TrySU available\n");
if (DestRC != RC) {
         report_fatal_error("Can't handle live physical register dependency!");
     }
     if (!NewDef) {
       // Issue copies, these can be expensive cross register class copies.
       SmallVector<SUnit*, 2> Copies;
       InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
       LLVM_DEBUG(dbgs() << "    Adding an edge from SU #" << TrySU->NodeNum
                         << " to SU #" << Copies.front()->NodeNum << "\n");
-      AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
+      AddPredQueued(TrySU, SDep(Copies.front(), SDep::Artificial));
       NewDef = Copies.back();
     }
 
     LLVM_DEBUG(dbgs() << "    Adding an edge from SU #" << NewDef->NodeNum
                       << " to SU #" << TrySU->NodeNum << "\n");
     LiveRegDefs[Reg] = NewDef;
-    AddPred(NewDef, SDep(TrySU, SDep::Artificial));
+    AddPredQueued(NewDef, SDep(TrySU, SDep::Artificial));
     TrySU->isAvailable = false;
     CurSU = NewDef;
   }
   assert(CurSU && "Unable to resolve live physical register dependencies!");
   return CurSU;
 }
 
 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
LLVM_DEBUG(
                << " to guide scheduling in the presence of multiple uses\n");
     for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
       SDep Edge = PredSU->Succs[i];
       assert(!Edge.isAssignedRegDep());
       SUnit *SuccSU = Edge.getSUnit();
       if (SuccSU != &SU) {
         Edge.setSUnit(PredSU);
         scheduleDAG->RemovePred(SuccSU, Edge);
-        scheduleDAG->AddPred(&SU, Edge);
+        scheduleDAG->AddPredQueued(&SU, Edge);
         Edge.setSUnit(&SU);
-        scheduleDAG->AddPred(SuccSU, Edge);
+        scheduleDAG->AddPredQueued(SuccSU, Edge);
         --i;
       }
     }
   outer_loop_continue:;
   }
 }
 
 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
for (unsigned j = 0; j != NumOps; ++j) {
         if (!canClobberReachingPhysRegUse(SuccSU, &SU, scheduleDAG, TII, TRI) &&
             (!canClobber(SuccSU, DUSU) ||
              (isLiveOut && !hasOnlyLiveOutUses(SuccSU)) ||
              (!SU.isCommutable && SuccSU->isCommutable)) &&
             !scheduleDAG->IsReachable(SuccSU, &SU)) {
           LLVM_DEBUG(dbgs()
                      << "    Adding a pseudo-two-addr edge from SU #"
                      << SU.NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
-          scheduleDAG->AddPred(&SU, SDep(SuccSU, SDep::Artificial));
+          scheduleDAG->AddPredQueued(&SU, SDep(SuccSU, SDep::Artificial));
         }
       }
     }
   }
 }
 
 //===----------------------------------------------------------------------===//
 //                         Public Constructor Functions