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