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