1 //===-- MCInstrDescView.h ---------------------------------------*- 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 /// \file
10 /// Provide views around LLVM structures to represents an instruction instance,
11 /// as well as its implicit and explicit arguments in a uniform way.
12 /// Arguments that are explicit and independant (non tied) also have a Variable
13 /// associated to them so the instruction can be fully defined by reading its
14 /// Variables.
15 ///
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H
19 #define LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H
20 
21 #include <memory>
22 #include <random>
23 #include <unordered_map>
24 
25 #include "RegisterAliasing.h"
26 #include "llvm/ADT/ArrayRef.h"
27 #include "llvm/ADT/Optional.h"
28 #include "llvm/MC/MCInst.h"
29 #include "llvm/MC/MCInstrDesc.h"
30 #include "llvm/MC/MCInstrInfo.h"
31 
32 namespace llvm {
33 namespace exegesis {
34 
35 // A variable represents the value associated to an Operand or a set of Operands
36 // if they are tied together.
37 struct Variable {
38   // Returns the index of this Variable inside Instruction's Variable.
39   unsigned getIndex() const;
40 
41   // Returns the index of the Operand linked to this Variable.
42   unsigned getPrimaryOperandIndex() const;
43 
44   // Returns whether this Variable has more than one Operand linked to it.
45   bool hasTiedOperands() const;
46 
47   // The indices of the operands tied to this Variable.
48   SmallVector<unsigned, 2> TiedOperands;
49 
50   // The index of this Variable in Instruction.Variables and its associated
51   // Value in InstructionBuilder.VariableValues.
52   Optional<uint8_t> Index;
53 };
54 
55 // MCOperandInfo can only represents Explicit operands. This object gives a
56 // uniform view of Implicit and Explicit Operands.
57 // - Index: can be used to refer to MCInstrDesc::operands for Explicit operands.
58 // - Tracker: is set for Register Operands and is used to keep track of possible
59 // registers and the registers reachable from them (aliasing registers).
60 // - Info: a shortcut for MCInstrDesc::operands()[Index].
61 // - TiedToIndex: the index of the Operand holding the value or -1.
62 // - ImplicitReg: a pointer to the register value when Operand is Implicit,
63 // nullptr otherwise.
64 // - VariableIndex: the index of the Variable holding the value for this Operand
65 // or -1 if this operand is implicit.
66 struct Operand {
67   bool isExplicit() const;
68   bool isImplicit() const;
69   bool isImplicitReg() const;
70   bool isDef() const;
71   bool isUse() const;
72   bool isReg() const;
73   bool isTied() const;
74   bool isVariable() const;
75   bool isMemory() const;
76   bool isImmediate() const;
77   unsigned getIndex() const;
78   unsigned getTiedToIndex() const;
79   unsigned getVariableIndex() const;
80   unsigned getImplicitReg() const;
81   const RegisterAliasingTracker &getRegisterAliasing() const;
82   const MCOperandInfo &getExplicitOperandInfo() const;
83 
84   // Please use the accessors above and not the following fields.
85   Optional<uint8_t> Index;
86   bool IsDef = false;
87   const RegisterAliasingTracker *Tracker = nullptr; // Set for Register Op.
88   const MCOperandInfo *Info = nullptr;              // Set for Explicit Op.
89   Optional<uint8_t> TiedToIndex;                    // Set for Reg&Explicit Op.
90   const MCPhysReg *ImplicitReg = nullptr;           // Set for Implicit Op.
91   Optional<uint8_t> VariableIndex;                  // Set for Explicit Op.
92 };
93 
94 /// A cache of BitVector to reuse between Instructions.
95 /// The cache will only be exercised during Instruction initialization.
96 /// For X86, this is ~160 unique vectors for all of the ~15K Instructions.
97 struct BitVectorCache {
98   // Finds or allocates the provided BitVector in the cache and retrieves it's
99   // unique instance.
100   const BitVector *getUnique(BitVector &&BV) const;
101 
102 private:
103   mutable std::vector<std::unique_ptr<BitVector>> Cache;
104 };
105 
106 // A view over an MCInstrDesc offering a convenient interface to compute
107 // Register aliasing.
108 struct Instruction {
109   // Create an instruction for a particular Opcode.
110   static std::unique_ptr<Instruction>
111   create(const MCInstrInfo &InstrInfo, const RegisterAliasingTrackerCache &RATC,
112          const BitVectorCache &BVC, unsigned Opcode);
113 
114   // Prevent copy or move, instructions are allocated once and cached.
115   Instruction(const Instruction &) = delete;
116   Instruction(Instruction &&) = delete;
117   Instruction &operator=(const Instruction &) = delete;
118   Instruction &operator=(Instruction &&) = delete;
119 
120   // Returns the Operand linked to this Variable.
121   // In case the Variable is tied, the primary (i.e. Def) Operand is returned.
122   const Operand &getPrimaryOperand(const Variable &Var) const;
123 
124   // Whether this instruction is self aliasing through its tied registers.
125   // Repeating this instruction is guaranteed to executes sequentially.
126   bool hasTiedRegisters() const;
127 
128   // Whether this instruction is self aliasing through its implicit registers.
129   // Repeating this instruction is guaranteed to executes sequentially.
130   bool hasAliasingImplicitRegisters() const;
131 
132   // Whether this instruction is self aliasing through some registers.
133   // Repeating this instruction may execute sequentially by picking aliasing
134   // Use and Def registers. It may also execute in parallel by picking non
135   // aliasing Use and Def registers.
136   bool hasAliasingRegisters(const BitVector &ForbiddenRegisters) const;
137 
138   // Whether this instruction's registers alias with OtherInstr's registers.
139   bool hasAliasingRegistersThrough(const Instruction &OtherInstr,
140                                    const BitVector &ForbiddenRegisters) const;
141 
142   // Returns whether this instruction has Memory Operands.
143   // Repeating this instruction executes sequentially with an instruction that
144   // reads or write the same memory region.
145   bool hasMemoryOperands() const;
146 
147   // Returns whether this instruction as at least one use or one def.
148   // Repeating this instruction may execute sequentially by adding an
149   // instruction that aliases one of these.
150   bool hasOneUseOrOneDef() const;
151 
152   // Convenient function to help with debugging.
153   void dump(const MCRegisterInfo &RegInfo,
154             const RegisterAliasingTrackerCache &RATC,
155             raw_ostream &Stream) const;
156 
157   const MCInstrDesc &Description;
158   const StringRef Name; // The name of this instruction.
159   const SmallVector<Operand, 8> Operands;
160   const SmallVector<Variable, 4> Variables;
161   const BitVector &ImplDefRegs; // The set of aliased implicit def registers.
162   const BitVector &ImplUseRegs; // The set of aliased implicit use registers.
163   const BitVector &AllDefRegs;  // The set of all aliased def registers.
164   const BitVector &AllUseRegs;  // The set of all aliased use registers.
165 private:
166   Instruction(const MCInstrDesc *Description, StringRef Name,
167               SmallVector<Operand, 8> Operands,
168               SmallVector<Variable, 4> Variables, const BitVector *ImplDefRegs,
169               const BitVector *ImplUseRegs, const BitVector *AllDefRegs,
170               const BitVector *AllUseRegs);
171 };
172 
173 // Instructions are expensive to instantiate. This class provides a cache of
174 // Instructions with lazy construction.
175 struct InstructionsCache {
176   InstructionsCache(const MCInstrInfo &InstrInfo,
177                     const RegisterAliasingTrackerCache &RATC);
178 
179   // Returns the Instruction object corresponding to this Opcode.
180   const Instruction &getInstr(unsigned Opcode) const;
181 
182 private:
183   const MCInstrInfo &InstrInfo;
184   const RegisterAliasingTrackerCache &RATC;
185   mutable std::unordered_map<unsigned, std::unique_ptr<Instruction>>
186       Instructions;
187   const BitVectorCache BVC;
188 };
189 
190 // Represents the assignment of a Register to an Operand.
191 struct RegisterOperandAssignment {
RegisterOperandAssignmentRegisterOperandAssignment192   RegisterOperandAssignment(const Operand *Operand, MCPhysReg Reg)
193       : Op(Operand), Reg(Reg) {}
194 
195   const Operand *Op; // Pointer to an Explicit Register Operand.
196   MCPhysReg Reg;
197 
198   bool operator==(const RegisterOperandAssignment &other) const;
199 };
200 
201 // Represents a set of Operands that would alias through the use of some
202 // Registers.
203 // There are two reasons why operands would alias:
204 // - The registers assigned to each of the operands are the same or alias each
205 //   other (e.g. AX/AL)
206 // - The operands are tied.
207 struct AliasingRegisterOperands {
208   SmallVector<RegisterOperandAssignment, 1> Defs; // Unlikely size() > 1.
209   SmallVector<RegisterOperandAssignment, 2> Uses;
210 
211   // True is Defs and Use contain an Implicit Operand.
212   bool hasImplicitAliasing() const;
213 
214   bool operator==(const AliasingRegisterOperands &other) const;
215 };
216 
217 // Returns all possible configurations leading Def registers of DefInstruction
218 // to alias with Use registers of UseInstruction.
219 struct AliasingConfigurations {
220   AliasingConfigurations(const Instruction &DefInstruction,
221                          const Instruction &UseInstruction);
222 
223   bool empty() const; // True if no aliasing configuration is found.
224   bool hasImplicitAliasing() const;
225 
226   SmallVector<AliasingRegisterOperands, 32> Configurations;
227 };
228 
229 // Writes MCInst to OS.
230 // This is not assembly but the internal LLVM's name for instructions and
231 // registers.
232 void DumpMCInst(const MCRegisterInfo &MCRegisterInfo,
233                 const MCInstrInfo &MCInstrInfo, const MCInst &MCInst,
234                 raw_ostream &OS);
235 
236 } // namespace exegesis
237 } // namespace llvm
238 
239 #endif // LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H
240