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/CodeGen/BranchRelaxation.h"
10#include "llvm/ADT/SmallVector.h"
11#include "llvm/ADT/Statistic.h"
12#include "llvm/CodeGen/LivePhysRegs.h"
13#include "llvm/CodeGen/MachineBasicBlock.h"
14#include "llvm/CodeGen/MachineDominators.h"
15#include "llvm/CodeGen/MachineFunction.h"
16#include "llvm/CodeGen/MachineFunctionPass.h"
17#include "llvm/CodeGen/MachineInstr.h"
18#include "llvm/CodeGen/MachinePostDominators.h"
19#include "llvm/CodeGen/RegisterScavenging.h"
20#include "llvm/CodeGen/TargetInstrInfo.h"
21#include "llvm/CodeGen/TargetRegisterInfo.h"
22#include "llvm/CodeGen/TargetSubtargetInfo.h"
23#include "llvm/Config/llvm-config.h"
24#include "llvm/IR/DebugLoc.h"
25#include "llvm/InitializePasses.h"
26#include "llvm/Pass.h"
27#include "llvm/Support/Compiler.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/Format.h"
31#include "llvm/Support/raw_ostream.h"
32#include "llvm/Target/TargetMachine.h"
33#include <cassert>
34#include <cstdint>
35#include <iterator>
36#include <memory>
37
38using namespace llvm;
39
40#define DEBUG_TYPE "branch-relaxation"
41
42STATISTIC(NumSplit, "Number of basic blocks split");
43STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
44STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
45
46#define BRANCH_RELAX_NAME "Branch relaxation pass"
47
48namespace {
49
50class BranchRelaxation {
51 /// BasicBlockInfo - Information about the offset and size of a single
52 /// basic block.
53 struct BasicBlockInfo {
54 /// Offset - Distance from the beginning of the function to the beginning
55 /// of this basic block.
56 ///
57 /// The offset is always aligned as required by the basic block.
58 unsigned Offset = 0;
59
60 /// Size - Size of the basic block in bytes. If the block contains
61 /// inline assembly, this is a worst case estimate.
62 ///
63 /// The size does not include any alignment padding whether from the
64 /// beginning of the block, or from an aligned jump table at the end.
65 unsigned Size = 0;
66
67 BasicBlockInfo() = default;
68
69 /// Compute the offset immediately following this block. \p MBB is the next
70 /// block.
71 unsigned postOffset(const MachineBasicBlock &MBB) const {
72 const unsigned PO = Offset + Size;
73 const Align Alignment = MBB.getAlignment();
74 const Align ParentAlign = MBB.getParent()->getAlignment();
75 if (Alignment <= ParentAlign)
76 return alignTo(Size: PO, A: Alignment);
77
78 // The alignment of this MBB is larger than the function's alignment, so
79 // we can't tell whether or not it will insert nops. Assume that it will.
80 return alignTo(Size: PO, A: Alignment) + Alignment.value() - ParentAlign.value();
81 }
82 };
83
84 SmallVector<BasicBlockInfo, 16> BlockInfo;
85
86 // The basic block after which trampolines are inserted. This is the last
87 // basic block that isn't in the cold section.
88 MachineBasicBlock *TrampolineInsertionPoint = nullptr;
89 SmallDenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>>
90 RelaxedUnconditionals;
91 std::unique_ptr<RegScavenger> RS;
92 LivePhysRegs LiveRegs;
93
94 MachineFunction *MF = nullptr;
95 const TargetRegisterInfo *TRI = nullptr;
96 const TargetInstrInfo *TII = nullptr;
97 const TargetMachine *TM = nullptr;
98
99 bool relaxBranchInstructions();
100 void scanFunction();
101
102 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB);
103 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB,
104 const BasicBlock *BB);
105
106 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
107 MachineBasicBlock *DestBB);
108 void adjustBlockOffsets(MachineBasicBlock &Start);
109 void adjustBlockOffsets(MachineBasicBlock &Start,
110 MachineFunction::iterator End);
111 bool isBlockInRange(const MachineInstr &MI,
112 const MachineBasicBlock &BB) const;
113
114 bool fixupConditionalBranch(MachineInstr &MI);
115 bool fixupUnconditionalBranch(MachineInstr &MI);
116 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
117 unsigned getInstrOffset(const MachineInstr &MI) const;
118 void dumpBBs();
119 void verify();
120
121public:
122 bool run(MachineFunction &MF);
123};
124
125class BranchRelaxationLegacy : public MachineFunctionPass {
126public:
127 static char ID;
128
129 BranchRelaxationLegacy() : MachineFunctionPass(ID) {}
130
131 bool runOnMachineFunction(MachineFunction &MF) override {
132 return BranchRelaxation().run(MF);
133 }
134
135 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
136};
137
138} // end anonymous namespace
139
140char BranchRelaxationLegacy::ID = 0;
141
142char &llvm::BranchRelaxationPassID = BranchRelaxationLegacy::ID;
143
144INITIALIZE_PASS(BranchRelaxationLegacy, DEBUG_TYPE, BRANCH_RELAX_NAME, false,
145 false)
146
147/// verify - check BBOffsets, BBSizes, alignment of islands
148void BranchRelaxation::verify() {
149#ifndef NDEBUG
150 unsigned PrevNum = MF->begin()->getNumber();
151 for (MachineBasicBlock &MBB : *MF) {
152 const unsigned Num = MBB.getNumber();
153 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
154 assert(BlockInfo[Num].Size == computeBlockSize(MBB));
155 PrevNum = Num;
156 }
157
158 for (MachineBasicBlock &MBB : *MF) {
159 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
160 J != MBB.end(); J = std::next(J)) {
161 MachineInstr &MI = *J;
162 if (!MI.isConditionalBranch() && !MI.isUnconditionalBranch())
163 continue;
164 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
165 continue;
166 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
167 assert(isBlockInRange(MI, *DestBB) ||
168 RelaxedUnconditionals.contains({&MBB, DestBB}));
169 }
170 }
171#endif
172}
173
174#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
175/// print block size and offset information - debugging
176LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
177 for (auto &MBB : *MF) {
178 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
179 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
180 << format("size=%#x\n", BBI.Size);
181 }
182}
183#endif
184
185/// scanFunction - Do the initial scan of the function, building up
186/// information about each block.
187void BranchRelaxation::scanFunction() {
188 BlockInfo.clear();
189 BlockInfo.resize(N: MF->getNumBlockIDs());
190
191 TrampolineInsertionPoint = nullptr;
192 RelaxedUnconditionals.clear();
193
194 // First thing, compute the size of all basic blocks, and see if the function
195 // has any inline assembly in it. If so, we have to be conservative about
196 // alignment assumptions, as we don't know for sure the size of any
197 // instructions in the inline assembly. At the same time, place the
198 // trampoline insertion point at the end of the hot portion of the function.
199 for (MachineBasicBlock &MBB : *MF) {
200 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
201
202 if (MBB.getSectionID() != MBBSectionID::ColdSectionID)
203 TrampolineInsertionPoint = &MBB;
204 }
205
206 // Compute block offsets and known bits.
207 adjustBlockOffsets(Start&: *MF->begin());
208
209 if (TrampolineInsertionPoint == nullptr) {
210 LLVM_DEBUG(dbgs() << " No suitable trampoline insertion point found in "
211 << MF->getName() << ".\n");
212 }
213}
214
215/// computeBlockSize - Compute the size for MBB.
216uint64_t
217BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
218 uint64_t Size = 0;
219 for (const MachineInstr &MI : MBB)
220 Size += TII->getInstSizeInBytes(MI);
221 return Size;
222}
223
224/// getInstrOffset - Return the current offset of the specified machine
225/// instruction from the start of the function. This offset changes as stuff is
226/// moved around inside the function.
227unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
228 const MachineBasicBlock *MBB = MI.getParent();
229
230 // The offset is composed of two things: the sum of the sizes of all MBB's
231 // before this instruction's block, and the offset from the start of the block
232 // it is in.
233 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
234
235 // Sum instructions before MI in MBB.
236 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
237 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
238 Offset += TII->getInstSizeInBytes(MI: *I);
239 }
240
241 return Offset;
242}
243
244void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
245 adjustBlockOffsets(Start, End: MF->end());
246}
247
248void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start,
249 MachineFunction::iterator End) {
250 unsigned PrevNum = Start.getNumber();
251 for (auto &MBB :
252 make_range(x: std::next(x: MachineFunction::iterator(Start)), y: End)) {
253 unsigned Num = MBB.getNumber();
254 // Get the offset and known bits at the end of the layout predecessor.
255 // Include the alignment of the current block.
256 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
257
258 PrevNum = Num;
259 }
260}
261
262/// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB
263MachineBasicBlock *
264BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {
265 return createNewBlockAfter(OrigMBB&: OrigBB, BB: OrigBB.getBasicBlock());
266}
267
268/// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock
269/// and insert it after \p OrigMBB
270MachineBasicBlock *
271BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigMBB,
272 const BasicBlock *BB) {
273 // Create a new MBB for the code after the OrigBB.
274 MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);
275 MF->insert(MBBI: ++OrigMBB.getIterator(), MBB: NewBB);
276
277 // Place the new block in the same section as OrigBB
278 NewBB->setSectionID(OrigMBB.getSectionID());
279 NewBB->setIsEndSection(OrigMBB.isEndSection());
280 OrigMBB.setIsEndSection(false);
281
282 // Insert an entry into BlockInfo to align it properly with the block numbers.
283 BlockInfo.insert(I: BlockInfo.begin() + NewBB->getNumber(), Elt: BasicBlockInfo());
284
285 return NewBB;
286}
287
288/// Split the basic block containing MI into two blocks, which are joined by
289/// an unconditional branch. Update data structures and renumber blocks to
290/// account for this change and returns the newly created block.
291MachineBasicBlock *
292BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
293 MachineBasicBlock *DestBB) {
294 MachineBasicBlock *OrigBB = MI.getParent();
295
296 // Create a new MBB for the code after the OrigBB.
297 MachineBasicBlock *NewBB =
298 MF->CreateMachineBasicBlock(BB: OrigBB->getBasicBlock());
299 MF->insert(MBBI: ++OrigBB->getIterator(), MBB: NewBB);
300
301 // Place the new block in the same section as OrigBB.
302 NewBB->setSectionID(OrigBB->getSectionID());
303 NewBB->setIsEndSection(OrigBB->isEndSection());
304 OrigBB->setIsEndSection(false);
305
306 // Splice the instructions starting with MI over to NewBB.
307 NewBB->splice(Where: NewBB->end(), Other: OrigBB, From: MI.getIterator(), To: OrigBB->end());
308
309 // Add an unconditional branch from OrigBB to NewBB.
310 // Note the new unconditional branch is not being recorded.
311 // There doesn't seem to be meaningful DebugInfo available; this doesn't
312 // correspond to anything in the source.
313 TII->insertUnconditionalBranch(MBB&: *OrigBB, DestBB: NewBB, DL: DebugLoc());
314
315 // Insert an entry into BlockInfo to align it properly with the block numbers.
316 BlockInfo.insert(I: BlockInfo.begin() + NewBB->getNumber(), Elt: BasicBlockInfo());
317
318 NewBB->transferSuccessors(FromMBB: OrigBB);
319 OrigBB->addSuccessor(Succ: NewBB);
320 OrigBB->addSuccessor(Succ: DestBB);
321
322 // Cleanup potential unconditional branch to successor block.
323 // Note that updateTerminator may change the size of the blocks.
324 OrigBB->updateTerminator(PreviousLayoutSuccessor: NewBB);
325
326 // Figure out how large the OrigBB is. As the first half of the original
327 // block, it cannot contain a tablejump. The size includes
328 // the new jump we added. (It should be possible to do this without
329 // recounting everything, but it's very confusing, and this is rarely
330 // executed.)
331 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(MBB: *OrigBB);
332
333 // Figure out how large the NewMBB is. As the second half of the original
334 // block, it may contain a tablejump.
335 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(MBB: *NewBB);
336
337 // Update the offset of the new block.
338 adjustBlockOffsets(Start&: *OrigBB, End: std::next(x: NewBB->getIterator()));
339
340 // Need to fix live-in lists if we track liveness.
341 if (TRI->trackLivenessAfterRegAlloc(MF: *MF))
342 computeAndAddLiveIns(LiveRegs, MBB&: *NewBB);
343
344 ++NumSplit;
345
346 return NewBB;
347}
348
349/// isBlockInRange - Returns true if the distance between specific MI and
350/// specific BB can fit in MI's displacement field.
351bool BranchRelaxation::isBlockInRange(const MachineInstr &MI,
352 const MachineBasicBlock &DestBB) const {
353 int64_t BrOffset = getInstrOffset(MI);
354 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
355
356 const MachineBasicBlock *SrcBB = MI.getParent();
357
358 if (TII->isBranchOffsetInRange(BranchOpc: MI.getOpcode(),
359 BrOffset: SrcBB->getSectionID() != DestBB.getSectionID()
360 ? TM->getMaxCodeSize()
361 : DestOffset - BrOffset))
362 return true;
363
364 LLVM_DEBUG(dbgs() << "Out of range branch to destination "
365 << printMBBReference(DestBB) << " from "
366 << printMBBReference(*MI.getParent()) << " to "
367 << DestOffset << " offset " << DestOffset - BrOffset << '\t'
368 << MI);
369
370 return false;
371}
372
373/// fixupConditionalBranch - Fix up a conditional branch whose destination is
374/// too far away to fit in its displacement field. It is converted to an inverse
375/// conditional branch + an unconditional branch to the destination.
376bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
377 DebugLoc DL = MI.getDebugLoc();
378 MachineBasicBlock *MBB = MI.getParent();
379 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
380 MachineBasicBlock *NewBB = nullptr;
381 SmallVector<MachineOperand, 4> Cond;
382
383 auto insertUncondBranch = [&](MachineBasicBlock *MBB,
384 MachineBasicBlock *DestBB) {
385 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
386 int NewBrSize = 0;
387 TII->insertUnconditionalBranch(MBB&: *MBB, DestBB, DL, BytesAdded: &NewBrSize);
388 BBSize += NewBrSize;
389 };
390 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
391 MachineBasicBlock *FBB,
392 SmallVectorImpl<MachineOperand> &Cond) {
393 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
394 int NewBrSize = 0;
395 TII->insertBranch(MBB&: *MBB, TBB, FBB, Cond, DL, BytesAdded: &NewBrSize);
396 BBSize += NewBrSize;
397 };
398 auto removeBranch = [&](MachineBasicBlock *MBB) {
399 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
400 int RemovedSize = 0;
401 TII->removeBranch(MBB&: *MBB, BytesRemoved: &RemovedSize);
402 BBSize -= RemovedSize;
403 };
404
405 // Populate the block offset and live-ins for a new basic block.
406 auto updateOffsetAndLiveness = [&](MachineBasicBlock *NewBB) {
407 assert(NewBB != nullptr && "can't populate offset for nullptr");
408
409 // Keep the block offsets approximately up to date. While they will be
410 // slight underestimates, we will update them appropriately in the next
411 // scan through the function.
412 adjustBlockOffsets(Start&: *std::prev(x: NewBB->getIterator()),
413 End: std::next(x: NewBB->getIterator()));
414
415 // Need to fix live-in lists if we track liveness.
416 if (TRI->trackLivenessAfterRegAlloc(MF: *MF))
417 computeAndAddLiveIns(LiveRegs, MBB&: *NewBB);
418 };
419
420 bool Fail = TII->analyzeBranch(MBB&: *MBB, TBB, FBB, Cond);
421 assert(!Fail && "branches to be relaxed must be analyzable");
422 (void)Fail;
423
424 // Since cross-section conditional branches to the cold section are rarely
425 // taken, try to avoid inverting the condition. Instead, add a "trampoline
426 // branch", which unconditionally branches to the branch destination. Place
427 // the trampoline branch at the end of the function and retarget the
428 // conditional branch to the trampoline.
429 // tbz L1
430 // =>
431 // tbz L1Trampoline
432 // ...
433 // L1Trampoline: b L1
434 if (MBB->getSectionID() != TBB->getSectionID() &&
435 TBB->getSectionID() == MBBSectionID::ColdSectionID &&
436 TrampolineInsertionPoint != nullptr) {
437 // If the insertion point is out of range, we can't put a trampoline there.
438 NewBB =
439 createNewBlockAfter(OrigMBB&: *TrampolineInsertionPoint, BB: MBB->getBasicBlock());
440
441 if (isBlockInRange(MI, DestBB: *NewBB)) {
442 LLVM_DEBUG(dbgs() << " Retarget destination to trampoline at "
443 << NewBB->back());
444
445 insertUncondBranch(NewBB, TBB);
446
447 // Update the successor lists to include the trampoline.
448 MBB->replaceSuccessor(Old: TBB, New: NewBB);
449 NewBB->addSuccessor(Succ: TBB);
450
451 // Replace branch in the current (MBB) block.
452 removeBranch(MBB);
453 insertBranch(MBB, NewBB, FBB, Cond);
454
455 TrampolineInsertionPoint = NewBB;
456 updateOffsetAndLiveness(NewBB);
457 return true;
458 }
459
460 LLVM_DEBUG(
461 dbgs() << " Trampoline insertion point out of range for Bcc from "
462 << printMBBReference(*MBB) << " to " << printMBBReference(*TBB)
463 << ".\n");
464 TrampolineInsertionPoint->setIsEndSection(NewBB->isEndSection());
465 MF->erase(MBBI: NewBB);
466 NewBB = nullptr;
467 }
468
469 // Add an unconditional branch to the destination and invert the branch
470 // condition to jump over it:
471 // tbz L1
472 // =>
473 // tbnz L2
474 // b L1
475 // L2:
476
477 bool ReversedCond = !TII->reverseBranchCondition(Cond);
478 if (ReversedCond) {
479 if (FBB && isBlockInRange(MI, DestBB: *FBB)) {
480 // Last MI in the BB is an unconditional branch. We can simply invert the
481 // condition and swap destinations:
482 // beq L1
483 // b L2
484 // =>
485 // bne L2
486 // b L1
487 LLVM_DEBUG(dbgs() << " Invert condition and swap "
488 "its destination with "
489 << MBB->back());
490
491 removeBranch(MBB);
492 insertBranch(MBB, FBB, TBB, Cond);
493 return true;
494 }
495 if (FBB) {
496 // If we get here with a MBB which ends like this:
497 //
498 // bb.1:
499 // successors: %bb.2;
500 // ...
501 // BNE $x1, $x0, %bb.2
502 // PseudoBR %bb.2
503 //
504 // Just remove conditional branch.
505 if (TBB == FBB) {
506 removeBranch(MBB);
507 insertUncondBranch(MBB, TBB);
508 return true;
509 }
510 // We need to split the basic block here to obtain two long-range
511 // unconditional branches.
512 NewBB = createNewBlockAfter(OrigBB&: *MBB);
513
514 insertUncondBranch(NewBB, FBB);
515 // Update the succesor lists according to the transformation to follow.
516 // Do it here since if there's no split, no update is needed.
517 MBB->replaceSuccessor(Old: FBB, New: NewBB);
518 NewBB->addSuccessor(Succ: FBB);
519 updateOffsetAndLiveness(NewBB);
520 }
521
522 // We now have an appropriate fall-through block in place (either naturally
523 // or just created), so we can use the inverted the condition.
524 MachineBasicBlock &NextBB = *std::next(x: MachineFunction::iterator(MBB));
525
526 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
527 << ", invert condition and change dest. to "
528 << printMBBReference(NextBB) << '\n');
529
530 removeBranch(MBB);
531 // Insert a new conditional branch and a new unconditional branch.
532 insertBranch(MBB, &NextBB, TBB, Cond);
533 return true;
534 }
535 // Branch cond can't be inverted.
536 // In this case we always add a block after the MBB.
537 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
538 << " Insert a new BB after " << MBB->back());
539
540 if (!FBB)
541 FBB = &(*std::next(x: MachineFunction::iterator(MBB)));
542
543 // This is the block with cond. branch and the distance to TBB is too long.
544 // beq L1
545 // L2:
546
547 // We do the following transformation:
548 // beq NewBB
549 // b L2
550 // NewBB:
551 // b L1
552 // L2:
553
554 NewBB = createNewBlockAfter(OrigBB&: *MBB);
555 insertUncondBranch(NewBB, TBB);
556
557 LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "
558 << printMBBReference(*NewBB)
559 << " Keep the exiting condition.\n"
560 << " Insert B to " << printMBBReference(*FBB) << ".\n"
561 << " In the new BB: Insert B to "
562 << printMBBReference(*TBB) << ".\n");
563
564 // Update the successor lists according to the transformation to follow.
565 MBB->replaceSuccessor(Old: TBB, New: NewBB);
566 NewBB->addSuccessor(Succ: TBB);
567
568 // Replace branch in the current (MBB) block.
569 removeBranch(MBB);
570 insertBranch(MBB, NewBB, FBB, Cond);
571
572 updateOffsetAndLiveness(NewBB);
573 return true;
574}
575
576bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
577 MachineBasicBlock *MBB = MI.getParent();
578 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
579 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
580
581 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
582 int64_t SrcOffset = getInstrOffset(MI);
583
584 assert(!TII->isBranchOffsetInRange(
585 MI.getOpcode(), MBB->getSectionID() != DestBB->getSectionID()
586 ? TM->getMaxCodeSize()
587 : DestOffset - SrcOffset));
588
589 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
590
591 MachineBasicBlock *BranchBB = MBB;
592
593 // If this was an expanded conditional branch, there is already a single
594 // unconditional branch in a block.
595 if (!MBB->empty()) {
596 BranchBB = createNewBlockAfter(OrigBB&: *MBB);
597
598 // Add live outs.
599 for (const MachineBasicBlock *Succ : MBB->successors()) {
600 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
601 BranchBB->addLiveIn(RegMaskPair: LiveIn);
602 }
603
604 BranchBB->sortUniqueLiveIns();
605 BranchBB->addSuccessor(Succ: DestBB);
606 MBB->replaceSuccessor(Old: DestBB, New: BranchBB);
607 if (TrampolineInsertionPoint == MBB)
608 TrampolineInsertionPoint = BranchBB;
609 }
610
611 DebugLoc DL = MI.getDebugLoc();
612 MI.eraseFromParent();
613
614 // Create the optional restore block and, initially, place it at the end of
615 // function. That block will be placed later if it's used; otherwise, it will
616 // be erased.
617 MachineBasicBlock *RestoreBB =
618 createNewBlockAfter(OrigMBB&: MF->back(), BB: DestBB->getBasicBlock());
619 std::prev(x: RestoreBB->getIterator())
620 ->setIsEndSection(RestoreBB->isEndSection());
621 RestoreBB->setIsEndSection(false);
622
623 TII->insertIndirectBranch(MBB&: *BranchBB, NewDestBB&: *DestBB, RestoreBB&: *RestoreBB, DL,
624 BrOffset: BranchBB->getSectionID() != DestBB->getSectionID()
625 ? TM->getMaxCodeSize()
626 : DestOffset - SrcOffset,
627 RS: RS.get());
628
629 // Update the block size and offset for the BranchBB (which may be newly
630 // created).
631 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(MBB: *BranchBB);
632 adjustBlockOffsets(Start&: *MBB, End: std::next(x: BranchBB->getIterator()));
633
634 // If RestoreBB is required, place it appropriately.
635 if (!RestoreBB->empty()) {
636 // If the jump is Cold -> Hot, don't place the restore block (which is
637 // cold) in the middle of the function. Place it at the end.
638 if (MBB->getSectionID() == MBBSectionID::ColdSectionID &&
639 DestBB->getSectionID() != MBBSectionID::ColdSectionID) {
640 MachineBasicBlock *NewBB = createNewBlockAfter(OrigBB&: *TrampolineInsertionPoint);
641 TII->insertUnconditionalBranch(MBB&: *NewBB, DestBB, DL: DebugLoc());
642 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(MBB: *NewBB);
643 adjustBlockOffsets(Start&: *TrampolineInsertionPoint,
644 End: std::next(x: NewBB->getIterator()));
645
646 // New trampolines should be inserted after NewBB.
647 TrampolineInsertionPoint = NewBB;
648
649 // Retarget the unconditional branch to the trampoline block.
650 BranchBB->replaceSuccessor(Old: DestBB, New: NewBB);
651 NewBB->addSuccessor(Succ: DestBB);
652
653 DestBB = NewBB;
654 }
655
656 // In all other cases, try to place just before DestBB.
657
658 // TODO: For multiple far branches to the same destination, there are
659 // chances that some restore blocks could be shared if they clobber the
660 // same registers and share the same restore sequence. So far, those
661 // restore blocks are just duplicated for each far branch.
662 assert(!DestBB->isEntryBlock());
663 MachineBasicBlock *PrevBB = &*std::prev(x: DestBB->getIterator());
664 // Fall through only if PrevBB has no unconditional branch as one of its
665 // terminators.
666 if (auto *FT = PrevBB->getLogicalFallThrough()) {
667 assert(FT == DestBB);
668 TII->insertUnconditionalBranch(MBB&: *PrevBB, DestBB: FT, DL: DebugLoc());
669 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(MBB: *PrevBB);
670 }
671 // Now, RestoreBB could be placed directly before DestBB.
672 MF->splice(InsertPt: DestBB->getIterator(), MBBI: RestoreBB->getIterator());
673 // Update successors and predecessors.
674 RestoreBB->addSuccessor(Succ: DestBB);
675 BranchBB->replaceSuccessor(Old: DestBB, New: RestoreBB);
676 if (TRI->trackLivenessAfterRegAlloc(MF: *MF))
677 computeAndAddLiveIns(LiveRegs, MBB&: *RestoreBB);
678 // Compute the restore block size.
679 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(MBB: *RestoreBB);
680 // Update the estimated offset for the restore block.
681 adjustBlockOffsets(Start&: *PrevBB, End: DestBB->getIterator());
682
683 // Fix up section information for RestoreBB and DestBB
684 RestoreBB->setSectionID(DestBB->getSectionID());
685 RestoreBB->setIsBeginSection(DestBB->isBeginSection());
686 DestBB->setIsBeginSection(false);
687 RelaxedUnconditionals.insert(V: {BranchBB, RestoreBB});
688 } else {
689 // Remove restore block if it's not required.
690 MF->erase(MBBI: RestoreBB);
691 RelaxedUnconditionals.insert(V: {BranchBB, DestBB});
692 }
693
694 return true;
695}
696
697bool BranchRelaxation::relaxBranchInstructions() {
698 bool Changed = false;
699
700 // Relaxing branches involves creating new basic blocks, so re-eval
701 // end() for termination.
702 for (MachineBasicBlock &MBB : *MF) {
703 // Empty block?
704 MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
705 if (Last == MBB.end())
706 continue;
707
708 // Expand the unconditional branch first if necessary. If there is a
709 // conditional branch, this will end up changing the branch destination of
710 // it to be over the newly inserted indirect branch block, which may avoid
711 // the need to try expanding the conditional branch first, saving an extra
712 // jump.
713 if (Last->isUnconditionalBranch()) {
714 // Unconditional branch destination might be unanalyzable, assume these
715 // are OK.
716 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI: *Last)) {
717 if (!isBlockInRange(MI: *Last, DestBB: *DestBB) && !TII->isTailCall(Inst: *Last) &&
718 !RelaxedUnconditionals.contains(V: {&MBB, DestBB})) {
719 fixupUnconditionalBranch(MI&: *Last);
720 ++NumUnconditionalRelaxed;
721 Changed = true;
722 }
723 }
724 }
725
726 // Loop over the conditional branches.
727 MachineBasicBlock::iterator Next;
728 for (MachineBasicBlock::iterator J = MBB.getFirstTerminator();
729 J != MBB.end(); J = Next) {
730 Next = std::next(x: J);
731 MachineInstr &MI = *J;
732
733 if (!MI.isConditionalBranch())
734 continue;
735
736 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
737 // FAULTING_OP's destination is not encoded in the instruction stream
738 // and thus never needs relaxed.
739 continue;
740
741 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
742 if (!isBlockInRange(MI, DestBB: *DestBB)) {
743 if (Next != MBB.end() && Next->isConditionalBranch()) {
744 // If there are multiple conditional branches, this isn't an
745 // analyzable block. Split later terminators into a new block so
746 // each one will be analyzable.
747
748 splitBlockBeforeInstr(MI&: *Next, DestBB);
749 } else {
750 fixupConditionalBranch(MI);
751 ++NumConditionalRelaxed;
752 }
753
754 Changed = true;
755
756 // This may have modified all of the terminators, so start over.
757 Next = MBB.getFirstTerminator();
758 }
759 }
760 }
761
762 // If we relaxed a branch, we must recompute offsets for *all* basic blocks.
763 // Otherwise, we may underestimate branch distances and fail to relax a branch
764 // that has been pushed out of range.
765 if (Changed)
766 adjustBlockOffsets(Start&: MF->front());
767
768 return Changed;
769}
770
771PreservedAnalyses
772BranchRelaxationPass::run(MachineFunction &MF,
773 MachineFunctionAnalysisManager &MFAM) {
774 auto *MDT = MFAM.getCachedResult<MachineDominatorTreeAnalysis>(IR&: MF);
775 auto *MPDT = MFAM.getCachedResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
776
777 if (BranchRelaxation().run(MF))
778 return getMachineFunctionPassPreservedAnalyses();
779
780 if (MDT)
781 MDT->updateBlockNumbers();
782 if (MPDT)
783 MPDT->updateBlockNumbers();
784 return PreservedAnalyses::all();
785}
786
787bool BranchRelaxation::run(MachineFunction &mf) {
788 MF = &mf;
789
790 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
791
792 const TargetSubtargetInfo &ST = MF->getSubtarget();
793 TII = ST.getInstrInfo();
794 TM = &MF->getTarget();
795
796 TRI = ST.getRegisterInfo();
797 if (TRI->trackLivenessAfterRegAlloc(MF: *MF))
798 RS.reset(p: new RegScavenger());
799
800 // Renumber all of the machine basic blocks in the function, guaranteeing that
801 // the numbers agree with the position of the block in the function.
802 MF->RenumberBlocks();
803
804 // Do the initial scan of the function, building up information about the
805 // sizes of each block.
806 scanFunction();
807
808 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
809
810 bool MadeChange = false;
811 while (relaxBranchInstructions())
812 MadeChange = true;
813
814 // After a while, this might be made debug-only, but it is not expensive.
815 verify();
816
817 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
818
819 BlockInfo.clear();
820 RelaxedUnconditionals.clear();
821
822 return MadeChange;
823}
824