Lines Matching +full:- +full:- +full:branch
1 //===- BranchRelaxation.cpp -----------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
20 #include "llvm/Config/llvm-config.h"
37 #define DEBUG_TYPE "branch-relaxation"
43 #define BRANCH_RELAX_NAME "Branch relaxation pass"
48 /// BasicBlockInfo - Information about the offset and size of a single
51 /// Offset - Distance from the beginning of the function to the beginning
57 /// Size - Size of the basic block in bytes. If the block contains
71 const Align ParentAlign = MBB.getParent()->getAlignment();
77 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();
133 /// verify - check BBOffsets, BBSizes, alignment of islands
136 unsigned PrevNum = MF->begin()->getNumber();
152 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
161 /// print block size and offset information - debugging
171 /// scanFunction - Do the initial scan of the function, building up
175 BlockInfo.resize(MF->getNumBlockIDs());
193 adjustBlockOffsets(*MF->begin());
197 << MF->getName() << ".\n");
201 /// computeBlockSize - Compute the size for MBB.
205 Size += TII->getInstSizeInBytes(MI);
209 /// getInstrOffset - Return the current offset of the specified machine
218 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
221 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
222 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
223 Offset += TII->getInstSizeInBytes(*I);
232 make_range(std::next(MachineFunction::iterator(Start)), MF->end())) {
254 MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);
255 MF->insert(++OrigMBB.getIterator(), NewBB);
258 NewBB->setSectionID(OrigMBB.getSectionID());
259 NewBB->setIsEndSection(OrigMBB.isEndSection());
263 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
269 /// an unconditional branch. Update data structures and renumber blocks to
278 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
279 MF->insert(++OrigBB->getIterator(), NewBB);
282 NewBB->setSectionID(OrigBB->getSectionID());
283 NewBB->setIsEndSection(OrigBB->isEndSection());
284 OrigBB->setIsEndSection(false);
287 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
289 // Add an unconditional branch from OrigBB to NewBB.
290 // Note the new unconditional branch is not being recorded.
293 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
296 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
298 NewBB->transferSuccessors(OrigBB);
299 OrigBB->addSuccessor(NewBB);
300 OrigBB->addSuccessor(DestBB);
302 // Cleanup potential unconditional branch to successor block.
304 OrigBB->updateTerminator(NewBB);
311 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
315 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
320 // Need to fix live-in lists if we track liveness.
321 if (TRI->trackLivenessAfterRegAlloc(*MF))
329 /// isBlockInRange - Returns true if the distance between specific MI and
338 if (TII->isBranchOffsetInRange(MI.getOpcode(),
339 SrcBB->getSectionID() != DestBB.getSectionID()
340 ? TM->getMaxCodeSize()
341 : DestOffset - BrOffset))
344 LLVM_DEBUG(dbgs() << "Out of range branch to destination "
347 << DestOffset << " offset " << DestOffset - BrOffset << '\t'
353 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
355 /// conditional branch + an unconditional branch to the destination.
365 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
367 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
373 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
375 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
379 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
381 TII->removeBranch(*MBB, &RemovedSize);
382 BBSize -= RemovedSize;
390 // Need to fix live-in lists if we track liveness.
391 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
395 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
399 // Since cross-section conditional branches to the cold section are rarely
401 // branch", which unconditionally branches to the branch destination. Place
402 // the trampoline branch at the end of the function and retarget the
403 // conditional branch to the trampoline.
409 if (MBB->getSectionID() != TBB->getSectionID() &&
410 TBB->getSectionID() == MBBSectionID::ColdSectionID &&
414 createNewBlockAfter(*TrampolineInsertionPoint, MBB->getBasicBlock());
418 << NewBB->back());
423 MBB->replaceSuccessor(TBB, NewBB);
424 NewBB->addSuccessor(TBB);
426 // Replace branch in the current (MBB) block.
439 TrampolineInsertionPoint->setIsEndSection(NewBB->isEndSection());
440 MF->erase(NewBB);
443 // Add an unconditional branch to the destination and invert the branch
451 bool ReversedCond = !TII->reverseBranchCondition(Cond);
454 // Last MI in the BB is an unconditional branch. We can simply invert the
463 << MBB->back());
471 // We need to split the basic block here to obtain two long-range
478 MBB->replaceSuccessor(FBB, NewBB);
479 NewBB->addSuccessor(FBB);
482 // We now have an appropriate fall-through block in place (either naturally or
491 // Insert a new conditional branch and a new unconditional branch.
497 // Branch cond can't be inverted.
499 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
500 << " Insert a new BB after " << MBB->back());
505 // This is the block with cond. branch and the distance to TBB is too long.
527 MBB->replaceSuccessor(TBB, NewBB);
528 NewBB->addSuccessor(TBB);
530 // Replace branch in the current (MBB) block.
541 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
542 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
544 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
547 assert(!TII->isBranchOffsetInRange(
548 MI.getOpcode(), MBB->getSectionID() != DestBB->getSectionID()
549 ? TM->getMaxCodeSize()
550 : DestOffset - SrcOffset));
552 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
556 // If this was an expanded conditional branch, there is already a single
557 // unconditional branch in a block.
558 if (!MBB->empty()) {
562 for (const MachineBasicBlock *Succ : MBB->successors()) {
563 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
564 BranchBB->addLiveIn(LiveIn);
567 BranchBB->sortUniqueLiveIns();
568 BranchBB->addSuccessor(DestBB);
569 MBB->replaceSuccessor(DestBB, BranchBB);
580 MachineBasicBlock *RestoreBB = createNewBlockAfter(MF->back(),
581 DestBB->getBasicBlock());
582 std::prev(RestoreBB->getIterator())
583 ->setIsEndSection(RestoreBB->isEndSection());
584 RestoreBB->setIsEndSection(false);
586 TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB, DL,
587 BranchBB->getSectionID() != DestBB->getSectionID()
588 ? TM->getMaxCodeSize()
589 : DestOffset - SrcOffset,
592 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);
596 if (!RestoreBB->empty()) {
597 // If the jump is Cold -> Hot, don't place the restore block (which is
599 if (MBB->getSectionID() == MBBSectionID::ColdSectionID &&
600 DestBB->getSectionID() != MBBSectionID::ColdSectionID) {
602 TII->insertUnconditionalBranch(*NewBB, DestBB, DebugLoc());
603 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
608 // Retarget the unconditional branch to the trampoline block.
609 BranchBB->replaceSuccessor(DestBB, NewBB);
610 NewBB->addSuccessor(DestBB);
620 // restore blocks are just duplicated for each far branch.
621 assert(!DestBB->isEntryBlock());
622 MachineBasicBlock *PrevBB = &*std::prev(DestBB->getIterator());
623 // Fall through only if PrevBB has no unconditional branch as one of its
625 if (auto *FT = PrevBB->getLogicalFallThrough()) {
627 TII->insertUnconditionalBranch(*PrevBB, FT, DebugLoc());
628 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(*PrevBB);
631 MF->splice(DestBB->getIterator(), RestoreBB->getIterator());
633 RestoreBB->addSuccessor(DestBB);
634 BranchBB->replaceSuccessor(DestBB, RestoreBB);
635 if (TRI->trackLivenessAfterRegAlloc(*MF))
638 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB);
643 RestoreBB->setSectionID(DestBB->getSectionID());
644 RestoreBB->setIsBeginSection(DestBB->isBeginSection());
645 DestBB->setIsBeginSection(false);
649 MF->erase(RestoreBB);
659 // Relaxing branches involves creating new basic blocks, so re-eval
667 // Expand the unconditional branch first if necessary. If there is a
668 // conditional branch, this will end up changing the branch destination of
669 // it to be over the newly inserted indirect branch block, which may avoid
670 // the need to try expanding the conditional branch first, saving an extra
672 if (Last->isUnconditionalBranch()) {
673 // Unconditional branch destination might be unanalyzable, assume these
675 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
676 if (!isBlockInRange(*Last, *DestBB) && !TII->isTailCall(*Last) &&
700 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
702 if (Next != MBB.end() && Next->isConditionalBranch()) {
729 const TargetSubtargetInfo &ST = MF->getSubtarget();
731 TM = &MF->getTarget();
734 if (TRI->trackLivenessAfterRegAlloc(*MF))
739 MF->RenumberBlocks();
751 // After a while, this might be made debug-only, but it is not expensive.