LLVM  10.0.0svn
RISCVMergeBaseOffset.cpp
Go to the documentation of this file.
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"
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 {
54  }
55 
56  StringRef getPassName() const override {
58  }
59 
60 private:
62  std::set<MachineInstr *> DeadInstrs;
63 };
64 } // end anonymous namespace
65 
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.
284  return new RISCVMergeBaseOffsetOpt();
285 }
unsigned getTargetFlags() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned Reg
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
#define RISCV_MERGE_BASE_OFFSET_NAME
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:200
Address of a global value.
unsigned const MachineRegisterInfo * MRI
This instruction implements an extending load to FP stack slots.
const GlobalValue * getGlobal() const
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
void setOffset(int64_t Offset)
MachineOperand class - Representation of each machine instruction operand.
INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, "riscv-merge-base-offset", RISCV_MERGE_BASE_OFFSET_NAME, false, false) bool RISCVMergeBaseOffsetOpt
int64_t getImm() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
FunctionPass * createRISCVMergeBaseOffsetOptPass()
Returns an instance of the Merge Base Offset Optimization pass.
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
Properties which a MachineFunction may have at a given point in time.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19