LLVM  9.0.0svn
TailDuplicator.cpp
Go to the documentation of this file.
1 //===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This utility class duplicates basic blocks ending in unconditional branches
10 // into the tails of their predecessors.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
33 #include "llvm/IR/DebugLoc.h"
34 #include "llvm/IR/Function.h"
36 #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  LLVM_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  // Allow duplication of CFI instructions.
375  if (MI->isCFIInstruction()) {
376  BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()),
377  TII->get(TargetOpcode::CFI_INSTRUCTION)).addCFIIndex(
378  MI->getOperand(0).getCFIIndex());
379  return;
380  }
381  MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI);
382  if (PreRegAlloc) {
383  for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) {
384  MachineOperand &MO = NewMI.getOperand(i);
385  if (!MO.isReg())
386  continue;
387  unsigned Reg = MO.getReg();
389  continue;
390  if (MO.isDef()) {
391  const TargetRegisterClass *RC = MRI->getRegClass(Reg);
392  unsigned NewReg = MRI->createVirtualRegister(RC);
393  MO.setReg(NewReg);
394  LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
395  if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg))
396  addSSAUpdateEntry(Reg, NewReg, PredBB);
397  } else {
398  auto VI = LocalVRMap.find(Reg);
399  if (VI != LocalVRMap.end()) {
400  // Need to make sure that the register class of the mapped register
401  // will satisfy the constraints of the class of the register being
402  // replaced.
403  auto *OrigRC = MRI->getRegClass(Reg);
404  auto *MappedRC = MRI->getRegClass(VI->second.Reg);
405  const TargetRegisterClass *ConstrRC;
406  if (VI->second.SubReg != 0) {
407  ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC,
408  VI->second.SubReg);
409  if (ConstrRC) {
410  // The actual constraining (as in "find appropriate new class")
411  // is done by getMatchingSuperRegClass, so now we only need to
412  // change the class of the mapped register.
413  MRI->setRegClass(VI->second.Reg, ConstrRC);
414  }
415  } else {
416  // For mapped registers that do not have sub-registers, simply
417  // restrict their class to match the original one.
418  ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC);
419  }
420 
421  if (ConstrRC) {
422  // If the class constraining succeeded, we can simply replace
423  // the old register with the mapped one.
424  MO.setReg(VI->second.Reg);
425  // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a
426  // sub-register, we need to compose the sub-register indices.
428  VI->second.SubReg));
429  } else {
430  // The direct replacement is not possible, due to failing register
431  // class constraints. An explicit COPY is necessary. Create one
432  // that can be reused
433  auto *NewRC = MI->getRegClassConstraint(i, TII, TRI);
434  if (NewRC == nullptr)
435  NewRC = OrigRC;
436  unsigned NewReg = MRI->createVirtualRegister(NewRC);
437  BuildMI(*PredBB, MI, MI->getDebugLoc(),
438  TII->get(TargetOpcode::COPY), NewReg)
439  .addReg(VI->second.Reg, 0, VI->second.SubReg);
440  LocalVRMap.erase(VI);
441  LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
442  MO.setReg(NewReg);
443  // The composed VI.Reg:VI.SubReg is replaced with NewReg, which
444  // is equivalent to the whole register Reg. Hence, Reg:subreg
445  // is same as NewReg:subreg, so keep the sub-register index
446  // unchanged.
447  }
448  // Clear any kill flags from this operand. The new register could
449  // have uses after this one, so kills are not valid here.
450  MO.setIsKill(false);
451  }
452  }
453  }
454  }
455 }
456 
457 /// After FromBB is tail duplicated into its predecessor blocks, the successors
458 /// have gained new predecessors. Update the PHI instructions in them
459 /// accordingly.
460 void TailDuplicator::updateSuccessorsPHIs(
461  MachineBasicBlock *FromBB, bool isDead,
464  for (MachineBasicBlock *SuccBB : Succs) {
465  for (MachineInstr &MI : *SuccBB) {
466  if (!MI.isPHI())
467  break;
468  MachineInstrBuilder MIB(*FromBB->getParent(), MI);
469  unsigned Idx = 0;
470  for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
471  MachineOperand &MO = MI.getOperand(i + 1);
472  if (MO.getMBB() == FromBB) {
473  Idx = i;
474  break;
475  }
476  }
477 
478  assert(Idx != 0);
479  MachineOperand &MO0 = MI.getOperand(Idx);
480  unsigned Reg = MO0.getReg();
481  if (isDead) {
482  // Folded into the previous BB.
483  // There could be duplicate phi source entries. FIXME: Should sdisel
484  // or earlier pass fixed this?
485  for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) {
486  MachineOperand &MO = MI.getOperand(i + 1);
487  if (MO.getMBB() == FromBB) {
488  MI.RemoveOperand(i + 1);
489  MI.RemoveOperand(i);
490  }
491  }
492  } else
493  Idx = 0;
494 
495  // If Idx is set, the operands at Idx and Idx+1 must be removed.
496  // We reuse the location to avoid expensive RemoveOperand calls.
497 
499  SSAUpdateVals.find(Reg);
500  if (LI != SSAUpdateVals.end()) {
501  // This register is defined in the tail block.
502  for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
503  MachineBasicBlock *SrcBB = LI->second[j].first;
504  // If we didn't duplicate a bb into a particular predecessor, we
505  // might still have added an entry to SSAUpdateVals to correcly
506  // recompute SSA. If that case, avoid adding a dummy extra argument
507  // this PHI.
508  if (!SrcBB->isSuccessor(SuccBB))
509  continue;
510 
511  unsigned SrcReg = LI->second[j].second;
512  if (Idx != 0) {
513  MI.getOperand(Idx).setReg(SrcReg);
514  MI.getOperand(Idx + 1).setMBB(SrcBB);
515  Idx = 0;
516  } else {
517  MIB.addReg(SrcReg).addMBB(SrcBB);
518  }
519  }
520  } else {
521  // Live in tail block, must also be live in predecessors.
522  for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) {
523  MachineBasicBlock *SrcBB = TDBBs[j];
524  if (Idx != 0) {
525  MI.getOperand(Idx).setReg(Reg);
526  MI.getOperand(Idx + 1).setMBB(SrcBB);
527  Idx = 0;
528  } else {
529  MIB.addReg(Reg).addMBB(SrcBB);
530  }
531  }
532  }
533  if (Idx != 0) {
534  MI.RemoveOperand(Idx + 1);
535  MI.RemoveOperand(Idx);
536  }
537  }
538  }
539 }
540 
541 /// Determine if it is profitable to duplicate this block.
543  MachineBasicBlock &TailBB) {
544  // When doing tail-duplication during layout, the block ordering is in flux,
545  // so canFallThrough returns a result based on incorrect information and
546  // should just be ignored.
547  if (!LayoutMode && TailBB.canFallThrough())
548  return false;
549 
550  // Don't try to tail-duplicate single-block loops.
551  if (TailBB.isSuccessor(&TailBB))
552  return false;
553 
554  // Set the limit on the cost to duplicate. When optimizing for size,
555  // duplicate only one, because one branch instruction can be eliminated to
556  // compensate for the duplication.
557  unsigned MaxDuplicateCount;
558  if (TailDupSize == 0 &&
559  TailDuplicateSize.getNumOccurrences() == 0 &&
560  MF->getFunction().hasOptSize())
561  MaxDuplicateCount = 1;
562  else if (TailDupSize == 0)
563  MaxDuplicateCount = TailDuplicateSize;
564  else
565  MaxDuplicateCount = TailDupSize;
566 
567  // If the block to be duplicated ends in an unanalyzable fallthrough, don't
568  // duplicate it.
569  // A similar check is necessary in MachineBlockPlacement to make sure pairs of
570  // blocks with unanalyzable fallthrough get layed out contiguously.
571  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
573  if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&
574  TailBB.canFallThrough())
575  return false;
576 
577  // If the target has hardware branch prediction that can handle indirect
578  // branches, duplicating them can often make them predictable when there
579  // are common paths through the code. The limit needs to be high enough
580  // to allow undoing the effects of tail merging and other optimizations
581  // that rearrange the predecessors of the indirect branch.
582 
583  bool HasIndirectbr = false;
584  if (!TailBB.empty())
585  HasIndirectbr = TailBB.back().isIndirectBranch();
586 
587  if (HasIndirectbr && PreRegAlloc)
588  MaxDuplicateCount = TailDupIndirectBranchSize;
589 
590  // Check the instructions in the block to determine whether tail-duplication
591  // is invalid or unlikely to be profitable.
592  unsigned InstrCount = 0;
593  for (MachineInstr &MI : TailBB) {
594  // Non-duplicable things shouldn't be tail-duplicated.
595  // CFI instructions are marked as non-duplicable, because Darwin compact
596  // unwind info emission can't handle multiple prologue setups. In case of
597  // DWARF, allow them be duplicated, so that their existence doesn't prevent
598  // tail duplication of some basic blocks, that would be duplicated otherwise.
599  if (MI.isNotDuplicable() &&
600  (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() ||
601  !MI.isCFIInstruction()))
602  return false;
603 
604  // Convergent instructions can be duplicated only if doing so doesn't add
605  // new control dependencies, which is what we're going to do here.
606  if (MI.isConvergent())
607  return false;
608 
609  // Do not duplicate 'return' instructions if this is a pre-regalloc run.
610  // A return may expand into a lot more instructions (e.g. reload of callee
611  // saved registers) after PEI.
612  if (PreRegAlloc && MI.isReturn())
613  return false;
614 
615  // Avoid duplicating calls before register allocation. Calls presents a
616  // barrier to register allocation so duplicating them may end up increasing
617  // spills.
618  if (PreRegAlloc && MI.isCall())
619  return false;
620 
621  if (!MI.isPHI() && !MI.isMetaInstruction())
622  InstrCount += 1;
623 
624  if (InstrCount > MaxDuplicateCount)
625  return false;
626  }
627 
628  // Check if any of the successors of TailBB has a PHI node in which the
629  // value corresponding to TailBB uses a subregister.
630  // If a phi node uses a register paired with a subregister, the actual
631  // "value type" of the phi may differ from the type of the register without
632  // any subregisters. Due to a bug, tail duplication may add a new operand
633  // without a necessary subregister, producing an invalid code. This is
634  // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.
635  // Disable tail duplication for this case for now, until the problem is
636  // fixed.
637  for (auto SB : TailBB.successors()) {
638  for (auto &I : *SB) {
639  if (!I.isPHI())
640  break;
641  unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
642  assert(Idx != 0);
643  MachineOperand &PU = I.getOperand(Idx);
644  if (PU.getSubReg() != 0)
645  return false;
646  }
647  }
648 
649  if (HasIndirectbr && PreRegAlloc)
650  return true;
651 
652  if (IsSimple)
653  return true;
654 
655  if (!PreRegAlloc)
656  return true;
657 
658  return canCompletelyDuplicateBB(TailBB);
659 }
660 
661 /// True if this BB has only one unconditional jump.
663  if (TailBB->succ_size() != 1)
664  return false;
665  if (TailBB->pred_empty())
666  return false;
668  if (I == TailBB->end())
669  return true;
670  return I->isUnconditionalBranch();
671 }
672 
673 static bool bothUsedInPHI(const MachineBasicBlock &A,
674  const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) {
675  for (MachineBasicBlock *BB : A.successors())
676  if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
677  return true;
678 
679  return false;
680 }
681 
682 bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
683  for (MachineBasicBlock *PredBB : BB.predecessors()) {
684  if (PredBB->succ_size() > 1)
685  return false;
686 
687  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
689  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
690  return false;
691 
692  if (!PredCond.empty())
693  return false;
694  }
695  return true;
696 }
697 
698 bool TailDuplicator::duplicateSimpleBB(
700  const DenseSet<unsigned> &UsedByPhi,
703  TailBB->succ_end());
705  TailBB->pred_end());
706  bool Changed = false;
707  for (MachineBasicBlock *PredBB : Preds) {
708  if (PredBB->hasEHPadSuccessor())
709  continue;
710 
711  if (bothUsedInPHI(*PredBB, Succs))
712  continue;
713 
714  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
716  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
717  continue;
718 
719  Changed = true;
720  LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
721  << "From simple Succ: " << *TailBB);
722 
723  MachineBasicBlock *NewTarget = *TailBB->succ_begin();
724  MachineBasicBlock *NextBB = PredBB->getNextNode();
725 
726  // Make PredFBB explicit.
727  if (PredCond.empty())
728  PredFBB = PredTBB;
729 
730  // Make fall through explicit.
731  if (!PredTBB)
732  PredTBB = NextBB;
733  if (!PredFBB)
734  PredFBB = NextBB;
735 
736  // Redirect
737  if (PredFBB == TailBB)
738  PredFBB = NewTarget;
739  if (PredTBB == TailBB)
740  PredTBB = NewTarget;
741 
742  // Make the branch unconditional if possible
743  if (PredTBB == PredFBB) {
744  PredCond.clear();
745  PredFBB = nullptr;
746  }
747 
748  // Avoid adding fall through branches.
749  if (PredFBB == NextBB)
750  PredFBB = nullptr;
751  if (PredTBB == NextBB && PredFBB == nullptr)
752  PredTBB = nullptr;
753 
754  auto DL = PredBB->findBranchDebugLoc();
755  TII->removeBranch(*PredBB);
756 
757  if (!PredBB->isSuccessor(NewTarget))
758  PredBB->replaceSuccessor(TailBB, NewTarget);
759  else {
760  PredBB->removeSuccessor(TailBB, true);
761  assert(PredBB->succ_size() <= 1);
762  }
763 
764  if (PredTBB)
765  TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);
766 
767  TDBBs.push_back(PredBB);
768  }
769  return Changed;
770 }
771 
773  MachineBasicBlock *PredBB) {
774  // EH edges are ignored by analyzeBranch.
775  if (PredBB->succ_size() > 1)
776  return false;
777 
778  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
780  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
781  return false;
782  if (!PredCond.empty())
783  return false;
784  return true;
785 }
786 
787 /// If it is profitable, duplicate TailBB's contents in each
788 /// of its predecessors.
789 /// \p IsSimple result of isSimpleBB
790 /// \p TailBB Block to be duplicated.
791 /// \p ForcedLayoutPred When non-null, use this block as the layout predecessor
792 /// instead of the previous block in MF's order.
793 /// \p TDBBs A vector to keep track of all blocks tail-duplicated
794 /// into.
795 /// \p Copies A vector of copy instructions inserted. Used later to
796 /// walk all the inserted copies and remove redundant ones.
797 bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
798  MachineBasicBlock *ForcedLayoutPred,
801  LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB)
802  << '\n');
803 
804  DenseSet<unsigned> UsedByPhi;
805  getRegsUsedByPHIs(*TailBB, &UsedByPhi);
806 
807  if (IsSimple)
808  return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies);
809 
810  // Iterate through all the unique predecessors and tail-duplicate this
811  // block into them, if possible. Copying the list ahead of time also
812  // avoids trouble with the predecessor list reallocating.
813  bool Changed = false;
815  TailBB->pred_end());
816  for (MachineBasicBlock *PredBB : Preds) {
817  assert(TailBB != PredBB &&
818  "Single-block loop should have been rejected earlier!");
819 
820  if (!canTailDuplicate(TailBB, PredBB))
821  continue;
822 
823  // Don't duplicate into a fall-through predecessor (at least for now).
824  bool IsLayoutSuccessor = false;
825  if (ForcedLayoutPred)
826  IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
827  else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
828  IsLayoutSuccessor = true;
829  if (IsLayoutSuccessor)
830  continue;
831 
832  LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
833  << "From Succ: " << *TailBB);
834 
835  TDBBs.push_back(PredBB);
836 
837  // Remove PredBB's unconditional branch.
838  TII->removeBranch(*PredBB);
839 
840  // Clone the contents of TailBB into PredBB.
843  for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end();
844  I != E; /* empty */) {
845  MachineInstr *MI = &*I;
846  ++I;
847  if (MI->isPHI()) {
848  // Replace the uses of the def of the PHI with the register coming
849  // from PredBB.
850  processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
851  } else {
852  // Replace def of virtual registers with new registers, and update
853  // uses with PHI source register or the new registers.
854  duplicateInstruction(MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
855  }
856  }
857  appendCopies(PredBB, CopyInfos, Copies);
858 
859  // Simplify
860  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
862  TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond);
863 
864  NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
865 
866  // Update the CFG.
867  PredBB->removeSuccessor(PredBB->succ_begin());
868  assert(PredBB->succ_empty() &&
869  "TailDuplicate called on block with multiple successors!");
870  for (MachineBasicBlock *Succ : TailBB->successors())
871  PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ));
872 
873  Changed = true;
874  ++NumTailDups;
875  }
876 
877  // If TailBB was duplicated into all its predecessors except for the prior
878  // block, which falls through unconditionally, move the contents of this
879  // block into the prior block.
880  MachineBasicBlock *PrevBB = ForcedLayoutPred;
881  if (!PrevBB)
882  PrevBB = &*std::prev(TailBB->getIterator());
883  MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
885  // This has to check PrevBB->succ_size() because EH edges are ignored by
886  // analyzeBranch.
887  if (PrevBB->succ_size() == 1 &&
888  // Layout preds are not always CFG preds. Check.
889  *PrevBB->succ_begin() == TailBB &&
890  !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) &&
891  PriorCond.empty() &&
892  (!PriorTBB || PriorTBB == TailBB) &&
893  TailBB->pred_size() == 1 &&
894  !TailBB->hasAddressTaken()) {
895  LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
896  << "From MBB: " << *TailBB);
897  // There may be a branch to the layout successor. This is unlikely but it
898  // happens. The correct thing to do is to remove the branch before
899  // duplicating the instructions in all cases.
900  TII->removeBranch(*PrevBB);
901  if (PreRegAlloc) {
904  MachineBasicBlock::iterator I = TailBB->begin();
905  // Process PHI instructions first.
906  while (I != TailBB->end() && I->isPHI()) {
907  // Replace the uses of the def of the PHI with the register coming
908  // from PredBB.
909  MachineInstr *MI = &*I++;
910  processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true);
911  }
912 
913  // Now copy the non-PHI instructions.
914  while (I != TailBB->end()) {
915  // Replace def of virtual registers with new registers, and update
916  // uses with PHI source register or the new registers.
917  MachineInstr *MI = &*I++;
918  assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
919  duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
920  MI->eraseFromParent();
921  }
922  appendCopies(PrevBB, CopyInfos, Copies);
923  } else {
924  TII->removeBranch(*PrevBB);
925  // No PHIs to worry about, just splice the instructions over.
926  PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
927  }
928  PrevBB->removeSuccessor(PrevBB->succ_begin());
929  assert(PrevBB->succ_empty());
930  PrevBB->transferSuccessors(TailBB);
931  TDBBs.push_back(PrevBB);
932  Changed = true;
933  }
934 
935  // If this is after register allocation, there are no phis to fix.
936  if (!PreRegAlloc)
937  return Changed;
938 
939  // If we made no changes so far, we are safe.
940  if (!Changed)
941  return Changed;
942 
943  // Handle the nasty case in that we duplicated a block that is part of a loop
944  // into some but not all of its predecessors. For example:
945  // 1 -> 2 <-> 3 |
946  // \ |
947  // \---> rest |
948  // if we duplicate 2 into 1 but not into 3, we end up with
949  // 12 -> 3 <-> 2 -> rest |
950  // \ / |
951  // \----->-----/ |
952  // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced
953  // with a phi in 3 (which now dominates 2).
954  // What we do here is introduce a copy in 3 of the register defined by the
955  // phi, just like when we are duplicating 2 into 3, but we don't copy any
956  // real instructions or remove the 3 -> 2 edge from the phi in 2.
957  for (MachineBasicBlock *PredBB : Preds) {
958  if (is_contained(TDBBs, PredBB))
959  continue;
960 
961  // EH edges
962  if (PredBB->succ_size() != 1)
963  continue;
964 
967  MachineBasicBlock::iterator I = TailBB->begin();
968  // Process PHI instructions first.
969  while (I != TailBB->end() && I->isPHI()) {
970  // Replace the uses of the def of the PHI with the register coming
971  // from PredBB.
972  MachineInstr *MI = &*I++;
973  processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
974  }
975  appendCopies(PredBB, CopyInfos, Copies);
976  }
977 
978  return Changed;
979 }
980 
981 /// At the end of the block \p MBB generate COPY instructions between registers
982 /// described by \p CopyInfos. Append resulting instructions to \p Copies.
983 void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
984  SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
987  const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
988  for (auto &CI : CopyInfos) {
989  auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
990  .addReg(CI.second.Reg, 0, CI.second.SubReg);
991  Copies.push_back(C);
992  }
993 }
994 
995 /// Remove the specified dead machine basic block from the function, updating
996 /// the CFG.
997 void TailDuplicator::removeDeadBlock(
998  MachineBasicBlock *MBB,
999  function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
1000  assert(MBB->pred_empty() && "MBB must be dead!");
1001  LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
1002 
1003  if (RemovalCallback)
1004  (*RemovalCallback)(MBB);
1005 
1006  // Remove all successors.
1007  while (!MBB->succ_empty())
1008  MBB->removeSuccessor(MBB->succ_end() - 1);
1009 
1010  // Remove the block.
1011  MBB->eraseFromParent();
1012 }
uint64_t CallInst * C
bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB)
Determine if it is profitable to duplicate this block.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:632
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:288
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:603
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool isCFIInstruction() const
Definition: MachineInstr.h:989
void push_back(const T &Elt)
Definition: SmallVector.h:211
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:382
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.
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:116
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:33
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...
bool isPHI() const
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:221
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
Retuns the total number of operands.
Definition: MachineInstr.h:411
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
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:662
bool isBundle() const
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:176
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:622
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:432
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)
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:381
self_iterator getIterator()
Definition: ilist_node.h:81
iterator_range< pred_iterator > predecessors()
bool isCopy() const
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:729
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...
size_t size() const
Definition: SmallVector.h:52
#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:297
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:417
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:996
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:841
A pair composed of a register and a sub-register index.
MachineInstrBuilder MachineInstrBuilder & DefMI
SI Lower i1 Copies
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:253
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:63
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:55
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
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:108
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:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
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:722
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:1244