[llvm-exegeis] Computing Latency configuration upfront so we can generate many CodeTemplates at once.

[gchatelet]

Summary

LatencyGenerator now computes all possible mode of serial execution for an Instruction upfront and generates CodeTemplate for the ones that give the best results (e.g. no need to generate a two instructions snippet when repeating a single one would do). The next step is to generate even more configurations for cases (e.g. for XOR we should generate "XOR EAX, EAX, EAX" and "XOR EAX, EAX, EBX")

[courbet]

tools/llvm-exegesis/lib/CodeTemplate.cpp

68

ditto

91

I can't convince myself that this is fine. Let's go through a static Execution[].

tools/llvm-exegesis/lib/CodeTemplate.h

51

please give an example for each one of these.

62

*powers

107

This is calling for buildbot failures (I remember that some compilers handle this differently). Let's rename one of these to ExecutionMode.

[courbet]

tools/llvm-exegesis/lib/CodeTemplate.h

53

There is a large difference between e.g. this one and SERIAL_VIA_IMPLICIT_REGS. The latter indicates that the inst is always serial, the former that it can be made serial. Maybe rename SERIAL_VIA_IMPLICIT_REGS to ALWAYS_SERIAL_VIA_IMPLICIT_REGS ?

53

Add doc for each one of these, e.g. "The instruction can be made serial by adding a back-to-back instruction that reads/writes to memory."

tools/llvm-exegesis/lib/Latency.cpp

67

back-to-back ? :D

67

I don't get this comment.

83

ditto

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

61

checkAndGetBestCodeTemplate

64

Please add a comment on generateCodeTemplates as to the order of templates.

[gchatelet]

-Addressing comments

[gchatelet]

• Remove dead code and fix comment

[gchatelet]

• Revert files from other commit to previous state

[gchatelet]

• Fix variable name

[courbet]

tools/llvm-exegesis/lib/CodeTemplate.cpp

69

why do you need this ? The type system should do that for you...

tools/llvm-exegesis/lib/CodeTemplate.h

60

This would be the case if you wrote to memory too, so add "/reads" after "clobbers"

70

Uses

78

doc ?

tools/llvm-exegesis/lib/Latency.cpp

85

ditto

tools/llvm-exegesis/lib/SnippetGenerator.cpp

25

pass by && ?

[gchatelet]

• Addressing comments

tools/llvm-exegesis/lib/CodeTemplate.h

 /// SnippetGenerator.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_CODETEMPLATE_H
 #define LLVM_TOOLS_LLVM_EXEGESIS_CODETEMPLATE_H
 
 #include "MCInstrDescView.h"
+#include "llvm/ADT/BitmaskEnum.h"
 
 namespace exegesis {
 
 // A template for an Instruction holding values for each of its Variables.
 struct InstructionTemplate {
   InstructionTemplate(const Instruction &Instr);
 
   InstructionTemplate(const InstructionTemplate &);            // default
struct InstructionTemplate {
   // to the corresponding variable values. Precondition: All VariableValues must
   // be set.
   llvm::MCInst build() const;
 
   Instruction Instr;
   llvm::SmallVector<llvm::MCOperand, 4> VariableValues;
 };
 
+enum class ExecutionMode : uint8_t {
+  UNKNOWN = 0U,
+  // The instruction is always serial because implicit Use and Def alias.
+  // e.g. AAA (alias via EFLAGS)
+  ALWAYS_SERIAL_VIA_IMPLICIT_REGS = 1u << 0,
+
+  // The instruction is always serial because one Def is tied to a Use.
+  // e.g. AND32ri (alias via tied GR32)
+  ALWAYS_SERIAL_VIA_TIED_REGS = 1u << 1,
+
+  // The execution can be made serial by inserting a second instruction that
+  // clobbers memory.
+  // e.g. MOV8rm
+  SERIAL_VIA_MEMORY_INSTR = 1u << 2,
+
+  // The execution can be made serial by picking one Def that aliases with one
+  // Use.
+  // e.g. VXORPSrr XMM1, XMM1, XMM2
+  SERIAL_VIA_EXPLICIT_REGS = 1u << 3,
+
+  // The execution can be made serial by inserting a second instruction that
+  // uses one of the Defs and defs one of the Use.
+  // e.g.
+  // 1st instruction: MMX_PMOVMSKBrr ECX, MM7
+  // 2nd instruction: MMX_MOVD64rr MM7, ECX
+  //  or instruction: MMX_MOVD64to64rr MM7, ECX
+  //  or instruction: MMX_PINSRWrr MM7, MM7, ECX, 1
+  SERIAL_VIA_NON_MEMORY_INSTR = 1u << 4,
+
+  PARALLEL_VIA_LACKING_OPERANDS = 1u << 5,
+  PARALLEL_VIA_EXPLICIT_REGS = 1u << 6,
+  LLVM_MARK_AS_BITMASK_ENUM(/*Largest*/ PARALLEL_VIA_EXPLICIT_REGS)
+};
+
+// Returns a human readable string for the enum.
+llvm::StringRef getName(ExecutionMode Execution);
+
+// Returns a sequence of increasing powers of two corresponding to all the
+// Execution flags.
+llvm::ArrayRef<ExecutionMode> getAllExecutionBits();
+
+// Decomposes Execution into individual set bits.
+llvm::SmallVector<ExecutionMode, 4> getExecutionModeBits(ExecutionMode);
+
+LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE();
+
 // A CodeTemplate is a set of InstructionTemplates that may not be fully
 // specified (i.e. some variables are not yet set). This allows the
-// BenchmarkRunner to instantiate it many times with specific values to study
+// 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;
 
+  ExecutionMode Execution = ExecutionMode::UNKNOWN;
   // 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;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_CODETEMPLATE_H

tools/llvm-exegesis/lib/CodeTemplate.cpp

llvm::MCInst InstructionTemplate::build() const {
   llvm::MCInst Result;
   Result.setOpcode(Instr.Description->Opcode);
   for (const auto &Op : Instr.Operands)
     if (Op.isExplicit())
       Result.addOperand(getValueFor(Op));
   return Result;
 }
 
+llvm::StringRef getName(ExecutionMode Bit) {
+  assert(llvm::isPowerOf2_32(static_cast<uint32_t>(Bit)) &&
+         "Bit must be a power of two");
+  switch (Bit) {
+  case ExecutionMode::UNKNOWN:
+    return "UNKNOWN";
+  case ExecutionMode::ALWAYS_SERIAL_VIA_IMPLICIT_REGS:
+    return "ALWAYS_SERIAL_VIA_IMPLICIT_REGS";
+  case ExecutionMode::ALWAYS_SERIAL_VIA_TIED_REGS:
+    return "ALWAYS_SERIAL_VIA_TIED_REGS";
+  case ExecutionMode::SERIAL_VIA_MEMORY_INSTR:
+    return "SERIAL_VIA_MEMORY_INSTR";
+  case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS:
+    return "SERIAL_VIA_EXPLICIT_REGS";
+  case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR:
+    return "SERIAL_VIA_NON_MEMORY_INSTR";
+  case ExecutionMode::PARALLEL_VIA_LACKING_OPERANDS:
+    return "PARALLEL_VIA_LACKING_OPERANDS";
+  case ExecutionMode::PARALLEL_VIA_EXPLICIT_REGS:
+    return "PARALLEL_VIA_EXPLICIT_REGS";
+  }
+  llvm_unreachable("Missing enum case");
+}
+
+static const ExecutionMode kAllExecutionModeBits[] = {
+    ExecutionMode::ALWAYS_SERIAL_VIA_IMPLICIT_REGS,
+    ExecutionMode::ALWAYS_SERIAL_VIA_TIED_REGS,
+    ExecutionMode::SERIAL_VIA_MEMORY_INSTR,
+    ExecutionMode::SERIAL_VIA_EXPLICIT_REGS,
+    ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR,
+    ExecutionMode::PARALLEL_VIA_LACKING_OPERANDS,
+    ExecutionMode::PARALLEL_VIA_EXPLICIT_REGS,
+};
+
+llvm::ArrayRef<ExecutionMode> getAllExecutionBits() {
+  return kAllExecutionModeBits;
+}
+
+llvm::SmallVector<ExecutionMode, 4>
+getExecutionModeBits(ExecutionMode Execution) {
+  llvm::SmallVector<ExecutionMode, 4> Result;
+  for (const auto Bit : getAllExecutionBits())
+    if ((Execution & Bit) == Bit)
+      Result.push_back(Bit);
+  return Result;
+}
+
 } // namespace exegesis

tools/llvm-exegesis/lib/Latency.h

 
 namespace exegesis {
 
 class LatencySnippetGenerator : public SnippetGenerator {
 public:
   LatencySnippetGenerator(const LLVMState &State) : SnippetGenerator(State) {}
   ~LatencySnippetGenerator() override;
 
-  llvm::Expected<CodeTemplate>
-  generateCodeTemplate(const Instruction &Instr) const override;
-
-private:
-  llvm::Expected<CodeTemplate>
-  generateTwoInstructionPrototype(const Instruction &Instr) const;
+  llvm::Expected<std::vector<CodeTemplate>>
+  generateCodeTemplates(const Instruction &Instr) const override;
 };
 
 class LatencyBenchmarkRunner : public BenchmarkRunner {
 public:
   LatencyBenchmarkRunner(const LLVMState &State)
       : BenchmarkRunner(State, InstructionBenchmark::Latency) {}
   ~LatencyBenchmarkRunner() override;
 

tools/llvm-exegesis/lib/Latency.cpp

 #include "PerfHelper.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstBuilder.h"
 #include "llvm/Support/FormatVariadic.h"
 
 namespace exegesis {
 
-LatencySnippetGenerator::~LatencySnippetGenerator() = default;
-
-llvm::Expected<CodeTemplate>
-LatencySnippetGenerator::generateTwoInstructionPrototype(
-    const Instruction &Instr) const {
+struct ExecutionClass {
+  ExecutionMode Mask;
+  const char *Description;
+} static const kExecutionClasses[] = {
+    {ExecutionMode::ALWAYS_SERIAL_VIA_IMPLICIT_REGS |
+         ExecutionMode::ALWAYS_SERIAL_VIA_TIED_REGS,
+     "Repeating a single implicitly serial instruction"},
+    {ExecutionMode::SERIAL_VIA_EXPLICIT_REGS,
+     "Repeating a single explicitly serial instruction"},
+    {ExecutionMode::SERIAL_VIA_MEMORY_INSTR |
+         ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR,
+     "Repeating two instructions"},
+};
+
+static constexpr size_t kMaxAliasingInstructions = 10;
+
+static std::vector<Instruction>
+computeAliasingInstructions(const LLVMState &State, const Instruction &Instr,
+                            size_t MaxAliasingInstructions) {
+  // Randomly iterate the set of instructions.
   std::vector<unsigned> Opcodes;
   Opcodes.resize(State.getInstrInfo().getNumOpcodes());
   std::iota(Opcodes.begin(), Opcodes.end(), 0U);
   std::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator());
+
+  std::vector<Instruction> AliasingInstructions;
   for (const unsigned OtherOpcode : Opcodes) {
-    if (OtherOpcode == Instr.Description->Opcode)
+    if (OtherOpcode == Instr.Description->getOpcode())
       continue;
     const Instruction OtherInstr(State, OtherOpcode);
     if (OtherInstr.hasMemoryOperands())
       continue;
+    if (Instr.hasAliasingRegistersThrough(OtherInstr))
+      AliasingInstructions.push_back(std::move(OtherInstr));
+    if (AliasingInstructions.size() >= MaxAliasingInstructions)
+      break;
+  }
+  return AliasingInstructions;
+}
+
+static ExecutionMode getExecutionModes(const Instruction &Instr) {
+  ExecutionMode EM;
+  if (Instr.hasAliasingImplicitRegisters())
+    EM |= ExecutionMode::ALWAYS_SERIAL_VIA_IMPLICIT_REGS;
+  if (Instr.hasTiedRegisters())
+    EM |= ExecutionMode::ALWAYS_SERIAL_VIA_TIED_REGS;
+  if (Instr.hasMemoryOperands())
+    EM |= ExecutionMode::SERIAL_VIA_MEMORY_INSTR;
+  else {
+    if (Instr.hasAliasingRegisters())
+      EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS;
+    if (Instr.hasOneUseOrOneDef())
+      EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR;
+  }
+  return EM;
+}
+
+static void appendCodeTemplates(const LLVMState &State,
+                                const Instruction &Instr,
+                                ExecutionMode ExecutionModeBit,
+                                llvm::StringRef ExecutionClassDescription,
+                                std::vector<CodeTemplate> &CodeTemplates) {
+  assert(llvm::isPowerOf2_32(static_cast<uint32_t>(ExecutionModeBit)) &&
+         "ExecutionModeBit must be a power of two");
+  switch (ExecutionModeBit) {
+  case ExecutionMode::ALWAYS_SERIAL_VIA_IMPLICIT_REGS:
+    // Nothing to do, the instruction is always serial.
+    LLVM_FALLTHROUGH;
+  case ExecutionMode::ALWAYS_SERIAL_VIA_TIED_REGS: {
+    // Picking whatever value for the tied variable will make the instruction
+    // serial.
+    CodeTemplate CT;
+    CT.Execution = ExecutionModeBit;
+    CT.Info = ExecutionClassDescription;
+    CT.Instructions.push_back(Instr);
+    CodeTemplates.push_back(std::move(CT));
+    return;
+  }
+  case ExecutionMode::SERIAL_VIA_MEMORY_INSTR: {
+    // Select back-to-back memory instruction.
+    // TODO: Implement me.
+    return;
+  }
+  case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS: {
+    // Making the execution of this instruction serial by selecting one def
+    // register to alias with one use register.
+    const AliasingConfigurations SelfAliasing(Instr, Instr);
+    assert(!SelfAliasing.empty() && !SelfAliasing.hasImplicitAliasing() &&
+           "Instr must alias itself explicitly");
+    InstructionTemplate IT(Instr);
+    // This is a self aliasing instruction so defs and uses are from the same
+    // instance, hence twice IT in the following call.
+    setRandomAliasing(SelfAliasing, IT, IT);
+    CodeTemplate CT;
+    CT.Execution = ExecutionModeBit;
+    CT.Info = ExecutionClassDescription;
+    CT.Instructions.push_back(std::move(IT));
+    CodeTemplates.push_back(std::move(CT));
+    return;
+  }
+  case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR: {
+    // Select back-to-back non-memory instruction.
+    for (const auto OtherInstr :
+         computeAliasingInstructions(State, Instr, kMaxAliasingInstructions)) {
       const AliasingConfigurations Forward(Instr, OtherInstr);
       const AliasingConfigurations Back(OtherInstr, Instr);
-    if (Forward.empty() || Back.empty())
-      continue;
       InstructionTemplate ThisIT(Instr);
       InstructionTemplate OtherIT(OtherInstr);
       if (!Forward.hasImplicitAliasing())
         setRandomAliasing(Forward, ThisIT, OtherIT);
       if (!Back.hasImplicitAliasing())
         setRandomAliasing(Back, OtherIT, ThisIT);
       CodeTemplate CT;
-    CT.Info = llvm::formatv("creating cycle through {0}.",
-                            State.getInstrInfo().getName(OtherOpcode));
+      CT.Execution = ExecutionModeBit;
+      CT.Info = ExecutionClassDescription;
       CT.Instructions.push_back(std::move(ThisIT));
       CT.Instructions.push_back(std::move(OtherIT));
-    return std::move(CT);
+      CodeTemplates.push_back(std::move(CT));
+    }
+    return;
+  }
+  default:
+    llvm_unreachable("Unhandled enum value");
   }
-  return llvm::make_error<BenchmarkFailure>(
-      "Infeasible : Didn't find any scheme to make the instruction serial");
 }
 
-llvm::Expected<CodeTemplate>
-LatencySnippetGenerator::generateCodeTemplate(const Instruction &Instr) const {
-  if (Instr.hasMemoryOperands())
+LatencySnippetGenerator::~LatencySnippetGenerator() = default;
+
+llvm::Expected<std::vector<CodeTemplate>>
+LatencySnippetGenerator::generateCodeTemplates(const Instruction &Instr) const {
+  std::vector<CodeTemplate> Results;
+  const ExecutionMode EM = getExecutionModes(Instr);
+  for (const auto EC : kExecutionClasses) {
+    for (const auto ExecutionModeBit : getExecutionModeBits(EM & EC.Mask))
+      appendCodeTemplates(State, Instr, ExecutionModeBit, EC.Description,
+                          Results);
+    if (!Results.empty())
+      break;
+  }
+  if (Results.empty())
     return llvm::make_error<BenchmarkFailure>(
-        "Infeasible : has memory operands");
-  if (auto CT = generateSelfAliasingCodeTemplate(Instr))
-    return CT;
-  else
-    llvm::consumeError(CT.takeError());
-  // No self aliasing, trying to create a dependency through another opcode.
-  return generateTwoInstructionPrototype(Instr);
+        "No strategy found to make the execution serial");
+  return std::move(Results);
 }
 
 const char *LatencyBenchmarkRunner::getCounterName() const {
   if (!State.getSubtargetInfo().getSchedModel().hasExtraProcessorInfo())
     llvm::report_fatal_error("sched model is missing extra processor info!");
   const char *CounterName = State.getSubtargetInfo()
                                 .getSchedModel()
                                 .getExtraProcessorInfo()

tools/llvm-exegesis/lib/MCInstrDescView.h

struct Instruction {
   // Whether this instruction's registers alias with OtherInstr's registers.
   bool hasAliasingRegistersThrough(const Instruction &OtherInstr) const;
 
   // Returns whether this instruction has Memory Operands.
   // Repeating this instruction executes sequentially with an instruction that
   // reads or write the same memory region.
   bool hasMemoryOperands() const;
 
+  // Returns whether this instruction as at least one use or one def.
+  // Repeating this instruction may execute sequentially by adding an
+  // instruction that aliases one of these.
+  bool hasOneUseOrOneDef() const;
+
   // Convenient function to help with debugging.
   void dump(const llvm::MCRegisterInfo &RegInfo,
             llvm::raw_ostream &Stream) const;
 
   const llvm::MCInstrDesc *Description; // Never nullptr.
   llvm::StringRef Name;                 // The name of this instruction.
   llvm::SmallVector<Operand, 8> Operands;
   llvm::SmallVector<Variable, 4> Variables;

 // Returns all possible configurations leading Def registers of DefInstruction
 // to alias with Use registers of UseInstruction.
 struct AliasingConfigurations {
   AliasingConfigurations(const Instruction &DefInstruction,
                          const Instruction &UseInstruction);
 
   bool empty() const; // True if no aliasing configuration is found.
   bool hasImplicitAliasing() const;
-  void setExplicitAliasing() const;
 
-  const Instruction &DefInstruction;
-  const Instruction &UseInstruction;
   llvm::SmallVector<AliasingRegisterOperands, 32> Configurations;
 };
 
 // Writes MCInst to OS.
 // This is not assembly but the internal LLVM's name for instructions and
 // registers.
 void DumpMCInst(const llvm::MCRegisterInfo &MCRegisterInfo,
                 const llvm::MCInstrInfo &MCInstrInfo,
                 const llvm::MCInst &MCInst, llvm::raw_ostream &OS);
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H

tools/llvm-exegesis/lib/MCInstrDescView.cpp

unsigned Variable::getIndex() const {
   return Index;
 }
 
 unsigned Variable::getPrimaryOperandIndex() const {
   assert(!TiedOperands.empty());
   return TiedOperands[0];
 }
 
-bool Variable::hasTiedOperands() const { return TiedOperands.size() > 1; }
+bool Variable::hasTiedOperands() const {
+  assert(TiedOperands.size() <= 2 &&
+         "No more than two operands can be tied together");
+  // By definition only Use and Def operands can be tied together.
+  // TiedOperands[0] is the Def operand (LLVM stores defs first).
+  // TiedOperands[1] is the Use operand.
+  return TiedOperands.size() > 1;
+}
 
 unsigned Operand::getIndex() const {
   assert(Index >= 0 && "Index must be set");
   return Index;
 }
 
 bool Operand::isExplicit() const { return Info; }
 
bool Instruction::hasTiedRegisters() const {
   return llvm::any_of(
       Variables, [](const Variable &Var) { return Var.hasTiedOperands(); });
 }
 
 bool Instruction::hasAliasingRegisters() const {
   return AllDefRegs.anyCommon(AllUseRegs);
 }
 
+bool Instruction::hasOneUseOrOneDef() const {
+  return AllDefRegs.count() || AllUseRegs.count();
+}
+
 void Instruction::dump(const llvm::MCRegisterInfo &RegInfo,
                        llvm::raw_ostream &Stream) const {
   Stream << "- " << Name << "\n";
   for (const auto &Op : Operands) {
     Stream << "- Op" << Op.getIndex();
     if (Op.isExplicit())
       Stream << " Explicit";
     if (Op.isImplicit())

 
 bool AliasingConfigurations::hasImplicitAliasing() const {
   return llvm::any_of(Configurations, [](const AliasingRegisterOperands &ARO) {
     return ARO.hasImplicitAliasing();
   });
 }
 
 AliasingConfigurations::AliasingConfigurations(
-    const Instruction &DefInstruction, const Instruction &UseInstruction)
-    : DefInstruction(DefInstruction), UseInstruction(UseInstruction) {
+    const Instruction &DefInstruction, const Instruction &UseInstruction) {
   if (UseInstruction.AllUseRegs.anyCommon(DefInstruction.AllDefRegs)) {
     auto CommonRegisters = UseInstruction.AllUseRegs;
     CommonRegisters &= DefInstruction.AllDefRegs;
     for (const llvm::MCPhysReg Reg : CommonRegisters.set_bits()) {
       AliasingRegisterOperands ARO;
       addOperandIfAlias(Reg, true, DefInstruction.Operands, ARO.Defs);
       addOperandIfAlias(Reg, false, UseInstruction.Operands, ARO.Uses);
       if (!ARO.Defs.empty() && !ARO.Uses.empty() &&

tools/llvm-exegesis/lib/SnippetGenerator.h

 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/Error.h"
 #include <cstdlib>
 #include <memory>
 #include <vector>
 
 namespace exegesis {
 
+std::vector<CodeTemplate> getSingleton(CodeTemplate &CT);
+
+// Generates code templates that has a self-dependency.
+llvm::Expected<std::vector<CodeTemplate>>
+generateSelfAliasingCodeTemplates(const Instruction &Instr);
+
+// Generates code templates without assignment constraints.
+llvm::Expected<std::vector<CodeTemplate>>
+generateUnconstrainedCodeTemplates(const Instruction &Instr,
+                                   llvm::StringRef Msg);
+
 // A class representing failures that happened during Benchmark, they are used
 // to report informations to the user.
 class SnippetGeneratorFailure : public llvm::StringError {
 public:
   SnippetGeneratorFailure(const llvm::Twine &S);
 };
 
 // Common code for all benchmark modes.
public:
 
   // Given a snippet, computes which registers the setup code needs to define.
   std::vector<RegisterValue> computeRegisterInitialValues(
       const std::vector<InstructionTemplate> &Snippet) const;
 
 protected:
   const LLVMState &State;
 
-  // Generates a single code template that has a self-dependency.
-  llvm::Expected<CodeTemplate>
-  generateSelfAliasingCodeTemplate(const Instruction &Instr) const;
-  // Generates a single code template without assignment constraints.
-  llvm::Expected<CodeTemplate>
-  generateUnconstrainedCodeTemplate(const Instruction &Instr,
-                                    llvm::StringRef Msg) const;
-
 private:
   // API to be implemented by subclasses.
-  virtual llvm::Expected<CodeTemplate>
-  generateCodeTemplate(const Instruction &Instr) const = 0;
+  virtual llvm::Expected<std::vector<CodeTemplate>>
+  generateCodeTemplates(const Instruction &Instr) const = 0;
 };
 
 // A global Random Number Generator to randomize configurations.
 // FIXME: Move random number generation into an object and make it seedable for
 // unit tests.
 std::mt19937 &randomGenerator();
 
 // Picks a random bit among the bits set in Vector and returns its index.

tools/llvm-exegesis/lib/SnippetGenerator.cpp

 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Program.h"
 
 namespace exegesis {
 
+std::vector<CodeTemplate> getSingleton(CodeTemplate &CT) {
+  std::vector<CodeTemplate> Result;
+  Result.push_back(std::move(CT));
+  return Result;
+}
+
 SnippetGeneratorFailure::SnippetGeneratorFailure(const llvm::Twine &S)
     : llvm::StringError(S, llvm::inconvertibleErrorCode()) {}
 
 SnippetGenerator::SnippetGenerator(const LLVMState &State) : State(State) {}
 
 SnippetGenerator::~SnippetGenerator() = default;
 
 llvm::Expected<std::vector<BenchmarkCode>>
 SnippetGenerator::generateConfigurations(const Instruction &Instr) const {
-  if (auto E = generateCodeTemplate(Instr)) {
-    CodeTemplate &CT = E.get();
+  if (auto E = generateCodeTemplates(Instr)) {
     const auto &RATC = State.getRATC();
+    std::vector<BenchmarkCode> Output;
+    for (CodeTemplate &CT : E.get()) {
       const llvm::BitVector &ForbiddenRegs =
           CT.ScratchSpacePointerInReg
               ? RATC.getRegister(CT.ScratchSpacePointerInReg).aliasedBits()
               : RATC.emptyRegisters();
-    std::vector<BenchmarkCode> Output;
       // TODO: Generate as many BenchmarkCode as needed.
       {
         BenchmarkCode BC;
         BC.Info = CT.Info;
         for (InstructionTemplate &IT : CT.Instructions) {
           randomizeUnsetVariables(ForbiddenRegs, IT);
           BC.Instructions.push_back(IT.build());
         }
         if (CT.ScratchSpacePointerInReg)
           BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
-      BC.RegisterInitialValues = computeRegisterInitialValues(CT.Instructions);
+        BC.RegisterInitialValues =
+            computeRegisterInitialValues(CT.Instructions);
         Output.push_back(std::move(BC));
       }
+    }
     return Output;
   } else
     return E.takeError();
 }
 
 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
     const std::vector<InstructionTemplate> &Instructions) const {
   // Collect all register uses and create an assignment for each of them.
for (const Operand &Op : IT.Instr.Operands) {
         if (Reg > 0)
           DefinedRegs.set(Reg);
       }
     }
   }
   return RIV;
 }
 
-llvm::Expected<CodeTemplate> SnippetGenerator::generateSelfAliasingCodeTemplate(
-    const Instruction &Instr) const {
+llvm::Expected<std::vector<CodeTemplate>>
+generateSelfAliasingCodeTemplates(const Instruction &Instr) {
   const AliasingConfigurations SelfAliasing(Instr, Instr);
-  if (SelfAliasing.empty()) {
+  if (SelfAliasing.empty())
     return llvm::make_error<SnippetGeneratorFailure>("empty self aliasing");
-  }
-  CodeTemplate CT;
+  std::vector<CodeTemplate> Result;
+  Result.emplace_back();
+  CodeTemplate &CT = Result.back();
   InstructionTemplate IT(Instr);
   if (SelfAliasing.hasImplicitAliasing()) {
     CT.Info = "implicit Self cycles, picking random values.";
   } else {
     CT.Info = "explicit self cycles, selecting one aliasing Conf.";
     // This is a self aliasing instruction so defs and uses are from the same
     // instance, hence twice IT in the following call.
     setRandomAliasing(SelfAliasing, IT, IT);
   }
   CT.Instructions.push_back(std::move(IT));
-  return std::move(CT);
+  return std::move(Result);
 }
 
-llvm::Expected<CodeTemplate>
-SnippetGenerator::generateUnconstrainedCodeTemplate(const Instruction &Instr,
-                                                    llvm::StringRef Msg) const {
-  CodeTemplate CT;
+llvm::Expected<std::vector<CodeTemplate>>
+generateUnconstrainedCodeTemplates(const Instruction &Instr,
+                                   llvm::StringRef Msg) {
+  std::vector<CodeTemplate> Result;
+  Result.emplace_back();
+  CodeTemplate &CT = Result.back();
   CT.Info = llvm::formatv("{0}, repeating an unconstrained assignment", Msg);
   CT.Instructions.emplace_back(Instr);
-  return std::move(CT);
+  return std::move(Result);
 }
 
 std::mt19937 &randomGenerator() {
   static std::random_device RandomDevice;
   static std::mt19937 RandomGenerator(RandomDevice());
   return RandomGenerator;
 }
 

tools/llvm-exegesis/lib/Uops.h

 
 namespace exegesis {
 
 class UopsSnippetGenerator : public SnippetGenerator {
 public:
   UopsSnippetGenerator(const LLVMState &State) : SnippetGenerator(State) {}
   ~UopsSnippetGenerator() override;
 
-  llvm::Expected<CodeTemplate>
-  generateCodeTemplate(const Instruction &Instr) const override;
+  llvm::Expected<std::vector<CodeTemplate>>
+  generateCodeTemplates(const Instruction &Instr) const override;
 
   static constexpr const size_t kMinNumDifferentAddresses = 6;
 
 private:
   // 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

tools/llvm-exegesis/lib/Uops.cpp

while (Instructions.size() < kMinNumDifferentAddresses) {
     ET.fillMemoryOperands(IT, ScratchSpacePointerInReg, I * MemStep);
     ++I;
     Instructions.push_back(std::move(IT));
   }
   assert(I * MemStep < BenchmarkRunner::ScratchSpace::kSize &&
          "not enough scratch space");
 }
 
-llvm::Expected<CodeTemplate>
-UopsSnippetGenerator::generateCodeTemplate(const Instruction &Instr) const {
+llvm::Expected<std::vector<CodeTemplate>>
+UopsSnippetGenerator::generateCodeTemplates(const Instruction &Instr) const {
   CodeTemplate CT;
   const llvm::BitVector *ScratchSpaceAliasedRegs = nullptr;
   if (Instr.hasMemoryOperands()) {
     const auto &ET = State.getExegesisTarget();
     CT.ScratchSpacePointerInReg =
         ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
     if (CT.ScratchSpacePointerInReg == 0)
       return llvm::make_error<BenchmarkFailure>(
UopsSnippetGenerator::generateCodeTemplates(const Instruction &Instr) const {
   }
 
   const AliasingConfigurations SelfAliasing(Instr, Instr);
   InstructionTemplate IT(Instr);
   if (SelfAliasing.empty()) {
     CT.Info = "instruction is parallel, repeating a random one.";
     CT.Instructions.push_back(std::move(IT));
     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
-    return std::move(CT);
+    return getSingleton(CT);
   }
   if (SelfAliasing.hasImplicitAliasing()) {
     CT.Info = "instruction is serial, repeating a random one.";
     CT.Instructions.push_back(std::move(IT));
     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
-    return std::move(CT);
+    return getSingleton(CT);
   }
   const auto TiedVariables = getVariablesWithTiedOperands(Instr);
   if (!TiedVariables.empty()) {
     if (TiedVariables.size() > 1)
       return llvm::make_error<llvm::StringError>(
           "Infeasible : don't know how to handle several tied variables",
           llvm::inconvertibleErrorCode());
     const Variable *Var = TiedVariables.front();
     assert(Var);
     const Operand &Op = Instr.getPrimaryOperand(*Var);
     assert(Op.isReg());
     CT.Info = "instruction has tied variables using static renaming.";
     for (const llvm::MCPhysReg Reg :
          Op.getRegisterAliasing().sourceBits().set_bits()) {
       if (ScratchSpaceAliasedRegs && ScratchSpaceAliasedRegs->test(Reg))
         continue; // Do not use the scratch memory address register.
       InstructionTemplate TmpIT = IT;
       TmpIT.getValueFor(*Var) = llvm::MCOperand::createReg(Reg);
       CT.Instructions.push_back(std::move(TmpIT));
     }
     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
-    return std::move(CT);
+    return getSingleton(CT);
   }
   const auto &ReservedRegisters = State.getRATC().reservedRegisters();
   // No tied variables, we pick random values for defs.
   llvm::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();
       remove(PossibleRegisters, ReservedRegisters);
if (Op.isReg() && Op.isExplicit() && Op.isUse() && !Op.isMemory()) {
       const auto RandomReg = randomBit(PossibleRegisters);
       IT.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg);
     }
   }
   CT.Info =
       "instruction has no tied variables picking Uses different from defs";
   CT.Instructions.push_back(std::move(IT));
   instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
-  return std::move(CT);
+  return getSingleton(CT);
 }
 
 std::vector<BenchmarkMeasure>
 UopsBenchmarkRunner::runMeasurements(const ExecutableFunction &Function,
                                      ScratchSpace &Scratch) const {
   const auto &SchedModel = State.getSubtargetInfo().getSchedModel();
 
   const auto RunMeasurement = [&Function,

tools/llvm-exegesis/lib/X86/Target.cpp

 static unsigned GetX86FPFlags(const Instruction &Instr) {
   return Instr.Description->TSFlags & llvm::X86II::FPTypeMask;
 }
 
 class X86LatencySnippetGenerator : public LatencySnippetGenerator {
 public:
   using LatencySnippetGenerator::LatencySnippetGenerator;
 
-  llvm::Expected<CodeTemplate>
-  generateCodeTemplate(const Instruction &Instr) const override {
+  llvm::Expected<std::vector<CodeTemplate>>
+  generateCodeTemplates(const Instruction &Instr) const override {
     if (auto E = IsInvalidOpcode(Instr))
       return std::move(E);
 
     switch (GetX86FPFlags(Instr)) {
     case llvm::X86II::NotFP:
-      return LatencySnippetGenerator::generateCodeTemplate(Instr);
+      return LatencySnippetGenerator::generateCodeTemplates(Instr);
     case llvm::X86II::ZeroArgFP:
     case llvm::X86II::OneArgFP:
     case llvm::X86II::SpecialFP:
     case llvm::X86II::CompareFP:
     case llvm::X86II::CondMovFP:
       return llvm::make_error<BenchmarkFailure>("Unsupported x87 Instruction");
     case llvm::X86II::OneArgFPRW:
     case llvm::X86II::TwoArgFP:
       // These are instructions like
       //   - `ST(0) = fsqrt(ST(0))` (OneArgFPRW)
       //   - `ST(0) = ST(0) + ST(i)` (TwoArgFP)
       // They are intrinsically serial and do not modify the state of the stack.
-      return generateSelfAliasingCodeTemplate(Instr);
+      return generateSelfAliasingCodeTemplates(Instr);
     default:
       llvm_unreachable("Unknown FP Type!");
     }
   }
 };
 
 class X86UopsSnippetGenerator : public UopsSnippetGenerator {
 public:
   using UopsSnippetGenerator::UopsSnippetGenerator;
 
-  llvm::Expected<CodeTemplate>
-  generateCodeTemplate(const Instruction &Instr) const override {
+  llvm::Expected<std::vector<CodeTemplate>>
+  generateCodeTemplates(const Instruction &Instr) const override {
     if (auto E = IsInvalidOpcode(Instr))
       return std::move(E);
 
     switch (GetX86FPFlags(Instr)) {
     case llvm::X86II::NotFP:
-      return UopsSnippetGenerator::generateCodeTemplate(Instr);
+      return UopsSnippetGenerator::generateCodeTemplates(Instr);
     case llvm::X86II::ZeroArgFP:
     case llvm::X86II::OneArgFP:
     case llvm::X86II::SpecialFP:
       return llvm::make_error<BenchmarkFailure>("Unsupported x87 Instruction");
     case llvm::X86II::OneArgFPRW:
     case llvm::X86II::TwoArgFP:
       // These are instructions like
       //   - `ST(0) = fsqrt(ST(0))` (OneArgFPRW)
       //   - `ST(0) = ST(0) + ST(i)` (TwoArgFP)
       // They are intrinsically serial and do not modify the state of the stack.
       // We generate the same code for latency and uops.
-      return generateSelfAliasingCodeTemplate(Instr);
+      return generateSelfAliasingCodeTemplates(Instr);
     case llvm::X86II::CompareFP:
     case llvm::X86II::CondMovFP:
       // We can compute uops for any FP instruction that does not grow or shrink
       // the stack (either do not touch the stack or push as much as they pop).
-      return generateUnconstrainedCodeTemplate(
+      return generateUnconstrainedCodeTemplates(
           Instr, "instruction does not grow/shrink the FP stack");
     default:
       llvm_unreachable("Unknown FP Type!");
     }
   }
 };
 
 static unsigned GetLoadImmediateOpcode(unsigned RegBitWidth) {

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

 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(); }
 
protected:
   const llvm::MCRegisterInfo &MCRegisterInfo;
 };
 
 template <typename SnippetGeneratorT>
 class SnippetGeneratorTest : public X86SnippetGeneratorTest {
 protected:
   SnippetGeneratorTest() : Generator(State) {}
 
-  CodeTemplate checkAndGetCodeTemplate(unsigned Opcode) {
+  std::vector<CodeTemplate> checkAndGetCodeTemplates(unsigned Opcode) {
     randomGenerator().seed(0); // Initialize seed.
     const Instruction Instr(State, Opcode);
-    auto CodeTemplateOrError = Generator.generateCodeTemplate(Instr);
+    auto CodeTemplateOrError = Generator.generateCodeTemplates(Instr);
     EXPECT_FALSE(CodeTemplateOrError.takeError()); // Valid configuration.
     return std::move(CodeTemplateOrError.get());
   }
 
   SnippetGeneratorT Generator;
 };
 
 using LatencySnippetGeneratorTest =
     SnippetGeneratorTest<LatencySnippetGenerator>;
 
 using UopsSnippetGeneratorTest = SnippetGeneratorTest<UopsSnippetGenerator>;
 
-TEST_F(LatencySnippetGeneratorTest, ImplicitSelfDependency) {
-  // ADC16i16 self alias because of implicit use and def.
-
-  // explicit use 0       : imm
-  // implicit def         : AX
-  // implicit def         : EFLAGS
-  // implicit use         : AX
-  // implicit use         : EFLAGS
+TEST_F(LatencySnippetGeneratorTest, 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 = llvm::X86::ADC16i16;
   EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitDefs()[0], llvm::X86::AX);
   EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitDefs()[1], llvm::X86::EFLAGS);
   EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitUses()[0], llvm::X86::AX);
   EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitUses()[1], llvm::X86::EFLAGS);
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
-  EXPECT_THAT(CT.Info, HasSubstr("implicit"));
+  const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
+  ASSERT_THAT(CodeTemplates, SizeIs(1));
+  const auto &CT = CodeTemplates[0];
+  EXPECT_THAT(CT.Execution, ExecutionMode::ALWAYS_SERIAL_VIA_IMPLICIT_REGS);
   ASSERT_THAT(CT.Instructions, SizeIs(1));
   const InstructionTemplate &IT = CT.Instructions[0];
   EXPECT_THAT(IT.getOpcode(), Opcode);
   ASSERT_THAT(IT.VariableValues, SizeIs(1)); // Imm.
   EXPECT_THAT(IT.VariableValues[0], IsInvalid()) << "Immediate is not set";
 }
 
-TEST_F(LatencySnippetGeneratorTest, ExplicitSelfDependency) {
-  // ADD16ri self alias because Op0 and Op1 are tied together.
-
-  // explicit def 0       : reg RegClass=GR16
-  // explicit use 1       : reg RegClass=GR16 | TIED_TO:0
-  // explicit use 2       : imm
-  // implicit def         : EFLAGS
+TEST_F(LatencySnippetGeneratorTest, 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 = llvm::X86::ADD16ri;
   EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitDefs()[0], llvm::X86::EFLAGS);
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
-  EXPECT_THAT(CT.Info, HasSubstr("explicit"));
+  const auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
+  ASSERT_THAT(CodeTemplates, SizeIs(1));
+  const auto &CT = CodeTemplates[0];
+  EXPECT_THAT(CT.Execution, ExecutionMode::ALWAYS_SERIAL_VIA_TIED_REGS);
   ASSERT_THAT(CT.Instructions, SizeIs(1));
   const InstructionTemplate &IT = CT.Instructions[0];
   EXPECT_THAT(IT.getOpcode(), Opcode);
   ASSERT_THAT(IT.VariableValues, SizeIs(2));
-  EXPECT_THAT(IT.VariableValues[0], IsReg()) << "Operand 0 and 1";
+  EXPECT_THAT(IT.VariableValues[0], IsInvalid()) << "Operand 1 is not set";
   EXPECT_THAT(IT.VariableValues[1], IsInvalid()) << "Operand 2 is not set";
 }
 
-TEST_F(LatencySnippetGeneratorTest, DependencyThroughOtherOpcode) {
-  // CMP64rr
-  // explicit use 0       : reg RegClass=GR64
-  // explicit use 1       : reg RegClass=GR64
-  // implicit def         : EFLAGS
+TEST_F(LatencySnippetGeneratorTest, 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 = llvm::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.VariableValues, SizeIs(3));
+  EXPECT_THAT(IT.VariableValues,
+              AnyOf(ElementsAre(IsReg(), IsInvalid(), IsReg()),
+                    ElementsAre(IsReg(), IsReg(), IsInvalid())))
+      << "Op0 is either set to Op1 or to Op2";
+}
 
+TEST_F(LatencySnippetGeneratorTest, DependencyThroughOtherOpcode) {
+  // - CMP64rr
+  // - Op0 Explicit Use RegClass(GR64)
+  // - Op1 Explicit Use RegClass(GR64)
+  // - Op2 Implicit Def Reg(EFLAGS)
+  // - Var0 [Op0]
+  // - Var1 [Op1]
   const unsigned Opcode = llvm::X86::CMP64rr;
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
-  EXPECT_THAT(CT.Info, HasSubstr("cycle through"));
+  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.VariableValues, SizeIs(2));
     EXPECT_THAT(IT.VariableValues, 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(LatencySnippetGeneratorTest, LAHF) {
+  // - LAHF
+  // - Op0 Implicit Def Reg(AH)
+  // - Op1 Implicit Use Reg(EFLAGS)
   const unsigned Opcode = llvm::X86::LAHF;
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
-  EXPECT_THAT(CT.Info, HasSubstr("cycle through"));
+  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.VariableValues, SizeIs(0));
   }
+}
 
 TEST_F(UopsSnippetGeneratorTest, ParallelInstruction) {
-  // BNDCL32rr is parallel no matter what.
-
-  // explicit use 0       : reg RegClass=BNDR
-  // explicit use 1       : reg RegClass=GR32
-
+  // - BNDCL32rr
+  // - Op0 Explicit Use RegClass(BNDR)
+  // - Op1 Explicit Use RegClass(GR32)
+  // - Var0 [Op0]
+  // - Var1 [Op1]
   const unsigned Opcode = llvm::X86::BNDCL32rr;
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
+  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.VariableValues, SizeIs(2));
   EXPECT_THAT(IT.VariableValues[0], IsInvalid());
   EXPECT_THAT(IT.VariableValues[1], IsInvalid());
 }
 
 TEST_F(UopsSnippetGeneratorTest, SerialInstruction) {
-  // CDQ is serial no matter what.
-
-  // implicit def         : EAX
-  // implicit def         : EDX
-  // implicit use         : EAX
+  // - 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 = llvm::X86::CDQ;
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
+  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.VariableValues, SizeIs(0));
 }
 
 TEST_F(UopsSnippetGeneratorTest, StaticRenaming) {
   // CMOVA32rr has tied variables, we enumerate the possible values to execute
   // as many in parallel as possible.
 
-  // explicit def 0       : reg RegClass=GR32
-  // explicit use 1       : reg RegClass=GR32 | TIED_TO:0
-  // explicit use 2       : reg RegClass=GR32
-  // implicit use         : EFLAGS
+  // - CMOVA32rr
+  // - Op0 Explicit Def RegClass(GR32)
+  // - Op1 Explicit Use RegClass(GR32) TiedToOp0
+  // - Op2 Explicit Use RegClass(GR32)
+  // - Op3 Implicit Use Reg(EFLAGS)
+  // - Var0 [Op0,Op1]
+  // - Var1 [Op2]
+  // - hasTiedRegisters (execution is always serial)
+  // - hasAliasingRegisters
   const unsigned Opcode = llvm::X86::CMOVA32rr;
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
+  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.VariableValues, SizeIs(2));
     AllDefRegisters.insert(IT.VariableValues[0].getReg());
   }
   EXPECT_THAT(AllDefRegisters, SizeIs(kInstructionCount))
       << "Each instruction writes to a different register";
 }
 
 TEST_F(UopsSnippetGeneratorTest, NoTiedVariables) {
   // CMOV_GR32 has no tied variables, we make sure def and use are different
   // from each other.
 
-  // explicit def 0       : reg RegClass=GR32
-  // explicit use 1       : reg RegClass=GR32
-  // explicit use 2       : reg RegClass=GR32
-  // explicit use 3       : imm
-  // implicit use         : EFLAGS
+  // - 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 = llvm::X86::CMOV_GR32;
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
+  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.VariableValues, SizeIs(4));
   EXPECT_THAT(IT.VariableValues[0].getReg(), Not(IT.VariableValues[1].getReg()))
       << "Def is different from first Use";
   EXPECT_THAT(IT.VariableValues[0].getReg(), Not(IT.VariableValues[2].getReg()))
       << "Def is different from second Use";
   EXPECT_THAT(IT.VariableValues[3], IsInvalid());
 }
 
 TEST_F(UopsSnippetGeneratorTest, 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 = llvm::X86::MOV32rm;
-  const CodeTemplate CT = checkAndGetCodeTemplate(Opcode);
+  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(UopsSnippetGenerator::kMinNumDifferentAddresses));
   const InstructionTemplate &IT = CT.Instructions[0];
   EXPECT_THAT(IT.getOpcode(), Opcode);
   ASSERT_THAT(IT.VariableValues, SizeIs(6));
   EXPECT_EQ(IT.VariableValues[2].getImm(), 1);
   EXPECT_EQ(IT.VariableValues[3].getReg(), 0u);
   EXPECT_EQ(IT.VariableValues[4].getImm(), 0);
   EXPECT_EQ(IT.VariableValues[5].getReg(), 0u);
 }
 
 TEST_F(UopsSnippetGeneratorTest, 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 = llvm::X86::MOVSB;
   const Instruction Instr(State, Opcode);
-  auto Error = Generator.generateCodeTemplate(Instr).takeError();
+  auto Error = Generator.generateCodeTemplates(Instr).takeError();
   EXPECT_TRUE((bool)Error);
   llvm::consumeError(std::move(Error));
 }
 
 class FakeSnippetGenerator : public SnippetGenerator {
 public:
   FakeSnippetGenerator(const LLVMState &State) : SnippetGenerator(State) {}
 
   Instruction createInstruction(unsigned Opcode) {
     return Instruction(State, Opcode);
   }
 
 private:
-  llvm::Expected<CodeTemplate>
-  generateCodeTemplate(const Instruction &Instr) const override {
+  llvm::Expected<std::vector<CodeTemplate>>
+  generateCodeTemplates(const Instruction &Instr) const override {
     return llvm::make_error<llvm::StringError>("not implemented",
                                                llvm::inconvertibleErrorCode());
   }
 };
 
 using FakeSnippetGeneratorTest = SnippetGeneratorTest<FakeSnippetGenerator>;
 
 testing::Matcher<const RegisterValue &> IsRegisterValue(unsigned Reg,