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//===----------------------------------------------------------------------===//
8
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>
34
35using namespace llvm;
36
37#define DEBUG_TYPE "branch-relaxation"
38
39STATISTIC(NumSplit, "Number of basic blocks split");
40STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
41STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
42
43#define BRANCH_RELAX_NAME "Branch relaxation pass"
44
45namespace {
46
47class 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;
56
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;
63
64 BasicBlockInfo() = default;
65
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(Size: PO, A: Alignment);
74
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(Size: PO, A: Alignment) + Alignment.value() - ParentAlign.value();
78 }
79 };
80
81 SmallVector<BasicBlockInfo, 16> BlockInfo;
82
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;
90
91 MachineFunction *MF = nullptr;
92 const TargetRegisterInfo *TRI = nullptr;
93 const TargetInstrInfo *TII = nullptr;
94 const TargetMachine *TM = nullptr;
95
96 bool relaxBranchInstructions();
97 void scanFunction();
98
99 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB);
100 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB,
101 const BasicBlock *BB);
102
103 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
104 MachineBasicBlock *DestBB);
105 void adjustBlockOffsets(MachineBasicBlock &Start);
106 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
107
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();
114
115public:
116 static char ID;
117
118 BranchRelaxation() : MachineFunctionPass(ID) {}
119
120 bool runOnMachineFunction(MachineFunction &MF) override;
121
122 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
123};
124
125} // end anonymous namespace
126
127char BranchRelaxation::ID = 0;
128
129char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
130
131INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
132
133/// verify - check BBOffsets, BBSizes, alignment of islands
134void 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;
142 }
143
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}));
155 }
156 }
157#endif
158}
159
160#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
161/// print block size and offset information - debugging
162LLVM_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);
167 }
168}
169#endif
170
171/// scanFunction - Do the initial scan of the function, building up
172/// information about each block.
173void BranchRelaxation::scanFunction() {
174 BlockInfo.clear();
175 BlockInfo.resize(N: MF->getNumBlockIDs());
176
177 TrampolineInsertionPoint = nullptr;
178 RelaxedUnconditionals.clear();
179
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);
187
188 if (MBB.getSectionID() != MBBSectionID::ColdSectionID)
189 TrampolineInsertionPoint = &MBB;
190 }
191
192 // Compute block offsets and known bits.
193 adjustBlockOffsets(Start&: *MF->begin());
194
195 if (TrampolineInsertionPoint == nullptr) {
196 LLVM_DEBUG(dbgs() << " No suitable trampoline insertion point found in "
197 << MF->getName() << ".\n");
198 }
199}
200
201/// computeBlockSize - Compute the size for MBB.
202uint64_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;
207}
208
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.
212unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
213 const MachineBasicBlock *MBB = MI.getParent();
214
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;
219
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(MI: *I);
224 }
225
226 return Offset;
227}
228
229void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
230 unsigned PrevNum = Start.getNumber();
231 for (auto &MBB :
232 make_range(x: std::next(x: MachineFunction::iterator(Start)), y: 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);
237
238 PrevNum = Num;
239 }
240}
241
242/// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB
243MachineBasicBlock *
244BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {
245 return createNewBlockAfter(OrigMBB&: OrigBB, BB: OrigBB.getBasicBlock());
246}
247
248/// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock
249/// and insert it after \p OrigMBB
250MachineBasicBlock *
251BranchRelaxation::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(MBBI: ++OrigMBB.getIterator(), MBB: NewBB);
256
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);
261
262 // Insert an entry into BlockInfo to align it properly with the block numbers.
263 BlockInfo.insert(I: BlockInfo.begin() + NewBB->getNumber(), Elt: BasicBlockInfo());
264
265 return NewBB;
266}
267
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.
271MachineBasicBlock *
272BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
273 MachineBasicBlock *DestBB) {
274 MachineBasicBlock *OrigBB = MI.getParent();
275
276 // Create a new MBB for the code after the OrigBB.
277 MachineBasicBlock *NewBB =
278 MF->CreateMachineBasicBlock(BB: OrigBB->getBasicBlock());
279 MF->insert(MBBI: ++OrigBB->getIterator(), MBB: NewBB);
280
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);
285
286 // Splice the instructions starting with MI over to NewBB.
287 NewBB->splice(Where: NewBB->end(), Other: OrigBB, From: MI.getIterator(), To: OrigBB->end());
288
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(MBB&: *OrigBB, DestBB: NewBB, DL: DebugLoc());
294
295 // Insert an entry into BlockInfo to align it properly with the block numbers.
296 BlockInfo.insert(I: BlockInfo.begin() + NewBB->getNumber(), Elt: BasicBlockInfo());
297
298 NewBB->transferSuccessors(FromMBB: OrigBB);
299 OrigBB->addSuccessor(Succ: NewBB);
300 OrigBB->addSuccessor(Succ: DestBB);
301
302 // Cleanup potential unconditional branch to successor block.
303 // Note that updateTerminator may change the size of the blocks.
304 OrigBB->updateTerminator(PreviousLayoutSuccessor: NewBB);
305
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(MBB: *OrigBB);
312
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(MBB: *NewBB);
316
317 // All BBOffsets following these blocks must be modified.
318 adjustBlockOffsets(Start&: *OrigBB);
319
320 // Need to fix live-in lists if we track liveness.
321 if (TRI->trackLivenessAfterRegAlloc(MF: *MF))
322 computeAndAddLiveIns(LiveRegs, MBB&: *NewBB);
323
324 ++NumSplit;
325
326 return NewBB;
327}
328
329/// isBlockInRange - Returns true if the distance between specific MI and
330/// specific BB can fit in MI's displacement field.
331bool BranchRelaxation::isBlockInRange(
332 const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
333 int64_t BrOffset = getInstrOffset(MI);
334 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
335
336 const MachineBasicBlock *SrcBB = MI.getParent();
337
338 if (TII->isBranchOffsetInRange(BranchOpc: MI.getOpcode(),
339 BrOffset: SrcBB->getSectionID() != DestBB.getSectionID()
340 ? TM->getMaxCodeSize()
341 : DestOffset - BrOffset))
342 return true;
343
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);
349
350 return false;
351}
352
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.
356bool 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;
362
363 auto insertUncondBranch = [&](MachineBasicBlock *MBB,
364 MachineBasicBlock *DestBB) {
365 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
366 int NewBrSize = 0;
367 TII->insertUnconditionalBranch(MBB&: *MBB, DestBB, DL, BytesAdded: &NewBrSize);
368 BBSize += NewBrSize;
369 };
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&: *MBB, TBB, FBB, Cond, DL, BytesAdded: &NewBrSize);
376 BBSize += NewBrSize;
377 };
378 auto removeBranch = [&](MachineBasicBlock *MBB) {
379 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
380 int RemovedSize = 0;
381 TII->removeBranch(MBB&: *MBB, BytesRemoved: &RemovedSize);
382 BBSize -= RemovedSize;
383 };
384
385 auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
386 MachineBasicBlock *NewBB) {
387 // Keep the block offsets up to date.
388 adjustBlockOffsets(Start&: *MBB);
389
390 // Need to fix live-in lists if we track liveness.
391 if (NewBB && TRI->trackLivenessAfterRegAlloc(MF: *MF))
392 computeAndAddLiveIns(LiveRegs, MBB&: *NewBB);
393 };
394
395 bool Fail = TII->analyzeBranch(MBB&: *MBB, TBB, FBB, Cond);
396 assert(!Fail && "branches to be relaxed must be analyzable");
397 (void)Fail;
398
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(OrigMBB&: *TrampolineInsertionPoint, BB: MBB->getBasicBlock());
415
416 if (isBlockInRange(MI, DestBB: *NewBB)) {
417 LLVM_DEBUG(dbgs() << " Retarget destination to trampoline at "
418 << NewBB->back());
419
420 insertUncondBranch(NewBB, TBB);
421
422 // Update the successor lists to include the trampoline.
423 MBB->replaceSuccessor(Old: TBB, New: NewBB);
424 NewBB->addSuccessor(Succ: TBB);
425
426 // Replace branch in the current (MBB) block.
427 removeBranch(MBB);
428 insertBranch(MBB, NewBB, FBB, Cond);
429
430 TrampolineInsertionPoint = NewBB;
431 finalizeBlockChanges(MBB, NewBB);
432 return true;
433 }
434
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(MBBI: NewBB);
441 }
442
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:
450
451 bool ReversedCond = !TII->reverseBranchCondition(Cond);
452 if (ReversedCond) {
453 if (FBB && isBlockInRange(MI, DestBB: *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());
464
465 removeBranch(MBB);
466 insertBranch(MBB, FBB, TBB, Cond);
467 finalizeBlockChanges(MBB, nullptr);
468 return true;
469 }
470 if (FBB) {
471 // We need to split the basic block here to obtain two long-range
472 // unconditional branches.
473 NewBB = createNewBlockAfter(OrigBB&: *MBB);
474
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(Old: FBB, New: NewBB);
479 NewBB->addSuccessor(Succ: FBB);
480 }
481
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(x: MachineFunction::iterator(MBB));
485
486 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
487 << ", invert condition and change dest. to "
488 << printMBBReference(NextBB) << '\n');
489
490 removeBranch(MBB);
491 // Insert a new conditional branch and a new unconditional branch.
492 insertBranch(MBB, &NextBB, TBB, Cond);
493
494 finalizeBlockChanges(MBB, NewBB);
495 return true;
496 }
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());
501
502 if (!FBB)
503 FBB = &(*std::next(x: MachineFunction::iterator(MBB)));
504
505 // This is the block with cond. branch and the distance to TBB is too long.
506 // beq L1
507 // L2:
508
509 // We do the following transformation:
510 // beq NewBB
511 // b L2
512 // NewBB:
513 // b L1
514 // L2:
515
516 NewBB = createNewBlockAfter(OrigBB&: *MBB);
517 insertUncondBranch(NewBB, TBB);
518
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");
525
526 // Update the successor lists according to the transformation to follow.
527 MBB->replaceSuccessor(Old: TBB, New: NewBB);
528 NewBB->addSuccessor(Succ: TBB);
529
530 // Replace branch in the current (MBB) block.
531 removeBranch(MBB);
532 insertBranch(MBB, NewBB, FBB, Cond);
533
534 finalizeBlockChanges(MBB, NewBB);
535 return true;
536}
537
538bool 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);
543
544 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
545 int64_t SrcOffset = getInstrOffset(MI);
546
547 assert(!TII->isBranchOffsetInRange(
548 MI.getOpcode(), MBB->getSectionID() != DestBB->getSectionID()
549 ? TM->getMaxCodeSize()
550 : DestOffset - SrcOffset));
551
552 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
553
554 MachineBasicBlock *BranchBB = MBB;
555
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(OrigBB&: *MBB);
560
561 // Add live outs.
562 for (const MachineBasicBlock *Succ : MBB->successors()) {
563 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
564 BranchBB->addLiveIn(RegMaskPair: LiveIn);
565 }
566
567 BranchBB->sortUniqueLiveIns();
568 BranchBB->addSuccessor(Succ: DestBB);
569 MBB->replaceSuccessor(Old: DestBB, New: BranchBB);
570 if (TrampolineInsertionPoint == MBB)
571 TrampolineInsertionPoint = BranchBB;
572 }
573
574 DebugLoc DL = MI.getDebugLoc();
575 MI.eraseFromParent();
576
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(OrigMBB&: MF->back(),
581 BB: DestBB->getBasicBlock());
582 std::prev(x: RestoreBB->getIterator())
583 ->setIsEndSection(RestoreBB->isEndSection());
584 RestoreBB->setIsEndSection(false);
585
586 TII->insertIndirectBranch(MBB&: *BranchBB, NewDestBB&: *DestBB, RestoreBB&: *RestoreBB, DL,
587 BrOffset: BranchBB->getSectionID() != DestBB->getSectionID()
588 ? TM->getMaxCodeSize()
589 : DestOffset - SrcOffset,
590 RS: RS.get());
591
592 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(MBB: *BranchBB);
593 adjustBlockOffsets(Start&: *MBB);
594
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(OrigBB&: *TrampolineInsertionPoint);
602 TII->insertUnconditionalBranch(MBB&: *NewBB, DestBB, DL: DebugLoc());
603 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(MBB: *NewBB);
604
605 // New trampolines should be inserted after NewBB.
606 TrampolineInsertionPoint = NewBB;
607
608 // Retarget the unconditional branch to the trampoline block.
609 BranchBB->replaceSuccessor(Old: DestBB, New: NewBB);
610 NewBB->addSuccessor(Succ: DestBB);
611
612 DestBB = NewBB;
613 }
614
615 // In all other cases, try to place just before DestBB.
616
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(x: 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(MBB&: *PrevBB, DestBB: FT, DL: DebugLoc());
628 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(MBB: *PrevBB);
629 }
630 // Now, RestoreBB could be placed directly before DestBB.
631 MF->splice(InsertPt: DestBB->getIterator(), MBBI: RestoreBB->getIterator());
632 // Update successors and predecessors.
633 RestoreBB->addSuccessor(Succ: DestBB);
634 BranchBB->replaceSuccessor(Old: DestBB, New: RestoreBB);
635 if (TRI->trackLivenessAfterRegAlloc(MF: *MF))
636 computeAndAddLiveIns(LiveRegs, MBB&: *RestoreBB);
637 // Compute the restore block size.
638 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(MBB: *RestoreBB);
639 // Update the offset starting from the previous block.
640 adjustBlockOffsets(Start&: *PrevBB);
641
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(V: {BranchBB, RestoreBB});
647 } else {
648 // Remove restore block if it's not required.
649 MF->erase(MBBI: RestoreBB);
650 RelaxedUnconditionals.insert(V: {BranchBB, DestBB});
651 }
652
653 return true;
654}
655
656bool BranchRelaxation::relaxBranchInstructions() {
657 bool Changed = false;
658
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;
666
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(MI: *Last)) {
676 if (!isBlockInRange(MI: *Last, DestBB: *DestBB) && !TII->isTailCall(Inst: *Last) &&
677 !RelaxedUnconditionals.contains(V: {&MBB, DestBB})) {
678 fixupUnconditionalBranch(MI&: *Last);
679 ++NumUnconditionalRelaxed;
680 Changed = true;
681 }
682 }
683 }
684
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(x: J);
690 MachineInstr &MI = *J;
691
692 if (!MI.isConditionalBranch())
693 continue;
694
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;
699
700 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
701 if (!isBlockInRange(MI, DestBB: *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.
706
707 splitBlockBeforeInstr(MI&: *Next, DestBB);
708 } else {
709 fixupConditionalBranch(MI);
710 ++NumConditionalRelaxed;
711 }
712
713 Changed = true;
714
715 // This may have modified all of the terminators, so start over.
716 Next = MBB.getFirstTerminator();
717 }
718 }
719 }
720
721 return Changed;
722}
723
724bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
725 MF = &mf;
726
727 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
728
729 const TargetSubtargetInfo &ST = MF->getSubtarget();
730 TII = ST.getInstrInfo();
731 TM = &MF->getTarget();
732
733 TRI = ST.getRegisterInfo();
734 if (TRI->trackLivenessAfterRegAlloc(MF: *MF))
735 RS.reset(p: new RegScavenger());
736
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();
740
741 // Do the initial scan of the function, building up information about the
742 // sizes of each block.
743 scanFunction();
744
745 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
746
747 bool MadeChange = false;
748 while (relaxBranchInstructions())
749 MadeChange = true;
750
751 // After a while, this might be made debug-only, but it is not expensive.
752 verify();
753
754 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
755
756 BlockInfo.clear();
757 RelaxedUnconditionals.clear();
758
759 return MadeChange;
760}
761