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 "pre-RA-sched"
19 #include "llvm/CodeGen/ScheduleDAG.h"
20 #include "llvm/CodeGen/SchedulerRegistry.h"
21 #include "llvm/CodeGen/SSARegMap.h"
22 #include "llvm/Target/MRegisterInfo.h"
23 #include "llvm/Target/TargetData.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/Compiler.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Support/CommandLine.h"
35 static RegisterScheduler
36 burrListDAGScheduler("list-burr",
37 " Bottom-up register reduction list scheduling",
38 createBURRListDAGScheduler);
39 static RegisterScheduler
40 tdrListrDAGScheduler("list-tdrr",
41 " Top-down register reduction list scheduling",
42 createTDRRListDAGScheduler);
45 //===----------------------------------------------------------------------===//
46 /// ScheduleDAGRRList - The actual register reduction list scheduler
47 /// implementation. This supports both top-down and bottom-up scheduling.
49 class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG {
51 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
55 /// AvailableQueue - The priority queue to use for the available SUnits.
57 SchedulingPriorityQueue *AvailableQueue;
59 /// LiveRegs / LiveRegDefs - A set of physical registers and their definition
60 /// that are "live". These nodes must be scheduled before any other nodes that
61 /// modifies the registers can be scheduled.
62 SmallSet<unsigned, 4> LiveRegs;
63 std::vector<SUnit*> LiveRegDefs;
64 std::vector<unsigned> LiveRegCycles;
67 ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb,
68 const TargetMachine &tm, bool isbottomup,
69 SchedulingPriorityQueue *availqueue)
70 : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
71 AvailableQueue(availqueue) {
74 ~ScheduleDAGRRList() {
75 delete AvailableQueue;
81 void ReleasePred(SUnit*, bool, unsigned);
82 void ReleaseSucc(SUnit*, bool isChain, unsigned);
83 void CapturePred(SUnit*, SUnit*, bool);
84 void ScheduleNodeBottomUp(SUnit*, unsigned);
85 void ScheduleNodeTopDown(SUnit*, unsigned);
86 void UnscheduleNodeBottomUp(SUnit*);
87 void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
88 SUnit *CopyAndMoveSuccessors(SUnit*);
89 SUnit *InsertCopiesAndMoveSuccs(SUnit*, unsigned,
90 const TargetRegisterClass*,
91 const TargetRegisterClass*);
92 bool DelayForLiveRegsBottomUp(SUnit*, unsigned&);
93 void ListScheduleTopDown();
94 void ListScheduleBottomUp();
95 void CommuteNodesToReducePressure();
97 } // end anonymous namespace
100 /// Schedule - Schedule the DAG using list scheduling.
101 void ScheduleDAGRRList::Schedule() {
102 DOUT << "********** List Scheduling **********\n";
104 LiveRegDefs.resize(MRI->getNumRegs(), NULL);
105 LiveRegCycles.resize(MRI->getNumRegs(), 0);
107 // Build scheduling units.
110 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
111 SUnits[su].dumpAll(&DAG));
115 AvailableQueue->initNodes(SUnitMap, SUnits);
117 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
119 ListScheduleBottomUp();
121 ListScheduleTopDown();
123 AvailableQueue->releaseState();
125 CommuteNodesToReducePressure();
127 DOUT << "*** Final schedule ***\n";
128 DEBUG(dumpSchedule());
131 // Emit in scheduled order
135 /// CommuteNodesToReducePressure - If a node is two-address and commutable, and
136 /// it is not the last use of its first operand, add it to the CommuteSet if
137 /// possible. It will be commuted when it is translated to a MI.
138 void ScheduleDAGRRList::CommuteNodesToReducePressure() {
139 SmallPtrSet<SUnit*, 4> OperandSeen;
140 for (unsigned i = Sequence.size()-1; i != 0; --i) { // Ignore first node.
141 SUnit *SU = Sequence[i];
142 if (!SU || !SU->Node) continue;
143 if (SU->isCommutable) {
144 unsigned Opc = SU->Node->getTargetOpcode();
145 unsigned NumRes = TII->getNumDefs(Opc);
146 unsigned NumOps = CountOperands(SU->Node);
147 for (unsigned j = 0; j != NumOps; ++j) {
148 if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) == -1)
151 SDNode *OpN = SU->Node->getOperand(j).Val;
152 SUnit *OpSU = SUnitMap[OpN][SU->InstanceNo];
153 if (OpSU && OperandSeen.count(OpSU) == 1) {
154 // Ok, so SU is not the last use of OpSU, but SU is two-address so
155 // it will clobber OpSU. Try to commute SU if no other source operands
157 bool DoCommute = true;
158 for (unsigned k = 0; k < NumOps; ++k) {
160 OpN = SU->Node->getOperand(k).Val;
161 OpSU = SUnitMap[OpN][SU->InstanceNo];
162 if (OpSU && OperandSeen.count(OpSU) == 1) {
169 CommuteSet.insert(SU->Node);
172 // Only look at the first use&def node for now.
177 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
180 OperandSeen.insert(I->Dep);
185 //===----------------------------------------------------------------------===//
186 // Bottom-Up Scheduling
187 //===----------------------------------------------------------------------===//
189 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
190 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
191 void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain,
193 // FIXME: the distance between two nodes is not always == the predecessor's
194 // latency. For example, the reader can very well read the register written
195 // by the predecessor later than the issue cycle. It also depends on the
196 // interrupt model (drain vs. freeze).
197 PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
200 --PredSU->NumSuccsLeft;
202 --PredSU->NumChainSuccsLeft;
205 if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
206 cerr << "*** List scheduling failed! ***\n";
208 cerr << " has been released too many times!\n";
213 if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
214 // EntryToken has to go last! Special case it here.
215 if (!PredSU->Node || PredSU->Node->getOpcode() != ISD::EntryToken) {
216 PredSU->isAvailable = true;
217 AvailableQueue->push(PredSU);
222 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
223 /// count of its predecessors. If a predecessor pending count is zero, add it to
224 /// the Available queue.
225 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
226 DOUT << "*** Scheduling [" << CurCycle << "]: ";
227 DEBUG(SU->dump(&DAG));
228 SU->Cycle = CurCycle;
230 AvailableQueue->ScheduledNode(SU);
232 // Bottom up: release predecessors
233 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
235 ReleasePred(I->Dep, I->isCtrl, CurCycle);
237 // This is a physical register dependency and it's impossible or
238 // expensive to copy the register. Make sure nothing that can
239 // clobber the register is scheduled between the predecessor and
241 if (LiveRegs.insert(I->Reg)) {
242 LiveRegDefs[I->Reg] = I->Dep;
243 LiveRegCycles[I->Reg] = CurCycle;
248 // Release all the implicit physical register defs that are live.
249 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
252 if (LiveRegCycles[I->Reg] == I->Dep->Cycle) {
253 LiveRegs.erase(I->Reg);
254 assert(LiveRegDefs[I->Reg] == SU &&
255 "Physical register dependency violated?");
256 LiveRegDefs[I->Reg] = NULL;
257 LiveRegCycles[I->Reg] = 0;
262 SU->isScheduled = true;
265 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
266 /// unscheduled, incrcease the succ left count of its predecessors. Remove
267 /// them from AvailableQueue if necessary.
268 void ScheduleDAGRRList::CapturePred(SUnit *PredSU, SUnit *SU, bool isChain) {
269 PredSU->CycleBound = 0;
270 for (SUnit::succ_iterator I = PredSU->Succs.begin(), E = PredSU->Succs.end();
274 PredSU->CycleBound = std::max(PredSU->CycleBound,
275 I->Dep->Cycle + PredSU->Latency);
278 if (PredSU->isAvailable) {
279 PredSU->isAvailable = false;
280 if (!PredSU->isPending)
281 AvailableQueue->remove(PredSU);
285 ++PredSU->NumSuccsLeft;
287 ++PredSU->NumChainSuccsLeft;
290 /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
291 /// its predecessor states to reflect the change.
292 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
293 DOUT << "*** Unscheduling [" << SU->Cycle << "]: ";
294 DEBUG(SU->dump(&DAG));
296 AvailableQueue->UnscheduledNode(SU);
298 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
300 CapturePred(I->Dep, SU, I->isCtrl);
301 if (I->Cost < 0 && SU->Cycle == LiveRegCycles[I->Reg]) {
302 LiveRegs.erase(I->Reg);
303 assert(LiveRegDefs[I->Reg] == I->Dep &&
304 "Physical register dependency violated?");
305 LiveRegDefs[I->Reg] = NULL;
306 LiveRegCycles[I->Reg] = 0;
310 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
313 if (LiveRegs.insert(I->Reg)) {
314 assert(!LiveRegDefs[I->Reg] &&
315 "Physical register dependency violated?");
316 LiveRegDefs[I->Reg] = SU;
318 if (I->Dep->Cycle < LiveRegCycles[I->Reg])
319 LiveRegCycles[I->Reg] = I->Dep->Cycle;
324 SU->isScheduled = false;
325 SU->isAvailable = true;
326 AvailableQueue->push(SU);
329 // FIXME: This is probably too slow!
330 static void isReachable(SUnit *SU, SUnit *TargetSU,
331 SmallPtrSet<SUnit*, 32> &Visited, bool &Reached) {
333 if (SU == TargetSU) {
337 if (!Visited.insert(SU)) return;
339 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E;
341 isReachable(I->Dep, TargetSU, Visited, Reached);
344 static bool isReachable(SUnit *SU, SUnit *TargetSU) {
345 SmallPtrSet<SUnit*, 32> Visited;
346 bool Reached = false;
347 isReachable(SU, TargetSU, Visited, Reached);
351 /// willCreateCycle - Returns true if adding an edge from SU to TargetSU will
353 static bool willCreateCycle(SUnit *SU, SUnit *TargetSU) {
354 if (isReachable(TargetSU, SU))
356 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
358 if (I->Cost < 0 && isReachable(TargetSU, I->Dep))
363 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
364 /// BTCycle in order to schedule a specific node. Returns the last unscheduled
365 /// SUnit. Also returns if a successor is unscheduled in the process.
366 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
367 unsigned &CurCycle) {
369 while (CurCycle > BtCycle) {
370 OldSU = Sequence.back();
372 if (SU->isSucc(OldSU))
373 // Don't try to remove SU from AvailableQueue.
374 SU->isAvailable = false;
375 UnscheduleNodeBottomUp(OldSU);
380 if (SU->isSucc(OldSU)) {
381 assert(false && "Something is wrong!");
386 /// isSafeToCopy - True if the SUnit for the given SDNode can safely cloned,
387 /// i.e. the node does not produce a flag, it does not read a flag and it does
388 /// not have an incoming chain.
389 static bool isSafeToCopy(SDNode *N) {
393 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
394 if (N->getValueType(i) == MVT::Flag)
396 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
397 const SDOperand &Op = N->getOperand(i);
398 MVT::ValueType VT = Op.Val->getValueType(Op.ResNo);
399 if (VT == MVT::Other || VT == MVT::Flag)
406 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
407 /// successors to the newly created node.
408 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
409 DOUT << "Duplicating SU # " << SU->NodeNum << "\n";
411 SUnit *NewSU = Clone(SU);
413 // New SUnit has the exact same predecessors.
414 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
417 NewSU->addPred(I->Dep, I->isCtrl, false, I->Reg, I->Cost);
418 NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1);
421 // Only copy scheduled successors. Cut them from old node's successor
422 // list and move them over.
423 SmallVector<SDep*, 2> DelDeps;
424 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
428 NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1);
429 if (I->Dep->isScheduled) {
430 I->Dep->addPred(NewSU, I->isCtrl, false, I->Reg, I->Cost);
431 DelDeps.push_back(I);
434 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
435 SUnit *Succ = DelDeps[i]->Dep;
436 bool isCtrl = DelDeps[i]->isCtrl;
437 Succ->removePred(SU, isCtrl, false);
440 AvailableQueue->updateNode(SU);
441 AvailableQueue->addNode(NewSU);
446 /// InsertCopiesAndMoveSuccs - Insert expensive cross register class copies and
447 /// move all scheduled successors of the given SUnit to the last copy.
448 SUnit *ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
449 const TargetRegisterClass *DestRC,
450 const TargetRegisterClass *SrcRC) {
451 SUnit *CopyFromSU = NewSUnit(NULL);
452 CopyFromSU->CopySrcRC = SrcRC;
453 CopyFromSU->CopyDstRC = DestRC;
454 CopyFromSU->Depth = SU->Depth;
455 CopyFromSU->Height = SU->Height;
457 SUnit *CopyToSU = NewSUnit(NULL);
458 CopyToSU->CopySrcRC = DestRC;
459 CopyToSU->CopyDstRC = SrcRC;
461 // Only copy scheduled successors. Cut them from old node's successor
462 // list and move them over.
463 SmallVector<SDep*, 2> DelDeps;
464 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
468 CopyToSU->Height = std::max(CopyToSU->Height, I->Dep->Height+1);
469 if (I->Dep->isScheduled) {
470 I->Dep->addPred(CopyToSU, I->isCtrl, false, I->Reg, I->Cost);
471 DelDeps.push_back(I);
474 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
475 SUnit *Succ = DelDeps[i]->Dep;
476 bool isCtrl = DelDeps[i]->isCtrl;
477 Succ->removePred(SU, isCtrl, false);
480 CopyFromSU->addPred(SU, false, false, Reg, -1);
481 CopyToSU->addPred(CopyFromSU, false, false, Reg, 1);
483 AvailableQueue->updateNode(SU);
484 AvailableQueue->addNode(CopyFromSU);
485 AvailableQueue->addNode(CopyToSU);
490 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
491 /// definition of the specified node.
492 /// FIXME: Move to SelectionDAG?
493 static MVT::ValueType getPhysicalRegisterVT(SDNode *N, unsigned Reg,
494 const TargetInstrInfo *TII) {
495 const TargetInstrDescriptor &TID = TII->get(N->getTargetOpcode());
496 assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
497 unsigned NumRes = TID.numDefs;
498 for (const unsigned *ImpDef = TID.ImplicitDefs; *ImpDef; ++ImpDef) {
503 return N->getValueType(NumRes);
506 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
507 /// scheduling of the given node to satisfy live physical register dependencies.
508 /// If the specific node is the last one that's available to schedule, do
509 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
510 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, unsigned &CurCycle){
511 if (LiveRegs.empty())
514 // If this node would clobber any "live" register, then it's not ready.
515 // However, if this is the last "available" node, then we may have to
517 bool MustSched = AvailableQueue->empty();
518 SmallVector<unsigned, 4> LRegs;
519 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
522 unsigned Reg = I->Reg;
523 if (LiveRegs.count(Reg) && LiveRegDefs[Reg] != I->Dep)
524 LRegs.push_back(Reg);
525 for (const unsigned *Alias = MRI->getAliasSet(Reg);
527 if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != I->Dep)
528 LRegs.push_back(*Alias);
532 for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) {
533 SDNode *Node = (i == 0) ? SU->Node : SU->FlaggedNodes[i-1];
534 if (!Node || !Node->isTargetOpcode())
536 const TargetInstrDescriptor &TID = TII->get(Node->getTargetOpcode());
537 if (!TID.ImplicitDefs)
539 for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) {
540 if (LiveRegs.count(*Reg) && LiveRegDefs[*Reg] != SU)
541 LRegs.push_back(*Reg);
542 for (const unsigned *Alias = MRI->getAliasSet(*Reg);
544 if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != SU)
545 LRegs.push_back(*Alias);
549 if (MustSched && !LRegs.empty()) {
550 // We have made a mistake by scheduling some nodes too early. Now we must
551 // schedule the current node which will end up clobbering some live
552 // registers that are expensive / impossible to copy. Try unscheduling
553 // up to the point where it's safe to schedule the current node.
554 unsigned LiveCycle = CurCycle;
555 for (unsigned i = 0, e = LRegs.size(); i != e; ++i) {
556 unsigned Reg = LRegs[i];
557 unsigned LCycle = LiveRegCycles[Reg];
558 LiveCycle = std::min(LiveCycle, LCycle);
561 SUnit *OldSU = Sequence[LiveCycle];
562 if (!willCreateCycle(SU, OldSU)) {
563 // If CycleBound is greater than backtrack cycle, then some of SU
564 // successors are going to be unscheduled.
565 bool SuccUnsched = SU->CycleBound > LiveCycle;
566 BacktrackBottomUp(SU, LiveCycle, CurCycle);
567 // Force the current node to be scheduled before the node that
568 // requires the physical reg dep.
569 if (OldSU->isAvailable) {
570 OldSU->isAvailable = false;
571 AvailableQueue->remove(OldSU);
573 SU->addPred(OldSU, true, true);
574 // If a successor has been unscheduled, then it's not possible to
575 // schedule the current node.
578 // Try duplicating the nodes that produces these "expensive to copy"
579 // values to break the dependency.
580 assert(LRegs.size() == 1 && "Can't handle this yet!");
581 unsigned Reg = LRegs[0];
582 SUnit *LRDef = LiveRegDefs[Reg];
584 if (isSafeToCopy(LRDef->Node))
585 NewDef = CopyAndMoveSuccessors(LRDef);
587 // Issue expensive cross register class copies.
588 MVT::ValueType VT = getPhysicalRegisterVT(LRDef->Node, Reg, TII);
589 const TargetRegisterClass *RC =
590 MRI->getPhysicalRegisterRegClass(VT, Reg);
591 const TargetRegisterClass *DestRC = MRI->getCrossCopyRegClass(RC);
593 assert(false && "Don't know how to copy this physical register!");
596 NewDef = InsertCopiesAndMoveSuccs(LRDef,Reg,DestRC,RC);
599 DOUT << "Adding an edge from SU # " << SU->NodeNum
600 << " to SU #" << NewDef->NodeNum << "\n";
601 LiveRegDefs[Reg] = NewDef;
602 NewDef->addPred(SU, true, true);
603 SU->isAvailable = false;
604 AvailableQueue->push(NewDef);
608 return !LRegs.empty();
611 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
613 void ScheduleDAGRRList::ListScheduleBottomUp() {
614 unsigned CurCycle = 0;
615 // Add root to Available queue.
616 SUnit *RootSU = SUnitMap[DAG.getRoot().Val].front();
617 RootSU->isAvailable = true;
618 AvailableQueue->push(RootSU);
620 // While Available queue is not empty, grab the node with the highest
621 // priority. If it is not ready put it back. Schedule the node.
622 SmallVector<SUnit*, 4> NotReady;
623 while (!AvailableQueue->empty()) {
624 SUnit *CurSU = AvailableQueue->pop();
626 if (CurSU->CycleBound <= CurCycle)
627 if (!DelayForLiveRegsBottomUp(CurSU, CurCycle))
630 // Verify node is still ready. It may not be in case the
631 // scheduler has backtracked.
632 if (CurSU->isAvailable) {
633 CurSU->isPending = true;
634 NotReady.push_back(CurSU);
636 CurSU = AvailableQueue->pop();
639 // Add the nodes that aren't ready back onto the available list.
640 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
641 NotReady[i]->isPending = false;
642 if (NotReady[i]->isAvailable)
643 AvailableQueue->push(NotReady[i]);
648 Sequence.push_back(0);
650 ScheduleNodeBottomUp(CurSU, CurCycle);
651 Sequence.push_back(CurSU);
656 // Add entry node last
657 if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
658 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
659 Sequence.push_back(Entry);
662 // Reverse the order if it is bottom up.
663 std::reverse(Sequence.begin(), Sequence.end());
667 // Verify that all SUnits were scheduled.
668 bool AnyNotSched = false;
669 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
670 if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
672 cerr << "*** List scheduling failed! ***\n";
673 SUnits[i].dump(&DAG);
674 cerr << "has not been scheduled!\n";
678 assert(!AnyNotSched);
682 //===----------------------------------------------------------------------===//
683 // Top-Down Scheduling
684 //===----------------------------------------------------------------------===//
686 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
687 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
688 void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain,
690 // FIXME: the distance between two nodes is not always == the predecessor's
691 // latency. For example, the reader can very well read the register written
692 // by the predecessor later than the issue cycle. It also depends on the
693 // interrupt model (drain vs. freeze).
694 SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency);
697 --SuccSU->NumPredsLeft;
699 --SuccSU->NumChainPredsLeft;
702 if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
703 cerr << "*** List scheduling failed! ***\n";
705 cerr << " has been released too many times!\n";
710 if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
711 SuccSU->isAvailable = true;
712 AvailableQueue->push(SuccSU);
717 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
718 /// count of its successors. If a successor pending count is zero, add it to
719 /// the Available queue.
720 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
721 DOUT << "*** Scheduling [" << CurCycle << "]: ";
722 DEBUG(SU->dump(&DAG));
723 SU->Cycle = CurCycle;
725 AvailableQueue->ScheduledNode(SU);
727 // Top down: release successors
728 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
730 ReleaseSucc(I->Dep, I->isCtrl, CurCycle);
731 SU->isScheduled = true;
734 /// ListScheduleTopDown - The main loop of list scheduling for top-down
736 void ScheduleDAGRRList::ListScheduleTopDown() {
737 unsigned CurCycle = 0;
738 SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
740 // All leaves to Available queue.
741 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
742 // It is available if it has no predecessors.
743 if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
744 AvailableQueue->push(&SUnits[i]);
745 SUnits[i].isAvailable = true;
749 // Emit the entry node first.
750 ScheduleNodeTopDown(Entry, CurCycle);
751 Sequence.push_back(Entry);
754 // While Available queue is not empty, grab the node with the highest
755 // priority. If it is not ready put it back. Schedule the node.
756 std::vector<SUnit*> NotReady;
757 while (!AvailableQueue->empty()) {
758 SUnit *CurSU = AvailableQueue->pop();
759 while (CurSU && CurSU->CycleBound > CurCycle) {
760 NotReady.push_back(CurSU);
761 CurSU = AvailableQueue->pop();
764 // Add the nodes that aren't ready back onto the available list.
765 AvailableQueue->push_all(NotReady);
769 Sequence.push_back(0);
771 ScheduleNodeTopDown(CurSU, CurCycle);
772 Sequence.push_back(CurSU);
779 // Verify that all SUnits were scheduled.
780 bool AnyNotSched = false;
781 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
782 if (!SUnits[i].isScheduled) {
784 cerr << "*** List scheduling failed! ***\n";
785 SUnits[i].dump(&DAG);
786 cerr << "has not been scheduled!\n";
790 assert(!AnyNotSched);
796 //===----------------------------------------------------------------------===//
797 // RegReductionPriorityQueue Implementation
798 //===----------------------------------------------------------------------===//
800 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
801 // to reduce register pressure.
805 class RegReductionPriorityQueue;
807 /// Sorting functions for the Available queue.
808 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
809 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
810 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
811 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
813 bool operator()(const SUnit* left, const SUnit* right) const;
816 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
817 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
818 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
819 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
821 bool operator()(const SUnit* left, const SUnit* right) const;
823 } // end anonymous namespace
825 static inline bool isCopyFromLiveIn(const SUnit *SU) {
826 SDNode *N = SU->Node;
827 return N && N->getOpcode() == ISD::CopyFromReg &&
828 N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
833 class VISIBILITY_HIDDEN RegReductionPriorityQueue
834 : public SchedulingPriorityQueue {
835 std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue;
838 RegReductionPriorityQueue() :
841 virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
842 std::vector<SUnit> &sunits) {}
844 virtual void addNode(const SUnit *SU) {}
846 virtual void updateNode(const SUnit *SU) {}
848 virtual void releaseState() {}
850 virtual unsigned getNodePriority(const SUnit *SU) const {
854 unsigned size() const { return Queue.size(); }
856 bool empty() const { return Queue.empty(); }
858 void push(SUnit *U) {
861 void push_all(const std::vector<SUnit *> &Nodes) {
862 for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
863 Queue.push(Nodes[i]);
867 if (empty()) return NULL;
868 SUnit *V = Queue.top();
873 /// remove - This is a really inefficient way to remove a node from a
874 /// priority queue. We should roll our own heap to make this better or
876 void remove(SUnit *SU) {
877 std::vector<SUnit*> Temp;
879 assert(!Queue.empty() && "Not in queue!");
880 while (Queue.top() != SU) {
881 Temp.push_back(Queue.top());
883 assert(!Queue.empty() && "Not in queue!");
886 // Remove the node from the PQ.
889 // Add all the other nodes back.
890 for (unsigned i = 0, e = Temp.size(); i != e; ++i)
896 class VISIBILITY_HIDDEN BURegReductionPriorityQueue
897 : public RegReductionPriorityQueue<SF> {
898 // SUnitMap SDNode to SUnit mapping (n -> n).
899 DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
901 // SUnits - The SUnits for the current graph.
902 const std::vector<SUnit> *SUnits;
904 // SethiUllmanNumbers - The SethiUllman number for each node.
905 std::vector<unsigned> SethiUllmanNumbers;
907 const TargetInstrInfo *TII;
909 explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii)
912 void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
913 std::vector<SUnit> &sunits) {
916 // Add pseudo dependency edges for two-address nodes.
917 AddPseudoTwoAddrDeps();
918 // Calculate node priorities.
919 CalculateSethiUllmanNumbers();
922 void addNode(const SUnit *SU) {
923 SethiUllmanNumbers.resize(SUnits->size(), 0);
924 CalcNodeSethiUllmanNumber(SU);
927 void updateNode(const SUnit *SU) {
928 SethiUllmanNumbers[SU->NodeNum] = 0;
929 CalcNodeSethiUllmanNumber(SU);
932 void releaseState() {
934 SethiUllmanNumbers.clear();
937 unsigned getNodePriority(const SUnit *SU) const {
938 assert(SU->NodeNum < SethiUllmanNumbers.size());
939 unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0;
940 if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU))
941 // CopyFromReg should be close to its def because it restricts
942 // allocation choices. But if it is a livein then perhaps we want it
943 // closer to its uses so it can be coalesced.
945 else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
946 // CopyToReg should be close to its uses to facilitate coalescing and
949 else if (SU->NumSuccs == 0)
950 // If SU does not have a use, i.e. it doesn't produce a value that would
951 // be consumed (e.g. store), then it terminates a chain of computation.
952 // Give it a large SethiUllman number so it will be scheduled right
953 // before its predecessors that it doesn't lengthen their live ranges.
955 else if (SU->NumPreds == 0)
956 // If SU does not have a def, schedule it close to its uses because it
957 // does not lengthen any live ranges.
960 return SethiUllmanNumbers[SU->NodeNum];
964 bool canClobber(SUnit *SU, SUnit *Op);
965 void AddPseudoTwoAddrDeps();
966 void CalculateSethiUllmanNumbers();
967 unsigned CalcNodeSethiUllmanNumber(const SUnit *SU);
972 class VISIBILITY_HIDDEN TDRegReductionPriorityQueue
973 : public RegReductionPriorityQueue<SF> {
974 // SUnitMap SDNode to SUnit mapping (n -> n).
975 DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
977 // SUnits - The SUnits for the current graph.
978 const std::vector<SUnit> *SUnits;
980 // SethiUllmanNumbers - The SethiUllman number for each node.
981 std::vector<unsigned> SethiUllmanNumbers;
984 TDRegReductionPriorityQueue() {}
986 void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
987 std::vector<SUnit> &sunits) {
990 // Calculate node priorities.
991 CalculateSethiUllmanNumbers();
994 void addNode(const SUnit *SU) {
995 SethiUllmanNumbers.resize(SUnits->size(), 0);
996 CalcNodeSethiUllmanNumber(SU);
999 void updateNode(const SUnit *SU) {
1000 SethiUllmanNumbers[SU->NodeNum] = 0;
1001 CalcNodeSethiUllmanNumber(SU);
1004 void releaseState() {
1006 SethiUllmanNumbers.clear();
1009 unsigned getNodePriority(const SUnit *SU) const {
1010 assert(SU->NodeNum < SethiUllmanNumbers.size());
1011 return SethiUllmanNumbers[SU->NodeNum];
1015 void CalculateSethiUllmanNumbers();
1016 unsigned CalcNodeSethiUllmanNumber(const SUnit *SU);
1020 /// closestSucc - Returns the scheduled cycle of the successor which is
1021 /// closet to the current cycle.
1022 static unsigned closestSucc(const SUnit *SU) {
1023 unsigned MaxCycle = 0;
1024 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1026 unsigned Cycle = I->Dep->Cycle;
1027 // If there are bunch of CopyToRegs stacked up, they should be considered
1028 // to be at the same position.
1029 if (I->Dep->Node && I->Dep->Node->getOpcode() == ISD::CopyToReg)
1030 Cycle = closestSucc(I->Dep)+1;
1031 if (Cycle > MaxCycle)
1037 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
1038 /// for scratch registers. Live-in operands and live-out results don't count
1039 /// since they are "fixed".
1040 static unsigned calcMaxScratches(const SUnit *SU) {
1041 unsigned Scratches = 0;
1042 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1044 if (I->isCtrl) continue; // ignore chain preds
1045 if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyFromReg)
1048 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1050 if (I->isCtrl) continue; // ignore chain succs
1051 if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyToReg)
1058 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1059 // There used to be a special tie breaker here that looked for
1060 // two-address instructions and preferred the instruction with a
1061 // def&use operand. The special case triggered diagnostics when
1062 // _GLIBCXX_DEBUG was enabled because it broke the strict weak
1063 // ordering that priority_queue requires. It didn't help much anyway
1064 // because AddPseudoTwoAddrDeps already covers many of the cases
1065 // where it would have applied. In addition, it's counter-intuitive
1066 // that a tie breaker would be the first thing attempted. There's a
1067 // "real" tie breaker below that is the operation of last resort.
1068 // The fact that the "special tie breaker" would trigger when there
1069 // wasn't otherwise a tie is what broke the strict weak ordering
1072 unsigned LPriority = SPQ->getNodePriority(left);
1073 unsigned RPriority = SPQ->getNodePriority(right);
1074 if (LPriority > RPriority)
1076 else if (LPriority == RPriority) {
1077 // Try schedule def + use closer when Sethi-Ullman numbers are the same.
1082 // and the following instructions are both ready.
1086 // Then schedule t2 = op first.
1093 // This creates more short live intervals.
1094 unsigned LDist = closestSucc(left);
1095 unsigned RDist = closestSucc(right);
1098 else if (LDist == RDist) {
1099 // Intuitively, it's good to push down instructions whose results are
1100 // liveout so their long live ranges won't conflict with other values
1101 // which are needed inside the BB. Further prioritize liveout instructions
1102 // by the number of operands which are calculated within the BB.
1103 unsigned LScratch = calcMaxScratches(left);
1104 unsigned RScratch = calcMaxScratches(right);
1105 if (LScratch > RScratch)
1107 else if (LScratch == RScratch)
1108 if (left->Height > right->Height)
1110 else if (left->Height == right->Height)
1111 if (left->Depth < right->Depth)
1113 else if (left->Depth == right->Depth)
1114 if (left->CycleBound > right->CycleBound)
1122 bool BURegReductionPriorityQueue<SF>::canClobber(SUnit *SU, SUnit *Op) {
1123 if (SU->isTwoAddress) {
1124 unsigned Opc = SU->Node->getTargetOpcode();
1125 unsigned NumRes = TII->getNumDefs(Opc);
1126 unsigned NumOps = ScheduleDAG::CountOperands(SU->Node);
1127 for (unsigned i = 0; i != NumOps; ++i) {
1128 if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) != -1) {
1129 SDNode *DU = SU->Node->getOperand(i).Val;
1130 if (Op == (*SUnitMap)[DU][SU->InstanceNo])
1139 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
1140 /// it as a def&use operand. Add a pseudo control edge from it to the other
1141 /// node (if it won't create a cycle) so the two-address one will be scheduled
1142 /// first (lower in the schedule).
1144 void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
1145 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1146 SUnit *SU = (SUnit *)&((*SUnits)[i]);
1147 if (!SU->isTwoAddress)
1150 SDNode *Node = SU->Node;
1151 if (!Node || !Node->isTargetOpcode())
1154 unsigned Opc = Node->getTargetOpcode();
1155 unsigned NumRes = TII->getNumDefs(Opc);
1156 unsigned NumOps = ScheduleDAG::CountOperands(Node);
1157 for (unsigned j = 0; j != NumOps; ++j) {
1158 if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) != -1) {
1159 SDNode *DU = SU->Node->getOperand(j).Val;
1160 SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo];
1161 if (!DUSU) continue;
1162 for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end();
1164 if (I->isCtrl) continue;
1165 SUnit *SuccSU = I->Dep;
1166 // Don't constraint nodes with implicit defs. It can create cycles
1167 // plus it may increase register pressures.
1168 if (SuccSU == SU || SuccSU->hasImplicitDefs)
1170 // Be conservative. Ignore if nodes aren't at the same depth.
1171 if (SuccSU->Depth != SU->Depth)
1173 if ((!canClobber(SuccSU, DUSU) ||
1174 (!SU->isCommutable && SuccSU->isCommutable)) &&
1175 !isReachable(SuccSU, SU)) {
1176 DOUT << "Adding an edge from SU # " << SU->NodeNum
1177 << " to SU #" << SuccSU->NodeNum << "\n";
1178 SU->addPred(SuccSU, true, true);
1186 /// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
1187 /// Smaller number is the higher priority.
1189 unsigned BURegReductionPriorityQueue<SF>::
1190 CalcNodeSethiUllmanNumber(const SUnit *SU) {
1191 unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
1192 if (SethiUllmanNumber != 0)
1193 return SethiUllmanNumber;
1196 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1198 if (I->isCtrl) continue; // ignore chain preds
1199 SUnit *PredSU = I->Dep;
1200 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU);
1201 if (PredSethiUllman > SethiUllmanNumber) {
1202 SethiUllmanNumber = PredSethiUllman;
1204 } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl)
1208 SethiUllmanNumber += Extra;
1210 if (SethiUllmanNumber == 0)
1211 SethiUllmanNumber = 1;
1213 return SethiUllmanNumber;
1216 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1217 /// scheduling units.
1219 void BURegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
1220 SethiUllmanNumbers.assign(SUnits->size(), 0);
1222 for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
1223 CalcNodeSethiUllmanNumber(&(*SUnits)[i]);
1226 static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) {
1228 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1230 SUnit *SuccSU = I->Dep;
1231 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
1232 EE = SuccSU->Preds.end(); II != EE; ++II) {
1233 SUnit *PredSU = II->Dep;
1234 if (!PredSU->isScheduled)
1244 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1245 unsigned LPriority = SPQ->getNodePriority(left);
1246 unsigned RPriority = SPQ->getNodePriority(right);
1247 bool LIsTarget = left->Node && left->Node->isTargetOpcode();
1248 bool RIsTarget = right->Node && right->Node->isTargetOpcode();
1249 bool LIsFloater = LIsTarget && left->NumPreds == 0;
1250 bool RIsFloater = RIsTarget && right->NumPreds == 0;
1251 unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0;
1252 unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0;
1254 if (left->NumSuccs == 0 && right->NumSuccs != 0)
1256 else if (left->NumSuccs != 0 && right->NumSuccs == 0)
1259 // Special tie breaker: if two nodes share a operand, the one that use it
1260 // as a def&use operand is preferred.
1261 if (LIsTarget && RIsTarget) {
1262 if (left->isTwoAddress && !right->isTwoAddress) {
1263 SDNode *DUNode = left->Node->getOperand(0).Val;
1264 if (DUNode->isOperand(right->Node))
1267 if (!left->isTwoAddress && right->isTwoAddress) {
1268 SDNode *DUNode = right->Node->getOperand(0).Val;
1269 if (DUNode->isOperand(left->Node))
1277 if (left->NumSuccs == 1)
1279 if (right->NumSuccs == 1)
1282 if (LPriority+LBonus < RPriority+RBonus)
1284 else if (LPriority == RPriority)
1285 if (left->Depth < right->Depth)
1287 else if (left->Depth == right->Depth)
1288 if (left->NumSuccsLeft > right->NumSuccsLeft)
1290 else if (left->NumSuccsLeft == right->NumSuccsLeft)
1291 if (left->CycleBound > right->CycleBound)
1296 /// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
1297 /// Smaller number is the higher priority.
1299 unsigned TDRegReductionPriorityQueue<SF>::
1300 CalcNodeSethiUllmanNumber(const SUnit *SU) {
1301 unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
1302 if (SethiUllmanNumber != 0)
1303 return SethiUllmanNumber;
1305 unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0;
1306 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
1307 SethiUllmanNumber = 0xffff;
1308 else if (SU->NumSuccsLeft == 0)
1309 // If SU does not have a use, i.e. it doesn't produce a value that would
1310 // be consumed (e.g. store), then it terminates a chain of computation.
1311 // Give it a small SethiUllman number so it will be scheduled right before
1312 // its predecessors that it doesn't lengthen their live ranges.
1313 SethiUllmanNumber = 0;
1314 else if (SU->NumPredsLeft == 0 &&
1315 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
1316 SethiUllmanNumber = 0xffff;
1319 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1321 if (I->isCtrl) continue; // ignore chain preds
1322 SUnit *PredSU = I->Dep;
1323 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU);
1324 if (PredSethiUllman > SethiUllmanNumber) {
1325 SethiUllmanNumber = PredSethiUllman;
1327 } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl)
1331 SethiUllmanNumber += Extra;
1334 return SethiUllmanNumber;
1337 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1338 /// scheduling units.
1340 void TDRegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
1341 SethiUllmanNumbers.assign(SUnits->size(), 0);
1343 for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
1344 CalcNodeSethiUllmanNumber(&(*SUnits)[i]);
1347 //===----------------------------------------------------------------------===//
1348 // Public Constructor Functions
1349 //===----------------------------------------------------------------------===//
1351 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
1353 MachineBasicBlock *BB) {
1354 const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo();
1355 return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true,
1356 new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII));
1359 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS,
1361 MachineBasicBlock *BB) {
1362 return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false,
1363 new TDRegReductionPriorityQueue<td_ls_rr_sort>());