Index: include/llvm/CodeGen/LiveInterval.h
===================================================================
--- include/llvm/CodeGen/LiveInterval.h
+++ include/llvm/CodeGen/LiveInterval.h
@@ -192,9 +192,11 @@
 
     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.
@@ -276,6 +278,7 @@
     void clear() {
       valnos.clear();
       segments.clear();
+      undefs.clear();
     }
 
     size_t size() const {
@@ -316,6 +319,10 @@
     /// add liveness for a dead def.
     VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator);
 
+    /// Create a def of value @p VNI. Return @p VNI. If there already exists
+    /// a definition at VNI->def, the value defined there must be @p VNI.
+    VNInfo *createDeadDef(VNInfo *VNI);
+
     /// Create a copy of the given value. The new value will be identical except
     /// for the Value number.
     VNInfo *createValueCopy(const VNInfo *orig,
@@ -451,10 +458,20 @@
     /// may have grown since it was inserted).
     iterator addSegment(Segment S);
 
+    /// 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, extend it to be live up to @p Use, and return the value. If
-    /// there is no segment before @p Use, return nullptr.
-    VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use);
+    /// @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);
 
     /// join - Join two live ranges (this, and other) together.  This applies
     /// mappings to the value numbers in the LHS/RHS ranges as specified.  If
@@ -555,12 +572,23 @@
       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(),
+                [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;
 
@@ -581,7 +609,7 @@
     friend class LiveRangeUpdater;
     void addSegmentToSet(Segment S);
     void markValNoForDeletion(VNInfo *V);
-
+    void pruneUndefs();
   };
 
   inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
@@ -729,6 +757,17 @@
       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();
Index: include/llvm/CodeGen/LiveIntervalAnalysis.h
===================================================================
--- include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -163,15 +163,20 @@
     /// LiveInterval::removeEmptySubranges() afterwards.
     void shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg);
 
-    /// extendToIndices - Extend the live range of LI to reach all points in
-    /// Indices. The points in the Indices array must be jointly dominated by
-    /// existing defs in LI. PHI-defs are added as needed to maintain SSA form.
+    /// Extend the live range of LI to reach all points in @p Indices. The
+    /// points in the @p Indices array must be jointly dominated by existing
+    /// defs in @p LR, unless @p AllowUndef is set. If @p AllowUndef is set,
+    /// an attempt to extend @p LR to an index where @p LR is undefined has
+    /// 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 Indices is the end index of a basic block, LI will be
-    /// extended to be live out of the basic block.
+    /// 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);
+    void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices,
+                         bool AllowUndef = false);
 
 
     /// If @p LR has a live value at @p Kill, prune its live range by removing
Index: lib/CodeGen/LiveInterval.cpp
===================================================================
--- lib/CodeGen/LiveInterval.cpp
+++ lib/CodeGen/LiveInterval.cpp
@@ -59,18 +59,23 @@
   typedef LiveRange::Segment Segment;
   typedef IteratorT iterator;
 
-  VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator) {
+  // The value to be defined at Def may be explicitly specified by ForVNI.
+  // In such case, it will be used instead of allocating a new one.
+  VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator *VNInfoAllocator,
+                        VNInfo *ForVNI) {
     assert(!Def.isDead() && "Cannot define a value at the dead slot");
-
+    assert((!ForVNI || ForVNI->def == Def) &&
+           "If ForVNI is specified, it must match Def");
     iterator I = impl().find(Def);
     if (I == segments().end()) {
-      VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator);
+      VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);
       impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
       return VNI;
     }
 
     Segment *S = segmentAt(I);
     if (SlotIndex::isSameInstr(Def, S->start)) {
+      assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch");
       assert(S->valno->def == S->start && "Inconsistent existing value def");
 
       // It is possible to have both normal and early-clobber defs of the same
@@ -84,24 +89,27 @@
       return S->valno;
     }
     assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
-    VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator);
+    VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator);
     segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
     return VNI;
   }
 
-  VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
+  std::pair<VNInfo*,bool> extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
     if (segments().empty())
-      return nullptr;
-    iterator I =
-        impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));
+      return std::make_pair(nullptr, false);
+    SlotIndex BeforeUse = Use.getPrevSlot();
+    iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));
     if (I == segments().begin())
-      return nullptr;
+      return std::make_pair(nullptr, LR->isUndefIn(StartIdx, BeforeUse));
     --I;
     if (I->end <= StartIdx)
-      return nullptr;
-    if (I->end < Use)
+      return std::make_pair(nullptr, LR->isUndefIn(StartIdx, BeforeUse));
+    if (I->end < Use) {
+      if (LR->isUndefIn(I->end, BeforeUse))
+        return std::make_pair(nullptr, true);
       extendSegmentEndTo(I, Use);
-    return I->valno;
+    }
+    return std::make_pair(I->valno, false);
   }
 
   /// This method is used when we want to extend the segment specified
@@ -320,13 +328,20 @@
   return I;
 }
 
-VNInfo *LiveRange::createDeadDef(SlotIndex Def,
-                                  VNInfo::Allocator &VNInfoAllocator) {
+VNInfo *LiveRange::createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc) {
+  // Use the segment set, if it is available.
+  if (segmentSet != nullptr)
+    return CalcLiveRangeUtilSet(this).createDeadDef(Def, &VNIAlloc, nullptr);
+  // Otherwise use the segment vector.
+  return CalcLiveRangeUtilVector(this).createDeadDef(Def, &VNIAlloc, nullptr);
+}
+
+VNInfo *LiveRange::createDeadDef(VNInfo *VNI) {
   // Use the segment set, if it is available.
   if (segmentSet != nullptr)
-    return CalcLiveRangeUtilSet(this).createDeadDef(Def, VNInfoAllocator);
+    return CalcLiveRangeUtilSet(this).createDeadDef(VNI->def, nullptr, VNI);
   // Otherwise use the segment vector.
-  return CalcLiveRangeUtilVector(this).createDeadDef(Def, VNInfoAllocator);
+  return CalcLiveRangeUtilVector(this).createDeadDef(VNI->def, nullptr, VNI);
 }
 
 // overlaps - Return true if the intersection of the two live ranges is
@@ -498,19 +513,23 @@
     return end();
   }
   // Otherwise use the segment vector.
-  return CalcLiveRangeUtilVector(this).addSegment(S);
+  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.
-VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
+std::pair<VNInfo*,bool> LiveRange::extendInBlock(SlotIndex StartIdx,
+                                                 SlotIndex Kill) {
   // Use the segment set, if it is available.
   if (segmentSet != nullptr)
     return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);
@@ -748,6 +767,7 @@
       "segment set can be used only initially before switching to the array");
   segments.append(segmentSet->begin(), segmentSet->end());
   segmentSet = nullptr;
+  pruneUndefs();
   verify();
 }
 
@@ -785,6 +805,12 @@
   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.
@@ -817,6 +843,27 @@
   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)
@@ -862,6 +909,15 @@
       }
     }
   }
+
+  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 {
@@ -906,6 +962,8 @@
         assert(I->valno != std::next(I)->valno);
     }
   }
+  for (SlotIndex U : undefs)
+    assert(getSegmentContaining(U) == nullptr);
 }
 
 void LiveInterval::verify(const MachineRegisterInfo *MRI) const {
@@ -1118,6 +1176,7 @@
   // Nothing to merge?
   if (Spills.empty()) {
     LR->segments.erase(WriteI, ReadI);
+    LR->pruneUndefs();
     LR->verify();
     return;
   }
@@ -1136,6 +1195,7 @@
   }
   ReadI = WriteI + Spills.size();
   mergeSpills();
+  LR->pruneUndefs();
   LR->verify();
 }
 
Index: lib/CodeGen/LiveIntervalAnalysis.cpp
===================================================================
--- lib/CodeGen/LiveIntervalAnalysis.cpp
+++ lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -352,7 +352,7 @@
 
 static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
                                  ShrinkToUsesWorkList &WorkList,
-                                 const LiveRange &OldRange) {
+                                 const LiveRange &OldRange, bool AllowUndef) {
   // Keep track of the PHIs that are in use.
   SmallPtrSet<VNInfo*, 8> UsedPHIs;
   // Blocks that have already been added to WorkList as live-out.
@@ -367,7 +367,7 @@
     SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
 
     // Extend the live range for VNI to be live at Idx.
-    if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
+    if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx).first) {
       assert(ExtVNI == VNI && "Unexpected existing value number");
       (void)ExtVNI;
       // Is this a PHIDef we haven't seen before?
@@ -395,6 +395,8 @@
       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));
@@ -451,7 +453,7 @@
   // 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);
+  extendSegmentsToUses(NewLR, *Indexes, WorkList, *li, false);
 
   // Move the trimmed segments back.
   li->segments.swap(NewLR.segments);
@@ -504,8 +506,7 @@
   return MayHaveSplitComponents;
 }
 
-void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
-{
+void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
   DEBUG(dbgs() << "Shrink: " << SR << '\n');
   assert(TargetRegisterInfo::isVirtualRegister(Reg)
          && "Can only shrink virtual registers");
@@ -516,12 +517,14 @@
   SlotIndex LastIdx;
   for (MachineOperand &MO : MRI->reg_operands(Reg)) {
     MachineInstr *UseMI = MO.getParent();
-    if (UseMI->isDebugValue())
+    if (UseMI->isDebugValue() || !MO.readsReg())
       continue;
     // Maybe the operand is for a subregister we don't care about.
     unsigned SubReg = MO.getSubReg();
     if (SubReg != 0) {
       LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
+      if (MO.isDef())
+        LaneMask = ~LaneMask & MRI->getMaxLaneMaskForVReg(Reg);
       if ((LaneMask & SR.LaneMask) == 0)
         continue;
     }
@@ -549,7 +552,7 @@
   // 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);
+  extendSegmentsToUses(NewLR, *Indexes, WorkList, SR, true);
 
   // Move the trimmed ranges back.
   SR.segments.swap(NewLR.segments);
@@ -574,11 +577,12 @@
 }
 
 void LiveIntervals::extendToIndices(LiveRange &LR,
-                                    ArrayRef<SlotIndex> Indices) {
+                                    ArrayRef<SlotIndex> Indices,
+                                    bool AllowUndef) {
   assert(LRCalc && "LRCalc not initialized.");
   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
   for (unsigned i = 0, e = Indices.size(); i != e; ++i)
-    LRCalc->extend(LR, Indices[i]);
+    LRCalc->extend(LR, Indices[i], /*PhysReg=*/0, AllowUndef);
 }
 
 void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
@@ -953,8 +957,10 @@
       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
         LiveInterval &LI = LIS.getInterval(Reg);
         if (LI.hasSubRanges()) {
+          LI.clearSubRangeUndefs();
           unsigned SubReg = MO.getSubReg();
-          LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
+          LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
+                                        : MRI.getMaxLaneMaskForVReg(Reg);
           for (LiveInterval::SubRange &S : LI.subranges()) {
             if ((S.LaneMask & LaneMask) == 0)
               continue;
@@ -973,6 +979,15 @@
     }
     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:
@@ -1538,15 +1553,19 @@
 }
 
 void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
+  // LI may not have the main range computed yet, but its subranges may
+  // be present.
   VNInfo *VNI = LI.getVNInfoAt(Pos);
-  if (VNI == nullptr)
-    return;
-  LI.removeValNo(VNI);
+  if (VNI != nullptr) {
+    assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
+    LI.removeValNo(VNI);
+  }
 
-  // Also remove the value in subranges.
+  // Also remove the value defined in subranges.
   for (LiveInterval::SubRange &S : LI.subranges()) {
     if (VNInfo *SVNI = S.getVNInfoAt(Pos))
-      S.removeValNo(SVNI);
+      if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
+        S.removeValNo(SVNI);
   }
   LI.removeEmptySubRanges();
 }
Index: lib/CodeGen/LiveRangeCalc.h
===================================================================
--- lib/CodeGen/LiveRangeCalc.h
+++ lib/CodeGen/LiveRangeCalc.h
@@ -24,6 +24,7 @@
 
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/LiveInterval.h"
 
 namespace llvm {
@@ -53,6 +54,13 @@
   /// when switching live ranges.
   BitVector Seen;
 
+  /// Bit vectors of blocks such that there is a path from at least one of
+  /// the defs in the live range to the entry of the block, and conversely,
+  /// of blocks for which there is no such path (i.e. no definition reaches
+  /// the entry of the block).
+  BitVector DefOnEntry;
+  BitVector UndefOnEntry;
+
   /// Map each basic block where a live range is live out to the live-out value
   /// and its defining block.
   ///
@@ -101,18 +109,31 @@
   /// used to add entries directly.
   SmallVector<LiveInBlock, 16> LiveIn;
 
-  /// Assuming that @p LR is live-in to @p UseMBB, find the set of defs that can
-  /// reach it.
+  /// 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);
+
+  /// Find the set of defs that can reach @p Kill. @p Kill must belong to
+  /// @p UseMBB.
   ///
-  /// If only one def can reach @p UseMBB, all paths from the def to @p UseMBB
-  /// are added to @p LR, and the function returns true.
+  /// 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);
+                        SlotIndex Kill, unsigned PhysReg, bool AllowUndef);
 
   /// 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.
@@ -127,9 +148,22 @@
 
   /// Extend the live range of @p LR to reach all uses of Reg.
   ///
-  /// All uses must be jointly dominated by existing liveness.  PHI-defs are
-  /// inserted as needed to preserve SSA form.
-  void extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask);
+  /// All uses must be jointly dominated by existing liveness, unless
+  /// @p AllowUndef is true..  PHI-defs are inserted as needed to preserve
+  /// SSA form. The set @p LiveAt optionally contains indexes where the
+  /// register is known to be live. The motivation for this are read-undef
+  /// definitions of Reg's subregisters. Consider the following:
+  ///   Reg:sub0<def,read-undef> = ...
+  ///   ...
+  ///   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);
 
   /// Reset Map and Seen fields.
   void resetLiveOutMap();
@@ -169,7 +203,8 @@
   /// 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);
+  void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg = 0,
+              bool AllowUndef = false);
 
   /// createDeadDefs - Create a dead def in LI for every def operand of Reg.
   /// Each instruction defining Reg gets a new VNInfo with a corresponding
Index: lib/CodeGen/LiveRangeCalc.cpp
===================================================================
--- lib/CodeGen/LiveRangeCalc.cpp
+++ lib/CodeGen/LiveRangeCalc.cpp
@@ -12,6 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "LiveRangeCalc.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
@@ -23,6 +24,10 @@
   unsigned NumBlocks = MF->getNumBlockIDs();
   Seen.clear();
   Seen.resize(NumBlocks);
+  DefOnEntry.clear();
+  DefOnEntry.resize(NumBlocks);
+  UndefOnEntry.clear();
+  UndefOnEntry.resize(NumBlocks);
   Map.resize(NumBlocks);
 }
 
@@ -53,6 +58,19 @@
 void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
   assert(MRI && Indexes && "call reset() first");
 
+  auto getCommonRange = [&LI,this] (LiveInterval::SubRange &S,
+                                    LaneBitmask Mask) {
+    LaneBitmask CM = S.LaneMask & Mask;
+    // A Mask for subregs covered by the subrange but not the current def.
+    if (LaneBitmask RM = S.LaneMask & ~Mask) {
+      // Split current subrange into Common and LRest ranges.
+      S.LaneMask = RM;
+      return LI.createSubRangeFrom(*Alloc, CM, S);
+    }
+    assert(CM == S.LaneMask);
+    return &S;
+  };
+
   // Step 1: Create minimal live segments for every definition of Reg.
   // Visit all def operands. If the same instruction has multiple defs of Reg,
   // createDeadDef() will deduplicate.
@@ -62,11 +80,15 @@
     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 Mask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
-                                     : MRI->getMaxLaneMaskForVReg(Reg);
-
+      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()) {
@@ -74,22 +96,13 @@
         LI.createSubRangeFrom(*Alloc, ClassMask, LI);
       }
 
+      LaneBitmask Mask = SubMask;
       for (LiveInterval::SubRange &S : LI.subranges()) {
         // A Mask for subregs common to the existing subrange and current def.
         LaneBitmask Common = S.LaneMask & Mask;
         if (Common == 0)
           continue;
-        // A Mask for subregs covered by the subrange but not the current def.
-        LaneBitmask LRest = S.LaneMask & ~Mask;
-        LiveInterval::SubRange *CommonRange;
-        if (LRest != 0) {
-          // Split current subrange into Common and LRest ranges.
-          S.LaneMask = LRest;
-          CommonRange = LI.createSubRangeFrom(*Alloc, Common, S);
-        } else {
-          assert(Common == S.LaneMask);
-          CommonRange = &S;
-        }
+        LiveInterval::SubRange *CommonRange = getCommonRange(S, Mask);
         if (MO.isDef())
           createDeadDef(*Indexes, *Alloc, *CommonRange, MO);
         Mask &= ~Common;
@@ -100,6 +113,21 @@
         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
@@ -117,7 +145,7 @@
   if (LI.hasSubRanges()) {
     for (LiveInterval::SubRange &S : LI.subranges()) {
       resetLiveOutMap();
-      extendToUses(S, Reg, S.LaneMask);
+      extendToUses(S, Reg, S.LaneMask, true);
     }
     LI.clear();
     constructMainRangeFromSubranges(LI);
@@ -139,9 +167,8 @@
         MainRange.createDeadDef(VNI->def, *Alloc);
     }
   }
-
   resetLiveOutMap();
-  extendToUses(MainRange, LI.reg);
+  extendToUses(MainRange, LI.reg, ~0U, true);
 }
 
 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
@@ -154,8 +181,8 @@
 }
 
 
-void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg,
-                                 LaneBitmask Mask) {
+void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
+                                 bool AllowUndef) {
   // Visit all operands that read Reg. This may include partial defs.
   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
@@ -163,20 +190,16 @@
     // by LiveIntervalAnalysis::addKillFlags().
     if (MO.isUse())
       MO.setIsKill(false);
-    else {
-      // We only care about uses, but on the main range (mask ~0u) this includes
-      // the "virtual" reads happening for subregister defs.
-      if (Mask != ~0u)
-        continue;
-    }
-
     if (!MO.readsReg())
       continue;
+
     unsigned SubReg = MO.getSubReg();
     if (SubReg != 0) {
-      LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(SubReg);
+      LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
+      if (MO.isDef())
+        SLM = MRI->getMaxLaneMaskForVReg(Reg) & ~SLM;
       // Ignore uses not covering the current subrange.
-      if ((SubRegMask & Mask) == 0)
+      if ((SLM & Mask) == 0)
         continue;
     }
 
@@ -205,7 +228,7 @@
 
     // 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);
+    extend(LR, UseIdx, Reg, AllowUndef);
   }
 }
 
@@ -236,7 +259,8 @@
 }
 
 
-void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg) {
+void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
+                           bool AllowUndef) {
   assert(Use.isValid() && "Invalid SlotIndex");
   assert(Indexes && "Missing SlotIndexes");
   assert(DomTree && "Missing dominator tree");
@@ -245,14 +269,15 @@
   assert(UseMBB && "No MBB at Use");
 
   // Is there a def in the same MBB we can extend?
-  if (LR.extendInBlock(Indexes->getMBBStartIdx(UseMBB), Use))
+  auto EP = LR.extendInBlock(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))
+  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, AllowUndef))
     return;
 
   // When there were multiple different values, we may need new PHIs.
@@ -271,8 +296,69 @@
 }
 
 
+bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, MachineBasicBlock &MBB) {
+  unsigned BN = MBB.getNumber();
+  if (DefOnEntry[BN])
+    return true;
+  if (UndefOnEntry[BN])
+    return false;
+
+  auto MarkDefined = [this,BN] (MachineBasicBlock &B) -> bool {
+    for (MachineBasicBlock *S : B.successors())
+      DefOnEntry[S->getNumber()] = true;
+    DefOnEntry[BN] = true;
+    return true;
+  };
+
+  SetVector<unsigned> WorkList;
+  // Checking if the entry of MBB is reached by some def: add all predecessors
+  // that are potentially defined-on-exit to the work list.
+  for (MachineBasicBlock *P : MBB.predecessors())
+    WorkList.insert(P->getNumber());
+
+  for (unsigned i = 0; i != WorkList.size(); ++i) {
+    // Determine if the exit from the block is reached by some def.
+    unsigned N = WorkList[i];
+    MachineBasicBlock &B = *MF->getBlockNumbered(N);
+    if (Seen[N] && Map[&B].first != nullptr)
+      return MarkDefined(B);
+    SlotIndex Begin, End;
+    std::tie(Begin, End) = Indexes->getMBBRange(&B);
+    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))
+          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)) {
+      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) {
+                                     SlotIndex Use, unsigned PhysReg,
+                                     bool AllowUndef) {
   unsigned UseMBBNum = UseMBB.getNumber();
 
   // Block numbers where LR should be live-in.
@@ -282,12 +368,14 @@
   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 (MBB->pred_empty()) {
+    if (!AllowUndef && MBB->pred_empty()) {
       MBB->getParent()->verify();
       errs() << "Use of " << PrintReg(PhysReg)
              << " does not have a corresponding definition on every path:\n";
@@ -306,6 +394,7 @@
       llvm_unreachable("Invalid global physical register");
     }
 #endif
+    FoundUndef |= MBB->pred_empty();
 
     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
          PE = MBB->pred_end(); PI != PE; ++PI) {
@@ -326,18 +415,21 @@
 
        // 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.
-       VNInfo *VNI = LR.extendInBlock(Start, End);
+       auto EP = LR.extendInBlock(Start, End);
+       VNInfo *VNI = EP.first;
+       FoundUndef |= EP.second;
        setLiveOutValue(Pred, VNI);
        if (VNI) {
          if (TheVNI && TheVNI != VNI)
            UniqueVNI = false;
          TheVNI = VNI;
-         continue;
        }
+       if (VNI || EP.second)
+         continue;
 
        // No, we need a live-in value for Pred as well
        if (Pred != &UseMBB)
-          WorkList.push_back(Pred->getNumber());
+         WorkList.push_back(Pred->getNumber());
        else
           // Loopback to UseMBB, so value is really live through.
          Use = SlotIndex();
@@ -345,6 +437,9 @@
   }
 
   LiveIn.clear();
+  FoundUndef |= (TheVNI == nullptr);
+  if (AllowUndef && FoundUndef)
+    UniqueVNI = false;
 
   // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
   // neither require it. Skip the sorting overhead for small updates.
@@ -354,16 +449,15 @@
   // If a unique reaching def was found, blit in the live ranges immediately.
   if (UniqueVNI) {
     LiveRangeUpdater Updater(&LR);
-    for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(),
-         E = WorkList.end(); I != E; ++I) {
-       SlotIndex Start, End;
-       std::tie(Start, End) = Indexes->getMBBRange(*I);
-       // Trim the live range in UseMBB.
-       if (*I == UseMBBNum && Use.isValid())
-         End = Use;
-       else
-         Map[MF->getBlockNumbered(*I)] = LiveOutPair(TheVNI, nullptr);
-       Updater.add(Start, End, TheVNI);
+    for (unsigned BN : WorkList) {
+      SlotIndex Start, End;
+      std::tie(Start, End) = Indexes->getMBBRange(BN);
+      // Trim the live range in UseMBB.
+      if (BN == UseMBBNum && Use.isValid())
+        End = Use;
+      else
+        Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
+      Updater.add(Start, End, TheVNI);
     }
     return true;
   }
@@ -371,9 +465,10 @@
   // 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 (SmallVectorImpl<unsigned>::const_iterator
-       I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
-    MachineBasicBlock *MBB = MF->getBlockNumbered(*I);
+  for (unsigned BN : WorkList) {
+    MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
+    if (AllowUndef && !isDefOnEntry(LR, *MBB))
+      continue;
     addLiveInBlock(LR, DomTree->getNode(MBB));
     if (MBB == &UseMBB)
       LiveIn.back().Kill = Use;
@@ -458,10 +553,12 @@
         I.DomNode = nullptr;
 
         // Add liveness since updateFromLiveIns now skips this node.
-        if (I.Kill.isValid())
-          LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
-        else {
-          LR.addSegment(LiveInterval::Segment(Start, End, VNI));
+        if (I.Kill.isValid()) {
+          if (VNI)
+            LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
+        } else {
+          if (VNI)
+            LR.addSegment(LiveInterval::Segment(Start, End, VNI));
           LOP = LiveOutPair(VNI, Node);
         }
       } else if (IDomValue.first) {
Index: lib/CodeGen/LiveRangeEdit.cpp
===================================================================
--- lib/CodeGen/LiveRangeEdit.cpp
+++ lib/CodeGen/LiveRangeEdit.cpp
@@ -37,6 +37,13 @@
     VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
   }
   LiveInterval &LI = LIS.createEmptyInterval(VReg);
+  // Create empty subranges if the OldReg's interval has them. Do not create
+  // the main range here---it will be constructed later after the subranges
+  // have been finalized.
+  LiveInterval &OldLI = LIS.getInterval(OldReg);
+  VNInfo::Allocator &Alloc = LIS.getVNInfoAllocator();
+  for (LiveInterval::SubRange &S : OldLI.subranges())
+    LI.createSubRange(Alloc, S.LaneMask);
   return LI;
 }
 
@@ -66,6 +73,8 @@
     unsigned Original = VRM->getOriginal(getReg());
     LiveInterval &OrigLI = LIS.getInterval(Original);
     VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
+    if (!OrigVNI)
+      continue;
     MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);
     if (!DefMI)
       continue;
@@ -335,6 +344,7 @@
     // allocations of the func are done.
     if (isOrigDef && DeadRemats && TII.isTriviallyReMaterializable(*MI, AA)) {
       LiveInterval &NewLI = createEmptyIntervalFrom(Dest);
+      NewLI.removeEmptySubRanges();
       VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator());
       NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
       pop_back();
Index: lib/CodeGen/MachineVerifier.cpp
===================================================================
--- lib/CodeGen/MachineVerifier.cpp
+++ lib/CodeGen/MachineVerifier.cpp
@@ -1769,18 +1769,25 @@
     bool hasRead = false;
     bool hasSubRegDef = false;
     bool hasDeadDef = false;
+    LaneBitmask RLM = MRI->getMaxLaneMaskForVReg(Reg);
     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
       if (!MOI->isReg() || MOI->getReg() != Reg)
         continue;
-      if (LaneMask != 0 &&
-          (LaneMask & TRI->getSubRegIndexLaneMask(MOI->getSubReg())) == 0)
-        continue;
+      unsigned Sub = MOI->getSubReg();
+      LaneBitmask SLM = Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub) : RLM;
       if (MOI->isDef()) {
-        if (MOI->getSubReg() != 0)
+        if (Sub != 0) {
           hasSubRegDef = true;
+          // An operand vreg0:sub0<def> reads vreg0:sub1..n. Invert the lane
+          // mask for subregister defs. Read-undef defs will be handled by
+          // readsReg below.
+          SLM = ~SLM & RLM;
+        }
         if (MOI->isDead())
           hasDeadDef = true;
       }
+      if (LaneMask != 0 && !(LaneMask & SLM))
+        continue;
       if (MOI->readsReg())
         hasRead = true;
     }
Index: lib/CodeGen/RegAllocBase.cpp
===================================================================
--- lib/CodeGen/RegAllocBase.cpp
+++ lib/CodeGen/RegAllocBase.cpp
@@ -143,6 +143,7 @@
         continue;
       }
       DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
+      assert(!SplitVirtReg->empty() && "expecting non-empty interval");
       assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
              "expect split value in virtual register");
       enqueue(SplitVirtReg);
Index: lib/CodeGen/RegisterCoalescer.cpp
===================================================================
--- lib/CodeGen/RegisterCoalescer.cpp
+++ lib/CodeGen/RegisterCoalescer.cpp
@@ -1210,6 +1210,17 @@
     MO.setIsUndef(true);
     DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI);
   }
+
+  // A def of a subregister may be a use of the othe subregisters, so
+  // deleting a def of a subregister may also remove uses. Since CopyMI
+  // is still connected to the program list (but about to be erased),
+  // mark all defs of DstReg in it as <undef>, so that shrinkToUses would
+  // ignore them.
+  for (MachineOperand &MO : CopyMI->operands())
+    if (MO.isReg() && MO.isDef() && MO.getReg() == DstReg)
+      MO.setIsUndef(true);
+  LIS->shrinkToUses(&DstLI);
+
   return true;
 }
 
@@ -1319,6 +1330,9 @@
         dbgs() << *UseMI;
       });
   }
+
+  if (DstInt && DstInt->hasSubRanges())
+    DstInt->recalculateSubRangeUndefs();
 }
 
 bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
@@ -1889,12 +1903,22 @@
   /// no useful information and can be removed.
   void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
 
+  /// Pruning values in subranges can lead to removing segments in these
+  /// subranges started by IMPLICIT_DEFs. The corresponding segments in
+  /// the main range also need to be removed. This function will mark
+  /// the corresponding values in the main range as pruned, so that
+  /// eraseInstrs can do the final cleanup.
+  /// The parameter @p LI must be the interval whose main range is the
+  /// live range LR.
+  void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);
+
   /// Erase any machine instructions that have been coalesced away.
   /// Add erased instructions to ErasedInstrs.
   /// Add foreign virtual registers to ShrinkRegs if their live range ended at
   /// the erased instrs.
   void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
-                   SmallVectorImpl<unsigned> &ShrinkRegs);
+                   SmallVectorImpl<unsigned> &ShrinkRegs,
+                   LiveInterval *LI = nullptr);
 
   /// Remove liverange defs at places where implicit defs will be removed.
   void removeImplicitDefs();
@@ -1997,6 +2021,7 @@
   } else {
     DefMI = Indexes->getInstructionFromIndex(VNI->def);
     assert(DefMI != nullptr);
+
     if (SubRangeJoin) {
       // We don't care about the lanes when joining subregister ranges.
       V.WriteLanes = V.ValidLanes = 1;
@@ -2448,8 +2473,7 @@
   }
 }
 
-void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask)
-{
+void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
   // Look for values being erased.
   bool DidPrune = false;
   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
@@ -2486,6 +2510,29 @@
     LI.removeEmptySubRanges();
 }
 
+void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {
+  assert(&static_cast<LiveRange&>(LI) == &LR);
+
+  auto IsDefInSubRange = [&LI] (SlotIndex Def) -> bool {
+    for (LiveInterval::SubRange &SR : LI.subranges()) {
+      if (VNInfo *VNI = SR.Query(Def).valueOutOrDead())
+        if (VNI->def == Def)
+          return true;
+    }
+    return false;
+  };
+
+  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
+    if (Vals[i].Resolution != CR_Keep)
+      continue;
+    VNInfo *VNI = LR.getValNumInfo(i);
+    if (VNI->isUnused() || VNI->isPHIDef() || IsDefInSubRange(VNI->def))
+      continue;
+    Vals[i].Pruned = true;
+    ShrinkMainRange = true;
+  }
+}
+
 void JoinVals::removeImplicitDefs() {
   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
     Val &V = Vals[i];
@@ -2499,7 +2546,8 @@
 }
 
 void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
-                           SmallVectorImpl<unsigned> &ShrinkRegs) {
+                           SmallVectorImpl<unsigned> &ShrinkRegs,
+                           LiveInterval *LI) {
   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
     // Get the def location before markUnused() below invalidates it.
     SlotIndex Def = LR.getValNumInfo(i)->def;
@@ -2511,12 +2559,64 @@
       if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
         break;
       // Remove value number i from LR.
+      // For intervals with subranges, removing a segment from the main range
+      // may require extending the previous segment: for each definition of
+      // a subregister, there will be a corresponding def in the main range.
+      // That def may fall in the middle of a segment from another subrange.
+      // In such cases, removing this def from the main range must be
+      // complemented by extending the main range to account for the liveness
+      // of the other subrange.
       VNInfo *VNI = LR.getValNumInfo(i);
+      SlotIndex Def = VNI->def;
+      // The new end point of the main range segment to be extended.
+      SlotIndex NewEnd;
+      if (LI != nullptr) {
+        LiveRange::iterator I = LR.FindSegmentContaining(Def);
+        assert(I != LR.end());
+        // Do not extend beyond the end of the segment being removed.
+        // The segment may have been pruned in preparation for joining
+        // live ranges.
+        NewEnd = I->end;
+      }
+
       LR.removeValNo(VNI);
       // Note that this VNInfo is reused and still referenced in NewVNInfo,
       // make it appear like an unused value number.
       VNI->markUnused();
-      DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n');
+
+      if (LI != nullptr && LI->hasSubRanges()) {
+        assert(static_cast<LiveRange*>(LI) == &LR);
+        // Determine the end point based on the subrange information:
+        // minimum of (earliest def of next segment,
+        //             latest end point of containing segment)
+        SlotIndex ED, LE;
+        for (LiveInterval::SubRange &SR : LI->subranges()) {
+          LiveRange::iterator I = SR.find(Def);
+          if (I == SR.end())
+            continue;
+          if (I->start > Def)
+            ED = ED.isValid() ? std::min(ED, I->start) : I->start;
+          else
+            LE = LE.isValid() ? std::max(LE, I->end) : I->end;
+        }
+        if (LE.isValid())
+          NewEnd = std::min(NewEnd, LE);
+        if (ED.isValid())
+          NewEnd = std::min(NewEnd, ED);
+
+        // We only want to do the extension if there was a subrange that
+        // was live across Def.
+        if (LE.isValid()) {
+          LiveRange::iterator S = LR.find(Def);
+          if (S != LR.begin())
+            std::prev(S)->end = NewEnd;
+        }
+      }
+      DEBUG({
+        dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n';
+        if (LI != nullptr)
+          dbgs() << "\t\t  LHS = " << *LI << '\n';
+      });
       // FALL THROUGH.
     }
 
@@ -2679,6 +2779,9 @@
         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');
 
@@ -2697,6 +2800,10 @@
     }
     DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
 
+    // Pruning implicit defs from subranges may result in the main range
+    // having stale segments.
+    LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
+
     LHSVals.pruneSubRegValues(LHS, ShrinkMask);
     RHSVals.pruneSubRegValues(LHS, ShrinkMask);
   }
@@ -2712,7 +2819,7 @@
   // Erase COPY and IMPLICIT_DEF instructions. This may cause some external
   // registers to require trimming.
   SmallVector<unsigned, 8> ShrinkRegs;
-  LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
+  LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
   RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
   while (!ShrinkRegs.empty())
     shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
Index: lib/CodeGen/RenameIndependentSubregs.cpp
===================================================================
--- lib/CodeGen/RenameIndependentSubregs.cpp
+++ lib/CodeGen/RenameIndependentSubregs.cpp
@@ -74,6 +74,14 @@
       : 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;
 
@@ -88,7 +96,8 @@
   /// belonging to their class.
   void distribute(const IntEqClasses &Classes,
                   const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-                  const SmallVectorImpl<LiveInterval*> &Intervals) const;
+                  const SmallVectorImpl<LiveInterval*> &Intervals,
+                  const SmallVectorImpl<UndefInfo> &UndefInfos) const;
 
   /// \brief Constructs main liverange and add missing undef+dead flags.
   void computeMainRangesFixFlags(const IntEqClasses &Classes,
@@ -98,7 +107,8 @@
   /// 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) const;
+                       const SmallVectorImpl<LiveInterval*> &Intervals,
+                       SmallVectorImpl<UndefInfo> &UndefInfos) const;
 
 
   LiveIntervals *LIS;
@@ -146,8 +156,9 @@
   }
   DEBUG(dbgs() << '\n');
 
-  rewriteOperands(Classes, SubRangeInfos, Intervals);
-  distribute(Classes, SubRangeInfos, Intervals);
+  SmallVector<UndefInfo,8> UndefInfos;
+  rewriteOperands(Classes, SubRangeInfos, Intervals, UndefInfos);
+  distribute(Classes, SubRangeInfos, Intervals, UndefInfos);
   computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
   return true;
 }
@@ -210,7 +221,8 @@
 
 void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
+    const SmallVectorImpl<LiveInterval*> &Intervals,
+    SmallVectorImpl<UndefInfo> &UndefInfos) const {
   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
   unsigned Reg = Intervals[0]->reg;;
   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
@@ -244,6 +256,8 @@
 
     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
@@ -252,7 +266,8 @@
 
 void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
-    const SmallVectorImpl<LiveInterval*> &Intervals) const {
+    const SmallVectorImpl<LiveInterval*> &Intervals,
+    const SmallVectorImpl<UndefInfo> &UndefInfos) const {
   unsigned NumClasses = Classes.getNumClasses();
   SmallVector<unsigned, 8> VNIMapping;
   SmallVector<LiveInterval::SubRange*, 8> SubRanges;
@@ -274,6 +289,15 @@
     }
     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) {
@@ -354,6 +378,12 @@
     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();
   }
 }
 
Index: lib/CodeGen/SplitKit.h
===================================================================
--- lib/CodeGen/SplitKit.h
+++ lib/CodeGen/SplitKit.h
@@ -325,12 +325,30 @@
     return LRCalc[SpillMode != SM_Partition && RegIdx != 0];
   }
 
+  /// Find a subrange corresponding to the lane mask LM in live interval LI.
+  /// The interval LI is assumed to contain such a subrange. This function
+  /// is used to find corresponding subranges between the original interval
+  /// and the new intervals.
+  LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM, LiveInterval &LI);
+
+  /// Add a segment to the interval LI for the value number VNI. If LI has
+  /// subranges, corresponding segments will be added to them as well, but
+  /// with newly created value numbers. If Original is true, dead def will
+  /// only be added a subrange of LI if the corresponding subrange of the
+  /// original interval has a def at this index. Otherwise, all subranges
+  /// of LI will be updated.
+  void addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original);
+
   /// defValue - define a value in RegIdx from ParentVNI at Idx.
   /// Idx does not have to be ParentVNI->def, but it must be contained within
   /// ParentVNI's live range in ParentLI. The new value is added to the value
-  /// map.
+  /// map. The value being defined may either come from rematerialization
+  /// (or an inserted copy), or it may be coming from the original interval.
+  /// The parameter Original should be true in the latter case, otherwise
+  /// it should be false.
   /// Return the new LI value.
-  VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx);
+  VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx,
+                   bool Original);
 
   /// forceRecompute - Force the live range of ParentVNI in RegIdx to be
   /// recomputed by LiveRangeCalc::extend regardless of the number of defs.
Index: lib/CodeGen/SplitKit.cpp
===================================================================
--- lib/CodeGen/SplitKit.cpp
+++ lib/CodeGen/SplitKit.cpp
@@ -381,9 +381,43 @@
 }
 #endif
 
+LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
+                                                        LiveInterval &LI) {
+  for (LiveInterval::SubRange &S : LI.subranges())
+    if (S.LaneMask == LM)
+      return S;
+  llvm_unreachable("SubRange for this mask not found");
+};
+
+void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
+  if (!LI.hasSubRanges()) {
+    LI.createDeadDef(VNI);
+    return;
+  }
+
+  SlotIndex Def = VNI->def;
+  if (Original) {
+    // If we are transferring a def from the original interval, make sure
+    // to only update the subranges for which the original subranges had
+    // a def at this location.
+    for (LiveInterval::SubRange &S : LI.subranges()) {
+      auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
+      VNInfo *PV = PS.getVNInfoAt(Def);
+      if (PV != nullptr && PV->def == Def)
+        S.createDeadDef(Def, LIS.getVNInfoAllocator());
+    }
+  } else {
+    // This is a new def: either from rematerialization, or from an inserted
+    // copy. Since it will define the whole register, update all subranges.
+    for (LiveInterval::SubRange &S : LI.subranges())
+      S.createDeadDef(Def, LIS.getVNInfoAllocator());
+  }
+}
+
 VNInfo *SplitEditor::defValue(unsigned RegIdx,
                               const VNInfo *ParentVNI,
-                              SlotIndex Idx) {
+                              SlotIndex Idx,
+                              bool Original) {
   assert(ParentVNI && "Mapping  NULL value");
   assert(Idx.isValid() && "Invalid SlotIndex");
   assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
@@ -392,28 +426,28 @@
   // Create a new value.
   VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
 
+  bool Force = LI->hasSubRanges();
+  ValueForcePair FP(Force ? nullptr : VNI, Force);
   // Use insert for lookup, so we can add missing values with a second lookup.
   std::pair<ValueMap::iterator, bool> InsP =
-    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id),
-                                 ValueForcePair(VNI, false)));
+    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));
 
-  // This was the first time (RegIdx, ParentVNI) was mapped.
-  // Keep it as a simple def without any liveness.
-  if (InsP.second)
+  // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
+  // forced. Keep it as a simple def without any liveness.
+  if (!Force && InsP.second)
     return VNI;
 
   // If the previous value was a simple mapping, add liveness for it now.
   if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
-    SlotIndex Def = OldVNI->def;
-    LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI));
-    // No longer a simple mapping.  Switch to a complex, non-forced mapping.
-    InsP.first->second = ValueForcePair();
+    addDeadDef(*LI, OldVNI, Original);
+
+    // No longer a simple mapping.  Switch to a complex mapping. If the
+    // interval has subranges, make it a forced mapping.
+    InsP.first->second = ValueForcePair(nullptr, Force);
   }
 
   // This is a complex mapping, add liveness for VNI
-  SlotIndex Def = VNI->def;
-  LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
-
+  addDeadDef(*LI, VNI, Original);
   return VNI;
 }
 
@@ -431,9 +465,8 @@
 
   // This was previously a single mapping. Make sure the old def is represented
   // by a trivial live range.
-  SlotIndex Def = VNI->def;
-  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
-  LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
+  addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
+
   // Mark as complex mapped, forced.
   VFP = ValueForcePair(nullptr, true);
 }
@@ -455,13 +488,18 @@
   unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
   LiveInterval &OrigLI = LIS.getInterval(Original);
   VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
-  LiveRangeEdit::Remat RM(ParentVNI);
-  RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
 
-  if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
-    Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late);
-    ++NumRemats;
-  } else {
+  bool DidRemat = false;
+  if (OrigVNI) {
+    LiveRangeEdit::Remat RM(ParentVNI);
+    RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
+    if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
+      Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late);
+      ++NumRemats;
+      DidRemat = true;
+    }
+  }
+  if (!DidRemat) {
     // Can't remat, just insert a copy from parent.
     CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
                .addReg(Edit->getReg());
@@ -472,7 +510,7 @@
   }
 
   // Define the value in Reg.
-  return defValue(RegIdx, ParentVNI, Def);
+  return defValue(RegIdx, ParentVNI, Def, false);
 }
 
 /// Create a new virtual register and live interval.
@@ -944,14 +982,15 @@
       }
 
       // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
-      DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx);
-      LiveRange &LR = LIS.getInterval(Edit->get(RegIdx));
+      DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx
+                   << '(' << PrintReg(Edit->get(RegIdx)) << ')');
+      LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
 
       // Check for a simply defined value that can be blitted directly.
       ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
       if (VNInfo *VNI = VFP.getPointer()) {
         DEBUG(dbgs() << ':' << VNI->id);
-        LR.addSegment(LiveInterval::Segment(Start, End, VNI));
+        LI.addSegment(LiveInterval::Segment(Start, End, VNI));
         Start = End;
         continue;
       }
@@ -975,7 +1014,8 @@
 
       // The first block may be live-in, or it may have its own def.
       if (Start != BlockStart) {
-        VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
+        auto EP = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
+        VNInfo *VNI = EP.first;
         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?
@@ -995,7 +1035,8 @@
         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?");
-          VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
+          auto EP = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
+          VNInfo *VNI = EP.first;
           assert(VNI && "Missing def for complex mapped parent PHI");
           if (End >= BlockEnd)
             LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
@@ -1003,10 +1044,10 @@
           // This block needs a live-in value.  The last block covered may not
           // be live-out.
           if (End < BlockEnd)
-            LRC.addLiveInBlock(LR, MDT[&*MBB], End);
+            LRC.addLiveInBlock(LI, MDT[&*MBB], End);
           else {
             // Live-through, and we don't know the value.
-            LRC.addLiveInBlock(LR, MDT[&*MBB]);
+            LRC.addLiveInBlock(LI, MDT[&*MBB]);
             LRC.setLiveOutValue(&*MBB, nullptr);
           }
         }
@@ -1027,40 +1068,84 @@
 
 void SplitEditor::extendPHIKillRanges() {
   // Extend live ranges to be live-out for successor PHI values.
-  for (const VNInfo *PHIVNI : Edit->getParent().valnos) {
-    if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
-      continue;
-    unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
-    LiveRange &LR = LIS.getInterval(Edit->get(RegIdx));
-
-    // Check whether PHI is dead.
-    const LiveRange::Segment *Segment = LR.getSegmentContaining(PHIVNI->def);
-    assert(Segment != nullptr && "Missing segment for VNI");
-    if (Segment->end == PHIVNI->def.getDeadSlot()) {
-      // This is a dead PHI. Remove it.
-      LR.removeSegment(*Segment, true);
-      continue;
-    }
+  auto RemoveDeadSegment = [] (SlotIndex Def, LiveRange &LR) -> bool {
+    const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
+    assert(Seg != nullptr && "Missing segment for VNI");
+    if (Seg->end != Def.getDeadSlot())
+      return false;
+    // This is a dead PHI. Remove it.
+    LR.removeSegment(*Seg, true);
+    return true;
+  };
 
-    LiveRangeCalc &LRC = getLRCalc(RegIdx);
-    MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
-    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
-         PE = MBB->pred_end(); PI != PE; ++PI) {
-      SlotIndex End = LIS.getMBBEndIdx(*PI);
+  auto ExtendPHIRange = [this] (MachineBasicBlock &B, LiveRangeCalc &LRC,
+                                LiveRange &LR, bool AllowUndef) -> 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)) {
-        assert(RegAssign.lookup(LastUse) == RegIdx &&
-               "Different register assignment in phi predecessor");
-        LRC.extend(LR, End);
-      }
+      if (Edit->getParent().liveAt(LastUse))
+        LRC.extend(LR, End, 0, AllowUndef);
+    }
+  };
+
+  // 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();
+  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);
+  }
+
+  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);
     }
   }
 }
 
 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
+  struct ExtPoint {
+    ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
+      : MO(O), RegIdx(R), Next(N) {}
+    MachineOperand MO;
+    unsigned RegIdx;
+    SlotIndex Next;
+  };
+
+  auto getMaskForOp = [this] (const MachineOperand &Op) -> LaneBitmask {
+    unsigned Reg = Op.getReg(), Sub = Op.getSubReg();
+    LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
+                              : MRI.getMaxLaneMaskForVReg(Reg);
+    return LM;
+  };
+
+  SmallVector<ExtPoint,4> ExtPoints;
+
   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
        RE = MRI.reg_end(); RI != RE;) {
     MachineOperand &MO = *RI;
@@ -1082,8 +1167,18 @@
 
     // Rewrite to the mapped register at Idx.
     unsigned RegIdx = RegAssign.lookup(Idx);
-    LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
-    MO.setReg(LI->reg);
+    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);
 
@@ -1095,7 +1190,7 @@
     if (MO.isDef()) {
       if (!MO.getSubReg() && !MO.isEarlyClobber())
         continue;
-      // We may wan't to extend a live range for a partial redef, or for a use
+      // We may want to extend a live range for a partial redef, or for a use
       // tied to an early clobber.
       Idx = Idx.getPrevSlot();
       if (!Edit->getParent().liveAt(Idx))
@@ -1103,7 +1198,53 @@
     } else
       Idx = Idx.getRegSlot(true);
 
-    getLRCalc(RegIdx).extend(*LI, Idx.getNextSlot());
+    SlotIndex Next = Idx.getNextSlot();
+    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);
+    }
+  }
+
+  for (ExtPoint &EP : ExtPoints) {
+    LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
+    assert(LI.hasSubRanges());
+
+    LiveRangeCalc SubLRC;
+    unsigned Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
+    LaneBitmask LM = getMaskForOp(EP.MO);
+    // If this is a non-read-undef definition of a sub-register, extend
+    // subranges for everything except that sub-register.
+    if (Sub != 0 && EP.MO.isDef())
+      LM = MRI.getMaxLaneMaskForVReg(Reg) & ~LM;
+    for (LiveInterval::SubRange &S : LI.subranges()) {
+      if (!(S.LaneMask & LM))
+        continue;
+      // The problem here can be that the new register may have been created
+      // 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);
+    }
+  }
+
+  for (unsigned R : *Edit) {
+    LiveInterval &LI = LIS.getInterval(R);
+    if (!LI.hasSubRanges())
+      continue;
+    LI.clear();
+    LI.removeEmptySubRanges();
+    LIS.constructMainRangeFromSubranges(LI);
   }
 }
 
@@ -1146,7 +1287,7 @@
     if (ParentVNI->isUnused())
       continue;
     unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
-    defValue(RegIdx, ParentVNI, ParentVNI->def);
+    defValue(RegIdx, ParentVNI, ParentVNI->def, true);
 
     // Force rematted values to be recomputed everywhere.
     // The new live ranges may be truncated.
@@ -1182,8 +1323,9 @@
     deleteRematVictims();
 
   // Get rid of unused values and set phi-kill flags.
-  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) {
-    LiveInterval &LI = LIS.getInterval(*I);
+  for (unsigned Reg : *Edit) {
+    LiveInterval &LI = LIS.getInterval(Reg);
+    LI.removeEmptySubRanges();
     LI.RenumberValues();
   }
 
Index: lib/CodeGen/VirtRegMap.cpp
===================================================================
--- lib/CodeGen/VirtRegMap.cpp
+++ lib/CodeGen/VirtRegMap.cpp
@@ -338,6 +338,7 @@
   assert(LI.liveAt(BaseIndex) &&
          "Reads of completely dead register should be marked undef already");
   unsigned SubRegIdx = MO.getSubReg();
+  assert(SubRegIdx != 0 && LI.hasSubRanges());
   LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
   // See if any of the relevant subregister liveranges is defined at this point.
   for (const LiveInterval::SubRange &SR : LI.subranges()) {
Index: lib/Target/Hexagon/HexagonExpandCondsets.cpp
===================================================================
--- lib/Target/Hexagon/HexagonExpandCondsets.cpp
+++ lib/Target/Hexagon/HexagonExpandCondsets.cpp
@@ -462,7 +462,8 @@
   }
   for (auto &SI : PredDefs) {
     MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
-    if (Range.extendInBlock(LIS->getMBBStartIdx(BB), SI))
+    auto P = Range.extendInBlock(LIS->getMBBStartIdx(BB), SI);
+    if (P.first != nullptr || P.second)
       SI = SlotIndex();
   }
 
@@ -479,7 +480,7 @@
     if (Dominate(Defs, BB))
       ExtTo.push_back(SI);
   }
-  LIS->extendToIndices(Range, ExtTo);
+  LIS->extendToIndices(Range, ExtTo, true);
 
   // Remove <dead> flags from all defs that are not dead after live range
   // extension, and collect all def operands. They will be used to generate
Index: test/CodeGen/Hexagon/regalloc-bad-undef.mir
===================================================================
--- /dev/null
+++ test/CodeGen/Hexagon/regalloc-bad-undef.mir
@@ -0,0 +1,209 @@
+# RUN: llc -march=hexagon -hexagon-subreg-liveness -start-after machine-scheduler -stop-after stack-slot-coloring -o - %s | FileCheck %s
+
+--- |
+  target triple = "hexagon"
+
+  ; Function Attrs: nounwind optsize
+  define void @main() #0 {
+  entry:
+    br label %for.body
+
+  for.body:                                         ; preds = %if.end82, %entry
+    %lsr.iv = phi i32 [ %lsr.iv.next, %if.end82 ], [ 524288, %entry ]
+    %call9 = tail call i32 @lrand48() #0
+    %conv10 = sext i32 %call9 to i64
+    %shr11 = lshr i64 %conv10, 9
+    %or12 = or i64 0, %shr11
+    %call14 = tail call i32 @lrand48() #0
+    %conv15138 = zext i32 %call14 to i64
+    %shr16 = lshr i64 %conv15138, 9
+    %0 = call i64 @llvm.hexagon.S2.extractup(i64 %conv15138, i32 22, i32 9)
+    %1 = shl i64 %0, 42
+    %shl17 = shl i64 %shr16, 42
+    %or22 = or i64 0, %1
+    %or26 = or i64 %or22, 0
+    %shr30 = lshr i64 undef, 25
+    %2 = call i64 @llvm.hexagon.S2.extractup(i64 undef, i32 6, i32 25)
+    %and = and i64 %shr30, 63
+    %sub = shl i64 2, %2
+    %add = add i64 %sub, -1
+    %shl37 = shl i64 %add, 0
+    %call38 = tail call i32 @lrand48() #0
+    %conv39141 = zext i32 %call38 to i64
+    %shr40 = lshr i64 %conv39141, 25
+    %3 = call i64 @llvm.hexagon.S2.extractup(i64 %conv39141, i32 6, i32 25)
+    %and41 = and i64 %shr40, 63
+    %sub43 = shl i64 2, %3
+    %add45 = add i64 %sub43, -1
+    %call46 = tail call i32 @lrand48() #0
+    %shr48 = lshr i64 undef, 25
+    %4 = call i64 @llvm.hexagon.S2.extractup(i64 undef, i32 6, i32 25)
+    %and49 = and i64 %shr48, 63
+    %shl50 = shl i64 %add45, %4
+    %and52 = and i64 %shl37, %or12
+    %and54 = and i64 %shl50, %or26
+    store i64 %and54, i64* undef, align 8
+    %cmp56 = icmp eq i64 %and52, 0
+    br i1 %cmp56, label %for.end, label %if.end82
+
+  if.end82:                                         ; preds = %for.body
+    %lsr.iv.next = add nsw i32 %lsr.iv, -1
+    %exitcond = icmp eq i32 %lsr.iv.next, 0
+    br i1 %exitcond, label %for.end, label %for.body
+
+  for.end:                                          ; preds = %if.end82, %for.body
+    unreachable
+  }
+
+  declare i32 @lrand48() #0
+  declare i64 @llvm.hexagon.S2.extractup(i64, i32, i32) #1
+
+  attributes #0 = { nounwind optsize "target-cpu"="hexagonv55" "target-features"="-hvx,-hvx-double" }
+  attributes #1 = { nounwind readnone }
+
+...
+---
+name:            main
+alignment:       2
+exposesReturnsTwice: false
+hasInlineAsm:    false
+allVRegsAllocated: false
+isSSA:           false
+tracksRegLiveness: true
+tracksSubRegLiveness: true
+registers:
+  - { id: 0, class: intregs }
+  - { id: 1, class: intregs }
+  - { id: 2, class: intregs }
+  - { id: 3, class: intregs }
+  - { id: 4, class: doubleregs }
+  - { id: 5, class: intregs }
+  - { id: 6, class: doubleregs }
+  - { id: 7, class: doubleregs }
+  - { id: 8, class: doubleregs }
+  - { id: 9, class: doubleregs }
+  - { id: 10, class: intregs }
+  - { id: 11, class: doubleregs }
+  - { id: 12, class: doubleregs }
+  - { id: 13, class: doubleregs }
+  - { id: 14, class: intregs }
+  - { id: 15, class: doubleregs }
+  - { id: 16, class: doubleregs }
+  - { id: 17, class: intregs }
+  - { id: 18, class: doubleregs }
+  - { id: 19, class: intregs }
+  - { id: 20, class: doubleregs }
+  - { id: 21, class: doubleregs }
+  - { id: 22, class: doubleregs }
+  - { id: 23, class: intregs }
+  - { id: 24, class: doubleregs }
+  - { id: 25, class: predregs }
+  - { id: 26, class: predregs }
+  - { id: 27, class: intregs }
+  - { id: 28, class: intregs }
+  - { id: 29, class: doubleregs }
+  - { id: 30, class: intregs }
+  - { id: 31, class: intregs }
+  - { id: 32, class: doubleregs }
+  - { id: 33, class: intregs }
+  - { id: 34, class: intregs }
+  - { id: 35, class: doubleregs }
+  - { id: 36, class: doubleregs }
+  - { id: 37, class: intregs }
+  - { id: 38, class: intregs }
+  - { id: 39, class: doubleregs }
+  - { id: 40, class: doubleregs }
+  - { id: 41, class: intregs }
+  - { id: 42, class: intregs }
+  - { id: 43, class: doubleregs }
+  - { id: 44, class: intregs }
+  - { id: 45, class: intregs }
+  - { id: 46, class: doubleregs }
+  - { id: 47, class: doubleregs }
+  - { id: 48, class: doubleregs }
+  - { id: 49, class: doubleregs }
+  - { id: 50, class: doubleregs }
+  - { id: 51, class: doubleregs }
+  - { id: 52, class: intregs }
+  - { id: 53, class: intregs }
+  - { id: 54, class: intregs }
+  - { id: 55, class: doubleregs }
+  - { id: 56, class: doubleregs }
+  - { id: 57, class: intregs }
+  - { id: 58, class: intregs }
+  - { id: 59, class: intregs }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        true
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+body:             |
+  bb.0.entry:
+    successors: %bb.1.for.body
+
+    %59 = A2_tfrsi 524288
+    undef %32:subreg_hireg = A2_tfrsi 0
+    %8 = S2_extractup undef %9, 6, 25
+    %47 = A2_tfrpi 2
+    %13 = A2_tfrpi -1
+    %13 = S2_asl_r_p_acc %13, %47, %8:subreg_loreg
+    %51 = A2_tfrpi 0
+
+    ; CHECK: %d2 = S2_extractup undef %d0, 6, 25
+    ; CHECK: %d0 = A2_tfrpi 2
+    ; CHECK: %d13 = A2_tfrpi -1
+    ; CHECK-NOT: undef %r4
+
+  bb.1.for.body:
+    successors: %bb.3.for.end, %bb.2.if.end82
+
+    ADJCALLSTACKDOWN 0, implicit-def dead %r29, implicit-def dead %r30, implicit %r31, implicit %r30, implicit %r29
+    J2_call @lrand48, implicit-def dead %d0, implicit-def dead %d1, implicit-def dead %d2, implicit-def dead %d3, implicit-def dead %d4, implicit-def dead %d5, implicit-def dead %d6, implicit-def dead %d7, implicit-def dead %r28, implicit-def dead %r31, implicit-def dead %p0, implicit-def dead %p1, implicit-def dead %p2, implicit-def dead %p3, implicit-def dead %m0, implicit-def dead %m1, implicit-def dead %lc0, implicit-def dead %lc1, implicit-def dead %sa0, implicit-def dead %sa1, implicit-def dead %usr, implicit-def %usr_ovf, implicit-def dead %cs0, implicit-def dead %cs1, implicit-def dead %w0, implicit-def dead %w1, implicit-def dead %w2, implicit-def dead %w3, implicit-def dead %w4, implicit-def dead %w5, implicit-def dead %w6, implicit-def dead %w7, implicit-def dead %w8, implicit-def dead %w9, implicit-def dead %w10, implicit-def dead %w11, implicit-def dead %w12, implicit-def dead %w13, implicit-def dead %w14, implicit-def dead %w15, implicit-def dead %q0, implicit-def dead %q1, implicit-def dead %q2, implicit-def dead %q3, implicit-def %r0
+    ADJCALLSTACKUP 0, 0, implicit-def dead %r29, implicit-def dead %r30, implicit-def dead %r31, implicit %r29
+    undef %29:subreg_loreg = COPY killed %r0
+    %29:subreg_hireg = S2_asr_i_r %29:subreg_loreg, 31
+    ADJCALLSTACKDOWN 0, implicit-def dead %r29, implicit-def dead %r30, implicit %r31, implicit %r30, implicit %r29
+    J2_call @lrand48, implicit-def dead %d0, implicit-def dead %d1, implicit-def dead %d2, implicit-def dead %d3, implicit-def dead %d4, implicit-def dead %d5, implicit-def dead %d6, implicit-def dead %d7, implicit-def dead %r28, implicit-def dead %r31, implicit-def dead %p0, implicit-def dead %p1, implicit-def dead %p2, implicit-def dead %p3, implicit-def dead %m0, implicit-def dead %m1, implicit-def dead %lc0, implicit-def dead %lc1, implicit-def dead %sa0, implicit-def dead %sa1, implicit-def dead %usr, implicit-def %usr_ovf, implicit-def dead %cs0, implicit-def dead %cs1, implicit-def dead %w0, implicit-def dead %w1, implicit-def dead %w2, implicit-def dead %w3, implicit-def dead %w4, implicit-def dead %w5, implicit-def dead %w6, implicit-def dead %w7, implicit-def dead %w8, implicit-def dead %w9, implicit-def dead %w10, implicit-def dead %w11, implicit-def dead %w12, implicit-def dead %w13, implicit-def dead %w14, implicit-def dead %w15, implicit-def dead %q0, implicit-def dead %q1, implicit-def dead %q2, implicit-def dead %q3, implicit-def %r0
+    ADJCALLSTACKUP 0, 0, implicit-def dead %r29, implicit-def dead %r30, implicit-def dead %r31, implicit %r29
+    %32:subreg_loreg = COPY killed %r0
+    %7 = S2_extractup %32, 22, 9
+    ADJCALLSTACKDOWN 0, implicit-def dead %r29, implicit-def dead %r30, implicit %r31, implicit %r30, implicit %r29
+    J2_call @lrand48, implicit-def dead %d0, implicit-def dead %d1, implicit-def dead %d2, implicit-def dead %d3, implicit-def dead %d4, implicit-def dead %d5, implicit-def dead %d6, implicit-def dead %d7, implicit-def dead %r28, implicit-def dead %r31, implicit-def dead %p0, implicit-def dead %p1, implicit-def dead %p2, implicit-def dead %p3, implicit-def dead %m0, implicit-def dead %m1, implicit-def dead %lc0, implicit-def dead %lc1, implicit-def dead %sa0, implicit-def dead %sa1, implicit-def dead %usr, implicit-def %usr_ovf, implicit-def dead %cs0, implicit-def dead %cs1, implicit-def dead %w0, implicit-def dead %w1, implicit-def dead %w2, implicit-def dead %w3, implicit-def dead %w4, implicit-def dead %w5, implicit-def dead %w6, implicit-def dead %w7, implicit-def dead %w8, implicit-def dead %w9, implicit-def dead %w10, implicit-def dead %w11, implicit-def dead %w12, implicit-def dead %w13, implicit-def dead %w14, implicit-def dead %w15, implicit-def dead %q0, implicit-def dead %q1, implicit-def dead %q2, implicit-def dead %q3, implicit-def %r0
+    ADJCALLSTACKUP 0, 0, implicit-def dead %r29, implicit-def dead %r30, implicit-def dead %r31, implicit %r29
+    undef %43:subreg_loreg = COPY killed %r0
+    %43:subreg_hireg = COPY %32:subreg_hireg
+    %16 = S2_extractup %43, 6, 25
+    %18 = A2_tfrpi -1
+    %18 = S2_asl_r_p_acc %18, %47, %16:subreg_loreg
+    ADJCALLSTACKDOWN 0, implicit-def dead %r29, implicit-def dead %r30, implicit %r31, implicit %r30, implicit %r29
+    J2_call @lrand48, implicit-def dead %d0, implicit-def dead %d1, implicit-def dead %d2, implicit-def dead %d3, implicit-def dead %d4, implicit-def dead %d5, implicit-def dead %d6, implicit-def dead %d7, implicit-def dead %r28, implicit-def dead %r31, implicit-def dead %p0, implicit-def dead %p1, implicit-def dead %p2, implicit-def dead %p3, implicit-def dead %m0, implicit-def dead %m1, implicit-def dead %lc0, implicit-def dead %lc1, implicit-def dead %sa0, implicit-def dead %sa1, implicit-def dead %usr, implicit-def %usr_ovf, implicit-def dead %cs0, implicit-def dead %cs1, implicit-def dead %w0, implicit-def dead %w1, implicit-def dead %w2, implicit-def dead %w3, implicit-def dead %w4, implicit-def dead %w5, implicit-def dead %w6, implicit-def dead %w7, implicit-def dead %w8, implicit-def dead %w9, implicit-def dead %w10, implicit-def dead %w11, implicit-def dead %w12, implicit-def dead %w13, implicit-def dead %w14, implicit-def dead %w15, implicit-def dead %q0, implicit-def dead %q1, implicit-def dead %q2, implicit-def dead %q3
+    ADJCALLSTACKUP 0, 0, implicit-def dead %r29, implicit-def dead %r30, implicit-def dead %r31, implicit %r29
+    %22 = S2_asl_r_p %18, %8:subreg_loreg
+    %21 = COPY %13
+    %21 = S2_lsr_i_p_and %21, %29, 9
+    %22 = S2_asl_i_p_and %22, %7, 42
+    S2_storerd_io undef %23, 0, %22 :: (store 8 into `i64* undef`)
+    %25 = C2_cmpeqp %21, %51
+    J2_jumpt %25, %bb.3.for.end, implicit-def dead %pc
+    J2_jump %bb.2.if.end82, implicit-def dead %pc
+
+  bb.2.if.end82:
+    successors: %bb.3.for.end, %bb.1.for.body
+
+    %59 = A2_addi %59, -1
+    %26 = C2_cmpeqi %59, 0
+    J2_jumpf %26, %bb.1.for.body, implicit-def dead %pc
+    J2_jump %bb.3.for.end, implicit-def dead %pc
+
+  bb.3.for.end:
+
+...