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