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   MBBInfo() = default;
 132 };
 133
 134 class MipsBranchExpansion : public MachineFunctionPass {
 135 public:
 136   static char ID;
 137
 138   MipsBranchExpansion() : MachineFunctionPass(ID), ABI(MipsABIInfo::Unknown()) {
 139     initializeMipsBranchExpansionPass(*PassRegistry::getPassRegistry());
 140   }
 141
 142   StringRef getPassName() const override {
 143     return "Mips Branch Expansion Pass";
 144   }
 145
 146   bool runOnMachineFunction(MachineFunction &F) override;
 147
 148   MachineFunctionProperties getRequiredProperties() const override {
 149     return MachineFunctionProperties().set(
 150         MachineFunctionProperties::Property::NoVRegs);
 151   }
 152
 153 private:
 154   void splitMBB(MachineBasicBlock *MBB);
 155   void initMBBInfo();
 156   int64_t computeOffset(const MachineInstr *Br);
 157   void replaceBranch(MachineBasicBlock &MBB, Iter Br, const DebugLoc &DL,
 158                      MachineBasicBlock *MBBOpnd);
 159   void expandToLongBranch(MBBInfo &Info);
 160   bool handleForbiddenSlot();
 161   bool handlePossibleLongBranch();
 162
 163   const MipsSubtarget *STI;
 164   const MipsInstrInfo *TII;
 165
 166   MachineFunction *MFp;
 167   SmallVector<MBBInfo, 16> MBBInfos;
 168   bool IsPIC;
 169   MipsABIInfo ABI;
 170   unsigned LongBranchSeqSize;
 171   bool ForceLongBranchFirstPass = false;
 172 };
 173
 174 } // end of anonymous namespace
 175
 176 char MipsBranchExpansion::ID = 0;
 177
 178 INITIALIZE_PASS(MipsBranchExpansion, DEBUG_TYPE,
 179                 "Expand out of range branch instructions and prevent forbidden"
 180                 " slot hazards",
 181                 false, false)
 182
 183 /// Returns a pass that clears pipeline hazards.
 184 FunctionPass *llvm::createMipsBranchExpansion() {
 185   return new MipsBranchExpansion();
 186 }
 187
 188 // Find the next real instruction from the current position in current basic
 189 // block.
 190 static Iter getNextMachineInstrInBB(Iter Position) {
 191   Iter I = Position, E = Position->getParent()->end();
 192   I = std::find_if_not(I, E,
 193                        [](const Iter &Insn) { return Insn->isTransient(); });
 194
 195   return I;
 196 }
 197
 198 // Find the next real instruction from the current position, looking through
 199 // basic block boundaries.
 200 static std::pair<Iter, bool> getNextMachineInstr(Iter Position,
 201                                                  MachineBasicBlock *Parent) {
 202   if (Position == Parent->end()) {
 203     do {
 204       MachineBasicBlock *Succ = Parent->getNextNode();
 205       if (Succ != nullptr && Parent->isSuccessor(Succ)) {
 206         Position = Succ->begin();
 207         Parent = Succ;
 208       } else {
 209         return std::make_pair(Position, true);
 210       }
 211     } while (Parent->empty());
 212   }
 213
 214   Iter Instr = getNextMachineInstrInBB(Position);
 215   if (Instr == Parent->end()) {
 216     return getNextMachineInstr(Instr, Parent);
 217   }
 218   return std::make_pair(Instr, false);
 219 }
 220
 221 /// Iterate over list of Br's operands and search for a MachineBasicBlock
 222 /// operand.
 223 static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) {
 224   for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) {
 225     const MachineOperand &MO = Br.getOperand(I);
 226
 227     if (MO.isMBB())
 228       return MO.getMBB();
 229   }
 230
 231   llvm_unreachable("This instruction does not have an MBB operand.");
 232 }
 233
 234 // Traverse the list of instructions backwards until a non-debug instruction is
 235 // found or it reaches E.
 236 static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E) {
 237   for (; B != E; ++B)
 238     if (!B->isDebugInstr())
 239       return B;
 240
 241   return E;
 242 }
 243
 244 // Split MBB if it has two direct jumps/branches.
 245 void MipsBranchExpansion::splitMBB(MachineBasicBlock *MBB) {
 246   ReverseIter End = MBB->rend();
 247   ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End);
 248
 249   // Return if MBB has no branch instructions.
 250   if ((LastBr == End) ||
 251       (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
 252     return;
 253
 254   ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End);
 255
 256   // MBB has only one branch instruction if FirstBr is not a branch
 257   // instruction.
 258   if ((FirstBr == End) ||
 259       (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
 260     return;
 261
 262   assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found.");
 263
 264   // Create a new MBB. Move instructions in MBB to the newly created MBB.
 265   MachineBasicBlock *NewMBB =
 266       MFp->CreateMachineBasicBlock(MBB->getBasicBlock());
 267
 268   // Insert NewMBB and fix control flow.
 269   MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
 270   NewMBB->transferSuccessors(MBB);
 271   NewMBB->removeSuccessor(Tgt, true);
 272   MBB->addSuccessor(NewMBB);
 273   MBB->addSuccessor(Tgt);
 274   MFp->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
 275
 276   NewMBB->splice(NewMBB->end(), MBB, LastBr.getReverse(), MBB->end());
 277 }
 278
 279 // Fill MBBInfos.
 280 void MipsBranchExpansion::initMBBInfo() {
 281   // Split the MBBs if they have two branches. Each basic block should have at
 282   // most one branch after this loop is executed.
 283   for (auto &MBB : *MFp)
 284     splitMBB(&MBB);
 285
 286   MFp->RenumberBlocks();
 287   MBBInfos.clear();
 288   MBBInfos.resize(MFp->size());
 289
 290   for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) {
 291     MachineBasicBlock *MBB = MFp->getBlockNumbered(I);
 292
 293     // Compute size of MBB.
 294     for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin();
 295          MI != MBB->instr_end(); ++MI)
 296       MBBInfos[I].Size += TII->getInstSizeInBytes(*MI);
 297
 298     // Search for MBB's branch instruction.
 299     ReverseIter End = MBB->rend();
 300     ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End);
 301
 302     if ((Br != End) && !Br->isIndirectBranch() &&
 303         (Br->isConditionalBranch() || (Br->isUnconditionalBranch() && IsPIC)))
 304       MBBInfos[I].Br = &*Br;
 305   }
 306 }
 307
 308 // Compute offset of branch in number of bytes.
 309 int64_t MipsBranchExpansion::computeOffset(const MachineInstr *Br) {
 310   int64_t Offset = 0;
 311   int ThisMBB = Br->getParent()->getNumber();
 312   int TargetMBB = getTargetMBB(*Br)->getNumber();
 313
 314   // Compute offset of a forward branch.
 315   if (ThisMBB < TargetMBB) {
 316     for (int N = ThisMBB + 1; N < TargetMBB; ++N)
 317       Offset += MBBInfos[N].Size;
 318
 319     return Offset + 4;
 320   }
 321
 322   // Compute offset of a backward branch.
 323   for (int N = ThisMBB; N >= TargetMBB; --N)
 324     Offset += MBBInfos[N].Size;
 325
 326   return -Offset + 4;
 327 }
 328
 329 // Replace Br with a branch which has the opposite condition code and a
 330 // MachineBasicBlock operand MBBOpnd.
 331 void MipsBranchExpansion::replaceBranch(MachineBasicBlock &MBB, Iter Br,
 332                                         const DebugLoc &DL,
 333                                         MachineBasicBlock *MBBOpnd) {
 334   unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode());
 335   const MCInstrDesc &NewDesc = TII->get(NewOpc);
 336
 337   MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc);
 338
 339   for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) {
 340     MachineOperand &MO = Br->getOperand(I);
 341
 342     if (!MO.isReg()) {
 343       assert(MO.isMBB() && "MBB operand expected.");
 344       break;
 345     }
 346
 347     MIB.addReg(MO.getReg());
 348   }
 349
 350   MIB.addMBB(MBBOpnd);
 351
 352   if (Br->hasDelaySlot()) {
 353     // Bundle the instruction in the delay slot to the newly created branch
 354     // and erase the original branch.
 355     assert(Br->isBundledWithSucc());
 356     MachineBasicBlock::instr_iterator II = Br.getInstrIterator();
 357     MIBundleBuilder(&*MIB).append((++II)->removeFromBundle());
 358   }
 359   Br->eraseFromParent();
 360 }
 361
 362 // Expand branch instructions to long branches.
 363 // TODO: This function has to be fixed for beqz16 and bnez16, because it
 364 // currently assumes that all branches have 16-bit offsets, and will produce
 365 // wrong code if branches whose allowed offsets are [-128, -126, ..., 126]
 366 // are present.
 367 void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) {
 368   MachineBasicBlock::iterator Pos;
 369   MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br);
 370   DebugLoc DL = I.Br->getDebugLoc();
 371   const BasicBlock *BB = MBB->getBasicBlock();
 372   MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB);
 373   MachineBasicBlock *LongBrMBB = MFp->CreateMachineBasicBlock(BB);
 374
 375   MFp->insert(FallThroughMBB, LongBrMBB);
 376   MBB->replaceSuccessor(TgtMBB, LongBrMBB);
 377
 378   if (IsPIC) {
 379     MachineBasicBlock *BalTgtMBB = MFp->CreateMachineBasicBlock(BB);
 380     MFp->insert(FallThroughMBB, BalTgtMBB);
 381     LongBrMBB->addSuccessor(BalTgtMBB);
 382     BalTgtMBB->addSuccessor(TgtMBB);
 383
 384     // We must select between the MIPS32r6/MIPS64r6 BALC (which is a normal
 385     // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an
 386     // pseudo-instruction wrapping BGEZAL).
 387     const unsigned BalOp =
 388         STI->hasMips32r6()
 389             ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
 390             : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
 391
 392     if (!ABI.IsN64()) {
 393       // Pre R6:
 394       // $longbr:
 395       //  addiu $sp, $sp, -8
 396       //  sw $ra, 0($sp)
 397       //  lui $at, %hi($tgt - $baltgt)
 398       //  bal $baltgt
 399       //  addiu $at, $at, %lo($tgt - $baltgt)
 400       // $baltgt:
 401       //  addu $at, $ra, $at
 402       //  lw $ra, 0($sp)
 403       //  jr $at
 404       //  addiu $sp, $sp, 8
 405       // $fallthrough:
 406       //
 407
 408       // R6:
 409       // $longbr:
 410       //  addiu $sp, $sp, -8
 411       //  sw $ra, 0($sp)
 412       //  lui $at, %hi($tgt - $baltgt)
 413       //  addiu $at, $at, %lo($tgt - $baltgt)
 414       //  balc $baltgt
 415       // $baltgt:
 416       //  addu $at, $ra, $at
 417       //  lw $ra, 0($sp)
 418       //  addiu $sp, $sp, 8
 419       //  jic $at, 0
 420       // $fallthrough:
 421
 422       Pos = LongBrMBB->begin();
 423
 424       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
 425           .addReg(Mips::SP)
 426           .addImm(-8);
 427       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW))
 428           .addReg(Mips::RA)
 429           .addReg(Mips::SP)
 430           .addImm(0);
 431
 432       // LUi and ADDiu instructions create 32-bit offset of the target basic
 433       // block from the target of BAL(C) instruction.  We cannot use immediate
 434       // value for this offset because it cannot be determined accurately when
 435       // the program has inline assembly statements.  We therefore use the
 436       // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which
 437       // are resolved during the fixup, so the values will always be correct.
 438       //
 439       // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt)
 440       // expressions at this point (it is possible only at the MC layer),
 441       // we replace LUi and ADDiu with pseudo instructions
 442       // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic
 443       // blocks as operands to these instructions.  When lowering these pseudo
 444       // instructions to LUi and ADDiu in the MC layer, we will create
 445       // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as
 446       // operands to lowered instructions.
 447
 448       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
 449           .addMBB(TgtMBB, MipsII::MO_ABS_HI)
 450           .addMBB(BalTgtMBB);
 451
 452       MachineInstrBuilder BalInstr =
 453           BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
 454       MachineInstrBuilder ADDiuInstr =
 455           BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
 456               .addReg(Mips::AT)
 457               .addMBB(TgtMBB, MipsII::MO_ABS_LO)
 458               .addMBB(BalTgtMBB);
 459       if (STI->hasMips32r6()) {
 460         LongBrMBB->insert(Pos, ADDiuInstr);
 461         LongBrMBB->insert(Pos, BalInstr);
 462       } else {
 463         LongBrMBB->insert(Pos, BalInstr);
 464         LongBrMBB->insert(Pos, ADDiuInstr);
 465         LongBrMBB->rbegin()->bundleWithPred();
 466       }
 467
 468       Pos = BalTgtMBB->begin();
 469
 470       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT)
 471           .addReg(Mips::RA)
 472           .addReg(Mips::AT);
 473       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA)
 474           .addReg(Mips::SP)
 475           .addImm(0);
 476       if (STI->isTargetNaCl())
 477         // Bundle-align the target of indirect branch JR.
 478         TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN);
 479
 480       // In NaCl, modifying the sp is not allowed in branch delay slot.
 481       // For MIPS32R6, we can skip using a delay slot branch.
 482       if (STI->isTargetNaCl() ||
 483           (STI->hasMips32r6() && !STI->useIndirectJumpsHazard()))
 484         BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
 485             .addReg(Mips::SP)
 486             .addImm(8);
 487
 488       if (STI->hasMips32r6() && !STI->useIndirectJumpsHazard()) {
 489         const unsigned JICOp =
 490             STI->inMicroMipsMode() ? Mips::JIC_MMR6 : Mips::JIC;
 491         BuildMI(*BalTgtMBB, Pos, DL, TII->get(JICOp))
 492             .addReg(Mips::AT)
 493             .addImm(0);
 494
 495       } else {
 496         unsigned JROp =
 497             STI->useIndirectJumpsHazard()
 498                 ? (STI->hasMips32r6() ? Mips::JR_HB_R6 : Mips::JR_HB)
 499                 : Mips::JR;
 500         BuildMI(*BalTgtMBB, Pos, DL, TII->get(JROp)).addReg(Mips::AT);
 501
 502         if (STI->isTargetNaCl()) {
 503           BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::NOP));
 504         } else
 505           BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP)
 506               .addReg(Mips::SP)
 507               .addImm(8);
 508
 509         BalTgtMBB->rbegin()->bundleWithPred();
 510       }
 511     } else {
 512       // Pre R6:
 513       // $longbr:
 514       //  daddiu $sp, $sp, -16
 515       //  sd $ra, 0($sp)
 516       //  daddiu $at, $zero, %hi($tgt - $baltgt)
 517       //  dsll $at, $at, 16
 518       //  bal $baltgt
 519       //  daddiu $at, $at, %lo($tgt - $baltgt)
 520       // $baltgt:
 521       //  daddu $at, $ra, $at
 522       //  ld $ra, 0($sp)
 523       //  jr64 $at
 524       //  daddiu $sp, $sp, 16
 525       // $fallthrough:
 526
 527       // R6:
 528       // $longbr:
 529       //  daddiu $sp, $sp, -16
 530       //  sd $ra, 0($sp)
 531       //  daddiu $at, $zero, %hi($tgt - $baltgt)
 532       //  dsll $at, $at, 16
 533       //  daddiu $at, $at, %lo($tgt - $baltgt)
 534       //  balc $baltgt
 535       // $baltgt:
 536       //  daddu $at, $ra, $at
 537       //  ld $ra, 0($sp)
 538       //  daddiu $sp, $sp, 16
 539       //  jic $at, 0
 540       // $fallthrough:
 541
 542       // We assume the branch is within-function, and that offset is within
 543       // +/- 2GB.  High 32 bits will therefore always be zero.
 544
 545       // Note that this will work even if the offset is negative, because
 546       // of the +1 modification that's added in that case.  For example, if the
 547       // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is
 548       //
 549       // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000
 550       //
 551       // and the bits [47:32] are zero.  For %highest
 552       //
 553       // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000
 554       //
 555       // and the bits [63:48] are zero.
 556
 557       Pos = LongBrMBB->begin();
 558
 559       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
 560           .addReg(Mips::SP_64)
 561           .addImm(-16);
 562       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD))
 563           .addReg(Mips::RA_64)
 564           .addReg(Mips::SP_64)
 565           .addImm(0);
 566       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu),
 567               Mips::AT_64)
 568           .addReg(Mips::ZERO_64)
 569           .addMBB(TgtMBB, MipsII::MO_ABS_HI)
 570           .addMBB(BalTgtMBB);
 571       BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64)
 572           .addReg(Mips::AT_64)
 573           .addImm(16);
 574
 575       MachineInstrBuilder BalInstr =
 576           BuildMI(*MFp, DL, TII->get(BalOp)).addMBB(BalTgtMBB);
 577       MachineInstrBuilder DADDiuInstr =
 578           BuildMI(*MFp, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
 579               .addReg(Mips::AT_64)
 580               .addMBB(TgtMBB, MipsII::MO_ABS_LO)
 581               .addMBB(BalTgtMBB);
 582       if (STI->hasMips32r6()) {
 583         LongBrMBB->insert(Pos, DADDiuInstr);
 584         LongBrMBB->insert(Pos, BalInstr);
 585       } else {
 586         LongBrMBB->insert(Pos, BalInstr);
 587         LongBrMBB->insert(Pos, DADDiuInstr);
 588         LongBrMBB->rbegin()->bundleWithPred();
 589       }
 590
 591       Pos = BalTgtMBB->begin();
 592
 593       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64)
 594           .addReg(Mips::RA_64)
 595           .addReg(Mips::AT_64);
 596       BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64)
 597           .addReg(Mips::SP_64)
 598           .addImm(0);
 599
 600       if (STI->hasMips64r6() && !STI->useIndirectJumpsHazard()) {
 601         BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
 602             .addReg(Mips::SP_64)
 603             .addImm(16);
 604         BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::JIC64))
 605             .addReg(Mips::AT_64)
 606             .addImm(0);
 607       } else {
 608         unsigned JROp =
 609             STI->useIndirectJumpsHazard()
 610                 ? (STI->hasMips32r6() ? Mips::JR_HB64_R6 : Mips::JR_HB64)
 611                 : Mips::JR64;
 612         BuildMI(*BalTgtMBB, Pos, DL, TII->get(JROp)).addReg(Mips::AT_64);
 613         BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64)
 614             .addReg(Mips::SP_64)
 615             .addImm(16);
 616         BalTgtMBB->rbegin()->bundleWithPred();
 617       }
 618     }
 619
 620     assert(LongBrMBB->size() + BalTgtMBB->size() == LongBranchSeqSize);
 621   } else {
 622     // Pre R6:                  R6:
 623     // $longbr:                 $longbr:
 624     //  j $tgt                   bc $tgt
 625     //  nop                     $fallthrough
 626     // $fallthrough:
 627     //
 628     Pos = LongBrMBB->begin();
 629     LongBrMBB->addSuccessor(TgtMBB);
 630     if (STI->hasMips32r6())
 631       BuildMI(*LongBrMBB, Pos, DL,
 632               TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
 633           .addMBB(TgtMBB);
 634     else
 635       MIBundleBuilder(*LongBrMBB, Pos)
 636           .append(BuildMI(*MFp, DL, TII->get(Mips::J)).addMBB(TgtMBB))
 637           .append(BuildMI(*MFp, DL, TII->get(Mips::NOP)));
 638
 639     assert(LongBrMBB->size() == LongBranchSeqSize);
 640   }
 641
 642   if (I.Br->isUnconditionalBranch()) {
 643     // Change branch destination.
 644     assert(I.Br->getDesc().getNumOperands() == 1);
 645     I.Br->RemoveOperand(0);
 646     I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB));
 647   } else
 648     // Change branch destination and reverse condition.
 649     replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);
 650 }
 651
 652 static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) {
 653   MachineBasicBlock &MBB = F.front();
 654   MachineBasicBlock::iterator I = MBB.begin();
 655   DebugLoc DL = MBB.findDebugLoc(MBB.begin());
 656   BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
 657       .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI);
 658   BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
 659       .addReg(Mips::V0)
 660       .addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO);
 661   MBB.removeLiveIn(Mips::V0);
 662 }
 663
 664 bool MipsBranchExpansion::handleForbiddenSlot() {
 665   // Forbidden slot hazards are only defined for MIPSR6 but not microMIPSR6.
 666   if (!STI->hasMips32r6() || STI->inMicroMipsMode())
 667     return false;
 668
 669   const MipsInstrInfo *TII = STI->getInstrInfo();
 670
 671   bool Changed = false;
 672
 673   for (MachineFunction::iterator FI = MFp->begin(); FI != MFp->end(); ++FI) {
 674     for (Iter I = FI->begin(); I != FI->end(); ++I) {
 675
 676       // Forbidden slot hazard handling. Use lookahead over state.
 677       if (!TII->HasForbiddenSlot(*I))
 678         continue;
 679
 680       Iter Inst;
 681       bool LastInstInFunction =
 682           std::next(I) == FI->end() && std::next(FI) == MFp->end();
 683       if (!LastInstInFunction) {
 684         std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);
 685         LastInstInFunction |= Res.second;
 686         Inst = Res.first;
 687       }
 688
 689       if (LastInstInFunction || !TII->SafeInForbiddenSlot(*Inst)) {
 690
 691         MachineBasicBlock::instr_iterator Iit = I->getIterator();
 692         if (std::next(Iit) == FI->end() ||
 693             std::next(Iit)->getOpcode() != Mips::NOP) {
 694           Changed = true;
 695           MIBundleBuilder(&*I).append(
 696               BuildMI(*MFp, I->getDebugLoc(), TII->get(Mips::NOP)));
 697           NumInsertedNops++;
 698         }
 699       }
 700     }
 701   }
 702
 703   return Changed;
 704 }
 705
 706 bool MipsBranchExpansion::handlePossibleLongBranch() {
 707
 708   LongBranchSeqSize = IsPIC ? ((ABI.IsN64() || STI->isTargetNaCl()) ? 10 : 9)
 709                             : (STI->hasMips32r6() ? 1 : 2);
 710
 711   if (STI->inMips16Mode() || !STI->enableLongBranchPass())
 712     return false;
 713
 714   if (SkipLongBranch)
 715     return false;
 716
 717   initMBBInfo();
 718
 719   SmallVectorImpl<MBBInfo>::iterator I, E = MBBInfos.end();
 720   bool EverMadeChange = false, MadeChange = true;
 721
 722   while (MadeChange) {
 723     MadeChange = false;
 724
 725     for (I = MBBInfos.begin(); I != E; ++I) {
 726       // Skip if this MBB doesn't have a branch or the branch has already been
 727       // converted to a long branch.
 728       if (!I->Br || I->HasLongBranch)
 729         continue;
 730
 731       int64_t Offset = computeOffset(I->Br);
 732
 733       if (STI->isTargetNaCl()) {
 734         // The offset calculation does not include sandboxing instructions
 735         // that will be added later in the MC layer.  Since at this point we
 736         // don't know the exact amount of code that "sandboxing" will add, we
 737         // conservatively estimate that code will not grow more than 100%.
 738         Offset *= 2;
 739       }
 740
 741       // Check if offset fits into the immediate field of the branch.
 742       if (!ForceLongBranchFirstPass &&
 743           TII->isBranchOffsetInRange(I->Br->getOpcode(), Offset))
 744         continue;
 745
 746       I->HasLongBranch = true;
 747       I->Size += LongBranchSeqSize * 4;
 748       ++LongBranches;
 749       EverMadeChange = MadeChange = true;
 750     }
 751   }
 752
 753   ForceLongBranchFirstPass = false;
 754
 755   if (!EverMadeChange)
 756     return false;
 757
 758   // Do the expansion.
 759   for (I = MBBInfos.begin(); I != E; ++I)
 760     if (I->HasLongBranch) {
 761       expandToLongBranch(*I);
 762     }
 763
 764   MFp->RenumberBlocks();
 765
 766   return true;
 767 }
 768
 769 bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {
 770   const TargetMachine &TM = MF.getTarget();
 771   IsPIC = TM.isPositionIndependent();
 772   ABI = static_cast<const MipsTargetMachine &>(TM).getABI();
 773   STI = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
 774   TII = static_cast<const MipsInstrInfo *>(STI->getInstrInfo());
 775
 776   if (IsPIC && ABI.IsO32() &&
 777       MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
 778     emitGPDisp(MF, TII);
 779
 780   MFp = &MF;
 781
 782   ForceLongBranchFirstPass = ForceLongBranch;
 783   // Run these two at least once
 784   bool longBranchChanged = handlePossibleLongBranch();
 785   bool forbiddenSlotChanged = handleForbiddenSlot();
 786
 787   bool Changed = longBranchChanged || forbiddenSlotChanged;
 788
 789   // Then run them alternatively while there are changes
 790   while (forbiddenSlotChanged) {
 791     longBranchChanged = handlePossibleLongBranch();
 792     if (!longBranchChanged)
 793       break;
 794     forbiddenSlotChanged = handleForbiddenSlot();
 795   }
 796
 797   return Changed;
 798 }