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