LLVM  15.0.0git
BranchFolding.cpp
Go to the documentation of this file.
1 //===- BranchFolding.cpp - Fold machine code branch instructions ----------===//
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 // This pass forwards branches to unconditional branches to make them branch
10 // directly to the target block. This pass often results in dead MBB's, which
11 // it then removes.
12 //
13 // Note that this pass must be run after register allocation, it cannot handle
14 // SSA form. It also must handle virtual registers for targets that emit virtual
15 // ISA (e.g. NVPTX).
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "BranchFolding.h"
20 #include "llvm/ADT/BitVector.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
26 #include "llvm/CodeGen/Analysis.h"
45 #include "llvm/IR/DebugLoc.h"
46 #include "llvm/IR/Function.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/MC/LaneBitmask.h"
49 #include "llvm/MC/MCRegisterInfo.h"
50 #include "llvm/Pass.h"
54 #include "llvm/Support/Debug.h"
58 #include <cassert>
59 #include <cstddef>
60 #include <iterator>
61 #include <numeric>
62 
63 using namespace llvm;
64 
65 #define DEBUG_TYPE "branch-folder"
66 
67 STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
68 STATISTIC(NumBranchOpts, "Number of branches optimized");
69 STATISTIC(NumTailMerge , "Number of block tails merged");
70 STATISTIC(NumHoist , "Number of times common instructions are hoisted");
71 STATISTIC(NumTailCalls, "Number of tail calls optimized");
72 
73 static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
75 
76 // Throttle for huge numbers of predecessors (compile speed problems)
77 static cl::opt<unsigned>
78 TailMergeThreshold("tail-merge-threshold",
79  cl::desc("Max number of predecessors to consider tail merging"),
80  cl::init(150), cl::Hidden);
81 
82 // Heuristic for tail merging (and, inversely, tail duplication).
83 // TODO: This should be replaced with a target query.
84 static cl::opt<unsigned>
85 TailMergeSize("tail-merge-size",
86  cl::desc("Min number of instructions to consider tail merging"),
87  cl::init(3), cl::Hidden);
88 
89 namespace {
90 
91  /// BranchFolderPass - Wrap branch folder in a machine function pass.
92  class BranchFolderPass : public MachineFunctionPass {
93  public:
94  static char ID;
95 
96  explicit BranchFolderPass(): MachineFunctionPass(ID) {}
97 
98  bool runOnMachineFunction(MachineFunction &MF) override;
99 
100  void getAnalysisUsage(AnalysisUsage &AU) const override {
106  }
107 
108  MachineFunctionProperties getRequiredProperties() const override {
111  }
112  };
113 
114 } // end anonymous namespace
115 
116 char BranchFolderPass::ID = 0;
117 
119 
120 INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE,
121  "Control Flow Optimizer", false, false)
122 
123 bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
124  if (skipFunction(MF.getFunction()))
125  return false;
126 
127  TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
128  // TailMerge can create jump into if branches that make CFG irreducible for
129  // HW that requires structurized CFG.
130  bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
131  PassConfig->getEnableTailMerge();
132  MBFIWrapper MBBFreqInfo(
133  getAnalysis<MachineBlockFrequencyInfo>());
134  BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true, MBBFreqInfo,
135  getAnalysis<MachineBranchProbabilityInfo>(),
136  &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
137  return Folder.OptimizeFunction(MF, MF.getSubtarget().getInstrInfo(),
138  MF.getSubtarget().getRegisterInfo());
139 }
140 
141 BranchFolder::BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,
142  MBFIWrapper &FreqInfo,
143  const MachineBranchProbabilityInfo &ProbInfo,
144  ProfileSummaryInfo *PSI, unsigned MinTailLength)
145  : EnableHoistCommonCode(CommonHoist), MinCommonTailLength(MinTailLength),
146  MBBFreqInfo(FreqInfo), MBPI(ProbInfo), PSI(PSI) {
147  if (MinCommonTailLength == 0)
148  MinCommonTailLength = TailMergeSize;
149  switch (FlagEnableTailMerge) {
150  case cl::BOU_UNSET:
151  EnableTailMerge = DefaultEnableTailMerge;
152  break;
153  case cl::BOU_TRUE: EnableTailMerge = true; break;
154  case cl::BOU_FALSE: EnableTailMerge = false; break;
155  }
156 }
157 
158 void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
159  assert(MBB->pred_empty() && "MBB must be dead!");
160  LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
161 
162  MachineFunction *MF = MBB->getParent();
163  // drop all successors.
164  while (!MBB->succ_empty())
166 
167  // Avoid matching if this pointer gets reused.
168  TriedMerging.erase(MBB);
169 
170  // Update call site info.
171  for (const MachineInstr &MI : *MBB)
172  if (MI.shouldUpdateCallSiteInfo())
173  MF->eraseCallSiteInfo(&MI);
174 
175  // Remove the block.
176  MF->erase(MBB);
177  EHScopeMembership.erase(MBB);
178  if (MLI)
179  MLI->removeBlock(MBB);
180 }
181 
183  const TargetInstrInfo *tii,
184  const TargetRegisterInfo *tri,
185  MachineLoopInfo *mli, bool AfterPlacement) {
186  if (!tii) return false;
187 
188  TriedMerging.clear();
189 
190  MachineRegisterInfo &MRI = MF.getRegInfo();
191  AfterBlockPlacement = AfterPlacement;
192  TII = tii;
193  TRI = tri;
194  MLI = mli;
195  this->MRI = &MRI;
196 
197  UpdateLiveIns = MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF);
198  if (!UpdateLiveIns)
200 
201  bool MadeChange = false;
202 
203  // Recalculate EH scope membership.
204  EHScopeMembership = getEHScopeMembership(MF);
205 
206  bool MadeChangeThisIteration = true;
207  while (MadeChangeThisIteration) {
208  MadeChangeThisIteration = TailMergeBlocks(MF);
209  // No need to clean up if tail merging does not change anything after the
210  // block placement.
211  if (!AfterBlockPlacement || MadeChangeThisIteration)
212  MadeChangeThisIteration |= OptimizeBranches(MF);
213  if (EnableHoistCommonCode)
214  MadeChangeThisIteration |= HoistCommonCode(MF);
215  MadeChange |= MadeChangeThisIteration;
216  }
217 
218  // See if any jump tables have become dead as the code generator
219  // did its thing.
221  if (!JTI)
222  return MadeChange;
223 
224  // Walk the function to find jump tables that are live.
225  BitVector JTIsLive(JTI->getJumpTables().size());
226  for (const MachineBasicBlock &BB : MF) {
227  for (const MachineInstr &I : BB)
228  for (const MachineOperand &Op : I.operands()) {
229  if (!Op.isJTI()) continue;
230 
231  // Remember that this JT is live.
232  JTIsLive.set(Op.getIndex());
233  }
234  }
235 
236  // Finally, remove dead jump tables. This happens when the
237  // indirect jump was unreachable (and thus deleted).
238  for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
239  if (!JTIsLive.test(i)) {
240  JTI->RemoveJumpTable(i);
241  MadeChange = true;
242  }
243 
244  return MadeChange;
245 }
246 
247 //===----------------------------------------------------------------------===//
248 // Tail Merging of Blocks
249 //===----------------------------------------------------------------------===//
250 
251 /// HashMachineInstr - Compute a hash value for MI and its operands.
252 static unsigned HashMachineInstr(const MachineInstr &MI) {
253  unsigned Hash = MI.getOpcode();
254  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
255  const MachineOperand &Op = MI.getOperand(i);
256 
257  // Merge in bits from the operand if easy. We can't use MachineOperand's
258  // hash_code here because it's not deterministic and we sort by hash value
259  // later.
260  unsigned OperandHash = 0;
261  switch (Op.getType()) {
263  OperandHash = Op.getReg();
264  break;
266  OperandHash = Op.getImm();
267  break;
269  OperandHash = Op.getMBB()->getNumber();
270  break;
274  OperandHash = Op.getIndex();
275  break;
278  // Global address / external symbol are too hard, don't bother, but do
279  // pull in the offset.
280  OperandHash = Op.getOffset();
281  break;
282  default:
283  break;
284  }
285 
286  Hash += ((OperandHash << 3) | Op.getType()) << (i & 31);
287  }
288  return Hash;
289 }
290 
291 /// HashEndOfMBB - Hash the last instruction in the MBB.
292 static unsigned HashEndOfMBB(const MachineBasicBlock &MBB) {
294  if (I == MBB.end())
295  return 0;
296 
297  return HashMachineInstr(*I);
298 }
299 
300 /// Whether MI should be counted as an instruction when calculating common tail.
301 static bool countsAsInstruction(const MachineInstr &MI) {
302  return !(MI.isDebugInstr() || MI.isCFIInstruction());
303 }
304 
305 /// Iterate backwards from the given iterator \p I, towards the beginning of the
306 /// block. If a MI satisfying 'countsAsInstruction' is found, return an iterator
307 /// pointing to that MI. If no such MI is found, return the end iterator.
311  while (I != MBB->begin()) {
312  --I;
313  if (countsAsInstruction(*I))
314  return I;
315  }
316  return MBB->end();
317 }
318 
319 /// Given two machine basic blocks, return the number of instructions they
320 /// actually have in common together at their end. If a common tail is found (at
321 /// least by one instruction), then iterators for the first shared instruction
322 /// in each block are returned as well.
323 ///
324 /// Non-instructions according to countsAsInstruction are ignored.
326  MachineBasicBlock *MBB2,
329  MachineBasicBlock::iterator MBBI1 = MBB1->end();
330  MachineBasicBlock::iterator MBBI2 = MBB2->end();
331 
332  unsigned TailLen = 0;
333  while (true) {
334  MBBI1 = skipBackwardPastNonInstructions(MBBI1, MBB1);
335  MBBI2 = skipBackwardPastNonInstructions(MBBI2, MBB2);
336  if (MBBI1 == MBB1->end() || MBBI2 == MBB2->end())
337  break;
338  if (!MBBI1->isIdenticalTo(*MBBI2) ||
339  // FIXME: This check is dubious. It's used to get around a problem where
340  // people incorrectly expect inline asm directives to remain in the same
341  // relative order. This is untenable because normal compiler
342  // optimizations (like this one) may reorder and/or merge these
343  // directives.
344  MBBI1->isInlineAsm()) {
345  break;
346  }
347  if (MBBI1->getFlag(MachineInstr::NoMerge) ||
348  MBBI2->getFlag(MachineInstr::NoMerge))
349  break;
350  ++TailLen;
351  I1 = MBBI1;
352  I2 = MBBI2;
353  }
354 
355  return TailLen;
356 }
357 
358 void BranchFolder::replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
359  MachineBasicBlock &NewDest) {
360  if (UpdateLiveIns) {
361  // OldInst should always point to an instruction.
362  MachineBasicBlock &OldMBB = *OldInst->getParent();
363  LiveRegs.clear();
364  LiveRegs.addLiveOuts(OldMBB);
365  // Move backward to the place where will insert the jump.
366  MachineBasicBlock::iterator I = OldMBB.end();
367  do {
368  --I;
369  LiveRegs.stepBackward(*I);
370  } while (I != OldInst);
371 
372  // Merging the tails may have switched some undef operand to non-undef ones.
373  // Add IMPLICIT_DEFS into OldMBB as necessary to have a definition of the
374  // register.
375  for (MachineBasicBlock::RegisterMaskPair P : NewDest.liveins()) {
376  // We computed the liveins with computeLiveIn earlier and should only see
377  // full registers:
378  assert(P.LaneMask == LaneBitmask::getAll() &&
379  "Can only handle full register.");
380  MCPhysReg Reg = P.PhysReg;
381  if (!LiveRegs.available(*MRI, Reg))
382  continue;
383  DebugLoc DL;
384  BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);
385  }
386  }
387 
388  TII->ReplaceTailWithBranchTo(OldInst, &NewDest);
389  ++NumTailMerge;
390 }
391 
392 MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
394  const BasicBlock *BB) {
395  if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
396  return nullptr;
397 
398  MachineFunction &MF = *CurMBB.getParent();
399 
400  // Create the fall-through block.
403  CurMBB.getParent()->insert(++MBBI, NewMBB);
404 
405  // Move all the successors of this block to the specified block.
406  NewMBB->transferSuccessors(&CurMBB);
407 
408  // Add an edge from CurMBB to NewMBB for the fall-through.
409  CurMBB.addSuccessor(NewMBB);
410 
411  // Splice the code over.
412  NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
413 
414  // NewMBB belongs to the same loop as CurMBB.
415  if (MLI)
416  if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))
417  ML->addBasicBlockToLoop(NewMBB, MLI->getBase());
418 
419  // NewMBB inherits CurMBB's block frequency.
420  MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
421 
422  if (UpdateLiveIns)
423  computeAndAddLiveIns(LiveRegs, *NewMBB);
424 
425  // Add the new block to the EH scope.
426  const auto &EHScopeI = EHScopeMembership.find(&CurMBB);
427  if (EHScopeI != EHScopeMembership.end()) {
428  auto n = EHScopeI->second;
429  EHScopeMembership[NewMBB] = n;
430  }
431 
432  return NewMBB;
433 }
434 
435 /// EstimateRuntime - Make a rough estimate for how long it will take to run
436 /// the specified code.
439  unsigned Time = 0;
440  for (; I != E; ++I) {
441  if (!countsAsInstruction(*I))
442  continue;
443  if (I->isCall())
444  Time += 10;
445  else if (I->mayLoadOrStore())
446  Time += 2;
447  else
448  ++Time;
449  }
450  return Time;
451 }
452 
453 // CurMBB needs to add an unconditional branch to SuccMBB (we removed these
454 // branches temporarily for tail merging). In the case where CurMBB ends
455 // with a conditional branch to the next block, optimize by reversing the
456 // test and conditionally branching to SuccMBB instead.
457 static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
458  const TargetInstrInfo *TII) {
459  MachineFunction *MF = CurMBB->getParent();
461  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
463  DebugLoc dl = CurMBB->findBranchDebugLoc();
464  if (I != MF->end() && !TII->analyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
465  MachineBasicBlock *NextBB = &*I;
466  if (TBB == NextBB && !Cond.empty() && !FBB) {
468  TII->removeBranch(*CurMBB);
469  TII->insertBranch(*CurMBB, SuccBB, nullptr, Cond, dl);
470  return;
471  }
472  }
473  }
474  TII->insertBranch(*CurMBB, SuccBB, nullptr,
476 }
477 
478 bool
479 BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {
480  if (getHash() < o.getHash())
481  return true;
482  if (getHash() > o.getHash())
483  return false;
484  if (getBlock()->getNumber() < o.getBlock()->getNumber())
485  return true;
486  if (getBlock()->getNumber() > o.getBlock()->getNumber())
487  return false;
488  // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
489  // an object with itself.
490 #ifndef _GLIBCXX_DEBUG
491  llvm_unreachable("Predecessor appears twice");
492 #else
493  return false;
494 #endif
495 }
496 
497 /// CountTerminators - Count the number of terminators in the given
498 /// block and set I to the position of the first non-terminator, if there
499 /// is one, or MBB->end() otherwise.
502  I = MBB->end();
503  unsigned NumTerms = 0;
504  while (true) {
505  if (I == MBB->begin()) {
506  I = MBB->end();
507  break;
508  }
509  --I;
510  if (!I->isTerminator()) break;
511  ++NumTerms;
512  }
513  return NumTerms;
514 }
515 
516 /// A no successor, non-return block probably ends in unreachable and is cold.
517 /// Also consider a block that ends in an indirect branch to be a return block,
518 /// since many targets use plain indirect branches to return.
520  if (!MBB->succ_empty())
521  return false;
522  if (MBB->empty())
523  return true;
524  return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());
525 }
526 
527 /// ProfitableToMerge - Check if two machine basic blocks have a common tail
528 /// and decide if it would be profitable to merge those tails. Return the
529 /// length of the common tail and iterators to the first common instruction
530 /// in each block.
531 /// MBB1, MBB2 The blocks to check
532 /// MinCommonTailLength Minimum size of tail block to be merged.
533 /// CommonTailLen Out parameter to record the size of the shared tail between
534 /// MBB1 and MBB2
535 /// I1, I2 Iterator references that will be changed to point to the first
536 /// instruction in the common tail shared by MBB1,MBB2
537 /// SuccBB A common successor of MBB1, MBB2 which are in a canonical form
538 /// relative to SuccBB
539 /// PredBB The layout predecessor of SuccBB, if any.
540 /// EHScopeMembership map from block to EH scope #.
541 /// AfterPlacement True if we are merging blocks after layout. Stricter
542 /// thresholds apply to prevent undoing tail-duplication.
543 static bool
545  unsigned MinCommonTailLength, unsigned &CommonTailLen,
548  MachineBasicBlock *PredBB,
549  DenseMap<const MachineBasicBlock *, int> &EHScopeMembership,
550  bool AfterPlacement,
551  MBFIWrapper &MBBFreqInfo,
552  ProfileSummaryInfo *PSI) {
553  // It is never profitable to tail-merge blocks from two different EH scopes.
554  if (!EHScopeMembership.empty()) {
555  auto EHScope1 = EHScopeMembership.find(MBB1);
556  assert(EHScope1 != EHScopeMembership.end());
557  auto EHScope2 = EHScopeMembership.find(MBB2);
558  assert(EHScope2 != EHScopeMembership.end());
559  if (EHScope1->second != EHScope2->second)
560  return false;
561  }
562 
563  CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
564  if (CommonTailLen == 0)
565  return false;
566  LLVM_DEBUG(dbgs() << "Common tail length of " << printMBBReference(*MBB1)
567  << " and " << printMBBReference(*MBB2) << " is "
568  << CommonTailLen << '\n');
569 
570  // Move the iterators to the beginning of the MBB if we only got debug
571  // instructions before the tail. This is to avoid splitting a block when we
572  // only got debug instructions before the tail (to be invariant on -g).
573  if (skipDebugInstructionsForward(MBB1->begin(), MBB1->end(), false) == I1)
574  I1 = MBB1->begin();
575  if (skipDebugInstructionsForward(MBB2->begin(), MBB2->end(), false) == I2)
576  I2 = MBB2->begin();
577 
578  bool FullBlockTail1 = I1 == MBB1->begin();
579  bool FullBlockTail2 = I2 == MBB2->begin();
580 
581  // It's almost always profitable to merge any number of non-terminator
582  // instructions with the block that falls through into the common successor.
583  // This is true only for a single successor. For multiple successors, we are
584  // trading a conditional branch for an unconditional one.
585  // TODO: Re-visit successor size for non-layout tail merging.
586  if ((MBB1 == PredBB || MBB2 == PredBB) &&
587  (!AfterPlacement || MBB1->succ_size() == 1)) {
589  unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
590  if (CommonTailLen > NumTerms)
591  return true;
592  }
593 
594  // If these are identical non-return blocks with no successors, merge them.
595  // Such blocks are typically cold calls to noreturn functions like abort, and
596  // are unlikely to become a fallthrough target after machine block placement.
597  // Tail merging these blocks is unlikely to create additional unconditional
598  // branches, and will reduce the size of this cold code.
599  if (FullBlockTail1 && FullBlockTail2 &&
601  return true;
602 
603  // If one of the blocks can be completely merged and happens to be in
604  // a position where the other could fall through into it, merge any number
605  // of instructions, because it can be done without a branch.
606  // TODO: If the blocks are not adjacent, move one of them so that they are?
607  if (MBB1->isLayoutSuccessor(MBB2) && FullBlockTail2)
608  return true;
609  if (MBB2->isLayoutSuccessor(MBB1) && FullBlockTail1)
610  return true;
611 
612  // If both blocks are identical and end in a branch, merge them unless they
613  // both have a fallthrough predecessor and successor.
614  // We can only do this after block placement because it depends on whether
615  // there are fallthroughs, and we don't know until after layout.
616  if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {
617  auto BothFallThrough = [](MachineBasicBlock *MBB) {
618  if (!MBB->succ_empty() && !MBB->canFallThrough())
619  return false;
621  MachineFunction *MF = MBB->getParent();
622  return (MBB != &*MF->begin()) && std::prev(I)->canFallThrough();
623  };
624  if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))
625  return true;
626  }
627 
628  // If both blocks have an unconditional branch temporarily stripped out,
629  // count that as an additional common instruction for the following
630  // heuristics. This heuristic is only accurate for single-succ blocks, so to
631  // make sure that during layout merging and duplicating don't crash, we check
632  // for that when merging during layout.
633  unsigned EffectiveTailLen = CommonTailLen;
634  if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
635  (MBB1->succ_size() == 1 || !AfterPlacement) &&
636  !MBB1->back().isBarrier() &&
637  !MBB2->back().isBarrier())
638  ++EffectiveTailLen;
639 
640  // Check if the common tail is long enough to be worthwhile.
641  if (EffectiveTailLen >= MinCommonTailLength)
642  return true;
643 
644  // If we are optimizing for code size, 2 instructions in common is enough if
645  // we don't have to split a block. At worst we will be introducing 1 new
646  // branch instruction, which is likely to be smaller than the 2
647  // instructions that would be deleted in the merge.
648  MachineFunction *MF = MBB1->getParent();
649  bool OptForSize =
650  MF->getFunction().hasOptSize() ||
651  (llvm::shouldOptimizeForSize(MBB1, PSI, &MBBFreqInfo) &&
652  llvm::shouldOptimizeForSize(MBB2, PSI, &MBBFreqInfo));
653  return EffectiveTailLen >= 2 && OptForSize &&
654  (FullBlockTail1 || FullBlockTail2);
655 }
656 
657 unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
658  unsigned MinCommonTailLength,
659  MachineBasicBlock *SuccBB,
660  MachineBasicBlock *PredBB) {
661  unsigned maxCommonTailLength = 0U;
662  SameTails.clear();
663  MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
664  MPIterator HighestMPIter = std::prev(MergePotentials.end());
665  for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
666  B = MergePotentials.begin();
667  CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
668  for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
669  unsigned CommonTailLen;
670  if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
671  MinCommonTailLength,
672  CommonTailLen, TrialBBI1, TrialBBI2,
673  SuccBB, PredBB,
674  EHScopeMembership,
675  AfterBlockPlacement, MBBFreqInfo, PSI)) {
676  if (CommonTailLen > maxCommonTailLength) {
677  SameTails.clear();
678  maxCommonTailLength = CommonTailLen;
679  HighestMPIter = CurMPIter;
680  SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
681  }
682  if (HighestMPIter == CurMPIter &&
683  CommonTailLen == maxCommonTailLength)
684  SameTails.push_back(SameTailElt(I, TrialBBI2));
685  }
686  if (I == B)
687  break;
688  }
689  }
690  return maxCommonTailLength;
691 }
692 
693 void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
694  MachineBasicBlock *SuccBB,
695  MachineBasicBlock *PredBB) {
696  MPIterator CurMPIter, B;
697  for (CurMPIter = std::prev(MergePotentials.end()),
698  B = MergePotentials.begin();
699  CurMPIter->getHash() == CurHash; --CurMPIter) {
700  // Put the unconditional branch back, if we need one.
701  MachineBasicBlock *CurMBB = CurMPIter->getBlock();
702  if (SuccBB && CurMBB != PredBB)
703  FixTail(CurMBB, SuccBB, TII);
704  if (CurMPIter == B)
705  break;
706  }
707  if (CurMPIter->getHash() != CurHash)
708  CurMPIter++;
709  MergePotentials.erase(CurMPIter, MergePotentials.end());
710 }
711 
712 bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
713  MachineBasicBlock *SuccBB,
714  unsigned maxCommonTailLength,
715  unsigned &commonTailIndex) {
716  commonTailIndex = 0;
717  unsigned TimeEstimate = ~0U;
718  for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
719  // Use PredBB if possible; that doesn't require a new branch.
720  if (SameTails[i].getBlock() == PredBB) {
721  commonTailIndex = i;
722  break;
723  }
724  // Otherwise, make a (fairly bogus) choice based on estimate of
725  // how long it will take the various blocks to execute.
726  unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),
727  SameTails[i].getTailStartPos());
728  if (t <= TimeEstimate) {
729  TimeEstimate = t;
730  commonTailIndex = i;
731  }
732  }
733 
735  SameTails[commonTailIndex].getTailStartPos();
736  MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
737 
738  LLVM_DEBUG(dbgs() << "\nSplitting " << printMBBReference(*MBB) << ", size "
739  << maxCommonTailLength);
740 
741  // If the split block unconditionally falls-thru to SuccBB, it will be
742  // merged. In control flow terms it should then take SuccBB's name. e.g. If
743  // SuccBB is an inner loop, the common tail is still part of the inner loop.
744  const BasicBlock *BB = (SuccBB && MBB->succ_size() == 1) ?
745  SuccBB->getBasicBlock() : MBB->getBasicBlock();
746  MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI, BB);
747  if (!newMBB) {
748  LLVM_DEBUG(dbgs() << "... failed!");
749  return false;
750  }
751 
752  SameTails[commonTailIndex].setBlock(newMBB);
753  SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
754 
755  // If we split PredBB, newMBB is the new predecessor.
756  if (PredBB == MBB)
757  PredBB = newMBB;
758 
759  return true;
760 }
761 
762 static void
764  MachineBasicBlock &MBBCommon) {
765  MachineBasicBlock *MBB = MBBIStartPos->getParent();
766  // Note CommonTailLen does not necessarily matches the size of
767  // the common BB nor all its instructions because of debug
768  // instructions differences.
769  unsigned CommonTailLen = 0;
770  for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)
771  ++CommonTailLen;
772 
775  MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin();
776  MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend();
777 
778  while (CommonTailLen--) {
779  assert(MBBI != MBBIE && "Reached BB end within common tail length!");
780  (void)MBBIE;
781 
782  if (!countsAsInstruction(*MBBI)) {
783  ++MBBI;
784  continue;
785  }
786 
787  while ((MBBICommon != MBBIECommon) && !countsAsInstruction(*MBBICommon))
788  ++MBBICommon;
789 
790  assert(MBBICommon != MBBIECommon &&
791  "Reached BB end within common tail length!");
792  assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!");
793 
794  // Merge MMOs from memory operations in the common block.
795  if (MBBICommon->mayLoadOrStore())
796  MBBICommon->cloneMergedMemRefs(*MBB->getParent(), {&*MBBICommon, &*MBBI});
797  // Drop undef flags if they aren't present in all merged instructions.
798  for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {
799  MachineOperand &MO = MBBICommon->getOperand(I);
800  if (MO.isReg() && MO.isUndef()) {
801  const MachineOperand &OtherMO = MBBI->getOperand(I);
802  if (!OtherMO.isUndef())
803  MO.setIsUndef(false);
804  }
805  }
806 
807  ++MBBI;
808  ++MBBICommon;
809  }
810 }
811 
812 void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {
813  MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
814 
815  std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
816  for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
817  if (i != commonTailIndex) {
818  NextCommonInsts[i] = SameTails[i].getTailStartPos();
819  mergeOperations(SameTails[i].getTailStartPos(), *MBB);
820  } else {
821  assert(SameTails[i].getTailStartPos() == MBB->begin() &&
822  "MBB is not a common tail only block");
823  }
824  }
825 
826  for (auto &MI : *MBB) {
827  if (!countsAsInstruction(MI))
828  continue;
829  DebugLoc DL = MI.getDebugLoc();
830  for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
831  if (i == commonTailIndex)
832  continue;
833 
834  auto &Pos = NextCommonInsts[i];
835  assert(Pos != SameTails[i].getBlock()->end() &&
836  "Reached BB end within common tail");
837  while (!countsAsInstruction(*Pos)) {
838  ++Pos;
839  assert(Pos != SameTails[i].getBlock()->end() &&
840  "Reached BB end within common tail");
841  }
842  assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
843  DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
844  NextCommonInsts[i] = ++Pos;
845  }
846  MI.setDebugLoc(DL);
847  }
848 
849  if (UpdateLiveIns) {
850  LivePhysRegs NewLiveIns(*TRI);
851  computeLiveIns(NewLiveIns, *MBB);
852  LiveRegs.init(*TRI);
853 
854  // The flag merging may lead to some register uses no longer using the
855  // <undef> flag, add IMPLICIT_DEFs in the predecessors as necessary.
856  for (MachineBasicBlock *Pred : MBB->predecessors()) {
857  LiveRegs.clear();
858  LiveRegs.addLiveOuts(*Pred);
859  MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();
860  for (Register Reg : NewLiveIns) {
861  if (!LiveRegs.available(*MRI, Reg))
862  continue;
863  DebugLoc DL;
864  BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
865  Reg);
866  }
867  }
868 
869  MBB->clearLiveIns();
870  addLiveIns(*MBB, NewLiveIns);
871  }
872 }
873 
874 // See if any of the blocks in MergePotentials (which all have SuccBB as a
875 // successor, or all have no successor if it is null) can be tail-merged.
876 // If there is a successor, any blocks in MergePotentials that are not
877 // tail-merged and are not immediately before Succ must have an unconditional
878 // branch to Succ added (but the predecessor/successor lists need no
879 // adjustment). The lone predecessor of Succ that falls through into Succ,
880 // if any, is given in PredBB.
881 // MinCommonTailLength - Except for the special cases below, tail-merge if
882 // there are at least this many instructions in common.
883 bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
884  MachineBasicBlock *PredBB,
885  unsigned MinCommonTailLength) {
886  bool MadeChange = false;
887 
888  LLVM_DEBUG(
889  dbgs() << "\nTryTailMergeBlocks: ";
890  for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()
891  << printMBBReference(*MergePotentials[i].getBlock())
892  << (i == e - 1 ? "" : ", ");
893  dbgs() << "\n"; if (SuccBB) {
894  dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';
895  if (PredBB)
896  dbgs() << " which has fall-through from "
897  << printMBBReference(*PredBB) << "\n";
898  } dbgs() << "Looking for common tails of at least "
899  << MinCommonTailLength << " instruction"
900  << (MinCommonTailLength == 1 ? "" : "s") << '\n';);
901 
902  // Sort by hash value so that blocks with identical end sequences sort
903  // together.
904  array_pod_sort(MergePotentials.begin(), MergePotentials.end());
905 
906  // Walk through equivalence sets looking for actual exact matches.
907  while (MergePotentials.size() > 1) {
908  unsigned CurHash = MergePotentials.back().getHash();
909 
910  // Build SameTails, identifying the set of blocks with this hash code
911  // and with the maximum number of instructions in common.
912  unsigned maxCommonTailLength = ComputeSameTails(CurHash,
913  MinCommonTailLength,
914  SuccBB, PredBB);
915 
916  // If we didn't find any pair that has at least MinCommonTailLength
917  // instructions in common, remove all blocks with this hash code and retry.
918  if (SameTails.empty()) {
919  RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
920  continue;
921  }
922 
923  // If one of the blocks is the entire common tail (and is not the entry
924  // block/an EH pad, which we can't jump to), we can treat all blocks with
925  // this same tail at once. Use PredBB if that is one of the possibilities,
926  // as that will not introduce any extra branches.
927  MachineBasicBlock *EntryBB =
928  &MergePotentials.front().getBlock()->getParent()->front();
929  unsigned commonTailIndex = SameTails.size();
930  // If there are two blocks, check to see if one can be made to fall through
931  // into the other.
932  if (SameTails.size() == 2 &&
933  SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
934  SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
935  commonTailIndex = 1;
936  else if (SameTails.size() == 2 &&
937  SameTails[1].getBlock()->isLayoutSuccessor(
938  SameTails[0].getBlock()) &&
939  SameTails[0].tailIsWholeBlock() &&
940  !SameTails[0].getBlock()->isEHPad())
941  commonTailIndex = 0;
942  else {
943  // Otherwise just pick one, favoring the fall-through predecessor if
944  // there is one.
945  for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
946  MachineBasicBlock *MBB = SameTails[i].getBlock();
947  if ((MBB == EntryBB || MBB->isEHPad()) &&
948  SameTails[i].tailIsWholeBlock())
949  continue;
950  if (MBB == PredBB) {
951  commonTailIndex = i;
952  break;
953  }
954  if (SameTails[i].tailIsWholeBlock())
955  commonTailIndex = i;
956  }
957  }
958 
959  if (commonTailIndex == SameTails.size() ||
960  (SameTails[commonTailIndex].getBlock() == PredBB &&
961  !SameTails[commonTailIndex].tailIsWholeBlock())) {
962  // None of the blocks consist entirely of the common tail.
963  // Split a block so that one does.
964  if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
965  maxCommonTailLength, commonTailIndex)) {
966  RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
967  continue;
968  }
969  }
970 
971  MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
972 
973  // Recompute common tail MBB's edge weights and block frequency.
974  setCommonTailEdgeWeights(*MBB);
975 
976  // Merge debug locations, MMOs and undef flags across identical instructions
977  // for common tail.
978  mergeCommonTails(commonTailIndex);
979 
980  // MBB is common tail. Adjust all other BB's to jump to this one.
981  // Traversal must be forwards so erases work.
982  LLVM_DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)
983  << " for ");
984  for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
985  if (commonTailIndex == i)
986  continue;
987  LLVM_DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())
988  << (i == e - 1 ? "" : ", "));
989  // Hack the end off BB i, making it jump to BB commonTailIndex instead.
990  replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
991  // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
992  MergePotentials.erase(SameTails[i].getMPIter());
993  }
994  LLVM_DEBUG(dbgs() << "\n");
995  // We leave commonTailIndex in the worklist in case there are other blocks
996  // that match it with a smaller number of instructions.
997  MadeChange = true;
998  }
999  return MadeChange;
1000 }
1001 
1002 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
1003  bool MadeChange = false;
1004  if (!EnableTailMerge)
1005  return MadeChange;
1006 
1007  // First find blocks with no successors.
1008  // Block placement may create new tail merging opportunities for these blocks.
1009  MergePotentials.clear();
1010  for (MachineBasicBlock &MBB : MF) {
1011  if (MergePotentials.size() == TailMergeThreshold)
1012  break;
1013  if (!TriedMerging.count(&MBB) && MBB.succ_empty())
1014  MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
1015  }
1016 
1017  // If this is a large problem, avoid visiting the same basic blocks
1018  // multiple times.
1019  if (MergePotentials.size() == TailMergeThreshold)
1020  for (const MergePotentialsElt &Elt : MergePotentials)
1021  TriedMerging.insert(Elt.getBlock());
1022 
1023  // See if we can do any tail merging on those.
1024  if (MergePotentials.size() >= 2)
1025  MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);
1026 
1027  // Look at blocks (IBB) with multiple predecessors (PBB).
1028  // We change each predecessor to a canonical form, by
1029  // (1) temporarily removing any unconditional branch from the predecessor
1030  // to IBB, and
1031  // (2) alter conditional branches so they branch to the other block
1032  // not IBB; this may require adding back an unconditional branch to IBB
1033  // later, where there wasn't one coming in. E.g.
1034  // Bcc IBB
1035  // fallthrough to QBB
1036  // here becomes
1037  // Bncc QBB
1038  // with a conceptual B to IBB after that, which never actually exists.
1039  // With those changes, we see whether the predecessors' tails match,
1040  // and merge them if so. We change things out of canonical form and
1041  // back to the way they were later in the process. (OptimizeBranches
1042  // would undo some of this, but we can't use it, because we'd get into
1043  // a compile-time infinite loop repeatedly doing and undoing the same
1044  // transformations.)
1045 
1046  for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
1047  I != E; ++I) {
1048  if (I->pred_size() < 2) continue;
1050  MachineBasicBlock *IBB = &*I;
1051  MachineBasicBlock *PredBB = &*std::prev(I);
1052  MergePotentials.clear();
1053  MachineLoop *ML;
1054 
1055  // Bail if merging after placement and IBB is the loop header because
1056  // -- If merging predecessors that belong to the same loop as IBB, the
1057  // common tail of merged predecessors may become the loop top if block
1058  // placement is called again and the predecessors may branch to this common
1059  // tail and require more branches. This can be relaxed if
1060  // MachineBlockPlacement::findBestLoopTop is more flexible.
1061  // --If merging predecessors that do not belong to the same loop as IBB, the
1062  // loop info of IBB's loop and the other loops may be affected. Calling the
1063  // block placement again may make big change to the layout and eliminate the
1064  // reason to do tail merging here.
1065  if (AfterBlockPlacement && MLI) {
1066  ML = MLI->getLoopFor(IBB);
1067  if (ML && IBB == ML->getHeader())
1068  continue;
1069  }
1070 
1071  for (MachineBasicBlock *PBB : I->predecessors()) {
1072  if (MergePotentials.size() == TailMergeThreshold)
1073  break;
1074 
1075  if (TriedMerging.count(PBB))
1076  continue;
1077 
1078  // Skip blocks that loop to themselves, can't tail merge these.
1079  if (PBB == IBB)
1080  continue;
1081 
1082  // Visit each predecessor only once.
1083  if (!UniquePreds.insert(PBB).second)
1084  continue;
1085 
1086  // Skip blocks which may jump to a landing pad or jump from an asm blob.
1087  // Can't tail merge these.
1088  if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
1089  continue;
1090 
1091  // After block placement, only consider predecessors that belong to the
1092  // same loop as IBB. The reason is the same as above when skipping loop
1093  // header.
1094  if (AfterBlockPlacement && MLI)
1095  if (ML != MLI->getLoopFor(PBB))
1096  continue;
1097 
1098  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1100  if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {
1101  // Failing case: IBB is the target of a cbr, and we cannot reverse the
1102  // branch.
1104  if (!Cond.empty() && TBB == IBB) {
1105  if (TII->reverseBranchCondition(NewCond))
1106  continue;
1107  // This is the QBB case described above
1108  if (!FBB) {
1109  auto Next = ++PBB->getIterator();
1110  if (Next != MF.end())
1111  FBB = &*Next;
1112  }
1113  }
1114 
1115  // Remove the unconditional branch at the end, if any.
1116  if (TBB && (Cond.empty() || FBB)) {
1117  DebugLoc dl = PBB->findBranchDebugLoc();
1118  TII->removeBranch(*PBB);
1119  if (!Cond.empty())
1120  // reinsert conditional branch only, for now
1121  TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,
1122  NewCond, dl);
1123  }
1124 
1125  MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(*PBB), PBB));
1126  }
1127  }
1128 
1129  // If this is a large problem, avoid visiting the same basic blocks multiple
1130  // times.
1131  if (MergePotentials.size() == TailMergeThreshold)
1132  for (MergePotentialsElt &Elt : MergePotentials)
1133  TriedMerging.insert(Elt.getBlock());
1134 
1135  if (MergePotentials.size() >= 2)
1136  MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
1137 
1138  // Reinsert an unconditional branch if needed. The 1 below can occur as a
1139  // result of removing blocks in TryTailMergeBlocks.
1140  PredBB = &*std::prev(I); // this may have been changed in TryTailMergeBlocks
1141  if (MergePotentials.size() == 1 &&
1142  MergePotentials.begin()->getBlock() != PredBB)
1143  FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
1144  }
1145 
1146  return MadeChange;
1147 }
1148 
1149 void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {
1150  SmallVector<BlockFrequency, 2> EdgeFreqLs(TailMBB.succ_size());
1151  BlockFrequency AccumulatedMBBFreq;
1152 
1153  // Aggregate edge frequency of successor edge j:
1154  // edgeFreq(j) = sum (freq(bb) * edgeProb(bb, j)),
1155  // where bb is a basic block that is in SameTails.
1156  for (const auto &Src : SameTails) {
1157  const MachineBasicBlock *SrcMBB = Src.getBlock();
1158  BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB);
1159  AccumulatedMBBFreq += BlockFreq;
1160 
1161  // It is not necessary to recompute edge weights if TailBB has less than two
1162  // successors.
1163  if (TailMBB.succ_size() <= 1)
1164  continue;
1165 
1166  auto EdgeFreq = EdgeFreqLs.begin();
1167 
1168  for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1169  SuccI != SuccE; ++SuccI, ++EdgeFreq)
1170  *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);
1171  }
1172 
1173  MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);
1174 
1175  if (TailMBB.succ_size() <= 1)
1176  return;
1177 
1178  auto SumEdgeFreq =
1179  std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
1180  .getFrequency();
1181  auto EdgeFreq = EdgeFreqLs.begin();
1182 
1183  if (SumEdgeFreq > 0) {
1184  for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1185  SuccI != SuccE; ++SuccI, ++EdgeFreq) {
1187  EdgeFreq->getFrequency(), SumEdgeFreq);
1188  TailMBB.setSuccProbability(SuccI, Prob);
1189  }
1190  }
1191 }
1192 
1193 //===----------------------------------------------------------------------===//
1194 // Branch Optimization
1195 //===----------------------------------------------------------------------===//
1196 
1197 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
1198  bool MadeChange = false;
1199 
1200  // Make sure blocks are numbered in order
1201  MF.RenumberBlocks();
1202  // Renumbering blocks alters EH scope membership, recalculate it.
1203  EHScopeMembership = getEHScopeMembership(MF);
1204 
1205  for (MachineBasicBlock &MBB :
1207  MadeChange |= OptimizeBlock(&MBB);
1208 
1209  // If it is dead, remove it.
1210  if (MBB.pred_empty()) {
1211  RemoveDeadBlock(&MBB);
1212  MadeChange = true;
1213  ++NumDeadBlocks;
1214  }
1215  }
1216 
1217  return MadeChange;
1218 }
1219 
1220 // Blocks should be considered empty if they contain only debug info;
1221 // else the debug info would affect codegen.
1223  return MBB->getFirstNonDebugInstr(true) == MBB->end();
1224 }
1225 
1226 // Blocks with only debug info and branches should be considered the same
1227 // as blocks with only branches.
1230  assert(I != MBB->end() && "empty block!");
1231  return I->isBranch();
1232 }
1233 
1234 /// IsBetterFallthrough - Return true if it would be clearly better to
1235 /// fall-through to MBB1 than to fall through into MBB2. This has to return
1236 /// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
1237 /// result in infinite loops.
1239  MachineBasicBlock *MBB2) {
1240  assert(MBB1 && MBB2 && "Unknown MachineBasicBlock");
1241 
1242  // Right now, we use a simple heuristic. If MBB2 ends with a call, and
1243  // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
1244  // optimize branches that branch to either a return block or an assert block
1245  // into a fallthrough to the return.
1248  if (MBB1I == MBB1->end() || MBB2I == MBB2->end())
1249  return false;
1250 
1251  // If there is a clear successor ordering we make sure that one block
1252  // will fall through to the next
1253  if (MBB1->isSuccessor(MBB2)) return true;
1254  if (MBB2->isSuccessor(MBB1)) return false;
1255 
1256  return MBB2I->isCall() && !MBB1I->isCall();
1257 }
1258 
1259 /// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
1260 /// instructions on the block.
1263  if (I != MBB.end() && I->isBranch())
1264  return I->getDebugLoc();
1265  return DebugLoc();
1266 }
1267 
1270  MachineBasicBlock &PredMBB) {
1271  auto InsertBefore = PredMBB.getFirstTerminator();
1272  for (MachineInstr &MI : MBB.instrs())
1273  if (MI.isDebugInstr()) {
1274  TII->duplicate(PredMBB, InsertBefore, MI);
1275  LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "
1276  << MI);
1277  }
1278 }
1279 
1282  MachineBasicBlock &SuccMBB) {
1283  auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
1284  for (MachineInstr &MI : MBB.instrs())
1285  if (MI.isDebugInstr()) {
1286  TII->duplicate(SuccMBB, InsertBefore, MI);
1287  LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "
1288  << MI);
1289  }
1290 }
1291 
1292 // Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
1293 // a basic block is removed we would lose the debug information unless we have
1294 // copied the information to a predecessor/successor.
1295 //
1296 // TODO: This function only handles some simple cases. An alternative would be
1297 // to run a heavier analysis, such as the LiveDebugValues pass, before we do
1298 // branch folding.
1301  assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).");
1302  // If this MBB is the only predecessor of a successor it is legal to copy
1303  // DBG_VALUE instructions to the beginning of the successor.
1304  for (MachineBasicBlock *SuccBB : MBB.successors())
1305  if (SuccBB->pred_size() == 1)
1306  copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
1307  // If this MBB is the only successor of a predecessor it is legal to copy the
1308  // DBG_VALUE instructions to the end of the predecessor (just before the
1309  // terminators, assuming that the terminator isn't affecting the DBG_VALUE).
1310  for (MachineBasicBlock *PredBB : MBB.predecessors())
1311  if (PredBB->succ_size() == 1)
1312  copyDebugInfoToPredecessor(TII, MBB, *PredBB);
1313 }
1314 
1315 bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
1316  bool MadeChange = false;
1317  MachineFunction &MF = *MBB->getParent();
1318 ReoptimizeBlock:
1319 
1320  MachineFunction::iterator FallThrough = MBB->getIterator();
1321  ++FallThrough;
1322 
1323  // Make sure MBB and FallThrough belong to the same EH scope.
1324  bool SameEHScope = true;
1325  if (!EHScopeMembership.empty() && FallThrough != MF.end()) {
1326  auto MBBEHScope = EHScopeMembership.find(MBB);
1327  assert(MBBEHScope != EHScopeMembership.end());
1328  auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1329  assert(FallThroughEHScope != EHScopeMembership.end());
1330  SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1331  }
1332 
1333  // Analyze the branch in the current block. As a side-effect, this may cause
1334  // the block to become empty.
1335  MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
1337  bool CurUnAnalyzable =
1338  TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
1339 
1340  // If this block is empty, make everyone use its fall-through, not the block
1341  // explicitly. Landing pads should not do this since the landing-pad table
1342  // points to this block. Blocks with their addresses taken shouldn't be
1343  // optimized away.
1344  if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
1345  SameEHScope) {
1347  // Dead block? Leave for cleanup later.
1348  if (MBB->pred_empty()) return MadeChange;
1349 
1350  if (FallThrough == MF.end()) {
1351  // TODO: Simplify preds to not branch here if possible!
1352  } else if (FallThrough->isEHPad()) {
1353  // Don't rewrite to a landing pad fallthough. That could lead to the case
1354  // where a BB jumps to more than one landing pad.
1355  // TODO: Is it ever worth rewriting predecessors which don't already
1356  // jump to a landing pad, and so can safely jump to the fallthrough?
1357  } else if (MBB->isSuccessor(&*FallThrough)) {
1358  // Rewrite all predecessors of the old block to go to the fallthrough
1359  // instead.
1360  while (!MBB->pred_empty()) {
1361  MachineBasicBlock *Pred = *(MBB->pred_end()-1);
1362  Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
1363  }
1364  // If MBB was the target of a jump table, update jump tables to go to the
1365  // fallthrough instead.
1366  if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1367  MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
1368  MadeChange = true;
1369  }
1370  return MadeChange;
1371  }
1372 
1373  // Check to see if we can simplify the terminator of the block before this
1374  // one.
1375  MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
1376 
1377  MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
1379  bool PriorUnAnalyzable =
1380  TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
1381  if (!PriorUnAnalyzable) {
1382  // If the previous branch is conditional and both conditions go to the same
1383  // destination, remove the branch, replacing it with an unconditional one or
1384  // a fall-through.
1385  if (PriorTBB && PriorTBB == PriorFBB) {
1386  DebugLoc dl = getBranchDebugLoc(PrevBB);
1387  TII->removeBranch(PrevBB);
1388  PriorCond.clear();
1389  if (PriorTBB != MBB)
1390  TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1391  MadeChange = true;
1392  ++NumBranchOpts;
1393  goto ReoptimizeBlock;
1394  }
1395 
1396  // If the previous block unconditionally falls through to this block and
1397  // this block has no other predecessors, move the contents of this block
1398  // into the prior block. This doesn't usually happen when SimplifyCFG
1399  // has been used, but it can happen if tail merging splits a fall-through
1400  // predecessor of a block.
1401  // This has to check PrevBB->succ_size() because EH edges are ignored by
1402  // analyzeBranch.
1403  if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
1404  PrevBB.succ_size() == 1 &&
1405  !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1406  LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBB
1407  << "From MBB: " << *MBB);
1408  // Remove redundant DBG_VALUEs first.
1409  if (!PrevBB.empty()) {
1410  MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
1411  --PrevBBIter;
1412  MachineBasicBlock::iterator MBBIter = MBB->begin();
1413  // Check if DBG_VALUE at the end of PrevBB is identical to the
1414  // DBG_VALUE at the beginning of MBB.
1415  while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
1416  && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1417  if (!MBBIter->isIdenticalTo(*PrevBBIter))
1418  break;
1419  MachineInstr &DuplicateDbg = *MBBIter;
1420  ++MBBIter; -- PrevBBIter;
1421  DuplicateDbg.eraseFromParent();
1422  }
1423  }
1424  PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1425  PrevBB.removeSuccessor(PrevBB.succ_begin());
1426  assert(PrevBB.succ_empty());
1427  PrevBB.transferSuccessors(MBB);
1428  MadeChange = true;
1429  return MadeChange;
1430  }
1431 
1432  // If the previous branch *only* branches to *this* block (conditional or
1433  // not) remove the branch.
1434  if (PriorTBB == MBB && !PriorFBB) {
1435  TII->removeBranch(PrevBB);
1436  MadeChange = true;
1437  ++NumBranchOpts;
1438  goto ReoptimizeBlock;
1439  }
1440 
1441  // If the prior block branches somewhere else on the condition and here if
1442  // the condition is false, remove the uncond second branch.
1443  if (PriorFBB == MBB) {
1444  DebugLoc dl = getBranchDebugLoc(PrevBB);
1445  TII->removeBranch(PrevBB);
1446  TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1447  MadeChange = true;
1448  ++NumBranchOpts;
1449  goto ReoptimizeBlock;
1450  }
1451 
1452  // If the prior block branches here on true and somewhere else on false, and
1453  // if the branch condition is reversible, reverse the branch to create a
1454  // fall-through.
1455  if (PriorTBB == MBB) {
1456  SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1457  if (!TII->reverseBranchCondition(NewPriorCond)) {
1458  DebugLoc dl = getBranchDebugLoc(PrevBB);
1459  TII->removeBranch(PrevBB);
1460  TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
1461  MadeChange = true;
1462  ++NumBranchOpts;
1463  goto ReoptimizeBlock;
1464  }
1465  }
1466 
1467  // If this block has no successors (e.g. it is a return block or ends with
1468  // a call to a no-return function like abort or __cxa_throw) and if the pred
1469  // falls through into this block, and if it would otherwise fall through
1470  // into the block after this, move this block to the end of the function.
1471  //
1472  // We consider it more likely that execution will stay in the function (e.g.
1473  // due to loops) than it is to exit it. This asserts in loops etc, moving
1474  // the assert condition out of the loop body.
1475  if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
1476  MachineFunction::iterator(PriorTBB) == FallThrough &&
1477  !MBB->canFallThrough()) {
1478  bool DoTransform = true;
1479 
1480  // We have to be careful that the succs of PredBB aren't both no-successor
1481  // blocks. If neither have successors and if PredBB is the second from
1482  // last block in the function, we'd just keep swapping the two blocks for
1483  // last. Only do the swap if one is clearly better to fall through than
1484  // the other.
1485  if (FallThrough == --MF.end() &&
1486  !IsBetterFallthrough(PriorTBB, MBB))
1487  DoTransform = false;
1488 
1489  if (DoTransform) {
1490  // Reverse the branch so we will fall through on the previous true cond.
1491  SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1492  if (!TII->reverseBranchCondition(NewPriorCond)) {
1493  LLVM_DEBUG(dbgs() << "\nMoving MBB: " << *MBB
1494  << "To make fallthrough to: " << *PriorTBB << "\n");
1495 
1496  DebugLoc dl = getBranchDebugLoc(PrevBB);
1497  TII->removeBranch(PrevBB);
1498  TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
1499 
1500  // Move this block to the end of the function.
1501  MBB->moveAfter(&MF.back());
1502  MadeChange = true;
1503  ++NumBranchOpts;
1504  return MadeChange;
1505  }
1506  }
1507  }
1508  }
1509 
1510  bool OptForSize =
1511  MF.getFunction().hasOptSize() ||
1512  llvm::shouldOptimizeForSize(MBB, PSI, &MBBFreqInfo);
1513  if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1 && OptForSize) {
1514  // Changing "Jcc foo; foo: jmp bar;" into "Jcc bar;" might change the branch
1515  // direction, thereby defeating careful block placement and regressing
1516  // performance. Therefore, only consider this for optsize functions.
1518  if (TII->isUnconditionalTailCall(TailCall)) {
1519  MachineBasicBlock *Pred = *MBB->pred_begin();
1520  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1522  bool PredAnalyzable =
1523  !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
1524 
1525  if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&
1526  PredTBB != PredFBB) {
1527  // The predecessor has a conditional branch to this block which consists
1528  // of only a tail call. Try to fold the tail call into the conditional
1529  // branch.
1530  if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
1531  // TODO: It would be nice if analyzeBranch() could provide a pointer
1532  // to the branch instruction so replaceBranchWithTailCall() doesn't
1533  // have to search for it.
1534  TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
1535  ++NumTailCalls;
1536  Pred->removeSuccessor(MBB);
1537  MadeChange = true;
1538  return MadeChange;
1539  }
1540  }
1541  // If the predecessor is falling through to this block, we could reverse
1542  // the branch condition and fold the tail call into that. However, after
1543  // that we might have to re-arrange the CFG to fall through to the other
1544  // block and there is a high risk of regressing code size rather than
1545  // improving it.
1546  }
1547  }
1548 
1549  if (!CurUnAnalyzable) {
1550  // If this is a two-way branch, and the FBB branches to this block, reverse
1551  // the condition so the single-basic-block loop is faster. Instead of:
1552  // Loop: xxx; jcc Out; jmp Loop
1553  // we want:
1554  // Loop: xxx; jncc Loop; jmp Out
1555  if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
1556  SmallVector<MachineOperand, 4> NewCond(CurCond);
1557  if (!TII->reverseBranchCondition(NewCond)) {
1559  TII->removeBranch(*MBB);
1560  TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
1561  MadeChange = true;
1562  ++NumBranchOpts;
1563  goto ReoptimizeBlock;
1564  }
1565  }
1566 
1567  // If this branch is the only thing in its block, see if we can forward
1568  // other blocks across it.
1569  if (CurTBB && CurCond.empty() && !CurFBB &&
1570  IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
1571  !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1573  // This block may contain just an unconditional branch. Because there can
1574  // be 'non-branch terminators' in the block, try removing the branch and
1575  // then seeing if the block is empty.
1576  TII->removeBranch(*MBB);
1577  // If the only things remaining in the block are debug info, remove these
1578  // as well, so this will behave the same as an empty block in non-debug
1579  // mode.
1580  if (IsEmptyBlock(MBB)) {
1581  // Make the block empty, losing the debug info (we could probably
1582  // improve this in some cases.)
1583  MBB->erase(MBB->begin(), MBB->end());
1584  }
1585  // If this block is just an unconditional branch to CurTBB, we can
1586  // usually completely eliminate the block. The only case we cannot
1587  // completely eliminate the block is when the block before this one
1588  // falls through into MBB and we can't understand the prior block's branch
1589  // condition.
1590  if (MBB->empty()) {
1591  bool PredHasNoFallThrough = !PrevBB.canFallThrough();
1592  if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1593  !PrevBB.isSuccessor(MBB)) {
1594  // If the prior block falls through into us, turn it into an
1595  // explicit branch to us to make updates simpler.
1596  if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
1597  PriorTBB != MBB && PriorFBB != MBB) {
1598  if (!PriorTBB) {
1599  assert(PriorCond.empty() && !PriorFBB &&
1600  "Bad branch analysis");
1601  PriorTBB = MBB;
1602  } else {
1603  assert(!PriorFBB && "Machine CFG out of date!");
1604  PriorFBB = MBB;
1605  }
1606  DebugLoc pdl = getBranchDebugLoc(PrevBB);
1607  TII->removeBranch(PrevBB);
1608  TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1609  }
1610 
1611  // Iterate through all the predecessors, revectoring each in-turn.
1612  size_t PI = 0;
1613  bool DidChange = false;
1614  bool HasBranchToSelf = false;
1615  while(PI != MBB->pred_size()) {
1616  MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
1617  if (PMBB == MBB) {
1618  // If this block has an uncond branch to itself, leave it.
1619  ++PI;
1620  HasBranchToSelf = true;
1621  } else {
1622  DidChange = true;
1623  PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
1624  // If this change resulted in PMBB ending in a conditional
1625  // branch where both conditions go to the same destination,
1626  // change this to an unconditional branch.
1627  MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
1628  SmallVector<MachineOperand, 4> NewCurCond;
1629  bool NewCurUnAnalyzable = TII->analyzeBranch(
1630  *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);
1631  if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1632  DebugLoc pdl = getBranchDebugLoc(*PMBB);
1633  TII->removeBranch(*PMBB);
1634  NewCurCond.clear();
1635  TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
1636  MadeChange = true;
1637  ++NumBranchOpts;
1638  }
1639  }
1640  }
1641 
1642  // Change any jumptables to go to the new MBB.
1643  if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1644  MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
1645  if (DidChange) {
1646  ++NumBranchOpts;
1647  MadeChange = true;
1648  if (!HasBranchToSelf) return MadeChange;
1649  }
1650  }
1651  }
1652 
1653  // Add the branch back if the block is more than just an uncond branch.
1654  TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
1655  }
1656  }
1657 
1658  // If the prior block doesn't fall through into this block, and if this
1659  // block doesn't fall through into some other block, see if we can find a
1660  // place to move this block where a fall-through will happen.
1661  if (!PrevBB.canFallThrough()) {
1662  // Now we know that there was no fall-through into this block, check to
1663  // see if it has a fall-through into its successor.
1664  bool CurFallsThru = MBB->canFallThrough();
1665 
1666  if (!MBB->isEHPad()) {
1667  // Check all the predecessors of this block. If one of them has no fall
1668  // throughs, and analyzeBranch thinks it _could_ fallthrough to this
1669  // block, move this block right after it.
1670  for (MachineBasicBlock *PredBB : MBB->predecessors()) {
1671  // Analyze the branch at the end of the pred.
1672  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1674  if (PredBB != MBB && !PredBB->canFallThrough() &&
1675  !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&
1676  (PredTBB == MBB || PredFBB == MBB) &&
1677  (!CurFallsThru || !CurTBB || !CurFBB) &&
1678  (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1679  // If the current block doesn't fall through, just move it.
1680  // If the current block can fall through and does not end with a
1681  // conditional branch, we need to append an unconditional jump to
1682  // the (current) next block. To avoid a possible compile-time
1683  // infinite loop, move blocks only backward in this case.
1684  // Also, if there are already 2 branches here, we cannot add a third;
1685  // this means we have the case
1686  // Bcc next
1687  // B elsewhere
1688  // next:
1689  if (CurFallsThru) {
1690  MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
1691  CurCond.clear();
1692  TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
1693  }
1694  MBB->moveAfter(PredBB);
1695  MadeChange = true;
1696  goto ReoptimizeBlock;
1697  }
1698  }
1699  }
1700 
1701  if (!CurFallsThru) {
1702  // Check analyzable branch-successors to see if we can move this block
1703  // before one.
1704  if (!CurUnAnalyzable) {
1705  for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {
1706  if (!SuccBB)
1707  continue;
1708  // Analyze the branch at the end of the block before the succ.
1709  MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
1710 
1711  // If this block doesn't already fall-through to that successor, and
1712  // if the succ doesn't already have a block that can fall through into
1713  // it, we can arrange for the fallthrough to happen.
1714  if (SuccBB != MBB && &*SuccPrev != MBB &&
1715  !SuccPrev->canFallThrough()) {
1716  MBB->moveBefore(SuccBB);
1717  MadeChange = true;
1718  goto ReoptimizeBlock;
1719  }
1720  }
1721  }
1722 
1723  // Okay, there is no really great place to put this block. If, however,
1724  // the block before this one would be a fall-through if this block were
1725  // removed, move this block to the end of the function. There is no real
1726  // advantage in "falling through" to an EH block, so we don't want to
1727  // perform this transformation for that case.
1728  //
1729  // Also, Windows EH introduced the possibility of an arbitrary number of
1730  // successors to a given block. The analyzeBranch call does not consider
1731  // exception handling and so we can get in a state where a block
1732  // containing a call is followed by multiple EH blocks that would be
1733  // rotated infinitely at the end of the function if the transformation
1734  // below were performed for EH "FallThrough" blocks. Therefore, even if
1735  // that appears not to be happening anymore, we should assume that it is
1736  // possible and not remove the "!FallThrough()->isEHPad" condition below.
1737  MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
1739  if (FallThrough != MF.end() &&
1740  !FallThrough->isEHPad() &&
1741  !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1742  PrevBB.isSuccessor(&*FallThrough)) {
1743  MBB->moveAfter(&MF.back());
1744  MadeChange = true;
1745  return MadeChange;
1746  }
1747  }
1748  }
1749 
1750  return MadeChange;
1751 }
1752 
1753 //===----------------------------------------------------------------------===//
1754 // Hoist Common Code
1755 //===----------------------------------------------------------------------===//
1756 
1757 bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
1758  bool MadeChange = false;
1760  MadeChange |= HoistCommonCodeInSuccs(&MBB);
1761 
1762  return MadeChange;
1763 }
1764 
1765 /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
1766 /// its 'true' successor.
1768  MachineBasicBlock *TrueBB) {
1769  for (MachineBasicBlock *SuccBB : BB->successors())
1770  if (SuccBB != TrueBB)
1771  return SuccBB;
1772  return nullptr;
1773 }
1774 
1775 template <class Container>
1777  Container &Set) {
1778  if (Reg.isPhysical()) {
1779  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
1780  Set.insert(*AI);
1781  } else {
1782  Set.insert(Reg);
1783  }
1784 }
1785 
1786 /// findHoistingInsertPosAndDeps - Find the location to move common instructions
1787 /// in successors to. The location is usually just before the terminator,
1788 /// however if the terminator is a conditional branch and its previous
1789 /// instruction is the flag setting instruction, the previous instruction is
1790 /// the preferred location. This function also gathers uses and defs of the
1791 /// instructions from the insertion point to the end of the block. The data is
1792 /// used by HoistCommonCodeInSuccs to ensure safety.
1793 static
1795  const TargetInstrInfo *TII,
1796  const TargetRegisterInfo *TRI,
1798  SmallSet<Register, 4> &Defs) {
1800  if (!TII->isUnpredicatedTerminator(*Loc))
1801  return MBB->end();
1802 
1803  for (const MachineOperand &MO : Loc->operands()) {
1804  if (!MO.isReg())
1805  continue;
1806  Register Reg = MO.getReg();
1807  if (!Reg)
1808  continue;
1809  if (MO.isUse()) {
1811  } else {
1812  if (!MO.isDead())
1813  // Don't try to hoist code in the rare case the terminator defines a
1814  // register that is later used.
1815  return MBB->end();
1816 
1817  // If the terminator defines a register, make sure we don't hoist
1818  // the instruction whose def might be clobbered by the terminator.
1819  addRegAndItsAliases(Reg, TRI, Defs);
1820  }
1821  }
1822 
1823  if (Uses.empty())
1824  return Loc;
1825  // If the terminator is the only instruction in the block and Uses is not
1826  // empty (or we would have returned above), we can still safely hoist
1827  // instructions just before the terminator as long as the Defs/Uses are not
1828  // violated (which is checked in HoistCommonCodeInSuccs).
1829  if (Loc == MBB->begin())
1830  return Loc;
1831 
1832  // The terminator is probably a conditional branch, try not to separate the
1833  // branch from condition setting instruction.
1835 
1836  bool IsDef = false;
1837  for (const MachineOperand &MO : PI->operands()) {
1838  // If PI has a regmask operand, it is probably a call. Separate away.
1839  if (MO.isRegMask())
1840  return Loc;
1841  if (!MO.isReg() || MO.isUse())
1842  continue;
1843  Register Reg = MO.getReg();
1844  if (!Reg)
1845  continue;
1846  if (Uses.count(Reg)) {
1847  IsDef = true;
1848  break;
1849  }
1850  }
1851  if (!IsDef)
1852  // The condition setting instruction is not just before the conditional
1853  // branch.
1854  return Loc;
1855 
1856  // Be conservative, don't insert instruction above something that may have
1857  // side-effects. And since it's potentially bad to separate flag setting
1858  // instruction from the conditional branch, just abort the optimization
1859  // completely.
1860  // Also avoid moving code above predicated instruction since it's hard to
1861  // reason about register liveness with predicated instruction.
1862  bool DontMoveAcrossStore = true;
1863  if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
1864  return MBB->end();
1865 
1866  // Find out what registers are live. Note this routine is ignoring other live
1867  // registers which are only used by instructions in successor blocks.
1868  for (const MachineOperand &MO : PI->operands()) {
1869  if (!MO.isReg())
1870  continue;
1871  Register Reg = MO.getReg();
1872  if (!Reg)
1873  continue;
1874  if (MO.isUse()) {
1876  } else {
1877  if (Uses.erase(Reg)) {
1879  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1880  Uses.erase(*SubRegs); // Use sub-registers to be conservative
1881  }
1882  }
1883  addRegAndItsAliases(Reg, TRI, Defs);
1884  }
1885  }
1886 
1887  return PI;
1888 }
1889 
1890 bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
1891  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1893  if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
1894  return false;
1895 
1896  if (!FBB) FBB = findFalseBlock(MBB, TBB);
1897  if (!FBB)
1898  // Malformed bcc? True and false blocks are the same?
1899  return false;
1900 
1901  // Restrict the optimization to cases where MBB is the only predecessor,
1902  // it is an obvious win.
1903  if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
1904  return false;
1905 
1906  // Find a suitable position to hoist the common instructions to. Also figure
1907  // out which registers are used or defined by instructions from the insertion
1908  // point to the end of the block.
1911  findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
1912  if (Loc == MBB->end())
1913  return false;
1914 
1915  bool HasDups = false;
1916  SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;
1917  MachineBasicBlock::iterator TIB = TBB->begin();
1918  MachineBasicBlock::iterator FIB = FBB->begin();
1919  MachineBasicBlock::iterator TIE = TBB->end();
1920  MachineBasicBlock::iterator FIE = FBB->end();
1921  while (TIB != TIE && FIB != FIE) {
1922  // Skip dbg_value instructions. These do not count.
1923  TIB = skipDebugInstructionsForward(TIB, TIE, false);
1924  FIB = skipDebugInstructionsForward(FIB, FIE, false);
1925  if (TIB == TIE || FIB == FIE)
1926  break;
1927 
1928  if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
1929  break;
1930 
1931  if (TII->isPredicated(*TIB))
1932  // Hard to reason about register liveness with predicated instruction.
1933  break;
1934 
1935  bool IsSafe = true;
1936  for (MachineOperand &MO : TIB->operands()) {
1937  // Don't attempt to hoist instructions with register masks.
1938  if (MO.isRegMask()) {
1939  IsSafe = false;
1940  break;
1941  }
1942  if (!MO.isReg())
1943  continue;
1944  Register Reg = MO.getReg();
1945  if (!Reg)
1946  continue;
1947  if (MO.isDef()) {
1948  if (Uses.count(Reg)) {
1949  // Avoid clobbering a register that's used by the instruction at
1950  // the point of insertion.
1951  IsSafe = false;
1952  break;
1953  }
1954 
1955  if (Defs.count(Reg) && !MO.isDead()) {
1956  // Don't hoist the instruction if the def would be clobber by the
1957  // instruction at the point insertion. FIXME: This is overly
1958  // conservative. It should be possible to hoist the instructions
1959  // in BB2 in the following example:
1960  // BB1:
1961  // r1, eflag = op1 r2, r3
1962  // brcc eflag
1963  //
1964  // BB2:
1965  // r1 = op2, ...
1966  // = op3, killed r1
1967  IsSafe = false;
1968  break;
1969  }
1970  } else if (!ActiveDefsSet.count(Reg)) {
1971  if (Defs.count(Reg)) {
1972  // Use is defined by the instruction at the point of insertion.
1973  IsSafe = false;
1974  break;
1975  }
1976 
1977  if (MO.isKill() && Uses.count(Reg))
1978  // Kills a register that's read by the instruction at the point of
1979  // insertion. Remove the kill marker.
1980  MO.setIsKill(false);
1981  }
1982  }
1983  if (!IsSafe)
1984  break;
1985 
1986  bool DontMoveAcrossStore = true;
1987  if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
1988  break;
1989 
1990  // Remove kills from ActiveDefsSet, these registers had short live ranges.
1991  for (const MachineOperand &MO : TIB->operands()) {
1992  if (!MO.isReg() || !MO.isUse() || !MO.isKill())
1993  continue;
1994  Register Reg = MO.getReg();
1995  if (!Reg)
1996  continue;
1997  if (!AllDefsSet.count(Reg)) {
1998  continue;
1999  }
2000  if (Reg.isPhysical()) {
2001  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
2002  ActiveDefsSet.erase(*AI);
2003  } else {
2004  ActiveDefsSet.erase(Reg);
2005  }
2006  }
2007 
2008  // Track local defs so we can update liveins.
2009  for (const MachineOperand &MO : TIB->operands()) {
2010  if (!MO.isReg() || !MO.isDef() || MO.isDead())
2011  continue;
2012  Register Reg = MO.getReg();
2013  if (!Reg || Reg.isVirtual())
2014  continue;
2015  addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
2016  addRegAndItsAliases(Reg, TRI, AllDefsSet);
2017  }
2018 
2019  HasDups = true;
2020  ++TIB;
2021  ++FIB;
2022  }
2023 
2024  if (!HasDups)
2025  return false;
2026 
2027  MBB->splice(Loc, TBB, TBB->begin(), TIB);
2028  FBB->erase(FBB->begin(), FIB);
2029 
2030  if (UpdateLiveIns) {
2031  recomputeLiveIns(*TBB);
2032  recomputeLiveIns(*FBB);
2033  }
2034 
2035  ++NumHoist;
2036  return true;
2037 }
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::BranchFolder
Definition: BranchFolding.h:31
i
i
Definition: README.txt:29
findHoistingInsertPosAndDeps
static MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, SmallSet< Register, 4 > &Uses, SmallSet< Register, 4 > &Defs)
findHoistingInsertPosAndDeps - Find the location to move common instructions in successors to.
Definition: BranchFolding.cpp:1794
llvm::array_pod_sort
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1520
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:354
IsBetterFallthrough
static bool IsBetterFallthrough(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
IsBetterFallthrough - Return true if it would be clearly better to fall-through to MBB1 than to fall ...
Definition: BranchFolding.cpp:1238
HashEndOfMBB
static unsigned HashEndOfMBB(const MachineBasicBlock &MBB)
HashEndOfMBB - Hash the last instruction in the MBB.
Definition: BranchFolding.cpp:292
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:326
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
MachineInstr.h
llvm::MachineOperand::MO_Immediate
@ MO_Immediate
Immediate operand.
Definition: MachineOperand.h:52
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
copyDebugInfoToSuccessor
static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &SuccMBB)
Definition: BranchFolding.cpp:1280
llvm::computeLiveIns
void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)
Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date.
Definition: LivePhysRegs.cpp:248
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:280
llvm::MachineInstr::isIndirectBranch
bool isIndirectBranch(QueryType Type=AnyInBundle) const
Return true if this is an indirect branch, such as a branch through a register.
Definition: MachineInstr.h:868
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:126
llvm::TargetInstrInfo::replaceBranchWithTailCall
virtual void replaceBranchWithTailCall(MachineBasicBlock &MBB, SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Replace the conditional branch in MBB with a conditional tail call.
Definition: TargetInstrInfo.h:1458
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
llvm::DILocation::getMergedLocation
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
Definition: DebugInfoMetadata.cpp:101
skipBackwardPastNonInstructions
static MachineBasicBlock::iterator skipBackwardPastNonInstructions(MachineBasicBlock::iterator I, MachineBasicBlock *MBB)
Iterate backwards from the given iterator I, towards the beginning of the block.
Definition: BranchFolding.cpp:309
DebugInfoMetadata.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::MachineBasicBlock::ReplaceUsesOfBlockWith
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to 'Old', change the code and CFG so that it branches to 'N...
Definition: MachineBasicBlock.cpp:1339
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::cl::BOU_FALSE
@ BOU_FALSE
Definition: CommandLine.h:611
Pass.h
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:344
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::MachineBasicBlock::instrs
instr_range instrs()
Definition: MachineBasicBlock.h:273
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::MachineInstr::CheckKillDead
@ CheckKillDead
Definition: MachineInstr.h:1149
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:855
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:116
ErrorHandling.h
llvm::recomputeLiveIns
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for MBB.
Definition: LivePhysRegs.h:198
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::MachineBasicBlock::setSuccProbability
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
Definition: MachineBasicBlock.cpp:1451
MachineSizeOpts.h
llvm::MachineFunction::back
const MachineBasicBlock & back() const
Definition: MachineFunction.h:867
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
ProfitableToMerge
static bool ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, unsigned MinCommonTailLength, unsigned &CommonTailLen, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB, MachineBasicBlock *PredBB, DenseMap< const MachineBasicBlock *, int > &EHScopeMembership, bool AfterPlacement, MBFIWrapper &MBBFreqInfo, ProfileSummaryInfo *PSI)
ProfitableToMerge - Check if two machine basic blocks have a common tail and decide if it would be pr...
Definition: BranchFolding.cpp:544
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
BlockFrequency.h
llvm::MachineBasicBlock::moveBefore
void moveBefore(MachineBasicBlock *NewAfter)
Move 'this' block before or after the specified block.
Definition: MachineBasicBlock.cpp:634
MachineJumpTableInfo.h
llvm::TargetInstrInfo::ReplaceTailWithBranchTo
virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail, MachineBasicBlock *NewDest) const
Delete the instruction OldInst and everything after it, replacing it with an unconditional branch to ...
Definition: TargetInstrInfo.cpp:139
llvm::MachineBasicBlock::liveins
iterator_range< livein_iterator > liveins() const
Definition: MachineBasicBlock.h:422
TargetInstrInfo.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::HexagonInstrInfo::isPredicated
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
Definition: HexagonInstrInfo.cpp:1659
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::MachineFunction::insert
void insert(iterator MBBI, MachineBasicBlock *MBB)
Definition: MachineFunction.h:872
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
MBFIWrapper.h
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:127
llvm::BranchProbability::getBranchProbability
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
Definition: BranchProbability.cpp:53
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
copyDebugInfoToPredecessor
static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &PredMBB)
Definition: BranchFolding.cpp:1268
IsEmptyBlock
static bool IsEmptyBlock(MachineBasicBlock *MBB)
Definition: BranchFolding.cpp:1222
llvm::addLiveIns
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
Definition: LivePhysRegs.cpp:259
STLExtras.h
llvm::MachineBasicBlock::back
MachineInstr & back()
Definition: MachineBasicBlock.h:258
FixTail
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, const TargetInstrInfo *TII)
Definition: BranchFolding.cpp:457
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::MBFIWrapper::setBlockFreq
void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F)
Definition: MBFIWrapper.cpp:29
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
countsAsInstruction
static bool countsAsInstruction(const MachineInstr &MI)
Whether MI should be counted as an instruction when calculating common tail.
Definition: BranchFolding.cpp:301
llvm::MachineOperand::MO_Register
@ MO_Register
Register operand.
Definition: MachineOperand.h:51
I1
@ I1
Definition: DXILOpLowering.cpp:37
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
MachineRegisterInfo.h
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:585
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::MachineBasicBlock::erase
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Definition: MachineBasicBlock.cpp:1299
llvm::TargetInstrInfo::insertBranch
virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const
Insert branch code into the end of the specified MachineBasicBlock.
Definition: TargetInstrInfo.h:709
llvm::MachineRegisterInfo::tracksLiveness
bool tracksLiveness() const
tracksLiveness - Returns true when tracking register liveness accurately.
Definition: MachineRegisterInfo.h:195
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
CommandLine.h
ComputeCommonTailLength
static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2)
Given two machine basic blocks, return the number of instructions they actually have in common togeth...
Definition: BranchFolding.cpp:325
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:338
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:666
llvm::shouldOptimizeForSize
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
Definition: MachineSizeOpts.cpp:183
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
MachineLoopInfo.h
llvm::TargetInstrInfo::removeBranch
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
Definition: TargetInstrInfo.h:691
TargetMachine.h
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:22
llvm::MachineOperand::MO_GlobalAddress
@ MO_GlobalAddress
Address of a global value.
Definition: MachineOperand.h:61
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineBasicBlock::succ_end
succ_iterator succ_end()
Definition: MachineBasicBlock.h:344
TailMergeThreshold
static cl::opt< unsigned > TailMergeThreshold("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)
llvm::BitVector::size
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:152
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:909
llvm::MachineOperand::MO_FrameIndex
@ MO_FrameIndex
Abstract Stack Frame Index.
Definition: MachineOperand.h:56
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
t
bitcast float %x to i32 %s=and i32 %t, 2147483647 %d=bitcast i32 %s to float ret float %d } declare float @fabsf(float %n) define float @bar(float %x) nounwind { %d=call float @fabsf(float %x) ret float %d } This IR(from PR6194):target datalayout="e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple="x86_64-apple-darwin10.0.0" %0=type { double, double } %struct.float3=type { float, float, float } define void @test(%0, %struct.float3 *nocapture %res) nounwind noinline ssp { entry:%tmp18=extractvalue %0 %0, 0 t
Definition: README-SSE.txt:788
llvm::TargetPassConfig::getEnableTailMerge
bool getEnableTailMerge() const
Definition: TargetPassConfig.h:176
llvm::LivePhysRegs::addLiveOuts
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
Definition: LivePhysRegs.cpp:232
TargetOpcodes.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:196
llvm::MachineBasicBlock::RegisterMaskPair
Pair of physical register and lane mask.
Definition: MachineBasicBlock.h:100
llvm::BranchFolder::BranchFolder
BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist, MBFIWrapper &FreqInfo, const MachineBranchProbabilityInfo &ProbInfo, ProfileSummaryInfo *PSI, unsigned MinTailLength=0)
Definition: BranchFolding.cpp:141
llvm::MachineBasicBlock::rend
reverse_iterator rend()
Definition: MachineBasicBlock.h:288
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
BitVector.h
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:853
FlagEnableTailMerge
static cl::opt< cl::boolOrDefault > FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
llvm::TargetInstrInfo::reverseBranchCondition
virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const
Reverses the branch condition of the specified condition list, returning false on success and true if...
Definition: TargetInstrInfo.h:1415
llvm::computeAndAddLiveIns
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
Definition: LivePhysRegs.cpp:341
DebugLoc.h
llvm::BitVector
Definition: BitVector.h:75
BranchFolding.h
llvm::MBFIWrapper
Definition: MBFIWrapper.h:26
getBranchDebugLoc
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB)
getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.
Definition: BranchFolding.cpp:1261
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
BranchProbability.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::TargetPassConfig
Target-Independent Code Generator Pass Configuration Options.
Definition: TargetPassConfig.h:84
llvm::TargetInstrInfo::canMakeTailCallConditional
virtual bool canMakeTailCallConditional(SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Returns true if the tail call can be made conditional on BranchCond.
Definition: TargetInstrInfo.h:1452
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::MachineJumpTableInfo::getJumpTables
const std::vector< MachineJumpTableEntry > & getJumpTables() const
Definition: MachineJumpTableInfo.h:99
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
llvm::LivePhysRegs::stepBackward
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
Definition: LivePhysRegs.cpp:68
llvm::BlockFrequency
Definition: BlockFrequency.h:23
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:394
llvm::SmallSet::count
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
llvm::cl::BOU_UNSET
@ BOU_UNSET
Definition: CommandLine.h:611
llvm::MachineBasicBlock::pred_end
pred_iterator pred_end()
Definition: MachineBasicBlock.h:328
TailMergeSize
static cl::opt< unsigned > TailMergeSize("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
ProfileSummaryInfo.h
INITIALIZE_PASS
INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE, "Control Flow Optimizer", false, false) bool BranchFolderPass
Definition: BranchFolding.cpp:120
llvm::MachineBasicBlock::hasAddressTaken
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
Definition: MachineBasicBlock.h:220
llvm::TargetInstrInfo::isPredicated
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
Definition: TargetInstrInfo.h:1435
llvm::LivePhysRegs::available
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
Definition: LivePhysRegs.cpp:141
llvm::MachineBasicBlock::SkipPHIsAndLabels
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
Definition: MachineBasicBlock.cpp:206
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
Analysis.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:618
MCRegisterInfo.h
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:193
addRegAndItsAliases
static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI, Container &Set)
Definition: BranchFolding.cpp:1776
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:439
llvm::prev_nodbg
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It, then continue decrementing it while it points to a debug instruction.
Definition: MachineBasicBlock.h:1269
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
TargetPassConfig.h
MachineFunctionPass.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::canFallThrough
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
Definition: MachineBasicBlock.cpp:966
MachineBranchProbabilityInfo.h
llvm::MachineBasicBlock::succ_begin
succ_iterator succ_begin()
Definition: MachineBasicBlock.h:342
salvageDebugInfoFromEmptyBlock
static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII, MachineBasicBlock &MBB)
Definition: BranchFolding.cpp:1299
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:234
llvm::MachineFunction::erase
void erase(iterator MBBI)
Definition: MachineFunction.h:887
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:359
llvm::MachineBranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Definition: MachineBranchProbabilityInfo.cpp:56
llvm::BranchFolder::OptimizeFunction
bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, const TargetRegisterInfo *tri, MachineLoopInfo *mli=nullptr, bool AfterPlacement=false)
Perhaps branch folding, tail merging and other CFG optimizations on the given function.
Definition: BranchFolding.cpp:182
llvm::MachineInstr::isReturn
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:820
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:341
llvm::SmallSet::erase
bool erase(const T &V)
Definition: SmallSet.h:209
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::TargetInstrInfo::isLegalToSplitMBBAt
virtual bool isLegalToSplitMBBAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI) const
Return true if it's legal to split the given basic block at the specified instruction (i....
Definition: TargetInstrInfo.h:802
llvm::MachineBasicBlock::moveAfter
void moveAfter(MachineBasicBlock *NewBefore)
Definition: MachineBasicBlock.cpp:638
llvm::MachineBasicBlock::succ_empty
bool succ_empty() const
Definition: MachineBasicBlock.h:357
llvm::MachineOperand::MO_JumpTableIndex
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
Definition: MachineOperand.h:59
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:238
llvm::skipDebugInstructionsForward
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Definition: MachineBasicBlock.h:1238
CountTerminators
static unsigned CountTerminators(MachineBasicBlock *MBB, MachineBasicBlock::iterator &I)
CountTerminators - Count the number of terminators in the given block and set I to the position of th...
Definition: BranchFolding.cpp:500
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
HashMachineInstr
static unsigned HashMachineInstr(const MachineInstr &MI)
HashMachineInstr - Compute a hash value for MI and its operands.
Definition: BranchFolding.cpp:252
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:365
llvm::MachineBasicBlock::getFirstNonDebugInstr
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
Definition: MachineBasicBlock.cpp:257
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:549
llvm::MachineBasicBlock::rbegin
reverse_iterator rbegin()
Definition: MachineBasicBlock.h:282
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
llvm::LivePhysRegs::init
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:68
MBBI
MachineBasicBlock MachineBasicBlock::iterator MBBI
Definition: AArch64SLSHardening.cpp:75
llvm::MachineBasicBlock::findBranchDebugLoc
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
Definition: MachineBasicBlock.cpp:1412
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::BranchFolderPassID
char & BranchFolderPassID
BranchFolding - This pass performs machine code CFG based optimizations to delete branches to branche...
Definition: BranchFolding.cpp:118
llvm::MachineOperand::setIsUndef
void setIsUndef(bool Val=true)
Definition: MachineOperand.h:520
llvm::MachineRegisterInfo::invalidateLiveness
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
Definition: MachineRegisterInfo.h:205
llvm::MachineOperand::MO_MachineBasicBlock
@ MO_MachineBasicBlock
MachineBasicBlock reference.
Definition: MachineOperand.h:55
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::MachineInstr::NoMerge
@ NoMerge
Definition: MachineInstr.h:112
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::MachineJumpTableInfo::RemoveJumpTable
void RemoveJumpTable(unsigned Idx)
RemoveJumpTable - Mark the specific index as being dead.
Definition: MachineJumpTableInfo.h:105
llvm::MipsISD::TailCall
@ TailCall
Definition: MipsISelLowering.h:65
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
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:664
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:98
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:454
llvm::TargetInstrInfo::isUnconditionalTailCall
virtual bool isUnconditionalTailCall(const MachineInstr &MI) const
Returns true if MI is an unconditional tail call.
Definition: TargetInstrInfo.h:1447
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:622
DEBUG_TYPE
#define DEBUG_TYPE
Definition: BranchFolding.cpp:65
llvm::MachineFunctionProperties::Property::NoPHIs
@ NoPHIs
operator<
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
llvm::MachineBasicBlock::removeSuccessor
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:785
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::TargetInstrInfo::analyzeBranch
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
Definition: TargetInstrInfo.h:638
llvm::MachineOperand::MO_ExternalSymbol
@ MO_ExternalSymbol
Name of external global symbol.
Definition: MachineOperand.h:60
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::MachineBasicBlock::isLayoutSuccessor
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
Definition: MachineBasicBlock.cpp:913
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::MachineLoopInfo::getBase
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()
Definition: MachineLoopInfo.h:105
llvm::cl::BOU_TRUE
@ BOU_TRUE
Definition: CommandLine.h:611
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:813
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::LivePhysRegs::clear
void clear()
Clears the set.
Definition: LivePhysRegs.h:75
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:278
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::MachineLoopInfo::removeBlock
void removeBlock(MachineBasicBlock *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: MachineLoopInfo.h:178
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
LaneBitmask.h
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:250
llvm::MachineBasicBlock::clearLiveIns
void clearLiveIns()
Clear live in list.
Definition: MachineBasicBlock.cpp:1596
blockEndsInUnreachable
static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)
A no successor, non-return block probably ends in unreachable and is cold.
Definition: BranchFolding.cpp:519
IsBranchOnlyBlock
static bool IsBranchOnlyBlock(MachineBasicBlock *MBB)
Definition: BranchFolding.cpp:1228
MachineOperand.h
mergeOperations
static void mergeOperations(MachineBasicBlock::iterator MBBIStartPos, MachineBasicBlock &MBBCommon)
Definition: BranchFolding.cpp:763
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::MCInstrInfo::get
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
llvm::MachineFunction::getJumpTableInfo
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
Definition: MachineFunction.h:679
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::getEHScopeMembership
DenseMap< const MachineBasicBlock *, int > getEHScopeMembership(const MachineFunction &MF)
Definition: Analysis.cpp:757
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:405
llvm::MachineJumpTableInfo
Definition: MachineJumpTableInfo.h:42
raw_ostream.h
EstimateRuntime
static unsigned EstimateRuntime(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)
EstimateRuntime - Make a rough estimate for how long it will take to run the specified code.
Definition: BranchFolding.cpp:437
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
findFalseBlock
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
findFalseBlock - BB has a fallthrough.
Definition: BranchFolding.cpp:1767
MachineFunction.h
llvm::MachineFunction::eraseCallSiteInfo
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
Definition: MachineFunction.cpp:922
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:650
llvm::MachineInstrBundleIterator< const MachineInstr >
llvm::MachineInstr::isBarrier
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:845
InitializePasses.h
llvm::MBFIWrapper::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
Definition: MBFIWrapper.cpp:20
MachineBlockFrequencyInfo.h
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:280
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
llvm::MachineFunction::RenumberBlocks
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
Definition: MachineFunction.cpp:319
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788
SmallSet.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::MachineOperand::MO_ConstantPoolIndex
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
Definition: MachineOperand.h:57