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