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