LLVM  7.0.0svn
TailDuplicator.cpp
Go to the documentation of this file.
1 //===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This utility class duplicates basic blocks ending in unconditional branches
11 // into the tails of their predecessors.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
34 #include "llvm/IR/DebugLoc.h"
35 #include "llvm/IR/Function.h"
37 #include "llvm/Support/Debug.h"
40 #include <algorithm>
41 #include <cassert>
42 #include <iterator>
43 #include <utility>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "tailduplication"
48 
49 STATISTIC(NumTails, "Number of tails duplicated");
50 STATISTIC(NumTailDups, "Number of tail duplicated blocks");
51 STATISTIC(NumTailDupAdded,
52  "Number of instructions added due to tail duplication");
53 STATISTIC(NumTailDupRemoved,
54  "Number of instructions removed due to tail duplication");
55 STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
56 STATISTIC(NumAddedPHIs, "Number of phis added");
57 
58 // Heuristic for tail duplication.
60  "tail-dup-size",
61  cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2),
62  cl::Hidden);
63 
65  "tail-dup-indirect-size",
66  cl::desc("Maximum instructions to consider tail duplicating blocks that "
67  "end with indirect branches."), cl::init(20),
68  cl::Hidden);
69 
70 static cl::opt<bool>
71  TailDupVerify("tail-dup-verify",
72  cl::desc("Verify sanity of PHI instructions during taildup"),
73  cl::init(false), cl::Hidden);
74 
75 static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
76  cl::Hidden);
77 
78 void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc,
79  const MachineBranchProbabilityInfo *MBPIin,
80  bool LayoutModeIn, unsigned TailDupSizeIn) {
81  MF = &MFin;
82  TII = MF->getSubtarget().getInstrInfo();
83  TRI = MF->getSubtarget().getRegisterInfo();
84  MRI = &MF->getRegInfo();
85  MMI = &MF->getMMI();
86  MBPI = MBPIin;
87  TailDupSize = TailDupSizeIn;
88 
89  assert(MBPI != nullptr && "Machine Branch Probability Info required");
90 
91  LayoutMode = LayoutModeIn;
92  this->PreRegAlloc = PreRegAlloc;
93 }
94 
95 static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
96  for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {
97  MachineBasicBlock *MBB = &*I;
99  MBB->pred_end());
101  while (MI != MBB->end()) {
102  if (!MI->isPHI())
103  break;
104  for (MachineBasicBlock *PredBB : Preds) {
105  bool Found = false;
106  for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
107  MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
108  if (PHIBB == PredBB) {
109  Found = true;
110  break;
111  }
112  }
113  if (!Found) {
114  dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
115  << *MI;
116  dbgs() << " missing input from predecessor "
117  << printMBBReference(*PredBB) << '\n';
118  llvm_unreachable(nullptr);
119  }
120  }
121 
122  for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
123  MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
124  if (CheckExtra && !Preds.count(PHIBB)) {
125  dbgs() << "Warning: malformed PHI in " << printMBBReference(*MBB)
126  << ": " << *MI;
127  dbgs() << " extra input from predecessor "
128  << printMBBReference(*PHIBB) << '\n';
129  llvm_unreachable(nullptr);
130  }
131  if (PHIBB->getNumber() < 0) {
132  dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
133  << *MI;
134  dbgs() << " non-existing " << printMBBReference(*PHIBB) << '\n';
135  llvm_unreachable(nullptr);
136  }
137  }
138  ++MI;
139  }
140  }
141 }
142 
143 /// Tail duplicate the block and cleanup.
144 /// \p IsSimple - return value of isSimpleBB
145 /// \p MBB - block to be duplicated
146 /// \p ForcedLayoutPred - If non-null, treat this block as the layout
147 /// predecessor, instead of using the ordering in MF
148 /// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of
149 /// all Preds that received a copy of \p MBB.
150 /// \p RemovalCallback - if non-null, called just before MBB is deleted.
152  bool IsSimple, MachineBasicBlock *MBB,
153  MachineBasicBlock *ForcedLayoutPred,
154  SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds,
155  function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
156  // Save the successors list.
158  MBB->succ_end());
159 
162  if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred, TDBBs, Copies))
163  return false;
164 
165  ++NumTails;
166 
168  MachineSSAUpdater SSAUpdate(*MF, &NewPHIs);
169 
170  // TailBB's immediate successors are now successors of those predecessors
171  // which duplicated TailBB. Add the predecessors as sources to the PHI
172  // instructions.
173  bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken();
174  if (PreRegAlloc)
175  updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);
176 
177  // If it is dead, remove it.
178  if (isDead) {
179  NumTailDupRemoved += MBB->size();
180  removeDeadBlock(MBB, RemovalCallback);
181  ++NumDeadBlocks;
182  }
183 
184  // Update SSA form.
185  if (!SSAUpdateVRs.empty()) {
186  for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {
187  unsigned VReg = SSAUpdateVRs[i];
188  SSAUpdate.Initialize(VReg);
189 
190  // If the original definition is still around, add it as an available
191  // value.
192  MachineInstr *DefMI = MRI->getVRegDef(VReg);
193  MachineBasicBlock *DefBB = nullptr;
194  if (DefMI) {
195  DefBB = DefMI->getParent();
196  SSAUpdate.AddAvailableValue(DefBB, VReg);
197  }
198 
199  // Add the new vregs as available values.
201  SSAUpdateVals.find(VReg);
202  for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
203  MachineBasicBlock *SrcBB = LI->second[j].first;
204  unsigned SrcReg = LI->second[j].second;
205  SSAUpdate.AddAvailableValue(SrcBB, SrcReg);
206  }
207 
208  // Rewrite uses that are outside of the original def's block.
210  while (UI != MRI->use_end()) {
211  MachineOperand &UseMO = *UI;
212  MachineInstr *UseMI = UseMO.getParent();
213  ++UI;
214  if (UseMI->isDebugValue()) {
215  // SSAUpdate can replace the use with an undef. That creates
216  // a debug instruction that is a kill.
217  // FIXME: Should it SSAUpdate job to delete debug instructions
218  // instead of replacing the use with undef?
219  UseMI->eraseFromParent();
220  continue;
221  }
222  if (UseMI->getParent() == DefBB && !UseMI->isPHI())
223  continue;
224  SSAUpdate.RewriteUse(UseMO);
225  }
226  }
227 
228  SSAUpdateVRs.clear();
229  SSAUpdateVals.clear();
230  }
231 
232  // Eliminate some of the copies inserted by tail duplication to maintain
233  // SSA form.
234  for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
235  MachineInstr *Copy = Copies[i];
236  if (!Copy->isCopy())
237  continue;
238  unsigned Dst = Copy->getOperand(0).getReg();
239  unsigned Src = Copy->getOperand(1).getReg();
240  if (MRI->hasOneNonDBGUse(Src) &&
241  MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) {
242  // Copy is the only use. Do trivial copy propagation here.
243  MRI->replaceRegWith(Dst, Src);
244  Copy->eraseFromParent();
245  }
246  }
247 
248  if (NewPHIs.size())
249  NumAddedPHIs += NewPHIs.size();
250 
251  if (DuplicatedPreds)
252  *DuplicatedPreds = std::move(TDBBs);
253 
254  return true;
255 }
256 
257 /// Look for small blocks that are unconditionally branched to and do not fall
258 /// through. Tail-duplicate their instructions into their predecessors to
259 /// eliminate (dynamic) branches.
261  bool MadeChange = false;
262 
263  if (PreRegAlloc && TailDupVerify) {
264  DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
265  VerifyPHIs(*MF, true);
266  }
267 
268  for (MachineFunction::iterator I = ++MF->begin(), E = MF->end(); I != E;) {
269  MachineBasicBlock *MBB = &*I++;
270 
271  if (NumTails == TailDupLimit)
272  break;
273 
274  bool IsSimple = isSimpleBB(MBB);
275 
276  if (!shouldTailDuplicate(IsSimple, *MBB))
277  continue;
278 
279  MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB, nullptr);
280  }
281 
282  if (PreRegAlloc && TailDupVerify)
283  VerifyPHIs(*MF, false);
284 
285  return MadeChange;
286 }
287 
288 static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,
289  const MachineRegisterInfo *MRI) {
290  for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
291  if (UseMI.isDebugValue())
292  continue;
293  if (UseMI.getParent() != BB)
294  return true;
295  }
296  return false;
297 }
298 
300  for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)
301  if (MI->getOperand(i + 1).getMBB() == SrcBB)
302  return i;
303  return 0;
304 }
305 
306 // Remember which registers are used by phis in this block. This is
307 // used to determine which registers are liveout while modifying the
308 // block (which is why we need to copy the information).
309 static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
310  DenseSet<unsigned> *UsedByPhi) {
311  for (const auto &MI : BB) {
312  if (!MI.isPHI())
313  break;
314  for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
315  unsigned SrcReg = MI.getOperand(i).getReg();
316  UsedByPhi->insert(SrcReg);
317  }
318  }
319 }
320 
321 /// Add a definition and source virtual registers pair for SSA update.
322 void TailDuplicator::addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
323  MachineBasicBlock *BB) {
325  SSAUpdateVals.find(OrigReg);
326  if (LI != SSAUpdateVals.end())
327  LI->second.push_back(std::make_pair(BB, NewReg));
328  else {
329  AvailableValsTy Vals;
330  Vals.push_back(std::make_pair(BB, NewReg));
331  SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));
332  SSAUpdateVRs.push_back(OrigReg);
333  }
334 }
335 
336 /// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the
337 /// source register that's contributed by PredBB and update SSA update map.
338 void TailDuplicator::processPHI(
341  SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
342  const DenseSet<unsigned> &RegsUsedByPhi, bool Remove) {
343  unsigned DefReg = MI->getOperand(0).getReg();
344  unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);
345  assert(SrcOpIdx && "Unable to find matching PHI source?");
346  unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg();
347  unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg();
348  const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
349  LocalVRMap.insert(std::make_pair(DefReg, RegSubRegPair(SrcReg, SrcSubReg)));
350 
351  // Insert a copy from source to the end of the block. The def register is the
352  // available value liveout of the block.
353  unsigned NewDef = MRI->createVirtualRegister(RC);
354  Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg)));
355  if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg))
356  addSSAUpdateEntry(DefReg, NewDef, PredBB);
357 
358  if (!Remove)
359  return;
360 
361  // Remove PredBB from the PHI node.
362  MI->RemoveOperand(SrcOpIdx + 1);
363  MI->RemoveOperand(SrcOpIdx);
364  if (MI->getNumOperands() == 1)
365  MI->eraseFromParent();
366 }
367 
368 /// Duplicate a TailBB instruction to PredBB and update
369 /// the source operands due to earlier PHI translation.
370 void TailDuplicator::duplicateInstruction(
371  MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
373  const DenseSet<unsigned> &UsedByPhi) {
374  MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI);
375  if (PreRegAlloc) {
376  for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) {
377  MachineOperand &MO = NewMI.getOperand(i);
378  if (!MO.isReg())
379  continue;
380  unsigned Reg = MO.getReg();
382  continue;
383  if (MO.isDef()) {
384  const TargetRegisterClass *RC = MRI->getRegClass(Reg);
385  unsigned NewReg = MRI->createVirtualRegister(RC);
386  MO.setReg(NewReg);
387  LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
388  if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg))
389  addSSAUpdateEntry(Reg, NewReg, PredBB);
390  } else {
391  auto VI = LocalVRMap.find(Reg);
392  if (VI != LocalVRMap.end()) {
393  // Need to make sure that the register class of the mapped register
394  // will satisfy the constraints of the class of the register being
395  // replaced.
396  auto *OrigRC = MRI->getRegClass(Reg);
397  auto *MappedRC = MRI->getRegClass(VI->second.Reg);
398  const TargetRegisterClass *ConstrRC;
399  if (VI->second.SubReg != 0) {
400  ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC,
401  VI->second.SubReg);
402  if (ConstrRC) {
403  // The actual constraining (as in "find appropriate new class")
404  // is done by getMatchingSuperRegClass, so now we only need to
405  // change the class of the mapped register.
406  MRI->setRegClass(VI->second.Reg, ConstrRC);
407  }
408  } else {
409  // For mapped registers that do not have sub-registers, simply
410  // restrict their class to match the original one.
411  ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC);
412  }
413 
414  if (ConstrRC) {
415  // If the class constraining succeeded, we can simply replace
416  // the old register with the mapped one.
417  MO.setReg(VI->second.Reg);
418  // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a
419  // sub-register, we need to compose the sub-register indices.
421  VI->second.SubReg));
422  } else {
423  // The direct replacement is not possible, due to failing register
424  // class constraints. An explicit COPY is necessary. Create one
425  // that can be reused
426  auto *NewRC = MI->getRegClassConstraint(i, TII, TRI);
427  if (NewRC == nullptr)
428  NewRC = OrigRC;
429  unsigned NewReg = MRI->createVirtualRegister(NewRC);
430  BuildMI(*PredBB, MI, MI->getDebugLoc(),
431  TII->get(TargetOpcode::COPY), NewReg)
432  .addReg(VI->second.Reg, 0, VI->second.SubReg);
433  LocalVRMap.erase(VI);
434  LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
435  MO.setReg(NewReg);
436  // The composed VI.Reg:VI.SubReg is replaced with NewReg, which
437  // is equivalent to the whole register Reg. Hence, Reg:subreg
438  // is same as NewReg:subreg, so keep the sub-register index
439  // unchanged.
440  }
441  // Clear any kill flags from this operand. The new register could
442  // have uses after this one, so kills are not valid here.
443  MO.setIsKill(false);
444  }
445  }
446  }
447  }
448 }
449 
450 /// After FromBB is tail duplicated into its predecessor blocks, the successors
451 /// have gained new predecessors. Update the PHI instructions in them
452 /// accordingly.
453 void TailDuplicator::updateSuccessorsPHIs(
454  MachineBasicBlock *FromBB, bool isDead,
457  for (MachineBasicBlock *SuccBB : Succs) {
458  for (MachineInstr &MI : *SuccBB) {
459  if (!MI.isPHI())
460  break;
461  MachineInstrBuilder MIB(*FromBB->getParent(), MI);
462  unsigned Idx = 0;
463  for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
464  MachineOperand &MO = MI.getOperand(i + 1);
465  if (MO.getMBB() == FromBB) {
466  Idx = i;
467  break;
468  }
469  }
470 
471  assert(Idx != 0);
472  MachineOperand &MO0 = MI.getOperand(Idx);
473  unsigned Reg = MO0.getReg();
474  if (isDead) {
475  // Folded into the previous BB.
476  // There could be duplicate phi source entries. FIXME: Should sdisel
477  // or earlier pass fixed this?
478  for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) {
479  MachineOperand &MO = MI.getOperand(i + 1);
480  if (MO.getMBB() == FromBB) {
481  MI.RemoveOperand(i + 1);
482  MI.RemoveOperand(i);
483  }
484  }
485  } else
486  Idx = 0;
487 
488  // If Idx is set, the operands at Idx and Idx+1 must be removed.
489  // We reuse the location to avoid expensive RemoveOperand calls.
490 
492  SSAUpdateVals.find(Reg);
493  if (LI != SSAUpdateVals.end()) {
494  // This register is defined in the tail block.
495  for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
496  MachineBasicBlock *SrcBB = LI->second[j].first;
497  // If we didn't duplicate a bb into a particular predecessor, we
498  // might still have added an entry to SSAUpdateVals to correcly
499  // recompute SSA. If that case, avoid adding a dummy extra argument
500  // this PHI.
501  if (!SrcBB->isSuccessor(SuccBB))
502  continue;
503 
504  unsigned SrcReg = LI->second[j].second;
505  if (Idx != 0) {
506  MI.getOperand(Idx).setReg(SrcReg);
507  MI.getOperand(Idx + 1).setMBB(SrcBB);
508  Idx = 0;
509  } else {
510  MIB.addReg(SrcReg).addMBB(SrcBB);
511  }
512  }
513  } else {
514  // Live in tail block, must also be live in predecessors.
515  for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) {
516  MachineBasicBlock *SrcBB = TDBBs[j];
517  if (Idx != 0) {
518  MI.getOperand(Idx).setReg(Reg);
519  MI.getOperand(Idx + 1).setMBB(SrcBB);
520  Idx = 0;
521  } else {
522  MIB.addReg(Reg).addMBB(SrcBB);
523  }
524  }
525  }
526  if (Idx != 0) {
527  MI.RemoveOperand(Idx + 1);
528  MI.RemoveOperand(Idx);
529  }
530  }
531  }
532 }
533 
534 /// Determine if it is profitable to duplicate this block.
536  MachineBasicBlock &TailBB) {
537  // When doing tail-duplication during layout, the block ordering is in flux,
538  // so canFallThrough returns a result based on incorrect information and
539  // should just be ignored.
540  if (!LayoutMode && TailBB.canFallThrough())
541  return false;
542 
543  // Don't try to tail-duplicate single-block loops.
544  if (TailBB.isSuccessor(&TailBB))
545  return false;
546 
547  // Set the limit on the cost to duplicate. When optimizing for size,
548  // duplicate only one, because one branch instruction can be eliminated to
549  // compensate for the duplication.
550  unsigned MaxDuplicateCount;
551  if (TailDupSize == 0 &&
552  TailDuplicateSize.getNumOccurrences() == 0 &&
553  MF->getFunction().optForSize())
554  MaxDuplicateCount = 1;
555  else if (TailDupSize == 0)
556  MaxDuplicateCount = TailDuplicateSize;
557  else
558  MaxDuplicateCount = TailDupSize;
559 
560  // If the block to be duplicated ends in an unanalyzable fallthrough, don't
561  // duplicate it.
562  // A similar check is necessary in MachineBlockPlacement to make sure pairs of
563  // blocks with unanalyzable fallthrough get layed out contiguously.
564  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
566  if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&
567  TailBB.canFallThrough())
568  return false;
569 
570  // If the target has hardware branch prediction that can handle indirect
571  // branches, duplicating them can often make them predictable when there
572  // are common paths through the code. The limit needs to be high enough
573  // to allow undoing the effects of tail merging and other optimizations
574  // that rearrange the predecessors of the indirect branch.
575 
576  bool HasIndirectbr = false;
577  if (!TailBB.empty())
578  HasIndirectbr = TailBB.back().isIndirectBranch();
579 
580  if (HasIndirectbr && PreRegAlloc)
581  MaxDuplicateCount = TailDupIndirectBranchSize;
582 
583  // Check the instructions in the block to determine whether tail-duplication
584  // is invalid or unlikely to be profitable.
585  unsigned InstrCount = 0;
586  for (MachineInstr &MI : TailBB) {
587  // Non-duplicable things shouldn't be tail-duplicated.
588  if (MI.isNotDuplicable())
589  return false;
590 
591  // Convergent instructions can be duplicated only if doing so doesn't add
592  // new control dependencies, which is what we're going to do here.
593  if (MI.isConvergent())
594  return false;
595 
596  // Do not duplicate 'return' instructions if this is a pre-regalloc run.
597  // A return may expand into a lot more instructions (e.g. reload of callee
598  // saved registers) after PEI.
599  if (PreRegAlloc && MI.isReturn())
600  return false;
601 
602  // Avoid duplicating calls before register allocation. Calls presents a
603  // barrier to register allocation so duplicating them may end up increasing
604  // spills.
605  if (PreRegAlloc && MI.isCall())
606  return false;
607 
608  if (!MI.isPHI() && !MI.isDebugValue())
609  InstrCount += 1;
610 
611  if (InstrCount > MaxDuplicateCount)
612  return false;
613  }
614 
615  // Check if any of the successors of TailBB has a PHI node in which the
616  // value corresponding to TailBB uses a subregister.
617  // If a phi node uses a register paired with a subregister, the actual
618  // "value type" of the phi may differ from the type of the register without
619  // any subregisters. Due to a bug, tail duplication may add a new operand
620  // without a necessary subregister, producing an invalid code. This is
621  // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.
622  // Disable tail duplication for this case for now, until the problem is
623  // fixed.
624  for (auto SB : TailBB.successors()) {
625  for (auto &I : *SB) {
626  if (!I.isPHI())
627  break;
628  unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
629  assert(Idx != 0);
630  MachineOperand &PU = I.getOperand(Idx);
631  if (PU.getSubReg() != 0)
632  return false;
633  }
634  }
635 
636  if (HasIndirectbr && PreRegAlloc)
637  return true;
638 
639  if (IsSimple)
640  return true;
641 
642  if (!PreRegAlloc)
643  return true;
644 
645  return canCompletelyDuplicateBB(TailBB);
646 }
647 
648 /// True if this BB has only one unconditional jump.
650  if (TailBB->succ_size() != 1)
651  return false;
652  if (TailBB->pred_empty())
653  return false;
655  if (I == TailBB->end())
656  return true;
657  return I->isUnconditionalBranch();
658 }
659 
660 static bool bothUsedInPHI(const MachineBasicBlock &A,
661  const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) {
662  for (MachineBasicBlock *BB : A.successors())
663  if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
664  return true;
665 
666  return false;
667 }
668 
669 bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
670  for (MachineBasicBlock *PredBB : BB.predecessors()) {
671  if (PredBB->succ_size() > 1)
672  return false;
673 
674  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
676  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
677  return false;
678 
679  if (!PredCond.empty())
680  return false;
681  }
682  return true;
683 }
684 
685 bool TailDuplicator::duplicateSimpleBB(
687  const DenseSet<unsigned> &UsedByPhi,
690  TailBB->succ_end());
692  TailBB->pred_end());
693  bool Changed = false;
694  for (MachineBasicBlock *PredBB : Preds) {
695  if (PredBB->hasEHPadSuccessor())
696  continue;
697 
698  if (bothUsedInPHI(*PredBB, Succs))
699  continue;
700 
701  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
703  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
704  continue;
705 
706  Changed = true;
707  DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
708  << "From simple Succ: " << *TailBB);
709 
710  MachineBasicBlock *NewTarget = *TailBB->succ_begin();
711  MachineBasicBlock *NextBB = PredBB->getNextNode();
712 
713  // Make PredFBB explicit.
714  if (PredCond.empty())
715  PredFBB = PredTBB;
716 
717  // Make fall through explicit.
718  if (!PredTBB)
719  PredTBB = NextBB;
720  if (!PredFBB)
721  PredFBB = NextBB;
722 
723  // Redirect
724  if (PredFBB == TailBB)
725  PredFBB = NewTarget;
726  if (PredTBB == TailBB)
727  PredTBB = NewTarget;
728 
729  // Make the branch unconditional if possible
730  if (PredTBB == PredFBB) {
731  PredCond.clear();
732  PredFBB = nullptr;
733  }
734 
735  // Avoid adding fall through branches.
736  if (PredFBB == NextBB)
737  PredFBB = nullptr;
738  if (PredTBB == NextBB && PredFBB == nullptr)
739  PredTBB = nullptr;
740 
741  auto DL = PredBB->findBranchDebugLoc();
742  TII->removeBranch(*PredBB);
743 
744  if (!PredBB->isSuccessor(NewTarget))
745  PredBB->replaceSuccessor(TailBB, NewTarget);
746  else {
747  PredBB->removeSuccessor(TailBB, true);
748  assert(PredBB->succ_size() <= 1);
749  }
750 
751  if (PredTBB)
752  TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);
753 
754  TDBBs.push_back(PredBB);
755  }
756  return Changed;
757 }
758 
760  MachineBasicBlock *PredBB) {
761  // EH edges are ignored by analyzeBranch.
762  if (PredBB->succ_size() > 1)
763  return false;
764 
765  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
767  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
768  return false;
769  if (!PredCond.empty())
770  return false;
771  return true;
772 }
773 
774 /// If it is profitable, duplicate TailBB's contents in each
775 /// of its predecessors.
776 /// \p IsSimple result of isSimpleBB
777 /// \p TailBB Block to be duplicated.
778 /// \p ForcedLayoutPred When non-null, use this block as the layout predecessor
779 /// instead of the previous block in MF's order.
780 /// \p TDBBs A vector to keep track of all blocks tail-duplicated
781 /// into.
782 /// \p Copies A vector of copy instructions inserted. Used later to
783 /// walk all the inserted copies and remove redundant ones.
784 bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
785  MachineBasicBlock *ForcedLayoutPred,
788  DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB)
789  << '\n');
790 
791  DenseSet<unsigned> UsedByPhi;
792  getRegsUsedByPHIs(*TailBB, &UsedByPhi);
793 
794  if (IsSimple)
795  return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies);
796 
797  // Iterate through all the unique predecessors and tail-duplicate this
798  // block into them, if possible. Copying the list ahead of time also
799  // avoids trouble with the predecessor list reallocating.
800  bool Changed = false;
802  TailBB->pred_end());
803  for (MachineBasicBlock *PredBB : Preds) {
804  assert(TailBB != PredBB &&
805  "Single-block loop should have been rejected earlier!");
806 
807  if (!canTailDuplicate(TailBB, PredBB))
808  continue;
809 
810  // Don't duplicate into a fall-through predecessor (at least for now).
811  bool IsLayoutSuccessor = false;
812  if (ForcedLayoutPred)
813  IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
814  else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
815  IsLayoutSuccessor = true;
816  if (IsLayoutSuccessor)
817  continue;
818 
819  DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
820  << "From Succ: " << *TailBB);
821 
822  TDBBs.push_back(PredBB);
823 
824  // Remove PredBB's unconditional branch.
825  TII->removeBranch(*PredBB);
826 
827  // Clone the contents of TailBB into PredBB.
830  for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end();
831  I != E; /* empty */) {
832  MachineInstr *MI = &*I;
833  ++I;
834  if (MI->isPHI()) {
835  // Replace the uses of the def of the PHI with the register coming
836  // from PredBB.
837  processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
838  } else {
839  // Replace def of virtual registers with new registers, and update
840  // uses with PHI source register or the new registers.
841  duplicateInstruction(MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
842  }
843  }
844  appendCopies(PredBB, CopyInfos, Copies);
845 
846  // Simplify
847  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
849  TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond);
850 
851  NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
852 
853  // Update the CFG.
854  PredBB->removeSuccessor(PredBB->succ_begin());
855  assert(PredBB->succ_empty() &&
856  "TailDuplicate called on block with multiple successors!");
857  for (MachineBasicBlock *Succ : TailBB->successors())
858  PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ));
859 
860  Changed = true;
861  ++NumTailDups;
862  }
863 
864  // If TailBB was duplicated into all its predecessors except for the prior
865  // block, which falls through unconditionally, move the contents of this
866  // block into the prior block.
867  MachineBasicBlock *PrevBB = ForcedLayoutPred;
868  if (!PrevBB)
869  PrevBB = &*std::prev(TailBB->getIterator());
870  MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
872  // This has to check PrevBB->succ_size() because EH edges are ignored by
873  // analyzeBranch.
874  if (PrevBB->succ_size() == 1 &&
875  // Layout preds are not always CFG preds. Check.
876  *PrevBB->succ_begin() == TailBB &&
877  !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) &&
878  PriorCond.empty() &&
879  (!PriorTBB || PriorTBB == TailBB) &&
880  TailBB->pred_size() == 1 &&
881  !TailBB->hasAddressTaken()) {
882  DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
883  << "From MBB: " << *TailBB);
884  // There may be a branch to the layout successor. This is unlikely but it
885  // happens. The correct thing to do is to remove the branch before
886  // duplicating the instructions in all cases.
887  TII->removeBranch(*PrevBB);
888  if (PreRegAlloc) {
891  MachineBasicBlock::iterator I = TailBB->begin();
892  // Process PHI instructions first.
893  while (I != TailBB->end() && I->isPHI()) {
894  // Replace the uses of the def of the PHI with the register coming
895  // from PredBB.
896  MachineInstr *MI = &*I++;
897  processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true);
898  }
899 
900  // Now copy the non-PHI instructions.
901  while (I != TailBB->end()) {
902  // Replace def of virtual registers with new registers, and update
903  // uses with PHI source register or the new registers.
904  MachineInstr *MI = &*I++;
905  assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
906  duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
907  MI->eraseFromParent();
908  }
909  appendCopies(PrevBB, CopyInfos, Copies);
910  } else {
911  TII->removeBranch(*PrevBB);
912  // No PHIs to worry about, just splice the instructions over.
913  PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
914  }
915  PrevBB->removeSuccessor(PrevBB->succ_begin());
916  assert(PrevBB->succ_empty());
917  PrevBB->transferSuccessors(TailBB);
918  TDBBs.push_back(PrevBB);
919  Changed = true;
920  }
921 
922  // If this is after register allocation, there are no phis to fix.
923  if (!PreRegAlloc)
924  return Changed;
925 
926  // If we made no changes so far, we are safe.
927  if (!Changed)
928  return Changed;
929 
930  // Handle the nasty case in that we duplicated a block that is part of a loop
931  // into some but not all of its predecessors. For example:
932  // 1 -> 2 <-> 3 |
933  // \ |
934  // \---> rest |
935  // if we duplicate 2 into 1 but not into 3, we end up with
936  // 12 -> 3 <-> 2 -> rest |
937  // \ / |
938  // \----->-----/ |
939  // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced
940  // with a phi in 3 (which now dominates 2).
941  // What we do here is introduce a copy in 3 of the register defined by the
942  // phi, just like when we are duplicating 2 into 3, but we don't copy any
943  // real instructions or remove the 3 -> 2 edge from the phi in 2.
944  for (MachineBasicBlock *PredBB : Preds) {
945  if (is_contained(TDBBs, PredBB))
946  continue;
947 
948  // EH edges
949  if (PredBB->succ_size() != 1)
950  continue;
951 
954  MachineBasicBlock::iterator I = TailBB->begin();
955  // Process PHI instructions first.
956  while (I != TailBB->end() && I->isPHI()) {
957  // Replace the uses of the def of the PHI with the register coming
958  // from PredBB.
959  MachineInstr *MI = &*I++;
960  processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
961  }
962  appendCopies(PredBB, CopyInfos, Copies);
963  }
964 
965  return Changed;
966 }
967 
968 /// At the end of the block \p MBB generate COPY instructions between registers
969 /// described by \p CopyInfos. Append resulting instructions to \p Copies.
970 void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
971  SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
974  const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
975  for (auto &CI : CopyInfos) {
976  auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
977  .addReg(CI.second.Reg, 0, CI.second.SubReg);
978  Copies.push_back(C);
979  }
980 }
981 
982 /// Remove the specified dead machine basic block from the function, updating
983 /// the CFG.
984 void TailDuplicator::removeDeadBlock(
985  MachineBasicBlock *MBB,
986  function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
987  assert(MBB->pred_empty() && "MBB must be dead!");
988  DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
989 
990  if (RemovalCallback)
991  (*RemovalCallback)(MBB);
992 
993  // Remove all successors.
994  while (!MBB->succ_empty())
995  MBB->removeSuccessor(MBB->succ_end() - 1);
996 
997  // Remove the block.
998  MBB->eraseFromParent();
999 }
uint64_t CallInst * C
bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB)
Determine if it is profitable to duplicate this block.
void push_back(const T &Elt)
Definition: SmallVector.h:212
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:461
static cl::opt< unsigned > TailDuplicateSize("tail-dup-size", cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2), cl::Hidden)
MachineBasicBlock * getMBB() const
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned createVirtualRegister(const TargetRegisterClass *RegClass)
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:271
iterator getFirstNonDebugInstr()
Returns an iterator to the first non-debug instruction in the basic block, or end().
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
virtual MachineInstr & duplicate(MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, const MachineInstr &Orig) const
Clones instruction or the whole instruction bundle Orig and insert into MBB before InsertBefore...
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
unsigned getSubReg() const
static void VerifyPHIs(MachineFunction &MF, bool CheckExtra)
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.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:89
STATISTIC(NumFunctions, "Total number of functions")
void RewriteUse(MachineOperand &U)
RewriteUse - Rewrite a use of the symbolic value.
A debug info location.
Definition: DebugLoc.h:34
MachineModuleInfo & getMMI() const
static unsigned InstrCount
bool isPHI() const
Definition: MachineInstr.h:829
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
MachineSSAUpdater - This class updates SSA form for a set of virtual registers defined in multiple bl...
iterator_range< succ_iterator > successors()
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing function and deletes it.
static use_iterator use_end()
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const TargetRegisterClass * getRegClassConstraint(unsigned OpIdx, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const
Compute the static register class constraint for operand OpIdx.
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:296
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
static bool bothUsedInPHI(const MachineBasicBlock &A, const SmallPtrSet< MachineBasicBlock *, 8 > &SuccsB)
Reg
All possible values of the reg field in the ModR/M byte.
bool tailDuplicateBlocks()
Look for small blocks that are unconditionally branched to and do not fall through.
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
void RemoveOperand(unsigned i)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
bool isIndirectBranch(QueryType Type=AnyInBundle) const
Return true if this is an indirect branch, such as a branch through a register.
Definition: MachineInstr.h:491
bool isBundle() const
Definition: MachineInstr.h:856
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
void initMF(MachineFunction &MF, bool PreRegAlloc, const MachineBranchProbabilityInfo *MBPI, bool LayoutMode, unsigned TailDupSize=0)
Prepare to run on a specific machine function.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
void Initialize(unsigned V)
Initialize - Reset this object to get ready for a new set of SSA updates.
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:457
static bool isSimpleBB(MachineBasicBlock *TailBB)
True if this BB has only one unconditional jump.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool tailDuplicateAndUpdate(bool IsSimple, MachineBasicBlock *MBB, MachineBasicBlock *ForcedLayoutPred, SmallVectorImpl< MachineBasicBlock *> *DuplicatedPreds=nullptr, function_ref< void(MachineBasicBlock *)> *RemovalCallback=nullptr)
Tail duplicate a single basic block into its predecessors, and then clean up.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
unsigned composeSubRegIndices(unsigned a, unsigned b) const
Return the subregister index you get from composing two subregister indices.
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB)
Returns true if TailBB can successfully be duplicated into PredBB.
void setMBB(MachineBasicBlock *MBB)
bool optForSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:576
virtual const TargetRegisterClass * getMatchingSuperRegClass(const TargetRegisterClass *A, const TargetRegisterClass *B, unsigned Idx) const
Return a subclass of the specified register class A so that each register in it has a sub-register of...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
self_iterator getIterator()
Definition: ilist_node.h:82
iterator_range< pred_iterator > predecessors()
bool isCopy() const
Definition: MachineInstr.h:860
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
bool isConvergent(QueryType Type=AnyInBundle) const
Return true if this instruction is convergent.
Definition: MachineInstr.h:552
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...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setIsKill(bool Val=true)
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, const MachineRegisterInfo *MRI)
bool isDebugValue() const
Definition: MachineInstr.h:819
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
A pair composed of a register and a sub-register index.
MachineInstrBuilder MachineInstrBuilder & DefMI
static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB)
unsigned pred_size() const
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static cl::opt< unsigned > TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden)
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
unsigned succ_size() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:142
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Representation of each machine instruction.
Definition: MachineInstr.h:60
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
use_iterator use_begin(unsigned RegNo) const
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
void setSubReg(unsigned subReg)
iterator end()
Definition: DenseMap.h:79
void AddAvailableValue(MachineBasicBlock *BB, unsigned V)
AddAvailableValue - Indicate that a rewritten value is available at the end of the specified block wi...
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug instruction using the specified regis...
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
iterator_range< use_instr_iterator > use_instructions(unsigned Reg) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
static cl::opt< unsigned > TailDupIndirectBranchSize("tail-dup-indirect-size", cl::desc("Maximum instructions to consider tail duplicating blocks that " "end with indirect branches."), cl::init(20), cl::Hidden)
void setRegClass(unsigned Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:298
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
static void getRegsUsedByPHIs(const MachineBasicBlock &BB, DenseSet< unsigned > *UsedByPhi)
static cl::opt< bool > TailDupVerify("tail-dup-verify", cl::desc("Verify sanity of PHI instructions during taildup"), cl::init(false), cl::Hidden)
bool isNotDuplicable(QueryType Type=AnyInBundle) const
Return true if this instruction cannot be safely duplicated.
Definition: MachineInstr.h:545
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:873