1//===----- ScheduleDAGFast.cpp - Fast poor list scheduler -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This implements a fast scheduler.
10//
11//===----------------------------------------------------------------------===//
12
13#include "InstrEmitter.h"
14#include "SDNodeDbgValue.h"
15#include "ScheduleDAGSDNodes.h"
16#include "llvm/ADT/SmallSet.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/CodeGen/SchedulerRegistry.h"
19#include "llvm/CodeGen/SelectionDAGISel.h"
20#include "llvm/CodeGen/TargetInstrInfo.h"
21#include "llvm/CodeGen/TargetRegisterInfo.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"
26using namespace llvm;
27
28#define DEBUG_TYPE "pre-RA-sched"
29
30STATISTIC(NumUnfolds, "Number of nodes unfolded");
31STATISTIC(NumDups, "Number of duplicated nodes");
32STATISTIC(NumPRCopies, "Number of physical copies");
33
34static RegisterScheduler
35 fastDAGScheduler("fast", "Fast suboptimal list scheduling",
36 createFastDAGScheduler);
37static RegisterScheduler
38 linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling",
39 createDAGLinearizer);
40
41
42namespace {
43 /// FastPriorityQueue - A degenerate priority queue that considers
44 /// all nodes to have the same priority.
45 ///
46 struct FastPriorityQueue {
47 SmallVector<SUnit *, 16> Queue;
48
49 bool empty() const { return Queue.empty(); }
50
51 void push(SUnit *U) {
52 Queue.push_back(Elt: U);
53 }
54
55 SUnit *pop() {
56 if (empty()) return nullptr;
57 return Queue.pop_back_val();
58 }
59 };
60
61//===----------------------------------------------------------------------===//
62/// ScheduleDAGFast - The actual "fast" list scheduler implementation.
63///
64class ScheduleDAGFast : public ScheduleDAGSDNodes {
65private:
66 /// AvailableQueue - The priority queue to use for the available SUnits.
67 FastPriorityQueue AvailableQueue;
68
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.
72 unsigned NumLiveRegs = 0u;
73 std::vector<SUnit*> LiveRegDefs;
74 std::vector<unsigned> LiveRegCycles;
75
76public:
77 ScheduleDAGFast(MachineFunction &mf)
78 : ScheduleDAGSDNodes(mf) {}
79
80 void Schedule() override;
81
82 /// AddPred - adds a predecessor edge to SUnit SU.
83 void AddPred(SUnit *SU, const SDep &D) { SU->addPred(D); }
84
85 /// RemovePred - removes a predecessor edge from SUnit SU.
86 void RemovePred(SUnit *SU, const SDep &D) { SU->removePred(D); }
87
88private:
89 void ReleasePred(SUnit *SU, SDep *PredEdge);
90 void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
91 void ScheduleNodeBottomUp(SUnit*, unsigned);
92 SUnit *CopyAndMoveSuccessors(SUnit*);
93 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
94 const TargetRegisterClass*,
95 const TargetRegisterClass*,
96 SmallVectorImpl<SUnit*>&);
97 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
98 void ListScheduleBottomUp();
99
100 /// forceUnitLatencies - The fast scheduler doesn't care about real latencies.
101 bool forceUnitLatencies() const override { return true; }
102};
103} // end anonymous namespace
104
105
106/// Schedule - Schedule the DAG using list scheduling.
107void ScheduleDAGFast::Schedule() {
108 LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");
109
110 NumLiveRegs = 0;
111 LiveRegDefs.resize(new_size: TRI->getNumRegs(), x: nullptr);
112 LiveRegCycles.resize(new_size: TRI->getNumRegs(), x: 0);
113
114 // Build the scheduling graph.
115 BuildSchedGraph();
116
117 LLVM_DEBUG(dump());
118
119 // Execute the actual scheduling loop.
120 ListScheduleBottomUp();
121}
122
123//===----------------------------------------------------------------------===//
124// Bottom-Up Scheduling
125//===----------------------------------------------------------------------===//
126
127/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
128/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
129void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) {
130 SUnit *PredSU = PredEdge->getSUnit();
131
132#ifndef NDEBUG
133 if (PredSU->NumSuccsLeft == 0) {
134 dbgs() << "*** Scheduling failed! ***\n";
135 dumpNode(*PredSU);
136 dbgs() << " has been released too many times!\n";
137 llvm_unreachable(nullptr);
138 }
139#endif
140 --PredSU->NumSuccsLeft;
141
142 // If all the node's successors are scheduled, this node is ready
143 // to be scheduled. Ignore the special EntrySU node.
144 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
145 PredSU->isAvailable = true;
146 AvailableQueue.push(U: PredSU);
147 }
148}
149
150void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
151 // Bottom up: release predecessors
152 for (SDep &Pred : SU->Preds) {
153 ReleasePred(SU, PredEdge: &Pred);
154 if (Pred.isAssignedRegDep()) {
155 // This is a physical register dependency and it's impossible or
156 // expensive to copy the register. Make sure nothing that can
157 // clobber the register is scheduled between the predecessor and
158 // this node.
159 if (!LiveRegDefs[Pred.getReg()]) {
160 ++NumLiveRegs;
161 LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
162 LiveRegCycles[Pred.getReg()] = CurCycle;
163 }
164 }
165 }
166}
167
168/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
169/// count of its predecessors. If a predecessor pending count is zero, add it to
170/// the Available queue.
171void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
172 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
173 LLVM_DEBUG(dumpNode(*SU));
174
175 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
176 SU->setHeightToAtLeast(CurCycle);
177 Sequence.push_back(x: SU);
178
179 ReleasePredecessors(SU, CurCycle);
180
181 // Release all the implicit physical register defs that are live.
182 for (SDep &Succ : SU->Succs) {
183 if (Succ.isAssignedRegDep()) {
184 if (LiveRegCycles[Succ.getReg()] == Succ.getSUnit()->getHeight()) {
185 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
186 assert(LiveRegDefs[Succ.getReg()] == SU &&
187 "Physical register dependency violated?");
188 --NumLiveRegs;
189 LiveRegDefs[Succ.getReg()] = nullptr;
190 LiveRegCycles[Succ.getReg()] = 0;
191 }
192 }
193 }
194
195 SU->isScheduled = true;
196}
197
198/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
199/// successors to the newly created node.
200SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) {
201 if (SU->getNode()->getGluedNode())
202 return nullptr;
203
204 SDNode *N = SU->getNode();
205 if (!N)
206 return nullptr;
207
208 SUnit *NewSU;
209 bool TryUnfold = false;
210 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
211 MVT VT = N->getSimpleValueType(ResNo: i);
212 if (VT == MVT::Glue)
213 return nullptr;
214 else if (VT == MVT::Other)
215 TryUnfold = true;
216 }
217 for (const SDValue &Op : N->op_values()) {
218 MVT VT = Op.getNode()->getSimpleValueType(ResNo: Op.getResNo());
219 if (VT == MVT::Glue)
220 return nullptr;
221 }
222
223 if (TryUnfold) {
224 SmallVector<SDNode*, 2> NewNodes;
225 if (!TII->unfoldMemoryOperand(DAG&: *DAG, N, NewNodes))
226 return nullptr;
227
228 assert(NewNodes.size() == 2 && "Expected a load folding node!");
229
230 N = NewNodes[1];
231 SDNode *LoadNode = NewNodes[0];
232 unsigned NumVals = N->getNumValues();
233 unsigned OldNumVals = SU->getNode()->getNumValues();
234
235 // Give up if LoadNode already exists, see ScheduleDAGRRList::TryUnfoldSU.
236 if (LoadNode->getNodeId() != -1)
237 return nullptr;
238 assert(N->getNodeId() == -1 && "Node using a new load can't exist yet!");
239
240 LLVM_DEBUG(dbgs() << "Unfolding " << *SU << "\n");
241
242 for (unsigned i = 0; i != NumVals; ++i)
243 DAG->ReplaceAllUsesOfValueWith(From: SDValue(SU->getNode(), i), To: SDValue(N, i));
244 DAG->ReplaceAllUsesOfValueWith(From: SDValue(SU->getNode(), OldNumVals - 1),
245 To: SDValue(LoadNode, 1));
246
247 SUnit *NewSU = newSUnit(N);
248 N->setNodeId(NewSU->NodeNum);
249
250 const MCInstrDesc &MCID = TII->get(Opcode: N->getMachineOpcode());
251 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
252 if (MCID.getOperandConstraint(OpNum: i, Constraint: MCOI::TIED_TO) != -1) {
253 NewSU->isTwoAddress = true;
254 break;
255 }
256 }
257 if (MCID.isCommutable())
258 NewSU->isCommutable = true;
259
260 SUnit *LoadSU = newSUnit(N: LoadNode);
261 LoadNode->setNodeId(LoadSU->NodeNum);
262
263 SDep ChainPred;
264 SmallVector<SDep, 4> ChainSuccs;
265 SmallVector<SDep, 4> LoadPreds;
266 SmallVector<SDep, 4> NodePreds;
267 SmallVector<SDep, 4> NodeSuccs;
268 for (SDep &Pred : SU->Preds) {
269 if (Pred.isCtrl())
270 ChainPred = Pred;
271 else if (Pred.getSUnit()->getNode() &&
272 Pred.getSUnit()->getNode()->isOperandOf(N: LoadNode))
273 LoadPreds.push_back(Elt: Pred);
274 else
275 NodePreds.push_back(Elt: Pred);
276 }
277 for (SDep &Succ : SU->Succs) {
278 if (Succ.isCtrl())
279 ChainSuccs.push_back(Elt: Succ);
280 else
281 NodeSuccs.push_back(Elt: Succ);
282 }
283
284 if (ChainPred.getSUnit()) {
285 RemovePred(SU, D: ChainPred);
286 AddPred(SU: LoadSU, D: ChainPred);
287 }
288 for (const SDep &Pred : LoadPreds) {
289 RemovePred(SU, D: Pred);
290 AddPred(SU: LoadSU, D: Pred);
291 }
292 for (const SDep &Pred : NodePreds) {
293 RemovePred(SU, D: Pred);
294 AddPred(SU: NewSU, D: Pred);
295 }
296 for (SDep D : NodeSuccs) {
297 SUnit *SuccDep = D.getSUnit();
298 D.setSUnit(SU);
299 RemovePred(SU: SuccDep, D);
300 D.setSUnit(NewSU);
301 AddPred(SU: SuccDep, D);
302 }
303 for (SDep D : ChainSuccs) {
304 SUnit *SuccDep = D.getSUnit();
305 D.setSUnit(SU);
306 RemovePred(SU: SuccDep, D);
307 D.setSUnit(LoadSU);
308 AddPred(SU: SuccDep, D);
309 }
310 SDep D(LoadSU, SDep::Barrier);
311 D.setLatency(LoadSU->Latency);
312 AddPred(SU: NewSU, D);
313
314 ++NumUnfolds;
315
316 if (NewSU->NumSuccsLeft == 0) {
317 NewSU->isAvailable = true;
318 return NewSU;
319 }
320 SU = NewSU;
321 }
322
323 LLVM_DEBUG(dbgs() << "Duplicating " << *SU << "\n");
324 NewSU = Clone(Old: SU);
325
326 // New SUnit has the exact same predecessors.
327 for (SDep &Pred : SU->Preds)
328 if (!Pred.isArtificial())
329 AddPred(SU: NewSU, D: Pred);
330
331 // Only copy scheduled successors. Cut them from old node's successor
332 // list and move them over.
333 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
334 for (SDep &Succ : SU->Succs) {
335 if (Succ.isArtificial())
336 continue;
337 SUnit *SuccSU = Succ.getSUnit();
338 if (SuccSU->isScheduled) {
339 SDep D = Succ;
340 D.setSUnit(NewSU);
341 AddPred(SU: SuccSU, D);
342 D.setSUnit(SU);
343 DelDeps.push_back(Elt: std::make_pair(x&: SuccSU, y&: D));
344 }
345 }
346 for (const auto &[Del, Dep] : DelDeps)
347 RemovePred(SU: Del, D: Dep);
348
349 ++NumDups;
350 return NewSU;
351}
352
353/// InsertCopiesAndMoveSuccs - Insert register copies and move all
354/// scheduled successors of the given SUnit to the last copy.
355void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
356 const TargetRegisterClass *DestRC,
357 const TargetRegisterClass *SrcRC,
358 SmallVectorImpl<SUnit*> &Copies) {
359 SUnit *CopyFromSU = newSUnit(N: static_cast<SDNode *>(nullptr));
360 CopyFromSU->CopySrcRC = SrcRC;
361 CopyFromSU->CopyDstRC = DestRC;
362
363 SUnit *CopyToSU = newSUnit(N: static_cast<SDNode *>(nullptr));
364 CopyToSU->CopySrcRC = DestRC;
365 CopyToSU->CopyDstRC = SrcRC;
366
367 // Only copy scheduled successors. Cut them from old node's successor
368 // list and move them over.
369 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
370 for (SDep &Succ : SU->Succs) {
371 if (Succ.isArtificial())
372 continue;
373 SUnit *SuccSU = Succ.getSUnit();
374 if (SuccSU->isScheduled) {
375 SDep D = Succ;
376 D.setSUnit(CopyToSU);
377 AddPred(SU: SuccSU, D);
378 DelDeps.push_back(Elt: std::make_pair(x&: SuccSU, y&: Succ));
379 }
380 }
381 for (const auto &[Del, Dep] : DelDeps)
382 RemovePred(SU: Del, D: Dep);
383 SDep FromDep(SU, SDep::Data, Reg);
384 FromDep.setLatency(SU->Latency);
385 AddPred(SU: CopyFromSU, D: FromDep);
386 SDep ToDep(CopyFromSU, SDep::Data, 0);
387 ToDep.setLatency(CopyFromSU->Latency);
388 AddPred(SU: CopyToSU, D: ToDep);
389
390 Copies.push_back(Elt: CopyFromSU);
391 Copies.push_back(Elt: CopyToSU);
392
393 ++NumPRCopies;
394}
395
396/// CheckForLiveRegDef - Return true and update live register vector if the
397/// specified register def of the specified SUnit clobbers any "live" registers.
398static bool CheckForLiveRegDef(SUnit *SU, MCRegister Reg,
399 std::vector<SUnit *> &LiveRegDefs,
400 SmallSet<unsigned, 4> &RegAdded,
401 SmallVectorImpl<unsigned> &LRegs,
402 const TargetRegisterInfo *TRI,
403 const SDNode *Node = nullptr) {
404 bool Added = false;
405 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
406 // Check if Ref is live.
407 if (!LiveRegDefs[*AI])
408 continue;
409
410 // Allow multiple uses of the same def.
411 if (LiveRegDefs[*AI] == SU)
412 continue;
413
414 // Allow multiple uses of same def
415 if (Node && LiveRegDefs[*AI]->getNode() == Node)
416 continue;
417
418 // Add Reg to the set of interfering live regs.
419 if (RegAdded.insert(V: *AI).second) {
420 LRegs.push_back(Elt: *AI);
421 Added = true;
422 }
423 }
424 return Added;
425}
426
427/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
428/// scheduling of the given node to satisfy live physical register dependencies.
429/// If the specific node is the last one that's available to schedule, do
430/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
431bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU,
432 SmallVectorImpl<unsigned> &LRegs){
433 if (NumLiveRegs == 0)
434 return false;
435
436 SmallSet<unsigned, 4> RegAdded;
437 // If this node would clobber any "live" register, then it's not ready.
438 for (SDep &Pred : SU->Preds) {
439 if (Pred.isAssignedRegDep()) {
440 CheckForLiveRegDef(SU: Pred.getSUnit(), Reg: Pred.getReg(), LiveRegDefs,
441 RegAdded, LRegs, TRI);
442 }
443 }
444
445 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
446 if (Node->getOpcode() == ISD::INLINEASM ||
447 Node->getOpcode() == ISD::INLINEASM_BR) {
448 // Inline asm can clobber physical defs.
449 unsigned NumOps = Node->getNumOperands();
450 if (Node->getOperand(Num: NumOps-1).getValueType() == MVT::Glue)
451 --NumOps; // Ignore the glue operand.
452
453 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
454 unsigned Flags = Node->getConstantOperandVal(Num: i);
455 const InlineAsm::Flag F(Flags);
456 unsigned NumVals = F.getNumOperandRegisters();
457
458 ++i; // Skip the ID value.
459 if (F.isRegDefKind() || F.isRegDefEarlyClobberKind() ||
460 F.isClobberKind()) {
461 // Check for def of register or earlyclobber register.
462 for (; NumVals; --NumVals, ++i) {
463 Register Reg = cast<RegisterSDNode>(Val: Node->getOperand(Num: i))->getReg();
464 if (Reg.isPhysical())
465 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
466 }
467 } else
468 i += NumVals;
469 }
470 continue;
471 }
472
473 if (Node->getOpcode() == ISD::CopyToReg) {
474 Register Reg = cast<RegisterSDNode>(Val: Node->getOperand(Num: 1))->getReg();
475 if (Reg.isPhysical()) {
476 SDNode *SrcNode = Node->getOperand(Num: 2).getNode();
477 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI, Node: SrcNode);
478 }
479 }
480
481 if (!Node->isMachineOpcode())
482 continue;
483 const MCInstrDesc &MCID = TII->get(Opcode: Node->getMachineOpcode());
484 for (MCPhysReg Reg : MCID.implicit_defs())
485 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
486 }
487 return !LRegs.empty();
488}
489
490
491/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
492/// schedulers.
493void ScheduleDAGFast::ListScheduleBottomUp() {
494 unsigned CurCycle = 0;
495
496 // Release any predecessors of the special Exit node.
497 ReleasePredecessors(SU: &ExitSU, CurCycle);
498
499 // Add root to Available queue.
500 if (!SUnits.empty()) {
501 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
502 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
503 RootSU->isAvailable = true;
504 AvailableQueue.push(U: RootSU);
505 }
506
507 // While Available queue is not empty, grab the node with the highest
508 // priority. If it is not ready put it back. Schedule the node.
509 SmallVector<SUnit*, 4> NotReady;
510 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
511 Sequence.reserve(n: SUnits.size());
512 while (!AvailableQueue.empty()) {
513 bool Delayed = false;
514 LRegsMap.clear();
515 SUnit *CurSU = AvailableQueue.pop();
516 while (CurSU) {
517 SmallVector<unsigned, 4> LRegs;
518 if (!DelayForLiveRegsBottomUp(SU: CurSU, LRegs))
519 break;
520 Delayed = true;
521 LRegsMap.insert(KV: std::make_pair(x&: CurSU, y&: LRegs));
522
523 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
524 NotReady.push_back(Elt: CurSU);
525 CurSU = AvailableQueue.pop();
526 }
527
528 // All candidates are delayed due to live physical reg dependencies.
529 // Try code duplication or inserting cross class copies
530 // to resolve it.
531 if (Delayed && !CurSU) {
532 if (!CurSU) {
533 // Try duplicating the nodes that produces these
534 // "expensive to copy" values to break the dependency. In case even
535 // that doesn't work, insert cross class copies.
536 SUnit *TrySU = NotReady[0];
537 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
538 assert(LRegs.size() == 1 && "Can't handle this yet!");
539 unsigned Reg = LRegs[0];
540 SUnit *LRDef = LiveRegDefs[Reg];
541 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
542 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
543
544 // If cross copy register class is the same as RC, then it must be
545 // possible copy the value directly. Do not try duplicate the def.
546 // If cross copy register class is not the same as RC, then it's
547 // possible to copy the value but it require cross register class copies
548 // and it is expensive.
549 // If cross copy register class is null, then it's not possible to copy
550 // the value at all.
551 SUnit *NewDef = nullptr;
552 if (DestRC != RC) {
553 NewDef = CopyAndMoveSuccessors(SU: LRDef);
554 if (!DestRC && !NewDef)
555 report_fatal_error(reason: "Can't handle live physical "
556 "register dependency!");
557 }
558 if (!NewDef) {
559 // Issue copies, these can be expensive cross register class copies.
560 SmallVector<SUnit*, 2> Copies;
561 InsertCopiesAndMoveSuccs(SU: LRDef, Reg, DestRC, SrcRC: RC, Copies);
562 LLVM_DEBUG(dbgs() << "Adding an edge from " << *TrySU << " to "
563 << *Copies.front() << "\n");
564 AddPred(SU: TrySU, D: SDep(Copies.front(), SDep::Artificial));
565 NewDef = Copies.back();
566 }
567
568 LLVM_DEBUG(dbgs() << "Adding an edge from " << *NewDef << " to "
569 << *TrySU << "\n");
570 LiveRegDefs[Reg] = NewDef;
571 AddPred(SU: NewDef, D: SDep(TrySU, SDep::Artificial));
572 TrySU->isAvailable = false;
573 CurSU = NewDef;
574 }
575
576 if (!CurSU) {
577 llvm_unreachable("Unable to resolve live physical register dependencies!");
578 }
579 }
580
581 // Add the nodes that aren't ready back onto the available list.
582 for (SUnit *SU : NotReady) {
583 SU->isPending = false;
584 // May no longer be available due to backtracking.
585 if (SU->isAvailable)
586 AvailableQueue.push(U: SU);
587 }
588 NotReady.clear();
589
590 if (CurSU)
591 ScheduleNodeBottomUp(SU: CurSU, CurCycle);
592 ++CurCycle;
593 }
594
595 // Reverse the order since it is bottom up.
596 std::reverse(first: Sequence.begin(), last: Sequence.end());
597
598#ifndef NDEBUG
599 VerifyScheduledSequence(/*isBottomUp=*/true);
600#endif
601}
602
603
604namespace {
605//===----------------------------------------------------------------------===//
606// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the
607// DAG in topological order.
608// IMPORTANT: this may not work for targets with phyreg dependency.
609//
610class ScheduleDAGLinearize : public ScheduleDAGSDNodes {
611public:
612 ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {}
613
614 void Schedule() override;
615
616 MachineBasicBlock *
617 EmitSchedule(MachineBasicBlock::iterator &InsertPos) override;
618
619private:
620 std::vector<SDNode*> Sequence;
621 DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user
622
623 void ScheduleNode(SDNode *N);
624};
625} // end anonymous namespace
626
627void ScheduleDAGLinearize::ScheduleNode(SDNode *N) {
628 if (N->getNodeId() != 0)
629 llvm_unreachable(nullptr);
630
631 if (!N->isMachineOpcode() &&
632 (N->getOpcode() == ISD::EntryToken || isPassiveNode(Node: N)))
633 // These nodes do not need to be translated into MIs.
634 return;
635
636 LLVM_DEBUG(dbgs() << "\n*** Scheduling: ");
637 LLVM_DEBUG(N->dump(DAG));
638 Sequence.push_back(x: N);
639
640 unsigned NumOps = N->getNumOperands();
641 if (unsigned NumLeft = NumOps) {
642 SDNode *GluedOpN = nullptr;
643 do {
644 const SDValue &Op = N->getOperand(Num: NumLeft-1);
645 SDNode *OpN = Op.getNode();
646
647 if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) {
648 // Schedule glue operand right above N.
649 GluedOpN = OpN;
650 assert(OpN->getNodeId() != 0 && "Glue operand not ready?");
651 OpN->setNodeId(0);
652 ScheduleNode(N: OpN);
653 continue;
654 }
655
656 if (OpN == GluedOpN)
657 // Glue operand is already scheduled.
658 continue;
659
660 auto DI = GluedMap.find(Val: OpN);
661 if (DI != GluedMap.end() && DI->second != N)
662 // Users of glues are counted against the glued users.
663 OpN = DI->second;
664
665 unsigned Degree = OpN->getNodeId();
666 assert(Degree > 0 && "Predecessor over-released!");
667 OpN->setNodeId(--Degree);
668 if (Degree == 0)
669 ScheduleNode(N: OpN);
670 } while (--NumLeft);
671 }
672}
673
674/// findGluedUser - Find the representative use of a glue value by walking
675/// the use chain.
676static SDNode *findGluedUser(SDNode *N) {
677 while (SDNode *Glued = N->getGluedUser())
678 N = Glued;
679 return N;
680}
681
682void ScheduleDAGLinearize::Schedule() {
683 LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n");
684
685 SmallVector<SDNode*, 8> Glues;
686 unsigned DAGSize = 0;
687 for (SDNode &Node : DAG->allnodes()) {
688 SDNode *N = &Node;
689
690 // Use node id to record degree.
691 unsigned Degree = N->use_size();
692 N->setNodeId(Degree);
693 unsigned NumVals = N->getNumValues();
694 if (NumVals && N->getValueType(ResNo: NumVals-1) == MVT::Glue &&
695 N->hasAnyUseOfValue(Value: NumVals-1)) {
696 SDNode *User = findGluedUser(N);
697 if (User) {
698 Glues.push_back(Elt: N);
699 GluedMap.insert(KV: std::make_pair(x&: N, y&: User));
700 }
701 }
702
703 if (N->isMachineOpcode() ||
704 (N->getOpcode() != ISD::EntryToken && !isPassiveNode(Node: N)))
705 ++DAGSize;
706 }
707
708 for (SDNode *Glue : Glues) {
709 SDNode *GUser = GluedMap[Glue];
710 unsigned Degree = Glue->getNodeId();
711 unsigned UDegree = GUser->getNodeId();
712
713 // Glue user must be scheduled together with the glue operand. So other
714 // users of the glue operand must be treated as its users.
715 SDNode *ImmGUser = Glue->getGluedUser();
716 for (const SDNode *U : Glue->users())
717 if (U == ImmGUser)
718 --Degree;
719 GUser->setNodeId(UDegree + Degree);
720 Glue->setNodeId(1);
721 }
722
723 Sequence.reserve(n: DAGSize);
724 ScheduleNode(N: DAG->getRoot().getNode());
725}
726
727MachineBasicBlock*
728ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
729 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
730 InstrEmitter::VRBaseMapType VRBaseMap;
731
732 LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; });
733
734 unsigned NumNodes = Sequence.size();
735 MachineBasicBlock *BB = Emitter.getBlock();
736 for (unsigned i = 0; i != NumNodes; ++i) {
737 SDNode *N = Sequence[NumNodes-i-1];
738 LLVM_DEBUG(N->dump(DAG));
739 Emitter.EmitNode(Node: N, IsClone: false, IsCloned: false, VRBaseMap);
740
741 // Emit any debug values associated with the node.
742 if (N->getHasDebugValue()) {
743 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
744 for (auto *DV : DAG->GetDbgValues(SD: N)) {
745 if (!DV->isEmitted())
746 if (auto *DbgMI = Emitter.EmitDbgValue(SD: DV, VRBaseMap))
747 BB->insert(I: InsertPos, MI: DbgMI);
748 }
749 }
750 }
751
752 LLVM_DEBUG(dbgs() << '\n');
753
754 InsertPos = Emitter.getInsertPos();
755 return Emitter.getBlock();
756}
757
758//===----------------------------------------------------------------------===//
759// Public Constructor Functions
760//===----------------------------------------------------------------------===//
761
762llvm::ScheduleDAGSDNodes *llvm::createFastDAGScheduler(SelectionDAGISel *IS,
763 CodeGenOptLevel) {
764 return new ScheduleDAGFast(*IS->MF);
765}
766
767llvm::ScheduleDAGSDNodes *llvm::createDAGLinearizer(SelectionDAGISel *IS,
768 CodeGenOptLevel) {
769 return new ScheduleDAGLinearize(*IS->MF);
770}
771