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