610 lines · cpp
1//===----- RISCVLoadStoreOptimizer.cpp ------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// Load/Store Pairing: It identifies pairs of load or store instructions10// operating on consecutive memory locations and merges them into a single11// paired instruction, leveraging hardware support for paired memory accesses.12// Much of the pairing logic is adapted from the AArch64LoadStoreOpt pass.13//14// Post-allocation Zilsd decomposition: Fixes invalid LD/SD instructions if15// register allocation didn't provide suitable consecutive registers.16//17// NOTE: The AArch64LoadStoreOpt pass performs additional optimizations such as18// merging zero store instructions, promoting loads that read directly from a19// preceding store, and merging base register updates with load/store20// instructions (via pre-/post-indexed addressing). These advanced21// transformations are not yet implemented in the RISC-V pass but represent22// potential future enhancements for further optimizing RISC-V memory23// operations.24//25//===----------------------------------------------------------------------===//26 27#include "RISCV.h"28#include "RISCVTargetMachine.h"29#include "llvm/ADT/Statistic.h"30#include "llvm/Analysis/AliasAnalysis.h"31#include "llvm/CodeGen/Passes.h"32#include "llvm/MC/TargetRegistry.h"33#include "llvm/Support/Debug.h"34#include "llvm/Target/TargetOptions.h"35 36using namespace llvm;37 38#define DEBUG_TYPE "riscv-load-store-opt"39#define RISCV_LOAD_STORE_OPT_NAME "RISC-V Load / Store Optimizer"40 41// The LdStLimit limits number of instructions how far we search for load/store42// pairs.43static cl::opt<unsigned> LdStLimit("riscv-load-store-scan-limit", cl::init(128),44 cl::Hidden);45STATISTIC(NumLD2LW, "Number of LD instructions split back to LW");46STATISTIC(NumSD2SW, "Number of SD instructions split back to SW");47 48namespace {49 50struct RISCVLoadStoreOpt : public MachineFunctionPass {51 static char ID;52 bool runOnMachineFunction(MachineFunction &Fn) override;53 54 RISCVLoadStoreOpt() : MachineFunctionPass(ID) {}55 56 MachineFunctionProperties getRequiredProperties() const override {57 return MachineFunctionProperties().setNoVRegs();58 }59 60 void getAnalysisUsage(AnalysisUsage &AU) const override {61 AU.addRequired<AAResultsWrapperPass>();62 MachineFunctionPass::getAnalysisUsage(AU);63 }64 65 StringRef getPassName() const override { return RISCV_LOAD_STORE_OPT_NAME; }66 67 // Find and pair load/store instructions.68 bool tryToPairLdStInst(MachineBasicBlock::iterator &MBBI);69 70 // Convert load/store pairs to single instructions.71 bool tryConvertToLdStPair(MachineBasicBlock::iterator First,72 MachineBasicBlock::iterator Second);73 74 // Scan the instructions looking for a load/store that can be combined75 // with the current instruction into a load/store pair.76 // Return the matching instruction if one is found, else MBB->end().77 MachineBasicBlock::iterator findMatchingInsn(MachineBasicBlock::iterator I,78 bool &MergeForward);79 80 MachineBasicBlock::iterator81 mergePairedInsns(MachineBasicBlock::iterator I,82 MachineBasicBlock::iterator Paired, bool MergeForward);83 84 // Post reg-alloc zilsd part85 bool fixInvalidRegPairOp(MachineBasicBlock &MBB,86 MachineBasicBlock::iterator &MBBI);87 bool isValidZilsdRegPair(Register First, Register Second);88 void splitLdSdIntoTwo(MachineBasicBlock &MBB,89 MachineBasicBlock::iterator &MBBI, bool IsLoad);90 91private:92 AliasAnalysis *AA;93 MachineRegisterInfo *MRI;94 const RISCVInstrInfo *TII;95 const RISCVRegisterInfo *TRI;96 LiveRegUnits ModifiedRegUnits, UsedRegUnits;97};98} // end anonymous namespace99 100char RISCVLoadStoreOpt::ID = 0;101INITIALIZE_PASS(RISCVLoadStoreOpt, DEBUG_TYPE, RISCV_LOAD_STORE_OPT_NAME, false,102 false)103 104bool RISCVLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {105 if (skipFunction(Fn.getFunction()))106 return false;107 const RISCVSubtarget &Subtarget = Fn.getSubtarget<RISCVSubtarget>();108 109 bool MadeChange = false;110 TII = Subtarget.getInstrInfo();111 TRI = Subtarget.getRegisterInfo();112 MRI = &Fn.getRegInfo();113 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();114 ModifiedRegUnits.init(*TRI);115 UsedRegUnits.init(*TRI);116 117 if (Subtarget.useMIPSLoadStorePairs()) {118 for (MachineBasicBlock &MBB : Fn) {119 LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");120 121 for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();122 MBBI != E;) {123 if (TII->isPairableLdStInstOpc(MBBI->getOpcode()) &&124 tryToPairLdStInst(MBBI))125 MadeChange = true;126 else127 ++MBBI;128 }129 }130 }131 132 if (!Subtarget.is64Bit() && Subtarget.hasStdExtZilsd()) {133 for (auto &MBB : Fn) {134 for (auto MBBI = MBB.begin(), E = MBB.end(); MBBI != E;) {135 if (fixInvalidRegPairOp(MBB, MBBI)) {136 MadeChange = true;137 // Iterator was updated by fixInvalidRegPairOp138 } else {139 ++MBBI;140 }141 }142 }143 }144 145 return MadeChange;146}147 148// Find loads and stores that can be merged into a single load or store pair149// instruction.150bool RISCVLoadStoreOpt::tryToPairLdStInst(MachineBasicBlock::iterator &MBBI) {151 MachineInstr &MI = *MBBI;152 153 // If this is volatile, it is not a candidate.154 if (MI.hasOrderedMemoryRef())155 return false;156 157 if (!TII->isLdStSafeToPair(MI, TRI))158 return false;159 160 // Look ahead for a pairable instruction.161 MachineBasicBlock::iterator E = MI.getParent()->end();162 bool MergeForward;163 MachineBasicBlock::iterator Paired = findMatchingInsn(MBBI, MergeForward);164 if (Paired != E) {165 MBBI = mergePairedInsns(MBBI, Paired, MergeForward);166 return true;167 }168 return false;169}170 171// Merge two adjacent load/store instructions into a paired instruction172// (LDP/SDP/SWP/LWP) if the effective address is 8-byte aligned in case of173// SWP/LWP 16-byte aligned in case of LDP/SDP. This function selects the174// appropriate paired opcode, verifies that the memory operand is properly175// aligned, and checks that the offset is valid. If all conditions are met, it176// builds and inserts the paired instruction.177bool RISCVLoadStoreOpt::tryConvertToLdStPair(178 MachineBasicBlock::iterator First, MachineBasicBlock::iterator Second) {179 unsigned PairOpc;180 Align RequiredAlignment;181 switch (First->getOpcode()) {182 default:183 llvm_unreachable("Unsupported load/store instruction for pairing");184 case RISCV::SW:185 PairOpc = RISCV::MIPS_SWP;186 RequiredAlignment = Align(8);187 break;188 case RISCV::LW:189 PairOpc = RISCV::MIPS_LWP;190 RequiredAlignment = Align(8);191 break;192 case RISCV::SD:193 PairOpc = RISCV::MIPS_SDP;194 RequiredAlignment = Align(16);195 break;196 case RISCV::LD:197 PairOpc = RISCV::MIPS_LDP;198 RequiredAlignment = Align(16);199 break;200 }201 202 MachineFunction *MF = First->getMF();203 const MachineMemOperand *MMO = *First->memoperands_begin();204 Align MMOAlign = MMO->getAlign();205 206 if (MMOAlign < RequiredAlignment)207 return false;208 209 int64_t Offset = First->getOperand(2).getImm();210 if (!isUInt<7>(Offset))211 return false;212 213 MachineInstrBuilder MIB = BuildMI(214 *MF, First->getDebugLoc() ? First->getDebugLoc() : Second->getDebugLoc(),215 TII->get(PairOpc));216 MIB.add(First->getOperand(0))217 .add(Second->getOperand(0))218 .add(First->getOperand(1))219 .add(First->getOperand(2))220 .cloneMergedMemRefs({&*First, &*Second});221 222 First->getParent()->insert(First, MIB);223 224 First->removeFromParent();225 Second->removeFromParent();226 227 return true;228}229 230static bool mayAlias(MachineInstr &MIa,231 SmallVectorImpl<MachineInstr *> &MemInsns,232 AliasAnalysis *AA) {233 for (MachineInstr *MIb : MemInsns)234 if (MIa.mayAlias(AA, *MIb, /*UseTBAA*/ false))235 return true;236 237 return false;238}239 240// Scan the instructions looking for a load/store that can be combined with the241// current instruction into a wider equivalent or a load/store pair.242// TODO: Extend pairing logic to consider reordering both instructions243// to a safe "middle" position rather than only merging forward/backward.244// This requires more sophisticated checks for aliasing, register245// liveness, and potential scheduling hazards.246MachineBasicBlock::iterator247RISCVLoadStoreOpt::findMatchingInsn(MachineBasicBlock::iterator I,248 bool &MergeForward) {249 MachineBasicBlock::iterator E = I->getParent()->end();250 MachineBasicBlock::iterator MBBI = I;251 MachineInstr &FirstMI = *I;252 MBBI = next_nodbg(MBBI, E);253 254 bool MayLoad = FirstMI.mayLoad();255 Register Reg = FirstMI.getOperand(0).getReg();256 Register BaseReg = FirstMI.getOperand(1).getReg();257 int64_t Offset = FirstMI.getOperand(2).getImm();258 int64_t OffsetStride = (*FirstMI.memoperands_begin())->getSize().getValue();259 260 MergeForward = false;261 262 // Track which register units have been modified and used between the first263 // insn (inclusive) and the second insn.264 ModifiedRegUnits.clear();265 UsedRegUnits.clear();266 267 // Remember any instructions that read/write memory between FirstMI and MI.268 SmallVector<MachineInstr *, 4> MemInsns;269 270 for (unsigned Count = 0; MBBI != E && Count < LdStLimit;271 MBBI = next_nodbg(MBBI, E)) {272 MachineInstr &MI = *MBBI;273 274 // Don't count transient instructions towards the search limit since there275 // may be different numbers of them if e.g. debug information is present.276 if (!MI.isTransient())277 ++Count;278 279 if (MI.getOpcode() == FirstMI.getOpcode() &&280 TII->isLdStSafeToPair(MI, TRI)) {281 Register MIBaseReg = MI.getOperand(1).getReg();282 int64_t MIOffset = MI.getOperand(2).getImm();283 284 if (BaseReg == MIBaseReg) {285 if ((Offset != MIOffset + OffsetStride) &&286 (Offset + OffsetStride != MIOffset)) {287 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,288 TRI);289 MemInsns.push_back(&MI);290 continue;291 }292 293 // If the destination register of one load is the same register or a294 // sub/super register of the other load, bail and keep looking.295 if (MayLoad &&296 TRI->isSuperOrSubRegisterEq(Reg, MI.getOperand(0).getReg())) {297 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,298 TRI);299 MemInsns.push_back(&MI);300 continue;301 }302 303 // If the BaseReg has been modified, then we cannot do the optimization.304 if (!ModifiedRegUnits.available(BaseReg))305 return E;306 307 // If the Rt of the second instruction was not modified or used between308 // the two instructions and none of the instructions between the second309 // and first alias with the second, we can combine the second into the310 // first.311 if (ModifiedRegUnits.available(MI.getOperand(0).getReg()) &&312 !(MI.mayLoad() &&313 !UsedRegUnits.available(MI.getOperand(0).getReg())) &&314 !mayAlias(MI, MemInsns, AA)) {315 316 MergeForward = false;317 return MBBI;318 }319 320 // Likewise, if the Rt of the first instruction is not modified or used321 // between the two instructions and none of the instructions between the322 // first and the second alias with the first, we can combine the first323 // into the second.324 if (!(MayLoad &&325 !UsedRegUnits.available(FirstMI.getOperand(0).getReg())) &&326 !mayAlias(FirstMI, MemInsns, AA)) {327 328 if (ModifiedRegUnits.available(FirstMI.getOperand(0).getReg())) {329 MergeForward = true;330 return MBBI;331 }332 }333 // Unable to combine these instructions due to interference in between.334 // Keep looking.335 }336 }337 338 // If the instruction wasn't a matching load or store. Stop searching if we339 // encounter a call instruction that might modify memory.340 if (MI.isCall())341 return E;342 343 // Update modified / uses register units.344 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);345 346 // Otherwise, if the base register is modified, we have no match, so347 // return early.348 if (!ModifiedRegUnits.available(BaseReg))349 return E;350 351 // Update list of instructions that read/write memory.352 if (MI.mayLoadOrStore())353 MemInsns.push_back(&MI);354 }355 return E;356}357 358MachineBasicBlock::iterator359RISCVLoadStoreOpt::mergePairedInsns(MachineBasicBlock::iterator I,360 MachineBasicBlock::iterator Paired,361 bool MergeForward) {362 MachineBasicBlock::iterator E = I->getParent()->end();363 MachineBasicBlock::iterator NextI = next_nodbg(I, E);364 // If NextI is the second of the two instructions to be merged, we need365 // to skip one further. Either way we merge will invalidate the iterator,366 // and we don't need to scan the new instruction, as it's a pairwise367 // instruction, which we're not considering for further action anyway.368 if (NextI == Paired)369 NextI = next_nodbg(NextI, E);370 371 // Insert our new paired instruction after whichever of the paired372 // instructions MergeForward indicates.373 MachineBasicBlock::iterator InsertionPoint = MergeForward ? Paired : I;374 MachineBasicBlock::iterator DeletionPoint = MergeForward ? I : Paired;375 int Offset = I->getOperand(2).getImm();376 int PairedOffset = Paired->getOperand(2).getImm();377 bool InsertAfter = (Offset < PairedOffset) ^ MergeForward;378 379 if (!MergeForward)380 Paired->getOperand(1).setIsKill(false);381 382 // Kill flags may become invalid when moving stores for pairing.383 if (I->getOperand(0).isUse()) {384 if (!MergeForward) {385 // Check if the Paired store's source register has a kill flag and clear386 // it only if there are intermediate uses between I and Paired.387 MachineOperand &PairedRegOp = Paired->getOperand(0);388 if (PairedRegOp.isKill()) {389 for (auto It = std::next(I); It != Paired; ++It) {390 if (It->readsRegister(PairedRegOp.getReg(), TRI)) {391 PairedRegOp.setIsKill(false);392 break;393 }394 }395 }396 } else {397 // Clear kill flags of the first store's register in the forward398 // direction.399 Register Reg = I->getOperand(0).getReg();400 for (MachineInstr &MI : make_range(std::next(I), std::next(Paired)))401 MI.clearRegisterKills(Reg, TRI);402 }403 }404 405 MachineInstr *ToInsert = DeletionPoint->removeFromParent();406 MachineBasicBlock &MBB = *InsertionPoint->getParent();407 MachineBasicBlock::iterator First, Second;408 409 if (!InsertAfter) {410 First = MBB.insert(InsertionPoint, ToInsert);411 Second = InsertionPoint;412 } else {413 Second = MBB.insertAfter(InsertionPoint, ToInsert);414 First = InsertionPoint;415 }416 417 if (tryConvertToLdStPair(First, Second)) {418 LLVM_DEBUG(dbgs() << "Pairing load/store:\n ");419 LLVM_DEBUG(prev_nodbg(NextI, MBB.begin())->print(dbgs()));420 }421 422 return NextI;423}424 425//===----------------------------------------------------------------------===//426// Post reg-alloc zilsd pass implementation427//===----------------------------------------------------------------------===//428 429bool RISCVLoadStoreOpt::isValidZilsdRegPair(Register First, Register Second) {430 // Special case: First register can not be zero unless both registers are431 // zeros.432 // Spec says: LD instructions with destination x0 are processed as any other433 // load, but the result is discarded entirely and x1 is not written. If using434 // x0 as src of SD, the entire 64-bit operand is zero — i.e., register x1 is435 // not accessed.436 if (First == RISCV::X0)437 return Second == RISCV::X0;438 439 // Check if registers form a valid even/odd pair for Zilsd440 unsigned FirstNum = TRI->getEncodingValue(First);441 unsigned SecondNum = TRI->getEncodingValue(Second);442 443 // Must be consecutive and first must be even444 return (FirstNum % 2 == 0) && (SecondNum == FirstNum + 1);445}446 447void RISCVLoadStoreOpt::splitLdSdIntoTwo(MachineBasicBlock &MBB,448 MachineBasicBlock::iterator &MBBI,449 bool IsLoad) {450 MachineInstr *MI = &*MBBI;451 DebugLoc DL = MI->getDebugLoc();452 453 const MachineOperand &FirstOp = MI->getOperand(0);454 const MachineOperand &SecondOp = MI->getOperand(1);455 const MachineOperand &BaseOp = MI->getOperand(2);456 Register FirstReg = FirstOp.getReg();457 Register SecondReg = SecondOp.getReg();458 Register BaseReg = BaseOp.getReg();459 460 // Handle both immediate and symbolic operands for offset461 const MachineOperand &OffsetOp = MI->getOperand(3);462 int BaseOffset;463 if (OffsetOp.isImm())464 BaseOffset = OffsetOp.getImm();465 else466 // For symbolic operands, extract the embedded offset467 BaseOffset = OffsetOp.getOffset();468 469 unsigned Opc = IsLoad ? RISCV::LW : RISCV::SW;470 MachineInstrBuilder MIB1, MIB2;471 472 // Create two separate instructions473 if (IsLoad) {474 // It's possible that first register is same as base register, when we split475 // it becomes incorrect because base register is overwritten, e.g.476 // X10, X13 = PseudoLD_RV32_OPT killed X10, 0477 // =>478 // X10 = LW X10, 0479 // X13 = LW killed X10, 4480 // we can just switch the order to resolve that:481 // X13 = LW X10, 4482 // X10 = LW killed X10, 0483 if (FirstReg == BaseReg) {484 MIB2 = BuildMI(MBB, MBBI, DL, TII->get(Opc))485 .addReg(SecondReg,486 RegState::Define | getDeadRegState(SecondOp.isDead()))487 .addReg(BaseReg);488 MIB1 = BuildMI(MBB, MBBI, DL, TII->get(Opc))489 .addReg(FirstReg,490 RegState::Define | getDeadRegState(FirstOp.isDead()))491 .addReg(BaseReg, getKillRegState(BaseOp.isKill()));492 493 } else {494 MIB1 = BuildMI(MBB, MBBI, DL, TII->get(Opc))495 .addReg(FirstReg,496 RegState::Define | getDeadRegState(FirstOp.isDead()))497 .addReg(BaseReg);498 499 MIB2 = BuildMI(MBB, MBBI, DL, TII->get(Opc))500 .addReg(SecondReg,501 RegState::Define | getDeadRegState(SecondOp.isDead()))502 .addReg(BaseReg, getKillRegState(BaseOp.isKill()));503 }504 505 ++NumLD2LW;506 LLVM_DEBUG(dbgs() << "Split LD back to two LW instructions\n");507 } else {508 assert(509 FirstReg != SecondReg &&510 "First register and second register is impossible to be same register");511 MIB1 = BuildMI(MBB, MBBI, DL, TII->get(Opc))512 .addReg(FirstReg, getKillRegState(FirstOp.isKill()))513 .addReg(BaseReg);514 515 MIB2 = BuildMI(MBB, MBBI, DL, TII->get(Opc))516 .addReg(SecondReg, getKillRegState(SecondOp.isKill()))517 .addReg(BaseReg, getKillRegState(BaseOp.isKill()));518 519 ++NumSD2SW;520 LLVM_DEBUG(dbgs() << "Split SD back to two SW instructions\n");521 }522 523 // Add offset operands - preserve symbolic references524 MIB1.add(OffsetOp);525 if (OffsetOp.isImm())526 MIB2.addImm(BaseOffset + 4);527 else if (OffsetOp.isGlobal())528 MIB2.addGlobalAddress(OffsetOp.getGlobal(), BaseOffset + 4,529 OffsetOp.getTargetFlags());530 else if (OffsetOp.isCPI())531 MIB2.addConstantPoolIndex(OffsetOp.getIndex(), BaseOffset + 4,532 OffsetOp.getTargetFlags());533 else if (OffsetOp.isBlockAddress())534 MIB2.addBlockAddress(OffsetOp.getBlockAddress(), BaseOffset + 4,535 OffsetOp.getTargetFlags());536 537 // Copy memory operands if the original instruction had them538 // FIXME: This is overly conservative; the new instruction accesses 4 bytes,539 // not 8.540 MIB1.cloneMemRefs(*MI);541 MIB2.cloneMemRefs(*MI);542 543 // Remove the original paired instruction and update iterator544 MBBI = MBB.erase(MBBI);545}546 547bool RISCVLoadStoreOpt::fixInvalidRegPairOp(MachineBasicBlock &MBB,548 MachineBasicBlock::iterator &MBBI) {549 MachineInstr *MI = &*MBBI;550 unsigned Opcode = MI->getOpcode();551 552 // Check if this is a Zilsd pseudo that needs fixing553 if (Opcode != RISCV::PseudoLD_RV32_OPT && Opcode != RISCV::PseudoSD_RV32_OPT)554 return false;555 556 bool IsLoad = Opcode == RISCV::PseudoLD_RV32_OPT;557 558 const MachineOperand &FirstOp = MI->getOperand(0);559 const MachineOperand &SecondOp = MI->getOperand(1);560 Register FirstReg = FirstOp.getReg();561 Register SecondReg = SecondOp.getReg();562 563 if (!isValidZilsdRegPair(FirstReg, SecondReg)) {564 // Need to split back into two instructions565 splitLdSdIntoTwo(MBB, MBBI, IsLoad);566 return true;567 }568 569 // Registers are valid, convert to real LD/SD instruction570 const MachineOperand &BaseOp = MI->getOperand(2);571 Register BaseReg = BaseOp.getReg();572 DebugLoc DL = MI->getDebugLoc();573 // Handle both immediate and symbolic operands for offset574 const MachineOperand &OffsetOp = MI->getOperand(3);575 576 unsigned RealOpc = IsLoad ? RISCV::LD_RV32 : RISCV::SD_RV32;577 578 // Create register pair from the two individual registers579 unsigned RegPair = TRI->getMatchingSuperReg(FirstReg, RISCV::sub_gpr_even,580 &RISCV::GPRPairRegClass);581 // Create the real LD/SD instruction with register pair582 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(RealOpc));583 584 if (IsLoad) {585 // For LD, the register pair is the destination586 MIB.addReg(RegPair, RegState::Define | getDeadRegState(FirstOp.isDead() &&587 SecondOp.isDead()));588 } else {589 // For SD, the register pair is the source590 MIB.addReg(RegPair, getKillRegState(FirstOp.isKill() && SecondOp.isKill()));591 }592 593 MIB.addReg(BaseReg, getKillRegState(BaseOp.isKill()))594 .add(OffsetOp)595 .cloneMemRefs(*MI);596 597 LLVM_DEBUG(dbgs() << "Converted pseudo to real instruction: " << *MIB598 << "\n");599 600 // Remove the pseudo instruction and update iterator601 MBBI = MBB.erase(MBBI);602 603 return true;604}605 606// Returns an instance of the Load / Store Optimization pass.607FunctionPass *llvm::createRISCVLoadStoreOptPass() {608 return new RISCVLoadStoreOpt();609}610