Index: lib/CodeGen/RegisterCoalescer.cpp
===================================================================
--- lib/CodeGen/RegisterCoalescer.cpp
+++ lib/CodeGen/RegisterCoalescer.cpp
@@ -1396,11 +1396,29 @@
   } else if (SrcLI.liveAt(Idx))
     return false;
 
-  LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
-
-  // Remove any DstReg segments starting at the instruction.
+  // If the undef copy defines a live-out value (i.e. an input to a PHI def),
+  // then replace it with an IMPLICIT_DEF.
   LiveInterval &DstLI = LIS->getInterval(DstReg);
   SlotIndex RegIndex = Idx.getRegSlot();
+  LiveRange::Segment *Seg = DstLI.getSegmentContaining(RegIndex);
+  assert(Seg != nullptr && "No segment for defining instruction");
+  if (VNInfo *V = DstLI.getVNInfoAt(Seg->end)) {
+    if (V->isPHIDef()) {
+      CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
+      for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {
+        MachineOperand &MO = CopyMI->getOperand(i-1);
+        if (MO.isReg() && MO.isUse())
+          CopyMI->RemoveOperand(i-1);
+      }
+      LLVM_DEBUG(dbgs() << "\tReplaced copy of <undef> value with an "
+                           "implicit def\n");
+      return false;
+    }
+  }
+
+  // Remove any DstReg segments starting at the instruction.
+  LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
+
   // Remove value or merge with previous one in case of a subregister def.
   if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
     VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
@@ -2078,6 +2096,13 @@
     /// True once Pruned above has been computed.
     bool PrunedComputed = false;
 
+    /// True if this value is determined to be identical to OtherVNI
+    /// (in valuesIdentical). This is used with CR_Erase where the erased
+    /// copy is redundant, i.e. the source value is already the same as
+    /// the destination. In such cases the subranges need to be updated
+    /// properly. See comment at pruneSubRegValues for more info.
+    bool Identical = false;
+
     Val() = default;
 
     bool isAnalyzed() const { return WriteLanes.any(); }
@@ -2092,7 +2117,8 @@
   LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
 
   /// Find the ultimate value that VNI was copied from.
-  std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const;
+  std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI,
+                                                    unsigned OtherReg) const;
 
   bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const;
 
@@ -2211,18 +2237,18 @@
 }
 
 std::pair<const VNInfo*, unsigned> JoinVals::followCopyChain(
-    const VNInfo *VNI) const {
-  unsigned Reg = this->Reg;
+    const VNInfo *VNI, unsigned OtherReg) const {
+  unsigned TrackReg = Reg;
 
   while (!VNI->isPHIDef()) {
     SlotIndex Def = VNI->def;
     MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
     assert(MI && "No defining instruction");
     if (!MI->isFullCopy())
-      return std::make_pair(VNI, Reg);
+      return std::make_pair(VNI, TrackReg);
     unsigned SrcReg = MI->getOperand(1).getReg();
     if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
-      return std::make_pair(VNI, Reg);
+      return std::make_pair(VNI, TrackReg);
 
     const LiveInterval &LI = LIS->getInterval(SrcReg);
     const VNInfo *ValueIn;
@@ -2243,25 +2269,41 @@
         break;
       }
     }
-    if (ValueIn == nullptr)
+    if (ValueIn == nullptr) {
+      // Reaching undefined value is legitimate in cases where it comes from
+      // one of the considered registers (Reg or OtherReg).
+      //
+      // 1   undef %0.sub1 = ...  ;; %0.sub0 == undef
+      // 2   %1 = COPY %0         ;; %1 is defined here.
+      // 3   %0 = COPY %1         ;; Now %0.sub0 has a definition!
+      // 4   ...                  ;; Here we should indicate that %0 at 3 is
+      //                          ;; the same as %0 at 2 (%0 at 3 == %1 at 2).
+      if (SrcReg == Reg || SrcReg == OtherReg)
+        return std::make_pair(nullptr, SrcReg);
       break;
+    }
     VNI = ValueIn;
-    Reg = SrcReg;
+    TrackReg = SrcReg;
   }
-  return std::make_pair(VNI, Reg);
+  return std::make_pair(VNI, TrackReg);
 }
 
 bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
                                const JoinVals &Other) const {
   const VNInfo *Orig0;
   unsigned Reg0;
-  std::tie(Orig0, Reg0) = followCopyChain(Value0);
-  if (Orig0 == Value1)
+  std::tie(Orig0, Reg0) = followCopyChain(Value0, Other.Reg);
+  if (Orig0 == Value1 && Reg0 == Other.Reg)
     return true;
 
   const VNInfo *Orig1;
   unsigned Reg1;
-  std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
+  std::tie(Orig1, Reg1) = Other.followCopyChain(Value1, Reg);
+  // If both values are undefined, and the source registers are the same
+  // register, the values are identical. Filter out cases where only one
+  // value is defined.
+  if (Orig0 == nullptr || Orig1 == nullptr)
+    return Orig0 == Orig1 && Reg0 == Reg1;
 
   // The values are equal if they are defined at the same place and use the
   // same register. Note that we cannot compare VNInfos directly as some of
@@ -2438,8 +2480,10 @@
   //   %this  = COPY %ext <-- Erase this copy
   //
   if (DefMI->isFullCopy() && !CP.isPartial()
-      && valuesIdentical(VNI, V.OtherVNI, Other))
+      && valuesIdentical(VNI, V.OtherVNI, Other)) {
+    V.Identical = true;
     return CR_Erase;
+  }
 
   // If the lanes written by this instruction were all undef in OtherVNI, it is
   // still safe to join the live ranges. This can't be done with a simple value
@@ -2743,19 +2787,62 @@
   }
 }
 
+/// Consider the following situation when coalescing the copy between
+/// %31 and %45 at 800. (The vertical lines represent live range segments.)
+///
+///                              Main range         Subrange 0004 (sub2)
+///                              %31    %45           %31    %45
+///  544    %45 = COPY %28               +                    +
+///                                      | v1                 | v1
+///  560B bb.1:                          +                    +
+///  624        = %45.sub2               | v2                 | v2
+///  800    %31 = COPY %45        +      +             +      +
+///                               | v0                 | v0
+///  816    %31.sub1 = ...        +                    |
+///  880    %30 = COPY %31        | v1                 +
+///  928    %45 = COPY %30        |      +                    +
+///                               |      | v0                 | v0  <--+
+///  992B   ; backedge -> bb.1    |      +                    +        |
+/// 1040        = %31.sub0        +                                    |
+///                                                 This value must remain
+///                                                 live-out!
+///
+/// Assuming that %31 is coalesced into %45, the copy at 928 becomes
+/// redundant, since it copies the value from %45 back into it. The
+/// conflict resolution for the main range determines that %45.v0 is
+/// to be erased, which is ok since %31.v1 is identical to it.
+/// The problem happens with the subrange for sub2: it has to be live
+/// on exit from the block, but since 928 was actually a point of
+/// definition of %45.sub2, %45.sub2 was not live immediately prior
+/// to that definition. As a result, when 928 was erased, the value v0
+/// for %45.sub2 was pruned in pruneSubRegValues. Consequently, an
+/// IMPLICIT_DEF was inserted as a "backedge" definition for %45.sub2,
+/// providing an incorrect value to the use at 624.
+///
+/// Since the main-range values %31.v1 and %45.v0 were proved to be
+/// identical, the corresponding values in subranges must also be the
+/// same. A redundant copy is removed because it's not needed, and not
+/// because it copied an undefined value, so any liveness that originated
+/// from that copy cannot disappear. When pruning a value that started
+/// at the removed copy, the corresponding identical value must be
+/// extended to replace it.
 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) {
+    Val &V = Vals[i];
     // We should trigger in all cases in which eraseInstrs() does something.
     // match what eraseInstrs() is doing, print a message so
-    if (Vals[i].Resolution != CR_Erase &&
-        (Vals[i].Resolution != CR_Keep || !Vals[i].ErasableImplicitDef ||
-         !Vals[i].Pruned))
+    if (V.Resolution != CR_Erase &&
+        (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned))
       continue;
 
     // Check subranges at the point where the copy will be removed.
     SlotIndex Def = LR.getValNumInfo(i)->def;
+    SlotIndex OtherDef;
+    if (V.Identical)
+      OtherDef = V.OtherVNI->def;
+
     // Print message so mismatches with eraseInstrs() can be diagnosed.
     LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def
                       << '\n');
@@ -2768,10 +2855,24 @@
       if (ValueOut != nullptr && Q.valueIn() == nullptr) {
         LLVM_DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)
                           << " at " << Def << "\n");
-        LIS->pruneValue(S, Def, nullptr);
+        SmallVector<SlotIndex,8> EndPoints;
+        LIS->pruneValue(S, Def, &EndPoints);
         DidPrune = true;
         // Mark value number as unused.
         ValueOut->markUnused();
+
+        if (V.Identical && S.Query(OtherDef).valueOut()) {
+          // If V is identical to V.OtherVNI (and S was live at OtherDef),
+          // then we can't simply prune V from S. V needs to be replaced
+          // with V.OtherVNI.
+          LIS->extendToIndices(S, EndPoints);
+#ifndef NDEBUG
+          // Make sure that the value at Def is really V.OtherVNI.
+          LiveRange::iterator Id = S.find(OtherDef);
+          LiveRange::iterator T = S.find(Def);
+          assert(Id != S.end() && T != S.end() && T->valno == Id->valno);
+#endif
+        }
         continue;
       }
       // If a subrange ends at the copy, then a value was copied but only
Index: test/CodeGen/AMDGPU/coalescer-extend-pruned-subrange.mir
===================================================================
--- /dev/null
+++ test/CodeGen/AMDGPU/coalescer-extend-pruned-subrange.mir
@@ -0,0 +1,128 @@
+# RUN: llc -mtriple=amdgcn--amdpal -mcpu=gfx803 -run-pass=simple-register-coalescing -o - %s | FileCheck -check-prefix=GCN %s
+
+# GCN: {{^body}}
+
+---
+name: foo
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.2
+
+    %0:sreg_32_xm0 = S_MOV_B32 1
+    %1:vgpr_32 = COPY %0
+    INLINEASM &"; %1", 1, 327690, def %1, 2147483657, %1(tied-def 3)
+    %2:sreg_64 = V_CMP_NE_U32_e64 0, %1, implicit $exec
+    undef %3.sub0:sreg_128 = COPY %0
+    %3.sub1:sreg_128 = COPY %0
+    %3.sub2:sreg_128 = COPY %0
+    %4:sreg_128 = COPY %3
+    %5:vgpr_32 = V_MOV_B32_e32 -64, implicit $exec
+    %6:vreg_128 = COPY %4
+    %7:sreg_32_xm0 = S_AND_B32 target-flags(amdgpu-gotprel) 1, %2.sub0, implicit-def dead $scc
+    %8:sreg_32_xm0 = S_MOV_B32 0
+    %9:vgpr_32 = COPY %5
+    %10:vreg_128 = COPY %6
+    S_BRANCH %bb.2
+
+  bb.1:
+    %11:vgpr_32 = V_OR_B32_e32 %12.sub0, %12.sub1, implicit $exec
+    %13:vgpr_32 = V_OR_B32_e32 %11, %12.sub2, implicit $exec
+    %14:vgpr_32 = V_AND_B32_e32 1, %13, implicit $exec
+    %15:sreg_64_xexec = V_CMP_EQ_U32_e64 0, %14, implicit $exec
+    %16:vgpr_32 = V_CNDMASK_B32_e64 0, 1, %15, implicit $exec
+    BUFFER_STORE_DWORD_OFFEN_exact %16, undef %17:vgpr_32, undef %18:sreg_128, 0, 0, 0, 0, 0, implicit $exec :: (dereferenceable store 4 into constant-pool, align 1, addrspace 4)
+    S_ENDPGM
+
+  bb.2:
+    successors: %bb.3, %bb.4
+
+    %19:sreg_64 = V_CMP_EQ_U32_e64 1, %7, implicit $exec
+    %20:sreg_64 = COPY $exec, implicit-def $exec
+    %21:sreg_64 = S_AND_B64 %20, %19, implicit-def dead $scc
+    $exec = S_MOV_B64_term %21
+    SI_MASK_BRANCH %bb.4, implicit $exec
+    S_BRANCH %bb.3
+
+  bb.3:
+    successors: %bb.4
+
+    undef %22.sub0:sreg_128 = COPY %8
+    %22.sub1:sreg_128 = COPY %8
+    %22.sub2:sreg_128 = COPY %8
+    %23:sreg_128 = COPY %22
+    %24:vreg_128 = COPY %23
+    %10:vreg_128 = COPY %24
+
+  bb.4:
+    successors: %bb.5
+
+    $exec = S_OR_B64 $exec, %20, implicit-def $scc
+
+  bb.5:
+    successors: %bb.7, %bb.6
+
+    S_CBRANCH_SCC0 %bb.7, implicit undef $scc
+
+  bb.6:
+    successors: %bb.9
+
+    %12:vreg_128 = COPY %10
+    S_BRANCH %bb.9
+
+  bb.7:
+    successors: %bb.8, %bb.10
+
+    %25:vgpr_32 = V_AND_B32_e32 target-flags(amdgpu-gotprel32-hi) 1, %10.sub2, implicit $exec
+    %26:sreg_64 = V_CMP_EQ_U32_e64 1, %25, implicit $exec
+    %27:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %28:vreg_1 = COPY %27
+    %29:sreg_64 = COPY $exec, implicit-def $exec
+    %30:sreg_64 = S_AND_B64 %29, %26, implicit-def dead $scc
+    $exec = S_MOV_B64_term %30
+    SI_MASK_BRANCH %bb.10, implicit $exec
+    S_BRANCH %bb.8
+
+  bb.8:
+    successors: %bb.10
+
+    %31:vgpr_32 = BUFFER_LOAD_DWORD_OFFEN undef %32:vgpr_32, undef %33:sreg_128, 0, 0, 0, 0, 0, implicit $exec :: (dereferenceable load 4 from constant-pool, align 1, addrspace 4)
+    %34:sreg_64_xexec = V_CMP_NE_U32_e64 0, %31, implicit $exec
+    %35:vgpr_32 = V_CNDMASK_B32_e64 0, -1, %34, implicit $exec
+    %28:vreg_1 = COPY %35
+    S_BRANCH %bb.10
+
+  bb.9:
+    successors: %bb.11
+
+    S_BRANCH %bb.11
+
+  bb.10:
+    successors: %bb.9
+
+    $exec = S_OR_B64 $exec, %29, implicit-def $scc
+    %36:vreg_1 = COPY %28
+    %37:sreg_64_xexec = V_CMP_NE_U32_e64 0, %36, implicit $exec
+    %38:vgpr_32 = V_CNDMASK_B32_e64 0, 1, %37, implicit $exec
+    %39:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    undef %40.sub0:vreg_128 = COPY %39
+    %40.sub1:vreg_128 = COPY %39
+    %40.sub2:vreg_128 = COPY %38
+    %41:vreg_128 = COPY %40
+    %12:vreg_128 = COPY %41
+    S_BRANCH %bb.9
+
+  bb.11:
+    successors: %bb.2, %bb.1
+
+    %42:vgpr_32 = V_ADD_I32_e32 32, %9, implicit-def dead $vcc, implicit $exec
+    V_CMP_EQ_U32_e32 0, %42, implicit-def $vcc, implicit $exec
+    %43:vgpr_32 = COPY %42
+    $vcc = S_AND_B64 $exec, killed $vcc, implicit-def dead $scc
+    %44:vreg_128 = COPY %12
+    %9:vgpr_32 = COPY %43
+    %10:vreg_128 = COPY %44
+    S_CBRANCH_VCCNZ %bb.1, implicit killed $vcc
+    S_BRANCH %bb.2
+
+...
Index: test/CodeGen/AMDGPU/coalescer-identical-values-undef.mir
===================================================================
--- /dev/null
+++ test/CodeGen/AMDGPU/coalescer-identical-values-undef.mir
@@ -0,0 +1,29 @@
+# RUN: llc -mtriple=amdgcn--amdpal -run-pass=simple-register-coalescing -o - %s | FileCheck %s
+
+# Check that this doesn't crash. Check for some legitimate output.
+# CHECK: S_CBRANCH_SCC1
+
+---
+name: fred
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: $sgpr4
+    undef %0.sub2:sreg_128 = COPY $sgpr4
+    %3 = IMPLICIT_DEF
+    S_CBRANCH_SCC1 %bb.2, implicit undef $scc
+
+  bb.1:
+    successors: %bb.2
+    %0.sub0:sreg_128 = COPY %0.sub2
+    %0.sub1:sreg_128 = COPY %0.sub2
+    %1:sreg_128 = COPY %0
+    %2:sreg_128 = COPY %0
+    %0:sreg_128 = COPY %2
+    %3:sreg_128 = COPY %1
+
+  bb.2:
+    $sgpr1 = COPY %3
+    $sgpr2 = COPY %0.sub2
+...
Index: test/CodeGen/AMDGPU/coalescing-with-subregs-in-loop-bug.mir
===================================================================
--- /dev/null
+++ test/CodeGen/AMDGPU/coalescing-with-subregs-in-loop-bug.mir
@@ -0,0 +1,98 @@
+# RUN: llc -mtriple=amdgcn--amdpal -mcpu=gfx803 -run-pass=simple-register-coalescing,rename-independent-subregs %s -o - | FileCheck -check-prefix=GCN %s
+
+# This test is for a bug where the following happens:
+#
+# Inside the loop, %29.sub2 is used in a V_LSHLREV whose result is then used
+# in an LDS read. %29 is a 128 bit value that is linked by copies to
+# %45 (from phi elimination), %28 (the value in the loop pre-header),
+# %31 (defined and subreg-modified in the loop, and used after the loop)
+# and %30:
+#
+#     %45:vreg_128 = COPY killed %28
+# bb.1:
+#     %29:vreg_128 = COPY killed %45
+#     %39:vgpr_32 = V_LSHLREV_B32_e32 2, %29.sub2, implicit $exec
+#     %31:vreg_128 = COPY killed %29
+#     %31.sub1:vreg_128 = COPY %34
+#     %30:vreg_128 = COPY %31
+#     %45:vreg_128 = COPY killed %30
+#     S_CBRANCH_EXECNZ %bb.39, implicit $exec
+#     S_BRANCH %bb.40
+# bb.2:
+#     undef %32.sub0:vreg_128 = COPY killed %31.sub0
+#
+# So this coalesces together into a single 128 bit value whose sub1 is modified
+# in the loop, but the sub2 used in the V_LSHLREV is not modified in the loop.
+#
+# The bug is that the coalesced value has a L00000004 subrange (for sub2) that
+# says that it is not live up to the end of the loop block. The symptom is that
+# Rename Independent Subregs separates sub2 into its own register, and it is
+# not live round the loop, so that pass adds an IMPLICIT_DEF for it just before
+# the loop backedge.
+
+# GCN: bb.1:
+# GCN: V_LSHLREV_B32_e32 2, [[val:%[0-9][0-9]*]].sub2
+# GCN-NOT: [[val]]:vreg_128 = IMPLICIT_DEF
+
+---
+name: _amdgpu_cs_main
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.1
+
+    %3:sgpr_32 = S_MOV_B32 0
+    undef %19.sub1:vreg_128 = COPY undef %3
+    %4:sgpr_32 = S_MOV_B32 1
+    %5:sgpr_32 = S_MOV_B32 2
+    %11:sreg_32_xm0 = S_MOV_B32 255
+    undef %28.sub0:vreg_128 = COPY killed %3
+    %28.sub1:vreg_128 = COPY killed %4
+    %28.sub2:vreg_128 = COPY killed %11
+    %28.sub3:vreg_128 = COPY killed %5
+    %2:sreg_64 = S_MOV_B64 0
+    %34:sreg_32 = S_MOV_B32 7
+    %37:vreg_128 = COPY undef %42:vreg_128
+    %43:sreg_64 = COPY killed %2
+    %44:vreg_128 = COPY killed %37
+    %45:vreg_128 = COPY killed %28
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    %29:vreg_128 = COPY killed %45
+    %36:vreg_128 = COPY killed %44
+    %0:sreg_64 = COPY killed %43
+    %39:vgpr_32 = V_LSHLREV_B32_e32 2, %29.sub2, implicit $exec
+    %41:vgpr_32 = V_ADD_I32_e32 1152, %39, implicit-def dead $vcc, implicit $exec
+    $m0 = S_MOV_B32 -1
+    %12:vreg_64 = DS_READ2_B32 killed %41, 0, 1, 0, implicit $m0, implicit $exec
+    %13:vreg_64 = DS_READ2_B32 %39, -112, -111, 0, implicit $m0, implicit $exec
+    %14:vreg_64 = DS_READ2_B32 %39, 0, 1, 0, implicit $m0, implicit $exec
+    %40:vgpr_32 = V_ADD_I32_e32 1160, %39, implicit-def dead $vcc, implicit $exec
+    %15:vreg_64 = DS_READ2_B32 killed %40, 0, 1, 0, implicit $m0, implicit $exec
+    %16:vreg_64 = DS_READ2_B32 %39, -110, -109, 0, implicit $m0, implicit $exec
+    %17:vreg_64 = DS_READ2_B32 %39, 2, 3, 0, implicit $m0, implicit $exec
+    undef %35.sub1:vreg_128 = COPY undef %34
+    %31:vreg_128 = COPY killed %29
+    %31.sub1:vreg_128 = COPY %34
+    %38:vgpr_32 = V_ADD_I32_e32 1, %36.sub0, implicit-def dead $vcc, implicit $exec
+    %18:sreg_64 = V_CMP_LT_I32_e64 5, %38, implicit $exec
+    %1:sreg_64 = S_OR_B64 killed %18, killed %0, implicit-def $scc
+    %30:vreg_128 = COPY %31
+    %43:sreg_64 = COPY %1
+    %44:vreg_128 = COPY %35
+    %45:vreg_128 = COPY killed %30
+    $exec = S_ANDN2_B64_term $exec, %1
+    S_CBRANCH_EXECNZ %bb.1, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.2:
+    $exec = S_OR_B64 $exec, killed %1, implicit-def $scc
+    %33:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    undef %32.sub0:vreg_128 = COPY killed %31.sub0
+    %32.sub2:vreg_128 = COPY %33
+    $vgpr0_vgpr1_vgpr2_vgpr3 = COPY %32:vreg_128
+    S_ENDPGM
+
+...