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