MipsLongBranch.cpp revision e11dda8631f1e65417971ee0c2f7a661fc7d0fd7
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 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 288 MIBundleBuilder(*LongBrMBB, Pos) 289 .append(BuildMI(*MF, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB)) 290 .append(BuildMI(*MF, DL, TII->get(Mips::LUi), Mips::AT).addImm(Hi)); 291 292 Pos = BalTgtMBB->begin(); 293 294 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::AT) 295 .addReg(Mips::AT).addImm(Lo); 296 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT) 297 .addReg(Mips::RA).addReg(Mips::AT); 298 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA) 299 .addReg(Mips::SP).addImm(0); 300 301 MIBundleBuilder(*BalTgtMBB, Pos) 302 .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT)) 303 .append(BuildMI(*MF, DL, TII->get(Mips::ADDiu), Mips::SP) 304 .addReg(Mips::SP).addImm(8)); 305 } else { 306 // $longbr: 307 // daddiu $sp, $sp, -16 308 // sd $ra, 0($sp) 309 // lui64 $at, %highest($tgt - $baltgt) 310 // daddiu $at, $at, %higher($tgt - $baltgt) 311 // dsll $at, $at, 16 312 // daddiu $at, $at, %hi($tgt - $baltgt) 313 // bal $baltgt 314 // dsll $at, $at, 16 315 // $baltgt: 316 // daddiu $at, $at, %lo($tgt - $baltgt) 317 // daddu $at, $ra, $at 318 // ld $ra, 0($sp) 319 // jr64 $at 320 // daddiu $sp, $sp, 16 321 // $fallthrough: 322 // 323 324 int64_t Higher = SignExtend64<16>(((Offset + 0x80008000) >> 32) & 0xffff); 325 int64_t Highest = 326 SignExtend64<16>(((Offset + 0x800080008000LL) >> 48) & 0xffff); 327 328 Pos = LongBrMBB->begin(); 329 330 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64) 331 .addReg(Mips::SP_64).addImm(-16); 332 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD)).addReg(Mips::RA_64) 333 .addReg(Mips::SP_64).addImm(0); 334 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LUi64), Mips::AT_64) 335 .addImm(Highest); 336 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) 337 .addReg(Mips::AT_64).addImm(Higher); 338 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64) 339 .addReg(Mips::AT_64).addImm(16); 340 BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) 341 .addReg(Mips::AT_64).addImm(Hi); 342 343 MIBundleBuilder(*LongBrMBB, Pos) 344 .append(BuildMI(*MF, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB)) 345 .append(BuildMI(*MF, DL, TII->get(Mips::DSLL), Mips::AT_64) 346 .addReg(Mips::AT_64).addImm(16)); 347 348 Pos = BalTgtMBB->begin(); 349 350 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) 351 .addReg(Mips::AT_64).addImm(Lo); 352 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64) 353 .addReg(Mips::RA_64).addReg(Mips::AT_64); 354 BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64) 355 .addReg(Mips::SP_64).addImm(0); 356 357 MIBundleBuilder(*BalTgtMBB, Pos) 358 .append(BuildMI(*MF, DL, TII->get(Mips::JR64)).addReg(Mips::AT_64)) 359 .append(BuildMI(*MF, DL, TII->get(Mips::DADDiu), Mips::SP_64) 360 .addReg(Mips::SP_64).addImm(16)); 361 } 362 363 assert(BalTgtMBBSize == BalTgtMBB->size()); 364 assert(LongBrMBB->size() + BalTgtMBBSize == LongBranchSeqSize); 365 } else { 366 // $longbr: 367 // j $tgt 368 // nop 369 // $fallthrough: 370 // 371 Pos = LongBrMBB->begin(); 372 LongBrMBB->addSuccessor(TgtMBB); 373 MIBundleBuilder(*LongBrMBB, Pos) 374 .append(BuildMI(*MF, DL, TII->get(Mips::J)).addMBB(TgtMBB)) 375 .append(BuildMI(*MF, DL, TII->get(Mips::NOP))); 376 377 assert(LongBrMBB->size() == LongBranchSeqSize); 378 } 379 380 if (I.Br->isUnconditionalBranch()) { 381 // Change branch destination. 382 assert(I.Br->getDesc().getNumOperands() == 1); 383 I.Br->RemoveOperand(0); 384 I.Br->addOperand(MachineOperand::CreateMBB(LongBrMBB)); 385 } else 386 // Change branch destination and reverse condition. 387 replaceBranch(*MBB, I.Br, DL, FallThroughMBB); 388} 389 390static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) { 391 MachineBasicBlock &MBB = F.front(); 392 MachineBasicBlock::iterator I = MBB.begin(); 393 DebugLoc DL = MBB.findDebugLoc(MBB.begin()); 394 BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0) 395 .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI); 396 BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0) 397 .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO); 398 MBB.removeLiveIn(Mips::V0); 399} 400 401bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { 402 if ((TM.getRelocationModel() == Reloc::PIC_) && 403 TM.getSubtarget<MipsSubtarget>().isABI_O32() && 404 F.getInfo<MipsFunctionInfo>()->globalBaseRegSet()) 405 emitGPDisp(F, TII); 406 407 if (SkipLongBranch) 408 return true; 409 410 MF = &F; 411 initMBBInfo(); 412 413 SmallVector<MBBInfo, 16>::iterator I, E = MBBInfos.end(); 414 bool EverMadeChange = false, MadeChange = true; 415 416 while (MadeChange) { 417 MadeChange = false; 418 419 for (I = MBBInfos.begin(); I != E; ++I) { 420 // Skip if this MBB doesn't have a branch or the branch has already been 421 // converted to a long branch. 422 if (!I->Br || I->HasLongBranch) 423 continue; 424 425 // Check if offset fits into 16-bit immediate field of branches. 426 if (!ForceLongBranch && isInt<16>(computeOffset(I->Br) / 4)) 427 continue; 428 429 I->HasLongBranch = true; 430 I->Size += LongBranchSeqSize * 4; 431 ++LongBranches; 432 EverMadeChange = MadeChange = true; 433 } 434 } 435 436 if (!EverMadeChange) 437 return true; 438 439 // Compute basic block addresses. 440 if (TM.getRelocationModel() == Reloc::PIC_) { 441 uint64_t Address = 0; 442 443 for (I = MBBInfos.begin(); I != E; Address += I->Size, ++I) 444 I->Address = Address; 445 } 446 447 // Do the expansion. 448 for (I = MBBInfos.begin(); I != E; ++I) 449 if (I->HasLongBranch) 450 expandToLongBranch(*I); 451 452 MF->RenumberBlocks(); 453 454 return true; 455} 456