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