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