LLVM  14.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  if (MPhi->peekDebugInstrNum()) {
320  // If referred to by debug-info, store where this PHI was.
321  MachineFunction *MF = MBB.getParent();
322  unsigned ID = MPhi->peekDebugInstrNum();
323  auto P = MachineFunction::DebugPHIRegallocPos(&MBB, IncomingReg, 0);
324  auto Res = MF->DebugPHIPositions.insert({ID, P});
325  assert(Res.second);
326  (void)Res;
327  }
328 
329  // Update live variable information if there is any.
330  if (LV) {
331  if (IncomingReg) {
332  LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
333 
334  // Increment use count of the newly created virtual register.
335  LV->setPHIJoin(IncomingReg);
336 
337  MachineInstr *OldKill = nullptr;
338  bool IsPHICopyAfterOldKill = false;
339 
340  if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
341  // Calculate whether the PHICopy is after the OldKill.
342  // In general, the PHICopy is inserted as the first non-phi instruction
343  // by default, so it's before the OldKill. But some Target hooks for
344  // createPHIDestinationCopy() may modify the default insert position of
345  // PHICopy.
346  for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
347  I != E; ++I) {
348  if (I == PHICopy)
349  break;
350 
351  if (I == OldKill) {
352  IsPHICopyAfterOldKill = true;
353  break;
354  }
355  }
356  }
357 
358  // When we are reusing the incoming register and it has been marked killed
359  // by OldKill, if the PHICopy is after the OldKill, we should remove the
360  // killed flag from OldKill.
361  if (IsPHICopyAfterOldKill) {
362  LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
363  LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
364  LLVM_DEBUG(MBB.dump());
365  }
366 
367  // Add information to LiveVariables to know that the first used incoming
368  // value or the resued incoming value whose PHICopy is after the OldKIll
369  // is killed. Note that because the value is defined in several places
370  // (once each for each incoming block), the "def" block and instruction
371  // fields for the VarInfo is not filled in.
372  if (!OldKill || IsPHICopyAfterOldKill)
373  LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
374  }
375 
376  // Since we are going to be deleting the PHI node, if it is the last use of
377  // any registers, or if the value itself is dead, we need to move this
378  // information over to the new copy we just inserted.
379  LV->removeVirtualRegistersKilled(*MPhi);
380 
381  // If the result is dead, update LV.
382  if (isDead) {
383  LV->addVirtualRegisterDead(DestReg, *PHICopy);
384  LV->removeVirtualRegisterDead(DestReg, *MPhi);
385  }
386  }
387 
388  // Update LiveIntervals for the new copy or implicit def.
389  if (LIS) {
390  SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
391 
392  SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
393  if (IncomingReg) {
394  // Add the region from the beginning of MBB to the copy instruction to
395  // IncomingReg's live interval.
396  LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
397  VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
398  if (!IncomingVNI)
399  IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
400  LIS->getVNInfoAllocator());
401  IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
402  DestCopyIndex.getRegSlot(),
403  IncomingVNI));
404  }
405 
406  LiveInterval &DestLI = LIS->getInterval(DestReg);
407  assert(!DestLI.empty() && "PHIs should have nonempty LiveIntervals.");
408  if (DestLI.endIndex().isDead()) {
409  // A dead PHI's live range begins and ends at the start of the MBB, but
410  // the lowered copy, which will still be dead, needs to begin and end at
411  // the copy instruction.
412  VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
413  assert(OrigDestVNI && "PHI destination should be live at block entry.");
414  DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
415  DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
416  LIS->getVNInfoAllocator());
417  DestLI.removeValNo(OrigDestVNI);
418  } else {
419  // Otherwise, remove the region from the beginning of MBB to the copy
420  // instruction from DestReg's live interval.
421  DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
422  VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
423  assert(DestVNI && "PHI destination should be live at its definition.");
424  DestVNI->def = DestCopyIndex.getRegSlot();
425  }
426  }
427 
428  // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
429  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
430  --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
431  MPhi->getOperand(i).getReg())];
432 
433  // Now loop over all of the incoming arguments, changing them to copy into the
434  // IncomingReg register in the corresponding predecessor basic block.
435  SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
436  for (int i = NumSrcs - 1; i >= 0; --i) {
437  Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
438  unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
439  bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
440  isImplicitlyDefined(SrcReg, *MRI);
442  "Machine PHI Operands must all be virtual registers!");
443 
444  // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
445  // path the PHI.
446  MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
447 
448  // Check to make sure we haven't already emitted the copy for this block.
449  // This can happen because PHI nodes may have multiple entries for the same
450  // basic block.
451  if (!MBBsInsertedInto.insert(&opBlock).second)
452  continue; // If the copy has already been emitted, we're done.
453 
454  MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
455  if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
456  assert(SrcRegDef->getOperand(0).isReg() &&
457  SrcRegDef->getOperand(0).isDef() &&
458  "Expected operand 0 to be a reg def!");
459  // Now that the PHI's use has been removed (as the instruction was
460  // removed) there should be no other uses of the SrcReg.
461  assert(MRI->use_empty(SrcReg) &&
462  "Expected a single use from UnspillableTerminator");
463  SrcRegDef->getOperand(0).setReg(IncomingReg);
464  continue;
465  }
466 
467  // Find a safe location to insert the copy, this may be the first terminator
468  // in the block (or end()).
469  MachineBasicBlock::iterator InsertPos =
470  findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
471 
472  // Insert the copy.
473  MachineInstr *NewSrcInstr = nullptr;
474  if (!reusedIncoming && IncomingReg) {
475  if (SrcUndef) {
476  // The source register is undefined, so there is no need for a real
477  // COPY, but we still need to ensure joint dominance by defs.
478  // Insert an IMPLICIT_DEF instruction.
479  NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
480  TII->get(TargetOpcode::IMPLICIT_DEF),
481  IncomingReg);
482 
483  // Clean up the old implicit-def, if there even was one.
484  if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
485  if (DefMI->isImplicitDef())
486  ImpDefs.insert(DefMI);
487  } else {
488  // Delete the debug location, since the copy is inserted into a
489  // different basic block.
490  NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,
491  SrcReg, SrcSubReg, IncomingReg);
492  }
493  }
494 
495  // We only need to update the LiveVariables kill of SrcReg if this was the
496  // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
497  // out of the predecessor. We can also ignore undef sources.
498  if (LV && !SrcUndef &&
499  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
500  !LV->isLiveOut(SrcReg, opBlock)) {
501  // We want to be able to insert a kill of the register if this PHI (aka,
502  // the copy we just inserted) is the last use of the source value. Live
503  // variable analysis conservatively handles this by saying that the value
504  // is live until the end of the block the PHI entry lives in. If the value
505  // really is dead at the PHI copy, there will be no successor blocks which
506  // have the value live-in.
507 
508  // Okay, if we now know that the value is not live out of the block, we
509  // can add a kill marker in this block saying that it kills the incoming
510  // value!
511 
512  // In our final twist, we have to decide which instruction kills the
513  // register. In most cases this is the copy, however, terminator
514  // instructions at the end of the block may also use the value. In this
515  // case, we should mark the last such terminator as being the killing
516  // block, not the copy.
517  MachineBasicBlock::iterator KillInst = opBlock.end();
518  MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
519  for (MachineBasicBlock::iterator Term = FirstTerm;
520  Term != opBlock.end(); ++Term) {
521  if (Term->readsRegister(SrcReg))
522  KillInst = Term;
523  }
524 
525  if (KillInst == opBlock.end()) {
526  // No terminator uses the register.
527 
528  if (reusedIncoming || !IncomingReg) {
529  // We may have to rewind a bit if we didn't insert a copy this time.
530  KillInst = FirstTerm;
531  while (KillInst != opBlock.begin()) {
532  --KillInst;
533  if (KillInst->isDebugInstr())
534  continue;
535  if (KillInst->readsRegister(SrcReg))
536  break;
537  }
538  } else {
539  // We just inserted this copy.
540  KillInst = NewSrcInstr;
541  }
542  }
543  assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
544 
545  // Finally, mark it killed.
546  LV->addVirtualRegisterKilled(SrcReg, *KillInst);
547 
548  // This vreg no longer lives all of the way through opBlock.
549  unsigned opBlockNum = opBlock.getNumber();
550  LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
551  }
552 
553  if (LIS) {
554  if (NewSrcInstr) {
555  LIS->InsertMachineInstrInMaps(*NewSrcInstr);
556  LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
557  }
558 
559  if (!SrcUndef &&
560  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
561  LiveInterval &SrcLI = LIS->getInterval(SrcReg);
562 
563  bool isLiveOut = false;
564  for (MachineBasicBlock *Succ : opBlock.successors()) {
565  SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
566  VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
567 
568  // Definitions by other PHIs are not truly live-in for our purposes.
569  if (VNI && VNI->def != startIdx) {
570  isLiveOut = true;
571  break;
572  }
573  }
574 
575  if (!isLiveOut) {
576  MachineBasicBlock::iterator KillInst = opBlock.end();
577  MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
578  for (MachineBasicBlock::iterator Term = FirstTerm;
579  Term != opBlock.end(); ++Term) {
580  if (Term->readsRegister(SrcReg))
581  KillInst = Term;
582  }
583 
584  if (KillInst == opBlock.end()) {
585  // No terminator uses the register.
586 
587  if (reusedIncoming || !IncomingReg) {
588  // We may have to rewind a bit if we didn't just insert a copy.
589  KillInst = FirstTerm;
590  while (KillInst != opBlock.begin()) {
591  --KillInst;
592  if (KillInst->isDebugInstr())
593  continue;
594  if (KillInst->readsRegister(SrcReg))
595  break;
596  }
597  } else {
598  // We just inserted this copy.
599  KillInst = std::prev(InsertPos);
600  }
601  }
602  assert(KillInst->readsRegister(SrcReg) &&
603  "Cannot find kill instruction");
604 
605  SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
606  SrcLI.removeSegment(LastUseIndex.getRegSlot(),
607  LIS->getMBBEndIdx(&opBlock));
608  }
609  }
610  }
611  }
612 
613  // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
614  if (reusedIncoming || !IncomingReg) {
615  if (LIS)
616  LIS->RemoveMachineInstrFromMaps(*MPhi);
617  MF.DeleteMachineInstr(MPhi);
618  }
619 }
620 
621 /// analyzePHINodes - Gather information about the PHI nodes in here. In
622 /// particular, we want to map the number of uses of a virtual register which is
623 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
624 /// used later to determine when the vreg is killed in the BB.
625 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
626  for (const auto &MBB : MF)
627  for (const auto &BBI : MBB) {
628  if (!BBI.isPHI())
629  break;
630  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
631  ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
632  BBI.getOperand(i).getReg())];
633  }
634 }
635 
636 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
638  MachineLoopInfo *MLI,
639  std::vector<SparseBitVector<>> *LiveInSets) {
640  if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
641  return false; // Quick exit for basic blocks without PHIs.
642 
643  const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
644  bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
645 
646  bool Changed = false;
647  for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
648  BBI != BBE && BBI->isPHI(); ++BBI) {
649  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
650  Register Reg = BBI->getOperand(i).getReg();
651  MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
652  // Is there a critical edge from PreMBB to MBB?
653  if (PreMBB->succ_size() == 1)
654  continue;
655 
656  // Avoid splitting backedges of loops. It would introduce small
657  // out-of-line blocks into the loop which is very bad for code placement.
658  if (PreMBB == &MBB && !SplitAllCriticalEdges)
659  continue;
660  const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
661  if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
662  continue;
663 
664  // LV doesn't consider a phi use live-out, so isLiveOut only returns true
665  // when the source register is live-out for some other reason than a phi
666  // use. That means the copy we will insert in PreMBB won't be a kill, and
667  // there is a risk it may not be coalesced away.
668  //
669  // If the copy would be a kill, there is no need to split the edge.
670  bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
671  if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
672  continue;
673  if (ShouldSplit) {
674  LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
675  << printMBBReference(*PreMBB) << " -> "
676  << printMBBReference(MBB) << ": " << *BBI);
677  }
678 
679  // If Reg is not live-in to MBB, it means it must be live-in to some
680  // other PreMBB successor, and we can avoid the interference by splitting
681  // the edge.
682  //
683  // If Reg *is* live-in to MBB, the interference is inevitable and a copy
684  // is likely to be left after coalescing. If we are looking at a loop
685  // exiting edge, split it so we won't insert code in the loop, otherwise
686  // don't bother.
687  ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
688 
689  // Check for a loop exiting edge.
690  if (!ShouldSplit && CurLoop != PreLoop) {
691  LLVM_DEBUG({
692  dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
693  if (PreLoop)
694  dbgs() << "PreLoop: " << *PreLoop;
695  if (CurLoop)
696  dbgs() << "CurLoop: " << *CurLoop;
697  });
698  // This edge could be entering a loop, exiting a loop, or it could be
699  // both: Jumping directly form one loop to the header of a sibling
700  // loop.
701  // Split unless this edge is entering CurLoop from an outer loop.
702  ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
703  }
704  if (!ShouldSplit && !SplitAllCriticalEdges)
705  continue;
706  if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
707  LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
708  continue;
709  }
710  Changed = true;
711  ++NumCriticalEdgesSplit;
712  }
713  }
714  return Changed;
715 }
716 
717 bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
718  assert((LV || LIS) &&
719  "isLiveIn() requires either LiveVariables or LiveIntervals");
720  if (LIS)
721  return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
722  else
723  return LV->isLiveIn(Reg, *MBB);
724 }
725 
726 bool PHIElimination::isLiveOutPastPHIs(Register Reg,
727  const MachineBasicBlock *MBB) {
728  assert((LV || LIS) &&
729  "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
730  // LiveVariables considers uses in PHIs to be in the predecessor basic block,
731  // so that a register used only in a PHI is not live out of the block. In
732  // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
733  // in the predecessor basic block, so that a register used only in a PHI is live
734  // out of the block.
735  if (LIS) {
736  const LiveInterval &LI = LIS->getInterval(Reg);
737  for (const MachineBasicBlock *SI : MBB->successors())
738  if (LI.liveAt(LIS->getMBBStartIdx(SI)))
739  return true;
740  return false;
741  } else {
742  return LV->isLiveOut(Reg, *MBB);
743  }
744 }
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:103
MachineInstr.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::MachineInstr::isImplicitDef
bool isImplicitDef() const
Definition: MachineInstr.h:1260
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:127
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
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
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:119
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:143
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::MachineInstr::peekDebugInstrNum
unsigned peekDebugInstrNum() const
Examine the instruction number of this MachineInstr.
Definition: MachineInstr.h:465
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
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:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
MachineRegisterInfo.h
llvm::MachineBasicBlock::dump
void dump() const
Definition: MachineBasicBlock.cpp:295
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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:636
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:930
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:499
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
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:818
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::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
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:626
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:7679
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:395
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:321
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:210
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:385
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
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())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1255
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
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:230
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:242
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:552
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1056
llvm::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:526
llvm::MachineFunction::DebugPHIRegallocPos
Location of a PHI instruction that is also a debug-info variable value, for the duration of register ...
Definition: MachineFunction.h:491
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
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:365
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:744
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:55
llvm::MachineRegisterInfo::leaveSSA
void leaveSSA()
Definition: MachineRegisterInfo.h:191
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:103
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:492
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::MachineFunction::DebugPHIPositions
DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions
Map of debug instruction numbers to the position of their PHI instructions during register allocation...
Definition: MachineFunction.h:502
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:414
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:1006
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:37