Reinstate "Nuke the old JIT."
[oota-llvm.git] / lib / Target / Mips / MipsLongBranch.cpp
index 92b57722100abf43f1776df3b2f40cc7b05c2aec..71a6f4d4a11e074c9bccfaacd59764d44ddf169d 100644 (file)
 // This pass expands a branch or jump instruction into a long branch if its
 // offset is too large to fit into its immediate field.
 //
+// FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries.
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "mips-long-branch"
-
 #include "Mips.h"
-#include "MipsTargetMachine.h"
 #include "MCTargetDesc/MipsBaseInfo.h"
+#include "MCTargetDesc/MipsMCNaCl.h"
+#include "MipsMachineFunction.h"
+#include "MipsTargetMachine.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/Function.h"
+#include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetInstrInfo.h"
@@ -29,6 +30,8 @@
 
 using namespace llvm;
 
+#define DEBUG_TYPE "mips-long-branch"
+
 STATISTIC(LongBranches, "Number of long branches.");
 
 static cl::opt<bool> SkipLongBranch(
@@ -48,11 +51,11 @@ namespace {
   typedef MachineBasicBlock::reverse_iterator ReverseIter;
 
   struct MBBInfo {
-    uint64_t Size;
+    uint64_t Size, Address;
     bool HasLongBranch;
     MachineInstr *Br;
 
-    MBBInfo() : Size(0), HasLongBranch(false), Br(0) {}
+    MBBInfo() : Size(0), HasLongBranch(false), Br(nullptr) {}
   };
 
   class MipsLongBranch : public MachineFunctionPass {
@@ -61,29 +64,31 @@ namespace {
     static char ID;
     MipsLongBranch(TargetMachine &tm)
       : MachineFunctionPass(ID), TM(tm),
-        TII(static_cast<const MipsInstrInfo*>(tm.getInstrInfo())) {}
+        IsPIC(TM.getRelocationModel() == Reloc::PIC_),
+        ABI(TM.getSubtarget<MipsSubtarget>().getTargetABI()),
+        LongBranchSeqSize(!IsPIC ? 2 : (ABI == MipsSubtarget::N64 ? 10 :
+            (!TM.getSubtarget<MipsSubtarget>().isTargetNaCl() ? 9 : 10))) {}
 
-    virtual const char *getPassName() const {
+    const char *getPassName() const override {
       return "Mips Long Branch";
     }
 
-    bool runOnMachineFunction(MachineFunction &F);
+    bool runOnMachineFunction(MachineFunction &F) override;
 
   private:
     void splitMBB(MachineBasicBlock *MBB);
     void initMBBInfo();
     int64_t computeOffset(const MachineInstr *Br);
-    bool offsetFitsIntoField(const MachineInstr *Br);
-    unsigned addLongBranch(MachineBasicBlock &MBB, Iter Pos,
-                           MachineBasicBlock *Tgt, DebugLoc DL, bool Nop);
     void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL,
                        MachineBasicBlock *MBBOpnd);
     void expandToLongBranch(MBBInfo &Info);
 
     const TargetMachine &TM;
-    const MipsInstrInfo *TII;
     MachineFunction *MF;
     SmallVector<MBBInfo, 16> MBBInfos;
+    bool IsPIC;
+    unsigned ABI;
+    unsigned LongBranchSeqSize;
   };
 
   char MipsLongBranch::ID = 0;
@@ -106,7 +111,7 @@ static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
   }
 
   assert(false && "This instruction does not have an MBB operand.");
-  return 0;
+  return nullptr;
 }
 
 // Traverse the list of instructions backwards until a non-debug instruction is
@@ -129,7 +134,7 @@ void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) {
       (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
     return;
 
-  ReverseIter FirstBr = getNonDebugInstr(next(LastBr), End);
+  ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End);
 
   // MBB has only one branch instruction if FirstBr is not a branch
   // instruction.
@@ -149,7 +154,7 @@ void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) {
   NewMBB->removeSuccessor(Tgt);
   MBB->addSuccessor(NewMBB);
   MBB->addSuccessor(Tgt);
-  MF->insert(next(MachineFunction::iterator(MBB)), NewMBB);
+  MF->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
 
   NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end());
 }
@@ -165,6 +170,8 @@ void MipsLongBranch::initMBBInfo() {
   MBBInfos.clear();
   MBBInfos.resize(MF->size());
 
+  const MipsInstrInfo *TII =
+      static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo());
   for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
 
@@ -178,7 +185,9 @@ void MipsLongBranch::initMBBInfo() {
     ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
 
     if ((Br != End) && !Br->isIndirectBranch() &&
-        (Br->isConditionalBranch() || Br->isUnconditionalBranch()))
+        (Br->isConditionalBranch() ||
+         (Br->isUnconditionalBranch() &&
+          TM.getRelocationModel() == Reloc::PIC_)))
       MBBInfos[I].Br = (++Br).base();
   }
 }
@@ -204,82 +213,13 @@ int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) {
   return -Offset + 4;
 }
 
-// Insert the following sequence:
-// (pic or N64)
-//  lw $at, global_reg_slot
-//  lw $at, got($L1)($at)
-//  addiu $at, $at, lo($L1)
-//  jr $at
-//  noop
-// (static and !N64)
-//  lui $at, hi($L1)
-//  addiu $at, $at, lo($L1)
-//  jr $at
-//  noop
-unsigned MipsLongBranch::addLongBranch(MachineBasicBlock &MBB, Iter Pos,
-                                       MachineBasicBlock *Tgt, DebugLoc DL,
-                                       bool Nop) {
-  MF->getInfo<MipsFunctionInfo>()->setEmitNOAT();
-  bool IsPIC = (TM.getRelocationModel() == Reloc::PIC_);
-  unsigned ABI = TM.getSubtarget<MipsSubtarget>().getTargetABI();
-  bool N64 = (ABI == MipsSubtarget::N64);
-  unsigned NumInstrs;
-
-  if (IsPIC || N64) {
-    bool HasMips64 = TM.getSubtarget<MipsSubtarget>().hasMips64();
-    unsigned AT = N64 ? Mips::AT_64 : Mips::AT;
-    unsigned Load = N64 ? Mips::LD_P8 : Mips::LW;
-    unsigned ADDiu = N64 ? Mips::DADDiu : Mips::ADDiu;
-    unsigned JR = N64 ? Mips::JR64 : Mips::JR;
-    unsigned GOTFlag = HasMips64 ? MipsII::MO_GOT_PAGE : MipsII::MO_GOT;
-    unsigned OFSTFlag = HasMips64 ? MipsII::MO_GOT_OFST : MipsII::MO_ABS_LO;
-    const MipsRegisterInfo *MRI =
-      static_cast<const MipsRegisterInfo*>(TM.getRegisterInfo());
-    unsigned SP = MRI->getFrameRegister(*MF);
-    unsigned GlobalRegFI = MF->getInfo<MipsFunctionInfo>()->getGlobalRegFI();
-    int64_t Offset = MF->getFrameInfo()->getObjectOffset(GlobalRegFI);
-
-    if (isInt<16>(Offset)) {
-      BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(SP).addImm(Offset);
-      NumInstrs = 1;
-    } else {
-      unsigned ADDu = N64 ? Mips::DADDu : Mips::ADDu;
-      MipsAnalyzeImmediate::Inst LastInst(0, 0);
-
-      MF->getInfo<MipsFunctionInfo>()->setEmitNOAT();
-      NumInstrs = Mips::loadImmediate(Offset, N64, *TII, MBB, Pos, DL, true,
-                                      &LastInst) + 2;
-      BuildMI(MBB, Pos, DL, TII->get(ADDu), AT).addReg(SP).addReg(AT);
-      BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(AT)
-        .addImm(SignExtend64<16>(LastInst.ImmOpnd));
-    }
-
-    BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(AT).addMBB(Tgt, GOTFlag);
-    BuildMI(MBB, Pos, DL, TII->get(ADDiu), AT).addReg(AT).addMBB(Tgt, OFSTFlag);
-    BuildMI(MBB, Pos, DL, TII->get(JR)).addReg(Mips::AT, RegState::Kill);
-    NumInstrs += 3;
-  } else {
-    BuildMI(MBB, Pos, DL, TII->get(Mips::LUi), Mips::AT)
-      .addMBB(Tgt, MipsII::MO_ABS_HI);
-    BuildMI(MBB, Pos, DL, TII->get(Mips::ADDiu), Mips::AT)
-      .addReg(Mips::AT).addMBB(Tgt, MipsII::MO_ABS_LO);
-    BuildMI(MBB, Pos, DL, TII->get(Mips::JR)).addReg(Mips::AT, RegState::Kill);
-    NumInstrs = 3;
-  }
-
-  if (Nop) {
-    BuildMI(MBB, Pos, DL, TII->get(Mips::NOP))->setIsInsideBundle();
-    ++NumInstrs;
-  }
-
-  return NumInstrs;
-}
-
 // Replace Br with a branch which has the opposite condition code and a
 // MachineBasicBlock operand MBBOpnd.
 void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br,
                                    DebugLoc DL, MachineBasicBlock *MBBOpnd) {
-  unsigned NewOpc = Mips::GetOppositeBranchOpc(Br->getOpcode());
+  const MipsInstrInfo *TII =
+      static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo());
+  unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());
   const MCInstrDesc &NewDesc = TII->get(NewOpc);
 
   MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
@@ -297,62 +237,202 @@ void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br,
 
   MIB.addMBB(MBBOpnd);
 
+  // Bundle the instruction in the delay slot to the newly created branch
+  // and erase the original branch.
+  assert(Br->isBundledWithSucc());
+  MachineBasicBlock::instr_iterator II(Br);
+  MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
   Br->eraseFromParent();
 }
 
 // Expand branch instructions to long branches.
 void MipsLongBranch::expandToLongBranch(MBBInfo &I) {
-  I.HasLongBranch = true;
-
-  MachineBasicBlock *MBB = I.Br->getParent(), *Tgt = getTargetMBB(*I.Br);
+  MachineBasicBlock::iterator Pos;
+  MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
   DebugLoc DL = I.Br->getDebugLoc();
+  const BasicBlock *BB = MBB->getBasicBlock();
+  MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);
+  MachineBasicBlock *LongBrMBB = MF->CreateMachineBasicBlock(BB);
+
+  const MipsInstrInfo *TII =
+      static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo());
+
+  MF->insert(FallThroughMBB, LongBrMBB);
+  MBB->removeSuccessor(TgtMBB);
+  MBB->addSuccessor(LongBrMBB);
+
+  if (IsPIC) {
+    MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB);
+    MF->insert(FallThroughMBB, BalTgtMBB);
+    LongBrMBB->addSuccessor(BalTgtMBB);
+    BalTgtMBB->addSuccessor(TgtMBB);
+
+    // We must select between the MIPS32r6/MIPS64r6 BAL (which is a normal
+    // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
+    // pseudo-instruction wrapping BGEZAL).
+
+    const MipsSubtarget &Subtarget = TM.getSubtarget<MipsSubtarget>();
+    unsigned BalOp = Subtarget.hasMips32r6() ? Mips::BAL : Mips::BAL_BR;
+
+    if (ABI != MipsSubtarget::N64) {
+      // $longbr:
+      //  addiu $sp, $sp, -8
+      //  sw $ra, 0($sp)
+      //  lui $at, %hi($tgt - $baltgt)
+      //  bal $baltgt
+      //  addiu $at, $at, %lo($tgt - $baltgt)
+      // $baltgt:
+      //  addu $at, $ra, $at
+      //  lw $ra, 0($sp)
+      //  jr $at
+      //  addiu $sp, $sp, 8
+      // $fallthrough:
+      //
+
+      Pos = LongBrMBB->begin();
+
+      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
+        .addReg(Mips::SP).addImm(-8);
+      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW)).addReg(Mips::RA)
+        .addReg(Mips::SP).addImm(0);
+
+      // LUi and ADDiu instructions create 32-bit offset of the target basic
+      // block from the target of BAL instruction.  We cannot use immediate
+      // value for this offset because it cannot be determined accurately when
+      // the program has inline assembly statements.  We therefore use the
+      // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
+      // are resolved during the fixup, so the values will always be correct.
+      //
+      // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)
+      // expressions at this point (it is possible only at the MC layer),
+      // we replace LUi and ADDiu with pseudo instructions
+      // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
+      // blocks as operands to these instructions.  When lowering these pseudo
+      // instructions to LUi and ADDiu in the MC layer, we will create
+      // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
+      // operands to lowered instructions.
+
+      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
+        .addMBB(TgtMBB).addMBB(BalTgtMBB);
+      MIBundleBuilder(*LongBrMBB, Pos)
+          .append(BuildMI(*MF, DL, TII->get(BalOp)).addMBB(BalTgtMBB))
+          .append(BuildMI(*MF, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
+                      .addReg(Mips::AT)
+                      .addMBB(TgtMBB)
+                      .addMBB(BalTgtMBB));
+
+      Pos = BalTgtMBB->begin();
+
+      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
+        .addReg(Mips::RA).addReg(Mips::AT);
+      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
+        .addReg(Mips::SP).addImm(0);
+
+      if (!TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) {
+        MIBundleBuilder(*BalTgtMBB, Pos)
+          .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT))
+          .append(BuildMI(*MF, DL, TII->get(Mips::ADDiu), Mips::SP)
+                  .addReg(Mips::SP).addImm(8));
+      } else {
+        // In NaCl, modifying the sp is not allowed in branch delay slot.
+        BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
+          .addReg(Mips::SP).addImm(8);
+
+        MIBundleBuilder(*BalTgtMBB, Pos)
+          .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT))
+          .append(BuildMI(*MF, DL, TII->get(Mips::NOP)));
+
+        // Bundle-align the target of indirect branch JR.
+        TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
+      }
+    } else {
+      // $longbr:
+      //  daddiu $sp, $sp, -16
+      //  sd $ra, 0($sp)
+      //  daddiu $at, $zero, %hi($tgt - $baltgt)
+      //  dsll $at, $at, 16
+      //  bal $baltgt
+      //  daddiu $at, $at, %lo($tgt - $baltgt)
+      // $baltgt:
+      //  daddu $at, $ra, $at
+      //  ld $ra, 0($sp)
+      //  jr64 $at
+      //  daddiu $sp, $sp, 16
+      // $fallthrough:
+      //
+
+      // We assume the branch is within-function, and that offset is within
+      // +/- 2GB.  High 32 bits will therefore always be zero.
+
+      // Note that this will work even if the offset is negative, because
+      // of the +1 modification that's added in that case.  For example, if the
+      // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
+      //
+      // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
+      //
+      // and the bits [47:32] are zero.  For %highest
+      //
+      // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
+      //
+      // and the bits [63:48] are zero.
+
+      Pos = LongBrMBB->begin();
+
+      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
+        .addReg(Mips::SP_64).addImm(-16);
+      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD)).addReg(Mips::RA_64)
+        .addReg(Mips::SP_64).addImm(0);
+      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
+              Mips::AT_64).addReg(Mips::ZERO_64)
+                          .addMBB(TgtMBB, MipsII::MO_ABS_HI).addMBB(BalTgtMBB);
+      BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
+        .addReg(Mips::AT_64).addImm(16);
+
+      MIBundleBuilder(*LongBrMBB, Pos)
+          .append(BuildMI(*MF, DL, TII->get(BalOp)).addMBB(BalTgtMBB))
+          .append(
+              BuildMI(*MF, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
+                  .addReg(Mips::AT_64)
+                  .addMBB(TgtMBB, MipsII::MO_ABS_LO)
+                  .addMBB(BalTgtMBB));
+
+      Pos = BalTgtMBB->begin();
+
+      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
+        .addReg(Mips::RA_64).addReg(Mips::AT_64);
+      BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
+        .addReg(Mips::SP_64).addImm(0);
+
+      MIBundleBuilder(*BalTgtMBB, Pos)
+        .append(BuildMI(*MF, DL, TII->get(Mips::JR64)).addReg(Mips::AT_64))
+        .append(BuildMI(*MF, DL, TII->get(Mips::DADDiu), Mips::SP_64)
+                .addReg(Mips::SP_64).addImm(16));
+    }
 
-  if (I.Br->isUnconditionalBranch()) {
-    // Unconditional branch before transformation:
-    //   b $tgt
-    //   delay-slot-instr
+    assert(LongBrMBB->size() + BalTgtMBB->size() == LongBranchSeqSize);
+  } else {
+    // $longbr:
+    //  j $tgt
+    //  nop
+    // $fallthrough:
     //
-    // after transformation:
-    //   delay-slot-instr
-    //   lw $at, global_reg_slot
-    //   lw $at, %got($tgt)($at)
-    //   addiu $at, $at, %lo($tgt)
-    //   jr $at
-    //   nop
-    I.Size += (addLongBranch(*MBB, next(Iter(I.Br)), Tgt, DL, true) - 1) * 4;
-
-    // Remove branch and clear InsideBundle bit of the next instruction.
-    next(MachineBasicBlock::instr_iterator(I.Br))->setIsInsideBundle(false);
-    I.Br->eraseFromParent();
-    return;
-  }
+    Pos = LongBrMBB->begin();
+    LongBrMBB->addSuccessor(TgtMBB);
+    MIBundleBuilder(*LongBrMBB, Pos)
+      .append(BuildMI(*MF, DL, TII->get(Mips::J)).addMBB(TgtMBB))
+      .append(BuildMI(*MF, DL, TII->get(Mips::NOP)));
 
-  assert(I.Br->isConditionalBranch() && "Conditional branch expected.");
-
-  // Conditional branch before transformation:
-  //   b cc, $tgt
-  //   delay-slot-instr
-  //  FallThrough:
-  //
-  // after transformation:
-  //   b !cc, FallThrough
-  //   delay-slot-instr
-  //  NewMBB:
-  //   lw $at, global_reg_slot
-  //   lw $at, %got($tgt)($at)
-  //   addiu $at, $at, %lo($tgt)
-  //   jr $at
-  //   noop
-  //  FallThrough:
-
-  MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(MBB->getBasicBlock());
-  MF->insert(next(MachineFunction::iterator(MBB)), NewMBB);
-  MBB->removeSuccessor(Tgt);
-  MBB->addSuccessor(NewMBB);
-  NewMBB->addSuccessor(Tgt);
+    assert(LongBrMBB->size() == LongBranchSeqSize);
+  }
 
-  I.Size += addLongBranch(*NewMBB, NewMBB->begin(), Tgt, DL, true) * 4;
-  replaceBranch(*MBB, I.Br, DL, *MBB->succ_begin());
+  if (I.Br->isUnconditionalBranch()) {
+    // Change branch destination.
+    assert(I.Br->getDesc().getNumOperands() == 1);
+    I.Br->RemoveOperand(0);
+    I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
+  } else
+    // Change branch destination and reverse condition.
+    replaceBranch(*MBB, I.Br, DL, FallThroughMBB);
 }
 
 static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
@@ -367,19 +447,24 @@ static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
 }
 
 bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) {
+  const MipsInstrInfo *TII =
+      static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo());
+
+  const MipsSubtarget &STI = TM.getSubtarget<MipsSubtarget>();
+  if (STI.inMips16Mode() || !STI.enableLongBranchPass())
+    return false;
   if ((TM.getRelocationModel() == Reloc::PIC_) &&
       TM.getSubtarget<MipsSubtarget>().isABI_O32() &&
       F.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
     emitGPDisp(F, TII);
 
   if (SkipLongBranch)
-    return false;
+    return true;
 
   MF = &F;
   initMBBInfo();
 
-  bool IsPIC = (TM.getRelocationModel() == Reloc::PIC_);
-  SmallVector<MBBInfo, 16>::iterator I, E = MBBInfos.end();
+  SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
   bool EverMadeChange = false, MadeChange = true;
 
   while (MadeChange) {
@@ -391,26 +476,45 @@ bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) {
       if (!I->Br || I->HasLongBranch)
         continue;
 
-      int64_t Offset = computeOffset(I->Br);
-
-      if (!ForceLongBranch) {
-        // Check if offset fits into 16-bit immediate field of branches.
-        if ((I->Br->isConditionalBranch() || IsPIC) && isInt<16>(Offset / 4))
-          continue;
+      int ShVal = TM.getSubtarget<MipsSubtarget>().inMicroMipsMode() ? 2 : 4;
+      int64_t Offset = computeOffset(I->Br) / ShVal;
 
-        // Check if offset fits into 26-bit immediate field of jumps (J).
-        if (I->Br->isUnconditionalBranch() && !IsPIC && isInt<26>(Offset / 4))
-          continue;
+      if (TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) {
+        // The offset calculation does not include sandboxing instructions
+        // that will be added later in the MC layer.  Since at this point we
+        // don't know the exact amount of code that "sandboxing" will add, we
+        // conservatively estimate that code will not grow more than 100%.
+        Offset *= 2;
       }
 
-      expandToLongBranch(*I);
+      // Check if offset fits into 16-bit immediate field of branches.
+      if (!ForceLongBranch && isInt<16>(Offset))
+        continue;
+
+      I->HasLongBranch = true;
+      I->Size += LongBranchSeqSize * 4;
       ++LongBranches;
       EverMadeChange = MadeChange = true;
     }
   }
 
-  if (EverMadeChange)
-    MF->RenumberBlocks();
+  if (!EverMadeChange)
+    return true;
+
+  // Compute basic block addresses.
+  if (TM.getRelocationModel() == Reloc::PIC_) {
+    uint64_t Address = 0;
+
+    for (I = MBBInfos.begin(); I != E; Address += I->Size, ++I)
+      I->Address = Address;
+  }
+
+  // Do the expansion.
+  for (I = MBBInfos.begin(); I != E; ++I)
+    if (I->HasLongBranch)
+      expandToLongBranch(*I);
+
+  MF->RenumberBlocks();
 
-  return EverMadeChange;
+  return true;
 }