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