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 31 namespace llvm { 32 namespace exegesis { 33 34 // A variable represents the value associated to an Operand or a set of Operands 35 // if they are tied together. 36 struct 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. 64 struct 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. 95 struct 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 100 private: 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. 106 struct 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. 163 private: 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. 173 struct 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 180 private: 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. 189 struct RegisterOperandAssignment { RegisterOperandAssignmentRegisterOperandAssignment190 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. 205 struct 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. 217 struct 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. 231 void 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