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