LLVM  15.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"
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "pre-RA-sched"
29 
30 STATISTIC(NumUnfolds, "Number of nodes unfolded");
31 STATISTIC(NumDups, "Number of duplicated nodes");
32 STATISTIC(NumPRCopies, "Number of physical copies");
33 
34 static RegisterScheduler
35  fastDAGScheduler("fast", "Fast suboptimal list scheduling",
37 static RegisterScheduler
38  linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling",
40 
41 
42 namespace {
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 ///
64 class ScheduleDAGFast : public ScheduleDAGSDNodes {
65 private:
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;
73  std::vector<SUnit*> LiveRegDefs;
74  std::vector<unsigned> LiveRegCycles;
75 
76 public:
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 
94 private:
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.
113 void 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.
135 void 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 
156 void 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.
177 void 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.
206 SUnit *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) {
230  SmallVector<SDNode*, 2> NewNodes;
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.
376 void 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?
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.ImplicitDefs && "Physical reg def must be in implicit def list!");
430  NumRes = MCID.getNumDefs();
431  for (const MCPhysReg *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) {
432  if (Reg == *ImpDef)
433  break;
434  ++NumRes;
435  }
436  }
437  return N->getSimpleValueType(NumRes);
438 }
439 
440 /// CheckForLiveRegDef - Return true and update live register vector if the
441 /// specified register def of the specified SUnit clobbers any "live" registers.
442 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
443  std::vector<SUnit *> &LiveRegDefs,
444  SmallSet<unsigned, 4> &RegAdded,
446  const TargetRegisterInfo *TRI,
447  const SDNode *Node = nullptr) {
448  bool Added = false;
449  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
450  // Check if Ref is live.
451  if (!LiveRegDefs[*AI])
452  continue;
453 
454  // Allow multiple uses of the same def.
455  if (LiveRegDefs[*AI] == SU)
456  continue;
457 
458  // Allow multiple uses of same def
459  if (Node && LiveRegDefs[*AI]->getNode() == Node)
460  continue;
461 
462  // Add Reg to the set of interfering live regs.
463  if (RegAdded.insert(*AI).second) {
464  LRegs.push_back(*AI);
465  Added = true;
466  }
467  }
468  return Added;
469 }
470 
471 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
472 /// scheduling of the given node to satisfy live physical register dependencies.
473 /// If the specific node is the last one that's available to schedule, do
474 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
475 bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU,
477  if (NumLiveRegs == 0)
478  return false;
479 
480  SmallSet<unsigned, 4> RegAdded;
481  // If this node would clobber any "live" register, then it's not ready.
482  for (SDep &Pred : SU->Preds) {
483  if (Pred.isAssignedRegDep()) {
484  CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs,
485  RegAdded, LRegs, TRI);
486  }
487  }
488 
489  for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
490  if (Node->getOpcode() == ISD::INLINEASM ||
491  Node->getOpcode() == ISD::INLINEASM_BR) {
492  // Inline asm can clobber physical defs.
493  unsigned NumOps = Node->getNumOperands();
494  if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
495  --NumOps; // Ignore the glue operand.
496 
497  for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
498  unsigned Flags =
499  cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
500  unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
501 
502  ++i; // Skip the ID value.
503  if (InlineAsm::isRegDefKind(Flags) ||
505  InlineAsm::isClobberKind(Flags)) {
506  // Check for def of register or earlyclobber register.
507  for (; NumVals; --NumVals, ++i) {
508  unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
510  CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
511  }
512  } else
513  i += NumVals;
514  }
515  continue;
516  }
517 
518  if (Node->getOpcode() == ISD::CopyToReg) {
519  Register Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
520  if (Reg.isPhysical()) {
521  SDNode *SrcNode = Node->getOperand(2).getNode();
522  CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI, SrcNode);
523  }
524  }
525 
526  if (!Node->isMachineOpcode())
527  continue;
528  const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
529  if (!MCID.ImplicitDefs)
530  continue;
531  for (const MCPhysReg *Reg = MCID.getImplicitDefs(); *Reg; ++Reg) {
532  CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
533  }
534  }
535  return !LRegs.empty();
536 }
537 
538 
539 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
540 /// schedulers.
541 void ScheduleDAGFast::ListScheduleBottomUp() {
542  unsigned CurCycle = 0;
543 
544  // Release any predecessors of the special Exit node.
545  ReleasePredecessors(&ExitSU, CurCycle);
546 
547  // Add root to Available queue.
548  if (!SUnits.empty()) {
549  SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
550  assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
551  RootSU->isAvailable = true;
552  AvailableQueue.push(RootSU);
553  }
554 
555  // While Available queue is not empty, grab the node with the highest
556  // priority. If it is not ready put it back. Schedule the node.
557  SmallVector<SUnit*, 4> NotReady;
559  Sequence.reserve(SUnits.size());
560  while (!AvailableQueue.empty()) {
561  bool Delayed = false;
562  LRegsMap.clear();
563  SUnit *CurSU = AvailableQueue.pop();
564  while (CurSU) {
566  if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
567  break;
568  Delayed = true;
569  LRegsMap.insert(std::make_pair(CurSU, LRegs));
570 
571  CurSU->isPending = true; // This SU is not in AvailableQueue right now.
572  NotReady.push_back(CurSU);
573  CurSU = AvailableQueue.pop();
574  }
575 
576  // All candidates are delayed due to live physical reg dependencies.
577  // Try code duplication or inserting cross class copies
578  // to resolve it.
579  if (Delayed && !CurSU) {
580  if (!CurSU) {
581  // Try duplicating the nodes that produces these
582  // "expensive to copy" values to break the dependency. In case even
583  // that doesn't work, insert cross class copies.
584  SUnit *TrySU = NotReady[0];
585  SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
586  assert(LRegs.size() == 1 && "Can't handle this yet!");
587  unsigned Reg = LRegs[0];
588  SUnit *LRDef = LiveRegDefs[Reg];
589  MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
590  const TargetRegisterClass *RC =
592  const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
593 
594  // If cross copy register class is the same as RC, then it must be
595  // possible copy the value directly. Do not try duplicate the def.
596  // If cross copy register class is not the same as RC, then it's
597  // possible to copy the value but it require cross register class copies
598  // and it is expensive.
599  // If cross copy register class is null, then it's not possible to copy
600  // the value at all.
601  SUnit *NewDef = nullptr;
602  if (DestRC != RC) {
603  NewDef = CopyAndMoveSuccessors(LRDef);
604  if (!DestRC && !NewDef)
605  report_fatal_error("Can't handle live physical "
606  "register dependency!");
607  }
608  if (!NewDef) {
609  // Issue copies, these can be expensive cross register class copies.
611  InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
612  LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum
613  << " to SU #" << Copies.front()->NodeNum << "\n");
614  AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
615  NewDef = Copies.back();
616  }
617 
618  LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum
619  << " to SU #" << TrySU->NodeNum << "\n");
620  LiveRegDefs[Reg] = NewDef;
621  AddPred(NewDef, SDep(TrySU, SDep::Artificial));
622  TrySU->isAvailable = false;
623  CurSU = NewDef;
624  }
625 
626  if (!CurSU) {
627  llvm_unreachable("Unable to resolve live physical register dependencies!");
628  }
629  }
630 
631  // Add the nodes that aren't ready back onto the available list.
632  for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
633  NotReady[i]->isPending = false;
634  // May no longer be available due to backtracking.
635  if (NotReady[i]->isAvailable)
636  AvailableQueue.push(NotReady[i]);
637  }
638  NotReady.clear();
639 
640  if (CurSU)
641  ScheduleNodeBottomUp(CurSU, CurCycle);
642  ++CurCycle;
643  }
644 
645  // Reverse the order since it is bottom up.
646  std::reverse(Sequence.begin(), Sequence.end());
647 
648 #ifndef NDEBUG
649  VerifyScheduledSequence(/*isBottomUp=*/true);
650 #endif
651 }
652 
653 
654 namespace {
655 //===----------------------------------------------------------------------===//
656 // ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the
657 // DAG in topological order.
658 // IMPORTANT: this may not work for targets with phyreg dependency.
659 //
660 class ScheduleDAGLinearize : public ScheduleDAGSDNodes {
661 public:
662  ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {}
663 
664  void Schedule() override;
665 
667  EmitSchedule(MachineBasicBlock::iterator &InsertPos) override;
668 
669 private:
670  std::vector<SDNode*> Sequence;
671  DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user
672 
673  void ScheduleNode(SDNode *N);
674 };
675 } // end anonymous namespace
676 
677 void ScheduleDAGLinearize::ScheduleNode(SDNode *N) {
678  if (N->getNodeId() != 0)
679  llvm_unreachable(nullptr);
680 
681  if (!N->isMachineOpcode() &&
682  (N->getOpcode() == ISD::EntryToken || isPassiveNode(N)))
683  // These nodes do not need to be translated into MIs.
684  return;
685 
686  LLVM_DEBUG(dbgs() << "\n*** Scheduling: ");
687  LLVM_DEBUG(N->dump(DAG));
688  Sequence.push_back(N);
689 
690  unsigned NumOps = N->getNumOperands();
691  if (unsigned NumLeft = NumOps) {
692  SDNode *GluedOpN = nullptr;
693  do {
694  const SDValue &Op = N->getOperand(NumLeft-1);
695  SDNode *OpN = Op.getNode();
696 
697  if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) {
698  // Schedule glue operand right above N.
699  GluedOpN = OpN;
700  assert(OpN->getNodeId() != 0 && "Glue operand not ready?");
701  OpN->setNodeId(0);
702  ScheduleNode(OpN);
703  continue;
704  }
705 
706  if (OpN == GluedOpN)
707  // Glue operand is already scheduled.
708  continue;
709 
710  DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN);
711  if (DI != GluedMap.end() && DI->second != N)
712  // Users of glues are counted against the glued users.
713  OpN = DI->second;
714 
715  unsigned Degree = OpN->getNodeId();
716  assert(Degree > 0 && "Predecessor over-released!");
717  OpN->setNodeId(--Degree);
718  if (Degree == 0)
719  ScheduleNode(OpN);
720  } while (--NumLeft);
721  }
722 }
723 
724 /// findGluedUser - Find the representative use of a glue value by walking
725 /// the use chain.
727  while (SDNode *Glued = N->getGluedUser())
728  N = Glued;
729  return N;
730 }
731 
732 void ScheduleDAGLinearize::Schedule() {
733  LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n");
734 
736  unsigned DAGSize = 0;
737  for (SDNode &Node : DAG->allnodes()) {
738  SDNode *N = &Node;
739 
740  // Use node id to record degree.
741  unsigned Degree = N->use_size();
742  N->setNodeId(Degree);
743  unsigned NumVals = N->getNumValues();
744  if (NumVals && N->getValueType(NumVals-1) == MVT::Glue &&
745  N->hasAnyUseOfValue(NumVals-1)) {
747  if (User) {
748  Glues.push_back(N);
749  GluedMap.insert(std::make_pair(N, User));
750  }
751  }
752 
753  if (N->isMachineOpcode() ||
754  (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N)))
755  ++DAGSize;
756  }
757 
758  for (unsigned i = 0, e = Glues.size(); i != e; ++i) {
759  SDNode *Glue = Glues[i];
760  SDNode *GUser = GluedMap[Glue];
761  unsigned Degree = Glue->getNodeId();
762  unsigned UDegree = GUser->getNodeId();
763 
764  // Glue user must be scheduled together with the glue operand. So other
765  // users of the glue operand must be treated as its users.
766  SDNode *ImmGUser = Glue->getGluedUser();
767  for (const SDNode *U : Glue->uses())
768  if (U == ImmGUser)
769  --Degree;
770  GUser->setNodeId(UDegree + Degree);
771  Glue->setNodeId(1);
772  }
773 
774  Sequence.reserve(DAGSize);
775  ScheduleNode(DAG->getRoot().getNode());
776 }
777 
779 ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
780  InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos,
781  DAG->getUseInstrRefDebugInfo());
782  DenseMap<SDValue, Register> VRBaseMap;
783 
784  LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; });
785 
786  unsigned NumNodes = Sequence.size();
787  MachineBasicBlock *BB = Emitter.getBlock();
788  for (unsigned i = 0; i != NumNodes; ++i) {
789  SDNode *N = Sequence[NumNodes-i-1];
790  LLVM_DEBUG(N->dump(DAG));
791  Emitter.EmitNode(N, false, false, VRBaseMap);
792 
793  // Emit any debug values associated with the node.
794  if (N->getHasDebugValue()) {
795  MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
796  for (auto DV : DAG->GetDbgValues(N)) {
797  if (!DV->isEmitted())
798  if (auto *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap))
799  BB->insert(InsertPos, DbgMI);
800  }
801  }
802  }
803 
804  LLVM_DEBUG(dbgs() << '\n');
805 
806  InsertPos = Emitter.getInsertPos();
807  return Emitter.getBlock();
808 }
809 
810 //===----------------------------------------------------------------------===//
811 // Public Constructor Functions
812 //===----------------------------------------------------------------------===//
813 
816  return new ScheduleDAGFast(*IS->MF);
817 }
818 
821  return new ScheduleDAGLinearize(*IS->MF);
822 }
i
i
Definition: README.txt:29
llvm::MCInstrDesc::getNumDefs
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:245
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:820
CheckForLiveRegDef
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...
Definition: ScheduleDAGFast.cpp:442
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:779
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::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
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::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
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:24
llvm::createFastDAGScheduler
ScheduleDAGSDNodes * createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createFastDAGScheduler - This creates a "fast" scheduler.
Definition: ScheduleDAGFast.cpp:815
llvm::SDNode
Represents one node in the SelectionDAG.
Definition: SelectionDAGNodes.h:454
llvm::MVT::Glue
@ Glue
Definition: MachineValueType.h:270
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
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:136
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:877
SDNodeDbgValue.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
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:1025
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::ISD::CopyToReg
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
Definition: ISDOpcodes.h:203
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:45
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:587
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
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:478
llvm::SDNode::uses
iterator_range< use_iterator > uses()
Definition: SelectionDAGNodes.h:793
llvm::InlineAsm::isRegDefKind
static bool isRegDefKind(unsigned Flag)
Definition: InlineAsm.h:294
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:143
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:94
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:952
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:726
llvm::InlineAsm::isRegDefEarlyClobberKind
static bool isRegDefEarlyClobberKind(unsigned Flag)
Definition: InlineAsm.h:297
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:112
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:716
llvm::DenseMap
Definition: DenseMap.h:716
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:152
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:713
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:257
SelectionDAGISel.h
llvm::SDep::getSUnit
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::SDNode::isOperandOf
bool isOperandOf(const SDNode *N) const
Return true if this node is an operand of N.
Definition: SelectionDAG.cpp:10819
llvm::InlineAsm::isClobberKind
static bool isClobberKind(unsigned Flag)
Definition: InlineAsm.h:300
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:182
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:209
llvm::SDep::isAssignedRegDep
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
llvm::SelectionDAGISel::MF
MachineFunction * MF
Definition: SelectionDAGISel.h:46
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:268
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
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:1028
llvm::SDValue
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
Definition: SelectionDAGNodes.h:137
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:967
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::SUnit::isTwoAddress
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:277
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:813
llvm::SelectionDAGISel
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
Definition: SelectionDAGISel.h:40
llvm::InlineAsm::getNumOperandRegisters
static unsigned getNumOperandRegisters(unsigned Flag)
getNumOperandRegisters - Extract the number of registers field from the inline asm operand flag.
Definition: InlineAsm.h:355
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:42
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:35
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:212
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:421
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:212
llvm::InlineAsm::Op_FirstOperand
@ Op_FirstOperand
Definition: InlineAsm.h:220
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:230
TargetRegisterInfo.h
Debug.h
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788
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:943
llvm::MCInstrDesc::ImplicitDefs
const MCPhysReg * ImplicitDefs
Definition: MCInstrDesc.h:207
SmallSet.h
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:792