LLVM API Documentation
00001 //===----- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler --===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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 "pre-RA-sched" 00019 #include "ScheduleDAGSDNodes.h" 00020 #include "llvm/CodeGen/SchedulerRegistry.h" 00021 #include "llvm/CodeGen/SelectionDAGISel.h" 00022 #include "llvm/Target/TargetRegisterInfo.h" 00023 #include "llvm/Target/TargetData.h" 00024 #include "llvm/Target/TargetMachine.h" 00025 #include "llvm/Target/TargetInstrInfo.h" 00026 #include "llvm/Support/Debug.h" 00027 #include "llvm/Support/Compiler.h" 00028 #include "llvm/Support/ErrorHandling.h" 00029 #include "llvm/ADT/PriorityQueue.h" 00030 #include "llvm/ADT/SmallSet.h" 00031 #include "llvm/ADT/Statistic.h" 00032 #include "llvm/ADT/STLExtras.h" 00033 #include <climits> 00034 using namespace llvm; 00035 00036 STATISTIC(NumBacktracks, "Number of times scheduler backtracked"); 00037 STATISTIC(NumUnfolds, "Number of nodes unfolded"); 00038 STATISTIC(NumDups, "Number of duplicated nodes"); 00039 STATISTIC(NumPRCopies, "Number of physical register copies"); 00040 00041 static RegisterScheduler 00042 burrListDAGScheduler("list-burr", 00043 "Bottom-up register reduction list scheduling", 00044 createBURRListDAGScheduler); 00045 static RegisterScheduler 00046 tdrListrDAGScheduler("list-tdrr", 00047 "Top-down register reduction list scheduling", 00048 createTDRRListDAGScheduler); 00049 00050 namespace { 00051 //===----------------------------------------------------------------------===// 00052 /// ScheduleDAGRRList - The actual register reduction list scheduler 00053 /// implementation. This supports both top-down and bottom-up scheduling. 00054 /// 00055 class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes { 00056 private: 00057 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if 00058 /// it is top-down. 00059 bool isBottomUp; 00060 00061 /// AvailableQueue - The priority queue to use for the available SUnits. 00062 SchedulingPriorityQueue *AvailableQueue; 00063 00064 /// LiveRegDefs - A set of physical registers and their definition 00065 /// that are "live". These nodes must be scheduled before any other nodes that 00066 /// modifies the registers can be scheduled. 00067 unsigned NumLiveRegs; 00068 std::vector<SUnit*> LiveRegDefs; 00069 std::vector<unsigned> LiveRegCycles; 00070 00071 /// Topo - A topological ordering for SUnits which permits fast IsReachable 00072 /// and similar queries. 00073 ScheduleDAGTopologicalSort Topo; 00074 00075 public: 00076 ScheduleDAGRRList(MachineFunction &mf, 00077 bool isbottomup, 00078 SchedulingPriorityQueue *availqueue) 00079 : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup), 00080 AvailableQueue(availqueue), Topo(SUnits) { 00081 } 00082 00083 ~ScheduleDAGRRList() { 00084 delete AvailableQueue; 00085 } 00086 00087 void Schedule(); 00088 00089 /// IsReachable - Checks if SU is reachable from TargetSU. 00090 bool IsReachable(const SUnit *SU, const SUnit *TargetSU) { 00091 return Topo.IsReachable(SU, TargetSU); 00092 } 00093 00094 /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 00095 /// create a cycle. 00096 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 00097 return Topo.WillCreateCycle(SU, TargetSU); 00098 } 00099 00100 /// AddPred - adds a predecessor edge to SUnit SU. 00101 /// This returns true if this is a new predecessor. 00102 /// Updates the topological ordering if required. 00103 void AddPred(SUnit *SU, const SDep &D) { 00104 Topo.AddPred(SU, D.getSUnit()); 00105 SU->addPred(D); 00106 } 00107 00108 /// RemovePred - removes a predecessor edge from SUnit SU. 00109 /// This returns true if an edge was removed. 00110 /// Updates the topological ordering if required. 00111 void RemovePred(SUnit *SU, const SDep &D) { 00112 Topo.RemovePred(SU, D.getSUnit()); 00113 SU->removePred(D); 00114 } 00115 00116 private: 00117 void ReleasePred(SUnit *SU, const SDep *PredEdge); 00118 void ReleasePredecessors(SUnit *SU, unsigned CurCycle); 00119 void ReleaseSucc(SUnit *SU, const SDep *SuccEdge); 00120 void ReleaseSuccessors(SUnit *SU); 00121 void CapturePred(SDep *PredEdge); 00122 void ScheduleNodeBottomUp(SUnit*, unsigned); 00123 void ScheduleNodeTopDown(SUnit*, unsigned); 00124 void UnscheduleNodeBottomUp(SUnit*); 00125 void BacktrackBottomUp(SUnit*, unsigned, unsigned&); 00126 SUnit *CopyAndMoveSuccessors(SUnit*); 00127 void InsertCopiesAndMoveSuccs(SUnit*, unsigned, 00128 const TargetRegisterClass*, 00129 const TargetRegisterClass*, 00130 SmallVector<SUnit*, 2>&); 00131 bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 00132 void ListScheduleTopDown(); 00133 void ListScheduleBottomUp(); 00134 00135 00136 /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it. 00137 /// Updates the topological ordering if required. 00138 SUnit *CreateNewSUnit(SDNode *N) { 00139 unsigned NumSUnits = SUnits.size(); 00140 SUnit *NewNode = NewSUnit(N); 00141 // Update the topological ordering. 00142 if (NewNode->NodeNum >= NumSUnits) 00143 Topo.InitDAGTopologicalSorting(); 00144 return NewNode; 00145 } 00146 00147 /// CreateClone - Creates a new SUnit from an existing one. 00148 /// Updates the topological ordering if required. 00149 SUnit *CreateClone(SUnit *N) { 00150 unsigned NumSUnits = SUnits.size(); 00151 SUnit *NewNode = Clone(N); 00152 // Update the topological ordering. 00153 if (NewNode->NodeNum >= NumSUnits) 00154 Topo.InitDAGTopologicalSorting(); 00155 return NewNode; 00156 } 00157 00158 /// ForceUnitLatencies - Return true, since register-pressure-reducing 00159 /// scheduling doesn't need actual latency information. 00160 bool ForceUnitLatencies() const { return true; } 00161 }; 00162 } // end anonymous namespace 00163 00164 00165 /// Schedule - Schedule the DAG using list scheduling. 00166 void ScheduleDAGRRList::Schedule() { 00167 DOUT << "********** List Scheduling **********\n"; 00168 00169 NumLiveRegs = 0; 00170 LiveRegDefs.resize(TRI->getNumRegs(), NULL); 00171 LiveRegCycles.resize(TRI->getNumRegs(), 0); 00172 00173 // Build the scheduling graph. 00174 BuildSchedGraph(); 00175 00176 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 00177 SUnits[su].dumpAll(this)); 00178 Topo.InitDAGTopologicalSorting(); 00179 00180 AvailableQueue->initNodes(SUnits); 00181 00182 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. 00183 if (isBottomUp) 00184 ListScheduleBottomUp(); 00185 else 00186 ListScheduleTopDown(); 00187 00188 AvailableQueue->releaseState(); 00189 } 00190 00191 //===----------------------------------------------------------------------===// 00192 // Bottom-Up Scheduling 00193 //===----------------------------------------------------------------------===// 00194 00195 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 00196 /// the AvailableQueue if the count reaches zero. Also update its cycle bound. 00197 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) { 00198 SUnit *PredSU = PredEdge->getSUnit(); 00199 --PredSU->NumSuccsLeft; 00200 00201 #ifndef NDEBUG 00202 if (PredSU->NumSuccsLeft < 0) { 00203 cerr << "*** Scheduling failed! ***\n"; 00204 PredSU->dump(this); 00205 cerr << " has been released too many times!\n"; 00206 llvm_unreachable(0); 00207 } 00208 #endif 00209 00210 // If all the node's successors are scheduled, this node is ready 00211 // to be scheduled. Ignore the special EntrySU node. 00212 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { 00213 PredSU->isAvailable = true; 00214 AvailableQueue->push(PredSU); 00215 } 00216 } 00217 00218 void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { 00219 // Bottom up: release predecessors 00220 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 00221 I != E; ++I) { 00222 ReleasePred(SU, &*I); 00223 if (I->isAssignedRegDep()) { 00224 // This is a physical register dependency and it's impossible or 00225 // expensive to copy the register. Make sure nothing that can 00226 // clobber the register is scheduled between the predecessor and 00227 // this node. 00228 if (!LiveRegDefs[I->getReg()]) { 00229 ++NumLiveRegs; 00230 LiveRegDefs[I->getReg()] = I->getSUnit(); 00231 LiveRegCycles[I->getReg()] = CurCycle; 00232 } 00233 } 00234 } 00235 } 00236 00237 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 00238 /// count of its predecessors. If a predecessor pending count is zero, add it to 00239 /// the Available queue. 00240 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 00241 DOUT << "*** Scheduling [" << CurCycle << "]: "; 00242 DEBUG(SU->dump(this)); 00243 00244 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); 00245 SU->setHeightToAtLeast(CurCycle); 00246 Sequence.push_back(SU); 00247 00248 ReleasePredecessors(SU, CurCycle); 00249 00250 // Release all the implicit physical register defs that are live. 00251 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 00252 I != E; ++I) { 00253 if (I->isAssignedRegDep()) { 00254 if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) { 00255 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 00256 assert(LiveRegDefs[I->getReg()] == SU && 00257 "Physical register dependency violated?"); 00258 --NumLiveRegs; 00259 LiveRegDefs[I->getReg()] = NULL; 00260 LiveRegCycles[I->getReg()] = 0; 00261 } 00262 } 00263 } 00264 00265 SU->isScheduled = true; 00266 AvailableQueue->ScheduledNode(SU); 00267 } 00268 00269 /// CapturePred - This does the opposite of ReleasePred. Since SU is being 00270 /// unscheduled, incrcease the succ left count of its predecessors. Remove 00271 /// them from AvailableQueue if necessary. 00272 void ScheduleDAGRRList::CapturePred(SDep *PredEdge) { 00273 SUnit *PredSU = PredEdge->getSUnit(); 00274 if (PredSU->isAvailable) { 00275 PredSU->isAvailable = false; 00276 if (!PredSU->isPending) 00277 AvailableQueue->remove(PredSU); 00278 } 00279 00280 ++PredSU->NumSuccsLeft; 00281 } 00282 00283 /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and 00284 /// its predecessor states to reflect the change. 00285 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) { 00286 DOUT << "*** Unscheduling [" << SU->getHeight() << "]: "; 00287 DEBUG(SU->dump(this)); 00288 00289 AvailableQueue->UnscheduledNode(SU); 00290 00291 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 00292 I != E; ++I) { 00293 CapturePred(&*I); 00294 if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) { 00295 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 00296 assert(LiveRegDefs[I->getReg()] == I->getSUnit() && 00297 "Physical register dependency violated?"); 00298 --NumLiveRegs; 00299 LiveRegDefs[I->getReg()] = NULL; 00300 LiveRegCycles[I->getReg()] = 0; 00301 } 00302 } 00303 00304 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 00305 I != E; ++I) { 00306 if (I->isAssignedRegDep()) { 00307 if (!LiveRegDefs[I->getReg()]) { 00308 LiveRegDefs[I->getReg()] = SU; 00309 ++NumLiveRegs; 00310 } 00311 if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()]) 00312 LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight(); 00313 } 00314 } 00315 00316 SU->setHeightDirty(); 00317 SU->isScheduled = false; 00318 SU->isAvailable = true; 00319 AvailableQueue->push(SU); 00320 } 00321 00322 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in 00323 /// BTCycle in order to schedule a specific node. 00324 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, 00325 unsigned &CurCycle) { 00326 SUnit *OldSU = NULL; 00327 while (CurCycle > BtCycle) { 00328 OldSU = Sequence.back(); 00329 Sequence.pop_back(); 00330 if (SU->isSucc(OldSU)) 00331 // Don't try to remove SU from AvailableQueue. 00332 SU->isAvailable = false; 00333 UnscheduleNodeBottomUp(OldSU); 00334 --CurCycle; 00335 } 00336 00337 assert(!SU->isSucc(OldSU) && "Something is wrong!"); 00338 00339 ++NumBacktracks; 00340 } 00341 00342 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 00343 /// successors to the newly created node. 00344 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { 00345 if (SU->getNode()->getFlaggedNode()) 00346 return NULL; 00347 00348 SDNode *N = SU->getNode(); 00349 if (!N) 00350 return NULL; 00351 00352 SUnit *NewSU; 00353 bool TryUnfold = false; 00354 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 00355 EVT VT = N->getValueType(i); 00356 if (VT == MVT::Flag) 00357 return NULL; 00358 else if (VT == MVT::Other) 00359 TryUnfold = true; 00360 } 00361 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 00362 const SDValue &Op = N->getOperand(i); 00363 EVT VT = Op.getNode()->getValueType(Op.getResNo()); 00364 if (VT == MVT::Flag) 00365 return NULL; 00366 } 00367 00368 if (TryUnfold) { 00369 SmallVector<SDNode*, 2> NewNodes; 00370 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) 00371 return NULL; 00372 00373 DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; 00374 assert(NewNodes.size() == 2 && "Expected a load folding node!"); 00375 00376 N = NewNodes[1]; 00377 SDNode *LoadNode = NewNodes[0]; 00378 unsigned NumVals = N->getNumValues(); 00379 unsigned OldNumVals = SU->getNode()->getNumValues(); 00380 for (unsigned i = 0; i != NumVals; ++i) 00381 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); 00382 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), 00383 SDValue(LoadNode, 1)); 00384 00385 // LoadNode may already exist. This can happen when there is another 00386 // load from the same location and producing the same type of value 00387 // but it has different alignment or volatileness. 00388 bool isNewLoad = true; 00389 SUnit *LoadSU; 00390 if (LoadNode->getNodeId() != -1) { 00391 LoadSU = &SUnits[LoadNode->getNodeId()]; 00392 isNewLoad = false; 00393 } else { 00394 LoadSU = CreateNewSUnit(LoadNode); 00395 LoadNode->setNodeId(LoadSU->NodeNum); 00396 ComputeLatency(LoadSU); 00397 } 00398 00399 SUnit *NewSU = CreateNewSUnit(N); 00400 assert(N->getNodeId() == -1 && "Node already inserted!"); 00401 N->setNodeId(NewSU->NodeNum); 00402 00403 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 00404 for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 00405 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 00406 NewSU->isTwoAddress = true; 00407 break; 00408 } 00409 } 00410 if (TID.isCommutable()) 00411 NewSU->isCommutable = true; 00412 ComputeLatency(NewSU); 00413 00414 // Record all the edges to and from the old SU, by category. 00415 SmallVector<SDep, 4> ChainPreds; 00416 SmallVector<SDep, 4> ChainSuccs; 00417 SmallVector<SDep, 4> LoadPreds; 00418 SmallVector<SDep, 4> NodePreds; 00419 SmallVector<SDep, 4> NodeSuccs; 00420 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 00421 I != E; ++I) { 00422 if (I->isCtrl()) 00423 ChainPreds.push_back(*I); 00424 else if (I->getSUnit()->getNode() && 00425 I->getSUnit()->getNode()->isOperandOf(LoadNode)) 00426 LoadPreds.push_back(*I); 00427 else 00428 NodePreds.push_back(*I); 00429 } 00430 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 00431 I != E; ++I) { 00432 if (I->isCtrl()) 00433 ChainSuccs.push_back(*I); 00434 else 00435 NodeSuccs.push_back(*I); 00436 } 00437 00438 // Now assign edges to the newly-created nodes. 00439 for (unsigned i = 0, e = ChainPreds.size(); i != e; ++i) { 00440 const SDep &Pred = ChainPreds[i]; 00441 RemovePred(SU, Pred); 00442 if (isNewLoad) 00443 AddPred(LoadSU, Pred); 00444 } 00445 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 00446 const SDep &Pred = LoadPreds[i]; 00447 RemovePred(SU, Pred); 00448 if (isNewLoad) 00449 AddPred(LoadSU, Pred); 00450 } 00451 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 00452 const SDep &Pred = NodePreds[i]; 00453 RemovePred(SU, Pred); 00454 AddPred(NewSU, Pred); 00455 } 00456 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 00457 SDep D = NodeSuccs[i]; 00458 SUnit *SuccDep = D.getSUnit(); 00459 D.setSUnit(SU); 00460 RemovePred(SuccDep, D); 00461 D.setSUnit(NewSU); 00462 AddPred(SuccDep, D); 00463 } 00464 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 00465 SDep D = ChainSuccs[i]; 00466 SUnit *SuccDep = D.getSUnit(); 00467 D.setSUnit(SU); 00468 RemovePred(SuccDep, D); 00469 if (isNewLoad) { 00470 D.setSUnit(LoadSU); 00471 AddPred(SuccDep, D); 00472 } 00473 } 00474 00475 // Add a data dependency to reflect that NewSU reads the value defined 00476 // by LoadSU. 00477 AddPred(NewSU, SDep(LoadSU, SDep::Data, LoadSU->Latency)); 00478 00479 if (isNewLoad) 00480 AvailableQueue->addNode(LoadSU); 00481 AvailableQueue->addNode(NewSU); 00482 00483 ++NumUnfolds; 00484 00485 if (NewSU->NumSuccsLeft == 0) { 00486 NewSU->isAvailable = true; 00487 return NewSU; 00488 } 00489 SU = NewSU; 00490 } 00491 00492 DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; 00493 NewSU = CreateClone(SU); 00494 00495 // New SUnit has the exact same predecessors. 00496 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 00497 I != E; ++I) 00498 if (!I->isArtificial()) 00499 AddPred(NewSU, *I); 00500 00501 // Only copy scheduled successors. Cut them from old node's successor 00502 // list and move them over. 00503 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 00504 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 00505 I != E; ++I) { 00506 if (I->isArtificial()) 00507 continue; 00508 SUnit *SuccSU = I->getSUnit(); 00509 if (SuccSU->isScheduled) { 00510 SDep D = *I; 00511 D.setSUnit(NewSU); 00512 AddPred(SuccSU, D); 00513 D.setSUnit(SU); 00514 DelDeps.push_back(std::make_pair(SuccSU, D)); 00515 } 00516 } 00517 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) 00518 RemovePred(DelDeps[i].first, DelDeps[i].second); 00519 00520 AvailableQueue->updateNode(SU); 00521 AvailableQueue->addNode(NewSU); 00522 00523 ++NumDups; 00524 return NewSU; 00525 } 00526 00527 /// InsertCopiesAndMoveSuccs - Insert register copies and move all 00528 /// scheduled successors of the given SUnit to the last copy. 00529 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 00530 const TargetRegisterClass *DestRC, 00531 const TargetRegisterClass *SrcRC, 00532 SmallVector<SUnit*, 2> &Copies) { 00533 SUnit *CopyFromSU = CreateNewSUnit(NULL); 00534 CopyFromSU->CopySrcRC = SrcRC; 00535 CopyFromSU->CopyDstRC = DestRC; 00536 00537 SUnit *CopyToSU = CreateNewSUnit(NULL); 00538 CopyToSU->CopySrcRC = DestRC; 00539 CopyToSU->CopyDstRC = SrcRC; 00540 00541 // Only copy scheduled successors. Cut them from old node's successor 00542 // list and move them over. 00543 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 00544 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 00545 I != E; ++I) { 00546 if (I->isArtificial()) 00547 continue; 00548 SUnit *SuccSU = I->getSUnit(); 00549 if (SuccSU->isScheduled) { 00550 SDep D = *I; 00551 D.setSUnit(CopyToSU); 00552 AddPred(SuccSU, D); 00553 DelDeps.push_back(std::make_pair(SuccSU, *I)); 00554 } 00555 } 00556 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) 00557 RemovePred(DelDeps[i].first, DelDeps[i].second); 00558 00559 AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg)); 00560 AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0)); 00561 00562 AvailableQueue->updateNode(SU); 00563 AvailableQueue->addNode(CopyFromSU); 00564 AvailableQueue->addNode(CopyToSU); 00565 Copies.push_back(CopyFromSU); 00566 Copies.push_back(CopyToSU); 00567 00568 ++NumPRCopies; 00569 } 00570 00571 /// getPhysicalRegisterVT - Returns the ValueType of the physical register 00572 /// definition of the specified node. 00573 /// FIXME: Move to SelectionDAG? 00574 static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, 00575 const TargetInstrInfo *TII) { 00576 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 00577 assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 00578 unsigned NumRes = TID.getNumDefs(); 00579 for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { 00580 if (Reg == *ImpDef) 00581 break; 00582 ++NumRes; 00583 } 00584 return N->getValueType(NumRes); 00585 } 00586 00587 /// CheckForLiveRegDef - Return true and update live register vector if the 00588 /// specified register def of the specified SUnit clobbers any "live" registers. 00589 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, 00590 std::vector<SUnit*> &LiveRegDefs, 00591 SmallSet<unsigned, 4> &RegAdded, 00592 SmallVector<unsigned, 4> &LRegs, 00593 const TargetRegisterInfo *TRI) { 00594 bool Added = false; 00595 if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != SU) { 00596 if (RegAdded.insert(Reg)) { 00597 LRegs.push_back(Reg); 00598 Added = true; 00599 } 00600 } 00601 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) 00602 if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) { 00603 if (RegAdded.insert(*Alias)) { 00604 LRegs.push_back(*Alias); 00605 Added = true; 00606 } 00607 } 00608 return Added; 00609 } 00610 00611 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 00612 /// scheduling of the given node to satisfy live physical register dependencies. 00613 /// If the specific node is the last one that's available to schedule, do 00614 /// whatever is necessary (i.e. backtracking or cloning) to make it possible. 00615 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, 00616 SmallVector<unsigned, 4> &LRegs){ 00617 if (NumLiveRegs == 0) 00618 return false; 00619 00620 SmallSet<unsigned, 4> RegAdded; 00621 // If this node would clobber any "live" register, then it's not ready. 00622 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 00623 I != E; ++I) { 00624 if (I->isAssignedRegDep()) 00625 CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs, 00626 RegAdded, LRegs, TRI); 00627 } 00628 00629 for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) { 00630 if (Node->getOpcode() == ISD::INLINEASM) { 00631 // Inline asm can clobber physical defs. 00632 unsigned NumOps = Node->getNumOperands(); 00633 if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag) 00634 --NumOps; // Ignore the flag operand. 00635 00636 for (unsigned i = 2; i != NumOps;) { 00637 unsigned Flags = 00638 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue(); 00639 unsigned NumVals = (Flags & 0xffff) >> 3; 00640 00641 ++i; // Skip the ID value. 00642 if ((Flags & 7) == 2 || (Flags & 7) == 6) { 00643 // Check for def of register or earlyclobber register. 00644 for (; NumVals; --NumVals, ++i) { 00645 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg(); 00646 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 00647 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI); 00648 } 00649 } else 00650 i += NumVals; 00651 } 00652 continue; 00653 } 00654 00655 if (!Node->isMachineOpcode()) 00656 continue; 00657 const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); 00658 if (!TID.ImplicitDefs) 00659 continue; 00660 for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) 00661 CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI); 00662 } 00663 return !LRegs.empty(); 00664 } 00665 00666 00667 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 00668 /// schedulers. 00669 void ScheduleDAGRRList::ListScheduleBottomUp() { 00670 unsigned CurCycle = 0; 00671 00672 // Release any predecessors of the special Exit node. 00673 ReleasePredecessors(&ExitSU, CurCycle); 00674 00675 // Add root to Available queue. 00676 if (!SUnits.empty()) { 00677 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; 00678 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); 00679 RootSU->isAvailable = true; 00680 AvailableQueue->push(RootSU); 00681 } 00682 00683 // While Available queue is not empty, grab the node with the highest 00684 // priority. If it is not ready put it back. Schedule the node. 00685 SmallVector<SUnit*, 4> NotReady; 00686 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 00687 Sequence.reserve(SUnits.size()); 00688 while (!AvailableQueue->empty()) { 00689 bool Delayed = false; 00690 LRegsMap.clear(); 00691 SUnit *CurSU = AvailableQueue->pop(); 00692 while (CurSU) { 00693 SmallVector<unsigned, 4> LRegs; 00694 if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 00695 break; 00696 Delayed = true; 00697 LRegsMap.insert(std::make_pair(CurSU, LRegs)); 00698 00699 CurSU->isPending = true; // This SU is not in AvailableQueue right now. 00700 NotReady.push_back(CurSU); 00701 CurSU = AvailableQueue->pop(); 00702 } 00703 00704 // All candidates are delayed due to live physical reg dependencies. 00705 // Try backtracking, code duplication, or inserting cross class copies 00706 // to resolve it. 00707 if (Delayed && !CurSU) { 00708 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 00709 SUnit *TrySU = NotReady[i]; 00710 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 00711 00712 // Try unscheduling up to the point where it's safe to schedule 00713 // this node. 00714 unsigned LiveCycle = CurCycle; 00715 for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) { 00716 unsigned Reg = LRegs[j]; 00717 unsigned LCycle = LiveRegCycles[Reg]; 00718 LiveCycle = std::min(LiveCycle, LCycle); 00719 } 00720 SUnit *OldSU = Sequence[LiveCycle]; 00721 if (!WillCreateCycle(TrySU, OldSU)) { 00722 BacktrackBottomUp(TrySU, LiveCycle, CurCycle); 00723 // Force the current node to be scheduled before the node that 00724 // requires the physical reg dep. 00725 if (OldSU->isAvailable) { 00726 OldSU->isAvailable = false; 00727 AvailableQueue->remove(OldSU); 00728 } 00729 AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1, 00730 /*Reg=*/0, /*isNormalMemory=*/false, 00731 /*isMustAlias=*/false, /*isArtificial=*/true)); 00732 // If one or more successors has been unscheduled, then the current 00733 // node is no longer avaialable. Schedule a successor that's now 00734 // available instead. 00735 if (!TrySU->isAvailable) 00736 CurSU = AvailableQueue->pop(); 00737 else { 00738 CurSU = TrySU; 00739 TrySU->isPending = false; 00740 NotReady.erase(NotReady.begin()+i); 00741 } 00742 break; 00743 } 00744 } 00745 00746 if (!CurSU) { 00747 // Can't backtrack. If it's too expensive to copy the value, then try 00748 // duplicate the nodes that produces these "too expensive to copy" 00749 // values to break the dependency. In case even that doesn't work, 00750 // insert cross class copies. 00751 // If it's not too expensive, i.e. cost != -1, issue copies. 00752 SUnit *TrySU = NotReady[0]; 00753 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 00754 assert(LRegs.size() == 1 && "Can't handle this yet!"); 00755 unsigned Reg = LRegs[0]; 00756 SUnit *LRDef = LiveRegDefs[Reg]; 00757 EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); 00758 const TargetRegisterClass *RC = 00759 TRI->getPhysicalRegisterRegClass(Reg, VT); 00760 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 00761 00762 // If cross copy register class is null, then it must be possible copy 00763 // the value directly. Do not try duplicate the def. 00764 SUnit *NewDef = 0; 00765 if (DestRC) 00766 NewDef = CopyAndMoveSuccessors(LRDef); 00767 else 00768 DestRC = RC; 00769 if (!NewDef) { 00770 // Issue copies, these can be expensive cross register class copies. 00771 SmallVector<SUnit*, 2> Copies; 00772 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 00773 DOUT << "Adding an edge from SU #" << TrySU->NodeNum 00774 << " to SU #" << Copies.front()->NodeNum << "\n"; 00775 AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1, 00776 /*Reg=*/0, /*isNormalMemory=*/false, 00777 /*isMustAlias=*/false, 00778 /*isArtificial=*/true)); 00779 NewDef = Copies.back(); 00780 } 00781 00782 DOUT << "Adding an edge from SU #" << NewDef->NodeNum 00783 << " to SU #" << TrySU->NodeNum << "\n"; 00784 LiveRegDefs[Reg] = NewDef; 00785 AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1, 00786 /*Reg=*/0, /*isNormalMemory=*/false, 00787 /*isMustAlias=*/false, 00788 /*isArtificial=*/true)); 00789 TrySU->isAvailable = false; 00790 CurSU = NewDef; 00791 } 00792 00793 assert(CurSU && "Unable to resolve live physical register dependencies!"); 00794 } 00795 00796 // Add the nodes that aren't ready back onto the available list. 00797 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 00798 NotReady[i]->isPending = false; 00799 // May no longer be available due to backtracking. 00800 if (NotReady[i]->isAvailable) 00801 AvailableQueue->push(NotReady[i]); 00802 } 00803 NotReady.clear(); 00804 00805 if (CurSU) 00806 ScheduleNodeBottomUp(CurSU, CurCycle); 00807 ++CurCycle; 00808 } 00809 00810 // Reverse the order if it is bottom up. 00811 std::reverse(Sequence.begin(), Sequence.end()); 00812 00813 #ifndef NDEBUG 00814 VerifySchedule(isBottomUp); 00815 #endif 00816 } 00817 00818 //===----------------------------------------------------------------------===// 00819 // Top-Down Scheduling 00820 //===----------------------------------------------------------------------===// 00821 00822 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 00823 /// the AvailableQueue if the count reaches zero. Also update its cycle bound. 00824 void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) { 00825 SUnit *SuccSU = SuccEdge->getSUnit(); 00826 --SuccSU->NumPredsLeft; 00827 00828 #ifndef NDEBUG 00829 if (SuccSU->NumPredsLeft < 0) { 00830 cerr << "*** Scheduling failed! ***\n"; 00831 SuccSU->dump(this); 00832 cerr << " has been released too many times!\n"; 00833 llvm_unreachable(0); 00834 } 00835 #endif 00836 00837 // If all the node's predecessors are scheduled, this node is ready 00838 // to be scheduled. Ignore the special ExitSU node. 00839 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { 00840 SuccSU->isAvailable = true; 00841 AvailableQueue->push(SuccSU); 00842 } 00843 } 00844 00845 void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) { 00846 // Top down: release successors 00847 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 00848 I != E; ++I) { 00849 assert(!I->isAssignedRegDep() && 00850 "The list-tdrr scheduler doesn't yet support physreg dependencies!"); 00851 00852 ReleaseSucc(SU, &*I); 00853 } 00854 } 00855 00856 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 00857 /// count of its successors. If a successor pending count is zero, add it to 00858 /// the Available queue. 00859 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 00860 DOUT << "*** Scheduling [" << CurCycle << "]: "; 00861 DEBUG(SU->dump(this)); 00862 00863 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 00864 SU->setDepthToAtLeast(CurCycle); 00865 Sequence.push_back(SU); 00866 00867 ReleaseSuccessors(SU); 00868 SU->isScheduled = true; 00869 AvailableQueue->ScheduledNode(SU); 00870 } 00871 00872 /// ListScheduleTopDown - The main loop of list scheduling for top-down 00873 /// schedulers. 00874 void ScheduleDAGRRList::ListScheduleTopDown() { 00875 unsigned CurCycle = 0; 00876 00877 // Release any successors of the special Entry node. 00878 ReleaseSuccessors(&EntrySU); 00879 00880 // All leaves to Available queue. 00881 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 00882 // It is available if it has no predecessors. 00883 if (SUnits[i].Preds.empty()) { 00884 AvailableQueue->push(&SUnits[i]); 00885 SUnits[i].isAvailable = true; 00886 } 00887 } 00888 00889 // While Available queue is not empty, grab the node with the highest 00890 // priority. If it is not ready put it back. Schedule the node. 00891 Sequence.reserve(SUnits.size()); 00892 while (!AvailableQueue->empty()) { 00893 SUnit *CurSU = AvailableQueue->pop(); 00894 00895 if (CurSU) 00896 ScheduleNodeTopDown(CurSU, CurCycle); 00897 ++CurCycle; 00898 } 00899 00900 #ifndef NDEBUG 00901 VerifySchedule(isBottomUp); 00902 #endif 00903 } 00904 00905 00906 //===----------------------------------------------------------------------===// 00907 // RegReductionPriorityQueue Implementation 00908 //===----------------------------------------------------------------------===// 00909 // 00910 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers 00911 // to reduce register pressure. 00912 // 00913 namespace { 00914 template<class SF> 00915 class RegReductionPriorityQueue; 00916 00917 /// Sorting functions for the Available queue. 00918 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 00919 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; 00920 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} 00921 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 00922 00923 bool operator()(const SUnit* left, const SUnit* right) const; 00924 }; 00925 00926 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 00927 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; 00928 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} 00929 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 00930 00931 bool operator()(const SUnit* left, const SUnit* right) const; 00932 }; 00933 } // end anonymous namespace 00934 00935 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number. 00936 /// Smaller number is the higher priority. 00937 static unsigned 00938 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) { 00939 unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum]; 00940 if (SethiUllmanNumber != 0) 00941 return SethiUllmanNumber; 00942 00943 unsigned Extra = 0; 00944 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 00945 I != E; ++I) { 00946 if (I->isCtrl()) continue; // ignore chain preds 00947 SUnit *PredSU = I->getSUnit(); 00948 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers); 00949 if (PredSethiUllman > SethiUllmanNumber) { 00950 SethiUllmanNumber = PredSethiUllman; 00951 Extra = 0; 00952 } else if (PredSethiUllman == SethiUllmanNumber) 00953 ++Extra; 00954 } 00955 00956 SethiUllmanNumber += Extra; 00957 00958 if (SethiUllmanNumber == 0) 00959 SethiUllmanNumber = 1; 00960 00961 return SethiUllmanNumber; 00962 } 00963 00964 namespace { 00965 template<class SF> 00966 class VISIBILITY_HIDDEN RegReductionPriorityQueue 00967 : public SchedulingPriorityQueue { 00968 PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue; 00969 unsigned currentQueueId; 00970 00971 protected: 00972 // SUnits - The SUnits for the current graph. 00973 std::vector<SUnit> *SUnits; 00974 00975 const TargetInstrInfo *TII; 00976 const TargetRegisterInfo *TRI; 00977 ScheduleDAGRRList *scheduleDAG; 00978 00979 // SethiUllmanNumbers - The SethiUllman number for each node. 00980 std::vector<unsigned> SethiUllmanNumbers; 00981 00982 public: 00983 RegReductionPriorityQueue(const TargetInstrInfo *tii, 00984 const TargetRegisterInfo *tri) : 00985 Queue(SF(this)), currentQueueId(0), 00986 TII(tii), TRI(tri), scheduleDAG(NULL) {} 00987 00988 void initNodes(std::vector<SUnit> &sunits) { 00989 SUnits = &sunits; 00990 // Add pseudo dependency edges for two-address nodes. 00991 AddPseudoTwoAddrDeps(); 00992 // Reroute edges to nodes with multiple uses. 00993 PrescheduleNodesWithMultipleUses(); 00994 // Calculate node priorities. 00995 CalculateSethiUllmanNumbers(); 00996 } 00997 00998 void addNode(const SUnit *SU) { 00999 unsigned SUSize = SethiUllmanNumbers.size(); 01000 if (SUnits->size() > SUSize) 01001 SethiUllmanNumbers.resize(SUSize*2, 0); 01002 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers); 01003 } 01004 01005 void updateNode(const SUnit *SU) { 01006 SethiUllmanNumbers[SU->NodeNum] = 0; 01007 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers); 01008 } 01009 01010 void releaseState() { 01011 SUnits = 0; 01012 SethiUllmanNumbers.clear(); 01013 } 01014 01015 unsigned getNodePriority(const SUnit *SU) const { 01016 assert(SU->NodeNum < SethiUllmanNumbers.size()); 01017 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0; 01018 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 01019 // CopyToReg should be close to its uses to facilitate coalescing and 01020 // avoid spilling. 01021 return 0; 01022 if (Opc == TargetInstrInfo::EXTRACT_SUBREG || 01023 Opc == TargetInstrInfo::SUBREG_TO_REG || 01024 Opc == TargetInstrInfo::INSERT_SUBREG) 01025 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be 01026 // close to their uses to facilitate coalescing. 01027 return 0; 01028 if (SU->NumSuccs == 0 && SU->NumPreds != 0) 01029 // If SU does not have a register use, i.e. it doesn't produce a value 01030 // that would be consumed (e.g. store), then it terminates a chain of 01031 // computation. Give it a large SethiUllman number so it will be 01032 // scheduled right before its predecessors that it doesn't lengthen 01033 // their live ranges. 01034 return 0xffff; 01035 if (SU->NumPreds == 0 && SU->NumSuccs != 0) 01036 // If SU does not have a register def, schedule it close to its uses 01037 // because it does not lengthen any live ranges. 01038 return 0; 01039 return SethiUllmanNumbers[SU->NodeNum]; 01040 } 01041 01042 unsigned size() const { return Queue.size(); } 01043 01044 bool empty() const { return Queue.empty(); } 01045 01046 void push(SUnit *U) { 01047 assert(!U->NodeQueueId && "Node in the queue already"); 01048 U->NodeQueueId = ++currentQueueId; 01049 Queue.push(U); 01050 } 01051 01052 void push_all(const std::vector<SUnit *> &Nodes) { 01053 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 01054 push(Nodes[i]); 01055 } 01056 01057 SUnit *pop() { 01058 if (empty()) return NULL; 01059 SUnit *V = Queue.top(); 01060 Queue.pop(); 01061 V->NodeQueueId = 0; 01062 return V; 01063 } 01064 01065 void remove(SUnit *SU) { 01066 assert(!Queue.empty() && "Queue is empty!"); 01067 assert(SU->NodeQueueId != 0 && "Not in queue!"); 01068 Queue.erase_one(SU); 01069 SU->NodeQueueId = 0; 01070 } 01071 01072 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) { 01073 scheduleDAG = scheduleDag; 01074 } 01075 01076 protected: 01077 bool canClobber(const SUnit *SU, const SUnit *Op); 01078 void AddPseudoTwoAddrDeps(); 01079 void PrescheduleNodesWithMultipleUses(); 01080 void CalculateSethiUllmanNumbers(); 01081 }; 01082 01083 typedef RegReductionPriorityQueue<bu_ls_rr_sort> 01084 BURegReductionPriorityQueue; 01085 01086 typedef RegReductionPriorityQueue<td_ls_rr_sort> 01087 TDRegReductionPriorityQueue; 01088 } 01089 01090 /// closestSucc - Returns the scheduled cycle of the successor which is 01091 /// closest to the current cycle. 01092 static unsigned closestSucc(const SUnit *SU) { 01093 unsigned MaxHeight = 0; 01094 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 01095 I != E; ++I) { 01096 if (I->isCtrl()) continue; // ignore chain succs 01097 unsigned Height = I->getSUnit()->getHeight(); 01098 // If there are bunch of CopyToRegs stacked up, they should be considered 01099 // to be at the same position. 01100 if (I->getSUnit()->getNode() && 01101 I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg) 01102 Height = closestSucc(I->getSUnit())+1; 01103 if (Height > MaxHeight) 01104 MaxHeight = Height; 01105 } 01106 return MaxHeight; 01107 } 01108 01109 /// calcMaxScratches - Returns an cost estimate of the worse case requirement 01110 /// for scratch registers, i.e. number of data dependencies. 01111 static unsigned calcMaxScratches(const SUnit *SU) { 01112 unsigned Scratches = 0; 01113 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 01114 I != E; ++I) { 01115 if (I->isCtrl()) continue; // ignore chain preds 01116 Scratches++; 01117 } 01118 return Scratches; 01119 } 01120 01121 // Bottom up 01122 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 01123 unsigned LPriority = SPQ->getNodePriority(left); 01124 unsigned RPriority = SPQ->getNodePriority(right); 01125 if (LPriority != RPriority) 01126 return LPriority > RPriority; 01127 01128 // Try schedule def + use closer when Sethi-Ullman numbers are the same. 01129 // e.g. 01130 // t1 = op t2, c1 01131 // t3 = op t4, c2 01132 // 01133 // and the following instructions are both ready. 01134 // t2 = op c3 01135 // t4 = op c4 01136 // 01137 // Then schedule t2 = op first. 01138 // i.e. 01139 // t4 = op c4 01140 // t2 = op c3 01141 // t1 = op t2, c1 01142 // t3 = op t4, c2 01143 // 01144 // This creates more short live intervals. 01145 unsigned LDist = closestSucc(left); 01146 unsigned RDist = closestSucc(right); 01147 if (LDist != RDist) 01148 return LDist < RDist; 01149 01150 // How many registers becomes live when the node is scheduled. 01151 unsigned LScratch = calcMaxScratches(left); 01152 unsigned RScratch = calcMaxScratches(right); 01153 if (LScratch != RScratch) 01154 return LScratch > RScratch; 01155 01156 if (left->getHeight() != right->getHeight()) 01157 return left->getHeight() > right->getHeight(); 01158 01159 if (left->getDepth() != right->getDepth()) 01160 return left->getDepth() < right->getDepth(); 01161 01162 assert(left->NodeQueueId && right->NodeQueueId && 01163 "NodeQueueId cannot be zero"); 01164 return (left->NodeQueueId > right->NodeQueueId); 01165 } 01166 01167 template<class SF> 01168 bool 01169 RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) { 01170 if (SU->isTwoAddress) { 01171 unsigned Opc = SU->getNode()->getMachineOpcode(); 01172 const TargetInstrDesc &TID = TII->get(Opc); 01173 unsigned NumRes = TID.getNumDefs(); 01174 unsigned NumOps = TID.getNumOperands() - NumRes; 01175 for (unsigned i = 0; i != NumOps; ++i) { 01176 if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) { 01177 SDNode *DU = SU->getNode()->getOperand(i).getNode(); 01178 if (DU->getNodeId() != -1 && 01179 Op->OrigNode == &(*SUnits)[DU->getNodeId()]) 01180 return true; 01181 } 01182 } 01183 } 01184 return false; 01185 } 01186 01187 01188 /// hasCopyToRegUse - Return true if SU has a value successor that is a 01189 /// CopyToReg node. 01190 static bool hasCopyToRegUse(const SUnit *SU) { 01191 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 01192 I != E; ++I) { 01193 if (I->isCtrl()) continue; 01194 const SUnit *SuccSU = I->getSUnit(); 01195 if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg) 01196 return true; 01197 } 01198 return false; 01199 } 01200 01201 /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's 01202 /// physical register defs. 01203 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU, 01204 const TargetInstrInfo *TII, 01205 const TargetRegisterInfo *TRI) { 01206 SDNode *N = SuccSU->getNode(); 01207 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs(); 01208 const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs(); 01209 assert(ImpDefs && "Caller should check hasPhysRegDefs"); 01210 for (const SDNode *SUNode = SU->getNode(); SUNode; 01211 SUNode = SUNode->getFlaggedNode()) { 01212 if (!SUNode->isMachineOpcode()) 01213 continue; 01214 const unsigned *SUImpDefs = 01215 TII->get(SUNode->getMachineOpcode()).getImplicitDefs(); 01216 if (!SUImpDefs) 01217 return false; 01218 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) { 01219 EVT VT = N->getValueType(i); 01220 if (VT == MVT::Flag || VT == MVT::Other) 01221 continue; 01222 if (!N->hasAnyUseOfValue(i)) 01223 continue; 01224 unsigned Reg = ImpDefs[i - NumDefs]; 01225 for (;*SUImpDefs; ++SUImpDefs) { 01226 unsigned SUReg = *SUImpDefs; 01227 if (TRI->regsOverlap(Reg, SUReg)) 01228 return true; 01229 } 01230 } 01231 } 01232 return false; 01233 } 01234 01235 /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses 01236 /// are not handled well by the general register pressure reduction 01237 /// heuristics. When presented with code like this: 01238 /// 01239 /// N 01240 /// / | 01241 /// / | 01242 /// U store 01243 /// | 01244 /// ... 01245 /// 01246 /// the heuristics tend to push the store up, but since the 01247 /// operand of the store has another use (U), this would increase 01248 /// the length of that other use (the U->N edge). 01249 /// 01250 /// This function transforms code like the above to route U's 01251 /// dependence through the store when possible, like this: 01252 /// 01253 /// N 01254 /// || 01255 /// || 01256 /// store 01257 /// | 01258 /// U 01259 /// | 01260 /// ... 01261 /// 01262 /// This results in the store being scheduled immediately 01263 /// after N, which shortens the U->N live range, reducing 01264 /// register pressure. 01265 /// 01266 template<class SF> 01267 void RegReductionPriorityQueue<SF>::PrescheduleNodesWithMultipleUses() { 01268 // Visit all the nodes in topological order, working top-down. 01269 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 01270 SUnit *SU = &(*SUnits)[i]; 01271 // For now, only look at nodes with no data successors, such as stores. 01272 // These are especially important, due to the heuristics in 01273 // getNodePriority for nodes with no data successors. 01274 if (SU->NumSuccs != 0) 01275 continue; 01276 // For now, only look at nodes with exactly one data predecessor. 01277 if (SU->NumPreds != 1) 01278 continue; 01279 // Avoid prescheduling copies to virtual registers, which don't behave 01280 // like other nodes from the perspective of scheduling heuristics. 01281 if (SDNode *N = SU->getNode()) 01282 if (N->getOpcode() == ISD::CopyToReg && 01283 TargetRegisterInfo::isVirtualRegister 01284 (cast<RegisterSDNode>(N->getOperand(1))->getReg())) 01285 continue; 01286 01287 // Locate the single data predecessor. 01288 SUnit *PredSU = 0; 01289 for (SUnit::const_pred_iterator II = SU->Preds.begin(), 01290 EE = SU->Preds.end(); II != EE; ++II) 01291 if (!II->isCtrl()) { 01292 PredSU = II->getSUnit(); 01293 break; 01294 } 01295 assert(PredSU); 01296 01297 // Don't rewrite edges that carry physregs, because that requires additional 01298 // support infrastructure. 01299 if (PredSU->hasPhysRegDefs) 01300 continue; 01301 // Short-circuit the case where SU is PredSU's only data successor. 01302 if (PredSU->NumSuccs == 1) 01303 continue; 01304 // Avoid prescheduling to copies from virtual registers, which don't behave 01305 // like other nodes from the perspective of scheduling // heuristics. 01306 if (SDNode *N = SU->getNode()) 01307 if (N->getOpcode() == ISD::CopyFromReg && 01308 TargetRegisterInfo::isVirtualRegister 01309 (cast<RegisterSDNode>(N->getOperand(1))->getReg())) 01310 continue; 01311 01312 // Perform checks on the successors of PredSU. 01313 for (SUnit::const_succ_iterator II = PredSU->Succs.begin(), 01314 EE = PredSU->Succs.end(); II != EE; ++II) { 01315 SUnit *PredSuccSU = II->getSUnit(); 01316 if (PredSuccSU == SU) continue; 01317 // If PredSU has another successor with no data successors, for 01318 // now don't attempt to choose either over the other. 01319 if (PredSuccSU->NumSuccs == 0) 01320 goto outer_loop_continue; 01321 // Don't break physical register dependencies. 01322 if (SU->hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs) 01323 if (canClobberPhysRegDefs(PredSuccSU, SU, TII, TRI)) 01324 goto outer_loop_continue; 01325 // Don't introduce graph cycles. 01326 if (scheduleDAG->IsReachable(SU, PredSuccSU)) 01327 goto outer_loop_continue; 01328 } 01329 01330 // Ok, the transformation is safe and the heuristics suggest it is 01331 // profitable. Update the graph. 01332 DOUT << "Prescheduling SU # " << SU->NodeNum 01333 << " next to PredSU # " << PredSU->NodeNum 01334 << " to guide scheduling in the presence of multiple uses\n"; 01335 for (unsigned i = 0; i != PredSU->Succs.size(); ++i) { 01336 SDep Edge = PredSU->Succs[i]; 01337 assert(!Edge.isAssignedRegDep()); 01338 SUnit *SuccSU = Edge.getSUnit(); 01339 if (SuccSU != SU) { 01340 Edge.setSUnit(PredSU); 01341 scheduleDAG->RemovePred(SuccSU, Edge); 01342 scheduleDAG->AddPred(SU, Edge); 01343 Edge.setSUnit(SU); 01344 scheduleDAG->AddPred(SuccSU, Edge); 01345 --i; 01346 } 01347 } 01348 outer_loop_continue:; 01349 } 01350 } 01351 01352 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses 01353 /// it as a def&use operand. Add a pseudo control edge from it to the other 01354 /// node (if it won't create a cycle) so the two-address one will be scheduled 01355 /// first (lower in the schedule). If both nodes are two-address, favor the 01356 /// one that has a CopyToReg use (more likely to be a loop induction update). 01357 /// If both are two-address, but one is commutable while the other is not 01358 /// commutable, favor the one that's not commutable. 01359 template<class SF> 01360 void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { 01361 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 01362 SUnit *SU = &(*SUnits)[i]; 01363 if (!SU->isTwoAddress) 01364 continue; 01365 01366 SDNode *Node = SU->getNode(); 01367 if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode()) 01368 continue; 01369 01370 unsigned Opc = Node->getMachineOpcode(); 01371 const TargetInstrDesc &TID = TII->get(Opc); 01372 unsigned NumRes = TID.getNumDefs(); 01373 unsigned NumOps = TID.getNumOperands() - NumRes; 01374 for (unsigned j = 0; j != NumOps; ++j) { 01375 if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1) 01376 continue; 01377 SDNode *DU = SU->getNode()->getOperand(j).getNode(); 01378 if (DU->getNodeId() == -1) 01379 continue; 01380 const SUnit *DUSU = &(*SUnits)[DU->getNodeId()]; 01381 if (!DUSU) continue; 01382 for (SUnit::const_succ_iterator I = DUSU->Succs.begin(), 01383 E = DUSU->Succs.end(); I != E; ++I) { 01384 if (I->isCtrl()) continue; 01385 SUnit *SuccSU = I->getSUnit(); 01386 if (SuccSU == SU) 01387 continue; 01388 // Be conservative. Ignore if nodes aren't at roughly the same 01389 // depth and height. 01390 if (SuccSU->getHeight() < SU->getHeight() && 01391 (SU->getHeight() - SuccSU->getHeight()) > 1) 01392 continue; 01393 // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge 01394 // constrains whatever is using the copy, instead of the copy 01395 // itself. In the case that the copy is coalesced, this 01396 // preserves the intent of the pseudo two-address heurietics. 01397 while (SuccSU->Succs.size() == 1 && 01398 SuccSU->getNode()->isMachineOpcode() && 01399 SuccSU->getNode()->getMachineOpcode() == 01400 TargetInstrInfo::COPY_TO_REGCLASS) 01401 SuccSU = SuccSU->Succs.front().getSUnit(); 01402 // Don't constrain non-instruction nodes. 01403 if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode()) 01404 continue; 01405 // Don't constrain nodes with physical register defs if the 01406 // predecessor can clobber them. 01407 if (SuccSU->hasPhysRegDefs && SU->hasPhysRegClobbers) { 01408 if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI)) 01409 continue; 01410 } 01411 // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG; 01412 // these may be coalesced away. We want them close to their uses. 01413 unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode(); 01414 if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG || 01415 SuccOpc == TargetInstrInfo::INSERT_SUBREG || 01416 SuccOpc == TargetInstrInfo::SUBREG_TO_REG) 01417 continue; 01418 if ((!canClobber(SuccSU, DUSU) || 01419 (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) || 01420 (!SU->isCommutable && SuccSU->isCommutable)) && 01421 !scheduleDAG->IsReachable(SuccSU, SU)) { 01422 DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum 01423 << " to SU #" << SuccSU->NodeNum << "\n"; 01424 scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0, 01425 /*Reg=*/0, /*isNormalMemory=*/false, 01426 /*isMustAlias=*/false, 01427 /*isArtificial=*/true)); 01428 } 01429 } 01430 } 01431 } 01432 } 01433 01434 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 01435 /// scheduling units. 01436 template<class SF> 01437 void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 01438 SethiUllmanNumbers.assign(SUnits->size(), 0); 01439 01440 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 01441 CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers); 01442 } 01443 01444 /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled 01445 /// predecessors of the successors of the SUnit SU. Stop when the provided 01446 /// limit is exceeded. 01447 static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU, 01448 unsigned Limit) { 01449 unsigned Sum = 0; 01450 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 01451 I != E; ++I) { 01452 const SUnit *SuccSU = I->getSUnit(); 01453 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(), 01454 EE = SuccSU->Preds.end(); II != EE; ++II) { 01455 SUnit *PredSU = II->getSUnit(); 01456 if (!PredSU->isScheduled) 01457 if (++Sum > Limit) 01458 return Sum; 01459 } 01460 } 01461 return Sum; 01462 } 01463 01464 01465 // Top down 01466 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 01467 unsigned LPriority = SPQ->getNodePriority(left); 01468 unsigned RPriority = SPQ->getNodePriority(right); 01469 bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode(); 01470 bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode(); 01471 bool LIsFloater = LIsTarget && left->NumPreds == 0; 01472 bool RIsFloater = RIsTarget && right->NumPreds == 0; 01473 unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0; 01474 unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0; 01475 01476 if (left->NumSuccs == 0 && right->NumSuccs != 0) 01477 return false; 01478 else if (left->NumSuccs != 0 && right->NumSuccs == 0) 01479 return true; 01480 01481 if (LIsFloater) 01482 LBonus -= 2; 01483 if (RIsFloater) 01484 RBonus -= 2; 01485 if (left->NumSuccs == 1) 01486 LBonus += 2; 01487 if (right->NumSuccs == 1) 01488 RBonus += 2; 01489 01490 if (LPriority+LBonus != RPriority+RBonus) 01491 return LPriority+LBonus < RPriority+RBonus; 01492 01493 if (left->getDepth() != right->getDepth()) 01494 return left->getDepth() < right->getDepth(); 01495 01496 if (left->NumSuccsLeft != right->NumSuccsLeft) 01497 return left->NumSuccsLeft > right->NumSuccsLeft; 01498 01499 assert(left->NodeQueueId && right->NodeQueueId && 01500 "NodeQueueId cannot be zero"); 01501 return (left->NodeQueueId > right->NodeQueueId); 01502 } 01503 01504 //===----------------------------------------------------------------------===// 01505 // Public Constructor Functions 01506 //===----------------------------------------------------------------------===// 01507 01508 llvm::ScheduleDAGSDNodes * 01509 llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 01510 const TargetMachine &TM = IS->TM; 01511 const TargetInstrInfo *TII = TM.getInstrInfo(); 01512 const TargetRegisterInfo *TRI = TM.getRegisterInfo(); 01513 01514 BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI); 01515 01516 ScheduleDAGRRList *SD = 01517 new ScheduleDAGRRList(*IS->MF, true, PQ); 01518 PQ->setScheduleDAG(SD); 01519 return SD; 01520 } 01521 01522 llvm::ScheduleDAGSDNodes * 01523 llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 01524 const TargetMachine &TM = IS->TM; 01525 const TargetInstrInfo *TII = TM.getInstrInfo(); 01526 const TargetRegisterInfo *TRI = TM.getRegisterInfo(); 01527 01528 TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI); 01529 01530 ScheduleDAGRRList *SD = 01531 new ScheduleDAGRRList(*IS->MF, false, PQ); 01532 PQ->setScheduleDAG(SD); 01533 return SD; 01534 }