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