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