1 //===----- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // 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 "pre-RA-sched"
19 #include "ScheduleDAGSDNodes.h"
20 #include "llvm/InlineAsm.h"
21 #include "llvm/CodeGen/SchedulerRegistry.h"
22 #include "llvm/CodeGen/SelectionDAGISel.h"
23 #include "llvm/Target/TargetRegisterInfo.h"
24 #include "llvm/Target/TargetData.h"
25 #include "llvm/Target/TargetMachine.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetLowering.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/ErrorHandling.h"
33 #include "llvm/Support/raw_ostream.h"
37 STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
38 STATISTIC(NumUnfolds, "Number of nodes unfolded");
39 STATISTIC(NumDups, "Number of duplicated nodes");
40 STATISTIC(NumPRCopies, "Number of physical register copies");
42 static RegisterScheduler
43 burrListDAGScheduler("list-burr",
44 "Bottom-up register reduction list scheduling",
45 createBURRListDAGScheduler);
46 static RegisterScheduler
47 tdrListrDAGScheduler("list-tdrr",
48 "Top-down register reduction list scheduling",
49 createTDRRListDAGScheduler);
50 static RegisterScheduler
51 sourceListDAGScheduler("source",
52 "Similar to list-burr but schedules in source "
53 "order when possible",
54 createSourceListDAGScheduler);
56 static RegisterScheduler
57 hybridListDAGScheduler("list-hybrid",
58 "Bottom-up rr list scheduling which avoid stalls for "
59 "long latency instructions",
60 createHybridListDAGScheduler);
63 //===----------------------------------------------------------------------===//
64 /// ScheduleDAGRRList - The actual register reduction list scheduler
65 /// implementation. This supports both top-down and bottom-up scheduling.
67 class ScheduleDAGRRList : public ScheduleDAGSDNodes {
69 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
73 /// NeedLatency - True if the scheduler will make use of latency information.
77 /// AvailableQueue - The priority queue to use for the available SUnits.
78 SchedulingPriorityQueue *AvailableQueue;
80 /// LiveRegDefs - A set of physical registers and their definition
81 /// that are "live". These nodes must be scheduled before any other nodes that
82 /// modifies the registers can be scheduled.
84 std::vector<SUnit*> LiveRegDefs;
85 std::vector<unsigned> LiveRegCycles;
87 /// Topo - A topological ordering for SUnits which permits fast IsReachable
88 /// and similar queries.
89 ScheduleDAGTopologicalSort Topo;
92 ScheduleDAGRRList(MachineFunction &mf,
93 bool isbottomup, bool needlatency,
94 SchedulingPriorityQueue *availqueue)
95 : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup), NeedLatency(needlatency),
96 AvailableQueue(availqueue), Topo(SUnits) {
99 ~ScheduleDAGRRList() {
100 delete AvailableQueue;
105 /// IsReachable - Checks if SU is reachable from TargetSU.
106 bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
107 return Topo.IsReachable(SU, TargetSU);
110 /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
112 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
113 return Topo.WillCreateCycle(SU, TargetSU);
116 /// AddPred - adds a predecessor edge to SUnit SU.
117 /// This returns true if this is a new predecessor.
118 /// Updates the topological ordering if required.
119 void AddPred(SUnit *SU, const SDep &D) {
120 Topo.AddPred(SU, D.getSUnit());
124 /// RemovePred - removes a predecessor edge from SUnit SU.
125 /// This returns true if an edge was removed.
126 /// Updates the topological ordering if required.
127 void RemovePred(SUnit *SU, const SDep &D) {
128 Topo.RemovePred(SU, D.getSUnit());
133 void ReleasePred(SUnit *SU, const SDep *PredEdge);
134 void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
135 void ReleaseSucc(SUnit *SU, const SDep *SuccEdge);
136 void ReleaseSuccessors(SUnit *SU);
137 void CapturePred(SDep *PredEdge);
138 void ScheduleNodeBottomUp(SUnit*, unsigned);
139 void ScheduleNodeTopDown(SUnit*, unsigned);
140 void UnscheduleNodeBottomUp(SUnit*);
141 void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
142 SUnit *CopyAndMoveSuccessors(SUnit*);
143 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
144 const TargetRegisterClass*,
145 const TargetRegisterClass*,
146 SmallVector<SUnit*, 2>&);
147 bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
148 void ListScheduleTopDown();
149 void ListScheduleBottomUp();
152 /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
153 /// Updates the topological ordering if required.
154 SUnit *CreateNewSUnit(SDNode *N) {
155 unsigned NumSUnits = SUnits.size();
156 SUnit *NewNode = NewSUnit(N);
157 // Update the topological ordering.
158 if (NewNode->NodeNum >= NumSUnits)
159 Topo.InitDAGTopologicalSorting();
163 /// CreateClone - Creates a new SUnit from an existing one.
164 /// Updates the topological ordering if required.
165 SUnit *CreateClone(SUnit *N) {
166 unsigned NumSUnits = SUnits.size();
167 SUnit *NewNode = Clone(N);
168 // Update the topological ordering.
169 if (NewNode->NodeNum >= NumSUnits)
170 Topo.InitDAGTopologicalSorting();
174 /// ForceUnitLatencies - Register-pressure-reducing scheduling doesn't
175 /// need actual latency information but the hybrid scheduler does.
176 bool ForceUnitLatencies() const {
180 } // end anonymous namespace
183 /// Schedule - Schedule the DAG using list scheduling.
184 void ScheduleDAGRRList::Schedule() {
186 << "********** List Scheduling BB#" << BB->getNumber()
190 LiveRegDefs.resize(TRI->getNumRegs(), NULL);
191 LiveRegCycles.resize(TRI->getNumRegs(), 0);
193 // Build the scheduling graph.
194 BuildSchedGraph(NULL);
196 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
197 SUnits[su].dumpAll(this));
198 Topo.InitDAGTopologicalSorting();
200 AvailableQueue->initNodes(SUnits);
202 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
204 ListScheduleBottomUp();
206 ListScheduleTopDown();
208 AvailableQueue->releaseState();
211 //===----------------------------------------------------------------------===//
212 // Bottom-Up Scheduling
213 //===----------------------------------------------------------------------===//
215 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
216 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
217 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
218 SUnit *PredSU = PredEdge->getSUnit();
221 if (PredSU->NumSuccsLeft == 0) {
222 dbgs() << "*** Scheduling failed! ***\n";
224 dbgs() << " has been released too many times!\n";
228 --PredSU->NumSuccsLeft;
230 if (!ForceUnitLatencies()) {
231 // Updating predecessor's height. This is now the cycle when the
232 // predecessor can be scheduled without causing a pipeline stall.
233 PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency());
236 // If all the node's successors are scheduled, this node is ready
237 // to be scheduled. Ignore the special EntrySU node.
238 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
239 PredSU->isAvailable = true;
240 AvailableQueue->push(PredSU);
244 void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
245 // Bottom up: release predecessors
246 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
248 ReleasePred(SU, &*I);
249 if (I->isAssignedRegDep()) {
250 // This is a physical register dependency and it's impossible or
251 // expensive to copy the register. Make sure nothing that can
252 // clobber the register is scheduled between the predecessor and
254 if (!LiveRegDefs[I->getReg()]) {
256 LiveRegDefs[I->getReg()] = I->getSUnit();
257 LiveRegCycles[I->getReg()] = CurCycle;
263 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
264 /// count of its predecessors. If a predecessor pending count is zero, add it to
265 /// the Available queue.
266 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
267 DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: ");
268 DEBUG(SU->dump(this));
271 if (CurCycle < SU->getHeight())
272 DEBUG(dbgs() << " Height [" << SU->getHeight() << "] pipeline stall!\n");
275 // FIXME: Handle noop hazard.
276 SU->setHeightToAtLeast(CurCycle);
277 Sequence.push_back(SU);
279 AvailableQueue->ScheduledNode(SU);
281 ReleasePredecessors(SU, CurCycle);
283 // Release all the implicit physical register defs that are live.
284 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
286 if (I->isAssignedRegDep()) {
287 if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) {
288 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
289 assert(LiveRegDefs[I->getReg()] == SU &&
290 "Physical register dependency violated?");
292 LiveRegDefs[I->getReg()] = NULL;
293 LiveRegCycles[I->getReg()] = 0;
298 SU->isScheduled = true;
301 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
302 /// unscheduled, incrcease the succ left count of its predecessors. Remove
303 /// them from AvailableQueue if necessary.
304 void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
305 SUnit *PredSU = PredEdge->getSUnit();
306 if (PredSU->isAvailable) {
307 PredSU->isAvailable = false;
308 if (!PredSU->isPending)
309 AvailableQueue->remove(PredSU);
312 assert(PredSU->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
313 ++PredSU->NumSuccsLeft;
316 /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
317 /// its predecessor states to reflect the change.
318 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
319 DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
320 DEBUG(SU->dump(this));
322 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
325 if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]){
326 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
327 assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
328 "Physical register dependency violated?");
330 LiveRegDefs[I->getReg()] = NULL;
331 LiveRegCycles[I->getReg()] = 0;
335 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
337 if (I->isAssignedRegDep()) {
338 if (!LiveRegDefs[I->getReg()]) {
339 LiveRegDefs[I->getReg()] = SU;
342 if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()])
343 LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight();
347 SU->setHeightDirty();
348 SU->isScheduled = false;
349 SU->isAvailable = true;
350 AvailableQueue->push(SU);
351 AvailableQueue->UnscheduledNode(SU);
354 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
355 /// BTCycle in order to schedule a specific node.
356 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
357 unsigned &CurCycle) {
359 while (CurCycle > BtCycle) {
360 OldSU = Sequence.back();
362 if (SU->isSucc(OldSU))
363 // Don't try to remove SU from AvailableQueue.
364 SU->isAvailable = false;
365 UnscheduleNodeBottomUp(OldSU);
367 AvailableQueue->setCurCycle(CurCycle);
370 assert(!SU->isSucc(OldSU) && "Something is wrong!");
375 static bool isOperandOf(const SUnit *SU, SDNode *N) {
376 for (const SDNode *SUNode = SU->getNode(); SUNode;
377 SUNode = SUNode->getFlaggedNode()) {
378 if (SUNode->isOperandOf(N))
384 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
385 /// successors to the newly created node.
386 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
387 if (SU->getNode()->getFlaggedNode())
390 SDNode *N = SU->getNode();
395 bool TryUnfold = false;
396 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
397 EVT VT = N->getValueType(i);
400 else if (VT == MVT::Other)
403 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
404 const SDValue &Op = N->getOperand(i);
405 EVT VT = Op.getNode()->getValueType(Op.getResNo());
411 SmallVector<SDNode*, 2> NewNodes;
412 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
415 DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n");
416 assert(NewNodes.size() == 2 && "Expected a load folding node!");
419 SDNode *LoadNode = NewNodes[0];
420 unsigned NumVals = N->getNumValues();
421 unsigned OldNumVals = SU->getNode()->getNumValues();
422 for (unsigned i = 0; i != NumVals; ++i)
423 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
424 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
425 SDValue(LoadNode, 1));
427 // LoadNode may already exist. This can happen when there is another
428 // load from the same location and producing the same type of value
429 // but it has different alignment or volatileness.
430 bool isNewLoad = true;
432 if (LoadNode->getNodeId() != -1) {
433 LoadSU = &SUnits[LoadNode->getNodeId()];
436 LoadSU = CreateNewSUnit(LoadNode);
437 LoadNode->setNodeId(LoadSU->NodeNum);
438 ComputeLatency(LoadSU);
441 SUnit *NewSU = CreateNewSUnit(N);
442 assert(N->getNodeId() == -1 && "Node already inserted!");
443 N->setNodeId(NewSU->NodeNum);
445 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
446 for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
447 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
448 NewSU->isTwoAddress = true;
452 if (TID.isCommutable())
453 NewSU->isCommutable = true;
454 ComputeLatency(NewSU);
456 // Record all the edges to and from the old SU, by category.
457 SmallVector<SDep, 4> ChainPreds;
458 SmallVector<SDep, 4> ChainSuccs;
459 SmallVector<SDep, 4> LoadPreds;
460 SmallVector<SDep, 4> NodePreds;
461 SmallVector<SDep, 4> NodeSuccs;
462 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
465 ChainPreds.push_back(*I);
466 else if (isOperandOf(I->getSUnit(), LoadNode))
467 LoadPreds.push_back(*I);
469 NodePreds.push_back(*I);
471 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
474 ChainSuccs.push_back(*I);
476 NodeSuccs.push_back(*I);
479 // Now assign edges to the newly-created nodes.
480 for (unsigned i = 0, e = ChainPreds.size(); i != e; ++i) {
481 const SDep &Pred = ChainPreds[i];
482 RemovePred(SU, Pred);
484 AddPred(LoadSU, Pred);
486 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
487 const SDep &Pred = LoadPreds[i];
488 RemovePred(SU, Pred);
490 AddPred(LoadSU, Pred);
492 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
493 const SDep &Pred = NodePreds[i];
494 RemovePred(SU, Pred);
495 AddPred(NewSU, Pred);
497 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
498 SDep D = NodeSuccs[i];
499 SUnit *SuccDep = D.getSUnit();
501 RemovePred(SuccDep, D);
505 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
506 SDep D = ChainSuccs[i];
507 SUnit *SuccDep = D.getSUnit();
509 RemovePred(SuccDep, D);
516 // Add a data dependency to reflect that NewSU reads the value defined
518 AddPred(NewSU, SDep(LoadSU, SDep::Data, LoadSU->Latency));
521 AvailableQueue->addNode(LoadSU);
522 AvailableQueue->addNode(NewSU);
526 if (NewSU->NumSuccsLeft == 0) {
527 NewSU->isAvailable = true;
533 DEBUG(dbgs() << " Duplicating SU #" << SU->NodeNum << "\n");
534 NewSU = CreateClone(SU);
536 // New SUnit has the exact same predecessors.
537 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
539 if (!I->isArtificial())
542 // Only copy scheduled successors. Cut them from old node's successor
543 // list and move them over.
544 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
545 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
547 if (I->isArtificial())
549 SUnit *SuccSU = I->getSUnit();
550 if (SuccSU->isScheduled) {
555 DelDeps.push_back(std::make_pair(SuccSU, D));
558 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
559 RemovePred(DelDeps[i].first, DelDeps[i].second);
561 AvailableQueue->updateNode(SU);
562 AvailableQueue->addNode(NewSU);
568 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
569 /// scheduled successors of the given SUnit to the last copy.
570 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
571 const TargetRegisterClass *DestRC,
572 const TargetRegisterClass *SrcRC,
573 SmallVector<SUnit*, 2> &Copies) {
574 SUnit *CopyFromSU = CreateNewSUnit(NULL);
575 CopyFromSU->CopySrcRC = SrcRC;
576 CopyFromSU->CopyDstRC = DestRC;
578 SUnit *CopyToSU = CreateNewSUnit(NULL);
579 CopyToSU->CopySrcRC = DestRC;
580 CopyToSU->CopyDstRC = SrcRC;
582 // Only copy scheduled successors. Cut them from old node's successor
583 // list and move them over.
584 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
585 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
587 if (I->isArtificial())
589 SUnit *SuccSU = I->getSUnit();
590 if (SuccSU->isScheduled) {
592 D.setSUnit(CopyToSU);
594 DelDeps.push_back(std::make_pair(SuccSU, *I));
597 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
598 RemovePred(DelDeps[i].first, DelDeps[i].second);
600 AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
601 AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
603 AvailableQueue->updateNode(SU);
604 AvailableQueue->addNode(CopyFromSU);
605 AvailableQueue->addNode(CopyToSU);
606 Copies.push_back(CopyFromSU);
607 Copies.push_back(CopyToSU);
612 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
613 /// definition of the specified node.
614 /// FIXME: Move to SelectionDAG?
615 static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
616 const TargetInstrInfo *TII) {
617 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
618 assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
619 unsigned NumRes = TID.getNumDefs();
620 for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
625 return N->getValueType(NumRes);
628 /// CheckForLiveRegDef - Return true and update live register vector if the
629 /// specified register def of the specified SUnit clobbers any "live" registers.
630 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
631 std::vector<SUnit*> &LiveRegDefs,
632 SmallSet<unsigned, 4> &RegAdded,
633 SmallVector<unsigned, 4> &LRegs,
634 const TargetRegisterInfo *TRI) {
636 if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != SU) {
637 if (RegAdded.insert(Reg)) {
638 LRegs.push_back(Reg);
642 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias)
643 if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) {
644 if (RegAdded.insert(*Alias)) {
645 LRegs.push_back(*Alias);
652 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
653 /// scheduling of the given node to satisfy live physical register dependencies.
654 /// If the specific node is the last one that's available to schedule, do
655 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
656 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU,
657 SmallVector<unsigned, 4> &LRegs){
658 if (NumLiveRegs == 0)
661 SmallSet<unsigned, 4> RegAdded;
662 // If this node would clobber any "live" register, then it's not ready.
663 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
665 if (I->isAssignedRegDep())
666 CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs,
667 RegAdded, LRegs, TRI);
670 for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) {
671 if (Node->getOpcode() == ISD::INLINEASM) {
672 // Inline asm can clobber physical defs.
673 unsigned NumOps = Node->getNumOperands();
674 if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
675 --NumOps; // Ignore the flag operand.
677 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
679 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
680 unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
682 ++i; // Skip the ID value.
683 if (InlineAsm::isRegDefKind(Flags) ||
684 InlineAsm::isRegDefEarlyClobberKind(Flags)) {
685 // Check for def of register or earlyclobber register.
686 for (; NumVals; --NumVals, ++i) {
687 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
688 if (TargetRegisterInfo::isPhysicalRegister(Reg))
689 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
697 if (!Node->isMachineOpcode())
699 const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode());
700 if (!TID.ImplicitDefs)
702 for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg)
703 CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
705 return !LRegs.empty();
709 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
711 void ScheduleDAGRRList::ListScheduleBottomUp() {
712 unsigned CurCycle = 0;
714 // Release any predecessors of the special Exit node.
715 ReleasePredecessors(&ExitSU, CurCycle);
717 // Add root to Available queue.
718 if (!SUnits.empty()) {
719 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
720 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
721 RootSU->isAvailable = true;
722 AvailableQueue->push(RootSU);
725 // While Available queue is not empty, grab the node with the highest
726 // priority. If it is not ready put it back. Schedule the node.
727 SmallVector<SUnit*, 4> NotReady;
728 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
729 Sequence.reserve(SUnits.size());
730 while (!AvailableQueue->empty()) {
731 bool Delayed = false;
733 SUnit *CurSU = AvailableQueue->pop();
735 SmallVector<unsigned, 4> LRegs;
736 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
739 LRegsMap.insert(std::make_pair(CurSU, LRegs));
741 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
742 NotReady.push_back(CurSU);
743 CurSU = AvailableQueue->pop();
746 // All candidates are delayed due to live physical reg dependencies.
747 // Try backtracking, code duplication, or inserting cross class copies
749 if (Delayed && !CurSU) {
750 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
751 SUnit *TrySU = NotReady[i];
752 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
754 // Try unscheduling up to the point where it's safe to schedule
756 unsigned LiveCycle = CurCycle;
757 for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
758 unsigned Reg = LRegs[j];
759 unsigned LCycle = LiveRegCycles[Reg];
760 LiveCycle = std::min(LiveCycle, LCycle);
762 SUnit *OldSU = Sequence[LiveCycle];
763 if (!WillCreateCycle(TrySU, OldSU)) {
764 BacktrackBottomUp(TrySU, LiveCycle, CurCycle);
765 // Force the current node to be scheduled before the node that
766 // requires the physical reg dep.
767 if (OldSU->isAvailable) {
768 OldSU->isAvailable = false;
769 AvailableQueue->remove(OldSU);
771 AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
772 /*Reg=*/0, /*isNormalMemory=*/false,
773 /*isMustAlias=*/false, /*isArtificial=*/true));
774 // If one or more successors has been unscheduled, then the current
775 // node is no longer avaialable. Schedule a successor that's now
776 // available instead.
777 if (!TrySU->isAvailable)
778 CurSU = AvailableQueue->pop();
781 TrySU->isPending = false;
782 NotReady.erase(NotReady.begin()+i);
789 // Can't backtrack. If it's too expensive to copy the value, then try
790 // duplicate the nodes that produces these "too expensive to copy"
791 // values to break the dependency. In case even that doesn't work,
792 // insert cross class copies.
793 // If it's not too expensive, i.e. cost != -1, issue copies.
794 SUnit *TrySU = NotReady[0];
795 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
796 assert(LRegs.size() == 1 && "Can't handle this yet!");
797 unsigned Reg = LRegs[0];
798 SUnit *LRDef = LiveRegDefs[Reg];
799 EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
800 const TargetRegisterClass *RC =
801 TRI->getMinimalPhysRegClass(Reg, VT);
802 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
804 // If cross copy register class is null, then it must be possible copy
805 // the value directly. Do not try duplicate the def.
808 NewDef = CopyAndMoveSuccessors(LRDef);
812 // Issue copies, these can be expensive cross register class copies.
813 SmallVector<SUnit*, 2> Copies;
814 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
815 DEBUG(dbgs() << " Adding an edge from SU #" << TrySU->NodeNum
816 << " to SU #" << Copies.front()->NodeNum << "\n");
817 AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
818 /*Reg=*/0, /*isNormalMemory=*/false,
819 /*isMustAlias=*/false,
820 /*isArtificial=*/true));
821 NewDef = Copies.back();
824 DEBUG(dbgs() << " Adding an edge from SU #" << NewDef->NodeNum
825 << " to SU #" << TrySU->NodeNum << "\n");
826 LiveRegDefs[Reg] = NewDef;
827 AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
828 /*Reg=*/0, /*isNormalMemory=*/false,
829 /*isMustAlias=*/false,
830 /*isArtificial=*/true));
831 TrySU->isAvailable = false;
835 assert(CurSU && "Unable to resolve live physical register dependencies!");
838 // Add the nodes that aren't ready back onto the available list.
839 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
840 NotReady[i]->isPending = false;
841 // May no longer be available due to backtracking.
842 if (NotReady[i]->isAvailable)
843 AvailableQueue->push(NotReady[i]);
848 ScheduleNodeBottomUp(CurSU, CurCycle);
850 AvailableQueue->setCurCycle(CurCycle);
853 // Reverse the order if it is bottom up.
854 std::reverse(Sequence.begin(), Sequence.end());
857 VerifySchedule(isBottomUp);
861 //===----------------------------------------------------------------------===//
862 // Top-Down Scheduling
863 //===----------------------------------------------------------------------===//
865 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
866 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
867 void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) {
868 SUnit *SuccSU = SuccEdge->getSUnit();
871 if (SuccSU->NumPredsLeft == 0) {
872 dbgs() << "*** Scheduling failed! ***\n";
874 dbgs() << " has been released too many times!\n";
878 --SuccSU->NumPredsLeft;
880 // If all the node's predecessors are scheduled, this node is ready
881 // to be scheduled. Ignore the special ExitSU node.
882 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {
883 SuccSU->isAvailable = true;
884 AvailableQueue->push(SuccSU);
888 void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) {
889 // Top down: release successors
890 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
892 assert(!I->isAssignedRegDep() &&
893 "The list-tdrr scheduler doesn't yet support physreg dependencies!");
895 ReleaseSucc(SU, &*I);
899 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
900 /// count of its successors. If a successor pending count is zero, add it to
901 /// the Available queue.
902 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
903 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
904 DEBUG(SU->dump(this));
906 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
907 SU->setDepthToAtLeast(CurCycle);
908 Sequence.push_back(SU);
910 ReleaseSuccessors(SU);
911 SU->isScheduled = true;
912 AvailableQueue->ScheduledNode(SU);
915 /// ListScheduleTopDown - The main loop of list scheduling for top-down
917 void ScheduleDAGRRList::ListScheduleTopDown() {
918 unsigned CurCycle = 0;
919 AvailableQueue->setCurCycle(CurCycle);
921 // Release any successors of the special Entry node.
922 ReleaseSuccessors(&EntrySU);
924 // All leaves to Available queue.
925 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
926 // It is available if it has no predecessors.
927 if (SUnits[i].Preds.empty()) {
928 AvailableQueue->push(&SUnits[i]);
929 SUnits[i].isAvailable = true;
933 // While Available queue is not empty, grab the node with the highest
934 // priority. If it is not ready put it back. Schedule the node.
935 Sequence.reserve(SUnits.size());
936 while (!AvailableQueue->empty()) {
937 SUnit *CurSU = AvailableQueue->pop();
940 ScheduleNodeTopDown(CurSU, CurCycle);
942 AvailableQueue->setCurCycle(CurCycle);
946 VerifySchedule(isBottomUp);
951 //===----------------------------------------------------------------------===//
952 // RegReductionPriorityQueue Implementation
953 //===----------------------------------------------------------------------===//
955 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
956 // to reduce register pressure.
960 class RegReductionPriorityQueue;
962 /// Sorting functions for the Available queue.
963 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
964 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
965 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
966 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
968 bool operator()(const SUnit* left, const SUnit* right) const;
971 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
972 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
973 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
974 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
976 bool operator()(const SUnit* left, const SUnit* right) const;
979 struct src_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
980 RegReductionPriorityQueue<src_ls_rr_sort> *SPQ;
981 src_ls_rr_sort(RegReductionPriorityQueue<src_ls_rr_sort> *spq)
983 src_ls_rr_sort(const src_ls_rr_sort &RHS)
986 bool operator()(const SUnit* left, const SUnit* right) const;
989 struct hybrid_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
990 RegReductionPriorityQueue<hybrid_ls_rr_sort> *SPQ;
991 hybrid_ls_rr_sort(RegReductionPriorityQueue<hybrid_ls_rr_sort> *spq)
993 hybrid_ls_rr_sort(const hybrid_ls_rr_sort &RHS)
996 bool operator()(const SUnit* left, const SUnit* right) const;
998 } // end anonymous namespace
1000 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
1001 /// Smaller number is the higher priority.
1003 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
1004 unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
1005 if (SethiUllmanNumber != 0)
1006 return SethiUllmanNumber;
1009 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1011 if (I->isCtrl()) continue; // ignore chain preds
1012 SUnit *PredSU = I->getSUnit();
1013 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
1014 if (PredSethiUllman > SethiUllmanNumber) {
1015 SethiUllmanNumber = PredSethiUllman;
1017 } else if (PredSethiUllman == SethiUllmanNumber)
1021 SethiUllmanNumber += Extra;
1023 if (SethiUllmanNumber == 0)
1024 SethiUllmanNumber = 1;
1026 return SethiUllmanNumber;
1031 class RegReductionPriorityQueue : public SchedulingPriorityQueue {
1032 std::vector<SUnit*> Queue;
1034 unsigned CurQueueId;
1035 bool TracksRegPressure;
1038 // SUnits - The SUnits for the current graph.
1039 std::vector<SUnit> *SUnits;
1041 MachineFunction &MF;
1042 const TargetInstrInfo *TII;
1043 const TargetRegisterInfo *TRI;
1044 const TargetLowering *TLI;
1045 ScheduleDAGRRList *scheduleDAG;
1047 // SethiUllmanNumbers - The SethiUllman number for each node.
1048 std::vector<unsigned> SethiUllmanNumbers;
1050 /// RegPressure - Tracking current reg pressure per register class.
1052 std::vector<unsigned> RegPressure;
1054 /// RegLimit - Tracking the number of allocatable registers per register
1056 std::vector<unsigned> RegLimit;
1059 RegReductionPriorityQueue(MachineFunction &mf,
1061 const TargetInstrInfo *tii,
1062 const TargetRegisterInfo *tri,
1063 const TargetLowering *tli)
1064 : Picker(this), CurQueueId(0), TracksRegPressure(tracksrp),
1065 MF(mf), TII(tii), TRI(tri), TLI(tli), scheduleDAG(NULL) {
1066 if (TracksRegPressure) {
1067 unsigned NumRC = TRI->getNumRegClasses();
1068 RegLimit.resize(NumRC);
1069 RegPressure.resize(NumRC);
1070 std::fill(RegLimit.begin(), RegLimit.end(), 0);
1071 std::fill(RegPressure.begin(), RegPressure.end(), 0);
1072 for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
1073 E = TRI->regclass_end(); I != E; ++I)
1074 RegLimit[(*I)->getID()] = tli->getRegPressureLimit(*I, MF);
1078 void initNodes(std::vector<SUnit> &sunits) {
1080 // Add pseudo dependency edges for two-address nodes.
1081 AddPseudoTwoAddrDeps();
1082 // Reroute edges to nodes with multiple uses.
1083 PrescheduleNodesWithMultipleUses();
1084 // Calculate node priorities.
1085 CalculateSethiUllmanNumbers();
1088 void addNode(const SUnit *SU) {
1089 unsigned SUSize = SethiUllmanNumbers.size();
1090 if (SUnits->size() > SUSize)
1091 SethiUllmanNumbers.resize(SUSize*2, 0);
1092 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1095 void updateNode(const SUnit *SU) {
1096 SethiUllmanNumbers[SU->NodeNum] = 0;
1097 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1100 void releaseState() {
1102 SethiUllmanNumbers.clear();
1103 std::fill(RegPressure.begin(), RegPressure.end(), 0);
1106 unsigned getNodePriority(const SUnit *SU) const {
1107 assert(SU->NodeNum < SethiUllmanNumbers.size());
1108 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
1109 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
1110 // CopyToReg should be close to its uses to facilitate coalescing and
1113 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
1114 Opc == TargetOpcode::SUBREG_TO_REG ||
1115 Opc == TargetOpcode::INSERT_SUBREG)
1116 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
1117 // close to their uses to facilitate coalescing.
1119 if (SU->NumSuccs == 0 && SU->NumPreds != 0)
1120 // If SU does not have a register use, i.e. it doesn't produce a value
1121 // that would be consumed (e.g. store), then it terminates a chain of
1122 // computation. Give it a large SethiUllman number so it will be
1123 // scheduled right before its predecessors that it doesn't lengthen
1124 // their live ranges.
1126 if (SU->NumPreds == 0 && SU->NumSuccs != 0)
1127 // If SU does not have a register def, schedule it close to its uses
1128 // because it does not lengthen any live ranges.
1130 return SethiUllmanNumbers[SU->NodeNum];
1133 unsigned getNodeOrdering(const SUnit *SU) const {
1134 return scheduleDAG->DAG->GetOrdering(SU->getNode());
1137 bool empty() const { return Queue.empty(); }
1139 void push(SUnit *U) {
1140 assert(!U->NodeQueueId && "Node in the queue already");
1141 U->NodeQueueId = ++CurQueueId;
1146 if (empty()) return NULL;
1147 std::vector<SUnit *>::iterator Best = Queue.begin();
1148 for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()),
1149 E = Queue.end(); I != E; ++I)
1150 if (Picker(*Best, *I))
1153 if (Best != prior(Queue.end()))
1154 std::swap(*Best, Queue.back());
1160 void remove(SUnit *SU) {
1161 assert(!Queue.empty() && "Queue is empty!");
1162 assert(SU->NodeQueueId != 0 && "Not in queue!");
1163 std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(),
1165 if (I != prior(Queue.end()))
1166 std::swap(*I, Queue.back());
1168 SU->NodeQueueId = 0;
1171 bool HighRegPressure(const SUnit *SU, unsigned &Excess) const {
1177 for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
1181 SUnit *PredSU = I->getSUnit();
1182 const SDNode *PN = PredSU->getNode();
1183 if (!PN->isMachineOpcode()) {
1184 if (PN->getOpcode() == ISD::CopyFromReg) {
1185 EVT VT = PN->getValueType(0);
1186 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1187 unsigned Cost = TLI->getRepRegClassCostFor(VT);
1188 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId]) {
1190 Excess += (RegPressure[RCId] + Cost) - RegLimit[RCId];
1195 unsigned POpc = PN->getMachineOpcode();
1196 if (POpc == TargetOpcode::IMPLICIT_DEF)
1198 if (POpc == TargetOpcode::EXTRACT_SUBREG) {
1199 EVT VT = PN->getOperand(0).getValueType();
1200 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1201 unsigned Cost = TLI->getRepRegClassCostFor(VT);
1202 // Check if this increases register pressure of the specific register
1203 // class to the point where it would cause spills.
1204 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId]) {
1206 Excess += (RegPressure[RCId] + Cost) - RegLimit[RCId];
1209 } else if (POpc == TargetOpcode::INSERT_SUBREG ||
1210 POpc == TargetOpcode::SUBREG_TO_REG) {
1211 EVT VT = PN->getValueType(0);
1212 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1213 unsigned Cost = TLI->getRepRegClassCostFor(VT);
1214 // Check if this increases register pressure of the specific register
1215 // class to the point where it would cause spills.
1216 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId]) {
1218 Excess += (RegPressure[RCId] + Cost) - RegLimit[RCId];
1222 unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
1223 for (unsigned i = 0; i != NumDefs; ++i) {
1224 EVT VT = PN->getValueType(i);
1225 if (!PN->hasAnyUseOfValue(i))
1227 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1228 unsigned Cost = TLI->getRepRegClassCostFor(VT);
1229 // Check if this increases register pressure of the specific register
1230 // class to the point where it would cause spills.
1231 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId]) {
1233 Excess += (RegPressure[RCId] + Cost) - RegLimit[RCId];
1241 void ScheduledNode(SUnit *SU) {
1242 if (!TracksRegPressure)
1245 const SDNode *N = SU->getNode();
1246 if (!N->isMachineOpcode()) {
1247 if (N->getOpcode() != ISD::CopyToReg)
1250 unsigned Opc = N->getMachineOpcode();
1251 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
1252 Opc == TargetOpcode::INSERT_SUBREG ||
1253 Opc == TargetOpcode::SUBREG_TO_REG ||
1254 Opc == TargetOpcode::REG_SEQUENCE ||
1255 Opc == TargetOpcode::IMPLICIT_DEF)
1259 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1263 SUnit *PredSU = I->getSUnit();
1264 if (PredSU->NumSuccsLeft != PredSU->NumSuccs)
1266 const SDNode *PN = PredSU->getNode();
1267 if (!PN->isMachineOpcode()) {
1268 if (PN->getOpcode() == ISD::CopyFromReg) {
1269 EVT VT = PN->getValueType(0);
1270 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1271 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1275 unsigned POpc = PN->getMachineOpcode();
1276 if (POpc == TargetOpcode::IMPLICIT_DEF)
1278 if (POpc == TargetOpcode::EXTRACT_SUBREG) {
1279 EVT VT = PN->getOperand(0).getValueType();
1280 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1281 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1283 } else if (POpc == TargetOpcode::INSERT_SUBREG ||
1284 POpc == TargetOpcode::SUBREG_TO_REG) {
1285 EVT VT = PN->getValueType(0);
1286 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1287 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1290 unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
1291 for (unsigned i = 0; i != NumDefs; ++i) {
1292 EVT VT = PN->getValueType(i);
1293 if (!PN->hasAnyUseOfValue(i))
1295 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1296 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1301 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1302 for (unsigned i = 0; i != NumDefs; ++i) {
1303 EVT VT = N->getValueType(i);
1304 if (!N->hasAnyUseOfValue(i))
1306 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1307 if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
1308 // Register pressure tracking is imprecise. This can happen.
1309 RegPressure[RCId] = 0;
1311 RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
1318 void UnscheduledNode(SUnit *SU) {
1319 if (!TracksRegPressure)
1322 const SDNode *N = SU->getNode();
1323 if (!N->isMachineOpcode()) {
1324 if (N->getOpcode() != ISD::CopyToReg)
1327 unsigned Opc = N->getMachineOpcode();
1328 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
1329 Opc == TargetOpcode::INSERT_SUBREG ||
1330 Opc == TargetOpcode::SUBREG_TO_REG ||
1331 Opc == TargetOpcode::REG_SEQUENCE ||
1332 Opc == TargetOpcode::IMPLICIT_DEF)
1335 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1339 SUnit *PredSU = I->getSUnit();
1340 if (PredSU->NumSuccsLeft != PredSU->NumSuccs)
1342 const SDNode *PN = PredSU->getNode();
1343 if (!PN->isMachineOpcode()) {
1344 if (PN->getOpcode() == ISD::CopyFromReg) {
1345 EVT VT = PN->getValueType(0);
1346 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1347 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1351 unsigned POpc = PN->getMachineOpcode();
1352 if (POpc == TargetOpcode::IMPLICIT_DEF)
1354 if (POpc == TargetOpcode::EXTRACT_SUBREG) {
1355 EVT VT = PN->getOperand(0).getValueType();
1356 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1357 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1359 } else if (POpc == TargetOpcode::INSERT_SUBREG ||
1360 POpc == TargetOpcode::SUBREG_TO_REG) {
1361 EVT VT = PN->getValueType(0);
1362 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1363 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1366 unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
1367 for (unsigned i = 0; i != NumDefs; ++i) {
1368 EVT VT = PN->getValueType(i);
1369 if (!PN->hasAnyUseOfValue(i))
1371 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1372 if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
1373 // Register pressure tracking is imprecise. This can happen.
1374 RegPressure[RCId] = 0;
1376 RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
1381 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1382 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
1383 EVT VT = N->getValueType(i);
1384 if (VT == MVT::Flag || VT == MVT::Other)
1386 if (!N->hasAnyUseOfValue(i))
1388 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1389 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
1396 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1397 scheduleDAG = scheduleDag;
1400 void dumpRegPressure() const {
1401 for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
1402 E = TRI->regclass_end(); I != E; ++I) {
1403 const TargetRegisterClass *RC = *I;
1404 unsigned Id = RC->getID();
1405 unsigned RP = RegPressure[Id];
1407 DEBUG(dbgs() << RC->getName() << ": " << RP << " / " << RegLimit[Id]
1413 bool canClobber(const SUnit *SU, const SUnit *Op);
1414 void AddPseudoTwoAddrDeps();
1415 void PrescheduleNodesWithMultipleUses();
1416 void CalculateSethiUllmanNumbers();
1419 typedef RegReductionPriorityQueue<bu_ls_rr_sort>
1420 BURegReductionPriorityQueue;
1422 typedef RegReductionPriorityQueue<td_ls_rr_sort>
1423 TDRegReductionPriorityQueue;
1425 typedef RegReductionPriorityQueue<src_ls_rr_sort>
1426 SrcRegReductionPriorityQueue;
1428 typedef RegReductionPriorityQueue<hybrid_ls_rr_sort>
1429 HybridBURRPriorityQueue;
1432 /// closestSucc - Returns the scheduled cycle of the successor which is
1433 /// closest to the current cycle.
1434 static unsigned closestSucc(const SUnit *SU) {
1435 unsigned MaxHeight = 0;
1436 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1438 if (I->isCtrl()) continue; // ignore chain succs
1439 unsigned Height = I->getSUnit()->getHeight();
1440 // If there are bunch of CopyToRegs stacked up, they should be considered
1441 // to be at the same position.
1442 if (I->getSUnit()->getNode() &&
1443 I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
1444 Height = closestSucc(I->getSUnit())+1;
1445 if (Height > MaxHeight)
1451 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
1452 /// for scratch registers, i.e. number of data dependencies.
1453 static unsigned calcMaxScratches(const SUnit *SU) {
1454 unsigned Scratches = 0;
1455 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1457 if (I->isCtrl()) continue; // ignore chain preds
1463 template <typename RRSort>
1464 static bool BURRSort(const SUnit *left, const SUnit *right,
1465 const RegReductionPriorityQueue<RRSort> *SPQ) {
1466 unsigned LPriority = SPQ->getNodePriority(left);
1467 unsigned RPriority = SPQ->getNodePriority(right);
1468 if (LPriority != RPriority)
1469 return LPriority > RPriority;
1471 // Try schedule def + use closer when Sethi-Ullman numbers are the same.
1476 // and the following instructions are both ready.
1480 // Then schedule t2 = op first.
1487 // This creates more short live intervals.
1488 unsigned LDist = closestSucc(left);
1489 unsigned RDist = closestSucc(right);
1491 return LDist < RDist;
1493 // How many registers becomes live when the node is scheduled.
1494 unsigned LScratch = calcMaxScratches(left);
1495 unsigned RScratch = calcMaxScratches(right);
1496 if (LScratch != RScratch)
1497 return LScratch > RScratch;
1499 if (left->getHeight() != right->getHeight())
1500 return left->getHeight() > right->getHeight();
1502 if (left->getDepth() != right->getDepth())
1503 return left->getDepth() < right->getDepth();
1505 assert(left->NodeQueueId && right->NodeQueueId &&
1506 "NodeQueueId cannot be zero");
1507 return (left->NodeQueueId > right->NodeQueueId);
1511 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1512 return BURRSort(left, right, SPQ);
1515 // Source order, otherwise bottom up.
1516 bool src_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1517 unsigned LOrder = SPQ->getNodeOrdering(left);
1518 unsigned ROrder = SPQ->getNodeOrdering(right);
1520 // Prefer an ordering where the lower the non-zero order number, the higher
1522 if ((LOrder || ROrder) && LOrder != ROrder)
1523 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
1525 return BURRSort(left, right, SPQ);
1528 bool hybrid_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const{
1529 unsigned LExcess, RExcess;
1530 bool LHigh = SPQ->HighRegPressure(left, LExcess);
1531 bool RHigh = SPQ->HighRegPressure(right, RExcess);
1532 if (LHigh && !RHigh)
1534 else if (!LHigh && RHigh)
1536 else if (LHigh && RHigh) {
1537 if (LExcess > RExcess)
1539 else if (LExcess < RExcess)
1541 // Otherwise schedule for register pressure reduction.
1543 // Low register pressure situation, schedule for latency if possible.
1544 bool LStall = left->SchedulingPref == Sched::Latency &&
1545 SPQ->getCurCycle() < left->getHeight();
1546 bool RStall = right->SchedulingPref == Sched::Latency &&
1547 SPQ->getCurCycle() < right->getHeight();
1548 // If scheduling one of the node will cause a pipeline stall, delay it.
1549 // If scheduling either one of the node will cause a pipeline stall, sort
1550 // them according to their height.
1551 // If neither will cause a pipeline stall, try to reduce register pressure.
1555 if (left->getHeight() != right->getHeight())
1556 return left->getHeight() > right->getHeight();
1560 // If either node is scheduling for latency, sort them by height and latency
1562 if (left->SchedulingPref == Sched::Latency ||
1563 right->SchedulingPref == Sched::Latency) {
1564 if (left->getHeight() != right->getHeight())
1565 return left->getHeight() > right->getHeight();
1566 if (left->Latency != right->Latency)
1567 return left->Latency > right->Latency;
1571 return BURRSort(left, right, SPQ);
1576 RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) {
1577 if (SU->isTwoAddress) {
1578 unsigned Opc = SU->getNode()->getMachineOpcode();
1579 const TargetInstrDesc &TID = TII->get(Opc);
1580 unsigned NumRes = TID.getNumDefs();
1581 unsigned NumOps = TID.getNumOperands() - NumRes;
1582 for (unsigned i = 0; i != NumOps; ++i) {
1583 if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
1584 SDNode *DU = SU->getNode()->getOperand(i).getNode();
1585 if (DU->getNodeId() != -1 &&
1586 Op->OrigNode == &(*SUnits)[DU->getNodeId()])
1594 /// hasCopyToRegUse - Return true if SU has a value successor that is a
1596 static bool hasCopyToRegUse(const SUnit *SU) {
1597 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1599 if (I->isCtrl()) continue;
1600 const SUnit *SuccSU = I->getSUnit();
1601 if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
1607 /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
1608 /// physical register defs.
1609 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
1610 const TargetInstrInfo *TII,
1611 const TargetRegisterInfo *TRI) {
1612 SDNode *N = SuccSU->getNode();
1613 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1614 const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
1615 assert(ImpDefs && "Caller should check hasPhysRegDefs");
1616 for (const SDNode *SUNode = SU->getNode(); SUNode;
1617 SUNode = SUNode->getFlaggedNode()) {
1618 if (!SUNode->isMachineOpcode())
1620 const unsigned *SUImpDefs =
1621 TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
1624 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
1625 EVT VT = N->getValueType(i);
1626 if (VT == MVT::Flag || VT == MVT::Other)
1628 if (!N->hasAnyUseOfValue(i))
1630 unsigned Reg = ImpDefs[i - NumDefs];
1631 for (;*SUImpDefs; ++SUImpDefs) {
1632 unsigned SUReg = *SUImpDefs;
1633 if (TRI->regsOverlap(Reg, SUReg))
1641 /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
1642 /// are not handled well by the general register pressure reduction
1643 /// heuristics. When presented with code like this:
1652 /// the heuristics tend to push the store up, but since the
1653 /// operand of the store has another use (U), this would increase
1654 /// the length of that other use (the U->N edge).
1656 /// This function transforms code like the above to route U's
1657 /// dependence through the store when possible, like this:
1668 /// This results in the store being scheduled immediately
1669 /// after N, which shortens the U->N live range, reducing
1670 /// register pressure.
1673 void RegReductionPriorityQueue<SF>::PrescheduleNodesWithMultipleUses() {
1674 // Visit all the nodes in topological order, working top-down.
1675 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1676 SUnit *SU = &(*SUnits)[i];
1677 // For now, only look at nodes with no data successors, such as stores.
1678 // These are especially important, due to the heuristics in
1679 // getNodePriority for nodes with no data successors.
1680 if (SU->NumSuccs != 0)
1682 // For now, only look at nodes with exactly one data predecessor.
1683 if (SU->NumPreds != 1)
1685 // Avoid prescheduling copies to virtual registers, which don't behave
1686 // like other nodes from the perspective of scheduling heuristics.
1687 if (SDNode *N = SU->getNode())
1688 if (N->getOpcode() == ISD::CopyToReg &&
1689 TargetRegisterInfo::isVirtualRegister
1690 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1693 // Locate the single data predecessor.
1695 for (SUnit::const_pred_iterator II = SU->Preds.begin(),
1696 EE = SU->Preds.end(); II != EE; ++II)
1697 if (!II->isCtrl()) {
1698 PredSU = II->getSUnit();
1703 // Don't rewrite edges that carry physregs, because that requires additional
1704 // support infrastructure.
1705 if (PredSU->hasPhysRegDefs)
1707 // Short-circuit the case where SU is PredSU's only data successor.
1708 if (PredSU->NumSuccs == 1)
1710 // Avoid prescheduling to copies from virtual registers, which don't behave
1711 // like other nodes from the perspective of scheduling // heuristics.
1712 if (SDNode *N = SU->getNode())
1713 if (N->getOpcode() == ISD::CopyFromReg &&
1714 TargetRegisterInfo::isVirtualRegister
1715 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1718 // Perform checks on the successors of PredSU.
1719 for (SUnit::const_succ_iterator II = PredSU->Succs.begin(),
1720 EE = PredSU->Succs.end(); II != EE; ++II) {
1721 SUnit *PredSuccSU = II->getSUnit();
1722 if (PredSuccSU == SU) continue;
1723 // If PredSU has another successor with no data successors, for
1724 // now don't attempt to choose either over the other.
1725 if (PredSuccSU->NumSuccs == 0)
1726 goto outer_loop_continue;
1727 // Don't break physical register dependencies.
1728 if (SU->hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
1729 if (canClobberPhysRegDefs(PredSuccSU, SU, TII, TRI))
1730 goto outer_loop_continue;
1731 // Don't introduce graph cycles.
1732 if (scheduleDAG->IsReachable(SU, PredSuccSU))
1733 goto outer_loop_continue;
1736 // Ok, the transformation is safe and the heuristics suggest it is
1737 // profitable. Update the graph.
1738 DEBUG(dbgs() << " Prescheduling SU #" << SU->NodeNum
1739 << " next to PredSU #" << PredSU->NodeNum
1740 << " to guide scheduling in the presence of multiple uses\n");
1741 for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
1742 SDep Edge = PredSU->Succs[i];
1743 assert(!Edge.isAssignedRegDep());
1744 SUnit *SuccSU = Edge.getSUnit();
1746 Edge.setSUnit(PredSU);
1747 scheduleDAG->RemovePred(SuccSU, Edge);
1748 scheduleDAG->AddPred(SU, Edge);
1750 scheduleDAG->AddPred(SuccSU, Edge);
1754 outer_loop_continue:;
1758 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
1759 /// it as a def&use operand. Add a pseudo control edge from it to the other
1760 /// node (if it won't create a cycle) so the two-address one will be scheduled
1761 /// first (lower in the schedule). If both nodes are two-address, favor the
1762 /// one that has a CopyToReg use (more likely to be a loop induction update).
1763 /// If both are two-address, but one is commutable while the other is not
1764 /// commutable, favor the one that's not commutable.
1766 void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
1767 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1768 SUnit *SU = &(*SUnits)[i];
1769 if (!SU->isTwoAddress)
1772 SDNode *Node = SU->getNode();
1773 if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode())
1776 unsigned Opc = Node->getMachineOpcode();
1777 const TargetInstrDesc &TID = TII->get(Opc);
1778 unsigned NumRes = TID.getNumDefs();
1779 unsigned NumOps = TID.getNumOperands() - NumRes;
1780 for (unsigned j = 0; j != NumOps; ++j) {
1781 if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
1783 SDNode *DU = SU->getNode()->getOperand(j).getNode();
1784 if (DU->getNodeId() == -1)
1786 const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
1787 if (!DUSU) continue;
1788 for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
1789 E = DUSU->Succs.end(); I != E; ++I) {
1790 if (I->isCtrl()) continue;
1791 SUnit *SuccSU = I->getSUnit();
1794 // Be conservative. Ignore if nodes aren't at roughly the same
1795 // depth and height.
1796 if (SuccSU->getHeight() < SU->getHeight() &&
1797 (SU->getHeight() - SuccSU->getHeight()) > 1)
1799 // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
1800 // constrains whatever is using the copy, instead of the copy
1801 // itself. In the case that the copy is coalesced, this
1802 // preserves the intent of the pseudo two-address heurietics.
1803 while (SuccSU->Succs.size() == 1 &&
1804 SuccSU->getNode()->isMachineOpcode() &&
1805 SuccSU->getNode()->getMachineOpcode() ==
1806 TargetOpcode::COPY_TO_REGCLASS)
1807 SuccSU = SuccSU->Succs.front().getSUnit();
1808 // Don't constrain non-instruction nodes.
1809 if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
1811 // Don't constrain nodes with physical register defs if the
1812 // predecessor can clobber them.
1813 if (SuccSU->hasPhysRegDefs && SU->hasPhysRegClobbers) {
1814 if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
1817 // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
1818 // these may be coalesced away. We want them close to their uses.
1819 unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
1820 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
1821 SuccOpc == TargetOpcode::INSERT_SUBREG ||
1822 SuccOpc == TargetOpcode::SUBREG_TO_REG)
1824 if ((!canClobber(SuccSU, DUSU) ||
1825 (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
1826 (!SU->isCommutable && SuccSU->isCommutable)) &&
1827 !scheduleDAG->IsReachable(SuccSU, SU)) {
1828 DEBUG(dbgs() << " Adding a pseudo-two-addr edge from SU #"
1829 << SU->NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
1830 scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0,
1831 /*Reg=*/0, /*isNormalMemory=*/false,
1832 /*isMustAlias=*/false,
1833 /*isArtificial=*/true));
1840 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1841 /// scheduling units.
1843 void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
1844 SethiUllmanNumbers.assign(SUnits->size(), 0);
1846 for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
1847 CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers);
1850 /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled
1851 /// predecessors of the successors of the SUnit SU. Stop when the provided
1852 /// limit is exceeded.
1853 static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU,
1856 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1858 const SUnit *SuccSU = I->getSUnit();
1859 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
1860 EE = SuccSU->Preds.end(); II != EE; ++II) {
1861 SUnit *PredSU = II->getSUnit();
1862 if (!PredSU->isScheduled)
1872 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1873 unsigned LPriority = SPQ->getNodePriority(left);
1874 unsigned RPriority = SPQ->getNodePriority(right);
1875 bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode();
1876 bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode();
1877 bool LIsFloater = LIsTarget && left->NumPreds == 0;
1878 bool RIsFloater = RIsTarget && right->NumPreds == 0;
1879 unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0;
1880 unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0;
1882 if (left->NumSuccs == 0 && right->NumSuccs != 0)
1884 else if (left->NumSuccs != 0 && right->NumSuccs == 0)
1891 if (left->NumSuccs == 1)
1893 if (right->NumSuccs == 1)
1896 if (LPriority+LBonus != RPriority+RBonus)
1897 return LPriority+LBonus < RPriority+RBonus;
1899 if (left->getDepth() != right->getDepth())
1900 return left->getDepth() < right->getDepth();
1902 if (left->NumSuccsLeft != right->NumSuccsLeft)
1903 return left->NumSuccsLeft > right->NumSuccsLeft;
1905 assert(left->NodeQueueId && right->NodeQueueId &&
1906 "NodeQueueId cannot be zero");
1907 return (left->NodeQueueId > right->NodeQueueId);
1910 //===----------------------------------------------------------------------===//
1911 // Public Constructor Functions
1912 //===----------------------------------------------------------------------===//
1914 llvm::ScheduleDAGSDNodes *
1915 llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1916 const TargetMachine &TM = IS->TM;
1917 const TargetInstrInfo *TII = TM.getInstrInfo();
1918 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1920 BURegReductionPriorityQueue *PQ =
1921 new BURegReductionPriorityQueue(*IS->MF, false, TII, TRI, 0);
1922 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, false, PQ);
1923 PQ->setScheduleDAG(SD);
1927 llvm::ScheduleDAGSDNodes *
1928 llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1929 const TargetMachine &TM = IS->TM;
1930 const TargetInstrInfo *TII = TM.getInstrInfo();
1931 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1933 TDRegReductionPriorityQueue *PQ =
1934 new TDRegReductionPriorityQueue(*IS->MF, false, TII, TRI, 0);
1935 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, false, PQ);
1936 PQ->setScheduleDAG(SD);
1940 llvm::ScheduleDAGSDNodes *
1941 llvm::createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1942 const TargetMachine &TM = IS->TM;
1943 const TargetInstrInfo *TII = TM.getInstrInfo();
1944 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1946 SrcRegReductionPriorityQueue *PQ =
1947 new SrcRegReductionPriorityQueue(*IS->MF, false, TII, TRI, 0);
1948 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, false, PQ);
1949 PQ->setScheduleDAG(SD);
1953 llvm::ScheduleDAGSDNodes *
1954 llvm::createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1955 const TargetMachine &TM = IS->TM;
1956 const TargetInstrInfo *TII = TM.getInstrInfo();
1957 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1958 const TargetLowering *TLI = &IS->getTargetLowering();
1960 HybridBURRPriorityQueue *PQ =
1961 new HybridBURRPriorityQueue(*IS->MF, true, TII, TRI, TLI);
1962 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, true, PQ);
1963 PQ->setScheduleDAG(SD);