Use LiveRangeCalc to extend live ranges in shrinkToUses

[kparzysz]

Summary

The function extendSegmentsToUses (used by shrinkToUses) in LiveIntervalAnalysis.cpp duplicates the functionality that is already available in LiveRangeCalc. Moreover, it does not handle cases where a use (of a subregister) is jointly dominated only by the corresponding undefs. This may lead to assertions while compiling valid code.

Switch shrinkToUses to utilize LiveRangeCalc and provide a mapping function that will ensure preservation of value numbers.

[kparzysz]

I was unable to generate a .mir testcase for this. The problem occurred with our internal compiler, with some non-public changes, and even that compiler would work fine on the .mir testcase that was printed immediately before register allocation (i.e. after machine scheduler).

However, here's a piece of information that illustrates the problem. It's a dump of LIS immediately before the problem occurs, i.e. before EliminateDeadDefs in "hoistAllSpills". The dump has been reduced to only include the offending register vreg268.

********** INTERVALS **********
...
%vreg268 [256r,432r:0)[432r,544B:1)[608r,640B:2)[640B,848B:3)[864B,2152r:3)[4128B,4132r:3)[5456B,5488B:1)[5520r,5544B:4)[5544B,5600B:1)  0@256r 1@432r 2@608r 3@640B-phi 4@5520r L00000002 [432r,544B:0)[640B,848B:0)[864B,2152r:0)[4128B,4132r:0)[5456B,5488B:0)[5544B,5600B:0)  0@432r L00000001 [256r,544B:0)[608r,640B:1)[640B,848B:3)[864B,2152r:3)[4128B,4132r:3)[5456B,5488B:0)[5520r,5544B:2)[5544B,5600B:0)  0@256r 1@608r 2@5520r 3@640B-phi
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function fred: NoPHIs, TracksLivenessFrame Objects:
  fi#0: size=8, align=8, at location [SP]

0B      BB#0: derived from LLVM BB %b3
256B            %vreg268:isub_hi<def,read-undef> = L2_loadruh_io %vreg187, 4
432B            %vreg268:isub_lo<def> = COPY %vreg10
448B            %vreg248<def> = S2_lsr_i_vw %vreg268, 8
            Successors according to CFG: BB#12 BB#1

544B    BB#1:
            Predecessors according to CFG: BB#0
608B            %vreg268:isub_hi<def,read-undef> = IMPLICIT_DEF
            Successors according to CFG: BB#2(?%)

640B    BB#2: derived from LLVM BB %b16
            Predecessors according to CFG: BB#14 BB#1 BB#13
            Successors according to CFG: BB#4 BB#3

848B    BB#3: derived from LLVM BB %b23
            Predecessors according to CFG: BB#2

864B    BB#4: derived from LLVM BB %b24
            Predecessors according to CFG: BB#2
            Successors according to CFG: BB#8 BB#5

1848B   BB#5: derived from LLVM BB %b31
            Predecessors according to CFG: BB#4
2108B           S2_storerd_io <fi#0>, 0, %vreg268
            Successors according to CFG: BB#9 BB#6

2144B   BB#6: derived from LLVM BB %b32
            Predecessors according to CFG: BB#5
2152B           KILL <fi#0>, 0, %vreg268
            Successors according to CFG: BB#10 BB#7

2240B   BB#7: derived from LLVM BB %b33
            Predecessors according to CFG: BB#6
            Successors according to CFG: BB#11

4120B   BB#8: derived from LLVM BB %b53
            Predecessors according to CFG: BB#4

4128B   BB#9: derived from LLVM BB %b54
            Predecessors according to CFG: BB#5
4132B           KILL <fi#0>, 0, %vreg268
            Successors according to CFG: BB#11

4256B   BB#10: derived from LLVM BB %b55
            Predecessors according to CFG: BB#6
            Successors according to CFG: BB#11

4376B   BB#11: derived from LLVM BB %b56
            Predecessors according to CFG: BB#7 BB#10 BB#9

5456B   BB#12: derived from LLVM BB %b64
            Predecessors according to CFG: BB#0
            Successors according to CFG: BB#14 BB#13

5488B   BB#13:
            Predecessors according to CFG: BB#12
5520B           %vreg268:isub_hi<def,read-undef> = IMPLICIT_DEF
            Successors according to CFG: BB#2

5544B   BB#14: derived from LLVM BB %b66
            Predecessors according to CFG: BB#12
            Successors according to CFG: BB#2

# End machine code for function fred.

Deleting dead def 2152r KILL <fi#0>, 0, %vreg268; mem:ST8[FixedStack0] DoubleRegs:%vreg268
Deleting dead def 4132r KILL <fi#0>, 0, %vreg268; mem:ST8[FixedStack0] DoubleRegs:%vreg268
Shrink: %vreg268 [256r,432r:0)[432r,544B:1)[608r,640B:2)[640B,848B:3)[864B,2152r:3)[4128B,4132r:3)[5456B,5488B:1)[5520r,5544B:4)[5544B,5600B:1)  0@256r 1@432r 2@608r 3@640B-phi 4@5520r L00000002 [432r,544B:0)[640B,848B:0)[864B,2152r:0)[4128B,4132r:0)[5456B,5488B:0)[5544B,5600B:0)  0@432r L00000001 [256r,544B:0)[608r,640B:1)[640B,848B:3)[864B,2152r:3)[4128B,4132r:3)[5456B,5488B:0)[5520r,5544B:2)[5544B,5600B:0)  0@256r 1@608r 2@5520r 3@640B-phi
Shrink:  L00000002 [432r,544B:0)[640B,848B:0)[864B,2152r:0)[4128B,4132r:0)[5456B,5488B:0)[5544B,5600B:0)  0@432r
 live-in at 1848B
 live-in at 864B
 live-in at 640B
llc: /w/src/llvm.m/lib/CodeGen/LiveIntervalAnalysis.cpp:394: void extendSegmentsToUses(llvm::LiveRange &, const llvm::SlotIndexes &, ShrinkToUsesWorkList &, const llvm::LiveRange &): Assertion `OldRange.getVNInfoBefore(Stop) == VNI && "Wrong value out of predecessor"' failed.

[kparzysz]

I found another instance of this problem, this time in extendPHIRanges.

The code in extendPHIRanges tries to extend a LiveRange that could be a subrange, but it checks the main range of the original LiveInterval to see whether it was live-on-exit in the predecessor. The liveness of the main range does not imply that every subrange was live, and the code may end up trying to extend a subrange that was not live (leading to an abort). Here's an example of how this could happen.

The new range is

%vreg553 [100r,2092B:3)[2092B,2100r:4)[3788r,3872r:1)[3872r,3920B:2)[3920B,4160B:1)[4176B,5156r:2)[5288r,8048B:0)[8064B,9256B:0)  0@5288r 1@3788r 2@3872r 3@100r 4@2092B-phi   L00000002 [2092B,2100r:1)[3788r,3788d:2)[3872r,3920B:3)[4176B,5156r:3)[5288r,5288d:0)  0@5288r 1@2092B-phi 2@3788r 3@3872r   L00000001 [100r,2092B:1)[2092B,2100r:2)[3788r,4160B:3)[4176B,5156r:3)[5288r,8048B:0)[8064B,9256B:0)  0@5288r 1@100r 2@2092B-phi 3@3788r

The block starting at 2092 is a loop header, the preheader ends at 2036 (there is an unrelated block in between). The subrange for L0002 is live-on-entry to 2092, but it is not live in the preheader. The original range (for vreg458 shown below) is live-on-exit from the predecessor (preheader), i.e. it is live at 2036. An attempt is made to extend L0002 to 2036 and it fails with an assertion:

llc: /w/src/llvm.m/lib/CodeGen/LiveRangeCalc.cpp:226: void llvm::LiveRangeCalc::updateFromLiveIns(): Assertion `I.Value && "No live-in value found"' failed.

The original live interval:

%vreg458 [100r,2092B:0)[2092B,2100r:1)[3788r,3872r:2)[3872r,3920B:3)[3920B,4160B:2)[4176B,8048B:3)[8064B,9256B:3)  0@100r 1@2092B-phi 2@3788r 3@3872r   L00000001 [100r,2092B:1)[2092B,2100r:2)[3788r,4160B:0)[4176B,8048B:0)[8064B,9256B:0)  0@3788r 1@100r 2@2092B-phi   L00000002 [2092B,2100r:2)[3788r,3788d:0)[3872r,3920B:1)[4176B,8048B:1)[8064B,9256B:1)  0@3788r 1@3872r 2@2092B-phi

[kparzysz]

Ping.

lib/CodeGen/LiveIntervalAnalysis.cpp

369

This should be make_pair(Stop, PVNI) to avoid warnings about unused variable in non-assert builds.

[kparzysz]

Changed VNI to PVNI to avoid warnings about unused variable in release builds (VNI and PVNI are equal at that point).

Updated the summary and title.

[MatzeB]

• extendToUses(): This is a very similar algorithm than LiveRangeCalc::extend(), the difference is just that we can reuse the existing value numbers (and hence phi insertion points). Given that it is mostly the same I would expect this to require the same handling with an Undef array and using the extend(..., undef) variant as LiveRangeCalc.

• The extendPHIRange change looks fine. I did not check but I assume it is fine to wait with updating the main liverange because constructMainRangeFromSubranges() will be called anyway? So the SplitKit pieces are "LGTM" and could be put into a separate patch.

[kparzysz]

Committed the SplitKit changes in r287571.

[kparzysz]

Changed shrinkToUses to use LiveRangeCalc for extending live ranges instead of having a local helper function.

[kparzysz]

Ping.

[MatzeB]

Reusing more of the LiveRangeCalc code is a good plan. However with this version I am confused as to why there is any custom code in shrinkToUses left anyway. It seems like you create a completely new liverange anyway, copy all the VNI objects instead of reusing them, even dropping all the PHI-VNIs and let LiveRangeCalc recompute them. At that point it would probably be easier to simply drop the recompute the whole LiveInterval.

Can explain why reusing the existing VNI objects is not possible?

lib/CodeGen/LiveIntervalAnalysis.cpp

338–339

Shouldn't you rather stay with the old code that reuses the existing VNInfo objects instead of creating new ones? It's also not clear to me whether the old ones ever get invalidated in this version.

[kparzysz]

In D26359#616745, @MatzeB wrote:

Can explain why reusing the existing VNI objects is not possible?

LiveRangeCalc cannot have pre-existing PHI defs in the live range (for reasons explained in the comment). When extending a range, it will allocate new VNInfo objects for the PHIs that it creates. This will cause the actual VNInfo pointers to differ between the old range and the freshly extended one. My understanding here is that shrinkToUses is expected to preserve those pointers, and at least for PHI values, this is impossible to do when using LiveRangeCalc. Because of that I wrote the "transferSegments" function that adjusts the old live range to match the extended one, while still using the original VNs from the old range.

I did some experiments with deleting certain segments (those starting at block boundaries) while keeping the VNInfo list, and then having LiveRangeCalc use these values when extending the range. The problem was that such a LiveRange object was then temporarily "invalid" (because of the missing segments for certain values), and I kept running into assertions failing because of that. What I didn't like about this approach was that it required changes in LiveRangeCalc to accommodate this unique mode of operation (in addition to simply allocating new VNs when needed), but it was the assertions that made me decide that this wasn't worth the effort. In the end I decided (as you observed) to simply create a new live range, extend it, and then map it back into the old one.

The pattern "traverse all register uses and collect slot indexes" does indeed appear in several places and can likely be reused. I actually thought about it, but I didn't want to make this patch too large. If you think it's a good idea, I can look into it.

[kparzysz]

We could use computeVirtRegInterval in shrinkToUses for a whole interval (I have tried that), however, there is no function that would calculate a sub-range on its own, so the operand traversal would still need to remain there.

[scott.linder]

I think I am running into the same bug. I do not have a reduced test case yet, because it appears the bug is triggered due to spilling in my case.

The "traverse all register uses and collect slot indexes" approach taken in LiveIntervals.cpp seems to handle subregisters significantly differently than in LiveRangeCalc.cpp. In the case I am hitting, the assert assert(OldRange.getVNInfoBefore(Stop) == VNI && "Wrong value out of predecessor"); in extendSegmentsToUses fails for a SubRange even when not dominated by undef (i.e. LR.extendInBlock(Undefs, ...) returns (nullptr, false)). It seems like the slot index should not have been added to the Worklist for that SubRange to begin with, but even if I update the "traverse all register uses" loop to match LiveRangeCalc it fails.

I'm still new to the code, but I would like to work on this. Can I ask for some guidance on where the current patch needs work?

[kparzysz]

I'm not sure if this patch needs any more work, it worked fine when I posted it (at least in my tests). Since it's been a while ago, it would be worthwhile to make sure that it still does. It's unfortunate that I didn't have a testcase to illustrate the problem I mentioned in the description, I'm wondering if it would still fail.

Your scenario seems like a problem of a different nature. This patch is trying to fix cases of valid situations not being handled correctly, in your case the situation seems wrong to begin with: every use (except undef uses) must be jointly dominated by the union of explicit defs and undefs. Trying to extend a range to an index outside of that joint dominance it an error, and this patch is not intended to deal with this.

Please check in detail how the problem happens: try to narrow down the area in the live interval code where a correct liveness information somehow becomes incorrect (or is interpreted incorrectly). That is critical to developing a proper fix.

[scott.linder]

Here is the simplified LIS in my case just before the assert. The failing SubRange is %8273.L00000001 which I believe is %8273.sub0

If I understand this correctly, LIS claims %8273.sub0 is live-in bb.4 due to the SPILL, and live-out bb.0 due to the undef, but for some reason is not live-through bb.2/bb.3

SubRange0.getVNInfoBefore(bb.4) then returns the correct VNInfo for bb.0, but returns nullptr for bb.3 and we hit the assert.

Is my understanding correct? If so, I can try to identify why L00000001 does not have live-through segments for bb.2 and bb.3

********** INTERVALS **********
%8273 [336r,368r:0)[368r,1872B:1)[5760r,6360B:2)[10000r,11040B:3)[11040B,13560B:4)[13560B,13584r:5)  0@336r 1@368r 2@5760r 3@10000r 4@11040B-phi 5@13560B-phi L00000002 [368r,1872B:0)[5760r,6360B:3)[10000r,11040B:4)[11040B,13560B:5)[13560B,13576r:2)  0@368r 1@x 2@13560B-phi 3@5760r 4@10000r 5@11040B-phi L00000001 [336r,1872B:0)[13560B,13584r:0)  0@336r weight:1.116891e-03
RegMasks: 128r
********** MACHINEINSTRS **********
# Machine code for function quux: NoPHIs, TracksLiveness
0B	bb.0.bb:
	  successors: %bb.1(0x40000000), %bb.4(0x40000000); %bb.1(50.00%), %bb.4(50.00%)

336B	  undef %8273.sub0:vreg_64 = V_MUL_LO_I32 %4451.sub0:vreg_64, %350:sreg_32_xm0, implicit $exec
368B	  %8273.sub1:vreg_64 = V_MOV_B32_e32 0, implicit $exec
416B	  %4457:vreg_64 = V_LSHLREV_B64 4, %8273:vreg_64, implicit $exec
1760B	  %7986:vgpr_32 = COPY %8273.sub1:vreg_64

1872B	bb.1.bb30:
	; predecessors: %bb.0
	  successors: %bb.2(0x40000000), %bb.3(0x40000000); %bb.2(50.00%), %bb.3(50.00%)

5760B	  undef %8273.sub1:vreg_64 = V_MOV_B32_e32 0, implicit $exec
10000B	  undef %8273.sub1:vreg_64 = V_MOV_B32_e32 -1, implicit $exec

6360B	bb.2.bb99:
	; predecessors: %bb.1
	  successors: %bb.3(0x80000000); %bb.3(200.00%)

11040B	bb.3.Flow308:
	; predecessors: %bb.1, %bb.2
	  successors: %bb.4(0x80000000); %bb.4(200.00%)

13560B	bb.4.bb195:
	; predecessors: %bb.0, %bb.3
	  successors: %bb.5(0x40000000), %bb.6(0x40000000); %bb.5(50.00%), %bb.6(50.00%)

13576B	  SI_SPILL_V64_SAVE %8273:vreg_64, %stack.26, $sgpr0_sgpr1_sgpr2_sgpr3, $sgpr101, 0, implicit $exec :: (store 8 into %stack.26, align 4, addrspace 5)

26508B	bb.5.bb652:
	; predecessors: %bb.4
	  successors: %bb.6(0x80000000); %bb.6(200.00%)

30848B	bb.6.bb733:
	; predecessors: %bb.4, %bb.5
	  successors: %bb.9(0x40000000), %bb.7(0x40000000); %bb.9(50.00%), %bb.7(50.00%)

30872B	  %8274:vreg_64 = SI_SPILL_V64_RESTORE %stack.26, $sgpr0_sgpr1_sgpr2_sgpr3, $sgpr101, 0, implicit $exec :: (load 8 from %stack.26, align 4, addrspace 5)

31472B	bb.7.Flow:
	; predecessors: %bb.6, %bb.9
	  successors: %bb.8(0x40000000), %bb.10(0x40000000); %bb.8(50.00%), %bb.10(50.00%)

31568B	bb.8.bb767:
	; predecessors: %bb.7
	  successors: %bb.10(0x80000000); %bb.10(200.00%)

31600B	bb.9.bb768:
	; predecessors: %bb.6
	  successors: %bb.7(0x80000000); %bb.7(200.00%)

60988B	bb.10.UnifiedUnreachableBlock:
	; predecessors: %bb.7, %bb.8


# End machine code for function quux.

[kparzysz]

I'm assuming that the line 10000B was misplaced in the snippet above, and should be in bb.2.

The subrange with the mask L00000001 corresponds to sub0. %8273.sub0 is assigned a value at 336r, which is then reached in bb.4 by the spill at 13576r. Blocks bb.2 and bb.3 both have instructions of form undef %8273.sub1:vreg_64 = ..., which defines %8273.sub1, while simultaneously undefining all other subregisters of %8273. Therefore, sub0 has a def at 336r, and an undef at 5760r and at 10000r. If there are no other uses of %8273.sub0 in bb.2 or bb.3, then it won't be live in those blocks, because its liveness is terminated by these undefs.

[scott.linder]

Yes, I had misplaced 10000B.

Thank you for the explanation. I did not understand the undef register flag. Is there somewhere I can read more about MIR, or is the code the best place? https://llvm.org/docs/MIRLangRef.html is currently a little short on specifics.

I think my case is exactly the one described in https://reviews.llvm.org/D48555 as the subregister is not live-out of bb.3, but it is jointly dominated by undef. After applying that patch the assert goes away.

[kparzysz]

In D26359#1147318, @scott.linder wrote:

I did not understand the undef register flag. Is there somewhere I can read more about MIR, or is the code the best place? https://llvm.org/docs/MIRLangRef.html is currently a little short on specifics.

There are some comments in include/llvm/CodeGen/MachineOperand.h that explain what different flags mean, for example:

/// IsUndef - True if this register operand reads an "undef" value, i.e. the
/// read value doesn't matter.  This flag can be set on both use and def
/// operands.  On a sub-register def operand, it refers to the part of the
/// register that isn't written.  On a full-register def operand, it is a
/// noop.  See readsReg().
///
/// This is only valid on registers.
///
/// Note that an instruction may have multiple <undef> operands referring to
/// the same register.  In that case, the instruction may depend on those
/// operands reading the same dont-care value.  For example:
///
///   %1 = XOR undef %2, undef %2
///
/// Any register can be used for %2, and its value doesn't matter, but
/// the two operands must be the same register.
///
unsigned IsUndef : 1;

The MIRLangRef is really a documentation of the MIR format, not of the contents. MIR is YAML-based and was introduced to print machine functions in such a way that the output can be read back in and the machine function reconstructed from it. Before that the printing code would dump the info in a fairly intuitive way, but the format was not defined anywhere and we had no way to parse it.

What I would suggest is that if you see something unfamiliar in the output, check the printing code to see where it gets it from (what data structures, etc.), and then check the source code that defines that data to see if there are any explanations in the comments. The most commonly used structures are typically documented.

lib/CodeGen/LiveIntervalAnalysis.cpp

void LiveIntervals::computeLiveInRegUnits() {
   for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) {
     unsigned Unit = NewRanges[i];
     computeRegUnitRange(*RegUnitRanges[Unit], Unit);
   }
 }
 
 
 static void createSegmentsForValues(LiveRange &LR,
-      iterator_range<LiveInterval::vni_iterator> VNIs) {
+      iterator_range<LiveInterval::vni_iterator> VNIs,
+      VNInfo::Allocator &VNA) {
   for (auto VNI : VNIs) {
-    if (VNI->isUnused())
-      continue;
-    SlotIndex Def = VNI->def;
-    LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
+    if (!VNI->isUnused() && !VNI->isPHIDef())
+      LR.createDeadDef(VNI->def, VNA);
   }
 }
 
-typedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList;
-
-static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
-                                 ShrinkToUsesWorkList &WorkList,
-                                 const LiveRange &OldRange) {
-  // Keep track of the PHIs that are in use.
-  SmallPtrSet<VNInfo*, 8> UsedPHIs;
-  // Blocks that have already been added to WorkList as live-out.
-  SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
 
-  // Extend intervals to reach all uses in WorkList.
-  while (!WorkList.empty()) {
-    SlotIndex Idx = WorkList.back().first;
-    VNInfo *VNI = WorkList.back().second;
-    WorkList.pop_back();
-    const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
-    SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
-
-    // Extend the live range for VNI to be live at Idx.
-    if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
-      assert(ExtVNI == VNI && "Unexpected existing value number");
-      (void)ExtVNI;
-      // Is this a PHIDef we haven't seen before?
-      if (!VNI->isPHIDef() || VNI->def != BlockStart ||
-          !UsedPHIs.insert(VNI).second)
-        continue;
-      // The PHI is live, make sure the predecessors are live-out.
-      for (auto &Pred : MBB->predecessors()) {
-        if (!LiveOut.insert(Pred).second)
-          continue;
-        SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
-        // A predecessor is not required to have a live-out value for a PHI.
-        if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
-          WorkList.push_back(std::make_pair(Stop, PVNI));
-      }
-      continue;
-    }
+/// Update segments in DstLR to match segments from SrcLR while preserving
+/// value numbers in DstLR.
+/// Return true if any PHI-defined value has become unused.
+static bool transferSegments(LiveRange &DstLR, LiveRange &SrcLR) {
+  BitVector UsedVNs(DstLR.valnos.size());
+  std::map<SlotIndex,VNInfo*> VMap;
+  for (VNInfo *V : make_range(DstLR.vni_begin(), DstLR.vni_end()))
+    if (!V->isUnused())
+      VMap.insert(std::make_pair(V->def, V));
+
+  // Iterate over all segments in DstLR. If the corresponding segment exists
+  // in SrcLR, copy over the end-point, otherwise mark the segment as dead.
+  LiveRange::iterator SI = SrcLR.begin(), SE = SrcLR.end();
+  for (auto DI = DstLR.begin(), DE = DstLR.end(); DI != DE || SI != SE; ) {
+    if (SI == SE || (DI != DE && DI->start < SI->start)) {
+      // If we reached the end of SrcLR, or if DI points to a segment that
+      // is missing in SrcLR, remove it from DstLR.
+      assert(DI->start.isBlock());
+      DI = DstLR.removeSegment(DI);
+      DE = DstLR.end();
+      continue;
+    }
+    if (DI == DE || DI->start > SI->start) {
+      // If we reached the end of DstLR, or SI points to a segment that is
+      // missing in DstLR, insert it into DstLR.
+      SlotIndex SD = SI->valno->def;
+      DI = DstLR.addSegment(LiveRange::Segment(SI->start, SI->end, VMap[SD]));
+      DE = DstLR.end();
+    } else {
+      // Found a matching segment in both ranges, update DstLR.
+      assert(DI != DE && DI->start == SI->start);
+      DI->end = SI->end;
+    UsedVNs.set(DI->valno->id);
+    ++SI;
+    ++DI;
 
-    // VNI is live-in to MBB.
-    DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
-    LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
-
-    // Make sure VNI is live-out from the predecessors.
-    for (auto &Pred : MBB->predecessors()) {
-      if (!LiveOut.insert(Pred).second)
-        continue;
-      SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
-      assert(OldRange.getVNInfoBefore(Stop) == VNI &&
-             "Wrong value out of predecessor");
-      WorkList.push_back(std::make_pair(Stop, VNI));
-    }
+  bool Removed = false;
+  for (VNInfo *V : make_range(DstLR.vni_begin(), DstLR.vni_end())) {
+    if (V->isUnused() || UsedVNs.test(V->id))
+    if (V->isPHIDef())
+      Removed = true;
+    V->markUnused();
   }
+
+  return Removed;
 }
 
+
 bool LiveIntervals::shrinkToUses(LiveInterval *li,
                                  SmallVectorImpl<MachineInstr*> *dead) {
   DEBUG(dbgs() << "Shrink: " << *li << '\n');
   assert(TargetRegisterInfo::isVirtualRegister(li->reg)
          && "Can only shrink virtual registers");
 
   // Shrink subregister live ranges.
   bool NeedsCleanup = false;
   for (LiveInterval::SubRange &S : li->subranges()) {
     shrinkToUses(S, li->reg);
     if (S.empty())
       NeedsCleanup = true;
   }
   if (NeedsCleanup)
     li->removeEmptySubRanges();
 
-  // Find all the values used, including PHI kills.
-  ShrinkToUsesWorkList WorkList;
+  // Create new live ranges with only minimal live segments per def.
+  //
+  // Use LiveRangeCalc to extend the live range NewLR to all uses.
+  // This requires that NewLR does not have any non-register defs.
+  // In particular, NewLR should not have any PHI defs. The reason is
+  // that such defs would prevent the originating register defs from
+  // being extended, since they may only reach the PHI defs.
+  // LiveRangeCalc assumes that it is the only creator of PHI defs in
+  // the given range.
+  // The catch is, however, that any value number added by LRC may
+  // no longer match its counterpart from li. To make sure that the
+  // value numbers in li remain unchanged, the segments from NewLR
+  // will be copied back into li, while preserving the value number
+  // information.
+  LiveRange NewLR;
+  createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()),
+                          getVNInfoAllocator());
+  LiveRangeCalc LRC;
+  LRC.reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
+  // Main range does not need undefs.
+  const SmallVector<SlotIndex,0> NoUndefs;
 
   // Visit all instructions reading li->reg.
   for (MachineRegisterInfo::reg_instr_iterator
        I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end();
        I != E; ) {
     MachineInstr *UseMI = &*(I++);
     if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
       continue;
if (!VNI) {
                     << *li << '\n');
       continue;
     }
     // Special case: An early-clobber tied operand reads and writes the
     // register one slot early.
     if (VNInfo *DefVNI = LRQ.valueDefined())
       Idx = DefVNI->def;
 
-    WorkList.push_back(std::make_pair(Idx, VNI));
+    LRC.extend(NewLR, Idx, 0, NoUndefs);
   }
 
-  // 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);
-
-  // Move the trimmed segments back.
-  li->segments.swap(NewLR.segments);
+  // Move the trimmed segments back, preserving the value numbers.
+  bool CanSeparate = transferSegments(*li, NewLR);
 
   // Handle dead values.
-  bool CanSeparate = computeDeadValues(*li, dead);
+  CanSeparate |= computeDeadValues(*li, dead);
   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
   return CanSeparate;
 }
 
 bool LiveIntervals::computeDeadValues(LiveInterval &LI,
                                       SmallVectorImpl<MachineInstr*> *dead) {
   bool MayHaveSplitComponents = false;
   for (auto VNI : LI.valnos) {
bool LiveIntervals::computeDeadValues(LiveInterval &LI,
   }
   return MayHaveSplitComponents;
 }
 
 void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
   DEBUG(dbgs() << "Shrink: " << SR << '\n');
   assert(TargetRegisterInfo::isVirtualRegister(Reg)
          && "Can only shrink virtual registers");
+
+  LiveInterval &LI = getInterval(Reg);
+  SmallVector<SlotIndex,4> Undefs;
+  LI.computeSubRangeUndefs(Undefs, SR.LaneMask, *MRI, *getSlotIndexes());
+
   // Find all the values used, including PHI kills.
-  ShrinkToUsesWorkList WorkList;
+  LiveRange NewLR;
+  createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()),
+                          getVNInfoAllocator());
+  LiveRangeCalc LRC;
+  LRC.reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
 
   // Visit all instructions reading Reg.
   SlotIndex LastIdx;
   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
     // Skip "undef" uses.
     if (!MO.readsReg())
       continue;
     // Maybe the operand is for a subregister we don't care about.
for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
     if (!VNI)
       continue;
 
     // Special case: An early-clobber tied operand reads and writes the
     // register one slot early.
     if (VNInfo *DefVNI = LRQ.valueDefined())
       Idx = DefVNI->def;
 
-    WorkList.push_back(std::make_pair(Idx, VNI));
+    LRC.extend(NewLR, Idx, 0, Undefs);
   }
 
-  // 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);
-
-  // Move the trimmed ranges back.
-  SR.segments.swap(NewLR.segments);
+  // Move the trimmed ranges back, preserving the value numbers.
+  transferSegments(SR, NewLR);
 
   // Remove dead PHI value numbers
   for (auto VNI : SR.valnos) {
     if (VNI->isUnused())
       continue;
     const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
     assert(Segment != nullptr && "Missing segment for VNI");
     if (Segment->end != VNI->def.getDeadSlot())