24#define DEBUG_TYPE "llvm-mca-instrbuilder"
36 : STI(sti), MCII(mcii), MRI(mri), MCIA(mcia), IM(
im), FirstCallInst(
true),
37 FirstReturnInst(
true), CallLatency(
cl) {
50 using ResourcePlusCycles = std::pair<uint64_t, ResourceUsage>;
66 APInt Buffers(NumProcResources, 0);
68 bool AllInOrderResources =
true;
69 bool AnyDispatchHazards =
false;
76 <<
"Ignoring invalid write of zero cycles on processor resource "
80 <<
" (write index #" <<
I <<
")\n";
87 AllInOrderResources =
false;
102 ID.MustIssueImmediately = AllInOrderResources && AnyDispatchHazards;
106 sort(Worklist, [](
const ResourcePlusCycles &
A,
const ResourcePlusCycles &
B) {
109 if (popcntA < popcntB)
111 if (popcntA > popcntB)
113 return A.first <
B.first;
118 uint64_t UnitsFromResourceGroups = 0;
122 ID.HasPartiallyOverlappingGroups =
false;
124 for (
unsigned I = 0,
E = Worklist.
size();
I <
E; ++
I) {
125 ResourcePlusCycles &
A = Worklist[
I];
126 if (!
A.second.size()) {
132 ID.Resources.emplace_back(
A);
136 UsedResourceUnits |=
A.first;
140 if (UnitsFromResourceGroups & NormalizedMask)
141 ID.HasPartiallyOverlappingGroups =
true;
143 UnitsFromResourceGroups |= NormalizedMask;
144 UsedResourceGroups |= (
A.first ^ NormalizedMask);
147 for (
unsigned J =
I + 1; J <
E; ++J) {
148 ResourcePlusCycles &
B = Worklist[J];
149 if ((NormalizedMask &
B.first) == NormalizedMask) {
150 B.second.CS.subtract(
A.second.size() - SuperResources[
A.first]);
174 for (ResourcePlusCycles &RPC :
ID.Resources) {
180 RPC.second.setReserved();
181 RPC.second.NumUnits = MaxResourceUnits;
187 for (
const std::pair<uint64_t, unsigned> &SR : SuperResources) {
188 for (
unsigned I = 1,
E = NumProcResources;
I <
E; ++
I) {
194 if (Mask != SR.first && ((Mask & SR.first) == SR.first))
200 ID.UsedProcResUnits = UsedResourceUnits;
201 ID.UsedProcResGroups = UsedResourceGroups;
204 for (
const std::pair<uint64_t, ResourceUsage> &R :
ID.Resources)
206 <<
"Reserved=" << R.second.isReserved() <<
", "
207 <<
"#Units=" << R.second.NumUnits <<
", "
208 <<
"cy=" << R.second.size() <<
'\n';
211 uint64_t Current = BufferIDs & (-BufferIDs);
213 BufferIDs ^= Current;
215 dbgs() <<
"\t\t Used Units=" <<
format_hex(
ID.UsedProcResUnits, 16) <<
'\n';
218 dbgs() <<
"\t\tHasPartiallyOverlappingGroups="
219 <<
ID.HasPartiallyOverlappingGroups <<
'\n';
229 ID.MaxLatency = CallLatency;
242 unsigned NumExplicitDefs = MCDesc.
getNumDefs();
249 if (NumExplicitDefs) {
251 "Expected more register operand definitions.", MCI);
258 std::string Message =
259 "expected a register operand for an optional definition. Instruction "
260 "has not been correctly analyzed.";
268void InstrBuilder::populateWrites(InstrDesc &
ID,
const MCInst &MCI,
269 unsigned SchedClassID) {
317 unsigned NumExplicitDefs = MCDesc.
getNumDefs();
320 unsigned TotalDefs = NumExplicitDefs + NumImplicitDefs;
325 ID.Writes.resize(TotalDefs + NumVariadicOps);
329 unsigned CurrentDef = 0;
332 for (; i < MCI.
getNumOperands() && CurrentDef < NumExplicitDefs; ++i) {
337 if (MCDesc.
operands()[CurrentDef].isOptionalDef()) {
338 OptionalDefIdx = CurrentDef++;
341 if (
MRI.isConstant(
Op.getReg())) {
346 WriteDescriptor &
Write =
ID.Writes[CurrentDef];
348 if (CurrentDef < NumWriteLatencyEntries) {
349 const MCWriteLatencyEntry &WLE =
350 *STI.getWriteLatencyEntry(&SCDesc, CurrentDef);
353 WLE.Cycles < 0 ?
ID.MaxLatency :
static_cast<unsigned>(WLE.Cycles);
354 Write.SClassOrWriteResourceID = WLE.WriteResourceID;
358 Write.SClassOrWriteResourceID = 0;
360 Write.IsOptionalDef =
false;
362 dbgs() <<
"\t\t[Def] OpIdx=" <<
Write.OpIndex
363 <<
", Latency=" <<
Write.Latency
364 <<
", WriteResourceID=" <<
Write.SClassOrWriteResourceID <<
'\n';
369 assert(CurrentDef == NumExplicitDefs &&
370 "Expected more register operand definitions.");
371 for (CurrentDef = 0; CurrentDef < NumImplicitDefs; ++CurrentDef) {
372 unsigned Index = NumExplicitDefs + CurrentDef;
374 Write.OpIndex = ~CurrentDef;
376 if (Index < NumWriteLatencyEntries) {
377 const MCWriteLatencyEntry &WLE =
378 *STI.getWriteLatencyEntry(&SCDesc, Index);
381 WLE.Cycles < 0 ?
ID.MaxLatency :
static_cast<unsigned>(WLE.Cycles);
382 Write.SClassOrWriteResourceID = WLE.WriteResourceID;
386 Write.SClassOrWriteResourceID = 0;
389 Write.IsOptionalDef =
false;
390 assert(
Write.RegisterID != 0 &&
"Expected a valid phys register!");
392 dbgs() <<
"\t\t[Def][I] OpIdx=" << ~Write.OpIndex
393 <<
", PhysReg=" << MRI.getName(
Write.RegisterID)
394 <<
", Latency=" <<
Write.Latency
395 <<
", WriteResourceID=" <<
Write.SClassOrWriteResourceID <<
'\n';
400 WriteDescriptor &
Write =
ID.Writes[NumExplicitDefs + NumImplicitDefs];
401 Write.OpIndex = OptionalDefIdx;
404 Write.SClassOrWriteResourceID = 0;
405 Write.IsOptionalDef =
true;
407 dbgs() <<
"\t\t[Def][O] OpIdx=" <<
Write.OpIndex
408 <<
", Latency=" <<
Write.Latency
409 <<
", WriteResourceID=" <<
Write.SClassOrWriteResourceID <<
'\n';
417 CurrentDef = NumExplicitDefs + NumImplicitDefs + MCDesc.
hasOptionalDef();
419 I < NumVariadicOps && !AssumeUsesOnly; ++
I, ++
OpIndex) {
423 if (MRI.isConstant(
Op.getReg()))
426 WriteDescriptor &
Write =
ID.Writes[CurrentDef];
430 Write.SClassOrWriteResourceID = 0;
431 Write.IsOptionalDef =
false;
434 dbgs() <<
"\t\t[Def][V] OpIdx=" <<
Write.OpIndex
435 <<
", Latency=" <<
Write.Latency
436 <<
", WriteResourceID=" <<
Write.SClassOrWriteResourceID <<
'\n';
440 ID.Writes.resize(CurrentDef);
443void InstrBuilder::populateReads(
InstrDesc &
ID,
const MCInst &MCI,
444 unsigned SchedClassID) {
445 const MCInstrDesc &MCDesc = MCII.get(MCI.getOpcode());
446 unsigned NumExplicitUses = MCDesc.
getNumOperands() - MCDesc.getNumDefs();
447 unsigned NumImplicitUses = MCDesc.implicit_uses().size();
449 if (MCDesc.hasOptionalDef())
451 unsigned NumVariadicOps = MCI.getNumOperands() - MCDesc.getNumOperands();
452 unsigned TotalUses = NumExplicitUses + NumImplicitUses + NumVariadicOps;
453 ID.Reads.resize(TotalUses);
454 unsigned CurrentUse = 0;
455 for (
unsigned I = 0,
OpIndex = MCDesc.getNumDefs();
I < NumExplicitUses;
457 const MCOperand &
Op = MCI.getOperand(
OpIndex);
460 if (MRI.isConstant(
Op.getReg()))
463 ReadDescriptor &
Read =
ID.Reads[CurrentUse];
466 Read.SchedClassID = SchedClassID;
469 <<
", UseIndex=" <<
Read.UseIndex <<
'\n');
474 for (
unsigned I = 0;
I < NumImplicitUses; ++
I) {
475 ReadDescriptor &
Read =
ID.Reads[CurrentUse +
I];
477 Read.UseIndex = NumExplicitUses +
I;
478 Read.RegisterID = MCDesc.implicit_uses()[
I];
479 if (MRI.isConstant(
Read.RegisterID))
481 Read.SchedClassID = SchedClassID;
483 <<
", UseIndex=" <<
Read.UseIndex <<
", RegisterID="
484 << MRI.getName(
Read.RegisterID) <<
'\n');
487 CurrentUse += NumImplicitUses;
489 bool AssumeDefsOnly = MCDesc.variadicOpsAreDefs();
490 for (
unsigned I = 0,
OpIndex = MCDesc.getNumOperands();
491 I < NumVariadicOps && !AssumeDefsOnly; ++
I, ++
OpIndex) {
492 const MCOperand &
Op = MCI.getOperand(
OpIndex);
496 ReadDescriptor &
Read =
ID.Reads[CurrentUse];
498 Read.UseIndex = NumExplicitUses + NumImplicitUses +
I;
499 Read.SchedClassID = SchedClassID;
502 <<
", UseIndex=" <<
Read.UseIndex <<
'\n');
505 ID.Reads.resize(CurrentUse);
523 return InstructionHash;
526Error InstrBuilder::verifyInstrDesc(
const InstrDesc &
ID,
527 const MCInst &MCI)
const {
528 if (
ID.NumMicroOps != 0)
531 bool UsesBuffers =
ID.UsedBuffers;
532 bool UsesResources = !
ID.Resources.empty();
533 if (!UsesBuffers && !UsesResources)
538 StringRef Message =
"found an inconsistent instruction that decodes to zero "
539 "opcodes and that consumes scheduler resources.";
543Expected<unsigned> InstrBuilder::getVariantSchedClassID(
const MCInst &MCI,
544 unsigned SchedClassID) {
547 while (SchedClassID && SM.getSchedClassDesc(SchedClassID)->isVariant())
553 "unable to resolve scheduling class for write variant.", MCI);
559Expected<const InstrDesc &>
560InstrBuilder::createInstrDescImpl(
const MCInst &MCI,
562 assert(STI.getSchedModel().hasInstrSchedModel() &&
563 "Itineraries are not yet supported!");
566 unsigned short Opcode = MCI.getOpcode();
567 const MCInstrDesc &MCDesc = MCII.get(Opcode);
568 const MCSchedModel &SM = STI.getSchedModel();
572 unsigned SchedClassID = IM.getSchedClassID(MCII, MCI, IVec);
573 bool IsVariant = SM.getSchedClassDesc(SchedClassID)->isVariant();
577 Expected<unsigned> VariantSchedClassIDOrErr =
578 getVariantSchedClassID(MCI, SchedClassID);
579 if (!VariantSchedClassIDOrErr) {
580 return VariantSchedClassIDOrErr.takeError();
583 SchedClassID = *VariantSchedClassIDOrErr;
587 const MCSchedClassDesc &SCDesc = *SM.getSchedClassDesc(SchedClassID);
590 "found an unsupported instruction in the input assembly sequence", MCI);
593 LLVM_DEBUG(
dbgs() <<
"\n\t\tOpcode Name= " << MCII.getName(Opcode) <<
'\n');
594 LLVM_DEBUG(
dbgs() <<
"\t\tSchedClassID=" << SchedClassID <<
'\n');
598 std::unique_ptr<InstrDesc>
ID = std::make_unique<InstrDesc>();
599 ID->NumMicroOps = SCDesc.NumMicroOps;
600 ID->SchedClassID = SchedClassID;
602 bool IsCall = MCIA->isCall(MCI);
603 if (IsCall && FirstCallInst) {
607 <<
"Assume a latency of " << CallLatency <<
"cy.\n";
608 FirstCallInst =
false;
611 if (MCIA->isReturn(MCI) && FirstReturnInst) {
613 <<
" assembly sequence.\n";
615 FirstReturnInst =
false;
622 return std::move(Err);
624 populateWrites(*
ID, MCI, SchedClassID);
625 populateReads(*
ID, MCI, SchedClassID);
631 if (
Error Err = verifyInstrDesc(*
ID, MCI))
632 return std::move(Err);
636 if (IM.canCustomize(IVec)) {
637 IM.customize(IVec, *
ID);
638 return *CustomDescriptors.emplace_back(std::move(
ID));
641 bool IsVariadic = MCDesc.isVariadic();
642 if ((
ID->IsRecyclable = !IsVariadic && !IsVariant)) {
643 auto DKey = std::make_pair(MCI.getOpcode(), SchedClassID);
644 return *(Descriptors[DKey] = std::move(
ID));
647 auto VDKey = std::make_pair(
hashMCInst(MCI), SchedClassID);
649 !VariantDescriptors.contains(VDKey) &&
650 "Expected VariantDescriptors to not already have a value for this key.");
651 return *(VariantDescriptors[VDKey] = std::move(
ID));
654Expected<const InstrDesc &>
655InstrBuilder::getOrCreateInstrDesc(
const MCInst &MCI,
658 unsigned SchedClassID = IM.getSchedClassID(MCII, MCI, IVec);
660 auto DKey = std::make_pair(MCI.getOpcode(), SchedClassID);
661 if (Descriptors.find_as(DKey) != Descriptors.end())
662 return *Descriptors[DKey];
664 Expected<unsigned> VariantSchedClassIDOrErr =
665 getVariantSchedClassID(MCI, SchedClassID);
666 if (!VariantSchedClassIDOrErr) {
667 return VariantSchedClassIDOrErr.takeError();
670 SchedClassID = *VariantSchedClassIDOrErr;
672 auto VDKey = std::make_pair(
hashMCInst(MCI), SchedClassID);
673 auto It = VariantDescriptors.find(VDKey);
674 if (It != VariantDescriptors.end())
677 return createInstrDescImpl(MCI, IVec);
680STATISTIC(NumVariantInst,
"Number of MCInsts that doesn't have static Desc");
686 ? createInstrDescImpl(MCI, IVec)
687 : getOrCreateInstrDesc(MCI, IVec);
692 std::unique_ptr<Instruction> CreatedIS;
693 bool IsInstRecycled =
false;
698 if (
D.IsRecyclable && InstRecycleCB) {
699 if (
auto *
I = InstRecycleCB(
D)) {
702 IsInstRecycled =
true;
705 if (!IsInstRecycled) {
706 CreatedIS = std::make_unique<Instruction>(
D, MCI.
getOpcode());
707 NewIS = CreatedIS.get();
712 *STI.getSchedModel().getSchedClassDesc(
D.SchedClassID);
724 bool IsZeroIdiom =
false;
725 bool IsDepBreaking =
false;
727 unsigned ProcID = STI.getSchedModel().getProcessorID();
728 IsZeroIdiom = MCIA->isZeroIdiom(MCI, Mask, ProcID);
730 IsZeroIdiom || MCIA->isDependencyBreaking(MCI, Mask, ProcID);
731 if (MCIA->isOptimizableRegisterMove(MCI, ProcID))
745 RegID =
Op.getReg().id();
757 if (IsInstRecycled && Idx < NewIS->getUses().
size()) {
761 NewIS->
getUses().emplace_back(RD, RegID);
778 if (Mask.getBitWidth() > RD.
UseIndex) {
786 if (IsInstRecycled && Idx < NewIS->getUses().
size())
790 if (
D.Writes.empty()) {
794 return std::move(CreatedIS);
799 APInt WriteMask(
D.Writes.size(), 0);
804 MCIA->clearsSuperRegisters(MRI, MCI, WriteMask);
807 unsigned WriteIndex = 0;
819 assert(RegID &&
"Expected a valid register ID!");
820 if (IsInstRecycled && Idx < NewIS->getDefs().
size()) {
823 WriteMask[WriteIndex],
826 NewIS->
getDefs().emplace_back(WD, RegID,
827 WriteMask[WriteIndex],
833 if (IsInstRecycled && Idx < NewIS->getDefs().
size())
839 return std::move(CreatedIS);
unsigned const MachineRegisterInfo * MRI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseMap class.
A builder class for instructions that are statically analyzed by llvm-mca.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
uint64_t getZExtValue() const
Get zero extended value.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Subclass of Error for the sole purpose of identifying the success path in the type system.
Lightweight error class with error context and mandatory checking.
Tagged union holding either a T or a Error.
Error takeError()
Take ownership of the stored error.
Instances of this class represent a single low-level machine instruction.
unsigned getNumOperands() const
unsigned getFlags() const
unsigned getOpcode() const
const MCOperand & getOperand(unsigned i) const
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
ArrayRef< MCOperandInfo > operands() const
bool mayStore() const
Return true if this instruction could possibly modify memory.
bool mayLoad() const
Return true if this instruction could possibly read memory.
bool hasOptionalDef() const
Set if this instruction has an optional definition, e.g.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
bool variadicOpsAreDefs() const
Return true if variadic operands of this instruction are definitions.
ArrayRef< MCPhysReg > implicit_defs() const
Return a list of registers that are potentially written by any instance of this machine instruction.
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by other flags.
Interface to description of machine instruction set.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Instances of this class represent operands of the MCInst class.
MCRegister getReg() const
Returns the register number.
MCRegisterInfo base class - We assume that the target defines a static array of MCRegisterDesc object...
constexpr unsigned id() const
Generic base class for all target subtargets.
virtual unsigned resolveVariantSchedClass(unsigned SchedClass, const MCInst *MI, const MCInstrInfo *MCII, unsigned CPUID) const
Resolve a variant scheduling class for the given MCInst and CPU.
const MCWriteProcResEntry * getWriteProcResBegin(const MCSchedClassDesc *SC) const
Return an iterator at the first process resource consumed by the given scheduling class.
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget's CPU.
reference emplace_back(ArgTypes &&... Args)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
static LLVM_ABI raw_ostream & warning()
Convenience method for printing "warning: " to stderr.
static LLVM_ABI raw_ostream & note()
Convenience method for printing "note: " to stderr.
An opaque object representing a hash code.
LLVM_ABI Expected< std::unique_ptr< Instruction > > createInstruction(const MCInst &MCI, const SmallVector< Instrument * > &IVec)
void setEndGroup(bool newVal)
void setRetireOOO(bool newVal)
SmallVectorImpl< WriteState > & getDefs()
void setBeginGroup(bool newVal)
SmallVectorImpl< ReadState > & getUses()
void setHasSideEffects(bool newVal)
void setMayStore(bool newVal)
void setOptimizableMove()
void setMayLoad(bool newVal)
An instruction propagated through the simulated instruction pipeline.
This class allows targets to optionally customize the logic that resolves scheduling class IDs.
Tracks register operand latency in cycles.
void setIndependentFromDef()
Tracks uses of a register definition (e.g.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This namespace contains all of the command line option processing machinery.
static void computeMaxLatency(InstrDesc &ID, const MCSchedClassDesc &SCDesc, const MCSubtargetInfo &STI, unsigned CallLatency, bool IsCall)
char InstructionError< T >::ID
hash_code hashMCInst(const MCInst &MCI)
static void initializeUsedResources(InstrDesc &ID, const MCSchedClassDesc &SCDesc, const MCSubtargetInfo &STI, ArrayRef< uint64_t > ProcResourceMasks)
hash_code hashMCOperand(const MCOperand &MCO)
LLVM_ABI void computeProcResourceMasks(const MCSchedModel &SM, MutableArrayRef< uint64_t > Masks)
Populates vector Masks with processor resource masks.
unsigned getResourceStateIndex(uint64_t Mask)
static Error verifyOperands(const MCInstrDesc &MCDesc, const MCInst &MCI)
This is an optimization pass for GlobalISel generic memory operations.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
FormattedNumber format_hex(uint64_t N, unsigned Width, bool Upper=false)
format_hex - Output N as a fixed width hexadecimal.
Error make_error(ArgTs &&... Args)
Make a Error instance representing failure using the given error info type.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
DWARFExpression::Operation Op
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
T bit_floor(T Value)
Returns the largest integral power of two no greater than Value if Value is nonzero.
int popcount(T Value) noexcept
Count the number of set bits in a value.
Define a kind of processor resource that will be modeled by the scheduler.
Summarize the scheduling resources required for an instruction of a particular scheduling class.
static const unsigned short InvalidNumMicroOps
uint16_t NumWriteLatencyEntries
uint16_t NumWriteProcResEntries
Machine model for scheduling, bundling, and heuristics.
const MCSchedClassDesc * getSchedClassDesc(unsigned SchedClassIdx) const
unsigned getProcessorID() const
unsigned getNumProcResourceKinds() const
static LLVM_ABI int computeInstrLatency(const MCSubtargetInfo &STI, const MCSchedClassDesc &SCDesc)
Returns the latency value for the scheduling class.
const MCProcResourceDesc * getProcResource(unsigned ProcResourceIdx) const
StringRef getSchedClassName(unsigned SchedClassIdx) const
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
uint16_t ReleaseAtCycle
Cycle at which the resource will be released by an instruction, relatively to the cycle in which the ...
An instruction descriptor.
A register read descriptor.
bool isImplicitRead() const
Helper used by class InstrDesc to describe how hardware resources are used.
A register write descriptor.
bool isImplicitWrite() const