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