LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveRangeCalc.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 264 266 99.2 %
Date: 2017-09-14 15:23:50 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/MC/LaneBitmask.h"
      28             : #include "llvm/Support/ErrorHandling.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : #include "llvm/Target/TargetRegisterInfo.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      144612 : static VNInfo UndefVNI(0xbad, SlotIndex());
      43             : 
      44     5428847 : void LiveRangeCalc::resetLiveOutMap() {
      45    10857694 :   unsigned NumBlocks = MF->getNumBlockIDs();
      46     5428847 :   Seen.clear();
      47     5428847 :   Seen.resize(NumBlocks);
      48     5428847 :   EntryInfos.clear();
      49    10857694 :   Map.resize(NumBlocks);
      50     5428847 : }
      51             : 
      52     3291149 : void LiveRangeCalc::reset(const MachineFunction *mf,
      53             :                           SlotIndexes *SI,
      54             :                           MachineDominatorTree *MDT,
      55             :                           VNInfo::Allocator *VNIA) {
      56     3291149 :   MF = mf;
      57     3291149 :   MRI = &MF->getRegInfo();
      58     3291149 :   Indexes = SI;
      59     3291149 :   DomTree = MDT;
      60     3291149 :   Alloc = VNIA;
      61     3291149 :   resetLiveOutMap();
      62     6582298 :   LiveIn.clear();
      63     3291149 : }
      64             : 
      65     3546154 : static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
      66             :                           LiveRange &LR, const MachineOperand &MO) {
      67     3546154 :   const MachineInstr &MI = *MO.getParent();
      68             :   SlotIndex DefIdx =
      69    10638462 :       Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
      70             : 
      71             :   // Create the def in LR. This may find an existing def.
      72     3546154 :   LR.createDeadDef(DefIdx, Alloc);
      73     3546154 : }
      74             : 
      75     2137535 : 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     4275070 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
      82     2137535 :   unsigned Reg = LI.reg;
      83    12335124 :   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
      84     5929906 :     if (!MO.isDef() && !MO.readsReg())
      85        7387 :       continue;
      86             : 
      87     5915132 :     unsigned SubReg = MO.getSubReg();
      88    11594650 :     if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
      89             :       LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
      90      606404 :                                         : 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      426898 :       if (!LI.hasSubRanges() && !LI.empty()) {
      94       54211 :         LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
      95       54211 :         LI.createSubRangeFrom(*Alloc, ClassMask, LI);
      96             :       }
      97             : 
      98      993768 :       LI.refineSubRanges(*Alloc, SubMask,
      99      562002 :           [&MO, this](LiveInterval::SubRange &SR) {
     100      441477 :         if (MO.isDef())
     101      241050 :           createDeadDef(*Indexes, *Alloc, SR, MO);
     102      441477 :       });
     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     5915132 :     if (MO.isDef() && !LI.hasSubRanges())
     108     2335941 :       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     2137535 :   LI.removeEmptySubRanges();
     114             : 
     115             :   // Step 2: Extend live segments to all uses, constructing SSA form as
     116             :   // necessary.
     117     2137535 :   if (LI.hasSubRanges()) {
     118      345684 :     for (LiveInterval::SubRange &S : LI.subranges()) {
     119      500084 :       LiveRangeCalc SubLRC;
     120      250042 :       SubLRC.reset(MF, Indexes, DomTree, Alloc);
     121      250042 :       SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
     122             :     }
     123      191284 :     LI.clear();
     124       95642 :     constructMainRangeFromSubranges(LI);
     125             :   } else {
     126     2041893 :     resetLiveOutMap();
     127     2041893 :     extendToUses(LI, Reg, LaneBitmask::getAll());
     128             :   }
     129     2137535 : }
     130             : 
     131       95805 : void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
     132             :   // First create dead defs at all defs found in subranges.
     133       95805 :   LiveRange &MainRange = LI;
     134             :   assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
     135             :          "Expect empty main liverange");
     136             : 
     137      441970 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     138     1001990 :     for (const VNInfo *VNI : SR.valnos) {
     139      501792 :       if (!VNI->isUnused() && !VNI->isPHIDef())
     140      250800 :         MainRange.createDeadDef(VNI->def, *Alloc);
     141             :     }
     142             :   }
     143       95805 :   resetLiveOutMap();
     144       95805 :   extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
     145       95805 : }
     146             : 
     147      424803 : 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     2364097 :   for (MachineOperand &MO : MRI->def_operands(Reg))
     153     1089688 :     createDeadDef(*Indexes, *Alloc, LR, MO);
     154      424803 : }
     155             : 
     156     2807613 : void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
     157             :                                  LiveInterval *LI) {
     158     5615226 :   SmallVector<SlotIndex, 4> Undefs;
     159     2807613 :   if (LI != nullptr)
     160      345847 :     LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
     161             : 
     162             :   // Visit all operands that read Reg. This may include partial defs.
     163     2807613 :   bool IsSubRange = !Mask.all();
     164     5615226 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     165    17477863 :   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     166             :     // Clear all kill flags. They will be reinserted after register allocation
     167             :     // by LiveIntervalAnalysis::addKillFlags().
     168     9055024 :     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     5529555 :     if (!MO.readsReg() || (IsSubRange && MO.isDef()))
     175     7987849 :       continue;
     176             : 
     177     5240324 :     unsigned SubReg = MO.getSubReg();
     178     5240324 :     if (SubReg != 0) {
     179     1627158 :       LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
     180      813579 :       if (MO.isDef())
     181      101916 :         SLM = ~SLM;
     182             :       // Ignore uses not reading the current (sub)range.
     183      813579 :       if ((SLM & Mask).none())
     184      358449 :         continue;
     185             :     }
     186             : 
     187             :     // Determine the actual place of the use.
     188     4881875 :     const MachineInstr *MI = MO.getParent();
     189     4881875 :     unsigned OpNo = (&MO - &MI->getOperand(0));
     190     4881875 :     SlotIndex UseIdx;
     191     4873393 :     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       25446 :       UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
     196             :     } else {
     197             :       // Check for early-clobber redefs.
     198     4873393 :       bool isEarlyClobber = false;
     199             :       unsigned DefIdx;
     200     4873393 :       if (MO.isDef())
     201      101916 :         isEarlyClobber = MO.isEarlyClobber();
     202     4771477 :       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      566373 :         isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
     206             :       }
     207     9746786 :       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     4881875 :     extend(LR, UseIdx, Reg, Undefs);
     213             :   }
     214     2807613 : }
     215             : 
     216       83151 : void LiveRangeCalc::updateFromLiveIns() {
     217      166302 :   LiveRangeUpdater Updater;
     218      378822 :   for (const LiveInBlock &I : LiveIn) {
     219      129369 :     if (!I.DomNode)
     220       46671 :       continue;
     221       82698 :     MachineBasicBlock *MBB = I.DomNode->getBlock();
     222             :     assert(I.Value && "No live-in value found");
     223      165396 :     SlotIndex Start, End;
     224      330792 :     std::tie(Start, End) = Indexes->getMBBRange(MBB);
     225             : 
     226      165396 :     if (I.Kill.isValid())
     227             :       // Value is killed inside this block.
     228       10553 :       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      288580 :       Map[MBB] = LiveOutPair(I.Value, nullptr);
     234             :     }
     235      165396 :     Updater.setDest(&I.LR);
     236      165396 :     Updater.add(Start, End, I.Value);
     237             :   }
     238      166302 :   LiveIn.clear();
     239       83151 : }
     240             : 
     241     5346546 : 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    10693092 :   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    10693092 :   auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
     252     5346546 :   if (EP.first != nullptr || EP.second)
     253     5307148 :     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      267458 :   if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
     260             :     return;
     261             : 
     262             :   // When there were multiple different values, we may need new PHIs.
     263       39398 :   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       83151 : void LiveRangeCalc::calculateValues() {
     270             :   assert(Indexes && "Missing SlotIndexes");
     271             :   assert(DomTree && "Missing dominator tree");
     272       83151 :   updateSSA();
     273       83151 :   updateFromLiveIns();
     274       83151 : }
     275             : 
     276          97 : bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
     277             :                                  MachineBasicBlock &MBB, BitVector &DefOnEntry,
     278             :                                  BitVector &UndefOnEntry) {
     279          97 :   unsigned BN = MBB.getNumber();
     280         194 :   if (DefOnEntry[BN])
     281             :     return true;
     282         160 :   if (UndefOnEntry[BN])
     283             :     return false;
     284             : 
     285         271 :   auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
     286         271 :     for (MachineBasicBlock *S : B.successors())
     287         363 :       DefOnEntry[S->getNumber()] = true;
     288         150 :     DefOnEntry[BN] = true;
     289          75 :     return true;
     290          80 :   };
     291             : 
     292         160 :   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         308 :   for (MachineBasicBlock *P : MBB.predecessors())
     296         148 :     WorkList.insert(P->getNumber());
     297             : 
     298         241 :   for (unsigned i = 0; i != WorkList.size(); ++i) {
     299             :     // Determine if the exit from the block is reached by some def.
     300         204 :     unsigned N = WorkList[i];
     301         204 :     MachineBasicBlock &B = *MF->getBlockNumbered(N);
     302         306 :     if (Seen[N]) {
     303         204 :       const LiveOutPair &LOB = Map[&B];
     304         102 :       if (LOB.first != nullptr && LOB.first != &UndefVNI)
     305         146 :         return MarkDefined(B);
     306             :     }
     307          62 :     SlotIndex Begin, End;
     308         124 :     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          62 :     LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
     314          62 :                                               End.getPrevSlot());
     315          31 :     if (UB != LR.begin()) {
     316          23 :       LiveRange::Segment &Seg = *std::prev(UB);
     317          46 :       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          99 :     if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
     331          16 :       UndefOnEntry[N] = true;
     332           8 :       continue;
     333             :     }
     334          46 :     if (DefOnEntry[N])
     335           4 :       return MarkDefined(B);
     336             : 
     337             :     // Still don't know: add all predecessors to the work list.
     338          73 :     for (MachineBasicBlock *P : B.predecessors())
     339          35 :       WorkList.insert(P->getNumber());
     340             :   }
     341             : 
     342          10 :   UndefOnEntry[BN] = true;
     343           5 :   return false;
     344             : }
     345             : 
     346      267458 : bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
     347             :                                      SlotIndex Use, unsigned PhysReg,
     348             :                                      ArrayRef<SlotIndex> Undefs) {
     349      267458 :   unsigned UseMBBNum = UseMBB.getNumber();
     350             : 
     351             :   // Block numbers where LR should be live-in.
     352      534916 :   SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
     353             : 
     354             :   // Remember if we have seen more than one value.
     355      267458 :   bool UniqueVNI = true;
     356      267458 :   VNInfo *TheVNI = nullptr;
     357             : 
     358      267458 :   bool FoundUndef = false;
     359             : 
     360             :   // Using Seen as a visited set, perform a BFS for all reaching defs.
     361     3171326 :   for (unsigned i = 0; i != WorkList.size(); ++i) {
     362     3954615 :     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 BB#" << MBB->getNumber()
     381             :              << ", but is missing from the live-in list.\n";
     382             :       report_fatal_error("Invalid global physical register");
     383             :     }
     384             : #endif
     385     1318205 :     FoundUndef |= MBB->pred_empty();
     386             : 
     387     4393435 :     for (MachineBasicBlock *Pred : MBB->predecessors()) {
     388             :        // Is this a known live-out block?
     389     3514050 :        if (Seen.test(Pred->getNumber())) {
     390      806918 :          if (VNInfo *VNI = Map[Pred].first) {
     391      110857 :            if (TheVNI && TheVNI != VNI)
     392        1121 :              UniqueVNI = false;
     393             :            TheVNI = VNI;
     394             :          }
     395     1080370 :          continue;
     396             :        }
     397             : 
     398     2707132 :        SlotIndex Start, End;
     399     5414264 :        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     1353566 :        auto EP = LR.extendInBlock(Undefs, Start, End);
     404     1353566 :        VNInfo *VNI = EP.first;
     405     1353566 :        FoundUndef |= EP.second;
     406     2707132 :        setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
     407     1353566 :        if (VNI) {
     408      273445 :          if (TheVNI && TheVNI != VNI)
     409       45809 :            UniqueVNI = false;
     410             :          TheVNI = VNI;
     411             :        }
     412     1353566 :        if (VNI || EP.second)
     413      273452 :          continue;
     414             : 
     415             :        // No, we need a live-in value for Pred as well
     416     1080114 :        if (Pred != &UseMBB)
     417     1050747 :          WorkList.push_back(Pred->getNumber());
     418             :        else
     419             :           // Loopback to UseMBB, so value is really live through.
     420             :          Use = SlotIndex();
     421             :     }
     422             :   }
     423             : 
     424      534916 :   LiveIn.clear();
     425      267458 :   FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
     426      267458 :   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      267458 :   if (WorkList.size() > 4)
     432       46642 :     array_pod_sort(WorkList.begin(), WorkList.end());
     433             : 
     434             :   // If a unique reaching def was found, blit in the live ranges immediately.
     435      267458 :   if (UniqueVNI) {
     436             :     assert(TheVNI != nullptr && TheVNI != &UndefVNI);
     437      456120 :     LiveRangeUpdater Updater(&LR);
     438     1934980 :     for (unsigned BN : WorkList) {
     439     2501600 :       SlotIndex Start, End;
     440     5003200 :       std::tie(Start, End) = Indexes->getMBBRange(BN);
     441             :       // Trim the live range in UseMBB.
     442     1478860 :       if (BN == UseMBBNum && Use.isValid())
     443      198940 :         End = Use;
     444             :       else
     445     5259300 :         Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
     446     2501600 :       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       78796 :   std::tie(Entry, DidInsert) = EntryInfos.insert(
     455      393980 :       std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
     456       39398 :   if (DidInsert) {
     457             :     // Initialize newly inserted entries.
     458       73984 :     unsigned N = MF->getNumBlockIDs();
     459       36992 :     Entry->second.first.resize(N);
     460       36992 :     Entry->second.second.resize(N);
     461             :   }
     462       39398 :   BitVector &DefOnEntry = Entry->second.first;
     463       39398 :   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       78796 :   LiveIn.reserve(WorkList.size());
     468      185599 :   for (unsigned BN : WorkList) {
     469      134810 :     MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
     470       67507 :     if (!Undefs.empty() &&
     471          97 :         !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
     472           5 :       continue;
     473      134800 :     addLiveInBlock(LR, DomTree->getNode(MBB));
     474       67400 :     if (MBB == &UseMBB)
     475       78788 :       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       83151 : void LiveRangeCalc::updateSSA() {
     484             :   assert(Indexes && "Missing SlotIndexes");
     485             :   assert(DomTree && "Missing dominator tree");
     486             : 
     487             :   // Interate until convergence.
     488             :   bool Changed;
     489      127969 :   do {
     490      127969 :     Changed = false;
     491             :     // Propagate live-out values down the dominator tree, inserting phi-defs
     492             :     // when necessary.
     493      689973 :     for (LiveInBlock &I : LiveIn) {
     494      306066 :       MachineDomTreeNode *Node = I.DomNode;
     495             :       // Skip block if the live-in value has already been determined.
     496      306066 :       if (!Node)
     497      221407 :         continue;
     498      256149 :       MachineBasicBlock *MBB = Node->getBlock();
     499      256149 :       MachineDomTreeNode *IDom = Node->getIDom();
     500      256149 :       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      512298 :       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      702438 :         IDomValue = Map[IDom->getBlock()];
     511             : 
     512             :         // Cache the DomTree node that defined the value.
     513      234146 :         if (IDomValue.first && IDomValue.first != &UndefVNI &&
     514             :             !IDomValue.second) {
     515       50786 :           Map[IDom->getBlock()].second = IDomValue.second =
     516       25393 :             DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
     517             :         }
     518             : 
     519      757908 :         for (MachineBasicBlock *Pred : MBB->predecessors()) {
     520      628568 :           LiveOutPair &Value = Map[Pred];
     521      314284 :           if (!Value.first || Value.first == IDomValue.first)
     522      289427 :             continue;
     523       24857 :           if (Value.first == &UndefVNI) {
     524             :             needPHI = true;
     525             :             break;
     526             :           }
     527             : 
     528             :           // Cache the DomTree node that defined the value.
     529       24856 :           if (!Value.second)
     530       21622 :             Value.second =
     531       21622 :               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       49712 :           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      512298 :       LiveOutPair &LOP = Map[MBB];
     547             : 
     548             :       // Create a phi-def if required.
     549      256149 :       if (needPHI) {
     550       46671 :         Changed = true;
     551             :         assert(Alloc && "Need VNInfo allocator to create PHI-defs");
     552       93342 :         SlotIndex Start, End;
     553      186684 :         std::tie(Start, End) = Indexes->getMBBRange(MBB);
     554       46671 :         LiveRange &LR = I.LR;
     555       46671 :         VNInfo *VNI = LR.getNextValue(Start, *Alloc);
     556       46671 :         I.Value = VNI;
     557             :         // This block is done, we know the final value.
     558       46671 :         I.DomNode = nullptr;
     559             : 
     560             :         // Add liveness since updateFromLiveIns now skips this node.
     561       93342 :         if (I.Kill.isValid()) {
     562       38943 :           if (VNI)
     563       77886 :             LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
     564             :         } else {
     565        7728 :           if (VNI)
     566       15456 :             LR.addSegment(LiveInterval::Segment(Start, End, VNI));
     567       15456 :           LOP = LiveOutPair(VNI, Node);
     568             :         }
     569      209478 :       } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
     570             :         // No phi-def here. Remember incoming value.
     571      202505 :         I.Value = IDomValue.first;
     572             : 
     573             :         // If the IDomValue is killed in the block, don't propagate through.
     574      405010 :         if (I.Kill.isValid())
     575       23205 :           continue;
     576             : 
     577             :         // Propagate IDomValue if it isn't killed:
     578             :         // MBB is live-out and doesn't define its own value.
     579      179300 :         if (LOP.first == IDomValue.first)
     580       98368 :           continue;
     581       80932 :         Changed = true;
     582             :         LOP = IDomValue;
     583             :       }
     584             :     }
     585             :   } while (Changed);
     586      227763 : }

Generated by: LCOV version 1.13