ScheduleDAG.cpp revision 5cffa6fe271351a8fd80e7767b5d61a999acfa9b
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//===----------------------------------------------------------------------===// 9// 10// This implements the ScheduleDAG class, which is a base class used by 11// scheduling implementation classes. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "pre-RA-sched" 16#include "llvm/CodeGen/ScheduleDAG.h" 17#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 18#include "llvm/Target/TargetMachine.h" 19#include "llvm/Target/TargetInstrInfo.h" 20#include "llvm/Target/TargetRegisterInfo.h" 21#include "llvm/Support/Debug.h" 22#include <climits> 23using namespace llvm; 24 25ScheduleDAG::ScheduleDAG(MachineFunction &mf) 26 : DAG(0), BB(0), TM(mf.getTarget()), 27 TII(TM.getInstrInfo()), 28 TRI(TM.getRegisterInfo()), 29 TLI(TM.getTargetLowering()), 30 MF(mf), MRI(mf.getRegInfo()), 31 ConstPool(MF.getConstantPool()), 32 EntrySU(), ExitSU() { 33} 34 35ScheduleDAG::~ScheduleDAG() {} 36 37/// dump - dump the schedule. 38void ScheduleDAG::dumpSchedule() const { 39 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 40 if (SUnit *SU = Sequence[i]) 41 SU->dump(this); 42 else 43 cerr << "**** NOOP ****\n"; 44 } 45} 46 47 48/// Run - perform scheduling. 49/// 50void ScheduleDAG::Run(SelectionDAG *dag, MachineBasicBlock *bb, 51 MachineBasicBlock::iterator begin, 52 MachineBasicBlock::iterator end) { 53 assert((!dag || begin == end) && 54 "An instruction range was given for SelectionDAG scheduling!"); 55 56 SUnits.clear(); 57 Sequence.clear(); 58 DAG = dag; 59 BB = bb; 60 Begin = begin; 61 End = end; 62 EntrySU = SUnit(); 63 ExitSU = SUnit(); 64 65 Schedule(); 66 67 DOUT << "*** Final schedule ***\n"; 68 DEBUG(dumpSchedule()); 69 DOUT << "\n"; 70} 71 72/// addPred - This adds the specified edge as a pred of the current node if 73/// not already. It also adds the current node as a successor of the 74/// specified node. 75void SUnit::addPred(const SDep &D) { 76 // If this node already has this depenence, don't add a redundant one. 77 for (SmallVector<SDep, 4>::const_iterator I = Preds.begin(), E = Preds.end(); 78 I != E; ++I) 79 if (*I == D) 80 return; 81 // Now add a corresponding succ to N. 82 SDep P = D; 83 P.setSUnit(this); 84 SUnit *N = D.getSUnit(); 85 // Update the bookkeeping. 86 if (D.getKind() == SDep::Data) { 87 ++NumPreds; 88 ++N->NumSuccs; 89 } 90 if (!N->isScheduled) 91 ++NumPredsLeft; 92 if (!isScheduled) 93 ++N->NumSuccsLeft; 94 Preds.push_back(D); 95 N->Succs.push_back(P); 96 if (P.getLatency() != 0) { 97 this->setDepthDirty(); 98 N->setHeightDirty(); 99 } 100} 101 102/// removePred - This removes the specified edge as a pred of the current 103/// node if it exists. It also removes the current node as a successor of 104/// the specified node. 105void SUnit::removePred(const SDep &D) { 106 // Find the matching predecessor. 107 for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 108 I != E; ++I) 109 if (*I == D) { 110 bool FoundSucc = false; 111 // Find the corresponding successor in N. 112 SDep P = D; 113 P.setSUnit(this); 114 SUnit *N = D.getSUnit(); 115 for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(), 116 EE = N->Succs.end(); II != EE; ++II) 117 if (*II == P) { 118 FoundSucc = true; 119 N->Succs.erase(II); 120 break; 121 } 122 assert(FoundSucc && "Mismatching preds / succs lists!"); 123 Preds.erase(I); 124 // Update the bookkeeping. 125 if (P.getKind() == SDep::Data) { 126 --NumPreds; 127 --N->NumSuccs; 128 } 129 if (!N->isScheduled) 130 --NumPredsLeft; 131 if (!isScheduled) 132 --N->NumSuccsLeft; 133 if (P.getLatency() != 0) { 134 this->setDepthDirty(); 135 N->setHeightDirty(); 136 } 137 return; 138 } 139} 140 141void SUnit::setDepthDirty() { 142 if (!isDepthCurrent) return; 143 SmallVector<SUnit*, 8> WorkList; 144 WorkList.push_back(this); 145 do { 146 SUnit *SU = WorkList.pop_back_val(); 147 SU->isDepthCurrent = false; 148 for (SUnit::const_succ_iterator I = SU->Succs.begin(), 149 E = SU->Succs.end(); I != E; ++I) { 150 SUnit *SuccSU = I->getSUnit(); 151 if (SuccSU->isDepthCurrent) 152 WorkList.push_back(SuccSU); 153 } 154 } while (!WorkList.empty()); 155} 156 157void SUnit::setHeightDirty() { 158 if (!isHeightCurrent) return; 159 SmallVector<SUnit*, 8> WorkList; 160 WorkList.push_back(this); 161 do { 162 SUnit *SU = WorkList.pop_back_val(); 163 SU->isHeightCurrent = false; 164 for (SUnit::const_pred_iterator I = SU->Preds.begin(), 165 E = SU->Preds.end(); I != E; ++I) { 166 SUnit *PredSU = I->getSUnit(); 167 if (PredSU->isHeightCurrent) 168 WorkList.push_back(PredSU); 169 } 170 } while (!WorkList.empty()); 171} 172 173/// setDepthToAtLeast - Update this node's successors to reflect the 174/// fact that this node's depth just increased. 175/// 176void SUnit::setDepthToAtLeast(unsigned NewDepth) { 177 if (NewDepth <= getDepth()) 178 return; 179 setDepthDirty(); 180 Depth = NewDepth; 181 isDepthCurrent = true; 182} 183 184/// setHeightToAtLeast - Update this node's predecessors to reflect the 185/// fact that this node's height just increased. 186/// 187void SUnit::setHeightToAtLeast(unsigned NewHeight) { 188 if (NewHeight <= getHeight()) 189 return; 190 setHeightDirty(); 191 Height = NewHeight; 192 isHeightCurrent = true; 193} 194 195/// ComputeDepth - Calculate the maximal path from the node to the exit. 196/// 197void SUnit::ComputeDepth() { 198 SmallVector<SUnit*, 8> WorkList; 199 WorkList.push_back(this); 200 do { 201 SUnit *Cur = WorkList.back(); 202 203 bool Done = true; 204 unsigned MaxPredDepth = 0; 205 for (SUnit::const_pred_iterator I = Cur->Preds.begin(), 206 E = Cur->Preds.end(); I != E; ++I) { 207 SUnit *PredSU = I->getSUnit(); 208 if (PredSU->isDepthCurrent) 209 MaxPredDepth = std::max(MaxPredDepth, 210 PredSU->Depth + I->getLatency()); 211 else { 212 Done = false; 213 WorkList.push_back(PredSU); 214 } 215 } 216 217 if (Done) { 218 WorkList.pop_back(); 219 if (MaxPredDepth != Cur->Depth) { 220 Cur->setDepthDirty(); 221 Cur->Depth = MaxPredDepth; 222 } 223 Cur->isDepthCurrent = true; 224 } 225 } while (!WorkList.empty()); 226} 227 228/// ComputeHeight - Calculate the maximal path from the node to the entry. 229/// 230void SUnit::ComputeHeight() { 231 SmallVector<SUnit*, 8> WorkList; 232 WorkList.push_back(this); 233 do { 234 SUnit *Cur = WorkList.back(); 235 236 bool Done = true; 237 unsigned MaxSuccHeight = 0; 238 for (SUnit::const_succ_iterator I = Cur->Succs.begin(), 239 E = Cur->Succs.end(); I != E; ++I) { 240 SUnit *SuccSU = I->getSUnit(); 241 if (SuccSU->isHeightCurrent) 242 MaxSuccHeight = std::max(MaxSuccHeight, 243 SuccSU->Height + I->getLatency()); 244 else { 245 Done = false; 246 WorkList.push_back(SuccSU); 247 } 248 } 249 250 if (Done) { 251 WorkList.pop_back(); 252 if (MaxSuccHeight != Cur->Height) { 253 Cur->setHeightDirty(); 254 Cur->Height = MaxSuccHeight; 255 } 256 Cur->isHeightCurrent = true; 257 } 258 } while (!WorkList.empty()); 259} 260 261/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 262/// a group of nodes flagged together. 263void SUnit::dump(const ScheduleDAG *G) const { 264 cerr << "SU(" << NodeNum << "): "; 265 G->dumpNode(this); 266} 267 268void SUnit::dumpAll(const ScheduleDAG *G) const { 269 dump(G); 270 271 cerr << " # preds left : " << NumPredsLeft << "\n"; 272 cerr << " # succs left : " << NumSuccsLeft << "\n"; 273 cerr << " Latency : " << Latency << "\n"; 274 cerr << " Depth : " << Depth << "\n"; 275 cerr << " Height : " << Height << "\n"; 276 277 if (Preds.size() != 0) { 278 cerr << " Predecessors:\n"; 279 for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 280 I != E; ++I) { 281 cerr << " "; 282 switch (I->getKind()) { 283 case SDep::Data: cerr << "val "; break; 284 case SDep::Anti: cerr << "anti"; break; 285 case SDep::Output: cerr << "out "; break; 286 case SDep::Order: cerr << "ch "; break; 287 } 288 cerr << "#"; 289 cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 290 if (I->isArtificial()) 291 cerr << " *"; 292 cerr << "\n"; 293 } 294 } 295 if (Succs.size() != 0) { 296 cerr << " Successors:\n"; 297 for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); 298 I != E; ++I) { 299 cerr << " "; 300 switch (I->getKind()) { 301 case SDep::Data: cerr << "val "; break; 302 case SDep::Anti: cerr << "anti"; break; 303 case SDep::Output: cerr << "out "; break; 304 case SDep::Order: cerr << "ch "; break; 305 } 306 cerr << "#"; 307 cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 308 if (I->isArtificial()) 309 cerr << " *"; 310 cerr << "\n"; 311 } 312 } 313 cerr << "\n"; 314} 315 316#ifndef NDEBUG 317/// VerifySchedule - Verify that all SUnits were scheduled and that 318/// their state is consistent. 319/// 320void ScheduleDAG::VerifySchedule(bool isBottomUp) { 321 bool AnyNotSched = false; 322 unsigned DeadNodes = 0; 323 unsigned Noops = 0; 324 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 325 if (!SUnits[i].isScheduled) { 326 if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 327 ++DeadNodes; 328 continue; 329 } 330 if (!AnyNotSched) 331 cerr << "*** Scheduling failed! ***\n"; 332 SUnits[i].dump(this); 333 cerr << "has not been scheduled!\n"; 334 AnyNotSched = true; 335 } 336 if (SUnits[i].isScheduled && 337 (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getHeight()) > 338 unsigned(INT_MAX)) { 339 if (!AnyNotSched) 340 cerr << "*** Scheduling failed! ***\n"; 341 SUnits[i].dump(this); 342 cerr << "has an unexpected " 343 << (isBottomUp ? "Height" : "Depth") << " value!\n"; 344 AnyNotSched = true; 345 } 346 if (isBottomUp) { 347 if (SUnits[i].NumSuccsLeft != 0) { 348 if (!AnyNotSched) 349 cerr << "*** Scheduling failed! ***\n"; 350 SUnits[i].dump(this); 351 cerr << "has successors left!\n"; 352 AnyNotSched = true; 353 } 354 } else { 355 if (SUnits[i].NumPredsLeft != 0) { 356 if (!AnyNotSched) 357 cerr << "*** Scheduling failed! ***\n"; 358 SUnits[i].dump(this); 359 cerr << "has predecessors left!\n"; 360 AnyNotSched = true; 361 } 362 } 363 } 364 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 365 if (!Sequence[i]) 366 ++Noops; 367 assert(!AnyNotSched); 368 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 369 "The number of nodes scheduled doesn't match the expected number!"); 370} 371#endif 372 373/// InitDAGTopologicalSorting - create the initial topological 374/// ordering from the DAG to be scheduled. 375/// 376/// The idea of the algorithm is taken from 377/// "Online algorithms for managing the topological order of 378/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 379/// This is the MNR algorithm, which was first introduced by 380/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 381/// "Maintaining a topological order under edge insertions". 382/// 383/// Short description of the algorithm: 384/// 385/// Topological ordering, ord, of a DAG maps each node to a topological 386/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 387/// 388/// This means that if there is a path from the node X to the node Z, 389/// then ord(X) < ord(Z). 390/// 391/// This property can be used to check for reachability of nodes: 392/// if Z is reachable from X, then an insertion of the edge Z->X would 393/// create a cycle. 394/// 395/// The algorithm first computes a topological ordering for the DAG by 396/// initializing the Index2Node and Node2Index arrays and then tries to keep 397/// the ordering up-to-date after edge insertions by reordering the DAG. 398/// 399/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 400/// the nodes reachable from Y, and then shifts them using Shift to lie 401/// immediately after X in Index2Node. 402void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 403 unsigned DAGSize = SUnits.size(); 404 std::vector<SUnit*> WorkList; 405 WorkList.reserve(DAGSize); 406 407 Index2Node.resize(DAGSize); 408 Node2Index.resize(DAGSize); 409 410 // Initialize the data structures. 411 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 412 SUnit *SU = &SUnits[i]; 413 int NodeNum = SU->NodeNum; 414 unsigned Degree = SU->Succs.size(); 415 // Temporarily use the Node2Index array as scratch space for degree counts. 416 Node2Index[NodeNum] = Degree; 417 418 // Is it a node without dependencies? 419 if (Degree == 0) { 420 assert(SU->Succs.empty() && "SUnit should have no successors"); 421 // Collect leaf nodes. 422 WorkList.push_back(SU); 423 } 424 } 425 426 int Id = DAGSize; 427 while (!WorkList.empty()) { 428 SUnit *SU = WorkList.back(); 429 WorkList.pop_back(); 430 Allocate(SU->NodeNum, --Id); 431 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 432 I != E; ++I) { 433 SUnit *SU = I->getSUnit(); 434 if (!--Node2Index[SU->NodeNum]) 435 // If all dependencies of the node are processed already, 436 // then the node can be computed now. 437 WorkList.push_back(SU); 438 } 439 } 440 441 Visited.resize(DAGSize); 442 443#ifndef NDEBUG 444 // Check correctness of the ordering 445 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 446 SUnit *SU = &SUnits[i]; 447 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 448 I != E; ++I) { 449 assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 450 "Wrong topological sorting"); 451 } 452 } 453#endif 454} 455 456/// AddPred - Updates the topological ordering to accomodate an edge 457/// to be added from SUnit X to SUnit Y. 458void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 459 int UpperBound, LowerBound; 460 LowerBound = Node2Index[Y->NodeNum]; 461 UpperBound = Node2Index[X->NodeNum]; 462 bool HasLoop = false; 463 // Is Ord(X) < Ord(Y) ? 464 if (LowerBound < UpperBound) { 465 // Update the topological order. 466 Visited.reset(); 467 DFS(Y, UpperBound, HasLoop); 468 assert(!HasLoop && "Inserted edge creates a loop!"); 469 // Recompute topological indexes. 470 Shift(Visited, LowerBound, UpperBound); 471 } 472} 473 474/// RemovePred - Updates the topological ordering to accomodate an 475/// an edge to be removed from the specified node N from the predecessors 476/// of the current node M. 477void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 478 // InitDAGTopologicalSorting(); 479} 480 481/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 482/// all nodes affected by the edge insertion. These nodes will later get new 483/// topological indexes by means of the Shift method. 484void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 485 bool& HasLoop) { 486 std::vector<const SUnit*> WorkList; 487 WorkList.reserve(SUnits.size()); 488 489 WorkList.push_back(SU); 490 do { 491 SU = WorkList.back(); 492 WorkList.pop_back(); 493 Visited.set(SU->NodeNum); 494 for (int I = SU->Succs.size()-1; I >= 0; --I) { 495 int s = SU->Succs[I].getSUnit()->NodeNum; 496 if (Node2Index[s] == UpperBound) { 497 HasLoop = true; 498 return; 499 } 500 // Visit successors if not already and in affected region. 501 if (!Visited.test(s) && Node2Index[s] < UpperBound) { 502 WorkList.push_back(SU->Succs[I].getSUnit()); 503 } 504 } 505 } while (!WorkList.empty()); 506} 507 508/// Shift - Renumber the nodes so that the topological ordering is 509/// preserved. 510void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 511 int UpperBound) { 512 std::vector<int> L; 513 int shift = 0; 514 int i; 515 516 for (i = LowerBound; i <= UpperBound; ++i) { 517 // w is node at topological index i. 518 int w = Index2Node[i]; 519 if (Visited.test(w)) { 520 // Unmark. 521 Visited.reset(w); 522 L.push_back(w); 523 shift = shift + 1; 524 } else { 525 Allocate(w, i - shift); 526 } 527 } 528 529 for (unsigned j = 0; j < L.size(); ++j) { 530 Allocate(L[j], i - shift); 531 i = i + 1; 532 } 533} 534 535 536/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 537/// create a cycle. 538bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 539 if (IsReachable(TargetSU, SU)) 540 return true; 541 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 542 I != E; ++I) 543 if (I->isAssignedRegDep() && 544 IsReachable(TargetSU, I->getSUnit())) 545 return true; 546 return false; 547} 548 549/// IsReachable - Checks if SU is reachable from TargetSU. 550bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 551 const SUnit *TargetSU) { 552 // If insertion of the edge SU->TargetSU would create a cycle 553 // then there is a path from TargetSU to SU. 554 int UpperBound, LowerBound; 555 LowerBound = Node2Index[TargetSU->NodeNum]; 556 UpperBound = Node2Index[SU->NodeNum]; 557 bool HasLoop = false; 558 // Is Ord(TargetSU) < Ord(SU) ? 559 if (LowerBound < UpperBound) { 560 Visited.reset(); 561 // There may be a path from TargetSU to SU. Check for it. 562 DFS(TargetSU, UpperBound, HasLoop); 563 } 564 return HasLoop; 565} 566 567/// Allocate - assign the topological index to the node n. 568void ScheduleDAGTopologicalSort::Allocate(int n, int index) { 569 Node2Index[n] = index; 570 Index2Node[index] = n; 571} 572 573ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort( 574 std::vector<SUnit> &sunits) 575 : SUnits(sunits) {} 576 577ScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} 578