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