contrib/llvm/lib/Target/Mips/MipsOptimizePICCall.cpp

   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 }