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