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 {
32namespace exegesis {
33
34// A variable represents the value associated to an Operand or a set of Operands
35// if they are tied together.
36struct Variable {
37 // Returns the index of this Variable inside Instruction's Variable.
38 unsigned getIndex() const;
39
40 // Returns the index of the Operand linked to this Variable.
41 unsigned getPrimaryOperandIndex() const;
42
43 // Returns whether this Variable has more than one Operand linked to it.
44 bool hasTiedOperands() const;
45
46 // The indices of the operands tied to this Variable.
47 SmallVector<unsigned, 2> TiedOperands;
48
49 // The index of this Variable in Instruction.Variables and its associated
50 // Value in InstructionBuilder.VariableValues.
51 std::optional<uint8_t> Index;
52};
53
54// MCOperandInfo can only represents Explicit operands. This object gives a
55// uniform view of Implicit and Explicit Operands.
56// - Index: can be used to refer to MCInstrDesc::operands for Explicit operands.
57// - Tracker: is set for Register Operands and is used to keep track of possible
58// registers and the registers reachable from them (aliasing registers).
59// - Info: a shortcut for MCInstrDesc::operands()[Index].
60// - TiedToIndex: the index of the Operand holding the value or -1.
61// - ImplicitReg: the register value when Operand is Implicit, 0 otherwise.
62// - VariableIndex: the index of the Variable holding the value for this Operand
63// or -1 if this operand is implicit.
64struct Operand {
65 bool isExplicit() const;
66 bool isImplicit() const;
67 bool isImplicitReg() const;
68 bool isDef() const;
69 bool isUse() const;
70 bool isReg() const;
71 bool isTied() const;
72 bool isVariable() const;
73 bool isMemory() const;
74 bool isImmediate() const;
75 bool isEarlyClobber() const;
76 unsigned getIndex() const;
77 unsigned getTiedToIndex() const;
78 unsigned getVariableIndex() const;
79 MCRegister getImplicitReg() const;
80 const RegisterAliasingTracker &getRegisterAliasing() const;
81 const MCOperandInfo &getExplicitOperandInfo() const;
82
83 // Please use the accessors above and not the following fields.
84 std::optional<uint8_t> Index;
85 bool IsDef = false;
86 bool IsEarlyClobber = false;
87 const RegisterAliasingTracker *Tracker = nullptr; // Set for Register Op.
88 const MCOperandInfo *Info = nullptr; // Set for Explicit Op.
89 std::optional<uint8_t> TiedToIndex; // Set for Reg&Explicit Op.
90 MCRegister ImplicitReg; // Non-0 for Implicit Op.
91 std::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.
97struct 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
102private:
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.
108struct 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 unsigned getOpcode() const { return Description.getOpcode(); }
121
122 // Returns the Operand linked to this Variable.
123 // In case the Variable is tied, the primary (i.e. Def) Operand is returned.
124 const Operand &getPrimaryOperand(const Variable &Var) const;
125
126 // Whether this instruction is self aliasing through its tied registers.
127 // Repeating this instruction is guaranteed to executes sequentially.
128 bool hasTiedRegisters() const;
129
130 // Whether this instruction is self aliasing through its implicit registers.
131 // Repeating this instruction is guaranteed to executes sequentially.
132 bool hasAliasingImplicitRegisters() const;
133
134 // Whether this instruction is self aliasing through some registers.
135 // Repeating this instruction may execute sequentially by picking aliasing
136 // Use and Def registers. It may also execute in parallel by picking non
137 // aliasing Use and Def registers.
138 bool hasAliasingRegisters(const BitVector &ForbiddenRegisters) const;
139
140 // Whether this instruction is self aliasing through some registers.
141 // Repeating this instruction may execute sequentially by picking aliasing
142 // Def and Not Memory Use registers. It may also execute in parallel by
143 // picking non aliasing Def and Not Memory Use registers.
144 bool hasAliasingNotMemoryRegisters(const BitVector &ForbiddenRegisters) const;
145
146 // Whether this instruction's registers alias with OtherInstr's registers.
147 bool hasAliasingRegistersThrough(const Instruction &OtherInstr,
148 const BitVector &ForbiddenRegisters) const;
149
150 // Returns whether this instruction has Memory Operands.
151 // Repeating this instruction executes sequentially with an instruction that
152 // reads or write the same memory region.
153 bool hasMemoryOperands() const;
154
155 // Returns whether this instruction as at least one use or one def.
156 // Repeating this instruction may execute sequentially by adding an
157 // instruction that aliases one of these.
158 bool hasOneUseOrOneDef() const;
159
160 // Convenient function to help with debugging.
161 void dump(const MCRegisterInfo &RegInfo,
162 const RegisterAliasingTrackerCache &RATC,
163 raw_ostream &Stream) const;
164
165 const MCInstrDesc &Description;
166 const StringRef Name; // The name of this instruction.
167 const SmallVector<Operand, 8> Operands;
168 const SmallVector<Variable, 4> Variables;
169 const BitVector &ImplDefRegs; // The set of aliased implicit def registers.
170 const BitVector &ImplUseRegs; // The set of aliased implicit use registers.
171 const BitVector &AllDefRegs; // The set of all aliased def registers.
172 const BitVector &AllUseRegs; // The set of all aliased use registers.
173 // The set of all aliased not memory use registers.
174 const BitVector &NonMemoryRegs;
175
176private:
177 Instruction(const MCInstrDesc *Description, StringRef Name,
178 SmallVector<Operand, 8> Operands,
179 SmallVector<Variable, 4> Variables, const BitVector *ImplDefRegs,
180 const BitVector *ImplUseRegs, const BitVector *AllDefRegs,
181 const BitVector *AllUseRegs, const BitVector *NonMemoryRegs);
182};
183
184// Instructions are expensive to instantiate. This class provides a cache of
185// Instructions with lazy construction.
186struct InstructionsCache {
187 InstructionsCache(const MCInstrInfo &InstrInfo,
188 const RegisterAliasingTrackerCache &RATC);
189
190 // Returns the Instruction object corresponding to this Opcode.
191 const Instruction &getInstr(unsigned Opcode) const;
192
193private:
194 const MCInstrInfo &InstrInfo;
195 const RegisterAliasingTrackerCache &RATC;
196 mutable std::unordered_map<unsigned, std::unique_ptr<Instruction>>
197 Instructions;
198 const BitVectorCache BVC;
199};
200
201// Represents the assignment of a Register to an Operand.
202struct RegisterOperandAssignment {
203 RegisterOperandAssignment(const Operand *Operand, MCPhysReg Reg)
204 : Op(Operand), Reg(Reg) {}
205
206 const Operand *Op; // Pointer to an Explicit Register Operand.
207 MCPhysReg Reg;
208
209 bool operator==(const RegisterOperandAssignment &other) const;
210};
211
212// Represents a set of Operands that would alias through the use of some
213// Registers.
214// There are two reasons why operands would alias:
215// - The registers assigned to each of the operands are the same or alias each
216// other (e.g. AX/AL)
217// - The operands are tied.
218struct AliasingRegisterOperands {
219 SmallVector<RegisterOperandAssignment, 1> Defs; // Unlikely size() > 1.
220 SmallVector<RegisterOperandAssignment, 2> Uses;
221
222 // True is Defs and Use contain an Implicit Operand.
223 bool hasImplicitAliasing() const;
224
225 bool operator==(const AliasingRegisterOperands &other) const;
226};
227
228// Returns all possible configurations leading Def registers of DefInstruction
229// to alias with Use registers of UseInstruction.
230struct AliasingConfigurations {
231 AliasingConfigurations(const Instruction &DefInstruction,
232 const Instruction &UseInstruction,
233 const BitVector &ForbiddenRegisters);
234
235 bool empty() const; // True if no aliasing configuration is found.
236 bool hasImplicitAliasing() const;
237
238 SmallVector<AliasingRegisterOperands, 32> Configurations;
239};
240
241// Writes MCInst to OS.
242// This is not assembly but the internal LLVM's name for instructions and
243// registers.
244void DumpMCInst(const MCRegisterInfo &MCRegisterInfo,
245 const MCInstrInfo &MCInstrInfo, const MCInst &MCInst,
246 raw_ostream &OS);
247
248} // namespace exegesis
249} // namespace llvm
250
251#endif // LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H
252