528 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains a pass that performs load/store optimizations for the10// RISC-V Zilsd extension. It combines pairs of 32-bit load/store instructions11// 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 memory15// accesses closer together and forms LD/SD pairs with register hints.16// 2. Post-allocation: Fixes invalid LD/SD instructions if register allocation17// didn't provide suitable consecutive registers.18//19// Note: second phase is integrated into RISCVLoadStoreOptimizer20//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/CommandLine.h"40#include "llvm/Support/Debug.h"41#include <algorithm>42 43using namespace llvm;44 45#define DEBUG_TYPE "riscv-zilsd-opt"46 47STATISTIC(NumLDFormed, "Number of LD instructions formed");48STATISTIC(NumSDFormed, "Number of SD instructions formed");49 50static cl::opt<bool>51 DisableZilsdOpt("disable-riscv-zilsd-opt", cl::Hidden, cl::init(false),52 cl::desc("Disable Zilsd load/store optimization"));53 54static cl::opt<unsigned> MaxRescheduleDistance(55 "riscv-zilsd-max-reschedule-distance", cl::Hidden, cl::init(10),56 cl::desc("Maximum distance for rescheduling load/store instructions"));57 58namespace {59 60//===----------------------------------------------------------------------===//61// Pre-allocation Zilsd optimization pass62//===----------------------------------------------------------------------===//63class RISCVPreAllocZilsdOpt : public MachineFunctionPass {64public:65 static char ID;66 67 RISCVPreAllocZilsdOpt() : MachineFunctionPass(ID) {}68 69 bool runOnMachineFunction(MachineFunction &MF) override;70 71 StringRef getPassName() const override {72 return "RISC-V pre-allocation Zilsd load/store optimization";73 }74 75 MachineFunctionProperties getRequiredProperties() const override {76 return MachineFunctionProperties().setIsSSA();77 }78 79 void getAnalysisUsage(AnalysisUsage &AU) const override {80 AU.addRequired<AAResultsWrapperPass>();81 AU.addRequired<MachineDominatorTreeWrapperPass>();82 AU.setPreservesCFG();83 MachineFunctionPass::getAnalysisUsage(AU);84 }85 enum class MemoryOffsetKind {86 Imm = 0,87 Global = 1,88 CPI = 2,89 BlockAddr = 3,90 Unknown = 4,91 };92 using MemOffset = std::pair<MemoryOffsetKind, int>;93 using BaseRegInfo = std::pair<unsigned, MemoryOffsetKind>;94 95private:96 bool isMemoryOp(const MachineInstr &MI);97 bool rescheduleLoadStoreInstrs(MachineBasicBlock *MBB);98 bool canFormLdSdPair(MachineInstr *MI0, MachineInstr *MI1);99 bool rescheduleOps(MachineBasicBlock *MBB,100 SmallVectorImpl<MachineInstr *> &MIs, BaseRegInfo Base,101 bool IsLoad,102 DenseMap<MachineInstr *, unsigned> &MI2LocMap);103 bool isSafeToMove(MachineInstr *MI, MachineInstr *Target, bool MoveForward);104 MemOffset getMemoryOpOffset(const MachineInstr &MI);105 106 const RISCVSubtarget *STI;107 const RISCVInstrInfo *TII;108 const RISCVRegisterInfo *TRI;109 MachineRegisterInfo *MRI;110 AliasAnalysis *AA;111 MachineDominatorTree *DT;112 Align RequiredAlign;113};114 115} // end anonymous namespace116 117char RISCVPreAllocZilsdOpt::ID = 0;118 119INITIALIZE_PASS_BEGIN(RISCVPreAllocZilsdOpt, "riscv-prera-zilsd-opt",120 "RISC-V pre-allocation Zilsd optimization", false, false)121INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)122INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)123INITIALIZE_PASS_END(RISCVPreAllocZilsdOpt, "riscv-prera-zilsd-opt",124 "RISC-V pre-allocation Zilsd optimization", false, false)125 126//===----------------------------------------------------------------------===//127// Pre-allocation pass implementation128//===----------------------------------------------------------------------===//129 130bool RISCVPreAllocZilsdOpt::runOnMachineFunction(MachineFunction &MF) {131 132 if (DisableZilsdOpt || skipFunction(MF.getFunction()))133 return false;134 135 STI = &MF.getSubtarget<RISCVSubtarget>();136 137 // Only run on RV32 with Zilsd extension138 if (STI->is64Bit() || !STI->hasStdExtZilsd())139 return false;140 141 TII = STI->getInstrInfo();142 TRI = STI->getRegisterInfo();143 MRI = &MF.getRegInfo();144 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();145 DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();146 147 // Check alignment: default is 8-byte, but allow 4-byte with tune feature148 // If unaligned scalar memory is enabled, allow any alignment149 RequiredAlign = STI->getZilsdAlign();150 bool Modified = false;151 for (auto &MBB : MF) {152 Modified |= rescheduleLoadStoreInstrs(&MBB);153 }154 155 return Modified;156}157 158RISCVPreAllocZilsdOpt::MemOffset159RISCVPreAllocZilsdOpt::getMemoryOpOffset(const MachineInstr &MI) {160 switch (MI.getOpcode()) {161 case RISCV::LW:162 case RISCV::SW: {163 // For LW/SW, the offset is in operand 2164 const MachineOperand &OffsetOp = MI.getOperand(2);165 166 // Handle immediate offset167 if (OffsetOp.isImm())168 return std::make_pair(MemoryOffsetKind::Imm, OffsetOp.getImm());169 170 // Handle symbolic operands with MO_LO flag (from MergeBaseOffset)171 if (OffsetOp.getTargetFlags() & RISCVII::MO_LO) {172 if (OffsetOp.isGlobal())173 return std::make_pair(MemoryOffsetKind::Global, OffsetOp.getOffset());174 if (OffsetOp.isCPI())175 return std::make_pair(MemoryOffsetKind::CPI, OffsetOp.getOffset());176 if (OffsetOp.isBlockAddress())177 return std::make_pair(MemoryOffsetKind::BlockAddr,178 OffsetOp.getOffset());179 }180 181 break;182 }183 default:184 break;185 }186 187 return std::make_pair(MemoryOffsetKind::Unknown, 0);188}189 190bool RISCVPreAllocZilsdOpt::canFormLdSdPair(MachineInstr *MI0,191 MachineInstr *MI1) {192 if (!MI0->hasOneMemOperand() || !MI1->hasOneMemOperand())193 return false;194 195 // Get offsets and check they are consecutive196 int Offset0 = getMemoryOpOffset(*MI0).second;197 int Offset1 = getMemoryOpOffset(*MI1).second;198 199 // Offsets must be 4 bytes apart200 if (Offset1 - Offset0 != 4)201 return false;202 203 // We need to guarantee the alignment(base + offset) is legal.204 const MachineMemOperand *MMO = *MI0->memoperands_begin();205 if (MMO->getAlign() < RequiredAlign)206 return false;207 208 // Check that the two destination/source registers are different for209 // load/store respectively.210 Register FirstReg = MI0->getOperand(0).getReg();211 Register SecondReg = MI1->getOperand(0).getReg();212 if (FirstReg == SecondReg)213 return false;214 215 return true;216}217 218bool RISCVPreAllocZilsdOpt::isSafeToMove(MachineInstr *MI, MachineInstr *Target,219 bool MoveForward) {220 MachineBasicBlock *MBB = MI->getParent();221 MachineBasicBlock::iterator Start = MI->getIterator();222 MachineBasicBlock::iterator End = Target->getIterator();223 224 if (!MoveForward)225 std::swap(Start, End);226 227 // Increment Start to skip the current instruction228 if (Start != MBB->end())229 ++Start;230 231 Register DefReg = MI->getOperand(0).getReg();232 Register BaseReg = MI->getOperand(1).getReg();233 234 unsigned ScanCount = 0;235 for (auto It = Start; It != End; ++It, ++ScanCount) {236 // Don't move across calls or terminators237 if (It->isCall() || It->isTerminator()) {238 LLVM_DEBUG(dbgs() << "Cannot move across call/terminator: " << *It);239 return false;240 }241 242 // Don't move across instructions that modify memory barrier243 if (It->hasUnmodeledSideEffects()) {244 LLVM_DEBUG(dbgs() << "Cannot move across instruction with side effects: "245 << *It);246 return false;247 }248 249 // Check if the base register is modified250 if (It->modifiesRegister(BaseReg, TRI)) {251 LLVM_DEBUG(dbgs() << "Base register " << BaseReg252 << " modified by: " << *It);253 return false;254 }255 256 // For loads, check if the loaded value is used257 if (MI->mayLoad() &&258 (It->readsRegister(DefReg, TRI) || It->modifiesRegister(DefReg, TRI))) {259 LLVM_DEBUG(dbgs() << "Destination register " << DefReg260 << " used by: " << *It);261 return false;262 }263 264 // For stores, check if the stored register is modified265 if (MI->mayStore() && It->modifiesRegister(DefReg, TRI)) {266 LLVM_DEBUG(dbgs() << "Source register " << DefReg267 << " modified by: " << *It);268 return false;269 }270 271 // Check for memory operation interference272 if (It->mayLoadOrStore() && It->mayAlias(AA, *MI, /*UseTBAA*/ false)) {273 LLVM_DEBUG(dbgs() << "Memory operation interference detected\n");274 return false;275 }276 }277 278 return true;279}280 281bool RISCVPreAllocZilsdOpt::rescheduleOps(282 MachineBasicBlock *MBB, SmallVectorImpl<MachineInstr *> &MIs,283 BaseRegInfo Base, bool IsLoad,284 DenseMap<MachineInstr *, unsigned> &MI2LocMap) {285 // Sort by offset, at this point it ensure base reg and MemoryOffsetKind are286 // same, so we just need to simply sort by offset value.287 llvm::sort(MIs.begin(), MIs.end(), [this](MachineInstr *A, MachineInstr *B) {288 return getMemoryOpOffset(*A).second < getMemoryOpOffset(*B).second;289 });290 291 bool Modified = false;292 293 // Try to pair consecutive operations294 for (size_t i = 0; i + 1 < MIs.size(); i++) {295 MachineInstr *MI0 = MIs[i];296 MachineInstr *MI1 = MIs[i + 1];297 298 Register FirstReg = MI0->getOperand(0).getReg();299 Register SecondReg = MI1->getOperand(0).getReg();300 Register BaseReg = MI0->getOperand(1).getReg();301 const MachineOperand &OffsetOp = MI0->getOperand(2);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 program313 // order314 bool MI1IsLater = MI2LocMap[MI1] > MI2LocMap[MI0];315 316 // For loads: move later instruction up (backwards) to earlier instruction317 // For stores: move earlier instruction down (forwards) to later instruction318 MachineInstr *MoveInstr, *TargetInstr;319 if (IsLoad) {320 // For loads: move the later instruction to the earlier one321 MoveInstr = MI1IsLater ? MI1 : MI0;322 TargetInstr = MI1IsLater ? MI0 : MI1;323 } else {324 // For stores: move the earlier instruction to the later one325 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(MoveInstr, TargetInstr, !IsLoad) ||332 Distance > MaxRescheduleDistance)333 continue;334 335 // Move the instruction to the target position336 MachineBasicBlock::iterator InsertPos = TargetInstr->getIterator();337 ++InsertPos;338 339 // If we need to move an instruction, do it now340 if (MoveInstr != TargetInstr)341 MBB->splice(InsertPos, MBB, MoveInstr->getIterator());342 343 // Create the paired instruction344 MachineInstrBuilder MIB;345 DebugLoc DL = MI0->getDebugLoc();346 347 if (IsLoad) {348 MIB = BuildMI(*MBB, InsertPos, DL, TII->get(RISCV::PseudoLD_RV32_OPT))349 .addReg(FirstReg, RegState::Define)350 .addReg(SecondReg, RegState::Define)351 .addReg(BaseReg)352 .add(OffsetOp);353 ++NumLDFormed;354 LLVM_DEBUG(dbgs() << "Formed LD: " << *MIB << "\n");355 } else {356 MIB = BuildMI(*MBB, InsertPos, DL, TII->get(RISCV::PseudoSD_RV32_OPT))357 .addReg(FirstReg)358 .addReg(SecondReg)359 .addReg(BaseReg)360 .add(OffsetOp);361 ++NumSDFormed;362 LLVM_DEBUG(dbgs() << "Formed SD: " << *MIB << "\n");363 }364 365 // Copy memory operands366 MIB.cloneMergedMemRefs({MI0, MI1});367 368 // Add register allocation hints for consecutive registers369 // RISC-V Zilsd requires even/odd register pairs370 // Only set hints for virtual registers (physical registers already have371 // encoding)372 if (FirstReg.isVirtual() && SecondReg.isVirtual()) {373 // For virtual registers, we can't determine even/odd yet, but we can hint374 // that they should be allocated as a consecutive pair375 MRI->setRegAllocationHint(FirstReg, RISCVRI::RegPairEven, SecondReg);376 MRI->setRegAllocationHint(SecondReg, RISCVRI::RegPairOdd, FirstReg);377 }378 379 // Remove the original instructions380 MI0->eraseFromParent();381 MI1->eraseFromParent();382 383 Modified = true;384 385 // Skip the next instruction since we've already processed it386 i++;387 }388 389 return Modified;390}391 392bool RISCVPreAllocZilsdOpt::isMemoryOp(const MachineInstr &MI) {393 unsigned Opcode = MI.getOpcode();394 if (Opcode != RISCV::LW && Opcode != RISCV::SW)395 return false;396 397 if (!MI.getOperand(1).isReg())398 return false;399 400 // When no memory operands are present, conservatively assume unaligned,401 // volatile, unfoldable.402 if (!MI.hasOneMemOperand())403 return false;404 405 const MachineMemOperand *MMO = *MI.memoperands_begin();406 407 if (MMO->isVolatile() || MMO->isAtomic())408 return false;409 410 // sw <undef> could probably be eliminated entirely, but for now we just want411 // to avoid making a mess of it.412 if (MI.getOperand(0).isReg() && MI.getOperand(0).isUndef())413 return false;414 415 // Likewise don't mess with references to undefined addresses.416 if (MI.getOperand(1).isUndef())417 return false;418 419 return true;420}421 422bool RISCVPreAllocZilsdOpt::rescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {423 bool Modified = false;424 425 // Process the basic block in windows delimited by calls, terminators,426 // or instructions with duplicate base+offset pairs427 MachineBasicBlock::iterator MBBI = MBB->begin();428 MachineBasicBlock::iterator E = MBB->end();429 430 while (MBBI != E) {431 // Map from instruction to its location in the current window432 DenseMap<MachineInstr *, unsigned> MI2LocMap;433 434 // Map from base register to list of load/store instructions435 using Base2InstMap = DenseMap<BaseRegInfo, SmallVector<MachineInstr *, 4>>;436 using BaseVec = SmallVector<BaseRegInfo, 4>;437 Base2InstMap Base2LdsMap;438 Base2InstMap Base2StsMap;439 BaseVec LdBases;440 BaseVec StBases;441 442 unsigned Loc = 0;443 444 // Build the current window of instructions445 for (; MBBI != E; ++MBBI) {446 MachineInstr &MI = *MBBI;447 448 // Stop at barriers (calls and terminators)449 if (MI.isCall() || MI.isTerminator()) {450 // Move past the barrier for next iteration451 ++MBBI;452 break;453 }454 455 // Track instruction location in window456 if (!MI.isDebugInstr())457 MI2LocMap[&MI] = ++Loc;458 459 MemOffset Offset = getMemoryOpOffset(MI);460 // Skip non-memory operations or it's not a valid memory offset kind.461 if (!isMemoryOp(MI) || Offset.first == MemoryOffsetKind::Unknown)462 continue;463 464 bool IsLd = (MI.getOpcode() == RISCV::LW);465 Register Base = MI.getOperand(1).getReg();466 bool StopHere = false;467 468 // Lambda to find or add base register entries469 auto FindBases = [&](Base2InstMap &Base2Ops, BaseVec &Bases) {470 auto [BI, Inserted] = Base2Ops.try_emplace({Base.id(), Offset.first});471 if (Inserted) {472 // First time seeing this base register473 BI->second.push_back(&MI);474 Bases.push_back({Base.id(), Offset.first});475 return;476 }477 // Check if we've seen this exact base+offset before478 if (any_of(BI->second, [&](const MachineInstr *PrevMI) {479 return Offset == getMemoryOpOffset(*PrevMI);480 })) {481 // Found duplicate base+offset - stop here to process current window482 StopHere = true;483 } else {484 BI->second.push_back(&MI);485 }486 };487 488 if (IsLd)489 FindBases(Base2LdsMap, LdBases);490 else491 FindBases(Base2StsMap, StBases);492 493 if (StopHere) {494 // Found a duplicate (a base+offset combination that's seen earlier).495 // Backtrack to process the current window.496 --Loc;497 break;498 }499 }500 501 // Process the current window - reschedule loads502 for (auto Base : LdBases) {503 SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];504 if (Lds.size() > 1) {505 Modified |= rescheduleOps(MBB, Lds, Base, true, MI2LocMap);506 }507 }508 509 // Process the current window - reschedule stores510 for (auto Base : StBases) {511 SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];512 if (Sts.size() > 1) {513 Modified |= rescheduleOps(MBB, Sts, Base, false, MI2LocMap);514 }515 }516 }517 518 return Modified;519}520 521//===----------------------------------------------------------------------===//522// Pass creation functions523//===----------------------------------------------------------------------===//524 525FunctionPass *llvm::createRISCVPreAllocZilsdOptPass() {526 return new RISCVPreAllocZilsdOpt();527}528