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

   1 //===-- SnippetGenerator.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 <array>
  10 #include <string>
  11
  12 #include "Assembler.h"
  13 #include "Error.h"
  14 #include "MCInstrDescView.h"
  15 #include "SnippetGenerator.h"
  16 #include "Target.h"
  17 #include "llvm/ADT/StringExtras.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/ADT/Twine.h"
  20 #include "llvm/Support/Error.h"
  21 #include "llvm/Support/FileSystem.h"
  22 #include "llvm/Support/FormatVariadic.h"
  23 #include "llvm/Support/Program.h"
  24
  25 namespace llvm {
  26 namespace exegesis {
  27
  28 std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {
  29   std::vector<CodeTemplate> Result;
  30   Result.push_back(std::move(CT));
  31   return Result;
  32 }
  33
  34 SnippetGeneratorFailure::SnippetGeneratorFailure(const Twine &S)
  35     : StringError(S, inconvertibleErrorCode()) {}
  36
  37 SnippetGenerator::SnippetGenerator(const LLVMState &State, const Options &Opts)
  38     : State(State), Opts(Opts) {}
  39
  40 SnippetGenerator::~SnippetGenerator() = default;
  41
  42 Error SnippetGenerator::generateConfigurations(
  43     const InstructionTemplate &Variant, std::vector<BenchmarkCode> &Benchmarks,
  44     const BitVector &ExtraForbiddenRegs) const {
  45   BitVector ForbiddenRegs = State.getRATC().reservedRegisters();
  46   ForbiddenRegs |= ExtraForbiddenRegs;
  47   // If the instruction has memory registers, prevent the generator from
  48   // using the scratch register and its aliasing registers.
  49   if (Variant.getInstr().hasMemoryOperands()) {
  50     const auto &ET = State.getExegesisTarget();
  51     unsigned ScratchSpacePointerInReg =
  52         ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
  53     if (ScratchSpacePointerInReg == 0)
  54       return make_error<Failure>(
  55           "Infeasible : target does not support memory instructions");
  56     const auto &ScratchRegAliases =
  57         State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits();
  58     // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
  59     // FIXME: We could make a copy of the scratch register.
  60     for (const auto &Op : Variant.getInstr().Operands) {
  61       if (Op.isDef() && Op.isImplicitReg() &&
  62           ScratchRegAliases.test(Op.getImplicitReg()))
  63         return make_error<Failure>(
  64             "Infeasible : memory instruction uses scratch memory register");
  65     }
  66     ForbiddenRegs |= ScratchRegAliases;
  67   }
  68
  69   if (auto E = generateCodeTemplates(Variant, ForbiddenRegs)) {
  70     MutableArrayRef<CodeTemplate> Templates = E.get();
  71
  72     // Avoid reallocations in the loop.
  73     Benchmarks.reserve(Benchmarks.size() + Templates.size());
  74     for (CodeTemplate &CT : Templates) {
  75       // TODO: Generate as many BenchmarkCode as needed.
  76       {
  77         BenchmarkCode BC;
  78         BC.Info = CT.Info;
  79         BC.Key.Instructions.reserve(CT.Instructions.size());
  80         for (InstructionTemplate &IT : CT.Instructions) {
  81           if (auto Error = randomizeUnsetVariables(State, ForbiddenRegs, IT))
  82             return Error;
  83           MCInst Inst = IT.build();
  84           if (auto Error = validateGeneratedInstruction(State, Inst))
  85             return Error;
  86           BC.Key.Instructions.push_back(Inst);
  87         }
  88         if (CT.ScratchSpacePointerInReg)
  89           BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
  90         BC.Key.RegisterInitialValues =
  91             computeRegisterInitialValues(CT.Instructions);
  92         BC.Key.Config = CT.Config;
  93         Benchmarks.emplace_back(std::move(BC));
  94         if (Benchmarks.size() >= Opts.MaxConfigsPerOpcode) {
  95           // We reached the number of  allowed configs and return early.
  96           return Error::success();
  97         }
  98       }
  99     }
 100     return Error::success();
 101   } else
 102     return E.takeError();
 103 }
 104
 105 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
 106     const std::vector<InstructionTemplate> &Instructions) const {
 107   // Collect all register uses and create an assignment for each of them.
 108   // Ignore memory operands which are handled separately.
 109   // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
 110   // before the current instruction.
 111   BitVector DefinedRegs = State.getRATC().emptyRegisters();
 112   std::vector<RegisterValue> RIV;
 113   for (const InstructionTemplate &IT : Instructions) {
 114     // Returns the register that this Operand sets or uses, or 0 if this is not
 115     // a register.
 116     const auto GetOpReg = [&IT](const Operand &Op) -> unsigned {
 117       if (Op.isMemory())
 118         return 0;
 119       if (Op.isImplicitReg())
 120         return Op.getImplicitReg();
 121       if (Op.isExplicit() && IT.getValueFor(Op).isReg())
 122         return IT.getValueFor(Op).getReg();
 123       return 0;
 124     };
 125     // Collect used registers that have never been def'ed.
 126     for (const Operand &Op : IT.getInstr().Operands) {
 127       if (Op.isUse()) {
 128         const unsigned Reg = GetOpReg(Op);
 129         if (Reg > 0 && !DefinedRegs.test(Reg)) {
 130           RIV.push_back(RegisterValue::zero(Reg));
 131           DefinedRegs.set(Reg);
 132         }
 133       }
 134     }
 135     // Mark defs as having been def'ed.
 136     for (const Operand &Op : IT.getInstr().Operands) {
 137       if (Op.isDef()) {
 138         const unsigned Reg = GetOpReg(Op);
 139         if (Reg > 0)
 140           DefinedRegs.set(Reg);
 141       }
 142     }
 143   }
 144   return RIV;
 145 }
 146
 147 Expected<std::vector<CodeTemplate>>
 148 generateSelfAliasingCodeTemplates(InstructionTemplate Variant,
 149                                   const BitVector &ForbiddenRegisters) {
 150   const AliasingConfigurations SelfAliasing(
 151       Variant.getInstr(), Variant.getInstr(), ForbiddenRegisters);
 152   if (SelfAliasing.empty())
 153     return make_error<SnippetGeneratorFailure>("empty self aliasing");
 154   std::vector<CodeTemplate> Result;
 155   Result.emplace_back();
 156   CodeTemplate &CT = Result.back();
 157   if (SelfAliasing.hasImplicitAliasing()) {
 158     CT.Info = "implicit Self cycles, picking random values.";
 159   } else {
 160     CT.Info = "explicit self cycles, selecting one aliasing Conf.";
 161     // This is a self aliasing instruction so defs and uses are from the same
 162     // instance, hence twice Variant in the following call.
 163     setRandomAliasing(SelfAliasing, Variant, Variant);
 164   }
 165   CT.Instructions.push_back(std::move(Variant));
 166   return std::move(Result);
 167 }
 168
 169 Expected<std::vector<CodeTemplate>>
 170 generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant,
 171                                    StringRef Msg) {
 172   std::vector<CodeTemplate> Result;
 173   Result.emplace_back();
 174   CodeTemplate &CT = Result.back();
 175   CT.Info =
 176       std::string(formatv("{0}, repeating an unconstrained assignment", Msg));
 177   CT.Instructions.push_back(std::move(Variant));
 178   return std::move(Result);
 179 }
 180
 181 std::mt19937 &randomGenerator() {
 182   static std::random_device RandomDevice;
 183   static std::mt19937 RandomGenerator(RandomDevice());
 184   return RandomGenerator;
 185 }
 186
 187 size_t randomIndex(size_t Max) {
 188   std::uniform_int_distribution<> Distribution(0, Max);
 189   return Distribution(randomGenerator());
 190 }
 191
 192 template <typename C> static decltype(auto) randomElement(const C &Container) {
 193   assert(!Container.empty() &&
 194          "Can't pick a random element from an empty container)");
 195   return Container[randomIndex(Container.size() - 1)];
 196 }
 197
 198 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
 199                                     InstructionTemplate &IB) {
 200   assert(ROV.Op);
 201   if (ROV.Op->isExplicit()) {
 202     auto &AssignedValue = IB.getValueFor(*ROV.Op);
 203     if (AssignedValue.isValid()) {
 204       assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
 205       return;
 206     }
 207     AssignedValue = MCOperand::createReg(ROV.Reg);
 208   } else {
 209     assert(ROV.Op->isImplicitReg());
 210     assert(ROV.Reg == ROV.Op->getImplicitReg());
 211   }
 212 }
 213
 214 size_t randomBit(const BitVector &Vector) {
 215   assert(Vector.any());
 216   auto Itr = Vector.set_bits_begin();
 217   for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
 218     ++Itr;
 219   return *Itr;
 220 }
 221
 222 std::optional<int> getFirstCommonBit(const BitVector &A, const BitVector &B) {
 223   BitVector Intersect = A;
 224   Intersect &= B;
 225   int idx = Intersect.find_first();
 226   if (idx != -1)
 227     return idx;
 228   return {};
 229 }
 230
 231 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
 232                        InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
 233   assert(!AliasingConfigurations.empty());
 234   assert(!AliasingConfigurations.hasImplicitAliasing());
 235   const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
 236   setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
 237   setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
 238 }
 239
 240 static Error randomizeMCOperand(const LLVMState &State,
 241                                 const Instruction &Instr, const Variable &Var,
 242                                 MCOperand &AssignedValue,
 243                                 const BitVector &ForbiddenRegs) {
 244   const Operand &Op = Instr.getPrimaryOperand(Var);
 245   if (Op.getExplicitOperandInfo().OperandType >=
 246       MCOI::OperandType::OPERAND_FIRST_TARGET)
 247     return State.getExegesisTarget().randomizeTargetMCOperand(
 248         Instr, Var, AssignedValue, ForbiddenRegs);
 249   switch (Op.getExplicitOperandInfo().OperandType) {
 250   case MCOI::OperandType::OPERAND_IMMEDIATE:
 251     // FIXME: explore immediate values too.
 252     AssignedValue = MCOperand::createImm(1);
 253     break;
 254   case MCOI::OperandType::OPERAND_REGISTER: {
 255     assert(Op.isReg());
 256     auto AllowedRegs = Op.getRegisterAliasing().sourceBits();
 257     assert(AllowedRegs.size() == ForbiddenRegs.size());
 258     for (auto I : ForbiddenRegs.set_bits())
 259       AllowedRegs.reset(I);
 260     if (!AllowedRegs.any())
 261       return make_error<Failure>(
 262           Twine("no available registers:\ncandidates:\n")
 263               .concat(debugString(State.getRegInfo(),
 264                                   Op.getRegisterAliasing().sourceBits()))
 265               .concat("\nforbidden:\n")
 266               .concat(debugString(State.getRegInfo(), ForbiddenRegs)));
 267     AssignedValue = MCOperand::createReg(randomBit(AllowedRegs));
 268     break;
 269   }
 270   default:
 271     break;
 272   }
 273   return Error::success();
 274 }
 275
 276 Error randomizeUnsetVariables(const LLVMState &State,
 277                               const BitVector &ForbiddenRegs,
 278                               InstructionTemplate &IT) {
 279   for (const Variable &Var : IT.getInstr().Variables) {
 280     MCOperand &AssignedValue = IT.getValueFor(Var);
 281     if (!AssignedValue.isValid())
 282       if (auto Err = randomizeMCOperand(State, IT.getInstr(), Var,
 283                                         AssignedValue, ForbiddenRegs))
 284         return Err;
 285   }
 286   return Error::success();
 287 }
 288
 289 Error validateGeneratedInstruction(const LLVMState &State, const MCInst &Inst) {
 290   for (const auto &Operand : Inst) {
 291     if (!Operand.isValid()) {
 292       // Mention the particular opcode - it is not necessarily the "main"
 293       // opcode being benchmarked by this snippet. For example, serial snippet
 294       // generator uses one more opcode when in SERIAL_VIA_NON_MEMORY_INSTR
 295       // execution mode.
 296       const auto OpcodeName = State.getInstrInfo().getName(Inst.getOpcode());
 297       return make_error<Failure>("Not all operands were initialized by the "
 298                                  "snippet generator for " +
 299                                  OpcodeName + " opcode.");
 300     }
 301   }
 302   return Error::success();
 303 }
 304
 305 } // namespace exegesis
 306 } // namespace llvm