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