LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveRangeCalc.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 220 222 99.1 %
Date: 2018-02-20 16:54:40 Functions: 16 16 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LiveRangeCalc.cpp - Calculate live ranges --------------------------===//
       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             : // Implementation of the LiveRangeCalc class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "LiveRangeCalc.h"
      15             : #include "llvm/ADT/BitVector.h"
      16             : #include "llvm/ADT/STLExtras.h"
      17             : #include "llvm/ADT/SetVector.h"
      18             : #include "llvm/ADT/SmallVector.h"
      19             : #include "llvm/CodeGen/LiveInterval.h"
      20             : #include "llvm/CodeGen/MachineBasicBlock.h"
      21             : #include "llvm/CodeGen/MachineDominators.h"
      22             : #include "llvm/CodeGen/MachineFunction.h"
      23             : #include "llvm/CodeGen/MachineInstr.h"
      24             : #include "llvm/CodeGen/MachineOperand.h"
      25             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      26             : #include "llvm/CodeGen/SlotIndexes.h"
      27             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      28             : #include "llvm/MC/LaneBitmask.h"
      29             : #include "llvm/Support/ErrorHandling.h"
      30             : #include "llvm/Support/raw_ostream.h"
      31             : #include <algorithm>
      32             : #include <cassert>
      33             : #include <iterator>
      34             : #include <tuple>
      35             : #include <utility>
      36             : 
      37             : using namespace llvm;
      38             : 
      39             : #define DEBUG_TYPE "regalloc"
      40             : 
      41             : // Reserve an address that indicates a value that is known to be "undef".
      42             : static VNInfo UndefVNI(0xbad, SlotIndex());
      43             : 
      44     5882762 : void LiveRangeCalc::resetLiveOutMap() {
      45     5882762 :   unsigned NumBlocks = MF->getNumBlockIDs();
      46             :   Seen.clear();
      47     5882762 :   Seen.resize(NumBlocks);
      48     5882762 :   EntryInfos.clear();
      49     5882762 :   Map.resize(NumBlocks);
      50     5882762 : }
      51             : 
      52     3578473 : void LiveRangeCalc::reset(const MachineFunction *mf,
      53             :                           SlotIndexes *SI,
      54             :                           MachineDominatorTree *MDT,
      55             :                           VNInfo::Allocator *VNIA) {
      56     3578473 :   MF = mf;
      57     3578473 :   MRI = &MF->getRegInfo();
      58     3578473 :   Indexes = SI;
      59     3578473 :   DomTree = MDT;
      60     3578473 :   Alloc = VNIA;
      61     3578473 :   resetLiveOutMap();
      62             :   LiveIn.clear();
      63     3578473 : }
      64             : 
      65     3810793 : static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
      66             :                           LiveRange &LR, const MachineOperand &MO) {
      67     3810793 :   const MachineInstr &MI = *MO.getParent();
      68             :   SlotIndex DefIdx =
      69     7621586 :       Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
      70             : 
      71             :   // Create the def in LR. This may find an existing def.
      72     3810793 :   LR.createDeadDef(DefIdx, Alloc);
      73     3810793 : }
      74             : 
      75     2304106 : void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
      76             :   assert(MRI && Indexes && "call reset() first");
      77             : 
      78             :   // Step 1: Create minimal live segments for every definition of Reg.
      79             :   // Visit all def operands. If the same instruction has multiple defs of Reg,
      80             :   // createDeadDef() will deduplicate.
      81     2304106 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
      82     2304106 :   unsigned Reg = LI.reg;
      83    10937809 :   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
      84     6337989 :     if (!MO.isDef() && !MO.readsReg())
      85        8392 :       continue;
      86             : 
      87             :     unsigned SubReg = MO.getSubReg();
      88    12406214 :     if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
      89             :       LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
      90      615327 :                                         : MRI->getMaxLaneMaskForVReg(Reg);
      91             :       // If this is the first time we see a subregister def, initialize
      92             :       // subranges by creating a copy of the main range.
      93      434140 :       if (!LI.hasSubRanges() && !LI.empty()) {
      94       56555 :         LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
      95       56555 :         LI.createSubRangeFrom(*Alloc, ClassMask, LI);
      96             :       }
      97             : 
      98      670336 :       LI.refineSubRanges(*Alloc, SubMask,
      99      568221 :           [&MO, this](LiveInterval::SubRange &SR) {
     100      445205 :         if (MO.isDef())
     101      246032 :           createDeadDef(*Indexes, *Alloc, SR, MO);
     102      445205 :       });
     103             :     }
     104             : 
     105             :     // Create the def in the main liverange. We do not have to do this if
     106             :     // subranges are tracked as we recreate the main range later in this case.
     107     6321205 :     if (MO.isDef() && !LI.hasSubRanges())
     108     2521441 :       createDeadDef(*Indexes, *Alloc, LI, MO);
     109             :   }
     110             : 
     111             :   // We may have created empty live ranges for partially undefined uses, we
     112             :   // can't keep them because we won't find defs in them later.
     113     2304106 :   LI.removeEmptySubRanges();
     114             : 
     115             :   // Step 2: Extend live segments to all uses, constructing SSA form as
     116             :   // necessary.
     117     2304105 :   if (LI.hasSubRanges()) {
     118      357347 :     for (LiveInterval::SubRange &S : LI.subranges()) {
     119      516750 :       LiveRangeCalc SubLRC;
     120      258375 :       SubLRC.reset(MF, Indexes, DomTree, Alloc);
     121      258375 :       SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
     122             :     }
     123             :     LI.clear();
     124       98972 :     constructMainRangeFromSubranges(LI);
     125             :   } else {
     126     2205133 :     resetLiveOutMap();
     127     2205134 :     extendToUses(LI, Reg, LaneBitmask::getAll());
     128             :   }
     129     2304105 : }
     130             : 
     131       99155 : void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
     132             :   // First create dead defs at all defs found in subranges.
     133       99155 :   LiveRange &MainRange = LI;
     134             :   assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
     135             :          "Expect empty main liverange");
     136             : 
     137      357947 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     138      777606 :     for (const VNInfo *VNI : SR.valnos) {
     139      518783 :       if (!VNI->isUnused() && !VNI->isPHIDef())
     140      259288 :         MainRange.createDeadDef(VNI->def, *Alloc);
     141             :     }
     142             :   }
     143       99155 :   resetLiveOutMap();
     144       99155 :   extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
     145       99155 : }
     146             : 
     147      490929 : void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
     148             :   assert(MRI && Indexes && "call reset() first");
     149             : 
     150             :   // Visit all def operands. If the same instruction has multiple defs of Reg,
     151             :   // LR.createDeadDef() will deduplicate.
     152     2148194 :   for (MachineOperand &MO : MRI->def_operands(Reg))
     153     1166336 :     createDeadDef(*Indexes, *Alloc, LR, MO);
     154      490929 : }
     155             : 
     156     3049869 : void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
     157             :                                  LiveInterval *LI) {
     158             :   SmallVector<SlotIndex, 4> Undefs;
     159     3049869 :   if (LI != nullptr)
     160      357530 :     LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
     161             : 
     162             :   // Visit all operands that read Reg. This may include partial defs.
     163             :   bool IsSubRange = !Mask.all();
     164     3049869 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     165    15769067 :   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     166             :     // Clear all kill flags. They will be reinserted after register allocation
     167             :     // by LiveIntervals::addKillFlags().
     168     9669329 :     if (MO.isUse())
     169             :       MO.setIsKill(false);
     170             :     // MO::readsReg returns "true" for subregister defs. This is for keeping
     171             :     // liveness of the entire register (i.e. for the main range of the live
     172             :     // interval). For subranges, definitions of non-overlapping subregisters
     173             :     // do not count as uses.
     174     5871448 :     if (!MO.readsReg() || (IsSubRange && MO.isDef()))
     175     8555420 :       continue;
     176             : 
     177             :     unsigned SubReg = MO.getSubReg();
     178     5576005 :     if (SubReg != 0) {
     179      835451 :       LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
     180      835451 :       if (MO.isDef())
     181             :         SLM = ~SLM;
     182             :       // Ignore uses not reading the current (sub)range.
     183      835451 :       if ((SLM & Mask).none())
     184             :         continue;
     185             :     }
     186             : 
     187             :     // Determine the actual place of the use.
     188     5207233 :     const MachineInstr *MI = MO.getParent();
     189     5207233 :     unsigned OpNo = (&MO - &MI->getOperand(0));
     190             :     SlotIndex UseIdx;
     191             :     if (MI->isPHI()) {
     192             :       assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
     193             :       // The actual place where a phi operand is used is the end of the pred
     194             :       // MBB. PHI operands are paired: (Reg, PredMBB).
     195       26478 :       UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
     196             :     } else {
     197             :       // Check for early-clobber redefs.
     198             :       bool isEarlyClobber = false;
     199             :       unsigned DefIdx;
     200     5198407 :       if (MO.isDef())
     201             :         isEarlyClobber = MO.isEarlyClobber();
     202     5094130 :       else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
     203             :         // FIXME: This would be a lot easier if tied early-clobber uses also
     204             :         // had an early-clobber flag.
     205      208203 :         isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
     206             :       }
     207    10396813 :       UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
     208             :     }
     209             : 
     210             :     // MI is reading Reg. We may have visited MI before if it happens to be
     211             :     // reading Reg multiple times. That is OK, extend() is idempotent.
     212     5207233 :     extend(LR, UseIdx, Reg, Undefs);
     213             :   }
     214     3049869 : }
     215             : 
     216       86511 : void LiveRangeCalc::updateFromLiveIns() {
     217       86511 :   LiveRangeUpdater Updater;
     218      354213 :   for (const LiveInBlock &I : LiveIn) {
     219      133851 :     if (!I.DomNode)
     220       48093 :       continue;
     221       85758 :     MachineBasicBlock *MBB = I.DomNode->getBlock();
     222             :     assert(I.Value && "No live-in value found");
     223             :     SlotIndex Start, End;
     224       85758 :     std::tie(Start, End) = Indexes->getMBBRange(MBB);
     225             : 
     226       85758 :     if (I.Kill.isValid())
     227             :       // Value is killed inside this block.
     228       10490 :       End = I.Kill;
     229             :     else {
     230             :       // The value is live-through, update LiveOut as well.
     231             :       // Defer the Domtree lookup until it is needed.
     232             :       assert(Seen.test(MBB->getNumber()));
     233             :       Map[MBB] = LiveOutPair(I.Value, nullptr);
     234             :     }
     235       85758 :     Updater.setDest(&I.LR);
     236       85758 :     Updater.add(Start, End, I.Value);
     237             :   }
     238             :   LiveIn.clear();
     239       86511 : }
     240             : 
     241     5680562 : void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
     242             :                            ArrayRef<SlotIndex> Undefs) {
     243             :   assert(Use.isValid() && "Invalid SlotIndex");
     244             :   assert(Indexes && "Missing SlotIndexes");
     245             :   assert(DomTree && "Missing dominator tree");
     246             : 
     247    11361124 :   MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
     248             :   assert(UseMBB && "No MBB at Use");
     249             : 
     250             :   // Is there a def in the same MBB we can extend?
     251    11361124 :   auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
     252     5680562 :   if (EP.first != nullptr || EP.second)
     253     5639916 :     return;
     254             : 
     255             :   // Find the single reaching def, or determine if Use is jointly dominated by
     256             :   // multiple values, and we may need to create even more phi-defs to preserve
     257             :   // VNInfo SSA form.  Perform a search for all predecessor blocks where we
     258             :   // know the dominating VNInfo.
     259      278262 :   if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
     260             :     return;
     261             : 
     262             :   // When there were multiple different values, we may need new PHIs.
     263       40646 :   calculateValues();
     264             : }
     265             : 
     266             : // This function is called by a client after using the low-level API to add
     267             : // live-out and live-in blocks.  The unique value optimization is not
     268             : // available, SplitEditor::transferValues handles that case directly anyway.
     269       86511 : void LiveRangeCalc::calculateValues() {
     270             :   assert(Indexes && "Missing SlotIndexes");
     271             :   assert(DomTree && "Missing dominator tree");
     272       86511 :   updateSSA();
     273       86511 :   updateFromLiveIns();
     274       86511 : }
     275             : 
     276          99 : bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
     277             :                                  MachineBasicBlock &MBB, BitVector &DefOnEntry,
     278             :                                  BitVector &UndefOnEntry) {
     279          99 :   unsigned BN = MBB.getNumber();
     280          99 :   if (DefOnEntry[BN])
     281             :     return true;
     282          81 :   if (UndefOnEntry[BN])
     283             :     return false;
     284             : 
     285         278 :   auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
     286         202 :     for (MachineBasicBlock *S : B.successors())
     287         126 :       DefOnEntry[S->getNumber()] = true;
     288             :     DefOnEntry[BN] = true;
     289          76 :     return true;
     290             :   };
     291             : 
     292          81 :   SetVector<unsigned> WorkList;
     293             :   // Checking if the entry of MBB is reached by some def: add all predecessors
     294             :   // that are potentially defined-on-exit to the work list.
     295         234 :   for (MachineBasicBlock *P : MBB.predecessors())
     296         153 :     WorkList.insert(P->getNumber());
     297             : 
     298         264 :   for (unsigned i = 0; i != WorkList.size(); ++i) {
     299             :     // Determine if the exit from the block is reached by some def.
     300         110 :     unsigned N = WorkList[i];
     301         110 :     MachineBasicBlock &B = *MF->getBlockNumbered(N);
     302         110 :     if (Seen[N]) {
     303             :       const LiveOutPair &LOB = Map[&B];
     304         110 :       if (LOB.first != nullptr && LOB.first != &UndefVNI)
     305         150 :         return MarkDefined(B);
     306             :     }
     307             :     SlotIndex Begin, End;
     308          36 :     std::tie(Begin, End) = Indexes->getMBBRange(&B);
     309             :     // Treat End as not belonging to B.
     310             :     // If LR has a segment S that starts at the next block, i.e. [End, ...),
     311             :     // std::upper_bound will return the segment following S. Instead,
     312             :     // S should be treated as the first segment that does not overlap B.
     313             :     LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
     314          72 :                                               End.getPrevSlot());
     315          36 :     if (UB != LR.begin()) {
     316             :       LiveRange::Segment &Seg = *std::prev(UB);
     317          26 :       if (Seg.end > Begin) {
     318             :         // There is a segment that overlaps B. If the range is not explicitly
     319             :         // undefined between the end of the segment and the end of the block,
     320             :         // treat the block as defined on exit. If it is, go to the next block
     321             :         // on the work list.
     322           0 :         if (LR.isUndefIn(Undefs, Seg.end, End))
     323           8 :           continue;
     324           0 :         return MarkDefined(B);
     325             :       }
     326             :     }
     327             : 
     328             :     // No segment overlaps with this block. If this block is not defined on
     329             :     // entry, or it undefines the range, do not process its predecessors.
     330          78 :     if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
     331             :       UndefOnEntry[N] = true;
     332           8 :       continue;
     333             :     }
     334          28 :     if (DefOnEntry[N])
     335           2 :       return MarkDefined(B);
     336             : 
     337             :     // Still don't know: add all predecessors to the work list.
     338          74 :     for (MachineBasicBlock *P : B.predecessors())
     339          48 :       WorkList.insert(P->getNumber());
     340             :   }
     341             : 
     342             :   UndefOnEntry[BN] = true;
     343           5 :   return false;
     344             : }
     345             : 
     346      278262 : bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
     347             :                                      SlotIndex Use, unsigned PhysReg,
     348             :                                      ArrayRef<SlotIndex> Undefs) {
     349      278262 :   unsigned UseMBBNum = UseMBB.getNumber();
     350             : 
     351             :   // Block numbers where LR should be live-in.
     352             :   SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
     353             : 
     354             :   // Remember if we have seen more than one value.
     355             :   bool UniqueVNI = true;
     356             :   VNInfo *TheVNI = nullptr;
     357             : 
     358             :   bool FoundUndef = false;
     359             : 
     360             :   // Using Seen as a visited set, perform a BFS for all reaching defs.
     361     4741737 :   for (unsigned i = 0; i != WorkList.size(); ++i) {
     362     2790142 :     MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
     363             : 
     364             : #ifndef NDEBUG
     365             :     if (MBB->pred_empty()) {
     366             :       MBB->getParent()->verify();
     367             :       errs() << "Use of " << printReg(PhysReg)
     368             :              << " does not have a corresponding definition on every path:\n";
     369             :       const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
     370             :       if (MI != nullptr)
     371             :         errs() << Use << " " << *MI;
     372             :       report_fatal_error("Use not jointly dominated by defs.");
     373             :     }
     374             : 
     375             :     if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
     376             :         !MBB->isLiveIn(PhysReg)) {
     377             :       MBB->getParent()->verify();
     378             :       const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
     379             :       errs() << "The register " << printReg(PhysReg, TRI)
     380             :              << " needs to be live in to " << printMBBReference(*MBB)
     381             :              << ", but is missing from the live-in list.\n";
     382             :       report_fatal_error("Invalid global physical register");
     383             :     }
     384             : #endif
     385     1395071 :     FoundUndef |= MBB->pred_empty();
     386             : 
     387     3259072 :     for (MachineBasicBlock *Pred : MBB->predecessors()) {
     388             :        // Is this a known live-out block?
     389     3728002 :        if (Seen.test(Pred->getNumber())) {
     390      430792 :          if (VNInfo *VNI = Map[Pred].first) {
     391      115072 :            if (TheVNI && TheVNI != VNI)
     392             :              UniqueVNI = false;
     393             :            TheVNI = VNI;
     394             :          }
     395     1146902 :          continue;
     396             :        }
     397             : 
     398             :        SlotIndex Start, End;
     399     1433209 :        std::tie(Start, End) = Indexes->getMBBRange(Pred);
     400             : 
     401             :        // First time we see Pred.  Try to determine the live-out value, but set
     402             :        // it as null if Pred is live-through with an unknown value.
     403     1433209 :        auto EP = LR.extendInBlock(Undefs, Start, End);
     404     1433209 :        VNInfo *VNI = EP.first;
     405     1433209 :        FoundUndef |= EP.second;
     406     1433209 :        setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
     407     1433209 :        if (VNI) {
     408      285311 :          if (TheVNI && TheVNI != VNI)
     409             :            UniqueVNI = false;
     410             :          TheVNI = VNI;
     411             :        }
     412     1433209 :        if (VNI || EP.second)
     413      285318 :          continue;
     414             : 
     415             :        // No, we need a live-in value for Pred as well
     416     1147891 :        if (Pred != &UseMBB)
     417     1116809 :          WorkList.push_back(Pred->getNumber());
     418             :        else
     419             :           // Loopback to UseMBB, so value is really live through.
     420             :          Use = SlotIndex();
     421             :     }
     422             :   }
     423             : 
     424      278262 :   LiveIn.clear();
     425      278262 :   FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
     426      278262 :   if (!Undefs.empty() && FoundUndef)
     427             :     UniqueVNI = false;
     428             : 
     429             :   // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
     430             :   // neither require it. Skip the sorting overhead for small updates.
     431      278262 :   if (WorkList.size() > 4)
     432             :     array_pod_sort(WorkList.begin(), WorkList.end());
     433             : 
     434             :   // If a unique reaching def was found, blit in the live ranges immediately.
     435      278262 :   if (UniqueVNI) {
     436             :     assert(TheVNI != nullptr && TheVNI != &UndefVNI);
     437      237616 :     LiveRangeUpdater Updater(&LR);
     438     2886780 :     for (unsigned BN : WorkList) {
     439             :       SlotIndex Start, End;
     440     1324582 :       std::tie(Start, End) = Indexes->getMBBRange(BN);
     441             :       // Trim the live range in UseMBB.
     442     1562198 :       if (BN == UseMBBNum && Use.isValid())
     443      206793 :         End = Use;
     444             :       else
     445     1117789 :         Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
     446             :       Updater.add(Start, End, TheVNI);
     447             :     }
     448             :     return true;
     449             :   }
     450             : 
     451             :   // Prepare the defined/undefined bit vectors.
     452             :   EntryInfoMap::iterator Entry;
     453             :   bool DidInsert;
     454       40646 :   std::tie(Entry, DidInsert) = EntryInfos.insert(
     455       81292 :       std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
     456       40646 :   if (DidInsert) {
     457             :     // Initialize newly inserted entries.
     458       38201 :     unsigned N = MF->getNumBlockIDs();
     459       38201 :     Entry->second.first.resize(N);
     460       38201 :     Entry->second.second.resize(N);
     461             :   }
     462       40646 :   BitVector &DefOnEntry = Entry->second.first;
     463       40646 :   BitVector &UndefOnEntry = Entry->second.second;
     464             : 
     465             :   // Multiple values were found, so transfer the work list to the LiveIn array
     466             :   // where UpdateSSA will use it as a work list.
     467       40646 :   LiveIn.reserve(WorkList.size());
     468      181624 :   for (unsigned BN : WorkList) {
     469       70489 :     MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
     470       70593 :     if (!Undefs.empty() &&
     471          99 :         !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
     472           5 :       continue;
     473       70484 :     addLiveInBlock(LR, DomTree->getNode(MBB));
     474       70484 :     if (MBB == &UseMBB)
     475       40642 :       LiveIn.back().Kill = Use;
     476             :   }
     477             : 
     478             :   return false;
     479             : }
     480             : 
     481             : // This is essentially the same iterative algorithm that SSAUpdater uses,
     482             : // except we already have a dominator tree, so we don't have to recompute it.
     483       86511 : void LiveRangeCalc::updateSSA() {
     484             :   assert(Indexes && "Missing SlotIndexes");
     485             :   assert(DomTree && "Missing dominator tree");
     486             : 
     487             :   // Interate until convergence.
     488             :   bool Changed;
     489      132712 :   do {
     490             :     Changed = false;
     491             :     // Propagate live-out values down the dominator tree, inserting phi-defs
     492             :     // when necessary.
     493      767726 :     for (LiveInBlock &I : LiveIn) {
     494      317507 :       MachineDomTreeNode *Node = I.DomNode;
     495             :       // Skip block if the live-in value has already been determined.
     496      317507 :       if (!Node)
     497       51616 :         continue;
     498      265891 :       MachineBasicBlock *MBB = Node->getBlock();
     499      265891 :       MachineDomTreeNode *IDom = Node->getIDom();
     500             :       LiveOutPair IDomValue;
     501             : 
     502             :       // We need a live-in value to a block with no immediate dominator?
     503             :       // This is probably an unreachable block that has survived somehow.
     504      531782 :       bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
     505             : 
     506             :       // IDom dominates all of our predecessors, but it may not be their
     507             :       // immediate dominator. Check if any of them have live-out values that are
     508             :       // properly dominated by IDom. If so, we need a phi-def here.
     509             :       if (!needPHI) {
     510             :         IDomValue = Map[IDom->getBlock()];
     511             : 
     512             :         // Cache the DomTree node that defined the value.
     513      243651 :         if (IDomValue.first && IDomValue.first != &UndefVNI &&
     514             :             !IDomValue.second) {
     515       53032 :           Map[IDom->getBlock()].second = IDomValue.second =
     516       26516 :             DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
     517             :         }
     518             : 
     519      545535 :         for (MachineBasicBlock *Pred : MBB->predecessors()) {
     520             :           LiveOutPair &Value = Map[Pred];
     521      327737 :           if (!Value.first || Value.first == IDomValue.first)
     522      301680 :             continue;
     523       26057 :           if (Value.first == &UndefVNI) {
     524             :             needPHI = true;
     525             :             break;
     526             :           }
     527             : 
     528             :           // Cache the DomTree node that defined the value.
     529       26056 :           if (!Value.second)
     530       22684 :             Value.second =
     531       22684 :               DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
     532             : 
     533             :           // This predecessor is carrying something other than IDomValue.
     534             :           // It could be because IDomValue hasn't propagated yet, or it could be
     535             :           // because MBB is in the dominance frontier of that value.
     536       52112 :           if (DomTree->dominates(IDom, Value.second)) {
     537             :             needPHI = true;
     538             :             break;
     539             :           }
     540             :         }
     541             :       }
     542             : 
     543             :       // The value may be live-through even if Kill is set, as can happen when
     544             :       // we are called from extendRange. In that case LiveOutSeen is true, and
     545             :       // LiveOut indicates a foreign or missing value.
     546             :       LiveOutPair &LOP = Map[MBB];
     547             : 
     548             :       // Create a phi-def if required.
     549      265891 :       if (needPHI) {
     550             :         Changed = true;
     551             :         assert(Alloc && "Need VNInfo allocator to create PHI-defs");
     552             :         SlotIndex Start, End;
     553       48093 :         std::tie(Start, End) = Indexes->getMBBRange(MBB);
     554       48093 :         LiveRange &LR = I.LR;
     555       48093 :         VNInfo *VNI = LR.getNextValue(Start, *Alloc);
     556       48093 :         I.Value = VNI;
     557             :         // This block is done, we know the final value.
     558       48093 :         I.DomNode = nullptr;
     559             : 
     560             :         // Add liveness since updateFromLiveIns now skips this node.
     561       48093 :         if (I.Kill.isValid()) {
     562       40135 :           if (VNI)
     563       40135 :             LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
     564             :         } else {
     565        7958 :           if (VNI)
     566        7958 :             LR.addSegment(LiveInterval::Segment(Start, End, VNI));
     567             :           LOP = LiveOutPair(VNI, Node);
     568             :         }
     569      217798 :       } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
     570             :         // No phi-def here. Remember incoming value.
     571      210779 :         I.Value = IDomValue.first;
     572             : 
     573             :         // If the IDomValue is killed in the block, don't propagate through.
     574      210779 :         if (I.Kill.isValid())
     575       23094 :           continue;
     576             : 
     577             :         // Propagate IDomValue if it isn't killed:
     578             :         // MBB is live-out and doesn't define its own value.
     579      187685 :         if (LOP.first == IDomValue.first)
     580      103195 :           continue;
     581             :         Changed = true;
     582             :         LOP = IDomValue;
     583             :       }
     584             :     }
     585             :   } while (Changed);
     586      281115 : }

Generated by: LCOV version 1.13