File: | llvm/lib/MCA/Stages/MicroOpQueueStage.cpp |
Warning: | line 30, column 31 Division by zero |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===---------------------- MicroOpQueueStage.cpp ---------------*- 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 | /// \file | |||
9 | /// | |||
10 | /// This file defines the MicroOpQueueStage. | |||
11 | /// | |||
12 | //===----------------------------------------------------------------------===// | |||
13 | ||||
14 | #include "llvm/MCA/Stages/MicroOpQueueStage.h" | |||
15 | ||||
16 | namespace llvm { | |||
17 | namespace mca { | |||
18 | ||||
19 | #define DEBUG_TYPE"llvm-mca" "llvm-mca" | |||
20 | ||||
21 | Error MicroOpQueueStage::moveInstructions() { | |||
22 | InstRef IR = Buffer[CurrentInstructionSlotIdx]; | |||
23 | while (IR && checkNextStage(IR)) { | |||
24 | if (llvm::Error Val = moveToTheNextStage(IR)) | |||
25 | return Val; | |||
26 | ||||
27 | Buffer[CurrentInstructionSlotIdx].invalidate(); | |||
28 | unsigned NormalizedOpcodes = getNormalizedOpcodes(IR); | |||
29 | CurrentInstructionSlotIdx += NormalizedOpcodes; | |||
30 | CurrentInstructionSlotIdx %= Buffer.size(); | |||
| ||||
31 | AvailableEntries += NormalizedOpcodes; | |||
32 | IR = Buffer[CurrentInstructionSlotIdx]; | |||
33 | } | |||
34 | ||||
35 | return llvm::ErrorSuccess(); | |||
36 | } | |||
37 | ||||
38 | MicroOpQueueStage::MicroOpQueueStage(unsigned Size, unsigned IPC, | |||
39 | bool ZeroLatencyStage) | |||
40 | : NextAvailableSlotIdx(0), CurrentInstructionSlotIdx(0), MaxIPC(IPC), | |||
41 | CurrentIPC(0), IsZeroLatencyStage(ZeroLatencyStage) { | |||
42 | Buffer.resize(Size ? Size : 1); | |||
43 | AvailableEntries = Buffer.size(); | |||
44 | } | |||
45 | ||||
46 | Error MicroOpQueueStage::execute(InstRef &IR) { | |||
47 | Buffer[NextAvailableSlotIdx] = IR; | |||
48 | unsigned NormalizedOpcodes = getNormalizedOpcodes(IR); | |||
49 | NextAvailableSlotIdx += NormalizedOpcodes; | |||
50 | NextAvailableSlotIdx %= Buffer.size(); | |||
51 | AvailableEntries -= NormalizedOpcodes; | |||
52 | ++CurrentIPC; | |||
53 | return llvm::ErrorSuccess(); | |||
54 | } | |||
55 | ||||
56 | Error MicroOpQueueStage::cycleStart() { | |||
57 | CurrentIPC = 0; | |||
58 | if (!IsZeroLatencyStage) | |||
59 | return moveInstructions(); | |||
60 | return llvm::ErrorSuccess(); | |||
61 | } | |||
62 | ||||
63 | Error MicroOpQueueStage::cycleEnd() { | |||
64 | if (IsZeroLatencyStage) | |||
| ||||
65 | return moveInstructions(); | |||
66 | return llvm::ErrorSuccess(); | |||
67 | } | |||
68 | ||||
69 | } // namespace mca | |||
70 | } // namespace llvm |
1 | //===--------------------- Instruction.h ------------------------*- 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 | /// \file |
9 | /// |
10 | /// This file defines abstractions used by the Pipeline to model register reads, |
11 | /// register writes and instructions. |
12 | /// |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_MCA_INSTRUCTION_H |
16 | #define LLVM_MCA_INSTRUCTION_H |
17 | |
18 | #include "llvm/ADT/ArrayRef.h" |
19 | #include "llvm/ADT/STLExtras.h" |
20 | #include "llvm/ADT/SmallVector.h" |
21 | #include "llvm/MC/MCRegister.h" // definition of MCPhysReg. |
22 | #include "llvm/Support/MathExtras.h" |
23 | |
24 | #ifndef NDEBUG |
25 | #include "llvm/Support/raw_ostream.h" |
26 | #endif |
27 | |
28 | #include <memory> |
29 | |
30 | namespace llvm { |
31 | |
32 | namespace mca { |
33 | |
34 | constexpr int UNKNOWN_CYCLES = -512; |
35 | |
36 | /// A register write descriptor. |
37 | struct WriteDescriptor { |
38 | // Operand index. The index is negative for implicit writes only. |
39 | // For implicit writes, the actual operand index is computed performing |
40 | // a bitwise not of the OpIndex. |
41 | int OpIndex; |
42 | // Write latency. Number of cycles before write-back stage. |
43 | unsigned Latency; |
44 | // This field is set to a value different than zero only if this |
45 | // is an implicit definition. |
46 | MCPhysReg RegisterID; |
47 | // Instruction itineraries would set this field to the SchedClass ID. |
48 | // Otherwise, it defaults to the WriteResourceID from the MCWriteLatencyEntry |
49 | // element associated to this write. |
50 | // When computing read latencies, this value is matched against the |
51 | // "ReadAdvance" information. The hardware backend may implement |
52 | // dedicated forwarding paths to quickly propagate write results to dependent |
53 | // instructions waiting in the reservation station (effectively bypassing the |
54 | // write-back stage). |
55 | unsigned SClassOrWriteResourceID; |
56 | // True only if this is a write obtained from an optional definition. |
57 | // Optional definitions are allowed to reference regID zero (i.e. "no |
58 | // register"). |
59 | bool IsOptionalDef; |
60 | |
61 | bool isImplicitWrite() const { return OpIndex < 0; }; |
62 | }; |
63 | |
64 | /// A register read descriptor. |
65 | struct ReadDescriptor { |
66 | // A MCOperand index. This is used by the Dispatch logic to identify register |
67 | // reads. Implicit reads have negative indices. The actual operand index of an |
68 | // implicit read is the bitwise not of field OpIndex. |
69 | int OpIndex; |
70 | // The actual "UseIdx". This is used to query the ReadAdvance table. Explicit |
71 | // uses always come first in the sequence of uses. |
72 | unsigned UseIndex; |
73 | // This field is only set if this is an implicit read. |
74 | MCPhysReg RegisterID; |
75 | // Scheduling Class Index. It is used to query the scheduling model for the |
76 | // MCSchedClassDesc object. |
77 | unsigned SchedClassID; |
78 | |
79 | bool isImplicitRead() const { return OpIndex < 0; }; |
80 | }; |
81 | |
82 | class ReadState; |
83 | |
84 | /// A critical data dependency descriptor. |
85 | /// |
86 | /// Field RegID is set to the invalid register for memory dependencies. |
87 | struct CriticalDependency { |
88 | unsigned IID; |
89 | MCPhysReg RegID; |
90 | unsigned Cycles; |
91 | }; |
92 | |
93 | /// Tracks uses of a register definition (e.g. register write). |
94 | /// |
95 | /// Each implicit/explicit register write is associated with an instance of |
96 | /// this class. A WriteState object tracks the dependent users of a |
97 | /// register write. It also tracks how many cycles are left before the write |
98 | /// back stage. |
99 | class WriteState { |
100 | const WriteDescriptor *WD; |
101 | // On instruction issue, this field is set equal to the write latency. |
102 | // Before instruction issue, this field defaults to -512, a special |
103 | // value that represents an "unknown" number of cycles. |
104 | int CyclesLeft; |
105 | |
106 | // Actual register defined by this write. This field is only used |
107 | // to speedup queries on the register file. |
108 | // For implicit writes, this field always matches the value of |
109 | // field RegisterID from WD. |
110 | MCPhysReg RegisterID; |
111 | |
112 | // Physical register file that serves register RegisterID. |
113 | unsigned PRFID; |
114 | |
115 | // True if this write implicitly clears the upper portion of RegisterID's |
116 | // super-registers. |
117 | bool ClearsSuperRegs; |
118 | |
119 | // True if this write is from a dependency breaking zero-idiom instruction. |
120 | bool WritesZero; |
121 | |
122 | // True if this write has been eliminated at register renaming stage. |
123 | // Example: a register move doesn't consume scheduler/pipleline resources if |
124 | // it is eliminated at register renaming stage. It still consumes |
125 | // decode bandwidth, and ROB entries. |
126 | bool IsEliminated; |
127 | |
128 | // This field is set if this is a partial register write, and it has a false |
129 | // dependency on any previous write of the same register (or a portion of it). |
130 | // DependentWrite must be able to complete before this write completes, so |
131 | // that we don't break the WAW, and the two writes can be merged together. |
132 | const WriteState *DependentWrite; |
133 | |
134 | // A partial write that is in a false dependency with this write. |
135 | WriteState *PartialWrite; |
136 | unsigned DependentWriteCyclesLeft; |
137 | |
138 | // Critical register dependency for this write. |
139 | CriticalDependency CRD; |
140 | |
141 | // A list of dependent reads. Users is a set of dependent |
142 | // reads. A dependent read is added to the set only if CyclesLeft |
143 | // is "unknown". As soon as CyclesLeft is 'known', each user in the set |
144 | // gets notified with the actual CyclesLeft. |
145 | |
146 | // The 'second' element of a pair is a "ReadAdvance" number of cycles. |
147 | SmallVector<std::pair<ReadState *, int>, 4> Users; |
148 | |
149 | public: |
150 | WriteState(const WriteDescriptor &Desc, MCPhysReg RegID, |
151 | bool clearsSuperRegs = false, bool writesZero = false) |
152 | : WD(&Desc), CyclesLeft(UNKNOWN_CYCLES), RegisterID(RegID), PRFID(0), |
153 | ClearsSuperRegs(clearsSuperRegs), WritesZero(writesZero), |
154 | IsEliminated(false), DependentWrite(nullptr), PartialWrite(nullptr), |
155 | DependentWriteCyclesLeft(0), CRD() {} |
156 | |
157 | WriteState(const WriteState &Other) = default; |
158 | WriteState &operator=(const WriteState &Other) = default; |
159 | |
160 | int getCyclesLeft() const { return CyclesLeft; } |
161 | unsigned getWriteResourceID() const { return WD->SClassOrWriteResourceID; } |
162 | MCPhysReg getRegisterID() const { return RegisterID; } |
163 | unsigned getRegisterFileID() const { return PRFID; } |
164 | unsigned getLatency() const { return WD->Latency; } |
165 | unsigned getDependentWriteCyclesLeft() const { |
166 | return DependentWriteCyclesLeft; |
167 | } |
168 | const WriteState *getDependentWrite() const { return DependentWrite; } |
169 | const CriticalDependency &getCriticalRegDep() const { return CRD; } |
170 | |
171 | // This method adds Use to the set of data dependent reads. IID is the |
172 | // instruction identifier associated with this write. ReadAdvance is the |
173 | // number of cycles to subtract from the latency of this data dependency. |
174 | // Use is in a RAW dependency with this write. |
175 | void addUser(unsigned IID, ReadState *Use, int ReadAdvance); |
176 | |
177 | // Use is a younger register write that is in a false dependency with this |
178 | // write. IID is the instruction identifier associated with this write. |
179 | void addUser(unsigned IID, WriteState *Use); |
180 | |
181 | unsigned getNumUsers() const { |
182 | unsigned NumUsers = Users.size(); |
183 | if (PartialWrite) |
184 | ++NumUsers; |
185 | return NumUsers; |
186 | } |
187 | |
188 | bool clearsSuperRegisters() const { return ClearsSuperRegs; } |
189 | bool isWriteZero() const { return WritesZero; } |
190 | bool isEliminated() const { return IsEliminated; } |
191 | |
192 | bool isReady() const { |
193 | if (DependentWrite) |
194 | return false; |
195 | unsigned CyclesLeft = getDependentWriteCyclesLeft(); |
196 | return !CyclesLeft || CyclesLeft < getLatency(); |
197 | } |
198 | |
199 | bool isExecuted() const { |
200 | return CyclesLeft != UNKNOWN_CYCLES && CyclesLeft <= 0; |
201 | } |
202 | |
203 | void setDependentWrite(const WriteState *Other) { DependentWrite = Other; } |
204 | void writeStartEvent(unsigned IID, MCPhysReg RegID, unsigned Cycles); |
205 | void setWriteZero() { WritesZero = true; } |
206 | void setEliminated() { |
207 | assert(Users.empty() && "Write is in an inconsistent state.")((Users.empty() && "Write is in an inconsistent state." ) ? static_cast<void> (0) : __assert_fail ("Users.empty() && \"Write is in an inconsistent state.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/MCA/Instruction.h" , 207, __PRETTY_FUNCTION__)); |
208 | CyclesLeft = 0; |
209 | IsEliminated = true; |
210 | } |
211 | |
212 | void setPRF(unsigned PRF) { PRFID = PRF; } |
213 | |
214 | // On every cycle, update CyclesLeft and notify dependent users. |
215 | void cycleEvent(); |
216 | void onInstructionIssued(unsigned IID); |
217 | |
218 | #ifndef NDEBUG |
219 | void dump() const; |
220 | #endif |
221 | }; |
222 | |
223 | /// Tracks register operand latency in cycles. |
224 | /// |
225 | /// A read may be dependent on more than one write. This occurs when some |
226 | /// writes only partially update the register associated to this read. |
227 | class ReadState { |
228 | const ReadDescriptor *RD; |
229 | // Physical register identified associated to this read. |
230 | MCPhysReg RegisterID; |
231 | // Physical register file that serves register RegisterID. |
232 | unsigned PRFID; |
233 | // Number of writes that contribute to the definition of RegisterID. |
234 | // In the absence of partial register updates, the number of DependentWrites |
235 | // cannot be more than one. |
236 | unsigned DependentWrites; |
237 | // Number of cycles left before RegisterID can be read. This value depends on |
238 | // the latency of all the dependent writes. It defaults to UNKNOWN_CYCLES. |
239 | // It gets set to the value of field TotalCycles only when the 'CyclesLeft' of |
240 | // every dependent write is known. |
241 | int CyclesLeft; |
242 | // This field is updated on every writeStartEvent(). When the number of |
243 | // dependent writes (i.e. field DependentWrite) is zero, this value is |
244 | // propagated to field CyclesLeft. |
245 | unsigned TotalCycles; |
246 | // Longest register dependency. |
247 | CriticalDependency CRD; |
248 | // This field is set to true only if there are no dependent writes, and |
249 | // there are no `CyclesLeft' to wait. |
250 | bool IsReady; |
251 | // True if this is a read from a known zero register. |
252 | bool IsZero; |
253 | // True if this register read is from a dependency-breaking instruction. |
254 | bool IndependentFromDef; |
255 | |
256 | public: |
257 | ReadState(const ReadDescriptor &Desc, MCPhysReg RegID) |
258 | : RD(&Desc), RegisterID(RegID), PRFID(0), DependentWrites(0), |
259 | CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0), CRD(), IsReady(true), |
260 | IsZero(false), IndependentFromDef(false) {} |
261 | |
262 | const ReadDescriptor &getDescriptor() const { return *RD; } |
263 | unsigned getSchedClass() const { return RD->SchedClassID; } |
264 | MCPhysReg getRegisterID() const { return RegisterID; } |
265 | unsigned getRegisterFileID() const { return PRFID; } |
266 | const CriticalDependency &getCriticalRegDep() const { return CRD; } |
267 | |
268 | bool isPending() const { return !IndependentFromDef && CyclesLeft > 0; } |
269 | bool isReady() const { return IsReady; } |
270 | bool isImplicitRead() const { return RD->isImplicitRead(); } |
271 | |
272 | bool isIndependentFromDef() const { return IndependentFromDef; } |
273 | void setIndependentFromDef() { IndependentFromDef = true; } |
274 | |
275 | void cycleEvent(); |
276 | void writeStartEvent(unsigned IID, MCPhysReg RegID, unsigned Cycles); |
277 | void setDependentWrites(unsigned Writes) { |
278 | DependentWrites = Writes; |
279 | IsReady = !Writes; |
280 | } |
281 | |
282 | bool isReadZero() const { return IsZero; } |
283 | void setReadZero() { IsZero = true; } |
284 | void setPRF(unsigned ID) { PRFID = ID; } |
285 | }; |
286 | |
287 | /// A sequence of cycles. |
288 | /// |
289 | /// This class can be used as a building block to construct ranges of cycles. |
290 | class CycleSegment { |
291 | unsigned Begin; // Inclusive. |
292 | unsigned End; // Exclusive. |
293 | bool Reserved; // Resources associated to this segment must be reserved. |
294 | |
295 | public: |
296 | CycleSegment(unsigned StartCycle, unsigned EndCycle, bool IsReserved = false) |
297 | : Begin(StartCycle), End(EndCycle), Reserved(IsReserved) {} |
298 | |
299 | bool contains(unsigned Cycle) const { return Cycle >= Begin && Cycle < End; } |
300 | bool startsAfter(const CycleSegment &CS) const { return End <= CS.Begin; } |
301 | bool endsBefore(const CycleSegment &CS) const { return Begin >= CS.End; } |
302 | bool overlaps(const CycleSegment &CS) const { |
303 | return !startsAfter(CS) && !endsBefore(CS); |
304 | } |
305 | bool isExecuting() const { return Begin == 0 && End != 0; } |
306 | bool isExecuted() const { return End == 0; } |
307 | bool operator<(const CycleSegment &Other) const { |
308 | return Begin < Other.Begin; |
309 | } |
310 | CycleSegment &operator--(void) { |
311 | if (Begin) |
312 | Begin--; |
313 | if (End) |
314 | End--; |
315 | return *this; |
316 | } |
317 | |
318 | bool isValid() const { return Begin <= End; } |
319 | unsigned size() const { return End - Begin; }; |
320 | void subtract(unsigned Cycles) { |
321 | assert(End >= Cycles)((End >= Cycles) ? static_cast<void> (0) : __assert_fail ("End >= Cycles", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/MCA/Instruction.h" , 321, __PRETTY_FUNCTION__)); |
322 | End -= Cycles; |
323 | } |
324 | |
325 | unsigned begin() const { return Begin; } |
326 | unsigned end() const { return End; } |
327 | void setEnd(unsigned NewEnd) { End = NewEnd; } |
328 | bool isReserved() const { return Reserved; } |
329 | void setReserved() { Reserved = true; } |
330 | }; |
331 | |
332 | /// Helper used by class InstrDesc to describe how hardware resources |
333 | /// are used. |
334 | /// |
335 | /// This class describes how many resource units of a specific resource kind |
336 | /// (and how many cycles) are "used" by an instruction. |
337 | struct ResourceUsage { |
338 | CycleSegment CS; |
339 | unsigned NumUnits; |
340 | ResourceUsage(CycleSegment Cycles, unsigned Units = 1) |
341 | : CS(Cycles), NumUnits(Units) {} |
342 | unsigned size() const { return CS.size(); } |
343 | bool isReserved() const { return CS.isReserved(); } |
344 | void setReserved() { CS.setReserved(); } |
345 | }; |
346 | |
347 | /// An instruction descriptor |
348 | struct InstrDesc { |
349 | SmallVector<WriteDescriptor, 4> Writes; // Implicit writes are at the end. |
350 | SmallVector<ReadDescriptor, 4> Reads; // Implicit reads are at the end. |
351 | |
352 | // For every resource used by an instruction of this kind, this vector |
353 | // reports the number of "consumed cycles". |
354 | SmallVector<std::pair<uint64_t, ResourceUsage>, 4> Resources; |
355 | |
356 | // A bitmask of used hardware buffers. |
357 | uint64_t UsedBuffers; |
358 | |
359 | // A bitmask of used processor resource units. |
360 | uint64_t UsedProcResUnits; |
361 | |
362 | // A bitmask of used processor resource groups. |
363 | uint64_t UsedProcResGroups; |
364 | |
365 | unsigned MaxLatency; |
366 | // Number of MicroOps for this instruction. |
367 | unsigned NumMicroOps; |
368 | // SchedClassID used to construct this InstrDesc. |
369 | // This information is currently used by views to do fast queries on the |
370 | // subtarget when computing the reciprocal throughput. |
371 | unsigned SchedClassID; |
372 | |
373 | bool MayLoad; |
374 | bool MayStore; |
375 | bool HasSideEffects; |
376 | bool BeginGroup; |
377 | bool EndGroup; |
378 | |
379 | // True if all buffered resources are in-order, and there is at least one |
380 | // buffer which is a dispatch hazard (BufferSize = 0). |
381 | bool MustIssueImmediately; |
382 | |
383 | // A zero latency instruction doesn't consume any scheduler resources. |
384 | bool isZeroLatency() const { return !MaxLatency && Resources.empty(); } |
385 | |
386 | InstrDesc() = default; |
387 | InstrDesc(const InstrDesc &Other) = delete; |
388 | InstrDesc &operator=(const InstrDesc &Other) = delete; |
389 | }; |
390 | |
391 | /// Base class for instructions consumed by the simulation pipeline. |
392 | /// |
393 | /// This class tracks data dependencies as well as generic properties |
394 | /// of the instruction. |
395 | class InstructionBase { |
396 | const InstrDesc &Desc; |
397 | |
398 | // This field is set for instructions that are candidates for move |
399 | // elimination. For more information about move elimination, see the |
400 | // definition of RegisterMappingTracker in RegisterFile.h |
401 | bool IsOptimizableMove; |
402 | |
403 | // Output dependencies. |
404 | // One entry per each implicit and explicit register definition. |
405 | SmallVector<WriteState, 4> Defs; |
406 | |
407 | // Input dependencies. |
408 | // One entry per each implicit and explicit register use. |
409 | SmallVector<ReadState, 4> Uses; |
410 | |
411 | public: |
412 | InstructionBase(const InstrDesc &D) : Desc(D), IsOptimizableMove(false) {} |
413 | |
414 | SmallVectorImpl<WriteState> &getDefs() { return Defs; } |
415 | const ArrayRef<WriteState> getDefs() const { return Defs; } |
416 | SmallVectorImpl<ReadState> &getUses() { return Uses; } |
417 | const ArrayRef<ReadState> getUses() const { return Uses; } |
418 | const InstrDesc &getDesc() const { return Desc; } |
419 | |
420 | unsigned getLatency() const { return Desc.MaxLatency; } |
421 | unsigned getNumMicroOps() const { return Desc.NumMicroOps; } |
422 | |
423 | bool hasDependentUsers() const { |
424 | return any_of(Defs, |
425 | [](const WriteState &Def) { return Def.getNumUsers() > 0; }); |
426 | } |
427 | |
428 | unsigned getNumUsers() const { |
429 | unsigned NumUsers = 0; |
430 | for (const WriteState &Def : Defs) |
431 | NumUsers += Def.getNumUsers(); |
432 | return NumUsers; |
433 | } |
434 | |
435 | // Returns true if this instruction is a candidate for move elimination. |
436 | bool isOptimizableMove() const { return IsOptimizableMove; } |
437 | void setOptimizableMove() { IsOptimizableMove = true; } |
438 | bool isMemOp() const { return Desc.MayLoad || Desc.MayStore; } |
439 | }; |
440 | |
441 | /// An instruction propagated through the simulated instruction pipeline. |
442 | /// |
443 | /// This class is used to monitor changes to the internal state of instructions |
444 | /// that are sent to the various components of the simulated hardware pipeline. |
445 | class Instruction : public InstructionBase { |
446 | enum InstrStage { |
447 | IS_INVALID, // Instruction in an invalid state. |
448 | IS_DISPATCHED, // Instruction dispatched but operands are not ready. |
449 | IS_PENDING, // Instruction is not ready, but operand latency is known. |
450 | IS_READY, // Instruction dispatched and operands ready. |
451 | IS_EXECUTING, // Instruction issued. |
452 | IS_EXECUTED, // Instruction executed. Values are written back. |
453 | IS_RETIRED // Instruction retired. |
454 | }; |
455 | |
456 | // The current instruction stage. |
457 | enum InstrStage Stage; |
458 | |
459 | // This value defaults to the instruction latency. This instruction is |
460 | // considered executed when field CyclesLeft goes to zero. |
461 | int CyclesLeft; |
462 | |
463 | // Retire Unit token ID for this instruction. |
464 | unsigned RCUTokenID; |
465 | |
466 | // LS token ID for this instruction. |
467 | // This field is set to the invalid null token if this is not a memory |
468 | // operation. |
469 | unsigned LSUTokenID; |
470 | |
471 | // A resource mask which identifies buffered resources consumed by this |
472 | // instruction at dispatch stage. In the absence of macro-fusion, this value |
473 | // should always match the value of field `UsedBuffers` from the instruction |
474 | // descriptor (see field InstrBase::Desc). |
475 | uint64_t UsedBuffers; |
476 | |
477 | // Critical register dependency. |
478 | CriticalDependency CriticalRegDep; |
479 | |
480 | // Critical memory dependency. |
481 | CriticalDependency CriticalMemDep; |
482 | |
483 | // A bitmask of busy processor resource units. |
484 | // This field is set to zero only if execution is not delayed during this |
485 | // cycle because of unavailable pipeline resources. |
486 | uint64_t CriticalResourceMask; |
487 | |
488 | // True if this instruction has been optimized at register renaming stage. |
489 | bool IsEliminated; |
490 | |
491 | public: |
492 | Instruction(const InstrDesc &D) |
493 | : InstructionBase(D), Stage(IS_INVALID), CyclesLeft(UNKNOWN_CYCLES), |
494 | RCUTokenID(0), LSUTokenID(0), UsedBuffers(D.UsedBuffers), |
495 | CriticalRegDep(), CriticalMemDep(), CriticalResourceMask(0), |
496 | IsEliminated(false) {} |
497 | |
498 | unsigned getRCUTokenID() const { return RCUTokenID; } |
499 | unsigned getLSUTokenID() const { return LSUTokenID; } |
500 | void setLSUTokenID(unsigned LSUTok) { LSUTokenID = LSUTok; } |
501 | |
502 | uint64_t getUsedBuffers() const { return UsedBuffers; } |
503 | void setUsedBuffers(uint64_t Mask) { UsedBuffers = Mask; } |
504 | void clearUsedBuffers() { UsedBuffers = 0ULL; } |
505 | |
506 | int getCyclesLeft() const { return CyclesLeft; } |
507 | |
508 | // Transition to the dispatch stage, and assign a RCUToken to this |
509 | // instruction. The RCUToken is used to track the completion of every |
510 | // register write performed by this instruction. |
511 | void dispatch(unsigned RCUTokenID); |
512 | |
513 | // Instruction issued. Transition to the IS_EXECUTING state, and update |
514 | // all the register definitions. |
515 | void execute(unsigned IID); |
516 | |
517 | // Force a transition from the IS_DISPATCHED state to the IS_READY or |
518 | // IS_PENDING state. State transitions normally occur either at the beginning |
519 | // of a new cycle (see method cycleEvent()), or as a result of another issue |
520 | // event. This method is called every time the instruction might have changed |
521 | // in state. It internally delegates to method updateDispatched() and |
522 | // updateWaiting(). |
523 | void update(); |
524 | bool updateDispatched(); |
525 | bool updatePending(); |
526 | |
527 | bool isDispatched() const { return Stage == IS_DISPATCHED; } |
528 | bool isPending() const { return Stage == IS_PENDING; } |
529 | bool isReady() const { return Stage == IS_READY; } |
530 | bool isExecuting() const { return Stage == IS_EXECUTING; } |
531 | bool isExecuted() const { return Stage == IS_EXECUTED; } |
532 | bool isRetired() const { return Stage == IS_RETIRED; } |
533 | bool isEliminated() const { return IsEliminated; } |
534 | |
535 | // Forces a transition from state IS_DISPATCHED to state IS_EXECUTED. |
536 | void forceExecuted(); |
537 | void setEliminated() { IsEliminated = true; } |
538 | |
539 | void retire() { |
540 | assert(isExecuted() && "Instruction is in an invalid state!")((isExecuted() && "Instruction is in an invalid state!" ) ? static_cast<void> (0) : __assert_fail ("isExecuted() && \"Instruction is in an invalid state!\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/MCA/Instruction.h" , 540, __PRETTY_FUNCTION__)); |
541 | Stage = IS_RETIRED; |
542 | } |
543 | |
544 | const CriticalDependency &getCriticalRegDep() const { return CriticalRegDep; } |
545 | const CriticalDependency &getCriticalMemDep() const { return CriticalMemDep; } |
546 | const CriticalDependency &computeCriticalRegDep(); |
547 | void setCriticalMemDep(const CriticalDependency &MemDep) { |
548 | CriticalMemDep = MemDep; |
549 | } |
550 | |
551 | uint64_t getCriticalResourceMask() const { return CriticalResourceMask; } |
552 | void setCriticalResourceMask(uint64_t ResourceMask) { |
553 | CriticalResourceMask = ResourceMask; |
554 | } |
555 | |
556 | void cycleEvent(); |
557 | }; |
558 | |
559 | /// An InstRef contains both a SourceMgr index and Instruction pair. The index |
560 | /// is used as a unique identifier for the instruction. MCA will make use of |
561 | /// this index as a key throughout MCA. |
562 | class InstRef { |
563 | std::pair<unsigned, Instruction *> Data; |
564 | |
565 | public: |
566 | InstRef() : Data(std::make_pair(0, nullptr)) {} |
567 | InstRef(unsigned Index, Instruction *I) : Data(std::make_pair(Index, I)) {} |
568 | |
569 | bool operator==(const InstRef &Other) const { return Data == Other.Data; } |
570 | bool operator!=(const InstRef &Other) const { return Data != Other.Data; } |
571 | bool operator<(const InstRef &Other) const { |
572 | return Data.first < Other.Data.first; |
573 | } |
574 | |
575 | unsigned getSourceIndex() const { return Data.first; } |
576 | Instruction *getInstruction() { return Data.second; } |
577 | const Instruction *getInstruction() const { return Data.second; } |
578 | |
579 | /// Returns true if this references a valid instruction. |
580 | explicit operator bool() const { return Data.second != nullptr; } |
581 | |
582 | /// Invalidate this reference. |
583 | void invalidate() { Data.second = nullptr; } |
584 | |
585 | #ifndef NDEBUG |
586 | void print(raw_ostream &OS) const { OS << getSourceIndex(); } |
587 | #endif |
588 | }; |
589 | |
590 | #ifndef NDEBUG |
591 | inline raw_ostream &operator<<(raw_ostream &OS, const InstRef &IR) { |
592 | IR.print(OS); |
593 | return OS; |
594 | } |
595 | #endif |
596 | |
597 | /// A reference to a register write. |
598 | /// |
599 | /// This class is mainly used by the register file to describe register |
600 | /// mappings. It correlates a register write to the source index of the |
601 | /// defining instruction. |
602 | class WriteRef { |
603 | std::pair<unsigned, WriteState *> Data; |
604 | static const unsigned INVALID_IID; |
605 | |
606 | public: |
607 | WriteRef() : Data(INVALID_IID, nullptr) {} |
608 | WriteRef(unsigned SourceIndex, WriteState *WS) : Data(SourceIndex, WS) {} |
609 | |
610 | unsigned getSourceIndex() const { return Data.first; } |
611 | const WriteState *getWriteState() const { return Data.second; } |
612 | WriteState *getWriteState() { return Data.second; } |
613 | void invalidate() { Data.second = nullptr; } |
614 | bool isWriteZero() const { |
615 | assert(isValid() && "Invalid null WriteState found!")((isValid() && "Invalid null WriteState found!") ? static_cast <void> (0) : __assert_fail ("isValid() && \"Invalid null WriteState found!\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/MCA/Instruction.h" , 615, __PRETTY_FUNCTION__)); |
616 | return getWriteState()->isWriteZero(); |
617 | } |
618 | |
619 | /// Returns true if this register write has been executed, and the new |
620 | /// register value is therefore available to users. |
621 | bool isAvailable() const { |
622 | if (getSourceIndex() == INVALID_IID) |
623 | return false; |
624 | const WriteState *WS = getWriteState(); |
625 | return !WS || WS->isExecuted(); |
626 | } |
627 | |
628 | bool isValid() const { return Data.second && Data.first != INVALID_IID; } |
629 | bool operator==(const WriteRef &Other) const { return Data == Other.Data; } |
630 | |
631 | #ifndef NDEBUG |
632 | void dump() const; |
633 | #endif |
634 | }; |
635 | |
636 | } // namespace mca |
637 | } // namespace llvm |
638 | |
639 | #endif // LLVM_MCA_INSTRUCTION_H |
1 | //===---------------------- Stage.h -----------------------------*- 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 | /// \file |
9 | /// |
10 | /// This file defines a stage. |
11 | /// A chain of stages compose an instruction pipeline. |
12 | /// |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_MCA_STAGE_H |
16 | #define LLVM_MCA_STAGE_H |
17 | |
18 | #include "llvm/MCA/HWEventListener.h" |
19 | #include "llvm/Support/Error.h" |
20 | #include <set> |
21 | |
22 | namespace llvm { |
23 | namespace mca { |
24 | |
25 | class InstRef; |
26 | |
27 | class Stage { |
28 | Stage *NextInSequence; |
29 | std::set<HWEventListener *> Listeners; |
30 | |
31 | Stage(const Stage &Other) = delete; |
32 | Stage &operator=(const Stage &Other) = delete; |
33 | |
34 | protected: |
35 | const std::set<HWEventListener *> &getListeners() const { return Listeners; } |
36 | |
37 | public: |
38 | Stage() : NextInSequence(nullptr) {} |
39 | virtual ~Stage(); |
40 | |
41 | /// Returns true if it can execute IR during this cycle. |
42 | virtual bool isAvailable(const InstRef &IR) const { return true; } |
43 | |
44 | /// Returns true if some instructions are still executing this stage. |
45 | virtual bool hasWorkToComplete() const = 0; |
46 | |
47 | /// Called once at the start of each cycle. This can be used as a setup |
48 | /// phase to prepare for the executions during the cycle. |
49 | virtual Error cycleStart() { return ErrorSuccess(); } |
50 | |
51 | /// Called once at the end of each cycle. |
52 | virtual Error cycleEnd() { return ErrorSuccess(); } |
53 | |
54 | /// The primary action that this stage performs on instruction IR. |
55 | virtual Error execute(InstRef &IR) = 0; |
56 | |
57 | void setNextInSequence(Stage *NextStage) { |
58 | assert(!NextInSequence && "This stage already has a NextInSequence!")((!NextInSequence && "This stage already has a NextInSequence!" ) ? static_cast<void> (0) : __assert_fail ("!NextInSequence && \"This stage already has a NextInSequence!\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/MCA/Stages/Stage.h" , 58, __PRETTY_FUNCTION__)); |
59 | NextInSequence = NextStage; |
60 | } |
61 | |
62 | bool checkNextStage(const InstRef &IR) const { |
63 | return NextInSequence && NextInSequence->isAvailable(IR); |
64 | } |
65 | |
66 | /// Called when an instruction is ready to move the next pipeline stage. |
67 | /// |
68 | /// Stages are responsible for moving instructions to their immediate |
69 | /// successor stages. |
70 | Error moveToTheNextStage(InstRef &IR) { |
71 | assert(checkNextStage(IR) && "Next stage is not ready!")((checkNextStage(IR) && "Next stage is not ready!") ? static_cast<void> (0) : __assert_fail ("checkNextStage(IR) && \"Next stage is not ready!\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/MCA/Stages/Stage.h" , 71, __PRETTY_FUNCTION__)); |
72 | return NextInSequence->execute(IR); |
73 | } |
74 | |
75 | /// Add a listener to receive callbacks during the execution of this stage. |
76 | void addListener(HWEventListener *Listener); |
77 | |
78 | /// Notify listeners of a particular hardware event. |
79 | template <typename EventT> void notifyEvent(const EventT &Event) const { |
80 | for (HWEventListener *Listener : Listeners) |
81 | Listener->onEvent(Event); |
82 | } |
83 | }; |
84 | |
85 | } // namespace mca |
86 | } // namespace llvm |
87 | #endif // LLVM_MCA_STAGE_H |
1 | //===---------------------- MicroOpQueueStage.h -----------------*- 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 | /// \file |
9 | /// |
10 | /// This file defines a stage that implements a queue of micro opcodes. |
11 | /// It can be used to simulate a hardware micro-op queue that serves opcodes to |
12 | /// the out of order backend. |
13 | /// |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #ifndef LLVM_MCA_MICRO_OP_QUEUE_STAGE_H |
17 | #define LLVM_MCA_MICRO_OP_QUEUE_STAGE_H |
18 | |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/MCA/Stages/Stage.h" |
21 | |
22 | namespace llvm { |
23 | namespace mca { |
24 | |
25 | /// A stage that simulates a queue of instruction opcodes. |
26 | class MicroOpQueueStage : public Stage { |
27 | SmallVector<InstRef, 8> Buffer; |
28 | unsigned NextAvailableSlotIdx; |
29 | unsigned CurrentInstructionSlotIdx; |
30 | |
31 | // Limits the number of instructions that can be written to this buffer every |
32 | // cycle. A value of zero means that there is no limit to the instruction |
33 | // throughput in input. |
34 | const unsigned MaxIPC; |
35 | unsigned CurrentIPC; |
36 | |
37 | // Number of entries that are available during this cycle. |
38 | unsigned AvailableEntries; |
39 | |
40 | // True if instructions dispatched to this stage don't need to wait for the |
41 | // next cycle before moving to the next stage. |
42 | // False if this buffer acts as a one cycle delay in the execution pipeline. |
43 | bool IsZeroLatencyStage; |
44 | |
45 | MicroOpQueueStage(const MicroOpQueueStage &Other) = delete; |
46 | MicroOpQueueStage &operator=(const MicroOpQueueStage &Other) = delete; |
47 | |
48 | // By default, an instruction consumes a number of buffer entries equal to its |
49 | // number of micro opcodes (see field `InstrDesc::NumMicroOpcodes`). The |
50 | // number of entries consumed by an instruction is normalized to the |
51 | // minimum value between NumMicroOpcodes and the buffer size. This is to avoid |
52 | // problems with (microcoded) instructions that generate a number of micro |
53 | // opcodes than doesn't fit in the buffer. |
54 | unsigned getNormalizedOpcodes(const InstRef &IR) const { |
55 | unsigned NormalizedOpcodes = |
56 | std::min(static_cast<unsigned>(Buffer.size()), |
57 | IR.getInstruction()->getDesc().NumMicroOps); |
58 | return NormalizedOpcodes ? NormalizedOpcodes : 1U; |
59 | } |
60 | |
61 | Error moveInstructions(); |
62 | |
63 | public: |
64 | MicroOpQueueStage(unsigned Size, unsigned IPC = 0, |
65 | bool ZeroLatencyStage = true); |
66 | |
67 | bool isAvailable(const InstRef &IR) const override { |
68 | if (MaxIPC && CurrentIPC == MaxIPC) |
69 | return false; |
70 | unsigned NormalizedOpcodes = getNormalizedOpcodes(IR); |
71 | if (NormalizedOpcodes > AvailableEntries) |
72 | return false; |
73 | return true; |
74 | } |
75 | |
76 | bool hasWorkToComplete() const override { |
77 | return AvailableEntries != Buffer.size(); |
78 | } |
79 | |
80 | Error execute(InstRef &IR) override; |
81 | Error cycleStart() override; |
82 | Error cycleEnd() override; |
83 | }; |
84 | |
85 | } // namespace mca |
86 | } // namespace llvm |
87 | |
88 | #endif // LLVM_MCA_MICRO_OP_QUEUE_STAGE_H |
1 | //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- 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 defines the SmallVector class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_ADT_SMALLVECTOR_H |
14 | #define LLVM_ADT_SMALLVECTOR_H |
15 | |
16 | #include "llvm/ADT/iterator_range.h" |
17 | #include "llvm/Support/AlignOf.h" |
18 | #include "llvm/Support/Compiler.h" |
19 | #include "llvm/Support/MathExtras.h" |
20 | #include "llvm/Support/MemAlloc.h" |
21 | #include "llvm/Support/type_traits.h" |
22 | #include "llvm/Support/ErrorHandling.h" |
23 | #include <algorithm> |
24 | #include <cassert> |
25 | #include <cstddef> |
26 | #include <cstdlib> |
27 | #include <cstring> |
28 | #include <initializer_list> |
29 | #include <iterator> |
30 | #include <memory> |
31 | #include <new> |
32 | #include <type_traits> |
33 | #include <utility> |
34 | |
35 | namespace llvm { |
36 | |
37 | /// This is all the non-templated stuff common to all SmallVectors. |
38 | class SmallVectorBase { |
39 | protected: |
40 | void *BeginX; |
41 | unsigned Size = 0, Capacity; |
42 | |
43 | SmallVectorBase() = delete; |
44 | SmallVectorBase(void *FirstEl, size_t TotalCapacity) |
45 | : BeginX(FirstEl), Capacity(TotalCapacity) {} |
46 | |
47 | /// This is an implementation of the grow() method which only works |
48 | /// on POD-like data types and is out of line to reduce code duplication. |
49 | void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize); |
50 | |
51 | public: |
52 | size_t size() const { return Size; } |
53 | size_t capacity() const { return Capacity; } |
54 | |
55 | LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; } |
56 | |
57 | /// Set the array size to \p N, which the current array must have enough |
58 | /// capacity for. |
59 | /// |
60 | /// This does not construct or destroy any elements in the vector. |
61 | /// |
62 | /// Clients can use this in conjunction with capacity() to write past the end |
63 | /// of the buffer when they know that more elements are available, and only |
64 | /// update the size later. This avoids the cost of value initializing elements |
65 | /// which will only be overwritten. |
66 | void set_size(size_t N) { |
67 | assert(N <= capacity())((N <= capacity()) ? static_cast<void> (0) : __assert_fail ("N <= capacity()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 67, __PRETTY_FUNCTION__)); |
68 | Size = N; |
69 | } |
70 | }; |
71 | |
72 | /// Figure out the offset of the first element. |
73 | template <class T, typename = void> struct SmallVectorAlignmentAndSize { |
74 | AlignedCharArrayUnion<SmallVectorBase> Base; |
75 | AlignedCharArrayUnion<T> FirstEl; |
76 | }; |
77 | |
78 | /// This is the part of SmallVectorTemplateBase which does not depend on whether |
79 | /// the type T is a POD. The extra dummy template argument is used by ArrayRef |
80 | /// to avoid unnecessarily requiring T to be complete. |
81 | template <typename T, typename = void> |
82 | class SmallVectorTemplateCommon : public SmallVectorBase { |
83 | /// Find the address of the first element. For this pointer math to be valid |
84 | /// with small-size of 0 for T with lots of alignment, it's important that |
85 | /// SmallVectorStorage is properly-aligned even for small-size of 0. |
86 | void *getFirstEl() const { |
87 | return const_cast<void *>(reinterpret_cast<const void *>( |
88 | reinterpret_cast<const char *>(this) + |
89 | offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl ))); |
90 | } |
91 | // Space after 'FirstEl' is clobbered, do not add any instance vars after it. |
92 | |
93 | protected: |
94 | SmallVectorTemplateCommon(size_t Size) |
95 | : SmallVectorBase(getFirstEl(), Size) {} |
96 | |
97 | void grow_pod(size_t MinCapacity, size_t TSize) { |
98 | SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize); |
99 | } |
100 | |
101 | /// Return true if this is a smallvector which has not had dynamic |
102 | /// memory allocated for it. |
103 | bool isSmall() const { return BeginX == getFirstEl(); } |
104 | |
105 | /// Put this vector in a state of being small. |
106 | void resetToSmall() { |
107 | BeginX = getFirstEl(); |
108 | Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect. |
109 | } |
110 | |
111 | public: |
112 | using size_type = size_t; |
113 | using difference_type = ptrdiff_t; |
114 | using value_type = T; |
115 | using iterator = T *; |
116 | using const_iterator = const T *; |
117 | |
118 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
119 | using reverse_iterator = std::reverse_iterator<iterator>; |
120 | |
121 | using reference = T &; |
122 | using const_reference = const T &; |
123 | using pointer = T *; |
124 | using const_pointer = const T *; |
125 | |
126 | // forward iterator creation methods. |
127 | iterator begin() { return (iterator)this->BeginX; } |
128 | const_iterator begin() const { return (const_iterator)this->BeginX; } |
129 | iterator end() { return begin() + size(); } |
130 | const_iterator end() const { return begin() + size(); } |
131 | |
132 | // reverse iterator creation methods. |
133 | reverse_iterator rbegin() { return reverse_iterator(end()); } |
134 | const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } |
135 | reverse_iterator rend() { return reverse_iterator(begin()); } |
136 | const_reverse_iterator rend() const { return const_reverse_iterator(begin());} |
137 | |
138 | size_type size_in_bytes() const { return size() * sizeof(T); } |
139 | size_type max_size() const { return size_type(-1) / sizeof(T); } |
140 | |
141 | size_t capacity_in_bytes() const { return capacity() * sizeof(T); } |
142 | |
143 | /// Return a pointer to the vector's buffer, even if empty(). |
144 | pointer data() { return pointer(begin()); } |
145 | /// Return a pointer to the vector's buffer, even if empty(). |
146 | const_pointer data() const { return const_pointer(begin()); } |
147 | |
148 | reference operator[](size_type idx) { |
149 | assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail ("idx < size()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 149, __PRETTY_FUNCTION__)); |
150 | return begin()[idx]; |
151 | } |
152 | const_reference operator[](size_type idx) const { |
153 | assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail ("idx < size()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 153, __PRETTY_FUNCTION__)); |
154 | return begin()[idx]; |
155 | } |
156 | |
157 | reference front() { |
158 | assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 158, __PRETTY_FUNCTION__)); |
159 | return begin()[0]; |
160 | } |
161 | const_reference front() const { |
162 | assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 162, __PRETTY_FUNCTION__)); |
163 | return begin()[0]; |
164 | } |
165 | |
166 | reference back() { |
167 | assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 167, __PRETTY_FUNCTION__)); |
168 | return end()[-1]; |
169 | } |
170 | const_reference back() const { |
171 | assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 171, __PRETTY_FUNCTION__)); |
172 | return end()[-1]; |
173 | } |
174 | }; |
175 | |
176 | /// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method |
177 | /// implementations that are designed to work with non-POD-like T's. |
178 | template <typename T, bool = is_trivially_copyable<T>::value> |
179 | class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { |
180 | protected: |
181 | SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} |
182 | |
183 | static void destroy_range(T *S, T *E) { |
184 | while (S != E) { |
185 | --E; |
186 | E->~T(); |
187 | } |
188 | } |
189 | |
190 | /// Move the range [I, E) into the uninitialized memory starting with "Dest", |
191 | /// constructing elements as needed. |
192 | template<typename It1, typename It2> |
193 | static void uninitialized_move(It1 I, It1 E, It2 Dest) { |
194 | std::uninitialized_copy(std::make_move_iterator(I), |
195 | std::make_move_iterator(E), Dest); |
196 | } |
197 | |
198 | /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", |
199 | /// constructing elements as needed. |
200 | template<typename It1, typename It2> |
201 | static void uninitialized_copy(It1 I, It1 E, It2 Dest) { |
202 | std::uninitialized_copy(I, E, Dest); |
203 | } |
204 | |
205 | /// Grow the allocated memory (without initializing new elements), doubling |
206 | /// the size of the allocated memory. Guarantees space for at least one more |
207 | /// element, or MinSize more elements if specified. |
208 | void grow(size_t MinSize = 0); |
209 | |
210 | public: |
211 | void push_back(const T &Elt) { |
212 | if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity ()), false)) |
213 | this->grow(); |
214 | ::new ((void*) this->end()) T(Elt); |
215 | this->set_size(this->size() + 1); |
216 | } |
217 | |
218 | void push_back(T &&Elt) { |
219 | if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity ()), false)) |
220 | this->grow(); |
221 | ::new ((void*) this->end()) T(::std::move(Elt)); |
222 | this->set_size(this->size() + 1); |
223 | } |
224 | |
225 | void pop_back() { |
226 | this->set_size(this->size() - 1); |
227 | this->end()->~T(); |
228 | } |
229 | }; |
230 | |
231 | // Define this out-of-line to dissuade the C++ compiler from inlining it. |
232 | template <typename T, bool TriviallyCopyable> |
233 | void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) { |
234 | if (MinSize > UINT32_MAX(4294967295U)) |
235 | report_bad_alloc_error("SmallVector capacity overflow during allocation"); |
236 | |
237 | // Always grow, even from zero. |
238 | size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2)); |
239 | NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX(4294967295U))); |
240 | T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T))); |
241 | |
242 | // Move the elements over. |
243 | this->uninitialized_move(this->begin(), this->end(), NewElts); |
244 | |
245 | // Destroy the original elements. |
246 | destroy_range(this->begin(), this->end()); |
247 | |
248 | // If this wasn't grown from the inline copy, deallocate the old space. |
249 | if (!this->isSmall()) |
250 | free(this->begin()); |
251 | |
252 | this->BeginX = NewElts; |
253 | this->Capacity = NewCapacity; |
254 | } |
255 | |
256 | /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put |
257 | /// method implementations that are designed to work with POD-like T's. |
258 | template <typename T> |
259 | class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { |
260 | protected: |
261 | SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} |
262 | |
263 | // No need to do a destroy loop for POD's. |
264 | static void destroy_range(T *, T *) {} |
265 | |
266 | /// Move the range [I, E) onto the uninitialized memory |
267 | /// starting with "Dest", constructing elements into it as needed. |
268 | template<typename It1, typename It2> |
269 | static void uninitialized_move(It1 I, It1 E, It2 Dest) { |
270 | // Just do a copy. |
271 | uninitialized_copy(I, E, Dest); |
272 | } |
273 | |
274 | /// Copy the range [I, E) onto the uninitialized memory |
275 | /// starting with "Dest", constructing elements into it as needed. |
276 | template<typename It1, typename It2> |
277 | static void uninitialized_copy(It1 I, It1 E, It2 Dest) { |
278 | // Arbitrary iterator types; just use the basic implementation. |
279 | std::uninitialized_copy(I, E, Dest); |
280 | } |
281 | |
282 | /// Copy the range [I, E) onto the uninitialized memory |
283 | /// starting with "Dest", constructing elements into it as needed. |
284 | template <typename T1, typename T2> |
285 | static void uninitialized_copy( |
286 | T1 *I, T1 *E, T2 *Dest, |
287 | typename std::enable_if<std::is_same<typename std::remove_const<T1>::type, |
288 | T2>::value>::type * = nullptr) { |
289 | // Use memcpy for PODs iterated by pointers (which includes SmallVector |
290 | // iterators): std::uninitialized_copy optimizes to memmove, but we can |
291 | // use memcpy here. Note that I and E are iterators and thus might be |
292 | // invalid for memcpy if they are equal. |
293 | if (I != E) |
294 | memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T)); |
295 | } |
296 | |
297 | /// Double the size of the allocated memory, guaranteeing space for at |
298 | /// least one more element or MinSize if specified. |
299 | void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); } |
300 | |
301 | public: |
302 | void push_back(const T &Elt) { |
303 | if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity ()), false)) |
304 | this->grow(); |
305 | memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T)); |
306 | this->set_size(this->size() + 1); |
307 | } |
308 | |
309 | void pop_back() { this->set_size(this->size() - 1); } |
310 | }; |
311 | |
312 | /// This class consists of common code factored out of the SmallVector class to |
313 | /// reduce code duplication based on the SmallVector 'N' template parameter. |
314 | template <typename T> |
315 | class SmallVectorImpl : public SmallVectorTemplateBase<T> { |
316 | using SuperClass = SmallVectorTemplateBase<T>; |
317 | |
318 | public: |
319 | using iterator = typename SuperClass::iterator; |
320 | using const_iterator = typename SuperClass::const_iterator; |
321 | using reference = typename SuperClass::reference; |
322 | using size_type = typename SuperClass::size_type; |
323 | |
324 | protected: |
325 | // Default ctor - Initialize to empty. |
326 | explicit SmallVectorImpl(unsigned N) |
327 | : SmallVectorTemplateBase<T>(N) {} |
328 | |
329 | public: |
330 | SmallVectorImpl(const SmallVectorImpl &) = delete; |
331 | |
332 | ~SmallVectorImpl() { |
333 | // Subclass has already destructed this vector's elements. |
334 | // If this wasn't grown from the inline copy, deallocate the old space. |
335 | if (!this->isSmall()) |
336 | free(this->begin()); |
337 | } |
338 | |
339 | void clear() { |
340 | this->destroy_range(this->begin(), this->end()); |
341 | this->Size = 0; |
342 | } |
343 | |
344 | void resize(size_type N) { |
345 | if (N < this->size()) { |
346 | this->destroy_range(this->begin()+N, this->end()); |
347 | this->set_size(N); |
348 | } else if (N > this->size()) { |
349 | if (this->capacity() < N) |
350 | this->grow(N); |
351 | for (auto I = this->end(), E = this->begin() + N; I != E; ++I) |
352 | new (&*I) T(); |
353 | this->set_size(N); |
354 | } |
355 | } |
356 | |
357 | void resize(size_type N, const T &NV) { |
358 | if (N < this->size()) { |
359 | this->destroy_range(this->begin()+N, this->end()); |
360 | this->set_size(N); |
361 | } else if (N > this->size()) { |
362 | if (this->capacity() < N) |
363 | this->grow(N); |
364 | std::uninitialized_fill(this->end(), this->begin()+N, NV); |
365 | this->set_size(N); |
366 | } |
367 | } |
368 | |
369 | void reserve(size_type N) { |
370 | if (this->capacity() < N) |
371 | this->grow(N); |
372 | } |
373 | |
374 | LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() { |
375 | T Result = ::std::move(this->back()); |
376 | this->pop_back(); |
377 | return Result; |
378 | } |
379 | |
380 | void swap(SmallVectorImpl &RHS); |
381 | |
382 | /// Add the specified range to the end of the SmallVector. |
383 | template <typename in_iter, |
384 | typename = typename std::enable_if<std::is_convertible< |
385 | typename std::iterator_traits<in_iter>::iterator_category, |
386 | std::input_iterator_tag>::value>::type> |
387 | void append(in_iter in_start, in_iter in_end) { |
388 | size_type NumInputs = std::distance(in_start, in_end); |
389 | if (NumInputs > this->capacity() - this->size()) |
390 | this->grow(this->size()+NumInputs); |
391 | |
392 | this->uninitialized_copy(in_start, in_end, this->end()); |
393 | this->set_size(this->size() + NumInputs); |
394 | } |
395 | |
396 | /// Append \p NumInputs copies of \p Elt to the end. |
397 | void append(size_type NumInputs, const T &Elt) { |
398 | if (NumInputs > this->capacity() - this->size()) |
399 | this->grow(this->size()+NumInputs); |
400 | |
401 | std::uninitialized_fill_n(this->end(), NumInputs, Elt); |
402 | this->set_size(this->size() + NumInputs); |
403 | } |
404 | |
405 | void append(std::initializer_list<T> IL) { |
406 | append(IL.begin(), IL.end()); |
407 | } |
408 | |
409 | // FIXME: Consider assigning over existing elements, rather than clearing & |
410 | // re-initializing them - for all assign(...) variants. |
411 | |
412 | void assign(size_type NumElts, const T &Elt) { |
413 | clear(); |
414 | if (this->capacity() < NumElts) |
415 | this->grow(NumElts); |
416 | this->set_size(NumElts); |
417 | std::uninitialized_fill(this->begin(), this->end(), Elt); |
418 | } |
419 | |
420 | template <typename in_iter, |
421 | typename = typename std::enable_if<std::is_convertible< |
422 | typename std::iterator_traits<in_iter>::iterator_category, |
423 | std::input_iterator_tag>::value>::type> |
424 | void assign(in_iter in_start, in_iter in_end) { |
425 | clear(); |
426 | append(in_start, in_end); |
427 | } |
428 | |
429 | void assign(std::initializer_list<T> IL) { |
430 | clear(); |
431 | append(IL); |
432 | } |
433 | |
434 | iterator erase(const_iterator CI) { |
435 | // Just cast away constness because this is a non-const member function. |
436 | iterator I = const_cast<iterator>(CI); |
437 | |
438 | assert(I >= this->begin() && "Iterator to erase is out of bounds.")((I >= this->begin() && "Iterator to erase is out of bounds." ) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Iterator to erase is out of bounds.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 438, __PRETTY_FUNCTION__)); |
439 | assert(I < this->end() && "Erasing at past-the-end iterator.")((I < this->end() && "Erasing at past-the-end iterator." ) ? static_cast<void> (0) : __assert_fail ("I < this->end() && \"Erasing at past-the-end iterator.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 439, __PRETTY_FUNCTION__)); |
440 | |
441 | iterator N = I; |
442 | // Shift all elts down one. |
443 | std::move(I+1, this->end(), I); |
444 | // Drop the last elt. |
445 | this->pop_back(); |
446 | return(N); |
447 | } |
448 | |
449 | iterator erase(const_iterator CS, const_iterator CE) { |
450 | // Just cast away constness because this is a non-const member function. |
451 | iterator S = const_cast<iterator>(CS); |
452 | iterator E = const_cast<iterator>(CE); |
453 | |
454 | assert(S >= this->begin() && "Range to erase is out of bounds.")((S >= this->begin() && "Range to erase is out of bounds." ) ? static_cast<void> (0) : __assert_fail ("S >= this->begin() && \"Range to erase is out of bounds.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 454, __PRETTY_FUNCTION__)); |
455 | assert(S <= E && "Trying to erase invalid range.")((S <= E && "Trying to erase invalid range.") ? static_cast <void> (0) : __assert_fail ("S <= E && \"Trying to erase invalid range.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 455, __PRETTY_FUNCTION__)); |
456 | assert(E <= this->end() && "Trying to erase past the end.")((E <= this->end() && "Trying to erase past the end." ) ? static_cast<void> (0) : __assert_fail ("E <= this->end() && \"Trying to erase past the end.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 456, __PRETTY_FUNCTION__)); |
457 | |
458 | iterator N = S; |
459 | // Shift all elts down. |
460 | iterator I = std::move(E, this->end(), S); |
461 | // Drop the last elts. |
462 | this->destroy_range(I, this->end()); |
463 | this->set_size(I - this->begin()); |
464 | return(N); |
465 | } |
466 | |
467 | iterator insert(iterator I, T &&Elt) { |
468 | if (I == this->end()) { // Important special case for empty vector. |
469 | this->push_back(::std::move(Elt)); |
470 | return this->end()-1; |
471 | } |
472 | |
473 | assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds." ) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 473, __PRETTY_FUNCTION__)); |
474 | assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector." ) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 474, __PRETTY_FUNCTION__)); |
475 | |
476 | if (this->size() >= this->capacity()) { |
477 | size_t EltNo = I-this->begin(); |
478 | this->grow(); |
479 | I = this->begin()+EltNo; |
480 | } |
481 | |
482 | ::new ((void*) this->end()) T(::std::move(this->back())); |
483 | // Push everything else over. |
484 | std::move_backward(I, this->end()-1, this->end()); |
485 | this->set_size(this->size() + 1); |
486 | |
487 | // If we just moved the element we're inserting, be sure to update |
488 | // the reference. |
489 | T *EltPtr = &Elt; |
490 | if (I <= EltPtr && EltPtr < this->end()) |
491 | ++EltPtr; |
492 | |
493 | *I = ::std::move(*EltPtr); |
494 | return I; |
495 | } |
496 | |
497 | iterator insert(iterator I, const T &Elt) { |
498 | if (I == this->end()) { // Important special case for empty vector. |
499 | this->push_back(Elt); |
500 | return this->end()-1; |
501 | } |
502 | |
503 | assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds." ) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 503, __PRETTY_FUNCTION__)); |
504 | assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector." ) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 504, __PRETTY_FUNCTION__)); |
505 | |
506 | if (this->size() >= this->capacity()) { |
507 | size_t EltNo = I-this->begin(); |
508 | this->grow(); |
509 | I = this->begin()+EltNo; |
510 | } |
511 | ::new ((void*) this->end()) T(std::move(this->back())); |
512 | // Push everything else over. |
513 | std::move_backward(I, this->end()-1, this->end()); |
514 | this->set_size(this->size() + 1); |
515 | |
516 | // If we just moved the element we're inserting, be sure to update |
517 | // the reference. |
518 | const T *EltPtr = &Elt; |
519 | if (I <= EltPtr && EltPtr < this->end()) |
520 | ++EltPtr; |
521 | |
522 | *I = *EltPtr; |
523 | return I; |
524 | } |
525 | |
526 | iterator insert(iterator I, size_type NumToInsert, const T &Elt) { |
527 | // Convert iterator to elt# to avoid invalidating iterator when we reserve() |
528 | size_t InsertElt = I - this->begin(); |
529 | |
530 | if (I == this->end()) { // Important special case for empty vector. |
531 | append(NumToInsert, Elt); |
532 | return this->begin()+InsertElt; |
533 | } |
534 | |
535 | assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds." ) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 535, __PRETTY_FUNCTION__)); |
536 | assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector." ) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 536, __PRETTY_FUNCTION__)); |
537 | |
538 | // Ensure there is enough space. |
539 | reserve(this->size() + NumToInsert); |
540 | |
541 | // Uninvalidate the iterator. |
542 | I = this->begin()+InsertElt; |
543 | |
544 | // If there are more elements between the insertion point and the end of the |
545 | // range than there are being inserted, we can use a simple approach to |
546 | // insertion. Since we already reserved space, we know that this won't |
547 | // reallocate the vector. |
548 | if (size_t(this->end()-I) >= NumToInsert) { |
549 | T *OldEnd = this->end(); |
550 | append(std::move_iterator<iterator>(this->end() - NumToInsert), |
551 | std::move_iterator<iterator>(this->end())); |
552 | |
553 | // Copy the existing elements that get replaced. |
554 | std::move_backward(I, OldEnd-NumToInsert, OldEnd); |
555 | |
556 | std::fill_n(I, NumToInsert, Elt); |
557 | return I; |
558 | } |
559 | |
560 | // Otherwise, we're inserting more elements than exist already, and we're |
561 | // not inserting at the end. |
562 | |
563 | // Move over the elements that we're about to overwrite. |
564 | T *OldEnd = this->end(); |
565 | this->set_size(this->size() + NumToInsert); |
566 | size_t NumOverwritten = OldEnd-I; |
567 | this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); |
568 | |
569 | // Replace the overwritten part. |
570 | std::fill_n(I, NumOverwritten, Elt); |
571 | |
572 | // Insert the non-overwritten middle part. |
573 | std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); |
574 | return I; |
575 | } |
576 | |
577 | template <typename ItTy, |
578 | typename = typename std::enable_if<std::is_convertible< |
579 | typename std::iterator_traits<ItTy>::iterator_category, |
580 | std::input_iterator_tag>::value>::type> |
581 | iterator insert(iterator I, ItTy From, ItTy To) { |
582 | // Convert iterator to elt# to avoid invalidating iterator when we reserve() |
583 | size_t InsertElt = I - this->begin(); |
584 | |
585 | if (I == this->end()) { // Important special case for empty vector. |
586 | append(From, To); |
587 | return this->begin()+InsertElt; |
588 | } |
589 | |
590 | assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds." ) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 590, __PRETTY_FUNCTION__)); |
591 | assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector." ) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\"" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h" , 591, __PRETTY_FUNCTION__)); |
592 | |
593 | size_t NumToInsert = std::distance(From, To); |
594 | |
595 | // Ensure there is enough space. |
596 | reserve(this->size() + NumToInsert); |
597 | |
598 | // Uninvalidate the iterator. |
599 | I = this->begin()+InsertElt; |
600 | |
601 | // If there are more elements between the insertion point and the end of the |
602 | // range than there are being inserted, we can use a simple approach to |
603 | // insertion. Since we already reserved space, we know that this won't |
604 | // reallocate the vector. |
605 | if (size_t(this->end()-I) >= NumToInsert) { |
606 | T *OldEnd = this->end(); |
607 | append(std::move_iterator<iterator>(this->end() - NumToInsert), |
608 | std::move_iterator<iterator>(this->end())); |
609 | |
610 | // Copy the existing elements that get replaced. |
611 | std::move_backward(I, OldEnd-NumToInsert, OldEnd); |
612 | |
613 | std::copy(From, To, I); |
614 | return I; |
615 | } |
616 | |
617 | // Otherwise, we're inserting more elements than exist already, and we're |
618 | // not inserting at the end. |
619 | |
620 | // Move over the elements that we're about to overwrite. |
621 | T *OldEnd = this->end(); |
622 | this->set_size(this->size() + NumToInsert); |
623 | size_t NumOverwritten = OldEnd-I; |
624 | this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); |
625 | |
626 | // Replace the overwritten part. |
627 | for (T *J = I; NumOverwritten > 0; --NumOverwritten) { |
628 | *J = *From; |
629 | ++J; ++From; |
630 | } |
631 | |
632 | // Insert the non-overwritten middle part. |
633 | this->uninitialized_copy(From, To, OldEnd); |
634 | return I; |
635 | } |
636 | |
637 | void insert(iterator I, std::initializer_list<T> IL) { |
638 | insert(I, IL.begin(), IL.end()); |
639 | } |
640 | |
641 | template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) { |
642 | if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity ()), false)) |
643 | this->grow(); |
644 | ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); |
645 | this->set_size(this->size() + 1); |
646 | return this->back(); |
647 | } |
648 | |
649 | SmallVectorImpl &operator=(const SmallVectorImpl &RHS); |
650 | |
651 | SmallVectorImpl &operator=(SmallVectorImpl &&RHS); |
652 | |
653 | bool operator==(const SmallVectorImpl &RHS) const { |
654 | if (this->size() != RHS.size()) return false; |
655 | return std::equal(this->begin(), this->end(), RHS.begin()); |
656 | } |
657 | bool operator!=(const SmallVectorImpl &RHS) const { |
658 | return !(*this == RHS); |
659 | } |
660 | |
661 | bool operator<(const SmallVectorImpl &RHS) const { |
662 | return std::lexicographical_compare(this->begin(), this->end(), |
663 | RHS.begin(), RHS.end()); |
664 | } |
665 | }; |
666 | |
667 | template <typename T> |
668 | void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { |
669 | if (this == &RHS) return; |
670 | |
671 | // We can only avoid copying elements if neither vector is small. |
672 | if (!this->isSmall() && !RHS.isSmall()) { |
673 | std::swap(this->BeginX, RHS.BeginX); |
674 | std::swap(this->Size, RHS.Size); |
675 | std::swap(this->Capacity, RHS.Capacity); |
676 | return; |
677 | } |
678 | if (RHS.size() > this->capacity()) |
679 | this->grow(RHS.size()); |
680 | if (this->size() > RHS.capacity()) |
681 | RHS.grow(this->size()); |
682 | |
683 | // Swap the shared elements. |
684 | size_t NumShared = this->size(); |
685 | if (NumShared > RHS.size()) NumShared = RHS.size(); |
686 | for (size_type i = 0; i != NumShared; ++i) |
687 | std::swap((*this)[i], RHS[i]); |
688 | |
689 | // Copy over the extra elts. |
690 | if (this->size() > RHS.size()) { |
691 | size_t EltDiff = this->size() - RHS.size(); |
692 | this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); |
693 | RHS.set_size(RHS.size() + EltDiff); |
694 | this->destroy_range(this->begin()+NumShared, this->end()); |
695 | this->set_size(NumShared); |
696 | } else if (RHS.size() > this->size()) { |
697 | size_t EltDiff = RHS.size() - this->size(); |
698 | this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); |
699 | this->set_size(this->size() + EltDiff); |
700 | this->destroy_range(RHS.begin()+NumShared, RHS.end()); |
701 | RHS.set_size(NumShared); |
702 | } |
703 | } |
704 | |
705 | template <typename T> |
706 | SmallVectorImpl<T> &SmallVectorImpl<T>:: |
707 | operator=(const SmallVectorImpl<T> &RHS) { |
708 | // Avoid self-assignment. |
709 | if (this == &RHS) return *this; |
710 | |
711 | // If we already have sufficient space, assign the common elements, then |
712 | // destroy any excess. |
713 | size_t RHSSize = RHS.size(); |
714 | size_t CurSize = this->size(); |
715 | if (CurSize >= RHSSize) { |
716 | // Assign common elements. |
717 | iterator NewEnd; |
718 | if (RHSSize) |
719 | NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); |
720 | else |
721 | NewEnd = this->begin(); |
722 | |
723 | // Destroy excess elements. |
724 | this->destroy_range(NewEnd, this->end()); |
725 | |
726 | // Trim. |
727 | this->set_size(RHSSize); |
728 | return *this; |
729 | } |
730 | |
731 | // If we have to grow to have enough elements, destroy the current elements. |
732 | // This allows us to avoid copying them during the grow. |
733 | // FIXME: don't do this if they're efficiently moveable. |
734 | if (this->capacity() < RHSSize) { |
735 | // Destroy current elements. |
736 | this->destroy_range(this->begin(), this->end()); |
737 | this->set_size(0); |
738 | CurSize = 0; |
739 | this->grow(RHSSize); |
740 | } else if (CurSize) { |
741 | // Otherwise, use assignment for the already-constructed elements. |
742 | std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); |
743 | } |
744 | |
745 | // Copy construct the new elements in place. |
746 | this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), |
747 | this->begin()+CurSize); |
748 | |
749 | // Set end. |
750 | this->set_size(RHSSize); |
751 | return *this; |
752 | } |
753 | |
754 | template <typename T> |
755 | SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { |
756 | // Avoid self-assignment. |
757 | if (this == &RHS) return *this; |
758 | |
759 | // If the RHS isn't small, clear this vector and then steal its buffer. |
760 | if (!RHS.isSmall()) { |
761 | this->destroy_range(this->begin(), this->end()); |
762 | if (!this->isSmall()) free(this->begin()); |
763 | this->BeginX = RHS.BeginX; |
764 | this->Size = RHS.Size; |
765 | this->Capacity = RHS.Capacity; |
766 | RHS.resetToSmall(); |
767 | return *this; |
768 | } |
769 | |
770 | // If we already have sufficient space, assign the common elements, then |
771 | // destroy any excess. |
772 | size_t RHSSize = RHS.size(); |
773 | size_t CurSize = this->size(); |
774 | if (CurSize >= RHSSize) { |
775 | // Assign common elements. |
776 | iterator NewEnd = this->begin(); |
777 | if (RHSSize) |
778 | NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd); |
779 | |
780 | // Destroy excess elements and trim the bounds. |
781 | this->destroy_range(NewEnd, this->end()); |
782 | this->set_size(RHSSize); |
783 | |
784 | // Clear the RHS. |
785 | RHS.clear(); |
786 | |
787 | return *this; |
788 | } |
789 | |
790 | // If we have to grow to have enough elements, destroy the current elements. |
791 | // This allows us to avoid copying them during the grow. |
792 | // FIXME: this may not actually make any sense if we can efficiently move |
793 | // elements. |
794 | if (this->capacity() < RHSSize) { |
795 | // Destroy current elements. |
796 | this->destroy_range(this->begin(), this->end()); |
797 | this->set_size(0); |
798 | CurSize = 0; |
799 | this->grow(RHSSize); |
800 | } else if (CurSize) { |
801 | // Otherwise, use assignment for the already-constructed elements. |
802 | std::move(RHS.begin(), RHS.begin()+CurSize, this->begin()); |
803 | } |
804 | |
805 | // Move-construct the new elements in place. |
806 | this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), |
807 | this->begin()+CurSize); |
808 | |
809 | // Set end. |
810 | this->set_size(RHSSize); |
811 | |
812 | RHS.clear(); |
813 | return *this; |
814 | } |
815 | |
816 | /// Storage for the SmallVector elements. This is specialized for the N=0 case |
817 | /// to avoid allocating unnecessary storage. |
818 | template <typename T, unsigned N> |
819 | struct SmallVectorStorage { |
820 | AlignedCharArrayUnion<T> InlineElts[N]; |
821 | }; |
822 | |
823 | /// We need the storage to be properly aligned even for small-size of 0 so that |
824 | /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is |
825 | /// well-defined. |
826 | template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {}; |
827 | |
828 | /// This is a 'vector' (really, a variable-sized array), optimized |
829 | /// for the case when the array is small. It contains some number of elements |
830 | /// in-place, which allows it to avoid heap allocation when the actual number of |
831 | /// elements is below that threshold. This allows normal "small" cases to be |
832 | /// fast without losing generality for large inputs. |
833 | /// |
834 | /// Note that this does not attempt to be exception safe. |
835 | /// |
836 | template <typename T, unsigned N> |
837 | class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> { |
838 | public: |
839 | SmallVector() : SmallVectorImpl<T>(N) {} |
840 | |
841 | ~SmallVector() { |
842 | // Destroy the constructed elements in the vector. |
843 | this->destroy_range(this->begin(), this->end()); |
844 | } |
845 | |
846 | explicit SmallVector(size_t Size, const T &Value = T()) |
847 | : SmallVectorImpl<T>(N) { |
848 | this->assign(Size, Value); |
849 | } |
850 | |
851 | template <typename ItTy, |
852 | typename = typename std::enable_if<std::is_convertible< |
853 | typename std::iterator_traits<ItTy>::iterator_category, |
854 | std::input_iterator_tag>::value>::type> |
855 | SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { |
856 | this->append(S, E); |
857 | } |
858 | |
859 | template <typename RangeTy> |
860 | explicit SmallVector(const iterator_range<RangeTy> &R) |
861 | : SmallVectorImpl<T>(N) { |
862 | this->append(R.begin(), R.end()); |
863 | } |
864 | |
865 | SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) { |
866 | this->assign(IL); |
867 | } |
868 | |
869 | SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { |
870 | if (!RHS.empty()) |
871 | SmallVectorImpl<T>::operator=(RHS); |
872 | } |
873 | |
874 | const SmallVector &operator=(const SmallVector &RHS) { |
875 | SmallVectorImpl<T>::operator=(RHS); |
876 | return *this; |
877 | } |
878 | |
879 | SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { |
880 | if (!RHS.empty()) |
881 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
882 | } |
883 | |
884 | SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) { |
885 | if (!RHS.empty()) |
886 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
887 | } |
888 | |
889 | const SmallVector &operator=(SmallVector &&RHS) { |
890 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
891 | return *this; |
892 | } |
893 | |
894 | const SmallVector &operator=(SmallVectorImpl<T> &&RHS) { |
895 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
896 | return *this; |
897 | } |
898 | |
899 | const SmallVector &operator=(std::initializer_list<T> IL) { |
900 | this->assign(IL); |
901 | return *this; |
902 | } |
903 | }; |
904 | |
905 | template <typename T, unsigned N> |
906 | inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { |
907 | return X.capacity_in_bytes(); |
908 | } |
909 | |
910 | } // end namespace llvm |
911 | |
912 | namespace std { |
913 | |
914 | /// Implement std::swap in terms of SmallVector swap. |
915 | template<typename T> |
916 | inline void |
917 | swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { |
918 | LHS.swap(RHS); |
919 | } |
920 | |
921 | /// Implement std::swap in terms of SmallVector swap. |
922 | template<typename T, unsigned N> |
923 | inline void |
924 | swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { |
925 | LHS.swap(RHS); |
926 | } |
927 | |
928 | } // end namespace std |
929 | |
930 | #endif // LLVM_ADT_SMALLVECTOR_H |