ff1b01bb78
Some of this was needed to fix implicit conversions from MCRegister to unsigned when calling getReg() on MCOperand for example. The majority was done by reviewing parts of the code that dealt with registers, converting them to MCRegister and then seeing what new implicit conversions were created and fixing those. There were a few places where I used MCPhysReg instead of MCRegiser for static arrays since its uint16_t instead of unsigned.
316 lines
12 KiB
C++
316 lines
12 KiB
C++
//===-- SnippetGenerator.cpp ------------------------------------*- C++ -*-===//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include <string>
|
|
|
|
#include "Assembler.h"
|
|
#include "Error.h"
|
|
#include "MCInstrDescView.h"
|
|
#include "SnippetGenerator.h"
|
|
#include "Target.h"
|
|
#include "llvm/ADT/StringExtras.h"
|
|
#include "llvm/ADT/StringRef.h"
|
|
#include "llvm/ADT/Twine.h"
|
|
#include "llvm/Support/Error.h"
|
|
#include "llvm/Support/FileSystem.h"
|
|
#include "llvm/Support/FormatVariadic.h"
|
|
#include "llvm/Support/Program.h"
|
|
|
|
namespace llvm {
|
|
namespace exegesis {
|
|
|
|
std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {
|
|
std::vector<CodeTemplate> Result;
|
|
Result.push_back(std::move(CT));
|
|
return Result;
|
|
}
|
|
|
|
SnippetGeneratorFailure::SnippetGeneratorFailure(const Twine &S)
|
|
: StringError(S, inconvertibleErrorCode()) {}
|
|
|
|
SnippetGenerator::SnippetGenerator(const LLVMState &State, const Options &Opts)
|
|
: State(State), Opts(Opts) {}
|
|
|
|
SnippetGenerator::~SnippetGenerator() = default;
|
|
|
|
Error SnippetGenerator::generateConfigurations(
|
|
const InstructionTemplate &Variant, std::vector<BenchmarkCode> &Benchmarks,
|
|
const BitVector &ExtraForbiddenRegs) const {
|
|
BitVector ForbiddenRegs = State.getRATC().reservedRegisters();
|
|
ForbiddenRegs |= ExtraForbiddenRegs;
|
|
// If the instruction has memory registers, prevent the generator from
|
|
// using the scratch register and its aliasing registers.
|
|
if (Variant.getInstr().hasMemoryOperands()) {
|
|
const auto &ET = State.getExegesisTarget();
|
|
MCRegister ScratchSpacePointerInReg =
|
|
ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
|
|
if (!ScratchSpacePointerInReg.isValid())
|
|
return make_error<Failure>(
|
|
"Infeasible : target does not support memory instructions");
|
|
const auto &ScratchRegAliases =
|
|
State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits();
|
|
// If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
|
|
// FIXME: We could make a copy of the scratch register.
|
|
for (const auto &Op : Variant.getInstr().Operands) {
|
|
if (Op.isDef() && Op.isImplicitReg() &&
|
|
ScratchRegAliases.test(Op.getImplicitReg().id()))
|
|
return make_error<Failure>(
|
|
"Infeasible : memory instruction uses scratch memory register");
|
|
}
|
|
ForbiddenRegs |= ScratchRegAliases;
|
|
}
|
|
|
|
if (auto E = generateCodeTemplates(Variant, ForbiddenRegs)) {
|
|
MutableArrayRef<CodeTemplate> Templates = E.get();
|
|
|
|
// Avoid reallocations in the loop.
|
|
Benchmarks.reserve(Benchmarks.size() + Templates.size());
|
|
for (CodeTemplate &CT : Templates) {
|
|
// TODO: Generate as many BenchmarkCode as needed.
|
|
{
|
|
CT.ScratchSpacePointerInReg =
|
|
State.getExegesisTarget().getScratchMemoryRegister(
|
|
State.getTargetMachine().getTargetTriple());
|
|
BenchmarkCode BC;
|
|
BC.Info = CT.Info;
|
|
BC.Key.Instructions.reserve(CT.Instructions.size());
|
|
for (InstructionTemplate &IT : CT.Instructions) {
|
|
if (auto Error = randomizeUnsetVariables(State, ForbiddenRegs, IT))
|
|
return Error;
|
|
MCInst Inst = IT.build();
|
|
if (auto Error = validateGeneratedInstruction(State, Inst))
|
|
return Error;
|
|
BC.Key.Instructions.push_back(Inst);
|
|
}
|
|
if (CT.ScratchSpacePointerInReg)
|
|
BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
|
|
BC.Key.RegisterInitialValues =
|
|
computeRegisterInitialValues(CT.Instructions);
|
|
BC.Key.Config = CT.Config;
|
|
Benchmarks.emplace_back(std::move(BC));
|
|
if (Benchmarks.size() >= Opts.MaxConfigsPerOpcode) {
|
|
// We reached the number of allowed configs and return early.
|
|
return Error::success();
|
|
}
|
|
}
|
|
}
|
|
return Error::success();
|
|
} else
|
|
return E.takeError();
|
|
}
|
|
|
|
std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
|
|
const std::vector<InstructionTemplate> &Instructions) const {
|
|
// Collect all register uses and create an assignment for each of them.
|
|
// Ignore memory operands which are handled separately.
|
|
// Loop invariant: DefinedRegs[i] is true iif it has been set at least once
|
|
// before the current instruction.
|
|
BitVector DefinedRegs = State.getRATC().emptyRegisters();
|
|
// If target always expects a scratch memory register as live input,
|
|
// mark it as defined.
|
|
const ExegesisTarget &Target = State.getExegesisTarget();
|
|
MCRegister ScratchMemoryReg = Target.getScratchMemoryRegister(
|
|
State.getTargetMachine().getTargetTriple());
|
|
DefinedRegs.set(ScratchMemoryReg.id());
|
|
std::vector<RegisterValue> RIV;
|
|
for (const InstructionTemplate &IT : Instructions) {
|
|
// Returns the register that this Operand sets or uses, or 0 if this is not
|
|
// a register.
|
|
const auto GetOpReg = [&IT](const Operand &Op) -> MCRegister {
|
|
if (Op.isMemory())
|
|
return MCRegister();
|
|
if (Op.isImplicitReg())
|
|
return Op.getImplicitReg();
|
|
if (Op.isExplicit() && IT.getValueFor(Op).isReg())
|
|
return IT.getValueFor(Op).getReg();
|
|
return MCRegister();
|
|
};
|
|
// Collect used registers that have never been def'ed.
|
|
for (const Operand &Op : IT.getInstr().Operands) {
|
|
if (Op.isUse()) {
|
|
const MCRegister Reg = GetOpReg(Op);
|
|
if (Reg && !DefinedRegs.test(Reg.id())) {
|
|
RIV.push_back(RegisterValue::zero(Reg));
|
|
DefinedRegs.set(Reg.id());
|
|
}
|
|
}
|
|
}
|
|
// Mark defs as having been def'ed.
|
|
for (const Operand &Op : IT.getInstr().Operands) {
|
|
if (Op.isDef()) {
|
|
const MCRegister Reg = GetOpReg(Op);
|
|
if (Reg)
|
|
DefinedRegs.set(Reg.id());
|
|
}
|
|
}
|
|
}
|
|
return RIV;
|
|
}
|
|
|
|
Expected<std::vector<CodeTemplate>>
|
|
generateSelfAliasingCodeTemplates(InstructionTemplate Variant,
|
|
const BitVector &ForbiddenRegisters) {
|
|
const AliasingConfigurations SelfAliasing(
|
|
Variant.getInstr(), Variant.getInstr(), ForbiddenRegisters);
|
|
if (SelfAliasing.empty())
|
|
return make_error<SnippetGeneratorFailure>("empty self aliasing");
|
|
std::vector<CodeTemplate> Result;
|
|
Result.emplace_back();
|
|
CodeTemplate &CT = Result.back();
|
|
if (SelfAliasing.hasImplicitAliasing()) {
|
|
CT.Info = "implicit Self cycles, picking random values.";
|
|
} else {
|
|
CT.Info = "explicit self cycles, selecting one aliasing Conf.";
|
|
// This is a self aliasing instruction so defs and uses are from the same
|
|
// instance, hence twice Variant in the following call.
|
|
setRandomAliasing(SelfAliasing, Variant, Variant);
|
|
}
|
|
CT.Instructions.push_back(std::move(Variant));
|
|
return std::move(Result);
|
|
}
|
|
|
|
Expected<std::vector<CodeTemplate>>
|
|
generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant,
|
|
StringRef Msg) {
|
|
std::vector<CodeTemplate> Result;
|
|
Result.emplace_back();
|
|
CodeTemplate &CT = Result.back();
|
|
CT.Info =
|
|
std::string(formatv("{0}, repeating an unconstrained assignment", Msg));
|
|
CT.Instructions.push_back(std::move(Variant));
|
|
return std::move(Result);
|
|
}
|
|
|
|
std::mt19937 &randomGenerator() {
|
|
static std::random_device RandomDevice;
|
|
static std::mt19937 RandomGenerator(RandomDevice());
|
|
return RandomGenerator;
|
|
}
|
|
|
|
size_t randomIndex(size_t Max) {
|
|
std::uniform_int_distribution<> Distribution(0, Max);
|
|
return Distribution(randomGenerator());
|
|
}
|
|
|
|
template <typename C> static decltype(auto) randomElement(const C &Container) {
|
|
assert(!Container.empty() &&
|
|
"Can't pick a random element from an empty container)");
|
|
return Container[randomIndex(Container.size() - 1)];
|
|
}
|
|
|
|
static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
|
|
InstructionTemplate &IB) {
|
|
assert(ROV.Op);
|
|
if (ROV.Op->isExplicit()) {
|
|
auto &AssignedValue = IB.getValueFor(*ROV.Op);
|
|
if (AssignedValue.isValid()) {
|
|
// TODO don't re-assign register operands which are already "locked"
|
|
// by Target in corresponding InstructionTemplate
|
|
return;
|
|
}
|
|
AssignedValue = MCOperand::createReg(ROV.Reg);
|
|
} else {
|
|
assert(ROV.Op->isImplicitReg());
|
|
assert(ROV.Reg == ROV.Op->getImplicitReg());
|
|
}
|
|
}
|
|
|
|
size_t randomBit(const BitVector &Vector) {
|
|
assert(Vector.any());
|
|
auto Itr = Vector.set_bits_begin();
|
|
for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
|
|
++Itr;
|
|
return *Itr;
|
|
}
|
|
|
|
std::optional<int> getFirstCommonBit(const BitVector &A, const BitVector &B) {
|
|
BitVector Intersect = A;
|
|
Intersect &= B;
|
|
int idx = Intersect.find_first();
|
|
if (idx != -1)
|
|
return idx;
|
|
return {};
|
|
}
|
|
|
|
void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
|
|
InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
|
|
assert(!AliasingConfigurations.empty());
|
|
assert(!AliasingConfigurations.hasImplicitAliasing());
|
|
const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
|
|
setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
|
|
setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
|
|
}
|
|
|
|
static Error randomizeMCOperand(const LLVMState &State,
|
|
const Instruction &Instr, const Variable &Var,
|
|
MCOperand &AssignedValue,
|
|
const BitVector &ForbiddenRegs) {
|
|
const Operand &Op = Instr.getPrimaryOperand(Var);
|
|
if (Op.getExplicitOperandInfo().OperandType >=
|
|
MCOI::OperandType::OPERAND_FIRST_TARGET)
|
|
return State.getExegesisTarget().randomizeTargetMCOperand(
|
|
Instr, Var, AssignedValue, ForbiddenRegs);
|
|
switch (Op.getExplicitOperandInfo().OperandType) {
|
|
case MCOI::OperandType::OPERAND_IMMEDIATE:
|
|
// FIXME: explore immediate values too.
|
|
AssignedValue = MCOperand::createImm(1);
|
|
break;
|
|
case MCOI::OperandType::OPERAND_REGISTER: {
|
|
assert(Op.isReg());
|
|
auto AllowedRegs = Op.getRegisterAliasing().sourceBits();
|
|
assert(AllowedRegs.size() == ForbiddenRegs.size());
|
|
for (auto I : ForbiddenRegs.set_bits())
|
|
AllowedRegs.reset(I);
|
|
if (!AllowedRegs.any())
|
|
return make_error<Failure>(
|
|
Twine("no available registers:\ncandidates:\n")
|
|
.concat(debugString(State.getRegInfo(),
|
|
Op.getRegisterAliasing().sourceBits()))
|
|
.concat("\nforbidden:\n")
|
|
.concat(debugString(State.getRegInfo(), ForbiddenRegs)));
|
|
AssignedValue = MCOperand::createReg(randomBit(AllowedRegs));
|
|
break;
|
|
}
|
|
default:
|
|
break;
|
|
}
|
|
return Error::success();
|
|
}
|
|
|
|
Error randomizeUnsetVariables(const LLVMState &State,
|
|
const BitVector &ForbiddenRegs,
|
|
InstructionTemplate &IT) {
|
|
for (const Variable &Var : IT.getInstr().Variables) {
|
|
MCOperand &AssignedValue = IT.getValueFor(Var);
|
|
if (!AssignedValue.isValid())
|
|
if (auto Err = randomizeMCOperand(State, IT.getInstr(), Var,
|
|
AssignedValue, ForbiddenRegs))
|
|
return Err;
|
|
}
|
|
return Error::success();
|
|
}
|
|
|
|
Error validateGeneratedInstruction(const LLVMState &State, const MCInst &Inst) {
|
|
for (const auto &Operand : Inst) {
|
|
if (!Operand.isValid()) {
|
|
// Mention the particular opcode - it is not necessarily the "main"
|
|
// opcode being benchmarked by this snippet. For example, serial snippet
|
|
// generator uses one more opcode when in SERIAL_VIA_NON_MEMORY_INSTR
|
|
// execution mode.
|
|
const auto OpcodeName = State.getInstrInfo().getName(Inst.getOpcode());
|
|
return make_error<Failure>("Not all operands were initialized by the "
|
|
"snippet generator for " +
|
|
OpcodeName + " opcode.");
|
|
}
|
|
}
|
|
return Error::success();
|
|
}
|
|
|
|
} // namespace exegesis
|
|
} // namespace llvm
|