[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

115–116

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

141

Keep MSVC happy:

llvm_unreachable("Unknown UseRegRandomizationStrategy enum");

143

(style) Avoid auto

162

(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

115–116

+1

133

[nit] getDescription ?

139

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

142–267

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

139

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

158

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

158

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

158

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

158

+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

158

Great, i can try to look into that later.

[courbet]

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

139

Ack, thanks.

227

[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

318–319

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

 // they implicitly read and write from the same operand, e.g. ADC16rr reads
 // and writes from EFLAGS.
 // In that case we just use a greedy register assignment and hope for the
 // best.
 
 namespace llvm {
 namespace exegesis {
 
-static SmallVector<const Variable *, 8>
-getVariablesWithTiedOperands(const Instruction &Instr) {
+static bool hasVariablesWithTiedOperands(const Instruction &Instr) {
   SmallVector<const Variable *, 8> Result;
   for (const auto &Var : Instr.Variables)
     if (Var.hasTiedOperands())
-      Result.push_back(&Var);
-  return Result;
+      return true;
+  return false;
 }
 
 ParallelSnippetGenerator::~ParallelSnippetGenerator() = default;
 
 void ParallelSnippetGenerator::instantiateMemoryOperands(
     const unsigned ScratchSpacePointerInReg,
     std::vector<InstructionTemplate> &Instructions) const {
   if (ScratchSpacePointerInReg == 0)
while (Instructions.size() < kMinNumDifferentAddresses) {
     InstructionTemplate IT = Instructions[I % OriginalInstructionsSize];
     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(
-    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));
+enum class RegRandomizationStrategy : uint8_t {
+  PickRandomRegs,
+  SingleStaticRegPerOperand,
+  SingleStaticReg,
+
+  FIRST = PickRandomRegs,
+  LAST = SingleStaticReg,
+};
+
+} // namespace exegesis
+
+template <> struct enum_iteration_traits<exegesis::RegRandomizationStrategy> {
+  static constexpr bool is_iterable = true;
+};
+
+namespace exegesis {
+
+const char *getDescription(RegRandomizationStrategy S) {
+  switch (S) {
+  case RegRandomizationStrategy::PickRandomRegs:
+    return "randomizing registers";
+  case RegRandomizationStrategy::SingleStaticRegPerOperand:
+    return "one unique register for each position";
+  case RegRandomizationStrategy::SingleStaticReg:
+    return "reusing the same register for all positions";
+  }
+  llvm_unreachable("Unknown UseRegRandomizationStrategy enum");
+}
+
+static std::variant<std::nullopt_t, MCOperand, Register>
+generateSingleRegisterForInstrAvoidingDefUseOverlap(
+    const LLVMState &State, const BitVector &ForbiddenRegisters,
+    const BitVector &ImplicitUseAliases, const BitVector &ImplicitDefAliases,
+    const BitVector &Uses, const BitVector &Defs, const InstructionTemplate &IT,
+    const Operand &Op, const ArrayRef<InstructionTemplate> Instructions,
+    RegRandomizationStrategy S) {
+  const Instruction &Instr = IT.getInstr();
+  assert(Op.isReg() && Op.isExplicit() && !Op.isMemory() &&
+         !IT.getValueFor(Op).isValid());
+  assert((!Op.isUse() || !Op.isTied()) &&
+         "Not expecting to see a tied use reg");
+
+  if (Op.isUse()) {
+    switch (S) {
+    case RegRandomizationStrategy::PickRandomRegs:
+      break;
+    case RegRandomizationStrategy::SingleStaticReg:
+    case RegRandomizationStrategy::SingleStaticRegPerOperand: {
+      if (!Instructions.empty())
+        return Instructions.front().getValueFor(Op);
+      if (S != RegRandomizationStrategy::SingleStaticReg)
+        break;
+      BitVector PossibleRegisters = Op.getRegisterAliasing().sourceBits();
+      const BitVector UseAliases = getAliasedBits(State.getRegInfo(), Uses);
+      if (std::optional<int> CommonBit =
+              getFirstCommonBit(PossibleRegisters, UseAliases))
+        return *CommonBit;
+      break;
     }
-  SmallVector<int, 2> Iterators(TiedVariables.size(), 0);
-  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) {
-        return Instructions;
-      }
-      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);
-      }
-    }
-    Instructions.push_back(std::move(TmpIT));
+
+  BitVector PossibleRegisters = Op.getRegisterAliasing().sourceBits();
+  remove(PossibleRegisters, ForbiddenRegisters);
+
+  if (Op.isDef()) {
+    remove(PossibleRegisters, ImplicitUseAliases);
+    const BitVector UseAliases = getAliasedBits(State.getRegInfo(), Uses);
+    remove(PossibleRegisters, UseAliases);
+
+  if (Op.isUse()) {
+    remove(PossibleRegisters, ImplicitDefAliases);
+    // NOTE: in general, using same reg for multiple Use's is fine.
+    if (S == RegRandomizationStrategy::SingleStaticRegPerOperand) {
+      const BitVector UseAliases = getAliasedBits(State.getRegInfo(), Uses);
+      remove(PossibleRegisters, UseAliases);
     }
   }
 
-Expected<std::vector<CodeTemplate>>
-ParallelSnippetGenerator::generateCodeTemplates(
-    InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const {
-  const Instruction &Instr = Variant.getInstr();
-  CodeTemplate CT;
-  CT.ScratchSpacePointerInReg =
-      Instr.hasMemoryOperands()
-          ? State.getExegesisTarget().getScratchMemoryRegister(
-                State.getTargetMachine().getTargetTriple())
-          : 0;
-  const AliasingConfigurations SelfAliasing(Instr, Instr);
-  if (SelfAliasing.empty()) {
-    CT.Info = "instruction is parallel, repeating a random one.";
-    CT.Instructions.push_back(std::move(Variant));
-    instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
-    return getSingleton(std::move(CT));
+  bool IsDefWithTiedUse =
+      Instr.Variables[Op.getVariableIndex()].hasTiedOperands();
+  if (Op.isUse() || IsDefWithTiedUse) {
+    // Now, important bit: if we have used some register for def,
+    // then we can not use that same register for *any* use,
+    // be it either an untied use, or an use tied to a def.
+    // But def-ing same regs is fine, as long as there are no uses!
+    const BitVector DefsAliases = getAliasedBits(State.getRegInfo(), Defs);
+    remove(PossibleRegisters, DefsAliases);
   }
-  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));
-  }
-  // No tied variables, we pick random values for defs.
+
+  if (!PossibleRegisters.any())
+    return std::nullopt;
+
+  return randomBit(PossibleRegisters);
+
+static std::optional<InstructionTemplate>
+generateSingleSnippetForInstrAvoidingDefUseOverlap(
+    const LLVMState &State, const BitVector &ForbiddenRegisters,
+    const BitVector &ImplicitUseAliases, const BitVector &ImplicitDefAliases,
+    BitVector &Uses, BitVector &Defs, InstructionTemplate IT,
+    const ArrayRef<InstructionTemplate> Instructions,
+    RegRandomizationStrategy S) {
+  const Instruction &Instr = IT.getInstr();
+  for (const Operand &Op : Instr.Operands) {
+    if (!Op.isReg() || !Op.isExplicit() || Op.isMemory() ||
+        IT.getValueFor(Op).isValid())
+      continue;
+    assert((!Op.isUse() || !Op.isTied()) && "Will not get tied uses.");
+
+    std::variant<std::nullopt_t, MCOperand, Register> R =
+        generateSingleRegisterForInstrAvoidingDefUseOverlap(
+            State, ForbiddenRegisters, ImplicitUseAliases, ImplicitDefAliases,
+            Uses, Defs, IT, Op, Instructions, S);
+
+    if (std::holds_alternative<std::nullopt_t>(R))
+      return {};
+
+    MCOperand MCOp;
+    if (std::holds_alternative<MCOperand>(R))
+      MCOp = std::get<MCOperand>(R);
+    else {
+      Register RandomReg = std::get<Register>(R);
+      if (Op.isDef())
+        Defs.set(RandomReg);
+      if (Op.isUse())
+        Uses.set(RandomReg);
+      MCOp = MCOperand::createReg(RandomReg);
+    }
+    IT.getValueFor(Op) = MCOp;
+  }
+  return IT;
 
+static std::vector<InstructionTemplate>
+generateSnippetForInstrAvoidingDefUseOverlap(
+    const LLVMState &State, const InstructionTemplate &IT,
+    RegRandomizationStrategy 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 : Instr.Operands) {
+  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());
       }
     }
   }
-  const auto ImplicitUseAliases =
+  const BitVector ImplicitUseAliases =
       getAliasedBits(State.getRegInfo(), ImplicitUses);
-  const auto ImplicitDefAliases =
+  const BitVector ImplicitDefAliases =
       getAliasedBits(State.getRegInfo(), ImplicitDefs);
+
   BitVector Defs(State.getRegInfo().getNumRegs());
-  for (const auto &Op : Instr.Operands) {
-    if (Op.isReg() && Op.isExplicit() && Op.isDef() && !Op.isMemory()) {
-      auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
-      // Do not use forbidden registers and regs that are implicitly used.
-      // Note that we don't try to avoid using implicit defs explicitly.
-      remove(PossibleRegisters, ForbiddenRegisters);
-      remove(PossibleRegisters, ImplicitUseAliases);
-      if (!PossibleRegisters.any())
-        return make_error<StringError>(
-            Twine("no available registers:\ncandidates:\n")
-                .concat(debugString(State.getRegInfo(),
-                                    Op.getRegisterAliasing().sourceBits()))
-                .concat("\nforbidden:\n")
-                .concat(debugString(State.getRegInfo(), ForbiddenRegisters))
-                .concat("\nimplicit use:\n")
-                .concat(debugString(State.getRegInfo(), ImplicitUseAliases)),
-            inconvertibleErrorCode());
-      const auto RandomReg = randomBit(PossibleRegisters);
-      Defs.set(RandomReg);
-      Variant.getValueFor(Op) = MCOperand::createReg(RandomReg);
-    }
+  BitVector Uses(State.getRegInfo().getNumRegs());
+  std::vector<InstructionTemplate> Instructions;
+
+  while (true) {
+    std::optional<InstructionTemplate> TmpIT =
+        generateSingleSnippetForInstrAvoidingDefUseOverlap(
+            State, ForbiddenRegisters, ImplicitUseAliases, ImplicitDefAliases,
+            Uses, Defs, IT, Instructions, S);
+    if (!TmpIT)
+      return Instructions;
+    Instructions.push_back(std::move(*TmpIT));
+    if (!hasVariablesWithTiedOperands(IT.getInstr()))
+      return Instructions;
+    assert(Instructions.size() <= 128 && "Stuck in endless loop?");
   }
-  // And pick random use values that are not reserved and don't alias with defs.
-  // Note that we don't try to avoid using implicit uses explicitly.
-  const auto DefAliases = getAliasedBits(State.getRegInfo(), Defs);
-  for (const auto &Op : Instr.Operands) {
-    if (Op.isReg() && Op.isExplicit() && Op.isUse() && !Op.isMemory()) {
-      auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
-      remove(PossibleRegisters, ForbiddenRegisters);
-      remove(PossibleRegisters, DefAliases);
-      remove(PossibleRegisters, ImplicitDefAliases);
-      assert(PossibleRegisters.any() && "No register left to choose from");
-      const auto RandomReg = randomBit(PossibleRegisters);
-      Variant.getValueFor(Op) = MCOperand::createReg(RandomReg);
-    }
+
+Expected<std::vector<CodeTemplate>>
+ParallelSnippetGenerator::generateCodeTemplates(
+    InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const {
+  const Instruction &Instr = Variant.getInstr();
+  CodeTemplate CT;
+  CT.ScratchSpacePointerInReg =
+      Instr.hasMemoryOperands()
+          ? State.getExegesisTarget().getScratchMemoryRegister(
+                State.getTargetMachine().getTargetTriple())
+          : 0;
+  const AliasingConfigurations SelfAliasing(Instr, Instr);
+  if (SelfAliasing.empty()) {
+    CT.Info = "instruction is parallel, repeating a random one.";
+    CT.Instructions.push_back(std::move(Variant));
+    instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
+    return getSingleton(std::move(CT));
   }
-  CT.Info =
-      "instruction has no tied variables picking Uses different from defs";
+  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));
   }
+  std::vector<CodeTemplate> Result;
+  bool HasTiedOperands = hasVariablesWithTiedOperands(Instr);
+  // If there are no tied operands, then we don't want to "saturate backedge",
+  // and the template we will produce will have only a single instruction.
+  unsigned NumUntiedUseRegs = count_if(Instr.Operands, [](const Operand &Op) {
+    return Op.isReg() && Op.isExplicit() && !Op.isMemory() && Op.isUse() &&
+           !Op.isTied();
+  });
+  SmallVector<RegRandomizationStrategy, 3> Strategies;
+  if (HasTiedOperands || NumUntiedUseRegs >= 3)
+    Strategies.push_back(RegRandomizationStrategy::PickRandomRegs);
+  if (HasTiedOperands || NumUntiedUseRegs >= 2)
+    Strategies.push_back(RegRandomizationStrategy::SingleStaticRegPerOperand);
+  Strategies.push_back(RegRandomizationStrategy::SingleStaticReg);
+  for (RegRandomizationStrategy S : Strategies) {
+    CodeTemplate CurrCT = CT.clone();
+    CurrCT.Info =
+        Twine("instruction has ")
+            .concat(HasTiedOperands ? "" : "no ")
+            .concat("tied variables, avoiding "
+                    "Read-After-Write issue, picking random def and use "
+                    "registers not aliasing each other, for uses, ")
+            .concat(getDescription(S))
+            .str();
+    CurrCT.Instructions = generateSnippetForInstrAvoidingDefUseOverlap(
+        State, Variant, 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;
+}
 
 constexpr const size_t ParallelSnippetGenerator::kMinNumDifferentAddresses;
 
 } // namespace exegesis
 } // namespace llvm

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<int> 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<int> 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/PowerPC/SnippetGeneratorTest.cpp

TEST_F(PPCParallelSnippetGeneratorTest, MemoryUse) {
   // - Var0 [Op0]
   // - Var1 [Op1]
   // - Var2 [Op2]
   // - hasMemoryOperands
   // - hasAliasingRegisters
   const unsigned Opcode = PPC::LDX;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
-  const auto &CT = CodeTemplates[0];
-  EXPECT_THAT(CT.Info, HasSubstr("instruction has no tied variables picking "
-                                 "Uses different from defs"));
+  for (const auto &CT : CodeTemplates) {
+    EXPECT_THAT(CT.Info, HasSubstr("instruction has no tied variables"));
     EXPECT_THAT(CT.Execution, ExecutionMode::UNKNOWN);
     ASSERT_THAT(CT.Instructions,
                 SizeIs(ParallelSnippetGenerator::kMinNumDifferentAddresses));
     const InstructionTemplate &IT = CT.Instructions[0];
     EXPECT_THAT(IT.getOpcode(), Opcode);
     ASSERT_THAT(IT.getVariableValues(), SizeIs(3));
     EXPECT_EQ(IT.getVariableValues()[1].getReg(), PPC::X1);
     EXPECT_EQ(IT.getVariableValues()[2].getReg(), PPC::X13);
   }
+}
 
 } // namespace
 } // namespace exegesis
 } // namespace llvm

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)
   // - Op1 Explicit Use RegClass(GR32)
   // - Op2 Explicit Use RegClass(GR32)
   // - Op3 Explicit Use Immediate
   // - Op4 Implicit Use Reg(EFLAGS)
   // - Var0 [Op0]
   // - Var1 [Op1]
   // - Var2 [Op2]
   // - Var3 [Op3]
   // - hasAliasingRegisters
   const unsigned Opcode = X86::CMOV_GR32;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
-  ASSERT_THAT(CodeTemplates, SizeIs(1));
-  const auto &CT = CodeTemplates[0];
+  ASSERT_THAT(CodeTemplates, SizeIs(2));
+  for (const auto &CT : CodeTemplates) {
     EXPECT_THAT(CT.Info, HasSubstr("no tied variables"));
     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(4));
     EXPECT_THAT(IT.getVariableValues()[0].getReg(),
                 Not(IT.getVariableValues()[1].getReg()))
         << "Def is different from first Use";
     EXPECT_THAT(IT.getVariableValues()[0].getReg(),
                 Not(IT.getVariableValues()[2].getReg()))
         << "Def is different from second Use";
     EXPECT_THAT(IT.getVariableValues()[3], IsInvalid());
   }
+}
 
 TEST_F(X86ParallelSnippetGeneratorTest, MemoryUse) {
   // Mov32rm reads from memory.
   // - MOV32rm
   // - Op0 Explicit Def RegClass(GR32)
   // - Op1 Explicit Use Memory RegClass(GR8)
   // - Op2 Explicit Use Memory
   // - Op3 Explicit Use Memory RegClass(GRH8)
   // - Op4 Explicit Use Memory
   // - Op5 Explicit Use Memory RegClass(SEGMENT_REG)
   // - Var0 [Op0]
   // - Var1 [Op1]
   // - Var2 [Op2]
   // - Var3 [Op3]
   // - Var4 [Op4]
   // - Var5 [Op5]
   // - hasMemoryOperands
   // - hasAliasingRegisters
   const unsigned Opcode = X86::MOV32rm;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
-  const auto &CT = CodeTemplates[0];
+  for (const auto &CT : CodeTemplates) {
     EXPECT_THAT(CT.Info, HasSubstr("no tied variables"));
     EXPECT_THAT(CT.Execution, ExecutionMode::UNKNOWN);
     ASSERT_THAT(CT.Instructions,
                 SizeIs(ParallelSnippetGenerator::kMinNumDifferentAddresses));
     const InstructionTemplate &IT = CT.Instructions[0];
     EXPECT_THAT(IT.getOpcode(), Opcode);
     ASSERT_THAT(IT.getVariableValues(), SizeIs(6));
     EXPECT_EQ(IT.getVariableValues()[2].getImm(), 1);
     EXPECT_EQ(IT.getVariableValues()[3].getReg(), 0u);
     EXPECT_EQ(IT.getVariableValues()[4].getImm(), 0);
     EXPECT_EQ(IT.getVariableValues()[5].getReg(), 0u);
   }
+}
 
 TEST_F(X86ParallelSnippetGeneratorTest, MOV16ms) {
   const unsigned Opcode = X86::MOV16ms;
   const Instruction &Instr = State.getIC().getInstr(Opcode);
   std::vector<BenchmarkCode> Benchmarks;
   auto Err = Generator.generateConfigurations(&Instr, Benchmarks,
                                               State.getRATC().emptyRegisters());
   EXPECT_TRUE((bool)Err);
TEST_F(X86ParallelSnippetGeneratorTest,
   AllRegisters.reset(X86::RDX);
   AllRegisters.reset(X86::EDX);
   AllRegisters.reset(X86::DX);
   AllRegisters.reset(X86::DH);
   AllRegisters.reset(X86::DL);
   auto Err = Generator.generateCodeTemplates(&Instr, AllRegisters);
   EXPECT_FALSE((bool)Err);
   EXPECT_THAT(toString(Err.takeError()),
-              testing::HasSubstr("no available registers"));
+              testing::HasSubstr("Failed to produce any snippet"));
 }
 
 class X86FakeSnippetGenerator : public SnippetGenerator {
 public:
   X86FakeSnippetGenerator(const LLVMState &State, const Options &Opts)
       : SnippetGenerator(State, Opts) {}
 
   const Instruction &getInstr(unsigned Opcode) {