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 } 799