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 *U : N->uses())
388  if (GlueVal.isOperandOf(U)) {
389  HasGlueUse = true;
390  assert(N->getNodeId() == -1 && "Node already inserted!");
391  N->setNodeId(NodeSUnit->NodeNum);
392  N = U;
393  if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
394  NodeSUnit->isCall = true;
395  break;
396  }
397  if (!HasGlueUse) break;
398  }
399 
400  if (NodeSUnit->isCall)
401  CallSUnits.push_back(NodeSUnit);
402 
403  // Schedule zero-latency TokenFactor below any nodes that may increase the
404  // schedule height. Otherwise, ancestors of the TokenFactor may appear to
405  // have false stalls.
406  if (NI->getOpcode() == ISD::TokenFactor)
407  NodeSUnit->isScheduleLow = true;
408 
409  // If there are glue operands involved, N is now the bottom-most node
410  // of the sequence of nodes that are glued together.
411  // Update the SUnit.
412  NodeSUnit->setNode(N);
413  assert(N->getNodeId() == -1 && "Node already inserted!");
414  N->setNodeId(NodeSUnit->NodeNum);
415 
416  // Compute NumRegDefsLeft. This must be done before AddSchedEdges.
417  InitNumRegDefsLeft(NodeSUnit);
418 
419  // Assign the Latency field of NodeSUnit using target-provided information.
420  computeLatency(NodeSUnit);
421  }
422 
423  // Find all call operands.
424  while (!CallSUnits.empty()) {
425  SUnit *SU = CallSUnits.pop_back_val();
426  for (const SDNode *SUNode = SU->getNode(); SUNode;
427  SUNode = SUNode->getGluedNode()) {
428  if (SUNode->getOpcode() != ISD::CopyToReg)
429  continue;
430  SDNode *SrcN = SUNode->getOperand(2).getNode();
431  if (isPassiveNode(SrcN)) continue; // Not scheduled.
432  SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
433  SrcSU->isCallOp = true;
434  }
435  }
436 }
437 
438 void ScheduleDAGSDNodes::AddSchedEdges() {
440 
441  // Check to see if the scheduler cares about latencies.
442  bool UnitLatencies = forceUnitLatencies();
443 
444  // Pass 2: add the preds, succs, etc.
445  for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
446  SUnit *SU = &SUnits[su];
447  SDNode *MainNode = SU->getNode();
448 
449  if (MainNode->isMachineOpcode()) {
450  unsigned Opc = MainNode->getMachineOpcode();
451  const MCInstrDesc &MCID = TII->get(Opc);
452  for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
453  if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
454  SU->isTwoAddress = true;
455  break;
456  }
457  }
458  if (MCID.isCommutable())
459  SU->isCommutable = true;
460  }
461 
462  // Find all predecessors and successors of the group.
463  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
464  if (N->isMachineOpcode() &&
465  TII->get(N->getMachineOpcode()).getImplicitDefs()) {
466  SU->hasPhysRegClobbers = true;
467  unsigned NumUsed = InstrEmitter::CountResults(N);
468  while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
469  --NumUsed; // Skip over unused values at the end.
470  if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
471  SU->hasPhysRegDefs = true;
472  }
473 
474  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
475  SDNode *OpN = N->getOperand(i).getNode();
476  unsigned DefIdx = N->getOperand(i).getResNo();
477  if (isPassiveNode(OpN)) continue; // Not scheduled.
478  SUnit *OpSU = &SUnits[OpN->getNodeId()];
479  assert(OpSU && "Node has no SUnit!");
480  if (OpSU == SU) continue; // In the same group.
481 
482  EVT OpVT = N->getOperand(i).getValueType();
483  assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
484  bool isChain = OpVT == MVT::Other;
485 
486  unsigned PhysReg = 0;
487  int Cost = 1;
488  // Determine if this is a physical register dependency.
489  CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
490  assert((PhysReg == 0 || !isChain) &&
491  "Chain dependence via physreg data?");
492  // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
493  // emits a copy from the physical register to a virtual register unless
494  // it requires a cross class copy (cost < 0). That means we are only
495  // treating "expensive to copy" register dependency as physical register
496  // dependency. This may change in the future though.
497  if (Cost >= 0 && !StressSched)
498  PhysReg = 0;
499 
500  // If this is a ctrl dep, latency is 1.
501  unsigned OpLatency = isChain ? 1 : OpSU->Latency;
502  // Special-case TokenFactor chains as zero-latency.
503  if(isChain && OpN->getOpcode() == ISD::TokenFactor)
504  OpLatency = 0;
505 
506  SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
507  : SDep(OpSU, SDep::Data, PhysReg);
508  Dep.setLatency(OpLatency);
509  if (!isChain && !UnitLatencies) {
510  computeOperandLatency(OpN, N, i, Dep);
511  ST.adjustSchedDependency(OpSU, DefIdx, SU, i, Dep);
512  }
513 
514  if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
515  // Multiple register uses are combined in the same SUnit. For example,
516  // we could have a set of glued nodes with all their defs consumed by
517  // another set of glued nodes. Register pressure tracking sees this as
518  // a single use, so to keep pressure balanced we reduce the defs.
519  //
520  // We can't tell (without more book-keeping) if this results from
521  // glued nodes or duplicate operands. As long as we don't reduce
522  // NumRegDefsLeft to zero, we handle the common cases well.
523  --OpSU->NumRegDefsLeft;
524  }
525  }
526  }
527  }
528 }
529 
530 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
531 /// are input. This SUnit graph is similar to the SelectionDAG, but
532 /// excludes nodes that aren't interesting to scheduling, and represents
533 /// glued together nodes with a single SUnit.
535  // Cluster certain nodes which should be scheduled together.
536  ClusterNodes();
537  // Populate the SUnits array.
538  BuildSchedUnits();
539  // Compute all the scheduling dependencies between nodes.
540  AddSchedEdges();
541 }
542 
543 // Initialize NumNodeDefs for the current Node's opcode.
544 void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
545  // Check for phys reg copy.
546  if (!Node)
547  return;
548 
549  if (!Node->isMachineOpcode()) {
550  if (Node->getOpcode() == ISD::CopyFromReg)
551  NodeNumDefs = 1;
552  else
553  NodeNumDefs = 0;
554  return;
555  }
556  unsigned POpc = Node->getMachineOpcode();
557  if (POpc == TargetOpcode::IMPLICIT_DEF) {
558  // No register need be allocated for this.
559  NodeNumDefs = 0;
560  return;
561  }
562  if (POpc == TargetOpcode::PATCHPOINT &&
563  Node->getValueType(0) == MVT::Other) {
564  // PATCHPOINT is defined to have one result, but it might really have none
565  // if we're not using CallingConv::AnyReg. Don't mistake the chain for a
566  // real definition.
567  NodeNumDefs = 0;
568  return;
569  }
570  unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
571  // Some instructions define regs that are not represented in the selection DAG
572  // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.
573  NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
574  DefIdx = 0;
575 }
576 
577 // Construct a RegDefIter for this SUnit and find the first valid value.
579  const ScheduleDAGSDNodes *SD)
580  : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) {
581  InitNodeNumDefs();
582  Advance();
583 }
584 
585 // Advance to the next valid value defined by the SUnit.
587  for (;Node;) { // Visit all glued nodes.
588  for (;DefIdx < NodeNumDefs; ++DefIdx) {
589  if (!Node->hasAnyUseOfValue(DefIdx))
590  continue;
591  ValueType = Node->getSimpleValueType(DefIdx);
592  ++DefIdx;
593  return; // Found a normal regdef.
594  }
595  Node = Node->getGluedNode();
596  if (!Node) {
597  return; // No values left to visit.
598  }
599  InitNodeNumDefs();
600  }
601 }
602 
604  assert(SU->NumRegDefsLeft == 0 && "expect a new node");
605  for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
606  assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
607  ++SU->NumRegDefsLeft;
608  }
609 }
610 
612  SDNode *N = SU->getNode();
613 
614  // TokenFactor operands are considered zero latency, and some schedulers
615  // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
616  // whenever node latency is nonzero.
617  if (N && N->getOpcode() == ISD::TokenFactor) {
618  SU->Latency = 0;
619  return;
620  }
621 
622  // Check to see if the scheduler cares about latencies.
623  if (forceUnitLatencies()) {
624  SU->Latency = 1;
625  return;
626  }
627 
628  if (!InstrItins || InstrItins->isEmpty()) {
629  if (N && N->isMachineOpcode() &&
630  TII->isHighLatencyDef(N->getMachineOpcode()))
632  else
633  SU->Latency = 1;
634  return;
635  }
636 
637  // Compute the latency for the node. We use the sum of the latencies for
638  // all nodes glued together into this SUnit.
639  SU->Latency = 0;
640  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
641  if (N->isMachineOpcode())
643 }
644 
646  unsigned OpIdx, SDep& dep) const{
647  // Check to see if the scheduler cares about latencies.
648  if (forceUnitLatencies())
649  return;
650 
651  if (dep.getKind() != SDep::Data)
652  return;
653 
654  unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
655  if (Use->isMachineOpcode())
656  // Adjust the use operand index by num of defs.
657  OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
658  int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
659  if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg &&
660  !BB->succ_empty()) {
661  unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
663  // This copy is a liveout value. It is likely coalesced, so reduce the
664  // latency so not to penalize the def.
665  // FIXME: need target specific adjustment here?
666  Latency = (Latency > 1) ? Latency - 1 : 1;
667  }
668  if (Latency >= 0)
669  dep.setLatency(Latency);
670 }
671 
672 void ScheduleDAGSDNodes::dumpNode(const SUnit &SU) const {
673 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
674  dumpNodeName(SU);
675  dbgs() << ": ";
676 
677  if (!SU.getNode()) {
678  dbgs() << "PHYS REG COPY\n";
679  return;
680  }
681 
682  SU.getNode()->dump(DAG);
683  dbgs() << "\n";
684  SmallVector<SDNode *, 4> GluedNodes;
685  for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())
686  GluedNodes.push_back(N);
687  while (!GluedNodes.empty()) {
688  dbgs() << " ";
689  GluedNodes.back()->dump(DAG);
690  dbgs() << "\n";
691  GluedNodes.pop_back();
692  }
693 #endif
694 }
695 
697 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
698  if (EntrySU.getNode() != nullptr)
700  for (const SUnit &SU : SUnits)
701  dumpNodeAll(SU);
702  if (ExitSU.getNode() != nullptr)
704 #endif
705 }
706 
707 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
709  for (const SUnit *SU : Sequence) {
710  if (SU)
711  dumpNode(*SU);
712  else
713  dbgs() << "**** NOOP ****\n";
714  }
715 }
716 #endif
717 
718 #ifndef NDEBUG
719 /// VerifyScheduledSequence - Verify that all SUnits were scheduled and that
720 /// their state is consistent with the nodes listed in Sequence.
721 ///
723  unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);
724  unsigned Noops = 0;
725  for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
726  if (!Sequence[i])
727  ++Noops;
728  assert(Sequence.size() - Noops == ScheduledNodes &&
729  "The number of nodes scheduled doesn't match the expected number!");
730 }
731 #endif // NDEBUG
732 
733 /// ProcessSDDbgValues - Process SDDbgValues associated with this node.
734 static void
736  SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
737  DenseMap<SDValue, Register> &VRBaseMap, unsigned Order) {
738  if (!N->getHasDebugValue())
739  return;
740 
741  /// Returns true if \p DV has any VReg operand locations which don't exist in
742  /// VRBaseMap.
743  auto HasUnknownVReg = [&VRBaseMap](SDDbgValue *DV) {
744  for (const SDDbgOperand &L : DV->getLocationOps()) {
745  if (L.getKind() == SDDbgOperand::SDNODE &&
746  VRBaseMap.count({L.getSDNode(), L.getResNo()}) == 0)
747  return true;
748  }
749  return false;
750  };
751 
752  // Opportunistically insert immediate dbg_value uses, i.e. those with the same
753  // source order number as N.
754  MachineBasicBlock *BB = Emitter.getBlock();
755  MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
756  for (auto DV : DAG->GetDbgValues(N)) {
757  if (DV->isEmitted())
758  continue;
759  unsigned DVOrder = DV->getOrder();
760  if (Order != 0 && DVOrder != Order)
761  continue;
762  // If DV has any VReg location operands which haven't been mapped then
763  // either that node is no longer available or we just haven't visited the
764  // node yet. In the former case we should emit an undef dbg_value, but we
765  // can do it later. And for the latter we'll want to wait until all
766  // dependent nodes have been visited.
767  if (!DV->isInvalidated() && HasUnknownVReg(DV))
768  continue;
769  MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
770  if (!DbgMI)
771  continue;
772  Orders.push_back({DVOrder, DbgMI});
773  BB->insert(InsertPos, DbgMI);
774  }
775 }
776 
777 // ProcessSourceNode - Process nodes with source order numbers. These are added
778 // to a vector which EmitSchedule uses to determine how to insert dbg_value
779 // instructions in the right order.
780 static void
782  DenseMap<SDValue, Register> &VRBaseMap,
783  SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,
784  SmallSet<Register, 8> &Seen, MachineInstr *NewInsn) {
785  unsigned Order = N->getIROrder();
786  if (!Order || Seen.count(Order)) {
787  // Process any valid SDDbgValues even if node does not have any order
788  // assigned.
789  ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
790  return;
791  }
792 
793  // If a new instruction was generated for this Order number, record it.
794  // Otherwise, leave this order number unseen: we will either find later
795  // instructions for it, or leave it unseen if there were no instructions at
796  // all.
797  if (NewInsn) {
798  Seen.insert(Order);
799  Orders.push_back({Order, NewInsn});
800  }
801 
802  // Even if no instruction was generated, a Value may have become defined via
803  // earlier nodes. Try to process them now.
804  ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
805 }
806 
807 void ScheduleDAGSDNodes::
808 EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, Register> &VRBaseMap,
809  MachineBasicBlock::iterator InsertPos) {
810  for (const SDep &Pred : SU->Preds) {
811  if (Pred.isCtrl())
812  continue; // ignore chain preds
813  if (Pred.getSUnit()->CopyDstRC) {
814  // Copy to physical register.
816  VRBaseMap.find(Pred.getSUnit());
817  assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
818  // Find the destination physical register.
819  Register Reg;
820  for (const SDep &Succ : SU->Succs) {
821  if (Succ.isCtrl())
822  continue; // ignore chain preds
823  if (Succ.getReg()) {
824  Reg = Succ.getReg();
825  break;
826  }
827  }
828  BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
829  .addReg(VRI->second);
830  } else {
831  // Copy from physical register.
832  assert(Pred.getReg() && "Unknown physical register!");
834  bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
835  (void)isNew; // Silence compiler warning.
836  assert(isNew && "Node emitted out of order - early");
837  BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
838  .addReg(Pred.getReg());
839  }
840  break;
841  }
842 }
843 
844 /// EmitSchedule - Emit the machine code in scheduled order. Return the new
845 /// InsertPos and MachineBasicBlock that contains this insertion
846 /// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
847 /// not necessarily refer to returned BB. The emitter may split blocks.
850  InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
851  DenseMap<SDValue, Register> VRBaseMap;
852  DenseMap<SUnit*, Register> CopyVRBaseMap;
855  bool HasDbg = DAG->hasDebugValues();
856 
857  // Emit a node, and determine where its first instruction is for debuginfo.
858  // Zero, one, or multiple instructions can be created when emitting a node.
859  auto EmitNode =
860  [&](SDNode *Node, bool IsClone, bool IsCloned,
861  DenseMap<SDValue, Register> &VRBaseMap) -> MachineInstr * {
862  // Fetch instruction prior to this, or end() if nonexistant.
863  auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
864  if (I == BB->begin())
865  return BB->end();
866  else
867  return std::prev(Emitter.getInsertPos());
868  };
869 
870  MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
871  Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
872  MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());
873 
874  // If the iterator did not change, no instructions were inserted.
875  if (Before == After)
876  return nullptr;
877 
878  MachineInstr *MI;
879  if (Before == BB->end()) {
880  // There were no prior instructions; the new ones must start at the
881  // beginning of the block.
882  MI = &Emitter.getBlock()->instr_front();
883  } else {
884  // Return first instruction after the pre-existing instructions.
885  MI = &*std::next(Before);
886  }
887 
888  if (MI->isCandidateForCallSiteEntry() &&
891 
892  if (DAG->getNoMergeSiteInfo(Node)) {
893  MI->setFlag(MachineInstr::MIFlag::NoMerge);
894  }
895 
896  return MI;
897  };
898 
899  // If this is the first BB, emit byval parameter dbg_value's.
900  if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
903  for (; PDI != PDE; ++PDI) {
904  MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
905  if (DbgMI) {
906  BB->insert(InsertPos, DbgMI);
907  // We re-emit the dbg_value closer to its use, too, after instructions
908  // are emitted to the BB.
909  (*PDI)->clearIsEmitted();
910  }
911  }
912  }
913 
914  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
915  SUnit *SU = Sequence[i];
916  if (!SU) {
917  // Null SUnit* is a noop.
918  TII->insertNoop(*Emitter.getBlock(), InsertPos);
919  continue;
920  }
921 
922  // For pre-regalloc scheduling, create instructions corresponding to the
923  // SDNode and any glued SDNodes and append them to the block.
924  if (!SU->getNode()) {
925  // Emit a copy.
926  EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
927  continue;
928  }
929 
930  SmallVector<SDNode *, 4> GluedNodes;
931  for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
932  GluedNodes.push_back(N);
933  while (!GluedNodes.empty()) {
934  SDNode *N = GluedNodes.back();
935  auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
936  // Remember the source order of the inserted instruction.
937  if (HasDbg)
938  ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
939 
940  if (MDNode *MD = DAG->getHeapAllocSite(N))
941  if (NewInsn && NewInsn->isCall())
942  NewInsn->setHeapAllocMarker(MF, MD);
943 
944  GluedNodes.pop_back();
945  }
946  auto NewInsn =
947  EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
948  // Remember the source order of the inserted instruction.
949  if (HasDbg)
950  ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
951  NewInsn);
952 
953  if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {
954  if (NewInsn && NewInsn->isCall())
955  NewInsn->setHeapAllocMarker(MF, MD);
956  }
957  }
958 
959  // Insert all the dbg_values which have not already been inserted in source
960  // order sequence.
961  if (HasDbg) {
963 
964  // Sort the source order instructions and use the order to insert debug
965  // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
966  // regardless of the host's implementation fo std::sort.
967  llvm::stable_sort(Orders, less_first());
969  [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
970  return LHS->getOrder() < RHS->getOrder();
971  });
972 
975  // Now emit the rest according to source order.
976  unsigned LastOrder = 0;
977  for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
978  unsigned Order = Orders[i].first;
979  MachineInstr *MI = Orders[i].second;
980  // Insert all SDDbgValue's whose order(s) are before "Order".
981  assert(MI);
982  for (; DI != DE; ++DI) {
983  if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
984  break;
985  if ((*DI)->isEmitted())
986  continue;
987 
988  MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
989  if (DbgMI) {
990  if (!LastOrder)
991  // Insert to start of the BB (after PHIs).
992  BB->insert(BBBegin, DbgMI);
993  else {
994  // Insert at the instruction, which may be in a different
995  // block, if the block was split by a custom inserter.
997  MI->getParent()->insert(Pos, DbgMI);
998  }
999  }
1000  }
1001  LastOrder = Order;
1002  }
1003  // Add trailing DbgValue's before the terminator. FIXME: May want to add
1004  // some of them before one or more conditional branches?
1006  for (; DI != DE; ++DI) {
1007  if ((*DI)->isEmitted())
1008  continue;
1009  assert((*DI)->getOrder() >= LastOrder &&
1010  "emitting DBG_VALUE out of order");
1011  if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
1012  DbgMIs.push_back(DbgMI);
1013  }
1014 
1015  MachineBasicBlock *InsertBB = Emitter.getBlock();
1017  InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
1018 
1021  // Now emit the rest according to source order.
1022  LastOrder = 0;
1023  for (const auto &InstrOrder : Orders) {
1024  unsigned Order = InstrOrder.first;
1025  MachineInstr *MI = InstrOrder.second;
1026  if (!MI)
1027  continue;
1028 
1029  // Insert all SDDbgLabel's whose order(s) are before "Order".
1030  for (; DLI != DLE &&
1031  (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
1032  ++DLI) {
1033  MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
1034  if (DbgMI) {
1035  if (!LastOrder)
1036  // Insert to start of the BB (after PHIs).
1037  BB->insert(BBBegin, DbgMI);
1038  else {
1039  // Insert at the instruction, which may be in a different
1040  // block, if the block was split by a custom inserter.
1042  MI->getParent()->insert(Pos, DbgMI);
1043  }
1044  }
1045  }
1046  if (DLI == DLE)
1047  break;
1048 
1049  LastOrder = Order;
1050  }
1051  }
1052 
1053  InsertPos = Emitter.getInsertPos();
1054  // In some cases, DBG_VALUEs might be inserted after the first terminator,
1055  // which results in an invalid MBB. If that happens, move the DBG_VALUEs
1056  // before the first terminator.
1057  MachineBasicBlock *InsertBB = Emitter.getBlock();
1058  auto FirstTerm = InsertBB->getFirstTerminator();
1059  if (FirstTerm != InsertBB->end()) {
1060  assert(!FirstTerm->isDebugValue() &&
1061  "first terminator cannot be a debug value");
1063  make_range(std::next(FirstTerm), InsertBB->end()))) {
1064  if (!MI.isDebugValue())
1065  continue;
1066 
1067  if (&MI == InsertPos)
1068  InsertPos = std::prev(InsertPos->getIterator());
1069 
1070  // The DBG_VALUE was referencing a value produced by a terminator. By
1071  // moving the DBG_VALUE, the referenced value also needs invalidating.
1072  MI.getOperand(0).ChangeToRegister(0, false);
1073  MI.moveBefore(&*FirstTerm);
1074  }
1075  }
1076  return InsertBB;
1077 }
1078 
1079 /// Return the basic block label.
1080 std::string ScheduleDAGSDNodes::getDAGName() const {
1081  return "sunit-dag." + BB->getFullName();
1082 }
i
i
Definition: README.txt:29
llvm::ScheduleDAGSDNodes::computeLatency
virtual void computeLatency(SUnit *SU)
computeLatency - Compute node latency.
Definition: ScheduleDAGSDNodes.cpp:611
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 is an optimization pass for GlobalISel generic memory operations.
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:1558
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:1311
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:151
llvm::ScheduleDAGSDNodes::VerifyScheduledSequence
void VerifyScheduledSequence(bool isBottomUp)
VerifyScheduledSequence - Verify that all SUnits are scheduled and consistent with the Sequence of sc...
Definition: ScheduleDAGSDNodes.cpp:722
llvm::SDNode::op_values
iterator_range< value_op_iterator > op_values() const
Definition: SelectionDAGNodes.h:926
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:8534
llvm::MachineSDNode
An SDNode that represents everything that will be needed to construct a MachineInstr.
Definition: SelectionDAGNodes.h:2762
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:2804
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:2071
llvm::SUnit::isCall
bool isCall
Is a function call.
Definition: ScheduleDAG.h:275
llvm::SDNode
Represents one node in the SelectionDAG.
Definition: SelectionDAGNodes.h:454
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:726
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
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:1559
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:1632
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:578
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:628
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:1327
llvm::ScheduleDAGSDNodes::getDAGName
std::string getDAGName() const override
Return the basic block label.
Definition: ScheduleDAGSDNodes.cpp:1080
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3254
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:1325
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
ScheduleDAGSDNodes.h
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:816
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:586
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:645
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:2047
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:634
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:782
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:1189
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:914
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:903
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:593
llvm::MachineBasicBlock::getFirstNonPHI
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: MachineBasicBlock.cpp:199
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:8871
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:121
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:706
llvm::SDValue::getResNo
unsigned getResNo() const
get the index which selects a specific result in the SDNode
Definition: SelectionDAGNodes.h:148
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:849
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:8740
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:735
llvm::SDNode::isMachineOpcode
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.
Definition: SelectionDAGNodes.h:680
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:241
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:786
llvm::MachineBasicBlock::getFullName
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
Definition: MachineBasicBlock.cpp:321
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:781
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:78
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:708
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:1735
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:325
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:1314
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:1541
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:2805
llvm::SDValue
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
Definition: SelectionDAGNodes.h:137
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:962
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:1150
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:856
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::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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:685
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:474
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:696
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:672
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:1088
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:2059
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:1263
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:534
llvm::ScheduleDAGSDNodes::InitNumRegDefsLeft
void InitNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
Definition: ScheduleDAGSDNodes.cpp:603
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:938
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