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