reland r332579: [llvm-exegesis] Update to cover latency through another opcode.

Restructuring the code to measure latency and uops.
The end goal is to have this program spawn another process to deal with SIGILL and other malformed programs. It is not yet the case in this redesign, it is still the main program that runs the code (and may crash).
It now uses BitVector instead of Graph for performance reasons.

https://reviews.llvm.org/D46821

(with fixed ARM tests)

Authored by Guillaume Chatelet

llvm-svn: 332592

1 files changed, 268 insertions, 0 deletions

diff --git a/llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp b/llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp
new file mode 100644
index 0000000..268136e
--- /dev/null
+++ b/llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp
@@ -0,0 +1,268 @@
+//===-- 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 {
+
+static void tie(const Operand *FromOperand, llvm::Optional<Variable> &Var) {
+  if (!Var)
+    Var.emplace();
+  Var->TiedOperands.push_back(FromOperand);
+}
+
+Instruction::Instruction(const llvm::MCInstrDesc &MCInstrDesc,
+                         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.IsExplicit = true;
+    // TODO(gchatelet): Handle isLookupPtrRegClass.
+    if (OpInfo.RegClass >= 0)
+      Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass);
+    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);
+  }
+  // Set TiedTo for operands.
+  for (auto &Op : Operands) {
+    if (Op.IsExplicit) {
+      const int TiedTo =
+          MCInstrDesc.getOperandConstraint(Op.Index, llvm::MCOI::TIED_TO);
+      if (TiedTo >= 0) {
+        Op.TiedTo = &Operands[TiedTo];
+        tie(&Op, Operands[TiedTo].Var);
+      } else {
+        tie(&Op, Op.Var);
+      }
+    }
+  }
+  for (auto &Op : Operands) {
+    if (Op.Var) {
+      Variables.push_back(&*Op.Var);
+    }
+  }
+  // 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 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(Variable &Var) {
+  assert(!Var.TiedOperands.empty());
+  assert(Var.TiedOperands.front() != nullptr);
+  const Operand &Op = *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.
+    Var.AssignedValue = llvm::MCOperand::createImm(1);
+    break;
+  case llvm::MCOI::OperandType::OPERAND_REGISTER: {
+    assert(Op.Tracker);
+    const auto &Registers = Op.Tracker->sourceBits();
+    Var.AssignedValue = llvm::MCOperand::createReg(randomBit(Registers));
+    break;
+  }
+  default:
+    break;
+  }
+}
+
+static void setRegisterOperandValue(const RegisterOperandAssignment &ROV) {
+  const Operand *Op = ROV.Op->TiedTo ? ROV.Op->TiedTo : ROV.Op;
+  assert(Op->Var);
+  auto &AssignedValue = Op->Var->AssignedValue;
+  if (AssignedValue.isValid()) {
+    assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
+    return;
+  }
+  Op->Var->AssignedValue = llvm::MCOperand::createReg(ROV.Reg);
+}
+
+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) {
+  assert(!AliasingConfigurations.empty());
+  assert(!AliasingConfigurations.hasImplicitAliasing());
+  const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
+  setRegisterOperandValue(randomElement(RandomConf.Defs));
+  setRegisterOperandValue(randomElement(RandomConf.Uses));
+}
+
+void randomizeUnsetVariable(const Instruction &Instruction) {
+  for (auto *Var : Instruction.Variables)
+    if (!Var->AssignedValue.isValid())
+      randomize(*Var);
+}
+
+void clearVariableAssignments(const Instruction &Instruction) {
+  for (auto *Var : Instruction.Variables)
+    Var->AssignedValue = llvm::MCOperand();
+}
+
+llvm::MCInst build(const Instruction &Instruction) {
+  llvm::MCInst Result;
+  Result.setOpcode(Instruction.Description.Opcode);
+  for (const auto &Op : Instruction.Operands) {
+    if (Op.IsExplicit) {
+      auto &Var = Op.TiedTo ? Op.TiedTo->Var : Op.Var;
+      assert(Var);
+      Result.addOperand(Var->AssignedValue);
+    }
+  }
+  return Result;
+}
+
+llvm::MCInst randomizeUnsetVariablesAndBuild(const Instruction &Instruction) {
+  randomizeUnsetVariable(Instruction);
+  return build(Instruction);
+}
+
+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