<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Oh that is an old ticket, the items in the TODO below are all done (some are obsolete).</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">We do have subregister liveness tracking enabled in production for AMDGPU and an out of tree target, so it certainly works today.</div><div class=""><br class=""></div><div class="">- Matthias</div><br class=""><div><blockquote type="cite" class=""><div class="">On Jul 19, 2016, at 9:26 AM, Sergey Yakoushkin <<a href="mailto:sergey.yakoushkin@gmail.com" class="">sergey.yakoushkin@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hi all,<div class=""><br class=""></div><div class="">I'm working on LLVM-based back-end. We have custom LLVM solution for sub-register liveness tracking.</div><div class=""><br class=""></div><div class="">Recently we tried to replace it with LLVM enableSubRegLiveness and run into multiple issues.</div><div class="">I can't share specific IR snippets now, but failures are related to spilling, undef sub-registers, etc.<br class=""></div><div class=""><br class=""></div><div class="">There is Bug 17557 open since 2013: Enable subregister liveness for scheduling and register allocation.</div><div class=""><a href="https://llvm.org/bugs/show_bug.cgi?id=17557" class="">https://llvm.org/bugs/show_bug.cgi?id=17557</a></div><div class=""><br class=""></div><div class="">with TODO list:</div><div class=""><pre class="" id="comment_text_0" style="white-space: pre-wrap; width: 50em;">"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."</pre></div><div class=""><div class=""><br class=""></div><div class="">Is someone still working on bug fixes and enhancements? any pending patches?</div></div><div class=""><br class=""></div><div class="">R600 back-end is using sub-reg liveness: e.g. r238999 - R600: Re-enable sub-reg liveness (June 2015).</div><div class="">But it seems requirements and use cases are GPU-specific.<br class=""></div><div class=""><br class=""></div><div class="">Does anyone use sub-reg liveness for RISC/CISC+SIMD targets?</div><div class=""><br class=""></div><div class="">Thanks,<br class=""></div><div class="">Sergey</div><div class=""><br class=""></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Wed, Oct 9, 2013 at 11:03 PM, Matthias Braun <span dir="ltr" class=""><<a href="mailto:mbraun@apple.com" target="_blank" class="">mbraun@apple.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><br class=""><div class=""><span class=""><div class="">On Oct 8, 2013, at 2:06 PM, Akira Hatanaka <<a href="mailto:ahatanak@gmail.com" target="_blank" class="">ahatanak@gmail.com</a>> wrote:</div><br class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class="">What I didn't mention in r<span style="font-size:13px;font-family:arial,sans-serif" class="">192119 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.</span></div></div></blockquote></span><div class="">Uh that is indeed nasty, and can’t really be expressed like that in the current RA framework I think.</div><span class=""><br class=""><blockquote type="cite" class=""><div dir="ltr" class="">
<div class=""><span style="font-size:13px;font-family:arial,sans-serif" class=""><br class=""></span></div><div class="">For example, this is an illegal sequence of instructions, where instruction 3 makes $hi unpredictable:</div><div class=""><br class=""></div><div class="">1. mult $lo<def>, $hi<def>, $2, $3 // $lo<def>, $hi<def> = $2 * $3</div>
<div class=""><div class="">2. mflo $4, $lo<use> // $4 <- $lo<br class=""></div><div class="">3. mtlo $lo<def>, $6 // $lo <- $6. effectively clobbers $hi too.<br class=""></div></div><div class=""><div class="">4. mfhi $5, $hi<use> // $5 <- $hi</div><div class="">5. mthi $hi<def>, $7 // $hi <- $7</div>
</div><div class=""><div class="">6. madd $lo<def>, $hi<def>, $8, $9, $lo<use>, $hi<use> // $lo<def>, $hi<def> = $2 * $3 + (lo,hi) </div><div class=""><br class=""></div><div class="">Unlike the mtlo instruction in the example above, instruction 5 in the next example does not clobber $hi:</div>
<div class=""><br class=""></div><div class=""><div class="">1. mult $lo<def>, $hi<def>, $2, $3 // $lo<def>, $hi<def> = $2 * $3</div><div class=""><div class="">2. mflo $4, $lo<use> // $4 <- $lo<br class=""></div><div class="">3. mfhi $5, $hi<use> // $5 <- $hi<br class="">
</div></div><div class="">4. mthi $hi<def>, $7 // $hi <- $7.<br class=""></div><div class=""><div class="">5. mtlo $lo<def>, $6 // $lo <- $6. This does not clobber $hi.<br class=""></div><div class=""></div><div class="">6. madd $lo<def>, $hi<def>, $8, $9, $lo<use>, $hi<use> // $lo<def>, $hi<def> = $2 * $3 + (lo,hi) </div>
<div class=""><br class=""></div><div class="">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).</div></div></div></div></div></blockquote></span><div class="">That is probably the cleanest solution, with the only downside being that the scheduler can’t place instruction between the mthi and mtlo anymore.</div><div class=""><br class=""></div><div class="">Greetings</div><span class=""><font color="#888888" class=""><div class=""><span style="white-space:pre-wrap" class=""> </span>Matthias</div></font></span><div class=""><div class=""><br class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class=""><div class=""><div class="">
</div></div></div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><br class=""><div class="gmail_quote">On Tue, Oct 8, 2013 at 1:04 PM, Matthias Braun <span dir="ltr" class=""><<a href="mailto:matze@braunis.de" target="_blank" class="">matze@braunis.de</a>></span> wrote:<br class="">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div class=""><div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<br class="">
<div class="">
<div class="">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.<br class="">
<br class="">
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?<br class="">
<br class="">
Greetings<br class="">
Matthias<br class="">
<br class="">
Am 10/8/13, 11:03 AM, schrieb Akira Hatanaka:<br class="">
</div>
<blockquote type="cite" class="">
<div dir="ltr" class="">
<div class="">Hi,</div>
<div class=""><br class="">
</div>
<div class="">I have a question about the way sub-registers are spilled
and restored that is related to the changes I made in
r192119.</div>
<div class=""><br class="">
</div>
<div class="">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.</div>
<div class=""><br class="">
</div>
instr0 %vreg0<def>
<div class="">instr1 %vreg1:sub_lo<def<span style="font-family:arial,sans-serif;font-size:13px" class="">,read-undef</span>><br class="">
</div>
<div class="">instr2 %vreg0<use></div>
<div class="">
<div class="">instr3 %vreg1:sub_hi<def></div>
</div>
<div class=""><br class="">
</div>
<div class="">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?</div>
<div class=""><br class="">
</div>
<div class="">instr0 %vreg0<def></div>
<div class="">spill0 %vreg0<br class="">
<div class="">instr1 %vreg1:sub_lo<def<span style="font-family:arial,sans-serif;font-size:13px" class="">,read-undef</span>><br class="">
</div>
spill1 %vreg1:sub_lo<br class="">
restore0 %vreg0<br class="">
<div class="">instr2 %vreg0<use></div>
restore1 %vreg1:sub_lo<br class="">
<div class="">instr3 %vreg1:sub_hi<def></div>
</div>
<div class=""><br class="">
</div>
<div class="">Or will it spill just the lo sub-register?</div>
<div class=""><br class="">
</div>
<div class="">
<div class="">instr0 %vreg0<def></div>
<div class="">spill0 %vreg0:sub_lo<br class="">
<div class="">instr1 %vreg1:sub_lo<def<span style="font-family:arial,sans-serif;font-size:13px" class="">,read-undef</span>><br class="">
</div>
spill1 %vreg1:sub_lo<br class="">
restore0 %vreg0:sub_lo<br class="">
<div class="">instr2 %vreg0<use></div>
restore1 %vreg1:sub_lo<br class="">
<div class="">instr3 %vreg1:sub_hi<def></div>
</div>
</div>
<div class=""><br class="">
</div>
<div class="">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.</div>
<div class=""><br class="">
</div>
</div>
<div class="gmail_extra"><br class="">
<br class="">
<div class="gmail_quote">On Mon, Oct 7, 2013 at 1:11 PM,
Matthias Braun <span dir="ltr" class=""><<a href="mailto:matze@braunis.de" target="_blank" class="">matze@braunis.de</a>></span> wrote:<br class="">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">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.<br class="">
<br class="">
Greetings<br class="">
Matthias Braun<br class="">
<br class="">
<br class="">
Subregisters in llvm<br class="">
====================<br class="">
<br class="">
Some targets can access registers in different ways
resulting in wider or<br class="">
narrower accesses. For example on ARM NEON one of the
single precision<br class="">
floating point registers is called 'S0'. You may also
access 'D0' on arm which<br class="">
is the combination of 'S0' and 'S1' and can store a double
prevision number or<br class="">
2 single precision floats. 'Q0' is the combination of
'S0', 'S1', 'S2' and<br class="">
'S3' (or 'D0' and 'D1') and so on.<br class="">
<br class="">
Before register allocation llvm machine code accesses
values through virtual<br class="">
registers, these get assigned to physical registers later.
Each virtual<br class="">
register has an assigned register class which is a set of
physical registers.<br class="">
So for example on ARM you have a register class containing
all the 'SXX'<br class="">
registers and another one containing all the 'DXX'
registers, ...<br class="">
<br class="">
But sometimes you want to mix narrow and wide accesses to
values. Like loading<br class="">
the 'D0' register but later reading the 'S0' and 'S1'
components separately.<br class="">
This is modeled with subregister operands which specify
that only parts of a<br class="">
wider value are accessed. For example the register class
of the 'DXX'<br class="">
registers supports subregisters calls 'ssub_0' and
'ssub_1' which would<br class="">
result in 'S4' and 'S5' getting used if 'D2' is assigned
to the virtual<br class="">
register later.<br class="">
<br class="">
Typical operations are decomposing wider values or
composing wide values with<br class="">
multiple smaller defs:<br class="">
<br class="">
Decomposing:<br class="">
%vreg1<def> = produce a 'D' value<br class="">
= use 'S' value %vreg1:ssub_0<br class="">
= use 'S' value %vreg1:ssub_1<br class="">
<br class="">
Composing:<br class="">
%vreg1:ssub_0<def,read-undef> = produce an 'S' value<br class="">
%vreg1:ssub_1<def> = produce an 'S' value<br class="">
= use a 'D' value %vreg1<br class="">
<br class="">
Problems / Motivation<br class="">
=====================<br class="">
<br class="">
Currently the llvm register allocator tracks liveness for
whole virtual<br class="">
registers. This can lead to suboptimal code:<br class="">
<br class="">
%vreg0:ssub_0<def,read-undef> = produce an 'S' value<br class="">
%vreg0:ssub_1<def> = produce an 'S' value<br class="">
= use a 'D' value %vreg0<br class="">
%vreg1 = produce an 'S' value<br class="">
= use an 'S' value %vreg1<br class="">
= use an 'S' value %vreg0:ssub_0<br class="">
<br class="">
The current code will realize that vreg0 and vreg1
interfere and assign them<br class="">
to different registers like D0+S2 aka S0+S1+S2; while in
reality after the<br class="">
full use of %vreg0 only %vreg0::ssub_0 must remain in a
register while the<br class="">
subregister used for %vreg0:ssub_1 can be reassigned to
%vreg1. An ideal<br class="">
assignment would be D0+S1 aka S0+S1.<br class="">
<br class="">
A even more pressing problem are artificial dependencies
in the schedule<br class="">
graph. This is a side effect of llvms live range
information being represented<br class="">
in a static single assignment like fashion: Every
definition of a vreg starts<br class="">
a new interval with a new value number. This means that
partial register<br class="">
writes must be modeled as an implicit use of the unwritten
parts of a register<br class="">
and force the creating of a new value number. This in turn
leads to artificial<br class="">
dependencies in the schedule graph for code like the
following where all defs<br class="">
should be independent:<br class="">
<br class="">
%vreg0:ssub_0<def,read-undef> = produce an 'S' value<br class="">
%vreg0:ssub_1<def> = produce an 'S' value<br class="">
%vreg0:ssub_2<def> = produce an 'S' value<br class="">
%vreg0:ssub_3<def> = produce an 'S' value<br class="">
<br class="">
<br class="">
Subegister liveness tracking<br class="">
============================<br class="">
<br class="">
I developed a set of patches which enable liveness
tracking on the subregister<br class="">
level, to overcome the problems mentioned above. After
these changes you can<br class="">
have separate live ranges for subregisters of a virtual
register. With these<br class="">
patches the following code:<br class="">
<br class="">
16B %vreg0:ssub_0<def,read-undef> = ...<br class="">
32B %vreg0:ssub_1<def> = ...<br class="">
48B = %vreg0<br class="">
64B = %vreg0:ssub_0<br class="">
80B %vreg0 = ...<br class="">
96B = %vreg0:ssub_1<br class="">
<br class="">
will be represented as the following live range(s):<br class="">
<br class="">
Common LiveRange: [16r,32r)[32r,64r),[80r,96r)<br class="">
SubRange with Mask 0x0004 (=ssub_0): [16r,64r)[80r,80d)<br class="">
SubRange with Mask 0x0008 (=ssub_1): [32r,48r)[80r,96r)<br class="">
<br class="">
Patches/Changes:<br class="">
* Moves live range management code in the LiveInterval
class to a new<br class="">
class LiveRange, move the previous LiveRange class
(which was just a single<br class="">
interval inside a live range) to LiveRange::Segment.<br class="">
LiveInterval is made a subclass of LiveRange, other code
paths like<br class="">
register units liveness use LiveRange instead of
LiveInterval now.<br class="">
* Introduce a linked list of SubRange objects to the
LiveInterval class.<br class="">
A SubRange is a subclass of LiveRange and contains a
LaneMask indicating<br class="">
which subregisters are represented.<br class="">
* Various algorithms have been adapted to
calculate/preserve subregister<br class="">
liveness.<br class="">
* The register allocator has been adapted to track
interference at the<br class="">
subregister level (LaneMasks are mapped to register
units)<br class="">
<br class="">
Note that SubRegister liveness tracking has to be
explicitely enabled by the<br class="">
target architecture, as it does not provide enough
benefits for the costs on<br class="">
some targets (e.g. having subregister liveness for the
lower/upper 8bit regs<br class="">
on x86 provided nearly no benefits in the llvm-testsuite,
so you can't justify<br class="">
more computations/memory usage for that.<br class="">
_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a>
<a href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class="">
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class="">
</blockquote>
</div>
<br class="">
</div>
<br class="">
<fieldset class=""></fieldset>
<br class="">
<pre class="">_______________________________________________
LLVM Developers mailing list
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br class="">
<br class="">
</div>
<br class="">
</div>
</div></div><br class="">_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class="">
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class="">
<br class=""></blockquote></div><br class=""></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class=""></blockquote></div></div></div><br class=""></div><br class="">_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" rel="noreferrer" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class="">
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class="">
<br class=""></blockquote></div><br class=""></div></div>
</div></blockquote></div><br class=""></body></html>