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