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  BlockInfo[BranchBB->getNumber()].Size += TII->insertIndirectBranch(
467  *BranchBB, *DestBB, DL, DestOffset - SrcOffset, RS.get());
468 
469  adjustBlockOffsets(*MBB);
470  return true;
471 }
472 
473 bool BranchRelaxation::relaxBranchInstructions() {
474  bool Changed = false;
475 
476  // Relaxing branches involves creating new basic blocks, so re-eval
477  // end() for termination.
478  for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
479  MachineBasicBlock &MBB = *I;
480 
481  // Empty block?
483  if (Last == MBB.end())
484  continue;
485 
486  // Expand the unconditional branch first if necessary. If there is a
487  // conditional branch, this will end up changing the branch destination of
488  // it to be over the newly inserted indirect branch block, which may avoid
489  // the need to try expanding the conditional branch first, saving an extra
490  // jump.
491  if (Last->isUnconditionalBranch()) {
492  // Unconditional branch destination might be unanalyzable, assume these
493  // are OK.
494  if (MachineBasicBlock *DestBB = TII->getBranchDestBlock(*Last)) {
495  if (!isBlockInRange(*Last, *DestBB)) {
496  fixupUnconditionalBranch(*Last);
497  ++NumUnconditionalRelaxed;
498  Changed = true;
499  }
500  }
501  }
502 
503  // Loop over the conditional branches.
506  J != MBB.end(); J = Next) {
507  Next = std::next(J);
508  MachineInstr &MI = *J;
509 
510  if (!MI.isConditionalBranch())
511  continue;
512 
513  if (MI.getOpcode() == TargetOpcode::FAULTING_OP)
514  // FAULTING_OP's destination is not encoded in the instruction stream
515  // and thus never needs relaxed.
516  continue;
517 
518  MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI);
519  if (!isBlockInRange(MI, *DestBB)) {
520  if (Next != MBB.end() && Next->isConditionalBranch()) {
521  // If there are multiple conditional branches, this isn't an
522  // analyzable block. Split later terminators into a new block so
523  // each one will be analyzable.
524 
525  splitBlockBeforeInstr(*Next, DestBB);
526  } else {
527  fixupConditionalBranch(MI);
528  ++NumConditionalRelaxed;
529  }
530 
531  Changed = true;
532 
533  // This may have modified all of the terminators, so start over.
534  Next = MBB.getFirstTerminator();
535  }
536  }
537  }
538 
539  return Changed;
540 }
541 
542 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
543  MF = &mf;
544 
545  LLVM_DEBUG(dbgs() << "***** BranchRelaxation *****\n");
546 
547  const TargetSubtargetInfo &ST = MF->getSubtarget();
548  TII = ST.getInstrInfo();
549 
550  TRI = ST.getRegisterInfo();
552  RS.reset(new RegScavenger());
553 
554  // Renumber all of the machine basic blocks in the function, guaranteeing that
555  // the numbers agree with the position of the block in the function.
556  MF->RenumberBlocks();
557 
558  // Do the initial scan of the function, building up information about the
559  // sizes of each block.
560  scanFunction();
561 
562  LLVM_DEBUG(dbgs() << " Basic blocks before relaxation\n"; dumpBBs(););
563 
564  bool MadeChange = false;
565  while (relaxBranchInstructions())
566  MadeChange = true;
567 
568  // After a while, this might be made debug-only, but it is not expensive.
569  verify();
570 
571  LLVM_DEBUG(dbgs() << " Basic blocks after relaxation\n\n"; dumpBBs());
572 
573  BlockInfo.clear();
574 
575  return MadeChange;
576 }
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:103
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:491
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
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:202
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:561
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:391
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:1168
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
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:261
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:81
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:248
Format.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
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:746
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:129
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:584
llvm::computeAndAddLiveIns
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
Definition: LivePhysRegs.cpp:339
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:59
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:267
llvm::MachineBasicBlock::getAlignment
Align getAlignment() const
Return alignment of the basic block.
Definition: MachineBasicBlock.h:519
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:225
llvm::MachineFunction
Definition: MachineFunction.h:230
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:242
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1056
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
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:950
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:865
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:367
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:807
llvm::MachineBasicBlock::sortUniqueLiveIns
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
Definition: MachineBasicBlock.cpp:581
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
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:1547
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:240
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:641
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:674
InitializePasses.h
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
LivePhysRegs.h