SnippetGenerator.cpp 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286
  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. #include <array>
  9. #include <string>
  10. #include "Assembler.h"
  11. #include "Error.h"
  12. #include "MCInstrDescView.h"
  13. #include "SnippetGenerator.h"
  14. #include "Target.h"
  15. #include "llvm/ADT/StringExtras.h"
  16. #include "llvm/ADT/StringRef.h"
  17. #include "llvm/ADT/Twine.h"
  18. #include "llvm/Support/FileSystem.h"
  19. #include "llvm/Support/FormatVariadic.h"
  20. #include "llvm/Support/Program.h"
  21. namespace llvm {
  22. namespace exegesis {
  23. std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {
  24. std::vector<CodeTemplate> Result;
  25. Result.push_back(std::move(CT));
  26. return Result;
  27. }
  28. SnippetGeneratorFailure::SnippetGeneratorFailure(const Twine &S)
  29. : StringError(S, inconvertibleErrorCode()) {}
  30. SnippetGenerator::SnippetGenerator(const LLVMState &State, const Options &Opts)
  31. : State(State), Opts(Opts) {}
  32. SnippetGenerator::~SnippetGenerator() = default;
  33. Error SnippetGenerator::generateConfigurations(
  34. const InstructionTemplate &Variant, std::vector<BenchmarkCode> &Benchmarks,
  35. const BitVector &ExtraForbiddenRegs) const {
  36. BitVector ForbiddenRegs = State.getRATC().reservedRegisters();
  37. ForbiddenRegs |= ExtraForbiddenRegs;
  38. // If the instruction has memory registers, prevent the generator from
  39. // using the scratch register and its aliasing registers.
  40. if (Variant.getInstr().hasMemoryOperands()) {
  41. const auto &ET = State.getExegesisTarget();
  42. unsigned ScratchSpacePointerInReg =
  43. ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
  44. if (ScratchSpacePointerInReg == 0)
  45. return make_error<Failure>(
  46. "Infeasible : target does not support memory instructions");
  47. const auto &ScratchRegAliases =
  48. State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits();
  49. // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
  50. // FIXME: We could make a copy of the scratch register.
  51. for (const auto &Op : Variant.getInstr().Operands) {
  52. if (Op.isDef() && Op.isImplicitReg() &&
  53. ScratchRegAliases.test(Op.getImplicitReg()))
  54. return make_error<Failure>(
  55. "Infeasible : memory instruction uses scratch memory register");
  56. }
  57. ForbiddenRegs |= ScratchRegAliases;
  58. }
  59. if (auto E = generateCodeTemplates(Variant, ForbiddenRegs)) {
  60. MutableArrayRef<CodeTemplate> Templates = E.get();
  61. // Avoid reallocations in the loop.
  62. Benchmarks.reserve(Benchmarks.size() + Templates.size());
  63. for (CodeTemplate &CT : Templates) {
  64. // TODO: Generate as many BenchmarkCode as needed.
  65. {
  66. BenchmarkCode BC;
  67. BC.Info = CT.Info;
  68. BC.Key.Instructions.reserve(CT.Instructions.size());
  69. for (InstructionTemplate &IT : CT.Instructions) {
  70. if (auto error = randomizeUnsetVariables(State, ForbiddenRegs, IT))
  71. return error;
  72. BC.Key.Instructions.push_back(IT.build());
  73. }
  74. if (CT.ScratchSpacePointerInReg)
  75. BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
  76. BC.Key.RegisterInitialValues =
  77. computeRegisterInitialValues(CT.Instructions);
  78. BC.Key.Config = CT.Config;
  79. Benchmarks.emplace_back(std::move(BC));
  80. if (Benchmarks.size() >= Opts.MaxConfigsPerOpcode) {
  81. // We reached the number of allowed configs and return early.
  82. return Error::success();
  83. }
  84. }
  85. }
  86. return Error::success();
  87. } else
  88. return E.takeError();
  89. }
  90. std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
  91. const std::vector<InstructionTemplate> &Instructions) const {
  92. // Collect all register uses and create an assignment for each of them.
  93. // Ignore memory operands which are handled separately.
  94. // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
  95. // before the current instruction.
  96. BitVector DefinedRegs = State.getRATC().emptyRegisters();
  97. std::vector<RegisterValue> RIV;
  98. for (const InstructionTemplate &IT : Instructions) {
  99. // Returns the register that this Operand sets or uses, or 0 if this is not
  100. // a register.
  101. const auto GetOpReg = [&IT](const Operand &Op) -> unsigned {
  102. if (Op.isMemory())
  103. return 0;
  104. if (Op.isImplicitReg())
  105. return Op.getImplicitReg();
  106. if (Op.isExplicit() && IT.getValueFor(Op).isReg())
  107. return IT.getValueFor(Op).getReg();
  108. return 0;
  109. };
  110. // Collect used registers that have never been def'ed.
  111. for (const Operand &Op : IT.getInstr().Operands) {
  112. if (Op.isUse()) {
  113. const unsigned Reg = GetOpReg(Op);
  114. if (Reg > 0 && !DefinedRegs.test(Reg)) {
  115. RIV.push_back(RegisterValue::zero(Reg));
  116. DefinedRegs.set(Reg);
  117. }
  118. }
  119. }
  120. // Mark defs as having been def'ed.
  121. for (const Operand &Op : IT.getInstr().Operands) {
  122. if (Op.isDef()) {
  123. const unsigned Reg = GetOpReg(Op);
  124. if (Reg > 0)
  125. DefinedRegs.set(Reg);
  126. }
  127. }
  128. }
  129. return RIV;
  130. }
  131. Expected<std::vector<CodeTemplate>>
  132. generateSelfAliasingCodeTemplates(InstructionTemplate Variant,
  133. const BitVector &ForbiddenRegisters) {
  134. const AliasingConfigurations SelfAliasing(
  135. Variant.getInstr(), Variant.getInstr(), ForbiddenRegisters);
  136. if (SelfAliasing.empty())
  137. return make_error<SnippetGeneratorFailure>("empty self aliasing");
  138. std::vector<CodeTemplate> Result;
  139. Result.emplace_back();
  140. CodeTemplate &CT = Result.back();
  141. if (SelfAliasing.hasImplicitAliasing()) {
  142. CT.Info = "implicit Self cycles, picking random values.";
  143. } else {
  144. CT.Info = "explicit self cycles, selecting one aliasing Conf.";
  145. // This is a self aliasing instruction so defs and uses are from the same
  146. // instance, hence twice Variant in the following call.
  147. setRandomAliasing(SelfAliasing, Variant, Variant);
  148. }
  149. CT.Instructions.push_back(std::move(Variant));
  150. return std::move(Result);
  151. }
  152. Expected<std::vector<CodeTemplate>>
  153. generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant,
  154. StringRef Msg) {
  155. std::vector<CodeTemplate> Result;
  156. Result.emplace_back();
  157. CodeTemplate &CT = Result.back();
  158. CT.Info =
  159. std::string(formatv("{0}, repeating an unconstrained assignment", Msg));
  160. CT.Instructions.push_back(std::move(Variant));
  161. return std::move(Result);
  162. }
  163. std::mt19937 &randomGenerator() {
  164. static std::random_device RandomDevice;
  165. static std::mt19937 RandomGenerator(RandomDevice());
  166. return RandomGenerator;
  167. }
  168. size_t randomIndex(size_t Max) {
  169. std::uniform_int_distribution<> Distribution(0, Max);
  170. return Distribution(randomGenerator());
  171. }
  172. template <typename C> static decltype(auto) randomElement(const C &Container) {
  173. assert(!Container.empty() &&
  174. "Can't pick a random element from an empty container)");
  175. return Container[randomIndex(Container.size() - 1)];
  176. }
  177. static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
  178. InstructionTemplate &IB) {
  179. assert(ROV.Op);
  180. if (ROV.Op->isExplicit()) {
  181. auto &AssignedValue = IB.getValueFor(*ROV.Op);
  182. if (AssignedValue.isValid()) {
  183. assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
  184. return;
  185. }
  186. AssignedValue = MCOperand::createReg(ROV.Reg);
  187. } else {
  188. assert(ROV.Op->isImplicitReg());
  189. assert(ROV.Reg == ROV.Op->getImplicitReg());
  190. }
  191. }
  192. size_t randomBit(const BitVector &Vector) {
  193. assert(Vector.any());
  194. auto Itr = Vector.set_bits_begin();
  195. for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
  196. ++Itr;
  197. return *Itr;
  198. }
  199. std::optional<int> getFirstCommonBit(const BitVector &A, const BitVector &B) {
  200. BitVector Intersect = A;
  201. Intersect &= B;
  202. int idx = Intersect.find_first();
  203. if (idx != -1)
  204. return idx;
  205. return {};
  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. static Error randomizeMCOperand(const LLVMState &State,
  216. const Instruction &Instr, const Variable &Var,
  217. MCOperand &AssignedValue,
  218. const BitVector &ForbiddenRegs) {
  219. const Operand &Op = Instr.getPrimaryOperand(Var);
  220. if (Op.getExplicitOperandInfo().OperandType >=
  221. MCOI::OperandType::OPERAND_FIRST_TARGET)
  222. return State.getExegesisTarget().randomizeTargetMCOperand(
  223. Instr, Var, AssignedValue, ForbiddenRegs);
  224. switch (Op.getExplicitOperandInfo().OperandType) {
  225. case MCOI::OperandType::OPERAND_IMMEDIATE:
  226. // FIXME: explore immediate values too.
  227. AssignedValue = MCOperand::createImm(1);
  228. break;
  229. case MCOI::OperandType::OPERAND_REGISTER: {
  230. assert(Op.isReg());
  231. auto AllowedRegs = Op.getRegisterAliasing().sourceBits();
  232. assert(AllowedRegs.size() == ForbiddenRegs.size());
  233. for (auto I : ForbiddenRegs.set_bits())
  234. AllowedRegs.reset(I);
  235. if (!AllowedRegs.any())
  236. return make_error<Failure>(
  237. Twine("no available registers:\ncandidates:\n")
  238. .concat(debugString(State.getRegInfo(),
  239. Op.getRegisterAliasing().sourceBits()))
  240. .concat("\nforbidden:\n")
  241. .concat(debugString(State.getRegInfo(), ForbiddenRegs)));
  242. AssignedValue = MCOperand::createReg(randomBit(AllowedRegs));
  243. break;
  244. }
  245. default:
  246. break;
  247. }
  248. return Error::success();
  249. }
  250. Error randomizeUnsetVariables(const LLVMState &State,
  251. const BitVector &ForbiddenRegs,
  252. InstructionTemplate &IT) {
  253. for (const Variable &Var : IT.getInstr().Variables) {
  254. MCOperand &AssignedValue = IT.getValueFor(Var);
  255. if (!AssignedValue.isValid())
  256. if (auto Err = randomizeMCOperand(State, IT.getInstr(), Var,
  257. AssignedValue, ForbiddenRegs))
  258. return Err;
  259. }
  260. return Error::success();
  261. }
  262. } // namespace exegesis
  263. } // namespace llvm