Bug Summary

File:llvm/lib/MCA/Stages/MicroOpQueueStage.cpp
Warning:line 30, column 31
Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MicroOpQueueStage.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/lib/MCA -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/lib/MCA -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/MCA -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/lib/MCA -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-07-26-235520-9401-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/MCA/Stages/MicroOpQueueStage.cpp

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/MCA/Stages/MicroOpQueueStage.cpp

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
16namespace llvm {
17namespace mca {
18
19#define DEBUG_TYPE"llvm-mca" "llvm-mca"
20
21Error MicroOpQueueStage::moveInstructions() {
22 InstRef IR = Buffer[CurrentInstructionSlotIdx];
23 while (IR && checkNextStage(IR)) {
4
Calling 'InstRef::operator bool'
7
Returning from 'InstRef::operator bool'
8
Calling 'Stage::checkNextStage'
11
Returning from 'Stage::checkNextStage'
12
Loop condition is true. Entering loop body
24 if (llvm::Error Val = moveToTheNextStage(IR))
13
Assuming the condition is false
14
Taking false branch
25 return Val;
26
27 Buffer[CurrentInstructionSlotIdx].invalidate();
15
Value assigned to field 'Size'
28 unsigned NormalizedOpcodes = getNormalizedOpcodes(IR);
16
Calling 'MicroOpQueueStage::getNormalizedOpcodes'
19
Returning from 'MicroOpQueueStage::getNormalizedOpcodes'
29 CurrentInstructionSlotIdx += NormalizedOpcodes;
30 CurrentInstructionSlotIdx %= Buffer.size();
20
Calling 'SmallVectorBase::size'
22
Returning from 'SmallVectorBase::size'
23
Division by zero
31 AvailableEntries += NormalizedOpcodes;
32 IR = Buffer[CurrentInstructionSlotIdx];
33 }
34
35 return llvm::ErrorSuccess();
36}
37
38MicroOpQueueStage::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
46Error 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
56Error MicroOpQueueStage::cycleStart() {
57 CurrentIPC = 0;
58 if (!IsZeroLatencyStage)
59 return moveInstructions();
60 return llvm::ErrorSuccess();
61}
62
63Error MicroOpQueueStage::cycleEnd() {
64 if (IsZeroLatencyStage)
1
Assuming field 'IsZeroLatencyStage' is true
2
Taking true branch
65 return moveInstructions();
3
Calling 'MicroOpQueueStage::moveInstructions'
66 return llvm::ErrorSuccess();
67}
68
69} // namespace mca
70} // namespace llvm

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Instruction.h

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
30namespace llvm {
31
32namespace mca {
33
34constexpr int UNKNOWN_CYCLES = -512;
35
36/// A representation of an mca::Instruction operand
37/// for use in mca::CustomBehaviour.
38class 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
64public:
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.
135struct 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.
163struct 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
180class ReadState;
181
182/// A critical data dependency descriptor.
183///
184/// Field RegID is set to the invalid register for memory dependencies.
185struct 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.
197class 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
247public:
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.
326class 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
355public:
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.
389class CycleSegment {
390 unsigned Begin; // Inclusive.
391 unsigned End; // Exclusive.
392 bool Reserved; // Resources associated to this segment must be reserved.
393
394public:
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.
436struct 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
447struct 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.
498class 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
520public:
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.
569class 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
615public:
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.
686class InstRef {
687 std::pair<unsigned, Instruction *> Data;
688
689public:
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; }
5
Assuming the condition is true
6
Returning the value 1, which participates in a condition later
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
715inline 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

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Stages/Stage.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
22namespace llvm {
23namespace mca {
24
25class InstRef;
26
27class Stage {
28 Stage *NextInSequence;
29 std::set<HWEventListener *> Listeners;
30
31 Stage(const Stage &Other) = delete;
32 Stage &operator=(const Stage &Other) = delete;
33
34protected:
35 const std::set<HWEventListener *> &getListeners() const { return Listeners; }
36
37public:
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);
9
Assuming field 'NextInSequence' is non-null
10
Returning value, which participates in a condition later
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

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/MCA/Stages/MicroOpQueueStage.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
22namespace llvm {
23namespace mca {
24
25/// A stage that simulates a queue of instruction opcodes.
26class 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;
17
Assuming 'NormalizedOpcodes' is 0
18
'?' condition is false
59 }
60
61 Error moveInstructions();
62
63public:
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

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/ADT/SmallVector.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
35namespace 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.
45template <class Size_T> class SmallVectorBase {
46protected:
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
69public:
70 size_t size() const { return Size; }
21
Returning zero
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
90template <class T>
91using 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.
96template <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.
105template <typename T, typename = void>
106class 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
120protected:
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
233public:
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.
312template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
313 (is_trivially_move_constructible<T>::value) &&
314 std::is_trivially_destructible<T>::value>
315class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
316 friend class SmallVectorTemplateCommon<T>;
317
318protected:
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
403public:
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.
423template <typename T, bool TriviallyCopyable>
424void 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.
432template <typename T, bool TriviallyCopyable>
433void 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.
443template <typename T, bool TriviallyCopyable>
444void 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.
458template <typename T>
459class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
460 friend class SmallVectorTemplateCommon<T>;
461
462protected:
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
545public:
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.
557template <typename T>
558class SmallVectorImpl : public SmallVectorTemplateBase<T> {
559 using SuperClass = SmallVectorTemplateBase<T>;
560
561public:
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
567protected:
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
575public:
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
590private:
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
605public:
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
735private:
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
772public:
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
935template <typename T>
936void 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
971template <typename T>
972SmallVectorImpl<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
1019template <typename T>
1020SmallVectorImpl<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.
1082template <typename T, unsigned N>
1083struct 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.
1090template <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>)`.
1095template <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.
1102template <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
1166template <typename T,
1167 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1168class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
1169 SmallVectorStorage<T, N> {
1170public:
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
1237template <typename T, unsigned N>
1238inline 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.
1245template <unsigned Size, typename R>
1246SmallVector<typename std::remove_const<typename std::remove_reference<
1247 decltype(*std::begin(std::declval<R &>()))>::type>::type,
1248 Size>
1249to_vector(R &&Range) {
1250 return {std::begin(Range), std::end(Range)};
1251}
1252
1253} // end namespace llvm
1254
1255namespace 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