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