LLVM  13.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()) == I1)
570  I1 = MBB1->begin();
571  if (skipDebugInstructionsForward(MBB2->begin(), MBB2->end()) == 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_size() != 0 && !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 (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
1202  I != E; ) {
1203  MachineBasicBlock *MBB = &*I++;
1204  MadeChange |= OptimizeBlock(MBB);
1205 
1206  // If it is dead, remove it.
1207  if (MBB->pred_empty()) {
1208  RemoveDeadBlock(MBB);
1209  MadeChange = true;
1210  ++NumDeadBlocks;
1211  }
1212  }
1213 
1214  return MadeChange;
1215 }
1216 
1217 // Blocks should be considered empty if they contain only debug info;
1218 // else the debug info would affect codegen.
1220  return MBB->getFirstNonDebugInstr(true) == MBB->end();
1221 }
1222 
1223 // Blocks with only debug info and branches should be considered the same
1224 // as blocks with only branches.
1227  assert(I != MBB->end() && "empty block!");
1228  return I->isBranch();
1229 }
1230 
1231 /// IsBetterFallthrough - Return true if it would be clearly better to
1232 /// fall-through to MBB1 than to fall through into MBB2. This has to return
1233 /// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
1234 /// result in infinite loops.
1236  MachineBasicBlock *MBB2) {
1237  assert(MBB1 && MBB2 && "Unknown MachineBasicBlock");
1238 
1239  // Right now, we use a simple heuristic. If MBB2 ends with a call, and
1240  // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
1241  // optimize branches that branch to either a return block or an assert block
1242  // into a fallthrough to the return.
1245  if (MBB1I == MBB1->end() || MBB2I == MBB2->end())
1246  return false;
1247 
1248  // If there is a clear successor ordering we make sure that one block
1249  // will fall through to the next
1250  if (MBB1->isSuccessor(MBB2)) return true;
1251  if (MBB2->isSuccessor(MBB1)) return false;
1252 
1253  return MBB2I->isCall() && !MBB1I->isCall();
1254 }
1255 
1256 /// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
1257 /// instructions on the block.
1260  if (I != MBB.end() && I->isBranch())
1261  return I->getDebugLoc();
1262  return DebugLoc();
1263 }
1264 
1267  MachineBasicBlock &PredMBB) {
1268  auto InsertBefore = PredMBB.getFirstTerminator();
1269  for (MachineInstr &MI : MBB.instrs())
1270  if (MI.isDebugInstr()) {
1271  TII->duplicate(PredMBB, InsertBefore, MI);
1272  LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "
1273  << MI);
1274  }
1275 }
1276 
1279  MachineBasicBlock &SuccMBB) {
1280  auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
1281  for (MachineInstr &MI : MBB.instrs())
1282  if (MI.isDebugInstr()) {
1283  TII->duplicate(SuccMBB, InsertBefore, MI);
1284  LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "
1285  << MI);
1286  }
1287 }
1288 
1289 // Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
1290 // a basic block is removed we would lose the debug information unless we have
1291 // copied the information to a predecessor/successor.
1292 //
1293 // TODO: This function only handles some simple cases. An alternative would be
1294 // to run a heavier analysis, such as the LiveDebugValues pass, before we do
1295 // branch folding.
1298  assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).");
1299  // If this MBB is the only predecessor of a successor it is legal to copy
1300  // DBG_VALUE instructions to the beginning of the successor.
1301  for (MachineBasicBlock *SuccBB : MBB.successors())
1302  if (SuccBB->pred_size() == 1)
1303  copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
1304  // If this MBB is the only successor of a predecessor it is legal to copy the
1305  // DBG_VALUE instructions to the end of the predecessor (just before the
1306  // terminators, assuming that the terminator isn't affecting the DBG_VALUE).
1307  for (MachineBasicBlock *PredBB : MBB.predecessors())
1308  if (PredBB->succ_size() == 1)
1309  copyDebugInfoToPredecessor(TII, MBB, *PredBB);
1310 
1311  // For AutoFDO, if the block is removed, we won't be able to sample it. To
1312  // avoid assigning a zero weight for BB, move all its pseudo probes into once
1313  // of its predecessors or successors and mark them dangling. This should allow
1314  // the counts inference a chance to get a more reasonable weight for the
1315  // block.
1316  if (!MBB.pred_empty())
1318  else if (!MBB.succ_empty())
1320 }
1321 
1322 bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
1323  bool MadeChange = false;
1324  MachineFunction &MF = *MBB->getParent();
1325 ReoptimizeBlock:
1326 
1327  MachineFunction::iterator FallThrough = MBB->getIterator();
1328  ++FallThrough;
1329 
1330  // Make sure MBB and FallThrough belong to the same EH scope.
1331  bool SameEHScope = true;
1332  if (!EHScopeMembership.empty() && FallThrough != MF.end()) {
1333  auto MBBEHScope = EHScopeMembership.find(MBB);
1334  assert(MBBEHScope != EHScopeMembership.end());
1335  auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1336  assert(FallThroughEHScope != EHScopeMembership.end());
1337  SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1338  }
1339 
1340  // Analyze the branch in the current block. As a side-effect, this may cause
1341  // the block to become empty.
1342  MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
1344  bool CurUnAnalyzable =
1345  TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
1346 
1347  // If this block is empty, make everyone use its fall-through, not the block
1348  // explicitly. Landing pads should not do this since the landing-pad table
1349  // points to this block. Blocks with their addresses taken shouldn't be
1350  // optimized away.
1351  if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
1352  SameEHScope) {
1354  // Dead block? Leave for cleanup later.
1355  if (MBB->pred_empty()) return MadeChange;
1356 
1357  if (FallThrough == MF.end()) {
1358  // TODO: Simplify preds to not branch here if possible!
1359  } else if (FallThrough->isEHPad()) {
1360  // Don't rewrite to a landing pad fallthough. That could lead to the case
1361  // where a BB jumps to more than one landing pad.
1362  // TODO: Is it ever worth rewriting predecessors which don't already
1363  // jump to a landing pad, and so can safely jump to the fallthrough?
1364  } else if (MBB->isSuccessor(&*FallThrough)) {
1365  // Rewrite all predecessors of the old block to go to the fallthrough
1366  // instead.
1367  while (!MBB->pred_empty()) {
1368  MachineBasicBlock *Pred = *(MBB->pred_end()-1);
1369  Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
1370  }
1371  // If MBB was the target of a jump table, update jump tables to go to the
1372  // fallthrough instead.
1373  if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1374  MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
1375  MadeChange = true;
1376  }
1377  return MadeChange;
1378  }
1379 
1380  // Check to see if we can simplify the terminator of the block before this
1381  // one.
1382  MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
1383 
1384  MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
1386  bool PriorUnAnalyzable =
1387  TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
1388  if (!PriorUnAnalyzable) {
1389  // If the previous branch is conditional and both conditions go to the same
1390  // destination, remove the branch, replacing it with an unconditional one or
1391  // a fall-through.
1392  if (PriorTBB && PriorTBB == PriorFBB) {
1393  DebugLoc dl = getBranchDebugLoc(PrevBB);
1394  TII->removeBranch(PrevBB);
1395  PriorCond.clear();
1396  if (PriorTBB != MBB)
1397  TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1398  MadeChange = true;
1399  ++NumBranchOpts;
1400  goto ReoptimizeBlock;
1401  }
1402 
1403  // If the previous block unconditionally falls through to this block and
1404  // this block has no other predecessors, move the contents of this block
1405  // into the prior block. This doesn't usually happen when SimplifyCFG
1406  // has been used, but it can happen if tail merging splits a fall-through
1407  // predecessor of a block.
1408  // This has to check PrevBB->succ_size() because EH edges are ignored by
1409  // analyzeBranch.
1410  if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
1411  PrevBB.succ_size() == 1 &&
1412  !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1413  LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBB
1414  << "From MBB: " << *MBB);
1415  // Remove redundant DBG_VALUEs first.
1416  if (!PrevBB.empty()) {
1417  MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
1418  --PrevBBIter;
1419  MachineBasicBlock::iterator MBBIter = MBB->begin();
1420  // Check if DBG_VALUE at the end of PrevBB is identical to the
1421  // DBG_VALUE at the beginning of MBB.
1422  while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
1423  && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1424  if (!MBBIter->isIdenticalTo(*PrevBBIter))
1425  break;
1426  MachineInstr &DuplicateDbg = *MBBIter;
1427  ++MBBIter; -- PrevBBIter;
1428  DuplicateDbg.eraseFromParent();
1429  }
1430  }
1431  PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1432  PrevBB.removeSuccessor(PrevBB.succ_begin());
1433  assert(PrevBB.succ_empty());
1434  PrevBB.transferSuccessors(MBB);
1435  MadeChange = true;
1436  return MadeChange;
1437  }
1438 
1439  // If the previous branch *only* branches to *this* block (conditional or
1440  // not) remove the branch.
1441  if (PriorTBB == MBB && !PriorFBB) {
1442  TII->removeBranch(PrevBB);
1443  MadeChange = true;
1444  ++NumBranchOpts;
1445  goto ReoptimizeBlock;
1446  }
1447 
1448  // If the prior block branches somewhere else on the condition and here if
1449  // the condition is false, remove the uncond second branch.
1450  if (PriorFBB == MBB) {
1451  DebugLoc dl = getBranchDebugLoc(PrevBB);
1452  TII->removeBranch(PrevBB);
1453  TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1454  MadeChange = true;
1455  ++NumBranchOpts;
1456  goto ReoptimizeBlock;
1457  }
1458 
1459  // If the prior block branches here on true and somewhere else on false, and
1460  // if the branch condition is reversible, reverse the branch to create a
1461  // fall-through.
1462  if (PriorTBB == MBB) {
1463  SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1464  if (!TII->reverseBranchCondition(NewPriorCond)) {
1465  DebugLoc dl = getBranchDebugLoc(PrevBB);
1466  TII->removeBranch(PrevBB);
1467  TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
1468  MadeChange = true;
1469  ++NumBranchOpts;
1470  goto ReoptimizeBlock;
1471  }
1472  }
1473 
1474  // If this block has no successors (e.g. it is a return block or ends with
1475  // a call to a no-return function like abort or __cxa_throw) and if the pred
1476  // falls through into this block, and if it would otherwise fall through
1477  // into the block after this, move this block to the end of the function.
1478  //
1479  // We consider it more likely that execution will stay in the function (e.g.
1480  // due to loops) than it is to exit it. This asserts in loops etc, moving
1481  // the assert condition out of the loop body.
1482  if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
1483  MachineFunction::iterator(PriorTBB) == FallThrough &&
1484  !MBB->canFallThrough()) {
1485  bool DoTransform = true;
1486 
1487  // We have to be careful that the succs of PredBB aren't both no-successor
1488  // blocks. If neither have successors and if PredBB is the second from
1489  // last block in the function, we'd just keep swapping the two blocks for
1490  // last. Only do the swap if one is clearly better to fall through than
1491  // the other.
1492  if (FallThrough == --MF.end() &&
1493  !IsBetterFallthrough(PriorTBB, MBB))
1494  DoTransform = false;
1495 
1496  if (DoTransform) {
1497  // Reverse the branch so we will fall through on the previous true cond.
1498  SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1499  if (!TII->reverseBranchCondition(NewPriorCond)) {
1500  LLVM_DEBUG(dbgs() << "\nMoving MBB: " << *MBB
1501  << "To make fallthrough to: " << *PriorTBB << "\n");
1502 
1503  DebugLoc dl = getBranchDebugLoc(PrevBB);
1504  TII->removeBranch(PrevBB);
1505  TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
1506 
1507  // Move this block to the end of the function.
1508  MBB->moveAfter(&MF.back());
1509  MadeChange = true;
1510  ++NumBranchOpts;
1511  return MadeChange;
1512  }
1513  }
1514  }
1515  }
1516 
1517  bool OptForSize =
1518  MF.getFunction().hasOptSize() ||
1519  llvm::shouldOptimizeForSize(MBB, PSI, &MBBFreqInfo);
1520  if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1 && OptForSize) {
1521  // Changing "Jcc foo; foo: jmp bar;" into "Jcc bar;" might change the branch
1522  // direction, thereby defeating careful block placement and regressing
1523  // performance. Therefore, only consider this for optsize functions.
1525  if (TII->isUnconditionalTailCall(TailCall)) {
1526  MachineBasicBlock *Pred = *MBB->pred_begin();
1527  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1529  bool PredAnalyzable =
1530  !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
1531 
1532  if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&
1533  PredTBB != PredFBB) {
1534  // The predecessor has a conditional branch to this block which consists
1535  // of only a tail call. Try to fold the tail call into the conditional
1536  // branch.
1537  if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
1538  // TODO: It would be nice if analyzeBranch() could provide a pointer
1539  // to the branch instruction so replaceBranchWithTailCall() doesn't
1540  // have to search for it.
1541  TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
1542  ++NumTailCalls;
1543  Pred->removeSuccessor(MBB);
1544  MadeChange = true;
1545  return MadeChange;
1546  }
1547  }
1548  // If the predecessor is falling through to this block, we could reverse
1549  // the branch condition and fold the tail call into that. However, after
1550  // that we might have to re-arrange the CFG to fall through to the other
1551  // block and there is a high risk of regressing code size rather than
1552  // improving it.
1553  }
1554  }
1555 
1556  if (!CurUnAnalyzable) {
1557  // If this is a two-way branch, and the FBB branches to this block, reverse
1558  // the condition so the single-basic-block loop is faster. Instead of:
1559  // Loop: xxx; jcc Out; jmp Loop
1560  // we want:
1561  // Loop: xxx; jncc Loop; jmp Out
1562  if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
1563  SmallVector<MachineOperand, 4> NewCond(CurCond);
1564  if (!TII->reverseBranchCondition(NewCond)) {
1566  TII->removeBranch(*MBB);
1567  TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
1568  MadeChange = true;
1569  ++NumBranchOpts;
1570  goto ReoptimizeBlock;
1571  }
1572  }
1573 
1574  // If this branch is the only thing in its block, see if we can forward
1575  // other blocks across it.
1576  if (CurTBB && CurCond.empty() && !CurFBB &&
1577  IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
1578  !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1580  // This block may contain just an unconditional branch. Because there can
1581  // be 'non-branch terminators' in the block, try removing the branch and
1582  // then seeing if the block is empty.
1583  TII->removeBranch(*MBB);
1584  // If the only things remaining in the block are debug info, remove these
1585  // as well, so this will behave the same as an empty block in non-debug
1586  // mode.
1587  if (IsEmptyBlock(MBB)) {
1588  // Make the block empty, losing the debug info (we could probably
1589  // improve this in some cases.)
1590  MBB->erase(MBB->begin(), MBB->end());
1591  }
1592  // If this block is just an unconditional branch to CurTBB, we can
1593  // usually completely eliminate the block. The only case we cannot
1594  // completely eliminate the block is when the block before this one
1595  // falls through into MBB and we can't understand the prior block's branch
1596  // condition.
1597  if (MBB->empty()) {
1598  bool PredHasNoFallThrough = !PrevBB.canFallThrough();
1599  if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1600  !PrevBB.isSuccessor(MBB)) {
1601  // If the prior block falls through into us, turn it into an
1602  // explicit branch to us to make updates simpler.
1603  if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
1604  PriorTBB != MBB && PriorFBB != MBB) {
1605  if (!PriorTBB) {
1606  assert(PriorCond.empty() && !PriorFBB &&
1607  "Bad branch analysis");
1608  PriorTBB = MBB;
1609  } else {
1610  assert(!PriorFBB && "Machine CFG out of date!");
1611  PriorFBB = MBB;
1612  }
1613  DebugLoc pdl = getBranchDebugLoc(PrevBB);
1614  TII->removeBranch(PrevBB);
1615  TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1616  }
1617 
1618  // Iterate through all the predecessors, revectoring each in-turn.
1619  size_t PI = 0;
1620  bool DidChange = false;
1621  bool HasBranchToSelf = false;
1622  while(PI != MBB->pred_size()) {
1623  MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
1624  if (PMBB == MBB) {
1625  // If this block has an uncond branch to itself, leave it.
1626  ++PI;
1627  HasBranchToSelf = true;
1628  } else {
1629  DidChange = true;
1630  PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
1631  // If this change resulted in PMBB ending in a conditional
1632  // branch where both conditions go to the same destination,
1633  // change this to an unconditional branch.
1634  MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
1635  SmallVector<MachineOperand, 4> NewCurCond;
1636  bool NewCurUnAnalyzable = TII->analyzeBranch(
1637  *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);
1638  if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1639  DebugLoc pdl = getBranchDebugLoc(*PMBB);
1640  TII->removeBranch(*PMBB);
1641  NewCurCond.clear();
1642  TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
1643  MadeChange = true;
1644  ++NumBranchOpts;
1645  }
1646  }
1647  }
1648 
1649  // Change any jumptables to go to the new MBB.
1650  if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1651  MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
1652  if (DidChange) {
1653  ++NumBranchOpts;
1654  MadeChange = true;
1655  if (!HasBranchToSelf) return MadeChange;
1656  }
1657  }
1658  }
1659 
1660  // Add the branch back if the block is more than just an uncond branch.
1661  TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
1662  }
1663  }
1664 
1665  // If the prior block doesn't fall through into this block, and if this
1666  // block doesn't fall through into some other block, see if we can find a
1667  // place to move this block where a fall-through will happen.
1668  if (!PrevBB.canFallThrough()) {
1669  // Now we know that there was no fall-through into this block, check to
1670  // see if it has a fall-through into its successor.
1671  bool CurFallsThru = MBB->canFallThrough();
1672 
1673  if (!MBB->isEHPad()) {
1674  // Check all the predecessors of this block. If one of them has no fall
1675  // throughs, and analyzeBranch thinks it _could_ fallthrough to this
1676  // block, move this block right after it.
1677  for (MachineBasicBlock *PredBB : MBB->predecessors()) {
1678  // Analyze the branch at the end of the pred.
1679  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1681  if (PredBB != MBB && !PredBB->canFallThrough() &&
1682  !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&
1683  (PredTBB == MBB || PredFBB == MBB) &&
1684  (!CurFallsThru || !CurTBB || !CurFBB) &&
1685  (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1686  // If the current block doesn't fall through, just move it.
1687  // If the current block can fall through and does not end with a
1688  // conditional branch, we need to append an unconditional jump to
1689  // the (current) next block. To avoid a possible compile-time
1690  // infinite loop, move blocks only backward in this case.
1691  // Also, if there are already 2 branches here, we cannot add a third;
1692  // this means we have the case
1693  // Bcc next
1694  // B elsewhere
1695  // next:
1696  if (CurFallsThru) {
1697  MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
1698  CurCond.clear();
1699  TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
1700  }
1701  MBB->moveAfter(PredBB);
1702  MadeChange = true;
1703  goto ReoptimizeBlock;
1704  }
1705  }
1706  }
1707 
1708  if (!CurFallsThru) {
1709  // Check analyzable branch-successors to see if we can move this block
1710  // before one.
1711  if (!CurUnAnalyzable) {
1712  for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {
1713  if (!SuccBB)
1714  continue;
1715  // Analyze the branch at the end of the block before the succ.
1716  MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
1717 
1718  // If this block doesn't already fall-through to that successor, and
1719  // if the succ doesn't already have a block that can fall through into
1720  // it, we can arrange for the fallthrough to happen.
1721  if (SuccBB != MBB && &*SuccPrev != MBB &&
1722  !SuccPrev->canFallThrough()) {
1723  MBB->moveBefore(SuccBB);
1724  MadeChange = true;
1725  goto ReoptimizeBlock;
1726  }
1727  }
1728  }
1729 
1730  // Okay, there is no really great place to put this block. If, however,
1731  // the block before this one would be a fall-through if this block were
1732  // removed, move this block to the end of the function. There is no real
1733  // advantage in "falling through" to an EH block, so we don't want to
1734  // perform this transformation for that case.
1735  //
1736  // Also, Windows EH introduced the possibility of an arbitrary number of
1737  // successors to a given block. The analyzeBranch call does not consider
1738  // exception handling and so we can get in a state where a block
1739  // containing a call is followed by multiple EH blocks that would be
1740  // rotated infinitely at the end of the function if the transformation
1741  // below were performed for EH "FallThrough" blocks. Therefore, even if
1742  // that appears not to be happening anymore, we should assume that it is
1743  // possible and not remove the "!FallThrough()->isEHPad" condition below.
1744  MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
1746  if (FallThrough != MF.end() &&
1747  !FallThrough->isEHPad() &&
1748  !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1749  PrevBB.isSuccessor(&*FallThrough)) {
1750  MBB->moveAfter(&MF.back());
1751  MadeChange = true;
1752  return MadeChange;
1753  }
1754  }
1755  }
1756 
1757  return MadeChange;
1758 }
1759 
1760 //===----------------------------------------------------------------------===//
1761 // Hoist Common Code
1762 //===----------------------------------------------------------------------===//
1763 
1764 bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
1765  bool MadeChange = false;
1766  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ) {
1767  MachineBasicBlock *MBB = &*I++;
1768  MadeChange |= HoistCommonCodeInSuccs(MBB);
1769  }
1770 
1771  return MadeChange;
1772 }
1773 
1774 /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
1775 /// its 'true' successor.
1777  MachineBasicBlock *TrueBB) {
1778  for (MachineBasicBlock *SuccBB : BB->successors())
1779  if (SuccBB != TrueBB)
1780  return SuccBB;
1781  return nullptr;
1782 }
1783 
1784 template <class Container>
1786  Container &Set) {
1787  if (Reg.isPhysical()) {
1788  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
1789  Set.insert(*AI);
1790  } else {
1791  Set.insert(Reg);
1792  }
1793 }
1794 
1795 /// findHoistingInsertPosAndDeps - Find the location to move common instructions
1796 /// in successors to. The location is usually just before the terminator,
1797 /// however if the terminator is a conditional branch and its previous
1798 /// instruction is the flag setting instruction, the previous instruction is
1799 /// the preferred location. This function also gathers uses and defs of the
1800 /// instructions from the insertion point to the end of the block. The data is
1801 /// used by HoistCommonCodeInSuccs to ensure safety.
1802 static
1804  const TargetInstrInfo *TII,
1805  const TargetRegisterInfo *TRI,
1807  SmallSet<Register, 4> &Defs) {
1809  if (!TII->isUnpredicatedTerminator(*Loc))
1810  return MBB->end();
1811 
1812  for (const MachineOperand &MO : Loc->operands()) {
1813  if (!MO.isReg())
1814  continue;
1815  Register Reg = MO.getReg();
1816  if (!Reg)
1817  continue;
1818  if (MO.isUse()) {
1820  } else {
1821  if (!MO.isDead())
1822  // Don't try to hoist code in the rare case the terminator defines a
1823  // register that is later used.
1824  return MBB->end();
1825 
1826  // If the terminator defines a register, make sure we don't hoist
1827  // the instruction whose def might be clobbered by the terminator.
1828  addRegAndItsAliases(Reg, TRI, Defs);
1829  }
1830  }
1831 
1832  if (Uses.empty())
1833  return Loc;
1834  // If the terminator is the only instruction in the block and Uses is not
1835  // empty (or we would have returned above), we can still safely hoist
1836  // instructions just before the terminator as long as the Defs/Uses are not
1837  // violated (which is checked in HoistCommonCodeInSuccs).
1838  if (Loc == MBB->begin())
1839  return Loc;
1840 
1841  // The terminator is probably a conditional branch, try not to separate the
1842  // branch from condition setting instruction.
1844 
1845  bool IsDef = false;
1846  for (const MachineOperand &MO : PI->operands()) {
1847  // If PI has a regmask operand, it is probably a call. Separate away.
1848  if (MO.isRegMask())
1849  return Loc;
1850  if (!MO.isReg() || MO.isUse())
1851  continue;
1852  Register Reg = MO.getReg();
1853  if (!Reg)
1854  continue;
1855  if (Uses.count(Reg)) {
1856  IsDef = true;
1857  break;
1858  }
1859  }
1860  if (!IsDef)
1861  // The condition setting instruction is not just before the conditional
1862  // branch.
1863  return Loc;
1864 
1865  // Be conservative, don't insert instruction above something that may have
1866  // side-effects. And since it's potentially bad to separate flag setting
1867  // instruction from the conditional branch, just abort the optimization
1868  // completely.
1869  // Also avoid moving code above predicated instruction since it's hard to
1870  // reason about register liveness with predicated instruction.
1871  bool DontMoveAcrossStore = true;
1872  if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
1873  return MBB->end();
1874 
1875  // Find out what registers are live. Note this routine is ignoring other live
1876  // registers which are only used by instructions in successor blocks.
1877  for (const MachineOperand &MO : PI->operands()) {
1878  if (!MO.isReg())
1879  continue;
1880  Register Reg = MO.getReg();
1881  if (!Reg)
1882  continue;
1883  if (MO.isUse()) {
1885  } else {
1886  if (Uses.erase(Reg)) {
1888  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1889  Uses.erase(*SubRegs); // Use sub-registers to be conservative
1890  }
1891  }
1892  addRegAndItsAliases(Reg, TRI, Defs);
1893  }
1894  }
1895 
1896  return PI;
1897 }
1898 
1899 bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
1900  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1902  if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
1903  return false;
1904 
1905  if (!FBB) FBB = findFalseBlock(MBB, TBB);
1906  if (!FBB)
1907  // Malformed bcc? True and false blocks are the same?
1908  return false;
1909 
1910  // Restrict the optimization to cases where MBB is the only predecessor,
1911  // it is an obvious win.
1912  if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
1913  return false;
1914 
1915  // Find a suitable position to hoist the common instructions to. Also figure
1916  // out which registers are used or defined by instructions from the insertion
1917  // point to the end of the block.
1920  findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
1921  if (Loc == MBB->end())
1922  return false;
1923 
1924  bool HasDups = false;
1925  SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;
1926  MachineBasicBlock::iterator TIB = TBB->begin();
1927  MachineBasicBlock::iterator FIB = FBB->begin();
1928  MachineBasicBlock::iterator TIE = TBB->end();
1929  MachineBasicBlock::iterator FIE = FBB->end();
1930  while (TIB != TIE && FIB != FIE) {
1931  // Skip dbg_value instructions. These do not count.
1932  TIB = skipDebugInstructionsForward(TIB, TIE);
1933  FIB = skipDebugInstructionsForward(FIB, FIE);
1934  if (TIB == TIE || FIB == FIE)
1935  break;
1936 
1937  if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
1938  break;
1939 
1940  if (TII->isPredicated(*TIB))
1941  // Hard to reason about register liveness with predicated instruction.
1942  break;
1943 
1944  bool IsSafe = true;
1945  for (MachineOperand &MO : TIB->operands()) {
1946  // Don't attempt to hoist instructions with register masks.
1947  if (MO.isRegMask()) {
1948  IsSafe = false;
1949  break;
1950  }
1951  if (!MO.isReg())
1952  continue;
1953  Register Reg = MO.getReg();
1954  if (!Reg)
1955  continue;
1956  if (MO.isDef()) {
1957  if (Uses.count(Reg)) {
1958  // Avoid clobbering a register that's used by the instruction at
1959  // the point of insertion.
1960  IsSafe = false;
1961  break;
1962  }
1963 
1964  if (Defs.count(Reg) && !MO.isDead()) {
1965  // Don't hoist the instruction if the def would be clobber by the
1966  // instruction at the point insertion. FIXME: This is overly
1967  // conservative. It should be possible to hoist the instructions
1968  // in BB2 in the following example:
1969  // BB1:
1970  // r1, eflag = op1 r2, r3
1971  // brcc eflag
1972  //
1973  // BB2:
1974  // r1 = op2, ...
1975  // = op3, killed r1
1976  IsSafe = false;
1977  break;
1978  }
1979  } else if (!ActiveDefsSet.count(Reg)) {
1980  if (Defs.count(Reg)) {
1981  // Use is defined by the instruction at the point of insertion.
1982  IsSafe = false;
1983  break;
1984  }
1985 
1986  if (MO.isKill() && Uses.count(Reg))
1987  // Kills a register that's read by the instruction at the point of
1988  // insertion. Remove the kill marker.
1989  MO.setIsKill(false);
1990  }
1991  }
1992  if (!IsSafe)
1993  break;
1994 
1995  bool DontMoveAcrossStore = true;
1996  if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
1997  break;
1998 
1999  // Remove kills from ActiveDefsSet, these registers had short live ranges.
2000  for (const MachineOperand &MO : TIB->operands()) {
2001  if (!MO.isReg() || !MO.isUse() || !MO.isKill())
2002  continue;
2003  Register Reg = MO.getReg();
2004  if (!Reg)
2005  continue;
2006  if (!AllDefsSet.count(Reg)) {
2007  continue;
2008  }
2009  if (Reg.isPhysical()) {
2010  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
2011  ActiveDefsSet.erase(*AI);
2012  } else {
2013  ActiveDefsSet.erase(Reg);
2014  }
2015  }
2016 
2017  // Track local defs so we can update liveins.
2018  for (const MachineOperand &MO : TIB->operands()) {
2019  if (!MO.isReg() || !MO.isDef() || MO.isDead())
2020  continue;
2021  Register Reg = MO.getReg();
2022  if (!Reg || Reg.isVirtual())
2023  continue;
2024  addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
2025  addRegAndItsAliases(Reg, TRI, AllDefsSet);
2026  }
2027 
2028  HasDups = true;
2029  ++TIB;
2030  ++FIB;
2031  }
2032 
2033  if (!HasDups)
2034  return false;
2035 
2036  MBB->splice(Loc, TBB, TBB->begin(), TIB);
2037  FBB->erase(FBB->begin(), FIB);
2038 
2039  if (UpdateLiveIns) {
2040  recomputeLiveIns(*TBB);
2041  recomputeLiveIns(*FBB);
2042  }
2043 
2044  ++NumHoist;
2045  return true;
2046 }
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:908
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:1803
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:1404
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:1235
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:100
MachineInstr.h
llvm::MachineOperand::MO_Immediate
@ MO_Immediate
Immediate operand.
Definition: MachineOperand.h:53
llvm
Definition: AllocatorList.h:23
copyDebugInfoToSuccessor
static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &SuccMBB)
Definition: BranchFolding.cpp:1277
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:242
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:850
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:124
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:1437
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:93
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:1362
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:622
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:1131
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:739
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
ErrorHandling.h
llvm::recomputeLiveIns
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for MBB.
Definition: LivePhysRegs.h:192
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:1474
MachineSizeOpts.h
llvm::MachineFunction::back
const MachineBasicBlock & back() const
Definition: MachineFunction.h:751
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:140
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:231
llvm::prev_nodbg
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=false)
Decrement It, then continue decrementing it while it points to a debug instruction.
Definition: MachineBasicBlock.h:1146
BlockFrequency.h
llvm::MachineBasicBlock::moveBefore
void moveBefore(MachineBasicBlock *NewAfter)
Move 'this' block before or after the specified block.
Definition: MachineBasicBlock.cpp:630
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:756
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:52
llvm::MachineBasicBlock::getFirstNonDebugInstr
iterator getFirstNonDebugInstr(bool SkipPseudoOp=false)
Returns an iterator to the first non-debug instruction in the basic block, or end().
Definition: MachineBasicBlock.cpp:258
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:1265
IsEmptyBlock
static bool IsEmptyBlock(MachineBasicBlock *MBB)
Definition: BranchFolding.cpp:1219
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:253
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:28
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:122
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:583
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:1322
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:683
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:132
llvm::MachineBasicBlock::addSuccessor
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:743
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:565
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:665
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:931
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:737
FlagEnableTailMerge
static cl::opt< cl::boolOrDefault > FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
llvm::MachineBasicBlock::moveAndDanglePseudoProbes
void moveAndDanglePseudoProbes(MachineBasicBlock *ToMBB)
move all pseudo probes in this block to the end of /c ToMBB To and tag them dangling.
Definition: MachineBasicBlock.cpp:911
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:1394
llvm::computeAndAddLiveIns
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
Definition: LivePhysRegs.cpp:335
DebugLoc.h
llvm::BitVector
Definition: BitVector.h:74
BranchFolding.h
llvm::MBFIWrapper
Definition: MBFIWrapper.h:25
getBranchDebugLoc
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB)
getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.
Definition: BranchFolding.cpp:1258
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:1431
llvm::cl::opt
Definition: CommandLine.h:1419
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:392
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:622
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:318
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:1414
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:209
llvm::skipDebugInstructionsForward
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=false)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Definition: MachineBasicBlock.h:1115
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:19
Analysis.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
MCRegisterInfo.h
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:188
addRegAndItsAliases
static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI, Container &Set)
Definition: BranchFolding.cpp:1785
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:414
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:984
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:1296
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:771
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:56
llvm::BranchFolder::OptimizeFunction
bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, const TargetRegisterInfo *tri, MachineLoopInfo *mli=nullptr, bool AfterPlacement=false)
Perhaps branch folding, tail merging and other CFG optimizations on the given function.
Definition: BranchFolding.cpp:178
llvm::MachineInstr::isReturn
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:802
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:227
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:772
llvm::MachineBasicBlock::moveAfter
void moveAfter(MachineBasicBlock *NewBefore)
Definition: MachineBasicBlock.cpp:634
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:239
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:965
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:167
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:435
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:859
llvm::LivePhysRegs::init
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:66
llvm::MachineBasicBlock::getLastNonDebugInstr
iterator getLastNonDebugInstr(bool SkipPseudoOp=false)
Returns an iterator to the last non-debug instruction in the basic block, or end().
Definition: MachineBasicBlock.cpp:264
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:1435
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:508
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:862
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:706
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:1426
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:521
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:781
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:314
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:612
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:935
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:622
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:329
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:176
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:1619
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:1225
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:578
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::getEHScopeMembership
DenseMap< const MachineBasicBlock *, int > getEHScopeMembership(const MachineFunction &MF)
Definition: Analysis.cpp:739
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:411
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:1776
MachineFunction.h
llvm::MachineFunction::eraseCallSiteInfo
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
Definition: MachineFunction.cpp:899
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:827
InitializePasses.h
llvm::MBFIWrapper::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
Definition: MBFIWrapper.cpp:19
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:83
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:38
llvm::MachineOperand::MO_ConstantPoolIndex
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
Definition: MachineOperand.h:58