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