Home | History | Annotate | Line # | Download | only in lib 
      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.hasValue(); }
     51 
     52 bool Operand::isVariable() const { return VariableIndex.hasValue(); }
     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->opInfo_begin()[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 (const MCPhysReg *MCPhysReg = Description->getImplicitDefs();
    132        MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
    133     Operand Operand;
    134     Operand.Index = OpIndex;
    135     Operand.IsDef = true;
    136     Operand.Tracker = &RATC.getRegister(*MCPhysReg);
    137     Operand.ImplicitReg = MCPhysReg;
    138     Operands.push_back(Operand);
    139   }
    140   for (const MCPhysReg *MCPhysReg = Description->getImplicitUses();
    141        MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
    142     Operand Operand;
    143     Operand.Index = OpIndex;
    144     Operand.IsDef = false;
    145     Operand.Tracker = &RATC.getRegister(*MCPhysReg);
    146     Operand.ImplicitReg = MCPhysReg;
    147     Operands.push_back(Operand);
    148   }
    149   Variables.reserve(Operands.size()); // Variables.size() <= Operands.size()
    150   // Assigning Variables to non tied explicit operands.
    151   for (auto &Op : Operands)
    152     if (Op.isExplicit() && !Op.isTied()) {
    153       const size_t VariableIndex = Variables.size();
    154       assert(VariableIndex < std::numeric_limits<uint8_t>::max());
    155       Op.VariableIndex = VariableIndex;
    156       Variables.emplace_back();
    157       Variables.back().Index = VariableIndex;
    158     }
    159   // Assigning Variables to tied operands.
    160   for (auto &Op : Operands)
    161     if (Op.isExplicit() && Op.isTied())
    162       Op.VariableIndex = Operands[Op.getTiedToIndex()].getVariableIndex();
    163   // Assigning Operands to Variables.
    164   for (auto &Op : Operands)
    165     if (Op.isVariable())
    166       Variables[Op.getVariableIndex()].TiedOperands.push_back(Op.getIndex());
    167   // Processing Aliasing.
    168   BitVector ImplDefRegs = RATC.emptyRegisters();
    169   BitVector ImplUseRegs = RATC.emptyRegisters();
    170   BitVector AllDefRegs = RATC.emptyRegisters();
    171   BitVector AllUseRegs = RATC.emptyRegisters();
    172   for (const auto &Op : Operands) {
    173     if (Op.isReg()) {
    174       const auto &AliasingBits = Op.getRegisterAliasing().aliasedBits();
    175       if (Op.isDef())
    176         AllDefRegs |= AliasingBits;
    177       if (Op.isUse())
    178         AllUseRegs |= AliasingBits;
    179       if (Op.isDef() && Op.isImplicit())
    180         ImplDefRegs |= AliasingBits;
    181       if (Op.isUse() && Op.isImplicit())
    182         ImplUseRegs |= AliasingBits;
    183     }
    184   }
    185   // Can't use make_unique because constructor is private.
    186   return std::unique_ptr<Instruction>(new Instruction(
    187       Description, InstrInfo.getName(Opcode), std::move(Operands),
    188       std::move(Variables), BVC.getUnique(std::move(ImplDefRegs)),
    189       BVC.getUnique(std::move(ImplUseRegs)),
    190       BVC.getUnique(std::move(AllDefRegs)),
    191       BVC.getUnique(std::move(AllUseRegs))));
    192 }
    193 
    194 const Operand &Instruction::getPrimaryOperand(const Variable &Var) const {
    195   const auto PrimaryOperandIndex = Var.getPrimaryOperandIndex();
    196   assert(PrimaryOperandIndex < Operands.size());
    197   return Operands[PrimaryOperandIndex];
    198 }
    199 
    200 bool Instruction::hasMemoryOperands() const {
    201   return any_of(Operands, [](const Operand &Op) {
    202     return Op.isReg() && Op.isExplicit() && Op.isMemory();
    203   });
    204 }
    205 
    206 bool Instruction::hasAliasingImplicitRegisters() const {
    207   return ImplDefRegs.anyCommon(ImplUseRegs);
    208 }
    209 
    210 // Returns true if there are registers that are both in `A` and `B` but not in
    211 // `Forbidden`.
    212 static bool anyCommonExcludingForbidden(const BitVector &A, const BitVector &B,
    213                                         const BitVector &Forbidden) {
    214   assert(A.size() == B.size() && B.size() == Forbidden.size());
    215   const auto Size = A.size();
    216   for (int AIndex = A.find_first(); AIndex != -1;) {
    217     const int BIndex = B.find_first_in(AIndex, Size);
    218     if (BIndex == -1)
    219       return false;
    220     if (AIndex == BIndex && !Forbidden.test(AIndex))
    221       return true;
    222     AIndex = A.find_first_in(BIndex + 1, Size);
    223   }
    224   return false;
    225 }
    226 
    227 bool Instruction::hasAliasingRegistersThrough(
    228     const Instruction &OtherInstr, const BitVector &ForbiddenRegisters) const {
    229   return anyCommonExcludingForbidden(AllDefRegs, OtherInstr.AllUseRegs,
    230                                      ForbiddenRegisters) &&
    231          anyCommonExcludingForbidden(OtherInstr.AllDefRegs, AllUseRegs,
    232                                      ForbiddenRegisters);
    233 }
    234 
    235 bool Instruction::hasTiedRegisters() const {
    236   return any_of(Variables,
    237                 [](const Variable &Var) { return Var.hasTiedOperands(); });
    238 }
    239 
    240 bool Instruction::hasAliasingRegisters(
    241     const BitVector &ForbiddenRegisters) const {
    242   return anyCommonExcludingForbidden(AllDefRegs, AllUseRegs,
    243                                      ForbiddenRegisters);
    244 }
    245 
    246 bool Instruction::hasOneUseOrOneDef() const {
    247   return AllDefRegs.count() || AllUseRegs.count();
    248 }
    249 
    250 void Instruction::dump(const MCRegisterInfo &RegInfo,
    251                        const RegisterAliasingTrackerCache &RATC,
    252                        raw_ostream &Stream) const {
    253   Stream << "- " << Name << "\n";
    254   for (const auto &Op : Operands) {
    255     Stream << "- Op" << Op.getIndex();
    256     if (Op.isExplicit())
    257       Stream << " Explicit";
    258     if (Op.isImplicit())
    259       Stream << " Implicit";
    260     if (Op.isUse())
    261       Stream << " Use";
    262     if (Op.isDef())
    263       Stream << " Def";
    264     if (Op.isImmediate())
    265       Stream << " Immediate";
    266     if (Op.isMemory())
    267       Stream << " Memory";
    268     if (Op.isReg()) {
    269       if (Op.isImplicitReg())
    270         Stream << " Reg(" << RegInfo.getName(Op.getImplicitReg()) << ")";
    271       else
    272         Stream << " RegClass("
    273                << RegInfo.getRegClassName(
    274                       &RegInfo.getRegClass(Op.Info->RegClass))
    275                << ")";
    276     }
    277     if (Op.isTied())
    278       Stream << " TiedToOp" << Op.getTiedToIndex();
    279     Stream << "\n";
    280   }
    281   for (const auto &Var : Variables) {
    282     Stream << "- Var" << Var.getIndex();
    283     Stream << " [";
    284     bool IsFirst = true;
    285     for (auto OperandIndex : Var.TiedOperands) {
    286       if (!IsFirst)
    287         Stream << ",";
    288       Stream << "Op" << OperandIndex;
    289       IsFirst = false;
    290     }
    291     Stream << "]";
    292     Stream << "\n";
    293   }
    294   if (hasMemoryOperands())
    295     Stream << "- hasMemoryOperands\n";
    296   if (hasAliasingImplicitRegisters())
    297     Stream << "- hasAliasingImplicitRegisters (execution is always serial)\n";
    298   if (hasTiedRegisters())
    299     Stream << "- hasTiedRegisters (execution is always serial)\n";
    300   if (hasAliasingRegisters(RATC.emptyRegisters()))
    301     Stream << "- hasAliasingRegisters\n";
    302 }
    303 
    304 InstructionsCache::InstructionsCache(const MCInstrInfo &InstrInfo,
    305                                      const RegisterAliasingTrackerCache &RATC)
    306     : InstrInfo(InstrInfo), RATC(RATC), BVC() {}
    307 
    308 const Instruction &InstructionsCache::getInstr(unsigned Opcode) const {
    309   auto &Found = Instructions[Opcode];
    310   if (!Found)
    311     Found = Instruction::create(InstrInfo, RATC, BVC, Opcode);
    312   return *Found;
    313 }
    314 
    315 bool RegisterOperandAssignment::
    316 operator==(const RegisterOperandAssignment &Other) const {
    317   return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg);
    318 }
    319 
    320 bool AliasingRegisterOperands::
    321 operator==(const AliasingRegisterOperands &Other) const {
    322   return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses);
    323 }
    324 
    325 static void
    326 addOperandIfAlias(const MCPhysReg Reg, bool SelectDef,
    327                   ArrayRef<Operand> Operands,
    328                   SmallVectorImpl<RegisterOperandAssignment> &OperandValues) {
    329   for (const auto &Op : Operands) {
    330     if (Op.isReg() && Op.isDef() == SelectDef) {
    331       const int SourceReg = Op.getRegisterAliasing().getOrigin(Reg);
    332       if (SourceReg >= 0)
    333         OperandValues.emplace_back(&Op, SourceReg);
    334     }
    335   }
    336 }
    337 
    338 bool AliasingRegisterOperands::hasImplicitAliasing() const {
    339   const auto HasImplicit = [](const RegisterOperandAssignment &ROV) {
    340     return ROV.Op->isImplicit();
    341   };
    342   return any_of(Defs, HasImplicit) && any_of(Uses, HasImplicit);
    343 }
    344 
    345 bool AliasingConfigurations::empty() const { return Configurations.empty(); }
    346 
    347 bool AliasingConfigurations::hasImplicitAliasing() const {
    348   return any_of(Configurations, [](const AliasingRegisterOperands &ARO) {
    349     return ARO.hasImplicitAliasing();
    350   });
    351 }
    352 
    353 AliasingConfigurations::AliasingConfigurations(
    354     const Instruction &DefInstruction, const Instruction &UseInstruction) {
    355   if (UseInstruction.AllUseRegs.anyCommon(DefInstruction.AllDefRegs)) {
    356     auto CommonRegisters = UseInstruction.AllUseRegs;
    357     CommonRegisters &= DefInstruction.AllDefRegs;
    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
    401