LCOV - code coverage report
Current view: top level - lib/CodeGen - PHIElimination.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 160 214 74.8 %
Date: 2018-07-13 00:08:38 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/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      299229 : DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
      52       99743 :                      cl::Hidden, cl::desc("Disable critical edge splitting "
      53      299229 :                                           "during PHI elimination"));
      54             : 
      55             : static cl::opt<bool>
      56      299229 : SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
      57       99743 :                       cl::Hidden, cl::desc("Split all critical edges during "
      58      299229 :                                            "PHI elimination"));
      59             : 
      60       99743 : static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
      61      199486 :     "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
      62      299229 :     cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
      63             : 
      64             : namespace {
      65             : 
      66       66372 :   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       44466 :     PHIElimination() : MachineFunctionPass(ID) {
      75       22233 :       initializePHIEliminationPass(*PassRegistry::getPassRegistry());
      76       22233 :     }
      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       26316 : INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
     130             :                       "Eliminate PHI nodes for register allocation",
     131             :                       false, false)
     132       26316 : INITIALIZE_PASS_DEPENDENCY(LiveVariables)
     133      191076 : INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
     134             :                     "Eliminate PHI nodes for register allocation", false, false)
     135             : 
     136       22062 : 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       22062 :   MachineFunctionPass::getAnalysisUsage(AU);
     144       22062 : }
     145             : 
     146      221360 : bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
     147      221360 :   MRI = &MF.getRegInfo();
     148      221360 :   LV = getAnalysisIfAvailable<LiveVariables>();
     149      221360 :   LIS = getAnalysisIfAvailable<LiveIntervals>();
     150             : 
     151             :   bool Changed = false;
     152             : 
     153             :   // This pass takes the function out of SSA form.
     154      221360 :   MRI->leaveSSA();
     155             : 
     156             :   // Split critical edges to help the coalescer. This does not yet support
     157             :   // updating LiveIntervals, so we disable it.
     158      221360 :   if (!DisableEdgeSplitting && (LV || LIS)) {
     159      184215 :     MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
     160      528206 :     for (auto &MBB : MF)
     161      343991 :       Changed |= SplitPHIEdges(MF, MBB, MLI);
     162             :   }
     163             : 
     164             :   // Populate VRegPHIUseCount
     165      221360 :   analyzePHINodes(MF);
     166             : 
     167             :   // Eliminate PHI instructions by inserting copies into predecessor blocks.
     168      649503 :   for (auto &MBB : MF)
     169      428143 :     Changed |= EliminatePHINodes(MF, MBB);
     170             : 
     171             :   // Remove dead IMPLICIT_DEF instructions.
     172      221360 :   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      480602 :   for (auto &I : LoweredPHIs) {
     183       37882 :     if (LIS)
     184           0 :       LIS->RemoveMachineInstrFromMaps(*I.first);
     185       37882 :     MF.DeleteMachineInstr(I.first);
     186             :   }
     187             : 
     188      221360 :   LoweredPHIs.clear();
     189      221360 :   ImpDefs.clear();
     190      221360 :   VRegPHIUseCount.clear();
     191             : 
     192             :   MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
     193             : 
     194      221360 :   return Changed;
     195             : }
     196             : 
     197             : /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
     198             : /// predecessor basic blocks.
     199      428143 : bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
     200             :                                              MachineBasicBlock &MBB) {
     201      428143 :   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       55196 :     std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
     208             : 
     209             :   while (MBB.front().isPHI())
     210       38248 :     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      121301 : static bool isImplicitlyDefined(unsigned VirtReg,
     218             :                                 const MachineRegisterInfo *MRI) {
     219      121378 :   for (MachineInstr &DI : MRI->def_instructions(VirtReg))
     220      119817 :     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       38248 : static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi,
     228             :                                          const MachineRegisterInfo *MRI) {
     229       41290 :   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
     230       79534 :     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       38248 : void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
     237             :                                   MachineBasicBlock::iterator LastPHIIt) {
     238             :   ++NumLowered;
     239             : 
     240             :   MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
     241             : 
     242             :   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
     243       38248 :   MachineInstr *MPhi = MBB.remove(&*MBB.begin());
     244             : 
     245       38248 :   unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
     246       38248 :   unsigned DestReg = MPhi->getOperand(0).getReg();
     247             :   assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
     248             :   bool isDead = MPhi->getOperand(0).isDead();
     249             : 
     250             :   // Create a new register for the incoming PHI arguments.
     251       38248 :   MachineFunction &MF = *MBB.getParent();
     252             :   unsigned IncomingReg = 0;
     253             :   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       38248 :   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
     259       38248 :   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           4 :             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       38246 :     unsigned &entry = LoweredPHIs[MPhi];
     268       38246 :     if (entry) {
     269             :       // An identical PHI node was already lowered. Reuse the incoming register.
     270             :       IncomingReg = entry;
     271             :       reusedIncoming = true;
     272             :       ++NumReused;
     273             :       LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
     274             :                         << *MPhi);
     275             :     } else {
     276       37882 :       const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
     277       37882 :       entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
     278             :     }
     279       76492 :     BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
     280       76492 :             TII->get(TargetOpcode::COPY), DestReg)
     281       38246 :       .addReg(IncomingReg);
     282             :   }
     283             : 
     284             :   // Update live variable information if there is any.
     285       38248 :   if (LV) {
     286             :     MachineInstr &PHICopy = *std::prev(AfterPHIsIt);
     287             : 
     288       37232 :     if (IncomingReg) {
     289       37231 :       LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
     290             : 
     291             :       // Increment use count of the newly created virtual register.
     292       37231 :       LV->setPHIJoin(IncomingReg);
     293             : 
     294             :       // When we are reusing the incoming register, it may already have been
     295             :       // killed in this block. The old kill will also have been inserted at
     296             :       // AfterPHIsIt, so it appears before the current PHICopy.
     297       37231 :       if (reusedIncoming)
     298         362 :         if (MachineInstr *OldKill = VI.findKill(&MBB)) {
     299             :           LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
     300          38 :           LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
     301             :           LLVM_DEBUG(MBB.dump());
     302             :         }
     303             : 
     304             :       // Add information to LiveVariables to know that the incoming value is
     305             :       // killed.  Note that because the value is defined in several places (once
     306             :       // each for each incoming block), the "def" block and instruction fields
     307             :       // for the VarInfo is not filled in.
     308       37231 :       LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
     309             :     }
     310             : 
     311             :     // Since we are going to be deleting the PHI node, if it is the last use of
     312             :     // any registers, or if the value itself is dead, we need to move this
     313             :     // information over to the new copy we just inserted.
     314       37232 :     LV->removeVirtualRegistersKilled(*MPhi);
     315             : 
     316             :     // If the result is dead, update LV.
     317       37232 :     if (isDead) {
     318           1 :       LV->addVirtualRegisterDead(DestReg, PHICopy);
     319           1 :       LV->removeVirtualRegisterDead(DestReg, *MPhi);
     320             :     }
     321             :   }
     322             : 
     323             :   // Update LiveIntervals for the new copy or implicit def.
     324       38248 :   if (LIS) {
     325             :     SlotIndex DestCopyIndex =
     326           0 :         LIS->InsertMachineInstrInMaps(*std::prev(AfterPHIsIt));
     327             : 
     328           0 :     SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
     329           0 :     if (IncomingReg) {
     330             :       // Add the region from the beginning of MBB to the copy instruction to
     331             :       // IncomingReg's live interval.
     332           0 :       LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
     333           0 :       VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
     334           0 :       if (!IncomingVNI)
     335           0 :         IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
     336           0 :                                               LIS->getVNInfoAllocator());
     337           0 :       IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
     338             :                                                   DestCopyIndex.getRegSlot(),
     339             :                                                   IncomingVNI));
     340             :     }
     341             : 
     342           0 :     LiveInterval &DestLI = LIS->getInterval(DestReg);
     343             :     assert(DestLI.begin() != DestLI.end() &&
     344             :            "PHIs should have nonempty LiveIntervals.");
     345           0 :     if (DestLI.endIndex().isDead()) {
     346             :       // A dead PHI's live range begins and ends at the start of the MBB, but
     347             :       // the lowered copy, which will still be dead, needs to begin and end at
     348             :       // the copy instruction.
     349           0 :       VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
     350             :       assert(OrigDestVNI && "PHI destination should be live at block entry.");
     351           0 :       DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
     352           0 :       DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
     353           0 :                            LIS->getVNInfoAllocator());
     354           0 :       DestLI.removeValNo(OrigDestVNI);
     355             :     } else {
     356             :       // Otherwise, remove the region from the beginning of MBB to the copy
     357             :       // instruction from DestReg's live interval.
     358           0 :       DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
     359             :       VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
     360             :       assert(DestVNI && "PHI destination should be live at its definition.");
     361           0 :       DestVNI->def = DestCopyIndex.getRegSlot();
     362             :     }
     363             :   }
     364             : 
     365             :   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
     366      204562 :   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
     367      249471 :     --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
     368      249471 :                                  MPhi->getOperand(i).getReg())];
     369             : 
     370             :   // Now loop over all of the incoming arguments, changing them to copy into the
     371             :   // IncomingReg register in the corresponding predecessor basic block.
     372             :   SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
     373      121405 :   for (int i = NumSrcs - 1; i >= 0; --i) {
     374      166314 :     unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
     375             :     unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
     376      164691 :     bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
     377       81534 :       isImplicitlyDefined(SrcReg, MRI);
     378             :     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
     379             :            "Machine PHI Operands must all be virtual registers!");
     380             : 
     381             :     // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
     382             :     // path the PHI.
     383      166314 :     MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
     384             : 
     385             :     // Check to make sure we haven't already emitted the copy for this block.
     386             :     // This can happen because PHI nodes may have multiple entries for the same
     387             :     // basic block.
     388       83157 :     if (!MBBsInsertedInto.insert(&opBlock).second)
     389          23 :       continue;  // If the copy has already been emitted, we're done.
     390             : 
     391             :     // Find a safe location to insert the copy, this may be the first terminator
     392             :     // in the block (or end()).
     393             :     MachineBasicBlock::iterator InsertPos =
     394       83134 :       findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
     395             : 
     396             :     // Insert the copy.
     397             :     MachineInstr *NewSrcInstr = nullptr;
     398       83134 :     if (!reusedIncoming && IncomingReg) {
     399       82119 :       if (SrcUndef) {
     400             :         // The source register is undefined, so there is no need for a real
     401             :         // COPY, but we still need to ensure joint dominance by defs.
     402             :         // Insert an IMPLICIT_DEF instruction.
     403        1635 :         NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
     404             :                               TII->get(TargetOpcode::IMPLICIT_DEF),
     405        3270 :                               IncomingReg);
     406             : 
     407             :         // Clean up the old implicit-def, if there even was one.
     408        1635 :         if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
     409          36 :           if (DefMI->isImplicitDef())
     410          36 :             ImpDefs.insert(DefMI);
     411             :       } else {
     412      160968 :         NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
     413      160968 :                             TII->get(TargetOpcode::COPY), IncomingReg)
     414       80484 :                         .addReg(SrcReg, 0, SrcSubReg);
     415             :       }
     416             :     }
     417             : 
     418             :     // We only need to update the LiveVariables kill of SrcReg if this was the
     419             :     // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
     420             :     // out of the predecessor. We can also ignore undef sources.
     421      243667 :     if (LV && !SrcUndef &&
     422      397301 :         !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
     423       75802 :         !LV->isLiveOut(SrcReg, opBlock)) {
     424             :       // We want to be able to insert a kill of the register if this PHI (aka,
     425             :       // the copy we just inserted) is the last use of the source value. Live
     426             :       // variable analysis conservatively handles this by saying that the value
     427             :       // is live until the end of the block the PHI entry lives in. If the value
     428             :       // really is dead at the PHI copy, there will be no successor blocks which
     429             :       // have the value live-in.
     430             : 
     431             :       // Okay, if we now know that the value is not live out of the block, we
     432             :       // can add a kill marker in this block saying that it kills the incoming
     433             :       // value!
     434             : 
     435             :       // In our final twist, we have to decide which instruction kills the
     436             :       // register.  In most cases this is the copy, however, terminator
     437             :       // instructions at the end of the block may also use the value. In this
     438             :       // case, we should mark the last such terminator as being the killing
     439             :       // block, not the copy.
     440       71984 :       MachineBasicBlock::iterator KillInst = opBlock.end();
     441       71984 :       MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
     442       71984 :       for (MachineBasicBlock::iterator Term = FirstTerm;
     443      127374 :           Term != opBlock.end(); ++Term) {
     444       55390 :         if (Term->readsRegister(SrcReg))
     445          33 :           KillInst = Term;
     446             :       }
     447             : 
     448       71984 :       if (KillInst == opBlock.end()) {
     449             :         // No terminator uses the register.
     450             : 
     451       71951 :         if (reusedIncoming || !IncomingReg) {
     452             :           // We may have to rewind a bit if we didn't insert a copy this time.
     453         656 :           KillInst = FirstTerm;
     454        2272 :           while (KillInst != opBlock.begin()) {
     455             :             --KillInst;
     456           0 :             if (KillInst->isDebugInstr())
     457           0 :               continue;
     458        2272 :             if (KillInst->readsRegister(SrcReg))
     459             :               break;
     460             :           }
     461             :         } else {
     462             :           // We just inserted this copy.
     463       71295 :           KillInst = std::prev(InsertPos);
     464             :         }
     465             :       }
     466             :       assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
     467             : 
     468             :       // Finally, mark it killed.
     469      143968 :       LV->addVirtualRegisterKilled(SrcReg, *KillInst);
     470             : 
     471             :       // This vreg no longer lives all of the way through opBlock.
     472       71984 :       unsigned opBlockNum = opBlock.getNumber();
     473       71984 :       LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
     474             :     }
     475             : 
     476       83134 :     if (LIS) {
     477           0 :       if (NewSrcInstr) {
     478           0 :         LIS->InsertMachineInstrInMaps(*NewSrcInstr);
     479           0 :         LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
     480             :       }
     481             : 
     482           0 :       if (!SrcUndef &&
     483           0 :           !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
     484           0 :         LiveInterval &SrcLI = LIS->getInterval(SrcReg);
     485             : 
     486             :         bool isLiveOut = false;
     487             :         for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
     488           0 :              SE = opBlock.succ_end(); SI != SE; ++SI) {
     489           0 :           SlotIndex startIdx = LIS->getMBBStartIdx(*SI);
     490           0 :           VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
     491             : 
     492             :           // Definitions by other PHIs are not truly live-in for our purposes.
     493           0 :           if (VNI && VNI->def != startIdx) {
     494             :             isLiveOut = true;
     495             :             break;
     496             :           }
     497             :         }
     498             : 
     499             :         if (!isLiveOut) {
     500           0 :           MachineBasicBlock::iterator KillInst = opBlock.end();
     501           0 :           MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
     502           0 :           for (MachineBasicBlock::iterator Term = FirstTerm;
     503           0 :               Term != opBlock.end(); ++Term) {
     504           0 :             if (Term->readsRegister(SrcReg))
     505           0 :               KillInst = Term;
     506             :           }
     507             : 
     508           0 :           if (KillInst == opBlock.end()) {
     509             :             // No terminator uses the register.
     510             : 
     511           0 :             if (reusedIncoming || !IncomingReg) {
     512             :               // We may have to rewind a bit if we didn't just insert a copy.
     513           0 :               KillInst = FirstTerm;
     514           0 :               while (KillInst != opBlock.begin()) {
     515             :                 --KillInst;
     516           0 :                 if (KillInst->isDebugInstr())
     517           0 :                   continue;
     518           0 :                 if (KillInst->readsRegister(SrcReg))
     519             :                   break;
     520             :               }
     521             :             } else {
     522             :               // We just inserted this copy.
     523           0 :               KillInst = std::prev(InsertPos);
     524             :             }
     525             :           }
     526             :           assert(KillInst->readsRegister(SrcReg) &&
     527             :                  "Cannot find kill instruction");
     528             : 
     529           0 :           SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
     530           0 :           SrcLI.removeSegment(LastUseIndex.getRegSlot(),
     531           0 :                               LIS->getMBBEndIdx(&opBlock));
     532             :         }
     533             :       }
     534             :     }
     535             :   }
     536             : 
     537             :   // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
     538       38248 :   if (reusedIncoming || !IncomingReg) {
     539         366 :     if (LIS)
     540           0 :       LIS->RemoveMachineInstrFromMaps(*MPhi);
     541         366 :     MF.DeleteMachineInstr(MPhi);
     542             :   }
     543       38248 : }
     544             : 
     545             : /// analyzePHINodes - Gather information about the PHI nodes in here. In
     546             : /// particular, we want to map the number of uses of a virtual register which is
     547             : /// used in a PHI node. We map that to the BB the vreg is coming from. This is
     548             : /// used later to determine when the vreg is killed in the BB.
     549      221360 : void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
     550      649503 :   for (const auto &MBB : MF)
     551      894534 :     for (const auto &BBI : MBB) {
     552             :       if (!BBI.isPHI())
     553             :         break;
     554      121405 :       for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
     555      249471 :         ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
     556      249471 :                                      BBI.getOperand(i).getReg())];
     557             :     }
     558      221360 : }
     559             : 
     560      343991 : bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
     561             :                                    MachineBasicBlock &MBB,
     562             :                                    MachineLoopInfo *MLI) {
     563      370665 :   if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
     564             :     return false;   // Quick exit for basic blocks without PHIs.
     565             : 
     566       26614 :   const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
     567       14710 :   bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
     568             : 
     569             :   bool Changed = false;
     570       26614 :   for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
     571       63786 :        BBI != BBE && BBI->isPHI(); ++BBI) {
     572      118140 :     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
     573      161936 :       unsigned Reg = BBI->getOperand(i).getReg();
     574      161936 :       MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
     575             :       // Is there a critical edge from PreMBB to MBB?
     576       80968 :       if (PreMBB->succ_size() == 1)
     577             :         continue;
     578             : 
     579             :       // Avoid splitting backedges of loops. It would introduce small
     580             :       // out-of-line blocks into the loop which is very bad for code placement.
     581       31635 :       if (PreMBB == &MBB && !SplitAllCriticalEdges)
     582             :         continue;
     583       15138 :       const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
     584       24120 :       if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
     585             :         continue;
     586             : 
     587             :       // LV doesn't consider a phi use live-out, so isLiveOut only returns true
     588             :       // when the source register is live-out for some other reason than a phi
     589             :       // use. That means the copy we will insert in PreMBB won't be a kill, and
     590             :       // there is a risk it may not be coalesced away.
     591             :       //
     592             :       // If the copy would be a kill, there is no need to split the edge.
     593       10647 :       bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
     594       25734 :       if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
     595             :         continue;
     596             :       if (ShouldSplit) {
     597             :         LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
     598             :                           << printMBBReference(*PreMBB) << " -> "
     599             :                           << printMBBReference(MBB) << ": " << *BBI);
     600             :       }
     601             : 
     602             :       // If Reg is not live-in to MBB, it means it must be live-in to some
     603             :       // other PreMBB successor, and we can avoid the interference by splitting
     604             :       // the edge.
     605             :       //
     606             :       // If Reg *is* live-in to MBB, the interference is inevitable and a copy
     607             :       // is likely to be left after coalescing. If we are looking at a loop
     608             :       // exiting edge, split it so we won't insert code in the loop, otherwise
     609             :       // don't bother.
     610        6207 :       ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
     611             : 
     612             :       // Check for a loop exiting edge.
     613        3110 :       if (!ShouldSplit && CurLoop != PreLoop) {
     614             :         LLVM_DEBUG({
     615             :           dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
     616             :           if (PreLoop)
     617             :             dbgs() << "PreLoop: " << *PreLoop;
     618             :           if (CurLoop)
     619             :             dbgs() << "CurLoop: " << *CurLoop;
     620             :         });
     621             :         // This edge could be entering a loop, exiting a loop, or it could be
     622             :         // both: Jumping directly form one loop to the header of a sibling
     623             :         // loop.
     624             :         // Split unless this edge is entering CurLoop from an outer loop.
     625         121 :         ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
     626             :       }
     627        4822 :       if (!ShouldSplit && !SplitAllCriticalEdges)
     628             :         continue;
     629        2376 :       if (!PreMBB->SplitCriticalEdge(&MBB, *this)) {
     630             :         LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
     631             :         continue;
     632             :       }
     633             :       Changed = true;
     634             :       ++NumCriticalEdgesSplit;
     635             :     }
     636             :   }
     637             :   return Changed;
     638             : }
     639             : 
     640        3097 : bool PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock *MBB) {
     641             :   assert((LV || LIS) &&
     642             :          "isLiveIn() requires either LiveVariables or LiveIntervals");
     643        3097 :   if (LIS)
     644           0 :     return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
     645             :   else
     646        3097 :     return LV->isLiveIn(Reg, *MBB);
     647             : }
     648             : 
     649       10647 : bool PHIElimination::isLiveOutPastPHIs(unsigned Reg,
     650             :                                        const MachineBasicBlock *MBB) {
     651             :   assert((LV || LIS) &&
     652             :          "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
     653             :   // LiveVariables considers uses in PHIs to be in the predecessor basic block,
     654             :   // so that a register used only in a PHI is not live out of the block. In
     655             :   // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
     656             :   // in the predecessor basic block, so that a register used only in a PHI is live
     657             :   // out of the block.
     658       10647 :   if (LIS) {
     659           0 :     const LiveInterval &LI = LIS->getInterval(Reg);
     660           0 :     for (const MachineBasicBlock *SI : MBB->successors())
     661           0 :       if (LI.liveAt(LIS->getMBBStartIdx(SI)))
     662             :         return true;
     663             :     return false;
     664             :   } else {
     665       10647 :     return LV->isLiveOut(Reg, *MBB);
     666             :   }
     667      299229 : }

Generated by: LCOV version 1.13