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 TiedToIndex < std::numeric_limits<uint8_t>::max()); 124 if (TiedToIndex >= 0) 125 Operand.TiedToIndex = TiedToIndex; 126 Operand.Info = &OpInfo; 127 Operands.push_back(Operand); 128 } 129 for (const MCPhysReg *MCPhysReg = Description->getImplicitDefs(); 130 MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) { 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 (const MCPhysReg *MCPhysReg = Description->getImplicitUses(); 139 MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) { 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 if (UseInstruction.AllUseRegs.anyCommon(DefInstruction.AllDefRegs)) { 354 auto CommonRegisters = UseInstruction.AllUseRegs; 355 CommonRegisters &= DefInstruction.AllDefRegs; 356 for (const MCPhysReg Reg : CommonRegisters.set_bits()) { 357 AliasingRegisterOperands ARO; 358 addOperandIfAlias(Reg, true, DefInstruction.Operands, ARO.Defs); 359 addOperandIfAlias(Reg, false, UseInstruction.Operands, ARO.Uses); 360 if (!ARO.Defs.empty() && !ARO.Uses.empty() && 361 !is_contained(Configurations, ARO)) 362 Configurations.push_back(std::move(ARO)); 363 } 364 } 365 } 366 367 void DumpMCOperand(const MCRegisterInfo &MCRegisterInfo, const MCOperand &Op, 368 raw_ostream &OS) { 369 if (!Op.isValid()) 370 OS << "Invalid"; 371 else if (Op.isReg()) 372 OS << MCRegisterInfo.getName(Op.getReg()); 373 else if (Op.isImm()) 374 OS << Op.getImm(); 375 else if (Op.isFPImm()) 376 OS << Op.getFPImm(); 377 else if (Op.isExpr()) 378 OS << "Expr"; 379 else if (Op.isInst()) 380 OS << "SubInst"; 381 } 382 383 void DumpMCInst(const MCRegisterInfo &MCRegisterInfo, 384 const MCInstrInfo &MCInstrInfo, const MCInst &MCInst, 385 raw_ostream &OS) { 386 OS << MCInstrInfo.getName(MCInst.getOpcode()); 387 for (unsigned I = 0, E = MCInst.getNumOperands(); I < E; ++I) { 388 if (I > 0) 389 OS << ','; 390 OS << ' '; 391 DumpMCOperand(MCRegisterInfo, MCInst.getOperand(I), OS); 392 } 393 } 394 395 } // namespace exegesis 396 } // namespace llvm 397