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/MC/MCInst.h"
28#include "llvm/MC/MCInstrDesc.h"
29#include "llvm/MC/MCInstrInfo.h"
30
31namespace llvm {
32class MCSubtargetInfo;
33namespace exegesis {
34
35// A variable represents the value associated to an Operand or a set of Operands
36// if they are tied together.
37struct 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 std::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: the register value when Operand is Implicit, 0 otherwise.
63// - VariableIndex: the index of the Variable holding the value for this Operand
64// or -1 if this operand is implicit.
65struct Operand {
66 bool isExplicit() const;
67 bool isImplicit() const;
68 bool isImplicitReg() const;
69 bool isDef() const;
70 bool isUse() const;
71 bool isReg() const;
72 bool isTied() const;
73 bool isVariable() const;
74 bool isMemory() const;
75 bool isImmediate() const;
76 bool isEarlyClobber() const;
77 unsigned getIndex() const;
78 unsigned getTiedToIndex() const;
79 unsigned getVariableIndex() const;
80 MCRegister 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 std::optional<uint8_t> Index;
86 bool IsDef = false;
87 bool IsEarlyClobber = false;
88 const RegisterAliasingTracker *Tracker = nullptr; // Set for Register Op.
89 const MCOperandInfo *Info = nullptr; // Set for Explicit Op.
90 std::optional<uint8_t> TiedToIndex; // Set for Reg&Explicit Op.
91 MCRegister ImplicitReg; // Non-0 for Implicit Op.
92 std::optional<uint8_t> VariableIndex; // Set for Explicit Op.
93};
94
95/// A cache of BitVector to reuse between Instructions.
96/// The cache will only be exercised during Instruction initialization.
97/// For X86, this is ~160 unique vectors for all of the ~15K Instructions.
98struct BitVectorCache {
99 // Finds or allocates the provided BitVector in the cache and retrieves it's
100 // unique instance.
101 const BitVector *getUnique(BitVector &&BV) const;
102
103private:
104 mutable std::vector<std::unique_ptr<BitVector>> Cache;
105};
106
107// A view over an MCInstrDesc offering a convenient interface to compute
108// Register aliasing.
109struct Instruction {
110 // Create an instruction for a particular Opcode.
111 static std::unique_ptr<Instruction>
112 create(const MCInstrInfo &InstrInfo, const RegisterAliasingTrackerCache &RATC,
113 const BitVectorCache &BVC, unsigned Opcode,
114 const MCSubtargetInfo *STI = nullptr);
115
116 // Prevent copy or move, instructions are allocated once and cached.
117 Instruction(const Instruction &) = delete;
118 Instruction(Instruction &&) = delete;
119 Instruction &operator=(const Instruction &) = delete;
120 Instruction &operator=(Instruction &&) = delete;
121
122 unsigned getOpcode() const { return Description.getOpcode(); }
123
124 // Returns the Operand linked to this Variable.
125 // In case the Variable is tied, the primary (i.e. Def) Operand is returned.
126 const Operand &getPrimaryOperand(const Variable &Var) const;
127
128 // Whether this instruction is self aliasing through its tied registers.
129 // Repeating this instruction is guaranteed to executes sequentially.
130 bool hasTiedRegisters() const;
131
132 // Whether this instruction is self aliasing through its implicit registers.
133 // Repeating this instruction is guaranteed to executes sequentially.
134 bool hasAliasingImplicitRegisters() const;
135
136 // Whether this instruction is self aliasing through some registers.
137 // Repeating this instruction may execute sequentially by picking aliasing
138 // Use and Def registers. It may also execute in parallel by picking non
139 // aliasing Use and Def registers.
140 bool hasAliasingRegisters(const BitVector &ForbiddenRegisters) const;
141
142 // Whether this instruction is self aliasing through some registers.
143 // Repeating this instruction may execute sequentially by picking aliasing
144 // Def and Not Memory Use registers. It may also execute in parallel by
145 // picking non aliasing Def and Not Memory Use registers.
146 bool hasAliasingNotMemoryRegisters(const BitVector &ForbiddenRegisters) const;
147
148 // Whether this instruction's registers alias with OtherInstr's registers.
149 bool hasAliasingRegistersThrough(const Instruction &OtherInstr,
150 const BitVector &ForbiddenRegisters) const;
151
152 // Returns whether this instruction has Memory Operands.
153 // Repeating this instruction executes sequentially with an instruction that
154 // reads or write the same memory region.
155 bool hasMemoryOperands() const;
156
157 // Returns whether this instruction as at least one use or one def.
158 // Repeating this instruction may execute sequentially by adding an
159 // instruction that aliases one of these.
160 bool hasOneUseOrOneDef() const;
161
162 // Convenient function to help with debugging.
163 void dump(const MCRegisterInfo &RegInfo,
164 const RegisterAliasingTrackerCache &RATC,
165 raw_ostream &Stream) const;
166
167 const MCInstrDesc &Description;
168 const StringRef Name; // The name of this instruction.
169 const SmallVector<Operand, 8> Operands;
170 const SmallVector<Variable, 4> Variables;
171 const BitVector &ImplDefRegs; // The set of aliased implicit def registers.
172 const BitVector &ImplUseRegs; // The set of aliased implicit use registers.
173 const BitVector &AllDefRegs; // The set of all aliased def registers.
174 const BitVector &AllUseRegs; // The set of all aliased use registers.
175 // The set of all aliased not memory use registers.
176 const BitVector &NonMemoryRegs;
177
178private:
179 Instruction(const MCInstrDesc *Description, StringRef Name,
180 SmallVector<Operand, 8> Operands,
181 SmallVector<Variable, 4> Variables, const BitVector *ImplDefRegs,
182 const BitVector *ImplUseRegs, const BitVector *AllDefRegs,
183 const BitVector *AllUseRegs, const BitVector *NonMemoryRegs);
184};
185
186// Instructions are expensive to instantiate. This class provides a cache of
187// Instructions with lazy construction.
188struct InstructionsCache {
189 InstructionsCache(const MCInstrInfo &InstrInfo,
190 const RegisterAliasingTrackerCache &RATC,
191 const MCSubtargetInfo *STI = nullptr);
192
193 // Returns the Instruction object corresponding to this Opcode.
194 const Instruction &getInstr(unsigned Opcode) const;
195
196private:
197 const MCInstrInfo &InstrInfo;
198 const RegisterAliasingTrackerCache &RATC;
199 const MCSubtargetInfo *STI;
200 mutable std::unordered_map<unsigned, std::unique_ptr<Instruction>>
201 Instructions;
202 const BitVectorCache BVC;
203};
204
205// Represents the assignment of a Register to an Operand.
206struct RegisterOperandAssignment {
207 RegisterOperandAssignment(const Operand *Operand, MCPhysReg Reg)
208 : Op(Operand), Reg(Reg) {}
209
210 const Operand *Op; // Pointer to an Explicit Register Operand.
211 MCPhysReg Reg;
212
213 bool operator==(const RegisterOperandAssignment &other) const;
214};
215
216// Represents a set of Operands that would alias through the use of some
217// Registers.
218// There are two reasons why operands would alias:
219// - The registers assigned to each of the operands are the same or alias each
220// other (e.g. AX/AL)
221// - The operands are tied.
222struct AliasingRegisterOperands {
223 SmallVector<RegisterOperandAssignment, 1> Defs; // Unlikely size() > 1.
224 SmallVector<RegisterOperandAssignment, 2> Uses;
225
226 // True is Defs and Use contain an Implicit Operand.
227 bool hasImplicitAliasing() const;
228
229 bool operator==(const AliasingRegisterOperands &other) const;
230};
231
232// Returns all possible configurations leading Def registers of DefInstruction
233// to alias with Use registers of UseInstruction.
234struct AliasingConfigurations {
235 AliasingConfigurations(const Instruction &DefInstruction,
236 const Instruction &UseInstruction,
237 const BitVector &ForbiddenRegisters);
238
239 bool empty() const; // True if no aliasing configuration is found.
240 bool hasImplicitAliasing() const;
241
242 SmallVector<AliasingRegisterOperands, 32> Configurations;
243};
244
245// Writes MCInst to OS.
246// This is not assembly but the internal LLVM's name for instructions and
247// registers.
248void DumpMCInst(const MCRegisterInfo &MCRegisterInfo,
249 const MCInstrInfo &MCInstrInfo, const MCInst &MCInst,
250 raw_ostream &OS);
251
252} // namespace exegesis
253} // namespace llvm
254
255#endif // LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H
256