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

   1 //===----------------------- MipsBranchExpansion.cpp ----------------------===//
   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 /// \file
  10 ///
  11 /// This pass do two things:
  12 /// - it expands a branch or jump instruction into a long branch if its offset
  13 ///   is too large to fit into its immediate field,
  14 /// - it inserts nops to prevent forbidden slot hazards.
  15 ///
  16 /// The reason why this pass combines these two tasks is that one of these two
  17 /// tasks can break the result of the previous one.
  18 ///
  19 /// Example of that is a situation where at first, no branch should be expanded,
  20 /// but after adding at least one nop somewhere in the code to prevent a
  21 /// forbidden slot hazard, offset of some branches may go out of range. In that
  22 /// case it is necessary to check again if there is some branch that needs
  23 /// expansion. On the other hand, expanding some branch may cause a control
  24 /// transfer instruction to appear in the forbidden slot, which is a hazard that
  25 /// should be fixed. This pass alternates between this two tasks untill no
  26 /// changes are made. Only then we can be sure that all branches are expanded
  27 /// properly, and no hazard situations exist.
  28 ///
  29 /// Regarding branch expanding:
  30 ///
  31 /// When branch instruction like beqzc or bnezc has offset that is too large
  32 /// to fit into its immediate field, it has to be expanded to another
  33 /// instruction or series of instructions.
  34 ///
  35 /// FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries.
  36 /// TODO: Handle out of range bc, b (pseudo) instructions.
  37 ///
  38 /// Regarding compact branch hazard prevention:
  39 ///
  40 /// Hazards handled: forbidden slots for MIPSR6.
  41 ///
  42 /// A forbidden slot hazard occurs when a compact branch instruction is executed
  43 /// and the adjacent instruction in memory is a control transfer instruction
  44 /// such as a branch or jump, ERET, ERETNC, DERET, WAIT and PAUSE.
  45 ///
  46 /// For example:
  47 ///
  48 /// 0x8004      bnec    a1,v0,<P+0x18>
  49 /// 0x8008      beqc    a1,a2,<P+0x54>
  50 ///
  51 /// In such cases, the processor is required to signal a Reserved Instruction
  52 /// exception.
  53 ///
  54 /// Here, if the instruction at 0x8004 is executed, the processor will raise an
  55 /// exception as there is a control transfer instruction at 0x8008.
  56 ///
  57 /// There are two sources of forbidden slot hazards:
  58 ///
  59 /// A) A previous pass has created a compact branch directly.
  60 /// B) Transforming a delay slot branch into compact branch. This case can be
  61 ///    difficult to process as lookahead for hazards is insufficient, as
  62 ///    backwards delay slot fillling can also produce hazards in previously
  63 ///    processed instuctions.
  64 ///
  65 /// In future this pass can be extended (or new pass can be created) to handle
  66 /// other pipeline hazards, such as various MIPS1 hazards, processor errata that
  67 /// require instruction reorganization, etc.
  68 ///
  69 /// This pass has to run after the delay slot filler as that pass can introduce
  70 /// pipeline hazards such as compact branch hazard, hence the existing hazard
  71 /// recognizer is not suitable.
  72 ///
  73 //===----------------------------------------------------------------------===//
  74
  75 #include "MCTargetDesc/MipsABIInfo.h"
  76 #include "MCTargetDesc/MipsBaseInfo.h"
  77 #include "MCTargetDesc/MipsMCNaCl.h"
  78 #include "MCTargetDesc/MipsMCTargetDesc.h"
  79 #include "Mips.h"
  80 #include "MipsInstrInfo.h"
  81 #include "MipsMachineFunction.h"
  82 #include "MipsSubtarget.h"
  83 #include "MipsTargetMachine.h"
  84 #include "llvm/ADT/SmallVector.h"
  85 #include "llvm/ADT/Statistic.h"
  86 #include "llvm/ADT/StringRef.h"
  87 #include "llvm/CodeGen/MachineBasicBlock.h"
  88 #include "llvm/CodeGen/MachineFunction.h"
  89 #include "llvm/CodeGen/MachineFunctionPass.h"
  90 #include "llvm/CodeGen/MachineInstr.h"
  91 #include "llvm/CodeGen/MachineInstrBuilder.h"
  92 #include "llvm/CodeGen/MachineModuleInfo.h"
  93 #include "llvm/CodeGen/MachineOperand.h"
  94 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  95 #include "llvm/IR/DebugLoc.h"
  96 #include "llvm/Support/CommandLine.h"
  97 #include "llvm/Support/ErrorHandling.h"
  98 #include "llvm/Support/MathExtras.h"
  99 #include "llvm/Target/TargetMachine.h"
 100 #include <algorithm>
 101 #include <cassert>
 102 #include <cstdint>
 103 #include <iterator>
 104 #include <utility>
 105
 106 using namespace llvm;
 107
 108 #define DEBUG_TYPE "mips-branch-expansion"
 109
 110 STATISTIC(NumInsertedNops, "Number of nops inserted");
 111 STATISTIC(LongBranches, "Number of long branches.");
 112
 113 static cl::opt<bool>
 114     SkipLongBranch("skip-mips-long-branch", cl::init(false),
 115                    cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden);
 116
 117 static cl::opt<bool>
 118     ForceLongBranch("force-mips-long-branch", cl::init(false),
 119                     cl::desc("MIPS: Expand all branches to long format."),
 120                     cl::Hidden);
 121
 122 namespace {
 123
 124 using Iter = MachineBasicBlock::iterator;
 125 using ReverseIter = MachineBasicBlock::reverse_iterator;
 126
 127 struct MBBInfo {
 128   uint64_t Size = 0;
 129   bool HasLongBranch = false;
 130   MachineInstr *Br = nullptr;
 131   uint64_t Offset = 0;
 132   MBBInfo() = default;
 133 };
 134
 135 class MipsBranchExpansion : public MachineFunctionPass {
 136 public:
 137   static char ID;
 138
 139   MipsBranchExpansion() : MachineFunctionPass(ID), ABI(MipsABIInfo::Unknown()) {
 140     initializeMipsBranchExpansionPass(*PassRegistry::getPassRegistry());
 141   }
 142
 143   StringRef getPassName() const override {
 144     return "Mips Branch Expansion Pass";
 145   }
 146
 147   bool runOnMachineFunction(MachineFunction &F) override;
 148
 149   MachineFunctionProperties getRequiredProperties() const override {
 150     return MachineFunctionProperties().set(
 151         MachineFunctionProperties::Property::NoVRegs);
 152   }
 153
 154 private:
 155   void splitMBB(MachineBasicBlock *MBB);
 156   void initMBBInfo();
 157   int64_t computeOffset(const MachineInstr *Br);
 158   uint64_t computeOffsetFromTheBeginning(int MBB);
 159   void replaceBranch(MachineBasicBlock &MBB, Iter Br, const DebugLoc &DL,
 160                      MachineBasicBlock *MBBOpnd);
 161   bool buildProperJumpMI(MachineBasicBlock *MBB,
 162                          MachineBasicBlock::iterator Pos, DebugLoc DL);
 163   void expandToLongBranch(MBBInfo &Info);
 164   bool handleForbiddenSlot();
 165   bool handlePossibleLongBranch();
 166
 167   const MipsSubtarget *STI;
 168   const MipsInstrInfo *TII;
 169
 170   MachineFunction *MFp;
 171   SmallVector<MBBInfo, 16> MBBInfos;
 172   bool IsPIC;
 173   MipsABIInfo ABI;
 174   bool ForceLongBranchFirstPass = false;
 175 };
 176
 177 } // end of anonymous namespace
 178
 179 char MipsBranchExpansion::ID = 0;
 180
 181 INITIALIZE_PASS(MipsBranchExpansion, DEBUG_TYPE,
 182                 "Expand out of range branch instructions and fix forbidden"
 183                 " slot hazards",
 184                 false, false)
 185
 186 /// Returns a pass that clears pipeline hazards.
 187 FunctionPass *llvm::createMipsBranchExpansion() {
 188   return new MipsBranchExpansion();
 189 }
 190
 191 // Find the next real instruction from the current position in current basic
 192 // block.
 193 static Iter getNextMachineInstrInBB(Iter Position) {
 194   Iter I = Position, E = Position->getParent()->end();
 195   I = std::find_if_not(I, E,
 196                        [](const Iter &Insn) { return Insn->isTransient(); });
 197
 198   return I;
 199 }
 200
 201 // Find the next real instruction from the current position, looking through
 202 // basic block boundaries.
 203 static std::pair<Iter, bool> getNextMachineInstr(Iter Position,
 204                                                  MachineBasicBlock *Parent) {
 205   if (Position == Parent->end()) {
 206     do {
 207       MachineBasicBlock *Succ = Parent->getNextNode();
 208       if (Succ != nullptr && Parent->isSuccessor(Succ)) {
 209         Position = Succ->begin();
 210         Parent = Succ;
 211       } else {
 212         return std::make_pair(Position, true);
 213       }
 214     } while (Parent->empty());
 215   }
 216
 217   Iter Instr = getNextMachineInstrInBB(Position);
 218   if (Instr == Parent->end()) {
 219     return getNextMachineInstr(Instr, Parent);
 220   }
 221   return std::make_pair(Instr, false);
 222 }
 223
 224 /// Iterate over list of Br's operands and search for a MachineBasicBlock
 225 /// operand.
 226 static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
 227   for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
 228     const MachineOperand &MO = Br.getOperand(I);
 229
 230     if (MO.isMBB())
 231       return MO.getMBB();
 232   }
 233
 234   llvm_unreachable("This instruction does not have an MBB operand.");
 235 }
 236
 237 // Traverse the list of instructions backwards until a non-debug instruction is
 238 // found or it reaches E.
 239 static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E) {
 240   for (; B != E; ++B)
 241     if (!B->isDebugInstr())
 242       return B;
 243
 244   return E;
 245 }
 246
 247 // Split MBB if it has two direct jumps/branches.
 248 void MipsBranchExpansion::splitMBB(MachineBasicBlock *MBB) {
 249   ReverseIter End = MBB->rend();
 250   ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
 251
 252   // Return if MBB has no branch instructions.
 253   if ((LastBr == End) ||
 254       (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
 255     return;
 256
 257   ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End);
 258
 259   // MBB has only one branch instruction if FirstBr is not a branch
 260   // instruction.
 261   if ((FirstBr == End) ||
 262       (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
 263     return;
 264
 265   assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
 266
 267   // Create a new MBB. Move instructions in MBB to the newly created MBB.
 268   MachineBasicBlock *NewMBB =
 269       MFp->CreateMachineBasicBlock(MBB->getBasicBlock());
 270
 271   // Insert NewMBB and fix control flow.
 272   MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
 273   NewMBB->transferSuccessors(MBB);
 274   if (Tgt != getTargetMBB(*LastBr))
 275     NewMBB->removeSuccessor(Tgt, true);
 276   MBB->addSuccessor(NewMBB);
 277   MBB->addSuccessor(Tgt);
 278   MFp->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
 279
 280   NewMBB->splice(NewMBB->end(), MBB, LastBr.getReverse(), MBB->end());
 281 }
 282
 283 // Fill MBBInfos.
 284 void MipsBranchExpansion::initMBBInfo() {
 285   // Split the MBBs if they have two branches. Each basic block should have at
 286   // most one branch after this loop is executed.
 287   for (auto &MBB : *MFp)
 288     splitMBB(&MBB);
 289
 290   MFp->RenumberBlocks();
 291   MBBInfos.clear();
 292   MBBInfos.resize(MFp->size());
 293
 294   for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
 295     MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
 296
 297     // Compute size of MBB.
 298     for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin();
 299          MI != MBB->instr_end(); ++MI)
 300       MBBInfos[I].Size += TII->getInstSizeInBytes(*MI);
 301   }
 302 }
 303
 304 // Compute offset of branch in number of bytes.
 305 int64_t MipsBranchExpansion::computeOffset(const MachineInstr *Br) {
 306   int64_t Offset = 0;
 307   int ThisMBB = Br->getParent()->getNumber();
 308   int TargetMBB = getTargetMBB(*Br)->getNumber();
 309
 310   // Compute offset of a forward branch.
 311   if (ThisMBB < TargetMBB) {
 312     for (int N = ThisMBB + 1; N < TargetMBB; ++N)
 313       Offset += MBBInfos[N].Size;
 314
 315     return Offset + 4;
 316   }
 317
 318   // Compute offset of a backward branch.
 319   for (int N = ThisMBB; N >= TargetMBB; --N)
 320     Offset += MBBInfos[N].Size;
 321
 322   return -Offset + 4;
 323 }
 324
 325 // Returns the distance in bytes up until MBB
 326 uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(int MBB) {
 327   uint64_t Offset = 0;
 328   for (int N = 0; N < MBB; ++N)
 329     Offset += MBBInfos[N].Size;
 330   return Offset;
 331 }
 332
 333 // Replace Br with a branch which has the opposite condition code and a
 334 // MachineBasicBlock operand MBBOpnd.
 335 void MipsBranchExpansion::replaceBranch(MachineBasicBlock &MBB, Iter Br,
 336                                         const DebugLoc &DL,
 337                                         MachineBasicBlock *MBBOpnd) {
 338   unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());
 339   const MCInstrDesc &NewDesc = TII->get(NewOpc);
 340
 341   MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
 342
 343   for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
 344     MachineOperand &MO = Br->getOperand(I);
 345
 346     if (!MO.isReg()) {
 347       assert(MO.isMBB() && "MBB operand expected.");
 348       break;
 349     }
 350
 351     MIB.addReg(MO.getReg());
 352   }
 353
 354   MIB.addMBB(MBBOpnd);
 355
 356   if (Br->hasDelaySlot()) {
 357     // Bundle the instruction in the delay slot to the newly created branch
 358     // and erase the original branch.
 359     assert(Br->isBundledWithSucc());
 360     MachineBasicBlock::instr_iterator II = Br.getInstrIterator();
 361     MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
 362   }
 363   Br->eraseFromParent();
 364 }
 365
 366 bool MipsBranchExpansion::buildProperJumpMI(MachineBasicBlock *MBB,
 367                                             MachineBasicBlock::iterator Pos,
 368                                             DebugLoc DL) {
 369   bool HasR6 = ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
 370   bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
 371
 372   unsigned JR = ABI.IsN64() ? Mips::JR64 : Mips::JR;
 373   unsigned JIC = ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
 374   unsigned JR_HB = ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
 375   unsigned JR_HB_R6 = ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
 376
 377   unsigned JumpOp;
 378   if (STI->useIndirectJumpsHazard())
 379     JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
 380   else
 381     JumpOp = HasR6 ? JIC : JR;
 382
 383   if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
 384     JumpOp = Mips::JIC_MMR6;
 385
 386   unsigned ATReg = ABI.IsN64() ? Mips::AT_64 : Mips::AT;
 387   MachineInstrBuilder Instr =
 388       BuildMI(*MBB, Pos, DL, TII->get(JumpOp)).addReg(ATReg);
 389   if (AddImm)
 390     Instr.addImm(0);
 391
 392   return !AddImm;
 393 }
 394
 395 // Expand branch instructions to long branches.
 396 // TODO: This function has to be fixed for beqz16 and bnez16, because it
 397 // currently assumes that all branches have 16-bit offsets, and will produce
 398 // wrong code if branches whose allowed offsets are [-128, -126, ..., 126]
 399 // are present.
 400 void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) {
 401   MachineBasicBlock::iterator Pos;
 402   MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
 403   DebugLoc DL = I.Br->getDebugLoc();
 404   const BasicBlock *BB = MBB->getBasicBlock();
 405   MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);
 406   MachineBasicBlock *LongBrMBB = MFp->CreateMachineBasicBlock(BB);
 407
 408   MFp->insert(FallThroughMBB, LongBrMBB);
 409   MBB->replaceSuccessor(TgtMBB, LongBrMBB);
 410
 411   if (IsPIC) {
 412     MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);
 413     MFp->insert(FallThroughMBB, BalTgtMBB);
 414     LongBrMBB->addSuccessor(BalTgtMBB);
 415     BalTgtMBB->addSuccessor(TgtMBB);
 416
 417     // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal
 418     // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
 419     // pseudo-instruction wrapping BGEZAL).
 420     const unsigned BalOp =
 421         STI->hasMips32r6()
 422             ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
 423             : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
 424
 425     if (!ABI.IsN64()) {
 426       // Pre R6:
 427       // $longbr:
 428       //  addiu $sp, $sp, -8
 429       //  sw $ra, 0($sp)
 430       //  lui $at, %hi($tgt - $baltgt)
 431       //  bal $baltgt
 432       //  addiu $at, $at, %lo($tgt - $baltgt)
 433       // $baltgt:
 434       //  addu $at, $ra, $at
 435       //  lw $ra, 0($sp)
 436       //  jr $at
 437       //  addiu $sp, $sp, 8
 438       // $fallthrough:
 439       //
 440
 441       // R6:
 442       // $longbr:
 443       //  addiu $sp, $sp, -8
 444       //  sw $ra, 0($sp)
 445       //  lui $at, %hi($tgt - $baltgt)
 446       //  addiu $at, $at, %lo($tgt - $baltgt)
 447       //  balc $baltgt
 448       // $baltgt:
 449       //  addu $at, $ra, $at
 450       //  lw $ra, 0($sp)
 451       //  addiu $sp, $sp, 8
 452       //  jic $at, 0
 453       // $fallthrough:
 454
 455       Pos = LongBrMBB->begin();
 456
 457       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
 458           .addReg(Mips::SP)
 459           .addImm(-8);
 460       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW))
 461           .addReg(Mips::RA)
 462           .addReg(Mips::SP)
 463           .addImm(0);
 464
 465       // LUi and ADDiu instructions create 32-bit offset of the target basic
 466       // block from the target of BAL(C) instruction.  We cannot use immediate
 467       // value for this offset because it cannot be determined accurately when
 468       // the program has inline assembly statements.  We therefore use the
 469       // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
 470       // are resolved during the fixup, so the values will always be correct.
 471       //
 472       // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)
 473       // expressions at this point (it is possible only at the MC layer),
 474       // we replace LUi and ADDiu with pseudo instructions
 475       // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
 476       // blocks as operands to these instructions.  When lowering these pseudo
 477       // instructions to LUi and ADDiu in the MC layer, we will create
 478       // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
 479       // operands to lowered instructions.
 480
 481       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
 482           .addMBB(TgtMBB, MipsII::MO_ABS_HI)
 483           .addMBB(BalTgtMBB);
 484
 485       MachineInstrBuilder BalInstr =
 486           BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
 487       MachineInstrBuilder ADDiuInstr =
 488           BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
 489               .addReg(Mips::AT)
 490               .addMBB(TgtMBB, MipsII::MO_ABS_LO)
 491               .addMBB(BalTgtMBB);
 492       if (STI->hasMips32r6()) {
 493         LongBrMBB->insert(Pos, ADDiuInstr);
 494         LongBrMBB->insert(Pos, BalInstr);
 495       } else {
 496         LongBrMBB->insert(Pos, BalInstr);
 497         LongBrMBB->insert(Pos, ADDiuInstr);
 498         LongBrMBB->rbegin()->bundleWithPred();
 499       }
 500
 501       Pos = BalTgtMBB->begin();
 502
 503       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
 504           .addReg(Mips::RA)
 505           .addReg(Mips::AT);
 506       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
 507           .addReg(Mips::SP)
 508           .addImm(0);
 509       if (STI->isTargetNaCl())
 510         // Bundle-align the target of indirect branch JR.
 511         TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
 512
 513       // In NaCl, modifying the sp is not allowed in branch delay slot.
 514       // For MIPS32R6, we can skip using a delay slot branch.
 515       bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
 516
 517       if (STI->isTargetNaCl() || !hasDelaySlot) {
 518         BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::ADDiu), Mips::SP)
 519             .addReg(Mips::SP)
 520             .addImm(8);
 521       }
 522       if (hasDelaySlot) {
 523         if (STI->isTargetNaCl()) {
 524           BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::NOP));
 525         } else {
 526           BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
 527               .addReg(Mips::SP)
 528               .addImm(8);
 529         }
 530         BalTgtMBB->rbegin()->bundleWithPred();
 531       }
 532     } else {
 533       // Pre R6:
 534       // $longbr:
 535       //  daddiu $sp, $sp, -16
 536       //  sd $ra, 0($sp)
 537       //  daddiu $at, $zero, %hi($tgt - $baltgt)
 538       //  dsll $at, $at, 16
 539       //  bal $baltgt
 540       //  daddiu $at, $at, %lo($tgt - $baltgt)
 541       // $baltgt:
 542       //  daddu $at, $ra, $at
 543       //  ld $ra, 0($sp)
 544       //  jr64 $at
 545       //  daddiu $sp, $sp, 16
 546       // $fallthrough:
 547
 548       // R6:
 549       // $longbr:
 550       //  daddiu $sp, $sp, -16
 551       //  sd $ra, 0($sp)
 552       //  daddiu $at, $zero, %hi($tgt - $baltgt)
 553       //  dsll $at, $at, 16
 554       //  daddiu $at, $at, %lo($tgt - $baltgt)
 555       //  balc $baltgt
 556       // $baltgt:
 557       //  daddu $at, $ra, $at
 558       //  ld $ra, 0($sp)
 559       //  daddiu $sp, $sp, 16
 560       //  jic $at, 0
 561       // $fallthrough:
 562
 563       // We assume the branch is within-function, and that offset is within
 564       // +/- 2GB.  High 32 bits will therefore always be zero.
 565
 566       // Note that this will work even if the offset is negative, because
 567       // of the +1 modification that's added in that case.  For example, if the
 568       // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
 569       //
 570       // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
 571       //
 572       // and the bits [47:32] are zero.  For %highest
 573       //
 574       // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
 575       //
 576       // and the bits [63:48] are zero.
 577
 578       Pos = LongBrMBB->begin();
 579
 580       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
 581           .addReg(Mips::SP_64)
 582           .addImm(-16);
 583       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD))
 584           .addReg(Mips::RA_64)
 585           .addReg(Mips::SP_64)
 586           .addImm(0);
 587       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
 588               Mips::AT_64)
 589           .addReg(Mips::ZERO_64)
 590           .addMBB(TgtMBB, MipsII::MO_ABS_HI)
 591           .addMBB(BalTgtMBB);
 592       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
 593           .addReg(Mips::AT_64)
 594           .addImm(16);
 595
 596       MachineInstrBuilder BalInstr =
 597           BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
 598       MachineInstrBuilder DADDiuInstr =
 599           BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
 600               .addReg(Mips::AT_64)
 601               .addMBB(TgtMBB, MipsII::MO_ABS_LO)
 602               .addMBB(BalTgtMBB);
 603       if (STI->hasMips32r6()) {
 604         LongBrMBB->insert(Pos, DADDiuInstr);
 605         LongBrMBB->insert(Pos, BalInstr);
 606       } else {
 607         LongBrMBB->insert(Pos, BalInstr);
 608         LongBrMBB->insert(Pos, DADDiuInstr);
 609         LongBrMBB->rbegin()->bundleWithPred();
 610       }
 611
 612       Pos = BalTgtMBB->begin();
 613
 614       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
 615           .addReg(Mips::RA_64)
 616           .addReg(Mips::AT_64);
 617       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
 618           .addReg(Mips::SP_64)
 619           .addImm(0);
 620
 621       bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
 622       // If there is no delay slot, Insert stack adjustment before
 623       if (!hasDelaySlot) {
 624         BuildMI(*BalTgtMBB, std::prev(Pos), DL, TII->get(Mips::DADDiu),
 625                 Mips::SP_64)
 626             .addReg(Mips::SP_64)
 627             .addImm(16);
 628       } else {
 629         BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
 630             .addReg(Mips::SP_64)
 631             .addImm(16);
 632         BalTgtMBB->rbegin()->bundleWithPred();
 633       }
 634     }
 635   } else { // Not PIC
 636     Pos = LongBrMBB->begin();
 637     LongBrMBB->addSuccessor(TgtMBB);
 638
 639     // Compute the position of the potentiall jump instruction (basic blocks
 640     // before + 4 for the instruction)
 641     uint64_t JOffset = computeOffsetFromTheBeginning(MBB->getNumber()) +
 642                        MBBInfos[MBB->getNumber()].Size + 4;
 643     uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
 644     // If it's a forward jump, then TgtMBBOffset will be shifted by two
 645     // instructions
 646     if (JOffset < TgtMBBOffset)
 647       TgtMBBOffset += 2 * 4;
 648     // Compare 4 upper bits to check if it's the same segment
 649     bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
 650
 651     if (STI->hasMips32r6() && TII->isBranchOffsetInRange(Mips::BC, I.Offset)) {
 652       // R6:
 653       // $longbr:
 654       //  bc $tgt
 655       // $fallthrough:
 656       //
 657       BuildMI(*LongBrMBB, Pos, DL,
 658               TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
 659           .addMBB(TgtMBB);
 660     } else if (SameSegmentJump) {
 661       // Pre R6:
 662       // $longbr:
 663       //  j $tgt
 664       //  nop
 665       // $fallthrough:
 666       //
 667       MIBundleBuilder(*LongBrMBB, Pos)
 668           .append(BuildMI(*MFp, DL, TII->get(Mips::J)).addMBB(TgtMBB))
 669           .append(BuildMI(*MFp, DL, TII->get(Mips::NOP)));
 670     } else {
 671       // At this point, offset where we need to branch does not fit into
 672       // immediate field of the branch instruction and is not in the same
 673       // segment as jump instruction. Therefore we will break it into couple
 674       // instructions, where we first load the offset into register, and then we
 675       // do branch register.
 676       if (ABI.IsN64()) {
 677         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op_64),
 678                 Mips::AT_64)
 679             .addMBB(TgtMBB, MipsII::MO_HIGHEST);
 680         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
 681                 Mips::AT_64)
 682             .addReg(Mips::AT_64)
 683             .addMBB(TgtMBB, MipsII::MO_HIGHER);
 684         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
 685             .addReg(Mips::AT_64)
 686             .addImm(16);
 687         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
 688                 Mips::AT_64)
 689             .addReg(Mips::AT_64)
 690             .addMBB(TgtMBB, MipsII::MO_ABS_HI);
 691         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
 692             .addReg(Mips::AT_64)
 693             .addImm(16);
 694         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu2Op),
 695                 Mips::AT_64)
 696             .addReg(Mips::AT_64)
 697             .addMBB(TgtMBB, MipsII::MO_ABS_LO);
 698       } else {
 699         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi2Op),
 700                 Mips::AT)
 701             .addMBB(TgtMBB, MipsII::MO_ABS_HI);
 702         BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_ADDiu2Op),
 703                 Mips::AT)
 704             .addReg(Mips::AT)
 705             .addMBB(TgtMBB, MipsII::MO_ABS_LO);
 706       }
 707       buildProperJumpMI(LongBrMBB, Pos, DL);
 708     }
 709   }
 710
 711   if (I.Br->isUnconditionalBranch()) {
 712     // Change branch destination.
 713     assert(I.Br->getDesc().getNumOperands() == 1);
 714     I.Br->RemoveOperand(0);
 715     I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
 716   } else
 717     // Change branch destination and reverse condition.
 718     replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);
 719 }
 720
 721 static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
 722   MachineBasicBlock &MBB = F.front();
 723   MachineBasicBlock::iterator I = MBB.begin();
 724   DebugLoc DL = MBB.findDebugLoc(MBB.begin());
 725   BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
 726       .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
 727   BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
 728       .addReg(Mips::V0)
 729       .addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
 730   MBB.removeLiveIn(Mips::V0);
 731 }
 732
 733 bool MipsBranchExpansion::handleForbiddenSlot() {
 734   // Forbidden slot hazards are only defined for MIPSR6 but not microMIPSR6.
 735   if (!STI->hasMips32r6() || STI->inMicroMipsMode())
 736     return false;
 737
 738   bool Changed = false;
 739
 740   for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); ++FI) {
 741     for (Iter I = FI->begin(); I != FI->end(); ++I) {
 742
 743       // Forbidden slot hazard handling. Use lookahead over state.
 744       if (!TII->HasForbiddenSlot(*I))
 745         continue;
 746
 747       Iter Inst;
 748       bool LastInstInFunction =
 749           std::next(I) == FI->end() && std::next(FI) == MFp->end();
 750       if (!LastInstInFunction) {
 751         std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);
 752         LastInstInFunction |= Res.second;
 753         Inst = Res.first;
 754       }
 755
 756       if (LastInstInFunction || !TII->SafeInForbiddenSlot(*Inst)) {
 757
 758         MachineBasicBlock::instr_iterator Iit = I->getIterator();
 759         if (std::next(Iit) == FI->end() ||
 760             std::next(Iit)->getOpcode() != Mips::NOP) {
 761           Changed = true;
 762           MIBundleBuilder(&*I).append(
 763               BuildMI(*MFp, I->getDebugLoc(), TII->get(Mips::NOP)));
 764           NumInsertedNops++;
 765         }
 766       }
 767     }
 768   }
 769
 770   return Changed;
 771 }
 772
 773 bool MipsBranchExpansion::handlePossibleLongBranch() {
 774   if (STI->inMips16Mode() || !STI->enableLongBranchPass())
 775     return false;
 776
 777   if (SkipLongBranch)
 778     return false;
 779
 780   bool EverMadeChange = false, MadeChange = true;
 781
 782   while (MadeChange) {
 783     MadeChange = false;
 784
 785     initMBBInfo();
 786
 787     for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
 788       MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
 789       // Search for MBB's branch instruction.
 790       ReverseIter End = MBB->rend();
 791       ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
 792
 793       if ((Br != End) && Br->isBranch() && !Br->isIndirectBranch() &&
 794           (Br->isConditionalBranch() ||
 795            (Br->isUnconditionalBranch() && IsPIC))) {
 796         int64_t Offset = computeOffset(&*Br);
 797
 798         if (STI->isTargetNaCl()) {
 799           // The offset calculation does not include sandboxing instructions
 800           // that will be added later in the MC layer.  Since at this point we
 801           // don't know the exact amount of code that "sandboxing" will add, we
 802           // conservatively estimate that code will not grow more than 100%.
 803           Offset *= 2;
 804         }
 805
 806         if (ForceLongBranchFirstPass ||
 807             !TII->isBranchOffsetInRange(Br->getOpcode(), Offset)) {
 808           MBBInfos[I].Offset = Offset;
 809           MBBInfos[I].Br = &*Br;
 810         }
 811       }
 812     } // End for
 813
 814     ForceLongBranchFirstPass = false;
 815
 816     SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
 817
 818     for (I = MBBInfos.begin(); I != E; ++I) {
 819       // Skip if this MBB doesn't have a branch or the branch has already been
 820       // converted to a long branch.
 821       if (!I->Br)
 822         continue;
 823
 824       expandToLongBranch(*I);
 825       ++LongBranches;
 826       EverMadeChange = MadeChange = true;
 827     }
 828
 829     MFp->RenumberBlocks();
 830   }
 831
 832   return EverMadeChange;
 833 }
 834
 835 bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {
 836   const TargetMachine &TM = MF.getTarget();
 837   IsPIC = TM.isPositionIndependent();
 838   ABI = static_cast<const MipsTargetMachine &>(TM).getABI();
 839   STI = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
 840   TII = static_cast<const MipsInstrInfo *>(STI->getInstrInfo());
 841
 842   if (IsPIC && ABI.IsO32() &&
 843       MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
 844     emitGPDisp(MF, TII);
 845
 846   MFp = &MF;
 847
 848   ForceLongBranchFirstPass = ForceLongBranch;
 849   // Run these two at least once
 850   bool longBranchChanged = handlePossibleLongBranch();
 851   bool forbiddenSlotChanged = handleForbiddenSlot();
 852
 853   bool Changed = longBranchChanged || forbiddenSlotChanged;
 854
 855   // Then run them alternatively while there are changes
 856   while (forbiddenSlotChanged) {
 857     longBranchChanged = handlePossibleLongBranch();
 858     if (!longBranchChanged)
 859       break;
 860     forbiddenSlotChanged = handleForbiddenSlot();
 861   }
 862
 863   return Changed;
 864 }