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