LLVM 20.0.0git
ScheduleDAGInstrs.cpp
Go to the documentation of this file.
1//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
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/// \file This implements the ScheduleDAGInstrs class, which implements
10/// re-scheduling of MachineInstrs.
11//
12//===----------------------------------------------------------------------===//
13
15
17#include "llvm/ADT/MapVector.h"
19#include "llvm/ADT/SparseSet.h"
41#include "llvm/Config/llvm-config.h"
42#include "llvm/IR/Constants.h"
43#include "llvm/IR/Function.h"
44#include "llvm/IR/Type.h"
45#include "llvm/IR/Value.h"
46#include "llvm/MC/LaneBitmask.h"
51#include "llvm/Support/Debug.h"
53#include "llvm/Support/Format.h"
55#include <algorithm>
56#include <cassert>
57#include <iterator>
58#include <utility>
59#include <vector>
60
61using namespace llvm;
62
63#define DEBUG_TYPE "machine-scheduler"
64
65static cl::opt<bool>
66 EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
67 cl::desc("Enable use of AA during MI DAG construction"));
68
69static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
70 cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"));
71
72// Note: the two options below might be used in tuning compile time vs
73// output quality. Setting HugeRegion so large that it will never be
74// reached means best-effort, but may be slow.
75
76// When Stores and Loads maps (or NonAliasStores and NonAliasLoads)
77// together hold this many SUs, a reduction of maps will be done.
78static cl::opt<unsigned> HugeRegion("dag-maps-huge-region", cl::Hidden,
79 cl::init(1000), cl::desc("The limit to use while constructing the DAG "
80 "prior to scheduling, at which point a trade-off "
81 "is made to avoid excessive compile time."));
82
84 "dag-maps-reduction-size", cl::Hidden,
85 cl::desc("A huge scheduling region will have maps reduced by this many "
86 "nodes at a time. Defaults to HugeRegion / 2."));
87
88#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
90 "sched-print-cycles", cl::Hidden, cl::init(false),
91 cl::desc("Report top/bottom cycles when dumping SUnit instances"));
92#endif
93
94static unsigned getReductionSize() {
95 // Always reduce a huge region with half of the elements, except
96 // when user sets this number explicitly.
97 if (ReductionSize.getNumOccurrences() == 0)
98 return HugeRegion / 2;
99 return ReductionSize;
100}
101
103#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
104 dbgs() << "{ ";
105 for (const SUnit *SU : L) {
106 dbgs() << "SU(" << SU->NodeNum << ")";
107 if (SU != L.back())
108 dbgs() << ", ";
109 }
110 dbgs() << "}\n";
111#endif
112}
113
115 const MachineLoopInfo *mli,
116 bool RemoveKillFlags)
117 : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
118 RemoveKillFlags(RemoveKillFlags),
119 UnknownValue(UndefValue::get(
120 Type::getVoidTy(mf.getFunction().getContext()))), Topo(SUnits, &ExitSU) {
121 DbgValues.clear();
122
123 const TargetSubtargetInfo &ST = mf.getSubtarget();
124 SchedModel.init(&ST);
125}
126
127/// If this machine instr has memory reference information and it can be
128/// tracked to a normal reference to a known object, return the Value
129/// for that object. This function returns false the memory location is
130/// unknown or may alias anything.
132 const MachineFrameInfo &MFI,
134 const DataLayout &DL) {
135 auto AllMMOsOkay = [&]() {
136 for (const MachineMemOperand *MMO : MI->memoperands()) {
137 // TODO: Figure out whether isAtomic is really necessary (see D57601).
138 if (MMO->isVolatile() || MMO->isAtomic())
139 return false;
140
141 if (const PseudoSourceValue *PSV = MMO->getPseudoValue()) {
142 // Function that contain tail calls don't have unique PseudoSourceValue
143 // objects. Two PseudoSourceValues might refer to the same or
144 // overlapping locations. The client code calling this function assumes
145 // this is not the case. So return a conservative answer of no known
146 // object.
147 if (MFI.hasTailCall())
148 return false;
149
150 // For now, ignore PseudoSourceValues which may alias LLVM IR values
151 // because the code that uses this function has no way to cope with
152 // such aliases.
153 if (PSV->isAliased(&MFI))
154 return false;
155
156 bool MayAlias = PSV->mayAlias(&MFI);
157 Objects.emplace_back(PSV, MayAlias);
158 } else if (const Value *V = MMO->getValue()) {
160 if (!getUnderlyingObjectsForCodeGen(V, Objs))
161 return false;
162
163 for (Value *V : Objs) {
165 Objects.emplace_back(V, true);
166 }
167 } else
168 return false;
169 }
170 return true;
171 };
172
173 if (!AllMMOsOkay()) {
174 Objects.clear();
175 return false;
176 }
177
178 return true;
179}
180
182 BB = bb;
183}
184
186 // Subclasses should no longer refer to the old block.
187 BB = nullptr;
188}
189
193 unsigned regioninstrs) {
194 assert(bb == BB && "startBlock should set BB");
196 RegionEnd = end;
197 NumRegionInstrs = regioninstrs;
198}
199
201 // Nothing to do.
202}
203
205 MachineInstr *ExitMI =
206 RegionEnd != BB->end()
208 : nullptr;
209 ExitSU.setInstr(ExitMI);
210 // Add dependencies on the defs and uses of the instruction.
211 if (ExitMI) {
212 for (const MachineOperand &MO : ExitMI->all_uses()) {
213 Register Reg = MO.getReg();
214 if (Reg.isPhysical()) {
215 for (MCRegUnit Unit : TRI->regunits(Reg))
216 Uses.insert(PhysRegSUOper(&ExitSU, -1, Unit));
217 } else if (Reg.isVirtual() && MO.readsReg()) {
218 addVRegUseDeps(&ExitSU, MO.getOperandNo());
219 }
220 }
221 }
222 if (!ExitMI || (!ExitMI->isCall() && !ExitMI->isBarrier())) {
223 // For others, e.g. fallthrough, conditional branch, assume the exit
224 // uses all the registers that are livein to the successor blocks.
225 for (const MachineBasicBlock *Succ : BB->successors()) {
226 for (const auto &LI : Succ->liveins()) {
227 for (MCRegUnitMaskIterator U(LI.PhysReg, TRI); U.isValid(); ++U) {
228 auto [Unit, Mask] = *U;
229 if ((Mask & LI.LaneMask).any() && !Uses.contains(Unit))
230 Uses.insert(PhysRegSUOper(&ExitSU, -1, Unit));
231 }
232 }
233 }
234 }
235}
236
237/// MO is an operand of SU's instruction that defines a physical register. Adds
238/// data dependencies from SU to any uses of the physical register.
239void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) {
240 const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx);
241 assert(MO.isDef() && "expect physreg def");
242 Register Reg = MO.getReg();
243
244 // Ask the target if address-backscheduling is desirable, and if so how much.
245 const TargetSubtargetInfo &ST = MF.getSubtarget();
246
247 // Only use any non-zero latency for real defs/uses, in contrast to
248 // "fake" operands added by regalloc.
249 const MCInstrDesc &DefMIDesc = SU->getInstr()->getDesc();
250 bool ImplicitPseudoDef = (OperIdx >= DefMIDesc.getNumOperands() &&
251 !DefMIDesc.hasImplicitDefOfPhysReg(Reg));
252 for (MCRegUnit Unit : TRI->regunits(Reg)) {
253 for (RegUnit2SUnitsMap::iterator I = Uses.find(Unit); I != Uses.end();
254 ++I) {
255 SUnit *UseSU = I->SU;
256 if (UseSU == SU)
257 continue;
258
259 // Adjust the dependence latency using operand def/use information,
260 // then allow the target to perform its own adjustments.
261 MachineInstr *UseInstr = nullptr;
262 int UseOpIdx = I->OpIdx;
263 bool ImplicitPseudoUse = false;
264 SDep Dep;
265 if (UseOpIdx < 0) {
266 Dep = SDep(SU, SDep::Artificial);
267 } else {
268 // Set the hasPhysRegDefs only for physreg defs that have a use within
269 // the scheduling region.
270 SU->hasPhysRegDefs = true;
271
272 UseInstr = UseSU->getInstr();
273 Register UseReg = UseInstr->getOperand(UseOpIdx).getReg();
274 const MCInstrDesc &UseMIDesc = UseInstr->getDesc();
275 ImplicitPseudoUse = UseOpIdx >= ((int)UseMIDesc.getNumOperands()) &&
277
278 Dep = SDep(SU, SDep::Data, UseReg);
279 }
280 if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
282 UseInstr, UseOpIdx));
283 } else {
284 Dep.setLatency(0);
285 }
286 ST.adjustSchedDependency(SU, OperIdx, UseSU, UseOpIdx, Dep, &SchedModel);
287 UseSU->addPred(Dep);
288 }
289 }
290}
291
292/// Adds register dependencies (data, anti, and output) from this SUnit
293/// to following instructions in the same scheduling region that depend the
294/// physical register referenced at OperIdx.
295void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
296 MachineInstr *MI = SU->getInstr();
297 MachineOperand &MO = MI->getOperand(OperIdx);
298 Register Reg = MO.getReg();
299 // We do not need to track any dependencies for constant registers.
300 if (MRI.isConstantPhysReg(Reg))
301 return;
302
303 const TargetSubtargetInfo &ST = MF.getSubtarget();
304
305 // Optionally add output and anti dependencies. For anti
306 // dependencies we use a latency of 0 because for a multi-issue
307 // target we want to allow the defining instruction to issue
308 // in the same cycle as the using instruction.
309 // TODO: Using a latency of 1 here for output dependencies assumes
310 // there's no cost for reusing registers.
311 SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
312 for (MCRegUnit Unit : TRI->regunits(Reg)) {
313 for (RegUnit2SUnitsMap::iterator I = Defs.find(Unit); I != Defs.end();
314 ++I) {
315 SUnit *DefSU = I->SU;
316 if (DefSU == &ExitSU)
317 continue;
318 MachineInstr *DefInstr = DefSU->getInstr();
319 MachineOperand &DefMO = DefInstr->getOperand(I->OpIdx);
320 if (DefSU != SU &&
321 (Kind != SDep::Output || !MO.isDead() || !DefMO.isDead())) {
322 SDep Dep(SU, Kind, DefMO.getReg());
323 if (Kind != SDep::Anti) {
324 Dep.setLatency(
325 SchedModel.computeOutputLatency(MI, OperIdx, DefInstr));
326 }
327 ST.adjustSchedDependency(SU, OperIdx, DefSU, I->OpIdx, Dep,
328 &SchedModel);
329 DefSU->addPred(Dep);
330 }
331 }
332 }
333
334 if (MO.isUse()) {
335 SU->hasPhysRegUses = true;
336 // Either insert a new Reg2SUnits entry with an empty SUnits list, or
337 // retrieve the existing SUnits list for this register's uses.
338 // Push this SUnit on the use list.
339 for (MCRegUnit Unit : TRI->regunits(Reg))
340 Uses.insert(PhysRegSUOper(SU, OperIdx, Unit));
341 if (RemoveKillFlags)
342 MO.setIsKill(false);
343 } else {
344 addPhysRegDataDeps(SU, OperIdx);
345
346 // Clear previous uses and defs of this register and its subregisters.
347 for (MCRegUnit Unit : TRI->regunits(Reg)) {
348 Uses.eraseAll(Unit);
349 if (!MO.isDead())
350 Defs.eraseAll(Unit);
351 }
352
353 if (MO.isDead() && SU->isCall) {
354 // Calls will not be reordered because of chain dependencies (see
355 // below). Since call operands are dead, calls may continue to be added
356 // to the DefList making dependence checking quadratic in the size of
357 // the block. Instead, we leave only one call at the back of the
358 // DefList.
359 for (MCRegUnit Unit : TRI->regunits(Reg)) {
363 for (bool isBegin = I == B; !isBegin; /* empty */) {
364 isBegin = (--I) == B;
365 if (!I->SU->isCall)
366 break;
367 I = Defs.erase(I);
368 }
369 }
370 }
371
372 // Defs are pushed in the order they are visited and never reordered.
373 for (MCRegUnit Unit : TRI->regunits(Reg))
374 Defs.insert(PhysRegSUOper(SU, OperIdx, Unit));
375 }
376}
377
379{
380 Register Reg = MO.getReg();
381 // No point in tracking lanemasks if we don't have interesting subregisters.
382 const TargetRegisterClass &RC = *MRI.getRegClass(Reg);
383 if (!RC.HasDisjunctSubRegs)
384 return LaneBitmask::getAll();
385
386 unsigned SubReg = MO.getSubReg();
387 if (SubReg == 0)
388 return RC.getLaneMask();
390}
391
393 auto RegUse = CurrentVRegUses.find(MO.getReg());
394 if (RegUse == CurrentVRegUses.end())
395 return true;
396 return (RegUse->LaneMask & getLaneMaskForMO(MO)).none();
397}
398
399/// Adds register output and data dependencies from this SUnit to instructions
400/// that occur later in the same scheduling region if they read from or write to
401/// the virtual register defined at OperIdx.
402///
403/// TODO: Hoist loop induction variable increments. This has to be
404/// reevaluated. Generally, IV scheduling should be done before coalescing.
405void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
406 MachineInstr *MI = SU->getInstr();
407 MachineOperand &MO = MI->getOperand(OperIdx);
408 Register Reg = MO.getReg();
409
410 LaneBitmask DefLaneMask;
411 LaneBitmask KillLaneMask;
412 if (TrackLaneMasks) {
413 bool IsKill = MO.getSubReg() == 0 || MO.isUndef();
414 DefLaneMask = getLaneMaskForMO(MO);
415 // If we have a <read-undef> flag, none of the lane values comes from an
416 // earlier instruction.
417 KillLaneMask = IsKill ? LaneBitmask::getAll() : DefLaneMask;
418
419 if (MO.getSubReg() != 0 && MO.isUndef()) {
420 // There may be other subregister defs on the same instruction of the same
421 // register in later operands. The lanes of other defs will now be live
422 // after this instruction, so these should not be treated as killed by the
423 // instruction even though they appear to be killed in this one operand.
424 for (const MachineOperand &OtherMO :
425 llvm::drop_begin(MI->operands(), OperIdx + 1))
426 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
427 KillLaneMask &= ~getLaneMaskForMO(OtherMO);
428 }
429
430 // Clear undef flag, we'll re-add it later once we know which subregister
431 // Def is first.
432 MO.setIsUndef(false);
433 } else {
434 DefLaneMask = LaneBitmask::getAll();
435 KillLaneMask = LaneBitmask::getAll();
436 }
437
438 if (MO.isDead()) {
439 assert(deadDefHasNoUse(MO) && "Dead defs should have no uses");
440 } else {
441 // Add data dependence to all uses we found so far.
442 const TargetSubtargetInfo &ST = MF.getSubtarget();
444 E = CurrentVRegUses.end(); I != E; /*empty*/) {
445 LaneBitmask LaneMask = I->LaneMask;
446 // Ignore uses of other lanes.
447 if ((LaneMask & KillLaneMask).none()) {
448 ++I;
449 continue;
450 }
451
452 if ((LaneMask & DefLaneMask).any()) {
453 SUnit *UseSU = I->SU;
454 MachineInstr *Use = UseSU->getInstr();
455 SDep Dep(SU, SDep::Data, Reg);
457 I->OperandIndex));
458 ST.adjustSchedDependency(SU, OperIdx, UseSU, I->OperandIndex, Dep,
459 &SchedModel);
460 UseSU->addPred(Dep);
461 }
462
463 LaneMask &= ~KillLaneMask;
464 // If we found a Def for all lanes of this use, remove it from the list.
465 if (LaneMask.any()) {
466 I->LaneMask = LaneMask;
467 ++I;
468 } else
470 }
471 }
472
473 // Shortcut: Singly defined vregs do not have output/anti dependencies.
474 if (MRI.hasOneDef(Reg))
475 return;
476
477 // Add output dependence to the next nearest defs of this vreg.
478 //
479 // Unless this definition is dead, the output dependence should be
480 // transitively redundant with antidependencies from this definition's
481 // uses. We're conservative for now until we have a way to guarantee the uses
482 // are not eliminated sometime during scheduling. The output dependence edge
483 // is also useful if output latency exceeds def-use latency.
484 LaneBitmask LaneMask = DefLaneMask;
485 for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
486 CurrentVRegDefs.end())) {
487 // Ignore defs for other lanes.
488 if ((V2SU.LaneMask & LaneMask).none())
489 continue;
490 // Add an output dependence.
491 SUnit *DefSU = V2SU.SU;
492 // Ignore additional defs of the same lanes in one instruction. This can
493 // happen because lanemasks are shared for targets with too many
494 // subregisters. We also use some representration tricks/hacks where we
495 // add super-register defs/uses, to imply that although we only access parts
496 // of the reg we care about the full one.
497 if (DefSU == SU)
498 continue;
499 SDep Dep(SU, SDep::Output, Reg);
500 Dep.setLatency(
501 SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
502 DefSU->addPred(Dep);
503
504 // Update current definition. This can get tricky if the def was about a
505 // bigger lanemask before. We then have to shrink it and create a new
506 // VReg2SUnit for the non-overlapping part.
507 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
508 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
509 V2SU.SU = SU;
510 V2SU.LaneMask = OverlapMask;
511 if (NonOverlapMask.any())
512 CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, DefSU));
513 }
514 // If there was no CurrentVRegDefs entry for some lanes yet, create one.
515 if (LaneMask.any())
516 CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU));
517}
518
519/// Adds a register data dependency if the instruction that defines the
520/// virtual register used at OperIdx is mapped to an SUnit. Add a register
521/// antidependency from this SUnit to instructions that occur later in the same
522/// scheduling region if they write the virtual register.
523///
524/// TODO: Handle ExitSU "uses" properly.
525void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
526 const MachineInstr *MI = SU->getInstr();
527 assert(!MI->isDebugOrPseudoInstr());
528
529 const MachineOperand &MO = MI->getOperand(OperIdx);
530 Register Reg = MO.getReg();
531
532 // Remember the use. Data dependencies will be added when we find the def.
535 CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU));
536
537 // Add antidependences to the following defs of the vreg.
538 for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
539 CurrentVRegDefs.end())) {
540 // Ignore defs for unrelated lanes.
541 LaneBitmask PrevDefLaneMask = V2SU.LaneMask;
542 if ((PrevDefLaneMask & LaneMask).none())
543 continue;
544 if (V2SU.SU == SU)
545 continue;
546
547 V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg));
548 }
549}
550
551
553 unsigned Latency) {
554 if (SUa->getInstr()->mayAlias(AAForDep, *SUb->getInstr(), UseTBAA)) {
555 SDep Dep(SUa, SDep::MayAliasMem);
556 Dep.setLatency(Latency);
557 SUb->addPred(Dep);
558 }
559}
560
561/// Creates an SUnit for each real instruction, numbered in top-down
562/// topological order. The instruction order A < B, implies that no edge exists
563/// from B to A.
564///
565/// Map each real instruction to its SUnit.
566///
567/// After initSUnits, the SUnits vector cannot be resized and the scheduler may
568/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs
569/// instead of pointers.
570///
571/// MachineScheduler relies on initSUnits numbering the nodes by their order in
572/// the original instruction list.
574 // We'll be allocating one SUnit for each real instruction in the region,
575 // which is contained within a basic block.
576 SUnits.reserve(NumRegionInstrs);
577
579 if (MI.isDebugOrPseudoInstr())
580 continue;
581
582 SUnit *SU = newSUnit(&MI);
583 MISUnitMap[&MI] = SU;
584
585 SU->isCall = MI.isCall();
586 SU->isCommutable = MI.isCommutable();
587
588 // Assign the Latency field of SU using target-provided information.
589 SU->Latency = SchedModel.computeInstrLatency(SU->getInstr());
590
591 // If this SUnit uses a reserved or unbuffered resource, mark it as such.
592 //
593 // Reserved resources block an instruction from issuing and stall the
594 // entire pipeline. These are identified by BufferSize=0.
595 //
596 // Unbuffered resources prevent execution of subsequent instructions that
597 // require the same resources. This is used for in-order execution pipelines
598 // within an out-of-order core. These are identified by BufferSize=1.
600 const MCSchedClassDesc *SC = getSchedClass(SU);
601 for (const MCWriteProcResEntry &PRE :
604 switch (SchedModel.getProcResource(PRE.ProcResourceIdx)->BufferSize) {
605 case 0:
606 SU->hasReservedResource = true;
607 break;
608 case 1:
609 SU->isUnbuffered = true;
610 break;
611 default:
612 break;
613 }
614 }
615 }
616 }
617}
618
620 : public SmallMapVector<ValueType, SUList, 4> {
621 /// Current total number of SUs in map.
622 unsigned NumNodes = 0;
623
624 /// 1 for loads, 0 for stores. (see comment in SUList)
625 unsigned TrueMemOrderLatency;
626
627public:
628 Value2SUsMap(unsigned lat = 0) : TrueMemOrderLatency(lat) {}
629
630 /// To keep NumNodes up to date, insert() is used instead of
631 /// this operator w/ push_back().
633 llvm_unreachable("Don't use. Use insert() instead."); };
634
635 /// Adds SU to the SUList of V. If Map grows huge, reduce its size by calling
636 /// reduce().
637 void inline insert(SUnit *SU, ValueType V) {
638 MapVector::operator[](V).push_back(SU);
639 NumNodes++;
640 }
641
642 /// Clears the list of SUs mapped to V.
643 void inline clearList(ValueType V) {
644 iterator Itr = find(V);
645 if (Itr != end()) {
646 assert(NumNodes >= Itr->second.size());
647 NumNodes -= Itr->second.size();
648
649 Itr->second.clear();
650 }
651 }
652
653 /// Clears map from all contents.
654 void clear() {
656 NumNodes = 0;
657 }
658
659 unsigned inline size() const { return NumNodes; }
660
661 /// Counts the number of SUs in this map after a reduction.
663 NumNodes = 0;
664 for (auto &I : *this)
665 NumNodes += I.second.size();
666 }
667
668 unsigned inline getTrueMemOrderLatency() const {
669 return TrueMemOrderLatency;
670 }
671
672 void dump();
673};
674
676 Value2SUsMap &Val2SUsMap) {
677 for (auto &I : Val2SUsMap)
678 addChainDependencies(SU, I.second,
679 Val2SUsMap.getTrueMemOrderLatency());
680}
681
683 Value2SUsMap &Val2SUsMap,
684 ValueType V) {
685 Value2SUsMap::iterator Itr = Val2SUsMap.find(V);
686 if (Itr != Val2SUsMap.end())
687 addChainDependencies(SU, Itr->second,
688 Val2SUsMap.getTrueMemOrderLatency());
689}
690
692 assert(BarrierChain != nullptr);
693
694 for (auto &[V, SUs] : map) {
695 (void)V;
696 for (auto *SU : SUs)
697 SU->addPredBarrier(BarrierChain);
698 }
699 map.clear();
700}
701
703 assert(BarrierChain != nullptr);
704
705 // Go through all lists of SUs.
706 for (Value2SUsMap::iterator I = map.begin(), EE = map.end(); I != EE;) {
707 Value2SUsMap::iterator CurrItr = I++;
708 SUList &sus = CurrItr->second;
709 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
710 for (; SUItr != SUEE; ++SUItr) {
711 // Stop on BarrierChain or any instruction above it.
712 if ((*SUItr)->NodeNum <= BarrierChain->NodeNum)
713 break;
714
715 (*SUItr)->addPredBarrier(BarrierChain);
716 }
717
718 // Remove also the BarrierChain from list if present.
719 if (SUItr != SUEE && *SUItr == BarrierChain)
720 SUItr++;
721
722 // Remove all SUs that are now successors of BarrierChain.
723 if (SUItr != sus.begin())
724 sus.erase(sus.begin(), SUItr);
725 }
726
727 // Remove all entries with empty su lists.
728 map.remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
729 return (mapEntry.second.empty()); });
730
731 // Recompute the size of the map (NumNodes).
732 map.reComputeSize();
733}
734
736 RegPressureTracker *RPTracker,
737 PressureDiffs *PDiffs,
738 LiveIntervals *LIS,
739 bool TrackLaneMasks) {
740 const TargetSubtargetInfo &ST = MF.getSubtarget();
742 : ST.useAA();
743 AAForDep = UseAA ? AA : nullptr;
744
745 BarrierChain = nullptr;
746
747 this->TrackLaneMasks = TrackLaneMasks;
748 MISUnitMap.clear();
750
751 // Create an SUnit for each real instruction.
752 initSUnits();
753
754 if (PDiffs)
755 PDiffs->init(SUnits.size());
756
757 // We build scheduling units by walking a block's instruction list
758 // from bottom to top.
759
760 // Each MIs' memory operand(s) is analyzed to a list of underlying
761 // objects. The SU is then inserted in the SUList(s) mapped from the
762 // Value(s). Each Value thus gets mapped to lists of SUs depending
763 // on it, stores and loads kept separately. Two SUs are trivially
764 // non-aliasing if they both depend on only identified Values and do
765 // not share any common Value.
766 Value2SUsMap Stores, Loads(1 /*TrueMemOrderLatency*/);
767
768 // Certain memory accesses are known to not alias any SU in Stores
769 // or Loads, and have therefore their own 'NonAlias'
770 // domain. E.g. spill / reload instructions never alias LLVM I/R
771 // Values. It would be nice to assume that this type of memory
772 // accesses always have a proper memory operand modelling, and are
773 // therefore never unanalyzable, but this is conservatively not
774 // done.
775 Value2SUsMap NonAliasStores, NonAliasLoads(1 /*TrueMemOrderLatency*/);
776
777 // Track all instructions that may raise floating-point exceptions.
778 // These do not depend on one other (or normal loads or stores), but
779 // must not be rescheduled across global barriers. Note that we don't
780 // really need a "map" here since we don't track those MIs by value;
781 // using the same Value2SUsMap data type here is simply a matter of
782 // convenience.
783 Value2SUsMap FPExceptions;
784
785 // Remove any stale debug info; sometimes BuildSchedGraph is called again
786 // without emitting the info from the previous call.
787 DbgValues.clear();
788 FirstDbgValue = nullptr;
789
790 assert(Defs.empty() && Uses.empty() &&
791 "Only BuildGraph should update Defs/Uses");
794
795 assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs");
796 assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses");
797 unsigned NumVirtRegs = MRI.getNumVirtRegs();
798 CurrentVRegDefs.setUniverse(NumVirtRegs);
799 CurrentVRegUses.setUniverse(NumVirtRegs);
800
801 // Model data dependencies between instructions being scheduled and the
802 // ExitSU.
804
805 // Walk the list of instructions, from bottom moving up.
806 MachineInstr *DbgMI = nullptr;
808 MII != MIE; --MII) {
809 MachineInstr &MI = *std::prev(MII);
810 if (DbgMI) {
811 DbgValues.emplace_back(DbgMI, &MI);
812 DbgMI = nullptr;
813 }
814
815 if (MI.isDebugValue() || MI.isDebugPHI()) {
816 DbgMI = &MI;
817 continue;
818 }
819
820 if (MI.isDebugLabel() || MI.isDebugRef() || MI.isPseudoProbe())
821 continue;
822
823 SUnit *SU = MISUnitMap[&MI];
824 assert(SU && "No SUnit mapped to this MI");
825
826 if (RPTracker) {
827 RegisterOperands RegOpers;
828 RegOpers.collect(MI, *TRI, MRI, TrackLaneMasks, false);
829 if (TrackLaneMasks) {
830 SlotIndex SlotIdx = LIS->getInstructionIndex(MI);
831 RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx);
832 }
833 if (PDiffs != nullptr)
834 PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI);
835
836 if (RPTracker->getPos() == RegionEnd || &*RPTracker->getPos() != &MI)
837 RPTracker->recedeSkipDebugValues();
838 assert(&*RPTracker->getPos() == &MI && "RPTracker in sync");
839 RPTracker->recede(RegOpers);
840 }
841
842 assert(
843 (CanHandleTerminators || (!MI.isTerminator() && !MI.isPosition())) &&
844 "Cannot schedule terminators or labels!");
845
846 // Add register-based dependencies (data, anti, and output).
847 // For some instructions (calls, returns, inline-asm, etc.) there can
848 // be explicit uses and implicit defs, in which case the use will appear
849 // on the operand list before the def. Do two passes over the operand
850 // list to make sure that defs are processed before any uses.
851 bool HasVRegDef = false;
852 for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
853 const MachineOperand &MO = MI.getOperand(j);
854 if (!MO.isReg() || !MO.isDef())
855 continue;
856 Register Reg = MO.getReg();
857 if (Reg.isPhysical()) {
858 addPhysRegDeps(SU, j);
859 } else if (Reg.isVirtual()) {
860 HasVRegDef = true;
861 addVRegDefDeps(SU, j);
862 }
863 }
864 // Now process all uses.
865 for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
866 const MachineOperand &MO = MI.getOperand(j);
867 // Only look at use operands.
868 // We do not need to check for MO.readsReg() here because subsequent
869 // subregister defs will get output dependence edges and need no
870 // additional use dependencies.
871 if (!MO.isReg() || !MO.isUse())
872 continue;
873 Register Reg = MO.getReg();
874 if (Reg.isPhysical()) {
875 addPhysRegDeps(SU, j);
876 } else if (Reg.isVirtual() && MO.readsReg()) {
877 addVRegUseDeps(SU, j);
878 }
879 }
880
881 // If we haven't seen any uses in this scheduling region, create a
882 // dependence edge to ExitSU to model the live-out latency. This is required
883 // for vreg defs with no in-region use, and prefetches with no vreg def.
884 //
885 // FIXME: NumDataSuccs would be more precise than NumSuccs here. This
886 // check currently relies on being called before adding chain deps.
887 if (SU->NumSuccs == 0 && SU->Latency > 1 && (HasVRegDef || MI.mayLoad())) {
888 SDep Dep(SU, SDep::Artificial);
889 Dep.setLatency(SU->Latency - 1);
890 ExitSU.addPred(Dep);
891 }
892
893 // Add memory dependencies (Note: isStoreToStackSlot and
894 // isLoadFromStackSLot are not usable after stack slots are lowered to
895 // actual addresses).
896
897 const TargetInstrInfo *TII = ST.getInstrInfo();
898 // This is a barrier event that acts as a pivotal node in the DAG.
899 if (TII->isGlobalMemoryObject(&MI)) {
900
901 // Become the barrier chain.
902 if (BarrierChain)
904 BarrierChain = SU;
905
906 LLVM_DEBUG(dbgs() << "Global memory object and new barrier chain: SU("
907 << BarrierChain->NodeNum << ").\n");
908
909 // Add dependencies against everything below it and clear maps.
910 addBarrierChain(Stores);
911 addBarrierChain(Loads);
912 addBarrierChain(NonAliasStores);
913 addBarrierChain(NonAliasLoads);
914 addBarrierChain(FPExceptions);
915
916 continue;
917 }
918
919 // Instructions that may raise FP exceptions may not be moved
920 // across any global barriers.
921 if (MI.mayRaiseFPException()) {
922 if (BarrierChain)
924
925 FPExceptions.insert(SU, UnknownValue);
926
927 if (FPExceptions.size() >= HugeRegion) {
928 LLVM_DEBUG(dbgs() << "Reducing FPExceptions map.\n");
929 Value2SUsMap empty;
930 reduceHugeMemNodeMaps(FPExceptions, empty, getReductionSize());
931 }
932 }
933
934 // If it's not a store or a variant load, we're done.
935 if (!MI.mayStore() &&
936 !(MI.mayLoad() && !MI.isDereferenceableInvariantLoad()))
937 continue;
938
939 // Always add dependecy edge to BarrierChain if present.
940 if (BarrierChain)
942
943 // Find the underlying objects for MI. The Objs vector is either
944 // empty, or filled with the Values of memory locations which this
945 // SU depends on.
947 bool ObjsFound = getUnderlyingObjectsForInstr(&MI, MFI, Objs,
948 MF.getDataLayout());
949
950 if (MI.mayStore()) {
951 if (!ObjsFound) {
952 // An unknown store depends on all stores and loads.
953 addChainDependencies(SU, Stores);
954 addChainDependencies(SU, NonAliasStores);
955 addChainDependencies(SU, Loads);
956 addChainDependencies(SU, NonAliasLoads);
957
958 // Map this store to 'UnknownValue'.
959 Stores.insert(SU, UnknownValue);
960 } else {
961 // Add precise dependencies against all previously seen memory
962 // accesses mapped to the same Value(s).
963 for (const UnderlyingObject &UnderlObj : Objs) {
964 ValueType V = UnderlObj.getValue();
965 bool ThisMayAlias = UnderlObj.mayAlias();
966
967 // Add dependencies to previous stores and loads mapped to V.
968 addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V);
969 addChainDependencies(SU, (ThisMayAlias ? Loads : NonAliasLoads), V);
970 }
971 // Update the store map after all chains have been added to avoid adding
972 // self-loop edge if multiple underlying objects are present.
973 for (const UnderlyingObject &UnderlObj : Objs) {
974 ValueType V = UnderlObj.getValue();
975 bool ThisMayAlias = UnderlObj.mayAlias();
976
977 // Map this store to V.
978 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
979 }
980 // The store may have dependencies to unanalyzable loads and
981 // stores.
984 }
985 } else { // SU is a load.
986 if (!ObjsFound) {
987 // An unknown load depends on all stores.
988 addChainDependencies(SU, Stores);
989 addChainDependencies(SU, NonAliasStores);
990
991 Loads.insert(SU, UnknownValue);
992 } else {
993 for (const UnderlyingObject &UnderlObj : Objs) {
994 ValueType V = UnderlObj.getValue();
995 bool ThisMayAlias = UnderlObj.mayAlias();
996
997 // Add precise dependencies against all previously seen stores
998 // mapping to the same Value(s).
999 addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V);
1000
1001 // Map this load to V.
1002 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1003 }
1004 // The load may have dependencies to unanalyzable stores.
1006 }
1007 }
1008
1009 // Reduce maps if they grow huge.
1010 if (Stores.size() + Loads.size() >= HugeRegion) {
1011 LLVM_DEBUG(dbgs() << "Reducing Stores and Loads maps.\n");
1012 reduceHugeMemNodeMaps(Stores, Loads, getReductionSize());
1013 }
1014 if (NonAliasStores.size() + NonAliasLoads.size() >= HugeRegion) {
1015 LLVM_DEBUG(dbgs() << "Reducing NonAliasStores and NonAliasLoads maps.\n");
1016 reduceHugeMemNodeMaps(NonAliasStores, NonAliasLoads, getReductionSize());
1017 }
1018 }
1019
1020 if (DbgMI)
1021 FirstDbgValue = DbgMI;
1022
1023 Defs.clear();
1024 Uses.clear();
1027
1028 Topo.MarkDirty();
1029}
1030
1032 PSV->printCustom(OS);
1033 return OS;
1034}
1035
1037 for (const auto &[ValType, SUs] : *this) {
1038 if (isa<const Value *>(ValType)) {
1039 const Value *V = cast<const Value *>(ValType);
1040 if (isa<UndefValue>(V))
1041 dbgs() << "Unknown";
1042 else
1043 V->printAsOperand(dbgs());
1044 } else if (isa<const PseudoSourceValue *>(ValType))
1045 dbgs() << cast<const PseudoSourceValue *>(ValType);
1046 else
1047 llvm_unreachable("Unknown Value type.");
1048
1049 dbgs() << " : ";
1050 dumpSUList(SUs);
1051 }
1052}
1053
1055 Value2SUsMap &loads, unsigned N) {
1056 LLVM_DEBUG(dbgs() << "Before reduction:\nStoring SUnits:\n"; stores.dump();
1057 dbgs() << "Loading SUnits:\n"; loads.dump());
1058
1059 // Insert all SU's NodeNums into a vector and sort it.
1060 std::vector<unsigned> NodeNums;
1061 NodeNums.reserve(stores.size() + loads.size());
1062 for (const auto &[V, SUs] : stores) {
1063 (void)V;
1064 for (const auto *SU : SUs)
1065 NodeNums.push_back(SU->NodeNum);
1066 }
1067 for (const auto &[V, SUs] : loads) {
1068 (void)V;
1069 for (const auto *SU : SUs)
1070 NodeNums.push_back(SU->NodeNum);
1071 }
1072 llvm::sort(NodeNums);
1073
1074 // The N last elements in NodeNums will be removed, and the SU with
1075 // the lowest NodeNum of them will become the new BarrierChain to
1076 // let the not yet seen SUs have a dependency to the removed SUs.
1077 assert(N <= NodeNums.size());
1078 SUnit *newBarrierChain = &SUnits[*(NodeNums.end() - N)];
1079 if (BarrierChain) {
1080 // The aliasing and non-aliasing maps reduce independently of each
1081 // other, but share a common BarrierChain. Check if the
1082 // newBarrierChain is above the former one. If it is not, it may
1083 // introduce a loop to use newBarrierChain, so keep the old one.
1084 if (newBarrierChain->NodeNum < BarrierChain->NodeNum) {
1085 BarrierChain->addPredBarrier(newBarrierChain);
1086 BarrierChain = newBarrierChain;
1087 LLVM_DEBUG(dbgs() << "Inserting new barrier chain: SU("
1088 << BarrierChain->NodeNum << ").\n");
1089 }
1090 else
1091 LLVM_DEBUG(dbgs() << "Keeping old barrier chain: SU("
1092 << BarrierChain->NodeNum << ").\n");
1093 }
1094 else
1095 BarrierChain = newBarrierChain;
1096
1099
1100 LLVM_DEBUG(dbgs() << "After reduction:\nStoring SUnits:\n"; stores.dump();
1101 dbgs() << "Loading SUnits:\n"; loads.dump());
1102}
1103
1105 MachineInstr &MI, bool addToLiveRegs) {
1106 for (MachineOperand &MO : MI.operands()) {
1107 if (!MO.isReg() || !MO.readsReg())
1108 continue;
1109 Register Reg = MO.getReg();
1110 if (!Reg)
1111 continue;
1112
1113 // Things that are available after the instruction are killed by it.
1114 bool IsKill = LiveRegs.available(Reg);
1115
1116 // Exception: Do not kill reserved registers
1117 MO.setIsKill(IsKill && !MRI.isReserved(Reg));
1118 if (addToLiveRegs)
1119 LiveRegs.addReg(Reg);
1120 }
1121}
1122
1124 LLVM_DEBUG(dbgs() << "Fixup kills for " << printMBBReference(MBB) << '\n');
1125
1126 LiveRegs.init(*TRI);
1128
1129 // Examine block from end to start...
1130 for (MachineInstr &MI : llvm::reverse(MBB)) {
1131 if (MI.isDebugOrPseudoInstr())
1132 continue;
1133
1134 // Update liveness. Registers that are defed but not used in this
1135 // instruction are now dead. Mark register and all subregs as they
1136 // are completely defined.
1137 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
1138 const MachineOperand &MO = *O;
1139 if (MO.isReg()) {
1140 if (!MO.isDef())
1141 continue;
1142 Register Reg = MO.getReg();
1143 if (!Reg)
1144 continue;
1145 LiveRegs.removeReg(Reg);
1146 } else if (MO.isRegMask()) {
1148 }
1149 }
1150
1151 // If there is a bundle header fix it up first.
1152 if (!MI.isBundled()) {
1153 toggleKills(MRI, LiveRegs, MI, true);
1154 } else {
1155 MachineBasicBlock::instr_iterator Bundle = MI.getIterator();
1156 if (MI.isBundle())
1157 toggleKills(MRI, LiveRegs, MI, false);
1158
1159 // Some targets make the (questionable) assumtion that the instructions
1160 // inside the bundle are ordered and consequently only the last use of
1161 // a register inside the bundle can kill it.
1162 MachineBasicBlock::instr_iterator I = std::next(Bundle);
1163 while (I->isBundledWithSucc())
1164 ++I;
1165 do {
1166 if (!I->isDebugOrPseudoInstr())
1167 toggleKills(MRI, LiveRegs, *I, true);
1168 --I;
1169 } while (I != Bundle);
1170 }
1171 }
1172}
1173
1174void ScheduleDAGInstrs::dumpNode(const SUnit &SU) const {
1175#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1176 dumpNodeName(SU);
1177 if (SchedPrintCycles)
1178 dbgs() << " [TopReadyCycle = " << SU.TopReadyCycle
1179 << ", BottomReadyCycle = " << SU.BotReadyCycle << "]";
1180 dbgs() << ": ";
1181 SU.getInstr()->dump();
1182#endif
1183}
1184
1186#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1187 if (EntrySU.getInstr() != nullptr)
1189 for (const SUnit &SU : SUnits)
1190 dumpNodeAll(SU);
1191 if (ExitSU.getInstr() != nullptr)
1193#endif
1194}
1195
1196std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
1197 std::string s;
1198 raw_string_ostream oss(s);
1199 if (SU == &EntrySU)
1200 oss << "<entry>";
1201 else if (SU == &ExitSU)
1202 oss << "<exit>";
1203 else
1204 SU->getInstr()->print(oss, /*IsStandalone=*/true);
1205 return s;
1206}
1207
1208/// Return the basic block label. It is not necessarily unique because a block
1209/// contains multiple scheduling regions. But it is fine for visualization.
1211 return "dag." + BB->getFullName();
1212}
1213
1215 return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
1216}
1217
1218bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) {
1219 if (SuccSU != &ExitSU) {
1220 // Do not use WillCreateCycle, it assumes SD scheduling.
1221 // If Pred is reachable from Succ, then the edge creates a cycle.
1222 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
1223 return false;
1224 Topo.AddPredQueued(SuccSU, PredDep.getSUnit());
1225 }
1226 SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
1227 // Return true regardless of whether a new edge needed to be inserted.
1228 return true;
1229}
1230
1231//===----------------------------------------------------------------------===//
1232// SchedDFSResult Implementation
1233//===----------------------------------------------------------------------===//
1234
1235namespace llvm {
1236
1237/// Internal state used to compute SchedDFSResult.
1239 SchedDFSResult &R;
1240
1241 /// Join DAG nodes into equivalence classes by their subtree.
1242 IntEqClasses SubtreeClasses;
1243 /// List PredSU, SuccSU pairs that represent data edges between subtrees.
1244 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1245
1246 struct RootData {
1247 unsigned NodeID;
1248 unsigned ParentNodeID; ///< Parent node (member of the parent subtree).
1249 unsigned SubInstrCount = 0; ///< Instr count in this tree only, not
1250 /// children.
1251
1252 RootData(unsigned id): NodeID(id),
1253 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1254
1255 unsigned getSparseSetIndex() const { return NodeID; }
1256 };
1257
1258 SparseSet<RootData> RootSet;
1259
1260public:
1261 SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) {
1262 RootSet.setUniverse(R.DFSNodeData.size());
1263 }
1264
1265 /// Returns true if this node been visited by the DFS traversal.
1266 ///
1267 /// During visitPostorderNode the Node's SubtreeID is assigned to the Node
1268 /// ID. Later, SubtreeID is updated but remains valid.
1269 bool isVisited(const SUnit *SU) const {
1270 return R.DFSNodeData[SU->NodeNum].SubtreeID
1271 != SchedDFSResult::InvalidSubtreeID;
1272 }
1273
1274 /// Initializes this node's instruction count. We don't need to flag the node
1275 /// visited until visitPostorder because the DAG cannot have cycles.
1276 void visitPreorder(const SUnit *SU) {
1277 R.DFSNodeData[SU->NodeNum].InstrCount =
1278 SU->getInstr()->isTransient() ? 0 : 1;
1279 }
1280
1281 /// Called once for each node after all predecessors are visited. Revisit this
1282 /// node's predecessors and potentially join them now that we know the ILP of
1283 /// the other predecessors.
1284 void visitPostorderNode(const SUnit *SU) {
1285 // Mark this node as the root of a subtree. It may be joined with its
1286 // successors later.
1287 R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum;
1288 RootData RData(SU->NodeNum);
1289 RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1;
1290
1291 // If any predecessors are still in their own subtree, they either cannot be
1292 // joined or are large enough to remain separate. If this parent node's
1293 // total instruction count is not greater than a child subtree by at least
1294 // the subtree limit, then try to join it now since splitting subtrees is
1295 // only useful if multiple high-pressure paths are possible.
1296 unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount;
1297 for (const SDep &PredDep : SU->Preds) {
1298 if (PredDep.getKind() != SDep::Data)
1299 continue;
1300 unsigned PredNum = PredDep.getSUnit()->NodeNum;
1301 if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1302 joinPredSubtree(PredDep, SU, /*CheckLimit=*/false);
1303
1304 // Either link or merge the TreeData entry from the child to the parent.
1305 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1306 // If the predecessor's parent is invalid, this is a tree edge and the
1307 // current node is the parent.
1308 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1309 RootSet[PredNum].ParentNodeID = SU->NodeNum;
1310 }
1311 else if (RootSet.count(PredNum)) {
1312 // The predecessor is not a root, but is still in the root set. This
1313 // must be the new parent that it was just joined to. Note that
1314 // RootSet[PredNum].ParentNodeID may either be invalid or may still be
1315 // set to the original parent.
1316 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1317 RootSet.erase(PredNum);
1318 }
1319 }
1320 RootSet[SU->NodeNum] = RData;
1321 }
1322
1323 /// Called once for each tree edge after calling visitPostOrderNode on
1324 /// the predecessor. Increment the parent node's instruction count and
1325 /// preemptively join this subtree to its parent's if it is small enough.
1326 void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) {
1327 R.DFSNodeData[Succ->NodeNum].InstrCount
1328 += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount;
1329 joinPredSubtree(PredDep, Succ);
1330 }
1331
1332 /// Adds a connection for cross edges.
1333 void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) {
1334 ConnectionPairs.emplace_back(PredDep.getSUnit(), Succ);
1335 }
1336
1337 /// Sets each node's subtree ID to the representative ID and record
1338 /// connections between trees.
1339 void finalize() {
1340 SubtreeClasses.compress();
1341 R.DFSTreeData.resize(SubtreeClasses.getNumClasses());
1342 assert(SubtreeClasses.getNumClasses() == RootSet.size()
1343 && "number of roots should match trees");
1344 for (const RootData &Root : RootSet) {
1345 unsigned TreeID = SubtreeClasses[Root.NodeID];
1346 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1347 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1348 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1349 // Note that SubInstrCount may be greater than InstrCount if we joined
1350 // subtrees across a cross edge. InstrCount will be attributed to the
1351 // original parent, while SubInstrCount will be attributed to the joined
1352 // parent.
1353 }
1354 R.SubtreeConnections.resize(SubtreeClasses.getNumClasses());
1355 R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses());
1356 LLVM_DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n");
1357 for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) {
1358 R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1359 LLVM_DEBUG(dbgs() << " SU(" << Idx << ") in tree "
1360 << R.DFSNodeData[Idx].SubtreeID << '\n');
1361 }
1362 for (const auto &[Pred, Succ] : ConnectionPairs) {
1363 unsigned PredTree = SubtreeClasses[Pred->NodeNum];
1364 unsigned SuccTree = SubtreeClasses[Succ->NodeNum];
1365 if (PredTree == SuccTree)
1366 continue;
1367 unsigned Depth = Pred->getDepth();
1368 addConnection(PredTree, SuccTree, Depth);
1369 addConnection(SuccTree, PredTree, Depth);
1370 }
1371 }
1372
1373protected:
1374 /// Joins the predecessor subtree with the successor that is its DFS parent.
1375 /// Applies some heuristics before joining.
1376 bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ,
1377 bool CheckLimit = true) {
1378 assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges");
1379
1380 // Check if the predecessor is already joined.
1381 const SUnit *PredSU = PredDep.getSUnit();
1382 unsigned PredNum = PredSU->NodeNum;
1383 if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1384 return false;
1385
1386 // Four is the magic number of successors before a node is considered a
1387 // pinch point.
1388 unsigned NumDataSucs = 0;
1389 for (const SDep &SuccDep : PredSU->Succs) {
1390 if (SuccDep.getKind() == SDep::Data) {
1391 if (++NumDataSucs >= 4)
1392 return false;
1393 }
1394 }
1395 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1396 return false;
1397 R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum;
1398 SubtreeClasses.join(Succ->NodeNum, PredNum);
1399 return true;
1400 }
1401
1402 /// Called by finalize() to record a connection between trees.
1403 void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) {
1404 if (!Depth)
1405 return;
1406
1407 do {
1409 R.SubtreeConnections[FromTree];
1410 for (SchedDFSResult::Connection &C : Connections) {
1411 if (C.TreeID == ToTree) {
1412 C.Level = std::max(C.Level, Depth);
1413 return;
1414 }
1415 }
1416 Connections.push_back(SchedDFSResult::Connection(ToTree, Depth));
1417 FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1418 } while (FromTree != SchedDFSResult::InvalidSubtreeID);
1419 }
1420};
1421
1422} // end namespace llvm
1423
1424namespace {
1425
1426/// Manage the stack used by a reverse depth-first search over the DAG.
1427class SchedDAGReverseDFS {
1428 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1429
1430public:
1431 bool isComplete() const { return DFSStack.empty(); }
1432
1433 void follow(const SUnit *SU) {
1434 DFSStack.emplace_back(SU, SU->Preds.begin());
1435 }
1436 void advance() { ++DFSStack.back().second; }
1437
1438 const SDep *backtrack() {
1439 DFSStack.pop_back();
1440 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1441 }
1442
1443 const SUnit *getCurr() const { return DFSStack.back().first; }
1444
1445 SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; }
1446
1447 SUnit::const_pred_iterator getPredEnd() const {
1448 return getCurr()->Preds.end();
1449 }
1450};
1451
1452} // end anonymous namespace
1453
1454static bool hasDataSucc(const SUnit *SU) {
1455 for (const SDep &SuccDep : SU->Succs) {
1456 if (SuccDep.getKind() == SDep::Data &&
1457 !SuccDep.getSUnit()->isBoundaryNode())
1458 return true;
1459 }
1460 return false;
1461}
1462
1463/// Computes an ILP metric for all nodes in the subDAG reachable via depth-first
1464/// search from this root.
1466 if (!IsBottomUp)
1467 llvm_unreachable("Top-down ILP metric is unimplemented");
1468
1469 SchedDFSImpl Impl(*this);
1470 for (const SUnit &SU : SUnits) {
1471 if (Impl.isVisited(&SU) || hasDataSucc(&SU))
1472 continue;
1473
1474 SchedDAGReverseDFS DFS;
1475 Impl.visitPreorder(&SU);
1476 DFS.follow(&SU);
1477 while (true) {
1478 // Traverse the leftmost path as far as possible.
1479 while (DFS.getPred() != DFS.getPredEnd()) {
1480 const SDep &PredDep = *DFS.getPred();
1481 DFS.advance();
1482 // Ignore non-data edges.
1483 if (PredDep.getKind() != SDep::Data
1484 || PredDep.getSUnit()->isBoundaryNode()) {
1485 continue;
1486 }
1487 // An already visited edge is a cross edge, assuming an acyclic DAG.
1488 if (Impl.isVisited(PredDep.getSUnit())) {
1489 Impl.visitCrossEdge(PredDep, DFS.getCurr());
1490 continue;
1491 }
1492 Impl.visitPreorder(PredDep.getSUnit());
1493 DFS.follow(PredDep.getSUnit());
1494 }
1495 // Visit the top of the stack in postorder and backtrack.
1496 const SUnit *Child = DFS.getCurr();
1497 const SDep *PredDep = DFS.backtrack();
1498 Impl.visitPostorderNode(Child);
1499 if (PredDep)
1500 Impl.visitPostorderEdge(*PredDep, DFS.getCurr());
1501 if (DFS.isComplete())
1502 break;
1503 }
1504 }
1505 Impl.finalize();
1506}
1507
1508/// The root of the given SubtreeID was just scheduled. For all subtrees
1509/// connected to this tree, record the depth of the connection so that the
1510/// nearest connected subtrees can be prioritized.
1511void SchedDFSResult::scheduleTree(unsigned SubtreeID) {
1512 for (const Connection &C : SubtreeConnections[SubtreeID]) {
1513 SubtreeConnectLevels[C.TreeID] =
1514 std::max(SubtreeConnectLevels[C.TreeID], C.Level);
1515 LLVM_DEBUG(dbgs() << " Tree: " << C.TreeID << " @"
1516 << SubtreeConnectLevels[C.TreeID] << '\n');
1517 }
1518}
1519
1520#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1522 OS << InstrCount << " / " << Length << " = ";
1523 if (!Length)
1524 OS << "BADILP";
1525 else
1526 OS << format("%g", ((double)InstrCount / Length));
1527}
1528
1530 dbgs() << *this << '\n';
1531}
1532
1533namespace llvm {
1534
1537 Val.print(OS);
1538 return OS;
1539}
1540
1541} // end namespace llvm
1542
1543#endif
unsigned SubReg
static cl::opt< bool > UseAA("aarch64-use-aa", cl::init(true), cl::desc("Enable the use of AA during codegen."))
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:622
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:282
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static unsigned InstrCount
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(...)
Definition: Debug.h:106
bool End
Definition: ELF_riscv.cpp:480
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:235
static Register UseReg(const MachineOperand &MO)
hexagon widen Hexagon Store false hexagon widen loads
hexagon widen stores
IRTranslator LLVM IR MI
Equivalence classes for small integers.
A common definition of LaneBitmask for use in TableGen and CodeGen.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
static void toggleKills(const MachineRegisterInfo &MRI, LiveRegUnits &LiveRegs, MachineInstr &MI, bool addToLiveRegs)
static cl::opt< unsigned > ReductionSize("dag-maps-reduction-size", cl::Hidden, cl::desc("A huge scheduling region will have maps reduced by this many " "nodes at a time. Defaults to HugeRegion / 2."))
static bool getUnderlyingObjectsForInstr(const MachineInstr *MI, const MachineFrameInfo &MFI, UnderlyingObjectsVector &Objects, const DataLayout &DL)
If this machine instr has memory reference information and it can be tracked to a normal reference to...
static bool hasDataSucc(const SUnit *SU)
static cl::opt< bool > EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::desc("Enable use of AA during MI DAG construction"))
static cl::opt< unsigned > HugeRegion("dag-maps-huge-region", cl::Hidden, cl::init(1000), cl::desc("The limit to use while constructing the DAG " "prior to scheduling, at which point a trade-off " "is made to avoid excessive compile time."))
static unsigned getReductionSize()
static void dumpSUList(const ScheduleDAGInstrs::SUList &L)
static cl::opt< bool > UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"))
static cl::opt< bool > SchedPrintCycles("sched-print-cycles", cl::Hidden, cl::init(false), cl::desc("Report top/bottom cycles when dumping SUnit instances"))
This file defines the SmallVector class.
This file defines the SparseSet class derived from the version described in Briggs,...
void reComputeSize()
Counts the number of SUs in this map after a reduction.
void insert(SUnit *SU, ValueType V)
Adds SU to the SUList of V.
void clear()
Clears map from all contents.
void clearList(ValueType V)
Clears the list of SUs mapped to V.
ValueType & operator[](const SUList &Key)
To keep NumNodes up to date, insert() is used instead of this operator w/ push_back().
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
void compress()
compress - Compress equivalence classes by numbering them 0 .
unsigned getNumClasses() const
getNumClasses - Return the number of equivalence classes after compress() was called.
Definition: IntEqClasses.h:72
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:116
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
Definition: LiveRegUnits.h:73
void addReg(MCPhysReg Reg)
Adds register units covered by physical register Reg.
Definition: LiveRegUnits.h:86
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
void removeRegsNotPreserved(const uint32_t *RegMask)
Removes register units not preserved by the regmask RegMask.
void removeReg(MCPhysReg Reg)
Removes all register units covered by physical register Reg.
Definition: LiveRegUnits.h:102
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 hasImplicitUseOfPhysReg(MCRegister Reg) const
Return true if this instruction implicitly uses the specified physical register.
Definition: MCInstrDesc.h:587
bool hasImplicitDefOfPhysReg(MCRegister Reg, const MCRegisterInfo *MRI=nullptr) const
Return true if this instruction implicitly defines the specified physical register.
Definition: MCInstrDesc.cpp:32
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Instructions::iterator instr_iterator
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
iterator_range< succ_iterator > successors()
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool hasTailCall() const
Returns true if the function contains a tail call.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
Representation of each machine instruction.
Definition: MachineInstr.h:69
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:972
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:956
iterator_range< filtered_mop_iterator > all_uses()
Returns an iterator range over all operands that are (explicit or implicit) register uses.
Definition: MachineInstr.h:772
bool mayAlias(AAResults *AA, const MachineInstr &Other, bool UseTBAA) const
Returns true if this instruction's memory access aliases the memory access of Other.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:572
void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
bool isTransient() const
Return true if this is a transient instruction that is either very likely to be eliminated during reg...
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:585
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setIsKill(bool Val=true)
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
typename VectorType::iterator iterator
Definition: MapVector.h:49
iterator end()
Definition: MapVector.h:71
ValueT & operator[](const KeyT &Key)
Definition: MapVector.h:98
iterator find(const KeyT &Key)
Definition: MapVector.h:167
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
iterator begin()
Definition: MapVector.h:69
Array of PressureDiffs.
void addInstruction(unsigned Idx, const RegisterOperands &RegOpers, const MachineRegisterInfo &MRI)
Record pressure difference induced by the given operand list to node with index Idx.
void init(unsigned N)
Initialize an array of N PressureDiffs.
Special value supplied for machine level alias analysis.
Track the current register pressure at some position in the instruction stream, and remember the high...
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
void recedeSkipDebugValues()
Recede until we find an instruction which is not a DebugValue.
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
List of registers defined and used by a machine instruction.
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)
Use liveness information to find out which uses/defs are partially undefined/dead and adjust the Regi...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
Scheduling dependency.
Definition: ScheduleDAG.h:49
SUnit * getSUnit() const
Definition: ScheduleDAG.h:498
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:504
Kind
These are the different kinds of scheduling dependencies.
Definition: ScheduleDAG.h:52
@ Output
A register output-dependence (aka WAW).
Definition: ScheduleDAG.h:55
@ Anti
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:54
@ 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
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Definition: ScheduleDAG.h:72
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
Definition: ScheduleDAG.h:70
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Definition: ScheduleDAG.h:200
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
bool isCall
Is a function call.
Definition: ScheduleDAG.h:287
bool addPredBarrier(SUnit *SU)
Adds a barrier edge to SU by calling addPred(), with latency 0 generally or latency 1 for a store fol...
Definition: ScheduleDAG.h:402
unsigned NumSuccs
Definition: ScheduleDAG.h:273
unsigned TopReadyCycle
Cycle relative to start when node is ready.
Definition: ScheduleDAG.h:278
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:270
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:300
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
Definition: ScheduleDAG.h:267
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
Definition: ScheduleDAG.h:382
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:303
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
Definition: ScheduleDAG.h:358
bool hasPhysRegDefs
Has physreg defs that are being used.
Definition: ScheduleDAG.h:292
unsigned BotReadyCycle
Cycle relative to end when node is ready.
Definition: ScheduleDAG.h:279
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:263
bool hasReservedResource
Uses a reserved resource.
Definition: ScheduleDAG.h:301
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:290
bool hasPhysRegUses
Has physreg uses.
Definition: ScheduleDAG.h:291
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:262
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:390
Internal state used to compute SchedDFSResult.
void visitPostorderNode(const SUnit *SU)
Called once for each node after all predecessors are visited.
bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, bool CheckLimit=true)
Joins the predecessor subtree with the successor that is its DFS parent.
void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth)
Called by finalize() to record a connection between trees.
void finalize()
Sets each node's subtree ID to the representative ID and record connections between trees.
void visitCrossEdge(const SDep &PredDep, const SUnit *Succ)
Adds a connection for cross edges.
void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ)
Called once for each tree edge after calling visitPostOrderNode on the predecessor.
void visitPreorder(const SUnit *SU)
Initializes this node's instruction count.
bool isVisited(const SUnit *SU) const
Returns true if this node been visited by the DFS traversal.
SchedDFSImpl(SchedDFSResult &r)
Compute the values of each DAG node for various metrics during DFS.
Definition: ScheduleDFS.h:65
void compute(ArrayRef< SUnit > SUnits)
Compute various metrics for the DAG with given roots.
void scheduleTree(unsigned SubtreeID)
Scheduler callback to update SubtreeConnectLevels when a tree is initially scheduled.
LiveRegUnits LiveRegs
Set of live physical registers for updating kill flags.
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
void addVRegUseDeps(SUnit *SU, unsigned OperIdx)
Adds a register data dependency if the instruction that defines the virtual register used at OperIdx ...
void addVRegDefDeps(SUnit *SU, unsigned OperIdx)
Adds register output and data dependencies from this SUnit to instructions that occur later in the sa...
virtual void finishBlock()
Cleans up after scheduling in the given block.
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
std::string getDAGName() const override
Returns a label for the region of code covered by the DAG.
MachineBasicBlock * BB
The block in which to insert instructions.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
void addBarrierChain(Value2SUsMap &map)
Adds barrier chain edges from all SUs in map, and then clear the map.
void reduceHugeMemNodeMaps(Value2SUsMap &stores, Value2SUsMap &loads, unsigned N)
Reduces maps in FIFO order, by N SUs.
void addPhysRegDeps(SUnit *SU, unsigned OperIdx)
Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the ...
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
void fixupKills(MachineBasicBlock &MBB)
Fixes register kill flags that scheduling has made invalid.
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx)
MO is an operand of SU's instruction that defines a physical register.
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const
Returns a mask for which lanes get read/written by the given (register) machine operand.
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
void initSUnits()
Creates an SUnit for each real instruction, numbered in top-down topological order.
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
std::list< SUnit * > SUList
A list of SUnits, used in Value2SUsMap, during DAG construction.
SUnit * BarrierChain
Remember a generic side-effecting instruction as we proceed.
bool TrackLaneMasks
Whether lane masks should get tracked.
void dumpNode(const SUnit &SU) const override
RegUnit2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
void insertBarrierChain(Value2SUsMap &map)
Inserts a barrier chain in a huge region, far below current SU.
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
void addSchedBarrierDeps()
Adds dependencies from instructions in the current list of instructions being scheduled to scheduling...
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
void dump() const override
void addChainDependency(SUnit *SUa, SUnit *SUb, unsigned Latency=0)
Adds a chain edge between SUa and SUb, but only if both AAResults and Target fail to deny the depende...
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
const MachineFrameInfo & MFI
bool deadDefHasNoUse(const MachineOperand &MO)
Returns true if the def register in MO has no uses.
std::string getGraphNodeLabel(const SUnit *SU) const override
Returns a label for a DAG node that points to an instruction.
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
Definition: ScheduleDAG.h:794
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
void AddPredQueued(SUnit *Y, SUnit *X)
Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:578
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:63
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:575
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:579
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:576
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:580
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:577
void dumpNodeAll(const SUnit &SU) const
void dumpNodeName(const SUnit &SU) const
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:581
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:65
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
iterator find(const KeyT &Key)
Find an element by its key.
bool empty() const
Returns true if the set is empty.
bool contains(const KeyT &Key) const
Returns true if this set contains an element identified by Key.
void clear()
Clears the set.
iterator erase(iterator I)
Erases an existing element identified by a valid iterator.
iterator end()
Returns an iterator past this container.
iterator insert(const ValueT &Val)
Insert a new element at the tail of the subset list.
void eraseAll(const KeyT &K)
Erase all elements with the given key.
RangePair equal_range(const KeyT &K)
The bounds of the range of items sharing Key K.
void setUniverse(unsigned U)
Set the universe size which determines the largest key the set can hold.
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
Definition: SparseSet.h:124
size_type size() const
size - Returns the number of elements in the set.
Definition: SparseSet.h:194
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:293
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
Definition: SparseSet.h:245
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:160
TargetInstrInfo - Interface to description of machine instruction set.
virtual bool isGlobalMemoryObject(const MachineInstr *MI) const
Returns true if MI is an instruction we are unable to reason about (like a call or something with unm...
const bool HasDisjunctSubRegs
Whether the class supports two (or more) disjunct subregister indices.
LaneBitmask getLaneMask() const
Returns the combination of all lane masks of register in this class.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *DepMI) const
Output dependency latency of a pair of defs of the same register.
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const
Compute operand latency based on the available machine model.
const MCProcResourceDesc * getProcResource(unsigned PIdx) const
Get a processor resource by ID for convenience.
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
TargetSubtargetInfo - Generic base class for all target subtargets.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
'undef' values are things that do not have specified contents.
Definition: Constants.h:1412
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
int getNumOccurrences() const
Definition: CommandLine.h:399
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:661
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
@ Length
Definition: DWP.cpp:480
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1697
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:420
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1664
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
IterT skipDebugInstructionsBackward(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:303
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
#define N
Represent the ILP of the subDAG rooted at a DAG node.
Definition: ScheduleDFS.h:34
void print(raw_ostream &OS) const
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
constexpr bool any() const
Definition: LaneBitmask.h:53
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:121
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
Definition: MCSchedule.h:66
Record a physical register access.
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:254
Mapping from virtual register to SUnit including an operand index.
An individual mapping from virtual register number to SUnit.