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