LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveRangeCalc.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 210 224 93.8 %
Date: 2018-09-23 13:06:45 Functions: 13 14 92.9 %
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     7299780 : void LiveRangeCalc::resetLiveOutMap() {
      45     7299780 :   unsigned NumBlocks = MF->getNumBlockIDs();
      46             :   Seen.clear();
      47     7299780 :   Seen.resize(NumBlocks);
      48     7299780 :   EntryInfos.clear();
      49     7299780 :   Map.resize(NumBlocks);
      50     7299780 : }
      51             : 
      52     4540816 : void LiveRangeCalc::reset(const MachineFunction *mf,
      53             :                           SlotIndexes *SI,
      54             :                           MachineDominatorTree *MDT,
      55             :                           VNInfo::Allocator *VNIA) {
      56     4540816 :   MF = mf;
      57     4540816 :   MRI = &MF->getRegInfo();
      58     4540816 :   Indexes = SI;
      59     4540816 :   DomTree = MDT;
      60     4540816 :   Alloc = VNIA;
      61     4540816 :   resetLiveOutMap();
      62             :   LiveIn.clear();
      63     4540816 : }
      64             : 
      65     4816078 : static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
      66             :                           LiveRange &LR, const MachineOperand &MO) {
      67     4816078 :   const MachineInstr &MI = *MO.getParent();
      68             :   SlotIndex DefIdx =
      69     4816078 :       Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
      70             : 
      71             :   // Create the def in LR. This may find an existing def.
      72     4816078 :   LR.createDeadDef(DefIdx, Alloc);
      73     4816078 : }
      74             : 
      75     2758742 : 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     2758742 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
      82     2758742 :   unsigned Reg = LI.reg;
      83    13061819 :   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
      84     7544335 :     if (!MO.isDef() && !MO.readsReg())
      85             :       continue;
      86             : 
      87             :     unsigned SubReg = MO.getSubReg();
      88     7535255 :     if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
      89      722738 :       LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
      90      425734 :                                         : 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      425734 :       if (!LI.hasSubRanges() && !LI.empty()) {
      94       63087 :         LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
      95       63087 :         LI.createSubRangeFrom(*Alloc, ClassMask, LI);
      96             :       }
      97             : 
      98      851469 :       LI.refineSubRanges(*Alloc, SubMask,
      99      149313 :           [&MO, this](LiveInterval::SubRange &SR) {
     100      548846 :         if (MO.isDef())
     101      149313 :           createDeadDef(*Indexes, *Alloc, SR, MO);
     102             :       });
     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     7535256 :     if (MO.isDef() && !LI.hasSubRanges())
     108     3084349 :       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     2758742 :   LI.removeEmptySubRanges();
     114             : 
     115             :   // Step 2: Extend live segments to all uses, constructing SSA form as
     116             :   // necessary.
     117     2758742 :   if (LI.hasSubRanges()) {
     118      447919 :     for (LiveInterval::SubRange &S : LI.subranges()) {
     119      663400 :       LiveRangeCalc SubLRC;
     120      331700 :       SubLRC.reset(MF, Indexes, DomTree, Alloc);
     121      331700 :       SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
     122             :     }
     123             :     LI.clear();
     124      116219 :     constructMainRangeFromSubranges(LI);
     125             :   } else {
     126     2642523 :     resetLiveOutMap();
     127     2642523 :     extendToUses(LI, Reg, LaneBitmask::getAll());
     128             :   }
     129     2758742 : }
     130             : 
     131      116441 : void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
     132             :   // First create dead defs at all defs found in subranges.
     133      116441 :   LiveRange &MainRange = LI;
     134             :   assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
     135             :          "Expect empty main liverange");
     136             : 
     137      448720 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     138      665442 :     for (const VNInfo *VNI : SR.valnos) {
     139      333163 :       if (!VNI->isUnused() && !VNI->isPHIDef())
     140      333029 :         MainRange.createDeadDef(VNI->def, *Alloc);
     141             :     }
     142             :   }
     143      116441 :   resetLiveOutMap();
     144      116441 :   extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
     145      116441 : }
     146             : 
     147      789866 : 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     3162148 :   for (MachineOperand &MO : MRI->def_operands(Reg))
     153     1582416 :     createDeadDef(*Indexes, *Alloc, LR, MO);
     154      789866 : }
     155             : 
     156     3871213 : void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
     157             :                                  LiveInterval *LI) {
     158             :   SmallVector<SlotIndex, 4> Undefs;
     159     3871213 :   if (LI != nullptr)
     160      448141 :     LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
     161             : 
     162             :   // Visit all operands that read Reg. This may include partial defs.
     163     3871213 :   bool IsSubRange = !Mask.all();
     164     3871213 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     165    19695656 :   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    11953230 :     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     7313427 :     if (!MO.readsReg() || (IsSubRange && MO.isDef()))
     175     5610084 :       continue;
     176             : 
     177             :     unsigned SubReg = MO.getSubReg();
     178     6968249 :     if (SubReg != 0) {
     179     1207733 :       LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
     180     1207733 :       if (MO.isDef())
     181             :         SLM = ~SLM;
     182             :       // Ignore uses not reading the current (sub)range.
     183     1207733 :       if ((SLM & Mask).none())
     184             :         continue;
     185             :     }
     186             : 
     187             :     // Determine the actual place of the use.
     188     6343146 :     const MachineInstr *MI = MO.getParent();
     189     6343146 :     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       30837 :       UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
     196             :     } else {
     197             :       // Check for early-clobber redefs.
     198             :       bool isEarlyClobber = false;
     199             :       unsigned DefIdx;
     200     6332867 :       if (MO.isDef())
     201             :         isEarlyClobber = MO.isEarlyClobber();
     202     6232995 :       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      268653 :         isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
     206             :       }
     207    12665734 :       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     6343146 :     extend(LR, UseIdx, Reg, Undefs);
     213             :   }
     214     3871213 : }
     215             : 
     216      135842 : void LiveRangeCalc::updateFromLiveIns() {
     217      135842 :   LiveRangeUpdater Updater;
     218      323092 :   for (const LiveInBlock &I : LiveIn) {
     219      187250 :     if (!I.DomNode)
     220      101558 :       continue;
     221       85692 :     MachineBasicBlock *MBB = I.DomNode->getBlock();
     222             :     assert(I.Value && "No live-in value found");
     223             :     SlotIndex Start, End;
     224       85692 :     std::tie(Start, End) = Indexes->getMBBRange(MBB);
     225             : 
     226       85692 :     if (I.Kill.isValid())
     227             :       // Value is killed inside this block.
     228        7695 :       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       85692 :     Updater.setDest(&I.LR);
     236       85692 :     Updater.add(Start, End, I.Value);
     237             :   }
     238             :   LiveIn.clear();
     239      135842 : }
     240             : 
     241     6825750 : 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    13651500 :   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    13651500 :   auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
     252     6825750 :   if (EP.first != nullptr || EP.second)
     253     6732553 :     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      403313 :   if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
     260             :     return;
     261             : 
     262             :   // When there were multiple different values, we may need new PHIs.
     263       93197 :   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      135842 : void LiveRangeCalc::calculateValues() {
     270             :   assert(Indexes && "Missing SlotIndexes");
     271             :   assert(DomTree && "Missing dominator tree");
     272      135842 :   updateSSA();
     273      135842 :   updateFromLiveIns();
     274      135842 : }
     275             : 
     276         146 : bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
     277             :                                  MachineBasicBlock &MBB, BitVector &DefOnEntry,
     278             :                                  BitVector &UndefOnEntry) {
     279         146 :   unsigned BN = MBB.getNumber();
     280         146 :   if (DefOnEntry[BN])
     281             :     return true;
     282         115 :   if (UndefOnEntry[BN])
     283             :     return false;
     284             : 
     285             :   auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
     286             :     for (MachineBasicBlock *S : B.successors())
     287             :       DefOnEntry[S->getNumber()] = true;
     288             :     DefOnEntry[BN] = true;
     289             :     return true;
     290             :   };
     291             : 
     292         114 :   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         321 :   for (MachineBasicBlock *P : MBB.predecessors())
     296         207 :     WorkList.insert(P->getNumber());
     297             : 
     298         243 :   for (unsigned i = 0; i != WorkList.size(); ++i) {
     299             :     // Determine if the exit from the block is reached by some def.
     300         127 :     unsigned N = WorkList[i];
     301         127 :     MachineBasicBlock &B = *MF->getBlockNumbered(N);
     302         127 :     if (Seen[N]) {
     303             :       const LiveOutPair &LOB = Map[&B];
     304         127 :       if (LOB.first != nullptr && LOB.first != &UndefVNI)
     305         112 :         return MarkDefined(B);
     306             :     }
     307             :     SlotIndex Begin, End;
     308          51 :     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          51 :                                               End.getPrevSlot());
     315          51 :     if (UB != LR.begin()) {
     316             :       LiveRange::Segment &Seg = *std::prev(UB);
     317          49 :       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           5 :           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          51 :     if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
     331             :       UndefOnEntry[N] = true;
     332           5 :       continue;
     333             :     }
     334          46 :     if (DefOnEntry[N])
     335          36 :       return MarkDefined(B);
     336             : 
     337             :     // Still don't know: add all predecessors to the work list.
     338          30 :     for (MachineBasicBlock *P : B.predecessors())
     339          20 :       WorkList.insert(P->getNumber());
     340             :   }
     341             : 
     342             :   UndefOnEntry[BN] = true;
     343           2 :   return false;
     344             : }
     345             : 
     346      403313 : bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
     347             :                                      SlotIndex Use, unsigned PhysReg,
     348             :                                      ArrayRef<SlotIndex> Undefs) {
     349      403313 :   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     2649936 :   for (unsigned i = 0; i != WorkList.size(); ++i) {
     362     3686620 :     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     1843310 :     FoundUndef |= MBB->pred_empty();
     386             : 
     387     4330831 :     for (MachineBasicBlock *Pred : MBB->predecessors()) {
     388             :        // Is this a known live-out block?
     389     4975042 :        if (Seen.test(Pred->getNumber())) {
     390      534552 :          if (VNInfo *VNI = Map[Pred].first) {
     391      128598 :            if (TheVNI && TheVNI != VNI)
     392             :              UniqueVNI = false;
     393             :            TheVNI = VNI;
     394             :          }
     395     1013950 :          continue;
     396             :        }
     397             : 
     398             :        SlotIndex Start, End;
     399     1952969 :        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     1952969 :        auto EP = LR.extendInBlock(Undefs, Start, End);
     404     1952969 :        VNInfo *VNI = EP.first;
     405     1952969 :        FoundUndef |= EP.second;
     406     1952969 :        setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
     407     1952969 :        if (VNI) {
     408      479391 :          if (TheVNI && TheVNI != VNI)
     409             :            UniqueVNI = false;
     410             :          TheVNI = VNI;
     411             :        }
     412     1952969 :        if (VNI || EP.second)
     413             :          continue;
     414             : 
     415             :        // No, we need a live-in value for Pred as well
     416     1473571 :        if (Pred != &UseMBB)
     417     1439997 :          WorkList.push_back(Pred->getNumber());
     418             :        else
     419             :           // Loopback to UseMBB, so value is really live through.
     420             :          Use = SlotIndex();
     421             :     }
     422             :   }
     423             : 
     424             :   LiveIn.clear();
     425      403313 :   FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
     426      403313 :   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      403313 :   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      403313 :   if (UniqueVNI) {
     436             :     assert(TheVNI != nullptr && TheVNI != &UndefVNI);
     437      310116 :     LiveRangeUpdater Updater(&LR);
     438     2022214 :     for (unsigned BN : WorkList) {
     439             :       SlotIndex Start, End;
     440     1712098 :       std::tie(Start, End) = Indexes->getMBBRange(BN);
     441             :       // Trim the live range in UseMBB.
     442     1712098 :       if (BN == UseMBBNum && Use.isValid())
     443      276804 :         End = Use;
     444             :       else
     445     1435294 :         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       93197 :   std::tie(Entry, DidInsert) = EntryInfos.insert(
     455       93197 :       std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
     456       93197 :   if (DidInsert) {
     457             :     // Initialize newly inserted entries.
     458       91176 :     unsigned N = MF->getNumBlockIDs();
     459       91176 :     Entry->second.first.resize(N);
     460       91176 :     Entry->second.second.resize(N);
     461             :   }
     462       93197 :   BitVector &DefOnEntry = Entry->second.first;
     463       93197 :   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       93197 :   LiveIn.reserve(WorkList.size());
     468      224409 :   for (unsigned BN : WorkList) {
     469      131212 :     MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
     470      131358 :     if (!Undefs.empty() &&
     471         146 :         !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
     472             :       continue;
     473      131209 :     addLiveInBlock(LR, DomTree->getNode(MBB));
     474      131209 :     if (MBB == &UseMBB)
     475       93195 :       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      135842 : void LiveRangeCalc::updateSSA() {
     484             :   assert(Indexes && "Missing SlotIndexes");
     485             :   assert(DomTree && "Missing dominator tree");
     486             : 
     487             :   // Interate until convergence.
     488             :   bool Changed;
     489      235908 :   do {
     490             :     Changed = false;
     491             :     // Propagate live-out values down the dominator tree, inserting phi-defs
     492             :     // when necessary.
     493      658889 :     for (LiveInBlock &I : LiveIn) {
     494      422981 :       MachineDomTreeNode *Node = I.DomNode;
     495             :       // Skip block if the live-in value has already been determined.
     496      422981 :       if (!Node)
     497             :         continue;
     498      316553 :       MachineBasicBlock *MBB = Node->getBlock();
     499      316553 :       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      316553 :       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      247502 :         IDomValue = Map[IDom->getBlock()];
     511             : 
     512             :         // Cache the DomTree node that defined the value.
     513      247502 :         if (IDomValue.first && IDomValue.first != &UndefVNI &&
     514             :             !IDomValue.second) {
     515       69522 :           Map[IDom->getBlock()].second = IDomValue.second =
     516       34761 :             DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
     517             :         }
     518             : 
     519      548369 :         for (MachineBasicBlock *Pred : MBB->predecessors()) {
     520             :           LiveOutPair &Value = Map[Pred];
     521      333374 :           if (!Value.first || Value.first == IDomValue.first)
     522             :             continue;
     523       32785 :           if (Value.first == &UndefVNI) {
     524             :             needPHI = true;
     525             :             break;
     526             :           }
     527             : 
     528             :           // Cache the DomTree node that defined the value.
     529       32783 :           if (!Value.second)
     530       26492 :             Value.second =
     531       26492 :               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       65566 :           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      316553 :       if (needPHI) {
     550             :         Changed = true;
     551             :         assert(Alloc && "Need VNInfo allocator to create PHI-defs");
     552             :         SlotIndex Start, End;
     553      101558 :         std::tie(Start, End) = Indexes->getMBBRange(MBB);
     554      101558 :         LiveRange &LR = I.LR;
     555      101558 :         VNInfo *VNI = LR.getNextValue(Start, *Alloc);
     556      101558 :         I.Value = VNI;
     557             :         // This block is done, we know the final value.
     558      101558 :         I.DomNode = nullptr;
     559             : 
     560             :         // Add liveness since updateFromLiveIns now skips this node.
     561      101558 :         if (I.Kill.isValid()) {
     562       93224 :           if (VNI)
     563       93224 :             LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
     564             :         } else {
     565        8334 :           if (VNI)
     566        8334 :             LR.addSegment(LiveInterval::Segment(Start, End, VNI));
     567             :           LOP = LiveOutPair(VNI, Node);
     568             :         }
     569      214995 :       } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
     570             :         // No phi-def here. Remember incoming value.
     571      210688 :         I.Value = IDomValue.first;
     572             : 
     573             :         // If the IDomValue is killed in the block, don't propagate through.
     574      210688 :         if (I.Kill.isValid())
     575             :           continue;
     576             : 
     577             :         // Propagate IDomValue if it isn't killed:
     578             :         // MBB is live-out and doesn't define its own value.
     579      191916 :         if (LOP.first == IDomValue.first)
     580             :           continue;
     581             :         Changed = true;
     582             :         LOP = IDomValue;
     583             :       }
     584             :     }
     585             :   } while (Changed);
     586      135842 : }
     587             : 
     588           0 : bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB,
     589             :                                        ArrayRef<SlotIndex> Defs,
     590             :                                        const SlotIndexes &Indexes) {
     591           0 :   const MachineFunction &MF = *MBB->getParent();
     592           0 :   BitVector DefBlocks(MF.getNumBlockIDs());
     593           0 :   for (SlotIndex I : Defs)
     594           0 :     DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());
     595             : 
     596           0 :   SetVector<unsigned> PredQueue;
     597           0 :   PredQueue.insert(MBB->getNumber());
     598           0 :   for (unsigned i = 0; i != PredQueue.size(); ++i) {
     599           0 :     unsigned BN = PredQueue[i];
     600           0 :     if (DefBlocks[BN])
     601             :       return true;
     602             :     const MachineBasicBlock *B = MF.getBlockNumbered(BN);
     603           0 :     for (const MachineBasicBlock *P : B->predecessors())
     604           0 :       PredQueue.insert(P->getNumber());
     605             :   }
     606             :   return false;
     607             : }

Generated by: LCOV version 1.13