LLVM 19.0.0git
RISCVMakeCompressible.cpp
Go to the documentation of this file.
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"
73#include "llvm/Support/Debug.h"
74
75using namespace llvm;
76
77#define DEBUG_TYPE "riscv-make-compressible"
78#define RISCV_COMPRESS_INSTRS_NAME "RISC-V Make Compressible"
79
80namespace {
81
82struct RISCVMakeCompressibleOpt : public MachineFunctionPass {
83 static char ID;
84
85 bool runOnMachineFunction(MachineFunction &Fn) override;
86
87 RISCVMakeCompressibleOpt() : MachineFunctionPass(ID) {}
88
89 StringRef getPassName() const override { return RISCV_COMPRESS_INSTRS_NAME; }
90};
91} // namespace
92
93char RISCVMakeCompressibleOpt::ID = 0;
94INITIALIZE_PASS(RISCVMakeCompressibleOpt, "riscv-make-compressible",
95 RISCV_COMPRESS_INSTRS_NAME, false, false)
96
97// Return log2(widthInBytes) of load/store done by Opcode.
98static unsigned log2LdstWidth(unsigned Opcode) {
99 switch (Opcode) {
100 default:
101 llvm_unreachable("Unexpected opcode");
102 case RISCV::LW:
103 case RISCV::SW:
104 case RISCV::FLW:
105 case RISCV::FSW:
106 return 2;
107 case RISCV::LD:
108 case RISCV::SD:
109 case RISCV::FLD:
110 case RISCV::FSD:
111 return 3;
112 }
113}
114
115// Return a mask for the offset bits of a non-stack-pointer based compressed
116// load/store.
117static uint8_t compressedLDSTOffsetMask(unsigned Opcode) {
118 return 0x1f << log2LdstWidth(Opcode);
119}
120
121// Return true if Offset fits within a compressed stack-pointer based
122// load/store.
123static bool compressibleSPOffset(int64_t Offset, unsigned Opcode) {
124 return log2LdstWidth(Opcode) == 2 ? isShiftedUInt<6, 2>(Offset)
125 : isShiftedUInt<6, 3>(Offset);
126}
127
128// Given an offset for a load/store, return the adjustment required to the base
129// register such that the address can be accessed with a compressible offset.
130// This will return 0 if the offset is already compressible.
131static int64_t getBaseAdjustForCompression(int64_t Offset, unsigned Opcode) {
132 // Return the excess bits that do not fit in a compressible offset.
133 return Offset & ~compressedLDSTOffsetMask(Opcode);
134}
135
136// Return true if Reg is in a compressed register class.
137static bool isCompressedReg(Register Reg) {
138 return RISCV::GPRCRegClass.contains(Reg) ||
139 RISCV::FPR32CRegClass.contains(Reg) ||
140 RISCV::FPR64CRegClass.contains(Reg);
141}
142
143// Return true if MI is a load for which there exists a compressed version.
144static bool isCompressibleLoad(const MachineInstr &MI) {
145 const RISCVSubtarget &STI = MI.getMF()->getSubtarget<RISCVSubtarget>();
146
147 switch (MI.getOpcode()) {
148 default:
149 return false;
150 case RISCV::LW:
151 case RISCV::LD:
152 return STI.hasStdExtCOrZca();
153 case RISCV::FLW:
154 return !STI.is64Bit() && STI.hasStdExtCOrZcfOrZce();
155 case RISCV::FLD:
156 return STI.hasStdExtCOrZcd();
157 }
158}
159
160// Return true if MI is a store for which there exists a compressed version.
162 const RISCVSubtarget &STI = MI.getMF()->getSubtarget<RISCVSubtarget>();
163
164 switch (MI.getOpcode()) {
165 default:
166 return false;
167 case RISCV::SW:
168 case RISCV::SD:
169 return STI.hasStdExtCOrZca();
170 case RISCV::FSW:
171 return !STI.is64Bit() && STI.hasStdExtCOrZcfOrZce();
172 case RISCV::FSD:
173 return STI.hasStdExtCOrZcd();
174 }
175}
176
177// Find a single register and/or large offset which, if compressible, would
178// allow the given instruction to be compressed.
179//
180// Possible return values:
181//
182// {Reg, 0} - Uncompressed Reg needs replacing with a compressed
183// register.
184// {Reg, N} - Reg needs replacing with a compressed register and
185// N needs adding to the new register. (Reg may be
186// compressed or uncompressed).
187// {RISCV::NoRegister, 0} - No suitable optimization found for this
188// instruction.
190 const unsigned Opcode = MI.getOpcode();
191
193 const MachineOperand &MOImm = MI.getOperand(2);
194 if (!MOImm.isImm())
195 return RegImmPair(RISCV::NoRegister, 0);
196
197 int64_t Offset = MOImm.getImm();
198 int64_t NewBaseAdjust = getBaseAdjustForCompression(Offset, Opcode);
199 Register Base = MI.getOperand(1).getReg();
200
201 // Memory accesses via the stack pointer do not have a requirement for
202 // either of the registers to be compressible and can take a larger offset.
203 if (RISCV::SPRegClass.contains(Base)) {
204 if (!compressibleSPOffset(Offset, Opcode) && NewBaseAdjust)
205 return RegImmPair(Base, NewBaseAdjust);
206 } else {
207 Register SrcDest = MI.getOperand(0).getReg();
208 bool SrcDestCompressed = isCompressedReg(SrcDest);
209 bool BaseCompressed = isCompressedReg(Base);
210
211 // If only Base and/or offset prevent compression, then return Base and
212 // any adjustment required to make the offset compressible.
213 if ((!BaseCompressed || NewBaseAdjust) && SrcDestCompressed)
214 return RegImmPair(Base, NewBaseAdjust);
215
216 // For loads, we can only change the base register since dest is defined
217 // rather than used.
218 //
219 // For stores, we can change SrcDest (and Base if SrcDest == Base) but
220 // cannot resolve an uncompressible offset in this case.
221 if (isCompressibleStore(MI)) {
222 if (!SrcDestCompressed && (BaseCompressed || SrcDest == Base) &&
223 !NewBaseAdjust)
224 return RegImmPair(SrcDest, NewBaseAdjust);
225 }
226 }
227 }
228 return RegImmPair(RISCV::NoRegister, 0);
229}
230
231// Check all uses after FirstMI of the given register, keeping a vector of
232// instructions that would be compressible if the given register (and offset if
233// applicable) were compressible.
234//
235// If there are enough uses for this optimization to improve code size and a
236// compressed register is available, return that compressed register.
238 RegImmPair RegImm,
240 MachineBasicBlock &MBB = *FirstMI.getParent();
241 const TargetRegisterInfo *TRI =
243
245 E = MBB.instr_end();
246 I != E; ++I) {
247 MachineInstr &MI = *I;
248
249 // Determine if this is an instruction which would benefit from using the
250 // new register.
252 if (CandidateRegImm.Reg == RegImm.Reg && CandidateRegImm.Imm == RegImm.Imm)
253 MIs.push_back(&MI);
254
255 // If RegImm.Reg is modified by this instruction, then we cannot optimize
256 // past this instruction. If the register is already compressed, then it may
257 // possible to optimize a large offset in the current instruction - this
258 // will have been detected by the preceeding call to
259 // getRegImmPairPreventingCompression.
260 if (MI.modifiesRegister(RegImm.Reg, TRI))
261 break;
262 }
263
264 // Adjusting the base costs one new uncompressed addi and therefore three uses
265 // are required for a code size reduction. If no base adjustment is required,
266 // then copying the register costs one new c.mv (or c.li Rd, 0 for "copying"
267 // the zero register) and therefore two uses are required for a code size
268 // reduction.
269 if (MIs.size() < 2 || (RegImm.Imm != 0 && MIs.size() < 3))
270 return RISCV::NoRegister;
271
272 // Find a compressible register which will be available from the first
273 // instruction we care about to the last.
274 const TargetRegisterClass *RCToScavenge;
275
276 // Work out the compressed register class from which to scavenge.
277 if (RISCV::GPRRegClass.contains(RegImm.Reg))
278 RCToScavenge = &RISCV::GPRCRegClass;
279 else if (RISCV::FPR32RegClass.contains(RegImm.Reg))
280 RCToScavenge = &RISCV::FPR32CRegClass;
281 else if (RISCV::FPR64RegClass.contains(RegImm.Reg))
282 RCToScavenge = &RISCV::FPR64CRegClass;
283 else
284 return RISCV::NoRegister;
285
286 RegScavenger RS;
288 RS.backward(std::next(MIs.back()->getIterator()));
289 return RS.scavengeRegisterBackwards(*RCToScavenge, FirstMI.getIterator(),
290 /*RestoreAfter=*/false, /*SPAdj=*/0,
291 /*AllowSpill=*/false);
292}
293
294// Update uses of the old register in the given instruction to the new register.
295static void updateOperands(MachineInstr &MI, RegImmPair OldRegImm,
296 Register NewReg) {
297 unsigned Opcode = MI.getOpcode();
298
299 // If this pass is extended to support more instructions, the check for
300 // definedness may need to be strengthened.
302 "Unsupported instruction for this optimization.");
303
304 int SkipN = 0;
305
306 // Skip the first (value) operand to a store instruction (except if the store
307 // offset is zero) in order to avoid an incorrect transformation.
308 // e.g. sd a0, 808(a0) to addi a2, a0, 768; sd a2, 40(a2)
309 if (isCompressibleStore(MI) && OldRegImm.Imm != 0)
310 SkipN = 1;
311
312 // Update registers
313 for (MachineOperand &MO : drop_begin(MI.operands(), SkipN))
314 if (MO.isReg() && MO.getReg() == OldRegImm.Reg) {
315 // Do not update operands that define the old register.
316 //
317 // The new register was scavenged for the range of instructions that are
318 // being updated, therefore it should not be defined within this range
319 // except possibly in the final instruction.
320 if (MO.isDef()) {
322 continue;
323 }
324 // Update reg
325 MO.setReg(NewReg);
326 }
327
328 // Update offset
329 MachineOperand &MOImm = MI.getOperand(2);
330 int64_t NewOffset = MOImm.getImm() & compressedLDSTOffsetMask(Opcode);
331 MOImm.setImm(NewOffset);
332}
333
334bool RISCVMakeCompressibleOpt::runOnMachineFunction(MachineFunction &Fn) {
335 // This is a size optimization.
336 if (skipFunction(Fn.getFunction()) || !Fn.getFunction().hasMinSize())
337 return false;
338
339 const RISCVSubtarget &STI = Fn.getSubtarget<RISCVSubtarget>();
340 const RISCVInstrInfo &TII = *STI.getInstrInfo();
341
342 // This optimization only makes sense if compressed instructions are emitted.
343 if (!STI.hasStdExtCOrZca())
344 return false;
345
346 for (MachineBasicBlock &MBB : Fn) {
347 LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
348 for (MachineInstr &MI : MBB) {
349 // Determine if this instruction would otherwise be compressed if not for
350 // an uncompressible register or offset.
352 if (!RegImm.Reg && RegImm.Imm == 0)
353 continue;
354
355 // Determine if there is a set of instructions for which replacing this
356 // register with a compressed register (and compressible offset if
357 // applicable) is possible and will allow compression.
359 Register NewReg = analyzeCompressibleUses(MI, RegImm, MIs);
360 if (!NewReg)
361 continue;
362
363 // Create the appropriate copy and/or offset.
364 if (RISCV::GPRRegClass.contains(RegImm.Reg)) {
365 assert(isInt<12>(RegImm.Imm));
366 BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(RISCV::ADDI), NewReg)
367 .addReg(RegImm.Reg)
368 .addImm(RegImm.Imm);
369 } else {
370 // If we are looking at replacing an FPR register we don't expect to
371 // have any offset. The only compressible FP instructions with an offset
372 // are loads and stores, for which the offset applies to the GPR operand
373 // not the FPR operand.
374 assert(RegImm.Imm == 0);
375 unsigned Opcode = RISCV::FPR32RegClass.contains(RegImm.Reg)
376 ? RISCV::FSGNJ_S
377 : RISCV::FSGNJ_D;
378 BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(Opcode), NewReg)
379 .addReg(RegImm.Reg)
380 .addReg(RegImm.Reg);
381 }
382
383 // Update the set of instructions to use the compressed register and
384 // compressible offset instead. These instructions should now be
385 // compressible.
386 // TODO: Update all uses if RegImm.Imm == 0? Not just those that are
387 // expected to become compressible.
388 for (MachineInstr *UpdateMI : MIs)
389 updateOperands(*UpdateMI, RegImm, NewReg);
390 }
391 }
392 return true;
393}
394
395/// Returns an instance of the Make Compressible Optimization pass.
397 return new RISCVMakeCompressibleOpt();
398}
MachineBasicBlock & MBB
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static bool isCompressibleLoad(const MachineInstr &MI)
#define RISCV_COMPRESS_INSTRS_NAME
static bool isCompressibleStore(const MachineInstr &MI)
static uint8_t compressedLDSTOffsetMask(unsigned Opcode)
static bool isCompressedReg(Register Reg)
static Register analyzeCompressibleUses(MachineInstr &FirstMI, RegImmPair RegImm, SmallVectorImpl< MachineInstr * > &MIs)
static int64_t getBaseAdjustForCompression(int64_t Offset, unsigned Opcode)
static void updateOperands(MachineInstr &MI, RegImmPair OldRegImm, Register NewReg)
static bool compressibleSPOffset(int64_t Offset, unsigned Opcode)
static RegImmPair getRegImmPairPreventingCompression(const MachineInstr &MI)
This file declares the machine register scavenger class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition: Value.cpp:469
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:674
Instructions::iterator instr_iterator
instr_iterator instr_end()
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:327
MachineOperand class - Representation of each machine instruction operand.
void setImm(int64_t immVal)
int64_t getImm() const
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
bool hasStdExtCOrZca() const
bool hasStdExtCOrZcfOrZce() const
const RISCVInstrInfo * getInstrInfo() const override
bool hasStdExtCOrZcd() const
void enterBasicBlockEnd(MachineBasicBlock &MBB)
Start tracking liveness from the end of basic block MBB.
void backward()
Update internal register state and move MBB iterator backwards.
Register scavengeRegisterBackwards(const TargetRegisterClass &RC, MachineBasicBlock::iterator To, bool RestoreAfter, int SPAdj, bool AllowSpill=true)
Make a register of the specific register class available from the current position backwards to the p...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
self_iterator getIterator()
Definition: ilist_node.h:109
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
@ Offset
Definition: DWP.cpp:456
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
FunctionPass * createRISCVMakeCompressibleOptPass()
Returns an instance of the Make Compressible Optimization pass.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Used to describe a register and immediate addition.