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

1147

Change the name to SubLRC

lib/CodeGen/VirtRegMap.cpp

339

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

339

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 ↗

(On Diff #62498)

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

510–511

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.

582

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

1540–1541

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

lib/CodeGen/LiveRangeCalc.cpp

297 ↗

(On Diff #62498)

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 ↗

(On Diff #62498)

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

393

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.

405–406

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

956

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

1540–1541

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 ↗

(On Diff #62498)

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

lib/CodeGen/SplitKit.cpp

956

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 ↗

(On Diff #64719)

Oops. Will remove this shortly.

lib/CodeGen/SplitKit.cpp

1157

Oops. Will remove this shortly.

[kparzysz]

Removed leftover code. NFC.

[kparzysz]

lib/CodeGen/LiveRangeCalc.cpp

299 ↗

(On Diff #64722)

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

229 ↗

(On Diff #64972)

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

389 ↗

(On Diff #64972)

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

232 ↗

(On Diff #64947)

does it handle partial register uses?

[kparzysz]

lib/CodeGen/LiveRangeCalc.cpp

229 ↗

(On Diff #64972)

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.

230 ↗

(On Diff #64972)

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 ↗

(On Diff #64972)

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

229 ↗

(On Diff #64972)

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

389 ↗

(On Diff #64972)

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

229 ↗

(On Diff #64972)

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

389 ↗

(On Diff #64972)

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

1092

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

458 ↗

(On Diff #68553)

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..."

611 ↗

(On Diff #68553)

this can be removed now.

include/llvm/CodeGen/LiveIntervalAnalysis.h

166–176 ↗

(On Diff #68553)

This should not talk about AllowUndef anymore

lib/CodeGen/LiveInterval.cpp

62–63 ↗

(On Diff #68553)

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

532–533 ↗

(On Diff #68553)

this change appears unnecessary.

542–544 ↗

(On Diff #68553)

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

581

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

977–984

empty loop?

lib/CodeGen/LiveRangeCalc.cpp

58–69 ↗

(On Diff #68553)

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

249 ↗

(On Diff #68553)

Should use LaneBitmask instead of unsigned.

lib/CodeGen/LiveRangeCalc.h

27 ↗

(On Diff #68553)

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

134–140 ↗

(On Diff #68553)

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

160–164 ↗

(On Diff #68553)

This needs an update a well.

208–209 ↗

(On Diff #68553)

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 ↗

(On Diff #68553)

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

2514–2521 ↗

(On Diff #68553)

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).

2780–2781 ↗

(On Diff #68553)

remove stale comment.

lib/CodeGen/SplitKit.cpp

1035–1044

Pull this out into a static toplevel function.

1045–1097

dito.

1111–1116

this is only used once and could be inlined.

lib/CodeGen/SplitKit.h

327–330

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

465 ↗

(On Diff #68553)

Should use LaneBitmask

466–480 ↗

(On Diff #68553)

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

458 ↗

(On Diff #68553)

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

lib/CodeGen/LiveIntervalAnalysis.cpp

581

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

977–984

Leftover from something.

lib/Target/Hexagon/HexagonExpandCondsets.cpp

466–480 ↗

(On Diff #68553)

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

[MatzeB]

lib/Target/Hexagon/HexagonExpandCondsets.cpp

466–480 ↗

(On Diff #68553)

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

1215 ↗

(On Diff #68874)

typo

1217 ↗

(On Diff #68874)

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.

lib/CodeGen/LiveIntervalAnalysis.cpp

if (VNI->isPHIDef()) {
       }
     }
   }
   return MayHaveSplitComponents;
 }
 
 void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
 {
-  DEBUG(dbgs() << "Shrink: " << SR << '\n');
+  DEBUG(dbgs() << "Shrink: L" << PrintLaneMask(SR.LaneMask)
+               << ' ' << 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())
       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 ((LaneMask & SR.LaneMask) == 0)
         continue;
     }
     // We only need to visit each instruction once.
     SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
     if (Idx == LastIdx)
       continue;
     LastIdx = Idx;
 
void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
 
   DEBUG(dbgs() << "Shrunk: " << SR << '\n');
 }
 
 void LiveIntervals::extendToIndices(LiveRange &LR,
                                     ArrayRef<SlotIndex> Indices) {
   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]);
 }
 
 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()) {
       // 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();
   }
 
 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;
     DEBUG({
       dbgs() << "     ";
       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
         dbgs() << PrintReg(Reg);
         if (LaneMask != 0)
           dbgs() << " L" << PrintLaneMask(LaneMask);
       } else {
         dbgs() << PrintRegUnit(Reg, &TRI);
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) {
   VNInfo *VNI = LI.getVNInfoAt(Pos);
   if (VNI == nullptr)
     return;
   LI.removeValNo(VNI);
 
   // Also remove the value in subranges.
   for (LiveInterval::SubRange &S : LI.subranges()) {
     if (VNInfo *SVNI = S.getVNInfoAt(Pos))
       S.removeValNo(SVNI);
   }

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.
+  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));
   }
if (ReadsPhysRegs) {
     DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
   } else {
     // If the dest of MI is an original reg, don't delete the inst. Replace
     // the dest with a new reg, 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) {
       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/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];
   }
 
+  /// 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.
+  void addDeadDef(LiveInterval &LI, VNInfo *VNI);
+
   /// 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.
   /// Return the new LI value.
   VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx);
 
   /// forceRecompute - Force the live range of ParentVNI in RegIdx to be

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
 
+void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI) {
+  SlotIndex Def = VNI->def;
+  LI.addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
+  for (LiveInterval::SubRange &S : LI.subranges()) {
+    VNInfo *V = S.getNextValue(Def, LIS.getVNInfoAllocator());
+    S.addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), V));
+  }
+}
+
 VNInfo *SplitEditor::defValue(unsigned RegIdx,
                               const VNInfo *ParentVNI,
                               SlotIndex Idx) {
   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());
 
   // 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)));
 
   // This was the first time (RegIdx, ParentVNI) was mapped.
   // Keep it as a simple def without any liveness.
   if (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);
+
+    // 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, LI->hasSubRanges());
   }
 
   // This is a complex mapping, add liveness for VNI
-  SlotIndex Def = VNI->def;
-  LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
-
+  addDeadDef(*LI, VNI);
   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);
+
   // Mark as complex mapped, forced.
   VFP = ValueForcePair(nullptr, true);
 }
 
 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
                                    VNInfo *ParentVNI,
                                    SlotIndex UseIdx,
                                    MachineBasicBlock &MBB,
do {
         }
       } 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));
+      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));
+        VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
         assert(VNI && "Missing def for complex mapped value");
         DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
         // MBB has its own def. Is it also live-out?
         if (BlockEnd <= End)
           LRC.setLiveOutValue(&*MBB, VNI);
 
         // Skip to the next block for live-in.
         ++MBB;
         BlockStart = BlockEnd;
       }
 
       // Handle the live-in blocks covered by [Start;End).
       assert(Start <= BlockStart && "Expected live-in block");
       while (BlockStart < End) {
         DEBUG(dbgs() << ">BB#" << MBB->getNumber());
         BlockEnd = LIS.getMBBEndIdx(&*MBB);
         if (BlockStart == ParentVNI->def) {
           // This block has the def of a parent PHI, so it isn't live-in.
           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
-          VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
+          VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
           assert(VNI && "Missing def for complex mapped parent PHI");
           if (End >= BlockEnd)
             LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
         } else {
           // This block needs a live-in value.  The last block covered may not
           // be live-out.
           if (End < BlockEnd)
-            LRC.addLiveInBlock(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) -> 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");
+      if (Edit->getParent().liveAt(LastUse))
         LRC.extend(LR, End);
-      }
+  };
+
+  // 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.
+
+  // Each location in the parent interval may correspond to a different
+  // interval after splitting. Also, a slot index from the parent interval
+  // may contain PHI defs for the main range as well as one or more of the
+  // subranges. The same holds for each of the newly created intervals.
+  // To reduce the complexity of the traversal, collect locations of all
+  // PHI defs first from the parent interval (and its subranges), then for
+  // each location, visit the corresponding new interval and its subranges.
+  std::set<SlotIndex> PhiDefs;
+  auto AppendPhiDefs = [&PhiDefs] (LiveRange &LR) -> void {
+    for (const VNInfo *V : LR.valnos)
+      if (!V->isUnused() && V->isPHIDef())
+        PhiDefs.insert(V->def);
+  };
+  for (LiveInterval::SubRange &S : Edit->getParent().subranges())
+    AppendPhiDefs(S);
+  AppendPhiDefs(Edit->getParent());
+
+  // The extending of the subranges must use a separate LiveRangeCalc,
+  // since the subranges can overlap. LRC caches some of its calculations
+  // making it unsuitable for use with overlapping ranges.
+  LiveRangeCalc SubLRC;
+
+  for (SlotIndex Def : PhiDefs) {
+    unsigned RegIdx = RegAssign.lookup(Def);
+    LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
+    LiveRangeCalc &LRC = getLRCalc(RegIdx);
+    MachineBasicBlock &B = *LIS.getMBBFromIndex(Def);
+
+    for (LiveInterval::SubRange &S : LI.subranges()) {
+      if (RemoveDeadSegment(Def, S))
+        continue;
+      SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
+                   &LIS.getVNInfoAllocator());
+      ExtendPHIRange(B, SubLRC, S);
     }
+    if (!RemoveDeadSegment(Def, LI))
+      ExtendPHIRange(B, LRC, LI);
   }
 }
 
 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
   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);
     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()) {
+      LiveRangeCalc C;
+      unsigned Sub = MO.getSubReg();
+      LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
+                                : MRI.getMaxLaneMaskForVReg(MO.getReg());
+      for (LiveInterval::SubRange &S : LI->subranges()) {
+        if (S.empty() || !(S.LaneMask & LM))
+          continue;
+        C.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
+                &LIS.getVNInfoAllocator());
+        C.extend(S, Next);
+      }
+    }
+    LiveRangeCalc &LRC = getLRCalc(RegIdx);
+    LRC.extend(*LI, Next);
   }
 }
 
 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) {
   case SM_Size:
   case SM_Speed:
     // hoistCopies will behave differently between size and speed.
     hoistCopies();
   }
 
   // Transfer the simply mapped values, check if any are skipped.
   bool Skipped = transferValues();
-
   // Rewrite virtual registers, possibly extending ranges.
   rewriteAssigned(Skipped);
 
   if (Skipped)
     extendPHIKillRanges();
   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);
+    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");
+  assert(LI.hasSubRanges());
   unsigned SubRegIdx = MO.getSubReg();
   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;

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

+# RUN: llc -march=hexagon -hexagon-subreg-liveness -start-after machine-scheduler -stop-after stack-slot-coloring %s 2>&1 -o /dev/null | 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:
+
+...