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