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