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