tools/llvm-exegesis/lib/SnippetGenerator.cpp

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