1 //===---- ScheduleDAGList.cpp - Implement a list scheduler for isel DAG ---===//
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 a simple two pass scheduler. The first pass attempts to push
11 // backward any lengthy instructions and critical paths. The second pass packs
12 // instructions into semi-optimal time slots.
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "sched"
17 #include "llvm/CodeGen/ScheduleDAG.h"
18 #include "llvm/CodeGen/SelectionDAG.h"
19 #include "llvm/Target/TargetMachine.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/ADT/Statistic.h"
31 Statistic<> NumNoops ("scheduler", "Number of noops inserted");
32 Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
34 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or a
35 /// group of nodes flagged together.
37 SDNode *Node; // Representative node.
38 std::vector<SDNode*> FlaggedNodes; // All nodes flagged to Node.
39 std::set<SUnit*> Preds; // All real predecessors.
40 std::set<SUnit*> ChainPreds; // All chain predecessors.
41 std::set<SUnit*> Succs; // All real successors.
42 std::set<SUnit*> ChainSuccs; // All chain successors.
43 int NumPredsLeft; // # of preds not scheduled.
44 int NumSuccsLeft; // # of succs not scheduled.
45 int NumChainPredsLeft; // # of chain preds not scheduled.
46 int NumChainSuccsLeft; // # of chain succs not scheduled.
47 int Priority1; // Scheduling priority 1.
48 int Priority2; // Scheduling priority 2.
49 bool isTwoAddress; // Is a two-address instruction.
50 bool isDefNUseOperand; // Is a def&use operand.
51 unsigned Latency; // Node latency.
52 unsigned CycleBound; // Upper/lower cycle to be scheduled at.
53 unsigned Slot; // Cycle node is scheduled at.
57 : Node(node), NumPredsLeft(0), NumSuccsLeft(0),
58 NumChainPredsLeft(0), NumChainSuccsLeft(0),
59 Priority1(INT_MIN), Priority2(INT_MIN),
60 isTwoAddress(false), isDefNUseOperand(false),
61 Latency(0), CycleBound(0), Slot(0), Next(NULL) {}
63 void dump(const SelectionDAG *G, bool All=true) const;
66 void SUnit::dump(const SelectionDAG *G, bool All) const {
70 if (FlaggedNodes.size() != 0) {
71 for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
73 FlaggedNodes[i]->dump(G);
79 std::cerr << " # preds left : " << NumPredsLeft << "\n";
80 std::cerr << " # succs left : " << NumSuccsLeft << "\n";
81 std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n";
82 std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n";
83 std::cerr << " Latency : " << Latency << "\n";
84 std::cerr << " Priority : " << Priority1 << " , "
87 if (Preds.size() != 0) {
88 std::cerr << " Predecessors:\n";
89 for (std::set<SUnit*>::const_iterator I = Preds.begin(),
90 E = Preds.end(); I != E; ++I) {
95 if (ChainPreds.size() != 0) {
96 std::cerr << " Chained Preds:\n";
97 for (std::set<SUnit*>::const_iterator I = ChainPreds.begin(),
98 E = ChainPreds.end(); I != E; ++I) {
100 (*I)->dump(G, false);
103 if (Succs.size() != 0) {
104 std::cerr << " Successors:\n";
105 for (std::set<SUnit*>::const_iterator I = Succs.begin(),
106 E = Succs.end(); I != E; ++I) {
108 (*I)->dump(G, false);
111 if (ChainSuccs.size() != 0) {
112 std::cerr << " Chained succs:\n";
113 for (std::set<SUnit*>::const_iterator I = ChainSuccs.begin(),
114 E = ChainSuccs.end(); I != E; ++I) {
116 (*I)->dump(G, false);
122 /// Sorting functions for the Available queue.
123 struct ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
124 bool operator()(const SUnit* left, const SUnit* right) const {
125 bool LFloater = (left ->Preds.size() == 0);
126 bool RFloater = (right->Preds.size() == 0);
127 int LBonus = (int)left ->isDefNUseOperand;
128 int RBonus = (int)right->isDefNUseOperand;
130 // Special tie breaker: if two nodes share a operand, the one that
131 // use it as a def&use operand is preferred.
132 if (left->isTwoAddress && !right->isTwoAddress) {
133 SDNode *DUNode = left->Node->getOperand(0).Val;
134 if (DUNode->isOperand(right->Node))
137 if (!left->isTwoAddress && right->isTwoAddress) {
138 SDNode *DUNode = right->Node->getOperand(0).Val;
139 if (DUNode->isOperand(left->Node))
143 int LPriority1 = left ->Priority1 - LBonus;
144 int RPriority1 = right->Priority1 - RBonus;
145 int LPriority2 = left ->Priority2 + LBonus;
146 int RPriority2 = right->Priority2 + RBonus;
148 // Favor floaters (i.e. node with no non-passive predecessors):
150 if (!LFloater && RFloater)
152 else if (LFloater == RFloater)
153 if (LPriority1 > RPriority1)
155 else if (LPriority1 == RPriority1)
156 if (LPriority2 < RPriority2)
158 else if (LPriority1 == RPriority1)
159 if (left->CycleBound > right->CycleBound)
167 /// HazardRecognizer - This determines whether or not an instruction can be
168 /// issued this cycle, and whether or not a noop needs to be inserted to handle
171 class HazardRecognizer {
173 virtual ~HazardRecognizer() {}
176 NoHazard, // This instruction can be emitted at this cycle.
177 Hazard, // This instruction can't be emitted at this cycle.
178 NoopHazard, // This instruction can't be emitted, and needs noops.
181 /// getHazardType - Return the hazard type of emitting this node. There are
182 /// three possible results. Either:
183 /// * NoHazard: it is legal to issue this instruction on this cycle.
184 /// * Hazard: issuing this instruction would stall the machine. If some
185 /// other instruction is available, issue it first.
186 /// * NoopHazard: issuing this instruction would break the program. If
187 /// some other instruction can be issued, do so, otherwise issue a noop.
188 virtual HazardType getHazardType(SDNode *Node) {
192 /// EmitInstruction - This callback is invoked when an instruction is
193 /// emitted, to advance the hazard state.
194 virtual void EmitInstruction(SDNode *Node) {
197 /// AdvanceCycle - This callback is invoked when no instructions can be
198 /// issued on this cycle without a hazard. This should increment the
199 /// internal state of the hazard recognizer so that previously "Hazard"
200 /// instructions will now not be hazards.
201 virtual void AdvanceCycle() {
204 /// EmitNoop - This callback is invoked when a noop was added to the
205 /// instruction stream.
206 virtual void EmitNoop() {
212 /// ScheduleDAGList - List scheduler.
213 class ScheduleDAGList : public ScheduleDAG {
215 // SDNode to SUnit mapping (many to one).
216 std::map<SDNode*, SUnit*> SUnitMap;
217 // The schedule. Null SUnit*'s represend noop instructions.
218 std::vector<SUnit*> Sequence;
219 // Current scheduling cycle.
221 // First and last SUnit created.
222 SUnit *HeadSUnit, *TailSUnit;
224 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
228 /// HazardRec - The hazard recognizer to use.
229 HazardRecognizer *HazardRec;
231 typedef std::priority_queue<SUnit*, std::vector<SUnit*>, ls_rr_sort>
235 ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
236 const TargetMachine &tm, bool isbottomup,
237 HazardRecognizer *HR = 0)
238 : ScheduleDAG(listSchedulingBURR, dag, bb, tm),
239 CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL), isBottomUp(isbottomup) {
240 if (HR == 0) HR = new HazardRecognizer();
245 SUnit *SU = HeadSUnit;
247 SUnit *NextSU = SU->Next;
260 SUnit *NewSUnit(SDNode *N);
261 void ReleasePred(AvailableQueueTy &Avail,SUnit *PredSU, bool isChain = false);
262 void ReleaseSucc(AvailableQueueTy &Avail,SUnit *SuccSU, bool isChain = false);
263 void ScheduleNodeBottomUp(AvailableQueueTy &Avail, SUnit *SU);
264 void ScheduleNodeTopDown(AvailableQueueTy &Avail, SUnit *SU);
265 int CalcNodePriority(SUnit *SU);
266 void CalculatePriorities();
267 void ListScheduleTopDown();
268 void ListScheduleBottomUp();
269 void BuildSchedUnits();
275 /// NewSUnit - Creates a new SUnit and return a ptr to it.
276 SUnit *ScheduleDAGList::NewSUnit(SDNode *N) {
277 SUnit *CurrSUnit = new SUnit(N);
279 if (HeadSUnit == NULL)
280 HeadSUnit = CurrSUnit;
281 if (TailSUnit != NULL)
282 TailSUnit->Next = CurrSUnit;
283 TailSUnit = CurrSUnit;
288 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
289 /// the Available queue is the count reaches zero. Also update its cycle bound.
290 void ScheduleDAGList::ReleasePred(AvailableQueueTy &Available,
291 SUnit *PredSU, bool isChain) {
292 // FIXME: the distance between two nodes is not always == the predecessor's
293 // latency. For example, the reader can very well read the register written
294 // by the predecessor later than the issue cycle. It also depends on the
295 // interrupt model (drain vs. freeze).
296 PredSU->CycleBound = std::max(PredSU->CycleBound, CurrCycle + PredSU->Latency);
299 PredSU->NumSuccsLeft--;
302 PredSU->NumChainSuccsLeft--;
305 if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
306 std::cerr << "*** List scheduling failed! ***\n";
308 std::cerr << " has been released too many times!\n";
313 if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
314 // EntryToken has to go last! Special case it here.
315 if (PredSU->Node->getOpcode() != ISD::EntryToken)
316 Available.push(PredSU);
320 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
321 /// the Available queue is the count reaches zero. Also update its cycle bound.
322 void ScheduleDAGList::ReleaseSucc(AvailableQueueTy &Available,
323 SUnit *SuccSU, bool isChain) {
324 // FIXME: the distance between two nodes is not always == the predecessor's
325 // latency. For example, the reader can very well read the register written
326 // by the predecessor later than the issue cycle. It also depends on the
327 // interrupt model (drain vs. freeze).
328 SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurrCycle + SuccSU->Latency);
331 SuccSU->NumPredsLeft--;
332 SuccSU->Priority1++; // FIXME: ??
334 SuccSU->NumChainPredsLeft--;
337 if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
338 std::cerr << "*** List scheduling failed! ***\n";
340 std::cerr << " has been released too many times!\n";
345 if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0)
346 Available.push(SuccSU);
349 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
350 /// count of its predecessors. If a predecessor pending count is zero, add it to
351 /// the Available queue.
352 void ScheduleDAGList::ScheduleNodeBottomUp(AvailableQueueTy &Available,
354 DEBUG(std::cerr << "*** Scheduling: ");
355 DEBUG(SU->dump(&DAG, false));
357 Sequence.push_back(SU);
358 SU->Slot = CurrCycle;
360 // Bottom up: release predecessors
361 for (std::set<SUnit*>::iterator I1 = SU->Preds.begin(),
362 E1 = SU->Preds.end(); I1 != E1; ++I1) {
363 ReleasePred(Available, *I1);
367 for (std::set<SUnit*>::iterator I2 = SU->ChainPreds.begin(),
368 E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
369 ReleasePred(Available, *I2, true);
374 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
375 /// count of its successors. If a successor pending count is zero, add it to
376 /// the Available queue.
377 void ScheduleDAGList::ScheduleNodeTopDown(AvailableQueueTy &Available,
379 DEBUG(std::cerr << "*** Scheduling: ");
380 DEBUG(SU->dump(&DAG, false));
382 Sequence.push_back(SU);
383 SU->Slot = CurrCycle;
385 // Bottom up: release successors.
386 for (std::set<SUnit*>::iterator I1 = SU->Succs.begin(),
387 E1 = SU->Succs.end(); I1 != E1; ++I1) {
388 ReleaseSucc(Available, *I1);
390 SU->Priority1--; // FIXME: what is this??
392 for (std::set<SUnit*>::iterator I2 = SU->ChainSuccs.begin(),
393 E2 = SU->ChainSuccs.end(); I2 != E2; ++I2)
394 ReleaseSucc(Available, *I2, true);
399 /// isReady - True if node's lower cycle bound is less or equal to the current
400 /// scheduling cycle. Always true if all nodes have uniform latency 1.
401 static inline bool isReady(SUnit *SU, unsigned CurrCycle) {
402 return SU->CycleBound <= CurrCycle;
405 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
407 void ScheduleDAGList::ListScheduleBottomUp() {
409 AvailableQueueTy Available;
411 // Add root to Available queue.
412 Available.push(SUnitMap[DAG.getRoot().Val]);
414 // While Available queue is not empty, grab the node with the highest
415 // priority. If it is not ready put it back. Schedule the node.
416 std::vector<SUnit*> NotReady;
417 while (!Available.empty()) {
418 SUnit *CurrNode = Available.top();
421 while (!isReady(CurrNode, CurrCycle)) {
422 NotReady.push_back(CurrNode);
423 CurrNode = Available.top();
427 // Add the nodes that aren't ready back onto the available list.
428 while (!NotReady.empty()) {
429 Available.push(NotReady.back());
433 ScheduleNodeBottomUp(Available, CurrNode);
436 // Add entry node last
437 if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
438 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
439 Entry->Slot = CurrCycle;
440 Sequence.push_back(Entry);
443 // Reverse the order if it is bottom up.
444 std::reverse(Sequence.begin(), Sequence.end());
448 // Verify that all SUnits were scheduled.
449 bool AnyNotSched = false;
450 for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
451 if (SU->NumSuccsLeft != 0 || SU->NumChainSuccsLeft != 0) {
453 std::cerr << "*** List scheduling failed! ***\n";
455 std::cerr << "has not been scheduled!\n";
459 assert(!AnyNotSched);
463 /// ListScheduleTopDown - The main loop of list scheduling for top-down
465 void ScheduleDAGList::ListScheduleTopDown() {
467 AvailableQueueTy Available;
469 // Emit the entry node first.
470 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
471 ScheduleNodeTopDown(Available, Entry);
472 HazardRec->EmitInstruction(Entry->Node);
474 // All leaves to Available queue.
475 for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
476 // It is available if it has no predecessors.
477 if ((SU->Preds.size() + SU->ChainPreds.size()) == 0 && SU != Entry)
481 // While Available queue is not empty, grab the node with the highest
482 // priority. If it is not ready put it back. Schedule the node.
483 std::vector<SUnit*> NotReady;
484 while (!Available.empty()) {
485 SUnit *FoundNode = 0;
487 bool HasNoopHazards = false;
489 SUnit *CurrNode = Available.top();
491 HazardRecognizer::HazardType HT =
492 HazardRec->getHazardType(CurrNode->Node);
493 if (HT == HazardRecognizer::NoHazard) {
494 FoundNode = CurrNode;
498 // Remember if this is a noop hazard.
499 HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
501 NotReady.push_back(CurrNode);
502 } while (!Available.empty());
504 // Add the nodes that aren't ready back onto the available list.
505 while (!NotReady.empty()) {
506 Available.push(NotReady.back());
510 // If we found a node to schedule, do it now.
512 ScheduleNodeTopDown(Available, FoundNode);
513 HazardRec->EmitInstruction(FoundNode->Node);
514 } else if (!HasNoopHazards) {
515 // Otherwise, we have a pipeline stall, but no other problem, just advance
516 // the current cycle and try again.
517 DEBUG(std::cerr << "*** Advancing cycle, no work to do");
518 HazardRec->AdvanceCycle();
521 // Otherwise, we have no instructions to issue and we have instructions
522 // that will fault if we don't do this right. This is the case for
523 // processors without pipeline interlocks and other cases.
524 DEBUG(std::cerr << "*** Emitting noop");
525 HazardRec->EmitNoop();
526 Sequence.push_back(0); // NULL SUnit -> noop
532 // Verify that all SUnits were scheduled.
533 bool AnyNotSched = false;
534 for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
535 if (SU->NumPredsLeft != 0 || SU->NumChainPredsLeft != 0) {
537 std::cerr << "*** List scheduling failed! ***\n";
539 std::cerr << "has not been scheduled!\n";
543 assert(!AnyNotSched);
548 /// CalcNodePriority - Priority1 is just the number of live range genned -
549 /// number of live range killed. Priority2 is the Sethi Ullman number. It
550 /// returns Priority2 since it is calculated recursively.
551 /// Smaller number is the higher priority for Priority2. Reverse is true for
553 int ScheduleDAGList::CalcNodePriority(SUnit *SU) {
554 if (SU->Priority2 != INT_MIN)
555 return SU->Priority2;
557 SU->Priority1 = SU->NumPredsLeft - SU->NumSuccsLeft;
559 if (SU->Preds.size() == 0) {
563 for (std::set<SUnit*>::iterator I = SU->Preds.begin(),
564 E = SU->Preds.end(); I != E; ++I) {
566 int PredPriority = CalcNodePriority(PredSU);
567 if (PredPriority > SU->Priority2) {
568 SU->Priority2 = PredPriority;
570 } else if (PredPriority == SU->Priority2)
574 if (SU->Node->getOpcode() != ISD::TokenFactor)
575 SU->Priority2 += Extra;
577 SU->Priority2 = (Extra == 1) ? 0 : Extra-1;
580 return SU->Priority2;
583 /// CalculatePriorities - Calculate priorities of all scheduling units.
584 void ScheduleDAGList::CalculatePriorities() {
585 for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
586 // FIXME: assumes uniform latency for now.
588 (void)CalcNodePriority(SU);
589 DEBUG(SU->dump(&DAG));
590 DEBUG(std::cerr << "\n");
594 void ScheduleDAGList::BuildSchedUnits() {
595 // Pass 1: create the SUnit's.
596 for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
597 NodeInfo *NI = &Info[i];
598 SDNode *N = NI->Node;
599 if (isPassiveNode(N))
603 if (NI->isInGroup()) {
604 if (NI != NI->Group->getBottom()) // Bottom up, so only look at bottom
605 continue; // node of the NodeGroup
608 // Find the flagged nodes.
609 SDOperand FlagOp = N->getOperand(N->getNumOperands() - 1);
610 SDNode *Flag = FlagOp.Val;
611 unsigned ResNo = FlagOp.ResNo;
612 while (Flag->getValueType(ResNo) == MVT::Flag) {
613 NodeInfo *FNI = getNI(Flag);
614 assert(FNI->Group == NI->Group);
615 SU->FlaggedNodes.insert(SU->FlaggedNodes.begin(), Flag);
618 FlagOp = Flag->getOperand(Flag->getNumOperands() - 1);
620 ResNo = FlagOp.ResNo;
628 // Pass 2: add the preds, succs, etc.
629 for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
630 SDNode *N = SU->Node;
631 NodeInfo *NI = getNI(N);
633 if (N->isTargetOpcode() && TII->isTwoAddrInstr(N->getTargetOpcode()))
634 SU->isTwoAddress = true;
636 if (NI->isInGroup()) {
637 // Find all predecessors (of the group).
638 NodeGroupOpIterator NGOI(NI);
639 while (!NGOI.isEnd()) {
640 SDOperand Op = NGOI.next();
641 SDNode *OpN = Op.Val;
642 MVT::ValueType VT = OpN->getValueType(Op.ResNo);
643 NodeInfo *OpNI = getNI(OpN);
644 if (OpNI->Group != NI->Group && !isPassiveNode(OpN)) {
645 assert(VT != MVT::Flag);
646 SUnit *OpSU = SUnitMap[OpN];
647 if (VT == MVT::Other) {
648 if (SU->ChainPreds.insert(OpSU).second)
649 SU->NumChainPredsLeft++;
650 if (OpSU->ChainSuccs.insert(SU).second)
651 OpSU->NumChainSuccsLeft++;
653 if (SU->Preds.insert(OpSU).second)
655 if (OpSU->Succs.insert(SU).second)
656 OpSU->NumSuccsLeft++;
661 // Find node predecessors.
662 for (unsigned j = 0, e = N->getNumOperands(); j != e; j++) {
663 SDOperand Op = N->getOperand(j);
664 SDNode *OpN = Op.Val;
665 MVT::ValueType VT = OpN->getValueType(Op.ResNo);
666 if (!isPassiveNode(OpN)) {
667 assert(VT != MVT::Flag);
668 SUnit *OpSU = SUnitMap[OpN];
669 if (VT == MVT::Other) {
670 if (SU->ChainPreds.insert(OpSU).second)
671 SU->NumChainPredsLeft++;
672 if (OpSU->ChainSuccs.insert(SU).second)
673 OpSU->NumChainSuccsLeft++;
675 if (SU->Preds.insert(OpSU).second)
677 if (OpSU->Succs.insert(SU).second)
678 OpSU->NumSuccsLeft++;
679 if (j == 0 && SU->isTwoAddress)
680 OpSU->isDefNUseOperand = true;
688 /// EmitSchedule - Emit the machine code in scheduled order.
689 void ScheduleDAGList::EmitSchedule() {
690 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
691 if (SUnit *SU = Sequence[i]) {
692 for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++) {
693 SDNode *N = SU->FlaggedNodes[j];
696 EmitNode(getNI(SU->Node));
698 // Null SUnit* is a noop.
704 /// dump - dump the schedule.
705 void ScheduleDAGList::dump() const {
706 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
707 if (SUnit *SU = Sequence[i])
708 SU->dump(&DAG, false);
710 std::cerr << "**** NOOP ****\n";
714 /// Schedule - Schedule the DAG using list scheduling.
715 /// FIXME: Right now it only supports the burr (bottom up register reducing)
717 void ScheduleDAGList::Schedule() {
718 DEBUG(std::cerr << "********** List Scheduling **********\n");
720 // Build scheduling units.
723 // Calculate node prirorities.
724 CalculatePriorities();
726 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
728 ListScheduleBottomUp();
730 ListScheduleTopDown();
732 DEBUG(std::cerr << "*** Final schedule ***\n");
734 DEBUG(std::cerr << "\n");
736 // Emit in scheduled order
740 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
741 MachineBasicBlock *BB) {
742 return new ScheduleDAGList(DAG, BB, DAG.getTarget(), true);
745 /// G5HazardRecognizer - A hazard recognizer for the PowerPC G5 processor.
746 /// FIXME: Move to the PowerPC backend.
747 class G5HazardRecognizer : public HazardRecognizer {
748 // Totally bogus hazard recognizer, used to test noop insertion. This requires
749 // a noop between copyfromreg's.
750 unsigned EmittedCopyFromReg;
752 G5HazardRecognizer() {
753 EmittedCopyFromReg = 0;
756 virtual HazardType getHazardType(SDNode *Node) {
757 if (Node->getOpcode() == ISD::CopyFromReg && EmittedCopyFromReg)
762 /// EmitInstruction - This callback is invoked when an instruction is
763 /// emitted, to advance the hazard state.
764 virtual void EmitInstruction(SDNode *Node) {
765 if (Node->getOpcode() == ISD::CopyFromReg) {
766 EmittedCopyFromReg = 5;
767 } else if (EmittedCopyFromReg) {
768 --EmittedCopyFromReg;
772 /// AdvanceCycle - This callback is invoked when no instructions can be
773 /// issued on this cycle without a hazard. This should increment the
774 /// internal state of the hazard recognizer so that previously "Hazard"
775 /// instructions will now not be hazards.
776 virtual void AdvanceCycle() {
779 /// EmitNoop - This callback is invoked when a noop was added to the
780 /// instruction stream.
781 virtual void EmitNoop() {
782 --EmittedCopyFromReg;
787 /// createTDG5ListDAGScheduler - This creates a top-down list scheduler for
788 /// the PowerPC G5. FIXME: pull the priority function out into the PPC
790 ScheduleDAG* llvm::createTDG5ListDAGScheduler(SelectionDAG &DAG,
791 MachineBasicBlock *BB) {
792 return new ScheduleDAGList(DAG, BB, DAG.getTarget(), false,
793 new G5HazardRecognizer());