1//===--------------------- InstrBuilder.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/// \file
9///
10/// This file implements the InstrBuilder interface.
11///
12//===----------------------------------------------------------------------===//
13
14#include "llvm/MCA/InstrBuilder.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/Hashing.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/MC/MCInst.h"
20#include "llvm/MCA/Support.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/WithColor.h"
23#include "llvm/Support/raw_ostream.h"
24
25#define DEBUG_TYPE "llvm-mca-instrbuilder"
26
27namespace llvm {
28namespace mca {
29
30char RecycledInstErr::ID = 0;
31
32template class LLVM_EXPORT_TEMPLATE InstructionError<MCInst>;
33
34InstrBuilder::InstrBuilder(const llvm::MCSubtargetInfo &sti,
35 const llvm::MCInstrInfo &mcii,
36 const llvm::MCRegisterInfo &mri,
37 const llvm::MCInstrAnalysis *mcia,
38 const mca::InstrumentManager &im, unsigned cl)
39 : STI(sti), MCII(mcii), MRI(mri), MCIA(mcia), IM(im), FirstCallInst(true),
40 FirstReturnInst(true), CallLatency(cl) {
41 const MCSchedModel &SM = STI.getSchedModel();
42 ProcResourceMasks.resize(N: SM.getNumProcResourceKinds());
43 computeProcResourceMasks(SM: STI.getSchedModel(), Masks: ProcResourceMasks);
44}
45
46static void initializeUsedResources(InstrDesc &ID,
47 const MCSchedClassDesc &SCDesc,
48 const MCSubtargetInfo &STI,
49 ArrayRef<uint64_t> ProcResourceMasks) {
50 const MCSchedModel &SM = STI.getSchedModel();
51
52 // Populate resources consumed.
53 using ResourcePlusCycles = std::pair<uint64_t, ResourceUsage>;
54 SmallVector<ResourcePlusCycles, 4> Worklist;
55
56 // Track cycles contributed by resources that are in a "Super" relationship.
57 // This is required if we want to correctly match the behavior of method
58 // SubtargetEmitter::ExpandProcResource() in Tablegen. When computing the set
59 // of "consumed" processor resources and resource cycles, the logic in
60 // ExpandProcResource() doesn't update the number of resource cycles
61 // contributed by a "Super" resource to a group.
62 // We need to take this into account when we find that a processor resource is
63 // part of a group, and it is also used as the "Super" of other resources.
64 // This map stores the number of cycles contributed by sub-resources that are
65 // part of a "Super" resource. The key value is the "Super" resource mask ID.
66 DenseMap<uint64_t, unsigned> SuperResources;
67
68 unsigned NumProcResources = SM.getNumProcResourceKinds();
69 APInt Buffers(NumProcResources, 0);
70
71 bool AllInOrderResources = true;
72 bool AnyDispatchHazards = false;
73 for (unsigned I = 0, E = SCDesc.NumWriteProcResEntries; I < E; ++I) {
74 const MCWriteProcResEntry *PRE = STI.getWriteProcResBegin(SC: &SCDesc) + I;
75 const MCProcResourceDesc &PR = *SM.getProcResource(ProcResourceIdx: PRE->ProcResourceIdx);
76 if (!PRE->ReleaseAtCycle) {
77#ifndef NDEBUG
78 WithColor::warning()
79 << "Ignoring invalid write of zero cycles on processor resource "
80 << PR.Name << "\n";
81 WithColor::note() << "found in scheduling class "
82 << SM.getSchedClassName(ID.SchedClassID)
83 << " (write index #" << I << ")\n";
84#endif
85 continue;
86 }
87
88 uint64_t Mask = ProcResourceMasks[PRE->ProcResourceIdx];
89 // Reservation station scaling preserves whether a size is -1, 0, or 1.
90 const int BufferSize = PR.BufferSize;
91 if (BufferSize < 0) {
92 AllInOrderResources = false;
93 } else {
94 Buffers.setBit(getResourceStateIndex(Mask));
95 AnyDispatchHazards |= (BufferSize == 0);
96 AllInOrderResources &= (BufferSize <= 1);
97 }
98
99 CycleSegment RCy(0, PRE->ReleaseAtCycle, false);
100 Worklist.emplace_back(Args: ResourcePlusCycles(Mask, ResourceUsage(RCy)));
101 if (PR.SuperIdx) {
102 uint64_t Super = ProcResourceMasks[PR.SuperIdx];
103 SuperResources[Super] += PRE->ReleaseAtCycle;
104 }
105 }
106
107 ID.MustIssueImmediately = AllInOrderResources && AnyDispatchHazards;
108
109 // Sort elements by mask popcount, so that we prioritize resource units over
110 // resource groups, and smaller groups over larger groups.
111 sort(C&: Worklist, Comp: [](const ResourcePlusCycles &A, const ResourcePlusCycles &B) {
112 unsigned popcntA = llvm::popcount(Value: A.first);
113 unsigned popcntB = llvm::popcount(Value: B.first);
114 if (popcntA < popcntB)
115 return true;
116 if (popcntA > popcntB)
117 return false;
118 return A.first < B.first;
119 });
120
121 uint64_t UsedResourceUnits = 0;
122 uint64_t UsedResourceGroups = 0;
123 uint64_t UnitsFromResourceGroups = 0;
124
125 // Remove cycles contributed by smaller resources, and check if there
126 // are partially overlapping resource groups.
127 ID.HasPartiallyOverlappingGroups = false;
128
129 for (unsigned I = 0, E = Worklist.size(); I < E; ++I) {
130 ResourcePlusCycles &A = Worklist[I];
131 if (!A.second.size()) {
132 assert(llvm::popcount(A.first) > 1 && "Expected a group!");
133 UsedResourceGroups |= llvm::bit_floor(Value: A.first);
134 continue;
135 }
136
137 ID.Resources.emplace_back(Args&: A);
138 uint64_t NormalizedMask = A.first;
139
140 if (llvm::popcount(Value: A.first) == 1) {
141 UsedResourceUnits |= A.first;
142 } else {
143 // Remove the leading 1 from the resource group mask.
144 NormalizedMask ^= llvm::bit_floor(Value: NormalizedMask);
145 if (UnitsFromResourceGroups & NormalizedMask)
146 ID.HasPartiallyOverlappingGroups = true;
147
148 UnitsFromResourceGroups |= NormalizedMask;
149 UsedResourceGroups |= (A.first ^ NormalizedMask);
150 }
151
152 for (unsigned J = I + 1; J < E; ++J) {
153 ResourcePlusCycles &B = Worklist[J];
154 if ((NormalizedMask & B.first) == NormalizedMask) {
155 B.second.CS.subtract(Cycles: A.second.size() - SuperResources[A.first]);
156 if (llvm::popcount(Value: B.first) > 1)
157 B.second.NumUnits++;
158 }
159 }
160 }
161
162 // A SchedWrite may specify a number of cycles in which a resource group
163 // is reserved. For example (on target x86; cpu Haswell):
164 //
165 // SchedWriteRes<[HWPort0, HWPort1, HWPort01]> {
166 // let ReleaseAtCycles = [2, 2, 3];
167 // }
168 //
169 // This means:
170 // Resource units HWPort0 and HWPort1 are both used for 2cy.
171 // Resource group HWPort01 is the union of HWPort0 and HWPort1.
172 // Since this write touches both HWPort0 and HWPort1 for 2cy, HWPort01
173 // will not be usable for 2 entire cycles from instruction issue.
174 //
175 // On top of those 2cy, SchedWriteRes explicitly specifies an extra latency
176 // of 3 cycles for HWPort01. This tool assumes that the 3cy latency is an
177 // extra delay on top of the 2 cycles latency.
178 // During those extra cycles, HWPort01 is not usable by other instructions.
179 for (ResourcePlusCycles &RPC : ID.Resources) {
180 if (llvm::popcount(Value: RPC.first) > 1 && !RPC.second.isReserved()) {
181 // Remove the leading 1 from the resource group mask.
182 uint64_t Mask = RPC.first ^ llvm::bit_floor(Value: RPC.first);
183 uint64_t MaxResourceUnits = llvm::popcount(Value: Mask);
184 if (RPC.second.NumUnits > (unsigned)llvm::popcount(Value: Mask)) {
185 RPC.second.setReserved();
186 RPC.second.NumUnits = MaxResourceUnits;
187 }
188 }
189 }
190
191 // Identify extra buffers that are consumed through super resources.
192 for (const auto &SR : SuperResources) {
193 for (unsigned I = 1, E = NumProcResources; I < E; ++I) {
194 if (SM.getProcResource(ProcResourceIdx: I)->BufferSize == -1)
195 continue;
196
197 uint64_t Mask = ProcResourceMasks[I];
198 if (Mask != SR.first && ((Mask & SR.first) == SR.first))
199 Buffers.setBit(getResourceStateIndex(Mask));
200 }
201 }
202
203 ID.UsedBuffers = Buffers.getZExtValue();
204 ID.UsedProcResUnits = UsedResourceUnits;
205 ID.UsedProcResGroups = UsedResourceGroups;
206
207 LLVM_DEBUG({
208 for (const std::pair<uint64_t, ResourceUsage> &R : ID.Resources)
209 dbgs() << "\t\tResource Mask=" << format_hex(R.first, 16) << ", "
210 << "Reserved=" << R.second.isReserved() << ", "
211 << "#Units=" << R.second.NumUnits << ", "
212 << "cy=" << R.second.size() << '\n';
213 uint64_t BufferIDs = ID.UsedBuffers;
214 while (BufferIDs) {
215 uint64_t Current = BufferIDs & (-BufferIDs);
216 dbgs() << "\t\tBuffer Mask=" << format_hex(Current, 16) << '\n';
217 BufferIDs ^= Current;
218 }
219 dbgs() << "\t\t Used Units=" << format_hex(ID.UsedProcResUnits, 16) << '\n';
220 dbgs() << "\t\tUsed Groups=" << format_hex(ID.UsedProcResGroups, 16)
221 << '\n';
222 dbgs() << "\t\tHasPartiallyOverlappingGroups="
223 << ID.HasPartiallyOverlappingGroups << '\n';
224 });
225}
226
227static void computeMaxLatency(InstrDesc &ID, const MCSchedClassDesc &SCDesc,
228 const MCSubtargetInfo &STI, unsigned CallLatency,
229 bool IsCall) {
230 if (IsCall) {
231 // We cannot estimate how long this call will take.
232 // Artificially set an arbitrarily high latency.
233 ID.MaxLatency = CallLatency;
234 return;
235 }
236
237 int Latency = MCSchedModel::computeInstrLatency(STI, SCDesc);
238 // If latency is unknown, then conservatively assume the MaxLatency set for
239 // calls.
240 ID.MaxLatency = Latency < 0 ? CallLatency : static_cast<unsigned>(Latency);
241}
242
243static Error verifyOperands(const MCInstrDesc &MCDesc, const MCInst &MCI) {
244 // Count register definitions, and skip non register operands in the process.
245 unsigned I, E;
246 unsigned NumExplicitDefs = MCDesc.getNumDefs();
247 for (I = 0, E = MCI.getNumOperands(); NumExplicitDefs && I < E; ++I) {
248 const MCOperand &Op = MCI.getOperand(i: I);
249 if (Op.isReg())
250 --NumExplicitDefs;
251 }
252
253 if (NumExplicitDefs) {
254 return make_error<InstructionError<MCInst>>(
255 Args: "Expected more register operand definitions.", Args: MCI);
256 }
257
258 if (MCDesc.hasOptionalDef()) {
259 // Always assume that the optional definition is the last operand.
260 const MCOperand &Op = MCI.getOperand(i: MCDesc.getNumOperands() - 1);
261 if (I == MCI.getNumOperands() || !Op.isReg()) {
262 std::string Message =
263 "expected a register operand for an optional definition. Instruction "
264 "has not been correctly analyzed.";
265 return make_error<InstructionError<MCInst>>(Args&: Message, Args: MCI);
266 }
267 }
268
269 return ErrorSuccess();
270}
271
272void InstrBuilder::populateWrites(InstrDesc &ID, const MCInst &MCI,
273 unsigned SchedClassID) {
274 const MCInstrDesc &MCDesc = MCII.get(Opcode: MCI.getOpcode());
275 const MCSchedModel &SM = STI.getSchedModel();
276 const MCSchedClassDesc &SCDesc = *SM.getSchedClassDesc(SchedClassIdx: SchedClassID);
277
278 // Assumptions made by this algorithm:
279 // 1. The number of explicit and implicit register definitions in a MCInst
280 // matches the number of explicit and implicit definitions according to
281 // the opcode descriptor (MCInstrDesc).
282 // 2. Uses start at index #(MCDesc.getNumDefs()).
283 // 3. There can only be a single optional register definition, an it is
284 // either the last operand of the sequence (excluding extra operands
285 // contributed by variadic opcodes) or one of the explicit register
286 // definitions. The latter occurs for some Thumb1 instructions.
287 //
288 // These assumptions work quite well for most out-of-order in-tree targets
289 // like x86. This is mainly because the vast majority of instructions is
290 // expanded to MCInst using a straightforward lowering logic that preserves
291 // the ordering of the operands.
292 //
293 // About assumption 1.
294 // The algorithm allows non-register operands between register operand
295 // definitions. This helps to handle some special ARM instructions with
296 // implicit operand increment (-mtriple=armv7):
297 //
298 // vld1.32 {d18, d19}, [r1]! @ <MCInst #1463 VLD1q32wb_fixed
299 // @ <MCOperand Reg:59>
300 // @ <MCOperand Imm:0> (!!)
301 // @ <MCOperand Reg:67>
302 // @ <MCOperand Imm:0>
303 // @ <MCOperand Imm:14>
304 // @ <MCOperand Reg:0>>
305 //
306 // MCDesc reports:
307 // 6 explicit operands.
308 // 1 optional definition
309 // 2 explicit definitions (!!)
310 //
311 // The presence of an 'Imm' operand between the two register definitions
312 // breaks the assumption that "register definitions are always at the
313 // beginning of the operand sequence".
314 //
315 // To workaround this issue, this algorithm ignores (i.e. skips) any
316 // non-register operands between register definitions. The optional
317 // definition is still at index #(NumOperands-1).
318 //
319 // According to assumption 2. register reads start at #(NumExplicitDefs-1).
320 // That means, register R1 from the example is both read and written.
321 unsigned NumExplicitDefs = MCDesc.getNumDefs();
322 unsigned NumImplicitDefs = MCDesc.implicit_defs().size();
323 unsigned NumWriteLatencyEntries = SCDesc.NumWriteLatencyEntries;
324 unsigned TotalDefs = NumExplicitDefs + NumImplicitDefs;
325 if (MCDesc.hasOptionalDef())
326 TotalDefs++;
327
328 unsigned NumVariadicOps = MCI.getNumOperands() - MCDesc.getNumOperands();
329 ID.Writes.resize(N: TotalDefs + NumVariadicOps);
330 // Iterate over the operands list, and skip non-register or constant register
331 // operands. The first NumExplicitDefs register operands are expected to be
332 // register definitions.
333 unsigned CurrentDef = 0;
334 unsigned OptionalDefIdx = MCDesc.getNumOperands() - 1;
335 unsigned i = 0;
336 for (; i < MCI.getNumOperands() && CurrentDef < NumExplicitDefs; ++i) {
337 const MCOperand &Op = MCI.getOperand(i);
338 if (!Op.isReg())
339 continue;
340
341 if (MCDesc.operands()[CurrentDef].isOptionalDef()) {
342 OptionalDefIdx = CurrentDef++;
343 continue;
344 }
345
346 WriteDescriptor &Write = ID.Writes[CurrentDef];
347 Write.OpIndex = i;
348 if (CurrentDef < NumWriteLatencyEntries) {
349 const MCWriteLatencyEntry &WLE =
350 *STI.getWriteLatencyEntry(SC: &SCDesc, DefIdx: CurrentDef);
351 // Conservatively default to MaxLatency.
352 Write.Latency =
353 WLE.Cycles < 0 ? ID.MaxLatency : static_cast<unsigned>(WLE.Cycles);
354 Write.SClassOrWriteResourceID = WLE.WriteResourceID;
355 } else {
356 // Assign a default latency for this write.
357 Write.Latency = ID.MaxLatency;
358 Write.SClassOrWriteResourceID = 0;
359 }
360 Write.IsOptionalDef = false;
361 LLVM_DEBUG({
362 dbgs() << "\t\t[Def] OpIdx=" << Write.OpIndex
363 << ", Latency=" << Write.Latency
364 << ", WriteResourceID=" << Write.SClassOrWriteResourceID << '\n';
365 });
366 CurrentDef++;
367 }
368
369 assert(CurrentDef == NumExplicitDefs &&
370 "Expected more register operand definitions.");
371 for (CurrentDef = 0; CurrentDef < NumImplicitDefs; ++CurrentDef) {
372 unsigned Index = NumExplicitDefs + CurrentDef;
373 WriteDescriptor &Write = ID.Writes[Index];
374 Write.OpIndex = ~CurrentDef;
375 Write.RegisterID = MCDesc.implicit_defs()[CurrentDef];
376 if (Index < NumWriteLatencyEntries) {
377 const MCWriteLatencyEntry &WLE =
378 *STI.getWriteLatencyEntry(SC: &SCDesc, DefIdx: Index);
379 // Conservatively default to MaxLatency.
380 Write.Latency =
381 WLE.Cycles < 0 ? ID.MaxLatency : static_cast<unsigned>(WLE.Cycles);
382 Write.SClassOrWriteResourceID = WLE.WriteResourceID;
383 } else {
384 // Assign a default latency for this write.
385 Write.Latency = ID.MaxLatency;
386 Write.SClassOrWriteResourceID = 0;
387 }
388
389 Write.IsOptionalDef = false;
390 assert(Write.RegisterID != 0 && "Expected a valid phys register!");
391 LLVM_DEBUG({
392 dbgs() << "\t\t[Def][I] OpIdx=" << ~Write.OpIndex
393 << ", PhysReg=" << MRI.getName(Write.RegisterID)
394 << ", Latency=" << Write.Latency
395 << ", WriteResourceID=" << Write.SClassOrWriteResourceID << '\n';
396 });
397 }
398
399 if (MCDesc.hasOptionalDef()) {
400 WriteDescriptor &Write = ID.Writes[NumExplicitDefs + NumImplicitDefs];
401 Write.OpIndex = OptionalDefIdx;
402 // Assign a default latency for this write.
403 Write.Latency = ID.MaxLatency;
404 Write.SClassOrWriteResourceID = 0;
405 Write.IsOptionalDef = true;
406 LLVM_DEBUG({
407 dbgs() << "\t\t[Def][O] OpIdx=" << Write.OpIndex
408 << ", Latency=" << Write.Latency
409 << ", WriteResourceID=" << Write.SClassOrWriteResourceID << '\n';
410 });
411 }
412
413 if (!NumVariadicOps)
414 return;
415
416 bool AssumeUsesOnly = !MCDesc.variadicOpsAreDefs();
417 CurrentDef = NumExplicitDefs + NumImplicitDefs + MCDesc.hasOptionalDef();
418 for (unsigned I = 0, OpIndex = MCDesc.getNumOperands();
419 I < NumVariadicOps && !AssumeUsesOnly; ++I, ++OpIndex) {
420 const MCOperand &Op = MCI.getOperand(i: OpIndex);
421 if (!Op.isReg())
422 continue;
423
424 WriteDescriptor &Write = ID.Writes[CurrentDef];
425 Write.OpIndex = OpIndex;
426 // Assign a default latency for this write.
427 Write.Latency = ID.MaxLatency;
428 Write.SClassOrWriteResourceID = 0;
429 Write.IsOptionalDef = false;
430 ++CurrentDef;
431 LLVM_DEBUG({
432 dbgs() << "\t\t[Def][V] OpIdx=" << Write.OpIndex
433 << ", Latency=" << Write.Latency
434 << ", WriteResourceID=" << Write.SClassOrWriteResourceID << '\n';
435 });
436 }
437
438 ID.Writes.resize(N: CurrentDef);
439}
440
441void InstrBuilder::populateReads(InstrDesc &ID, const MCInst &MCI,
442 unsigned SchedClassID) {
443 const MCInstrDesc &MCDesc = MCII.get(Opcode: MCI.getOpcode());
444 unsigned NumExplicitUses = MCDesc.getNumOperands() - MCDesc.getNumDefs();
445 unsigned NumImplicitUses = MCDesc.implicit_uses().size();
446 // Remove the optional definition.
447 if (MCDesc.hasOptionalDef())
448 --NumExplicitUses;
449 unsigned NumVariadicOps = MCI.getNumOperands() - MCDesc.getNumOperands();
450 unsigned TotalUses = NumExplicitUses + NumImplicitUses + NumVariadicOps;
451 ID.Reads.resize(N: TotalUses);
452 unsigned CurrentUse = 0;
453 for (unsigned I = 0, OpIndex = MCDesc.getNumDefs(); I < NumExplicitUses;
454 ++I, ++OpIndex) {
455 const MCOperand &Op = MCI.getOperand(i: OpIndex);
456 if (!Op.isReg())
457 continue;
458
459 ReadDescriptor &Read = ID.Reads[CurrentUse];
460 Read.OpIndex = OpIndex;
461 Read.UseIndex = I;
462 Read.SchedClassID = SchedClassID;
463 ++CurrentUse;
464 LLVM_DEBUG(dbgs() << "\t\t[Use] OpIdx=" << Read.OpIndex
465 << ", UseIndex=" << Read.UseIndex << '\n');
466 }
467
468 // For the purpose of ReadAdvance, implicit uses come directly after explicit
469 // uses. The "UseIndex" must be updated according to that implicit layout.
470 for (unsigned I = 0; I < NumImplicitUses; ++I) {
471 ReadDescriptor &Read = ID.Reads[CurrentUse + I];
472 Read.OpIndex = ~I;
473 Read.UseIndex = NumExplicitUses + I;
474 Read.RegisterID = MCDesc.implicit_uses()[I];
475 Read.SchedClassID = SchedClassID;
476 LLVM_DEBUG(dbgs() << "\t\t[Use][I] OpIdx=" << ~Read.OpIndex
477 << ", UseIndex=" << Read.UseIndex << ", RegisterID="
478 << MRI.getName(Read.RegisterID) << '\n');
479 }
480
481 CurrentUse += NumImplicitUses;
482
483 bool AssumeDefsOnly = MCDesc.variadicOpsAreDefs();
484 for (unsigned I = 0, OpIndex = MCDesc.getNumOperands();
485 I < NumVariadicOps && !AssumeDefsOnly; ++I, ++OpIndex) {
486 const MCOperand &Op = MCI.getOperand(i: OpIndex);
487 if (!Op.isReg())
488 continue;
489
490 ReadDescriptor &Read = ID.Reads[CurrentUse];
491 Read.OpIndex = OpIndex;
492 Read.UseIndex = NumExplicitUses + NumImplicitUses + I;
493 Read.SchedClassID = SchedClassID;
494 ++CurrentUse;
495 LLVM_DEBUG(dbgs() << "\t\t[Use][V] OpIdx=" << Read.OpIndex
496 << ", UseIndex=" << Read.UseIndex << '\n');
497 }
498
499 ID.Reads.resize(N: CurrentUse);
500}
501
502hash_code hashMCOperand(const MCOperand &MCO) {
503 hash_code TypeHash = hash_combine(args: MCO.isReg(), args: MCO.isImm(), args: MCO.isSFPImm(),
504 args: MCO.isDFPImm(), args: MCO.isExpr(), args: MCO.isInst());
505 if (MCO.isReg())
506 return hash_combine(args: TypeHash, args: MCO.getReg());
507
508 return TypeHash;
509}
510
511hash_code hashMCInst(const MCInst &MCI) {
512 hash_code InstructionHash = hash_combine(args: MCI.getOpcode(), args: MCI.getFlags());
513 for (unsigned I = 0; I < MCI.getNumOperands(); ++I) {
514 InstructionHash =
515 hash_combine(args: InstructionHash, args: hashMCOperand(MCO: MCI.getOperand(i: I)));
516 }
517 return InstructionHash;
518}
519
520Error InstrBuilder::verifyInstrDesc(const InstrDesc &ID,
521 const MCInst &MCI) const {
522 if (ID.NumMicroOps != 0)
523 return ErrorSuccess();
524
525 bool UsesBuffers = ID.UsedBuffers;
526 bool UsesResources = !ID.Resources.empty();
527 if (!UsesBuffers && !UsesResources)
528 return ErrorSuccess();
529
530 // FIXME: see PR44797. We should revisit these checks and possibly move them
531 // in CodeGenSchedule.cpp.
532 StringRef Message = "found an inconsistent instruction that decodes to zero "
533 "opcodes and that consumes scheduler resources.";
534 return make_error<InstructionError<MCInst>>(Args: std::string(Message), Args: MCI);
535}
536
537Expected<unsigned> InstrBuilder::getVariantSchedClassID(const MCInst &MCI,
538 unsigned SchedClassID) {
539 const MCSchedModel &SM = STI.getSchedModel();
540 unsigned CPUID = SM.getProcessorID();
541 while (SchedClassID && SM.getSchedClassDesc(SchedClassIdx: SchedClassID)->isVariant())
542 SchedClassID =
543 STI.resolveVariantSchedClass(SchedClass: SchedClassID, MI: &MCI, MCII: &MCII, CPUID);
544
545 if (!SchedClassID) {
546 return make_error<InstructionError<MCInst>>(
547 Args: "unable to resolve scheduling class for write variant.", Args: MCI);
548 }
549
550 return SchedClassID;
551}
552
553Expected<const InstrDesc &>
554InstrBuilder::createInstrDescImpl(const MCInst &MCI,
555 const SmallVector<Instrument *> &IVec) {
556 assert(STI.getSchedModel().hasInstrSchedModel() &&
557 "Itineraries are not yet supported!");
558
559 // Obtain the instruction descriptor from the opcode.
560 unsigned Opcode = MCI.getOpcode();
561 const MCInstrDesc &MCDesc = MCII.get(Opcode);
562 const MCSchedModel &SM = STI.getSchedModel();
563
564 // Then obtain the scheduling class information from the instruction.
565 // Allow InstrumentManager to override and use a different SchedClassID
566 unsigned SchedClassID = IM.getSchedClassID(MCII, MCI, IVec);
567 bool IsVariant = SM.getSchedClassDesc(SchedClassIdx: SchedClassID)->isVariant();
568
569 // Try to solve variant scheduling classes.
570 if (IsVariant) {
571 Expected<unsigned> VariantSchedClassIDOrErr =
572 getVariantSchedClassID(MCI, SchedClassID);
573 if (!VariantSchedClassIDOrErr) {
574 return VariantSchedClassIDOrErr.takeError();
575 }
576
577 SchedClassID = *VariantSchedClassIDOrErr;
578 }
579
580 // Check if this instruction is supported. Otherwise, report an error.
581 const MCSchedClassDesc &SCDesc = *SM.getSchedClassDesc(SchedClassIdx: SchedClassID);
582 if (SCDesc.NumMicroOps == MCSchedClassDesc::InvalidNumMicroOps) {
583 return make_error<InstructionError<MCInst>>(
584 Args: "found an unsupported instruction in the input assembly sequence", Args: MCI);
585 }
586
587 LLVM_DEBUG(dbgs() << "\n\t\tOpcode Name= " << MCII.getName(Opcode) << '\n');
588 LLVM_DEBUG(dbgs() << "\t\tSchedClassID=" << SchedClassID << '\n');
589 LLVM_DEBUG(dbgs() << "\t\tOpcode=" << Opcode << '\n');
590
591 // Create a new empty descriptor.
592 std::unique_ptr<InstrDesc> ID = std::make_unique<InstrDesc>();
593 ID->NumMicroOps = SCDesc.NumMicroOps;
594 ID->SchedClassID = SchedClassID;
595
596 bool IsCall = MCIA->isCall(Inst: MCI);
597 if (IsCall && FirstCallInst) {
598 // We don't correctly model calls.
599 WithColor::warning() << "found a call in the input assembly sequence.\n";
600 WithColor::note() << "call instructions are not correctly modeled. "
601 << "Assume a latency of " << CallLatency << "cy.\n";
602 FirstCallInst = false;
603 }
604
605 if (MCIA->isReturn(Inst: MCI) && FirstReturnInst) {
606 WithColor::warning() << "found a return instruction in the input"
607 << " assembly sequence.\n";
608 WithColor::note() << "program counter updates are ignored.\n";
609 FirstReturnInst = false;
610 }
611
612 initializeUsedResources(ID&: *ID, SCDesc, STI, ProcResourceMasks);
613 computeMaxLatency(ID&: *ID, SCDesc, STI, CallLatency, IsCall);
614
615 if (Error Err = verifyOperands(MCDesc, MCI))
616 return std::move(Err);
617
618 populateWrites(ID&: *ID, MCI, SchedClassID);
619 populateReads(ID&: *ID, MCI, SchedClassID);
620
621 LLVM_DEBUG(dbgs() << "\t\tMaxLatency=" << ID->MaxLatency << '\n');
622 LLVM_DEBUG(dbgs() << "\t\tNumMicroOps=" << ID->NumMicroOps << '\n');
623
624 // Validation check on the instruction descriptor.
625 if (Error Err = verifyInstrDesc(ID: *ID, MCI))
626 return std::move(Err);
627
628 // Now add the new descriptor.
629
630 if (IM.canCustomize(IVec)) {
631 IM.customize(IVec, Desc&: *ID);
632 return *CustomDescriptors.emplace_back(Args: std::move(ID));
633 }
634
635 bool IsVariadic = MCDesc.isVariadic();
636 if ((ID->IsRecyclable = !IsVariadic && !IsVariant)) {
637 auto DKey = std::make_pair(x: MCI.getOpcode(), y&: SchedClassID);
638 return *(Descriptors[DKey] = std::move(ID));
639 }
640
641 auto VDKey = std::make_pair(x: hashMCInst(MCI), y&: SchedClassID);
642 assert(
643 !VariantDescriptors.contains(VDKey) &&
644 "Expected VariantDescriptors to not already have a value for this key.");
645 return *(VariantDescriptors[VDKey] = std::move(ID));
646}
647
648Expected<const InstrDesc &>
649InstrBuilder::getOrCreateInstrDesc(const MCInst &MCI,
650 const SmallVector<Instrument *> &IVec) {
651 // Cache lookup using SchedClassID from Instrumentation
652 unsigned SchedClassID = IM.getSchedClassID(MCII, MCI, IVec);
653
654 auto DKey = std::make_pair(x: MCI.getOpcode(), y&: SchedClassID);
655 if (Descriptors.find_as(Val: DKey) != Descriptors.end())
656 return *Descriptors[DKey];
657
658 Expected<unsigned> VariantSchedClassIDOrErr =
659 getVariantSchedClassID(MCI, SchedClassID);
660 if (!VariantSchedClassIDOrErr) {
661 return VariantSchedClassIDOrErr.takeError();
662 }
663
664 SchedClassID = *VariantSchedClassIDOrErr;
665
666 auto VDKey = std::make_pair(x: hashMCInst(MCI), y&: SchedClassID);
667 auto It = VariantDescriptors.find(Val: VDKey);
668 if (It != VariantDescriptors.end())
669 return *It->second;
670
671 return createInstrDescImpl(MCI, IVec);
672}
673
674STATISTIC(NumVariantInst, "Number of MCInsts that doesn't have static Desc");
675
676Expected<std::unique_ptr<Instruction>>
677InstrBuilder::createInstruction(const MCInst &MCI,
678 const SmallVector<Instrument *> &IVec) {
679 Expected<const InstrDesc &> DescOrErr = IM.canCustomize(IVec)
680 ? createInstrDescImpl(MCI, IVec)
681 : getOrCreateInstrDesc(MCI, IVec);
682 if (!DescOrErr)
683 return DescOrErr.takeError();
684 const InstrDesc &D = *DescOrErr;
685 Instruction *NewIS = nullptr;
686 std::unique_ptr<Instruction> CreatedIS;
687 bool IsInstRecycled = false;
688
689 if (!D.IsRecyclable)
690 ++NumVariantInst;
691
692 if (D.IsRecyclable && InstRecycleCB) {
693 if (auto *I = InstRecycleCB(D)) {
694 NewIS = I;
695 NewIS->reset();
696 IsInstRecycled = true;
697 }
698 }
699 if (!IsInstRecycled) {
700 CreatedIS = std::make_unique<Instruction>(args: D, args: MCI.getOpcode());
701 NewIS = CreatedIS.get();
702 }
703
704 const MCInstrDesc &MCDesc = MCII.get(Opcode: MCI.getOpcode());
705 const MCSchedClassDesc &SCDesc =
706 *STI.getSchedModel().getSchedClassDesc(SchedClassIdx: D.SchedClassID);
707
708 NewIS->setMayLoad(MCDesc.mayLoad());
709 NewIS->setMayStore(MCDesc.mayStore());
710 NewIS->setHasSideEffects(MCDesc.hasUnmodeledSideEffects());
711 NewIS->setBeginGroup(SCDesc.BeginGroup);
712 NewIS->setEndGroup(SCDesc.EndGroup);
713 NewIS->setRetireOOO(SCDesc.RetireOOO);
714
715 // Check if this is a dependency breaking instruction.
716 APInt Mask;
717
718 bool IsZeroIdiom = false;
719 bool IsDepBreaking = false;
720 if (MCIA) {
721 unsigned ProcID = STI.getSchedModel().getProcessorID();
722 IsZeroIdiom = MCIA->isZeroIdiom(MI: MCI, Mask, CPUID: ProcID);
723 IsDepBreaking =
724 IsZeroIdiom || MCIA->isDependencyBreaking(MI: MCI, Mask, CPUID: ProcID);
725 if (MCIA->isOptimizableRegisterMove(MI: MCI, CPUID: ProcID))
726 NewIS->setOptimizableMove();
727 }
728
729 // Initialize Reads first.
730 MCPhysReg RegID = 0;
731 size_t Idx = 0U;
732 for (const ReadDescriptor &RD : D.Reads) {
733 if (!RD.isImplicitRead()) {
734 // explicit read.
735 const MCOperand &Op = MCI.getOperand(i: RD.OpIndex);
736 // Skip non-register operands.
737 if (!Op.isReg())
738 continue;
739 // Skip constant register operands.
740 if (MRI.isConstant(RegNo: Op.getReg()))
741 continue;
742 RegID = Op.getReg().id();
743 } else {
744 // Implicit read.
745 RegID = RD.RegisterID;
746 }
747
748 // Skip invalid register operands.
749 if (!RegID)
750 continue;
751
752 // Okay, this is a register operand. Create a ReadState for it.
753 ReadState *RS = nullptr;
754 if (IsInstRecycled && Idx < NewIS->getUses().size()) {
755 NewIS->getUses()[Idx] = ReadState(RD, RegID);
756 RS = &NewIS->getUses()[Idx++];
757 } else {
758 NewIS->getUses().emplace_back(Args: RD, Args&: RegID);
759 RS = &NewIS->getUses().back();
760 ++Idx;
761 }
762
763 if (IsDepBreaking) {
764 // A mask of all zeroes means: explicit input operands are not
765 // independent.
766 if (Mask.isZero()) {
767 if (!RD.isImplicitRead())
768 RS->setIndependentFromDef();
769 } else {
770 // Check if this register operand is independent according to `Mask`.
771 // Note that Mask may not have enough bits to describe all explicit and
772 // implicit input operands. If this register operand doesn't have a
773 // corresponding bit in Mask, then conservatively assume that it is
774 // dependent.
775 if (Mask.getBitWidth() > RD.UseIndex) {
776 // Okay. This map describe register use `RD.UseIndex`.
777 if (Mask[RD.UseIndex])
778 RS->setIndependentFromDef();
779 }
780 }
781 }
782 }
783 if (IsInstRecycled && Idx < NewIS->getUses().size())
784 NewIS->getUses().pop_back_n(NumItems: NewIS->getUses().size() - Idx);
785
786 // Early exit if there are no writes.
787 if (D.Writes.empty()) {
788 if (IsInstRecycled)
789 return llvm::make_error<RecycledInstErr>(Args&: NewIS);
790 else
791 return std::move(CreatedIS);
792 }
793
794 // Track register writes that implicitly clear the upper portion of the
795 // underlying super-registers using an APInt.
796 APInt WriteMask(D.Writes.size(), 0);
797
798 // Now query the MCInstrAnalysis object to obtain information about which
799 // register writes implicitly clear the upper portion of a super-register.
800 if (MCIA)
801 MCIA->clearsSuperRegisters(MRI, Inst: MCI, Writes&: WriteMask);
802
803 // Initialize writes.
804 unsigned WriteIndex = 0;
805 Idx = 0U;
806 for (const WriteDescriptor &WD : D.Writes) {
807 RegID = WD.isImplicitWrite() ? WD.RegisterID
808 : MCI.getOperand(i: WD.OpIndex).getReg().id();
809 // Check if this is a optional definition that references NoReg or a write
810 // to a constant register.
811 if ((WD.IsOptionalDef && !RegID) || MRI.isConstant(RegNo: RegID)) {
812 ++WriteIndex;
813 continue;
814 }
815
816 assert(RegID && "Expected a valid register ID!");
817 if (IsInstRecycled && Idx < NewIS->getDefs().size()) {
818 NewIS->getDefs()[Idx++] =
819 WriteState(WD, RegID,
820 /* ClearsSuperRegs */ WriteMask[WriteIndex],
821 /* WritesZero */ IsZeroIdiom);
822 } else {
823 NewIS->getDefs().emplace_back(Args: WD, Args&: RegID,
824 /* ClearsSuperRegs */ Args: WriteMask[WriteIndex],
825 /* WritesZero */ Args&: IsZeroIdiom);
826 ++Idx;
827 }
828 ++WriteIndex;
829 }
830 if (IsInstRecycled && Idx < NewIS->getDefs().size())
831 NewIS->getDefs().pop_back_n(NumItems: NewIS->getDefs().size() - Idx);
832
833 if (IsInstRecycled)
834 return llvm::make_error<RecycledInstErr>(Args&: NewIS);
835 else
836 return std::move(CreatedIS);
837}
838} // namespace mca
839} // namespace llvm
840