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/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         for (InstructionTemplate &IT : CT.Instructions) {
  79           if (auto error = randomizeUnsetVariables(State, ForbiddenRegs, IT))
  80             return error;
  81           BC.Key.Instructions.push_back(IT.build());
  82         }
  83         if (CT.ScratchSpacePointerInReg)
  84           BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
  85         BC.Key.RegisterInitialValues =
  86             computeRegisterInitialValues(CT.Instructions);
  87         BC.Key.Config = CT.Config;
  88         Benchmarks.emplace_back(std::move(BC));
  89         if (Benchmarks.size() >= Opts.MaxConfigsPerOpcode) {
  90           // We reached the number of  allowed configs and return early.
  91           return Error::success();
  92         }
  93       }
  94     }
  95     return Error::success();
  96   } else
  97     return E.takeError();
  98 }
  99
 100 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
 101     const std::vector<InstructionTemplate> &Instructions) const {
 102   // Collect all register uses and create an assignment for each of them.
 103   // Ignore memory operands which are handled separately.
 104   // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
 105   // before the current instruction.
 106   BitVector DefinedRegs = State.getRATC().emptyRegisters();
 107   std::vector<RegisterValue> RIV;
 108   for (const InstructionTemplate &IT : Instructions) {
 109     // Returns the register that this Operand sets or uses, or 0 if this is not
 110     // a register.
 111     const auto GetOpReg = [&IT](const Operand &Op) -> unsigned {
 112       if (Op.isMemory())
 113         return 0;
 114       if (Op.isImplicitReg())
 115         return Op.getImplicitReg();
 116       if (Op.isExplicit() && IT.getValueFor(Op).isReg())
 117         return IT.getValueFor(Op).getReg();
 118       return 0;
 119     };
 120     // Collect used registers that have never been def'ed.
 121     for (const Operand &Op : IT.getInstr().Operands) {
 122       if (Op.isUse()) {
 123         const unsigned Reg = GetOpReg(Op);
 124         if (Reg > 0 && !DefinedRegs.test(Reg)) {
 125           RIV.push_back(RegisterValue::zero(Reg));
 126           DefinedRegs.set(Reg);
 127         }
 128       }
 129     }
 130     // Mark defs as having been def'ed.
 131     for (const Operand &Op : IT.getInstr().Operands) {
 132       if (Op.isDef()) {
 133         const unsigned Reg = GetOpReg(Op);
 134         if (Reg > 0)
 135           DefinedRegs.set(Reg);
 136       }
 137     }
 138   }
 139   return RIV;
 140 }
 141
 142 Expected<std::vector<CodeTemplate>>
 143 generateSelfAliasingCodeTemplates(InstructionTemplate Variant) {
 144   const AliasingConfigurations SelfAliasing(Variant.getInstr(),
 145                                             Variant.getInstr());
 146   if (SelfAliasing.empty())
 147     return make_error<SnippetGeneratorFailure>("empty self aliasing");
 148   std::vector<CodeTemplate> Result;
 149   Result.emplace_back();
 150   CodeTemplate &CT = Result.back();
 151   if (SelfAliasing.hasImplicitAliasing()) {
 152     CT.Info = "implicit Self cycles, picking random values.";
 153   } else {
 154     CT.Info = "explicit self cycles, selecting one aliasing Conf.";
 155     // This is a self aliasing instruction so defs and uses are from the same
 156     // instance, hence twice Variant in the following call.
 157     setRandomAliasing(SelfAliasing, Variant, Variant);
 158   }
 159   CT.Instructions.push_back(std::move(Variant));
 160   return std::move(Result);
 161 }
 162
 163 Expected<std::vector<CodeTemplate>>
 164 generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant,
 165                                    StringRef Msg) {
 166   std::vector<CodeTemplate> Result;
 167   Result.emplace_back();
 168   CodeTemplate &CT = Result.back();
 169   CT.Info =
 170       std::string(formatv("{0}, repeating an unconstrained assignment", Msg));
 171   CT.Instructions.push_back(std::move(Variant));
 172   return std::move(Result);
 173 }
 174
 175 std::mt19937 &randomGenerator() {
 176   static std::random_device RandomDevice;
 177   static std::mt19937 RandomGenerator(RandomDevice());
 178   return RandomGenerator;
 179 }
 180
 181 size_t randomIndex(size_t Max) {
 182   std::uniform_int_distribution<> Distribution(0, Max);
 183   return Distribution(randomGenerator());
 184 }
 185
 186 template <typename C> static decltype(auto) randomElement(const C &Container) {
 187   assert(!Container.empty() &&
 188          "Can't pick a random element from an empty container)");
 189   return Container[randomIndex(Container.size() - 1)];
 190 }
 191
 192 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
 193                                     InstructionTemplate &IB) {
 194   assert(ROV.Op);
 195   if (ROV.Op->isExplicit()) {
 196     auto &AssignedValue = IB.getValueFor(*ROV.Op);
 197     if (AssignedValue.isValid()) {
 198       assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
 199       return;
 200     }
 201     AssignedValue = MCOperand::createReg(ROV.Reg);
 202   } else {
 203     assert(ROV.Op->isImplicitReg());
 204     assert(ROV.Reg == ROV.Op->getImplicitReg());
 205   }
 206 }
 207
 208 size_t randomBit(const BitVector &Vector) {
 209   assert(Vector.any());
 210   auto Itr = Vector.set_bits_begin();
 211   for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
 212     ++Itr;
 213   return *Itr;
 214 }
 215
 216 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
 217                        InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
 218   assert(!AliasingConfigurations.empty());
 219   assert(!AliasingConfigurations.hasImplicitAliasing());
 220   const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
 221   setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
 222   setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
 223 }
 224
 225 static Error randomizeMCOperand(const LLVMState &State,
 226                                 const Instruction &Instr, const Variable &Var,
 227                                 MCOperand &AssignedValue,
 228                                 const BitVector &ForbiddenRegs) {
 229   const Operand &Op = Instr.getPrimaryOperand(Var);
 230   if (Op.getExplicitOperandInfo().OperandType >=
 231       MCOI::OperandType::OPERAND_FIRST_TARGET)
 232     return State.getExegesisTarget().randomizeTargetMCOperand(
 233         Instr, Var, AssignedValue, ForbiddenRegs);
 234   switch (Op.getExplicitOperandInfo().OperandType) {
 235   case MCOI::OperandType::OPERAND_IMMEDIATE:
 236     // FIXME: explore immediate values too.
 237     AssignedValue = MCOperand::createImm(1);
 238     break;
 239   case MCOI::OperandType::OPERAND_REGISTER: {
 240     assert(Op.isReg());
 241     auto AllowedRegs = Op.getRegisterAliasing().sourceBits();
 242     assert(AllowedRegs.size() == ForbiddenRegs.size());
 243     for (auto I : ForbiddenRegs.set_bits())
 244       AllowedRegs.reset(I);
 245     if (!AllowedRegs.any())
 246       return make_error<Failure>(
 247           Twine("no available registers:\ncandidates:\n")
 248               .concat(debugString(State.getRegInfo(),
 249                                   Op.getRegisterAliasing().sourceBits()))
 250               .concat("\nforbidden:\n")
 251               .concat(debugString(State.getRegInfo(), ForbiddenRegs)));
 252     AssignedValue = MCOperand::createReg(randomBit(AllowedRegs));
 253     break;
 254   }
 255   default:
 256     break;
 257   }
 258   return Error::success();
 259 }
 260
 261 Error randomizeUnsetVariables(const LLVMState &State,
 262                               const BitVector &ForbiddenRegs,
 263                               InstructionTemplate &IT) {
 264   for (const Variable &Var : IT.getInstr().Variables) {
 265     MCOperand &AssignedValue = IT.getValueFor(Var);
 266     if (!AssignedValue.isValid())
 267       if (auto Err = randomizeMCOperand(State, IT.getInstr(), Var,
 268                                         AssignedValue, ForbiddenRegs))
 269         return Err;
 270   }
 271   return Error::success();
 272 }
 273
 274 } // namespace exegesis
 275 } // namespace llvm