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);
RISCVMergeBaseOffsetOpt__anon99178d800111::RISCVMergeBaseOffsetOpt49 RISCVMergeBaseOffsetOpt() : MachineFunctionPass(ID) {}
50
getRequiredProperties__anon99178d800111::RISCVMergeBaseOffsetOpt51 MachineFunctionProperties getRequiredProperties() const override {
52 return MachineFunctionProperties().set(
53 MachineFunctionProperties::Property::IsSSA);
54 }
55
getPassName__anon99178d800111::RISCVMergeBaseOffsetOpt56 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;
INITIALIZE_PASS(RISCVMergeBaseOffsetOpt,DEBUG_TYPE,RISCV_MERGE_BASE_OFFSET_NAME,false,false)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.
foldOffset(MachineInstr & HiLUI,MachineInstr & LoADDI,MachineInstr & Tail,int64_t Offset)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
matchLargeOffset(MachineInstr & TailAdd,Register GAReg,int64_t & Offset)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
detectAndFoldOffset(MachineInstr & HiLUI,MachineInstr & LoADDI)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
runOnMachineFunction(MachineFunction & Fn)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.
createRISCVMergeBaseOffsetOptPass()285 FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() {
286 return new RISCVMergeBaseOffsetOpt();
287 }
288