ScheduleDAG.cpp revision 4de099d8ca651e00fa5fac22bace4f4dba2d0292
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, bool IgnoreAntiDep) { 187 if (NewDepth <= getDepth(IgnoreAntiDep)) 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, bool IgnoreAntiDep) { 198 if (NewHeight <= getHeight(IgnoreAntiDep)) 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(bool IgnoreAntiDep) { 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 if (IgnoreAntiDep && (I->getKind() == SDep::Anti)) continue; 218 SUnit *PredSU = I->getSUnit(); 219 if (PredSU->isDepthCurrent) 220 MaxPredDepth = std::max(MaxPredDepth, 221 PredSU->Depth + I->getLatency()); 222 else { 223 Done = false; 224 WorkList.push_back(PredSU); 225 } 226 } 227 228 if (Done) { 229 WorkList.pop_back(); 230 if (MaxPredDepth != Cur->Depth) { 231 Cur->setDepthDirty(); 232 Cur->Depth = MaxPredDepth; 233 } 234 Cur->isDepthCurrent = true; 235 } 236 } while (!WorkList.empty()); 237} 238 239/// ComputeHeight - Calculate the maximal path from the node to the entry. 240/// 241void SUnit::ComputeHeight(bool IgnoreAntiDep) { 242 SmallVector<SUnit*, 8> WorkList; 243 WorkList.push_back(this); 244 do { 245 SUnit *Cur = WorkList.back(); 246 247 bool Done = true; 248 unsigned MaxSuccHeight = 0; 249 for (SUnit::const_succ_iterator I = Cur->Succs.begin(), 250 E = Cur->Succs.end(); I != E; ++I) { 251 if (IgnoreAntiDep && (I->getKind() == SDep::Anti)) continue; 252 SUnit *SuccSU = I->getSUnit(); 253 if (SuccSU->isHeightCurrent) 254 MaxSuccHeight = std::max(MaxSuccHeight, 255 SuccSU->Height + I->getLatency()); 256 else { 257 Done = false; 258 WorkList.push_back(SuccSU); 259 } 260 } 261 262 if (Done) { 263 WorkList.pop_back(); 264 if (MaxSuccHeight != Cur->Height) { 265 Cur->setHeightDirty(); 266 Cur->Height = MaxSuccHeight; 267 } 268 Cur->isHeightCurrent = true; 269 } 270 } while (!WorkList.empty()); 271} 272 273/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 274/// a group of nodes flagged together. 275void SUnit::dump(const ScheduleDAG *G) const { 276 errs() << "SU(" << NodeNum << "): "; 277 G->dumpNode(this); 278} 279 280void SUnit::dumpAll(const ScheduleDAG *G) const { 281 dump(G); 282 283 errs() << " # preds left : " << NumPredsLeft << "\n"; 284 errs() << " # succs left : " << NumSuccsLeft << "\n"; 285 errs() << " Latency : " << Latency << "\n"; 286 errs() << " Depth : " << Depth << "\n"; 287 errs() << " Height : " << Height << "\n"; 288 289 if (Preds.size() != 0) { 290 errs() << " Predecessors:\n"; 291 for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 292 I != E; ++I) { 293 errs() << " "; 294 switch (I->getKind()) { 295 case SDep::Data: errs() << "val "; break; 296 case SDep::Anti: errs() << "anti"; break; 297 case SDep::Output: errs() << "out "; break; 298 case SDep::Order: errs() << "ch "; break; 299 } 300 errs() << "#"; 301 errs() << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 302 if (I->isArtificial()) 303 errs() << " *"; 304 errs() << ": Latency=" << I->getLatency(); 305 errs() << "\n"; 306 } 307 } 308 if (Succs.size() != 0) { 309 errs() << " Successors:\n"; 310 for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); 311 I != E; ++I) { 312 errs() << " "; 313 switch (I->getKind()) { 314 case SDep::Data: errs() << "val "; break; 315 case SDep::Anti: errs() << "anti"; break; 316 case SDep::Output: errs() << "out "; break; 317 case SDep::Order: errs() << "ch "; break; 318 } 319 errs() << "#"; 320 errs() << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 321 if (I->isArtificial()) 322 errs() << " *"; 323 errs() << ": Latency=" << I->getLatency(); 324 errs() << "\n"; 325 } 326 } 327 errs() << "\n"; 328} 329 330#ifndef NDEBUG 331/// VerifySchedule - Verify that all SUnits were scheduled and that 332/// their state is consistent. 333/// 334void ScheduleDAG::VerifySchedule(bool isBottomUp) { 335 bool AnyNotSched = false; 336 unsigned DeadNodes = 0; 337 unsigned Noops = 0; 338 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 339 if (!SUnits[i].isScheduled) { 340 if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 341 ++DeadNodes; 342 continue; 343 } 344 if (!AnyNotSched) 345 errs() << "*** Scheduling failed! ***\n"; 346 SUnits[i].dump(this); 347 errs() << "has not been scheduled!\n"; 348 AnyNotSched = true; 349 } 350 if (SUnits[i].isScheduled && 351 (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getDepth()) > 352 unsigned(INT_MAX)) { 353 if (!AnyNotSched) 354 errs() << "*** Scheduling failed! ***\n"; 355 SUnits[i].dump(this); 356 errs() << "has an unexpected " 357 << (isBottomUp ? "Height" : "Depth") << " value!\n"; 358 AnyNotSched = true; 359 } 360 if (isBottomUp) { 361 if (SUnits[i].NumSuccsLeft != 0) { 362 if (!AnyNotSched) 363 errs() << "*** Scheduling failed! ***\n"; 364 SUnits[i].dump(this); 365 errs() << "has successors left!\n"; 366 AnyNotSched = true; 367 } 368 } else { 369 if (SUnits[i].NumPredsLeft != 0) { 370 if (!AnyNotSched) 371 errs() << "*** Scheduling failed! ***\n"; 372 SUnits[i].dump(this); 373 errs() << "has predecessors left!\n"; 374 AnyNotSched = true; 375 } 376 } 377 } 378 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 379 if (!Sequence[i]) 380 ++Noops; 381 assert(!AnyNotSched); 382 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 383 "The number of nodes scheduled doesn't match the expected number!"); 384} 385#endif 386 387/// InitDAGTopologicalSorting - create the initial topological 388/// ordering from the DAG to be scheduled. 389/// 390/// The idea of the algorithm is taken from 391/// "Online algorithms for managing the topological order of 392/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 393/// This is the MNR algorithm, which was first introduced by 394/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 395/// "Maintaining a topological order under edge insertions". 396/// 397/// Short description of the algorithm: 398/// 399/// Topological ordering, ord, of a DAG maps each node to a topological 400/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 401/// 402/// This means that if there is a path from the node X to the node Z, 403/// then ord(X) < ord(Z). 404/// 405/// This property can be used to check for reachability of nodes: 406/// if Z is reachable from X, then an insertion of the edge Z->X would 407/// create a cycle. 408/// 409/// The algorithm first computes a topological ordering for the DAG by 410/// initializing the Index2Node and Node2Index arrays and then tries to keep 411/// the ordering up-to-date after edge insertions by reordering the DAG. 412/// 413/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 414/// the nodes reachable from Y, and then shifts them using Shift to lie 415/// immediately after X in Index2Node. 416void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 417 unsigned DAGSize = SUnits.size(); 418 std::vector<SUnit*> WorkList; 419 WorkList.reserve(DAGSize); 420 421 Index2Node.resize(DAGSize); 422 Node2Index.resize(DAGSize); 423 424 // Initialize the data structures. 425 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 426 SUnit *SU = &SUnits[i]; 427 int NodeNum = SU->NodeNum; 428 unsigned Degree = SU->Succs.size(); 429 // Temporarily use the Node2Index array as scratch space for degree counts. 430 Node2Index[NodeNum] = Degree; 431 432 // Is it a node without dependencies? 433 if (Degree == 0) { 434 assert(SU->Succs.empty() && "SUnit should have no successors"); 435 // Collect leaf nodes. 436 WorkList.push_back(SU); 437 } 438 } 439 440 int Id = DAGSize; 441 while (!WorkList.empty()) { 442 SUnit *SU = WorkList.back(); 443 WorkList.pop_back(); 444 Allocate(SU->NodeNum, --Id); 445 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 446 I != E; ++I) { 447 SUnit *SU = I->getSUnit(); 448 if (!--Node2Index[SU->NodeNum]) 449 // If all dependencies of the node are processed already, 450 // then the node can be computed now. 451 WorkList.push_back(SU); 452 } 453 } 454 455 Visited.resize(DAGSize); 456 457#ifndef NDEBUG 458 // Check correctness of the ordering 459 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 460 SUnit *SU = &SUnits[i]; 461 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 462 I != E; ++I) { 463 assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 464 "Wrong topological sorting"); 465 } 466 } 467#endif 468} 469 470/// AddPred - Updates the topological ordering to accomodate an edge 471/// to be added from SUnit X to SUnit Y. 472void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 473 int UpperBound, LowerBound; 474 LowerBound = Node2Index[Y->NodeNum]; 475 UpperBound = Node2Index[X->NodeNum]; 476 bool HasLoop = false; 477 // Is Ord(X) < Ord(Y) ? 478 if (LowerBound < UpperBound) { 479 // Update the topological order. 480 Visited.reset(); 481 DFS(Y, UpperBound, HasLoop); 482 assert(!HasLoop && "Inserted edge creates a loop!"); 483 // Recompute topological indexes. 484 Shift(Visited, LowerBound, UpperBound); 485 } 486} 487 488/// RemovePred - Updates the topological ordering to accomodate an 489/// an edge to be removed from the specified node N from the predecessors 490/// of the current node M. 491void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 492 // InitDAGTopologicalSorting(); 493} 494 495/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 496/// all nodes affected by the edge insertion. These nodes will later get new 497/// topological indexes by means of the Shift method. 498void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 499 bool& HasLoop) { 500 std::vector<const SUnit*> WorkList; 501 WorkList.reserve(SUnits.size()); 502 503 WorkList.push_back(SU); 504 do { 505 SU = WorkList.back(); 506 WorkList.pop_back(); 507 Visited.set(SU->NodeNum); 508 for (int I = SU->Succs.size()-1; I >= 0; --I) { 509 int s = SU->Succs[I].getSUnit()->NodeNum; 510 if (Node2Index[s] == UpperBound) { 511 HasLoop = true; 512 return; 513 } 514 // Visit successors if not already and in affected region. 515 if (!Visited.test(s) && Node2Index[s] < UpperBound) { 516 WorkList.push_back(SU->Succs[I].getSUnit()); 517 } 518 } 519 } while (!WorkList.empty()); 520} 521 522/// Shift - Renumber the nodes so that the topological ordering is 523/// preserved. 524void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 525 int UpperBound) { 526 std::vector<int> L; 527 int shift = 0; 528 int i; 529 530 for (i = LowerBound; i <= UpperBound; ++i) { 531 // w is node at topological index i. 532 int w = Index2Node[i]; 533 if (Visited.test(w)) { 534 // Unmark. 535 Visited.reset(w); 536 L.push_back(w); 537 shift = shift + 1; 538 } else { 539 Allocate(w, i - shift); 540 } 541 } 542 543 for (unsigned j = 0; j < L.size(); ++j) { 544 Allocate(L[j], i - shift); 545 i = i + 1; 546 } 547} 548 549 550/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 551/// create a cycle. 552bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 553 if (IsReachable(TargetSU, SU)) 554 return true; 555 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 556 I != E; ++I) 557 if (I->isAssignedRegDep() && 558 IsReachable(TargetSU, I->getSUnit())) 559 return true; 560 return false; 561} 562 563/// IsReachable - Checks if SU is reachable from TargetSU. 564bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 565 const SUnit *TargetSU) { 566 // If insertion of the edge SU->TargetSU would create a cycle 567 // then there is a path from TargetSU to SU. 568 int UpperBound, LowerBound; 569 LowerBound = Node2Index[TargetSU->NodeNum]; 570 UpperBound = Node2Index[SU->NodeNum]; 571 bool HasLoop = false; 572 // Is Ord(TargetSU) < Ord(SU) ? 573 if (LowerBound < UpperBound) { 574 Visited.reset(); 575 // There may be a path from TargetSU to SU. Check for it. 576 DFS(TargetSU, UpperBound, HasLoop); 577 } 578 return HasLoop; 579} 580 581/// Allocate - assign the topological index to the node n. 582void ScheduleDAGTopologicalSort::Allocate(int n, int index) { 583 Node2Index[n] = index; 584 Index2Node[index] = n; 585} 586 587ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort( 588 std::vector<SUnit> &sunits) 589 : SUnits(sunits) {} 590 591ScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} 592