ARMConstantIslandPass.cpp revision 764ab52dd80310a205c9888bf166d09dab858f90
1//===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===// 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 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 "ARMAddressingModes.h" 19#include "ARMMachineFunctionInfo.h" 20#include "ARMInstrInfo.h" 21#include "llvm/CodeGen/MachineConstantPool.h" 22#include "llvm/CodeGen/MachineFunctionPass.h" 23#include "llvm/CodeGen/MachineInstrBuilder.h" 24#include "llvm/CodeGen/MachineJumpTableInfo.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/Support/ErrorHandling.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/ADT/STLExtras.h" 32#include "llvm/ADT/Statistic.h" 33using namespace llvm; 34 35STATISTIC(NumCPEs, "Number of constpool entries"); 36STATISTIC(NumSplit, "Number of uncond branches inserted"); 37STATISTIC(NumCBrFixed, "Number of cond branches fixed"); 38STATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 39STATISTIC(NumTBs, "Number of table branches generated"); 40 41namespace { 42 /// ARMConstantIslands - Due to limited PC-relative displacements, ARM 43 /// requires constant pool entries to be scattered among the instructions 44 /// inside a function. To do this, it completely ignores the normal LLVM 45 /// constant pool; instead, it places constants wherever it feels like with 46 /// special instructions. 47 /// 48 /// The terminology used in this pass includes: 49 /// Islands - Clumps of constants placed in the function. 50 /// Water - Potential places where an island could be formed. 51 /// CPE - A constant pool entry that has been placed somewhere, which 52 /// tracks a list of users. 53 class VISIBILITY_HIDDEN ARMConstantIslands : public MachineFunctionPass { 54 /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed 55 /// by MBB Number. The two-byte pads required for Thumb alignment are 56 /// counted as part of the following block (i.e., the offset and size for 57 /// a padded block will both be ==2 mod 4). 58 std::vector<unsigned> BBSizes; 59 60 /// BBOffsets - the offset of each MBB in bytes, starting from 0. 61 /// The two-byte pads required for Thumb alignment are counted as part of 62 /// the following block. 63 std::vector<unsigned> BBOffsets; 64 65 /// WaterList - A sorted list of basic blocks where islands could be placed 66 /// (i.e. blocks that don't fall through to the following block, due 67 /// to a return, unreachable, or unconditional branch). 68 std::vector<MachineBasicBlock*> WaterList; 69 70 /// CPUser - One user of a constant pool, keeping the machine instruction 71 /// pointer, the constant pool being referenced, and the max displacement 72 /// allowed from the instruction to the CP. 73 struct CPUser { 74 MachineInstr *MI; 75 MachineInstr *CPEMI; 76 unsigned MaxDisp; 77 bool NegOk; 78 bool IsSoImm; 79 CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, 80 bool neg, bool soimm) 81 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {} 82 }; 83 84 /// CPUsers - Keep track of all of the machine instructions that use various 85 /// constant pools and their max displacement. 86 std::vector<CPUser> CPUsers; 87 88 /// CPEntry - One per constant pool entry, keeping the machine instruction 89 /// pointer, the constpool index, and the number of CPUser's which 90 /// reference this entry. 91 struct CPEntry { 92 MachineInstr *CPEMI; 93 unsigned CPI; 94 unsigned RefCount; 95 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 96 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 97 }; 98 99 /// CPEntries - Keep track of all of the constant pool entry machine 100 /// instructions. For each original constpool index (i.e. those that 101 /// existed upon entry to this pass), it keeps a vector of entries. 102 /// Original elements are cloned as we go along; the clones are 103 /// put in the vector of the original element, but have distinct CPIs. 104 std::vector<std::vector<CPEntry> > CPEntries; 105 106 /// ImmBranch - One per immediate branch, keeping the machine instruction 107 /// pointer, conditional or unconditional, the max displacement, 108 /// and (if isCond is true) the corresponding unconditional branch 109 /// opcode. 110 struct ImmBranch { 111 MachineInstr *MI; 112 unsigned MaxDisp : 31; 113 bool isCond : 1; 114 int UncondBr; 115 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 116 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 117 }; 118 119 /// ImmBranches - Keep track of all the immediate branch instructions. 120 /// 121 std::vector<ImmBranch> ImmBranches; 122 123 /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 124 /// 125 SmallVector<MachineInstr*, 4> PushPopMIs; 126 127 /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions. 128 SmallVector<MachineInstr*, 4> T2JumpTables; 129 130 /// HasFarJump - True if any far jump instruction has been emitted during 131 /// the branch fix up pass. 132 bool HasFarJump; 133 134 const TargetInstrInfo *TII; 135 const ARMSubtarget *STI; 136 ARMFunctionInfo *AFI; 137 bool isThumb; 138 bool isThumb1; 139 bool isThumb2; 140 public: 141 static char ID; 142 ARMConstantIslands() : MachineFunctionPass(&ID) {} 143 144 virtual bool runOnMachineFunction(MachineFunction &MF); 145 146 virtual const char *getPassName() const { 147 return "ARM constant island placement and branch shortening pass"; 148 } 149 150 private: 151 void DoInitialPlacement(MachineFunction &MF, 152 std::vector<MachineInstr*> &CPEMIs); 153 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 154 void InitialFunctionScan(MachineFunction &MF, 155 const std::vector<MachineInstr*> &CPEMIs); 156 MachineBasicBlock *SplitBlockBeforeInstr(MachineInstr *MI); 157 void UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB); 158 void AdjustBBOffsetsAfter(MachineBasicBlock *BB, int delta); 159 bool DecrementOldEntry(unsigned CPI, MachineInstr* CPEMI); 160 int LookForExistingCPEntry(CPUser& U, unsigned UserOffset); 161 bool LookForWater(CPUser&U, unsigned UserOffset, 162 MachineBasicBlock** NewMBB); 163 MachineBasicBlock* AcceptWater(MachineBasicBlock *WaterBB, 164 std::vector<MachineBasicBlock*>::iterator IP); 165 void CreateNewWater(unsigned CPUserIndex, unsigned UserOffset, 166 MachineBasicBlock** NewMBB); 167 bool HandleConstantPoolUser(MachineFunction &MF, unsigned CPUserIndex); 168 void RemoveDeadCPEMI(MachineInstr *CPEMI); 169 bool RemoveUnusedCPEntries(); 170 bool CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 171 MachineInstr *CPEMI, unsigned Disp, bool NegOk, 172 bool DoDump = false); 173 bool WaterIsInRange(unsigned UserOffset, MachineBasicBlock *Water, 174 CPUser &U); 175 bool OffsetIsInRange(unsigned UserOffset, unsigned TrialOffset, 176 unsigned Disp, bool NegativeOK, bool IsSoImm = false); 177 bool BBIsInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 178 bool FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br); 179 bool FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br); 180 bool FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br); 181 bool UndoLRSpillRestore(); 182 bool OptimizeThumb2JumpTables(MachineFunction &MF); 183 184 unsigned GetOffsetOf(MachineInstr *MI) const; 185 void dumpBBs(); 186 void verify(MachineFunction &MF); 187 }; 188 char ARMConstantIslands::ID = 0; 189} 190 191/// verify - check BBOffsets, BBSizes, alignment of islands 192void ARMConstantIslands::verify(MachineFunction &MF) { 193 assert(BBOffsets.size() == BBSizes.size()); 194 for (unsigned i = 1, e = BBOffsets.size(); i != e; ++i) 195 assert(BBOffsets[i-1]+BBSizes[i-1] == BBOffsets[i]); 196 if (!isThumb) 197 return; 198#ifndef NDEBUG 199 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 200 MBBI != E; ++MBBI) { 201 MachineBasicBlock *MBB = MBBI; 202 if (!MBB->empty() && 203 MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 204 unsigned MBBId = MBB->getNumber(); 205 assert((BBOffsets[MBBId]%4 == 0 && BBSizes[MBBId]%4 == 0) || 206 (BBOffsets[MBBId]%4 != 0 && BBSizes[MBBId]%4 != 0)); 207 } 208 } 209#endif 210} 211 212/// print block size and offset information - debugging 213void ARMConstantIslands::dumpBBs() { 214 for (unsigned J = 0, E = BBOffsets.size(); J !=E; ++J) { 215 DOUT << "block " << J << " offset " << BBOffsets[J] << 216 " size " << BBSizes[J] << "\n"; 217 } 218} 219 220/// createARMConstantIslandPass - returns an instance of the constpool 221/// island pass. 222FunctionPass *llvm::createARMConstantIslandPass() { 223 return new ARMConstantIslands(); 224} 225 226bool ARMConstantIslands::runOnMachineFunction(MachineFunction &MF) { 227 MachineConstantPool &MCP = *MF.getConstantPool(); 228 229 TII = MF.getTarget().getInstrInfo(); 230 AFI = MF.getInfo<ARMFunctionInfo>(); 231 STI = &MF.getTarget().getSubtarget<ARMSubtarget>(); 232 233 isThumb = AFI->isThumbFunction(); 234 isThumb1 = AFI->isThumb1OnlyFunction(); 235 isThumb2 = AFI->isThumb2Function(); 236 237 HasFarJump = false; 238 239 // Renumber all of the machine basic blocks in the function, guaranteeing that 240 // the numbers agree with the position of the block in the function. 241 MF.RenumberBlocks(); 242 243 // Thumb1 functions containing constant pools get 4-byte alignment. 244 // This is so we can keep exact track of where the alignment padding goes. 245 246 // Set default. Thumb1 function is 2-byte aligned, ARM and Thumb2 are 4-byte 247 // aligned. 248 AFI->setAlign(isThumb1 ? 1U : 2U); 249 250 // Perform the initial placement of the constant pool entries. To start with, 251 // we put them all at the end of the function. 252 std::vector<MachineInstr*> CPEMIs; 253 if (!MCP.isEmpty()) { 254 DoInitialPlacement(MF, CPEMIs); 255 if (isThumb1) 256 AFI->setAlign(2U); 257 } 258 259 /// The next UID to take is the first unused one. 260 AFI->initConstPoolEntryUId(CPEMIs.size()); 261 262 // Do the initial scan of the function, building up information about the 263 // sizes of each block, the location of all the water, and finding all of the 264 // constant pool users. 265 InitialFunctionScan(MF, CPEMIs); 266 CPEMIs.clear(); 267 268 /// Remove dead constant pool entries. 269 RemoveUnusedCPEntries(); 270 271 // Iteratively place constant pool entries and fix up branches until there 272 // is no change. 273 bool MadeChange = false; 274 unsigned NoCPIters = 0, NoBRIters = 0; 275 while (true) { 276 bool CPChange = false; 277 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 278 CPChange |= HandleConstantPoolUser(MF, i); 279 if (CPChange && ++NoCPIters > 30) 280 llvm_unreachable("Constant Island pass failed to converge!"); 281 DEBUG(dumpBBs()); 282 283 bool BRChange = false; 284 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 285 BRChange |= FixUpImmediateBr(MF, ImmBranches[i]); 286 if (BRChange && ++NoBRIters > 30) 287 llvm_unreachable("Branch Fix Up pass failed to converge!"); 288 DEBUG(dumpBBs()); 289 290 if (!CPChange && !BRChange) 291 break; 292 MadeChange = true; 293 } 294 295 // Let's see if we can use tbb / tbh to do jump tables. 296 MadeChange |= OptimizeThumb2JumpTables(MF); 297 298 // After a while, this might be made debug-only, but it is not expensive. 299 verify(MF); 300 301 // If LR has been forced spilled and no far jumps (i.e. BL) has been issued. 302 // Undo the spill / restore of LR if possible. 303 if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump()) 304 MadeChange |= UndoLRSpillRestore(); 305 306 BBSizes.clear(); 307 BBOffsets.clear(); 308 WaterList.clear(); 309 CPUsers.clear(); 310 CPEntries.clear(); 311 ImmBranches.clear(); 312 PushPopMIs.clear(); 313 T2JumpTables.clear(); 314 315 return MadeChange; 316} 317 318/// DoInitialPlacement - Perform the initial placement of the constant pool 319/// entries. To start with, we put them all at the end of the function. 320void ARMConstantIslands::DoInitialPlacement(MachineFunction &MF, 321 std::vector<MachineInstr*> &CPEMIs) { 322 // Create the basic block to hold the CPE's. 323 MachineBasicBlock *BB = MF.CreateMachineBasicBlock(); 324 MF.push_back(BB); 325 326 // Add all of the constants from the constant pool to the end block, use an 327 // identity mapping of CPI's to CPE's. 328 const std::vector<MachineConstantPoolEntry> &CPs = 329 MF.getConstantPool()->getConstants(); 330 331 const TargetData &TD = *MF.getTarget().getTargetData(); 332 for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 333 unsigned Size = TD.getTypeAllocSize(CPs[i].getType()); 334 // Verify that all constant pool entries are a multiple of 4 bytes. If not, 335 // we would have to pad them out or something so that instructions stay 336 // aligned. 337 assert((Size & 3) == 0 && "CP Entry not multiple of 4 bytes!"); 338 MachineInstr *CPEMI = 339 BuildMI(BB, DebugLoc::getUnknownLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) 340 .addImm(i).addConstantPoolIndex(i).addImm(Size); 341 CPEMIs.push_back(CPEMI); 342 343 // Add a new CPEntry, but no corresponding CPUser yet. 344 std::vector<CPEntry> CPEs; 345 CPEs.push_back(CPEntry(CPEMI, i)); 346 CPEntries.push_back(CPEs); 347 NumCPEs++; 348 DOUT << "Moved CPI#" << i << " to end of function as #" << i << "\n"; 349 } 350} 351 352/// BBHasFallthrough - Return true if the specified basic block can fallthrough 353/// into the block immediately after it. 354static bool BBHasFallthrough(MachineBasicBlock *MBB) { 355 // Get the next machine basic block in the function. 356 MachineFunction::iterator MBBI = MBB; 357 if (next(MBBI) == MBB->getParent()->end()) // Can't fall off end of function. 358 return false; 359 360 MachineBasicBlock *NextBB = next(MBBI); 361 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 362 E = MBB->succ_end(); I != E; ++I) 363 if (*I == NextBB) 364 return true; 365 366 return false; 367} 368 369/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 370/// look up the corresponding CPEntry. 371ARMConstantIslands::CPEntry 372*ARMConstantIslands::findConstPoolEntry(unsigned CPI, 373 const MachineInstr *CPEMI) { 374 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 375 // Number of entries per constpool index should be small, just do a 376 // linear search. 377 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 378 if (CPEs[i].CPEMI == CPEMI) 379 return &CPEs[i]; 380 } 381 return NULL; 382} 383 384/// InitialFunctionScan - Do the initial scan of the function, building up 385/// information about the sizes of each block, the location of all the water, 386/// and finding all of the constant pool users. 387void ARMConstantIslands::InitialFunctionScan(MachineFunction &MF, 388 const std::vector<MachineInstr*> &CPEMIs) { 389 unsigned Offset = 0; 390 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 391 MBBI != E; ++MBBI) { 392 MachineBasicBlock &MBB = *MBBI; 393 394 // If this block doesn't fall through into the next MBB, then this is 395 // 'water' that a constant pool island could be placed. 396 if (!BBHasFallthrough(&MBB)) 397 WaterList.push_back(&MBB); 398 399 unsigned MBBSize = 0; 400 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 401 I != E; ++I) { 402 // Add instruction size to MBBSize. 403 MBBSize += TII->GetInstSizeInBytes(I); 404 405 int Opc = I->getOpcode(); 406 if (I->getDesc().isBranch()) { 407 bool isCond = false; 408 unsigned Bits = 0; 409 unsigned Scale = 1; 410 int UOpc = Opc; 411 switch (Opc) { 412 default: 413 continue; // Ignore other JT branches 414 case ARM::tBR_JTr: 415 // A Thumb1 table jump may involve padding; for the offsets to 416 // be right, functions containing these must be 4-byte aligned. 417 AFI->setAlign(2U); 418 if ((Offset+MBBSize)%4 != 0) 419 // FIXME: Add a pseudo ALIGN instruction instead. 420 MBBSize += 2; // padding 421 continue; // Does not get an entry in ImmBranches 422 case ARM::t2BR_JT: 423 T2JumpTables.push_back(I); 424 continue; // Does not get an entry in ImmBranches 425 case ARM::Bcc: 426 isCond = true; 427 UOpc = ARM::B; 428 // Fallthrough 429 case ARM::B: 430 Bits = 24; 431 Scale = 4; 432 break; 433 case ARM::tBcc: 434 isCond = true; 435 UOpc = ARM::tB; 436 Bits = 8; 437 Scale = 2; 438 break; 439 case ARM::tB: 440 Bits = 11; 441 Scale = 2; 442 break; 443 case ARM::t2Bcc: 444 isCond = true; 445 UOpc = ARM::t2B; 446 Bits = 20; 447 Scale = 2; 448 break; 449 case ARM::t2B: 450 Bits = 24; 451 Scale = 2; 452 break; 453 } 454 455 // Record this immediate branch. 456 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 457 ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); 458 } 459 460 if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 461 PushPopMIs.push_back(I); 462 463 if (Opc == ARM::CONSTPOOL_ENTRY) 464 continue; 465 466 // Scan the instructions for constant pool operands. 467 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 468 if (I->getOperand(op).isCPI()) { 469 // We found one. The addressing mode tells us the max displacement 470 // from the PC that this instruction permits. 471 472 // Basic size info comes from the TSFlags field. 473 unsigned Bits = 0; 474 unsigned Scale = 1; 475 bool NegOk = false; 476 bool IsSoImm = false; 477 478 // FIXME: Temporary workaround until I can figure out what's going on. 479 unsigned Slack = T2JumpTables.empty() ? 0 : 4; 480 switch (Opc) { 481 default: 482 llvm_unreachable("Unknown addressing mode for CP reference!"); 483 break; 484 485 // Taking the address of a CP entry. 486 case ARM::LEApcrel: 487 // This takes a SoImm, which is 8 bit immediate rotated. We'll 488 // pretend the maximum offset is 255 * 4. Since each instruction 489 // 4 byte wide, this is always correct. We'llc heck for other 490 // displacements that fits in a SoImm as well. 491 Bits = 8; 492 Scale = 4; 493 NegOk = true; 494 IsSoImm = true; 495 break; 496 case ARM::t2LEApcrel: 497 Bits = 12; 498 NegOk = true; 499 break; 500 case ARM::tLEApcrel: 501 Bits = 8; 502 Scale = 4; 503 break; 504 505 case ARM::LDR: 506 case ARM::LDRcp: 507 case ARM::t2LDRpci: 508 Bits = 12; // +-offset_12 509 NegOk = true; 510 break; 511 512 case ARM::tLDRpci: 513 case ARM::tLDRcp: 514 Bits = 8; 515 Scale = 4; // +(offset_8*4) 516 break; 517 518 case ARM::FLDD: 519 case ARM::FLDS: 520 Bits = 8; 521 Scale = 4; // +-(offset_8*4) 522 NegOk = true; 523 break; 524 } 525 526 // Remember that this is a user of a CP entry. 527 unsigned CPI = I->getOperand(op).getIndex(); 528 MachineInstr *CPEMI = CPEMIs[CPI]; 529 unsigned MaxOffs = ((1 << Bits)-1) * Scale - Slack; 530 CPUsers.push_back(CPUser(I, CPEMI, MaxOffs, NegOk, IsSoImm)); 531 532 // Increment corresponding CPEntry reference count. 533 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 534 assert(CPE && "Cannot find a corresponding CPEntry!"); 535 CPE->RefCount++; 536 537 // Instructions can only use one CP entry, don't bother scanning the 538 // rest of the operands. 539 break; 540 } 541 } 542 543 // In thumb mode, if this block is a constpool island, we may need padding 544 // so it's aligned on 4 byte boundary. 545 if (isThumb && 546 !MBB.empty() && 547 MBB.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY && 548 (Offset%4) != 0) 549 MBBSize += 2; 550 551 BBSizes.push_back(MBBSize); 552 BBOffsets.push_back(Offset); 553 Offset += MBBSize; 554 } 555} 556 557/// GetOffsetOf - Return the current offset of the specified machine instruction 558/// from the start of the function. This offset changes as stuff is moved 559/// around inside the function. 560unsigned ARMConstantIslands::GetOffsetOf(MachineInstr *MI) const { 561 MachineBasicBlock *MBB = MI->getParent(); 562 563 // The offset is composed of two things: the sum of the sizes of all MBB's 564 // before this instruction's block, and the offset from the start of the block 565 // it is in. 566 unsigned Offset = BBOffsets[MBB->getNumber()]; 567 568 // If we're looking for a CONSTPOOL_ENTRY in Thumb, see if this block has 569 // alignment padding, and compensate if so. 570 if (isThumb && 571 MI->getOpcode() == ARM::CONSTPOOL_ENTRY && 572 Offset%4 != 0) 573 Offset += 2; 574 575 // Sum instructions before MI in MBB. 576 for (MachineBasicBlock::iterator I = MBB->begin(); ; ++I) { 577 assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 578 if (&*I == MI) return Offset; 579 Offset += TII->GetInstSizeInBytes(I); 580 } 581} 582 583/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 584/// ID. 585static bool CompareMBBNumbers(const MachineBasicBlock *LHS, 586 const MachineBasicBlock *RHS) { 587 return LHS->getNumber() < RHS->getNumber(); 588} 589 590/// UpdateForInsertedWaterBlock - When a block is newly inserted into the 591/// machine function, it upsets all of the block numbers. Renumber the blocks 592/// and update the arrays that parallel this numbering. 593void ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 594 // Renumber the MBB's to keep them consequtive. 595 NewBB->getParent()->RenumberBlocks(NewBB); 596 597 // Insert a size into BBSizes to align it properly with the (newly 598 // renumbered) block numbers. 599 BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 600 601 // Likewise for BBOffsets. 602 BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 603 604 // Next, update WaterList. Specifically, we need to add NewMBB as having 605 // available water after it. 606 std::vector<MachineBasicBlock*>::iterator IP = 607 std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 608 CompareMBBNumbers); 609 WaterList.insert(IP, NewBB); 610} 611 612 613/// Split the basic block containing MI into two blocks, which are joined by 614/// an unconditional branch. Update datastructures and renumber blocks to 615/// account for this change and returns the newly created block. 616MachineBasicBlock *ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr *MI) { 617 MachineBasicBlock *OrigBB = MI->getParent(); 618 MachineFunction &MF = *OrigBB->getParent(); 619 620 // Create a new MBB for the code after the OrigBB. 621 MachineBasicBlock *NewBB = 622 MF.CreateMachineBasicBlock(OrigBB->getBasicBlock()); 623 MachineFunction::iterator MBBI = OrigBB; ++MBBI; 624 MF.insert(MBBI, NewBB); 625 626 // Splice the instructions starting with MI over to NewBB. 627 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 628 629 // Add an unconditional branch from OrigBB to NewBB. 630 // Note the new unconditional branch is not being recorded. 631 // There doesn't seem to be meaningful DebugInfo available; this doesn't 632 // correspond to anything in the source. 633 unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B; 634 BuildMI(OrigBB, DebugLoc::getUnknownLoc(), TII->get(Opc)).addMBB(NewBB); 635 NumSplit++; 636 637 // Update the CFG. All succs of OrigBB are now succs of NewBB. 638 while (!OrigBB->succ_empty()) { 639 MachineBasicBlock *Succ = *OrigBB->succ_begin(); 640 OrigBB->removeSuccessor(Succ); 641 NewBB->addSuccessor(Succ); 642 643 // This pass should be run after register allocation, so there should be no 644 // PHI nodes to update. 645 assert((Succ->empty() || Succ->begin()->getOpcode() != TargetInstrInfo::PHI) 646 && "PHI nodes should be eliminated by now!"); 647 } 648 649 // OrigBB branches to NewBB. 650 OrigBB->addSuccessor(NewBB); 651 652 // Update internal data structures to account for the newly inserted MBB. 653 // This is almost the same as UpdateForInsertedWaterBlock, except that 654 // the Water goes after OrigBB, not NewBB. 655 MF.RenumberBlocks(NewBB); 656 657 // Insert a size into BBSizes to align it properly with the (newly 658 // renumbered) block numbers. 659 BBSizes.insert(BBSizes.begin()+NewBB->getNumber(), 0); 660 661 // Likewise for BBOffsets. 662 BBOffsets.insert(BBOffsets.begin()+NewBB->getNumber(), 0); 663 664 // Next, update WaterList. Specifically, we need to add OrigMBB as having 665 // available water after it (but not if it's already there, which happens 666 // when splitting before a conditional branch that is followed by an 667 // unconditional branch - in that case we want to insert NewBB). 668 std::vector<MachineBasicBlock*>::iterator IP = 669 std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 670 CompareMBBNumbers); 671 MachineBasicBlock* WaterBB = *IP; 672 if (WaterBB == OrigBB) 673 WaterList.insert(next(IP), NewBB); 674 else 675 WaterList.insert(IP, OrigBB); 676 677 // Figure out how large the first NewMBB is. (It cannot 678 // contain a constpool_entry or tablejump.) 679 unsigned NewBBSize = 0; 680 for (MachineBasicBlock::iterator I = NewBB->begin(), E = NewBB->end(); 681 I != E; ++I) 682 NewBBSize += TII->GetInstSizeInBytes(I); 683 684 unsigned OrigBBI = OrigBB->getNumber(); 685 unsigned NewBBI = NewBB->getNumber(); 686 // Set the size of NewBB in BBSizes. 687 BBSizes[NewBBI] = NewBBSize; 688 689 // We removed instructions from UserMBB, subtract that off from its size. 690 // Add 2 or 4 to the block to count the unconditional branch we added to it. 691 int delta = isThumb1 ? 2 : 4; 692 BBSizes[OrigBBI] -= NewBBSize - delta; 693 694 // ...and adjust BBOffsets for NewBB accordingly. 695 BBOffsets[NewBBI] = BBOffsets[OrigBBI] + BBSizes[OrigBBI]; 696 697 // All BBOffsets following these blocks must be modified. 698 AdjustBBOffsetsAfter(NewBB, delta); 699 700 return NewBB; 701} 702 703/// OffsetIsInRange - Checks whether UserOffset (the location of a constant pool 704/// reference) is within MaxDisp of TrialOffset (a proposed location of a 705/// constant pool entry). 706bool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset, 707 unsigned TrialOffset, unsigned MaxDisp, 708 bool NegativeOK, bool IsSoImm) { 709 // On Thumb offsets==2 mod 4 are rounded down by the hardware for 710 // purposes of the displacement computation; compensate for that here. 711 // Effectively, the valid range of displacements is 2 bytes smaller for such 712 // references. 713 if (isThumb && UserOffset%4 !=0) 714 UserOffset -= 2; 715 // CPEs will be rounded up to a multiple of 4. 716 if (isThumb && TrialOffset%4 != 0) 717 TrialOffset += 2; 718 719 if (UserOffset <= TrialOffset) { 720 // User before the Trial. 721 if (TrialOffset - UserOffset <= MaxDisp) 722 return true; 723 // FIXME: Make use full range of soimm values. 724 } else if (NegativeOK) { 725 if (UserOffset - TrialOffset <= MaxDisp) 726 return true; 727 // FIXME: Make use full range of soimm values. 728 } 729 return false; 730} 731 732/// WaterIsInRange - Returns true if a CPE placed after the specified 733/// Water (a basic block) will be in range for the specific MI. 734 735bool ARMConstantIslands::WaterIsInRange(unsigned UserOffset, 736 MachineBasicBlock* Water, CPUser &U) { 737 unsigned MaxDisp = U.MaxDisp; 738 unsigned CPEOffset = BBOffsets[Water->getNumber()] + 739 BBSizes[Water->getNumber()]; 740 741 // If the CPE is to be inserted before the instruction, that will raise 742 // the offset of the instruction. (Currently applies only to ARM, so 743 // no alignment compensation attempted here.) 744 if (CPEOffset < UserOffset) 745 UserOffset += U.CPEMI->getOperand(2).getImm(); 746 747 return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, U.NegOk, U.IsSoImm); 748} 749 750/// CPEIsInRange - Returns true if the distance between specific MI and 751/// specific ConstPool entry instruction can fit in MI's displacement field. 752bool ARMConstantIslands::CPEIsInRange(MachineInstr *MI, unsigned UserOffset, 753 MachineInstr *CPEMI, unsigned MaxDisp, 754 bool NegOk, bool DoDump) { 755 unsigned CPEOffset = GetOffsetOf(CPEMI); 756 assert(CPEOffset%4 == 0 && "Misaligned CPE"); 757 758 if (DoDump) { 759 DOUT << "User of CPE#" << CPEMI->getOperand(0).getImm() 760 << " max delta=" << MaxDisp 761 << " insn address=" << UserOffset 762 << " CPE address=" << CPEOffset 763 << " offset=" << int(CPEOffset-UserOffset) << "\t" << *MI; 764 } 765 766 return OffsetIsInRange(UserOffset, CPEOffset, MaxDisp, NegOk); 767} 768 769#ifndef NDEBUG 770/// BBIsJumpedOver - Return true of the specified basic block's only predecessor 771/// unconditionally branches to its only successor. 772static bool BBIsJumpedOver(MachineBasicBlock *MBB) { 773 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 774 return false; 775 776 MachineBasicBlock *Succ = *MBB->succ_begin(); 777 MachineBasicBlock *Pred = *MBB->pred_begin(); 778 MachineInstr *PredMI = &Pred->back(); 779 if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB 780 || PredMI->getOpcode() == ARM::t2B) 781 return PredMI->getOperand(0).getMBB() == Succ; 782 return false; 783} 784#endif // NDEBUG 785 786void ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock *BB, 787 int delta) { 788 MachineFunction::iterator MBBI = BB; MBBI = next(MBBI); 789 for(unsigned i = BB->getNumber()+1, e = BB->getParent()->getNumBlockIDs(); 790 i < e; ++i) { 791 BBOffsets[i] += delta; 792 // If some existing blocks have padding, adjust the padding as needed, a 793 // bit tricky. delta can be negative so don't use % on that. 794 if (!isThumb) 795 continue; 796 MachineBasicBlock *MBB = MBBI; 797 if (!MBB->empty()) { 798 // Constant pool entries require padding. 799 if (MBB->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY) { 800 unsigned OldOffset = BBOffsets[i] - delta; 801 if ((OldOffset%4) == 0 && (BBOffsets[i]%4) != 0) { 802 // add new padding 803 BBSizes[i] += 2; 804 delta += 2; 805 } else if ((OldOffset%4) != 0 && (BBOffsets[i]%4) == 0) { 806 // remove existing padding 807 BBSizes[i] -= 2; 808 delta -= 2; 809 } 810 } 811 // Thumb1 jump tables require padding. They should be at the end; 812 // following unconditional branches are removed by AnalyzeBranch. 813 MachineInstr *ThumbJTMI = prior(MBB->end()); 814 if (ThumbJTMI->getOpcode() == ARM::tBR_JTr) { 815 unsigned NewMIOffset = GetOffsetOf(ThumbJTMI); 816 unsigned OldMIOffset = NewMIOffset - delta; 817 if ((OldMIOffset%4) == 0 && (NewMIOffset%4) != 0) { 818 // remove existing padding 819 BBSizes[i] -= 2; 820 delta -= 2; 821 } else if ((OldMIOffset%4) != 0 && (NewMIOffset%4) == 0) { 822 // add new padding 823 BBSizes[i] += 2; 824 delta += 2; 825 } 826 } 827 if (delta==0) 828 return; 829 } 830 MBBI = next(MBBI); 831 } 832} 833 834/// DecrementOldEntry - find the constant pool entry with index CPI 835/// and instruction CPEMI, and decrement its refcount. If the refcount 836/// becomes 0 remove the entry and instruction. Returns true if we removed 837/// the entry, false if we didn't. 838 839bool ARMConstantIslands::DecrementOldEntry(unsigned CPI, MachineInstr *CPEMI) { 840 // Find the old entry. Eliminate it if it is no longer used. 841 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 842 assert(CPE && "Unexpected!"); 843 if (--CPE->RefCount == 0) { 844 RemoveDeadCPEMI(CPEMI); 845 CPE->CPEMI = NULL; 846 NumCPEs--; 847 return true; 848 } 849 return false; 850} 851 852/// LookForCPEntryInRange - see if the currently referenced CPE is in range; 853/// if not, see if an in-range clone of the CPE is in range, and if so, 854/// change the data structures so the user references the clone. Returns: 855/// 0 = no existing entry found 856/// 1 = entry found, and there were no code insertions or deletions 857/// 2 = entry found, and there were code insertions or deletions 858int ARMConstantIslands::LookForExistingCPEntry(CPUser& U, unsigned UserOffset) 859{ 860 MachineInstr *UserMI = U.MI; 861 MachineInstr *CPEMI = U.CPEMI; 862 863 // Check to see if the CPE is already in-range. 864 if (CPEIsInRange(UserMI, UserOffset, CPEMI, U.MaxDisp, U.NegOk, true)) { 865 DOUT << "In range\n"; 866 return 1; 867 } 868 869 // No. Look for previously created clones of the CPE that are in range. 870 unsigned CPI = CPEMI->getOperand(1).getIndex(); 871 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 872 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 873 // We already tried this one 874 if (CPEs[i].CPEMI == CPEMI) 875 continue; 876 // Removing CPEs can leave empty entries, skip 877 if (CPEs[i].CPEMI == NULL) 878 continue; 879 if (CPEIsInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.MaxDisp, U.NegOk)) { 880 DOUT << "Replacing CPE#" << CPI << " with CPE#" << CPEs[i].CPI << "\n"; 881 // Point the CPUser node to the replacement 882 U.CPEMI = CPEs[i].CPEMI; 883 // Change the CPI in the instruction operand to refer to the clone. 884 for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 885 if (UserMI->getOperand(j).isCPI()) { 886 UserMI->getOperand(j).setIndex(CPEs[i].CPI); 887 break; 888 } 889 // Adjust the refcount of the clone... 890 CPEs[i].RefCount++; 891 // ...and the original. If we didn't remove the old entry, none of the 892 // addresses changed, so we don't need another pass. 893 return DecrementOldEntry(CPI, CPEMI) ? 2 : 1; 894 } 895 } 896 return 0; 897} 898 899/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 900/// the specific unconditional branch instruction. 901static inline unsigned getUnconditionalBrDisp(int Opc) { 902 switch (Opc) { 903 case ARM::tB: 904 return ((1<<10)-1)*2; 905 case ARM::t2B: 906 return ((1<<23)-1)*2; 907 default: 908 break; 909 } 910 911 return ((1<<23)-1)*4; 912} 913 914/// AcceptWater - Small amount of common code factored out of the following. 915 916MachineBasicBlock* ARMConstantIslands::AcceptWater(MachineBasicBlock *WaterBB, 917 std::vector<MachineBasicBlock*>::iterator IP) { 918 DOUT << "found water in range\n"; 919 // Remove the original WaterList entry; we want subsequent 920 // insertions in this vicinity to go after the one we're 921 // about to insert. This considerably reduces the number 922 // of times we have to move the same CPE more than once. 923 WaterList.erase(IP); 924 // CPE goes before following block (NewMBB). 925 return next(MachineFunction::iterator(WaterBB)); 926} 927 928/// LookForWater - look for an existing entry in the WaterList in which 929/// we can place the CPE referenced from U so it's within range of U's MI. 930/// Returns true if found, false if not. If it returns true, *NewMBB 931/// is set to the WaterList entry. 932/// For ARM, we prefer the water that's farthest away. For Thumb, prefer 933/// water that will not introduce padding to water that will; within each 934/// group, prefer the water that's farthest away. 935bool ARMConstantIslands::LookForWater(CPUser &U, unsigned UserOffset, 936 MachineBasicBlock** NewMBB) { 937 std::vector<MachineBasicBlock*>::iterator IPThatWouldPad; 938 MachineBasicBlock* WaterBBThatWouldPad = NULL; 939 if (!WaterList.empty()) { 940 for (std::vector<MachineBasicBlock*>::iterator IP = prior(WaterList.end()), 941 B = WaterList.begin();; --IP) { 942 MachineBasicBlock* WaterBB = *IP; 943 if (WaterIsInRange(UserOffset, WaterBB, U)) { 944 unsigned WBBId = WaterBB->getNumber(); 945 if (isThumb && 946 (BBOffsets[WBBId] + BBSizes[WBBId])%4 != 0) { 947 // This is valid Water, but would introduce padding. Remember 948 // it in case we don't find any Water that doesn't do this. 949 if (!WaterBBThatWouldPad) { 950 WaterBBThatWouldPad = WaterBB; 951 IPThatWouldPad = IP; 952 } 953 } else { 954 *NewMBB = AcceptWater(WaterBB, IP); 955 return true; 956 } 957 } 958 if (IP == B) 959 break; 960 } 961 } 962 if (isThumb && WaterBBThatWouldPad) { 963 *NewMBB = AcceptWater(WaterBBThatWouldPad, IPThatWouldPad); 964 return true; 965 } 966 return false; 967} 968 969/// CreateNewWater - No existing WaterList entry will work for 970/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 971/// block is used if in range, and the conditional branch munged so control 972/// flow is correct. Otherwise the block is split to create a hole with an 973/// unconditional branch around it. In either case *NewMBB is set to a 974/// block following which the new island can be inserted (the WaterList 975/// is not adjusted). 976 977void ARMConstantIslands::CreateNewWater(unsigned CPUserIndex, 978 unsigned UserOffset, MachineBasicBlock** NewMBB) { 979 CPUser &U = CPUsers[CPUserIndex]; 980 MachineInstr *UserMI = U.MI; 981 MachineInstr *CPEMI = U.CPEMI; 982 MachineBasicBlock *UserMBB = UserMI->getParent(); 983 unsigned OffsetOfNextBlock = BBOffsets[UserMBB->getNumber()] + 984 BBSizes[UserMBB->getNumber()]; 985 assert(OffsetOfNextBlock== BBOffsets[UserMBB->getNumber()+1]); 986 987 // If the use is at the end of the block, or the end of the block 988 // is within range, make new water there. (The addition below is 989 // for the unconditional branch we will be adding: 4 bytes on ARM + Thumb2, 990 // 2 on Thumb1. Possible Thumb1 alignment padding is allowed for 991 // inside OffsetIsInRange. 992 // If the block ends in an unconditional branch already, it is water, 993 // and is known to be out of range, so we'll always be adding a branch.) 994 if (&UserMBB->back() == UserMI || 995 OffsetIsInRange(UserOffset, OffsetOfNextBlock + (isThumb1 ? 2: 4), 996 U.MaxDisp, U.NegOk, U.IsSoImm)) { 997 DOUT << "Split at end of block\n"; 998 if (&UserMBB->back() == UserMI) 999 assert(BBHasFallthrough(UserMBB) && "Expected a fallthrough BB!"); 1000 *NewMBB = next(MachineFunction::iterator(UserMBB)); 1001 // Add an unconditional branch from UserMBB to fallthrough block. 1002 // Record it for branch lengthening; this new branch will not get out of 1003 // range, but if the preceding conditional branch is out of range, the 1004 // targets will be exchanged, and the altered branch may be out of 1005 // range, so the machinery has to know about it. 1006 int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B; 1007 BuildMI(UserMBB, DebugLoc::getUnknownLoc(), 1008 TII->get(UncondBr)).addMBB(*NewMBB); 1009 unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 1010 ImmBranches.push_back(ImmBranch(&UserMBB->back(), 1011 MaxDisp, false, UncondBr)); 1012 int delta = isThumb1 ? 2 : 4; 1013 BBSizes[UserMBB->getNumber()] += delta; 1014 AdjustBBOffsetsAfter(UserMBB, delta); 1015 } else { 1016 // What a big block. Find a place within the block to split it. 1017 // This is a little tricky on Thumb1 since instructions are 2 bytes 1018 // and constant pool entries are 4 bytes: if instruction I references 1019 // island CPE, and instruction I+1 references CPE', it will 1020 // not work well to put CPE as far forward as possible, since then 1021 // CPE' cannot immediately follow it (that location is 2 bytes 1022 // farther away from I+1 than CPE was from I) and we'd need to create 1023 // a new island. So, we make a first guess, then walk through the 1024 // instructions between the one currently being looked at and the 1025 // possible insertion point, and make sure any other instructions 1026 // that reference CPEs will be able to use the same island area; 1027 // if not, we back up the insertion point. 1028 1029 // The 4 in the following is for the unconditional branch we'll be 1030 // inserting (allows for long branch on Thumb1). Alignment of the 1031 // island is handled inside OffsetIsInRange. 1032 unsigned BaseInsertOffset = UserOffset + U.MaxDisp -4; 1033 // This could point off the end of the block if we've already got 1034 // constant pool entries following this block; only the last one is 1035 // in the water list. Back past any possible branches (allow for a 1036 // conditional and a maximally long unconditional). 1037 if (BaseInsertOffset >= BBOffsets[UserMBB->getNumber()+1]) 1038 BaseInsertOffset = BBOffsets[UserMBB->getNumber()+1] - 1039 (isThumb1 ? 6 : 8); 1040 unsigned EndInsertOffset = BaseInsertOffset + 1041 CPEMI->getOperand(2).getImm(); 1042 MachineBasicBlock::iterator MI = UserMI; 1043 ++MI; 1044 unsigned CPUIndex = CPUserIndex+1; 1045 for (unsigned Offset = UserOffset+TII->GetInstSizeInBytes(UserMI); 1046 Offset < BaseInsertOffset; 1047 Offset += TII->GetInstSizeInBytes(MI), 1048 MI = next(MI)) { 1049 if (CPUIndex < CPUsers.size() && CPUsers[CPUIndex].MI == MI) { 1050 CPUser &U = CPUsers[CPUIndex]; 1051 if (!OffsetIsInRange(Offset, EndInsertOffset, 1052 U.MaxDisp, U.NegOk, U.IsSoImm)) { 1053 BaseInsertOffset -= (isThumb1 ? 2 : 4); 1054 EndInsertOffset -= (isThumb1 ? 2 : 4); 1055 } 1056 // This is overly conservative, as we don't account for CPEMIs 1057 // being reused within the block, but it doesn't matter much. 1058 EndInsertOffset += CPUsers[CPUIndex].CPEMI->getOperand(2).getImm(); 1059 CPUIndex++; 1060 } 1061 } 1062 DOUT << "Split in middle of big block\n"; 1063 *NewMBB = SplitBlockBeforeInstr(prior(MI)); 1064 } 1065} 1066 1067/// HandleConstantPoolUser - Analyze the specified user, checking to see if it 1068/// is out-of-range. If so, pick up the constant pool value and move it some 1069/// place in-range. Return true if we changed any addresses (thus must run 1070/// another pass of branch lengthening), false otherwise. 1071bool ARMConstantIslands::HandleConstantPoolUser(MachineFunction &MF, 1072 unsigned CPUserIndex) { 1073 CPUser &U = CPUsers[CPUserIndex]; 1074 MachineInstr *UserMI = U.MI; 1075 MachineInstr *CPEMI = U.CPEMI; 1076 unsigned CPI = CPEMI->getOperand(1).getIndex(); 1077 unsigned Size = CPEMI->getOperand(2).getImm(); 1078 MachineBasicBlock *NewMBB; 1079 // Compute this only once, it's expensive. The 4 or 8 is the value the 1080 // hardware keeps in the PC (2 insns ahead of the reference). 1081 unsigned UserOffset = GetOffsetOf(UserMI) + (isThumb ? 4 : 8); 1082 1083 // See if the current entry is within range, or there is a clone of it 1084 // in range. 1085 int result = LookForExistingCPEntry(U, UserOffset); 1086 if (result==1) return false; 1087 else if (result==2) return true; 1088 1089 // No existing clone of this CPE is within range. 1090 // We will be generating a new clone. Get a UID for it. 1091 unsigned ID = AFI->createConstPoolEntryUId(); 1092 1093 // Look for water where we can place this CPE. We look for the farthest one 1094 // away that will work. Forward references only for now (although later 1095 // we might find some that are backwards). 1096 1097 if (!LookForWater(U, UserOffset, &NewMBB)) { 1098 // No water found. 1099 DOUT << "No water found\n"; 1100 CreateNewWater(CPUserIndex, UserOffset, &NewMBB); 1101 } 1102 1103 // Okay, we know we can put an island before NewMBB now, do it! 1104 MachineBasicBlock *NewIsland = MF.CreateMachineBasicBlock(); 1105 MF.insert(NewMBB, NewIsland); 1106 1107 // Update internal data structures to account for the newly inserted MBB. 1108 UpdateForInsertedWaterBlock(NewIsland); 1109 1110 // Decrement the old entry, and remove it if refcount becomes 0. 1111 DecrementOldEntry(CPI, CPEMI); 1112 1113 // Now that we have an island to add the CPE to, clone the original CPE and 1114 // add it to the island. 1115 U.CPEMI = BuildMI(NewIsland, DebugLoc::getUnknownLoc(), 1116 TII->get(ARM::CONSTPOOL_ENTRY)) 1117 .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 1118 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 1119 NumCPEs++; 1120 1121 BBOffsets[NewIsland->getNumber()] = BBOffsets[NewMBB->getNumber()]; 1122 // Compensate for .align 2 in thumb mode. 1123 if (isThumb && BBOffsets[NewIsland->getNumber()]%4 != 0) 1124 Size += 2; 1125 // Increase the size of the island block to account for the new entry. 1126 BBSizes[NewIsland->getNumber()] += Size; 1127 AdjustBBOffsetsAfter(NewIsland, Size); 1128 1129 // Finally, change the CPI in the instruction operand to be ID. 1130 for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 1131 if (UserMI->getOperand(i).isCPI()) { 1132 UserMI->getOperand(i).setIndex(ID); 1133 break; 1134 } 1135 1136 DOUT << " Moved CPE to #" << ID << " CPI=" << CPI << "\t" << *UserMI; 1137 1138 return true; 1139} 1140 1141/// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update 1142/// sizes and offsets of impacted basic blocks. 1143void ARMConstantIslands::RemoveDeadCPEMI(MachineInstr *CPEMI) { 1144 MachineBasicBlock *CPEBB = CPEMI->getParent(); 1145 unsigned Size = CPEMI->getOperand(2).getImm(); 1146 CPEMI->eraseFromParent(); 1147 BBSizes[CPEBB->getNumber()] -= Size; 1148 // All succeeding offsets have the current size value added in, fix this. 1149 if (CPEBB->empty()) { 1150 // In thumb1 mode, the size of island may be padded by two to compensate for 1151 // the alignment requirement. Then it will now be 2 when the block is 1152 // empty, so fix this. 1153 // All succeeding offsets have the current size value added in, fix this. 1154 if (BBSizes[CPEBB->getNumber()] != 0) { 1155 Size += BBSizes[CPEBB->getNumber()]; 1156 BBSizes[CPEBB->getNumber()] = 0; 1157 } 1158 } 1159 AdjustBBOffsetsAfter(CPEBB, -Size); 1160 // An island has only one predecessor BB and one successor BB. Check if 1161 // this BB's predecessor jumps directly to this BB's successor. This 1162 // shouldn't happen currently. 1163 assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 1164 // FIXME: remove the empty blocks after all the work is done? 1165} 1166 1167/// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts 1168/// are zero. 1169bool ARMConstantIslands::RemoveUnusedCPEntries() { 1170 unsigned MadeChange = false; 1171 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 1172 std::vector<CPEntry> &CPEs = CPEntries[i]; 1173 for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 1174 if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 1175 RemoveDeadCPEMI(CPEs[j].CPEMI); 1176 CPEs[j].CPEMI = NULL; 1177 MadeChange = true; 1178 } 1179 } 1180 } 1181 return MadeChange; 1182} 1183 1184/// BBIsInRange - Returns true if the distance between specific MI and 1185/// specific BB can fit in MI's displacement field. 1186bool ARMConstantIslands::BBIsInRange(MachineInstr *MI,MachineBasicBlock *DestBB, 1187 unsigned MaxDisp) { 1188 unsigned PCAdj = isThumb ? 4 : 8; 1189 unsigned BrOffset = GetOffsetOf(MI) + PCAdj; 1190 unsigned DestOffset = BBOffsets[DestBB->getNumber()]; 1191 1192 DOUT << "Branch of destination BB#" << DestBB->getNumber() 1193 << " from BB#" << MI->getParent()->getNumber() 1194 << " max delta=" << MaxDisp 1195 << " from " << GetOffsetOf(MI) << " to " << DestOffset 1196 << " offset " << int(DestOffset-BrOffset) << "\t" << *MI; 1197 1198 if (BrOffset <= DestOffset) { 1199 // Branch before the Dest. 1200 if (DestOffset-BrOffset <= MaxDisp) 1201 return true; 1202 } else { 1203 if (BrOffset-DestOffset <= MaxDisp) 1204 return true; 1205 } 1206 return false; 1207} 1208 1209/// FixUpImmediateBr - Fix up an immediate branch whose destination is too far 1210/// away to fit in its displacement field. 1211bool ARMConstantIslands::FixUpImmediateBr(MachineFunction &MF, ImmBranch &Br) { 1212 MachineInstr *MI = Br.MI; 1213 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1214 1215 // Check to see if the DestBB is already in-range. 1216 if (BBIsInRange(MI, DestBB, Br.MaxDisp)) 1217 return false; 1218 1219 if (!Br.isCond) 1220 return FixUpUnconditionalBr(MF, Br); 1221 return FixUpConditionalBr(MF, Br); 1222} 1223 1224/// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is 1225/// too far away to fit in its displacement field. If the LR register has been 1226/// spilled in the epilogue, then we can use BL to implement a far jump. 1227/// Otherwise, add an intermediate branch instruction to a branch. 1228bool 1229ARMConstantIslands::FixUpUnconditionalBr(MachineFunction &MF, ImmBranch &Br) { 1230 MachineInstr *MI = Br.MI; 1231 MachineBasicBlock *MBB = MI->getParent(); 1232 if (!isThumb1) 1233 llvm_unreachable("FixUpUnconditionalBr is Thumb1 only!"); 1234 1235 // Use BL to implement far jump. 1236 Br.MaxDisp = (1 << 21) * 2; 1237 MI->setDesc(TII->get(ARM::tBfar)); 1238 BBSizes[MBB->getNumber()] += 2; 1239 AdjustBBOffsetsAfter(MBB, 2); 1240 HasFarJump = true; 1241 NumUBrFixed++; 1242 1243 DOUT << " Changed B to long jump " << *MI; 1244 1245 return true; 1246} 1247 1248/// FixUpConditionalBr - Fix up a conditional branch whose destination is too 1249/// far away to fit in its displacement field. It is converted to an inverse 1250/// conditional branch + an unconditional branch to the destination. 1251bool 1252ARMConstantIslands::FixUpConditionalBr(MachineFunction &MF, ImmBranch &Br) { 1253 MachineInstr *MI = Br.MI; 1254 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1255 1256 // Add an unconditional branch to the destination and invert the branch 1257 // condition to jump over it: 1258 // blt L1 1259 // => 1260 // bge L2 1261 // b L1 1262 // L2: 1263 ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm(); 1264 CC = ARMCC::getOppositeCondition(CC); 1265 unsigned CCReg = MI->getOperand(2).getReg(); 1266 1267 // If the branch is at the end of its MBB and that has a fall-through block, 1268 // direct the updated conditional branch to the fall-through block. Otherwise, 1269 // split the MBB before the next instruction. 1270 MachineBasicBlock *MBB = MI->getParent(); 1271 MachineInstr *BMI = &MBB->back(); 1272 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 1273 1274 NumCBrFixed++; 1275 if (BMI != MI) { 1276 if (next(MachineBasicBlock::iterator(MI)) == prior(MBB->end()) && 1277 BMI->getOpcode() == Br.UncondBr) { 1278 // Last MI in the BB is an unconditional branch. Can we simply invert the 1279 // condition and swap destinations: 1280 // beq L1 1281 // b L2 1282 // => 1283 // bne L2 1284 // b L1 1285 MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); 1286 if (BBIsInRange(MI, NewDest, Br.MaxDisp)) { 1287 DOUT << " Invert Bcc condition and swap its destination with " << *BMI; 1288 BMI->getOperand(0).setMBB(DestBB); 1289 MI->getOperand(0).setMBB(NewDest); 1290 MI->getOperand(1).setImm(CC); 1291 return true; 1292 } 1293 } 1294 } 1295 1296 if (NeedSplit) { 1297 SplitBlockBeforeInstr(MI); 1298 // No need for the branch to the next block. We're adding an unconditional 1299 // branch to the destination. 1300 int delta = TII->GetInstSizeInBytes(&MBB->back()); 1301 BBSizes[MBB->getNumber()] -= delta; 1302 MachineBasicBlock* SplitBB = next(MachineFunction::iterator(MBB)); 1303 AdjustBBOffsetsAfter(SplitBB, -delta); 1304 MBB->back().eraseFromParent(); 1305 // BBOffsets[SplitBB] is wrong temporarily, fixed below 1306 } 1307 MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 1308 1309 DOUT << " Insert B to BB#" << DestBB->getNumber() 1310 << " also invert condition and change dest. to BB#" 1311 << NextBB->getNumber() << "\n"; 1312 1313 // Insert a new conditional branch and a new unconditional branch. 1314 // Also update the ImmBranch as well as adding a new entry for the new branch. 1315 BuildMI(MBB, DebugLoc::getUnknownLoc(), 1316 TII->get(MI->getOpcode())) 1317 .addMBB(NextBB).addImm(CC).addReg(CCReg); 1318 Br.MI = &MBB->back(); 1319 BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 1320 BuildMI(MBB, DebugLoc::getUnknownLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); 1321 BBSizes[MBB->getNumber()] += TII->GetInstSizeInBytes(&MBB->back()); 1322 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1323 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 1324 1325 // Remove the old conditional branch. It may or may not still be in MBB. 1326 BBSizes[MI->getParent()->getNumber()] -= TII->GetInstSizeInBytes(MI); 1327 MI->eraseFromParent(); 1328 1329 // The net size change is an addition of one unconditional branch. 1330 int delta = TII->GetInstSizeInBytes(&MBB->back()); 1331 AdjustBBOffsetsAfter(MBB, delta); 1332 return true; 1333} 1334 1335/// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills 1336/// LR / restores LR to pc. 1337bool ARMConstantIslands::UndoLRSpillRestore() { 1338 bool MadeChange = false; 1339 for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) { 1340 MachineInstr *MI = PushPopMIs[i]; 1341 if (MI->getOpcode() == ARM::tPOP_RET && 1342 MI->getOperand(0).getReg() == ARM::PC && 1343 MI->getNumExplicitOperands() == 1) { 1344 BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET)); 1345 MI->eraseFromParent(); 1346 MadeChange = true; 1347 } 1348 } 1349 return MadeChange; 1350} 1351 1352bool ARMConstantIslands::OptimizeThumb2JumpTables(MachineFunction &MF) { 1353 bool MadeChange = false; 1354 1355 // FIXME: After the tables are shrunk, can we get rid some of the 1356 // constantpool tables? 1357 const MachineJumpTableInfo *MJTI = MF.getJumpTableInfo(); 1358 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); 1359 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { 1360 MachineInstr *MI = T2JumpTables[i]; 1361 const TargetInstrDesc &TID = MI->getDesc(); 1362 unsigned NumOps = TID.getNumOperands(); 1363 unsigned JTOpIdx = NumOps - (TID.isPredicable() ? 3 : 2); 1364 MachineOperand JTOP = MI->getOperand(JTOpIdx); 1365 unsigned JTI = JTOP.getIndex(); 1366 assert(JTI < JT.size()); 1367 1368 bool ByteOk = true; 1369 bool HalfWordOk = true; 1370 unsigned JTOffset = GetOffsetOf(MI) + 4; 1371 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; 1372 for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) { 1373 MachineBasicBlock *MBB = JTBBs[j]; 1374 unsigned DstOffset = BBOffsets[MBB->getNumber()]; 1375 // Negative offset is not ok. FIXME: We should change BB layout to make 1376 // sure all the branches are forward. 1377 if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2) 1378 ByteOk = false; 1379 unsigned TBHLimit = ((1<<16)-1)*2; 1380 if (STI->isTargetDarwin()) 1381 TBHLimit >>= 1; // FIXME: Work around an assembler bug. 1382 if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit) 1383 HalfWordOk = false; 1384 if (!ByteOk && !HalfWordOk) 1385 break; 1386 } 1387 1388 if (ByteOk || HalfWordOk) { 1389 MachineBasicBlock *MBB = MI->getParent(); 1390 unsigned BaseReg = MI->getOperand(0).getReg(); 1391 bool BaseRegKill = MI->getOperand(0).isKill(); 1392 if (!BaseRegKill) 1393 continue; 1394 unsigned IdxReg = MI->getOperand(1).getReg(); 1395 bool IdxRegKill = MI->getOperand(1).isKill(); 1396 MachineBasicBlock::iterator PrevI = MI; 1397 if (PrevI == MBB->begin()) 1398 continue; 1399 1400 MachineInstr *AddrMI = --PrevI; 1401 bool OptOk = true; 1402 // Examine the instruction that calculate the jumptable entry address. 1403 // If it's not the one just before the t2BR_JT, we won't delete it, then 1404 // it's not worth doing the optimization. 1405 for (unsigned k = 0, eee = AddrMI->getNumOperands(); k != eee; ++k) { 1406 const MachineOperand &MO = AddrMI->getOperand(k); 1407 if (!MO.isReg() || !MO.getReg()) 1408 continue; 1409 if (MO.isDef() && MO.getReg() != BaseReg) { 1410 OptOk = false; 1411 break; 1412 } 1413 if (MO.isUse() && !MO.isKill() && MO.getReg() != IdxReg) { 1414 OptOk = false; 1415 break; 1416 } 1417 } 1418 if (!OptOk) 1419 continue; 1420 1421 // The previous instruction should be a t2LEApcrelJT, we want to delete 1422 // it as well. 1423 MachineInstr *LeaMI = --PrevI; 1424 if (LeaMI->getOpcode() != ARM::t2LEApcrelJT || 1425 LeaMI->getOperand(0).getReg() != BaseReg) 1426 OptOk = false; 1427 1428 if (!OptOk) 1429 continue; 1430 1431 unsigned Opc = ByteOk ? ARM::t2TBB : ARM::t2TBH; 1432 MachineInstr *NewJTMI = BuildMI(MBB, MI->getDebugLoc(), TII->get(Opc)) 1433 .addReg(IdxReg, getKillRegState(IdxRegKill)) 1434 .addJumpTableIndex(JTI, JTOP.getTargetFlags()) 1435 .addImm(MI->getOperand(JTOpIdx+1).getImm()); 1436 // FIXME: Insert an "ALIGN" instruction to ensure the next instruction 1437 // is 2-byte aligned. For now, asm printer will fix it up. 1438 unsigned NewSize = TII->GetInstSizeInBytes(NewJTMI); 1439 unsigned OrigSize = TII->GetInstSizeInBytes(AddrMI); 1440 OrigSize += TII->GetInstSizeInBytes(LeaMI); 1441 OrigSize += TII->GetInstSizeInBytes(MI); 1442 1443 AddrMI->eraseFromParent(); 1444 LeaMI->eraseFromParent(); 1445 MI->eraseFromParent(); 1446 1447 int delta = OrigSize - NewSize; 1448 BBSizes[MBB->getNumber()] -= delta; 1449 AdjustBBOffsetsAfter(MBB, -delta); 1450 1451 ++NumTBs; 1452 MadeChange = true; 1453 } 1454 } 1455 1456 return MadeChange; 1457} 1458