[LLVMdev] Subregister liveness tracking

[Matthias Braun]

I've been working on patches to improve subregister liveness tracking on
llvm and I wanted to inform the llvm community about the overal
design/motivation for them. I will send the patches to llvm-commits
later today.

Greetings
Matthias Braun


Subregisters in llvm
====================

Some targets can access registers in different ways resulting in wider or
narrower accesses. For example on ARM NEON one of the single precision
floating point registers is called 'S0'. You may also access 'D0' on arm
which
is the combination of 'S0' and 'S1' and can store a double prevision
number or
2 single precision floats. 'Q0' is the combination of 'S0', 'S1', 'S2' and
'S3' (or 'D0' and 'D1') and so on.

Before register allocation llvm machine code accesses values through
virtual
registers, these get assigned to physical registers later. Each virtual
register has an assigned register class which is a set of physical
registers.
So for example on ARM you have a register class containing all the 'SXX'
registers and another one containing all the 'DXX' registers, ...

But sometimes you want to mix narrow and wide accesses to values. Like
loading
the 'D0' register but later reading the 'S0' and 'S1' components
separately.
This is modeled with subregister operands which specify that only parts
of a
wider value are accessed. For example the register class of the 'DXX'
registers supports subregisters calls 'ssub_0' and 'ssub_1' which would
result in 'S4' and 'S5' getting used if 'D2' is assigned to the virtual
register later.

Typical operations are decomposing wider values or composing wide values
with
multiple smaller defs:

Decomposing:
%vreg1<def> = produce a 'D' value
= use 'S' value %vreg1:ssub_0
= use 'S' value %vreg1:ssub_1

Composing:
%vreg1:ssub_0<def,read-undef> = produce an 'S' value
%vreg1:ssub_1<def> = produce an 'S' value
= use a 'D' value %vreg1

Problems / Motivation
=====================

Currently the llvm register allocator tracks liveness for whole virtual
registers. This can lead to suboptimal code:

%vreg0:ssub_0<def,read-undef> = produce an 'S' value
%vreg0:ssub_1<def> = produce an 'S' value
= use a 'D' value %vreg0
%vreg1 = produce an 'S' value
= use an 'S' value %vreg1
= use an 'S' value %vreg0:ssub_0

The current code will realize that vreg0 and vreg1 interfere and assign
them
to different registers like D0+S2 aka S0+S1+S2; while in reality after the
full use of %vreg0 only %vreg0::ssub_0 must remain in a register while the
subregister used for %vreg0:ssub_1 can be reassigned to %vreg1. An ideal
assignment would be D0+S1 aka S0+S1.

A even more pressing problem are artificial dependencies in the schedule
graph. This is a side effect of llvms live range information being
represented
in a static single assignment like fashion: Every definition of a vreg
starts
a new interval with a new value number. This means that partial register
writes must be modeled as an implicit use of the unwritten parts of a
register
and force the creating of a new value number. This in turn leads to
artificial
dependencies in the schedule graph for code like the following where all
defs
should be independent:

%vreg0:ssub_0<def,read-undef> = produce an 'S' value
%vreg0:ssub_1<def> = produce an 'S' value
%vreg0:ssub_2<def> = produce an 'S' value
%vreg0:ssub_3<def> = produce an 'S' value


Subegister liveness tracking
============================

I developed a set of patches which enable liveness tracking on the
subregister
level, to overcome the problems mentioned above. After these changes you
can
have separate live ranges for subregisters of a virtual register. With
these
patches the following code:

16B %vreg0:ssub_0<def,read-undef> = ...
32B %vreg0:ssub_1<def> = ...
48B = %vreg0
64B = %vreg0:ssub_0
80B %vreg0 = ...
96B = %vreg0:ssub_1

will be represented as the following live range(s):

Common LiveRange: [16r,32r)[32r,64r),[80r,96r)
SubRange with Mask 0x0004 (=ssub_0): [16r,64r)[80r,80d)
SubRange with Mask 0x0008 (=ssub_1): [32r,48r)[80r,96r)

Patches/Changes:
* Moves live range management code in the LiveInterval class to a new
class LiveRange, move the previous LiveRange class (which was just a
single
interval inside a live range) to LiveRange::Segment.
LiveInterval is made a subclass of LiveRange, other code paths like
register units liveness use LiveRange instead of LiveInterval now.
* Introduce a linked list of SubRange objects to the LiveInterval class.
A SubRange is a subclass of LiveRange and contains a LaneMask indicating
which subregisters are represented.
* Various algorithms have been adapted to calculate/preserve subregister
liveness.
* The register allocator has been adapted to track interference at the
subregister level (LaneMasks are mapped to register units)

Note that SubRegister liveness tracking has to be explicitely enabled by
the
target architecture, as it does not provide enough benefits for the
costs on
some targets (e.g. having subregister liveness for the lower/upper 8bit
regs
on x86 provided nearly no benefits in the llvm-testsuite, so you can't
justify
more computations/memory usage for that.
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Akira Hatanaka]

Hi,

I have a question about the way sub-registers are spilled and restored that is related to the changes I made in r192119.

Suppose I have the following piece of code with four instructions. %vreg0 and %vreg1 consist of two sub-registers indexed by sub_lo and sub_hi.

instr0 %vreg0<def>

instr1 %vreg1:sub_lo<def,read-undef>

instr2 %vreg0<use>

instr3 %vreg1:sub_hi<def>

If register allocator decides to insert spill and restore instructions for %vreg0, will it spill the whole register that includes sub-registers lo and hi?

instr0 %vreg0<def>

spill0 %vreg0

instr1 %vreg1:sub_lo<def,read-undef>

spill1 %vreg1:sub_lo
restore0 %vreg0

instr2 %vreg0<use>

restore1 %vreg1:sub_lo

instr3 %vreg1:sub_hi<def>

Or will it spill just the lo sub-register?

instr0 %vreg0<def>

spill0 %vreg0:sub_lo

instr1 %vreg1:sub_lo<def,read-undef>

spill1 %vreg1:sub_lo
restore0 %vreg0:sub_lo

instr2 %vreg0<use>

restore1 %vreg1:sub_lo

instr3 %vreg1:sub_hi<def>

If it spills the whole register (both sub-registers lo and hi), the changes I made should be fine. Otherwise, I will have to find another way to prevent the problems I mentioned in r192119's commit log.

[Matthias Braun]

Currently it will always spill / restore the whole vreg but only spilling the parts that are actually live would be a nice addition in the future.

Looking at r192119’: if “mtlo” writes to $LO and sets $HI to an unpredictable value, then it should just have an additional (dead) def operand for $hi, shouldn’t it?

Greetings
    Matthias

Am 10/8/13, 11:03 AM, schrieb Akira Hatanaka:

[Akira Hatanaka]

What I didn't mention in r192119 is that mthi/lo clobbers the other sub-register only if the contents of hi and lo are produced by mult or other arithmetic instructions (div, madd, etc.) It doesn't have this side-effect if it is produced by another mthi/lo. So I don't think making mthi/lo clobber the other half would work.

For example, this is an illegal sequence of instructions, where instruction 3 makes $hi unpredictable:

1. mult $lo<def>, $hi<def>, $2, $3 // $lo<def>, $hi<def> = $2 * $3

2. mflo $4, $lo<use> // $4 <- $lo

3. mtlo $lo<def>, $6 // $lo <- $6. effectively clobbers $hi too.

4. mfhi $5, $hi<use> // $5 <- $hi

5. mthi $hi<def>, $7 // $hi <- $7

6. madd $lo<def>, $hi<def>, $8, $9, $lo<use>, $hi<use> // $lo<def>, $hi<def> = $2 * $3 + (lo,hi) 

Unlike the mtlo instruction in the example above, instruction 5 in the next example does not clobber $hi:

1. mult $lo<def>, $hi<def>, $2, $3 // $lo<def>, $hi<def> = $2 * $3

2. mflo $4, $lo<use> // $4 <- $lo

3. mfhi $5, $hi<use> // $5 <- $hi

4. mthi $hi<def>, $7 // $hi <- $7.

5. mtlo $lo<def>, $6 // $lo <- $6. This does not clobber $hi.

6. madd $lo<def>, $hi<def>, $8, $9, $lo<use>, $hi<use> // $lo<def>, $hi<def> = $2 * $3 + (lo,hi) 

Probably I can define a pseudo instruction "mthilo" that defines both lo and hi and expands to mthi and mtlo after register allocation, which will force register allocator to spill/restore the whole register in most cases (the only exception I can think of is the inline-assembly constraint 'l' for 'lo' register).

[Matthias Braun]

On Oct 8, 2013, at 2:06 PM, Akira Hatanaka <ahat...@gmail.com> wrote:

What I didn't mention in r192119 is that mthi/lo clobbers the other sub-register only if the contents of hi and lo are produced by mult or other arithmetic instructions (div, madd, etc.) It doesn't have this side-effect if it is produced by another mthi/lo. So I don't think making mthi/lo clobber the other half would work.

Uh that is indeed nasty, and can’t really be expressed like that in the current RA framework I think.

For example, this is an illegal sequence of instructions, where instruction 3 makes $hi unpredictable:

1. mult $lo<def>, $hi<def>, $2, $3 // $lo<def>, $hi<def> = $2 * $3

2. mflo $4, $lo<use> // $4 <- $lo

3. mtlo $lo<def>, $6 // $lo <- $6. effectively clobbers $hi too.

4. mfhi $5, $hi<use> // $5 <- $hi

5. mthi $hi<def>, $7 // $hi <- $7

6. madd $lo<def>, $hi<def>, $8, $9, $lo<use>, $hi<use> // $lo<def>, $hi<def> = $2 * $3 + (lo,hi) 

Unlike the mtlo instruction in the example above, instruction 5 in the next example does not clobber $hi:

1. mult $lo<def>, $hi<def>, $2, $3 // $lo<def>, $hi<def> = $2 * $3

2. mflo $4, $lo<use> // $4 <- $lo

3. mfhi $5, $hi<use> // $5 <- $hi

4. mthi $hi<def>, $7 // $hi <- $7.

5. mtlo $lo<def>, $6 // $lo <- $6. This does not clobber $hi.

6. madd $lo<def>, $hi<def>, $8, $9, $lo<use>, $hi<use> // $lo<def>, $hi<def> = $2 * $3 + (lo,hi) 

Probably I can define a pseudo instruction "mthilo" that defines both lo and hi and expands to mthi and mtlo after register allocation, which will force register allocator to spill/restore the whole register in most cases (the only exception I can think of is the inline-assembly constraint 'l' for 'lo' register).

That is probably the cleanest solution, with the only downside being that the scheduler can’t place instruction between the mthi and mtlo anymore.

Greetings

Matthias

[Sergey Yakoushkin via llvm-dev]

Hi all,

I'm working on LLVM-based back-end. We have custom LLVM solution for sub-register liveness tracking.

Recently we tried to replace it with LLVM enableSubRegLiveness and run into multiple issues.

I can't share specific IR snippets now, but failures are related to spilling, undef sub-registers, etc.

There is Bug 17557 open since 2013: Enable subregister liveness for scheduling and register allocation.

https://llvm.org/bugs/show_bug.cgi?id=17557

with TODO list:

"These are the remaining steps to get Matthias' subregister liveness fully integrated:
- Fix LiveRegUnits to correctly handle regmasks.
- Benchmark/tune compile time.
- Enable subreg liveness on x86 for testing purposes.
- Use LiveRegUnits to fix ARM VMOV widening.
- Fix the scheduler's DAG builder to use bundler iterator, not operand index.
- Discard the master live range after coalescing so that LiveInterval updates don't need to preserve it when we reorder subregister defs.
- Enable subreg scheduling on all targets that enable MI scheduler."

Is someone still working on bug fixes and enhancements? any pending patches?

R600 back-end is using sub-reg liveness: e.g. r238999 - R600: Re-enable sub-reg liveness (June 2015).

But it seems requirements and use cases are GPU-specific.

Does anyone use sub-reg liveness for RISC/CISC+SIMD targets?

Thanks,

Sergey

[Matthias Braun via llvm-dev]

Oh that is an old ticket, the items in the TODO below are all done (some are obsolete).

subregister liveness tracking has been available in llvm for roughly a year now and for a few months we also have scheduler extensions in place to allow independent scheduling of subregister definitions.

While I had subregister liveness tracking working for all CPU targets I decided against enabling it in the end. This is because I could not measure any benefits in the generated code, so I couldn't justify the added compiletime.

We do have subregister liveness tracking enabled in production for AMDGPU and an out of tree target, so it certainly works today.

- Matthias

[Matthias Braun via llvm-dev]

On Jul 19, 2016, at 1:11 PM, Sergey Yakoushkin <sergey.y...@gmail.com> wrote:

Hi Matthias,

Thanks for quick reply. I have few questions about sub-register support.

I'm currently using LLVM 3.8. Could you send links to recent patches/reviews?

Given the time the 3.8 branch was created it should definitely have all the subregister liveness tracking code, it may not have all the things necessary to enable the scheduler enhancements though.

1) Does LLVM maintain sub-register liveness while splitting live intervals?

No, currently subregister liveness information is dropped if registers get split or spilled.

There are currently some issues with recalculating liveness after invasive changes relating to the fact that you cannot set undef/dead flags on subregister granularity in todays llvm. There is no such problem when the liveness information is computed before register coalescing and the coalescer itself has code to update the liveness information rather than recomputing it.

The spilling and splitting code currently takes the easy way out and drops the subregister information (so you are only left with the liveness of the superregister). This hasn't been a problem for GPUs as those typically have many register so spilling and splitting are untypical operations.

2) How sub-register kill/dead flags and BB liveins should look after regalloc?

The kill and the dead flag describes the whole machine operand:

     %vreg0<dead>.             // dead def of the whole vreg0

     %vreg1.sub1<dead>.    // dead def of the sub1 subregisters (the other subregs may be live)

         = %vreg2<undef>.    // undef %vreg2 usage <=> the operand does not affect vreg2s liveness

         = %vreg2.sub2<undef>.  // undef %vreg2.sub1 usage

   %AL = xxx

            = use %EAX.  // this is legal: you only need part of the physreg to be defined for a use to be fine

            = use %EBX<undef>   // this still requires the undef flag as the complete register is undefined.

E.g. target has instructions both for sub-registers and registers.

Composite 64b reg contains 2x32b regs: Rxy = { Rx, Ry }. and scalar/vector add/ld/etc.

LiveRangeCalc::findReachingDefs expects to see all sub-registers in BB liveins together with pair registers.

BB1:

  Rxy<def> = ...

BB2: LiveIn: Rxy and Rx ?

You can either have Rxy in the live-in list, you may also have Rx and Ry separately in the list.

(Note that each live-in also has a lanemask assigned so you can have situations in which Rxy is in the live-in list

but the lanemask is telling you that just one of Rx/Ry is actually live)

  ... = ADD   Rx<use>

  ... = VADD Rxy<use>

00284     if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
00285         !MBB->isLiveIn(PhysReg)) {
00286       MBB->getParent()->verify();
00287       errs() << "The register " << PrintReg(PhysReg)
00288              << " needs to be live in to BB#" << MBB->getNumber()
00289              << ", but is missing from the live-in list.\n";
00290       llvm_unreachable("Invalid global physical register");
00291     }

You may be running in the recalculation problems here. Tricky situations may look like this:

BB0:

    %vreg0 = xxx

    jmp BB2

BB1:

    %vreg0.sub1<read-undef> = yyy

    jmp BB2

BB2:

      = use %vreg0.   // the instruction only cares about vreg0.sub1 but for some reason encodes the full register.

                                // However as we lack a way to add an "undef" flag for vreg0.sub0 the liveness calculation traces

                                // backwards and fails to find an actual sub0 definition in BB1.

If that is your actual problem, there is more discussion and a possible solution being discussed in  https://reviews.llvm.org/D21189. I must say though that I don't feel comfortable with the complexity added to the code there...

- Matthias

3) LLVM coalesces composite register and sub-registers, leaving some sub-registers undefined, but information is lost after regalloc rewriting.

Is it expected?

before regalloc:

%vreg:item1<def,read-undef> = MOV_imm 0

STORE <..#0>, 0, %vreg56

after regalloc:
%Rx<def> = MOV_imm 0
STORE <..#0>, 0, %Rxy

Regards,

Sergey

[Krzysztof Parzyszek via llvm-dev]

On 7/19/2016 3:46 PM, Matthias Braun wrote:
> If that is your actual problem, there is more discussion and a possible
> solution being discussed in https://reviews.llvm.org/D21189. I must say
> though that I don't feel comfortable with the complexity added to the
> code there...

I have a different version of isDefOnEntry coming that should reduce the
actual complexity. I have run into an unrelated problem though and I'm
getting that fixed now...

-Krzysztof

--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted by The Linux Foundation

_______________________________________________
LLVM Developers mailing list

llvm...@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev