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