LLVM 17.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"
29#include <cassert>
30#include <cstdint>
31#include <iterator>
32#include <memory>
33
34using namespace llvm;
35
36#define DEBUG_TYPE "branch-relaxation"
37
38STATISTIC(NumSplit, "Number of basic blocks split");
39STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
40STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
41
42#define BRANCH_RELAX_NAME "Branch relaxation pass"
43
44namespace {
45
46class BranchRelaxation : public MachineFunctionPass {
47 /// BasicBlockInfo - Information about the offset and size of a single
48 /// basic block.
49 struct BasicBlockInfo {
50 /// Offset - Distance from the beginning of the function to the beginning
51 /// of this basic block.
52 ///
53 /// The offset is always aligned as required by the basic block.
54 unsigned Offset = 0;
55
56 /// Size - Size of the basic block in bytes. If the block contains
57 /// inline assembly, this is a worst case estimate.
58 ///
59 /// The size does not include any alignment padding whether from the
60 /// beginning of the block, or from an aligned jump table at the end.
61 unsigned Size = 0;
62
63 BasicBlockInfo() = default;
64
65 /// Compute the offset immediately following this block. \p MBB is the next
66 /// block.
67 unsigned postOffset(const MachineBasicBlock &MBB) const {
68 const unsigned PO = Offset + Size;
69 const Align Alignment = MBB.getAlignment();
70 const Align ParentAlign = MBB.getParent()->getAlignment();
71 if (Alignment <= ParentAlign)
72 return alignTo(PO, Alignment);
73
74 // The alignment of this MBB is larger than the function's alignment, so we
75 // can't tell whether or not it will insert nops. Assume that it will.
76 return alignTo(PO, Alignment) + Alignment.value() - ParentAlign.value();
77 }
78 };
79
81 std::unique_ptr<RegScavenger> RS;
82 LivePhysRegs LiveRegs;
83
86 const TargetInstrInfo *TII;
87
88 bool relaxBranchInstructions();
89 void scanFunction();
90
91 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB);
92 MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &OrigMBB,
93 const BasicBlock *BB);
94
95 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
96 MachineBasicBlock *DestBB);
97 void adjustBlockOffsets(MachineBasicBlock &Start);
98 bool isBlockInRange(const MachineInstr &MI, const MachineBasicBlock &BB) const;
99
100 bool fixupConditionalBranch(MachineInstr &MI);
101 bool fixupUnconditionalBranch(MachineInstr &MI);
102 uint64_t computeBlockSize(const MachineBasicBlock &MBB) const;
103 unsigned getInstrOffset(const MachineInstr &MI) const;
104 void dumpBBs();
105 void verify();
106
107public:
108 static char ID;
109
110 BranchRelaxation() : MachineFunctionPass(ID) {}
111
112 bool runOnMachineFunction(MachineFunction &MF) override;
113
114 StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
115};
116
117} // end anonymous namespace
118
119char BranchRelaxation::ID = 0;
120
121char &llvm::BranchRelaxationPassID = BranchRelaxation::ID;
122
123INITIALIZE_PASS(BranchRelaxation, DEBUG_TYPE, BRANCH_RELAX_NAME, false, false)
124
125/// verify - check BBOffsets, BBSizes, alignment of islands
126void BranchRelaxation::verify() {
127#ifndef NDEBUG
128 unsigned PrevNum = MF->begin()->getNumber();
129 for (MachineBasicBlock &MBB : *MF) {
130 const unsigned Num = MBB.getNumber();
131 assert(!Num || BlockInfo[PrevNum].postOffset(MBB) <= BlockInfo[Num].Offset);
132 assert(BlockInfo[Num].Size == computeBlockSize(MBB));
133 PrevNum = Num;
134 }
135
136 for (MachineBasicBlock &MBB : *MF) {
138 J != MBB.end(); J = std::next(J)) {
139 MachineInstr &MI = *J;
140 if (!MI.isConditionalBranch() && !MI.isUnconditionalBranch())
141 continue;
142 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
143 continue;
144 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
145 assert(isBlockInRange(MI, *DestBB));
146 }
147 }
148#endif
149}
150
151#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
152/// print block size and offset information - debugging
153LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
154 for (auto &MBB : *MF) {
155 const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
156 dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
157 << format("size=%#x\n", BBI.Size);
158 }
159}
160#endif
161
162/// scanFunction - Do the initial scan of the function, building up
163/// information about each block.
164void BranchRelaxation::scanFunction() {
165 BlockInfo.clear();
166 BlockInfo.resize(MF->getNumBlockIDs());
167
168 // First thing, compute the size of all basic blocks, and see if the function
169 // has any inline assembly in it. If so, we have to be conservative about
170 // alignment assumptions, as we don't know for sure the size of any
171 // instructions in the inline assembly.
172 for (MachineBasicBlock &MBB : *MF)
173 BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
174
175 // Compute block offsets and known bits.
176 adjustBlockOffsets(*MF->begin());
177}
178
179/// computeBlockSize - Compute the size for MBB.
180uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
181 uint64_t Size = 0;
182 for (const MachineInstr &MI : MBB)
183 Size += TII->getInstSizeInBytes(MI);
184 return Size;
185}
186
187/// getInstrOffset - Return the current offset of the specified machine
188/// instruction from the start of the function. This offset changes as stuff is
189/// moved around inside the function.
190unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
191 const MachineBasicBlock *MBB = MI.getParent();
192
193 // The offset is composed of two things: the sum of the sizes of all MBB's
194 // before this instruction's block, and the offset from the start of the block
195 // it is in.
196 unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
197
198 // Sum instructions before MI in MBB.
199 for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
200 assert(I != MBB->end() && "Didn't find MI in its own basic block?");
201 Offset += TII->getInstSizeInBytes(*I);
202 }
203
204 return Offset;
205}
206
207void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
208 unsigned PrevNum = Start.getNumber();
209 for (auto &MBB :
210 make_range(std::next(MachineFunction::iterator(Start)), MF->end())) {
211 unsigned Num = MBB.getNumber();
212 // Get the offset and known bits at the end of the layout predecessor.
213 // Include the alignment of the current block.
214 BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
215
216 PrevNum = Num;
217 }
218}
219
220/// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB
222BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {
223 return createNewBlockAfter(OrigBB, OrigBB.getBasicBlock());
224}
225
226/// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock
227/// and insert it after \p OrigMBB
229BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigMBB,
230 const BasicBlock *BB) {
231 // Create a new MBB for the code after the OrigBB.
232 MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);
233 MF->insert(++OrigMBB.getIterator(), NewBB);
234
235 // Insert an entry into BlockInfo to align it properly with the block numbers.
236 BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
237
238 return NewBB;
239}
240
241/// Split the basic block containing MI into two blocks, which are joined by
242/// an unconditional branch. Update data structures and renumber blocks to
243/// account for this change and returns the newly created block.
244MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
245 MachineBasicBlock *DestBB) {
246 MachineBasicBlock *OrigBB = MI.getParent();
247
248 // Create a new MBB for the code after the OrigBB.
249 MachineBasicBlock *NewBB =
250 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
251 MF->insert(++OrigBB->getIterator(), NewBB);
252
253 // Splice the instructions starting with MI over to NewBB.
254 NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
255
256 // Add an unconditional branch from OrigBB to NewBB.
257 // Note the new unconditional branch is not being recorded.
258 // There doesn't seem to be meaningful DebugInfo available; this doesn't
259 // correspond to anything in the source.
260 TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
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 NewBB->transferSuccessors(OrigBB);
266 OrigBB->addSuccessor(NewBB);
267 OrigBB->addSuccessor(DestBB);
268
269 // Cleanup potential unconditional branch to successor block.
270 // Note that updateTerminator may change the size of the blocks.
271 OrigBB->updateTerminator(NewBB);
272
273 // Figure out how large the OrigBB is. As the first half of the original
274 // block, it cannot contain a tablejump. The size includes
275 // the new jump we added. (It should be possible to do this without
276 // recounting everything, but it's very confusing, and this is rarely
277 // executed.)
278 BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
279
280 // Figure out how large the NewMBB is. As the second half of the original
281 // block, it may contain a tablejump.
282 BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
283
284 // All BBOffsets following these blocks must be modified.
285 adjustBlockOffsets(*OrigBB);
286
287 // Need to fix live-in lists if we track liveness.
288 if (TRI->trackLivenessAfterRegAlloc(*MF))
289 computeAndAddLiveIns(LiveRegs, *NewBB);
290
291 ++NumSplit;
292
293 return NewBB;
294}
295
296/// isBlockInRange - Returns true if the distance between specific MI and
297/// specific BB can fit in MI's displacement field.
298bool BranchRelaxation::isBlockInRange(
299 const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
300 int64_t BrOffset = getInstrOffset(MI);
301 int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
302
303 if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
304 return true;
305
306 LLVM_DEBUG(dbgs() << "Out of range branch to destination "
307 << printMBBReference(DestBB) << " from "
308 << printMBBReference(*MI.getParent()) << " to "
309 << DestOffset << " offset " << DestOffset - BrOffset << '\t'
310 << MI);
311
312 return false;
313}
314
315/// fixupConditionalBranch - Fix up a conditional branch whose destination is
316/// too far away to fit in its displacement field. It is converted to an inverse
317/// conditional branch + an unconditional branch to the destination.
318bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
319 DebugLoc DL = MI.getDebugLoc();
320 MachineBasicBlock *MBB = MI.getParent();
321 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
322 MachineBasicBlock *NewBB = nullptr;
324
325 auto insertUncondBranch = [&](MachineBasicBlock *MBB,
326 MachineBasicBlock *DestBB) {
327 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
328 int NewBrSize = 0;
329 TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
330 BBSize += NewBrSize;
331 };
332 auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
335 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
336 int NewBrSize = 0;
337 TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
338 BBSize += NewBrSize;
339 };
340 auto removeBranch = [&](MachineBasicBlock *MBB) {
341 unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
342 int RemovedSize = 0;
343 TII->removeBranch(*MBB, &RemovedSize);
344 BBSize -= RemovedSize;
345 };
346
347 auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
348 MachineBasicBlock *NewBB) {
349 // Keep the block offsets up to date.
350 adjustBlockOffsets(*MBB);
351
352 // Need to fix live-in lists if we track liveness.
353 if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
354 computeAndAddLiveIns(LiveRegs, *NewBB);
355 };
356
357 bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
358 assert(!Fail && "branches to be relaxed must be analyzable");
359 (void)Fail;
360
361 // Add an unconditional branch to the destination and invert the branch
362 // condition to jump over it:
363 // tbz L1
364 // =>
365 // tbnz L2
366 // b L1
367 // L2:
368
369 bool ReversedCond = !TII->reverseBranchCondition(Cond);
370 if (ReversedCond) {
371 if (FBB && isBlockInRange(MI, *FBB)) {
372 // Last MI in the BB is an unconditional branch. We can simply invert the
373 // condition and swap destinations:
374 // beq L1
375 // b L2
376 // =>
377 // bne L2
378 // b L1
379 LLVM_DEBUG(dbgs() << " Invert condition and swap "
380 "its destination with "
381 << MBB->back());
382
383 removeBranch(MBB);
384 insertBranch(MBB, FBB, TBB, Cond);
385 finalizeBlockChanges(MBB, nullptr);
386 return true;
387 }
388 if (FBB) {
389 // We need to split the basic block here to obtain two long-range
390 // unconditional branches.
391 NewBB = createNewBlockAfter(*MBB);
392
393 insertUncondBranch(NewBB, FBB);
394 // Update the succesor lists according to the transformation to follow.
395 // Do it here since if there's no split, no update is needed.
396 MBB->replaceSuccessor(FBB, NewBB);
397 NewBB->addSuccessor(FBB);
398 }
399
400 // We now have an appropriate fall-through block in place (either naturally or
401 // just created), so we can use the inverted the condition.
402 MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
403
404 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
405 << ", invert condition and change dest. to "
406 << printMBBReference(NextBB) << '\n');
407
408 removeBranch(MBB);
409 // Insert a new conditional branch and a new unconditional branch.
410 insertBranch(MBB, &NextBB, TBB, Cond);
411
412 finalizeBlockChanges(MBB, NewBB);
413 return true;
414 }
415 // Branch cond can't be inverted.
416 // In this case we always add a block after the MBB.
417 LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
418 << " Insert a new BB after " << MBB->back());
419
420 if (!FBB)
421 FBB = &(*std::next(MachineFunction::iterator(MBB)));
422
423 // This is the block with cond. branch and the distance to TBB is too long.
424 // beq L1
425 // L2:
426
427 // We do the following transformation:
428 // beq NewBB
429 // b L2
430 // NewBB:
431 // b L1
432 // L2:
433
434 NewBB = createNewBlockAfter(*MBB);
435 insertUncondBranch(NewBB, TBB);
436
437 LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "
438 << printMBBReference(*NewBB)
439 << " Keep the exiting condition.\n"
440 << " Insert B to " << printMBBReference(*FBB) << ".\n"
441 << " In the new BB: Insert B to "
442 << printMBBReference(*TBB) << ".\n");
443
444 // Update the successor lists according to the transformation to follow.
445 MBB->replaceSuccessor(TBB, NewBB);
446 NewBB->addSuccessor(TBB);
447
448 // Replace branch in the current (MBB) block.
449 removeBranch(MBB);
450 insertBranch(MBB, NewBB, FBB, Cond);
451
452 finalizeBlockChanges(MBB, NewBB);
453 return true;
454}
455
456bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
457 MachineBasicBlock *MBB = MI.getParent();
459 unsigned OldBrSize = TII->getInstSizeInBytes(MI);
460 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
461
462 int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
463 int64_t SrcOffset = getInstrOffset(MI);
464
465 assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
466
467 BlockInfo[MBB->getNumber()].Size -= OldBrSize;
468
469 MachineBasicBlock *BranchBB = MBB;
470
471 // If this was an expanded conditional branch, there is already a single
472 // unconditional branch in a block.
473 if (!MBB->empty()) {
474 BranchBB = createNewBlockAfter(*MBB);
475
476 // Add live outs.
477 for (const MachineBasicBlock *Succ : MBB->successors()) {
478 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
479 BranchBB->addLiveIn(LiveIn);
480 }
481
482 BranchBB->sortUniqueLiveIns();
483 BranchBB->addSuccessor(DestBB);
484 MBB->replaceSuccessor(DestBB, BranchBB);
485 }
486
487 DebugLoc DL = MI.getDebugLoc();
488 MI.eraseFromParent();
489
490 // Create the optional restore block and, initially, place it at the end of
491 // function. That block will be placed later if it's used; otherwise, it will
492 // be erased.
493 MachineBasicBlock *RestoreBB = createNewBlockAfter(MF->back(),
494 DestBB->getBasicBlock());
495
496 TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB, DL,
497 DestOffset - SrcOffset, RS.get());
498
499 BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);
500 adjustBlockOffsets(*MBB);
501
502 // If RestoreBB is required, try to place just before DestBB.
503 if (!RestoreBB->empty()) {
504 // TODO: For multiple far branches to the same destination, there are
505 // chances that some restore blocks could be shared if they clobber the
506 // same registers and share the same restore sequence. So far, those
507 // restore blocks are just duplicated for each far branch.
508 assert(!DestBB->isEntryBlock());
509 MachineBasicBlock *PrevBB = &*std::prev(DestBB->getIterator());
510 // Fall through only if PrevBB has no unconditional branch as one of its
511 // terminators.
512 if (auto *FT = PrevBB->getLogicalFallThrough()) {
513 assert(FT == DestBB);
514 TII->insertUnconditionalBranch(*PrevBB, FT, DebugLoc());
515 BlockInfo[PrevBB->getNumber()].Size = computeBlockSize(*PrevBB);
516 }
517 // Now, RestoreBB could be placed directly before DestBB.
518 MF->splice(DestBB->getIterator(), RestoreBB->getIterator());
519 // Update successors and predecessors.
520 RestoreBB->addSuccessor(DestBB);
521 BranchBB->replaceSuccessor(DestBB, RestoreBB);
522 if (TRI->trackLivenessAfterRegAlloc(*MF))
523 computeAndAddLiveIns(LiveRegs, *RestoreBB);
524 // Compute the restore block size.
525 BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB);
526 // Update the offset starting from the previous block.
527 adjustBlockOffsets(*PrevBB);
528 } else {
529 // Remove restore block if it's not required.
530 MF->erase(RestoreBB);
531 }
532
533 return true;
534}
535
536bool BranchRelaxation::relaxBranchInstructions() {
537 bool Changed = false;
538
539 // Relaxing branches involves creating new basic blocks, so re-eval
540 // end() for termination.
541 for (MachineBasicBlock &MBB : *MF) {
542 // Empty block?
544 if (Last == MBB.end())
545 continue;
546
547 // Expand the unconditional branch first if necessary. If there is a
548 // conditional branch, this will end up changing the branch destination of
549 // it to be over the newly inserted indirect branch block, which may avoid
550 // the need to try expanding the conditional branch first, saving an extra
551 // jump.
552 if (Last->isUnconditionalBranch()) {
553 // Unconditional branch destination might be unanalyzable, assume these
554 // are OK.
555 if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
556 if (!isBlockInRange(*Last, *DestBB)) {
557 fixupUnconditionalBranch(*Last);
558 ++NumUnconditionalRelaxed;
559 Changed = true;
560 }
561 }
562 }
563
564 // Loop over the conditional branches.
567 J != MBB.end(); J = Next) {
568 Next = std::next(J);
569 MachineInstr &MI = *J;
570
571 if (!MI.isConditionalBranch())
572 continue;
573
574 if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
575 // FAULTING_OP's destination is not encoded in the instruction stream
576 // and thus never needs relaxed.
577 continue;
578
579 MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
580 if (!isBlockInRange(MI, *DestBB)) {
581 if (Next != MBB.end() && Next->isConditionalBranch()) {
582 // If there are multiple conditional branches, this isn't an
583 // analyzable block. Split later terminators into a new block so
584 // each one will be analyzable.
585
586 splitBlockBeforeInstr(*Next, DestBB);
587 } else {
588 fixupConditionalBranch(MI);
589 ++NumConditionalRelaxed;
590 }
591
592 Changed = true;
593
594 // This may have modified all of the terminators, so start over.
595 Next = MBB.getFirstTerminator();
596 }
597 }
598 }
599
600 return Changed;
601}
602
603bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
604 MF = &mf;
605
606 LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
607
608 const TargetSubtargetInfo &ST = MF->getSubtarget();
609 TII = ST.getInstrInfo();
610
611 TRI = ST.getRegisterInfo();
612 if (TRI->trackLivenessAfterRegAlloc(*MF))
613 RS.reset(new RegScavenger());
614
615 // Renumber all of the machine basic blocks in the function, guaranteeing that
616 // the numbers agree with the position of the block in the function.
617 MF->RenumberBlocks();
618
619 // Do the initial scan of the function, building up information about the
620 // sizes of each block.
621 scanFunction();
622
623 LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
624
625 bool MadeChange = false;
626 while (relaxBranchInstructions())
627 MadeChange = true;
628
629 // After a while, this might be made debug-only, but it is not expensive.
630 verify();
631
632 LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
633
634 BlockInfo.clear();
635
636 return MadeChange;
637}
#define Fail
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallVector< MachineOperand, 4 > Cond
#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:492
#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
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
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:56
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.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
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.
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.
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.
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 '...
Align getAlignment() const
Return alignment of the basic block.
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:68
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
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:82
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:406
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:124
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.
Pair of physical register and lane mask.