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