[RISCV] Fix mgather -> riscv.masked.strided.load combine not extending indices (...
[llvm-project.git] / llvm / lib / CodeGen / BranchRelaxation.cpp
blobf50eb5e1730a3280b1ed574738eee8205801ed2e
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 //===----------------------------------------------------------------------===//
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/ErrorHandling.h"
27 #include "llvm/Support/Format.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/Target/TargetMachine.h"
30 #include <cassert>
31 #include <cstdint>
32 #include <iterator>
33 #include <memory>
35 using namespace llvm;
37 #define DEBUG_TYPE "branch-relaxation"
39 STATISTIC(NumSplit, "Number of basic blocks split");
40 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
41 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
43 #define BRANCH_RELAX_NAME "Branch relaxation pass"
45 namespace {
47 class BranchRelaxation : public MachineFunctionPass {
48 /// BasicBlockInfo - Information about the offset and size of a single
49 /// basic block.
50 struct BasicBlockInfo {
51 /// Offset - Distance from the beginning of the function to the beginning
52 /// of this basic block.
53 ///
54 /// The offset is always aligned as required by the basic block.
55 unsigned Offset = 0;
57 /// Size - Size of the basic block in bytes. If the block contains
58 /// inline assembly, this is a worst case estimate.
59 ///
60 /// The size does not include any alignment padding whether from the
61 /// beginning of the block, or from an aligned jump table at the end.
62 unsigned Size = 0;
64 BasicBlockInfo() = default;
66 /// Compute the offset immediately following this block. \p MBB is the next
67 /// block.
68 unsigned postOffset(const MachineBasicBlock &MBB) const {
69 const unsigned PO = Offset + Size;
70 const Align Alignment = MBB.getAlignment();
71 const Align ParentAlign = MBB.getParent()->getAlignment();
72 if (Alignment <= ParentAlign)
73 return alignTo(PO, Alignment);
75 // The alignment of this MBB is larger than the function's alignment, so we
76 // can't tell whether or not it will insert nops. Assume that it will.
77 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();
81 SmallVector<BasicBlockInfo, 16> BlockInfo;
83 // The basic block after which trampolines are inserted. This is the last
84 // basic block that isn't in the cold section.
85 MachineBasicBlock *TrampolineInsertionPoint = nullptr;
86 SmallDenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>>
87 RelaxedUnconditionals;
88 std::unique_ptr<RegScavenger> RS;
89 LivePhysRegs LiveRegs;
91 MachineFunction *MF = nullptr;
92 const TargetRegisterInfo *TRI = nullptr;
93 const TargetInstrInfo *TII = nullptr;
94 const TargetMachine *TM = nullptr;
96 bool relaxBranchInstructions();
97 void scanFunction();
99 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB);
100 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB,
101 const BasicBlock *BB);
103 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
104 MachineBasicBlock *DestBB);
105 void adjustBlockOffsets(MachineBasicBlock &Start);
106 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
108 bool fixupConditionalBranch(MachineInstr &MI);
109 bool fixupUnconditionalBranch(MachineInstr &MI);
110 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
111 unsigned getInstrOffset(const MachineInstr &MI) const;
112 void dumpBBs();
113 void verify();
115 public:
116 static char ID;
118 BranchRelaxation() : MachineFunctionPass(ID) {}
120 bool runOnMachineFunction(MachineFunction &MF) override;
122 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
125 } // end anonymous namespace
127 char BranchRelaxation::ID = 0;
129 char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
131 INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
133 /// verify - check BBOffsets, BBSizes, alignment of islands
134 void BranchRelaxation::verify() {
135 #ifndef NDEBUG
136 unsigned PrevNum = MF->begin()->getNumber();
137 for (MachineBasicBlock &MBB : *MF) {
138 const unsigned Num = MBB.getNumber();
139 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
140 assert(BlockInfo[Num].Size == computeBlockSize(MBB));
141 PrevNum = Num;
144 for (MachineBasicBlock &MBB : *MF) {
145 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
146 J != MBB.end(); J = std::next(J)) {
147 MachineInstr &MI = *J;
148 if (!MI.isConditionalBranch() && !MI.isUnconditionalBranch())
149 continue;
150 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
151 continue;
152 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
153 assert(isBlockInRange(MI, *DestBB) ||
154 RelaxedUnconditionals.contains({&MBB, DestBB}));
157 #endif
160 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
161 /// print block size and offset information - debugging
162 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
163 for (auto &MBB : *MF) {
164 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
165 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
166 << format("size=%#x\n", BBI.Size);
169 #endif
171 /// scanFunction - Do the initial scan of the function, building up
172 /// information about each block.
173 void BranchRelaxation::scanFunction() {
174 BlockInfo.clear();
175 BlockInfo.resize(MF->getNumBlockIDs());
177 TrampolineInsertionPoint = nullptr;
178 RelaxedUnconditionals.clear();
180 // First thing, compute the size of all basic blocks, and see if the function
181 // has any inline assembly in it. If so, we have to be conservative about
182 // alignment assumptions, as we don't know for sure the size of any
183 // instructions in the inline assembly. At the same time, place the
184 // trampoline insertion point at the end of the hot portion of the function.
185 for (MachineBasicBlock &MBB : *MF) {
186 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
188 if (MBB.getSectionID() != MBBSectionID::ColdSectionID)
189 TrampolineInsertionPoint = &MBB;
192 // Compute block offsets and known bits.
193 adjustBlockOffsets(*MF->begin());
195 if (TrampolineInsertionPoint == nullptr) {
196 LLVM_DEBUG(dbgs() << " No suitable trampoline insertion point found in "
197 << MF->getName() << ".\n");
201 /// computeBlockSize - Compute the size for MBB.
202 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
203 uint64_t Size = 0;
204 for (const MachineInstr &MI : MBB)
205 Size += TII->getInstSizeInBytes(MI);
206 return Size;
209 /// getInstrOffset - Return the current offset of the specified machine
210 /// instruction from the start of the function. This offset changes as stuff is
211 /// moved around inside the function.
212 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
213 const MachineBasicBlock *MBB = MI.getParent();
215 // The offset is composed of two things: the sum of the sizes of all MBB's
216 // before this instruction's block, and the offset from the start of the block
217 // it is in.
218 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
220 // Sum instructions before MI in MBB.
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);
226 return Offset;
229 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
230 unsigned PrevNum = Start.getNumber();
231 for (auto &MBB :
232 make_range(std::next(MachineFunction::iterator(Start)), MF->end())) {
233 unsigned Num = MBB.getNumber();
234 // Get the offset and known bits at the end of the layout predecessor.
235 // Include the alignment of the current block.
236 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
238 PrevNum = Num;
242 /// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB
243 MachineBasicBlock *
244 BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {
245 return createNewBlockAfter(OrigBB, OrigBB.getBasicBlock());
248 /// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock
249 /// and insert it after \p OrigMBB
250 MachineBasicBlock *
251 BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigMBB,
252 const BasicBlock *BB) {
253 // Create a new MBB for the code after the OrigBB.
254 MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);
255 MF->insert(++OrigMBB.getIterator(), NewBB);
257 // Place the new block in the same section as OrigBB
258 NewBB->setSectionID(OrigMBB.getSectionID());
259 NewBB->setIsEndSection(OrigMBB.isEndSection());
260 OrigMBB.setIsEndSection(false);
262 // Insert an entry into BlockInfo to align it properly with the block numbers.
263 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
265 return NewBB;
268 /// Split the basic block containing MI into two blocks, which are joined by
269 /// an unconditional branch. Update data structures and renumber blocks to
270 /// account for this change and returns the newly created block.
271 MachineBasicBlock *
272 BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
273 MachineBasicBlock *DestBB) {
274 MachineBasicBlock *OrigBB = MI.getParent();
276 // Create a new MBB for the code after the OrigBB.
277 MachineBasicBlock *NewBB =
278 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
279 MF->insert(++OrigBB->getIterator(), NewBB);
281 // Place the new block in the same section as OrigBB.
282 NewBB->setSectionID(OrigBB->getSectionID());
283 NewBB->setIsEndSection(OrigBB->isEndSection());
284 OrigBB->setIsEndSection(false);
286 // Splice the instructions starting with MI over to NewBB.
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.
291 // There doesn't seem to be meaningful DebugInfo available; this doesn't
292 // correspond to anything in the source.
293 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
295 // Insert an entry into BlockInfo to align it properly with the block numbers.
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.
303 // Note that updateTerminator may change the size of the blocks.
304 OrigBB->updateTerminator(NewBB);
306 // Figure out how large the OrigBB is. As the first half of the original
307 // block, it cannot contain a tablejump. The size includes
308 // the new jump we added. (It should be possible to do this without
309 // recounting everything, but it's very confusing, and this is rarely
310 // executed.)
311 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
313 // Figure out how large the NewMBB is. As the second half of the original
314 // block, it may contain a tablejump.
315 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
317 // All BBOffsets following these blocks must be modified.
318 adjustBlockOffsets(*OrigBB);
320 // Need to fix live-in lists if we track liveness.
321 if (TRI->trackLivenessAfterRegAlloc(*MF))
322 computeAndAddLiveIns(LiveRegs, *NewBB);
324 ++NumSplit;
326 return NewBB;
329 /// isBlockInRange - Returns true if the distance between specific MI and
330 /// specific BB can fit in MI's displacement field.
331 bool BranchRelaxation::isBlockInRange(
332 const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
333 int64_t BrOffset = getInstrOffset(MI);
334 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
336 const MachineBasicBlock *SrcBB = MI.getParent();
338 if (TII->isBranchOffsetInRange(MI.getOpcode(),
339 SrcBB->getSectionID() != DestBB.getSectionID()
340 ? TM->getMaxCodeSize()
341 : DestOffset - BrOffset))
342 return true;
344 LLVM_DEBUG(dbgs() << "Out of range branch to destination "
345 << printMBBReference(DestBB) << " from "
346 << printMBBReference(*MI.getParent()) << " to "
347 << DestOffset << " offset " << DestOffset - BrOffset << '\t'
348 << MI);
350 return false;
353 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
354 /// too far away to fit in its displacement field. It is converted to an inverse
355 /// conditional branch + an unconditional branch to the destination.
356 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
357 DebugLoc DL = MI.getDebugLoc();
358 MachineBasicBlock *MBB = MI.getParent();
359 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
360 MachineBasicBlock *NewBB = nullptr;
361 SmallVector<MachineOperand, 4> Cond;
363 auto insertUncondBranch = [&](MachineBasicBlock *MBB,
364 MachineBasicBlock *DestBB) {
365 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
366 int NewBrSize = 0;
367 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
368 BBSize += NewBrSize;
370 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
371 MachineBasicBlock *FBB,
372 SmallVectorImpl<MachineOperand>& Cond) {
373 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
374 int NewBrSize = 0;
375 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
376 BBSize += NewBrSize;
378 auto removeBranch = [&](MachineBasicBlock *MBB) {
379 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
380 int RemovedSize = 0;
381 TII->removeBranch(*MBB, &RemovedSize);
382 BBSize -= RemovedSize;
385 auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
386 MachineBasicBlock *NewBB) {
387 // Keep the block offsets up to date.
388 adjustBlockOffsets(*MBB);
390 // Need to fix live-in lists if we track liveness.
391 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
392 computeAndAddLiveIns(LiveRegs, *NewBB);
395 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
396 assert(!Fail && "branches to be relaxed must be analyzable");
397 (void)Fail;
399 // Since cross-section conditional branches to the cold section are rarely
400 // taken, try to avoid inverting the condition. Instead, add a "trampoline
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.
404 // tbz L1
405 // =>
406 // tbz L1Trampoline
407 // ...
408 // L1Trampoline: b L1
409 if (MBB->getSectionID() != TBB->getSectionID() &&
410 TBB->getSectionID() == MBBSectionID::ColdSectionID &&
411 TrampolineInsertionPoint != nullptr) {
412 // If the insertion point is out of range, we can't put a trampoline there.
413 NewBB =
414 createNewBlockAfter(*TrampolineInsertionPoint, MBB->getBasicBlock());
416 if (isBlockInRange(MI, *NewBB)) {
417 LLVM_DEBUG(dbgs() << " Retarget destination to trampoline at "
418 << NewBB->back());
420 insertUncondBranch(NewBB, TBB);
422 // Update the successor lists to include the trampoline.
423 MBB->replaceSuccessor(TBB, NewBB);
424 NewBB->addSuccessor(TBB);
426 // Replace branch in the current (MBB) block.
427 removeBranch(MBB);
428 insertBranch(MBB, NewBB, FBB, Cond);
430 TrampolineInsertionPoint = NewBB;
431 finalizeBlockChanges(MBB, NewBB);
432 return true;
435 LLVM_DEBUG(
436 dbgs() << " Trampoline insertion point out of range for Bcc from "
437 << printMBBReference(*MBB) << " to " << printMBBReference(*TBB)
438 << ".\n");
439 TrampolineInsertionPoint->setIsEndSection(NewBB->isEndSection());
440 MF->erase(NewBB);
443 // Add an unconditional branch to the destination and invert the branch
444 // condition to jump over it:
445 // tbz L1
446 // =>
447 // tbnz L2
448 // b L1
449 // L2:
451 bool ReversedCond = !TII->reverseBranchCondition(Cond);
452 if (ReversedCond) {
453 if (FBB && isBlockInRange(MI, *FBB)) {
454 // Last MI in the BB is an unconditional branch. We can simply invert the
455 // condition and swap destinations:
456 // beq L1
457 // b L2
458 // =>
459 // bne L2
460 // b L1
461 LLVM_DEBUG(dbgs() << " Invert condition and swap "
462 "its destination with "
463 << MBB->back());
465 removeBranch(MBB);
466 insertBranch(MBB, FBB, TBB, Cond);
467 finalizeBlockChanges(MBB, nullptr);
468 return true;
470 if (FBB) {
471 // We need to split the basic block here to obtain two long-range
472 // unconditional branches.
473 NewBB = createNewBlockAfter(*MBB);
475 insertUncondBranch(NewBB, FBB);
476 // Update the succesor lists according to the transformation to follow.
477 // Do it here since if there's no split, no update is needed.
478 MBB->replaceSuccessor(FBB, NewBB);
479 NewBB->addSuccessor(FBB);
482 // We now have an appropriate fall-through block in place (either naturally or
483 // just created), so we can use the inverted the condition.
484 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
486 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
487 << ", invert condition and change dest. to "
488 << printMBBReference(NextBB) << '\n');
490 removeBranch(MBB);
491 // Insert a new conditional branch and a new unconditional branch.
492 insertBranch(MBB, &NextBB, TBB, Cond);
494 finalizeBlockChanges(MBB, NewBB);
495 return true;
497 // Branch cond can't be inverted.
498 // In this case we always add a block after the MBB.
499 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
500 << " Insert a new BB after " << MBB->back());
502 if (!FBB)
503 FBB = &(*std::next(MachineFunction::iterator(MBB)));
505 // This is the block with cond. branch and the distance to TBB is too long.
506 // beq L1
507 // L2:
509 // We do the following transformation:
510 // beq NewBB
511 // b L2
512 // NewBB:
513 // b L1
514 // L2:
516 NewBB = createNewBlockAfter(*MBB);
517 insertUncondBranch(NewBB, TBB);
519 LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "
520 << printMBBReference(*NewBB)
521 << " Keep the exiting condition.\n"
522 << " Insert B to " << printMBBReference(*FBB) << ".\n"
523 << " In the new BB: Insert B to "
524 << printMBBReference(*TBB) << ".\n");
526 // Update the successor lists according to the transformation to follow.
527 MBB->replaceSuccessor(TBB, NewBB);
528 NewBB->addSuccessor(TBB);
530 // Replace branch in the current (MBB) block.
531 removeBranch(MBB);
532 insertBranch(MBB, NewBB, FBB, Cond);
534 finalizeBlockChanges(MBB, NewBB);
535 return true;
538 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
539 MachineBasicBlock *MBB = MI.getParent();
540 SmallVector<MachineOperand, 4> Cond;
541 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
542 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
544 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
545 int64_t SrcOffset = getInstrOffset(MI);
547 assert(!TII->isBranchOffsetInRange(
548 MI.getOpcode(), MBB->getSectionID() != DestBB->getSectionID()
549 ? TM->getMaxCodeSize()
550 : DestOffset - SrcOffset));
552 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
554 MachineBasicBlock *BranchBB = MBB;
556 // If this was an expanded conditional branch, there is already a single
557 // unconditional branch in a block.
558 if (!MBB->empty()) {
559 BranchBB = createNewBlockAfter(*MBB);
561 // Add live outs.
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);
570 if (TrampolineInsertionPoint == MBB)
571 TrampolineInsertionPoint = BranchBB;
574 DebugLoc DL = MI.getDebugLoc();
575 MI.eraseFromParent();
577 // Create the optional restore block and, initially, place it at the end of
578 // function. That block will be placed later if it's used; otherwise, it will
579 // be erased.
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,
590 RS.get());
592 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);
593 adjustBlockOffsets(*MBB);
595 // If RestoreBB is required, place it appropriately.
596 if (!RestoreBB->empty()) {
597 // If the jump is Cold -> Hot, don't place the restore block (which is
598 // cold) in the middle of the function. Place it at the end.
599 if (MBB->getSectionID() == MBBSectionID::ColdSectionID &&
600 DestBB->getSectionID() != MBBSectionID::ColdSectionID) {
601 MachineBasicBlock *NewBB = createNewBlockAfter(*TrampolineInsertionPoint);
602 TII->insertUnconditionalBranch(*NewBB, DestBB, DebugLoc());
603 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
605 // New trampolines should be inserted after NewBB.
606 TrampolineInsertionPoint = NewBB;
608 // Retarget the unconditional branch to the trampoline block.
609 BranchBB->replaceSuccessor(DestBB, NewBB);
610 NewBB->addSuccessor(DestBB);
612 DestBB = NewBB;
615 // In all other cases, try to place just before DestBB.
617 // TODO: For multiple far branches to the same destination, there are
618 // chances that some restore blocks could be shared if they clobber the
619 // same registers and share the same restore sequence. So far, those
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
624 // terminators.
625 if (auto *FT = PrevBB->getLogicalFallThrough()) {
626 assert(FT == DestBB);
627 TII->insertUnconditionalBranch(*PrevBB, FT, DebugLoc());
628 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(*PrevBB);
630 // Now, RestoreBB could be placed directly before DestBB.
631 MF->splice(DestBB->getIterator(), RestoreBB->getIterator());
632 // Update successors and predecessors.
633 RestoreBB->addSuccessor(DestBB);
634 BranchBB->replaceSuccessor(DestBB, RestoreBB);
635 if (TRI->trackLivenessAfterRegAlloc(*MF))
636 computeAndAddLiveIns(LiveRegs, *RestoreBB);
637 // Compute the restore block size.
638 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB);
639 // Update the offset starting from the previous block.
640 adjustBlockOffsets(*PrevBB);
642 // Fix up section information for RestoreBB and DestBB
643 RestoreBB->setSectionID(DestBB->getSectionID());
644 RestoreBB->setIsBeginSection(DestBB->isBeginSection());
645 DestBB->setIsBeginSection(false);
646 RelaxedUnconditionals.insert({BranchBB, RestoreBB});
647 } else {
648 // Remove restore block if it's not required.
649 MF->erase(RestoreBB);
650 RelaxedUnconditionals.insert({BranchBB, DestBB});
653 return true;
656 bool BranchRelaxation::relaxBranchInstructions() {
657 bool Changed = false;
659 // Relaxing branches involves creating new basic blocks, so re-eval
660 // end() for termination.
661 for (MachineBasicBlock &MBB : *MF) {
662 // Empty block?
663 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
664 if (Last == MBB.end())
665 continue;
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
671 // jump.
672 if (Last->isUnconditionalBranch()) {
673 // Unconditional branch destination might be unanalyzable, assume these
674 // are OK.
675 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
676 if (!isBlockInRange(*Last, *DestBB) && !TII->isTailCall(*Last) &&
677 !RelaxedUnconditionals.contains({&MBB, DestBB})) {
678 fixupUnconditionalBranch(*Last);
679 ++NumUnconditionalRelaxed;
680 Changed = true;
685 // Loop over the conditional branches.
686 MachineBasicBlock::iterator Next;
687 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
688 J != MBB.end(); J = Next) {
689 Next = std::next(J);
690 MachineInstr &MI = *J;
692 if (!MI.isConditionalBranch())
693 continue;
695 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
696 // FAULTING_OP's destination is not encoded in the instruction stream
697 // and thus never needs relaxed.
698 continue;
700 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
701 if (!isBlockInRange(MI, *DestBB)) {
702 if (Next != MBB.end() && Next->isConditionalBranch()) {
703 // If there are multiple conditional branches, this isn't an
704 // analyzable block. Split later terminators into a new block so
705 // each one will be analyzable.
707 splitBlockBeforeInstr(*Next, DestBB);
708 } else {
709 fixupConditionalBranch(MI);
710 ++NumConditionalRelaxed;
713 Changed = true;
715 // This may have modified all of the terminators, so start over.
716 Next = MBB.getFirstTerminator();
721 return Changed;
724 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
725 MF = &mf;
727 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
729 const TargetSubtargetInfo &ST = MF->getSubtarget();
730 TII = ST.getInstrInfo();
731 TM = &MF->getTarget();
733 TRI = ST.getRegisterInfo();
734 if (TRI->trackLivenessAfterRegAlloc(*MF))
735 RS.reset(new RegScavenger());
737 // Renumber all of the machine basic blocks in the function, guaranteeing that
738 // the numbers agree with the position of the block in the function.
739 MF->RenumberBlocks();
741 // Do the initial scan of the function, building up information about the
742 // sizes of each block.
743 scanFunction();
745 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
747 bool MadeChange = false;
748 while (relaxBranchInstructions())
749 MadeChange = true;
751 // After a while, this might be made debug-only, but it is not expensive.
752 verify();
754 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
756 BlockInfo.clear();
757 RelaxedUnconditionals.clear();
759 return MadeChange;