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.isFPImm()) 378 OS << Op.getFPImm(); 379 else if (Op.isExpr()) 380 OS << "Expr"; 381 else if (Op.isInst()) 382 OS << "SubInst"; 383 } 384 385 void DumpMCInst(const MCRegisterInfo &MCRegisterInfo, 386 const MCInstrInfo &MCInstrInfo, const MCInst &MCInst, 387 raw_ostream &OS) { 388 OS << MCInstrInfo.getName(MCInst.getOpcode()); 389 for (unsigned I = 0, E = MCInst.getNumOperands(); I < E; ++I) { 390 if (I > 0) 391 OS << ','; 392 OS << ' '; 393 DumpMCOperand(MCRegisterInfo, MCInst.getOperand(I), OS); 394 } 395 } 396 397 } // namespace exegesis 398 } // namespace llvm 399