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
41 using namespace llvm;
42
43 #define DEBUG_TYPE "optimize-mips-pic-call"
44
45 static cl::opt<bool> LoadTargetFromGOT("mips-load-target-from-got",
46 cl::init(true),
47 cl::desc("Load target address from GOT"),
48 cl::Hidden);
49
50 static cl::opt<bool> EraseGPOpnd("mips-erase-gp-opnd",
51 cl::init(true), cl::desc("Erase GP Operand"),
52 cl::Hidden);
53
54 namespace {
55
56 using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>;
57 using CntRegP = std::pair<unsigned, unsigned>;
58 using AllocatorTy = RecyclingAllocator<BumpPtrAllocator,
59 ScopedHashTableVal<ValueType, CntRegP>>;
60 using ScopedHTType = ScopedHashTable<ValueType, CntRegP,
61 DenseMapInfo<ValueType>, AllocatorTy>;
62
63 class MBBInfo {
64 public:
65 MBBInfo(MachineDomTreeNode *N);
66
67 const MachineDomTreeNode *getNode() const;
68 bool isVisited() const;
69 void preVisit(ScopedHTType &ScopedHT);
70 void postVisit();
71
72 private:
73 MachineDomTreeNode *Node;
74 ScopedHTType::ScopeTy *HTScope;
75 };
76
77 class OptimizePICCall : public MachineFunctionPass {
78 public:
OptimizePICCall()79 OptimizePICCall() : MachineFunctionPass(ID) {}
80
getPassName() const81 StringRef getPassName() const override { return "Mips OptimizePICCall"; }
82
83 bool runOnMachineFunction(MachineFunction &F) override;
84
getAnalysisUsage(AnalysisUsage & AU) const85 void getAnalysisUsage(AnalysisUsage &AU) const override {
86 AU.addRequired<MachineDominatorTreeWrapperPass>();
87 MachineFunctionPass::getAnalysisUsage(AU);
88 }
89
90 private:
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
120 char OptimizePICCall::ID = 0;
121
122 /// Return the first MachineOperand of MI if it is a used virtual register.
getCallTargetRegOpnd(MachineInstr & MI)123 static MachineOperand *getCallTargetRegOpnd(MachineInstr &MI) {
124 if (MI.getNumOperands() == 0)
125 return nullptr;
126
127 MachineOperand &MO = MI.getOperand(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.
getRegTy(unsigned Reg,MachineFunction & MF)136 static 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);
141 }
142
143 /// Do the following transformation:
144 ///
145 /// jalr $vreg
146 /// =>
147 /// copy $t9, $vreg
148 /// jalr $t9
setCallTargetReg(MachineBasicBlock * MBB,MachineBasicBlock::iterator I)149 static 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(0).getReg();
154 unsigned DstReg = getRegTy(SrcReg, MF) == MVT::i32 ? Mips::T9 : Mips::T9_64;
155 BuildMI(*MBB, I, I->getDebugLoc(), TII.get(TargetOpcode::COPY), DstReg)
156 .addReg(SrcReg);
157 I->getOperand(0).setReg(DstReg);
158 }
159
160 /// Search MI's operands for register GP and erase it.
eraseGPOpnd(MachineInstr & MI)161 static void eraseGPOpnd(MachineInstr &MI) {
162 if (!EraseGPOpnd)
163 return;
164
165 MachineFunction &MF = *MI.getParent()->getParent();
166 MVT::SimpleValueType Ty = getRegTy(MI.getOperand(0).getReg(), MF);
167 unsigned Reg = Ty == MVT::i32 ? Mips::GP : Mips::GP_64;
168
169 for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
170 MachineOperand &MO = MI.getOperand(I);
171 if (MO.isReg() && MO.getReg() == Reg) {
172 MI.removeOperand(I);
173 return;
174 }
175 }
176
177 llvm_unreachable(nullptr);
178 }
179
MBBInfo(MachineDomTreeNode * N)180 MBBInfo::MBBInfo(MachineDomTreeNode *N) : Node(N), HTScope(nullptr) {}
181
getNode() const182 const MachineDomTreeNode *MBBInfo::getNode() const { return Node; }
183
isVisited() const184 bool MBBInfo::isVisited() const { return HTScope; }
185
preVisit(ScopedHTType & ScopedHT)186 void MBBInfo::preVisit(ScopedHTType &ScopedHT) {
187 HTScope = new ScopedHTType::ScopeTy(ScopedHT);
188 }
189
postVisit()190 void MBBInfo::postVisit() {
191 delete HTScope;
192 }
193
194 // OptimizePICCall methods.
runOnMachineFunction(MachineFunction & F)195 bool OptimizePICCall::runOnMachineFunction(MachineFunction &F) {
196 if (F.getSubtarget<MipsSubtarget>().inMips16Mode())
197 return false;
198
199 // Do a pre-order traversal of the dominator tree.
200 MachineDominatorTree *MDT =
201 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
202 bool Changed = false;
203
204 SmallVector<MBBInfo, 8> WorkList(1, MBBInfo(MDT->getRootNode()));
205
206 while (!WorkList.empty()) {
207 MBBInfo &MBBI = WorkList.back();
208
209 // If this MBB has already been visited, destroy the scope for the MBB and
210 // pop it from the work list.
211 if (MBBI.isVisited()) {
212 MBBI.postVisit();
213 WorkList.pop_back();
214 continue;
215 }
216
217 // Visit the MBB and add its children to the work list.
218 MBBI.preVisit(ScopedHT);
219 Changed |= visitNode(MBBI);
220 const MachineDomTreeNode *Node = MBBI.getNode();
221 WorkList.append(Node->begin(), Node->end());
222 }
223
224 return Changed;
225 }
226
visitNode(MBBInfo & MBBI)227 bool OptimizePICCall::visitNode(MBBInfo &MBBI) {
228 bool Changed = false;
229 MachineBasicBlock *MBB = MBBI.getNode()->getBlock();
230
231 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
232 ++I) {
233 unsigned Reg;
234 ValueType Entry;
235
236 // Skip instructions that are not call instructions via registers.
237 if (!isCallViaRegister(*I, Reg, Entry))
238 continue;
239
240 Changed = true;
241 unsigned N = getCount(Entry);
242
243 if (N != 0) {
244 // If a function has been called more than twice, we do not have to emit a
245 // load instruction to get the function address from the GOT, but can
246 // instead reuse the address that has been loaded before.
247 if (N >= 2 && !LoadTargetFromGOT)
248 getCallTargetRegOpnd(*I)->setReg(getReg(Entry));
249
250 // Erase the $gp operand if this isn't the first time a function has
251 // been called. $gp needs to be set up only if the function call can go
252 // through a lazy binding stub.
253 eraseGPOpnd(*I);
254 }
255
256 if (Entry)
257 incCntAndSetReg(Entry, Reg);
258
259 setCallTargetReg(MBB, I);
260 }
261
262 return Changed;
263 }
264
isCallViaRegister(MachineInstr & MI,unsigned & Reg,ValueType & Val) const265 bool OptimizePICCall::isCallViaRegister(MachineInstr &MI, unsigned &Reg,
266 ValueType &Val) const {
267 if (!MI.isCall())
268 return false;
269
270 MachineOperand *MO = getCallTargetRegOpnd(MI);
271
272 // Return if MI is not a function call via a register.
273 if (!MO)
274 return false;
275
276 // Get the instruction that loads the function address from the GOT.
277 Reg = MO->getReg();
278 Val = nullptr;
279 MachineRegisterInfo &MRI = MI.getParent()->getParent()->getRegInfo();
280 MachineInstr *DefMI = MRI.getVRegDef(Reg);
281
282 assert(DefMI);
283
284 // See if DefMI is an instruction that loads from a GOT entry that holds the
285 // address of a lazy binding stub.
286 if (!DefMI->mayLoad() || DefMI->getNumOperands() < 3)
287 return true;
288
289 unsigned Flags = DefMI->getOperand(2).getTargetFlags();
290
291 if (Flags != MipsII::MO_GOT_CALL && Flags != MipsII::MO_CALL_LO16)
292 return true;
293
294 // Return the underlying object for the GOT entry in Val.
295 assert(DefMI->hasOneMemOperand());
296 Val = (*DefMI->memoperands_begin())->getValue();
297 if (!Val)
298 Val = (*DefMI->memoperands_begin())->getPseudoValue();
299 return true;
300 }
301
getCount(ValueType Entry)302 unsigned OptimizePICCall::getCount(ValueType Entry) {
303 return ScopedHT.lookup(Entry).first;
304 }
305
getReg(ValueType Entry)306 unsigned OptimizePICCall::getReg(ValueType Entry) {
307 unsigned Reg = ScopedHT.lookup(Entry).second;
308 assert(Reg);
309 return Reg;
310 }
311
incCntAndSetReg(ValueType Entry,unsigned Reg)312 void OptimizePICCall::incCntAndSetReg(ValueType Entry, unsigned Reg) {
313 CntRegP P = ScopedHT.lookup(Entry);
314 ScopedHT.insert(Entry, std::make_pair(P.first + 1, Reg));
315 }
316
317 /// Return an OptimizeCall object.
createMipsOptimizePICCallPass()318 FunctionPass *llvm::createMipsOptimizePICCallPass() {
319 return new OptimizePICCall();
320 }
321