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