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 MCRegister 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 MCRegister ImplicitReg; // 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 is self aliasing through some registers. 137 // Repeating this instruction may execute sequentially by picking aliasing 138 // Def and Not Memory Use registers. It may also execute in parallel by 139 // picking non aliasing Def and Not Memory Use registers. 140 bool hasAliasingNotMemoryRegisters(const BitVector &ForbiddenRegisters) const; 141 142 // Whether this instruction's registers alias with OtherInstr's registers. 143 bool hasAliasingRegistersThrough(const Instruction &OtherInstr, 144 const BitVector &ForbiddenRegisters) const; 145 146 // Returns whether this instruction has Memory Operands. 147 // Repeating this instruction executes sequentially with an instruction that 148 // reads or write the same memory region. 149 bool hasMemoryOperands() const; 150 151 // Returns whether this instruction as at least one use or one def. 152 // Repeating this instruction may execute sequentially by adding an 153 // instruction that aliases one of these. 154 bool hasOneUseOrOneDef() const; 155 156 // Convenient function to help with debugging. 157 void dump(const MCRegisterInfo &RegInfo, 158 const RegisterAliasingTrackerCache &RATC, 159 raw_ostream &Stream) const; 160 161 const MCInstrDesc &Description; 162 const StringRef Name; // The name of this instruction. 163 const SmallVector<Operand, 8> Operands; 164 const SmallVector<Variable, 4> Variables; 165 const BitVector &ImplDefRegs; // The set of aliased implicit def registers. 166 const BitVector &ImplUseRegs; // The set of aliased implicit use registers. 167 const BitVector &AllDefRegs; // The set of all aliased def registers. 168 const BitVector &AllUseRegs; // The set of all aliased use registers. 169 // The set of all aliased not memory use registers. 170 const BitVector &NonMemoryRegs; 171 172 private: 173 Instruction(const MCInstrDesc *Description, StringRef Name, 174 SmallVector<Operand, 8> Operands, 175 SmallVector<Variable, 4> Variables, const BitVector *ImplDefRegs, 176 const BitVector *ImplUseRegs, const BitVector *AllDefRegs, 177 const BitVector *AllUseRegs, const BitVector *NonMemoryRegs); 178 }; 179 180 // Instructions are expensive to instantiate. This class provides a cache of 181 // Instructions with lazy construction. 182 struct InstructionsCache { 183 InstructionsCache(const MCInstrInfo &InstrInfo, 184 const RegisterAliasingTrackerCache &RATC); 185 186 // Returns the Instruction object corresponding to this Opcode. 187 const Instruction &getInstr(unsigned Opcode) const; 188 189 private: 190 const MCInstrInfo &InstrInfo; 191 const RegisterAliasingTrackerCache &RATC; 192 mutable std::unordered_map<unsigned, std::unique_ptr<Instruction>> 193 Instructions; 194 const BitVectorCache BVC; 195 }; 196 197 // Represents the assignment of a Register to an Operand. 198 struct RegisterOperandAssignment { 199 RegisterOperandAssignment(const Operand *Operand, MCPhysReg Reg) 200 : Op(Operand), Reg(Reg) {} 201 202 const Operand *Op; // Pointer to an Explicit Register Operand. 203 MCPhysReg Reg; 204 205 bool operator==(const RegisterOperandAssignment &other) const; 206 }; 207 208 // Represents a set of Operands that would alias through the use of some 209 // Registers. 210 // There are two reasons why operands would alias: 211 // - The registers assigned to each of the operands are the same or alias each 212 // other (e.g. AX/AL) 213 // - The operands are tied. 214 struct AliasingRegisterOperands { 215 SmallVector<RegisterOperandAssignment, 1> Defs; // Unlikely size() > 1. 216 SmallVector<RegisterOperandAssignment, 2> Uses; 217 218 // True is Defs and Use contain an Implicit Operand. 219 bool hasImplicitAliasing() const; 220 221 bool operator==(const AliasingRegisterOperands &other) const; 222 }; 223 224 // Returns all possible configurations leading Def registers of DefInstruction 225 // to alias with Use registers of UseInstruction. 226 struct AliasingConfigurations { 227 AliasingConfigurations(const Instruction &DefInstruction, 228 const Instruction &UseInstruction, 229 const BitVector &ForbiddenRegisters); 230 231 bool empty() const; // True if no aliasing configuration is found. 232 bool hasImplicitAliasing() const; 233 234 SmallVector<AliasingRegisterOperands, 32> Configurations; 235 }; 236 237 // Writes MCInst to OS. 238 // This is not assembly but the internal LLVM's name for instructions and 239 // registers. 240 void DumpMCInst(const MCRegisterInfo &MCRegisterInfo, 241 const MCInstrInfo &MCInstrInfo, const MCInst &MCInst, 242 raw_ostream &OS); 243 244 } // namespace exegesis 245 } // namespace llvm 246 247 #endif // LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H 248