1 //===----- RISCVMergeBaseOffset.cpp - Optimise address calculations ------===// 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 // Merge the offset of address calculation into the offset field 10 // of instructions in a global address lowering sequence. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "RISCV.h" 15 #include "RISCVTargetMachine.h" 16 #include "llvm/CodeGen/MachineFunctionPass.h" 17 #include "llvm/CodeGen/Passes.h" 18 #include "llvm/MC/TargetRegistry.h" 19 #include "llvm/Support/Debug.h" 20 #include "llvm/Target/TargetOptions.h" 21 #include <optional> 22 using namespace llvm; 23 24 #define DEBUG_TYPE "riscv-merge-base-offset" 25 #define RISCV_MERGE_BASE_OFFSET_NAME "RISC-V Merge Base Offset" 26 namespace { 27 28 class RISCVMergeBaseOffsetOpt : public MachineFunctionPass { 29 const RISCVSubtarget *ST = nullptr; 30 MachineRegisterInfo *MRI; 31 32 public: 33 static char ID; 34 bool runOnMachineFunction(MachineFunction &Fn) override; 35 bool detectFoldable(MachineInstr &Hi, MachineInstr *&Lo); 36 37 bool detectAndFoldOffset(MachineInstr &Hi, MachineInstr &Lo); 38 void foldOffset(MachineInstr &Hi, MachineInstr &Lo, MachineInstr &Tail, 39 int64_t Offset); 40 bool foldLargeOffset(MachineInstr &Hi, MachineInstr &Lo, 41 MachineInstr &TailAdd, Register GSReg); 42 bool foldShiftedOffset(MachineInstr &Hi, MachineInstr &Lo, 43 MachineInstr &TailShXAdd, Register GSReg); 44 45 bool foldIntoMemoryOps(MachineInstr &Hi, MachineInstr &Lo); 46 47 RISCVMergeBaseOffsetOpt() : MachineFunctionPass(ID) {} 48 49 MachineFunctionProperties getRequiredProperties() const override { 50 return MachineFunctionProperties().set( 51 MachineFunctionProperties::Property::IsSSA); 52 } 53 54 void getAnalysisUsage(AnalysisUsage &AU) const override { 55 AU.setPreservesCFG(); 56 MachineFunctionPass::getAnalysisUsage(AU); 57 } 58 59 StringRef getPassName() const override { 60 return RISCV_MERGE_BASE_OFFSET_NAME; 61 } 62 }; 63 } // end anonymous namespace 64 65 char RISCVMergeBaseOffsetOpt::ID = 0; 66 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, DEBUG_TYPE, 67 RISCV_MERGE_BASE_OFFSET_NAME, false, false) 68 69 // Detect either of the patterns: 70 // 71 // 1. (medlow pattern): 72 // lui vreg1, %hi(s) 73 // addi vreg2, vreg1, %lo(s) 74 // 75 // 2. (medany pattern): 76 // .Lpcrel_hi1: 77 // auipc vreg1, %pcrel_hi(s) 78 // addi vreg2, vreg1, %pcrel_lo(.Lpcrel_hi1) 79 // 80 // The pattern is only accepted if: 81 // 1) The first instruction has only one use, which is the ADDI. 82 // 2) The address operands have the appropriate type, reflecting the 83 // lowering of a global address or constant pool using medlow or medany. 84 // 3) The offset value in the Global Address or Constant Pool is 0. 85 bool RISCVMergeBaseOffsetOpt::detectFoldable(MachineInstr &Hi, 86 MachineInstr *&Lo) { 87 if (Hi.getOpcode() != RISCV::LUI && Hi.getOpcode() != RISCV::AUIPC) 88 return false; 89 90 const MachineOperand &HiOp1 = Hi.getOperand(1); 91 unsigned ExpectedFlags = 92 Hi.getOpcode() == RISCV::AUIPC ? RISCVII::MO_PCREL_HI : RISCVII::MO_HI; 93 if (HiOp1.getTargetFlags() != ExpectedFlags) 94 return false; 95 96 if (!(HiOp1.isGlobal() || HiOp1.isCPI() || HiOp1.isBlockAddress()) || 97 HiOp1.getOffset() != 0) 98 return false; 99 100 Register HiDestReg = Hi.getOperand(0).getReg(); 101 if (!MRI->hasOneUse(HiDestReg)) 102 return false; 103 104 Lo = &*MRI->use_instr_begin(HiDestReg); 105 if (Lo->getOpcode() != RISCV::ADDI) 106 return false; 107 108 const MachineOperand &LoOp2 = Lo->getOperand(2); 109 if (Hi.getOpcode() == RISCV::LUI) { 110 if (LoOp2.getTargetFlags() != RISCVII::MO_LO || 111 !(LoOp2.isGlobal() || LoOp2.isCPI() || LoOp2.isBlockAddress()) || 112 LoOp2.getOffset() != 0) 113 return false; 114 } else { 115 assert(Hi.getOpcode() == RISCV::AUIPC); 116 if (LoOp2.getTargetFlags() != RISCVII::MO_PCREL_LO || 117 LoOp2.getType() != MachineOperand::MO_MCSymbol) 118 return false; 119 } 120 121 if (HiOp1.isGlobal()) { 122 LLVM_DEBUG(dbgs() << " Found lowered global address: " 123 << *HiOp1.getGlobal() << "\n"); 124 } else if (HiOp1.isBlockAddress()) { 125 LLVM_DEBUG(dbgs() << " Found lowered basic address: " 126 << *HiOp1.getBlockAddress() << "\n"); 127 } else if (HiOp1.isCPI()) { 128 LLVM_DEBUG(dbgs() << " Found lowered constant pool: " << HiOp1.getIndex() 129 << "\n"); 130 } 131 132 return true; 133 } 134 135 // Update the offset in Hi and Lo instructions. 136 // Delete the tail instruction and update all the uses to use the 137 // output from Lo. 138 void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &Hi, MachineInstr &Lo, 139 MachineInstr &Tail, int64_t Offset) { 140 assert(isInt<32>(Offset) && "Unexpected offset"); 141 // Put the offset back in Hi and the Lo 142 Hi.getOperand(1).setOffset(Offset); 143 if (Hi.getOpcode() != RISCV::AUIPC) 144 Lo.getOperand(2).setOffset(Offset); 145 // Delete the tail instruction. 146 MRI->constrainRegClass(Lo.getOperand(0).getReg(), 147 MRI->getRegClass(Tail.getOperand(0).getReg())); 148 MRI->replaceRegWith(Tail.getOperand(0).getReg(), Lo.getOperand(0).getReg()); 149 Tail.eraseFromParent(); 150 LLVM_DEBUG(dbgs() << " Merged offset " << Offset << " into base.\n" 151 << " " << Hi << " " << Lo;); 152 } 153 154 // Detect patterns for large offsets that are passed into an ADD instruction. 155 // If the pattern is found, updates the offset in Hi and Lo instructions 156 // and deletes TailAdd and the instructions that produced the offset. 157 // 158 // Base address lowering is of the form: 159 // Hi: lui vreg1, %hi(s) 160 // Lo: addi vreg2, vreg1, %lo(s) 161 // / \ 162 // / \ 163 // / \ 164 // / The large offset can be of two forms: \ 165 // 1) Offset that has non zero bits in lower 2) Offset that has non zero 166 // 12 bits and upper 20 bits bits in upper 20 bits only 167 // OffseLUI: lui vreg3, 4 168 // OffsetTail: addi voff, vreg3, 188 OffsetTail: lui voff, 128 169 // \ / 170 // \ / 171 // \ / 172 // \ / 173 // TailAdd: add vreg4, vreg2, voff 174 bool RISCVMergeBaseOffsetOpt::foldLargeOffset(MachineInstr &Hi, 175 MachineInstr &Lo, 176 MachineInstr &TailAdd, 177 Register GAReg) { 178 assert((TailAdd.getOpcode() == RISCV::ADD) && "Expected ADD instruction!"); 179 Register Rs = TailAdd.getOperand(1).getReg(); 180 Register Rt = TailAdd.getOperand(2).getReg(); 181 Register Reg = Rs == GAReg ? Rt : Rs; 182 183 // Can't fold if the register has more than one use. 184 if (!MRI->hasOneUse(Reg)) 185 return false; 186 // This can point to an ADDI(W) or a LUI: 187 MachineInstr &OffsetTail = *MRI->getVRegDef(Reg); 188 if (OffsetTail.getOpcode() == RISCV::ADDI || 189 OffsetTail.getOpcode() == RISCV::ADDIW) { 190 // The offset value has non zero bits in both %hi and %lo parts. 191 // Detect an ADDI that feeds from a LUI instruction. 192 MachineOperand &AddiImmOp = OffsetTail.getOperand(2); 193 if (AddiImmOp.getTargetFlags() != RISCVII::MO_None) 194 return false; 195 int64_t OffLo = AddiImmOp.getImm(); 196 MachineInstr &OffsetLui = 197 *MRI->getVRegDef(OffsetTail.getOperand(1).getReg()); 198 MachineOperand &LuiImmOp = OffsetLui.getOperand(1); 199 if (OffsetLui.getOpcode() != RISCV::LUI || 200 LuiImmOp.getTargetFlags() != RISCVII::MO_None || 201 !MRI->hasOneUse(OffsetLui.getOperand(0).getReg())) 202 return false; 203 int64_t Offset = SignExtend64<32>(LuiImmOp.getImm() << 12); 204 Offset += OffLo; 205 // RV32 ignores the upper 32 bits. ADDIW sign extends the result. 206 if (!ST->is64Bit() || OffsetTail.getOpcode() == RISCV::ADDIW) 207 Offset = SignExtend64<32>(Offset); 208 // We can only fold simm32 offsets. 209 if (!isInt<32>(Offset)) 210 return false; 211 LLVM_DEBUG(dbgs() << " Offset Instrs: " << OffsetTail 212 << " " << OffsetLui); 213 foldOffset(Hi, Lo, TailAdd, Offset); 214 OffsetTail.eraseFromParent(); 215 OffsetLui.eraseFromParent(); 216 return true; 217 } else if (OffsetTail.getOpcode() == RISCV::LUI) { 218 // The offset value has all zero bits in the lower 12 bits. Only LUI 219 // exists. 220 LLVM_DEBUG(dbgs() << " Offset Instr: " << OffsetTail); 221 int64_t Offset = SignExtend64<32>(OffsetTail.getOperand(1).getImm() << 12); 222 foldOffset(Hi, Lo, TailAdd, Offset); 223 OffsetTail.eraseFromParent(); 224 return true; 225 } 226 return false; 227 } 228 229 // Detect patterns for offsets that are passed into a SHXADD instruction. 230 // The offset has 1, 2, or 3 trailing zeros and fits in simm13, simm14, simm15. 231 // The constant is created with addi voff, x0, C, and shXadd is used to 232 // fill insert the trailing zeros and do the addition. 233 // If the pattern is found, updates the offset in Hi and Lo instructions 234 // and deletes TailShXAdd and the instructions that produced the offset. 235 // 236 // Hi: lui vreg1, %hi(s) 237 // Lo: addi vreg2, vreg1, %lo(s) 238 // OffsetTail: addi voff, x0, C 239 // TailAdd: shXadd vreg4, voff, vreg2 240 bool RISCVMergeBaseOffsetOpt::foldShiftedOffset(MachineInstr &Hi, 241 MachineInstr &Lo, 242 MachineInstr &TailShXAdd, 243 Register GAReg) { 244 assert((TailShXAdd.getOpcode() == RISCV::SH1ADD || 245 TailShXAdd.getOpcode() == RISCV::SH2ADD || 246 TailShXAdd.getOpcode() == RISCV::SH3ADD) && 247 "Expected SHXADD instruction!"); 248 249 // The first source is the shifted operand. 250 Register Rs1 = TailShXAdd.getOperand(1).getReg(); 251 252 if (GAReg != TailShXAdd.getOperand(2).getReg()) 253 return false; 254 255 // Can't fold if the register has more than one use. 256 if (!MRI->hasOneUse(Rs1)) 257 return false; 258 // This can point to an ADDI X0, C. 259 MachineInstr &OffsetTail = *MRI->getVRegDef(Rs1); 260 if (OffsetTail.getOpcode() != RISCV::ADDI) 261 return false; 262 if (!OffsetTail.getOperand(1).isReg() || 263 OffsetTail.getOperand(1).getReg() != RISCV::X0 || 264 !OffsetTail.getOperand(2).isImm()) 265 return false; 266 267 int64_t Offset = OffsetTail.getOperand(2).getImm(); 268 assert(isInt<12>(Offset) && "Unexpected offset"); 269 270 unsigned ShAmt; 271 switch (TailShXAdd.getOpcode()) { 272 default: llvm_unreachable("Unexpected opcode"); 273 case RISCV::SH1ADD: ShAmt = 1; break; 274 case RISCV::SH2ADD: ShAmt = 2; break; 275 case RISCV::SH3ADD: ShAmt = 3; break; 276 } 277 278 Offset = (uint64_t)Offset << ShAmt; 279 280 LLVM_DEBUG(dbgs() << " Offset Instr: " << OffsetTail); 281 foldOffset(Hi, Lo, TailShXAdd, Offset); 282 OffsetTail.eraseFromParent(); 283 return true; 284 } 285 286 bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &Hi, 287 MachineInstr &Lo) { 288 Register DestReg = Lo.getOperand(0).getReg(); 289 290 // Look for arithmetic instructions we can get an offset from. 291 // We might be able to remove the arithmetic instructions by folding the 292 // offset into the LUI+ADDI. 293 if (!MRI->hasOneUse(DestReg)) 294 return false; 295 296 // Lo has only one use. 297 MachineInstr &Tail = *MRI->use_instr_begin(DestReg); 298 switch (Tail.getOpcode()) { 299 default: 300 LLVM_DEBUG(dbgs() << "Don't know how to get offset from this instr:" 301 << Tail); 302 break; 303 case RISCV::ADDI: { 304 // Offset is simply an immediate operand. 305 int64_t Offset = Tail.getOperand(2).getImm(); 306 307 // We might have two ADDIs in a row. 308 Register TailDestReg = Tail.getOperand(0).getReg(); 309 if (MRI->hasOneUse(TailDestReg)) { 310 MachineInstr &TailTail = *MRI->use_instr_begin(TailDestReg); 311 if (TailTail.getOpcode() == RISCV::ADDI) { 312 Offset += TailTail.getOperand(2).getImm(); 313 LLVM_DEBUG(dbgs() << " Offset Instrs: " << Tail << TailTail); 314 foldOffset(Hi, Lo, TailTail, Offset); 315 Tail.eraseFromParent(); 316 return true; 317 } 318 } 319 320 LLVM_DEBUG(dbgs() << " Offset Instr: " << Tail); 321 foldOffset(Hi, Lo, Tail, Offset); 322 return true; 323 } 324 case RISCV::ADD: 325 // The offset is too large to fit in the immediate field of ADDI. 326 // This can be in two forms: 327 // 1) LUI hi_Offset followed by: 328 // ADDI lo_offset 329 // This happens in case the offset has non zero bits in 330 // both hi 20 and lo 12 bits. 331 // 2) LUI (offset20) 332 // This happens in case the lower 12 bits of the offset are zeros. 333 return foldLargeOffset(Hi, Lo, Tail, DestReg); 334 case RISCV::SH1ADD: 335 case RISCV::SH2ADD: 336 case RISCV::SH3ADD: 337 // The offset is too large to fit in the immediate field of ADDI. 338 // It may be encoded as (SH2ADD (ADDI X0, C), DestReg) or 339 // (SH3ADD (ADDI X0, C), DestReg). 340 return foldShiftedOffset(Hi, Lo, Tail, DestReg); 341 } 342 343 return false; 344 } 345 346 bool RISCVMergeBaseOffsetOpt::foldIntoMemoryOps(MachineInstr &Hi, 347 MachineInstr &Lo) { 348 Register DestReg = Lo.getOperand(0).getReg(); 349 350 // If all the uses are memory ops with the same offset, we can transform: 351 // 352 // 1. (medlow pattern): 353 // Hi: lui vreg1, %hi(foo) ---> lui vreg1, %hi(foo+8) 354 // Lo: addi vreg2, vreg1, %lo(foo) ---> lw vreg3, lo(foo+8)(vreg1) 355 // Tail: lw vreg3, 8(vreg2) 356 // 357 // 2. (medany pattern): 358 // Hi: 1:auipc vreg1, %pcrel_hi(s) ---> auipc vreg1, %pcrel_hi(foo+8) 359 // Lo: addi vreg2, vreg1, %pcrel_lo(1b) ---> lw vreg3, %pcrel_lo(1b)(vreg1) 360 // Tail: lw vreg3, 8(vreg2) 361 362 std::optional<int64_t> CommonOffset; 363 for (const MachineInstr &UseMI : MRI->use_instructions(DestReg)) { 364 switch (UseMI.getOpcode()) { 365 default: 366 LLVM_DEBUG(dbgs() << "Not a load or store instruction: " << UseMI); 367 return false; 368 case RISCV::LB: 369 case RISCV::LH: 370 case RISCV::LW: 371 case RISCV::LBU: 372 case RISCV::LHU: 373 case RISCV::LWU: 374 case RISCV::LD: 375 case RISCV::FLH: 376 case RISCV::FLW: 377 case RISCV::FLD: 378 case RISCV::SB: 379 case RISCV::SH: 380 case RISCV::SW: 381 case RISCV::SD: 382 case RISCV::FSH: 383 case RISCV::FSW: 384 case RISCV::FSD: { 385 if (UseMI.getOperand(1).isFI()) 386 return false; 387 // Register defined by Lo should not be the value register. 388 if (DestReg == UseMI.getOperand(0).getReg()) 389 return false; 390 assert(DestReg == UseMI.getOperand(1).getReg() && 391 "Expected base address use"); 392 // All load/store instructions must use the same offset. 393 int64_t Offset = UseMI.getOperand(2).getImm(); 394 if (CommonOffset && Offset != CommonOffset) 395 return false; 396 CommonOffset = Offset; 397 } 398 } 399 } 400 401 // We found a common offset. 402 // Update the offsets in global address lowering. 403 // We may have already folded some arithmetic so we need to add to any 404 // existing offset. 405 int64_t NewOffset = Hi.getOperand(1).getOffset() + *CommonOffset; 406 // RV32 ignores the upper 32 bits. 407 if (!ST->is64Bit()) 408 NewOffset = SignExtend64<32>(NewOffset); 409 // We can only fold simm32 offsets. 410 if (!isInt<32>(NewOffset)) 411 return false; 412 413 Hi.getOperand(1).setOffset(NewOffset); 414 MachineOperand &ImmOp = Lo.getOperand(2); 415 if (Hi.getOpcode() != RISCV::AUIPC) 416 ImmOp.setOffset(NewOffset); 417 418 // Update the immediate in the load/store instructions to add the offset. 419 for (MachineInstr &UseMI : 420 llvm::make_early_inc_range(MRI->use_instructions(DestReg))) { 421 UseMI.removeOperand(2); 422 UseMI.addOperand(ImmOp); 423 // Update the base reg in the Tail instruction to feed from LUI. 424 // Output of Hi is only used in Lo, no need to use MRI->replaceRegWith(). 425 UseMI.getOperand(1).setReg(Hi.getOperand(0).getReg()); 426 } 427 428 Lo.eraseFromParent(); 429 return true; 430 } 431 432 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) { 433 if (skipFunction(Fn.getFunction())) 434 return false; 435 436 ST = &Fn.getSubtarget<RISCVSubtarget>(); 437 438 bool MadeChange = false; 439 MRI = &Fn.getRegInfo(); 440 for (MachineBasicBlock &MBB : Fn) { 441 LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n"); 442 for (MachineInstr &Hi : MBB) { 443 MachineInstr *Lo = nullptr; 444 if (!detectFoldable(Hi, Lo)) 445 continue; 446 MadeChange |= detectAndFoldOffset(Hi, *Lo); 447 MadeChange |= foldIntoMemoryOps(Hi, *Lo); 448 } 449 } 450 451 return MadeChange; 452 } 453 454 /// Returns an instance of the Merge Base Offset Optimization pass. 455 FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() { 456 return new RISCVMergeBaseOffsetOpt(); 457 } 458