LLVM 19.0.0git
BranchRelaxation.cpp
Go to the documentation of this file.
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
10#include "llvm/ADT/Statistic.h"
20#include "llvm/Config/llvm-config.h"
21#include "llvm/IR/DebugLoc.h"
23#include "llvm/Pass.h"
25#include "llvm/Support/Debug.h"
27#include "llvm/Support/Format.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(PO, 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(PO, Alignment) + Alignment.value() - ParentAlign.value();
78 }
79 };
80
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;
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) {
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(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
189 TrampolineInsertionPoint = &MBB;
190 }
191
192 // Compute block offsets and known bits.
193 adjustBlockOffsets(*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(*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(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);
237
238 PrevNum = Num;
239 }
240}
241
242/// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB
244BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {
245 return createNewBlockAfter(OrigBB, OrigBB.getBasicBlock());
246}
247
248/// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock
249/// and insert it after \p OrigMBB
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(++OrigMBB.getIterator(), 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(BlockInfo.begin() + NewBB->getNumber(), 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.
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(OrigBB->getBasicBlock());
279 MF->insert(++OrigBB->getIterator(), 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(NewBB->end(), OrigBB, MI.getIterator(), 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(*OrigBB, NewBB, DebugLoc());
294
295 // Insert an entry into BlockInfo to align it properly with the block numbers.
296 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
297
298 NewBB->transferSuccessors(OrigBB);
299 OrigBB->addSuccessor(NewBB);
300 OrigBB->addSuccessor(DestBB);
301
302 // Cleanup potential unconditional branch to successor block.
303 // Note that updateTerminator may change the size of the blocks.
304 OrigBB->updateTerminator(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(*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(*NewBB);
316
317 // All BBOffsets following these blocks must be modified.
318 adjustBlockOffsets(*OrigBB);
319
320 // Need to fix live-in lists if we track liveness.
321 if (TRI->trackLivenessAfterRegAlloc(*MF))
322 computeAndAddLiveIns(LiveRegs, *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(MI.getOpcode(),
339 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;
362
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;
369 };
370 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
373 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
374 int NewBrSize = 0;
375 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &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, &RemovedSize);
382 BBSize -= RemovedSize;
383 };
384
385 auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
386 MachineBasicBlock *NewBB) {
387 // Keep the block offsets up to date.
388 adjustBlockOffsets(*MBB);
389
390 // Need to fix live-in lists if we track liveness.
391 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
392 computeAndAddLiveIns(LiveRegs, *NewBB);
393 };
394
395 bool Fail = TII->analyzeBranch(*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() &&
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());
415
416 if (isBlockInRange(MI, *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(TBB, NewBB);
424 NewBB->addSuccessor(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
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);
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, *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(*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(FBB, NewBB);
479 NewBB->addSuccessor(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(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(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(*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(TBB, NewBB);
528 NewBB->addSuccessor(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();
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(*MBB);
560
561 // Add live outs.
562 for (const MachineBasicBlock *Succ : MBB->successors()) {
563 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
564 BranchBB->addLiveIn(LiveIn);
565 }
566
567 BranchBB->sortUniqueLiveIns();
568 BranchBB->addSuccessor(DestBB);
569 MBB->replaceSuccessor(DestBB, 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(MF->back(),
581 DestBB->getBasicBlock());
582 std::prev(RestoreBB->getIterator())
583 ->setIsEndSection(RestoreBB->isEndSection());
584 RestoreBB->setIsEndSection(false);
585
586 TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB, DL,
587 BranchBB->getSectionID() != DestBB->getSectionID()
588 ? TM->getMaxCodeSize()
589 : DestOffset - SrcOffset,
590 RS.get());
591
592 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);
593 adjustBlockOffsets(*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.
601 MachineBasicBlock *NewBB = createNewBlockAfter(*TrampolineInsertionPoint);
602 TII->insertUnconditionalBranch(*NewBB, DestBB, DebugLoc());
603 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*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(DestBB, NewBB);
610 NewBB->addSuccessor(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(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);
629 }
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);
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({BranchBB, RestoreBB});
647 } else {
648 // Remove restore block if it's not required.
649 MF->erase(RestoreBB);
650 RelaxedUnconditionals.insert({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?
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(*Last)) {
676 if (!isBlockInRange(*Last, *DestBB) && !TII->isTailCall(*Last) &&
677 !RelaxedUnconditionals.contains({&MBB, DestBB})) {
678 fixupUnconditionalBranch(*Last);
679 ++NumUnconditionalRelaxed;
680 Changed = true;
681 }
682 }
683 }
684
685 // Loop over the conditional branches.
688 J != MBB.end(); J = Next) {
689 Next = std::next(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)) {
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(*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))
735 RS.reset(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}
#define Fail
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define BRANCH_RELAX_NAME
#define DEBUG_TYPE
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Size
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
ppc ctr loops verify
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
This file declares the machine register scavenger class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
A debug info location.
Definition: DebugLoc.h:33
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
bool isTailCall(const MachineInstr &MI) const override
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
void setIsEndSection(bool V=true)
MachineBasicBlock * getLogicalFallThrough()
Return the fallthrough block if the block can implicitly transfer control to it's successor,...
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
MBBSectionID getSectionID() const
Returns the section ID of this basic block.
bool isEntryBlock() const
Returns true if this is the entry block of the function.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
void setSectionID(MBBSectionID V)
Sets the section ID for this basic block.
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
bool isBeginSection() const
Returns true if this block begins any section.
iterator_range< succ_iterator > successors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
bool isEndSection() const
Returns true if this block ends any section.
Align getAlignment() const
Return alignment of the basic block.
void setIsBeginSection(bool V=true)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Align getAlignment() const
getAlignment - Return the alignment of the function.
Representation of each machine instruction.
Definition: MachineInstr.h:69
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:76
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
self_iterator getIterator()
Definition: ilist_node.h:109
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
char & BranchRelaxationPassID
BranchRelaxation - This pass replaces branches that need to jump further than is supported by a branc...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
BasicBlockInfo - Information about the offset and size of a single basic block.
unsigned Size
Size - Size of the basic block in bytes.
unsigned Offset
Offset - Distance from the beginning of the function to the beginning of this basic block.
static const MBBSectionID ColdSectionID
Pair of physical register and lane mask.