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