+/// InitDAGTopologicalSorting - create the initial topological
+/// ordering from the DAG to be scheduled.
+void ScheduleDAGRRList::InitDAGTopologicalSorting() {
+ unsigned DAGSize = SUnits.size();
+ std::vector<unsigned> InDegree(DAGSize);
+ std::vector<SUnit*> WorkList;
+ WorkList.reserve(DAGSize);
+ std::vector<SUnit*> TopOrder;
+ TopOrder.reserve(DAGSize);
+
+ // Initialize the data structures.
+ for (unsigned i = 0, e = DAGSize; i != e; ++i) {
+ SUnit *SU = &SUnits[i];
+ int NodeNum = SU->NodeNum;
+ unsigned Degree = SU->Succs.size();
+ InDegree[NodeNum] = Degree;
+
+ // Is it a node without dependencies?
+ if (Degree == 0) {
+ assert(SU->Succs.empty() && "SUnit should have no successors");
+ // Collect leaf nodes.
+ WorkList.push_back(SU);
+ }
+ }
+
+ while (!WorkList.empty()) {
+ SUnit *SU = WorkList.back();
+ WorkList.pop_back();
+ TopOrder.push_back(SU);
+ for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+ I != E; ++I) {
+ SUnit *SU = I->Dep;
+ if (!--InDegree[SU->NodeNum])
+ // If all dependencies of the node are processed already,
+ // then the node can be computed now.
+ WorkList.push_back(SU);
+ }
+ }
+
+ // Second pass, assign the actual topological order as node ids.
+ int Id = 0;
+
+ Index2Node.clear();
+ Node2Index.clear();
+ Index2Node.resize(DAGSize);
+ Node2Index.resize(DAGSize);
+ Visited.resize(DAGSize);
+
+ for (std::vector<SUnit*>::reverse_iterator TI = TopOrder.rbegin(),
+ TE = TopOrder.rend();TI != TE; ++TI) {
+ Allocate((*TI)->NodeNum, Id);
+ Id++;
+ }
+
+#ifndef NDEBUG
+ // Check correctness of the ordering
+ for (unsigned i = 0, e = DAGSize; i != e; ++i) {
+ SUnit *SU = &SUnits[i];
+ for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+ I != E; ++I) {
+ assert(Node2Index[SU->NodeNum] > Node2Index[I->Dep->NodeNum] &&
+ "Wrong topological sorting");
+ }
+ }
+#endif
+}
+
+/// AddPred - adds an edge from SUnit X to SUnit Y.
+/// Updates the topological ordering if required.
+bool ScheduleDAGRRList::AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isSpecial,
+ unsigned PhyReg, int Cost) {
+ 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.
+ Visited.reset();
+ DFS(Y, UpperBound, HasLoop);
+ assert(!HasLoop && "Inserted edge creates a loop!");
+ // Recompute topological indexes.
+ Shift(Visited, LowerBound, UpperBound);
+ }
+ // Now really insert the edge.
+ return Y->addPred(X, isCtrl, isSpecial, PhyReg, Cost);
+}
+
+/// RemovePred - This removes the specified node N from the predecessors of
+/// the current node M. Updates the topological ordering if required.
+bool ScheduleDAGRRList::RemovePred(SUnit *M, SUnit *N,
+ bool isCtrl, bool isSpecial) {
+ // InitDAGTopologicalSorting();
+ return M->removePred(N, isCtrl, isSpecial);
+}
+
+/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark
+/// all nodes affected by the edge insertion. These nodes will later get new
+/// topological indexes by means of the Shift method.
+void ScheduleDAGRRList::DFS(SUnit *SU, int UpperBound, bool& HasLoop) {
+ std::vector<SUnit*> WorkList;
+ WorkList.reserve(SUnits.size());
+
+ WorkList.push_back(SU);
+ while (!WorkList.empty()) {
+ SU = WorkList.back();
+ WorkList.pop_back();
+ Visited.set(SU->NodeNum);
+ for (int I = SU->Succs.size()-1; I >= 0; --I) {
+ int s = SU->Succs[I].Dep->NodeNum;
+ if (Node2Index[s] == UpperBound) {
+ HasLoop = true;
+ return;
+ }
+ // Visit successors if not already and in affected region.
+ if (!Visited.test(s) && Node2Index[s] < UpperBound) {
+ WorkList.push_back(SU->Succs[I].Dep);
+ }
+ }
+ }
+}
+
+/// Shift - Renumber the nodes so that the topological ordering is
+/// preserved.
+void ScheduleDAGRRList::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.
+ int w = Index2Node[i];
+ if (Visited.test(w)) {
+ // Unmark.
+ Visited.reset(w);
+ L.push_back(w);
+ shift = shift + 1;
+ } else {
+ Allocate(w, i - shift);
+ }
+ }
+
+ for (unsigned j = 0; j < L.size(); ++j) {
+ Allocate(L[j], i - shift);
+ i = i + 1;
+ }