1//===-- RISCVZilsdOptimizer.cpp - RISC-V Zilsd Load/Store Optimizer ------===//
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 contains a pass that performs load/store optimizations for the
10// RISC-V Zilsd extension. It combines pairs of 32-bit load/store instructions
11// into single 64-bit LD/SD instructions when possible.
12//
13// The pass runs in two phases:
14// 1. Pre-allocation: Reschedules loads/stores to bring consecutive memory
15// accesses closer together and forms LD/SD pairs with register hints.
16// 2. Post-allocation: Fixes invalid LD/SD instructions if register allocation
17// didn't provide suitable consecutive registers.
18//
19// Note: second phase is integrated into RISCVLoadStoreOptimizer
20//
21//===----------------------------------------------------------------------===//
22
23#include "RISCV.h"
24#include "RISCVInstrInfo.h"
25#include "RISCVRegisterInfo.h"
26#include "RISCVSubtarget.h"
27#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/SmallVector.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/Analysis/AliasAnalysis.h"
31#include "llvm/CodeGen/MachineBasicBlock.h"
32#include "llvm/CodeGen/MachineDominators.h"
33#include "llvm/CodeGen/MachineFunction.h"
34#include "llvm/CodeGen/MachineFunctionPass.h"
35#include "llvm/CodeGen/MachineInstr.h"
36#include "llvm/CodeGen/MachineInstrBuilder.h"
37#include "llvm/CodeGen/MachineRegisterInfo.h"
38#include "llvm/InitializePasses.h"
39#include "llvm/Support/Debug.h"
40#include <algorithm>
41
42using namespace llvm;
43
44#define DEBUG_TYPE "riscv-zilsd-opt"
45
46STATISTIC(NumLDFormed, "Number of LD instructions formed");
47STATISTIC(NumSDFormed, "Number of SD instructions formed");
48
49namespace {
50
51//===----------------------------------------------------------------------===//
52// Pre-allocation Zilsd optimization pass
53//===----------------------------------------------------------------------===//
54class RISCVPreAllocZilsdOpt : public MachineFunctionPass {
55public:
56 static char ID;
57
58 RISCVPreAllocZilsdOpt() : MachineFunctionPass(ID) {}
59
60 bool runOnMachineFunction(MachineFunction &MF) override;
61
62 StringRef getPassName() const override {
63 return "RISC-V pre-allocation Zilsd load/store optimization";
64 }
65
66 MachineFunctionProperties getRequiredProperties() const override {
67 return MachineFunctionProperties().setIsSSA();
68 }
69
70 void getAnalysisUsage(AnalysisUsage &AU) const override {
71 AU.addRequired<AAResultsWrapperPass>();
72 AU.addRequired<MachineDominatorTreeWrapperPass>();
73 AU.setPreservesCFG();
74 MachineFunctionPass::getAnalysisUsage(AU);
75 }
76 enum class MemoryOffsetKind {
77 Imm = 0,
78 Global = 1,
79 CPI = 2,
80 BlockAddr = 3,
81 FrameIdx = 4,
82 Unknown = 5,
83 };
84 using MemOffset = std::pair<MemoryOffsetKind, int>;
85 using BaseRegInfo = std::pair<unsigned, MemoryOffsetKind>;
86
87private:
88 bool isMemoryOp(const MachineInstr &MI);
89 bool rescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
90 bool canFormLdSdPair(MachineInstr *MI0, MachineInstr *MI1);
91 bool rescheduleOps(MachineBasicBlock *MBB,
92 SmallVectorImpl<MachineInstr *> &MIs, BaseRegInfo Base,
93 bool IsLoad,
94 DenseMap<MachineInstr *, unsigned> &MI2LocMap);
95 bool isSafeToMove(MachineInstr *MI, MachineInstr *Target, bool MoveForward);
96 MemOffset getMemoryOpOffset(const MachineInstr &MI);
97
98 const RISCVSubtarget *STI;
99 const RISCVInstrInfo *TII;
100 const RISCVRegisterInfo *TRI;
101 MachineRegisterInfo *MRI;
102 AliasAnalysis *AA;
103 MachineDominatorTree *DT;
104 Align RequiredAlign;
105};
106
107} // end anonymous namespace
108
109char RISCVPreAllocZilsdOpt::ID = 0;
110
111INITIALIZE_PASS_BEGIN(RISCVPreAllocZilsdOpt, "riscv-prera-zilsd-opt",
112 "RISC-V pre-allocation Zilsd optimization", false, false)
113INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
114INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
115INITIALIZE_PASS_END(RISCVPreAllocZilsdOpt, "riscv-prera-zilsd-opt",
116 "RISC-V pre-allocation Zilsd optimization", false, false)
117
118//===----------------------------------------------------------------------===//
119// Pre-allocation pass implementation
120//===----------------------------------------------------------------------===//
121
122bool RISCVPreAllocZilsdOpt::runOnMachineFunction(MachineFunction &MF) {
123
124 STI = &MF.getSubtarget<RISCVSubtarget>();
125 if (!STI->getCLOpts().zilsd_opt || skipFunction(F: MF.getFunction()))
126 return false;
127
128 // Only run on RV32 with Zilsd extension
129 if (STI->is64Bit() || !STI->hasStdExtZilsd())
130 return false;
131
132 TII = STI->getInstrInfo();
133 TRI = STI->getRegisterInfo();
134 MRI = &MF.getRegInfo();
135 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
136 DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
137
138 // Check alignment: default is 8-byte, but allow 4-byte with tune feature
139 // If unaligned scalar memory is enabled, allow any alignment
140 RequiredAlign = STI->getZilsdAlign();
141 bool Modified = false;
142 for (auto &MBB : MF) {
143 Modified |= rescheduleLoadStoreInstrs(MBB: &MBB);
144 }
145
146 return Modified;
147}
148
149RISCVPreAllocZilsdOpt::MemOffset
150RISCVPreAllocZilsdOpt::getMemoryOpOffset(const MachineInstr &MI) {
151 switch (MI.getOpcode()) {
152 case RISCV::LW:
153 case RISCV::SW: {
154 // For LW/SW, the base is in operand 1 and offset is in operand 2
155 const MachineOperand &BaseOp = MI.getOperand(i: 1);
156 const MachineOperand &OffsetOp = MI.getOperand(i: 2);
157
158 // Handle immediate offset
159 if (OffsetOp.isImm()) {
160 if (BaseOp.isFI())
161 return std::make_pair(x: MemoryOffsetKind::FrameIdx, y: OffsetOp.getImm());
162 return std::make_pair(x: MemoryOffsetKind::Imm, y: OffsetOp.getImm());
163 }
164
165 // Handle symbolic operands with MO_LO flag (from MergeBaseOffset)
166 if (OffsetOp.getTargetFlags() & RISCVII::MO_LO) {
167 if (OffsetOp.isGlobal())
168 return std::make_pair(x: MemoryOffsetKind::Global, y: OffsetOp.getOffset());
169 if (OffsetOp.isCPI())
170 return std::make_pair(x: MemoryOffsetKind::CPI, y: OffsetOp.getOffset());
171 if (OffsetOp.isBlockAddress())
172 return std::make_pair(x: MemoryOffsetKind::BlockAddr,
173 y: OffsetOp.getOffset());
174 }
175
176 break;
177 }
178 default:
179 break;
180 }
181
182 return std::make_pair(x: MemoryOffsetKind::Unknown, y: 0);
183}
184
185bool RISCVPreAllocZilsdOpt::canFormLdSdPair(MachineInstr *MI0,
186 MachineInstr *MI1) {
187 if (!MI0->hasOneMemOperand() || !MI1->hasOneMemOperand())
188 return false;
189
190 // Get offsets and check they are consecutive
191 int Offset0 = getMemoryOpOffset(MI: *MI0).second;
192 int Offset1 = getMemoryOpOffset(MI: *MI1).second;
193
194 // Offsets must be 4 bytes apart
195 if (Offset1 - Offset0 != 4)
196 return false;
197
198 // We need to guarantee the alignment(base + offset) is legal.
199 const MachineMemOperand *MMO = *MI0->memoperands_begin();
200 if (MMO->getAlign() < RequiredAlign)
201 return false;
202
203 // Check that the two destination/source registers are different for
204 // load/store respectively.
205 if (MI0->getOperand(i: 0).getReg() == MI1->getOperand(i: 0).getReg())
206 return false;
207
208 return true;
209}
210
211bool RISCVPreAllocZilsdOpt::isSafeToMove(MachineInstr *MI, MachineInstr *Target,
212 bool MoveForward) {
213 MachineBasicBlock *MBB = MI->getParent();
214 MachineBasicBlock::iterator Start = MI->getIterator();
215 MachineBasicBlock::iterator End = Target->getIterator();
216
217 if (!MoveForward)
218 std::swap(a&: Start, b&: End);
219
220 // Increment Start to skip the current instruction
221 if (Start != MBB->end())
222 ++Start;
223
224 Register DefReg = MI->getOperand(i: 0).getReg();
225 const MachineOperand &BaseOp = MI->getOperand(i: 1);
226
227 unsigned ScanCount = 0;
228 for (auto It = Start; It != End; ++It, ++ScanCount) {
229 // Don't move across calls or terminators
230 if (It->isCall() || It->isTerminator()) {
231 LLVM_DEBUG(dbgs() << "Cannot move across call/terminator: " << *It);
232 return false;
233 }
234
235 // Don't move across instructions that modify memory barrier
236 if (It->hasUnmodeledSideEffects()) {
237 LLVM_DEBUG(dbgs() << "Cannot move across instruction with side effects: "
238 << *It);
239 return false;
240 }
241
242 // Check if the base register is modified
243 if (BaseOp.isReg() && It->modifiesRegister(Reg: BaseOp.getReg(), TRI)) {
244 LLVM_DEBUG(dbgs() << "Base register " << BaseOp.getReg()
245 << " modified by: " << *It);
246 return false;
247 }
248
249 // For loads, check if the loaded value is used
250 if (MI->mayLoad() &&
251 (It->readsRegister(Reg: DefReg, TRI) || It->modifiesRegister(Reg: DefReg, TRI))) {
252 LLVM_DEBUG(dbgs() << "Destination register " << DefReg
253 << " used by: " << *It);
254 return false;
255 }
256
257 // For stores, check if the stored register is modified
258 if (MI->mayStore() && It->modifiesRegister(Reg: DefReg, TRI)) {
259 LLVM_DEBUG(dbgs() << "Source register " << DefReg
260 << " modified by: " << *It);
261 return false;
262 }
263
264 // Check for memory operation interference
265 if (It->mayLoadOrStore() && It->mayAlias(AA, Other: *MI, /*UseTBAA*/ false)) {
266 LLVM_DEBUG(dbgs() << "Memory operation interference detected\n");
267 return false;
268 }
269 }
270
271 return true;
272}
273
274bool RISCVPreAllocZilsdOpt::rescheduleOps(
275 MachineBasicBlock *MBB, SmallVectorImpl<MachineInstr *> &MIs,
276 BaseRegInfo Base, bool IsLoad,
277 DenseMap<MachineInstr *, unsigned> &MI2LocMap) {
278 // Sort by offset, at this point it ensure base reg and MemoryOffsetKind are
279 // same, so we just need to simply sort by offset value.
280 llvm::sort(Start: MIs.begin(), End: MIs.end(), Comp: [this](MachineInstr *A, MachineInstr *B) {
281 return getMemoryOpOffset(MI: *A).second < getMemoryOpOffset(MI: *B).second;
282 });
283
284 bool Modified = false;
285
286 // Try to pair consecutive operations
287 for (size_t i = 0; i + 1 < MIs.size(); i++) {
288 MachineInstr *MI0 = MIs[i];
289 MachineInstr *MI1 = MIs[i + 1];
290
291 Register FirstReg = MI0->getOperand(i: 0).getReg();
292 Register SecondReg = MI1->getOperand(i: 0).getReg();
293 const MachineOperand &BaseOp = MI0->getOperand(i: 1);
294 const MachineOperand &OffsetOp = MI0->getOperand(i: 2);
295 assert((BaseOp.isReg() || BaseOp.isFI()) &&
296 "Base register should be register or frame index");
297
298 // At this point, MI0 and MI1 are:
299 // 1. both either LW or SW.
300 // 2. guaranteed to have same memory kind.
301 // 3. guaranteed to have same base register.
302 // 4. already be sorted by offset value.
303 // so we don't have to check these in canFormLdSdPair.
304 if (!canFormLdSdPair(MI0, MI1))
305 continue;
306
307 // Use MI2LocMap to determine which instruction appears later in program
308 // order
309 bool MI1IsLater = MI2LocMap[MI1] > MI2LocMap[MI0];
310
311 // For loads: move later instruction up (backwards) to earlier instruction
312 // For stores: move earlier instruction down (forwards) to later instruction
313 MachineInstr *MoveInstr, *TargetInstr;
314 if (IsLoad) {
315 // For loads: move the later instruction to the earlier one
316 MoveInstr = MI1IsLater ? MI1 : MI0;
317 TargetInstr = MI1IsLater ? MI0 : MI1;
318 } else {
319 // For stores: move the earlier instruction to the later one
320 MoveInstr = MI1IsLater ? MI0 : MI1;
321 TargetInstr = MI1IsLater ? MI1 : MI0;
322 }
323
324 unsigned Distance = MI1IsLater ? MI2LocMap[MI1] - MI2LocMap[MI0]
325 : MI2LocMap[MI0] - MI2LocMap[MI1];
326 if (!isSafeToMove(MI: MoveInstr, Target: TargetInstr, MoveForward: !IsLoad) ||
327 Distance > STI->getCLOpts().zilsd_max_reschedule_distance)
328 continue;
329
330 // Move the instruction to the target position
331 MachineBasicBlock::iterator InsertPos = TargetInstr->getIterator();
332 ++InsertPos;
333
334 // If we need to move an instruction, do it now
335 if (MoveInstr != TargetInstr)
336 MBB->splice(Where: InsertPos, Other: MBB, From: MoveInstr->getIterator());
337
338 // Create the paired instruction
339 MachineInstrBuilder MIB;
340 DebugLoc DL = MI0->getDebugLoc();
341
342 if (IsLoad) {
343 MIB = BuildMI(BB&: *MBB, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: RISCV::PseudoLD_RV32_OPT))
344 .addDef(RegNo: FirstReg)
345 .addDef(RegNo: SecondReg);
346 ++NumLDFormed;
347 LLVM_DEBUG(dbgs() << "Formed LD: " << *MIB << "\n");
348 } else {
349 MIB = BuildMI(BB&: *MBB, I: InsertPos, MIMD: DL, MCID: TII->get(Opcode: RISCV::PseudoSD_RV32_OPT))
350 .addReg(RegNo: FirstReg)
351 .addReg(RegNo: SecondReg);
352 ++NumSDFormed;
353 LLVM_DEBUG(dbgs() << "Formed SD: " << *MIB << "\n");
354 }
355
356 if (BaseOp.isReg())
357 MIB = MIB.addReg(RegNo: BaseOp.getReg());
358 else
359 MIB = MIB.addFrameIndex(Idx: BaseOp.getIndex());
360 MIB = MIB.add(MO: OffsetOp);
361
362 // Copy memory operands
363 MIB.cloneMergedMemRefs(OtherMIs: {MI0, MI1});
364
365 // Add register allocation hints for consecutive registers
366 // RISC-V Zilsd requires even/odd register pairs
367 // Only set hints for virtual registers (physical registers already have
368 // encoding)
369 if (FirstReg.isVirtual() && SecondReg.isVirtual()) {
370 // For virtual registers, we can't determine even/odd yet, but we can hint
371 // that they should be allocated as a consecutive pair
372 MRI->setRegAllocationHint(VReg: FirstReg, Type: RISCVRI::RegPairEven, PrefReg: SecondReg);
373 MRI->setRegAllocationHint(VReg: SecondReg, Type: RISCVRI::RegPairOdd, PrefReg: FirstReg);
374 }
375
376 // Remove the original instructions
377 MI0->eraseFromParent();
378 MI1->eraseFromParent();
379
380 Modified = true;
381
382 // Skip the next instruction since we've already processed it
383 i++;
384 }
385
386 return Modified;
387}
388
389bool RISCVPreAllocZilsdOpt::isMemoryOp(const MachineInstr &MI) {
390 unsigned Opcode = MI.getOpcode();
391 if (Opcode != RISCV::LW && Opcode != RISCV::SW)
392 return false;
393
394 if (!MI.getOperand(i: 1).isReg() && !MI.getOperand(i: 1).isFI())
395 return false;
396
397 // When no memory operands are present, conservatively assume unaligned,
398 // volatile, unfoldable.
399 if (!MI.hasOneMemOperand())
400 return false;
401
402 const MachineMemOperand *MMO = *MI.memoperands_begin();
403
404 if (MMO->isVolatile() || MMO->isAtomic())
405 return false;
406
407 // sw <undef> could probably be eliminated entirely, but for now we just want
408 // to avoid making a mess of it.
409 if (MI.getOperand(i: 0).isReg() && MI.getOperand(i: 0).isUndef())
410 return false;
411
412 // Likewise don't mess with references to undefined addresses.
413 if (MI.getOperand(i: 1).isReg() && MI.getOperand(i: 1).isUndef())
414 return false;
415
416 return true;
417}
418
419bool RISCVPreAllocZilsdOpt::rescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
420 bool Modified = false;
421
422 // Process the basic block in windows delimited by calls, terminators,
423 // or instructions with duplicate base+offset pairs
424 MachineBasicBlock::iterator MBBI = MBB->begin();
425 MachineBasicBlock::iterator E = MBB->end();
426
427 while (MBBI != E) {
428 // Map from instruction to its location in the current window
429 DenseMap<MachineInstr *, unsigned> MI2LocMap;
430
431 // Map from base register to list of load/store instructions
432 using Base2InstMap = DenseMap<BaseRegInfo, SmallVector<MachineInstr *, 4>>;
433 using BaseVec = SmallVector<BaseRegInfo, 4>;
434 Base2InstMap Base2LdsMap;
435 Base2InstMap Base2StsMap;
436 BaseVec LdBases;
437 BaseVec StBases;
438
439 unsigned Loc = 0;
440
441 // Build the current window of instructions
442 for (; MBBI != E; ++MBBI) {
443 MachineInstr &MI = *MBBI;
444
445 // Stop at barriers (calls and terminators)
446 if (MI.isCall() || MI.isTerminator()) {
447 // Move past the barrier for next iteration
448 ++MBBI;
449 break;
450 }
451
452 // Track instruction location in window
453 if (!MI.isDebugInstr())
454 MI2LocMap[&MI] = ++Loc;
455
456 MemOffset Offset = getMemoryOpOffset(MI);
457 // Skip non-memory operations or it's not a valid memory offset kind.
458 if (!isMemoryOp(MI) || Offset.first == MemoryOffsetKind::Unknown)
459 continue;
460
461 bool IsLd = (MI.getOpcode() == RISCV::LW);
462 const MachineOperand &BaseOp = MI.getOperand(i: 1);
463 unsigned Base;
464 if (BaseOp.isReg())
465 Base = BaseOp.getReg().id();
466 else
467 Base = BaseOp.getIndex();
468 bool StopHere = false;
469
470 // Lambda to find or add base register entries
471 auto FindBases = [&](Base2InstMap &Base2Ops, BaseVec &Bases) {
472 auto [BI, Inserted] = Base2Ops.try_emplace(Key: {Base, Offset.first});
473 if (Inserted) {
474 // First time seeing this base register
475 BI->second.push_back(Elt: &MI);
476 Bases.push_back(Elt: {Base, Offset.first});
477 return;
478 }
479 // Check if we've seen this exact base+offset before
480 if (any_of(Range&: BI->second, P: [&](const MachineInstr *PrevMI) {
481 return Offset == getMemoryOpOffset(MI: *PrevMI);
482 })) {
483 // Found duplicate base+offset - stop here to process current window
484 StopHere = true;
485 } else {
486 BI->second.push_back(Elt: &MI);
487 }
488 };
489
490 if (IsLd)
491 FindBases(Base2LdsMap, LdBases);
492 else
493 FindBases(Base2StsMap, StBases);
494
495 if (StopHere) {
496 // Found a duplicate (a base+offset combination that's seen earlier).
497 // Backtrack to process the current window.
498 --Loc;
499 break;
500 }
501 }
502
503 // Process the current window - reschedule loads
504 for (auto Base : LdBases) {
505 SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
506 if (Lds.size() > 1) {
507 Modified |= rescheduleOps(MBB, MIs&: Lds, Base, IsLoad: true, MI2LocMap);
508 }
509 }
510
511 // Process the current window - reschedule stores
512 for (auto Base : StBases) {
513 SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
514 if (Sts.size() > 1) {
515 Modified |= rescheduleOps(MBB, MIs&: Sts, Base, IsLoad: false, MI2LocMap);
516 }
517 }
518 }
519
520 return Modified;
521}
522
523//===----------------------------------------------------------------------===//
524// Pass creation functions
525//===----------------------------------------------------------------------===//
526
527FunctionPass *llvm::createRISCVPreAllocZilsdOptPass() {
528 return new RISCVPreAllocZilsdOpt();
529}
530