LLVM  13.0.0git
MCInstrItineraries.h
Go to the documentation of this file.
1 //===- llvm/MC/MCInstrItineraries.h - Scheduling ----------------*- 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 // This file describes the structures used for instruction
10 // itineraries, stages, and operand reads/writes. This is used by
11 // schedulers to determine instruction stages and latencies.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_MC_MCINSTRITINERARIES_H
16 #define LLVM_MC_MCINSTRITINERARIES_H
17 
18 #include "llvm/MC/MCSchedule.h"
19 #include <algorithm>
20 
21 namespace llvm {
22 
23 //===----------------------------------------------------------------------===//
24 /// These values represent a non-pipelined step in
25 /// the execution of an instruction. Cycles represents the number of
26 /// discrete time slots needed to complete the stage. Units represent
27 /// the choice of functional units that can be used to complete the
28 /// stage. Eg. IntUnit1, IntUnit2. NextCycles indicates how many
29 /// cycles should elapse from the start of this stage to the start of
30 /// the next stage in the itinerary. A value of -1 indicates that the
31 /// next stage should start immediately after the current one.
32 /// For example:
33 ///
34 /// { 1, x, -1 }
35 /// indicates that the stage occupies FU x for 1 cycle and that
36 /// the next stage starts immediately after this one.
37 ///
38 /// { 2, x|y, 1 }
39 /// indicates that the stage occupies either FU x or FU y for 2
40 /// consecutive cycles and that the next stage starts one cycle
41 /// after this stage starts. That is, the stage requirements
42 /// overlap in time.
43 ///
44 /// { 1, x, 0 }
45 /// indicates that the stage occupies FU x for 1 cycle and that
46 /// the next stage starts in this same cycle. This can be used to
47 /// indicate that the instruction requires multiple stages at the
48 /// same time.
49 ///
50 /// FU reservation can be of two different kinds:
51 /// - FUs which instruction actually requires
52 /// - FUs which instruction just reserves. Reserved unit is not available for
53 /// execution of other instruction. However, several instructions can reserve
54 /// the same unit several times.
55 /// Such two types of units reservation is used to model instruction domain
56 /// change stalls, FUs using the same resource (e.g. same register file), etc.
57 
58 struct InstrStage {
60  Required = 0,
62  };
63 
64  /// Bitmask representing a set of functional units.
65  typedef uint64_t FuncUnits;
66 
67  unsigned Cycles_; ///< Length of stage in machine cycles
68  FuncUnits Units_; ///< Choice of functional units
69  int NextCycles_; ///< Number of machine cycles to next stage
70  ReservationKinds Kind_; ///< Kind of the FU reservation
71 
72  /// Returns the number of cycles the stage is occupied.
73  unsigned getCycles() const {
74  return Cycles_;
75  }
76 
77  /// Returns the choice of FUs.
78  FuncUnits getUnits() const {
79  return Units_;
80  }
81 
83  return Kind_;
84  }
85 
86  /// Returns the number of cycles from the start of this stage to the
87  /// start of the next stage in the itinerary
88  unsigned getNextCycles() const {
89  return (NextCycles_ >= 0) ? (unsigned)NextCycles_ : Cycles_;
90  }
91 };
92 
93 //===----------------------------------------------------------------------===//
94 /// An itinerary represents the scheduling information for an instruction.
95 /// This includes a set of stages occupied by the instruction and the pipeline
96 /// cycle in which operands are read and written.
97 ///
99  int16_t NumMicroOps; ///< # of micro-ops, -1 means it's variable
100  uint16_t FirstStage; ///< Index of first stage in itinerary
101  uint16_t LastStage; ///< Index of last + 1 stage in itinerary
102  uint16_t FirstOperandCycle; ///< Index of first operand rd/wr
103  uint16_t LastOperandCycle; ///< Index of last + 1 operand rd/wr
104 };
105 
106 //===----------------------------------------------------------------------===//
107 /// Itinerary data supplied by a subtarget to be used by a target.
108 ///
110 public:
112  MCSchedModel::GetDefaultSchedModel(); ///< Basic machine properties.
113  const InstrStage *Stages = nullptr; ///< Array of stages selected
114  const unsigned *OperandCycles = nullptr; ///< Array of operand cycles selected
115  const unsigned *Forwardings = nullptr; ///< Array of pipeline forwarding paths
117  nullptr; ///< Array of itineraries selected
118 
119  InstrItineraryData() = default;
121  const unsigned *OS, const unsigned *F)
122  : SchedModel(SM), Stages(S), OperandCycles(OS), Forwardings(F),
123  Itineraries(SchedModel.InstrItineraries) {}
124 
125  /// Returns true if there are no itineraries.
126  bool isEmpty() const { return Itineraries == nullptr; }
127 
128  /// Returns true if the index is for the end marker itinerary.
129  bool isEndMarker(unsigned ItinClassIndx) const {
130  return ((Itineraries[ItinClassIndx].FirstStage == UINT16_MAX) &&
131  (Itineraries[ItinClassIndx].LastStage == UINT16_MAX));
132  }
133 
134  /// Return the first stage of the itinerary.
135  const InstrStage *beginStage(unsigned ItinClassIndx) const {
136  unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage;
137  return Stages + StageIdx;
138  }
139 
140  /// Return the last+1 stage of the itinerary.
141  const InstrStage *endStage(unsigned ItinClassIndx) const {
142  unsigned StageIdx = Itineraries[ItinClassIndx].LastStage;
143  return Stages + StageIdx;
144  }
145 
146  /// Return the total stage latency of the given class. The latency is
147  /// the maximum completion time for any stage in the itinerary. If no stages
148  /// exist, it defaults to one cycle.
149  unsigned getStageLatency(unsigned ItinClassIndx) const {
150  // If the target doesn't provide itinerary information, use a simple
151  // non-zero default value for all instructions.
152  if (isEmpty())
153  return 1;
154 
155  // Calculate the maximum completion time for any stage.
156  unsigned Latency = 0, StartCycle = 0;
157  for (const InstrStage *IS = beginStage(ItinClassIndx),
158  *E = endStage(ItinClassIndx); IS != E; ++IS) {
159  Latency = std::max(Latency, StartCycle + IS->getCycles());
160  StartCycle += IS->getNextCycles();
161  }
162  return Latency;
163  }
164 
165  /// Return the cycle for the given class and operand. Return -1 if no
166  /// cycle is specified for the operand.
167  int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const {
168  if (isEmpty())
169  return -1;
170 
171  unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle;
172  unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle;
173  if ((FirstIdx + OperandIdx) >= LastIdx)
174  return -1;
175 
176  return (int)OperandCycles[FirstIdx + OperandIdx];
177  }
178 
179  /// Return true if there is a pipeline forwarding between instructions
180  /// of itinerary classes DefClass and UseClasses so that value produced by an
181  /// instruction of itinerary class DefClass, operand index DefIdx can be
182  /// bypassed when it's read by an instruction of itinerary class UseClass,
183  /// operand index UseIdx.
184  bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx,
185  unsigned UseClass, unsigned UseIdx) const {
186  unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle;
187  unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle;
188  if ((FirstDefIdx + DefIdx) >= LastDefIdx)
189  return false;
190  if (Forwardings[FirstDefIdx + DefIdx] == 0)
191  return false;
192 
193  unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle;
194  unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle;
195  if ((FirstUseIdx + UseIdx) >= LastUseIdx)
196  return false;
197 
198  return Forwardings[FirstDefIdx + DefIdx] ==
199  Forwardings[FirstUseIdx + UseIdx];
200  }
201 
202  /// Compute and return the use operand latency of a given itinerary
203  /// class and operand index if the value is produced by an instruction of the
204  /// specified itinerary class and def operand index.
205  int getOperandLatency(unsigned DefClass, unsigned DefIdx,
206  unsigned UseClass, unsigned UseIdx) const {
207  if (isEmpty())
208  return -1;
209 
210  int DefCycle = getOperandCycle(DefClass, DefIdx);
211  if (DefCycle == -1)
212  return -1;
213 
214  int UseCycle = getOperandCycle(UseClass, UseIdx);
215  if (UseCycle == -1)
216  return -1;
217 
218  UseCycle = DefCycle - UseCycle + 1;
219  if (UseCycle > 0 &&
220  hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx))
221  // FIXME: This assumes one cycle benefit for every pipeline forwarding.
222  --UseCycle;
223  return UseCycle;
224  }
225 
226  /// Return the number of micro-ops that the given class decodes to.
227  /// Return -1 for classes that require dynamic lookup via TargetInstrInfo.
228  int getNumMicroOps(unsigned ItinClassIndx) const {
229  if (isEmpty())
230  return 1;
231  return Itineraries[ItinClassIndx].NumMicroOps;
232  }
233 };
234 
235 } // end namespace llvm
236 
237 #endif // LLVM_MC_MCINSTRITINERARIES_H
llvm::InstrStage::getCycles
unsigned getCycles() const
Returns the number of cycles the stage is occupied.
Definition: MCInstrItineraries.h:73
llvm
Definition: AllocatorList.h:23
llvm::Latency
@ Latency
Definition: SIMachineScheduler.h:32
llvm::InstrItineraryData::getNumMicroOps
int getNumMicroOps(unsigned ItinClassIndx) const
Return the number of micro-ops that the given class decodes to.
Definition: MCInstrItineraries.h:228
llvm::InstrStage::Reserved
@ Reserved
Definition: MCInstrItineraries.h:61
llvm::InstrItineraryData::Stages
const InstrStage * Stages
Array of stages selected.
Definition: MCInstrItineraries.h:113
llvm::InstrStage::Kind_
ReservationKinds Kind_
Kind of the FU reservation.
Definition: MCInstrItineraries.h:70
llvm::InstrStage::Cycles_
unsigned Cycles_
Length of stage in machine cycles.
Definition: MCInstrItineraries.h:67
llvm::InstrItineraryData::getOperandCycle
int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const
Return the cycle for the given class and operand.
Definition: MCInstrItineraries.h:167
llvm::InstrItineraryData::endStage
const InstrStage * endStage(unsigned ItinClassIndx) const
Return the last+1 stage of the itinerary.
Definition: MCInstrItineraries.h:141
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::InstrStage::ReservationKinds
ReservationKinds
Definition: MCInstrItineraries.h:59
llvm::InstrStage::Required
@ Required
Definition: MCInstrItineraries.h:60
llvm::InstrItineraryData::getOperandLatency
int getOperandLatency(unsigned DefClass, unsigned DefIdx, unsigned UseClass, unsigned UseIdx) const
Compute and return the use operand latency of a given itinerary class and operand index if the value ...
Definition: MCInstrItineraries.h:205
llvm::InstrItinerary
An itinerary represents the scheduling information for an instruction.
Definition: MCInstrItineraries.h:98
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::InstrItineraryData::InstrItineraryData
InstrItineraryData(const MCSchedModel &SM, const InstrStage *S, const unsigned *OS, const unsigned *F)
Definition: MCInstrItineraries.h:120
llvm::InstrItineraryData::Itineraries
const InstrItinerary * Itineraries
Array of itineraries selected.
Definition: MCInstrItineraries.h:116
llvm::InstrStage::FuncUnits
uint64_t FuncUnits
Bitmask representing a set of functional units.
Definition: MCInstrItineraries.h:65
llvm::InstrItinerary::NumMicroOps
int16_t NumMicroOps
Definition: MCInstrItineraries.h:99
llvm::InstrItineraryData::isEndMarker
bool isEndMarker(unsigned ItinClassIndx) const
Returns true if the index is for the end marker itinerary.
Definition: MCInstrItineraries.h:129
llvm::InstrStage::getUnits
FuncUnits getUnits() const
Returns the choice of FUs.
Definition: MCInstrItineraries.h:78
MCSchedule.h
llvm::InstrStage::Units_
FuncUnits Units_
Choice of functional units.
Definition: MCInstrItineraries.h:68
llvm::InstrStage::getNextCycles
unsigned getNextCycles() const
Returns the number of cycles from the start of this stage to the start of the next stage in the itine...
Definition: MCInstrItineraries.h:88
llvm::InstrItinerary::FirstStage
uint16_t FirstStage
Index of first stage in itinerary.
Definition: MCInstrItineraries.h:100
llvm::InstrStage::NextCycles_
int NextCycles_
Number of machine cycles to next stage.
Definition: MCInstrItineraries.h:69
llvm::InstrItineraryData::hasPipelineForwarding
bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx, unsigned UseClass, unsigned UseIdx) const
Return true if there is a pipeline forwarding between instructions of itinerary classes DefClass and ...
Definition: MCInstrItineraries.h:184
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::InstrStage
These values represent a non-pipelined step in the execution of an instruction.
Definition: MCInstrItineraries.h:58
llvm::MCSchedModel::GetDefaultSchedModel
static const MCSchedModel & GetDefaultSchedModel()
Returns the default initialized model.
Definition: MCSchedule.h:380
llvm::InstrItineraryData::getStageLatency
unsigned getStageLatency(unsigned ItinClassIndx) const
Return the total stage latency of the given class.
Definition: MCInstrItineraries.h:149
uint16_t
llvm::InstrItineraryData::OperandCycles
const unsigned * OperandCycles
Array of operand cycles selected.
Definition: MCInstrItineraries.h:114
llvm::InstrItineraryData::InstrItineraryData
InstrItineraryData()=default
llvm::InstrStage::getReservationKind
ReservationKinds getReservationKind() const
Definition: MCInstrItineraries.h:82
llvm::InstrItinerary::FirstOperandCycle
uint16_t FirstOperandCycle
Index of first operand rd/wr.
Definition: MCInstrItineraries.h:102
llvm::MCSchedModel
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:245
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::InstrItinerary::LastOperandCycle
uint16_t LastOperandCycle
Index of last + 1 operand rd/wr.
Definition: MCInstrItineraries.h:103
llvm::InstrItinerary::LastStage
uint16_t LastStage
Index of last + 1 stage in itinerary.
Definition: MCInstrItineraries.h:101
llvm::InstrItineraryData::beginStage
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
Definition: MCInstrItineraries.h:135
llvm::InstrItineraryData::isEmpty
bool isEmpty() const
Returns true if there are no itineraries.
Definition: MCInstrItineraries.h:126
llvm::InstrItineraryData
Itinerary data supplied by a subtarget to be used by a target.
Definition: MCInstrItineraries.h:109
llvm::InstrItineraryData::SchedModel
MCSchedModel SchedModel
Basic machine properties.
Definition: MCInstrItineraries.h:111
llvm::InstrItineraryData::Forwardings
const unsigned * Forwardings
Array of pipeline forwarding paths.
Definition: MCInstrItineraries.h:115