LLVM  14.0.0git
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  void getAnalysisUsage(AnalysisUsage &AU) const override {
57  AU.setPreservesCFG();
59  }
60 
61  StringRef getPassName() const override {
63  }
64 
65 private:
67  std::set<MachineInstr *> DeadInstrs;
68 };
69 } // end anonymous namespace
70 
72 INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, DEBUG_TYPE,
73  RISCV_MERGE_BASE_OFFSET_NAME, false, false)
74 
75 // Detect the pattern:
76 // lui vreg1, %hi(s)
77 // addi vreg2, vreg1, %lo(s)
78 //
79 // Pattern only accepted if:
80 // 1) ADDI has only one use.
81 // 2) LUI has only one use; which is the ADDI.
82 // 3) Both ADDI and LUI have GlobalAddress type which indicates that these
83 // are generated from global address lowering.
84 // 4) Offset value in the Global Address is 0.
85 bool RISCVMergeBaseOffsetOpt::detectLuiAddiGlobal(MachineInstr &HiLUI,
86  MachineInstr *&LoADDI) {
87  if (HiLUI.getOpcode() != RISCV::LUI ||
88  HiLUI.getOperand(1).getTargetFlags() != RISCVII::MO_HI ||
89  HiLUI.getOperand(1).getType() != MachineOperand::MO_GlobalAddress ||
90  HiLUI.getOperand(1).getOffset() != 0 ||
91  !MRI->hasOneUse(HiLUI.getOperand(0).getReg()))
92  return false;
93  Register HiLuiDestReg = HiLUI.getOperand(0).getReg();
94  LoADDI = MRI->use_begin(HiLuiDestReg)->getParent();
95  if (LoADDI->getOpcode() != RISCV::ADDI ||
96  LoADDI->getOperand(2).getTargetFlags() != RISCVII::MO_LO ||
97  LoADDI->getOperand(2).getType() != MachineOperand::MO_GlobalAddress ||
98  LoADDI->getOperand(2).getOffset() != 0 ||
99  !MRI->hasOneUse(LoADDI->getOperand(0).getReg()))
100  return false;
101  return true;
102 }
103 
104 // Update the offset in HiLUI and LoADDI instructions.
105 // Delete the tail instruction and update all the uses to use the
106 // output from LoADDI.
107 void RISCVMergeBaseOffsetOpt::foldOffset(MachineInstr &HiLUI,
108  MachineInstr &LoADDI,
109  MachineInstr &Tail, int64_t Offset) {
110  // Put the offset back in HiLUI and the LoADDI
111  HiLUI.getOperand(1).setOffset(Offset);
112  LoADDI.getOperand(2).setOffset(Offset);
113  // Delete the tail instruction.
114  DeadInstrs.insert(&Tail);
115  MRI->replaceRegWith(Tail.getOperand(0).getReg(),
116  LoADDI.getOperand(0).getReg());
117  LLVM_DEBUG(dbgs() << " Merged offset " << Offset << " into base.\n"
118  << " " << HiLUI << " " << LoADDI;);
119 }
120 
121 // Detect patterns for large offsets that are passed into an ADD instruction.
122 //
123 // Base address lowering is of the form:
124 // HiLUI: lui vreg1, %hi(s)
125 // LoADDI: addi vreg2, vreg1, %lo(s)
126 // / \
127 // / \
128 // / \
129 // / The large offset can be of two forms: \
130 // 1) Offset that has non zero bits in lower 2) Offset that has non zero
131 // 12 bits and upper 20 bits bits in upper 20 bits only
132 // OffseLUI: lui vreg3, 4
133 // OffsetTail: addi voff, vreg3, 188 OffsetTail: lui voff, 128
134 // \ /
135 // \ /
136 // \ /
137 // \ /
138 // TailAdd: add vreg4, vreg2, voff
139 bool RISCVMergeBaseOffsetOpt::matchLargeOffset(MachineInstr &TailAdd,
140  Register GAReg,
141  int64_t &Offset) {
142  assert((TailAdd.getOpcode() == RISCV::ADD) && "Expected ADD instruction!");
143  Register Rs = TailAdd.getOperand(1).getReg();
144  Register Rt = TailAdd.getOperand(2).getReg();
145  Register Reg = Rs == GAReg ? Rt : Rs;
146 
147  // Can't fold if the register has more than one use.
148  if (!MRI->hasOneUse(Reg))
149  return false;
150  // This can point to an ADDI or a LUI:
151  MachineInstr &OffsetTail = *MRI->getVRegDef(Reg);
152  if (OffsetTail.getOpcode() == RISCV::ADDI) {
153  // The offset value has non zero bits in both %hi and %lo parts.
154  // Detect an ADDI that feeds from a LUI instruction.
155  MachineOperand &AddiImmOp = OffsetTail.getOperand(2);
156  if (AddiImmOp.getTargetFlags() != RISCVII::MO_None)
157  return false;
158  int64_t OffLo = AddiImmOp.getImm();
159  MachineInstr &OffsetLui =
160  *MRI->getVRegDef(OffsetTail.getOperand(1).getReg());
161  MachineOperand &LuiImmOp = OffsetLui.getOperand(1);
162  if (OffsetLui.getOpcode() != RISCV::LUI ||
163  LuiImmOp.getTargetFlags() != RISCVII::MO_None ||
164  !MRI->hasOneUse(OffsetLui.getOperand(0).getReg()))
165  return false;
166  int64_t OffHi = OffsetLui.getOperand(1).getImm();
167  Offset = (OffHi << 12) + OffLo;
168  LLVM_DEBUG(dbgs() << " Offset Instrs: " << OffsetTail
169  << " " << OffsetLui);
170  DeadInstrs.insert(&OffsetTail);
171  DeadInstrs.insert(&OffsetLui);
172  return true;
173  } else if (OffsetTail.getOpcode() == RISCV::LUI) {
174  // The offset value has all zero bits in the lower 12 bits. Only LUI
175  // exists.
176  LLVM_DEBUG(dbgs() << " Offset Instr: " << OffsetTail);
177  Offset = OffsetTail.getOperand(1).getImm() << 12;
178  DeadInstrs.insert(&OffsetTail);
179  return true;
180  }
181  return false;
182 }
183 
184 bool RISCVMergeBaseOffsetOpt::detectAndFoldOffset(MachineInstr &HiLUI,
185  MachineInstr &LoADDI) {
186  Register DestReg = LoADDI.getOperand(0).getReg();
187  assert(MRI->hasOneUse(DestReg) && "expected one use for LoADDI");
188  // LoADDI has only one use.
189  MachineInstr &Tail = *MRI->use_begin(DestReg)->getParent();
190  switch (Tail.getOpcode()) {
191  default:
192  LLVM_DEBUG(dbgs() << "Don't know how to get offset from this instr:"
193  << Tail);
194  return false;
195  case RISCV::ADDI: {
196  // Offset is simply an immediate operand.
197  int64_t Offset = Tail.getOperand(2).getImm();
198  LLVM_DEBUG(dbgs() << " Offset Instr: " << Tail);
199  foldOffset(HiLUI, LoADDI, Tail, Offset);
200  return true;
201  }
202  case RISCV::ADD: {
203  // The offset is too large to fit in the immediate field of ADDI.
204  // This can be in two forms:
205  // 1) LUI hi_Offset followed by:
206  // ADDI lo_offset
207  // This happens in case the offset has non zero bits in
208  // both hi 20 and lo 12 bits.
209  // 2) LUI (offset20)
210  // This happens in case the lower 12 bits of the offset are zeros.
211  int64_t Offset;
212  if (!matchLargeOffset(Tail, DestReg, Offset))
213  return false;
214  foldOffset(HiLUI, LoADDI, Tail, Offset);
215  return true;
216  }
217  case RISCV::LB:
218  case RISCV::LH:
219  case RISCV::LW:
220  case RISCV::LBU:
221  case RISCV::LHU:
222  case RISCV::LWU:
223  case RISCV::LD:
224  case RISCV::FLH:
225  case RISCV::FLW:
226  case RISCV::FLD:
227  case RISCV::SB:
228  case RISCV::SH:
229  case RISCV::SW:
230  case RISCV::SD:
231  case RISCV::FSH:
232  case RISCV::FSW:
233  case RISCV::FSD: {
234  // Transforms the sequence: Into:
235  // HiLUI: lui vreg1, %hi(foo) ---> lui vreg1, %hi(foo+8)
236  // LoADDI: addi vreg2, vreg1, %lo(foo) ---> lw vreg3, lo(foo+8)(vreg1)
237  // Tail: lw vreg3, 8(vreg2)
238  if (Tail.getOperand(1).isFI())
239  return false;
240  // Register defined by LoADDI should be used in the base part of the
241  // load\store instruction. Otherwise, no folding possible.
242  Register BaseAddrReg = Tail.getOperand(1).getReg();
243  if (DestReg != BaseAddrReg)
244  return false;
245  MachineOperand &TailImmOp = Tail.getOperand(2);
246  int64_t Offset = TailImmOp.getImm();
247  // Update the offsets in global address lowering.
248  HiLUI.getOperand(1).setOffset(Offset);
249  // Update the immediate in the Tail instruction to add the offset.
250  Tail.RemoveOperand(2);
251  MachineOperand &ImmOp = LoADDI.getOperand(2);
252  ImmOp.setOffset(Offset);
253  Tail.addOperand(ImmOp);
254  // Update the base reg in the Tail instruction to feed from LUI.
255  // Output of HiLUI is only used in LoADDI, no need to use
256  // MRI->replaceRegWith().
257  Tail.getOperand(1).setReg(HiLUI.getOperand(0).getReg());
258  DeadInstrs.insert(&LoADDI);
259  return true;
260  }
261  }
262  return false;
263 }
264 
265 bool RISCVMergeBaseOffsetOpt::runOnMachineFunction(MachineFunction &Fn) {
266  if (skipFunction(Fn.getFunction()))
267  return false;
268 
269  bool MadeChange = false;
270  DeadInstrs.clear();
271  MRI = &Fn.getRegInfo();
272  for (MachineBasicBlock &MBB : Fn) {
273  LLVM_DEBUG(dbgs() << "MBB: " << MBB.getName() << "\n");
274  for (MachineInstr &HiLUI : MBB) {
275  MachineInstr *LoADDI = nullptr;
276  if (!detectLuiAddiGlobal(HiLUI, LoADDI))
277  continue;
278  LLVM_DEBUG(dbgs() << " Found lowered global address with one use: "
279  << *LoADDI->getOperand(2).getGlobal() << "\n");
280  // If the use count is only one, merge the offset
281  MadeChange |= detectAndFoldOffset(HiLUI, *LoADDI);
282  }
283  }
284  // Delete dead instructions.
285  for (auto *MI : DeadInstrs)
286  MI->eraseFromParent();
287  return MadeChange;
288 }
289 
290 /// Returns an instance of the Merge Base Offset Optimization pass.
292  return new RISCVMergeBaseOffsetOpt();
293 }
DEBUG_TYPE
#define DEBUG_TYPE
Definition: RISCVMergeBaseOffset.cpp:35
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::RISCVII::MO_LO
@ MO_LO
Definition: RISCVBaseInfo.h:155
llvm::MachineOperand::getGlobal
const GlobalValue * getGlobal() const
Definition: MachineOperand.h:563
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::ARM_MB::LD
@ LD
Definition: ARMBaseInfo.h:72
llvm::RISCVII::MO_HI
@ MO_HI
Definition: RISCVBaseInfo.h:156
llvm::createRISCVMergeBaseOffsetOptPass
FunctionPass * createRISCVMergeBaseOffsetOptPass()
Returns an instance of the Merge Base Offset Optimization pass.
Definition: RISCVMergeBaseOffset.cpp:291
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::RISCVII::MO_None
@ MO_None
Definition: RISCVBaseInfo.h:152
llvm::MachineFunctionProperties::Property::IsSSA
@ IsSSA
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:636
llvm::MachineOperand::MO_GlobalAddress
@ MO_GlobalAddress
Address of a global value.
Definition: MachineOperand.h:62
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:537
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:169
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:400
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:238
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
Passes.h
llvm::MachineOperand::getTargetFlags
unsigned getTargetFlags() const
Definition: MachineOperand.h:221
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
RISCV.h
llvm::MachineFunction
Definition: MachineFunction.h:230
TargetOptions.h
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:489
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
llvm::MachineRegisterInfo::use_begin
use_iterator use_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:464
llvm::X86ISD::FLD
@ FLD
This instruction implements an extending load to FP stack slots.
Definition: X86ISelLowering.h:840
RISCV_MERGE_BASE_OFFSET_NAME
#define RISCV_MERGE_BASE_OFFSET_NAME
Definition: RISCVMergeBaseOffset.cpp:36
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineRegisterInfo::replaceRegWith
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Definition: MachineRegisterInfo.cpp:380
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:592
INITIALIZE_PASS
INITIALIZE_PASS(RISCVMergeBaseOffsetOpt, DEBUG_TYPE, RISCV_MERGE_BASE_OFFSET_NAME, false, false) bool RISCVMergeBaseOffsetOpt
Definition: RISCVMergeBaseOffset.cpp:72
llvm::ISD::ADD
@ ADD
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:239
llvm::MachineRegisterInfo::hasOneUse
bool hasOneUse(Register RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
Definition: MachineRegisterInfo.h:510
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
TargetRegistry.h
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:314
Debug.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
RISCVTargetMachine.h
llvm::MachineOperand::setOffset
void setOffset(int64_t Offset)
Definition: MachineOperand.h:670