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