LLVM  6.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  DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi);
274  } else {
275  const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
276  entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
277  }
278  BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
279  TII->get(TargetOpcode::COPY), DestReg)
280  .addReg(IncomingReg);
281  }
282 
283  // Update live variable information if there is any.
284  if (LV) {
285  MachineInstr &PHICopy = *std::prev(AfterPHIsIt);
286 
287  if (IncomingReg) {
288  LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
289 
290  // Increment use count of the newly created virtual register.
291  LV->setPHIJoin(IncomingReg);
292 
293  // When we are reusing the incoming register, it may already have been
294  // killed in this block. The old kill will also have been inserted at
295  // AfterPHIsIt, so it appears before the current PHICopy.
296  if (reusedIncoming)
297  if (MachineInstr *OldKill = VI.findKill(&MBB)) {
298  DEBUG(dbgs() << "Remove old kill from " << *OldKill);
299  LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
300  DEBUG(MBB.dump());
301  }
302 
303  // Add information to LiveVariables to know that the incoming value is
304  // killed. Note that because the value is defined in several places (once
305  // each for each incoming block), the "def" block and instruction fields
306  // for the VarInfo is not filled in.
307  LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
308  }
309 
310  // Since we are going to be deleting the PHI node, if it is the last use of
311  // any registers, or if the value itself is dead, we need to move this
312  // information over to the new copy we just inserted.
313  LV->removeVirtualRegistersKilled(*MPhi);
314 
315  // If the result is dead, update LV.
316  if (isDead) {
317  LV->addVirtualRegisterDead(DestReg, PHICopy);
318  LV->removeVirtualRegisterDead(DestReg, *MPhi);
319  }
320  }
321 
322  // Update LiveIntervals for the new copy or implicit def.
323  if (LIS) {
324  SlotIndex DestCopyIndex =
325  LIS->InsertMachineInstrInMaps(*std::prev(AfterPHIsIt));
326 
327  SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
328  if (IncomingReg) {
329  // Add the region from the beginning of MBB to the copy instruction to
330  // IncomingReg's live interval.
331  LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
332  VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
333  if (!IncomingVNI)
334  IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
335  LIS->getVNInfoAllocator());
336  IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
337  DestCopyIndex.getRegSlot(),
338  IncomingVNI));
339  }
340 
341  LiveInterval &DestLI = LIS->getInterval(DestReg);
342  assert(DestLI.begin() != DestLI.end() &&
343  "PHIs should have nonempty LiveIntervals.");
344  if (DestLI.endIndex().isDead()) {
345  // A dead PHI's live range begins and ends at the start of the MBB, but
346  // the lowered copy, which will still be dead, needs to begin and end at
347  // the copy instruction.
348  VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
349  assert(OrigDestVNI && "PHI destination should be live at block entry.");
350  DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
351  DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
352  LIS->getVNInfoAllocator());
353  DestLI.removeValNo(OrigDestVNI);
354  } else {
355  // Otherwise, remove the region from the beginning of MBB to the copy
356  // instruction from DestReg's live interval.
357  DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
358  VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
359  assert(DestVNI && "PHI destination should be live at its definition.");
360  DestVNI->def = DestCopyIndex.getRegSlot();
361  }
362  }
363 
364  // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
365  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
366  --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
367  MPhi->getOperand(i).getReg())];
368 
369  // Now loop over all of the incoming arguments, changing them to copy into the
370  // IncomingReg register in the corresponding predecessor basic block.
371  SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
372  for (int i = NumSrcs - 1; i >= 0; --i) {
373  unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
374  unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
375  bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
376  isImplicitlyDefined(SrcReg, MRI);
378  "Machine PHI Operands must all be virtual registers!");
379 
380  // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
381  // path the PHI.
382  MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
383 
384  // Check to make sure we haven't already emitted the copy for this block.
385  // This can happen because PHI nodes may have multiple entries for the same
386  // basic block.
387  if (!MBBsInsertedInto.insert(&opBlock).second)
388  continue; // If the copy has already been emitted, we're done.
389 
390  // Find a safe location to insert the copy, this may be the first terminator
391  // in the block (or end()).
392  MachineBasicBlock::iterator InsertPos =
393  findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
394 
395  // Insert the copy.
396  MachineInstr *NewSrcInstr = nullptr;
397  if (!reusedIncoming && IncomingReg) {
398  if (SrcUndef) {
399  // The source register is undefined, so there is no need for a real
400  // COPY, but we still need to ensure joint dominance by defs.
401  // Insert an IMPLICIT_DEF instruction.
402  NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
403  TII->get(TargetOpcode::IMPLICIT_DEF),
404  IncomingReg);
405 
406  // Clean up the old implicit-def, if there even was one.
407  if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
408  if (DefMI->isImplicitDef())
409  ImpDefs.insert(DefMI);
410  } else {
411  NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
412  TII->get(TargetOpcode::COPY), IncomingReg)
413  .addReg(SrcReg, 0, SrcSubReg);
414  }
415  }
416 
417  // We only need to update the LiveVariables kill of SrcReg if this was the
418  // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
419  // out of the predecessor. We can also ignore undef sources.
420  if (LV && !SrcUndef &&
421  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
422  !LV->isLiveOut(SrcReg, opBlock)) {
423  // We want to be able to insert a kill of the register if this PHI (aka,
424  // the copy we just inserted) is the last use of the source value. Live
425  // variable analysis conservatively handles this by saying that the value
426  // is live until the end of the block the PHI entry lives in. If the value
427  // really is dead at the PHI copy, there will be no successor blocks which
428  // have the value live-in.
429 
430  // Okay, if we now know that the value is not live out of the block, we
431  // can add a kill marker in this block saying that it kills the incoming
432  // value!
433 
434  // In our final twist, we have to decide which instruction kills the
435  // register. In most cases this is the copy, however, terminator
436  // instructions at the end of the block may also use the value. In this
437  // case, we should mark the last such terminator as being the killing
438  // block, not the copy.
439  MachineBasicBlock::iterator KillInst = opBlock.end();
440  MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
441  for (MachineBasicBlock::iterator Term = FirstTerm;
442  Term != opBlock.end(); ++Term) {
443  if (Term->readsRegister(SrcReg))
444  KillInst = Term;
445  }
446 
447  if (KillInst == opBlock.end()) {
448  // No terminator uses the register.
449 
450  if (reusedIncoming || !IncomingReg) {
451  // We may have to rewind a bit if we didn't insert a copy this time.
452  KillInst = FirstTerm;
453  while (KillInst != opBlock.begin()) {
454  --KillInst;
455  if (KillInst->isDebugValue())
456  continue;
457  if (KillInst->readsRegister(SrcReg))
458  break;
459  }
460  } else {
461  // We just inserted this copy.
462  KillInst = std::prev(InsertPos);
463  }
464  }
465  assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
466 
467  // Finally, mark it killed.
468  LV->addVirtualRegisterKilled(SrcReg, *KillInst);
469 
470  // This vreg no longer lives all of the way through opBlock.
471  unsigned opBlockNum = opBlock.getNumber();
472  LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
473  }
474 
475  if (LIS) {
476  if (NewSrcInstr) {
477  LIS->InsertMachineInstrInMaps(*NewSrcInstr);
478  LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
479  }
480 
481  if (!SrcUndef &&
482  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
483  LiveInterval &SrcLI = LIS->getInterval(SrcReg);
484 
485  bool isLiveOut = false;
487  SE = opBlock.succ_end(); SI != SE; ++SI) {
488  SlotIndex startIdx = LIS->getMBBStartIdx(*SI);
489  VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
490 
491  // Definitions by other PHIs are not truly live-in for our purposes.
492  if (VNI && VNI->def != startIdx) {
493  isLiveOut = true;
494  break;
495  }
496  }
497 
498  if (!isLiveOut) {
499  MachineBasicBlock::iterator KillInst = opBlock.end();
500  MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
501  for (MachineBasicBlock::iterator Term = FirstTerm;
502  Term != opBlock.end(); ++Term) {
503  if (Term->readsRegister(SrcReg))
504  KillInst = Term;
505  }
506 
507  if (KillInst == opBlock.end()) {
508  // No terminator uses the register.
509 
510  if (reusedIncoming || !IncomingReg) {
511  // We may have to rewind a bit if we didn't just insert a copy.
512  KillInst = FirstTerm;
513  while (KillInst != opBlock.begin()) {
514  --KillInst;
515  if (KillInst->isDebugValue())
516  continue;
517  if (KillInst->readsRegister(SrcReg))
518  break;
519  }
520  } else {
521  // We just inserted this copy.
522  KillInst = std::prev(InsertPos);
523  }
524  }
525  assert(KillInst->readsRegister(SrcReg) &&
526  "Cannot find kill instruction");
527 
528  SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
529  SrcLI.removeSegment(LastUseIndex.getRegSlot(),
530  LIS->getMBBEndIdx(&opBlock));
531  }
532  }
533  }
534  }
535 
536  // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
537  if (reusedIncoming || !IncomingReg) {
538  if (LIS)
539  LIS->RemoveMachineInstrFromMaps(*MPhi);
540  MF.DeleteMachineInstr(MPhi);
541  }
542 }
543 
544 /// analyzePHINodes - Gather information about the PHI nodes in here. In
545 /// particular, we want to map the number of uses of a virtual register which is
546 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
547 /// used later to determine when the vreg is killed in the BB.
548 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
549  for (const auto &MBB : MF)
550  for (const auto &BBI : MBB) {
551  if (!BBI.isPHI())
552  break;
553  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
554  ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
555  BBI.getOperand(i).getReg())];
556  }
557 }
558 
559 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
560  MachineBasicBlock &MBB,
561  MachineLoopInfo *MLI) {
562  if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
563  return false; // Quick exit for basic blocks without PHIs.
564 
565  const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
566  bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
567 
568  bool Changed = false;
569  for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
570  BBI != BBE && BBI->isPHI(); ++BBI) {
571  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
572  unsigned Reg = BBI->getOperand(i).getReg();
573  MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
574  // Is there a critical edge from PreMBB to MBB?
575  if (PreMBB->succ_size() == 1)
576  continue;
577 
578  // Avoid splitting backedges of loops. It would introduce small
579  // out-of-line blocks into the loop which is very bad for code placement.
580  if (PreMBB == &MBB && !SplitAllCriticalEdges)
581  continue;
582  const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
583  if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
584  continue;
585 
586  // LV doesn't consider a phi use live-out, so isLiveOut only returns true
587  // when the source register is live-out for some other reason than a phi
588  // use. That means the copy we will insert in PreMBB won't be a kill, and
589  // there is a risk it may not be coalesced away.
590  //
591  // If the copy would be a kill, there is no need to split the edge.
592  bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
593  if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
594  continue;
595  if (ShouldSplit) {
596  DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#"
597  << PreMBB->getNumber() << " -> BB#" << MBB.getNumber()
598  << ": " << *BBI);
599  }
600 
601  // If Reg is not live-in to MBB, it means it must be live-in to some
602  // other PreMBB successor, and we can avoid the interference by splitting
603  // the edge.
604  //
605  // If Reg *is* live-in to MBB, the interference is inevitable and a copy
606  // is likely to be left after coalescing. If we are looking at a loop
607  // exiting edge, split it so we won't insert code in the loop, otherwise
608  // don't bother.
609  ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
610 
611  // Check for a loop exiting edge.
612  if (!ShouldSplit && CurLoop != PreLoop) {
613  DEBUG({
614  dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
615  if (PreLoop) dbgs() << "PreLoop: " << *PreLoop;
616  if (CurLoop) dbgs() << "CurLoop: " << *CurLoop;
617  });
618  // This edge could be entering a loop, exiting a loop, or it could be
619  // both: Jumping directly form one loop to the header of a sibling
620  // loop.
621  // Split unless this edge is entering CurLoop from an outer loop.
622  ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
623  }
624  if (!ShouldSplit && !SplitAllCriticalEdges)
625  continue;
626  if (!PreMBB->SplitCriticalEdge(&MBB, *this)) {
627  DEBUG(dbgs() << "Failed to split critical edge.\n");
628  continue;
629  }
630  Changed = true;
631  ++NumCriticalEdgesSplit;
632  }
633  }
634  return Changed;
635 }
636 
637 bool PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock *MBB) {
638  assert((LV || LIS) &&
639  "isLiveIn() requires either LiveVariables or LiveIntervals");
640  if (LIS)
641  return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
642  else
643  return LV->isLiveIn(Reg, *MBB);
644 }
645 
646 bool PHIElimination::isLiveOutPastPHIs(unsigned Reg,
647  const MachineBasicBlock *MBB) {
648  assert((LV || LIS) &&
649  "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
650  // LiveVariables considers uses in PHIs to be in the predecessor basic block,
651  // so that a register used only in a PHI is not live out of the block. In
652  // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
653  // in the predecessor basic block, so that a register used only in a PHI is live
654  // out of the block.
655  if (LIS) {
656  const LiveInterval &LI = LIS->getInterval(Reg);
657  for (const MachineBasicBlock *SI : MBB->successors())
658  if (LI.liveAt(LIS->getMBBStartIdx(SI)))
659  return true;
660  return false;
661  } else {
662  return LV->isLiveOut(Reg, *MBB);
663  }
664 }
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
unsigned createVirtualRegister(const TargetRegisterClass *RegClass)
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:268
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.
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:826
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
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
iterator end()
Definition: LiveInterval.h:212
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
Reg
All possible values of the reg field in the ModR/M byte.
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."))
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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:406
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
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:831
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:132
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:59
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:89
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
#define DEBUG(X)
Definition: Debug.h:118
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
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