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

   1 //===-- MCInstrDescView.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
   9 #include "MCInstrDescView.h"
  10
  11 #include <iterator>
  12 #include <tuple>
  13
  14 #include "llvm/ADT/STLExtras.h"
  15
  16 namespace llvm {
  17 namespace exegesis {
  18
  19 unsigned Variable::getIndex() const { return *Index; }
  20
  21 unsigned Variable::getPrimaryOperandIndex() const {
  22   assert(!TiedOperands.empty());
  23   return TiedOperands[0];
  24 }
  25
  26 bool Variable::hasTiedOperands() const {
  27   assert(TiedOperands.size() <= 2 &&
  28          "No more than two operands can be tied together");
  29   // By definition only Use and Def operands can be tied together.
  30   // TiedOperands[0] is the Def operand (LLVM stores defs first).
  31   // TiedOperands[1] is the Use operand.
  32   return TiedOperands.size() > 1;
  33 }
  34
  35 unsigned Operand::getIndex() const { return *Index; }
  36
  37 bool Operand::isExplicit() const { return Info; }
  38
  39 bool Operand::isImplicit() const { return !Info; }
  40
  41 bool Operand::isImplicitReg() const { return ImplicitReg; }
  42
  43 bool Operand::isDef() const { return IsDef; }
  44
  45 bool Operand::isUse() const { return !IsDef; }
  46
  47 bool Operand::isReg() const { return Tracker; }
  48
  49 bool Operand::isTied() const { return TiedToIndex.has_value(); }
  50
  51 bool Operand::isVariable() const { return VariableIndex.has_value(); }
  52
  53 bool Operand::isMemory() const {
  54   return isExplicit() &&
  55          getExplicitOperandInfo().OperandType == MCOI::OPERAND_MEMORY;
  56 }
  57
  58 bool Operand::isImmediate() const {
  59   return isExplicit() &&
  60          getExplicitOperandInfo().OperandType == MCOI::OPERAND_IMMEDIATE;
  61 }
  62
  63 unsigned Operand::getTiedToIndex() const { return *TiedToIndex; }
  64
  65 unsigned Operand::getVariableIndex() const { return *VariableIndex; }
  66
  67 unsigned Operand::getImplicitReg() const {
  68   assert(ImplicitReg);
  69   return ImplicitReg;
  70 }
  71
  72 const RegisterAliasingTracker &Operand::getRegisterAliasing() const {
  73   assert(Tracker);
  74   return *Tracker;
  75 }
  76
  77 const MCOperandInfo &Operand::getExplicitOperandInfo() const {
  78   assert(Info);
  79   return *Info;
  80 }
  81
  82 const BitVector *BitVectorCache::getUnique(BitVector &&BV) const {
  83   for (const auto &Entry : Cache)
  84     if (*Entry == BV)
  85       return Entry.get();
  86   Cache.push_back(std::make_unique<BitVector>());
  87   auto &Entry = Cache.back();
  88   Entry->swap(BV);
  89   return Entry.get();
  90 }
  91
  92 Instruction::Instruction(const MCInstrDesc *Description, StringRef Name,
  93                          SmallVector<Operand, 8> Operands,
  94                          SmallVector<Variable, 4> Variables,
  95                          const BitVector *ImplDefRegs,
  96                          const BitVector *ImplUseRegs,
  97                          const BitVector *AllDefRegs,
  98                          const BitVector *AllUseRegs)
  99     : Description(*Description), Name(Name), Operands(std::move(Operands)),
 100       Variables(std::move(Variables)), ImplDefRegs(*ImplDefRegs),
 101       ImplUseRegs(*ImplUseRegs), AllDefRegs(*AllDefRegs),
 102       AllUseRegs(*AllUseRegs) {}
 103
 104 std::unique_ptr<Instruction>
 105 Instruction::create(const MCInstrInfo &InstrInfo,
 106                     const RegisterAliasingTrackerCache &RATC,
 107                     const BitVectorCache &BVC, unsigned Opcode) {
 108   const MCInstrDesc *const Description = &InstrInfo.get(Opcode);
 109   unsigned OpIndex = 0;
 110   SmallVector<Operand, 8> Operands;
 111   SmallVector<Variable, 4> Variables;
 112   for (; OpIndex < Description->getNumOperands(); ++OpIndex) {
 113     const auto &OpInfo = Description->operands()[OpIndex];
 114     Operand Operand;
 115     Operand.Index = OpIndex;
 116     Operand.IsDef = (OpIndex < Description->getNumDefs());
 117     // TODO(gchatelet): Handle isLookupPtrRegClass.
 118     if (OpInfo.RegClass >= 0)
 119       Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass);
 120     int TiedToIndex = Description->getOperandConstraint(OpIndex, MCOI::TIED_TO);
 121     assert((TiedToIndex == -1 ||
 122             (0 <= TiedToIndex &&
 123              TiedToIndex < std::numeric_limits<uint8_t>::max())) &&
 124            "Unknown Operand Constraint");
 125     if (TiedToIndex >= 0)
 126       Operand.TiedToIndex = TiedToIndex;
 127     Operand.Info = &OpInfo;
 128     Operands.push_back(Operand);
 129   }
 130   for (MCPhysReg MCPhysReg : Description->implicit_defs()) {
 131     Operand Operand;
 132     Operand.Index = OpIndex++;
 133     Operand.IsDef = true;
 134     Operand.Tracker = &RATC.getRegister(MCPhysReg);
 135     Operand.ImplicitReg = MCPhysReg;
 136     Operands.push_back(Operand);
 137   }
 138   for (MCPhysReg MCPhysReg : Description->implicit_uses()) {
 139     Operand Operand;
 140     Operand.Index = OpIndex++;
 141     Operand.IsDef = false;
 142     Operand.Tracker = &RATC.getRegister(MCPhysReg);
 143     Operand.ImplicitReg = MCPhysReg;
 144     Operands.push_back(Operand);
 145   }
 146   Variables.reserve(Operands.size()); // Variables.size() <= Operands.size()
 147   // Assigning Variables to non tied explicit operands.
 148   for (auto &Op : Operands)
 149     if (Op.isExplicit() && !Op.isTied()) {
 150       const size_t VariableIndex = Variables.size();
 151       assert(VariableIndex < std::numeric_limits<uint8_t>::max());
 152       Op.VariableIndex = VariableIndex;
 153       Variables.emplace_back();
 154       Variables.back().Index = VariableIndex;
 155     }
 156   // Assigning Variables to tied operands.
 157   for (auto &Op : Operands)
 158     if (Op.isExplicit() && Op.isTied())
 159       Op.VariableIndex = Operands[Op.getTiedToIndex()].getVariableIndex();
 160   // Assigning Operands to Variables.
 161   for (auto &Op : Operands)
 162     if (Op.isVariable())
 163       Variables[Op.getVariableIndex()].TiedOperands.push_back(Op.getIndex());
 164   // Processing Aliasing.
 165   BitVector ImplDefRegs = RATC.emptyRegisters();
 166   BitVector ImplUseRegs = RATC.emptyRegisters();
 167   BitVector AllDefRegs = RATC.emptyRegisters();
 168   BitVector AllUseRegs = RATC.emptyRegisters();
 169   for (const auto &Op : Operands) {
 170     if (Op.isReg()) {
 171       const auto &AliasingBits = Op.getRegisterAliasing().aliasedBits();
 172       if (Op.isDef())
 173         AllDefRegs |= AliasingBits;
 174       if (Op.isUse())
 175         AllUseRegs |= AliasingBits;
 176       if (Op.isDef() && Op.isImplicit())
 177         ImplDefRegs |= AliasingBits;
 178       if (Op.isUse() && Op.isImplicit())
 179         ImplUseRegs |= AliasingBits;
 180     }
 181   }
 182   // Can't use make_unique because constructor is private.
 183   return std::unique_ptr<Instruction>(new Instruction(
 184       Description, InstrInfo.getName(Opcode), std::move(Operands),
 185       std::move(Variables), BVC.getUnique(std::move(ImplDefRegs)),
 186       BVC.getUnique(std::move(ImplUseRegs)),
 187       BVC.getUnique(std::move(AllDefRegs)),
 188       BVC.getUnique(std::move(AllUseRegs))));
 189 }
 190
 191 const Operand &Instruction::getPrimaryOperand(const Variable &Var) const {
 192   const auto PrimaryOperandIndex = Var.getPrimaryOperandIndex();
 193   assert(PrimaryOperandIndex < Operands.size());
 194   return Operands[PrimaryOperandIndex];
 195 }
 196
 197 bool Instruction::hasMemoryOperands() const {
 198   return any_of(Operands, [](const Operand &Op) {
 199     return Op.isReg() && Op.isExplicit() && Op.isMemory();
 200   });
 201 }
 202
 203 bool Instruction::hasAliasingImplicitRegisters() const {
 204   return ImplDefRegs.anyCommon(ImplUseRegs);
 205 }
 206
 207 // Returns true if there are registers that are both in `A` and `B` but not in
 208 // `Forbidden`.
 209 static bool anyCommonExcludingForbidden(const BitVector &A, const BitVector &B,
 210                                         const BitVector &Forbidden) {
 211   assert(A.size() == B.size() && B.size() == Forbidden.size());
 212   const auto Size = A.size();
 213   for (int AIndex = A.find_first(); AIndex != -1;) {
 214     const int BIndex = B.find_first_in(AIndex, Size);
 215     if (BIndex == -1)
 216       return false;
 217     if (AIndex == BIndex && !Forbidden.test(AIndex))
 218       return true;
 219     AIndex = A.find_first_in(BIndex + 1, Size);
 220   }
 221   return false;
 222 }
 223
 224 bool Instruction::hasAliasingRegistersThrough(
 225     const Instruction &OtherInstr, const BitVector &ForbiddenRegisters) const {
 226   return anyCommonExcludingForbidden(AllDefRegs, OtherInstr.AllUseRegs,
 227                                      ForbiddenRegisters) &&
 228          anyCommonExcludingForbidden(OtherInstr.AllDefRegs, AllUseRegs,
 229                                      ForbiddenRegisters);
 230 }
 231
 232 bool Instruction::hasTiedRegisters() const {
 233   return any_of(Variables,
 234                 [](const Variable &Var) { return Var.hasTiedOperands(); });
 235 }
 236
 237 bool Instruction::hasAliasingRegisters(
 238     const BitVector &ForbiddenRegisters) const {
 239   return anyCommonExcludingForbidden(AllDefRegs, AllUseRegs,
 240                                      ForbiddenRegisters);
 241 }
 242
 243 bool Instruction::hasOneUseOrOneDef() const {
 244   return AllDefRegs.count() || AllUseRegs.count();
 245 }
 246
 247 void Instruction::dump(const MCRegisterInfo &RegInfo,
 248                        const RegisterAliasingTrackerCache &RATC,
 249                        raw_ostream &Stream) const {
 250   Stream << "- " << Name << "\n";
 251   for (const auto &Op : Operands) {
 252     Stream << "- Op" << Op.getIndex();
 253     if (Op.isExplicit())
 254       Stream << " Explicit";
 255     if (Op.isImplicit())
 256       Stream << " Implicit";
 257     if (Op.isUse())
 258       Stream << " Use";
 259     if (Op.isDef())
 260       Stream << " Def";
 261     if (Op.isImmediate())
 262       Stream << " Immediate";
 263     if (Op.isMemory())
 264       Stream << " Memory";
 265     if (Op.isReg()) {
 266       if (Op.isImplicitReg())
 267         Stream << " Reg(" << RegInfo.getName(Op.getImplicitReg()) << ")";
 268       else
 269         Stream << " RegClass("
 270                << RegInfo.getRegClassName(
 271                       &RegInfo.getRegClass(Op.Info->RegClass))
 272                << ")";
 273     }
 274     if (Op.isTied())
 275       Stream << " TiedToOp" << Op.getTiedToIndex();
 276     Stream << "\n";
 277   }
 278   for (const auto &Var : Variables) {
 279     Stream << "- Var" << Var.getIndex();
 280     Stream << " [";
 281     bool IsFirst = true;
 282     for (auto OperandIndex : Var.TiedOperands) {
 283       if (!IsFirst)
 284         Stream << ",";
 285       Stream << "Op" << OperandIndex;
 286       IsFirst = false;
 287     }
 288     Stream << "]";
 289     Stream << "\n";
 290   }
 291   if (hasMemoryOperands())
 292     Stream << "- hasMemoryOperands\n";
 293   if (hasAliasingImplicitRegisters())
 294     Stream << "- hasAliasingImplicitRegisters (execution is always serial)\n";
 295   if (hasTiedRegisters())
 296     Stream << "- hasTiedRegisters (execution is always serial)\n";
 297   if (hasAliasingRegisters(RATC.emptyRegisters()))
 298     Stream << "- hasAliasingRegisters\n";
 299 }
 300
 301 InstructionsCache::InstructionsCache(const MCInstrInfo &InstrInfo,
 302                                      const RegisterAliasingTrackerCache &RATC)
 303     : InstrInfo(InstrInfo), RATC(RATC), BVC() {}
 304
 305 const Instruction &InstructionsCache::getInstr(unsigned Opcode) const {
 306   auto &Found = Instructions[Opcode];
 307   if (!Found)
 308     Found = Instruction::create(InstrInfo, RATC, BVC, Opcode);
 309   return *Found;
 310 }
 311
 312 bool RegisterOperandAssignment::
 313 operator==(const RegisterOperandAssignment &Other) const {
 314   return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg);
 315 }
 316
 317 bool AliasingRegisterOperands::
 318 operator==(const AliasingRegisterOperands &Other) const {
 319   return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses);
 320 }
 321
 322 static void
 323 addOperandIfAlias(const MCPhysReg Reg, bool SelectDef,
 324                   ArrayRef<Operand> Operands,
 325                   SmallVectorImpl<RegisterOperandAssignment> &OperandValues) {
 326   for (const auto &Op : Operands) {
 327     if (Op.isReg() && Op.isDef() == SelectDef) {
 328       const int SourceReg = Op.getRegisterAliasing().getOrigin(Reg);
 329       if (SourceReg >= 0)
 330         OperandValues.emplace_back(&Op, SourceReg);
 331     }
 332   }
 333 }
 334
 335 bool AliasingRegisterOperands::hasImplicitAliasing() const {
 336   const auto HasImplicit = [](const RegisterOperandAssignment &ROV) {
 337     return ROV.Op->isImplicit();
 338   };
 339   return any_of(Defs, HasImplicit) && any_of(Uses, HasImplicit);
 340 }
 341
 342 bool AliasingConfigurations::empty() const { return Configurations.empty(); }
 343
 344 bool AliasingConfigurations::hasImplicitAliasing() const {
 345   return any_of(Configurations, [](const AliasingRegisterOperands &ARO) {
 346     return ARO.hasImplicitAliasing();
 347   });
 348 }
 349
 350 AliasingConfigurations::AliasingConfigurations(
 351     const Instruction &DefInstruction, const Instruction &UseInstruction,
 352     const BitVector &ForbiddenRegisters) {
 353   auto CommonRegisters = UseInstruction.AllUseRegs;
 354   CommonRegisters &= DefInstruction.AllDefRegs;
 355   CommonRegisters.reset(ForbiddenRegisters);
 356   if (!CommonRegisters.empty()) {
 357     for (const MCPhysReg Reg : CommonRegisters.set_bits()) {
 358       AliasingRegisterOperands ARO;
 359       addOperandIfAlias(Reg, true, DefInstruction.Operands, ARO.Defs);
 360       addOperandIfAlias(Reg, false, UseInstruction.Operands, ARO.Uses);
 361       if (!ARO.Defs.empty() && !ARO.Uses.empty() &&
 362           !is_contained(Configurations, ARO))
 363         Configurations.push_back(std::move(ARO));
 364     }
 365   }
 366 }
 367
 368 void DumpMCOperand(const MCRegisterInfo &MCRegisterInfo, const MCOperand &Op,
 369                    raw_ostream &OS) {
 370   if (!Op.isValid())
 371     OS << "Invalid";
 372   else if (Op.isReg())
 373     OS << MCRegisterInfo.getName(Op.getReg());
 374   else if (Op.isImm())
 375     OS << Op.getImm();
 376   else if (Op.isDFPImm())
 377     OS << bit_cast<double>(Op.getDFPImm());
 378   else if (Op.isSFPImm())
 379     OS << bit_cast<float>(Op.getSFPImm());
 380   else if (Op.isExpr())
 381     OS << "Expr";
 382   else if (Op.isInst())
 383     OS << "SubInst";
 384 }
 385
 386 void DumpMCInst(const MCRegisterInfo &MCRegisterInfo,
 387                 const MCInstrInfo &MCInstrInfo, const MCInst &MCInst,
 388                 raw_ostream &OS) {
 389   OS << MCInstrInfo.getName(MCInst.getOpcode());
 390   for (unsigned I = 0, E = MCInst.getNumOperands(); I < E; ++I) {
 391     if (I > 0)
 392       OS << ',';
 393     OS << ' ';
 394     DumpMCOperand(MCRegisterInfo, MCInst.getOperand(I), OS);
 395   }
 396 }
 397
 398 } // namespace exegesis
 399 } // namespace llvm