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/CodeGen/SchedulerRegistry.h"
21 #include "llvm/CodeGen/SelectionDAGISel.h"
22 #include "llvm/Target/TargetRegisterInfo.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/ErrorHandling.h"
28 #include "llvm/ADT/PriorityQueue.h"
29 #include "llvm/ADT/SmallSet.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/Support/raw_ostream.h"
36 STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
37 STATISTIC(NumUnfolds, "Number of nodes unfolded");
38 STATISTIC(NumDups, "Number of duplicated nodes");
39 STATISTIC(NumPRCopies, "Number of physical register copies");
41 static RegisterScheduler
42 burrListDAGScheduler("list-burr",
43 "Bottom-up register reduction list scheduling",
44 createBURRListDAGScheduler);
45 static RegisterScheduler
46 tdrListrDAGScheduler("list-tdrr",
47 "Top-down register reduction list scheduling",
48 createTDRRListDAGScheduler);
49 static RegisterScheduler
50 sourceListDAGScheduler("source",
51 "Similar to list-burr but schedules in source "
52 "order when possible",
53 createSourceListDAGScheduler);
56 //===----------------------------------------------------------------------===//
57 /// ScheduleDAGRRList - The actual register reduction list scheduler
58 /// implementation. This supports both top-down and bottom-up scheduling.
60 class ScheduleDAGRRList : public ScheduleDAGSDNodes {
62 /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
66 /// AvailableQueue - The priority queue to use for the available SUnits.
67 SchedulingPriorityQueue *AvailableQueue;
69 /// LiveRegDefs - A set of physical registers and their definition
70 /// that are "live". These nodes must be scheduled before any other nodes that
71 /// modifies the registers can be scheduled.
73 std::vector<SUnit*> LiveRegDefs;
74 std::vector<unsigned> LiveRegCycles;
76 /// Topo - A topological ordering for SUnits which permits fast IsReachable
77 /// and similar queries.
78 ScheduleDAGTopologicalSort Topo;
81 ScheduleDAGRRList(MachineFunction &mf,
83 SchedulingPriorityQueue *availqueue)
84 : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup),
85 AvailableQueue(availqueue), Topo(SUnits) {
88 ~ScheduleDAGRRList() {
89 delete AvailableQueue;
94 /// IsReachable - Checks if SU is reachable from TargetSU.
95 bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
96 return Topo.IsReachable(SU, TargetSU);
99 /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
101 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
102 return Topo.WillCreateCycle(SU, TargetSU);
105 /// AddPred - adds a predecessor edge to SUnit SU.
106 /// This returns true if this is a new predecessor.
107 /// Updates the topological ordering if required.
108 void AddPred(SUnit *SU, const SDep &D) {
109 Topo.AddPred(SU, D.getSUnit());
113 /// RemovePred - removes a predecessor edge from SUnit SU.
114 /// This returns true if an edge was removed.
115 /// Updates the topological ordering if required.
116 void RemovePred(SUnit *SU, const SDep &D) {
117 Topo.RemovePred(SU, D.getSUnit());
122 void ReleasePred(SUnit *SU, const SDep *PredEdge);
123 void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
124 void ReleaseSucc(SUnit *SU, const SDep *SuccEdge);
125 void ReleaseSuccessors(SUnit *SU);
126 void CapturePred(SDep *PredEdge);
127 void ScheduleNodeBottomUp(SUnit*, unsigned);
128 void ScheduleNodeTopDown(SUnit*, unsigned);
129 void UnscheduleNodeBottomUp(SUnit*);
130 void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
131 SUnit *CopyAndMoveSuccessors(SUnit*);
132 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
133 const TargetRegisterClass*,
134 const TargetRegisterClass*,
135 SmallVector<SUnit*, 2>&);
136 bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
137 void ListScheduleTopDown();
138 void ListScheduleBottomUp();
141 /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
142 /// Updates the topological ordering if required.
143 SUnit *CreateNewSUnit(SDNode *N) {
144 unsigned NumSUnits = SUnits.size();
145 SUnit *NewNode = NewSUnit(N);
146 // Update the topological ordering.
147 if (NewNode->NodeNum >= NumSUnits)
148 Topo.InitDAGTopologicalSorting();
152 /// CreateClone - Creates a new SUnit from an existing one.
153 /// Updates the topological ordering if required.
154 SUnit *CreateClone(SUnit *N) {
155 unsigned NumSUnits = SUnits.size();
156 SUnit *NewNode = Clone(N);
157 // Update the topological ordering.
158 if (NewNode->NodeNum >= NumSUnits)
159 Topo.InitDAGTopologicalSorting();
163 /// ForceUnitLatencies - Return true, since register-pressure-reducing
164 /// scheduling doesn't need actual latency information.
165 bool ForceUnitLatencies() const { return true; }
167 } // end anonymous namespace
170 /// Schedule - Schedule the DAG using list scheduling.
171 void ScheduleDAGRRList::Schedule() {
172 DEBUG(dbgs() << "********** List Scheduling **********\n");
175 LiveRegDefs.resize(TRI->getNumRegs(), NULL);
176 LiveRegCycles.resize(TRI->getNumRegs(), 0);
178 // Build the scheduling graph.
179 BuildSchedGraph(NULL);
181 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
182 SUnits[su].dumpAll(this));
183 Topo.InitDAGTopologicalSorting();
185 AvailableQueue->initNodes(SUnits);
187 // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
189 ListScheduleBottomUp();
191 ListScheduleTopDown();
193 AvailableQueue->releaseState();
196 //===----------------------------------------------------------------------===//
197 // Bottom-Up Scheduling
198 //===----------------------------------------------------------------------===//
200 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
201 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
202 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
203 SUnit *PredSU = PredEdge->getSUnit();
206 if (PredSU->NumSuccsLeft == 0) {
207 dbgs() << "*** Scheduling failed! ***\n";
209 dbgs() << " has been released too many times!\n";
213 --PredSU->NumSuccsLeft;
215 // If all the node's successors are scheduled, this node is ready
216 // to be scheduled. Ignore the special EntrySU node.
217 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
218 PredSU->isAvailable = true;
219 AvailableQueue->push(PredSU);
223 void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
224 // Bottom up: release predecessors
225 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
227 ReleasePred(SU, &*I);
228 if (I->isAssignedRegDep()) {
229 // This is a physical register dependency and it's impossible or
230 // expensive to copy the register. Make sure nothing that can
231 // clobber the register is scheduled between the predecessor and
233 if (!LiveRegDefs[I->getReg()]) {
235 LiveRegDefs[I->getReg()] = I->getSUnit();
236 LiveRegCycles[I->getReg()] = CurCycle;
242 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
243 /// count of its predecessors. If a predecessor pending count is zero, add it to
244 /// the Available queue.
245 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
246 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
247 DEBUG(SU->dump(this));
249 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
250 SU->setHeightToAtLeast(CurCycle);
251 Sequence.push_back(SU);
253 ReleasePredecessors(SU, CurCycle);
255 // Release all the implicit physical register defs that are live.
256 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
258 if (I->isAssignedRegDep()) {
259 if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) {
260 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
261 assert(LiveRegDefs[I->getReg()] == SU &&
262 "Physical register dependency violated?");
264 LiveRegDefs[I->getReg()] = NULL;
265 LiveRegCycles[I->getReg()] = 0;
270 SU->isScheduled = true;
271 AvailableQueue->ScheduledNode(SU);
274 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
275 /// unscheduled, incrcease the succ left count of its predecessors. Remove
276 /// them from AvailableQueue if necessary.
277 void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
278 SUnit *PredSU = PredEdge->getSUnit();
279 if (PredSU->isAvailable) {
280 PredSU->isAvailable = false;
281 if (!PredSU->isPending)
282 AvailableQueue->remove(PredSU);
285 assert(PredSU->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
286 ++PredSU->NumSuccsLeft;
289 /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
290 /// its predecessor states to reflect the change.
291 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
292 DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
293 DEBUG(SU->dump(this));
295 AvailableQueue->UnscheduledNode(SU);
297 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
300 if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) {
301 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
302 assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
303 "Physical register dependency violated?");
305 LiveRegDefs[I->getReg()] = NULL;
306 LiveRegCycles[I->getReg()] = 0;
310 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
312 if (I->isAssignedRegDep()) {
313 if (!LiveRegDefs[I->getReg()]) {
314 LiveRegDefs[I->getReg()] = SU;
317 if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()])
318 LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight();
322 SU->setHeightDirty();
323 SU->isScheduled = false;
324 SU->isAvailable = true;
325 AvailableQueue->push(SU);
328 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
329 /// BTCycle in order to schedule a specific node.
330 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
331 unsigned &CurCycle) {
333 while (CurCycle > BtCycle) {
334 OldSU = Sequence.back();
336 if (SU->isSucc(OldSU))
337 // Don't try to remove SU from AvailableQueue.
338 SU->isAvailable = false;
339 UnscheduleNodeBottomUp(OldSU);
343 assert(!SU->isSucc(OldSU) && "Something is wrong!");
348 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
349 /// successors to the newly created node.
350 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
351 if (SU->getNode()->getFlaggedNode())
354 SDNode *N = SU->getNode();
359 bool TryUnfold = false;
360 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
361 EVT VT = N->getValueType(i);
364 else if (VT == MVT::Other)
367 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
368 const SDValue &Op = N->getOperand(i);
369 EVT VT = Op.getNode()->getValueType(Op.getResNo());
375 SmallVector<SDNode*, 2> NewNodes;
376 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
379 DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n");
380 assert(NewNodes.size() == 2 && "Expected a load folding node!");
383 SDNode *LoadNode = NewNodes[0];
384 unsigned NumVals = N->getNumValues();
385 unsigned OldNumVals = SU->getNode()->getNumValues();
386 for (unsigned i = 0; i != NumVals; ++i)
387 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
388 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
389 SDValue(LoadNode, 1));
391 // LoadNode may already exist. This can happen when there is another
392 // load from the same location and producing the same type of value
393 // but it has different alignment or volatileness.
394 bool isNewLoad = true;
396 if (LoadNode->getNodeId() != -1) {
397 LoadSU = &SUnits[LoadNode->getNodeId()];
400 LoadSU = CreateNewSUnit(LoadNode);
401 LoadNode->setNodeId(LoadSU->NodeNum);
402 ComputeLatency(LoadSU);
405 SUnit *NewSU = CreateNewSUnit(N);
406 assert(N->getNodeId() == -1 && "Node already inserted!");
407 N->setNodeId(NewSU->NodeNum);
409 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
410 for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
411 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
412 NewSU->isTwoAddress = true;
416 if (TID.isCommutable())
417 NewSU->isCommutable = true;
418 ComputeLatency(NewSU);
420 // Record all the edges to and from the old SU, by category.
421 SmallVector<SDep, 4> ChainPreds;
422 SmallVector<SDep, 4> ChainSuccs;
423 SmallVector<SDep, 4> LoadPreds;
424 SmallVector<SDep, 4> NodePreds;
425 SmallVector<SDep, 4> NodeSuccs;
426 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
429 ChainPreds.push_back(*I);
430 else if (I->getSUnit()->getNode() &&
431 I->getSUnit()->getNode()->isOperandOf(LoadNode))
432 LoadPreds.push_back(*I);
434 NodePreds.push_back(*I);
436 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
439 ChainSuccs.push_back(*I);
441 NodeSuccs.push_back(*I);
444 // Now assign edges to the newly-created nodes.
445 for (unsigned i = 0, e = ChainPreds.size(); i != e; ++i) {
446 const SDep &Pred = ChainPreds[i];
447 RemovePred(SU, Pred);
449 AddPred(LoadSU, Pred);
451 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
452 const SDep &Pred = LoadPreds[i];
453 RemovePred(SU, Pred);
455 AddPred(LoadSU, Pred);
457 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
458 const SDep &Pred = NodePreds[i];
459 RemovePred(SU, Pred);
460 AddPred(NewSU, Pred);
462 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
463 SDep D = NodeSuccs[i];
464 SUnit *SuccDep = D.getSUnit();
466 RemovePred(SuccDep, D);
470 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
471 SDep D = ChainSuccs[i];
472 SUnit *SuccDep = D.getSUnit();
474 RemovePred(SuccDep, D);
481 // Add a data dependency to reflect that NewSU reads the value defined
483 AddPred(NewSU, SDep(LoadSU, SDep::Data, LoadSU->Latency));
486 AvailableQueue->addNode(LoadSU);
487 AvailableQueue->addNode(NewSU);
491 if (NewSU->NumSuccsLeft == 0) {
492 NewSU->isAvailable = true;
498 DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n");
499 NewSU = CreateClone(SU);
501 // New SUnit has the exact same predecessors.
502 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
504 if (!I->isArtificial())
507 // Only copy scheduled successors. Cut them from old node's successor
508 // list and move them over.
509 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
510 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
512 if (I->isArtificial())
514 SUnit *SuccSU = I->getSUnit();
515 if (SuccSU->isScheduled) {
520 DelDeps.push_back(std::make_pair(SuccSU, D));
523 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
524 RemovePred(DelDeps[i].first, DelDeps[i].second);
526 AvailableQueue->updateNode(SU);
527 AvailableQueue->addNode(NewSU);
533 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
534 /// scheduled successors of the given SUnit to the last copy.
535 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
536 const TargetRegisterClass *DestRC,
537 const TargetRegisterClass *SrcRC,
538 SmallVector<SUnit*, 2> &Copies) {
539 SUnit *CopyFromSU = CreateNewSUnit(NULL);
540 CopyFromSU->CopySrcRC = SrcRC;
541 CopyFromSU->CopyDstRC = DestRC;
543 SUnit *CopyToSU = CreateNewSUnit(NULL);
544 CopyToSU->CopySrcRC = DestRC;
545 CopyToSU->CopyDstRC = SrcRC;
547 // Only copy scheduled successors. Cut them from old node's successor
548 // list and move them over.
549 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
550 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
552 if (I->isArtificial())
554 SUnit *SuccSU = I->getSUnit();
555 if (SuccSU->isScheduled) {
557 D.setSUnit(CopyToSU);
559 DelDeps.push_back(std::make_pair(SuccSU, *I));
562 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
563 RemovePred(DelDeps[i].first, DelDeps[i].second);
565 AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
566 AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
568 AvailableQueue->updateNode(SU);
569 AvailableQueue->addNode(CopyFromSU);
570 AvailableQueue->addNode(CopyToSU);
571 Copies.push_back(CopyFromSU);
572 Copies.push_back(CopyToSU);
577 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
578 /// definition of the specified node.
579 /// FIXME: Move to SelectionDAG?
580 static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
581 const TargetInstrInfo *TII) {
582 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
583 assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
584 unsigned NumRes = TID.getNumDefs();
585 for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
590 return N->getValueType(NumRes);
593 /// CheckForLiveRegDef - Return true and update live register vector if the
594 /// specified register def of the specified SUnit clobbers any "live" registers.
595 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
596 std::vector<SUnit*> &LiveRegDefs,
597 SmallSet<unsigned, 4> &RegAdded,
598 SmallVector<unsigned, 4> &LRegs,
599 const TargetRegisterInfo *TRI) {
601 if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != SU) {
602 if (RegAdded.insert(Reg)) {
603 LRegs.push_back(Reg);
607 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias)
608 if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) {
609 if (RegAdded.insert(*Alias)) {
610 LRegs.push_back(*Alias);
617 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
618 /// scheduling of the given node to satisfy live physical register dependencies.
619 /// If the specific node is the last one that's available to schedule, do
620 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
621 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU,
622 SmallVector<unsigned, 4> &LRegs){
623 if (NumLiveRegs == 0)
626 SmallSet<unsigned, 4> RegAdded;
627 // If this node would clobber any "live" register, then it's not ready.
628 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
630 if (I->isAssignedRegDep())
631 CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs,
632 RegAdded, LRegs, TRI);
635 for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) {
636 if (Node->getOpcode() == ISD::INLINEASM) {
637 // Inline asm can clobber physical defs.
638 unsigned NumOps = Node->getNumOperands();
639 if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
640 --NumOps; // Ignore the flag operand.
642 for (unsigned i = 2; i != NumOps;) {
644 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
645 unsigned NumVals = (Flags & 0xffff) >> 3;
647 ++i; // Skip the ID value.
648 if ((Flags & 7) == 2 || (Flags & 7) == 6) {
649 // Check for def of register or earlyclobber register.
650 for (; NumVals; --NumVals, ++i) {
651 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
652 if (TargetRegisterInfo::isPhysicalRegister(Reg))
653 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
661 if (!Node->isMachineOpcode())
663 const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode());
664 if (!TID.ImplicitDefs)
666 for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg)
667 CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
669 return !LRegs.empty();
673 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
675 void ScheduleDAGRRList::ListScheduleBottomUp() {
676 unsigned CurCycle = 0;
678 // Release any predecessors of the special Exit node.
679 ReleasePredecessors(&ExitSU, CurCycle);
681 // Add root to Available queue.
682 if (!SUnits.empty()) {
683 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
684 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
685 RootSU->isAvailable = true;
686 AvailableQueue->push(RootSU);
689 // While Available queue is not empty, grab the node with the highest
690 // priority. If it is not ready put it back. Schedule the node.
691 SmallVector<SUnit*, 4> NotReady;
692 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
693 Sequence.reserve(SUnits.size());
694 while (!AvailableQueue->empty()) {
695 bool Delayed = false;
697 SUnit *CurSU = AvailableQueue->pop();
699 SmallVector<unsigned, 4> LRegs;
700 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
703 LRegsMap.insert(std::make_pair(CurSU, LRegs));
705 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
706 NotReady.push_back(CurSU);
707 CurSU = AvailableQueue->pop();
710 // All candidates are delayed due to live physical reg dependencies.
711 // Try backtracking, code duplication, or inserting cross class copies
713 if (Delayed && !CurSU) {
714 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
715 SUnit *TrySU = NotReady[i];
716 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
718 // Try unscheduling up to the point where it's safe to schedule
720 unsigned LiveCycle = CurCycle;
721 for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
722 unsigned Reg = LRegs[j];
723 unsigned LCycle = LiveRegCycles[Reg];
724 LiveCycle = std::min(LiveCycle, LCycle);
726 SUnit *OldSU = Sequence[LiveCycle];
727 if (!WillCreateCycle(TrySU, OldSU)) {
728 BacktrackBottomUp(TrySU, LiveCycle, CurCycle);
729 // Force the current node to be scheduled before the node that
730 // requires the physical reg dep.
731 if (OldSU->isAvailable) {
732 OldSU->isAvailable = false;
733 AvailableQueue->remove(OldSU);
735 AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
736 /*Reg=*/0, /*isNormalMemory=*/false,
737 /*isMustAlias=*/false, /*isArtificial=*/true));
738 // If one or more successors has been unscheduled, then the current
739 // node is no longer avaialable. Schedule a successor that's now
740 // available instead.
741 if (!TrySU->isAvailable)
742 CurSU = AvailableQueue->pop();
745 TrySU->isPending = false;
746 NotReady.erase(NotReady.begin()+i);
753 // Can't backtrack. If it's too expensive to copy the value, then try
754 // duplicate the nodes that produces these "too expensive to copy"
755 // values to break the dependency. In case even that doesn't work,
756 // insert cross class copies.
757 // If it's not too expensive, i.e. cost != -1, issue copies.
758 SUnit *TrySU = NotReady[0];
759 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
760 assert(LRegs.size() == 1 && "Can't handle this yet!");
761 unsigned Reg = LRegs[0];
762 SUnit *LRDef = LiveRegDefs[Reg];
763 EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
764 const TargetRegisterClass *RC =
765 TRI->getPhysicalRegisterRegClass(Reg, VT);
766 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
768 // If cross copy register class is null, then it must be possible copy
769 // the value directly. Do not try duplicate the def.
772 NewDef = CopyAndMoveSuccessors(LRDef);
776 // Issue copies, these can be expensive cross register class copies.
777 SmallVector<SUnit*, 2> Copies;
778 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
779 DEBUG(dbgs() << "Adding an edge from SU #" << TrySU->NodeNum
780 << " to SU #" << Copies.front()->NodeNum << "\n");
781 AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
782 /*Reg=*/0, /*isNormalMemory=*/false,
783 /*isMustAlias=*/false,
784 /*isArtificial=*/true));
785 NewDef = Copies.back();
788 DEBUG(dbgs() << "Adding an edge from SU #" << NewDef->NodeNum
789 << " to SU #" << TrySU->NodeNum << "\n");
790 LiveRegDefs[Reg] = NewDef;
791 AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
792 /*Reg=*/0, /*isNormalMemory=*/false,
793 /*isMustAlias=*/false,
794 /*isArtificial=*/true));
795 TrySU->isAvailable = false;
799 assert(CurSU && "Unable to resolve live physical register dependencies!");
802 // Add the nodes that aren't ready back onto the available list.
803 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
804 NotReady[i]->isPending = false;
805 // May no longer be available due to backtracking.
806 if (NotReady[i]->isAvailable)
807 AvailableQueue->push(NotReady[i]);
812 ScheduleNodeBottomUp(CurSU, CurCycle);
816 // Reverse the order if it is bottom up.
817 std::reverse(Sequence.begin(), Sequence.end());
820 VerifySchedule(isBottomUp);
824 //===----------------------------------------------------------------------===//
825 // Top-Down Scheduling
826 //===----------------------------------------------------------------------===//
828 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
829 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
830 void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) {
831 SUnit *SuccSU = SuccEdge->getSUnit();
834 if (SuccSU->NumPredsLeft == 0) {
835 dbgs() << "*** Scheduling failed! ***\n";
837 dbgs() << " has been released too many times!\n";
841 --SuccSU->NumPredsLeft;
843 // If all the node's predecessors are scheduled, this node is ready
844 // to be scheduled. Ignore the special ExitSU node.
845 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {
846 SuccSU->isAvailable = true;
847 AvailableQueue->push(SuccSU);
851 void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) {
852 // Top down: release successors
853 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
855 assert(!I->isAssignedRegDep() &&
856 "The list-tdrr scheduler doesn't yet support physreg dependencies!");
858 ReleaseSucc(SU, &*I);
862 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
863 /// count of its successors. If a successor pending count is zero, add it to
864 /// the Available queue.
865 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
866 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
867 DEBUG(SU->dump(this));
869 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
870 SU->setDepthToAtLeast(CurCycle);
871 Sequence.push_back(SU);
873 ReleaseSuccessors(SU);
874 SU->isScheduled = true;
875 AvailableQueue->ScheduledNode(SU);
878 /// ListScheduleTopDown - The main loop of list scheduling for top-down
880 void ScheduleDAGRRList::ListScheduleTopDown() {
881 unsigned CurCycle = 0;
883 // Release any successors of the special Entry node.
884 ReleaseSuccessors(&EntrySU);
886 // All leaves to Available queue.
887 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
888 // It is available if it has no predecessors.
889 if (SUnits[i].Preds.empty()) {
890 AvailableQueue->push(&SUnits[i]);
891 SUnits[i].isAvailable = true;
895 // While Available queue is not empty, grab the node with the highest
896 // priority. If it is not ready put it back. Schedule the node.
897 Sequence.reserve(SUnits.size());
898 while (!AvailableQueue->empty()) {
899 SUnit *CurSU = AvailableQueue->pop();
902 ScheduleNodeTopDown(CurSU, CurCycle);
907 VerifySchedule(isBottomUp);
912 //===----------------------------------------------------------------------===//
913 // RegReductionPriorityQueue Implementation
914 //===----------------------------------------------------------------------===//
916 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
917 // to reduce register pressure.
921 class RegReductionPriorityQueue;
923 /// Sorting functions for the Available queue.
924 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
925 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
926 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
927 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
929 bool operator()(const SUnit* left, const SUnit* right) const;
932 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
933 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
934 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
935 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
937 bool operator()(const SUnit* left, const SUnit* right) const;
940 struct src_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
941 RegReductionPriorityQueue<src_ls_rr_sort> *SPQ;
942 src_ls_rr_sort(RegReductionPriorityQueue<src_ls_rr_sort> *spq)
944 src_ls_rr_sort(const src_ls_rr_sort &RHS)
947 bool operator()(const SUnit* left, const SUnit* right) const;
949 } // end anonymous namespace
951 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
952 /// Smaller number is the higher priority.
954 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
955 unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
956 if (SethiUllmanNumber != 0)
957 return SethiUllmanNumber;
960 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
962 if (I->isCtrl()) continue; // ignore chain preds
963 SUnit *PredSU = I->getSUnit();
964 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
965 if (PredSethiUllman > SethiUllmanNumber) {
966 SethiUllmanNumber = PredSethiUllman;
968 } else if (PredSethiUllman == SethiUllmanNumber)
972 SethiUllmanNumber += Extra;
974 if (SethiUllmanNumber == 0)
975 SethiUllmanNumber = 1;
977 return SethiUllmanNumber;
982 class RegReductionPriorityQueue : public SchedulingPriorityQueue {
983 PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue;
984 unsigned currentQueueId;
987 // SUnits - The SUnits for the current graph.
988 std::vector<SUnit> *SUnits;
990 const TargetInstrInfo *TII;
991 const TargetRegisterInfo *TRI;
992 ScheduleDAGRRList *scheduleDAG;
994 // SethiUllmanNumbers - The SethiUllman number for each node.
995 std::vector<unsigned> SethiUllmanNumbers;
998 RegReductionPriorityQueue(const TargetInstrInfo *tii,
999 const TargetRegisterInfo *tri)
1000 : Queue(SF(this)), currentQueueId(0),
1001 TII(tii), TRI(tri), scheduleDAG(NULL) {}
1003 void initNodes(std::vector<SUnit> &sunits) {
1005 // Add pseudo dependency edges for two-address nodes.
1006 AddPseudoTwoAddrDeps();
1007 // Reroute edges to nodes with multiple uses.
1008 PrescheduleNodesWithMultipleUses();
1009 // Calculate node priorities.
1010 CalculateSethiUllmanNumbers();
1013 void addNode(const SUnit *SU) {
1014 unsigned SUSize = SethiUllmanNumbers.size();
1015 if (SUnits->size() > SUSize)
1016 SethiUllmanNumbers.resize(SUSize*2, 0);
1017 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1020 void updateNode(const SUnit *SU) {
1021 SethiUllmanNumbers[SU->NodeNum] = 0;
1022 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1025 void releaseState() {
1027 SethiUllmanNumbers.clear();
1030 unsigned getNodePriority(const SUnit *SU) const {
1031 assert(SU->NodeNum < SethiUllmanNumbers.size());
1032 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
1033 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
1034 // CopyToReg should be close to its uses to facilitate coalescing and
1037 if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
1038 Opc == TargetInstrInfo::SUBREG_TO_REG ||
1039 Opc == TargetInstrInfo::INSERT_SUBREG)
1040 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
1041 // close to their uses to facilitate coalescing.
1043 if (SU->NumSuccs == 0 && SU->NumPreds != 0)
1044 // If SU does not have a register use, i.e. it doesn't produce a value
1045 // that would be consumed (e.g. store), then it terminates a chain of
1046 // computation. Give it a large SethiUllman number so it will be
1047 // scheduled right before its predecessors that it doesn't lengthen
1048 // their live ranges.
1050 if (SU->NumPreds == 0 && SU->NumSuccs != 0)
1051 // If SU does not have a register def, schedule it close to its uses
1052 // because it does not lengthen any live ranges.
1054 return SethiUllmanNumbers[SU->NodeNum];
1057 unsigned getNodeOrdering(const SUnit *SU) const {
1058 return scheduleDAG->DAG->GetOrdering(SU->getNode());
1061 unsigned size() const { return Queue.size(); }
1063 bool empty() const { return Queue.empty(); }
1065 void push(SUnit *U) {
1066 assert(!U->NodeQueueId && "Node in the queue already");
1067 U->NodeQueueId = ++currentQueueId;
1071 void push_all(const std::vector<SUnit *> &Nodes) {
1072 for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
1077 if (empty()) return NULL;
1078 SUnit *V = Queue.top();
1084 void remove(SUnit *SU) {
1085 assert(!Queue.empty() && "Queue is empty!");
1086 assert(SU->NodeQueueId != 0 && "Not in queue!");
1087 Queue.erase_one(SU);
1088 SU->NodeQueueId = 0;
1091 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1092 scheduleDAG = scheduleDag;
1096 bool canClobber(const SUnit *SU, const SUnit *Op);
1097 void AddPseudoTwoAddrDeps();
1098 void PrescheduleNodesWithMultipleUses();
1099 void CalculateSethiUllmanNumbers();
1102 typedef RegReductionPriorityQueue<bu_ls_rr_sort>
1103 BURegReductionPriorityQueue;
1105 typedef RegReductionPriorityQueue<td_ls_rr_sort>
1106 TDRegReductionPriorityQueue;
1108 typedef RegReductionPriorityQueue<src_ls_rr_sort>
1109 SrcRegReductionPriorityQueue;
1112 /// closestSucc - Returns the scheduled cycle of the successor which is
1113 /// closest to the current cycle.
1114 static unsigned closestSucc(const SUnit *SU) {
1115 unsigned MaxHeight = 0;
1116 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1118 if (I->isCtrl()) continue; // ignore chain succs
1119 unsigned Height = I->getSUnit()->getHeight();
1120 // If there are bunch of CopyToRegs stacked up, they should be considered
1121 // to be at the same position.
1122 if (I->getSUnit()->getNode() &&
1123 I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
1124 Height = closestSucc(I->getSUnit())+1;
1125 if (Height > MaxHeight)
1131 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
1132 /// for scratch registers, i.e. number of data dependencies.
1133 static unsigned calcMaxScratches(const SUnit *SU) {
1134 unsigned Scratches = 0;
1135 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1137 if (I->isCtrl()) continue; // ignore chain preds
1143 template <typename RRSort>
1144 static bool BURRSort(const SUnit *left, const SUnit *right,
1145 const RegReductionPriorityQueue<RRSort> *SPQ) {
1146 unsigned LPriority = SPQ->getNodePriority(left);
1147 unsigned RPriority = SPQ->getNodePriority(right);
1148 if (LPriority != RPriority)
1149 return LPriority > RPriority;
1151 // Try schedule def + use closer when Sethi-Ullman numbers are the same.
1156 // and the following instructions are both ready.
1160 // Then schedule t2 = op first.
1167 // This creates more short live intervals.
1168 unsigned LDist = closestSucc(left);
1169 unsigned RDist = closestSucc(right);
1171 return LDist < RDist;
1173 // How many registers becomes live when the node is scheduled.
1174 unsigned LScratch = calcMaxScratches(left);
1175 unsigned RScratch = calcMaxScratches(right);
1176 if (LScratch != RScratch)
1177 return LScratch > RScratch;
1179 if (left->getHeight() != right->getHeight())
1180 return left->getHeight() > right->getHeight();
1182 if (left->getDepth() != right->getDepth())
1183 return left->getDepth() < right->getDepth();
1185 assert(left->NodeQueueId && right->NodeQueueId &&
1186 "NodeQueueId cannot be zero");
1187 return (left->NodeQueueId > right->NodeQueueId);
1191 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1192 return BURRSort(left, right, SPQ);
1195 // Source order, otherwise bottom up.
1196 bool src_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const{
1197 unsigned LOrder = SPQ->getNodeOrdering(left);
1198 unsigned ROrder = SPQ->getNodeOrdering(right);
1200 // Prefer an ordering where the lower the non-zero order number, the higher
1202 if ((LOrder || ROrder) && LOrder != ROrder)
1203 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
1205 return BURRSort(left, right, SPQ);
1210 RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) {
1211 if (SU->isTwoAddress) {
1212 unsigned Opc = SU->getNode()->getMachineOpcode();
1213 const TargetInstrDesc &TID = TII->get(Opc);
1214 unsigned NumRes = TID.getNumDefs();
1215 unsigned NumOps = TID.getNumOperands() - NumRes;
1216 for (unsigned i = 0; i != NumOps; ++i) {
1217 if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
1218 SDNode *DU = SU->getNode()->getOperand(i).getNode();
1219 if (DU->getNodeId() != -1 &&
1220 Op->OrigNode == &(*SUnits)[DU->getNodeId()])
1228 /// hasCopyToRegUse - Return true if SU has a value successor that is a
1230 static bool hasCopyToRegUse(const SUnit *SU) {
1231 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1233 if (I->isCtrl()) continue;
1234 const SUnit *SuccSU = I->getSUnit();
1235 if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
1241 /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
1242 /// physical register defs.
1243 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
1244 const TargetInstrInfo *TII,
1245 const TargetRegisterInfo *TRI) {
1246 SDNode *N = SuccSU->getNode();
1247 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1248 const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
1249 assert(ImpDefs && "Caller should check hasPhysRegDefs");
1250 for (const SDNode *SUNode = SU->getNode(); SUNode;
1251 SUNode = SUNode->getFlaggedNode()) {
1252 if (!SUNode->isMachineOpcode())
1254 const unsigned *SUImpDefs =
1255 TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
1258 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
1259 EVT VT = N->getValueType(i);
1260 if (VT == MVT::Flag || VT == MVT::Other)
1262 if (!N->hasAnyUseOfValue(i))
1264 unsigned Reg = ImpDefs[i - NumDefs];
1265 for (;*SUImpDefs; ++SUImpDefs) {
1266 unsigned SUReg = *SUImpDefs;
1267 if (TRI->regsOverlap(Reg, SUReg))
1275 /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
1276 /// are not handled well by the general register pressure reduction
1277 /// heuristics. When presented with code like this:
1286 /// the heuristics tend to push the store up, but since the
1287 /// operand of the store has another use (U), this would increase
1288 /// the length of that other use (the U->N edge).
1290 /// This function transforms code like the above to route U's
1291 /// dependence through the store when possible, like this:
1302 /// This results in the store being scheduled immediately
1303 /// after N, which shortens the U->N live range, reducing
1304 /// register pressure.
1307 void RegReductionPriorityQueue<SF>::PrescheduleNodesWithMultipleUses() {
1308 // Visit all the nodes in topological order, working top-down.
1309 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1310 SUnit *SU = &(*SUnits)[i];
1311 // For now, only look at nodes with no data successors, such as stores.
1312 // These are especially important, due to the heuristics in
1313 // getNodePriority for nodes with no data successors.
1314 if (SU->NumSuccs != 0)
1316 // For now, only look at nodes with exactly one data predecessor.
1317 if (SU->NumPreds != 1)
1319 // Avoid prescheduling copies to virtual registers, which don't behave
1320 // like other nodes from the perspective of scheduling heuristics.
1321 if (SDNode *N = SU->getNode())
1322 if (N->getOpcode() == ISD::CopyToReg &&
1323 TargetRegisterInfo::isVirtualRegister
1324 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1327 // Locate the single data predecessor.
1329 for (SUnit::const_pred_iterator II = SU->Preds.begin(),
1330 EE = SU->Preds.end(); II != EE; ++II)
1331 if (!II->isCtrl()) {
1332 PredSU = II->getSUnit();
1337 // Don't rewrite edges that carry physregs, because that requires additional
1338 // support infrastructure.
1339 if (PredSU->hasPhysRegDefs)
1341 // Short-circuit the case where SU is PredSU's only data successor.
1342 if (PredSU->NumSuccs == 1)
1344 // Avoid prescheduling to copies from virtual registers, which don't behave
1345 // like other nodes from the perspective of scheduling // heuristics.
1346 if (SDNode *N = SU->getNode())
1347 if (N->getOpcode() == ISD::CopyFromReg &&
1348 TargetRegisterInfo::isVirtualRegister
1349 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
1352 // Perform checks on the successors of PredSU.
1353 for (SUnit::const_succ_iterator II = PredSU->Succs.begin(),
1354 EE = PredSU->Succs.end(); II != EE; ++II) {
1355 SUnit *PredSuccSU = II->getSUnit();
1356 if (PredSuccSU == SU) continue;
1357 // If PredSU has another successor with no data successors, for
1358 // now don't attempt to choose either over the other.
1359 if (PredSuccSU->NumSuccs == 0)
1360 goto outer_loop_continue;
1361 // Don't break physical register dependencies.
1362 if (SU->hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
1363 if (canClobberPhysRegDefs(PredSuccSU, SU, TII, TRI))
1364 goto outer_loop_continue;
1365 // Don't introduce graph cycles.
1366 if (scheduleDAG->IsReachable(SU, PredSuccSU))
1367 goto outer_loop_continue;
1370 // Ok, the transformation is safe and the heuristics suggest it is
1371 // profitable. Update the graph.
1372 DEBUG(dbgs() << "Prescheduling SU # " << SU->NodeNum
1373 << " next to PredSU # " << PredSU->NodeNum
1374 << " to guide scheduling in the presence of multiple uses\n");
1375 for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
1376 SDep Edge = PredSU->Succs[i];
1377 assert(!Edge.isAssignedRegDep());
1378 SUnit *SuccSU = Edge.getSUnit();
1380 Edge.setSUnit(PredSU);
1381 scheduleDAG->RemovePred(SuccSU, Edge);
1382 scheduleDAG->AddPred(SU, Edge);
1384 scheduleDAG->AddPred(SuccSU, Edge);
1388 outer_loop_continue:;
1392 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
1393 /// it as a def&use operand. Add a pseudo control edge from it to the other
1394 /// node (if it won't create a cycle) so the two-address one will be scheduled
1395 /// first (lower in the schedule). If both nodes are two-address, favor the
1396 /// one that has a CopyToReg use (more likely to be a loop induction update).
1397 /// If both are two-address, but one is commutable while the other is not
1398 /// commutable, favor the one that's not commutable.
1400 void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
1401 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
1402 SUnit *SU = &(*SUnits)[i];
1403 if (!SU->isTwoAddress)
1406 SDNode *Node = SU->getNode();
1407 if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode())
1410 unsigned Opc = Node->getMachineOpcode();
1411 const TargetInstrDesc &TID = TII->get(Opc);
1412 unsigned NumRes = TID.getNumDefs();
1413 unsigned NumOps = TID.getNumOperands() - NumRes;
1414 for (unsigned j = 0; j != NumOps; ++j) {
1415 if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
1417 SDNode *DU = SU->getNode()->getOperand(j).getNode();
1418 if (DU->getNodeId() == -1)
1420 const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
1421 if (!DUSU) continue;
1422 for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
1423 E = DUSU->Succs.end(); I != E; ++I) {
1424 if (I->isCtrl()) continue;
1425 SUnit *SuccSU = I->getSUnit();
1428 // Be conservative. Ignore if nodes aren't at roughly the same
1429 // depth and height.
1430 if (SuccSU->getHeight() < SU->getHeight() &&
1431 (SU->getHeight() - SuccSU->getHeight()) > 1)
1433 // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
1434 // constrains whatever is using the copy, instead of the copy
1435 // itself. In the case that the copy is coalesced, this
1436 // preserves the intent of the pseudo two-address heurietics.
1437 while (SuccSU->Succs.size() == 1 &&
1438 SuccSU->getNode()->isMachineOpcode() &&
1439 SuccSU->getNode()->getMachineOpcode() ==
1440 TargetInstrInfo::COPY_TO_REGCLASS)
1441 SuccSU = SuccSU->Succs.front().getSUnit();
1442 // Don't constrain non-instruction nodes.
1443 if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
1445 // Don't constrain nodes with physical register defs if the
1446 // predecessor can clobber them.
1447 if (SuccSU->hasPhysRegDefs && SU->hasPhysRegClobbers) {
1448 if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
1451 // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
1452 // these may be coalesced away. We want them close to their uses.
1453 unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
1454 if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG ||
1455 SuccOpc == TargetInstrInfo::INSERT_SUBREG ||
1456 SuccOpc == TargetInstrInfo::SUBREG_TO_REG)
1458 if ((!canClobber(SuccSU, DUSU) ||
1459 (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
1460 (!SU->isCommutable && SuccSU->isCommutable)) &&
1461 !scheduleDAG->IsReachable(SuccSU, SU)) {
1462 DEBUG(dbgs() << "Adding a pseudo-two-addr edge from SU # "
1463 << SU->NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
1464 scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0,
1465 /*Reg=*/0, /*isNormalMemory=*/false,
1466 /*isMustAlias=*/false,
1467 /*isArtificial=*/true));
1474 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1475 /// scheduling units.
1477 void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
1478 SethiUllmanNumbers.assign(SUnits->size(), 0);
1480 for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
1481 CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers);
1484 /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled
1485 /// predecessors of the successors of the SUnit SU. Stop when the provided
1486 /// limit is exceeded.
1487 static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU,
1490 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1492 const SUnit *SuccSU = I->getSUnit();
1493 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
1494 EE = SuccSU->Preds.end(); II != EE; ++II) {
1495 SUnit *PredSU = II->getSUnit();
1496 if (!PredSU->isScheduled)
1506 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
1507 unsigned LPriority = SPQ->getNodePriority(left);
1508 unsigned RPriority = SPQ->getNodePriority(right);
1509 bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode();
1510 bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode();
1511 bool LIsFloater = LIsTarget && left->NumPreds == 0;
1512 bool RIsFloater = RIsTarget && right->NumPreds == 0;
1513 unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0;
1514 unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0;
1516 if (left->NumSuccs == 0 && right->NumSuccs != 0)
1518 else if (left->NumSuccs != 0 && right->NumSuccs == 0)
1525 if (left->NumSuccs == 1)
1527 if (right->NumSuccs == 1)
1530 if (LPriority+LBonus != RPriority+RBonus)
1531 return LPriority+LBonus < RPriority+RBonus;
1533 if (left->getDepth() != right->getDepth())
1534 return left->getDepth() < right->getDepth();
1536 if (left->NumSuccsLeft != right->NumSuccsLeft)
1537 return left->NumSuccsLeft > right->NumSuccsLeft;
1539 assert(left->NodeQueueId && right->NodeQueueId &&
1540 "NodeQueueId cannot be zero");
1541 return (left->NodeQueueId > right->NodeQueueId);
1544 //===----------------------------------------------------------------------===//
1545 // Public Constructor Functions
1546 //===----------------------------------------------------------------------===//
1548 llvm::ScheduleDAGSDNodes *
1549 llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1550 const TargetMachine &TM = IS->TM;
1551 const TargetInstrInfo *TII = TM.getInstrInfo();
1552 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1554 BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI);
1556 ScheduleDAGRRList *SD =
1557 new ScheduleDAGRRList(*IS->MF, true, PQ);
1558 PQ->setScheduleDAG(SD);
1562 llvm::ScheduleDAGSDNodes *
1563 llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1564 const TargetMachine &TM = IS->TM;
1565 const TargetInstrInfo *TII = TM.getInstrInfo();
1566 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1568 TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI);
1570 ScheduleDAGRRList *SD =
1571 new ScheduleDAGRRList(*IS->MF, false, PQ);
1572 PQ->setScheduleDAG(SD);
1576 llvm::ScheduleDAGSDNodes *
1577 llvm::createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
1578 const TargetMachine &TM = IS->TM;
1579 const TargetInstrInfo *TII = TM.getInstrInfo();
1580 const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1582 SrcRegReductionPriorityQueue *PQ = new SrcRegReductionPriorityQueue(TII, TRI);
1584 ScheduleDAGRRList *SD =
1585 new ScheduleDAGRRList(*IS->MF, true, PQ);
1586 PQ->setScheduleDAG(SD);