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/// 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///      consecutive 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  /// \brief Returns the number of cycles the stage is occupied.
71  unsigned getCycles() const {
72    return Cycles_;
73  }
74
75  /// \brief Returns the choice of FUs.
76  unsigned getUnits() const {
77    return Units_;
78  }
79
80  ReservationKinds getReservationKind() const {
81    return Kind_;
82  }
83
84  /// \brief Returns the number of cycles from the start of this stage to the
85  /// 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/// An itinerary represents the scheduling information for an instruction.
94/// This includes a set of stages occupied by the instruction and the pipeline
95/// cycle in which operands are read and written.
96///
97struct InstrItinerary {
98  int      NumMicroOps;        ///< # of micro-ops, -1 means it's variable
99  unsigned FirstStage;         ///< Index of first stage in itinerary
100  unsigned LastStage;          ///< Index of last + 1 stage in itinerary
101  unsigned FirstOperandCycle;  ///< Index of first operand rd/wr
102  unsigned LastOperandCycle;   ///< Index of last + 1 operand rd/wr
103};
104
105
106//===----------------------------------------------------------------------===//
107/// Itinerary data supplied by a subtarget to be used by a target.
108///
109class InstrItineraryData {
110public:
111  MCSchedModel          SchedModel;     ///< Basic machine properties.
112  const InstrStage     *Stages;         ///< Array of stages selected
113  const unsigned       *OperandCycles;  ///< Array of operand cycles selected
114  const unsigned       *Forwardings;    ///< Array of pipeline forwarding pathes
115  const InstrItinerary *Itineraries;    ///< Array of itineraries selected
116
117  /// Ctors.
118  InstrItineraryData() : SchedModel(MCSchedModel::GetDefaultSchedModel()),
119                         Stages(nullptr), OperandCycles(nullptr),
120                         Forwardings(nullptr), Itineraries(nullptr) {}
121
122  InstrItineraryData(const MCSchedModel &SM, const InstrStage *S,
123                     const unsigned *OS, const unsigned *F)
124    : SchedModel(SM), Stages(S), OperandCycles(OS), Forwardings(F),
125      Itineraries(SchedModel.InstrItineraries) {}
126
127  /// \brief Returns true if there are no itineraries.
128  bool isEmpty() const { return Itineraries == nullptr; }
129
130  /// \brief Returns true if the index is for the end marker itinerary.
131  bool isEndMarker(unsigned ItinClassIndx) const {
132    return ((Itineraries[ItinClassIndx].FirstStage == ~0U) &&
133            (Itineraries[ItinClassIndx].LastStage == ~0U));
134  }
135
136  /// \brief Return the first stage of the itinerary.
137  const InstrStage *beginStage(unsigned ItinClassIndx) const {
138    unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage;
139    return Stages + StageIdx;
140  }
141
142  /// \brief Return the last+1 stage of the itinerary.
143  const InstrStage *endStage(unsigned ItinClassIndx) const {
144    unsigned StageIdx = Itineraries[ItinClassIndx].LastStage;
145    return Stages + StageIdx;
146  }
147
148  /// \brief Return the total stage latency of the given class.  The latency is
149  /// the maximum completion time for any stage in the itinerary.  If no stages
150  /// exist, it defaults to one cycle.
151  unsigned getStageLatency(unsigned ItinClassIndx) const {
152    // If the target doesn't provide itinerary information, use a simple
153    // non-zero default value for all instructions.
154    if (isEmpty())
155      return 1;
156
157    // Calculate the maximum completion time for any stage.
158    unsigned Latency = 0, StartCycle = 0;
159    for (const InstrStage *IS = beginStage(ItinClassIndx),
160           *E = endStage(ItinClassIndx); IS != E; ++IS) {
161      Latency = std::max(Latency, StartCycle + IS->getCycles());
162      StartCycle += IS->getNextCycles();
163    }
164    return Latency;
165  }
166
167  /// \brief Return the cycle for the given class and operand.  Return -1 if no
168  /// cycle is specified for the operand.
169  int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const {
170    if (isEmpty())
171      return -1;
172
173    unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle;
174    unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle;
175    if ((FirstIdx + OperandIdx) >= LastIdx)
176      return -1;
177
178    return (int)OperandCycles[FirstIdx + OperandIdx];
179  }
180
181  /// \brief Return true if there is a pipeline forwarding between instructions
182  /// of itinerary classes DefClass and UseClasses so that value produced by an
183  /// instruction of itinerary class DefClass, operand index DefIdx can be
184  /// bypassed when it's read by an instruction of itinerary class UseClass,
185  /// operand index UseIdx.
186  bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx,
187                             unsigned UseClass, unsigned UseIdx) const {
188    unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle;
189    unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle;
190    if ((FirstDefIdx + DefIdx) >= LastDefIdx)
191      return false;
192    if (Forwardings[FirstDefIdx + DefIdx] == 0)
193      return false;
194
195    unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle;
196    unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle;
197    if ((FirstUseIdx + UseIdx) >= LastUseIdx)
198      return false;
199
200    return Forwardings[FirstDefIdx + DefIdx] ==
201      Forwardings[FirstUseIdx + UseIdx];
202  }
203
204  /// \brief Compute and return the use operand latency of a given itinerary
205  /// class and operand index if the value is produced by an instruction of the
206  /// specified itinerary class and def operand index.
207  int getOperandLatency(unsigned DefClass, unsigned DefIdx,
208                        unsigned UseClass, unsigned UseIdx) const {
209    if (isEmpty())
210      return -1;
211
212    int DefCycle = getOperandCycle(DefClass, DefIdx);
213    if (DefCycle == -1)
214      return -1;
215
216    int UseCycle = getOperandCycle(UseClass, UseIdx);
217    if (UseCycle == -1)
218      return -1;
219
220    UseCycle = DefCycle - UseCycle + 1;
221    if (UseCycle > 0 &&
222        hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx))
223      // FIXME: This assumes one cycle benefit for every pipeline forwarding.
224      --UseCycle;
225    return UseCycle;
226  }
227
228  /// \brief Return the number of micro-ops that the given class decodes to.
229  /// Return -1 for classes that require dynamic lookup via TargetInstrInfo.
230  int getNumMicroOps(unsigned ItinClassIndx) const {
231    if (isEmpty())
232      return 1;
233    return Itineraries[ItinClassIndx].NumMicroOps;
234  }
235};
236
237} // End llvm namespace
238
239#endif
240