Create subranges for new intervals resulting from live interval splitting

[kparzysz]

Summary

The register allocator can split a live interval of a register into a set of smaller intervals. After the allocation of registers is complete, the rewriter will modify the IR to replace virtual registers with the corresponding physical registers. At this stage, if a register corresponding to a subregister of a virtual register is used, the rewriter will check if that subregister is undefined, and if so, it will add the <undef> flag to the machine operand. The function verifying liveness of the subregister would assume that it is undefined, unless any of the subranges of the live interval proves otherwise.

The problem is that the live intervals created during splitting do not have any subranges, even if the original parent interval did. This could result in the <undef> flag placed on a register that is actually defined.

[qcolombet]

Hi Krzysztof,

Looks mostly good to me, I do not think the assert I’ve pointed out is correct though.

Cheers,
-Quentin

lib/CodeGen/SplitKit.cpp

1206

Change the name to SubLRC

lib/CodeGen/VirtRegMap.cpp

340

I believe the assertion should be on SubRegIdx != 0, because hasSubRanges is only populated when we have sub register liveness enabled.

[kparzysz]

lib/CodeGen/VirtRegMap.cpp

340

This function is only called when the subregister liveness is enabled, and when MO has a non-zero subregister (line 399 below).

[kparzysz]

I have another patch coming---this one has a bug: forcing should be set for intervals with subranges even when the value id is defined for the first time. Otherwise, if a value id has only one definition, but the same register has other values with subranges, the subrange information will not be updated correctly for that particular value id (since it will be blitted in transferValues, which does not handle subranges).

Testing it now, should have it ready tomorrow morning.

[kparzysz]

The update in this patch is the complete handling of subregister live ranges (subranges of the main live interval) in live range splitting. The live range extension code has been changed to allow extending to points where the live range is not reached by any def: doing so has no effect, but it allow speculative extensions for subranges, whose liveness is not known at the moment.

The splitting code will only create and maintain liveness for subranges (for registers that have those). The main range will be constructed after subrange updates are complete.

If a new live range is created for a part of the original live range where only a part of the original register was defined, the new range will still have a "full size" register associated with it. Since the boundary of the new live range will involve a copy or a spill of the whole register (which was only partially defined), if the new range was contained in a loop, the subrange information for the undefined parts will now contain instructions which were not included in the original live range. Necessary changes were made to deal with such situations.

The treatment of "undef" subregister definitions was updated to preserve liveness of the super-register: previously a <def,read-undef>of a subregister would be considered a "non-reading" def of the super-register. If another subregister was defined prior to such a def and was live across it, this liveness would not be reflected in the super-register's live range.

[MatzeB]

In D21189#463775, @kparzysz wrote:

The update in this patch is the complete handling of subregister live ranges (subranges of the main live interval) in live range splitting. The live range extension code has been changed to allow extending to points where the live range is not reached by any def: doing so has no effect, but it allow speculative extensions for subranges, whose liveness is not known at the moment.

The splitting code will only create and maintain liveness for subranges (for registers that have those). The main range will be constructed after subrange updates are complete.

If a new live range is created for a part of the original live range where only a part of the original register was defined, the new range will still have a "full size" register associated with it. Since the boundary of the new live range will involve a copy or a spill of the whole register (which was only partially defined), if the new range was contained in a loop, the subrange information for the undefined parts will now contain instructions which were not included in the original live range. Necessary changes were made to deal with such situations.

The treatment of "undef" subregister definitions was updated to preserve liveness of the super-register: previously a <def,read-undef>of a subregister would be considered a "non-reading" def of the super-register. If another subregister was defined prior to such a def and was live across it, this liveness would not be reflected in the super-register's live range.

I haven't looked at the actual patch yet, but this last paragraph sounds wrong to me. A <def,read-undef> does indeed not read the super register, this is exactly why we add the read-undef flag!

[kparzysz]

In D21189#463791, @MatzeB wrote:

I haven't looked at the actual patch yet, but this last paragraph sounds wrong to me. A <def,read-undef> does indeed not read the super register, this is exactly why we add the read-undef flag!

Consider this case:

100 vreg1:sub0<def,read-undef> = ...
108 ...
116 vreg1:sub1<def,read-undef> = ...
124 ...
132 ... = vreg1<kill>

The live range for sub0 will be [100,132), the live range for sub1 will be [116,132). Now, when the live range for the main register is constructed, we first see the def at 100 and create a dead def: [100,100d). Then a def at 116 is seen, and we add [116,116d) for it, finally there is a use at 132, so we extend the range [100r,100d)[116r,116d) to 132. The problem is that the def at 116 does not read vreg1, so the def at 100 will not be extended to 132.

[MatzeB]

In D21189#464458, @kparzysz wrote:

In D21189#463791, @MatzeB wrote:

I haven't looked at the actual patch yet, but this last paragraph sounds wrong to me. A <def,read-undef> does indeed not read the super register, this is exactly why we add the read-undef flag!

Consider this case:

100 vreg1:sub0<def,read-undef> = ...
108 ...
116 vreg1:sub1<def,read-undef> = ...
124 ...
132 ... = vreg1<kill>

The live range for sub0 will be [100,132), the live range for sub1 will be [116,132). Now, when the live range for the main register is constructed, we first see the def at 100 and create a dead def: [100,100d). Then a def at 116 is seen, and we add [116,116d) for it, finally there is a use at 132, so we extend the range [100r,100d)[116r,116d) to 132. The problem is that the def at 116 does not read vreg1, so the def at 100 will not be extended to 132.

In this situation the sub0 def at 100 does NOT live until the 132. That would only be the case if the 116 def does not have the read-undef flag set.

The motivation for this behavior is the situation when subregisters are not tracked individually. In this scheme subregister defs look like a read+write. And a typical problematic situation would be this:

100 %vreg0:sub0 = ...
110 %vreg0:sub1 = ...
120     use %vreg0
 ... (no use of vreg0 here)
800 %vreg0:sub0 = ...
810 %vreg0:sub1 = ...
820.   use %vreg0

In this example you do not want vreg0 to be alive between 120 and 800. So you have to make sure the def at 800 does not look like a use, so we add the read-undef flag. (see also the comment in MachineOperand::readsReg()/IsUndef).

[kparzysz]

A read-undef flag on a def of sub0 does not have any implications about the liveness of sub1. Otherwise, a sub0<def,read-undef> would need to be reflected in the live range of sub1, or else you wouldn't be able to extend it to its uses.

[kparzysz]

I have actually consulted with Quentin regarding the interpretation of read-undef. I'd like to see his input in this review.

[MatzeB]

In D21189#465028, @kparzysz wrote:

A read-undef flag on a def of sub0 does not have any implications about the liveness of sub1. Otherwise, a sub0<def,read-undef> would need to be reflected in the live range of sub1, or else you wouldn't be able to extend it to its uses.

No no no: On a def for sub0 the read-undef flag is exactly about the liveness of the other subregs like sub1

[qcolombet]

Hi Krzystof,

[kparzysz]

With this interpretation of <def,read-undef>, there is a problem in extending live ranges:

16 vreg0<def> = ...
24 ... = vreg0<kill>
...
64 vreg0:sub0<def,read-undef>
72 ... = vreg0

Suppose that vreg0 has two lanes: L1 and L2, corresponding to sub0 and sub1. When creating the live ranges, after the dead defs have been created, but before extending to uses, the live range for L2 will be simply [16r,16d). There will be no indication in there that the value defined at 16 should not be extended to the use at 72.

What I'm considering is to treat <def,read-undef> of a lane as if it was an IMPLICIT_DEF of all other lanes. In other words, a <def,read-undef> would add a def to all subranges, not only the one corresponding to the specified subregister. In the example above, the live range for L2 will be [16r,16d)[64r,64d). Now, that will prevent the def at 16 from reaching the use at 72. Instead, the def at 64r will reach it (in the same fashion as a def produced by an IMPLICIT_DEF would).

What are your thoughts about it? There are a few places in the code that will need to be made aware of this (register coalescer is one of them). Do you have any other suggestions?

[MatzeB]

In D21189#466407, @kparzysz wrote:

With this interpretation of <def,read-undef>, there is a problem in extending live ranges:

16 vreg0<def> = ...
24 ... = vreg0<kill>
...
64 vreg0:sub0<def,read-undef>
72 ... = vreg0

Suppose that vreg0 has two lanes: L1 and L2, corresponding to sub0 and sub1. When creating the live ranges, after the dead defs have been created, but before extending to uses, the live range for L2 will be simply [16r,16d). There will be no indication in there that the value defined at 16 should not be extended to the use at 72.

What I'm considering is to treat <def,read-undef> of a lane as if it was an IMPLICIT_DEF of all other lanes. In other words, a <def,read-undef> would add a def to all subranges, not only the one corresponding to the specified subregister. In the example above, the live range for L2 will be [16r,16d)[64r,64d). Now, that will prevent the def at 16 from reaching the use at 72. Instead, the def at 64r will reach it (in the same fashion as a def produced by an IMPLICIT_DEF would).

What are your thoughts about it? There are a few places in the code that will need to be made aware of this (register coalescer is one of them). Do you have any other suggestions?

I think I've been running in to the same problems before when working with subreg liveness. And so far I mostly dodged it by not trying to recompute liveness past the register coalescer. After coming fresh out of SSA form before the coalescer the live ranges are always simply enough that you cannot run into this problem.

Ideally we would have lane masks on every machine operand to specify which lanes are unused or dead. This would solve this recomputation problem cleanly (in your example above we would mark the L2 lane as unused). It would also simply and speedup RegisterOperands::adjustLaneLiveness() in RegisterPressure.cpp.
Unfortunately we would increase the size of the MachineOperands which from what I hear dominate the memory usage in the backend, so I am not sure if this solution is acceptable for the community.

Considering def,read-undef as an implicit-def would give us conservatively correct live ranges. However I fear that we will regress register allocation, they will block registers even when the value turns out never to be read. Maybe if we had a way to clean extra unused dead-defs...

[kparzysz]

In D21189#466694, @MatzeB wrote:

Maybe if we had a way to clean extra unused dead-defs...

I thought of having such defs (including those created by IMPLICIT_DEFs) as always dead in a live range, and have them be non-extendable. In other words, LiveRange would somehow know that a [64r,64d) is a definition that cannot be extended to any use.
That would require storing extra information inside LiveRange, or perhaps we could use a special (reserved) id for the value number?

[kparzysz]

In D21189#466695, @kparzysz wrote:

In D21189#466694, @MatzeB wrote:

Maybe if we had a way to clean extra unused dead-defs...

I thought of having such defs (including those created by IMPLICIT_DEFs) as always dead in a live range, and have them be non-extendable.

I may have misread your comment. You are saying that the existence of these defs (dead or not) can cause regressions in the register allocator? I don't think that the allocator can actually assign two different (unrelated) registers to sub-ranges of a single large virtual register, can it? There is a pass that would separate independent lanes, I guess that would help here: a read-undef could become an actual IMPLICIT_DEF, and then, if it's removable, it could be deleted completely.

[MatzeB]

In D21189#466695, @kparzysz wrote:

In D21189#466694, @MatzeB wrote:

Maybe if we had a way to clean extra unused dead-defs...

I thought of having such defs (including those created by IMPLICIT_DEFs) as always dead in a live range, and have them be non-extendable. In other words, LiveRange would somehow know that a [64r,64d) is a definition that cannot be extended to any use.
That would require storing extra information inside LiveRange, or perhaps we could use a special (reserved) id for the value number?

I am not sure what you mean by "non-extendable". But in each case even a dead def occupies a register at that point and will prohibit the allocator from letting other values live through that point.

The IMPLICIT_DEFs are slightly odd but are no problem for allocation, because they are only used at the end of a block in situations where the block jumps to a merge point after which the register is live anyway. So this only prohibits us from letting something live through the implicit def into the terminator instructions, we couldn't have anything live into the merge block anyway because the regiser is occupied (for real) there.
read-undef subregister defs on the other hand can happen anywhere in a block and will therefore block registers at a point where we may want to let other values live through.

If you use them as a tool for liveness calculation, then liveness calculation should also clean those up I think. We could indeed temporarily use the VNInfo id field or similar to mark those...

[MatzeB]

In D21189#466696, @kparzysz wrote:

In D21189#466695, @kparzysz wrote:

In D21189#466694, @MatzeB wrote:

Maybe if we had a way to clean extra unused dead-defs...

I thought of having such defs (including those created by IMPLICIT_DEFs) as always dead in a live range, and have them be non-extendable.

I may have misread your comment. You are saying that the existence of these defs (dead or not) can cause regressions in the register allocator? I don't think that the allocator can actually assign two different (unrelated) registers to sub-ranges of a single large virtual register, can it? There is a pass that would separate independent lanes, I guess that would help here: a read-undef could become an actual IMPLICIT_DEF, and then, if it's removable, it could be deleted completely.

If you ask about cases like this:

%vreg0  = ...
   use vreg0

%vreg1.sub1 = ...

use vreg0.sub0
use vreg1.sub1

The register allocator is able to use the same physical register for vreg1 and vreg1 here (as there is never a point where both have sub0 or sub1 live at the same time).

[MatzeB]

In D21189#466696, @kparzysz wrote:

In D21189#466695, @kparzysz wrote:

In D21189#466694, @MatzeB wrote:

Maybe if we had a way to clean extra unused dead-defs...

I thought of having such defs (including those created by IMPLICIT_DEFs) as always dead in a live range, and have them be non-extendable.

I may have misread your comment. You are saying that the existence of these defs (dead or not) can cause regressions in the register allocator? I don't think that the allocator can actually assign two different (unrelated) registers to sub-ranges of a single large virtual register, can it? There is a pass that would separate independent lanes, I guess that would help here: a read-undef could become an actual IMPLICIT_DEF, and then, if it's removable, it could be deleted completely.

Oh I just understood what you meant. No the register allocator will of course only assign a single physreg superregister to a vreg. Assigning independent physregs to different lanes is invalid in general (indeed the RenameIndependentSubRegs pass I added goes to great length to find the cases where it is legal and renamed the registers to give the regalloc more freedom).

Having dead-defs around will still negatively affect allocation because we may block the possibility to re-use an otherwise unused sublane for a different vreg (I hope I explained this better in my other comment).

[kparzysz]

In D21189#466699, @MatzeB wrote:

The register allocator is able to use the same physical register for vreg1 and vreg1 here (as there is never a point where both have sub0 or sub1 live at the same time).

What I meant by "non-extendable" defs are defs that always remain dead in the live range, even if the flow of the program indicates that they could reach some use (in the same block, or not). By keeping them that way, they would not occupy any additional space in the live range, so they could get redefined/reused in the "empty" space. They would only serve as a barrier preventing a prior def from reaching any subsequent use.

If the subranges were separated into individual virtual registers, the read-undef could become an IMPLICIT_DEF, at least temporarily, and it could be erased if possible.

I believe that taking advantage of the situation that you mention above can only happen via register coalescing, and it already has some knowledge about implicit defs and invalidated lanes. The code that joins live ranges could be extended to handle cases like that: a "non-extendable" dead def could be treated as a removable implicit-def (since the read-undef flag could be removed from the offending operand). Wouldn't this be sufficient to avoid regressions?

[MatzeB]

In D21189#466724, @kparzysz wrote:

In D21189#466699, @MatzeB wrote:

The register allocator is able to use the same physical register for vreg1 and vreg1 here (as there is never a point where both have sub0 or sub1 live at the same time).

What I meant by "non-extendable" defs are defs that always remain dead in the live range, even if the flow of the program indicates that they could reach some use (in the same block, or not). By keeping them that way, they would not occupy any additional space in the live range, so they could get redefined/reused in the "empty" space. They would only serve as a barrier preventing a prior def from reaching any subsequent use.

If the subranges were separated into individual virtual registers, the read-undef could become an IMPLICIT_DEF, at least temporarily, and it could be erased if possible.

I believe that taking advantage of the situation that you mention above can only happen via register coalescing, and it already has some knowledge about implicit defs and invalidated lanes. The code that joins live ranges could be extended to handle cases like that: a "non-extendable" dead def could be treated as a removable implicit-def (since the read-undef flag could be removed from the offending operand). Wouldn't this be sufficient to avoid regressions?

I am thinking of this:

10.  vreg1.sub1<read-undef> = ...
20.  vreg0.sub0<read-undef> = ...
30.    use vreg1.sub1
 ...
100.   use vreg0.sub0

We would like the allocator to be able to assing the same physical (super) register to vreg0 and vreg1. However if we put a dead-def for vreg0.sub1 at 20 then the register allocator will see an interference with vreg1(.sub1) and will assign a different register to vreg1.

[kparzysz]

Updated the patch to reflect the "undefining" interpretation of <def,read-undef>. The code related to subrange creation in live range splitting remains unchanged. The differences are in how live ranges (specifically subranges) are extended.

The main problem to overcome was that a LiveRange that is a subrange of a LiveInterval did not contain any information about locations of <def,read-undef> for non-overlapping subranges, even though they do affect liveness of the subrange. Specifically, <def,read-undef> of sub0 does undefine sub1 (assuming sub0 and sub1 do not overlap), but the LiveRange of sub1 would not contain any information about that. This lead to difficulties in extending the LiveRange of sub1, since by analyzing that LiveRange alone, it could be extended across a <def,read-undef> for sub0, causing inconsistency between the code (i.e. operand flags) and the calculated live ranges.

The solution is to add a list of such explicit "undefinition points" to each subrange. A <def,read-undef> of sub0 at Idx would cause Idx to be added to "undefs" list for all non-overlapping subranges. Later on, when extending the live range for sub1, these "undefs" will prevent any def in that range from reaching any use across such an "undefinition point". The "undef" information is only used for extending live ranges and does not interfere with any other analyses, including checking live ranges for overlapping. Code that manipulated live intervals directly needs to be amended to update the "undef" information in the live ranges, since such manipulation can render the "undef" information invalid. A member function in LiveInterval was introduced to recalculate the "undef" data.

This patch passes our internal correctness tests (on Hexagon, with subregister liveness tracking enabled). Please consider it a proof-of-concept (which may be close to the final version)---I plan to review the LLVM code to see if any other places need updating to reflect the changes before committing.

[kparzysz]

Ping.

[MatzeB]

First: This is a tough problem to solve (nicely), so thanks for pushing!

• I am not happy with extending the core datatype (LiveRange) with an undef list (see below).

• I am also not happy that we just start searching around in the isDefOnEntry() function; Is it realistic to create fake LiveRange Segments (with the Undef VNInfo) and clean them up afterwards?

include/llvm/CodeGen/LiveInterval.h

199

I think LiveRange objects are one of the larger memory consumers in codegen. I think we should try hard to not add any members to it. Would it work to create special VNInfo objects during liverange construction (for example set id = (unsigned)-1 for Undefs)? I think we could restrict those special VNInfos to be only valid during liverange construction and undefined otherwise so we do not need to modify all the functions here to support them, but can restrict ourself to the functions used by LiveRangeCalc.

lib/CodeGen/LiveIntervalAnalysis.cpp

511–512

We should override the print() and dump() functions in the SubRange class instead. We can leave that for another patch though.

There are a bunch of slightly unrelated but obvious changes here like this one, the check for readsReg() or the move of the DEBUG print at the end of the function. Would be nice if you could split those into a separate commit (no need to review such obvious changes).

526

The MO.isUndef() case cannot happen after you checked MO.readsReg() above.

585

Use /*PhysReg=*/0 to make it clear what the zero is about.

1556–1557

This can only be the case during LiveRangCalc, do we really need to handle this case?

lib/CodeGen/LiveRangeCalc.cpp

299

Adding a worklist algorithm adds a dangerous quadratic runtime here (esp. since the results for negative answers are not cached).

lib/CodeGen/RenameIndependentSubregs.cpp

381–385

This is odd, why do we need to redo shrinkToUses()? Can you give an example or an detailed explanation, the comment isn't clear to me right now.

lib/CodeGen/SplitKit.cpp

395

Maybe we should factor this line out and add a convenience function to LiveRange that complements LiveRange::createDeadDef(), we just need a variant that takes a VNInfo as well.

407–408

This and the next one looks like LiveRange::createDeadDef() to me.

990

Isn't ParentVNI->id already unsigned?

[kparzysz]

Regarding the "shrinkToUses" in RenameIndependentSubregs.cpp, here's the failing testcase (a lit test from AMDGPU): vreg12 is the subject to optimization here.

# *** IR Dump Before Rename Disconnected Subregister Components ***:
# Machine code for function insertelement_v3f32_1: Properties: <Post SSA, tracking liveness, HasVRegs>
Function Live Ins: %SGPR0_SGPR1 in %vreg0

0B      BB#0: derived from LLVM BB %0
            Live Ins: %SGPR0_SGPR1
16B             %vreg0<def> = COPY %SGPR0_SGPR1; SReg_64:%vreg0
32B             %vreg10:sub0_sub1<def,read-undef> = S_LOAD_DWORDX2_IMM %vreg0, 9; mem:LD8[undef(addrspace=2)](nontemporal)(invariant) SReg_128:%vreg10 SReg_64:%vreg0
48B             %vreg5<def> = S_LOAD_DWORDX4_IMM %vreg0, 13; mem:LD16[undef(addrspace=2)](nontemporal)(invariant) SReg_128:%vreg5 SReg_64:%vreg0
96B             %vreg10:sub3<def> = S_MOV_B32 61440; SReg_128:%vreg10
112B            %vreg10:sub2<def> = S_MOV_B32 -1; SReg_128:%vreg10
192B            %vreg20<def> = V_MOV_B32_e32 1084227584, %EXEC<imp-use>; VGPR_32:%vreg20
208B            %vreg12<def> = COPY %vreg5; VReg_128:%vreg12 SReg_128:%vreg5
224B            %vreg12:sub1<def> = COPY %vreg20<undef>; VReg_128:%vreg12 VGPR_32:%vreg20
256B            BUFFER_STORE_DWORD_OFFSET %vreg12:sub2, %vreg10, 0, 8, 0, 0, 0, %EXEC<imp-use>; mem:ST4[%out(addrspace=1)+8](align=8) VReg_128:%vreg12 SReg_128:%vreg10
320B            %vreg12:sub1<def> = COPY %vreg20; VReg_128:%vreg12 VGPR_32:%vreg20
336B            BUFFER_STORE_DWORDX2_OFFSET %vreg12:sub0_sub1, %vreg10, 0, 0, 0, 0, 0, %EXEC<imp-use>; mem:ST8[%out(addrspace=1)](align=16) VReg_128:%vreg12 SReg_128:%vreg10
352B            S_ENDPGM

# After Rename Disconnected Subregister Components
********** INTERVALS **********
SGPR0 [0B,16r:0)  0@0B-phi
SGPR1 [0B,16r:0)  0@0B-phi
%vreg0 [16r,48r:0)  0@16r
%vreg5 [48r,208r:0)  0@48r
%vreg10 [32r,96r:0)[96r,112r:1)[112r,336r:2)  0@32r 1@96r 2@112r L00000001 [32r,336r:0)  0@32r L00000002 [32r,336r:0)  0@32r L00000004 [112r,336r:0)  0@112r  undef@32r,96r L00000008 [96r,336r:0)  0@96r  undef@32r
%vreg12 [208r,320r:0)[320r,336r:1)  0@208r 1@320r L00000001 [208r,336r:0)  0@208r L00000004 [208r,256r:0)  0@208r  undef@320r L00000002 [208r,208d:0)[320r,336r:1)  0@208r 1@320r L00000008 [208r,224r:0)  0@208r  undef@224r,320r
%vreg20 [192r,320r:0)  0@192r
%vreg24 [224r,224d:0)  0@224r L00000002 [224r,224d:0)  0@224r
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function insertelement_v3f32_1: Properties: <Post SSA, tracking liveness, HasVRegs>
Function Live Ins: %SGPR0_SGPR1 in %vreg0

0B      BB#0: derived from LLVM BB %0
            Live Ins: %SGPR0_SGPR1
16B             %vreg0<def> = COPY %SGPR0_SGPR1; SReg_64:%vreg0
32B             %vreg10:sub0_sub1<def,read-undef> = S_LOAD_DWORDX2_IMM %vreg0, 9; mem:LD8[undef(addrspace=2)](nontemporal)(invariant) SReg_128:%vreg10 SReg_64:%vreg0
48B             %vreg5<def> = S_LOAD_DWORDX4_IMM %vreg0, 13; mem:LD16[undef(addrspace=2)](nontemporal)(invariant) SReg_128:%vreg5 SReg_64:%vreg0
96B             %vreg10:sub3<def> = S_MOV_B32 61440; SReg_128:%vreg10
112B            %vreg10:sub2<def> = S_MOV_B32 -1; SReg_128:%vreg10
192B            %vreg20<def> = V_MOV_B32_e32 1084227584, %EXEC<imp-use>; VGPR_32:%vreg20
208B            %vreg12<def> = COPY %vreg5; VReg_128:%vreg12 SReg_128:%vreg5
224B            %vreg24:sub1<def,read-undef,dead> = COPY %vreg20<undef>; VReg_128:%vreg24 VGPR_32:%vreg20
256B            BUFFER_STORE_DWORD_OFFSET %vreg12:sub2, %vreg10, 0, 8, 0, 0, 0, %EXEC<imp-use>; mem:ST4[%out(addrspace=1)+8](align=8) VReg_128:%vreg12 SReg_128:%vreg10
320B            %vreg12:sub1<def> = COPY %vreg20; VReg_128:%vreg12 VGPR_32:%vreg20
336B            BUFFER_STORE_DWORDX2_OFFSET %vreg12:sub0_sub1, %vreg10, 0, 0, 0, 0, 0, %EXEC<imp-use>; mem:ST8[%out(addrspace=1)](align=16) VReg_128:%vreg12 SReg_128:%vreg10
352B            S_ENDPGM

# End machine code for function insertelement_v3f32_1.

*** Bad machine code: Instruction ending live segment doesn't read the register ***
- function:    insertelement_v3f32_1
- basic block: BB#0  (0x35d33a8) [0B;368B)
- instruction: 224B     %vreg24:sub1<def,read-undef,dead> = COPY
- liverange:   [208r,224r:0)  0@208r  undef@224r,320r
- register:    %vreg12
- lanemask:    00000008
- segment:     [208r,224r:0)
LLVM ERROR: Found 1 machine code errors.

lib/CodeGen/LiveIntervalAnalysis.cpp

1556–1557

This can also happen in SplitKit.cpp, in hoistCopies. In SplitKit, the subranges are created first, and the main ranges are created later on (in rewriteAssigned).

lib/CodeGen/RenameIndependentSubregs.cpp

381–385

Will add a top-level comment with a failing example.

lib/CodeGen/SplitKit.cpp

990

Yeah, this is a leftover from some previous approach.

[kparzysz]

In D21189#482034, @kparzysz wrote:

Regarding the "shrinkToUses" in RenameIndependentSubregs.cpp, here's the failing testcase (a lit test from AMDGPU): vreg12 is the subject to optimization here.

I should add that this happens with the patch as-is, except for the lines 384-385 commented out.

[kparzysz]

Regarding the list of "undefs":

The main problem here is that this information should be available even after the initial calculation of the live range. The main consumers of this data are the extending routines (e.g. LIS::extendToIndices). In the absence of the explicit list of "undefs", in some circumstances, they could extend the live range "too much", i.e. the range would cover code where the corresponding subregister is not live. Such a scenario could happen when live range splitting breaks a live range at a point where the register is only partially defined:

BB#123:
  ...
  %vreg0:sub0<def,read-undef> = ...
  ...
  %vreg0:sub1<def> = ...
  ...

Splitting of the range between the definitions of sub0 and sub1 could create this case:

BB#123:
  ...
  %vreg1:sub0<def,read-undef> = ...
  ...
  %vreg2<def> = COPY %vreg1   ; vreg1:sub1 is undefined
  %vreg2:sub1<def> = ...
  ...

At this point, an extension of the live range for vreg1:sub1 could include instructions between the sub0<def,read-undef> and the use of vreg1. (I'm writing this from memory---I don't have an example at hand that I could paste here.)

[kparzysz]

I just checked memory usage of live intervals on a fairly large customer application (without the patch): the maximum amount of memory consumed by live intervals was about 1MB for a function with around 9000 virtual registers. The average memory used was in the 6-7kB range. The total memory consumed by llc was ~2.8GB.
The measurement was done by calling mallinfo before and after freeing all live intervals in LiveIntervals::releaseMemory(), and taking the difference between the values uordblks+hblkhd.
This suggests to me that the memory consumed by live intervals is actually rather insignificant. What data do you have that show large memory usage?

[kparzysz]

Addressed inline comments. Added more caching in isDefOnEntry to reduce the run time.

[kparzysz]

Cache negative results in isDefOnEntry to reduce compile time.

Fix removing IMPLICIT_DEFs for sub-registers in register coalescer: adjust the main range appropriately, depending on the liveness of the subranges.

[kparzysz]

Ping.

lib/CodeGen/LiveRangeCalc.cpp

360

Oops. Will remove this shortly.

lib/CodeGen/SplitKit.cpp

1216

Oops. Will remove this shortly.

[kparzysz]

Removed leftover code. NFC.

[kparzysz]

lib/CodeGen/LiveRangeCalc.cpp

299

Added caching of negative results.

[kparzysz]

Make sure that the main range extension in register coalescer is only done when necessary.

[kparzysz]

This comment was removed by kparzysz.

[kparzysz]

Please disregard the previous comment with these statistics---I forgot to enable subregister liveness tracking in that experiment.

Regarding the complexity of isDefOnEntry, I have collected some statistics: between each time a LiveRangeCalc object is created/reset and reset/destroyed, I counted how many times each particular basic block is added to the work list. Then I divided that number by the number of distinct blocks that were added to the worklist. This would give an average number of visits for each block that has been visited.
For a customer code with over 20,000 functions, this code was executed 647 times (i.e. 647 times there was a lifespan of a LiveRangeCalc objects when at least one block was visited). The average visit count over all such lifespans was 1.19.

[kparzysz]

Recompute the main range for all new registers in the LiveRangeEdit object (in SplitKit.cpp). This accounts for unusual cases when a newly created register only has dead defs of its subregisters. The previous code would skip it, causing it to have an empty main range.

[kparzysz]

Avoid using the same DefOnEntry and UndefOnEntry bit vectors for different live ranges. SplitKit uses the same LiveRangeCalc object for multiple registers, so make sure that the bit vectors are kept separate.

All my correctness tests passed without this change, but I am not convinced that there is a logical reason that would justify not making it.

[kparzysz]

Ping.

[yakush]

lib/CodeGen/LiveRangeCalc.cpp

231

why LaneBitmask can be omitted in this call of ::extend?

232

does it handle partial register uses?

389

code assumes PhysReg here can't be sub-registers. if livein contains super-register and PhysReg is sub-register, it will fail?

[kparzysz]

lib/CodeGen/LiveRangeCalc.cpp

231

This calls LiveRangeCalc::extend, which does not take a LaneBitmask argument. It does not scan the code, it performs the extension based only on the LiveRange.

232

It does not have to be concerned about it. It takes a live range LR and a slot index Use, to which the LR needs to be extended. Whether the extension is the right thing to do should be checked by the caller.

389

The physical register liveness is handled a bit differently, and I haven't looked at that code in detail. At the first glance it appears as if this code could fail, but since it has never happened for me, I'm guessing that this case is taken care of somewhere else.

[yakush]

lib/CodeGen/LiveRangeCalc.cpp

231

however, findReachingDefs is invoked. it will use full Reg (phys) to report errors - even if LaneBitmask was specifying single sub-register.

389

can you suggest where to look? maybe i need to integrate some commits.
in fact, it fails for out of tree compiler (based on llvm 3.8), where we have scalar/vector registers and scalar/vector instructions with PhysReg side-effects annotations.

[kparzysz]

lib/CodeGen/LiveRangeCalc.cpp

231

Yes, but Reg is often 0, so the register printed in the error message is not always accurate anyways.

389

I'd look at LiveIntervalAnalysis.cpp.

[kparzysz]

Ping.

[MatzeB]

One thing that still worries me with this patch is that pruneUndefs() is sprinkled around in various LiveRange functions.

I am still worried about the undefs list in the LiveRange class. This is from a maintenance point of view: Are the pruneUndefs() calls necessary for correctness or are they just an optimization? I am not sure all the code uses addSegment()/append()/etc. At the very least there should be some documentation on what it does and when it needs to be called because, as that will not be obvious to people editing the code in the future.
Would it be possible to not save this information in the LiveInterval at all and instead recompute it on demand in the LiveRangeCalc only? That way these complications would be limited to that file. I may experiment with that later.

This should have simpler tests that make the problem obvious. I am currently experimenting with this (still needs some CHECK lines though; Feel free to convert to Hexagon, I was just used to AMDGCN from my previous .mir tests).

# RUN: llc -march=amdgcn -run-pass liveintervals -debug-only=regalloc -o /dev/null %s 2>&1 | FileCheck %s
# REQUIRES: asserts
--- |
  define void @test0() { ret void }
  define void @test1() { ret void }
...
---
name: test0
registers:
  - { id: 0, class: sreg_64 }
body: |
  bb.0:
    S_NOP 0, implicit-def %0
    S_NOP 0, implicit %0

    S_NOP 0, implicit-def undef %0.sub0
    S_NOP 0, implicit %0
...
---
name: test1
registers:
  - { id: 0, class: sreg_64 }
body: |
  bb.0:
    successors: %bb.1, %bb.2
    S_CBRANCH_VCCNZ %bb.1, implicit undef %vcc
    S_BRANCH %bb.2

  bb.1:
    successors: %bb.3
    S_NOP 0, implicit-def undef %0.sub0
    S_BRANCH %bb.3

  bb.2:
    successors: %bb.3
    S_NOP 0, implicit-def %0
    S_BRANCH %bb.3

  bb.3:
    S_NOP 0
    S_NOP 0, implicit %0
...

[MatzeB]

I played with the patch and hacked a rough prototype on how I imagine that we can contain the def-read-undef complexities more to the LRCalc class and not force people to maintain an extra undefs list inside every LiveRange object: https://reviews.llvm.org/D23484

[kparzysz]

Added a few of fixes:

1. Don't create "undef" defs that don't have subregisters. This did happened in the register coalescer in some cases. Matthias followup patch exposed that.
2. Update only the affected subranges after rematerializing an instruction in SplitKit. The previous assumption was that rematerialization will always generate a def of the entire register. That is not true.
3. Don't crash on missing ranges in extendPHIKillRanges.

This update will prepare this patch to work with Matthias's D23484.

[kparzysz]

Merged D23484 in.

[kparzysz]

lib/CodeGen/SplitKit.cpp

1127

This should be LI, not ParentLI.

[kparzysz]

Use LI instead of ParentLI in extendPHIKillRanges.

[kparzysz]

In D21189#514512, @MatzeB wrote:

This should have simpler tests that make the problem obvious. I am currently experimenting with this (still needs some CHECK lines though

This test crashes without the patch and compiles cleanly with it. Was that the intent? If so, why would it need CHECK lines, isn't the "REQUIRES: asserts" sufficient?

[kparzysz]

Added the AMD testcase with CHECK lines.

[MatzeB]

This is getting really close. I have no highlevel concerns anymore.

A bunch of smaller changes below (I realize that a number of them just clean up aspects of my "rough" patch).

I also tested the code on an important out-of-tree target with subregister usage here and it worked nicely (though admittedly you rarely see spill instructions there).

include/llvm/CodeGen/LiveInterval.h

461

This needs documentation. Probably most of the following function. (You can probably shorten the docu of the following function to something like "variant of extendInBlock() ... put undefs explanation here..."

612

this can be removed now.

include/llvm/CodeGen/LiveIntervalAnalysis.h

166–176

This should not talk about AllowUndef anymore

lib/CodeGen/LiveInterval.cpp

62–66

Use /// doxygen. Should explain what the function does or use \see LiveRange::createDeadDef.

516–519

this change appears unnecessary.

528–530

This duplicate comment should be removed, there is one in the header anyway (and this is not up to date anymore after this patch).

lib/CodeGen/LiveIntervalAnalysis.cpp

584

ArrayRef<SlotIndex> NoUndefs; should be slightly more efficient and a better name.

982–989

empty loop?

lib/CodeGen/LiveRangeCalc.cpp

61–72

this can probably be inlined again now that is only used once.

266

Should use LaneBitmask instead of unsigned.

lib/CodeGen/LiveRangeCalc.h

27

I believe llvm/ADT/ArrayRef.h is enough here.

126–132

This needs an update now that we have the Undefs list.

151–167

This needs an update a well.

199–200

Needs docu.

For a given lane compute indexes at which the lane is marked undefined by subregister (def-read-undef) definitions.

lib/CodeGen/RegisterCoalescer.cpp

978

This should go in an independent change (but this line LGTM so no need for an extra review).

2516–2523

Put this into a static toplevel function instead of a lambda. (This is the common llvm style, uses slightly more familiar syntax and I know how to set set a debugger breakpoint on a function).

2782–2783

remove stale comment.

lib/CodeGen/SplitKit.cpp

1071–1080

Pull this out into a static toplevel function.

1081–1126

dito.

1140–1145

this is only used once and could be inlined.

lib/CodeGen/SplitKit.h

328–331

Should prefix argument names with \p (or @p)

lib/CodeGen/TargetInstrInfo.cpp

381–385 ↗

(On Diff #68553)

This will fail if there is more than 1 definition or implicit definitions. It would probably be better to patch MachineOperand::substVirtReg() which in turn is used by MachineInstr::substituteRegister()

lib/Target/Hexagon/HexagonExpandCondsets.cpp

466

Should use LaneBitmask

467–481

This block appears to be the same as LiveRangeCalc::computeSubRangeUndefs(). We should find a way to share this code. Like adding a static variant of the function to LiveRangeCalc so you can call it independently of constructing a LiveRangeCalc instance.

test/CodeGen/Hexagon/regalloc-bad-undef.mir

69–72

test can be simplified by leaving the xxx: false things out as that is the default anyway.

[kparzysz]

include/llvm/CodeGen/LiveInterval.h

461

I documented the "complicated" version first, and then the simpler one after that.

lib/CodeGen/LiveIntervalAnalysis.cpp

584

/*Undefs=*/{} looks even prettier. :)

982–989

Leftover from something.

lib/Target/Hexagon/HexagonExpandCondsets.cpp

467–481

LiveRangeCalc is only available inside CodeGen. Maybe we can move the "computeSubRangeUndefs" to LiveInterval?

[MatzeB]

lib/Target/Hexagon/HexagonExpandCondsets.cpp

467–481

sure

[kparzysz]

Made all the changes locally. Will test and post the updated patch on Monday.

lib/CodeGen/TargetInstrInfo.cpp

381–385 ↗

(On Diff #68553)

This one is still not done. I will post a separate patch for this on Monday.

[kparzysz]

lib/CodeGen/TargetInstrInfo.cpp

381–385 ↗

(On Diff #68553)

It was substPhysReg that needed to be updated and the change was fairly trivial, so I just fixed it in r279437.

[kparzysz]

Made the changes suggested in comments. I hope I didn't miss anything.

[MatzeB]

LGTM (just nitpicks below).

lib/CodeGen/RegisterCoalescer.cpp

1214

typo

1216

Instead of "connected to the program list" use "part of the function"?

test/CodeGen/Hexagon/regalloc-bad-undef.mir

167

completely unrelated to this patch, but this looks like a regmask operand could nicely replace dozens of implicit dead defs.

[vitalybuka]

This patch has memory leaks http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/15771/steps/check-llvm%20asan/logs/stdio

[kparzysz]

I think it's an unrelated problem. I'll take a look at this.

[kparzysz]

It should be fixed in r279678.

include/llvm/CodeGen/LiveInterval.h

struct Segment {
         return start == Other.start && end == Other.end;
       }
 
       void dump() const;
     };
 
     typedef SmallVector<Segment, 2> Segments;
     typedef SmallVector<VNInfo *, 2> VNInfoList;
+    typedef SmallVector<SlotIndex, 2> SlotList;
 
     Segments segments;   // the liveness segments
     VNInfoList valnos;   // value#'s
+    SlotList undefs;     // explicit "undefs" via <def,read-undef>
 
     // The segment set is used temporarily to accelerate initial computation
     // of live ranges of physical registers in computeRegUnitRange.
     // After that the set is flushed to the segment vector and deleted.
     typedef std::set<Segment> SegmentSet;
     std::unique_ptr<SegmentSet> segmentSet;
 
     typedef Segments::iterator iterator;
public:
 
     const_iterator find(SlotIndex Pos) const {
       return const_cast<LiveRange*>(this)->find(Pos);
     }
 
     void clear() {
       valnos.clear();
       segments.clear();
+      undefs.clear();
     }
 
     size_t size() const {
       return segments.size();
     }
 
     bool hasAtLeastOneValue() const { return !valnos.empty(); }
 
VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) {
       return VNI;
     }
 
     /// createDeadDef - Make sure the range has a value defined at Def.
     /// If one already exists, return it. Otherwise allocate a new value and
     /// 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,
                             VNInfo::Allocator &VNInfoAllocator) {
       VNInfo *VNI =
         new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
       valnos.push_back(VNI);
       return VNI;
public:
     /// [1,5](5,10] covers (3,7].
     bool covers(const LiveRange &Other) const;
 
     /// Add the specified Segment to this range, merging segments as
     /// appropriate.  This returns an iterator to the inserted segment (which
     /// may have grown since it was inserted).
     iterator addSegment(Segment S);
 
+    /// 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
     /// the ranges are not joinable, this aborts.
     void join(LiveRange &Other,
               const int *ValNoAssignments,
               const int *RHSValNoAssignments,
               SmallVectorImpl<VNInfo *> &NewVNInfo);
public:
     bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const;
 
     bool operator<(const LiveRange& other) const {
       const SlotIndex &thisIndex = beginIndex();
       const SlotIndex &otherIndex = other.beginIndex();
       return thisIndex < otherIndex;
     }
 
+    /// Returns true if there is an explicit "undef" between @p Begin
+    /// @p End.
+    bool isUndefIn(SlotIndex Begin, SlotIndex End) const {
+      return std::any_of(undefs.begin(), undefs.end(),
+                [Begin,End] (SlotIndex Idx) -> bool {
+                  return Begin <= Idx && Idx < End;
+                });
+    }
+
     /// Flush segment set into the regular segment vector.
     /// The method is to be called after the live range
     /// has been created, if use of the segment set was
     /// activated in the constructor of the live range.
     void flushSegmentSet();
 
+    void clearUndefs() { undefs.clear(); }
+
     void print(raw_ostream &OS) const;
     void dump() const;
 
     /// \brief Walk the range and assert if any invariants fail to hold.
     ///
     /// Note that this is a no-op when asserts are disabled.
 #ifdef NDEBUG
     void verify() const {}
 #else
     void verify() const;
 #endif
 
   protected:
     /// Append a segment to the list of segments.
     void append(const LiveRange::Segment S);
 
   private:
     friend class LiveRangeUpdater;
     void addSegmentToSet(Segment S);
     void markValNoForDeletion(VNInfo *V);
-
+    void pruneUndefs();
   };
 
   inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
     LR.print(OS);
     return OS;
   }
 
   /// LiveInterval - This class represents the liveness of a register,
bool isSpillable() const {
       return weight != llvm::huge_valf;
     }
 
     /// markNotSpillable - Mark interval as not spillable
     void markNotSpillable() {
       weight = llvm::huge_valf;
     }
 
+    void clearSubRangeUndefs() {
+      super::clearUndefs();
+      for (SubRange &S : subranges())
+        S.clearUndefs();
+    }
+
+    /// Recalculate explicit "undefs" for all subranges: if a subrange is
+    /// defined at Idx, any subranges that are not defined at Idx and are
+    /// not live at Idx will be considered explicitly undefined.
+    void recalculateSubRangeUndefs();
+
     bool operator<(const LiveInterval& other) const {
       const SlotIndex &thisIndex = beginIndex();
       const SlotIndex &otherIndex = other.beginIndex();
       return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg);
     }
 
     void print(raw_ostream &OS) const;
     void dump() const;

include/llvm/CodeGen/LiveIntervalAnalysis.h

public:
     /// Specialized version of
     /// shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead)
     /// that works on a subregister live range and only looks at uses matching
     /// the lane mask of the subregister range.
     /// This may leave the subrange empty which needs to be cleaned up with
     /// 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
     /// any liveness reachable from Kill. Add live range end points to
     /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the
     /// value's live range.
     ///
     /// Calling pruneValue() and extendToIndices() can be used to reconstruct

lib/CodeGen/LiveInterval.cpp

 
 protected:
   CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}
 
 public:
   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
       // register on an instruction. It doesn't make a lot of sense, but it is
       // possible to specify in inline assembly.
       //
       // Just convert everything to early-clobber.
       Def = std::min(Def, S->start);
       if (Def != S->start)
         S->start = S->valno->def = Def;
       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
   /// by I to end at the specified endpoint. To do this, we should
   /// merge and eliminate all segments that this will overlap
   /// with. The iterator is not invalidated.
   void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
     assert(I != segments().end() && "Not a valid segment!");
do {
     } else {
       I += Mid + 1;
       Len -= Mid + 1;
     }
   } while (Len);
   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
 // not empty.
 //
 // An example for overlaps():
 //
 // 0: A = ...

 
 LiveRange::iterator LiveRange::addSegment(Segment S) {
   // Use the segment set, if it is available.
   if (segmentSet != nullptr) {
     addSegmentToSet(S);
     return end();
   }
   // Otherwise use the segment vector.
-  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);
   // Otherwise use the segment vector.
   return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);
 }
 
 /// Remove the specified segment from this range.  Note that the segment must

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

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

lib/CodeGen/LiveIntervalAnalysis.cpp

for (auto VNI : VNIs) {
     LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
   }
 }
 
 typedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList;
 
 static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
                                  ShrinkToUsesWorkList &WorkList,
-                                 const LiveRange &OldRange) {
+                                 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.
   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)) {
+    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?
       if (!VNI->isPHIDef() || VNI->def != BlockStart ||
           !UsedPHIs.insert(VNI).second)
         continue;
       // The PHI is live, make sure the predecessors are live-out.
       for (auto &Pred : MBB->predecessors()) {
while (!WorkList.empty()) {
     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
     LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
 
     // Make sure VNI is live-out from the predecessors.
     for (auto &Pred : MBB->predecessors()) {
       if (!LiveOut.insert(Pred).second)
         continue;
       SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
+      if (AllowUndef && OldRange.getVNInfoBefore(Stop) == nullptr)
+        continue;
       assert(OldRange.getVNInfoBefore(Stop) == VNI &&
              "Wrong value out of predecessor");
       WorkList.push_back(std::make_pair(Stop, VNI));
     }
   }
 }
 
 bool LiveIntervals::shrinkToUses(LiveInterval *li,
if (VNInfo *DefVNI = LRQ.valueDefined())
       Idx = DefVNI->def;
 
     WorkList.push_back(std::make_pair(Idx, VNI));
   }
 
   // Create new live ranges with only minimal live segments per def.
   LiveRange NewLR;
   createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
-  extendSegmentsToUses(NewLR, *Indexes, WorkList, *li);
+  extendSegmentsToUses(NewLR, *Indexes, WorkList, *li, false);
 
   // Move the trimmed segments back.
   li->segments.swap(NewLR.segments);
 
   // Handle dead values.
   bool CanSeparate = computeDeadValues(*li, dead);
   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
   return CanSeparate;
if (VNI->isPHIDef()) {
         DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
         dead->push_back(MI);
       }
     }
   }
   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");
   // Find all the values used, including PHI kills.
   ShrinkToUsesWorkList WorkList;
 
   // Visit all instructions reading Reg.
   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;
     }
     // We only need to visit each instruction once.
     SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
     if (Idx == LastIdx)
       continue;
     LastIdx = Idx;
if (VNInfo *DefVNI = LRQ.valueDefined())
       Idx = DefVNI->def;
 
     WorkList.push_back(std::make_pair(Idx, VNI));
   }
 
   // Create a new live ranges with only minimal live segments per def.
   LiveRange NewLR;
   createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
-  extendSegmentsToUses(NewLR, *Indexes, WorkList, SR);
+  extendSegmentsToUses(NewLR, *Indexes, WorkList, SR, true);
 
   // Move the trimmed ranges back.
   SR.segments.swap(NewLR.segments);
 
   // Remove dead PHI value numbers
   for (auto VNI : SR.valnos) {
     if (VNI->isUnused())
       continue;
     const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
     assert(Segment != nullptr && "Missing segment for VNI");
     if (Segment->end != VNI->def.getDeadSlot())
       continue;
     if (VNI->isPHIDef()) {
       // This is a dead PHI. Remove it.
       DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
       VNI->markUnused();
       SR.removeSegment(*Segment);
     }
   }
 
   DEBUG(dbgs() << "Shrunk: " << SR << '\n');
 }
 
 void LiveIntervals::extendToIndices(LiveRange &LR,
-                                    ArrayRef<SlotIndex> Indices) {
+                                    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,
                                SmallVectorImpl<SlotIndex> *EndPoints) {
   LiveQueryResult LRQ = LR.Query(Kill);
   VNInfo *VNI = LRQ.valueOutOrDead();
   if (!VNI)
     return;
for (MachineOperand &MO : MI->operands()) {
       }
 
       unsigned Reg = MO.getReg();
       if (!Reg)
         continue;
       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
         LiveInterval &LI = LIS.getInterval(Reg);
         if (LI.hasSubRanges()) {
+          LI.clearSubRangeUndefs();
           unsigned SubReg = MO.getSubReg();
-          LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
+          LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
+                                        : MRI.getMaxLaneMaskForVReg(Reg);
           for (LiveInterval::SubRange &S : LI.subranges()) {
             if ((S.LaneMask & LaneMask) == 0)
               continue;
             updateRange(S, Reg, S.LaneMask);
           }
         }
         updateRange(LI, Reg, 0);
         continue;
       }
 
       // For physregs, only update the regunits that actually have a
       // precomputed live range.
       for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
         if (LiveRange *LR = getRegUnitLI(*Units))
           updateRange(*LR, *Units, 0);
     }
     if (hasRegMask)
       updateRegMaskSlots();
+
+    for (MachineOperand &MO : MI->operands()) {
+      if (!MO.isReg() || !MO.isDef())
+        continue;
+      unsigned Reg = MO.getReg();
+      if (!TargetRegisterInfo::isVirtualRegister(Reg))
+        continue;
+      LIS.getInterval(Reg).recalculateSubRangeUndefs();
+    }
   }
 
 private:
   /// Update a single live range, assuming an instruction has been moved from
   /// OldIdx to NewIdx.
   void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
     if (!Updated.insert(&LR).second)
       return;
void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
   for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
     if (LiveRange *LR = getCachedRegUnit(*Units))
       if (VNInfo *VNI = LR->getVNInfoAt(Pos))
         LR->removeValNo(VNI);
   }
 }
 
 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;
+  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))
+      if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
         S.removeValNo(SVNI);
   }
   LI.removeEmptySubRanges();
 }
 
 void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
     SmallVectorImpl<LiveInterval*> &SplitLIs) {
   ConnectedVNInfoEqClasses ConEQ(*this);
   unsigned NumComp = ConEQ.Classify(LI);

lib/CodeGen/LiveRangeCalc.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_CODEGEN_LIVERANGECALC_H
 #define LLVM_LIB_CODEGEN_LIVERANGECALC_H
 
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/LiveInterval.h"
 
 namespace llvm {
 
 /// Forward declarations for MachineDominators.h:
 class MachineDominatorTree;
 template <class NodeT> class DomTreeNodeBase;
 typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
class LiveRangeCalc {
   typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap;
 
   /// Bit vector of active entries in LiveOut, also used as a visited set by
   /// findReachingDefs.  One entry per basic block, indexed by block number.
   /// This is kept as a separate bit vector because it can be cleared quickly
   /// 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.
   ///
   /// For every basic block, MBB, one of these conditions shall be true:
   ///
   ///  1. !Seen.count(MBB->getNumber())
   ///     Blocks without a Seen bit are ignored.
   ///  2. LiveOut[MBB].second.getNode() == MBB
class LiveRangeCalc {
   };
 
   /// LiveIn - Work list of blocks where the live-in value has yet to be
   /// determined.  This list is typically computed by findReachingDefs() and
   /// used as a work list by updateSSA().  The low-level interface may also be
   /// used to add entries directly.
   SmallVector<LiveInBlock, 16> LiveIn;
 
-  /// Assuming that @p LR is live-in to @p UseMBB, find the set of defs that can
-  /// reach it.
-  ///
-  /// 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.
+  /// 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 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.
   ///
   /// Every live-in block must be jointly dominated by the added live-out
   /// blocks.  No values are read from the live ranges.
   void updateSSA();
 
   /// Transfer information from the LiveIn vector to the live ranges and update
   /// the given @p LiveOuts.
   void updateFromLiveIns();
 
   /// 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();
 
 public:
   LiveRangeCalc() : MF(nullptr), MRI(nullptr), Indexes(nullptr),
                     DomTree(nullptr), Alloc(nullptr) {}
 
   //===--------------------------------------------------------------------===//
public:
 
   //===--------------------------------------------------------------------===//
   // Mid-level interface.
   //===--------------------------------------------------------------------===//
   //
   // Modify existing live ranges.
   //
 
   /// Extend the live range of @p LR to reach @p Use.
   ///
   /// The existing values in @p LR must be live so they jointly dominate @p Use.
   /// If @p Use is not dominated by a single existing value, PHI-defs are
   /// inserted as required to preserve SSA form.
   ///
   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
-  void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg = 0);
+  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
   /// minimal live range.
   void createDeadDefs(LiveRange &LR, unsigned Reg);
 
   /// Extend the live range of @p LR to reach all uses of Reg.
   ///

lib/CodeGen/LiveRangeCalc.cpp

 //===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Implementation of the LiveRangeCalc class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "LiveRangeCalc.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "regalloc"
 
 void LiveRangeCalc::resetLiveOutMap() {
   unsigned NumBlocks = MF->getNumBlockIDs();
   Seen.clear();
   Seen.resize(NumBlocks);
+  DefOnEntry.clear();
+  DefOnEntry.resize(NumBlocks);
+  UndefOnEntry.clear();
+  UndefOnEntry.resize(NumBlocks);
   Map.resize(NumBlocks);
 }
 
 void LiveRangeCalc::reset(const MachineFunction *mf,
                           SlotIndexes *SI,
                           MachineDominatorTree *MDT,
                           VNInfo::Allocator *VNIA) {
   MF = mf;
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
 
   // Create the def in LR. This may find an existing def.
   LR.createDeadDef(DefIdx, Alloc);
 }
 
 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.
   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
   unsigned Reg = LI.reg;
   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     if (!MO.isDef() && !MO.readsReg())
       continue;
 
+    const MachineInstr &MI = *MO.getParent();
+    bool IsEC = MO.isEarlyClobber();
+    SlotIndex Idx = Indexes->getInstructionIndex(MI).getRegSlot(IsEC);
+
     unsigned SubReg = MO.getSubReg();
     if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
-      LaneBitmask 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()) {
         LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
         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;
       }
       // Create a new SubRange for subregs we did not cover yet.
       if (Mask != 0) {
         LiveInterval::SubRange *NewRange = LI.createSubRange(*Alloc, Mask);
         if (MO.isDef())
           createDeadDef(*Indexes, *Alloc, *NewRange, MO);
       }
+
+      if (MO.isDef() && MO.isUndef() && SubReg != 0) {
+        LaneBitmask UndefMask = WholeMask & ~SubMask;
+        // Add undefs to the subranges covered by UndefMask. Create new
+        // subranges if necessary.
+        for (LiveInterval::SubRange &S : LI.subranges()) {
+          LaneBitmask Common = S.LaneMask & UndefMask;
+          if (Common == 0)
+            continue;
+          getCommonRange(S, UndefMask)->undefs.push_back(Idx);
+          UndefMask &= ~Common;
+        }
+        if (UndefMask != 0)
+          LI.createSubRange(*Alloc, UndefMask)->undefs.push_back(Idx);
+      }
     }
 
     // Create the def in the main liverange. We do not have to do this if
     // subranges are tracked as we recreate the main range later in this case.
     if (MO.isDef() && !LI.hasSubRanges())
       createDeadDef(*Indexes, *Alloc, LI, MO);
   }
 
   // We may have created empty live ranges for partially undefined uses, we
   // can't keep them because we won't find defs in them later.
   LI.removeEmptySubRanges();
 
   // Step 2: Extend live segments to all uses, constructing SSA form as
   // necessary.
   if (LI.hasSubRanges()) {
     for (LiveInterval::SubRange &S : LI.subranges()) {
       resetLiveOutMap();
-      extendToUses(S, Reg, S.LaneMask);
+      extendToUses(S, Reg, S.LaneMask, true);
     }
     LI.clear();
     constructMainRangeFromSubranges(LI);
   } else {
     resetLiveOutMap();
     extendToUses(LI, Reg, ~0u);
   }
 }
 
 void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
   // First create dead defs at all defs found in subranges.
   LiveRange &MainRange = LI;
   assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
          "Expect empty main liverange");
 
   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     for (const VNInfo *VNI : SR.valnos) {
       if (!VNI->isUnused() && !VNI->isPHIDef())
         MainRange.createDeadDef(VNI->def, *Alloc);
     }
   }
-
   resetLiveOutMap();
-  extendToUses(MainRange, LI.reg);
+  extendToUses(MainRange, LI.reg, ~0U, true);
 }
 
 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
   assert(MRI && Indexes && "call reset() first");
 
   // Visit all def operands. If the same instruction has multiple defs of Reg,
   // LR.createDeadDef() will deduplicate.
   for (MachineOperand &MO : MRI->def_operands(Reg))
     createDeadDef(*Indexes, *Alloc, LR, MO);
 }
 
 
-void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg,
-                                 LaneBitmask Mask) {
+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)) {
     // Clear all kill flags. They will be reinserted after register allocation
     // 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;
     }
 
     // Determine the actual place of the use.
     const MachineInstr *MI = MO.getParent();
     unsigned OpNo = (&MO - &MI->getOperand(0));
     SlotIndex UseIdx;
     if (MI->isPHI()) {
if (MI->isPHI()) {
         // had an early-clobber flag.
         isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
       }
       UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
     }
 
     // MI is reading Reg. We may have visited MI before if it happens to be
     // reading Reg multiple times. That is OK, extend() is idempotent.
-    extend(LR, UseIdx, Reg);
+    extend(LR, UseIdx, Reg, AllowUndef);
   }
 }
 
 
 void LiveRangeCalc::updateFromLiveIns() {
   LiveRangeUpdater Updater;
   for (const LiveInBlock &I : LiveIn) {
     if (!I.DomNode)
       continue;
for (const LiveInBlock &I : LiveIn) {
     }
     Updater.setDest(&I.LR);
     Updater.add(Start, End, I.Value);
   }
   LiveIn.clear();
 }
 
 
-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");
 
   MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
   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.
   calculateValues();
 }
 
 
 // This function is called by a client after using the low-level API to add
 // live-out and live-in blocks.  The unique value optimization is not
 // available, SplitEditor::transferValues handles that case directly anyway.
 void LiveRangeCalc::calculateValues() {
   assert(Indexes && "Missing SlotIndexes");
   assert(DomTree && "Missing dominator tree");
   updateSSA();
   updateFromLiveIns();
 }
 
 
+bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, MachineBasicBlock &MBB) {
+  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.
   SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
 
   // Remember if we have seen more than one value.
   bool UniqueVNI = true;
   VNInfo *TheVNI = nullptr;
 
+  bool FoundUndef = false;
+
   // Using Seen as a visited set, perform a BFS for all reaching defs.
   for (unsigned i = 0; i != WorkList.size(); ++i) {
     MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
 
 #ifndef NDEBUG
-    if (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";
       const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
       if (MI != nullptr)
         errs() << Use << " " << *MI;
       llvm_unreachable("Use not jointly dominated by defs.");
     }
 
     if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
         !MBB->isLiveIn(PhysReg)) {
       MBB->getParent()->verify();
       errs() << "The register " << PrintReg(PhysReg)
              << " needs to be live in to BB#" << MBB->getNumber()
              << ", but is missing from the live-in list.\n";
       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) {
        MachineBasicBlock *Pred = *PI;
 
        // Is this a known live-out block?
        if (Seen.test(Pred->getNumber())) {
          if (VNInfo *VNI = Map[Pred].first) {
            if (TheVNI && TheVNI != VNI)
              UniqueVNI = false;
            TheVNI = VNI;
          }
          continue;
        }
 
        SlotIndex Start, End;
        std::tie(Start, End) = Indexes->getMBBRange(Pred);
 
        // First time we see Pred.  Try to determine the live-out value, but set
        // it as null if Pred is live-through with an unknown value.
-       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());
        else
           // Loopback to UseMBB, so value is really live through.
          Use = SlotIndex();
     }
   }
 
   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.
   if (WorkList.size() > 4)
     array_pod_sort(WorkList.begin(), WorkList.end());
 
   // 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) {
+      std::tie(Start, End) = Indexes->getMBBRange(BN);
+      if (BN == UseMBBNum && Use.isValid())
+        Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
     }
     return true;
   }
 
   // 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;
   }
 
   return false;
 }
 
for (LiveInBlock &I : LiveIn) {
         std::tie(Start, End) = Indexes->getMBBRange(MBB);
         LiveRange &LR = I.LR;
         VNInfo *VNI = LR.getNextValue(Start, *Alloc);
         I.Value = VNI;
         // This block is done, we know the final value.
         I.DomNode = nullptr;
 
         // Add liveness since updateFromLiveIns now skips this node.
-        if (I.Kill.isValid())
+        if (I.Kill.isValid()) {
+          if (VNI)
             LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
-        else {
+        } else {
+          if (VNI)
             LR.addSegment(LiveInterval::Segment(Start, End, VNI));
           LOP = LiveOutPair(VNI, Node);
         }
       } else if (IDomValue.first) {
         // No phi-def here. Remember incoming value.
         I.Value = IDomValue.first;
 
         // If the IDomValue is killed in the block, don't propagate through.
         if (I.Kill.isValid())

lib/CodeGen/LiveRangeEdit.cpp

 void LiveRangeEdit::Delegate::anchor() { }
 
 LiveInterval &LiveRangeEdit::createEmptyIntervalFrom(unsigned OldReg) {
   unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
   if (VRM) {
     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;
 }
 
 unsigned LiveRangeEdit::createFrom(unsigned OldReg) {
   unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
   if (VRM) {
     VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
   }

 
 void LiveRangeEdit::scanRemattable(AliasAnalysis *aa) {
   for (VNInfo *VNI : getParent().valnos) {
     if (VNI->isUnused())
       continue;
     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;
     checkRematerializable(OrigVNI, DefMI, aa);
   }
   ScannedRemattable = true;
 }
 
void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink,
   } else {
     // If the dest of MI is an original reg and MI is reMaterializable,
     // don't delete the inst. Replace the dest with a new reg, and keep
     // the inst for remat of other siblings. The inst is saved in
     // LiveRangeEdit::DeadRemats and will be deleted after all the
     // 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();
       markDeadRemat(MI);
       const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
       MI->substituteRegister(Dest, NewLI.reg, 0, TRI);
       MI->getOperand(0).setIsDead(true);
     } else {

lib/CodeGen/MachineVerifier.cpp

void MachineVerifier::verifyLiveRangeSegment(const LiveRange &LR,
   // The following checks only apply to virtual registers. Physreg liveness
   // is too weird to check.
   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
     // A live segment can end with either a redefinition, a kill flag on a
     // use, or a dead flag on a def.
     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;
     }
     if (S.end.isDead()) {
       // Make sure that the corresponding machine operand for a "dead" live
       // range has the dead flag. We cannot perform this check for subregister
       // liveranges as partially dead values are allowed.
       if (LaneMask == 0 && !hasDeadDef) {

lib/CodeGen/RegisterCoalescer.cpp

if (DefMO.getSubReg() == DstIdx) {
              && "Shouldn't have SrcIdx+DstIdx at this point");
       const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
       const TargetRegisterClass *CommonRC =
         TRI->getCommonSubClass(DefRC, DstRC);
       if (CommonRC != nullptr) {
         NewRC = CommonRC;
         DstIdx = 0;
         DefMO.setSubReg(0);
       }
     }
   }
 
   // CopyMI may have implicit operands, save them so that we can transfer them
   // over to the newly materialized instruction after CopyMI is removed.
   SmallVector<MachineOperand, 4> ImplicitOps;
   ImplicitOps.reserve(CopyMI->getNumOperands() -
                       CopyMI->getDesc().getNumOperands());
if (UseMask != ~0u && DstLI.hasSubRanges()) {
       }
     } else
       isLive = DstLI.liveAt(UseIdx);
     if (isLive)
       continue;
     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;
 }
 
 void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
                                      MachineOperand &MO, unsigned SubRegIdx) {
   LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx);
   if (MO.isDef())
     Mask = ~Mask;
for (MachineRegisterInfo::reg_instr_iterator
 
     DEBUG({
         dbgs() << "\t\tupdated: ";
         if (!UseMI->isDebugValue())
           dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";
         dbgs() << *UseMI;
       });
   }
+
+  if (DstInt && DstInt->hasSubRanges())
+    DstInt->recalculateSubRangeUndefs();
 }
 
 bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
   // Always join simple intervals that are defined by a single copy from a
   // reserved register. This doesn't increase register pressure, so it is
   // always beneficial.
   if (!MRI->isReserved(CP.getDstReg())) {
     DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
public:
   void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
                    bool changeInstrs);
 
   /// Removes subranges starting at copies that get removed. This sometimes
   /// happens when undefined subranges are copied around. These ranges contain
   /// 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();
 
   /// Get the value assignments suitable for passing to LiveInterval::join.
   const int *getAssignments() const { return Assignments.data(); }
 };
 } // end anonymous namespace
JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
   const MachineInstr *DefMI = nullptr;
   if (VNI->isPHIDef()) {
     // Conservatively assume that all lanes in a PHI are valid.
     LaneBitmask Lanes = SubRangeJoin ? 1 : TRI->getSubRegIndexLaneMask(SubIdx);
     V.ValidLanes = V.WriteLanes = Lanes;
   } 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;
       if (DefMI->isImplicitDef()) {
         V.ValidLanes = 0;
         V.ErasableImplicitDef = true;
       }
     } else {
case CR_Merge:
       break;
     case CR_Unresolved:
     case CR_Impossible:
       llvm_unreachable("Unresolved conflicts");
     }
   }
 }
 
-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) {
     if (Vals[i].Resolution != CR_Erase)
       continue;
 
     // Check subranges at the point where the copy will be removed.
     SlotIndex Def = LR.getValNumInfo(i)->def;
for (LiveInterval::SubRange &S : LI.subranges()) {
         ShrinkMask |= S.LaneMask;
       }
     }
   }
   if (DidPrune)
     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];
     if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)
       continue;
 
     VNInfo *VNI = LR.getValNumInfo(i);
     VNI->markUnused();
     LR.removeValNo(VNI);
   }
 }
 
 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;
     switch (Vals[i].Resolution) {
     case CR_Keep: {
       // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
       // longer. The IMPLICIT_DEF instructions are only inserted by
       // PHIElimination to guarantee that all PHI predecessors have a value.
       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.
     }
 
     case CR_Erase: {
       MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
       assert(MI && "No instruction to erase");
       if (MI->isCopy()) {
         unsigned Reg = MI->getOperand(1).getReg();
if (!LHS.hasSubRanges()) {
       LHS.createSubRangeFrom(Allocator, Mask, LHS);
     } else if (DstIdx != 0) {
       // Transform LHS lanemasks to new register class if necessary.
       for (LiveInterval::SubRange &R : LHS.subranges()) {
         LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
         R.LaneMask = Mask;
       }
     }
+    // The merging process may cause the undef information to become invalid
+    // and fail verification. Clear it here, it will be recalculated later.
+    LHS.clearSubRangeUndefs();
     DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg())
                  << ' ' << LHS << '\n');
 
     // Determine lanemasks of RHS in the coalesced register and merge subranges.
     unsigned SrcIdx = CP.getSrcIdx();
     if (!RHS.hasSubRanges()) {
       LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
                                      : TRI->getSubRegIndexLaneMask(SrcIdx);
       mergeSubRangeInto(LHS, RHS, Mask, CP);
     } else {
       // Pair up subranges and merge.
       for (LiveInterval::SubRange &R : RHS.subranges()) {
         LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
         mergeSubRangeInto(LHS, R, Mask, CP);
       }
     }
     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);
   }
 
   // The merging algorithm in LiveInterval::join() can't handle conflicting
   // value mappings, so we need to remove any live ranges that overlap a
   // CR_Replace resolution. Collect a set of end points that can be used to
   // restore the live range after joining.
   SmallVector<SlotIndex, 8> EndPoints;
   LHSVals.pruneValues(RHSVals, EndPoints, true);
   RHSVals.pruneValues(LHSVals, EndPoints, true);
 
   // 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()));
 
   // Join RHS into LHS.
   LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
 
   // Kill flags are going to be wrong if the live ranges were overlapping.

lib/CodeGen/RenameIndependentSubregs.cpp

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

lib/CodeGen/SplitKit.h

private:
 
   /// getLRCalc - Return the LRCalc to use for RegIdx.  In spill mode, the
   /// complement interval can overlap the other intervals, so it gets its own
   /// LRCalc instance.  When not in spill mode, all intervals can share one.
   LiveRangeCalc &getLRCalc(unsigned RegIdx) {
     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.
   /// This is used for values whose live range doesn't match RegAssign exactly.
   /// They could have rematerialized, or back-copies may have been moved.
   void forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI);
 
   /// defFromParent - Define Reg from ParentVNI at UseIdx using either

lib/CodeGen/SplitKit.cpp

LLVM_DUMP_METHOD void SplitEditor::dump() const {
   }
 
   for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
     dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
   dbgs() << '\n';
 }
 #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");
   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
 
   // 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;
 }
 
 void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
   assert(ParentVNI && "Mapping  NULL value");
   ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
   VNInfo *VNI = VFP.getPointer();
 
   // ParentVNI was either unmapped or already complex mapped. Either way, just
   // set the force bit.
   if (!VNI) {
     VFP.setInt(true);
     return;
   }
 
   // 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);
 }
 
 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
                                    VNInfo *ParentVNI,
                                    SlotIndex UseIdx,
                                    MachineBasicBlock &MBB,
                                    MachineBasicBlock::iterator I) {
   MachineInstr *CopyMI = nullptr;
   SlotIndex Def;
   LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
 
   // We may be trying to avoid interference that ends at a deleted instruction,
   // so always begin RegIdx 0 early and all others late.
   bool Late = RegIdx != 0;
 
   // Attempt cheap-as-a-copy rematerialization.
   unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
   LiveInterval &OrigLI = LIS.getInterval(Original);
   VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
+
+  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;
-  } else {
+      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());
     Def = LIS.getSlotIndexes()
               ->insertMachineInstrInMaps(*CopyMI, Late)
               .getRegSlot();
     ++NumCopies;
   }
 
   // Define the value in Reg.
-  return defValue(RegIdx, ParentVNI, Def);
+  return defValue(RegIdx, ParentVNI, Def, false);
 }
 
 /// Create a new virtual register and live interval.
 unsigned SplitEditor::openIntv() {
   // Create the complement as index 0.
   if (Edit->empty())
     Edit->createEmptyInterval();
 
do {
           ++AssignI;
         }
       } else {
         RegIdx = 0;
         End = std::min(End, AssignI.start());
       }
 
       // 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;
       }
 
       // Skip values with forced recomputation.
       if (VFP.getInt()) {
         DEBUG(dbgs() << "(recalc)");
         Skipped = true;
         Start = End;
         continue;
       }
 
       LiveRangeCalc &LRC = getLRCalc(RegIdx);
 
       // This value has multiple defs in RegIdx, but it wasn't rematerialized,
       // so the live range is accurate. Add live-in blocks in [Start;End) to the
       // LiveInBlocks.
       MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
       SlotIndex BlockStart, BlockEnd;
       std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
 
       // The first block may be live-in, or it may have its own def.
       if (Start != BlockStart) {
-        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?
         if (BlockEnd <= End)
           LRC.setLiveOutValue(&*MBB, VNI);
 
         // Skip to the next block for live-in.
         ++MBB;
         BlockStart = BlockEnd;
       }
 
       // Handle the live-in blocks covered by [Start;End).
       assert(Start <= BlockStart && "Expected live-in block");
       while (BlockStart < End) {
         DEBUG(dbgs() << ">BB#" << MBB->getNumber());
         BlockEnd = LIS.getMBBEndIdx(&*MBB);
         if (BlockStart == ParentVNI->def) {
           // This block has the def of a parent PHI, so it isn't live-in.
           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
-          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.
         } else {
           // 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);
           }
         }
         BlockStart = BlockEnd;
         ++MBB;
       }
       Start = End;
     } while (Start != S.end);
     DEBUG(dbgs() << '\n');
   }
 
   LRCalc[0].calculateValues();
   if (SpillMode)
     LRCalc[1].calculateValues();
 
   return Skipped;
 }
 
 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;
+    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) {
+  SetVector<unsigned> RecalcMain;
+
+  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;
     MachineInstr *MI = MO.getParent();
     ++RI;
     // LiveDebugVariables should have handled all DBG_VALUE instructions.
     if (MI->isDebugValue()) {
       DEBUG(dbgs() << "Zapping " << *MI);
       MO.setReg(0);
       continue;
     }
 
     // <undef> operands don't really read the register, so it doesn't matter
     // which register we choose.  When the use operand is tied to a def, we must
     // use the same register as the def, so just do that always.
     SlotIndex Idx = LIS.getInstructionIndex(*MI);
     if (MO.isDef() || MO.isUndef())
       Idx = Idx.getRegSlot(MO.isEarlyClobber());
 
     // Rewrite to the mapped register at Idx.
     unsigned RegIdx = RegAssign.lookup(Idx);
-    LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
-    MO.setReg(LI->reg);
+    LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
+    MO.setReg(LI.reg);
+    if (LI.hasSubRanges()) {
+      RecalcMain.insert(LI.reg);
+      // If this is a read-undef def of a subregister, add undefs to the
+      // undefined subranges.
+      if (MO.getSubReg() && MO.isUndef()) {
+        LaneBitmask LM = getMaskForOp(MO);
+        for (LiveInterval::SubRange &S : LI.subranges())
+          if (!(S.LaneMask & LM))
+            S.undefs.push_back(Idx);
+      }
+    }
     DEBUG(dbgs() << "  rewr BB#" << MI->getParent()->getNumber() << '\t'
                  << Idx << ':' << RegIdx << '\t' << *MI);
 
     // Extend liveness to Idx if the instruction reads reg.
     if (!ExtendRanges || MO.isUndef())
       continue;
 
     // Skip instructions that don't read Reg.
     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))
         continue;
     } 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 : RecalcMain) {
+    LiveInterval &LI = LIS.getInterval(R);
+    LI.clear();
+    LI.removeEmptySubRanges();
+    LIS.constructMainRangeFromSubranges(LI);
   }
 }
 
 void SplitEditor::deleteRematVictims() {
   SmallVector<MachineInstr*, 8> Dead;
   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
     LiveInterval *LI = &LIS.getInterval(*I);
     for (const LiveRange::Segment &S : LI->segments) {
void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
   // At this point, the live intervals in Edit contain VNInfos corresponding to
   // the inserted copies.
 
   // Add the original defs from the parent interval.
   for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
     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.
     if (Edit->didRematerialize(ParentVNI))
       for (unsigned i = 0, e = Edit->size(); i != e; ++i)
         forceRecompute(i, ParentVNI);
   }
 
void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
   else
     ++NumSimple;
 
   // Delete defs that were rematted everywhere.
   if (Skipped)
     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();
   }
 
   // Provide a reverse mapping from original indices to Edit ranges.
   if (LRMap) {
     LRMap->clear();
     for (unsigned i = 0, e = Edit->size(); i != e; ++i)
       LRMap->push_back(i);

lib/CodeGen/VirtRegMap.cpp

bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {
   unsigned Reg = MO.getReg();
   const LiveInterval &LI = LIS->getInterval(Reg);
   const MachineInstr &MI = *MO.getParent();
   SlotIndex BaseIndex = LIS->getInstructionIndex(MI);
   // This code is only meant to handle reading undefined subregisters which
   // we couldn't properly detect before.
   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()) {
     if ((SR.LaneMask & UseMask) != 0 && SR.liveAt(BaseIndex))
       return false;
   }
   return true;
 }

lib/Target/Hexagon/HexagonExpandCondsets.cpp

for (auto &Seg : Range) {
     if (LocalImpDefs.count(DefI))
       continue;
     Defs.insert(DefI->getParent());
     if (HII->isPredicated(*DefI))
       PredDefs.push_back(Seg.start);
   }
   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();
   }
 
   // Calculate reachability for those predicated defs that were not handled
   // by the in-block extension.
   SmallVector<SlotIndex,4> ExtTo;
   for (auto &SI : PredDefs) {
     if (!SI.isValid())
       continue;
     MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
     if (BB->pred_empty())
       continue;
     // If the defs from this range reach SI via all predecessors, it is live.
     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
   // the necessary implicit uses.
   std::set<RegisterRef> DefRegs;
   for (auto &Seg : Range) {
     if (!Seg.start.isRegister())
       continue;

test/CodeGen/Hexagon/regalloc-bad-undef.mir

+# 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:
+
+...