1 //===-- SILoadStoreOptimizer.cpp ------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
15 // ds_read2_b32 v[0:1], v2, offset0:4 offset1:8
18 // Future improvements:
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.
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.
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.
36 //===----------------------------------------------------------------------===//
39 #include "AMDGPUSubtarget.h"
40 #include "SIInstrInfo.h"
41 #include "SIRegisterInfo.h"
42 #include "Utils/AMDGPUBaseInfo.h"
43 #include "llvm/ADT/ArrayRef.h"
44 #include "llvm/ADT/SmallVector.h"
45 #include "llvm/ADT/StringRef.h"
46 #include "llvm/Analysis/AliasAnalysis.h"
47 #include "llvm/CodeGen/MachineBasicBlock.h"
48 #include "llvm/CodeGen/MachineFunction.h"
49 #include "llvm/CodeGen/MachineFunctionPass.h"
50 #include "llvm/CodeGen/MachineInstr.h"
51 #include "llvm/CodeGen/MachineInstrBuilder.h"
52 #include "llvm/CodeGen/MachineOperand.h"
53 #include "llvm/CodeGen/MachineRegisterInfo.h"
54 #include "llvm/IR/DebugLoc.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/Debug.h"
57 #include "llvm/Support/MathExtras.h"
58 #include "llvm/Support/raw_ostream.h"
59 #include "llvm/Target/TargetMachine.h"
66 #define DEBUG_TYPE "si-load-store-opt"
70 class SILoadStoreOptimizer : public MachineFunctionPass {
73 MachineBasicBlock::iterator I;
74 MachineBasicBlock::iterator Paired;
80 SmallVector<MachineInstr*, 8> InstsToMove;
84 const SIInstrInfo *TII = nullptr;
85 const SIRegisterInfo *TRI = nullptr;
86 MachineRegisterInfo *MRI = nullptr;
87 AliasAnalysis *AA = nullptr;
89 static bool offsetsCanBeCombined(CombineInfo &CI);
91 bool findMatchingDSInst(CombineInfo &CI);
93 MachineBasicBlock::iterator mergeRead2Pair(CombineInfo &CI);
95 MachineBasicBlock::iterator mergeWrite2Pair(CombineInfo &CI);
100 SILoadStoreOptimizer() : MachineFunctionPass(ID) {}
102 SILoadStoreOptimizer(const TargetMachine &TM_) : MachineFunctionPass(ID) {
103 initializeSILoadStoreOptimizerPass(*PassRegistry::getPassRegistry());
106 bool optimizeBlock(MachineBasicBlock &MBB);
108 bool runOnMachineFunction(MachineFunction &MF) override;
110 StringRef getPassName() const override { return "SI Load / Store Optimizer"; }
112 void getAnalysisUsage(AnalysisUsage &AU) const override {
113 AU.setPreservesCFG();
114 AU.addRequired<AAResultsWrapperPass>();
116 MachineFunctionPass::getAnalysisUsage(AU);
120 } // end anonymous namespace.
122 INITIALIZE_PASS_BEGIN(SILoadStoreOptimizer, DEBUG_TYPE,
123 "SI Load / Store Optimizer", false, false)
124 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
125 INITIALIZE_PASS_END(SILoadStoreOptimizer, DEBUG_TYPE,
126 "SI Load / Store Optimizer", false, false)
128 char SILoadStoreOptimizer::ID = 0;
130 char &llvm::SILoadStoreOptimizerID = SILoadStoreOptimizer::ID;
132 FunctionPass *llvm::createSILoadStoreOptimizerPass(TargetMachine &TM) {
133 return new SILoadStoreOptimizer(TM);
136 static void moveInstsAfter(MachineBasicBlock::iterator I,
137 ArrayRef<MachineInstr*> InstsToMove) {
138 MachineBasicBlock *MBB = I->getParent();
140 for (MachineInstr *MI : InstsToMove) {
141 MI->removeFromParent();
146 static void addDefsToList(const MachineInstr &MI,
147 SmallVectorImpl<const MachineOperand *> &Defs) {
148 for (const MachineOperand &Def : MI.defs()) {
149 Defs.push_back(&Def);
153 static bool memAccessesCanBeReordered(MachineBasicBlock::iterator A,
154 MachineBasicBlock::iterator B,
155 const SIInstrInfo *TII,
156 AliasAnalysis * AA) {
157 return (TII->areMemAccessesTriviallyDisjoint(*A, *B, AA) ||
158 // RAW or WAR - cannot reorder
159 // WAW - cannot reorder
160 // RAR - safe to reorder
161 !(A->mayStore() || B->mayStore()));
164 // Add MI and its defs to the lists if MI reads one of the defs that are
165 // already in the list. Returns true in that case.
167 addToListsIfDependent(MachineInstr &MI,
168 SmallVectorImpl<const MachineOperand *> &Defs,
169 SmallVectorImpl<MachineInstr*> &Insts) {
170 for (const MachineOperand *Def : Defs) {
171 bool ReadDef = MI.readsVirtualRegister(Def->getReg());
172 // If ReadDef is true, then there is a use of Def between I
173 // and the instruction that I will potentially be merged with. We
174 // will need to move this instruction after the merged instructions.
176 Insts.push_back(&MI);
177 addDefsToList(MI, Defs);
186 canMoveInstsAcrossMemOp(MachineInstr &MemOp,
187 ArrayRef<MachineInstr*> InstsToMove,
188 const SIInstrInfo *TII,
190 assert(MemOp.mayLoadOrStore());
192 for (MachineInstr *InstToMove : InstsToMove) {
193 if (!InstToMove->mayLoadOrStore())
195 if (!memAccessesCanBeReordered(MemOp, *InstToMove, TII, AA))
201 bool SILoadStoreOptimizer::offsetsCanBeCombined(CombineInfo &CI) {
202 // XXX - Would the same offset be OK? Is there any reason this would happen or
204 if (CI.Offset0 == CI.Offset1)
207 // This won't be valid if the offset isn't aligned.
208 if ((CI.Offset0 % CI.EltSize != 0) || (CI.Offset1 % CI.EltSize != 0))
211 unsigned EltOffset0 = CI.Offset0 / CI.EltSize;
212 unsigned EltOffset1 = CI.Offset1 / CI.EltSize;
216 // If the offset in elements doesn't fit in 8-bits, we might be able to use
217 // the stride 64 versions.
218 if ((EltOffset0 % 64 == 0) && (EltOffset1 % 64) == 0 &&
219 isUInt<8>(EltOffset0 / 64) && isUInt<8>(EltOffset1 / 64)) {
220 CI.Offset0 = EltOffset0 / 64;
221 CI.Offset1 = EltOffset1 / 64;
226 // Check if the new offsets fit in the reduced 8-bit range.
227 if (isUInt<8>(EltOffset0) && isUInt<8>(EltOffset1)) {
228 CI.Offset0 = EltOffset0;
229 CI.Offset1 = EltOffset1;
233 // Try to shift base address to decrease offsets.
234 unsigned OffsetDiff = std::abs((int)EltOffset1 - (int)EltOffset0);
235 CI.BaseOff = std::min(CI.Offset0, CI.Offset1);
237 if ((OffsetDiff % 64 == 0) && isUInt<8>(OffsetDiff / 64)) {
238 CI.Offset0 = (EltOffset0 - CI.BaseOff / CI.EltSize) / 64;
239 CI.Offset1 = (EltOffset1 - CI.BaseOff / CI.EltSize) / 64;
244 if (isUInt<8>(OffsetDiff)) {
245 CI.Offset0 = EltOffset0 - CI.BaseOff / CI.EltSize;
246 CI.Offset1 = EltOffset1 - CI.BaseOff / CI.EltSize;
253 bool SILoadStoreOptimizer::findMatchingDSInst(CombineInfo &CI) {
254 MachineBasicBlock::iterator E = CI.I->getParent()->end();
255 MachineBasicBlock::iterator MBBI = CI.I;
258 SmallVector<const MachineOperand *, 8> DefsToMove;
259 addDefsToList(*CI.I, DefsToMove);
261 for ( ; MBBI != E; ++MBBI) {
262 if (MBBI->getOpcode() != CI.I->getOpcode()) {
264 // This is not a matching DS instruction, but we can keep looking as
265 // long as one of these conditions are met:
266 // 1. It is safe to move I down past MBBI.
267 // 2. It is safe to move MBBI down past the instruction that I will
270 if (MBBI->hasUnmodeledSideEffects())
271 // We can't re-order this instruction with respect to other memory
272 // opeations, so we fail both conditions mentioned above.
275 if (MBBI->mayLoadOrStore() &&
276 !memAccessesCanBeReordered(*CI.I, *MBBI, TII, AA)) {
277 // We fail condition #1, but we may still be able to satisfy condition
278 // #2. Add this instruction to the move list and then we will check
279 // if condition #2 holds once we have selected the matching instruction.
280 CI.InstsToMove.push_back(&*MBBI);
281 addDefsToList(*MBBI, DefsToMove);
285 // When we match I with another DS instruction we will be moving I down
286 // to the location of the matched instruction any uses of I will need to
287 // be moved down as well.
288 addToListsIfDependent(*MBBI, DefsToMove, CI.InstsToMove);
292 // Don't merge volatiles.
293 if (MBBI->hasOrderedMemoryRef())
296 // Handle a case like
297 // DS_WRITE_B32 addr, v, idx0
298 // w = DS_READ_B32 addr, idx0
299 // DS_WRITE_B32 addr, f(w), idx1
300 // where the DS_READ_B32 ends up in InstsToMove and therefore prevents
301 // merging of the two writes.
302 if (addToListsIfDependent(*MBBI, DefsToMove, CI.InstsToMove))
305 int AddrIdx = AMDGPU::getNamedOperandIdx(CI.I->getOpcode(),
306 AMDGPU::OpName::addr);
307 const MachineOperand &AddrReg0 = CI.I->getOperand(AddrIdx);
308 const MachineOperand &AddrReg1 = MBBI->getOperand(AddrIdx);
310 // Check same base pointer. Be careful of subregisters, which can occur with
311 // vectors of pointers.
312 if (AddrReg0.getReg() == AddrReg1.getReg() &&
313 AddrReg0.getSubReg() == AddrReg1.getSubReg()) {
314 int OffsetIdx = AMDGPU::getNamedOperandIdx(CI.I->getOpcode(),
315 AMDGPU::OpName::offset);
316 CI.Offset0 = CI.I->getOperand(OffsetIdx).getImm() & 0xffff;
317 CI.Offset1 = MBBI->getOperand(OffsetIdx).getImm() & 0xffff;
320 // Check both offsets fit in the reduced range.
321 // We also need to go through the list of instructions that we plan to
322 // move and make sure they are all safe to move down past the merged
324 if (offsetsCanBeCombined(CI))
325 if (canMoveInstsAcrossMemOp(*MBBI, CI.InstsToMove, TII, AA))
329 // We've found a load/store that we couldn't merge for some reason.
330 // We could potentially keep looking, but we'd need to make sure that
331 // it was safe to move I and also all the instruction in InstsToMove
332 // down past this instruction.
333 // check if we can move I across MBBI and if we can move all I's users
334 if (!memAccessesCanBeReordered(*CI.I, *MBBI, TII, AA) ||
335 !canMoveInstsAcrossMemOp(*MBBI, CI.InstsToMove, TII, AA))
341 MachineBasicBlock::iterator SILoadStoreOptimizer::mergeRead2Pair(
343 MachineBasicBlock *MBB = CI.I->getParent();
345 // Be careful, since the addresses could be subregisters themselves in weird
346 // cases, like vectors of pointers.
347 const auto *AddrReg = TII->getNamedOperand(*CI.I, AMDGPU::OpName::addr);
349 const auto *Dest0 = TII->getNamedOperand(*CI.I, AMDGPU::OpName::vdst);
350 const auto *Dest1 = TII->getNamedOperand(*CI.Paired, AMDGPU::OpName::vdst);
352 unsigned NewOffset0 = CI.Offset0;
353 unsigned NewOffset1 = CI.Offset1;
354 unsigned Opc = (CI.EltSize == 4) ? AMDGPU::DS_READ2_B32
355 : AMDGPU::DS_READ2_B64;
358 Opc = (CI.EltSize == 4) ? AMDGPU::DS_READ2ST64_B32
359 : AMDGPU::DS_READ2ST64_B64;
361 unsigned SubRegIdx0 = (CI.EltSize == 4) ? AMDGPU::sub0 : AMDGPU::sub0_sub1;
362 unsigned SubRegIdx1 = (CI.EltSize == 4) ? AMDGPU::sub1 : AMDGPU::sub2_sub3;
364 if (NewOffset0 > NewOffset1) {
365 // Canonicalize the merged instruction so the smaller offset comes first.
366 std::swap(NewOffset0, NewOffset1);
367 std::swap(SubRegIdx0, SubRegIdx1);
370 assert((isUInt<8>(NewOffset0) && isUInt<8>(NewOffset1)) &&
371 (NewOffset0 != NewOffset1) &&
372 "Computed offset doesn't fit");
374 const MCInstrDesc &Read2Desc = TII->get(Opc);
376 const TargetRegisterClass *SuperRC
377 = (CI.EltSize == 4) ? &AMDGPU::VReg_64RegClass : &AMDGPU::VReg_128RegClass;
378 unsigned DestReg = MRI->createVirtualRegister(SuperRC);
380 DebugLoc DL = CI.I->getDebugLoc();
382 unsigned BaseReg = AddrReg->getReg();
383 unsigned BaseRegFlags = 0;
385 BaseReg = MRI->createVirtualRegister(&AMDGPU::VGPR_32RegClass);
386 BaseRegFlags = RegState::Kill;
387 BuildMI(*MBB, CI.Paired, DL, TII->get(AMDGPU::V_ADD_I32_e32), BaseReg)
389 .addReg(AddrReg->getReg());
392 MachineInstrBuilder Read2 =
393 BuildMI(*MBB, CI.Paired, DL, Read2Desc, DestReg)
394 .addReg(BaseReg, BaseRegFlags) // addr
395 .addImm(NewOffset0) // offset0
396 .addImm(NewOffset1) // offset1
398 .setMemRefs(CI.I->mergeMemRefsWith(*CI.Paired));
402 const MCInstrDesc &CopyDesc = TII->get(TargetOpcode::COPY);
404 // Copy to the old destination registers.
405 BuildMI(*MBB, CI.Paired, DL, CopyDesc)
406 .add(*Dest0) // Copy to same destination including flags and sub reg.
407 .addReg(DestReg, 0, SubRegIdx0);
408 MachineInstr *Copy1 = BuildMI(*MBB, CI.Paired, DL, CopyDesc)
410 .addReg(DestReg, RegState::Kill, SubRegIdx1);
412 moveInstsAfter(Copy1, CI.InstsToMove);
414 MachineBasicBlock::iterator Next = std::next(CI.I);
415 CI.I->eraseFromParent();
416 CI.Paired->eraseFromParent();
418 DEBUG(dbgs() << "Inserted read2: " << *Read2 << '\n');
422 MachineBasicBlock::iterator SILoadStoreOptimizer::mergeWrite2Pair(
424 MachineBasicBlock *MBB = CI.I->getParent();
426 // Be sure to use .addOperand(), and not .addReg() with these. We want to be
427 // sure we preserve the subregister index and any register flags set on them.
428 const MachineOperand *Addr = TII->getNamedOperand(*CI.I, AMDGPU::OpName::addr);
429 const MachineOperand *Data0 = TII->getNamedOperand(*CI.I, AMDGPU::OpName::data0);
430 const MachineOperand *Data1
431 = TII->getNamedOperand(*CI.Paired, AMDGPU::OpName::data0);
433 unsigned NewOffset0 = CI.Offset0;
434 unsigned NewOffset1 = CI.Offset1;
435 unsigned Opc = (CI.EltSize == 4) ? AMDGPU::DS_WRITE2_B32
436 : AMDGPU::DS_WRITE2_B64;
439 Opc = (CI.EltSize == 4) ? AMDGPU::DS_WRITE2ST64_B32
440 : AMDGPU::DS_WRITE2ST64_B64;
442 if (NewOffset0 > NewOffset1) {
443 // Canonicalize the merged instruction so the smaller offset comes first.
444 std::swap(NewOffset0, NewOffset1);
445 std::swap(Data0, Data1);
448 assert((isUInt<8>(NewOffset0) && isUInt<8>(NewOffset1)) &&
449 (NewOffset0 != NewOffset1) &&
450 "Computed offset doesn't fit");
452 const MCInstrDesc &Write2Desc = TII->get(Opc);
453 DebugLoc DL = CI.I->getDebugLoc();
455 unsigned BaseReg = Addr->getReg();
456 unsigned BaseRegFlags = 0;
458 BaseReg = MRI->createVirtualRegister(&AMDGPU::VGPR_32RegClass);
459 BaseRegFlags = RegState::Kill;
460 BuildMI(*MBB, CI.Paired, DL, TII->get(AMDGPU::V_ADD_I32_e32), BaseReg)
462 .addReg(Addr->getReg());
465 MachineInstrBuilder Write2 =
466 BuildMI(*MBB, CI.Paired, DL, Write2Desc)
467 .addReg(BaseReg, BaseRegFlags) // addr
468 .add(*Data0) // data0
469 .add(*Data1) // data1
470 .addImm(NewOffset0) // offset0
471 .addImm(NewOffset1) // offset1
473 .setMemRefs(CI.I->mergeMemRefsWith(*CI.Paired));
475 moveInstsAfter(Write2, CI.InstsToMove);
477 MachineBasicBlock::iterator Next = std::next(CI.I);
478 CI.I->eraseFromParent();
479 CI.Paired->eraseFromParent();
481 DEBUG(dbgs() << "Inserted write2 inst: " << *Write2 << '\n');
485 // Scan through looking for adjacent LDS operations with constant offsets from
486 // the same base register. We rely on the scheduler to do the hard work of
487 // clustering nearby loads, and assume these are all adjacent.
488 bool SILoadStoreOptimizer::optimizeBlock(MachineBasicBlock &MBB) {
489 bool Modified = false;
491 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
492 MachineInstr &MI = *I;
494 // Don't combine if volatile.
495 if (MI.hasOrderedMemoryRef()) {
502 unsigned Opc = MI.getOpcode();
503 if (Opc == AMDGPU::DS_READ_B32 || Opc == AMDGPU::DS_READ_B64) {
504 CI.EltSize = (Opc == AMDGPU::DS_READ_B64) ? 8 : 4;
505 if (findMatchingDSInst(CI)) {
507 I = mergeRead2Pair(CI);
513 } else if (Opc == AMDGPU::DS_WRITE_B32 || Opc == AMDGPU::DS_WRITE_B64) {
514 CI.EltSize = (Opc == AMDGPU::DS_WRITE_B64) ? 8 : 4;
515 if (findMatchingDSInst(CI)) {
517 I = mergeWrite2Pair(CI);
531 bool SILoadStoreOptimizer::runOnMachineFunction(MachineFunction &MF) {
532 if (skipFunction(*MF.getFunction()))
535 const SISubtarget &STM = MF.getSubtarget<SISubtarget>();
536 if (!STM.loadStoreOptEnabled())
539 TII = STM.getInstrInfo();
540 TRI = &TII->getRegisterInfo();
542 MRI = &MF.getRegInfo();
543 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
545 DEBUG(dbgs() << "Running SILoadStoreOptimizer\n");
547 bool Modified = false;
549 for (MachineBasicBlock &MBB : MF)
550 Modified |= optimizeBlock(MBB);