llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp

//===-- MCInstrDescView.cpp -------------------------------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "MCInstrDescView.h"

#include <iterator>
#include <map>
#include <tuple>

#include "llvm/ADT/STLExtras.h"

namespace exegesis {

Instruction::Instruction(const llvm::MCInstrDesc &MCInstrDesc,
                         const RegisterAliasingTrackerCache &RATC)
    : Description(&MCInstrDesc) {
  unsigned OpIndex = 0;
  for (; OpIndex < MCInstrDesc.getNumOperands(); ++OpIndex) {
    const auto &OpInfo = MCInstrDesc.opInfo_begin()[OpIndex];
    Operand Operand;
    Operand.Index = OpIndex;
    Operand.IsDef = (OpIndex < MCInstrDesc.getNumDefs());
    Operand.IsMem = OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY;
    Operand.IsExplicit = true;
    // TODO(gchatelet): Handle isLookupPtrRegClass.
    if (OpInfo.RegClass >= 0)
      Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass);
    Operand.TiedToIndex =
        MCInstrDesc.getOperandConstraint(OpIndex, llvm::MCOI::TIED_TO);
    Operand.Info = &OpInfo;
    Operands.push_back(Operand);
  }
  for (const llvm::MCPhysReg *MCPhysReg = MCInstrDesc.getImplicitDefs();
       MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
    Operand Operand;
    Operand.Index = OpIndex;
    Operand.IsDef = true;
    Operand.IsExplicit = false;
    Operand.Tracker = &RATC.getRegister(*MCPhysReg);
    Operand.ImplicitReg = MCPhysReg;
    Operands.push_back(Operand);
  }
  for (const llvm::MCPhysReg *MCPhysReg = MCInstrDesc.getImplicitUses();
       MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
    Operand Operand;
    Operand.Index = OpIndex;
    Operand.IsDef = false;
    Operand.IsExplicit = false;
    Operand.Tracker = &RATC.getRegister(*MCPhysReg);
    Operand.ImplicitReg = MCPhysReg;
    Operands.push_back(Operand);
  }
  // Assigning Variables to non tied explicit operands.
  Variables.reserve(Operands.size()); // Variables.size() <= Operands.size()
  for (auto &Op : Operands)
    if (Op.IsExplicit && Op.TiedToIndex < 0) {
      const size_t VariableIndex = Variables.size();
      Op.VariableIndex = VariableIndex;
      Variables.emplace_back();
      Variables.back().Index = VariableIndex;
    }
  // Assigning Variables to tied operands.
  for (auto &Op : Operands)
    if (Op.TiedToIndex >= 0)
      Op.VariableIndex = Operands[Op.TiedToIndex].VariableIndex;
  // Assigning Operands to Variables.
  for (auto &Op : Operands)
    if (Op.VariableIndex >= 0)
      Variables[Op.VariableIndex].TiedOperands.push_back(Op.Index);
  // Processing Aliasing.
  DefRegisters = RATC.emptyRegisters();
  UseRegisters = RATC.emptyRegisters();
  for (const auto &Op : Operands) {
    if (Op.Tracker) {
      auto &Registers = Op.IsDef ? DefRegisters : UseRegisters;
      Registers |= Op.Tracker->aliasedBits();
    }
  }
}

bool Instruction::hasMemoryOperands() const {
  return std::any_of(Operands.begin(), Operands.end(),
                     [](const Operand &Op) { return Op.IsMem; });
}

InstructionInstance::InstructionInstance(const Instruction &Instr)
    : Instr(Instr), VariableValues(Instr.Variables.size()) {}

InstructionInstance::InstructionInstance(InstructionInstance &&) = default;

InstructionInstance &InstructionInstance::
operator=(InstructionInstance &&) = default;

InstructionInstance::InstructionInstance(const InstructionInstance &) = default;

InstructionInstance &InstructionInstance::
operator=(const InstructionInstance &) = default;

unsigned InstructionInstance::getOpcode() const {
  return Instr.Description->getOpcode();
}

llvm::MCOperand &InstructionInstance::getValueFor(const Variable &Var) {
  return VariableValues[Var.Index];
}

const llvm::MCOperand &
InstructionInstance::getValueFor(const Variable &Var) const {
  return VariableValues[Var.Index];
}

llvm::MCOperand &InstructionInstance::getValueFor(const Operand &Op) {
  assert(Op.VariableIndex >= 0);
  return getValueFor(Instr.Variables[Op.VariableIndex]);
}

const llvm::MCOperand &
InstructionInstance::getValueFor(const Operand &Op) const {
  assert(Op.VariableIndex >= 0);
  return getValueFor(Instr.Variables[Op.VariableIndex]);
}

// forward declaration.
static void randomize(const Instruction &Instr, const Variable &Var,
                      llvm::MCOperand &AssignedValue,
                      const llvm::BitVector &ForbiddenRegs);

bool InstructionInstance::hasImmediateVariables() const {
  return llvm::any_of(Instr.Variables, [this](const Variable &Var) {
    assert(!Var.TiedOperands.empty());
    const unsigned OpIndex = Var.TiedOperands[0];
    const Operand &Op = Instr.Operands[OpIndex];
    assert(Op.Info);
    return Op.Info->OperandType == llvm::MCOI::OPERAND_IMMEDIATE;
  });
}

void InstructionInstance::randomizeUnsetVariables(
    const llvm::BitVector &ForbiddenRegs) {
  for (const Variable &Var : Instr.Variables) {
    llvm::MCOperand &AssignedValue = getValueFor(Var);
    if (!AssignedValue.isValid())
      randomize(Instr, Var, AssignedValue, ForbiddenRegs);
  }
}

llvm::MCInst InstructionInstance::build() const {
  llvm::MCInst Result;
  Result.setOpcode(Instr.Description->Opcode);
  for (const auto &Op : Instr.Operands)
    if (Op.IsExplicit)
      Result.addOperand(getValueFor(Op));
  return Result;
}

SnippetPrototype::SnippetPrototype(SnippetPrototype &&) = default;

SnippetPrototype &SnippetPrototype::operator=(SnippetPrototype &&) = default;

bool RegisterOperandAssignment::
operator==(const RegisterOperandAssignment &Other) const {
  return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg);
}

bool AliasingRegisterOperands::
operator==(const AliasingRegisterOperands &Other) const {
  return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses);
}

static void addOperandIfAlias(
    const llvm::MCPhysReg Reg, bool SelectDef, llvm::ArrayRef<Operand> Operands,
    llvm::SmallVectorImpl<RegisterOperandAssignment> &OperandValues) {
  for (const auto &Op : Operands) {
    if (Op.Tracker && Op.IsDef == SelectDef) {
      const int SourceReg = Op.Tracker->getOrigin(Reg);
      if (SourceReg >= 0)
        OperandValues.emplace_back(&Op, SourceReg);
    }
  }
}

bool AliasingRegisterOperands::hasImplicitAliasing() const {
  const auto HasImplicit = [](const RegisterOperandAssignment &ROV) {
    return !ROV.Op->IsExplicit;
  };
  return llvm::any_of(Defs, HasImplicit) && llvm::any_of(Uses, HasImplicit);
}

bool AliasingConfigurations::empty() const { return Configurations.empty(); }

bool AliasingConfigurations::hasImplicitAliasing() const {
  return llvm::any_of(Configurations, [](const AliasingRegisterOperands &ARO) {
    return ARO.hasImplicitAliasing();
  });
}

AliasingConfigurations::AliasingConfigurations(
    const Instruction &DefInstruction, const Instruction &UseInstruction)
    : DefInstruction(DefInstruction), UseInstruction(UseInstruction) {
  if (UseInstruction.UseRegisters.anyCommon(DefInstruction.DefRegisters)) {
    auto CommonRegisters = UseInstruction.UseRegisters;
    CommonRegisters &= DefInstruction.DefRegisters;
    for (const llvm::MCPhysReg Reg : CommonRegisters.set_bits()) {
      AliasingRegisterOperands ARO;
      addOperandIfAlias(Reg, true, DefInstruction.Operands, ARO.Defs);
      addOperandIfAlias(Reg, false, UseInstruction.Operands, ARO.Uses);
      if (!ARO.Defs.empty() && !ARO.Uses.empty() &&
          !llvm::is_contained(Configurations, ARO))
        Configurations.push_back(std::move(ARO));
    }
  }
}

std::mt19937 &randomGenerator() {
  static std::random_device RandomDevice;
  static std::mt19937 RandomGenerator(RandomDevice());
  return RandomGenerator;
}

static size_t randomIndex(size_t Size) {
  assert(Size > 0);
  std::uniform_int_distribution<> Distribution(0, Size - 1);
  return Distribution(randomGenerator());
}

template <typename C>
static auto randomElement(const C &Container) -> decltype(Container[0]) {
  return Container[randomIndex(Container.size())];
}

static void randomize(const Instruction &Instr, const Variable &Var,
                      llvm::MCOperand &AssignedValue,
                      const llvm::BitVector &ForbiddenRegs) {
  assert(!Var.TiedOperands.empty());
  const Operand &Op = Instr.Operands[Var.TiedOperands.front()];
  assert(Op.Info != nullptr);
  const auto &OpInfo = *Op.Info;
  switch (OpInfo.OperandType) {
  case llvm::MCOI::OperandType::OPERAND_IMMEDIATE:
    // FIXME: explore immediate values too.
    AssignedValue = llvm::MCOperand::createImm(1);
    break;
  case llvm::MCOI::OperandType::OPERAND_REGISTER: {
    assert(Op.Tracker);
    auto AllowedRegs = Op.Tracker->sourceBits();
    assert(AllowedRegs.size() == ForbiddenRegs.size());
    for (auto I : ForbiddenRegs.set_bits())
      AllowedRegs.reset(I);
    AssignedValue = llvm::MCOperand::createReg(randomBit(AllowedRegs));
    break;
  }
  default:
    break;
  }
}

static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
                                    InstructionInstance &II) {
  assert(ROV.Op);
  if (ROV.Op->IsExplicit) {
    auto &AssignedValue = II.getValueFor(*ROV.Op);
    if (AssignedValue.isValid()) {
      assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
      return;
    }
    AssignedValue = llvm::MCOperand::createReg(ROV.Reg);
  } else {
    assert(ROV.Op->ImplicitReg != nullptr);
    assert(ROV.Reg == *ROV.Op->ImplicitReg);
  }
}

size_t randomBit(const llvm::BitVector &Vector) {
  assert(Vector.any());
  auto Itr = Vector.set_bits_begin();
  for (size_t I = randomIndex(Vector.count()); I != 0; --I)
    ++Itr;
  return *Itr;
}

void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
                       InstructionInstance &DefII, InstructionInstance &UseII) {
  assert(!AliasingConfigurations.empty());
  assert(!AliasingConfigurations.hasImplicitAliasing());
  const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
  setRegisterOperandValue(randomElement(RandomConf.Defs), DefII);
  setRegisterOperandValue(randomElement(RandomConf.Uses), UseII);
}

void DumpMCOperand(const llvm::MCRegisterInfo &MCRegisterInfo,
                   const llvm::MCOperand &Op, llvm::raw_ostream &OS) {
  if (!Op.isValid())
    OS << "Invalid";
  else if (Op.isReg())
    OS << MCRegisterInfo.getName(Op.getReg());
  else if (Op.isImm())
    OS << Op.getImm();
  else if (Op.isFPImm())
    OS << Op.getFPImm();
  else if (Op.isExpr())
    OS << "Expr";
  else if (Op.isInst())
    OS << "SubInst";
}

void DumpMCInst(const llvm::MCRegisterInfo &MCRegisterInfo,
                const llvm::MCInstrInfo &MCInstrInfo,
                const llvm::MCInst &MCInst, llvm::raw_ostream &OS) {
  OS << MCInstrInfo.getName(MCInst.getOpcode());
  for (unsigned I = 0, E = MCInst.getNumOperands(); I < E; ++I) {
    if (I > 0)
      OS << ',';
    OS << ' ';
    DumpMCOperand(MCRegisterInfo, MCInst.getOperand(I), OS);
  }
}

} // namespace exegesis