[exegesis] `ParallelSnippetGenerator`: always use `RegRandomizationStrategy`

[lebedev.ri]

Summary

Even for instructions without tied operands, as long as
there are at least two untied use reg operands,
we may find something interesting by passing the same register.

In particular, we already know that CMP64rr & friends are dep-breaking,
and some of them are even 0-cycle zero-idioms.

$ /builddirs/llvm-project/build-Clang15/bin/llvm-exegesis -mode=inverse_throughput -opcode-name=CMP64rr -max-configs-per-opcode=1048576 --benchmarks-file=- --repetition-mode=loop --loop-body-size=1024 --num-repetitions=10240000
---
mode:            inverse_throughput
key:
  instructions:
    - 'CMP64rr RAX RSI'
  config:          ''
  register_initial_values:
    - 'RAX=0x0'
    - 'RSI=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10240000
measurements:
  - { key: inverse_throughput, value: 0.250251, per_snippet_value: 0.250251 }
error:           ''
info:            instruction is parallel, repeating a random one. For uses, one unique register for each position
assembled_snippet: 48B8000000000000000048BE000000000000000049B802000000000000004839F04839F04983C0FF75F4C3
...
---
mode:            inverse_throughput
key:
  instructions:
    - 'CMP64rr RSI RSI'
  config:          ''
  register_initial_values:
    - 'RSI=0x0'
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10240000
measurements:
  - { key: inverse_throughput, value: 0.166852, per_snippet_value: 0.166852 }
error:           ''
info:            instruction is parallel, repeating a random one. For uses, reusing the same register for all positions
assembled_snippet: 48BE000000000000000049B802000000000000004839F64839F64983C0FF75F4C3
...

[lebedev.ri]

(will only proceed after D140271.)

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

 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_PARALLELSNIPPETGENERATOR_H
 #define LLVM_TOOLS_LLVM_EXEGESIS_PARALLELSNIPPETGENERATOR_H
 
 #include "SnippetGenerator.h"
 
 namespace llvm {
 namespace exegesis {
 
+enum class RegRandomizationStrategy : uint8_t;
+
 class ParallelSnippetGenerator : public SnippetGenerator {
 public:
   using SnippetGenerator::SnippetGenerator;
   ~ParallelSnippetGenerator() override;
 
   Expected<std::vector<CodeTemplate>>
   generateCodeTemplates(InstructionTemplate Variant,
                         const BitVector &ForbiddenRegisters) const override;
 
   static constexpr const size_t kMinNumDifferentAddresses = 6;
 
 private:
+  void generateCodeTemplatesImpl(InstructionTemplate Variant, CodeTemplate &CT,
+                                 RegRandomizationStrategy Strategy,
+                                 const BitVector &ForbiddenRegisters) const;
+
   // Instantiates memory operands within a snippet.
   // To make computations as parallel as possible, we generate independant
   // memory locations for instructions that load and store. If there are less
   // than kMinNumDifferentAddresses in the original snippet, we duplicate
   // instructions until there are this number of instructions.
   // For example, assuming kMinNumDifferentAddresses=5 and
   // getMaxMemoryAccessSize()=64, if the original snippet is:
   //   mov eax, [memory]

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

 // and writes from EFLAGS.
 // In that case we just use a greedy register assignment and hope for the
 // best.
 
 namespace llvm {
 namespace exegesis {
 
 static bool hasVariablesWithTiedOperands(const Instruction &Instr) {
-  SmallVector<const Variable *, 8> Result;
   for (const auto &Var : Instr.Variables)
     if (Var.hasTiedOperands())
       return true;
   return false;
 }
 
 ParallelSnippetGenerator::~ParallelSnippetGenerator() = default;
 
if (!TmpIT)
       return Instructions;
     Instructions.push_back(std::move(*TmpIT));
     if (!hasVariablesWithTiedOperands(IT.getInstr()))
       return Instructions;
     assert(Instructions.size() <= 128 && "Stuck in endless loop?");
   }
 }
 
+void ParallelSnippetGenerator::generateCodeTemplatesImpl(
+    InstructionTemplate Variant, CodeTemplate &CT,
+    RegRandomizationStrategy Strategy,
+    const BitVector &ForbiddenRegisters) const {
+  const Instruction &Instr = Variant.getInstr();
+  const AliasingConfigurations SelfAliasing(Instr, Instr, ForbiddenRegisters);
+  if (SelfAliasing.empty()) {
+    CT.Info = "instruction is parallel, repeating a random one.";
+    CT.Instructions = generateSnippetForInstrAvoidingDefUseOverlap(
+        State, Variant, Strategy, ForbiddenRegisters);
+    return;
+  }
+  if (SelfAliasing.hasImplicitAliasing()) {
+    CT.Info = "instruction is serial, repeating a random one.";
+    CT.Instructions.push_back(std::move(Variant));
+    return;
+  }
+  {
+    bool HasTiedOperands = hasVariablesWithTiedOperands(Instr);
+    CT.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.")
+                  .str();
+    CT.Instructions = generateSnippetForInstrAvoidingDefUseOverlap(
+        State, Variant, Strategy, ForbiddenRegisters);
+    return;
+  }
+}
+
 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, ForbiddenRegisters);
-  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));
-  }
-  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.
+  SmallVector<RegRandomizationStrategy, 3> Strategies;
   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 (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))
+
+  std::vector<CodeTemplate> Results;
+  Results.reserve(Strategies.size());
+  for (RegRandomizationStrategy Strategy : Strategies) {
+    CodeTemplate CurrCT = CT.clone(); // FIXME: avoid clone for last strategy?
+    generateCodeTemplatesImpl(Variant, CurrCT, Strategy, ForbiddenRegisters);
+    CurrCT.Info = Twine(CurrCT.Info)
+                      .concat(" For uses, ")
+                      .concat(getDescription(Strategy))
                       .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());
+      continue;
     instantiateMemoryOperands(CurrCT.ScratchSpacePointerInReg,
                               CurrCT.Instructions);
-    Result.push_back(std::move(CurrCT));
+    Results.push_back(std::move(CurrCT));
   }
-  return Result;
+  if (Results.empty())
+    return make_error<Failure>("No strategy found to produce parallel snippet");
+  return std::move(Results);
 }
 
 constexpr const size_t ParallelSnippetGenerator::kMinNumDifferentAddresses;
 
 } // namespace exegesis
 } // namespace llvm

llvm/tools/llvm-exegesis/llvm-exegesis.cpp

static std::vector<unsigned> getOpcodesOrDie(const LLVMState &State) {
   }
   return Result;
 }
 
 // Generates code snippets for opcode `Opcode`.
 static Expected<std::vector<BenchmarkCode>>
 generateSnippets(const LLVMState &State, unsigned Opcode,
                  const BitVector &ForbiddenRegs) {
+  PrettyStackTraceFormat StackTrace("Generating snippets for opcode %u (%s)",
+                                    Opcode,
+                                    State.getInstrInfo().getName(Opcode));
+
   const Instruction &Instr = State.getIC().getInstr(Opcode);
   const MCInstrDesc &InstrDesc = Instr.Description;
   // Ignore instructions that we cannot run.
   if (InstrDesc.isPseudo() || InstrDesc.usesCustomInsertionHook())
     return make_error<Failure>(
         "Unsupported opcode: isPseudo/usesCustomInserter");
   if (InstrDesc.isBranch() || InstrDesc.isIndirectBranch())
     return make_error<Failure>("Unsupported opcode: isBranch/isIndirectBranch");

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

 
 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);
-  EXPECT_THAT(toString(std::move(Err)),
-              testing::HasSubstr("no available registers"));
+  EXPECT_THAT(
+      toString(std::move(Err)),
+      testing::HasSubstr("No strategy found to produce parallel snippet"));
 }
 
 TEST_F(X86ParallelSnippetGeneratorTest,
        AvoidSerializingThroughImplicitRegisters) {
   // MULX32rr implicitly uses EDX. We should not select that register to avoid
   // serialization.
   const unsigned Opcode = X86::MULX32rr;
   randomGenerator().seed(0); // Initialize seed.
   const Instruction &Instr = State.getIC().getInstr(Opcode);
   // Forbid all registers but RDX/EDX/DX/DH/DL. The only option would be to
   // choose that register, but that would serialize the instruction, so we
   // should be returning an error.
   auto AllRegisters = State.getRATC().emptyRegisters();
   AllRegisters.flip();
   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("Failed to produce any snippet"));
+  EXPECT_THAT(
+      toString(Err.takeError()),
+      testing::HasSubstr("No strategy found to produce parallel snippet"));
+}
+
+TEST_F(X86ParallelSnippetGeneratorTest, CMP64rr_idiom) {
+  // - CMP64rr
+  // - Op0 Explicit Use RegClass(GR64)
+  // - Op1 Explicit Use RegClass(GR64)
+  // - Op2 Implicit Def Reg(EFLAGS)
+  // - Var0 [Op0]
+  // - Var1 [Op1]
+  const unsigned Opcode = X86::CMP64rr;
+  const Instruction &Instr = State.getIC().getInstr(Opcode);
+  auto ForbiddenRegisters = State.getRATC().emptyRegisters();
+  ForbiddenRegisters.flip();
+  ForbiddenRegisters.reset(X86::RAX);
+  ForbiddenRegisters.reset(X86::RBX);
+  auto Error = Generator.generateCodeTemplates(&Instr, ForbiddenRegisters);
+  EXPECT_FALSE((bool)Error.takeError());
+  auto CodeTemplates = std::move(Error.get());
+  ASSERT_THAT(CodeTemplates, SizeIs(Gt(1U))) << "Many templates are available";
+  for (const auto &CT : CodeTemplates) {
+    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(2));
+    EXPECT_THAT(IT.getVariableValues(), ElementsAre(IsReg(), IsReg()));
+  }
+  {
+    const auto &CT = CodeTemplates[0];
+    EXPECT_THAT(
+        CT.Info,
+        testing::HasSubstr("instruction is parallel, repeating a random one. "
+                           "For uses, one unique register for each position"));
+    ArrayRef<MCOperand> VariableValues = CT.Instructions[0].getVariableValues();
+    ASSERT_NE(VariableValues[0].getReg(), VariableValues[1].getReg());
+  }
+  {
+    const auto &CT = CodeTemplates[1];
+    EXPECT_THAT(CT.Info,
+                testing::HasSubstr(
+                    "instruction is parallel, repeating a random one. For "
+                    "uses, reusing the same register for all positions"));
+    ArrayRef<MCOperand> VariableValues = CT.Instructions[0].getVariableValues();
+    ASSERT_EQ(VariableValues[0].getReg(), VariableValues[1].getReg());
+  }
 }
 
 class X86FakeSnippetGenerator : public SnippetGenerator {
 public:
   X86FakeSnippetGenerator(const LLVMState &State, const Options &Opts)
       : SnippetGenerator(State, Opts) {}
 
   const Instruction &getInstr(unsigned Opcode) {