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