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