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