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