llvm/lib/CodeGen/PHIElimination.cpp

   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"
  20 #include "llvm/CodeGen/LiveInterval.h"
  21 #include "llvm/CodeGen/LiveIntervals.h"
  22 #include "llvm/CodeGen/LiveVariables.h"
  23 #include "llvm/CodeGen/MachineBasicBlock.h"
  24 #include "llvm/CodeGen/MachineDominators.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/CodeGen/MachineInstr.h"
  28 #include "llvm/CodeGen/MachineInstrBuilder.h"
  29 #include "llvm/CodeGen/MachineLoopInfo.h"
  30 #include "llvm/CodeGen/MachineOperand.h"
  31 #include "llvm/CodeGen/MachineRegisterInfo.h"
  32 #include "llvm/CodeGen/SlotIndexes.h"
  33 #include "llvm/CodeGen/TargetInstrInfo.h"
  34 #include "llvm/CodeGen/TargetLowering.h"
  35 #include "llvm/CodeGen/TargetOpcodes.h"
  36 #include "llvm/CodeGen/TargetPassConfig.h"
  37 #include "llvm/CodeGen/TargetRegisterInfo.h"
  38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  39 #include "llvm/Pass.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/raw_ostream.h"
  43 #include <cassert>
  44 #include <iterator>
  45 #include <utility>
  46
  47 using namespace llvm;
  48
  49 #define DEBUG_TYPE "phi-node-elimination"
  50
  51 static cl::opt<bool>
  52 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
  53                      cl::Hidden, cl::desc("Disable critical edge splitting "
  54                                           "during PHI elimination"));
  55
  56 static cl::opt<bool>
  57 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
  58                       cl::Hidden, cl::desc("Split all critical edges during "
  59                                            "PHI elimination"));
  60
  61 static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
  62     "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
  63     cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
  64
  65 namespace {
  66
  67   class PHIElimination : public MachineFunctionPass {
  68     MachineRegisterInfo *MRI; // Machine register information
  69     LiveVariables *LV;
  70     LiveIntervals *LIS;
  71
  72   public:
  73     static char ID; // Pass identification, replacement for typeid
  74
  75     PHIElimination() : MachineFunctionPass(ID) {
  76       initializePHIEliminationPass(*PassRegistry::getPassRegistry());
  77     }
  78
  79     bool runOnMachineFunction(MachineFunction &MF) override;
  80     void getAnalysisUsage(AnalysisUsage &AU) const override;
  81
  82   private:
  83     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
  84     /// in predecessor basic blocks.
  85     bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
  86
  87     void LowerPHINode(MachineBasicBlock &MBB,
  88                       MachineBasicBlock::iterator LastPHIIt);
  89
  90     /// analyzePHINodes - Gather information about the PHI nodes in
  91     /// here. In particular, we want to map the number of uses of a virtual
  92     /// register which is used in a PHI node. We map that to the BB the
  93     /// vreg is coming from. This is used later to determine when the vreg
  94     /// is killed in the BB.
  95     void analyzePHINodes(const MachineFunction& MF);
  96
  97     /// Split critical edges where necessary for good coalescer performance.
  98     bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
  99                        MachineLoopInfo *MLI,
 100                        std::vector<SparseBitVector<>> *LiveInSets);
 101
 102     // These functions are temporary abstractions around LiveVariables and
 103     // LiveIntervals, so they can go away when LiveVariables does.
 104     bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);
 105     bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);
 106
 107     using BBVRegPair = std::pair<unsigned, Register>;
 108     using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
 109
 110     // Count the number of non-undef PHI uses of each register in each BB.
 111     VRegPHIUse VRegPHIUseCount;
 112
 113     // Defs of PHI sources which are implicit_def.
 114     SmallPtrSet<MachineInstr*, 4> ImpDefs;
 115
 116     // Map reusable lowered PHI node -> incoming join register.
 117     using LoweredPHIMap =
 118         DenseMap<MachineInstr*, unsigned, MachineInstrExpressionTrait>;
 119     LoweredPHIMap LoweredPHIs;
 120   };
 121
 122 } // end anonymous namespace
 123
 124 STATISTIC(NumLowered, "Number of phis lowered");
 125 STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
 126 STATISTIC(NumReused, "Number of reused lowered phis");
 127
 128 char PHIElimination::ID = 0;
 129
 130 char& llvm::PHIEliminationID = PHIElimination::ID;
 131
 132 INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
 133                       "Eliminate PHI nodes for register allocation",
 134                       false, false)
 135 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
 136 INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
 137                     "Eliminate PHI nodes for register allocation", false, false)
 138
 139 void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
 140   AU.addUsedIfAvailable<LiveVariables>();
 141   AU.addPreserved<LiveVariables>();
 142   AU.addPreserved<SlotIndexes>();
 143   AU.addPreserved<LiveIntervals>();
 144   AU.addPreserved<MachineDominatorTree>();
 145   AU.addPreserved<MachineLoopInfo>();
 146   MachineFunctionPass::getAnalysisUsage(AU);
 147 }
 148
 149 bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
 150   MRI = &MF.getRegInfo();
 151   LV = getAnalysisIfAvailable<LiveVariables>();
 152   LIS = getAnalysisIfAvailable<LiveIntervals>();
 153
 154   bool Changed = false;
 155
 156   // Split critical edges to help the coalescer.
 157   if (!DisableEdgeSplitting && (LV || LIS)) {
 158     // A set of live-in regs for each MBB which is used to update LV
 159     // efficiently also with large functions.
 160     std::vector<SparseBitVector<>> LiveInSets;
 161     if (LV) {
 162       LiveInSets.resize(MF.size());
 163       for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
 164         // Set the bit for this register for each MBB where it is
 165         // live-through or live-in (killed).
 166         unsigned VirtReg = Register::index2VirtReg(Index);
 167         MachineInstr *DefMI = MRI->getVRegDef(VirtReg);
 168         if (!DefMI)
 169           continue;
 170         LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);
 171         SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();
 172         SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();
 173         while (AliveBlockItr != EndItr) {
 174           unsigned BlockNum = *(AliveBlockItr++);
 175           LiveInSets[BlockNum].set(Index);
 176         }
 177         // The register is live into an MBB in which it is killed but not
 178         // defined. See comment for VarInfo in LiveVariables.h.
 179         MachineBasicBlock *DefMBB = DefMI->getParent();
 180         if (VI.Kills.size() > 1 ||
 181             (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
 182           for (auto *MI : VI.Kills)
 183             LiveInSets[MI->getParent()->getNumber()].set(Index);
 184       }
 185     }
 186
 187     MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
 188     for (auto &MBB : MF)
 189       Changed |= SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr));
 190   }
 191
 192   // This pass takes the function out of SSA form.
 193   MRI->leaveSSA();
 194
 195   // Populate VRegPHIUseCount
 196   analyzePHINodes(MF);
 197
 198   // Eliminate PHI instructions by inserting copies into predecessor blocks.
 199   for (auto &MBB : MF)
 200     Changed |= EliminatePHINodes(MF, MBB);
 201
 202   // Remove dead IMPLICIT_DEF instructions.
 203   for (MachineInstr *DefMI : ImpDefs) {
 204     Register DefReg = DefMI->getOperand(0).getReg();
 205     if (MRI->use_nodbg_empty(DefReg)) {
 206       if (LIS)
 207         LIS->RemoveMachineInstrFromMaps(*DefMI);
 208       DefMI->eraseFromParent();
 209     }
 210   }
 211
 212   // Clean up the lowered PHI instructions.
 213   for (auto &I : LoweredPHIs) {
 214     if (LIS)
 215       LIS->RemoveMachineInstrFromMaps(*I.first);
 216     MF.deleteMachineInstr(I.first);
 217   }
 218
 219   // TODO: we should use the incremental DomTree updater here.
 220   if (Changed)
 221     if (auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>())
 222       MDT->getBase().recalculate(MF);
 223
 224   LoweredPHIs.clear();
 225   ImpDefs.clear();
 226   VRegPHIUseCount.clear();
 227
 228   MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
 229
 230   return Changed;
 231 }
 232
 233 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 234 /// predecessor basic blocks.
 235 bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
 236                                        MachineBasicBlock &MBB) {
 237   if (MBB.empty() || !MBB.front().isPHI())
 238     return false;   // Quick exit for basic blocks without PHIs.
 239
 240   // Get an iterator to the last PHI node.
 241   MachineBasicBlock::iterator LastPHIIt =
 242     std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
 243
 244   while (MBB.front().isPHI())
 245     LowerPHINode(MBB, LastPHIIt);
 246
 247   return true;
 248 }
 249
 250 /// Return true if all defs of VirtReg are implicit-defs.
 251 /// This includes registers with no defs.
 252 static bool isImplicitlyDefined(unsigned VirtReg,
 253                                 const MachineRegisterInfo &MRI) {
 254   for (MachineInstr &DI : MRI.def_instructions(VirtReg))
 255     if (!DI.isImplicitDef())
 256       return false;
 257   return true;
 258 }
 259
 260 /// Return true if all sources of the phi node are implicit_def's, or undef's.
 261 static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
 262                                     const MachineRegisterInfo &MRI) {
 263   for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
 264     const MachineOperand &MO = MPhi.getOperand(I);
 265     if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
 266       return false;
 267   }
 268   return true;
 269 }
 270 /// LowerPHINode - Lower the PHI node at the top of the specified block.
 271 void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
 272                                   MachineBasicBlock::iterator LastPHIIt) {
 273   ++NumLowered;
 274
 275   MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
 276
 277   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
 278   MachineInstr *MPhi = MBB.remove(&*MBB.begin());
 279
 280   unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
 281   Register DestReg = MPhi->getOperand(0).getReg();
 282   assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
 283   bool isDead = MPhi->getOperand(0).isDead();
 284
 285   // Create a new register for the incoming PHI arguments.
 286   MachineFunction &MF = *MBB.getParent();
 287   unsigned IncomingReg = 0;
 288   bool reusedIncoming = false;  // Is IncomingReg reused from an earlier PHI?
 289
 290   // Insert a register to register copy at the top of the current block (but
 291   // after any remaining phi nodes) which copies the new incoming register
 292   // into the phi node destination.
 293   MachineInstr *PHICopy = nullptr;
 294   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
 295   if (allPhiOperandsUndefined(*MPhi, *MRI))
 296     // If all sources of a PHI node are implicit_def or undef uses, just emit an
 297     // implicit_def instead of a copy.
 298     PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
 299             TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
 300   else {
 301     // Can we reuse an earlier PHI node? This only happens for critical edges,
 302     // typically those created by tail duplication.
 303     unsigned &entry = LoweredPHIs[MPhi];
 304     if (entry) {
 305       // An identical PHI node was already lowered. Reuse the incoming register.
 306       IncomingReg = entry;
 307       reusedIncoming = true;
 308       ++NumReused;
 309       LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
 310                         << *MPhi);
 311     } else {
 312       const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
 313       entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
 314     }
 315     // Give the target possiblity to handle special cases fallthrough otherwise
 316     PHICopy = TII->createPHIDestinationCopy(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
 317                                   IncomingReg, DestReg);
 318   }
 319
 320   if (MPhi->peekDebugInstrNum()) {
 321     // If referred to by debug-info, store where this PHI was.
 322     MachineFunction *MF = MBB.getParent();
 323     unsigned ID = MPhi->peekDebugInstrNum();
 324     auto P = MachineFunction::DebugPHIRegallocPos(&MBB, IncomingReg, 0);
 325     auto Res = MF->DebugPHIPositions.insert({ID, P});
 326     assert(Res.second);
 327     (void)Res;
 328   }
 329
 330   // Update live variable information if there is any.
 331   if (LV) {
 332     if (IncomingReg) {
 333       LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
 334
 335       // Increment use count of the newly created virtual register.
 336       LV->setPHIJoin(IncomingReg);
 337
 338       MachineInstr *OldKill = nullptr;
 339       bool IsPHICopyAfterOldKill = false;
 340
 341       if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
 342         // Calculate whether the PHICopy is after the OldKill.
 343         // In general, the PHICopy is inserted as the first non-phi instruction
 344         // by default, so it's before the OldKill. But some Target hooks for
 345         // createPHIDestinationCopy() may modify the default insert position of
 346         // PHICopy.
 347         for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
 348              I != E; ++I) {
 349           if (I == PHICopy)
 350             break;
 351
 352           if (I == OldKill) {
 353             IsPHICopyAfterOldKill = true;
 354             break;
 355           }
 356         }
 357       }
 358
 359       // When we are reusing the incoming register and it has been marked killed
 360       // by OldKill, if the PHICopy is after the OldKill, we should remove the
 361       // killed flag from OldKill.
 362       if (IsPHICopyAfterOldKill) {
 363         LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
 364         LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
 365         LLVM_DEBUG(MBB.dump());
 366       }
 367
 368       // Add information to LiveVariables to know that the first used incoming
 369       // value or the resued incoming value whose PHICopy is after the OldKIll
 370       // is killed. Note that because the value is defined in several places
 371       // (once each for each incoming block), the "def" block and instruction
 372       // fields for the VarInfo is not filled in.
 373       if (!OldKill || IsPHICopyAfterOldKill)
 374         LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
 375     }
 376
 377     // Since we are going to be deleting the PHI node, if it is the last use of
 378     // any registers, or if the value itself is dead, we need to move this
 379     // information over to the new copy we just inserted.
 380     LV->removeVirtualRegistersKilled(*MPhi);
 381
 382     // If the result is dead, update LV.
 383     if (isDead) {
 384       LV->addVirtualRegisterDead(DestReg, *PHICopy);
 385       LV->removeVirtualRegisterDead(DestReg, *MPhi);
 386     }
 387   }
 388
 389   // Update LiveIntervals for the new copy or implicit def.
 390   if (LIS) {
 391     SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
 392
 393     SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
 394     if (IncomingReg) {
 395       // Add the region from the beginning of MBB to the copy instruction to
 396       // IncomingReg's live interval.
 397       LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
 398       VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
 399       if (!IncomingVNI)
 400         IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
 401                                               LIS->getVNInfoAllocator());
 402       IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
 403                                                   DestCopyIndex.getRegSlot(),
 404                                                   IncomingVNI));
 405     }
 406
 407     LiveInterval &DestLI = LIS->getInterval(DestReg);
 408     assert(!DestLI.empty() && "PHIs should have nonempty LiveIntervals.");
 409     if (DestLI.endIndex().isDead()) {
 410       // A dead PHI's live range begins and ends at the start of the MBB, but
 411       // the lowered copy, which will still be dead, needs to begin and end at
 412       // the copy instruction.
 413       VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
 414       assert(OrigDestVNI && "PHI destination should be live at block entry.");
 415       DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
 416       DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
 417                            LIS->getVNInfoAllocator());
 418       DestLI.removeValNo(OrigDestVNI);
 419     } else {
 420       // Otherwise, remove the region from the beginning of MBB to the copy
 421       // instruction from DestReg's live interval.
 422       DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
 423       VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
 424       assert(DestVNI && "PHI destination should be live at its definition.");
 425       DestVNI->def = DestCopyIndex.getRegSlot();
 426     }
 427   }
 428
 429   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
 430   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
 431     if (!MPhi->getOperand(i).isUndef()) {
 432       --VRegPHIUseCount[BBVRegPair(
 433           MPhi->getOperand(i + 1).getMBB()->getNumber(),
 434           MPhi->getOperand(i).getReg())];
 435     }
 436   }
 437
 438   // Now loop over all of the incoming arguments, changing them to copy into the
 439   // IncomingReg register in the corresponding predecessor basic block.
 440   SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
 441   for (int i = NumSrcs - 1; i >= 0; --i) {
 442     Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
 443     unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
 444     bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
 445       isImplicitlyDefined(SrcReg, *MRI);
 446     assert(Register::isVirtualRegister(SrcReg) &&
 447            "Machine PHI Operands must all be virtual registers!");
 448
 449     // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
 450     // path the PHI.
 451     MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
 452
 453     // Check to make sure we haven't already emitted the copy for this block.
 454     // This can happen because PHI nodes may have multiple entries for the same
 455     // basic block.
 456     if (!MBBsInsertedInto.insert(&opBlock).second)
 457       continue;  // If the copy has already been emitted, we're done.
 458
 459     MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
 460     if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
 461       assert(SrcRegDef->getOperand(0).isReg() &&
 462              SrcRegDef->getOperand(0).isDef() &&
 463              "Expected operand 0 to be a reg def!");
 464       // Now that the PHI's use has been removed (as the instruction was
 465       // removed) there should be no other uses of the SrcReg.
 466       assert(MRI->use_empty(SrcReg) &&
 467              "Expected a single use from UnspillableTerminator");
 468       SrcRegDef->getOperand(0).setReg(IncomingReg);
 469
 470       // Update LiveVariables.
 471       if (LV) {
 472         LiveVariables::VarInfo &SrcVI = LV->getVarInfo(SrcReg);
 473         LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(IncomingReg);
 474         IncomingVI.AliveBlocks = std::move(SrcVI.AliveBlocks);
 475         SrcVI.AliveBlocks.clear();
 476       }
 477
 478       continue;
 479     }
 480
 481     // Find a safe location to insert the copy, this may be the first terminator
 482     // in the block (or end()).
 483     MachineBasicBlock::iterator InsertPos =
 484       findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
 485
 486     // Insert the copy.
 487     MachineInstr *NewSrcInstr = nullptr;
 488     if (!reusedIncoming && IncomingReg) {
 489       if (SrcUndef) {
 490         // The source register is undefined, so there is no need for a real
 491         // COPY, but we still need to ensure joint dominance by defs.
 492         // Insert an IMPLICIT_DEF instruction.
 493         NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
 494                               TII->get(TargetOpcode::IMPLICIT_DEF),
 495                               IncomingReg);
 496
 497         // Clean up the old implicit-def, if there even was one.
 498         if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
 499           if (DefMI->isImplicitDef())
 500             ImpDefs.insert(DefMI);
 501       } else {
 502         // Delete the debug location, since the copy is inserted into a
 503         // different basic block.
 504         NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,
 505                                                SrcReg, SrcSubReg, IncomingReg);
 506       }
 507     }
 508
 509     // We only need to update the LiveVariables kill of SrcReg if this was the
 510     // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
 511     // out of the predecessor. We can also ignore undef sources.
 512     if (LV && !SrcUndef &&
 513         !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
 514         !LV->isLiveOut(SrcReg, opBlock)) {
 515       // We want to be able to insert a kill of the register if this PHI (aka,
 516       // the copy we just inserted) is the last use of the source value. Live
 517       // variable analysis conservatively handles this by saying that the value
 518       // is live until the end of the block the PHI entry lives in. If the value
 519       // really is dead at the PHI copy, there will be no successor blocks which
 520       // have the value live-in.
 521
 522       // Okay, if we now know that the value is not live out of the block, we
 523       // can add a kill marker in this block saying that it kills the incoming
 524       // value!
 525
 526       // In our final twist, we have to decide which instruction kills the
 527       // register.  In most cases this is the copy, however, terminator
 528       // instructions at the end of the block may also use the value. In this
 529       // case, we should mark the last such terminator as being the killing
 530       // block, not the copy.
 531       MachineBasicBlock::iterator KillInst = opBlock.end();
 532       for (MachineBasicBlock::iterator Term = InsertPos; Term != opBlock.end();
 533            ++Term) {
 534         if (Term->readsRegister(SrcReg))
 535           KillInst = Term;
 536       }
 537
 538       if (KillInst == opBlock.end()) {
 539         // No terminator uses the register.
 540
 541         if (reusedIncoming || !IncomingReg) {
 542           // We may have to rewind a bit if we didn't insert a copy this time.
 543           KillInst = InsertPos;
 544           while (KillInst != opBlock.begin()) {
 545             --KillInst;
 546             if (KillInst->isDebugInstr())
 547               continue;
 548             if (KillInst->readsRegister(SrcReg))
 549               break;
 550           }
 551         } else {
 552           // We just inserted this copy.
 553           KillInst = NewSrcInstr;
 554         }
 555       }
 556       assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
 557
 558       // Finally, mark it killed.
 559       LV->addVirtualRegisterKilled(SrcReg, *KillInst);
 560
 561       // This vreg no longer lives all of the way through opBlock.
 562       unsigned opBlockNum = opBlock.getNumber();
 563       LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
 564     }
 565
 566     if (LIS) {
 567       if (NewSrcInstr) {
 568         LIS->InsertMachineInstrInMaps(*NewSrcInstr);
 569         LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
 570       }
 571
 572       if (!SrcUndef &&
 573           !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
 574         LiveInterval &SrcLI = LIS->getInterval(SrcReg);
 575
 576         bool isLiveOut = false;
 577         for (MachineBasicBlock *Succ : opBlock.successors()) {
 578           SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
 579           VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
 580
 581           // Definitions by other PHIs are not truly live-in for our purposes.
 582           if (VNI && VNI->def != startIdx) {
 583             isLiveOut = true;
 584             break;
 585           }
 586         }
 587
 588         if (!isLiveOut) {
 589           MachineBasicBlock::iterator KillInst = opBlock.end();
 590           for (MachineBasicBlock::iterator Term = InsertPos;
 591                Term != opBlock.end(); ++Term) {
 592             if (Term->readsRegister(SrcReg))
 593               KillInst = Term;
 594           }
 595
 596           if (KillInst == opBlock.end()) {
 597             // No terminator uses the register.
 598
 599             if (reusedIncoming || !IncomingReg) {
 600               // We may have to rewind a bit if we didn't just insert a copy.
 601               KillInst = InsertPos;
 602               while (KillInst != opBlock.begin()) {
 603                 --KillInst;
 604                 if (KillInst->isDebugInstr())
 605                   continue;
 606                 if (KillInst->readsRegister(SrcReg))
 607                   break;
 608               }
 609             } else {
 610               // We just inserted this copy.
 611               KillInst = std::prev(InsertPos);
 612             }
 613           }
 614           assert(KillInst->readsRegister(SrcReg) &&
 615                  "Cannot find kill instruction");
 616
 617           SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
 618           SrcLI.removeSegment(LastUseIndex.getRegSlot(),
 619                               LIS->getMBBEndIdx(&opBlock));
 620         }
 621       }
 622     }
 623   }
 624
 625   // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
 626   if (reusedIncoming || !IncomingReg) {
 627     if (LIS)
 628       LIS->RemoveMachineInstrFromMaps(*MPhi);
 629     MF.deleteMachineInstr(MPhi);
 630   }
 631 }
 632
 633 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 634 /// particular, we want to map the number of uses of a virtual register which is
 635 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
 636 /// used later to determine when the vreg is killed in the BB.
 637 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
 638   for (const auto &MBB : MF) {
 639     for (const auto &BBI : MBB) {
 640       if (!BBI.isPHI())
 641         break;
 642       for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
 643         if (!BBI.getOperand(i).isUndef()) {
 644           ++VRegPHIUseCount[BBVRegPair(
 645               BBI.getOperand(i + 1).getMBB()->getNumber(),
 646               BBI.getOperand(i).getReg())];
 647         }
 648       }
 649     }
 650   }
 651 }
 652
 653 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
 654                                    MachineBasicBlock &MBB,
 655                                    MachineLoopInfo *MLI,
 656                                    std::vector<SparseBitVector<>> *LiveInSets) {
 657   if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
 658     return false;   // Quick exit for basic blocks without PHIs.
 659
 660   const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
 661   bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
 662
 663   bool Changed = false;
 664   for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
 665        BBI != BBE && BBI->isPHI(); ++BBI) {
 666     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
 667       Register Reg = BBI->getOperand(i).getReg();
 668       MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
 669       // Is there a critical edge from PreMBB to MBB?
 670       if (PreMBB->succ_size() == 1)
 671         continue;
 672
 673       // Avoid splitting backedges of loops. It would introduce small
 674       // out-of-line blocks into the loop which is very bad for code placement.
 675       if (PreMBB == &MBB && !SplitAllCriticalEdges)
 676         continue;
 677       const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
 678       if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
 679         continue;
 680
 681       // LV doesn't consider a phi use live-out, so isLiveOut only returns true
 682       // when the source register is live-out for some other reason than a phi
 683       // use. That means the copy we will insert in PreMBB won't be a kill, and
 684       // there is a risk it may not be coalesced away.
 685       //
 686       // If the copy would be a kill, there is no need to split the edge.
 687       bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
 688       if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
 689         continue;
 690       if (ShouldSplit) {
 691         LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
 692                           << printMBBReference(*PreMBB) << " -> "
 693                           << printMBBReference(MBB) << ": " << *BBI);
 694       }
 695
 696       // If Reg is not live-in to MBB, it means it must be live-in to some
 697       // other PreMBB successor, and we can avoid the interference by splitting
 698       // the edge.
 699       //
 700       // If Reg *is* live-in to MBB, the interference is inevitable and a copy
 701       // is likely to be left after coalescing. If we are looking at a loop
 702       // exiting edge, split it so we won't insert code in the loop, otherwise
 703       // don't bother.
 704       ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
 705
 706       // Check for a loop exiting edge.
 707       if (!ShouldSplit && CurLoop != PreLoop) {
 708         LLVM_DEBUG({
 709           dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
 710           if (PreLoop)
 711             dbgs() << "PreLoop: " << *PreLoop;
 712           if (CurLoop)
 713             dbgs() << "CurLoop: " << *CurLoop;
 714         });
 715         // This edge could be entering a loop, exiting a loop, or it could be
 716         // both: Jumping directly form one loop to the header of a sibling
 717         // loop.
 718         // Split unless this edge is entering CurLoop from an outer loop.
 719         ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
 720       }
 721       if (!ShouldSplit && !SplitAllCriticalEdges)
 722         continue;
 723       if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
 724         LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
 725         continue;
 726       }
 727       Changed = true;
 728       ++NumCriticalEdgesSplit;
 729     }
 730   }
 731   return Changed;
 732 }
 733
 734 bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
 735   assert((LV || LIS) &&
 736          "isLiveIn() requires either LiveVariables or LiveIntervals");
 737   if (LIS)
 738     return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
 739   else
 740     return LV->isLiveIn(Reg, *MBB);
 741 }
 742
 743 bool PHIElimination::isLiveOutPastPHIs(Register Reg,
 744                                        const MachineBasicBlock *MBB) {
 745   assert((LV || LIS) &&
 746          "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
 747   // LiveVariables considers uses in PHIs to be in the predecessor basic block,
 748   // so that a register used only in a PHI is not live out of the block. In
 749   // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
 750   // in the predecessor basic block, so that a register used only in a PHI is live
 751   // out of the block.
 752   if (LIS) {
 753     const LiveInterval &LI = LIS->getInterval(Reg);
 754     for (const MachineBasicBlock *SI : MBB->successors())
 755       if (LI.liveAt(LIS->getMBBStartIdx(SI)))
 756         return true;
 757     return false;
 758   } else {
 759     return LV->isLiveOut(Reg, *MBB);
 760   }
 761 }