LLVM 19.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();
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 const TargetLowering &TLI,
115 unsigned &PhysReg, int &Cost) {
116 if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
117 return;
118
119 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
120 if (TLI.checkForPhysRegDependency(Def, User, Op, TRI, TII, PhysReg, Cost))
121 return;
122
124 return;
125
126 unsigned ResNo = User->getOperand(2).getResNo();
127 if (Def->getOpcode() == ISD::CopyFromReg &&
128 cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {
129 PhysReg = Reg;
130 } else if (Def->isMachineOpcode()) {
131 const MCInstrDesc &II = TII->get(Def->getMachineOpcode());
132 if (ResNo >= II.getNumDefs() && II.hasImplicitDefOfPhysReg(Reg))
133 PhysReg = Reg;
134 }
135
136 if (PhysReg != 0) {
137 const TargetRegisterClass *RC =
138 TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
139 Cost = RC->getCopyCost();
140 }
141}
142
143// Helper for AddGlue to clone node operands.
145 SDValue ExtraOper = SDValue()) {
146 SmallVector<SDValue, 8> Ops(N->op_begin(), N->op_end());
147 if (ExtraOper.getNode())
148 Ops.push_back(ExtraOper);
149
150 SDVTList VTList = DAG->getVTList(VTs);
151 MachineSDNode *MN = dyn_cast<MachineSDNode>(N);
152
153 // Store memory references.
155 if (MN)
156 MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());
157
158 DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
159
160 // Reset the memory references
161 if (MN)
162 DAG->setNodeMemRefs(MN, MMOs);
163}
164
165static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) {
166 SDNode *GlueDestNode = Glue.getNode();
167
168 // Don't add glue from a node to itself.
169 if (GlueDestNode == N) return false;
170
171 // Don't add a glue operand to something that already uses glue.
172 if (GlueDestNode &&
173 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
174 return false;
175 }
176 // Don't add glue to something that already has a glue value.
177 if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;
178
179 SmallVector<EVT, 4> VTs(N->values());
180 if (AddGlue)
181 VTs.push_back(MVT::Glue);
182
183 CloneNodeWithValues(N, DAG, VTs, Glue);
184
185 return true;
186}
187
188// Cleanup after unsuccessful AddGlue. Use the standard method of morphing the
189// node even though simply shrinking the value list is sufficient.
191 assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
192 !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
193 "expected an unused glue value");
194
196 ArrayRef(N->value_begin(), N->getNumValues() - 1));
197}
198
199/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.
200/// This function finds loads of the same base and different offsets. If the
201/// offsets are not far apart (target specific), it add MVT::Glue inputs and
202/// outputs to ensure they are scheduled together and in order. This
203/// optimization may benefit some targets by improving cache locality.
204void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
205 SDValue Chain;
206 unsigned NumOps = Node->getNumOperands();
207 if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
208 Chain = Node->getOperand(NumOps-1);
209 if (!Chain)
210 return;
211
212 // Skip any load instruction that has a tied input. There may be an additional
213 // dependency requiring a different order than by increasing offsets, and the
214 // added glue may introduce a cycle.
215 auto hasTiedInput = [this](const SDNode *N) {
216 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
217 for (unsigned I = 0; I != MCID.getNumOperands(); ++I) {
218 if (MCID.getOperandConstraint(I, MCOI::TIED_TO) != -1)
219 return true;
220 }
221
222 return false;
223 };
224
225 // Look for other loads of the same chain. Find loads that are loading from
226 // the same base pointer and different offsets.
229 DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode.
230 bool Cluster = false;
231 SDNode *Base = Node;
232
233 if (hasTiedInput(Base))
234 return;
235
236 // This algorithm requires a reasonably low use count before finding a match
237 // to avoid uselessly blowing up compile time in large blocks.
238 unsigned UseCount = 0;
239 for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
240 I != E && UseCount < 100; ++I, ++UseCount) {
241 if (I.getUse().getResNo() != Chain.getResNo())
242 continue;
243
244 SDNode *User = *I;
245 if (User == Node || !Visited.insert(User).second)
246 continue;
247 int64_t Offset1, Offset2;
248 if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
249 Offset1 == Offset2 ||
250 hasTiedInput(User)) {
251 // FIXME: Should be ok if they addresses are identical. But earlier
252 // optimizations really should have eliminated one of the loads.
253 continue;
254 }
255 if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
256 Offsets.push_back(Offset1);
257 O2SMap.insert(std::make_pair(Offset2, User));
258 Offsets.push_back(Offset2);
259 if (Offset2 < Offset1)
260 Base = User;
261 Cluster = true;
262 // Reset UseCount to allow more matches.
263 UseCount = 0;
264 }
265
266 if (!Cluster)
267 return;
268
269 // Sort them in increasing order.
270 llvm::sort(Offsets);
271
272 // Check if the loads are close enough.
274 unsigned NumLoads = 0;
275 int64_t BaseOff = Offsets[0];
276 SDNode *BaseLoad = O2SMap[BaseOff];
277 Loads.push_back(BaseLoad);
278 for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
279 int64_t Offset = Offsets[i];
280 SDNode *Load = O2SMap[Offset];
281 if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
282 break; // Stop right here. Ignore loads that are further away.
283 Loads.push_back(Load);
284 ++NumLoads;
285 }
286
287 if (NumLoads == 0)
288 return;
289
290 // Cluster loads by adding MVT::Glue outputs and inputs. This also
291 // ensure they are scheduled in order of increasing addresses.
292 SDNode *Lead = Loads[0];
293 SDValue InGlue;
294 if (AddGlue(Lead, InGlue, true, DAG))
295 InGlue = SDValue(Lead, Lead->getNumValues() - 1);
296 for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
297 bool OutGlue = I < E - 1;
298 SDNode *Load = Loads[I];
299
300 // If AddGlue fails, we could leave an unsused glue value. This should not
301 // cause any
302 if (AddGlue(Load, InGlue, OutGlue, DAG)) {
303 if (OutGlue)
304 InGlue = SDValue(Load, Load->getNumValues() - 1);
305
306 ++LoadsClustered;
307 }
308 else if (!OutGlue && InGlue.getNode())
309 RemoveUnusedGlue(InGlue.getNode(), DAG);
310 }
311}
312
313/// ClusterNodes - Cluster certain nodes which should be scheduled together.
314///
315void ScheduleDAGSDNodes::ClusterNodes() {
316 for (SDNode &NI : DAG->allnodes()) {
317 SDNode *Node = &NI;
318 if (!Node || !Node->isMachineOpcode())
319 continue;
320
321 unsigned Opc = Node->getMachineOpcode();
322 const MCInstrDesc &MCID = TII->get(Opc);
323 if (MCID.mayLoad())
324 // Cluster loads from "near" addresses into combined SUnits.
325 ClusterNeighboringLoads(Node);
326 }
327}
328
329void ScheduleDAGSDNodes::BuildSchedUnits() {
330 // During scheduling, the NodeId field of SDNode is used to map SDNodes
331 // to their associated SUnits by holding SUnits table indices. A value
332 // of -1 means the SDNode does not yet have an associated SUnit.
333 unsigned NumNodes = 0;
334 for (SDNode &NI : DAG->allnodes()) {
335 NI.setNodeId(-1);
336 ++NumNodes;
337 }
338
339 // Reserve entries in the vector for each of the SUnits we are creating. This
340 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
341 // invalidated.
342 // FIXME: Multiply by 2 because we may clone nodes during scheduling.
343 // This is a temporary workaround.
344 SUnits.reserve(NumNodes * 2);
345
346 // Add all nodes in depth first order.
349 Worklist.push_back(DAG->getRoot().getNode());
350 Visited.insert(DAG->getRoot().getNode());
351
352 SmallVector<SUnit*, 8> CallSUnits;
353 while (!Worklist.empty()) {
354 SDNode *NI = Worklist.pop_back_val();
355
356 // Add all operands to the worklist unless they've already been added.
357 for (const SDValue &Op : NI->op_values())
358 if (Visited.insert(Op.getNode()).second)
359 Worklist.push_back(Op.getNode());
360
361 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
362 continue;
363
364 // If this node has already been processed, stop now.
365 if (NI->getNodeId() != -1) continue;
366
367 SUnit *NodeSUnit = newSUnit(NI);
368
369 // See if anything is glued to this node, if so, add them to glued
370 // nodes. Nodes can have at most one glue input and one glue output. Glue
371 // is required to be the last operand and result of a node.
372
373 // Scan up to find glued preds.
374 SDNode *N = NI;
375 while (N->getNumOperands() &&
376 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
377 N = N->getOperand(N->getNumOperands()-1).getNode();
378 assert(N->getNodeId() == -1 && "Node already inserted!");
379 N->setNodeId(NodeSUnit->NodeNum);
380 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
381 NodeSUnit->isCall = true;
382 }
383
384 // Scan down to find any glued succs.
385 N = NI;
386 while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {
387 SDValue GlueVal(N, N->getNumValues()-1);
388
389 // There are either zero or one users of the Glue result.
390 bool HasGlueUse = false;
391 for (SDNode *U : N->uses())
392 if (GlueVal.isOperandOf(U)) {
393 HasGlueUse = true;
394 assert(N->getNodeId() == -1 && "Node already inserted!");
395 N->setNodeId(NodeSUnit->NodeNum);
396 N = U;
397 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
398 NodeSUnit->isCall = true;
399 break;
400 }
401 if (!HasGlueUse) break;
402 }
403
404 if (NodeSUnit->isCall)
405 CallSUnits.push_back(NodeSUnit);
406
407 // Schedule zero-latency TokenFactor below any nodes that may increase the
408 // schedule height. Otherwise, ancestors of the TokenFactor may appear to
409 // have false stalls.
410 if (NI->getOpcode() == ISD::TokenFactor)
411 NodeSUnit->isScheduleLow = true;
412
413 // If there are glue operands involved, N is now the bottom-most node
414 // of the sequence of nodes that are glued together.
415 // Update the SUnit.
416 NodeSUnit->setNode(N);
417 assert(N->getNodeId() == -1 && "Node already inserted!");
418 N->setNodeId(NodeSUnit->NodeNum);
419
420 // Compute NumRegDefsLeft. This must be done before AddSchedEdges.
421 InitNumRegDefsLeft(NodeSUnit);
422
423 // Assign the Latency field of NodeSUnit using target-provided information.
424 computeLatency(NodeSUnit);
425 }
426
427 // Find all call operands.
428 while (!CallSUnits.empty()) {
429 SUnit *SU = CallSUnits.pop_back_val();
430 for (const SDNode *SUNode = SU->getNode(); SUNode;
431 SUNode = SUNode->getGluedNode()) {
432 if (SUNode->getOpcode() != ISD::CopyToReg)
433 continue;
434 SDNode *SrcN = SUNode->getOperand(2).getNode();
435 if (isPassiveNode(SrcN)) continue; // Not scheduled.
436 SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
437 SrcSU->isCallOp = true;
438 }
439 }
440}
441
442void ScheduleDAGSDNodes::AddSchedEdges() {
444
445 // Check to see if the scheduler cares about latencies.
446 bool UnitLatencies = forceUnitLatencies();
447
448 // Pass 2: add the preds, succs, etc.
449 for (SUnit &SU : SUnits) {
450 SDNode *MainNode = SU.getNode();
451
452 if (MainNode->isMachineOpcode()) {
453 unsigned Opc = MainNode->getMachineOpcode();
454 const MCInstrDesc &MCID = TII->get(Opc);
455 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
456 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
457 SU.isTwoAddress = true;
458 break;
459 }
460 }
461 if (MCID.isCommutable())
462 SU.isCommutable = true;
463 }
464
465 // Find all predecessors and successors of the group.
466 for (SDNode *N = SU.getNode(); N; N = N->getGluedNode()) {
467 if (N->isMachineOpcode() &&
468 !TII->get(N->getMachineOpcode()).implicit_defs().empty()) {
469 SU.hasPhysRegClobbers = true;
470 unsigned NumUsed = InstrEmitter::CountResults(N);
471 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
472 --NumUsed; // Skip over unused values at the end.
473 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
474 SU.hasPhysRegDefs = true;
475 }
476
477 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
478 SDNode *OpN = N->getOperand(i).getNode();
479 unsigned DefIdx = N->getOperand(i).getResNo();
480 if (isPassiveNode(OpN)) continue; // Not scheduled.
481 SUnit *OpSU = &SUnits[OpN->getNodeId()];
482 assert(OpSU && "Node has no SUnit!");
483 if (OpSU == &SU)
484 continue; // In the same group.
485
486 EVT OpVT = N->getOperand(i).getValueType();
487 assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
488 bool isChain = OpVT == MVT::Other;
489
490 unsigned PhysReg = 0;
491 int Cost = 1;
492 // Determine if this is a physical register dependency.
494 CheckForPhysRegDependency(OpN, N, i, TRI, TII, TLI, PhysReg, Cost);
495 assert((PhysReg == 0 || !isChain) &&
496 "Chain dependence via physreg data?");
497 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
498 // emits a copy from the physical register to a virtual register unless
499 // it requires a cross class copy (cost < 0). That means we are only
500 // treating "expensive to copy" register dependency as physical register
501 // dependency. This may change in the future though.
502 if (Cost >= 0 && !StressSched)
503 PhysReg = 0;
504
505 // If this is a ctrl dep, latency is 1.
506 unsigned OpLatency = isChain ? 1 : OpSU->Latency;
507 // Special-case TokenFactor chains as zero-latency.
508 if(isChain && OpN->getOpcode() == ISD::TokenFactor)
509 OpLatency = 0;
510
511 SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
512 : SDep(OpSU, SDep::Data, PhysReg);
513 Dep.setLatency(OpLatency);
514 if (!isChain && !UnitLatencies) {
515 computeOperandLatency(OpN, N, i, Dep);
516 ST.adjustSchedDependency(OpSU, DefIdx, &SU, i, Dep, nullptr);
517 }
518
519 if (!SU.addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
520 // Multiple register uses are combined in the same SUnit. For example,
521 // we could have a set of glued nodes with all their defs consumed by
522 // another set of glued nodes. Register pressure tracking sees this as
523 // a single use, so to keep pressure balanced we reduce the defs.
524 //
525 // We can't tell (without more book-keeping) if this results from
526 // glued nodes or duplicate operands. As long as we don't reduce
527 // NumRegDefsLeft to zero, we handle the common cases well.
528 --OpSU->NumRegDefsLeft;
529 }
530 }
531 }
532 }
533}
534
535/// BuildSchedGraph - Build the SUnit graph from the selection dag that we
536/// are input. This SUnit graph is similar to the SelectionDAG, but
537/// excludes nodes that aren't interesting to scheduling, and represents
538/// glued together nodes with a single SUnit.
540 // Cluster certain nodes which should be scheduled together.
541 ClusterNodes();
542 // Populate the SUnits array.
543 BuildSchedUnits();
544 // Compute all the scheduling dependencies between nodes.
545 AddSchedEdges();
546}
547
548// Initialize NumNodeDefs for the current Node's opcode.
549void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
550 // Check for phys reg copy.
551 if (!Node)
552 return;
553
554 if (!Node->isMachineOpcode()) {
555 if (Node->getOpcode() == ISD::CopyFromReg)
556 NodeNumDefs = 1;
557 else
558 NodeNumDefs = 0;
559 return;
560 }
561 unsigned POpc = Node->getMachineOpcode();
562 if (POpc == TargetOpcode::IMPLICIT_DEF) {
563 // No register need be allocated for this.
564 NodeNumDefs = 0;
565 return;
566 }
567 if (POpc == TargetOpcode::PATCHPOINT &&
568 Node->getValueType(0) == MVT::Other) {
569 // PATCHPOINT is defined to have one result, but it might really have none
570 // if we're not using CallingConv::AnyReg. Don't mistake the chain for a
571 // real definition.
572 NodeNumDefs = 0;
573 return;
574 }
575 unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
576 // Some instructions define regs that are not represented in the selection DAG
577 // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.
578 NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
579 DefIdx = 0;
580}
581
582// Construct a RegDefIter for this SUnit and find the first valid value.
584 const ScheduleDAGSDNodes *SD)
585 : SchedDAG(SD), Node(SU->getNode()) {
586 InitNodeNumDefs();
587 Advance();
588}
589
590// Advance to the next valid value defined by the SUnit.
592 for (;Node;) { // Visit all glued nodes.
593 for (;DefIdx < NodeNumDefs; ++DefIdx) {
594 if (!Node->hasAnyUseOfValue(DefIdx))
595 continue;
596 ValueType = Node->getSimpleValueType(DefIdx);
597 ++DefIdx;
598 return; // Found a normal regdef.
599 }
600 Node = Node->getGluedNode();
601 if (!Node) {
602 return; // No values left to visit.
603 }
604 InitNodeNumDefs();
605 }
606}
607
609 assert(SU->NumRegDefsLeft == 0 && "expect a new node");
610 for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
611 assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
612 ++SU->NumRegDefsLeft;
613 }
614}
615
617 SDNode *N = SU->getNode();
618
619 // TokenFactor operands are considered zero latency, and some schedulers
620 // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
621 // whenever node latency is nonzero.
622 if (N && N->getOpcode() == ISD::TokenFactor) {
623 SU->Latency = 0;
624 return;
625 }
626
627 // Check to see if the scheduler cares about latencies.
628 if (forceUnitLatencies()) {
629 SU->Latency = 1;
630 return;
631 }
632
633 if (!InstrItins || InstrItins->isEmpty()) {
634 if (N && N->isMachineOpcode() &&
635 TII->isHighLatencyDef(N->getMachineOpcode()))
637 else
638 SU->Latency = 1;
639 return;
640 }
641
642 // Compute the latency for the node. We use the sum of the latencies for
643 // all nodes glued together into this SUnit.
644 SU->Latency = 0;
645 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
646 if (N->isMachineOpcode())
648}
649
651 unsigned OpIdx, SDep& dep) const{
652 // Check to see if the scheduler cares about latencies.
653 if (forceUnitLatencies())
654 return;
655
656 if (dep.getKind() != SDep::Data)
657 return;
658
659 unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
660 if (Use->isMachineOpcode())
661 // Adjust the use operand index by num of defs.
662 OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
663 std::optional<unsigned> Latency =
664 TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
665 if (Latency > 1U && Use->getOpcode() == ISD::CopyToReg &&
666 !BB->succ_empty()) {
667 unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
669 // This copy is a liveout value. It is likely coalesced, so reduce the
670 // latency so not to penalize the def.
671 // FIXME: need target specific adjustment here?
672 Latency = *Latency - 1;
673 }
674 if (Latency)
675 dep.setLatency(*Latency);
676}
677
678void ScheduleDAGSDNodes::dumpNode(const SUnit &SU) const {
679#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
680 dumpNodeName(SU);
681 dbgs() << ": ";
682
683 if (!SU.getNode()) {
684 dbgs() << "PHYS REG COPY\n";
685 return;
686 }
687
688 SU.getNode()->dump(DAG);
689 dbgs() << "\n";
690 SmallVector<SDNode *, 4> GluedNodes;
691 for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())
692 GluedNodes.push_back(N);
693 while (!GluedNodes.empty()) {
694 dbgs() << " ";
695 GluedNodes.back()->dump(DAG);
696 dbgs() << "\n";
697 GluedNodes.pop_back();
698 }
699#endif
700}
701
703#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
704 if (EntrySU.getNode() != nullptr)
706 for (const SUnit &SU : SUnits)
707 dumpNodeAll(SU);
708 if (ExitSU.getNode() != nullptr)
710#endif
711}
712
713#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
715 for (const SUnit *SU : Sequence) {
716 if (SU)
717 dumpNode(*SU);
718 else
719 dbgs() << "**** NOOP ****\n";
720 }
721}
722#endif
723
724#ifndef NDEBUG
725/// VerifyScheduledSequence - Verify that all SUnits were scheduled and that
726/// their state is consistent with the nodes listed in Sequence.
727///
729 unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);
730 unsigned Noops = llvm::count(Sequence, nullptr);
731 assert(Sequence.size() - Noops == ScheduledNodes &&
732 "The number of nodes scheduled doesn't match the expected number!");
733}
734#endif // NDEBUG
735
736/// ProcessSDDbgValues - Process SDDbgValues associated with this node.
737static void
739 SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
740 DenseMap<SDValue, Register> &VRBaseMap, unsigned Order) {
741 if (!N->getHasDebugValue())
742 return;
743
744 /// Returns true if \p DV has any VReg operand locations which don't exist in
745 /// VRBaseMap.
746 auto HasUnknownVReg = [&VRBaseMap](SDDbgValue *DV) {
747 for (const SDDbgOperand &L : DV->getLocationOps()) {
748 if (L.getKind() == SDDbgOperand::SDNODE &&
749 VRBaseMap.count({L.getSDNode(), L.getResNo()}) == 0)
750 return true;
751 }
752 return false;
753 };
754
755 // Opportunistically insert immediate dbg_value uses, i.e. those with the same
756 // source order number as N.
757 MachineBasicBlock *BB = Emitter.getBlock();
758 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
759 for (auto *DV : DAG->GetDbgValues(N)) {
760 if (DV->isEmitted())
761 continue;
762 unsigned DVOrder = DV->getOrder();
763 if (Order != 0 && DVOrder != Order)
764 continue;
765 // If DV has any VReg location operands which haven't been mapped then
766 // either that node is no longer available or we just haven't visited the
767 // node yet. In the former case we should emit an undef dbg_value, but we
768 // can do it later. And for the latter we'll want to wait until all
769 // dependent nodes have been visited.
770 if (!DV->isInvalidated() && HasUnknownVReg(DV))
771 continue;
772 MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
773 if (!DbgMI)
774 continue;
775 Orders.push_back({DVOrder, DbgMI});
776 BB->insert(InsertPos, DbgMI);
777 }
778}
779
780// ProcessSourceNode - Process nodes with source order numbers. These are added
781// to a vector which EmitSchedule uses to determine how to insert dbg_value
782// instructions in the right order.
783static void
786 SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,
787 SmallSet<Register, 8> &Seen, MachineInstr *NewInsn) {
788 unsigned Order = N->getIROrder();
789 if (!Order || Seen.count(Order)) {
790 // Process any valid SDDbgValues even if node does not have any order
791 // assigned.
792 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
793 return;
794 }
795
796 // If a new instruction was generated for this Order number, record it.
797 // Otherwise, leave this order number unseen: we will either find later
798 // instructions for it, or leave it unseen if there were no instructions at
799 // all.
800 if (NewInsn) {
801 Seen.insert(Order);
802 Orders.push_back({Order, NewInsn});
803 }
804
805 // Even if no instruction was generated, a Value may have become defined via
806 // earlier nodes. Try to process them now.
807 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
808}
809
810void ScheduleDAGSDNodes::
811EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, Register> &VRBaseMap,
812 MachineBasicBlock::iterator InsertPos) {
813 for (const SDep &Pred : SU->Preds) {
814 if (Pred.isCtrl())
815 continue; // ignore chain preds
816 if (Pred.getSUnit()->CopyDstRC) {
817 // Copy to physical register.
819 VRBaseMap.find(Pred.getSUnit());
820 assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
821 // Find the destination physical register.
823 for (const SDep &Succ : SU->Succs) {
824 if (Succ.isCtrl())
825 continue; // ignore chain preds
826 if (Succ.getReg()) {
827 Reg = Succ.getReg();
828 break;
829 }
830 }
831 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
832 .addReg(VRI->second);
833 } else {
834 // Copy from physical register.
835 assert(Pred.getReg() && "Unknown physical register!");
837 bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
838 (void)isNew; // Silence compiler warning.
839 assert(isNew && "Node emitted out of order - early");
840 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
841 .addReg(Pred.getReg());
842 }
843 break;
844 }
845}
846
847/// EmitSchedule - Emit the machine code in scheduled order. Return the new
848/// InsertPos and MachineBasicBlock that contains this insertion
849/// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
850/// not necessarily refer to returned BB. The emitter may split blocks.
853 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
855 DenseMap<SUnit*, Register> CopyVRBaseMap;
858 bool HasDbg = DAG->hasDebugValues();
859
860 // Emit a node, and determine where its first instruction is for debuginfo.
861 // Zero, one, or multiple instructions can be created when emitting a node.
862 auto EmitNode =
863 [&](SDNode *Node, bool IsClone, bool IsCloned,
865 // Fetch instruction prior to this, or end() if nonexistant.
866 auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
867 if (I == BB->begin())
868 return BB->end();
869 else
870 return std::prev(Emitter.getInsertPos());
871 };
872
873 MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
874 Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
875 MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());
876
877 // If the iterator did not change, no instructions were inserted.
878 if (Before == After)
879 return nullptr;
880
882 if (Before == BB->end()) {
883 // There were no prior instructions; the new ones must start at the
884 // beginning of the block.
885 MI = &Emitter.getBlock()->instr_front();
886 } else {
887 // Return first instruction after the pre-existing instructions.
888 MI = &*std::next(Before);
889 }
890
891 if (MI->isCandidateForCallSiteEntry() &&
894 }
895
896 if (DAG->getNoMergeSiteInfo(Node)) {
898 }
899
900 if (MDNode *MD = DAG->getPCSections(Node))
901 MI->setPCSections(MF, MD);
902
903 // Set MMRAs on _all_ added instructions.
904 if (MDNode *MMRA = DAG->getMMRAMetadata(Node)) {
905 for (MachineBasicBlock::iterator It = MI->getIterator(),
906 End = std::next(After);
907 It != End; ++It)
908 It->setMMRAMetadata(MF, MMRA);
909 }
910
911 return MI;
912 };
913
914 // If this is the first BB, emit byval parameter dbg_value's.
915 if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
918 for (; PDI != PDE; ++PDI) {
919 MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
920 if (DbgMI) {
921 BB->insert(InsertPos, DbgMI);
922 // We re-emit the dbg_value closer to its use, too, after instructions
923 // are emitted to the BB.
924 (*PDI)->clearIsEmitted();
925 }
926 }
927 }
928
929 for (SUnit *SU : Sequence) {
930 if (!SU) {
931 // Null SUnit* is a noop.
932 TII->insertNoop(*Emitter.getBlock(), InsertPos);
933 continue;
934 }
935
936 // For pre-regalloc scheduling, create instructions corresponding to the
937 // SDNode and any glued SDNodes and append them to the block.
938 if (!SU->getNode()) {
939 // Emit a copy.
940 EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
941 continue;
942 }
943
944 SmallVector<SDNode *, 4> GluedNodes;
945 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
946 GluedNodes.push_back(N);
947 while (!GluedNodes.empty()) {
948 SDNode *N = GluedNodes.back();
949 auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
950 // Remember the source order of the inserted instruction.
951 if (HasDbg)
952 ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
953
954 if (MDNode *MD = DAG->getHeapAllocSite(N))
955 if (NewInsn && NewInsn->isCall())
956 NewInsn->setHeapAllocMarker(MF, MD);
957
958 GluedNodes.pop_back();
959 }
960 auto NewInsn =
961 EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
962 // Remember the source order of the inserted instruction.
963 if (HasDbg)
964 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
965 NewInsn);
966
967 if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {
968 if (NewInsn && NewInsn->isCall())
969 NewInsn->setHeapAllocMarker(MF, MD);
970 }
971 }
972
973 // Insert all the dbg_values which have not already been inserted in source
974 // order sequence.
975 if (HasDbg) {
977
978 // Sort the source order instructions and use the order to insert debug
979 // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
980 // regardless of the host's implementation fo std::sort.
981 llvm::stable_sort(Orders, less_first());
982 std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
983 [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
984 return LHS->getOrder() < RHS->getOrder();
985 });
986
989 // Now emit the rest according to source order.
990 unsigned LastOrder = 0;
991 for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
992 unsigned Order = Orders[i].first;
993 MachineInstr *MI = Orders[i].second;
994 // Insert all SDDbgValue's whose order(s) are before "Order".
995 assert(MI);
996 for (; DI != DE; ++DI) {
997 if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
998 break;
999 if ((*DI)->isEmitted())
1000 continue;
1001
1002 MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
1003 if (DbgMI) {
1004 if (!LastOrder)
1005 // Insert to start of the BB (after PHIs).
1006 BB->insert(BBBegin, DbgMI);
1007 else {
1008 // Insert at the instruction, which may be in a different
1009 // block, if the block was split by a custom inserter.
1011 MI->getParent()->insert(Pos, DbgMI);
1012 }
1013 }
1014 }
1015 LastOrder = Order;
1016 }
1017 // Add trailing DbgValue's before the terminator. FIXME: May want to add
1018 // some of them before one or more conditional branches?
1020 for (; DI != DE; ++DI) {
1021 if ((*DI)->isEmitted())
1022 continue;
1023 assert((*DI)->getOrder() >= LastOrder &&
1024 "emitting DBG_VALUE out of order");
1025 if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
1026 DbgMIs.push_back(DbgMI);
1027 }
1028
1029 MachineBasicBlock *InsertBB = Emitter.getBlock();
1031 InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
1032
1035 // Now emit the rest according to source order.
1036 LastOrder = 0;
1037 for (const auto &InstrOrder : Orders) {
1038 unsigned Order = InstrOrder.first;
1039 MachineInstr *MI = InstrOrder.second;
1040 if (!MI)
1041 continue;
1042
1043 // Insert all SDDbgLabel's whose order(s) are before "Order".
1044 for (; DLI != DLE &&
1045 (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
1046 ++DLI) {
1047 MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
1048 if (DbgMI) {
1049 if (!LastOrder)
1050 // Insert to start of the BB (after PHIs).
1051 BB->insert(BBBegin, DbgMI);
1052 else {
1053 // Insert at the instruction, which may be in a different
1054 // block, if the block was split by a custom inserter.
1056 MI->getParent()->insert(Pos, DbgMI);
1057 }
1058 }
1059 }
1060 if (DLI == DLE)
1061 break;
1062
1063 LastOrder = Order;
1064 }
1065 }
1066
1067 InsertPos = Emitter.getInsertPos();
1068 // In some cases, DBG_VALUEs might be inserted after the first terminator,
1069 // which results in an invalid MBB. If that happens, move the DBG_VALUEs
1070 // before the first terminator.
1071 MachineBasicBlock *InsertBB = Emitter.getBlock();
1072 auto FirstTerm = InsertBB->getFirstTerminator();
1073 if (FirstTerm != InsertBB->end()) {
1074 assert(!FirstTerm->isDebugValue() &&
1075 "first terminator cannot be a debug value");
1077 make_range(std::next(FirstTerm), InsertBB->end()))) {
1078 // Only scan up to insertion point.
1079 if (&MI == InsertPos)
1080 break;
1081
1082 if (!MI.isDebugValue())
1083 continue;
1084
1085 // The DBG_VALUE was referencing a value produced by a terminator. By
1086 // moving the DBG_VALUE, the referenced value also needs invalidating.
1087 MI.getOperand(0).ChangeToRegister(0, false);
1088 MI.moveBefore(&*FirstTerm);
1089 }
1090 }
1091 return InsertBB;
1092}
1093
1094/// Return the basic block label.
1096 return "sunit-dag." + BB->getFullName();
1097}
dxil DXContainer Global Emitter
This file defines the DenseMap class.
uint64_t Addr
bool End
Definition: ELF_riscv.cpp:480
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG)
static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG)
static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, const TargetLowering &TLI, unsigned &PhysReg, int &Cost)
CheckForPhysRegDependency - Check if the dependency between def and use of a specified operand is a p...
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)
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 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:167
This file describes how to lower LLVM code to machine code.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
This class represents an Operation in the Expression.
A debug info location.
Definition: DebugLoc.h:33
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
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:151
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
static unsigned CountResults(SDNode *Node)
CountResults - The results of target nodes have register or immediate operands first,...
bool isEmpty() const
Returns true if there are no itineraries.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:237
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:438
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:248
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specified operand constraint if it is present.
Definition: MCInstrDesc.h:219
ArrayRef< MCPhysReg > implicit_defs() const
Return a list of registers that are potentially written by any instance of this machine instruction.
Definition: MCInstrDesc.h:579
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:481
bool hasImplicitDefOfPhysReg(unsigned Reg, const MCRegisterInfo *MRI=nullptr) const
Return true if this instruction implicitly defines the specified physical register.
Definition: MCInstrDesc.cpp:32
bool isCall() const
Return true if the instruction is a call.
Definition: MCInstrDesc.h:288
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
Metadata node.
Definition: Metadata.h:1067
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void addCallSiteInfo(const MachineInstr *CallI, CallSiteInfo &&CallInfo)
Start tracking the arguments passed to the call CallI.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
Definition: MachineInstr.h:69
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
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
static constexpr bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
SmallVectorImpl< SDDbgLabel * >::iterator DbgLabelIterator
Definition: SelectionDAG.h:202
SmallVectorImpl< SDDbgValue * >::iterator DbgIterator
Definition: SelectionDAG.h:201
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.
This class provides iterator support for SDUse operands that use a specific SDNode.
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.
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.
const SDValue & getOperand(unsigned Num) const
use_iterator use_begin() const
Provide iteration support to walk over all uses of an SDNode.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
static use_iterator use_end()
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:49
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
void setLatency(unsigned Lat)
Sets the latency for this edge.
Definition: ScheduleDAG.h:147
@ Barrier
An unknown scheduling barrier.
Definition: ScheduleDAG.h:69
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
unsigned getReg() const
Returns the register associated with this edge.
Definition: ScheduleDAG.h:218
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
bool isCloned
True if this node has been cloned.
Definition: ScheduleDAG.h:287
bool isCall
Is a function call.
Definition: ScheduleDAG.h:275
void setNode(SDNode *N)
Assigns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:348
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
bool hasPhysRegClobbers
Has any physreg defs, used or not.
Definition: ScheduleDAG.h:281
bool isCallOp
Is a function call operand.
Definition: ScheduleDAG.h:276
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
Definition: ScheduleDAG.h:302
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
unsigned short NumRegDefsLeft
Definition: ScheduleDAG.h:272
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
bool isScheduleLow
True if preferable to schedule low.
Definition: ScheduleDAG.h:286
bool hasPhysRegDefs
Has physreg defs that are being used.
Definition: ScheduleDAG.h:280
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
Sched::Preference SchedulingPref
Scheduling preference.
Definition: ScheduleDAG.h:290
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:355
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:277
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:278
bool isVRegCycle
May use and def the same vreg.
Definition: ScheduleDAG.h:274
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
SUnit * OrigNode
If not this, the node from which this node was cloned.
Definition: ScheduleDAG.h:250
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)
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
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.
void BuildSchedGraph(AAResults *AA)
BuildSchedGraph - Build the SUnit graph from the selection dag that we are input.
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.
MachineBasicBlock * BB
void Run(SelectionDAG *dag, MachineBasicBlock *bb)
Run - perform scheduling.
void dump() const override
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.
Definition: ScheduleDAG.h:560
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:63
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:557
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:558
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:562
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:559
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.
Definition: ScheduleDAG.h:563
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:225
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
Definition: SelectionDAG.h:552
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
SDDbgInfo::DbgIterator ByvalParmDbgEnd() const
SDDbgInfo::DbgIterator ByvalParmDbgBegin() const
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:479
MDNode * getHeapAllocSite(const SDNode *Node) const
Return HeapAllocSite associated with Node, or nullptr if none exists.
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.
MDNode * getMMRAMetadata(const SDNode *Node) const
Return the MMRA MDNode associated with Node, or nullptr if none exists.
SDDbgInfo::DbgIterator DbgEnd() const
void setNodeMemRefs(MachineSDNode *N, ArrayRef< MachineMemOperand * > NewMemRefs)
Mutate the specified machine node's memory references to the provided list.
CallSiteInfo getCallSiteInfo(const SDNode *Node)
Return CallSiteInfo associated with Node, or a default if none exists.
MDNode * getPCSections(const SDNode *Node) const
Return PCSections associated with Node, or nullptr if none exists.
bool hasDebugValues() const
Return true if there are any SDDbgValue nodes associated with this SelectionDAG.
SDDbgInfo::DbgLabelIterator DbgLabelEnd() const
SDDbgInfo::DbgLabelIterator DbgLabelBegin() const
const TargetMachine & getTarget() const
Definition: SelectionDAG.h:474
bool getNoMergeSiteInfo(const SDNode *Node) const
Return NoMerge info associated with Node.
SDDbgInfo::DbgIterator DbgBegin() const
iterator_range< allnodes_iterator > allnodes()
Definition: SelectionDAG.h:544
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.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
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:179
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:717
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
TargetInstrInfo - Interface to description of machine instruction set.
virtual void insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const
Insert a noop into the instruction stream at the specified point.
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...
virtual std::optional< unsigned > getOperandLatency(const InstrItineraryData *ItinData, SDNode *DefNode, unsigned DefIdx, SDNode *UseNode, unsigned UseIdx) const
virtual unsigned getInstrLatency(const InstrItineraryData *ItinData, const MachineInstr &MI, unsigned *PredCost=nullptr) const
Compute the instruction latency of a given instruction.
virtual bool isHighLatencyDef(int opc) const
Return true if this opcode has high latency to its result.
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...
Sched::Preference getSchedulingPreference() const
Return target scheduling preference.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
virtual bool checkForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, unsigned &PhysReg, int &Cost) const
Allows the target to handle physreg-carried dependency in target-specific way.
TargetOptions Options
unsigned EmitCallSiteInfo
The flag enables call site info production.
int 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...
TargetSubtargetInfo - Generic base class for all target subtargets.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Value * getOperand(unsigned i) const
Definition: User.h:169
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
Definition: ISDOpcodes.h:209
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
Definition: ISDOpcodes.h:203
@ TokenFactor
TokenFactor - This node takes multiple tokens as input and produces a single token result.
Definition: ISDOpcodes.h:52
Offsets
Offsets in bytes from the start of the input buffer.
Definition: SIInstrInfo.h:1542
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
void stable_sort(R &&Range)
Definition: STLExtras.h:1995
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
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:656
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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:1914
#define N
Extended Value Type.
Definition: ValueTypes.h:34
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:1450