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 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(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{Reg, llvm::APInt()});
  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 static size_t randomIndex(size_t Size) {
 150   assert(Size > 0);
 151   std::uniform_int_distribution<> Distribution(0, Size - 1);
 152   return Distribution(randomGenerator());
 153 }
 154
 155 template <typename C>
 156 static auto randomElement(const C &Container) -> decltype(Container[0]) {
 157   return Container[randomIndex(Container.size())];
 158 }
 159
 160 static void randomize(const Instruction &Instr, const Variable &Var,
 161                       llvm::MCOperand &AssignedValue,
 162                       const llvm::BitVector &ForbiddenRegs) {
 163   const Operand &Op = Instr.getPrimaryOperand(Var);
 164   switch (Op.getExplicitOperandInfo().OperandType) {
 165   case llvm::MCOI::OperandType::OPERAND_IMMEDIATE:
 166     // FIXME: explore immediate values too.
 167     AssignedValue = llvm::MCOperand::createImm(1);
 168     break;
 169   case llvm::MCOI::OperandType::OPERAND_REGISTER: {
 170     assert(Op.isReg());
 171     auto AllowedRegs = Op.getRegisterAliasing().sourceBits();
 172     assert(AllowedRegs.size() == ForbiddenRegs.size());
 173     for (auto I : ForbiddenRegs.set_bits())
 174       AllowedRegs.reset(I);
 175     AssignedValue = llvm::MCOperand::createReg(randomBit(AllowedRegs));
 176     break;
 177   }
 178   default:
 179     break;
 180   }
 181 }
 182
 183 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
 184                                     InstructionTemplate &IB) {
 185   assert(ROV.Op);
 186   if (ROV.Op->isExplicit()) {
 187     auto &AssignedValue = IB.getValueFor(*ROV.Op);
 188     if (AssignedValue.isValid()) {
 189       assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
 190       return;
 191     }
 192     AssignedValue = llvm::MCOperand::createReg(ROV.Reg);
 193   } else {
 194     assert(ROV.Op->isImplicitReg());
 195     assert(ROV.Reg == ROV.Op->getImplicitReg());
 196   }
 197 }
 198
 199 size_t randomBit(const llvm::BitVector &Vector) {
 200   assert(Vector.any());
 201   auto Itr = Vector.set_bits_begin();
 202   for (size_t I = randomIndex(Vector.count()); I != 0; --I)
 203     ++Itr;
 204   return *Itr;
 205 }
 206
 207 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
 208                        InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
 209   assert(!AliasingConfigurations.empty());
 210   assert(!AliasingConfigurations.hasImplicitAliasing());
 211   const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
 212   setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
 213   setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
 214 }
 215
 216 void randomizeUnsetVariables(const llvm::BitVector &ForbiddenRegs,
 217                              InstructionTemplate &IT) {
 218   for (const Variable &Var : IT.Instr.Variables) {
 219     llvm::MCOperand &AssignedValue = IT.getValueFor(Var);
 220     if (!AssignedValue.isValid())
 221       randomize(IT.Instr, Var, AssignedValue, ForbiddenRegs);
 222   }
 223 }
 224
 225 } // namespace exegesis
 226 } // namespace llvm