1 //===-- GCNNSAReassign.cpp - Reassign registers in NSA unstructions -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// \brief Try to reassign registers on GFX10+ from non-sequential to sequential
11 /// in NSA image instructions. Later SIShrinkInstructions pass will relace NSA
12 /// with sequential versions where possible.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #include "AMDGPU.h"
17 #include "GCNSubtarget.h"
18 #include "SIMachineFunctionInfo.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/CodeGen/LiveIntervals.h"
21 #include "llvm/CodeGen/LiveRegMatrix.h"
22 #include "llvm/CodeGen/MachineFunctionPass.h"
23 #include "llvm/InitializePasses.h"
24 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "amdgpu-nsa-reassign"
28 
29 STATISTIC(NumNSAInstructions,
30           "Number of NSA instructions with non-sequential address found");
31 STATISTIC(NumNSAConverted,
32           "Number of NSA instructions changed to sequential");
33 
34 namespace {
35 
36 class GCNNSAReassign : public MachineFunctionPass {
37 public:
38   static char ID;
39 
40   GCNNSAReassign() : MachineFunctionPass(ID) {
41     initializeGCNNSAReassignPass(*PassRegistry::getPassRegistry());
42   }
43 
44   bool runOnMachineFunction(MachineFunction &MF) override;
45 
46   StringRef getPassName() const override { return "GCN NSA Reassign"; }
47 
48   void getAnalysisUsage(AnalysisUsage &AU) const override {
49     AU.addRequired<LiveIntervals>();
50     AU.addRequired<VirtRegMap>();
51     AU.addRequired<LiveRegMatrix>();
52     AU.setPreservesAll();
53     MachineFunctionPass::getAnalysisUsage(AU);
54   }
55 
56 private:
57   typedef enum {
58     NOT_NSA,        // Not an NSA instruction
59     FIXED,          // NSA which we cannot modify
60     NON_CONTIGUOUS, // NSA with non-sequential address which we can try
61                     // to optimize.
62     CONTIGUOUS      // NSA with all sequential address registers
63   } NSA_Status;
64 
65   const GCNSubtarget *ST;
66 
67   const MachineRegisterInfo *MRI;
68 
69   const SIRegisterInfo *TRI;
70 
71   VirtRegMap *VRM;
72 
73   LiveRegMatrix *LRM;
74 
75   LiveIntervals *LIS;
76 
77   unsigned MaxNumVGPRs;
78 
79   const MCPhysReg *CSRegs;
80 
81   NSA_Status CheckNSA(const MachineInstr &MI, bool Fast = false) const;
82 
83   bool tryAssignRegisters(SmallVectorImpl<LiveInterval *> &Intervals,
84                           unsigned StartReg) const;
85 
86   bool canAssign(unsigned StartReg, unsigned NumRegs) const;
87 
88   bool scavengeRegs(SmallVectorImpl<LiveInterval *> &Intervals) const;
89 };
90 
91 } // End anonymous namespace.
92 
93 INITIALIZE_PASS_BEGIN(GCNNSAReassign, DEBUG_TYPE, "GCN NSA Reassign",
94                       false, false)
95 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
96 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
97 INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
98 INITIALIZE_PASS_END(GCNNSAReassign, DEBUG_TYPE, "GCN NSA Reassign",
99                     false, false)
100 
101 
102 char GCNNSAReassign::ID = 0;
103 
104 char &llvm::GCNNSAReassignID = GCNNSAReassign::ID;
105 
106 bool
107 GCNNSAReassign::tryAssignRegisters(SmallVectorImpl<LiveInterval *> &Intervals,
108                                    unsigned StartReg) const {
109   unsigned NumRegs = Intervals.size();
110 
111   for (unsigned N = 0; N < NumRegs; ++N)
112     if (VRM->hasPhys(Intervals[N]->reg()))
113       LRM->unassign(*Intervals[N]);
114 
115   for (unsigned N = 0; N < NumRegs; ++N)
116     if (LRM->checkInterference(*Intervals[N], MCRegister::from(StartReg + N)))
117       return false;
118 
119   for (unsigned N = 0; N < NumRegs; ++N)
120     LRM->assign(*Intervals[N], MCRegister::from(StartReg + N));
121 
122   return true;
123 }
124 
125 bool GCNNSAReassign::canAssign(unsigned StartReg, unsigned NumRegs) const {
126   for (unsigned N = 0; N < NumRegs; ++N) {
127     unsigned Reg = StartReg + N;
128     if (!MRI->isAllocatable(Reg))
129       return false;
130 
131     for (unsigned I = 0; CSRegs[I]; ++I)
132       if (TRI->isSubRegisterEq(Reg, CSRegs[I]) &&
133           !LRM->isPhysRegUsed(CSRegs[I]))
134       return false;
135   }
136 
137   return true;
138 }
139 
140 bool
141 GCNNSAReassign::scavengeRegs(SmallVectorImpl<LiveInterval *> &Intervals) const {
142   unsigned NumRegs = Intervals.size();
143 
144   if (NumRegs > MaxNumVGPRs)
145     return false;
146   unsigned MaxReg = MaxNumVGPRs - NumRegs + AMDGPU::VGPR0;
147 
148   for (unsigned Reg = AMDGPU::VGPR0; Reg <= MaxReg; ++Reg) {
149     if (!canAssign(Reg, NumRegs))
150       continue;
151 
152     if (tryAssignRegisters(Intervals, Reg))
153       return true;
154   }
155 
156   return false;
157 }
158 
159 GCNNSAReassign::NSA_Status
160 GCNNSAReassign::CheckNSA(const MachineInstr &MI, bool Fast) const {
161   const AMDGPU::MIMGInfo *Info = AMDGPU::getMIMGInfo(MI.getOpcode());
162   if (!Info || Info->MIMGEncoding != AMDGPU::MIMGEncGfx10NSA)
163     return NSA_Status::NOT_NSA;
164 
165   int VAddr0Idx =
166     AMDGPU::getNamedOperandIdx(MI.getOpcode(), AMDGPU::OpName::vaddr0);
167 
168   unsigned VgprBase = 0;
169   bool NSA = false;
170   for (unsigned I = 0; I < Info->VAddrDwords; ++I) {
171     const MachineOperand &Op = MI.getOperand(VAddr0Idx + I);
172     Register Reg = Op.getReg();
173     if (Reg.isPhysical() || !VRM->isAssignedReg(Reg))
174       return NSA_Status::FIXED;
175 
176     Register PhysReg = VRM->getPhys(Reg);
177 
178     if (!Fast) {
179       if (!PhysReg)
180         return NSA_Status::FIXED;
181 
182       // Bail if address is not a VGPR32. That should be possible to extend the
183       // optimization to work with subregs of a wider register tuples, but the
184       // logic to find free registers will be much more complicated with much
185       // less chances for success. That seems reasonable to assume that in most
186       // cases a tuple is used because a vector variable contains different
187       // parts of an address and it is either already consequitive or cannot
188       // be reassigned if not. If needed it is better to rely on register
189       // coalescer to process such address tuples.
190       if (MRI->getRegClass(Reg) != &AMDGPU::VGPR_32RegClass || Op.getSubReg())
191         return NSA_Status::FIXED;
192 
193       const MachineInstr *Def = MRI->getUniqueVRegDef(Reg);
194 
195       if (Def && Def->isCopy() && Def->getOperand(1).getReg() == PhysReg)
196         return NSA_Status::FIXED;
197 
198       for (auto U : MRI->use_nodbg_operands(Reg)) {
199         if (U.isImplicit())
200           return NSA_Status::FIXED;
201         const MachineInstr *UseInst = U.getParent();
202         if (UseInst->isCopy() && UseInst->getOperand(0).getReg() == PhysReg)
203           return NSA_Status::FIXED;
204       }
205 
206       if (!LIS->hasInterval(Reg))
207         return NSA_Status::FIXED;
208     }
209 
210     if (I == 0)
211       VgprBase = PhysReg;
212     else if (VgprBase + I != PhysReg)
213       NSA = true;
214   }
215 
216   return NSA ? NSA_Status::NON_CONTIGUOUS : NSA_Status::CONTIGUOUS;
217 }
218 
219 bool GCNNSAReassign::runOnMachineFunction(MachineFunction &MF) {
220   ST = &MF.getSubtarget<GCNSubtarget>();
221   if (ST->getGeneration() < GCNSubtarget::GFX10)
222     return false;
223 
224   MRI = &MF.getRegInfo();
225   TRI = ST->getRegisterInfo();
226   VRM = &getAnalysis<VirtRegMap>();
227   LRM = &getAnalysis<LiveRegMatrix>();
228   LIS = &getAnalysis<LiveIntervals>();
229 
230   const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
231   MaxNumVGPRs = ST->getMaxNumVGPRs(MF);
232   MaxNumVGPRs = std::min(ST->getMaxNumVGPRs(MFI->getOccupancy()), MaxNumVGPRs);
233   CSRegs = MRI->getCalleeSavedRegs();
234 
235   using Candidate = std::pair<const MachineInstr*, bool>;
236   SmallVector<Candidate, 32> Candidates;
237   for (const MachineBasicBlock &MBB : MF) {
238     for (const MachineInstr &MI : MBB) {
239       switch (CheckNSA(MI)) {
240       default:
241         continue;
242       case NSA_Status::CONTIGUOUS:
243         Candidates.push_back(std::make_pair(&MI, true));
244         break;
245       case NSA_Status::NON_CONTIGUOUS:
246         Candidates.push_back(std::make_pair(&MI, false));
247         ++NumNSAInstructions;
248         break;
249       }
250     }
251   }
252 
253   bool Changed = false;
254   for (auto &C : Candidates) {
255     if (C.second)
256       continue;
257 
258     const MachineInstr *MI = C.first;
259     if (CheckNSA(*MI, true) == NSA_Status::CONTIGUOUS) {
260       // Already happen to be fixed.
261       C.second = true;
262       ++NumNSAConverted;
263       continue;
264     }
265 
266     const AMDGPU::MIMGInfo *Info = AMDGPU::getMIMGInfo(MI->getOpcode());
267     int VAddr0Idx =
268       AMDGPU::getNamedOperandIdx(MI->getOpcode(), AMDGPU::OpName::vaddr0);
269 
270     SmallVector<LiveInterval *, 16> Intervals;
271     SmallVector<MCRegister, 16> OrigRegs;
272     SlotIndex MinInd, MaxInd;
273     for (unsigned I = 0; I < Info->VAddrDwords; ++I) {
274       const MachineOperand &Op = MI->getOperand(VAddr0Idx + I);
275       Register Reg = Op.getReg();
276       LiveInterval *LI = &LIS->getInterval(Reg);
277       if (llvm::is_contained(Intervals, LI)) {
278         // Same register used, unable to make sequential
279         Intervals.clear();
280         break;
281       }
282       Intervals.push_back(LI);
283       OrigRegs.push_back(VRM->getPhys(Reg));
284       if (LI->empty()) {
285         // The address input is undef, so it doesn't contribute to the relevant
286         // range. Seed a reasonable index range if required.
287         if (I == 0)
288           MinInd = MaxInd = LIS->getInstructionIndex(*MI);
289         continue;
290       }
291       MinInd = I != 0 ? std::min(MinInd, LI->beginIndex()) : LI->beginIndex();
292       MaxInd = I != 0 ? std::max(MaxInd, LI->endIndex()) : LI->endIndex();
293     }
294 
295     if (Intervals.empty())
296       continue;
297 
298     LLVM_DEBUG(dbgs() << "Attempting to reassign NSA: " << *MI
299                       << "\tOriginal allocation:\t";
300                for (auto *LI
301                     : Intervals) dbgs()
302                << " " << llvm::printReg((VRM->getPhys(LI->reg())), TRI);
303                dbgs() << '\n');
304 
305     bool Success = scavengeRegs(Intervals);
306     if (!Success) {
307       LLVM_DEBUG(dbgs() << "\tCannot reallocate.\n");
308       if (VRM->hasPhys(Intervals.back()->reg())) // Did not change allocation.
309         continue;
310     } else {
311       // Check we did not make it worse for other instructions.
312       auto I = std::lower_bound(Candidates.begin(), &C, MinInd,
313                                 [this](const Candidate &C, SlotIndex I) {
314                                   return LIS->getInstructionIndex(*C.first) < I;
315                                 });
316       for (auto E = Candidates.end(); Success && I != E &&
317               LIS->getInstructionIndex(*I->first) < MaxInd; ++I) {
318         if (I->second && CheckNSA(*I->first, true) < NSA_Status::CONTIGUOUS) {
319           Success = false;
320           LLVM_DEBUG(dbgs() << "\tNSA conversion conflict with " << *I->first);
321         }
322       }
323     }
324 
325     if (!Success) {
326       for (unsigned I = 0; I < Info->VAddrDwords; ++I)
327         if (VRM->hasPhys(Intervals[I]->reg()))
328           LRM->unassign(*Intervals[I]);
329 
330       for (unsigned I = 0; I < Info->VAddrDwords; ++I)
331         LRM->assign(*Intervals[I], OrigRegs[I]);
332 
333       continue;
334     }
335 
336     C.second = true;
337     ++NumNSAConverted;
338     LLVM_DEBUG(
339         dbgs() << "\tNew allocation:\t\t ["
340                << llvm::printReg((VRM->getPhys(Intervals.front()->reg())), TRI)
341                << " : "
342                << llvm::printReg((VRM->getPhys(Intervals.back()->reg())), TRI)
343                << "]\n");
344     Changed = true;
345   }
346 
347   return Changed;
348 }
349