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