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