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
14#include "llvm/CodeGen/ScheduleDAGInstrs.h"
15
16#include "llvm/ADT/IntEqClasses.h"
17#include "llvm/ADT/MapVector.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/SparseSet.h"
20#include "llvm/ADT/iterator_range.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/CodeGen/LiveIntervals.h"
24#include "llvm/CodeGen/LivePhysRegs.h"
25#include "llvm/CodeGen/MachineBasicBlock.h"
26#include "llvm/CodeGen/MachineFrameInfo.h"
27#include "llvm/CodeGen/MachineFunction.h"
28#include "llvm/CodeGen/MachineInstr.h"
29#include "llvm/CodeGen/MachineInstrBundle.h"
30#include "llvm/CodeGen/MachineMemOperand.h"
31#include "llvm/CodeGen/MachineOperand.h"
32#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/CodeGen/PseudoSourceValue.h"
34#include "llvm/CodeGen/RegisterPressure.h"
35#include "llvm/CodeGen/ScheduleDAG.h"
36#include "llvm/CodeGen/ScheduleDFS.h"
37#include "llvm/CodeGen/SlotIndexes.h"
38#include "llvm/CodeGen/TargetInstrInfo.h"
39#include "llvm/CodeGen/TargetRegisterInfo.h"
40#include "llvm/CodeGen/TargetSubtargetInfo.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"
47#include "llvm/MC/MCRegisterInfo.h"
48#include "llvm/Support/Casting.h"
49#include "llvm/Support/CommandLine.h"
50#include "llvm/Support/Compiler.h"
51#include "llvm/Support/Debug.h"
52#include "llvm/Support/ErrorHandling.h"
53#include "llvm/Support/Format.h"
54#include "llvm/Support/raw_ostream.h"
55#include <algorithm>
56#include <cassert>
57#include <iterator>
58#include <list>
59#include <utility>
60#include <vector>
61
62using namespace llvm;
63
64#define DEBUG_TYPE "machine-scheduler"
65
66static cl::opt<bool>
67 EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
68 cl::desc("Enable use of AA during MI DAG construction"));
69
70static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
71 cl::init(Val: true), cl::desc("Enable use of TBAA during MI DAG construction"));
72
73static cl::opt<bool>
74 EnableSchedModel("schedmodel", cl::Hidden, cl::init(Val: true),
75 cl::desc("Use TargetSchedModel for latency lookup"));
76
77static cl::opt<bool>
78 EnableSchedItins("scheditins", cl::Hidden, cl::init(Val: true),
79 cl::desc("Use InstrItineraryData for latency lookup"));
80
81// Note: the two options below might be used in tuning compile time vs
82// output quality. Setting HugeRegion so large that it will never be
83// reached means best-effort, but may be slow.
84
85// When Stores and Loads maps together hold this many SUs, a reduction of maps
86// will be done.
87static cl::opt<unsigned>
88 HugeRegion("dag-maps-huge-region", cl::Hidden, cl::init(Val: 500),
89 cl::desc("The limit to use while constructing the DAG "
90 "prior to scheduling, at which point a trade-off "
91 "is made to avoid excessive compile time."));
92
93static cl::opt<bool> EnableStoreSequencing(
94 "enable-unanalyzable-store-sequencing", cl::Hidden, cl::init(Val: false),
95 cl::desc("Enable the store-sequencing DAG construction algorithm. This can "
96 "eliminate a large number of redundant control dependencies and "
97 "spurious alias analysis queries at the cost of some unnecessary "
98 "dependencies."));
99
100#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
101static cl::opt<bool> SchedPrintCycles(
102 "sched-print-cycles", cl::Hidden, cl::init(false),
103 cl::desc("Report top/bottom cycles when dumping SUnit instances"));
104#endif
105
106ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
107 const MachineLoopInfo *mli,
108 bool RemoveKillFlags)
109 : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
110 RemoveKillFlags(RemoveKillFlags), Topo(SUnits, &ExitSU) {
111 DbgValues.clear();
112
113 const TargetSubtargetInfo &ST = mf.getSubtarget();
114 SchedModel.init(TSInfo: &ST, EnableSModel: EnableSchedModel, EnableSItins: EnableSchedItins);
115}
116
117/// If this machine instruction has memory reference information, collect the
118/// list of underlying objects in \p Objects. If any of these objects are
119/// unknown or may alias anything, return false. Atomic and volatile memory
120/// operands are skipped.
121static bool getUnderlyingObjectsForInstr(const MachineInstr *MI,
122 const MachineFrameInfo &MFI,
123 UnderlyingObjectsVector &Objects,
124 const DataLayout &DL) {
125 bool AllObjectsIdentified = true;
126
127 for (const MachineMemOperand *MMO : MI->memoperands()) {
128 // TODO: Figure out whether isAtomic is really necessary (see D57601).
129 if (MMO->isVolatile() || MMO->isAtomic()) {
130 AllObjectsIdentified = false;
131 continue;
132 }
133
134 if (const PseudoSourceValue *PSV = MMO->getPseudoValue()) {
135 if (MFI.hasTailCall()) {
136 // Function that contain tail calls don't have unique PseudoSourceValue
137 // objects. Two PseudoSourceValues might refer to the same or
138 // overlapping locations. The client code calling this function assumes
139 // this is not the case. So return a conservative answer of no known
140 // object.
141 AllObjectsIdentified = false;
142 } else if (PSV->isAliased(&MFI)) {
143 // For now, ignore PseudoSourceValues which may alias LLVM IR values
144 // because the code that uses this function has no way to cope with such
145 // aliases.
146 AllObjectsIdentified = false;
147 }
148
149 Objects.push_back(Elt: PSV);
150 } else if (const Value *V = MMO->getValue()) {
151 SmallVector<Value *, 4> Objs;
152 bool ObjectsIdentified = getUnderlyingObjectsForCodeGen(V, Objects&: Objs);
153 AllObjectsIdentified &= ObjectsIdentified;
154
155 for (Value *V : Objs) {
156 assert(!ObjectsIdentified || isIdentifiedObject(V));
157 Objects.push_back(Elt: V);
158 }
159 } else {
160 AllObjectsIdentified = false;
161 }
162 }
163
164 return AllObjectsIdentified;
165}
166
167void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) {
168 BB = bb;
169}
170
171void ScheduleDAGInstrs::finishBlock() {
172 // Subclasses should no longer refer to the old block.
173 BB = nullptr;
174}
175
176void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb,
177 MachineBasicBlock::iterator begin,
178 MachineBasicBlock::iterator end,
179 unsigned regioninstrs) {
180 assert(bb == BB && "startBlock should set BB");
181 RegionBegin = begin;
182 RegionEnd = end;
183 NumRegionInstrs = regioninstrs;
184}
185
186void ScheduleDAGInstrs::exitRegion() {
187 // Nothing to do.
188}
189
190void ScheduleDAGInstrs::addSchedBarrierDeps() {
191 MachineInstr *ExitMI =
192 RegionEnd != BB->end()
193 ? &*skipDebugInstructionsBackward(It: RegionEnd, Begin: RegionBegin)
194 : nullptr;
195 ExitSU.setInstr(ExitMI);
196 // Add dependencies on the defs and uses of the instruction.
197 if (ExitMI) {
198 const MCInstrDesc &MIDesc = ExitMI->getDesc();
199 for (const MachineOperand &MO : ExitMI->all_uses()) {
200 unsigned OpIdx = MO.getOperandNo();
201 Register Reg = MO.getReg();
202 if (Reg.isPhysical()) {
203 // addPhysRegDataDeps uses the provided operand index to retrieve
204 // the operand use cycle from the scheduling model. If the operand
205 // is "fake" (e.g., an operand of a call instruction used to pass
206 // an argument to the called function.), the scheduling model may not
207 // have an entry for it. If this is the case, pass -1 as operand index,
208 // which will cause addPhysRegDataDeps to add an artificial dependency.
209 // FIXME: Using hasImplicitUseOfPhysReg here is inaccurate as it misses
210 // aliases. When fixing, make sure to update addPhysRegDataDeps, too.
211 bool IsRealUse = OpIdx < MIDesc.getNumOperands() ||
212 MIDesc.hasImplicitUseOfPhysReg(Reg);
213 for (MCRegUnit Unit : TRI->regunits(Reg))
214 Uses.insert(Val: PhysRegSUOper(&ExitSU, IsRealUse ? OpIdx : -1, Unit));
215 } else if (Reg.isVirtual() && MO.readsReg()) {
216 addVRegUseDeps(SU: &ExitSU, OperIdx: OpIdx);
217 }
218 }
219 }
220 if (!ExitMI || (!ExitMI->isCall() && !ExitMI->isBarrier())) {
221 // For others, e.g. fallthrough, conditional branch, assume the exit
222 // uses all the registers that are livein to the successor blocks.
223 for (const MachineBasicBlock *Succ : BB->successors()) {
224 for (const auto &LI : Succ->liveins()) {
225 for (MCRegUnitMaskIterator U(LI.PhysReg, TRI); U.isValid(); ++U) {
226 auto [Unit, Mask] = *U;
227 if ((Mask & LI.LaneMask).any() && !Uses.contains(Key: Unit))
228 Uses.insert(Val: PhysRegSUOper(&ExitSU, -1, Unit));
229 }
230 }
231 }
232 }
233}
234
235/// MO is an operand of SU's instruction that defines a physical register. Adds
236/// data dependencies from SU to any uses of the physical register.
237void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) {
238 const MachineOperand &MO = SU->getInstr()->getOperand(i: OperIdx);
239 assert(MO.isDef() && "expect physreg def");
240 Register Reg = MO.getReg();
241
242 // Ask the target if address-backscheduling is desirable, and if so how much.
243 const TargetSubtargetInfo &ST = MF.getSubtarget();
244
245 // Only use any non-zero latency for real defs/uses, in contrast to
246 // "fake" operands added by regalloc.
247 const MCInstrDesc &DefMIDesc = SU->getInstr()->getDesc();
248 bool ImplicitPseudoDef = (OperIdx >= DefMIDesc.getNumOperands() &&
249 !DefMIDesc.hasImplicitDefOfPhysReg(Reg));
250 for (MCRegUnit Unit : TRI->regunits(Reg)) {
251 for (RegUnit2SUnitsMap::iterator I = Uses.find(Key: Unit); I != Uses.end();
252 ++I) {
253 SUnit *UseSU = I->SU;
254 if (UseSU == SU)
255 continue;
256
257 // Adjust the dependence latency using operand def/use information,
258 // then allow the target to perform its own adjustments.
259 MachineInstr *UseInstr = nullptr;
260 int UseOpIdx = I->OpIdx;
261 bool ImplicitPseudoUse = false;
262 SDep Dep;
263 if (UseOpIdx < 0) {
264 Dep = SDep(SU, SDep::Artificial);
265 } else {
266 // Set the hasPhysRegDefs only for physreg defs that have a use within
267 // the scheduling region.
268 SU->hasPhysRegDefs = true;
269
270 UseInstr = UseSU->getInstr();
271 Register UseReg = UseInstr->getOperand(i: UseOpIdx).getReg();
272 const MCInstrDesc &UseMIDesc = UseInstr->getDesc();
273 ImplicitPseudoUse = UseOpIdx >= ((int)UseMIDesc.getNumOperands()) &&
274 !UseMIDesc.hasImplicitUseOfPhysReg(Reg: UseReg);
275
276 Dep = SDep(SU, SDep::Data, UseReg);
277 }
278 if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
279 Dep.setLatency(SchedModel.computeOperandLatency(DefMI: SU->getInstr(), DefOperIdx: OperIdx,
280 UseMI: UseInstr, UseOperIdx: UseOpIdx));
281 } else {
282 Dep.setLatency(0);
283 }
284 ST.adjustSchedDependency(Def: SU, DefOpIdx: OperIdx, Use: UseSU, UseOpIdx, Dep, SchedModel: &SchedModel);
285 UseSU->addPred(D: Dep);
286 }
287 }
288}
289
290/// Adds register dependencies (data, anti, and output) from this SUnit
291/// to following instructions in the same scheduling region that depend the
292/// physical register referenced at OperIdx.
293void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
294 MachineInstr *MI = SU->getInstr();
295 MachineOperand &MO = MI->getOperand(i: OperIdx);
296 Register Reg = MO.getReg();
297 // We do not need to track any dependencies for constant registers.
298 if (MRI.isConstantPhysReg(PhysReg: Reg))
299 return;
300
301 const TargetSubtargetInfo &ST = MF.getSubtarget();
302
303 // Optionally add output and anti dependencies. For anti
304 // dependencies we use a latency of 0 because for a multi-issue
305 // target we want to allow the defining instruction to issue
306 // in the same cycle as the using instruction.
307 // TODO: Using a latency of 1 here for output dependencies assumes
308 // there's no cost for reusing registers.
309 SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
310 for (MCRegUnit Unit : TRI->regunits(Reg)) {
311 for (RegUnit2SUnitsMap::iterator I = Defs.find(Key: Unit); I != Defs.end();
312 ++I) {
313 SUnit *DefSU = I->SU;
314 if (DefSU == &ExitSU)
315 continue;
316 MachineInstr *DefInstr = DefSU->getInstr();
317 MachineOperand &DefMO = DefInstr->getOperand(i: I->OpIdx);
318 if (DefSU != SU &&
319 (Kind != SDep::Output || !MO.isDead() || !DefMO.isDead())) {
320 SDep Dep(SU, Kind, DefMO.getReg());
321 if (Kind != SDep::Anti) {
322 Dep.setLatency(
323 SchedModel.computeOutputLatency(DefMI: MI, DefOperIdx: OperIdx, DepMI: DefInstr));
324 }
325 ST.adjustSchedDependency(Def: SU, DefOpIdx: OperIdx, Use: DefSU, UseOpIdx: I->OpIdx, Dep,
326 SchedModel: &SchedModel);
327 DefSU->addPred(D: Dep);
328 }
329 }
330 }
331
332 if (MO.isUse()) {
333 SU->hasPhysRegUses = true;
334 // Either insert a new Reg2SUnits entry with an empty SUnits list, or
335 // retrieve the existing SUnits list for this register's uses.
336 // Push this SUnit on the use list.
337 for (MCRegUnit Unit : TRI->regunits(Reg))
338 Uses.insert(Val: PhysRegSUOper(SU, OperIdx, Unit));
339 if (RemoveKillFlags)
340 MO.setIsKill(false);
341 } else {
342 addPhysRegDataDeps(SU, OperIdx);
343
344 // Clear previous uses and defs of this register and its subregisters.
345 for (MCRegUnit Unit : TRI->regunits(Reg)) {
346 Uses.eraseAll(K: Unit);
347 if (!MO.isDead())
348 Defs.eraseAll(K: Unit);
349 }
350
351 if (MO.isDead() && SU->isCall) {
352 // Calls will not be reordered because of chain dependencies (see
353 // below). Since call operands are dead, calls may continue to be added
354 // to the DefList making dependence checking quadratic in the size of
355 // the block. Instead, we leave only one call at the back of the
356 // DefList.
357 for (MCRegUnit Unit : TRI->regunits(Reg)) {
358 RegUnit2SUnitsMap::RangePair P = Defs.equal_range(K: Unit);
359 RegUnit2SUnitsMap::iterator B = P.first;
360 RegUnit2SUnitsMap::iterator I = P.second;
361 for (bool isBegin = I == B; !isBegin; /* empty */) {
362 isBegin = (--I) == B;
363 if (!I->SU->isCall)
364 break;
365 I = Defs.erase(I);
366 }
367 }
368 }
369
370 // Defs are pushed in the order they are visited and never reordered.
371 for (MCRegUnit Unit : TRI->regunits(Reg))
372 Defs.insert(Val: PhysRegSUOper(SU, OperIdx, Unit));
373 }
374}
375
376LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const
377{
378 Register Reg = MO.getReg();
379 // No point in tracking lanemasks if we don't have interesting subregisters.
380 const TargetRegisterClass &RC = *MRI.getRegClass(Reg);
381 if (!RC.HasDisjunctSubRegs)
382 return LaneBitmask::getAll();
383
384 unsigned SubReg = MO.getSubReg();
385 if (SubReg == 0)
386 return RC.getLaneMask();
387 return TRI->getSubRegIndexLaneMask(SubIdx: SubReg);
388}
389
390bool ScheduleDAGInstrs::deadDefHasNoUse(const MachineOperand &MO) {
391 auto RegUse = CurrentVRegUses.find(Key: MO.getReg());
392 if (RegUse == CurrentVRegUses.end())
393 return true;
394 return (RegUse->LaneMask & getLaneMaskForMO(MO)).none();
395}
396
397/// Adds register output and data dependencies from this SUnit to instructions
398/// that occur later in the same scheduling region if they read from or write to
399/// the virtual register defined at OperIdx.
400///
401/// TODO: Hoist loop induction variable increments. This has to be
402/// reevaluated. Generally, IV scheduling should be done before coalescing.
403void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
404 MachineInstr *MI = SU->getInstr();
405 MachineOperand &MO = MI->getOperand(i: OperIdx);
406 Register Reg = MO.getReg();
407
408 LaneBitmask DefLaneMask;
409 LaneBitmask KillLaneMask;
410 if (TrackLaneMasks) {
411 bool IsKill = MO.getSubReg() == 0 || MO.isUndef();
412 DefLaneMask = getLaneMaskForMO(MO);
413 // If we have a <read-undef> flag, none of the lane values comes from an
414 // earlier instruction.
415 KillLaneMask = IsKill ? LaneBitmask::getAll() : DefLaneMask;
416
417 if (MO.getSubReg() != 0 && MO.isUndef()) {
418 // There may be other subregister defs on the same instruction of the same
419 // register in later operands. The lanes of other defs will now be live
420 // after this instruction, so these should not be treated as killed by the
421 // instruction even though they appear to be killed in this one operand.
422 for (const MachineOperand &OtherMO :
423 llvm::drop_begin(RangeOrContainer: MI->operands(), N: OperIdx + 1))
424 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
425 KillLaneMask &= ~getLaneMaskForMO(MO: OtherMO);
426 }
427
428 // Clear undef flag, we'll re-add it later once we know which subregister
429 // Def is first.
430 MO.setIsUndef(false);
431 } else {
432 DefLaneMask = LaneBitmask::getAll();
433 KillLaneMask = LaneBitmask::getAll();
434 }
435
436 if (MO.isDead()) {
437 assert(deadDefHasNoUse(MO) && "Dead defs should have no uses");
438 } else {
439 // Add data dependence to all uses we found so far.
440 const TargetSubtargetInfo &ST = MF.getSubtarget();
441 for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Key: Reg),
442 E = CurrentVRegUses.end(); I != E; /*empty*/) {
443 LaneBitmask LaneMask = I->LaneMask;
444 // Ignore uses of other lanes.
445 if ((LaneMask & KillLaneMask).none()) {
446 ++I;
447 continue;
448 }
449
450 if ((LaneMask & DefLaneMask).any()) {
451 SUnit *UseSU = I->SU;
452 MachineInstr *Use = UseSU->getInstr();
453 SDep Dep(SU, SDep::Data, Reg);
454 Dep.setLatency(SchedModel.computeOperandLatency(DefMI: MI, DefOperIdx: OperIdx, UseMI: Use,
455 UseOperIdx: I->OperandIndex));
456 ST.adjustSchedDependency(Def: SU, DefOpIdx: OperIdx, Use: UseSU, UseOpIdx: I->OperandIndex, Dep,
457 SchedModel: &SchedModel);
458 UseSU->addPred(D: Dep);
459 }
460
461 LaneMask &= ~KillLaneMask;
462 // If we found a Def for all lanes of this use, remove it from the list.
463 if (LaneMask.any()) {
464 I->LaneMask = LaneMask;
465 ++I;
466 } else
467 I = CurrentVRegUses.erase(I);
468 }
469 }
470
471 // Shortcut: Singly defined vregs do not have output/anti dependencies.
472 if (MRI.hasOneDef(RegNo: Reg))
473 return;
474
475 // Add output dependence to the next nearest defs of this vreg.
476 //
477 // Unless this definition is dead, the output dependence should be
478 // transitively redundant with antidependencies from this definition's
479 // uses. We're conservative for now until we have a way to guarantee the uses
480 // are not eliminated sometime during scheduling. The output dependence edge
481 // is also useful if output latency exceeds def-use latency.
482 LaneBitmask LaneMask = DefLaneMask;
483 for (VReg2SUnit &V2SU : make_range(x: CurrentVRegDefs.find(Key: Reg),
484 y: CurrentVRegDefs.end())) {
485 // Ignore defs for other lanes.
486 if ((V2SU.LaneMask & LaneMask).none())
487 continue;
488 // Add an output dependence.
489 SUnit *DefSU = V2SU.SU;
490 // Ignore additional defs of the same lanes in one instruction. This can
491 // happen because lanemasks are shared for targets with too many
492 // subregisters. We also use some representration tricks/hacks where we
493 // add super-register defs/uses, to imply that although we only access parts
494 // of the reg we care about the full one.
495 if (DefSU == SU)
496 continue;
497 SDep Dep(SU, SDep::Output, Reg);
498 Dep.setLatency(
499 SchedModel.computeOutputLatency(DefMI: MI, DefOperIdx: OperIdx, DepMI: DefSU->getInstr()));
500 DefSU->addPred(D: Dep);
501
502 // Update current definition. This can get tricky if the def was about a
503 // bigger lanemask before. We then have to shrink it and create a new
504 // VReg2SUnit for the non-overlapping part.
505 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
506 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
507 V2SU.SU = SU;
508 V2SU.LaneMask = OverlapMask;
509 if (NonOverlapMask.any())
510 CurrentVRegDefs.insert(Val: VReg2SUnit(Reg, NonOverlapMask, DefSU));
511 }
512 // If there was no CurrentVRegDefs entry for some lanes yet, create one.
513 if (LaneMask.any())
514 CurrentVRegDefs.insert(Val: VReg2SUnit(Reg, LaneMask, SU));
515}
516
517/// Adds a register data dependency if the instruction that defines the
518/// virtual register used at OperIdx is mapped to an SUnit. Add a register
519/// antidependency from this SUnit to instructions that occur later in the same
520/// scheduling region if they write the virtual register.
521///
522/// TODO: Handle ExitSU "uses" properly.
523void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
524 const MachineInstr *MI = SU->getInstr();
525 assert(!MI->isDebugOrPseudoInstr());
526
527 const MachineOperand &MO = MI->getOperand(i: OperIdx);
528 Register Reg = MO.getReg();
529
530 // Remember the use. Data dependencies will be added when we find the def.
531 LaneBitmask LaneMask = TrackLaneMasks ? getLaneMaskForMO(MO)
532 : LaneBitmask::getAll();
533 CurrentVRegUses.insert(Val: VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU));
534
535 // Add antidependences to the following defs of the vreg.
536 for (VReg2SUnit &V2SU : make_range(x: CurrentVRegDefs.find(Key: Reg),
537 y: CurrentVRegDefs.end())) {
538 // Ignore defs for unrelated lanes.
539 LaneBitmask PrevDefLaneMask = V2SU.LaneMask;
540 if ((PrevDefLaneMask & LaneMask).none())
541 continue;
542 if (V2SU.SU == SU)
543 continue;
544
545 V2SU.SU->addPred(D: SDep(SU, SDep::Anti, Reg));
546 }
547}
548
549/// Creates an SUnit for each real instruction, numbered in top-down
550/// topological order. The instruction order A < B, implies that no edge exists
551/// from B to A.
552///
553/// Map each real instruction to its SUnit.
554///
555/// After initSUnits, the SUnits vector cannot be resized and the scheduler may
556/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs
557/// instead of pointers.
558///
559/// MachineScheduler relies on initSUnits numbering the nodes by their order in
560/// the original instruction list.
561void ScheduleDAGInstrs::initSUnits() {
562 // We'll be allocating one SUnit for each real instruction in the region,
563 // which is contained within a basic block.
564 SUnits.reserve(n: NumRegionInstrs);
565
566 for (MachineInstr &MI : make_range(x: RegionBegin, y: RegionEnd)) {
567 if (MI.isDebugOrPseudoInstr())
568 continue;
569
570 SUnit *SU = newSUnit(MI: &MI);
571 MISUnitMap[&MI] = SU;
572
573 SU->isCall = MI.isCall();
574 SU->isCommutable = MI.isCommutable();
575
576 // Assign the Latency field of SU using target-provided information.
577 SU->Latency = SchedModel.computeInstrLatency(MI: SU->getInstr());
578
579 // If this SUnit uses a reserved or unbuffered resource, mark it as such.
580 //
581 // Reserved resources block an instruction from issuing and stall the
582 // entire pipeline. These are identified by BufferSize=0.
583 //
584 // Unbuffered resources prevent execution of subsequent instructions that
585 // require the same resources. This is used for in-order execution pipelines
586 // within an out-of-order core. These are identified by BufferSize=1.
587 if (SchedModel.hasInstrSchedModel()) {
588 const MCSchedClassDesc *SC = getSchedClass(SU);
589 for (const MCWriteProcResEntry &PRE :
590 make_range(x: SchedModel.getWriteProcResBegin(SC),
591 y: SchedModel.getWriteProcResEnd(SC))) {
592 switch (SchedModel.getResourceBufferSize(PIdx: PRE.ProcResourceIdx)) {
593 case 0:
594 SU->hasReservedResource = true;
595 break;
596 case 1:
597 SU->isUnbuffered = true;
598 break;
599 default:
600 break;
601 }
602 }
603 }
604 }
605}
606
607namespace {
608/// A list of SUnits, used in Value2SUsMap, during DAG construction.
609/// FIXME: to gain speed it might be worth investigating an optimized
610/// implementation of this data structure, such as a singly linked list
611/// with a memory pool (SmallVector was tried but slow and SparseSet is not
612/// applicable).
613using SUList = std::list<SUnit *>;
614
615static void dumpSUList(const SUList &L) {
616#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
617 dbgs() << "{ ";
618 for (const SUnit *SU : L) {
619 dbgs() << *SU;
620 if (SU != L.back())
621 dbgs() << ", ";
622 }
623 dbgs() << "}\n";
624#endif
625}
626
627class Value2SUsMap : public SmallMapVector<ValueType, SUList, 4> {
628 /// Current total number of SUs in map.
629 unsigned NumNodes = 0;
630
631 /// 1 for loads, 0 for stores. (see comment in SUList)
632 unsigned TrueMemOrderLatency;
633
634public:
635 Value2SUsMap(unsigned lat = 0) : TrueMemOrderLatency(lat) {}
636
637 /// To keep NumNodes up to date, insert() is used instead of
638 /// this operator w/ push_back().
639 ValueType &operator[](const SUList &Key) {
640 llvm_unreachable("Don't use. Use insert() instead.");
641 };
642
643 /// Adds SU to the SUList of V. If Map grows huge, reduce its size by calling
644 /// reduce().
645 void inline insert(SUnit *SU, ValueType V) {
646 MapVector::operator[](Key: V).push_back(x: SU);
647 NumNodes++;
648 }
649
650 /// Clears the list of SUs mapped to V.
651 void inline clearList(ValueType V) {
652 iterator Itr = find(Key: V);
653 if (Itr != end()) {
654 assert(NumNodes >= Itr->second.size());
655 NumNodes -= Itr->second.size();
656
657 Itr->second.clear();
658 }
659 }
660
661 /// Clears map from all contents.
662 void clear() {
663 SmallMapVector<ValueType, SUList, 4>::clear();
664 NumNodes = 0;
665 }
666
667 unsigned inline size() const { return NumNodes; }
668
669 /// Counts the number of SUs in this map after a reduction.
670 void reComputeSize() {
671 NumNodes = 0;
672 for (auto &I : *this)
673 NumNodes += I.second.size();
674 }
675
676 unsigned inline getTrueMemOrderLatency() const {
677 return TrueMemOrderLatency;
678 }
679
680 void dump();
681};
682
683void Value2SUsMap::dump() {
684 for (const auto &[ValType, SUs] : *this) {
685 if (isa<const Value *>(Val: ValType)) {
686 const Value *V = cast<const Value *>(Val: ValType);
687 if (isa<UndefValue>(Val: V))
688 dbgs() << "Unknown";
689 else
690 V->printAsOperand(O&: dbgs());
691 } else if (isa<const PseudoSourceValue *>(Val: ValType))
692 dbgs() << cast<const PseudoSourceValue *>(Val: ValType);
693 else
694 llvm_unreachable("Unknown Value type.");
695
696 dbgs() << " : ";
697 dumpSUList(L: SUs);
698 }
699}
700} // end anonymous namespace
701
702namespace llvm {
703class ScheduleDAGDependencyBuilder {
704private:
705 ScheduleDAGInstrs &DAG;
706
707 BatchAAResults *AA;
708 RegPressureTracker *RPTracker;
709 PressureDiffs *PDiffs;
710 LiveIntervals *LIS;
711
712 // Each MIs' memory operand(s) is analyzed to a list of underlying
713 // objects. The SU is then inserted in the SUList(s) mapped from the
714 // Value(s). Each Value thus gets mapped to lists of SUs depending
715 // on it, stores and loads kept separately. Two SUs are trivially
716 // non-aliasing if they both depend on only identified Values and do
717 // not share any common Value.
718 Value2SUsMap Stores, Loads;
719
720 // Track all instructions that may raise floating-point exceptions.
721 // These do not depend on one other (or normal loads or stores), but
722 // must not be rescheduled across global barriers. Note that we don't
723 // really need a "map" here since we don't track those MIs by value;
724 // using the same Value2SUsMap data type here is simply a matter of
725 // convenience.
726 Value2SUsMap FPExceptions;
727
728 /// A frontier of unanalyzable memory operations.
729 ///
730 /// As we process memory operations (bottom to top), each new unanalyzable
731 /// memory operation needs to be checked for required control dependencies
732 /// against later memory operations. A naive implementation issues AA calls
733 /// quadratically in the number of memory operations and is therefore
734 /// unacceptable.
735 ///
736 /// To bound the complexity, we only ever consider a frontier of memory
737 /// operations which we frequently clear, modeled by this struct. To ensure
738 /// that we are not missing any necessary control dependencies, we promote
739 /// certain store instructions to what we term 'sequencing stores'. These
740 /// sequencing stores are treated carefully to ensure that all previously seen
741 /// unanalyzable memory operations that do not belong to the frontier
742 /// necessarily transitively succeed the current sequencing store.
743 ///
744 /// By frequently updating the sequencing store, we bound the number of alias
745 /// analysis queries and transitively redundant control dependencies we
746 /// generate. However, doing so we necessarily overconstrain the DAG. Indeed,
747 /// if we were to update the sequencing store every time we see a store
748 /// instruction, the effect would be to linearize the stores.
749 ///
750 /// The conditions we choose to update the sequencing store are as follows:
751 /// 1. If an incoming store instruction refers to an underlying object outside
752 /// of the set of underlying objects of the current sequencing store;
753 /// 2. If an incoming store instruction precedes an intervening load from an
754 /// underlying object outside of the set of underlying objects of the
755 /// current sequencing store (a 'sequencing load').
756 /// In these cases, a BasicAA query will (generally) already induce a
757 /// (transitive) edge from the incoming store to the current sequencing store.
758 /// However, this process introduces spurious (transitive) barrier edges in
759 /// the following cases:
760 /// 1. From all preceding loads to the new sequencing store;
761 /// 2. From the new sequencing store to all stores in the current frontier;
762 /// 3. From all preceding unanalyzable stores to (a subset of) the same base
763 /// objects, independent of AA results;
764 /// 4. From all preceding analyzable stores, independent of AA results.
765 struct UnanalyzableFrontier {
766 /// The current sequencing store.
767 SUnit *SequencingStore = nullptr;
768 /// The underlying objects of the current sequencing store.
769 UnderlyingObjectsVector BaseObjects;
770 /// The memory operations in the frontier (keyed by UnknownValue).
771 Value2SUsMap Stores, Loads{1 /*TrueMemOrderLatency*/};
772 /// `true` if the frontier contains a load whose underlying objects escape
773 /// #BaseObjects.
774 bool SeenSequencingLoad = false;
775
776 /// Given a store instruction with underlying objects \p Objs, returns true
777 /// if the store should be promoted to a sequencing store and false
778 /// otherwise.
779 bool shouldUpdate(const UnderlyingObjectsVector &Objs);
780
781 /// Returns true if any of \p Objs does not belong to #BaseObjects.
782 bool escapesBaseObjects(const UnderlyingObjectsVector &Objs);
783
784 /// Clears the frontier.
785 void clear();
786 };
787
788 /// Track a frontier of unanalyzable memory operations.
789 ///
790 /// FIXME(@cofibrant): For some platforms, a single frontier is too coarse and
791 /// we should be maintaining one frontier per address space.
792 UnanalyzableFrontier Frontier;
793
794 /// For an unanalyzable memory access, this Value is used in maps.
795 UndefValue *UnknownValue;
796
797 /// Remember a generic side-effecting instruction as we proceed.
798 /// No other SU ever gets scheduled around it (except in the special
799 /// case of a huge region that gets reduced).
800 SUnit *BarrierChain = nullptr;
801
802 unsigned MemOpsProcessed = 0;
803
804public:
805 ScheduleDAGDependencyBuilder(ScheduleDAGInstrs &DAG, BatchAAResults *AA,
806 RegPressureTracker *RPTracker,
807 PressureDiffs *PDiffs, LiveIntervals *LIS)
808 : DAG(DAG), AA(AA), RPTracker(RPTracker), PDiffs(PDiffs), LIS(LIS),
809 Stores(), Loads(1), FPExceptions(), Frontier(),
810 UnknownValue(UndefValue::get(
811 T: Type::getVoidTy(C&: DAG.MF.getFunction().getContext()))) {}
812
813private:
814 /// Adds a chain edge between SUa and SUb, but only if both
815 /// AAResults and Target fail to deny the dependency.
816 ///
817 /// Returns true if an edge was inserted.
818 bool addChainDependency(SUnit *SUa, SUnit *SUb, unsigned Latency = 0);
819
820 /// Adds dependencies as needed from all SUs in list to SU.
821 void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency);
822 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap);
823 void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap, ValueType V);
824 void addChainDependencies(SUnit *SU, UnanalyzableFrontier &UF, bool IsStore);
825
826 void addBarrierChain(Value2SUsMap &map);
827 void addBarrierChain(UnanalyzableFrontier &UF);
828
829 /// Promote the store \p SU with underlying objects \p Objs to be a new
830 /// sequencing store in the frontier \p UF.
831 void updateSequencingStore(UnanalyzableFrontier &UF, SUnit *SU,
832 UnderlyingObjectsVector &Objs);
833
834public:
835 void buildDeps();
836};
837} // end namespace llvm
838
839bool ScheduleDAGDependencyBuilder::UnanalyzableFrontier::shouldUpdate(
840 const UnderlyingObjectsVector &Objs) {
841 if (!EnableStoreSequencing)
842 return false;
843 return !SequencingStore || SeenSequencingLoad || escapesBaseObjects(Objs);
844}
845
846bool ScheduleDAGDependencyBuilder::UnanalyzableFrontier::escapesBaseObjects(
847 const UnderlyingObjectsVector &Objs) {
848 for (const ValueType V : Objs) {
849 if (!is_contained(Range&: BaseObjects, Element: V))
850 return true;
851 }
852
853 return false;
854}
855
856void ScheduleDAGDependencyBuilder::UnanalyzableFrontier::clear() {
857 SequencingStore = nullptr;
858 SeenSequencingLoad = false;
859 BaseObjects.clear();
860 Stores.clear();
861 Loads.clear();
862}
863
864bool ScheduleDAGDependencyBuilder::addChainDependency(SUnit *SUa, SUnit *SUb,
865 unsigned Latency) {
866 if (!SUa->getInstr()->mayAlias(AA, Other: *SUb->getInstr(), UseTBAA))
867 return false;
868
869 SDep Dep(SUa, SDep::MayAliasMem);
870 Dep.setLatency(Latency);
871 SUb->addPred(D: Dep);
872 return true;
873}
874
875void ScheduleDAGDependencyBuilder::addChainDependencies(SUnit *SU, SUList &SUs,
876 unsigned Latency) {
877 for (SUnit *Entry : SUs)
878 addChainDependency(SUa: SU, SUb: Entry, Latency);
879}
880
881void ScheduleDAGDependencyBuilder::addChainDependencies(
882 SUnit *SU, Value2SUsMap &Val2SUsMap) {
883 for (auto &I : Val2SUsMap)
884 addChainDependencies(SU, SUs&: I.second, Latency: Val2SUsMap.getTrueMemOrderLatency());
885}
886
887void ScheduleDAGDependencyBuilder::addChainDependencies(
888 SUnit *SU, Value2SUsMap &Val2SUsMap, ValueType V) {
889 Value2SUsMap::iterator Itr = Val2SUsMap.find(Key: V);
890 if (Itr != Val2SUsMap.end())
891 addChainDependencies(SU, SUs&: Itr->second, Latency: Val2SUsMap.getTrueMemOrderLatency());
892}
893
894void ScheduleDAGDependencyBuilder::addChainDependencies(
895 SUnit *SU, UnanalyzableFrontier &UF, bool IsStore) {
896 if (UF.SequencingStore)
897 UF.SequencingStore->addPredBarrier(SU);
898
899 addChainDependencies(SU, Val2SUsMap&: UF.Stores, V: UnknownValue);
900 if (IsStore)
901 addChainDependencies(SU, Val2SUsMap&: UF.Loads, V: UnknownValue);
902}
903
904void ScheduleDAGDependencyBuilder::addBarrierChain(Value2SUsMap &map) {
905 assert(BarrierChain != nullptr);
906
907 for (auto &[V, SUs] : map) {
908 (void)V;
909 for (auto *SU : SUs)
910 SU->addPredBarrier(SU: BarrierChain);
911 }
912
913 map.clear();
914}
915
916void ScheduleDAGDependencyBuilder::addBarrierChain(UnanalyzableFrontier &UF) {
917 assert(BarrierChain != nullptr);
918
919 addBarrierChain(map&: UF.Stores);
920 addBarrierChain(map&: UF.Loads);
921
922 if (UF.SequencingStore)
923 UF.SequencingStore->addPredBarrier(SU: BarrierChain);
924
925 UF.clear();
926}
927
928void ScheduleDAGDependencyBuilder::updateSequencingStore(
929 UnanalyzableFrontier &UF, SUnit *SU, UnderlyingObjectsVector &Objs) {
930 assert(SU->getInstr()->mayStore() &&
931 "Only store instructions should be used as sequencing stores");
932
933 if (UF.SequencingStore)
934 UF.SequencingStore->addPredBarrier(SU);
935
936 // Sequence all stores against the sequencing store and clear the map.
937 for (auto &[V, SUs] : UF.Stores) {
938 for (SUnit *S : SUs)
939 S->addPredBarrier(SU);
940 }
941
942 UF.Stores.clear();
943
944 // For loads, we can do slightly better. Rather than naively adding pred
945 // barriers and clearing the map, we check whether each load genuinely needs
946 // to sequence against the new sequencing store. Wherever an edge is not
947 // required, we retain the load and avoid the spurious control dependency.
948 for (auto &[V, SUs] : UF.Loads) {
949 for (auto It = SUs.begin(); It != SUs.end();) {
950 if (addChainDependency(SUa: SU, SUb: *It, /*TrueMemOrderLatency=*/Latency: 1)) {
951 // FIXME(@cofibrant): `UF.Loads` won't record the reduction in its size
952 // here. This wants fixing before we work on promoting stores to
953 // sequencing stores when the maps get too large.
954 It = SUs.erase(position: It);
955 } else {
956 ++It;
957 }
958 }
959 }
960
961 UF.SequencingStore = SU;
962 UF.BaseObjects = std::move(Objs);
963 UF.SeenSequencingLoad = false;
964}
965
966void ScheduleDAGDependencyBuilder::buildDeps() {
967 const TargetSubtargetInfo &ST = DAG.MF.getSubtarget();
968
969 // We build scheduling units by walking a block's instruction list
970 // from bottom to top.
971
972 // Model data dependencies between instructions being scheduled and the
973 // ExitSU.
974 DAG.addSchedBarrierDeps();
975
976 // Walk the list of instructions, from bottom moving up.
977 MachineInstr *DbgMI = nullptr;
978 for (MachineBasicBlock::iterator MII = DAG.RegionEnd, MIE = DAG.RegionBegin;
979 MII != MIE; --MII) {
980 MachineInstr &MI = *std::prev(x: MII);
981 if (DbgMI) {
982 DAG.DbgValues.emplace_back(args&: DbgMI, args: &MI);
983 DbgMI = nullptr;
984 }
985
986 if (MI.isDebugValue() || MI.isDebugPHI()) {
987 DbgMI = &MI;
988 continue;
989 }
990
991 if (MI.isDebugLabel() || MI.isDebugRef() || MI.isPseudoProbe())
992 continue;
993
994 SUnit *SU = DAG.MISUnitMap[&MI];
995 assert(SU && "No SUnit mapped to this MI");
996
997 if (RPTracker) {
998 RegisterOperands RegOpers;
999 RegOpers.collect(MI, TRI: *DAG.TRI, MRI: DAG.MRI, TrackLaneMasks: DAG.TrackLaneMasks, IgnoreDead: false);
1000 if (DAG.TrackLaneMasks) {
1001 SlotIndex SlotIdx = LIS->getInstructionIndex(Instr: MI);
1002 RegOpers.adjustLaneLiveness(LIS&: *LIS, MRI: DAG.MRI, Pos: SlotIdx);
1003 } else if (LIS) {
1004 // Detect dead defs from LiveIntervals instead of trusting operand dead
1005 // flags.
1006 RegOpers.detectDeadDefs(MI, LIS&: *LIS, MRI: DAG.MRI);
1007 }
1008 if (PDiffs != nullptr)
1009 PDiffs->addInstruction(Idx: SU->NodeNum, RegOpers, MRI: DAG.MRI);
1010
1011 if (RPTracker->getPos() == DAG.RegionEnd || &*RPTracker->getPos() != &MI)
1012 RPTracker->recedeSkipDebugValues();
1013 assert(&*RPTracker->getPos() == &MI && "RPTracker in sync");
1014 RPTracker->recede(RegOpers);
1015 }
1016
1017 assert((DAG.CanHandleTerminators ||
1018 (!MI.isTerminator() && !MI.isPosition())) &&
1019 "Cannot schedule terminators or labels!");
1020
1021 // Add register-based dependencies (data, anti, and output).
1022 // For some instructions (calls, returns, inline-asm, etc.) there can
1023 // be explicit uses and implicit defs, in which case the use will appear
1024 // on the operand list before the def. Do two passes over the operand
1025 // list to make sure that defs are processed before any uses.
1026 bool HasVRegDef = false;
1027 for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
1028 const MachineOperand &MO = MI.getOperand(i: j);
1029 if (!MO.isReg() || !MO.isDef())
1030 continue;
1031 Register Reg = MO.getReg();
1032 if (Reg.isPhysical()) {
1033 DAG.addPhysRegDeps(SU, OperIdx: j);
1034 } else if (Reg.isVirtual()) {
1035 HasVRegDef = true;
1036 DAG.addVRegDefDeps(SU, OperIdx: j);
1037 }
1038 }
1039 // Now process all uses.
1040 for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
1041 const MachineOperand &MO = MI.getOperand(i: j);
1042 // Only look at use operands.
1043 // We do not need to check for MO.readsReg() here because subsequent
1044 // subregister defs will get output dependence edges and need no
1045 // additional use dependencies.
1046 if (!MO.isReg() || !MO.isUse())
1047 continue;
1048 Register Reg = MO.getReg();
1049 if (Reg.isPhysical()) {
1050 DAG.addPhysRegDeps(SU, OperIdx: j);
1051 } else if (Reg.isVirtual() && MO.readsReg()) {
1052 DAG.addVRegUseDeps(SU, OperIdx: j);
1053 }
1054 }
1055
1056 // If we haven't seen any uses in this scheduling region, create a
1057 // dependence edge to ExitSU to model the live-out latency. This is required
1058 // for vreg defs with no in-region use, and prefetches with no vreg def.
1059 //
1060 // FIXME: NumDataSuccs would be more precise than NumSuccs here. This
1061 // check currently relies on being called before adding chain deps.
1062 if (SU->NumSuccs == 0 && SU->Latency > 1 && (HasVRegDef || MI.mayLoad())) {
1063 SDep Dep(SU, SDep::Artificial);
1064 Dep.setLatency(SU->Latency - 1);
1065 DAG.ExitSU.addPred(D: Dep);
1066 }
1067
1068 // Add memory dependencies (Note: isStoreToStackSlot and
1069 // isLoadFromStackSLot are not usable after stack slots are lowered to
1070 // actual addresses).
1071
1072 const TargetInstrInfo *TII = ST.getInstrInfo();
1073 // This is a barrier event that acts as a pivotal node in the DAG.
1074 if (TII->isGlobalMemoryObject(MI: &MI)) {
1075
1076 // Become the barrier chain.
1077 if (BarrierChain)
1078 BarrierChain->addPredBarrier(SU);
1079 BarrierChain = SU;
1080
1081 LLVM_DEBUG(dbgs() << "Global memory object and new barrier chain: "
1082 << *BarrierChain << ".\n");
1083
1084 // Add dependencies against everything below it and clear maps.
1085 addBarrierChain(map&: Stores);
1086 addBarrierChain(map&: Loads);
1087 addBarrierChain(map&: FPExceptions);
1088 addBarrierChain(UF&: Frontier);
1089
1090 continue;
1091 }
1092
1093 // Instructions that may raise FP exceptions may not be moved
1094 // across any global barriers.
1095 if (MI.mayRaiseFPException()) {
1096 if (BarrierChain)
1097 BarrierChain->addPredBarrier(SU);
1098
1099 if (FPExceptions.size() + 1 >= HugeRegion) {
1100 LLVM_DEBUG(
1101 dbgs()
1102 << "Creating barrier chain and clearing FPExceptions map.\n");
1103 BarrierChain = SU;
1104 addBarrierChain(map&: FPExceptions);
1105 } else {
1106 FPExceptions.insert(SU, V: UnknownValue);
1107 }
1108 }
1109
1110 // If it's not a store or a variant load, we're done.
1111 if (!MI.mayStore() &&
1112 !(MI.mayLoad() && !MI.isDereferenceableInvariantLoad()))
1113 continue;
1114
1115 MemOpsProcessed++;
1116
1117 // Always add dependecy edge to BarrierChain if present.
1118 if (BarrierChain && BarrierChain != SU)
1119 BarrierChain->addPredBarrier(SU);
1120
1121 // Reduce maps if they grow huge.
1122 //
1123 // FIXME(@cofibrant): With store-sequencing, this condition can be relaxed
1124 // and improved. Specifically, we are not so worried about `Stores` and
1125 // `Loads` growing too large, but more interested in making sure that the
1126 // frontier(s) themselves stay sufficiently small. This is best achieved by
1127 // measuring the size of the frontier(s) and, if sufficiently large,
1128 // promoting the next store to a sequencing store.
1129 if (MemOpsProcessed >= HugeRegion) {
1130 LLVM_DEBUG(dbgs() << "Creating barrier chain and clearing maps.\n");
1131
1132 BarrierChain = SU;
1133
1134 addBarrierChain(map&: Stores);
1135 addBarrierChain(map&: Loads);
1136 addBarrierChain(UF&: Frontier);
1137
1138 MemOpsProcessed = 0;
1139 continue;
1140 }
1141
1142 // Find the underlying objects for MI. The Objs vector is either
1143 // empty, or filled with the Values of memory locations which this
1144 // SU depends on.
1145 UnderlyingObjectsVector Objs;
1146 bool ObjsIdentified = getUnderlyingObjectsForInstr(MI: &MI, MFI: DAG.MFI, Objects&: Objs,
1147 DL: DAG.MF.getDataLayout());
1148
1149 if (MI.mayStore()) {
1150 if (!ObjsIdentified) {
1151 // An unknown store depends on all stores and loads.
1152 addChainDependencies(SU, Val2SUsMap&: Stores);
1153 addChainDependencies(SU, Val2SUsMap&: Loads);
1154
1155 if (Frontier.shouldUpdate(Objs)) {
1156 LLVM_DEBUG(dbgs() << "Promoting " << *SU << " to sequencing store\n");
1157 updateSequencingStore(UF&: Frontier, SU, Objs);
1158 } else {
1159 addChainDependencies(SU, UF&: Frontier, /*IsStore=*/true);
1160 Frontier.Stores.insert(SU, V: UnknownValue);
1161 }
1162 } else {
1163 // Add precise dependencies against all previously seen memory
1164 // accesses mapped to the same Value(s).
1165 for (const ValueType V : Objs) {
1166 // Add dependencies to previous stores and loads mapped to V.
1167 addChainDependencies(SU, Val2SUsMap&: Stores, V);
1168 addChainDependencies(SU, Val2SUsMap&: Loads, V);
1169 }
1170 // Update the store map after all chains have been added to avoid adding
1171 // self-loop edge if multiple underlying objects are present.
1172 for (const ValueType V : Objs)
1173 Stores.insert(SU, V);
1174
1175 // The store may have dependencies to unanalyzable loads and
1176 // stores.
1177 addChainDependencies(SU, UF&: Frontier, /*IsStore=*/true);
1178 }
1179 } else { // SU is a load.
1180 if (!ObjsIdentified) {
1181 // An unknown load depends on all stores.
1182 addChainDependencies(SU, Val2SUsMap&: Stores);
1183 addChainDependencies(SU, UF&: Frontier, /*IsStore=*/false);
1184
1185 Frontier.Loads.insert(SU, V: UnknownValue);
1186 if (Frontier.escapesBaseObjects(Objs))
1187 Frontier.SeenSequencingLoad = true;
1188 } else {
1189 for (const ValueType V : Objs) {
1190 // Add precise dependencies against all previously seen stores
1191 // mapping to the same Value(s).
1192 addChainDependencies(SU, Val2SUsMap&: Stores, V);
1193
1194 // Map this load to V.
1195 Loads.insert(SU, V);
1196 }
1197 // The load may have dependencies to unanalyzable stores.
1198 addChainDependencies(SU, UF&: Frontier, /*IsStore=*/false);
1199 }
1200 }
1201 }
1202
1203 if (DbgMI)
1204 DAG.FirstDbgValue = DbgMI;
1205}
1206
1207void ScheduleDAGInstrs::buildSchedGraph(AAResults *AA,
1208 RegPressureTracker *RPTracker,
1209 PressureDiffs *PDiffs,
1210 LiveIntervals *LIS,
1211 bool TrackLaneMasks) {
1212 const TargetSubtargetInfo &ST = MF.getSubtarget();
1213 bool UseAA =
1214 EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI : ST.useAA();
1215 this->TrackLaneMasks = TrackLaneMasks;
1216 MISUnitMap.clear();
1217 ScheduleDAG::clearDAG();
1218
1219 // Create an SUnit for each real instruction.
1220 initSUnits();
1221
1222 if (PDiffs)
1223 PDiffs->init(N: SUnits.size());
1224
1225 // Remove any stale debug info; sometimes BuildSchedGraph is called again
1226 // without emitting the info from the previous call.
1227 DbgValues.clear();
1228 FirstDbgValue = nullptr;
1229
1230 assert(Defs.empty() && Uses.empty() &&
1231 "Only BuildGraph should update Defs/Uses");
1232 Defs.setUniverse(TRI->getNumRegs());
1233 Uses.setUniverse(TRI->getNumRegs());
1234
1235 assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs");
1236 assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses");
1237 unsigned NumVirtRegs = MRI.getNumVirtRegs();
1238 CurrentVRegDefs.setUniverse(NumVirtRegs);
1239 CurrentVRegUses.setUniverse(NumVirtRegs);
1240
1241 std::optional<BatchAAResults> BatchAA;
1242 if (UseAA && AA)
1243 BatchAA.emplace(args&: *AA);
1244
1245 ScheduleDAGDependencyBuilder DepBuilder(
1246 *this, BatchAA.has_value() ? &BatchAA.value() : nullptr, RPTracker,
1247 PDiffs, LIS);
1248 DepBuilder.buildDeps();
1249
1250 Defs.clear();
1251 Uses.clear();
1252 CurrentVRegDefs.clear();
1253 CurrentVRegUses.clear();
1254
1255 Topo.MarkDirty();
1256}
1257
1258raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) {
1259 PSV->printCustom(O&: OS);
1260 return OS;
1261}
1262
1263static void toggleKills(const MachineRegisterInfo &MRI, LiveRegUnits &LiveRegs,
1264 MachineInstr &MI, bool addToLiveRegs) {
1265 for (MachineOperand &MO : MI.operands()) {
1266 if (!MO.isReg() || !MO.readsReg())
1267 continue;
1268 Register Reg = MO.getReg();
1269 if (!Reg)
1270 continue;
1271
1272 // Things that are available after the instruction are killed by it.
1273 bool IsKill = LiveRegs.available(Reg);
1274
1275 // Exception: Do not kill reserved registers
1276 MO.setIsKill(IsKill && !MRI.isReserved(PhysReg: Reg));
1277 if (addToLiveRegs)
1278 LiveRegs.addReg(Reg);
1279 }
1280}
1281
1282void ScheduleDAGInstrs::fixupKills(MachineBasicBlock &MBB) {
1283 LLVM_DEBUG(dbgs() << "Fixup kills for " << printMBBReference(MBB) << '\n');
1284
1285 LiveRegs.init(TRI: *TRI);
1286 LiveRegs.addLiveOuts(MBB);
1287
1288 // Examine block from end to start...
1289 for (MachineInstr &MI : llvm::reverse(C&: MBB)) {
1290 if (MI.isDebugOrPseudoInstr())
1291 continue;
1292
1293 // Update liveness. Registers that are defed but not used in this
1294 // instruction are now dead. Mark register and all subregs as they
1295 // are completely defined.
1296 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
1297 const MachineOperand &MO = *O;
1298 if (MO.isReg()) {
1299 if (!MO.isDef())
1300 continue;
1301 Register Reg = MO.getReg();
1302 if (!Reg)
1303 continue;
1304 LiveRegs.removeReg(Reg);
1305 } else if (MO.isRegMask()) {
1306 LiveRegs.removeRegsNotPreserved(RegMask: MO.getRegMask());
1307 }
1308 }
1309
1310 // If there is a bundle header fix it up first.
1311 if (!MI.isBundled()) {
1312 toggleKills(MRI, LiveRegs, MI, addToLiveRegs: true);
1313 } else {
1314 MachineBasicBlock::instr_iterator Bundle = MI.getIterator();
1315 if (MI.isBundle())
1316 toggleKills(MRI, LiveRegs, MI, addToLiveRegs: false);
1317
1318 // Some targets make the (questionable) assumtion that the instructions
1319 // inside the bundle are ordered and consequently only the last use of
1320 // a register inside the bundle can kill it.
1321 MachineBasicBlock::instr_iterator I = std::next(x: Bundle);
1322 while (I->isBundledWithSucc())
1323 ++I;
1324 do {
1325 if (!I->isDebugOrPseudoInstr())
1326 toggleKills(MRI, LiveRegs, MI&: *I, addToLiveRegs: true);
1327 --I;
1328 } while (I != Bundle);
1329 }
1330 }
1331}
1332
1333void ScheduleDAGInstrs::dumpNode(const SUnit &SU) const {
1334#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1335 dumpNodeName(SU);
1336 if (SchedPrintCycles)
1337 dbgs() << " [TopReadyCycle = " << SU.TopReadyCycle
1338 << ", BottomReadyCycle = " << SU.BotReadyCycle << "]";
1339 dbgs() << ": ";
1340 SU.getInstr()->dump();
1341#endif
1342}
1343
1344void ScheduleDAGInstrs::dump() const {
1345#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1346 if (EntrySU.getInstr() != nullptr)
1347 dumpNodeAll(EntrySU);
1348 for (const SUnit &SU : SUnits)
1349 dumpNodeAll(SU);
1350 if (ExitSU.getInstr() != nullptr)
1351 dumpNodeAll(ExitSU);
1352#endif
1353}
1354
1355#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
1356std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
1357 std::string s;
1358 raw_string_ostream oss(s);
1359 if (SU == &EntrySU)
1360 oss << "<entry>";
1361 else if (SU == &ExitSU)
1362 oss << "<exit>";
1363 else
1364 SU->getInstr()->print(oss, /*IsStandalone=*/true);
1365 return s;
1366}
1367#endif
1368
1369/// Return the basic block label. It is not necessarily unique because a block
1370/// contains multiple scheduling regions. But it is fine for visualization.
1371std::string ScheduleDAGInstrs::getDAGName() const {
1372 return "dag." + BB->getFullName();
1373}
1374
1375bool ScheduleDAGInstrs::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
1376 return SuccSU == &ExitSU || !Topo.IsReachable(SU: PredSU, TargetSU: SuccSU);
1377}
1378
1379bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) {
1380 if (SuccSU != &ExitSU) {
1381 // Do not use WillCreateCycle, it assumes SD scheduling.
1382 // If Pred is reachable from Succ, then the edge creates a cycle.
1383 if (Topo.IsReachable(SU: PredDep.getSUnit(), TargetSU: SuccSU))
1384 return false;
1385 Topo.AddPredQueued(Y: SuccSU, X: PredDep.getSUnit());
1386 }
1387 SuccSU->addPred(D: PredDep, /*Required=*/!PredDep.isArtificial());
1388 // Return true regardless of whether a new edge needed to be inserted.
1389 return true;
1390}
1391
1392//===----------------------------------------------------------------------===//
1393// SchedDFSResult Implementation
1394//===----------------------------------------------------------------------===//
1395
1396namespace llvm {
1397
1398/// Internal state used to compute SchedDFSResult.
1399class SchedDFSImpl {
1400 SchedDFSResult &R;
1401
1402 /// Join DAG nodes into equivalence classes by their subtree.
1403 IntEqClasses SubtreeClasses;
1404 /// List PredSU, SuccSU pairs that represent data edges between subtrees.
1405 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1406
1407 struct RootData {
1408 unsigned NodeID;
1409 unsigned ParentNodeID; ///< Parent node (member of the parent subtree).
1410 unsigned SubInstrCount = 0; ///< Instr count in this tree only, not
1411 /// children.
1412
1413 RootData(unsigned id): NodeID(id),
1414 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1415
1416 unsigned getSparseSetIndex() const { return NodeID; }
1417 };
1418
1419 SparseSet<RootData> RootSet;
1420
1421public:
1422 SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) {
1423 RootSet.setUniverse(R.DFSNodeData.size());
1424 }
1425
1426 /// Returns true if this node been visited by the DFS traversal.
1427 ///
1428 /// During visitPostorderNode the Node's SubtreeID is assigned to the Node
1429 /// ID. Later, SubtreeID is updated but remains valid.
1430 bool isVisited(const SUnit *SU) const {
1431 return R.DFSNodeData[SU->NodeNum].SubtreeID
1432 != SchedDFSResult::InvalidSubtreeID;
1433 }
1434
1435 /// Initializes this node's instruction count. We don't need to flag the node
1436 /// visited until visitPostorder because the DAG cannot have cycles.
1437 void visitPreorder(const SUnit *SU) {
1438 R.DFSNodeData[SU->NodeNum].InstrCount =
1439 SU->getInstr()->isTransient() ? 0 : 1;
1440 }
1441
1442 /// Called once for each node after all predecessors are visited. Revisit this
1443 /// node's predecessors and potentially join them now that we know the ILP of
1444 /// the other predecessors.
1445 void visitPostorderNode(const SUnit *SU) {
1446 // Mark this node as the root of a subtree. It may be joined with its
1447 // successors later.
1448 R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum;
1449 RootData RData(SU->NodeNum);
1450 RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1;
1451
1452 // If any predecessors are still in their own subtree, they either cannot be
1453 // joined or are large enough to remain separate. If this parent node's
1454 // total instruction count is not greater than a child subtree by at least
1455 // the subtree limit, then try to join it now since splitting subtrees is
1456 // only useful if multiple high-pressure paths are possible.
1457 unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount;
1458 for (const SDep &PredDep : SU->Preds) {
1459 if (PredDep.getKind() != SDep::Data)
1460 continue;
1461 unsigned PredNum = PredDep.getSUnit()->NodeNum;
1462 if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1463 joinPredSubtree(PredDep, Succ: SU, /*CheckLimit=*/false);
1464
1465 // Either link or merge the TreeData entry from the child to the parent.
1466 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1467 // If the predecessor's parent is invalid, this is a tree edge and the
1468 // current node is the parent.
1469 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1470 RootSet[PredNum].ParentNodeID = SU->NodeNum;
1471 }
1472 else if (RootSet.count(Key: PredNum)) {
1473 // The predecessor is not a root, but is still in the root set. This
1474 // must be the new parent that it was just joined to. Note that
1475 // RootSet[PredNum].ParentNodeID may either be invalid or may still be
1476 // set to the original parent.
1477 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1478 RootSet.erase(Key: PredNum);
1479 }
1480 }
1481 RootSet[SU->NodeNum] = RData;
1482 }
1483
1484 /// Called once for each tree edge after calling visitPostOrderNode on
1485 /// the predecessor. Increment the parent node's instruction count and
1486 /// preemptively join this subtree to its parent's if it is small enough.
1487 void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) {
1488 R.DFSNodeData[Succ->NodeNum].InstrCount
1489 += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount;
1490 joinPredSubtree(PredDep, Succ);
1491 }
1492
1493 /// Adds a connection for cross edges.
1494 void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) {
1495 ConnectionPairs.emplace_back(args: PredDep.getSUnit(), args&: Succ);
1496 }
1497
1498 /// Sets each node's subtree ID to the representative ID and record
1499 /// connections between trees.
1500 void finalize() {
1501 SubtreeClasses.compress();
1502 R.DFSTreeData.resize(N: SubtreeClasses.getNumClasses());
1503 assert(SubtreeClasses.getNumClasses() == RootSet.size()
1504 && "number of roots should match trees");
1505 for (const RootData &Root : RootSet) {
1506 unsigned TreeID = SubtreeClasses[Root.NodeID];
1507 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1508 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1509 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1510 // Note that SubInstrCount may be greater than InstrCount if we joined
1511 // subtrees across a cross edge. InstrCount will be attributed to the
1512 // original parent, while SubInstrCount will be attributed to the joined
1513 // parent.
1514 }
1515 R.SubtreeConnections.resize(new_size: SubtreeClasses.getNumClasses());
1516 R.SubtreeConnectLevels.resize(new_size: SubtreeClasses.getNumClasses());
1517 LLVM_DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n");
1518 for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) {
1519 R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1520 LLVM_DEBUG(dbgs() << " SU(" << Idx << ") in tree "
1521 << R.DFSNodeData[Idx].SubtreeID << '\n');
1522 }
1523 for (const auto &[Pred, Succ] : ConnectionPairs) {
1524 unsigned PredTree = SubtreeClasses[Pred->NodeNum];
1525 unsigned SuccTree = SubtreeClasses[Succ->NodeNum];
1526 if (PredTree == SuccTree)
1527 continue;
1528 unsigned Depth = Pred->getDepth();
1529 addConnection(FromTree: PredTree, ToTree: SuccTree, Depth);
1530 addConnection(FromTree: SuccTree, ToTree: PredTree, Depth);
1531 }
1532 }
1533
1534protected:
1535 /// Joins the predecessor subtree with the successor that is its DFS parent.
1536 /// Applies some heuristics before joining.
1537 bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ,
1538 bool CheckLimit = true) {
1539 assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges");
1540
1541 // Check if the predecessor is already joined.
1542 const SUnit *PredSU = PredDep.getSUnit();
1543 unsigned PredNum = PredSU->NodeNum;
1544 if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1545 return false;
1546
1547 // Four is the magic number of successors before a node is considered a
1548 // pinch point.
1549 unsigned NumDataSucs = 0;
1550 for (const SDep &SuccDep : PredSU->Succs) {
1551 if (SuccDep.getKind() == SDep::Data) {
1552 if (++NumDataSucs >= 4)
1553 return false;
1554 }
1555 }
1556 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1557 return false;
1558 R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum;
1559 SubtreeClasses.join(a: Succ->NodeNum, b: PredNum);
1560 return true;
1561 }
1562
1563 /// Called by finalize() to record a connection between trees.
1564 void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) {
1565 if (!Depth)
1566 return;
1567
1568 do {
1569 SmallVectorImpl<SchedDFSResult::Connection> &Connections =
1570 R.SubtreeConnections[FromTree];
1571 for (SchedDFSResult::Connection &C : Connections) {
1572 if (C.TreeID == ToTree) {
1573 C.Level = std::max(a: C.Level, b: Depth);
1574 return;
1575 }
1576 }
1577 Connections.push_back(Elt: SchedDFSResult::Connection(ToTree, Depth));
1578 FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1579 } while (FromTree != SchedDFSResult::InvalidSubtreeID);
1580 }
1581};
1582
1583} // end namespace llvm
1584
1585namespace {
1586
1587/// Manage the stack used by a reverse depth-first search over the DAG.
1588class SchedDAGReverseDFS {
1589 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1590
1591public:
1592 bool isComplete() const { return DFSStack.empty(); }
1593
1594 void follow(const SUnit *SU) {
1595 DFSStack.emplace_back(args&: SU, args: SU->Preds.begin());
1596 }
1597 void advance() { ++DFSStack.back().second; }
1598
1599 const SDep *backtrack() {
1600 DFSStack.pop_back();
1601 return DFSStack.empty() ? nullptr : std::prev(x: DFSStack.back().second);
1602 }
1603
1604 const SUnit *getCurr() const { return DFSStack.back().first; }
1605
1606 SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; }
1607
1608 SUnit::const_pred_iterator getPredEnd() const {
1609 return getCurr()->Preds.end();
1610 }
1611};
1612
1613} // end anonymous namespace
1614
1615static bool hasDataSucc(const SUnit *SU) {
1616 for (const SDep &SuccDep : SU->Succs) {
1617 if (SuccDep.getKind() == SDep::Data &&
1618 !SuccDep.getSUnit()->isBoundaryNode())
1619 return true;
1620 }
1621 return false;
1622}
1623
1624/// Computes an ILP metric for all nodes in the subDAG reachable via depth-first
1625/// search from this root.
1626void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) {
1627 if (!IsBottomUp)
1628 llvm_unreachable("Top-down ILP metric is unimplemented");
1629
1630 SchedDFSImpl Impl(*this);
1631 for (const SUnit &SU : SUnits) {
1632 if (Impl.isVisited(SU: &SU) || hasDataSucc(SU: &SU))
1633 continue;
1634
1635 SchedDAGReverseDFS DFS;
1636 Impl.visitPreorder(SU: &SU);
1637 DFS.follow(SU: &SU);
1638 while (true) {
1639 // Traverse the leftmost path as far as possible.
1640 while (DFS.getPred() != DFS.getPredEnd()) {
1641 const SDep &PredDep = *DFS.getPred();
1642 DFS.advance();
1643 // Ignore non-data edges.
1644 if (PredDep.getKind() != SDep::Data
1645 || PredDep.getSUnit()->isBoundaryNode()) {
1646 continue;
1647 }
1648 // An already visited edge is a cross edge, assuming an acyclic DAG.
1649 if (Impl.isVisited(SU: PredDep.getSUnit())) {
1650 Impl.visitCrossEdge(PredDep, Succ: DFS.getCurr());
1651 continue;
1652 }
1653 Impl.visitPreorder(SU: PredDep.getSUnit());
1654 DFS.follow(SU: PredDep.getSUnit());
1655 }
1656 // Visit the top of the stack in postorder and backtrack.
1657 const SUnit *Child = DFS.getCurr();
1658 const SDep *PredDep = DFS.backtrack();
1659 Impl.visitPostorderNode(SU: Child);
1660 if (PredDep)
1661 Impl.visitPostorderEdge(PredDep: *PredDep, Succ: DFS.getCurr());
1662 if (DFS.isComplete())
1663 break;
1664 }
1665 }
1666 Impl.finalize();
1667}
1668
1669/// The root of the given SubtreeID was just scheduled. For all subtrees
1670/// connected to this tree, record the depth of the connection so that the
1671/// nearest connected subtrees can be prioritized.
1672void SchedDFSResult::scheduleTree(unsigned SubtreeID) {
1673 for (const Connection &C : SubtreeConnections[SubtreeID]) {
1674 SubtreeConnectLevels[C.TreeID] =
1675 std::max(a: SubtreeConnectLevels[C.TreeID], b: C.Level);
1676 LLVM_DEBUG(dbgs() << " Tree: " << C.TreeID << " @"
1677 << SubtreeConnectLevels[C.TreeID] << '\n');
1678 }
1679}
1680
1681#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1682LLVM_DUMP_METHOD void ILPValue::print(raw_ostream &OS) const {
1683 OS << InstrCount << " / " << Length << " = ";
1684 if (!Length)
1685 OS << "BADILP";
1686 else
1687 OS << format("%g", ((double)InstrCount / Length));
1688}
1689
1690LLVM_DUMP_METHOD void ILPValue::dump() const {
1691 dbgs() << *this << '\n';
1692}
1693
1694[[maybe_unused]]
1695raw_ostream &llvm::operator<<(raw_ostream &OS, const ILPValue &Val) {
1696 Val.print(OS);
1697 return OS;
1698}
1699
1700#endif
1701