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 "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/FileSystem.h"
  20 #include "llvm/Support/FormatVariadic.h"
  21 #include "llvm/Support/Program.h"
  22
  23 namespace llvm {
  24 namespace exegesis {
  25
  26 std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {
  27   std::vector<CodeTemplate> Result;
  28   Result.push_back(std::move(CT));
  29   return Result;
  30 }
  31
  32 SnippetGeneratorFailure::SnippetGeneratorFailure(const llvm::Twine &S)
  33     : llvm::StringError(S, llvm::inconvertibleErrorCode()) {}
  34
  35 SnippetGenerator::SnippetGenerator(const LLVMState &State) : State(State) {}
  36
  37 SnippetGenerator::~SnippetGenerator() = default;
  38
  39 llvm::Expected<std::vector<BenchmarkCode>>
  40 SnippetGenerator::generateConfigurations(const Instruction &Instr) const {
  41   if (auto E = generateCodeTemplates(Instr)) {
  42     const auto &RATC = State.getRATC();
  43     std::vector<BenchmarkCode> Output;
  44     for (CodeTemplate &CT : E.get()) {
  45       const llvm::BitVector &ForbiddenRegs =
  46           CT.ScratchSpacePointerInReg
  47               ? RATC.getRegister(CT.ScratchSpacePointerInReg).aliasedBits()
  48               : RATC.emptyRegisters();
  49       // TODO: Generate as many BenchmarkCode as needed.
  50       {
  51         BenchmarkCode BC;
  52         BC.Info = CT.Info;
  53         for (InstructionTemplate &IT : CT.Instructions) {
  54           randomizeUnsetVariables(State.getExegesisTarget(), ForbiddenRegs, IT);
  55           BC.Instructions.push_back(IT.build());
  56         }
  57         if (CT.ScratchSpacePointerInReg)
  58           BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
  59         BC.RegisterInitialValues =
  60             computeRegisterInitialValues(CT.Instructions);
  61         Output.push_back(std::move(BC));
  62       }
  63     }
  64     return Output;
  65   } else
  66     return E.takeError();
  67 }
  68
  69 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
  70     const std::vector<InstructionTemplate> &Instructions) const {
  71   // Collect all register uses and create an assignment for each of them.
  72   // Ignore memory operands which are handled separately.
  73   // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
  74   // before the current instruction.
  75   llvm::BitVector DefinedRegs = State.getRATC().emptyRegisters();
  76   std::vector<RegisterValue> RIV;
  77   for (const InstructionTemplate &IT : Instructions) {
  78     // Returns the register that this Operand sets or uses, or 0 if this is not
  79     // a register.
  80     const auto GetOpReg = [&IT](const Operand &Op) -> unsigned {
  81       if (Op.isMemory())
  82         return 0;
  83       if (Op.isImplicitReg())
  84         return Op.getImplicitReg();
  85       if (Op.isExplicit() && IT.getValueFor(Op).isReg())
  86         return IT.getValueFor(Op).getReg();
  87       return 0;
  88     };
  89     // Collect used registers that have never been def'ed.
  90     for (const Operand &Op : IT.Instr.Operands) {
  91       if (Op.isUse()) {
  92         const unsigned Reg = GetOpReg(Op);
  93         if (Reg > 0 && !DefinedRegs.test(Reg)) {
  94           RIV.push_back(RegisterValue::zero(Reg));
  95           DefinedRegs.set(Reg);
  96         }
  97       }
  98     }
  99     // Mark defs as having been def'ed.
 100     for (const Operand &Op : IT.Instr.Operands) {
 101       if (Op.isDef()) {
 102         const unsigned Reg = GetOpReg(Op);
 103         if (Reg > 0)
 104           DefinedRegs.set(Reg);
 105       }
 106     }
 107   }
 108   return RIV;
 109 }
 110
 111 llvm::Expected<std::vector<CodeTemplate>>
 112 generateSelfAliasingCodeTemplates(const Instruction &Instr) {
 113   const AliasingConfigurations SelfAliasing(Instr, Instr);
 114   if (SelfAliasing.empty())
 115     return llvm::make_error<SnippetGeneratorFailure>("empty self aliasing");
 116   std::vector<CodeTemplate> Result;
 117   Result.emplace_back();
 118   CodeTemplate &CT = Result.back();
 119   InstructionTemplate IT(Instr);
 120   if (SelfAliasing.hasImplicitAliasing()) {
 121     CT.Info = "implicit Self cycles, picking random values.";
 122   } else {
 123     CT.Info = "explicit self cycles, selecting one aliasing Conf.";
 124     // This is a self aliasing instruction so defs and uses are from the same
 125     // instance, hence twice IT in the following call.
 126     setRandomAliasing(SelfAliasing, IT, IT);
 127   }
 128   CT.Instructions.push_back(std::move(IT));
 129   return std::move(Result);
 130 }
 131
 132 llvm::Expected<std::vector<CodeTemplate>>
 133 generateUnconstrainedCodeTemplates(const Instruction &Instr,
 134                                    llvm::StringRef Msg) {
 135   std::vector<CodeTemplate> Result;
 136   Result.emplace_back();
 137   CodeTemplate &CT = Result.back();
 138   CT.Info = llvm::formatv("{0}, repeating an unconstrained assignment", Msg);
 139   CT.Instructions.emplace_back(Instr);
 140   return std::move(Result);
 141 }
 142
 143 std::mt19937 &randomGenerator() {
 144   static std::random_device RandomDevice;
 145   static std::mt19937 RandomGenerator(RandomDevice());
 146   return RandomGenerator;
 147 }
 148
 149 size_t randomIndex(size_t Max) {
 150   std::uniform_int_distribution<> Distribution(0, Max);
 151   return Distribution(randomGenerator());
 152 }
 153
 154 template <typename C>
 155 static auto randomElement(const C &Container) -> decltype(Container[0]) {
 156   assert(!Container.empty() &&
 157          "Can't pick a random element from an empty container)");
 158   return Container[randomIndex(Container.size() - 1)];
 159 }
 160
 161 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
 162                                     InstructionTemplate &IB) {
 163   assert(ROV.Op);
 164   if (ROV.Op->isExplicit()) {
 165     auto &AssignedValue = IB.getValueFor(*ROV.Op);
 166     if (AssignedValue.isValid()) {
 167       assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
 168       return;
 169     }
 170     AssignedValue = llvm::MCOperand::createReg(ROV.Reg);
 171   } else {
 172     assert(ROV.Op->isImplicitReg());
 173     assert(ROV.Reg == ROV.Op->getImplicitReg());
 174   }
 175 }
 176
 177 size_t randomBit(const llvm::BitVector &Vector) {
 178   assert(Vector.any());
 179   auto Itr = Vector.set_bits_begin();
 180   for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
 181     ++Itr;
 182   return *Itr;
 183 }
 184
 185 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
 186                        InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
 187   assert(!AliasingConfigurations.empty());
 188   assert(!AliasingConfigurations.hasImplicitAliasing());
 189   const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
 190   setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
 191   setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
 192 }
 193
 194 void randomizeUnsetVariables(const ExegesisTarget &Target,
 195                              const llvm::BitVector &ForbiddenRegs,
 196                              InstructionTemplate &IT) {
 197   for (const Variable &Var : IT.Instr.Variables) {
 198     llvm::MCOperand &AssignedValue = IT.getValueFor(Var);
 199     if (!AssignedValue.isValid())
 200       Target.randomizeMCOperand(IT.Instr, Var, AssignedValue, ForbiddenRegs);
 201   }
 202 }
 203
 204 } // namespace exegesis
 205 } // namespace llvm