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

   1 //===-- SerialSnippetGenerator.cpp ------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "SerialSnippetGenerator.h"
  10
  11 #include "MCInstrDescView.h"
  12 #include "CodeTemplate.h"
  13 #include <algorithm>
  14 #include <numeric>
  15 #include <vector>
  16
  17 namespace llvm {
  18 namespace exegesis {
  19
  20 struct ExecutionClass {
  21   ExecutionMode Mask;
  22   const char *Description;
  23 } static const kExecutionClasses[] = {
  24     {ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS |
  25          ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS,
  26      "Repeating a single implicitly serial instruction"},
  27     {ExecutionMode::SERIAL_VIA_EXPLICIT_REGS,
  28      "Repeating a single explicitly serial instruction"},
  29     {ExecutionMode::SERIAL_VIA_MEMORY_INSTR |
  30          ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR,
  31      "Repeating two instructions"},
  32 };
  33
  34 static constexpr size_t kMaxAliasingInstructions = 10;
  35
  36 static std::vector<const Instruction *>
  37 computeAliasingInstructions(const LLVMState &State, const Instruction *Instr,
  38                             size_t MaxAliasingInstructions,
  39                             const BitVector &ForbiddenRegisters) {
  40   // Randomly iterate the set of instructions.
  41   std::vector<unsigned> Opcodes;
  42   Opcodes.resize(State.getInstrInfo().getNumOpcodes());
  43   std::iota(Opcodes.begin(), Opcodes.end(), 0U);
  44   std::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator());
  45
  46   std::vector<const Instruction *> AliasingInstructions;
  47   for (const unsigned OtherOpcode : Opcodes) {
  48     if (OtherOpcode == Instr->Description.getOpcode())
  49       continue;
  50     const Instruction &OtherInstr = State.getIC().getInstr(OtherOpcode);
  51     if (OtherInstr.hasMemoryOperands())
  52       continue;
  53     if (Instr->hasAliasingRegistersThrough(OtherInstr, ForbiddenRegisters))
  54       AliasingInstructions.push_back(&OtherInstr);
  55     if (AliasingInstructions.size() >= MaxAliasingInstructions)
  56       break;
  57   }
  58   return AliasingInstructions;
  59 }
  60
  61 static ExecutionMode getExecutionModes(const Instruction &Instr,
  62                                        const BitVector &ForbiddenRegisters) {
  63   ExecutionMode EM = ExecutionMode::UNKNOWN;
  64   if (Instr.hasAliasingImplicitRegisters())
  65     EM |= ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS;
  66   if (Instr.hasTiedRegisters())
  67     EM |= ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS;
  68   if (Instr.hasMemoryOperands())
  69     EM |= ExecutionMode::SERIAL_VIA_MEMORY_INSTR;
  70   else {
  71     if (Instr.hasAliasingRegisters(ForbiddenRegisters))
  72       EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS;
  73     if (Instr.hasOneUseOrOneDef())
  74       EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR;
  75   }
  76   return EM;
  77 }
  78
  79 static void appendCodeTemplates(const LLVMState &State,
  80                                 const Instruction *Instr,
  81                                 const BitVector &ForbiddenRegisters,
  82                                 ExecutionMode ExecutionModeBit,
  83                                 StringRef ExecutionClassDescription,
  84                                 std::vector<CodeTemplate> &CodeTemplates) {
  85   assert(isEnumValue(ExecutionModeBit) && "Bit must be a power of two");
  86   switch (ExecutionModeBit) {
  87   case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS:
  88     // Nothing to do, the instruction is always serial.
  89     LLVM_FALLTHROUGH;
  90   case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS: {
  91     // Picking whatever value for the tied variable will make the instruction
  92     // serial.
  93     CodeTemplate CT;
  94     CT.Execution = ExecutionModeBit;
  95     CT.Info = ExecutionClassDescription;
  96     CT.Instructions.push_back(Instr);
  97     CodeTemplates.push_back(std::move(CT));
  98     return;
  99   }
 100   case ExecutionMode::SERIAL_VIA_MEMORY_INSTR: {
 101     // Select back-to-back memory instruction.
 102     // TODO: Implement me.
 103     return;
 104   }
 105   case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS: {
 106     // Making the execution of this instruction serial by selecting one def
 107     // register to alias with one use register.
 108     const AliasingConfigurations SelfAliasing(*Instr, *Instr);
 109     assert(!SelfAliasing.empty() && !SelfAliasing.hasImplicitAliasing() &&
 110            "Instr must alias itself explicitly");
 111     InstructionTemplate IT(Instr);
 112     // This is a self aliasing instruction so defs and uses are from the same
 113     // instance, hence twice IT in the following call.
 114     setRandomAliasing(SelfAliasing, IT, IT);
 115     CodeTemplate CT;
 116     CT.Execution = ExecutionModeBit;
 117     CT.Info = ExecutionClassDescription;
 118     CT.Instructions.push_back(std::move(IT));
 119     CodeTemplates.push_back(std::move(CT));
 120     return;
 121   }
 122   case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR: {
 123     // Select back-to-back non-memory instruction.
 124     for (const auto *OtherInstr : computeAliasingInstructions(
 125              State, Instr, kMaxAliasingInstructions, ForbiddenRegisters)) {
 126       const AliasingConfigurations Forward(*Instr, *OtherInstr);
 127       const AliasingConfigurations Back(*OtherInstr, *Instr);
 128       InstructionTemplate ThisIT(Instr);
 129       InstructionTemplate OtherIT(OtherInstr);
 130       if (!Forward.hasImplicitAliasing())
 131         setRandomAliasing(Forward, ThisIT, OtherIT);
 132       if (!Back.hasImplicitAliasing())
 133         setRandomAliasing(Back, OtherIT, ThisIT);
 134       CodeTemplate CT;
 135       CT.Execution = ExecutionModeBit;
 136       CT.Info = ExecutionClassDescription;
 137       CT.Instructions.push_back(std::move(ThisIT));
 138       CT.Instructions.push_back(std::move(OtherIT));
 139       CodeTemplates.push_back(std::move(CT));
 140     }
 141     return;
 142   }
 143   default:
 144     llvm_unreachable("Unhandled enum value");
 145   }
 146 }
 147
 148 SerialSnippetGenerator::~SerialSnippetGenerator() = default;
 149
 150 Expected<std::vector<CodeTemplate>>
 151 SerialSnippetGenerator::generateCodeTemplates(
 152     const Instruction &Instr, const BitVector &ForbiddenRegisters) const {
 153   std::vector<CodeTemplate> Results;
 154   const ExecutionMode EM = getExecutionModes(Instr, ForbiddenRegisters);
 155   for (const auto EC : kExecutionClasses) {
 156     for (const auto ExecutionModeBit : getExecutionModeBits(EM & EC.Mask))
 157       appendCodeTemplates(State, &Instr, ForbiddenRegisters, ExecutionModeBit,
 158                           EC.Description, Results);
 159     if (!Results.empty())
 160       break;
 161   }
 162   if (Results.empty())
 163     return make_error<Failure>(
 164         "No strategy found to make the execution serial");
 165   return std::move(Results);
 166 }
 167
 168 } // namespace exegesis
 169 } // namespace llvm