ScheduleDAGRRList.cpp revision d5ad440f4371448e2c926b4f6613cc7107dd5c5c
1//===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Evan Cheng and is distributed under the 6// University of Illinois Open Source 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 "sched" 19#include "llvm/CodeGen/ScheduleDAG.h" 20#include "llvm/CodeGen/SchedulerRegistry.h" 21#include "llvm/CodeGen/SSARegMap.h" 22#include "llvm/Target/MRegisterInfo.h" 23#include "llvm/Target/TargetData.h" 24#include "llvm/Target/TargetMachine.h" 25#include "llvm/Target/TargetInstrInfo.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/Support/Compiler.h" 28#include "llvm/ADT/Statistic.h" 29#include <climits> 30#include <iostream> 31#include <queue> 32#include "llvm/Support/CommandLine.h" 33using namespace llvm; 34 35static RegisterScheduler 36 burrListDAGScheduler("list-burr", 37 " Bottom-up register reduction list scheduling", 38 createBURRListDAGScheduler); 39static RegisterScheduler 40 tdrListrDAGScheduler("list-tdrr", 41 " Top-down register reduction list scheduling", 42 createTDRRListDAGScheduler); 43 44namespace { 45//===----------------------------------------------------------------------===// 46/// ScheduleDAGRRList - The actual register reduction list scheduler 47/// implementation. This supports both top-down and bottom-up scheduling. 48/// 49 50class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG { 51private: 52 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if 53 /// it is top-down. 54 bool isBottomUp; 55 56 /// AvailableQueue - The priority queue to use for the available SUnits. 57 /// 58 SchedulingPriorityQueue *AvailableQueue; 59 60public: 61 ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb, 62 const TargetMachine &tm, bool isbottomup, 63 SchedulingPriorityQueue *availqueue) 64 : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), 65 AvailableQueue(availqueue) { 66 } 67 68 ~ScheduleDAGRRList() { 69 delete AvailableQueue; 70 } 71 72 void Schedule(); 73 74private: 75 void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle); 76 void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle); 77 void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle); 78 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 79 void ListScheduleTopDown(); 80 void ListScheduleBottomUp(); 81 void CommuteNodesToReducePressure(); 82}; 83} // end anonymous namespace 84 85 86/// Schedule - Schedule the DAG using list scheduling. 87void ScheduleDAGRRList::Schedule() { 88 DEBUG(std::cerr << "********** List Scheduling **********\n"); 89 90 // Build scheduling units. 91 BuildSchedUnits(); 92 93 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 94 SUnits[su].dumpAll(&DAG)); 95 CalculateDepths(); 96 CalculateHeights(); 97 98 AvailableQueue->initNodes(SUnitMap, SUnits); 99 100 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. 101 if (isBottomUp) 102 ListScheduleBottomUp(); 103 else 104 ListScheduleTopDown(); 105 106 AvailableQueue->releaseState(); 107 108 CommuteNodesToReducePressure(); 109 110 DEBUG(std::cerr << "*** Final schedule ***\n"); 111 DEBUG(dumpSchedule()); 112 DEBUG(std::cerr << "\n"); 113 114 // Emit in scheduled order 115 EmitSchedule(); 116} 117 118/// CommuteNodesToReducePressure - If a node is two-address and commutable, and 119/// it is not the last use of its first operand, add it to the CommuteSet if 120/// possible. It will be commuted when it is translated to a MI. 121void ScheduleDAGRRList::CommuteNodesToReducePressure() { 122 std::set<SUnit *> OperandSeen; 123 for (unsigned i = Sequence.size()-1; i != 0; --i) { // Ignore first node. 124 SUnit *SU = Sequence[i]; 125 if (!SU) continue; 126 if (SU->isCommutable) { 127 unsigned Opc = SU->Node->getTargetOpcode(); 128 unsigned NumRes = CountResults(SU->Node); 129 unsigned NumOps = CountOperands(SU->Node); 130 for (unsigned j = 0; j != NumOps; ++j) { 131 if (TII->getOperandConstraint(Opc, j+NumRes, 132 TargetInstrInfo::TIED_TO) == -1) 133 continue; 134 135 SDNode *OpN = SU->Node->getOperand(j).Val; 136 SUnit *OpSU = SUnitMap[OpN]; 137 if (OpSU && OperandSeen.count(OpSU) == 1) { 138 // Ok, so SU is not the last use of OpSU, but SU is two-address so 139 // it will clobber OpSU. Try to commute SU if no other source operands 140 // are live below. 141 bool DoCommute = true; 142 for (unsigned k = 0; k < NumOps; ++k) { 143 if (k != j) { 144 OpN = SU->Node->getOperand(k).Val; 145 OpSU = SUnitMap[OpN]; 146 if (OpSU && OperandSeen.count(OpSU) == 1) { 147 DoCommute = false; 148 break; 149 } 150 } 151 } 152 if (DoCommute) 153 CommuteSet.insert(SU->Node); 154 } 155 156 // Only look at the first use&def node for now. 157 break; 158 } 159 } 160 161 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 162 I != E; ++I) { 163 if (!I->second) 164 OperandSeen.insert(I->first); 165 } 166 } 167} 168 169//===----------------------------------------------------------------------===// 170// Bottom-Up Scheduling 171//===----------------------------------------------------------------------===// 172 173/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 174/// the Available queue is the count reaches zero. Also update its cycle bound. 175void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain, 176 unsigned CurCycle) { 177 // FIXME: the distance between two nodes is not always == the predecessor's 178 // latency. For example, the reader can very well read the register written 179 // by the predecessor later than the issue cycle. It also depends on the 180 // interrupt model (drain vs. freeze). 181 PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency); 182 183 if (!isChain) 184 PredSU->NumSuccsLeft--; 185 else 186 PredSU->NumChainSuccsLeft--; 187 188#ifndef NDEBUG 189 if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) { 190 std::cerr << "*** List scheduling failed! ***\n"; 191 PredSU->dump(&DAG); 192 std::cerr << " has been released too many times!\n"; 193 assert(0); 194 } 195#endif 196 197 if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) { 198 // EntryToken has to go last! Special case it here. 199 if (PredSU->Node->getOpcode() != ISD::EntryToken) { 200 PredSU->isAvailable = true; 201 AvailableQueue->push(PredSU); 202 } 203 } 204} 205 206/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 207/// count of its predecessors. If a predecessor pending count is zero, add it to 208/// the Available queue. 209void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 210 DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: "); 211 DEBUG(SU->dump(&DAG)); 212 SU->Cycle = CurCycle; 213 214 AvailableQueue->ScheduledNode(SU); 215 Sequence.push_back(SU); 216 217 // Bottom up: release predecessors 218 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 219 I != E; ++I) 220 ReleasePred(I->first, I->second, CurCycle); 221 SU->isScheduled = true; 222} 223 224/// isReady - True if node's lower cycle bound is less or equal to the current 225/// scheduling cycle. Always true if all nodes have uniform latency 1. 226static inline bool isReady(SUnit *SU, unsigned CurCycle) { 227 return SU->CycleBound <= CurCycle; 228} 229 230/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 231/// schedulers. 232void ScheduleDAGRRList::ListScheduleBottomUp() { 233 unsigned CurCycle = 0; 234 // Add root to Available queue. 235 AvailableQueue->push(SUnitMap[DAG.getRoot().Val]); 236 237 // While Available queue is not empty, grab the node with the highest 238 // priority. If it is not ready put it back. Schedule the node. 239 std::vector<SUnit*> NotReady; 240 while (!AvailableQueue->empty()) { 241 SUnit *CurNode = AvailableQueue->pop(); 242 while (CurNode && !isReady(CurNode, CurCycle)) { 243 NotReady.push_back(CurNode); 244 CurNode = AvailableQueue->pop(); 245 } 246 247 // Add the nodes that aren't ready back onto the available list. 248 AvailableQueue->push_all(NotReady); 249 NotReady.clear(); 250 251 if (CurNode != NULL) 252 ScheduleNodeBottomUp(CurNode, CurCycle); 253 CurCycle++; 254 } 255 256 // Add entry node last 257 if (DAG.getEntryNode().Val != DAG.getRoot().Val) { 258 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val]; 259 Sequence.push_back(Entry); 260 } 261 262 // Reverse the order if it is bottom up. 263 std::reverse(Sequence.begin(), Sequence.end()); 264 265 266#ifndef NDEBUG 267 // Verify that all SUnits were scheduled. 268 bool AnyNotSched = false; 269 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 270 if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) { 271 if (!AnyNotSched) 272 std::cerr << "*** List scheduling failed! ***\n"; 273 SUnits[i].dump(&DAG); 274 std::cerr << "has not been scheduled!\n"; 275 AnyNotSched = true; 276 } 277 } 278 assert(!AnyNotSched); 279#endif 280} 281 282//===----------------------------------------------------------------------===// 283// Top-Down Scheduling 284//===----------------------------------------------------------------------===// 285 286/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 287/// the PendingQueue if the count reaches zero. 288void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain, 289 unsigned CurCycle) { 290 // FIXME: the distance between two nodes is not always == the predecessor's 291 // latency. For example, the reader can very well read the register written 292 // by the predecessor later than the issue cycle. It also depends on the 293 // interrupt model (drain vs. freeze). 294 SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency); 295 296 if (!isChain) 297 SuccSU->NumPredsLeft--; 298 else 299 SuccSU->NumChainPredsLeft--; 300 301#ifndef NDEBUG 302 if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) { 303 std::cerr << "*** List scheduling failed! ***\n"; 304 SuccSU->dump(&DAG); 305 std::cerr << " has been released too many times!\n"; 306 assert(0); 307 } 308#endif 309 310 if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) { 311 SuccSU->isAvailable = true; 312 AvailableQueue->push(SuccSU); 313 } 314} 315 316 317/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 318/// count of its successors. If a successor pending count is zero, add it to 319/// the Available queue. 320void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 321 DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: "); 322 DEBUG(SU->dump(&DAG)); 323 SU->Cycle = CurCycle; 324 325 AvailableQueue->ScheduledNode(SU); 326 Sequence.push_back(SU); 327 328 // Top down: release successors 329 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 330 I != E; ++I) 331 ReleaseSucc(I->first, I->second, CurCycle); 332 SU->isScheduled = true; 333} 334 335void ScheduleDAGRRList::ListScheduleTopDown() { 336 unsigned CurCycle = 0; 337 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val]; 338 339 // All leaves to Available queue. 340 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 341 // It is available if it has no predecessors. 342 if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) { 343 AvailableQueue->push(&SUnits[i]); 344 SUnits[i].isAvailable = true; 345 } 346 } 347 348 // Emit the entry node first. 349 ScheduleNodeTopDown(Entry, CurCycle); 350 CurCycle++; 351 352 // While Available queue is not empty, grab the node with the highest 353 // priority. If it is not ready put it back. Schedule the node. 354 std::vector<SUnit*> NotReady; 355 while (!AvailableQueue->empty()) { 356 SUnit *CurNode = AvailableQueue->pop(); 357 while (CurNode && !isReady(CurNode, CurCycle)) { 358 NotReady.push_back(CurNode); 359 CurNode = AvailableQueue->pop(); 360 } 361 362 // Add the nodes that aren't ready back onto the available list. 363 AvailableQueue->push_all(NotReady); 364 NotReady.clear(); 365 366 if (CurNode != NULL) 367 ScheduleNodeTopDown(CurNode, CurCycle); 368 CurCycle++; 369 } 370 371 372#ifndef NDEBUG 373 // Verify that all SUnits were scheduled. 374 bool AnyNotSched = false; 375 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 376 if (!SUnits[i].isScheduled) { 377 if (!AnyNotSched) 378 std::cerr << "*** List scheduling failed! ***\n"; 379 SUnits[i].dump(&DAG); 380 std::cerr << "has not been scheduled!\n"; 381 AnyNotSched = true; 382 } 383 } 384 assert(!AnyNotSched); 385#endif 386} 387 388 389 390//===----------------------------------------------------------------------===// 391// RegReductionPriorityQueue Implementation 392//===----------------------------------------------------------------------===// 393// 394// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers 395// to reduce register pressure. 396// 397namespace { 398 template<class SF> 399 class RegReductionPriorityQueue; 400 401 /// Sorting functions for the Available queue. 402 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 403 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; 404 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} 405 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 406 407 bool operator()(const SUnit* left, const SUnit* right) const; 408 }; 409 410 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 411 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; 412 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} 413 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 414 415 bool operator()(const SUnit* left, const SUnit* right) const; 416 }; 417} // end anonymous namespace 418 419namespace { 420 template<class SF> 421 class VISIBILITY_HIDDEN RegReductionPriorityQueue 422 : public SchedulingPriorityQueue { 423 std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue; 424 425 public: 426 RegReductionPriorityQueue() : 427 Queue(SF(this)) {} 428 429 virtual void initNodes(std::map<SDNode*, SUnit*> &sumap, 430 std::vector<SUnit> &sunits) {} 431 virtual void releaseState() {} 432 433 virtual int getSethiUllmanNumber(unsigned NodeNum) const { 434 return 0; 435 } 436 437 bool empty() const { return Queue.empty(); } 438 439 void push(SUnit *U) { 440 Queue.push(U); 441 } 442 void push_all(const std::vector<SUnit *> &Nodes) { 443 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 444 Queue.push(Nodes[i]); 445 } 446 447 SUnit *pop() { 448 if (empty()) return NULL; 449 SUnit *V = Queue.top(); 450 Queue.pop(); 451 return V; 452 } 453 454 virtual bool isDUOperand(const SUnit *SU1, const SUnit *SU2) { 455 return false; 456 } 457 }; 458 459 template<class SF> 460 class VISIBILITY_HIDDEN BURegReductionPriorityQueue 461 : public RegReductionPriorityQueue<SF> { 462 // SUnitMap SDNode to SUnit mapping (n -> 1). 463 std::map<SDNode*, SUnit*> *SUnitMap; 464 465 // SUnits - The SUnits for the current graph. 466 const std::vector<SUnit> *SUnits; 467 468 // SethiUllmanNumbers - The SethiUllman number for each node. 469 std::vector<int> SethiUllmanNumbers; 470 471 const TargetInstrInfo *TII; 472 public: 473 BURegReductionPriorityQueue(const TargetInstrInfo *tii) 474 : TII(tii) {} 475 476 void initNodes(std::map<SDNode*, SUnit*> &sumap, 477 std::vector<SUnit> &sunits) { 478 SUnitMap = &sumap; 479 SUnits = &sunits; 480 // Add pseudo dependency edges for two-address nodes. 481 AddPseudoTwoAddrDeps(); 482 // Calculate node priorities. 483 CalculatePriorities(); 484 } 485 486 void releaseState() { 487 SUnits = 0; 488 SethiUllmanNumbers.clear(); 489 } 490 491 int getSethiUllmanNumber(unsigned NodeNum) const { 492 assert(NodeNum < SethiUllmanNumbers.size()); 493 return SethiUllmanNumbers[NodeNum]; 494 } 495 496 bool isDUOperand(const SUnit *SU1, const SUnit *SU2) { 497 unsigned Opc = SU1->Node->getTargetOpcode(); 498 unsigned NumRes = ScheduleDAG::CountResults(SU1->Node); 499 unsigned NumOps = ScheduleDAG::CountOperands(SU1->Node); 500 for (unsigned i = 0; i != NumOps; ++i) { 501 if (TII->getOperandConstraint(Opc, i+NumRes, 502 TargetInstrInfo::TIED_TO) == -1) 503 continue; 504 if (SU1->Node->getOperand(i).isOperand(SU2->Node)) 505 return true; 506 } 507 return false; 508 } 509 private: 510 bool canClobber(SUnit *SU, SUnit *Op); 511 void AddPseudoTwoAddrDeps(); 512 void CalculatePriorities(); 513 int CalcNodePriority(const SUnit *SU); 514 }; 515 516 517 template<class SF> 518 class TDRegReductionPriorityQueue : public RegReductionPriorityQueue<SF> { 519 // SUnitMap SDNode to SUnit mapping (n -> 1). 520 std::map<SDNode*, SUnit*> *SUnitMap; 521 522 // SUnits - The SUnits for the current graph. 523 const std::vector<SUnit> *SUnits; 524 525 // SethiUllmanNumbers - The SethiUllman number for each node. 526 std::vector<int> SethiUllmanNumbers; 527 528 public: 529 TDRegReductionPriorityQueue() {} 530 531 void initNodes(std::map<SDNode*, SUnit*> &sumap, 532 std::vector<SUnit> &sunits) { 533 SUnitMap = &sumap; 534 SUnits = &sunits; 535 // Calculate node priorities. 536 CalculatePriorities(); 537 } 538 539 void releaseState() { 540 SUnits = 0; 541 SethiUllmanNumbers.clear(); 542 } 543 544 int getSethiUllmanNumber(unsigned NodeNum) const { 545 assert(NodeNum < SethiUllmanNumbers.size()); 546 return SethiUllmanNumbers[NodeNum]; 547 } 548 549 private: 550 void CalculatePriorities(); 551 int CalcNodePriority(const SUnit *SU); 552 }; 553} 554 555static bool isFloater(const SUnit *SU) { 556 if (SU->Node->isTargetOpcode()) { 557 if (SU->NumPreds == 0) 558 return true; 559 if (SU->NumPreds == 1) { 560 for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end(); 561 I != E; ++I) { 562 if (I->second) continue; 563 564 SUnit *PredSU = I->first; 565 unsigned Opc = PredSU->Node->getOpcode(); 566 if (Opc != ISD::EntryToken && Opc != ISD::TokenFactor && 567 Opc != ISD::CopyToReg) 568 return false; 569 } 570 return true; 571 } 572 } 573 return false; 574} 575 576static bool isSimpleFloaterUse(const SUnit *SU) { 577 unsigned NumOps = 0; 578 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 579 I != E; ++I) { 580 if (I->second) continue; 581 if (++NumOps > 1) 582 return false; 583 if (!isFloater(I->first)) 584 return false; 585 } 586 return true; 587} 588 589// Bottom up 590bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 591 unsigned LeftNum = left->NodeNum; 592 unsigned RightNum = right->NodeNum; 593 bool LIsTarget = left->Node->isTargetOpcode(); 594 bool RIsTarget = right->Node->isTargetOpcode(); 595 int LPriority = SPQ->getSethiUllmanNumber(LeftNum); 596 int RPriority = SPQ->getSethiUllmanNumber(RightNum); 597 int LBonus = 0; 598 int RBonus = 0; 599 600 // Schedule floaters (e.g. load from some constant address) and those nodes 601 // with a single predecessor each first. They maintain / reduce register 602 // pressure. 603 if (isFloater(left) || isSimpleFloaterUse(left)) 604 LBonus += 2; 605 if (isFloater(right) || isSimpleFloaterUse(right)) 606 RBonus += 2; 607 608 // Special tie breaker: if two nodes share a operand, the one that use it 609 // as a def&use operand is preferred. 610 if (LIsTarget && RIsTarget) { 611 if (left->isTwoAddress && !right->isTwoAddress) { 612 if (SPQ->isDUOperand(left, right)) 613 LBonus += 2; 614 } 615 if (!left->isTwoAddress && right->isTwoAddress) { 616 if (SPQ->isDUOperand(right, left)) 617 RBonus += 2; 618 } 619 } 620 621 if (LPriority+LBonus < RPriority+RBonus) 622 return true; 623 else if (LPriority+LBonus == RPriority+RBonus) 624 if (left->Height > right->Height) 625 return true; 626 else if (left->Height == right->Height) 627 if (left->Depth < right->Depth) 628 return true; 629 else if (left->Depth == right->Depth) 630 if (left->CycleBound > right->CycleBound) 631 return true; 632 return false; 633} 634 635static inline bool isCopyFromLiveIn(const SUnit *SU) { 636 SDNode *N = SU->Node; 637 return N->getOpcode() == ISD::CopyFromReg && 638 N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag; 639} 640 641// FIXME: This is probably too slow! 642static void isReachable(SUnit *SU, SUnit *TargetSU, 643 std::set<SUnit *> &Visited, bool &Reached) { 644 if (Reached) return; 645 if (SU == TargetSU) { 646 Reached = true; 647 return; 648 } 649 if (!Visited.insert(SU).second) return; 650 651 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; 652 ++I) 653 isReachable(I->first, TargetSU, Visited, Reached); 654} 655 656static bool isReachable(SUnit *SU, SUnit *TargetSU) { 657 std::set<SUnit *> Visited; 658 bool Reached = false; 659 isReachable(SU, TargetSU, Visited, Reached); 660 return Reached; 661} 662 663template<class SF> 664bool BURegReductionPriorityQueue<SF>::canClobber(SUnit *SU, SUnit *Op) { 665 if (SU->isTwoAddress) { 666 unsigned Opc = SU->Node->getTargetOpcode(); 667 unsigned NumRes = ScheduleDAG::CountResults(SU->Node); 668 unsigned NumOps = ScheduleDAG::CountOperands(SU->Node); 669 for (unsigned i = 0; i != NumOps; ++i) { 670 if (TII->getOperandConstraint(Opc, i+NumRes, 671 TargetInstrInfo::TIED_TO) != -1) { 672 SDNode *DU = SU->Node->getOperand(i).Val; 673 if (Op == (*SUnitMap)[DU]) 674 return true; 675 } 676 } 677 } 678 return false; 679} 680 681 682/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses 683/// it as a def&use operand. Add a pseudo control edge from it to the other 684/// node (if it won't create a cycle) so the two-address one will be scheduled 685/// first (lower in the schedule). 686template<class SF> 687void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { 688 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 689 SUnit *SU = (SUnit *)&((*SUnits)[i]); 690 if (!SU->isTwoAddress) 691 continue; 692 693 SDNode *Node = SU->Node; 694 if (!Node->isTargetOpcode()) 695 continue; 696 697 unsigned Opc = Node->getTargetOpcode(); 698 unsigned NumRes = ScheduleDAG::CountResults(Node); 699 unsigned NumOps = ScheduleDAG::CountOperands(Node); 700 for (unsigned j = 0; j != NumOps; ++j) { 701 if (TII->getOperandConstraint(Opc, j+NumRes, 702 TargetInstrInfo::TIED_TO) != -1) { 703 SDNode *DU = SU->Node->getOperand(j).Val; 704 SUnit *DUSU = (*SUnitMap)[DU]; 705 if (!DUSU) continue; 706 for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end(); 707 I != E; ++I) { 708 if (I->second) continue; 709 SUnit *SuccSU = I->first; 710 if (SuccSU != SU && 711 (!canClobber(SuccSU, DUSU) || 712 (!SU->isCommutable && SuccSU->isCommutable))){ 713 if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) { 714 DEBUG(std::cerr << "Adding an edge from SU # " << SU->NodeNum 715 << " to SU #" << SuccSU->NodeNum << "\n"); 716 if (SU->addPred(SuccSU, true)) 717 SU->NumChainPredsLeft++; 718 if (SuccSU->addSucc(SU, true)) 719 SuccSU->NumChainSuccsLeft++; 720 } 721 } 722 } 723 } 724 } 725 } 726} 727 728/// CalcNodePriority - Priority is the Sethi Ullman number. 729/// Smaller number is the higher priority. 730template<class SF> 731int BURegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) { 732 int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 733 if (SethiUllmanNumber != 0) 734 return SethiUllmanNumber; 735 736 unsigned Opc = SU->Node->getOpcode(); 737 if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU)) 738 // CopyFromReg should be close to its def because it restricts allocation 739 // choices. But if it is a livein then perhaps we want it closer to the 740 // uses so it can be coalesced. 741 SethiUllmanNumber = INT_MIN + 10; 742 else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 743 // CopyToReg should be close to its uses to facilitate coalescing and avoid 744 // spilling. 745 SethiUllmanNumber = INT_MAX - 10; 746 else if (SU->NumSuccsLeft == 0) 747 // If SU does not have a use, i.e. it doesn't produce a value that would 748 // be consumed (e.g. store), then it terminates a chain of computation. 749 // Give it a small SethiUllman number so it will be scheduled right before its 750 // predecessors that it doesn't lengthen their live ranges. 751 SethiUllmanNumber = INT_MIN + 10; 752 else if (SU->NumPredsLeft == 0) 753 // If SU does not have a def, schedule it close to its uses because it does 754 // not lengthen any live ranges. 755 SethiUllmanNumber = INT_MAX - 10; 756 else { 757 int Extra = 0; 758 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 759 I != E; ++I) { 760 if (I->second) continue; // ignore chain preds 761 SUnit *PredSU = I->first; 762 int PredSethiUllman = CalcNodePriority(PredSU); 763 if (PredSethiUllman > SethiUllmanNumber) { 764 SethiUllmanNumber = PredSethiUllman; 765 Extra = 0; 766 } else if (PredSethiUllman == SethiUllmanNumber && !I->second) 767 Extra++; 768 } 769 770 SethiUllmanNumber += Extra; 771 } 772 773 return SethiUllmanNumber; 774} 775 776/// CalculatePriorities - Calculate priorities of all scheduling units. 777template<class SF> 778void BURegReductionPriorityQueue<SF>::CalculatePriorities() { 779 SethiUllmanNumbers.assign(SUnits->size(), 0); 780 781 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 782 CalcNodePriority(&(*SUnits)[i]); 783} 784 785static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) { 786 unsigned Sum = 0; 787 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 788 I != E; ++I) { 789 SUnit *SuccSU = I->first; 790 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(), 791 EE = SuccSU->Preds.end(); II != EE; ++II) { 792 SUnit *PredSU = II->first; 793 if (!PredSU->isScheduled) 794 Sum++; 795 } 796 } 797 798 return Sum; 799} 800 801 802// Top down 803bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 804 unsigned LeftNum = left->NodeNum; 805 unsigned RightNum = right->NodeNum; 806 int LPriority = SPQ->getSethiUllmanNumber(LeftNum); 807 int RPriority = SPQ->getSethiUllmanNumber(RightNum); 808 bool LIsTarget = left->Node->isTargetOpcode(); 809 bool RIsTarget = right->Node->isTargetOpcode(); 810 bool LIsFloater = LIsTarget && left->NumPreds == 0; 811 bool RIsFloater = RIsTarget && right->NumPreds == 0; 812 unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0; 813 unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0; 814 815 if (left->NumSuccs == 0 && right->NumSuccs != 0) 816 return false; 817 else if (left->NumSuccs != 0 && right->NumSuccs == 0) 818 return true; 819 820 // Special tie breaker: if two nodes share a operand, the one that use it 821 // as a def&use operand is preferred. 822 if (LIsTarget && RIsTarget) { 823 if (left->isTwoAddress && !right->isTwoAddress) { 824 SDNode *DUNode = left->Node->getOperand(0).Val; 825 if (DUNode->isOperand(right->Node)) 826 RBonus += 2; 827 } 828 if (!left->isTwoAddress && right->isTwoAddress) { 829 SDNode *DUNode = right->Node->getOperand(0).Val; 830 if (DUNode->isOperand(left->Node)) 831 LBonus += 2; 832 } 833 } 834 if (LIsFloater) 835 LBonus -= 2; 836 if (RIsFloater) 837 RBonus -= 2; 838 if (left->NumSuccs == 1) 839 LBonus += 2; 840 if (right->NumSuccs == 1) 841 RBonus += 2; 842 843 if (LPriority+LBonus < RPriority+RBonus) 844 return true; 845 else if (LPriority == RPriority) 846 if (left->Depth < right->Depth) 847 return true; 848 else if (left->Depth == right->Depth) 849 if (left->NumSuccsLeft > right->NumSuccsLeft) 850 return true; 851 else if (left->NumSuccsLeft == right->NumSuccsLeft) 852 if (left->CycleBound > right->CycleBound) 853 return true; 854 return false; 855} 856 857/// CalcNodePriority - Priority is the Sethi Ullman number. 858/// Smaller number is the higher priority. 859template<class SF> 860int TDRegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) { 861 int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 862 if (SethiUllmanNumber != 0) 863 return SethiUllmanNumber; 864 865 unsigned Opc = SU->Node->getOpcode(); 866 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 867 SethiUllmanNumber = INT_MAX - 10; 868 else if (SU->NumSuccsLeft == 0) 869 // If SU does not have a use, i.e. it doesn't produce a value that would 870 // be consumed (e.g. store), then it terminates a chain of computation. 871 // Give it a small SethiUllman number so it will be scheduled right before its 872 // predecessors that it doesn't lengthen their live ranges. 873 SethiUllmanNumber = INT_MIN + 10; 874 else if (SU->NumPredsLeft == 0 && 875 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) 876 SethiUllmanNumber = 1; 877 else { 878 int Extra = 0; 879 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 880 I != E; ++I) { 881 if (I->second) continue; // ignore chain preds 882 SUnit *PredSU = I->first; 883 int PredSethiUllman = CalcNodePriority(PredSU); 884 if (PredSethiUllman > SethiUllmanNumber) { 885 SethiUllmanNumber = PredSethiUllman; 886 Extra = 0; 887 } else if (PredSethiUllman == SethiUllmanNumber && !I->second) 888 Extra++; 889 } 890 891 SethiUllmanNumber += Extra; 892 } 893 894 return SethiUllmanNumber; 895} 896 897/// CalculatePriorities - Calculate priorities of all scheduling units. 898template<class SF> 899void TDRegReductionPriorityQueue<SF>::CalculatePriorities() { 900 SethiUllmanNumbers.assign(SUnits->size(), 0); 901 902 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 903 CalcNodePriority(&(*SUnits)[i]); 904} 905 906//===----------------------------------------------------------------------===// 907// Public Constructor Functions 908//===----------------------------------------------------------------------===// 909 910llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, 911 SelectionDAG *DAG, 912 MachineBasicBlock *BB) { 913 const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo(); 914 return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, 915 new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII)); 916} 917 918llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, 919 SelectionDAG *DAG, 920 MachineBasicBlock *BB) { 921 return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false, 922 new TDRegReductionPriorityQueue<td_ls_rr_sort>()); 923} 924 925