<div dir="ltr">Thanks Philip for the feedback, I am glad you enjoyed reading it.<div><br></div><div>Vasileios</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jan 26, 2022 at 8:29 PM Philip Reames <<a href="mailto:listmail@philipreames.com">listmail@philipreames.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>
<p>This is a wonderful writeup of an interesting design problem, and
the chosen solution. I learned several things from reading it.
Thank you taking the time to write this up.</p>
<p>My takeaway after reading was that you've clearly thought through
all the issues in some depth. I might not lean the same direction
on each choice, but you've more than convinced me that you've
thought about them and made a reasoned choice. Solid +1 on the
design here.</p>
<p>Philip<br>
</p>
<div>On 1/26/22 6:57 PM, Vasileios Porpodas
via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hi everyone,<br>
<br>
This is an RFC for a new machine IR pass called Spill2Reg, which
selectively replaces spills to the stack with spills to vector
registers.<br>
The chain of patches can be found here: <a href="https://reviews.llvm.org/D118298" target="_blank">https://reviews.llvm.org/D118298</a>
(it includes all patches from D118298 to D118305).<br>
<br>
### Overview<br>
The register allocator emits spill/reload instructions to
temporarily save register values to memory. These are typically
stores to the stack (aka spills) and loads from the stack (aka
reloads or fills). These instructions hurt performance not only
because they increase the number of instructions executed, but
also because they add pressure to the memory resources, which
may already be heavily used by the actual memory instructions of
the workload.<br>
<br>
Spill2Reg aims at reducing this overhead by selectively
replacing spills/reloads to/from the stack with spills/reloads
to/from registers only when it is profitable. The target
registers that will hold the spilled value must be of a
different class than those that caused the spill, and in
architectures like x86 or ARM we can use vector registers to
save values from general purpose registers. Spill2reg can be
profitable in a couple of cases: (i) on targets where spills to
stack are always slower than spills to registers, (ii) in
pathological cases with lots of spill/reload instructions
back-to-back, (iii) in memory intensive workloads. It is worth
pointing out that Spill2Reg can be profitable even on targets
where spills to registers and spills to stack have a similar
latency. This is because replacing some of the stack
instructions with register instructions can help remove some
stalls caused by bottle-necks in the memory resources.<br>
<br>
Early evaluation on a Skylake(Server) x86_64 system shows that
Spill2Reg can improve performance of both synthetic tests and of
real-life workloads.<br>
<br>
<br>
Why Spill to Registers?<br>
=======================<br>
There are a couple of reasons why it makes sense to spill to
registers instead of memory. To summarize: (i) there is usually
a lot of free register space even when spilling and (ii)
spilling to vector registers can remove back-end stalls. The
following sections discuss these points in more detail.<br>
<br>
<br>
1. Free register space even when spilling<br>
-----------------------------------------<br>
Consider the following code:<br>
```<br>
int D0, D1, D2, ..., D18;<br>
foo() {<br>
int t0 = D0<br>
int t1 = D1<br>
...<br>
int t18 = D18<br>
// Some code<br>
... = t0<br>
... = t1<br>
...<br>
... = t18<br>
}<br>
```<br>
<br>
Variables t0 to t18 are all live across the middle point (marked
with `// Some code`). When compiled for x86_64, this code will
assign t0 to t14 to registers, but will spill t15 to t18.<br>
Here is what the assembly looks like:<br>
```<br>
movl D0(%rip), %eax<br>
movl %eax, -8(%rsp) # 4-byte Spill<br>
movl D1(%rip), %ecx<br>
movl D2(%rip), %edx<br>
movl D3(%rip), %esi<br>
movl D4(%rip), %edi<br>
movl D5(%rip), %r8d<br>
movl D6(%rip), %r9d<br>
movl D7(%rip), %r10d<br>
movl D8(%rip), %r11d<br>
movl D9(%rip), %ebx<br>
movl D10(%rip), %ebp<br>
movl D11(%rip), %r14d<br>
movl D12(%rip), %r15d<br>
movl D13(%rip), %r12d<br>
movl D14(%rip), %r13d<br>
movl D15(%rip), %eax<br>
movl %eax, -4(%rsp) # 4-byte Spill<br>
movl D16(%rip), %eax<br>
movl %eax, -12(%rsp) # 4-byte Spill<br>
movl D17(%rip), %eax<br>
movl %eax, -16(%rsp) # 4-byte Spill<br>
movl D18(%rip), %eax<br>
movl %eax, -20(%rsp) # 4-byte Spill<br>
# ... Some code ...<br>
movl -8(%rsp), %eax # 4-byte Reload<br>
movl %eax, U0(%rip)<br>
movl %ecx, U1(%rip)<br>
movl %edx, U2(%rip)<br>
movl %esi, U3(%rip)<br>
movl %edi, U4(%rip)<br>
movl %r8d, U5(%rip)<br>
movl %r9d, U6(%rip)<br>
movl %r10d, U7(%rip)<br>
movl %r11d, U8(%rip)<br>
movl %ebx, U9(%rip)<br>
movl %ebp, U10(%rip)<br>
movl %r14d, U11(%rip)<br>
movl %r15d, U12(%rip)<br>
movl %r12d, U13(%rip)<br>
movl %r13d, U14(%rip)<br>
movl -4(%rsp), %eax # 4-byte Reload<br>
movl %eax, U15(%rip)<br>
movl -12(%rsp), %eax # 4-byte Reload<br>
movl %eax, U16(%rip)<br>
movl -16(%rsp), %eax # 4-byte Reload<br>
movl %eax, U17(%rip)<br>
movl -20(%rsp), %eax # 4-byte Reload<br>
movl %eax, U18(%rip)<br>
```<br>
<br>
Meanwhile there is a lot of free space in the vector register
file, yet we are spilling to memory.<br>
<br>
<br>
2. Memory and register spills use different ports in x86<br>
--------------------------------------------------------<br>
According to [1] spill/reloads to/from the stack use ports 2, 3,
4, 7 on a Skylake Server x86 micro-architecture, while
spills/reloads to/from the vector register file use Ports 0, 1,
5. This means that the stack-based and vector-register-based
spills/reloads use different back-end resources, and by
replacing one with the other can shift the overhead from some
type of resources to another.<br>
<br>
This is particularly important for Spill2Reg, because it shows
that it can improve performance even if spills-to-stack and
spills-to-registers have a similar latency. If the CPU is
stalling due to over-subscribed memory resources, Spill2Reg can
replace some of them with spills-to-registers, which can help
remove some of the stalls.<br>
<br>
<br>
I think this looks familiar<br>
===========================<br>
If spilling to vector registers looks familiar, it is probably
because GCC has included support for spilling to registers for
quite some time. In x86 this was done with `vmovd` instructions
spilling to `xmm` registers.<br>
<br>
However, to the best of my knowledge, spilling to vector
registers in x86 has been disabled [2] due to stability [3,4,5],
correctness [6], and performance [7] issues.<br>
The performance issues highlighted in [7] seem to be related to:<br>
(i) double spilling: the vector register used for spilling get
spilled to memory, and<br>
(ii) folded reloads: if a reload can be folded into an
instruction, then spilling to a vector register results in an
additional instruction: the one extracting the value from the
vector register and inserting it into the general purpose
register.<br>
<br>
I believe that the proposed Spill2Reg design can address all
these issues. These points are discussed in the following
sections.<br>
<br>
<br>
Spill2Reg in x86<br>
================<br>
There are several interesting points about spilling to vector
registers in x86:<br>
<br>
- Writing/Reading to vector registers can be done with a single
assembly instruction. So spilling to vector register does not
introduce more instructions.<br>
- The vector register space is quite large at 2KB (32 ZMM
registers X 64 bytes) in Skylake server, so the chances are that
there will be a lot of free vector register space in general
purpose workloads.<br>
- If needed we could insert values to any vector lane using
`(V)PINSR{B,W,D,Q}` and `(V)PEXTR{B,W,D,Q}` (supported since
SSE4.1), or to lane 0 using `MOVD` (supported since MMX).<br>
- We can choose between two types of instructions for moving
data to vector registers: `MOVD/Q` and `PINSRD/Q`:<br>
- `PINSRD/Q` `PEXTRD/Q` allow us to insert/extract a value
to/from any lane of the vector register. It is implemented in
SSE4_1+.<br>
- `MOVD/Q` moves a 32/64bit value to the first lane of a
vector register. It is implemented in MMX+ instruction sets, so
it is widely supported. GCC’s implementation uses `MOVD`.<br>
- According to Agner Fog's latency/throughput data for Skylake
[9], `MOVD` has a lower latency than `PINSRD/Q`, same latency
than `MOV` to/from memory, but lower throughput:<br>
<br>
```<br>
uops uops uops<br>
fused unfused each latency throughput<br>
domain domain port<br>
Spill-to-reg<br>
------------<br>
MOVD mm/x r32/64 1 1 p5 2 1<br>
MOVD r32/64 mm/x 1 1 p0 2 1<br>
<br>
PINSRD/Q x,r,i 2 2 2p5 3 2<br>
PEXTRB/W/D/Q r,x,i 2 2 p0 p5 3 1<br>
<br>
Spill-to-stack<br>
--------------<br>
MOV m,r 1 2 p237 p4 2 1<br>
MOV r32/64, m 1 1 p23 2 0.5<br>
------------------------------------------------------------<br>
mm : 64-bit mmx register<br>
x : 128-bit xmm register<br>
m : memory operand<br>
m32 : 32-bit memory operand<br>
<br>
Source: Agner Fog's Instruction tables: <a href="https://www.agner.org/optimize/instruction_tables.pdf" target="_blank">https://www.agner.org/optimize/instruction_tables.pdf</a><br>
```<br>
<br>
<br>
Spill2Reg on ARM<br>
----------------<br>
According to ARM's software optimization guide [8] section 4.3
(page 57), it is encouraged to spill to vector registers because
these instructions have a lower latency than spills to memory.<br>
Also, given the RISC nature of ARM instructions, there are no
folded memory operands that we have to worry about when applying
Spill2Reg.<br>
<br>
<br>
Caveats<br>
=======<br>
- Instruction throughput/latency: Vector insert/extract
instructions may have lower throughput or higher latency than
memory load/stores on certain targets. If this is the case they
should be used only when memory resources are over subscribed.<br>
- Double spilling: We must take extra care not to spill the
vector registers that hold the spilled value, because this will
only add overhead. This was also observed in GCC's
implementation [7]. This is a concern when Spill2Reg is
implemented as part of the register allocator's spiller.<br>
- Additional instructions: Stack based spills/reloads can
potentially be folded. This is quite common in x86. For example,
given a reload `MOV Reg1, [Spill]` and an instruction using
`Reg1`, like `ADD Reg2, Reg1`, this can be folded into `Add
Reg2, [Spill]`, saving one instruction. Spill2Reg can
potentially block this folding, which will add an additional
instruction that reloads the data from the vector before the
`ADD`. This is a concern when Spill2Reg is implemented as part
of the register allocator's spiller, because folding of
spills/reloads may be taking place later on, after all
spills/reloads have been emitted.<br>
- Frequency throttling: Some targets will lower their turbo
frequency when running vector instructions [10]. Throttling is
the highest for AVX-512 but decreases as the vector width
decreases, and it seems that there is no frequency drop for
128-bit instructions.<br>
- Profitability models: There may be different trade-offs for
different targets or different generations of the same target.
Each target should implement its own profitability model.<br>
<br>
<br>
Proposed Design<br>
===============<br>
Spill2Reg can be implemented either as part of the spiller,
within the register allocator, or as a standalone pass after
register allocation. Each design point has its own benefits and
shortcomings. The following sections list some of the most
important points for and against each design. The discussion
provides some insights into why we believe Spill2Reg is best
implemented as a separate pass after the register allocator and
after physical registers are introduced.<br>
<br>
In the spiller versus as a standalone pass<br>
------------------------------------------<br>
<br>
### In the spiller<br>
- Pros:<br>
- The spiller is a natural location for the Spill2Reg code.<br>
- All analysis data needed are already computed and readily
available.<br>
- The actual logic is quite simple.<br>
<br>
- Cons:<br>
- The register allocator expects that a Spill/Reload is a
store/load. So supporting Spill2Reg requires some refactoring.<br>
- Spill/Reload removal optimizations within the register
allocator need to be updated to handle spills to registers.<br>
- The register allocation pass is already quite complex, and
adding Spill2Reg can increase complexity even further.<br>
- Folded spills/reloads (see GCC issue [7]): We need to be
able to skip Spill2Reg if spills/reloads to the stack can be
folded. Folding happens after the spill code is emitted, so
implementing this is not trivial.<br>
- Double-spills must be avoided (see GCC issue [7]): The
vector pseudo register that holds the spilled value needs to be
colored by the register allocator itself, and we need to
guarantee that it won't get spilled.<br>
<br>
### As a standalone pass<br>
- Pros:<br>
- Small pass, easy to design and maintain.<br>
- Easier pass testing.<br>
- Straight-forward tracking of performance
improvements/regressions, without having to worry if changes in
Spill2Reg may affect the decisions of the register allocator.<br>
<br>
- Cons:<br>
- May replicate analysis that is already available within the
register allocator.<br>
- Yet one more compiler pass.<br>
<br>
<br>
Given the points listed above, and the performance/stability
bugs reported in GCC [2,3,4,5,6,7], I believe that it makes
sense to implement Spill2Reg as a standalone pass. This results
in a simpler design, with simpler testing and easier performance
tracking to avoid performance regressions.<br>
<br>
<br>
As a standalone-pass: Before or after VirtRegRewriter<br>
-----------------------------------------------------<br>
Another design decision is whether we place the pass before or
after the `Virtual Register Rewriter` pass.<br>
<br>
### Before VirtRegRewriter<br>
- Pros:<br>
- We are still working with pseudo-registers.<br>
- Straight forward checking of pseudo register interference
using LiveIntervals and LiveRegMatrix.<br>
<br>
- Cons:<br>
- The main issue is with testing. Testing Spill2Reg would
require running the register allocator pass first, and relying
on it to generate spill/reload code, which would make tests very
verbose and tricky to write.<br>
- The pass would need to maintain the state of several
data-structures, like LiveIntervals and LiveRegMatrix.<br>
<br>
### After VirtRegRewriter<br>
- Pros:<br>
- The main point is ease of testing: We can test the pass in
isolation, using small tests containing hand-written
spill/reload code. No need to run other passes before it.<br>
- Fewer data structures to maintain.<br>
<br>
- Cons:<br>
- Spill2Reg needs its own live register tracking
implementation since it can no longer rely on LiveIntervals and
LiveRegMatrix for finding free physical registers.<br>
<br>
<br>
Given that the pass design is quite similar in both cases, and
that testing is significantly nicer in one of them, the
preferred option is after VirtRegRewriter.<br>
<br>
<br>
Target independent component<br>
----------------------------<br>
The Spill2Reg pass works as follows:<br>
1. It collects all candidate spill/reloads. This filters out
folded spills/reloads and unsupported data-types by the target
(target dependent legality check).<br>
2. Then it iterates through the collected candidates and checks
if it is profitable to spill to the vector register (target
dependent cost model).<br>
3. If profitable, it generates the new spills/reloads to/from
the vector register file and it removes the original
instructions (target dependent spill/reload instruction
generation).<br>
<br>
Target dependent components<br>
---------------------------<br>
This includes:<br>
- Legality checks that test whether the opcodes and types of
spills/reloads can be handled by the target.<br>
- The profitability heuristic, which checks whether we applying
Spill2Reg for a specific set of spills/reloads will lead to
better performing code on the target.<br>
- The generation of spill/reload instructions to/from a vector
register.<br>
<br>
<br>
Profitability Heuristic in x86<br>
------------------------------<br>
Given a candidate set of spills/reloads, we need to decide
whether applying Spill2Reg is more profitable. We are currently
implementing an all or nothing approach for the whole set: we
will either replace all spills/reloads or none.<br>
<br>
According to [9] spills to vector registers have the same
latency as spills to memory, but have lower throughput on
Skylake. So replacing all spills to memory with spills to the
stack can degrade performance. Instead, a better strategy is to
spill to registers only when the memory units are
over-subscribed, in an attempt to reduce any potential back-end
stalls.<br>
<br>
Since our goal is to avoid back-end stalls caused by
bottle-necks on memory resources, we need some way to measure
when these stalls could happen. Ideally we would query a
pipeline model (like the one used in instruction schedulers) to
determine if spills-to-stack can cause pipeline stalls. For now
the implementation is based on a simple instruction count: if
the count of memory instructions in the proximity of the
spill/reload is above a threshold, then apply Spill2Reg.<br>
<br>
Please note that the profitability heuristic is implemented as a
target-dependent components, so other targets can implement
their own specialized heuristics.<br>
<br>
<br>
Performance Results<br>
===================<br>
The performance evaluation was done using
`ba51d26ec4519f5b31de3acf643264504ea7bc7c` as a base commit on a
Skylake Xeon Gold 6154. The code was compiled with `-O3
-march=native`.<br>
Applying Spill2Reg to the code of the motivating example shown
in a previous section, replaces some of the spills/reloads with
`movd` instructions, leading to about 10% better performance.<br>
Spill2Reg also works on real-life applications: In SPEC CPU 2017
525.x264 Spill2Reg improves performance by about 0.3%.<br>
<br>
<br>
<br>
References<br>
----------<br>
[1] WikiChip Skylake microarchitecture: <a href="https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(server)" target="_blank">https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(server)</a><br>
<br>
[2] GCC spill to register: <a href="https://github.com/gcc-mirror/gcc/blob/5a431b60d1f221992e5e9f7a5c032df3b5fa35a5/gcc/config/i386/i386.c#L22874" target="_blank">https://github.com/gcc-mirror/gcc/blob/5a431b60d1f221992e5e9f7a5c032df3b5fa35a5/gcc/config/i386/i386.c#L22874</a><br>
<br>
[3] GCC stability bug: <a href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70902" target="_blank">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70902</a><br>
<br>
[4] GCC stability bug: <a href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71596" target="_blank">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71596</a><br>
<br>
[5] GCC stability bug: <a href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71555" target="_blank">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71555</a><br>
<br>
[6] GCC correctness bug: <a href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71657" target="_blank">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71657</a><br>
<br>
[7] GCC performance bug: <a href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71453" target="_blank">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71453</a><br>
<br>
[8] ARM Software Optimization Guide: <a href="https://developer.arm.com/documentation/swog309707/a" target="_blank">https://developer.arm.com/documentation/swog309707/a</a><br>
<br>
[9] Agner Fog's Instruction tables: <a href="https://www.agner.org/optimize/instruction_tables.pdf" target="_blank">https://www.agner.org/optimize/instruction_tables.pdf</a><br>
<br>
[10] Daniel Lemire's AVX throttling blog: <a href="https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-use-these-new-instructions/" target="_blank">https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-use-these-new-instructions/</a><br>
<br>
<br>
Thanks,<br>
Vasileios<br>
</div>
<br>
<fieldset></fieldset>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</div>
</blockquote></div>