MipsLongBranch.cpp revision c984657c7461ce28b25ca91fdc6caaf2860127fd
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 "MipsTargetMachine.h" 23#include "MCTargetDesc/MipsBaseInfo.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/CodeGen/MachineFunctionPass.h" 26#include "llvm/CodeGen/MachineInstrBuilder.h" 27#include "llvm/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 TII(static_cast<const MipsInstrInfo*>(tm.getInstrInfo())), 69 IsPIC(TM.getRelocationModel() == Reloc::PIC_), 70 ABI(TM.getSubtarget<MipsSubtarget>().getTargetABI()), 71 LongBranchSeqSize(!IsPIC ? 2 : (ABI == MipsSubtarget::N64 ? 13 : 9)) {} 72 73 virtual const char *getPassName() const { 74 return "Mips Long Branch"; 75 } 76 77 bool runOnMachineFunction(MachineFunction &F); 78 79 private: 80 void splitMBB(MachineBasicBlock *MBB); 81 void initMBBInfo(); 82 int64_t computeOffset(const MachineInstr *Br); 83 void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL, 84 MachineBasicBlock *MBBOpnd); 85 void expandToLongBranch(MBBInfo &Info); 86 87 const TargetMachine &TM; 88 const MipsInstrInfo *TII; 89 MachineFunction *MF; 90 SmallVector<MBBInfo, 16> MBBInfos; 91 bool IsPIC; 92 unsigned ABI; 93 unsigned LongBranchSeqSize; 94 }; 95 96 char MipsLongBranch::ID = 0; 97} // end of anonymous namespace 98 99/// createMipsLongBranchPass - Returns a pass that converts branches to long 100/// branches. 101FunctionPass *llvm::createMipsLongBranchPass(MipsTargetMachine &tm) { 102 return new MipsLongBranch(tm); 103} 104 105/// Iterate over list of Br's operands and search for a MachineBasicBlock 106/// operand. 107static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) { 108 for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) { 109 const MachineOperand &MO = Br.getOperand(I); 110 111 if (MO.isMBB()) 112 return MO.getMBB(); 113 } 114 115 assert(false && "This instruction does not have an MBB operand."); 116 return 0; 117} 118 119// Traverse the list of instructions backwards until a non-debug instruction is 120// found or it reaches E. 121static ReverseIter getNonDebugInstr(ReverseIter B, ReverseIter E) { 122 for (; B != E; ++B) 123 if (!B->isDebugValue()) 124 return B; 125 126 return E; 127} 128 129// Split MBB if it has two direct jumps/branches. 130void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) { 131 ReverseIter End = MBB->rend(); 132 ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End); 133 134 // Return if MBB has no branch instructions. 135 if ((LastBr == End) || 136 (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch())) 137 return; 138 139 ReverseIter FirstBr = getNonDebugInstr(llvm::next(LastBr), End); 140 141 // MBB has only one branch instruction if FirstBr is not a branch 142 // instruction. 143 if ((FirstBr == End) || 144 (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch())) 145 return; 146 147 assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found."); 148 149 // Create a new MBB. Move instructions in MBB to the newly created MBB. 150 MachineBasicBlock *NewMBB = 151 MF->CreateMachineBasicBlock(MBB->getBasicBlock()); 152 153 // Insert NewMBB and fix control flow. 154 MachineBasicBlock *Tgt = getTargetMBB(*FirstBr); 155 NewMBB->transferSuccessors(MBB); 156 NewMBB->removeSuccessor(Tgt); 157 MBB->addSuccessor(NewMBB); 158 MBB->addSuccessor(Tgt); 159 MF->insert(llvm::next(MachineFunction::iterator(MBB)), NewMBB); 160 161 NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end()); 162} 163 164// Fill MBBInfos. 165void MipsLongBranch::initMBBInfo() { 166 // Split the MBBs if they have two branches. Each basic block should have at 167 // most one branch after this loop is executed. 168 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E;) 169 splitMBB(I++); 170 171 MF->RenumberBlocks(); 172 MBBInfos.clear(); 173 MBBInfos.resize(MF->size()); 174 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 unsigned NewOpc = TII->GetOppositeBranchOpc(Br->getOpcode()); 221 const MCInstrDesc &NewDesc = TII->get(NewOpc); 222 223 MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc); 224 225 for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) { 226 MachineOperand &MO = Br->getOperand(I); 227 228 if (!MO.isReg()) { 229 assert(MO.isMBB() && "MBB operand expected."); 230 break; 231 } 232 233 MIB.addReg(MO.getReg()); 234 } 235 236 MIB.addMBB(MBBOpnd); 237 238 Br->eraseFromParent(); 239} 240 241// Expand branch instructions to long branches. 242void MipsLongBranch::expandToLongBranch(MBBInfo &I) { 243 MachineBasicBlock::iterator Pos; 244 MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br); 245 DebugLoc DL = I.Br->getDebugLoc(); 246 const BasicBlock *BB = MBB->getBasicBlock(); 247 MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB); 248 MachineBasicBlock *LongBrMBB = MF->CreateMachineBasicBlock(BB); 249 250 MF->insert(FallThroughMBB, LongBrMBB); 251 MBB->removeSuccessor(TgtMBB); 252 MBB->addSuccessor(LongBrMBB); 253 254 if (IsPIC) { 255 MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB); 256 MF->insert(FallThroughMBB, BalTgtMBB); 257 LongBrMBB->addSuccessor(BalTgtMBB); 258 BalTgtMBB->addSuccessor(TgtMBB); 259 260 int64_t TgtAddress = MBBInfos[TgtMBB->getNumber()].Address; 261 unsigned BalTgtMBBSize = 5; 262 int64_t Offset = TgtAddress - (I.Address + I.Size - BalTgtMBBSize * 4); 263 int64_t Lo = SignExtend64<16>(Offset & 0xffff); 264 int64_t Hi = SignExtend64<16>(((Offset + 0x8000) >> 16) & 0xffff); 265 266 if (ABI != MipsSubtarget::N64) { 267 // $longbr: 268 // addiu $sp, $sp, -8 269 // sw $ra, 0($sp) 270 // bal $baltgt 271 // lui $at, %hi($tgt - $baltgt) 272 // $baltgt: 273 // addiu $at, $at, %lo($tgt - $baltgt) 274 // addu $at, $ra, $at 275 // lw $ra, 0($sp) 276 // jr $at 277 // addiu $sp, $sp, 8 278 // $fallthrough: 279 // 280 281 Pos = LongBrMBB->begin(); 282 283 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP) 284 .addReg(Mips::SP).addImm(-8); 285 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW)).addReg(Mips::RA) 286 .addReg(Mips::SP).addImm(0); 287 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB); 288 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LUi), Mips::AT).addImm(Hi) 289 ->setIsInsideBundle(); 290 291 Pos = BalTgtMBB->begin(); 292 293 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::AT) 294 .addReg(Mips::AT).addImm(Lo); 295 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT) 296 .addReg(Mips::RA).addReg(Mips::AT); 297 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA) 298 .addReg(Mips::SP).addImm(0); 299 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::JR)).addReg(Mips::AT); 300 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP) 301 .addReg(Mips::SP).addImm(8)->setIsInsideBundle(); 302 } else { 303 // $longbr: 304 // daddiu $sp, $sp, -16 305 // sd $ra, 0($sp) 306 // lui64 $at, %highest($tgt - $baltgt) 307 // daddiu $at, $at, %higher($tgt - $baltgt) 308 // dsll $at, $at, 16 309 // daddiu $at, $at, %hi($tgt - $baltgt) 310 // bal $baltgt 311 // dsll $at, $at, 16 312 // $baltgt: 313 // daddiu $at, $at, %lo($tgt - $baltgt) 314 // daddu $at, $ra, $at 315 // ld $ra, 0($sp) 316 // jr64 $at 317 // daddiu $sp, $sp, 16 318 // $fallthrough: 319 // 320 321 int64_t Higher = SignExtend64<16>(((Offset + 0x80008000) >> 32) & 0xffff); 322 int64_t Highest = 323 SignExtend64<16>(((Offset + 0x800080008000LL) >> 48) & 0xffff); 324 325 Pos = LongBrMBB->begin(); 326 327 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64) 328 .addReg(Mips::SP_64).addImm(-16); 329 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD)).addReg(Mips::RA_64) 330 .addReg(Mips::SP_64).addImm(0); 331 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LUi64), Mips::AT_64) 332 .addImm(Highest); 333 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) 334 .addReg(Mips::AT_64).addImm(Higher); 335 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64) 336 .addReg(Mips::AT_64).addImm(16); 337 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) 338 .addReg(Mips::AT_64).addImm(Hi); 339 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB); 340 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64) 341 .addReg(Mips::AT_64).addImm(16)->setIsInsideBundle(); 342 343 Pos = BalTgtMBB->begin(); 344 345 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) 346 .addReg(Mips::AT_64).addImm(Lo); 347 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64) 348 .addReg(Mips::RA_64).addReg(Mips::AT_64); 349 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64) 350 .addReg(Mips::SP_64).addImm(0); 351 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::JR64)).addReg(Mips::AT_64); 352 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64) 353 .addReg(Mips::SP_64).addImm(16)->setIsInsideBundle(); 354 } 355 356 assert(BalTgtMBBSize == BalTgtMBB->size()); 357 assert(LongBrMBB->size() + BalTgtMBBSize == LongBranchSeqSize); 358 } else { 359 // $longbr: 360 // j $tgt 361 // nop 362 // $fallthrough: 363 // 364 Pos = LongBrMBB->begin(); 365 LongBrMBB->addSuccessor(TgtMBB); 366 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::J)).addMBB(TgtMBB); 367 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::NOP))->setIsInsideBundle(); 368 369 assert(LongBrMBB->size() == LongBranchSeqSize); 370 } 371 372 if (I.Br->isUnconditionalBranch()) { 373 // Change branch destination. 374 assert(I.Br->getDesc().getNumOperands() == 1); 375 I.Br->RemoveOperand(0); 376 I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB)); 377 } else 378 // Change branch destination and reverse condition. 379 replaceBranch(*MBB, I.Br, DL, FallThroughMBB); 380} 381 382static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) { 383 MachineBasicBlock &MBB = F.front(); 384 MachineBasicBlock::iterator I = MBB.begin(); 385 DebugLoc DL = MBB.findDebugLoc(MBB.begin()); 386 BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0) 387 .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI); 388 BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0) 389 .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO); 390 MBB.removeLiveIn(Mips::V0); 391} 392 393bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { 394 if ((TM.getRelocationModel() == Reloc::PIC_) && 395 TM.getSubtarget<MipsSubtarget>().isABI_O32() && 396 F.getInfo<MipsFunctionInfo>()->globalBaseRegSet()) 397 emitGPDisp(F, TII); 398 399 if (SkipLongBranch) 400 return true; 401 402 MF = &F; 403 initMBBInfo(); 404 405 SmallVector<MBBInfo, 16>::iterator I, E = MBBInfos.end(); 406 bool EverMadeChange = false, MadeChange = true; 407 408 while (MadeChange) { 409 MadeChange = false; 410 411 for (I = MBBInfos.begin(); I != E; ++I) { 412 // Skip if this MBB doesn't have a branch or the branch has already been 413 // converted to a long branch. 414 if (!I->Br || I->HasLongBranch) 415 continue; 416 417 // Check if offset fits into 16-bit immediate field of branches. 418 if (!ForceLongBranch && isInt<16>(computeOffset(I->Br) / 4)) 419 continue; 420 421 I->HasLongBranch = true; 422 I->Size += LongBranchSeqSize * 4; 423 ++LongBranches; 424 EverMadeChange = MadeChange = true; 425 } 426 } 427 428 if (!EverMadeChange) 429 return true; 430 431 // Compute basic block addresses. 432 if (TM.getRelocationModel() == Reloc::PIC_) { 433 uint64_t Address = 0; 434 435 for (I = MBBInfos.begin(); I != E; Address += I->Size, ++I) 436 I->Address = Address; 437 } 438 439 // Do the expansion. 440 for (I = MBBInfos.begin(); I != E; ++I) 441 if (I->HasLongBranch) 442 expandToLongBranch(*I); 443 444 MF->RenumberBlocks(); 445 446 return true; 447} 448