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. This pass transforms: 11 // lui vreg1, %hi(s) 12 // addi vreg2, vreg1, %lo(s) 13 // addi vreg3, verg2, Offset 14 // 15 // Into: 16 // lui vreg1, %hi(s+Offset) 17 // addi vreg2, vreg1, %lo(s+Offset) 18 // 19 // The transformation is carried out under certain conditions: 20 // 1) The offset field in the base of global address lowering sequence is zero. 21 // 2) The lowered global address has only one use. 22 // 23 // The offset field can be in a different form. This pass handles all of them. 24 //===----------------------------------------------------------------------===// 25 26 #include "RISCV.h" 27 #include "RISCVTargetMachine.h" 28 #include "llvm/CodeGen/Passes.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/TargetRegistry.h" 31 #include "llvm/Target/TargetOptions.h" 32 #include <set> 33 using namespace llvm; 34 35 #define DEBUG_TYPE "riscv-merge-base-offset" 36 #define RISCV_MERGE_BASE_OFFSET_NAME "RISCV Merge Base Offset" 37 namespace { 38 39 struct RISCVMergeBaseOffsetOpt : public MachineFunctionPass { 40 static char ID; 41 const MachineFunction *MF; 42 bool runOnMachineFunction(MachineFunction &Fn) override; 43 bool detectLuiAddiGlobal(MachineInstr &LUI, MachineInstr *&ADDI); 44 45 bool detectAndFoldOffset(MachineInstr &HiLUI, MachineInstr &LoADDI); 46 void foldOffset(MachineInstr &HiLUI, MachineInstr &LoADDI, MachineInstr &Tail, 47 int64_t Offset); 48 bool matchLargeOffset(MachineInstr &TailAdd, Register GSReg, int64_t &Offset); 49 RISCVMergeBaseOffsetOpt() : MachineFunctionPass(ID) {} 50 51 MachineFunctionProperties getRequiredProperties() const override { 52 return MachineFunctionProperties().set( 53 MachineFunctionProperties::Property::IsSSA); 54 } 55 56 StringRef getPassName() const override { 57 return RISCV_MERGE_BASE_OFFSET_NAME; 58 } 59 60 private: 61 MachineRegisterInfo *MRI; 62 std::set<MachineInstr *> DeadInstrs; 63 }; 64 } // end anonymous namespace 65 66 char RISCVMergeBaseOffsetOpt::ID = 0; 67 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, DEBUG_TYPE, 68 RISCV_MERGE_BASE_OFFSET_NAME, false, false) 69 70 // Detect the pattern: 71 // lui vreg1, %hi(s) 72 // addi vreg2, vreg1, %lo(s) 73 // 74 // Pattern only accepted if: 75 // 1) ADDI has only one use. 76 // 2) LUI has only one use; which is the ADDI. 77 // 3) Both ADDI and LUI have GlobalAddress type which indicates that these 78 // are generated from global address lowering. 79 // 4) Offset value in the Global Address is 0. 80 bool RISCVMergeBaseOffsetOpt::detectLuiAddiGlobal(MachineInstr &HiLUI, 81 MachineInstr *&LoADDI) { 82 if (HiLUI.getOpcode() != RISCV::LUI || 83 HiLUI.getOperand(1).getTargetFlags() != RISCVII::MO_HI || 84 HiLUI.getOperand(1).getType() != MachineOperand::MO_GlobalAddress || 85 HiLUI.getOperand(1).getOffset() != 0 || 86 !MRI->hasOneUse(HiLUI.getOperand(0).getReg())) 87 return false; 88 Register HiLuiDestReg = HiLUI.getOperand(0).getReg(); 89 LoADDI = MRI->use_begin(HiLuiDestReg)->getParent(); 90 if (LoADDI->getOpcode() != RISCV::ADDI || 91 LoADDI->getOperand(2).getTargetFlags() != RISCVII::MO_LO || 92 LoADDI->getOperand(2).getType() != MachineOperand::MO_GlobalAddress || 93 LoADDI->getOperand(2).getOffset() != 0 || 94 !MRI->hasOneUse(LoADDI->getOperand(0).getReg())) 95 return false; 96 return true; 97 } 98 99 // Update the offset in HiLUI and LoADDI instructions. 100 // Delete the tail instruction and update all the uses to use the 101 // output from LoADDI. 102 void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &HiLUI, 103 MachineInstr &LoADDI, 104 MachineInstr &Tail, int64_t Offset) { 105 // Put the offset back in HiLUI and the LoADDI 106 HiLUI.getOperand(1).setOffset(Offset); 107 LoADDI.getOperand(2).setOffset(Offset); 108 // Delete the tail instruction. 109 DeadInstrs.insert(&Tail); 110 MRI->replaceRegWith(Tail.getOperand(0).getReg(), 111 LoADDI.getOperand(0).getReg()); 112 LLVM_DEBUG(dbgs() << " Merged offset " << Offset << " into base.\n" 113 << " " << HiLUI << " " << LoADDI;); 114 } 115 116 // Detect patterns for large offsets that are passed into an ADD instruction. 117 // 118 // Base address lowering is of the form: 119 // HiLUI: lui vreg1, %hi(s) 120 // LoADDI: addi vreg2, vreg1, %lo(s) 121 // / \ 122 // / \ 123 // / \ 124 // / The large offset can be of two forms: \ 125 // 1) Offset that has non zero bits in lower 2) Offset that has non zero 126 // 12 bits and upper 20 bits bits in upper 20 bits only 127 // OffseLUI: lui vreg3, 4 128 // OffsetTail: addi voff, vreg3, 188 OffsetTail: lui voff, 128 129 // \ / 130 // \ / 131 // \ / 132 // \ / 133 // TailAdd: add vreg4, vreg2, voff 134 bool RISCVMergeBaseOffsetOpt::matchLargeOffset(MachineInstr &TailAdd, 135 Register GAReg, 136 int64_t &Offset) { 137 assert((TailAdd.getOpcode() == RISCV::ADD) && "Expected ADD instruction!"); 138 Register Rs = TailAdd.getOperand(1).getReg(); 139 Register Rt = TailAdd.getOperand(2).getReg(); 140 Register Reg = Rs == GAReg ? Rt : Rs; 141 142 // Can't fold if the register has more than one use. 143 if (!MRI->hasOneUse(Reg)) 144 return false; 145 // This can point to an ADDI or a LUI: 146 MachineInstr &OffsetTail = *MRI->getVRegDef(Reg); 147 if (OffsetTail.getOpcode() == RISCV::ADDI) { 148 // The offset value has non zero bits in both %hi and %lo parts. 149 // Detect an ADDI that feeds from a LUI instruction. 150 MachineOperand &AddiImmOp = OffsetTail.getOperand(2); 151 if (AddiImmOp.getTargetFlags() != RISCVII::MO_None) 152 return false; 153 int64_t OffLo = AddiImmOp.getImm(); 154 MachineInstr &OffsetLui = 155 *MRI->getVRegDef(OffsetTail.getOperand(1).getReg()); 156 MachineOperand &LuiImmOp = OffsetLui.getOperand(1); 157 if (OffsetLui.getOpcode() != RISCV::LUI || 158 LuiImmOp.getTargetFlags() != RISCVII::MO_None || 159 !MRI->hasOneUse(OffsetLui.getOperand(0).getReg())) 160 return false; 161 int64_t OffHi = OffsetLui.getOperand(1).getImm(); 162 Offset = (OffHi << 12) + OffLo; 163 LLVM_DEBUG(dbgs() << " Offset Instrs: " << OffsetTail 164 << " " << OffsetLui); 165 DeadInstrs.insert(&OffsetTail); 166 DeadInstrs.insert(&OffsetLui); 167 return true; 168 } else if (OffsetTail.getOpcode() == RISCV::LUI) { 169 // The offset value has all zero bits in the lower 12 bits. Only LUI 170 // exists. 171 LLVM_DEBUG(dbgs() << " Offset Instr: " << OffsetTail); 172 Offset = OffsetTail.getOperand(1).getImm() << 12; 173 DeadInstrs.insert(&OffsetTail); 174 return true; 175 } 176 return false; 177 } 178 179 bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &HiLUI, 180 MachineInstr &LoADDI) { 181 Register DestReg = LoADDI.getOperand(0).getReg(); 182 assert(MRI->hasOneUse(DestReg) && "expected one use for LoADDI"); 183 // LoADDI has only one use. 184 MachineInstr &Tail = *MRI->use_begin(DestReg)->getParent(); 185 switch (Tail.getOpcode()) { 186 default: 187 LLVM_DEBUG(dbgs() << "Don't know how to get offset from this instr:" 188 << Tail); 189 return false; 190 case RISCV::ADDI: { 191 // Offset is simply an immediate operand. 192 int64_t Offset = Tail.getOperand(2).getImm(); 193 LLVM_DEBUG(dbgs() << " Offset Instr: " << Tail); 194 foldOffset(HiLUI, LoADDI, Tail, Offset); 195 return true; 196 } break; 197 case RISCV::ADD: { 198 // The offset is too large to fit in the immediate field of ADDI. 199 // This can be in two forms: 200 // 1) LUI hi_Offset followed by: 201 // ADDI lo_offset 202 // This happens in case the offset has non zero bits in 203 // both hi 20 and lo 12 bits. 204 // 2) LUI (offset20) 205 // This happens in case the lower 12 bits of the offset are zeros. 206 int64_t Offset; 207 if (!matchLargeOffset(Tail, DestReg, Offset)) 208 return false; 209 foldOffset(HiLUI, LoADDI, Tail, Offset); 210 return true; 211 } break; 212 case RISCV::LB: 213 case RISCV::LH: 214 case RISCV::LW: 215 case RISCV::LBU: 216 case RISCV::LHU: 217 case RISCV::LWU: 218 case RISCV::LD: 219 case RISCV::FLH: 220 case RISCV::FLW: 221 case RISCV::FLD: 222 case RISCV::SB: 223 case RISCV::SH: 224 case RISCV::SW: 225 case RISCV::SD: 226 case RISCV::FSH: 227 case RISCV::FSW: 228 case RISCV::FSD: { 229 // Transforms the sequence: Into: 230 // HiLUI: lui vreg1, %hi(foo) ---> lui vreg1, %hi(foo+8) 231 // LoADDI: addi vreg2, vreg1, %lo(foo) ---> lw vreg3, lo(foo+8)(vreg1) 232 // Tail: lw vreg3, 8(vreg2) 233 if (Tail.getOperand(1).isFI()) 234 return false; 235 // Register defined by LoADDI should be used in the base part of the 236 // load\store instruction. Otherwise, no folding possible. 237 Register BaseAddrReg = Tail.getOperand(1).getReg(); 238 if (DestReg != BaseAddrReg) 239 return false; 240 MachineOperand &TailImmOp = Tail.getOperand(2); 241 int64_t Offset = TailImmOp.getImm(); 242 // Update the offsets in global address lowering. 243 HiLUI.getOperand(1).setOffset(Offset); 244 // Update the immediate in the Tail instruction to add the offset. 245 Tail.RemoveOperand(2); 246 MachineOperand &ImmOp = LoADDI.getOperand(2); 247 ImmOp.setOffset(Offset); 248 Tail.addOperand(ImmOp); 249 // Update the base reg in the Tail instruction to feed from LUI. 250 // Output of HiLUI is only used in LoADDI, no need to use 251 // MRI->replaceRegWith(). 252 Tail.getOperand(1).setReg(HiLUI.getOperand(0).getReg()); 253 DeadInstrs.insert(&LoADDI); 254 return true; 255 } break; 256 } 257 return false; 258 } 259 260 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) { 261 if (skipFunction(Fn.getFunction())) 262 return false; 263 264 DeadInstrs.clear(); 265 MRI = &Fn.getRegInfo(); 266 for (MachineBasicBlock &MBB : Fn) { 267 LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n"); 268 for (MachineInstr &HiLUI : MBB) { 269 MachineInstr *LoADDI = nullptr; 270 if (!detectLuiAddiGlobal(HiLUI, LoADDI)) 271 continue; 272 LLVM_DEBUG(dbgs() << " Found lowered global address with one use: " 273 << *LoADDI->getOperand(2).getGlobal() << "\n"); 274 // If the use count is only one, merge the offset 275 detectAndFoldOffset(HiLUI, *LoADDI); 276 } 277 } 278 // Delete dead instructions. 279 for (auto *MI : DeadInstrs) 280 MI->eraseFromParent(); 281 return true; 282 } 283 284 /// Returns an instance of the Merge Base Offset Optimization pass. 285 FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() { 286 return new RISCVMergeBaseOffsetOpt(); 287 } 288