LLVM API Documentation
00001 //===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by Evan Cheng and is distributed under the 00006 // University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements bottom-up and top-down register pressure reduction list 00011 // schedulers, using standard algorithms. The basic approach uses a priority 00012 // queue of available nodes to schedule. One at a time, nodes are taken from 00013 // the priority queue (thus in priority order), checked for legality to 00014 // schedule, and emitted if legal. 00015 // 00016 //===----------------------------------------------------------------------===// 00017 00018 #define DEBUG_TYPE "sched" 00019 #include "llvm/CodeGen/ScheduleDAG.h" 00020 #include "llvm/CodeGen/SSARegMap.h" 00021 #include "llvm/Target/MRegisterInfo.h" 00022 #include "llvm/Target/TargetData.h" 00023 #include "llvm/Target/TargetMachine.h" 00024 #include "llvm/Target/TargetInstrInfo.h" 00025 #include "llvm/Support/Debug.h" 00026 #include "llvm/Support/Visibility.h" 00027 #include "llvm/ADT/Statistic.h" 00028 #include <climits> 00029 #include <iostream> 00030 #include <queue> 00031 #include "llvm/Support/CommandLine.h" 00032 using namespace llvm; 00033 00034 namespace { 00035 //===----------------------------------------------------------------------===// 00036 /// ScheduleDAGRRList - The actual register reduction list scheduler 00037 /// implementation. This supports both top-down and bottom-up scheduling. 00038 /// 00039 00040 class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG { 00041 private: 00042 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if 00043 /// it is top-down. 00044 bool isBottomUp; 00045 00046 /// AvailableQueue - The priority queue to use for the available SUnits. 00047 /// 00048 SchedulingPriorityQueue *AvailableQueue; 00049 00050 public: 00051 ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb, 00052 const TargetMachine &tm, bool isbottomup, 00053 SchedulingPriorityQueue *availqueue) 00054 : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), 00055 AvailableQueue(availqueue) { 00056 } 00057 00058 ~ScheduleDAGRRList() { 00059 delete AvailableQueue; 00060 } 00061 00062 void Schedule(); 00063 00064 private: 00065 void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle); 00066 void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle); 00067 void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle); 00068 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 00069 void ListScheduleTopDown(); 00070 void ListScheduleBottomUp(); 00071 void CommuteNodesToReducePressure(); 00072 }; 00073 } // end anonymous namespace 00074 00075 00076 /// Schedule - Schedule the DAG using list scheduling. 00077 void ScheduleDAGRRList::Schedule() { 00078 DEBUG(std::cerr << "********** List Scheduling **********\n"); 00079 00080 // Build scheduling units. 00081 BuildSchedUnits(); 00082 00083 CalculateDepths(); 00084 CalculateHeights(); 00085 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 00086 SUnits[su].dumpAll(&DAG)); 00087 00088 AvailableQueue->initNodes(SUnits); 00089 00090 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. 00091 if (isBottomUp) 00092 ListScheduleBottomUp(); 00093 else 00094 ListScheduleTopDown(); 00095 00096 AvailableQueue->releaseState(); 00097 00098 CommuteNodesToReducePressure(); 00099 00100 DEBUG(std::cerr << "*** Final schedule ***\n"); 00101 DEBUG(dumpSchedule()); 00102 DEBUG(std::cerr << "\n"); 00103 00104 // Emit in scheduled order 00105 EmitSchedule(); 00106 } 00107 00108 /// CommuteNodesToReducePressure - Is a node is two-address and commutable, and 00109 /// it is not the last use of its first operand, add it to the CommuteSet if 00110 /// possible. It will be commuted when it is translated to a MI. 00111 void ScheduleDAGRRList::CommuteNodesToReducePressure() { 00112 std::set<SUnit *> OperandSeen; 00113 for (unsigned i = Sequence.size()-1; i != 0; --i) { // Ignore first node. 00114 SUnit *SU = Sequence[i]; 00115 if (!SU) continue; 00116 if (SU->isTwoAddress && SU->isCommutable) { 00117 SDNode *OpN = SU->Node->getOperand(0).Val; 00118 SUnit *OpSU = SUnitMap[OpN]; 00119 if (OpSU && OperandSeen.count(OpSU) == 1) { 00120 // Ok, so SU is not the last use of OpSU, but SU is two-address so 00121 // it will clobber OpSU. Try to commute it if possible. 00122 bool DoCommute = true; 00123 for (unsigned j = 1, e = SU->Node->getNumOperands(); j != e; ++j) { 00124 OpN = SU->Node->getOperand(j).Val; 00125 OpSU = SUnitMap[OpN]; 00126 if (OpSU && OperandSeen.count(OpSU) == 1) { 00127 DoCommute = false; 00128 break; 00129 } 00130 } 00131 if (DoCommute) 00132 CommuteSet.insert(SU->Node); 00133 } 00134 } 00135 00136 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(), 00137 E = SU->Preds.end(); I != E; ++I) { 00138 if (!I->second) 00139 OperandSeen.insert(I->first); 00140 } 00141 } 00142 } 00143 00144 //===----------------------------------------------------------------------===// 00145 // Bottom-Up Scheduling 00146 //===----------------------------------------------------------------------===// 00147 00148 static const TargetRegisterClass *getRegClass(SUnit *SU, 00149 const TargetInstrInfo *TII, 00150 const MRegisterInfo *MRI, 00151 SSARegMap *RegMap) { 00152 if (SU->Node->isTargetOpcode()) { 00153 unsigned Opc = SU->Node->getTargetOpcode(); 00154 const TargetInstrDescriptor &II = TII->get(Opc); 00155 return MRI->getRegClass(II.OpInfo->RegClass); 00156 } else { 00157 assert(SU->Node->getOpcode() == ISD::CopyFromReg); 00158 unsigned SrcReg = cast<RegisterSDNode>(SU->Node->getOperand(1))->getReg(); 00159 if (MRegisterInfo::isVirtualRegister(SrcReg)) 00160 return RegMap->getRegClass(SrcReg); 00161 else { 00162 for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(), 00163 E = MRI->regclass_end(); I != E; ++I) 00164 if ((*I)->hasType(SU->Node->getValueType(0)) && 00165 (*I)->contains(SrcReg)) 00166 return *I; 00167 assert(false && "Couldn't find register class for reg copy!"); 00168 } 00169 return NULL; 00170 } 00171 } 00172 00173 static unsigned getNumResults(SUnit *SU) { 00174 unsigned NumResults = 0; 00175 for (unsigned i = 0, e = SU->Node->getNumValues(); i != e; ++i) { 00176 MVT::ValueType VT = SU->Node->getValueType(i); 00177 if (VT != MVT::Other && VT != MVT::Flag) 00178 NumResults++; 00179 } 00180 return NumResults; 00181 } 00182 00183 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 00184 /// the Available queue is the count reaches zero. Also update its cycle bound. 00185 void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain, 00186 unsigned CurCycle) { 00187 // FIXME: the distance between two nodes is not always == the predecessor's 00188 // latency. For example, the reader can very well read the register written 00189 // by the predecessor later than the issue cycle. It also depends on the 00190 // interrupt model (drain vs. freeze). 00191 PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency); 00192 00193 if (!isChain) 00194 PredSU->NumSuccsLeft--; 00195 else 00196 PredSU->NumChainSuccsLeft--; 00197 00198 #ifndef NDEBUG 00199 if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) { 00200 std::cerr << "*** List scheduling failed! ***\n"; 00201 PredSU->dump(&DAG); 00202 std::cerr << " has been released too many times!\n"; 00203 assert(0); 00204 } 00205 #endif 00206 00207 if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) { 00208 // EntryToken has to go last! Special case it here. 00209 if (PredSU->Node->getOpcode() != ISD::EntryToken) { 00210 PredSU->isAvailable = true; 00211 AvailableQueue->push(PredSU); 00212 } 00213 } 00214 } 00215 00216 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 00217 /// count of its predecessors. If a predecessor pending count is zero, add it to 00218 /// the Available queue. 00219 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 00220 DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: "); 00221 DEBUG(SU->dump(&DAG)); 00222 SU->Cycle = CurCycle; 00223 00224 AvailableQueue->ScheduledNode(SU); 00225 Sequence.push_back(SU); 00226 00227 // Bottom up: release predecessors 00228 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(), 00229 E = SU->Preds.end(); I != E; ++I) 00230 ReleasePred(I->first, I->second, CurCycle); 00231 SU->isScheduled = true; 00232 } 00233 00234 /// isReady - True if node's lower cycle bound is less or equal to the current 00235 /// scheduling cycle. Always true if all nodes have uniform latency 1. 00236 static inline bool isReady(SUnit *SU, unsigned CurCycle) { 00237 return SU->CycleBound <= CurCycle; 00238 } 00239 00240 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 00241 /// schedulers. 00242 void ScheduleDAGRRList::ListScheduleBottomUp() { 00243 unsigned CurCycle = 0; 00244 // Add root to Available queue. 00245 AvailableQueue->push(SUnitMap[DAG.getRoot().Val]); 00246 00247 // While Available queue is not empty, grab the node with the highest 00248 // priority. If it is not ready put it back. Schedule the node. 00249 std::vector<SUnit*> NotReady; 00250 SUnit *CurNode = NULL; 00251 while (!AvailableQueue->empty()) { 00252 SUnit *CurNode = AvailableQueue->pop(); 00253 while (CurNode && !isReady(CurNode, CurCycle)) { 00254 NotReady.push_back(CurNode); 00255 CurNode = AvailableQueue->pop(); 00256 } 00257 00258 // Add the nodes that aren't ready back onto the available list. 00259 AvailableQueue->push_all(NotReady); 00260 NotReady.clear(); 00261 00262 if (CurNode != NULL) 00263 ScheduleNodeBottomUp(CurNode, CurCycle); 00264 CurCycle++; 00265 } 00266 00267 // Add entry node last 00268 if (DAG.getEntryNode().Val != DAG.getRoot().Val) { 00269 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val]; 00270 Sequence.push_back(Entry); 00271 } 00272 00273 // Reverse the order if it is bottom up. 00274 std::reverse(Sequence.begin(), Sequence.end()); 00275 00276 00277 #ifndef NDEBUG 00278 // Verify that all SUnits were scheduled. 00279 bool AnyNotSched = false; 00280 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 00281 if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) { 00282 if (!AnyNotSched) 00283 std::cerr << "*** List scheduling failed! ***\n"; 00284 SUnits[i].dump(&DAG); 00285 std::cerr << "has not been scheduled!\n"; 00286 AnyNotSched = true; 00287 } 00288 } 00289 assert(!AnyNotSched); 00290 #endif 00291 } 00292 00293 //===----------------------------------------------------------------------===// 00294 // Top-Down Scheduling 00295 //===----------------------------------------------------------------------===// 00296 00297 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 00298 /// the PendingQueue if the count reaches zero. 00299 void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain, 00300 unsigned CurCycle) { 00301 // FIXME: the distance between two nodes is not always == the predecessor's 00302 // latency. For example, the reader can very well read the register written 00303 // by the predecessor later than the issue cycle. It also depends on the 00304 // interrupt model (drain vs. freeze). 00305 SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency); 00306 00307 if (!isChain) 00308 SuccSU->NumPredsLeft--; 00309 else 00310 SuccSU->NumChainPredsLeft--; 00311 00312 #ifndef NDEBUG 00313 if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) { 00314 std::cerr << "*** List scheduling failed! ***\n"; 00315 SuccSU->dump(&DAG); 00316 std::cerr << " has been released too many times!\n"; 00317 assert(0); 00318 } 00319 #endif 00320 00321 if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) { 00322 SuccSU->isAvailable = true; 00323 AvailableQueue->push(SuccSU); 00324 } 00325 } 00326 00327 00328 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 00329 /// count of its successors. If a successor pending count is zero, add it to 00330 /// the Available queue. 00331 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 00332 DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: "); 00333 DEBUG(SU->dump(&DAG)); 00334 SU->Cycle = CurCycle; 00335 00336 AvailableQueue->ScheduledNode(SU); 00337 Sequence.push_back(SU); 00338 00339 // Top down: release successors 00340 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(), 00341 E = SU->Succs.end(); I != E; ++I) 00342 ReleaseSucc(I->first, I->second, CurCycle); 00343 SU->isScheduled = true; 00344 } 00345 00346 void ScheduleDAGRRList::ListScheduleTopDown() { 00347 unsigned CurCycle = 0; 00348 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val]; 00349 00350 // All leaves to Available queue. 00351 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 00352 // It is available if it has no predecessors. 00353 if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) { 00354 AvailableQueue->push(&SUnits[i]); 00355 SUnits[i].isAvailable = true; 00356 } 00357 } 00358 00359 // Emit the entry node first. 00360 ScheduleNodeTopDown(Entry, CurCycle); 00361 CurCycle++; 00362 00363 // While Available queue is not empty, grab the node with the highest 00364 // priority. If it is not ready put it back. Schedule the node. 00365 std::vector<SUnit*> NotReady; 00366 SUnit *CurNode = NULL; 00367 while (!AvailableQueue->empty()) { 00368 SUnit *CurNode = AvailableQueue->pop(); 00369 while (CurNode && !isReady(CurNode, CurCycle)) { 00370 NotReady.push_back(CurNode); 00371 CurNode = AvailableQueue->pop(); 00372 } 00373 00374 // Add the nodes that aren't ready back onto the available list. 00375 AvailableQueue->push_all(NotReady); 00376 NotReady.clear(); 00377 00378 if (CurNode != NULL) 00379 ScheduleNodeTopDown(CurNode, CurCycle); 00380 CurCycle++; 00381 } 00382 00383 00384 #ifndef NDEBUG 00385 // Verify that all SUnits were scheduled. 00386 bool AnyNotSched = false; 00387 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 00388 if (!SUnits[i].isScheduled) { 00389 if (!AnyNotSched) 00390 std::cerr << "*** List scheduling failed! ***\n"; 00391 SUnits[i].dump(&DAG); 00392 std::cerr << "has not been scheduled!\n"; 00393 AnyNotSched = true; 00394 } 00395 } 00396 assert(!AnyNotSched); 00397 #endif 00398 } 00399 00400 00401 00402 //===----------------------------------------------------------------------===// 00403 // RegReductionPriorityQueue Implementation 00404 //===----------------------------------------------------------------------===// 00405 // 00406 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers 00407 // to reduce register pressure. 00408 // 00409 namespace { 00410 template<class SF> 00411 class RegReductionPriorityQueue; 00412 00413 /// Sorting functions for the Available queue. 00414 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 00415 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; 00416 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} 00417 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 00418 00419 bool operator()(const SUnit* left, const SUnit* right) const; 00420 }; 00421 00422 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 00423 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; 00424 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} 00425 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 00426 00427 bool operator()(const SUnit* left, const SUnit* right) const; 00428 }; 00429 } // end anonymous namespace 00430 00431 namespace { 00432 template<class SF> 00433 class VISIBILITY_HIDDEN RegReductionPriorityQueue 00434 : public SchedulingPriorityQueue { 00435 std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue; 00436 00437 public: 00438 RegReductionPriorityQueue() : 00439 Queue(SF(this)) {} 00440 00441 virtual void initNodes(const std::vector<SUnit> &sunits) {} 00442 virtual void releaseState() {} 00443 00444 virtual int getSethiUllmanNumber(unsigned NodeNum) const { 00445 return 0; 00446 } 00447 00448 bool empty() const { return Queue.empty(); } 00449 00450 void push(SUnit *U) { 00451 Queue.push(U); 00452 } 00453 void push_all(const std::vector<SUnit *> &Nodes) { 00454 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 00455 Queue.push(Nodes[i]); 00456 } 00457 00458 SUnit *pop() { 00459 if (empty()) return NULL; 00460 SUnit *V = Queue.top(); 00461 Queue.pop(); 00462 return V; 00463 } 00464 }; 00465 00466 template<class SF> 00467 class VISIBILITY_HIDDEN BURegReductionPriorityQueue 00468 : public RegReductionPriorityQueue<SF> { 00469 // SUnits - The SUnits for the current graph. 00470 const std::vector<SUnit> *SUnits; 00471 00472 // SethiUllmanNumbers - The SethiUllman number for each node. 00473 std::vector<int> SethiUllmanNumbers; 00474 00475 public: 00476 BURegReductionPriorityQueue() {} 00477 00478 void initNodes(const std::vector<SUnit> &sunits) { 00479 SUnits = &sunits; 00480 // Add pseudo dependency edges for two-address nodes. 00481 AddPseudoTwoAddrDeps(); 00482 // Calculate node priorities. 00483 CalculatePriorities(); 00484 } 00485 00486 void releaseState() { 00487 SUnits = 0; 00488 SethiUllmanNumbers.clear(); 00489 } 00490 00491 int getSethiUllmanNumber(unsigned NodeNum) const { 00492 assert(NodeNum < SethiUllmanNumbers.size()); 00493 return SethiUllmanNumbers[NodeNum]; 00494 } 00495 00496 private: 00497 void AddPseudoTwoAddrDeps(); 00498 void CalculatePriorities(); 00499 int CalcNodePriority(const SUnit *SU); 00500 }; 00501 00502 00503 template<class SF> 00504 class TDRegReductionPriorityQueue : public RegReductionPriorityQueue<SF> { 00505 // SUnits - The SUnits for the current graph. 00506 const std::vector<SUnit> *SUnits; 00507 00508 // SethiUllmanNumbers - The SethiUllman number for each node. 00509 std::vector<int> SethiUllmanNumbers; 00510 00511 public: 00512 TDRegReductionPriorityQueue() {} 00513 00514 void initNodes(const std::vector<SUnit> &sunits) { 00515 SUnits = &sunits; 00516 // Calculate node priorities. 00517 CalculatePriorities(); 00518 } 00519 00520 void releaseState() { 00521 SUnits = 0; 00522 SethiUllmanNumbers.clear(); 00523 } 00524 00525 int getSethiUllmanNumber(unsigned NodeNum) const { 00526 assert(NodeNum < SethiUllmanNumbers.size()); 00527 return SethiUllmanNumbers[NodeNum]; 00528 } 00529 00530 private: 00531 void CalculatePriorities(); 00532 int CalcNodePriority(const SUnit *SU); 00533 }; 00534 } 00535 00536 static bool isFloater(const SUnit *SU) { 00537 if (SU->Node->isTargetOpcode()) { 00538 if (SU->NumPreds == 0) 00539 return true; 00540 if (SU->NumPreds == 1) { 00541 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(), 00542 E = SU->Preds.end(); I != E; ++I) { 00543 if (I->second) continue; 00544 00545 SUnit *PredSU = I->first; 00546 unsigned Opc = PredSU->Node->getOpcode(); 00547 if (Opc != ISD::EntryToken && Opc != ISD::TokenFactor && 00548 Opc != ISD::CopyFromReg && Opc != ISD::CopyToReg) 00549 return false; 00550 } 00551 return true; 00552 } 00553 } 00554 return false; 00555 } 00556 00557 static bool isSimpleFloaterUse(const SUnit *SU) { 00558 unsigned NumOps = 0; 00559 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(), 00560 E = SU->Preds.end(); I != E; ++I) { 00561 if (I->second) continue; 00562 if (++NumOps > 1) 00563 return false; 00564 if (!isFloater(I->first)) 00565 return false; 00566 } 00567 return true; 00568 } 00569 00570 // Bottom up 00571 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 00572 unsigned LeftNum = left->NodeNum; 00573 unsigned RightNum = right->NodeNum; 00574 bool LIsTarget = left->Node->isTargetOpcode(); 00575 bool RIsTarget = right->Node->isTargetOpcode(); 00576 int LPriority = SPQ->getSethiUllmanNumber(LeftNum); 00577 int RPriority = SPQ->getSethiUllmanNumber(RightNum); 00578 int LBonus = 0; 00579 int RBonus = 0; 00580 00581 // Schedule floaters (e.g. load from some constant address) and those nodes 00582 // with a single predecessor each first. They maintain / reduce register 00583 // pressure. 00584 if (isFloater(left) || isSimpleFloaterUse(left)) 00585 LBonus += 2; 00586 if (isFloater(right) || isSimpleFloaterUse(right)) 00587 RBonus += 2; 00588 00589 // Special tie breaker: if two nodes share a operand, the one that use it 00590 // as a def&use operand is preferred. 00591 if (LIsTarget && RIsTarget) { 00592 if (left->isTwoAddress && !right->isTwoAddress) { 00593 SDNode *DUNode = left->Node->getOperand(0).Val; 00594 if (DUNode->isOperand(right->Node)) 00595 LBonus += 2; 00596 } 00597 if (!left->isTwoAddress && right->isTwoAddress) { 00598 SDNode *DUNode = right->Node->getOperand(0).Val; 00599 if (DUNode->isOperand(left->Node)) 00600 RBonus += 2; 00601 } 00602 } 00603 00604 if (LPriority+LBonus < RPriority+RBonus) 00605 return true; 00606 else if (LPriority+LBonus == RPriority+RBonus) 00607 if (left->Height > right->Height) 00608 return true; 00609 else if (left->Height == right->Height) 00610 if (left->Depth < right->Depth) 00611 return true; 00612 else if (left->Depth == right->Depth) 00613 if (left->CycleBound > right->CycleBound) 00614 return true; 00615 return false; 00616 } 00617 00618 static inline bool isCopyFromLiveIn(const SUnit *SU) { 00619 SDNode *N = SU->Node; 00620 return N->getOpcode() == ISD::CopyFromReg && 00621 N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag; 00622 } 00623 00624 // FIXME: This is probably too slow! 00625 static void isReachable(SUnit *SU, SUnit *TargetSU, 00626 std::set<SUnit *> &Visited, bool &Reached) { 00627 if (Reached) return; 00628 if (SU == TargetSU) { 00629 Reached = true; 00630 return; 00631 } 00632 if (!Visited.insert(SU).second) return; 00633 00634 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(), 00635 E = SU->Preds.end(); I != E; ++I) 00636 isReachable(I->first, TargetSU, Visited, Reached); 00637 } 00638 00639 static bool isReachable(SUnit *SU, SUnit *TargetSU) { 00640 std::set<SUnit *> Visited; 00641 bool Reached = false; 00642 isReachable(SU, TargetSU, Visited, Reached); 00643 return Reached; 00644 } 00645 00646 static SUnit *getDefUsePredecessor(SUnit *SU) { 00647 SDNode *DU = SU->Node->getOperand(0).Val; 00648 for (std::set<std::pair<SUnit*, bool> >::iterator 00649 I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) { 00650 if (I->second) continue; // ignore chain preds 00651 SUnit *PredSU = I->first; 00652 if (PredSU->Node == DU) 00653 return PredSU; 00654 } 00655 00656 // Must be flagged. 00657 return NULL; 00658 } 00659 00660 static bool canClobber(SUnit *SU, SUnit *Op) { 00661 if (SU->isTwoAddress) 00662 return Op == getDefUsePredecessor(SU); 00663 return false; 00664 } 00665 00666 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses 00667 /// it as a def&use operand. Add a pseudo control edge from it to the other 00668 /// node (if it won't create a cycle) so the two-address one will be scheduled 00669 /// first (lower in the schedule). 00670 template<class SF> 00671 void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { 00672 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 00673 SUnit *SU = (SUnit *)&((*SUnits)[i]); 00674 SDNode *Node = SU->Node; 00675 if (!Node->isTargetOpcode()) 00676 continue; 00677 00678 if (SU->isTwoAddress) { 00679 SUnit *DUSU = getDefUsePredecessor(SU); 00680 if (!DUSU) continue; 00681 00682 for (std::set<std::pair<SUnit*, bool> >::iterator I = DUSU->Succs.begin(), 00683 E = DUSU->Succs.end(); I != E; ++I) { 00684 if (I->second) continue; 00685 SUnit *SuccSU = I->first; 00686 if (SuccSU != SU && 00687 (!canClobber(SuccSU, DUSU) || 00688 (!SU->isCommutable && SuccSU->isCommutable))){ 00689 if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) { 00690 DEBUG(std::cerr << "Adding an edge from SU # " << SU->NodeNum 00691 << " to SU #" << SuccSU->NodeNum << "\n"); 00692 if (SU->Preds.insert(std::make_pair(SuccSU, true)).second) 00693 SU->NumChainPredsLeft++; 00694 if (SuccSU->Succs.insert(std::make_pair(SU, true)).second) 00695 SuccSU->NumChainSuccsLeft++; 00696 } 00697 } 00698 } 00699 } 00700 } 00701 } 00702 00703 /// CalcNodePriority - Priority is the Sethi Ullman number. 00704 /// Smaller number is the higher priority. 00705 template<class SF> 00706 int BURegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) { 00707 int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 00708 if (SethiUllmanNumber != 0) 00709 return SethiUllmanNumber; 00710 00711 unsigned Opc = SU->Node->getOpcode(); 00712 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 00713 SethiUllmanNumber = INT_MAX - 10; 00714 else if (SU->NumSuccsLeft == 0) 00715 // If SU does not have a use, i.e. it doesn't produce a value that would 00716 // be consumed (e.g. store), then it terminates a chain of computation. 00717 // Give it a small SethiUllman number so it will be scheduled right before its 00718 // predecessors that it doesn't lengthen their live ranges. 00719 SethiUllmanNumber = INT_MIN + 10; 00720 // FIXME: remove this else if? It seems to reduce register spills but often 00721 // ends up increasing runtime. Need to investigate. 00722 else if (SU->NumPredsLeft == 0 && 00723 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) 00724 SethiUllmanNumber = INT_MAX - 10; 00725 else { 00726 int Extra = 0; 00727 for (std::set<std::pair<SUnit*, bool> >::const_iterator 00728 I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) { 00729 if (I->second) continue; // ignore chain preds 00730 SUnit *PredSU = I->first; 00731 int PredSethiUllman = CalcNodePriority(PredSU); 00732 if (PredSethiUllman > SethiUllmanNumber) { 00733 SethiUllmanNumber = PredSethiUllman; 00734 Extra = 0; 00735 } else if (PredSethiUllman == SethiUllmanNumber && !I->second) 00736 Extra++; 00737 } 00738 00739 SethiUllmanNumber += Extra; 00740 } 00741 00742 return SethiUllmanNumber; 00743 } 00744 00745 /// CalculatePriorities - Calculate priorities of all scheduling units. 00746 template<class SF> 00747 void BURegReductionPriorityQueue<SF>::CalculatePriorities() { 00748 SethiUllmanNumbers.assign(SUnits->size(), 0); 00749 00750 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 00751 CalcNodePriority(&(*SUnits)[i]); 00752 } 00753 00754 static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) { 00755 unsigned Sum = 0; 00756 for (std::set<std::pair<SUnit*, bool> >::const_iterator 00757 I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) { 00758 SUnit *SuccSU = I->first; 00759 for (std::set<std::pair<SUnit*, bool> >::const_iterator 00760 II = SuccSU->Preds.begin(), EE = SuccSU->Preds.end(); II != EE; ++II) { 00761 SUnit *PredSU = II->first; 00762 if (!PredSU->isScheduled) 00763 Sum++; 00764 } 00765 } 00766 00767 return Sum; 00768 } 00769 00770 00771 // Top down 00772 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 00773 unsigned LeftNum = left->NodeNum; 00774 unsigned RightNum = right->NodeNum; 00775 int LPriority = SPQ->getSethiUllmanNumber(LeftNum); 00776 int RPriority = SPQ->getSethiUllmanNumber(RightNum); 00777 bool LIsTarget = left->Node->isTargetOpcode(); 00778 bool RIsTarget = right->Node->isTargetOpcode(); 00779 bool LIsFloater = LIsTarget && left->NumPreds == 0; 00780 bool RIsFloater = RIsTarget && right->NumPreds == 0; 00781 unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0; 00782 unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0; 00783 00784 if (left->NumSuccs == 0 && right->NumSuccs != 0) 00785 return false; 00786 else if (left->NumSuccs != 0 && right->NumSuccs == 0) 00787 return true; 00788 00789 // Special tie breaker: if two nodes share a operand, the one that use it 00790 // as a def&use operand is preferred. 00791 if (LIsTarget && RIsTarget) { 00792 if (left->isTwoAddress && !right->isTwoAddress) { 00793 SDNode *DUNode = left->Node->getOperand(0).Val; 00794 if (DUNode->isOperand(right->Node)) 00795 RBonus += 2; 00796 } 00797 if (!left->isTwoAddress && right->isTwoAddress) { 00798 SDNode *DUNode = right->Node->getOperand(0).Val; 00799 if (DUNode->isOperand(left->Node)) 00800 LBonus += 2; 00801 } 00802 } 00803 if (LIsFloater) 00804 LBonus -= 2; 00805 if (RIsFloater) 00806 RBonus -= 2; 00807 if (left->NumSuccs == 1) 00808 LBonus += 2; 00809 if (right->NumSuccs == 1) 00810 RBonus += 2; 00811 00812 if (LPriority+LBonus < RPriority+RBonus) 00813 return true; 00814 else if (LPriority == RPriority) 00815 if (left->Depth < right->Depth) 00816 return true; 00817 else if (left->Depth == right->Depth) 00818 if (left->NumSuccsLeft > right->NumSuccsLeft) 00819 return true; 00820 else if (left->NumSuccsLeft == right->NumSuccsLeft) 00821 if (left->CycleBound > right->CycleBound) 00822 return true; 00823 return false; 00824 } 00825 00826 /// CalcNodePriority - Priority is the Sethi Ullman number. 00827 /// Smaller number is the higher priority. 00828 template<class SF> 00829 int TDRegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) { 00830 int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 00831 if (SethiUllmanNumber != 0) 00832 return SethiUllmanNumber; 00833 00834 unsigned Opc = SU->Node->getOpcode(); 00835 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 00836 SethiUllmanNumber = INT_MAX - 10; 00837 else if (SU->NumSuccsLeft == 0) 00838 // If SU does not have a use, i.e. it doesn't produce a value that would 00839 // be consumed (e.g. store), then it terminates a chain of computation. 00840 // Give it a small SethiUllman number so it will be scheduled right before its 00841 // predecessors that it doesn't lengthen their live ranges. 00842 SethiUllmanNumber = INT_MIN + 10; 00843 else if (SU->NumPredsLeft == 0 && 00844 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) 00845 SethiUllmanNumber = 1; 00846 else { 00847 int Extra = 0; 00848 for (std::set<std::pair<SUnit*, bool> >::const_iterator 00849 I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) { 00850 if (I->second) continue; // ignore chain preds 00851 SUnit *PredSU = I->first; 00852 int PredSethiUllman = CalcNodePriority(PredSU); 00853 if (PredSethiUllman > SethiUllmanNumber) { 00854 SethiUllmanNumber = PredSethiUllman; 00855 Extra = 0; 00856 } else if (PredSethiUllman == SethiUllmanNumber && !I->second) 00857 Extra++; 00858 } 00859 00860 SethiUllmanNumber += Extra; 00861 } 00862 00863 return SethiUllmanNumber; 00864 } 00865 00866 /// CalculatePriorities - Calculate priorities of all scheduling units. 00867 template<class SF> 00868 void TDRegReductionPriorityQueue<SF>::CalculatePriorities() { 00869 SethiUllmanNumbers.assign(SUnits->size(), 0); 00870 00871 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 00872 CalcNodePriority(&(*SUnits)[i]); 00873 } 00874 00875 //===----------------------------------------------------------------------===// 00876 // Public Constructor Functions 00877 //===----------------------------------------------------------------------===// 00878 00879 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG, 00880 MachineBasicBlock *BB) { 00881 return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), true, 00882 new BURegReductionPriorityQueue<bu_ls_rr_sort>()); 00883 } 00884 00885 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAG &DAG, 00886 MachineBasicBlock *BB) { 00887 return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), false, 00888 new TDRegReductionPriorityQueue<td_ls_rr_sort>()); 00889 } 00890