1 //===-- RISCVMakeCompressible.cpp - Make more instructions compressible ---===// 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 // This pass searches for instructions that are prevented from being compressed 10 // by one of the following: 11 // 12 // 1. The use of a single uncompressed register. 13 // 2. A base register + offset where the offset is too large to be compressed 14 // and the base register may or may not be compressed. 15 // 16 // 17 // For case 1, if a compressed register is available, then the uncompressed 18 // register is copied to the compressed register and its uses are replaced. 19 // 20 // For example, storing zero uses the uncompressible zero register: 21 // sw zero, 0(a0) # if zero 22 // sw zero, 8(a0) # if zero 23 // sw zero, 4(a0) # if zero 24 // sw zero, 24(a0) # if zero 25 // 26 // If a compressed register (e.g. a1) is available, the above can be transformed 27 // to the following to improve code size: 28 // li a1, 0 29 // c.sw a1, 0(a0) 30 // c.sw a1, 8(a0) 31 // c.sw a1, 4(a0) 32 // c.sw a1, 24(a0) 33 // 34 // 35 // For case 2, if a compressed register is available, then the original base 36 // is copied and adjusted such that: 37 // 38 // new_base_register = base_register + adjustment 39 // base_register + large_offset = new_base_register + small_offset 40 // 41 // For example, the following offsets are too large for c.sw: 42 // lui a2, 983065 43 // sw a1, -236(a2) 44 // sw a1, -240(a2) 45 // sw a1, -244(a2) 46 // sw a1, -248(a2) 47 // sw a1, -252(a2) 48 // sw a0, -256(a2) 49 // 50 // If a compressed register is available (e.g. a3), a new base could be created 51 // such that the addresses can accessed with a compressible offset, thus 52 // improving code size: 53 // lui a2, 983065 54 // addi a3, a2, -256 55 // c.sw a1, 20(a3) 56 // c.sw a1, 16(a3) 57 // c.sw a1, 12(a3) 58 // c.sw a1, 8(a3) 59 // c.sw a1, 4(a3) 60 // c.sw a0, 0(a3) 61 // 62 // 63 // This optimization is only applied if there are enough uses of the copied 64 // register for code size to be reduced. 65 // 66 //===----------------------------------------------------------------------===// 67 68 #include "RISCV.h" 69 #include "RISCVSubtarget.h" 70 #include "llvm/CodeGen/Passes.h" 71 #include "llvm/CodeGen/RegisterScavenging.h" 72 #include "llvm/MC/TargetRegistry.h" 73 #include "llvm/Support/Debug.h" 74 75 using namespace llvm; 76 77 #define DEBUG_TYPE "riscv-make-compressible" 78 #define RISCV_COMPRESS_INSTRS_NAME "RISC-V Make Compressible" 79 80 namespace { 81 82 struct RISCVMakeCompressibleOpt : public MachineFunctionPass { 83 static char ID; 84 85 bool runOnMachineFunction(MachineFunction &Fn) override; 86 87 RISCVMakeCompressibleOpt() : MachineFunctionPass(ID) { 88 initializeRISCVMakeCompressibleOptPass(*PassRegistry::getPassRegistry()); 89 } 90 91 StringRef getPassName() const override { return RISCV_COMPRESS_INSTRS_NAME; } 92 }; 93 } // namespace 94 95 char RISCVMakeCompressibleOpt::ID = 0; 96 INITIALIZE_PASS(RISCVMakeCompressibleOpt, "riscv-make-compressible", 97 RISCV_COMPRESS_INSTRS_NAME, false, false) 98 99 // Return log2(widthInBytes) of load/store done by Opcode. 100 static unsigned log2LdstWidth(unsigned Opcode) { 101 switch (Opcode) { 102 default: 103 llvm_unreachable("Unexpected opcode"); 104 case RISCV::LW: 105 case RISCV::SW: 106 case RISCV::FLW: 107 case RISCV::FSW: 108 return 2; 109 case RISCV::LD: 110 case RISCV::SD: 111 case RISCV::FLD: 112 case RISCV::FSD: 113 return 3; 114 } 115 } 116 117 // Return a mask for the offset bits of a non-stack-pointer based compressed 118 // load/store. 119 static uint8_t compressedLDSTOffsetMask(unsigned Opcode) { 120 return 0x1f << log2LdstWidth(Opcode); 121 } 122 123 // Return true if Offset fits within a compressed stack-pointer based 124 // load/store. 125 static bool compressibleSPOffset(int64_t Offset, unsigned Opcode) { 126 return log2LdstWidth(Opcode) == 2 ? isShiftedUInt<6, 2>(Offset) 127 : isShiftedUInt<6, 3>(Offset); 128 } 129 130 // Given an offset for a load/store, return the adjustment required to the base 131 // register such that the address can be accessed with a compressible offset. 132 // This will return 0 if the offset is already compressible. 133 static int64_t getBaseAdjustForCompression(int64_t Offset, unsigned Opcode) { 134 // Return the excess bits that do not fit in a compressible offset. 135 return Offset & ~compressedLDSTOffsetMask(Opcode); 136 } 137 138 // Return true if Reg is in a compressed register class. 139 static bool isCompressedReg(Register Reg) { 140 return RISCV::GPRCRegClass.contains(Reg) || 141 RISCV::FPR32CRegClass.contains(Reg) || 142 RISCV::FPR64CRegClass.contains(Reg); 143 } 144 145 // Return true if MI is a load for which there exists a compressed version. 146 static bool isCompressibleLoad(const MachineInstr &MI) { 147 const RISCVSubtarget &STI = MI.getMF()->getSubtarget<RISCVSubtarget>(); 148 const unsigned Opcode = MI.getOpcode(); 149 150 return Opcode == RISCV::LW || (!STI.is64Bit() && Opcode == RISCV::FLW) || 151 Opcode == RISCV::LD || Opcode == RISCV::FLD; 152 } 153 154 // Return true if MI is a store for which there exists a compressed version. 155 static bool isCompressibleStore(const MachineInstr &MI) { 156 const RISCVSubtarget &STI = MI.getMF()->getSubtarget<RISCVSubtarget>(); 157 const unsigned Opcode = MI.getOpcode(); 158 159 return Opcode == RISCV::SW || (!STI.is64Bit() && Opcode == RISCV::FSW) || 160 Opcode == RISCV::SD || Opcode == RISCV::FSD; 161 } 162 163 // Find a single register and/or large offset which, if compressible, would 164 // allow the given instruction to be compressed. 165 // 166 // Possible return values: 167 // 168 // {Reg, 0} - Uncompressed Reg needs replacing with a compressed 169 // register. 170 // {Reg, N} - Reg needs replacing with a compressed register and 171 // N needs adding to the new register. (Reg may be 172 // compressed or uncompressed). 173 // {RISCV::NoRegister, 0} - No suitable optimization found for this 174 // instruction. 175 static RegImmPair getRegImmPairPreventingCompression(const MachineInstr &MI) { 176 const unsigned Opcode = MI.getOpcode(); 177 178 if (isCompressibleLoad(MI) || isCompressibleStore(MI)) { 179 const MachineOperand &MOImm = MI.getOperand(2); 180 if (!MOImm.isImm()) 181 return RegImmPair(RISCV::NoRegister, 0); 182 183 int64_t Offset = MOImm.getImm(); 184 int64_t NewBaseAdjust = getBaseAdjustForCompression(Offset, Opcode); 185 Register Base = MI.getOperand(1).getReg(); 186 187 // Memory accesses via the stack pointer do not have a requirement for 188 // either of the registers to be compressible and can take a larger offset. 189 if (RISCV::SPRegClass.contains(Base)) { 190 if (!compressibleSPOffset(Offset, Opcode) && NewBaseAdjust) 191 return RegImmPair(Base, NewBaseAdjust); 192 } else { 193 Register SrcDest = MI.getOperand(0).getReg(); 194 bool SrcDestCompressed = isCompressedReg(SrcDest); 195 bool BaseCompressed = isCompressedReg(Base); 196 197 // If only Base and/or offset prevent compression, then return Base and 198 // any adjustment required to make the offset compressible. 199 if ((!BaseCompressed || NewBaseAdjust) && SrcDestCompressed) 200 return RegImmPair(Base, NewBaseAdjust); 201 202 // For loads, we can only change the base register since dest is defined 203 // rather than used. 204 // 205 // For stores, we can change SrcDest (and Base if SrcDest == Base) but 206 // cannot resolve an uncompressible offset in this case. 207 if (isCompressibleStore(MI)) { 208 if (!SrcDestCompressed && (BaseCompressed || SrcDest == Base) && 209 !NewBaseAdjust) 210 return RegImmPair(SrcDest, NewBaseAdjust); 211 } 212 } 213 } 214 return RegImmPair(RISCV::NoRegister, 0); 215 } 216 217 // Check all uses after FirstMI of the given register, keeping a vector of 218 // instructions that would be compressible if the given register (and offset if 219 // applicable) were compressible. 220 // 221 // If there are enough uses for this optimization to improve code size and a 222 // compressed register is available, return that compressed register. 223 static Register analyzeCompressibleUses(MachineInstr &FirstMI, 224 RegImmPair RegImm, 225 SmallVectorImpl<MachineInstr *> &MIs) { 226 MachineBasicBlock &MBB = *FirstMI.getParent(); 227 const TargetRegisterInfo *TRI = 228 MBB.getParent()->getSubtarget().getRegisterInfo(); 229 230 for (MachineBasicBlock::instr_iterator I = FirstMI.getIterator(), 231 E = MBB.instr_end(); 232 I != E; ++I) { 233 MachineInstr &MI = *I; 234 235 // Determine if this is an instruction which would benefit from using the 236 // new register. 237 RegImmPair CandidateRegImm = getRegImmPairPreventingCompression(MI); 238 if (CandidateRegImm.Reg == RegImm.Reg && CandidateRegImm.Imm == RegImm.Imm) 239 MIs.push_back(&MI); 240 241 // If RegImm.Reg is modified by this instruction, then we cannot optimize 242 // past this instruction. If the register is already compressed, then it may 243 // possible to optimize a large offset in the current instruction - this 244 // will have been detected by the preceeding call to 245 // getRegImmPairPreventingCompression. 246 if (MI.modifiesRegister(RegImm.Reg, TRI)) 247 break; 248 } 249 250 // Adjusting the base costs one new uncompressed addi and therefore three uses 251 // are required for a code size reduction. If no base adjustment is required, 252 // then copying the register costs one new c.mv (or c.li Rd, 0 for "copying" 253 // the zero register) and therefore two uses are required for a code size 254 // reduction. 255 if (MIs.size() < 2 || (RegImm.Imm != 0 && MIs.size() < 3)) 256 return RISCV::NoRegister; 257 258 // Find a compressible register which will be available from the first 259 // instruction we care about to the last. 260 const TargetRegisterClass *RCToScavenge; 261 262 // Work out the compressed register class from which to scavenge. 263 if (RISCV::GPRRegClass.contains(RegImm.Reg)) 264 RCToScavenge = &RISCV::GPRCRegClass; 265 else if (RISCV::FPR32RegClass.contains(RegImm.Reg)) 266 RCToScavenge = &RISCV::FPR32CRegClass; 267 else if (RISCV::FPR64RegClass.contains(RegImm.Reg)) 268 RCToScavenge = &RISCV::FPR64CRegClass; 269 else 270 return RISCV::NoRegister; 271 272 RegScavenger RS; 273 RS.enterBasicBlockEnd(MBB); 274 RS.backward(MIs.back()->getIterator()); 275 return RS.scavengeRegisterBackwards(*RCToScavenge, FirstMI.getIterator(), 276 /*RestoreAfter=*/false, /*SPAdj=*/0, 277 /*AllowSpill=*/false); 278 } 279 280 // Update uses of the old register in the given instruction to the new register. 281 static void updateOperands(MachineInstr &MI, RegImmPair OldRegImm, 282 Register NewReg) { 283 unsigned Opcode = MI.getOpcode(); 284 285 // If this pass is extended to support more instructions, the check for 286 // definedness may need to be strengthened. 287 assert((isCompressibleLoad(MI) || isCompressibleStore(MI)) && 288 "Unsupported instruction for this optimization."); 289 290 int SkipN = 0; 291 292 // Skip the first (value) operand to a store instruction (except if the store 293 // offset is zero) in order to avoid an incorrect transformation. 294 // e.g. sd a0, 808(a0) to addi a2, a0, 768; sd a2, 40(a2) 295 if (isCompressibleStore(MI) && OldRegImm.Imm != 0) 296 SkipN = 1; 297 298 // Update registers 299 for (MachineOperand &MO : drop_begin(MI.operands(), SkipN)) 300 if (MO.isReg() && MO.getReg() == OldRegImm.Reg) { 301 // Do not update operands that define the old register. 302 // 303 // The new register was scavenged for the range of instructions that are 304 // being updated, therefore it should not be defined within this range 305 // except possibly in the final instruction. 306 if (MO.isDef()) { 307 assert(isCompressibleLoad(MI)); 308 continue; 309 } 310 // Update reg 311 MO.setReg(NewReg); 312 } 313 314 // Update offset 315 MachineOperand &MOImm = MI.getOperand(2); 316 int64_t NewOffset = MOImm.getImm() & compressedLDSTOffsetMask(Opcode); 317 MOImm.setImm(NewOffset); 318 } 319 320 bool RISCVMakeCompressibleOpt::runOnMachineFunction(MachineFunction &Fn) { 321 // This is a size optimization. 322 if (skipFunction(Fn.getFunction()) || !Fn.getFunction().hasMinSize()) 323 return false; 324 325 const RISCVSubtarget &STI = Fn.getSubtarget<RISCVSubtarget>(); 326 const RISCVInstrInfo &TII = *STI.getInstrInfo(); 327 328 // This optimization only makes sense if compressed instructions are emitted. 329 // FIXME: Support Zca, Zcf, Zcd granularity. 330 if (!STI.hasStdExtC()) 331 return false; 332 333 for (MachineBasicBlock &MBB : Fn) { 334 LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n"); 335 for (MachineInstr &MI : MBB) { 336 // Determine if this instruction would otherwise be compressed if not for 337 // an uncompressible register or offset. 338 RegImmPair RegImm = getRegImmPairPreventingCompression(MI); 339 if (!RegImm.Reg && RegImm.Imm == 0) 340 continue; 341 342 // Determine if there is a set of instructions for which replacing this 343 // register with a compressed register (and compressible offset if 344 // applicable) is possible and will allow compression. 345 SmallVector<MachineInstr *, 8> MIs; 346 Register NewReg = analyzeCompressibleUses(MI, RegImm, MIs); 347 if (!NewReg) 348 continue; 349 350 // Create the appropriate copy and/or offset. 351 if (RISCV::GPRRegClass.contains(RegImm.Reg)) { 352 assert(isInt<12>(RegImm.Imm)); 353 BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(RISCV::ADDI), NewReg) 354 .addReg(RegImm.Reg) 355 .addImm(RegImm.Imm); 356 } else { 357 // If we are looking at replacing an FPR register we don't expect to 358 // have any offset. The only compressible FP instructions with an offset 359 // are loads and stores, for which the offset applies to the GPR operand 360 // not the FPR operand. 361 assert(RegImm.Imm == 0); 362 unsigned Opcode = RISCV::FPR32RegClass.contains(RegImm.Reg) 363 ? RISCV::FSGNJ_S 364 : RISCV::FSGNJ_D; 365 BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(Opcode), NewReg) 366 .addReg(RegImm.Reg) 367 .addReg(RegImm.Reg); 368 } 369 370 // Update the set of instructions to use the compressed register and 371 // compressible offset instead. These instructions should now be 372 // compressible. 373 // TODO: Update all uses if RegImm.Imm == 0? Not just those that are 374 // expected to become compressible. 375 for (MachineInstr *UpdateMI : MIs) 376 updateOperands(*UpdateMI, RegImm, NewReg); 377 } 378 } 379 return true; 380 } 381 382 /// Returns an instance of the Make Compressible Optimization pass. 383 FunctionPass *llvm::createRISCVMakeCompressibleOptPass() { 384 return new RISCVMakeCompressibleOpt(); 385 } 386