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