Rough proposal for an alternative way to recompute subreg liveness while respecting undef-read-defs

[MatzeB]

Summary

This is a rough patch on how I think liveness calculation for subregs that respects undef-read-defs should look like.

This is an unfinished patch, meant to move the discussion in D21189 forward (it is also based on this patch).

[MatzeB]

I tested this with AMDGPU lit tests and the two tests I meantioned in D21189, I just realized that I did not have hexagon enabled and that target probably needs some further changes.

[kparzysz]

I have merged this into D21189.

[MatzeB]

This got merged into D21189

include/llvm/CodeGen/LiveInterval.h

struct Segment {
         return start == Other.start && end == Other.end;
       }
 
       void dump() const;
     };
 
     typedef SmallVector<Segment, 2> Segments;
     typedef SmallVector<VNInfo *, 2> VNInfoList;
-    typedef SmallVector<SlotIndex, 2> SlotList;
 
     Segments segments;   // the liveness segments
     VNInfoList valnos;   // value#'s
-    SlotList undefs;     // explicit "undefs" via <def,read-undef>
 
     // The segment set is used temporarily to accelerate initial computation
     // of live ranges of physical registers in computeRegUnitRange.
     // After that the set is flushed to the segment vector and deleted.
     typedef std::set<Segment> SegmentSet;
     std::unique_ptr<SegmentSet> segmentSet;
 
     typedef Segments::iterator iterator;
public:
 
     const_iterator find(SlotIndex Pos) const {
       return const_cast<LiveRange*>(this)->find(Pos);
     }
 
     void clear() {
       valnos.clear();
       segments.clear();
-      undefs.clear();
     }
 
     size_t size() const {
       return segments.size();
     }
 
     bool hasAtLeastOneValue() const { return !valnos.empty(); }
 
public:
     /// [1,5](5,10] covers (3,7].
     bool covers(const LiveRange &Other) const;
 
     /// Add the specified Segment to this range, merging segments as
     /// appropriate.  This returns an iterator to the inserted segment (which
     /// may have grown since it was inserted).
     iterator addSegment(Segment S);
 
+    VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
+
     /// Attempt to extend a value defined after @p StartIdx to include @p Use.
     /// Both @p StartIdx and @p Use should be in the same basic block. In case
     /// of subranges, an extension could be prevented by an explicit "undef"
     /// caused by a <def,read-undef> on a non-overlapping lane.
     /// The return value is a pair: the first element is VNInfo of the value
     /// that was extended (possibly nullptr), the second is a boolean value
     /// indicating whether an "undef" was encountered.
     /// If this range is live before @p Use in the basic block that starts at
     /// @p StartIdx, and there is no intervening "undef", extend it to be live
     /// up to @p Use, and return the pair {value, false}. If there is no
     /// segment before @p Use and there is no "undef" between @p StartIdx and
     /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use,
     /// return {nullptr, true}.
-    std::pair<VNInfo*,bool> extendInBlock(SlotIndex StartIdx, SlotIndex Use);
+    std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
+        SlotIndex StartIdx, SlotIndex Use);
 
     /// join - Join two live ranges (this, and other) together.  This applies
     /// mappings to the value numbers in the LHS/RHS ranges as specified.  If
     /// the ranges are not joinable, this aborts.
     void join(LiveRange &Other,
               const int *ValNoAssignments,
               const int *RHSValNoAssignments,
               SmallVectorImpl<VNInfo *> &NewVNInfo);
public:
     bool operator<(const LiveRange& other) const {
       const SlotIndex &thisIndex = beginIndex();
       const SlotIndex &otherIndex = other.beginIndex();
       return thisIndex < otherIndex;
     }
 
     /// Returns true if there is an explicit "undef" between @p Begin
     /// @p End.
-    bool isUndefIn(SlotIndex Begin, SlotIndex End) const {
-      return std::any_of(undefs.begin(), undefs.end(),
+    bool isUndefIn(ArrayRef<SlotIndex> Undefs, SlotIndex Begin,
+                   SlotIndex End) const {
+      return std::any_of(Undefs.begin(), Undefs.end(),
                 [Begin,End] (SlotIndex Idx) -> bool {
                   return Begin <= Idx && Idx < End;
                 });
     }
 
     /// Flush segment set into the regular segment vector.
     /// The method is to be called after the live range
     /// has been created, if use of the segment set was
     /// activated in the constructor of the live range.
     void flushSegmentSet();
 
-    void clearUndefs() { undefs.clear(); }
-
     void print(raw_ostream &OS) const;
     void dump() const;
 
     /// \brief Walk the range and assert if any invariants fail to hold.
     ///
     /// Note that this is a no-op when asserts are disabled.
 #ifdef NDEBUG
     void verify() const {}
bool isSpillable() const {
       return weight != llvm::huge_valf;
     }
 
     /// markNotSpillable - Mark interval as not spillable
     void markNotSpillable() {
       weight = llvm::huge_valf;
     }
 
-    void clearSubRangeUndefs() {
-      super::clearUndefs();
-      for (SubRange &S : subranges())
-        S.clearUndefs();
-    }
-
-    /// Recalculate explicit "undefs" for all subranges: if a subrange is
-    /// defined at Idx, any subranges that are not defined at Idx and are
-    /// not live at Idx will be considered explicitly undefined.
-    void recalculateSubRangeUndefs();
-
     bool operator<(const LiveInterval& other) const {
       const SlotIndex &thisIndex = beginIndex();
       const SlotIndex &otherIndex = other.beginIndex();
       return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg);
     }
 
     void print(raw_ostream &OS) const;
     void dump() const;

include/llvm/CodeGen/LiveIntervalAnalysis.h

public:
     /// no effect. This is useful when extending subranges, but increases
     /// the complexity of the extension code.
     /// PHI-defs are added as needed to maintain SSA form.
     ///
     /// If a SlotIndex in @p Indices is the end index of a basic block, @p LR
     /// will be extended to be live out of the basic block.
     ///
     /// See also LiveRangeCalc::extend().
-    void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices,
-                         bool AllowUndef = false);
+    void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices);
 
 
     /// If @p LR has a live value at @p Kill, prune its live range by removing
     /// any liveness reachable from Kill. Add live range end points to
     /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the
     /// value's live range.
     ///
     /// Calling pruneValue() and extendToIndices() can be used to reconstruct

lib/CodeGen/LiveInterval.cpp

if (SlotIndex::isSameInstr(Def, S->start)) {
       return S->valno;
     }
     assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
     VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);
     segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
     return VNI;
   }
 
-  std::pair<VNInfo*,bool> extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
+  VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
+    if (segments().empty())
+      return nullptr;
+    iterator I =
+      impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));
+    if (I == segments().begin())
+      return nullptr;
+    --I;
+    if (I->end <= StartIdx)
+      return nullptr;
+    if (I->end < Use)
+      extendSegmentEndTo(I, Use);
+    return I->valno;
+  }
+
+  std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
+      SlotIndex StartIdx, SlotIndex Use) {
     if (segments().empty())
       return std::make_pair(nullptr, false);
     SlotIndex BeforeUse = Use.getPrevSlot();
     iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));
     if (I == segments().begin())
-      return std::make_pair(nullptr, LR->isUndefIn(StartIdx, BeforeUse));
+      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
     --I;
     if (I->end <= StartIdx)
-      return std::make_pair(nullptr, LR->isUndefIn(StartIdx, BeforeUse));
+      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
     if (I->end < Use) {
-      if (LR->isUndefIn(I->end, BeforeUse))
+      if (LR->isUndefIn(Undefs, I->end, BeforeUse))
         return std::make_pair(nullptr, true);
       extendSegmentEndTo(I, Use);
     }
     return std::make_pair(I->valno, false);
   }
 
   /// This method is used when we want to extend the segment specified
   /// by I to end at the specified endpoint. To do this, we should

 LiveRange::iterator LiveRange::addSegment(Segment S) {
   // Use the segment set, if it is available.
   if (segmentSet != nullptr) {
     addSegmentToSet(S);
     return end();
   }
   // Otherwise use the segment vector.
   LiveRange::iterator I = CalcLiveRangeUtilVector(this).addSegment(S);
-  pruneUndefs();
   return I;
 }
 
 void LiveRange::append(const Segment S) {
   // Check that the segment belongs to the back of the list.
   assert(segments.empty() || segments.back().end <= S.start);
   segments.push_back(S);
-  pruneUndefs();
 }
 
 /// extendInBlock - If this range is live before Kill in the basic
 /// block that starts at StartIdx, extend it to be live up to Kill and return
 /// the value. If there is no live range before Kill, return NULL.
-std::pair<VNInfo*,bool> LiveRange::extendInBlock(SlotIndex StartIdx,
-                                                 SlotIndex Kill) {
+std::pair<VNInfo*,bool> LiveRange::extendInBlock(ArrayRef<SlotIndex> Undefs,
+    SlotIndex StartIdx, SlotIndex Kill) {
+  // Use the segment set, if it is available.
+  if (segmentSet != nullptr)
+    return CalcLiveRangeUtilSet(this).extendInBlock(Undefs, StartIdx, Kill);
+  // Otherwise use the segment vector.
+  return CalcLiveRangeUtilVector(this).extendInBlock(Undefs, StartIdx, Kill);
+}
+
+VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
   // Use the segment set, if it is available.
   if (segmentSet != nullptr)
     return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);
   // Otherwise use the segment vector.
   return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);
 }
 
 /// Remove the specified segment from this range.  Note that the segment must

 
 void LiveRange::flushSegmentSet() {
   assert(segmentSet != nullptr && "segment set must have been created");
   assert(
       segments.empty() &&
       "segment set can be used only initially before switching to the array");
   segments.append(segmentSet->begin(), segmentSet->end());
   segmentSet = nullptr;
-  pruneUndefs();
   verify();
 }
 
 bool LiveRange::isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const {
   ArrayRef<SlotIndex>::iterator SlotI = Slots.begin();
   ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
 
   // If there are no regmask slots, we have nothing to search.
if (SegmentI->contains(*SlotI))
       return true;
     // Otherwise, look for the next slot.
   }
 
   // We didn't find a segment containing any of the slots.
   return false;
 }
 
-void LiveRange::pruneUndefs() {
-  for (unsigned i = undefs.size(); i > 0; --i)
-    if (getSegmentContaining(undefs[i-1]))
-      undefs.erase(undefs.begin()+i-1);
-}
-
 void LiveInterval::freeSubRange(SubRange *S) {
   S->~SubRange();
   // Memory was allocated with BumpPtr allocator and is not freed here.
 }
 
 void LiveInterval::removeEmptySubRanges() {
   SubRange **NextPtr = &SubRanges;
   SubRange *I = *NextPtr;

 void LiveInterval::clearSubRanges() {
   for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) {
     Next = I->Next;
     freeSubRange(I);
   }
   SubRanges = nullptr;
 }
 
-void LiveInterval::recalculateSubRangeUndefs() {
-  clearSubRangeUndefs();
-  // Go over the main range and visit all register defs. For each subrange
-  // that is not live immediately after the point of the def, add "undef"
-  // to it. An exception is a subrange with a dead def at that position---
-  // it should not receive an undef.
-  for (Segment &Seg : *this) {
-    if (!Seg.start.isRegister())
-      continue;
-    SlotIndex After = Seg.start.getDeadSlot();
-    for (SubRange &S : subranges()) {
-      // If S has a def at Seg.start, skip it.
-      iterator I = S.find(Seg.start);
-      if (I != S.end() && I->start == Seg.start)
-        continue;
-      if (I == S.end() || I->start >= After)
-        S.undefs.push_back(Seg.start);
-    }
-  }
-}
-
 unsigned LiveInterval::getSize() const {
   unsigned Sum = 0;
   for (const Segment &S : segments)
     Sum += S.start.distance(S.end);
   return Sum;
 }
 
 raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange::Segment &S) {
for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
         OS << 'x';
       } else {
         OS << vni->def;
         if (vni->isPHIDef())
           OS << "-phi";
       }
     }
   }
-
-  if (!undefs.empty()) {
-    OS << "  undef@";
-    for (unsigned i = 0, n = undefs.size(); i != n; ++i) {
-      OS << undefs[i];
-      if (i != n-1)
-        OS << ',';
-    }
-  }
 }
 
 void LiveInterval::SubRange::print(raw_ostream &OS) const {
   OS << " L" << PrintLaneMask(LaneMask) << ' '
      << static_cast<const LiveRange&>(*this);
 }
 
 void LiveInterval::print(raw_ostream &OS) const {
for (const_iterator I = begin(), E = end(); I != E; ++I) {
     assert(I->valno->id < valnos.size());
     assert(I->valno == valnos[I->valno->id]);
     if (std::next(I) != E) {
       assert(I->end <= std::next(I)->start);
       if (I->end == std::next(I)->start)
         assert(I->valno != std::next(I)->valno);
     }
   }
-  for (SlotIndex U : undefs)
-    assert(getSegmentContaining(U) == nullptr);
 }
 
 void LiveInterval::verify(const MachineRegisterInfo *MRI) const {
   super::verify();
 
   // Make sure SubRanges are fine and LaneMasks are disjunct.
   LaneBitmask Mask = 0;
   LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg) : ~0u;
void LiveRangeUpdater::flush() {
   // Clear the dirty state.
   LastStart = SlotIndex();
 
   assert(LR && "Cannot add to a null destination");
 
   // Nothing to merge?
   if (Spills.empty()) {
     LR->segments.erase(WriteI, ReadI);
-    LR->pruneUndefs();
     LR->verify();
     return;
   }
 
   // Resize the WriteI - ReadI gap to match Spills.
   size_t GapSize = ReadI - WriteI;
   if (GapSize < Spills.size()) {
     // The gap is too small. Make some room.
     size_t WritePos = WriteI - LR->begin();
     LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());
     // This also invalidated ReadI, but it is recomputed below.
     WriteI = LR->begin() + WritePos;
   } else {
     // Shrink the gap if necessary.
     LR->segments.erase(WriteI + Spills.size(), ReadI);
   }
   ReadI = WriteI + Spills.size();
   mergeSpills();
-  LR->pruneUndefs();
   LR->verify();
 }
 
 unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) {
   // Create initial equivalence classes.
   EqClass.clear();
   EqClass.grow(LR.getNumValNums());
 

lib/CodeGen/LiveIntervalAnalysis.cpp

for (auto VNI : VNIs) {
     LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
   }
 }
 
 typedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList;
 
 static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
                                  ShrinkToUsesWorkList &WorkList,
-                                 const LiveRange &OldRange, bool AllowUndef) {
+                                 const LiveRange &OldRange) {
   // Keep track of the PHIs that are in use.
   SmallPtrSet<VNInfo*, 8> UsedPHIs;
   // Blocks that have already been added to WorkList as live-out.
   SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
 
   // Extend intervals to reach all uses in WorkList.
   while (!WorkList.empty()) {
     SlotIndex Idx = WorkList.back().first;
     VNInfo *VNI = WorkList.back().second;
     WorkList.pop_back();
     const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
     SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
 
     // Extend the live range for VNI to be live at Idx.
-    if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx).first) {
+    if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
       assert(ExtVNI == VNI && "Unexpected existing value number");
       (void)ExtVNI;
       // Is this a PHIDef we haven't seen before?
       if (!VNI->isPHIDef() || VNI->def != BlockStart ||
           !UsedPHIs.insert(VNI).second)
         continue;
       // The PHI is live, make sure the predecessors are live-out.
       for (auto &Pred : MBB->predecessors()) {
while (!WorkList.empty()) {
     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
     LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
 
     // Make sure VNI is live-out from the predecessors.
     for (auto &Pred : MBB->predecessors()) {
       if (!LiveOut.insert(Pred).second)
         continue;
       SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
-      if (AllowUndef && OldRange.getVNInfoBefore(Stop) == nullptr)
-        continue;
       assert(OldRange.getVNInfoBefore(Stop) == VNI &&
              "Wrong value out of predecessor");
       WorkList.push_back(std::make_pair(Stop, VNI));
     }
   }
 }
 
 bool LiveIntervals::shrinkToUses(LiveInterval *li,
if (VNInfo *DefVNI = LRQ.valueDefined())
       Idx = DefVNI->def;
 
     WorkList.push_back(std::make_pair(Idx, VNI));
   }
 
   // Create new live ranges with only minimal live segments per def.
   LiveRange NewLR;
   createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
-  extendSegmentsToUses(NewLR, *Indexes, WorkList, *li, false);
+  extendSegmentsToUses(NewLR, *Indexes, WorkList, *li);
 
   // Move the trimmed segments back.
   li->segments.swap(NewLR.segments);
 
   // Handle dead values.
   bool CanSeparate = computeDeadValues(*li, dead);
   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
   return CanSeparate;
if (VNInfo *DefVNI = LRQ.valueDefined())
       Idx = DefVNI->def;
 
     WorkList.push_back(std::make_pair(Idx, VNI));
   }
 
   // Create a new live ranges with only minimal live segments per def.
   LiveRange NewLR;
   createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
-  extendSegmentsToUses(NewLR, *Indexes, WorkList, SR, true);
+  extendSegmentsToUses(NewLR, *Indexes, WorkList, SR);
 
   // Move the trimmed ranges back.
   SR.segments.swap(NewLR.segments);
 
   // Remove dead PHI value numbers
   for (auto VNI : SR.valnos) {
     if (VNI->isUnused())
       continue;
     const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
     assert(Segment != nullptr && "Missing segment for VNI");
     if (Segment->end != VNI->def.getDeadSlot())
       continue;
     if (VNI->isPHIDef()) {
       // This is a dead PHI. Remove it.
       DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
       VNI->markUnused();
       SR.removeSegment(*Segment);
     }
   }
 
   DEBUG(dbgs() << "Shrunk: " << SR << '\n');
 }
 
 void LiveIntervals::extendToIndices(LiveRange &LR,
-                                    ArrayRef<SlotIndex> Indices,
-                                    bool AllowUndef) {
+                                    ArrayRef<SlotIndex> Indices) {
   assert(LRCalc && "LRCalc not initialized.");
   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
+  SmallVector<SlotIndex, 0> Undefs;
   for (unsigned i = 0, e = Indices.size(); i != e; ++i)
-    LRCalc->extend(LR, Indices[i], /*PhysReg=*/0, AllowUndef);
+    LRCalc->extend(LR, Indices[i], /*PhysReg=*/0, Undefs);
 }
 
 void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
                                SmallVectorImpl<SlotIndex> *EndPoints) {
   LiveQueryResult LRQ = LR.Query(Kill);
   VNInfo *VNI = LRQ.valueOutOrDead();
   if (!VNI)
     return;
for (MachineOperand &MO : MI->operands()) {
       }
 
       unsigned Reg = MO.getReg();
       if (!Reg)
         continue;
       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
         LiveInterval &LI = LIS.getInterval(Reg);
         if (LI.hasSubRanges()) {
-          LI.clearSubRangeUndefs();
           unsigned SubReg = MO.getSubReg();
           LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
                                         : MRI.getMaxLaneMaskForVReg(Reg);
           for (LiveInterval::SubRange &S : LI.subranges()) {
             if ((S.LaneMask & LaneMask) == 0)
               continue;
             updateRange(S, Reg, S.LaneMask);
           }
if (hasRegMask)
       updateRegMaskSlots();
 
     for (MachineOperand &MO : MI->operands()) {
       if (!MO.isReg() || !MO.isDef())
         continue;
       unsigned Reg = MO.getReg();
       if (!TargetRegisterInfo::isVirtualRegister(Reg))
         continue;
-      LIS.getInterval(Reg).recalculateSubRangeUndefs();
     }
   }
 
 private:
   /// Update a single live range, assuming an instruction has been moved from
   /// OldIdx to NewIdx.
   void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
     if (!Updated.insert(&LR).second)

lib/CodeGen/LiveRangeCalc.h

class LiveRangeCalc {
   /// LiveIn - Work list of blocks where the live-in value has yet to be
   /// determined.  This list is typically computed by findReachingDefs() and
   /// used as a work list by updateSSA().  The low-level interface may also be
   /// used to add entries directly.
   SmallVector<LiveInBlock, 16> LiveIn;
 
   /// Check if the entry to block @p MBB can be reached by any of the defs
   /// in @p LR. Return true if none of the defs reach the entry to @p MBB.
-  bool isDefOnEntry(LiveRange &LR, MachineBasicBlock &MBB,
-                    BitVector &DefOnEntry, BitVector &UndefOnEntry);
+  bool isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
+                    MachineBasicBlock &MBB, BitVector &DefOnEntry,
+                    BitVector &UndefOnEntry);
 
   /// Find the set of defs that can reach @p Kill. @p Kill must belong to
   /// @p UseMBB.
   ///
   /// If exactly one def can reach @p UseMBB, and the def dominates @p Kill,
   /// all paths from the def to @p UseMBB are added to @p LR, and the function
   /// returns true.
   ///
   /// If multiple values can reach @p UseMBB, the blocks that need @p LR to be
   /// live in are added to the LiveIn array, and the function returns false.
   ///
   /// Unless @p AllowUndef is set, it is assumed that @p LR is live at @p Kill.
   /// If @p AllowUndef is set and @p Kill can be reached from entry without
   /// encountering any def, the function returns false. Allowing @p Kill to be
   /// undefined helps when extending subranges of a live interval: while the
   /// register as a whole may be live at @p Kill, a particular subregister may
   /// be undefined. Whether that is the case or not is often unknown until the
   /// reaching defs are actually located.
   ///
   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
   bool findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
-                        SlotIndex Kill, unsigned PhysReg, bool AllowUndef);
+                        SlotIndex Kill, unsigned PhysReg,
+                        ArrayRef<SlotIndex> Undefs);
 
   /// updateSSA - Compute the values that will be live in to all requested
   /// blocks in LiveIn.  Create PHI-def values as required to preserve SSA form.
   ///
   /// Every live-in block must be jointly dominated by the added live-out
   /// blocks.  No values are read from the live ranges.
   void updateSSA();
 
class LiveRangeCalc {
   ///   Reg:sub1<def,read-undef> = ...
   /// The second def does not read Reg, and by looking at machine operands
   /// alone, the main live range for Reg would seem to have two defs, the
   /// first of which does not reach any use. It would then appear to be
   /// dead, while in fact, the sub0 lane is actually live. Inserting the
   /// location of the second def into the @p LiveAt set informs this
   /// function that Reg is live at that location.
   void extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask,
-                    bool AllowUndef = false);
+                    LiveInterval *LI = nullptr);
 
   /// Reset Map and Seen fields.
   void resetLiveOutMap();
 
 public:
   LiveRangeCalc() : MF(nullptr), MRI(nullptr), Indexes(nullptr),
                     DomTree(nullptr), Alloc(nullptr) {}
 
public:
 
   //===--------------------------------------------------------------------===//
   // Mid-level interface.
   //===--------------------------------------------------------------------===//
   //
   // Modify existing live ranges.
   //
 
+  void computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs,
+                             LiveInterval &LI, LaneBitmask LaneMask) const;
+
   /// Extend the live range of @p LR to reach @p Use.
   ///
   /// The existing values in @p LR must be live so they jointly dominate @p Use.
   /// If @p Use is not dominated by a single existing value, PHI-defs are
   /// inserted as required to preserve SSA form.
   ///
   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
-  void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg = 0,
-              bool AllowUndef = false);
+  void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
+              ArrayRef<SlotIndex> Undefs);
 
   /// createDeadDefs - Create a dead def in LI for every def operand of Reg.
   /// Each instruction defining Reg gets a new VNInfo with a corresponding
   /// minimal live range.
   void createDeadDefs(LiveRange &LR, unsigned Reg);
 
   /// Extend the live range of @p LR to reach all uses of Reg.
   ///

lib/CodeGen/LiveRangeCalc.cpp

void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
   // Visit all def operands. If the same instruction has multiple defs of Reg,
   // createDeadDef() will deduplicate.
   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
   unsigned Reg = LI.reg;
   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     if (!MO.isDef() && !MO.readsReg())
       continue;
 
-    const MachineInstr &MI = *MO.getParent();
-    bool IsEC = MO.isEarlyClobber();
-    SlotIndex Idx = Indexes->getInstructionIndex(MI).getRegSlot(IsEC);
-
     unsigned SubReg = MO.getSubReg();
     if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
       LaneBitmask WholeMask = MRI->getMaxLaneMaskForVReg(Reg);
       LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
                                         : WholeMask;
       // If this is the first time we see a subregister def, initialize
       // subranges by creating a copy of the main range.
       if (!LI.hasSubRanges() && !LI.empty()) {
if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
         Mask &= ~Common;
       }
       // Create a new SubRange for subregs we did not cover yet.
       if (Mask != 0) {
         LiveInterval::SubRange *NewRange = LI.createSubRange(*Alloc, Mask);
         if (MO.isDef())
           createDeadDef(*Indexes, *Alloc, *NewRange, MO);
       }
-
-      if (MO.isDef() && MO.isUndef() && SubReg != 0) {
-        LaneBitmask UndefMask = WholeMask & ~SubMask;
-        // Add undefs to the subranges covered by UndefMask. Create new
-        // subranges if necessary.
-        for (LiveInterval::SubRange &S : LI.subranges()) {
-          LaneBitmask Common = S.LaneMask & UndefMask;
-          if (Common == 0)
-            continue;
-          getCommonRange(S, UndefMask)->undefs.push_back(Idx);
-          UndefMask &= ~Common;
-        }
-        if (UndefMask != 0)
-          LI.createSubRange(*Alloc, UndefMask)->undefs.push_back(Idx);
-      }
     }
 
     // Create the def in the main liverange. We do not have to do this if
     // subranges are tracked as we recreate the main range later in this case.
     if (MO.isDef() && !LI.hasSubRanges())
       createDeadDef(*Indexes, *Alloc, LI, MO);
   }
 
   // We may have created empty live ranges for partially undefined uses, we
   // can't keep them because we won't find defs in them later.
   LI.removeEmptySubRanges();
 
   // Step 2: Extend live segments to all uses, constructing SSA form as
   // necessary.
   if (LI.hasSubRanges()) {
     for (LiveInterval::SubRange &S : LI.subranges()) {
       LiveRangeCalc SubLRC;
       SubLRC.reset(MF, Indexes, DomTree, Alloc);
-      SubLRC.extendToUses(S, Reg, S.LaneMask, true);
+      SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
     }
     LI.clear();
     constructMainRangeFromSubranges(LI);
   } else {
     resetLiveOutMap();
     extendToUses(LI, Reg, ~0u);
   }
 }
 
 void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
   // First create dead defs at all defs found in subranges.
   LiveRange &MainRange = LI;
   assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
          "Expect empty main liverange");
 
   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     for (const VNInfo *VNI : SR.valnos) {
       if (!VNI->isUnused() && !VNI->isPHIDef())
         MainRange.createDeadDef(VNI->def, *Alloc);
     }
   }
   resetLiveOutMap();
-  extendToUses(MainRange, LI.reg, ~0U, true);
+  extendToUses(MainRange, LI.reg, ~0U, &LI);
 }
 
 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
   assert(MRI && Indexes && "call reset() first");
 
   // Visit all def operands. If the same instruction has multiple defs of Reg,
   // LR.createDeadDef() will deduplicate.
   for (MachineOperand &MO : MRI->def_operands(Reg))
     createDeadDef(*Indexes, *Alloc, LR, MO);
 }
 
 
 void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
-                                 bool AllowUndef) {
+                                 LiveInterval *LI) {
+  SmallVector<SlotIndex, 4> Undefs;
+  if (LI != nullptr)
+    computeSubRangeUndefs(Undefs, *LI, Mask);
+
   // Visit all operands that read Reg. This may include partial defs.
   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     // Clear all kill flags. They will be reinserted after register allocation
     // by LiveIntervalAnalysis::addKillFlags().
     if (MO.isUse())
       MO.setIsKill(false);
     if (!MO.readsReg())
if (MI->isPHI()) {
         // had an early-clobber flag.
         isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
       }
       UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
     }
 
     // MI is reading Reg. We may have visited MI before if it happens to be
     // reading Reg multiple times. That is OK, extend() is idempotent.
-    extend(LR, UseIdx, Reg, AllowUndef);
+    extend(LR, UseIdx, Reg, Undefs);
   }
 }
 
 
 void LiveRangeCalc::updateFromLiveIns() {
   LiveRangeUpdater Updater;
   for (const LiveInBlock &I : LiveIn) {
     if (!I.DomNode)
else {
       Map[MBB] = LiveOutPair(I.Value, nullptr);
     }
     Updater.setDest(&I.LR);
     Updater.add(Start, End, I.Value);
   }
   LiveIn.clear();
 }
 
+void LiveRangeCalc::computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs,
+                                          LiveInterval &LI,
+                                          LaneBitmask LaneMask) const {
+  unsigned Reg = LI.reg;
+  assert(TargetRegisterInfo::isVirtualRegister(Reg));
+  unsigned VRegMask = MRI->getMaxLaneMaskForVReg(Reg);
+  assert((VRegMask & LaneMask) != 0);
+  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
+  for (const MachineOperand &MO : MRI->def_operands(Reg)) {
+    if (!MO.isUndef())
+      continue;
+    unsigned SubReg = MO.getSubReg();
+    assert(SubReg != 0 && "Undef should only be set on subreg defs");
+    LaneBitmask DefMask = TRI.getSubRegIndexLaneMask(SubReg);
+    LaneBitmask UndefMask = VRegMask & ~DefMask;
+    if ((UndefMask & LaneMask) != 0) {
+      const MachineInstr &MI = *MO.getParent();
+      bool EarlyClobber = MO.isEarlyClobber();
+      SlotIndex Pos = Indexes->getInstructionIndex(MI).getRegSlot(EarlyClobber);
+      Undefs.push_back(Pos);
+    }
+  }
+}
 
 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
-                           bool AllowUndef) {
+                           ArrayRef<SlotIndex> Undefs) {
   assert(Use.isValid() && "Invalid SlotIndex");
   assert(Indexes && "Missing SlotIndexes");
   assert(DomTree && "Missing dominator tree");
 
   MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
   assert(UseMBB && "No MBB at Use");
 
   // Is there a def in the same MBB we can extend?
-  auto EP = LR.extendInBlock(Indexes->getMBBStartIdx(UseMBB), Use);
+  auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
   if (EP.first != nullptr || EP.second)
     return;
 
   // Find the single reaching def, or determine if Use is jointly dominated by
   // multiple values, and we may need to create even more phi-defs to preserve
   // VNInfo SSA form.  Perform a search for all predecessor blocks where we
   // know the dominating VNInfo.
-  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, AllowUndef))
+  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
     return;
 
   // When there were multiple different values, we may need new PHIs.
   calculateValues();
 }
 
 
 // This function is called by a client after using the low-level API to add
 // live-out and live-in blocks.  The unique value optimization is not
 // available, SplitEditor::transferValues handles that case directly anyway.
 void LiveRangeCalc::calculateValues() {
   assert(Indexes && "Missing SlotIndexes");
   assert(DomTree && "Missing dominator tree");
   updateSSA();
   updateFromLiveIns();
 }
 
 
-bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, MachineBasicBlock &MBB,
-      BitVector &DefOnEntry, BitVector &UndefOnEntry) {
+bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
+                                 MachineBasicBlock &MBB, BitVector &DefOnEntry,
+                                 BitVector &UndefOnEntry) {
   unsigned BN = MBB.getNumber();
   if (DefOnEntry[BN])
     return true;
   if (UndefOnEntry[BN])
     return false;
 
   auto MarkDefined =
         [this,BN,&DefOnEntry,&UndefOnEntry] (MachineBasicBlock &B) -> bool {
for (unsigned i = 0; i != WorkList.size(); ++i) {
     LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(), End);
     if (UB != LR.begin()) {
       LiveRange::Segment &Seg = *std::prev(UB);
       if (Seg.end > Begin) {
         // There is a segment that overlaps B. If the range is not explicitly
         // undefined between the end of the segment and the end of the block,
         // treat the block as defined on exit. If it is, go to the next block
         // on the work list.
-        if (LR.isUndefIn(Seg.end, End))
+        if (LR.isUndefIn(Undefs, Seg.end, End))
           continue;
         return MarkDefined(B);
       }
     }
 
     // No segment overlaps with this block. If this block is not defined on
     // entry, or it undefines the range, do not process its predecessors.
-    if (UndefOnEntry[N] || LR.isUndefIn(Begin, End)) {
+    if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
       UndefOnEntry[N] = true;
       continue;
     }
     if (DefOnEntry[N])
       return MarkDefined(B);
 
     // Still don't know: add all predecessors to the work list.
     for (MachineBasicBlock *P : B.predecessors())
       WorkList.insert(P->getNumber());
   }
 
   UndefOnEntry[BN] = true;
   return false;
 }
 
 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
                                      SlotIndex Use, unsigned PhysReg,
-                                     bool AllowUndef) {
+                                     ArrayRef<SlotIndex> Undefs) {
   unsigned UseMBBNum = UseMBB.getNumber();
 
   // Block numbers where LR should be live-in.
   SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
 
   // Remember if we have seen more than one value.
   bool UniqueVNI = true;
   VNInfo *TheVNI = nullptr;
 
   bool FoundUndef = false;
 
   // Using Seen as a visited set, perform a BFS for all reaching defs.
   for (unsigned i = 0; i != WorkList.size(); ++i) {
     MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
 
 #ifndef NDEBUG
-    if (!AllowUndef && MBB->pred_empty()) {
+    if (Undefs.size() > 0 && MBB->pred_empty()) {
       MBB->getParent()->verify();
       errs() << "Use of " << PrintReg(PhysReg)
              << " does not have a corresponding definition on every path:\n";
       const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
       if (MI != nullptr)
         errs() << Use << " " << *MI;
       llvm_unreachable("Use not jointly dominated by defs.");
     }
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
          continue;
        }
 
        SlotIndex Start, End;
        std::tie(Start, End) = Indexes->getMBBRange(Pred);
 
        // First time we see Pred.  Try to determine the live-out value, but set
        // it as null if Pred is live-through with an unknown value.
-       auto EP = LR.extendInBlock(Start, End);
+       auto EP = LR.extendInBlock(Undefs, Start, End);
        VNInfo *VNI = EP.first;
        FoundUndef |= EP.second;
        setLiveOutValue(Pred, VNI);
        if (VNI) {
          if (TheVNI && TheVNI != VNI)
            UniqueVNI = false;
          TheVNI = VNI;
        }
        if (VNI || EP.second)
          continue;
 
        // No, we need a live-in value for Pred as well
        if (Pred != &UseMBB)
          WorkList.push_back(Pred->getNumber());
        else
           // Loopback to UseMBB, so value is really live through.
          Use = SlotIndex();
     }
   }
 
   LiveIn.clear();
   FoundUndef |= (TheVNI == nullptr);
-  if (AllowUndef && FoundUndef)
+  if (Undefs.size() > 0 && FoundUndef)
     UniqueVNI = false;
 
   // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
   // neither require it. Skip the sorting overhead for small updates.
   if (WorkList.size() > 4)
     array_pod_sort(WorkList.begin(), WorkList.end());
 
   // If a unique reaching def was found, blit in the live ranges immediately.
#endif
   BitVector &DefOnEntry = EF->second.first;
   BitVector &UndefOnEntry = EF->second.second;
 
   // Multiple values were found, so transfer the work list to the LiveIn array
   // where UpdateSSA will use it as a work list.
   LiveIn.reserve(WorkList.size());
   for (unsigned BN : WorkList) {
     MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
-    if (AllowUndef && !isDefOnEntry(LR, *MBB, DefOnEntry, UndefOnEntry))
+    if (Undefs.size() > 0 && !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
       continue;
     addLiveInBlock(LR, DomTree->getNode(MBB));
     if (MBB == &UseMBB)
       LiveIn.back().Kill = Use;
   }
 
   return false;
 }

lib/CodeGen/RegisterCoalescer.cpp

for (MachineRegisterInfo::reg_instr_iterator
 
     DEBUG({
         dbgs() << "\t\tupdated: ";
         if (!UseMI->isDebugValue())
           dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";
         dbgs() << *UseMI;
       });
   }
-
-  if (DstInt && DstInt->hasSubRanges())
-    DstInt->recalculateSubRangeUndefs();
 }
 
 bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
   // Always join simple intervals that are defined by a single copy from a
   // reserved register. This doesn't increase register pressure, so it is
   // always beneficial.
   if (!MRI->isReserved(CP.getDstReg())) {
     DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
if (!LHS.hasSubRanges()) {
       // Transform LHS lanemasks to new register class if necessary.
       for (LiveInterval::SubRange &R : LHS.subranges()) {
         LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
         R.LaneMask = Mask;
       }
     }
     // The merging process may cause the undef information to become invalid
     // and fail verification. Clear it here, it will be recalculated later.
-    LHS.clearSubRangeUndefs();
     DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg())
                  << ' ' << LHS << '\n');
 
     // Determine lanemasks of RHS in the coalesced register and merge subranges.
     unsigned SrcIdx = CP.getSrcIdx();
     if (!RHS.hasSubRanges()) {
       LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
                                      : TRI->getSubRegIndexLaneMask(SrcIdx);

lib/CodeGen/RenameIndependentSubregs.cpp

struct SubRangeInfo {
     LiveInterval::SubRange *SR;
     unsigned Index;
 
     SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
                  unsigned Index)
       : ConEQ(LIS), SR(&SR), Index(Index) {}
   };
 
-  struct UndefInfo {
-    UndefInfo() : Reg(0), SubIdx(0), At() {}
-    UndefInfo(unsigned R, unsigned S, SlotIndex P)
-      : Reg(R), SubIdx(S), At(P) {}
-    unsigned Reg, SubIdx;
-    SlotIndex At;
-  };
-
   /// Split unrelated subregister components and rename them to new vregs.
   bool renameComponents(LiveInterval &LI) const;
 
   /// \brief Build a vector of SubRange infos and a union find set of
   /// equivalence classes.
   /// Returns true if more than 1 equivalence class was found.
   bool findComponents(IntEqClasses &Classes,
                       SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
                       LiveInterval &LI) const;
 
   /// \brief Distribute the LiveInterval segments into the new LiveIntervals
   /// belonging to their class.
   void distribute(const IntEqClasses &Classes,
                   const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                  const SmallVectorImpl<LiveInterval*> &Intervals,
-                  const SmallVectorImpl<UndefInfo> &UndefInfos) const;
+                  const SmallVectorImpl<LiveInterval*> &Intervals) const;
 
   /// \brief Constructs main liverange and add missing undef+dead flags.
   void computeMainRangesFixFlags(const IntEqClasses &Classes,
       const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
       const SmallVectorImpl<LiveInterval*> &Intervals) const;
 
   /// Rewrite Machine Operands to use the new vreg belonging to their class.
   void rewriteOperands(const IntEqClasses &Classes,
                        const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                       const SmallVectorImpl<LiveInterval*> &Intervals,
-                       SmallVectorImpl<UndefInfo> &UndefInfos) const;
+                       const SmallVectorImpl<LiveInterval*> &Intervals) const;
 
 
   LiveIntervals *LIS;
   MachineRegisterInfo *MRI;
   const TargetInstrInfo *TII;
 };
 
 } // end anonymous namespace
for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
        ++I) {
     unsigned NewVReg = MRI->createVirtualRegister(RegClass);
     LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
     Intervals.push_back(&NewLI);
     DEBUG(dbgs() << ' ' << PrintReg(NewVReg));
   }
   DEBUG(dbgs() << '\n');
 
-  SmallVector<UndefInfo,8> UndefInfos;
-  rewriteOperands(Classes, SubRangeInfos, Intervals, UndefInfos);
-  distribute(Classes, SubRangeInfos, Intervals, UndefInfos);
+  rewriteOperands(Classes, SubRangeInfos, Intervals);
+  distribute(Classes, SubRangeInfos, Intervals);
   computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
   return true;
 }
 
 bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
     SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos,
     LiveInterval &LI) const {
   // First step: Create connected components for the VNInfos inside the
bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
   // Early exit if we ended up with a single equivalence class.
   Classes.compress();
   unsigned NumClasses = Classes.getNumClasses();
   return NumClasses > 1;
 }
 
 void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals,
-    SmallVectorImpl<UndefInfo> &UndefInfos) const {
+    const SmallVectorImpl<LiveInterval*> &Intervals) const {
   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
   unsigned Reg = Intervals[0]->reg;;
   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
        E = MRI->reg_nodbg_end(); I != E; ) {
     MachineOperand &MO = *I++;
     if (!MO.isDef() && !MO.readsReg())
       continue;
 
for (const SubRangeInfo &SRInfo : SubRangeInfos) {
       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
       // Global ID
       ID = Classes[LocalID + SRInfo.Index];
       break;
     }
 
     unsigned VReg = Intervals[ID]->reg;
     MO.setReg(VReg);
-    if (SubRegIdx && MO.isUndef())
-      UndefInfos.push_back(UndefInfo(VReg, SubRegIdx, Pos));
   }
   // TODO: We could attempt to recompute new register classes while visiting
   // the operands: Some of the split register may be fine with less constraint
   // classes than the original vreg.
 }
 
 void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals,
-    const SmallVectorImpl<UndefInfo> &UndefInfos) const {
+    const SmallVectorImpl<LiveInterval*> &Intervals) const {
   unsigned NumClasses = Classes.getNumClasses();
   SmallVector<unsigned, 8> VNIMapping;
   SmallVector<LiveInterval::SubRange*, 8> SubRanges;
   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
   for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     LiveInterval::SubRange &SR = *SRInfo.SR;
     unsigned NumValNos = SR.valnos.size();
     VNIMapping.clear();
     VNIMapping.reserve(NumValNos);
     SubRanges.clear();
     SubRanges.resize(NumClasses-1, nullptr);
     for (unsigned I = 0; I < NumValNos; ++I) {
       const VNInfo &VNI = *SR.valnos[I];
       unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
       unsigned ID = Classes[LocalID + SRInfo.Index];
       VNIMapping.push_back(ID);
       if (ID > 0 && SubRanges[ID-1] == nullptr)
         SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
     }
     DistributeRange(SR, SubRanges.data(), VNIMapping);
   }
-
-  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
-  for (const UndefInfo &U : UndefInfos) {
-    LiveInterval &LI = LIS->getInterval(U.Reg);
-    LaneBitmask LM = TRI.getSubRegIndexLaneMask(U.SubIdx);
-    for (LiveInterval::SubRange &SR : LI.subranges())
-      if ((SR.LaneMask & LM) == 0)
-        SR.undefs.push_back(U.At);
-  }
 }
 
 static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     if (SR.liveAt(Pos))
       return true;
   }
   return false;
for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
     if (I == 0)
       LI.clear();
     LIS->constructMainRangeFromSubranges(LI);
     // A def of a subregister may be a use of other register lanes. Replacing
     // such a def with a def of a different register will eliminate the use,
     // and may cause the recorded live range to be larger than the actual
     // liveness in the program IR.
     LIS->shrinkToUses(&LI);
-    LI.recalculateSubRangeUndefs();
   }
 }
 
 bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
   // Skip renaming if liveness of subregister is not tracked.
   if (!MF.getSubtarget().enableSubRegLiveness())
     return false;
 

lib/CodeGen/SplitKit.cpp

do {
       // so the live range is accurate. Add live-in blocks in [Start;End) to the
       // LiveInBlocks.
       MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
       SlotIndex BlockStart, BlockEnd;
       std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
 
       // The first block may be live-in, or it may have its own def.
       if (Start != BlockStart) {
-        auto EP = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
-        VNInfo *VNI = EP.first;
+        VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
         assert(VNI && "Missing def for complex mapped value");
         DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
         // MBB has its own def. Is it also live-out?
         if (BlockEnd <= End)
           LRC.setLiveOutValue(&*MBB, VNI);
 
         // Skip to the next block for live-in.
         ++MBB;
         BlockStart = BlockEnd;
       }
 
       // Handle the live-in blocks covered by [Start;End).
       assert(Start <= BlockStart && "Expected live-in block");
       while (BlockStart < End) {
         DEBUG(dbgs() << ">BB#" << MBB->getNumber());
         BlockEnd = LIS.getMBBEndIdx(&*MBB);
         if (BlockStart == ParentVNI->def) {
           // This block has the def of a parent PHI, so it isn't live-in.
           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
-          auto EP = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
-          VNInfo *VNI = EP.first;
+          VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
           assert(VNI && "Missing def for complex mapped parent PHI");
           if (End >= BlockEnd)
             LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
         } else {
           // This block needs a live-in value.  The last block covered may not
           // be live-out.
           if (End < BlockEnd)
             LRC.addLiveInBlock(LI, MDT[&*MBB], End);
auto RemoveDeadSegment = [] (SlotIndex Def, LiveRange &LR) -> bool {
     if (Seg->end != Def.getDeadSlot())
       return false;
     // This is a dead PHI. Remove it.
     LR.removeSegment(*Seg, true);
     return true;
   };
 
   auto ExtendPHIRange = [this] (MachineBasicBlock &B, LiveRangeCalc &LRC,
-                                LiveRange &LR, bool AllowUndef) -> void {
+                                LiveRange &LR,
+                                ArrayRef<SlotIndex> Undefs) -> void {
     for (MachineBasicBlock *P : B.predecessors()) {
       SlotIndex End = LIS.getMBBEndIdx(P);
       SlotIndex LastUse = End.getPrevSlot();
       // The predecessor may not have a live-out value. That is OK, like an
       // undef PHI operand.
       if (Edit->getParent().liveAt(LastUse))
-        LRC.extend(LR, End, 0, AllowUndef);
+        LRC.extend(LR, End, 0, Undefs);
     }
   };
 
   // Visit each PHI def slot in the parent live interval. If the def is dead,
   // remove it. Otherwise, extend the live interval to reach the end indexes
   // of all predecessor blocks.
 
   LiveInterval &ParentLI = Edit->getParent();
+  SmallVector<SlotIndex, 4> Undefs;
   for (const VNInfo *V : ParentLI.valnos) {
     if (V->isUnused() || !V->isPHIDef())
       continue;
 
     unsigned RegIdx = RegAssign.lookup(V->def);
     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
     LiveRangeCalc &LRC = getLRCalc(RegIdx);
     MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
     if (!RemoveDeadSegment(V->def, LI))
-      ExtendPHIRange(B, LRC, LI, false);
+      ExtendPHIRange(B, LRC, LI, Undefs);
   }
 
   LiveRangeCalc SubLRC;
 
   for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
     for (const VNInfo *V : PS.valnos) {
       if (V->isUnused() || !V->isPHIDef())
         continue;
       unsigned RegIdx = RegAssign.lookup(V->def);
       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
       LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI);
       if (RemoveDeadSegment(V->def, S))
         continue;
 
       MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
       SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
                    &LIS.getVNInfoAllocator());
-      ExtendPHIRange(B, SubLRC, S, true);
+      Undefs.clear();
+      SubLRC.computeSubRangeUndefs(Undefs, ParentLI, PS.LaneMask);
+      ExtendPHIRange(B, SubLRC, S, Undefs);
     }
   }
 }
 
 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
   struct ExtPoint {
     ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
     SlotIndex Idx = LIS.getInstructionIndex(*MI);
     if (MO.isDef() || MO.isUndef())
       Idx = Idx.getRegSlot(MO.isEarlyClobber());
 
     // Rewrite to the mapped register at Idx.
     unsigned RegIdx = RegAssign.lookup(Idx);
     LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
     MO.setReg(LI.reg);
-    if (LI.hasSubRanges()) {
-      // If this is a read-undef def of a subregister, add undefs to the
-      // undefined subranges.
-      if (MO.getSubReg() && MO.isUndef()) {
-        LaneBitmask LM = getMaskForOp(MO);
-        for (LiveInterval::SubRange &S : LI.subranges())
-          if (!(S.LaneMask & LM))
-            S.undefs.push_back(Idx);
-      }
-    }
     DEBUG(dbgs() << "  rewr BB#" << MI->getParent()->getNumber() << '\t'
                  << Idx << ':' << RegIdx << '\t' << *MI);
 
     // Extend liveness to Idx if the instruction reads reg.
     if (!ExtendRanges || MO.isUndef())
       continue;
 
     // Skip instructions that don't read Reg.
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
     if (LI.hasSubRanges()) {
       // We have to delay extending subranges until we have seen all operands
       // defining the register. This is because a <def,read-undef> operand
       // will create an "undef" point, and we cannot extend any subranges
       // until all of them have been accounted for.
       ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
     } else {
       LiveRangeCalc &LRC = getLRCalc(RegIdx);
-      LRC.extend(LI, Next);
+      LRC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
     }
   }
 
   for (ExtPoint &EP : ExtPoints) {
     LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
     assert(LI.hasSubRanges());
 
     LiveRangeCalc SubLRC;
for (LiveInterval::SubRange &S : LI.subranges()) {
       // for a partially defined original register. For example:
       //   %vreg827:subreg_hireg<def,read-undef> = ...
       //   ...
       //   %vreg828<def> = COPY %vreg827
       if (S.empty())
         continue;
       SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
                    &LIS.getVNInfoAllocator());
-      SubLRC.extend(S, EP.Next, 0, true);
+      SmallVector<SlotIndex, 4> Undefs;
+      SubLRC.computeSubRangeUndefs(Undefs, LI, S.LaneMask);
+      SubLRC.extend(S, EP.Next, 0, Undefs);
     }
   }
 
   for (unsigned R : *Edit) {
     LiveInterval &LI = LIS.getInterval(R);
     if (!LI.hasSubRanges())
       continue;
     LI.clear();