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 LLVM_DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n");
229 assert(NewNodes.size() == 2 && "Expected a load folding node!");
230
231 N = NewNodes[1];
232 SDNode *LoadNode = NewNodes[0];
233 unsigned NumVals = N->getNumValues();
234 unsigned OldNumVals = SU->getNode()->getNumValues();
235 for (unsigned i = 0; i != NumVals; ++i)
236 DAG->ReplaceAllUsesOfValueWith(From: SDValue(SU->getNode(), i), To: SDValue(N, i));
237 DAG->ReplaceAllUsesOfValueWith(From: SDValue(SU->getNode(), OldNumVals-1),
238 To: SDValue(LoadNode, 1));
239
240 SUnit *NewSU = newSUnit(N);
241 assert(N->getNodeId() == -1 && "Node already inserted!");
242 N->setNodeId(NewSU->NodeNum);
243
244 const MCInstrDesc &MCID = TII->get(Opcode: N->getMachineOpcode());
245 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
246 if (MCID.getOperandConstraint(OpNum: i, Constraint: MCOI::TIED_TO) != -1) {
247 NewSU->isTwoAddress = true;
248 break;
249 }
250 }
251 if (MCID.isCommutable())
252 NewSU->isCommutable = true;
253
254 // LoadNode may already exist. This can happen when there is another
255 // load from the same location and producing the same type of value
256 // but it has different alignment or volatileness.
257 bool isNewLoad = true;
258 SUnit *LoadSU;
259 if (LoadNode->getNodeId() != -1) {
260 LoadSU = &SUnits[LoadNode->getNodeId()];
261 isNewLoad = false;
262 } else {
263 LoadSU = newSUnit(N: LoadNode);
264 LoadNode->setNodeId(LoadSU->NodeNum);
265 }
266
267 SDep ChainPred;
268 SmallVector<SDep, 4> ChainSuccs;
269 SmallVector<SDep, 4> LoadPreds;
270 SmallVector<SDep, 4> NodePreds;
271 SmallVector<SDep, 4> NodeSuccs;
272 for (SDep &Pred : SU->Preds) {
273 if (Pred.isCtrl())
274 ChainPred = Pred;
275 else if (Pred.getSUnit()->getNode() &&
276 Pred.getSUnit()->getNode()->isOperandOf(N: LoadNode))
277 LoadPreds.push_back(Elt: Pred);
278 else
279 NodePreds.push_back(Elt: Pred);
280 }
281 for (SDep &Succ : SU->Succs) {
282 if (Succ.isCtrl())
283 ChainSuccs.push_back(Elt: Succ);
284 else
285 NodeSuccs.push_back(Elt: Succ);
286 }
287
288 if (ChainPred.getSUnit()) {
289 RemovePred(SU, D: ChainPred);
290 if (isNewLoad)
291 AddPred(SU: LoadSU, D: ChainPred);
292 }
293 for (const SDep &Pred : LoadPreds) {
294 RemovePred(SU, D: Pred);
295 if (isNewLoad) {
296 AddPred(SU: LoadSU, D: Pred);
297 }
298 }
299 for (const SDep &Pred : NodePreds) {
300 RemovePred(SU, D: Pred);
301 AddPred(SU: NewSU, D: Pred);
302 }
303 for (SDep D : NodeSuccs) {
304 SUnit *SuccDep = D.getSUnit();
305 D.setSUnit(SU);
306 RemovePred(SU: SuccDep, D);
307 D.setSUnit(NewSU);
308 AddPred(SU: SuccDep, D);
309 }
310 for (SDep D : ChainSuccs) {
311 SUnit *SuccDep = D.getSUnit();
312 D.setSUnit(SU);
313 RemovePred(SU: SuccDep, D);
314 if (isNewLoad) {
315 D.setSUnit(LoadSU);
316 AddPred(SU: SuccDep, D);
317 }
318 }
319 if (isNewLoad) {
320 SDep D(LoadSU, SDep::Barrier);
321 D.setLatency(LoadSU->Latency);
322 AddPred(SU: NewSU, D);
323 }
324
325 ++NumUnfolds;
326
327 if (NewSU->NumSuccsLeft == 0) {
328 NewSU->isAvailable = true;
329 return NewSU;
330 }
331 SU = NewSU;
332 }
333
334 LLVM_DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n");
335 NewSU = Clone(Old: SU);
336
337 // New SUnit has the exact same predecessors.
338 for (SDep &Pred : SU->Preds)
339 if (!Pred.isArtificial())
340 AddPred(SU: NewSU, D: Pred);
341
342 // Only copy scheduled successors. Cut them from old node's successor
343 // list and move them over.
344 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
345 for (SDep &Succ : SU->Succs) {
346 if (Succ.isArtificial())
347 continue;
348 SUnit *SuccSU = Succ.getSUnit();
349 if (SuccSU->isScheduled) {
350 SDep D = Succ;
351 D.setSUnit(NewSU);
352 AddPred(SU: SuccSU, D);
353 D.setSUnit(SU);
354 DelDeps.push_back(Elt: std::make_pair(x&: SuccSU, y&: D));
355 }
356 }
357 for (const auto &[Del, Dep] : DelDeps)
358 RemovePred(SU: Del, D: Dep);
359
360 ++NumDups;
361 return NewSU;
362}
363
364/// InsertCopiesAndMoveSuccs - Insert register copies and move all
365/// scheduled successors of the given SUnit to the last copy.
366void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
367 const TargetRegisterClass *DestRC,
368 const TargetRegisterClass *SrcRC,
369 SmallVectorImpl<SUnit*> &Copies) {
370 SUnit *CopyFromSU = newSUnit(N: static_cast<SDNode *>(nullptr));
371 CopyFromSU->CopySrcRC = SrcRC;
372 CopyFromSU->CopyDstRC = DestRC;
373
374 SUnit *CopyToSU = newSUnit(N: static_cast<SDNode *>(nullptr));
375 CopyToSU->CopySrcRC = DestRC;
376 CopyToSU->CopyDstRC = SrcRC;
377
378 // Only copy scheduled successors. Cut them from old node's successor
379 // list and move them over.
380 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
381 for (SDep &Succ : SU->Succs) {
382 if (Succ.isArtificial())
383 continue;
384 SUnit *SuccSU = Succ.getSUnit();
385 if (SuccSU->isScheduled) {
386 SDep D = Succ;
387 D.setSUnit(CopyToSU);
388 AddPred(SU: SuccSU, D);
389 DelDeps.push_back(Elt: std::make_pair(x&: SuccSU, y&: Succ));
390 }
391 }
392 for (const auto &[Del, Dep] : DelDeps)
393 RemovePred(SU: Del, D: Dep);
394 SDep FromDep(SU, SDep::Data, Reg);
395 FromDep.setLatency(SU->Latency);
396 AddPred(SU: CopyFromSU, D: FromDep);
397 SDep ToDep(CopyFromSU, SDep::Data, 0);
398 ToDep.setLatency(CopyFromSU->Latency);
399 AddPred(SU: CopyToSU, D: ToDep);
400
401 Copies.push_back(Elt: CopyFromSU);
402 Copies.push_back(Elt: CopyToSU);
403
404 ++NumPRCopies;
405}
406
407/// CheckForLiveRegDef - Return true and update live register vector if the
408/// specified register def of the specified SUnit clobbers any "live" registers.
409static bool CheckForLiveRegDef(SUnit *SU, MCRegister Reg,
410 std::vector<SUnit *> &LiveRegDefs,
411 SmallSet<unsigned, 4> &RegAdded,
412 SmallVectorImpl<unsigned> &LRegs,
413 const TargetRegisterInfo *TRI,
414 const SDNode *Node = nullptr) {
415 bool Added = false;
416 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
417 // Check if Ref is live.
418 if (!LiveRegDefs[*AI])
419 continue;
420
421 // Allow multiple uses of the same def.
422 if (LiveRegDefs[*AI] == SU)
423 continue;
424
425 // Allow multiple uses of same def
426 if (Node && LiveRegDefs[*AI]->getNode() == Node)
427 continue;
428
429 // Add Reg to the set of interfering live regs.
430 if (RegAdded.insert(V: *AI).second) {
431 LRegs.push_back(Elt: *AI);
432 Added = true;
433 }
434 }
435 return Added;
436}
437
438/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
439/// scheduling of the given node to satisfy live physical register dependencies.
440/// If the specific node is the last one that's available to schedule, do
441/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
442bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU,
443 SmallVectorImpl<unsigned> &LRegs){
444 if (NumLiveRegs == 0)
445 return false;
446
447 SmallSet<unsigned, 4> RegAdded;
448 // If this node would clobber any "live" register, then it's not ready.
449 for (SDep &Pred : SU->Preds) {
450 if (Pred.isAssignedRegDep()) {
451 CheckForLiveRegDef(SU: Pred.getSUnit(), Reg: Pred.getReg(), LiveRegDefs,
452 RegAdded, LRegs, TRI);
453 }
454 }
455
456 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
457 if (Node->getOpcode() == ISD::INLINEASM ||
458 Node->getOpcode() == ISD::INLINEASM_BR) {
459 // Inline asm can clobber physical defs.
460 unsigned NumOps = Node->getNumOperands();
461 if (Node->getOperand(Num: NumOps-1).getValueType() == MVT::Glue)
462 --NumOps; // Ignore the glue operand.
463
464 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
465 unsigned Flags = Node->getConstantOperandVal(Num: i);
466 const InlineAsm::Flag F(Flags);
467 unsigned NumVals = F.getNumOperandRegisters();
468
469 ++i; // Skip the ID value.
470 if (F.isRegDefKind() || F.isRegDefEarlyClobberKind() ||
471 F.isClobberKind()) {
472 // Check for def of register or earlyclobber register.
473 for (; NumVals; --NumVals, ++i) {
474 Register Reg = cast<RegisterSDNode>(Val: Node->getOperand(Num: i))->getReg();
475 if (Reg.isPhysical())
476 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
477 }
478 } else
479 i += NumVals;
480 }
481 continue;
482 }
483
484 if (Node->getOpcode() == ISD::CopyToReg) {
485 Register Reg = cast<RegisterSDNode>(Val: Node->getOperand(Num: 1))->getReg();
486 if (Reg.isPhysical()) {
487 SDNode *SrcNode = Node->getOperand(Num: 2).getNode();
488 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI, Node: SrcNode);
489 }
490 }
491
492 if (!Node->isMachineOpcode())
493 continue;
494 const MCInstrDesc &MCID = TII->get(Opcode: Node->getMachineOpcode());
495 for (MCPhysReg Reg : MCID.implicit_defs())
496 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
497 }
498 return !LRegs.empty();
499}
500
501
502/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
503/// schedulers.
504void ScheduleDAGFast::ListScheduleBottomUp() {
505 unsigned CurCycle = 0;
506
507 // Release any predecessors of the special Exit node.
508 ReleasePredecessors(SU: &ExitSU, CurCycle);
509
510 // Add root to Available queue.
511 if (!SUnits.empty()) {
512 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
513 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
514 RootSU->isAvailable = true;
515 AvailableQueue.push(U: RootSU);
516 }
517
518 // While Available queue is not empty, grab the node with the highest
519 // priority. If it is not ready put it back. Schedule the node.
520 SmallVector<SUnit*, 4> NotReady;
521 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
522 Sequence.reserve(n: SUnits.size());
523 while (!AvailableQueue.empty()) {
524 bool Delayed = false;
525 LRegsMap.clear();
526 SUnit *CurSU = AvailableQueue.pop();
527 while (CurSU) {
528 SmallVector<unsigned, 4> LRegs;
529 if (!DelayForLiveRegsBottomUp(SU: CurSU, LRegs))
530 break;
531 Delayed = true;
532 LRegsMap.insert(KV: std::make_pair(x&: CurSU, y&: LRegs));
533
534 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
535 NotReady.push_back(Elt: CurSU);
536 CurSU = AvailableQueue.pop();
537 }
538
539 // All candidates are delayed due to live physical reg dependencies.
540 // Try code duplication or inserting cross class copies
541 // to resolve it.
542 if (Delayed && !CurSU) {
543 if (!CurSU) {
544 // Try duplicating the nodes that produces these
545 // "expensive to copy" values to break the dependency. In case even
546 // that doesn't work, insert cross class copies.
547 SUnit *TrySU = NotReady[0];
548 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
549 assert(LRegs.size() == 1 && "Can't handle this yet!");
550 unsigned Reg = LRegs[0];
551 SUnit *LRDef = LiveRegDefs[Reg];
552 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
553 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
554
555 // If cross copy register class is the same as RC, then it must be
556 // possible copy the value directly. Do not try duplicate the def.
557 // If cross copy register class is not the same as RC, then it's
558 // possible to copy the value but it require cross register class copies
559 // and it is expensive.
560 // If cross copy register class is null, then it's not possible to copy
561 // the value at all.
562 SUnit *NewDef = nullptr;
563 if (DestRC != RC) {
564 NewDef = CopyAndMoveSuccessors(SU: LRDef);
565 if (!DestRC && !NewDef)
566 report_fatal_error(reason: "Can't handle live physical "
567 "register dependency!");
568 }
569 if (!NewDef) {
570 // Issue copies, these can be expensive cross register class copies.
571 SmallVector<SUnit*, 2> Copies;
572 InsertCopiesAndMoveSuccs(SU: LRDef, Reg, DestRC, SrcRC: RC, Copies);
573 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum
574 << " to SU #" << Copies.front()->NodeNum << "\n");
575 AddPred(SU: TrySU, D: SDep(Copies.front(), SDep::Artificial));
576 NewDef = Copies.back();
577 }
578
579 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum
580 << " to SU #" << TrySU->NodeNum << "\n");
581 LiveRegDefs[Reg] = NewDef;
582 AddPred(SU: NewDef, D: SDep(TrySU, SDep::Artificial));
583 TrySU->isAvailable = false;
584 CurSU = NewDef;
585 }
586
587 if (!CurSU) {
588 llvm_unreachable("Unable to resolve live physical register dependencies!");
589 }
590 }
591
592 // Add the nodes that aren't ready back onto the available list.
593 for (SUnit *SU : NotReady) {
594 SU->isPending = false;
595 // May no longer be available due to backtracking.
596 if (SU->isAvailable)
597 AvailableQueue.push(U: SU);
598 }
599 NotReady.clear();
600
601 if (CurSU)
602 ScheduleNodeBottomUp(SU: CurSU, CurCycle);
603 ++CurCycle;
604 }
605
606 // Reverse the order since it is bottom up.
607 std::reverse(first: Sequence.begin(), last: Sequence.end());
608
609#ifndef NDEBUG
610 VerifyScheduledSequence(/*isBottomUp=*/true);
611#endif
612}
613
614
615namespace {
616//===----------------------------------------------------------------------===//
617// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the
618// DAG in topological order.
619// IMPORTANT: this may not work for targets with phyreg dependency.
620//
621class ScheduleDAGLinearize : public ScheduleDAGSDNodes {
622public:
623 ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {}
624
625 void Schedule() override;
626
627 MachineBasicBlock *
628 EmitSchedule(MachineBasicBlock::iterator &InsertPos) override;
629
630private:
631 std::vector<SDNode*> Sequence;
632 DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user
633
634 void ScheduleNode(SDNode *N);
635};
636} // end anonymous namespace
637
638void ScheduleDAGLinearize::ScheduleNode(SDNode *N) {
639 if (N->getNodeId() != 0)
640 llvm_unreachable(nullptr);
641
642 if (!N->isMachineOpcode() &&
643 (N->getOpcode() == ISD::EntryToken || isPassiveNode(Node: N)))
644 // These nodes do not need to be translated into MIs.
645 return;
646
647 LLVM_DEBUG(dbgs() << "\n*** Scheduling: ");
648 LLVM_DEBUG(N->dump(DAG));
649 Sequence.push_back(x: N);
650
651 unsigned NumOps = N->getNumOperands();
652 if (unsigned NumLeft = NumOps) {
653 SDNode *GluedOpN = nullptr;
654 do {
655 const SDValue &Op = N->getOperand(Num: NumLeft-1);
656 SDNode *OpN = Op.getNode();
657
658 if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) {
659 // Schedule glue operand right above N.
660 GluedOpN = OpN;
661 assert(OpN->getNodeId() != 0 && "Glue operand not ready?");
662 OpN->setNodeId(0);
663 ScheduleNode(N: OpN);
664 continue;
665 }
666
667 if (OpN == GluedOpN)
668 // Glue operand is already scheduled.
669 continue;
670
671 auto DI = GluedMap.find(Val: OpN);
672 if (DI != GluedMap.end() && DI->second != N)
673 // Users of glues are counted against the glued users.
674 OpN = DI->second;
675
676 unsigned Degree = OpN->getNodeId();
677 assert(Degree > 0 && "Predecessor over-released!");
678 OpN->setNodeId(--Degree);
679 if (Degree == 0)
680 ScheduleNode(N: OpN);
681 } while (--NumLeft);
682 }
683}
684
685/// findGluedUser - Find the representative use of a glue value by walking
686/// the use chain.
687static SDNode *findGluedUser(SDNode *N) {
688 while (SDNode *Glued = N->getGluedUser())
689 N = Glued;
690 return N;
691}
692
693void ScheduleDAGLinearize::Schedule() {
694 LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n");
695
696 SmallVector<SDNode*, 8> Glues;
697 unsigned DAGSize = 0;
698 for (SDNode &Node : DAG->allnodes()) {
699 SDNode *N = &Node;
700
701 // Use node id to record degree.
702 unsigned Degree = N->use_size();
703 N->setNodeId(Degree);
704 unsigned NumVals = N->getNumValues();
705 if (NumVals && N->getValueType(ResNo: NumVals-1) == MVT::Glue &&
706 N->hasAnyUseOfValue(Value: NumVals-1)) {
707 SDNode *User = findGluedUser(N);
708 if (User) {
709 Glues.push_back(Elt: N);
710 GluedMap.insert(KV: std::make_pair(x&: N, y&: User));
711 }
712 }
713
714 if (N->isMachineOpcode() ||
715 (N->getOpcode() != ISD::EntryToken && !isPassiveNode(Node: N)))
716 ++DAGSize;
717 }
718
719 for (SDNode *Glue : Glues) {
720 SDNode *GUser = GluedMap[Glue];
721 unsigned Degree = Glue->getNodeId();
722 unsigned UDegree = GUser->getNodeId();
723
724 // Glue user must be scheduled together with the glue operand. So other
725 // users of the glue operand must be treated as its users.
726 SDNode *ImmGUser = Glue->getGluedUser();
727 for (const SDNode *U : Glue->users())
728 if (U == ImmGUser)
729 --Degree;
730 GUser->setNodeId(UDegree + Degree);
731 Glue->setNodeId(1);
732 }
733
734 Sequence.reserve(n: DAGSize);
735 ScheduleNode(N: DAG->getRoot().getNode());
736}
737
738MachineBasicBlock*
739ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
740 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
741 InstrEmitter::VRBaseMapType VRBaseMap;
742
743 LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; });
744
745 unsigned NumNodes = Sequence.size();
746 MachineBasicBlock *BB = Emitter.getBlock();
747 for (unsigned i = 0; i != NumNodes; ++i) {
748 SDNode *N = Sequence[NumNodes-i-1];
749 LLVM_DEBUG(N->dump(DAG));
750 Emitter.EmitNode(Node: N, IsClone: false, IsCloned: false, VRBaseMap);
751
752 // Emit any debug values associated with the node.
753 if (N->getHasDebugValue()) {
754 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
755 for (auto *DV : DAG->GetDbgValues(SD: N)) {
756 if (!DV->isEmitted())
757 if (auto *DbgMI = Emitter.EmitDbgValue(SD: DV, VRBaseMap))
758 BB->insert(I: InsertPos, MI: DbgMI);
759 }
760 }
761 }
762
763 LLVM_DEBUG(dbgs() << '\n');
764
765 InsertPos = Emitter.getInsertPos();
766 return Emitter.getBlock();
767}
768
769//===----------------------------------------------------------------------===//
770// Public Constructor Functions
771//===----------------------------------------------------------------------===//
772
773llvm::ScheduleDAGSDNodes *llvm::createFastDAGScheduler(SelectionDAGISel *IS,
774 CodeGenOptLevel) {
775 return new ScheduleDAGFast(*IS->MF);
776}
777
778llvm::ScheduleDAGSDNodes *llvm::createDAGLinearizer(SelectionDAGISel *IS,
779 CodeGenOptLevel) {
780 return new ScheduleDAGLinearize(*IS->MF);
781}
782