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