[llvm-exegesis] parallel snippet generator: avoid Read-After-Write pitfail for instrs w/ tied variables

[lebedev.ri]

Summary

As it is being discussed in https://github.com/llvm/llvm-project/issues/59325,
at least for the instructions with tied variables,
when trying to parallelize the instructions,
register selection is rather bad, and may either
use a register which we have used for def,
or vice versa.

That introduces serialization, and leads to
overly pessimistic inverse throughput measurement.

The new implementation avoids that,

New result:

$ ninja llvm-exegesis && ./bin/llvm-exegesis --mode=inverse_throughput --opcode-name=VFMADD132PDr --max-configs-per-opcode=9182
ninja: no work to do.
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-4af034.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'VFMADD132PDr XMM3 XMM3 XMM4 XMM8'
    - 'VFMADD132PDr XMM5 XMM5 XMM14 XMM7'
    - 'VFMADD132PDr XMM10 XMM10 XMM11 XMM15'
    - 'VFMADD132PDr XMM13 XMM13 XMM15 XMM15'
    - 'VFMADD132PDr XMM12 XMM12 XMM11 XMM1'
    - 'VFMADD132PDr XMM0 XMM0 XMM6 XMM9'
    - 'VFMADD132PDr XMM2 XMM2 XMM15 XMM11'
  config:          ''
  register_initial_values:
    - 'XMM3=0x0'
    - 'XMM4=0x0'
    - 'XMM8=0x0'
    - 'MXCSR=0x0'
    - 'XMM5=0x0'
    - 'XMM14=0x0'
    - 'XMM7=0x0'
    - 'XMM10=0x0'
    - 'XMM11=0x0'
    - 'XMM15=0x0'
    - 'XMM13=0x0'
    - 'XMM12=0x0'
    - 'XMM1=0x0'
    - 'XMM0=0x0'
    - 'XMM6=0x0'
    - 'XMM9=0x0'
    - 'XMM2=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.6403, per_snippet_value: 4.4821 }
error:           ''
info:            instruction has tied variables, avoiding Read-After-Write issue, picking random def and use registers not aliasing each other, randomizing registers for uses
assembled_snippet: 4883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F04244883C4104883EC04C70424801F0000C5F8AE14244883C4044883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F14244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F14244883C410C4C2D998D8C4E28998EFC442A198D7C4428198EFC462A198E1C4C2C998C1C4C28198D3C4C2D998D8C4E28998EFC442A198D7C4428198EFC462A198E1C4C2C998C1C4C28198D3C4C2D998D8C4E28998EFC442A198D7C4428198EFC462A198E1C4C2C998C1C4C28198D3C4C2D998D8C4E28998EFC442A198D7C4428198EFC462A198E1C4C2C998C1C4C28198D3C3
...
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-f05c2f.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'VFMADD132PDr XMM15 XMM15 XMM11 XMM2'
    - 'VFMADD132PDr XMM5 XMM5 XMM11 XMM2'
    - 'VFMADD132PDr XMM14 XMM14 XMM11 XMM2'
    - 'VFMADD132PDr XMM4 XMM4 XMM11 XMM2'
    - 'VFMADD132PDr XMM8 XMM8 XMM11 XMM2'
    - 'VFMADD132PDr XMM3 XMM3 XMM11 XMM2'
    - 'VFMADD132PDr XMM10 XMM10 XMM11 XMM2'
    - 'VFMADD132PDr XMM7 XMM7 XMM11 XMM2'
    - 'VFMADD132PDr XMM13 XMM13 XMM11 XMM2'
    - 'VFMADD132PDr XMM9 XMM9 XMM11 XMM2'
    - 'VFMADD132PDr XMM1 XMM1 XMM11 XMM2'
    - 'VFMADD132PDr XMM6 XMM6 XMM11 XMM2'
    - 'VFMADD132PDr XMM0 XMM0 XMM11 XMM2'
    - 'VFMADD132PDr XMM12 XMM12 XMM11 XMM2'
  config:          ''
  register_initial_values:
    - 'XMM15=0x0'
    - 'XMM11=0x0'
    - 'XMM2=0x0'
    - 'MXCSR=0x0'
    - 'XMM5=0x0'
    - 'XMM14=0x0'
    - 'XMM4=0x0'
    - 'XMM8=0x0'
    - 'XMM3=0x0'
    - 'XMM10=0x0'
    - 'XMM7=0x0'
    - 'XMM13=0x0'
    - 'XMM9=0x0'
    - 'XMM1=0x0'
    - 'XMM6=0x0'
    - 'XMM0=0x0'
    - 'XMM12=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.5312, per_snippet_value: 7.4368 }
error:           ''
info:            instruction has tied variables, avoiding Read-After-Write issue, picking random def and use registers not aliasing each other, one unique register for each use position
assembled_snippet: 4883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F14244883C4104883EC04C70424801F0000C5F8AE14244883C4044883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F14244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F24244883C410C462A198FAC4E2A198EAC462A198F2C4E2A198E2C462A198C2C4E2A198DAC462A198D2C4E2A198FAC462A198EAC462A198CAC4E2A198CAC4E2A198F2C4E2A198C2C462A198E2C462A198FAC4E2A198EAC462A198F2C4E2A198E2C462A198C2C4E2A198DAC462A198D2C4E2A198FAC462A198EAC462A198CAC4E2A198CAC4E2A198F2C4E2A198C2C462A198E2C462A198FAC4E2A198EAC462A198F2C4E2A198E2C462A198C2C4E2A198DAC462A198D2C4E2A198FAC462A198EAC462A198CAC4E2A198CAC4E2A198F2C4E2A198C2C462A198E2C462A198FAC4E2A198EAC462A198F2C4E2A198E2C462A198C2C4E2A198DAC462A198D2C4E2A198FAC462A198EAC462A198CAC4E2A198CAC4E2A198F2C4E2A198C2C462A198E2C3
...
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-c32060.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'VFMADD132PDr XMM10 XMM10 XMM6 XMM6'
    - 'VFMADD132PDr XMM8 XMM8 XMM6 XMM6'
    - 'VFMADD132PDr XMM12 XMM12 XMM6 XMM6'
    - 'VFMADD132PDr XMM9 XMM9 XMM6 XMM6'
    - 'VFMADD132PDr XMM7 XMM7 XMM6 XMM6'
    - 'VFMADD132PDr XMM1 XMM1 XMM6 XMM6'
    - 'VFMADD132PDr XMM0 XMM0 XMM6 XMM6'
    - 'VFMADD132PDr XMM5 XMM5 XMM6 XMM6'
    - 'VFMADD132PDr XMM11 XMM11 XMM6 XMM6'
    - 'VFMADD132PDr XMM2 XMM2 XMM6 XMM6'
    - 'VFMADD132PDr XMM15 XMM15 XMM6 XMM6'
    - 'VFMADD132PDr XMM3 XMM3 XMM6 XMM6'
    - 'VFMADD132PDr XMM14 XMM14 XMM6 XMM6'
    - 'VFMADD132PDr XMM4 XMM4 XMM6 XMM6'
    - 'VFMADD132PDr XMM13 XMM13 XMM6 XMM6'
  config:          ''
  register_initial_values:
    - 'XMM10=0x0'
    - 'XMM6=0x0'
    - 'MXCSR=0x0'
    - 'XMM8=0x0'
    - 'XMM12=0x0'
    - 'XMM9=0x0'
    - 'XMM7=0x0'
    - 'XMM1=0x0'
    - 'XMM0=0x0'
    - 'XMM5=0x0'
    - 'XMM11=0x0'
    - 'XMM2=0x0'
    - 'XMM15=0x0'
    - 'XMM3=0x0'
    - 'XMM14=0x0'
    - 'XMM4=0x0'
    - 'XMM13=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.5311, per_snippet_value: 7.9665 }
error:           ''
info:            instruction has tied variables, avoiding Read-After-Write issue, picking random def and use registers not aliasing each other, reusing the same register for all uses
assembled_snippet: 4883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F14244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F34244883C4104883EC04C70424801F0000C5F8AE14244883C4044883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F14244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F2C244883C410C462C998D6C462C998C6C462C998E6C462C998CEC4E2C998FEC4E2C998CEC4E2C998C6C4E2C998EEC462C998DEC4E2C998D6C462C998FEC4E2C998DEC462C998F6C4E2C998E6C462C998EEC462C998D6C462C998C6C462C998E6C462C998CEC4E2C998FEC4E2C998CEC4E2C998C6C4E2C998EEC462C998DEC4E2C998D6C462C998FEC4E2C998DEC462C998F6C4E2C998E6C462C998EEC462C998D6C462C998C6C462C998E6C462C998CEC4E2C998FEC4E2C998CEC4E2C998C6C4E2C998EEC462C998DEC4E2C998D6C462C998FEC4E2C998DEC462C998F6C4E2C998E6C462C998EEC462C998D6C462C998C6C462C998E6C462C998CEC4E2C998FEC4E2C998CEC4E2C998C6C4E2C998EEC462C998DEC4E2C998D6C462C998FEC4E2C998DEC462C998F6C4E2C998E6C462C998EEC3
...

[lebedev.ri]

Err, an actual diff.

[lebedev.ri]

Ok, well, re-using the same use register will likely hit zero idioms and such in some cases,
so let's avoid that and look for one more pattern.

[lebedev.ri]

... and actually ensure that in SingleStaticUseRegPerOperand,
the operands actually won't match...

[RKSimon]

Thanks @lebedev.ri - I've noticed a few minors, but ideally @courbet or @gchatelet need to review this

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

117–147

(trivial) Not sure if we need the 'Use' prefix? RegRandomizationStrategy?

143

Keep MSVC happy:

llvm_unreachable("Unknown UseRegRandomizationStrategy enum");

169

(style) Avoid auto

198

(style) Avoid auto

[andreadb]

Much better thanks!

The first code snippet from your example is a bit too short for testing FMA throughput. However, if the tool is able to try different code snippets to get a sense of what the median throughput is, then it should be fine.

[lebedev.ri]

In D139283#3970319, @RKSimon wrote:

Thanks @lebedev.ri - I've noticed a few minors, but ideally @courbet or @gchatelet need to review this

Yeah. There are a few changes i had in mind here though.

In D139283#3970439, @andreadb wrote:

Much better thanks!

The first code snippet from your example is a bit too short for testing FMA throughput.

This is essentially due to random.
We now avoid picking overlapping defs/uses, so if we happened to pick
some reg for a use, instead of reusing some reg already-used for use
then we can not pick it for a def, and will run out of registers sooner,
thus shortening the sequence. I've certainly noticed this,
but not quite sure if there is anything to do about it yet.

However, if the tool is able to try different code snippets to get a sense of what the median throughput is, then it should be fine.

That is why that strategy now generates those two extra variants with at most one use reg / at most one use reg per operand.

[courbet]

The overall approach sounds good.

FYI, there is an other way to model all this, that we tried at one point: Simply use an SMT solver and generate constraints (LLVM already depends on S3). That was too slow though, so we abandoned it.

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

117–147

+1

135

[nit] getDescription ?

141

Are there cases when this is worse than the previous option ? I'm under the impression that we could just always do that.

178–232

Can you refactor this in a separate function ? It would make it clearer what state is only read and what state is modified by the loop.

[RKSimon]

random thought - how is exegesis handling the SSE PBLENDVB/BLENDVPS/BLENDVPD instructions? They have an explicit dependency on xmm0 as well which might also be causing issues

[lebedev.ri]

@RKSimon @courbet thank you for taking a look!
Addressing review notes.

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

141

If we only have a single register for all use positions,
then we may unintentionally stumble into zero idioms and such,
which is useful, but not always intended,
I think we should just keep all three choices here.

[lebedev.ri]

In D139283#3970982, @RKSimon wrote:

random thought - how is exegesis handling the SSE PBLENDVB/BLENDVPS/BLENDVPD instructions? They have an explicit dependency on xmm0 as well which might also be causing issues

Please let me know if this is bad, or i'm looking at the wrong instruction:

$ ./bin/llvm-exegesis --mode=inverse_throughput --opcode-name=BLENDVPSrr0 --max-configs-per-opcode=9182
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-77314f.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'BLENDVPSrr0 XMM1 XMM1 XMM5'
    - 'BLENDVPSrr0 XMM12 XMM12 XMM15'
    - 'BLENDVPSrr0 XMM14 XMM14 XMM9'
    - 'BLENDVPSrr0 XMM3 XMM3 XMM8'
    - 'BLENDVPSrr0 XMM7 XMM7 XMM4'
    - 'BLENDVPSrr0 XMM13 XMM13 XMM6'
    - 'BLENDVPSrr0 XMM10 XMM10 XMM8'
    - 'BLENDVPSrr0 XMM11 XMM11 XMM8'
    - 'BLENDVPSrr0 XMM2 XMM2 XMM8'
  config:          ''
  register_initial_values:
    - 'XMM1=0x0'
    - 'XMM5=0x0'
    - 'XMM0=0x0'
    - 'XMM12=0x0'
    - 'XMM15=0x0'
    - 'XMM14=0x0'
    - 'XMM9=0x0'
    - 'XMM3=0x0'
    - 'XMM8=0x0'
    - 'XMM7=0x0'
    - 'XMM4=0x0'
    - 'XMM13=0x0'
    - 'XMM6=0x0'
    - 'XMM10=0x0'
    - 'XMM11=0x0'
    - 'XMM2=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.5294, per_snippet_value: 4.7646 }
error:           ''
info:            instruction has tied variables, avoiding Read-After-Write issue, picking random def and use registers not aliasing each other, for uses, randomizing registers
assembled_snippet: 4883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F14244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F14244883C410660F3814CD66450F3814E766450F3814F166410F3814D8660F3814FC66440F3814EE66450F3814D066450F3814D866410F3814D0660F3814CD66450F3814E766450F3814F166410F3814D8660F3814FC66440F3814EE66450F3814D066450F3814D866410F3814D0660F3814CD66450F3814E766450F3814F166410F3814D8660F3814FC66440F3814EE66450F3814D066450F3814D866410F3814D0660F3814CD66450F3814E766450F3814F166410F3814D8660F3814FC66440F3814EE66450F3814D066450F3814D866410F3814D0C3
...
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-d0b778.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'BLENDVPSrr0 XMM15 XMM15 XMM9'
    - 'BLENDVPSrr0 XMM6 XMM6 XMM9'
    - 'BLENDVPSrr0 XMM13 XMM13 XMM9'
    - 'BLENDVPSrr0 XMM5 XMM5 XMM9'
    - 'BLENDVPSrr0 XMM11 XMM11 XMM9'
    - 'BLENDVPSrr0 XMM3 XMM3 XMM9'
    - 'BLENDVPSrr0 XMM10 XMM10 XMM9'
    - 'BLENDVPSrr0 XMM12 XMM12 XMM9'
    - 'BLENDVPSrr0 XMM8 XMM8 XMM9'
    - 'BLENDVPSrr0 XMM14 XMM14 XMM9'
    - 'BLENDVPSrr0 XMM1 XMM1 XMM9'
    - 'BLENDVPSrr0 XMM4 XMM4 XMM9'
    - 'BLENDVPSrr0 XMM7 XMM7 XMM9'
    - 'BLENDVPSrr0 XMM2 XMM2 XMM9'
  config:          ''
  register_initial_values:
    - 'XMM15=0x0'
    - 'XMM9=0x0'
    - 'XMM0=0x0'
    - 'XMM6=0x0'
    - 'XMM13=0x0'
    - 'XMM5=0x0'
    - 'XMM11=0x0'
    - 'XMM3=0x0'
    - 'XMM10=0x0'
    - 'XMM12=0x0'
    - 'XMM8=0x0'
    - 'XMM14=0x0'
    - 'XMM1=0x0'
    - 'XMM4=0x0'
    - 'XMM7=0x0'
    - 'XMM2=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.5291, per_snippet_value: 7.4074 }
error:           ''
info:            instruction has tied variables, avoiding Read-After-Write issue, picking random def and use registers not aliasing each other, for uses, one unique register for each position
assembled_snippet: 4883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F14244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F14244883C41066450F3814F966410F3814F166450F3814E966410F3814E966450F3814D966410F3814D966450F3814D166450F3814E166450F3814C166450F3814F166410F3814C966410F3814E166410F3814F966410F3814D166450F3814F966410F3814F166450F3814E966410F3814E966450F3814D966410F3814D966450F3814D166450F3814E166450F3814C166450F3814F166410F3814C966410F3814E166410F3814F966410F3814D166450F3814F966410F3814F166450F3814E966410F3814E966450F3814D966410F3814D966450F3814D166450F3814E166450F3814C166450F3814F166410F3814C966410F3814E166410F3814F966410F3814D166450F3814F966410F3814F166450F3814E966410F3814E966450F3814D966410F3814D966450F3814D166450F3814E166450F3814C166450F3814F166410F3814C966410F3814E166410F3814F966410F3814D1C3
...
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-9024ea.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'BLENDVPSrr0 XMM7 XMM7 XMM5'
    - 'BLENDVPSrr0 XMM15 XMM15 XMM5'
    - 'BLENDVPSrr0 XMM9 XMM9 XMM5'
    - 'BLENDVPSrr0 XMM14 XMM14 XMM5'
    - 'BLENDVPSrr0 XMM12 XMM12 XMM5'
    - 'BLENDVPSrr0 XMM3 XMM3 XMM5'
    - 'BLENDVPSrr0 XMM1 XMM1 XMM5'
    - 'BLENDVPSrr0 XMM6 XMM6 XMM5'
    - 'BLENDVPSrr0 XMM4 XMM4 XMM5'
    - 'BLENDVPSrr0 XMM10 XMM10 XMM5'
    - 'BLENDVPSrr0 XMM8 XMM8 XMM5'
    - 'BLENDVPSrr0 XMM13 XMM13 XMM5'
    - 'BLENDVPSrr0 XMM11 XMM11 XMM5'
    - 'BLENDVPSrr0 XMM2 XMM2 XMM5'
  config:          ''
  register_initial_values:
    - 'XMM7=0x0'
    - 'XMM5=0x0'
    - 'XMM0=0x0'
    - 'XMM15=0x0'
    - 'XMM9=0x0'
    - 'XMM14=0x0'
    - 'XMM12=0x0'
    - 'XMM3=0x0'
    - 'XMM1=0x0'
    - 'XMM6=0x0'
    - 'XMM4=0x0'
    - 'XMM10=0x0'
    - 'XMM8=0x0'
    - 'XMM13=0x0'
    - 'XMM11=0x0'
    - 'XMM2=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.5294, per_snippet_value: 7.4116 }
error:           ''
info:            instruction has tied variables, avoiding Read-After-Write issue, picking random def and use registers not aliasing each other, for uses, reusing the same register for all positions
assembled_snippet: 4883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F3C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F0C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F34244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F24244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F14244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F04244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F2C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C57A6F1C244883C4104883EC10C7042400000000C744240400000000C744240800000000C744240C00000000C5FA6F14244883C410660F3814FD66440F3814FD66440F3814CD66440F3814F566440F3814E5660F3814DD660F3814CD660F3814F5660F3814E566440F3814D566440F3814C566440F3814ED66440F3814DD660F3814D5660F3814FD66440F3814FD66440F3814CD66440F3814F566440F3814E5660F3814DD660F3814CD660F3814F5660F3814E566440F3814D566440F3814C566440F3814ED66440F3814DD660F3814D5660F3814FD66440F3814FD66440F3814CD66440F3814F566440F3814E5660F3814DD660F3814CD660F3814F5660F3814E566440F3814D566440F3814C566440F3814ED66440F3814DD660F3814D5660F3814FD66440F3814FD66440F3814CD66440F3814F566440F3814E5660F3814DD660F3814CD660F3814F5660F3814E566440F3814D566440F3814C566440F3814ED66440F3814DD660F3814D5C3
...

[lebedev.ri]

And take this to it's logical conclusion by deduplicating the codepaths with/without tied variables.
@courbet any further thoughts?

[lebedev.ri]

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

194

One thing i was thinking of, are there cases where we have
both defs with tied uses AND defs without tied uses?
If we have (which instruction is that?),
should we just always reuse the reg for defs without tied uses?

[RKSimon]

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

194

The weirdest x86 instructions for that kind of thing are some of the CMPXCHG reg-reg instructions - maybe some of the MUL/IMUL and DIV/IDIV variants as well?

[RKSimon]

Cheers - the blendv cases look ok (no defs/uses of xmm0 at all)

[lebedev.ri]

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

194

What i would like, is --dry-run option for exegesis,
to do everything, EXCEPT actually running the measurements.
It will help with test coverage, too.
If that option was present, i would have an easy way to check if there is such an opcode...

[RKSimon]

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

194

+1 - the need to have to install libPFM for most of the test coverage is limiting.

[lebedev.ri]

(@courbet waiting on you)

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

194

Great, i can try to look into that later.

[courbet]

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

141

Ack, thanks.

263

[nit] R

(for the record I also hate having uppercase variable names :) )

[lebedev.ri]

@courbet thank you for the review!
While there, i've also gone ahead, and added necessary constrains
to prevent generation of snippets with pointless strategies.

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

266–267

To be fair, one thing we don't do here, is elimination of unreasonable choices.
If there is only a single use reg, there is no difference
between SingleStaticUseRegPerOperand and SingleStaticUseReg.

[ormris]

This doesn't compile on GCC 7.5.0 (it's older but supported). See this buildbot: https://lab.llvm.org/staging/#/builders/235/builds/731

[lebedev.ri]

In D139283#3975371, @ormris wrote:

This doesn't compile on GCC 7.5.0 (it's older but supported). See this buildbot: https://lab.llvm.org/staging/#/builders/235/builds/731

That's not great. It's an obvious compiler bug.
Are you sure that GCC version is actually up to date?
https://godbolt.org/z/YaEd5P86Y

[lebedev.ri]

In D139283#3975452, @lebedev.ri wrote:

In D139283#3975371, @ormris wrote:

This doesn't compile on GCC 7.5.0 (it's older but supported). See this buildbot: https://lab.llvm.org/staging/#/builders/235/builds/731

That's not great. It's an obvious compiler bug.
Are you sure that GCC version is actually up to date?
https://godbolt.org/z/YaEd5P86Y

Nonetheless, attempted to workaround via e3f908a557d3e463353aad6b41a6fcd77d049c71.

[ormris]

Thanks! LG

llvm/tools/llvm-exegesis/lib/CodeTemplate.h

 // specified (i.e. some variables are not yet set). This allows the
 // SnippetGenerator to instantiate it many times with specific values to study
 // their impact on instruction's performance.
 struct CodeTemplate {
   CodeTemplate() = default;
 
   CodeTemplate(CodeTemplate &&);            // default
   CodeTemplate &operator=(CodeTemplate &&); // default
-  CodeTemplate(const CodeTemplate &) = delete;
-  CodeTemplate &operator=(const CodeTemplate &) = delete;
+
+  CodeTemplate clone() const;
 
   ExecutionMode Execution = ExecutionMode::UNKNOWN;
   // See InstructionBenchmarkKey.::Config.
   std::string Config;
   // Some information about how this template has been created.
   std::string Info;
   // The list of the instructions for this template.
   std::vector<InstructionTemplate> Instructions;
   // If the template uses the provided scratch memory, the register in which
   // the pointer to this memory is passed in to the function.
   unsigned ScratchSpacePointerInReg = 0;
+
+private:
+  CodeTemplate(const CodeTemplate &);            // default
+  CodeTemplate &operator=(const CodeTemplate &); // default
 };
 
 } // namespace exegesis
 } // namespace llvm
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_CODETEMPLATE_H

llvm/tools/llvm-exegesis/lib/CodeTemplate.cpp

 //===-- CodeTemplate.cpp ----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeTemplate.h"
 
 namespace llvm {
 namespace exegesis {
 
+CodeTemplate::CodeTemplate(const CodeTemplate &) = default;
+
 CodeTemplate::CodeTemplate(CodeTemplate &&) = default;
 
 CodeTemplate &CodeTemplate::operator=(CodeTemplate &&) = default;
 
+CodeTemplate &CodeTemplate::operator=(const CodeTemplate &) = default;
+
+CodeTemplate CodeTemplate::clone() const {
+  CodeTemplate CT = *this;
+  return CT;
+}
+
 InstructionTemplate::InstructionTemplate(const Instruction *Instr)
     : Instr(Instr), VariableValues(Instr->Variables.size()) {}
 
 InstructionTemplate::InstructionTemplate(InstructionTemplate &&) = default;
 
 InstructionTemplate &InstructionTemplate::
 operator=(InstructionTemplate &&) = default;
 

llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp

while (Instructions.size() < kMinNumDifferentAddresses) {
     ET.fillMemoryOperands(IT, ScratchSpacePointerInReg, I * MemStep);
     ++I;
     Instructions.push_back(std::move(IT));
   }
   assert(I * MemStep < BenchmarkRunner::ScratchSpace::kSize &&
          "not enough scratch space");
 }
 
-static std::vector<InstructionTemplate> generateSnippetUsingStaticRenaming(
+enum class UseRegRandomizationStrategy : uint8_t {
+  PickRandomRegs,
+  SingleStaticUseRegPerOperand,
+  SingleStaticUseReg,
+
+  FIRST = PickRandomRegs,
+  LAST = SingleStaticUseReg,
+};
+
+} // namespace exegesis
+
+template <>
+struct enum_iteration_traits<exegesis::UseRegRandomizationStrategy> {
+  static constexpr bool is_iterable = true;
+};
+
+namespace exegesis {
+
+const char *getName(UseRegRandomizationStrategy S) {
+  switch (S) {
+  case UseRegRandomizationStrategy::PickRandomRegs:
+    return "randomizing registers for uses";
+  case UseRegRandomizationStrategy::SingleStaticUseRegPerOperand:
+    return "one unique register for each use position";
+  case UseRegRandomizationStrategy::SingleStaticUseReg:
+    return "reusing the same register for all uses";
+  }
+}
+
+static std::vector<InstructionTemplate>
+generateSnippetForInstrWithTiedVariables(
     const LLVMState &State, const InstructionTemplate &IT,
     const ArrayRef<const Variable *> TiedVariables,
-    const BitVector &ForbiddenRegisters) {
-  std::vector<InstructionTemplate> Instructions;
-  // Assign registers to variables in a round-robin manner. This is simple but
-  // ensures that the most register-constrained variable does not get starved.
-  std::vector<BitVector> PossibleRegsForVar;
-  for (const Variable *Var : TiedVariables) {
-    assert(Var);
-    const Operand &Op = IT.getInstr().getPrimaryOperand(*Var);
-    assert(Op.isReg());
-    BitVector PossibleRegs = Op.getRegisterAliasing().sourceBits();
-    remove(PossibleRegs, ForbiddenRegisters);
-    PossibleRegsForVar.push_back(std::move(PossibleRegs));
+    UseRegRandomizationStrategy S, const BitVector &ForbiddenRegisters) {
+  // We don't want to accidentally serialize the instruction,
+  // so we must be sure that we don't pick a def that is an implicit use,
+  // or a use that is an implicit def, so record implicit regs now.
+  BitVector ImplicitUses(State.getRegInfo().getNumRegs());
+  BitVector ImplicitDefs(State.getRegInfo().getNumRegs());
+  for (const auto &Op : IT.getInstr().Operands) {
+    if (Op.isReg() && Op.isImplicit() && !Op.isMemory()) {
+      assert(Op.isImplicitReg() && "Not an implicit register operand?");
+      if (Op.isUse())
+        ImplicitUses.set(Op.getImplicitReg());
+      else {
+        assert(Op.isDef() && "Not a use and not a def?");
+        ImplicitDefs.set(Op.getImplicitReg());
+      }
     }
-  SmallVector<int, 2> Iterators(TiedVariables.size(), 0);
+  }
+  const auto ImplicitUseAliases =
+      getAliasedBits(State.getRegInfo(), ImplicitUses);
+  const auto ImplicitDefAliases =
+      getAliasedBits(State.getRegInfo(), ImplicitDefs);
+
+  BitVector Defs(State.getRegInfo().getNumRegs());
+  BitVector Uses(State.getRegInfo().getNumRegs());
+  std::vector<InstructionTemplate> Instructions;
+
   while (true) {
     InstructionTemplate TmpIT = IT;
-    // Find a possible register for each variable in turn, marking the
-    // register as taken.
-    for (size_t VarId = 0; VarId < TiedVariables.size(); ++VarId) {
-      const int NextPossibleReg =
-          PossibleRegsForVar[VarId].find_next(Iterators[VarId]);
-      if (NextPossibleReg <= 0) {
+    for (const auto &Op : IT.getInstr().Operands) {
+      if (Op.isReg() && Op.isExplicit() && !Op.isMemory() &&
+          !TmpIT.getValueFor(Op).isValid()) {
+        assert((!Op.isUse() || !Op.isTied()) &&
+               "Not expecting to see a tied use reg");
+        std::optional<size_t> RandomReg;
+        std::optional<MCOperand> MCOp;
+        if (Op.isUse()) {
+          switch (S) {
+          case UseRegRandomizationStrategy::PickRandomRegs:
+            break;
+          case UseRegRandomizationStrategy::SingleStaticUseReg:
+          case UseRegRandomizationStrategy::SingleStaticUseRegPerOperand: {
+            if (!Instructions.empty()) {
+              MCOp = Instructions.front().getValueFor(Op);
+              break;
+            }
+            if (S != UseRegRandomizationStrategy::SingleStaticUseReg)
+              break;
+            auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
+            const auto UseAliases = getAliasedBits(State.getRegInfo(), Uses);
+            if (auto CommonBit =
+                    getFirstCommonBit(PossibleRegisters, UseAliases))
+              RandomReg = *CommonBit;
+            break;
+          }
+          }
+        }
+        if (!MCOp && !RandomReg) {
+          auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
+          remove(PossibleRegisters, ForbiddenRegisters);
+          if (Op.isDef()) {
+            remove(PossibleRegisters, ImplicitUseAliases);
+            const auto UseAliases = getAliasedBits(State.getRegInfo(), Uses);
+            remove(PossibleRegisters, UseAliases);
+          }
+          if (Op.isUse())
+            remove(PossibleRegisters, ImplicitDefAliases);
+          // Now, important bit: neither do we want to reuse def registers, nor
+          // we want to use them as use registers. So def'd regs are off-limits!
+          const auto DefsAliases = getAliasedBits(State.getRegInfo(), Defs);
+          remove(PossibleRegisters, DefsAliases);
+          if (!PossibleRegisters.any())
             return Instructions;
+          RandomReg = randomBit(PossibleRegisters);
+        }
+        if (RandomReg) {
+          if (Op.isDef())
+            Defs.set(*RandomReg);
+          if (Op.isUse())
+            Uses.set(*RandomReg);
+          MCOp = MCOperand::createReg(*RandomReg);
         }
-      TmpIT.getValueFor(*TiedVariables[VarId]) =
-          MCOperand::createReg(NextPossibleReg);
-      // Bump iterator.
-      Iterators[VarId] = NextPossibleReg;
-      // Prevent other variables from using the register.
-      for (BitVector &OtherPossibleRegs : PossibleRegsForVar) {
-        OtherPossibleRegs.reset(NextPossibleReg);
+        assert(MCOp);
+        TmpIT.getValueFor(Op) = *MCOp;
       }
     }
     Instructions.push_back(std::move(TmpIT));
+    assert(Instructions.size() <= 128 && "Stuck in endless loop?");
   }
 }
 
 Expected<std::vector<CodeTemplate>>
 ParallelSnippetGenerator::generateCodeTemplates(
     InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const {
   const Instruction &Instr = Variant.getInstr();
   CodeTemplate CT;
if (SelfAliasing.empty()) {
     return getSingleton(std::move(CT));
   }
   if (SelfAliasing.hasImplicitAliasing()) {
     CT.Info = "instruction is serial, repeating a random one.";
     CT.Instructions.push_back(std::move(Variant));
     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
     return getSingleton(std::move(CT));
   }
   const auto TiedVariables = getVariablesWithTiedOperands(Instr);
   if (!TiedVariables.empty()) {
-    CT.Info = "instruction has tied variables, using static renaming.";
-    CT.Instructions = generateSnippetUsingStaticRenaming(
-        State, Variant, TiedVariables, ForbiddenRegisters);
-    instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
-    return getSingleton(std::move(CT));
+    std::vector<CodeTemplate> Result;
+    for (UseRegRandomizationStrategy S :
+         enum_seq_inclusive(UseRegRandomizationStrategy::FIRST,
+                            UseRegRandomizationStrategy::LAST)) {
+      CodeTemplate CurrCT = CT.clone();
+      CurrCT.Info = Twine("instruction has tied variables, avoiding "
+                          "Read-After-Write issue, picking random def and use "
+                          "registers not aliasing each other, ")
+                        .concat(getName(S))
+                        .str();
+      CurrCT.Instructions = generateSnippetForInstrWithTiedVariables(
+          State, Variant, TiedVariables, S, ForbiddenRegisters);
+      if (CurrCT.Instructions.empty())
+        return make_error<StringError>(
+            Twine("Failed to produce any snippet via: ").concat(CurrCT.Info),
+            inconvertibleErrorCode());
+      instantiateMemoryOperands(CurrCT.ScratchSpacePointerInReg,
+                                CurrCT.Instructions);
+      Result.push_back(std::move(CurrCT));
+    }
+    return Result;
   }
   // No tied variables, we pick random values for defs.
 
   // We don't want to accidentally serialize the instruction,
   // so we must be sure that we don't pick a def that is an implicit use,
   // or a use that is an implicit def, so record implicit regs now.
   BitVector ImplicitUses(State.getRegInfo().getNumRegs());
   BitVector ImplicitDefs(State.getRegInfo().getNumRegs());

llvm/tools/llvm-exegesis/lib/SnippetGenerator.h

 
 // Picks a random unsigned integer from 0 to Max (inclusive).
 size_t randomIndex(size_t Max);
 
 // Picks a random bit among the bits set in Vector and returns its index.
 // Precondition: Vector must have at least one bit set.
 size_t randomBit(const BitVector &Vector);
 
+// Picks a first bit that is common to these two vectors.
+std::optional<size_t> getFirstCommonBit(const BitVector &A, const BitVector &B);
+
 // Picks a random configuration, then selects a random def and a random use from
 // it and finally set the selected values in the provided InstructionInstances.
 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
                        InstructionTemplate &DefIB, InstructionTemplate &UseIB);
 
 // Assigns a Random Value to all Variables in IT that are still Invalid.
 // Do not use any of the registers in `ForbiddenRegs`.
 Error randomizeUnsetVariables(const LLVMState &State,
                               const BitVector &ForbiddenRegs,
                               InstructionTemplate &IT);
 
 } // namespace exegesis
 } // namespace llvm
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H

llvm/tools/llvm-exegesis/lib/SnippetGenerator.cpp

 size_t randomBit(const BitVector &Vector) {
   assert(Vector.any());
   auto Itr = Vector.set_bits_begin();
   for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
     ++Itr;
   return *Itr;
 }
 
+std::optional<size_t> getFirstCommonBit(const BitVector &A,
+                                        const BitVector &B) {
+  BitVector Intersect = A;
+  Intersect &= B;
+  int idx = Intersect.find_first();
+  if (idx != -1)
+    return idx;
+  return {};
+}
+
 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
                        InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
   assert(!AliasingConfigurations.empty());
   assert(!AliasingConfigurations.hasImplicitAliasing());
   const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
   setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
   setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
 }

llvm/unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp

 //===-- SnippetGeneratorTest.cpp --------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../Common/AssemblerUtils.h"
 #include "LlvmState.h"
 #include "MCInstrDescView.h"
 #include "ParallelSnippetGenerator.h"
 #include "RegisterAliasing.h"
 #include "SerialSnippetGenerator.h"
 #include "TestBase.h"
 #include "X86InstrInfo.h"
+#include "llvm/ADT/SetOperations.h"
 
 #include <unordered_set>
 
 namespace llvm {
 namespace exegesis {
 
 void InitializeX86ExegesisTarget();
 
 namespace {
 
 using testing::AnyOf;
 using testing::ElementsAre;
+using testing::Ge;
 using testing::Gt;
 using testing::HasSubstr;
+using testing::IsEmpty;
 using testing::Not;
 using testing::SizeIs;
 using testing::UnorderedElementsAre;
 
 MATCHER(IsInvalid, "") { return !arg.isValid(); }
 MATCHER(IsReg, "") { return arg.isReg(); }
 
 template <typename SnippetGeneratorT>
TEST_F(X86ParallelSnippetGeneratorTest, SerialInstruction) {
   EXPECT_THAT(CT.Info, HasSubstr("serial"));
   EXPECT_THAT(CT.Execution, ExecutionMode::UNKNOWN);
   ASSERT_THAT(CT.Instructions, SizeIs(1));
   const InstructionTemplate &IT = CT.Instructions[0];
   EXPECT_THAT(IT.getOpcode(), Opcode);
   ASSERT_THAT(IT.getVariableValues(), SizeIs(0));
 }
 
-TEST_F(X86ParallelSnippetGeneratorTest, StaticRenaming) {
+TEST_F(X86ParallelSnippetGeneratorTest, ReadAfterWrite_CMOV32rr) {
   // CMOV32rr has tied variables, we enumerate the possible values to execute
   // as many in parallel as possible.
 
   // - CMOV32rr
   // - Op0 Explicit Def RegClass(GR32)
   // - Op1 Explicit Use RegClass(GR32) TiedToOp0
   // - Op2 Explicit Use RegClass(GR32)
   // - Op3 Explicit Use Immediate
   // - Op3 Implicit Use Reg(EFLAGS)
   // - Var0 [Op0,Op1]
   // - Var1 [Op2]
   // - hasTiedRegisters (execution is always serial)
   // - hasAliasingRegisters
   const unsigned Opcode = X86::CMOV32rr;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
-  ASSERT_THAT(CodeTemplates, SizeIs(1));
-  const auto &CT = CodeTemplates[0];
-  EXPECT_THAT(CT.Info, HasSubstr("static renaming"));
+  ASSERT_THAT(CodeTemplates, SizeIs(3));
+  for (const auto &CT : CodeTemplates) {
+    EXPECT_THAT(CT.Info, HasSubstr("avoiding Read-After-Write issue"));
+    EXPECT_THAT(CT.Execution, ExecutionMode::UNKNOWN);
+    ASSERT_GT(CT.Instructions.size(), 1U);
+    std::unordered_set<unsigned> AllDefRegisters;
+    std::unordered_set<unsigned> AllUseRegisters;
+    for (const auto &IT : CT.Instructions) {
+      ASSERT_THAT(IT.getVariableValues(), SizeIs(3));
+      AllDefRegisters.insert(IT.getVariableValues()[0].getReg());
+      AllUseRegisters.insert(IT.getVariableValues()[1].getReg());
+    }
+    EXPECT_THAT(AllDefRegisters, SizeIs(CT.Instructions.size()))
+        << "Each instruction writes to a different register";
+    EXPECT_THAT(AllUseRegisters, Not(IsEmpty()))
+        << "In total, some other registers are used";
+    auto AllDefAndUseRegs = AllUseRegisters;
+    llvm::set_intersect(AllDefAndUseRegs, AllDefRegisters); // A := A ^ B
+    EXPECT_THAT(AllDefAndUseRegs, IsEmpty())
+        << "No instruction uses any register defined by any of the "
+           "instructions";
+  }
+}
+
+TEST_F(X86ParallelSnippetGeneratorTest, ReadAfterWrite_VFMADD132PDr) {
+  // VFMADD132PDr has tied variables, we enumerate the possible values
+  // to execute as many in parallel as possible.
+
+  // - VFMADD132PDr
+  // - Op0 Explicit Def RegClass(XMM)
+  // - Op1 Explicit Use RegClass(XMM) TiedToOp0
+  // - Op2 Explicit Use RegClass(XMM)
+  // - Op3 Explicit Use RegClass(XMM)
+  // - Var0 [Op0,Op1]
+  // - Var1 [Op2]
+  // - Var2 [Op3]
+  // - hasTiedRegisters (execution is always serial)
+  // - hasAliasingRegisters
+  const unsigned Opcode = X86::VFMADD132PDr;
+  const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
+  ASSERT_THAT(CodeTemplates, SizeIs(3));
+  for (const auto &CT : CodeTemplates) {
+    EXPECT_THAT(CT.Info, HasSubstr("avoiding Read-After-Write issue"));
     EXPECT_THAT(CT.Execution, ExecutionMode::UNKNOWN);
-  constexpr const unsigned kInstructionCount = 15;
-  ASSERT_THAT(CT.Instructions, SizeIs(kInstructionCount));
+    ASSERT_GT(CT.Instructions.size(), 1U);
     std::unordered_set<unsigned> AllDefRegisters;
+    std::unordered_set<unsigned> AllUseRegisters;
     for (const auto &IT : CT.Instructions) {
       ASSERT_THAT(IT.getVariableValues(), SizeIs(3));
       AllDefRegisters.insert(IT.getVariableValues()[0].getReg());
+      AllUseRegisters.insert(IT.getVariableValues()[1].getReg());
+      AllUseRegisters.insert(IT.getVariableValues()[2].getReg());
     }
-  EXPECT_THAT(AllDefRegisters, SizeIs(kInstructionCount))
+    EXPECT_THAT(AllDefRegisters, SizeIs(CT.Instructions.size()))
         << "Each instruction writes to a different register";
+    EXPECT_THAT(AllUseRegisters, Not(IsEmpty()))
+        << "In total, some other registers are used";
+    auto AllDefAndUseRegs = AllUseRegisters;
+    llvm::set_intersect(AllDefAndUseRegs, AllDefRegisters); // A := A ^ B
+    EXPECT_THAT(AllDefAndUseRegs, IsEmpty())
+        << "No instruction uses any register defined by any of the "
+           "instructions";
+  }
 }
 
 TEST_F(X86ParallelSnippetGeneratorTest, NoTiedVariables) {
   // CMOV_GR32 has no tied variables, we make sure def and use are different
   // from each other.
 
   // - CMOV_GR32
   // - Op0 Explicit Def RegClass(GR32)