MipsLongBranch.cpp revision a32ccf92c1d53e0f16d2f29ad1fae75c3aa013a0
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 bool offsetFitsIntoField(const MachineInstr *Br); 77 unsigned addLongBranch(MachineBasicBlock &MBB, Iter Pos, 78 MachineBasicBlock *Tgt, DebugLoc DL, bool Nop); 79 void replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL, 80 MachineBasicBlock *MBBOpnd); 81 void expandToLongBranch(MBBInfo &Info); 82 83 const TargetMachine &TM; 84 const MipsInstrInfo *TII; 85 MachineFunction *MF; 86 SmallVector<MBBInfo, 16> MBBInfos; 87 }; 88 89 char MipsLongBranch::ID = 0; 90} // end of anonymous namespace 91 92/// createMipsLongBranchPass - Returns a pass that converts branches to long 93/// branches. 94FunctionPass *llvm::createMipsLongBranchPass(MipsTargetMachine &tm) { 95 return new MipsLongBranch(tm); 96} 97 98/// Iterate over list of Br's operands and search for a MachineBasicBlock 99/// operand. 100static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) { 101 for (unsigned I = 0, E = Br.getDesc().getNumOperands(); I < E; ++I) { 102 const MachineOperand &MO = Br.getOperand(I); 103 104 if (MO.isMBB()) 105 return MO.getMBB(); 106 } 107 108 assert(false && "This instruction does not have an MBB operand."); 109 return 0; 110} 111 112// Traverse the list of instructions backwards until a non-debug instruction is 113// found or it reaches E. 114static ReverseIter getNonDebugInstr(ReverseIter B, ReverseIter E) { 115 for (; B != E; ++B) 116 if (!B->isDebugValue()) 117 return B; 118 119 return E; 120} 121 122// Split MBB if it has two direct jumps/branches. 123void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) { 124 ReverseIter End = MBB->rend(); 125 ReverseIter LastBr = getNonDebugInstr(MBB->rbegin(), End); 126 127 // Return if MBB has no branch instructions. 128 if ((LastBr == End) || 129 (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch())) 130 return; 131 132 ReverseIter FirstBr = getNonDebugInstr(next(LastBr), End); 133 134 // MBB has only one branch instruction if FirstBr is not a branch 135 // instruction. 136 if ((FirstBr == End) || 137 (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch())) 138 return; 139 140 assert(!FirstBr->isIndirectBranch() && "Unexpected indirect branch found."); 141 142 // Create a new MBB. Move instructions in MBB to the newly created MBB. 143 MachineBasicBlock *NewMBB = 144 MF->CreateMachineBasicBlock(MBB->getBasicBlock()); 145 146 // Insert NewMBB and fix control flow. 147 MachineBasicBlock *Tgt = getTargetMBB(*FirstBr); 148 NewMBB->transferSuccessors(MBB); 149 NewMBB->removeSuccessor(Tgt); 150 MBB->addSuccessor(NewMBB); 151 MBB->addSuccessor(Tgt); 152 MF->insert(next(MachineFunction::iterator(MBB)), NewMBB); 153 154 NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end()); 155} 156 157// Fill MBBInfos. 158void MipsLongBranch::initMBBInfo() { 159 // Split the MBBs if they have two branches. Each basic block should have at 160 // most one branch after this loop is executed. 161 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E;) 162 splitMBB(I++); 163 164 MF->RenumberBlocks(); 165 MBBInfos.clear(); 166 MBBInfos.resize(MF->size()); 167 168 for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) { 169 MachineBasicBlock *MBB = MF->getBlockNumbered(I); 170 171 // Compute size of MBB. 172 for (MachineBasicBlock::instr_iterator MI = MBB->instr_begin(); 173 MI != MBB->instr_end(); ++MI) 174 MBBInfos[I].Size += TII->GetInstSizeInBytes(&*MI); 175 176 // Search for MBB's branch instruction. 177 ReverseIter End = MBB->rend(); 178 ReverseIter Br = getNonDebugInstr(MBB->rbegin(), End); 179 180 if ((Br != End) && !Br->isIndirectBranch() && 181 (Br->isConditionalBranch() || Br->isUnconditionalBranch())) 182 MBBInfos[I].Br = (++Br).base(); 183 } 184} 185 186// Compute offset of branch in number of bytes. 187int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) { 188 int64_t Offset = 0; 189 int ThisMBB = Br->getParent()->getNumber(); 190 int TargetMBB = getTargetMBB(*Br)->getNumber(); 191 192 // Compute offset of a forward branch. 193 if (ThisMBB < TargetMBB) { 194 for (int N = ThisMBB + 1; N < TargetMBB; ++N) 195 Offset += MBBInfos[N].Size; 196 197 return Offset + 4; 198 } 199 200 // Compute offset of a backward branch. 201 for (int N = ThisMBB; N >= TargetMBB; --N) 202 Offset += MBBInfos[N].Size; 203 204 return -Offset + 4; 205} 206 207// Insert the following sequence: 208// (pic or N64) 209// lw $at, global_reg_slot 210// lw $at, got($L1)($at) 211// addiu $at, $at, lo($L1) 212// jr $at 213// noop 214// (static and !N64) 215// lui $at, hi($L1) 216// addiu $at, $at, lo($L1) 217// jr $at 218// noop 219unsigned MipsLongBranch::addLongBranch(MachineBasicBlock &MBB, Iter Pos, 220 MachineBasicBlock *Tgt, DebugLoc DL, 221 bool Nop) { 222 MF->getInfo<MipsFunctionInfo>()->setEmitNOAT(); 223 bool IsPIC = (TM.getRelocationModel() == Reloc::PIC_); 224 unsigned ABI = TM.getSubtarget<MipsSubtarget>().getTargetABI(); 225 bool N64 = (ABI == MipsSubtarget::N64); 226 unsigned NumInstrs; 227 228 if (IsPIC || N64) { 229 bool HasMips64 = TM.getSubtarget<MipsSubtarget>().hasMips64(); 230 unsigned AT = N64 ? Mips::AT_64 : Mips::AT; 231 unsigned Load = N64 ? Mips::LD_P8 : Mips::LW; 232 unsigned ADDiu = N64 ? Mips::DADDiu : Mips::ADDiu; 233 unsigned JR = N64 ? Mips::JR64 : Mips::JR; 234 unsigned GOTFlag = HasMips64 ? MipsII::MO_GOT_PAGE : MipsII::MO_GOT; 235 unsigned OFSTFlag = HasMips64 ? MipsII::MO_GOT_OFST : MipsII::MO_ABS_LO; 236 const MipsRegisterInfo *MRI = 237 static_cast<const MipsRegisterInfo*>(TM.getRegisterInfo()); 238 unsigned SP = MRI->getFrameRegister(*MF); 239 unsigned GlobalRegFI = MF->getInfo<MipsFunctionInfo>()->getGlobalRegFI(); 240 int64_t Offset = MF->getFrameInfo()->getObjectOffset(GlobalRegFI); 241 242 if (isInt<16>(Offset)) { 243 BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(SP).addImm(Offset); 244 NumInstrs = 1; 245 } else { 246 unsigned ADDu = N64 ? Mips::DADDu : Mips::ADDu; 247 MipsAnalyzeImmediate::Inst LastInst(0, 0); 248 249 MF->getInfo<MipsFunctionInfo>()->setEmitNOAT(); 250 NumInstrs = Mips::loadImmediate(Offset, N64, *TII, MBB, Pos, DL, true, 251 &LastInst) + 2; 252 BuildMI(MBB, Pos, DL, TII->get(ADDu), AT).addReg(SP).addReg(AT); 253 BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(AT) 254 .addImm(SignExtend64<16>(LastInst.ImmOpnd)); 255 } 256 257 BuildMI(MBB, Pos, DL, TII->get(Load), AT).addReg(AT).addMBB(Tgt, GOTFlag); 258 BuildMI(MBB, Pos, DL, TII->get(ADDiu), AT).addReg(AT).addMBB(Tgt, OFSTFlag); 259 BuildMI(MBB, Pos, DL, TII->get(JR)).addReg(Mips::AT, RegState::Kill); 260 NumInstrs += 3; 261 } else { 262 BuildMI(MBB, Pos, DL, TII->get(Mips::LUi), Mips::AT) 263 .addMBB(Tgt, MipsII::MO_ABS_HI); 264 BuildMI(MBB, Pos, DL, TII->get(Mips::ADDiu), Mips::AT) 265 .addReg(Mips::AT).addMBB(Tgt, MipsII::MO_ABS_LO); 266 BuildMI(MBB, Pos, DL, TII->get(Mips::JR)).addReg(Mips::AT, RegState::Kill); 267 NumInstrs = 3; 268 } 269 270 if (Nop) { 271 BuildMI(MBB, Pos, DL, TII->get(Mips::NOP))->setIsInsideBundle(); 272 ++NumInstrs; 273 } 274 275 return NumInstrs; 276} 277 278// Replace Br with a branch which has the opposite condition code and a 279// MachineBasicBlock operand MBBOpnd. 280void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br, 281 DebugLoc DL, MachineBasicBlock *MBBOpnd) { 282 unsigned NewOpc = Mips::GetOppositeBranchOpc(Br->getOpcode()); 283 const MCInstrDesc &NewDesc = TII->get(NewOpc); 284 285 MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc); 286 287 for (unsigned I = 0, E = Br->getDesc().getNumOperands(); I < E; ++I) { 288 MachineOperand &MO = Br->getOperand(I); 289 290 if (!MO.isReg()) { 291 assert(MO.isMBB() && "MBB operand expected."); 292 break; 293 } 294 295 MIB.addReg(MO.getReg()); 296 } 297 298 MIB.addMBB(MBBOpnd); 299 300 Br->eraseFromParent(); 301} 302 303// Expand branch instructions to long branches. 304void MipsLongBranch::expandToLongBranch(MBBInfo &I) { 305 I.HasLongBranch = true; 306 307 MachineBasicBlock *MBB = I.Br->getParent(), *Tgt = getTargetMBB(*I.Br); 308 DebugLoc DL = I.Br->getDebugLoc(); 309 310 if (I.Br->isUnconditionalBranch()) { 311 // Unconditional branch before transformation: 312 // b $tgt 313 // delay-slot-instr 314 // 315 // after transformation: 316 // delay-slot-instr 317 // lw $at, global_reg_slot 318 // lw $at, %got($tgt)($at) 319 // addiu $at, $at, %lo($tgt) 320 // jr $at 321 // nop 322 I.Size += (addLongBranch(*MBB, next(Iter(I.Br)), Tgt, DL, true) - 1) * 4; 323 324 // Remove branch and clear InsideBundle bit of the next instruction. 325 next(MachineBasicBlock::instr_iterator(I.Br))->setIsInsideBundle(false); 326 I.Br->eraseFromParent(); 327 return; 328 } 329 330 assert(I.Br->isConditionalBranch() && "Conditional branch expected."); 331 332 // Conditional branch before transformation: 333 // b cc, $tgt 334 // delay-slot-instr 335 // FallThrough: 336 // 337 // after transformation: 338 // b !cc, FallThrough 339 // delay-slot-instr 340 // NewMBB: 341 // lw $at, global_reg_slot 342 // lw $at, %got($tgt)($at) 343 // addiu $at, $at, %lo($tgt) 344 // jr $at 345 // noop 346 // FallThrough: 347 348 MachineBasicBlock *NewMBB = MF->CreateMachineBasicBlock(MBB->getBasicBlock()); 349 MF->insert(next(MachineFunction::iterator(MBB)), NewMBB); 350 MBB->removeSuccessor(Tgt); 351 MBB->addSuccessor(NewMBB); 352 NewMBB->addSuccessor(Tgt); 353 354 I.Size += addLongBranch(*NewMBB, NewMBB->begin(), Tgt, DL, true) * 4; 355 replaceBranch(*MBB, I.Br, DL, *MBB->succ_begin()); 356} 357 358static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) { 359 MachineBasicBlock &MBB = F.front(); 360 MachineBasicBlock::iterator I = MBB.begin(); 361 DebugLoc DL = MBB.findDebugLoc(MBB.begin()); 362 BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0) 363 .addExternalSymbol("_gp_disp", MipsII::MO_ABS_HI); 364 BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0) 365 .addReg(Mips::V0).addExternalSymbol("_gp_disp", MipsII::MO_ABS_LO); 366 MBB.removeLiveIn(Mips::V0); 367} 368 369bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { 370 if ((TM.getRelocationModel() == Reloc::PIC_) && 371 TM.getSubtarget<MipsSubtarget>().isABI_O32() && 372 F.getInfo<MipsFunctionInfo>()->globalBaseRegSet()) 373 emitGPDisp(F, TII); 374 375 if (SkipLongBranch) 376 return false; 377 378 MF = &F; 379 initMBBInfo(); 380 381 bool IsPIC = (TM.getRelocationModel() == Reloc::PIC_); 382 SmallVector<MBBInfo, 16>::iterator I, E = MBBInfos.end(); 383 bool EverMadeChange = false, MadeChange = true; 384 385 while (MadeChange) { 386 MadeChange = false; 387 388 for (I = MBBInfos.begin(); I != E; ++I) { 389 // Skip if this MBB doesn't have a branch or the branch has already been 390 // converted to a long branch. 391 if (!I->Br || I->HasLongBranch) 392 continue; 393 394 int64_t Offset = computeOffset(I->Br); 395 396 if (!ForceLongBranch) { 397 // Check if offset fits into 16-bit immediate field of branches. 398 if ((I->Br->isConditionalBranch() || IsPIC) && isInt<16>(Offset / 4)) 399 continue; 400 401 // Check if offset fits into 26-bit immediate field of jumps (J). 402 if (I->Br->isUnconditionalBranch() && !IsPIC && isInt<26>(Offset / 4)) 403 continue; 404 } 405 406 expandToLongBranch(*I); 407 ++LongBranches; 408 EverMadeChange = MadeChange = true; 409 } 410 } 411 412 if (EverMadeChange) 413 MF->RenumberBlocks(); 414 415 return EverMadeChange; 416} 417