1 //===- BranchRelaxation.cpp -----------------------------------------------===// 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 #include "llvm/ADT/SmallVector.h" 10 #include "llvm/ADT/Statistic.h" 11 #include "llvm/CodeGen/LivePhysRegs.h" 12 #include "llvm/CodeGen/MachineBasicBlock.h" 13 #include "llvm/CodeGen/MachineFunction.h" 14 #include "llvm/CodeGen/MachineFunctionPass.h" 15 #include "llvm/CodeGen/MachineInstr.h" 16 #include "llvm/CodeGen/RegisterScavenging.h" 17 #include "llvm/CodeGen/TargetInstrInfo.h" 18 #include "llvm/CodeGen/TargetRegisterInfo.h" 19 #include "llvm/CodeGen/TargetSubtargetInfo.h" 20 #include "llvm/Config/llvm-config.h" 21 #include "llvm/IR/DebugLoc.h" 22 #include "llvm/InitializePasses.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Support/Compiler.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/Format.h" 27 #include "llvm/Support/MathExtras.h" 28 #include "llvm/Support/raw_ostream.h" 29 #include <cassert> 30 #include <cstdint> 31 #include <iterator> 32 #include <memory> 33 34 using namespace llvm; 35 36 #define DEBUG_TYPE "branch-relaxation" 37 38 STATISTIC(NumSplit, "Number of basic blocks split"); 39 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed"); 40 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed"); 41 42 #define BRANCH_RELAX_NAME "Branch relaxation pass" 43 44 namespace { 45 46 class BranchRelaxation : public MachineFunctionPass { 47 /// BasicBlockInfo - Information about the offset and size of a single 48 /// basic block. 49 struct BasicBlockInfo { 50 /// Offset - Distance from the beginning of the function to the beginning 51 /// of this basic block. 52 /// 53 /// The offset is always aligned as required by the basic block. 54 unsigned Offset = 0; 55 56 /// Size - Size of the basic block in bytes. If the block contains 57 /// inline assembly, this is a worst case estimate. 58 /// 59 /// The size does not include any alignment padding whether from the 60 /// beginning of the block, or from an aligned jump table at the end. 61 unsigned Size = 0; 62 63 BasicBlockInfo() = default; 64 65 /// Compute the offset immediately following this block. \p MBB is the next 66 /// block. 67 unsigned postOffset(const MachineBasicBlock &MBB) const { 68 const unsigned PO = Offset + Size; 69 const Align Alignment = MBB.getAlignment(); 70 const Align ParentAlign = MBB.getParent()->getAlignment(); 71 if (Alignment <= ParentAlign) 72 return alignTo(PO, Alignment); 73 74 // The alignment of this MBB is larger than the function's alignment, so we 75 // can't tell whether or not it will insert nops. Assume that it will. 76 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value(); 77 } 78 }; 79 80 SmallVector<BasicBlockInfo, 16> BlockInfo; 81 std::unique_ptr<RegScavenger> RS; 82 LivePhysRegs LiveRegs; 83 84 MachineFunction *MF; 85 const TargetRegisterInfo *TRI; 86 const TargetInstrInfo *TII; 87 88 bool relaxBranchInstructions(); 89 void scanFunction(); 90 91 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB); 92 93 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI, 94 MachineBasicBlock *DestBB); 95 void adjustBlockOffsets(MachineBasicBlock &Start); 96 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const; 97 98 bool fixupConditionalBranch(MachineInstr &MI); 99 bool fixupUnconditionalBranch(MachineInstr &MI); 100 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const; 101 unsigned getInstrOffset(const MachineInstr &MI) const; 102 void dumpBBs(); 103 void verify(); 104 105 public: 106 static char ID; 107 108 BranchRelaxation() : MachineFunctionPass(ID) {} 109 110 bool runOnMachineFunction(MachineFunction &MF) override; 111 112 StringRef getPassName() const override { return BRANCH_RELAX_NAME; } 113 }; 114 115 } // end anonymous namespace 116 117 char BranchRelaxation::ID = 0; 118 119 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID; 120 121 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false) 122 123 /// verify - check BBOffsets, BBSizes, alignment of islands 124 void BranchRelaxation::verify() { 125 #ifndef NDEBUG 126 unsigned PrevNum = MF->begin()->getNumber(); 127 for (MachineBasicBlock &MBB : *MF) { 128 const unsigned Num = MBB.getNumber(); 129 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset); 130 assert(BlockInfo[Num].Size == computeBlockSize(MBB)); 131 PrevNum = Num; 132 } 133 #endif 134 } 135 136 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 137 /// print block size and offset information - debugging 138 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() { 139 for (auto &MBB : *MF) { 140 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()]; 141 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset) 142 << format("size=%#x\n", BBI.Size); 143 } 144 } 145 #endif 146 147 /// scanFunction - Do the initial scan of the function, building up 148 /// information about each block. 149 void BranchRelaxation::scanFunction() { 150 BlockInfo.clear(); 151 BlockInfo.resize(MF->getNumBlockIDs()); 152 153 // First thing, compute the size of all basic blocks, and see if the function 154 // has any inline assembly in it. If so, we have to be conservative about 155 // alignment assumptions, as we don't know for sure the size of any 156 // instructions in the inline assembly. 157 for (MachineBasicBlock &MBB : *MF) 158 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB); 159 160 // Compute block offsets and known bits. 161 adjustBlockOffsets(*MF->begin()); 162 } 163 164 /// computeBlockSize - Compute the size for MBB. 165 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const { 166 uint64_t Size = 0; 167 for (const MachineInstr &MI : MBB) 168 Size += TII->getInstSizeInBytes(MI); 169 return Size; 170 } 171 172 /// getInstrOffset - Return the current offset of the specified machine 173 /// instruction from the start of the function. This offset changes as stuff is 174 /// moved around inside the function. 175 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const { 176 const MachineBasicBlock *MBB = MI.getParent(); 177 178 // The offset is composed of two things: the sum of the sizes of all MBB's 179 // before this instruction's block, and the offset from the start of the block 180 // it is in. 181 unsigned Offset = BlockInfo[MBB->getNumber()].Offset; 182 183 // Sum instructions before MI in MBB. 184 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) { 185 assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 186 Offset += TII->getInstSizeInBytes(*I); 187 } 188 189 return Offset; 190 } 191 192 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) { 193 unsigned PrevNum = Start.getNumber(); 194 for (auto &MBB : 195 make_range(std::next(MachineFunction::iterator(Start)), MF->end())) { 196 unsigned Num = MBB.getNumber(); 197 // Get the offset and known bits at the end of the layout predecessor. 198 // Include the alignment of the current block. 199 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB); 200 201 PrevNum = Num; 202 } 203 } 204 205 /// Insert a new empty basic block and insert it after \BB 206 MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) { 207 // Create a new MBB for the code after the OrigBB. 208 MachineBasicBlock *NewBB = 209 MF->CreateMachineBasicBlock(BB.getBasicBlock()); 210 MF->insert(++BB.getIterator(), NewBB); 211 212 // Insert an entry into BlockInfo to align it properly with the block numbers. 213 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo()); 214 215 return NewBB; 216 } 217 218 /// Split the basic block containing MI into two blocks, which are joined by 219 /// an unconditional branch. Update data structures and renumber blocks to 220 /// account for this change and returns the newly created block. 221 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI, 222 MachineBasicBlock *DestBB) { 223 MachineBasicBlock *OrigBB = MI.getParent(); 224 225 // Create a new MBB for the code after the OrigBB. 226 MachineBasicBlock *NewBB = 227 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock()); 228 MF->insert(++OrigBB->getIterator(), NewBB); 229 230 // Splice the instructions starting with MI over to NewBB. 231 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end()); 232 233 // Add an unconditional branch from OrigBB to NewBB. 234 // Note the new unconditional branch is not being recorded. 235 // There doesn't seem to be meaningful DebugInfo available; this doesn't 236 // correspond to anything in the source. 237 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc()); 238 239 // Insert an entry into BlockInfo to align it properly with the block numbers. 240 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo()); 241 242 NewBB->transferSuccessors(OrigBB); 243 OrigBB->addSuccessor(NewBB); 244 OrigBB->addSuccessor(DestBB); 245 246 // Cleanup potential unconditional branch to successor block. 247 // Note that updateTerminator may change the size of the blocks. 248 OrigBB->updateTerminator(NewBB); 249 250 // Figure out how large the OrigBB is. As the first half of the original 251 // block, it cannot contain a tablejump. The size includes 252 // the new jump we added. (It should be possible to do this without 253 // recounting everything, but it's very confusing, and this is rarely 254 // executed.) 255 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB); 256 257 // Figure out how large the NewMBB is. As the second half of the original 258 // block, it may contain a tablejump. 259 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB); 260 261 // All BBOffsets following these blocks must be modified. 262 adjustBlockOffsets(*OrigBB); 263 264 // Need to fix live-in lists if we track liveness. 265 if (TRI->trackLivenessAfterRegAlloc(*MF)) 266 computeAndAddLiveIns(LiveRegs, *NewBB); 267 268 ++NumSplit; 269 270 return NewBB; 271 } 272 273 /// isBlockInRange - Returns true if the distance between specific MI and 274 /// specific BB can fit in MI's displacement field. 275 bool BranchRelaxation::isBlockInRange( 276 const MachineInstr &MI, const MachineBasicBlock &DestBB) const { 277 int64_t BrOffset = getInstrOffset(MI); 278 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset; 279 280 if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset)) 281 return true; 282 283 LLVM_DEBUG(dbgs() << "Out of range branch to destination " 284 << printMBBReference(DestBB) << " from " 285 << printMBBReference(*MI.getParent()) << " to " 286 << DestOffset << " offset " << DestOffset - BrOffset << '\t' 287 << MI); 288 289 return false; 290 } 291 292 /// fixupConditionalBranch - Fix up a conditional branch whose destination is 293 /// too far away to fit in its displacement field. It is converted to an inverse 294 /// conditional branch + an unconditional branch to the destination. 295 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) { 296 DebugLoc DL = MI.getDebugLoc(); 297 MachineBasicBlock *MBB = MI.getParent(); 298 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 299 MachineBasicBlock *NewBB = nullptr; 300 SmallVector<MachineOperand, 4> Cond; 301 302 auto insertUncondBranch = [&](MachineBasicBlock *MBB, 303 MachineBasicBlock *DestBB) { 304 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size; 305 int NewBrSize = 0; 306 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize); 307 BBSize += NewBrSize; 308 }; 309 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB, 310 MachineBasicBlock *FBB, 311 SmallVectorImpl<MachineOperand>& Cond) { 312 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size; 313 int NewBrSize = 0; 314 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize); 315 BBSize += NewBrSize; 316 }; 317 auto removeBranch = [&](MachineBasicBlock *MBB) { 318 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size; 319 int RemovedSize = 0; 320 TII->removeBranch(*MBB, &RemovedSize); 321 BBSize -= RemovedSize; 322 }; 323 324 auto finalizeBlockChanges = [&](MachineBasicBlock *MBB, 325 MachineBasicBlock *NewBB) { 326 // Keep the block offsets up to date. 327 adjustBlockOffsets(*MBB); 328 329 // Need to fix live-in lists if we track liveness. 330 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF)) 331 computeAndAddLiveIns(LiveRegs, *NewBB); 332 }; 333 334 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond); 335 assert(!Fail && "branches to be relaxed must be analyzable"); 336 (void)Fail; 337 338 // Add an unconditional branch to the destination and invert the branch 339 // condition to jump over it: 340 // tbz L1 341 // => 342 // tbnz L2 343 // b L1 344 // L2: 345 346 bool ReversedCond = !TII->reverseBranchCondition(Cond); 347 if (ReversedCond) { 348 if (FBB && isBlockInRange(MI, *FBB)) { 349 // Last MI in the BB is an unconditional branch. We can simply invert the 350 // condition and swap destinations: 351 // beq L1 352 // b L2 353 // => 354 // bne L2 355 // b L1 356 LLVM_DEBUG(dbgs() << " Invert condition and swap " 357 "its destination with " 358 << MBB->back()); 359 360 removeBranch(MBB); 361 insertBranch(MBB, FBB, TBB, Cond); 362 finalizeBlockChanges(MBB, nullptr); 363 return true; 364 } 365 if (FBB) { 366 // We need to split the basic block here to obtain two long-range 367 // unconditional branches. 368 NewBB = createNewBlockAfter(*MBB); 369 370 insertUncondBranch(NewBB, FBB); 371 // Update the succesor lists according to the transformation to follow. 372 // Do it here since if there's no split, no update is needed. 373 MBB->replaceSuccessor(FBB, NewBB); 374 NewBB->addSuccessor(FBB); 375 } 376 377 // We now have an appropriate fall-through block in place (either naturally or 378 // just created), so we can use the inverted the condition. 379 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB)); 380 381 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB) 382 << ", invert condition and change dest. to " 383 << printMBBReference(NextBB) << '\n'); 384 385 removeBranch(MBB); 386 // Insert a new conditional branch and a new unconditional branch. 387 insertBranch(MBB, &NextBB, TBB, Cond); 388 389 finalizeBlockChanges(MBB, NewBB); 390 return true; 391 } 392 // Branch cond can't be inverted. 393 // In this case we always add a block after the MBB. 394 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. " 395 << " Insert a new BB after " << MBB->back()); 396 397 if (!FBB) 398 FBB = &(*std::next(MachineFunction::iterator(MBB))); 399 400 // This is the block with cond. branch and the distance to TBB is too long. 401 // beq L1 402 // L2: 403 404 // We do the following transformation: 405 // beq NewBB 406 // b L2 407 // NewBB: 408 // b L1 409 // L2: 410 411 NewBB = createNewBlockAfter(*MBB); 412 insertUncondBranch(NewBB, TBB); 413 414 LLVM_DEBUG(dbgs() << " Insert cond B to the new BB " 415 << printMBBReference(*NewBB) 416 << " Keep the exiting condition.\n" 417 << " Insert B to " << printMBBReference(*FBB) << ".\n" 418 << " In the new BB: Insert B to " 419 << printMBBReference(*TBB) << ".\n"); 420 421 // Update the successor lists according to the transformation to follow. 422 MBB->replaceSuccessor(TBB, NewBB); 423 NewBB->addSuccessor(TBB); 424 425 // Replace branch in the current (MBB) block. 426 removeBranch(MBB); 427 insertBranch(MBB, NewBB, FBB, Cond); 428 429 finalizeBlockChanges(MBB, NewBB); 430 return true; 431 } 432 433 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) { 434 MachineBasicBlock *MBB = MI.getParent(); 435 436 unsigned OldBrSize = TII->getInstSizeInBytes(MI); 437 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI); 438 439 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset; 440 int64_t SrcOffset = getInstrOffset(MI); 441 442 assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset)); 443 444 BlockInfo[MBB->getNumber()].Size -= OldBrSize; 445 446 MachineBasicBlock *BranchBB = MBB; 447 448 // If this was an expanded conditional branch, there is already a single 449 // unconditional branch in a block. 450 if (!MBB->empty()) { 451 BranchBB = createNewBlockAfter(*MBB); 452 453 // Add live outs. 454 for (const MachineBasicBlock *Succ : MBB->successors()) { 455 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins()) 456 BranchBB->addLiveIn(LiveIn); 457 } 458 459 BranchBB->sortUniqueLiveIns(); 460 BranchBB->addSuccessor(DestBB); 461 MBB->replaceSuccessor(DestBB, BranchBB); 462 } 463 464 DebugLoc DL = MI.getDebugLoc(); 465 MI.eraseFromParent(); 466 BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch( 467 *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get()); 468 469 adjustBlockOffsets(*MBB); 470 return true; 471 } 472 473 bool BranchRelaxation::relaxBranchInstructions() { 474 bool Changed = false; 475 476 // Relaxing branches involves creating new basic blocks, so re-eval 477 // end() for termination. 478 for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) { 479 MachineBasicBlock &MBB = *I; 480 481 // Empty block? 482 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr(); 483 if (Last == MBB.end()) 484 continue; 485 486 // Expand the unconditional branch first if necessary. If there is a 487 // conditional branch, this will end up changing the branch destination of 488 // it to be over the newly inserted indirect branch block, which may avoid 489 // the need to try expanding the conditional branch first, saving an extra 490 // jump. 491 if (Last->isUnconditionalBranch()) { 492 // Unconditional branch destination might be unanalyzable, assume these 493 // are OK. 494 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) { 495 if (!isBlockInRange(*Last, *DestBB)) { 496 fixupUnconditionalBranch(*Last); 497 ++NumUnconditionalRelaxed; 498 Changed = true; 499 } 500 } 501 } 502 503 // Loop over the conditional branches. 504 MachineBasicBlock::iterator Next; 505 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator(); 506 J != MBB.end(); J = Next) { 507 Next = std::next(J); 508 MachineInstr &MI = *J; 509 510 if (MI.isConditionalBranch()) { 511 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI); 512 if (!isBlockInRange(MI, *DestBB)) { 513 if (Next != MBB.end() && Next->isConditionalBranch()) { 514 // If there are multiple conditional branches, this isn't an 515 // analyzable block. Split later terminators into a new block so 516 // each one will be analyzable. 517 518 splitBlockBeforeInstr(*Next, DestBB); 519 } else { 520 fixupConditionalBranch(MI); 521 ++NumConditionalRelaxed; 522 } 523 524 Changed = true; 525 526 // This may have modified all of the terminators, so start over. 527 Next = MBB.getFirstTerminator(); 528 } 529 } 530 } 531 } 532 533 return Changed; 534 } 535 536 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) { 537 MF = &mf; 538 539 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n"); 540 541 const TargetSubtargetInfo &ST = MF->getSubtarget(); 542 TII = ST.getInstrInfo(); 543 544 TRI = ST.getRegisterInfo(); 545 if (TRI->trackLivenessAfterRegAlloc(*MF)) 546 RS.reset(new RegScavenger()); 547 548 // Renumber all of the machine basic blocks in the function, guaranteeing that 549 // the numbers agree with the position of the block in the function. 550 MF->RenumberBlocks(); 551 552 // Do the initial scan of the function, building up information about the 553 // sizes of each block. 554 scanFunction(); 555 556 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs();); 557 558 bool MadeChange = false; 559 while (relaxBranchInstructions()) 560 MadeChange = true; 561 562 // After a while, this might be made debug-only, but it is not expensive. 563 verify(); 564 565 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs()); 566 567 BlockInfo.clear(); 568 569 return MadeChange; 570 } 571