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