LLVM 18.0.0git
ScheduleDAGFast.cpp
Go to the documentation of this file.
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"
22#include "llvm/IR/InlineAsm.h"
23#include "llvm/Support/Debug.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
35 fastDAGScheduler("fast", "Fast suboptimal list scheduling",
38 linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling",
40
41
42namespace {
43 /// FastPriorityQueue - A degenerate priority queue that considers
44 /// all nodes to have the same priority.
45 ///
46 struct FastPriorityQueue {
48
49 bool empty() const { return Queue.empty(); }
50
51 void push(SUnit *U) {
52 Queue.push_back(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 /// This returns true if this is a new predecessor.
84 void AddPred(SUnit *SU, const SDep &D) {
85 SU->addPred(D);
86 }
87
88 /// RemovePred - removes a predecessor edge from SUnit SU.
89 /// This returns true if an edge was removed.
90 void RemovePred(SUnit *SU, const SDep &D) {
91 SU->removePred(D);
92 }
93
94private:
95 void ReleasePred(SUnit *SU, SDep *PredEdge);
96 void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
97 void ScheduleNodeBottomUp(SUnit*, unsigned);
98 SUnit *CopyAndMoveSuccessors(SUnit*);
99 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
100 const TargetRegisterClass*,
101 const TargetRegisterClass*,
103 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
104 void ListScheduleBottomUp();
105
106 /// forceUnitLatencies - The fast scheduler doesn't care about real latencies.
107 bool forceUnitLatencies() const override { return true; }
108};
109} // end anonymous namespace
110
111
112/// Schedule - Schedule the DAG using list scheduling.
113void ScheduleDAGFast::Schedule() {
114 LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");
115
116 NumLiveRegs = 0;
117 LiveRegDefs.resize(TRI->getNumRegs(), nullptr);
118 LiveRegCycles.resize(TRI->getNumRegs(), 0);
119
120 // Build the scheduling graph.
121 BuildSchedGraph(nullptr);
122
123 LLVM_DEBUG(dump());
124
125 // Execute the actual scheduling loop.
126 ListScheduleBottomUp();
127}
128
129//===----------------------------------------------------------------------===//
130// Bottom-Up Scheduling
131//===----------------------------------------------------------------------===//
132
133/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
134/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
135void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) {
136 SUnit *PredSU = PredEdge->getSUnit();
137
138#ifndef NDEBUG
139 if (PredSU->NumSuccsLeft == 0) {
140 dbgs() << "*** Scheduling failed! ***\n";
141 dumpNode(*PredSU);
142 dbgs() << " has been released too many times!\n";
143 llvm_unreachable(nullptr);
144 }
145#endif
146 --PredSU->NumSuccsLeft;
147
148 // If all the node's successors are scheduled, this node is ready
149 // to be scheduled. Ignore the special EntrySU node.
150 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
151 PredSU->isAvailable = true;
152 AvailableQueue.push(PredSU);
153 }
154}
155
156void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
157 // Bottom up: release predecessors
158 for (SDep &Pred : SU->Preds) {
159 ReleasePred(SU, &Pred);
160 if (Pred.isAssignedRegDep()) {
161 // This is a physical register dependency and it's impossible or
162 // expensive to copy the register. Make sure nothing that can
163 // clobber the register is scheduled between the predecessor and
164 // this node.
165 if (!LiveRegDefs[Pred.getReg()]) {
166 ++NumLiveRegs;
167 LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
168 LiveRegCycles[Pred.getReg()] = CurCycle;
169 }
170 }
171 }
172}
173
174/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
175/// count of its predecessors. If a predecessor pending count is zero, add it to
176/// the Available queue.
177void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
178 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
179 LLVM_DEBUG(dumpNode(*SU));
180
181 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
182 SU->setHeightToAtLeast(CurCycle);
183 Sequence.push_back(SU);
184
185 ReleasePredecessors(SU, CurCycle);
186
187 // Release all the implicit physical register defs that are live.
188 for (SDep &Succ : SU->Succs) {
189 if (Succ.isAssignedRegDep()) {
190 if (LiveRegCycles[Succ.getReg()] == Succ.getSUnit()->getHeight()) {
191 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
192 assert(LiveRegDefs[Succ.getReg()] == SU &&
193 "Physical register dependency violated?");
194 --NumLiveRegs;
195 LiveRegDefs[Succ.getReg()] = nullptr;
196 LiveRegCycles[Succ.getReg()] = 0;
197 }
198 }
199 }
200
201 SU->isScheduled = true;
202}
203
204/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
205/// successors to the newly created node.
206SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) {
207 if (SU->getNode()->getGluedNode())
208 return nullptr;
209
210 SDNode *N = SU->getNode();
211 if (!N)
212 return nullptr;
213
214 SUnit *NewSU;
215 bool TryUnfold = false;
216 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
217 MVT VT = N->getSimpleValueType(i);
218 if (VT == MVT::Glue)
219 return nullptr;
220 else if (VT == MVT::Other)
221 TryUnfold = true;
222 }
223 for (const SDValue &Op : N->op_values()) {
224 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
225 if (VT == MVT::Glue)
226 return nullptr;
227 }
228
229 if (TryUnfold) {
231 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
232 return nullptr;
233
234 LLVM_DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n");
235 assert(NewNodes.size() == 2 && "Expected a load folding node!");
236
237 N = NewNodes[1];
238 SDNode *LoadNode = NewNodes[0];
239 unsigned NumVals = N->getNumValues();
240 unsigned OldNumVals = SU->getNode()->getNumValues();
241 for (unsigned i = 0; i != NumVals; ++i)
242 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
243 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
244 SDValue(LoadNode, 1));
245
246 SUnit *NewSU = newSUnit(N);
247 assert(N->getNodeId() == -1 && "Node already inserted!");
248 N->setNodeId(NewSU->NodeNum);
249
250 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
251 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
252 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
253 NewSU->isTwoAddress = true;
254 break;
255 }
256 }
257 if (MCID.isCommutable())
258 NewSU->isCommutable = true;
259
260 // LoadNode may already exist. This can happen when there is another
261 // load from the same location and producing the same type of value
262 // but it has different alignment or volatileness.
263 bool isNewLoad = true;
264 SUnit *LoadSU;
265 if (LoadNode->getNodeId() != -1) {
266 LoadSU = &SUnits[LoadNode->getNodeId()];
267 isNewLoad = false;
268 } else {
269 LoadSU = newSUnit(LoadNode);
270 LoadNode->setNodeId(LoadSU->NodeNum);
271 }
272
273 SDep ChainPred;
274 SmallVector<SDep, 4> ChainSuccs;
275 SmallVector<SDep, 4> LoadPreds;
276 SmallVector<SDep, 4> NodePreds;
277 SmallVector<SDep, 4> NodeSuccs;
278 for (SDep &Pred : SU->Preds) {
279 if (Pred.isCtrl())
280 ChainPred = Pred;
281 else if (Pred.getSUnit()->getNode() &&
282 Pred.getSUnit()->getNode()->isOperandOf(LoadNode))
283 LoadPreds.push_back(Pred);
284 else
285 NodePreds.push_back(Pred);
286 }
287 for (SDep &Succ : SU->Succs) {
288 if (Succ.isCtrl())
289 ChainSuccs.push_back(Succ);
290 else
291 NodeSuccs.push_back(Succ);
292 }
293
294 if (ChainPred.getSUnit()) {
295 RemovePred(SU, ChainPred);
296 if (isNewLoad)
297 AddPred(LoadSU, ChainPred);
298 }
299 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
300 const SDep &Pred = LoadPreds[i];
301 RemovePred(SU, Pred);
302 if (isNewLoad) {
303 AddPred(LoadSU, Pred);
304 }
305 }
306 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
307 const SDep &Pred = NodePreds[i];
308 RemovePred(SU, Pred);
309 AddPred(NewSU, Pred);
310 }
311 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
312 SDep D = NodeSuccs[i];
313 SUnit *SuccDep = D.getSUnit();
314 D.setSUnit(SU);
315 RemovePred(SuccDep, D);
316 D.setSUnit(NewSU);
317 AddPred(SuccDep, D);
318 }
319 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
320 SDep D = ChainSuccs[i];
321 SUnit *SuccDep = D.getSUnit();
322 D.setSUnit(SU);
323 RemovePred(SuccDep, D);
324 if (isNewLoad) {
325 D.setSUnit(LoadSU);
326 AddPred(SuccDep, D);
327 }
328 }
329 if (isNewLoad) {
330 SDep D(LoadSU, SDep::Barrier);
331 D.setLatency(LoadSU->Latency);
332 AddPred(NewSU, D);
333 }
334
335 ++NumUnfolds;
336
337 if (NewSU->NumSuccsLeft == 0) {
338 NewSU->isAvailable = true;
339 return NewSU;
340 }
341 SU = NewSU;
342 }
343
344 LLVM_DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n");
345 NewSU = Clone(SU);
346
347 // New SUnit has the exact same predecessors.
348 for (SDep &Pred : SU->Preds)
349 if (!Pred.isArtificial())
350 AddPred(NewSU, Pred);
351
352 // Only copy scheduled successors. Cut them from old node's successor
353 // list and move them over.
355 for (SDep &Succ : SU->Succs) {
356 if (Succ.isArtificial())
357 continue;
358 SUnit *SuccSU = Succ.getSUnit();
359 if (SuccSU->isScheduled) {
360 SDep D = Succ;
361 D.setSUnit(NewSU);
362 AddPred(SuccSU, D);
363 D.setSUnit(SU);
364 DelDeps.push_back(std::make_pair(SuccSU, D));
365 }
366 }
367 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
368 RemovePred(DelDeps[i].first, DelDeps[i].second);
369
370 ++NumDups;
371 return NewSU;
372}
373
374/// InsertCopiesAndMoveSuccs - Insert register copies and move all
375/// scheduled successors of the given SUnit to the last copy.
376void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
377 const TargetRegisterClass *DestRC,
378 const TargetRegisterClass *SrcRC,
380 SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(nullptr));
381 CopyFromSU->CopySrcRC = SrcRC;
382 CopyFromSU->CopyDstRC = DestRC;
383
384 SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(nullptr));
385 CopyToSU->CopySrcRC = DestRC;
386 CopyToSU->CopyDstRC = SrcRC;
387
388 // Only copy scheduled successors. Cut them from old node's successor
389 // list and move them over.
391 for (SDep &Succ : SU->Succs) {
392 if (Succ.isArtificial())
393 continue;
394 SUnit *SuccSU = Succ.getSUnit();
395 if (SuccSU->isScheduled) {
396 SDep D = Succ;
397 D.setSUnit(CopyToSU);
398 AddPred(SuccSU, D);
399 DelDeps.push_back(std::make_pair(SuccSU, Succ));
400 }
401 }
402 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
403 RemovePred(DelDeps[i].first, DelDeps[i].second);
404 }
405 SDep FromDep(SU, SDep::Data, Reg);
406 FromDep.setLatency(SU->Latency);
407 AddPred(CopyFromSU, FromDep);
408 SDep ToDep(CopyFromSU, SDep::Data, 0);
409 ToDep.setLatency(CopyFromSU->Latency);
410 AddPred(CopyToSU, ToDep);
411
412 Copies.push_back(CopyFromSU);
413 Copies.push_back(CopyToSU);
414
415 ++NumPRCopies;
416}
417
418/// getPhysicalRegisterVT - Returns the ValueType of the physical register
419/// definition of the specified node.
420/// FIXME: Move to SelectionDAG?
421static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
422 const TargetInstrInfo *TII) {
423 unsigned NumRes;
424 if (N->getOpcode() == ISD::CopyFromReg) {
425 // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
426 NumRes = 1;
427 } else {
428 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
429 assert(!MCID.implicit_defs().empty() &&
430 "Physical reg def must be in implicit def list!");
431 NumRes = MCID.getNumDefs();
432 for (MCPhysReg ImpDef : MCID.implicit_defs()) {
433 if (Reg == ImpDef)
434 break;
435 ++NumRes;
436 }
437 }
438 return N->getSimpleValueType(NumRes);
439}
440
441/// CheckForLiveRegDef - Return true and update live register vector if the
442/// specified register def of the specified SUnit clobbers any "live" registers.
443static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
444 std::vector<SUnit *> &LiveRegDefs,
445 SmallSet<unsigned, 4> &RegAdded,
447 const TargetRegisterInfo *TRI,
448 const SDNode *Node = nullptr) {
449 bool Added = false;
450 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
451 // Check if Ref is live.
452 if (!LiveRegDefs[*AI])
453 continue;
454
455 // Allow multiple uses of the same def.
456 if (LiveRegDefs[*AI] == SU)
457 continue;
458
459 // Allow multiple uses of same def
460 if (Node && LiveRegDefs[*AI]->getNode() == Node)
461 continue;
462
463 // Add Reg to the set of interfering live regs.
464 if (RegAdded.insert(*AI).second) {
465 LRegs.push_back(*AI);
466 Added = true;
467 }
468 }
469 return Added;
470}
471
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.
476bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU,
478 if (NumLiveRegs == 0)
479 return false;
480
481 SmallSet<unsigned, 4> RegAdded;
482 // If this node would clobber any "live" register, then it's not ready.
483 for (SDep &Pred : SU->Preds) {
484 if (Pred.isAssignedRegDep()) {
485 CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs,
486 RegAdded, LRegs, TRI);
487 }
488 }
489
490 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
491 if (Node->getOpcode() == ISD::INLINEASM ||
492 Node->getOpcode() == ISD::INLINEASM_BR) {
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.
497
498 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
499 unsigned Flags =
500 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
501 const InlineAsm::Flag F(Flags);
502 unsigned NumVals = F.getNumOperandRegisters();
503
504 ++i; // Skip the ID value.
505 if (F.isRegDefKind() || F.isRegDefEarlyClobberKind() ||
506 F.isClobberKind()) {
507 // Check for def of register or earlyclobber register.
508 for (; NumVals; --NumVals, ++i) {
509 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
511 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
512 }
513 } else
514 i += NumVals;
515 }
516 continue;
517 }
518
519 if (Node->getOpcode() == ISD::CopyToReg) {
520 Register Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
521 if (Reg.isPhysical()) {
522 SDNode *SrcNode = Node->getOperand(2).getNode();
523 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI, SrcNode);
524 }
525 }
526
527 if (!Node->isMachineOpcode())
528 continue;
529 const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
530 for (MCPhysReg Reg : MCID.implicit_defs())
531 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
532 }
533 return !LRegs.empty();
534}
535
536
537/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
538/// schedulers.
539void ScheduleDAGFast::ListScheduleBottomUp() {
540 unsigned CurCycle = 0;
541
542 // Release any predecessors of the special Exit node.
543 ReleasePredecessors(&ExitSU, CurCycle);
544
545 // Add root to Available queue.
546 if (!SUnits.empty()) {
547 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
548 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
549 RootSU->isAvailable = true;
550 AvailableQueue.push(RootSU);
551 }
552
553 // While Available queue is not empty, grab the node with the highest
554 // priority. If it is not ready put it back. Schedule the node.
555 SmallVector<SUnit*, 4> NotReady;
557 Sequence.reserve(SUnits.size());
558 while (!AvailableQueue.empty()) {
559 bool Delayed = false;
560 LRegsMap.clear();
561 SUnit *CurSU = AvailableQueue.pop();
562 while (CurSU) {
564 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
565 break;
566 Delayed = true;
567 LRegsMap.insert(std::make_pair(CurSU, LRegs));
568
569 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
570 NotReady.push_back(CurSU);
571 CurSU = AvailableQueue.pop();
572 }
573
574 // All candidates are delayed due to live physical reg dependencies.
575 // Try code duplication or inserting cross class copies
576 // to resolve it.
577 if (Delayed && !CurSU) {
578 if (!CurSU) {
579 // Try duplicating the nodes that produces these
580 // "expensive to copy" values to break the dependency. In case even
581 // that doesn't work, insert cross class copies.
582 SUnit *TrySU = NotReady[0];
583 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
584 assert(LRegs.size() == 1 && "Can't handle this yet!");
585 unsigned Reg = LRegs[0];
586 SUnit *LRDef = LiveRegDefs[Reg];
587 MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
588 const TargetRegisterClass *RC =
589 TRI->getMinimalPhysRegClass(Reg, VT);
590 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
591
592 // If cross copy register class is the same as RC, then it must be
593 // possible copy the value directly. Do not try duplicate the def.
594 // If cross copy register class is not the same as RC, then it's
595 // possible to copy the value but it require cross register class copies
596 // and it is expensive.
597 // If cross copy register class is null, then it's not possible to copy
598 // the value at all.
599 SUnit *NewDef = nullptr;
600 if (DestRC != RC) {
601 NewDef = CopyAndMoveSuccessors(LRDef);
602 if (!DestRC && !NewDef)
603 report_fatal_error("Can't handle live physical "
604 "register dependency!");
605 }
606 if (!NewDef) {
607 // Issue copies, these can be expensive cross register class copies.
609 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
610 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum
611 << " to SU #" << Copies.front()->NodeNum << "\n");
612 AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
613 NewDef = Copies.back();
614 }
615
616 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum
617 << " to SU #" << TrySU->NodeNum << "\n");
618 LiveRegDefs[Reg] = NewDef;
619 AddPred(NewDef, SDep(TrySU, SDep::Artificial));
620 TrySU->isAvailable = false;
621 CurSU = NewDef;
622 }
623
624 if (!CurSU) {
625 llvm_unreachable("Unable to resolve live physical register dependencies!");
626 }
627 }
628
629 // Add the nodes that aren't ready back onto the available list.
630 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
631 NotReady[i]->isPending = false;
632 // May no longer be available due to backtracking.
633 if (NotReady[i]->isAvailable)
634 AvailableQueue.push(NotReady[i]);
635 }
636 NotReady.clear();
637
638 if (CurSU)
639 ScheduleNodeBottomUp(CurSU, CurCycle);
640 ++CurCycle;
641 }
642
643 // Reverse the order since it is bottom up.
644 std::reverse(Sequence.begin(), Sequence.end());
645
646#ifndef NDEBUG
647 VerifyScheduledSequence(/*isBottomUp=*/true);
648#endif
649}
650
651
652namespace {
653//===----------------------------------------------------------------------===//
654// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the
655// DAG in topological order.
656// IMPORTANT: this may not work for targets with phyreg dependency.
657//
658class ScheduleDAGLinearize : public ScheduleDAGSDNodes {
659public:
660 ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {}
661
662 void Schedule() override;
663
665 EmitSchedule(MachineBasicBlock::iterator &InsertPos) override;
666
667private:
668 std::vector<SDNode*> Sequence;
669 DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user
670
671 void ScheduleNode(SDNode *N);
672};
673} // end anonymous namespace
674
675void ScheduleDAGLinearize::ScheduleNode(SDNode *N) {
676 if (N->getNodeId() != 0)
677 llvm_unreachable(nullptr);
678
679 if (!N->isMachineOpcode() &&
680 (N->getOpcode() == ISD::EntryToken || isPassiveNode(N)))
681 // These nodes do not need to be translated into MIs.
682 return;
683
684 LLVM_DEBUG(dbgs() << "\n*** Scheduling: ");
685 LLVM_DEBUG(N->dump(DAG));
686 Sequence.push_back(N);
687
688 unsigned NumOps = N->getNumOperands();
689 if (unsigned NumLeft = NumOps) {
690 SDNode *GluedOpN = nullptr;
691 do {
692 const SDValue &Op = N->getOperand(NumLeft-1);
693 SDNode *OpN = Op.getNode();
694
695 if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) {
696 // Schedule glue operand right above N.
697 GluedOpN = OpN;
698 assert(OpN->getNodeId() != 0 && "Glue operand not ready?");
699 OpN->setNodeId(0);
700 ScheduleNode(OpN);
701 continue;
702 }
703
704 if (OpN == GluedOpN)
705 // Glue operand is already scheduled.
706 continue;
707
709 if (DI != GluedMap.end() && DI->second != N)
710 // Users of glues are counted against the glued users.
711 OpN = DI->second;
712
713 unsigned Degree = OpN->getNodeId();
714 assert(Degree > 0 && "Predecessor over-released!");
715 OpN->setNodeId(--Degree);
716 if (Degree == 0)
717 ScheduleNode(OpN);
718 } while (--NumLeft);
719 }
720}
721
722/// findGluedUser - Find the representative use of a glue value by walking
723/// the use chain.
725 while (SDNode *Glued = N->getGluedUser())
726 N = Glued;
727 return N;
728}
729
730void ScheduleDAGLinearize::Schedule() {
731 LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n");
732
734 unsigned DAGSize = 0;
735 for (SDNode &Node : DAG->allnodes()) {
736 SDNode *N = &Node;
737
738 // Use node id to record degree.
739 unsigned Degree = N->use_size();
740 N->setNodeId(Degree);
741 unsigned NumVals = N->getNumValues();
742 if (NumVals && N->getValueType(NumVals-1) == MVT::Glue &&
743 N->hasAnyUseOfValue(NumVals-1)) {
745 if (User) {
746 Glues.push_back(N);
747 GluedMap.insert(std::make_pair(N, User));
748 }
749 }
750
751 if (N->isMachineOpcode() ||
752 (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N)))
753 ++DAGSize;
754 }
755
756 for (unsigned i = 0, e = Glues.size(); i != e; ++i) {
757 SDNode *Glue = Glues[i];
758 SDNode *GUser = GluedMap[Glue];
759 unsigned Degree = Glue->getNodeId();
760 unsigned UDegree = GUser->getNodeId();
761
762 // Glue user must be scheduled together with the glue operand. So other
763 // users of the glue operand must be treated as its users.
764 SDNode *ImmGUser = Glue->getGluedUser();
765 for (const SDNode *U : Glue->uses())
766 if (U == ImmGUser)
767 --Degree;
768 GUser->setNodeId(UDegree + Degree);
769 Glue->setNodeId(1);
770 }
771
772 Sequence.reserve(DAGSize);
773 ScheduleNode(DAG->getRoot().getNode());
774}
775
777ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
778 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
780
781 LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; });
782
783 unsigned NumNodes = Sequence.size();
784 MachineBasicBlock *BB = Emitter.getBlock();
785 for (unsigned i = 0; i != NumNodes; ++i) {
786 SDNode *N = Sequence[NumNodes-i-1];
787 LLVM_DEBUG(N->dump(DAG));
788 Emitter.EmitNode(N, false, false, VRBaseMap);
789
790 // Emit any debug values associated with the node.
791 if (N->getHasDebugValue()) {
792 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
793 for (auto *DV : DAG->GetDbgValues(N)) {
794 if (!DV->isEmitted())
795 if (auto *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap))
796 BB->insert(InsertPos, DbgMI);
797 }
798 }
799 }
800
801 LLVM_DEBUG(dbgs() << '\n');
802
803 InsertPos = Emitter.getInsertPos();
804 return Emitter.getBlock();
805}
806
807//===----------------------------------------------------------------------===//
808// Public Constructor Functions
809//===----------------------------------------------------------------------===//
810
813 return new ScheduleDAGFast(*IS->MF);
814}
815
818 return new ScheduleDAGLinearize(*IS->MF);
819}
static void push(SmallVectorImpl< uint64_t > &R, StringRef Str)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
dxil DXContainer Global Emitter
#define LLVM_DEBUG(X)
Definition: Debug.h:101
const HexagonInstrInfo * TII
#define F(x, y, z)
Definition: MD5.cpp:55
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI Lower i1 Copies
static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, const TargetInstrInfo *TII)
getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified no...
static RegisterScheduler fastDAGScheduler("fast", "Fast suboptimal list scheduling", createFastDAGScheduler)
static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, std::vector< SUnit * > &LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI, const SDNode *Node=nullptr)
CheckForLiveRegDef - Return true and update live register vector if the specified register def of the...
static RegisterScheduler linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", createDAGLinearizer)
static SDNode * findGluedUser(SDNode *N)
findGluedUser - Find the representative use of a glue value by walking the use chain.
This file defines the SmallSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:237
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:248
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specified operand constraint if it is present.
Definition: MCInstrDesc.h:219
ArrayRef< MCPhysReg > implicit_defs() const
Return a list of registers that are potentially written by any instance of this machine instruction.
Definition: MCInstrDesc.h:579
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
Definition: MCInstrDesc.h:481
MCRegAliasIterator enumerates all registers aliasing Reg.
Machine Value Type.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
Represents one node in the SelectionDAG.
int getNodeId() const
Return the unique node id.
SDNode * getGluedUser() const
If this node has a glue value with a user, return the user (there is at most one).
iterator_range< use_iterator > uses()
void setNodeId(int Id)
Set unique node id.
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
bool isOperandOf(const SDNode *N) const
Return true if this node is an operand of N.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
Scheduling dependency.
Definition: ScheduleDAG.h:49
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
@ Barrier
An unknown scheduling barrier.
Definition: ScheduleDAG.h:69
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Definition: ScheduleDAG.h:72
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Definition: ScheduleDAG.h:200
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
unsigned getReg() const
Returns the register associated with this edge.
Definition: ScheduleDAG.h:218
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
unsigned NumSuccsLeft
Definition: ScheduleDAG.h:269
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
Definition: ScheduleDAG.h:302
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
Definition: ScheduleDAG.h:406
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
bool isPending
True once pending.
Definition: ScheduleDAG.h:282
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
bool isAvailable
True once available.
Definition: ScheduleDAG.h:283
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
const TargetRegisterClass * CopySrcRC
Definition: ScheduleDAG.h:304
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:355
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:277
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:278
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
virtual MachineBasicBlock * EmitSchedule(MachineBasicBlock::iterator &InsertPos)
EmitSchedule - Insert MachineInstrs into the MachineBasicBlock according to the order specified in Se...
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one.
std::vector< SUnit * > Sequence
The schedule. Null SUnit*'s represent noop instructions.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
MachineFunction * MF
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
Definition: ISDOpcodes.h:208
@ EntryToken
EntryToken - This is the marker used to indicate the start of a region.
Definition: ISDOpcodes.h:47
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
Definition: ISDOpcodes.h:203
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Definition: ISDOpcodes.h:1092
@ INLINEASM
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:1089
Reg
All possible values of the reg field in the ModR/M byte.
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:41
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
ScheduleDAGSDNodes * createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createFastDAGScheduler - This creates a "fast" scheduler.
ScheduleDAGSDNodes * createDAGLinearizer(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createDAGLinearizer - This creates a "no-scheduling" scheduler which linearize the DAG using topologi...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:156
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
#define N