1//===-- llvm/MC/MCSchedule.h - Scheduling -----------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the classes used to describe a subtarget's machine model 11// for scheduling and other instruction cost heuristics. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_MC_MCSCHEDULE_H 16#define LLVM_MC_MCSCHEDULE_H 17 18#include "llvm/Support/DataTypes.h" 19#include <cassert> 20 21namespace llvm { 22 23struct InstrItinerary; 24 25/// Define a kind of processor resource that will be modeled by the scheduler. 26struct MCProcResourceDesc { 27#ifndef NDEBUG 28 const char *Name; 29#endif 30 unsigned NumUnits; // Number of resource of this kind 31 unsigned SuperIdx; // Index of the resources kind that contains this kind. 32 33 // Number of resources that may be buffered. 34 // 35 // Buffered resources (BufferSize != 0) may be consumed at some indeterminate 36 // cycle after dispatch. This should be used for out-of-order cpus when 37 // instructions that use this resource can be buffered in a reservaton 38 // station. 39 // 40 // Unbuffered resources (BufferSize == 0) always consume their resource some 41 // fixed number of cycles after dispatch. If a resource is unbuffered, then 42 // the scheduler will avoid scheduling instructions with conflicting resources 43 // in the same cycle. This is for in-order cpus, or the in-order portion of 44 // an out-of-order cpus. 45 int BufferSize; 46 47 bool operator==(const MCProcResourceDesc &Other) const { 48 return NumUnits == Other.NumUnits && SuperIdx == Other.SuperIdx 49 && BufferSize == Other.BufferSize; 50 } 51}; 52 53/// Identify one of the processor resource kinds consumed by a particular 54/// scheduling class for the specified number of cycles. 55struct MCWriteProcResEntry { 56 unsigned ProcResourceIdx; 57 unsigned Cycles; 58 59 bool operator==(const MCWriteProcResEntry &Other) const { 60 return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles; 61 } 62}; 63 64/// Specify the latency in cpu cycles for a particular scheduling class and def 65/// index. -1 indicates an invalid latency. Heuristics would typically consider 66/// an instruction with invalid latency to have infinite latency. Also identify 67/// the WriteResources of this def. When the operand expands to a sequence of 68/// writes, this ID is the last write in the sequence. 69struct MCWriteLatencyEntry { 70 int Cycles; 71 unsigned WriteResourceID; 72 73 bool operator==(const MCWriteLatencyEntry &Other) const { 74 return Cycles == Other.Cycles && WriteResourceID == Other.WriteResourceID; 75 } 76}; 77 78/// Specify the number of cycles allowed after instruction issue before a 79/// particular use operand reads its registers. This effectively reduces the 80/// write's latency. Here we allow negative cycles for corner cases where 81/// latency increases. This rule only applies when the entry's WriteResource 82/// matches the write's WriteResource. 83/// 84/// MCReadAdvanceEntries are sorted first by operand index (UseIdx), then by 85/// WriteResourceIdx. 86struct MCReadAdvanceEntry { 87 unsigned UseIdx; 88 unsigned WriteResourceID; 89 int Cycles; 90 91 bool operator==(const MCReadAdvanceEntry &Other) const { 92 return UseIdx == Other.UseIdx && WriteResourceID == Other.WriteResourceID 93 && Cycles == Other.Cycles; 94 } 95}; 96 97/// Summarize the scheduling resources required for an instruction of a 98/// particular scheduling class. 99/// 100/// Defined as an aggregate struct for creating tables with initializer lists. 101struct MCSchedClassDesc { 102 static const unsigned short InvalidNumMicroOps = UINT16_MAX; 103 static const unsigned short VariantNumMicroOps = UINT16_MAX - 1; 104 105#ifndef NDEBUG 106 const char* Name; 107#endif 108 unsigned short NumMicroOps; 109 bool BeginGroup; 110 bool EndGroup; 111 unsigned WriteProcResIdx; // First index into WriteProcResTable. 112 unsigned NumWriteProcResEntries; 113 unsigned WriteLatencyIdx; // First index into WriteLatencyTable. 114 unsigned NumWriteLatencyEntries; 115 unsigned ReadAdvanceIdx; // First index into ReadAdvanceTable. 116 unsigned NumReadAdvanceEntries; 117 118 bool isValid() const { 119 return NumMicroOps != InvalidNumMicroOps; 120 } 121 bool isVariant() const { 122 return NumMicroOps == VariantNumMicroOps; 123 } 124}; 125 126/// Machine model for scheduling, bundling, and heuristics. 127/// 128/// The machine model directly provides basic information about the 129/// microarchitecture to the scheduler in the form of properties. It also 130/// optionally refers to scheduler resource tables and itinerary 131/// tables. Scheduler resource tables model the latency and cost for each 132/// instruction type. Itinerary tables are an independent mechanism that 133/// provides a detailed reservation table describing each cycle of instruction 134/// execution. Subtargets may define any or all of the above categories of data 135/// depending on the type of CPU and selected scheduler. 136struct MCSchedModel { 137 // IssueWidth is the maximum number of instructions that may be scheduled in 138 // the same per-cycle group. 139 unsigned IssueWidth; 140 static const unsigned DefaultIssueWidth = 1; 141 142 // MicroOpBufferSize is the number of micro-ops that the processor may buffer 143 // for out-of-order execution. 144 // 145 // "0" means operations that are not ready in this cycle are not considered 146 // for scheduling (they go in the pending queue). Latency is paramount. This 147 // may be more efficient if many instructions are pending in a schedule. 148 // 149 // "1" means all instructions are considered for scheduling regardless of 150 // whether they are ready in this cycle. Latency still causes issue stalls, 151 // but we balance those stalls against other heuristics. 152 // 153 // "> 1" means the processor is out-of-order. This is a machine independent 154 // estimate of highly machine specific characteristics such as the register 155 // renaming pool and reorder buffer. 156 unsigned MicroOpBufferSize; 157 static const unsigned DefaultMicroOpBufferSize = 0; 158 159 // LoopMicroOpBufferSize is the number of micro-ops that the processor may 160 // buffer for optimized loop execution. More generally, this represents the 161 // optimal number of micro-ops in a loop body. A loop may be partially 162 // unrolled to bring the count of micro-ops in the loop body closer to this 163 // number. 164 unsigned LoopMicroOpBufferSize; 165 static const unsigned DefaultLoopMicroOpBufferSize = 0; 166 167 // LoadLatency is the expected latency of load instructions. 168 // 169 // If MinLatency >= 0, this may be overriden for individual load opcodes by 170 // InstrItinerary OperandCycles. 171 unsigned LoadLatency; 172 static const unsigned DefaultLoadLatency = 4; 173 174 // HighLatency is the expected latency of "very high latency" operations. 175 // See TargetInstrInfo::isHighLatencyDef(). 176 // By default, this is set to an arbitrarily high number of cycles 177 // likely to have some impact on scheduling heuristics. 178 // If MinLatency >= 0, this may be overriden by InstrItinData OperandCycles. 179 unsigned HighLatency; 180 static const unsigned DefaultHighLatency = 10; 181 182 // MispredictPenalty is the typical number of extra cycles the processor 183 // takes to recover from a branch misprediction. 184 unsigned MispredictPenalty; 185 static const unsigned DefaultMispredictPenalty = 10; 186 187 bool PostRAScheduler; // default value is false 188 189 bool CompleteModel; 190 191 unsigned ProcID; 192 const MCProcResourceDesc *ProcResourceTable; 193 const MCSchedClassDesc *SchedClassTable; 194 unsigned NumProcResourceKinds; 195 unsigned NumSchedClasses; 196 // Instruction itinerary tables used by InstrItineraryData. 197 friend class InstrItineraryData; 198 const InstrItinerary *InstrItineraries; 199 200 unsigned getProcessorID() const { return ProcID; } 201 202 /// Does this machine model include instruction-level scheduling. 203 bool hasInstrSchedModel() const { return SchedClassTable; } 204 205 /// Return true if this machine model data for all instructions with a 206 /// scheduling class (itinerary class or SchedRW list). 207 bool isComplete() const { return CompleteModel; } 208 209 unsigned getNumProcResourceKinds() const { 210 return NumProcResourceKinds; 211 } 212 213 const MCProcResourceDesc *getProcResource(unsigned ProcResourceIdx) const { 214 assert(hasInstrSchedModel() && "No scheduling machine model"); 215 216 assert(ProcResourceIdx < NumProcResourceKinds && "bad proc resource idx"); 217 return &ProcResourceTable[ProcResourceIdx]; 218 } 219 220 const MCSchedClassDesc *getSchedClassDesc(unsigned SchedClassIdx) const { 221 assert(hasInstrSchedModel() && "No scheduling machine model"); 222 223 assert(SchedClassIdx < NumSchedClasses && "bad scheduling class idx"); 224 return &SchedClassTable[SchedClassIdx]; 225 } 226 227 // /\brief Returns a default initialized model. Used for unknown processors. 228 static MCSchedModel GetDefaultSchedModel() { 229 MCSchedModel Ret = { DefaultIssueWidth, 230 DefaultMicroOpBufferSize, 231 DefaultLoopMicroOpBufferSize, 232 DefaultLoadLatency, 233 DefaultHighLatency, 234 DefaultMispredictPenalty, 235 false, 236 true, 237 0, 238 nullptr, 239 nullptr, 240 0, 241 0, 242 nullptr 243 }; 244 return Ret; 245 } 246}; 247 248} // End llvm namespace 249 250#endif 251