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