1 //===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "sched"
19 #include "llvm/CodeGen/ScheduleDAG.h"
20 #include "llvm/CodeGen/SSARegMap.h"
21 #include "llvm/Target/MRegisterInfo.h"
22 #include "llvm/Target/TargetData.h"
23 #include "llvm/Target/TargetMachine.h"
24 #include "llvm/Target/TargetInstrInfo.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/ADT/Statistic.h"
30 #include "llvm/Support/CommandLine.h"
34 //===----------------------------------------------------------------------===//
35 /// ScheduleDAGRRList - The actual register reduction list scheduler
36 /// implementation. This supports both top-down and bottom-up scheduling.
39 class ScheduleDAGRRList : public ScheduleDAG {
41 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
45 /// AvailableQueue - The priority queue to use for the available SUnits.
47 SchedulingPriorityQueue *AvailableQueue;
50 ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb,
51 const TargetMachine &tm, bool isbottomup,
52 SchedulingPriorityQueue *availqueue)
53 : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
54 AvailableQueue(availqueue) {
57 ~ScheduleDAGRRList() {
58 delete AvailableQueue;
64 void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
65 void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle);
66 void ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle);
67 void ScheduleNodeTopDown(SUnit *SU, unsigned& CurCycle);
68 void ListScheduleTopDown();
69 void ListScheduleBottomUp();
70 void CommuteNodesToReducePressure();
72 } // end anonymous namespace
75 /// Schedule - Schedule the DAG using list scheduling.
76 void ScheduleDAGRRList::Schedule() {
77 DEBUG(std::cerr << "********** List Scheduling **********\n");
79 // Build scheduling units.
81 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
82 SUnits[su].dumpAll(&DAG));
86 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
87 SUnits[su].dumpAll(&DAG));
89 AvailableQueue->initNodes(SUnits);
91 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
93 ListScheduleBottomUp();
95 ListScheduleTopDown();
97 AvailableQueue->releaseState();
99 CommuteNodesToReducePressure();
101 DEBUG(std::cerr << "*** Final schedule ***\n");
102 DEBUG(dumpSchedule());
103 DEBUG(std::cerr << "\n");
105 // Emit in scheduled order
109 /// CommuteNodesToReducePressure - Is a node is two-address and commutable, and
110 /// it is not the last use of its first operand, add it to the CommuteSet if
111 /// possible. It will be commuted when it is translated to a MI.
112 void ScheduleDAGRRList::CommuteNodesToReducePressure() {
113 std::set<SUnit *> OperandSeen;
114 for (unsigned i = Sequence.size()-1; i != 0; --i) { // Ignore first node.
115 SUnit *SU = Sequence[i];
117 if (SU->isTwoAddress && SU->isCommutable) {
118 SDNode *OpN = SU->Node->getOperand(0).Val;
119 SUnit *OpSU = SUnitMap[OpN];
120 if (OpSU && OperandSeen.count(OpSU) == 1) {
121 // Ok, so SU is not the last use of OpSU, but SU is two-address so
122 // it will clobber OpSU. Try to commute it if possible.
123 bool DoCommute = true;
124 for (unsigned j = 1, e = SU->Node->getNumOperands(); j != e; ++j) {
125 OpN = SU->Node->getOperand(j).Val;
126 OpSU = SUnitMap[OpN];
127 if (OpSU && OperandSeen.count(OpSU) == 1) {
133 CommuteSet.insert(SU->Node);
137 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
138 E = SU->Preds.end(); I != E; ++I) {
140 OperandSeen.insert(I->first);
145 //===----------------------------------------------------------------------===//
146 // Bottom-Up Scheduling
147 //===----------------------------------------------------------------------===//
149 static const TargetRegisterClass *getRegClass(SUnit *SU,
150 const TargetInstrInfo *TII,
151 const MRegisterInfo *MRI,
153 if (SU->Node->isTargetOpcode()) {
154 unsigned Opc = SU->Node->getTargetOpcode();
155 const TargetInstrDescriptor &II = TII->get(Opc);
156 return II.OpInfo->RegClass;
158 assert(SU->Node->getOpcode() == ISD::CopyFromReg);
159 unsigned SrcReg = cast<RegisterSDNode>(SU->Node->getOperand(1))->getReg();
160 if (MRegisterInfo::isVirtualRegister(SrcReg))
161 return RegMap->getRegClass(SrcReg);
163 for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
164 E = MRI->regclass_end(); I != E; ++I)
165 if ((*I)->hasType(SU->Node->getValueType(0)) &&
166 (*I)->contains(SrcReg))
168 assert(false && "Couldn't find register class for reg copy!");
174 static unsigned getNumResults(SUnit *SU) {
175 unsigned NumResults = 0;
176 for (unsigned i = 0, e = SU->Node->getNumValues(); i != e; ++i) {
177 MVT::ValueType VT = SU->Node->getValueType(i);
178 if (VT != MVT::Other && VT != MVT::Flag)
184 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
185 /// the Available queue is the count reaches zero. Also update its cycle bound.
186 void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain,
188 // FIXME: the distance between two nodes is not always == the predecessor's
189 // latency. For example, the reader can very well read the register written
190 // by the predecessor later than the issue cycle. It also depends on the
191 // interrupt model (drain vs. freeze).
192 PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
195 PredSU->NumSuccsLeft--;
197 PredSU->NumChainSuccsLeft--;
200 if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
201 std::cerr << "*** List scheduling failed! ***\n";
203 std::cerr << " has been released too many times!\n";
208 if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
209 // EntryToken has to go last! Special case it here.
210 if (PredSU->Node->getOpcode() != ISD::EntryToken) {
211 PredSU->isAvailable = true;
212 AvailableQueue->push(PredSU);
217 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
218 /// count of its predecessors. If a predecessor pending count is zero, add it to
219 /// the Available queue.
220 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle) {
221 DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
222 DEBUG(SU->dump(&DAG));
223 SU->Cycle = CurCycle;
225 AvailableQueue->ScheduledNode(SU);
226 Sequence.push_back(SU);
228 // Bottom up: release predecessors
229 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
230 E = SU->Preds.end(); I != E; ++I)
231 ReleasePred(I->first, I->second, CurCycle);
232 SU->isScheduled = true;
236 /// isReady - True if node's lower cycle bound is less or equal to the current
237 /// scheduling cycle. Always true if all nodes have uniform latency 1.
238 static inline bool isReady(SUnit *SU, unsigned CurCycle) {
239 return SU->CycleBound <= CurCycle;
242 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
244 void ScheduleDAGRRList::ListScheduleBottomUp() {
245 unsigned CurCycle = 0;
246 // Add root to Available queue.
247 AvailableQueue->push(SUnitMap[DAG.getRoot().Val]);
249 // While Available queue is not empty, grab the node with the highest
250 // priority. If it is not ready put it back. Schedule the node.
251 std::vector<SUnit*> NotReady;
252 SUnit *CurNode = NULL;
253 while (!AvailableQueue->empty()) {
254 SUnit *CurNode = AvailableQueue->pop();
255 while (!isReady(CurNode, CurCycle)) {
256 NotReady.push_back(CurNode);
257 CurNode = AvailableQueue->pop();
260 // Add the nodes that aren't ready back onto the available list.
261 AvailableQueue->push_all(NotReady);
264 ScheduleNodeBottomUp(CurNode, CurCycle);
267 // Add entry node last
268 if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
269 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
270 Sequence.push_back(Entry);
273 // Reverse the order if it is bottom up.
274 std::reverse(Sequence.begin(), Sequence.end());
278 // Verify that all SUnits were scheduled.
279 bool AnyNotSched = false;
280 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
281 if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
283 std::cerr << "*** List scheduling failed! ***\n";
284 SUnits[i].dump(&DAG);
285 std::cerr << "has not been scheduled!\n";
289 assert(!AnyNotSched);
293 //===----------------------------------------------------------------------===//
294 // Top-Down Scheduling
295 //===----------------------------------------------------------------------===//
297 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
298 /// the PendingQueue if the count reaches zero.
299 void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain,
301 // FIXME: the distance between two nodes is not always == the predecessor's
302 // latency. For example, the reader can very well read the register written
303 // by the predecessor later than the issue cycle. It also depends on the
304 // interrupt model (drain vs. freeze).
305 SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency);
308 SuccSU->NumPredsLeft--;
310 SuccSU->NumChainPredsLeft--;
313 if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
314 std::cerr << "*** List scheduling failed! ***\n";
316 std::cerr << " has been released too many times!\n";
321 if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
322 SuccSU->isAvailable = true;
323 AvailableQueue->push(SuccSU);
328 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
329 /// count of its successors. If a successor pending count is zero, add it to
330 /// the Available queue.
331 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned& CurCycle) {
332 DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
333 DEBUG(SU->dump(&DAG));
334 SU->Cycle = CurCycle;
336 AvailableQueue->ScheduledNode(SU);
337 Sequence.push_back(SU);
339 // Top down: release successors
340 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(),
341 E = SU->Succs.end(); I != E; ++I)
342 ReleaseSucc(I->first, I->second, CurCycle);
343 SU->isScheduled = true;
347 void ScheduleDAGRRList::ListScheduleTopDown() {
348 unsigned CurCycle = 0;
349 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
351 // All leaves to Available queue.
352 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
353 // It is available if it has no predecessors.
354 if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
355 AvailableQueue->push(&SUnits[i]);
356 SUnits[i].isAvailable = true;
360 // Emit the entry node first.
361 ScheduleNodeTopDown(Entry, CurCycle);
363 // While Available queue is not empty, grab the node with the highest
364 // priority. If it is not ready put it back. Schedule the node.
365 std::vector<SUnit*> NotReady;
366 SUnit *CurNode = NULL;
367 while (!AvailableQueue->empty()) {
368 SUnit *CurNode = AvailableQueue->pop();
369 while (!isReady(CurNode, CurCycle)) {
370 NotReady.push_back(CurNode);
371 CurNode = AvailableQueue->pop();
374 // Add the nodes that aren't ready back onto the available list.
375 AvailableQueue->push_all(NotReady);
378 ScheduleNodeTopDown(CurNode, CurCycle);
383 // Verify that all SUnits were scheduled.
384 bool AnyNotSched = false;
385 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
386 if (!SUnits[i].isScheduled) {
388 std::cerr << "*** List scheduling failed! ***\n";
389 SUnits[i].dump(&DAG);
390 std::cerr << "has not been scheduled!\n";
394 assert(!AnyNotSched);
400 //===----------------------------------------------------------------------===//
401 // RegReductionPriorityQueue Implementation
402 //===----------------------------------------------------------------------===//
404 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
405 // to reduce register pressure.
409 class RegReductionPriorityQueue;
411 /// Sorting functions for the Available queue.
412 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
413 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
414 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
415 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
417 bool operator()(const SUnit* left, const SUnit* right) const;
420 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
421 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
422 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
423 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
425 bool operator()(const SUnit* left, const SUnit* right) const;
427 } // end anonymous namespace
431 class RegReductionPriorityQueue : public SchedulingPriorityQueue {
432 std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue;
435 RegReductionPriorityQueue() :
438 virtual void initNodes(const std::vector<SUnit> &sunits) {}
439 virtual void releaseState() {}
441 virtual int getSethiUllmanNumber(unsigned NodeNum) const {
445 bool empty() const { return Queue.empty(); }
447 void push(SUnit *U) {
450 void push_all(const std::vector<SUnit *> &Nodes) {
451 for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
452 Queue.push(Nodes[i]);
456 SUnit *V = Queue.top();
463 class BURegReductionPriorityQueue : public RegReductionPriorityQueue<SF> {
464 // SUnits - The SUnits for the current graph.
465 const std::vector<SUnit> *SUnits;
467 // SethiUllmanNumbers - The SethiUllman number for each node.
468 std::vector<int> SethiUllmanNumbers;
471 BURegReductionPriorityQueue() {}
473 void initNodes(const std::vector<SUnit> &sunits) {
475 // Add pseudo dependency edges for two-address nodes.
476 AddPseudoTwoAddrDeps();
477 // Calculate node priorities.
478 CalculatePriorities();
481 void releaseState() {
483 SethiUllmanNumbers.clear();
486 int getSethiUllmanNumber(unsigned NodeNum) const {
487 assert(NodeNum < SethiUllmanNumbers.size());
488 return SethiUllmanNumbers[NodeNum];
492 void AddPseudoTwoAddrDeps();
493 void CalculatePriorities();
494 int CalcNodePriority(const SUnit *SU);
499 class TDRegReductionPriorityQueue : public RegReductionPriorityQueue<SF> {
500 // SUnits - The SUnits for the current graph.
501 const std::vector<SUnit> *SUnits;
503 // SethiUllmanNumbers - The SethiUllman number for each node.
504 std::vector<int> SethiUllmanNumbers;
507 TDRegReductionPriorityQueue() {}
509 void initNodes(const std::vector<SUnit> &sunits) {
511 // Calculate node priorities.
512 CalculatePriorities();
515 void releaseState() {
517 SethiUllmanNumbers.clear();
520 int getSethiUllmanNumber(unsigned NodeNum) const {
521 assert(NodeNum < SethiUllmanNumbers.size());
522 return SethiUllmanNumbers[NodeNum];
526 void CalculatePriorities();
527 int CalcNodePriority(const SUnit *SU);
531 static bool isFloater(const SUnit *SU) {
532 if (SU->Node->isTargetOpcode()) {
533 if (SU->NumPreds == 0)
535 if (SU->NumPreds == 1) {
536 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
537 E = SU->Preds.end(); I != E; ++I) {
538 if (I->second) continue;
540 SUnit *PredSU = I->first;
541 unsigned Opc = PredSU->Node->getOpcode();
542 if (Opc != ISD::EntryToken && Opc != ISD::TokenFactor &&
543 Opc != ISD::CopyFromReg && Opc != ISD::CopyToReg)
552 static bool isSimpleFloaterUse(const SUnit *SU) {
554 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
555 E = SU->Preds.end(); I != E; ++I) {
556 if (I->second) continue;
559 if (!isFloater(I->first))
566 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
567 unsigned LeftNum = left->NodeNum;
568 unsigned RightNum = right->NodeNum;
569 bool LIsTarget = left->Node->isTargetOpcode();
570 bool RIsTarget = right->Node->isTargetOpcode();
571 int LPriority = SPQ->getSethiUllmanNumber(LeftNum);
572 int RPriority = SPQ->getSethiUllmanNumber(RightNum);
576 // Schedule floaters (e.g. load from some constant address) and those nodes
577 // with a single predecessor each first. They maintain / reduce register
579 if (isFloater(left) || isSimpleFloaterUse(left))
581 if (isFloater(right) || isSimpleFloaterUse(right))
584 // Special tie breaker: if two nodes share a operand, the one that use it
585 // as a def&use operand is preferred.
586 if (LIsTarget && RIsTarget) {
587 if (left->isTwoAddress && !right->isTwoAddress) {
588 SDNode *DUNode = left->Node->getOperand(0).Val;
589 if (DUNode->isOperand(right->Node))
592 if (!left->isTwoAddress && right->isTwoAddress) {
593 SDNode *DUNode = right->Node->getOperand(0).Val;
594 if (DUNode->isOperand(left->Node))
599 if (LPriority+LBonus < RPriority+RBonus)
601 else if (LPriority+LBonus == RPriority+RBonus)
602 if (left->Height > right->Height)
604 else if (left->Height == right->Height)
605 if (left->Depth < right->Depth)
607 else if (left->Depth == right->Depth)
608 if (left->CycleBound > right->CycleBound)
613 static inline bool isCopyFromLiveIn(const SUnit *SU) {
614 SDNode *N = SU->Node;
615 return N->getOpcode() == ISD::CopyFromReg &&
616 N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
619 // FIXME: This is probably too slow!
620 static void isReachable(SUnit *SU, SUnit *TargetSU,
621 std::set<SUnit *> &Visited, bool &Reached) {
623 if (SU == TargetSU) {
627 if (!Visited.insert(SU).second) return;
629 for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
630 E = SU->Preds.end(); I != E; ++I)
631 isReachable(I->first, TargetSU, Visited, Reached);
634 static bool isReachable(SUnit *SU, SUnit *TargetSU) {
635 std::set<SUnit *> Visited;
636 bool Reached = false;
637 isReachable(SU, TargetSU, Visited, Reached);
641 static SUnit *getDefUsePredecessor(SUnit *SU) {
642 SDNode *DU = SU->Node->getOperand(0).Val;
643 for (std::set<std::pair<SUnit*, bool> >::iterator
644 I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
645 if (I->second) continue; // ignore chain preds
646 SUnit *PredSU = I->first;
647 if (PredSU->Node == DU)
655 static bool canClobber(SUnit *SU, SUnit *Op) {
656 if (SU->isTwoAddress)
657 return Op == getDefUsePredecessor(SU);
661 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
662 /// it as a def&use operand. Add a pseudo control edge from it to the other
663 /// node (if it won't create a cycle) so the two-address one will be scheduled
664 /// first (lower in the schedule).
666 void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
667 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
668 SUnit *SU = (SUnit *)&((*SUnits)[i]);
669 SDNode *Node = SU->Node;
670 if (!Node->isTargetOpcode())
673 if (SU->isTwoAddress) {
674 SUnit *DUSU = getDefUsePredecessor(SU);
677 for (std::set<std::pair<SUnit*, bool> >::iterator I = DUSU->Succs.begin(),
678 E = DUSU->Succs.end(); I != E; ++I) {
679 if (I->second) continue;
680 SUnit *SuccSU = I->first;
682 (!canClobber(SuccSU, DUSU) ||
683 (!SU->isCommutable && SuccSU->isCommutable))){
684 if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) {
685 DEBUG(std::cerr << "Adding an edge from SU # " << SU->NodeNum
686 << " to SU #" << SuccSU->NodeNum << "\n");
687 if (SU->Preds.insert(std::make_pair(SuccSU, true)).second)
688 SU->NumChainPredsLeft++;
689 if (SuccSU->Succs.insert(std::make_pair(SU, true)).second)
690 SuccSU->NumChainSuccsLeft++;
698 /// CalcNodePriority - Priority is the Sethi Ullman number.
699 /// Smaller number is the higher priority.
701 int BURegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) {
702 int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
703 if (SethiUllmanNumber != 0)
704 return SethiUllmanNumber;
706 unsigned Opc = SU->Node->getOpcode();
707 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
708 SethiUllmanNumber = INT_MAX - 10;
709 else if (SU->NumSuccsLeft == 0)
710 // If SU does not have a use, i.e. it doesn't produce a value that would
711 // be consumed (e.g. store), then it terminates a chain of computation.
712 // Give it a small SethiUllman number so it will be scheduled right before its
713 // predecessors that it doesn't lengthen their live ranges.
714 SethiUllmanNumber = INT_MIN + 10;
715 // FIXME: remove this else if? It seems to reduce register spills but often
716 // ends up increasing runtime. Need to investigate.
717 else if (SU->NumPredsLeft == 0 &&
718 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
719 SethiUllmanNumber = INT_MAX - 10;
722 for (std::set<std::pair<SUnit*, bool> >::const_iterator
723 I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
724 if (I->second) continue; // ignore chain preds
725 SUnit *PredSU = I->first;
726 int PredSethiUllman = CalcNodePriority(PredSU);
727 if (PredSethiUllman > SethiUllmanNumber) {
728 SethiUllmanNumber = PredSethiUllman;
730 } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
734 SethiUllmanNumber += Extra;
737 return SethiUllmanNumber;
740 /// CalculatePriorities - Calculate priorities of all scheduling units.
742 void BURegReductionPriorityQueue<SF>::CalculatePriorities() {
743 SethiUllmanNumbers.assign(SUnits->size(), 0);
745 for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
746 CalcNodePriority(&(*SUnits)[i]);
749 static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) {
751 for (std::set<std::pair<SUnit*, bool> >::const_iterator
752 I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) {
753 SUnit *SuccSU = I->first;
754 for (std::set<std::pair<SUnit*, bool> >::const_iterator
755 II = SuccSU->Preds.begin(), EE = SuccSU->Preds.end(); II != EE; ++II) {
756 SUnit *PredSU = II->first;
757 if (!PredSU->isScheduled)
767 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
768 unsigned LeftNum = left->NodeNum;
769 unsigned RightNum = right->NodeNum;
770 int LPriority = SPQ->getSethiUllmanNumber(LeftNum);
771 int RPriority = SPQ->getSethiUllmanNumber(RightNum);
772 bool LIsTarget = left->Node->isTargetOpcode();
773 bool RIsTarget = right->Node->isTargetOpcode();
774 bool LIsFloater = LIsTarget && left->NumPreds == 0;
775 bool RIsFloater = RIsTarget && right->NumPreds == 0;
776 unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0;
777 unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0;
779 if (left->NumSuccs == 0 && right->NumSuccs != 0)
781 else if (left->NumSuccs != 0 && right->NumSuccs == 0)
784 // Special tie breaker: if two nodes share a operand, the one that use it
785 // as a def&use operand is preferred.
786 if (LIsTarget && RIsTarget) {
787 if (left->isTwoAddress && !right->isTwoAddress) {
788 SDNode *DUNode = left->Node->getOperand(0).Val;
789 if (DUNode->isOperand(right->Node))
792 if (!left->isTwoAddress && right->isTwoAddress) {
793 SDNode *DUNode = right->Node->getOperand(0).Val;
794 if (DUNode->isOperand(left->Node))
802 if (left->NumSuccs == 1)
804 if (right->NumSuccs == 1)
807 if (LPriority+LBonus < RPriority+RBonus)
809 else if (LPriority == RPriority)
810 if (left->Depth < right->Depth)
812 else if (left->Depth == right->Depth)
813 if (left->NumSuccsLeft > right->NumSuccsLeft)
815 else if (left->NumSuccsLeft == right->NumSuccsLeft)
816 if (left->CycleBound > right->CycleBound)
821 /// CalcNodePriority - Priority is the Sethi Ullman number.
822 /// Smaller number is the higher priority.
824 int TDRegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) {
825 int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
826 if (SethiUllmanNumber != 0)
827 return SethiUllmanNumber;
829 unsigned Opc = SU->Node->getOpcode();
830 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
831 SethiUllmanNumber = INT_MAX - 10;
832 else if (SU->NumSuccsLeft == 0)
833 // If SU does not have a use, i.e. it doesn't produce a value that would
834 // be consumed (e.g. store), then it terminates a chain of computation.
835 // Give it a small SethiUllman number so it will be scheduled right before its
836 // predecessors that it doesn't lengthen their live ranges.
837 SethiUllmanNumber = INT_MIN + 10;
838 else if (SU->NumPredsLeft == 0 &&
839 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
840 SethiUllmanNumber = 1;
843 for (std::set<std::pair<SUnit*, bool> >::const_iterator
844 I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
845 if (I->second) continue; // ignore chain preds
846 SUnit *PredSU = I->first;
847 int PredSethiUllman = CalcNodePriority(PredSU);
848 if (PredSethiUllman > SethiUllmanNumber) {
849 SethiUllmanNumber = PredSethiUllman;
851 } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
855 SethiUllmanNumber += Extra;
858 return SethiUllmanNumber;
861 /// CalculatePriorities - Calculate priorities of all scheduling units.
863 void TDRegReductionPriorityQueue<SF>::CalculatePriorities() {
864 SethiUllmanNumbers.assign(SUnits->size(), 0);
866 for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
867 CalcNodePriority(&(*SUnits)[i]);
870 //===----------------------------------------------------------------------===//
871 // Public Constructor Functions
872 //===----------------------------------------------------------------------===//
874 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
875 MachineBasicBlock *BB) {
876 return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), true,
877 new BURegReductionPriorityQueue<bu_ls_rr_sort>());
880 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAG &DAG,
881 MachineBasicBlock *BB) {
882 return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), false,
883 new TDRegReductionPriorityQueue<td_ls_rr_sort>());