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

Generated by: LCOV version 1.13