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