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/TargetInstrInfo.h" 31 #include "llvm/CodeGen/TargetOpcodes.h" 32 #include "llvm/CodeGen/TargetRegisterInfo.h" 33 #include "llvm/CodeGen/TargetSubtargetInfo.h" 34 #include "llvm/Support/Allocator.h" 35 #include "llvm/Support/CommandLine.h" 36 #include "llvm/Support/ErrorHandling.h" 37 #include "llvm/Support/MachineValueType.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 /// Visit MBB. 94 bool visitNode(MBBInfo &MBBI); 95 96 /// 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 /// 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 /// Return the destination virtual register of the last instruction 109 /// that loads from object Entry. 110 unsigned getReg(ValueType Entry); 111 112 /// 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