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