LCOV - code coverage report
Current view: top level - lib/CodeGen - PHIElimination.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 121 212 57.1 %
Date: 2018-10-20 13:21:21 Functions: 9 13 69.2 %
Legend: Lines: hit not hit

          Line data    Source code
       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       27456 :     PHIElimination() : MachineFunctionPass(ID) {
      75       27456 :       initializePHIEliminationPass(*PassRegistry::getPassRegistry());
      76       27456 :     }
      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       31780 : INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
     130             :                       "Eliminate PHI nodes for register allocation",
     131             :                       false, false)
     132       31780 : INITIALIZE_PASS_DEPENDENCY(LiveVariables)
     133      112603 : INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
     134             :                     "Eliminate PHI nodes for register allocation", false, false)
     135             : 
     136       27262 : 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       27262 :   MachineFunctionPass::getAnalysisUsage(AU);
     144       27262 : }
     145             : 
     146      406008 : bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
     147      406008 :   MRI = &MF.getRegInfo();
     148      406008 :   LV = getAnalysisIfAvailable<LiveVariables>();
     149      406008 :   LIS = getAnalysisIfAvailable<LiveIntervals>();
     150             : 
     151             :   bool Changed = false;
     152             : 
     153             :   // This pass takes the function out of SSA form.
     154      406008 :   MRI->leaveSSA();
     155             : 
     156             :   // Split critical edges to help the coalescer.
     157      406008 :   if (!DisableEdgeSplitting && (LV || LIS)) {
     158      197886 :     MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
     159      655888 :     for (auto &MBB : MF)
     160      458002 :       Changed |= SplitPHIEdges(MF, MBB, MLI);
     161             :   }
     162             : 
     163             :   // Populate VRegPHIUseCount
     164      406008 :   analyzePHINodes(MF);
     165             : 
     166             :   // Eliminate PHI instructions by inserting copies into predecessor blocks.
     167     3691595 :   for (auto &MBB : MF)
     168     3285587 :     Changed |= EliminatePHINodes(MF, MBB);
     169             : 
     170             :   // Remove dead IMPLICIT_DEF instructions.
     171      406026 :   for (MachineInstr *DefMI : ImpDefs) {
     172          18 :     unsigned DefReg = DefMI->getOperand(0).getReg();
     173          18 :     if (MRI->use_nodbg_empty(DefReg)) {
     174          18 :       if (LIS)
     175           0 :         LIS->RemoveMachineInstrFromMaps(*DefMI);
     176          18 :       DefMI->eraseFromParent();
     177             :     }
     178             :   }
     179             : 
     180             :   // Clean up the lowered PHI instructions.
     181     1009767 :   for (auto &I : LoweredPHIs) {
     182      197751 :     if (LIS)
     183           0 :       LIS->RemoveMachineInstrFromMaps(*I.first);
     184      197751 :     MF.DeleteMachineInstr(I.first);
     185             :   }
     186             : 
     187      406008 :   LoweredPHIs.clear();
     188      406008 :   ImpDefs.clear();
     189      406008 :   VRegPHIUseCount.clear();
     190             : 
     191             :   MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
     192             : 
     193      406008 :   return Changed;
     194             : }
     195             : 
     196             : /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
     197             : /// predecessor basic blocks.
     198           0 : bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
     199             :                                        MachineBasicBlock &MBB) {
     200           0 :   if (MBB.empty() || !MBB.front().isPHI())
     201           0 :     return false;   // Quick exit for basic blocks without PHIs.
     202             : 
     203             :   // Get an iterator to the last PHI node.
     204             :   MachineBasicBlock::iterator LastPHIIt =
     205           0 :     std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
     206             : 
     207           0 :   while (MBB.front().isPHI())
     208           0 :     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      622512 : static bool isImplicitlyDefined(unsigned VirtReg,
     216             :                                 const MachineRegisterInfo &MRI) {
     217      622585 :   for (MachineInstr &DI : MRI.def_instructions(VirtReg))
     218      620937 :     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      198109 : static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
     225             :                                     const MachineRegisterInfo &MRI) {
     226      199723 :   for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
     227      199719 :     const MachineOperand &MO = MPhi.getOperand(I);
     228      199719 :     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      198109 : void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
     235             :                                   MachineBasicBlock::iterator LastPHIIt) {
     236             :   ++NumLowered;
     237             : 
     238      198109 :   MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
     239             : 
     240             :   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
     241      198109 :   MachineInstr *MPhi = MBB.remove(&*MBB.begin());
     242             : 
     243      198109 :   unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
     244      198109 :   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      198109 :   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      198109 :   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
     257      198109 :   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          12 :             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      198105 :     unsigned &entry = LoweredPHIs[MPhi];
     266      198105 :     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      197751 :       const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
     275      197751 :       entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
     276             :     }
     277      198105 :     BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
     278      594315 :             TII->get(TargetOpcode::COPY), DestReg)
     279      198105 :       .addReg(IncomingReg);
     280             :   }
     281             : 
     282             :   // Update live variable information if there is any.
     283      198109 :   if (LV) {
     284       86231 :     MachineInstr &PHICopy = *std::prev(AfterPHIsIt);
     285             : 
     286       86231 :     if (IncomingReg) {
     287       86228 :       LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
     288             : 
     289             :       // Increment use count of the newly created virtual register.
     290       86228 :       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       86228 :       if (reusedIncoming)
     296         352 :         if (MachineInstr *OldKill = VI.findKill(&MBB)) {
     297             :           LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
     298          40 :           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       86228 :       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       86231 :     LV->removeVirtualRegistersKilled(*MPhi);
     313             : 
     314             :     // If the result is dead, update LV.
     315       86231 :     if (isDead) {
     316           3 :       LV->addVirtualRegisterDead(DestReg, PHICopy);
     317           3 :       LV->removeVirtualRegisterDead(DestReg, *MPhi);
     318             :     }
     319             :   }
     320             : 
     321             :   // Update LiveIntervals for the new copy or implicit def.
     322      198109 :   if (LIS) {
     323             :     SlotIndex DestCopyIndex =
     324           0 :         LIS->InsertMachineInstrInMaps(*std::prev(AfterPHIsIt));
     325             : 
     326           0 :     SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
     327           0 :     if (IncomingReg) {
     328             :       // Add the region from the beginning of MBB to the copy instruction to
     329             :       // IncomingReg's live interval.
     330           0 :       LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
     331           0 :       VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
     332           0 :       if (!IncomingVNI)
     333           0 :         IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
     334           0 :                                               LIS->getVNInfoAllocator());
     335           0 :       IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
     336             :                                                   DestCopyIndex.getRegSlot(),
     337             :                                                   IncomingVNI));
     338             :     }
     339             : 
     340           0 :     LiveInterval &DestLI = LIS->getInterval(DestReg);
     341             :     assert(DestLI.begin() != DestLI.end() &&
     342             :            "PHIs should have nonempty LiveIntervals.");
     343           0 :     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           0 :       VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
     348             :       assert(OrigDestVNI && "PHI destination should be live at block entry.");
     349           0 :       DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
     350           0 :       DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
     351           0 :                            LIS->getVNInfoAllocator());
     352           0 :       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           0 :       DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
     357           0 :       VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
     358             :       assert(DestVNI && "PHI destination should be live at its definition.");
     359           0 :       DestVNI->def = DestCopyIndex.getRegSlot();
     360             :     }
     361             :   }
     362             : 
     363             :   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
     364      622632 :   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
     365      849046 :     --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
     366      849046 :                                  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      622632 :   for (int i = NumSrcs - 1; i >= 0; --i) {
     372      849046 :     unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
     373             :     unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
     374      847316 :     bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
     375      422793 :       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      424523 :     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      424523 :     if (!MBBsInsertedInto.insert(&opBlock).second)
     387          72 :       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      424451 :       findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
     393             : 
     394             :     // Insert the copy.
     395             :     MachineInstr *NewSrcInstr = nullptr;
     396      424451 :     if (!reusedIncoming && IncomingReg) {
     397      423452 :       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        1737 :         NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
     402             :                               TII->get(TargetOpcode::IMPLICIT_DEF),
     403        5211 :                               IncomingReg);
     404             : 
     405             :         // Clean up the old implicit-def, if there even was one.
     406        1737 :         if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
     407          34 :           if (DefMI->isImplicitDef())
     408          34 :             ImpDefs.insert(DefMI);
     409             :       } else {
     410      421715 :         NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
     411     1265145 :                             TII->get(TargetOpcode::COPY), IncomingReg)
     412      421715 :                         .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      195681 :     if (LV && !SrcUndef &&
     420     1003836 :         !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
     421      189753 :         !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      177938 :       MachineBasicBlock::iterator KillInst = opBlock.end();
     439      177938 :       MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
     440      177938 :       for (MachineBasicBlock::iterator Term = FirstTerm;
     441      308485 :           Term != opBlock.end(); ++Term) {
     442      130547 :         if (Term->readsRegister(SrcReg))
     443          39 :           KillInst = Term;
     444             :       }
     445             : 
     446      177938 :       if (KillInst == opBlock.end()) {
     447             :         // No terminator uses the register.
     448             : 
     449      177899 :         if (reusedIncoming || !IncomingReg) {
     450             :           // We may have to rewind a bit if we didn't insert a copy this time.
     451         637 :           KillInst = FirstTerm;
     452        2193 :           while (KillInst != opBlock.begin()) {
     453             :             --KillInst;
     454             :             if (KillInst->isDebugInstr())
     455             :               continue;
     456        2193 :             if (KillInst->readsRegister(SrcReg))
     457             :               break;
     458             :           }
     459             :         } else {
     460             :           // We just inserted this copy.
     461      177262 :           KillInst = std::prev(InsertPos);
     462             :         }
     463             :       }
     464             :       assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
     465             : 
     466             :       // Finally, mark it killed.
     467      355876 :       LV->addVirtualRegisterKilled(SrcReg, *KillInst);
     468             : 
     469             :       // This vreg no longer lives all of the way through opBlock.
     470      177938 :       unsigned opBlockNum = opBlock.getNumber();
     471      177938 :       LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
     472             :     }
     473             : 
     474      424451 :     if (LIS) {
     475           0 :       if (NewSrcInstr) {
     476           0 :         LIS->InsertMachineInstrInMaps(*NewSrcInstr);
     477           0 :         LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
     478             :       }
     479             : 
     480           0 :       if (!SrcUndef &&
     481           0 :           !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
     482           0 :         LiveInterval &SrcLI = LIS->getInterval(SrcReg);
     483             : 
     484             :         bool isLiveOut = false;
     485             :         for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
     486           0 :              SE = opBlock.succ_end(); SI != SE; ++SI) {
     487           0 :           SlotIndex startIdx = LIS->getMBBStartIdx(*SI);
     488           0 :           VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
     489             : 
     490             :           // Definitions by other PHIs are not truly live-in for our purposes.
     491           0 :           if (VNI && VNI->def != startIdx) {
     492             :             isLiveOut = true;
     493             :             break;
     494             :           }
     495             :         }
     496             : 
     497             :         if (!isLiveOut) {
     498           0 :           MachineBasicBlock::iterator KillInst = opBlock.end();
     499           0 :           MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
     500           0 :           for (MachineBasicBlock::iterator Term = FirstTerm;
     501           0 :               Term != opBlock.end(); ++Term) {
     502           0 :             if (Term->readsRegister(SrcReg))
     503           0 :               KillInst = Term;
     504             :           }
     505             : 
     506           0 :           if (KillInst == opBlock.end()) {
     507             :             // No terminator uses the register.
     508             : 
     509           0 :             if (reusedIncoming || !IncomingReg) {
     510             :               // We may have to rewind a bit if we didn't just insert a copy.
     511           0 :               KillInst = FirstTerm;
     512           0 :               while (KillInst != opBlock.begin()) {
     513             :                 --KillInst;
     514             :                 if (KillInst->isDebugInstr())
     515             :                   continue;
     516           0 :                 if (KillInst->readsRegister(SrcReg))
     517             :                   break;
     518             :               }
     519             :             } else {
     520             :               // We just inserted this copy.
     521           0 :               KillInst = std::prev(InsertPos);
     522             :             }
     523             :           }
     524             :           assert(KillInst->readsRegister(SrcReg) &&
     525             :                  "Cannot find kill instruction");
     526             : 
     527           0 :           SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
     528           0 :           SrcLI.removeSegment(LastUseIndex.getRegSlot(),
     529           0 :                               LIS->getMBBEndIdx(&opBlock));
     530             :         }
     531             :       }
     532             :     }
     533             :   }
     534             : 
     535             :   // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
     536      198109 :   if (reusedIncoming || !IncomingReg) {
     537         358 :     if (LIS)
     538           0 :       LIS->RemoveMachineInstrFromMaps(*MPhi);
     539         358 :     MF.DeleteMachineInstr(MPhi);
     540             :   }
     541      198109 : }
     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      406008 : void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
     548     3691595 :   for (const auto &MBB : MF)
     549     3483696 :     for (const auto &BBI : MBB) {
     550             :       if (!BBI.isPHI())
     551             :         break;
     552      622632 :       for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
     553      849046 :         ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
     554      849046 :                                      BBI.getOperand(i).getReg())];
     555             :     }
     556      406008 : }
     557             : 
     558           0 : bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
     559             :                                    MachineBasicBlock &MBB,
     560             :                                    MachineLoopInfo *MLI) {
     561           0 :   if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
     562           0 :     return false;   // Quick exit for basic blocks without PHIs.
     563             : 
     564           0 :   const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
     565           0 :   bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
     566             : 
     567             :   bool Changed = false;
     568             :   for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
     569           0 :        BBI != BBE && BBI->isPHI(); ++BBI) {
     570           0 :     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
     571           0 :       unsigned Reg = BBI->getOperand(i).getReg();
     572           0 :       MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
     573             :       // Is there a critical edge from PreMBB to MBB?
     574           0 :       if (PreMBB->succ_size() == 1)
     575           0 :         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           0 :       if (PreMBB == &MBB && !SplitAllCriticalEdges)
     580           0 :         continue;
     581           0 :       const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
     582           0 :       if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
     583           0 :         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           0 :       bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
     592           0 :       if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
     593           0 :         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           0 :       ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
     609             : 
     610             :       // Check for a loop exiting edge.
     611           0 :       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           0 :         ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
     624             :       }
     625           0 :       if (!ShouldSplit && !SplitAllCriticalEdges)
     626           0 :         continue;
     627           0 :       if (!PreMBB->SplitCriticalEdge(&MBB, *this)) {
     628             :         LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
     629           0 :         continue;
     630             :       }
     631             :       Changed = true;
     632             :       ++NumCriticalEdgesSplit;
     633             :     }
     634             :   }
     635             :   return Changed;
     636             : }
     637             : 
     638           0 : bool PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock *MBB) {
     639             :   assert((LV || LIS) &&
     640             :          "isLiveIn() requires either LiveVariables or LiveIntervals");
     641           0 :   if (LIS)
     642           0 :     return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
     643             :   else
     644           0 :     return LV->isLiveIn(Reg, *MBB);
     645             : }
     646             : 
     647           0 : 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           0 :   if (LIS) {
     657           0 :     const LiveInterval &LI = LIS->getInterval(Reg);
     658           0 :     for (const MachineBasicBlock *SI : MBB->successors())
     659           0 :       if (LI.liveAt(LIS->getMBBStartIdx(SI)))
     660           0 :         return true;
     661           0 :     return false;
     662             :   } else {
     663           0 :     return LV->isLiveOut(Reg, *MBB);
     664             :   }
     665             : }

Generated by: LCOV version 1.13