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
getIndex() const20 unsigned Variable::getIndex() const { return *Index; }
21
getPrimaryOperandIndex() const22 unsigned Variable::getPrimaryOperandIndex() const {
23 assert(!TiedOperands.empty());
24 return TiedOperands[0];
25 }
26
hasTiedOperands() const27 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
getIndex() const36 unsigned Operand::getIndex() const { return *Index; }
37
isExplicit() const38 bool Operand::isExplicit() const { return Info; }
39
isImplicit() const40 bool Operand::isImplicit() const { return !Info; }
41
isImplicitReg() const42 bool Operand::isImplicitReg() const { return ImplicitReg; }
43
isDef() const44 bool Operand::isDef() const { return IsDef; }
45
isUse() const46 bool Operand::isUse() const { return !IsDef; }
47
isReg() const48 bool Operand::isReg() const { return Tracker; }
49
isTied() const50 bool Operand::isTied() const { return TiedToIndex.hasValue(); }
51
isVariable() const52 bool Operand::isVariable() const { return VariableIndex.hasValue(); }
53
isMemory() const54 bool Operand::isMemory() const {
55 return isExplicit() &&
56 getExplicitOperandInfo().OperandType == MCOI::OPERAND_MEMORY;
57 }
58
isImmediate() const59 bool Operand::isImmediate() const {
60 return isExplicit() &&
61 getExplicitOperandInfo().OperandType == MCOI::OPERAND_IMMEDIATE;
62 }
63
getTiedToIndex() const64 unsigned Operand::getTiedToIndex() const { return *TiedToIndex; }
65
getVariableIndex() const66 unsigned Operand::getVariableIndex() const { return *VariableIndex; }
67
getImplicitReg() const68 unsigned Operand::getImplicitReg() const {
69 assert(ImplicitReg);
70 return *ImplicitReg;
71 }
72
getRegisterAliasing() const73 const RegisterAliasingTracker &Operand::getRegisterAliasing() const {
74 assert(Tracker);
75 return *Tracker;
76 }
77
getExplicitOperandInfo() const78 const MCOperandInfo &Operand::getExplicitOperandInfo() const {
79 assert(Info);
80 return *Info;
81 }
82
getUnique(BitVector && BV) const83 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
Instruction(const MCInstrDesc * Description,StringRef Name,SmallVector<Operand,8> Operands,SmallVector<Variable,4> Variables,const BitVector * ImplDefRegs,const BitVector * ImplUseRegs,const BitVector * AllDefRegs,const BitVector * AllUseRegs)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>
create(const MCInstrInfo & InstrInfo,const RegisterAliasingTrackerCache & RATC,const BitVectorCache & BVC,unsigned Opcode)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
getPrimaryOperand(const Variable & Var) const194 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
hasMemoryOperands() const200 bool Instruction::hasMemoryOperands() const {
201 return any_of(Operands, [](const Operand &Op) {
202 return Op.isReg() && Op.isExplicit() && Op.isMemory();
203 });
204 }
205
hasAliasingImplicitRegisters() const206 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`.
anyCommonExcludingForbidden(const BitVector & A,const BitVector & B,const BitVector & 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
hasAliasingRegistersThrough(const Instruction & OtherInstr,const BitVector & ForbiddenRegisters) const227 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
hasTiedRegisters() const235 bool Instruction::hasTiedRegisters() const {
236 return any_of(Variables,
237 [](const Variable &Var) { return Var.hasTiedOperands(); });
238 }
239
hasAliasingRegisters(const BitVector & ForbiddenRegisters) const240 bool Instruction::hasAliasingRegisters(
241 const BitVector &ForbiddenRegisters) const {
242 return anyCommonExcludingForbidden(AllDefRegs, AllUseRegs,
243 ForbiddenRegisters);
244 }
245
hasOneUseOrOneDef() const246 bool Instruction::hasOneUseOrOneDef() const {
247 return AllDefRegs.count() || AllUseRegs.count();
248 }
249
dump(const MCRegisterInfo & RegInfo,const RegisterAliasingTrackerCache & RATC,raw_ostream & Stream) const250 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
InstructionsCache(const MCInstrInfo & InstrInfo,const RegisterAliasingTrackerCache & RATC)304 InstructionsCache::InstructionsCache(const MCInstrInfo &InstrInfo,
305 const RegisterAliasingTrackerCache &RATC)
306 : InstrInfo(InstrInfo), RATC(RATC), BVC() {}
307
getInstr(unsigned Opcode) const308 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::
operator ==(const RegisterOperandAssignment & Other) const316 operator==(const RegisterOperandAssignment &Other) const {
317 return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg);
318 }
319
320 bool AliasingRegisterOperands::
operator ==(const AliasingRegisterOperands & Other) const321 operator==(const AliasingRegisterOperands &Other) const {
322 return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses);
323 }
324
325 static void
addOperandIfAlias(const MCPhysReg Reg,bool SelectDef,ArrayRef<Operand> Operands,SmallVectorImpl<RegisterOperandAssignment> & OperandValues)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
hasImplicitAliasing() const338 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
empty() const345 bool AliasingConfigurations::empty() const { return Configurations.empty(); }
346
hasImplicitAliasing() const347 bool AliasingConfigurations::hasImplicitAliasing() const {
348 return any_of(Configurations, [](const AliasingRegisterOperands &ARO) {
349 return ARO.hasImplicitAliasing();
350 });
351 }
352
AliasingConfigurations(const Instruction & DefInstruction,const Instruction & UseInstruction)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
DumpMCOperand(const MCRegisterInfo & MCRegisterInfo,const MCOperand & Op,raw_ostream & OS)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
DumpMCInst(const MCRegisterInfo & MCRegisterInfo,const MCInstrInfo & MCInstrInfo,const MCInst & MCInst,raw_ostream & OS)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