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