LLVM  15.0.0git
PHIElimination.cpp
Go to the documentation of this file.
1 //===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass eliminates machine instruction PHI nodes by inserting copy
10 // instructions. This destroys SSA information, but is the desired input for
11 // some register allocators.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "PHIEliminationUtils.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/LoopInfo.h"
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  std::vector<SparseBitVector<>> *LiveInSets);
99 
100  // These functions are temporary abstractions around LiveVariables and
101  // LiveIntervals, so they can go away when LiveVariables does.
102  bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);
103  bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);
104 
105  using BBVRegPair = std::pair<unsigned, Register>;
106  using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
107 
108  // Count the number of non-undef PHI uses of each register in each BB.
109  VRegPHIUse VRegPHIUseCount;
110 
111  // Defs of PHI sources which are implicit_def.
113 
114  // Map reusable lowered PHI node -> incoming join register.
115  using LoweredPHIMap =
117  LoweredPHIMap LoweredPHIs;
118  };
119 
120 } // end anonymous namespace
121 
122 STATISTIC(NumLowered, "Number of phis lowered");
123 STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
124 STATISTIC(NumReused, "Number of reused lowered phis");
125 
126 char PHIElimination::ID = 0;
127 
129 
130 INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
131  "Eliminate PHI nodes for register allocation",
132  false, false)
135  "Eliminate PHI nodes for register allocation", false, false)
136 
137 void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
138  AU.addUsedIfAvailable<LiveVariables>();
139  AU.addPreserved<LiveVariables>();
140  AU.addPreserved<SlotIndexes>();
141  AU.addPreserved<LiveIntervals>();
142  AU.addPreserved<MachineDominatorTree>();
143  AU.addPreserved<MachineLoopInfo>();
145 }
146 
147 bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
148  MRI = &MF.getRegInfo();
149  LV = getAnalysisIfAvailable<LiveVariables>();
150  LIS = getAnalysisIfAvailable<LiveIntervals>();
151 
152  bool Changed = false;
153 
154  // Split critical edges to help the coalescer.
155  if (!DisableEdgeSplitting && (LV || LIS)) {
156  // A set of live-in regs for each MBB which is used to update LV
157  // efficiently also with large functions.
158  std::vector<SparseBitVector<>> LiveInSets;
159  if (LV) {
160  LiveInSets.resize(MF.size());
161  for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
162  // Set the bit for this register for each MBB where it is
163  // live-through or live-in (killed).
164  unsigned VirtReg = Register::index2VirtReg(Index);
165  MachineInstr *DefMI = MRI->getVRegDef(VirtReg);
166  if (!DefMI)
167  continue;
168  LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);
169  SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();
170  SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();
171  while (AliveBlockItr != EndItr) {
172  unsigned BlockNum = *(AliveBlockItr++);
173  LiveInSets[BlockNum].set(Index);
174  }
175  // The register is live into an MBB in which it is killed but not
176  // defined. See comment for VarInfo in LiveVariables.h.
177  MachineBasicBlock *DefMBB = DefMI->getParent();
178  if (VI.Kills.size() > 1 ||
179  (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
180  for (auto *MI : VI.Kills)
181  LiveInSets[MI->getParent()->getNumber()].set(Index);
182  }
183  }
184 
185  MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
186  for (auto &MBB : MF)
187  Changed |= SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr));
188  }
189 
190  // This pass takes the function out of SSA form.
191  MRI->leaveSSA();
192 
193  // Populate VRegPHIUseCount
194  analyzePHINodes(MF);
195 
196  // Eliminate PHI instructions by inserting copies into predecessor blocks.
197  for (auto &MBB : MF)
198  Changed |= EliminatePHINodes(MF, MBB);
199 
200  // Remove dead IMPLICIT_DEF instructions.
201  for (MachineInstr *DefMI : ImpDefs) {
202  Register DefReg = DefMI->getOperand(0).getReg();
203  if (MRI->use_nodbg_empty(DefReg)) {
204  if (LIS)
205  LIS->RemoveMachineInstrFromMaps(*DefMI);
207  }
208  }
209 
210  // Clean up the lowered PHI instructions.
211  for (auto &I : LoweredPHIs) {
212  if (LIS)
213  LIS->RemoveMachineInstrFromMaps(*I.first);
214  MF.deleteMachineInstr(I.first);
215  }
216 
217  // TODO: we should use the incremental DomTree updater here.
218  if (Changed)
219  if (auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>())
220  MDT->getBase().recalculate(MF);
221 
222  LoweredPHIs.clear();
223  ImpDefs.clear();
224  VRegPHIUseCount.clear();
225 
226  MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
227 
228  return Changed;
229 }
230 
231 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
232 /// predecessor basic blocks.
233 bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
235  if (MBB.empty() || !MBB.front().isPHI())
236  return false; // Quick exit for basic blocks without PHIs.
237 
238  // Get an iterator to the last PHI node.
239  MachineBasicBlock::iterator LastPHIIt =
240  std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
241 
242  while (MBB.front().isPHI())
243  LowerPHINode(MBB, LastPHIIt);
244 
245  return true;
246 }
247 
248 /// Return true if all defs of VirtReg are implicit-defs.
249 /// This includes registers with no defs.
250 static bool isImplicitlyDefined(unsigned VirtReg,
251  const MachineRegisterInfo &MRI) {
252  for (MachineInstr &DI : MRI.def_instructions(VirtReg))
253  if (!DI.isImplicitDef())
254  return false;
255  return true;
256 }
257 
258 /// Return true if all sources of the phi node are implicit_def's, or undef's.
259 static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
260  const MachineRegisterInfo &MRI) {
261  for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
262  const MachineOperand &MO = MPhi.getOperand(I);
263  if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
264  return false;
265  }
266  return true;
267 }
268 /// LowerPHINode - Lower the PHI node at the top of the specified block.
269 void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
270  MachineBasicBlock::iterator LastPHIIt) {
271  ++NumLowered;
272 
273  MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
274 
275  // Unlink the PHI node from the basic block, but don't delete the PHI yet.
276  MachineInstr *MPhi = MBB.remove(&*MBB.begin());
277 
278  unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
279  Register DestReg = MPhi->getOperand(0).getReg();
280  assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
281  bool isDead = MPhi->getOperand(0).isDead();
282 
283  // Create a new register for the incoming PHI arguments.
284  MachineFunction &MF = *MBB.getParent();
285  unsigned IncomingReg = 0;
286  bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
287 
288  // Insert a register to register copy at the top of the current block (but
289  // after any remaining phi nodes) which copies the new incoming register
290  // into the phi node destination.
291  MachineInstr *PHICopy = nullptr;
293  if (allPhiOperandsUndefined(*MPhi, *MRI))
294  // If all sources of a PHI node are implicit_def or undef uses, just emit an
295  // implicit_def instead of a copy.
296  PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
297  TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
298  else {
299  // Can we reuse an earlier PHI node? This only happens for critical edges,
300  // typically those created by tail duplication.
301  unsigned &entry = LoweredPHIs[MPhi];
302  if (entry) {
303  // An identical PHI node was already lowered. Reuse the incoming register.
304  IncomingReg = entry;
305  reusedIncoming = true;
306  ++NumReused;
307  LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
308  << *MPhi);
309  } else {
310  const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
311  entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
312  }
313  // Give the target possiblity to handle special cases fallthrough otherwise
314  PHICopy = TII->createPHIDestinationCopy(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
315  IncomingReg, DestReg);
316  }
317 
318  if (MPhi->peekDebugInstrNum()) {
319  // If referred to by debug-info, store where this PHI was.
320  MachineFunction *MF = MBB.getParent();
321  unsigned ID = MPhi->peekDebugInstrNum();
322  auto P = MachineFunction::DebugPHIRegallocPos(&MBB, IncomingReg, 0);
323  auto Res = MF->DebugPHIPositions.insert({ID, P});
324  assert(Res.second);
325  (void)Res;
326  }
327 
328  // Update live variable information if there is any.
329  if (LV) {
330  if (IncomingReg) {
331  LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
332 
333  // Increment use count of the newly created virtual register.
334  LV->setPHIJoin(IncomingReg);
335 
336  MachineInstr *OldKill = nullptr;
337  bool IsPHICopyAfterOldKill = false;
338 
339  if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
340  // Calculate whether the PHICopy is after the OldKill.
341  // In general, the PHICopy is inserted as the first non-phi instruction
342  // by default, so it's before the OldKill. But some Target hooks for
343  // createPHIDestinationCopy() may modify the default insert position of
344  // PHICopy.
345  for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
346  I != E; ++I) {
347  if (I == PHICopy)
348  break;
349 
350  if (I == OldKill) {
351  IsPHICopyAfterOldKill = true;
352  break;
353  }
354  }
355  }
356 
357  // When we are reusing the incoming register and it has been marked killed
358  // by OldKill, if the PHICopy is after the OldKill, we should remove the
359  // killed flag from OldKill.
360  if (IsPHICopyAfterOldKill) {
361  LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
362  LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
363  LLVM_DEBUG(MBB.dump());
364  }
365 
366  // Add information to LiveVariables to know that the first used incoming
367  // value or the resued incoming value whose PHICopy is after the OldKIll
368  // is killed. Note that because the value is defined in several places
369  // (once each for each incoming block), the "def" block and instruction
370  // fields for the VarInfo is not filled in.
371  if (!OldKill || IsPHICopyAfterOldKill)
372  LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
373  }
374 
375  // Since we are going to be deleting the PHI node, if it is the last use of
376  // any registers, or if the value itself is dead, we need to move this
377  // information over to the new copy we just inserted.
378  LV->removeVirtualRegistersKilled(*MPhi);
379 
380  // If the result is dead, update LV.
381  if (isDead) {
382  LV->addVirtualRegisterDead(DestReg, *PHICopy);
383  LV->removeVirtualRegisterDead(DestReg, *MPhi);
384  }
385  }
386 
387  // Update LiveIntervals for the new copy or implicit def.
388  if (LIS) {
389  SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
390 
391  SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
392  if (IncomingReg) {
393  // Add the region from the beginning of MBB to the copy instruction to
394  // IncomingReg's live interval.
395  LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
396  VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
397  if (!IncomingVNI)
398  IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
399  LIS->getVNInfoAllocator());
400  IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
401  DestCopyIndex.getRegSlot(),
402  IncomingVNI));
403  }
404 
405  LiveInterval &DestLI = LIS->getInterval(DestReg);
406  assert(!DestLI.empty() && "PHIs should have nonempty LiveIntervals.");
407  if (DestLI.endIndex().isDead()) {
408  // A dead PHI's live range begins and ends at the start of the MBB, but
409  // the lowered copy, which will still be dead, needs to begin and end at
410  // the copy instruction.
411  VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
412  assert(OrigDestVNI && "PHI destination should be live at block entry.");
413  DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
414  DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
415  LIS->getVNInfoAllocator());
416  DestLI.removeValNo(OrigDestVNI);
417  } else {
418  // Otherwise, remove the region from the beginning of MBB to the copy
419  // instruction from DestReg's live interval.
420  DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
421  VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
422  assert(DestVNI && "PHI destination should be live at its definition.");
423  DestVNI->def = DestCopyIndex.getRegSlot();
424  }
425  }
426 
427  // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
428  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
429  if (!MPhi->getOperand(i).isUndef()) {
430  --VRegPHIUseCount[BBVRegPair(
431  MPhi->getOperand(i + 1).getMBB()->getNumber(),
432  MPhi->getOperand(i).getReg())];
433  }
434  }
435 
436  // Now loop over all of the incoming arguments, changing them to copy into the
437  // IncomingReg register in the corresponding predecessor basic block.
438  SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
439  for (int i = NumSrcs - 1; i >= 0; --i) {
440  Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
441  unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
442  bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
443  isImplicitlyDefined(SrcReg, *MRI);
445  "Machine PHI Operands must all be virtual registers!");
446 
447  // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
448  // path the PHI.
449  MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
450 
451  // Check to make sure we haven't already emitted the copy for this block.
452  // This can happen because PHI nodes may have multiple entries for the same
453  // basic block.
454  if (!MBBsInsertedInto.insert(&opBlock).second)
455  continue; // If the copy has already been emitted, we're done.
456 
457  MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
458  if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
459  assert(SrcRegDef->getOperand(0).isReg() &&
460  SrcRegDef->getOperand(0).isDef() &&
461  "Expected operand 0 to be a reg def!");
462  // Now that the PHI's use has been removed (as the instruction was
463  // removed) there should be no other uses of the SrcReg.
464  assert(MRI->use_empty(SrcReg) &&
465  "Expected a single use from UnspillableTerminator");
466  SrcRegDef->getOperand(0).setReg(IncomingReg);
467 
468  // Update LiveVariables.
469  if (LV) {
470  LiveVariables::VarInfo &SrcVI = LV->getVarInfo(SrcReg);
471  LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(IncomingReg);
472  IncomingVI.AliveBlocks = std::move(SrcVI.AliveBlocks);
473  SrcVI.AliveBlocks.clear();
474  }
475 
476  continue;
477  }
478 
479  // Find a safe location to insert the copy, this may be the first terminator
480  // in the block (or end()).
481  MachineBasicBlock::iterator InsertPos =
482  findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
483 
484  // Insert the copy.
485  MachineInstr *NewSrcInstr = nullptr;
486  if (!reusedIncoming && IncomingReg) {
487  if (SrcUndef) {
488  // The source register is undefined, so there is no need for a real
489  // COPY, but we still need to ensure joint dominance by defs.
490  // Insert an IMPLICIT_DEF instruction.
491  NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
492  TII->get(TargetOpcode::IMPLICIT_DEF),
493  IncomingReg);
494 
495  // Clean up the old implicit-def, if there even was one.
496  if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
497  if (DefMI->isImplicitDef())
498  ImpDefs.insert(DefMI);
499  } else {
500  // Delete the debug location, since the copy is inserted into a
501  // different basic block.
502  NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,
503  SrcReg, SrcSubReg, IncomingReg);
504  }
505  }
506 
507  // We only need to update the LiveVariables kill of SrcReg if this was the
508  // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
509  // out of the predecessor. We can also ignore undef sources.
510  if (LV && !SrcUndef &&
511  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
512  !LV->isLiveOut(SrcReg, opBlock)) {
513  // We want to be able to insert a kill of the register if this PHI (aka,
514  // the copy we just inserted) is the last use of the source value. Live
515  // variable analysis conservatively handles this by saying that the value
516  // is live until the end of the block the PHI entry lives in. If the value
517  // really is dead at the PHI copy, there will be no successor blocks which
518  // have the value live-in.
519 
520  // Okay, if we now know that the value is not live out of the block, we
521  // can add a kill marker in this block saying that it kills the incoming
522  // value!
523 
524  // In our final twist, we have to decide which instruction kills the
525  // register. In most cases this is the copy, however, terminator
526  // instructions at the end of the block may also use the value. In this
527  // case, we should mark the last such terminator as being the killing
528  // block, not the copy.
529  MachineBasicBlock::iterator KillInst = opBlock.end();
530  for (MachineBasicBlock::iterator Term = InsertPos; Term != opBlock.end();
531  ++Term) {
532  if (Term->readsRegister(SrcReg))
533  KillInst = Term;
534  }
535 
536  if (KillInst == opBlock.end()) {
537  // No terminator uses the register.
538 
539  if (reusedIncoming || !IncomingReg) {
540  // We may have to rewind a bit if we didn't insert a copy this time.
541  KillInst = InsertPos;
542  while (KillInst != opBlock.begin()) {
543  --KillInst;
544  if (KillInst->isDebugInstr())
545  continue;
546  if (KillInst->readsRegister(SrcReg))
547  break;
548  }
549  } else {
550  // We just inserted this copy.
551  KillInst = NewSrcInstr;
552  }
553  }
554  assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
555 
556  // Finally, mark it killed.
557  LV->addVirtualRegisterKilled(SrcReg, *KillInst);
558 
559  // This vreg no longer lives all of the way through opBlock.
560  unsigned opBlockNum = opBlock.getNumber();
561  LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
562  }
563 
564  if (LIS) {
565  if (NewSrcInstr) {
566  LIS->InsertMachineInstrInMaps(*NewSrcInstr);
567  LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
568  }
569 
570  if (!SrcUndef &&
571  !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
572  LiveInterval &SrcLI = LIS->getInterval(SrcReg);
573 
574  bool isLiveOut = false;
575  for (MachineBasicBlock *Succ : opBlock.successors()) {
576  SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
577  VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
578 
579  // Definitions by other PHIs are not truly live-in for our purposes.
580  if (VNI && VNI->def != startIdx) {
581  isLiveOut = true;
582  break;
583  }
584  }
585 
586  if (!isLiveOut) {
587  MachineBasicBlock::iterator KillInst = opBlock.end();
588  for (MachineBasicBlock::iterator Term = InsertPos;
589  Term != opBlock.end(); ++Term) {
590  if (Term->readsRegister(SrcReg))
591  KillInst = Term;
592  }
593 
594  if (KillInst == opBlock.end()) {
595  // No terminator uses the register.
596 
597  if (reusedIncoming || !IncomingReg) {
598  // We may have to rewind a bit if we didn't just insert a copy.
599  KillInst = InsertPos;
600  while (KillInst != opBlock.begin()) {
601  --KillInst;
602  if (KillInst->isDebugInstr())
603  continue;
604  if (KillInst->readsRegister(SrcReg))
605  break;
606  }
607  } else {
608  // We just inserted this copy.
609  KillInst = std::prev(InsertPos);
610  }
611  }
612  assert(KillInst->readsRegister(SrcReg) &&
613  "Cannot find kill instruction");
614 
615  SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
616  SrcLI.removeSegment(LastUseIndex.getRegSlot(),
617  LIS->getMBBEndIdx(&opBlock));
618  }
619  }
620  }
621  }
622 
623  // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
624  if (reusedIncoming || !IncomingReg) {
625  if (LIS)
626  LIS->RemoveMachineInstrFromMaps(*MPhi);
627  MF.deleteMachineInstr(MPhi);
628  }
629 }
630 
631 /// analyzePHINodes - Gather information about the PHI nodes in here. In
632 /// particular, we want to map the number of uses of a virtual register which is
633 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
634 /// used later to determine when the vreg is killed in the BB.
635 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
636  for (const auto &MBB : MF) {
637  for (const auto &BBI : MBB) {
638  if (!BBI.isPHI())
639  break;
640  for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
641  if (!BBI.getOperand(i).isUndef()) {
642  ++VRegPHIUseCount[BBVRegPair(
643  BBI.getOperand(i + 1).getMBB()->getNumber(),
644  BBI.getOperand(i).getReg())];
645  }
646  }
647  }
648  }
649 }
650 
651 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
653  MachineLoopInfo *MLI,
654  std::vector<SparseBitVector<>> *LiveInSets) {
655  if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
656  return false; // Quick exit for basic blocks without PHIs.
657 
658  const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
659  bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
660 
661  bool Changed = false;
662  for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
663  BBI != BBE && BBI->isPHI(); ++BBI) {
664  for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
665  Register Reg = BBI->getOperand(i).getReg();
666  MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
667  // Is there a critical edge from PreMBB to MBB?
668  if (PreMBB->succ_size() == 1)
669  continue;
670 
671  // Avoid splitting backedges of loops. It would introduce small
672  // out-of-line blocks into the loop which is very bad for code placement.
673  if (PreMBB == &MBB && !SplitAllCriticalEdges)
674  continue;
675  const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
676  if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
677  continue;
678 
679  // LV doesn't consider a phi use live-out, so isLiveOut only returns true
680  // when the source register is live-out for some other reason than a phi
681  // use. That means the copy we will insert in PreMBB won't be a kill, and
682  // there is a risk it may not be coalesced away.
683  //
684  // If the copy would be a kill, there is no need to split the edge.
685  bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
686  if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
687  continue;
688  if (ShouldSplit) {
689  LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
690  << printMBBReference(*PreMBB) << " -> "
691  << printMBBReference(MBB) << ": " << *BBI);
692  }
693 
694  // If Reg is not live-in to MBB, it means it must be live-in to some
695  // other PreMBB successor, and we can avoid the interference by splitting
696  // the edge.
697  //
698  // If Reg *is* live-in to MBB, the interference is inevitable and a copy
699  // is likely to be left after coalescing. If we are looking at a loop
700  // exiting edge, split it so we won't insert code in the loop, otherwise
701  // don't bother.
702  ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
703 
704  // Check for a loop exiting edge.
705  if (!ShouldSplit && CurLoop != PreLoop) {
706  LLVM_DEBUG({
707  dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
708  if (PreLoop)
709  dbgs() << "PreLoop: " << *PreLoop;
710  if (CurLoop)
711  dbgs() << "CurLoop: " << *CurLoop;
712  });
713  // This edge could be entering a loop, exiting a loop, or it could be
714  // both: Jumping directly form one loop to the header of a sibling
715  // loop.
716  // Split unless this edge is entering CurLoop from an outer loop.
717  ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
718  }
719  if (!ShouldSplit && !SplitAllCriticalEdges)
720  continue;
721  if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
722  LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
723  continue;
724  }
725  Changed = true;
726  ++NumCriticalEdgesSplit;
727  }
728  }
729  return Changed;
730 }
731 
732 bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
733  assert((LV || LIS) &&
734  "isLiveIn() requires either LiveVariables or LiveIntervals");
735  if (LIS)
736  return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
737  else
738  return LV->isLiveIn(Reg, *MBB);
739 }
740 
741 bool PHIElimination::isLiveOutPastPHIs(Register Reg,
742  const MachineBasicBlock *MBB) {
743  assert((LV || LIS) &&
744  "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
745  // LiveVariables considers uses in PHIs to be in the predecessor basic block,
746  // so that a register used only in a PHI is not live out of the block. In
747  // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
748  // in the predecessor basic block, so that a register used only in a PHI is live
749  // out of the block.
750  if (LIS) {
751  const LiveInterval &LI = LIS->getInterval(Reg);
752  for (const MachineBasicBlock *SI : MBB->successors())
753  if (LI.liveAt(LIS->getMBBStartIdx(SI)))
754  return true;
755  return false;
756  } else {
757  return LV->isLiveOut(Reg, *MBB);
758  }
759 }
i
i
Definition: README.txt:29
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:353
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::MachineInstr::isImplicitDef
bool isImplicitDef() const
Definition: MachineInstr.h:1262
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:382
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:126
llvm::MachineRegisterInfo::createVirtualRegister
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
Definition: MachineRegisterInfo.cpp:156
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::SparseBitVector::clear
void clear()
Definition: SparseBitVector.h:452
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:93
llvm::PHIEliminationID
char & PHIEliminationID
PHIElimination - This pass eliminates machine instruction PHI nodes by inserting copy instructions.
Definition: PHIElimination.cpp:128
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:116
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
allPhiOperandsUndefined
static bool allPhiOperandsUndefined(const MachineInstr &MPhi, const MachineRegisterInfo &MRI)
Return true if all sources of the phi node are implicit_def's, or undef's.
Definition: PHIElimination.cpp:259
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::VNInfo::def
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
DenseMap.h
TargetInstrInfo.h
isImplicitlyDefined
static bool isImplicitlyDefined(unsigned VirtReg, const MachineRegisterInfo &MRI)
Return true if all defs of VirtReg are implicit-defs.
Definition: PHIElimination.cpp:250
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:765
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::MachineInstr::peekDebugInstrNum
unsigned peekDebugInstrNum() const
Examine the instruction number of this MachineInstr.
Definition: MachineInstr.h:467
llvm::Register::index2VirtReg
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
DEBUG_TYPE
#define DEBUG_TYPE
Definition: PHIElimination.cpp:47
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
MachineRegisterInfo.h
llvm::MachineBasicBlock::dump
void dump() const
Definition: MachineBasicBlock.cpp:291
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
DisableEdgeSplitting
static cl::opt< bool > DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), cl::Hidden, cl::desc("Disable critical edge splitting " "during PHI elimination"))
isLiveOut
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
Definition: SIOptimizeExecMasking.cpp:287
CommandLine.h
PHIEliminationUtils.h
llvm::SparseBitVector
Definition: SparseBitVector.h:256
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:650
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
MachineLoopInfo.h
llvm::LiveRange::liveAt
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:401
llvm::MachineBasicBlock::remove
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
Definition: MachineBasicBlock.h:952
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LiveVariables::VarInfo
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:80
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:501
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:548
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:45
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::initializePHIEliminationPass
void initializePHIEliminationPass(PassRegistry &)
llvm::MachineFunction::deleteMachineInstr
void deleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
Definition: MachineFunction.cpp:420
LiveVariables.h
false
Definition: StackSlotColoring.cpp:141
TargetOpcodes.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
llvm::MachineFunction::size
unsigned size() const
Definition: MachineFunction.h:832
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::SlotIndex::getDeadSlot
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:258
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:313
SmallPtrSet.h
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:396
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::MachineRegisterInfo::use_empty
bool use_empty(Register RegNo) const
use_empty - Return true if there are no instructions using the specified register.
Definition: MachineRegisterInfo.h:514
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:642
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:640
llvm::cl::opt< bool >
allocation
Eliminate PHI nodes for register allocation
Definition: PHIElimination.cpp:135
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:420
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
VI
@ VI
Definition: SIInstrInfo.cpp:7834
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:394
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE, "Eliminate PHI nodes for register allocation", false, false) INITIALIZE_PASS_END(PHIElimination
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
LiveIntervals.h
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::MachineBasicBlock::SkipPHIsAndLabels
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
Definition: MachineBasicBlock.cpp:206
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
llvm::nodes
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Definition: GraphTraits.h:110
llvm::MachineRegisterInfo::def_instructions
iterator_range< def_instr_iterator > def_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:413
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:384
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
MachineFunctionPass.h
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:234
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1257
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
register
should just be implemented with a CLZ instruction Since there are other e that share this it would be best to implement this in a target independent as zero is the default value for the binary encoder e add r0 add r5 Register operands should be distinct That when the encoding does not require two syntactical operands to refer to the same register
Definition: README.txt:726
llvm::SlotIndex::getRegSlot
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
Definition: SlotIndexes.h:253
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::MachineRegisterInfo::use_nodbg_empty
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
Definition: MachineRegisterInfo.h:574
llvm::LiveRange::createDeadDef
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
Definition: LiveInterval.cpp:370
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:561
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1078
llvm::SparseBitVector::iterator
SparseBitVectorIterator iterator
Definition: SparseBitVector.h:442
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:364
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:548
llvm::MachineFunction::DebugPHIRegallocPos
Location of a PHI instruction that is also a debug-info variable value, for the duration of register ...
Definition: MachineFunction.h:496
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
llvm::findPHICopyInsertPoint
MachineBasicBlock::iterator findPHICopyInsertPoint(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, unsigned SrcReg)
findPHICopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg when following the CFG...
Definition: PHIEliminationUtils.cpp:21
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:288
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:364
llvm::LiveRange::endIndex
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:392
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::MachineFunctionProperties::Property::NoPHIs
@ NoPHIs
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::MachineBasicBlock::front
MachineInstr & front()
Definition: MachineBasicBlock.h:256
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::LiveRange::getVNInfoAt
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:421
llvm::LiveRange::removeSegment
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
Definition: LiveInterval.cpp:583
LiveInterval.h
llvm::SplitAllCriticalEdges
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
Definition: BasicBlockUtils.cpp:767
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:277
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:53
llvm::MachineRegisterInfo::leaveSSA
void leaveSSA()
Definition: MachineRegisterInfo.h:189
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:104
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:494
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:249
MachineOperand.h
NoPhiElimLiveOutEarlyExit
static cl::opt< bool > NoPhiElimLiveOutEarlyExit("no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden, cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."))
llvm::MachineFunction::DebugPHIPositions
DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions
Map of debug instruction numbers to the position of their PHI instructions during register allocation...
Definition: MachineFunction.h:507
llvm::LiveVariables
Definition: LiveVariables.h:47
llvm::LiveRange::removeValNo
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
Definition: LiveInterval.cpp:634
SlotIndexes.h
llvm::cl::desc
Definition: CommandLine.h:405
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
llvm::SlotIndex::isDead
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
Definition: SlotIndexes.h:235
MachineFunction.h
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:111
llvm::MachineInstr::eraseFromParent
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
Definition: MachineInstr.cpp:650
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::MachineBasicBlock::SplitCriticalEdge
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, std::vector< SparseBitVector<>> *LiveInSets=nullptr)
Split the critical edge from this block to the given successor block, and return the newly created bl...
Definition: MachineBasicBlock.cpp:1007
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:279
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:336
MachineDominators.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::LiveVariables::VarInfo::AliveBlocks
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:85