LLVM  13.0.0git
PHIElimination.cpp
Go to the documentation of this file.
1 //===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
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 pass eliminates machine instruction PHI nodes by inserting copy
10 // instructions. This destroys SSA information, but is the desired input for
11 // some register allocators.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "PHIEliminationUtils.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/LoopInfo.h"
39 #include "llvm/Pass.h"
41 #include "llvm/Support/Debug.h"
43 #include <cassert>
44 #include <iterator>
45 #include <utility>
46 
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "phi-node-elimination"
50 
51 static cl::opt<bool>
52 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
53  cl::Hidden, cl::desc("Disable critical edge splitting "
54  "during PHI elimination"));
55 
56 static cl::opt<bool>
57 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
58  cl::Hidden, cl::desc("Split all critical edges during "
59  "PHI elimination"));
60 
62  "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
63  cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
64 
65 namespace {
66 
67  class PHIElimination : public MachineFunctionPass {
68  MachineRegisterInfo *MRI; // Machine register information
69  LiveVariables *LV;
70  LiveIntervals *LIS;
71 
72  public:
73  static char ID; // Pass identification, replacement for typeid
74 
75  PHIElimination() : MachineFunctionPass(ID) {
77  }
78 
79  bool runOnMachineFunction(MachineFunction &MF) override;
80  void getAnalysisUsage(AnalysisUsage &AU) const override;
81 
82  private:
83  /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
84  /// in predecessor basic blocks.
85  bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
86 
87  void LowerPHINode(MachineBasicBlock &MBB,
88  MachineBasicBlock::iterator LastPHIIt);
89 
90  /// analyzePHINodes - Gather information about the PHI nodes in
91  /// here. In particular, we want to map the number of uses of a virtual
92  /// register which is used in a PHI node. We map that to the BB the
93  /// vreg is coming from. This is used later to determine when the vreg
94  /// is killed in the BB.
95  void analyzePHINodes(const MachineFunction& MF);
96 
97  /// Split critical edges where necessary for good coalescer performance.
98  bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
99  MachineLoopInfo *MLI,
100  std::vector<SparseBitVector<>> *LiveInSets);
101 
102  // These functions are temporary abstractions around LiveVariables and
103  // LiveIntervals, so they can go away when LiveVariables does.
104  bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);
105  bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);
106 
107  using BBVRegPair = std::pair<unsigned, Register>;
108  using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
109 
110  VRegPHIUse VRegPHIUseCount;
111 
112  // Defs of PHI sources which are implicit_def.
114 
115  // Map reusable lowered PHI node -> incoming join register.
116  using LoweredPHIMap =
118  LoweredPHIMap LoweredPHIs;
119  };
120 
121 } // end anonymous namespace
122 
123 STATISTIC(NumLowered, "Number of phis lowered");
124 STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
125 STATISTIC(NumReused, "Number of reused lowered phis");
126 
127 char PHIElimination::ID = 0;
128 
130 
131 INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
132  "Eliminate PHI nodes for register allocation",
133  false, false)
136  "Eliminate PHI nodes for register allocation", false, false)
137 
138 void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
139  AU.addUsedIfAvailable<LiveVariables>();
140  AU.addPreserved<LiveVariables>();
141  AU.addPreserved<SlotIndexes>();
142  AU.addPreserved<LiveIntervals>();
143  AU.addPreserved<MachineDominatorTree>();
144  AU.addPreserved<MachineLoopInfo>();
146 }
147 
148 bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
149  MRI = &MF.getRegInfo();
150  LV = getAnalysisIfAvailable<LiveVariables>();
151  LIS = getAnalysisIfAvailable<LiveIntervals>();
152 
153  bool Changed = false;
154 
155  // Split critical edges to help the coalescer.
156  if (!DisableEdgeSplitting && (LV || LIS)) {
157  // A set of live-in regs for each MBB which is used to update LV
158  // efficiently also with large functions.
159  std::vector<SparseBitVector<>> LiveInSets;
160  if (LV) {
161  LiveInSets.resize(MF.size());
162  for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
163  // Set the bit for this register for each MBB where it is
164  // live-through or live-in (killed).
165  unsigned VirtReg = Register::index2VirtReg(Index);
166  MachineInstr *DefMI = MRI->getVRegDef(VirtReg);
167  if (!DefMI)
168  continue;
169  LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);
170  SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();
171  SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();
172  while (AliveBlockItr != EndItr) {
173  unsigned BlockNum = *(AliveBlockItr++);
174  LiveInSets[BlockNum].set(Index);
175  }
176  // The register is live into an MBB in which it is killed but not
177  // defined. See comment for VarInfo in LiveVariables.h.
178  MachineBasicBlock *DefMBB = DefMI->getParent();
179  if (VI.Kills.size() > 1 ||
180  (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
181  for (auto *MI : VI.Kills)
182  LiveInSets[MI->getParent()->getNumber()].set(Index);
183  }
184  }
185 
186  MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
187  for (auto &MBB : MF)
188  Changed |= SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr));
189  }
190 
191  // This pass takes the function out of SSA form.
192  MRI->leaveSSA();
193 
194  // Populate VRegPHIUseCount
195  analyzePHINodes(MF);
196 
197  // Eliminate PHI instructions by inserting copies into predecessor blocks.
198  for (auto &MBB : MF)
199  Changed |= EliminatePHINodes(MF, MBB);
200 
201  // Remove dead IMPLICIT_DEF instructions.
202  for (MachineInstr *DefMI : ImpDefs) {
203  Register DefReg = DefMI->getOperand(0).getReg();
204  if (MRI->use_nodbg_empty(DefReg)) {
205  if (LIS)
206  LIS->RemoveMachineInstrFromMaps(*DefMI);
208  }
209  }
210 
211  // Clean up the lowered PHI instructions.
212  for (auto &I : LoweredPHIs) {
213  if (LIS)
214  LIS->RemoveMachineInstrFromMaps(*I.first);
215  MF.DeleteMachineInstr(I.first);
216  }
217 
218  // TODO: we should use the incremental DomTree updater here.
219  if (Changed)
220  if (auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>())
221  MDT->getBase().recalculate(MF);
222 
223  LoweredPHIs.clear();
224  ImpDefs.clear();
225  VRegPHIUseCount.clear();
226 
227  MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
228 
229  return Changed;
230 }
231 
232 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
233 /// predecessor basic blocks.
234 bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
236  if (MBB.empty() || !MBB.front().isPHI())
237  return false; // Quick exit for basic blocks without PHIs.
238 
239  // Get an iterator to the last PHI node.
240  MachineBasicBlock::iterator LastPHIIt =
241  std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
242 
243  while (MBB.front().isPHI())
244  LowerPHINode(MBB, LastPHIIt);
245 
246  return true;
247 }
248 
249 /// Return true if all defs of VirtReg are implicit-defs.
250 /// This includes registers with no defs.
251 static bool isImplicitlyDefined(unsigned VirtReg,
252  const MachineRegisterInfo &MRI) {
253  for (MachineInstr &DI : MRI.def_instructions(VirtReg))
254  if (!DI.isImplicitDef())
255  return false;
256  return true;
257 }
258 
259 /// Return true if all sources of the phi node are implicit_def's, or undef's.
260 static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
261  const MachineRegisterInfo &MRI) {
262  for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
263  const MachineOperand &MO = MPhi.getOperand(I);
264  if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
265  return false;
266  }
267  return true;
268 }
269 /// LowerPHINode - Lower the PHI node at the top of the specified block.
270 void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
271  MachineBasicBlock::iterator LastPHIIt) {
272  ++NumLowered;
273 
274  MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
275 
276  // Unlink the PHI node from the basic block, but don't delete the PHI yet.
277  MachineInstr *MPhi = MBB.remove(&*MBB.begin());
278 
279  unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
280  Register DestReg = MPhi->getOperand(0).getReg();
281  assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
282  bool isDead = MPhi->getOperand(0).isDead();
283 
284  // Create a new register for the incoming PHI arguments.
285  MachineFunction &MF = *MBB.getParent();
286  unsigned IncomingReg = 0;
287  bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
288 
289  // Insert a register to register copy at the top of the current block (but
290  // after any remaining phi nodes) which copies the new incoming register
291  // into the phi node destination.
292  MachineInstr *PHICopy = nullptr;
294  if (allPhiOperandsUndefined(*MPhi, *MRI))
295  // If all sources of a PHI node are implicit_def or undef uses, just emit an
296  // implicit_def instead of a copy.
297  PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
298  TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
299  else {
300  // Can we reuse an earlier PHI node? This only happens for critical edges,
301  // typically those created by tail duplication.
302  unsigned &entry = LoweredPHIs[MPhi];
303  if (entry) {
304  // An identical PHI node was already lowered. Reuse the incoming register.
305  IncomingReg = entry;
306  reusedIncoming = true;
307  ++NumReused;
308  LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
309  << *MPhi);
310  } else {
311  const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
312  entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
313  }
314  // Give the target possiblity to handle special cases fallthrough otherwise
315  PHICopy = TII->createPHIDestinationCopy(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
316  IncomingReg, DestReg);
317  }
318 
319  // Update live variable information if there is any.
320  if (LV) {
321  if (IncomingReg) {
322  LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
323 
324  // Increment use count of the newly created virtual register.
325  LV->setPHIJoin(IncomingReg);
326 
327  MachineInstr *OldKill = nullptr;
328  bool IsPHICopyAfterOldKill = false;
329 
330  if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
331  // Calculate whether the PHICopy is after the OldKill.
332  // In general, the PHICopy is inserted as the first non-phi instruction
333  // by default, so it's before the OldKill. But some Target hooks for
334  // createPHIDestinationCopy() may modify the default insert position of
335  // PHICopy.
336  for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
337  I != E; ++I) {
338  if (I == PHICopy)
339  break;
340 
341  if (I == OldKill) {
342  IsPHICopyAfterOldKill = true;
343  break;
344  }
345  }
346  }
347 
348  // When we are reusing the incoming register and it has been marked killed
349  // by OldKill, if the PHICopy is after the OldKill, we should remove the
350  // killed flag from OldKill.
351  if (IsPHICopyAfterOldKill) {
352  LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
353  LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
354  LLVM_DEBUG(MBB.dump());
355  }
356 
357  // Add information to LiveVariables to know that the first used incoming
358  // value or the resued incoming value whose PHICopy is after the OldKIll
359  // is killed. Note that because the value is defined in several places
360  // (once each for each incoming block), the "def" block and instruction
361  // fields for the VarInfo is not filled in.
362  if (!OldKill || IsPHICopyAfterOldKill)
363  LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
364  }
365 
366  // Since we are going to be deleting the PHI node, if it is the last use of
367  // any registers, or if the value itself is dead, we need to move this
368  // information over to the new copy we just inserted.
369  LV->removeVirtualRegistersKilled(*MPhi);
370 
371  // If the result is dead, update LV.
372  if (isDead) {
373  LV->addVirtualRegisterDead(DestReg, *PHICopy);
374  LV->removeVirtualRegisterDead(DestReg, *MPhi);
375  }
376  }
377 
378  // Update LiveIntervals for the new copy or implicit def.
379  if (LIS) {
380  SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
381 
382  SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
383  if (IncomingReg) {
384  // Add the region from the beginning of MBB to the copy instruction to
385  // IncomingReg's live interval.
386  LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
387  VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
388  if (!IncomingVNI)
389  IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
390  LIS->getVNInfoAllocator());
391  IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
392  DestCopyIndex.getRegSlot(),
393  IncomingVNI));
394  }
395 
396  LiveInterval &DestLI = LIS->getInterval(DestReg);
397  assert(!DestLI.empty() && "PHIs should have nonempty LiveIntervals.");
398  if (DestLI.endIndex().isDead()) {
399  // A dead PHI's live range begins and ends at the start of the MBB, but
400  // the lowered copy, which will still be dead, needs to begin and end at
401  // the copy instruction.
402  VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
403  assert(OrigDestVNI && "PHI destination should be live at block entry.");
404  DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
405  DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
406  LIS->getVNInfoAllocator());
407  DestLI.removeValNo(OrigDestVNI);
408  } else {
409  // Otherwise, remove the region from the beginning of MBB to the copy
410  // instruction from DestReg's live interval.
411  DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
412  VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
413  assert(DestVNI && "PHI destination should be live at its definition.");
414  DestVNI->def = DestCopyIndex.getRegSlot();
415  }
416  }
417 
418  // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
419  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
420  --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
421  MPhi->getOperand(i).getReg())];
422 
423  // Now loop over all of the incoming arguments, changing them to copy into the
424  // IncomingReg register in the corresponding predecessor basic block.
425  SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
426  for (int i = NumSrcs - 1; i >= 0; --i) {
427  Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
428  unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
429  bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
430  isImplicitlyDefined(SrcReg, *MRI);
432  "Machine PHI Operands must all be virtual registers!");
433 
434  // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
435  // path the PHI.
436  MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
437 
438  // Check to make sure we haven't already emitted the copy for this block.
439  // This can happen because PHI nodes may have multiple entries for the same
440  // basic block.
441  if (!MBBsInsertedInto.insert(&opBlock).second)
442  continue; // If the copy has already been emitted, we're done.
443 
444  MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
445  if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
446  assert(SrcRegDef->getOperand(0).isReg() &&
447  SrcRegDef->getOperand(0).isDef() &&
448  "Expected operand 0 to be a reg def!");
449  // Now that the PHI's use has been removed (as the instruction was
450  // removed) there should be no other uses of the SrcReg.
451  assert(MRI->use_empty(SrcReg) &&
452  "Expected a single use from UnspillableTerminator");
453  SrcRegDef->getOperand(0).setReg(IncomingReg);
454  continue;
455  }
456 
457  // Find a safe location to insert the copy, this may be the first terminator
458  // in the block (or end()).
459  MachineBasicBlock::iterator InsertPos =
460  findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
461 
462  // Insert the copy.
463  MachineInstr *NewSrcInstr = nullptr;
464  if (!reusedIncoming && IncomingReg) {
465  if (SrcUndef) {
466  // The source register is undefined, so there is no need for a real
467  // COPY, but we still need to ensure joint dominance by defs.
468  // Insert an IMPLICIT_DEF instruction.
469  NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
470  TII->get(TargetOpcode::IMPLICIT_DEF),
471  IncomingReg);
472 
473  // Clean up the old implicit-def, if there even was one.
474  if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
475  if (DefMI->isImplicitDef())
476  ImpDefs.insert(DefMI);
477  } else {
478  NewSrcInstr =
479  TII->createPHISourceCopy(opBlock, InsertPos, MPhi->getDebugLoc(),
480  SrcReg, SrcSubReg, IncomingReg);
481  }
482  }
483 
484  // We only need to update the LiveVariables kill of SrcReg if this was the
485  // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
486  // out of the predecessor. We can also ignore undef sources.
487  if (LV && !SrcUndef &&
488  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
489  !LV->isLiveOut(SrcReg, opBlock)) {
490  // We want to be able to insert a kill of the register if this PHI (aka,
491  // the copy we just inserted) is the last use of the source value. Live
492  // variable analysis conservatively handles this by saying that the value
493  // is live until the end of the block the PHI entry lives in. If the value
494  // really is dead at the PHI copy, there will be no successor blocks which
495  // have the value live-in.
496 
497  // Okay, if we now know that the value is not live out of the block, we
498  // can add a kill marker in this block saying that it kills the incoming
499  // value!
500 
501  // In our final twist, we have to decide which instruction kills the
502  // register. In most cases this is the copy, however, terminator
503  // instructions at the end of the block may also use the value. In this
504  // case, we should mark the last such terminator as being the killing
505  // block, not the copy.
506  MachineBasicBlock::iterator KillInst = opBlock.end();
507  MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
508  for (MachineBasicBlock::iterator Term = FirstTerm;
509  Term != opBlock.end(); ++Term) {
510  if (Term->readsRegister(SrcReg))
511  KillInst = Term;
512  }
513 
514  if (KillInst == opBlock.end()) {
515  // No terminator uses the register.
516 
517  if (reusedIncoming || !IncomingReg) {
518  // We may have to rewind a bit if we didn't insert a copy this time.
519  KillInst = FirstTerm;
520  while (KillInst != opBlock.begin()) {
521  --KillInst;
522  if (KillInst->isDebugInstr())
523  continue;
524  if (KillInst->readsRegister(SrcReg))
525  break;
526  }
527  } else {
528  // We just inserted this copy.
529  KillInst = NewSrcInstr;
530  }
531  }
532  assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
533 
534  // Finally, mark it killed.
535  LV->addVirtualRegisterKilled(SrcReg, *KillInst);
536 
537  // This vreg no longer lives all of the way through opBlock.
538  unsigned opBlockNum = opBlock.getNumber();
539  LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
540  }
541 
542  if (LIS) {
543  if (NewSrcInstr) {
544  LIS->InsertMachineInstrInMaps(*NewSrcInstr);
545  LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
546  }
547 
548  if (!SrcUndef &&
549  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
550  LiveInterval &SrcLI = LIS->getInterval(SrcReg);
551 
552  bool isLiveOut = false;
553  for (MachineBasicBlock *Succ : opBlock.successors()) {
554  SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
555  VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
556 
557  // Definitions by other PHIs are not truly live-in for our purposes.
558  if (VNI && VNI->def != startIdx) {
559  isLiveOut = true;
560  break;
561  }
562  }
563 
564  if (!isLiveOut) {
565  MachineBasicBlock::iterator KillInst = opBlock.end();
566  MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
567  for (MachineBasicBlock::iterator Term = FirstTerm;
568  Term != opBlock.end(); ++Term) {
569  if (Term->readsRegister(SrcReg))
570  KillInst = Term;
571  }
572 
573  if (KillInst == opBlock.end()) {
574  // No terminator uses the register.
575 
576  if (reusedIncoming || !IncomingReg) {
577  // We may have to rewind a bit if we didn't just insert a copy.
578  KillInst = FirstTerm;
579  while (KillInst != opBlock.begin()) {
580  --KillInst;
581  if (KillInst->isDebugInstr())
582  continue;
583  if (KillInst->readsRegister(SrcReg))
584  break;
585  }
586  } else {
587  // We just inserted this copy.
588  KillInst = std::prev(InsertPos);
589  }
590  }
591  assert(KillInst->readsRegister(SrcReg) &&
592  "Cannot find kill instruction");
593 
594  SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
595  SrcLI.removeSegment(LastUseIndex.getRegSlot(),
596  LIS->getMBBEndIdx(&opBlock));
597  }
598  }
599  }
600  }
601 
602  // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
603  if (reusedIncoming || !IncomingReg) {
604  if (LIS)
605  LIS->RemoveMachineInstrFromMaps(*MPhi);
606  MF.DeleteMachineInstr(MPhi);
607  }
608 }
609 
610 /// analyzePHINodes - Gather information about the PHI nodes in here. In
611 /// particular, we want to map the number of uses of a virtual register which is
612 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
613 /// used later to determine when the vreg is killed in the BB.
614 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
615  for (const auto &MBB : MF)
616  for (const auto &BBI : MBB) {
617  if (!BBI.isPHI())
618  break;
619  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
620  ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
621  BBI.getOperand(i).getReg())];
622  }
623 }
624 
625 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
627  MachineLoopInfo *MLI,
628  std::vector<SparseBitVector<>> *LiveInSets) {
629  if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
630  return false; // Quick exit for basic blocks without PHIs.
631 
632  const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
633  bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
634 
635  bool Changed = false;
636  for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
637  BBI != BBE && BBI->isPHI(); ++BBI) {
638  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
639  Register Reg = BBI->getOperand(i).getReg();
640  MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
641  // Is there a critical edge from PreMBB to MBB?
642  if (PreMBB->succ_size() == 1)
643  continue;
644 
645  // Avoid splitting backedges of loops. It would introduce small
646  // out-of-line blocks into the loop which is very bad for code placement.
647  if (PreMBB == &MBB && !SplitAllCriticalEdges)
648  continue;
649  const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
650  if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
651  continue;
652 
653  // LV doesn't consider a phi use live-out, so isLiveOut only returns true
654  // when the source register is live-out for some other reason than a phi
655  // use. That means the copy we will insert in PreMBB won't be a kill, and
656  // there is a risk it may not be coalesced away.
657  //
658  // If the copy would be a kill, there is no need to split the edge.
659  bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
660  if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
661  continue;
662  if (ShouldSplit) {
663  LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
664  << printMBBReference(*PreMBB) << " -> "
665  << printMBBReference(MBB) << ": " << *BBI);
666  }
667 
668  // If Reg is not live-in to MBB, it means it must be live-in to some
669  // other PreMBB successor, and we can avoid the interference by splitting
670  // the edge.
671  //
672  // If Reg *is* live-in to MBB, the interference is inevitable and a copy
673  // is likely to be left after coalescing. If we are looking at a loop
674  // exiting edge, split it so we won't insert code in the loop, otherwise
675  // don't bother.
676  ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
677 
678  // Check for a loop exiting edge.
679  if (!ShouldSplit && CurLoop != PreLoop) {
680  LLVM_DEBUG({
681  dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
682  if (PreLoop)
683  dbgs() << "PreLoop: " << *PreLoop;
684  if (CurLoop)
685  dbgs() << "CurLoop: " << *CurLoop;
686  });
687  // This edge could be entering a loop, exiting a loop, or it could be
688  // both: Jumping directly form one loop to the header of a sibling
689  // loop.
690  // Split unless this edge is entering CurLoop from an outer loop.
691  ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
692  }
693  if (!ShouldSplit && !SplitAllCriticalEdges)
694  continue;
695  if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
696  LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
697  continue;
698  }
699  Changed = true;
700  ++NumCriticalEdgesSplit;
701  }
702  }
703  return Changed;
704 }
705 
706 bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
707  assert((LV || LIS) &&
708  "isLiveIn() requires either LiveVariables or LiveIntervals");
709  if (LIS)
710  return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
711  else
712  return LV->isLiveIn(Reg, *MBB);
713 }
714 
715 bool PHIElimination::isLiveOutPastPHIs(Register Reg,
716  const MachineBasicBlock *MBB) {
717  assert((LV || LIS) &&
718  "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
719  // LiveVariables considers uses in PHIs to be in the predecessor basic block,
720  // so that a register used only in a PHI is not live out of the block. In
721  // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
722  // in the predecessor basic block, so that a register used only in a PHI is live
723  // out of the block.
724  if (LIS) {
725  const LiveInterval &LI = LIS->getInterval(Reg);
726  for (const MachineBasicBlock *SI : MBB->successors())
727  if (LI.liveAt(LIS->getMBBStartIdx(SI)))
728  return true;
729  return false;
730  } else {
731  return LV->isLiveOut(Reg, *MBB);
732  }
733 }
i
i
Definition: README.txt:29
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:344
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
MachineInstr.h
llvm
Definition: AllocatorList.h:23
llvm::MachineInstr::isImplicitDef
bool isImplicitDef() const
Definition: MachineInstr.h:1248
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:374
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:124
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
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:92
llvm::PHIEliminationID
char & PHIEliminationID
PHIElimination - This pass eliminates machine instruction PHI nodes by inserting copy instructions.
Definition: PHIElimination.cpp:129
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
allPhiOperandsUndefined
static bool allPhiOperandsUndefined(const MachineInstr &MPhi, const MachineRegisterInfo &MRI)
Return true if all sources of the phi node are implicit_def's, or undef's.
Definition: PHIElimination.cpp:260
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::VNInfo::def
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
DenseMap.h
TargetInstrInfo.h
isImplicitlyDefined
static bool isImplicitlyDefined(unsigned VirtReg, const MachineRegisterInfo &MRI)
Return true if all defs of VirtReg are implicit-defs.
Definition: PHIElimination.cpp:251
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:757
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::Register::index2VirtReg
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
DEBUG_TYPE
#define DEBUG_TYPE
Definition: PHIElimination.cpp:49
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
MachineRegisterInfo.h
llvm::MachineBasicBlock::dump
void dump() const
Definition: MachineBasicBlock.cpp:292
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
DisableEdgeSplitting
static cl::opt< bool > DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), cl::Hidden, cl::desc("Disable critical edge splitting " "during PHI elimination"))
isLiveOut
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
Definition: SIOptimizeExecMasking.cpp:286
CommandLine.h
TargetLowering.h
PHIEliminationUtils.h
llvm::SparseBitVector
Definition: SparseBitVector.h:255
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:565
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
MachineLoopInfo.h
llvm::LiveRange::liveAt
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:393
llvm::MachineBasicBlock::remove
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
Definition: MachineBasicBlock.h:839
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LiveVariables::VarInfo
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:79
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:488
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:548
llvm::MachineFunction::DeleteMachineInstr
void DeleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
Definition: MachineFunction.cpp:393
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::initializePHIEliminationPass
void initializePHIEliminationPass(PassRegistry &)
LiveVariables.h
false
Definition: StackSlotColoring.cpp:142
TargetOpcodes.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MachineFunction::size
unsigned size() const
Definition: MachineFunction.h:747
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::SlotIndex::getDeadSlot
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:259
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
SmallPtrSet.h
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:400
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::MachineRegisterInfo::use_empty
bool use_empty(Register RegNo) const
use_empty - Return true if there are no instructions using the specified register.
Definition: MachineRegisterInfo.h:506
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
LoopInfo.h
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:555
llvm::cl::opt< bool >
allocation
Eliminate PHI nodes for register allocation
Definition: PHIElimination.cpp:136
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:418
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
VI
@ VI
Definition: SIInstrInfo.cpp:7343
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:392
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE, "Eliminate PHI nodes for register allocation", false, false) INITIALIZE_PASS_END(PHIElimination
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:318
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
LiveIntervals.h
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::MachineBasicBlock::SkipPHIsAndLabels
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
Definition: MachineBasicBlock.cpp:209
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::nodes
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Definition: GraphTraits.h:108
llvm::MachineRegisterInfo::def_instructions
iterator_range< def_instr_iterator > def_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:405
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:382
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:323
TargetPassConfig.h
MachineFunctionPass.h
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
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:1243
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:357
register
should just be implemented with a CLZ instruction Since there are other e that share this it would be best to implement this in a target independent as zero is the default value for the binary encoder e add r0 add r5 Register operands should be distinct That when the encoding does not require two syntactical operands to refer to the same register
Definition: README.txt:726
llvm::SlotIndex::getRegSlot
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
Definition: SlotIndexes.h:254
llvm::MachineFunction
Definition: MachineFunction.h:227
llvm::MachineRegisterInfo::use_nodbg_empty
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
Definition: MachineRegisterInfo.h:566
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:239
llvm::LiveRange::createDeadDef
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
Definition: LiveInterval.cpp:370
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:549
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:965
llvm::SparseBitVector::iterator
SparseBitVectorIterator iterator
Definition: SparseBitVector.h:441
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:435
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:372
llvm::findPHICopyInsertPoint
MachineBasicBlock::iterator findPHICopyInsertPoint(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, unsigned SrcReg)
findPHICopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg when following the CFG...
Definition: PHIEliminationUtils.cpp:21
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
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:362
llvm::LiveRange::endIndex
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:384
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunctionProperties::Property::NoPHIs
@ NoPHIs
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:247
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::LiveRange::getVNInfoAt
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:413
llvm::LiveRange::removeSegment
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
Definition: LiveInterval.cpp:583
LiveInterval.h
llvm::SplitAllCriticalEdges
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
Definition: BasicBlockUtils.cpp:752
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:329
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:55
llvm::MachineRegisterInfo::leaveSSA
void leaveSSA()
Definition: MachineRegisterInfo.h:191
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:101
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:481
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:240
MachineOperand.h
NoPhiElimLiveOutEarlyExit
static cl::opt< bool > NoPhiElimLiveOutEarlyExit("no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden, cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."))
llvm::LiveVariables
Definition: LiveVariables.h:46
llvm::LiveRange::removeValNo
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
Definition: LiveInterval.cpp:632
SlotIndexes.h
llvm::cl::desc
Definition: CommandLine.h:411
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::SlotIndex::isDead
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
Definition: SlotIndexes.h:236
MachineFunction.h
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:110
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:677
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::MachineBasicBlock::SplitCriticalEdge
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, std::vector< SparseBitVector<>> *LiveInSets=nullptr)
Split the critical edge from this block to the given successor block, and return the newly created bl...
Definition: MachineBasicBlock.cpp:1029
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:339
MachineDominators.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38