contrib/llvm/lib/CodeGen/PHIElimination.cpp

   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"
  21 #include "llvm/CodeGen/LiveInterval.h"
  22 #include "llvm/CodeGen/LiveIntervals.h"
  23 #include "llvm/CodeGen/LiveVariables.h"
  24 #include "llvm/CodeGen/MachineBasicBlock.h"
  25 #include "llvm/CodeGen/MachineDominators.h"
  26 #include "llvm/CodeGen/MachineFunction.h"
  27 #include "llvm/CodeGen/MachineFunctionPass.h"
  28 #include "llvm/CodeGen/MachineInstr.h"
  29 #include "llvm/CodeGen/MachineInstrBuilder.h"
  30 #include "llvm/CodeGen/MachineLoopInfo.h"
  31 #include "llvm/CodeGen/MachineOperand.h"
  32 #include "llvm/CodeGen/MachineRegisterInfo.h"
  33 #include "llvm/CodeGen/SlotIndexes.h"
  34 #include "llvm/CodeGen/TargetInstrInfo.h"
  35 #include "llvm/CodeGen/TargetOpcodes.h"
  36 #include "llvm/CodeGen/TargetRegisterInfo.h"
  37 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  38 #include "llvm/Pass.h"
  39 #include "llvm/Support/CommandLine.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/raw_ostream.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
  60 static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
  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) {
  75       initializePHIEliminationPass(*PassRegistry::getPassRegistry());
  76     }
  77
  78     bool runOnMachineFunction(MachineFunction &MF) 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& MF);
  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.
 111     SmallPtrSet<MachineInstr*, 4> ImpDefs;
 112
 113     // Map reusable lowered PHI node -> incoming join register.
 114     using LoweredPHIMap =
 115         DenseMap<MachineInstr*, unsigned, MachineInstrExpressionTrait>;
 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
 127 char& llvm::PHIEliminationID = PHIElimination::ID;
 128
 129 INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
 130                       "Eliminate PHI nodes for register allocation",
 131                       false, false)
 132 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
 133 INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
 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>();
 143   MachineFunctionPass::getAnalysisUsage(AU);
 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.
 157   if (!DisableEdgeSplitting && (LV || LIS)) {
 158     MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
 159     for (auto &MBB : MF)
 160       Changed |= SplitPHIEdges(MF, MBB, MLI);
 161   }
 162
 163   // Populate VRegPHIUseCount
 164   analyzePHINodes(MF);
 165
 166   // Eliminate PHI instructions by inserting copies into predecessor blocks.
 167   for (auto &MBB : MF)
 168     Changed |= EliminatePHINodes(MF, MBB);
 169
 170   // Remove dead IMPLICIT_DEF instructions.
 171   for (MachineInstr *DefMI : ImpDefs) {
 172     unsigned DefReg = DefMI->getOperand(0).getReg();
 173     if (MRI->use_nodbg_empty(DefReg)) {
 174       if (LIS)
 175         LIS->RemoveMachineInstrFromMaps(*DefMI);
 176       DefMI->eraseFromParent();
 177     }
 178   }
 179
 180   // Clean up the lowered PHI instructions.
 181   for (auto &I : LoweredPHIs) {
 182     if (LIS)
 183       LIS->RemoveMachineInstrFromMaps(*I.first);
 184     MF.DeleteMachineInstr(I.first);
 185   }
 186
 187   LoweredPHIs.clear();
 188   ImpDefs.clear();
 189   VRegPHIUseCount.clear();
 190
 191   MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
 192
 193   return Changed;
 194 }
 195
 196 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 197 /// predecessor basic blocks.
 198 bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
 199                                        MachineBasicBlock &MBB) {
 200   if (MBB.empty() || !MBB.front().isPHI())
 201     return false;   // Quick exit for basic blocks without PHIs.
 202
 203   // Get an iterator to the last PHI node.
 204   MachineBasicBlock::iterator LastPHIIt =
 205     std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
 206
 207   while (MBB.front().isPHI())
 208     LowerPHINode(MBB, LastPHIIt);
 209
 210   return true;
 211 }
 212
 213 /// Return true if all defs of VirtReg are implicit-defs.
 214 /// This includes registers with no defs.
 215 static bool isImplicitlyDefined(unsigned VirtReg,
 216                                 const MachineRegisterInfo &MRI) {
 217   for (MachineInstr &DI : MRI.def_instructions(VirtReg))
 218     if (!DI.isImplicitDef())
 219       return false;
 220   return true;
 221 }
 222
 223 /// Return true if all sources of the phi node are implicit_def's, or undef's.
 224 static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
 225                                     const MachineRegisterInfo &MRI) {
 226   for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
 227     const MachineOperand &MO = MPhi.getOperand(I);
 228     if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
 229       return false;
 230   }
 231   return true;
 232 }
 233 /// LowerPHINode - Lower the PHI node at the top of the specified block.
 234 void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
 235                                   MachineBasicBlock::iterator LastPHIIt) {
 236   ++NumLowered;
 237
 238   MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
 239
 240   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
 241   MachineInstr *MPhi = MBB.remove(&*MBB.begin());
 242
 243   unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
 244   unsigned DestReg = MPhi->getOperand(0).getReg();
 245   assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
 246   bool isDead = MPhi->getOperand(0).isDead();
 247
 248   // Create a new register for the incoming PHI arguments.
 249   MachineFunction &MF = *MBB.getParent();
 250   unsigned IncomingReg = 0;
 251   bool reusedIncoming = false;  // Is IncomingReg reused from an earlier PHI?
 252
 253   // Insert a register to register copy at the top of the current block (but
 254   // after any remaining phi nodes) which copies the new incoming register
 255   // into the phi node destination.
 256   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
 257   if (allPhiOperandsUndefined(*MPhi, *MRI))
 258     // If all sources of a PHI node are implicit_def or undef uses, just emit an
 259     // implicit_def instead of a copy.
 260     BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
 261             TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
 262   else {
 263     // Can we reuse an earlier PHI node? This only happens for critical edges,
 264     // typically those created by tail duplication.
 265     unsigned &entry = LoweredPHIs[MPhi];
 266     if (entry) {
 267       // An identical PHI node was already lowered. Reuse the incoming register.
 268       IncomingReg = entry;
 269       reusedIncoming = true;
 270       ++NumReused;
 271       LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
 272                         << *MPhi);
 273     } else {
 274       const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
 275       entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
 276     }
 277     BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
 278             TII->get(TargetOpcode::COPY), DestReg)
 279       .addReg(IncomingReg);
 280   }
 281
 282   // Update live variable information if there is any.
 283   if (LV) {
 284     MachineInstr &PHICopy = *std::prev(AfterPHIsIt);
 285
 286     if (IncomingReg) {
 287       LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
 288
 289       // Increment use count of the newly created virtual register.
 290       LV->setPHIJoin(IncomingReg);
 291
 292       // When we are reusing the incoming register, it may already have been
 293       // killed in this block. The old kill will also have been inserted at
 294       // AfterPHIsIt, so it appears before the current PHICopy.
 295       if (reusedIncoming)
 296         if (MachineInstr *OldKill = VI.findKill(&MBB)) {
 297           LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
 298           LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
 299           LLVM_DEBUG(MBB.dump());
 300         }
 301
 302       // Add information to LiveVariables to know that the incoming value is
 303       // killed.  Note that because the value is defined in several places (once
 304       // each for each incoming block), the "def" block and instruction fields
 305       // for the VarInfo is not filled in.
 306       LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
 307     }
 308
 309     // Since we are going to be deleting the PHI node, if it is the last use of
 310     // any registers, or if the value itself is dead, we need to move this
 311     // information over to the new copy we just inserted.
 312     LV->removeVirtualRegistersKilled(*MPhi);
 313
 314     // If the result is dead, update LV.
 315     if (isDead) {
 316       LV->addVirtualRegisterDead(DestReg, PHICopy);
 317       LV->removeVirtualRegisterDead(DestReg, *MPhi);
 318     }
 319   }
 320
 321   // Update LiveIntervals for the new copy or implicit def.
 322   if (LIS) {
 323     SlotIndex DestCopyIndex =
 324         LIS->InsertMachineInstrInMaps(*std::prev(AfterPHIsIt));
 325
 326     SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
 327     if (IncomingReg) {
 328       // Add the region from the beginning of MBB to the copy instruction to
 329       // IncomingReg's live interval.
 330       LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
 331       VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
 332       if (!IncomingVNI)
 333         IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
 334                                               LIS->getVNInfoAllocator());
 335       IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
 336                                                   DestCopyIndex.getRegSlot(),
 337                                                   IncomingVNI));
 338     }
 339
 340     LiveInterval &DestLI = LIS->getInterval(DestReg);
 341     assert(DestLI.begin() != DestLI.end() &&
 342            "PHIs should have nonempty LiveIntervals.");
 343     if (DestLI.endIndex().isDead()) {
 344       // A dead PHI's live range begins and ends at the start of the MBB, but
 345       // the lowered copy, which will still be dead, needs to begin and end at
 346       // the copy instruction.
 347       VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
 348       assert(OrigDestVNI && "PHI destination should be live at block entry.");
 349       DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
 350       DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
 351                            LIS->getVNInfoAllocator());
 352       DestLI.removeValNo(OrigDestVNI);
 353     } else {
 354       // Otherwise, remove the region from the beginning of MBB to the copy
 355       // instruction from DestReg's live interval.
 356       DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
 357       VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
 358       assert(DestVNI && "PHI destination should be live at its definition.");
 359       DestVNI->def = DestCopyIndex.getRegSlot();
 360     }
 361   }
 362
 363   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
 364   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
 365     --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
 366                                  MPhi->getOperand(i).getReg())];
 367
 368   // Now loop over all of the incoming arguments, changing them to copy into the
 369   // IncomingReg register in the corresponding predecessor basic block.
 370   SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
 371   for (int i = NumSrcs - 1; i >= 0; --i) {
 372     unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
 373     unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
 374     bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
 375       isImplicitlyDefined(SrcReg, *MRI);
 376     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
 377            "Machine PHI Operands must all be virtual registers!");
 378
 379     // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
 380     // path the PHI.
 381     MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
 382
 383     // Check to make sure we haven't already emitted the copy for this block.
 384     // This can happen because PHI nodes may have multiple entries for the same
 385     // basic block.
 386     if (!MBBsInsertedInto.insert(&opBlock).second)
 387       continue;  // If the copy has already been emitted, we're done.
 388
 389     // Find a safe location to insert the copy, this may be the first terminator
 390     // in the block (or end()).
 391     MachineBasicBlock::iterator InsertPos =
 392       findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
 393
 394     // Insert the copy.
 395     MachineInstr *NewSrcInstr = nullptr;
 396     if (!reusedIncoming && IncomingReg) {
 397       if (SrcUndef) {
 398         // The source register is undefined, so there is no need for a real
 399         // COPY, but we still need to ensure joint dominance by defs.
 400         // Insert an IMPLICIT_DEF instruction.
 401         NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
 402                               TII->get(TargetOpcode::IMPLICIT_DEF),
 403                               IncomingReg);
 404
 405         // Clean up the old implicit-def, if there even was one.
 406         if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
 407           if (DefMI->isImplicitDef())
 408             ImpDefs.insert(DefMI);
 409       } else {
 410         NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
 411                             TII->get(TargetOpcode::COPY), IncomingReg)
 412                         .addReg(SrcReg, 0, SrcSubReg);
 413       }
 414     }
 415
 416     // We only need to update the LiveVariables kill of SrcReg if this was the
 417     // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
 418     // out of the predecessor. We can also ignore undef sources.
 419     if (LV && !SrcUndef &&
 420         !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
 421         !LV->isLiveOut(SrcReg, opBlock)) {
 422       // We want to be able to insert a kill of the register if this PHI (aka,
 423       // the copy we just inserted) is the last use of the source value. Live
 424       // variable analysis conservatively handles this by saying that the value
 425       // is live until the end of the block the PHI entry lives in. If the value
 426       // really is dead at the PHI copy, there will be no successor blocks which
 427       // have the value live-in.
 428
 429       // Okay, if we now know that the value is not live out of the block, we
 430       // can add a kill marker in this block saying that it kills the incoming
 431       // value!
 432
 433       // In our final twist, we have to decide which instruction kills the
 434       // register.  In most cases this is the copy, however, terminator
 435       // instructions at the end of the block may also use the value. In this
 436       // case, we should mark the last such terminator as being the killing
 437       // block, not the copy.
 438       MachineBasicBlock::iterator KillInst = opBlock.end();
 439       MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
 440       for (MachineBasicBlock::iterator Term = FirstTerm;
 441           Term != opBlock.end(); ++Term) {
 442         if (Term->readsRegister(SrcReg))
 443           KillInst = Term;
 444       }
 445
 446       if (KillInst == opBlock.end()) {
 447         // No terminator uses the register.
 448
 449         if (reusedIncoming || !IncomingReg) {
 450           // We may have to rewind a bit if we didn't insert a copy this time.
 451           KillInst = FirstTerm;
 452           while (KillInst != opBlock.begin()) {
 453             --KillInst;
 454             if (KillInst->isDebugInstr())
 455               continue;
 456             if (KillInst->readsRegister(SrcReg))
 457               break;
 458           }
 459         } else {
 460           // We just inserted this copy.
 461           KillInst = std::prev(InsertPos);
 462         }
 463       }
 464       assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
 465
 466       // Finally, mark it killed.
 467       LV->addVirtualRegisterKilled(SrcReg, *KillInst);
 468
 469       // This vreg no longer lives all of the way through opBlock.
 470       unsigned opBlockNum = opBlock.getNumber();
 471       LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
 472     }
 473
 474     if (LIS) {
 475       if (NewSrcInstr) {
 476         LIS->InsertMachineInstrInMaps(*NewSrcInstr);
 477         LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
 478       }
 479
 480       if (!SrcUndef &&
 481           !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
 482         LiveInterval &SrcLI = LIS->getInterval(SrcReg);
 483
 484         bool isLiveOut = false;
 485         for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
 486              SE = opBlock.succ_end(); SI != SE; ++SI) {
 487           SlotIndex startIdx = LIS->getMBBStartIdx(*SI);
 488           VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
 489
 490           // Definitions by other PHIs are not truly live-in for our purposes.
 491           if (VNI && VNI->def != startIdx) {
 492             isLiveOut = true;
 493             break;
 494           }
 495         }
 496
 497         if (!isLiveOut) {
 498           MachineBasicBlock::iterator KillInst = opBlock.end();
 499           MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
 500           for (MachineBasicBlock::iterator Term = FirstTerm;
 501               Term != opBlock.end(); ++Term) {
 502             if (Term->readsRegister(SrcReg))
 503               KillInst = Term;
 504           }
 505
 506           if (KillInst == opBlock.end()) {
 507             // No terminator uses the register.
 508
 509             if (reusedIncoming || !IncomingReg) {
 510               // We may have to rewind a bit if we didn't just insert a copy.
 511               KillInst = FirstTerm;
 512               while (KillInst != opBlock.begin()) {
 513                 --KillInst;
 514                 if (KillInst->isDebugInstr())
 515                   continue;
 516                 if (KillInst->readsRegister(SrcReg))
 517                   break;
 518               }
 519             } else {
 520               // We just inserted this copy.
 521               KillInst = std::prev(InsertPos);
 522             }
 523           }
 524           assert(KillInst->readsRegister(SrcReg) &&
 525                  "Cannot find kill instruction");
 526
 527           SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
 528           SrcLI.removeSegment(LastUseIndex.getRegSlot(),
 529                               LIS->getMBBEndIdx(&opBlock));
 530         }
 531       }
 532     }
 533   }
 534
 535   // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
 536   if (reusedIncoming || !IncomingReg) {
 537     if (LIS)
 538       LIS->RemoveMachineInstrFromMaps(*MPhi);
 539     MF.DeleteMachineInstr(MPhi);
 540   }
 541 }
 542
 543 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 544 /// particular, we want to map the number of uses of a virtual register which is
 545 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
 546 /// used later to determine when the vreg is killed in the BB.
 547 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
 548   for (const auto &MBB : MF)
 549     for (const auto &BBI : MBB) {
 550       if (!BBI.isPHI())
 551         break;
 552       for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
 553         ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
 554                                      BBI.getOperand(i).getReg())];
 555     }
 556 }
 557
 558 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
 559                                    MachineBasicBlock &MBB,
 560                                    MachineLoopInfo *MLI) {
 561   if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
 562     return false;   // Quick exit for basic blocks without PHIs.
 563
 564   const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
 565   bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
 566
 567   bool Changed = false;
 568   for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
 569        BBI != BBE && BBI->isPHI(); ++BBI) {
 570     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
 571       unsigned Reg = BBI->getOperand(i).getReg();
 572       MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
 573       // Is there a critical edge from PreMBB to MBB?
 574       if (PreMBB->succ_size() == 1)
 575         continue;
 576
 577       // Avoid splitting backedges of loops. It would introduce small
 578       // out-of-line blocks into the loop which is very bad for code placement.
 579       if (PreMBB == &MBB && !SplitAllCriticalEdges)
 580         continue;
 581       const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
 582       if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
 583         continue;
 584
 585       // LV doesn't consider a phi use live-out, so isLiveOut only returns true
 586       // when the source register is live-out for some other reason than a phi
 587       // use. That means the copy we will insert in PreMBB won't be a kill, and
 588       // there is a risk it may not be coalesced away.
 589       //
 590       // If the copy would be a kill, there is no need to split the edge.
 591       bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
 592       if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
 593         continue;
 594       if (ShouldSplit) {
 595         LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
 596                           << printMBBReference(*PreMBB) << " -> "
 597                           << printMBBReference(MBB) << ": " << *BBI);
 598       }
 599
 600       // If Reg is not live-in to MBB, it means it must be live-in to some
 601       // other PreMBB successor, and we can avoid the interference by splitting
 602       // the edge.
 603       //
 604       // If Reg *is* live-in to MBB, the interference is inevitable and a copy
 605       // is likely to be left after coalescing. If we are looking at a loop
 606       // exiting edge, split it so we won't insert code in the loop, otherwise
 607       // don't bother.
 608       ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
 609
 610       // Check for a loop exiting edge.
 611       if (!ShouldSplit && CurLoop != PreLoop) {
 612         LLVM_DEBUG({
 613           dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
 614           if (PreLoop)
 615             dbgs() << "PreLoop: " << *PreLoop;
 616           if (CurLoop)
 617             dbgs() << "CurLoop: " << *CurLoop;
 618         });
 619         // This edge could be entering a loop, exiting a loop, or it could be
 620         // both: Jumping directly form one loop to the header of a sibling
 621         // loop.
 622         // Split unless this edge is entering CurLoop from an outer loop.
 623         ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
 624       }
 625       if (!ShouldSplit && !SplitAllCriticalEdges)
 626         continue;
 627       if (!PreMBB->SplitCriticalEdge(&MBB, *this)) {
 628         LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
 629         continue;
 630       }
 631       Changed = true;
 632       ++NumCriticalEdgesSplit;
 633     }
 634   }
 635   return Changed;
 636 }
 637
 638 bool PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock *MBB) {
 639   assert((LV || LIS) &&
 640          "isLiveIn() requires either LiveVariables or LiveIntervals");
 641   if (LIS)
 642     return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
 643   else
 644     return LV->isLiveIn(Reg, *MBB);
 645 }
 646
 647 bool PHIElimination::isLiveOutPastPHIs(unsigned Reg,
 648                                        const MachineBasicBlock *MBB) {
 649   assert((LV || LIS) &&
 650          "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
 651   // LiveVariables considers uses in PHIs to be in the predecessor basic block,
 652   // so that a register used only in a PHI is not live out of the block. In
 653   // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
 654   // in the predecessor basic block, so that a register used only in a PHI is live
 655   // out of the block.
 656   if (LIS) {
 657     const LiveInterval &LI = LIS->getInterval(Reg);
 658     for (const MachineBasicBlock *SI : MBB->successors())
 659       if (LI.liveAt(LIS->getMBBStartIdx(SI)))
 660         return true;
 661     return false;
 662   } else {
 663     return LV->isLiveOut(Reg, *MBB);
 664   }
 665 }