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