ScheduleDAGRRList.cpp revision 8701816221817cfb8b8b67ca06cc9a39bacbcbde
1//===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===// 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 bottom-up and top-down register pressure reduction list 11// schedulers, using standard algorithms. The basic approach uses a priority 12// queue of available nodes to schedule. One at a time, nodes are taken from 13// the priority queue (thus in priority order), checked for legality to 14// schedule, and emitted if legal. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "pre-RA-sched" 19#include "llvm/CodeGen/ScheduleDAG.h" 20#include "llvm/CodeGen/SchedulerRegistry.h" 21#include "llvm/Target/TargetRegisterInfo.h" 22#include "llvm/Target/TargetData.h" 23#include "llvm/Target/TargetMachine.h" 24#include "llvm/Target/TargetInstrInfo.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/Compiler.h" 27#include "llvm/ADT/SmallPtrSet.h" 28#include "llvm/ADT/SmallSet.h" 29#include "llvm/ADT/Statistic.h" 30#include <climits> 31#include <queue> 32#include "llvm/Support/CommandLine.h" 33using namespace llvm; 34 35STATISTIC(NumBacktracks, "Number of times scheduler backtracked"); 36STATISTIC(NumUnfolds, "Number of nodes unfolded"); 37STATISTIC(NumDups, "Number of duplicated nodes"); 38STATISTIC(NumCCCopies, "Number of cross class copies"); 39 40static RegisterScheduler 41 burrListDAGScheduler("list-burr", 42 " Bottom-up register reduction list scheduling", 43 createBURRListDAGScheduler); 44static RegisterScheduler 45 tdrListrDAGScheduler("list-tdrr", 46 " Top-down register reduction list scheduling", 47 createTDRRListDAGScheduler); 48 49namespace { 50//===----------------------------------------------------------------------===// 51/// ScheduleDAGRRList - The actual register reduction list scheduler 52/// implementation. This supports both top-down and bottom-up scheduling. 53/// 54class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG { 55private: 56 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if 57 /// it is top-down. 58 bool isBottomUp; 59 60 /// AvailableQueue - The priority queue to use for the available SUnits. 61 SchedulingPriorityQueue *AvailableQueue; 62 63 /// LiveRegs / LiveRegDefs - A set of physical registers and their definition 64 /// that are "live". These nodes must be scheduled before any other nodes that 65 /// modifies the registers can be scheduled. 66 SmallSet<unsigned, 4> LiveRegs; 67 std::vector<SUnit*> LiveRegDefs; 68 std::vector<unsigned> LiveRegCycles; 69 70public: 71 ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb, 72 const TargetMachine &tm, bool isbottomup, 73 SchedulingPriorityQueue *availqueue) 74 : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), 75 AvailableQueue(availqueue) { 76 } 77 78 ~ScheduleDAGRRList() { 79 delete AvailableQueue; 80 } 81 82 void Schedule(); 83 84 /// IsReachable - Checks if SU is reachable from TargetSU. 85 bool IsReachable(SUnit *SU, SUnit *TargetSU); 86 87 /// willCreateCycle - Returns true if adding an edge from SU to TargetSU will 88 /// create a cycle. 89 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU); 90 91 /// AddPred - This adds the specified node X as a predecessor of 92 /// the current node Y if not already. 93 /// This returns true if this is a new predecessor. 94 /// Updates the topological ordering if required. 95 bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isSpecial, 96 unsigned PhyReg = 0, int Cost = 1); 97 98 /// RemovePred - This removes the specified node N from the predecessors of 99 /// the current node M. Updates the topological ordering if required. 100 bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isSpecial); 101 102private: 103 void ReleasePred(SUnit*, bool, unsigned); 104 void ReleaseSucc(SUnit*, bool isChain, unsigned); 105 void CapturePred(SUnit*, SUnit*, bool); 106 void ScheduleNodeBottomUp(SUnit*, unsigned); 107 void ScheduleNodeTopDown(SUnit*, unsigned); 108 void UnscheduleNodeBottomUp(SUnit*); 109 void BacktrackBottomUp(SUnit*, unsigned, unsigned&); 110 SUnit *CopyAndMoveSuccessors(SUnit*); 111 void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned, 112 const TargetRegisterClass*, 113 const TargetRegisterClass*, 114 SmallVector<SUnit*, 2>&); 115 bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 116 void ListScheduleTopDown(); 117 void ListScheduleBottomUp(); 118 void CommuteNodesToReducePressure(); 119 120 121 /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it. 122 /// Updates the topological ordering if required. 123 SUnit *CreateNewSUnit(SDNode *N) { 124 SUnit *NewNode = NewSUnit(N); 125 // Update the topological ordering. 126 if (NewNode->NodeNum >= Node2Index.size()) 127 InitDAGTopologicalSorting(); 128 return NewNode; 129 } 130 131 /// CreateClone - Creates a new SUnit from an existing one. 132 /// Updates the topological ordering if required. 133 SUnit *CreateClone(SUnit *N) { 134 SUnit *NewNode = Clone(N); 135 // Update the topological ordering. 136 if (NewNode->NodeNum >= Node2Index.size()) 137 InitDAGTopologicalSorting(); 138 return NewNode; 139 } 140 141 /// Functions for preserving the topological ordering 142 /// even after dynamic insertions of new edges. 143 /// This allows a very fast implementation of IsReachable. 144 145 146 /** 147 The idea of the algorithm is taken from 148 "Online algorithms for managing the topological order of 149 a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 150 This is the MNR algorithm, which was first introduced by 151 A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 152 "Maintaining a topological order under edge insertions". 153 154 Short description of the algorithm: 155 156 Topological ordering, ord, of a DAG maps each node to a topological 157 index so that for all edges X->Y it is the case that ord(X) < ord(Y). 158 159 This means that if there is a path from the node X to the node Z, 160 then ord(X) < ord(Z). 161 162 This property can be used to check for reachability of nodes: 163 if Z is reachable from X, then an insertion of the edge Z->X would 164 create a cycle. 165 166 The algorithm first computes a topological ordering for the DAG by initializing 167 the Index2Node and Node2Index arrays and then tries to keep the ordering 168 up-to-date after edge insertions by reordering the DAG. 169 170 On insertion of the edge X->Y, the algorithm first marks by calling DFS the 171 nodes reachable from Y, and then shifts them using Shift to lie immediately 172 after X in Index2Node. 173 */ 174 175 /// InitDAGTopologicalSorting - create the initial topological 176 /// ordering from the DAG to be scheduled. 177 void InitDAGTopologicalSorting(); 178 179 /// DFS - make a DFS traversal and mark all nodes affected by the 180 /// edge insertion. These nodes will later get new topological indexes 181 /// by means of the Shift method. 182 void DFS(SUnit *SU, int UpperBound, bool& HasLoop); 183 184 /// Shift - reassign topological indexes for the nodes in the DAG 185 /// to preserve the topological ordering. 186 void Shift(BitVector& Visited, int LowerBound, int UpperBound); 187 188 /// Allocate - assign the topological index to the node n. 189 void Allocate(int n, int index); 190 191 /// Index2Node - Maps topological index to the node number. 192 std::vector<int> Index2Node; 193 /// Node2Index - Maps the node number to its topological index. 194 std::vector<int> Node2Index; 195 /// Visited - a set of nodes visited during a DFS traversal. 196 BitVector Visited; 197}; 198} // end anonymous namespace 199 200 201/// Schedule - Schedule the DAG using list scheduling. 202void ScheduleDAGRRList::Schedule() { 203 DOUT << "********** List Scheduling **********\n"; 204 205 LiveRegDefs.resize(TRI->getNumRegs(), NULL); 206 LiveRegCycles.resize(TRI->getNumRegs(), 0); 207 208 // Build scheduling units. 209 BuildSchedUnits(); 210 211 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 212 SUnits[su].dumpAll(&DAG)); 213 CalculateDepths(); 214 CalculateHeights(); 215 InitDAGTopologicalSorting(); 216 217 AvailableQueue->initNodes(SUnitMap, SUnits); 218 219 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. 220 if (isBottomUp) 221 ListScheduleBottomUp(); 222 else 223 ListScheduleTopDown(); 224 225 AvailableQueue->releaseState(); 226 227 CommuteNodesToReducePressure(); 228 229 DOUT << "*** Final schedule ***\n"; 230 DEBUG(dumpSchedule()); 231 DOUT << "\n"; 232 233 // Emit in scheduled order 234 EmitSchedule(); 235} 236 237/// CommuteNodesToReducePressure - If a node is two-address and commutable, and 238/// it is not the last use of its first operand, add it to the CommuteSet if 239/// possible. It will be commuted when it is translated to a MI. 240void ScheduleDAGRRList::CommuteNodesToReducePressure() { 241 SmallPtrSet<SUnit*, 4> OperandSeen; 242 for (unsigned i = Sequence.size(); i != 0; ) { 243 --i; 244 SUnit *SU = Sequence[i]; 245 if (!SU || !SU->Node) continue; 246 if (SU->isCommutable) { 247 unsigned Opc = SU->Node->getTargetOpcode(); 248 const TargetInstrDesc &TID = TII->get(Opc); 249 unsigned NumRes = TID.getNumDefs(); 250 unsigned NumOps = TID.getNumOperands() - NumRes; 251 for (unsigned j = 0; j != NumOps; ++j) { 252 if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1) 253 continue; 254 255 SDNode *OpN = SU->Node->getOperand(j).Val; 256 SUnit *OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo]; 257 if (OpSU && OperandSeen.count(OpSU) == 1) { 258 // Ok, so SU is not the last use of OpSU, but SU is two-address so 259 // it will clobber OpSU. Try to commute SU if no other source operands 260 // are live below. 261 bool DoCommute = true; 262 for (unsigned k = 0; k < NumOps; ++k) { 263 if (k != j) { 264 OpN = SU->Node->getOperand(k).Val; 265 OpSU = isPassiveNode(OpN) ? NULL : SUnitMap[OpN][SU->InstanceNo]; 266 if (OpSU && OperandSeen.count(OpSU) == 1) { 267 DoCommute = false; 268 break; 269 } 270 } 271 } 272 if (DoCommute) 273 CommuteSet.insert(SU->Node); 274 } 275 276 // Only look at the first use&def node for now. 277 break; 278 } 279 } 280 281 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 282 I != E; ++I) { 283 if (!I->isCtrl) 284 OperandSeen.insert(I->Dep); 285 } 286 } 287} 288 289//===----------------------------------------------------------------------===// 290// Bottom-Up Scheduling 291//===----------------------------------------------------------------------===// 292 293/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 294/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 295void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain, 296 unsigned CurCycle) { 297 // FIXME: the distance between two nodes is not always == the predecessor's 298 // latency. For example, the reader can very well read the register written 299 // by the predecessor later than the issue cycle. It also depends on the 300 // interrupt model (drain vs. freeze). 301 PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency); 302 303 --PredSU->NumSuccsLeft; 304 305#ifndef NDEBUG 306 if (PredSU->NumSuccsLeft < 0) { 307 cerr << "*** List scheduling failed! ***\n"; 308 PredSU->dump(&DAG); 309 cerr << " has been released too many times!\n"; 310 assert(0); 311 } 312#endif 313 314 if (PredSU->NumSuccsLeft == 0) { 315 PredSU->isAvailable = true; 316 AvailableQueue->push(PredSU); 317 } 318} 319 320/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 321/// count of its predecessors. If a predecessor pending count is zero, add it to 322/// the Available queue. 323void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 324 DOUT << "*** Scheduling [" << CurCycle << "]: "; 325 DEBUG(SU->dump(&DAG)); 326 SU->Cycle = CurCycle; 327 328 AvailableQueue->ScheduledNode(SU); 329 330 // Bottom up: release predecessors 331 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 332 I != E; ++I) { 333 ReleasePred(I->Dep, I->isCtrl, CurCycle); 334 if (I->Cost < 0) { 335 // This is a physical register dependency and it's impossible or 336 // expensive to copy the register. Make sure nothing that can 337 // clobber the register is scheduled between the predecessor and 338 // this node. 339 if (LiveRegs.insert(I->Reg)) { 340 LiveRegDefs[I->Reg] = I->Dep; 341 LiveRegCycles[I->Reg] = CurCycle; 342 } 343 } 344 } 345 346 // Release all the implicit physical register defs that are live. 347 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 348 I != E; ++I) { 349 if (I->Cost < 0) { 350 if (LiveRegCycles[I->Reg] == I->Dep->Cycle) { 351 LiveRegs.erase(I->Reg); 352 assert(LiveRegDefs[I->Reg] == SU && 353 "Physical register dependency violated?"); 354 LiveRegDefs[I->Reg] = NULL; 355 LiveRegCycles[I->Reg] = 0; 356 } 357 } 358 } 359 360 SU->isScheduled = true; 361} 362 363/// CapturePred - This does the opposite of ReleasePred. Since SU is being 364/// unscheduled, incrcease the succ left count of its predecessors. Remove 365/// them from AvailableQueue if necessary. 366void ScheduleDAGRRList::CapturePred(SUnit *PredSU, SUnit *SU, bool isChain) { 367 PredSU->CycleBound = 0; 368 for (SUnit::succ_iterator I = PredSU->Succs.begin(), E = PredSU->Succs.end(); 369 I != E; ++I) { 370 if (I->Dep == SU) 371 continue; 372 PredSU->CycleBound = std::max(PredSU->CycleBound, 373 I->Dep->Cycle + PredSU->Latency); 374 } 375 376 if (PredSU->isAvailable) { 377 PredSU->isAvailable = false; 378 if (!PredSU->isPending) 379 AvailableQueue->remove(PredSU); 380 } 381 382 ++PredSU->NumSuccsLeft; 383} 384 385/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and 386/// its predecessor states to reflect the change. 387void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) { 388 DOUT << "*** Unscheduling [" << SU->Cycle << "]: "; 389 DEBUG(SU->dump(&DAG)); 390 391 AvailableQueue->UnscheduledNode(SU); 392 393 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 394 I != E; ++I) { 395 CapturePred(I->Dep, SU, I->isCtrl); 396 if (I->Cost < 0 && SU->Cycle == LiveRegCycles[I->Reg]) { 397 LiveRegs.erase(I->Reg); 398 assert(LiveRegDefs[I->Reg] == I->Dep && 399 "Physical register dependency violated?"); 400 LiveRegDefs[I->Reg] = NULL; 401 LiveRegCycles[I->Reg] = 0; 402 } 403 } 404 405 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 406 I != E; ++I) { 407 if (I->Cost < 0) { 408 if (LiveRegs.insert(I->Reg)) { 409 assert(!LiveRegDefs[I->Reg] && 410 "Physical register dependency violated?"); 411 LiveRegDefs[I->Reg] = SU; 412 } 413 if (I->Dep->Cycle < LiveRegCycles[I->Reg]) 414 LiveRegCycles[I->Reg] = I->Dep->Cycle; 415 } 416 } 417 418 SU->Cycle = 0; 419 SU->isScheduled = false; 420 SU->isAvailable = true; 421 AvailableQueue->push(SU); 422} 423 424/// IsReachable - Checks if SU is reachable from TargetSU. 425bool ScheduleDAGRRList::IsReachable(SUnit *SU, SUnit *TargetSU) { 426 // If insertion of the edge SU->TargetSU would create a cycle 427 // then there is a path from TargetSU to SU. 428 int UpperBound, LowerBound; 429 LowerBound = Node2Index[TargetSU->NodeNum]; 430 UpperBound = Node2Index[SU->NodeNum]; 431 bool HasLoop = false; 432 // Is Ord(TargetSU) < Ord(SU) ? 433 if (LowerBound < UpperBound) { 434 Visited.reset(); 435 // There may be a path from TargetSU to SU. Check for it. 436 DFS(TargetSU, UpperBound, HasLoop); 437 } 438 return HasLoop; 439} 440 441/// Allocate - assign the topological index to the node n. 442inline void ScheduleDAGRRList::Allocate(int n, int index) { 443 Node2Index[n] = index; 444 Index2Node[index] = n; 445} 446 447/// InitDAGTopologicalSorting - create the initial topological 448/// ordering from the DAG to be scheduled. 449void ScheduleDAGRRList::InitDAGTopologicalSorting() { 450 unsigned DAGSize = SUnits.size(); 451 std::vector<unsigned> InDegree(DAGSize); 452 std::vector<SUnit*> WorkList; 453 WorkList.reserve(DAGSize); 454 std::vector<SUnit*> TopOrder; 455 TopOrder.reserve(DAGSize); 456 457 // Initialize the data structures. 458 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 459 SUnit *SU = &SUnits[i]; 460 int NodeNum = SU->NodeNum; 461 unsigned Degree = SU->Succs.size(); 462 InDegree[NodeNum] = Degree; 463 464 // Is it a node without dependencies? 465 if (Degree == 0) { 466 assert(SU->Succs.empty() && "SUnit should have no successors"); 467 // Collect leaf nodes. 468 WorkList.push_back(SU); 469 } 470 } 471 472 while (!WorkList.empty()) { 473 SUnit *SU = WorkList.back(); 474 WorkList.pop_back(); 475 TopOrder.push_back(SU); 476 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 477 I != E; ++I) { 478 SUnit *SU = I->Dep; 479 if (!--InDegree[SU->NodeNum]) 480 // If all dependencies of the node are processed already, 481 // then the node can be computed now. 482 WorkList.push_back(SU); 483 } 484 } 485 486 // Second pass, assign the actual topological order as node ids. 487 int Id = 0; 488 489 Index2Node.clear(); 490 Node2Index.clear(); 491 Index2Node.resize(DAGSize); 492 Node2Index.resize(DAGSize); 493 Visited.resize(DAGSize); 494 495 for (std::vector<SUnit*>::reverse_iterator TI = TopOrder.rbegin(), 496 TE = TopOrder.rend();TI != TE; ++TI) { 497 Allocate((*TI)->NodeNum, Id); 498 Id++; 499 } 500 501#ifndef NDEBUG 502 // Check correctness of the ordering 503 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 504 SUnit *SU = &SUnits[i]; 505 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 506 I != E; ++I) { 507 assert(Node2Index[SU->NodeNum] > Node2Index[I->Dep->NodeNum] && 508 "Wrong topological sorting"); 509 } 510 } 511#endif 512} 513 514/// AddPred - adds an edge from SUnit X to SUnit Y. 515/// Updates the topological ordering if required. 516bool ScheduleDAGRRList::AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isSpecial, 517 unsigned PhyReg, int Cost) { 518 int UpperBound, LowerBound; 519 LowerBound = Node2Index[Y->NodeNum]; 520 UpperBound = Node2Index[X->NodeNum]; 521 bool HasLoop = false; 522 // Is Ord(X) < Ord(Y) ? 523 if (LowerBound < UpperBound) { 524 // Update the topological order. 525 Visited.reset(); 526 DFS(Y, UpperBound, HasLoop); 527 assert(!HasLoop && "Inserted edge creates a loop!"); 528 // Recompute topological indexes. 529 Shift(Visited, LowerBound, UpperBound); 530 } 531 // Now really insert the edge. 532 return Y->addPred(X, isCtrl, isSpecial, PhyReg, Cost); 533} 534 535/// RemovePred - This removes the specified node N from the predecessors of 536/// the current node M. Updates the topological ordering if required. 537bool ScheduleDAGRRList::RemovePred(SUnit *M, SUnit *N, 538 bool isCtrl, bool isSpecial) { 539 // InitDAGTopologicalSorting(); 540 return M->removePred(N, isCtrl, isSpecial); 541} 542 543/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 544/// all nodes affected by the edge insertion. These nodes will later get new 545/// topological indexes by means of the Shift method. 546void ScheduleDAGRRList::DFS(SUnit *SU, int UpperBound, bool& HasLoop) { 547 std::vector<SUnit*> WorkList; 548 WorkList.reserve(SUnits.size()); 549 550 WorkList.push_back(SU); 551 while (!WorkList.empty()) { 552 SU = WorkList.back(); 553 WorkList.pop_back(); 554 Visited.set(SU->NodeNum); 555 for (int I = SU->Succs.size()-1; I >= 0; --I) { 556 int s = SU->Succs[I].Dep->NodeNum; 557 if (Node2Index[s] == UpperBound) { 558 HasLoop = true; 559 return; 560 } 561 // Visit successors if not already and in affected region. 562 if (!Visited.test(s) && Node2Index[s] < UpperBound) { 563 WorkList.push_back(SU->Succs[I].Dep); 564 } 565 } 566 } 567} 568 569/// Shift - Renumber the nodes so that the topological ordering is 570/// preserved. 571void ScheduleDAGRRList::Shift(BitVector& Visited, int LowerBound, 572 int UpperBound) { 573 std::vector<int> L; 574 int shift = 0; 575 int i; 576 577 for (i = LowerBound; i <= UpperBound; ++i) { 578 // w is node at topological index i. 579 int w = Index2Node[i]; 580 if (Visited.test(w)) { 581 // Unmark. 582 Visited.reset(w); 583 L.push_back(w); 584 shift = shift + 1; 585 } else { 586 Allocate(w, i - shift); 587 } 588 } 589 590 for (unsigned j = 0; j < L.size(); ++j) { 591 Allocate(L[j], i - shift); 592 i = i + 1; 593 } 594} 595 596 597/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 598/// create a cycle. 599bool ScheduleDAGRRList::WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 600 if (IsReachable(TargetSU, SU)) 601 return true; 602 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 603 I != E; ++I) 604 if (I->Cost < 0 && IsReachable(TargetSU, I->Dep)) 605 return true; 606 return false; 607} 608 609/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in 610/// BTCycle in order to schedule a specific node. Returns the last unscheduled 611/// SUnit. Also returns if a successor is unscheduled in the process. 612void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, 613 unsigned &CurCycle) { 614 SUnit *OldSU = NULL; 615 while (CurCycle > BtCycle) { 616 OldSU = Sequence.back(); 617 Sequence.pop_back(); 618 if (SU->isSucc(OldSU)) 619 // Don't try to remove SU from AvailableQueue. 620 SU->isAvailable = false; 621 UnscheduleNodeBottomUp(OldSU); 622 --CurCycle; 623 } 624 625 626 if (SU->isSucc(OldSU)) { 627 assert(false && "Something is wrong!"); 628 abort(); 629 } 630 631 ++NumBacktracks; 632} 633 634/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 635/// successors to the newly created node. 636SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { 637 if (SU->FlaggedNodes.size()) 638 return NULL; 639 640 SDNode *N = SU->Node; 641 if (!N) 642 return NULL; 643 644 SUnit *NewSU; 645 bool TryUnfold = false; 646 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 647 MVT::ValueType VT = N->getValueType(i); 648 if (VT == MVT::Flag) 649 return NULL; 650 else if (VT == MVT::Other) 651 TryUnfold = true; 652 } 653 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 654 const SDOperand &Op = N->getOperand(i); 655 MVT::ValueType VT = Op.Val->getValueType(Op.ResNo); 656 if (VT == MVT::Flag) 657 return NULL; 658 } 659 660 if (TryUnfold) { 661 SmallVector<SDNode*, 4> NewNodes; 662 if (!TII->unfoldMemoryOperand(DAG, N, NewNodes)) 663 return NULL; 664 665 DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; 666 assert(NewNodes.size() == 2 && "Expected a load folding node!"); 667 668 N = NewNodes[1]; 669 SDNode *LoadNode = NewNodes[0]; 670 unsigned NumVals = N->getNumValues(); 671 unsigned OldNumVals = SU->Node->getNumValues(); 672 for (unsigned i = 0; i != NumVals; ++i) 673 DAG.ReplaceAllUsesOfValueWith(SDOperand(SU->Node, i), SDOperand(N, i)); 674 DAG.ReplaceAllUsesOfValueWith(SDOperand(SU->Node, OldNumVals-1), 675 SDOperand(LoadNode, 1)); 676 677 SUnit *NewSU = CreateNewSUnit(N); 678 SUnitMap[N].push_back(NewSU); 679 const TargetInstrDesc &TID = TII->get(N->getTargetOpcode()); 680 for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 681 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 682 NewSU->isTwoAddress = true; 683 break; 684 } 685 } 686 if (TID.isCommutable()) 687 NewSU->isCommutable = true; 688 // FIXME: Calculate height / depth and propagate the changes? 689 NewSU->Depth = SU->Depth; 690 NewSU->Height = SU->Height; 691 ComputeLatency(NewSU); 692 693 // LoadNode may already exist. This can happen when there is another 694 // load from the same location and producing the same type of value 695 // but it has different alignment or volatileness. 696 bool isNewLoad = true; 697 SUnit *LoadSU; 698 DenseMap<SDNode*, std::vector<SUnit*> >::iterator SMI = 699 SUnitMap.find(LoadNode); 700 if (SMI != SUnitMap.end()) { 701 LoadSU = SMI->second.front(); 702 isNewLoad = false; 703 } else { 704 LoadSU = CreateNewSUnit(LoadNode); 705 SUnitMap[LoadNode].push_back(LoadSU); 706 707 LoadSU->Depth = SU->Depth; 708 LoadSU->Height = SU->Height; 709 ComputeLatency(LoadSU); 710 } 711 712 SUnit *ChainPred = NULL; 713 SmallVector<SDep, 4> ChainSuccs; 714 SmallVector<SDep, 4> LoadPreds; 715 SmallVector<SDep, 4> NodePreds; 716 SmallVector<SDep, 4> NodeSuccs; 717 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 718 I != E; ++I) { 719 if (I->isCtrl) 720 ChainPred = I->Dep; 721 else if (I->Dep->Node && I->Dep->Node->isOperandOf(LoadNode)) 722 LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false)); 723 else 724 NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false)); 725 } 726 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 727 I != E; ++I) { 728 if (I->isCtrl) 729 ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost, 730 I->isCtrl, I->isSpecial)); 731 else 732 NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost, 733 I->isCtrl, I->isSpecial)); 734 } 735 736 if (ChainPred) { 737 RemovePred(SU, ChainPred, true, false); 738 if (isNewLoad) 739 AddPred(LoadSU, ChainPred, true, false); 740 } 741 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 742 SDep *Pred = &LoadPreds[i]; 743 RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isSpecial); 744 if (isNewLoad) { 745 AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isSpecial, 746 Pred->Reg, Pred->Cost); 747 } 748 } 749 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 750 SDep *Pred = &NodePreds[i]; 751 RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isSpecial); 752 AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isSpecial, 753 Pred->Reg, Pred->Cost); 754 } 755 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 756 SDep *Succ = &NodeSuccs[i]; 757 RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isSpecial); 758 AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isSpecial, 759 Succ->Reg, Succ->Cost); 760 } 761 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 762 SDep *Succ = &ChainSuccs[i]; 763 RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isSpecial); 764 if (isNewLoad) { 765 AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isSpecial, 766 Succ->Reg, Succ->Cost); 767 } 768 } 769 if (isNewLoad) { 770 AddPred(NewSU, LoadSU, false, false); 771 } 772 773 if (isNewLoad) 774 AvailableQueue->addNode(LoadSU); 775 AvailableQueue->addNode(NewSU); 776 777 ++NumUnfolds; 778 779 if (NewSU->NumSuccsLeft == 0) { 780 NewSU->isAvailable = true; 781 return NewSU; 782 } 783 SU = NewSU; 784 } 785 786 DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; 787 NewSU = CreateClone(SU); 788 789 // New SUnit has the exact same predecessors. 790 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 791 I != E; ++I) 792 if (!I->isSpecial) { 793 AddPred(NewSU, I->Dep, I->isCtrl, false, I->Reg, I->Cost); 794 NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1); 795 } 796 797 // Only copy scheduled successors. Cut them from old node's successor 798 // list and move them over. 799 SmallVector<std::pair<SUnit*, bool>, 4> DelDeps; 800 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 801 I != E; ++I) { 802 if (I->isSpecial) 803 continue; 804 if (I->Dep->isScheduled) { 805 NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1); 806 AddPred(I->Dep, NewSU, I->isCtrl, false, I->Reg, I->Cost); 807 DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl)); 808 } 809 } 810 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 811 SUnit *Succ = DelDeps[i].first; 812 bool isCtrl = DelDeps[i].second; 813 RemovePred(Succ, SU, isCtrl, false); 814 } 815 816 AvailableQueue->updateNode(SU); 817 AvailableQueue->addNode(NewSU); 818 819 ++NumDups; 820 return NewSU; 821} 822 823/// InsertCCCopiesAndMoveSuccs - Insert expensive cross register class copies 824/// and move all scheduled successors of the given SUnit to the last copy. 825void ScheduleDAGRRList::InsertCCCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 826 const TargetRegisterClass *DestRC, 827 const TargetRegisterClass *SrcRC, 828 SmallVector<SUnit*, 2> &Copies) { 829 SUnit *CopyFromSU = CreateNewSUnit(NULL); 830 CopyFromSU->CopySrcRC = SrcRC; 831 CopyFromSU->CopyDstRC = DestRC; 832 CopyFromSU->Depth = SU->Depth; 833 CopyFromSU->Height = SU->Height; 834 835 SUnit *CopyToSU = CreateNewSUnit(NULL); 836 CopyToSU->CopySrcRC = DestRC; 837 CopyToSU->CopyDstRC = SrcRC; 838 839 // Only copy scheduled successors. Cut them from old node's successor 840 // list and move them over. 841 SmallVector<std::pair<SUnit*, bool>, 4> DelDeps; 842 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 843 I != E; ++I) { 844 if (I->isSpecial) 845 continue; 846 if (I->Dep->isScheduled) { 847 CopyToSU->Height = std::max(CopyToSU->Height, I->Dep->Height+1); 848 AddPred(I->Dep, CopyToSU, I->isCtrl, false, I->Reg, I->Cost); 849 DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl)); 850 } 851 } 852 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 853 SUnit *Succ = DelDeps[i].first; 854 bool isCtrl = DelDeps[i].second; 855 RemovePred(Succ, SU, isCtrl, false); 856 } 857 858 AddPred(CopyFromSU, SU, false, false, Reg, -1); 859 AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1); 860 861 AvailableQueue->updateNode(SU); 862 AvailableQueue->addNode(CopyFromSU); 863 AvailableQueue->addNode(CopyToSU); 864 Copies.push_back(CopyFromSU); 865 Copies.push_back(CopyToSU); 866 867 ++NumCCCopies; 868} 869 870/// getPhysicalRegisterVT - Returns the ValueType of the physical register 871/// definition of the specified node. 872/// FIXME: Move to SelectionDAG? 873static MVT::ValueType getPhysicalRegisterVT(SDNode *N, unsigned Reg, 874 const TargetInstrInfo *TII) { 875 const TargetInstrDesc &TID = TII->get(N->getTargetOpcode()); 876 assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 877 unsigned NumRes = TID.getNumDefs(); 878 for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { 879 if (Reg == *ImpDef) 880 break; 881 ++NumRes; 882 } 883 return N->getValueType(NumRes); 884} 885 886/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 887/// scheduling of the given node to satisfy live physical register dependencies. 888/// If the specific node is the last one that's available to schedule, do 889/// whatever is necessary (i.e. backtracking or cloning) to make it possible. 890bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, 891 SmallVector<unsigned, 4> &LRegs){ 892 if (LiveRegs.empty()) 893 return false; 894 895 SmallSet<unsigned, 4> RegAdded; 896 // If this node would clobber any "live" register, then it's not ready. 897 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 898 I != E; ++I) { 899 if (I->Cost < 0) { 900 unsigned Reg = I->Reg; 901 if (LiveRegs.count(Reg) && LiveRegDefs[Reg] != I->Dep) { 902 if (RegAdded.insert(Reg)) 903 LRegs.push_back(Reg); 904 } 905 for (const unsigned *Alias = TRI->getAliasSet(Reg); 906 *Alias; ++Alias) 907 if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != I->Dep) { 908 if (RegAdded.insert(*Alias)) 909 LRegs.push_back(*Alias); 910 } 911 } 912 } 913 914 for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) { 915 SDNode *Node = (i == 0) ? SU->Node : SU->FlaggedNodes[i-1]; 916 if (!Node || !Node->isTargetOpcode()) 917 continue; 918 const TargetInstrDesc &TID = TII->get(Node->getTargetOpcode()); 919 if (!TID.ImplicitDefs) 920 continue; 921 for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) { 922 if (LiveRegs.count(*Reg) && LiveRegDefs[*Reg] != SU) { 923 if (RegAdded.insert(*Reg)) 924 LRegs.push_back(*Reg); 925 } 926 for (const unsigned *Alias = TRI->getAliasSet(*Reg); 927 *Alias; ++Alias) 928 if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != SU) { 929 if (RegAdded.insert(*Alias)) 930 LRegs.push_back(*Alias); 931 } 932 } 933 } 934 return !LRegs.empty(); 935} 936 937 938/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 939/// schedulers. 940void ScheduleDAGRRList::ListScheduleBottomUp() { 941 unsigned CurCycle = 0; 942 // Add root to Available queue. 943 if (!SUnits.empty()) { 944 SUnit *RootSU = SUnitMap[DAG.getRoot().Val].front(); 945 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); 946 RootSU->isAvailable = true; 947 AvailableQueue->push(RootSU); 948 } 949 950 // While Available queue is not empty, grab the node with the highest 951 // priority. If it is not ready put it back. Schedule the node. 952 SmallVector<SUnit*, 4> NotReady; 953 while (!AvailableQueue->empty()) { 954 bool Delayed = false; 955 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 956 SUnit *CurSU = AvailableQueue->pop(); 957 while (CurSU) { 958 if (CurSU->CycleBound <= CurCycle) { 959 SmallVector<unsigned, 4> LRegs; 960 if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 961 break; 962 Delayed = true; 963 LRegsMap.insert(std::make_pair(CurSU, LRegs)); 964 } 965 966 CurSU->isPending = true; // This SU is not in AvailableQueue right now. 967 NotReady.push_back(CurSU); 968 CurSU = AvailableQueue->pop(); 969 } 970 971 // All candidates are delayed due to live physical reg dependencies. 972 // Try backtracking, code duplication, or inserting cross class copies 973 // to resolve it. 974 if (Delayed && !CurSU) { 975 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 976 SUnit *TrySU = NotReady[i]; 977 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 978 979 // Try unscheduling up to the point where it's safe to schedule 980 // this node. 981 unsigned LiveCycle = CurCycle; 982 for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) { 983 unsigned Reg = LRegs[j]; 984 unsigned LCycle = LiveRegCycles[Reg]; 985 LiveCycle = std::min(LiveCycle, LCycle); 986 } 987 SUnit *OldSU = Sequence[LiveCycle]; 988 if (!WillCreateCycle(TrySU, OldSU)) { 989 BacktrackBottomUp(TrySU, LiveCycle, CurCycle); 990 // Force the current node to be scheduled before the node that 991 // requires the physical reg dep. 992 if (OldSU->isAvailable) { 993 OldSU->isAvailable = false; 994 AvailableQueue->remove(OldSU); 995 } 996 AddPred(TrySU, OldSU, true, true); 997 // If one or more successors has been unscheduled, then the current 998 // node is no longer avaialable. Schedule a successor that's now 999 // available instead. 1000 if (!TrySU->isAvailable) 1001 CurSU = AvailableQueue->pop(); 1002 else { 1003 CurSU = TrySU; 1004 TrySU->isPending = false; 1005 NotReady.erase(NotReady.begin()+i); 1006 } 1007 break; 1008 } 1009 } 1010 1011 if (!CurSU) { 1012 // Can't backtrack. Try duplicating the nodes that produces these 1013 // "expensive to copy" values to break the dependency. In case even 1014 // that doesn't work, insert cross class copies. 1015 SUnit *TrySU = NotReady[0]; 1016 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 1017 assert(LRegs.size() == 1 && "Can't handle this yet!"); 1018 unsigned Reg = LRegs[0]; 1019 SUnit *LRDef = LiveRegDefs[Reg]; 1020 SUnit *NewDef = CopyAndMoveSuccessors(LRDef); 1021 if (!NewDef) { 1022 // Issue expensive cross register class copies. 1023 MVT::ValueType VT = getPhysicalRegisterVT(LRDef->Node, Reg, TII); 1024 const TargetRegisterClass *RC = 1025 TRI->getPhysicalRegisterRegClass(Reg, VT); 1026 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 1027 if (!DestRC) { 1028 assert(false && "Don't know how to copy this physical register!"); 1029 abort(); 1030 } 1031 SmallVector<SUnit*, 2> Copies; 1032 InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 1033 DOUT << "Adding an edge from SU # " << TrySU->NodeNum 1034 << " to SU #" << Copies.front()->NodeNum << "\n"; 1035 AddPred(TrySU, Copies.front(), true, true); 1036 NewDef = Copies.back(); 1037 } 1038 1039 DOUT << "Adding an edge from SU # " << NewDef->NodeNum 1040 << " to SU #" << TrySU->NodeNum << "\n"; 1041 LiveRegDefs[Reg] = NewDef; 1042 AddPred(NewDef, TrySU, true, true); 1043 TrySU->isAvailable = false; 1044 CurSU = NewDef; 1045 } 1046 1047 if (!CurSU) { 1048 assert(false && "Unable to resolve live physical register dependencies!"); 1049 abort(); 1050 } 1051 } 1052 1053 // Add the nodes that aren't ready back onto the available list. 1054 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 1055 NotReady[i]->isPending = false; 1056 // May no longer be available due to backtracking. 1057 if (NotReady[i]->isAvailable) 1058 AvailableQueue->push(NotReady[i]); 1059 } 1060 NotReady.clear(); 1061 1062 if (!CurSU) 1063 Sequence.push_back(0); 1064 else { 1065 ScheduleNodeBottomUp(CurSU, CurCycle); 1066 Sequence.push_back(CurSU); 1067 } 1068 ++CurCycle; 1069 } 1070 1071 // Reverse the order if it is bottom up. 1072 std::reverse(Sequence.begin(), Sequence.end()); 1073 1074 1075#ifndef NDEBUG 1076 // Verify that all SUnits were scheduled. 1077 bool AnyNotSched = false; 1078 unsigned DeadNodes = 0; 1079 unsigned Noops = 0; 1080 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 1081 if (!SUnits[i].isScheduled) { 1082 if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 1083 ++DeadNodes; 1084 continue; 1085 } 1086 if (!AnyNotSched) 1087 cerr << "*** List scheduling failed! ***\n"; 1088 SUnits[i].dump(&DAG); 1089 cerr << "has not been scheduled!\n"; 1090 AnyNotSched = true; 1091 } 1092 if (SUnits[i].NumSuccsLeft != 0) { 1093 if (!AnyNotSched) 1094 cerr << "*** List scheduling failed! ***\n"; 1095 SUnits[i].dump(&DAG); 1096 cerr << "has successors left!\n"; 1097 AnyNotSched = true; 1098 } 1099 } 1100 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 1101 if (!Sequence[i]) 1102 ++Noops; 1103 assert(!AnyNotSched); 1104 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 1105 "The number of nodes scheduled doesn't match the expected number!"); 1106#endif 1107} 1108 1109//===----------------------------------------------------------------------===// 1110// Top-Down Scheduling 1111//===----------------------------------------------------------------------===// 1112 1113/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 1114/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 1115void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain, 1116 unsigned CurCycle) { 1117 // FIXME: the distance between two nodes is not always == the predecessor's 1118 // latency. For example, the reader can very well read the register written 1119 // by the predecessor later than the issue cycle. It also depends on the 1120 // interrupt model (drain vs. freeze). 1121 SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency); 1122 1123 --SuccSU->NumPredsLeft; 1124 1125#ifndef NDEBUG 1126 if (SuccSU->NumPredsLeft < 0) { 1127 cerr << "*** List scheduling failed! ***\n"; 1128 SuccSU->dump(&DAG); 1129 cerr << " has been released too many times!\n"; 1130 assert(0); 1131 } 1132#endif 1133 1134 if (SuccSU->NumPredsLeft == 0) { 1135 SuccSU->isAvailable = true; 1136 AvailableQueue->push(SuccSU); 1137 } 1138} 1139 1140 1141/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 1142/// count of its successors. If a successor pending count is zero, add it to 1143/// the Available queue. 1144void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 1145 DOUT << "*** Scheduling [" << CurCycle << "]: "; 1146 DEBUG(SU->dump(&DAG)); 1147 SU->Cycle = CurCycle; 1148 1149 AvailableQueue->ScheduledNode(SU); 1150 1151 // Top down: release successors 1152 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1153 I != E; ++I) 1154 ReleaseSucc(I->Dep, I->isCtrl, CurCycle); 1155 SU->isScheduled = true; 1156} 1157 1158/// ListScheduleTopDown - The main loop of list scheduling for top-down 1159/// schedulers. 1160void ScheduleDAGRRList::ListScheduleTopDown() { 1161 unsigned CurCycle = 0; 1162 1163 // All leaves to Available queue. 1164 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 1165 // It is available if it has no predecessors. 1166 if (SUnits[i].Preds.empty()) { 1167 AvailableQueue->push(&SUnits[i]); 1168 SUnits[i].isAvailable = true; 1169 } 1170 } 1171 1172 // While Available queue is not empty, grab the node with the highest 1173 // priority. If it is not ready put it back. Schedule the node. 1174 std::vector<SUnit*> NotReady; 1175 while (!AvailableQueue->empty()) { 1176 SUnit *CurSU = AvailableQueue->pop(); 1177 while (CurSU && CurSU->CycleBound > CurCycle) { 1178 NotReady.push_back(CurSU); 1179 CurSU = AvailableQueue->pop(); 1180 } 1181 1182 // Add the nodes that aren't ready back onto the available list. 1183 AvailableQueue->push_all(NotReady); 1184 NotReady.clear(); 1185 1186 if (!CurSU) 1187 Sequence.push_back(0); 1188 else { 1189 ScheduleNodeTopDown(CurSU, CurCycle); 1190 Sequence.push_back(CurSU); 1191 } 1192 ++CurCycle; 1193 } 1194 1195 1196#ifndef NDEBUG 1197 // Verify that all SUnits were scheduled. 1198 bool AnyNotSched = false; 1199 unsigned DeadNodes = 0; 1200 unsigned Noops = 0; 1201 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 1202 if (!SUnits[i].isScheduled) { 1203 if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 1204 ++DeadNodes; 1205 continue; 1206 } 1207 if (!AnyNotSched) 1208 cerr << "*** List scheduling failed! ***\n"; 1209 SUnits[i].dump(&DAG); 1210 cerr << "has not been scheduled!\n"; 1211 AnyNotSched = true; 1212 } 1213 if (SUnits[i].NumPredsLeft != 0) { 1214 if (!AnyNotSched) 1215 cerr << "*** List scheduling failed! ***\n"; 1216 SUnits[i].dump(&DAG); 1217 cerr << "has predecessors left!\n"; 1218 AnyNotSched = true; 1219 } 1220 } 1221 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 1222 if (!Sequence[i]) 1223 ++Noops; 1224 assert(!AnyNotSched); 1225 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 1226 "The number of nodes scheduled doesn't match the expected number!"); 1227#endif 1228} 1229 1230 1231 1232//===----------------------------------------------------------------------===// 1233// RegReductionPriorityQueue Implementation 1234//===----------------------------------------------------------------------===// 1235// 1236// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers 1237// to reduce register pressure. 1238// 1239namespace { 1240 template<class SF> 1241 class RegReductionPriorityQueue; 1242 1243 /// Sorting functions for the Available queue. 1244 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 1245 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; 1246 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} 1247 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 1248 1249 bool operator()(const SUnit* left, const SUnit* right) const; 1250 }; 1251 1252 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 1253 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; 1254 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} 1255 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 1256 1257 bool operator()(const SUnit* left, const SUnit* right) const; 1258 }; 1259} // end anonymous namespace 1260 1261static inline bool isCopyFromLiveIn(const SUnit *SU) { 1262 SDNode *N = SU->Node; 1263 return N && N->getOpcode() == ISD::CopyFromReg && 1264 N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag; 1265} 1266 1267namespace { 1268 template<class SF> 1269 class VISIBILITY_HIDDEN RegReductionPriorityQueue 1270 : public SchedulingPriorityQueue { 1271 std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue; 1272 1273 public: 1274 RegReductionPriorityQueue() : 1275 Queue(SF(this)) {} 1276 1277 virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 1278 std::vector<SUnit> &sunits) {} 1279 1280 virtual void addNode(const SUnit *SU) {} 1281 1282 virtual void updateNode(const SUnit *SU) {} 1283 1284 virtual void releaseState() {} 1285 1286 virtual unsigned getNodePriority(const SUnit *SU) const { 1287 return 0; 1288 } 1289 1290 unsigned size() const { return Queue.size(); } 1291 1292 bool empty() const { return Queue.empty(); } 1293 1294 void push(SUnit *U) { 1295 Queue.push(U); 1296 } 1297 void push_all(const std::vector<SUnit *> &Nodes) { 1298 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 1299 Queue.push(Nodes[i]); 1300 } 1301 1302 SUnit *pop() { 1303 if (empty()) return NULL; 1304 SUnit *V = Queue.top(); 1305 Queue.pop(); 1306 return V; 1307 } 1308 1309 /// remove - This is a really inefficient way to remove a node from a 1310 /// priority queue. We should roll our own heap to make this better or 1311 /// something. 1312 void remove(SUnit *SU) { 1313 std::vector<SUnit*> Temp; 1314 1315 assert(!Queue.empty() && "Not in queue!"); 1316 while (Queue.top() != SU) { 1317 Temp.push_back(Queue.top()); 1318 Queue.pop(); 1319 assert(!Queue.empty() && "Not in queue!"); 1320 } 1321 1322 // Remove the node from the PQ. 1323 Queue.pop(); 1324 1325 // Add all the other nodes back. 1326 for (unsigned i = 0, e = Temp.size(); i != e; ++i) 1327 Queue.push(Temp[i]); 1328 } 1329 }; 1330 1331 template<class SF> 1332 class VISIBILITY_HIDDEN BURegReductionPriorityQueue 1333 : public RegReductionPriorityQueue<SF> { 1334 // SUnitMap SDNode to SUnit mapping (n -> n). 1335 DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap; 1336 1337 // SUnits - The SUnits for the current graph. 1338 const std::vector<SUnit> *SUnits; 1339 1340 // SethiUllmanNumbers - The SethiUllman number for each node. 1341 std::vector<unsigned> SethiUllmanNumbers; 1342 1343 const TargetInstrInfo *TII; 1344 const TargetRegisterInfo *TRI; 1345 ScheduleDAGRRList *scheduleDAG; 1346 public: 1347 explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii, 1348 const TargetRegisterInfo *tri) 1349 : TII(tii), TRI(tri), scheduleDAG(NULL) {} 1350 1351 void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 1352 std::vector<SUnit> &sunits) { 1353 SUnitMap = &sumap; 1354 SUnits = &sunits; 1355 // Add pseudo dependency edges for two-address nodes. 1356 AddPseudoTwoAddrDeps(); 1357 // Calculate node priorities. 1358 CalculateSethiUllmanNumbers(); 1359 } 1360 1361 void addNode(const SUnit *SU) { 1362 SethiUllmanNumbers.resize(SUnits->size(), 0); 1363 CalcNodeSethiUllmanNumber(SU); 1364 } 1365 1366 void updateNode(const SUnit *SU) { 1367 SethiUllmanNumbers[SU->NodeNum] = 0; 1368 CalcNodeSethiUllmanNumber(SU); 1369 } 1370 1371 void releaseState() { 1372 SUnits = 0; 1373 SethiUllmanNumbers.clear(); 1374 } 1375 1376 unsigned getNodePriority(const SUnit *SU) const { 1377 assert(SU->NodeNum < SethiUllmanNumbers.size()); 1378 unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; 1379 if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU)) 1380 // CopyFromReg should be close to its def because it restricts 1381 // allocation choices. But if it is a livein then perhaps we want it 1382 // closer to its uses so it can be coalesced. 1383 return 0xffff; 1384 else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 1385 // CopyToReg should be close to its uses to facilitate coalescing and 1386 // avoid spilling. 1387 return 0; 1388 else if (Opc == TargetInstrInfo::EXTRACT_SUBREG || 1389 Opc == TargetInstrInfo::INSERT_SUBREG) 1390 // EXTRACT_SUBREG / INSERT_SUBREG should be close to its use to 1391 // facilitate coalescing. 1392 return 0; 1393 else if (SU->NumSuccs == 0) 1394 // If SU does not have a use, i.e. it doesn't produce a value that would 1395 // be consumed (e.g. store), then it terminates a chain of computation. 1396 // Give it a large SethiUllman number so it will be scheduled right 1397 // before its predecessors that it doesn't lengthen their live ranges. 1398 return 0xffff; 1399 else if (SU->NumPreds == 0) 1400 // If SU does not have a def, schedule it close to its uses because it 1401 // does not lengthen any live ranges. 1402 return 0; 1403 else 1404 return SethiUllmanNumbers[SU->NodeNum]; 1405 } 1406 1407 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) { 1408 scheduleDAG = scheduleDag; 1409 } 1410 1411 private: 1412 bool canClobber(const SUnit *SU, const SUnit *Op); 1413 void AddPseudoTwoAddrDeps(); 1414 void CalculateSethiUllmanNumbers(); 1415 unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); 1416 }; 1417 1418 1419 template<class SF> 1420 class VISIBILITY_HIDDEN TDRegReductionPriorityQueue 1421 : public RegReductionPriorityQueue<SF> { 1422 // SUnitMap SDNode to SUnit mapping (n -> n). 1423 DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap; 1424 1425 // SUnits - The SUnits for the current graph. 1426 const std::vector<SUnit> *SUnits; 1427 1428 // SethiUllmanNumbers - The SethiUllman number for each node. 1429 std::vector<unsigned> SethiUllmanNumbers; 1430 1431 public: 1432 TDRegReductionPriorityQueue() {} 1433 1434 void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 1435 std::vector<SUnit> &sunits) { 1436 SUnitMap = &sumap; 1437 SUnits = &sunits; 1438 // Calculate node priorities. 1439 CalculateSethiUllmanNumbers(); 1440 } 1441 1442 void addNode(const SUnit *SU) { 1443 SethiUllmanNumbers.resize(SUnits->size(), 0); 1444 CalcNodeSethiUllmanNumber(SU); 1445 } 1446 1447 void updateNode(const SUnit *SU) { 1448 SethiUllmanNumbers[SU->NodeNum] = 0; 1449 CalcNodeSethiUllmanNumber(SU); 1450 } 1451 1452 void releaseState() { 1453 SUnits = 0; 1454 SethiUllmanNumbers.clear(); 1455 } 1456 1457 unsigned getNodePriority(const SUnit *SU) const { 1458 assert(SU->NodeNum < SethiUllmanNumbers.size()); 1459 return SethiUllmanNumbers[SU->NodeNum]; 1460 } 1461 1462 private: 1463 void CalculateSethiUllmanNumbers(); 1464 unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); 1465 }; 1466} 1467 1468/// closestSucc - Returns the scheduled cycle of the successor which is 1469/// closet to the current cycle. 1470static unsigned closestSucc(const SUnit *SU) { 1471 unsigned MaxCycle = 0; 1472 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1473 I != E; ++I) { 1474 unsigned Cycle = I->Dep->Cycle; 1475 // If there are bunch of CopyToRegs stacked up, they should be considered 1476 // to be at the same position. 1477 if (I->Dep->Node && I->Dep->Node->getOpcode() == ISD::CopyToReg) 1478 Cycle = closestSucc(I->Dep)+1; 1479 if (Cycle > MaxCycle) 1480 MaxCycle = Cycle; 1481 } 1482 return MaxCycle; 1483} 1484 1485/// calcMaxScratches - Returns an cost estimate of the worse case requirement 1486/// for scratch registers. Live-in operands and live-out results don't count 1487/// since they are "fixed". 1488static unsigned calcMaxScratches(const SUnit *SU) { 1489 unsigned Scratches = 0; 1490 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1491 I != E; ++I) { 1492 if (I->isCtrl) continue; // ignore chain preds 1493 if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyFromReg) 1494 Scratches++; 1495 } 1496 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1497 I != E; ++I) { 1498 if (I->isCtrl) continue; // ignore chain succs 1499 if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyToReg) 1500 Scratches += 10; 1501 } 1502 return Scratches; 1503} 1504 1505// Bottom up 1506bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1507 // There used to be a special tie breaker here that looked for 1508 // two-address instructions and preferred the instruction with a 1509 // def&use operand. The special case triggered diagnostics when 1510 // _GLIBCXX_DEBUG was enabled because it broke the strict weak 1511 // ordering that priority_queue requires. It didn't help much anyway 1512 // because AddPseudoTwoAddrDeps already covers many of the cases 1513 // where it would have applied. In addition, it's counter-intuitive 1514 // that a tie breaker would be the first thing attempted. There's a 1515 // "real" tie breaker below that is the operation of last resort. 1516 // The fact that the "special tie breaker" would trigger when there 1517 // wasn't otherwise a tie is what broke the strict weak ordering 1518 // constraint. 1519 1520 unsigned LPriority = SPQ->getNodePriority(left); 1521 unsigned RPriority = SPQ->getNodePriority(right); 1522 if (LPriority != RPriority) 1523 return LPriority > RPriority; 1524 1525 // Try schedule def + use closer when Sethi-Ullman numbers are the same. 1526 // e.g. 1527 // t1 = op t2, c1 1528 // t3 = op t4, c2 1529 // 1530 // and the following instructions are both ready. 1531 // t2 = op c3 1532 // t4 = op c4 1533 // 1534 // Then schedule t2 = op first. 1535 // i.e. 1536 // t4 = op c4 1537 // t2 = op c3 1538 // t1 = op t2, c1 1539 // t3 = op t4, c2 1540 // 1541 // This creates more short live intervals. 1542 unsigned LDist = closestSucc(left); 1543 unsigned RDist = closestSucc(right); 1544 if (LDist != RDist) 1545 return LDist < RDist; 1546 1547 // Intuitively, it's good to push down instructions whose results are 1548 // liveout so their long live ranges won't conflict with other values 1549 // which are needed inside the BB. Further prioritize liveout instructions 1550 // by the number of operands which are calculated within the BB. 1551 unsigned LScratch = calcMaxScratches(left); 1552 unsigned RScratch = calcMaxScratches(right); 1553 if (LScratch != RScratch) 1554 return LScratch > RScratch; 1555 1556 if (left->Height != right->Height) 1557 return left->Height > right->Height; 1558 1559 if (left->Depth != right->Depth) 1560 return left->Depth < right->Depth; 1561 1562 if (left->CycleBound != right->CycleBound) 1563 return left->CycleBound > right->CycleBound; 1564 1565 // FIXME: No strict ordering. 1566 return false; 1567} 1568 1569template<class SF> bool 1570BURegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) { 1571 if (SU->isTwoAddress) { 1572 unsigned Opc = SU->Node->getTargetOpcode(); 1573 const TargetInstrDesc &TID = TII->get(Opc); 1574 unsigned NumRes = TID.getNumDefs(); 1575 unsigned NumOps = TID.getNumOperands() - NumRes; 1576 for (unsigned i = 0; i != NumOps; ++i) { 1577 if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) { 1578 SDNode *DU = SU->Node->getOperand(i).Val; 1579 if ((*SUnitMap).find(DU) != (*SUnitMap).end() && 1580 Op == (*SUnitMap)[DU][SU->InstanceNo]) 1581 return true; 1582 } 1583 } 1584 } 1585 return false; 1586} 1587 1588 1589/// hasCopyToRegUse - Return true if SU has a value successor that is a 1590/// CopyToReg node. 1591static bool hasCopyToRegUse(SUnit *SU) { 1592 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1593 I != E; ++I) { 1594 if (I->isCtrl) continue; 1595 SUnit *SuccSU = I->Dep; 1596 if (SuccSU->Node && SuccSU->Node->getOpcode() == ISD::CopyToReg) 1597 return true; 1598 } 1599 return false; 1600} 1601 1602/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's 1603/// physical register def. 1604static bool canClobberPhysRegDefs(SUnit *SuccSU, SUnit *SU, 1605 const TargetInstrInfo *TII, 1606 const TargetRegisterInfo *TRI) { 1607 SDNode *N = SuccSU->Node; 1608 unsigned NumDefs = TII->get(N->getTargetOpcode()).getNumDefs(); 1609 const unsigned *ImpDefs = TII->get(N->getTargetOpcode()).getImplicitDefs(); 1610 if (!ImpDefs) 1611 return false; 1612 const unsigned *SUImpDefs = 1613 TII->get(SU->Node->getTargetOpcode()).getImplicitDefs(); 1614 if (!SUImpDefs) 1615 return false; 1616 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) { 1617 MVT::ValueType VT = N->getValueType(i); 1618 if (VT == MVT::Flag || VT == MVT::Other) 1619 continue; 1620 unsigned Reg = ImpDefs[i - NumDefs]; 1621 for (;*SUImpDefs; ++SUImpDefs) { 1622 unsigned SUReg = *SUImpDefs; 1623 if (TRI->regsOverlap(Reg, SUReg)) 1624 return true; 1625 } 1626 } 1627 return false; 1628} 1629 1630/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses 1631/// it as a def&use operand. Add a pseudo control edge from it to the other 1632/// node (if it won't create a cycle) so the two-address one will be scheduled 1633/// first (lower in the schedule). If both nodes are two-address, favor the 1634/// one that has a CopyToReg use (more likely to be a loop induction update). 1635/// If both are two-address, but one is commutable while the other is not 1636/// commutable, favor the one that's not commutable. 1637template<class SF> 1638void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { 1639 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 1640 SUnit *SU = (SUnit *)&((*SUnits)[i]); 1641 if (!SU->isTwoAddress) 1642 continue; 1643 1644 SDNode *Node = SU->Node; 1645 if (!Node || !Node->isTargetOpcode() || SU->FlaggedNodes.size() > 0) 1646 continue; 1647 1648 unsigned Opc = Node->getTargetOpcode(); 1649 const TargetInstrDesc &TID = TII->get(Opc); 1650 unsigned NumRes = TID.getNumDefs(); 1651 unsigned NumOps = TID.getNumOperands() - NumRes; 1652 for (unsigned j = 0; j != NumOps; ++j) { 1653 if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) != -1) { 1654 SDNode *DU = SU->Node->getOperand(j).Val; 1655 if ((*SUnitMap).find(DU) == (*SUnitMap).end()) 1656 continue; 1657 SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo]; 1658 if (!DUSU) continue; 1659 for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end(); 1660 I != E; ++I) { 1661 if (I->isCtrl) continue; 1662 SUnit *SuccSU = I->Dep; 1663 if (SuccSU == SU) 1664 continue; 1665 // Be conservative. Ignore if nodes aren't at roughly the same 1666 // depth and height. 1667 if (SuccSU->Height < SU->Height && (SU->Height - SuccSU->Height) > 1) 1668 continue; 1669 if (!SuccSU->Node || !SuccSU->Node->isTargetOpcode()) 1670 continue; 1671 // Don't constrain nodes with physical register defs if the 1672 // predecessor can clobber them. 1673 if (SuccSU->hasPhysRegDefs) { 1674 if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI)) 1675 continue; 1676 } 1677 // Don't constraint extract_subreg / insert_subreg these may be 1678 // coalesced away. We don't them close to their uses. 1679 unsigned SuccOpc = SuccSU->Node->getTargetOpcode(); 1680 if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG || 1681 SuccOpc == TargetInstrInfo::INSERT_SUBREG) 1682 continue; 1683 if ((!canClobber(SuccSU, DUSU) || 1684 (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) || 1685 (!SU->isCommutable && SuccSU->isCommutable)) && 1686 !scheduleDAG->IsReachable(SuccSU, SU)) { 1687 DOUT << "Adding an edge from SU # " << SU->NodeNum 1688 << " to SU #" << SuccSU->NodeNum << "\n"; 1689 scheduleDAG->AddPred(SU, SuccSU, true, true); 1690 } 1691 } 1692 } 1693 } 1694 } 1695} 1696 1697/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. 1698/// Smaller number is the higher priority. 1699template<class SF> 1700unsigned BURegReductionPriorityQueue<SF>:: 1701CalcNodeSethiUllmanNumber(const SUnit *SU) { 1702 unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 1703 if (SethiUllmanNumber != 0) 1704 return SethiUllmanNumber; 1705 1706 unsigned Extra = 0; 1707 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1708 I != E; ++I) { 1709 if (I->isCtrl) continue; // ignore chain preds 1710 SUnit *PredSU = I->Dep; 1711 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); 1712 if (PredSethiUllman > SethiUllmanNumber) { 1713 SethiUllmanNumber = PredSethiUllman; 1714 Extra = 0; 1715 } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) 1716 ++Extra; 1717 } 1718 1719 SethiUllmanNumber += Extra; 1720 1721 if (SethiUllmanNumber == 0) 1722 SethiUllmanNumber = 1; 1723 1724 return SethiUllmanNumber; 1725} 1726 1727/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 1728/// scheduling units. 1729template<class SF> 1730void BURegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 1731 SethiUllmanNumbers.assign(SUnits->size(), 0); 1732 1733 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 1734 CalcNodeSethiUllmanNumber(&(*SUnits)[i]); 1735} 1736 1737/// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled 1738/// predecessors of the successors of the SUnit SU. Stop when the provided 1739/// limit is exceeded. 1740static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU, 1741 unsigned Limit) { 1742 unsigned Sum = 0; 1743 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1744 I != E; ++I) { 1745 SUnit *SuccSU = I->Dep; 1746 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(), 1747 EE = SuccSU->Preds.end(); II != EE; ++II) { 1748 SUnit *PredSU = II->Dep; 1749 if (!PredSU->isScheduled) 1750 if (++Sum > Limit) 1751 return Sum; 1752 } 1753 } 1754 return Sum; 1755} 1756 1757 1758// Top down 1759bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1760 unsigned LPriority = SPQ->getNodePriority(left); 1761 unsigned RPriority = SPQ->getNodePriority(right); 1762 bool LIsTarget = left->Node && left->Node->isTargetOpcode(); 1763 bool RIsTarget = right->Node && right->Node->isTargetOpcode(); 1764 bool LIsFloater = LIsTarget && left->NumPreds == 0; 1765 bool RIsFloater = RIsTarget && right->NumPreds == 0; 1766 unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0; 1767 unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0; 1768 1769 if (left->NumSuccs == 0 && right->NumSuccs != 0) 1770 return false; 1771 else if (left->NumSuccs != 0 && right->NumSuccs == 0) 1772 return true; 1773 1774 if (LIsFloater) 1775 LBonus -= 2; 1776 if (RIsFloater) 1777 RBonus -= 2; 1778 if (left->NumSuccs == 1) 1779 LBonus += 2; 1780 if (right->NumSuccs == 1) 1781 RBonus += 2; 1782 1783 if (LPriority+LBonus != RPriority+RBonus) 1784 return LPriority+LBonus < RPriority+RBonus; 1785 1786 if (left->Depth != right->Depth) 1787 return left->Depth < right->Depth; 1788 1789 if (left->NumSuccsLeft != right->NumSuccsLeft) 1790 return left->NumSuccsLeft > right->NumSuccsLeft; 1791 1792 if (left->CycleBound != right->CycleBound) 1793 return left->CycleBound > right->CycleBound; 1794 1795 // FIXME: No strict ordering. 1796 return false; 1797} 1798 1799/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. 1800/// Smaller number is the higher priority. 1801template<class SF> 1802unsigned TDRegReductionPriorityQueue<SF>:: 1803CalcNodeSethiUllmanNumber(const SUnit *SU) { 1804 unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 1805 if (SethiUllmanNumber != 0) 1806 return SethiUllmanNumber; 1807 1808 unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; 1809 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 1810 SethiUllmanNumber = 0xffff; 1811 else if (SU->NumSuccsLeft == 0) 1812 // If SU does not have a use, i.e. it doesn't produce a value that would 1813 // be consumed (e.g. store), then it terminates a chain of computation. 1814 // Give it a small SethiUllman number so it will be scheduled right before 1815 // its predecessors that it doesn't lengthen their live ranges. 1816 SethiUllmanNumber = 0; 1817 else if (SU->NumPredsLeft == 0 && 1818 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) 1819 SethiUllmanNumber = 0xffff; 1820 else { 1821 int Extra = 0; 1822 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1823 I != E; ++I) { 1824 if (I->isCtrl) continue; // ignore chain preds 1825 SUnit *PredSU = I->Dep; 1826 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); 1827 if (PredSethiUllman > SethiUllmanNumber) { 1828 SethiUllmanNumber = PredSethiUllman; 1829 Extra = 0; 1830 } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) 1831 ++Extra; 1832 } 1833 1834 SethiUllmanNumber += Extra; 1835 } 1836 1837 return SethiUllmanNumber; 1838} 1839 1840/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 1841/// scheduling units. 1842template<class SF> 1843void TDRegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 1844 SethiUllmanNumbers.assign(SUnits->size(), 0); 1845 1846 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 1847 CalcNodeSethiUllmanNumber(&(*SUnits)[i]); 1848} 1849 1850//===----------------------------------------------------------------------===// 1851// Public Constructor Functions 1852//===----------------------------------------------------------------------===// 1853 1854llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, 1855 SelectionDAG *DAG, 1856 MachineBasicBlock *BB) { 1857 const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo(); 1858 const TargetRegisterInfo *TRI = DAG->getTarget().getRegisterInfo(); 1859 1860 BURegReductionPriorityQueue<bu_ls_rr_sort> *priorityQueue = 1861 new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII, TRI); 1862 1863 ScheduleDAGRRList * scheduleDAG = 1864 new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, priorityQueue); 1865 priorityQueue->setScheduleDAG(scheduleDAG); 1866 return scheduleDAG; 1867} 1868 1869llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, 1870 SelectionDAG *DAG, 1871 MachineBasicBlock *BB) { 1872 return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false, 1873 new TDRegReductionPriorityQueue<td_ls_rr_sort>()); 1874} 1875 1876