LLVM 22.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"
19#include "llvm/ADT/SmallSet.h"
21#include "llvm/ADT/Statistic.h"
29#include "llvm/Config/llvm-config.h"
33#include "llvm/Support/Debug.h"
36using namespace llvm;
37
38#define DEBUG_TYPE "pre-RA-sched"
39
40STATISTIC(LoadsClustered, "Number of loads clustered together");
41
42// This allows the latency-based scheduler to notice high latency instructions
43// without a target itinerary. The choice of number here has more to do with
44// balancing scheduler heuristics than with the actual machine latency.
46 "sched-high-latency-cycles", cl::Hidden, cl::init(10),
47 cl::desc("Roughly estimate the number of cycles that 'long latency' "
48 "instructions take for targets with no itinerary"));
49
51 : ScheduleDAG(mf), 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();
80 const TargetLowering &TLI = DAG->getTargetLoweringInfo();
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;
102 SU->isScheduleLow = Old->isScheduleLow;
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.
111static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
112 const TargetRegisterInfo *TRI,
113 const TargetInstrInfo *TII,
114 MCRegister &PhysReg, int &Cost) {
115 if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
116 return;
117
119 if (Reg.isVirtual())
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) {
133 const TargetRegisterClass *RC =
134 TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
135 Cost = RC->expensiveOrImpossibleToCopy() ? -1 : RC->getCopyCost();
136 }
137}
138
139// Helper for AddGlue to clone node operands.
141 SDValue ExtraOper = SDValue()) {
143 if (ExtraOper.getNode())
144 Ops.push_back(ExtraOper);
145
146 SDVTList VTList = DAG->getVTList(VTs);
148
149 // Store memory references.
151 if (MN)
152 MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());
153
154 DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
155
156 // Reset the memory references
157 if (MN)
158 DAG->setNodeMemRefs(MN, MMOs);
159}
160
161static 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.
187 assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
188 !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
189 "expected an unused glue value");
190
192 ArrayRef(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.
200void 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::user_iterator I = Chain->user_begin(), E = Chain->user_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.
266 llvm::sort(Offsets);
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;
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///
311void 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
325void 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.
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->users())
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
438void ScheduleDAGSDNodes::AddSchedEdges() {
439 const TargetSubtargetInfo &ST = MF.getSubtarget();
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 (SUnit &SU : SUnits) {
446 SDNode *MainNode = SU.getNode();
447
448 if (MainNode->isMachineOpcode()) {
449 unsigned Opc = MainNode->getMachineOpcode();
450 const MCInstrDesc &MCID = TII->get(Opc);
451 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
452 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
453 SU.isTwoAddress = true;
454 break;
455 }
456 }
457 if (MCID.isCommutable())
458 SU.isCommutable = true;
459 }
460
461 // Find all predecessors and successors of the group.
462 for (SDNode *N = SU.getNode(); N; N = N->getGluedNode()) {
463 if (N->isMachineOpcode() &&
464 !TII->get(N->getMachineOpcode()).implicit_defs().empty()) {
465 SU.hasPhysRegClobbers = true;
466 unsigned NumUsed = InstrEmitter::CountResults(N);
467 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
468 --NumUsed; // Skip over unused values at the end.
469 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
470 SU.hasPhysRegDefs = true;
471 }
472
473 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
474 SDNode *OpN = N->getOperand(i).getNode();
475 unsigned DefIdx = N->getOperand(i).getResNo();
476 if (isPassiveNode(OpN)) continue; // Not scheduled.
477 SUnit *OpSU = &SUnits[OpN->getNodeId()];
478 assert(OpSU && "Node has no SUnit!");
479 if (OpSU == &SU)
480 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 MCRegister PhysReg;
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 || !isChain) && "Chain dependence via physreg data?");
491 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
492 // emits a copy from the physical register to a virtual register unless
493 // it requires a cross class copy (cost < 0). That means we are only
494 // treating "expensive to copy" register dependency as physical register
495 // dependency. This may change in the future though.
496 if (Cost >= 0 && !StressSched)
497 PhysReg = MCRegister();
498
499 // If this is a ctrl dep, latency is 1.
500 unsigned OpLatency = isChain ? 1 : OpSU->Latency;
501 // Special-case TokenFactor chains as zero-latency.
502 if(isChain && OpN->getOpcode() == ISD::TokenFactor)
503 OpLatency = 0;
504
505 SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
506 : SDep(OpSU, SDep::Data, PhysReg);
507 Dep.setLatency(OpLatency);
508 if (!isChain && !UnitLatencies) {
509 computeOperandLatency(OpN, N, i, Dep);
510 ST.adjustSchedDependency(OpSU, DefIdx, &SU, i, Dep, nullptr);
511 }
512
513 if (!SU.addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
514 // Multiple register uses are combined in the same SUnit. For example,
515 // we could have a set of glued nodes with all their defs consumed by
516 // another set of glued nodes. Register pressure tracking sees this as
517 // a single use, so to keep pressure balanced we reduce the defs.
518 //
519 // We can't tell (without more book-keeping) if this results from
520 // glued nodes or duplicate operands. As long as we don't reduce
521 // NumRegDefsLeft to zero, we handle the common cases well.
522 --OpSU->NumRegDefsLeft;
523 }
524 }
525 }
526 }
527}
528
529/// BuildSchedGraph - Build the SUnit graph from the selection dag that we
530/// are input. This SUnit graph is similar to the SelectionDAG, but
531/// excludes nodes that aren't interesting to scheduling, and represents
532/// glued together nodes with a single SUnit.
534 // Cluster certain nodes which should be scheduled together.
535 ClusterNodes();
536 // Populate the SUnits array.
537 BuildSchedUnits();
538 // Compute all the scheduling dependencies between nodes.
539 AddSchedEdges();
540}
541
542// Initialize NumNodeDefs for the current Node's opcode.
543void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
544 // Check for phys reg copy.
545 if (!Node)
546 return;
547
548 if (!Node->isMachineOpcode()) {
549 if (Node->getOpcode() == ISD::CopyFromReg)
550 NodeNumDefs = 1;
551 else
552 NodeNumDefs = 0;
553 return;
554 }
555 unsigned POpc = Node->getMachineOpcode();
556 if (POpc == TargetOpcode::IMPLICIT_DEF) {
557 // No register need be allocated for this.
558 NodeNumDefs = 0;
559 return;
560 }
561 if (POpc == TargetOpcode::PATCHPOINT &&
562 Node->getValueType(0) == MVT::Other) {
563 // PATCHPOINT is defined to have one result, but it might really have none
564 // if we're not using CallingConv::AnyReg. Don't mistake the chain for a
565 // real definition.
566 NodeNumDefs = 0;
567 return;
568 }
569 unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
570 // Some instructions define regs that are not represented in the selection DAG
571 // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.
572 NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
573 DefIdx = 0;
574}
575
576// Construct a RegDefIter for this SUnit and find the first valid value.
578 const ScheduleDAGSDNodes *SD)
579 : SchedDAG(SD), Node(SU->getNode()) {
580 InitNodeNumDefs();
581 Advance();
582}
583
584// Advance to the next valid value defined by the SUnit.
586 for (;Node;) { // Visit all glued nodes.
587 for (;DefIdx < NodeNumDefs; ++DefIdx) {
588 if (!Node->hasAnyUseOfValue(DefIdx))
589 continue;
590 ValueType = Node->getSimpleValueType(DefIdx);
591 ++DefIdx;
592 return; // Found a normal regdef.
593 }
594 Node = Node->getGluedNode();
595 if (!Node) {
596 return; // No values left to visit.
597 }
598 InitNodeNumDefs();
599 }
600}
601
603 assert(SU->NumRegDefsLeft == 0 && "expect a new node");
604 for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
605 assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
606 ++SU->NumRegDefsLeft;
607 }
608}
609
611 SDNode *N = SU->getNode();
612
613 // TokenFactor operands are considered zero latency, and some schedulers
614 // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
615 // whenever node latency is nonzero.
616 if (N && N->getOpcode() == ISD::TokenFactor) {
617 SU->Latency = 0;
618 return;
619 }
620
621 // Check to see if the scheduler cares about latencies.
622 if (forceUnitLatencies()) {
623 SU->Latency = 1;
624 return;
625 }
626
627 if (!InstrItins || InstrItins->isEmpty()) {
628 if (N && N->isMachineOpcode() &&
629 TII->isHighLatencyDef(N->getMachineOpcode()))
631 else
632 SU->Latency = 1;
633 return;
634 }
635
636 // Compute the latency for the node. We use the sum of the latencies for
637 // all nodes glued together into this SUnit.
638 SU->Latency = 0;
639 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
640 if (N->isMachineOpcode())
641 SU->Latency += TII->getInstrLatency(InstrItins, N);
642}
643
645 unsigned OpIdx, SDep& dep) const{
646 // Check to see if the scheduler cares about latencies.
647 if (forceUnitLatencies())
648 return;
649
650 if (dep.getKind() != SDep::Data)
651 return;
652
653 unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
654 if (Use->isMachineOpcode())
655 // Adjust the use operand index by num of defs.
656 OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
657 std::optional<unsigned> Latency =
658 TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
659 if (Latency > 1U && Use->getOpcode() == ISD::CopyToReg &&
660 !BB->succ_empty()) {
661 Register Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
662 if (Reg.isVirtual())
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;
667 }
668 if (Latency)
669 dep.setLatency(*Latency);
670}
671
672void 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 = llvm::count(Sequence, nullptr);
725 assert(Sequence.size() - Noops == ScheduledNodes &&
726 "The number of nodes scheduled doesn't match the expected number!");
727}
728#endif // NDEBUG
729
730/// ProcessSDDbgValues - Process SDDbgValues associated with this node.
731static void
733 SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
734 InstrEmitter::VRBaseMapType &VRBaseMap, unsigned Order) {
735 if (!N->getHasDebugValue())
736 return;
737
738 /// Returns true if \p DV has any VReg operand locations which don't exist in
739 /// VRBaseMap.
740 auto HasUnknownVReg = [&VRBaseMap](SDDbgValue *DV) {
741 for (const SDDbgOperand &L : DV->getLocationOps()) {
742 if (L.getKind() == SDDbgOperand::SDNODE &&
743 VRBaseMap.count({L.getSDNode(), L.getResNo()}) == 0)
744 return true;
745 }
746 return false;
747 };
748
749 // Opportunistically insert immediate dbg_value uses, i.e. those with the same
750 // source order number as N.
751 MachineBasicBlock *BB = Emitter.getBlock();
752 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
753 for (auto *DV : DAG->GetDbgValues(N)) {
754 if (DV->isEmitted())
755 continue;
756 unsigned DVOrder = DV->getOrder();
757 if (Order != 0 && DVOrder != Order)
758 continue;
759 // If DV has any VReg location operands which haven't been mapped then
760 // either that node is no longer available or we just haven't visited the
761 // node yet. In the former case we should emit an undef dbg_value, but we
762 // can do it later. And for the latter we'll want to wait until all
763 // dependent nodes have been visited.
764 if (!DV->isInvalidated() && HasUnknownVReg(DV))
765 continue;
766 MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
767 if (!DbgMI)
768 continue;
769 Orders.push_back({DVOrder, DbgMI});
770 BB->insert(InsertPos, DbgMI);
771 }
772}
773
774// ProcessSourceNode - Process nodes with source order numbers. These are added
775// to a vector which EmitSchedule uses to determine how to insert dbg_value
776// instructions in the right order.
777static void
780 SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,
781 SmallSet<Register, 8> &Seen, MachineInstr *NewInsn) {
782 unsigned Order = N->getIROrder();
783 if (!Order || Seen.count(Order)) {
784 // Process any valid SDDbgValues even if node does not have any order
785 // assigned.
786 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
787 return;
788 }
789
790 // If a new instruction was generated for this Order number, record it.
791 // Otherwise, leave this order number unseen: we will either find later
792 // instructions for it, or leave it unseen if there were no instructions at
793 // all.
794 if (NewInsn) {
795 Seen.insert(Order);
796 Orders.push_back({Order, NewInsn});
797 }
798
799 // Even if no instruction was generated, a Value may have become defined via
800 // earlier nodes. Try to process them now.
801 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
802}
803
804void ScheduleDAGSDNodes::
805EmitPhysRegCopy(SUnit *SU, SmallDenseMap<SUnit *, Register, 16> &VRBaseMap,
806 MachineBasicBlock::iterator InsertPos) {
807 for (const SDep &Pred : SU->Preds) {
808 if (Pred.isCtrl())
809 continue; // ignore chain preds
810 if (Pred.getSUnit()->CopyDstRC) {
811 // Copy to physical register.
813 VRBaseMap.find(Pred.getSUnit());
814 assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
815 // Find the destination physical register.
817 for (const SDep &Succ : SU->Succs) {
818 if (Succ.isCtrl())
819 continue; // ignore chain preds
820 if (Succ.getReg()) {
821 Reg = Succ.getReg();
822 break;
823 }
824 }
825 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
826 .addReg(VRI->second);
827 } else {
828 // Copy from physical register.
829 assert(Pred.getReg() && "Unknown physical register!");
830 Register VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
831 bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
832 (void)isNew; // Silence compiler warning.
833 assert(isNew && "Node emitted out of order - early");
834 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
835 .addReg(Pred.getReg());
836 }
837 break;
838 }
839}
840
841/// EmitSchedule - Emit the machine code in scheduled order. Return the new
842/// InsertPos and MachineBasicBlock that contains this insertion
843/// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
844/// not necessarily refer to returned BB. The emitter may split blocks.
847 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
852 bool HasDbg = DAG->hasDebugValues();
853
854 // Emit a node, and determine where its first instruction is for debuginfo.
855 // Zero, one, or multiple instructions can be created when emitting a node.
856 auto EmitNode =
857 [&](SDNode *Node, bool IsClone, bool IsCloned,
859 // Fetch instruction prior to this, or end() if nonexistant.
860 auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
861 if (I == BB->begin())
862 return BB->end();
863 else
864 return std::prev(Emitter.getInsertPos());
865 };
866
867 MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
868 Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
869 MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());
870
871 // If the iterator did not change, no instructions were inserted.
872 if (Before == After)
873 return nullptr;
874
876 if (Before == BB->end()) {
877 // There were no prior instructions; the new ones must start at the
878 // beginning of the block.
879 MI = &Emitter.getBlock()->instr_front();
880 } else {
881 // Return first instruction after the pre-existing instructions.
882 MI = &*std::next(Before);
883 }
884
885 if (MI->isCandidateForAdditionalCallInfo()) {
886 if (DAG->getTarget().Options.EmitCallSiteInfo ||
887 DAG->getTarget().Options.EmitCallGraphSection)
888 MF.addCallSiteInfo(MI, DAG->getCallSiteInfo(Node));
889
890 if (auto CalledGlobal = DAG->getCalledGlobal(Node))
891 if (CalledGlobal->Callee)
892 MF.addCalledGlobal(MI, *CalledGlobal);
893 }
894
895 if (DAG->getNoMergeSiteInfo(Node)) {
897 }
898
899 if (MDNode *MD = DAG->getPCSections(Node))
900 MI->setPCSections(MF, MD);
901
902 // Set MMRAs on _all_ added instructions.
903 if (MDNode *MMRA = DAG->getMMRAMetadata(Node)) {
904 for (MachineBasicBlock::iterator It = MI->getIterator(),
905 End = std::next(After);
906 It != End; ++It)
907 It->setMMRAMetadata(MF, MMRA);
908 }
909
910 return MI;
911 };
912
913 // If this is the first BB, emit byval parameter dbg_value's.
914 if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
915 SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
916 SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
917 for (; PDI != PDE; ++PDI) {
918 MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
919 if (DbgMI) {
920 BB->insert(InsertPos, DbgMI);
921 // We re-emit the dbg_value closer to its use, too, after instructions
922 // are emitted to the BB.
923 (*PDI)->clearIsEmitted();
924 }
925 }
926 }
927
928 for (SUnit *SU : Sequence) {
929 if (!SU) {
930 // Null SUnit* is a noop.
931 TII->insertNoop(*Emitter.getBlock(), InsertPos);
932 continue;
933 }
934
935 // For pre-regalloc scheduling, create instructions corresponding to the
936 // SDNode and any glued SDNodes and append them to the block.
937 if (!SU->getNode()) {
938 // Emit a copy.
939 EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
940 continue;
941 }
942
943 SmallVector<SDNode *, 4> GluedNodes;
944 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
945 GluedNodes.push_back(N);
946 while (!GluedNodes.empty()) {
947 SDNode *N = GluedNodes.back();
948 auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
949 // Remember the source order of the inserted instruction.
950 if (HasDbg)
951 ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
952
953 if (MDNode *MD = DAG->getHeapAllocSite(N))
954 if (NewInsn && NewInsn->isCall())
955 NewInsn->setHeapAllocMarker(MF, MD);
956
957 GluedNodes.pop_back();
958 }
959 auto NewInsn =
960 EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
961 // Remember the source order of the inserted instruction.
962 if (HasDbg)
963 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
964 NewInsn);
965
966 if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {
967 if (NewInsn && NewInsn->isCall())
968 NewInsn->setHeapAllocMarker(MF, MD);
969 }
970 }
971
972 // Insert all the dbg_values which have not already been inserted in source
973 // order sequence.
974 if (HasDbg) {
975 MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
976
977 // Sort the source order instructions and use the order to insert debug
978 // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
979 // regardless of the host's implementation fo std::sort.
980 llvm::stable_sort(Orders, less_first());
981 std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
982 [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
983 return LHS->getOrder() < RHS->getOrder();
984 });
985
986 SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
987 SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
988 // Now emit the rest according to source order.
989 unsigned LastOrder = 0;
990 for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
991 unsigned Order = Orders[i].first;
992 MachineInstr *MI = Orders[i].second;
993 // Insert all SDDbgValue's whose order(s) are before "Order".
994 assert(MI);
995 for (; DI != DE; ++DI) {
996 if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
997 break;
998 if ((*DI)->isEmitted())
999 continue;
1000
1001 MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
1002 if (DbgMI) {
1003 if (!LastOrder)
1004 // Insert to start of the BB (after PHIs).
1005 BB->insert(BBBegin, DbgMI);
1006 else {
1007 // Insert at the instruction, which may be in a different
1008 // block, if the block was split by a custom inserter.
1010 MI->getParent()->insert(Pos, DbgMI);
1011 }
1012 }
1013 }
1014 LastOrder = Order;
1015 }
1016 // Add trailing DbgValue's before the terminator. FIXME: May want to add
1017 // some of them before one or more conditional branches?
1019 for (; DI != DE; ++DI) {
1020 if ((*DI)->isEmitted())
1021 continue;
1022 assert((*DI)->getOrder() >= LastOrder &&
1023 "emitting DBG_VALUE out of order");
1024 if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
1025 DbgMIs.push_back(DbgMI);
1026 }
1027
1028 MachineBasicBlock *InsertBB = Emitter.getBlock();
1030 InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
1031
1032 SDDbgInfo::DbgLabelIterator DLI = DAG->DbgLabelBegin();
1033 SDDbgInfo::DbgLabelIterator DLE = DAG->DbgLabelEnd();
1034 // Now emit the rest according to source order.
1035 LastOrder = 0;
1036 for (const auto &InstrOrder : Orders) {
1037 unsigned Order = InstrOrder.first;
1038 MachineInstr *MI = InstrOrder.second;
1039 if (!MI)
1040 continue;
1041
1042 // Insert all SDDbgLabel's whose order(s) are before "Order".
1043 for (; DLI != DLE &&
1044 (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
1045 ++DLI) {
1046 MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
1047 if (DbgMI) {
1048 if (!LastOrder)
1049 // Insert to start of the BB (after PHIs).
1050 BB->insert(BBBegin, DbgMI);
1051 else {
1052 // Insert at the instruction, which may be in a different
1053 // block, if the block was split by a custom inserter.
1055 MI->getParent()->insert(Pos, DbgMI);
1056 }
1057 }
1058 }
1059 if (DLI == DLE)
1060 break;
1061
1062 LastOrder = Order;
1063 }
1064 }
1065
1066 InsertPos = Emitter.getInsertPos();
1067 // In some cases, DBG_VALUEs might be inserted after the first terminator,
1068 // which results in an invalid MBB. If that happens, move the DBG_VALUEs
1069 // before the first terminator.
1070 MachineBasicBlock *InsertBB = Emitter.getBlock();
1071 auto FirstTerm = InsertBB->getFirstTerminator();
1072 if (FirstTerm != InsertBB->end()) {
1073 assert(!FirstTerm->isDebugValue() &&
1074 "first terminator cannot be a debug value");
1076 make_range(std::next(FirstTerm), InsertBB->end()))) {
1077 // Only scan up to insertion point.
1078 if (&MI == InsertPos)
1079 break;
1080
1081 if (!MI.isDebugValue())
1082 continue;
1083
1084 // The DBG_VALUE was referencing a value produced by a terminator. By
1085 // moving the DBG_VALUE, the referenced value also needs invalidating.
1086 MI.getOperand(0).ChangeToRegister(0, false);
1087 MI.moveBefore(&*FirstTerm);
1088 }
1089 }
1090 return InsertBB;
1091}
1092
1093/// Return the basic block label.
1095 return "sunit-dag." + BB->getFullName();
1096}
return SDValue()
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
dxil DXContainer Global Emitter
This file defines the DenseMap class.
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
#define I(x, y, z)
Definition MD5.cpp:58
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
MachineInstr unsigned OpIdx
uint64_t IntrinsicInst * II
static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, InstrEmitter::VRBaseMapType &VRBaseMap, SmallVectorImpl< std::pair< unsigned, MachineInstr * > > &Orders, SmallSet< Register, 8 > &Seen, MachineInstr *NewInsn)
static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG)
static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG)
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"))
static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, MCRegister &PhysReg, int &Cost)
CheckForPhysRegDependency - Check if the dependency between def and use of a specified operand is a p...
static void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, SmallVectorImpl< std::pair< unsigned, MachineInstr * > > &Orders, InstrEmitter::VRBaseMapType &VRBaseMap, unsigned Order)
ProcessSDDbgValues - Process SDDbgValues associated with this node.
static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef< EVT > VTs, SDValue ExtraOper=SDValue())
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
This file describes how to lower LLVM code to machine code.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:41
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:167
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition DenseMap.h:74
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:163
iterator end()
Definition DenseMap.h:81
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:222
SmallDenseMap< SDValue, Register, 16 > VRBaseMapType
static unsigned CountResults(SDNode *Node)
CountResults - The results of target nodes have register or immediate operands first,...
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
bool mayLoad() const
Return true if this instruction could possibly read memory.
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specified operand constraint if it is present.
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
Wrapper class representing physical registers. Should be passed by value.
Definition MCRegister.h:33
Metadata node.
Definition Metadata.h:1078
LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
MachineInstrBundleIterator< MachineInstr > iterator
BasicBlockListType::iterator iterator
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
An SDNode that represents everything that will be needed to construct a MachineInstr.
mmo_iterator memoperands_begin() const
mmo_iterator memoperands_end() const
Wrapper class representing virtual and physical registers.
Definition Register.h:19
SmallVectorImpl< SDDbgLabel * >::iterator DbgLabelIterator
SmallVectorImpl< SDDbgValue * >::iterator DbgIterator
Holds the information for a single machine location through SDISel; either an SDNode,...
@ SDNODE
Value is the result of an expression.
Holds the information from a dbg_value node through SDISel.
Represents one node in the SelectionDAG.
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.
int getNodeId() const
Return the unique node id.
LLVM_ABI void dump() const
Dump this node, for debugging.
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
iterator_range< value_op_iterator > op_values() const
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
static user_iterator user_end()
user_iterator user_begin() const
Provide iteration support to walk over all users of an SDNode.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
SDNode * getNode() const
get the SDNode which holds the desired result
unsigned getResNo() const
get the index which selects a specific result in the SDNode
Scheduling dependency.
Definition ScheduleDAG.h:51
SUnit * getSUnit() const
Kind getKind() const
Returns an enum value representing the kind of the dependence.
@ Data
Regular data dependence (aka true-dependence).
Definition ScheduleDAG.h:55
void setLatency(unsigned Lat)
Sets the latency for this edge.
@ Barrier
An unknown scheduling barrier.
Definition ScheduleDAG.h:71
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Register getReg() const
Returns the register associated with this edge.
Scheduling unit. This is a node in the scheduling DAG.
bool isCloned
True if this node has been cloned.
bool isCall
Is a function call.
void setNode(SDNode *N)
Assigns the representative SDNode for this SUnit.
unsigned NodeNum
Entry # of node in the node vector.
bool hasPhysRegClobbers
Has any physreg defs, used or not.
bool isCallOp
Is a function call operand.
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
unsigned short Latency
Node latency.
unsigned short NumRegDefsLeft
bool isScheduleHigh
True if preferable to schedule high.
bool isScheduleLow
True if preferable to schedule low.
bool hasPhysRegDefs
Has physreg defs that are being used.
SmallVector< SDep, 4 > Succs
All sunit successors.
Sched::Preference SchedulingPref
Scheduling preference.
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
bool isTwoAddress
Is a two-address instruction.
bool isCommutable
Is a commutable instruction.
bool isVRegCycle
May use and def the same vreg.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
SUnit * OrigNode
If not this, the node from which this node was cloned.
LLVM_ABI bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
RegDefIter - In place iteration over the values defined by an SUnit.
RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD)
SUnit * newSUnit(SDNode *N)
NewSUnit - Creates a new SUnit and return a ptr to it.
void VerifyScheduledSequence(bool isBottomUp)
VerifyScheduledSequence - Verify that all SUnits are scheduled and consistent with the Sequence of sc...
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
virtual void computeLatency(SUnit *SU)
computeLatency - Compute node latency.
std::string getDAGName() const override
Return the basic block label.
virtual MachineBasicBlock * EmitSchedule(MachineBasicBlock::iterator &InsertPos)
EmitSchedule - Insert MachineInstrs into the MachineBasicBlock according to the order specified in Se...
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one.
static bool isPassiveNode(SDNode *Node)
isPassiveNode - Return true if the node is a non-scheduled leaf.
const InstrItineraryData * InstrItins
void InitNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
std::vector< SUnit * > Sequence
The schedule. Null SUnit*'s represent noop instructions.
void Run(SelectionDAG *dag, MachineBasicBlock *bb)
Run - perform scheduling.
void BuildSchedGraph()
BuildSchedGraph - Build the SUnit graph from the selection dag that we are input.
void dumpNode(const SUnit &SU) const override
SUnit * Clone(SUnit *Old)
Clone - Creates a clone of the specified SUnit.
ScheduleDAGSDNodes(MachineFunction &mf)
virtual void computeOperandLatency(SDNode *Def, SDNode *Use, unsigned OpIdx, SDep &dep) const
MachineRegisterInfo & MRI
Virtual/real register map.
void clearDAG()
Clears the DAG state (between regions).
const TargetInstrInfo * TII
Target instruction information.
std::vector< SUnit > SUnits
The scheduling units.
const TargetRegisterInfo * TRI
Target processor register info.
SUnit EntrySU
Special node for the region entry.
MachineFunction & MF
Machine function.
ScheduleDAG(const ScheduleDAG &)=delete
void dumpNodeAll(const SUnit &SU) const
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
void dumpNodeName(const SUnit &SU) const
SUnit ExitSU
Special node for the region exit.
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
LLVM_ABI SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
LLVM_ABI 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.
LLVM_ABI void setNodeMemRefs(MachineSDNode *N, ArrayRef< MachineMemOperand * > NewMemRefs)
Mutate the specified machine node's memory references to the provided list.
ArrayRef< SDDbgValue * > GetDbgValues(const SDNode *SD) const
Get the debug values which reference the given SDNode.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition SmallSet.h:133
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition SmallSet.h:175
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition SmallSet.h:183
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
Sched::Preference getSchedulingPreference() const
Return target scheduling preference.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
uint8_t getCopyCost() const
Return the cost of copying a value between two registers in this class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
Value * getOperand(unsigned i) const
Definition User.h:232
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
Definition ISDOpcodes.h:225
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
Definition ISDOpcodes.h:219
@ TokenFactor
TokenFactor - This node takes multiple tokens as input and produces a single token result.
Definition ISDOpcodes.h:53
Offsets
Offsets in bytes from the start of the input buffer.
initializer< Ty > init(const Ty &Val)
@ User
could "use" a pointer
NodeAddr< NodeBase * > Node
Definition RDFGraph.h:381
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:477
void stable_sort(R &&Range)
Definition STLExtras.h:2058
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
InstructionCost Cost
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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:632
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1622
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
FunctionAddr VTableAddr uintptr_t uintptr_t Data
Definition InstrProf.h:189
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition STLExtras.h:1954
DWARFExpression::Operation Op
ArrayRef(const T &OneElt) -> ArrayRef< T >
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
#define N
This represents a list of ValueType's that has been intern'd by a SelectionDAG.
Function object to check whether the first component of a container supported by std::get (like std::...
Definition STLExtras.h:1425