1 //===- ARMConstantIslandPass.cpp - ARM constant islands -------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains a pass that splits the constant pool up into 'islands' 10 // which are scattered through-out the function. This is required due to the 11 // limited pc-relative displacements that ARM has. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "ARM.h" 16 #include "ARMBaseInstrInfo.h" 17 #include "ARMBasicBlockInfo.h" 18 #include "ARMMachineFunctionInfo.h" 19 #include "ARMSubtarget.h" 20 #include "MCTargetDesc/ARMBaseInfo.h" 21 #include "MVETailPredUtils.h" 22 #include "Thumb2InstrInfo.h" 23 #include "Utils/ARMBaseInfo.h" 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/STLExtras.h" 26 #include "llvm/ADT/SmallSet.h" 27 #include "llvm/ADT/SmallVector.h" 28 #include "llvm/ADT/Statistic.h" 29 #include "llvm/ADT/StringRef.h" 30 #include "llvm/CodeGen/LivePhysRegs.h" 31 #include "llvm/CodeGen/MachineBasicBlock.h" 32 #include "llvm/CodeGen/MachineConstantPool.h" 33 #include "llvm/CodeGen/MachineDominators.h" 34 #include "llvm/CodeGen/MachineFunction.h" 35 #include "llvm/CodeGen/MachineFunctionPass.h" 36 #include "llvm/CodeGen/MachineInstr.h" 37 #include "llvm/CodeGen/MachineJumpTableInfo.h" 38 #include "llvm/CodeGen/MachineOperand.h" 39 #include "llvm/CodeGen/MachineRegisterInfo.h" 40 #include "llvm/Config/llvm-config.h" 41 #include "llvm/IR/DataLayout.h" 42 #include "llvm/IR/DebugLoc.h" 43 #include "llvm/MC/MCInstrDesc.h" 44 #include "llvm/Pass.h" 45 #include "llvm/Support/CommandLine.h" 46 #include "llvm/Support/Compiler.h" 47 #include "llvm/Support/Debug.h" 48 #include "llvm/Support/ErrorHandling.h" 49 #include "llvm/Support/Format.h" 50 #include "llvm/Support/MathExtras.h" 51 #include "llvm/Support/raw_ostream.h" 52 #include <algorithm> 53 #include <cassert> 54 #include <cstdint> 55 #include <iterator> 56 #include <utility> 57 #include <vector> 58 59 using namespace llvm; 60 61 #define DEBUG_TYPE "arm-cp-islands" 62 63 #define ARM_CP_ISLANDS_OPT_NAME \ 64 "ARM constant island placement and branch shortening pass" 65 STATISTIC(NumCPEs, "Number of constpool entries"); 66 STATISTIC(NumSplit, "Number of uncond branches inserted"); 67 STATISTIC(NumCBrFixed, "Number of cond branches fixed"); 68 STATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 69 STATISTIC(NumTBs, "Number of table branches generated"); 70 STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk"); 71 STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk"); 72 STATISTIC(NumCBZ, "Number of CBZ / CBNZ formed"); 73 STATISTIC(NumJTMoved, "Number of jump table destination blocks moved"); 74 STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted"); 75 STATISTIC(NumLEInserted, "Number of LE backwards branches inserted"); 76 77 static cl::opt<bool> 78 AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true), 79 cl::desc("Adjust basic block layout to better use TB[BH]")); 80 81 static cl::opt<unsigned> 82 CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30), 83 cl::desc("The max number of iteration for converge")); 84 85 static cl::opt<bool> SynthesizeThumb1TBB( 86 "arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true), 87 cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an " 88 "equivalent to the TBB/TBH instructions")); 89 90 namespace { 91 92 /// ARMConstantIslands - Due to limited PC-relative displacements, ARM 93 /// requires constant pool entries to be scattered among the instructions 94 /// inside a function. To do this, it completely ignores the normal LLVM 95 /// constant pool; instead, it places constants wherever it feels like with 96 /// special instructions. 97 /// 98 /// The terminology used in this pass includes: 99 /// Islands - Clumps of constants placed in the function. 100 /// Water - Potential places where an island could be formed. 101 /// CPE - A constant pool entry that has been placed somewhere, which 102 /// tracks a list of users. 103 class ARMConstantIslands : public MachineFunctionPass { 104 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr; 105 106 /// WaterList - A sorted list of basic blocks where islands could be placed 107 /// (i.e. blocks that don't fall through to the following block, due 108 /// to a return, unreachable, or unconditional branch). 109 std::vector<MachineBasicBlock*> WaterList; 110 111 /// NewWaterList - The subset of WaterList that was created since the 112 /// previous iteration by inserting unconditional branches. 113 SmallSet<MachineBasicBlock*, 4> NewWaterList; 114 115 using water_iterator = std::vector<MachineBasicBlock *>::iterator; 116 117 /// CPUser - One user of a constant pool, keeping the machine instruction 118 /// pointer, the constant pool being referenced, and the max displacement 119 /// allowed from the instruction to the CP. The HighWaterMark records the 120 /// highest basic block where a new CPEntry can be placed. To ensure this 121 /// pass terminates, the CP entries are initially placed at the end of the 122 /// function and then move monotonically to lower addresses. The 123 /// exception to this rule is when the current CP entry for a particular 124 /// CPUser is out of range, but there is another CP entry for the same 125 /// constant value in range. We want to use the existing in-range CP 126 /// entry, but if it later moves out of range, the search for new water 127 /// should resume where it left off. The HighWaterMark is used to record 128 /// that point. 129 struct CPUser { 130 MachineInstr *MI; 131 MachineInstr *CPEMI; 132 MachineBasicBlock *HighWaterMark; 133 unsigned MaxDisp; 134 bool NegOk; 135 bool IsSoImm; 136 bool KnownAlignment = false; 137 138 CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, 139 bool neg, bool soimm) 140 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) { 141 HighWaterMark = CPEMI->getParent(); 142 } 143 144 /// getMaxDisp - Returns the maximum displacement supported by MI. 145 /// Correct for unknown alignment. 146 /// Conservatively subtract 2 bytes to handle weird alignment effects. 147 unsigned getMaxDisp() const { 148 return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2; 149 } 150 }; 151 152 /// CPUsers - Keep track of all of the machine instructions that use various 153 /// constant pools and their max displacement. 154 std::vector<CPUser> CPUsers; 155 156 /// CPEntry - One per constant pool entry, keeping the machine instruction 157 /// pointer, the constpool index, and the number of CPUser's which 158 /// reference this entry. 159 struct CPEntry { 160 MachineInstr *CPEMI; 161 unsigned CPI; 162 unsigned RefCount; 163 164 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 165 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 166 }; 167 168 /// CPEntries - Keep track of all of the constant pool entry machine 169 /// instructions. For each original constpool index (i.e. those that existed 170 /// upon entry to this pass), it keeps a vector of entries. Original 171 /// elements are cloned as we go along; the clones are put in the vector of 172 /// the original element, but have distinct CPIs. 173 /// 174 /// The first half of CPEntries contains generic constants, the second half 175 /// contains jump tables. Use getCombinedIndex on a generic CPEMI to look up 176 /// which vector it will be in here. 177 std::vector<std::vector<CPEntry>> CPEntries; 178 179 /// Maps a JT index to the offset in CPEntries containing copies of that 180 /// table. The equivalent map for a CONSTPOOL_ENTRY is the identity. 181 DenseMap<int, int> JumpTableEntryIndices; 182 183 /// Maps a JT index to the LEA that actually uses the index to calculate its 184 /// base address. 185 DenseMap<int, int> JumpTableUserIndices; 186 187 // Maps a MachineBasicBlock to the number of jump tables entries. 188 DenseMap<const MachineBasicBlock *, int> BlockJumpTableRefCount; 189 190 /// ImmBranch - One per immediate branch, keeping the machine instruction 191 /// pointer, conditional or unconditional, the max displacement, 192 /// and (if isCond is true) the corresponding unconditional branch 193 /// opcode. 194 struct ImmBranch { 195 MachineInstr *MI; 196 unsigned MaxDisp : 31; 197 bool isCond : 1; 198 unsigned UncondBr; 199 200 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr) 201 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 202 }; 203 204 /// ImmBranches - Keep track of all the immediate branch instructions. 205 std::vector<ImmBranch> ImmBranches; 206 207 /// PushPopMIs - Keep track of all the Thumb push / pop instructions. 208 SmallVector<MachineInstr*, 4> PushPopMIs; 209 210 /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions. 211 SmallVector<MachineInstr*, 4> T2JumpTables; 212 213 MachineFunction *MF; 214 MachineConstantPool *MCP; 215 const ARMBaseInstrInfo *TII; 216 const ARMSubtarget *STI; 217 ARMFunctionInfo *AFI; 218 MachineDominatorTree *DT = nullptr; 219 bool isThumb; 220 bool isThumb1; 221 bool isThumb2; 222 bool isPositionIndependentOrROPI; 223 224 public: 225 static char ID; 226 227 ARMConstantIslands() : MachineFunctionPass(ID) {} 228 229 bool runOnMachineFunction(MachineFunction &MF) override; 230 231 void getAnalysisUsage(AnalysisUsage &AU) const override { 232 AU.addRequired<MachineDominatorTree>(); 233 MachineFunctionPass::getAnalysisUsage(AU); 234 } 235 236 MachineFunctionProperties getRequiredProperties() const override { 237 return MachineFunctionProperties().set( 238 MachineFunctionProperties::Property::NoVRegs); 239 } 240 241 StringRef getPassName() const override { 242 return ARM_CP_ISLANDS_OPT_NAME; 243 } 244 245 private: 246 void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs); 247 void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs); 248 bool BBHasFallthrough(MachineBasicBlock *MBB); 249 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 250 Align getCPEAlign(const MachineInstr *CPEMI); 251 void scanFunctionJumpTables(); 252 void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs); 253 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI); 254 void updateForInsertedWaterBlock(MachineBasicBlock *NewBB); 255 bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI); 256 unsigned getCombinedIndex(const MachineInstr *CPEMI); 257 int findInRangeCPEntry(CPUser& U, unsigned UserOffset); 258 bool findAvailableWater(CPUser&U, unsigned UserOffset, 259 water_iterator &WaterIter, bool CloserWater); 260 void createNewWater(unsigned CPUserIndex, unsigned UserOffset, 261 MachineBasicBlock *&NewMBB); 262 bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater); 263 void removeDeadCPEMI(MachineInstr *CPEMI); 264 bool removeUnusedCPEntries(); 265 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset, 266 MachineInstr *CPEMI, unsigned Disp, bool NegOk, 267 bool DoDump = false); 268 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, 269 CPUser &U, unsigned &Growth); 270 bool fixupImmediateBr(ImmBranch &Br); 271 bool fixupConditionalBr(ImmBranch &Br); 272 bool fixupUnconditionalBr(ImmBranch &Br); 273 bool optimizeThumb2Instructions(); 274 bool optimizeThumb2Branches(); 275 bool reorderThumb2JumpTables(); 276 bool preserveBaseRegister(MachineInstr *JumpMI, MachineInstr *LEAMI, 277 unsigned &DeadSize, bool &CanDeleteLEA, 278 bool &BaseRegKill); 279 bool optimizeThumb2JumpTables(); 280 void fixupBTI(unsigned JTI, MachineBasicBlock &OldBB, 281 MachineBasicBlock &NewBB); 282 MachineBasicBlock *adjustJTTargetBlockForward(unsigned JTI, 283 MachineBasicBlock *BB, 284 MachineBasicBlock *JTBB); 285 286 unsigned getUserOffset(CPUser&) const; 287 void dumpBBs(); 288 void verify(); 289 290 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, 291 unsigned Disp, bool NegativeOK, bool IsSoImm = false); 292 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, 293 const CPUser &U) { 294 return isOffsetInRange(UserOffset, TrialOffset, 295 U.getMaxDisp(), U.NegOk, U.IsSoImm); 296 } 297 }; 298 299 } // end anonymous namespace 300 301 char ARMConstantIslands::ID = 0; 302 303 /// verify - check BBOffsets, BBSizes, alignment of islands 304 void ARMConstantIslands::verify() { 305 #ifndef NDEBUG 306 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 307 assert(is_sorted(*MF, [&BBInfo](const MachineBasicBlock &LHS, 308 const MachineBasicBlock &RHS) { 309 return BBInfo[LHS.getNumber()].postOffset() < 310 BBInfo[RHS.getNumber()].postOffset(); 311 })); 312 LLVM_DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n"); 313 for (CPUser &U : CPUsers) { 314 unsigned UserOffset = getUserOffset(U); 315 // Verify offset using the real max displacement without the safety 316 // adjustment. 317 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk, 318 /* DoDump = */ true)) { 319 LLVM_DEBUG(dbgs() << "OK\n"); 320 continue; 321 } 322 LLVM_DEBUG(dbgs() << "Out of range.\n"); 323 dumpBBs(); 324 LLVM_DEBUG(MF->dump()); 325 llvm_unreachable("Constant pool entry out of range!"); 326 } 327 #endif 328 } 329 330 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 331 /// print block size and offset information - debugging 332 LLVM_DUMP_METHOD void ARMConstantIslands::dumpBBs() { 333 LLVM_DEBUG({ 334 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 335 for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) { 336 const BasicBlockInfo &BBI = BBInfo[J]; 337 dbgs() << format("%08x %bb.%u\t", BBI.Offset, J) 338 << " kb=" << unsigned(BBI.KnownBits) 339 << " ua=" << unsigned(BBI.Unalign) << " pa=" << Log2(BBI.PostAlign) 340 << format(" size=%#x\n", BBInfo[J].Size); 341 } 342 }); 343 } 344 #endif 345 346 // Align blocks where the previous block does not fall through. This may add 347 // extra NOP's but they will not be executed. It uses the PrefLoopAlignment as a 348 // measure of how much to align, and only runs at CodeGenOpt::Aggressive. 349 static bool AlignBlocks(MachineFunction *MF, const ARMSubtarget *STI) { 350 if (MF->getTarget().getOptLevel() != CodeGenOpt::Aggressive || 351 MF->getFunction().hasOptSize()) 352 return false; 353 354 auto *TLI = STI->getTargetLowering(); 355 const Align Alignment = TLI->getPrefLoopAlignment(); 356 if (Alignment < 4) 357 return false; 358 359 bool Changed = false; 360 bool PrevCanFallthough = true; 361 for (auto &MBB : *MF) { 362 if (!PrevCanFallthough) { 363 Changed = true; 364 MBB.setAlignment(Alignment); 365 } 366 367 PrevCanFallthough = MBB.canFallThrough(); 368 369 // For LOB's, the ARMLowOverheadLoops pass may remove the unconditional 370 // branch later in the pipeline. 371 if (STI->hasLOB()) { 372 for (const auto &MI : reverse(MBB.terminators())) { 373 if (MI.getOpcode() == ARM::t2B && 374 MI.getOperand(0).getMBB() == MBB.getNextNode()) 375 continue; 376 if (isLoopStart(MI) || MI.getOpcode() == ARM::t2LoopEnd || 377 MI.getOpcode() == ARM::t2LoopEndDec) { 378 PrevCanFallthough = true; 379 break; 380 } 381 // Any other terminator - nothing to do 382 break; 383 } 384 } 385 } 386 387 return Changed; 388 } 389 390 bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) { 391 MF = &mf; 392 MCP = mf.getConstantPool(); 393 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(mf)); 394 395 LLVM_DEBUG(dbgs() << "***** ARMConstantIslands: " 396 << MCP->getConstants().size() << " CP entries, aligned to " 397 << MCP->getConstantPoolAlign().value() << " bytes *****\n"); 398 399 STI = &MF->getSubtarget<ARMSubtarget>(); 400 TII = STI->getInstrInfo(); 401 isPositionIndependentOrROPI = 402 STI->getTargetLowering()->isPositionIndependent() || STI->isROPI(); 403 AFI = MF->getInfo<ARMFunctionInfo>(); 404 DT = &getAnalysis<MachineDominatorTree>(); 405 406 isThumb = AFI->isThumbFunction(); 407 isThumb1 = AFI->isThumb1OnlyFunction(); 408 isThumb2 = AFI->isThumb2Function(); 409 410 bool GenerateTBB = isThumb2 || (isThumb1 && SynthesizeThumb1TBB); 411 // TBB generation code in this constant island pass has not been adapted to 412 // deal with speculation barriers. 413 if (STI->hardenSlsRetBr()) 414 GenerateTBB = false; 415 416 // Renumber all of the machine basic blocks in the function, guaranteeing that 417 // the numbers agree with the position of the block in the function. 418 MF->RenumberBlocks(); 419 420 // Try to reorder and otherwise adjust the block layout to make good use 421 // of the TB[BH] instructions. 422 bool MadeChange = false; 423 if (GenerateTBB && AdjustJumpTableBlocks) { 424 scanFunctionJumpTables(); 425 MadeChange |= reorderThumb2JumpTables(); 426 // Data is out of date, so clear it. It'll be re-computed later. 427 T2JumpTables.clear(); 428 // Blocks may have shifted around. Keep the numbering up to date. 429 MF->RenumberBlocks(); 430 } 431 432 // Align any non-fallthrough blocks 433 MadeChange |= AlignBlocks(MF, STI); 434 435 // Perform the initial placement of the constant pool entries. To start with, 436 // we put them all at the end of the function. 437 std::vector<MachineInstr*> CPEMIs; 438 if (!MCP->isEmpty()) 439 doInitialConstPlacement(CPEMIs); 440 441 if (MF->getJumpTableInfo()) 442 doInitialJumpTablePlacement(CPEMIs); 443 444 /// The next UID to take is the first unused one. 445 AFI->initPICLabelUId(CPEMIs.size()); 446 447 // Do the initial scan of the function, building up information about the 448 // sizes of each block, the location of all the water, and finding all of the 449 // constant pool users. 450 initializeFunctionInfo(CPEMIs); 451 CPEMIs.clear(); 452 LLVM_DEBUG(dumpBBs()); 453 454 // Functions with jump tables need an alignment of 4 because they use the ADR 455 // instruction, which aligns the PC to 4 bytes before adding an offset. 456 if (!T2JumpTables.empty()) 457 MF->ensureAlignment(Align(4)); 458 459 /// Remove dead constant pool entries. 460 MadeChange |= removeUnusedCPEntries(); 461 462 // Iteratively place constant pool entries and fix up branches until there 463 // is no change. 464 unsigned NoCPIters = 0, NoBRIters = 0; 465 while (true) { 466 LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n'); 467 bool CPChange = false; 468 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 469 // For most inputs, it converges in no more than 5 iterations. 470 // If it doesn't end in 10, the input may have huge BB or many CPEs. 471 // In this case, we will try different heuristics. 472 CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2); 473 if (CPChange && ++NoCPIters > CPMaxIteration) 474 report_fatal_error("Constant Island pass failed to converge!"); 475 LLVM_DEBUG(dumpBBs()); 476 477 // Clear NewWaterList now. If we split a block for branches, it should 478 // appear as "new water" for the next iteration of constant pool placement. 479 NewWaterList.clear(); 480 481 LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n'); 482 bool BRChange = false; 483 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 484 BRChange |= fixupImmediateBr(ImmBranches[i]); 485 if (BRChange && ++NoBRIters > 30) 486 report_fatal_error("Branch Fix Up pass failed to converge!"); 487 LLVM_DEBUG(dumpBBs()); 488 489 if (!CPChange && !BRChange) 490 break; 491 MadeChange = true; 492 } 493 494 // Shrink 32-bit Thumb2 load and store instructions. 495 if (isThumb2 && !STI->prefers32BitThumb()) 496 MadeChange |= optimizeThumb2Instructions(); 497 498 // Shrink 32-bit branch instructions. 499 if (isThumb && STI->hasV8MBaselineOps()) 500 MadeChange |= optimizeThumb2Branches(); 501 502 // Optimize jump tables using TBB / TBH. 503 if (GenerateTBB && !STI->genExecuteOnly()) 504 MadeChange |= optimizeThumb2JumpTables(); 505 506 // After a while, this might be made debug-only, but it is not expensive. 507 verify(); 508 509 // Save the mapping between original and cloned constpool entries. 510 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 511 for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) { 512 const CPEntry & CPE = CPEntries[i][j]; 513 if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI()) 514 AFI->recordCPEClone(i, CPE.CPI); 515 } 516 } 517 518 LLVM_DEBUG(dbgs() << '\n'; dumpBBs()); 519 520 BBUtils->clear(); 521 WaterList.clear(); 522 CPUsers.clear(); 523 CPEntries.clear(); 524 JumpTableEntryIndices.clear(); 525 JumpTableUserIndices.clear(); 526 BlockJumpTableRefCount.clear(); 527 ImmBranches.clear(); 528 PushPopMIs.clear(); 529 T2JumpTables.clear(); 530 531 return MadeChange; 532 } 533 534 /// Perform the initial placement of the regular constant pool entries. 535 /// To start with, we put them all at the end of the function. 536 void 537 ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) { 538 // Create the basic block to hold the CPE's. 539 MachineBasicBlock *BB = MF->CreateMachineBasicBlock(); 540 MF->push_back(BB); 541 542 // MachineConstantPool measures alignment in bytes. 543 const Align MaxAlign = MCP->getConstantPoolAlign(); 544 const unsigned MaxLogAlign = Log2(MaxAlign); 545 546 // Mark the basic block as required by the const-pool. 547 BB->setAlignment(MaxAlign); 548 549 // The function needs to be as aligned as the basic blocks. The linker may 550 // move functions around based on their alignment. 551 // Special case: halfword literals still need word alignment on the function. 552 Align FuncAlign = MaxAlign; 553 if (MaxAlign == 2) 554 FuncAlign = Align(4); 555 MF->ensureAlignment(FuncAlign); 556 557 // Order the entries in BB by descending alignment. That ensures correct 558 // alignment of all entries as long as BB is sufficiently aligned. Keep 559 // track of the insertion point for each alignment. We are going to bucket 560 // sort the entries as they are created. 561 SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxLogAlign + 1, 562 BB->end()); 563 564 // Add all of the constants from the constant pool to the end block, use an 565 // identity mapping of CPI's to CPE's. 566 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants(); 567 568 const DataLayout &TD = MF->getDataLayout(); 569 for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 570 unsigned Size = CPs[i].getSizeInBytes(TD); 571 Align Alignment = CPs[i].getAlign(); 572 // Verify that all constant pool entries are a multiple of their alignment. 573 // If not, we would have to pad them out so that instructions stay aligned. 574 assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!"); 575 576 // Insert CONSTPOOL_ENTRY before entries with a smaller alignment. 577 unsigned LogAlign = Log2(Alignment); 578 MachineBasicBlock::iterator InsAt = InsPoint[LogAlign]; 579 MachineInstr *CPEMI = 580 BuildMI(*BB, InsAt, DebugLoc(), TII->get(ARM::CONSTPOOL_ENTRY)) 581 .addImm(i).addConstantPoolIndex(i).addImm(Size); 582 CPEMIs.push_back(CPEMI); 583 584 // Ensure that future entries with higher alignment get inserted before 585 // CPEMI. This is bucket sort with iterators. 586 for (unsigned a = LogAlign + 1; a <= MaxLogAlign; ++a) 587 if (InsPoint[a] == InsAt) 588 InsPoint[a] = CPEMI; 589 590 // Add a new CPEntry, but no corresponding CPUser yet. 591 CPEntries.emplace_back(1, CPEntry(CPEMI, i)); 592 ++NumCPEs; 593 LLVM_DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = " 594 << Size << ", align = " << Alignment.value() << '\n'); 595 } 596 LLVM_DEBUG(BB->dump()); 597 } 598 599 /// Do initial placement of the jump tables. Because Thumb2's TBB and TBH 600 /// instructions can be made more efficient if the jump table immediately 601 /// follows the instruction, it's best to place them immediately next to their 602 /// jumps to begin with. In almost all cases they'll never be moved from that 603 /// position. 604 void ARMConstantIslands::doInitialJumpTablePlacement( 605 std::vector<MachineInstr *> &CPEMIs) { 606 unsigned i = CPEntries.size(); 607 auto MJTI = MF->getJumpTableInfo(); 608 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); 609 610 MachineBasicBlock *LastCorrectlyNumberedBB = nullptr; 611 for (MachineBasicBlock &MBB : *MF) { 612 auto MI = MBB.getLastNonDebugInstr(); 613 // Look past potential SpeculationBarriers at end of BB. 614 while (MI != MBB.end() && 615 (isSpeculationBarrierEndBBOpcode(MI->getOpcode()) || 616 MI->isDebugInstr())) 617 --MI; 618 619 if (MI == MBB.end()) 620 continue; 621 622 unsigned JTOpcode; 623 switch (MI->getOpcode()) { 624 default: 625 continue; 626 case ARM::BR_JTadd: 627 case ARM::BR_JTr: 628 case ARM::tBR_JTr: 629 case ARM::BR_JTm_i12: 630 case ARM::BR_JTm_rs: 631 JTOpcode = ARM::JUMPTABLE_ADDRS; 632 break; 633 case ARM::t2BR_JT: 634 JTOpcode = ARM::JUMPTABLE_INSTS; 635 break; 636 case ARM::tTBB_JT: 637 case ARM::t2TBB_JT: 638 JTOpcode = ARM::JUMPTABLE_TBB; 639 break; 640 case ARM::tTBH_JT: 641 case ARM::t2TBH_JT: 642 JTOpcode = ARM::JUMPTABLE_TBH; 643 break; 644 } 645 646 unsigned NumOps = MI->getDesc().getNumOperands(); 647 MachineOperand JTOp = 648 MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1)); 649 unsigned JTI = JTOp.getIndex(); 650 unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t); 651 MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock(); 652 MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB); 653 MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(), 654 DebugLoc(), TII->get(JTOpcode)) 655 .addImm(i++) 656 .addJumpTableIndex(JTI) 657 .addImm(Size); 658 CPEMIs.push_back(CPEMI); 659 CPEntries.emplace_back(1, CPEntry(CPEMI, JTI)); 660 JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1)); 661 if (!LastCorrectlyNumberedBB) 662 LastCorrectlyNumberedBB = &MBB; 663 } 664 665 // If we did anything then we need to renumber the subsequent blocks. 666 if (LastCorrectlyNumberedBB) 667 MF->RenumberBlocks(LastCorrectlyNumberedBB); 668 } 669 670 /// BBHasFallthrough - Return true if the specified basic block can fallthrough 671 /// into the block immediately after it. 672 bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) { 673 // Get the next machine basic block in the function. 674 MachineFunction::iterator MBBI = MBB->getIterator(); 675 // Can't fall off end of function. 676 if (std::next(MBBI) == MBB->getParent()->end()) 677 return false; 678 679 MachineBasicBlock *NextBB = &*std::next(MBBI); 680 if (!MBB->isSuccessor(NextBB)) 681 return false; 682 683 // Try to analyze the end of the block. A potential fallthrough may already 684 // have an unconditional branch for whatever reason. 685 MachineBasicBlock *TBB, *FBB; 686 SmallVector<MachineOperand, 4> Cond; 687 bool TooDifficult = TII->analyzeBranch(*MBB, TBB, FBB, Cond); 688 return TooDifficult || FBB == nullptr; 689 } 690 691 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 692 /// look up the corresponding CPEntry. 693 ARMConstantIslands::CPEntry * 694 ARMConstantIslands::findConstPoolEntry(unsigned CPI, 695 const MachineInstr *CPEMI) { 696 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 697 // Number of entries per constpool index should be small, just do a 698 // linear search. 699 for (CPEntry &CPE : CPEs) 700 if (CPE.CPEMI == CPEMI) 701 return &CPE; 702 return nullptr; 703 } 704 705 /// getCPEAlign - Returns the required alignment of the constant pool entry 706 /// represented by CPEMI. 707 Align ARMConstantIslands::getCPEAlign(const MachineInstr *CPEMI) { 708 switch (CPEMI->getOpcode()) { 709 case ARM::CONSTPOOL_ENTRY: 710 break; 711 case ARM::JUMPTABLE_TBB: 712 return isThumb1 ? Align(4) : Align(1); 713 case ARM::JUMPTABLE_TBH: 714 return isThumb1 ? Align(4) : Align(2); 715 case ARM::JUMPTABLE_INSTS: 716 return Align(2); 717 case ARM::JUMPTABLE_ADDRS: 718 return Align(4); 719 default: 720 llvm_unreachable("unknown constpool entry kind"); 721 } 722 723 unsigned CPI = getCombinedIndex(CPEMI); 724 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index."); 725 return MCP->getConstants()[CPI].getAlign(); 726 } 727 728 // Exception landing pads, blocks that has their adress taken, and function 729 // entry blocks will always be (potential) indirect jump targets, regardless of 730 // whether they are referenced by or not by jump tables. 731 static bool isAlwaysIndirectTarget(const MachineBasicBlock &MBB) { 732 return MBB.isEHPad() || MBB.hasAddressTaken() || 733 &MBB == &MBB.getParent()->front(); 734 } 735 736 /// scanFunctionJumpTables - Do a scan of the function, building up 737 /// information about the sizes of each block and the locations of all 738 /// the jump tables. 739 void ARMConstantIslands::scanFunctionJumpTables() { 740 for (MachineBasicBlock &MBB : *MF) { 741 for (MachineInstr &I : MBB) 742 if (I.isBranch() && 743 (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr)) 744 T2JumpTables.push_back(&I); 745 } 746 747 if (!MF->getInfo<ARMFunctionInfo>()->branchTargetEnforcement()) 748 return; 749 750 if (const MachineJumpTableInfo *JTI = MF->getJumpTableInfo()) 751 for (const MachineJumpTableEntry &JTE : JTI->getJumpTables()) 752 for (const MachineBasicBlock *MBB : JTE.MBBs) { 753 if (isAlwaysIndirectTarget(*MBB)) 754 // Set the reference count essentially to infinity, it will never 755 // reach zero and the BTI Instruction will never be removed. 756 BlockJumpTableRefCount[MBB] = std::numeric_limits<int>::max(); 757 else 758 ++BlockJumpTableRefCount[MBB]; 759 } 760 } 761 762 /// initializeFunctionInfo - Do the initial scan of the function, building up 763 /// information about the sizes of each block, the location of all the water, 764 /// and finding all of the constant pool users. 765 void ARMConstantIslands:: 766 initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) { 767 768 BBUtils->computeAllBlockSizes(); 769 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 770 // The known bits of the entry block offset are determined by the function 771 // alignment. 772 BBInfo.front().KnownBits = Log2(MF->getAlignment()); 773 774 // Compute block offsets and known bits. 775 BBUtils->adjustBBOffsetsAfter(&MF->front()); 776 777 // Now go back through the instructions and build up our data structures. 778 for (MachineBasicBlock &MBB : *MF) { 779 // If this block doesn't fall through into the next MBB, then this is 780 // 'water' that a constant pool island could be placed. 781 if (!BBHasFallthrough(&MBB)) 782 WaterList.push_back(&MBB); 783 784 for (MachineInstr &I : MBB) { 785 if (I.isDebugInstr()) 786 continue; 787 788 unsigned Opc = I.getOpcode(); 789 if (I.isBranch()) { 790 bool isCond = false; 791 unsigned Bits = 0; 792 unsigned Scale = 1; 793 int UOpc = Opc; 794 switch (Opc) { 795 default: 796 continue; // Ignore other JT branches 797 case ARM::t2BR_JT: 798 case ARM::tBR_JTr: 799 T2JumpTables.push_back(&I); 800 continue; // Does not get an entry in ImmBranches 801 case ARM::Bcc: 802 isCond = true; 803 UOpc = ARM::B; 804 LLVM_FALLTHROUGH; 805 case ARM::B: 806 Bits = 24; 807 Scale = 4; 808 break; 809 case ARM::tBcc: 810 isCond = true; 811 UOpc = ARM::tB; 812 Bits = 8; 813 Scale = 2; 814 break; 815 case ARM::tB: 816 Bits = 11; 817 Scale = 2; 818 break; 819 case ARM::t2Bcc: 820 isCond = true; 821 UOpc = ARM::t2B; 822 Bits = 20; 823 Scale = 2; 824 break; 825 case ARM::t2B: 826 Bits = 24; 827 Scale = 2; 828 break; 829 } 830 831 // Record this immediate branch. 832 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 833 ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc)); 834 } 835 836 if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET) 837 PushPopMIs.push_back(&I); 838 839 if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS || 840 Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB || 841 Opc == ARM::JUMPTABLE_TBH) 842 continue; 843 844 // Scan the instructions for constant pool operands. 845 for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op) 846 if (I.getOperand(op).isCPI() || I.getOperand(op).isJTI()) { 847 // We found one. The addressing mode tells us the max displacement 848 // from the PC that this instruction permits. 849 850 // Basic size info comes from the TSFlags field. 851 unsigned Bits = 0; 852 unsigned Scale = 1; 853 bool NegOk = false; 854 bool IsSoImm = false; 855 856 switch (Opc) { 857 default: 858 llvm_unreachable("Unknown addressing mode for CP reference!"); 859 860 // Taking the address of a CP entry. 861 case ARM::LEApcrel: 862 case ARM::LEApcrelJT: { 863 // This takes a SoImm, which is 8 bit immediate rotated. We'll 864 // pretend the maximum offset is 255 * 4. Since each instruction 865 // 4 byte wide, this is always correct. We'll check for other 866 // displacements that fits in a SoImm as well. 867 Bits = 8; 868 NegOk = true; 869 IsSoImm = true; 870 unsigned CPI = I.getOperand(op).getIndex(); 871 assert(CPI < CPEMIs.size()); 872 MachineInstr *CPEMI = CPEMIs[CPI]; 873 const Align CPEAlign = getCPEAlign(CPEMI); 874 const unsigned LogCPEAlign = Log2(CPEAlign); 875 if (LogCPEAlign >= 2) 876 Scale = 4; 877 else 878 // For constants with less than 4-byte alignment, 879 // we'll pretend the maximum offset is 255 * 1. 880 Scale = 1; 881 } 882 break; 883 case ARM::t2LEApcrel: 884 case ARM::t2LEApcrelJT: 885 Bits = 12; 886 NegOk = true; 887 break; 888 case ARM::tLEApcrel: 889 case ARM::tLEApcrelJT: 890 Bits = 8; 891 Scale = 4; 892 break; 893 894 case ARM::LDRBi12: 895 case ARM::LDRi12: 896 case ARM::LDRcp: 897 case ARM::t2LDRpci: 898 case ARM::t2LDRHpci: 899 case ARM::t2LDRSHpci: 900 case ARM::t2LDRBpci: 901 case ARM::t2LDRSBpci: 902 Bits = 12; // +-offset_12 903 NegOk = true; 904 break; 905 906 case ARM::tLDRpci: 907 Bits = 8; 908 Scale = 4; // +(offset_8*4) 909 break; 910 911 case ARM::VLDRD: 912 case ARM::VLDRS: 913 Bits = 8; 914 Scale = 4; // +-(offset_8*4) 915 NegOk = true; 916 break; 917 case ARM::VLDRH: 918 Bits = 8; 919 Scale = 2; // +-(offset_8*2) 920 NegOk = true; 921 break; 922 } 923 924 // Remember that this is a user of a CP entry. 925 unsigned CPI = I.getOperand(op).getIndex(); 926 if (I.getOperand(op).isJTI()) { 927 JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size())); 928 CPI = JumpTableEntryIndices[CPI]; 929 } 930 931 MachineInstr *CPEMI = CPEMIs[CPI]; 932 unsigned MaxOffs = ((1 << Bits)-1) * Scale; 933 CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm)); 934 935 // Increment corresponding CPEntry reference count. 936 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 937 assert(CPE && "Cannot find a corresponding CPEntry!"); 938 CPE->RefCount++; 939 940 // Instructions can only use one CP entry, don't bother scanning the 941 // rest of the operands. 942 break; 943 } 944 } 945 } 946 } 947 948 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 949 /// ID. 950 static bool CompareMBBNumbers(const MachineBasicBlock *LHS, 951 const MachineBasicBlock *RHS) { 952 return LHS->getNumber() < RHS->getNumber(); 953 } 954 955 /// updateForInsertedWaterBlock - When a block is newly inserted into the 956 /// machine function, it upsets all of the block numbers. Renumber the blocks 957 /// and update the arrays that parallel this numbering. 958 void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) { 959 // Renumber the MBB's to keep them consecutive. 960 NewBB->getParent()->RenumberBlocks(NewBB); 961 962 // Insert an entry into BBInfo to align it properly with the (newly 963 // renumbered) block numbers. 964 BBUtils->insert(NewBB->getNumber(), BasicBlockInfo()); 965 966 // Next, update WaterList. Specifically, we need to add NewMBB as having 967 // available water after it. 968 water_iterator IP = llvm::lower_bound(WaterList, NewBB, CompareMBBNumbers); 969 WaterList.insert(IP, NewBB); 970 } 971 972 /// Split the basic block containing MI into two blocks, which are joined by 973 /// an unconditional branch. Update data structures and renumber blocks to 974 /// account for this change and returns the newly created block. 975 MachineBasicBlock *ARMConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) { 976 MachineBasicBlock *OrigBB = MI->getParent(); 977 978 // Collect liveness information at MI. 979 LivePhysRegs LRs(*MF->getSubtarget().getRegisterInfo()); 980 LRs.addLiveOuts(*OrigBB); 981 auto LivenessEnd = ++MachineBasicBlock::iterator(MI).getReverse(); 982 for (MachineInstr &LiveMI : make_range(OrigBB->rbegin(), LivenessEnd)) 983 LRs.stepBackward(LiveMI); 984 985 // Create a new MBB for the code after the OrigBB. 986 MachineBasicBlock *NewBB = 987 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock()); 988 MachineFunction::iterator MBBI = ++OrigBB->getIterator(); 989 MF->insert(MBBI, NewBB); 990 991 // Splice the instructions starting with MI over to NewBB. 992 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 993 994 // Add an unconditional branch from OrigBB to NewBB. 995 // Note the new unconditional branch is not being recorded. 996 // There doesn't seem to be meaningful DebugInfo available; this doesn't 997 // correspond to anything in the source. 998 unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B; 999 if (!isThumb) 1000 BuildMI(OrigBB, DebugLoc(), TII->get(Opc)).addMBB(NewBB); 1001 else 1002 BuildMI(OrigBB, DebugLoc(), TII->get(Opc)) 1003 .addMBB(NewBB) 1004 .add(predOps(ARMCC::AL)); 1005 ++NumSplit; 1006 1007 // Update the CFG. All succs of OrigBB are now succs of NewBB. 1008 NewBB->transferSuccessors(OrigBB); 1009 1010 // OrigBB branches to NewBB. 1011 OrigBB->addSuccessor(NewBB); 1012 1013 // Update live-in information in the new block. 1014 MachineRegisterInfo &MRI = MF->getRegInfo(); 1015 for (MCPhysReg L : LRs) 1016 if (!MRI.isReserved(L)) 1017 NewBB->addLiveIn(L); 1018 1019 // Update internal data structures to account for the newly inserted MBB. 1020 // This is almost the same as updateForInsertedWaterBlock, except that 1021 // the Water goes after OrigBB, not NewBB. 1022 MF->RenumberBlocks(NewBB); 1023 1024 // Insert an entry into BBInfo to align it properly with the (newly 1025 // renumbered) block numbers. 1026 BBUtils->insert(NewBB->getNumber(), BasicBlockInfo()); 1027 1028 // Next, update WaterList. Specifically, we need to add OrigMBB as having 1029 // available water after it (but not if it's already there, which happens 1030 // when splitting before a conditional branch that is followed by an 1031 // unconditional branch - in that case we want to insert NewBB). 1032 water_iterator IP = llvm::lower_bound(WaterList, OrigBB, CompareMBBNumbers); 1033 MachineBasicBlock* WaterBB = *IP; 1034 if (WaterBB == OrigBB) 1035 WaterList.insert(std::next(IP), NewBB); 1036 else 1037 WaterList.insert(IP, OrigBB); 1038 NewWaterList.insert(OrigBB); 1039 1040 // Figure out how large the OrigBB is. As the first half of the original 1041 // block, it cannot contain a tablejump. The size includes 1042 // the new jump we added. (It should be possible to do this without 1043 // recounting everything, but it's very confusing, and this is rarely 1044 // executed.) 1045 BBUtils->computeBlockSize(OrigBB); 1046 1047 // Figure out how large the NewMBB is. As the second half of the original 1048 // block, it may contain a tablejump. 1049 BBUtils->computeBlockSize(NewBB); 1050 1051 // All BBOffsets following these blocks must be modified. 1052 BBUtils->adjustBBOffsetsAfter(OrigBB); 1053 1054 return NewBB; 1055 } 1056 1057 /// getUserOffset - Compute the offset of U.MI as seen by the hardware 1058 /// displacement computation. Update U.KnownAlignment to match its current 1059 /// basic block location. 1060 unsigned ARMConstantIslands::getUserOffset(CPUser &U) const { 1061 unsigned UserOffset = BBUtils->getOffsetOf(U.MI); 1062 1063 SmallVectorImpl<BasicBlockInfo> &BBInfo = BBUtils->getBBInfo(); 1064 const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()]; 1065 unsigned KnownBits = BBI.internalKnownBits(); 1066 1067 // The value read from PC is offset from the actual instruction address. 1068 UserOffset += (isThumb ? 4 : 8); 1069 1070 // Because of inline assembly, we may not know the alignment (mod 4) of U.MI. 1071 // Make sure U.getMaxDisp() returns a constrained range. 1072 U.KnownAlignment = (KnownBits >= 2); 1073 1074 // On Thumb, offsets==2 mod 4 are rounded down by the hardware for 1075 // purposes of the displacement computation; compensate for that here. 1076 // For unknown alignments, getMaxDisp() constrains the range instead. 1077 if (isThumb && U.KnownAlignment) 1078 UserOffset &= ~3u; 1079 1080 return UserOffset; 1081 } 1082 1083 /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool 1084 /// reference) is within MaxDisp of TrialOffset (a proposed location of a 1085 /// constant pool entry). 1086 /// UserOffset is computed by getUserOffset above to include PC adjustments. If 1087 /// the mod 4 alignment of UserOffset is not known, the uncertainty must be 1088 /// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that. 1089 bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset, 1090 unsigned TrialOffset, unsigned MaxDisp, 1091 bool NegativeOK, bool IsSoImm) { 1092 if (UserOffset <= TrialOffset) { 1093 // User before the Trial. 1094 if (TrialOffset - UserOffset <= MaxDisp) 1095 return true; 1096 // FIXME: Make use full range of soimm values. 1097 } else if (NegativeOK) { 1098 if (UserOffset - TrialOffset <= MaxDisp) 1099 return true; 1100 // FIXME: Make use full range of soimm values. 1101 } 1102 return false; 1103 } 1104 1105 /// isWaterInRange - Returns true if a CPE placed after the specified 1106 /// Water (a basic block) will be in range for the specific MI. 1107 /// 1108 /// Compute how much the function will grow by inserting a CPE after Water. 1109 bool ARMConstantIslands::isWaterInRange(unsigned UserOffset, 1110 MachineBasicBlock* Water, CPUser &U, 1111 unsigned &Growth) { 1112 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 1113 const Align CPEAlign = getCPEAlign(U.CPEMI); 1114 const unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPEAlign); 1115 unsigned NextBlockOffset; 1116 Align NextBlockAlignment; 1117 MachineFunction::const_iterator NextBlock = Water->getIterator(); 1118 if (++NextBlock == MF->end()) { 1119 NextBlockOffset = BBInfo[Water->getNumber()].postOffset(); 1120 } else { 1121 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset; 1122 NextBlockAlignment = NextBlock->getAlignment(); 1123 } 1124 unsigned Size = U.CPEMI->getOperand(2).getImm(); 1125 unsigned CPEEnd = CPEOffset + Size; 1126 1127 // The CPE may be able to hide in the alignment padding before the next 1128 // block. It may also cause more padding to be required if it is more aligned 1129 // that the next block. 1130 if (CPEEnd > NextBlockOffset) { 1131 Growth = CPEEnd - NextBlockOffset; 1132 // Compute the padding that would go at the end of the CPE to align the next 1133 // block. 1134 Growth += offsetToAlignment(CPEEnd, NextBlockAlignment); 1135 1136 // If the CPE is to be inserted before the instruction, that will raise 1137 // the offset of the instruction. Also account for unknown alignment padding 1138 // in blocks between CPE and the user. 1139 if (CPEOffset < UserOffset) 1140 UserOffset += Growth + UnknownPadding(MF->getAlignment(), Log2(CPEAlign)); 1141 } else 1142 // CPE fits in existing padding. 1143 Growth = 0; 1144 1145 return isOffsetInRange(UserOffset, CPEOffset, U); 1146 } 1147 1148 /// isCPEntryInRange - Returns true if the distance between specific MI and 1149 /// specific ConstPool entry instruction can fit in MI's displacement field. 1150 bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset, 1151 MachineInstr *CPEMI, unsigned MaxDisp, 1152 bool NegOk, bool DoDump) { 1153 unsigned CPEOffset = BBUtils->getOffsetOf(CPEMI); 1154 1155 if (DoDump) { 1156 LLVM_DEBUG({ 1157 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 1158 unsigned Block = MI->getParent()->getNumber(); 1159 const BasicBlockInfo &BBI = BBInfo[Block]; 1160 dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() 1161 << " max delta=" << MaxDisp 1162 << format(" insn address=%#x", UserOffset) << " in " 1163 << printMBBReference(*MI->getParent()) << ": " 1164 << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI 1165 << format("CPE address=%#x offset=%+d: ", CPEOffset, 1166 int(CPEOffset - UserOffset)); 1167 }); 1168 } 1169 1170 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk); 1171 } 1172 1173 #ifndef NDEBUG 1174 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor 1175 /// unconditionally branches to its only successor. 1176 static bool BBIsJumpedOver(MachineBasicBlock *MBB) { 1177 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 1178 return false; 1179 1180 MachineBasicBlock *Succ = *MBB->succ_begin(); 1181 MachineBasicBlock *Pred = *MBB->pred_begin(); 1182 MachineInstr *PredMI = &Pred->back(); 1183 if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB 1184 || PredMI->getOpcode() == ARM::t2B) 1185 return PredMI->getOperand(0).getMBB() == Succ; 1186 return false; 1187 } 1188 #endif // NDEBUG 1189 1190 /// decrementCPEReferenceCount - find the constant pool entry with index CPI 1191 /// and instruction CPEMI, and decrement its refcount. If the refcount 1192 /// becomes 0 remove the entry and instruction. Returns true if we removed 1193 /// the entry, false if we didn't. 1194 bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI, 1195 MachineInstr *CPEMI) { 1196 // Find the old entry. Eliminate it if it is no longer used. 1197 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 1198 assert(CPE && "Unexpected!"); 1199 if (--CPE->RefCount == 0) { 1200 removeDeadCPEMI(CPEMI); 1201 CPE->CPEMI = nullptr; 1202 --NumCPEs; 1203 return true; 1204 } 1205 return false; 1206 } 1207 1208 unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) { 1209 if (CPEMI->getOperand(1).isCPI()) 1210 return CPEMI->getOperand(1).getIndex(); 1211 1212 return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()]; 1213 } 1214 1215 /// LookForCPEntryInRange - see if the currently referenced CPE is in range; 1216 /// if not, see if an in-range clone of the CPE is in range, and if so, 1217 /// change the data structures so the user references the clone. Returns: 1218 /// 0 = no existing entry found 1219 /// 1 = entry found, and there were no code insertions or deletions 1220 /// 2 = entry found, and there were code insertions or deletions 1221 int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) { 1222 MachineInstr *UserMI = U.MI; 1223 MachineInstr *CPEMI = U.CPEMI; 1224 1225 // Check to see if the CPE is already in-range. 1226 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk, 1227 true)) { 1228 LLVM_DEBUG(dbgs() << "In range\n"); 1229 return 1; 1230 } 1231 1232 // No. Look for previously created clones of the CPE that are in range. 1233 unsigned CPI = getCombinedIndex(CPEMI); 1234 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 1235 for (CPEntry &CPE : CPEs) { 1236 // We already tried this one 1237 if (CPE.CPEMI == CPEMI) 1238 continue; 1239 // Removing CPEs can leave empty entries, skip 1240 if (CPE.CPEMI == nullptr) 1241 continue; 1242 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getMaxDisp(), 1243 U.NegOk)) { 1244 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPE.CPI 1245 << "\n"); 1246 // Point the CPUser node to the replacement 1247 U.CPEMI = CPE.CPEMI; 1248 // Change the CPI in the instruction operand to refer to the clone. 1249 for (MachineOperand &MO : UserMI->operands()) 1250 if (MO.isCPI()) { 1251 MO.setIndex(CPE.CPI); 1252 break; 1253 } 1254 // Adjust the refcount of the clone... 1255 CPE.RefCount++; 1256 // ...and the original. If we didn't remove the old entry, none of the 1257 // addresses changed, so we don't need another pass. 1258 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1; 1259 } 1260 } 1261 return 0; 1262 } 1263 1264 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 1265 /// the specific unconditional branch instruction. 1266 static inline unsigned getUnconditionalBrDisp(int Opc) { 1267 switch (Opc) { 1268 case ARM::tB: 1269 return ((1<<10)-1)*2; 1270 case ARM::t2B: 1271 return ((1<<23)-1)*2; 1272 default: 1273 break; 1274 } 1275 1276 return ((1<<23)-1)*4; 1277 } 1278 1279 /// findAvailableWater - Look for an existing entry in the WaterList in which 1280 /// we can place the CPE referenced from U so it's within range of U's MI. 1281 /// Returns true if found, false if not. If it returns true, WaterIter 1282 /// is set to the WaterList entry. For Thumb, prefer water that will not 1283 /// introduce padding to water that will. To ensure that this pass 1284 /// terminates, the CPE location for a particular CPUser is only allowed to 1285 /// move to a lower address, so search backward from the end of the list and 1286 /// prefer the first water that is in range. 1287 bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset, 1288 water_iterator &WaterIter, 1289 bool CloserWater) { 1290 if (WaterList.empty()) 1291 return false; 1292 1293 unsigned BestGrowth = ~0u; 1294 // The nearest water without splitting the UserBB is right after it. 1295 // If the distance is still large (we have a big BB), then we need to split it 1296 // if we don't converge after certain iterations. This helps the following 1297 // situation to converge: 1298 // BB0: 1299 // Big BB 1300 // BB1: 1301 // Constant Pool 1302 // When a CP access is out of range, BB0 may be used as water. However, 1303 // inserting islands between BB0 and BB1 makes other accesses out of range. 1304 MachineBasicBlock *UserBB = U.MI->getParent(); 1305 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 1306 const Align CPEAlign = getCPEAlign(U.CPEMI); 1307 unsigned MinNoSplitDisp = BBInfo[UserBB->getNumber()].postOffset(CPEAlign); 1308 if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2) 1309 return false; 1310 for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();; 1311 --IP) { 1312 MachineBasicBlock* WaterBB = *IP; 1313 // Check if water is in range and is either at a lower address than the 1314 // current "high water mark" or a new water block that was created since 1315 // the previous iteration by inserting an unconditional branch. In the 1316 // latter case, we want to allow resetting the high water mark back to 1317 // this new water since we haven't seen it before. Inserting branches 1318 // should be relatively uncommon and when it does happen, we want to be 1319 // sure to take advantage of it for all the CPEs near that block, so that 1320 // we don't insert more branches than necessary. 1321 // When CloserWater is true, we try to find the lowest address after (or 1322 // equal to) user MI's BB no matter of padding growth. 1323 unsigned Growth; 1324 if (isWaterInRange(UserOffset, WaterBB, U, Growth) && 1325 (WaterBB->getNumber() < U.HighWaterMark->getNumber() || 1326 NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) && 1327 Growth < BestGrowth) { 1328 // This is the least amount of required padding seen so far. 1329 BestGrowth = Growth; 1330 WaterIter = IP; 1331 LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB) 1332 << " Growth=" << Growth << '\n'); 1333 1334 if (CloserWater && WaterBB == U.MI->getParent()) 1335 return true; 1336 // Keep looking unless it is perfect and we're not looking for the lowest 1337 // possible address. 1338 if (!CloserWater && BestGrowth == 0) 1339 return true; 1340 } 1341 if (IP == B) 1342 break; 1343 } 1344 return BestGrowth != ~0u; 1345 } 1346 1347 /// createNewWater - No existing WaterList entry will work for 1348 /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 1349 /// block is used if in range, and the conditional branch munged so control 1350 /// flow is correct. Otherwise the block is split to create a hole with an 1351 /// unconditional branch around it. In either case NewMBB is set to a 1352 /// block following which the new island can be inserted (the WaterList 1353 /// is not adjusted). 1354 void ARMConstantIslands::createNewWater(unsigned CPUserIndex, 1355 unsigned UserOffset, 1356 MachineBasicBlock *&NewMBB) { 1357 CPUser &U = CPUsers[CPUserIndex]; 1358 MachineInstr *UserMI = U.MI; 1359 MachineInstr *CPEMI = U.CPEMI; 1360 const Align CPEAlign = getCPEAlign(CPEMI); 1361 MachineBasicBlock *UserMBB = UserMI->getParent(); 1362 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 1363 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()]; 1364 1365 // If the block does not end in an unconditional branch already, and if the 1366 // end of the block is within range, make new water there. (The addition 1367 // below is for the unconditional branch we will be adding: 4 bytes on ARM + 1368 // Thumb2, 2 on Thumb1. 1369 if (BBHasFallthrough(UserMBB)) { 1370 // Size of branch to insert. 1371 unsigned Delta = isThumb1 ? 2 : 4; 1372 // Compute the offset where the CPE will begin. 1373 unsigned CPEOffset = UserBBI.postOffset(CPEAlign) + Delta; 1374 1375 if (isOffsetInRange(UserOffset, CPEOffset, U)) { 1376 LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB) 1377 << format(", expected CPE offset %#x\n", CPEOffset)); 1378 NewMBB = &*++UserMBB->getIterator(); 1379 // Add an unconditional branch from UserMBB to fallthrough block. Record 1380 // it for branch lengthening; this new branch will not get out of range, 1381 // but if the preceding conditional branch is out of range, the targets 1382 // will be exchanged, and the altered branch may be out of range, so the 1383 // machinery has to know about it. 1384 int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B; 1385 if (!isThumb) 1386 BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB); 1387 else 1388 BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)) 1389 .addMBB(NewMBB) 1390 .add(predOps(ARMCC::AL)); 1391 unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 1392 ImmBranches.push_back(ImmBranch(&UserMBB->back(), 1393 MaxDisp, false, UncondBr)); 1394 BBUtils->computeBlockSize(UserMBB); 1395 BBUtils->adjustBBOffsetsAfter(UserMBB); 1396 return; 1397 } 1398 } 1399 1400 // What a big block. Find a place within the block to split it. This is a 1401 // little tricky on Thumb1 since instructions are 2 bytes and constant pool 1402 // entries are 4 bytes: if instruction I references island CPE, and 1403 // instruction I+1 references CPE', it will not work well to put CPE as far 1404 // forward as possible, since then CPE' cannot immediately follow it (that 1405 // location is 2 bytes farther away from I+1 than CPE was from I) and we'd 1406 // need to create a new island. So, we make a first guess, then walk through 1407 // the instructions between the one currently being looked at and the 1408 // possible insertion point, and make sure any other instructions that 1409 // reference CPEs will be able to use the same island area; if not, we back 1410 // up the insertion point. 1411 1412 // Try to split the block so it's fully aligned. Compute the latest split 1413 // point where we can add a 4-byte branch instruction, and then align to 1414 // Align which is the largest possible alignment in the function. 1415 const Align Align = MF->getAlignment(); 1416 assert(Align >= CPEAlign && "Over-aligned constant pool entry"); 1417 unsigned KnownBits = UserBBI.internalKnownBits(); 1418 unsigned UPad = UnknownPadding(Align, KnownBits); 1419 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad; 1420 LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x", 1421 BaseInsertOffset)); 1422 1423 // The 4 in the following is for the unconditional branch we'll be inserting 1424 // (allows for long branch on Thumb1). Alignment of the island is handled 1425 // inside isOffsetInRange. 1426 BaseInsertOffset -= 4; 1427 1428 LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset) 1429 << " la=" << Log2(Align) << " kb=" << KnownBits 1430 << " up=" << UPad << '\n'); 1431 1432 // This could point off the end of the block if we've already got constant 1433 // pool entries following this block; only the last one is in the water list. 1434 // Back past any possible branches (allow for a conditional and a maximally 1435 // long unconditional). 1436 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) { 1437 // Ensure BaseInsertOffset is larger than the offset of the instruction 1438 // following UserMI so that the loop which searches for the split point 1439 // iterates at least once. 1440 BaseInsertOffset = 1441 std::max(UserBBI.postOffset() - UPad - 8, 1442 UserOffset + TII->getInstSizeInBytes(*UserMI) + 1); 1443 // If the CP is referenced(ie, UserOffset) is in first four instructions 1444 // after IT, this recalculated BaseInsertOffset could be in the middle of 1445 // an IT block. If it is, change the BaseInsertOffset to just after the 1446 // IT block. This still make the CP Entry is in range becuase of the 1447 // following reasons. 1448 // 1. The initial BaseseInsertOffset calculated is (UserOffset + 1449 // U.getMaxDisp() - UPad). 1450 // 2. An IT block is only at most 4 instructions plus the "it" itself (18 1451 // bytes). 1452 // 3. All the relevant instructions support much larger Maximum 1453 // displacement. 1454 MachineBasicBlock::iterator I = UserMI; 1455 ++I; 1456 Register PredReg; 1457 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI); 1458 I->getOpcode() != ARM::t2IT && 1459 getITInstrPredicate(*I, PredReg) != ARMCC::AL; 1460 Offset += TII->getInstSizeInBytes(*I), I = std::next(I)) { 1461 BaseInsertOffset = 1462 std::max(BaseInsertOffset, Offset + TII->getInstSizeInBytes(*I) + 1); 1463 assert(I != UserMBB->end() && "Fell off end of block"); 1464 } 1465 LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset)); 1466 } 1467 unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad + 1468 CPEMI->getOperand(2).getImm(); 1469 MachineBasicBlock::iterator MI = UserMI; 1470 ++MI; 1471 unsigned CPUIndex = CPUserIndex+1; 1472 unsigned NumCPUsers = CPUsers.size(); 1473 MachineInstr *LastIT = nullptr; 1474 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI); 1475 Offset < BaseInsertOffset; 1476 Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) { 1477 assert(MI != UserMBB->end() && "Fell off end of block"); 1478 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) { 1479 CPUser &U = CPUsers[CPUIndex]; 1480 if (!isOffsetInRange(Offset, EndInsertOffset, U)) { 1481 // Shift intertion point by one unit of alignment so it is within reach. 1482 BaseInsertOffset -= Align.value(); 1483 EndInsertOffset -= Align.value(); 1484 } 1485 // This is overly conservative, as we don't account for CPEMIs being 1486 // reused within the block, but it doesn't matter much. Also assume CPEs 1487 // are added in order with alignment padding. We may eventually be able 1488 // to pack the aligned CPEs better. 1489 EndInsertOffset += U.CPEMI->getOperand(2).getImm(); 1490 CPUIndex++; 1491 } 1492 1493 // Remember the last IT instruction. 1494 if (MI->getOpcode() == ARM::t2IT) 1495 LastIT = &*MI; 1496 } 1497 1498 --MI; 1499 1500 // Avoid splitting an IT block. 1501 if (LastIT) { 1502 Register PredReg; 1503 ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg); 1504 if (CC != ARMCC::AL) 1505 MI = LastIT; 1506 } 1507 1508 // Avoid splitting a MOVW+MOVT pair with a relocation on Windows. 1509 // On Windows, this instruction pair is covered by one single 1510 // IMAGE_REL_ARM_MOV32T relocation which covers both instructions. If a 1511 // constant island is injected inbetween them, the relocation will clobber 1512 // the instruction and fail to update the MOVT instruction. 1513 // (These instructions are bundled up until right before the ConstantIslands 1514 // pass.) 1515 if (STI->isTargetWindows() && isThumb && MI->getOpcode() == ARM::t2MOVTi16 && 1516 (MI->getOperand(2).getTargetFlags() & ARMII::MO_OPTION_MASK) == 1517 ARMII::MO_HI16) { 1518 --MI; 1519 assert(MI->getOpcode() == ARM::t2MOVi16 && 1520 (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) == 1521 ARMII::MO_LO16); 1522 } 1523 1524 // We really must not split an IT block. 1525 #ifndef NDEBUG 1526 Register PredReg; 1527 assert(!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL); 1528 #endif 1529 NewMBB = splitBlockBeforeInstr(&*MI); 1530 } 1531 1532 /// handleConstantPoolUser - Analyze the specified user, checking to see if it 1533 /// is out-of-range. If so, pick up the constant pool value and move it some 1534 /// place in-range. Return true if we changed any addresses (thus must run 1535 /// another pass of branch lengthening), false otherwise. 1536 bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex, 1537 bool CloserWater) { 1538 CPUser &U = CPUsers[CPUserIndex]; 1539 MachineInstr *UserMI = U.MI; 1540 MachineInstr *CPEMI = U.CPEMI; 1541 unsigned CPI = getCombinedIndex(CPEMI); 1542 unsigned Size = CPEMI->getOperand(2).getImm(); 1543 // Compute this only once, it's expensive. 1544 unsigned UserOffset = getUserOffset(U); 1545 1546 // See if the current entry is within range, or there is a clone of it 1547 // in range. 1548 int result = findInRangeCPEntry(U, UserOffset); 1549 if (result==1) return false; 1550 else if (result==2) return true; 1551 1552 // No existing clone of this CPE is within range. 1553 // We will be generating a new clone. Get a UID for it. 1554 unsigned ID = AFI->createPICLabelUId(); 1555 1556 // Look for water where we can place this CPE. 1557 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock(); 1558 MachineBasicBlock *NewMBB; 1559 water_iterator IP; 1560 if (findAvailableWater(U, UserOffset, IP, CloserWater)) { 1561 LLVM_DEBUG(dbgs() << "Found water in range\n"); 1562 MachineBasicBlock *WaterBB = *IP; 1563 1564 // If the original WaterList entry was "new water" on this iteration, 1565 // propagate that to the new island. This is just keeping NewWaterList 1566 // updated to match the WaterList, which will be updated below. 1567 if (NewWaterList.erase(WaterBB)) 1568 NewWaterList.insert(NewIsland); 1569 1570 // The new CPE goes before the following block (NewMBB). 1571 NewMBB = &*++WaterBB->getIterator(); 1572 } else { 1573 // No water found. 1574 LLVM_DEBUG(dbgs() << "No water found\n"); 1575 createNewWater(CPUserIndex, UserOffset, NewMBB); 1576 1577 // splitBlockBeforeInstr adds to WaterList, which is important when it is 1578 // called while handling branches so that the water will be seen on the 1579 // next iteration for constant pools, but in this context, we don't want 1580 // it. Check for this so it will be removed from the WaterList. 1581 // Also remove any entry from NewWaterList. 1582 MachineBasicBlock *WaterBB = &*--NewMBB->getIterator(); 1583 IP = find(WaterList, WaterBB); 1584 if (IP != WaterList.end()) 1585 NewWaterList.erase(WaterBB); 1586 1587 // We are adding new water. Update NewWaterList. 1588 NewWaterList.insert(NewIsland); 1589 } 1590 // Always align the new block because CP entries can be smaller than 4 1591 // bytes. Be careful not to decrease the existing alignment, e.g. NewMBB may 1592 // be an already aligned constant pool block. 1593 const Align Alignment = isThumb ? Align(2) : Align(4); 1594 if (NewMBB->getAlignment() < Alignment) 1595 NewMBB->setAlignment(Alignment); 1596 1597 // Remove the original WaterList entry; we want subsequent insertions in 1598 // this vicinity to go after the one we're about to insert. This 1599 // considerably reduces the number of times we have to move the same CPE 1600 // more than once and is also important to ensure the algorithm terminates. 1601 if (IP != WaterList.end()) 1602 WaterList.erase(IP); 1603 1604 // Okay, we know we can put an island before NewMBB now, do it! 1605 MF->insert(NewMBB->getIterator(), NewIsland); 1606 1607 // Update internal data structures to account for the newly inserted MBB. 1608 updateForInsertedWaterBlock(NewIsland); 1609 1610 // Now that we have an island to add the CPE to, clone the original CPE and 1611 // add it to the island. 1612 U.HighWaterMark = NewIsland; 1613 U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc()) 1614 .addImm(ID) 1615 .add(CPEMI->getOperand(1)) 1616 .addImm(Size); 1617 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 1618 ++NumCPEs; 1619 1620 // Decrement the old entry, and remove it if refcount becomes 0. 1621 decrementCPEReferenceCount(CPI, CPEMI); 1622 1623 // Mark the basic block as aligned as required by the const-pool entry. 1624 NewIsland->setAlignment(getCPEAlign(U.CPEMI)); 1625 1626 // Increase the size of the island block to account for the new entry. 1627 BBUtils->adjustBBSize(NewIsland, Size); 1628 BBUtils->adjustBBOffsetsAfter(&*--NewIsland->getIterator()); 1629 1630 // Finally, change the CPI in the instruction operand to be ID. 1631 for (MachineOperand &MO : UserMI->operands()) 1632 if (MO.isCPI()) { 1633 MO.setIndex(ID); 1634 break; 1635 } 1636 1637 LLVM_DEBUG( 1638 dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI 1639 << format(" offset=%#x\n", 1640 BBUtils->getBBInfo()[NewIsland->getNumber()].Offset)); 1641 1642 return true; 1643 } 1644 1645 /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update 1646 /// sizes and offsets of impacted basic blocks. 1647 void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) { 1648 MachineBasicBlock *CPEBB = CPEMI->getParent(); 1649 unsigned Size = CPEMI->getOperand(2).getImm(); 1650 CPEMI->eraseFromParent(); 1651 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 1652 BBUtils->adjustBBSize(CPEBB, -Size); 1653 // All succeeding offsets have the current size value added in, fix this. 1654 if (CPEBB->empty()) { 1655 BBInfo[CPEBB->getNumber()].Size = 0; 1656 1657 // This block no longer needs to be aligned. 1658 CPEBB->setAlignment(Align(1)); 1659 } else { 1660 // Entries are sorted by descending alignment, so realign from the front. 1661 CPEBB->setAlignment(getCPEAlign(&*CPEBB->begin())); 1662 } 1663 1664 BBUtils->adjustBBOffsetsAfter(CPEBB); 1665 // An island has only one predecessor BB and one successor BB. Check if 1666 // this BB's predecessor jumps directly to this BB's successor. This 1667 // shouldn't happen currently. 1668 assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 1669 // FIXME: remove the empty blocks after all the work is done? 1670 } 1671 1672 /// removeUnusedCPEntries - Remove constant pool entries whose refcounts 1673 /// are zero. 1674 bool ARMConstantIslands::removeUnusedCPEntries() { 1675 unsigned MadeChange = false; 1676 for (std::vector<CPEntry> &CPEs : CPEntries) { 1677 for (CPEntry &CPE : CPEs) { 1678 if (CPE.RefCount == 0 && CPE.CPEMI) { 1679 removeDeadCPEMI(CPE.CPEMI); 1680 CPE.CPEMI = nullptr; 1681 MadeChange = true; 1682 } 1683 } 1684 } 1685 return MadeChange; 1686 } 1687 1688 1689 /// fixupImmediateBr - Fix up an immediate branch whose destination is too far 1690 /// away to fit in its displacement field. 1691 bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) { 1692 MachineInstr *MI = Br.MI; 1693 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1694 1695 // Check to see if the DestBB is already in-range. 1696 if (BBUtils->isBBInRange(MI, DestBB, Br.MaxDisp)) 1697 return false; 1698 1699 if (!Br.isCond) 1700 return fixupUnconditionalBr(Br); 1701 return fixupConditionalBr(Br); 1702 } 1703 1704 /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is 1705 /// too far away to fit in its displacement field. If the LR register has been 1706 /// spilled in the epilogue, then we can use BL to implement a far jump. 1707 /// Otherwise, add an intermediate branch instruction to a branch. 1708 bool 1709 ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) { 1710 MachineInstr *MI = Br.MI; 1711 MachineBasicBlock *MBB = MI->getParent(); 1712 if (!isThumb1) 1713 llvm_unreachable("fixupUnconditionalBr is Thumb1 only!"); 1714 1715 if (!AFI->isLRSpilled()) 1716 report_fatal_error("underestimated function size"); 1717 1718 // Use BL to implement far jump. 1719 Br.MaxDisp = (1 << 21) * 2; 1720 MI->setDesc(TII->get(ARM::tBfar)); 1721 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 1722 BBInfo[MBB->getNumber()].Size += 2; 1723 BBUtils->adjustBBOffsetsAfter(MBB); 1724 ++NumUBrFixed; 1725 1726 LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI); 1727 1728 return true; 1729 } 1730 1731 /// fixupConditionalBr - Fix up a conditional branch whose destination is too 1732 /// far away to fit in its displacement field. It is converted to an inverse 1733 /// conditional branch + an unconditional branch to the destination. 1734 bool 1735 ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) { 1736 MachineInstr *MI = Br.MI; 1737 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1738 1739 // Add an unconditional branch to the destination and invert the branch 1740 // condition to jump over it: 1741 // blt L1 1742 // => 1743 // bge L2 1744 // b L1 1745 // L2: 1746 ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm(); 1747 CC = ARMCC::getOppositeCondition(CC); 1748 Register CCReg = MI->getOperand(2).getReg(); 1749 1750 // If the branch is at the end of its MBB and that has a fall-through block, 1751 // direct the updated conditional branch to the fall-through block. Otherwise, 1752 // split the MBB before the next instruction. 1753 MachineBasicBlock *MBB = MI->getParent(); 1754 MachineInstr *BMI = &MBB->back(); 1755 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 1756 1757 ++NumCBrFixed; 1758 if (BMI != MI) { 1759 if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) && 1760 BMI->getOpcode() == Br.UncondBr) { 1761 // Last MI in the BB is an unconditional branch. Can we simply invert the 1762 // condition and swap destinations: 1763 // beq L1 1764 // b L2 1765 // => 1766 // bne L2 1767 // b L1 1768 MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); 1769 if (BBUtils->isBBInRange(MI, NewDest, Br.MaxDisp)) { 1770 LLVM_DEBUG( 1771 dbgs() << " Invert Bcc condition and swap its destination with " 1772 << *BMI); 1773 BMI->getOperand(0).setMBB(DestBB); 1774 MI->getOperand(0).setMBB(NewDest); 1775 MI->getOperand(1).setImm(CC); 1776 return true; 1777 } 1778 } 1779 } 1780 1781 if (NeedSplit) { 1782 splitBlockBeforeInstr(MI); 1783 // No need for the branch to the next block. We're adding an unconditional 1784 // branch to the destination. 1785 int delta = TII->getInstSizeInBytes(MBB->back()); 1786 BBUtils->adjustBBSize(MBB, -delta); 1787 MBB->back().eraseFromParent(); 1788 1789 // The conditional successor will be swapped between the BBs after this, so 1790 // update CFG. 1791 MBB->addSuccessor(DestBB); 1792 std::next(MBB->getIterator())->removeSuccessor(DestBB); 1793 1794 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below 1795 } 1796 MachineBasicBlock *NextBB = &*++MBB->getIterator(); 1797 1798 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB) 1799 << " also invert condition and change dest. to " 1800 << printMBBReference(*NextBB) << "\n"); 1801 1802 // Insert a new conditional branch and a new unconditional branch. 1803 // Also update the ImmBranch as well as adding a new entry for the new branch. 1804 BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode())) 1805 .addMBB(NextBB).addImm(CC).addReg(CCReg); 1806 Br.MI = &MBB->back(); 1807 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back())); 1808 if (isThumb) 1809 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)) 1810 .addMBB(DestBB) 1811 .add(predOps(ARMCC::AL)); 1812 else 1813 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); 1814 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back())); 1815 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1816 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 1817 1818 // Remove the old conditional branch. It may or may not still be in MBB. 1819 BBUtils->adjustBBSize(MI->getParent(), -TII->getInstSizeInBytes(*MI)); 1820 MI->eraseFromParent(); 1821 BBUtils->adjustBBOffsetsAfter(MBB); 1822 return true; 1823 } 1824 1825 bool ARMConstantIslands::optimizeThumb2Instructions() { 1826 bool MadeChange = false; 1827 1828 // Shrink ADR and LDR from constantpool. 1829 for (CPUser &U : CPUsers) { 1830 unsigned Opcode = U.MI->getOpcode(); 1831 unsigned NewOpc = 0; 1832 unsigned Scale = 1; 1833 unsigned Bits = 0; 1834 switch (Opcode) { 1835 default: break; 1836 case ARM::t2LEApcrel: 1837 if (isARMLowRegister(U.MI->getOperand(0).getReg())) { 1838 NewOpc = ARM::tLEApcrel; 1839 Bits = 8; 1840 Scale = 4; 1841 } 1842 break; 1843 case ARM::t2LDRpci: 1844 if (isARMLowRegister(U.MI->getOperand(0).getReg())) { 1845 NewOpc = ARM::tLDRpci; 1846 Bits = 8; 1847 Scale = 4; 1848 } 1849 break; 1850 } 1851 1852 if (!NewOpc) 1853 continue; 1854 1855 unsigned UserOffset = getUserOffset(U); 1856 unsigned MaxOffs = ((1 << Bits) - 1) * Scale; 1857 1858 // Be conservative with inline asm. 1859 if (!U.KnownAlignment) 1860 MaxOffs -= 2; 1861 1862 // FIXME: Check if offset is multiple of scale if scale is not 4. 1863 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) { 1864 LLVM_DEBUG(dbgs() << "Shrink: " << *U.MI); 1865 U.MI->setDesc(TII->get(NewOpc)); 1866 MachineBasicBlock *MBB = U.MI->getParent(); 1867 BBUtils->adjustBBSize(MBB, -2); 1868 BBUtils->adjustBBOffsetsAfter(MBB); 1869 ++NumT2CPShrunk; 1870 MadeChange = true; 1871 } 1872 } 1873 1874 return MadeChange; 1875 } 1876 1877 1878 bool ARMConstantIslands::optimizeThumb2Branches() { 1879 1880 auto TryShrinkBranch = [this](ImmBranch &Br) { 1881 unsigned Opcode = Br.MI->getOpcode(); 1882 unsigned NewOpc = 0; 1883 unsigned Scale = 1; 1884 unsigned Bits = 0; 1885 switch (Opcode) { 1886 default: break; 1887 case ARM::t2B: 1888 NewOpc = ARM::tB; 1889 Bits = 11; 1890 Scale = 2; 1891 break; 1892 case ARM::t2Bcc: 1893 NewOpc = ARM::tBcc; 1894 Bits = 8; 1895 Scale = 2; 1896 break; 1897 } 1898 if (NewOpc) { 1899 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 1900 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); 1901 if (BBUtils->isBBInRange(Br.MI, DestBB, MaxOffs)) { 1902 LLVM_DEBUG(dbgs() << "Shrink branch: " << *Br.MI); 1903 Br.MI->setDesc(TII->get(NewOpc)); 1904 MachineBasicBlock *MBB = Br.MI->getParent(); 1905 BBUtils->adjustBBSize(MBB, -2); 1906 BBUtils->adjustBBOffsetsAfter(MBB); 1907 ++NumT2BrShrunk; 1908 return true; 1909 } 1910 } 1911 return false; 1912 }; 1913 1914 struct ImmCompare { 1915 MachineInstr* MI = nullptr; 1916 unsigned NewOpc = 0; 1917 }; 1918 1919 auto FindCmpForCBZ = [this](ImmBranch &Br, ImmCompare &ImmCmp, 1920 MachineBasicBlock *DestBB) { 1921 ImmCmp.MI = nullptr; 1922 ImmCmp.NewOpc = 0; 1923 1924 // If the conditional branch doesn't kill CPSR, then CPSR can be liveout 1925 // so this transformation is not safe. 1926 if (!Br.MI->killsRegister(ARM::CPSR)) 1927 return false; 1928 1929 Register PredReg; 1930 unsigned NewOpc = 0; 1931 ARMCC::CondCodes Pred = getInstrPredicate(*Br.MI, PredReg); 1932 if (Pred == ARMCC::EQ) 1933 NewOpc = ARM::tCBZ; 1934 else if (Pred == ARMCC::NE) 1935 NewOpc = ARM::tCBNZ; 1936 else 1937 return false; 1938 1939 // Check if the distance is within 126. Subtract starting offset by 2 1940 // because the cmp will be eliminated. 1941 unsigned BrOffset = BBUtils->getOffsetOf(Br.MI) + 4 - 2; 1942 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 1943 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset; 1944 if (BrOffset >= DestOffset || (DestOffset - BrOffset) > 126) 1945 return false; 1946 1947 // Search backwards to find a tCMPi8 1948 auto *TRI = STI->getRegisterInfo(); 1949 MachineInstr *CmpMI = findCMPToFoldIntoCBZ(Br.MI, TRI); 1950 if (!CmpMI || CmpMI->getOpcode() != ARM::tCMPi8) 1951 return false; 1952 1953 ImmCmp.MI = CmpMI; 1954 ImmCmp.NewOpc = NewOpc; 1955 return true; 1956 }; 1957 1958 auto TryConvertToLE = [this](ImmBranch &Br, ImmCompare &Cmp) { 1959 if (Br.MI->getOpcode() != ARM::t2Bcc || !STI->hasLOB() || 1960 STI->hasMinSize()) 1961 return false; 1962 1963 MachineBasicBlock *MBB = Br.MI->getParent(); 1964 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); 1965 if (BBUtils->getOffsetOf(MBB) < BBUtils->getOffsetOf(DestBB) || 1966 !BBUtils->isBBInRange(Br.MI, DestBB, 4094)) 1967 return false; 1968 1969 if (!DT->dominates(DestBB, MBB)) 1970 return false; 1971 1972 // We queried for the CBN?Z opcode based upon the 'ExitBB', the opposite 1973 // target of Br. So now we need to reverse the condition. 1974 Cmp.NewOpc = Cmp.NewOpc == ARM::tCBZ ? ARM::tCBNZ : ARM::tCBZ; 1975 1976 MachineInstrBuilder MIB = BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), 1977 TII->get(ARM::t2LE)); 1978 // Swapped a t2Bcc for a t2LE, so no need to update the size of the block. 1979 MIB.add(Br.MI->getOperand(0)); 1980 Br.MI->eraseFromParent(); 1981 Br.MI = MIB; 1982 ++NumLEInserted; 1983 return true; 1984 }; 1985 1986 bool MadeChange = false; 1987 1988 // The order in which branches appear in ImmBranches is approximately their 1989 // order within the function body. By visiting later branches first, we reduce 1990 // the distance between earlier forward branches and their targets, making it 1991 // more likely that the cbn?z optimization, which can only apply to forward 1992 // branches, will succeed. 1993 for (ImmBranch &Br : reverse(ImmBranches)) { 1994 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB(); 1995 MachineBasicBlock *MBB = Br.MI->getParent(); 1996 MachineBasicBlock *ExitBB = &MBB->back() == Br.MI ? 1997 MBB->getFallThrough() : 1998 MBB->back().getOperand(0).getMBB(); 1999 2000 ImmCompare Cmp; 2001 if (FindCmpForCBZ(Br, Cmp, ExitBB) && TryConvertToLE(Br, Cmp)) { 2002 DestBB = ExitBB; 2003 MadeChange = true; 2004 } else { 2005 FindCmpForCBZ(Br, Cmp, DestBB); 2006 MadeChange |= TryShrinkBranch(Br); 2007 } 2008 2009 unsigned Opcode = Br.MI->getOpcode(); 2010 if ((Opcode != ARM::tBcc && Opcode != ARM::t2LE) || !Cmp.NewOpc) 2011 continue; 2012 2013 Register Reg = Cmp.MI->getOperand(0).getReg(); 2014 2015 // Check for Kill flags on Reg. If they are present remove them and set kill 2016 // on the new CBZ. 2017 auto *TRI = STI->getRegisterInfo(); 2018 MachineBasicBlock::iterator KillMI = Br.MI; 2019 bool RegKilled = false; 2020 do { 2021 --KillMI; 2022 if (KillMI->killsRegister(Reg, TRI)) { 2023 KillMI->clearRegisterKills(Reg, TRI); 2024 RegKilled = true; 2025 break; 2026 } 2027 } while (KillMI != Cmp.MI); 2028 2029 // Create the new CBZ/CBNZ 2030 LLVM_DEBUG(dbgs() << "Fold: " << *Cmp.MI << " and: " << *Br.MI); 2031 MachineInstr *NewBR = 2032 BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), TII->get(Cmp.NewOpc)) 2033 .addReg(Reg, getKillRegState(RegKilled) | 2034 getRegState(Cmp.MI->getOperand(0))) 2035 .addMBB(DestBB, Br.MI->getOperand(0).getTargetFlags()); 2036 2037 Cmp.MI->eraseFromParent(); 2038 2039 if (Br.MI->getOpcode() == ARM::tBcc) { 2040 Br.MI->eraseFromParent(); 2041 Br.MI = NewBR; 2042 BBUtils->adjustBBSize(MBB, -2); 2043 } else if (MBB->back().getOpcode() != ARM::t2LE) { 2044 // An LE has been generated, but it's not the terminator - that is an 2045 // unconditional branch. However, the logic has now been reversed with the 2046 // CBN?Z being the conditional branch and the LE being the unconditional 2047 // branch. So this means we can remove the redundant unconditional branch 2048 // at the end of the block. 2049 MachineInstr *LastMI = &MBB->back(); 2050 BBUtils->adjustBBSize(MBB, -LastMI->getDesc().getSize()); 2051 LastMI->eraseFromParent(); 2052 } 2053 BBUtils->adjustBBOffsetsAfter(MBB); 2054 ++NumCBZ; 2055 MadeChange = true; 2056 } 2057 2058 return MadeChange; 2059 } 2060 2061 static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg, 2062 unsigned BaseReg) { 2063 if (I.getOpcode() != ARM::t2ADDrs) 2064 return false; 2065 2066 if (I.getOperand(0).getReg() != EntryReg) 2067 return false; 2068 2069 if (I.getOperand(1).getReg() != BaseReg) 2070 return false; 2071 2072 // FIXME: what about CC and IdxReg? 2073 return true; 2074 } 2075 2076 /// While trying to form a TBB/TBH instruction, we may (if the table 2077 /// doesn't immediately follow the BR_JT) need access to the start of the 2078 /// jump-table. We know one instruction that produces such a register; this 2079 /// function works out whether that definition can be preserved to the BR_JT, 2080 /// possibly by removing an intervening addition (which is usually needed to 2081 /// calculate the actual entry to jump to). 2082 bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI, 2083 MachineInstr *LEAMI, 2084 unsigned &DeadSize, 2085 bool &CanDeleteLEA, 2086 bool &BaseRegKill) { 2087 if (JumpMI->getParent() != LEAMI->getParent()) 2088 return false; 2089 2090 // Now we hope that we have at least these instructions in the basic block: 2091 // BaseReg = t2LEA ... 2092 // [...] 2093 // EntryReg = t2ADDrs BaseReg, ... 2094 // [...] 2095 // t2BR_JT EntryReg 2096 // 2097 // We have to be very conservative about what we recognise here though. The 2098 // main perturbing factors to watch out for are: 2099 // + Spills at any point in the chain: not direct problems but we would 2100 // expect a blocking Def of the spilled register so in practice what we 2101 // can do is limited. 2102 // + EntryReg == BaseReg: this is the one situation we should allow a Def 2103 // of BaseReg, but only if the t2ADDrs can be removed. 2104 // + Some instruction other than t2ADDrs computing the entry. Not seen in 2105 // the wild, but we should be careful. 2106 Register EntryReg = JumpMI->getOperand(0).getReg(); 2107 Register BaseReg = LEAMI->getOperand(0).getReg(); 2108 2109 CanDeleteLEA = true; 2110 BaseRegKill = false; 2111 MachineInstr *RemovableAdd = nullptr; 2112 MachineBasicBlock::iterator I(LEAMI); 2113 for (++I; &*I != JumpMI; ++I) { 2114 if (isSimpleIndexCalc(*I, EntryReg, BaseReg)) { 2115 RemovableAdd = &*I; 2116 break; 2117 } 2118 2119 for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) { 2120 const MachineOperand &MO = I->getOperand(K); 2121 if (!MO.isReg() || !MO.getReg()) 2122 continue; 2123 if (MO.isDef() && MO.getReg() == BaseReg) 2124 return false; 2125 if (MO.isUse() && MO.getReg() == BaseReg) { 2126 BaseRegKill = BaseRegKill || MO.isKill(); 2127 CanDeleteLEA = false; 2128 } 2129 } 2130 } 2131 2132 if (!RemovableAdd) 2133 return true; 2134 2135 // Check the add really is removable, and that nothing else in the block 2136 // clobbers BaseReg. 2137 for (++I; &*I != JumpMI; ++I) { 2138 for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) { 2139 const MachineOperand &MO = I->getOperand(K); 2140 if (!MO.isReg() || !MO.getReg()) 2141 continue; 2142 if (MO.isDef() && MO.getReg() == BaseReg) 2143 return false; 2144 if (MO.isUse() && MO.getReg() == EntryReg) 2145 RemovableAdd = nullptr; 2146 } 2147 } 2148 2149 if (RemovableAdd) { 2150 RemovableAdd->eraseFromParent(); 2151 DeadSize += isThumb2 ? 4 : 2; 2152 } else if (BaseReg == EntryReg) { 2153 // The add wasn't removable, but clobbered the base for the TBB. So we can't 2154 // preserve it. 2155 return false; 2156 } 2157 2158 // We reached the end of the block without seeing another definition of 2159 // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be 2160 // used in the TBB/TBH if necessary. 2161 return true; 2162 } 2163 2164 /// Returns whether CPEMI is the first instruction in the block 2165 /// immediately following JTMI (assumed to be a TBB or TBH terminator). If so, 2166 /// we can switch the first register to PC and usually remove the address 2167 /// calculation that preceded it. 2168 static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) { 2169 MachineFunction::iterator MBB = JTMI->getParent()->getIterator(); 2170 MachineFunction *MF = MBB->getParent(); 2171 ++MBB; 2172 2173 return MBB != MF->end() && !MBB->empty() && &*MBB->begin() == CPEMI; 2174 } 2175 2176 static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI, 2177 MachineInstr *JumpMI, 2178 unsigned &DeadSize) { 2179 // Remove a dead add between the LEA and JT, which used to compute EntryReg, 2180 // but the JT now uses PC. Finds the last ADD (if any) that def's EntryReg 2181 // and is not clobbered / used. 2182 MachineInstr *RemovableAdd = nullptr; 2183 Register EntryReg = JumpMI->getOperand(0).getReg(); 2184 2185 // Find the last ADD to set EntryReg 2186 MachineBasicBlock::iterator I(LEAMI); 2187 for (++I; &*I != JumpMI; ++I) { 2188 if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg) 2189 RemovableAdd = &*I; 2190 } 2191 2192 if (!RemovableAdd) 2193 return; 2194 2195 // Ensure EntryReg is not clobbered or used. 2196 MachineBasicBlock::iterator J(RemovableAdd); 2197 for (++J; &*J != JumpMI; ++J) { 2198 for (unsigned K = 0, E = J->getNumOperands(); K != E; ++K) { 2199 const MachineOperand &MO = J->getOperand(K); 2200 if (!MO.isReg() || !MO.getReg()) 2201 continue; 2202 if (MO.isDef() && MO.getReg() == EntryReg) 2203 return; 2204 if (MO.isUse() && MO.getReg() == EntryReg) 2205 return; 2206 } 2207 } 2208 2209 LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd); 2210 RemovableAdd->eraseFromParent(); 2211 DeadSize += 4; 2212 } 2213 2214 /// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller 2215 /// jumptables when it's possible. 2216 bool ARMConstantIslands::optimizeThumb2JumpTables() { 2217 bool MadeChange = false; 2218 2219 // FIXME: After the tables are shrunk, can we get rid some of the 2220 // constantpool tables? 2221 MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); 2222 if (!MJTI) return false; 2223 2224 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); 2225 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { 2226 MachineInstr *MI = T2JumpTables[i]; 2227 const MCInstrDesc &MCID = MI->getDesc(); 2228 unsigned NumOps = MCID.getNumOperands(); 2229 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1); 2230 MachineOperand JTOP = MI->getOperand(JTOpIdx); 2231 unsigned JTI = JTOP.getIndex(); 2232 assert(JTI < JT.size()); 2233 2234 bool ByteOk = true; 2235 bool HalfWordOk = true; 2236 unsigned JTOffset = BBUtils->getOffsetOf(MI) + 4; 2237 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; 2238 BBInfoVector &BBInfo = BBUtils->getBBInfo(); 2239 for (MachineBasicBlock *MBB : JTBBs) { 2240 unsigned DstOffset = BBInfo[MBB->getNumber()].Offset; 2241 // Negative offset is not ok. FIXME: We should change BB layout to make 2242 // sure all the branches are forward. 2243 if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2) 2244 ByteOk = false; 2245 unsigned TBHLimit = ((1<<16)-1)*2; 2246 if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit) 2247 HalfWordOk = false; 2248 if (!ByteOk && !HalfWordOk) 2249 break; 2250 } 2251 2252 if (!ByteOk && !HalfWordOk) 2253 continue; 2254 2255 CPUser &User = CPUsers[JumpTableUserIndices[JTI]]; 2256 MachineBasicBlock *MBB = MI->getParent(); 2257 if (!MI->getOperand(0).isKill()) // FIXME: needed now? 2258 continue; 2259 2260 unsigned DeadSize = 0; 2261 bool CanDeleteLEA = false; 2262 bool BaseRegKill = false; 2263 2264 unsigned IdxReg = ~0U; 2265 bool IdxRegKill = true; 2266 if (isThumb2) { 2267 IdxReg = MI->getOperand(1).getReg(); 2268 IdxRegKill = MI->getOperand(1).isKill(); 2269 2270 bool PreservedBaseReg = 2271 preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill); 2272 if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg) 2273 continue; 2274 } else { 2275 // We're in thumb-1 mode, so we must have something like: 2276 // %idx = tLSLri %idx, 2 2277 // %base = tLEApcrelJT 2278 // %t = tLDRr %base, %idx 2279 Register BaseReg = User.MI->getOperand(0).getReg(); 2280 2281 if (User.MI->getIterator() == User.MI->getParent()->begin()) 2282 continue; 2283 MachineInstr *Shift = User.MI->getPrevNode(); 2284 if (Shift->getOpcode() != ARM::tLSLri || 2285 Shift->getOperand(3).getImm() != 2 || 2286 !Shift->getOperand(2).isKill()) 2287 continue; 2288 IdxReg = Shift->getOperand(2).getReg(); 2289 Register ShiftedIdxReg = Shift->getOperand(0).getReg(); 2290 2291 // It's important that IdxReg is live until the actual TBB/TBH. Most of 2292 // the range is checked later, but the LEA might still clobber it and not 2293 // actually get removed. 2294 if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI)) 2295 continue; 2296 2297 MachineInstr *Load = User.MI->getNextNode(); 2298 if (Load->getOpcode() != ARM::tLDRr) 2299 continue; 2300 if (Load->getOperand(1).getReg() != BaseReg || 2301 Load->getOperand(2).getReg() != ShiftedIdxReg || 2302 !Load->getOperand(2).isKill()) 2303 continue; 2304 2305 // If we're in PIC mode, there should be another ADD following. 2306 auto *TRI = STI->getRegisterInfo(); 2307 2308 // %base cannot be redefined after the load as it will appear before 2309 // TBB/TBH like: 2310 // %base = 2311 // %base = 2312 // tBB %base, %idx 2313 if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI)) 2314 continue; 2315 2316 if (isPositionIndependentOrROPI) { 2317 MachineInstr *Add = Load->getNextNode(); 2318 if (Add->getOpcode() != ARM::tADDrr || 2319 Add->getOperand(2).getReg() != BaseReg || 2320 Add->getOperand(3).getReg() != Load->getOperand(0).getReg() || 2321 !Add->getOperand(3).isKill()) 2322 continue; 2323 if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg()) 2324 continue; 2325 if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI)) 2326 // IdxReg gets redefined in the middle of the sequence. 2327 continue; 2328 Add->eraseFromParent(); 2329 DeadSize += 2; 2330 } else { 2331 if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg()) 2332 continue; 2333 if (registerDefinedBetween(IdxReg, Load->getNextNode(), MI, TRI)) 2334 // IdxReg gets redefined in the middle of the sequence. 2335 continue; 2336 } 2337 2338 // Now safe to delete the load and lsl. The LEA will be removed later. 2339 CanDeleteLEA = true; 2340 Shift->eraseFromParent(); 2341 Load->eraseFromParent(); 2342 DeadSize += 4; 2343 } 2344 2345 LLVM_DEBUG(dbgs() << "Shrink JT: " << *MI); 2346 MachineInstr *CPEMI = User.CPEMI; 2347 unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT; 2348 if (!isThumb2) 2349 Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT; 2350 2351 MachineBasicBlock::iterator MI_JT = MI; 2352 MachineInstr *NewJTMI = 2353 BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc)) 2354 .addReg(User.MI->getOperand(0).getReg(), 2355 getKillRegState(BaseRegKill)) 2356 .addReg(IdxReg, getKillRegState(IdxRegKill)) 2357 .addJumpTableIndex(JTI, JTOP.getTargetFlags()) 2358 .addImm(CPEMI->getOperand(0).getImm()); 2359 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI); 2360 2361 unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH; 2362 CPEMI->setDesc(TII->get(JTOpc)); 2363 2364 if (jumpTableFollowsTB(MI, User.CPEMI)) { 2365 NewJTMI->getOperand(0).setReg(ARM::PC); 2366 NewJTMI->getOperand(0).setIsKill(false); 2367 2368 if (CanDeleteLEA) { 2369 if (isThumb2) 2370 RemoveDeadAddBetweenLEAAndJT(User.MI, MI, DeadSize); 2371 2372 User.MI->eraseFromParent(); 2373 DeadSize += isThumb2 ? 4 : 2; 2374 2375 // The LEA was eliminated, the TBB instruction becomes the only new user 2376 // of the jump table. 2377 User.MI = NewJTMI; 2378 User.MaxDisp = 4; 2379 User.NegOk = false; 2380 User.IsSoImm = false; 2381 User.KnownAlignment = false; 2382 } else { 2383 // The LEA couldn't be eliminated, so we must add another CPUser to 2384 // record the TBB or TBH use. 2385 int CPEntryIdx = JumpTableEntryIndices[JTI]; 2386 auto &CPEs = CPEntries[CPEntryIdx]; 2387 auto Entry = 2388 find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; }); 2389 ++Entry->RefCount; 2390 CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false)); 2391 } 2392 } 2393 2394 unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI); 2395 unsigned OrigSize = TII->getInstSizeInBytes(*MI); 2396 MI->eraseFromParent(); 2397 2398 int Delta = OrigSize - NewSize + DeadSize; 2399 BBInfo[MBB->getNumber()].Size -= Delta; 2400 BBUtils->adjustBBOffsetsAfter(MBB); 2401 2402 ++NumTBs; 2403 MadeChange = true; 2404 } 2405 2406 return MadeChange; 2407 } 2408 2409 /// reorderThumb2JumpTables - Adjust the function's block layout to ensure that 2410 /// jump tables always branch forwards, since that's what tbb and tbh need. 2411 bool ARMConstantIslands::reorderThumb2JumpTables() { 2412 bool MadeChange = false; 2413 2414 MachineJumpTableInfo *MJTI = MF->getJumpTableInfo(); 2415 if (!MJTI) return false; 2416 2417 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables(); 2418 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) { 2419 MachineInstr *MI = T2JumpTables[i]; 2420 const MCInstrDesc &MCID = MI->getDesc(); 2421 unsigned NumOps = MCID.getNumOperands(); 2422 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1); 2423 MachineOperand JTOP = MI->getOperand(JTOpIdx); 2424 unsigned JTI = JTOP.getIndex(); 2425 assert(JTI < JT.size()); 2426 2427 // We prefer if target blocks for the jump table come after the jump 2428 // instruction so we can use TB[BH]. Loop through the target blocks 2429 // and try to adjust them such that that's true. 2430 int JTNumber = MI->getParent()->getNumber(); 2431 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs; 2432 for (MachineBasicBlock *MBB : JTBBs) { 2433 int DTNumber = MBB->getNumber(); 2434 2435 if (DTNumber < JTNumber) { 2436 // The destination precedes the switch. Try to move the block forward 2437 // so we have a positive offset. 2438 MachineBasicBlock *NewBB = 2439 adjustJTTargetBlockForward(JTI, MBB, MI->getParent()); 2440 if (NewBB) 2441 MJTI->ReplaceMBBInJumpTable(JTI, MBB, NewBB); 2442 MadeChange = true; 2443 } 2444 } 2445 } 2446 2447 return MadeChange; 2448 } 2449 2450 void ARMConstantIslands::fixupBTI(unsigned JTI, MachineBasicBlock &OldBB, 2451 MachineBasicBlock &NewBB) { 2452 assert(isThumb2 && "BTI in Thumb1?"); 2453 2454 // Insert a BTI instruction into NewBB 2455 BuildMI(NewBB, NewBB.begin(), DebugLoc(), TII->get(ARM::t2BTI)); 2456 2457 // Update jump table reference counts. 2458 const MachineJumpTableInfo &MJTI = *MF->getJumpTableInfo(); 2459 const MachineJumpTableEntry &JTE = MJTI.getJumpTables()[JTI]; 2460 for (const MachineBasicBlock *MBB : JTE.MBBs) { 2461 if (MBB != &OldBB) 2462 continue; 2463 --BlockJumpTableRefCount[MBB]; 2464 ++BlockJumpTableRefCount[&NewBB]; 2465 } 2466 2467 // If the old basic block reference count dropped to zero, remove 2468 // the BTI instruction at its beginning. 2469 if (BlockJumpTableRefCount[&OldBB] > 0) 2470 return; 2471 2472 // Skip meta instructions 2473 auto BTIPos = llvm::find_if_not(OldBB.instrs(), [](const MachineInstr &MI) { 2474 return MI.isMetaInstruction(); 2475 }); 2476 assert(BTIPos->getOpcode() == ARM::t2BTI && 2477 "BasicBlock is mentioned in a jump table but does start with BTI"); 2478 if (BTIPos->getOpcode() == ARM::t2BTI) 2479 BTIPos->eraseFromParent(); 2480 } 2481 2482 MachineBasicBlock *ARMConstantIslands::adjustJTTargetBlockForward( 2483 unsigned JTI, MachineBasicBlock *BB, MachineBasicBlock *JTBB) { 2484 // If the destination block is terminated by an unconditional branch, 2485 // try to move it; otherwise, create a new block following the jump 2486 // table that branches back to the actual target. This is a very simple 2487 // heuristic. FIXME: We can definitely improve it. 2488 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 2489 SmallVector<MachineOperand, 4> Cond; 2490 SmallVector<MachineOperand, 4> CondPrior; 2491 MachineFunction::iterator BBi = BB->getIterator(); 2492 MachineFunction::iterator OldPrior = std::prev(BBi); 2493 MachineFunction::iterator OldNext = std::next(BBi); 2494 2495 // If the block terminator isn't analyzable, don't try to move the block 2496 bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond); 2497 2498 // If the block ends in an unconditional branch, move it. The prior block 2499 // has to have an analyzable terminator for us to move this one. Be paranoid 2500 // and make sure we're not trying to move the entry block of the function. 2501 if (!B && Cond.empty() && BB != &MF->front() && 2502 !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) { 2503 BB->moveAfter(JTBB); 2504 OldPrior->updateTerminator(BB); 2505 BB->updateTerminator(OldNext != MF->end() ? &*OldNext : nullptr); 2506 // Update numbering to account for the block being moved. 2507 MF->RenumberBlocks(); 2508 ++NumJTMoved; 2509 return nullptr; 2510 } 2511 2512 // Create a new MBB for the code after the jump BB. 2513 MachineBasicBlock *NewBB = 2514 MF->CreateMachineBasicBlock(JTBB->getBasicBlock()); 2515 MachineFunction::iterator MBBI = ++JTBB->getIterator(); 2516 MF->insert(MBBI, NewBB); 2517 2518 // Copy live-in information to new block. 2519 for (const MachineBasicBlock::RegisterMaskPair &RegMaskPair : BB->liveins()) 2520 NewBB->addLiveIn(RegMaskPair); 2521 2522 // Add an unconditional branch from NewBB to BB. 2523 // There doesn't seem to be meaningful DebugInfo available; this doesn't 2524 // correspond directly to anything in the source. 2525 if (isThumb2) 2526 BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B)) 2527 .addMBB(BB) 2528 .add(predOps(ARMCC::AL)); 2529 else 2530 BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB)) 2531 .addMBB(BB) 2532 .add(predOps(ARMCC::AL)); 2533 2534 // Update internal data structures to account for the newly inserted MBB. 2535 MF->RenumberBlocks(NewBB); 2536 2537 // Update the CFG. 2538 NewBB->addSuccessor(BB); 2539 JTBB->replaceSuccessor(BB, NewBB); 2540 2541 if (MF->getInfo<ARMFunctionInfo>()->branchTargetEnforcement()) 2542 fixupBTI(JTI, *BB, *NewBB); 2543 2544 ++NumJTInserted; 2545 return NewBB; 2546 } 2547 2548 /// createARMConstantIslandPass - returns an instance of the constpool 2549 /// island pass. 2550 FunctionPass *llvm::createARMConstantIslandPass() { 2551 return new ARMConstantIslands(); 2552 } 2553 2554 INITIALIZE_PASS(ARMConstantIslands, "arm-cp-islands", ARM_CP_ISLANDS_OPT_NAME, 2555 false, false) 2556