1 //===----- ScheduleDAGFast.cpp - Fast poor 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 a fast scheduler.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SchedulerRegistry.h"
15 #include "InstrEmitter.h"
16 #include "ScheduleDAGSDNodes.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/CodeGen/SelectionDAGISel.h"
21 #include "llvm/IR/DataLayout.h"
22 #include "llvm/IR/InlineAsm.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetRegisterInfo.h"
30 #define DEBUG_TYPE "pre-RA-sched"
32 STATISTIC(NumUnfolds
, "Number of nodes unfolded");
33 STATISTIC(NumDups
, "Number of duplicated nodes");
34 STATISTIC(NumPRCopies
, "Number of physical copies");
36 static RegisterScheduler
37 fastDAGScheduler("fast", "Fast suboptimal list scheduling",
38 createFastDAGScheduler
);
39 static RegisterScheduler
40 linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling",
45 /// FastPriorityQueue - A degenerate priority queue that considers
46 /// all nodes to have the same priority.
48 struct FastPriorityQueue
{
49 SmallVector
<SUnit
*, 16> Queue
;
51 bool empty() const { return Queue
.empty(); }
58 if (empty()) return nullptr;
59 SUnit
*V
= Queue
.back();
65 //===----------------------------------------------------------------------===//
66 /// ScheduleDAGFast - The actual "fast" list scheduler implementation.
68 class ScheduleDAGFast
: public ScheduleDAGSDNodes
{
70 /// AvailableQueue - The priority queue to use for the available SUnits.
71 FastPriorityQueue AvailableQueue
;
73 /// LiveRegDefs - A set of physical registers and their definition
74 /// that are "live". These nodes must be scheduled before any other nodes that
75 /// modifies the registers can be scheduled.
77 std::vector
<SUnit
*> LiveRegDefs
;
78 std::vector
<unsigned> LiveRegCycles
;
81 ScheduleDAGFast(MachineFunction
&mf
)
82 : ScheduleDAGSDNodes(mf
) {}
84 void Schedule() override
;
86 /// AddPred - adds a predecessor edge to SUnit SU.
87 /// This returns true if this is a new predecessor.
88 void AddPred(SUnit
*SU
, const SDep
&D
) {
92 /// RemovePred - removes a predecessor edge from SUnit SU.
93 /// This returns true if an edge was removed.
94 void RemovePred(SUnit
*SU
, const SDep
&D
) {
99 void ReleasePred(SUnit
*SU
, SDep
*PredEdge
);
100 void ReleasePredecessors(SUnit
*SU
, unsigned CurCycle
);
101 void ScheduleNodeBottomUp(SUnit
*, unsigned);
102 SUnit
*CopyAndMoveSuccessors(SUnit
*);
103 void InsertCopiesAndMoveSuccs(SUnit
*, unsigned,
104 const TargetRegisterClass
*,
105 const TargetRegisterClass
*,
106 SmallVectorImpl
<SUnit
*>&);
107 bool DelayForLiveRegsBottomUp(SUnit
*, SmallVectorImpl
<unsigned>&);
108 void ListScheduleBottomUp();
110 /// forceUnitLatencies - The fast scheduler doesn't care about real latencies.
111 bool forceUnitLatencies() const override
{ return true; }
113 } // end anonymous namespace
116 /// Schedule - Schedule the DAG using list scheduling.
117 void ScheduleDAGFast::Schedule() {
118 DEBUG(dbgs() << "********** List Scheduling **********\n");
121 LiveRegDefs
.resize(TRI
->getNumRegs(), nullptr);
122 LiveRegCycles
.resize(TRI
->getNumRegs(), 0);
124 // Build the scheduling graph.
125 BuildSchedGraph(nullptr);
127 DEBUG(for (unsigned su
= 0, e
= SUnits
.size(); su
!= e
; ++su
)
128 SUnits
[su
].dumpAll(this));
130 // Execute the actual scheduling loop.
131 ListScheduleBottomUp();
134 //===----------------------------------------------------------------------===//
135 // Bottom-Up Scheduling
136 //===----------------------------------------------------------------------===//
138 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
139 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
140 void ScheduleDAGFast::ReleasePred(SUnit
*SU
, SDep
*PredEdge
) {
141 SUnit
*PredSU
= PredEdge
->getSUnit();
144 if (PredSU
->NumSuccsLeft
== 0) {
145 dbgs() << "*** Scheduling failed! ***\n";
147 dbgs() << " has been released too many times!\n";
148 llvm_unreachable(nullptr);
151 --PredSU
->NumSuccsLeft
;
153 // If all the node's successors are scheduled, this node is ready
154 // to be scheduled. Ignore the special EntrySU node.
155 if (PredSU
->NumSuccsLeft
== 0 && PredSU
!= &EntrySU
) {
156 PredSU
->isAvailable
= true;
157 AvailableQueue
.push(PredSU
);
161 void ScheduleDAGFast::ReleasePredecessors(SUnit
*SU
, unsigned CurCycle
) {
162 // Bottom up: release predecessors
163 for (SUnit::pred_iterator I
= SU
->Preds
.begin(), E
= SU
->Preds
.end();
165 ReleasePred(SU
, &*I
);
166 if (I
->isAssignedRegDep()) {
167 // This is a physical register dependency and it's impossible or
168 // expensive to copy the register. Make sure nothing that can
169 // clobber the register is scheduled between the predecessor and
171 if (!LiveRegDefs
[I
->getReg()]) {
173 LiveRegDefs
[I
->getReg()] = I
->getSUnit();
174 LiveRegCycles
[I
->getReg()] = CurCycle
;
180 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
181 /// count of its predecessors. If a predecessor pending count is zero, add it to
182 /// the Available queue.
183 void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit
*SU
, unsigned CurCycle
) {
184 DEBUG(dbgs() << "*** Scheduling [" << CurCycle
<< "]: ");
185 DEBUG(SU
->dump(this));
187 assert(CurCycle
>= SU
->getHeight() && "Node scheduled below its height!");
188 SU
->setHeightToAtLeast(CurCycle
);
189 Sequence
.push_back(SU
);
191 ReleasePredecessors(SU
, CurCycle
);
193 // Release all the implicit physical register defs that are live.
194 for (SUnit::succ_iterator I
= SU
->Succs
.begin(), E
= SU
->Succs
.end();
196 if (I
->isAssignedRegDep()) {
197 if (LiveRegCycles
[I
->getReg()] == I
->getSUnit()->getHeight()) {
198 assert(NumLiveRegs
> 0 && "NumLiveRegs is already zero!");
199 assert(LiveRegDefs
[I
->getReg()] == SU
&&
200 "Physical register dependency violated?");
202 LiveRegDefs
[I
->getReg()] = nullptr;
203 LiveRegCycles
[I
->getReg()] = 0;
208 SU
->isScheduled
= true;
211 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
212 /// successors to the newly created node.
213 SUnit
*ScheduleDAGFast::CopyAndMoveSuccessors(SUnit
*SU
) {
214 if (SU
->getNode()->getGluedNode())
217 SDNode
*N
= SU
->getNode();
222 bool TryUnfold
= false;
223 for (unsigned i
= 0, e
= N
->getNumValues(); i
!= e
; ++i
) {
224 MVT VT
= N
->getSimpleValueType(i
);
227 else if (VT
== MVT::Other
)
230 for (unsigned i
= 0, e
= N
->getNumOperands(); i
!= e
; ++i
) {
231 const SDValue
&Op
= N
->getOperand(i
);
232 MVT VT
= Op
.getNode()->getSimpleValueType(Op
.getResNo());
238 SmallVector
<SDNode
*, 2> NewNodes
;
239 if (!TII
->unfoldMemoryOperand(*DAG
, N
, NewNodes
))
242 DEBUG(dbgs() << "Unfolding SU # " << SU
->NodeNum
<< "\n");
243 assert(NewNodes
.size() == 2 && "Expected a load folding node!");
246 SDNode
*LoadNode
= NewNodes
[0];
247 unsigned NumVals
= N
->getNumValues();
248 unsigned OldNumVals
= SU
->getNode()->getNumValues();
249 for (unsigned i
= 0; i
!= NumVals
; ++i
)
250 DAG
->ReplaceAllUsesOfValueWith(SDValue(SU
->getNode(), i
), SDValue(N
, i
));
251 DAG
->ReplaceAllUsesOfValueWith(SDValue(SU
->getNode(), OldNumVals
-1),
252 SDValue(LoadNode
, 1));
254 SUnit
*NewSU
= newSUnit(N
);
255 assert(N
->getNodeId() == -1 && "Node already inserted!");
256 N
->setNodeId(NewSU
->NodeNum
);
258 const MCInstrDesc
&MCID
= TII
->get(N
->getMachineOpcode());
259 for (unsigned i
= 0; i
!= MCID
.getNumOperands(); ++i
) {
260 if (MCID
.getOperandConstraint(i
, MCOI::TIED_TO
) != -1) {
261 NewSU
->isTwoAddress
= true;
265 if (MCID
.isCommutable())
266 NewSU
->isCommutable
= true;
268 // LoadNode may already exist. This can happen when there is another
269 // load from the same location and producing the same type of value
270 // but it has different alignment or volatileness.
271 bool isNewLoad
= true;
273 if (LoadNode
->getNodeId() != -1) {
274 LoadSU
= &SUnits
[LoadNode
->getNodeId()];
277 LoadSU
= newSUnit(LoadNode
);
278 LoadNode
->setNodeId(LoadSU
->NodeNum
);
282 SmallVector
<SDep
, 4> ChainSuccs
;
283 SmallVector
<SDep
, 4> LoadPreds
;
284 SmallVector
<SDep
, 4> NodePreds
;
285 SmallVector
<SDep
, 4> NodeSuccs
;
286 for (SUnit::pred_iterator I
= SU
->Preds
.begin(), E
= SU
->Preds
.end();
290 else if (I
->getSUnit()->getNode() &&
291 I
->getSUnit()->getNode()->isOperandOf(LoadNode
))
292 LoadPreds
.push_back(*I
);
294 NodePreds
.push_back(*I
);
296 for (SUnit::succ_iterator I
= SU
->Succs
.begin(), E
= SU
->Succs
.end();
299 ChainSuccs
.push_back(*I
);
301 NodeSuccs
.push_back(*I
);
304 if (ChainPred
.getSUnit()) {
305 RemovePred(SU
, ChainPred
);
307 AddPred(LoadSU
, ChainPred
);
309 for (unsigned i
= 0, e
= LoadPreds
.size(); i
!= e
; ++i
) {
310 const SDep
&Pred
= LoadPreds
[i
];
311 RemovePred(SU
, Pred
);
313 AddPred(LoadSU
, Pred
);
316 for (unsigned i
= 0, e
= NodePreds
.size(); i
!= e
; ++i
) {
317 const SDep
&Pred
= NodePreds
[i
];
318 RemovePred(SU
, Pred
);
319 AddPred(NewSU
, Pred
);
321 for (unsigned i
= 0, e
= NodeSuccs
.size(); i
!= e
; ++i
) {
322 SDep D
= NodeSuccs
[i
];
323 SUnit
*SuccDep
= D
.getSUnit();
325 RemovePred(SuccDep
, D
);
329 for (unsigned i
= 0, e
= ChainSuccs
.size(); i
!= e
; ++i
) {
330 SDep D
= ChainSuccs
[i
];
331 SUnit
*SuccDep
= D
.getSUnit();
333 RemovePred(SuccDep
, D
);
340 SDep
D(LoadSU
, SDep::Barrier
);
341 D
.setLatency(LoadSU
->Latency
);
347 if (NewSU
->NumSuccsLeft
== 0) {
348 NewSU
->isAvailable
= true;
354 DEBUG(dbgs() << "Duplicating SU # " << SU
->NodeNum
<< "\n");
357 // New SUnit has the exact same predecessors.
358 for (SUnit::pred_iterator I
= SU
->Preds
.begin(), E
= SU
->Preds
.end();
360 if (!I
->isArtificial())
363 // Only copy scheduled successors. Cut them from old node's successor
364 // list and move them over.
365 SmallVector
<std::pair
<SUnit
*, SDep
>, 4> DelDeps
;
366 for (SUnit::succ_iterator I
= SU
->Succs
.begin(), E
= SU
->Succs
.end();
368 if (I
->isArtificial())
370 SUnit
*SuccSU
= I
->getSUnit();
371 if (SuccSU
->isScheduled
) {
376 DelDeps
.push_back(std::make_pair(SuccSU
, D
));
379 for (unsigned i
= 0, e
= DelDeps
.size(); i
!= e
; ++i
)
380 RemovePred(DelDeps
[i
].first
, DelDeps
[i
].second
);
386 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
387 /// scheduled successors of the given SUnit to the last copy.
388 void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit
*SU
, unsigned Reg
,
389 const TargetRegisterClass
*DestRC
,
390 const TargetRegisterClass
*SrcRC
,
391 SmallVectorImpl
<SUnit
*> &Copies
) {
392 SUnit
*CopyFromSU
= newSUnit(static_cast<SDNode
*>(nullptr));
393 CopyFromSU
->CopySrcRC
= SrcRC
;
394 CopyFromSU
->CopyDstRC
= DestRC
;
396 SUnit
*CopyToSU
= newSUnit(static_cast<SDNode
*>(nullptr));
397 CopyToSU
->CopySrcRC
= DestRC
;
398 CopyToSU
->CopyDstRC
= SrcRC
;
400 // Only copy scheduled successors. Cut them from old node's successor
401 // list and move them over.
402 SmallVector
<std::pair
<SUnit
*, SDep
>, 4> DelDeps
;
403 for (SUnit::succ_iterator I
= SU
->Succs
.begin(), E
= SU
->Succs
.end();
405 if (I
->isArtificial())
407 SUnit
*SuccSU
= I
->getSUnit();
408 if (SuccSU
->isScheduled
) {
410 D
.setSUnit(CopyToSU
);
412 DelDeps
.push_back(std::make_pair(SuccSU
, *I
));
415 for (unsigned i
= 0, e
= DelDeps
.size(); i
!= e
; ++i
) {
416 RemovePred(DelDeps
[i
].first
, DelDeps
[i
].second
);
418 SDep
FromDep(SU
, SDep::Data
, Reg
);
419 FromDep
.setLatency(SU
->Latency
);
420 AddPred(CopyFromSU
, FromDep
);
421 SDep
ToDep(CopyFromSU
, SDep::Data
, 0);
422 ToDep
.setLatency(CopyFromSU
->Latency
);
423 AddPred(CopyToSU
, ToDep
);
425 Copies
.push_back(CopyFromSU
);
426 Copies
.push_back(CopyToSU
);
431 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
432 /// definition of the specified node.
433 /// FIXME: Move to SelectionDAG?
434 static MVT
getPhysicalRegisterVT(SDNode
*N
, unsigned Reg
,
435 const TargetInstrInfo
*TII
) {
437 if (N
->getOpcode() == ISD::CopyFromReg
) {
438 // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
441 const MCInstrDesc
&MCID
= TII
->get(N
->getMachineOpcode());
442 assert(MCID
.ImplicitDefs
&& "Physical reg def must be in implicit def list!");
443 NumRes
= MCID
.getNumDefs();
444 for (const uint16_t *ImpDef
= MCID
.getImplicitDefs(); *ImpDef
; ++ImpDef
) {
450 return N
->getSimpleValueType(NumRes
);
453 /// CheckForLiveRegDef - Return true and update live register vector if the
454 /// specified register def of the specified SUnit clobbers any "live" registers.
455 static bool CheckForLiveRegDef(SUnit
*SU
, unsigned Reg
,
456 std::vector
<SUnit
*> &LiveRegDefs
,
457 SmallSet
<unsigned, 4> &RegAdded
,
458 SmallVectorImpl
<unsigned> &LRegs
,
459 const TargetRegisterInfo
*TRI
) {
461 for (MCRegAliasIterator
AI(Reg
, TRI
, true); AI
.isValid(); ++AI
) {
462 if (LiveRegDefs
[*AI
] && LiveRegDefs
[*AI
] != SU
) {
463 if (RegAdded
.insert(*AI
).second
) {
464 LRegs
.push_back(*AI
);
472 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
473 /// scheduling of the given node to satisfy live physical register dependencies.
474 /// If the specific node is the last one that's available to schedule, do
475 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
476 bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit
*SU
,
477 SmallVectorImpl
<unsigned> &LRegs
){
478 if (NumLiveRegs
== 0)
481 SmallSet
<unsigned, 4> RegAdded
;
482 // If this node would clobber any "live" register, then it's not ready.
483 for (SUnit::pred_iterator I
= SU
->Preds
.begin(), E
= SU
->Preds
.end();
485 if (I
->isAssignedRegDep()) {
486 CheckForLiveRegDef(I
->getSUnit(), I
->getReg(), LiveRegDefs
,
487 RegAdded
, LRegs
, TRI
);
491 for (SDNode
*Node
= SU
->getNode(); Node
; Node
= Node
->getGluedNode()) {
492 if (Node
->getOpcode() == ISD::INLINEASM
) {
493 // Inline asm can clobber physical defs.
494 unsigned NumOps
= Node
->getNumOperands();
495 if (Node
->getOperand(NumOps
-1).getValueType() == MVT::Glue
)
496 --NumOps
; // Ignore the glue operand.
498 for (unsigned i
= InlineAsm::Op_FirstOperand
; i
!= NumOps
;) {
500 cast
<ConstantSDNode
>(Node
->getOperand(i
))->getZExtValue();
501 unsigned NumVals
= InlineAsm::getNumOperandRegisters(Flags
);
503 ++i
; // Skip the ID value.
504 if (InlineAsm::isRegDefKind(Flags
) ||
505 InlineAsm::isRegDefEarlyClobberKind(Flags
) ||
506 InlineAsm::isClobberKind(Flags
)) {
507 // Check for def of register or earlyclobber register.
508 for (; NumVals
; --NumVals
, ++i
) {
509 unsigned Reg
= cast
<RegisterSDNode
>(Node
->getOperand(i
))->getReg();
510 if (TargetRegisterInfo::isPhysicalRegister(Reg
))
511 CheckForLiveRegDef(SU
, Reg
, LiveRegDefs
, RegAdded
, LRegs
, TRI
);
518 if (!Node
->isMachineOpcode())
520 const MCInstrDesc
&MCID
= TII
->get(Node
->getMachineOpcode());
521 if (!MCID
.ImplicitDefs
)
523 for (const uint16_t *Reg
= MCID
.getImplicitDefs(); *Reg
; ++Reg
) {
524 CheckForLiveRegDef(SU
, *Reg
, LiveRegDefs
, RegAdded
, LRegs
, TRI
);
527 return !LRegs
.empty();
531 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
533 void ScheduleDAGFast::ListScheduleBottomUp() {
534 unsigned CurCycle
= 0;
536 // Release any predecessors of the special Exit node.
537 ReleasePredecessors(&ExitSU
, CurCycle
);
539 // Add root to Available queue.
540 if (!SUnits
.empty()) {
541 SUnit
*RootSU
= &SUnits
[DAG
->getRoot().getNode()->getNodeId()];
542 assert(RootSU
->Succs
.empty() && "Graph root shouldn't have successors!");
543 RootSU
->isAvailable
= true;
544 AvailableQueue
.push(RootSU
);
547 // While Available queue is not empty, grab the node with the highest
548 // priority. If it is not ready put it back. Schedule the node.
549 SmallVector
<SUnit
*, 4> NotReady
;
550 DenseMap
<SUnit
*, SmallVector
<unsigned, 4> > LRegsMap
;
551 Sequence
.reserve(SUnits
.size());
552 while (!AvailableQueue
.empty()) {
553 bool Delayed
= false;
555 SUnit
*CurSU
= AvailableQueue
.pop();
557 SmallVector
<unsigned, 4> LRegs
;
558 if (!DelayForLiveRegsBottomUp(CurSU
, LRegs
))
561 LRegsMap
.insert(std::make_pair(CurSU
, LRegs
));
563 CurSU
->isPending
= true; // This SU is not in AvailableQueue right now.
564 NotReady
.push_back(CurSU
);
565 CurSU
= AvailableQueue
.pop();
568 // All candidates are delayed due to live physical reg dependencies.
569 // Try code duplication or inserting cross class copies
571 if (Delayed
&& !CurSU
) {
573 // Try duplicating the nodes that produces these
574 // "expensive to copy" values to break the dependency. In case even
575 // that doesn't work, insert cross class copies.
576 SUnit
*TrySU
= NotReady
[0];
577 SmallVectorImpl
<unsigned> &LRegs
= LRegsMap
[TrySU
];
578 assert(LRegs
.size() == 1 && "Can't handle this yet!");
579 unsigned Reg
= LRegs
[0];
580 SUnit
*LRDef
= LiveRegDefs
[Reg
];
581 MVT VT
= getPhysicalRegisterVT(LRDef
->getNode(), Reg
, TII
);
582 const TargetRegisterClass
*RC
=
583 TRI
->getMinimalPhysRegClass(Reg
, VT
);
584 const TargetRegisterClass
*DestRC
= TRI
->getCrossCopyRegClass(RC
);
586 // If cross copy register class is the same as RC, then it must be
587 // possible copy the value directly. Do not try duplicate the def.
588 // If cross copy register class is not the same as RC, then it's
589 // possible to copy the value but it require cross register class copies
590 // and it is expensive.
591 // If cross copy register class is null, then it's not possible to copy
593 SUnit
*NewDef
= nullptr;
595 NewDef
= CopyAndMoveSuccessors(LRDef
);
596 if (!DestRC
&& !NewDef
)
597 report_fatal_error("Can't handle live physical "
598 "register dependency!");
601 // Issue copies, these can be expensive cross register class copies.
602 SmallVector
<SUnit
*, 2> Copies
;
603 InsertCopiesAndMoveSuccs(LRDef
, Reg
, DestRC
, RC
, Copies
);
604 DEBUG(dbgs() << "Adding an edge from SU # " << TrySU
->NodeNum
605 << " to SU #" << Copies
.front()->NodeNum
<< "\n");
606 AddPred(TrySU
, SDep(Copies
.front(), SDep::Artificial
));
607 NewDef
= Copies
.back();
610 DEBUG(dbgs() << "Adding an edge from SU # " << NewDef
->NodeNum
611 << " to SU #" << TrySU
->NodeNum
<< "\n");
612 LiveRegDefs
[Reg
] = NewDef
;
613 AddPred(NewDef
, SDep(TrySU
, SDep::Artificial
));
614 TrySU
->isAvailable
= false;
619 llvm_unreachable("Unable to resolve live physical register dependencies!");
623 // Add the nodes that aren't ready back onto the available list.
624 for (unsigned i
= 0, e
= NotReady
.size(); i
!= e
; ++i
) {
625 NotReady
[i
]->isPending
= false;
626 // May no longer be available due to backtracking.
627 if (NotReady
[i
]->isAvailable
)
628 AvailableQueue
.push(NotReady
[i
]);
633 ScheduleNodeBottomUp(CurSU
, CurCycle
);
637 // Reverse the order since it is bottom up.
638 std::reverse(Sequence
.begin(), Sequence
.end());
641 VerifyScheduledSequence(/*isBottomUp=*/true);
647 //===----------------------------------------------------------------------===//
648 // ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the
649 // DAG in topological order.
650 // IMPORTANT: this may not work for targets with phyreg dependency.
652 class ScheduleDAGLinearize
: public ScheduleDAGSDNodes
{
654 ScheduleDAGLinearize(MachineFunction
&mf
) : ScheduleDAGSDNodes(mf
) {}
656 void Schedule() override
;
659 EmitSchedule(MachineBasicBlock::iterator
&InsertPos
) override
;
662 std::vector
<SDNode
*> Sequence
;
663 DenseMap
<SDNode
*, SDNode
*> GluedMap
; // Cache glue to its user
665 void ScheduleNode(SDNode
*N
);
667 } // end anonymous namespace
669 void ScheduleDAGLinearize::ScheduleNode(SDNode
*N
) {
670 if (N
->getNodeId() != 0)
671 llvm_unreachable(nullptr);
673 if (!N
->isMachineOpcode() &&
674 (N
->getOpcode() == ISD::EntryToken
|| isPassiveNode(N
)))
675 // These nodes do not need to be translated into MIs.
678 DEBUG(dbgs() << "\n*** Scheduling: ");
680 Sequence
.push_back(N
);
682 unsigned NumOps
= N
->getNumOperands();
683 if (unsigned NumLeft
= NumOps
) {
684 SDNode
*GluedOpN
= nullptr;
686 const SDValue
&Op
= N
->getOperand(NumLeft
-1);
687 SDNode
*OpN
= Op
.getNode();
689 if (NumLeft
== NumOps
&& Op
.getValueType() == MVT::Glue
) {
690 // Schedule glue operand right above N.
692 assert(OpN
->getNodeId() != 0 && "Glue operand not ready?");
699 // Glue operand is already scheduled.
702 DenseMap
<SDNode
*, SDNode
*>::iterator DI
= GluedMap
.find(OpN
);
703 if (DI
!= GluedMap
.end() && DI
->second
!= N
)
704 // Users of glues are counted against the glued users.
707 unsigned Degree
= OpN
->getNodeId();
708 assert(Degree
> 0 && "Predecessor over-released!");
709 OpN
->setNodeId(--Degree
);
716 /// findGluedUser - Find the representative use of a glue value by walking
718 static SDNode
*findGluedUser(SDNode
*N
) {
719 while (SDNode
*Glued
= N
->getGluedUser())
724 void ScheduleDAGLinearize::Schedule() {
725 DEBUG(dbgs() << "********** DAG Linearization **********\n");
727 SmallVector
<SDNode
*, 8> Glues
;
728 unsigned DAGSize
= 0;
729 for (SelectionDAG::allnodes_iterator I
= DAG
->allnodes_begin(),
730 E
= DAG
->allnodes_end(); I
!= E
; ++I
) {
733 // Use node id to record degree.
734 unsigned Degree
= N
->use_size();
735 N
->setNodeId(Degree
);
736 unsigned NumVals
= N
->getNumValues();
737 if (NumVals
&& N
->getValueType(NumVals
-1) == MVT::Glue
&&
738 N
->hasAnyUseOfValue(NumVals
-1)) {
739 SDNode
*User
= findGluedUser(N
);
742 GluedMap
.insert(std::make_pair(N
, User
));
746 if (N
->isMachineOpcode() ||
747 (N
->getOpcode() != ISD::EntryToken
&& !isPassiveNode(N
)))
751 for (unsigned i
= 0, e
= Glues
.size(); i
!= e
; ++i
) {
752 SDNode
*Glue
= Glues
[i
];
753 SDNode
*GUser
= GluedMap
[Glue
];
754 unsigned Degree
= Glue
->getNodeId();
755 unsigned UDegree
= GUser
->getNodeId();
757 // Glue user must be scheduled together with the glue operand. So other
758 // users of the glue operand must be treated as its users.
759 SDNode
*ImmGUser
= Glue
->getGluedUser();
760 for (SDNode::use_iterator ui
= Glue
->use_begin(), ue
= Glue
->use_end();
764 GUser
->setNodeId(UDegree
+ Degree
);
768 Sequence
.reserve(DAGSize
);
769 ScheduleNode(DAG
->getRoot().getNode());
773 ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator
&InsertPos
) {
774 InstrEmitter
Emitter(BB
, InsertPos
);
775 DenseMap
<SDValue
, unsigned> VRBaseMap
;
778 dbgs() << "\n*** Final schedule ***\n";
781 // FIXME: Handle dbg_values.
782 unsigned NumNodes
= Sequence
.size();
783 for (unsigned i
= 0; i
!= NumNodes
; ++i
) {
784 SDNode
*N
= Sequence
[NumNodes
-i
-1];
786 Emitter
.EmitNode(N
, false, false, VRBaseMap
);
789 DEBUG(dbgs() << '\n');
791 InsertPos
= Emitter
.getInsertPos();
792 return Emitter
.getBlock();
795 //===----------------------------------------------------------------------===//
796 // Public Constructor Functions
797 //===----------------------------------------------------------------------===//
799 llvm::ScheduleDAGSDNodes
*
800 llvm::createFastDAGScheduler(SelectionDAGISel
*IS
, CodeGenOpt::Level
) {
801 return new ScheduleDAGFast(*IS
->MF
);
804 llvm::ScheduleDAGSDNodes
*
805 llvm::createDAGLinearizer(SelectionDAGISel
*IS
, CodeGenOpt::Level
) {
806 return new ScheduleDAGLinearize(*IS
->MF
);