LLVM  16.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 
9 #include "llvm/ADT/SmallVector.h"
10 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Config/llvm-config.h"
21 #include "llvm/IR/DebugLoc.h"
22 #include "llvm/InitializePasses.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/Format.h"
29 #include <cassert>
30 #include <cstdint>
31 #include <iterator>
32 #include <memory>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "branch-relaxation"
37 
38 STATISTIC(NumSplit, "Number of basic blocks split");
39 STATISTIC(NumConditionalRelaxed, "Number of conditional branches relaxed");
40 STATISTIC(NumUnconditionalRelaxed, "Number of unconditional branches relaxed");
41 
42 #define BRANCH_RELAX_NAME "Branch relaxation pass"
43 
44 namespace {
45 
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 
84  MachineFunction *MF;
85  const TargetRegisterInfo *TRI;
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 
107 public:
108  static char ID;
109 
111 
112  bool runOnMachineFunction(MachineFunction &MF) override;
113 
114  StringRef getPassName() const override { return BRANCH_RELAX_NAME; }
115 };
116 
117 } // end anonymous namespace
118 
119 char BranchRelaxation::ID = 0;
120 
122 
124 
125 /// verify - check BBOffsets, BBSizes, alignment of islands
126 void 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 #endif
136 }
137 
138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
139 /// print block size and offset information - debugging
140 LLVM_DUMP_METHOD void BranchRelaxation::dumpBBs() {
141  for (auto &MBB : *MF) {
142  const BasicBlockInfo &BBI = BlockInfo[MBB.getNumber()];
143  dbgs() << format("%%bb.%u\toffset=%08x\t", MBB.getNumber(), BBI.Offset)
144  << format("size=%#x\n", BBI.Size);
145  }
146 }
147 #endif
148 
149 /// scanFunction - Do the initial scan of the function, building up
150 /// information about each block.
151 void BranchRelaxation::scanFunction() {
152  BlockInfo.clear();
153  BlockInfo.resize(MF->getNumBlockIDs());
154 
155  // First thing, compute the size of all basic blocks, and see if the function
156  // has any inline assembly in it. If so, we have to be conservative about
157  // alignment assumptions, as we don't know for sure the size of any
158  // instructions in the inline assembly.
159  for (MachineBasicBlock &MBB : *MF)
160  BlockInfo[MBB.getNumber()].Size = computeBlockSize(MBB);
161 
162  // Compute block offsets and known bits.
163  adjustBlockOffsets(*MF->begin());
164 }
165 
166 /// computeBlockSize - Compute the size for MBB.
167 uint64_t BranchRelaxation::computeBlockSize(const MachineBasicBlock &MBB) const {
168  uint64_t Size = 0;
169  for (const MachineInstr &MI : MBB)
170  Size += TII->getInstSizeInBytes(MI);
171  return Size;
172 }
173 
174 /// getInstrOffset - Return the current offset of the specified machine
175 /// instruction from the start of the function. This offset changes as stuff is
176 /// moved around inside the function.
177 unsigned BranchRelaxation::getInstrOffset(const MachineInstr &MI) const {
178  const MachineBasicBlock *MBB = MI.getParent();
179 
180  // The offset is composed of two things: the sum of the sizes of all MBB's
181  // before this instruction's block, and the offset from the start of the block
182  // it is in.
183  unsigned Offset = BlockInfo[MBB->getNumber()].Offset;
184 
185  // Sum instructions before MI in MBB.
186  for (MachineBasicBlock::const_iterator I = MBB->begin(); &*I != &MI; ++I) {
187  assert(I != MBB->end() && "Didn't find MI in its own basic block?");
188  Offset += TII->getInstSizeInBytes(*I);
189  }
190 
191  return Offset;
192 }
193 
194 void BranchRelaxation::adjustBlockOffsets(MachineBasicBlock &Start) {
195  unsigned PrevNum = Start.getNumber();
196  for (auto &MBB :
197  make_range(std::next(MachineFunction::iterator(Start)), MF->end())) {
198  unsigned Num = MBB.getNumber();
199  // Get the offset and known bits at the end of the layout predecessor.
200  // Include the alignment of the current block.
201  BlockInfo[Num].Offset = BlockInfo[PrevNum].postOffset(MBB);
202 
203  PrevNum = Num;
204  }
205 }
206 
207 /// Insert a new empty MachineBasicBlock and insert it after \p OrigMBB
209 BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigBB) {
210  return createNewBlockAfter(OrigBB, OrigBB.getBasicBlock());
211 }
212 
213 /// Insert a new empty MachineBasicBlock with \p BB as its BasicBlock
214 /// and insert it after \p OrigMBB
216 BranchRelaxation::createNewBlockAfter(MachineBasicBlock &OrigMBB,
217  const BasicBlock *BB) {
218  // Create a new MBB for the code after the OrigBB.
219  MachineBasicBlock *NewBB = MF->CreateMachineBasicBlock(BB);
220  MF->insert(++OrigMBB.getIterator(), NewBB);
221 
222  // Insert an entry into BlockInfo to align it properly with the block numbers.
223  BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
224 
225  return NewBB;
226 }
227 
228 /// Split the basic block containing MI into two blocks, which are joined by
229 /// an unconditional branch. Update data structures and renumber blocks to
230 /// account for this change and returns the newly created block.
231 MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
232  MachineBasicBlock *DestBB) {
233  MachineBasicBlock *OrigBB = MI.getParent();
234 
235  // Create a new MBB for the code after the OrigBB.
236  MachineBasicBlock *NewBB =
237  MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
238  MF->insert(++OrigBB->getIterator(), NewBB);
239 
240  // Splice the instructions starting with MI over to NewBB.
241  NewBB->splice(NewBB->end(), OrigBB, MI.getIterator(), OrigBB->end());
242 
243  // Add an unconditional branch from OrigBB to NewBB.
244  // Note the new unconditional branch is not being recorded.
245  // There doesn't seem to be meaningful DebugInfo available; this doesn't
246  // correspond to anything in the source.
247  TII->insertUnconditionalBranch(*OrigBB, NewBB, DebugLoc());
248 
249  // Insert an entry into BlockInfo to align it properly with the block numbers.
250  BlockInfo.insert(BlockInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
251 
252  NewBB->transferSuccessors(OrigBB);
253  OrigBB->addSuccessor(NewBB);
254  OrigBB->addSuccessor(DestBB);
255 
256  // Cleanup potential unconditional branch to successor block.
257  // Note that updateTerminator may change the size of the blocks.
258  OrigBB->updateTerminator(NewBB);
259 
260  // Figure out how large the OrigBB is. As the first half of the original
261  // block, it cannot contain a tablejump. The size includes
262  // the new jump we added. (It should be possible to do this without
263  // recounting everything, but it's very confusing, and this is rarely
264  // executed.)
265  BlockInfo[OrigBB->getNumber()].Size = computeBlockSize(*OrigBB);
266 
267  // Figure out how large the NewMBB is. As the second half of the original
268  // block, it may contain a tablejump.
269  BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
270 
271  // All BBOffsets following these blocks must be modified.
272  adjustBlockOffsets(*OrigBB);
273 
274  // Need to fix live-in lists if we track liveness.
276  computeAndAddLiveIns(LiveRegs, *NewBB);
277 
278  ++NumSplit;
279 
280  return NewBB;
281 }
282 
283 /// isBlockInRange - Returns true if the distance between specific MI and
284 /// specific BB can fit in MI's displacement field.
285 bool BranchRelaxation::isBlockInRange(
286  const MachineInstr &MI, const MachineBasicBlock &DestBB) const {
287  int64_t BrOffset = getInstrOffset(MI);
288  int64_t DestOffset = BlockInfo[DestBB.getNumber()].Offset;
289 
290  if (TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - BrOffset))
291  return true;
292 
293  LLVM_DEBUG(dbgs() << "Out of range branch to destination "
294  << printMBBReference(DestBB) << " from "
295  << printMBBReference(*MI.getParent()) << " to "
296  << DestOffset << " offset " << DestOffset - BrOffset << '\t'
297  << MI);
298 
299  return false;
300 }
301 
302 /// fixupConditionalBranch - Fix up a conditional branch whose destination is
303 /// too far away to fit in its displacement field. It is converted to an inverse
304 /// conditional branch + an unconditional branch to the destination.
305 bool BranchRelaxation::fixupConditionalBranch(MachineInstr &MI) {
306  DebugLoc DL = MI.getDebugLoc();
307  MachineBasicBlock *MBB = MI.getParent();
308  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
309  MachineBasicBlock *NewBB = nullptr;
311 
312  auto insertUncondBranch = [&](MachineBasicBlock *MBB,
313  MachineBasicBlock *DestBB) {
314  unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
315  int NewBrSize = 0;
316  TII->insertUnconditionalBranch(*MBB, DestBB, DL, &NewBrSize);
317  BBSize += NewBrSize;
318  };
319  auto insertBranch = [&](MachineBasicBlock *MBB, MachineBasicBlock *TBB,
320  MachineBasicBlock *FBB,
322  unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
323  int NewBrSize = 0;
324  TII->insertBranch(*MBB, TBB, FBB, Cond, DL, &NewBrSize);
325  BBSize += NewBrSize;
326  };
327  auto removeBranch = [&](MachineBasicBlock *MBB) {
328  unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
329  int RemovedSize = 0;
330  TII->removeBranch(*MBB, &RemovedSize);
331  BBSize -= RemovedSize;
332  };
333 
334  auto finalizeBlockChanges = [&](MachineBasicBlock *MBB,
335  MachineBasicBlock *NewBB) {
336  // Keep the block offsets up to date.
337  adjustBlockOffsets(*MBB);
338 
339  // Need to fix live-in lists if we track liveness.
340  if (NewBB && TRI->trackLivenessAfterRegAlloc(*MF))
341  computeAndAddLiveIns(LiveRegs, *NewBB);
342  };
343 
344  bool Fail = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
345  assert(!Fail && "branches to be relaxed must be analyzable");
346  (void)Fail;
347 
348  // Add an unconditional branch to the destination and invert the branch
349  // condition to jump over it:
350  // tbz L1
351  // =>
352  // tbnz L2
353  // b L1
354  // L2:
355 
356  bool ReversedCond = !TII->reverseBranchCondition(Cond);
357  if (ReversedCond) {
358  if (FBB && isBlockInRange(MI, *FBB)) {
359  // Last MI in the BB is an unconditional branch. We can simply invert the
360  // condition and swap destinations:
361  // beq L1
362  // b L2
363  // =>
364  // bne L2
365  // b L1
366  LLVM_DEBUG(dbgs() << " Invert condition and swap "
367  "its destination with "
368  << MBB->back());
369 
370  removeBranch(MBB);
371  insertBranch(MBB, FBB, TBB, Cond);
372  finalizeBlockChanges(MBB, nullptr);
373  return true;
374  }
375  if (FBB) {
376  // We need to split the basic block here to obtain two long-range
377  // unconditional branches.
378  NewBB = createNewBlockAfter(*MBB);
379 
380  insertUncondBranch(NewBB, FBB);
381  // Update the succesor lists according to the transformation to follow.
382  // Do it here since if there's no split, no update is needed.
383  MBB->replaceSuccessor(FBB, NewBB);
384  NewBB->addSuccessor(FBB);
385  }
386 
387  // We now have an appropriate fall-through block in place (either naturally or
388  // just created), so we can use the inverted the condition.
389  MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
390 
391  LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*TBB)
392  << ", invert condition and change dest. to "
393  << printMBBReference(NextBB) << '\n');
394 
395  removeBranch(MBB);
396  // Insert a new conditional branch and a new unconditional branch.
397  insertBranch(MBB, &NextBB, TBB, Cond);
398 
399  finalizeBlockChanges(MBB, NewBB);
400  return true;
401  }
402  // Branch cond can't be inverted.
403  // In this case we always add a block after the MBB.
404  LLVM_DEBUG(dbgs() << " The branch condition can't be inverted. "
405  << " Insert a new BB after " << MBB->back());
406 
407  if (!FBB)
408  FBB = &(*std::next(MachineFunction::iterator(MBB)));
409 
410  // This is the block with cond. branch and the distance to TBB is too long.
411  // beq L1
412  // L2:
413 
414  // We do the following transformation:
415  // beq NewBB
416  // b L2
417  // NewBB:
418  // b L1
419  // L2:
420 
421  NewBB = createNewBlockAfter(*MBB);
422  insertUncondBranch(NewBB, TBB);
423 
424  LLVM_DEBUG(dbgs() << " Insert cond B to the new BB "
425  << printMBBReference(*NewBB)
426  << " Keep the exiting condition.\n"
427  << " Insert B to " << printMBBReference(*FBB) << ".\n"
428  << " In the new BB: Insert B to "
429  << printMBBReference(*TBB) << ".\n");
430 
431  // Update the successor lists according to the transformation to follow.
432  MBB->replaceSuccessor(TBB, NewBB);
433  NewBB->addSuccessor(TBB);
434 
435  // Replace branch in the current (MBB) block.
436  removeBranch(MBB);
437  insertBranch(MBB, NewBB, FBB, Cond);
438 
439  finalizeBlockChanges(MBB, NewBB);
440  return true;
441 }
442 
443 bool BranchRelaxation::fixupUnconditionalBranch(MachineInstr &MI) {
444  MachineBasicBlock *MBB = MI.getParent();
445  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
447  unsigned OldBrSize = TII->getInstSizeInBytes(MI);
448  MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
449 
450  int64_t DestOffset = BlockInfo[DestBB->getNumber()].Offset;
451  int64_t SrcOffset = getInstrOffset(MI);
452 
453  assert(!TII->isBranchOffsetInRange(MI.getOpcode(), DestOffset - SrcOffset));
454 
455  BlockInfo[MBB->getNumber()].Size -= OldBrSize;
456 
457  MachineBasicBlock *BranchBB = MBB;
458 
459  auto RemoveBranch = [&](MachineBasicBlock *MBB) {
460  unsigned &BBSize = BlockInfo[MBB->getNumber()].Size;
461  int RemovedSize = 0;
462  TII->removeBranch(*MBB, &RemovedSize);
463  BBSize -= RemovedSize;
464  };
465 
467  MachineBasicBlock *Dst) {
468  TII->insertUnconditionalBranch(*MBB, Dst, DebugLoc());
469  // Recalculate the block size.
470  BlockInfo[MBB->getNumber()].Size = computeBlockSize(*MBB);
471  };
472 
473  // If this was an expanded conditional branch, there is already a single
474  // unconditional branch in a block.
475  if (!MBB->empty()) {
476  BranchBB = createNewBlockAfter(*MBB);
477 
478  // Add live outs.
479  for (const MachineBasicBlock *Succ : MBB->successors()) {
480  for (const MachineBasicBlock::RegisterMaskPair &LiveIn : Succ->liveins())
481  BranchBB->addLiveIn(LiveIn);
482  }
483 
484  BranchBB->sortUniqueLiveIns();
485  BranchBB->addSuccessor(DestBB);
486  MBB->replaceSuccessor(DestBB, BranchBB);
487  }
488 
489  DebugLoc DL = MI.getDebugLoc();
490  MI.eraseFromParent();
491 
492  // Create the optional restore block and, initially, place it at the end of
493  // function. That block will be placed later if it's used; otherwise, it will
494  // be erased.
495  MachineBasicBlock *RestoreBB = createNewBlockAfter(MF->back(),
496  DestBB->getBasicBlock());
497 
498  TII->insertIndirectBranch(*BranchBB, *DestBB, *RestoreBB, DL,
499  DestOffset - SrcOffset, RS.get());
500 
501  BlockInfo[BranchBB->getNumber()].Size = computeBlockSize(*BranchBB);
502  adjustBlockOffsets(*MBB);
503 
504  // If RestoreBB is required, try to place just before DestBB.
505  if (!RestoreBB->empty()) {
506  // TODO: For multiple far branches to the same destination, there are
507  // chances that some restore blocks could be shared if they clobber the
508  // same registers and share the same restore sequence. So far, those
509  // restore blocks are just duplicated for each far branch.
510  assert(!DestBB->isEntryBlock());
511  MachineBasicBlock *PrevBB = &*std::prev(DestBB->getIterator());
512  // Fall through only if PrevBB has no unconditional branch as one of its
513  // terminators.
514  if (TII->analyzeBranch(*PrevBB, TBB, FBB, Cond))
515  report_fatal_error("Could not analyze terminators.");
516  if (!FBB) {
517  if (!Cond.empty() && TBB && TBB == DestBB)
518  RemoveBranch(PrevBB);
519  if (!TBB || (TBB && !Cond.empty()))
520  InsertUncondBranch(PrevBB, DestBB);
521  }
522  // Now, RestoreBB could be placed directly before DestBB.
523  MF->splice(DestBB->getIterator(), RestoreBB->getIterator());
524  // Update successors and predecessors.
525  RestoreBB->addSuccessor(DestBB);
526  BranchBB->replaceSuccessor(DestBB, RestoreBB);
528  computeAndAddLiveIns(LiveRegs, *RestoreBB);
529  // Compute the restore block size.
530  BlockInfo[RestoreBB->getNumber()].Size = computeBlockSize(*RestoreBB);
531  // Update the offset starting from the previous block.
532  adjustBlockOffsets(*PrevBB);
533  } else {
534  // Remove restore block if it's not required.
535  MF->erase(RestoreBB);
536  }
537 
538  return true;
539 }
540 
541 bool BranchRelaxation::relaxBranchInstructions() {
542  bool Changed = false;
543 
544  // Relaxing branches involves creating new basic blocks, so re-eval
545  // end() for termination.
546  for (MachineBasicBlock &MBB : *MF) {
547  // Empty block?
549  if (Last == MBB.end())
550  continue;
551 
552  // Expand the unconditional branch first if necessary. If there is a
553  // conditional branch, this will end up changing the branch destination of
554  // it to be over the newly inserted indirect branch block, which may avoid
555  // the need to try expanding the conditional branch first, saving an extra
556  // jump.
557  if (Last->isUnconditionalBranch()) {
558  // Unconditional branch destination might be unanalyzable, assume these
559  // are OK.
560  if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
561  if (!isBlockInRange(*Last, *DestBB)) {
562  fixupUnconditionalBranch(*Last);
563  ++NumUnconditionalRelaxed;
564  Changed = true;
565  }
566  }
567  }
568 
569  // Loop over the conditional branches.
572  J != MBB.end(); J = Next) {
573  Next = std::next(J);
574  MachineInstr &MI = *J;
575 
576  if (!MI.isConditionalBranch())
577  continue;
578 
579  if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
580  // FAULTING_OP's destination is not encoded in the instruction stream
581  // and thus never needs relaxed.
582  continue;
583 
584  MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
585  if (!isBlockInRange(MI, *DestBB)) {
586  if (Next != MBB.end() && Next->isConditionalBranch()) {
587  // If there are multiple conditional branches, this isn't an
588  // analyzable block. Split later terminators into a new block so
589  // each one will be analyzable.
590 
591  splitBlockBeforeInstr(*Next, DestBB);
592  } else {
593  fixupConditionalBranch(MI);
594  ++NumConditionalRelaxed;
595  }
596 
597  Changed = true;
598 
599  // This may have modified all of the terminators, so start over.
600  Next = MBB.getFirstTerminator();
601  }
602  }
603  }
604 
605  return Changed;
606 }
607 
608 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
609  MF = &mf;
610 
611  LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
612 
613  const TargetSubtargetInfo &ST = MF->getSubtarget();
614  TII = ST.getInstrInfo();
615 
616  TRI = ST.getRegisterInfo();
618  RS.reset(new RegScavenger());
619 
620  // Renumber all of the machine basic blocks in the function, guaranteeing that
621  // the numbers agree with the position of the block in the function.
622  MF->RenumberBlocks();
623 
624  // Do the initial scan of the function, building up information about the
625  // sizes of each block.
626  scanFunction();
627 
628  LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
629 
630  bool MadeChange = false;
631  while (relaxBranchInstructions())
632  MadeChange = true;
633 
634  // After a while, this might be made debug-only, but it is not expensive.
635  verify();
636 
637  LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
638 
639  BlockInfo.clear();
640 
641  return MadeChange;
642 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
llvm::TargetRegisterInfo::trackLivenessAfterRegAlloc
virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const
Returns true if the live-ins should be tracked after register allocation.
Definition: TargetRegisterInfo.h:956
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:156
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::MachineBasicBlock::getBasicBlock
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Definition: MachineBasicBlock.h:209
llvm::HexagonInstrInfo::removeBranch
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
Definition: HexagonInstrInfo.cpp:603
llvm::PseudoProbeReservedId::Last
@ Last
Pass.h
llvm::HexagonInstrInfo::analyzeBranch
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....
Definition: HexagonInstrInfo.cpp:433
llvm::BasicBlockInfo::Offset
unsigned Offset
Offset - Distance from the beginning of the function to the beginning of this basic block.
Definition: ARMBasicBlockInfo.h:51
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:117
ErrorHandling.h
llvm::MachineBasicBlock::isEntryBlock
bool isEntryBlock() const
Returns true if this is the entry block of the function.
Definition: MachineBasicBlock.cpp:287
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
Fail
#define Fail
Definition: AArch64Disassembler.cpp:296
MachineBasicBlock.h
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
TargetInstrInfo.h
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:285
Format.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineBasicBlock::addSuccessor
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:762
BranchRelaxation
static cl::opt< bool > BranchRelaxation("aarch64-enable-branch-relax", cl::Hidden, cl::init(true), cl::desc("Relax out of range conditional branches"))
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
DEBUG_TYPE
#define DEBUG_TYPE
Definition: BranchRelaxation.cpp:36
llvm::BasicBlockInfo
BasicBlockInfo - Information about the offset and size of a single basic block.
Definition: ARMBasicBlockInfo.h:41
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
TBB
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
Definition: RISCVRedundantCopyElimination.cpp:76
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineBasicBlock::RegisterMaskPair
Pair of physical register and lane mask.
Definition: MachineBasicBlock.h:100
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::HexagonInstrInfo::insertBranch
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.
Definition: HexagonInstrInfo.cpp:626
llvm::computeAndAddLiveIns
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
Definition: LivePhysRegs.cpp:341
DebugLoc.h
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
BRANCH_RELAX_NAME
#define BRANCH_RELAX_NAME
Definition: BranchRelaxation.cpp:42
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
uint64_t
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::RegScavenger
Definition: RegisterScavenging.h:34
llvm::MachineBasicBlock::getLastNonDebugInstr
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
Definition: MachineBasicBlock.cpp:264
llvm::MachineBasicBlock::getAlignment
Align getAlignment() const
Return alignment of the basic block.
Definition: MachineBasicBlock.h:556
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:261
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::BasicBlockInfo::Size
unsigned Size
Size - Size of the basic block in bytes.
Definition: ARMBasicBlockInfo.h:58
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:239
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::MachineBasicBlock::splice
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 '...
Definition: MachineBasicBlock.h:1009
Compiler.h
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::format
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
llvm::MachineBasicBlock::transferSuccessors
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
Definition: MachineBasicBlock.cpp:881
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
llvm::MachineBasicBlock::addLiveIn
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
Definition: MachineBasicBlock.h:404
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineBasicBlock::replaceSuccessor
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
Definition: MachineBasicBlock.cpp:823
llvm::MachineBasicBlock::sortUniqueLiveIns
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
Definition: MachineBasicBlock.cpp:597
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1327
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
verify
ppc ctr loops verify
Definition: PPCCTRLoopsVerify.cpp:76
llvm::BranchRelaxationPassID
char & BranchRelaxationPassID
BranchRelaxation - This pass replaces branches that need to jump further than is supported by a branc...
Definition: BranchRelaxation.cpp:121
llvm::HexagonInstrInfo::reverseBranchCondition
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
Definition: HexagonInstrInfo.cpp:1626
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
InsertUncondBranch
static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB, const TargetInstrInfo *TII)
Inserts an unconditional branch from MBB to ToMBB.
Definition: IfConversion.cpp:1470
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:277
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
RegisterScavenging.h
llvm::MachineBasicBlock::updateTerminator
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
Definition: MachineBasicBlock.cpp:657
raw_ostream.h
MachineFunction.h
llvm::MachineInstrBundleIterator< const MachineInstr >
llvm::MachineFunction::getAlignment
Align getAlignment() const
getAlignment - Return the alignment of the function.
Definition: MachineFunction.h:705
InitializePasses.h
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
LivePhysRegs.h