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 
217  // Rewrite uses that are outside of the original def's block.
219  while (UI != MRI->use_end()) {
220  MachineOperand &UseMO = *UI;
221  MachineInstr *UseMI = UseMO.getParent();
222  ++UI;
223  // Rewrite debug uses last so that they can take advantage of any
224  // register mappings introduced by other users in its BB, since we
225  // cannot create new register definitions specifically for the debug
226  // instruction (as debug instructions should not affect CodeGen).
227  if (UseMI->isDebugValue()) {
228  DebugUses.push_back(&UseMO);
229  continue;
230  }
231  if (UseMI->getParent() == DefBB && !UseMI->isPHI())
232  continue;
233  SSAUpdate.RewriteUse(UseMO);
234  }
235  for (auto *UseMO : DebugUses) {
236  MachineInstr *UseMI = UseMO->getParent();
237  UseMO->setReg(
238  SSAUpdate.GetValueInMiddleOfBlock(UseMI->getParent(), true));
239  }
240  }
241 
242  SSAUpdateVRs.clear();
243  SSAUpdateVals.clear();
244  }
245 
246  // Eliminate some of the copies inserted by tail duplication to maintain
247  // SSA form.
248  for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
249  MachineInstr *Copy = Copies[i];
250  if (!Copy->isCopy())
251  continue;
252  Register Dst = Copy->getOperand(0).getReg();
253  Register Src = Copy->getOperand(1).getReg();
254  if (MRI->hasOneNonDBGUse(Src) &&
255  MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) {
256  // Copy is the only use. Do trivial copy propagation here.
257  MRI->replaceRegWith(Dst, Src);
258  Copy->eraseFromParent();
259  }
260  }
261 
262  if (NewPHIs.size())
263  NumAddedPHIs += NewPHIs.size();
264 
265  if (DuplicatedPreds)
266  *DuplicatedPreds = std::move(TDBBs);
267 
268  return true;
269 }
270 
271 /// Look for small blocks that are unconditionally branched to and do not fall
272 /// through. Tail-duplicate their instructions into their predecessors to
273 /// eliminate (dynamic) branches.
275  bool MadeChange = false;
276 
277  if (PreRegAlloc && TailDupVerify) {
278  LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
279  VerifyPHIs(*MF, true);
280  }
281 
282  for (MachineBasicBlock &MBB :
284  if (NumTails == TailDupLimit)
285  break;
286 
287  bool IsSimple = isSimpleBB(&MBB);
288 
289  if (!shouldTailDuplicate(IsSimple, MBB))
290  continue;
291 
292  MadeChange |= tailDuplicateAndUpdate(IsSimple, &MBB, nullptr);
293  }
294 
295  if (PreRegAlloc && TailDupVerify)
296  VerifyPHIs(*MF, false);
297 
298  return MadeChange;
299 }
300 
302  const MachineRegisterInfo *MRI) {
304  if (UseMI.isDebugValue())
305  continue;
306  if (UseMI.getParent() != BB)
307  return true;
308  }
309  return false;
310 }
311 
313  for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)
314  if (MI->getOperand(i + 1).getMBB() == SrcBB)
315  return i;
316  return 0;
317 }
318 
319 // Remember which registers are used by phis in this block. This is
320 // used to determine which registers are liveout while modifying the
321 // block (which is why we need to copy the information).
323  DenseSet<Register> *UsedByPhi) {
324  for (const auto &MI : BB) {
325  if (!MI.isPHI())
326  break;
327  for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
328  Register SrcReg = MI.getOperand(i).getReg();
329  UsedByPhi->insert(SrcReg);
330  }
331  }
332 }
333 
334 /// Add a definition and source virtual registers pair for SSA update.
335 void TailDuplicator::addSSAUpdateEntry(Register OrigReg, Register NewReg,
338  SSAUpdateVals.find(OrigReg);
339  if (LI != SSAUpdateVals.end())
340  LI->second.push_back(std::make_pair(BB, NewReg));
341  else {
342  AvailableValsTy Vals;
343  Vals.push_back(std::make_pair(BB, NewReg));
344  SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));
345  SSAUpdateVRs.push_back(OrigReg);
346  }
347 }
348 
349 /// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the
350 /// source register that's contributed by PredBB and update SSA update map.
351 void TailDuplicator::processPHI(
354  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
355  const DenseSet<Register> &RegsUsedByPhi, bool Remove) {
356  Register DefReg = MI->getOperand(0).getReg();
357  unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);
358  assert(SrcOpIdx && "Unable to find matching PHI source?");
359  Register SrcReg = MI->getOperand(SrcOpIdx).getReg();
360  unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg();
361  const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
362  LocalVRMap.insert(std::make_pair(DefReg, RegSubRegPair(SrcReg, SrcSubReg)));
363 
364  // Insert a copy from source to the end of the block. The def register is the
365  // available value liveout of the block.
366  Register NewDef = MRI->createVirtualRegister(RC);
367  Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg)));
368  if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg))
369  addSSAUpdateEntry(DefReg, NewDef, PredBB);
370 
371  if (!Remove)
372  return;
373 
374  // Remove PredBB from the PHI node.
375  MI->RemoveOperand(SrcOpIdx + 1);
376  MI->RemoveOperand(SrcOpIdx);
377  if (MI->getNumOperands() == 1)
378  MI->eraseFromParent();
379 }
380 
381 /// Duplicate a TailBB instruction to PredBB and update
382 /// the source operands due to earlier PHI translation.
383 void TailDuplicator::duplicateInstruction(
386  const DenseSet<Register> &UsedByPhi) {
387  // Allow duplication of CFI instructions.
388  if (MI->isCFIInstruction()) {
389  BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()),
390  TII->get(TargetOpcode::CFI_INSTRUCTION)).addCFIIndex(
391  MI->getOperand(0).getCFIIndex());
392  return;
393  }
394  MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI);
395  if (PreRegAlloc) {
396  for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) {
397  MachineOperand &MO = NewMI.getOperand(i);
398  if (!MO.isReg())
399  continue;
400  Register Reg = MO.getReg();
402  continue;
403  if (MO.isDef()) {
404  const TargetRegisterClass *RC = MRI->getRegClass(Reg);
405  Register NewReg = MRI->createVirtualRegister(RC);
406  MO.setReg(NewReg);
407  LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
408  if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg))
409  addSSAUpdateEntry(Reg, NewReg, PredBB);
410  } else {
411  auto VI = LocalVRMap.find(Reg);
412  if (VI != LocalVRMap.end()) {
413  // Need to make sure that the register class of the mapped register
414  // will satisfy the constraints of the class of the register being
415  // replaced.
416  auto *OrigRC = MRI->getRegClass(Reg);
417  auto *MappedRC = MRI->getRegClass(VI->second.Reg);
418  const TargetRegisterClass *ConstrRC;
419  if (VI->second.SubReg != 0) {
420  ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC,
421  VI->second.SubReg);
422  if (ConstrRC) {
423  // The actual constraining (as in "find appropriate new class")
424  // is done by getMatchingSuperRegClass, so now we only need to
425  // change the class of the mapped register.
426  MRI->setRegClass(VI->second.Reg, ConstrRC);
427  }
428  } else {
429  // For mapped registers that do not have sub-registers, simply
430  // restrict their class to match the original one.
431  ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC);
432  }
433 
434  if (ConstrRC) {
435  // If the class constraining succeeded, we can simply replace
436  // the old register with the mapped one.
437  MO.setReg(VI->second.Reg);
438  // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a
439  // sub-register, we need to compose the sub-register indices.
441  VI->second.SubReg));
442  } else {
443  // The direct replacement is not possible, due to failing register
444  // class constraints. An explicit COPY is necessary. Create one
445  // that can be reused
446  auto *NewRC = MI->getRegClassConstraint(i, TII, TRI);
447  if (NewRC == nullptr)
448  NewRC = OrigRC;
449  Register NewReg = MRI->createVirtualRegister(NewRC);
450  BuildMI(*PredBB, NewMI, NewMI.getDebugLoc(),
451  TII->get(TargetOpcode::COPY), NewReg)
452  .addReg(VI->second.Reg, 0, VI->second.SubReg);
453  LocalVRMap.erase(VI);
454  LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
455  MO.setReg(NewReg);
456  // The composed VI.Reg:VI.SubReg is replaced with NewReg, which
457  // is equivalent to the whole register Reg. Hence, Reg:subreg
458  // is same as NewReg:subreg, so keep the sub-register index
459  // unchanged.
460  }
461  // Clear any kill flags from this operand. The new register could
462  // have uses after this one, so kills are not valid here.
463  MO.setIsKill(false);
464  }
465  }
466  }
467  }
468 }
469 
470 /// After FromBB is tail duplicated into its predecessor blocks, the successors
471 /// have gained new predecessors. Update the PHI instructions in them
472 /// accordingly.
473 void TailDuplicator::updateSuccessorsPHIs(
474  MachineBasicBlock *FromBB, bool isDead,
477  for (MachineBasicBlock *SuccBB : Succs) {
478  for (MachineInstr &MI : *SuccBB) {
479  if (!MI.isPHI())
480  break;
481  MachineInstrBuilder MIB(*FromBB->getParent(), MI);
482  unsigned Idx = 0;
483  for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
484  MachineOperand &MO = MI.getOperand(i + 1);
485  if (MO.getMBB() == FromBB) {
486  Idx = i;
487  break;
488  }
489  }
490 
491  assert(Idx != 0);
492  MachineOperand &MO0 = MI.getOperand(Idx);
493  Register Reg = MO0.getReg();
494  if (isDead) {
495  // Folded into the previous BB.
496  // There could be duplicate phi source entries. FIXME: Should sdisel
497  // or earlier pass fixed this?
498  for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) {
499  MachineOperand &MO = MI.getOperand(i + 1);
500  if (MO.getMBB() == FromBB) {
501  MI.RemoveOperand(i + 1);
502  MI.RemoveOperand(i);
503  }
504  }
505  } else
506  Idx = 0;
507 
508  // If Idx is set, the operands at Idx and Idx+1 must be removed.
509  // We reuse the location to avoid expensive RemoveOperand calls.
510 
512  SSAUpdateVals.find(Reg);
513  if (LI != SSAUpdateVals.end()) {
514  // This register is defined in the tail block.
515  for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
516  MachineBasicBlock *SrcBB = LI->second[j].first;
517  // If we didn't duplicate a bb into a particular predecessor, we
518  // might still have added an entry to SSAUpdateVals to correcly
519  // recompute SSA. If that case, avoid adding a dummy extra argument
520  // this PHI.
521  if (!SrcBB->isSuccessor(SuccBB))
522  continue;
523 
524  Register SrcReg = LI->second[j].second;
525  if (Idx != 0) {
526  MI.getOperand(Idx).setReg(SrcReg);
527  MI.getOperand(Idx + 1).setMBB(SrcBB);
528  Idx = 0;
529  } else {
530  MIB.addReg(SrcReg).addMBB(SrcBB);
531  }
532  }
533  } else {
534  // Live in tail block, must also be live in predecessors.
535  for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) {
536  MachineBasicBlock *SrcBB = TDBBs[j];
537  if (Idx != 0) {
538  MI.getOperand(Idx).setReg(Reg);
539  MI.getOperand(Idx + 1).setMBB(SrcBB);
540  Idx = 0;
541  } else {
542  MIB.addReg(Reg).addMBB(SrcBB);
543  }
544  }
545  }
546  if (Idx != 0) {
547  MI.RemoveOperand(Idx + 1);
548  MI.RemoveOperand(Idx);
549  }
550  }
551  }
552 }
553 
554 /// Determine if it is profitable to duplicate this block.
556  MachineBasicBlock &TailBB) {
557  // When doing tail-duplication during layout, the block ordering is in flux,
558  // so canFallThrough returns a result based on incorrect information and
559  // should just be ignored.
560  if (!LayoutMode && TailBB.canFallThrough())
561  return false;
562 
563  // Don't try to tail-duplicate single-block loops.
564  if (TailBB.isSuccessor(&TailBB))
565  return false;
566 
567  // Set the limit on the cost to duplicate. When optimizing for size,
568  // duplicate only one, because one branch instruction can be eliminated to
569  // compensate for the duplication.
570  unsigned MaxDuplicateCount;
571  bool OptForSize = MF->getFunction().hasOptSize() ||
572  llvm::shouldOptimizeForSize(&TailBB, PSI, MBFI);
573  if (TailDupSize == 0)
574  MaxDuplicateCount = TailDuplicateSize;
575  else
576  MaxDuplicateCount = TailDupSize;
577  if (OptForSize)
578  MaxDuplicateCount = 1;
579 
580  // If the block to be duplicated ends in an unanalyzable fallthrough, don't
581  // duplicate it.
582  // A similar check is necessary in MachineBlockPlacement to make sure pairs of
583  // blocks with unanalyzable fallthrough get layed out contiguously.
584  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
586  if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&
587  TailBB.canFallThrough())
588  return false;
589 
590  // If the target has hardware branch prediction that can handle indirect
591  // branches, duplicating them can often make them predictable when there
592  // are common paths through the code. The limit needs to be high enough
593  // to allow undoing the effects of tail merging and other optimizations
594  // that rearrange the predecessors of the indirect branch.
595 
596  bool HasIndirectbr = false;
597  if (!TailBB.empty())
598  HasIndirectbr = TailBB.back().isIndirectBranch();
599 
600  if (HasIndirectbr && PreRegAlloc)
601  MaxDuplicateCount = TailDupIndirectBranchSize;
602 
603  // Check the instructions in the block to determine whether tail-duplication
604  // is invalid or unlikely to be profitable.
605  unsigned InstrCount = 0;
606  for (MachineInstr &MI : TailBB) {
607  // Non-duplicable things shouldn't be tail-duplicated.
608  // CFI instructions are marked as non-duplicable, because Darwin compact
609  // unwind info emission can't handle multiple prologue setups. In case of
610  // DWARF, allow them be duplicated, so that their existence doesn't prevent
611  // tail duplication of some basic blocks, that would be duplicated otherwise.
612  if (MI.isNotDuplicable() &&
613  (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() ||
614  !MI.isCFIInstruction()))
615  return false;
616 
617  // Convergent instructions can be duplicated only if doing so doesn't add
618  // new control dependencies, which is what we're going to do here.
619  if (MI.isConvergent())
620  return false;
621 
622  // Do not duplicate 'return' instructions if this is a pre-regalloc run.
623  // A return may expand into a lot more instructions (e.g. reload of callee
624  // saved registers) after PEI.
625  if (PreRegAlloc && MI.isReturn())
626  return false;
627 
628  // Avoid duplicating calls before register allocation. Calls presents a
629  // barrier to register allocation so duplicating them may end up increasing
630  // spills.
631  if (PreRegAlloc && MI.isCall())
632  return false;
633 
634  // TailDuplicator::appendCopies will erroneously place COPYs after
635  // INLINEASM_BR instructions after 4b0aa5724fea, which demonstrates the same
636  // bug that was fixed in f7a53d82c090.
637  // FIXME: Use findPHICopyInsertPoint() to find the correct insertion point
638  // for the COPY when replacing PHIs.
639  if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)
640  return false;
641 
642  if (MI.isBundle())
643  InstrCount += MI.getBundleSize();
644  else if (!MI.isPHI() && !MI.isMetaInstruction())
645  InstrCount += 1;
646 
647  if (InstrCount > MaxDuplicateCount)
648  return false;
649  }
650 
651  // Check if any of the successors of TailBB has a PHI node in which the
652  // value corresponding to TailBB uses a subregister.
653  // If a phi node uses a register paired with a subregister, the actual
654  // "value type" of the phi may differ from the type of the register without
655  // any subregisters. Due to a bug, tail duplication may add a new operand
656  // without a necessary subregister, producing an invalid code. This is
657  // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.
658  // Disable tail duplication for this case for now, until the problem is
659  // fixed.
660  for (auto SB : TailBB.successors()) {
661  for (auto &I : *SB) {
662  if (!I.isPHI())
663  break;
664  unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
665  assert(Idx != 0);
666  MachineOperand &PU = I.getOperand(Idx);
667  if (PU.getSubReg() != 0)
668  return false;
669  }
670  }
671 
672  if (HasIndirectbr && PreRegAlloc)
673  return true;
674 
675  if (IsSimple)
676  return true;
677 
678  if (!PreRegAlloc)
679  return true;
680 
681  return canCompletelyDuplicateBB(TailBB);
682 }
683 
684 /// True if this BB has only one unconditional jump.
686  if (TailBB->succ_size() != 1)
687  return false;
688  if (TailBB->pred_empty())
689  return false;
691  if (I == TailBB->end())
692  return true;
693  return I->isUnconditionalBranch();
694 }
695 
696 static bool bothUsedInPHI(const MachineBasicBlock &A,
697  const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) {
698  for (MachineBasicBlock *BB : A.successors())
699  if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
700  return true;
701 
702  return false;
703 }
704 
705 bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
706  for (MachineBasicBlock *PredBB : BB.predecessors()) {
707  if (PredBB->succ_size() > 1)
708  return false;
709 
710  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
712  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
713  return false;
714 
715  if (!PredCond.empty())
716  return false;
717  }
718  return true;
719 }
720 
721 bool TailDuplicator::duplicateSimpleBB(
723  const DenseSet<Register> &UsedByPhi,
726  TailBB->succ_end());
728  bool Changed = false;
729  for (MachineBasicBlock *PredBB : Preds) {
730  if (PredBB->hasEHPadSuccessor() || PredBB->mayHaveInlineAsmBr())
731  continue;
732 
733  if (bothUsedInPHI(*PredBB, Succs))
734  continue;
735 
736  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
738  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
739  continue;
740 
741  Changed = true;
742  LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
743  << "From simple Succ: " << *TailBB);
744 
745  MachineBasicBlock *NewTarget = *TailBB->succ_begin();
746  MachineBasicBlock *NextBB = PredBB->getNextNode();
747 
748  // Make PredFBB explicit.
749  if (PredCond.empty())
750  PredFBB = PredTBB;
751 
752  // Make fall through explicit.
753  if (!PredTBB)
754  PredTBB = NextBB;
755  if (!PredFBB)
756  PredFBB = NextBB;
757 
758  // Redirect
759  if (PredFBB == TailBB)
760  PredFBB = NewTarget;
761  if (PredTBB == TailBB)
762  PredTBB = NewTarget;
763 
764  // Make the branch unconditional if possible
765  if (PredTBB == PredFBB) {
766  PredCond.clear();
767  PredFBB = nullptr;
768  }
769 
770  // Avoid adding fall through branches.
771  if (PredFBB == NextBB)
772  PredFBB = nullptr;
773  if (PredTBB == NextBB && PredFBB == nullptr)
774  PredTBB = nullptr;
775 
776  auto DL = PredBB->findBranchDebugLoc();
777  TII->removeBranch(*PredBB);
778 
779  if (!PredBB->isSuccessor(NewTarget))
780  PredBB->replaceSuccessor(TailBB, NewTarget);
781  else {
782  PredBB->removeSuccessor(TailBB, true);
783  assert(PredBB->succ_size() <= 1);
784  }
785 
786  if (PredTBB)
787  TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);
788 
789  TDBBs.push_back(PredBB);
790  }
791  return Changed;
792 }
793 
795  MachineBasicBlock *PredBB) {
796  // EH edges are ignored by analyzeBranch.
797  if (PredBB->succ_size() > 1)
798  return false;
799 
800  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
802  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
803  return false;
804  if (!PredCond.empty())
805  return false;
806  return true;
807 }
808 
809 /// If it is profitable, duplicate TailBB's contents in each
810 /// of its predecessors.
811 /// \p IsSimple result of isSimpleBB
812 /// \p TailBB Block to be duplicated.
813 /// \p ForcedLayoutPred When non-null, use this block as the layout predecessor
814 /// instead of the previous block in MF's order.
815 /// \p TDBBs A vector to keep track of all blocks tail-duplicated
816 /// into.
817 /// \p Copies A vector of copy instructions inserted. Used later to
818 /// walk all the inserted copies and remove redundant ones.
819 bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
820  MachineBasicBlock *ForcedLayoutPred,
823  SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) {
824  LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB)
825  << '\n');
826 
827  bool ShouldUpdateTerminators = TailBB->canFallThrough();
828 
829  DenseSet<Register> UsedByPhi;
830  getRegsUsedByPHIs(*TailBB, &UsedByPhi);
831 
832  if (IsSimple)
833  return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies);
834 
835  // Iterate through all the unique predecessors and tail-duplicate this
836  // block into them, if possible. Copying the list ahead of time also
837  // avoids trouble with the predecessor list reallocating.
838  bool Changed = false;
840  if (CandidatePtr)
841  Preds.insert(CandidatePtr->begin(), CandidatePtr->end());
842  else
843  Preds.insert(TailBB->pred_begin(), TailBB->pred_end());
844 
845  for (MachineBasicBlock *PredBB : Preds) {
846  assert(TailBB != PredBB &&
847  "Single-block loop should have been rejected earlier!");
848 
849  if (!canTailDuplicate(TailBB, PredBB))
850  continue;
851 
852  // Don't duplicate into a fall-through predecessor (at least for now).
853  // If profile is available, findDuplicateCandidates can choose better
854  // fall-through predecessor.
855  if (!(MF->getFunction().hasProfileData() && LayoutMode)) {
856  bool IsLayoutSuccessor = false;
857  if (ForcedLayoutPred)
858  IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
859  else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
860  IsLayoutSuccessor = true;
861  if (IsLayoutSuccessor)
862  continue;
863  }
864 
865  LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
866  << "From Succ: " << *TailBB);
867 
868  TDBBs.push_back(PredBB);
869 
870  // Remove PredBB's unconditional branch.
871  TII->removeBranch(*PredBB);
872 
873  // Clone the contents of TailBB into PredBB.
876  for (MachineInstr &MI : llvm::make_early_inc_range(*TailBB)) {
877  if (MI.isPHI()) {
878  // Replace the uses of the def of the PHI with the register coming
879  // from PredBB.
880  processPHI(&MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
881  } else {
882  // Replace def of virtual registers with new registers, and update
883  // uses with PHI source register or the new registers.
884  duplicateInstruction(&MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
885  }
886  }
887  appendCopies(PredBB, CopyInfos, Copies);
888 
889  NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
890 
891  // Update the CFG.
892  PredBB->removeSuccessor(PredBB->succ_begin());
893  assert(PredBB->succ_empty() &&
894  "TailDuplicate called on block with multiple successors!");
895  for (MachineBasicBlock *Succ : TailBB->successors())
896  PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ));
897 
898  // Update branches in pred to jump to tail's layout successor if needed.
899  if (ShouldUpdateTerminators)
900  PredBB->updateTerminator(TailBB->getNextNode());
901 
902  Changed = true;
903  ++NumTailDups;
904  }
905 
906  // If TailBB was duplicated into all its predecessors except for the prior
907  // block, which falls through unconditionally, move the contents of this
908  // block into the prior block.
909  MachineBasicBlock *PrevBB = ForcedLayoutPred;
910  if (!PrevBB)
911  PrevBB = &*std::prev(TailBB->getIterator());
912  MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
914  // This has to check PrevBB->succ_size() because EH edges are ignored by
915  // analyzeBranch.
916  if (PrevBB->succ_size() == 1 &&
917  // Layout preds are not always CFG preds. Check.
918  *PrevBB->succ_begin() == TailBB &&
919  !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) &&
920  PriorCond.empty() &&
921  (!PriorTBB || PriorTBB == TailBB) &&
922  TailBB->pred_size() == 1 &&
923  !TailBB->hasAddressTaken()) {
924  LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
925  << "From MBB: " << *TailBB);
926  // There may be a branch to the layout successor. This is unlikely but it
927  // happens. The correct thing to do is to remove the branch before
928  // duplicating the instructions in all cases.
929  bool RemovedBranches = TII->removeBranch(*PrevBB) != 0;
930 
931  // If there are still tail instructions, abort the merge
932  if (PrevBB->getFirstTerminator() == PrevBB->end()) {
933  if (PreRegAlloc) {
936  MachineBasicBlock::iterator I = TailBB->begin();
937  // Process PHI instructions first.
938  while (I != TailBB->end() && I->isPHI()) {
939  // Replace the uses of the def of the PHI with the register coming
940  // from PredBB.
941  MachineInstr *MI = &*I++;
942  processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi,
943  true);
944  }
945 
946  // Now copy the non-PHI instructions.
947  while (I != TailBB->end()) {
948  // Replace def of virtual registers with new registers, and update
949  // uses with PHI source register or the new registers.
950  MachineInstr *MI = &*I++;
951  assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
952  duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
953  MI->eraseFromParent();
954  }
955  appendCopies(PrevBB, CopyInfos, Copies);
956  } else {
957  TII->removeBranch(*PrevBB);
958  // No PHIs to worry about, just splice the instructions over.
959  PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
960  }
961  PrevBB->removeSuccessor(PrevBB->succ_begin());
962  assert(PrevBB->succ_empty());
963  PrevBB->transferSuccessors(TailBB);
964 
965  // Update branches in PrevBB based on Tail's layout successor.
966  if (ShouldUpdateTerminators)
967  PrevBB->updateTerminator(TailBB->getNextNode());
968 
969  TDBBs.push_back(PrevBB);
970  Changed = true;
971  } else {
972  LLVM_DEBUG(dbgs() << "Abort merging blocks, the predecessor still "
973  "contains terminator instructions");
974  // Return early if no changes were made
975  if (!Changed)
976  return RemovedBranches;
977  }
978  Changed |= RemovedBranches;
979  }
980 
981  // If this is after register allocation, there are no phis to fix.
982  if (!PreRegAlloc)
983  return Changed;
984 
985  // If we made no changes so far, we are safe.
986  if (!Changed)
987  return Changed;
988 
989  // Handle the nasty case in that we duplicated a block that is part of a loop
990  // into some but not all of its predecessors. For example:
991  // 1 -> 2 <-> 3 |
992  // \ |
993  // \---> rest |
994  // if we duplicate 2 into 1 but not into 3, we end up with
995  // 12 -> 3 <-> 2 -> rest |
996  // \ / |
997  // \----->-----/ |
998  // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced
999  // with a phi in 3 (which now dominates 2).
1000  // What we do here is introduce a copy in 3 of the register defined by the
1001  // phi, just like when we are duplicating 2 into 3, but we don't copy any
1002  // real instructions or remove the 3 -> 2 edge from the phi in 2.
1003  for (MachineBasicBlock *PredBB : Preds) {
1004  if (is_contained(TDBBs, PredBB))
1005  continue;
1006 
1007  // EH edges
1008  if (PredBB->succ_size() != 1)
1009  continue;
1010 
1013  MachineBasicBlock::iterator I = TailBB->begin();
1014  // Process PHI instructions first.
1015  while (I != TailBB->end() && I->isPHI()) {
1016  // Replace the uses of the def of the PHI with the register coming
1017  // from PredBB.
1018  MachineInstr *MI = &*I++;
1019  processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
1020  }
1021  appendCopies(PredBB, CopyInfos, Copies);
1022  }
1023 
1024  return Changed;
1025 }
1026 
1027 /// At the end of the block \p MBB generate COPY instructions between registers
1028 /// described by \p CopyInfos. Append resulting instructions to \p Copies.
1029 void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
1030  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
1033  const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
1034  for (auto &CI : CopyInfos) {
1035  auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
1036  .addReg(CI.second.Reg, 0, CI.second.SubReg);
1037  Copies.push_back(C);
1038  }
1039 }
1040 
1041 /// Remove the specified dead machine basic block from the function, updating
1042 /// the CFG.
1043 void TailDuplicator::removeDeadBlock(
1045  function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
1046  assert(MBB->pred_empty() && "MBB must be dead!");
1047  LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
1048 
1049  MachineFunction *MF = MBB->getParent();
1050  // Update the call site info.
1051  for (const MachineInstr &MI : *MBB)
1052  if (MI.shouldUpdateCallSiteInfo())
1053  MF->eraseCallSiteInfo(&MI);
1054 
1055  if (RemovalCallback)
1056  (*RemovalCallback)(MBB);
1057 
1058  // Remove all successors.
1059  while (!MBB->succ_empty())
1060  MBB->removeSuccessor(MBB->succ_end() - 1);
1061 
1062  // Remove the block.
1063  MBB->eraseFromParent();
1064 }
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:105
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
MachineSSAUpdater.h
Reg
unsigned Reg
Definition: MachineSink.cpp:1558
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:1375
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:555
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:301
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:480
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:698
llvm::TailDuplicator::isSimpleBB
static bool isSimpleBB(MachineBasicBlock *TailBB)
True if this BB has only one unconditional jump.
Definition: TailDuplicator.cpp:685
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:750
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:644
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:680
getPHISrcRegOpIdx
static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB)
Definition: TailDuplicator.cpp:312
TargetMachine.h
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:24
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:912
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:1334
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:398
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:585
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:634
llvm::cl::opt
Definition: CommandLine.h:1432
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:299
VI
@ VI
Definition: SIInstrInfo.cpp:7721
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:696
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:441
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:593
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:1665
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:965
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:234
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:241
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:260
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:282
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:417
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:1414
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
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:869
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:661
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:811
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:600
getRegsUsedByPHIs
static void getRegsUsedByPHIs(const MachineBasicBlock &BB, DenseSet< Register > *UsedByPhi)
Definition: TailDuplicator.cpp:322
llvm::MachineBasicBlock::removeSuccessor
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:788
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:627
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:292
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:916
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:794
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:412
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:645
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:274