1 //===-- MCInstrDescView.cpp -------------------------------------*- 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 #include "MCInstrDescView.h"
10
11 #include <iterator>
12 #include <map>
13 #include <tuple>
14
15 #include "llvm/ADT/STLExtras.h"
16
17 namespace llvm {
18 namespace exegesis {
19
getIndex() const20 unsigned Variable::getIndex() const {
21 assert(Index >= 0 && "Index must be set");
22 return Index;
23 }
24
getPrimaryOperandIndex() const25 unsigned Variable::getPrimaryOperandIndex() const {
26 assert(!TiedOperands.empty());
27 return TiedOperands[0];
28 }
29
hasTiedOperands() const30 bool Variable::hasTiedOperands() const {
31 assert(TiedOperands.size() <= 2 &&
32 "No more than two operands can be tied together");
33 // By definition only Use and Def operands can be tied together.
34 // TiedOperands[0] is the Def operand (LLVM stores defs first).
35 // TiedOperands[1] is the Use operand.
36 return TiedOperands.size() > 1;
37 }
38
getIndex() const39 unsigned Operand::getIndex() const {
40 assert(Index >= 0 && "Index must be set");
41 return Index;
42 }
43
isExplicit() const44 bool Operand::isExplicit() const { return Info; }
45
isImplicit() const46 bool Operand::isImplicit() const { return !Info; }
47
isImplicitReg() const48 bool Operand::isImplicitReg() const { return ImplicitReg; }
49
isDef() const50 bool Operand::isDef() const { return IsDef; }
51
isUse() const52 bool Operand::isUse() const { return !IsDef; }
53
isReg() const54 bool Operand::isReg() const { return Tracker; }
55
isTied() const56 bool Operand::isTied() const { return TiedToIndex >= 0; }
57
isVariable() const58 bool Operand::isVariable() const { return VariableIndex >= 0; }
59
isMemory() const60 bool Operand::isMemory() const {
61 return isExplicit() &&
62 getExplicitOperandInfo().OperandType == llvm::MCOI::OPERAND_MEMORY;
63 }
64
isImmediate() const65 bool Operand::isImmediate() const {
66 return isExplicit() &&
67 getExplicitOperandInfo().OperandType == llvm::MCOI::OPERAND_IMMEDIATE;
68 }
69
getTiedToIndex() const70 unsigned Operand::getTiedToIndex() const {
71 assert(isTied() && "Operand must be tied to get the tied index");
72 assert(TiedToIndex >= 0 && "TiedToIndex must be set");
73 return TiedToIndex;
74 }
75
getVariableIndex() const76 unsigned Operand::getVariableIndex() const {
77 assert(isVariable() && "Operand must be variable to get the Variable index");
78 assert(VariableIndex >= 0 && "VariableIndex must be set");
79 return VariableIndex;
80 }
81
getImplicitReg() const82 unsigned Operand::getImplicitReg() const {
83 assert(ImplicitReg);
84 return *ImplicitReg;
85 }
86
getRegisterAliasing() const87 const RegisterAliasingTracker &Operand::getRegisterAliasing() const {
88 assert(Tracker);
89 return *Tracker;
90 }
91
getExplicitOperandInfo() const92 const llvm::MCOperandInfo &Operand::getExplicitOperandInfo() const {
93 assert(Info);
94 return *Info;
95 }
96
Instruction(const llvm::MCInstrInfo & InstrInfo,const RegisterAliasingTrackerCache & RATC,unsigned Opcode)97 Instruction::Instruction(const llvm::MCInstrInfo &InstrInfo,
98 const RegisterAliasingTrackerCache &RATC,
99 unsigned Opcode)
100 : Description(&InstrInfo.get(Opcode)), Name(InstrInfo.getName(Opcode)) {
101 unsigned OpIndex = 0;
102 for (; OpIndex < Description->getNumOperands(); ++OpIndex) {
103 const auto &OpInfo = Description->opInfo_begin()[OpIndex];
104 Operand Operand;
105 Operand.Index = OpIndex;
106 Operand.IsDef = (OpIndex < Description->getNumDefs());
107 // TODO(gchatelet): Handle isLookupPtrRegClass.
108 if (OpInfo.RegClass >= 0)
109 Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass);
110 Operand.TiedToIndex =
111 Description->getOperandConstraint(OpIndex, llvm::MCOI::TIED_TO);
112 Operand.Info = &OpInfo;
113 Operands.push_back(Operand);
114 }
115 for (const llvm::MCPhysReg *MCPhysReg = Description->getImplicitDefs();
116 MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
117 Operand Operand;
118 Operand.Index = OpIndex;
119 Operand.IsDef = true;
120 Operand.Tracker = &RATC.getRegister(*MCPhysReg);
121 Operand.ImplicitReg = MCPhysReg;
122 Operands.push_back(Operand);
123 }
124 for (const llvm::MCPhysReg *MCPhysReg = Description->getImplicitUses();
125 MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
126 Operand Operand;
127 Operand.Index = OpIndex;
128 Operand.IsDef = false;
129 Operand.Tracker = &RATC.getRegister(*MCPhysReg);
130 Operand.ImplicitReg = MCPhysReg;
131 Operands.push_back(Operand);
132 }
133 // Assigning Variables to non tied explicit operands.
134 Variables.reserve(Operands.size()); // Variables.size() <= Operands.size()
135 for (auto &Op : Operands)
136 if (Op.isExplicit() && !Op.isTied()) {
137 const size_t VariableIndex = Variables.size();
138 Op.VariableIndex = VariableIndex;
139 Variables.emplace_back();
140 Variables.back().Index = VariableIndex;
141 }
142 // Assigning Variables to tied operands.
143 for (auto &Op : Operands)
144 if (Op.isTied())
145 Op.VariableIndex = Operands[Op.getTiedToIndex()].getVariableIndex();
146 // Assigning Operands to Variables.
147 for (auto &Op : Operands)
148 if (Op.isVariable())
149 Variables[Op.getVariableIndex()].TiedOperands.push_back(Op.getIndex());
150 // Processing Aliasing.
151 ImplDefRegs = RATC.emptyRegisters();
152 ImplUseRegs = RATC.emptyRegisters();
153 AllDefRegs = RATC.emptyRegisters();
154 AllUseRegs = RATC.emptyRegisters();
155 for (const auto &Op : Operands) {
156 if (Op.isReg()) {
157 const auto &AliasingBits = Op.getRegisterAliasing().aliasedBits();
158 if (Op.isDef())
159 AllDefRegs |= AliasingBits;
160 if (Op.isUse())
161 AllUseRegs |= AliasingBits;
162 if (Op.isDef() && Op.isImplicit())
163 ImplDefRegs |= AliasingBits;
164 if (Op.isUse() && Op.isImplicit())
165 ImplUseRegs |= AliasingBits;
166 }
167 }
168 }
169
getPrimaryOperand(const Variable & Var) const170 const Operand &Instruction::getPrimaryOperand(const Variable &Var) const {
171 const auto PrimaryOperandIndex = Var.getPrimaryOperandIndex();
172 assert(PrimaryOperandIndex < Operands.size());
173 return Operands[PrimaryOperandIndex];
174 }
175
hasMemoryOperands() const176 bool Instruction::hasMemoryOperands() const {
177 return any_of(Operands, [](const Operand &Op) {
178 return Op.isReg() && Op.isExplicit() && Op.isMemory();
179 });
180 }
181
hasAliasingImplicitRegisters() const182 bool Instruction::hasAliasingImplicitRegisters() const {
183 return ImplDefRegs.anyCommon(ImplUseRegs);
184 }
185
hasAliasingImplicitRegistersThrough(const Instruction & OtherInstr) const186 bool Instruction::hasAliasingImplicitRegistersThrough(
187 const Instruction &OtherInstr) const {
188 return ImplDefRegs.anyCommon(OtherInstr.ImplUseRegs) &&
189 OtherInstr.ImplDefRegs.anyCommon(ImplUseRegs);
190 }
191
hasAliasingRegistersThrough(const Instruction & OtherInstr) const192 bool Instruction::hasAliasingRegistersThrough(
193 const Instruction &OtherInstr) const {
194 return AllDefRegs.anyCommon(OtherInstr.AllUseRegs) &&
195 OtherInstr.AllDefRegs.anyCommon(AllUseRegs);
196 }
197
hasTiedRegisters() const198 bool Instruction::hasTiedRegisters() const {
199 return llvm::any_of(
200 Variables, [](const Variable &Var) { return Var.hasTiedOperands(); });
201 }
202
hasAliasingRegisters() const203 bool Instruction::hasAliasingRegisters() const {
204 return AllDefRegs.anyCommon(AllUseRegs);
205 }
206
hasOneUseOrOneDef() const207 bool Instruction::hasOneUseOrOneDef() const {
208 return AllDefRegs.count() || AllUseRegs.count();
209 }
210
dump(const llvm::MCRegisterInfo & RegInfo,llvm::raw_ostream & Stream) const211 void Instruction::dump(const llvm::MCRegisterInfo &RegInfo,
212 llvm::raw_ostream &Stream) const {
213 Stream << "- " << Name << "\n";
214 for (const auto &Op : Operands) {
215 Stream << "- Op" << Op.getIndex();
216 if (Op.isExplicit())
217 Stream << " Explicit";
218 if (Op.isImplicit())
219 Stream << " Implicit";
220 if (Op.isUse())
221 Stream << " Use";
222 if (Op.isDef())
223 Stream << " Def";
224 if (Op.isImmediate())
225 Stream << " Immediate";
226 if (Op.isMemory())
227 Stream << " Memory";
228 if (Op.isReg()) {
229 if (Op.isImplicitReg())
230 Stream << " Reg(" << RegInfo.getName(Op.getImplicitReg()) << ")";
231 else
232 Stream << " RegClass("
233 << RegInfo.getRegClassName(
234 &RegInfo.getRegClass(Op.Info->RegClass))
235 << ")";
236 }
237 if (Op.isTied())
238 Stream << " TiedToOp" << Op.getTiedToIndex();
239 Stream << "\n";
240 }
241 for (const auto &Var : Variables) {
242 Stream << "- Var" << Var.getIndex();
243 Stream << " [";
244 bool IsFirst = true;
245 for (auto OperandIndex : Var.TiedOperands) {
246 if (!IsFirst)
247 Stream << ",";
248 Stream << "Op" << OperandIndex;
249 IsFirst = false;
250 }
251 Stream << "]";
252 Stream << "\n";
253 }
254 if (hasMemoryOperands())
255 Stream << "- hasMemoryOperands\n";
256 if (hasAliasingImplicitRegisters())
257 Stream << "- hasAliasingImplicitRegisters (execution is always serial)\n";
258 if (hasTiedRegisters())
259 Stream << "- hasTiedRegisters (execution is always serial)\n";
260 if (hasAliasingRegisters())
261 Stream << "- hasAliasingRegisters\n";
262 }
263
InstructionsCache(const llvm::MCInstrInfo & InstrInfo,const RegisterAliasingTrackerCache & RATC)264 InstructionsCache::InstructionsCache(const llvm::MCInstrInfo &InstrInfo,
265 const RegisterAliasingTrackerCache &RATC)
266 : InstrInfo(InstrInfo), RATC(RATC) {}
267
getInstr(unsigned Opcode) const268 const Instruction &InstructionsCache::getInstr(unsigned Opcode) const {
269 auto &Found = Instructions[Opcode];
270 if (!Found)
271 Found.reset(new Instruction(InstrInfo, RATC, Opcode));
272 return *Found;
273 }
274
275 bool RegisterOperandAssignment::
operator ==(const RegisterOperandAssignment & Other) const276 operator==(const RegisterOperandAssignment &Other) const {
277 return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg);
278 }
279
280 bool AliasingRegisterOperands::
operator ==(const AliasingRegisterOperands & Other) const281 operator==(const AliasingRegisterOperands &Other) const {
282 return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses);
283 }
284
addOperandIfAlias(const llvm::MCPhysReg Reg,bool SelectDef,llvm::ArrayRef<Operand> Operands,llvm::SmallVectorImpl<RegisterOperandAssignment> & OperandValues)285 static void addOperandIfAlias(
286 const llvm::MCPhysReg Reg, bool SelectDef, llvm::ArrayRef<Operand> Operands,
287 llvm::SmallVectorImpl<RegisterOperandAssignment> &OperandValues) {
288 for (const auto &Op : Operands) {
289 if (Op.isReg() && Op.isDef() == SelectDef) {
290 const int SourceReg = Op.getRegisterAliasing().getOrigin(Reg);
291 if (SourceReg >= 0)
292 OperandValues.emplace_back(&Op, SourceReg);
293 }
294 }
295 }
296
hasImplicitAliasing() const297 bool AliasingRegisterOperands::hasImplicitAliasing() const {
298 const auto HasImplicit = [](const RegisterOperandAssignment &ROV) {
299 return ROV.Op->isImplicit();
300 };
301 return llvm::any_of(Defs, HasImplicit) && llvm::any_of(Uses, HasImplicit);
302 }
303
empty() const304 bool AliasingConfigurations::empty() const { return Configurations.empty(); }
305
hasImplicitAliasing() const306 bool AliasingConfigurations::hasImplicitAliasing() const {
307 return llvm::any_of(Configurations, [](const AliasingRegisterOperands &ARO) {
308 return ARO.hasImplicitAliasing();
309 });
310 }
311
AliasingConfigurations(const Instruction & DefInstruction,const Instruction & UseInstruction)312 AliasingConfigurations::AliasingConfigurations(
313 const Instruction &DefInstruction, const Instruction &UseInstruction) {
314 if (UseInstruction.AllUseRegs.anyCommon(DefInstruction.AllDefRegs)) {
315 auto CommonRegisters = UseInstruction.AllUseRegs;
316 CommonRegisters &= DefInstruction.AllDefRegs;
317 for (const llvm::MCPhysReg Reg : CommonRegisters.set_bits()) {
318 AliasingRegisterOperands ARO;
319 addOperandIfAlias(Reg, true, DefInstruction.Operands, ARO.Defs);
320 addOperandIfAlias(Reg, false, UseInstruction.Operands, ARO.Uses);
321 if (!ARO.Defs.empty() && !ARO.Uses.empty() &&
322 !llvm::is_contained(Configurations, ARO))
323 Configurations.push_back(std::move(ARO));
324 }
325 }
326 }
327
DumpMCOperand(const llvm::MCRegisterInfo & MCRegisterInfo,const llvm::MCOperand & Op,llvm::raw_ostream & OS)328 void DumpMCOperand(const llvm::MCRegisterInfo &MCRegisterInfo,
329 const llvm::MCOperand &Op, llvm::raw_ostream &OS) {
330 if (!Op.isValid())
331 OS << "Invalid";
332 else if (Op.isReg())
333 OS << MCRegisterInfo.getName(Op.getReg());
334 else if (Op.isImm())
335 OS << Op.getImm();
336 else if (Op.isFPImm())
337 OS << Op.getFPImm();
338 else if (Op.isExpr())
339 OS << "Expr";
340 else if (Op.isInst())
341 OS << "SubInst";
342 }
343
DumpMCInst(const llvm::MCRegisterInfo & MCRegisterInfo,const llvm::MCInstrInfo & MCInstrInfo,const llvm::MCInst & MCInst,llvm::raw_ostream & OS)344 void DumpMCInst(const llvm::MCRegisterInfo &MCRegisterInfo,
345 const llvm::MCInstrInfo &MCInstrInfo,
346 const llvm::MCInst &MCInst, llvm::raw_ostream &OS) {
347 OS << MCInstrInfo.getName(MCInst.getOpcode());
348 for (unsigned I = 0, E = MCInst.getNumOperands(); I < E; ++I) {
349 if (I > 0)
350 OS << ',';
351 OS << ' ';
352 DumpMCOperand(MCRegisterInfo, MCInst.getOperand(I), OS);
353 }
354 }
355
356 } // namespace exegesis
357 } // namespace llvm
358