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