1 //===-- SILoadStoreOptimizer.cpp ------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass tries to fuse DS instructions with close by immediate offsets.
11 // This will fuse operations such as
12 //  ds_read_b32 v0, v2 offset:16
13 //  ds_read_b32 v1, v2 offset:32
14 // ==>
15 //   ds_read2_b32 v[0:1], v2, offset0:4 offset1:8
16 //
17 //
18 // Future improvements:
19 //
20 // - This currently relies on the scheduler to place loads and stores next to
21 //   each other, and then only merges adjacent pairs of instructions. It would
22 //   be good to be more flexible with interleaved instructions, and possibly run
23 //   before scheduling. It currently missing stores of constants because loading
24 //   the constant into the data register is placed between the stores, although
25 //   this is arguably a scheduling problem.
26 //
27 // - Live interval recomputing seems inefficient. This currently only matches
28 //   one pair, and recomputes live intervals and moves on to the next pair. It
29 //   would be better to compute a list of all merges that need to occur
30 //
31 // - With a list of instructions to process, we can also merge more. If a
32 //   cluster of loads have offsets that are too large to fit in the 8-bit
33 //   offsets, but are close enough to fit in the 8 bits, we can add to the base
34 //   pointer and use the new reduced offsets.
35 //
36 //===----------------------------------------------------------------------===//
37 
38 #include "AMDGPU.h"
39 #include "SIInstrInfo.h"
40 #include "SIRegisterInfo.h"
41 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
42 #include "llvm/CodeGen/LiveVariables.h"
43 #include "llvm/CodeGen/MachineFunction.h"
44 #include "llvm/CodeGen/MachineFunctionPass.h"
45 #include "llvm/CodeGen/MachineInstrBuilder.h"
46 #include "llvm/CodeGen/MachineRegisterInfo.h"
47 #include "llvm/Support/Debug.h"
48 #include "llvm/Target/TargetMachine.h"
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "si-load-store-opt"
53 
54 namespace {
55 
56 class SILoadStoreOptimizer : public MachineFunctionPass {
57 private:
58   const TargetMachine *TM;
59   const SIInstrInfo *TII;
60   const SIRegisterInfo *TRI;
61   MachineRegisterInfo *MRI;
62   LiveIntervals *LIS;
63 
64 
65   static bool offsetsCanBeCombined(unsigned Offset0,
66                                    unsigned Offset1,
67                                    unsigned EltSize);
68 
69   MachineBasicBlock::iterator findMatchingDSInst(MachineBasicBlock::iterator I,
70                                                  unsigned EltSize);
71 
72   void updateRegDefsUses(unsigned SrcReg,
73                          unsigned DstReg,
74                          unsigned SubIdx);
75 
76   MachineBasicBlock::iterator mergeRead2Pair(
77     MachineBasicBlock::iterator I,
78     MachineBasicBlock::iterator Paired,
79     unsigned EltSize);
80 
81   MachineBasicBlock::iterator mergeWrite2Pair(
82     MachineBasicBlock::iterator I,
83     MachineBasicBlock::iterator Paired,
84     unsigned EltSize);
85 
86 public:
87   static char ID;
88 
SILoadStoreOptimizer()89   SILoadStoreOptimizer() :
90     MachineFunctionPass(ID),
91     TM(nullptr),
92     TII(nullptr),
93     TRI(nullptr),
94     MRI(nullptr),
95     LIS(nullptr) {
96 
97   }
98 
SILoadStoreOptimizer(const TargetMachine & TM_)99   SILoadStoreOptimizer(const TargetMachine &TM_) :
100     MachineFunctionPass(ID),
101     TM(&TM_),
102     TII(static_cast<const SIInstrInfo*>(TM->getSubtargetImpl()->getInstrInfo())) {
103     initializeSILoadStoreOptimizerPass(*PassRegistry::getPassRegistry());
104   }
105 
106   bool optimizeBlock(MachineBasicBlock &MBB);
107 
108   bool runOnMachineFunction(MachineFunction &MF) override;
109 
getPassName() const110   const char *getPassName() const override {
111     return "SI Load / Store Optimizer";
112   }
113 
getAnalysisUsage(AnalysisUsage & AU) const114   void getAnalysisUsage(AnalysisUsage &AU) const override {
115     AU.setPreservesCFG();
116     AU.addPreserved<SlotIndexes>();
117     AU.addPreserved<LiveIntervals>();
118     AU.addPreserved<LiveVariables>();
119     AU.addRequired<LiveIntervals>();
120 
121     MachineFunctionPass::getAnalysisUsage(AU);
122   }
123 };
124 
125 } // End anonymous namespace.
126 
127 INITIALIZE_PASS_BEGIN(SILoadStoreOptimizer, DEBUG_TYPE,
128                       "SI Load / Store Optimizer", false, false)
129 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
130 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
131 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
132 INITIALIZE_PASS_END(SILoadStoreOptimizer, DEBUG_TYPE,
133                     "SI Load / Store Optimizer", false, false)
134 
135 char SILoadStoreOptimizer::ID = 0;
136 
137 char &llvm::SILoadStoreOptimizerID = SILoadStoreOptimizer::ID;
138 
createSILoadStoreOptimizerPass(TargetMachine & TM)139 FunctionPass *llvm::createSILoadStoreOptimizerPass(TargetMachine &TM) {
140   return new SILoadStoreOptimizer(TM);
141 }
142 
offsetsCanBeCombined(unsigned Offset0,unsigned Offset1,unsigned Size)143 bool SILoadStoreOptimizer::offsetsCanBeCombined(unsigned Offset0,
144                                                 unsigned Offset1,
145                                                 unsigned Size) {
146   // XXX - Would the same offset be OK? Is there any reason this would happen or
147   // be useful?
148   if (Offset0 == Offset1)
149     return false;
150 
151   // This won't be valid if the offset isn't aligned.
152   if ((Offset0 % Size != 0) || (Offset1 % Size != 0))
153     return false;
154 
155   unsigned EltOffset0 = Offset0 / Size;
156   unsigned EltOffset1 = Offset1 / Size;
157 
158   // Check if the new offsets fit in the reduced 8-bit range.
159   if (isUInt<8>(EltOffset0) && isUInt<8>(EltOffset1))
160     return true;
161 
162   // If the offset in elements doesn't fit in 8-bits, we might be able to use
163   // the stride 64 versions.
164   if ((EltOffset0 % 64 != 0) || (EltOffset1 % 64) != 0)
165     return false;
166 
167   return isUInt<8>(EltOffset0 / 64) && isUInt<8>(EltOffset1 / 64);
168 }
169 
170 MachineBasicBlock::iterator
findMatchingDSInst(MachineBasicBlock::iterator I,unsigned EltSize)171 SILoadStoreOptimizer::findMatchingDSInst(MachineBasicBlock::iterator I,
172                                          unsigned EltSize){
173   MachineBasicBlock::iterator E = I->getParent()->end();
174   MachineBasicBlock::iterator MBBI = I;
175   ++MBBI;
176 
177   if (MBBI->getOpcode() != I->getOpcode())
178     return E;
179 
180   // Don't merge volatiles.
181   if (MBBI->hasOrderedMemoryRef())
182     return E;
183 
184   int AddrIdx = AMDGPU::getNamedOperandIdx(I->getOpcode(), AMDGPU::OpName::addr);
185   const MachineOperand &AddrReg0 = I->getOperand(AddrIdx);
186   const MachineOperand &AddrReg1 = MBBI->getOperand(AddrIdx);
187 
188   // Check same base pointer. Be careful of subregisters, which can occur with
189   // vectors of pointers.
190   if (AddrReg0.getReg() == AddrReg1.getReg() &&
191       AddrReg0.getSubReg() == AddrReg1.getSubReg()) {
192     int OffsetIdx = AMDGPU::getNamedOperandIdx(I->getOpcode(),
193                                                AMDGPU::OpName::offset);
194     unsigned Offset0 = I->getOperand(OffsetIdx).getImm() & 0xffff;
195     unsigned Offset1 = MBBI->getOperand(OffsetIdx).getImm() & 0xffff;
196 
197     // Check both offsets fit in the reduced range.
198     if (offsetsCanBeCombined(Offset0, Offset1, EltSize))
199       return MBBI;
200   }
201 
202   return E;
203 }
204 
updateRegDefsUses(unsigned SrcReg,unsigned DstReg,unsigned SubIdx)205 void SILoadStoreOptimizer::updateRegDefsUses(unsigned SrcReg,
206                                              unsigned DstReg,
207                                              unsigned SubIdx) {
208   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg),
209          E = MRI->reg_end(); I != E; ) {
210     MachineOperand &O = *I;
211     ++I;
212     O.substVirtReg(DstReg, SubIdx, *TRI);
213   }
214 }
215 
mergeRead2Pair(MachineBasicBlock::iterator I,MachineBasicBlock::iterator Paired,unsigned EltSize)216 MachineBasicBlock::iterator  SILoadStoreOptimizer::mergeRead2Pair(
217   MachineBasicBlock::iterator I,
218   MachineBasicBlock::iterator Paired,
219   unsigned EltSize) {
220   MachineBasicBlock *MBB = I->getParent();
221 
222   // Be careful, since the addresses could be subregisters themselves in weird
223   // cases, like vectors of pointers.
224   const MachineOperand *AddrReg = TII->getNamedOperand(*I, AMDGPU::OpName::addr);
225   const MachineOperand *M0Reg = TII->getNamedOperand(*I, AMDGPU::OpName::m0);
226 
227   unsigned DestReg0 = TII->getNamedOperand(*I, AMDGPU::OpName::vdst)->getReg();
228   unsigned DestReg1
229     = TII->getNamedOperand(*Paired, AMDGPU::OpName::vdst)->getReg();
230 
231   unsigned Offset0
232           = TII->getNamedOperand(*I, AMDGPU::OpName::offset)->getImm() & 0xffff;
233   unsigned Offset1
234     = TII->getNamedOperand(*Paired, AMDGPU::OpName::offset)->getImm() & 0xffff;
235 
236   unsigned NewOffset0 = Offset0 / EltSize;
237   unsigned NewOffset1 = Offset1 / EltSize;
238   unsigned Opc = (EltSize == 4) ? AMDGPU::DS_READ2_B32 : AMDGPU::DS_READ2_B64;
239 
240   // Prefer the st64 form if we can use it, even if we can fit the offset in the
241   // non st64 version. I'm not sure if there's any real reason to do this.
242   bool UseST64 = (NewOffset0 % 64 == 0) && (NewOffset1 % 64 == 0);
243   if (UseST64) {
244     NewOffset0 /= 64;
245     NewOffset1 /= 64;
246     Opc = (EltSize == 4) ? AMDGPU::DS_READ2ST64_B32 : AMDGPU::DS_READ2ST64_B64;
247   }
248 
249   assert((isUInt<8>(NewOffset0) && isUInt<8>(NewOffset1)) &&
250          (NewOffset0 != NewOffset1) &&
251          "Computed offset doesn't fit");
252 
253   const MCInstrDesc &Read2Desc = TII->get(Opc);
254 
255   const TargetRegisterClass *SuperRC
256     = (EltSize == 4) ? &AMDGPU::VReg_64RegClass : &AMDGPU::VReg_128RegClass;
257   unsigned DestReg = MRI->createVirtualRegister(SuperRC);
258 
259   DebugLoc DL = I->getDebugLoc();
260   MachineInstrBuilder Read2
261     = BuildMI(*MBB, I, DL, Read2Desc, DestReg)
262     .addImm(0) // gds
263     .addOperand(*AddrReg) // addr
264     .addImm(NewOffset0) // offset0
265     .addImm(NewOffset1) // offset1
266     .addOperand(*M0Reg) // M0
267     .addMemOperand(*I->memoperands_begin())
268     .addMemOperand(*Paired->memoperands_begin());
269 
270   LIS->InsertMachineInstrInMaps(Read2);
271 
272   unsigned SubRegIdx0 = (EltSize == 4) ? AMDGPU::sub0 : AMDGPU::sub0_sub1;
273   unsigned SubRegIdx1 = (EltSize == 4) ? AMDGPU::sub1 : AMDGPU::sub2_sub3;
274   updateRegDefsUses(DestReg0, DestReg, SubRegIdx0);
275   updateRegDefsUses(DestReg1, DestReg, SubRegIdx1);
276 
277   LIS->RemoveMachineInstrFromMaps(I);
278   LIS->RemoveMachineInstrFromMaps(Paired);
279   I->eraseFromParent();
280   Paired->eraseFromParent();
281 
282   LiveInterval &AddrRegLI = LIS->getInterval(AddrReg->getReg());
283   LIS->shrinkToUses(&AddrRegLI);
284 
285   LiveInterval &M0RegLI = LIS->getInterval(M0Reg->getReg());
286   LIS->shrinkToUses(&M0RegLI);
287 
288   // Currently m0 is treated as a register class with one member instead of an
289   // implicit physical register. We are using the virtual register for the first
290   // one, but we still need to update the live range of the now unused second m0
291   // virtual register to avoid verifier errors.
292   const MachineOperand *PairedM0Reg
293     = TII->getNamedOperand(*Paired, AMDGPU::OpName::m0);
294   LiveInterval &PairedM0RegLI = LIS->getInterval(PairedM0Reg->getReg());
295   LIS->shrinkToUses(&PairedM0RegLI);
296 
297   LIS->getInterval(DestReg); // Create new LI
298 
299   DEBUG(dbgs() << "Inserted read2: " << *Read2 << '\n');
300   return Read2.getInstr();
301 }
302 
mergeWrite2Pair(MachineBasicBlock::iterator I,MachineBasicBlock::iterator Paired,unsigned EltSize)303 MachineBasicBlock::iterator SILoadStoreOptimizer::mergeWrite2Pair(
304   MachineBasicBlock::iterator I,
305   MachineBasicBlock::iterator Paired,
306   unsigned EltSize) {
307   MachineBasicBlock *MBB = I->getParent();
308 
309   // Be sure to use .addOperand(), and not .addReg() with these. We want to be
310   // sure we preserve the subregister index and any register flags set on them.
311   const MachineOperand *Addr = TII->getNamedOperand(*I, AMDGPU::OpName::addr);
312   const MachineOperand *M0Reg = TII->getNamedOperand(*I, AMDGPU::OpName::m0);
313   const MachineOperand *Data0 = TII->getNamedOperand(*I, AMDGPU::OpName::data0);
314   const MachineOperand *Data1
315     = TII->getNamedOperand(*Paired, AMDGPU::OpName::data0);
316 
317 
318   unsigned Offset0
319     = TII->getNamedOperand(*I, AMDGPU::OpName::offset)->getImm() & 0xffff;
320   unsigned Offset1
321     = TII->getNamedOperand(*Paired, AMDGPU::OpName::offset)->getImm() & 0xffff;
322 
323   unsigned NewOffset0 = Offset0 / EltSize;
324   unsigned NewOffset1 = Offset1 / EltSize;
325   unsigned Opc = (EltSize == 4) ? AMDGPU::DS_WRITE2_B32 : AMDGPU::DS_WRITE2_B64;
326 
327   // Prefer the st64 form if we can use it, even if we can fit the offset in the
328   // non st64 version. I'm not sure if there's any real reason to do this.
329   bool UseST64 = (NewOffset0 % 64 == 0) && (NewOffset1 % 64 == 0);
330   if (UseST64) {
331     NewOffset0 /= 64;
332     NewOffset1 /= 64;
333     Opc = (EltSize == 4) ? AMDGPU::DS_WRITE2ST64_B32 : AMDGPU::DS_WRITE2ST64_B64;
334   }
335 
336   assert((isUInt<8>(NewOffset0) && isUInt<8>(NewOffset1)) &&
337          (NewOffset0 != NewOffset1) &&
338          "Computed offset doesn't fit");
339 
340   const MCInstrDesc &Write2Desc = TII->get(Opc);
341   DebugLoc DL = I->getDebugLoc();
342 
343   MachineInstrBuilder Write2
344     = BuildMI(*MBB, I, DL, Write2Desc)
345     .addImm(0) // gds
346     .addOperand(*Addr) // addr
347     .addOperand(*Data0) // data0
348     .addOperand(*Data1) // data1
349     .addImm(NewOffset0) // offset0
350     .addImm(NewOffset1) // offset1
351     .addOperand(*M0Reg)  // m0
352     .addMemOperand(*I->memoperands_begin())
353     .addMemOperand(*Paired->memoperands_begin());
354 
355   // XXX - How do we express subregisters here?
356   unsigned OrigRegs[] = { Data0->getReg(), Data1->getReg(), Addr->getReg(),
357                           M0Reg->getReg()};
358 
359   LIS->RemoveMachineInstrFromMaps(I);
360   LIS->RemoveMachineInstrFromMaps(Paired);
361   I->eraseFromParent();
362   Paired->eraseFromParent();
363 
364   LIS->repairIntervalsInRange(MBB, Write2, Write2, OrigRegs);
365 
366   DEBUG(dbgs() << "Inserted write2 inst: " << *Write2 << '\n');
367   return Write2.getInstr();
368 }
369 
370 // Scan through looking for adjacent LDS operations with constant offsets from
371 // the same base register. We rely on the scheduler to do the hard work of
372 // clustering nearby loads, and assume these are all adjacent.
optimizeBlock(MachineBasicBlock & MBB)373 bool SILoadStoreOptimizer::optimizeBlock(MachineBasicBlock &MBB) {
374   bool Modified = false;
375 
376   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
377     MachineInstr &MI = *I;
378 
379     // Don't combine if volatile.
380     if (MI.hasOrderedMemoryRef()) {
381       ++I;
382       continue;
383     }
384 
385     unsigned Opc = MI.getOpcode();
386     if (Opc == AMDGPU::DS_READ_B32 || Opc == AMDGPU::DS_READ_B64) {
387       unsigned Size = (Opc == AMDGPU::DS_READ_B64) ? 8 : 4;
388       MachineBasicBlock::iterator Match = findMatchingDSInst(I, Size);
389       if (Match != E) {
390         Modified = true;
391         I = mergeRead2Pair(I, Match, Size);
392       } else {
393         ++I;
394       }
395 
396       continue;
397     } else if (Opc == AMDGPU::DS_WRITE_B32 || Opc == AMDGPU::DS_WRITE_B64) {
398       unsigned Size = (Opc == AMDGPU::DS_WRITE_B64) ? 8 : 4;
399       MachineBasicBlock::iterator Match = findMatchingDSInst(I, Size);
400       if (Match != E) {
401         Modified = true;
402         I = mergeWrite2Pair(I, Match, Size);
403       } else {
404         ++I;
405       }
406 
407       continue;
408     }
409 
410     ++I;
411   }
412 
413   return Modified;
414 }
415 
runOnMachineFunction(MachineFunction & MF)416 bool SILoadStoreOptimizer::runOnMachineFunction(MachineFunction &MF) {
417   const TargetSubtargetInfo *STM = MF.getTarget().getSubtargetImpl();
418   TRI = static_cast<const SIRegisterInfo*>(STM->getRegisterInfo());
419   TII = static_cast<const SIInstrInfo*>(STM->getInstrInfo());
420   MRI = &MF.getRegInfo();
421 
422   LIS = &getAnalysis<LiveIntervals>();
423 
424   DEBUG(dbgs() << "Running SILoadStoreOptimizer\n");
425 
426   assert(!MRI->isSSA());
427 
428   bool Modified = false;
429 
430   for (MachineBasicBlock &MBB : MF)
431     Modified |= optimizeBlock(MBB);
432 
433   return Modified;
434 }
435