| ScheduleDAG.cpp (208954) | ScheduleDAG.cpp (210299) |
|---|---|
| 1//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// --- 366 unchanged lines hidden (view full) --- 375 if (!Sequence[i]) 376 ++Noops; 377 assert(!AnyNotSched); 378 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 379 "The number of nodes scheduled doesn't match the expected number!"); 380} 381#endif 382 | 1//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// --- 366 unchanged lines hidden (view full) --- 375 if (!Sequence[i]) 376 ++Noops; 377 assert(!AnyNotSched); 378 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 379 "The number of nodes scheduled doesn't match the expected number!"); 380} 381#endif 382 |
| 383/// InitDAGTopologicalSorting - create the initial topological | 383/// InitDAGTopologicalSorting - create the initial topological |
| 384/// ordering from the DAG to be scheduled. 385/// | 384/// ordering from the DAG to be scheduled. 385/// |
| 386/// The idea of the algorithm is taken from | 386/// The idea of the algorithm is taken from |
| 387/// "Online algorithms for managing the topological order of 388/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly | 387/// "Online algorithms for managing the topological order of 388/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly |
| 389/// This is the MNR algorithm, which was first introduced by 390/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in | 389/// This is the MNR algorithm, which was first introduced by 390/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in |
| 391/// "Maintaining a topological order under edge insertions". 392/// | 391/// "Maintaining a topological order under edge insertions". 392/// |
| 393/// Short description of the algorithm: | 393/// Short description of the algorithm: |
| 394/// 395/// Topological ordering, ord, of a DAG maps each node to a topological 396/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 397/// | 394/// 395/// Topological ordering, ord, of a DAG maps each node to a topological 396/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 397/// |
| 398/// This means that if there is a path from the node X to the node Z, | 398/// This means that if there is a path from the node X to the node Z, |
| 399/// then ord(X) < ord(Z). 400/// 401/// This property can be used to check for reachability of nodes: | 399/// then ord(X) < ord(Z). 400/// 401/// This property can be used to check for reachability of nodes: |
| 402/// if Z is reachable from X, then an insertion of the edge Z->X would | 402/// if Z is reachable from X, then an insertion of the edge Z->X would |
| 403/// create a cycle. 404/// 405/// The algorithm first computes a topological ordering for the DAG by 406/// initializing the Index2Node and Node2Index arrays and then tries to keep 407/// the ordering up-to-date after edge insertions by reordering the DAG. 408/// 409/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 410/// the nodes reachable from Y, and then shifts them using Shift to lie --- 15 unchanged lines hidden (view full) --- 426 Node2Index[NodeNum] = Degree; 427 428 // Is it a node without dependencies? 429 if (Degree == 0) { 430 assert(SU->Succs.empty() && "SUnit should have no successors"); 431 // Collect leaf nodes. 432 WorkList.push_back(SU); 433 } | 403/// create a cycle. 404/// 405/// The algorithm first computes a topological ordering for the DAG by 406/// initializing the Index2Node and Node2Index arrays and then tries to keep 407/// the ordering up-to-date after edge insertions by reordering the DAG. 408/// 409/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 410/// the nodes reachable from Y, and then shifts them using Shift to lie --- 15 unchanged lines hidden (view full) --- 426 Node2Index[NodeNum] = Degree; 427 428 // Is it a node without dependencies? 429 if (Degree == 0) { 430 assert(SU->Succs.empty() && "SUnit should have no successors"); 431 // Collect leaf nodes. 432 WorkList.push_back(SU); 433 } |
| 434 } | 434 } |
| 435 436 int Id = DAGSize; 437 while (!WorkList.empty()) { 438 SUnit *SU = WorkList.back(); 439 WorkList.pop_back(); 440 Allocate(SU->NodeNum, --Id); 441 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 442 I != E; ++I) { --- 8 unchanged lines hidden (view full) --- 451 Visited.resize(DAGSize); 452 453#ifndef NDEBUG 454 // Check correctness of the ordering 455 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 456 SUnit *SU = &SUnits[i]; 457 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 458 I != E; ++I) { | 435 436 int Id = DAGSize; 437 while (!WorkList.empty()) { 438 SUnit *SU = WorkList.back(); 439 WorkList.pop_back(); 440 Allocate(SU->NodeNum, --Id); 441 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 442 I != E; ++I) { --- 8 unchanged lines hidden (view full) --- 451 Visited.resize(DAGSize); 452 453#ifndef NDEBUG 454 // Check correctness of the ordering 455 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 456 SUnit *SU = &SUnits[i]; 457 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 458 I != E; ++I) { |
| 459 assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && | 459 assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && |
| 460 "Wrong topological sorting"); 461 } 462 } 463#endif 464} 465 466/// AddPred - Updates the topological ordering to accomodate an edge 467/// to be added from SUnit X to SUnit Y. --- 21 unchanged lines hidden (view full) --- 489} 490 491/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 492/// all nodes affected by the edge insertion. These nodes will later get new 493/// topological indexes by means of the Shift method. 494void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 495 bool& HasLoop) { 496 std::vector<const SUnit*> WorkList; | 460 "Wrong topological sorting"); 461 } 462 } 463#endif 464} 465 466/// AddPred - Updates the topological ordering to accomodate an edge 467/// to be added from SUnit X to SUnit Y. --- 21 unchanged lines hidden (view full) --- 489} 490 491/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 492/// all nodes affected by the edge insertion. These nodes will later get new 493/// topological indexes by means of the Shift method. 494void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 495 bool& HasLoop) { 496 std::vector<const SUnit*> WorkList; |
| 497 WorkList.reserve(SUnits.size()); | 497 WorkList.reserve(SUnits.size()); |
| 498 499 WorkList.push_back(SU); 500 do { 501 SU = WorkList.back(); 502 WorkList.pop_back(); 503 Visited.set(SU->NodeNum); 504 for (int I = SU->Succs.size()-1; I >= 0; --I) { 505 int s = SU->Succs[I].getSUnit()->NodeNum; 506 if (Node2Index[s] == UpperBound) { | 498 499 WorkList.push_back(SU); 500 do { 501 SU = WorkList.back(); 502 WorkList.pop_back(); 503 Visited.set(SU->NodeNum); 504 for (int I = SU->Succs.size()-1; I >= 0; --I) { 505 int s = SU->Succs[I].getSUnit()->NodeNum; 506 if (Node2Index[s] == UpperBound) { |
| 507 HasLoop = true; | 507 HasLoop = true; |
| 508 return; 509 } 510 // Visit successors if not already and in affected region. 511 if (!Visited.test(s) && Node2Index[s] < UpperBound) { 512 WorkList.push_back(SU->Succs[I].getSUnit()); | 508 return; 509 } 510 // Visit successors if not already and in affected region. 511 if (!Visited.test(s) && Node2Index[s] < UpperBound) { 512 WorkList.push_back(SU->Succs[I].getSUnit()); |
| 513 } 514 } | 513 } 514 } |
| 515 } while (!WorkList.empty()); 516} 517 | 515 } while (!WorkList.empty()); 516} 517 |
| 518/// Shift - Renumber the nodes so that the topological ordering is | 518/// Shift - Renumber the nodes so that the topological ordering is |
| 519/// preserved. | 519/// preserved. |
| 520void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, | 520void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, |
| 521 int UpperBound) { 522 std::vector<int> L; 523 int shift = 0; 524 int i; 525 526 for (i = LowerBound; i <= UpperBound; ++i) { 527 // w is node at topological index i. 528 int w = Index2Node[i]; --- 34 unchanged lines hidden (view full) --- 563 // then there is a path from TargetSU to SU. 564 int UpperBound, LowerBound; 565 LowerBound = Node2Index[TargetSU->NodeNum]; 566 UpperBound = Node2Index[SU->NodeNum]; 567 bool HasLoop = false; 568 // Is Ord(TargetSU) < Ord(SU) ? 569 if (LowerBound < UpperBound) { 570 Visited.reset(); | 521 int UpperBound) { 522 std::vector<int> L; 523 int shift = 0; 524 int i; 525 526 for (i = LowerBound; i <= UpperBound; ++i) { 527 // w is node at topological index i. 528 int w = Index2Node[i]; --- 34 unchanged lines hidden (view full) --- 563 // then there is a path from TargetSU to SU. 564 int UpperBound, LowerBound; 565 LowerBound = Node2Index[TargetSU->NodeNum]; 566 UpperBound = Node2Index[SU->NodeNum]; 567 bool HasLoop = false; 568 // Is Ord(TargetSU) < Ord(SU) ? 569 if (LowerBound < UpperBound) { 570 Visited.reset(); |
| 571 // There may be a path from TargetSU to SU. Check for it. | 571 // There may be a path from TargetSU to SU. Check for it. |
| 572 DFS(TargetSU, UpperBound, HasLoop); 573 } 574 return HasLoop; 575} 576 577/// Allocate - assign the topological index to the node n. 578void ScheduleDAGTopologicalSort::Allocate(int n, int index) { 579 Node2Index[n] = index; 580 Index2Node[index] = n; 581} 582 | 572 DFS(TargetSU, UpperBound, HasLoop); 573 } 574 return HasLoop; 575} 576 577/// Allocate - assign the topological index to the node n. 578void ScheduleDAGTopologicalSort::Allocate(int n, int index) { 579 Node2Index[n] = index; 580 Index2Node[index] = n; 581} 582 |
| 583ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort( 584 std::vector<SUnit> &sunits) 585 : SUnits(sunits) {} | 583ScheduleDAGTopologicalSort:: 584ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits) : SUnits(sunits) {} |
| 586 587ScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} | 585 586ScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} |