unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp - llvm-project/llvm - Git at Google

 //===-- 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 <unordered_set>

 namespace llvm {
 namespace exegesis {

 void InitializeX86ExegesisTarget();

 namespace {

 using testing::AnyOf;
 using testing::ElementsAre;
 using testing::Gt;
 using testing::HasSubstr;
 using testing::Not;
 using testing::SizeIs;
 using testing::UnorderedElementsAre;

 MATCHER(IsInvalid, "") { return !arg.isValid(); }
 MATCHER(IsReg, "") { return arg.isReg(); }

 class X86SnippetGeneratorTest : public X86TestBase {
 protected:
   X86SnippetGeneratorTest() : InstrInfo(State.getInstrInfo()) {}

   const MCInstrInfo &InstrInfo;
 };

 template <typename SnippetGeneratorT>
 class SnippetGeneratorTest : public X86SnippetGeneratorTest {
 protected:
   SnippetGeneratorTest() : Generator(State, SnippetGenerator::Options()) {}

   std::vector<CodeTemplate> checkAndGetCodeTemplates(unsigned Opcode) {
     randomGenerator().seed(0); // Initialize seed.
     const Instruction &Instr = State.getIC().getInstr(Opcode);
     auto CodeTemplateOrError = Generator.generateCodeTemplates(
         &Instr, State.getRATC().emptyRegisters());
     EXPECT_FALSE(CodeTemplateOrError.takeError()); // Valid configuration.
     return std::move(CodeTemplateOrError.get());
   }

   SnippetGeneratorT Generator;
 };

 using SerialSnippetGeneratorTest = SnippetGeneratorTest<SerialSnippetGenerator>;

 using ParallelSnippetGeneratorTest =
     SnippetGeneratorTest<ParallelSnippetGenerator>;

 TEST_F(SerialSnippetGeneratorTest, ImplicitSelfDependencyThroughImplicitReg) {
   // - ADC16i16
   // - Op0 Explicit Use Immediate
   // - Op1 Implicit Def Reg(AX)
   // - Op2 Implicit Def Reg(EFLAGS)
   // - Op3 Implicit Use Reg(AX)
   // - Op4 Implicit Use Reg(EFLAGS)
   // - Var0 [Op0]
   // - hasAliasingImplicitRegisters (execution is always serial)
   // - hasAliasingRegisters
   const unsigned Opcode = X86::ADC16i16;
   EXPECT_THAT(InstrInfo.get(Opcode).getImplicitDefs()[0], X86::AX);
   EXPECT_THAT(InstrInfo.get(Opcode).getImplicitDefs()[1], X86::EFLAGS);
   EXPECT_THAT(InstrInfo.get(Opcode).getImplicitUses()[0], X86::AX);
   EXPECT_THAT(InstrInfo.get(Opcode).getImplicitUses()[1], X86::EFLAGS);
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
   const auto &CT = CodeTemplates[0];
   EXPECT_THAT(CT.Execution, ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS);
   ASSERT_THAT(CT.Instructions, SizeIs(1));
   const InstructionTemplate &IT = CT.Instructions[0];
   EXPECT_THAT(IT.getOpcode(), Opcode);
   ASSERT_THAT(IT.getVariableValues(), SizeIs(1)); // Imm.
   EXPECT_THAT(IT.getVariableValues()[0], IsInvalid()) << "Immediate is not set";
 }

 TEST_F(SerialSnippetGeneratorTest, ImplicitSelfDependencyThroughTiedRegs) {
   // - ADD16ri
   // - Op0 Explicit Def RegClass(GR16)
   // - Op1 Explicit Use RegClass(GR16) TiedToOp0
   // - Op2 Explicit Use Immediate
   // - Op3 Implicit Def Reg(EFLAGS)
   // - Var0 [Op0,Op1]
   // - Var1 [Op2]
   // - hasTiedRegisters (execution is always serial)
   // - hasAliasingRegisters
   const unsigned Opcode = X86::ADD16ri;
   EXPECT_THAT(InstrInfo.get(Opcode).getImplicitDefs()[0], X86::EFLAGS);
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
   const auto &CT = CodeTemplates[0];
   EXPECT_THAT(CT.Execution, ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS);
   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()[0], IsInvalid()) << "Operand 1 is not set";
   EXPECT_THAT(IT.getVariableValues()[1], IsInvalid()) << "Operand 2 is not set";
 }

 TEST_F(SerialSnippetGeneratorTest, ImplicitSelfDependencyThroughExplicitRegs) {
   // - VXORPSrr
   // - Op0 Explicit Def RegClass(VR128)
   // - Op1 Explicit Use RegClass(VR128)
   // - Op2 Explicit Use RegClass(VR128)
   // - Var0 [Op0]
   // - Var1 [Op1]
   // - Var2 [Op2]
   // - hasAliasingRegisters
   const unsigned Opcode = X86::VXORPSrr;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
   const auto &CT = CodeTemplates[0];
   EXPECT_THAT(CT.Execution, ExecutionMode::SERIAL_VIA_EXPLICIT_REGS);
   ASSERT_THAT(CT.Instructions, SizeIs(1));
   const InstructionTemplate &IT = CT.Instructions[0];
   EXPECT_THAT(IT.getOpcode(), Opcode);
   ASSERT_THAT(IT.getVariableValues(), SizeIs(3));
   EXPECT_THAT(IT.getVariableValues(),
               AnyOf(ElementsAre(IsReg(), IsInvalid(), IsReg()),
                     ElementsAre(IsReg(), IsReg(), IsInvalid())))
       << "Op0 is either set to Op1 or to Op2";
 }

 TEST_F(SerialSnippetGeneratorTest,
        ImplicitSelfDependencyThroughExplicitRegsForbidAll) {
   // - VXORPSrr
   // - Op0 Explicit Def RegClass(VR128)
   // - Op1 Explicit Use RegClass(VR128)
   // - Op2 Explicit Use RegClass(VR128)
   // - Var0 [Op0]
   // - Var1 [Op1]
   // - Var2 [Op2]
   // - hasAliasingRegisters
   const unsigned Opcode = X86::VXORPSrr;
   randomGenerator().seed(0); // Initialize seed.
   const Instruction &Instr = State.getIC().getInstr(Opcode);
   auto AllRegisters = State.getRATC().emptyRegisters();
   AllRegisters.flip();
   auto Error =
       Generator.generateCodeTemplates(&Instr, AllRegisters).takeError();
   EXPECT_TRUE((bool)Error);
   consumeError(std::move(Error));
 }

 TEST_F(SerialSnippetGeneratorTest, DependencyThroughOtherOpcode) {
   // - 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 auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(Gt(1U))) << "Many templates are available";
   for (const auto &CT : CodeTemplates) {
     EXPECT_THAT(CT.Execution, ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR);
     ASSERT_THAT(CT.Instructions, SizeIs(2));
     const InstructionTemplate &IT = CT.Instructions[0];
     EXPECT_THAT(IT.getOpcode(), Opcode);
     ASSERT_THAT(IT.getVariableValues(), SizeIs(2));
     EXPECT_THAT(IT.getVariableValues(),
                 AnyOf(ElementsAre(IsReg(), IsInvalid()),
                       ElementsAre(IsInvalid(), IsReg())));
     EXPECT_THAT(CT.Instructions[1].getOpcode(), Not(Opcode));
     // TODO: check that the two instructions alias each other.
   }
 }

 TEST_F(SerialSnippetGeneratorTest, LAHF) {
   // - LAHF
   // - Op0 Implicit Def Reg(AH)
   // - Op1 Implicit Use Reg(EFLAGS)
   const unsigned Opcode = X86::LAHF;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(Gt(1U))) << "Many templates are available";
   for (const auto &CT : CodeTemplates) {
     EXPECT_THAT(CT.Execution, ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR);
     ASSERT_THAT(CT.Instructions, SizeIs(2));
     const InstructionTemplate &IT = CT.Instructions[0];
     EXPECT_THAT(IT.getOpcode(), Opcode);
     ASSERT_THAT(IT.getVariableValues(), SizeIs(0));
   }
 }

 TEST_F(SerialSnippetGeneratorTest, VCVTUSI642SDZrrb_Int) {
   // - VCVTUSI642SDZrrb_Int
   // - Op0 Explicit Def RegClass(VR128X)
   // - Op1 Explicit Use RegClass(VR128X)
   // - Op2 Explicit Use STATIC_ROUNDING
   // - Op2 Explicit Use RegClass(GR64)
   // - Op4 Implicit Use Reg(MXSCR)
   const unsigned Opcode = X86::VCVTUSI642SDZrrb_Int;
   const Instruction &Instr = State.getIC().getInstr(Opcode);
   std::vector<BenchmarkCode> Configs;
   auto Error = Generator.generateConfigurations(
       &Instr, Configs, State.getRATC().emptyRegisters());
   ASSERT_FALSE(Error);
   ASSERT_THAT(Configs, SizeIs(1));
   const BenchmarkCode &BC = Configs[0];
   ASSERT_THAT(BC.Key.Instructions, SizeIs(1));
   ASSERT_TRUE(BC.Key.Instructions[0].getOperand(3).isImm());
 }

 TEST_F(ParallelSnippetGeneratorTest, ParallelInstruction) {
   // - BNDCL32rr
   // - Op0 Explicit Use RegClass(BNDR)
   // - Op1 Explicit Use RegClass(GR32)
   // - Var0 [Op0]
   // - Var1 [Op1]
   const unsigned Opcode = X86::BNDCL32rr;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
   const auto &CT = CodeTemplates[0];
   EXPECT_THAT(CT.Info, HasSubstr("parallel"));
   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()[0], IsInvalid());
   EXPECT_THAT(IT.getVariableValues()[1], IsInvalid());
 }

 TEST_F(ParallelSnippetGeneratorTest, SerialInstruction) {
   // - CDQ
   // - Op0 Implicit Def Reg(EAX)
   // - Op1 Implicit Def Reg(EDX)
   // - Op2 Implicit Use Reg(EAX)
   // - hasAliasingImplicitRegisters (execution is always serial)
   // - hasAliasingRegisters
   const unsigned Opcode = X86::CDQ;
   const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
   const auto &CT = CodeTemplates[0];
   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(ParallelSnippetGeneratorTest, StaticRenaming) {
   // 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"));
   EXPECT_THAT(CT.Execution, ExecutionMode::UNKNOWN);
   constexpr const unsigned kInstructionCount = 15;
   ASSERT_THAT(CT.Instructions, SizeIs(kInstructionCount));
   std::unordered_set<unsigned> AllDefRegisters;
   for (const auto &IT : CT.Instructions) {
     ASSERT_THAT(IT.getVariableValues(), SizeIs(3));
     AllDefRegisters.insert(IT.getVariableValues()[0].getReg());
   }
   EXPECT_THAT(AllDefRegisters, SizeIs(kInstructionCount))
       << "Each instruction writes to a different register";
 }

 TEST_F(ParallelSnippetGeneratorTest, 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];
   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(ParallelSnippetGeneratorTest, 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];
   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(ParallelSnippetGeneratorTest, 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"));
 }

 class FakeSnippetGenerator : public SnippetGenerator {
 public:
   FakeSnippetGenerator(const LLVMState &State, const Options &Opts)
       : SnippetGenerator(State, Opts) {}

   const Instruction &getInstr(unsigned Opcode) {
     return State.getIC().getInstr(Opcode);
   }

   InstructionTemplate getInstructionTemplate(unsigned Opcode) {
     return {&getInstr(Opcode)};
   }

 private:
   Expected<std::vector<CodeTemplate>>
   generateCodeTemplates(InstructionTemplate, const BitVector &) const override {
     return make_error<StringError>("not implemented", inconvertibleErrorCode());
   }
 };

 using FakeSnippetGeneratorTest = SnippetGeneratorTest<FakeSnippetGenerator>;

 testing::Matcher<const RegisterValue &> IsRegisterValue(unsigned Reg,
                                                         APInt Value) {
   return testing::AllOf(testing::Field(&RegisterValue::Register, Reg),
                         testing::Field(&RegisterValue::Value, Value));
 }

 TEST_F(FakeSnippetGeneratorTest, MemoryUse_Movsb) {
   // MOVSB writes to scratch memory register.
   // - MOVSB
   // - Op0 Explicit Use Memory RegClass(GR8)
   // - Op1 Explicit Use Memory RegClass(GR8)
   // - Op2 Explicit Use Memory RegClass(SEGMENT_REG)
   // - Op3 Implicit Def Reg(EDI)
   // - Op4 Implicit Def Reg(ESI)
   // - Op5 Implicit Use Reg(EDI)
   // - Op6 Implicit Use Reg(ESI)
   // - Op7 Implicit Use Reg(DF)
   // - Var0 [Op0]
   // - Var1 [Op1]
   // - Var2 [Op2]
   // - hasMemoryOperands
   // - hasAliasingImplicitRegisters (execution is always serial)
   // - hasAliasingRegisters
   const unsigned Opcode = X86::MOVSB;
   const Instruction &Instr = State.getIC().getInstr(Opcode);
   std::vector<BenchmarkCode> Benchmarks;
   auto Error = Generator.generateConfigurations(
       &Instr, Benchmarks, State.getRATC().emptyRegisters());
   EXPECT_TRUE((bool)Error);
   consumeError(std::move(Error));
 }

 TEST_F(FakeSnippetGeneratorTest, ComputeRegisterInitialValuesAdd16ri) {
   // ADD16ri:
   // explicit def 0       : reg RegClass=GR16
   // explicit use 1       : reg RegClass=GR16 | TIED_TO:0
   // explicit use 2       : imm
   // implicit def         : EFLAGS
   InstructionTemplate IT = Generator.getInstructionTemplate(X86::ADD16ri);
   IT.getValueFor(IT.getInstr().Variables[0]) = MCOperand::createReg(X86::AX);
   std::vector<InstructionTemplate> Snippet;
   Snippet.push_back(std::move(IT));
   const auto RIV = Generator.computeRegisterInitialValues(Snippet);
   EXPECT_THAT(RIV, ElementsAre(IsRegisterValue(X86::AX, APInt())));
 }

 TEST_F(FakeSnippetGeneratorTest, ComputeRegisterInitialValuesAdd64rr) {
   // ADD64rr:
   //  mov64ri rax, 42
   //  add64rr rax, rax, rbx
   // -> only rbx needs defining.
   std::vector<InstructionTemplate> Snippet;
   {
     InstructionTemplate Mov = Generator.getInstructionTemplate(X86::MOV64ri);
     Mov.getValueFor(Mov.getInstr().Variables[0]) =
         MCOperand::createReg(X86::RAX);
     Mov.getValueFor(Mov.getInstr().Variables[1]) = MCOperand::createImm(42);
     Snippet.push_back(std::move(Mov));
   }
   {
     InstructionTemplate Add = Generator.getInstructionTemplate(X86::ADD64rr);
     Add.getValueFor(Add.getInstr().Variables[0]) =
         MCOperand::createReg(X86::RAX);
     Add.getValueFor(Add.getInstr().Variables[1]) =
         MCOperand::createReg(X86::RBX);
     Snippet.push_back(std::move(Add));
   }

   const auto RIV = Generator.computeRegisterInitialValues(Snippet);
   EXPECT_THAT(RIV, ElementsAre(IsRegisterValue(X86::RBX, APInt())));
 }

 } // namespace
 } // namespace exegesis
 } // namespace llvm
	//===-- 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 <unordered_set>

	namespace llvm {
	namespace exegesis {

	void InitializeX86ExegesisTarget();

	namespace {

	using testing::AnyOf;
	using testing::ElementsAre;
	using testing::Gt;
	using testing::HasSubstr;
	using testing::Not;
	using testing::SizeIs;
	using testing::UnorderedElementsAre;

	MATCHER(IsInvalid, "") { return !arg.isValid(); }
	MATCHER(IsReg, "") { return arg.isReg(); }

	class X86SnippetGeneratorTest : public X86TestBase {
	protected:
	X86SnippetGeneratorTest() : InstrInfo(State.getInstrInfo()) {}

	const MCInstrInfo &InstrInfo;
	};

	template <typename SnippetGeneratorT>
	class SnippetGeneratorTest : public X86SnippetGeneratorTest {
	protected:
	SnippetGeneratorTest() : Generator(State, SnippetGenerator::Options()) {}

	std::vector<CodeTemplate> checkAndGetCodeTemplates(unsigned Opcode) {
	randomGenerator().seed(0); // Initialize seed.
	const Instruction &Instr = State.getIC().getInstr(Opcode);
	auto CodeTemplateOrError = Generator.generateCodeTemplates(
	&Instr, State.getRATC().emptyRegisters());
	EXPECT_FALSE(CodeTemplateOrError.takeError()); // Valid configuration.
	return std::move(CodeTemplateOrError.get());
	}

	SnippetGeneratorT Generator;
	};

	using SerialSnippetGeneratorTest = SnippetGeneratorTest<SerialSnippetGenerator>;

	using ParallelSnippetGeneratorTest =
	SnippetGeneratorTest<ParallelSnippetGenerator>;

	TEST_F(SerialSnippetGeneratorTest, ImplicitSelfDependencyThroughImplicitReg) {
	// - ADC16i16
	// - Op0 Explicit Use Immediate
	// - Op1 Implicit Def Reg(AX)
	// - Op2 Implicit Def Reg(EFLAGS)
	// - Op3 Implicit Use Reg(AX)
	// - Op4 Implicit Use Reg(EFLAGS)
	// - Var0 [Op0]
	// - hasAliasingImplicitRegisters (execution is always serial)
	// - hasAliasingRegisters
	const unsigned Opcode = X86::ADC16i16;
	EXPECT_THAT(InstrInfo.get(Opcode).getImplicitDefs()[0], X86::AX);
	EXPECT_THAT(InstrInfo.get(Opcode).getImplicitDefs()[1], X86::EFLAGS);
	EXPECT_THAT(InstrInfo.get(Opcode).getImplicitUses()[0], X86::AX);
	EXPECT_THAT(InstrInfo.get(Opcode).getImplicitUses()[1], X86::EFLAGS);
	const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
	ASSERT_THAT(CodeTemplates, SizeIs(1));
	const auto &CT = CodeTemplates[0];
	EXPECT_THAT(CT.Execution, ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS);
	ASSERT_THAT(CT.Instructions, SizeIs(1));
	const InstructionTemplate &IT = CT.Instructions[0];
	EXPECT_THAT(IT.getOpcode(), Opcode);
	ASSERT_THAT(IT.getVariableValues(), SizeIs(1)); // Imm.
	EXPECT_THAT(IT.getVariableValues()[0], IsInvalid()) << "Immediate is not set";
	}

	TEST_F(SerialSnippetGeneratorTest, ImplicitSelfDependencyThroughTiedRegs) {
	// - ADD16ri
	// - Op0 Explicit Def RegClass(GR16)
	// - Op1 Explicit Use RegClass(GR16) TiedToOp0
	// - Op2 Explicit Use Immediate
	// - Op3 Implicit Def Reg(EFLAGS)
	// - Var0 [Op0,Op1]
	// - Var1 [Op2]
	// - hasTiedRegisters (execution is always serial)
	// - hasAliasingRegisters
	const unsigned Opcode = X86::ADD16ri;
	EXPECT_THAT(InstrInfo.get(Opcode).getImplicitDefs()[0], X86::EFLAGS);
	const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
	ASSERT_THAT(CodeTemplates, SizeIs(1));
	const auto &CT = CodeTemplates[0];
	EXPECT_THAT(CT.Execution, ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS);
	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()[0], IsInvalid()) << "Operand 1 is not set";
	EXPECT_THAT(IT.getVariableValues()[1], IsInvalid()) << "Operand 2 is not set";
	}

	TEST_F(SerialSnippetGeneratorTest, ImplicitSelfDependencyThroughExplicitRegs) {
	// - VXORPSrr
	// - Op0 Explicit Def RegClass(VR128)
	// - Op1 Explicit Use RegClass(VR128)
	// - Op2 Explicit Use RegClass(VR128)
	// - Var0 [Op0]
	// - Var1 [Op1]
	// - Var2 [Op2]
	// - hasAliasingRegisters
	const unsigned Opcode = X86::VXORPSrr;
	const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
	ASSERT_THAT(CodeTemplates, SizeIs(1));
	const auto &CT = CodeTemplates[0];
	EXPECT_THAT(CT.Execution, ExecutionMode::SERIAL_VIA_EXPLICIT_REGS);
	ASSERT_THAT(CT.Instructions, SizeIs(1));
	const InstructionTemplate &IT = CT.Instructions[0];
	EXPECT_THAT(IT.getOpcode(), Opcode);
	ASSERT_THAT(IT.getVariableValues(), SizeIs(3));
	EXPECT_THAT(IT.getVariableValues(),
	AnyOf(ElementsAre(IsReg(), IsInvalid(), IsReg()),
	ElementsAre(IsReg(), IsReg(), IsInvalid())))
	<< "Op0 is either set to Op1 or to Op2";
	}

	TEST_F(SerialSnippetGeneratorTest,
	ImplicitSelfDependencyThroughExplicitRegsForbidAll) {
	// - VXORPSrr
	// - Op0 Explicit Def RegClass(VR128)
	// - Op1 Explicit Use RegClass(VR128)
	// - Op2 Explicit Use RegClass(VR128)
	// - Var0 [Op0]
	// - Var1 [Op1]
	// - Var2 [Op2]
	// - hasAliasingRegisters
	const unsigned Opcode = X86::VXORPSrr;
	randomGenerator().seed(0); // Initialize seed.
	const Instruction &Instr = State.getIC().getInstr(Opcode);
	auto AllRegisters = State.getRATC().emptyRegisters();
	AllRegisters.flip();
	auto Error =
	Generator.generateCodeTemplates(&Instr, AllRegisters).takeError();
	EXPECT_TRUE((bool)Error);
	consumeError(std::move(Error));
	}

	TEST_F(SerialSnippetGeneratorTest, DependencyThroughOtherOpcode) {
	// - 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 auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
	ASSERT_THAT(CodeTemplates, SizeIs(Gt(1U))) << "Many templates are available";
	for (const auto &CT : CodeTemplates) {
	EXPECT_THAT(CT.Execution, ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR);
	ASSERT_THAT(CT.Instructions, SizeIs(2));
	const InstructionTemplate &IT = CT.Instructions[0];
	EXPECT_THAT(IT.getOpcode(), Opcode);
	ASSERT_THAT(IT.getVariableValues(), SizeIs(2));
	EXPECT_THAT(IT.getVariableValues(),
	AnyOf(ElementsAre(IsReg(), IsInvalid()),
	ElementsAre(IsInvalid(), IsReg())));
	EXPECT_THAT(CT.Instructions[1].getOpcode(), Not(Opcode));
	// TODO: check that the two instructions alias each other.
	}
	}

	TEST_F(SerialSnippetGeneratorTest, LAHF) {
	// - LAHF
	// - Op0 Implicit Def Reg(AH)
	// - Op1 Implicit Use Reg(EFLAGS)
	const unsigned Opcode = X86::LAHF;
	const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
	ASSERT_THAT(CodeTemplates, SizeIs(Gt(1U))) << "Many templates are available";
	for (const auto &CT : CodeTemplates) {
	EXPECT_THAT(CT.Execution, ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR);
	ASSERT_THAT(CT.Instructions, SizeIs(2));
	const InstructionTemplate &IT = CT.Instructions[0];
	EXPECT_THAT(IT.getOpcode(), Opcode);
	ASSERT_THAT(IT.getVariableValues(), SizeIs(0));
	}
	}

	TEST_F(SerialSnippetGeneratorTest, VCVTUSI642SDZrrb_Int) {
	// - VCVTUSI642SDZrrb_Int
	// - Op0 Explicit Def RegClass(VR128X)
	// - Op1 Explicit Use RegClass(VR128X)
	// - Op2 Explicit Use STATIC_ROUNDING
	// - Op2 Explicit Use RegClass(GR64)
	// - Op4 Implicit Use Reg(MXSCR)
	const unsigned Opcode = X86::VCVTUSI642SDZrrb_Int;
	const Instruction &Instr = State.getIC().getInstr(Opcode);
	std::vector<BenchmarkCode> Configs;
	auto Error = Generator.generateConfigurations(
	&Instr, Configs, State.getRATC().emptyRegisters());
	ASSERT_FALSE(Error);
	ASSERT_THAT(Configs, SizeIs(1));
	const BenchmarkCode &BC = Configs[0];
	ASSERT_THAT(BC.Key.Instructions, SizeIs(1));
	ASSERT_TRUE(BC.Key.Instructions[0].getOperand(3).isImm());
	}

	TEST_F(ParallelSnippetGeneratorTest, ParallelInstruction) {
	// - BNDCL32rr
	// - Op0 Explicit Use RegClass(BNDR)
	// - Op1 Explicit Use RegClass(GR32)
	// - Var0 [Op0]
	// - Var1 [Op1]
	const unsigned Opcode = X86::BNDCL32rr;
	const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
	ASSERT_THAT(CodeTemplates, SizeIs(1));
	const auto &CT = CodeTemplates[0];
	EXPECT_THAT(CT.Info, HasSubstr("parallel"));
	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()[0], IsInvalid());
	EXPECT_THAT(IT.getVariableValues()[1], IsInvalid());
	}

	TEST_F(ParallelSnippetGeneratorTest, SerialInstruction) {
	// - CDQ
	// - Op0 Implicit Def Reg(EAX)
	// - Op1 Implicit Def Reg(EDX)
	// - Op2 Implicit Use Reg(EAX)
	// - hasAliasingImplicitRegisters (execution is always serial)
	// - hasAliasingRegisters
	const unsigned Opcode = X86::CDQ;
	const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
	ASSERT_THAT(CodeTemplates, SizeIs(1));
	const auto &CT = CodeTemplates[0];
	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(ParallelSnippetGeneratorTest, StaticRenaming) {
	// 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"));
	EXPECT_THAT(CT.Execution, ExecutionMode::UNKNOWN);
	constexpr const unsigned kInstructionCount = 15;
	ASSERT_THAT(CT.Instructions, SizeIs(kInstructionCount));
	std::unordered_set<unsigned> AllDefRegisters;
	for (const auto &IT : CT.Instructions) {
	ASSERT_THAT(IT.getVariableValues(), SizeIs(3));
	AllDefRegisters.insert(IT.getVariableValues()[0].getReg());
	}
	EXPECT_THAT(AllDefRegisters, SizeIs(kInstructionCount))
	<< "Each instruction writes to a different register";
	}

	TEST_F(ParallelSnippetGeneratorTest, 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];
	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(ParallelSnippetGeneratorTest, 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];
	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(ParallelSnippetGeneratorTest, 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"));
	}

	class FakeSnippetGenerator : public SnippetGenerator {
	public:
	FakeSnippetGenerator(const LLVMState &State, const Options &Opts)
	: SnippetGenerator(State, Opts) {}

	const Instruction &getInstr(unsigned Opcode) {
	return State.getIC().getInstr(Opcode);
	}

	InstructionTemplate getInstructionTemplate(unsigned Opcode) {
	return {&getInstr(Opcode)};
	}

	private:
	Expected<std::vector<CodeTemplate>>
	generateCodeTemplates(InstructionTemplate, const BitVector &) const override {
	return make_error<StringError>("not implemented", inconvertibleErrorCode());
	}
	};

	using FakeSnippetGeneratorTest = SnippetGeneratorTest<FakeSnippetGenerator>;

	testing::Matcher<const RegisterValue &> IsRegisterValue(unsigned Reg,
	APInt Value) {
	return testing::AllOf(testing::Field(&RegisterValue::Register, Reg),
	testing::Field(&RegisterValue::Value, Value));
	}

	TEST_F(FakeSnippetGeneratorTest, MemoryUse_Movsb) {
	// MOVSB writes to scratch memory register.
	// - MOVSB
	// - Op0 Explicit Use Memory RegClass(GR8)
	// - Op1 Explicit Use Memory RegClass(GR8)
	// - Op2 Explicit Use Memory RegClass(SEGMENT_REG)
	// - Op3 Implicit Def Reg(EDI)
	// - Op4 Implicit Def Reg(ESI)
	// - Op5 Implicit Use Reg(EDI)
	// - Op6 Implicit Use Reg(ESI)
	// - Op7 Implicit Use Reg(DF)
	// - Var0 [Op0]
	// - Var1 [Op1]
	// - Var2 [Op2]
	// - hasMemoryOperands
	// - hasAliasingImplicitRegisters (execution is always serial)
	// - hasAliasingRegisters
	const unsigned Opcode = X86::MOVSB;
	const Instruction &Instr = State.getIC().getInstr(Opcode);
	std::vector<BenchmarkCode> Benchmarks;
	auto Error = Generator.generateConfigurations(
	&Instr, Benchmarks, State.getRATC().emptyRegisters());
	EXPECT_TRUE((bool)Error);
	consumeError(std::move(Error));
	}

	TEST_F(FakeSnippetGeneratorTest, ComputeRegisterInitialValuesAdd16ri) {
	// ADD16ri:
	// explicit def 0 : reg RegClass=GR16
	// explicit use 1 : reg RegClass=GR16 \| TIED_TO:0
	// explicit use 2 : imm
	// implicit def : EFLAGS
	InstructionTemplate IT = Generator.getInstructionTemplate(X86::ADD16ri);
	IT.getValueFor(IT.getInstr().Variables[0]) = MCOperand::createReg(X86::AX);
	std::vector<InstructionTemplate> Snippet;
	Snippet.push_back(std::move(IT));
	const auto RIV = Generator.computeRegisterInitialValues(Snippet);
	EXPECT_THAT(RIV, ElementsAre(IsRegisterValue(X86::AX, APInt())));
	}

	TEST_F(FakeSnippetGeneratorTest, ComputeRegisterInitialValuesAdd64rr) {
	// ADD64rr:
	// mov64ri rax, 42
	// add64rr rax, rax, rbx
	// -> only rbx needs defining.
	std::vector<InstructionTemplate> Snippet;
	{
	InstructionTemplate Mov = Generator.getInstructionTemplate(X86::MOV64ri);
	Mov.getValueFor(Mov.getInstr().Variables[0]) =
	MCOperand::createReg(X86::RAX);
	Mov.getValueFor(Mov.getInstr().Variables[1]) = MCOperand::createImm(42);
	Snippet.push_back(std::move(Mov));
	}
	{
	InstructionTemplate Add = Generator.getInstructionTemplate(X86::ADD64rr);
	Add.getValueFor(Add.getInstr().Variables[0]) =
	MCOperand::createReg(X86::RAX);
	Add.getValueFor(Add.getInstr().Variables[1]) =
	MCOperand::createReg(X86::RBX);
	Snippet.push_back(std::move(Add));
	}

	const auto RIV = Generator.computeRegisterInitialValues(Snippet);
	EXPECT_THAT(RIV, ElementsAre(IsRegisterValue(X86::RBX, APInt())));
	}

	} // namespace
	} // namespace exegesis
	} // namespace llvm