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