1//===- MipsOptimizePICCall.cpp - Optimize PIC Calls -----------------------===//
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// This pass eliminates unnecessary instructions that set up $gp and replace
10// instructions that load target function addresses with copy instructions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "MCTargetDesc/MipsBaseInfo.h"
15#include "Mips.h"
16#include "MipsRegisterInfo.h"
17#include "MipsSubtarget.h"
18#include "llvm/ADT/PointerUnion.h"
19#include "llvm/ADT/ScopedHashTable.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineDominators.h"
23#include "llvm/CodeGen/MachineFunction.h"
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include "llvm/CodeGen/MachineInstr.h"
26#include "llvm/CodeGen/MachineInstrBuilder.h"
27#include "llvm/CodeGen/MachineOperand.h"
28#include "llvm/CodeGen/MachineRegisterInfo.h"
29#include "llvm/CodeGen/TargetInstrInfo.h"
30#include "llvm/CodeGen/TargetOpcodes.h"
31#include "llvm/CodeGen/TargetRegisterInfo.h"
32#include "llvm/CodeGen/TargetSubtargetInfo.h"
33#include "llvm/CodeGenTypes/MachineValueType.h"
34#include "llvm/Support/Allocator.h"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Support/RecyclingAllocator.h"
37#include <cassert>
38#include <utility>
39
40using namespace llvm;
41
42#define DEBUG_TYPE "optimize-mips-pic-call"
43
44namespace {
45
46using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>;
47using CntRegP = std::pair<unsigned, unsigned>;
48using AllocatorTy = RecyclingAllocator<BumpPtrAllocator,
49 ScopedHashTableVal<ValueType, CntRegP>>;
50using ScopedHTType = ScopedHashTable<ValueType, CntRegP,
51 DenseMapInfo<ValueType>, AllocatorTy>;
52
53class MBBInfo {
54public:
55 MBBInfo(MachineDomTreeNode *N);
56
57 const MachineDomTreeNode *getNode() const;
58 bool isVisited() const;
59 void preVisit(ScopedHTType &ScopedHT);
60 void postVisit();
61
62private:
63 MachineDomTreeNode *Node;
64 ScopedHTType::ScopeTy *HTScope;
65};
66
67class OptimizePICCall : public MachineFunctionPass {
68public:
69 OptimizePICCall() : MachineFunctionPass(ID) {}
70
71 StringRef getPassName() const override { return "Mips OptimizePICCall"; }
72
73 bool runOnMachineFunction(MachineFunction &F) override;
74
75 void getAnalysisUsage(AnalysisUsage &AU) const override {
76 AU.addRequired<MachineDominatorTreeWrapperPass>();
77 MachineFunctionPass::getAnalysisUsage(AU);
78 }
79
80private:
81 /// Visit MBB.
82 bool visitNode(MBBInfo &MBBI);
83
84 /// Test if MI jumps to a function via a register.
85 ///
86 /// Also, return the virtual register containing the target function's address
87 /// and the underlying object in Reg and Val respectively, if the function's
88 /// address can be resolved lazily.
89 bool isCallViaRegister(MachineInstr &MI, unsigned &Reg,
90 ValueType &Val) const;
91
92 /// Return the number of instructions that dominate the current
93 /// instruction and load the function address from object Entry.
94 unsigned getCount(ValueType Entry);
95
96 /// Return the destination virtual register of the last instruction
97 /// that loads from object Entry.
98 unsigned getReg(ValueType Entry);
99
100 /// Update ScopedHT.
101 void incCntAndSetReg(ValueType Entry, unsigned Reg);
102
103 ScopedHTType ScopedHT;
104
105 static char ID;
106};
107
108} // end of anonymous namespace
109
110char OptimizePICCall::ID = 0;
111
112/// Return the first MachineOperand of MI if it is a used virtual register.
113static MachineOperand *getCallTargetRegOpnd(MachineInstr &MI) {
114 if (MI.getNumOperands() == 0)
115 return nullptr;
116
117 MachineOperand &MO = MI.getOperand(i: 0);
118
119 if (!MO.isReg() || !MO.isUse() || !MO.getReg().isVirtual())
120 return nullptr;
121
122 return &MO;
123}
124
125/// Return type of register Reg.
126static MVT::SimpleValueType getRegTy(unsigned Reg, MachineFunction &MF) {
127 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
128 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(Reg);
129 assert(TRI.legalclasstypes_end(*RC) - TRI.legalclasstypes_begin(*RC) == 1);
130 return *TRI.legalclasstypes_begin(RC: *RC);
131}
132
133/// Do the following transformation:
134///
135/// jalr $vreg
136/// =>
137/// copy $t9, $vreg
138/// jalr $t9
139static void setCallTargetReg(MachineBasicBlock *MBB,
140 MachineBasicBlock::iterator I) {
141 MachineFunction &MF = *MBB->getParent();
142 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
143 Register SrcReg = I->getOperand(i: 0).getReg();
144 MCRegister DstReg = MF.getSubtarget<MipsSubtarget>().getABI().getTempReg(
145 I: 9, Is64Bit: getRegTy(Reg: SrcReg, MF) != MVT::i32);
146 BuildMI(BB&: *MBB, I, MIMD: I->getDebugLoc(), MCID: TII.get(Opcode: TargetOpcode::COPY), DestReg: DstReg)
147 .addReg(RegNo: SrcReg);
148 I->getOperand(i: 0).setReg(DstReg);
149}
150
151/// Search MI's operands for register GP and erase it.
152static bool eraseGPOpnd(const MipsOptions &CLOpts, MachineInstr &MI) {
153 if (!CLOpts.erase_gp_opnd)
154 return false;
155
156 MachineFunction &MF = *MI.getParent()->getParent();
157 MVT::SimpleValueType Ty = getRegTy(Reg: MI.getOperand(i: 0).getReg(), MF);
158 unsigned Reg = Ty == MVT::i32 ? Mips::GP : Mips::GP_64;
159
160 for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
161 MachineOperand &MO = MI.getOperand(i: I);
162 if (MO.isReg() && MO.getReg() == Reg) {
163 MI.removeOperand(OpNo: I);
164 return true;
165 }
166 }
167
168 llvm_unreachable(nullptr);
169}
170
171MBBInfo::MBBInfo(MachineDomTreeNode *N) : Node(N), HTScope(nullptr) {}
172
173const MachineDomTreeNode *MBBInfo::getNode() const { return Node; }
174
175bool MBBInfo::isVisited() const { return HTScope; }
176
177void MBBInfo::preVisit(ScopedHTType &ScopedHT) {
178 HTScope = new ScopedHTType::ScopeTy(ScopedHT);
179}
180
181void MBBInfo::postVisit() {
182 delete HTScope;
183}
184
185// OptimizePICCall methods.
186bool OptimizePICCall::runOnMachineFunction(MachineFunction &F) {
187 if (F.getSubtarget<MipsSubtarget>().inMips16Mode())
188 return false;
189
190 // Do a pre-order traversal of the dominator tree.
191 MachineDominatorTree *MDT =
192 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
193 bool Changed = false;
194
195 SmallVector<MBBInfo, 8> WorkList(1, MBBInfo(MDT->getRootNode()));
196
197 while (!WorkList.empty()) {
198 MBBInfo &MBBI = WorkList.back();
199
200 // If this MBB has already been visited, destroy the scope for the MBB and
201 // pop it from the work list.
202 if (MBBI.isVisited()) {
203 MBBI.postVisit();
204 WorkList.pop_back();
205 continue;
206 }
207
208 // Visit the MBB and add its children to the work list.
209 MBBI.preVisit(ScopedHT);
210 Changed |= visitNode(MBBI);
211 const MachineDomTreeNode *Node = MBBI.getNode();
212 WorkList.append(in_start: Node->begin(), in_end: Node->end());
213 }
214
215 return Changed;
216}
217
218bool OptimizePICCall::visitNode(MBBInfo &MBBI) {
219 bool Changed = false;
220 MachineBasicBlock *MBB = MBBI.getNode()->getBlock();
221 const MipsSubtarget &STI = MBB->getParent()->getSubtarget<MipsSubtarget>();
222 const MipsOptions &CLOpts = STI.getCLOpts();
223 const MipsRegisterInfo &TRI = *STI.getRegisterInfo();
224
225 // Definition of $gp reaching the current instruction.
226 MachineOperand *GPDef = nullptr;
227
228 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
229 ++I) {
230 unsigned Reg;
231 ValueType Entry;
232
233 // Handle call instructions via registers.
234 if (isCallViaRegister(MI&: *I, Reg, Val&: Entry)) {
235 Changed = true;
236 unsigned N = getCount(Entry);
237
238 if (N != 0) {
239 // If a function has been called more than twice, we do not have to emit
240 // a load instruction to get the function address from the GOT, but can
241 // instead reuse the address that has been loaded before.
242 if (N >= 2 && !CLOpts.load_target_from_got)
243 getCallTargetRegOpnd(MI&: *I)->setReg(getReg(Entry));
244
245 // Erase the $gp operand if this isn't the first time a function has
246 // been called. $gp needs to be set up only if the function call can go
247 // through a lazy binding stub.
248 if (eraseGPOpnd(CLOpts, MI&: *I) && GPDef)
249 GPDef->setIsDead();
250 }
251
252 if (Entry)
253 incCntAndSetReg(Entry, Reg);
254
255 setCallTargetReg(MBB, I);
256 }
257
258 if (MachineOperand *Def = I->findRegisterDefOperand(Reg: Mips::GP, TRI: &TRI))
259 GPDef = Def;
260 else if (I->readsRegister(Reg: Mips::GP, TRI: &TRI))
261 GPDef = nullptr;
262 }
263
264 return Changed;
265}
266
267bool OptimizePICCall::isCallViaRegister(MachineInstr &MI, unsigned &Reg,
268 ValueType &Val) const {
269 if (!MI.isCall())
270 return false;
271
272 MachineOperand *MO = getCallTargetRegOpnd(MI);
273
274 // Return if MI is not a function call via a register.
275 if (!MO)
276 return false;
277
278 // Get the instruction that loads the function address from the GOT.
279 Reg = MO->getReg();
280 Val = nullptr;
281 MachineRegisterInfo &MRI = MI.getParent()->getParent()->getRegInfo();
282 MachineInstr *DefMI = MRI.getVRegDef(Reg);
283
284 assert(DefMI);
285
286 // See if DefMI is an instruction that loads from a GOT entry that holds the
287 // address of a lazy binding stub.
288 if (!DefMI->mayLoad() || DefMI->getNumOperands() < 3)
289 return true;
290
291 unsigned Flags = DefMI->getOperand(i: 2).getTargetFlags();
292
293 if (Flags != MipsII::MO_GOT_CALL && Flags != MipsII::MO_CALL_LO16)
294 return true;
295
296 // Return the underlying object for the GOT entry in Val.
297 assert(DefMI->hasOneMemOperand());
298 Val = (*DefMI->memoperands_begin())->getValue();
299 if (!Val)
300 Val = (*DefMI->memoperands_begin())->getPseudoValue();
301 return true;
302}
303
304unsigned OptimizePICCall::getCount(ValueType Entry) {
305 return ScopedHT.lookup(Key: Entry).first;
306}
307
308unsigned OptimizePICCall::getReg(ValueType Entry) {
309 unsigned Reg = ScopedHT.lookup(Key: Entry).second;
310 assert(Reg);
311 return Reg;
312}
313
314void OptimizePICCall::incCntAndSetReg(ValueType Entry, unsigned Reg) {
315 CntRegP P = ScopedHT.lookup(Key: Entry);
316 ScopedHT.insert(Key: Entry, Val: std::make_pair(x: P.first + 1, y&: Reg));
317}
318
319/// Return an OptimizeCall object.
320FunctionPass *llvm::createMipsOptimizePICCallPass() {
321 return new OptimizePICCall();
322}
323