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     void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL,
  77                        MachineBasicBlock *MBBOpnd);
  78     void expandToLongBranch(MBBInfo &Info);
  79
  80     const TargetMachine &TM;
  81     const MipsInstrInfo *TII;
  82     MachineFunction *MF;
  83     SmallVector<MBBInfo, 16> MBBInfos;
  84   };
  85
  86   char MipsLongBranch::ID = 0;
  87 } // end of anonymous namespace
  88
  89 /// createMipsLongBranchPass - Returns a pass that converts branches to long
  90 /// branches.
  91 FunctionPass *llvm::createMipsLongBranchPass(MipsTargetMachine &tm) {
  92   return new MipsLongBranch(tm);
  93 }
  94
  95 /// Iterate over list of Br's operands and search for a MachineBasicBlock
  96 /// operand.
  97 static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
  98   for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
  99     const MachineOperand &MO = Br.getOperand(I);
 100
 101     if (MO.isMBB())
 102       return MO.getMBB();
 103   }
 104
 105   assert(false && "This instruction does not have an MBB operand.");
 106   return 0;
 107 }
 108
 109 // Traverse the list of instructions backwards until a non-debug instruction is
 110 // found or it reaches E.
 111 static ReverseIter getNonDebugInstr(ReverseIter B, ReverseIter E) {
 112   for (; B != E; ++B)
 113     if (!B->isDebugValue())
 114       return B;
 115
 116   return E;
 117 }
 118
 119 // Split MBB if it has two direct jumps/branches.
 120 void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) {
 121   ReverseIter End = MBB->rend();
 122   ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
 123
 124   // Return if MBB has no branch instructions.
 125   if ((LastBr == End) ||
 126       (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
 127     return;
 128
 129   ReverseIter FirstBr = getNonDebugInstr(llvm::next(LastBr), End);
 130
 131   // MBB has only one branch instruction if FirstBr is not a branch
 132   // instruction.
 133   if ((FirstBr == End) ||
 134       (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
 135     return;
 136
 137   assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
 138
 139   // Create a new MBB. Move instructions in MBB to the newly created MBB.
 140   MachineBasicBlock *NewMBB =
 141     MF->CreateMachineBasicBlock(MBB->getBasicBlock());
 142
 143   // Insert NewMBB and fix control flow.
 144   MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
 145   NewMBB->transferSuccessors(MBB);
 146   NewMBB->removeSuccessor(Tgt);
 147   MBB->addSuccessor(NewMBB);
 148   MBB->addSuccessor(Tgt);
 149   MF->insert(llvm::next(MachineFunction::iterator(MBB)), NewMBB);
 150
 151   NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end());
 152 }
 153
 154 // Fill MBBInfos.
 155 void MipsLongBranch::initMBBInfo() {
 156   // Split the MBBs if they have two branches. Each basic block should have at
 157   // most one branch after this loop is executed.
 158   for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E;)
 159     splitMBB(I++);
 160
 161   MF->RenumberBlocks();
 162   MBBInfos.clear();
 163   MBBInfos.resize(MF->size());
 164
 165   for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
 166     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
 167
 168     // Compute size of MBB.
 169     for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin();
 170          MI != MBB->instr_end(); ++MI)
 171       MBBInfos[I].Size += TII->GetInstSizeInBytes(&*MI);
 172
 173     // Search for MBB's branch instruction.
 174     ReverseIter End = MBB->rend();
 175     ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
 176
 177     if ((Br != End) && !Br->isIndirectBranch() &&
 178         (Br->isConditionalBranch() ||
 179          (Br->isUnconditionalBranch() &&
 180           TM.getRelocationModel() == Reloc::PIC_)))
 181       MBBInfos[I].Br = (++Br).base();
 182   }
 183 }
 184
 185 // Compute offset of branch in number of bytes.
 186 int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) {
 187   int64_t Offset = 0;
 188   int ThisMBB = Br->getParent()->getNumber();
 189   int TargetMBB = getTargetMBB(*Br)->getNumber();
 190
 191   // Compute offset of a forward branch.
 192   if (ThisMBB < TargetMBB) {
 193     for (int N = ThisMBB + 1; N < TargetMBB; ++N)
 194       Offset += MBBInfos[N].Size;
 195
 196     return Offset + 4;
 197   }
 198
 199   // Compute offset of a backward branch.
 200   for (int N = ThisMBB; N >= TargetMBB; --N)
 201     Offset += MBBInfos[N].Size;
 202
 203   return -Offset + 4;
 204 }
 205
 206 // Replace Br with a branch which has the opposite condition code and a
 207 // MachineBasicBlock operand MBBOpnd.
 208 void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br,
 209                                    DebugLoc DL, MachineBasicBlock *MBBOpnd) {
 210   unsigned NewOpc = TII->GetOppositeBranchOpc(Br->getOpcode());
 211   const MCInstrDesc &NewDesc = TII->get(NewOpc);
 212
 213   MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
 214
 215   for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
 216     MachineOperand &MO = Br->getOperand(I);
 217
 218     if (!MO.isReg()) {
 219       assert(MO.isMBB() && "MBB operand expected.");
 220       break;
 221     }
 222
 223     MIB.addReg(MO.getReg());
 224   }
 225
 226   MIB.addMBB(MBBOpnd);
 227
 228   Br->eraseFromParent();
 229 }
 230
 231 // Expand branch instructions to long branches.
 232 void MipsLongBranch::expandToLongBranch(MBBInfo &I) {
 233   I.HasLongBranch = true;
 234
 235   bool IsPIC = TM.getRelocationModel() == Reloc::PIC_;
 236   unsigned ABI = TM.getSubtarget<MipsSubtarget>().getTargetABI();
 237   bool N64 = ABI == MipsSubtarget::N64;
 238
 239   MachineBasicBlock::iterator Pos;
 240   MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
 241   DebugLoc DL = I.Br->getDebugLoc();
 242   const BasicBlock *BB = MBB->getBasicBlock();
 243   MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);
 244   MachineBasicBlock *LongBrMBB = MF->CreateMachineBasicBlock(BB);
 245
 246   MF->insert(FallThroughMBB, LongBrMBB);
 247   MBB->removeSuccessor(TgtMBB);
 248   MBB->addSuccessor(LongBrMBB);
 249
 250   if (IsPIC) {
 251     // $longbr:
 252     //  addiu $sp, $sp, -regsize * 2
 253     //  sw $ra, 0($sp)
 254     //  bal $baltgt
 255     //  sw $a3, regsize($sp)
 256     // $baltgt:
 257     //  lui $a3, %hi($baltgt)
 258     //  lui $at, %hi($tgt)
 259     //  addiu $a3, $a3, %lo($baltgt)
 260     //  addiu $at, $at, %lo($tgt)
 261     //  subu $at, $at, $a3
 262     //  addu $at, $ra, $at
 263     //
 264     //  if n64:
 265     //   lui $a3, %highest($baltgt)
 266     //   lui $ra, %highest($tgt)
 267     //   addiu $a3, $a3, %higher($baltgt)
 268     //   addiu $ra, $ra, %higher($tgt)
 269     //   dsll $a3, $a3, 32
 270     //   dsll $ra, $ra, 32
 271     //   subu $at, $at, $a3
 272     //   addu $at, $at, $ra
 273     //
 274     //  lw $ra, 0($sp)
 275     //  lw $a3, regsize($sp)
 276     //  jr $at
 277     //  addiu $sp, $sp, regsize * 2
 278     // $fallthrough:
 279     //
 280     MF->getInfo<MipsFunctionInfo>()->setEmitNOAT();
 281     MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB);
 282     MF->insert(FallThroughMBB, BalTgtMBB);
 283     LongBrMBB->addSuccessor(BalTgtMBB);
 284     BalTgtMBB->addSuccessor(TgtMBB);
 285
 286     int RegSize = N64 ? 8 : 4;
 287     unsigned AT = N64 ? Mips::AT_64 : Mips::AT;
 288     unsigned A3 = N64 ? Mips::A3_64 : Mips::A3;
 289     unsigned SP = N64 ? Mips::SP_64 : Mips::SP;
 290     unsigned RA = N64 ? Mips::RA_64 : Mips::RA;
 291     unsigned Load = N64 ? Mips::LD_P8 : Mips::LW;
 292     unsigned Store = N64 ? Mips::SD_P8 : Mips::SW;
 293     unsigned LUi = N64 ? Mips::LUi64 : Mips::LUi;
 294     unsigned ADDiu = N64 ? Mips::DADDiu : Mips::ADDiu;
 295     unsigned ADDu = N64 ? Mips::DADDu : Mips::ADDu;
 296     unsigned SUBu = N64 ? Mips::SUBu : Mips::SUBu;
 297     unsigned JR = N64 ? Mips::JR64 : Mips::JR;
 298
 299     Pos = LongBrMBB->begin();
 300
 301     BuildMI(*LongBrMBB, Pos, DL, TII->get(ADDiu), SP).addReg(SP)
 302       .addImm(-RegSize * 2);
 303     BuildMI(*LongBrMBB, Pos, DL, TII->get(Store)).addReg(RA).addReg(SP)
 304       .addImm(0);
 305     BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB);
 306     BuildMI(*LongBrMBB, Pos, DL, TII->get(Store)).addReg(A3).addReg(SP)
 307       .addImm(RegSize)->setIsInsideBundle();
 308
 309     Pos = BalTgtMBB->begin();
 310
 311     BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), A3)
 312       .addMBB(BalTgtMBB, MipsII::MO_ABS_HI);
 313     BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), AT)
 314       .addMBB(TgtMBB, MipsII::MO_ABS_HI);
 315     BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), A3).addReg(A3)
 316       .addMBB(BalTgtMBB, MipsII::MO_ABS_LO);
 317     BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), AT).addReg(AT)
 318       .addMBB(TgtMBB, MipsII::MO_ABS_LO);
 319     BuildMI(*BalTgtMBB, Pos, DL, TII->get(SUBu), AT).addReg(AT).addReg(A3);
 320     BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDu), AT).addReg(RA).addReg(AT);
 321
 322     if (N64) {
 323       BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), A3)
 324         .addMBB(BalTgtMBB, MipsII::MO_HIGHEST);
 325       BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), RA)
 326         .addMBB(TgtMBB, MipsII::MO_HIGHEST);
 327       BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), A3).addReg(A3)
 328         .addMBB(BalTgtMBB, MipsII::MO_HIGHER);
 329       BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), RA).addReg(RA)
 330         .addMBB(TgtMBB, MipsII::MO_HIGHER);
 331       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DSLL), A3).addReg(A3)
 332         .addImm(32);
 333       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DSLL), RA).addReg(RA)
 334         .addImm(32);
 335       BuildMI(*BalTgtMBB, Pos, DL, TII->get(SUBu), AT).addReg(AT).addReg(A3);
 336       BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDu), AT).addReg(AT).addReg(RA);
 337       I.Size += 4 * 8;
 338     }
 339
 340     BuildMI(*BalTgtMBB, Pos, DL, TII->get(Load), RA).addReg(SP).addImm(0);
 341     BuildMI(*BalTgtMBB, Pos, DL, TII->get(Load), A3).addReg(SP).addImm(RegSize);
 342     BuildMI(*BalTgtMBB, Pos, DL, TII->get(JR)).addReg(AT);
 343     BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), SP).addReg(SP)
 344       .addImm(RegSize * 2)->setIsInsideBundle();
 345     I.Size += 4 * 14;
 346   } else {
 347     // $longbr:
 348     //  j $tgt
 349     //  nop
 350     // $fallthrough:
 351     //
 352     Pos = LongBrMBB->begin();
 353     LongBrMBB->addSuccessor(TgtMBB);
 354     BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::J)).addMBB(TgtMBB);
 355     BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::NOP))->setIsInsideBundle();
 356     I.Size += 4 * 2;
 357   }
 358
 359   if (I.Br->isUnconditionalBranch()) {
 360     // Change branch destination.
 361     assert(I.Br->getDesc().getNumOperands() == 1);
 362     I.Br->RemoveOperand(0);
 363     I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
 364   } else
 365     // Change branch destination and reverse condition.
 366     replaceBranch(*MBB, I.Br, DL, FallThroughMBB);
 367 }
 368
 369 static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
 370   MachineBasicBlock &MBB = F.front();
 371   MachineBasicBlock::iterator I = MBB.begin();
 372   DebugLoc DL = MBB.findDebugLoc(MBB.begin());
 373   BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
 374     .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
 375   BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
 376     .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
 377   MBB.removeLiveIn(Mips::V0);
 378 }
 379
 380 bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) {
 381   if ((TM.getRelocationModel() == Reloc::PIC_) &&
 382       TM.getSubtarget<MipsSubtarget>().isABI_O32() &&
 383       F.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
 384     emitGPDisp(F, TII);
 385
 386   if (SkipLongBranch)
 387     return true;
 388
 389   MF = &F;
 390   initMBBInfo();
 391
 392   SmallVector<MBBInfo, 16>::iterator I, E = MBBInfos.end();
 393   bool EverMadeChange = false, MadeChange = true;
 394
 395   while (MadeChange) {
 396     MadeChange = false;
 397
 398     for (I = MBBInfos.begin(); I != E; ++I) {
 399       // Skip if this MBB doesn't have a branch or the branch has already been
 400       // converted to a long branch.
 401       if (!I->Br || I->HasLongBranch)
 402         continue;
 403
 404       if (!ForceLongBranch)
 405         // Check if offset fits into 16-bit immediate field of branches.
 406         if (isInt<16>(computeOffset(I->Br) / 4))
 407           continue;
 408
 409       expandToLongBranch(*I);
 410       ++LongBranches;
 411       EverMadeChange = MadeChange = true;
 412     }
 413   }
 414
 415   if (EverMadeChange)
 416     MF->RenumberBlocks();
 417
 418   return true;
 419 }