Home | History | Annotate | Download | only in Mips 
      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 // FIXME:
     14 // 1. Fix pc-region jump instructions which cross 256MB segment boundaries.
     15 // 2. If program has inline assembly statements whose size cannot be
     16 //    determined accurately, load branch target addresses from the GOT.
     17 //===----------------------------------------------------------------------===//
     18 
     19 #define DEBUG_TYPE "mips-long-branch"
     20 
     21 #include "Mips.h"
     22 #include "MCTargetDesc/MipsBaseInfo.h"
     23 #include "MipsTargetMachine.h"
     24 #include "llvm/ADT/Statistic.h"
     25 #include "llvm/CodeGen/MachineFunctionPass.h"
     26 #include "llvm/CodeGen/MachineInstrBuilder.h"
     27 #include "llvm/IR/Function.h"
     28 #include "llvm/Support/CommandLine.h"
     29 #include "llvm/Support/MathExtras.h"
     30 #include "llvm/Target/TargetInstrInfo.h"
     31 #include "llvm/Target/TargetMachine.h"
     32 #include "llvm/Target/TargetRegisterInfo.h"
     33 
     34 using namespace llvm;
     35 
     36 STATISTIC(LongBranches, "Number of long branches.");
     37 
     38 static cl::opt<bool> SkipLongBranch(
     39   "skip-mips-long-branch",
     40   cl::init(false),
     41   cl::desc("MIPS: Skip long branch pass."),
     42   cl::Hidden);
     43 
     44 static cl::opt<bool> ForceLongBranch(
     45   "force-mips-long-branch",
     46   cl::init(false),
     47   cl::desc("MIPS: Expand all branches to long format."),
     48   cl::Hidden);
     49 
     50 namespace {
     51   typedef MachineBasicBlock::iterator Iter;
     52   typedef MachineBasicBlock::reverse_iterator ReverseIter;
     53 
     54   struct MBBInfo {
     55     uint64_t Size, Address;
     56     bool HasLongBranch;
     57     MachineInstr *Br;
     58 
     59     MBBInfo() : Size(0), HasLongBranch(false), Br(0) {}
     60   };
     61 
     62   class MipsLongBranch : public MachineFunctionPass {
     63 
     64   public:
     65     static char ID;
     66     MipsLongBranch(TargetMachine &tm)
     67       : MachineFunctionPass(ID), TM(tm),
     68         IsPIC(TM.getRelocationModel() == Reloc::PIC_),
     69         ABI(TM.getSubtarget<MipsSubtarget>().getTargetABI()),
     70         LongBranchSeqSize(!IsPIC ? 2 : (ABI == MipsSubtarget::N64 ? 13 : 9)) {}
     71 
     72     virtual const char *getPassName() const {
     73       return "Mips Long Branch";
     74     }
     75 
     76     bool runOnMachineFunction(MachineFunction &F);
     77 
     78   private:
     79     void splitMBB(MachineBasicBlock *MBB);
     80     void initMBBInfo();
     81     int64_t computeOffset(const MachineInstr *Br);
     82     void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL,
     83                        MachineBasicBlock *MBBOpnd);
     84     void expandToLongBranch(MBBInfo &Info);
     85 
     86     const TargetMachine &TM;
     87     MachineFunction *MF;
     88     SmallVector<MBBInfo, 16> MBBInfos;
     89     bool IsPIC;
     90     unsigned ABI;
     91     unsigned LongBranchSeqSize;
     92   };
     93 
     94   char MipsLongBranch::ID = 0;
     95 } // end of anonymous namespace
     96 
     97 /// createMipsLongBranchPass - Returns a pass that converts branches to long
     98 /// branches.
     99 FunctionPass *llvm::createMipsLongBranchPass(MipsTargetMachine &tm) {
    100   return new MipsLongBranch(tm);
    101 }
    102 
    103 /// Iterate over list of Br's operands and search for a MachineBasicBlock
    104 /// operand.
    105 static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
    106   for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
    107     const MachineOperand &MO = Br.getOperand(I);
    108 
    109     if (MO.isMBB())
    110       return MO.getMBB();
    111   }
    112 
    113   assert(false && "This instruction does not have an MBB operand.");
    114   return 0;
    115 }
    116 
    117 // Traverse the list of instructions backwards until a non-debug instruction is
    118 // found or it reaches E.
    119 static ReverseIter getNonDebugInstr(ReverseIter B, ReverseIter E) {
    120   for (; B != E; ++B)
    121     if (!B->isDebugValue())
    122       return B;
    123 
    124   return E;
    125 }
    126 
    127 // Split MBB if it has two direct jumps/branches.
    128 void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) {
    129   ReverseIter End = MBB->rend();
    130   ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
    131 
    132   // Return if MBB has no branch instructions.
    133   if ((LastBr == End) ||
    134       (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
    135     return;
    136 
    137   ReverseIter FirstBr = getNonDebugInstr(llvm::next(LastBr), End);
    138 
    139   // MBB has only one branch instruction if FirstBr is not a branch
    140   // instruction.
    141   if ((FirstBr == End) ||
    142       (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
    143     return;
    144 
    145   assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
    146 
    147   // Create a new MBB. Move instructions in MBB to the newly created MBB.
    148   MachineBasicBlock *NewMBB =
    149     MF->CreateMachineBasicBlock(MBB->getBasicBlock());
    150 
    151   // Insert NewMBB and fix control flow.
    152   MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
    153   NewMBB->transferSuccessors(MBB);
    154   NewMBB->removeSuccessor(Tgt);
    155   MBB->addSuccessor(NewMBB);
    156   MBB->addSuccessor(Tgt);
    157   MF->insert(llvm::next(MachineFunction::iterator(MBB)), NewMBB);
    158 
    159   NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end());
    160 }
    161 
    162 // Fill MBBInfos.
    163 void MipsLongBranch::initMBBInfo() {
    164   // Split the MBBs if they have two branches. Each basic block should have at
    165   // most one branch after this loop is executed.
    166   for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E;)
    167     splitMBB(I++);
    168 
    169   MF->RenumberBlocks();
    170   MBBInfos.clear();
    171   MBBInfos.resize(MF->size());
    172 
    173   const MipsInstrInfo *TII =
    174     static_cast<const MipsInstrInfo*>(TM.getInstrInfo());
    175   for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
    176     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
    177 
    178     // Compute size of MBB.
    179     for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin();
    180          MI != MBB->instr_end(); ++MI)
    181       MBBInfos[I].Size += TII->GetInstSizeInBytes(&*MI);
    182 
    183     // Search for MBB's branch instruction.
    184     ReverseIter End = MBB->rend();
    185     ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
    186 
    187     if ((Br != End) && !Br->isIndirectBranch() &&
    188         (Br->isConditionalBranch() ||
    189          (Br->isUnconditionalBranch() &&
    190           TM.getRelocationModel() == Reloc::PIC_)))
    191       MBBInfos[I].Br = (++Br).base();
    192   }
    193 }
    194 
    195 // Compute offset of branch in number of bytes.
    196 int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) {
    197   int64_t Offset = 0;
    198   int ThisMBB = Br->getParent()->getNumber();
    199   int TargetMBB = getTargetMBB(*Br)->getNumber();
    200 
    201   // Compute offset of a forward branch.
    202   if (ThisMBB < TargetMBB) {
    203     for (int N = ThisMBB + 1; N < TargetMBB; ++N)
    204       Offset += MBBInfos[N].Size;
    205 
    206     return Offset + 4;
    207   }
    208 
    209   // Compute offset of a backward branch.
    210   for (int N = ThisMBB; N >= TargetMBB; --N)
    211     Offset += MBBInfos[N].Size;
    212 
    213   return -Offset + 4;
    214 }
    215 
    216 // Replace Br with a branch which has the opposite condition code and a
    217 // MachineBasicBlock operand MBBOpnd.
    218 void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br,
    219                                    DebugLoc DL, MachineBasicBlock *MBBOpnd) {
    220   const MipsInstrInfo *TII =
    221     static_cast<const MipsInstrInfo*>(TM.getInstrInfo());
    222   unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());
    223   const MCInstrDesc &NewDesc = TII->get(NewOpc);
    224 
    225   MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
    226 
    227   for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
    228     MachineOperand &MO = Br->getOperand(I);
    229 
    230     if (!MO.isReg()) {
    231       assert(MO.isMBB() && "MBB operand expected.");
    232       break;
    233     }
    234 
    235     MIB.addReg(MO.getReg());
    236   }
    237 
    238   MIB.addMBB(MBBOpnd);
    239 
    240   Br->eraseFromParent();
    241 }
    242 
    243 // Expand branch instructions to long branches.
    244 void MipsLongBranch::expandToLongBranch(MBBInfo &I) {
    245   MachineBasicBlock::iterator Pos;
    246   MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
    247   DebugLoc DL = I.Br->getDebugLoc();
    248   const BasicBlock *BB = MBB->getBasicBlock();
    249   MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);
    250   MachineBasicBlock *LongBrMBB = MF->CreateMachineBasicBlock(BB);
    251 
    252   const MipsInstrInfo *TII =
    253     static_cast<const MipsInstrInfo*>(TM.getInstrInfo());
    254 
    255   MF->insert(FallThroughMBB, LongBrMBB);
    256   MBB->removeSuccessor(TgtMBB);
    257   MBB->addSuccessor(LongBrMBB);
    258 
    259   if (IsPIC) {
    260     MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB);
    261     MF->insert(FallThroughMBB, BalTgtMBB);
    262     LongBrMBB->addSuccessor(BalTgtMBB);
    263     BalTgtMBB->addSuccessor(TgtMBB);
    264 
    265     int64_t TgtAddress = MBBInfos[TgtMBB->getNumber()].Address;
    266     unsigned BalTgtMBBSize = 5;
    267     int64_t Offset = TgtAddress - (I.Address + I.Size - BalTgtMBBSize * 4);
    268     int64_t Lo = SignExtend64<16>(Offset & 0xffff);
    269     int64_t Hi = SignExtend64<16>(((Offset + 0x8000) >> 16) & 0xffff);
    270 
    271     if (ABI != MipsSubtarget::N64) {
    272       // $longbr:
    273       //  addiu $sp, $sp, -8
    274       //  sw $ra, 0($sp)
    275       //  bal $baltgt
    276       //  lui $at, %hi($tgt - $baltgt)
    277       // $baltgt:
    278       //  addiu $at, $at, %lo($tgt - $baltgt)
    279       //  addu $at, $ra, $at
    280       //  lw $ra, 0($sp)
    281       //  jr $at
    282       //  addiu $sp, $sp, 8
    283       // $fallthrough:
    284       //
    285 
    286       Pos = LongBrMBB->begin();
    287 
    288       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
    289         .addReg(Mips::SP).addImm(-8);
    290       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW)).addReg(Mips::RA)
    291         .addReg(Mips::SP).addImm(0);
    292 
    293       MIBundleBuilder(*LongBrMBB, Pos)
    294         .append(BuildMI(*MF, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB))
    295         .append(BuildMI(*MF, DL, TII->get(Mips::LUi), Mips::AT).addImm(Hi));
    296 
    297       Pos = BalTgtMBB->begin();
    298 
    299       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::AT)
    300         .addReg(Mips::AT).addImm(Lo);
    301       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
    302         .addReg(Mips::RA).addReg(Mips::AT);
    303       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
    304         .addReg(Mips::SP).addImm(0);
    305 
    306       MIBundleBuilder(*BalTgtMBB, Pos)
    307         .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT))
    308         .append(BuildMI(*MF, DL, TII->get(Mips::ADDiu), Mips::SP)
    309                 .addReg(Mips::SP).addImm(8));
    310     } else {
    311       // $longbr:
    312       //  daddiu $sp, $sp, -16
    313       //  sd $ra, 0($sp)
    314       //  lui64 $at, %highest($tgt - $baltgt)
    315       //  daddiu $at, $at, %higher($tgt - $baltgt)
    316       //  dsll $at, $at, 16
    317       //  daddiu $at, $at, %hi($tgt - $baltgt)
    318       //  bal $baltgt
    319       //  dsll $at, $at, 16
    320       // $baltgt:
    321       //  daddiu $at, $at, %lo($tgt - $baltgt)
    322       //  daddu $at, $ra, $at
    323       //  ld $ra, 0($sp)
    324       //  jr64 $at
    325       //  daddiu $sp, $sp, 16
    326       // $fallthrough:
    327       //
    328 
    329       int64_t Higher = SignExtend64<16>(((Offset + 0x80008000) >> 32) & 0xffff);
    330       int64_t Highest =
    331         SignExtend64<16>(((Offset + 0x800080008000LL) >> 48) & 0xffff);
    332 
    333       Pos = LongBrMBB->begin();
    334 
    335       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
    336         .addReg(Mips::SP_64).addImm(-16);
    337       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD)).addReg(Mips::RA_64)
    338         .addReg(Mips::SP_64).addImm(0);
    339       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LUi64), Mips::AT_64)
    340         .addImm(Highest);
    341       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64)
    342         .addReg(Mips::AT_64).addImm(Higher);
    343       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
    344         .addReg(Mips::AT_64).addImm(16);
    345       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64)
    346         .addReg(Mips::AT_64).addImm(Hi);
    347 
    348       MIBundleBuilder(*LongBrMBB, Pos)
    349         .append(BuildMI(*MF, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB))
    350         .append(BuildMI(*MF, DL, TII->get(Mips::DSLL), Mips::AT_64)
    351                 .addReg(Mips::AT_64).addImm(16));
    352 
    353       Pos = BalTgtMBB->begin();
    354 
    355       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64)
    356         .addReg(Mips::AT_64).addImm(Lo);
    357       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
    358         .addReg(Mips::RA_64).addReg(Mips::AT_64);
    359       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
    360         .addReg(Mips::SP_64).addImm(0);
    361 
    362       MIBundleBuilder(*BalTgtMBB, Pos)
    363         .append(BuildMI(*MF, DL, TII->get(Mips::JR64)).addReg(Mips::AT_64))
    364         .append(BuildMI(*MF, DL, TII->get(Mips::DADDiu), Mips::SP_64)
    365                 .addReg(Mips::SP_64).addImm(16));
    366     }
    367 
    368     assert(BalTgtMBBSize == BalTgtMBB->size());
    369     assert(LongBrMBB->size() + BalTgtMBBSize == LongBranchSeqSize);
    370   } else {
    371     // $longbr:
    372     //  j $tgt
    373     //  nop
    374     // $fallthrough:
    375     //
    376     Pos = LongBrMBB->begin();
    377     LongBrMBB->addSuccessor(TgtMBB);
    378     MIBundleBuilder(*LongBrMBB, Pos)
    379       .append(BuildMI(*MF, DL, TII->get(Mips::J)).addMBB(TgtMBB))
    380       .append(BuildMI(*MF, DL, TII->get(Mips::NOP)));
    381 
    382     assert(LongBrMBB->size() == LongBranchSeqSize);
    383   }
    384 
    385   if (I.Br->isUnconditionalBranch()) {
    386     // Change branch destination.
    387     assert(I.Br->getDesc().getNumOperands() == 1);
    388     I.Br->RemoveOperand(0);
    389     I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
    390   } else
    391     // Change branch destination and reverse condition.
    392     replaceBranch(*MBB, I.Br, DL, FallThroughMBB);
    393 }
    394 
    395 static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
    396   MachineBasicBlock &MBB = F.front();
    397   MachineBasicBlock::iterator I = MBB.begin();
    398   DebugLoc DL = MBB.findDebugLoc(MBB.begin());
    399   BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
    400     .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
    401   BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
    402     .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
    403   MBB.removeLiveIn(Mips::V0);
    404 }
    405 
    406 bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) {
    407   const MipsInstrInfo *TII =
    408     static_cast<const MipsInstrInfo*>(TM.getInstrInfo());
    409 
    410   if (TM.getSubtarget<MipsSubtarget>().inMips16Mode())
    411     return false;
    412   if ((TM.getRelocationModel() == Reloc::PIC_) &&
    413       TM.getSubtarget<MipsSubtarget>().isABI_O32() &&
    414       F.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
    415     emitGPDisp(F, TII);
    416 
    417   if (SkipLongBranch)
    418     return true;
    419 
    420   MF = &F;
    421   initMBBInfo();
    422 
    423   SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
    424   bool EverMadeChange = false, MadeChange = true;
    425 
    426   while (MadeChange) {
    427     MadeChange = false;
    428 
    429     for (I = MBBInfos.begin(); I != E; ++I) {
    430       // Skip if this MBB doesn't have a branch or the branch has already been
    431       // converted to a long branch.
    432       if (!I->Br || I->HasLongBranch)
    433         continue;
    434 
    435       // Check if offset fits into 16-bit immediate field of branches.
    436       if (!ForceLongBranch && isInt<16>(computeOffset(I->Br) / 4))
    437         continue;
    438 
    439       I->HasLongBranch = true;
    440       I->Size += LongBranchSeqSize * 4;
    441       ++LongBranches;
    442       EverMadeChange = MadeChange = true;
    443     }
    444   }
    445 
    446   if (!EverMadeChange)
    447     return true;
    448 
    449   // Compute basic block addresses.
    450   if (TM.getRelocationModel() == Reloc::PIC_) {
    451     uint64_t Address = 0;
    452 
    453     for (I = MBBInfos.begin(); I != E; Address += I->Size, ++I)
    454       I->Address = Address;
    455   }
    456 
    457   // Do the expansion.
    458   for (I = MBBInfos.begin(); I != E; ++I)
    459     if (I->HasLongBranch)
    460       expandToLongBranch(*I);
    461 
    462   MF->RenumberBlocks();
    463 
    464   return true;
    465 }
    466