ARMConstantIslandPass.cpp revision 1ee29257428960fede862fcfdbe80d5d007927e9
1//===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under the 6// University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains a pass that splits the constant pool up into 'islands' 11// which are scattered through-out the function. This is required due to the 12// limited pc-relative displacements that ARM has. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "arm-cp-islands" 17#include "ARM.h" 18#include "ARMMachineFunctionInfo.h" 19#include "ARMInstrInfo.h" 20#include "llvm/CodeGen/MachineConstantPool.h" 21#include "llvm/CodeGen/MachineFunctionPass.h" 22#include "llvm/CodeGen/MachineInstrBuilder.h" 23#include "llvm/CodeGen/MachineJumpTableInfo.h" 24#include "llvm/Target/TargetAsmInfo.h" 25#include "llvm/Target/TargetData.h" 26#include "llvm/Target/TargetMachine.h" 27#include "llvm/Support/Compiler.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/ADT/STLExtras.h" 30#include "llvm/ADT/Statistic.h" 31#include <iostream> 32using namespace llvm; 33 34STATISTIC(NumSplit, "Number of uncond branches inserted"); 35 36namespace { 37 /// ARMConstantIslands - Due to limited pc-relative displacements, ARM 38 /// requires constant pool entries to be scattered among the instructions 39 /// inside a function. To do this, it completely ignores the normal LLVM 40 /// constant pool, instead, it places constants where-ever it feels like with 41 /// special instructions. 42 /// 43 /// The terminology used in this pass includes: 44 /// Islands - Clumps of constants placed in the function. 45 /// Water - Potential places where an island could be formed. 46 /// CPE - A constant pool entry that has been placed somewhere, which 47 /// tracks a list of users. 48 class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { 49 /// NextUID - Assign unique ID's to CPE's. 50 unsigned NextUID; 51 52 /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 53 /// by MBB Number. 54 std::vector<unsigned> BBSizes; 55 56 /// WaterList - A sorted list of basic blocks where islands could be placed 57 /// (i.e. blocks that don't fall through to the following block, due 58 /// to a return, unreachable, or unconditional branch). 59 std::vector<MachineBasicBlock*> WaterList; 60 61 /// CPUser - One user of a constant pool, keeping the machine instruction 62 /// pointer, the constant pool being referenced, and the max displacement 63 /// allowed from the instruction to the CP. 64 struct CPUser { 65 MachineInstr *MI; 66 MachineInstr *CPEMI; 67 unsigned MaxDisp; 68 CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp) 69 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp) {} 70 }; 71 72 /// CPUsers - Keep track of all of the machine instructions that use various 73 /// constant pools and their max displacement. 74 std::vector<CPUser> CPUsers; 75 76 /// ImmBranch - One per immediate branch, keeping the machine instruction 77 /// pointer, conditional or unconditional, the max displacement, 78 /// and (if isCond is true) the corresponding unconditional branch 79 /// opcode. 80 struct ImmBranch { 81 MachineInstr *MI; 82 unsigned MaxDisp : 31; 83 bool isCond : 1; 84 int UncondBr; 85 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 86 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 87 }; 88 89 /// Branches - Keep track of all the immediate branch instructions. 90 /// 91 std::vector<ImmBranch> ImmBranches; 92 93 const TargetInstrInfo *TII; 94 const TargetAsmInfo *TAI; 95 public: 96 virtual bool runOnMachineFunction(MachineFunction &Fn); 97 98 virtual const char *getPassName() const { 99 return "ARM constant island placement and branch shortening pass"; 100 } 101 102 private: 103 void DoInitialPlacement(MachineFunction &Fn, 104 std::vector<MachineInstr*> &CPEMIs); 105 void InitialFunctionScan(MachineFunction &Fn, 106 const std::vector<MachineInstr*> &CPEMIs); 107 void SplitBlockBeforeInstr(MachineInstr *MI); 108 void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 109 bool HandleConstantPoolUser(MachineFunction &Fn, CPUser &U); 110 bool FixUpImmediateBranch(MachineFunction &Fn, ImmBranch &Br); 111 112 unsigned GetInstSize(MachineInstr *MI) const; 113 unsigned GetOffsetOf(MachineInstr *MI) const; 114 unsigned GetOffsetOf(MachineBasicBlock *MBB) const; 115 }; 116} 117 118/// createARMConstantIslandPass - returns an instance of the constpool 119/// island pass. 120FunctionPass *llvm::createARMConstantIslandPass() { 121 return new ARMConstantIslands(); 122} 123 124bool ARMConstantIslands::runOnMachineFunction(MachineFunction &Fn) { 125 MachineConstantPool &MCP = *Fn.getConstantPool(); 126 127 TII = Fn.getTarget().getInstrInfo(); 128 TAI = Fn.getTarget().getTargetAsmInfo(); 129 130 // Renumber all of the machine basic blocks in the function, guaranteeing that 131 // the numbers agree with the position of the block in the function. 132 Fn.RenumberBlocks(); 133 134 // Perform the initial placement of the constant pool entries. To start with, 135 // we put them all at the end of the function. 136 std::vector<MachineInstr*> CPEMIs; 137 if (!MCP.isEmpty()) 138 DoInitialPlacement(Fn, CPEMIs); 139 140 /// The next UID to take is the first unused one. 141 NextUID = CPEMIs.size(); 142 143 // Do the initial scan of the function, building up information about the 144 // sizes of each block, the location of all the water, and finding all of the 145 // constant pool users. 146 InitialFunctionScan(Fn, CPEMIs); 147 CPEMIs.clear(); 148 149 // Iteratively place constant pool entries until there is no change. 150 bool MadeChange; 151 do { 152 MadeChange = false; 153 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 154 MadeChange |= HandleConstantPoolUser(Fn, CPUsers[i]); 155 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 156 MadeChange |= FixUpImmediateBranch(Fn, ImmBranches[i]); 157 } while (MadeChange); 158 159 BBSizes.clear(); 160 WaterList.clear(); 161 CPUsers.clear(); 162 ImmBranches.clear(); 163 164 return true; 165} 166 167/// DoInitialPlacement - Perform the initial placement of the constant pool 168/// entries. To start with, we put them all at the end of the function. 169void ARMConstantIslands::DoInitialPlacement(MachineFunction &Fn, 170 std::vector<MachineInstr*> &CPEMIs){ 171 // Create the basic block to hold the CPE's. 172 MachineBasicBlock *BB = new MachineBasicBlock(); 173 Fn.getBasicBlockList().push_back(BB); 174 175 // Add all of the constants from the constant pool to the end block, use an 176 // identity mapping of CPI's to CPE's. 177 const std::vector<MachineConstantPoolEntry> &CPs = 178 Fn.getConstantPool()->getConstants(); 179 180 const TargetData &TD = *Fn.getTarget().getTargetData(); 181 for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 182 unsigned Size = TD.getTypeSize(CPs[i].getType()); 183 // Verify that all constant pool entries are a multiple of 4 bytes. If not, 184 // we would have to pad them out or something so that instructions stay 185 // aligned. 186 assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 187 MachineInstr *CPEMI = 188 BuildMI(BB, TII->get(ARM::CONSTPOOL_ENTRY)) 189 .addImm(i).addConstantPoolIndex(i).addImm(Size); 190 CPEMIs.push_back(CPEMI); 191 DEBUG(std::cerr << "Moved CPI#" << i << " to end of function as #" 192 << i << "\n"); 193 } 194} 195 196/// BBHasFallthrough - Return true of the specified basic block can fallthrough 197/// into the block immediately after it. 198static bool BBHasFallthrough(MachineBasicBlock *MBB) { 199 // Get the next machine basic block in the function. 200 MachineFunction::iterator MBBI = MBB; 201 if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 202 return false; 203 204 MachineBasicBlock *NextBB = next(MBBI); 205 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 206 E = MBB->succ_end(); I != E; ++I) 207 if (*I == NextBB) 208 return true; 209 210 return false; 211} 212 213/// InitialFunctionScan - Do the initial scan of the function, building up 214/// information about the sizes of each block, the location of all the water, 215/// and finding all of the constant pool users. 216void ARMConstantIslands::InitialFunctionScan(MachineFunction &Fn, 217 const std::vector<MachineInstr*> &CPEMIs) { 218 for (MachineFunction::iterator MBBI = Fn.begin(), E = Fn.end(); 219 MBBI != E; ++MBBI) { 220 MachineBasicBlock &MBB = *MBBI; 221 222 // If this block doesn't fall through into the next MBB, then this is 223 // 'water' that a constant pool island could be placed. 224 if (!BBHasFallthrough(&MBB)) 225 WaterList.push_back(&MBB); 226 227 unsigned MBBSize = 0; 228 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 229 I != E; ++I) { 230 // Add instruction size to MBBSize. 231 MBBSize += GetInstSize(I); 232 233 int Opc = I->getOpcode(); 234 if (TII->isBranch(Opc)) { 235 bool isCond = false; 236 unsigned Bits = 0; 237 unsigned Scale = 1; 238 int UOpc = Opc; 239 switch (Opc) { 240 default: 241 continue; // Ignore JT branches 242 case ARM::Bcc: 243 isCond = true; 244 UOpc = ARM::B; 245 // Fallthrough 246 case ARM::B: 247 Bits = 24; 248 Scale = 4; 249 break; 250 case ARM::tBcc: 251 isCond = true; 252 UOpc = ARM::tB; 253 Bits = 8; 254 Scale = 2; 255 break; 256 case ARM::tB: 257 Bits = 11; 258 Scale = 2; 259 break; 260 } 261 unsigned MaxDisp = (1 << (Bits-1)) * Scale; 262 ImmBranches.push_back(ImmBranch(I, MaxDisp, isCond, UOpc)); 263 } 264 265 // Scan the instructions for constant pool operands. 266 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 267 if (I->getOperand(op).isConstantPoolIndex()) { 268 // We found one. The addressing mode tells us the max displacement 269 // from the PC that this instruction permits. 270 unsigned MaxOffs = 0; 271 272 // Basic size info comes from the TSFlags field. 273 unsigned TSFlags = I->getInstrDescriptor()->TSFlags; 274 switch (TSFlags & ARMII::AddrModeMask) { 275 default: 276 // Constant pool entries can reach anything. 277 if (I->getOpcode() == ARM::CONSTPOOL_ENTRY) 278 continue; 279 assert(0 && "Unknown addressing mode for CP reference!"); 280 case ARMII::AddrMode1: // AM1: 8 bits << 2 281 MaxOffs = 1 << (8+2); // Taking the address of a CP entry. 282 break; 283 case ARMII::AddrMode2: 284 MaxOffs = 1 << 12; // +-offset_12 285 break; 286 case ARMII::AddrMode3: 287 MaxOffs = 1 << 8; // +-offset_8 288 break; 289 // addrmode4 has no immediate offset. 290 case ARMII::AddrMode5: 291 MaxOffs = 1 << (8+2); // +-(offset_8*4) 292 break; 293 case ARMII::AddrModeT1: 294 MaxOffs = 1 << 5; 295 break; 296 case ARMII::AddrModeT2: 297 MaxOffs = 1 << (5+1); 298 break; 299 case ARMII::AddrModeT4: 300 MaxOffs = 1 << (5+2); 301 break; 302 case ARMII::AddrModeTs: 303 MaxOffs = 1 << (8+2); 304 break; 305 } 306 307 // Remember that this is a user of a CP entry. 308 MachineInstr *CPEMI =CPEMIs[I->getOperand(op).getConstantPoolIndex()]; 309 CPUsers.push_back(CPUser(I, CPEMI, MaxOffs)); 310 311 // Instructions can only use one CP entry, don't bother scanning the 312 // rest of the operands. 313 break; 314 } 315 } 316 BBSizes.push_back(MBBSize); 317 } 318} 319 320/// FIXME: Works around a gcc miscompilation with -fstrict-aliasing 321static unsigned getNumJTEntries(const std::vector<MachineJumpTableEntry> &JT, 322 unsigned JTI) DISABLE_INLINE; 323static unsigned getNumJTEntries(const std::vector<MachineJumpTableEntry> &JT, 324 unsigned JTI) { 325 return JT[JTI].MBBs.size(); 326} 327 328/// GetInstSize - Return the size of the specified MachineInstr. 329/// 330unsigned ARMConstantIslands::GetInstSize(MachineInstr *MI) const { 331 // Basic size info comes from the TSFlags field. 332 unsigned TSFlags = MI->getInstrDescriptor()->TSFlags; 333 334 switch ((TSFlags & ARMII::SizeMask) >> ARMII::SizeShift) { 335 default: 336 // If this machine instr is an inline asm, measure it. 337 if (MI->getOpcode() == ARM::INLINEASM) 338 return TAI->getInlineAsmLength(MI->getOperand(0).getSymbolName()); 339 if (MI->getOpcode() == ARM::LABEL) 340 return 0; 341 assert(0 && "Unknown or unset size field for instr!"); 342 break; 343 case ARMII::Size8Bytes: return 8; // Arm instruction x 2. 344 case ARMII::Size4Bytes: return 4; // Arm instruction. 345 case ARMII::Size2Bytes: return 2; // Thumb instruction. 346 case ARMII::SizeSpecial: { 347 switch (MI->getOpcode()) { 348 case ARM::CONSTPOOL_ENTRY: 349 // If this machine instr is a constant pool entry, its size is recorded as 350 // operand #2. 351 return MI->getOperand(2).getImm(); 352 case ARM::BR_JTr: 353 case ARM::BR_JTm: 354 case ARM::BR_JTadd: { 355 // These are jumptable branches, i.e. a branch followed by an inlined 356 // jumptable. The size is 4 + 4 * number of entries. 357 unsigned JTI = MI->getOperand(MI->getNumOperands()-2).getJumpTableIndex(); 358 const MachineFunction *MF = MI->getParent()->getParent(); 359 MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); 360 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); 361 assert(JTI < JT.size()); 362 return getNumJTEntries(JT, JTI) * 4 + 4; 363 } 364 default: 365 // Otherwise, pseudo-instruction sizes are zero. 366 return 0; 367 } 368 } 369 } 370} 371 372/// GetOffsetOf - Return the current offset of the specified machine instruction 373/// from the start of the function. This offset changes as stuff is moved 374/// around inside the function. 375unsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 376 MachineBasicBlock *MBB = MI->getParent(); 377 378 // The offset is composed of two things: the sum of the sizes of all MBB's 379 // before this instruction's block, and the offset from the start of the block 380 // it is in. 381 unsigned Offset = 0; 382 383 // Sum block sizes before MBB. 384 for (unsigned BB = 0, e = MBB->getNumber(); BB != e; ++BB) 385 Offset += BBSizes[BB]; 386 387 // Sum instructions before MI in MBB. 388 for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 389 assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 390 if (&*I == MI) return Offset; 391 Offset += GetInstSize(I); 392 } 393} 394 395/// GetOffsetOf - Return the current offset of the specified machine BB 396/// from the start of the function. This offset changes as stuff is moved 397/// around inside the function. 398unsigned ARMConstantIslands::GetOffsetOf(MachineBasicBlock *MBB) const { 399 // Sum block sizes before MBB. 400 unsigned Offset = 0; 401 for (unsigned BB = 0, e = MBB->getNumber(); BB != e; ++BB) 402 Offset += BBSizes[BB]; 403 404 return Offset; 405} 406 407/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 408/// ID. 409static bool CompareMBBNumbers(const MachineBasicBlock *LHS, 410 const MachineBasicBlock *RHS) { 411 return LHS->getNumber() < RHS->getNumber(); 412} 413 414/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 415/// machine function, it upsets all of the block numbers. Renumber the blocks 416/// and update the arrays that parallel this numbering. 417void ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 418 // Renumber the MBB's to keep them consequtive. 419 NewBB->getParent()->RenumberBlocks(NewBB); 420 421 // Insert a size into BBSizes to align it properly with the (newly 422 // renumbered) block numbers. 423 BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 424 425 // Next, update WaterList. Specifically, we need to add NewMBB as having 426 // available water after it. 427 std::vector<MachineBasicBlock*>::iterator IP = 428 std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 429 CompareMBBNumbers); 430 WaterList.insert(IP, NewBB); 431} 432 433 434/// Split the basic block containing MI into two blocks, which are joined by 435/// an unconditional branch. Update datastructures and renumber blocks to 436/// account for this change. 437void ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 438 MachineBasicBlock *OrigBB = MI->getParent(); 439 const ARMFunctionInfo *AFI = OrigBB->getParent()->getInfo<ARMFunctionInfo>(); 440 bool isThumb = AFI->isThumbFunction(); 441 442 // Create a new MBB for the code after the OrigBB. 443 MachineBasicBlock *NewBB = new MachineBasicBlock(OrigBB->getBasicBlock()); 444 MachineFunction::iterator MBBI = OrigBB; ++MBBI; 445 OrigBB->getParent()->getBasicBlockList().insert(MBBI, NewBB); 446 447 // Splice the instructions starting with MI over to NewBB. 448 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 449 450 // Add an unconditional branch from OrigBB to NewBB. 451 BuildMI(OrigBB, TII->get(isThumb ? ARM::tB : ARM::B)).addMBB(NewBB); 452 NumSplit++; 453 454 // Update the CFG. All succs of OrigBB are now succs of NewBB. 455 while (!OrigBB->succ_empty()) { 456 MachineBasicBlock *Succ = *OrigBB->succ_begin(); 457 OrigBB->removeSuccessor(Succ); 458 NewBB->addSuccessor(Succ); 459 460 // This pass should be run after register allocation, so there should be no 461 // PHI nodes to update. 462 assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 463 && "PHI nodes should be eliminated by now!"); 464 } 465 466 // OrigBB branches to NewBB. 467 OrigBB->addSuccessor(NewBB); 468 469 // Update internal data structures to account for the newly inserted MBB. 470 UpdateForInsertedWaterBlock(NewBB); 471 472 // Figure out how large the first NewMBB is. 473 unsigned NewBBSize = 0; 474 for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 475 I != E; ++I) 476 NewBBSize += GetInstSize(I); 477 478 // Set the size of NewBB in BBSizes. 479 BBSizes[NewBB->getNumber()] = NewBBSize; 480 481 // We removed instructions from UserMBB, subtract that off from its size. 482 // Add 2 or 4 to the block to count the unconditional branch we added to it. 483 BBSizes[OrigBB->getNumber()] -= NewBBSize - (isThumb ? 2 : 4); 484} 485 486/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 487/// is out-of-range. If so, pick it up the constant pool value and move it some 488/// place in-range. 489bool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &Fn, CPUser &U){ 490 MachineInstr *UserMI = U.MI; 491 MachineInstr *CPEMI = U.CPEMI; 492 493 unsigned UserOffset = GetOffsetOf(UserMI); 494 unsigned CPEOffset = GetOffsetOf(CPEMI); 495 496 DEBUG(std::cerr << "User of CPE#" << CPEMI->getOperand(0).getImm() 497 << " max delta=" << U.MaxDisp 498 << " at offset " << int(UserOffset-CPEOffset) << "\t" 499 << *UserMI); 500 501 // Check to see if the CPE is already in-range. 502 if (UserOffset < CPEOffset) { 503 // User before the CPE. 504 if (CPEOffset-UserOffset <= U.MaxDisp) 505 return false; 506 } else { 507 if (UserOffset-CPEOffset <= U.MaxDisp) 508 return false; 509 } 510 511 512 // Solution guaranteed to work: split the user's MBB right before the user and 513 // insert a clone the CPE into the newly created water. 514 515 // If the user isn't at the start of its MBB, or if there is a fall-through 516 // into the user's MBB, split the MBB before the User. 517 MachineBasicBlock *UserMBB = UserMI->getParent(); 518 if (&UserMBB->front() != UserMI || 519 UserMBB == &Fn.front() || // entry MBB of function. 520 BBHasFallthrough(prior(MachineFunction::iterator(UserMBB)))) { 521 // TODO: Search for the best place to split the code. In practice, using 522 // loop nesting information to insert these guys outside of loops would be 523 // sufficient. 524 SplitBlockBeforeInstr(UserMI); 525 526 // UserMI's BB may have changed. 527 UserMBB = UserMI->getParent(); 528 } 529 530 // Okay, we know we can put an island before UserMBB now, do it! 531 MachineBasicBlock *NewIsland = new MachineBasicBlock(); 532 Fn.getBasicBlockList().insert(UserMBB, NewIsland); 533 534 // Update internal data structures to account for the newly inserted MBB. 535 UpdateForInsertedWaterBlock(NewIsland); 536 537 // Now that we have an island to add the CPE to, clone the original CPE and 538 // add it to the island. 539 unsigned ID = NextUID++; 540 unsigned CPI = CPEMI->getOperand(1).getConstantPoolIndex(); 541 unsigned Size = CPEMI->getOperand(2).getImm(); 542 543 // Build a new CPE for this user. 544 U.CPEMI = BuildMI(NewIsland, TII->get(ARM::CONSTPOOL_ENTRY)) 545 .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 546 547 // Increase the size of the island block to account for the new entry. 548 BBSizes[NewIsland->getNumber()] += Size; 549 550 // Finally, change the CPI in the instruction operand to be ID. 551 for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 552 if (UserMI->getOperand(i).isConstantPoolIndex()) { 553 UserMI->getOperand(i).setConstantPoolIndex(ID); 554 break; 555 } 556 557 DEBUG(std::cerr << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" 558 << *UserMI); 559 560 561 return true; 562} 563 564/// FixUpImmediateBranch - Fix up immediate branches whose destination is too 565/// far away to fit in its displacement field. If it is a conditional branch, 566/// then it is converted to an inverse conditional branch + an unconditional 567/// branch to the destination. If it is an unconditional branch, then it is 568/// converted to a branch to a branch. 569bool 570ARMConstantIslands::FixUpImmediateBranch(MachineFunction &Fn, ImmBranch &Br) { 571 MachineInstr *MI = Br.MI; 572 MachineBasicBlock *DestBB = MI->getOperand(0).getMachineBasicBlock(); 573 574 unsigned BrOffset = GetOffsetOf(MI); 575 unsigned DestOffset = GetOffsetOf(DestBB); 576 577 // Check to see if the destination BB is in range. 578 if (BrOffset < DestOffset) { 579 if (DestOffset - BrOffset < Br.MaxDisp) 580 return false; 581 } else { 582 if (BrOffset - DestOffset <= Br.MaxDisp) 583 return false; 584 } 585 586 if (!Br.isCond) { 587 // Unconditional branch. We have to insert a branch somewhere to perform 588 // a two level branch (branch to branch). FIXME: not yet implemented. 589 assert(false && "Can't handle unconditional branch yet!"); 590 return false; 591 } 592 593 // Otherwise, add a unconditional branch to the destination and 594 // invert the branch condition to jump over it: 595 // blt L1 596 // => 597 // bge L2 598 // b L1 599 // L2: 600 ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImmedValue(); 601 CC = ARMCC::getOppositeCondition(CC); 602 603 // If the branch is at the end of its MBB and that has a fall-through block, 604 // direct the updated conditional branch to the fall-through block. Otherwise, 605 // split the MBB before the next instruction. 606 MachineBasicBlock *MBB = MI->getParent(); 607 if (&MBB->back() != MI || !BBHasFallthrough(MBB)) { 608 SplitBlockBeforeInstr(MI); 609 // No need for the branch to the next block. We're adding a unconditional 610 // branch to the destination. 611 MBB->back().eraseFromParent(); 612 } 613 MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 614 615 // Insert a unconditional branch and replace the conditional branch. 616 // Also update the ImmBranch as well as adding a new entry for the new branch. 617 BuildMI(MBB, TII->get(MI->getOpcode())).addMBB(NextBB).addImm(CC); 618 Br.MI = &MBB->back(); 619 BuildMI(MBB, TII->get(Br.UncondBr)).addMBB(DestBB); 620 unsigned MaxDisp = (Br.UncondBr == ARM::tB) ? (1<<10)*2 : (1<<23)*4; 621 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 622 MI->eraseFromParent(); 623 624 // Increase the size of MBB to account for the new unconditional branch. 625 BBSizes[MBB->getNumber()] += GetInstSize(&MBB->back()); 626 return true; 627} 628