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 representation of an mca::Instruction operand |
37 | /// for use in mca::CustomBehaviour. |
38 | class MCAOperand { |
39 | // This class is mostly copied from MCOperand within |
40 | // MCInst.h except that we don't keep track of |
41 | // expressions or sub-instructions. |
42 | enum MCAOperandType : unsigned char { |
43 | kInvalid, ///< Uninitialized, Relocatable immediate, or Sub-instruction. |
44 | kRegister, ///< Register operand. |
45 | kImmediate, ///< Immediate operand. |
46 | kSFPImmediate, ///< Single-floating-point immediate operand. |
47 | kDFPImmediate, ///< Double-Floating-point immediate operand. |
48 | }; |
49 | MCAOperandType Kind = kInvalid; |
50 | |
51 | union { |
52 | unsigned RegVal; |
53 | int64_t ImmVal; |
54 | uint32_t SFPImmVal; |
55 | uint64_t FPImmVal; |
56 | }; |
57 | |
58 | // We only store specific operands for specific instructions |
59 | // so an instruction's operand 3 may be stored within the list |
60 | // of MCAOperand as element 0. This Index attribute keeps track |
61 | // of the original index (3 for this example). |
62 | unsigned Index; |
63 | |
64 | public: |
65 | MCAOperand() : FPImmVal(0) {} |
66 | |
67 | bool isValid() const { return Kind != kInvalid; } |
68 | bool isReg() const { return Kind == kRegister; } |
69 | bool isImm() const { return Kind == kImmediate; } |
70 | bool isSFPImm() const { return Kind == kSFPImmediate; } |
71 | bool isDFPImm() const { return Kind == kDFPImmediate; } |
72 | |
73 | /// Returns the register number. |
74 | unsigned getReg() const { |
75 | assert(isReg() && "This is not a register operand!")(static_cast <bool> (isReg() && "This is not a register operand!" ) ? void (0) : __assert_fail ("isReg() && \"This is not a register operand!\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h" , 75, __extension__ __PRETTY_FUNCTION__)); |
76 | return RegVal; |
77 | } |
78 | |
79 | int64_t getImm() const { |
80 | assert(isImm() && "This is not an immediate")(static_cast <bool> (isImm() && "This is not an immediate" ) ? void (0) : __assert_fail ("isImm() && \"This is not an immediate\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h" , 80, __extension__ __PRETTY_FUNCTION__)); |
81 | return ImmVal; |
82 | } |
83 | |
84 | uint32_t getSFPImm() const { |
85 | assert(isSFPImm() && "This is not an SFP immediate")(static_cast <bool> (isSFPImm() && "This is not an SFP immediate" ) ? void (0) : __assert_fail ("isSFPImm() && \"This is not an SFP immediate\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h" , 85, __extension__ __PRETTY_FUNCTION__)); |
86 | return SFPImmVal; |
87 | } |
88 | |
89 | uint64_t getDFPImm() const { |
90 | assert(isDFPImm() && "This is not an FP immediate")(static_cast <bool> (isDFPImm() && "This is not an FP immediate" ) ? void (0) : __assert_fail ("isDFPImm() && \"This is not an FP immediate\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h" , 90, __extension__ __PRETTY_FUNCTION__)); |
91 | return FPImmVal; |
92 | } |
93 | |
94 | void setIndex(const unsigned Idx) { Index = Idx; } |
95 | |
96 | unsigned getIndex() const { return Index; } |
97 | |
98 | static MCAOperand createReg(unsigned Reg) { |
99 | MCAOperand Op; |
100 | Op.Kind = kRegister; |
101 | Op.RegVal = Reg; |
102 | return Op; |
103 | } |
104 | |
105 | static MCAOperand createImm(int64_t Val) { |
106 | MCAOperand Op; |
107 | Op.Kind = kImmediate; |
108 | Op.ImmVal = Val; |
109 | return Op; |
110 | } |
111 | |
112 | static MCAOperand createSFPImm(uint32_t Val) { |
113 | MCAOperand Op; |
114 | Op.Kind = kSFPImmediate; |
115 | Op.SFPImmVal = Val; |
116 | return Op; |
117 | } |
118 | |
119 | static MCAOperand createDFPImm(uint64_t Val) { |
120 | MCAOperand Op; |
121 | Op.Kind = kDFPImmediate; |
122 | Op.FPImmVal = Val; |
123 | return Op; |
124 | } |
125 | |
126 | static MCAOperand createInvalid() { |
127 | MCAOperand Op; |
128 | Op.Kind = kInvalid; |
129 | Op.FPImmVal = 0; |
130 | return Op; |
131 | } |
132 | }; |
133 | |
134 | /// A register write descriptor. |
135 | struct WriteDescriptor { |
136 | // Operand index. The index is negative for implicit writes only. |
137 | // For implicit writes, the actual operand index is computed performing |
138 | // a bitwise not of the OpIndex. |
139 | int OpIndex; |
140 | // Write latency. Number of cycles before write-back stage. |
141 | unsigned Latency; |
142 | // This field is set to a value different than zero only if this |
143 | // is an implicit definition. |
144 | MCPhysReg RegisterID; |
145 | // Instruction itineraries would set this field to the SchedClass ID. |
146 | // Otherwise, it defaults to the WriteResourceID from the MCWriteLatencyEntry |
147 | // element associated to this write. |
148 | // When computing read latencies, this value is matched against the |
149 | // "ReadAdvance" information. The hardware backend may implement |
150 | // dedicated forwarding paths to quickly propagate write results to dependent |
151 | // instructions waiting in the reservation station (effectively bypassing the |
152 | // write-back stage). |
153 | unsigned SClassOrWriteResourceID; |
154 | // True only if this is a write obtained from an optional definition. |
155 | // Optional definitions are allowed to reference regID zero (i.e. "no |
156 | // register"). |
157 | bool IsOptionalDef; |
158 | |
159 | bool isImplicitWrite() const { return OpIndex < 0; }; |
160 | }; |
161 | |
162 | /// A register read descriptor. |
163 | struct ReadDescriptor { |
164 | // A MCOperand index. This is used by the Dispatch logic to identify register |
165 | // reads. Implicit reads have negative indices. The actual operand index of an |
166 | // implicit read is the bitwise not of field OpIndex. |
167 | int OpIndex; |
168 | // The actual "UseIdx". This is used to query the ReadAdvance table. Explicit |
169 | // uses always come first in the sequence of uses. |
170 | unsigned UseIndex; |
171 | // This field is only set if this is an implicit read. |
172 | MCPhysReg RegisterID; |
173 | // Scheduling Class Index. It is used to query the scheduling model for the |
174 | // MCSchedClassDesc object. |
175 | unsigned SchedClassID; |
176 | |
177 | bool isImplicitRead() const { return OpIndex < 0; }; |
178 | }; |
179 | |
180 | class ReadState; |
181 | |
182 | /// A critical data dependency descriptor. |
183 | /// |
184 | /// Field RegID is set to the invalid register for memory dependencies. |
185 | struct CriticalDependency { |
186 | unsigned IID; |
187 | MCPhysReg RegID; |
188 | unsigned Cycles; |
189 | }; |
190 | |
191 | /// Tracks uses of a register definition (e.g. register write). |
192 | /// |
193 | /// Each implicit/explicit register write is associated with an instance of |
194 | /// this class. A WriteState object tracks the dependent users of a |
195 | /// register write. It also tracks how many cycles are left before the write |
196 | /// back stage. |
197 | class WriteState { |
198 | const WriteDescriptor *WD; |
199 | // On instruction issue, this field is set equal to the write latency. |
200 | // Before instruction issue, this field defaults to -512, a special |
201 | // value that represents an "unknown" number of cycles. |
202 | int CyclesLeft; |
203 | |
204 | // Actual register defined by this write. This field is only used |
205 | // to speedup queries on the register file. |
206 | // For implicit writes, this field always matches the value of |
207 | // field RegisterID from WD. |
208 | MCPhysReg RegisterID; |
209 | |
210 | // Physical register file that serves register RegisterID. |
211 | unsigned PRFID; |
212 | |
213 | // True if this write implicitly clears the upper portion of RegisterID's |
214 | // super-registers. |
215 | bool ClearsSuperRegs; |
216 | |
217 | // True if this write is from a dependency breaking zero-idiom instruction. |
218 | bool WritesZero; |
219 | |
220 | // True if this write has been eliminated at register renaming stage. |
221 | // Example: a register move doesn't consume scheduler/pipleline resources if |
222 | // it is eliminated at register renaming stage. It still consumes |
223 | // decode bandwidth, and ROB entries. |
224 | bool IsEliminated; |
225 | |
226 | // This field is set if this is a partial register write, and it has a false |
227 | // dependency on any previous write of the same register (or a portion of it). |
228 | // DependentWrite must be able to complete before this write completes, so |
229 | // that we don't break the WAW, and the two writes can be merged together. |
230 | const WriteState *DependentWrite; |
231 | |
232 | // A partial write that is in a false dependency with this write. |
233 | WriteState *PartialWrite; |
234 | unsigned DependentWriteCyclesLeft; |
235 | |
236 | // Critical register dependency for this write. |
237 | CriticalDependency CRD; |
238 | |
239 | // A list of dependent reads. Users is a set of dependent |
240 | // reads. A dependent read is added to the set only if CyclesLeft |
241 | // is "unknown". As soon as CyclesLeft is 'known', each user in the set |
242 | // gets notified with the actual CyclesLeft. |
243 | |
244 | // The 'second' element of a pair is a "ReadAdvance" number of cycles. |
245 | SmallVector<std::pair<ReadState *, int>, 4> Users; |
246 | |
247 | public: |
248 | WriteState(const WriteDescriptor &Desc, MCPhysReg RegID, |
249 | bool clearsSuperRegs = false, bool writesZero = false) |
250 | : WD(&Desc), CyclesLeft(UNKNOWN_CYCLES), RegisterID(RegID), PRFID(0), |
251 | ClearsSuperRegs(clearsSuperRegs), WritesZero(writesZero), |
252 | IsEliminated(false), DependentWrite(nullptr), PartialWrite(nullptr), |
253 | DependentWriteCyclesLeft(0), CRD() {} |
254 | |
255 | WriteState(const WriteState &Other) = default; |
256 | WriteState &operator=(const WriteState &Other) = default; |
257 | |
258 | int getCyclesLeft() const { return CyclesLeft; } |
259 | unsigned getWriteResourceID() const { return WD->SClassOrWriteResourceID; } |
260 | MCPhysReg getRegisterID() const { return RegisterID; } |
261 | void setRegisterID(const MCPhysReg RegID) { RegisterID = RegID; } |
262 | unsigned getRegisterFileID() const { return PRFID; } |
263 | unsigned getLatency() const { return WD->Latency; } |
264 | unsigned getDependentWriteCyclesLeft() const { |
265 | return DependentWriteCyclesLeft; |
266 | } |
267 | const WriteState *getDependentWrite() const { return DependentWrite; } |
268 | const CriticalDependency &getCriticalRegDep() const { return CRD; } |
269 | |
270 | // This method adds Use to the set of data dependent reads. IID is the |
271 | // instruction identifier associated with this write. ReadAdvance is the |
272 | // number of cycles to subtract from the latency of this data dependency. |
273 | // Use is in a RAW dependency with this write. |
274 | void addUser(unsigned IID, ReadState *Use, int ReadAdvance); |
275 | |
276 | // Use is a younger register write that is in a false dependency with this |
277 | // write. IID is the instruction identifier associated with this write. |
278 | void addUser(unsigned IID, WriteState *Use); |
279 | |
280 | unsigned getNumUsers() const { |
281 | unsigned NumUsers = Users.size(); |
282 | if (PartialWrite) |
283 | ++NumUsers; |
284 | return NumUsers; |
285 | } |
286 | |
287 | bool clearsSuperRegisters() const { return ClearsSuperRegs; } |
288 | bool isWriteZero() const { return WritesZero; } |
289 | bool isEliminated() const { return IsEliminated; } |
290 | |
291 | bool isReady() const { |
292 | if (DependentWrite) |
293 | return false; |
294 | unsigned CyclesLeft = getDependentWriteCyclesLeft(); |
295 | return !CyclesLeft || CyclesLeft < getLatency(); |
296 | } |
297 | |
298 | bool isExecuted() const { |
299 | return CyclesLeft != UNKNOWN_CYCLES && CyclesLeft <= 0; |
300 | } |
301 | |
302 | void setDependentWrite(const WriteState *Other) { DependentWrite = Other; } |
303 | void writeStartEvent(unsigned IID, MCPhysReg RegID, unsigned Cycles); |
304 | void setWriteZero() { WritesZero = true; } |
305 | void setEliminated() { |
306 | assert(Users.empty() && "Write is in an inconsistent state.")(static_cast <bool> (Users.empty() && "Write is in an inconsistent state." ) ? void (0) : __assert_fail ("Users.empty() && \"Write is in an inconsistent state.\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h" , 306, __extension__ __PRETTY_FUNCTION__)); |
307 | CyclesLeft = 0; |
308 | IsEliminated = true; |
309 | } |
310 | |
311 | void setPRF(unsigned PRF) { PRFID = PRF; } |
312 | |
313 | // On every cycle, update CyclesLeft and notify dependent users. |
314 | void cycleEvent(); |
315 | void onInstructionIssued(unsigned IID); |
316 | |
317 | #ifndef NDEBUG |
318 | void dump() const; |
319 | #endif |
320 | }; |
321 | |
322 | /// Tracks register operand latency in cycles. |
323 | /// |
324 | /// A read may be dependent on more than one write. This occurs when some |
325 | /// writes only partially update the register associated to this read. |
326 | class ReadState { |
327 | const ReadDescriptor *RD; |
328 | // Physical register identified associated to this read. |
329 | MCPhysReg RegisterID; |
330 | // Physical register file that serves register RegisterID. |
331 | unsigned PRFID; |
332 | // Number of writes that contribute to the definition of RegisterID. |
333 | // In the absence of partial register updates, the number of DependentWrites |
334 | // cannot be more than one. |
335 | unsigned DependentWrites; |
336 | // Number of cycles left before RegisterID can be read. This value depends on |
337 | // the latency of all the dependent writes. It defaults to UNKNOWN_CYCLES. |
338 | // It gets set to the value of field TotalCycles only when the 'CyclesLeft' of |
339 | // every dependent write is known. |
340 | int CyclesLeft; |
341 | // This field is updated on every writeStartEvent(). When the number of |
342 | // dependent writes (i.e. field DependentWrite) is zero, this value is |
343 | // propagated to field CyclesLeft. |
344 | unsigned TotalCycles; |
345 | // Longest register dependency. |
346 | CriticalDependency CRD; |
347 | // This field is set to true only if there are no dependent writes, and |
348 | // there are no `CyclesLeft' to wait. |
349 | bool IsReady; |
350 | // True if this is a read from a known zero register. |
351 | bool IsZero; |
352 | // True if this register read is from a dependency-breaking instruction. |
353 | bool IndependentFromDef; |
354 | |
355 | public: |
356 | ReadState(const ReadDescriptor &Desc, MCPhysReg RegID) |
357 | : RD(&Desc), RegisterID(RegID), PRFID(0), DependentWrites(0), |
358 | CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0), CRD(), IsReady(true), |
359 | IsZero(false), IndependentFromDef(false) {} |
360 | |
361 | const ReadDescriptor &getDescriptor() const { return *RD; } |
362 | unsigned getSchedClass() const { return RD->SchedClassID; } |
363 | MCPhysReg getRegisterID() const { return RegisterID; } |
364 | unsigned getRegisterFileID() const { return PRFID; } |
365 | const CriticalDependency &getCriticalRegDep() const { return CRD; } |
366 | |
367 | bool isPending() const { return !IndependentFromDef && CyclesLeft > 0; } |
368 | bool isReady() const { return IsReady; } |
369 | bool isImplicitRead() const { return RD->isImplicitRead(); } |
370 | |
371 | bool isIndependentFromDef() const { return IndependentFromDef; } |
372 | void setIndependentFromDef() { IndependentFromDef = true; } |
373 | |
374 | void cycleEvent(); |
375 | void writeStartEvent(unsigned IID, MCPhysReg RegID, unsigned Cycles); |
376 | void setDependentWrites(unsigned Writes) { |
377 | DependentWrites = Writes; |
378 | IsReady = !Writes; |
379 | } |
380 | |
381 | bool isReadZero() const { return IsZero; } |
382 | void setReadZero() { IsZero = true; } |
383 | void setPRF(unsigned ID) { PRFID = ID; } |
384 | }; |
385 | |
386 | /// A sequence of cycles. |
387 | /// |
388 | /// This class can be used as a building block to construct ranges of cycles. |
389 | class CycleSegment { |
390 | unsigned Begin; // Inclusive. |
391 | unsigned End; // Exclusive. |
392 | bool Reserved; // Resources associated to this segment must be reserved. |
393 | |
394 | public: |
395 | CycleSegment(unsigned StartCycle, unsigned EndCycle, bool IsReserved = false) |
396 | : Begin(StartCycle), End(EndCycle), Reserved(IsReserved) {} |
397 | |
398 | bool contains(unsigned Cycle) const { return Cycle >= Begin && Cycle < End; } |
399 | bool startsAfter(const CycleSegment &CS) const { return End <= CS.Begin; } |
400 | bool endsBefore(const CycleSegment &CS) const { return Begin >= CS.End; } |
401 | bool overlaps(const CycleSegment &CS) const { |
402 | return !startsAfter(CS) && !endsBefore(CS); |
403 | } |
404 | bool isExecuting() const { return Begin == 0 && End != 0; } |
405 | bool isExecuted() const { return End == 0; } |
406 | bool operator<(const CycleSegment &Other) const { |
407 | return Begin < Other.Begin; |
408 | } |
409 | CycleSegment &operator--(void) { |
410 | if (Begin) |
411 | Begin--; |
412 | if (End) |
413 | End--; |
414 | return *this; |
415 | } |
416 | |
417 | bool isValid() const { return Begin <= End; } |
418 | unsigned size() const { return End - Begin; }; |
419 | void subtract(unsigned Cycles) { |
420 | assert(End >= Cycles)(static_cast <bool> (End >= Cycles) ? void (0) : __assert_fail ("End >= Cycles", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h" , 420, __extension__ __PRETTY_FUNCTION__)); |
421 | End -= Cycles; |
422 | } |
423 | |
424 | unsigned begin() const { return Begin; } |
425 | unsigned end() const { return End; } |
426 | void setEnd(unsigned NewEnd) { End = NewEnd; } |
427 | bool isReserved() const { return Reserved; } |
428 | void setReserved() { Reserved = true; } |
429 | }; |
430 | |
431 | /// Helper used by class InstrDesc to describe how hardware resources |
432 | /// are used. |
433 | /// |
434 | /// This class describes how many resource units of a specific resource kind |
435 | /// (and how many cycles) are "used" by an instruction. |
436 | struct ResourceUsage { |
437 | CycleSegment CS; |
438 | unsigned NumUnits; |
439 | ResourceUsage(CycleSegment Cycles, unsigned Units = 1) |
440 | : CS(Cycles), NumUnits(Units) {} |
441 | unsigned size() const { return CS.size(); } |
442 | bool isReserved() const { return CS.isReserved(); } |
443 | void setReserved() { CS.setReserved(); } |
444 | }; |
445 | |
446 | /// An instruction descriptor |
447 | struct InstrDesc { |
448 | SmallVector<WriteDescriptor, 2> Writes; // Implicit writes are at the end. |
449 | SmallVector<ReadDescriptor, 4> Reads; // Implicit reads are at the end. |
450 | |
451 | // For every resource used by an instruction of this kind, this vector |
452 | // reports the number of "consumed cycles". |
453 | SmallVector<std::pair<uint64_t, ResourceUsage>, 4> Resources; |
454 | |
455 | // A bitmask of used hardware buffers. |
456 | uint64_t UsedBuffers; |
457 | |
458 | // A bitmask of used processor resource units. |
459 | uint64_t UsedProcResUnits; |
460 | |
461 | // A bitmask of implicit uses of processor resource units. |
462 | uint64_t ImplicitlyUsedProcResUnits; |
463 | |
464 | // A bitmask of used processor resource groups. |
465 | uint64_t UsedProcResGroups; |
466 | |
467 | unsigned MaxLatency; |
468 | // Number of MicroOps for this instruction. |
469 | unsigned NumMicroOps; |
470 | // SchedClassID used to construct this InstrDesc. |
471 | // This information is currently used by views to do fast queries on the |
472 | // subtarget when computing the reciprocal throughput. |
473 | unsigned SchedClassID; |
474 | |
475 | unsigned MayLoad : 1; |
476 | unsigned MayStore : 1; |
477 | unsigned HasSideEffects : 1; |
478 | unsigned BeginGroup : 1; |
479 | unsigned EndGroup : 1; |
480 | unsigned RetireOOO : 1; |
481 | |
482 | // True if all buffered resources are in-order, and there is at least one |
483 | // buffer which is a dispatch hazard (BufferSize = 0). |
484 | unsigned MustIssueImmediately : 1; |
485 | |
486 | // A zero latency instruction doesn't consume any scheduler resources. |
487 | bool isZeroLatency() const { return !MaxLatency && Resources.empty(); } |
488 | |
489 | InstrDesc() = default; |
490 | InstrDesc(const InstrDesc &Other) = delete; |
491 | InstrDesc &operator=(const InstrDesc &Other) = delete; |
492 | }; |
493 | |
494 | /// Base class for instructions consumed by the simulation pipeline. |
495 | /// |
496 | /// This class tracks data dependencies as well as generic properties |
497 | /// of the instruction. |
498 | class InstructionBase { |
499 | const InstrDesc &Desc; |
500 | |
501 | // This field is set for instructions that are candidates for move |
502 | // elimination. For more information about move elimination, see the |
503 | // definition of RegisterMappingTracker in RegisterFile.h |
504 | bool IsOptimizableMove; |
505 | |
506 | // Output dependencies. |
507 | // One entry per each implicit and explicit register definition. |
508 | SmallVector<WriteState, 2> Defs; |
509 | |
510 | // Input dependencies. |
511 | // One entry per each implicit and explicit register use. |
512 | SmallVector<ReadState, 4> Uses; |
513 | |
514 | // List of operands which can be used by mca::CustomBehaviour |
515 | std::vector<MCAOperand> Operands; |
516 | |
517 | // Instruction opcode which can be used by mca::CustomBehaviour |
518 | unsigned Opcode; |
519 | |
520 | public: |
521 | InstructionBase(const InstrDesc &D, const unsigned Opcode) |
522 | : Desc(D), IsOptimizableMove(false), Operands(0), Opcode(Opcode) {} |
523 | |
524 | SmallVectorImpl<WriteState> &getDefs() { return Defs; } |
525 | ArrayRef<WriteState> getDefs() const { return Defs; } |
526 | SmallVectorImpl<ReadState> &getUses() { return Uses; } |
527 | ArrayRef<ReadState> getUses() const { return Uses; } |
528 | const InstrDesc &getDesc() const { return Desc; } |
529 | |
530 | unsigned getLatency() const { return Desc.MaxLatency; } |
531 | unsigned getNumMicroOps() const { return Desc.NumMicroOps; } |
532 | unsigned getOpcode() const { return Opcode; } |
533 | |
534 | /// Return the MCAOperand which corresponds to index Idx within the original |
535 | /// MCInst. |
536 | const MCAOperand *getOperand(const unsigned Idx) const { |
537 | auto It = std::find_if( |
538 | Operands.begin(), Operands.end(), |
539 | [&Idx](const MCAOperand &Op) { return Op.getIndex() == Idx; }); |
540 | if (It == Operands.end()) |
541 | return nullptr; |
542 | return &(*It); |
543 | } |
544 | unsigned getNumOperands() const { return Operands.size(); } |
545 | void addOperand(const MCAOperand Op) { Operands.push_back(Op); } |
546 | |
547 | bool hasDependentUsers() const { |
548 | return any_of(Defs, |
549 | [](const WriteState &Def) { return Def.getNumUsers() > 0; }); |
550 | } |
551 | |
552 | unsigned getNumUsers() const { |
553 | unsigned NumUsers = 0; |
554 | for (const WriteState &Def : Defs) |
555 | NumUsers += Def.getNumUsers(); |
556 | return NumUsers; |
557 | } |
558 | |
559 | // Returns true if this instruction is a candidate for move elimination. |
560 | bool isOptimizableMove() const { return IsOptimizableMove; } |
561 | void setOptimizableMove() { IsOptimizableMove = true; } |
562 | bool isMemOp() const { return Desc.MayLoad || Desc.MayStore; } |
563 | }; |
564 | |
565 | /// An instruction propagated through the simulated instruction pipeline. |
566 | /// |
567 | /// This class is used to monitor changes to the internal state of instructions |
568 | /// that are sent to the various components of the simulated hardware pipeline. |
569 | class Instruction : public InstructionBase { |
570 | enum InstrStage { |
571 | IS_INVALID, // Instruction in an invalid state. |
572 | IS_DISPATCHED, // Instruction dispatched but operands are not ready. |
573 | IS_PENDING, // Instruction is not ready, but operand latency is known. |
574 | IS_READY, // Instruction dispatched and operands ready. |
575 | IS_EXECUTING, // Instruction issued. |
576 | IS_EXECUTED, // Instruction executed. Values are written back. |
577 | IS_RETIRED // Instruction retired. |
578 | }; |
579 | |
580 | // The current instruction stage. |
581 | enum InstrStage Stage; |
582 | |
583 | // This value defaults to the instruction latency. This instruction is |
584 | // considered executed when field CyclesLeft goes to zero. |
585 | int CyclesLeft; |
586 | |
587 | // Retire Unit token ID for this instruction. |
588 | unsigned RCUTokenID; |
589 | |
590 | // LS token ID for this instruction. |
591 | // This field is set to the invalid null token if this is not a memory |
592 | // operation. |
593 | unsigned LSUTokenID; |
594 | |
595 | // A resource mask which identifies buffered resources consumed by this |
596 | // instruction at dispatch stage. In the absence of macro-fusion, this value |
597 | // should always match the value of field `UsedBuffers` from the instruction |
598 | // descriptor (see field InstrBase::Desc). |
599 | uint64_t UsedBuffers; |
600 | |
601 | // Critical register dependency. |
602 | CriticalDependency CriticalRegDep; |
603 | |
604 | // Critical memory dependency. |
605 | CriticalDependency CriticalMemDep; |
606 | |
607 | // A bitmask of busy processor resource units. |
608 | // This field is set to zero only if execution is not delayed during this |
609 | // cycle because of unavailable pipeline resources. |
610 | uint64_t CriticalResourceMask; |
611 | |
612 | // True if this instruction has been optimized at register renaming stage. |
613 | bool IsEliminated; |
614 | |
615 | public: |
616 | Instruction(const InstrDesc &D, const unsigned Opcode) |
617 | : InstructionBase(D, Opcode), Stage(IS_INVALID), |
618 | CyclesLeft(UNKNOWN_CYCLES), RCUTokenID(0), LSUTokenID(0), |
619 | UsedBuffers(D.UsedBuffers), CriticalRegDep(), CriticalMemDep(), |
620 | CriticalResourceMask(0), IsEliminated(false) {} |
621 | |
622 | unsigned getRCUTokenID() const { return RCUTokenID; } |
623 | unsigned getLSUTokenID() const { return LSUTokenID; } |
624 | void setLSUTokenID(unsigned LSUTok) { LSUTokenID = LSUTok; } |
625 | |
626 | uint64_t getUsedBuffers() const { return UsedBuffers; } |
627 | void setUsedBuffers(uint64_t Mask) { UsedBuffers = Mask; } |
628 | void clearUsedBuffers() { UsedBuffers = 0ULL; } |
629 | |
630 | int getCyclesLeft() const { return CyclesLeft; } |
631 | |
632 | // Transition to the dispatch stage, and assign a RCUToken to this |
633 | // instruction. The RCUToken is used to track the completion of every |
634 | // register write performed by this instruction. |
635 | void dispatch(unsigned RCUTokenID); |
636 | |
637 | // Instruction issued. Transition to the IS_EXECUTING state, and update |
638 | // all the register definitions. |
639 | void execute(unsigned IID); |
640 | |
641 | // Force a transition from the IS_DISPATCHED state to the IS_READY or |
642 | // IS_PENDING state. State transitions normally occur either at the beginning |
643 | // of a new cycle (see method cycleEvent()), or as a result of another issue |
644 | // event. This method is called every time the instruction might have changed |
645 | // in state. It internally delegates to method updateDispatched() and |
646 | // updateWaiting(). |
647 | void update(); |
648 | bool updateDispatched(); |
649 | bool updatePending(); |
650 | |
651 | bool isDispatched() const { return Stage == IS_DISPATCHED; } |
652 | bool isPending() const { return Stage == IS_PENDING; } |
653 | bool isReady() const { return Stage == IS_READY; } |
654 | bool isExecuting() const { return Stage == IS_EXECUTING; } |
655 | bool isExecuted() const { return Stage == IS_EXECUTED; } |
656 | bool isRetired() const { return Stage == IS_RETIRED; } |
657 | bool isEliminated() const { return IsEliminated; } |
658 | |
659 | // Forces a transition from state IS_DISPATCHED to state IS_EXECUTED. |
660 | void forceExecuted(); |
661 | void setEliminated() { IsEliminated = true; } |
662 | |
663 | void retire() { |
664 | assert(isExecuted() && "Instruction is in an invalid state!")(static_cast <bool> (isExecuted() && "Instruction is in an invalid state!" ) ? void (0) : __assert_fail ("isExecuted() && \"Instruction is in an invalid state!\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h" , 664, __extension__ __PRETTY_FUNCTION__)); |
665 | Stage = IS_RETIRED; |
666 | } |
667 | |
668 | const CriticalDependency &getCriticalRegDep() const { return CriticalRegDep; } |
669 | const CriticalDependency &getCriticalMemDep() const { return CriticalMemDep; } |
670 | const CriticalDependency &computeCriticalRegDep(); |
671 | void setCriticalMemDep(const CriticalDependency &MemDep) { |
672 | CriticalMemDep = MemDep; |
673 | } |
674 | |
675 | uint64_t getCriticalResourceMask() const { return CriticalResourceMask; } |
676 | void setCriticalResourceMask(uint64_t ResourceMask) { |
677 | CriticalResourceMask = ResourceMask; |
678 | } |
679 | |
680 | void cycleEvent(); |
681 | }; |
682 | |
683 | /// An InstRef contains both a SourceMgr index and Instruction pair. The index |
684 | /// is used as a unique identifier for the instruction. MCA will make use of |
685 | /// this index as a key throughout MCA. |
686 | class InstRef { |
687 | std::pair<unsigned, Instruction *> Data; |
688 | |
689 | public: |
690 | InstRef() : Data(std::make_pair(0, nullptr)) {} |
691 | InstRef(unsigned Index, Instruction *I) : Data(std::make_pair(Index, I)) {} |
692 | |
693 | bool operator==(const InstRef &Other) const { return Data == Other.Data; } |
694 | bool operator!=(const InstRef &Other) const { return Data != Other.Data; } |
695 | bool operator<(const InstRef &Other) const { |
696 | return Data.first < Other.Data.first; |
697 | } |
698 | |
699 | unsigned getSourceIndex() const { return Data.first; } |
700 | Instruction *getInstruction() { return Data.second; } |
701 | const Instruction *getInstruction() const { return Data.second; } |
702 | |
703 | /// Returns true if this references a valid instruction. |
704 | explicit operator bool() const { return Data.second != nullptr; } |
705 | |
706 | /// Invalidate this reference. |
707 | void invalidate() { Data.second = nullptr; } |
708 | |
709 | #ifndef NDEBUG |
710 | void print(raw_ostream &OS) const { OS << getSourceIndex(); } |
711 | #endif |
712 | }; |
713 | |
714 | #ifndef NDEBUG |
715 | inline raw_ostream &operator<<(raw_ostream &OS, const InstRef &IR) { |
716 | IR.print(OS); |
717 | return OS; |
718 | } |
719 | #endif |
720 | |
721 | } // namespace mca |
722 | } // namespace llvm |
723 | |
724 | #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_STAGES_STAGE_H |
16 | #define LLVM_MCA_STAGES_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!")(static_cast <bool> (!NextInSequence && "This stage already has a NextInSequence!" ) ? void (0) : __assert_fail ("!NextInSequence && \"This stage already has a NextInSequence!\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Stages/Stage.h" , 58, __extension__ __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!")(static_cast <bool> (checkNextStage(IR) && "Next stage is not ready!" ) ? void (0) : __assert_fail ("checkNextStage(IR) && \"Next stage is not ready!\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Stages/Stage.h" , 71, __extension__ __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_STAGES_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_STAGES_MICROOPQUEUESTAGE_H |
17 | #define LLVM_MCA_STAGES_MICROOPQUEUESTAGE_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_STAGES_MICROOPQUEUESTAGE_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/Compiler.h" |
18 | #include "llvm/Support/ErrorHandling.h" |
19 | #include "llvm/Support/MemAlloc.h" |
20 | #include "llvm/Support/type_traits.h" |
21 | #include <algorithm> |
22 | #include <cassert> |
23 | #include <cstddef> |
24 | #include <cstdlib> |
25 | #include <cstring> |
26 | #include <functional> |
27 | #include <initializer_list> |
28 | #include <iterator> |
29 | #include <limits> |
30 | #include <memory> |
31 | #include <new> |
32 | #include <type_traits> |
33 | #include <utility> |
34 | |
35 | namespace llvm { |
36 | |
37 | /// This is all the stuff common to all SmallVectors. |
38 | /// |
39 | /// The template parameter specifies the type which should be used to hold the |
40 | /// Size and Capacity of the SmallVector, so it can be adjusted. |
41 | /// Using 32 bit size is desirable to shrink the size of the SmallVector. |
42 | /// Using 64 bit size is desirable for cases like SmallVector<char>, where a |
43 | /// 32 bit size would limit the vector to ~4GB. SmallVectors are used for |
44 | /// buffering bitcode output - which can exceed 4GB. |
45 | template <class Size_T> class SmallVectorBase { |
46 | protected: |
47 | void *BeginX; |
48 | Size_T Size = 0, Capacity; |
49 | |
50 | /// The maximum value of the Size_T used. |
51 | static constexpr size_t SizeTypeMax() { |
52 | return std::numeric_limits<Size_T>::max(); |
53 | } |
54 | |
55 | SmallVectorBase() = delete; |
56 | SmallVectorBase(void *FirstEl, size_t TotalCapacity) |
57 | : BeginX(FirstEl), Capacity(TotalCapacity) {} |
58 | |
59 | /// This is a helper for \a grow() that's out of line to reduce code |
60 | /// duplication. This function will report a fatal error if it can't grow at |
61 | /// least to \p MinSize. |
62 | void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity); |
63 | |
64 | /// This is an implementation of the grow() method which only works |
65 | /// on POD-like data types and is out of line to reduce code duplication. |
66 | /// This function will report a fatal error if it cannot increase capacity. |
67 | void grow_pod(void *FirstEl, size_t MinSize, size_t TSize); |
68 | |
69 | public: |
70 | size_t size() const { return Size; } |
71 | size_t capacity() const { return Capacity; } |
72 | |
73 | LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; } |
74 | |
75 | /// Set the array size to \p N, which the current array must have enough |
76 | /// capacity for. |
77 | /// |
78 | /// This does not construct or destroy any elements in the vector. |
79 | /// |
80 | /// Clients can use this in conjunction with capacity() to write past the end |
81 | /// of the buffer when they know that more elements are available, and only |
82 | /// update the size later. This avoids the cost of value initializing elements |
83 | /// which will only be overwritten. |
84 | void set_size(size_t N) { |
85 | assert(N <= capacity())(static_cast <bool> (N <= capacity()) ? void (0) : __assert_fail ("N <= capacity()", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 85, __extension__ __PRETTY_FUNCTION__)); |
86 | Size = N; |
87 | } |
88 | }; |
89 | |
90 | template <class T> |
91 | using SmallVectorSizeType = |
92 | typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t, |
93 | uint32_t>::type; |
94 | |
95 | /// Figure out the offset of the first element. |
96 | template <class T, typename = void> struct SmallVectorAlignmentAndSize { |
97 | alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof( |
98 | SmallVectorBase<SmallVectorSizeType<T>>)]; |
99 | alignas(T) char FirstEl[sizeof(T)]; |
100 | }; |
101 | |
102 | /// This is the part of SmallVectorTemplateBase which does not depend on whether |
103 | /// the type T is a POD. The extra dummy template argument is used by ArrayRef |
104 | /// to avoid unnecessarily requiring T to be complete. |
105 | template <typename T, typename = void> |
106 | class SmallVectorTemplateCommon |
107 | : public SmallVectorBase<SmallVectorSizeType<T>> { |
108 | using Base = SmallVectorBase<SmallVectorSizeType<T>>; |
109 | |
110 | /// Find the address of the first element. For this pointer math to be valid |
111 | /// with small-size of 0 for T with lots of alignment, it's important that |
112 | /// SmallVectorStorage is properly-aligned even for small-size of 0. |
113 | void *getFirstEl() const { |
114 | return const_cast<void *>(reinterpret_cast<const void *>( |
115 | reinterpret_cast<const char *>(this) + |
116 | offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl ))); |
117 | } |
118 | // Space after 'FirstEl' is clobbered, do not add any instance vars after it. |
119 | |
120 | protected: |
121 | SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {} |
122 | |
123 | void grow_pod(size_t MinSize, size_t TSize) { |
124 | Base::grow_pod(getFirstEl(), MinSize, TSize); |
125 | } |
126 | |
127 | /// Return true if this is a smallvector which has not had dynamic |
128 | /// memory allocated for it. |
129 | bool isSmall() const { return this->BeginX == getFirstEl(); } |
130 | |
131 | /// Put this vector in a state of being small. |
132 | void resetToSmall() { |
133 | this->BeginX = getFirstEl(); |
134 | this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect. |
135 | } |
136 | |
137 | /// Return true if V is an internal reference to the given range. |
138 | bool isReferenceToRange(const void *V, const void *First, const void *Last) const { |
139 | // Use std::less to avoid UB. |
140 | std::less<> LessThan; |
141 | return !LessThan(V, First) && LessThan(V, Last); |
142 | } |
143 | |
144 | /// Return true if V is an internal reference to this vector. |
145 | bool isReferenceToStorage(const void *V) const { |
146 | return isReferenceToRange(V, this->begin(), this->end()); |
147 | } |
148 | |
149 | /// Return true if First and Last form a valid (possibly empty) range in this |
150 | /// vector's storage. |
151 | bool isRangeInStorage(const void *First, const void *Last) const { |
152 | // Use std::less to avoid UB. |
153 | std::less<> LessThan; |
154 | return !LessThan(First, this->begin()) && !LessThan(Last, First) && |
155 | !LessThan(this->end(), Last); |
156 | } |
157 | |
158 | /// Return true unless Elt will be invalidated by resizing the vector to |
159 | /// NewSize. |
160 | bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) { |
161 | // Past the end. |
162 | if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true)) |
163 | return true; |
164 | |
165 | // Return false if Elt will be destroyed by shrinking. |
166 | if (NewSize <= this->size()) |
167 | return Elt < this->begin() + NewSize; |
168 | |
169 | // Return false if we need to grow. |
170 | return NewSize <= this->capacity(); |
171 | } |
172 | |
173 | /// Check whether Elt will be invalidated by resizing the vector to NewSize. |
174 | void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) { |
175 | assert(isSafeToReferenceAfterResize(Elt, NewSize) &&(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize ) && "Attempting to reference an element of the vector in an operation " "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 177, __extension__ __PRETTY_FUNCTION__)) |
176 | "Attempting to reference an element of the vector in an operation "(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize ) && "Attempting to reference an element of the vector in an operation " "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 177, __extension__ __PRETTY_FUNCTION__)) |
177 | "that invalidates it")(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize ) && "Attempting to reference an element of the vector in an operation " "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 177, __extension__ __PRETTY_FUNCTION__)); |
178 | } |
179 | |
180 | /// Check whether Elt will be invalidated by increasing the size of the |
181 | /// vector by N. |
182 | void assertSafeToAdd(const void *Elt, size_t N = 1) { |
183 | this->assertSafeToReferenceAfterResize(Elt, this->size() + N); |
184 | } |
185 | |
186 | /// Check whether any part of the range will be invalidated by clearing. |
187 | void assertSafeToReferenceAfterClear(const T *From, const T *To) { |
188 | if (From == To) |
189 | return; |
190 | this->assertSafeToReferenceAfterResize(From, 0); |
191 | this->assertSafeToReferenceAfterResize(To - 1, 0); |
192 | } |
193 | template < |
194 | class ItTy, |
195 | std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value, |
196 | bool> = false> |
197 | void assertSafeToReferenceAfterClear(ItTy, ItTy) {} |
198 | |
199 | /// Check whether any part of the range will be invalidated by growing. |
200 | void assertSafeToAddRange(const T *From, const T *To) { |
201 | if (From == To) |
202 | return; |
203 | this->assertSafeToAdd(From, To - From); |
204 | this->assertSafeToAdd(To - 1, To - From); |
205 | } |
206 | template < |
207 | class ItTy, |
208 | std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value, |
209 | bool> = false> |
210 | void assertSafeToAddRange(ItTy, ItTy) {} |
211 | |
212 | /// Reserve enough space to add one element, and return the updated element |
213 | /// pointer in case it was a reference to the storage. |
214 | template <class U> |
215 | static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt, |
216 | size_t N) { |
217 | size_t NewSize = This->size() + N; |
218 | if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true )) |
219 | return &Elt; |
220 | |
221 | bool ReferencesStorage = false; |
222 | int64_t Index = -1; |
223 | if (!U::TakesParamByValue) { |
224 | if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt )), false)) { |
225 | ReferencesStorage = true; |
226 | Index = &Elt - This->begin(); |
227 | } |
228 | } |
229 | This->grow(NewSize); |
230 | return ReferencesStorage ? This->begin() + Index : &Elt; |
231 | } |
232 | |
233 | public: |
234 | using size_type = size_t; |
235 | using difference_type = ptrdiff_t; |
236 | using value_type = T; |
237 | using iterator = T *; |
238 | using const_iterator = const T *; |
239 | |
240 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
241 | using reverse_iterator = std::reverse_iterator<iterator>; |
242 | |
243 | using reference = T &; |
244 | using const_reference = const T &; |
245 | using pointer = T *; |
246 | using const_pointer = const T *; |
247 | |
248 | using Base::capacity; |
249 | using Base::empty; |
250 | using Base::size; |
251 | |
252 | // forward iterator creation methods. |
253 | iterator begin() { return (iterator)this->BeginX; } |
254 | const_iterator begin() const { return (const_iterator)this->BeginX; } |
255 | iterator end() { return begin() + size(); } |
256 | const_iterator end() const { return begin() + size(); } |
257 | |
258 | // reverse iterator creation methods. |
259 | reverse_iterator rbegin() { return reverse_iterator(end()); } |
260 | const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } |
261 | reverse_iterator rend() { return reverse_iterator(begin()); } |
262 | const_reverse_iterator rend() const { return const_reverse_iterator(begin());} |
263 | |
264 | size_type size_in_bytes() const { return size() * sizeof(T); } |
265 | size_type max_size() const { |
266 | return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T)); |
267 | } |
268 | |
269 | size_t capacity_in_bytes() const { return capacity() * sizeof(T); } |
270 | |
271 | /// Return a pointer to the vector's buffer, even if empty(). |
272 | pointer data() { return pointer(begin()); } |
273 | /// Return a pointer to the vector's buffer, even if empty(). |
274 | const_pointer data() const { return const_pointer(begin()); } |
275 | |
276 | reference operator[](size_type idx) { |
277 | assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail ("idx < size()", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 277, __extension__ __PRETTY_FUNCTION__)); |
278 | return begin()[idx]; |
279 | } |
280 | const_reference operator[](size_type idx) const { |
281 | assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail ("idx < size()", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 281, __extension__ __PRETTY_FUNCTION__)); |
282 | return begin()[idx]; |
283 | } |
284 | |
285 | reference front() { |
286 | assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail ("!empty()", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 286, __extension__ __PRETTY_FUNCTION__)); |
287 | return begin()[0]; |
288 | } |
289 | const_reference front() const { |
290 | assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail ("!empty()", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 290, __extension__ __PRETTY_FUNCTION__)); |
291 | return begin()[0]; |
292 | } |
293 | |
294 | reference back() { |
295 | assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail ("!empty()", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 295, __extension__ __PRETTY_FUNCTION__)); |
296 | return end()[-1]; |
297 | } |
298 | const_reference back() const { |
299 | assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail ("!empty()", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 299, __extension__ __PRETTY_FUNCTION__)); |
300 | return end()[-1]; |
301 | } |
302 | }; |
303 | |
304 | /// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put |
305 | /// method implementations that are designed to work with non-trivial T's. |
306 | /// |
307 | /// We approximate is_trivially_copyable with trivial move/copy construction and |
308 | /// trivial destruction. While the standard doesn't specify that you're allowed |
309 | /// copy these types with memcpy, there is no way for the type to observe this. |
310 | /// This catches the important case of std::pair<POD, POD>, which is not |
311 | /// trivially assignable. |
312 | template <typename T, bool = (is_trivially_copy_constructible<T>::value) && |
313 | (is_trivially_move_constructible<T>::value) && |
314 | std::is_trivially_destructible<T>::value> |
315 | class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { |
316 | friend class SmallVectorTemplateCommon<T>; |
317 | |
318 | protected: |
319 | static constexpr bool TakesParamByValue = false; |
320 | using ValueParamT = const T &; |
321 | |
322 | SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} |
323 | |
324 | static void destroy_range(T *S, T *E) { |
325 | while (S != E) { |
326 | --E; |
327 | E->~T(); |
328 | } |
329 | } |
330 | |
331 | /// Move the range [I, E) into the uninitialized memory starting with "Dest", |
332 | /// constructing elements as needed. |
333 | template<typename It1, typename It2> |
334 | static void uninitialized_move(It1 I, It1 E, It2 Dest) { |
335 | std::uninitialized_copy(std::make_move_iterator(I), |
336 | std::make_move_iterator(E), Dest); |
337 | } |
338 | |
339 | /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", |
340 | /// constructing elements as needed. |
341 | template<typename It1, typename It2> |
342 | static void uninitialized_copy(It1 I, It1 E, It2 Dest) { |
343 | std::uninitialized_copy(I, E, Dest); |
344 | } |
345 | |
346 | /// Grow the allocated memory (without initializing new elements), doubling |
347 | /// the size of the allocated memory. Guarantees space for at least one more |
348 | /// element, or MinSize more elements if specified. |
349 | void grow(size_t MinSize = 0); |
350 | |
351 | /// Create a new allocation big enough for \p MinSize and pass back its size |
352 | /// in \p NewCapacity. This is the first section of \a grow(). |
353 | T *mallocForGrow(size_t MinSize, size_t &NewCapacity) { |
354 | return static_cast<T *>( |
355 | SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow( |
356 | MinSize, sizeof(T), NewCapacity)); |
357 | } |
358 | |
359 | /// Move existing elements over to the new allocation \p NewElts, the middle |
360 | /// section of \a grow(). |
361 | void moveElementsForGrow(T *NewElts); |
362 | |
363 | /// Transfer ownership of the allocation, finishing up \a grow(). |
364 | void takeAllocationForGrow(T *NewElts, size_t NewCapacity); |
365 | |
366 | /// Reserve enough space to add one element, and return the updated element |
367 | /// pointer in case it was a reference to the storage. |
368 | const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) { |
369 | return this->reserveForParamAndGetAddressImpl(this, Elt, N); |
370 | } |
371 | |
372 | /// Reserve enough space to add one element, and return the updated element |
373 | /// pointer in case it was a reference to the storage. |
374 | T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) { |
375 | return const_cast<T *>( |
376 | this->reserveForParamAndGetAddressImpl(this, Elt, N)); |
377 | } |
378 | |
379 | static T &&forward_value_param(T &&V) { return std::move(V); } |
380 | static const T &forward_value_param(const T &V) { return V; } |
381 | |
382 | void growAndAssign(size_t NumElts, const T &Elt) { |
383 | // Grow manually in case Elt is an internal reference. |
384 | size_t NewCapacity; |
385 | T *NewElts = mallocForGrow(NumElts, NewCapacity); |
386 | std::uninitialized_fill_n(NewElts, NumElts, Elt); |
387 | this->destroy_range(this->begin(), this->end()); |
388 | takeAllocationForGrow(NewElts, NewCapacity); |
389 | this->set_size(NumElts); |
390 | } |
391 | |
392 | template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) { |
393 | // Grow manually in case one of Args is an internal reference. |
394 | size_t NewCapacity; |
395 | T *NewElts = mallocForGrow(0, NewCapacity); |
396 | ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...); |
397 | moveElementsForGrow(NewElts); |
398 | takeAllocationForGrow(NewElts, NewCapacity); |
399 | this->set_size(this->size() + 1); |
400 | return this->back(); |
401 | } |
402 | |
403 | public: |
404 | void push_back(const T &Elt) { |
405 | const T *EltPtr = reserveForParamAndGetAddress(Elt); |
406 | ::new ((void *)this->end()) T(*EltPtr); |
407 | this->set_size(this->size() + 1); |
408 | } |
409 | |
410 | void push_back(T &&Elt) { |
411 | T *EltPtr = reserveForParamAndGetAddress(Elt); |
412 | ::new ((void *)this->end()) T(::std::move(*EltPtr)); |
413 | this->set_size(this->size() + 1); |
414 | } |
415 | |
416 | void pop_back() { |
417 | this->set_size(this->size() - 1); |
418 | this->end()->~T(); |
419 | } |
420 | }; |
421 | |
422 | // Define this out-of-line to dissuade the C++ compiler from inlining it. |
423 | template <typename T, bool TriviallyCopyable> |
424 | void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) { |
425 | size_t NewCapacity; |
426 | T *NewElts = mallocForGrow(MinSize, NewCapacity); |
427 | moveElementsForGrow(NewElts); |
428 | takeAllocationForGrow(NewElts, NewCapacity); |
429 | } |
430 | |
431 | // Define this out-of-line to dissuade the C++ compiler from inlining it. |
432 | template <typename T, bool TriviallyCopyable> |
433 | void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow( |
434 | T *NewElts) { |
435 | // Move the elements over. |
436 | this->uninitialized_move(this->begin(), this->end(), NewElts); |
437 | |
438 | // Destroy the original elements. |
439 | destroy_range(this->begin(), this->end()); |
440 | } |
441 | |
442 | // Define this out-of-line to dissuade the C++ compiler from inlining it. |
443 | template <typename T, bool TriviallyCopyable> |
444 | void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow( |
445 | T *NewElts, size_t NewCapacity) { |
446 | // If this wasn't grown from the inline copy, deallocate the old space. |
447 | if (!this->isSmall()) |
448 | free(this->begin()); |
449 | |
450 | this->BeginX = NewElts; |
451 | this->Capacity = NewCapacity; |
452 | } |
453 | |
454 | /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put |
455 | /// method implementations that are designed to work with trivially copyable |
456 | /// T's. This allows using memcpy in place of copy/move construction and |
457 | /// skipping destruction. |
458 | template <typename T> |
459 | class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { |
460 | friend class SmallVectorTemplateCommon<T>; |
461 | |
462 | protected: |
463 | /// True if it's cheap enough to take parameters by value. Doing so avoids |
464 | /// overhead related to mitigations for reference invalidation. |
465 | static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *); |
466 | |
467 | /// Either const T& or T, depending on whether it's cheap enough to take |
468 | /// parameters by value. |
469 | using ValueParamT = |
470 | typename std::conditional<TakesParamByValue, T, const T &>::type; |
471 | |
472 | SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} |
473 | |
474 | // No need to do a destroy loop for POD's. |
475 | static void destroy_range(T *, T *) {} |
476 | |
477 | /// Move the range [I, E) onto the uninitialized memory |
478 | /// starting with "Dest", constructing elements into it as needed. |
479 | template<typename It1, typename It2> |
480 | static void uninitialized_move(It1 I, It1 E, It2 Dest) { |
481 | // Just do a copy. |
482 | uninitialized_copy(I, E, Dest); |
483 | } |
484 | |
485 | /// Copy the range [I, E) onto the uninitialized memory |
486 | /// starting with "Dest", constructing elements into it as needed. |
487 | template<typename It1, typename It2> |
488 | static void uninitialized_copy(It1 I, It1 E, It2 Dest) { |
489 | // Arbitrary iterator types; just use the basic implementation. |
490 | std::uninitialized_copy(I, E, Dest); |
491 | } |
492 | |
493 | /// Copy the range [I, E) onto the uninitialized memory |
494 | /// starting with "Dest", constructing elements into it as needed. |
495 | template <typename T1, typename T2> |
496 | static void uninitialized_copy( |
497 | T1 *I, T1 *E, T2 *Dest, |
498 | std::enable_if_t<std::is_same<typename std::remove_const<T1>::type, |
499 | T2>::value> * = nullptr) { |
500 | // Use memcpy for PODs iterated by pointers (which includes SmallVector |
501 | // iterators): std::uninitialized_copy optimizes to memmove, but we can |
502 | // use memcpy here. Note that I and E are iterators and thus might be |
503 | // invalid for memcpy if they are equal. |
504 | if (I != E) |
505 | memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T)); |
506 | } |
507 | |
508 | /// Double the size of the allocated memory, guaranteeing space for at |
509 | /// least one more element or MinSize if specified. |
510 | void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); } |
511 | |
512 | /// Reserve enough space to add one element, and return the updated element |
513 | /// pointer in case it was a reference to the storage. |
514 | const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) { |
515 | return this->reserveForParamAndGetAddressImpl(this, Elt, N); |
516 | } |
517 | |
518 | /// Reserve enough space to add one element, and return the updated element |
519 | /// pointer in case it was a reference to the storage. |
520 | T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) { |
521 | return const_cast<T *>( |
522 | this->reserveForParamAndGetAddressImpl(this, Elt, N)); |
523 | } |
524 | |
525 | /// Copy \p V or return a reference, depending on \a ValueParamT. |
526 | static ValueParamT forward_value_param(ValueParamT V) { return V; } |
527 | |
528 | void growAndAssign(size_t NumElts, T Elt) { |
529 | // Elt has been copied in case it's an internal reference, side-stepping |
530 | // reference invalidation problems without losing the realloc optimization. |
531 | this->set_size(0); |
532 | this->grow(NumElts); |
533 | std::uninitialized_fill_n(this->begin(), NumElts, Elt); |
534 | this->set_size(NumElts); |
535 | } |
536 | |
537 | template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) { |
538 | // Use push_back with a copy in case Args has an internal reference, |
539 | // side-stepping reference invalidation problems without losing the realloc |
540 | // optimization. |
541 | push_back(T(std::forward<ArgTypes>(Args)...)); |
542 | return this->back(); |
543 | } |
544 | |
545 | public: |
546 | void push_back(ValueParamT Elt) { |
547 | const T *EltPtr = reserveForParamAndGetAddress(Elt); |
548 | memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T)); |
549 | this->set_size(this->size() + 1); |
550 | } |
551 | |
552 | void pop_back() { this->set_size(this->size() - 1); } |
553 | }; |
554 | |
555 | /// This class consists of common code factored out of the SmallVector class to |
556 | /// reduce code duplication based on the SmallVector 'N' template parameter. |
557 | template <typename T> |
558 | class SmallVectorImpl : public SmallVectorTemplateBase<T> { |
559 | using SuperClass = SmallVectorTemplateBase<T>; |
560 | |
561 | public: |
562 | using iterator = typename SuperClass::iterator; |
563 | using const_iterator = typename SuperClass::const_iterator; |
564 | using reference = typename SuperClass::reference; |
565 | using size_type = typename SuperClass::size_type; |
566 | |
567 | protected: |
568 | using SmallVectorTemplateBase<T>::TakesParamByValue; |
569 | using ValueParamT = typename SuperClass::ValueParamT; |
570 | |
571 | // Default ctor - Initialize to empty. |
572 | explicit SmallVectorImpl(unsigned N) |
573 | : SmallVectorTemplateBase<T>(N) {} |
574 | |
575 | public: |
576 | SmallVectorImpl(const SmallVectorImpl &) = delete; |
577 | |
578 | ~SmallVectorImpl() { |
579 | // Subclass has already destructed this vector's elements. |
580 | // If this wasn't grown from the inline copy, deallocate the old space. |
581 | if (!this->isSmall()) |
582 | free(this->begin()); |
583 | } |
584 | |
585 | void clear() { |
586 | this->destroy_range(this->begin(), this->end()); |
587 | this->Size = 0; |
588 | } |
589 | |
590 | private: |
591 | template <bool ForOverwrite> void resizeImpl(size_type N) { |
592 | if (N < this->size()) { |
593 | this->pop_back_n(this->size() - N); |
594 | } else if (N > this->size()) { |
595 | this->reserve(N); |
596 | for (auto I = this->end(), E = this->begin() + N; I != E; ++I) |
597 | if (ForOverwrite) |
598 | new (&*I) T; |
599 | else |
600 | new (&*I) T(); |
601 | this->set_size(N); |
602 | } |
603 | } |
604 | |
605 | public: |
606 | void resize(size_type N) { resizeImpl<false>(N); } |
607 | |
608 | /// Like resize, but \ref T is POD, the new values won't be initialized. |
609 | void resize_for_overwrite(size_type N) { resizeImpl<true>(N); } |
610 | |
611 | void resize(size_type N, ValueParamT NV) { |
612 | if (N == this->size()) |
613 | return; |
614 | |
615 | if (N < this->size()) { |
616 | this->pop_back_n(this->size() - N); |
617 | return; |
618 | } |
619 | |
620 | // N > this->size(). Defer to append. |
621 | this->append(N - this->size(), NV); |
622 | } |
623 | |
624 | void reserve(size_type N) { |
625 | if (this->capacity() < N) |
626 | this->grow(N); |
627 | } |
628 | |
629 | void pop_back_n(size_type NumItems) { |
630 | assert(this->size() >= NumItems)(static_cast <bool> (this->size() >= NumItems) ? void (0) : __assert_fail ("this->size() >= NumItems", "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 630, __extension__ __PRETTY_FUNCTION__)); |
631 | this->destroy_range(this->end() - NumItems, this->end()); |
632 | this->set_size(this->size() - NumItems); |
633 | } |
634 | |
635 | LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() { |
636 | T Result = ::std::move(this->back()); |
637 | this->pop_back(); |
638 | return Result; |
639 | } |
640 | |
641 | void swap(SmallVectorImpl &RHS); |
642 | |
643 | /// Add the specified range to the end of the SmallVector. |
644 | template <typename in_iter, |
645 | typename = std::enable_if_t<std::is_convertible< |
646 | typename std::iterator_traits<in_iter>::iterator_category, |
647 | std::input_iterator_tag>::value>> |
648 | void append(in_iter in_start, in_iter in_end) { |
649 | this->assertSafeToAddRange(in_start, in_end); |
650 | size_type NumInputs = std::distance(in_start, in_end); |
651 | this->reserve(this->size() + NumInputs); |
652 | this->uninitialized_copy(in_start, in_end, this->end()); |
653 | this->set_size(this->size() + NumInputs); |
654 | } |
655 | |
656 | /// Append \p NumInputs copies of \p Elt to the end. |
657 | void append(size_type NumInputs, ValueParamT Elt) { |
658 | const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs); |
659 | std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr); |
660 | this->set_size(this->size() + NumInputs); |
661 | } |
662 | |
663 | void append(std::initializer_list<T> IL) { |
664 | append(IL.begin(), IL.end()); |
665 | } |
666 | |
667 | void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); } |
668 | |
669 | void assign(size_type NumElts, ValueParamT Elt) { |
670 | // Note that Elt could be an internal reference. |
671 | if (NumElts > this->capacity()) { |
672 | this->growAndAssign(NumElts, Elt); |
673 | return; |
674 | } |
675 | |
676 | // Assign over existing elements. |
677 | std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt); |
678 | if (NumElts > this->size()) |
679 | std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt); |
680 | else if (NumElts < this->size()) |
681 | this->destroy_range(this->begin() + NumElts, this->end()); |
682 | this->set_size(NumElts); |
683 | } |
684 | |
685 | // FIXME: Consider assigning over existing elements, rather than clearing & |
686 | // re-initializing them - for all assign(...) variants. |
687 | |
688 | template <typename in_iter, |
689 | typename = std::enable_if_t<std::is_convertible< |
690 | typename std::iterator_traits<in_iter>::iterator_category, |
691 | std::input_iterator_tag>::value>> |
692 | void assign(in_iter in_start, in_iter in_end) { |
693 | this->assertSafeToReferenceAfterClear(in_start, in_end); |
694 | clear(); |
695 | append(in_start, in_end); |
696 | } |
697 | |
698 | void assign(std::initializer_list<T> IL) { |
699 | clear(); |
700 | append(IL); |
701 | } |
702 | |
703 | void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); } |
704 | |
705 | iterator erase(const_iterator CI) { |
706 | // Just cast away constness because this is a non-const member function. |
707 | iterator I = const_cast<iterator>(CI); |
708 | |
709 | assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.") ? void (0) : __assert_fail ("this->isReferenceToStorage(CI) && \"Iterator to erase is out of bounds.\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 709, __extension__ __PRETTY_FUNCTION__)); |
710 | |
711 | iterator N = I; |
712 | // Shift all elts down one. |
713 | std::move(I+1, this->end(), I); |
714 | // Drop the last elt. |
715 | this->pop_back(); |
716 | return(N); |
717 | } |
718 | |
719 | iterator erase(const_iterator CS, const_iterator CE) { |
720 | // Just cast away constness because this is a non-const member function. |
721 | iterator S = const_cast<iterator>(CS); |
722 | iterator E = const_cast<iterator>(CE); |
723 | |
724 | assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")(static_cast <bool> (this->isRangeInStorage(S, E) && "Range to erase is out of bounds.") ? void (0) : __assert_fail ("this->isRangeInStorage(S, E) && \"Range to erase is out of bounds.\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 724, __extension__ __PRETTY_FUNCTION__)); |
725 | |
726 | iterator N = S; |
727 | // Shift all elts down. |
728 | iterator I = std::move(E, this->end(), S); |
729 | // Drop the last elts. |
730 | this->destroy_range(I, this->end()); |
731 | this->set_size(I - this->begin()); |
732 | return(N); |
733 | } |
734 | |
735 | private: |
736 | template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) { |
737 | // Callers ensure that ArgType is derived from T. |
738 | static_assert( |
739 | std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, |
740 | T>::value, |
741 | "ArgType must be derived from T!"); |
742 | |
743 | if (I == this->end()) { // Important special case for empty vector. |
744 | this->push_back(::std::forward<ArgType>(Elt)); |
745 | return this->end()-1; |
746 | } |
747 | |
748 | assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.") ? void (0) : __assert_fail ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 748, __extension__ __PRETTY_FUNCTION__)); |
749 | |
750 | // Grow if necessary. |
751 | size_t Index = I - this->begin(); |
752 | std::remove_reference_t<ArgType> *EltPtr = |
753 | this->reserveForParamAndGetAddress(Elt); |
754 | I = this->begin() + Index; |
755 | |
756 | ::new ((void*) this->end()) T(::std::move(this->back())); |
757 | // Push everything else over. |
758 | std::move_backward(I, this->end()-1, this->end()); |
759 | this->set_size(this->size() + 1); |
760 | |
761 | // If we just moved the element we're inserting, be sure to update |
762 | // the reference (never happens if TakesParamByValue). |
763 | static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value, |
764 | "ArgType must be 'T' when taking by value!"); |
765 | if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end())) |
766 | ++EltPtr; |
767 | |
768 | *I = ::std::forward<ArgType>(*EltPtr); |
769 | return I; |
770 | } |
771 | |
772 | public: |
773 | iterator insert(iterator I, T &&Elt) { |
774 | return insert_one_impl(I, this->forward_value_param(std::move(Elt))); |
775 | } |
776 | |
777 | iterator insert(iterator I, const T &Elt) { |
778 | return insert_one_impl(I, this->forward_value_param(Elt)); |
779 | } |
780 | |
781 | iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) { |
782 | // Convert iterator to elt# to avoid invalidating iterator when we reserve() |
783 | size_t InsertElt = I - this->begin(); |
784 | |
785 | if (I == this->end()) { // Important special case for empty vector. |
786 | append(NumToInsert, Elt); |
787 | return this->begin()+InsertElt; |
788 | } |
789 | |
790 | assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.") ? void (0) : __assert_fail ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 790, __extension__ __PRETTY_FUNCTION__)); |
791 | |
792 | // Ensure there is enough space, and get the (maybe updated) address of |
793 | // Elt. |
794 | const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert); |
795 | |
796 | // Uninvalidate the iterator. |
797 | I = this->begin()+InsertElt; |
798 | |
799 | // If there are more elements between the insertion point and the end of the |
800 | // range than there are being inserted, we can use a simple approach to |
801 | // insertion. Since we already reserved space, we know that this won't |
802 | // reallocate the vector. |
803 | if (size_t(this->end()-I) >= NumToInsert) { |
804 | T *OldEnd = this->end(); |
805 | append(std::move_iterator<iterator>(this->end() - NumToInsert), |
806 | std::move_iterator<iterator>(this->end())); |
807 | |
808 | // Copy the existing elements that get replaced. |
809 | std::move_backward(I, OldEnd-NumToInsert, OldEnd); |
810 | |
811 | // If we just moved the element we're inserting, be sure to update |
812 | // the reference (never happens if TakesParamByValue). |
813 | if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end()) |
814 | EltPtr += NumToInsert; |
815 | |
816 | std::fill_n(I, NumToInsert, *EltPtr); |
817 | return I; |
818 | } |
819 | |
820 | // Otherwise, we're inserting more elements than exist already, and we're |
821 | // not inserting at the end. |
822 | |
823 | // Move over the elements that we're about to overwrite. |
824 | T *OldEnd = this->end(); |
825 | this->set_size(this->size() + NumToInsert); |
826 | size_t NumOverwritten = OldEnd-I; |
827 | this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); |
828 | |
829 | // If we just moved the element we're inserting, be sure to update |
830 | // the reference (never happens if TakesParamByValue). |
831 | if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end()) |
832 | EltPtr += NumToInsert; |
833 | |
834 | // Replace the overwritten part. |
835 | std::fill_n(I, NumOverwritten, *EltPtr); |
836 | |
837 | // Insert the non-overwritten middle part. |
838 | std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr); |
839 | return I; |
840 | } |
841 | |
842 | template <typename ItTy, |
843 | typename = std::enable_if_t<std::is_convertible< |
844 | typename std::iterator_traits<ItTy>::iterator_category, |
845 | std::input_iterator_tag>::value>> |
846 | iterator insert(iterator I, ItTy From, ItTy To) { |
847 | // Convert iterator to elt# to avoid invalidating iterator when we reserve() |
848 | size_t InsertElt = I - this->begin(); |
849 | |
850 | if (I == this->end()) { // Important special case for empty vector. |
851 | append(From, To); |
852 | return this->begin()+InsertElt; |
853 | } |
854 | |
855 | assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.") ? void (0) : __assert_fail ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\"" , "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.h" , 855, __extension__ __PRETTY_FUNCTION__)); |
856 | |
857 | // Check that the reserve that follows doesn't invalidate the iterators. |
858 | this->assertSafeToAddRange(From, To); |
859 | |
860 | size_t NumToInsert = std::distance(From, To); |
861 | |
862 | // Ensure there is enough space. |
863 | reserve(this->size() + NumToInsert); |
864 | |
865 | // Uninvalidate the iterator. |
866 | I = this->begin()+InsertElt; |
867 | |
868 | // If there are more elements between the insertion point and the end of the |
869 | // range than there are being inserted, we can use a simple approach to |
870 | // insertion. Since we already reserved space, we know that this won't |
871 | // reallocate the vector. |
872 | if (size_t(this->end()-I) >= NumToInsert) { |
873 | T *OldEnd = this->end(); |
874 | append(std::move_iterator<iterator>(this->end() - NumToInsert), |
875 | std::move_iterator<iterator>(this->end())); |
876 | |
877 | // Copy the existing elements that get replaced. |
878 | std::move_backward(I, OldEnd-NumToInsert, OldEnd); |
879 | |
880 | std::copy(From, To, I); |
881 | return I; |
882 | } |
883 | |
884 | // Otherwise, we're inserting more elements than exist already, and we're |
885 | // not inserting at the end. |
886 | |
887 | // Move over the elements that we're about to overwrite. |
888 | T *OldEnd = this->end(); |
889 | this->set_size(this->size() + NumToInsert); |
890 | size_t NumOverwritten = OldEnd-I; |
891 | this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); |
892 | |
893 | // Replace the overwritten part. |
894 | for (T *J = I; NumOverwritten > 0; --NumOverwritten) { |
895 | *J = *From; |
896 | ++J; ++From; |
897 | } |
898 | |
899 | // Insert the non-overwritten middle part. |
900 | this->uninitialized_copy(From, To, OldEnd); |
901 | return I; |
902 | } |
903 | |
904 | void insert(iterator I, std::initializer_list<T> IL) { |
905 | insert(I, IL.begin(), IL.end()); |
906 | } |
907 | |
908 | template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) { |
909 | if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity ()), false)) |
910 | return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...); |
911 | |
912 | ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); |
913 | this->set_size(this->size() + 1); |
914 | return this->back(); |
915 | } |
916 | |
917 | SmallVectorImpl &operator=(const SmallVectorImpl &RHS); |
918 | |
919 | SmallVectorImpl &operator=(SmallVectorImpl &&RHS); |
920 | |
921 | bool operator==(const SmallVectorImpl &RHS) const { |
922 | if (this->size() != RHS.size()) return false; |
923 | return std::equal(this->begin(), this->end(), RHS.begin()); |
924 | } |
925 | bool operator!=(const SmallVectorImpl &RHS) const { |
926 | return !(*this == RHS); |
927 | } |
928 | |
929 | bool operator<(const SmallVectorImpl &RHS) const { |
930 | return std::lexicographical_compare(this->begin(), this->end(), |
931 | RHS.begin(), RHS.end()); |
932 | } |
933 | }; |
934 | |
935 | template <typename T> |
936 | void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { |
937 | if (this == &RHS) return; |
938 | |
939 | // We can only avoid copying elements if neither vector is small. |
940 | if (!this->isSmall() && !RHS.isSmall()) { |
941 | std::swap(this->BeginX, RHS.BeginX); |
942 | std::swap(this->Size, RHS.Size); |
943 | std::swap(this->Capacity, RHS.Capacity); |
944 | return; |
945 | } |
946 | this->reserve(RHS.size()); |
947 | RHS.reserve(this->size()); |
948 | |
949 | // Swap the shared elements. |
950 | size_t NumShared = this->size(); |
951 | if (NumShared > RHS.size()) NumShared = RHS.size(); |
952 | for (size_type i = 0; i != NumShared; ++i) |
953 | std::swap((*this)[i], RHS[i]); |
954 | |
955 | // Copy over the extra elts. |
956 | if (this->size() > RHS.size()) { |
957 | size_t EltDiff = this->size() - RHS.size(); |
958 | this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); |
959 | RHS.set_size(RHS.size() + EltDiff); |
960 | this->destroy_range(this->begin()+NumShared, this->end()); |
961 | this->set_size(NumShared); |
962 | } else if (RHS.size() > this->size()) { |
963 | size_t EltDiff = RHS.size() - this->size(); |
964 | this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); |
965 | this->set_size(this->size() + EltDiff); |
966 | this->destroy_range(RHS.begin()+NumShared, RHS.end()); |
967 | RHS.set_size(NumShared); |
968 | } |
969 | } |
970 | |
971 | template <typename T> |
972 | SmallVectorImpl<T> &SmallVectorImpl<T>:: |
973 | operator=(const SmallVectorImpl<T> &RHS) { |
974 | // Avoid self-assignment. |
975 | if (this == &RHS) return *this; |
976 | |
977 | // If we already have sufficient space, assign the common elements, then |
978 | // destroy any excess. |
979 | size_t RHSSize = RHS.size(); |
980 | size_t CurSize = this->size(); |
981 | if (CurSize >= RHSSize) { |
982 | // Assign common elements. |
983 | iterator NewEnd; |
984 | if (RHSSize) |
985 | NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); |
986 | else |
987 | NewEnd = this->begin(); |
988 | |
989 | // Destroy excess elements. |
990 | this->destroy_range(NewEnd, this->end()); |
991 | |
992 | // Trim. |
993 | this->set_size(RHSSize); |
994 | return *this; |
995 | } |
996 | |
997 | // If we have to grow to have enough elements, destroy the current elements. |
998 | // This allows us to avoid copying them during the grow. |
999 | // FIXME: don't do this if they're efficiently moveable. |
1000 | if (this->capacity() < RHSSize) { |
1001 | // Destroy current elements. |
1002 | this->clear(); |
1003 | CurSize = 0; |
1004 | this->grow(RHSSize); |
1005 | } else if (CurSize) { |
1006 | // Otherwise, use assignment for the already-constructed elements. |
1007 | std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); |
1008 | } |
1009 | |
1010 | // Copy construct the new elements in place. |
1011 | this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), |
1012 | this->begin()+CurSize); |
1013 | |
1014 | // Set end. |
1015 | this->set_size(RHSSize); |
1016 | return *this; |
1017 | } |
1018 | |
1019 | template <typename T> |
1020 | SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { |
1021 | // Avoid self-assignment. |
1022 | if (this == &RHS) return *this; |
1023 | |
1024 | // If the RHS isn't small, clear this vector and then steal its buffer. |
1025 | if (!RHS.isSmall()) { |
1026 | this->destroy_range(this->begin(), this->end()); |
1027 | if (!this->isSmall()) free(this->begin()); |
1028 | this->BeginX = RHS.BeginX; |
1029 | this->Size = RHS.Size; |
1030 | this->Capacity = RHS.Capacity; |
1031 | RHS.resetToSmall(); |
1032 | return *this; |
1033 | } |
1034 | |
1035 | // If we already have sufficient space, assign the common elements, then |
1036 | // destroy any excess. |
1037 | size_t RHSSize = RHS.size(); |
1038 | size_t CurSize = this->size(); |
1039 | if (CurSize >= RHSSize) { |
1040 | // Assign common elements. |
1041 | iterator NewEnd = this->begin(); |
1042 | if (RHSSize) |
1043 | NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd); |
1044 | |
1045 | // Destroy excess elements and trim the bounds. |
1046 | this->destroy_range(NewEnd, this->end()); |
1047 | this->set_size(RHSSize); |
1048 | |
1049 | // Clear the RHS. |
1050 | RHS.clear(); |
1051 | |
1052 | return *this; |
1053 | } |
1054 | |
1055 | // If we have to grow to have enough elements, destroy the current elements. |
1056 | // This allows us to avoid copying them during the grow. |
1057 | // FIXME: this may not actually make any sense if we can efficiently move |
1058 | // elements. |
1059 | if (this->capacity() < RHSSize) { |
1060 | // Destroy current elements. |
1061 | this->clear(); |
1062 | CurSize = 0; |
1063 | this->grow(RHSSize); |
1064 | } else if (CurSize) { |
1065 | // Otherwise, use assignment for the already-constructed elements. |
1066 | std::move(RHS.begin(), RHS.begin()+CurSize, this->begin()); |
1067 | } |
1068 | |
1069 | // Move-construct the new elements in place. |
1070 | this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), |
1071 | this->begin()+CurSize); |
1072 | |
1073 | // Set end. |
1074 | this->set_size(RHSSize); |
1075 | |
1076 | RHS.clear(); |
1077 | return *this; |
1078 | } |
1079 | |
1080 | /// Storage for the SmallVector elements. This is specialized for the N=0 case |
1081 | /// to avoid allocating unnecessary storage. |
1082 | template <typename T, unsigned N> |
1083 | struct SmallVectorStorage { |
1084 | alignas(T) char InlineElts[N * sizeof(T)]; |
1085 | }; |
1086 | |
1087 | /// We need the storage to be properly aligned even for small-size of 0 so that |
1088 | /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is |
1089 | /// well-defined. |
1090 | template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {}; |
1091 | |
1092 | /// Forward declaration of SmallVector so that |
1093 | /// calculateSmallVectorDefaultInlinedElements can reference |
1094 | /// `sizeof(SmallVector<T, 0>)`. |
1095 | template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector; |
1096 | |
1097 | /// Helper class for calculating the default number of inline elements for |
1098 | /// `SmallVector<T>`. |
1099 | /// |
1100 | /// This should be migrated to a constexpr function when our minimum |
1101 | /// compiler support is enough for multi-statement constexpr functions. |
1102 | template <typename T> struct CalculateSmallVectorDefaultInlinedElements { |
1103 | // Parameter controlling the default number of inlined elements |
1104 | // for `SmallVector<T>`. |
1105 | // |
1106 | // The default number of inlined elements ensures that |
1107 | // 1. There is at least one inlined element. |
1108 | // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless |
1109 | // it contradicts 1. |
1110 | static constexpr size_t kPreferredSmallVectorSizeof = 64; |
1111 | |
1112 | // static_assert that sizeof(T) is not "too big". |
1113 | // |
1114 | // Because our policy guarantees at least one inlined element, it is possible |
1115 | // for an arbitrarily large inlined element to allocate an arbitrarily large |
1116 | // amount of inline storage. We generally consider it an antipattern for a |
1117 | // SmallVector to allocate an excessive amount of inline storage, so we want |
1118 | // to call attention to these cases and make sure that users are making an |
1119 | // intentional decision if they request a lot of inline storage. |
1120 | // |
1121 | // We want this assertion to trigger in pathological cases, but otherwise |
1122 | // not be too easy to hit. To accomplish that, the cutoff is actually somewhat |
1123 | // larger than kPreferredSmallVectorSizeof (otherwise, |
1124 | // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that |
1125 | // pattern seems useful in practice). |
1126 | // |
1127 | // One wrinkle is that this assertion is in theory non-portable, since |
1128 | // sizeof(T) is in general platform-dependent. However, we don't expect this |
1129 | // to be much of an issue, because most LLVM development happens on 64-bit |
1130 | // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for |
1131 | // 32-bit hosts, dodging the issue. The reverse situation, where development |
1132 | // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a |
1133 | // 64-bit host, is expected to be very rare. |
1134 | static_assert( |
1135 | sizeof(T) <= 256, |
1136 | "You are trying to use a default number of inlined elements for " |
1137 | "`SmallVector<T>` but `sizeof(T)` is really big! Please use an " |
1138 | "explicit number of inlined elements with `SmallVector<T, N>` to make " |
1139 | "sure you really want that much inline storage."); |
1140 | |
1141 | // Discount the size of the header itself when calculating the maximum inline |
1142 | // bytes. |
1143 | static constexpr size_t PreferredInlineBytes = |
1144 | kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>); |
1145 | static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T); |
1146 | static constexpr size_t value = |
1147 | NumElementsThatFit == 0 ? 1 : NumElementsThatFit; |
1148 | }; |
1149 | |
1150 | /// This is a 'vector' (really, a variable-sized array), optimized |
1151 | /// for the case when the array is small. It contains some number of elements |
1152 | /// in-place, which allows it to avoid heap allocation when the actual number of |
1153 | /// elements is below that threshold. This allows normal "small" cases to be |
1154 | /// fast without losing generality for large inputs. |
1155 | /// |
1156 | /// \note |
1157 | /// In the absence of a well-motivated choice for the number of inlined |
1158 | /// elements \p N, it is recommended to use \c SmallVector<T> (that is, |
1159 | /// omitting the \p N). This will choose a default number of inlined elements |
1160 | /// reasonable for allocation on the stack (for example, trying to keep \c |
1161 | /// sizeof(SmallVector<T>) around 64 bytes). |
1162 | /// |
1163 | /// \warning This does not attempt to be exception safe. |
1164 | /// |
1165 | /// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h |
1166 | template <typename T, |
1167 | unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value> |
1168 | class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>, |
1169 | SmallVectorStorage<T, N> { |
1170 | public: |
1171 | SmallVector() : SmallVectorImpl<T>(N) {} |
1172 | |
1173 | ~SmallVector() { |
1174 | // Destroy the constructed elements in the vector. |
1175 | this->destroy_range(this->begin(), this->end()); |
1176 | } |
1177 | |
1178 | explicit SmallVector(size_t Size, const T &Value = T()) |
1179 | : SmallVectorImpl<T>(N) { |
1180 | this->assign(Size, Value); |
1181 | } |
1182 | |
1183 | template <typename ItTy, |
1184 | typename = std::enable_if_t<std::is_convertible< |
1185 | typename std::iterator_traits<ItTy>::iterator_category, |
1186 | std::input_iterator_tag>::value>> |
1187 | SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { |
1188 | this->append(S, E); |
1189 | } |
1190 | |
1191 | template <typename RangeTy> |
1192 | explicit SmallVector(const iterator_range<RangeTy> &R) |
1193 | : SmallVectorImpl<T>(N) { |
1194 | this->append(R.begin(), R.end()); |
1195 | } |
1196 | |
1197 | SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) { |
1198 | this->assign(IL); |
1199 | } |
1200 | |
1201 | SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { |
1202 | if (!RHS.empty()) |
1203 | SmallVectorImpl<T>::operator=(RHS); |
1204 | } |
1205 | |
1206 | SmallVector &operator=(const SmallVector &RHS) { |
1207 | SmallVectorImpl<T>::operator=(RHS); |
1208 | return *this; |
1209 | } |
1210 | |
1211 | SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { |
1212 | if (!RHS.empty()) |
1213 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
1214 | } |
1215 | |
1216 | SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) { |
1217 | if (!RHS.empty()) |
1218 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
1219 | } |
1220 | |
1221 | SmallVector &operator=(SmallVector &&RHS) { |
1222 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
1223 | return *this; |
1224 | } |
1225 | |
1226 | SmallVector &operator=(SmallVectorImpl<T> &&RHS) { |
1227 | SmallVectorImpl<T>::operator=(::std::move(RHS)); |
1228 | return *this; |
1229 | } |
1230 | |
1231 | SmallVector &operator=(std::initializer_list<T> IL) { |
1232 | this->assign(IL); |
1233 | return *this; |
1234 | } |
1235 | }; |
1236 | |
1237 | template <typename T, unsigned N> |
1238 | inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { |
1239 | return X.capacity_in_bytes(); |
1240 | } |
1241 | |
1242 | /// Given a range of type R, iterate the entire range and return a |
1243 | /// SmallVector with elements of the vector. This is useful, for example, |
1244 | /// when you want to iterate a range and then sort the results. |
1245 | template <unsigned Size, typename R> |
1246 | SmallVector<typename std::remove_const<typename std::remove_reference< |
1247 | decltype(*std::begin(std::declval<R &>()))>::type>::type, |
1248 | Size> |
1249 | to_vector(R &&Range) { |
1250 | return {std::begin(Range), std::end(Range)}; |
1251 | } |
1252 | |
1253 | } // end namespace llvm |
1254 | |
1255 | namespace std { |
1256 | |
1257 | /// Implement std::swap in terms of SmallVector swap. |
1258 | template<typename T> |
1259 | inline void |
1260 | swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { |
1261 | LHS.swap(RHS); |
1262 | } |
1263 | |
1264 | /// Implement std::swap in terms of SmallVector swap. |
1265 | template<typename T, unsigned N> |
1266 | inline void |
1267 | swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { |
1268 | LHS.swap(RHS); |
1269 | } |
1270 | |
1271 | } // end namespace std |
1272 | |
1273 | #endif // LLVM_ADT_SMALLVECTOR_H |