1 //===- BranchRelaxation.cpp -----------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
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"
36 #define DEBUG_TYPE "branch-relaxation"
38 STATISTIC(NumSplit, "Number of basic blocks split");
39 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
40 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
42 #define BRANCH_RELAX_NAME "Branch relaxation pass"
46 class BranchRelaxation : public MachineFunctionPass {
47 /// BasicBlockInfo - Information about the offset and size of a single
49 struct BasicBlockInfo {
50 /// Offset - Distance from the beginning of the function to the beginning
51 /// of this basic block.
53 /// The offset is always aligned as required by the basic block.
56 /// Size - Size of the basic block in bytes. If the block contains
57 /// inline assembly, this is a worst case estimate.
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.
63 BasicBlockInfo() = default;
65 /// Compute the offset immediately following this block. \p MBB is the next
67 unsigned postOffset(const MachineBasicBlock &MBB) const {
68 const unsigned PO = Offset + Size;
69 const Align Alignment = MBB.getAlignment();
73 const Align ParentAlign = MBB.getParent()->getAlignment();
74 if (Alignment <= ParentAlign)
75 return PO + offsetToAlignment(PO, Alignment);
77 // The alignment of this MBB is larger than the function's alignment, so we
78 // can't tell whether or not it will insert nops. Assume that it will.
79 return PO + Alignment.value() + offsetToAlignment(PO, Alignment);
83 SmallVector<BasicBlockInfo, 16> BlockInfo;
84 std::unique_ptr<RegScavenger> RS;
85 LivePhysRegs LiveRegs;
88 const TargetRegisterInfo *TRI;
89 const TargetInstrInfo *TII;
91 bool relaxBranchInstructions();
94 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
96 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
97 MachineBasicBlock *DestBB);
98 void adjustBlockOffsets(MachineBasicBlock &Start);
99 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
101 bool fixupConditionalBranch(MachineInstr &MI);
102 bool fixupUnconditionalBranch(MachineInstr &MI);
103 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
104 unsigned getInstrOffset(const MachineInstr &MI) const;
111 BranchRelaxation() : MachineFunctionPass(ID) {}
113 bool runOnMachineFunction(MachineFunction &MF) override;
115 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
118 } // end anonymous namespace
120 char BranchRelaxation::ID = 0;
122 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
124 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
126 /// verify - check BBOffsets, BBSizes, alignment of islands
127 void BranchRelaxation::verify() {
129 unsigned PrevNum = MF->begin()->getNumber();
130 for (MachineBasicBlock &MBB : *MF) {
131 const unsigned Num = MBB.getNumber();
132 assert(isAligned(MBB.getAlignment(), BlockInfo[Num].Offset));
133 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
134 assert(BlockInfo[Num].Size == computeBlockSize(MBB));
140 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
141 /// print block size and offset information - debugging
142 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
143 for (auto &MBB : *MF) {
144 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
145 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
146 << format("size=%#x\n", BBI.Size);
151 /// scanFunction - Do the initial scan of the function, building up
152 /// information about each block.
153 void BranchRelaxation::scanFunction() {
155 BlockInfo.resize(MF->getNumBlockIDs());
157 // First thing, compute the size of all basic blocks, and see if the function
158 // has any inline assembly in it. If so, we have to be conservative about
159 // alignment assumptions, as we don't know for sure the size of any
160 // instructions in the inline assembly.
161 for (MachineBasicBlock &MBB : *MF)
162 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
164 // Compute block offsets and known bits.
165 adjustBlockOffsets(*MF->begin());
168 /// computeBlockSize - Compute the size for MBB.
169 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
171 for (const MachineInstr &MI : MBB)
172 Size += TII->getInstSizeInBytes(MI);
176 /// getInstrOffset - Return the current offset of the specified machine
177 /// instruction from the start of the function. This offset changes as stuff is
178 /// moved around inside the function.
179 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
180 const MachineBasicBlock *MBB = MI.getParent();
182 // The offset is composed of two things: the sum of the sizes of all MBB's
183 // before this instruction's block, and the offset from the start of the block
185 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
187 // Sum instructions before MI in MBB.
188 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
189 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
190 Offset += TII->getInstSizeInBytes(*I);
196 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
197 unsigned PrevNum = Start.getNumber();
198 for (auto &MBB : make_range(MachineFunction::iterator(Start), MF->end())) {
199 unsigned Num = MBB.getNumber();
200 if (!Num) // block zero is never changed from offset zero.
202 // Get the offset and known bits at the end of the layout predecessor.
203 // Include the alignment of the current block.
204 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
210 /// Insert a new empty basic block and insert it after \BB
211 MachineBasicBlock *BranchRelaxation::createNewBlockAfter(MachineBasicBlock &BB) {
212 // Create a new MBB for the code after the OrigBB.
213 MachineBasicBlock *NewBB =
214 MF->CreateMachineBasicBlock(BB.getBasicBlock());
215 MF->insert(++BB.getIterator(), NewBB);
217 // Insert an entry into BlockInfo to align it properly with the block numbers.
218 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
223 /// Split the basic block containing MI into two blocks, which are joined by
224 /// an unconditional branch. Update data structures and renumber blocks to
225 /// account for this change and returns the newly created block.
226 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
227 MachineBasicBlock *DestBB) {
228 MachineBasicBlock *OrigBB = MI.getParent();
230 // Create a new MBB for the code after the OrigBB.
231 MachineBasicBlock *NewBB =
232 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
233 MF->insert(++OrigBB->getIterator(), NewBB);
235 // Splice the instructions starting with MI over to NewBB.
236 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
238 // Add an unconditional branch from OrigBB to NewBB.
239 // Note the new unconditional branch is not being recorded.
240 // There doesn't seem to be meaningful DebugInfo available; this doesn't
241 // correspond to anything in the source.
242 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
244 // Insert an entry into BlockInfo to align it properly with the block numbers.
245 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
247 NewBB->transferSuccessors(OrigBB);
248 OrigBB->addSuccessor(NewBB);
249 OrigBB->addSuccessor(DestBB);
251 // Cleanup potential unconditional branch to successor block.
252 // Note that updateTerminator may change the size of the blocks.
253 NewBB->updateTerminator();
254 OrigBB->updateTerminator();
256 // Figure out how large the OrigBB is. As the first half of the original
257 // block, it cannot contain a tablejump. The size includes
258 // the new jump we added. (It should be possible to do this without
259 // recounting everything, but it's very confusing, and this is rarely
261 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
263 // Figure out how large the NewMBB is. As the second half of the original
264 // block, it may contain a tablejump.
265 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
267 // All BBOffsets following these blocks must be modified.
268 adjustBlockOffsets(*OrigBB);
270 // Need to fix live-in lists if we track liveness.
271 if (TRI->trackLivenessAfterRegAlloc(*MF))
272 computeAndAddLiveIns(LiveRegs, *NewBB);
279 /// isBlockInRange - Returns true if the distance between specific MI and
280 /// specific BB can fit in MI's displacement field.
281 bool BranchRelaxation::isBlockInRange(
282 const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
283 int64_t BrOffset = getInstrOffset(MI);
284 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
286 if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
289 LLVM_DEBUG(dbgs() << "Out of range branch to destination "
290 << printMBBReference(DestBB) << " from "
291 << printMBBReference(*MI.getParent()) << " to "
292 << DestOffset << " offset " << DestOffset - BrOffset << '\t'
298 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
299 /// too far away to fit in its displacement field. It is converted to an inverse
300 /// conditional branch + an unconditional branch to the destination.
301 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
302 DebugLoc DL = MI.getDebugLoc();
303 MachineBasicBlock *MBB = MI.getParent();
304 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
305 MachineBasicBlock *NewBB = nullptr;
306 SmallVector<MachineOperand, 4> Cond;
308 auto insertUncondBranch = [&](MachineBasicBlock *MBB,
309 MachineBasicBlock *DestBB) {
310 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
312 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
315 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
316 MachineBasicBlock *FBB,
317 SmallVectorImpl<MachineOperand>& Cond) {
318 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
320 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
323 auto removeBranch = [&](MachineBasicBlock *MBB) {
324 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
326 TII->removeBranch(*MBB, &RemovedSize);
327 BBSize -= RemovedSize;
330 auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
331 MachineBasicBlock *NewBB) {
332 // Keep the block offsets up to date.
333 adjustBlockOffsets(*MBB);
335 // Need to fix live-in lists if we track liveness.
336 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
337 computeAndAddLiveIns(LiveRegs, *NewBB);
340 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
341 assert(!Fail && "branches to be relaxed must be analyzable");
344 // Add an unconditional branch to the destination and invert the branch
345 // condition to jump over it:
352 bool ReversedCond = !TII->reverseBranchCondition(Cond);
354 if (FBB && isBlockInRange(MI, *FBB)) {
355 // Last MI in the BB is an unconditional branch. We can simply invert the
356 // condition and swap destinations:
362 LLVM_DEBUG(dbgs() << " Invert condition and swap "
363 "its destination with "
367 insertBranch(MBB, FBB, TBB, Cond);
368 finalizeBlockChanges(MBB, nullptr);
372 // We need to split the basic block here to obtain two long-range
373 // unconditional branches.
374 NewBB = createNewBlockAfter(*MBB);
376 insertUncondBranch(NewBB, FBB);
377 // Update the succesor lists according to the transformation to follow.
378 // Do it here since if there's no split, no update is needed.
379 MBB->replaceSuccessor(FBB, NewBB);
380 NewBB->addSuccessor(FBB);
383 // We now have an appropriate fall-through block in place (either naturally or
384 // just created), so we can use the inverted the condition.
385 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
387 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
388 << ", invert condition and change dest. to "
389 << printMBBReference(NextBB) << '\n');
392 // Insert a new conditional branch and a new unconditional branch.
393 insertBranch(MBB, &NextBB, TBB, Cond);
395 finalizeBlockChanges(MBB, NewBB);
398 // Branch cond can't be inverted.
399 // In this case we always add a block after the MBB.
400 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
401 << " Insert a new BB after " << MBB->back());
404 FBB = &(*std::next(MachineFunction::iterator(MBB)));
406 // This is the block with cond. branch and the distance to TBB is too long.
410 // We do the following transformation:
417 NewBB = createNewBlockAfter(*MBB);
418 insertUncondBranch(NewBB, TBB);
420 LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "
421 << printMBBReference(*NewBB)
422 << " Keep the exiting condition.\n"
423 << " Insert B to " << printMBBReference(*FBB) << ".\n"
424 << " In the new BB: Insert B to "
425 << printMBBReference(*TBB) << ".\n");
427 // Update the successor lists according to the transformation to follow.
428 MBB->replaceSuccessor(TBB, NewBB);
429 NewBB->addSuccessor(TBB);
431 // Replace branch in the current (MBB) block.
433 insertBranch(MBB, NewBB, FBB, Cond);
435 finalizeBlockChanges(MBB, NewBB);
439 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
440 MachineBasicBlock *MBB = MI.getParent();
442 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
443 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
445 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
446 int64_t SrcOffset = getInstrOffset(MI);
448 assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
450 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
452 MachineBasicBlock *BranchBB = MBB;
454 // If this was an expanded conditional branch, there is already a single
455 // unconditional branch in a block.
457 BranchBB = createNewBlockAfter(*MBB);
460 for (const MachineBasicBlock *Succ : MBB->successors()) {
461 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
462 BranchBB->addLiveIn(LiveIn);
465 BranchBB->sortUniqueLiveIns();
466 BranchBB->addSuccessor(DestBB);
467 MBB->replaceSuccessor(DestBB, BranchBB);
470 DebugLoc DL = MI.getDebugLoc();
471 MI.eraseFromParent();
472 BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
473 *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
475 adjustBlockOffsets(*MBB);
479 bool BranchRelaxation::relaxBranchInstructions() {
480 bool Changed = false;
482 // Relaxing branches involves creating new basic blocks, so re-eval
483 // end() for termination.
484 for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
485 MachineBasicBlock &MBB = *I;
488 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
489 if (Last == MBB.end())
492 // Expand the unconditional branch first if necessary. If there is a
493 // conditional branch, this will end up changing the branch destination of
494 // it to be over the newly inserted indirect branch block, which may avoid
495 // the need to try expanding the conditional branch first, saving an extra
497 if (Last->isUnconditionalBranch()) {
498 // Unconditional branch destination might be unanalyzable, assume these
500 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
501 if (!isBlockInRange(*Last, *DestBB)) {
502 fixupUnconditionalBranch(*Last);
503 ++NumUnconditionalRelaxed;
509 // Loop over the conditional branches.
510 MachineBasicBlock::iterator Next;
511 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
512 J != MBB.end(); J = Next) {
514 MachineInstr &MI = *J;
516 if (MI.isConditionalBranch()) {
517 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
518 if (!isBlockInRange(MI, *DestBB)) {
519 if (Next != MBB.end() && Next->isConditionalBranch()) {
520 // If there are multiple conditional branches, this isn't an
521 // analyzable block. Split later terminators into a new block so
522 // each one will be analyzable.
524 splitBlockBeforeInstr(*Next, DestBB);
526 fixupConditionalBranch(MI);
527 ++NumConditionalRelaxed;
532 // This may have modified all of the terminators, so start over.
533 Next = MBB.getFirstTerminator();
542 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
545 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
547 const TargetSubtargetInfo &ST = MF->getSubtarget();
548 TII = ST.getInstrInfo();
550 TRI = ST.getRegisterInfo();
551 if (TRI->trackLivenessAfterRegAlloc(*MF))
552 RS.reset(new RegScavenger());
554 // Renumber all of the machine basic blocks in the function, guaranteeing that
555 // the numbers agree with the position of the block in the function.
556 MF->RenumberBlocks();
558 // Do the initial scan of the function, building up information about the
559 // sizes of each block.
562 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
564 bool MadeChange = false;
565 while (relaxBranchInstructions())
568 // After a while, this might be made debug-only, but it is not expensive.
571 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());