[llvm-exegesis] ExecutionMode is computed upfront for Uops as well

[courbet]

tools/llvm-exegesis/lib/CodeTemplate.h

87

s/each memory access hits a different cache line/memory accesses do not alias/

tools/llvm-exegesis/lib/Latency.cpp

134

Let's commit this separately.

tools/llvm-exegesis/lib/MCInstrDescView.h

98

I think it would be better to return a vector<const Variable*> and deal with unicity at the call site.

141

*writes

tools/llvm-exegesis/lib/Uops.h

38

doc ?

[courbet]

tools/llvm-exegesis/lib/Uops.cpp

102

...for non-memory purposes

180

"missing ScratchSpaceReg" would be clearer

233

please add a comment here

247

ditto

256

this doe snot need to be a member

tools/llvm-exegesis/lib/CodeTemplate.h

struct InstructionTemplate {
   InstructionTemplate(InstructionTemplate &&);                 // default
   InstructionTemplate &operator=(InstructionTemplate &&);      // default
 
   unsigned getOpcode() const;
   llvm::MCOperand &getValueFor(const Variable &Var);
   const llvm::MCOperand &getValueFor(const Variable &Var) const;
   llvm::MCOperand &getValueFor(const Operand &Op);
   const llvm::MCOperand &getValueFor(const Operand &Op) const;
-  bool hasImmediateVariables() const;
 
   // Builds an llvm::MCInst from this InstructionTemplate setting its operands
-  // to the corresponding variable values. Precondition: All VariableValues must
-  // be set.
+  // 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_IMPLICIT_REGS_ALIAS = 1u << 0,
 
-  // The instruction is always serial because one Def is tied to a Use.
+  // The instruction is serial if repeated because one Def is tied to a Use.
   // e.g. AND32ri (alias via tied GR32)
-  ALWAYS_SERIAL_TIED_REGS_ALIAS = 1u << 1,
+  SERIAL_VIA_TIED_REGS = 1u << 1,
 
   // The execution can be made serial by inserting a second instruction that
   // clobbers/reads 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.
enum class ExecutionMode : uint8_t {
 
   // The execution is always parallel because the instruction is missing Use or
   // Def operands.
   ALWAYS_PARALLEL_MISSING_USE_OR_DEF = 1u << 5,
 
   // The execution can be made parallel by repeating the same instruction but
   // making sure that Defs of one instruction do not alias with Uses of the
   // second one.
-  PARALLEL_VIA_EXPLICIT_REGS = 1u << 6,
+  PARALLEL_VIA_DISTINCT_EXPLICIT_REGS = 1u << 6,
 
-  LLVM_MARK_AS_BITMASK_ENUM(/*Largest*/ PARALLEL_VIA_EXPLICIT_REGS)
+  // The execution can be made parallel by repeating the same instruction but
+  // making sure each memory access hits a different cache line.
+  PARALLEL_VIA_DISTINCT_MEMORY_ACCESS = 1u << 7,
+
+  LLVM_MARK_AS_BITMASK_ENUM(/*Largest*/ PARALLEL_VIA_DISTINCT_MEMORY_ACCESS)
 };
 
 // Returns whether Execution is one of the values defined in the enum above.
 bool isEnumValue(ExecutionMode Execution);
 
 // 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);
 
+// Computes all possible execution modes for Instr.
+ExecutionMode getExecutionModes(const Instruction &Instr);
+
 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
 // SnippetGenerator to instantiate it many times with specific values to study
 // their impact on instruction's performance.
 struct CodeTemplate {
   CodeTemplate() = default;

tools/llvm-exegesis/lib/CodeTemplate.cpp

llvm::MCOperand &InstructionTemplate::getValueFor(const Operand &Op) {
   return getValueFor(Instr.Variables[Op.getVariableIndex()]);
 }
 
 const llvm::MCOperand &
 InstructionTemplate::getValueFor(const Operand &Op) const {
   return getValueFor(Instr.Variables[Op.getVariableIndex()]);
 }
 
-bool InstructionTemplate::hasImmediateVariables() const {
-  return llvm::any_of(Instr.Variables, [this](const Variable &Var) {
-    return Instr.getPrimaryOperand(Var).isImmediate();
-  });
-}
-
 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;
 }
 
 bool isEnumValue(ExecutionMode Execution) {
   return llvm::isPowerOf2_32(static_cast<uint32_t>(Execution));
 }
 
 llvm::StringRef getName(ExecutionMode Bit) {
   assert(isEnumValue(Bit) && "Bit must be a power of two");
   switch (Bit) {
   case ExecutionMode::UNKNOWN:
     return "UNKNOWN";
   case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS:
     return "ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS";
-  case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS:
-    return "ALWAYS_SERIAL_TIED_REGS_ALIAS";
+  case ExecutionMode::SERIAL_VIA_TIED_REGS:
+    return "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::ALWAYS_PARALLEL_MISSING_USE_OR_DEF:
     return "ALWAYS_PARALLEL_MISSING_USE_OR_DEF";
-  case ExecutionMode::PARALLEL_VIA_EXPLICIT_REGS:
-    return "PARALLEL_VIA_EXPLICIT_REGS";
+  case ExecutionMode::PARALLEL_VIA_DISTINCT_EXPLICIT_REGS:
+    return "PARALLEL_VIA_DISTINCT_EXPLICIT_REGS";
+  case ExecutionMode::PARALLEL_VIA_DISTINCT_MEMORY_ACCESS:
+    return "PARALLEL_VIA_DISTINCT_MEMORY_ACCESS";
   }
   llvm_unreachable("Missing enum case");
 }
 
 llvm::ArrayRef<ExecutionMode> getAllExecutionBits() {
   static const ExecutionMode kAllExecutionModeBits[] = {
       ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS,
-      ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS,
+      ExecutionMode::SERIAL_VIA_TIED_REGS,
       ExecutionMode::SERIAL_VIA_MEMORY_INSTR,
       ExecutionMode::SERIAL_VIA_EXPLICIT_REGS,
       ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR,
       ExecutionMode::ALWAYS_PARALLEL_MISSING_USE_OR_DEF,
-      ExecutionMode::PARALLEL_VIA_EXPLICIT_REGS,
+      ExecutionMode::PARALLEL_VIA_DISTINCT_EXPLICIT_REGS,
+      ExecutionMode::PARALLEL_VIA_DISTINCT_MEMORY_ACCESS,
   };
   return llvm::makeArrayRef(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;
 }
 
+ExecutionMode getExecutionModes(const Instruction &Instr) {
+  ExecutionMode EM = ExecutionMode::UNKNOWN;
+  if (Instr.hasAliasingImplicitRegisters())
+    EM |= ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS;
+  if (Instr.hasTiedRegisters())
+    EM |= ExecutionMode::SERIAL_VIA_TIED_REGS;
+  if (Instr.hasMemoryOperands()) {
+    EM |= ExecutionMode::SERIAL_VIA_MEMORY_INSTR;
+    EM |= ExecutionMode::PARALLEL_VIA_DISTINCT_MEMORY_ACCESS;
+  }
+  if (Instr.hasAliasingRegisters() && !Instr.hasMemoryOperands())
+    EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS;
+  if (Instr.hasOneUseOrOneDef() && !Instr.hasMemoryOperands())
+    EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR;
+  if (Instr.hasNoUseOrNoDef() && !Instr.hasMemoryOperands())
+    EM |= ExecutionMode::ALWAYS_PARALLEL_MISSING_USE_OR_DEF;
+  if (Instr.hasAliasingRegisters() || Instr.hasTiedRegisters() ||
+      Instr.hasOneUseOrOneDef())
+    EM |= ExecutionMode::PARALLEL_VIA_DISTINCT_EXPLICIT_REGS;
+  return EM;
+}
 } // namespace exegesis

tools/llvm-exegesis/lib/Latency.cpp

 
 namespace exegesis {
 
 struct ExecutionClass {
   ExecutionMode Mask;
   const char *Description;
 } static const kExecutionClasses[] = {
     {ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS |
-         ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS,
+         ExecutionMode::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"},
 };
 
for (const unsigned OtherOpcode : Opcodes) {
     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 = ExecutionMode::UNKNOWN;
-  if (Instr.hasAliasingImplicitRegisters())
-    EM |= ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS;
-  if (Instr.hasTiedRegisters())
-    EM |= ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS;
-  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(isEnumValue(ExecutionModeBit) && "Bit must be a power of two");
   switch (ExecutionModeBit) {
   case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS:
     // Nothing to do, the instruction is always serial.
     LLVM_FALLTHROUGH;
-  case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS: {
+  case ExecutionMode::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;
default:
     llvm_unreachable("Unhandled enum value");
   }
 }
 
 LatencySnippetGenerator::~LatencySnippetGenerator() = default;
 
 llvm::Expected<std::vector<CodeTemplate>>
 LatencySnippetGenerator::generateCodeTemplates(const Instruction &Instr) const {
+  if (Instr.hasMemoryOperands())
+    return llvm::make_error<BenchmarkFailure>(
+        "Latency does not handle memory operands yet");
   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;

tools/llvm-exegesis/lib/MCInstrDescView.h

struct Operand {
   int VariableIndex = -1;                           // Set for Explicit Op.
 };
 
 // A view over an MCInstrDesc offering a convenient interface to compute
 // Register aliasing.
 struct Instruction {
   Instruction(const LLVMState &State, unsigned Opcode);
 
+  // Return the Variable that ties together two operands or nullptr if this
+  // instruction has no tied operands.
+  const Variable *getTiedVariable() const;
+
   // Returns the Operand linked to this Variable.
   // In case the Variable is tied, the primary (i.e. Def) Operand is returned.
   const Operand &getPrimaryOperand(const Variable &Var) const;
 
   // Whether this instruction is self aliasing through its tied registers.
   // Repeating this instruction is guaranteed to executes sequentially.
   bool hasTiedRegisters() const;
 
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.
+  // Returns whether this instruction has 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;
 
+  // Returns whether this instruction has no use or no def.
+  // Repeating this instruction always execute in parallel.
+  bool hasNoUseOrNoDef() const;
+
+  // Whether this instruction implicitly reads or write this register.
+  bool isImplicitlyAliasingWith(unsigned reg) 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;

tools/llvm-exegesis/lib/MCInstrDescView.cpp

if (Op.isReg()) {
       if (Op.isDef() && Op.isImplicit())
         ImplDefRegs |= AliasingBits;
       if (Op.isUse() && Op.isImplicit())
         ImplUseRegs |= AliasingBits;
     }
   }
 }
 
+const Variable *Instruction::getTiedVariable() const {
+  for (const auto &Var : Variables)
+    if (Var.hasTiedOperands())
+      return &Var;
+  return nullptr;
+}
+
 const Operand &Instruction::getPrimaryOperand(const Variable &Var) const {
   const auto PrimaryOperandIndex = Var.getPrimaryOperandIndex();
   assert(PrimaryOperandIndex < Operands.size());
   return Operands[PrimaryOperandIndex];
 }
 
 bool Instruction::hasMemoryOperands() const {
   return any_of(Operands, [](const Operand &Op) {

 bool Instruction::hasAliasingRegisters() const {
   return AllDefRegs.anyCommon(AllUseRegs);
 }
 
 bool Instruction::hasOneUseOrOneDef() const {
   return AllDefRegs.count() || AllUseRegs.count();
 }
 
+bool Instruction::hasNoUseOrNoDef() const {
+  return !AllDefRegs.count() || !AllUseRegs.count();
+}
+
+bool Instruction::isImplicitlyAliasingWith(unsigned reg) const {
+  return ImplUseRegs.test(reg) || ImplDefRegs.test(reg);
+}
+
 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())
for (auto OperandIndex : Var.TiedOperands) {
       if (!IsFirst)
         Stream << ",";
       Stream << "Op" << OperandIndex;
       IsFirst = false;
     }
     Stream << "]";
     Stream << "\n";
   }
-  if (hasMemoryOperands())
-    Stream << "- hasMemoryOperands\n";
   if (hasAliasingImplicitRegisters())
     Stream << "- hasAliasingImplicitRegisters (execution is always serial)\n";
   if (hasTiedRegisters())
-    Stream << "- hasTiedRegisters (execution is always serial)\n";
+    Stream << "- hasTiedRegisters\n";
   if (hasAliasingRegisters())
     Stream << "- hasAliasingRegisters\n";
+  if (hasMemoryOperands())
+    Stream << "- hasMemoryOperands\n";
+  if (hasOneUseOrOneDef())
+    Stream << "- hasOneUseOrOneDef\n";
+  if (hasNoUseOrNoDef())
+    Stream << "- hasNoUseOrNoDef (execution is always parallel)\n";
 }
 
 bool RegisterOperandAssignment::
 operator==(const RegisterOperandAssignment &Other) const {
   return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg);
 }
 
 bool AliasingRegisterOperands::

tools/llvm-exegesis/lib/SnippetGenerator.cpp

static void randomize(const Instruction &Instr, const Variable &Var,
   switch (Op.getExplicitOperandInfo().OperandType) {
   case llvm::MCOI::OperandType::OPERAND_IMMEDIATE:
     // FIXME: explore immediate values too.
     AssignedValue = llvm::MCOperand::createImm(1);
     break;
   case llvm::MCOI::OperandType::OPERAND_REGISTER: {
     assert(Op.isReg());
     auto AllowedRegs = Op.getRegisterAliasing().sourceBits();
+    assert(AllowedRegs.any() && "No registers to choose from");
     assert(AllowedRegs.size() == ForbiddenRegs.size());
     for (auto I : ForbiddenRegs.set_bits())
       AllowedRegs.reset(I);
+    assert(AllowedRegs.any() && "No more registers to choose from");
     AssignedValue = llvm::MCOperand::createReg(randomBit(AllowedRegs));
     break;
   }
   default:
     break;
   }
 }
 

tools/llvm-exegesis/lib/Uops.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_UOPS_H
 #define LLVM_TOOLS_LLVM_EXEGESIS_UOPS_H
 
 #include "BenchmarkRunner.h"
 #include "SnippetGenerator.h"
+#include "Target.h"
 
 namespace exegesis {
 
 class UopsSnippetGenerator : public SnippetGenerator {
 public:
-  UopsSnippetGenerator(const LLVMState &State) : SnippetGenerator(State) {}
+  UopsSnippetGenerator(const LLVMState &State)
+      : SnippetGenerator(State), ET(State.getExegesisTarget()),
+        ScratchSpaceReg(ET.getScratchMemoryRegister(
+            State.getTargetMachine().getTargetTriple())) {}
+
   ~UopsSnippetGenerator() 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
-  // instructions until there are this number of instructions.
-  // For example, assuming kMinNumDifferentAddresses=5 and
-  // getMaxMemoryAccessSize()=64, if the original snippet is:
-  //   mov eax, [memory]
-  // we might generate:
-  //   mov eax, [rdi]
-  //   mov eax, [rdi + 64]
-  //   mov eax, [rdi + 128]
-  //   mov eax, [rdi + 192]
-  //   mov eax, [rdi + 256]
-  // If the original snippet is:
-  //   mov eax, [memory]
-  //   add eax, [memory]
-  // we might generate:
-  //   mov eax, [rdi]
-  //   add eax, [rdi + 64]
-  //   mov eax, [rdi + 128]
-  //   add eax, [rdi + 192]
-  //   mov eax, [rdi + 256]
-  void instantiateMemoryOperands(
-      unsigned ScratchSpaceReg,
-      std::vector<InstructionTemplate> &SnippetTemplate) const;
+  llvm::Expected<CodeTemplate>
+  generateCodeTemplate(const Instruction &Instr) const;
+
+  llvm::Expected<CodeTemplate> generateMemoryCodeTemplate(
+      const ExecutionMode EM, llvm::StringRef Info,
+      const std::vector<InstructionTemplate> &OriginalInstrs) const;
+
+  std::vector<InstructionTemplate>
+  generateUseDistinctFromDefs(const Instruction &Instr,
+                              llvm::BitVector ForbiddenRegs) const;
+
+  std::vector<InstructionTemplate>
+  generateStaticRenaming(const Instruction &Instr, const Variable &TiedVar,
+                         llvm::BitVector ForbiddenRegs) const;
+
+  std::vector<InstructionTemplate>
+  generateSingleInstruction(const Instruction &Instr) const;
+
+  const ExegesisTarget &ET;
+  const unsigned ScratchSpaceReg = 0;
 };
 
 class UopsBenchmarkRunner : public BenchmarkRunner {
 public:
   UopsBenchmarkRunner(const LLVMState &State)
       : BenchmarkRunner(State, InstructionBenchmark::Uops) {}
   ~UopsBenchmarkRunner() override;
 

tools/llvm-exegesis/lib/Uops.cpp

 //===-- Uops.cpp ------------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Uops.h"
 
 #include "Assembler.h"
 #include "BenchmarkRunner.h"
 #include "MCInstrDescView.h"
 #include "Target.h"
 
-// FIXME: Load constants into registers (e.g. with fld1) to not break
-// instructions like x87.
-
 // Ideally we would like the only limitation on executing uops to be the issue
 // ports. Maximizing port pressure increases the likelihood that the load is
 // distributed evenly across possible ports.
 
 // To achieve that, one approach is to generate instructions that do not have
 // data dependencies between them.
 //
 // For some instructions, this is trivial:

 // Some instruction even make the above static renaming impossible because
 // they implicitly read and write from the same operand, e.g. ADC16rr reads
 // and writes from EFLAGS.
 // In that case we just use a greedy register assignment and hope for the
 // best.
 
 namespace exegesis {
 
-static llvm::SmallVector<const Variable *, 8>
-getVariablesWithTiedOperands(const Instruction &Instr) {
-  llvm::SmallVector<const Variable *, 8> Result;
-  for (const auto &Var : Instr.Variables)
-    if (Var.hasTiedOperands())
-      Result.push_back(&Var);
-  return Result;
-}
-
 static void remove(llvm::BitVector &a, const llvm::BitVector &b) {
   assert(a.size() == b.size());
   for (auto I : b.set_bits())
     a.reset(I);
 }
 
+static bool has(const ExecutionMode EM, const ExecutionMode Bits) {
+  return (EM & Bits) == Bits;
+}
 UopsBenchmarkRunner::~UopsBenchmarkRunner() = default;
 
 UopsSnippetGenerator::~UopsSnippetGenerator() = default;
 
-void UopsSnippetGenerator::instantiateMemoryOperands(
-    const unsigned ScratchSpacePointerInReg,
-    std::vector<InstructionTemplate> &Instructions) const {
-  if (ScratchSpacePointerInReg == 0)
-    return; // no memory operands.
-  const auto &ET = State.getExegesisTarget();
-  const unsigned MemStep = ET.getMaxMemoryAccessSize();
-  const size_t OriginalInstructionsSize = Instructions.size();
-  size_t I = 0;
-  for (InstructionTemplate &IT : Instructions) {
-    ET.fillMemoryOperands(IT, ScratchSpacePointerInReg, I * MemStep);
-    ++I;
+llvm::Expected<CodeTemplate>
+UopsSnippetGenerator::generateCodeTemplate(const Instruction &Instr) const {
+  const auto EM = getExecutionModes(Instr);
+  if (has(EM, ExecutionMode::PARALLEL_VIA_DISTINCT_MEMORY_ACCESS)) {
+    if (ScratchSpaceReg == 0)
+      return llvm::make_error<BenchmarkFailure>(
+          "infeasible : target does not support memory instructions");
+    if (Instr.isImplicitlyAliasingWith(ScratchSpaceReg))
+      return llvm::make_error<BenchmarkFailure>(
+          "infeasible : memory instruction uses scratch memory register");
   }
 
-  while (Instructions.size() < kMinNumDifferentAddresses) {
-    InstructionTemplate IT = Instructions[I % OriginalInstructionsSize];
-    ET.fillMemoryOperands(IT, ScratchSpacePointerInReg, I * MemStep);
-    ++I;
-    Instructions.push_back(std::move(IT));
+  if (has(EM, ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS))
+    return generateMemoryCodeTemplate(
+        EM, "instruction is serial, repeating a random one.",
+        generateSingleInstruction(Instr));
+
+  if (has(EM, ExecutionMode::ALWAYS_PARALLEL_MISSING_USE_OR_DEF))
+    return generateMemoryCodeTemplate(
+        EM, "instruction is parallel, repeating a random one.",
+        generateSingleInstruction(Instr));
+
+  const auto &RATC = State.getRATC();
+  llvm::BitVector ForbiddenRegs = RATC.reservedRegisters();
+  ForbiddenRegs |= RATC.getRegister(ScratchSpaceReg).aliasedBits();
+
+  if (has(EM, ExecutionMode::PARALLEL_VIA_DISTINCT_EXPLICIT_REGS)) {
+    if (const Variable *const TiedVar = Instr.getTiedVariable())
+      return generateMemoryCodeTemplate(
+          EM, "instruction has tied variables using static renaming.",
+          generateStaticRenaming(Instr, *TiedVar, ForbiddenRegs));
+    else
+      return generateMemoryCodeTemplate(
+          EM, "instruction has no tied variables picking distinct Uses/Defs.",
+          generateUseDistinctFromDefs(Instr, ForbiddenRegs));
+  }
+
+  if (has(EM, ExecutionMode::PARALLEL_VIA_DISTINCT_MEMORY_ACCESS)) {
+    return generateMemoryCodeTemplate(
+        EM, "instruction is parallel via distinct memory access.",
+        generateSingleInstruction(Instr));
   }
-  assert(I * MemStep < BenchmarkRunner::ScratchSpace::kSize &&
-         "not enough scratch space");
+
+  for (const auto Bit : getExecutionModeBits(EM))
+    llvm::errs() << " - " << getName(Bit) << "\n";
+
+  return llvm::make_error<BenchmarkFailure>("Unhandled case");
 }
 
 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>(
-          "Infeasible : target does not support memory instructions");
-    ScratchSpaceAliasedRegs =
-        &State.getRATC().getRegister(CT.ScratchSpacePointerInReg).aliasedBits();
-    // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
-    // FIXME: We could make a copy of the scratch register.
-    for (const auto &Op : Instr.Operands) {
-      if (Op.isDef() && Op.isImplicitReg() &&
-          ScratchSpaceAliasedRegs->test(Op.getImplicitReg()))
-        return llvm::make_error<BenchmarkFailure>(
-            "Infeasible : memory instruction uses scratch memory register");
-    }
-  }
+  if (auto ECT = generateCodeTemplate(Instr))
+    return getSingleton(std::move(*ECT));
+  else
+    return ECT.takeError();
 
-  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 getSingleton(std::move(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 getSingleton(std::move(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 getSingleton(std::move(CT));
-  }
-  const auto &ReservedRegisters = State.getRATC().reservedRegisters();
-  // No tied variables, we pick random values for defs.
+// 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]
+// we might generate:
+//   mov eax, [rdi]
+//   mov eax, [rdi + 64]
+//   mov eax, [rdi + 128]
+//   mov eax, [rdi + 192]
+//   mov eax, [rdi + 256]
+// If the original snippet is:
+//   mov eax, [memory]
+//   add eax, [memory]
+// we might generate:
+//   mov eax, [rdi]
+//   add eax, [rdi + 64]
+//   mov eax, [rdi + 128]
+//   add eax, [rdi + 192]
+//   mov eax, [rdi + 256]
+llvm::Expected<CodeTemplate> UopsSnippetGenerator::generateMemoryCodeTemplate(
+    ExecutionMode EM, llvm::StringRef Info,
+    const std::vector<InstructionTemplate> &OriginalInstrs) const {
+  std::vector<InstructionTemplate> Instrs;
+  if (has(EM, ExecutionMode::PARALLEL_VIA_DISTINCT_MEMORY_ACCESS)) {
+    assert(ScratchSpaceReg && "must not be 0");
+    const unsigned MemStep = ET.getMaxMemoryAccessSize();
+    const size_t MaxInstrs = std::max(
+        OriginalInstrs.size(), UopsSnippetGenerator::kMinNumDifferentAddresses);
+    for (size_t I = 0, E = MaxInstrs; I < E; ++I) {
+      InstructionTemplate IT = OriginalInstrs[I % OriginalInstrs.size()];
+      ET.fillMemoryOperands(IT, ScratchSpaceReg, I * MemStep);
+      Instrs.push_back(std::move(IT));
+    }
+    if (MaxInstrs * MemStep >= BenchmarkRunner::ScratchSpace::kSize)
+      return llvm::make_error<BenchmarkFailure>("Not enough scratch space");
+  } else {
+    Instrs = std::move(OriginalInstrs);
+  CodeTemplate CT;
+  CT.Execution = EM;
+  CT.Info = Info;
+  CT.ScratchSpacePointerInReg = ScratchSpaceReg;
+  CT.Instructions = std::move(Instrs);
+  return std::move(CT);
+}
+
+std::vector<InstructionTemplate> UopsSnippetGenerator::generateStaticRenaming(
+    const Instruction &Instr, const Variable &TiedVar,
+    llvm::BitVector ForbiddenRegs) const {
+  std::vector<InstructionTemplate> Instructions;
+  const auto &Op = Instr.getPrimaryOperand(TiedVar);
+  assert(Op.isReg() && Op.isExplicit() && Op.isDef() &&
+         "Op is expected to be an explicit def register operand");
+  const auto &PossibleRegisters = Op.getRegisterAliasing().sourceBits();
+  for (auto Reg : PossibleRegisters.set_bits()) {
+    if (ForbiddenRegs.test(Reg))
+      continue;
+    Instructions.emplace_back(Instr);
+    Instructions.back().getValueFor(Op) = llvm::MCOperand::createReg(Reg);
+    ForbiddenRegs |= State.getRATC().getRegister(Reg).aliasedBits();
+  }
+  return Instructions;
+
+std::vector<InstructionTemplate>
+UopsSnippetGenerator::generateUseDistinctFromDefs(
+    const Instruction &Instr, llvm::BitVector ForbiddenRegs) const {
+  std::vector<InstructionTemplate> Result;
+  Result.emplace_back(Instr);
+  InstructionTemplate &IT = Result.back();
+  // 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);
-      // Do not use the scratch memory address register.
-      if (ScratchSpaceAliasedRegs)
-        remove(PossibleRegisters, *ScratchSpaceAliasedRegs);
-      assert(PossibleRegisters.any() && "No register left to choose from");
+      remove(PossibleRegisters, ForbiddenRegs);
+      if (PossibleRegisters.none())
+        continue;
       const auto RandomReg = randomBit(PossibleRegisters);
       Defs.set(RandomReg);
       IT.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg);
     }
   }
   // And pick random use values that are not reserved and don't alias with defs.
   const auto DefAliases = getAliasedBits(State.getRegInfo(), Defs);
   for (const auto &Op : Instr.Operands) {
     if (Op.isReg() && Op.isExplicit() && Op.isUse() && !Op.isMemory()) {
       auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
-      remove(PossibleRegisters, ReservedRegisters);
-      // Do not use the scratch memory address register.
-      if (ScratchSpaceAliasedRegs)
-        remove(PossibleRegisters, *ScratchSpaceAliasedRegs);
+      remove(PossibleRegisters, ForbiddenRegs);
       remove(PossibleRegisters, DefAliases);
-      assert(PossibleRegisters.any() && "No register left to choose from");
+      if (PossibleRegisters.none())
+        continue;
       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 getSingleton(std::move(CT));
+  return Result;
+}
+
+std::vector<InstructionTemplate>
+UopsSnippetGenerator::generateSingleInstruction(
+    const Instruction &Instr) const {
+  std::vector<InstructionTemplate> Result;
+  Result.emplace_back(Instr);
+  return Result;
 }
 
 llvm::Expected<std::vector<BenchmarkMeasure>>
 UopsBenchmarkRunner::runMeasurements(const FunctionExecutor &Executor) const {
   const auto &SchedModel = State.getSubtargetInfo().getSchedModel();
 
   std::vector<BenchmarkMeasure> Result;
   const auto &PfmCounters = SchedModel.getExtraProcessorInfo().PfmCounters;

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

 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(); }
+MATCHER_P(HasExecution, EM, "") { return (arg & EM) == EM; }
 
 class X86SnippetGeneratorTest : public ::testing::Test {
 protected:
   X86SnippetGeneratorTest()
       : State("x86_64-unknown-linux", "haswell"),
         MCInstrInfo(State.getInstrInfo()), MCRegisterInfo(State.getRegInfo()) {}
 
   static void SetUpTestCase() {
TEST_F(LatencySnippetGeneratorTest, ImplicitSelfDependencyThroughTiedRegs) {
   // - 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 auto CodeTemplates = checkAndGetCodeTemplates(Opcode);
   ASSERT_THAT(CodeTemplates, SizeIs(1));
   const auto &CT = CodeTemplates[0];
-  EXPECT_THAT(CT.Execution, ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS);
+  EXPECT_THAT(CT.Execution, ExecutionMode::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], IsInvalid()) << "Operand 1 is not set";
   EXPECT_THAT(IT.VariableValues[1], IsInvalid()) << "Operand 2 is not set";
 }
 
TEST_F(UopsSnippetGeneratorTest, ParallelInstruction) {
   // - Op1 Explicit Use RegClass(GR32)
   // - Var0 [Op0]
   // - Var1 [Op1]
   const unsigned Opcode = llvm::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);
+  EXPECT_THAT(CT.Execution,
+              HasExecution(ExecutionMode::ALWAYS_PARALLEL_MISSING_USE_OR_DEF));
   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
   // - 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 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);
+  EXPECT_THAT(CT.Execution,
+              HasExecution(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.VariableValues, SizeIs(0));
 }
 
 TEST_F(UopsSnippetGeneratorTest, StaticRenaming) {
   // CMOVA32rr has tied variables, we enumerate the possible values to execute
   // as many in parallel as possible.
 
   // - 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 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;
+  EXPECT_THAT(CT.Execution,
+              HasExecution(ExecutionMode::PARALLEL_VIA_DISTINCT_EXPLICIT_REGS));
+  constexpr const unsigned kInstructionCount = 14; // 15 registers - EDI.
   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) {
   // - Var2 [Op2]
   // - Var3 [Op3]
   // - hasAliasingRegisters
   const unsigned Opcode = llvm::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);
+  EXPECT_THAT(CT.Execution,
+              HasExecution(ExecutionMode::PARALLEL_VIA_DISTINCT_EXPLICIT_REGS));
   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";
TEST_F(UopsSnippetGeneratorTest, MemoryUse) {
   // - Var5 [Op5]
   // - hasMemoryOperands
   // - hasAliasingRegisters
   const unsigned Opcode = llvm::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);
+  EXPECT_THAT(CT.Execution,
+              HasExecution(ExecutionMode::PARALLEL_VIA_DISTINCT_EXPLICIT_REGS));
   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);