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);
49   RISCVMergeBaseOffsetOpt() : MachineFunctionPass(ID) {}
50 
51   MachineFunctionProperties getRequiredProperties() const override {
52     return MachineFunctionProperties().set(
53         MachineFunctionProperties::Property::IsSSA);
54   }
55 
56   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;
67 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, "riscv-merge-base-offset",
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.
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
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 
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::FLW:
220   case RISCV::FLD:
221   case RISCV::SB:
222   case RISCV::SH:
223   case RISCV::SW:
224   case RISCV::SD:
225   case RISCV::FSW:
226   case RISCV::FSD: {
227     // Transforms the sequence:            Into:
228     // HiLUI:  lui vreg1, %hi(foo)          --->  lui vreg1, %hi(foo+8)
229     // LoADDI: addi vreg2, vreg1, %lo(foo)  --->  lw vreg3, lo(foo+8)(vreg1)
230     // Tail:   lw vreg3, 8(vreg2)
231     if (Tail.getOperand(1).isFI())
232       return false;
233     // Register defined by LoADDI should be used in the base part of the
234     // load\store instruction. Otherwise, no folding possible.
235     Register BaseAddrReg = Tail.getOperand(1).getReg();
236     if (DestReg != BaseAddrReg)
237       return false;
238     MachineOperand &TailImmOp = Tail.getOperand(2);
239     int64_t Offset = TailImmOp.getImm();
240     // Update the offsets in global address lowering.
241     HiLUI.getOperand(1).setOffset(Offset);
242     // Update the immediate in the Tail instruction to add the offset.
243     Tail.RemoveOperand(2);
244     MachineOperand &ImmOp = LoADDI.getOperand(2);
245     ImmOp.setOffset(Offset);
246     Tail.addOperand(ImmOp);
247     // Update the base reg in the Tail instruction to feed from LUI.
248     // Output of HiLUI is only used in LoADDI, no need to use
249     // MRI->replaceRegWith().
250     Tail.getOperand(1).setReg(HiLUI.getOperand(0).getReg());
251     DeadInstrs.insert(&LoADDI);
252     return true;
253   } break;
254   }
255   return false;
256 }
257 
258 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) {
259   if (skipFunction(Fn.getFunction()))
260     return false;
261 
262   DeadInstrs.clear();
263   MRI = &Fn.getRegInfo();
264   for (MachineBasicBlock &MBB : Fn) {
265     LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
266     for (MachineInstr &HiLUI : MBB) {
267       MachineInstr *LoADDI = nullptr;
268       if (!detectLuiAddiGlobal(HiLUI, LoADDI))
269         continue;
270       LLVM_DEBUG(dbgs() << "  Found lowered global address with one use: "
271                         << *LoADDI->getOperand(2).getGlobal() << "\n");
272       // If the use count is only one, merge the offset
273       detectAndFoldOffset(HiLUI, *LoADDI);
274     }
275   }
276   // Delete dead instructions.
277   for (auto *MI : DeadInstrs)
278     MI->eraseFromParent();
279   return true;
280 }
281 
282 /// Returns an instance of the Merge Base Offset Optimization pass.
283 FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() {
284   return new RISCVMergeBaseOffsetOpt();
285 }
286