1//===---------------------- AMDGPUNextUseAnalysis.cpp ---------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the AMDGPUNextUseAnalysis pass, a machine-level analysis
10// that computes the distance from each instruction to the "nearest" next use of
11// every live virtual register. These distances guide register spilling
12// decisions by identifying which live values are furthest from their next use
13// and are therefore the best candidates to spill.
14//
15// The analysis is based on the Braun & Hack CC'09 paper "Register Spilling and
16// Live-Range Splitting for SSA-Form Programs."
17//
18// Key concepts:
19//
20// NextUseDistance A loop-depth-weighted instruction count representing
21// how far away a register's next use is. Distances
22// through deeper loops are scaled by fromLoopDepth() so
23// that uses inside hot loops appear closer.
24//
25// Inter-block Pre-computed shortest weighted distances between all
26// distances pairs of basic blocks, used to efficiently answer
27// cross-block next-use queries. Each intermediate block
28// is weighted by fromLoopDepth() applied once per loop
29// boundary crossing relative to the destination.
30//
31// Configuration flags (see Config struct in the header):
32//
33// CountPhis Count PHI instructions toward distance and block size.
34// ForwardOnly Restrict inter-block distances to forward-reachable
35// paths.
36// PreciseUseModeling Model PHI uses at their incoming edge block and filter
37// uses with intermediate redefinitions.
38// PromoteToPreheader Route loop-entry and inner-loop uses to the preheader.
39//
40// This file contains:
41//
42// - Command-line options for configuration and debug output
43// - LiveRegUse / JSON helpers
44// - AMDGPUNextUseAnalysisImpl (the main analysis implementation)
45// - Instruction ID assignment and block size computation
46// - CFG path pre-computation (reachability, loop depth, back-edges)
47// - Inter-block distance computation
48// - Per-register next-use distance queries and caching
49// - AMDGPUNextUseAnalysis (public facade, pimpl)
50// - Legacy and new pass manager wrappers
51//
52//===----------------------------------------------------------------------===//
53
54#include "AMDGPUNextUseAnalysis.h"
55#include "AMDGPU.h"
56#include "GCNRegPressure.h"
57#include "GCNSubtarget.h"
58
59#include "llvm/ADT/SmallVector.h"
60#include "llvm/CodeGen/MachineBasicBlock.h"
61#include "llvm/CodeGen/MachineFunction.h"
62#include "llvm/CodeGen/MachineInstr.h"
63#include "llvm/CodeGen/MachineLoopInfo.h"
64#include "llvm/IR/ModuleSlotTracker.h"
65#include "llvm/InitializePasses.h"
66#include "llvm/Support/FileSystem.h"
67#include "llvm/Support/JSON.h"
68#include "llvm/Support/Timer.h"
69#include "llvm/Support/ToolOutputFile.h"
70#include "llvm/Support/raw_ostream.h"
71
72#include <string>
73
74using namespace llvm;
75
76#define DEBUG_TYPE "amdgpu-next-use-analysis"
77
78//==============================================================================
79// Options etc
80//==============================================================================
81namespace {
82
83cl::opt<bool>
84 DistanceCacheEnabled("amdgpu-next-use-analysis-distance-cache",
85 cl::init(Val: true), cl::Hidden,
86 cl::desc("Enable live-reg-use distance cache"));
87
88cl::opt<std::string>
89 DumpNextUseDistanceAsJson("amdgpu-next-use-analysis-dump-distance-as-json",
90 cl::Hidden);
91
92cl::opt<bool> DumpNextUseDistanceDefToUse(
93 "amdgpu-next-use-analysis-dump-distance-def-to-use", cl::init(Val: false),
94 cl::Hidden);
95
96cl::opt<bool>
97 DumpNextUseDistanceVerbose("amdgpu-next-use-analysis-dump-distance-verbose",
98 cl::init(Val: false), cl::Hidden);
99
100// 'graphics' and 'compute' modes arose due to initial competing implementations
101// of next-use analysis that emphasized different types of workloads. This
102// implementation is a compromise that combines aspects of both. Over time, the
103// hope is we will be able to remove some of these differences and settle on a
104// more unified implementation.
105cl::opt<std::string>
106 ConfigPresetOpt("amdgpu-next-use-analysis-config", cl::Hidden,
107 cl::init(Val: "graphics"),
108 cl::desc("Config preset: 'graphics' or 'compute'"));
109
110cl::opt<bool> ConfigCountPhisOpt(
111 "amdgpu-next-use-analysis-count-phis", cl::Hidden,
112 cl::desc("Count PHI instructions toward distance and block size"));
113cl::opt<bool> ConfigForwardOnlyOpt(
114 "amdgpu-next-use-analysis-forward-only", cl::Hidden,
115 cl::desc("Restrict inter-block distances to forward-reachable paths"));
116cl::opt<bool> ConfigPreciseUseModelingOpt(
117 "amdgpu-next-use-analysis-precise-use-modeling", cl::Hidden,
118 cl::desc("Model PHI uses via incoming edge block with loop-aware "
119 "reachability filtering"));
120cl::opt<bool> ConfigPromoteToPreheaderOpt(
121 "amdgpu-next-use-analysis-use-preheader-model", cl::Hidden,
122 cl::desc("Promote loop-entry and inner-loop uses to the loop preheader"));
123} // namespace
124
125//==============================================================================
126// LiveRegUse - Represents a live register use with its distance. Used for
127// tracking and sorting register uses by distance.
128//==============================================================================
129namespace {
130using UseDistancePair = AMDGPUNextUseAnalysis::UseDistancePair;
131struct LiveRegUse : public UseDistancePair {
132 // 'nullptr' indicates an unset/invalid state.
133 LiveRegUse() : UseDistancePair(nullptr, 0) {}
134 LiveRegUse(const MachineOperand *Use, NextUseDistance Dist)
135 : UseDistancePair(Use, Dist) {}
136 LiveRegUse(const UseDistancePair &P) : UseDistancePair(P) {}
137
138 bool isUnset() const { return Use == nullptr; }
139
140 Register getReg() const { return Use->getReg(); }
141 unsigned getSubReg() const { return Use->getSubReg(); }
142 LaneBitmask getLaneMask(const SIRegisterInfo *TRI) const {
143 return TRI->getSubRegIndexLaneMask(SubIdx: Use->getSubReg());
144 }
145
146 bool isCloserThan(const LiveRegUse &X) const {
147 if (Dist < X.Dist)
148 return true;
149
150 if (Dist > X.Dist)
151 return false;
152
153 if (Use == X.Use)
154 return false;
155
156 // Ugh. When !CountPhis, PHIs and the first non-PHI instruction have id
157 // 0. In this case, consider PHIs as less than the first non-PHI
158 // instruction.
159 const MachineInstr *ThisMI = Use->getParent();
160 const MachineInstr *XMI = X.Use->getParent();
161 const MachineBasicBlock *ThisMBB = ThisMI->getParent();
162 if (ThisMBB == XMI->getParent()) {
163 if (ThisMI->isPHI() && !XMI->isPHI() &&
164 XMI == &(*ThisMBB->getFirstNonPHI()))
165 return true;
166 }
167
168 // Ensure deterministic results
169 return X.getReg() < getReg();
170 }
171
172 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr,
173 const MachineRegisterInfo *MRI = nullptr) const {
174 if (isUnset()) {
175 OS << "<unset>";
176 return;
177 }
178 Dist.print(OS);
179 OS << " [" << printReg(Reg: getReg(), TRI, SubIdx: getSubReg(), MRI) << "]";
180 }
181
182 LLVM_DUMP_METHOD void dump() const {
183 print(OS&: dbgs());
184 dbgs() << '\n';
185 }
186};
187
188inline bool updateClosest(LiveRegUse &Closest, const LiveRegUse &X) {
189 if (!Closest.Use || X.isCloserThan(X: Closest)) {
190 Closest = X;
191 return true;
192 }
193 return false;
194}
195
196inline bool updateFurthest(LiveRegUse &Furthest, const LiveRegUse &X) {
197 if (!Furthest.Use || Furthest.isCloserThan(X)) {
198 Furthest = X;
199 return true;
200 }
201 return false;
202}
203} // namespace
204
205//==============================================================================
206// JSON helpers
207//==============================================================================
208namespace {
209template <typename Lambda>
210void printStringAttr(json::OStream &J, const char *Name, Lambda L) {
211 J.attributeBegin(Key: Name);
212 raw_ostream &OS = J.rawValueBegin();
213 OS << '"';
214 L(OS);
215 OS << '"';
216 J.rawValueEnd();
217 J.attributeEnd();
218}
219void printStringAttr(json::OStream &J, const char *Name, Printable P) {
220 printStringAttr(J, Name, L: [&](raw_ostream &OS) { OS << P; });
221}
222
223void printStringAttr(json::OStream &J, const char *Name, const MachineInstr &MI,
224 ModuleSlotTracker &MST) {
225 printStringAttr(J, Name, L: [&](raw_ostream &OS) {
226 MI.print(OS, MST,
227 /* IsStandalone */ false,
228 /* SkipOpers */ false,
229 /* SkipDebugLoc */ false,
230 /* AddNewLine ---> */ AddNewLine: false,
231 /* TargetInstrInfo */ TII: nullptr);
232 });
233}
234
235void printMBBNameAttr(json::OStream &J, const char *Name,
236 const MachineBasicBlock &MBB, ModuleSlotTracker &MST) {
237 printStringAttr(J, Name, L: [&](raw_ostream &OS) {
238 MBB.printName(os&: OS, printNameFlags: MachineBasicBlock::PrintNameIr, moduleSlotTracker: &MST);
239 });
240}
241
242template <typename NameLambda, typename ValueT>
243void printAttr(json::OStream &J, NameLambda NL, ValueT V) {
244 std::string Name;
245 raw_string_ostream NameOS(Name);
246 NL(NameOS);
247 J.attribute(Key: NameOS.str(), Contents: V);
248}
249
250template <typename ValueT>
251void printAttr(json::OStream &J, const Printable &P, ValueT V) {
252 printAttr(J, [&](raw_ostream &OS) { OS << P; }, V);
253}
254
255} // namespace
256
257//==============================================================================
258// AMDGPUNextUseAnalysisImpl
259//==============================================================================
260class llvm::AMDGPUNextUseAnalysisImpl {
261public:
262 struct CacheableNextUseDistance {
263 bool IsInstrRelative;
264 NextUseDistance Distance;
265 };
266 static constexpr bool InstrRelative = true;
267 static constexpr bool InstrInvariant = false;
268
269private:
270 const MachineFunction *MF = nullptr;
271 const SIRegisterInfo *TRI = nullptr;
272 const SIInstrInfo *TII = nullptr;
273 const MachineLoopInfo *MLI = nullptr;
274 const MachineRegisterInfo *MRI = nullptr;
275
276 using InstrIdTy = unsigned;
277 using InstrToIdMap = DenseMap<const MachineInstr *, InstrIdTy>;
278 InstrToIdMap InstrToId;
279 AMDGPUNextUseAnalysis::Config Cfg;
280
281 void initializeTables() {
282 for (const MachineBasicBlock &BB : *MF)
283 calcInstrIds(BB: &BB, MutableInstrToId&: InstrToId);
284 initializeCfgPaths();
285 initializeInterBlockDistances();
286 }
287
288 void clearTables() {
289 InstrToId.clear();
290 RegUseMap.clear();
291 Paths.clear();
292
293 resetDistanceCache();
294 }
295
296 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
297 // Instruction Ids
298 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
299private:
300 unsigned sizeOf(const MachineInstr &MI) const {
301 // When !Cfg.CountPhis, PHIs do not contribute to distances/sizes since they
302 // generally don't result in the generation of a machine instruction.
303 // FIXME: Consider using MI.isPseudo() or maybe MI.isMetaInstruction().
304 return Cfg.CountPhis ? 1 : !MI.isPHI();
305 }
306
307 void calcInstrIds(const MachineBasicBlock *BB,
308 InstrToIdMap &MutableInstrToId) const {
309 InstrIdTy Id = 0;
310 for (auto &MI : BB->instrs()) {
311 MutableInstrToId[&MI] = Id;
312 Id += sizeOf(MI);
313 }
314 }
315
316 /// Returns MI's instruction Id. It renumbers (part of) the BB if MI is not
317 /// found in the map.
318 InstrIdTy getInstrId(const MachineInstr *MI) const {
319 auto It = InstrToId.find(Val: MI);
320 if (It != InstrToId.end())
321 return It->second;
322
323 // Renumber the MBB.
324 // TODO: Renumber from MI onwards.
325 auto &MutableInstrToId = const_cast<InstrToIdMap &>(InstrToId);
326 calcInstrIds(BB: MI->getParent(), MutableInstrToId);
327 return InstrToId.find(Val: MI)->second;
328 }
329
330 // Length of the segment from MI (inclusive) to the first instruction of the
331 // basic block.
332 InstrIdTy getHeadLen(const MachineInstr *MI) const {
333 const MachineBasicBlock *MBB = MI->getParent();
334 return getInstrId(MI) + getInstrId(MI: &MBB->instr_front()) + 1;
335 }
336
337 // Length of the segment from MI (exclusive) to the last instruction of the
338 // basic block.
339 InstrIdTy getTailLen(const MachineInstr *MI) const {
340 const MachineBasicBlock *MBB = MI->getParent();
341 return getInstrId(MI: &MBB->instr_back()) - getInstrId(MI);
342 }
343
344 // Length of the segment from 'From' to 'To' (exclusive). Both instructions
345 // must be in the same basic block.
346 InstrIdTy getDistance(const MachineInstr *From,
347 const MachineInstr *To) const {
348 assert(From->getParent() == To->getParent());
349 return getInstrId(MI: To) - getInstrId(MI: From);
350 }
351
352 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
353 // RegUses - cache of uses by register
354 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
355private:
356 DenseMap<Register, SmallVector<const MachineOperand *>> RegUseMap;
357
358 const SmallVector<const MachineOperand *> &
359 getRegisterUses(Register Reg) const {
360 auto I = RegUseMap.find(Val: Reg);
361 if (I != RegUseMap.end())
362 return I->second;
363
364 auto *NonConstThis = const_cast<AMDGPUNextUseAnalysisImpl *>(this);
365 SmallVector<const MachineOperand *> &Uses = NonConstThis->RegUseMap[Reg];
366 for (const MachineOperand &UseMO : MRI->use_nodbg_operands(Reg)) {
367 if (!UseMO.isUndef())
368 Uses.push_back(Elt: &UseMO);
369 }
370 return Uses;
371 }
372
373 bool hasAtLeastOneUse(Register Reg) const {
374 return !getRegisterUses(Reg).empty();
375 }
376
377 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
378 // Paths
379 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
380private:
381 class Path {
382 using StorageTy =
383 std::pair<const MachineBasicBlock *, const MachineBasicBlock *>;
384 StorageTy P;
385
386 public:
387 constexpr Path() : P(nullptr, nullptr) {}
388 constexpr Path(const MachineBasicBlock *Src, const MachineBasicBlock *Dst)
389 : P(Src, Dst) {}
390 Path(const StorageTy &Pair) : P(Pair) {}
391
392 constexpr operator const StorageTy &() const { return P; }
393 using DenseMapInfo = llvm::DenseMapInfo<StorageTy>;
394
395 const MachineBasicBlock *src() const { return P.first; }
396 const MachineBasicBlock *dst() const { return P.second; }
397 };
398
399 enum class EdgeKind { Back = -1, None = 0, Forward = 1 };
400 static constexpr StringRef toString(EdgeKind EK) {
401 if (EK == EdgeKind::Back)
402 return "back";
403 if (EK == EdgeKind::Forward)
404 return "fwd";
405 return "none";
406 }
407
408 struct PathInfo {
409 EdgeKind EK;
410 bool Reachable;
411 int ForwardReachable;
412 unsigned RelativeLoopDepth;
413 std::optional<NextUseDistance> ShortestDistance;
414 std::optional<NextUseDistance> ShortestUnweightedDistance;
415 InstrIdTy Size;
416
417 PathInfo()
418 : EK(EdgeKind::None), Reachable(false), ForwardReachable(-1),
419 RelativeLoopDepth(0), Size(0) {}
420
421 bool isBackedge() const { return EK == EdgeKind::Back; }
422
423 bool isForwardReachableSet() const { return 0 <= ForwardReachable; }
424 bool isForwardReachableUnset() const { return ForwardReachable < 0; }
425 bool isForwardReachable() const { return ForwardReachable == 1; }
426 bool isNotForwardReachable() const { return ForwardReachable == 0; }
427
428 void print(raw_ostream &OS) const {
429 OS << "{ek=" << toString(EK) << " reach=" << Reachable
430 << " fwd-reach=" << ForwardReachable
431 << " loop-depth=" << RelativeLoopDepth << " size=" << Size;
432 if (ShortestDistance) {
433 OS << " shortest-dist=";
434 ShortestDistance->print(OS);
435 }
436 if (ShortestUnweightedDistance) {
437 OS << " shortest-unweighted-dist=";
438 ShortestUnweightedDistance->print(OS);
439 }
440 OS << "}";
441 }
442
443 LLVM_DUMP_METHOD void dump() const {
444 print(OS&: dbgs());
445 dbgs() << '\n';
446 }
447 };
448
449 //----------------------------------------------------------------------------
450 // Path Storage - 'Paths' is lazily populated and some members are lazily
451 // computed. All mutations should go through one of the 'initializePathInfo*'
452 // flavors below.
453 //----------------------------------------------------------------------------
454 DenseMap<Path, PathInfo, Path::DenseMapInfo> Paths;
455
456 const PathInfo *maybePathInfoFor(const MachineBasicBlock *From,
457 const MachineBasicBlock *To) const {
458 auto I = Paths.find(Val: {From, To});
459 return I == Paths.end() ? nullptr : &I->second;
460 }
461
462 PathInfo &getOrInitPathInfo(const MachineBasicBlock *From,
463 const MachineBasicBlock *To) const {
464 auto *NonConstThis = const_cast<AMDGPUNextUseAnalysisImpl *>(this);
465 auto &MutablePaths = NonConstThis->Paths;
466
467 Path P(From, To);
468 auto [I, Inserted] = MutablePaths.try_emplace(Key: P);
469 if (!Inserted)
470 return I->second;
471
472 bool Reachable = calcIsReachable(From: P.src(), To: P.dst());
473
474 // Iterator may have been invalidated by calcIsReachable, so get a fresh
475 // reference to the slot.
476 return NonConstThis->initializePathInfo(Slot&: MutablePaths.at(Val: P), P,
477 EK: EdgeKind::None, Reachable);
478 }
479
480 const PathInfo &pathInfoFor(const MachineBasicBlock *From,
481 const MachineBasicBlock *To) const {
482 return getOrInitPathInfo(From, To);
483 }
484
485 //----------------------------------------------------------------------------
486 // initializePathInfo* - various flavors of PathInfo initialization. They
487 // (should) always funnel to the first flavor below.
488 //----------------------------------------------------------------------------
489 PathInfo &initializePathInfo(PathInfo &Slot, Path P, EdgeKind EK,
490 bool Reachable) {
491 Slot.EK = EK;
492 Slot.Reachable = Reachable;
493 Slot.ForwardReachable = EK == EdgeKind::None ? -1 : EK == EdgeKind::Forward;
494 Slot.RelativeLoopDepth =
495 Slot.Reachable ? calcRelativeLoopDepth(From: P.src(), To: P.dst()) : 0;
496 Slot.Size = P.src() == P.dst() ? calcSize(BB: P.src()) : 0;
497 if (EK != EdgeKind::None)
498 Slot.ShortestUnweightedDistance = 0;
499 return Slot;
500 }
501
502 PathInfo &initializePathInfo(Path P, EdgeKind EK, bool Reachable) const {
503 auto *NonConstThis = const_cast<AMDGPUNextUseAnalysisImpl *>(this);
504 auto &MutablePaths = NonConstThis->Paths;
505 return NonConstThis->initializePathInfo(Slot&: MutablePaths[P], P, EK, Reachable);
506 }
507
508 std::pair<PathInfo *, bool> maybeInitializePathInfo(Path P, EdgeKind EK,
509 bool Reachable) const {
510 auto *NonConstThis = const_cast<AMDGPUNextUseAnalysisImpl *>(this);
511 auto &MutablePaths = NonConstThis->Paths;
512 auto [I, Inserted] = MutablePaths.try_emplace(Key: P);
513 if (Inserted)
514 NonConstThis->initializePathInfo(Slot&: I->second, P, EK, Reachable);
515 return {&I->second, Inserted};
516 }
517
518 bool initializePathInfoForwardReachable(const MachineBasicBlock *From,
519 const MachineBasicBlock *To,
520 bool Value) const {
521 PathInfo &Slot = getOrInitPathInfo(From, To);
522 assert(Slot.isForwardReachableUnset());
523 Slot.ForwardReachable = Value;
524 return Value;
525 }
526
527 NextUseDistance
528 initializePathInfoShortestDistance(const MachineBasicBlock *From,
529 const MachineBasicBlock *To,
530 NextUseDistance Value) const {
531 PathInfo &Slot = getOrInitPathInfo(From, To);
532 assert(!Slot.ShortestDistance.has_value());
533 Slot.ShortestDistance = Value;
534 return Value;
535 }
536
537 NextUseDistance
538 initializePathInfoShortestUnweightedDistance(const MachineBasicBlock *From,
539 const MachineBasicBlock *To,
540 NextUseDistance Value) const {
541 PathInfo &Slot = getOrInitPathInfo(From, To);
542 assert(!Slot.ShortestUnweightedDistance.has_value());
543 Slot.ShortestUnweightedDistance = Value;
544 return Value;
545 }
546
547 //----------------------------------------------------------------------------
548 // initialize*Paths
549 //----------------------------------------------------------------------------
550private:
551 void initializePaths(const SmallVector<Path> &ReachablePaths,
552 const SmallVector<Path> &UnreachablePaths) const {
553 for (const Path &P : ReachablePaths)
554 initializePathInfo(P, EK: EdgeKind::None, Reachable: true);
555 for (const Path &P : UnreachablePaths)
556 initializePathInfo(P, EK: EdgeKind::None, Reachable: false);
557 }
558
559 void
560 initializeForwardOnlyPaths(const SmallVector<Path> &ReachablePaths,
561 const SmallVector<Path> &UnreachablePaths) const {
562 for (bool R : {true, false}) {
563 const auto &ToInit = R ? ReachablePaths : UnreachablePaths;
564 for (const Path &P : ToInit) {
565 PathInfo &Slot = getOrInitPathInfo(From: P.src(), To: P.dst());
566 assert(Slot.isForwardReachableUnset() || Slot.ForwardReachable == R);
567 Slot.ForwardReachable = R;
568 }
569 }
570 }
571
572 // Follow the control flow graph starting at the entry block until all blocks
573 // have been visited. Along the way, initialize the PathInfo for each edge
574 // traversed.
575 void initializeCfgPaths() {
576 Paths.clear();
577
578 enum VisitState { Undiscovered, Visiting, Finished };
579 DenseMap<const MachineBasicBlock *, VisitState> State;
580
581 SmallVector<const MachineBasicBlock *> Work{&MF->front()};
582 State[&MF->front()] = Undiscovered;
583
584 while (!Work.empty()) {
585 const MachineBasicBlock *Src = Work.back();
586 VisitState &SrcState = State[Src];
587
588 // A block may already be 'Finished' if it is reachable from multiple
589 // predecessors causing it to be pushed more than once while still
590 // 'Undiscovered'.
591 if (SrcState == Visiting || SrcState == Finished) {
592 Work.pop_back();
593 SrcState = Finished;
594 continue;
595 }
596
597 SrcState = Visiting;
598 for (const MachineBasicBlock *Dst : Src->successors()) {
599 const VisitState DstState = State.lookup(Val: Dst);
600
601 EdgeKind EK;
602 if (DstState == Undiscovered) {
603 EK = EdgeKind::Forward;
604 Work.push_back(Elt: Dst);
605 } else if (DstState == Visiting) {
606 EK = EdgeKind::Back;
607 } else {
608 EK = EdgeKind::Forward;
609 }
610
611 Path P(Src, Dst);
612 assert(!Paths.contains(P));
613 initializePathInfo(P, EK, /*Reachable*/ true);
614 }
615 }
616
617 LLVM_DEBUG(dumpPaths());
618 }
619
620 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
621 // Loop helpers
622 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
623private:
624 static bool isStandAloneLoop(const MachineLoop *Loop) {
625 return Loop->getSubLoops().empty() && Loop->isOutermost();
626 }
627
628 static MachineLoop *findChildLoop(MachineLoop *const Parent,
629 MachineLoop *Descendant) {
630 for (MachineLoop *L = Descendant; L != Parent; L = L->getParentLoop()) {
631 if (L->getParentLoop() == Parent)
632 return L;
633 }
634 return nullptr;
635 }
636
637 // If loops 'A' and 'B' share a common parent loop, return that loop and the
638 // depth of 'A' relative to it. Otherwise return nullptr and the loop depth of
639 // 'A'.
640 static std::pair<MachineLoop *, unsigned>
641 findCommonParent(MachineLoop *A, const MachineLoop *B) {
642 unsigned Depth = 0;
643 for (; A != nullptr; A = A->getParentLoop(), ++Depth) {
644 if (A->contains(L: B))
645 break;
646 }
647 return {A, Depth};
648 }
649
650 static const MachineBasicBlock *
651 getOutermostPreheader(const MachineLoop *Loop) {
652 return Loop ? Loop->getOutermostLoop()->getLoopPreheader() : nullptr;
653 }
654
655 static MachineBasicBlock *findChildPreheader(MachineLoop *const Parent,
656 MachineLoop *Descendant) {
657 MachineLoop *ChildLoop = findChildLoop(Parent, Descendant);
658 return ChildLoop ? ChildLoop->getLoopPreheader() : nullptr;
659 }
660
661 static const MachineBasicBlock *
662 getIncomingBlockIfPhiUse(const MachineInstr *MI, const MachineOperand *MO) {
663 return MI->isPHI() ? MI->getOperand(i: MO->getOperandNo() + 1).getMBB()
664 : nullptr;
665 }
666
667 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
668 // Calculate features
669 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
670private:
671 InstrIdTy calcSize(const MachineBasicBlock *BB) const {
672 InstrIdTy Size = BB->size();
673 if (!Cfg.CountPhis)
674 Size -= std::distance(first: BB->begin(), last: BB->getFirstNonPHI());
675 return Size;
676 }
677
678 NextUseDistance calcWeightedSize(const MachineBasicBlock *From,
679 const MachineBasicBlock *To) const {
680 return NextUseDistance::fromSize(Size: getSize(BB: From),
681 Depth: getRelativeLoopDepth(From, To));
682 }
683
684 // Return the loop depth of 'From' relative to 'To'.
685 unsigned calcRelativeLoopDepth(const MachineBasicBlock *From,
686 const MachineBasicBlock *To) const {
687 MachineLoop *LoopFrom = MLI->getLoopFor(BB: From);
688 MachineLoop *LoopTo = MLI->getLoopFor(BB: To);
689
690 if (!LoopFrom)
691 return 0;
692
693 if (!LoopTo)
694 return LoopFrom->getLoopDepth();
695
696 if (LoopFrom->contains(L: LoopTo)) // covers LoopFrom == LoopTo
697 return 0;
698
699 if (LoopTo->contains(L: LoopFrom))
700 return LoopFrom->getLoopDepth() - LoopTo->getLoopDepth();
701
702 // Loops are siblings of some sort.
703 return findCommonParent(A: LoopFrom, B: LoopTo).second;
704 }
705
706 // Attempt to find a path from 'From' to 'To' using a depth first search. If
707 // 'ForwardOnly' is true, do not follow backedges. As a performance
708 // improvement, this may initialize reachable intermediate paths or paths we
709 // determine are unreachable.
710 bool calcIsReachable(const MachineBasicBlock *From,
711 const MachineBasicBlock *To,
712 bool ForwardOnly = false) const {
713 if (From == To && !MLI->getLoopFor(BB: From))
714 return false;
715
716 if (!ForwardOnly && interBlockDistanceExists(From, To))
717 return true;
718
719 enum { VisitOp, PopOp };
720 using MBBOpPair = std::pair<const MachineBasicBlock *, int>;
721 SmallVector<MBBOpPair> Work{{From, VisitOp}};
722 DenseSet<const MachineBasicBlock *> Visited{From};
723
724 SmallVector<Path> IntermediatePath;
725 SmallVector<Path> Unreachable;
726
727 // Should be run at every function exit point.
728 auto Finally = [&](bool Reachable) {
729 // This is an optimization. For intermediate paths we found while
730 // calculating reachability for 'From' --> 'To', remember their
731 // reachability.
732 if (!Reachable) {
733 IntermediatePath.clear();
734 for (const MachineBasicBlock *MBB : Visited) {
735 if (MBB != From)
736 Unreachable.emplace_back(Args&: MBB, Args&: To);
737 }
738 }
739
740 if (ForwardOnly)
741 initializeForwardOnlyPaths(ReachablePaths: IntermediatePath, UnreachablePaths: Unreachable);
742 else
743 initializePaths(ReachablePaths: IntermediatePath, UnreachablePaths: Unreachable);
744
745 return Reachable;
746 };
747
748 while (!Work.empty()) {
749 auto [Current, Op] = Work.pop_back_val();
750
751 // Backtracking
752 if (Op == PopOp) {
753 IntermediatePath.pop_back();
754 if (ForwardOnly)
755 Unreachable.emplace_back(Args&: Current, Args&: To);
756 continue;
757 }
758
759 if (Current->succ_empty())
760 continue;
761
762 if (Current != From) {
763 IntermediatePath.emplace_back(Args&: Current, Args&: To);
764 Work.emplace_back(Args&: Current, Args: PopOp);
765 }
766
767 for (const MachineBasicBlock *Succ : Current->successors()) {
768 if (ForwardOnly && isBackedge(From: Current, To: Succ))
769 continue;
770
771 if (Succ == To)
772 return Finally(true);
773
774 if (auto CachedReachable = isMaybeReachable(From: Succ, To, ForwardOnly)) {
775 if (CachedReachable.value())
776 return Finally(true);
777 Visited.insert(V: Succ);
778 continue;
779 }
780
781 if (Visited.insert(V: Succ).second)
782 Work.emplace_back(Args&: Succ, Args: VisitOp);
783 }
784 }
785
786 return Finally(false);
787 }
788
789 //----------------------------------------------------------------------------
790 // Inter-block distance - the weighted and unweighted cost (i.e. "distance")
791 // to travel from one MachineBasicBlock to another.
792 //
793 // Values are pre-computed and stored in 'InterBlockDistances' using a
794 // backwards data-flow algorithm similar to the one described in 4.1 of a
795 // "Register Spilling and Live-Range Splitting for SSA-Form Programs" by
796 // Matthias Braun and Sebastian Hack, CC'09. This replaced a prior
797 // implementation based on Dijkstra's shortest path algorithm.
798 //----------------------------------------------------------------------------
799private:
800 struct InterBlockDistance {
801 NextUseDistance Weighted;
802 NextUseDistance Unweighted;
803 InterBlockDistance() : Weighted(-1), Unweighted(-1) {}
804 InterBlockDistance(NextUseDistance W, NextUseDistance UW)
805 : Weighted(W), Unweighted(UW) {}
806 bool operator==(const InterBlockDistance &Other) const {
807 return Weighted == Other.Weighted && Unweighted == Other.Unweighted;
808 }
809 bool operator!=(const InterBlockDistance &Other) const {
810 return !(*this == Other);
811 }
812
813 void print(raw_ostream &OS) const {
814 OS << "{W=";
815 Weighted.print(OS);
816 OS << " U=";
817 Unweighted.print(OS);
818 OS << "}";
819 }
820
821 LLVM_DUMP_METHOD void dump() const {
822 print(OS&: dbgs());
823 dbgs() << '\n';
824 }
825 };
826 using InterBlockDistanceMap =
827 DenseMap<unsigned, DenseMap<unsigned, InterBlockDistance>>;
828 InterBlockDistanceMap InterBlockDistances;
829
830 void initializeInterBlockDistances() {
831 InterBlockDistanceMap Distances;
832
833 bool Changed;
834 do {
835 Changed = false;
836 for (const MachineBasicBlock *MBB : post_order(G: MF)) {
837 unsigned MBBNum = MBB->getNumber();
838
839 // Save previous state for convergence check
840 InterBlockDistanceMap::mapped_type Prev = std::move(Distances[MBBNum]);
841 InterBlockDistanceMap::mapped_type Curr;
842 Curr.reserve(NumEntries: Prev.size());
843
844 // Direct successors are distance 0 by definition: no instructions are
845 // executed between exiting MBB and entering Succ.
846 for (const MachineBasicBlock *Succ : MBB->successors())
847 Curr[Succ->getNumber()] = InterBlockDistance(0, 0);
848
849 // Propagate further destinations through each successor.
850 for (const MachineBasicBlock *Succ : MBB->successors()) {
851 unsigned SuccNum = Succ->getNumber();
852 const unsigned UnweightedSize{getSize(BB: Succ)};
853
854 for (const auto &[DestBlockNum, DestDist] : Distances[SuccNum]) {
855 // MBB -> MBB is considered unreachable (getInterBlockDistance
856 // asserts From != To).
857 if (DestBlockNum == MBBNum)
858 continue;
859
860 const MachineBasicBlock *DestMBB =
861 MF->getBlockNumbered(N: DestBlockNum);
862
863 const NextUseDistance UnweightedDist{UnweightedSize +
864 DestDist.Unweighted};
865
866 unsigned SuccToDestLoopDepth = calcRelativeLoopDepth(From: Succ, To: DestMBB);
867
868 const NextUseDistance WeightedDist =
869 DestDist.Weighted +
870 NextUseDistance::fromSize(Size: UnweightedSize, Depth: SuccToDestLoopDepth);
871
872 // Insert or update distances (take minimum)
873 auto [I, First] =
874 Curr.try_emplace(Key: DestBlockNum, Args: WeightedDist, Args: UnweightedDist);
875 if (!First) {
876 InterBlockDistance &Slot = I->second;
877 Slot.Weighted = min(A: Slot.Weighted, B: WeightedDist);
878 Slot.Unweighted = min(A: Slot.Unweighted, B: UnweightedDist);
879 }
880 }
881 }
882 Changed |= (Prev != Curr);
883 Distances[MBBNum] = std::move(Curr);
884 }
885 } while (Changed);
886
887 InterBlockDistances = std::move(Distances);
888 LLVM_DEBUG(dumpInterBlockDistances());
889 }
890
891 const InterBlockDistance *
892 getInterBlockDistanceMapValue(const MachineBasicBlock *From,
893 const MachineBasicBlock *To) const {
894 auto I = InterBlockDistances.find(Val: From->getNumber());
895 if (I == InterBlockDistances.end())
896 return nullptr;
897 const InterBlockDistanceMap::mapped_type &FromSlot = I->second;
898 auto J = FromSlot.find(Val: To->getNumber());
899 return J == FromSlot.end() ? nullptr : &J->second;
900 }
901
902 bool interBlockDistanceExists(const MachineBasicBlock *From,
903 const MachineBasicBlock *To) const {
904 return getInterBlockDistanceMapValue(From, To);
905 }
906
907 NextUseDistance getInterBlockDistance(const MachineBasicBlock *From,
908 const MachineBasicBlock *To,
909 bool Unweighted) const {
910
911 assert(From != To && "The basic blocks should be different.");
912 if (!From || !To)
913 return NextUseDistance::unreachable();
914
915 if (Cfg.ForwardOnly && !isForwardReachable(From, To))
916 return NextUseDistance::unreachable();
917
918 const InterBlockDistance *BD = getInterBlockDistanceMapValue(From, To);
919 if (!BD)
920 return NextUseDistance::unreachable();
921
922 return Unweighted ? BD->Unweighted : BD->Weighted;
923 }
924
925 NextUseDistance
926 getWeightedInterBlockDistance(const MachineBasicBlock *From,
927 const MachineBasicBlock *To) const {
928 return getInterBlockDistance(From, To, Unweighted: false);
929 }
930
931 NextUseDistance
932 getUnweightedInterBlockDistance(const MachineBasicBlock *From,
933 const MachineBasicBlock *To) const {
934 return getInterBlockDistance(From, To, Unweighted: true);
935 }
936
937 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
938 // Feature getters. Use cached results if available. If not calculate.
939 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
940private:
941 InstrIdTy getSize(const MachineBasicBlock *BB) const {
942 return pathInfoFor(From: BB, To: BB).Size;
943 }
944
945 bool isReachable(const MachineBasicBlock *From,
946 const MachineBasicBlock *To) const {
947 return pathInfoFor(From, To).Reachable;
948 }
949
950 bool isReachableOrSame(const MachineBasicBlock *From,
951 const MachineBasicBlock *To) const {
952 return From == To || pathInfoFor(From, To).Reachable;
953 }
954
955 bool isForwardReachable(const MachineBasicBlock *From,
956 const MachineBasicBlock *To) const {
957 const PathInfo &PI = pathInfoFor(From, To);
958 if (PI.isForwardReachableSet())
959 return PI.isForwardReachable();
960
961 return initializePathInfoForwardReachable(
962 From, To,
963 Value: PI.Reachable && calcIsReachable(From, To, /*ForwardOnly*/ true));
964 }
965
966 // Return true/false if we know that 'To' is reachable or not from
967 // 'From'. Otherwise return 'std::nullopt'.
968 std::optional<bool> isMaybeReachable(const MachineBasicBlock *From,
969 const MachineBasicBlock *To,
970 bool ForwardOnly) const {
971 const PathInfo *PI = maybePathInfoFor(From, To);
972 if (!PI)
973 return std::nullopt;
974
975 if (ForwardOnly) {
976 if (PI->isForwardReachable())
977 return true;
978
979 if (PI->isNotForwardReachable())
980 return false;
981 return std::nullopt;
982 }
983 return PI->Reachable;
984 }
985
986 bool isBackedge(const MachineBasicBlock *From,
987 const MachineBasicBlock *To) const {
988 return pathInfoFor(From, To).isBackedge();
989 }
990
991 // Can be used as a substitute for DT->dominates(A, B) if A and B are in the
992 // same basic block.
993 bool instrsAreInOrder(const MachineInstr *A, const MachineInstr *B) const {
994 assert(A->getParent() == B->getParent() &&
995 "instructions must be in the same basic block!");
996 if (A == B || getInstrId(MI: A) < getInstrId(MI: B))
997 return true;
998 if (!A->isPHI())
999 return false;
1000 if (!B->isPHI())
1001 return true;
1002 for (auto &PHI : A->getParent()->phis()) {
1003 if (&PHI == A)
1004 return true;
1005 if (&PHI == B)
1006 return false;
1007 }
1008 return false;
1009 }
1010
1011 unsigned getRelativeLoopDepth(const MachineBasicBlock *From,
1012 const MachineBasicBlock *To) const {
1013 return pathInfoFor(From, To).RelativeLoopDepth;
1014 }
1015
1016 NextUseDistance getShortestPath(const MachineBasicBlock *From,
1017 const MachineBasicBlock *To) const {
1018 std::optional<NextUseDistance> MaybeD =
1019 pathInfoFor(From, To).ShortestDistance;
1020 if (MaybeD.has_value())
1021 return MaybeD.value();
1022
1023 NextUseDistance Dist = getWeightedInterBlockDistance(From, To);
1024 return initializePathInfoShortestDistance(From, To, Value: Dist);
1025 }
1026
1027 NextUseDistance getShortestUnweightedPath(const MachineBasicBlock *From,
1028 const MachineBasicBlock *To) const {
1029 std::optional<NextUseDistance> MaybeD =
1030 pathInfoFor(From, To).ShortestUnweightedDistance;
1031 if (MaybeD.has_value())
1032 return MaybeD.value();
1033
1034 return initializePathInfoShortestUnweightedDistance(
1035 From, To, Value: getUnweightedInterBlockDistance(From, To));
1036 }
1037
1038 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1039 /// MBBDistPair - Represents the distance to a machine basic block.
1040 /// Used for returning both the distance and the target block together.
1041 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1042private:
1043 struct MBBDistPair {
1044 NextUseDistance Distance;
1045 const MachineBasicBlock *MBB;
1046 MBBDistPair() : Distance(NextUseDistance::unreachable()), MBB(nullptr) {}
1047 MBBDistPair(NextUseDistance D, const MachineBasicBlock *B)
1048 : Distance(D), MBB(B) {}
1049
1050 MBBDistPair operator+(NextUseDistance D) { return {Distance + D, MBB}; }
1051 MBBDistPair &operator+=(NextUseDistance D) {
1052 Distance += D;
1053 return *this;
1054 }
1055
1056 void print(raw_ostream &OS) const {
1057 OS << "{";
1058 Distance.print(OS);
1059 if (MBB)
1060 OS << " " << printMBBReference(MBB: *MBB);
1061 else
1062 OS << " <null>";
1063 OS << "}";
1064 }
1065
1066 LLVM_DUMP_METHOD void dump() const {
1067 print(OS&: dbgs());
1068 dbgs() << '\n';
1069 }
1070 };
1071
1072 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1073 // CFG Helpers
1074 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1075private:
1076 // Return the shortest distance to a latch
1077 MBBDistPair calcShortestDistanceToLatch(const MachineBasicBlock *CurMBB,
1078 const MachineLoop *CurLoop) const {
1079 SmallVector<MachineBasicBlock *, 2> Latches;
1080 CurLoop->getLoopLatches(LoopLatches&: Latches);
1081 MBBDistPair LD;
1082
1083 for (MachineBasicBlock *LMBB : Latches) {
1084 if (LMBB == CurMBB)
1085 return {0, CurMBB};
1086
1087 NextUseDistance Dst = getShortestPath(From: CurMBB, To: LMBB);
1088 if (Dst < LD.Distance) {
1089 LD.Distance = Dst;
1090 LD.MBB = LMBB;
1091 }
1092 }
1093 return LD;
1094 }
1095
1096 // Return the shortest unweighted distance to a latch
1097 MBBDistPair
1098 calcShortestUnweightedDistanceToLatch(const MachineBasicBlock *CurMBB,
1099 const MachineLoop *CurLoop) const {
1100 SmallVector<MachineBasicBlock *, 2> Latches;
1101 CurLoop->getLoopLatches(LoopLatches&: Latches);
1102 MBBDistPair LD;
1103
1104 for (MachineBasicBlock *LMBB : Latches) {
1105 if (LMBB == CurMBB)
1106 return {0, CurMBB};
1107
1108 NextUseDistance Dst = getShortestUnweightedPath(From: CurMBB, To: LMBB);
1109 if (Dst < LD.Distance) {
1110 LD.Distance = Dst;
1111 LD.MBB = LMBB;
1112 }
1113 }
1114 return LD;
1115 }
1116
1117 // Return the shortest distance to an exit
1118 MBBDistPair calcShortestDistanceToExit(const MachineBasicBlock *CurMBB,
1119 const MachineLoop *CurLoop) const {
1120 SmallVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ExitEdges;
1121 MLI->getExitEdges(L: *CurLoop, ExitEdges);
1122 MBBDistPair LD;
1123
1124 for (auto [Exit, Dest] : ExitEdges) {
1125 if (Exit == CurMBB)
1126 return {0, CurMBB};
1127
1128 NextUseDistance Dst = getShortestPath(From: CurMBB, To: Exit);
1129 if (Dst < LD.Distance) {
1130 LD.Distance = Dst;
1131 LD.MBB = Exit;
1132 }
1133 }
1134 return LD;
1135 }
1136
1137 // Return the shortest distance through a loop (header to latch) that goes
1138 // through CurMBB.
1139 MBBDistPair
1140 calcShortestDistanceThroughInnermostLoop(const MachineBasicBlock *CurMBB,
1141 MachineLoop *CurLoop) const {
1142 assert(MLI->getLoopFor(CurMBB) == CurLoop);
1143
1144 // This is a hot spot. Check it before doing anything else.
1145 if (CurLoop->getNumBlocks() == 1)
1146 return {getSize(BB: CurMBB), CurMBB};
1147
1148 MachineBasicBlock *LoopHeader = CurLoop->getHeader();
1149 MBBDistPair LD{0, nullptr};
1150
1151 LD += getSize(BB: LoopHeader);
1152
1153 if (CurMBB != LoopHeader)
1154 LD += getShortestPath(From: LoopHeader, To: CurMBB);
1155
1156 if (CurLoop->isLoopExiting(BB: CurMBB))
1157 LD.MBB = CurMBB;
1158 else
1159 LD = calcShortestDistanceToExit(CurMBB, CurLoop) + LD.Distance;
1160
1161 if (CurMBB != LoopHeader && CurMBB != LD.MBB)
1162 LD += getSize(BB: CurMBB);
1163
1164 if (LD.MBB != LoopHeader)
1165 LD += getSize(BB: LD.MBB);
1166
1167 return LD;
1168 }
1169
1170 // Return the shortest distance through a loop (header to latch) that goes
1171 // through CurMBB.
1172 MBBDistPair calcShortestDistanceThroughLoop(const MachineBasicBlock *CurMBB,
1173 MachineLoop *OuterLoop) const {
1174 MachineLoop *CurLoop = MLI->getLoopFor(BB: CurMBB);
1175 MBBDistPair CurLD =
1176 calcShortestDistanceThroughInnermostLoop(CurMBB, CurLoop);
1177
1178 MachineBasicBlock *CurHdr = CurLoop->getHeader();
1179 for (;;) {
1180 if (OuterLoop == CurLoop)
1181 return CurLD;
1182
1183 MachineLoop *ParentLoop = CurLoop->getParentLoop();
1184 MachineBasicBlock *ParentHdr = ParentLoop->getHeader();
1185
1186 MBBDistPair LD{0, nullptr};
1187 LD += getSize(BB: ParentHdr);
1188 LD += getShortestPath(From: ParentHdr, To: CurHdr);
1189 LD += CurLD.Distance.applyLoopWeight();
1190 LD = calcShortestDistanceToExit(CurMBB: CurLD.MBB, CurLoop: ParentLoop) + LD.Distance;
1191 LD += getSize(BB: LD.MBB);
1192 CurLD = LD;
1193 CurLoop = ParentLoop;
1194 CurHdr = ParentHdr;
1195 }
1196 llvm_unreachable("CurMBB not contained in OuterLoop");
1197 }
1198
1199 // Similar to calcShortestDistanceThroughLoop with LoopWeight applied to the
1200 // returned distance.
1201 MBBDistPair
1202 calcWeightedDistanceThroughLoopViaMBB(const MachineBasicBlock *CurMBB,
1203 MachineLoop *CurLoop) const {
1204 MBBDistPair LD = calcShortestDistanceThroughLoop(CurMBB, OuterLoop: CurLoop);
1205 LD.Distance = LD.Distance.applyLoopWeight();
1206 return LD;
1207 }
1208
1209 // Return the weighted, shortest distance through a loop (header to latch).
1210 // If ParentLoop is provided, use it to adjust the loop depth.
1211 MBBDistPair calcWeightedDistanceThroughLoop(
1212 const MachineBasicBlock *CurMBB, MachineLoop *CurLoop,
1213 const MachineLoop *ParentLoop = nullptr) const {
1214 if (CurLoop->getNumBlocks() != 1)
1215 return calcWeightedDistanceThroughLoopViaMBB(CurMBB, CurLoop);
1216
1217 unsigned LoopDepth = MLI->getLoopDepth(BB: CurMBB);
1218 if (ParentLoop)
1219 LoopDepth -= ParentLoop->getLoopDepth();
1220
1221 return {NextUseDistance::fromSize(Size: getSize(BB: CurMBB), Depth: LoopDepth),
1222 CurLoop->getLoopLatch()};
1223 }
1224
1225 // Calculate total distance from exit point to use instruction
1226 NextUseDistance appendDistanceToUse(const MBBDistPair &Exit,
1227 const MachineInstr *UseMI,
1228 const MachineBasicBlock *UseMBB) const {
1229 return Exit.Distance + getShortestPath(From: Exit.MBB, To: UseMBB) +
1230 getHeadLen(MI: UseMI);
1231 }
1232
1233 // Return the weighted, shortest distance through the CurLoop which is a
1234 // sub-loop of UseLoop.
1235 MBBDistPair calcDistanceThroughSubLoopUse(const MachineBasicBlock *CurMBB,
1236 MachineLoop *CurLoop,
1237 MachineLoop *UseLoop) const {
1238 // All the sub-loops of the UseLoop will be executed before the use.
1239 // Hence, we should take this into consideration in distance calculation.
1240 MachineLoop *UseLoopSubLoop = findChildLoop(Parent: UseLoop, Descendant: CurLoop);
1241 assert(UseLoopSubLoop && "CurLoop should be nested in UseLoop");
1242 return calcWeightedDistanceThroughLoop(CurMBB, CurLoop: UseLoopSubLoop, ParentLoop: UseLoop);
1243 }
1244
1245 // Similar to calcDistanceThroughSubLoopUse, adding the distance to 'UseMI'.
1246 NextUseDistance calcDistanceThroughSubLoopToUseMI(
1247 const MachineBasicBlock *CurMBB, MachineLoop *CurLoop,
1248 const MachineInstr *UseMI, const MachineBasicBlock *UseMBB,
1249 MachineLoop *UseLoop) const {
1250 return appendDistanceToUse(
1251 Exit: calcDistanceThroughSubLoopUse(CurMBB, CurLoop, UseLoop), UseMI, UseMBB);
1252 }
1253
1254 // Return the weighted distance through a loop to an outside use loop.
1255 // Differentiates between uses inside or outside of the current loop nest.
1256 MBBDistPair calcDistanceThroughLoopToOutsideLoopUse(
1257 const MachineBasicBlock *CurMBB, MachineLoop *CurLoop,
1258 const MachineBasicBlock *UseMBB, MachineLoop *UseLoop) const {
1259 assert(!CurLoop->contains(UseLoop));
1260
1261 if (isStandAloneLoop(Loop: CurLoop))
1262 return calcWeightedDistanceThroughLoopViaMBB(CurMBB, CurLoop);
1263
1264 MachineLoop *OutermostLoop = CurLoop->getOutermostLoop();
1265 if (!OutermostLoop->contains(L: UseLoop)) {
1266 // We should take into consideration the whole loop nest in the
1267 // calculation of the distance because we will reach the use after
1268 // executing the whole loop nest.
1269
1270 // ... But make sure that we pick a route that goes through CurMBB
1271 return calcWeightedDistanceThroughLoopViaMBB(CurMBB, CurLoop: OutermostLoop);
1272 }
1273
1274 // At this point we know that CurLoop and UseLoop are independent and they
1275 // are in the same loop nest.
1276
1277 if (MLI->getLoopDepth(BB: CurMBB) <= MLI->getLoopDepth(BB: UseMBB))
1278 return calcWeightedDistanceThroughLoop(CurMBB, CurLoop);
1279
1280 assert(CurLoop != OutermostLoop && "The loop cannot be the outermost.");
1281 const unsigned UseLoopDepth = MLI->getLoopDepth(BB: UseMBB);
1282 for (;;) {
1283 if (CurLoop->getLoopDepth() == UseLoopDepth)
1284 break;
1285 CurLoop = CurLoop->getParentLoop();
1286 if (CurLoop == OutermostLoop)
1287 break;
1288 }
1289 return calcWeightedDistanceThroughLoop(CurMBB, CurLoop);
1290 }
1291
1292 // Similar to calcDistanceThroughLoopToOutsideLoopUse but adds the distance to
1293 // an instruction in the loop.
1294 NextUseDistance calcDistanceThroughLoopToOutsideLoopUseMI(
1295 const MachineBasicBlock *CurMBB, MachineLoop *CurLoop,
1296 const MachineInstr *UseMI, const MachineBasicBlock *UseMBB,
1297 MachineLoop *UseLoop) const {
1298 return appendDistanceToUse(Exit: calcDistanceThroughLoopToOutsideLoopUse(
1299 CurMBB, CurLoop, UseMBB, UseLoop),
1300 UseMI, UseMBB);
1301 }
1302
1303 // Return true if 'MO' is covered by 'LaneMask'
1304 bool machineOperandCoveredBy(const MachineOperand &MO,
1305 LaneBitmask LaneMask) const {
1306 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubIdx: MO.getSubReg());
1307 return (Mask & LaneMask) == Mask;
1308 }
1309
1310 // Returns true iff uses of LiveReg/LiveLaneMask in PHI UseMI are coming from
1311 // a backedge when starting at CurMI.
1312 bool isIncomingValFromBackedge(Register LiveReg, LaneBitmask LiveLaneMask,
1313 const MachineInstr *CurMI,
1314 const MachineInstr *UseMI) const {
1315 if (!UseMI->isPHI())
1316 return false;
1317
1318 MachineLoop *CurLoop = MLI->getLoopFor(BB: CurMI->getParent());
1319 MachineLoop *UseLoop = MLI->getLoopFor(BB: UseMI->getParent());
1320
1321 // Not a backedge if ...
1322 // A: not in a loop at all
1323 // B: or CurMI is in a loop outside of UseLoop
1324 // C: or UseMI is not in the UseLoop header
1325 if (/*A:*/ !UseLoop ||
1326 /*B:*/ (CurLoop && !UseLoop->contains(L: CurLoop)) ||
1327 /*C:*/ UseMI->getParent() != UseLoop->getHeader())
1328 return false;
1329
1330 SmallVector<MachineBasicBlock *, 2> Latches;
1331 UseLoop->getLoopLatches(LoopLatches&: Latches);
1332
1333 const unsigned NumOps = UseMI->getNumOperands();
1334 for (unsigned I = 1; I < NumOps; I += 2) {
1335 const MachineOperand &RegMO = UseMI->getOperand(i: I - 1);
1336 const MachineOperand &MBBMO = UseMI->getOperand(i: I);
1337 assert(RegMO.isReg() && "Expected register operand of PHI");
1338 assert(MBBMO.isMBB() && "Expected MBB operand of PHI");
1339 if (RegMO.getReg() == LiveReg &&
1340 machineOperandCoveredBy(MO: RegMO, LaneMask: LiveLaneMask)) {
1341 MachineBasicBlock *IncomingBB = MBBMO.getMBB();
1342 if (llvm::is_contained(Range&: Latches, Element: IncomingBB))
1343 return true;
1344 }
1345 }
1346 return false;
1347 }
1348
1349 // Return the distance from 'CurMI' through a parent loop backedge PHI Use
1350 // ('UseMI').
1351 CacheableNextUseDistance calcDistanceViaEnclosingBackedge(
1352 const MachineInstr *CurMI, const MachineBasicBlock *CurMBB,
1353 MachineLoop *CurLoop, const MachineInstr *UseMI,
1354 const MachineBasicBlock *UseMBB, MachineLoop *UseLoop) const {
1355 assert(UseLoop && "There is no backedge.");
1356 assert(CurLoop && (UseLoop != CurLoop) && UseLoop->contains(CurLoop) &&
1357 "Unexpected loop configuration");
1358
1359 InstrIdTy UseHeadLen = getHeadLen(MI: UseMI);
1360 MBBDistPair InnerLoopLD =
1361 calcDistanceThroughSubLoopUse(CurMBB, CurLoop, UseLoop);
1362 MBBDistPair LD = calcShortestDistanceToLatch(CurMBB: InnerLoopLD.MBB, CurLoop: UseLoop);
1363 return {.IsInstrRelative: InstrInvariant,
1364 .Distance: InnerLoopLD.Distance + LD.Distance + getSize(BB: LD.MBB) + UseHeadLen};
1365 }
1366
1367 // Optimized version of calcBackedgeDistance when we already know that CurMI
1368 // and UseMI are in the same basic block
1369 NextUseDistance calcBackedgeDistance(const MachineInstr *CurMI,
1370 const MachineBasicBlock *CurMBB,
1371 MachineLoop *CurLoop,
1372 const MachineInstr *UseMI) const {
1373 // use is in the next loop iteration
1374 InstrIdTy CurTailLen = getTailLen(MI: CurMI);
1375 InstrIdTy UseHeadLen = getHeadLen(MI: UseMI);
1376 MBBDistPair LD = calcShortestUnweightedDistanceToLatch(CurMBB, CurLoop);
1377 const MachineBasicBlock *HdrMBB = CurLoop->getHeader();
1378 NextUseDistance Hdr = CurMBB == HdrMBB ? 0 : getSize(BB: HdrMBB);
1379 NextUseDistance Dst =
1380 CurMBB == HdrMBB ? 0 : getShortestUnweightedPath(From: HdrMBB, To: CurMBB);
1381
1382 return CurTailLen + LD.Distance + getSize(BB: LD.MBB) + Hdr + Dst + UseHeadLen;
1383 }
1384
1385 //----------------------------------------------------------------------------
1386 // Calculate inter-instruction distances
1387 //----------------------------------------------------------------------------
1388private:
1389 // Calculate the shortest weighted path from MachineInstruction 'FromMI' to
1390 // 'ToMI'. It is weighted distance in that paths that exit loops are made to
1391 // look much further away.
1392 NextUseDistance calcShortestDistance(const MachineInstr *FromMI,
1393 const MachineInstr *ToMI) const {
1394 const MachineBasicBlock *FromMBB = FromMI->getParent();
1395 const MachineBasicBlock *ToMBB = ToMI->getParent();
1396
1397 if (FromMBB == ToMBB) {
1398 NextUseDistance RV = getDistance(From: FromMI, To: ToMI);
1399 assert(RV >= 0 && "unexpected negative distance from getDistance");
1400 return RV;
1401 }
1402
1403 InstrIdTy FromTailLen = getTailLen(MI: FromMI);
1404 InstrIdTy ToHeadLen = getHeadLen(MI: ToMI);
1405 NextUseDistance Dst = getShortestPath(From: FromMBB, To: ToMBB);
1406 assert(Dst.isReachable() &&
1407 "calcShortestDistance called for instructions in non-reachable"
1408 " basic blocks!");
1409 NextUseDistance RV = FromTailLen + Dst + ToHeadLen;
1410 assert(RV >= 0 && "unexpected negative distance");
1411 return RV;
1412 }
1413
1414 // Calculate the shortest unweighted path from MachineInstruction 'FromMI' to
1415 // 'ToMI'. In contrast with 'calcShortestDistance', distances are based solely
1416 // on basic block instruction counts and traversing a loop exit does not
1417 // affect the value.
1418 NextUseDistance
1419 calcShortestUnweightedDistance(const MachineInstr *FromMI,
1420 const MachineInstr *ToMI) const {
1421 const MachineBasicBlock *FromMBB = FromMI->getParent();
1422 const MachineBasicBlock *ToMBB = ToMI->getParent();
1423
1424 if (FromMBB == ToMBB)
1425 return getDistance(From: FromMI, To: ToMI);
1426
1427 InstrIdTy FromTailLen = getTailLen(MI: FromMI);
1428 InstrIdTy ToHeadLen = getHeadLen(MI: ToMI);
1429 NextUseDistance Dst = getShortestUnweightedPath(From: FromMBB, To: ToMBB);
1430 assert(Dst.isReachable() &&
1431 "calcShortestUnweightedDistance called for instructions in"
1432 " non-reachable basic blocks!");
1433 return FromTailLen + Dst + ToHeadLen;
1434 }
1435
1436 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1437 // calcDistanceToUse* - various flavors of calculating the distance from an
1438 // instruction 'CurMI' to the use of a live [sub]register.
1439 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1440private:
1441 // Return the distance from 'CurMI' to a live [sub]register use ('UseMI').
1442 //
1443 // Cfg flags controlling behavior:
1444 // PreciseUseModeling — rewrite PHI uses to their incoming edge block;
1445 // also selects unweighted cross-block distance
1446 // PromoteToPreheader — route loop-entry / inner-loop uses to the preheader
1447 CacheableNextUseDistance
1448 calcDistanceToUse(Register LiveReg, LaneBitmask LiveLaneMask,
1449 const MachineInstr &CurMI,
1450 const MachineOperand *UseMO) const {
1451 const MachineInstr *UseMI = UseMO->getParent();
1452 const MachineBasicBlock *CurMBB = CurMI.getParent();
1453 const MachineBasicBlock *UseMBB = UseMI->getParent();
1454 MachineLoop *CurLoop = MLI->getLoopFor(BB: CurMBB);
1455 MachineLoop *UseLoop = MLI->getLoopFor(BB: UseMBB);
1456
1457 if (Cfg.PreciseUseModeling) {
1458 // Map PHI use to the end of its incoming edge block.
1459 if (auto *PhiUseEdge = getIncomingBlockIfPhiUse(MI: UseMI, MO: UseMO)) {
1460 UseMI = &PhiUseEdge->back();
1461 UseMBB = PhiUseEdge;
1462 UseLoop = MLI->getLoopFor(BB: PhiUseEdge);
1463 }
1464 }
1465
1466 enum class LoopConfig {
1467 NoCur,
1468 Same,
1469 CurContainsUse,
1470 UseContainsCur,
1471 Siblings,
1472 Unrelated
1473 };
1474 auto [LpCfg, PreHdr, CommonParent] = [&]()
1475 -> std::tuple<LoopConfig, const MachineBasicBlock *, MachineLoop *> {
1476 if (!CurLoop) {
1477 return {LoopConfig::NoCur, getOutermostPreheader(Loop: UseLoop), nullptr};
1478 }
1479 if (CurLoop->contains(L: UseLoop)) {
1480 return {CurMBB == UseMBB ? LoopConfig::Same
1481 : LoopConfig::CurContainsUse,
1482 findChildPreheader(Parent: CurLoop, Descendant: UseLoop), nullptr};
1483 }
1484
1485 if (MachineLoop *P = findCommonParent(A: UseLoop, B: CurLoop).first) {
1486 if (P != UseLoop)
1487 return {LoopConfig::Siblings, findChildPreheader(Parent: P, Descendant: UseLoop), P};
1488 return {LoopConfig::UseContainsCur, nullptr, nullptr};
1489 }
1490 return {LoopConfig::Unrelated, getOutermostPreheader(Loop: UseLoop), nullptr};
1491 }();
1492
1493 //--------------------------------------------------------------------------
1494 // Don't PromoteToPreheader
1495 //--------------------------------------------------------------------------
1496 if (!Cfg.PromoteToPreheader) {
1497 switch (LpCfg) {
1498 case LoopConfig::NoCur:
1499 case LoopConfig::Same:
1500 case LoopConfig::CurContainsUse:
1501 return {.IsInstrRelative: InstrRelative, .Distance: calcShortestDistance(FromMI: &CurMI, ToMI: UseMI)};
1502
1503 case LoopConfig::UseContainsCur: {
1504 if (isIncomingValFromBackedge(LiveReg, LiveLaneMask, CurMI: &CurMI, UseMI)) {
1505 return calcDistanceViaEnclosingBackedge(CurMI: &CurMI, CurMBB, CurLoop,
1506 UseMI, UseMBB, UseLoop);
1507 }
1508
1509 return {.IsInstrRelative: InstrInvariant, .Distance: calcDistanceThroughSubLoopToUseMI(
1510 CurMBB, CurLoop, UseMI, UseMBB, UseLoop)};
1511 }
1512 case LoopConfig::Siblings:
1513 case LoopConfig::Unrelated:
1514 return {.IsInstrRelative: InstrInvariant, .Distance: calcDistanceThroughLoopToOutsideLoopUseMI(
1515 CurMBB, CurLoop, UseMI, UseMBB, UseLoop)};
1516 }
1517 llvm_unreachable("unexpected loop configuration!");
1518 }
1519
1520 //--------------------------------------------------------------------------
1521 // PromoteToPreheader
1522 //--------------------------------------------------------------------------
1523 if (PreHdr) {
1524 UseMI = &PreHdr->back();
1525 UseMBB = PreHdr;
1526 UseLoop = CommonParent;
1527 }
1528
1529 switch (LpCfg) {
1530 case LoopConfig::NoCur:
1531 return {.IsInstrRelative: InstrRelative, .Distance: calcShortestUnweightedDistance(FromMI: &CurMI, ToMI: UseMI) -
1532 (sizeOf(MI: *UseMI) ? 0 : 1)};
1533
1534 case LoopConfig::Same:
1535 case LoopConfig::CurContainsUse:
1536 if (CurMBB == UseMBB && !instrsAreInOrder(A: &CurMI, B: UseMI))
1537 return {.IsInstrRelative: InstrRelative,
1538 .Distance: calcBackedgeDistance(CurMI: &CurMI, CurMBB, CurLoop, UseMI)};
1539
1540 return {.IsInstrRelative: InstrRelative, .Distance: calcShortestUnweightedDistance(FromMI: &CurMI, ToMI: UseMI)};
1541
1542 case LoopConfig::UseContainsCur:
1543 case LoopConfig::Siblings:
1544 return {.IsInstrRelative: InstrInvariant, .Distance: calcDistanceThroughSubLoopToUseMI(
1545 CurMBB, CurLoop, UseMI, UseMBB, UseLoop)};
1546
1547 case LoopConfig::Unrelated:
1548 return {.IsInstrRelative: InstrInvariant, .Distance: calcDistanceThroughLoopToOutsideLoopUseMI(
1549 CurMBB, CurLoop, UseMI, UseMBB, UseLoop)};
1550 }
1551 llvm_unreachable("unexpected loop configuration!");
1552 }
1553
1554 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1555 // getUses helpers (compute mode)
1556 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1557private:
1558 // Returns true if Use is reachable from MI. Handles backedges and intervening
1559 // defs.
1560 bool isUseReachablePrecise(const MachineInstr &MI,
1561 const MachineBasicBlock *MBB,
1562 const MachineOperand *UseMO,
1563 const MachineInstr *UseMI,
1564 const MachineBasicBlock *UseMBB) const {
1565
1566 // Filter out uses that are clearly unreachable
1567 if (MBB != UseMBB && !isReachable(From: MBB, To: UseMBB))
1568 return false;
1569
1570 // PHI uses are considered part of the incoming BB. Check for reachability
1571 // at the edge.
1572 if (auto *PhiUseEdge = getIncomingBlockIfPhiUse(MI: UseMI, MO: UseMO)) {
1573 if (!isReachableOrSame(From: MBB, To: PhiUseEdge))
1574 return false;
1575 }
1576
1577 // Filter out uses with an intermediate def.
1578 const MachineInstr *DefMI = MRI->getUniqueVRegDef(Reg: UseMO->getReg());
1579 const MachineBasicBlock *DefMBB = DefMI->getParent();
1580 if (MBB == UseMBB) {
1581 if (UseMI->isPHI() && MBB == DefMBB)
1582 return true;
1583
1584 if (instrsAreInOrder(A: &MI, B: UseMI))
1585 return true;
1586
1587 // A Def in the loop means that the value at MI will not survive through
1588 // to this use.
1589 MachineLoop *UseLoop = MLI->getLoopFor(BB: UseMBB);
1590 return UseLoop && !UseLoop->contains(BB: DefMBB);
1591 }
1592
1593 if (MBB == DefMBB)
1594 return instrsAreInOrder(A: DefMI, B: &MI);
1595
1596 MachineLoop *Loop = MLI->getLoopFor(BB: MBB);
1597 if (!Loop)
1598 return true;
1599
1600 MachineLoop *TopLoop = Loop->getOutermostLoop();
1601 return !TopLoop->contains(BB: DefMBB) || !isReachable(From: MBB, To: DefMBB) ||
1602 !isForwardReachable(From: UseMBB, To: MBB);
1603 }
1604
1605 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1606 // Debug/Developer Helpers
1607 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1608private:
1609 /// Goes over all MBB pairs in \p MF, calculates the shortest path between
1610 /// them.
1611 void populatePathTable() {
1612 for (const MachineBasicBlock &MBB1 : *MF) {
1613 for (const MachineBasicBlock &MBB2 : *MF) {
1614 if (&MBB1 == &MBB2)
1615 continue;
1616 getShortestPath(From: &MBB1, To: &MBB2);
1617 }
1618 }
1619 }
1620
1621 void printPaths(raw_ostream &OS) const {
1622 OS << "\n---------------- Paths --------------- {\n";
1623 for (const auto &[P, PI] : Paths) {
1624 OS << " " << printMBBReference(MBB: *P.src()) << " -> "
1625 << printMBBReference(MBB: *P.dst()) << ": ";
1626 PI.print(OS);
1627 OS << '\n';
1628 }
1629 OS << "}\n";
1630 }
1631
1632 LLVM_DUMP_METHOD void dumpPaths() const { printPaths(OS&: dbgs()); }
1633
1634 // Legacy alias kept for existing call sites.
1635 void dumpShortestPaths() const {
1636 for (const auto &P : Paths) {
1637 const MachineBasicBlock *From = P.first.src();
1638 const MachineBasicBlock *To = P.first.dst();
1639 std::optional<NextUseDistance> Dist = P.second.ShortestDistance;
1640 dbgs() << "From: " << printMBBReference(MBB: *From)
1641 << "-> To:" << printMBBReference(MBB: *To) << " = "
1642 << Dist.value_or(u: -1).fmt() << "\n";
1643 }
1644 }
1645
1646 void printInterBlockDistances(raw_ostream &OS) const {
1647 using MBBPair = std::pair<unsigned, unsigned>;
1648 using Elem = std::pair<NextUseDistance, MBBPair>;
1649 std::vector<Elem> SortedDistances;
1650
1651 for (const auto &[FromNum, Dsts] : InterBlockDistances) {
1652 for (const auto &[ToNum, Dist] : Dsts) {
1653 SortedDistances.emplace_back(args: Dist.Weighted, args: MBBPair(FromNum, ToNum));
1654 }
1655 }
1656 llvm::sort(C&: SortedDistances, Comp: [](const auto &A, const auto &B) {
1657 if (A.first != B.first)
1658 return A.first < B.first;
1659
1660 if (A.second.first != B.second.first)
1661 return A.second.first < B.second.first;
1662
1663 return A.second.second < B.second.second;
1664 });
1665
1666 OS << "\n--------- InterBlockDistances -------- {\n";
1667 for (const Elem &E : SortedDistances) {
1668
1669 OS << " bb." << E.second.first << " -> bb." << E.second.second << ": ";
1670 E.first.print(OS);
1671 OS << '\n';
1672 }
1673 OS << "}\n";
1674 }
1675
1676 LLVM_DUMP_METHOD void dumpInterBlockDistances() const {
1677 printInterBlockDistances(OS&: dbgs());
1678 }
1679
1680 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1681 // LiveRegUse Caching - A cache of the distances for the last
1682 // MachineInstruction. When getting the distances for a MachineInstruction, if
1683 // it is the same basic block as the cached instruction, we can generally use
1684 // an offset from the cached values to compute the distances. There are some
1685 // exceptions - see 'cacheLiveRegUse'.
1686 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1687private:
1688 struct LiveRegToUseMapElem {
1689 LiveRegUse Use;
1690 bool MIDependent;
1691 LiveRegToUseMapElem() : Use(), MIDependent(false) {}
1692 LiveRegToUseMapElem(LiveRegUse U, bool MIDep)
1693 : Use(U), MIDependent(MIDep) {}
1694
1695 void print(raw_ostream &OS) const {
1696 Use.print(OS);
1697 OS << (MIDependent ? " [mi-dep]" : " [mi-indep]");
1698 }
1699
1700 LLVM_DUMP_METHOD void dump() const {
1701 print(OS&: dbgs());
1702 dbgs() << '\n';
1703 }
1704 };
1705
1706 // Using std::map because LaneBitmask does not work out-of-the-box as a
1707 // DenseMap key and I did not see a performance benefit over std::map.
1708 using LaneBitmaskToUseMap = std::map<LaneBitmask, LiveRegToUseMapElem>;
1709 using LiveRegToUseMap = DenseMap<Register, LaneBitmaskToUseMap>;
1710
1711 const MachineInstr *CachedDistancesMI = nullptr;
1712 LiveRegToUseMap CachedDistances;
1713 LiveRegToUseMap PendingCachedDistances;
1714 unsigned DistanceCacheHits = 0;
1715 unsigned DistanceCacheMisses = 0;
1716
1717 void resetDistanceCache() {
1718 CachedDistancesMI = nullptr;
1719 CachedDistances.clear();
1720 DistanceCacheHits = 0;
1721 DistanceCacheMisses = 0;
1722 }
1723
1724 void maybeClearCachedLiveRegUses(const MachineInstr &MI) {
1725 if (CachedDistancesMI &&
1726 (CachedDistancesMI->getParent() != MI.getParent() ||
1727 !instrsAreInOrder(A: CachedDistancesMI, B: &MI))) {
1728 CachedDistancesMI = nullptr;
1729 CachedDistances.clear();
1730 }
1731 }
1732
1733 bool okToUseCacheElem(const LiveRegToUseMapElem &CacheElem,
1734 const MachineInstr &MI, const InstrIdTy LastDelta) {
1735 if (!CacheElem.MIDependent)
1736 return true;
1737
1738 const LiveRegUse &U = CacheElem.Use;
1739
1740 // Never okay to produce a negative distance
1741 if (U.Dist < LastDelta)
1742 return false;
1743
1744 const MachineInstr *UseMI = U.Use->getParent();
1745
1746 // Always okay if use is in another basic block or UseMI is MI
1747 if (UseMI->getParent() != MI.getParent() || UseMI == &MI)
1748 return true;
1749
1750 // If CachedDistancesMI <= Use < MI we could have a problem since we don't
1751 // know if Use is still reachable.
1752 return !instrsAreInOrder(A: CachedDistancesMI, B: UseMI) ||
1753 !instrsAreInOrder(A: UseMI, B: &MI);
1754 }
1755
1756 std::pair<const LaneBitmaskToUseMap *, const LiveRegToUseMapElem *>
1757 findCachedLiveRegUse(Register Reg, LaneBitmask LaneMask,
1758 const MachineInstr &MI, const InstrIdTy LastDelta) {
1759 if (!DistanceCacheEnabled)
1760 return {nullptr, nullptr};
1761
1762 ++DistanceCacheMisses; // Assume miss
1763 auto I = CachedDistances.find(Val: Reg);
1764 if (I == CachedDistances.end())
1765 return {nullptr, nullptr};
1766 const LaneBitmaskToUseMap &RegSlot = I->second;
1767 if (RegSlot.empty())
1768 return {nullptr, nullptr};
1769
1770 auto J = RegSlot.find(x: LaneMask);
1771 if (J == RegSlot.end())
1772 return {nullptr, nullptr};
1773
1774 const LiveRegToUseMapElem &MaskSlot = J->second;
1775 if (!okToUseCacheElem(CacheElem: MaskSlot, MI, LastDelta))
1776 return {nullptr, nullptr};
1777
1778 --DistanceCacheMisses;
1779 ++DistanceCacheHits;
1780 return {&RegSlot, &MaskSlot};
1781 }
1782
1783 void cacheLiveRegUse(const MachineInstr &MI, Register Reg, LaneBitmask Mask,
1784 LiveRegUse U, bool MIDependent) {
1785 if (!DistanceCacheEnabled)
1786 return;
1787
1788 auto I = PendingCachedDistances.try_emplace(Key: Reg).first;
1789 LaneBitmaskToUseMap &RegSlot = I->second;
1790 RegSlot.try_emplace(k: Mask, args&: U, args&: MIDependent);
1791 }
1792
1793 void updateCachedLiveRegUses(const MachineInstr &MI) {
1794 if (!DistanceCacheEnabled)
1795 return;
1796
1797 CachedDistancesMI = &MI;
1798 CachedDistances = std::move(PendingCachedDistances);
1799 PendingCachedDistances.clear();
1800 LLVM_DEBUG(dumpDistanceCache());
1801 }
1802
1803 void printDistanceCache(raw_ostream &OS) const {
1804 OS << "\n----------- Distance Cache ----------- {\n";
1805 OS << " CachedAt: ";
1806 if (CachedDistancesMI)
1807 OS << *CachedDistancesMI;
1808 else
1809 OS << "<none>\n";
1810
1811 constexpr size_t RegNameWidth = 20;
1812 for (const auto &[Reg, ByMask] : CachedDistances) {
1813 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
1814 LaneBitmask AllLanes = MRI->getMaxLaneMaskForVReg(Reg);
1815
1816 for (const auto &[Mask, Elem] : ByMask) {
1817 std::string RegName;
1818 raw_string_ostream KOS(RegName);
1819 if (Mask == AllLanes) {
1820 KOS << printReg(Reg);
1821 } else {
1822 SmallVector<unsigned> Indexes;
1823 TRI->getCoveringSubRegIndexes(RC, LaneMask: Mask, Indexes);
1824 if (Indexes.size() == 1)
1825 KOS << printReg(Reg, TRI, SubIdx: Indexes.front(), MRI);
1826 else
1827 KOS << printReg(Reg) << " mask=" << Mask.getAsInteger();
1828 }
1829 OS << " " << left_justify(Str: RegName, Width: RegNameWidth) << " : ";
1830 Elem.print(OS);
1831 OS << '\n';
1832 }
1833 }
1834 OS << " (hits=" << DistanceCacheHits << " misses=" << DistanceCacheMisses
1835 << ")\n";
1836 OS << "}\n";
1837 }
1838
1839 LLVM_DUMP_METHOD void dumpDistanceCache() const {
1840 printDistanceCache(OS&: dbgs());
1841 }
1842
1843 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1844 // Processing Live Reg Uses
1845 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1846private:
1847 // Decompose each use in 'Uses' by sub-reg and store the nearest one in
1848 // 'UseByMask'. Ignores subregs matching 'LiveRegLaneMask' - these are handled
1849 // as registers, not sub-regs.
1850 DenseMap<const TargetRegisterClass *, SmallVector<unsigned>>
1851 SubRegIndexesForRegClass;
1852 void collectSubRegUsesByMask(
1853 const SmallVectorImpl<const MachineOperand *> &Uses,
1854 const SmallVectorImpl<CacheableNextUseDistance> &Distances,
1855 LaneBitmask LiveRegLaneMask, LaneBitmaskToUseMap &UseByMask) {
1856
1857 assert(Uses.size());
1858 assert(Uses.size() == Distances.size());
1859
1860 const TargetRegisterClass *RC = MRI->getRegClass(Reg: Uses.front()->getReg());
1861 auto [SRI, Inserted] = SubRegIndexesForRegClass.try_emplace(Key: RC);
1862 if (Inserted)
1863 TRI->getCoveringSubRegIndexes(RC, LaneMask: LaneBitmask::getAll(), Indexes&: SRI->second);
1864 const SmallVector<unsigned> &RCSubRegIndexes = SRI->second;
1865
1866 unsigned OneIndex; // Backing store for 'Indexes' below when 1 index
1867 for (size_t I = 0; I < Uses.size(); ++I) {
1868 const MachineOperand *MO = Uses[I];
1869 auto [SubRegMIDep, Dist] = Distances[I];
1870 const LiveRegUse LRU{MO, Dist};
1871
1872 ArrayRef<unsigned> Indexes;
1873 if (MO->getSubReg()) {
1874 OneIndex = MO->getSubReg();
1875 Indexes = ArrayRef(OneIndex);
1876 } else {
1877 Indexes = RCSubRegIndexes;
1878 }
1879
1880 for (unsigned Idx : Indexes) {
1881 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubIdx: Idx);
1882 if (Mask.all() || Mask == LiveRegLaneMask)
1883 continue;
1884
1885 auto &[SlotU, SlotMIDep] = UseByMask[Mask];
1886 if (updateClosest(Closest&: SlotU, X: LRU))
1887 SlotMIDep = SubRegMIDep;
1888 }
1889 }
1890 }
1891
1892 // Similar to 'collectSubRegUsesByMask' above, but uses cached distances.
1893 void collectSubRegUsesByMaskFromCache(const LaneBitmaskToUseMap &CachedMap,
1894 LaneBitmask LiveRegLaneMask,
1895 const MachineInstr *MI,
1896 InstrIdTy LastDelta,
1897 LaneBitmaskToUseMap &UseByMask) {
1898
1899 for (const auto &KV : CachedMap) {
1900 LaneBitmask SubregLaneMask = KV.first;
1901 if (SubregLaneMask.all() || SubregLaneMask == LiveRegLaneMask)
1902 continue;
1903
1904 const LiveRegToUseMapElem &SubregE = KV.second;
1905 if (!okToUseCacheElem(CacheElem: SubregE, MI: *MI, LastDelta))
1906 continue;
1907
1908 const bool MIDep = SubregE.MIDependent;
1909 LiveRegUse U = SubregE.Use;
1910 if (MIDep)
1911 U.Dist -= LastDelta;
1912
1913 auto &[SlotU, SlotMIDep] = UseByMask[SubregLaneMask];
1914 if (updateClosest(Closest&: SlotU, X: U))
1915 SlotMIDep = MIDep;
1916 }
1917 }
1918
1919 // Loops through 'UseByMask' finding the furthest sub-register and updating
1920 // 'FurthestSubreg' accordingly.
1921 void updateFurthestSubReg(
1922 const MachineInstr &MI, const LiveRegUse &U,
1923 const LaneBitmaskToUseMap &UseByMask,
1924 DenseMap<const MachineOperand *, UseDistancePair> *RelevantUses,
1925 LiveRegUse &FurthestSubreg) {
1926
1927 if (UseByMask.empty()) {
1928 updateFurthest(Furthest&: FurthestSubreg, X: U);
1929 return;
1930 }
1931
1932 for (const auto &KV : UseByMask) {
1933 const LiveRegUse &SubregU = KV.second.Use;
1934 const bool SubregMIDep = KV.second.MIDependent;
1935
1936 if (RelevantUses)
1937 RelevantUses->try_emplace(Key: SubregU.Use, Args: SubregU);
1938 cacheLiveRegUse(MI, Reg: SubregU.Use->getReg(), Mask: KV.first, U: SubregU,
1939 MIDependent: SubregMIDep);
1940 updateFurthest(Furthest&: FurthestSubreg, X: SubregU);
1941 }
1942 }
1943
1944 // Used to populate 'MIDefs' to be passed to 'getNextUseDistances'.
1945 SmallSet<Register, 4> collectDefinedRegisters(const MachineInstr &MI) const {
1946 SmallSet<Register, 4> MIDefs;
1947
1948 for (const MachineOperand &MO : MI.all_defs()) {
1949 if (MO.isReg() && MO.getReg().isValid() && hasAtLeastOneUse(Reg: MO.getReg()))
1950 MIDefs.insert(V: MO.getReg());
1951 }
1952 return MIDefs;
1953 }
1954
1955 // Computes distances from 'MI' to each registers in 'LiveRegs'. Returns the
1956 // furthest register and (optionally) sub-register in 'Furthest' and
1957 // 'FurthestSubreg' respectively.
1958public:
1959 void getNextUseDistances(const GCNRPTracker::LiveRegSet &LiveRegs,
1960 const MachineInstr &MI, LiveRegUse &Furthest,
1961 LiveRegUse *FurthestSubreg = nullptr,
1962 DenseMap<const MachineOperand *, UseDistancePair>
1963 *RelevantUses = nullptr) {
1964 const SmallSet<Register, 4> MIDefs(collectDefinedRegisters(MI));
1965
1966 SmallVector<const MachineOperand *> Uses;
1967 SmallVector<CacheableNextUseDistance> Distances;
1968 LaneBitmaskToUseMap UseByMask;
1969
1970 maybeClearCachedLiveRegUses(MI);
1971 const InstrIdTy LastDelta =
1972 CachedDistancesMI ? getDistance(From: CachedDistancesMI, To: &MI) : 0;
1973
1974 for (auto &KV : LiveRegs) {
1975 const Register Reg = KV.first;
1976 const LaneBitmask LaneMask = KV.second;
1977
1978 if (MIDefs.contains(V: Reg))
1979 continue;
1980
1981 Uses.clear();
1982 UseByMask.clear();
1983
1984 LiveRegUse U;
1985 bool MIDependent = false;
1986 auto [CacheMap, CacheElem] =
1987 findCachedLiveRegUse(Reg, LaneMask, MI, LastDelta);
1988 if (CacheMap && CacheElem) {
1989 MIDependent = CacheElem->MIDependent;
1990 U = CacheElem->Use;
1991 if (MIDependent)
1992 U.Dist -= LastDelta;
1993 } else {
1994 getReachableUses(LiveReg: Reg, LaneMask, MI, Uses);
1995 if (Uses.empty())
1996 continue;
1997
1998 const MachineOperand *NextUse = nullptr;
1999 NextUseDistance Dist = getShortestDistance(
2000 LiveReg: Reg, LaneMask, FromMI: MI, Uses, ShortestUseOut: &NextUse, MIDependent: &MIDependent, Distances: &Distances);
2001 U = LiveRegUse{NextUse, Dist};
2002 }
2003
2004 if (RelevantUses)
2005 RelevantUses->try_emplace(Key: U.Use, Args&: U);
2006 cacheLiveRegUse(MI, Reg, Mask: LaneMask, U, MIDependent);
2007
2008 updateFurthest(Furthest, X: U);
2009
2010 if (!FurthestSubreg)
2011 continue;
2012
2013 if (CacheMap) {
2014 collectSubRegUsesByMaskFromCache(CachedMap: *CacheMap, LiveRegLaneMask: LaneMask, MI: &MI, LastDelta,
2015 UseByMask);
2016 } else {
2017 collectSubRegUsesByMask(Uses, Distances, LiveRegLaneMask: LaneMask, UseByMask);
2018 }
2019 updateFurthestSubReg(MI, U, UseByMask, RelevantUses, FurthestSubreg&: *FurthestSubreg);
2020 }
2021 updateCachedLiveRegUses(MI);
2022 }
2023
2024 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2025 // Helper methods for printAsJson
2026 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2027private:
2028 static format_object<unsigned> Fmt(unsigned Id) { return format(Fmt: "%u", Vals: Id); }
2029
2030public:
2031 void printVerboseInstrFields(json::OStream &J, const MachineInstr &MI) const {
2032 J.attribute(Key: "id", Contents: getInstrId(MI: &MI));
2033 J.attribute(Key: "head-len", Contents: getHeadLen(MI: &MI));
2034 J.attribute(Key: "tail-len", Contents: getTailLen(MI: &MI));
2035 }
2036
2037 void printPaths(json::OStream &J, ModuleSlotTracker &MST) const {
2038 J.attributeBegin(Key: "paths");
2039 J.arrayBegin();
2040 for (const auto &KV : Paths) {
2041 const Path &P = KV.first;
2042 const PathInfo &PI = KV.second;
2043
2044 J.objectBegin();
2045
2046 printMBBNameAttr(J, Name: "src", MBB: *P.src(), MST);
2047 printMBBNameAttr(J, Name: "dst", MBB: *P.dst(), MST);
2048
2049 if (PI.ShortestDistance.has_value()) {
2050 J.attribute(Key: "shortest-distance",
2051 Contents: PI.ShortestDistance.value().toJsonValue());
2052 } else {
2053 J.attribute(Key: "shortest-distance", Contents: nullptr);
2054 }
2055
2056 if (PI.ShortestUnweightedDistance.has_value()) {
2057 J.attribute(Key: "shortest-unweighted-distance",
2058 Contents: PI.ShortestUnweightedDistance.value().toJsonValue());
2059 } else {
2060 J.attribute(Key: "shortest-unweighted-distance", Contents: nullptr);
2061 }
2062
2063 J.attribute(Key: "edge-kind", Contents: static_cast<int>(PI.EK));
2064 J.attribute(Key: "reachable", Contents: PI.Reachable);
2065 J.attribute(Key: "forward-reachable", Contents: PI.ForwardReachable);
2066
2067 J.objectEnd();
2068 }
2069 J.arrayEnd();
2070 J.attributeEnd();
2071 }
2072
2073public:
2074 AMDGPUNextUseAnalysisImpl(const MachineFunction *, const MachineLoopInfo *);
2075 ~AMDGPUNextUseAnalysisImpl() { clearTables(); }
2076
2077 AMDGPUNextUseAnalysis::Config getConfig() const { return Cfg; }
2078 void setConfig(AMDGPUNextUseAnalysis::Config NewCfg) {
2079 Cfg = NewCfg;
2080 clearTables();
2081 initializeTables();
2082 }
2083
2084 unsigned getDistanceCacheHits() const { return DistanceCacheHits; }
2085 unsigned getDistanceCacheMisses() const { return DistanceCacheMisses; }
2086
2087 void getReachableUses(Register LiveReg, LaneBitmask LaneMask,
2088 const MachineInstr &MI,
2089 SmallVector<const MachineOperand *> &Uses) const;
2090
2091 /// \Returns the shortest next-use distance for \p LiveReg.
2092 NextUseDistance
2093 getShortestDistance(Register LiveReg, LaneBitmask LaneMask,
2094 const MachineInstr &FromMI,
2095 const SmallVector<const MachineOperand *> &Uses,
2096 const MachineOperand **ShortestUseOut, bool *MIDependent,
2097 SmallVector<CacheableNextUseDistance> *Distances) const;
2098
2099 NextUseDistance
2100 getShortestDistance(Register LiveReg, const MachineInstr &FromMI,
2101 const SmallVector<const MachineOperand *> &Uses) const {
2102 return getShortestDistance(LiveReg, LaneMask: LaneBitmask::getAll(), FromMI, Uses,
2103 ShortestUseOut: nullptr, MIDependent: nullptr, Distances: nullptr);
2104 }
2105};
2106
2107AMDGPUNextUseAnalysisImpl::AMDGPUNextUseAnalysisImpl(
2108 const MachineFunction *MF, const MachineLoopInfo *ML) {
2109
2110 this->MF = MF;
2111 this->MLI = ML;
2112
2113 const GCNSubtarget &ST = MF->getSubtarget<GCNSubtarget>();
2114 TII = ST.getInstrInfo();
2115 TRI = &TII->getRegisterInfo();
2116 MRI = &MF->getRegInfo();
2117
2118 // FIXME: Hopefully we will soon converge on a single way of calculating
2119 // next-use distance and remove these presets.
2120 if (ConfigPresetOpt == "compute")
2121 Cfg = AMDGPUNextUseAnalysis::Config::Compute();
2122 else
2123 Cfg = AMDGPUNextUseAnalysis::Config::Graphics();
2124
2125 if (ConfigCountPhisOpt.getNumOccurrences())
2126 Cfg.CountPhis = ConfigCountPhisOpt;
2127 if (ConfigForwardOnlyOpt.getNumOccurrences())
2128 Cfg.ForwardOnly = ConfigForwardOnlyOpt;
2129 if (ConfigPreciseUseModelingOpt.getNumOccurrences())
2130 Cfg.PreciseUseModeling = ConfigPreciseUseModelingOpt;
2131 if (ConfigPromoteToPreheaderOpt.getNumOccurrences())
2132 Cfg.PromoteToPreheader = ConfigPromoteToPreheaderOpt;
2133
2134 initializeTables();
2135}
2136
2137NextUseDistance AMDGPUNextUseAnalysisImpl::getShortestDistance(
2138 Register LiveReg, LaneBitmask LaneMask, const MachineInstr &CurMI,
2139 const SmallVector<const MachineOperand *> &Uses,
2140 const MachineOperand **ShortestUseOut, bool *CurMIDependentOut,
2141 SmallVector<CacheableNextUseDistance> *Distances) const {
2142
2143 assert(!LiveReg.isPhysical() && !TRI->isAGPR(*MRI, LiveReg) &&
2144 "Next-use distance is calculated for SGPRs and VGPRs");
2145 const MachineOperand *NextUse = nullptr;
2146 auto NextUseDist = NextUseDistance::unreachable();
2147 bool CurMIDependent = false;
2148
2149 if (Distances) {
2150 Distances->clear();
2151 Distances->reserve(N: Uses.size());
2152 }
2153 for (auto *UseMO : Uses) {
2154 auto [Dep, D] = calcDistanceToUse(LiveReg, LiveLaneMask: LaneMask, CurMI, UseMO);
2155
2156 if (D < NextUseDist) {
2157 NextUseDist = D;
2158 NextUse = UseMO;
2159 CurMIDependent = Dep;
2160 }
2161
2162 if (Distances)
2163 Distances->push_back(Elt: {.IsInstrRelative: Dep, .Distance: D});
2164 }
2165 if (ShortestUseOut)
2166 *ShortestUseOut = NextUse;
2167 if (CurMIDependentOut)
2168 *CurMIDependentOut = CurMIDependent;
2169
2170 assert(NextUseDist.isReachable() &&
2171 "getShortestDistance called with no reachable uses");
2172 return NextUseDist;
2173}
2174
2175void AMDGPUNextUseAnalysisImpl::getReachableUses(
2176 Register Reg, LaneBitmask LaneMask, const MachineInstr &MI,
2177 SmallVector<const MachineOperand *> &Uses) const {
2178 const bool CheckMask = LaneMask != LaneBitmask::getAll() &&
2179 LaneMask != MRI->getMaxLaneMaskForVReg(Reg);
2180 const MachineBasicBlock *MBB = MI.getParent();
2181
2182 for (const MachineOperand *UseMO : getRegisterUses(Reg)) {
2183 const MachineInstr *UseMI = UseMO->getParent();
2184 const MachineBasicBlock *UseMBB = UseMI->getParent();
2185
2186 if (CheckMask && !machineOperandCoveredBy(MO: *UseMO, LaneMask))
2187 continue;
2188
2189 bool Reachable;
2190 if (Cfg.PreciseUseModeling)
2191 Reachable = isUseReachablePrecise(MI, MBB, UseMO, UseMI, UseMBB);
2192 else if (MBB == UseMBB)
2193 Reachable = instrsAreInOrder(A: &MI, B: UseMI);
2194 else
2195 Reachable = isForwardReachable(From: MBB, To: UseMBB);
2196
2197 if (Reachable)
2198 Uses.push_back(Elt: UseMO);
2199 }
2200}
2201
2202//==============================================================================
2203// AMDGPUNextUseAnalysis
2204//==============================================================================
2205AMDGPUNextUseAnalysis::AMDGPUNextUseAnalysis(const MachineFunction *MF,
2206 const MachineLoopInfo *MLI) {
2207 Impl = std::make_unique<AMDGPUNextUseAnalysisImpl>(args&: MF, args&: MLI);
2208}
2209AMDGPUNextUseAnalysis::AMDGPUNextUseAnalysis(AMDGPUNextUseAnalysis &&Other)
2210 : Impl(std::move(Other.Impl)) {}
2211AMDGPUNextUseAnalysis::~AMDGPUNextUseAnalysis() {}
2212
2213AMDGPUNextUseAnalysis &
2214AMDGPUNextUseAnalysis::operator=(AMDGPUNextUseAnalysis &&Other) {
2215 if (this != &Other)
2216 Impl = std::move(Other.Impl);
2217 return *this;
2218}
2219
2220AMDGPUNextUseAnalysis::Config AMDGPUNextUseAnalysis::getConfig() const {
2221 return Impl->getConfig();
2222}
2223
2224void AMDGPUNextUseAnalysis::setConfig(Config Cfg) { Impl->setConfig(Cfg); }
2225
2226/// \Returns the next-use distance for \p LiveReg.
2227NextUseDistance AMDGPUNextUseAnalysis::getShortestDistance(
2228 Register LiveReg, const MachineInstr &FromMI,
2229 const SmallVector<const MachineOperand *> &Uses,
2230 const MachineOperand **ShortestUseOut,
2231 SmallVector<NextUseDistance> *DistancesOut) const {
2232
2233 SmallVector<AMDGPUNextUseAnalysisImpl::CacheableNextUseDistance> Distances;
2234 auto Dist = Impl->getShortestDistance(LiveReg, LaneMask: LaneBitmask::getAll(), CurMI: FromMI,
2235 Uses, ShortestUseOut, CurMIDependentOut: nullptr,
2236 Distances: DistancesOut ? &Distances : nullptr);
2237 if (DistancesOut) {
2238 for (auto [MIDep, D] : Distances)
2239 DistancesOut->push_back(Elt: D);
2240 }
2241 return Dist;
2242}
2243
2244void AMDGPUNextUseAnalysis::getNextUseDistances(
2245 const DenseMap<unsigned, LaneBitmask> &LiveRegs, const MachineInstr &MI,
2246 UseDistancePair &FurthestOut, UseDistancePair *FurthestSubregOut,
2247 DenseMap<const MachineOperand *, UseDistancePair> *RelevantUses) const {
2248
2249 LiveRegUse Furthest;
2250 LiveRegUse FurthestSubreg;
2251 Impl->getNextUseDistances(LiveRegs, MI, Furthest,
2252 FurthestSubreg: FurthestSubregOut ? &FurthestSubreg : nullptr,
2253 RelevantUses);
2254 FurthestOut = Furthest;
2255 if (FurthestSubregOut)
2256 *FurthestSubregOut = FurthestSubreg;
2257}
2258void AMDGPUNextUseAnalysis::getReachableUses(
2259 Register LiveReg, LaneBitmask LaneMask, const MachineInstr &MI,
2260 SmallVector<const MachineOperand *> &Uses) const {
2261 return Impl->getReachableUses(Reg: LiveReg, LaneMask, MI, Uses);
2262}
2263
2264//==============================================================================
2265// AMDGPUNextUseAnalysisLegacyPass
2266//==============================================================================
2267
2268//------------------------------------------------------------------------------
2269// Legacy Analysis Pass
2270//------------------------------------------------------------------------------
2271AMDGPUNextUseAnalysisLegacyPass::AMDGPUNextUseAnalysisLegacyPass()
2272 : MachineFunctionPass(ID) {}
2273StringRef AMDGPUNextUseAnalysisLegacyPass::getPassName() const {
2274 return "Next Use Analysis";
2275}
2276
2277bool AMDGPUNextUseAnalysisLegacyPass::runOnMachineFunction(
2278 MachineFunction &MF) {
2279 const MachineLoopInfo *MLI =
2280 &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
2281 NUA.reset(p: new AMDGPUNextUseAnalysis(&MF, MLI));
2282 return false;
2283}
2284
2285void AMDGPUNextUseAnalysisLegacyPass::getAnalysisUsage(
2286 AnalysisUsage &AU) const {
2287 AU.addRequired<MachineLoopInfoWrapperPass>();
2288 AU.setPreservesAll();
2289 MachineFunctionPass::getAnalysisUsage(AU);
2290}
2291
2292char AMDGPUNextUseAnalysisLegacyPass::ID = 0;
2293char &llvm::AMDGPUNextUseAnalysisLegacyID = AMDGPUNextUseAnalysisLegacyPass::ID;
2294
2295INITIALIZE_PASS_BEGIN(AMDGPUNextUseAnalysisLegacyPass, DEBUG_TYPE,
2296 "Next Use Analysis", false, true)
2297INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
2298INITIALIZE_PASS_END(AMDGPUNextUseAnalysisLegacyPass, DEBUG_TYPE,
2299 "Next Use Analysis", false, true)
2300
2301FunctionPass *llvm::createAMDGPUNextUseAnalysisLegacyPass() {
2302 return new AMDGPUNextUseAnalysisLegacyPass();
2303}
2304
2305//------------------------------------------------------------------------------
2306// New Pass Manager Analysis Pass
2307//------------------------------------------------------------------------------
2308AnalysisKey AMDGPUNextUseAnalysisPass::Key;
2309
2310AMDGPUNextUseAnalysisPass::Result
2311AMDGPUNextUseAnalysisPass::run(MachineFunction &MF,
2312 MachineFunctionAnalysisManager &MFAM) {
2313 const MachineLoopInfo &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
2314 return AMDGPUNextUseAnalysis(&MF, &MLI);
2315}
2316
2317//==============================================================================
2318// AMDGPUNextUseAnalysisPrinterLegacyPass
2319//==============================================================================
2320namespace {
2321void printInstrMember(json::OStream &J, ModuleSlotTracker &MST,
2322 const MachineInstr &MI,
2323 const AMDGPUNextUseAnalysisImpl &NUA) {
2324 printStringAttr(J, Name: "instr", MI, MST);
2325 if (DumpNextUseDistanceVerbose)
2326 NUA.printVerboseInstrFields(J, MI);
2327}
2328
2329void printDistances(
2330 json::OStream &J, const MachineRegisterInfo &MRI, const SIRegisterInfo &TRI,
2331 ModuleSlotTracker &MST,
2332 const DenseMap<const MachineOperand *, UseDistancePair> &Uses) {
2333 if (!DumpNextUseDistanceVerbose)
2334 return;
2335
2336 // Sorting isn't necessary for the purposes of JSON, but it reduces
2337 // FileCheck differences.
2338 SmallVector<const MachineOperand *> Keys;
2339 for (const MachineOperand *K : Uses.keys())
2340 Keys.push_back(Elt: K);
2341 llvm::sort(C&: Keys, Comp: [](const auto &A, const auto &B) {
2342 return A->getReg() < B->getReg() ||
2343 (A->getReg() == B->getReg() && A->getSubReg() < B->getSubReg());
2344 });
2345
2346 J.attributeBegin(Key: "distances");
2347 J.objectBegin();
2348
2349 for (const MachineOperand *K : Keys) {
2350 const LiveRegUse U = Uses.at(Val: K);
2351 printAttr(J, P: printReg(Reg: U.getReg(), TRI: &TRI, SubIdx: U.getSubReg(), MRI: &MRI),
2352 V: U.Dist.toJsonValue());
2353 }
2354
2355 J.objectEnd();
2356 J.attributeEnd();
2357}
2358
2359void printFurthestUse(json::OStream &J, const MachineRegisterInfo &MRI,
2360 const SIRegisterInfo &TRI, ModuleSlotTracker &MST,
2361 const LiveRegUse F, bool Subreg = false) {
2362 J.attributeBegin(Key: Subreg ? "furthest-subreg" : "furthest");
2363 J.objectBegin();
2364
2365 if (F.Use) {
2366 printStringAttr(
2367 J, Name: "register",
2368 P: printReg(Reg: F.getReg(), TRI: &TRI, SubIdx: Subreg ? F.getSubReg() : 0, MRI: &MRI));
2369
2370 if (DumpNextUseDistanceVerbose) {
2371 printStringAttr(J, Name: "use", L: [&](raw_ostream &OS) { OS << (*F.Use); });
2372 printStringAttr(J, Name: "use-mi", MI: *F.Use->getParent(), MST);
2373 }
2374 J.attribute(Key: "distance", Contents: F.Dist.toJsonValue());
2375 }
2376
2377 J.objectEnd();
2378 J.attributeEnd();
2379}
2380
2381void printDistanceFromDefToUse(json::OStream &J, const MachineFunction &MF,
2382 const AMDGPUNextUseAnalysis &NUA,
2383 const SIRegisterInfo &TRI,
2384 const MachineRegisterInfo &MRI) {
2385 auto getRegNextUseDistance = [&](Register DefReg) {
2386 const MachineInstr &DefMI = *MRI.def_instr_begin(RegNo: DefReg);
2387
2388 SmallVector<const MachineOperand *> Uses;
2389 NUA.getReachableUses(LiveReg: DefReg, LaneMask: LaneBitmask::getAll(), MI: DefMI, Uses);
2390 if (Uses.empty())
2391 return NextUseDistance::unreachable();
2392 return NUA.getShortestDistance(LiveReg: DefReg, FromMI: DefMI, Uses);
2393 };
2394
2395 J.attributeBegin(Key: "distance-from-def-to-closest-use");
2396 J.objectBegin();
2397
2398 for (const MachineBasicBlock &MBB : MF) {
2399 for (const MachineInstr &MI : MBB) {
2400 for (const MachineOperand &MO : MI.all_defs()) {
2401 Register Reg = MO.getReg();
2402 if (Reg.isPhysical())
2403 continue;
2404 NextUseDistance D = getRegNextUseDistance(Reg);
2405 printAttr(J, P: printReg(Reg, TRI: &TRI, SubIdx: 0, MRI: &MRI), V: D.toJsonValue());
2406 }
2407 }
2408 }
2409
2410 J.objectEnd();
2411 J.attributeEnd();
2412}
2413
2414void printNextUseDistancesAsJson(json::OStream &J, const MachineFunction &MF,
2415 const AMDGPUNextUseAnalysis &NUA,
2416 const AMDGPUNextUseAnalysisImpl &NUAImpl,
2417 const LiveIntervals &LIS) {
2418 using UseDistancePair = AMDGPUNextUseAnalysis::UseDistancePair;
2419 const Function &F = MF.getFunction();
2420 const Module *M = F.getParent();
2421
2422 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
2423 const SIInstrInfo *TII = ST.getInstrInfo();
2424 const SIRegisterInfo &TRI = TII->getRegisterInfo();
2425 const MachineRegisterInfo &MRI = MF.getRegInfo();
2426
2427 // We don't actually care about register pressure here - just using
2428 // GCNDownwardRPTracker as a convenient way of getting the set of live
2429 // registers at a given instruction.
2430 GCNDownwardRPTracker RPTracker(LIS);
2431 ModuleSlotTracker MST(M);
2432 MST.incorporateFunction(F);
2433
2434 DenseMap<const MachineOperand *, UseDistancePair> RelevantUses;
2435
2436 J.attributeBegin(Key: "furthest-distances");
2437 J.objectBegin();
2438
2439 for (const MachineBasicBlock &MBB : MF) {
2440 std::string BBName;
2441 raw_string_ostream BBOS(BBName);
2442 MBB.printName(os&: BBOS, printNameFlags: MachineBasicBlock::PrintNameIr, moduleSlotTracker: &MST);
2443
2444 J.attributeBegin(Key: BBOS.str());
2445 J.arrayBegin();
2446
2447 const MachineInstr *PrevMI = nullptr;
2448 for (const MachineInstr &MI : MBB) {
2449 // Update register pressure tracker
2450 if (!PrevMI || PrevMI->getOpcode() == AMDGPU::PHI)
2451 RPTracker.reset(MI, End: MBB.end());
2452 RPTracker.advance();
2453
2454 UseDistancePair Furthest;
2455 UseDistancePair FurthestSubreg;
2456 RelevantUses.clear();
2457 NUA.getNextUseDistances(LiveRegs: RPTracker.getLiveRegs(), MI, FurthestOut&: Furthest,
2458 FurthestSubregOut: &FurthestSubreg, RelevantUses: &RelevantUses);
2459
2460 J.objectBegin();
2461 printInstrMember(J, MST, MI, NUA: NUAImpl);
2462 printDistances(J, MRI, TRI, MST, Uses: RelevantUses);
2463 printFurthestUse(J, MRI, TRI, MST, F: Furthest);
2464 printFurthestUse(J, MRI, TRI, MST, F: FurthestSubreg, /*Subreg*/ true);
2465 J.objectEnd();
2466
2467 PrevMI = &MI;
2468 }
2469
2470 J.arrayEnd();
2471 J.attributeEnd();
2472 }
2473
2474 J.objectEnd();
2475 J.attributeEnd();
2476
2477 if (DumpNextUseDistanceVerbose || DumpNextUseDistanceDefToUse)
2478 printDistanceFromDefToUse(J, MF, NUA, TRI, MRI);
2479
2480 if (DumpNextUseDistanceVerbose)
2481 NUAImpl.printPaths(J, MST);
2482
2483 if (DistanceCacheEnabled) {
2484 J.attributeBegin(Key: "metrics");
2485 J.objectBegin();
2486 {
2487 J.attributeBegin(Key: "distance-cache");
2488 J.objectBegin();
2489 {
2490 J.attribute(Key: "hits", Contents: NUAImpl.getDistanceCacheHits());
2491 J.attribute(Key: "misses", Contents: NUAImpl.getDistanceCacheMisses());
2492 }
2493 J.objectEnd();
2494 J.attributeEnd(); // distance-cache
2495 }
2496 J.objectEnd();
2497 J.attributeEnd(); // metrics
2498 }
2499}
2500
2501void printAsJson(raw_ostream &FallbackOS, TimerGroup &JsonTimerGroup,
2502 Timer &JsonTimer, const MachineFunction &MF,
2503 const AMDGPUNextUseAnalysis &NUA,
2504 const AMDGPUNextUseAnalysisImpl &NUAImpl,
2505 const LiveIntervals &LIS) {
2506 std::string FN = DumpNextUseDistanceAsJson;
2507
2508 auto dump = [&](raw_ostream &OS) {
2509 json::OStream J(OS, 2);
2510 J.objectBegin();
2511
2512 J.attributeBegin(Key: "next-use-analysis");
2513 J.objectBegin();
2514 printNextUseDistancesAsJson(J, MF, NUA, NUAImpl, LIS);
2515 J.objectEnd();
2516 J.attributeEnd();
2517
2518 JsonTimer.stopTimer();
2519 JsonTimerGroup.printJSONValues(OS, delim: ",\n");
2520
2521 J.objectEnd();
2522 };
2523
2524 if (!DumpNextUseDistanceAsJson.getNumOccurrences()) {
2525 dump(FallbackOS);
2526 } else if (FN.empty() || FN == "-") {
2527 dump(outs());
2528 } else {
2529 std::error_code EC;
2530 ToolOutputFile OutF(FN, EC, sys::fs::OF_None);
2531 dump(OutF.os());
2532 OutF.keep();
2533 }
2534}
2535} // namespace
2536
2537//------------------------------------------------------------------------------
2538// Legacy Printer Pass
2539//------------------------------------------------------------------------------
2540AMDGPUNextUseAnalysisPrinterLegacyPass::AMDGPUNextUseAnalysisPrinterLegacyPass()
2541 : MachineFunctionPass(ID) {}
2542
2543StringRef AMDGPUNextUseAnalysisPrinterLegacyPass::getPassName() const {
2544 return "AMDGPU Next Use Analysis Printer";
2545}
2546
2547bool AMDGPUNextUseAnalysisPrinterLegacyPass::runOnMachineFunction(
2548 MachineFunction &MF) {
2549 TimerGroup JsonTimerGroup("amdgpu-next-use-analysis-json",
2550 "AMDGPU Next Use Analysis JSON Printer", false);
2551 Timer JsonTimer("json", "Total time spent generating json", JsonTimerGroup);
2552 JsonTimer.startTimer();
2553
2554 const LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
2555 const AMDGPUNextUseAnalysis &NUA =
2556 getAnalysis<AMDGPUNextUseAnalysisLegacyPass>().getNextUseAnalysis();
2557
2558 printAsJson(FallbackOS&: errs(), JsonTimerGroup, JsonTimer, MF, NUA, NUAImpl: *NUA.Impl, LIS);
2559
2560 return false;
2561}
2562
2563void AMDGPUNextUseAnalysisPrinterLegacyPass::getAnalysisUsage(
2564 AnalysisUsage &AU) const {
2565 AU.addRequired<MachineLoopInfoWrapperPass>();
2566 AU.addRequired<LiveIntervalsWrapperPass>();
2567 AU.addRequired<AMDGPUNextUseAnalysisLegacyPass>();
2568 AU.setPreservesAll();
2569 MachineFunctionPass::getAnalysisUsage(AU);
2570}
2571
2572char AMDGPUNextUseAnalysisPrinterLegacyPass::ID = 0;
2573char &AMDGPUNextUseAnalysisPrinterLegacyID =
2574 AMDGPUNextUseAnalysisPrinterLegacyPass::ID;
2575
2576INITIALIZE_PASS_BEGIN(AMDGPUNextUseAnalysisPrinterLegacyPass,
2577 "amdgpu-next-use-printer",
2578 "AMDGPU Next Use Analysis Printer", false, false)
2579
2580INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
2581INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
2582
2583INITIALIZE_PASS_END(AMDGPUNextUseAnalysisPrinterLegacyPass,
2584 "amdgpu-next-use-printer",
2585 "AMDGPU Next Use Analysis Printer", false, false)
2586
2587FunctionPass *llvm::createAMDGPUNextUseAnalysisPrinterLegacyPass() {
2588 return new AMDGPUNextUseAnalysisPrinterLegacyPass();
2589}
2590
2591//------------------------------------------------------------------------------
2592// New Pass Manager Printer Pass
2593//------------------------------------------------------------------------------
2594PreservedAnalyses
2595AMDGPUNextUseAnalysisPrinterPass::run(MachineFunction &MF,
2596 MachineFunctionAnalysisManager &MFAM) {
2597
2598 TimerGroup JsonTimerGroup("amdgpu-next-use-analysis-json",
2599 "AMDGPU Next Use Analysis JSON Printer", false);
2600 Timer JsonTimer("json", "Total time spent generating json", JsonTimerGroup);
2601 JsonTimer.startTimer();
2602
2603 const LiveIntervals &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
2604 const AMDGPUNextUseAnalysis &NUA =
2605 MFAM.getResult<AMDGPUNextUseAnalysisPass>(IR&: MF);
2606
2607 printAsJson(FallbackOS&: OS, JsonTimerGroup, JsonTimer, MF, NUA, NUAImpl: *NUA.Impl, LIS);
2608
2609 return PreservedAnalyses::all();
2610}
2611