815 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/CodeGen/BranchRelaxation.h"10#include "llvm/ADT/SmallVector.h"11#include "llvm/ADT/Statistic.h"12#include "llvm/CodeGen/LivePhysRegs.h"13#include "llvm/CodeGen/MachineBasicBlock.h"14#include "llvm/CodeGen/MachineFunction.h"15#include "llvm/CodeGen/MachineFunctionPass.h"16#include "llvm/CodeGen/MachineInstr.h"17#include "llvm/CodeGen/RegisterScavenging.h"18#include "llvm/CodeGen/TargetInstrInfo.h"19#include "llvm/CodeGen/TargetRegisterInfo.h"20#include "llvm/CodeGen/TargetSubtargetInfo.h"21#include "llvm/Config/llvm-config.h"22#include "llvm/IR/DebugLoc.h"23#include "llvm/InitializePasses.h"24#include "llvm/Pass.h"25#include "llvm/Support/Compiler.h"26#include "llvm/Support/Debug.h"27#include "llvm/Support/ErrorHandling.h"28#include "llvm/Support/Format.h"29#include "llvm/Support/raw_ostream.h"30#include "llvm/Target/TargetMachine.h"31#include <cassert>32#include <cstdint>33#include <iterator>34#include <memory>35 36using namespace llvm;37 38#define DEBUG_TYPE "branch-relaxation"39 40STATISTIC(NumSplit, "Number of basic blocks split");41STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");42STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");43 44#define BRANCH_RELAX_NAME "Branch relaxation pass"45 46namespace {47 48class BranchRelaxation {49 /// BasicBlockInfo - Information about the offset and size of a single50 /// basic block.51 struct BasicBlockInfo {52 /// Offset - Distance from the beginning of the function to the beginning53 /// of this basic block.54 ///55 /// The offset is always aligned as required by the basic block.56 unsigned Offset = 0;57 58 /// Size - Size of the basic block in bytes. If the block contains59 /// inline assembly, this is a worst case estimate.60 ///61 /// The size does not include any alignment padding whether from the62 /// beginning of the block, or from an aligned jump table at the end.63 unsigned Size = 0;64 65 BasicBlockInfo() = default;66 67 /// Compute the offset immediately following this block. \p MBB is the next68 /// block.69 unsigned postOffset(const MachineBasicBlock &MBB) const {70 const unsigned PO = Offset + Size;71 const Align Alignment = MBB.getAlignment();72 const Align ParentAlign = MBB.getParent()->getAlignment();73 if (Alignment <= ParentAlign)74 return alignTo(PO, Alignment);75 76 // The alignment of this MBB is larger than the function's alignment, so77 // we can't tell whether or not it will insert nops. Assume that it will.78 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();79 }80 };81 82 SmallVector<BasicBlockInfo, 16> BlockInfo;83 84 // The basic block after which trampolines are inserted. This is the last85 // basic block that isn't in the cold section.86 MachineBasicBlock *TrampolineInsertionPoint = nullptr;87 SmallDenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>>88 RelaxedUnconditionals;89 std::unique_ptr<RegScavenger> RS;90 LivePhysRegs LiveRegs;91 92 MachineFunction *MF = nullptr;93 const TargetRegisterInfo *TRI = nullptr;94 const TargetInstrInfo *TII = nullptr;95 const TargetMachine *TM = nullptr;96 97 bool relaxBranchInstructions();98 void scanFunction();99 100 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB);101 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB,102 const BasicBlock *BB);103 104 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,105 MachineBasicBlock *DestBB);106 void adjustBlockOffsets(MachineBasicBlock &Start);107 void adjustBlockOffsets(MachineBasicBlock &Start,108 MachineFunction::iterator End);109 bool isBlockInRange(const MachineInstr &MI,110 const MachineBasicBlock &BB) const;111 112 bool fixupConditionalBranch(MachineInstr &MI);113 bool fixupUnconditionalBranch(MachineInstr &MI);114 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;115 unsigned getInstrOffset(const MachineInstr &MI) const;116 void dumpBBs();117 void verify();118 119public:120 bool run(MachineFunction &MF);121};122 123class BranchRelaxationLegacy : public MachineFunctionPass {124public:125 static char ID;126 127 BranchRelaxationLegacy() : MachineFunctionPass(ID) {}128 129 bool runOnMachineFunction(MachineFunction &MF) override {130 return BranchRelaxation().run(MF);131 }132 133 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }134};135 136} // end anonymous namespace137 138char BranchRelaxationLegacy::ID = 0;139 140char &llvm::BranchRelaxationPassID = BranchRelaxationLegacy::ID;141 142INITIALIZE_PASS(BranchRelaxationLegacy, DEBUG_TYPE, BRANCH_RELAX_NAME, false,143 false)144 145/// verify - check BBOffsets, BBSizes, alignment of islands146void BranchRelaxation::verify() {147#ifndef NDEBUG148 unsigned PrevNum = MF->begin()->getNumber();149 for (MachineBasicBlock &MBB : *MF) {150 const unsigned Num = MBB.getNumber();151 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);152 assert(BlockInfo[Num].Size == computeBlockSize(MBB));153 PrevNum = Num;154 }155 156 for (MachineBasicBlock &MBB : *MF) {157 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();158 J != MBB.end(); J = std::next(J)) {159 MachineInstr &MI = *J;160 if (!MI.isConditionalBranch() && !MI.isUnconditionalBranch())161 continue;162 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)163 continue;164 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);165 assert(isBlockInRange(MI, *DestBB) ||166 RelaxedUnconditionals.contains({&MBB, DestBB}));167 }168 }169#endif170}171 172#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)173/// print block size and offset information - debugging174LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {175 for (auto &MBB : *MF) {176 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];177 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)178 << format("size=%#x\n", BBI.Size);179 }180}181#endif182 183/// scanFunction - Do the initial scan of the function, building up184/// information about each block.185void BranchRelaxation::scanFunction() {186 BlockInfo.clear();187 BlockInfo.resize(MF->getNumBlockIDs());188 189 TrampolineInsertionPoint = nullptr;190 RelaxedUnconditionals.clear();191 192 // First thing, compute the size of all basic blocks, and see if the function193 // has any inline assembly in it. If so, we have to be conservative about194 // alignment assumptions, as we don't know for sure the size of any195 // instructions in the inline assembly. At the same time, place the196 // trampoline insertion point at the end of the hot portion of the function.197 for (MachineBasicBlock &MBB : *MF) {198 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);199 200 if (MBB.getSectionID() != MBBSectionID::ColdSectionID)201 TrampolineInsertionPoint = &MBB;202 }203 204 // Compute block offsets and known bits.205 adjustBlockOffsets(*MF->begin());206 207 if (TrampolineInsertionPoint == nullptr) {208 LLVM_DEBUG(dbgs() << " No suitable trampoline insertion point found in "209 << MF->getName() << ".\n");210 }211}212 213/// computeBlockSize - Compute the size for MBB.214uint64_t215BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {216 uint64_t Size = 0;217 for (const MachineInstr &MI : MBB)218 Size += TII->getInstSizeInBytes(MI);219 return Size;220}221 222/// getInstrOffset - Return the current offset of the specified machine223/// instruction from the start of the function. This offset changes as stuff is224/// moved around inside the function.225unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {226 const MachineBasicBlock *MBB = MI.getParent();227 228 // The offset is composed of two things: the sum of the sizes of all MBB's229 // before this instruction's block, and the offset from the start of the block230 // it is in.231 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;232 233 // Sum instructions before MI in MBB.234 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {235 assert(I != MBB->end() && "Didn't find MI in its own basic block?");236 Offset += TII->getInstSizeInBytes(*I);237 }238 239 return Offset;240}241 242void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {243 adjustBlockOffsets(Start, MF->end());244}245 246void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start,247 MachineFunction::iterator End) {248 unsigned PrevNum = Start.getNumber();249 for (auto &MBB :250 make_range(std::next(MachineFunction::iterator(Start)), End)) {251 unsigned Num = MBB.getNumber();252 // Get the offset and known bits at the end of the layout predecessor.253 // Include the alignment of the current block.254 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);255 256 PrevNum = Num;257 }258}259 260/// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB261MachineBasicBlock *262BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {263 return createNewBlockAfter(OrigBB, OrigBB.getBasicBlock());264}265 266/// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock267/// and insert it after \p OrigMBB268MachineBasicBlock *269BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigMBB,270 const BasicBlock *BB) {271 // Create a new MBB for the code after the OrigBB.272 MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);273 MF->insert(++OrigMBB.getIterator(), NewBB);274 275 // Place the new block in the same section as OrigBB276 NewBB->setSectionID(OrigMBB.getSectionID());277 NewBB->setIsEndSection(OrigMBB.isEndSection());278 OrigMBB.setIsEndSection(false);279 280 // Insert an entry into BlockInfo to align it properly with the block numbers.281 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());282 283 return NewBB;284}285 286/// Split the basic block containing MI into two blocks, which are joined by287/// an unconditional branch. Update data structures and renumber blocks to288/// account for this change and returns the newly created block.289MachineBasicBlock *290BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,291 MachineBasicBlock *DestBB) {292 MachineBasicBlock *OrigBB = MI.getParent();293 294 // Create a new MBB for the code after the OrigBB.295 MachineBasicBlock *NewBB =296 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());297 MF->insert(++OrigBB->getIterator(), NewBB);298 299 // Place the new block in the same section as OrigBB.300 NewBB->setSectionID(OrigBB->getSectionID());301 NewBB->setIsEndSection(OrigBB->isEndSection());302 OrigBB->setIsEndSection(false);303 304 // Splice the instructions starting with MI over to NewBB.305 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());306 307 // Add an unconditional branch from OrigBB to NewBB.308 // Note the new unconditional branch is not being recorded.309 // There doesn't seem to be meaningful DebugInfo available; this doesn't310 // correspond to anything in the source.311 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());312 313 // Insert an entry into BlockInfo to align it properly with the block numbers.314 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());315 316 NewBB->transferSuccessors(OrigBB);317 OrigBB->addSuccessor(NewBB);318 OrigBB->addSuccessor(DestBB);319 320 // Cleanup potential unconditional branch to successor block.321 // Note that updateTerminator may change the size of the blocks.322 OrigBB->updateTerminator(NewBB);323 324 // Figure out how large the OrigBB is. As the first half of the original325 // block, it cannot contain a tablejump. The size includes326 // the new jump we added. (It should be possible to do this without327 // recounting everything, but it's very confusing, and this is rarely328 // executed.)329 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);330 331 // Figure out how large the NewMBB is. As the second half of the original332 // block, it may contain a tablejump.333 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);334 335 // Update the offset of the new block.336 adjustBlockOffsets(*OrigBB, std::next(NewBB->getIterator()));337 338 // Need to fix live-in lists if we track liveness.339 if (TRI->trackLivenessAfterRegAlloc(*MF))340 computeAndAddLiveIns(LiveRegs, *NewBB);341 342 ++NumSplit;343 344 return NewBB;345}346 347/// isBlockInRange - Returns true if the distance between specific MI and348/// specific BB can fit in MI's displacement field.349bool BranchRelaxation::isBlockInRange(const MachineInstr &MI,350 const MachineBasicBlock &DestBB) const {351 int64_t BrOffset = getInstrOffset(MI);352 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;353 354 const MachineBasicBlock *SrcBB = MI.getParent();355 356 if (TII->isBranchOffsetInRange(MI.getOpcode(),357 SrcBB->getSectionID() != DestBB.getSectionID()358 ? TM->getMaxCodeSize()359 : DestOffset - BrOffset))360 return true;361 362 LLVM_DEBUG(dbgs() << "Out of range branch to destination "363 << printMBBReference(DestBB) << " from "364 << printMBBReference(*MI.getParent()) << " to "365 << DestOffset << " offset " << DestOffset - BrOffset << '\t'366 << MI);367 368 return false;369}370 371/// fixupConditionalBranch - Fix up a conditional branch whose destination is372/// too far away to fit in its displacement field. It is converted to an inverse373/// conditional branch + an unconditional branch to the destination.374bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {375 DebugLoc DL = MI.getDebugLoc();376 MachineBasicBlock *MBB = MI.getParent();377 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;378 MachineBasicBlock *NewBB = nullptr;379 SmallVector<MachineOperand, 4> Cond;380 381 auto insertUncondBranch = [&](MachineBasicBlock *MBB,382 MachineBasicBlock *DestBB) {383 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;384 int NewBrSize = 0;385 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);386 BBSize += NewBrSize;387 };388 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,389 MachineBasicBlock *FBB,390 SmallVectorImpl<MachineOperand> &Cond) {391 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;392 int NewBrSize = 0;393 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);394 BBSize += NewBrSize;395 };396 auto removeBranch = [&](MachineBasicBlock *MBB) {397 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;398 int RemovedSize = 0;399 TII->removeBranch(*MBB, &RemovedSize);400 BBSize -= RemovedSize;401 };402 403 // Populate the block offset and live-ins for a new basic block.404 auto updateOffsetAndLiveness = [&](MachineBasicBlock *NewBB) {405 assert(NewBB != nullptr && "can't populate offset for nullptr");406 407 // Keep the block offsets approximately up to date. While they will be408 // slight underestimates, we will update them appropriately in the next409 // scan through the function.410 adjustBlockOffsets(*std::prev(NewBB->getIterator()),411 std::next(NewBB->getIterator()));412 413 // Need to fix live-in lists if we track liveness.414 if (TRI->trackLivenessAfterRegAlloc(*MF))415 computeAndAddLiveIns(LiveRegs, *NewBB);416 };417 418 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);419 assert(!Fail && "branches to be relaxed must be analyzable");420 (void)Fail;421 422 // Since cross-section conditional branches to the cold section are rarely423 // taken, try to avoid inverting the condition. Instead, add a "trampoline424 // branch", which unconditionally branches to the branch destination. Place425 // the trampoline branch at the end of the function and retarget the426 // conditional branch to the trampoline.427 // tbz L1428 // =>429 // tbz L1Trampoline430 // ...431 // L1Trampoline: b L1432 if (MBB->getSectionID() != TBB->getSectionID() &&433 TBB->getSectionID() == MBBSectionID::ColdSectionID &&434 TrampolineInsertionPoint != nullptr) {435 // If the insertion point is out of range, we can't put a trampoline there.436 NewBB =437 createNewBlockAfter(*TrampolineInsertionPoint, MBB->getBasicBlock());438 439 if (isBlockInRange(MI, *NewBB)) {440 LLVM_DEBUG(dbgs() << " Retarget destination to trampoline at "441 << NewBB->back());442 443 insertUncondBranch(NewBB, TBB);444 445 // Update the successor lists to include the trampoline.446 MBB->replaceSuccessor(TBB, NewBB);447 NewBB->addSuccessor(TBB);448 449 // Replace branch in the current (MBB) block.450 removeBranch(MBB);451 insertBranch(MBB, NewBB, FBB, Cond);452 453 TrampolineInsertionPoint = NewBB;454 updateOffsetAndLiveness(NewBB);455 return true;456 }457 458 LLVM_DEBUG(459 dbgs() << " Trampoline insertion point out of range for Bcc from "460 << printMBBReference(*MBB) << " to " << printMBBReference(*TBB)461 << ".\n");462 TrampolineInsertionPoint->setIsEndSection(NewBB->isEndSection());463 MF->erase(NewBB);464 NewBB = nullptr;465 }466 467 // Add an unconditional branch to the destination and invert the branch468 // condition to jump over it:469 // tbz L1470 // =>471 // tbnz L2472 // b L1473 // L2:474 475 bool ReversedCond = !TII->reverseBranchCondition(Cond);476 if (ReversedCond) {477 if (FBB && isBlockInRange(MI, *FBB)) {478 // Last MI in the BB is an unconditional branch. We can simply invert the479 // condition and swap destinations:480 // beq L1481 // b L2482 // =>483 // bne L2484 // b L1485 LLVM_DEBUG(dbgs() << " Invert condition and swap "486 "its destination with "487 << MBB->back());488 489 removeBranch(MBB);490 insertBranch(MBB, FBB, TBB, Cond);491 return true;492 }493 if (FBB) {494 // If we get here with a MBB which ends like this:495 //496 // bb.1:497 // successors: %bb.2;498 // ...499 // BNE $x1, $x0, %bb.2500 // PseudoBR %bb.2501 //502 // Just remove conditional branch.503 if (TBB == FBB) {504 removeBranch(MBB);505 insertUncondBranch(MBB, TBB);506 return true;507 }508 // We need to split the basic block here to obtain two long-range509 // unconditional branches.510 NewBB = createNewBlockAfter(*MBB);511 512 insertUncondBranch(NewBB, FBB);513 // Update the succesor lists according to the transformation to follow.514 // Do it here since if there's no split, no update is needed.515 MBB->replaceSuccessor(FBB, NewBB);516 NewBB->addSuccessor(FBB);517 updateOffsetAndLiveness(NewBB);518 }519 520 // We now have an appropriate fall-through block in place (either naturally521 // or just created), so we can use the inverted the condition.522 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));523 524 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)525 << ", invert condition and change dest. to "526 << printMBBReference(NextBB) << '\n');527 528 removeBranch(MBB);529 // Insert a new conditional branch and a new unconditional branch.530 insertBranch(MBB, &NextBB, TBB, Cond);531 return true;532 }533 // Branch cond can't be inverted.534 // In this case we always add a block after the MBB.535 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "536 << " Insert a new BB after " << MBB->back());537 538 if (!FBB)539 FBB = &(*std::next(MachineFunction::iterator(MBB)));540 541 // This is the block with cond. branch and the distance to TBB is too long.542 // beq L1543 // L2:544 545 // We do the following transformation:546 // beq NewBB547 // b L2548 // NewBB:549 // b L1550 // L2:551 552 NewBB = createNewBlockAfter(*MBB);553 insertUncondBranch(NewBB, TBB);554 555 LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "556 << printMBBReference(*NewBB)557 << " Keep the exiting condition.\n"558 << " Insert B to " << printMBBReference(*FBB) << ".\n"559 << " In the new BB: Insert B to "560 << printMBBReference(*TBB) << ".\n");561 562 // Update the successor lists according to the transformation to follow.563 MBB->replaceSuccessor(TBB, NewBB);564 NewBB->addSuccessor(TBB);565 566 // Replace branch in the current (MBB) block.567 removeBranch(MBB);568 insertBranch(MBB, NewBB, FBB, Cond);569 570 updateOffsetAndLiveness(NewBB);571 return true;572}573 574bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {575 MachineBasicBlock *MBB = MI.getParent();576 unsigned OldBrSize = TII->getInstSizeInBytes(MI);577 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);578 579 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;580 int64_t SrcOffset = getInstrOffset(MI);581 582 assert(!TII->isBranchOffsetInRange(583 MI.getOpcode(), MBB->getSectionID() != DestBB->getSectionID()584 ? TM->getMaxCodeSize()585 : DestOffset - SrcOffset));586 587 BlockInfo[MBB->getNumber()].Size -= OldBrSize;588 589 MachineBasicBlock *BranchBB = MBB;590 591 // If this was an expanded conditional branch, there is already a single592 // unconditional branch in a block.593 if (!MBB->empty()) {594 BranchBB = createNewBlockAfter(*MBB);595 596 // Add live outs.597 for (const MachineBasicBlock *Succ : MBB->successors()) {598 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())599 BranchBB->addLiveIn(LiveIn);600 }601 602 BranchBB->sortUniqueLiveIns();603 BranchBB->addSuccessor(DestBB);604 MBB->replaceSuccessor(DestBB, BranchBB);605 if (TrampolineInsertionPoint == MBB)606 TrampolineInsertionPoint = BranchBB;607 }608 609 DebugLoc DL = MI.getDebugLoc();610 MI.eraseFromParent();611 612 // Create the optional restore block and, initially, place it at the end of613 // function. That block will be placed later if it's used; otherwise, it will614 // be erased.615 MachineBasicBlock *RestoreBB =616 createNewBlockAfter(MF->back(), DestBB->getBasicBlock());617 std::prev(RestoreBB->getIterator())618 ->setIsEndSection(RestoreBB->isEndSection());619 RestoreBB->setIsEndSection(false);620 621 TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB, DL,622 BranchBB->getSectionID() != DestBB->getSectionID()623 ? TM->getMaxCodeSize()624 : DestOffset - SrcOffset,625 RS.get());626 627 // Update the block size and offset for the BranchBB (which may be newly628 // created).629 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);630 adjustBlockOffsets(*MBB, std::next(BranchBB->getIterator()));631 632 // If RestoreBB is required, place it appropriately.633 if (!RestoreBB->empty()) {634 // If the jump is Cold -> Hot, don't place the restore block (which is635 // cold) in the middle of the function. Place it at the end.636 if (MBB->getSectionID() == MBBSectionID::ColdSectionID &&637 DestBB->getSectionID() != MBBSectionID::ColdSectionID) {638 MachineBasicBlock *NewBB = createNewBlockAfter(*TrampolineInsertionPoint);639 TII->insertUnconditionalBranch(*NewBB, DestBB, DebugLoc());640 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);641 adjustBlockOffsets(*TrampolineInsertionPoint,642 std::next(NewBB->getIterator()));643 644 // New trampolines should be inserted after NewBB.645 TrampolineInsertionPoint = NewBB;646 647 // Retarget the unconditional branch to the trampoline block.648 BranchBB->replaceSuccessor(DestBB, NewBB);649 NewBB->addSuccessor(DestBB);650 651 DestBB = NewBB;652 }653 654 // In all other cases, try to place just before DestBB.655 656 // TODO: For multiple far branches to the same destination, there are657 // chances that some restore blocks could be shared if they clobber the658 // same registers and share the same restore sequence. So far, those659 // restore blocks are just duplicated for each far branch.660 assert(!DestBB->isEntryBlock());661 MachineBasicBlock *PrevBB = &*std::prev(DestBB->getIterator());662 // Fall through only if PrevBB has no unconditional branch as one of its663 // terminators.664 if (auto *FT = PrevBB->getLogicalFallThrough()) {665 assert(FT == DestBB);666 TII->insertUnconditionalBranch(*PrevBB, FT, DebugLoc());667 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(*PrevBB);668 }669 // Now, RestoreBB could be placed directly before DestBB.670 MF->splice(DestBB->getIterator(), RestoreBB->getIterator());671 // Update successors and predecessors.672 RestoreBB->addSuccessor(DestBB);673 BranchBB->replaceSuccessor(DestBB, RestoreBB);674 if (TRI->trackLivenessAfterRegAlloc(*MF))675 computeAndAddLiveIns(LiveRegs, *RestoreBB);676 // Compute the restore block size.677 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB);678 // Update the estimated offset for the restore block.679 adjustBlockOffsets(*PrevBB, DestBB->getIterator());680 681 // Fix up section information for RestoreBB and DestBB682 RestoreBB->setSectionID(DestBB->getSectionID());683 RestoreBB->setIsBeginSection(DestBB->isBeginSection());684 DestBB->setIsBeginSection(false);685 RelaxedUnconditionals.insert({BranchBB, RestoreBB});686 } else {687 // Remove restore block if it's not required.688 MF->erase(RestoreBB);689 RelaxedUnconditionals.insert({BranchBB, DestBB});690 }691 692 return true;693}694 695bool BranchRelaxation::relaxBranchInstructions() {696 bool Changed = false;697 698 // Relaxing branches involves creating new basic blocks, so re-eval699 // end() for termination.700 for (MachineBasicBlock &MBB : *MF) {701 // Empty block?702 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();703 if (Last == MBB.end())704 continue;705 706 // Expand the unconditional branch first if necessary. If there is a707 // conditional branch, this will end up changing the branch destination of708 // it to be over the newly inserted indirect branch block, which may avoid709 // the need to try expanding the conditional branch first, saving an extra710 // jump.711 if (Last->isUnconditionalBranch()) {712 // Unconditional branch destination might be unanalyzable, assume these713 // are OK.714 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {715 if (!isBlockInRange(*Last, *DestBB) && !TII->isTailCall(*Last) &&716 !RelaxedUnconditionals.contains({&MBB, DestBB})) {717 fixupUnconditionalBranch(*Last);718 ++NumUnconditionalRelaxed;719 Changed = true;720 }721 }722 }723 724 // Loop over the conditional branches.725 MachineBasicBlock::iterator Next;726 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();727 J != MBB.end(); J = Next) {728 Next = std::next(J);729 MachineInstr &MI = *J;730 731 if (!MI.isConditionalBranch())732 continue;733 734 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)735 // FAULTING_OP's destination is not encoded in the instruction stream736 // and thus never needs relaxed.737 continue;738 739 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);740 if (!isBlockInRange(MI, *DestBB)) {741 if (Next != MBB.end() && Next->isConditionalBranch()) {742 // If there are multiple conditional branches, this isn't an743 // analyzable block. Split later terminators into a new block so744 // each one will be analyzable.745 746 splitBlockBeforeInstr(*Next, DestBB);747 } else {748 fixupConditionalBranch(MI);749 ++NumConditionalRelaxed;750 }751 752 Changed = true;753 754 // This may have modified all of the terminators, so start over.755 Next = MBB.getFirstTerminator();756 }757 }758 }759 760 // If we relaxed a branch, we must recompute offsets for *all* basic blocks.761 // Otherwise, we may underestimate branch distances and fail to relax a branch762 // that has been pushed out of range.763 if (Changed)764 adjustBlockOffsets(MF->front());765 766 return Changed;767}768 769PreservedAnalyses770BranchRelaxationPass::run(MachineFunction &MF,771 MachineFunctionAnalysisManager &MFAM) {772 if (!BranchRelaxation().run(MF))773 return PreservedAnalyses::all();774 775 return getMachineFunctionPassPreservedAnalyses();776}777 778bool BranchRelaxation::run(MachineFunction &mf) {779 MF = &mf;780 781 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");782 783 const TargetSubtargetInfo &ST = MF->getSubtarget();784 TII = ST.getInstrInfo();785 TM = &MF->getTarget();786 787 TRI = ST.getRegisterInfo();788 if (TRI->trackLivenessAfterRegAlloc(*MF))789 RS.reset(new RegScavenger());790 791 // Renumber all of the machine basic blocks in the function, guaranteeing that792 // the numbers agree with the position of the block in the function.793 MF->RenumberBlocks();794 795 // Do the initial scan of the function, building up information about the796 // sizes of each block.797 scanFunction();798 799 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););800 801 bool MadeChange = false;802 while (relaxBranchInstructions())803 MadeChange = true;804 805 // After a while, this might be made debug-only, but it is not expensive.806 verify();807 808 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());809 810 BlockInfo.clear();811 RelaxedUnconditionals.clear();812 813 return MadeChange;814}815