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/ADT/PriorityQueue.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);
57 //===----------------------------------------------------------------------===//
58 /// ScheduleDAGRRList - The actual register reduction list scheduler
59 /// implementation. This supports both top-down and bottom-up scheduling.
61 class ScheduleDAGRRList : public ScheduleDAGSDNodes {
63 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
67 /// AvailableQueue - The priority queue to use for the available SUnits.
68 SchedulingPriorityQueue *AvailableQueue;
70 /// LiveRegDefs - A set of physical registers and their definition
71 /// that are "live". These nodes must be scheduled before any other nodes that
72 /// modifies the registers can be scheduled.
74 std::vector<SUnit*> LiveRegDefs;
75 std::vector<unsigned> LiveRegCycles;
77 /// Topo - A topological ordering for SUnits which permits fast IsReachable
78 /// and similar queries.
79 ScheduleDAGTopologicalSort Topo;
82 ScheduleDAGRRList(MachineFunction &mf,
84 SchedulingPriorityQueue *availqueue)
85 : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup),
86 AvailableQueue(availqueue), Topo(SUnits) {
89 ~ScheduleDAGRRList() {
90 delete AvailableQueue;
95 /// IsReachable - Checks if SU is reachable from TargetSU.
96 bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
97 return Topo.IsReachable(SU, TargetSU);
100 /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
102 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
103 return Topo.WillCreateCycle(SU, TargetSU);
106 /// AddPred - adds a predecessor edge to SUnit SU.
107 /// This returns true if this is a new predecessor.
108 /// Updates the topological ordering if required.
109 void AddPred(SUnit *SU, const SDep &D) {
110 Topo.AddPred(SU, D.getSUnit());
114 /// RemovePred - removes a predecessor edge from SUnit SU.
115 /// This returns true if an edge was removed.
116 /// Updates the topological ordering if required.
117 void RemovePred(SUnit *SU, const SDep &D) {
118 Topo.RemovePred(SU, D.getSUnit());
123 void ReleasePred(SUnit *SU, const SDep *PredEdge);
124 void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
125 void ReleaseSucc(SUnit *SU, const SDep *SuccEdge);
126 void ReleaseSuccessors(SUnit *SU);
127 void CapturePred(SDep *PredEdge);
128 void ScheduleNodeBottomUp(SUnit*, unsigned);
129 void ScheduleNodeTopDown(SUnit*, unsigned);
130 void UnscheduleNodeBottomUp(SUnit*);
131 void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
132 SUnit *CopyAndMoveSuccessors(SUnit*);
133 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
134 const TargetRegisterClass*,
135 const TargetRegisterClass*,
136 SmallVector<SUnit*, 2>&);
137 bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
138 void ListScheduleTopDown();
139 void ListScheduleBottomUp();
142 /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
143 /// Updates the topological ordering if required.
144 SUnit *CreateNewSUnit(SDNode *N) {
145 unsigned NumSUnits = SUnits.size();
146 SUnit *NewNode = NewSUnit(N);
147 // Update the topological ordering.
148 if (NewNode->NodeNum >= NumSUnits)
149 Topo.InitDAGTopologicalSorting();
153 /// CreateClone - Creates a new SUnit from an existing one.
154 /// Updates the topological ordering if required.
155 SUnit *CreateClone(SUnit *N) {
156 unsigned NumSUnits = SUnits.size();
157 SUnit *NewNode = Clone(N);
158 // Update the topological ordering.
159 if (NewNode->NodeNum >= NumSUnits)
160 Topo.InitDAGTopologicalSorting();
164 /// ForceUnitLatencies - Return true, since register-pressure-reducing
165 /// scheduling doesn't need actual latency information.
166 bool ForceUnitLatencies() const { return true; }
168 } // end anonymous namespace
171 /// Schedule - Schedule the DAG using list scheduling.
172 void ScheduleDAGRRList::Schedule() {
173 DEBUG(dbgs() << "********** List Scheduling **********\n");
176 LiveRegDefs.resize(TRI->getNumRegs(), NULL);
177 LiveRegCycles.resize(TRI->getNumRegs(), 0);
179 // Build the scheduling graph.
180 BuildSchedGraph(NULL);
182 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
183 SUnits[su].dumpAll(this));
184 Topo.InitDAGTopologicalSorting();
186 AvailableQueue->initNodes(SUnits);
188 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
190 ListScheduleBottomUp();
192 ListScheduleTopDown();
194 AvailableQueue->releaseState();
197 //===----------------------------------------------------------------------===//
198 // Bottom-Up Scheduling
199 //===----------------------------------------------------------------------===//
201 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
202 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
203 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
204 SUnit *PredSU = PredEdge->getSUnit();
207 if (PredSU->NumSuccsLeft == 0) {
208 dbgs() << "*** Scheduling failed! ***\n";
210 dbgs() << " has been released too many times!\n";
214 --PredSU->NumSuccsLeft;
216 // If all the node's successors are scheduled, this node is ready
217 // to be scheduled. Ignore the special EntrySU node.
218 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
219 PredSU->isAvailable = true;
220 AvailableQueue->push(PredSU);
224 void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
225 // Bottom up: release predecessors
226 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
228 ReleasePred(SU, &*I);
229 if (I->isAssignedRegDep()) {
230 // This is a physical register dependency and it's impossible or
231 // expensive to copy the register. Make sure nothing that can
232 // clobber the register is scheduled between the predecessor and
234 if (!LiveRegDefs[I->getReg()]) {
236 LiveRegDefs[I->getReg()] = I->getSUnit();
237 LiveRegCycles[I->getReg()] = CurCycle;
243 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
244 /// count of its predecessors. If a predecessor pending count is zero, add it to
245 /// the Available queue.
246 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
247 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
248 DEBUG(SU->dump(this));
250 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
251 SU->setHeightToAtLeast(CurCycle);
252 Sequence.push_back(SU);
254 ReleasePredecessors(SU, CurCycle);
256 // Release all the implicit physical register defs that are live.
257 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
259 if (I->isAssignedRegDep()) {
260 if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) {
261 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
262 assert(LiveRegDefs[I->getReg()] == SU &&
263 "Physical register dependency violated?");
265 LiveRegDefs[I->getReg()] = NULL;
266 LiveRegCycles[I->getReg()] = 0;
271 SU->isScheduled = true;
272 AvailableQueue->ScheduledNode(SU);
275 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
276 /// unscheduled, incrcease the succ left count of its predecessors. Remove
277 /// them from AvailableQueue if necessary.
278 void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
279 SUnit *PredSU = PredEdge->getSUnit();
280 if (PredSU->isAvailable) {
281 PredSU->isAvailable = false;
282 if (!PredSU->isPending)
283 AvailableQueue->remove(PredSU);
286 assert(PredSU->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
287 ++PredSU->NumSuccsLeft;
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 DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
294 DEBUG(SU->dump(this));
296 AvailableQueue->UnscheduledNode(SU);
298 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
301 if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) {
302 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
303 assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
304 "Physical register dependency violated?");
306 LiveRegDefs[I->getReg()] = NULL;
307 LiveRegCycles[I->getReg()] = 0;
311 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
313 if (I->isAssignedRegDep()) {
314 if (!LiveRegDefs[I->getReg()]) {
315 LiveRegDefs[I->getReg()] = SU;
318 if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()])
319 LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight();
323 SU->setHeightDirty();
324 SU->isScheduled = false;
325 SU->isAvailable = true;
326 AvailableQueue->push(SU);
329 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
330 /// BTCycle in order to schedule a specific node.
331 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
332 unsigned &CurCycle) {
334 while (CurCycle > BtCycle) {
335 OldSU = Sequence.back();
337 if (SU->isSucc(OldSU))
338 // Don't try to remove SU from AvailableQueue.
339 SU->isAvailable = false;
340 UnscheduleNodeBottomUp(OldSU);
344 assert(!SU->isSucc(OldSU) && "Something is wrong!");
349 static bool isOperandOf(const SUnit *SU, SDNode *N) {
350 for (const SDNode *SUNode = SU->getNode(); SUNode;
351 SUNode = SUNode->getFlaggedNode()) {
352 if (SUNode->isOperandOf(N))
358 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
359 /// successors to the newly created node.
360 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
361 if (SU->getNode()->getFlaggedNode())
364 SDNode *N = SU->getNode();
369 bool TryUnfold = false;
370 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
371 EVT VT = N->getValueType(i);
374 else if (VT == MVT::Other)
377 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
378 const SDValue &Op = N->getOperand(i);
379 EVT VT = Op.getNode()->getValueType(Op.getResNo());
385 SmallVector<SDNode*, 2> NewNodes;
386 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
389 DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n");
390 assert(NewNodes.size() == 2 && "Expected a load folding node!");
393 SDNode *LoadNode = NewNodes[0];
394 unsigned NumVals = N->getNumValues();
395 unsigned OldNumVals = SU->getNode()->getNumValues();
396 for (unsigned i = 0; i != NumVals; ++i)
397 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
398 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
399 SDValue(LoadNode, 1));
401 // LoadNode may already exist. This can happen when there is another
402 // load from the same location and producing the same type of value
403 // but it has different alignment or volatileness.
404 bool isNewLoad = true;
406 if (LoadNode->getNodeId() != -1) {
407 LoadSU = &SUnits[LoadNode->getNodeId()];
410 LoadSU = CreateNewSUnit(LoadNode);
411 LoadNode->setNodeId(LoadSU->NodeNum);
412 ComputeLatency(LoadSU);
415 SUnit *NewSU = CreateNewSUnit(N);
416 assert(N->getNodeId() == -1 && "Node already inserted!");
417 N->setNodeId(NewSU->NodeNum);
419 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
420 for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
421 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
422 NewSU->isTwoAddress = true;
426 if (TID.isCommutable())
427 NewSU->isCommutable = true;
428 ComputeLatency(NewSU);
430 // Record all the edges to and from the old SU, by category.
431 SmallVector<SDep, 4> ChainPreds;
432 SmallVector<SDep, 4> ChainSuccs;
433 SmallVector<SDep, 4> LoadPreds;
434 SmallVector<SDep, 4> NodePreds;
435 SmallVector<SDep, 4> NodeSuccs;
436 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
439 ChainPreds.push_back(*I);
440 else if (isOperandOf(I->getSUnit(), LoadNode))
441 LoadPreds.push_back(*I);
443 NodePreds.push_back(*I);
445 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
448 ChainSuccs.push_back(*I);
450 NodeSuccs.push_back(*I);
453 // Now assign edges to the newly-created nodes.
454 for (unsigned i = 0, e = ChainPreds.size(); i != e; ++i) {
455 const SDep &Pred = ChainPreds[i];
456 RemovePred(SU, Pred);
458 AddPred(LoadSU, Pred);
460 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
461 const SDep &Pred = LoadPreds[i];
462 RemovePred(SU, Pred);
464 AddPred(LoadSU, Pred);
466 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
467 const SDep &Pred = NodePreds[i];
468 RemovePred(SU, Pred);
469 AddPred(NewSU, Pred);
471 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
472 SDep D = NodeSuccs[i];
473 SUnit *SuccDep = D.getSUnit();
475 RemovePred(SuccDep, D);
479 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
480 SDep D = ChainSuccs[i];
481 SUnit *SuccDep = D.getSUnit();
483 RemovePred(SuccDep, D);
490 // Add a data dependency to reflect that NewSU reads the value defined
492 AddPred(NewSU, SDep(LoadSU, SDep::Data, LoadSU->Latency));
495 AvailableQueue->addNode(LoadSU);
496 AvailableQueue->addNode(NewSU);
500 if (NewSU->NumSuccsLeft == 0) {
501 NewSU->isAvailable = true;
507 DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n");
508 NewSU = CreateClone(SU);
510 // New SUnit has the exact same predecessors.
511 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
513 if (!I->isArtificial())
516 // Only copy scheduled successors. Cut them from old node's successor
517 // list and move them over.
518 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
519 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
521 if (I->isArtificial())
523 SUnit *SuccSU = I->getSUnit();
524 if (SuccSU->isScheduled) {
529 DelDeps.push_back(std::make_pair(SuccSU, D));
532 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
533 RemovePred(DelDeps[i].first, DelDeps[i].second);
535 AvailableQueue->updateNode(SU);
536 AvailableQueue->addNode(NewSU);
542 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
543 /// scheduled successors of the given SUnit to the last copy.
544 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
545 const TargetRegisterClass *DestRC,
546 const TargetRegisterClass *SrcRC,
547 SmallVector<SUnit*, 2> &Copies) {
548 SUnit *CopyFromSU = CreateNewSUnit(NULL);
549 CopyFromSU->CopySrcRC = SrcRC;
550 CopyFromSU->CopyDstRC = DestRC;
552 SUnit *CopyToSU = CreateNewSUnit(NULL);
553 CopyToSU->CopySrcRC = DestRC;
554 CopyToSU->CopyDstRC = SrcRC;
556 // Only copy scheduled successors. Cut them from old node's successor
557 // list and move them over.
558 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
559 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
561 if (I->isArtificial())
563 SUnit *SuccSU = I->getSUnit();
564 if (SuccSU->isScheduled) {
566 D.setSUnit(CopyToSU);
568 DelDeps.push_back(std::make_pair(SuccSU, *I));
571 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
572 RemovePred(DelDeps[i].first, DelDeps[i].second);
574 AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
575 AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
577 AvailableQueue->updateNode(SU);
578 AvailableQueue->addNode(CopyFromSU);
579 AvailableQueue->addNode(CopyToSU);
580 Copies.push_back(CopyFromSU);
581 Copies.push_back(CopyToSU);
586 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
587 /// definition of the specified node.
588 /// FIXME: Move to SelectionDAG?
589 static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
590 const TargetInstrInfo *TII) {
591 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
592 assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
593 unsigned NumRes = TID.getNumDefs();
594 for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
599 return N->getValueType(NumRes);
602 /// CheckForLiveRegDef - Return true and update live register vector if the
603 /// specified register def of the specified SUnit clobbers any "live" registers.
604 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
605 std::vector<SUnit*> &LiveRegDefs,
606 SmallSet<unsigned, 4> &RegAdded,
607 SmallVector<unsigned, 4> &LRegs,
608 const TargetRegisterInfo *TRI) {
610 if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != SU) {
611 if (RegAdded.insert(Reg)) {
612 LRegs.push_back(Reg);
616 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias)
617 if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) {
618 if (RegAdded.insert(*Alias)) {
619 LRegs.push_back(*Alias);
626 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
627 /// scheduling of the given node to satisfy live physical register dependencies.
628 /// If the specific node is the last one that's available to schedule, do
629 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
630 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU,
631 SmallVector<unsigned, 4> &LRegs){
632 if (NumLiveRegs == 0)
635 SmallSet<unsigned, 4> RegAdded;
636 // If this node would clobber any "live" register, then it's not ready.
637 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
639 if (I->isAssignedRegDep())
640 CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs,
641 RegAdded, LRegs, TRI);
644 for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) {
645 if (Node->getOpcode() == ISD::INLINEASM) {
646 // Inline asm can clobber physical defs.
647 unsigned NumOps = Node->getNumOperands();
648 if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
649 --NumOps; // Ignore the flag operand.
651 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
653 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
654 unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
656 ++i; // Skip the ID value.
657 if (InlineAsm::isRegDefKind(Flags) ||
658 InlineAsm::isRegDefEarlyClobberKind(Flags)) {
659 // Check for def of register or earlyclobber register.
660 for (; NumVals; --NumVals, ++i) {
661 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
662 if (TargetRegisterInfo::isPhysicalRegister(Reg))
663 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
671 if (!Node->isMachineOpcode())
673 const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode());
674 if (!TID.ImplicitDefs)
676 for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg)
677 CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
679 return !LRegs.empty();
683 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
685 void ScheduleDAGRRList::ListScheduleBottomUp() {
686 unsigned CurCycle = 0;
688 // Release any predecessors of the special Exit node.
689 ReleasePredecessors(&ExitSU, CurCycle);
691 // Add root to Available queue.
692 if (!SUnits.empty()) {
693 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
694 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
695 RootSU->isAvailable = true;
696 AvailableQueue->push(RootSU);
699 // While Available queue is not empty, grab the node with the highest
700 // priority. If it is not ready put it back. Schedule the node.
701 SmallVector<SUnit*, 4> NotReady;
702 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
703 Sequence.reserve(SUnits.size());
704 while (!AvailableQueue->empty()) {
705 bool Delayed = false;
707 SUnit *CurSU = AvailableQueue->pop();
709 SmallVector<unsigned, 4> LRegs;
710 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
713 LRegsMap.insert(std::make_pair(CurSU, LRegs));
715 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
716 NotReady.push_back(CurSU);
717 CurSU = AvailableQueue->pop();
720 // All candidates are delayed due to live physical reg dependencies.
721 // Try backtracking, code duplication, or inserting cross class copies
723 if (Delayed && !CurSU) {
724 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
725 SUnit *TrySU = NotReady[i];
726 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
728 // Try unscheduling up to the point where it's safe to schedule
730 unsigned LiveCycle = CurCycle;
731 for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
732 unsigned Reg = LRegs[j];
733 unsigned LCycle = LiveRegCycles[Reg];
734 LiveCycle = std::min(LiveCycle, LCycle);
736 SUnit *OldSU = Sequence[LiveCycle];
737 if (!WillCreateCycle(TrySU, OldSU)) {
738 BacktrackBottomUp(TrySU, LiveCycle, CurCycle);
739 // Force the current node to be scheduled before the node that
740 // requires the physical reg dep.
741 if (OldSU->isAvailable) {
742 OldSU->isAvailable = false;
743 AvailableQueue->remove(OldSU);
745 AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
746 /*Reg=*/0, /*isNormalMemory=*/false,
747 /*isMustAlias=*/false, /*isArtificial=*/true));
748 // If one or more successors has been unscheduled, then the current
749 // node is no longer avaialable. Schedule a successor that's now
750 // available instead.
751 if (!TrySU->isAvailable)
752 CurSU = AvailableQueue->pop();
755 TrySU->isPending = false;
756 NotReady.erase(NotReady.begin()+i);
763 // Can't backtrack. If it's too expensive to copy the value, then try
764 // duplicate the nodes that produces these "too expensive to copy"
765 // values to break the dependency. In case even that doesn't work,
766 // insert cross class copies.
767 // If it's not too expensive, i.e. cost != -1, issue copies.
768 SUnit *TrySU = NotReady[0];
769 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
770 assert(LRegs.size() == 1 && "Can't handle this yet!");
771 unsigned Reg = LRegs[0];
772 SUnit *LRDef = LiveRegDefs[Reg];
773 EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
774 const TargetRegisterClass *RC =
775 TRI->getPhysicalRegisterRegClass(Reg, VT);
776 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
778 // If cross copy register class is null, then it must be possible copy
779 // the value directly. Do not try duplicate the def.
782 NewDef = CopyAndMoveSuccessors(LRDef);
786 // Issue copies, these can be expensive cross register class copies.
787 SmallVector<SUnit*, 2> Copies;
788 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
789 DEBUG(dbgs() << "Adding an edge from SU #" << TrySU->NodeNum
790 << " to SU #" << Copies.front()->NodeNum << "\n");
791 AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
792 /*Reg=*/0, /*isNormalMemory=*/false,
793 /*isMustAlias=*/false,
794 /*isArtificial=*/true));
795 NewDef = Copies.back();
798 DEBUG(dbgs() << "Adding an edge from SU #" << NewDef->NodeNum
799 << " to SU #" << TrySU->NodeNum << "\n");
800 LiveRegDefs[Reg] = NewDef;
801 AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
802 /*Reg=*/0, /*isNormalMemory=*/false,
803 /*isMustAlias=*/false,
804 /*isArtificial=*/true));
805 TrySU->isAvailable = false;
809 assert(CurSU && "Unable to resolve live physical register dependencies!");
812 // Add the nodes that aren't ready back onto the available list.
813 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
814 NotReady[i]->isPending = false;
815 // May no longer be available due to backtracking.
816 if (NotReady[i]->isAvailable)
817 AvailableQueue->push(NotReady[i]);
822 ScheduleNodeBottomUp(CurSU, CurCycle);
826 // Reverse the order if it is bottom up.
827 std::reverse(Sequence.begin(), Sequence.end());
830 VerifySchedule(isBottomUp);
834 //===----------------------------------------------------------------------===//
835 // Top-Down Scheduling
836 //===----------------------------------------------------------------------===//
838 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
839 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
840 void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) {
841 SUnit *SuccSU = SuccEdge->getSUnit();
844 if (SuccSU->NumPredsLeft == 0) {
845 dbgs() << "*** Scheduling failed! ***\n";
847 dbgs() << " has been released too many times!\n";
851 --SuccSU->NumPredsLeft;
853 // If all the node's predecessors are scheduled, this node is ready
854 // to be scheduled. Ignore the special ExitSU node.
855 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {
856 SuccSU->isAvailable = true;
857 AvailableQueue->push(SuccSU);
861 void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) {
862 // Top down: release successors
863 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
865 assert(!I->isAssignedRegDep() &&
866 "The list-tdrr scheduler doesn't yet support physreg dependencies!");
868 ReleaseSucc(SU, &*I);
872 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
873 /// count of its successors. If a successor pending count is zero, add it to
874 /// the Available queue.
875 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
876 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
877 DEBUG(SU->dump(this));
879 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
880 SU->setDepthToAtLeast(CurCycle);
881 Sequence.push_back(SU);
883 ReleaseSuccessors(SU);
884 SU->isScheduled = true;
885 AvailableQueue->ScheduledNode(SU);
888 /// ListScheduleTopDown - The main loop of list scheduling for top-down
890 void ScheduleDAGRRList::ListScheduleTopDown() {
891 unsigned CurCycle = 0;
893 // Release any successors of the special Entry node.
894 ReleaseSuccessors(&EntrySU);
896 // All leaves to Available queue.
897 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
898 // It is available if it has no predecessors.
899 if (SUnits[i].Preds.empty()) {
900 AvailableQueue->push(&SUnits[i]);
901 SUnits[i].isAvailable = true;
905 // While Available queue is not empty, grab the node with the highest
906 // priority. If it is not ready put it back. Schedule the node.
907 Sequence.reserve(SUnits.size());
908 while (!AvailableQueue->empty()) {
909 SUnit *CurSU = AvailableQueue->pop();
912 ScheduleNodeTopDown(CurSU, CurCycle);
917 VerifySchedule(isBottomUp);
922 //===----------------------------------------------------------------------===//
923 // RegReductionPriorityQueue Implementation
924 //===----------------------------------------------------------------------===//
926 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
927 // to reduce register pressure.
931 class RegReductionPriorityQueue;
933 /// Sorting functions for the Available queue.
934 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
935 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
936 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
937 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
939 bool operator()(const SUnit* left, const SUnit* right) const;
942 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
943 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
944 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
945 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
947 bool operator()(const SUnit* left, const SUnit* right) const;
950 struct src_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
951 RegReductionPriorityQueue<src_ls_rr_sort> *SPQ;
952 src_ls_rr_sort(RegReductionPriorityQueue<src_ls_rr_sort> *spq)
954 src_ls_rr_sort(const src_ls_rr_sort &RHS)
957 bool operator()(const SUnit* left, const SUnit* right) const;
959 } // end anonymous namespace
961 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
962 /// Smaller number is the higher priority.
964 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
965 unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
966 if (SethiUllmanNumber != 0)
967 return SethiUllmanNumber;
970 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
972 if (I->isCtrl()) continue; // ignore chain preds
973 SUnit *PredSU = I->getSUnit();
974 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
975 if (PredSethiUllman > SethiUllmanNumber) {
976 SethiUllmanNumber = PredSethiUllman;
978 } else if (PredSethiUllman == SethiUllmanNumber)
982 SethiUllmanNumber += Extra;
984 if (SethiUllmanNumber == 0)
985 SethiUllmanNumber = 1;
987 return SethiUllmanNumber;
992 class RegReductionPriorityQueue : public SchedulingPriorityQueue {
993 PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue;
994 unsigned currentQueueId;
997 // SUnits - The SUnits for the current graph.
998 std::vector<SUnit> *SUnits;
1000 const TargetInstrInfo *TII;
1001 const TargetRegisterInfo *TRI;
1002 ScheduleDAGRRList *scheduleDAG;
1004 // SethiUllmanNumbers - The SethiUllman number for each node.
1005 std::vector<unsigned> SethiUllmanNumbers;
1008 RegReductionPriorityQueue(const TargetInstrInfo *tii,
1009 const TargetRegisterInfo *tri)
1010 : Queue(SF(this)), currentQueueId(0),
1011 TII(tii), TRI(tri), scheduleDAG(NULL) {}
1013 void initNodes(std::vector<SUnit> &sunits) {
1015 // Add pseudo dependency edges for two-address nodes.
1016 AddPseudoTwoAddrDeps();
1017 // Reroute edges to nodes with multiple uses.
1018 PrescheduleNodesWithMultipleUses();
1019 // Calculate node priorities.
1020 CalculateSethiUllmanNumbers();
1023 void addNode(const SUnit *SU) {
1024 unsigned SUSize = SethiUllmanNumbers.size();
1025 if (SUnits->size() > SUSize)
1026 SethiUllmanNumbers.resize(SUSize*2, 0);
1027 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1030 void updateNode(const SUnit *SU) {
1031 SethiUllmanNumbers[SU->NodeNum] = 0;
1032 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1035 void releaseState() {
1037 SethiUllmanNumbers.clear();
1040 unsigned getNodePriority(const SUnit *SU) const {
1041 assert(SU->NodeNum < SethiUllmanNumbers.size());
1042 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
1043 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
1044 // CopyToReg should be close to its uses to facilitate coalescing and
1047 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
1048 Opc == TargetOpcode::SUBREG_TO_REG ||
1049 Opc == TargetOpcode::INSERT_SUBREG)
1050 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
1051 // close to their uses to facilitate coalescing.
1053 if (SU->NumSuccs == 0 && SU->NumPreds != 0)
1054 // If SU does not have a register use, i.e. it doesn't produce a value
1055 // that would be consumed (e.g. store), then it terminates a chain of
1056 // computation. Give it a large SethiUllman number so it will be
1057 // scheduled right before its predecessors that it doesn't lengthen
1058 // their live ranges.
1060 if (SU->NumPreds == 0 && SU->NumSuccs != 0)
1061 // If SU does not have a register def, schedule it close to its uses
1062 // because it does not lengthen any live ranges.
1064 return SethiUllmanNumbers[SU->NodeNum];
1067 unsigned getNodeOrdering(const SUnit *SU) const {
1068 return scheduleDAG->DAG->GetOrdering(SU->getNode());
1071 unsigned size() const { return Queue.size(); }
1073 bool empty() const { return Queue.empty(); }
1075 void push(SUnit *U) {
1076 assert(!U->NodeQueueId && "Node in the queue already");
1077 U->NodeQueueId = ++currentQueueId;
1081 void push_all(const std::vector<SUnit *> &Nodes) {
1082 for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
1087 if (empty()) return NULL;
1088 SUnit *V = Queue.top();
1094 void remove(SUnit *SU) {
1095 assert(!Queue.empty() && "Queue is empty!");
1096 assert(SU->NodeQueueId != 0 && "Not in queue!");
1097 Queue.erase_one(SU);
1098 SU->NodeQueueId = 0;
1101 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1102 scheduleDAG = scheduleDag;
1106 bool canClobber(const SUnit *SU, const SUnit *Op);
1107 void AddPseudoTwoAddrDeps();
1108 void PrescheduleNodesWithMultipleUses();
1109 void CalculateSethiUllmanNumbers();
1112 typedef RegReductionPriorityQueue<bu_ls_rr_sort>
1113 BURegReductionPriorityQueue;
1115 typedef RegReductionPriorityQueue<td_ls_rr_sort>
1116 TDRegReductionPriorityQueue;
1118 typedef RegReductionPriorityQueue<src_ls_rr_sort>
1119 SrcRegReductionPriorityQueue;
1122 /// closestSucc - Returns the scheduled cycle of the successor which is
1123 /// closest to the current cycle.
1124 static unsigned closestSucc(const SUnit *SU) {
1125 unsigned MaxHeight = 0;
1126 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1128 if (I->isCtrl()) continue; // ignore chain succs
1129 unsigned Height = I->getSUnit()->getHeight();
1130 // If there are bunch of CopyToRegs stacked up, they should be considered
1131 // to be at the same position.
1132 if (I->getSUnit()->getNode() &&
1133 I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
1134 Height = closestSucc(I->getSUnit())+1;
1135 if (Height > MaxHeight)
1141 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
1142 /// for scratch registers, i.e. number of data dependencies.
1143 static unsigned calcMaxScratches(const SUnit *SU) {
1144 unsigned Scratches = 0;
1145 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1147 if (I->isCtrl()) continue; // ignore chain preds
1153 template <typename RRSort>
1154 static bool BURRSort(const SUnit *left, const SUnit *right,
1155 const RegReductionPriorityQueue<RRSort> *SPQ) {
1156 unsigned LPriority = SPQ->getNodePriority(left);
1157 unsigned RPriority = SPQ->getNodePriority(right);
1158 if (LPriority != RPriority)
1159 return LPriority > RPriority;
1161 // Try schedule def + use closer when Sethi-Ullman numbers are the same.
1166 // and the following instructions are both ready.
1170 // Then schedule t2 = op first.
1177 // This creates more short live intervals.
1178 unsigned LDist = closestSucc(left);
1179 unsigned RDist = closestSucc(right);
1181 return LDist < RDist;
1183 // How many registers becomes live when the node is scheduled.
1184 unsigned LScratch = calcMaxScratches(left);
1185 unsigned RScratch = calcMaxScratches(right);
1186 if (LScratch != RScratch)
1187 return LScratch > RScratch;
1189 if (left->getHeight() != right->getHeight())
1190 return left->getHeight() > right->getHeight();
1192 if (left->getDepth() != right->getDepth())
1193 return left->getDepth() < right->getDepth();
1195 assert(left->NodeQueueId && right->NodeQueueId &&
1196 "NodeQueueId cannot be zero");
1197 return (left->NodeQueueId > right->NodeQueueId);
1201 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1202 return BURRSort(left, right, SPQ);
1205 // Source order, otherwise bottom up.
1206 bool src_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const{
1207 unsigned LOrder = SPQ->getNodeOrdering(left);
1208 unsigned ROrder = SPQ->getNodeOrdering(right);
1210 // Prefer an ordering where the lower the non-zero order number, the higher
1212 if ((LOrder || ROrder) && LOrder != ROrder)
1213 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
1215 return BURRSort(left, right, SPQ);
1220 RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) {
1221 if (SU->isTwoAddress) {
1222 unsigned Opc = SU->getNode()->getMachineOpcode();
1223 const TargetInstrDesc &TID = TII->get(Opc);
1224 unsigned NumRes = TID.getNumDefs();
1225 unsigned NumOps = TID.getNumOperands() - NumRes;
1226 for (unsigned i = 0; i != NumOps; ++i) {
1227 if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
1228 SDNode *DU = SU->getNode()->getOperand(i).getNode();
1229 if (DU->getNodeId() != -1 &&
1230 Op->OrigNode == &(*SUnits)[DU->getNodeId()])
1238 /// hasCopyToRegUse - Return true if SU has a value successor that is a
1240 static bool hasCopyToRegUse(const SUnit *SU) {
1241 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1243 if (I->isCtrl()) continue;
1244 const SUnit *SuccSU = I->getSUnit();
1245 if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
1251 /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
1252 /// physical register defs.
1253 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
1254 const TargetInstrInfo *TII,
1255 const TargetRegisterInfo *TRI) {
1256 SDNode *N = SuccSU->getNode();
1257 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1258 const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
1259 assert(ImpDefs && "Caller should check hasPhysRegDefs");
1260 for (const SDNode *SUNode = SU->getNode(); SUNode;
1261 SUNode = SUNode->getFlaggedNode()) {
1262 if (!SUNode->isMachineOpcode())
1264 const unsigned *SUImpDefs =
1265 TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
1268 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
1269 EVT VT = N->getValueType(i);
1270 if (VT == MVT::Flag || VT == MVT::Other)
1272 if (!N->hasAnyUseOfValue(i))
1274 unsigned Reg = ImpDefs[i - NumDefs];
1275 for (;*SUImpDefs; ++SUImpDefs) {
1276 unsigned SUReg = *SUImpDefs;
1277 if (TRI->regsOverlap(Reg, SUReg))
1285 /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
1286 /// are not handled well by the general register pressure reduction
1287 /// heuristics. When presented with code like this:
1296 /// the heuristics tend to push the store up, but since the
1297 /// operand of the store has another use (U), this would increase
1298 /// the length of that other use (the U->N edge).
1300 /// This function transforms code like the above to route U's
1301 /// dependence through the store when possible, like this:
1312 /// This results in the store being scheduled immediately
1313 /// after N, which shortens the U->N live range, reducing
1314 /// register pressure.
1317 void RegReductionPriorityQueue<SF>::PrescheduleNodesWithMultipleUses() {
1318 // Visit all the nodes in topological order, working top-down.
1319 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1320 SUnit *SU = &(*SUnits)[i];
1321 // For now, only look at nodes with no data successors, such as stores.
1322 // These are especially important, due to the heuristics in
1323 // getNodePriority for nodes with no data successors.
1324 if (SU->NumSuccs != 0)
1326 // For now, only look at nodes with exactly one data predecessor.
1327 if (SU->NumPreds != 1)
1329 // Avoid prescheduling copies to virtual registers, which don't behave
1330 // like other nodes from the perspective of scheduling heuristics.
1331 if (SDNode *N = SU->getNode())
1332 if (N->getOpcode() == ISD::CopyToReg &&
1333 TargetRegisterInfo::isVirtualRegister
1334 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1337 // Locate the single data predecessor.
1339 for (SUnit::const_pred_iterator II = SU->Preds.begin(),
1340 EE = SU->Preds.end(); II != EE; ++II)
1341 if (!II->isCtrl()) {
1342 PredSU = II->getSUnit();
1347 // Don't rewrite edges that carry physregs, because that requires additional
1348 // support infrastructure.
1349 if (PredSU->hasPhysRegDefs)
1351 // Short-circuit the case where SU is PredSU's only data successor.
1352 if (PredSU->NumSuccs == 1)
1354 // Avoid prescheduling to copies from virtual registers, which don't behave
1355 // like other nodes from the perspective of scheduling // heuristics.
1356 if (SDNode *N = SU->getNode())
1357 if (N->getOpcode() == ISD::CopyFromReg &&
1358 TargetRegisterInfo::isVirtualRegister
1359 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1362 // Perform checks on the successors of PredSU.
1363 for (SUnit::const_succ_iterator II = PredSU->Succs.begin(),
1364 EE = PredSU->Succs.end(); II != EE; ++II) {
1365 SUnit *PredSuccSU = II->getSUnit();
1366 if (PredSuccSU == SU) continue;
1367 // If PredSU has another successor with no data successors, for
1368 // now don't attempt to choose either over the other.
1369 if (PredSuccSU->NumSuccs == 0)
1370 goto outer_loop_continue;
1371 // Don't break physical register dependencies.
1372 if (SU->hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
1373 if (canClobberPhysRegDefs(PredSuccSU, SU, TII, TRI))
1374 goto outer_loop_continue;
1375 // Don't introduce graph cycles.
1376 if (scheduleDAG->IsReachable(SU, PredSuccSU))
1377 goto outer_loop_continue;
1380 // Ok, the transformation is safe and the heuristics suggest it is
1381 // profitable. Update the graph.
1382 DEBUG(dbgs() << "Prescheduling SU # " << SU->NodeNum
1383 << " next to PredSU # " << PredSU->NodeNum
1384 << " to guide scheduling in the presence of multiple uses\n");
1385 for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
1386 SDep Edge = PredSU->Succs[i];
1387 assert(!Edge.isAssignedRegDep());
1388 SUnit *SuccSU = Edge.getSUnit();
1390 Edge.setSUnit(PredSU);
1391 scheduleDAG->RemovePred(SuccSU, Edge);
1392 scheduleDAG->AddPred(SU, Edge);
1394 scheduleDAG->AddPred(SuccSU, Edge);
1398 outer_loop_continue:;
1402 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
1403 /// it as a def&use operand. Add a pseudo control edge from it to the other
1404 /// node (if it won't create a cycle) so the two-address one will be scheduled
1405 /// first (lower in the schedule). If both nodes are two-address, favor the
1406 /// one that has a CopyToReg use (more likely to be a loop induction update).
1407 /// If both are two-address, but one is commutable while the other is not
1408 /// commutable, favor the one that's not commutable.
1410 void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
1411 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1412 SUnit *SU = &(*SUnits)[i];
1413 if (!SU->isTwoAddress)
1416 SDNode *Node = SU->getNode();
1417 if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode())
1420 unsigned Opc = Node->getMachineOpcode();
1421 const TargetInstrDesc &TID = TII->get(Opc);
1422 unsigned NumRes = TID.getNumDefs();
1423 unsigned NumOps = TID.getNumOperands() - NumRes;
1424 for (unsigned j = 0; j != NumOps; ++j) {
1425 if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
1427 SDNode *DU = SU->getNode()->getOperand(j).getNode();
1428 if (DU->getNodeId() == -1)
1430 const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
1431 if (!DUSU) continue;
1432 for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
1433 E = DUSU->Succs.end(); I != E; ++I) {
1434 if (I->isCtrl()) continue;
1435 SUnit *SuccSU = I->getSUnit();
1438 // Be conservative. Ignore if nodes aren't at roughly the same
1439 // depth and height.
1440 if (SuccSU->getHeight() < SU->getHeight() &&
1441 (SU->getHeight() - SuccSU->getHeight()) > 1)
1443 // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
1444 // constrains whatever is using the copy, instead of the copy
1445 // itself. In the case that the copy is coalesced, this
1446 // preserves the intent of the pseudo two-address heurietics.
1447 while (SuccSU->Succs.size() == 1 &&
1448 SuccSU->getNode()->isMachineOpcode() &&
1449 SuccSU->getNode()->getMachineOpcode() ==
1450 TargetOpcode::COPY_TO_REGCLASS)
1451 SuccSU = SuccSU->Succs.front().getSUnit();
1452 // Don't constrain non-instruction nodes.
1453 if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
1455 // Don't constrain nodes with physical register defs if the
1456 // predecessor can clobber them.
1457 if (SuccSU->hasPhysRegDefs && SU->hasPhysRegClobbers) {
1458 if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
1461 // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
1462 // these may be coalesced away. We want them close to their uses.
1463 unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
1464 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
1465 SuccOpc == TargetOpcode::INSERT_SUBREG ||
1466 SuccOpc == TargetOpcode::SUBREG_TO_REG)
1468 if ((!canClobber(SuccSU, DUSU) ||
1469 (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
1470 (!SU->isCommutable && SuccSU->isCommutable)) &&
1471 !scheduleDAG->IsReachable(SuccSU, SU)) {
1472 DEBUG(dbgs() << "Adding a pseudo-two-addr edge from SU # "
1473 << SU->NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
1474 scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0,
1475 /*Reg=*/0, /*isNormalMemory=*/false,
1476 /*isMustAlias=*/false,
1477 /*isArtificial=*/true));
1484 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1485 /// scheduling units.
1487 void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
1488 SethiUllmanNumbers.assign(SUnits->size(), 0);
1490 for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
1491 CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers);
1494 /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled
1495 /// predecessors of the successors of the SUnit SU. Stop when the provided
1496 /// limit is exceeded.
1497 static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU,
1500 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1502 const SUnit *SuccSU = I->getSUnit();
1503 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
1504 EE = SuccSU->Preds.end(); II != EE; ++II) {
1505 SUnit *PredSU = II->getSUnit();
1506 if (!PredSU->isScheduled)
1516 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1517 unsigned LPriority = SPQ->getNodePriority(left);
1518 unsigned RPriority = SPQ->getNodePriority(right);
1519 bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode();
1520 bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode();
1521 bool LIsFloater = LIsTarget && left->NumPreds == 0;
1522 bool RIsFloater = RIsTarget && right->NumPreds == 0;
1523 unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0;
1524 unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0;
1526 if (left->NumSuccs == 0 && right->NumSuccs != 0)
1528 else if (left->NumSuccs != 0 && right->NumSuccs == 0)
1535 if (left->NumSuccs == 1)
1537 if (right->NumSuccs == 1)
1540 if (LPriority+LBonus != RPriority+RBonus)
1541 return LPriority+LBonus < RPriority+RBonus;
1543 if (left->getDepth() != right->getDepth())
1544 return left->getDepth() < right->getDepth();
1546 if (left->NumSuccsLeft != right->NumSuccsLeft)
1547 return left->NumSuccsLeft > right->NumSuccsLeft;
1549 assert(left->NodeQueueId && right->NodeQueueId &&
1550 "NodeQueueId cannot be zero");
1551 return (left->NodeQueueId > right->NodeQueueId);
1554 //===----------------------------------------------------------------------===//
1555 // Public Constructor Functions
1556 //===----------------------------------------------------------------------===//
1558 llvm::ScheduleDAGSDNodes *
1559 llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1560 const TargetMachine &TM = IS->TM;
1561 const TargetInstrInfo *TII = TM.getInstrInfo();
1562 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1564 BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI);
1566 ScheduleDAGRRList *SD =
1567 new ScheduleDAGRRList(*IS->MF, true, PQ);
1568 PQ->setScheduleDAG(SD);
1572 llvm::ScheduleDAGSDNodes *
1573 llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1574 const TargetMachine &TM = IS->TM;
1575 const TargetInstrInfo *TII = TM.getInstrInfo();
1576 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1578 TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI);
1580 ScheduleDAGRRList *SD =
1581 new ScheduleDAGRRList(*IS->MF, false, PQ);
1582 PQ->setScheduleDAG(SD);
1586 llvm::ScheduleDAGSDNodes *
1587 llvm::createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1588 const TargetMachine &TM = IS->TM;
1589 const TargetInstrInfo *TII = TM.getInstrInfo();
1590 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1592 SrcRegReductionPriorityQueue *PQ = new SrcRegReductionPriorityQueue(TII, TRI);
1594 ScheduleDAGRRList *SD =
1595 new ScheduleDAGRRList(*IS->MF, true, PQ);
1596 PQ->setScheduleDAG(SD);