RISCVMergeBaseOffset.cpp revision 360784 
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>
33using namespace llvm;
34
35#define DEBUG_TYPE "riscv-merge-base-offset"
36#define RISCV_MERGE_BASE_OFFSET_NAME "RISCV Merge Base Offset"
37namespace {
38
39struct 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
60private:
61  MachineRegisterInfo *MRI;
62  std::set<MachineInstr *> DeadInstrs;
63};
64} // end anonymous namespace
65
66char RISCVMergeBaseOffsetOpt::ID = 0;
67INITIALIZE_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.
80bool 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.
102void 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
134bool 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
179bool 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
258bool 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.
283FunctionPass *llvm::createRISCVMergeBaseOffsetOptPass() {
284  return new RISCVMergeBaseOffsetOpt();
285}
286