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