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.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "RISCV.h"
15 #include "RISCVTargetMachine.h"
16 #include "llvm/CodeGen/MachineFunctionPass.h"
17 #include "llvm/CodeGen/Passes.h"
18 #include "llvm/MC/TargetRegistry.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Target/TargetOptions.h"
21 #include <optional>
22 #include <set>
23 using namespace llvm;
24 
25 #define DEBUG_TYPE "riscv-merge-base-offset"
26 #define RISCV_MERGE_BASE_OFFSET_NAME "RISC-V Merge Base Offset"
27 namespace {
28 
29 class RISCVMergeBaseOffsetOpt : public MachineFunctionPass {
30   const RISCVSubtarget *ST = nullptr;
31   MachineRegisterInfo *MRI;
32 
33 public:
34   static char ID;
35   bool runOnMachineFunction(MachineFunction &Fn) override;
36   bool detectFoldable(MachineInstr &Hi, MachineInstr *&Lo);
37 
38   bool detectAndFoldOffset(MachineInstr &Hi, MachineInstr &Lo);
39   void foldOffset(MachineInstr &Hi, MachineInstr &Lo, MachineInstr &Tail,
40                   int64_t Offset);
41   bool foldLargeOffset(MachineInstr &Hi, MachineInstr &Lo,
42                        MachineInstr &TailAdd, Register GSReg);
43   bool foldShiftedOffset(MachineInstr &Hi, MachineInstr &Lo,
44                          MachineInstr &TailShXAdd, Register GSReg);
45 
46   bool foldIntoMemoryOps(MachineInstr &Hi, MachineInstr &Lo);
47 
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 } // end anonymous namespace
65 
66 char RISCVMergeBaseOffsetOpt::ID = 0;
67 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, DEBUG_TYPE,
68                 RISCV_MERGE_BASE_OFFSET_NAME, false, false)
69 
70 // Detect either of the patterns:
71 //
72 // 1. (medlow pattern):
73 //   lui   vreg1, %hi(s)
74 //   addi  vreg2, vreg1, %lo(s)
75 //
76 // 2. (medany pattern):
77 // .Lpcrel_hi1:
78 //   auipc vreg1, %pcrel_hi(s)
79 //   addi  vreg2, vreg1, %pcrel_lo(.Lpcrel_hi1)
80 //
81 // The pattern is only accepted if:
82 //    1) The first instruction has only one use, which is the ADDI.
83 //    2) The address operands have the appropriate type, reflecting the
84 //       lowering of a global address or constant pool using medlow or medany.
85 //    3) The offset value in the Global Address or Constant Pool is 0.
86 bool RISCVMergeBaseOffsetOpt::detectFoldable(MachineInstr &Hi,
87                                              MachineInstr *&Lo) {
88   if (Hi.getOpcode() != RISCV::LUI && Hi.getOpcode() != RISCV::AUIPC)
89     return false;
90 
91   const MachineOperand &HiOp1 = Hi.getOperand(1);
92   unsigned ExpectedFlags =
93       Hi.getOpcode() == RISCV::AUIPC ? RISCVII::MO_PCREL_HI : RISCVII::MO_HI;
94   if (HiOp1.getTargetFlags() != ExpectedFlags)
95     return false;
96 
97   if (!(HiOp1.isGlobal() || HiOp1.isCPI()) || HiOp1.getOffset() != 0)
98     return false;
99 
100   Register HiDestReg = Hi.getOperand(0).getReg();
101   if (!MRI->hasOneUse(HiDestReg))
102     return false;
103 
104   Lo = &*MRI->use_instr_begin(HiDestReg);
105   if (Lo->getOpcode() != RISCV::ADDI)
106     return false;
107 
108   const MachineOperand &LoOp2 = Lo->getOperand(2);
109   if (Hi.getOpcode() == RISCV::LUI) {
110     if (LoOp2.getTargetFlags() != RISCVII::MO_LO ||
111         !(LoOp2.isGlobal() || LoOp2.isCPI()) || LoOp2.getOffset() != 0)
112       return false;
113   } else {
114     assert(Hi.getOpcode() == RISCV::AUIPC);
115     if (LoOp2.getTargetFlags() != RISCVII::MO_PCREL_LO ||
116         LoOp2.getType() != MachineOperand::MO_MCSymbol)
117       return false;
118   }
119 
120   if (HiOp1.isGlobal()) {
121     LLVM_DEBUG(dbgs() << "  Found lowered global address: "
122                       << *HiOp1.getGlobal() << "\n");
123   } else {
124     assert(HiOp1.isCPI());
125     LLVM_DEBUG(dbgs() << "  Found lowered constant pool: " << HiOp1.getIndex()
126                       << "\n");
127   }
128 
129   return true;
130 }
131 
132 // Update the offset in Hi and Lo instructions.
133 // Delete the tail instruction and update all the uses to use the
134 // output from Lo.
135 void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &Hi, MachineInstr &Lo,
136                                          MachineInstr &Tail, int64_t Offset) {
137   assert(isInt<32>(Offset) && "Unexpected offset");
138   // Put the offset back in Hi and the Lo
139   Hi.getOperand(1).setOffset(Offset);
140   if (Hi.getOpcode() != RISCV::AUIPC)
141     Lo.getOperand(2).setOffset(Offset);
142   // Delete the tail instruction.
143   MRI->constrainRegClass(Lo.getOperand(0).getReg(),
144                          MRI->getRegClass(Tail.getOperand(0).getReg()));
145   MRI->replaceRegWith(Tail.getOperand(0).getReg(), Lo.getOperand(0).getReg());
146   Tail.eraseFromParent();
147   LLVM_DEBUG(dbgs() << "  Merged offset " << Offset << " into base.\n"
148                     << "     " << Hi << "     " << Lo;);
149 }
150 
151 // Detect patterns for large offsets that are passed into an ADD instruction.
152 // If the pattern is found, updates the offset in Hi and Lo instructions
153 // and deletes TailAdd and the instructions that produced the offset.
154 //
155 //                     Base address lowering is of the form:
156 //                       Hi:  lui   vreg1, %hi(s)
157 //                       Lo:  addi  vreg2, vreg1, %lo(s)
158 //                       /                                  \
159 //                      /                                    \
160 //                     /                                      \
161 //                    /  The large offset can be of two forms: \
162 //  1) Offset that has non zero bits in lower      2) Offset that has non zero
163 //     12 bits and upper 20 bits                      bits in upper 20 bits only
164 //   OffseLUI: lui   vreg3, 4
165 // OffsetTail: addi  voff, vreg3, 188                OffsetTail: lui  voff, 128
166 //                    \                                        /
167 //                     \                                      /
168 //                      \                                    /
169 //                       \                                  /
170 //                         TailAdd: add  vreg4, vreg2, voff
171 bool RISCVMergeBaseOffsetOpt::foldLargeOffset(MachineInstr &Hi,
172                                               MachineInstr &Lo,
173                                               MachineInstr &TailAdd,
174                                               Register GAReg) {
175   assert((TailAdd.getOpcode() == RISCV::ADD) && "Expected ADD instruction!");
176   Register Rs = TailAdd.getOperand(1).getReg();
177   Register Rt = TailAdd.getOperand(2).getReg();
178   Register Reg = Rs == GAReg ? Rt : Rs;
179 
180   // Can't fold if the register has more than one use.
181   if (!MRI->hasOneUse(Reg))
182     return false;
183   // This can point to an ADDI(W) or a LUI:
184   MachineInstr &OffsetTail = *MRI->getVRegDef(Reg);
185   if (OffsetTail.getOpcode() == RISCV::ADDI ||
186       OffsetTail.getOpcode() == RISCV::ADDIW) {
187     // The offset value has non zero bits in both %hi and %lo parts.
188     // Detect an ADDI that feeds from a LUI instruction.
189     MachineOperand &AddiImmOp = OffsetTail.getOperand(2);
190     if (AddiImmOp.getTargetFlags() != RISCVII::MO_None)
191       return false;
192     int64_t OffLo = AddiImmOp.getImm();
193     MachineInstr &OffsetLui =
194         *MRI->getVRegDef(OffsetTail.getOperand(1).getReg());
195     MachineOperand &LuiImmOp = OffsetLui.getOperand(1);
196     if (OffsetLui.getOpcode() != RISCV::LUI ||
197         LuiImmOp.getTargetFlags() != RISCVII::MO_None ||
198         !MRI->hasOneUse(OffsetLui.getOperand(0).getReg()))
199       return false;
200     int64_t Offset = SignExtend64<32>(LuiImmOp.getImm() << 12);
201     Offset += OffLo;
202     // RV32 ignores the upper 32 bits. ADDIW sign extends the result.
203     if (!ST->is64Bit() || OffsetTail.getOpcode() == RISCV::ADDIW)
204        Offset = SignExtend64<32>(Offset);
205     // We can only fold simm32 offsets.
206     if (!isInt<32>(Offset))
207       return false;
208     LLVM_DEBUG(dbgs() << "  Offset Instrs: " << OffsetTail
209                       << "                 " << OffsetLui);
210     foldOffset(Hi, Lo, TailAdd, Offset);
211     OffsetTail.eraseFromParent();
212     OffsetLui.eraseFromParent();
213     return true;
214   } else if (OffsetTail.getOpcode() == RISCV::LUI) {
215     // The offset value has all zero bits in the lower 12 bits. Only LUI
216     // exists.
217     LLVM_DEBUG(dbgs() << "  Offset Instr: " << OffsetTail);
218     int64_t Offset = SignExtend64<32>(OffsetTail.getOperand(1).getImm() << 12);
219     foldOffset(Hi, Lo, TailAdd, Offset);
220     OffsetTail.eraseFromParent();
221     return true;
222   }
223   return false;
224 }
225 
226 // Detect patterns for offsets that are passed into a SHXADD instruction.
227 // The offset has 1, 2, or 3 trailing zeros and fits in simm13, simm14, simm15.
228 // The constant is created with addi voff, x0, C, and shXadd is used to
229 // fill insert the trailing zeros and do the addition.
230 // If the pattern is found, updates the offset in Hi and Lo instructions
231 // and deletes TailShXAdd and the instructions that produced the offset.
232 //
233 // Hi:         lui     vreg1, %hi(s)
234 // Lo:         addi    vreg2, vreg1, %lo(s)
235 // OffsetTail: addi    voff, x0, C
236 // TailAdd:    shXadd  vreg4, voff, vreg2
237 bool RISCVMergeBaseOffsetOpt::foldShiftedOffset(MachineInstr &Hi,
238                                                 MachineInstr &Lo,
239                                                 MachineInstr &TailShXAdd,
240                                                 Register GAReg) {
241   assert((TailShXAdd.getOpcode() == RISCV::SH1ADD ||
242           TailShXAdd.getOpcode() == RISCV::SH2ADD ||
243           TailShXAdd.getOpcode() == RISCV::SH3ADD) &&
244          "Expected SHXADD instruction!");
245 
246   // The first source is the shifted operand.
247   Register Rs1 = TailShXAdd.getOperand(1).getReg();
248 
249   if (GAReg != TailShXAdd.getOperand(2).getReg())
250     return false;
251 
252   // Can't fold if the register has more than one use.
253   if (!MRI->hasOneUse(Rs1))
254     return false;
255   // This can point to an ADDI X0, C.
256   MachineInstr &OffsetTail = *MRI->getVRegDef(Rs1);
257   if (OffsetTail.getOpcode() != RISCV::ADDI)
258     return false;
259   if (!OffsetTail.getOperand(1).isReg() ||
260       OffsetTail.getOperand(1).getReg() != RISCV::X0 ||
261       !OffsetTail.getOperand(2).isImm())
262     return false;
263 
264   int64_t Offset = OffsetTail.getOperand(2).getImm();
265   assert(isInt<12>(Offset) && "Unexpected offset");
266 
267   unsigned ShAmt;
268   switch (TailShXAdd.getOpcode()) {
269   default: llvm_unreachable("Unexpected opcode");
270   case RISCV::SH1ADD: ShAmt = 1; break;
271   case RISCV::SH2ADD: ShAmt = 2; break;
272   case RISCV::SH3ADD: ShAmt = 3; break;
273   }
274 
275   Offset = (uint64_t)Offset << ShAmt;
276 
277   LLVM_DEBUG(dbgs() << "  Offset Instr: " << OffsetTail);
278   foldOffset(Hi, Lo, TailShXAdd, Offset);
279   OffsetTail.eraseFromParent();
280   return true;
281 }
282 
283 bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &Hi,
284                                                   MachineInstr &Lo) {
285   Register DestReg = Lo.getOperand(0).getReg();
286 
287   // Look for arithmetic instructions we can get an offset from.
288   // We might be able to remove the arithmetic instructions by folding the
289   // offset into the LUI+ADDI.
290   if (!MRI->hasOneUse(DestReg))
291     return false;
292 
293   // Lo has only one use.
294   MachineInstr &Tail = *MRI->use_instr_begin(DestReg);
295   switch (Tail.getOpcode()) {
296   default:
297     LLVM_DEBUG(dbgs() << "Don't know how to get offset from this instr:"
298                       << Tail);
299     break;
300   case RISCV::ADDI: {
301     // Offset is simply an immediate operand.
302     int64_t Offset = Tail.getOperand(2).getImm();
303 
304     // We might have two ADDIs in a row.
305     Register TailDestReg = Tail.getOperand(0).getReg();
306     if (MRI->hasOneUse(TailDestReg)) {
307       MachineInstr &TailTail = *MRI->use_instr_begin(TailDestReg);
308       if (TailTail.getOpcode() == RISCV::ADDI) {
309         Offset += TailTail.getOperand(2).getImm();
310         LLVM_DEBUG(dbgs() << "  Offset Instrs: " << Tail << TailTail);
311         foldOffset(Hi, Lo, TailTail, Offset);
312         Tail.eraseFromParent();
313         return true;
314       }
315     }
316 
317     LLVM_DEBUG(dbgs() << "  Offset Instr: " << Tail);
318     foldOffset(Hi, Lo, Tail, Offset);
319     return true;
320   }
321   case RISCV::ADD:
322     // The offset is too large to fit in the immediate field of ADDI.
323     // This can be in two forms:
324     // 1) LUI hi_Offset followed by:
325     //    ADDI lo_offset
326     //    This happens in case the offset has non zero bits in
327     //    both hi 20 and lo 12 bits.
328     // 2) LUI (offset20)
329     //    This happens in case the lower 12 bits of the offset are zeros.
330     return foldLargeOffset(Hi, Lo, Tail, DestReg);
331   case RISCV::SH1ADD:
332   case RISCV::SH2ADD:
333   case RISCV::SH3ADD:
334     // The offset is too large to fit in the immediate field of ADDI.
335     // It may be encoded as (SH2ADD (ADDI X0, C), DestReg) or
336     // (SH3ADD (ADDI X0, C), DestReg).
337     return foldShiftedOffset(Hi, Lo, Tail, DestReg);
338   }
339 
340   return false;
341 }
342 
343 bool RISCVMergeBaseOffsetOpt::foldIntoMemoryOps(MachineInstr &Hi,
344                                                 MachineInstr &Lo) {
345   Register DestReg = Lo.getOperand(0).getReg();
346 
347   // If all the uses are memory ops with the same offset, we can transform:
348   //
349   // 1. (medlow pattern):
350   // Hi:   lui vreg1, %hi(foo)          --->  lui vreg1, %hi(foo+8)
351   // Lo:   addi vreg2, vreg1, %lo(foo)  --->  lw vreg3, lo(foo+8)(vreg1)
352   // Tail: lw vreg3, 8(vreg2)
353   //
354   // 2. (medany pattern):
355   // Hi: 1:auipc vreg1, %pcrel_hi(s)         ---> auipc vreg1, %pcrel_hi(foo+8)
356   // Lo:   addi  vreg2, vreg1, %pcrel_lo(1b) ---> lw vreg3, %pcrel_lo(1b)(vreg1)
357   // Tail: lw vreg3, 8(vreg2)
358 
359   std::optional<int64_t> CommonOffset;
360   for (const MachineInstr &UseMI : MRI->use_instructions(DestReg)) {
361     switch (UseMI.getOpcode()) {
362     default:
363       LLVM_DEBUG(dbgs() << "Not a load or store instruction: " << UseMI);
364       return false;
365     case RISCV::LB:
366     case RISCV::LH:
367     case RISCV::LW:
368     case RISCV::LBU:
369     case RISCV::LHU:
370     case RISCV::LWU:
371     case RISCV::LD:
372     case RISCV::FLH:
373     case RISCV::FLW:
374     case RISCV::FLD:
375     case RISCV::SB:
376     case RISCV::SH:
377     case RISCV::SW:
378     case RISCV::SD:
379     case RISCV::FSH:
380     case RISCV::FSW:
381     case RISCV::FSD: {
382       if (UseMI.getOperand(1).isFI())
383         return false;
384       // Register defined by Lo should not be the value register.
385       if (DestReg == UseMI.getOperand(0).getReg())
386         return false;
387       assert(DestReg == UseMI.getOperand(1).getReg() &&
388              "Expected base address use");
389       // All load/store instructions must use the same offset.
390       int64_t Offset = UseMI.getOperand(2).getImm();
391       if (CommonOffset && Offset != CommonOffset)
392         return false;
393       CommonOffset = Offset;
394     }
395     }
396   }
397 
398   // We found a common offset.
399   // Update the offsets in global address lowering.
400   // We may have already folded some arithmetic so we need to add to any
401   // existing offset.
402   int64_t NewOffset = Hi.getOperand(1).getOffset() + *CommonOffset;
403   // RV32 ignores the upper 32 bits.
404   if (!ST->is64Bit())
405     NewOffset = SignExtend64<32>(NewOffset);
406   // We can only fold simm32 offsets.
407   if (!isInt<32>(NewOffset))
408     return false;
409 
410   Hi.getOperand(1).setOffset(NewOffset);
411   MachineOperand &ImmOp = Lo.getOperand(2);
412   if (Hi.getOpcode() != RISCV::AUIPC)
413     ImmOp.setOffset(NewOffset);
414 
415   // Update the immediate in the load/store instructions to add the offset.
416   for (MachineInstr &UseMI :
417        llvm::make_early_inc_range(MRI->use_instructions(DestReg))) {
418     UseMI.removeOperand(2);
419     UseMI.addOperand(ImmOp);
420     // Update the base reg in the Tail instruction to feed from LUI.
421     // Output of Hi is only used in Lo, no need to use MRI->replaceRegWith().
422     UseMI.getOperand(1).setReg(Hi.getOperand(0).getReg());
423   }
424 
425   Lo.eraseFromParent();
426   return true;
427 }
428 
429 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) {
430   if (skipFunction(Fn.getFunction()))
431     return false;
432 
433   ST = &Fn.getSubtarget<RISCVSubtarget>();
434 
435   bool MadeChange = false;
436   MRI = &Fn.getRegInfo();
437   for (MachineBasicBlock &MBB : Fn) {
438     LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
439     for (MachineInstr &Hi : MBB) {
440       MachineInstr *Lo = nullptr;
441       if (!detectFoldable(Hi, Lo))
442         continue;
443       MadeChange |= detectAndFoldOffset(Hi, *Lo);
444       MadeChange |= foldIntoMemoryOps(Hi, *Lo);
445     }
446   }
447 
448   return MadeChange;
449 }
450 
451 /// Returns an instance of the Merge Base Offset Optimization pass.
452 FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() {
453   return new RISCVMergeBaseOffsetOpt();
454 }
455