lib/Target/Mips/MipsLongBranch.cpp

   1 //===-- MipsLongBranch.cpp - Emit long branches ---------------------------===//
   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 expands a branch or jump instruction into a long branch if its
  11 // offset is too large to fit into its immediate field.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "mips-long-branch"
  16
  17 #include "Mips.h"
  18 #include "MipsTargetMachine.h"
  19 #include "MCTargetDesc/MipsBaseInfo.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/Function.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/MathExtras.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Target/TargetMachine.h"
  28 #include "llvm/Target/TargetRegisterInfo.h"
  29
  30 using namespace llvm;
  31
  32 STATISTIC(LongBranches, "Number of long branches.");
  33
  34 static cl::opt<bool> SkipLongBranch(
  35   "skip-mips-long-branch",
  36   cl::init(false),
  37   cl::desc("MIPS: Skip long branch pass."),
  38   cl::Hidden);
  39
  40 static cl::opt<bool> ForceLongBranch(
  41   "force-mips-long-branch",
  42   cl::init(false),
  43   cl::desc("MIPS: Expand all branches to long format."),
  44   cl::Hidden);
  45
  46 namespace {
  47   typedef MachineBasicBlock::iterator Iter;
  48   typedef MachineBasicBlock::reverse_iterator ReverseIter;
  49
  50   struct MBBInfo {
  51     uint64_t Size;
  52     bool HasLongBranch;
  53     MachineInstr *Br;
  54
  55     MBBInfo() : Size(0), HasLongBranch(false), Br(0) {}
  56   };
  57
  58   class MipsLongBranch : public MachineFunctionPass {
  59
  60   public:
  61     static char ID;
  62     MipsLongBranch(TargetMachine &tm)
  63       : MachineFunctionPass(ID), TM(tm),
  64         TII(static_cast<const MipsInstrInfo*>(tm.getInstrInfo())) {}
  65
  66     virtual const char *getPassName() const {
  67       return "Mips Long Branch";
  68     }
  69
  70     bool runOnMachineFunction(MachineFunction &F);
  71
  72   private:
  73     void splitMBB(MachineBasicBlock *MBB);
  74     void initMBBInfo();
  75     int64_t computeOffset(const MachineInstr *Br);
  76     bool offsetFitsIntoField(const MachineInstr *Br);
  77     unsigned addLongBranch(MachineBasicBlock &MBB, Iter Pos,
  78                            MachineBasicBlock *Tgt, DebugLoc DL, bool Nop);
  79     void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL,
  80                        MachineBasicBlock *MBBOpnd);
  81     void expandToLongBranch(MBBInfo &Info);
  82
  83     const TargetMachine &TM;
  84     const MipsInstrInfo *TII;
  85     MachineFunction *MF;
  86     SmallVector<MBBInfo, 16> MBBInfos;
  87   };
  88
  89   char MipsLongBranch::ID = 0;
  90 } // end of anonymous namespace
  91
  92 /// createMipsLongBranchPass - Returns a pass that converts branches to long
  93 /// branches.
  94 FunctionPass *llvm::createMipsLongBranchPass(MipsTargetMachine &tm) {
  95   return new MipsLongBranch(tm);
  96 }
  97
  98 /// Iterate over list of Br's operands and search for a MachineBasicBlock
  99 /// operand.
 100 static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
 101   for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
 102     const MachineOperand &MO = Br.getOperand(I);
 103
 104     if (MO.isMBB())
 105       return MO.getMBB();
 106   }
 107
 108   assert(false && "This instruction does not have an MBB operand.");
 109   return 0;
 110 }
 111
 112 // Traverse the list of instructions backwards until a non-debug instruction is
 113 // found or it reaches E.
 114 static ReverseIter getNonDebugInstr(ReverseIter B, ReverseIter E) {
 115   for (; B != E; ++B)
 116     if (!B->isDebugValue())
 117       return B;
 118
 119   return E;
 120 }
 121
 122 // Split MBB if it has two direct jumps/branches.
 123 void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) {
 124   ReverseIter End = MBB->rend();
 125   ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
 126
 127   // Return if MBB has no branch instructions.
 128   if ((LastBr == End) ||
 129       (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
 130     return;
 131
 132   ReverseIter FirstBr = getNonDebugInstr(llvm::next(LastBr), End);
 133
 134   // MBB has only one branch instruction if FirstBr is not a branch
 135   // instruction.
 136   if ((FirstBr == End) ||
 137       (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
 138     return;
 139
 140   assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
 141
 142   // Create a new MBB. Move instructions in MBB to the newly created MBB.
 143   MachineBasicBlock *NewMBB =
 144     MF->CreateMachineBasicBlock(MBB->getBasicBlock());
 145
 146   // Insert NewMBB and fix control flow.
 147   MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
 148   NewMBB->transferSuccessors(MBB);
 149   NewMBB->removeSuccessor(Tgt);
 150   MBB->addSuccessor(NewMBB);
 151   MBB->addSuccessor(Tgt);
 152   MF->insert(llvm::next(MachineFunction::iterator(MBB)), NewMBB);
 153
 154   NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end());
 155 }
 156
 157 // Fill MBBInfos.
 158 void MipsLongBranch::initMBBInfo() {
 159   // Split the MBBs if they have two branches. Each basic block should have at
 160   // most one branch after this loop is executed.
 161   for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E;)
 162     splitMBB(I++);
 163
 164   MF->RenumberBlocks();
 165   MBBInfos.clear();
 166   MBBInfos.resize(MF->size());
 167
 168   for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
 169     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
 170
 171     // Compute size of MBB.
 172     for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin();
 173          MI != MBB->instr_end(); ++MI)
 174       MBBInfos[I].Size += TII->GetInstSizeInBytes(&*MI);
 175
 176     // Search for MBB's branch instruction.
 177     ReverseIter End = MBB->rend();
 178     ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
 179
 180     if ((Br != End) && !Br->isIndirectBranch() &&
 181         (Br->isConditionalBranch() || Br->isUnconditionalBranch()))
 182       MBBInfos[I].Br = (++Br).base();
 183   }
 184 }
 185
 186 // Compute offset of branch in number of bytes.
 187 int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) {
 188   int64_t Offset = 0;
 189   int ThisMBB = Br->getParent()->getNumber();
 190   int TargetMBB = getTargetMBB(*Br)->getNumber();
 191
 192   // Compute offset of a forward branch.
 193   if (ThisMBB < TargetMBB) {
 194     for (int N = ThisMBB + 1; N < TargetMBB; ++N)
 195       Offset += MBBInfos[N].Size;
 196
 197     return Offset + 4;
 198   }
 199
 200   // Compute offset of a backward branch.
 201   for (int N = ThisMBB; N >= TargetMBB; --N)
 202     Offset += MBBInfos[N].Size;
 203
 204   return -Offset + 4;
 205 }
 206
 207 // Insert the following sequence:
 208 // (pic or N64)
 209 //  lw $at, global_reg_slot
 210 //  lw $at, got($L1)($at)
 211 //  addiu $at, $at, lo($L1)
 212 //  jr $at
 213 //  noop
 214 // (static and !N64)
 215 //  lui $at, hi($L1)
 216 //  addiu $at, $at, lo($L1)
 217 //  jr $at
 218 //  noop
 219 unsigned MipsLongBranch::addLongBranch(MachineBasicBlock &MBB, Iter Pos,
 220                                        MachineBasicBlock *Tgt, DebugLoc DL,
 221                                        bool Nop) {
 222   MF->getInfo<MipsFunctionInfo>()->setEmitNOAT();
 223   bool IsPIC = (TM.getRelocationModel() == Reloc::PIC_);
 224   unsigned ABI = TM.getSubtarget<MipsSubtarget>().getTargetABI();
 225   bool N64 = (ABI == MipsSubtarget::N64);
 226   unsigned NumInstrs;
 227
 228   if (IsPIC || N64) {
 229     bool HasMips64 = TM.getSubtarget<MipsSubtarget>().hasMips64();
 230     unsigned AT = N64 ? Mips::AT_64 : Mips::AT;
 231     unsigned Load = N64 ? Mips::LD_P8 : Mips::LW;
 232     unsigned ADDiu = N64 ? Mips::DADDiu : Mips::ADDiu;
 233     unsigned JR = N64 ? Mips::JR64 : Mips::JR;
 234     unsigned GOTFlag = HasMips64 ? MipsII::MO_GOT_PAGE : MipsII::MO_GOT;
 235     unsigned OFSTFlag = HasMips64 ? MipsII::MO_GOT_OFST : MipsII::MO_ABS_LO;
 236     const MipsRegisterInfo *MRI =
 237       static_cast<const MipsRegisterInfo*>(TM.getRegisterInfo());
 238     unsigned SP = MRI->getFrameRegister(*MF);
 239     unsigned GlobalRegFI = MF->getInfo<MipsFunctionInfo>()->getGlobalRegFI();
 240     int64_t Offset = MF->getFrameInfo()->getObjectOffset(GlobalRegFI);
 241
 242     if (isInt<16>(Offset)) {
 243       BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(SP).addImm(Offset);
 244       NumInstrs = 1;
 245     } else {
 246       unsigned ADDu = N64 ? Mips::DADDu : Mips::ADDu;
 247       MipsAnalyzeImmediate::Inst LastInst(0, 0);
 248
 249       MF->getInfo<MipsFunctionInfo>()->setEmitNOAT();
 250       NumInstrs = Mips::loadImmediate(Offset, N64, *TII, MBB, Pos, DL, true,
 251                                       &LastInst) + 2;
 252       BuildMI(MBB, Pos, DL, TII->get(ADDu), AT).addReg(SP).addReg(AT);
 253       BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(AT)
 254         .addImm(SignExtend64<16>(LastInst.ImmOpnd));
 255     }
 256
 257     BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(AT).addMBB(Tgt, GOTFlag);
 258     BuildMI(MBB, Pos, DL, TII->get(ADDiu), AT).addReg(AT).addMBB(Tgt, OFSTFlag);
 259     BuildMI(MBB, Pos, DL, TII->get(JR)).addReg(Mips::AT, RegState::Kill);
 260     NumInstrs += 3;
 261   } else {
 262     BuildMI(MBB, Pos, DL, TII->get(Mips::LUi), Mips::AT)
 263       .addMBB(Tgt, MipsII::MO_ABS_HI);
 264     BuildMI(MBB, Pos, DL, TII->get(Mips::ADDiu), Mips::AT)
 265       .addReg(Mips::AT).addMBB(Tgt, MipsII::MO_ABS_LO);
 266     BuildMI(MBB, Pos, DL, TII->get(Mips::JR)).addReg(Mips::AT, RegState::Kill);
 267     NumInstrs = 3;
 268   }
 269
 270   if (Nop) {
 271     BuildMI(MBB, Pos, DL, TII->get(Mips::NOP))->setIsInsideBundle();
 272     ++NumInstrs;
 273   }
 274
 275   return NumInstrs;
 276 }
 277
 278 // Replace Br with a branch which has the opposite condition code and a
 279 // MachineBasicBlock operand MBBOpnd.
 280 void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br,
 281                                    DebugLoc DL, MachineBasicBlock *MBBOpnd) {
 282   unsigned NewOpc = Mips::GetOppositeBranchOpc(Br->getOpcode());
 283   const MCInstrDesc &NewDesc = TII->get(NewOpc);
 284
 285   MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
 286
 287   for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
 288     MachineOperand &MO = Br->getOperand(I);
 289
 290     if (!MO.isReg()) {
 291       assert(MO.isMBB() && "MBB operand expected.");
 292       break;
 293     }
 294
 295     MIB.addReg(MO.getReg());
 296   }
 297
 298   MIB.addMBB(MBBOpnd);
 299
 300   Br->eraseFromParent();
 301 }
 302
 303 // Expand branch instructions to long branches.
 304 void MipsLongBranch::expandToLongBranch(MBBInfo &I) {
 305   I.HasLongBranch = true;
 306
 307   MachineBasicBlock *MBB = I.Br->getParent(), *Tgt = getTargetMBB(*I.Br);
 308   DebugLoc DL = I.Br->getDebugLoc();
 309
 310   if (I.Br->isUnconditionalBranch()) {
 311     // Unconditional branch before transformation:
 312     //   b $tgt
 313     //   delay-slot-instr
 314     //
 315     // after transformation:
 316     //   delay-slot-instr
 317     //   lw $at, global_reg_slot
 318     //   lw $at, %got($tgt)($at)
 319     //   addiu $at, $at, %lo($tgt)
 320     //   jr $at
 321     //   nop
 322     I.Size += (addLongBranch(*MBB, llvm::next(Iter(I.Br)), Tgt, DL, true)
 323                - 1) * 4;
 324
 325     // Remove branch and clear InsideBundle bit of the next instruction.
 326     llvm::next(MachineBasicBlock::instr_iterator(I.Br))
 327       ->setIsInsideBundle(false);
 328     I.Br->eraseFromParent();
 329     return;
 330   }
 331
 332   assert(I.Br->isConditionalBranch() && "Conditional branch expected.");
 333
 334   // Conditional branch before transformation:
 335   //   b cc, $tgt
 336   //   delay-slot-instr
 337   //  FallThrough:
 338   //
 339   // after transformation:
 340   //   b !cc, FallThrough
 341   //   delay-slot-instr
 342   //  NewMBB:
 343   //   lw $at, global_reg_slot
 344   //   lw $at, %got($tgt)($at)
 345   //   addiu $at, $at, %lo($tgt)
 346   //   jr $at
 347   //   noop
 348   //  FallThrough:
 349
 350   MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(MBB->getBasicBlock());
 351   MF->insert(llvm::next(MachineFunction::iterator(MBB)), NewMBB);
 352   MBB->removeSuccessor(Tgt);
 353   MBB->addSuccessor(NewMBB);
 354   NewMBB->addSuccessor(Tgt);
 355
 356   I.Size += addLongBranch(*NewMBB, NewMBB->begin(), Tgt, DL, true) * 4;
 357   replaceBranch(*MBB, I.Br, DL, *MBB->succ_begin());
 358 }
 359
 360 static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
 361   MachineBasicBlock &MBB = F.front();
 362   MachineBasicBlock::iterator I = MBB.begin();
 363   DebugLoc DL = MBB.findDebugLoc(MBB.begin());
 364   BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
 365     .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
 366   BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
 367     .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
 368   MBB.removeLiveIn(Mips::V0);
 369 }
 370
 371 bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) {
 372   if ((TM.getRelocationModel() == Reloc::PIC_) &&
 373       TM.getSubtarget<MipsSubtarget>().isABI_O32() &&
 374       F.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
 375     emitGPDisp(F, TII);
 376
 377   if (SkipLongBranch)
 378     return true;
 379
 380   MF = &F;
 381   initMBBInfo();
 382
 383   bool IsPIC = (TM.getRelocationModel() == Reloc::PIC_);
 384   SmallVector<MBBInfo, 16>::iterator I, E = MBBInfos.end();
 385   bool EverMadeChange = false, MadeChange = true;
 386
 387   while (MadeChange) {
 388     MadeChange = false;
 389
 390     for (I = MBBInfos.begin(); I != E; ++I) {
 391       // Skip if this MBB doesn't have a branch or the branch has already been
 392       // converted to a long branch.
 393       if (!I->Br || I->HasLongBranch)
 394         continue;
 395
 396       if (!ForceLongBranch) {
 397         int64_t Offset = computeOffset(I->Br);
 398
 399         // Check if offset fits into 16-bit immediate field of branches.
 400         if ((I->Br->isConditionalBranch() || IsPIC) && isInt<16>(Offset / 4))
 401           continue;
 402
 403         // Check if offset fits into 26-bit immediate field of jumps (J).
 404         if (I->Br->isUnconditionalBranch() && !IsPIC && isInt<26>(Offset / 4))
 405           continue;
 406       }
 407
 408       expandToLongBranch(*I);
 409       ++LongBranches;
 410       EverMadeChange = MadeChange = true;
 411     }
 412   }
 413
 414   if (EverMadeChange)
 415     MF->RenumberBlocks();
 416
 417   return true;
 418 }