Lines Matching +full:block +full:- +full:offset
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"
48 /// BasicBlockInfo - Information about the offset and size of a single
49 /// basic block.
51 /// Offset - Distance from the beginning of the function to the beginning
52 /// of this basic block.
54 /// The offset is always aligned as required by the basic block.
55 unsigned Offset = 0; member
57 /// Size - Size of the basic block in bytes. If the block contains
61 /// beginning of the block, or from an aligned jump table at the end.
66 /// Compute the offset immediately following this block. \p MBB is the next
67 /// block.
69 const unsigned PO = Offset + Size; in postOffset()
71 const Align ParentAlign = MBB.getParent()->getAlignment(); in postOffset()
77 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value(); in postOffset()
83 // The basic block after which trampolines are inserted. This is the last
84 // basic block that isn't in the cold section.
133 /// verify - check BBOffsets, BBSizes, alignment of islands in INITIALIZE_PASS()
136 unsigned PrevNum = MF->begin()->getNumber(); in INITIALIZE_PASS()
139 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset); in INITIALIZE_PASS()
152 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI); in INITIALIZE_PASS()
161 /// print block size and offset information - debugging
165 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset) in dumpBBs()
171 /// scanFunction - Do the initial scan of the function, building up
172 /// information about each block.
175 BlockInfo.resize(MF->getNumBlockIDs()); in scanFunction()
192 // Compute block offsets and known bits. in scanFunction()
193 adjustBlockOffsets(*MF->begin()); in scanFunction()
197 << MF->getName() << ".\n"); in scanFunction()
201 /// computeBlockSize - Compute the size for MBB.
205 Size += TII->getInstSizeInBytes(MI); in computeBlockSize()
209 /// getInstrOffset - Return the current offset of the specified machine
210 /// instruction from the start of the function. This offset changes as stuff is
215 // The offset is composed of two things: the sum of the sizes of all MBB's in getInstrOffset()
216 // before this instruction's block, and the offset from the start of the block in getInstrOffset()
218 unsigned Offset = BlockInfo[MBB->getNumber()].Offset; in getInstrOffset() local
221 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) { in getInstrOffset()
222 assert(I != MBB->end() && "Didn't find MI in its own basic block?"); in getInstrOffset()
223 Offset += TII->getInstSizeInBytes(*I); in getInstrOffset()
226 return Offset; in getInstrOffset()
232 make_range(std::next(MachineFunction::iterator(Start)), MF->end())) { in adjustBlockOffsets()
234 // Get the offset and known bits at the end of the layout predecessor. in adjustBlockOffsets()
235 // Include the alignment of the current block. in adjustBlockOffsets()
236 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB); in adjustBlockOffsets()
254 MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB); in createNewBlockAfter()
255 MF->insert(++OrigMBB.getIterator(), NewBB); in createNewBlockAfter()
257 // Place the new block in the same section as OrigBB in createNewBlockAfter()
258 NewBB->setSectionID(OrigMBB.getSectionID()); in createNewBlockAfter()
259 NewBB->setIsEndSection(OrigMBB.isEndSection()); in createNewBlockAfter()
262 // Insert an entry into BlockInfo to align it properly with the block numbers. in createNewBlockAfter()
263 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo()); in createNewBlockAfter()
268 /// Split the basic block containing MI into two blocks, which are joined by
270 /// account for this change and returns the newly created block.
278 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock()); in splitBlockBeforeInstr()
279 MF->insert(++OrigBB->getIterator(), NewBB); in splitBlockBeforeInstr()
281 // Place the new block in the same section as OrigBB. in splitBlockBeforeInstr()
282 NewBB->setSectionID(OrigBB->getSectionID()); in splitBlockBeforeInstr()
283 NewBB->setIsEndSection(OrigBB->isEndSection()); in splitBlockBeforeInstr()
284 OrigBB->setIsEndSection(false); in splitBlockBeforeInstr()
287 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end()); in splitBlockBeforeInstr()
293 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc()); in splitBlockBeforeInstr()
295 // Insert an entry into BlockInfo to align it properly with the block numbers. in splitBlockBeforeInstr()
296 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo()); in splitBlockBeforeInstr()
298 NewBB->transferSuccessors(OrigBB); in splitBlockBeforeInstr()
299 OrigBB->addSuccessor(NewBB); in splitBlockBeforeInstr()
300 OrigBB->addSuccessor(DestBB); in splitBlockBeforeInstr()
302 // Cleanup potential unconditional branch to successor block. in splitBlockBeforeInstr()
304 OrigBB->updateTerminator(NewBB); in splitBlockBeforeInstr()
307 // block, it cannot contain a tablejump. The size includes in splitBlockBeforeInstr()
311 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB); in splitBlockBeforeInstr()
314 // block, it may contain a tablejump. in splitBlockBeforeInstr()
315 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB); in splitBlockBeforeInstr()
320 // Need to fix live-in lists if we track liveness. in splitBlockBeforeInstr()
321 if (TRI->trackLivenessAfterRegAlloc(*MF)) in splitBlockBeforeInstr()
329 /// isBlockInRange - Returns true if the distance between specific MI and
334 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset; in isBlockInRange()
338 if (TII->isBranchOffsetInRange(MI.getOpcode(), in isBlockInRange()
339 SrcBB->getSectionID() != DestBB.getSectionID() in isBlockInRange()
340 ? TM->getMaxCodeSize() in isBlockInRange()
341 : DestOffset - BrOffset)) in isBlockInRange()
347 << DestOffset << " offset " << DestOffset - BrOffset << '\t' in isBlockInRange()
353 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
365 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size; in fixupConditionalBranch()
367 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize); in fixupConditionalBranch()
373 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size; in fixupConditionalBranch()
375 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize); in fixupConditionalBranch()
379 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size; in fixupConditionalBranch()
381 TII->removeBranch(*MBB, &RemovedSize); in fixupConditionalBranch()
382 BBSize -= RemovedSize; in fixupConditionalBranch()
387 // Keep the block offsets up to date. in fixupConditionalBranch()
390 // Need to fix live-in lists if we track liveness. in fixupConditionalBranch()
391 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF)) in fixupConditionalBranch()
395 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond); in fixupConditionalBranch()
399 // Since cross-section conditional branches to the cold section are rarely in fixupConditionalBranch()
409 if (MBB->getSectionID() != TBB->getSectionID() && in fixupConditionalBranch()
410 TBB->getSectionID() == MBBSectionID::ColdSectionID && in fixupConditionalBranch()
414 createNewBlockAfter(*TrampolineInsertionPoint, MBB->getBasicBlock()); in fixupConditionalBranch()
418 << NewBB->back()); in fixupConditionalBranch()
423 MBB->replaceSuccessor(TBB, NewBB); in fixupConditionalBranch()
424 NewBB->addSuccessor(TBB); in fixupConditionalBranch()
426 // Replace branch in the current (MBB) block. in fixupConditionalBranch()
439 TrampolineInsertionPoint->setIsEndSection(NewBB->isEndSection()); in fixupConditionalBranch()
440 MF->erase(NewBB); in fixupConditionalBranch()
451 bool ReversedCond = !TII->reverseBranchCondition(Cond); in fixupConditionalBranch()
463 << MBB->back()); in fixupConditionalBranch()
471 // We need to split the basic block here to obtain two long-range in fixupConditionalBranch()
478 MBB->replaceSuccessor(FBB, NewBB); in fixupConditionalBranch()
479 NewBB->addSuccessor(FBB); in fixupConditionalBranch()
482 // We now have an appropriate fall-through block in place (either naturally or in fixupConditionalBranch()
498 // In this case we always add a block after the MBB. in fixupConditionalBranch()
500 << " Insert a new BB after " << MBB->back()); in fixupConditionalBranch()
505 // This is the block with cond. branch and the distance to TBB is too long. in fixupConditionalBranch()
527 MBB->replaceSuccessor(TBB, NewBB); in fixupConditionalBranch()
528 NewBB->addSuccessor(TBB); in fixupConditionalBranch()
530 // Replace branch in the current (MBB) block. in fixupConditionalBranch()
541 unsigned OldBrSize = TII->getInstSizeInBytes(MI); in fixupUnconditionalBranch()
542 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI); in fixupUnconditionalBranch()
544 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset; in fixupUnconditionalBranch()
547 assert(!TII->isBranchOffsetInRange( in fixupUnconditionalBranch()
548 MI.getOpcode(), MBB->getSectionID() != DestBB->getSectionID() in fixupUnconditionalBranch()
549 ? TM->getMaxCodeSize() in fixupUnconditionalBranch()
550 : DestOffset - SrcOffset)); in fixupUnconditionalBranch()
552 BlockInfo[MBB->getNumber()].Size -= OldBrSize; in fixupUnconditionalBranch()
557 // unconditional branch in a block. in fixupUnconditionalBranch()
558 if (!MBB->empty()) { in fixupUnconditionalBranch()
562 for (const MachineBasicBlock *Succ : MBB->successors()) { in fixupUnconditionalBranch()
563 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins()) in fixupUnconditionalBranch()
564 BranchBB->addLiveIn(LiveIn); in fixupUnconditionalBranch()
567 BranchBB->sortUniqueLiveIns(); in fixupUnconditionalBranch()
568 BranchBB->addSuccessor(DestBB); in fixupUnconditionalBranch()
569 MBB->replaceSuccessor(DestBB, BranchBB); in fixupUnconditionalBranch()
577 // Create the optional restore block and, initially, place it at the end of in fixupUnconditionalBranch()
578 // function. That block will be placed later if it's used; otherwise, it will in fixupUnconditionalBranch()
580 MachineBasicBlock *RestoreBB = createNewBlockAfter(MF->back(), in fixupUnconditionalBranch()
581 DestBB->getBasicBlock()); in fixupUnconditionalBranch()
582 std::prev(RestoreBB->getIterator()) in fixupUnconditionalBranch()
583 ->setIsEndSection(RestoreBB->isEndSection()); in fixupUnconditionalBranch()
584 RestoreBB->setIsEndSection(false); in fixupUnconditionalBranch()
586 TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB, DL, in fixupUnconditionalBranch()
587 BranchBB->getSectionID() != DestBB->getSectionID() in fixupUnconditionalBranch()
588 ? TM->getMaxCodeSize() in fixupUnconditionalBranch()
589 : DestOffset - SrcOffset, in fixupUnconditionalBranch()
592 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB); in fixupUnconditionalBranch()
596 if (!RestoreBB->empty()) { in fixupUnconditionalBranch()
597 // If the jump is Cold -> Hot, don't place the restore block (which is in fixupUnconditionalBranch()
599 if (MBB->getSectionID() == MBBSectionID::ColdSectionID && in fixupUnconditionalBranch()
600 DestBB->getSectionID() != MBBSectionID::ColdSectionID) { in fixupUnconditionalBranch()
602 TII->insertUnconditionalBranch(*NewBB, DestBB, DebugLoc()); in fixupUnconditionalBranch()
603 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB); in fixupUnconditionalBranch()
608 // Retarget the unconditional branch to the trampoline block. in fixupUnconditionalBranch()
609 BranchBB->replaceSuccessor(DestBB, NewBB); in fixupUnconditionalBranch()
610 NewBB->addSuccessor(DestBB); in fixupUnconditionalBranch()
621 assert(!DestBB->isEntryBlock()); in fixupUnconditionalBranch()
622 MachineBasicBlock *PrevBB = &*std::prev(DestBB->getIterator()); in fixupUnconditionalBranch()
625 if (auto *FT = PrevBB->getLogicalFallThrough()) { in fixupUnconditionalBranch()
627 TII->insertUnconditionalBranch(*PrevBB, FT, DebugLoc()); in fixupUnconditionalBranch()
628 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(*PrevBB); in fixupUnconditionalBranch()
631 MF->splice(DestBB->getIterator(), RestoreBB->getIterator()); in fixupUnconditionalBranch()
633 RestoreBB->addSuccessor(DestBB); in fixupUnconditionalBranch()
634 BranchBB->replaceSuccessor(DestBB, RestoreBB); in fixupUnconditionalBranch()
635 if (TRI->trackLivenessAfterRegAlloc(*MF)) in fixupUnconditionalBranch()
637 // Compute the restore block size. in fixupUnconditionalBranch()
638 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB); in fixupUnconditionalBranch()
639 // Update the offset starting from the previous block. in fixupUnconditionalBranch()
643 RestoreBB->setSectionID(DestBB->getSectionID()); in fixupUnconditionalBranch()
644 RestoreBB->setIsBeginSection(DestBB->isBeginSection()); in fixupUnconditionalBranch()
645 DestBB->setIsBeginSection(false); in fixupUnconditionalBranch()
648 // Remove restore block if it's not required. in fixupUnconditionalBranch()
649 MF->erase(RestoreBB); in fixupUnconditionalBranch()
659 // Relaxing branches involves creating new basic blocks, so re-eval in relaxBranchInstructions()
662 // Empty block? in relaxBranchInstructions()
669 // it to be over the newly inserted indirect branch block, which may avoid in relaxBranchInstructions()
672 if (Last->isUnconditionalBranch()) { in relaxBranchInstructions()
675 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) { in relaxBranchInstructions()
676 if (!isBlockInRange(*Last, *DestBB) && !TII->isTailCall(*Last) && in relaxBranchInstructions()
700 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI); in relaxBranchInstructions()
702 if (Next != MBB.end() && Next->isConditionalBranch()) { in relaxBranchInstructions()
704 // analyzable block. Split later terminators into a new block so in relaxBranchInstructions()
729 const TargetSubtargetInfo &ST = MF->getSubtarget(); in runOnMachineFunction()
731 TM = &MF->getTarget(); in runOnMachineFunction()
734 if (TRI->trackLivenessAfterRegAlloc(*MF)) in runOnMachineFunction()
738 // the numbers agree with the position of the block in the function. in runOnMachineFunction()
739 MF->RenumberBlocks(); in runOnMachineFunction()
742 // sizes of each block. in runOnMachineFunction()
751 // After a while, this might be made debug-only, but it is not expensive. in runOnMachineFunction()