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