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