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