LLVM  9.0.0svn
ScheduleDAGSDNodes.cpp
Go to the documentation of this file.
1 //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
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 the ScheduleDAG class, which is a base class used by
10 // scheduling implementation classes.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "ScheduleDAGSDNodes.h"
15 #include "InstrEmitter.h"
16 #include "SDNodeDbgValue.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
29 #include "llvm/Config/llvm-config.h"
32 #include "llvm/Support/Debug.h"
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "pre-RA-sched"
37 
38 STATISTIC(LoadsClustered, "Number of loads clustered together");
39 
40 // This allows the latency-based scheduler to notice high latency instructions
41 // without a target itinerary. The choice of number here has more to do with
42 // balancing scheduler heuristics than with the actual machine latency.
44  "sched-high-latency-cycles", cl::Hidden, cl::init(10),
45  cl::desc("Roughly estimate the number of cycles that 'long latency'"
46  "instructions take for targets with no itinerary"));
47 
49  : ScheduleDAG(mf), BB(nullptr), DAG(nullptr),
50  InstrItins(mf.getSubtarget().getInstrItineraryData()) {}
51 
52 /// Run - perform scheduling.
53 ///
55  BB = bb;
56  DAG = dag;
57 
58  // Clear the scheduler's SUnit DAG.
60  Sequence.clear();
61 
62  // Invoke the target's selection of scheduler.
63  Schedule();
64 }
65 
66 /// NewSUnit - Creates a new SUnit and return a ptr to it.
67 ///
69 #ifndef NDEBUG
70  const SUnit *Addr = nullptr;
71  if (!SUnits.empty())
72  Addr = &SUnits[0];
73 #endif
74  SUnits.emplace_back(N, (unsigned)SUnits.size());
75  assert((Addr == nullptr || Addr == &SUnits[0]) &&
76  "SUnits std::vector reallocated on the fly!");
77  SUnits.back().OrigNode = &SUnits.back();
78  SUnit *SU = &SUnits.back();
80  if (!N ||
81  (N->isMachineOpcode() &&
82  N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF))
84  else
86  return SU;
87 }
88 
90  SUnit *SU = newSUnit(Old->getNode());
91  SU->OrigNode = Old->OrigNode;
92  SU->Latency = Old->Latency;
93  SU->isVRegCycle = Old->isVRegCycle;
94  SU->isCall = Old->isCall;
95  SU->isCallOp = Old->isCallOp;
96  SU->isTwoAddress = Old->isTwoAddress;
97  SU->isCommutable = Old->isCommutable;
98  SU->hasPhysRegDefs = Old->hasPhysRegDefs;
100  SU->isScheduleHigh = Old->isScheduleHigh;
101  SU->isScheduleLow = Old->isScheduleLow;
102  SU->SchedulingPref = Old->SchedulingPref;
103  Old->isCloned = true;
104  return SU;
105 }
106 
107 /// CheckForPhysRegDependency - Check if the dependency between def and use of
108 /// a specified operand is a physical register dependency. If so, returns the
109 /// register and the cost of copying the register.
111  const TargetRegisterInfo *TRI,
112  const TargetInstrInfo *TII,
113  unsigned &PhysReg, int &Cost) {
114  if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
115  return;
116 
117  unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
119  return;
120 
121  unsigned ResNo = User->getOperand(2).getResNo();
122  if (Def->getOpcode() == ISD::CopyFromReg &&
123  cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {
124  PhysReg = Reg;
125  } else if (Def->isMachineOpcode()) {
126  const MCInstrDesc &II = TII->get(Def->getMachineOpcode());
127  if (ResNo >= II.getNumDefs() &&
128  II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg)
129  PhysReg = Reg;
130  }
131 
132  if (PhysReg != 0) {
133  const TargetRegisterClass *RC =
134  TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
135  Cost = RC->getCopyCost();
136  }
137 }
138 
139 // Helper for AddGlue to clone node operands.
141  SDValue ExtraOper = SDValue()) {
142  SmallVector<SDValue, 8> Ops(N->op_begin(), N->op_end());
143  if (ExtraOper.getNode())
144  Ops.push_back(ExtraOper);
145 
146  SDVTList VTList = DAG->getVTList(VTs);
148 
149  // Store memory references.
151  if (MN)
152  MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());
153 
154  DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
155 
156  // Reset the memory references
157  if (MN)
158  DAG->setNodeMemRefs(MN, MMOs);
159 }
160 
161 static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) {
162  SDNode *GlueDestNode = Glue.getNode();
163 
164  // Don't add glue from a node to itself.
165  if (GlueDestNode == N) return false;
166 
167  // Don't add a glue operand to something that already uses glue.
168  if (GlueDestNode &&
169  N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
170  return false;
171  }
172  // Don't add glue to something that already has a glue value.
173  if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;
174 
175  SmallVector<EVT, 4> VTs(N->value_begin(), N->value_end());
176  if (AddGlue)
177  VTs.push_back(MVT::Glue);
178 
179  CloneNodeWithValues(N, DAG, VTs, Glue);
180 
181  return true;
182 }
183 
184 // Cleanup after unsuccessful AddGlue. Use the standard method of morphing the
185 // node even though simply shrinking the value list is sufficient.
186 static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) {
187  assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
188  !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
189  "expected an unused glue value");
190 
191  CloneNodeWithValues(N, DAG,
192  makeArrayRef(N->value_begin(), N->getNumValues() - 1));
193 }
194 
195 /// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.
196 /// This function finds loads of the same base and different offsets. If the
197 /// offsets are not far apart (target specific), it add MVT::Glue inputs and
198 /// outputs to ensure they are scheduled together and in order. This
199 /// optimization may benefit some targets by improving cache locality.
200 void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
201  SDNode *Chain = nullptr;
202  unsigned NumOps = Node->getNumOperands();
203  if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
204  Chain = Node->getOperand(NumOps-1).getNode();
205  if (!Chain)
206  return;
207 
208  // Skip any load instruction that has a tied input. There may be an additional
209  // dependency requiring a different order than by increasing offsets, and the
210  // added glue may introduce a cycle.
211  auto hasTiedInput = [this](const SDNode *N) {
212  const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
213  for (unsigned I = 0; I != MCID.getNumOperands(); ++I) {
214  if (MCID.getOperandConstraint(I, MCOI::TIED_TO) != -1)
215  return true;
216  }
217 
218  return false;
219  };
220 
221  // Look for other loads of the same chain. Find loads that are loading from
222  // the same base pointer and different offsets.
223  SmallPtrSet<SDNode*, 16> Visited;
225  DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode.
226  bool Cluster = false;
227  SDNode *Base = Node;
228 
229  if (hasTiedInput(Base))
230  return;
231 
232  // This algorithm requires a reasonably low use count before finding a match
233  // to avoid uselessly blowing up compile time in large blocks.
234  unsigned UseCount = 0;
235  for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
236  I != E && UseCount < 100; ++I, ++UseCount) {
237  SDNode *User = *I;
238  if (User == Node || !Visited.insert(User).second)
239  continue;
240  int64_t Offset1, Offset2;
241  if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
242  Offset1 == Offset2 ||
243  hasTiedInput(User)) {
244  // FIXME: Should be ok if they addresses are identical. But earlier
245  // optimizations really should have eliminated one of the loads.
246  continue;
247  }
248  if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
249  Offsets.push_back(Offset1);
250  O2SMap.insert(std::make_pair(Offset2, User));
251  Offsets.push_back(Offset2);
252  if (Offset2 < Offset1)
253  Base = User;
254  Cluster = true;
255  // Reset UseCount to allow more matches.
256  UseCount = 0;
257  }
258 
259  if (!Cluster)
260  return;
261 
262  // Sort them in increasing order.
263  llvm::sort(Offsets);
264 
265  // Check if the loads are close enough.
267  unsigned NumLoads = 0;
268  int64_t BaseOff = Offsets[0];
269  SDNode *BaseLoad = O2SMap[BaseOff];
270  Loads.push_back(BaseLoad);
271  for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
272  int64_t Offset = Offsets[i];
273  SDNode *Load = O2SMap[Offset];
274  if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
275  break; // Stop right here. Ignore loads that are further away.
276  Loads.push_back(Load);
277  ++NumLoads;
278  }
279 
280  if (NumLoads == 0)
281  return;
282 
283  // Cluster loads by adding MVT::Glue outputs and inputs. This also
284  // ensure they are scheduled in order of increasing addresses.
285  SDNode *Lead = Loads[0];
286  SDValue InGlue = SDValue(nullptr, 0);
287  if (AddGlue(Lead, InGlue, true, DAG))
288  InGlue = SDValue(Lead, Lead->getNumValues() - 1);
289  for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
290  bool OutGlue = I < E - 1;
291  SDNode *Load = Loads[I];
292 
293  // If AddGlue fails, we could leave an unsused glue value. This should not
294  // cause any
295  if (AddGlue(Load, InGlue, OutGlue, DAG)) {
296  if (OutGlue)
297  InGlue = SDValue(Load, Load->getNumValues() - 1);
298 
299  ++LoadsClustered;
300  }
301  else if (!OutGlue && InGlue.getNode())
302  RemoveUnusedGlue(InGlue.getNode(), DAG);
303  }
304 }
305 
306 /// ClusterNodes - Cluster certain nodes which should be scheduled together.
307 ///
308 void ScheduleDAGSDNodes::ClusterNodes() {
309  for (SDNode &NI : DAG->allnodes()) {
310  SDNode *Node = &NI;
311  if (!Node || !Node->isMachineOpcode())
312  continue;
313 
314  unsigned Opc = Node->getMachineOpcode();
315  const MCInstrDesc &MCID = TII->get(Opc);
316  if (MCID.mayLoad())
317  // Cluster loads from "near" addresses into combined SUnits.
318  ClusterNeighboringLoads(Node);
319  }
320 }
321 
322 void ScheduleDAGSDNodes::BuildSchedUnits() {
323  // During scheduling, the NodeId field of SDNode is used to map SDNodes
324  // to their associated SUnits by holding SUnits table indices. A value
325  // of -1 means the SDNode does not yet have an associated SUnit.
326  unsigned NumNodes = 0;
327  for (SDNode &NI : DAG->allnodes()) {
328  NI.setNodeId(-1);
329  ++NumNodes;
330  }
331 
332  // Reserve entries in the vector for each of the SUnits we are creating. This
333  // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
334  // invalidated.
335  // FIXME: Multiply by 2 because we may clone nodes during scheduling.
336  // This is a temporary workaround.
337  SUnits.reserve(NumNodes * 2);
338 
339  // Add all nodes in depth first order.
340  SmallVector<SDNode*, 64> Worklist;
341  SmallPtrSet<SDNode*, 32> Visited;
342  Worklist.push_back(DAG->getRoot().getNode());
343  Visited.insert(DAG->getRoot().getNode());
344 
345  SmallVector<SUnit*, 8> CallSUnits;
346  while (!Worklist.empty()) {
347  SDNode *NI = Worklist.pop_back_val();
348 
349  // Add all operands to the worklist unless they've already been added.
350  for (const SDValue &Op : NI->op_values())
351  if (Visited.insert(Op.getNode()).second)
352  Worklist.push_back(Op.getNode());
353 
354  if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
355  continue;
356 
357  // If this node has already been processed, stop now.
358  if (NI->getNodeId() != -1) continue;
359 
360  SUnit *NodeSUnit = newSUnit(NI);
361 
362  // See if anything is glued to this node, if so, add them to glued
363  // nodes. Nodes can have at most one glue input and one glue output. Glue
364  // is required to be the last operand and result of a node.
365 
366  // Scan up to find glued preds.
367  SDNode *N = NI;
368  while (N->getNumOperands() &&
369  N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
370  N = N->getOperand(N->getNumOperands()-1).getNode();
371  assert(N->getNodeId() == -1 && "Node already inserted!");
372  N->setNodeId(NodeSUnit->NodeNum);
373  if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
374  NodeSUnit->isCall = true;
375  }
376 
377  // Scan down to find any glued succs.
378  N = NI;
379  while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {
380  SDValue GlueVal(N, N->getNumValues()-1);
381 
382  // There are either zero or one users of the Glue result.
383  bool HasGlueUse = false;
384  for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
385  UI != E; ++UI)
386  if (GlueVal.isOperandOf(*UI)) {
387  HasGlueUse = true;
388  assert(N->getNodeId() == -1 && "Node already inserted!");
389  N->setNodeId(NodeSUnit->NodeNum);
390  N = *UI;
391  if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
392  NodeSUnit->isCall = true;
393  break;
394  }
395  if (!HasGlueUse) break;
396  }
397 
398  if (NodeSUnit->isCall)
399  CallSUnits.push_back(NodeSUnit);
400 
401  // Schedule zero-latency TokenFactor below any nodes that may increase the
402  // schedule height. Otherwise, ancestors of the TokenFactor may appear to
403  // have false stalls.
404  if (NI->getOpcode() == ISD::TokenFactor)
405  NodeSUnit->isScheduleLow = true;
406 
407  // If there are glue operands involved, N is now the bottom-most node
408  // of the sequence of nodes that are glued together.
409  // Update the SUnit.
410  NodeSUnit->setNode(N);
411  assert(N->getNodeId() == -1 && "Node already inserted!");
412  N->setNodeId(NodeSUnit->NodeNum);
413 
414  // Compute NumRegDefsLeft. This must be done before AddSchedEdges.
415  InitNumRegDefsLeft(NodeSUnit);
416 
417  // Assign the Latency field of NodeSUnit using target-provided information.
418  computeLatency(NodeSUnit);
419  }
420 
421  // Find all call operands.
422  while (!CallSUnits.empty()) {
423  SUnit *SU = CallSUnits.pop_back_val();
424  for (const SDNode *SUNode = SU->getNode(); SUNode;
425  SUNode = SUNode->getGluedNode()) {
426  if (SUNode->getOpcode() != ISD::CopyToReg)
427  continue;
428  SDNode *SrcN = SUNode->getOperand(2).getNode();
429  if (isPassiveNode(SrcN)) continue; // Not scheduled.
430  SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
431  SrcSU->isCallOp = true;
432  }
433  }
434 }
435 
436 void ScheduleDAGSDNodes::AddSchedEdges() {
438 
439  // Check to see if the scheduler cares about latencies.
440  bool UnitLatencies = forceUnitLatencies();
441 
442  // Pass 2: add the preds, succs, etc.
443  for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
444  SUnit *SU = &SUnits[su];
445  SDNode *MainNode = SU->getNode();
446 
447  if (MainNode->isMachineOpcode()) {
448  unsigned Opc = MainNode->getMachineOpcode();
449  const MCInstrDesc &MCID = TII->get(Opc);
450  for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
451  if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
452  SU->isTwoAddress = true;
453  break;
454  }
455  }
456  if (MCID.isCommutable())
457  SU->isCommutable = true;
458  }
459 
460  // Find all predecessors and successors of the group.
461  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
462  if (N->isMachineOpcode() &&
463  TII->get(N->getMachineOpcode()).getImplicitDefs()) {
464  SU->hasPhysRegClobbers = true;
465  unsigned NumUsed = InstrEmitter::CountResults(N);
466  while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
467  --NumUsed; // Skip over unused values at the end.
468  if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
469  SU->hasPhysRegDefs = true;
470  }
471 
472  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
473  SDNode *OpN = N->getOperand(i).getNode();
474  if (isPassiveNode(OpN)) continue; // Not scheduled.
475  SUnit *OpSU = &SUnits[OpN->getNodeId()];
476  assert(OpSU && "Node has no SUnit!");
477  if (OpSU == SU) continue; // In the same group.
478 
479  EVT OpVT = N->getOperand(i).getValueType();
480  assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
481  bool isChain = OpVT == MVT::Other;
482 
483  unsigned PhysReg = 0;
484  int Cost = 1;
485  // Determine if this is a physical register dependency.
486  CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
487  assert((PhysReg == 0 || !isChain) &&
488  "Chain dependence via physreg data?");
489  // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
490  // emits a copy from the physical register to a virtual register unless
491  // it requires a cross class copy (cost < 0). That means we are only
492  // treating "expensive to copy" register dependency as physical register
493  // dependency. This may change in the future though.
494  if (Cost >= 0 && !StressSched)
495  PhysReg = 0;
496 
497  // If this is a ctrl dep, latency is 1.
498  unsigned OpLatency = isChain ? 1 : OpSU->Latency;
499  // Special-case TokenFactor chains as zero-latency.
500  if(isChain && OpN->getOpcode() == ISD::TokenFactor)
501  OpLatency = 0;
502 
503  SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
504  : SDep(OpSU, SDep::Data, PhysReg);
505  Dep.setLatency(OpLatency);
506  if (!isChain && !UnitLatencies) {
507  computeOperandLatency(OpN, N, i, Dep);
508  ST.adjustSchedDependency(OpSU, SU, Dep);
509  }
510 
511  if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
512  // Multiple register uses are combined in the same SUnit. For example,
513  // we could have a set of glued nodes with all their defs consumed by
514  // another set of glued nodes. Register pressure tracking sees this as
515  // a single use, so to keep pressure balanced we reduce the defs.
516  //
517  // We can't tell (without more book-keeping) if this results from
518  // glued nodes or duplicate operands. As long as we don't reduce
519  // NumRegDefsLeft to zero, we handle the common cases well.
520  --OpSU->NumRegDefsLeft;
521  }
522  }
523  }
524  }
525 }
526 
527 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
528 /// are input. This SUnit graph is similar to the SelectionDAG, but
529 /// excludes nodes that aren't interesting to scheduling, and represents
530 /// glued together nodes with a single SUnit.
532  // Cluster certain nodes which should be scheduled together.
533  ClusterNodes();
534  // Populate the SUnits array.
535  BuildSchedUnits();
536  // Compute all the scheduling dependencies between nodes.
537  AddSchedEdges();
538 }
539 
540 // Initialize NumNodeDefs for the current Node's opcode.
541 void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
542  // Check for phys reg copy.
543  if (!Node)
544  return;
545 
546  if (!Node->isMachineOpcode()) {
547  if (Node->getOpcode() == ISD::CopyFromReg)
548  NodeNumDefs = 1;
549  else
550  NodeNumDefs = 0;
551  return;
552  }
553  unsigned POpc = Node->getMachineOpcode();
554  if (POpc == TargetOpcode::IMPLICIT_DEF) {
555  // No register need be allocated for this.
556  NodeNumDefs = 0;
557  return;
558  }
559  if (POpc == TargetOpcode::PATCHPOINT &&
560  Node->getValueType(0) == MVT::Other) {
561  // PATCHPOINT is defined to have one result, but it might really have none
562  // if we're not using CallingConv::AnyReg. Don't mistake the chain for a
563  // real definition.
564  NodeNumDefs = 0;
565  return;
566  }
567  unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
568  // Some instructions define regs that are not represented in the selection DAG
569  // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.
570  NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
571  DefIdx = 0;
572 }
573 
574 // Construct a RegDefIter for this SUnit and find the first valid value.
576  const ScheduleDAGSDNodes *SD)
577  : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) {
578  InitNodeNumDefs();
579  Advance();
580 }
581 
582 // Advance to the next valid value defined by the SUnit.
584  for (;Node;) { // Visit all glued nodes.
585  for (;DefIdx < NodeNumDefs; ++DefIdx) {
586  if (!Node->hasAnyUseOfValue(DefIdx))
587  continue;
588  ValueType = Node->getSimpleValueType(DefIdx);
589  ++DefIdx;
590  return; // Found a normal regdef.
591  }
592  Node = Node->getGluedNode();
593  if (!Node) {
594  return; // No values left to visit.
595  }
596  InitNodeNumDefs();
597  }
598 }
599 
601  assert(SU->NumRegDefsLeft == 0 && "expect a new node");
602  for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
603  assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
604  ++SU->NumRegDefsLeft;
605  }
606 }
607 
609  SDNode *N = SU->getNode();
610 
611  // TokenFactor operands are considered zero latency, and some schedulers
612  // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
613  // whenever node latency is nonzero.
614  if (N && N->getOpcode() == ISD::TokenFactor) {
615  SU->Latency = 0;
616  return;
617  }
618 
619  // Check to see if the scheduler cares about latencies.
620  if (forceUnitLatencies()) {
621  SU->Latency = 1;
622  return;
623  }
624 
625  if (!InstrItins || InstrItins->isEmpty()) {
626  if (N && N->isMachineOpcode() &&
629  else
630  SU->Latency = 1;
631  return;
632  }
633 
634  // Compute the latency for the node. We use the sum of the latencies for
635  // all nodes glued together into this SUnit.
636  SU->Latency = 0;
637  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
638  if (N->isMachineOpcode())
640 }
641 
643  unsigned OpIdx, SDep& dep) const{
644  // Check to see if the scheduler cares about latencies.
645  if (forceUnitLatencies())
646  return;
647 
648  if (dep.getKind() != SDep::Data)
649  return;
650 
651  unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
652  if (Use->isMachineOpcode())
653  // Adjust the use operand index by num of defs.
654  OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
655  int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
656  if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg &&
657  !BB->succ_empty()) {
658  unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
660  // This copy is a liveout value. It is likely coalesced, so reduce the
661  // latency so not to penalize the def.
662  // FIXME: need target specific adjustment here?
663  Latency = (Latency > 1) ? Latency - 1 : 1;
664  }
665  if (Latency >= 0)
666  dep.setLatency(Latency);
667 }
668 
669 void ScheduleDAGSDNodes::dumpNode(const SUnit &SU) const {
670 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
671  dumpNodeName(SU);
672  dbgs() << ": ";
673 
674  if (!SU.getNode()) {
675  dbgs() << "PHYS REG COPY\n";
676  return;
677  }
678 
679  SU.getNode()->dump(DAG);
680  dbgs() << "\n";
681  SmallVector<SDNode *, 4> GluedNodes;
682  for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())
683  GluedNodes.push_back(N);
684  while (!GluedNodes.empty()) {
685  dbgs() << " ";
686  GluedNodes.back()->dump(DAG);
687  dbgs() << "\n";
688  GluedNodes.pop_back();
689  }
690 #endif
691 }
692 
694 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
695  if (EntrySU.getNode() != nullptr)
697  for (const SUnit &SU : SUnits)
698  dumpNodeAll(SU);
699  if (ExitSU.getNode() != nullptr)
701 #endif
702 }
703 
704 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
706  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
707  if (SUnit *SU = Sequence[i])
708  dumpNode(*SU);
709  else
710  dbgs() << "**** NOOP ****\n";
711  }
712 }
713 #endif
714 
715 #ifndef NDEBUG
716 /// VerifyScheduledSequence - Verify that all SUnits were scheduled and that
717 /// their state is consistent with the nodes listed in Sequence.
718 ///
720  unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);
721  unsigned Noops = 0;
722  for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
723  if (!Sequence[i])
724  ++Noops;
725  assert(Sequence.size() - Noops == ScheduledNodes &&
726  "The number of nodes scheduled doesn't match the expected number!");
727 }
728 #endif // NDEBUG
729 
730 /// ProcessSDDbgValues - Process SDDbgValues associated with this node.
731 static void
733  SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
734  DenseMap<SDValue, unsigned> &VRBaseMap, unsigned Order) {
735  if (!N->getHasDebugValue())
736  return;
737 
738  // Opportunistically insert immediate dbg_value uses, i.e. those with the same
739  // source order number as N.
740  MachineBasicBlock *BB = Emitter.getBlock();
741  MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
742  for (auto DV : DAG->GetDbgValues(N)) {
743  if (DV->isEmitted())
744  continue;
745  unsigned DVOrder = DV->getOrder();
746  if (!Order || DVOrder == Order) {
747  MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
748  if (DbgMI) {
749  Orders.push_back({DVOrder, DbgMI});
750  BB->insert(InsertPos, DbgMI);
751  }
752  }
753  }
754 }
755 
756 // ProcessSourceNode - Process nodes with source order numbers. These are added
757 // to a vector which EmitSchedule uses to determine how to insert dbg_value
758 // instructions in the right order.
759 static void
761  DenseMap<SDValue, unsigned> &VRBaseMap,
762  SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,
763  SmallSet<unsigned, 8> &Seen, MachineInstr *NewInsn) {
764  unsigned Order = N->getIROrder();
765  if (!Order || Seen.count(Order)) {
766  // Process any valid SDDbgValues even if node does not have any order
767  // assigned.
768  ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
769  return;
770  }
771 
772  // If a new instruction was generated for this Order number, record it.
773  // Otherwise, leave this order number unseen: we will either find later
774  // instructions for it, or leave it unseen if there were no instructions at
775  // all.
776  if (NewInsn) {
777  Seen.insert(Order);
778  Orders.push_back({Order, NewInsn});
779  }
780 
781  // Even if no instruction was generated, a Value may have become defined via
782  // earlier nodes. Try to process them now.
783  ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
784 }
785 
786 void ScheduleDAGSDNodes::
787 EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap,
788  MachineBasicBlock::iterator InsertPos) {
789  for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
790  I != E; ++I) {
791  if (I->isCtrl()) continue; // ignore chain preds
792  if (I->getSUnit()->CopyDstRC) {
793  // Copy to physical register.
794  DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit());
795  assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
796  // Find the destination physical register.
797  unsigned Reg = 0;
798  for (SUnit::const_succ_iterator II = SU->Succs.begin(),
799  EE = SU->Succs.end(); II != EE; ++II) {
800  if (II->isCtrl()) continue; // ignore chain preds
801  if (II->getReg()) {
802  Reg = II->getReg();
803  break;
804  }
805  }
806  BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
807  .addReg(VRI->second);
808  } else {
809  // Copy from physical register.
810  assert(I->getReg() && "Unknown physical register!");
811  unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
812  bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
813  (void)isNew; // Silence compiler warning.
814  assert(isNew && "Node emitted out of order - early");
815  BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
816  .addReg(I->getReg());
817  }
818  break;
819  }
820 }
821 
822 /// EmitSchedule - Emit the machine code in scheduled order. Return the new
823 /// InsertPos and MachineBasicBlock that contains this insertion
824 /// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
825 /// not necessarily refer to returned BB. The emitter may split blocks.
828  InstrEmitter Emitter(BB, InsertPos);
829  DenseMap<SDValue, unsigned> VRBaseMap;
830  DenseMap<SUnit*, unsigned> CopyVRBaseMap;
833  bool HasDbg = DAG->hasDebugValues();
834 
835  // Emit a node, and determine where its first instruction is for debuginfo.
836  // Zero, one, or multiple instructions can be created when emitting a node.
837  auto EmitNode =
838  [&](SDNode *Node, bool IsClone, bool IsCloned,
839  DenseMap<SDValue, unsigned> &VRBaseMap) -> MachineInstr * {
840  // Fetch instruction prior to this, or end() if nonexistant.
841  auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
842  if (I == BB->begin())
843  return BB->end();
844  else
845  return std::prev(Emitter.getInsertPos());
846  };
847 
848  MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
849  Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
850  MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());
851 
852  // If the iterator did not change, no instructions were inserted.
853  if (Before == After)
854  return nullptr;
855 
856  if (Before == BB->end()) {
857  // There were no prior instructions; the new ones must start at the
858  // beginning of the block.
859  return &Emitter.getBlock()->instr_front();
860  } else {
861  // Return first instruction after the pre-existing instructions.
862  return &*std::next(Before);
863  }
864  };
865 
866  // If this is the first BB, emit byval parameter dbg_value's.
867  if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
870  for (; PDI != PDE; ++PDI) {
871  MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
872  if (DbgMI) {
873  BB->insert(InsertPos, DbgMI);
874  // We re-emit the dbg_value closer to its use, too, after instructions
875  // are emitted to the BB.
876  (*PDI)->clearIsEmitted();
877  }
878  }
879  }
880 
881  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
882  SUnit *SU = Sequence[i];
883  if (!SU) {
884  // Null SUnit* is a noop.
885  TII->insertNoop(*Emitter.getBlock(), InsertPos);
886  continue;
887  }
888 
889  // For pre-regalloc scheduling, create instructions corresponding to the
890  // SDNode and any glued SDNodes and append them to the block.
891  if (!SU->getNode()) {
892  // Emit a copy.
893  EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
894  continue;
895  }
896 
897  SmallVector<SDNode *, 4> GluedNodes;
898  for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
899  GluedNodes.push_back(N);
900  while (!GluedNodes.empty()) {
901  SDNode *N = GluedNodes.back();
902  auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
903  // Remember the source order of the inserted instruction.
904  if (HasDbg)
905  ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
906  GluedNodes.pop_back();
907  }
908  auto NewInsn =
909  EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
910  // Remember the source order of the inserted instruction.
911  if (HasDbg)
912  ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
913  NewInsn);
914  }
915 
916  // Insert all the dbg_values which have not already been inserted in source
917  // order sequence.
918  if (HasDbg) {
920 
921  // Sort the source order instructions and use the order to insert debug
922  // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
923  // regardless of the host's implementation fo std::sort.
924  std::stable_sort(Orders.begin(), Orders.end(), less_first());
925  std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
926  [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
927  return LHS->getOrder() < RHS->getOrder();
928  });
929 
930  SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
931  SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
932  // Now emit the rest according to source order.
933  unsigned LastOrder = 0;
934  for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
935  unsigned Order = Orders[i].first;
936  MachineInstr *MI = Orders[i].second;
937  // Insert all SDDbgValue's whose order(s) are before "Order".
938  assert(MI);
939  for (; DI != DE; ++DI) {
940  if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
941  break;
942  if ((*DI)->isEmitted())
943  continue;
944 
945  MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
946  if (DbgMI) {
947  if (!LastOrder)
948  // Insert to start of the BB (after PHIs).
949  BB->insert(BBBegin, DbgMI);
950  else {
951  // Insert at the instruction, which may be in a different
952  // block, if the block was split by a custom inserter.
954  MI->getParent()->insert(Pos, DbgMI);
955  }
956  }
957  }
958  LastOrder = Order;
959  }
960  // Add trailing DbgValue's before the terminator. FIXME: May want to add
961  // some of them before one or more conditional branches?
963  for (; DI != DE; ++DI) {
964  if ((*DI)->isEmitted())
965  continue;
966  assert((*DI)->getOrder() >= LastOrder &&
967  "emitting DBG_VALUE out of order");
968  if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
969  DbgMIs.push_back(DbgMI);
970  }
971 
972  MachineBasicBlock *InsertBB = Emitter.getBlock();
974  InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
975 
978  // Now emit the rest according to source order.
979  LastOrder = 0;
980  for (const auto &InstrOrder : Orders) {
981  unsigned Order = InstrOrder.first;
982  MachineInstr *MI = InstrOrder.second;
983  if (!MI)
984  continue;
985 
986  // Insert all SDDbgLabel's whose order(s) are before "Order".
987  for (; DLI != DLE &&
988  (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
989  ++DLI) {
990  MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
991  if (DbgMI) {
992  if (!LastOrder)
993  // Insert to start of the BB (after PHIs).
994  BB->insert(BBBegin, DbgMI);
995  else {
996  // Insert at the instruction, which may be in a different
997  // block, if the block was split by a custom inserter.
999  MI->getParent()->insert(Pos, DbgMI);
1000  }
1001  }
1002  }
1003  if (DLI == DLE)
1004  break;
1005 
1006  LastOrder = Order;
1007  }
1008  }
1009 
1010  InsertPos = Emitter.getInsertPos();
1011  return Emitter.getBlock();
1012 }
1013 
1014 /// Return the basic block label.
1015 std::string ScheduleDAGSDNodes::getDAGName() const {
1016  return "sunit-dag." + BB->getFullName();
1017 }
SDNode * MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, ArrayRef< SDValue > Ops)
This mutates the specified node to have the specified return type, opcode, and operands.
static cl::opt< int > HighLatencyCycles("sched-high-latency-cycles", cl::Hidden, cl::init(10), cl::desc("Roughly estimate the number of cycles that 'long latency'" "instructions take for targets with no itinerary"))
void dumpNode(const SUnit &SU) const override
EVT getValueType() const
Return the ValueType of the referenced return value.
virtual bool areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2, int64_t &Offset1, int64_t &Offset2) const
This is used by the pre-regalloc scheduler to determine if two loads are loading from the same base a...
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
void setNode(SDNode *N)
Assigns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:348
This class represents lattice values for constants.
Definition: AllocatorList.h:23
value_iterator value_end() const
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z, ..."), which produces the same result if Y and Z are exchanged.
Definition: MCInstrDesc.h:436
MachineInstr & instr_front()
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:355
Sched::Preference getSchedulingPreference() const
Return target scheduling preference.
unsigned getIROrder() const
Return the node ordering.
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
void push_back(const T &Elt)
Definition: SmallVector.h:211
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:277
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
Offsets
Offsets in bytes from the start of the input buffer.
Definition: SIInstrInfo.h:1034
static unsigned CountResults(SDNode *Node)
CountResults - The results of target nodes have register or immediate operands first, then an optional chain, and optional flag operands (which do not go into the machine instrs.)
unsigned second
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:33
MVT getSimpleValueType(unsigned ResNo) const
Return the type of a specified result as a simple type.
SDDbgInfo::DbgLabelIterator DbgLabelBegin() const
void setNodeId(int Id)
Set unique node id.
SDNode * getNode() const
get the SDNode which holds the desired result
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:398
SmallVectorImpl< SDDbgLabel * >::iterator DbgLabelIterator
Definition: SelectionDAG.h:198
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
Definition: ScheduleDAG.h:302
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
virtual bool isHighLatencyDef(int opc) const
Return true if this opcode has high latency to its result.
virtual void adjustSchedDependency(SUnit *def, SUnit *use, SDep &dep) const
MachineBasicBlock * getBlock()
getBlock - Return the current basic block.
Definition: InstrEmitter.h:129
static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef< EVT > VTs, SDValue ExtraOper=SDValue())
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:560
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
void InitNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
void dump() const override
SDDbgInfo::DbgIterator DbgEnd() const
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:210
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
Definition: ScheduleDAG.h:261
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
CopyToReg - This node has three operands: a chain, a register number to set to this value...
Definition: ISDOpcodes.h:169
op_iterator op_end() const
bool hasPhysRegDefs
Has physreg defs that are being used.
Definition: ScheduleDAG.h:280
SmallVectorImpl< SDDbgValue * >::iterator DbgIterator
Definition: SelectionDAG.h:197
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
ScheduleDAGSDNodes(MachineFunction &mf)
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
This represents a list of ValueType&#39;s that has been intern&#39;d by a SelectionDAG.
iterator_range< allnodes_iterator > allnodes()
Definition: SelectionDAG.h:451
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:416
SUnit * OrigNode
If not this, the node from which this node was cloned.
Definition: ScheduleDAG.h:250
static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, unsigned &PhysReg, int &Cost)
CheckForPhysRegDependency - Check if the dependency between def and use of a specified operand is a p...
virtual unsigned getInstrLatency(const InstrItineraryData *ItinData, const MachineInstr &MI, unsigned *PredCost=nullptr) const
Compute the instruction latency of a given instruction.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
std::string getDAGName() const override
Return the basic block label.
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
op_iterator op_begin() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
SDDbgInfo::DbgIterator DbgBegin() const
bool getHasDebugValue() const
mmo_iterator memoperands_end() const
static void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, SmallVectorImpl< std::pair< unsigned, MachineInstr *> > &Orders, DenseMap< SDValue, unsigned > &VRBaseMap, unsigned Order)
ProcessSDDbgValues - Process SDDbgValues associated with this node.
BasicBlockListType::iterator iterator
TargetInstrInfo - Interface to description of machine instruction set.
void dumpNodeAll(const SUnit &SU) const
Scheduling dependency.
Definition: ScheduleDAG.h:49
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
bool isCall
Is a function call.
Definition: ScheduleDAG.h:275
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
std::vector< SUnit * > Sequence
The schedule. Null SUnit*&#39;s represent noop instructions.
SUnit * newSUnit(SDNode *N)
NewSUnit - Creates a new SUnit and return a ptr to it.
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:64
use_iterator use_begin() const
Provide iteration support to walk over all uses of an SDNode.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
bool hasAnyUseOfValue(unsigned Value) const
Return true if there are any use of the indicated value.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
iterator_range< value_op_iterator > op_values() const
bool hasDebugValues() const
Return true if there are any SDDbgValue nodes associated with this SelectionDAG.
const SDValue & getOperand(unsigned Num) const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
virtual void computeOperandLatency(SDNode *Def, SDNode *Use, unsigned OpIdx, SDep &dep) const
const MCPhysReg * ImplicitDefs
Definition: MCInstrDesc.h:173
const InstrItineraryData * InstrItins
bool isVRegCycle
May use and def the same vreg.
Definition: ScheduleDAG.h:274
This class provides iterator support for SDUse operands that use a specific SDNode.
virtual void computeLatency(SUnit *SU)
computeLatency - Compute node latency.
bool isCloned
True if this node has been cloned.
Definition: ScheduleDAG.h:287
SDDbgInfo::DbgIterator ByvalParmDbgEnd() const
static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, DenseMap< SDValue, unsigned > &VRBaseMap, SmallVectorImpl< std::pair< unsigned, MachineInstr *>> &Orders, SmallSet< unsigned, 8 > &Seen, MachineInstr *NewInsn)
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
void dumpNodeName(const SUnit &SU) const
Extended Value Type.
Definition: ValueTypes.h:33
Sched::Preference SchedulingPref
Scheduling preference.
Definition: ScheduleDAG.h:290
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
RegDefIter - In place iteration over the values defined by an SUnit.
size_t size() const
Definition: SmallVector.h:52
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode...
unsigned getNumOperands() const
Return the number of values used by this operation.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
An unknown scheduling barrier.
Definition: ScheduleDAG.h:69
static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG)
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specific constraint if it is set.
Definition: MCInstrDesc.h:187
TokenFactor - This node takes multiple tokens as input and produces a single token result...
Definition: ISDOpcodes.h:49
void dump() const
Dump this node, for debugging.
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:278
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:406
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
MachineBasicBlock * BB
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:221
value_iterator value_begin() const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
int getCopyCost() const
Return the cost of copying a value between two registers in this class.
An SDNode that represents everything that will be needed to construct a MachineInstr.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
SUnit * Clone(SUnit *Old)
Clone - Creates a clone of the specified SUnit.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:225
Represents one node in the SelectionDAG.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one...
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
static use_iterator use_end()
SmallVectorImpl< SDep >::const_iterator const_succ_iterator
Definition: ScheduleDAG.h:262
SDDbgInfo::DbgLabelIterator DbgLabelEnd() const
bool isCallOp
Is a function call operand.
Definition: ScheduleDAG.h:276
bool isEmpty() const
Returns true if there are no itineraries.
void setLatency(unsigned Lat)
Sets the latency for this edge.
Definition: ScheduleDAG.h:147
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
static bool isPassiveNode(SDNode *Node)
isPassiveNode - Return true if the node is a non-scheduled leaf.
TargetSubtargetInfo - Generic base class for all target subtargets.
int getNodeId() const
Return the unique node id.
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:563
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
virtual void insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const
Insert a noop into the instruction stream at the specified point.
Representation of each machine instruction.
Definition: MachineInstr.h:63
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:564
mmo_iterator memoperands_begin() const
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:559
void EmitNode(SDNode *Node, bool IsClone, bool IsCloned, DenseMap< SDValue, unsigned > &VRBaseMap)
EmitNode - Generate machine code for a node and needed dependencies.
Definition: InstrEmitter.h:120
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD)
void BuildSchedGraph(AliasAnalysis *AA)
BuildSchedGraph - Build the SUnit graph from the selection dag that we are input. ...
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
unsigned short NumRegDefsLeft
of reg defs with no scheduled use.
Definition: ScheduleDAG.h:272
SDDbgInfo::DbgIterator ByvalParmDbgBegin() const
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
void Run(SelectionDAG *dag, MachineBasicBlock *bb)
Run - perform scheduling.
MachineInstr * EmitDbgLabel(SDDbgLabel *SD)
Generate machine instruction for a dbg_label node.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:558
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
Definition: ISDOpcodes.h:174
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
Definition: SelectionDAG.h:459
const TargetRegisterClass * getMinimalPhysRegClass(unsigned Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineInstr * EmitDbgValue(SDDbgValue *SD, DenseMap< SDValue, unsigned > &VRBaseMap)
EmitDbgValue - Generate machine instruction for a dbg_value node.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
MachineBasicBlock::iterator getInsertPos()
getInsertPos - Return the current insertion position.
Definition: InstrEmitter.h:132
unsigned getResNo() const
get the index which selects a specific result in the SDNode
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
virtual MachineBasicBlock * EmitSchedule(MachineBasicBlock::iterator &InsertPos)
EmitSchedule - Insert MachineInstrs into the MachineBasicBlock according to the order specified in Se...
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
ArrayRef< SDDbgValue * > GetDbgValues(const SDNode *SD) const
Get the debug values which reference the given SDNode.
IRTranslator LLVM IR MI
bool isScheduleLow
True if preferable to schedule low.
Definition: ScheduleDAG.h:286
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:561
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
void setNodeMemRefs(MachineSDNode *N, ArrayRef< MachineMemOperand *> NewMemRefs)
Mutate the specified machine node&#39;s memory references to the provided list.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
bool hasPhysRegClobbers
Has any physreg defs, used or not.
Definition: ScheduleDAG.h:281
Holds the information from a dbg_value node through SDISel.
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
virtual int getOperandLatency(const InstrItineraryData *ItinData, SDNode *DefNode, unsigned DefIdx, SDNode *UseNode, unsigned UseIdx) const
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:959
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
virtual bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2, int64_t Offset1, int64_t Offset2, unsigned NumLoads) const
This is a used by the pre-regalloc scheduler to determine (in conjunction with areLoadsFromSameBasePt...
unsigned getOrder() const
Returns the SDNodeOrder.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG)
This file describes how to lower LLVM code to machine code.
void VerifyScheduledSequence(bool isBottomUp)
VerifyScheduledSequence - Verify that all SUnits are scheduled and consistent with the Sequence of sc...
A discriminated union of two pointer types, with the discriminator in the low bit of the pointer...
Definition: PointerUnion.h:86
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164