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/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 Expected<std::vector<BenchmarkCode>> SnippetGenerator::generateConfigurations(
  42     const Instruction &Instr, const BitVector &ExtraForbiddenRegs) const {
  43   BitVector ForbiddenRegs = State.getRATC().reservedRegisters();
  44   ForbiddenRegs |= ExtraForbiddenRegs;
  45   // If the instruction has memory registers, prevent the generator from
  46   // using the scratch register and its aliasing registers.
  47   if (Instr.hasMemoryOperands()) {
  48     const auto &ET = State.getExegesisTarget();
  49     unsigned ScratchSpacePointerInReg =
  50         ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
  51     if (ScratchSpacePointerInReg == 0)
  52       return make_error<Failure>(
  53           "Infeasible : target does not support memory instructions");
  54     const auto &ScratchRegAliases =
  55         State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits();
  56     // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
  57     // FIXME: We could make a copy of the scratch register.
  58     for (const auto &Op : Instr.Operands) {
  59       if (Op.isDef() && Op.isImplicitReg() &&
  60           ScratchRegAliases.test(Op.getImplicitReg()))
  61         return make_error<Failure>(
  62             "Infeasible : memory instruction uses scratch memory register");
  63     }
  64     ForbiddenRegs |= ScratchRegAliases;
  65   }
  66
  67   if (auto E = generateCodeTemplates(Instr, ForbiddenRegs)) {
  68     std::vector<BenchmarkCode> Output;
  69     for (CodeTemplate &CT : E.get()) {
  70       // TODO: Generate as many BenchmarkCode as needed.
  71       {
  72         BenchmarkCode BC;
  73         BC.Info = CT.Info;
  74         for (InstructionTemplate &IT : CT.Instructions) {
  75           randomizeUnsetVariables(State.getExegesisTarget(), ForbiddenRegs, IT);
  76           BC.Key.Instructions.push_back(IT.build());
  77         }
  78         if (CT.ScratchSpacePointerInReg)
  79           BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
  80         BC.Key.RegisterInitialValues =
  81             computeRegisterInitialValues(CT.Instructions);
  82         BC.Key.Config = CT.Config;
  83         Output.push_back(std::move(BC));
  84         if (Output.size() >= Opts.MaxConfigsPerOpcode)
  85           return Output; // Early exit if we exceeded the number of allowed
  86                          // configs.
  87       }
  88     }
  89     return Output;
  90   } else
  91     return E.takeError();
  92 }
  93
  94 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
  95     const std::vector<InstructionTemplate> &Instructions) const {
  96   // Collect all register uses and create an assignment for each of them.
  97   // Ignore memory operands which are handled separately.
  98   // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
  99   // before the current instruction.
 100   BitVector DefinedRegs = State.getRATC().emptyRegisters();
 101   std::vector<RegisterValue> RIV;
 102   for (const InstructionTemplate &IT : Instructions) {
 103     // Returns the register that this Operand sets or uses, or 0 if this is not
 104     // a register.
 105     const auto GetOpReg = [&IT](const Operand &Op) -> unsigned {
 106       if (Op.isMemory())
 107         return 0;
 108       if (Op.isImplicitReg())
 109         return Op.getImplicitReg();
 110       if (Op.isExplicit() && IT.getValueFor(Op).isReg())
 111         return IT.getValueFor(Op).getReg();
 112       return 0;
 113     };
 114     // Collect used registers that have never been def'ed.
 115     for (const Operand &Op : IT.Instr.Operands) {
 116       if (Op.isUse()) {
 117         const unsigned Reg = GetOpReg(Op);
 118         if (Reg > 0 && !DefinedRegs.test(Reg)) {
 119           RIV.push_back(RegisterValue::zero(Reg));
 120           DefinedRegs.set(Reg);
 121         }
 122       }
 123     }
 124     // Mark defs as having been def'ed.
 125     for (const Operand &Op : IT.Instr.Operands) {
 126       if (Op.isDef()) {
 127         const unsigned Reg = GetOpReg(Op);
 128         if (Reg > 0)
 129           DefinedRegs.set(Reg);
 130       }
 131     }
 132   }
 133   return RIV;
 134 }
 135
 136 Expected<std::vector<CodeTemplate>>
 137 generateSelfAliasingCodeTemplates(const Instruction &Instr) {
 138   const AliasingConfigurations SelfAliasing(Instr, Instr);
 139   if (SelfAliasing.empty())
 140     return make_error<SnippetGeneratorFailure>("empty self aliasing");
 141   std::vector<CodeTemplate> Result;
 142   Result.emplace_back();
 143   CodeTemplate &CT = Result.back();
 144   InstructionTemplate IT(Instr);
 145   if (SelfAliasing.hasImplicitAliasing()) {
 146     CT.Info = "implicit Self cycles, picking random values.";
 147   } else {
 148     CT.Info = "explicit self cycles, selecting one aliasing Conf.";
 149     // This is a self aliasing instruction so defs and uses are from the same
 150     // instance, hence twice IT in the following call.
 151     setRandomAliasing(SelfAliasing, IT, IT);
 152   }
 153   CT.Instructions.push_back(std::move(IT));
 154   return std::move(Result);
 155 }
 156
 157 Expected<std::vector<CodeTemplate>>
 158 generateUnconstrainedCodeTemplates(const Instruction &Instr, StringRef Msg) {
 159   std::vector<CodeTemplate> Result;
 160   Result.emplace_back();
 161   CodeTemplate &CT = Result.back();
 162   CT.Info = formatv("{0}, repeating an unconstrained assignment", Msg);
 163   CT.Instructions.emplace_back(Instr);
 164   return std::move(Result);
 165 }
 166
 167 std::mt19937 &randomGenerator() {
 168   static std::random_device RandomDevice;
 169   static std::mt19937 RandomGenerator(RandomDevice());
 170   return RandomGenerator;
 171 }
 172
 173 size_t randomIndex(size_t Max) {
 174   std::uniform_int_distribution<> Distribution(0, Max);
 175   return Distribution(randomGenerator());
 176 }
 177
 178 template <typename C>
 179 static auto randomElement(const C &Container) -> decltype(Container[0]) {
 180   assert(!Container.empty() &&
 181          "Can't pick a random element from an empty container)");
 182   return Container[randomIndex(Container.size() - 1)];
 183 }
 184
 185 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
 186                                     InstructionTemplate &IB) {
 187   assert(ROV.Op);
 188   if (ROV.Op->isExplicit()) {
 189     auto &AssignedValue = IB.getValueFor(*ROV.Op);
 190     if (AssignedValue.isValid()) {
 191       assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
 192       return;
 193     }
 194     AssignedValue = MCOperand::createReg(ROV.Reg);
 195   } else {
 196     assert(ROV.Op->isImplicitReg());
 197     assert(ROV.Reg == ROV.Op->getImplicitReg());
 198   }
 199 }
 200
 201 size_t randomBit(const BitVector &Vector) {
 202   assert(Vector.any());
 203   auto Itr = Vector.set_bits_begin();
 204   for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
 205     ++Itr;
 206   return *Itr;
 207 }
 208
 209 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
 210                        InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
 211   assert(!AliasingConfigurations.empty());
 212   assert(!AliasingConfigurations.hasImplicitAliasing());
 213   const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
 214   setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
 215   setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
 216 }
 217
 218 void randomizeUnsetVariables(const ExegesisTarget &Target,
 219                              const BitVector &ForbiddenRegs,
 220                              InstructionTemplate &IT) {
 221   for (const Variable &Var : IT.Instr.Variables) {
 222     MCOperand &AssignedValue = IT.getValueFor(Var);
 223     if (!AssignedValue.isValid())
 224       Target.randomizeMCOperand(IT.Instr, Var, AssignedValue, ForbiddenRegs);
 225   }
 226 }
 227
 228 } // namespace exegesis
 229 } // namespace llvm