clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name CriticalAntiDepBreaker.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-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D 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-14/lib/clang/14.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-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -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-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen/CriticalAntiDepBreaker.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | #include "CriticalAntiDepBreaker.h" |
16 | #include "llvm/ADT/ArrayRef.h" |
17 | #include "llvm/ADT/DenseMap.h" |
18 | #include "llvm/ADT/SmallVector.h" |
19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
20 | #include "llvm/CodeGen/MachineFrameInfo.h" |
21 | #include "llvm/CodeGen/MachineFunction.h" |
22 | #include "llvm/CodeGen/MachineInstr.h" |
23 | #include "llvm/CodeGen/MachineOperand.h" |
24 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
25 | #include "llvm/CodeGen/RegisterClassInfo.h" |
26 | #include "llvm/CodeGen/ScheduleDAG.h" |
27 | #include "llvm/CodeGen/TargetInstrInfo.h" |
28 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
29 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
30 | #include "llvm/MC/MCInstrDesc.h" |
31 | #include "llvm/MC/MCRegisterInfo.h" |
32 | #include "llvm/Support/Debug.h" |
33 | #include "llvm/Support/raw_ostream.h" |
34 | #include <cassert> |
35 | #include <utility> |
36 | |
37 | using namespace llvm; |
38 | |
39 | #define DEBUG_TYPE "post-RA-sched" |
40 | |
41 | CriticalAntiDepBreaker::CriticalAntiDepBreaker(MachineFunction &MFi, |
42 | const RegisterClassInfo &RCI) |
43 | : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), |
44 | TII(MF.getSubtarget().getInstrInfo()), |
45 | TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI), |
46 | Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0), |
47 | DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {} |
48 | |
49 | CriticalAntiDepBreaker::~CriticalAntiDepBreaker() = default; |
50 | |
51 | void CriticalAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { |
52 | const unsigned BBSize = BB->size(); |
53 | for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) { |
54 | |
55 | Classes[i] = nullptr; |
56 | |
57 | |
58 | KillIndices[i] = ~0u; |
59 | DefIndices[i] = BBSize; |
60 | } |
61 | |
62 | |
63 | KeepRegs.reset(); |
64 | |
65 | bool IsReturnBlock = BB->isReturnBlock(); |
66 | |
67 | |
68 | for (const MachineBasicBlock *Succ : BB->successors()) |
69 | for (const auto &LI : Succ->liveins()) { |
70 | for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) { |
71 | unsigned Reg = *AI; |
72 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
73 | KillIndices[Reg] = BBSize; |
74 | DefIndices[Reg] = ~0u; |
75 | } |
76 | } |
77 | |
78 | |
79 | |
80 | |
81 | const MachineFrameInfo &MFI = MF.getFrameInfo(); |
82 | BitVector Pristine = MFI.getPristineRegs(MF); |
83 | for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I; |
84 | ++I) { |
85 | unsigned Reg = *I; |
86 | if (!IsReturnBlock && !Pristine.test(Reg)) |
87 | continue; |
88 | for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { |
89 | unsigned Reg = *AI; |
90 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
91 | KillIndices[Reg] = BBSize; |
92 | DefIndices[Reg] = ~0u; |
93 | } |
94 | } |
95 | } |
96 | |
97 | void CriticalAntiDepBreaker::FinishBlock() { |
98 | RegRefs.clear(); |
99 | KeepRegs.reset(); |
100 | } |
101 | |
102 | void CriticalAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count, |
103 | unsigned InsertPosIndex) { |
104 | |
105 | |
106 | |
107 | |
108 | |
109 | |
110 | |
111 | if (MI.isDebugInstr() || MI.isKill()) |
112 | return; |
113 | assert(Count < InsertPosIndex && "Instruction index out of expected range!"); |
114 | |
115 | for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { |
116 | if (KillIndices[Reg] != ~0u) { |
117 | |
118 | |
119 | |
120 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
121 | KillIndices[Reg] = Count; |
122 | } else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) { |
123 | |
124 | |
125 | |
126 | |
127 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
128 | |
129 | |
130 | |
131 | DefIndices[Reg] = InsertPosIndex; |
132 | } |
133 | } |
134 | |
135 | PrescanInstruction(MI); |
136 | ScanInstruction(MI, Count); |
137 | } |
138 | |
139 | |
140 | |
141 | static const SDep *CriticalPathStep(const SUnit *SU) { |
142 | const SDep *Next = nullptr; |
143 | unsigned NextDepth = 0; |
144 | |
145 | for (const SDep &P : SU->Preds) { |
146 | const SUnit *PredSU = P.getSUnit(); |
147 | unsigned PredLatency = P.getLatency(); |
148 | unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; |
149 | |
150 | |
151 | if (NextDepth < PredTotalLatency || |
152 | (NextDepth == PredTotalLatency && P.getKind() == SDep::Anti)) { |
153 | NextDepth = PredTotalLatency; |
154 | Next = &P; |
155 | } |
156 | } |
157 | return Next; |
158 | } |
159 | |
160 | void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr &MI) { |
161 | |
162 | |
163 | |
164 | |
165 | |
166 | |
167 | |
168 | |
169 | |
170 | |
171 | |
172 | |
173 | |
174 | |
175 | |
176 | |
177 | bool Special = |
178 | MI.isCall() || MI.hasExtraSrcRegAllocReq() || TII->isPredicated(MI); |
179 | |
180 | |
181 | |
182 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
183 | MachineOperand &MO = MI.getOperand(i); |
184 | if (!MO.isReg()) continue; |
185 | Register Reg = MO.getReg(); |
186 | if (Reg == 0) continue; |
187 | const TargetRegisterClass *NewRC = nullptr; |
188 | |
189 | if (i < MI.getDesc().getNumOperands()) |
190 | NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); |
191 | |
192 | |
193 | |
194 | if (!Classes[Reg] && NewRC) |
195 | Classes[Reg] = NewRC; |
196 | else if (!NewRC || Classes[Reg] != NewRC) |
197 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
198 | |
199 | |
200 | for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { |
201 | |
202 | |
203 | |
204 | unsigned AliasReg = *AI; |
205 | if (Classes[AliasReg]) { |
206 | Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); |
207 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
208 | } |
209 | } |
210 | |
211 | |
212 | if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) |
213 | RegRefs.insert(std::make_pair(Reg, &MO)); |
214 | |
215 | |
216 | |
217 | |
218 | |
219 | |
220 | |
221 | |
222 | |
223 | |
224 | |
225 | if (MI.isRegTiedToUseOperand(i) && |
226 | Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) { |
227 | for (MCSubRegIterator SubRegs(Reg, TRI, true); |
228 | SubRegs.isValid(); ++SubRegs) { |
229 | KeepRegs.set(*SubRegs); |
230 | } |
231 | for (MCSuperRegIterator SuperRegs(Reg, TRI); |
232 | SuperRegs.isValid(); ++SuperRegs) { |
233 | KeepRegs.set(*SuperRegs); |
234 | } |
235 | } |
236 | |
237 | if (MO.isUse() && Special) { |
238 | if (!KeepRegs.test(Reg)) { |
239 | for (MCSubRegIterator SubRegs(Reg, TRI, true); |
240 | SubRegs.isValid(); ++SubRegs) |
241 | KeepRegs.set(*SubRegs); |
242 | } |
243 | } |
244 | } |
245 | } |
246 | |
247 | void CriticalAntiDepBreaker::ScanInstruction(MachineInstr &MI, unsigned Count) { |
248 | |
249 | |
250 | |
251 | assert(!MI.isKill() && "Attempting to scan a kill instruction"); |
252 | |
253 | if (!TII->isPredicated(MI)) { |
| 20 | | Assuming the condition is true | |
|
| |
254 | |
255 | |
256 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
| 22 | | Loop condition is true. Entering loop body | |
|
257 | MachineOperand &MO = MI.getOperand(i); |
258 | |
259 | if (MO.isRegMask()) { |
| |
260 | auto ClobbersPhysRegAndSubRegs = [&](unsigned PhysReg) { |
261 | for (MCSubRegIterator SRI(PhysReg, TRI, true); SRI.isValid(); ++SRI) |
262 | if (!MO.clobbersPhysReg(*SRI)) |
263 | return false; |
264 | |
265 | return true; |
266 | }; |
267 | |
268 | for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) { |
| 24 | | Assuming 'i' is not equal to 'e' | |
|
| 25 | | Loop condition is true. Entering loop body | |
|
| 28 | | Assuming 'i' is equal to 'e' | |
|
| 29 | | Loop condition is false. Execution continues on line 279 | |
|
269 | if (ClobbersPhysRegAndSubRegs(i)) { |
| 26 | | Assuming the condition is false | |
|
| |
270 | DefIndices[i] = Count; |
271 | KillIndices[i] = ~0u; |
272 | KeepRegs.reset(i); |
273 | Classes[i] = nullptr; |
274 | RegRefs.erase(i); |
275 | } |
276 | } |
277 | } |
278 | |
279 | if (!MO.isReg()) continue; |
| |
280 | Register Reg = MO.getReg(); |
281 | if (Reg == 0) continue; |
| |
282 | if (!MO.isDef()) continue; |
| 32 | | Assuming the condition is false | |
|
| |
283 | |
284 | |
285 | if (MI.isRegTiedToUseOperand(i)) |
| |
286 | continue; |
287 | |
288 | |
289 | |
290 | bool Keep = KeepRegs.test(Reg); |
291 | |
292 | |
293 | |
294 | for (MCSubRegIterator SRI(Reg, TRI, true); SRI.isValid(); ++SRI) { |
| 35 | | Loop condition is false. Execution continues on line 304 | |
|
295 | unsigned SubregReg = *SRI; |
296 | DefIndices[SubregReg] = Count; |
297 | KillIndices[SubregReg] = ~0u; |
298 | Classes[SubregReg] = nullptr; |
299 | RegRefs.erase(SubregReg); |
300 | if (!Keep) |
301 | KeepRegs.reset(SubregReg); |
302 | } |
303 | |
304 | for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) |
| 36 | | Calling constructor for 'MCSuperRegIterator' | |
|
305 | Classes[*SR] = reinterpret_cast<TargetRegisterClass *>(-1); |
306 | } |
307 | } |
308 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
309 | MachineOperand &MO = MI.getOperand(i); |
310 | if (!MO.isReg()) continue; |
311 | Register Reg = MO.getReg(); |
312 | if (Reg == 0) continue; |
313 | if (!MO.isUse()) continue; |
314 | |
315 | const TargetRegisterClass *NewRC = nullptr; |
316 | if (i < MI.getDesc().getNumOperands()) |
317 | NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); |
318 | |
319 | |
320 | |
321 | if (!Classes[Reg] && NewRC) |
322 | Classes[Reg] = NewRC; |
323 | else if (!NewRC || Classes[Reg] != NewRC) |
324 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
325 | |
326 | RegRefs.insert(std::make_pair(Reg, &MO)); |
327 | |
328 | |
329 | |
330 | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { |
331 | unsigned AliasReg = *AI; |
332 | if (KillIndices[AliasReg] == ~0u) { |
333 | KillIndices[AliasReg] = Count; |
334 | DefIndices[AliasReg] = ~0u; |
335 | } |
336 | } |
337 | } |
338 | } |
339 | |
340 | |
341 | |
342 | |
343 | |
344 | |
345 | |
346 | |
347 | |
348 | |
349 | |
350 | |
351 | bool |
352 | CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin, |
353 | RegRefIter RegRefEnd, |
354 | unsigned NewReg) { |
355 | for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) { |
356 | MachineOperand *RefOper = I->second; |
357 | |
358 | |
359 | |
360 | |
361 | if (RefOper->isDef() && RefOper->isEarlyClobber()) |
362 | return true; |
363 | |
364 | |
365 | MachineInstr *MI = RefOper->getParent(); |
366 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
367 | const MachineOperand &CheckOper = MI->getOperand(i); |
368 | |
369 | if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg)) |
370 | return true; |
371 | |
372 | if (!CheckOper.isReg() || !CheckOper.isDef() || |
373 | CheckOper.getReg() != NewReg) |
374 | continue; |
375 | |
376 | |
377 | |
378 | if (RefOper->isDef()) |
379 | return true; |
380 | |
381 | |
382 | |
383 | if (CheckOper.isEarlyClobber()) |
384 | return true; |
385 | |
386 | |
387 | |
388 | if (MI->isInlineAsm()) |
389 | return true; |
390 | } |
391 | } |
392 | return false; |
393 | } |
394 | |
395 | unsigned CriticalAntiDepBreaker:: |
396 | findSuitableFreeRegister(RegRefIter RegRefBegin, |
397 | RegRefIter RegRefEnd, |
398 | unsigned AntiDepReg, |
399 | unsigned LastNewReg, |
400 | const TargetRegisterClass *RC, |
401 | SmallVectorImpl<unsigned> &Forbid) { |
402 | ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC); |
403 | for (unsigned i = 0; i != Order.size(); ++i) { |
404 | unsigned NewReg = Order[i]; |
405 | |
406 | if (NewReg == AntiDepReg) continue; |
407 | |
408 | |
409 | |
410 | if (NewReg == LastNewReg) continue; |
411 | |
412 | |
413 | |
414 | if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue; |
415 | |
416 | |
417 | assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) |
418 | && "Kill and Def maps aren't consistent for AntiDepReg!"); |
419 | assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) |
420 | && "Kill and Def maps aren't consistent for NewReg!"); |
421 | if (KillIndices[NewReg] != ~0u || |
422 | Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || |
423 | KillIndices[AntiDepReg] > DefIndices[NewReg]) |
424 | continue; |
425 | |
426 | bool Forbidden = false; |
427 | for (unsigned R : Forbid) |
428 | if (TRI->regsOverlap(NewReg, R)) { |
429 | Forbidden = true; |
430 | break; |
431 | } |
432 | if (Forbidden) continue; |
433 | return NewReg; |
434 | } |
435 | |
436 | |
437 | return 0; |
438 | } |
439 | |
440 | unsigned CriticalAntiDepBreaker:: |
441 | BreakAntiDependencies(const std::vector<SUnit> &SUnits, |
442 | MachineBasicBlock::iterator Begin, |
443 | MachineBasicBlock::iterator End, |
444 | unsigned InsertPosIndex, |
445 | DbgValueVector &DbgValues) { |
446 | |
447 | |
448 | if (SUnits.empty()) return 0; |
| 1 | Assuming the condition is false | |
|
| |
449 | |
450 | |
451 | |
452 | |
453 | |
454 | DenseMap<MachineInstr *, const SUnit *> MISUnitMap; |
455 | |
456 | |
457 | const SUnit *Max = nullptr; |
458 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
| 3 | | Assuming 'i' is not equal to 'e' | |
|
| 4 | | Loop condition is true. Entering loop body | |
|
| 5 | | Assuming 'i' is equal to 'e' | |
|
| 6 | | Loop condition is false. Execution continues on line 464 | |
|
459 | const SUnit *SU = &SUnits[i]; |
460 | MISUnitMap[SU->getInstr()] = SU; |
461 | if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency) |
462 | Max = SU; |
463 | } |
464 | assert(Max && "Failed to find bottom of the critical path"); |
465 | |
466 | #ifndef NDEBUG |
467 | { |
468 | LLVM_DEBUG(dbgs() << "Critical path has total latency " |
469 | << (Max->getDepth() + Max->Latency) << "\n"); |
470 | LLVM_DEBUG(dbgs() << "Available regs:"); |
471 | for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { |
472 | if (KillIndices[Reg] == ~0u) |
473 | LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); |
474 | } |
475 | LLVM_DEBUG(dbgs() << '\n'); |
476 | } |
477 | #endif |
478 | |
479 | |
480 | |
481 | const SUnit *CriticalPathSU = Max; |
482 | MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); |
483 | |
484 | |
485 | |
486 | |
487 | |
488 | |
489 | |
490 | |
491 | |
492 | |
493 | |
494 | |
495 | |
496 | |
497 | |
498 | |
499 | |
500 | |
501 | |
502 | |
503 | |
504 | |
505 | |
506 | |
507 | |
508 | |
509 | |
510 | |
511 | |
512 | |
513 | |
514 | |
515 | |
516 | |
517 | |
518 | |
519 | |
520 | |
521 | |
522 | |
523 | |
524 | |
525 | std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0); |
526 | |
527 | |
528 | |
529 | |
530 | unsigned Broken = 0; |
531 | unsigned Count = InsertPosIndex - 1; |
532 | for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) { |
| 7 | | Loop condition is true. Entering loop body | |
|
533 | MachineInstr &MI = *--I; |
534 | |
535 | |
536 | |
537 | |
538 | |
539 | |
540 | |
541 | if (MI.isDebugInstr() || MI.isKill()) |
| |
542 | continue; |
543 | |
544 | |
545 | |
546 | |
547 | |
548 | |
549 | |
550 | |
551 | |
552 | |
553 | |
554 | |
555 | |
556 | |
557 | unsigned AntiDepReg = 0; |
558 | if (&MI == CriticalPathMI) { |
| 9 | | Assuming the condition is false | |
|
| |
559 | if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) { |
560 | const SUnit *NextSU = Edge->getSUnit(); |
561 | |
562 | |
563 | if (Edge->getKind() == SDep::Anti) { |
564 | AntiDepReg = Edge->getReg(); |
565 | assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); |
566 | if (!MRI.isAllocatable(AntiDepReg)) |
567 | |
568 | AntiDepReg = 0; |
569 | else if (KeepRegs.test(AntiDepReg)) |
570 | |
571 | |
572 | AntiDepReg = 0; |
573 | else { |
574 | |
575 | |
576 | |
577 | |
578 | |
579 | |
580 | |
581 | |
582 | for (const SDep &P : CriticalPathSU->Preds) |
583 | if (P.getSUnit() == NextSU |
584 | ? (P.getKind() != SDep::Anti || P.getReg() != AntiDepReg) |
585 | : (P.getKind() == SDep::Data && |
586 | P.getReg() == AntiDepReg)) { |
587 | AntiDepReg = 0; |
588 | break; |
589 | } |
590 | } |
591 | } |
592 | CriticalPathSU = NextSU; |
593 | CriticalPathMI = CriticalPathSU->getInstr(); |
594 | } else { |
595 | |
596 | CriticalPathSU = nullptr; |
597 | CriticalPathMI = nullptr; |
598 | } |
599 | } |
600 | |
601 | PrescanInstruction(MI); |
602 | |
603 | SmallVector<unsigned, 2> ForbidRegs; |
604 | |
605 | |
606 | |
607 | |
608 | if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI)) |
| 11 | | Assuming the condition is false | |
|
| 12 | | Assuming the condition is false | |
|
| 13 | | Assuming the condition is false | |
|
| |
609 | |
610 | |
611 | AntiDepReg = 0; |
612 | else if (AntiDepReg) { |
613 | |
614 | |
615 | |
616 | |
617 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
618 | MachineOperand &MO = MI.getOperand(i); |
619 | if (!MO.isReg()) continue; |
620 | Register Reg = MO.getReg(); |
621 | if (Reg == 0) continue; |
622 | if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) { |
623 | AntiDepReg = 0; |
624 | break; |
625 | } |
626 | if (MO.isDef() && Reg != AntiDepReg) |
627 | ForbidRegs.push_back(Reg); |
628 | } |
629 | } |
630 | |
631 | |
632 | |
633 | const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] |
| |
| |
634 | : nullptr; |
635 | assert((AntiDepReg == 0 || RC != nullptr) && |
636 | "Register should be live if it's causing an anti-dependence!"); |
637 | if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) |
| |
638 | AntiDepReg = 0; |
639 | |
640 | |
641 | |
642 | |
643 | |
644 | if (AntiDepReg != 0) { |
| |
645 | std::pair<std::multimap<unsigned, MachineOperand *>::iterator, |
646 | std::multimap<unsigned, MachineOperand *>::iterator> |
647 | Range = RegRefs.equal_range(AntiDepReg); |
648 | if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second, |
649 | AntiDepReg, |
650 | LastNewReg[AntiDepReg], |
651 | RC, ForbidRegs)) { |
652 | LLVM_DEBUG(dbgs() << "Breaking anti-dependence edge on " |
653 | << printReg(AntiDepReg, TRI) << " with " |
654 | << RegRefs.count(AntiDepReg) << " references" |
655 | << " using " << printReg(NewReg, TRI) << "!\n"); |
656 | |
657 | |
658 | |
659 | for (std::multimap<unsigned, MachineOperand *>::iterator |
660 | Q = Range.first, QE = Range.second; Q != QE; ++Q) { |
661 | Q->second->setReg(NewReg); |
662 | |
663 | |
664 | |
665 | const SUnit *SU = MISUnitMap[Q->second->getParent()]; |
666 | if (!SU) continue; |
667 | UpdateDbgValues(DbgValues, Q->second->getParent(), |
668 | AntiDepReg, NewReg); |
669 | } |
670 | |
671 | |
672 | |
673 | |
674 | Classes[NewReg] = Classes[AntiDepReg]; |
675 | DefIndices[NewReg] = DefIndices[AntiDepReg]; |
676 | KillIndices[NewReg] = KillIndices[AntiDepReg]; |
677 | assert(((KillIndices[NewReg] == ~0u) != |
678 | (DefIndices[NewReg] == ~0u)) && |
679 | "Kill and Def maps aren't consistent for NewReg!"); |
680 | |
681 | Classes[AntiDepReg] = nullptr; |
682 | DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; |
683 | KillIndices[AntiDepReg] = ~0u; |
684 | assert(((KillIndices[AntiDepReg] == ~0u) != |
685 | (DefIndices[AntiDepReg] == ~0u)) && |
686 | "Kill and Def maps aren't consistent for AntiDepReg!"); |
687 | |
688 | RegRefs.erase(AntiDepReg); |
689 | LastNewReg[AntiDepReg] = NewReg; |
690 | ++Broken; |
691 | } |
692 | } |
693 | |
694 | ScanInstruction(MI, Count); |
| 19 | | Calling 'CriticalAntiDepBreaker::ScanInstruction' | |
|
695 | } |
696 | |
697 | return Broken; |
698 | } |
699 | |
700 | AntiDepBreaker * |
701 | llvm::createCriticalAntiDepBreaker(MachineFunction &MFi, |
702 | const RegisterClassInfo &RCI) { |
703 | return new CriticalAntiDepBreaker(MFi, RCI); |
704 | } |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | |
31 | |
32 | |
33 | |
34 | |
35 | |
36 | |
37 | |
38 | |
39 | |
40 | |
41 | |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | |
48 | |
49 | |
50 | |
51 | |
52 | |
53 | |
54 | |
55 | |
56 | #ifndef _STL_VECTOR_H |
57 | #define _STL_VECTOR_H 1 |
58 | |
59 | #include <bits/stl_iterator_base_funcs.h> |
60 | #include <bits/functexcept.h> |
61 | #include <bits/concept_check.h> |
62 | #if __cplusplus >= 201103L |
63 | #include <initializer_list> |
64 | #endif |
65 | #if __cplusplus > 201703L |
66 | # include <compare> |
67 | #endif |
68 | |
69 | #include <debug/assertions.h> |
70 | |
71 | #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |
72 | extern "C" void |
73 | __sanitizer_annotate_contiguous_container(const void*, const void*, |
74 | const void*, const void*); |
75 | #endif |
76 | |
77 | namespace std _GLIBCXX_VISIBILITY(default) |
78 | { |
79 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
80 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
81 | |
82 | |
83 | template<typename _Tp, typename _Alloc> |
84 | struct _Vector_base |
85 | { |
86 | typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template |
87 | rebind<_Tp>::other _Tp_alloc_type; |
88 | typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer |
89 | pointer; |
90 | |
91 | struct _Vector_impl_data |
92 | { |
93 | pointer _M_start; |
94 | pointer _M_finish; |
95 | pointer _M_end_of_storage; |
96 | |
97 | _Vector_impl_data() _GLIBCXX_NOEXCEPT |
98 | : _M_start(), _M_finish(), _M_end_of_storage() |
99 | { } |
100 | |
101 | #if __cplusplus >= 201103L |
102 | _Vector_impl_data(_Vector_impl_data&& __x) noexcept |
103 | : _M_start(__x._M_start), _M_finish(__x._M_finish), |
104 | _M_end_of_storage(__x._M_end_of_storage) |
105 | { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); } |
106 | #endif |
107 | |
108 | void |
109 | _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT |
110 | { |
111 | _M_start = __x._M_start; |
112 | _M_finish = __x._M_finish; |
113 | _M_end_of_storage = __x._M_end_of_storage; |
114 | } |
115 | |
116 | void |
117 | _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT |
118 | { |
119 | |
120 | |
121 | _Vector_impl_data __tmp; |
122 | __tmp._M_copy_data(*this); |
123 | _M_copy_data(__x); |
124 | __x._M_copy_data(__tmp); |
125 | } |
126 | }; |
127 | |
128 | struct _Vector_impl |
129 | : public _Tp_alloc_type, public _Vector_impl_data |
130 | { |
131 | _Vector_impl() _GLIBCXX_NOEXCEPT_IF( |
132 | is_nothrow_default_constructible<_Tp_alloc_type>::value) |
133 | : _Tp_alloc_type() |
134 | { } |
135 | |
136 | _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT |
137 | : _Tp_alloc_type(__a) |
138 | { } |
139 | |
140 | #if __cplusplus >= 201103L |
141 | |
142 | |
143 | _Vector_impl(_Vector_impl&& __x) noexcept |
144 | : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x)) |
145 | { } |
146 | |
147 | _Vector_impl(_Tp_alloc_type&& __a) noexcept |
148 | : _Tp_alloc_type(std::move(__a)) |
149 | { } |
150 | |
151 | _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept |
152 | : _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv)) |
153 | { } |
154 | #endif |
155 | |
156 | #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |
157 | template<typename = _Tp_alloc_type> |
158 | struct _Asan |
159 | { |
160 | typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type> |
161 | ::size_type size_type; |
162 | |
163 | static void _S_shrink(_Vector_impl&, size_type) { } |
164 | static void _S_on_dealloc(_Vector_impl&) { } |
165 | |
166 | typedef _Vector_impl& _Reinit; |
167 | |
168 | struct _Grow |
169 | { |
170 | _Grow(_Vector_impl&, size_type) { } |
171 | void _M_grew(size_type) { } |
172 | }; |
173 | }; |
174 | |
175 | |
176 | template<typename _Up> |
177 | struct _Asan<allocator<_Up> > |
178 | { |
179 | typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type> |
180 | ::size_type size_type; |
181 | |
182 | |
183 | |
184 | static void |
185 | _S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr) |
186 | { |
187 | __sanitizer_annotate_contiguous_container(__impl._M_start, |
188 | __impl._M_end_of_storage, __prev, __curr); |
189 | } |
190 | |
191 | static void |
192 | _S_grow(_Vector_impl& __impl, size_type __n) |
193 | { _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); } |
194 | |
195 | static void |
196 | _S_shrink(_Vector_impl& __impl, size_type __n) |
197 | { _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); } |
198 | |
199 | static void |
200 | _S_on_dealloc(_Vector_impl& __impl) |
201 | { |
202 | if (__impl._M_start) |
203 | _S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage); |
204 | } |
205 | |
206 | |
207 | struct _Reinit |
208 | { |
209 | explicit _Reinit(_Vector_impl& __impl) : _M_impl(__impl) |
210 | { |
211 | |
212 | _S_on_dealloc(_M_impl); |
213 | } |
214 | |
215 | ~_Reinit() |
216 | { |
217 | |
218 | if (_M_impl._M_start) |
219 | _S_adjust(_M_impl, _M_impl._M_end_of_storage, |
220 | _M_impl._M_finish); |
221 | } |
222 | |
223 | _Vector_impl& _M_impl; |
224 | |
225 | #if __cplusplus >= 201103L |
226 | _Reinit(const _Reinit&) = delete; |
227 | _Reinit& operator=(const _Reinit&) = delete; |
228 | #endif |
229 | }; |
230 | |
231 | |
232 | struct _Grow |
233 | { |
234 | _Grow(_Vector_impl& __impl, size_type __n) |
235 | : _M_impl(__impl), _M_n(__n) |
236 | { _S_grow(_M_impl, __n); } |
237 | |
238 | ~_Grow() { if (_M_n) _S_shrink(_M_impl, _M_n); } |
239 | |
240 | void _M_grew(size_type __n) { _M_n -= __n; } |
241 | |
242 | #if __cplusplus >= 201103L |
243 | _Grow(const _Grow&) = delete; |
244 | _Grow& operator=(const _Grow&) = delete; |
245 | #endif |
246 | private: |
247 | _Vector_impl& _M_impl; |
248 | size_type _M_n; |
249 | }; |
250 | }; |
251 | |
252 | #define _GLIBCXX_ASAN_ANNOTATE_REINIT \ |
253 | typename _Base::_Vector_impl::template _Asan<>::_Reinit const \ |
254 | __attribute__((__unused__)) __reinit_guard(this->_M_impl) |
255 | #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \ |
256 | typename _Base::_Vector_impl::template _Asan<>::_Grow \ |
257 | __attribute__((__unused__)) __grow_guard(this->_M_impl, (n)) |
258 | #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n) |
259 | #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \ |
260 | _Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n) |
261 | #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \ |
262 | _Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl) |
263 | #else // ! (_GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR) |
264 | #define _GLIBCXX_ASAN_ANNOTATE_REINIT |
265 | #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) |
266 | #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) |
267 | #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) |
268 | #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC |
269 | #endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |
270 | }; |
271 | |
272 | public: |
273 | typedef _Alloc allocator_type; |
274 | |
275 | _Tp_alloc_type& |
276 | _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT |
277 | { return this->_M_impl; } |
278 | |
279 | const _Tp_alloc_type& |
280 | _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT |
281 | { return this->_M_impl; } |
282 | |
283 | allocator_type |
284 | get_allocator() const _GLIBCXX_NOEXCEPT |
285 | { return allocator_type(_M_get_Tp_allocator()); } |
286 | |
287 | #if __cplusplus >= 201103L |
288 | _Vector_base() = default; |
289 | #else |
290 | _Vector_base() { } |
291 | #endif |
292 | |
293 | _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT |
294 | : _M_impl(__a) { } |
295 | |
296 | |
297 | #if !_GLIBCXX_INLINE_VERSION |
298 | _Vector_base(size_t __n) |
299 | : _M_impl() |
300 | { _M_create_storage(__n); } |
301 | #endif |
302 | |
303 | _Vector_base(size_t __n, const allocator_type& __a) |
304 | : _M_impl(__a) |
305 | { _M_create_storage(__n); } |
306 | |
307 | #if __cplusplus >= 201103L |
308 | _Vector_base(_Vector_base&&) = default; |
309 | |
310 | |
311 | # if !_GLIBCXX_INLINE_VERSION |
312 | _Vector_base(_Tp_alloc_type&& __a) noexcept |
313 | : _M_impl(std::move(__a)) { } |
314 | |
315 | _Vector_base(_Vector_base&& __x, const allocator_type& __a) |
316 | : _M_impl(__a) |
317 | { |
318 | if (__x.get_allocator() == __a) |
319 | this->_M_impl._M_swap_data(__x._M_impl); |
320 | else |
321 | { |
322 | size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start; |
323 | _M_create_storage(__n); |
324 | } |
325 | } |
326 | # endif |
327 | |
328 | _Vector_base(const allocator_type& __a, _Vector_base&& __x) |
329 | : _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl)) |
330 | { } |
331 | #endif |
332 | |
333 | ~_Vector_base() _GLIBCXX_NOEXCEPT |
334 | { |
335 | _M_deallocate(_M_impl._M_start, |
336 | _M_impl._M_end_of_storage - _M_impl._M_start); |
337 | } |
338 | |
339 | public: |
340 | _Vector_impl _M_impl; |
341 | |
342 | pointer |
343 | _M_allocate(size_t __n) |
344 | { |
345 | typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; |
346 | return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer(); |
347 | } |
348 | |
349 | void |
350 | _M_deallocate(pointer __p, size_t __n) |
351 | { |
352 | typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; |
353 | if (__p) |
354 | _Tr::deallocate(_M_impl, __p, __n); |
355 | } |
356 | |
357 | protected: |
358 | void |
359 | _M_create_storage(size_t __n) |
360 | { |
361 | this->_M_impl._M_start = this->_M_allocate(__n); |
362 | this->_M_impl._M_finish = this->_M_impl._M_start; |
363 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; |
364 | } |
365 | }; |
366 | |
367 | |
368 | |
369 | |
370 | |
371 | |
372 | |
373 | |
374 | |
375 | |
376 | |
377 | |
378 | |
379 | |
380 | |
381 | |
382 | |
383 | |
384 | |
385 | |
386 | |
387 | |
388 | template<typename _Tp, typename _Alloc = std::allocator<_Tp> > |
389 | class vector : protected _Vector_base<_Tp, _Alloc> |
390 | { |
391 | #ifdef _GLIBCXX_CONCEPT_CHECKS |
392 | |
393 | typedef typename _Alloc::value_type _Alloc_value_type; |
394 | # if __cplusplus < 201103L |
395 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |
396 | # endif |
397 | __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) |
398 | #endif |
399 | |
400 | #if __cplusplus >= 201103L |
401 | static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value, |
402 | "std::vector must have a non-const, non-volatile value_type"); |
403 | # if __cplusplus > 201703L || defined __STRICT_ANSI__ |
404 | static_assert(is_same<typename _Alloc::value_type, _Tp>::value, |
405 | "std::vector must have the same value_type as its allocator"); |
406 | # endif |
407 | #endif |
408 | |
409 | typedef _Vector_base<_Tp, _Alloc> _Base; |
410 | typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; |
411 | typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; |
412 | |
413 | public: |
414 | typedef _Tp value_type; |
415 | typedef typename _Base::pointer pointer; |
416 | typedef typename _Alloc_traits::const_pointer const_pointer; |
417 | typedef typename _Alloc_traits::reference reference; |
418 | typedef typename _Alloc_traits::const_reference const_reference; |
419 | typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; |
420 | typedef __gnu_cxx::__normal_iterator<const_pointer, vector> |
421 | const_iterator; |
422 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
423 | typedef std::reverse_iterator<iterator> reverse_iterator; |
424 | typedef size_t size_type; |
425 | typedef ptrdiff_t difference_type; |
426 | typedef _Alloc allocator_type; |
427 | |
428 | private: |
429 | #if __cplusplus >= 201103L |
430 | static constexpr bool |
431 | _S_nothrow_relocate(true_type) |
432 | { |
433 | return noexcept(std::__relocate_a(std::declval<pointer>(), |
434 | std::declval<pointer>(), |
435 | std::declval<pointer>(), |
436 | std::declval<_Tp_alloc_type&>())); |
437 | } |
438 | |
439 | static constexpr bool |
440 | _S_nothrow_relocate(false_type) |
441 | { return false; } |
442 | |
443 | static constexpr bool |
444 | _S_use_relocate() |
445 | { |
446 | |
447 | |
448 | |
449 | return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{}); |
450 | } |
451 | |
452 | static pointer |
453 | _S_do_relocate(pointer __first, pointer __last, pointer __result, |
454 | _Tp_alloc_type& __alloc, true_type) noexcept |
455 | { |
456 | return std::__relocate_a(__first, __last, __result, __alloc); |
457 | } |
458 | |
459 | static pointer |
460 | _S_do_relocate(pointer, pointer, pointer __result, |
461 | _Tp_alloc_type&, false_type) noexcept |
462 | { return __result; } |
463 | |
464 | static pointer |
465 | _S_relocate(pointer __first, pointer __last, pointer __result, |
466 | _Tp_alloc_type& __alloc) noexcept |
467 | { |
468 | using __do_it = __bool_constant<_S_use_relocate()>; |
469 | return _S_do_relocate(__first, __last, __result, __alloc, __do_it{}); |
470 | } |
471 | #endif // C++11 |
472 | |
473 | protected: |
474 | using _Base::_M_allocate; |
475 | using _Base::_M_deallocate; |
476 | using _Base::_M_impl; |
477 | using _Base::_M_get_Tp_allocator; |
478 | |
479 | public: |
480 | |
481 | |
482 | |
483 | |
484 | |
485 | |
486 | #if __cplusplus >= 201103L |
487 | vector() = default; |
488 | #else |
489 | vector() { } |
490 | #endif |
491 | |
492 | |
493 | |
494 | |
495 | |
496 | explicit |
497 | vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT |
498 | : _Base(__a) { } |
499 | |
500 | #if __cplusplus >= 201103L |
501 | |
502 | |
503 | |
504 | |
505 | |
506 | |
507 | |
508 | |
509 | explicit |
510 | vector(size_type __n, const allocator_type& __a = allocator_type()) |
511 | : _Base(_S_check_init_len(__n, __a), __a) |
512 | { _M_default_initialize(__n); } |
513 | |
514 | |
515 | |
516 | |
517 | |
518 | |
519 | |
520 | |
521 | |
522 | vector(size_type __n, const value_type& __value, |
523 | const allocator_type& __a = allocator_type()) |
524 | : _Base(_S_check_init_len(__n, __a), __a) |
525 | { _M_fill_initialize(__n, __value); } |
526 | #else |
527 | |
528 | |
529 | |
530 | |
531 | |
532 | |
533 | |
534 | |
535 | explicit |
536 | vector(size_type __n, const value_type& __value = value_type(), |
537 | const allocator_type& __a = allocator_type()) |
538 | : _Base(_S_check_init_len(__n, __a), __a) |
539 | { _M_fill_initialize(__n, __value); } |
540 | #endif |
541 | |
542 | |
543 | |
544 | |
545 | |
546 | |
547 | |
548 | |
549 | |
550 | |
551 | |
552 | |
553 | vector(const vector& __x) |
554 | : _Base(__x.size(), |
555 | _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) |
556 | { |
557 | this->_M_impl._M_finish = |
558 | std::__uninitialized_copy_a(__x.begin(), __x.end(), |
559 | this->_M_impl._M_start, |
560 | _M_get_Tp_allocator()); |
561 | } |
562 | |
563 | #if __cplusplus >= 201103L |
564 | |
565 | |
566 | |
567 | |
568 | |
569 | |
570 | |
571 | |
572 | vector(vector&&) noexcept = default; |
573 | |
574 | |
575 | vector(const vector& __x, const allocator_type& __a) |
576 | : _Base(__x.size(), __a) |
577 | { |
578 | this->_M_impl._M_finish = |
579 | std::__uninitialized_copy_a(__x.begin(), __x.end(), |
580 | this->_M_impl._M_start, |
581 | _M_get_Tp_allocator()); |
582 | } |
583 | |
584 | private: |
585 | vector(vector&& __rv, const allocator_type& __m, true_type) noexcept |
586 | : _Base(__m, std::move(__rv)) |
587 | { } |
588 | |
589 | vector(vector&& __rv, const allocator_type& __m, false_type) |
590 | : _Base(__m) |
591 | { |
592 | if (__rv.get_allocator() == __m) |
593 | this->_M_impl._M_swap_data(__rv._M_impl); |
594 | else if (!__rv.empty()) |
595 | { |
596 | this->_M_create_storage(__rv.size()); |
597 | this->_M_impl._M_finish = |
598 | std::__uninitialized_move_a(__rv.begin(), __rv.end(), |
599 | this->_M_impl._M_start, |
600 | _M_get_Tp_allocator()); |
601 | __rv.clear(); |
602 | } |
603 | } |
604 | |
605 | public: |
606 | |
607 | vector(vector&& __rv, const allocator_type& __m) |
608 | noexcept( noexcept( |
609 | vector(std::declval<vector&&>(), std::declval<const allocator_type&>(), |
610 | std::declval<typename _Alloc_traits::is_always_equal>())) ) |
611 | : vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{}) |
612 | { } |
613 | |
614 | |
615 | |
616 | |
617 | |
618 | |
619 | |
620 | |
621 | |
622 | |
623 | |
624 | |
625 | vector(initializer_list<value_type> __l, |
626 | const allocator_type& __a = allocator_type()) |
627 | : _Base(__a) |
628 | { |
629 | _M_range_initialize(__l.begin(), __l.end(), |
630 | random_access_iterator_tag()); |
631 | } |
632 | #endif |
633 | |
634 | |
635 | |
636 | |
637 | |
638 | |
639 | |
640 | |
641 | |
642 | |
643 | |
644 | |
645 | |
646 | |
647 | |
648 | |
649 | |
650 | #if __cplusplus >= 201103L |
651 | template<typename _InputIterator, |
652 | typename = std::_RequireInputIter<_InputIterator>> |
653 | vector(_InputIterator __first, _InputIterator __last, |
654 | const allocator_type& __a = allocator_type()) |
655 | : _Base(__a) |
656 | { |
657 | _M_range_initialize(__first, __last, |
658 | std::__iterator_category(__first)); |
659 | } |
660 | #else |
661 | template<typename _InputIterator> |
662 | vector(_InputIterator __first, _InputIterator __last, |
663 | const allocator_type& __a = allocator_type()) |
664 | : _Base(__a) |
665 | { |
666 | |
667 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
668 | _M_initialize_dispatch(__first, __last, _Integral()); |
669 | } |
670 | #endif |
671 | |
672 | |
673 | |
674 | |
675 | |
676 | |
677 | |
678 | ~vector() _GLIBCXX_NOEXCEPT |
679 | { |
680 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
681 | _M_get_Tp_allocator()); |
682 | _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC; |
683 | } |
684 | |
685 | |
686 | |
687 | |
688 | |
689 | |
690 | |
691 | |
692 | |
693 | |
694 | vector& |
695 | operator=(const vector& __x); |
696 | |
697 | #if __cplusplus >= 201103L |
698 | |
699 | |
700 | |
701 | |
702 | |
703 | |
704 | |
705 | |
706 | |
707 | |
708 | vector& |
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) |
710 | { |
711 | constexpr bool __move_storage = |
712 | _Alloc_traits::_S_propagate_on_move_assign() |
713 | || _Alloc_traits::_S_always_equal(); |
714 | _M_move_assign(std::move(__x), __bool_constant<__move_storage>()); |
715 | return *this; |
716 | } |
717 | |
718 | |
719 | |
720 | |
721 | |
722 | |
723 | |
724 | |
725 | |
726 | |
727 | |
728 | |
729 | vector& |
730 | operator=(initializer_list<value_type> __l) |
731 | { |
732 | this->_M_assign_aux(__l.begin(), __l.end(), |
733 | random_access_iterator_tag()); |
734 | return *this; |
735 | } |
736 | #endif |
737 | |
738 | |
739 | |
740 | |
741 | |
742 | |
743 | |
744 | |
745 | |
746 | |
747 | |
748 | void |
749 | assign(size_type __n, const value_type& __val) |
750 | { _M_fill_assign(__n, __val); } |
751 | |
752 | |
753 | |
754 | |
755 | |
756 | |
757 | |
758 | |
759 | |
760 | |
761 | |
762 | |
763 | |
764 | #if __cplusplus >= 201103L |
765 | template<typename _InputIterator, |
766 | typename = std::_RequireInputIter<_InputIterator>> |
767 | void |
768 | assign(_InputIterator __first, _InputIterator __last) |
769 | { _M_assign_dispatch(__first, __last, __false_type()); } |
770 | #else |
771 | template<typename _InputIterator> |
772 | void |
773 | assign(_InputIterator __first, _InputIterator __last) |
774 | { |
775 | |
776 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
777 | _M_assign_dispatch(__first, __last, _Integral()); |
778 | } |
779 | #endif |
780 | |
781 | #if __cplusplus >= 201103L |
782 | |
783 | |
784 | |
785 | |
786 | |
787 | |
788 | |
789 | |
790 | |
791 | |
792 | |
793 | void |
794 | assign(initializer_list<value_type> __l) |
795 | { |
796 | this->_M_assign_aux(__l.begin(), __l.end(), |
797 | random_access_iterator_tag()); |
798 | } |
799 | #endif |
800 | |
801 | |
802 | using _Base::get_allocator; |
803 | |
804 | |
805 | |
806 | |
807 | |
808 | |
809 | |
810 | iterator |
811 | begin() _GLIBCXX_NOEXCEPT |
812 | { return iterator(this->_M_impl._M_start); } |
813 | |
814 | |
815 | |
816 | |
817 | |
818 | |
819 | const_iterator |
820 | begin() const _GLIBCXX_NOEXCEPT |
821 | { return const_iterator(this->_M_impl._M_start); } |
822 | |
823 | |
824 | |
825 | |
826 | |
827 | |
828 | iterator |
829 | end() _GLIBCXX_NOEXCEPT |
830 | { return iterator(this->_M_impl._M_finish); } |
831 | |
832 | |
833 | |
834 | |
835 | |
836 | |
837 | const_iterator |
838 | end() const _GLIBCXX_NOEXCEPT |
839 | { return const_iterator(this->_M_impl._M_finish); } |
840 | |
841 | |
842 | |
843 | |
844 | |
845 | |
846 | reverse_iterator |
847 | rbegin() _GLIBCXX_NOEXCEPT |
848 | { return reverse_iterator(end()); } |
849 | |
850 | |
851 | |
852 | |
853 | |
854 | |
855 | const_reverse_iterator |
856 | rbegin() const _GLIBCXX_NOEXCEPT |
857 | { return const_reverse_iterator(end()); } |
858 | |
859 | |
860 | |
861 | |
862 | |
863 | |
864 | reverse_iterator |
865 | rend() _GLIBCXX_NOEXCEPT |
866 | { return reverse_iterator(begin()); } |
867 | |
868 | |
869 | |
870 | |
871 | |
872 | |
873 | const_reverse_iterator |
874 | rend() const _GLIBCXX_NOEXCEPT |
875 | { return const_reverse_iterator(begin()); } |
876 | |
877 | #if __cplusplus >= 201103L |
878 | |
879 | |
880 | |
881 | |
882 | |
883 | const_iterator |
884 | cbegin() const noexcept |
885 | { return const_iterator(this->_M_impl._M_start); } |
886 | |
887 | |
888 | |
889 | |
890 | |
891 | |
892 | const_iterator |
893 | cend() const noexcept |
894 | { return const_iterator(this->_M_impl._M_finish); } |
895 | |
896 | |
897 | |
898 | |
899 | |
900 | |
901 | const_reverse_iterator |
902 | crbegin() const noexcept |
903 | { return const_reverse_iterator(end()); } |
904 | |
905 | |
906 | |
907 | |
908 | |
909 | |
910 | const_reverse_iterator |
911 | crend() const noexcept |
912 | { return const_reverse_iterator(begin()); } |
913 | #endif |
914 | |
915 | |
916 | |
917 | size_type |
918 | size() const _GLIBCXX_NOEXCEPT |
919 | { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } |
920 | |
921 | |
922 | size_type |
923 | max_size() const _GLIBCXX_NOEXCEPT |
924 | { return _S_max_size(_M_get_Tp_allocator()); } |
925 | |
926 | #if __cplusplus >= 201103L |
927 | |
928 | |
929 | |
930 | |
931 | |
932 | |
933 | |
934 | |
935 | |
936 | void |
937 | resize(size_type __new_size) |
938 | { |
939 | if (__new_size > size()) |
940 | _M_default_append(__new_size - size()); |
941 | else if (__new_size < size()) |
942 | _M_erase_at_end(this->_M_impl._M_start + __new_size); |
943 | } |
944 | |
945 | |
946 | |
947 | |
948 | |
949 | |
950 | |
951 | |
952 | |
953 | |
954 | |
955 | |
956 | void |
957 | resize(size_type __new_size, const value_type& __x) |
958 | { |
959 | if (__new_size > size()) |
960 | _M_fill_insert(end(), __new_size - size(), __x); |
961 | else if (__new_size < size()) |
962 | _M_erase_at_end(this->_M_impl._M_start + __new_size); |
963 | } |
964 | #else |
965 | |
966 | |
967 | |
968 | |
969 | |
970 | |
971 | |
972 | |
973 | |
974 | |
975 | |
976 | void |
977 | resize(size_type __new_size, value_type __x = value_type()) |
978 | { |
979 | if (__new_size > size()) |
980 | _M_fill_insert(end(), __new_size - size(), __x); |
981 | else if (__new_size < size()) |
982 | _M_erase_at_end(this->_M_impl._M_start + __new_size); |
983 | } |
984 | #endif |
985 | |
986 | #if __cplusplus >= 201103L |
987 | |
988 | void |
989 | shrink_to_fit() |
990 | { _M_shrink_to_fit(); } |
991 | #endif |
992 | |
993 | |
994 | |
995 | |
996 | |
997 | size_type |
998 | capacity() const _GLIBCXX_NOEXCEPT |
999 | { return size_type(this->_M_impl._M_end_of_storage |
1000 | - this->_M_impl._M_start); } |
1001 | |
1002 | |
1003 | |
1004 | |
1005 | |
1006 | _GLIBCXX_NODISCARD bool |
1007 | empty() const _GLIBCXX_NOEXCEPT |
1008 | { return begin() == end(); } |
1009 | |
1010 | |
1011 | |
1012 | |
1013 | |
1014 | |
1015 | |
1016 | |
1017 | |
1018 | |
1019 | |
1020 | |
1021 | |
1022 | |
1023 | |
1024 | |
1025 | |
1026 | |
1027 | void |
1028 | reserve(size_type __n); |
1029 | |
1030 | |
1031 | |
1032 | |
1033 | |
1034 | |
1035 | |
1036 | |
1037 | |
1038 | |
1039 | |
1040 | |
1041 | |
1042 | reference |
1043 | operator[](size_type __n) _GLIBCXX_NOEXCEPT |
1044 | { |
1045 | __glibcxx_requires_subscript(__n); |
1046 | return *(this->_M_impl._M_start + __n); |
1047 | } |
1048 | |
1049 | |
1050 | |
1051 | |
1052 | |
1053 | |
1054 | |
1055 | |
1056 | |
1057 | |
1058 | |
1059 | |
1060 | const_reference |
1061 | operator[](size_type __n) const _GLIBCXX_NOEXCEPT |
1062 | { |
1063 | __glibcxx_requires_subscript(__n); |
1064 | return *(this->_M_impl._M_start + __n); |
1065 | } |
1066 | |
1067 | protected: |
1068 | |
1069 | void |
1070 | _M_range_check(size_type __n) const |
1071 | { |
1072 | if (__n >= this->size()) |
1073 | __throw_out_of_range_fmt(__N("vector::_M_range_check: __n " |
1074 | "(which is %zu) >= this->size() " |
1075 | "(which is %zu)"), |
1076 | __n, this->size()); |
1077 | } |
1078 | |
1079 | public: |
1080 | |
1081 | |
1082 | |
1083 | |
1084 | |
1085 | |
1086 | |
1087 | |
1088 | |
1089 | |
1090 | |
1091 | reference |
1092 | at(size_type __n) |
1093 | { |
1094 | _M_range_check(__n); |
1095 | return (*this)[__n]; |
1096 | } |
1097 | |
1098 | |
1099 | |
1100 | |
1101 | |
1102 | |
1103 | |
1104 | |
1105 | |
1106 | |
1107 | |
1108 | |
1109 | const_reference |
1110 | at(size_type __n) const |
1111 | { |
1112 | _M_range_check(__n); |
1113 | return (*this)[__n]; |
1114 | } |
1115 | |
1116 | |
1117 | |
1118 | |
1119 | |
1120 | reference |
1121 | front() _GLIBCXX_NOEXCEPT |
1122 | { |
1123 | __glibcxx_requires_nonempty(); |
1124 | return *begin(); |
1125 | } |
1126 | |
1127 | |
1128 | |
1129 | |
1130 | |
1131 | const_reference |
1132 | front() const _GLIBCXX_NOEXCEPT |
1133 | { |
1134 | __glibcxx_requires_nonempty(); |
1135 | return *begin(); |
1136 | } |
1137 | |
1138 | |
1139 | |
1140 | |
1141 | |
1142 | reference |
1143 | back() _GLIBCXX_NOEXCEPT |
1144 | { |
1145 | __glibcxx_requires_nonempty(); |
1146 | return *(end() - 1); |
1147 | } |
1148 | |
1149 | |
1150 | |
1151 | |
1152 | |
1153 | const_reference |
1154 | back() const _GLIBCXX_NOEXCEPT |
1155 | { |
1156 | __glibcxx_requires_nonempty(); |
1157 | return *(end() - 1); |
1158 | } |
1159 | |
1160 | |
1161 | |
1162 | |
1163 | |
1164 | |
1165 | |
1166 | |
1167 | _Tp* |
1168 | data() _GLIBCXX_NOEXCEPT |
1169 | { return _M_data_ptr(this->_M_impl._M_start); } |
1170 | |
1171 | const _Tp* |
1172 | data() const _GLIBCXX_NOEXCEPT |
1173 | { return _M_data_ptr(this->_M_impl._M_start); } |
1174 | |
1175 | |
1176 | |
1177 | |
1178 | |
1179 | |
1180 | |
1181 | |
1182 | |
1183 | |
1184 | |
1185 | |
1186 | void |
1187 | push_back(const value_type& __x) |
1188 | { |
1189 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
1190 | { |
1191 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
1192 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
1193 | __x); |
1194 | ++this->_M_impl._M_finish; |
1195 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
1196 | } |
1197 | else |
1198 | _M_realloc_insert(end(), __x); |
1199 | } |
1200 | |
1201 | #if __cplusplus >= 201103L |
1202 | void |
1203 | push_back(value_type&& __x) |
1204 | { emplace_back(std::move(__x)); } |
1205 | |
1206 | template<typename... _Args> |
1207 | #if __cplusplus > 201402L |
1208 | reference |
1209 | #else |
1210 | void |
1211 | #endif |
1212 | emplace_back(_Args&&... __args); |
1213 | #endif |
1214 | |
1215 | |
1216 | |
1217 | |
1218 | |
1219 | |
1220 | |
1221 | |
1222 | |
1223 | |
1224 | void |
1225 | pop_back() _GLIBCXX_NOEXCEPT |
1226 | { |
1227 | __glibcxx_requires_nonempty(); |
1228 | --this->_M_impl._M_finish; |
1229 | _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); |
1230 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); |
1231 | } |
1232 | |
1233 | #if __cplusplus >= 201103L |
1234 | |
1235 | |
1236 | |
1237 | |
1238 | |
1239 | |
1240 | |
1241 | |
1242 | |
1243 | |
1244 | |
1245 | |
1246 | template<typename... _Args> |
1247 | iterator |
1248 | emplace(const_iterator __position, _Args&&... __args) |
1249 | { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); } |
1250 | |
1251 | |
1252 | |
1253 | |
1254 | |
1255 | |
1256 | |
1257 | |
1258 | |
1259 | |
1260 | |
1261 | |
1262 | iterator |
1263 | insert(const_iterator __position, const value_type& __x); |
1264 | #else |
1265 | |
1266 | |
1267 | |
1268 | |
1269 | |
1270 | |
1271 | |
1272 | |
1273 | |
1274 | |
1275 | |
1276 | iterator |
1277 | insert(iterator __position, const value_type& __x); |
1278 | #endif |
1279 | |
1280 | #if __cplusplus >= 201103L |
1281 | |
1282 | |
1283 | |
1284 | |
1285 | |
1286 | |
1287 | |
1288 | |
1289 | |
1290 | |
1291 | |
1292 | iterator |
1293 | insert(const_iterator __position, value_type&& __x) |
1294 | { return _M_insert_rval(__position, std::move(__x)); } |
1295 | |
1296 | |
1297 | |
1298 | |
1299 | |
1300 | |
1301 | |
1302 | |
1303 | |
1304 | |
1305 | |
1306 | |
1307 | |
1308 | |
1309 | iterator |
1310 | insert(const_iterator __position, initializer_list<value_type> __l) |
1311 | { |
1312 | auto __offset = __position - cbegin(); |
1313 | _M_range_insert(begin() + __offset, __l.begin(), __l.end(), |
1314 | std::random_access_iterator_tag()); |
1315 | return begin() + __offset; |
1316 | } |
1317 | #endif |
1318 | |
1319 | #if __cplusplus >= 201103L |
1320 | |
1321 | |
1322 | |
1323 | |
1324 | |
1325 | |
1326 | |
1327 | |
1328 | |
1329 | |
1330 | |
1331 | |
1332 | |
1333 | |
1334 | iterator |
1335 | insert(const_iterator __position, size_type __n, const value_type& __x) |
1336 | { |
1337 | difference_type __offset = __position - cbegin(); |
1338 | _M_fill_insert(begin() + __offset, __n, __x); |
1339 | return begin() + __offset; |
1340 | } |
1341 | #else |
1342 | |
1343 | |
1344 | |
1345 | |
1346 | |
1347 | |
1348 | |
1349 | |
1350 | |
1351 | |
1352 | |
1353 | |
1354 | |
1355 | void |
1356 | insert(iterator __position, size_type __n, const value_type& __x) |
1357 | { _M_fill_insert(__position, __n, __x); } |
1358 | #endif |
1359 | |
1360 | #if __cplusplus >= 201103L |
1361 | |
1362 | |
1363 | |
1364 | |
1365 | |
1366 | |
1367 | |
1368 | |
1369 | |
1370 | |
1371 | |
1372 | |
1373 | |
1374 | |
1375 | |
1376 | template<typename _InputIterator, |
1377 | typename = std::_RequireInputIter<_InputIterator>> |
1378 | iterator |
1379 | insert(const_iterator __position, _InputIterator __first, |
1380 | _InputIterator __last) |
1381 | { |
1382 | difference_type __offset = __position - cbegin(); |
1383 | _M_insert_dispatch(begin() + __offset, |
1384 | __first, __last, __false_type()); |
1385 | return begin() + __offset; |
1386 | } |
1387 | #else |
1388 | |
1389 | |
1390 | |
1391 | |
1392 | |
1393 | |
1394 | |
1395 | |
1396 | |
1397 | |
1398 | |
1399 | |
1400 | |
1401 | |
1402 | template<typename _InputIterator> |
1403 | void |
1404 | insert(iterator __position, _InputIterator __first, |
1405 | _InputIterator __last) |
1406 | { |
1407 | |
1408 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
1409 | _M_insert_dispatch(__position, __first, __last, _Integral()); |
1410 | } |
1411 | #endif |
1412 | |
1413 | |
1414 | |
1415 | |
1416 | |
1417 | |
1418 | |
1419 | |
1420 | |
1421 | |
1422 | |
1423 | |
1424 | |
1425 | |
1426 | |
1427 | |
1428 | iterator |
1429 | #if __cplusplus >= 201103L |
1430 | erase(const_iterator __position) |
1431 | { return _M_erase(begin() + (__position - cbegin())); } |
1432 | #else |
1433 | erase(iterator __position) |
1434 | { return _M_erase(__position); } |
1435 | #endif |
1436 | |
1437 | |
1438 | |
1439 | |
1440 | |
1441 | |
1442 | |
1443 | |
1444 | |
1445 | |
1446 | |
1447 | |
1448 | |
1449 | |
1450 | |
1451 | |
1452 | |
1453 | |
1454 | |
1455 | iterator |
1456 | #if __cplusplus >= 201103L |
1457 | erase(const_iterator __first, const_iterator __last) |
1458 | { |
1459 | const auto __beg = begin(); |
1460 | const auto __cbeg = cbegin(); |
1461 | return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg)); |
1462 | } |
1463 | #else |
1464 | erase(iterator __first, iterator __last) |
1465 | { return _M_erase(__first, __last); } |
1466 | #endif |
1467 | |
1468 | |
1469 | |
1470 | |
1471 | |
1472 | |
1473 | |
1474 | |
1475 | |
1476 | |
1477 | |
1478 | |
1479 | void |
1480 | swap(vector& __x) _GLIBCXX_NOEXCEPT |
1481 | { |
1482 | #if __cplusplus >= 201103L |
1483 | __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value |
1484 | || _M_get_Tp_allocator() == __x._M_get_Tp_allocator()); |
1485 | #endif |
1486 | this->_M_impl._M_swap_data(__x._M_impl); |
1487 | _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), |
1488 | __x._M_get_Tp_allocator()); |
1489 | } |
1490 | |
1491 | |
1492 | |
1493 | |
1494 | |
1495 | |
1496 | |
1497 | void |
1498 | clear() _GLIBCXX_NOEXCEPT |
1499 | { _M_erase_at_end(this->_M_impl._M_start); } |
1500 | |
1501 | protected: |
1502 | |
1503 | |
1504 | |
1505 | |
1506 | template<typename _ForwardIterator> |
1507 | pointer |
1508 | _M_allocate_and_copy(size_type __n, |
1509 | _ForwardIterator __first, _ForwardIterator __last) |
1510 | { |
1511 | pointer __result = this->_M_allocate(__n); |
1512 | __try |
1513 | { |
1514 | std::__uninitialized_copy_a(__first, __last, __result, |
1515 | _M_get_Tp_allocator()); |
1516 | return __result; |
1517 | } |
1518 | __catch(...) |
1519 | { |
1520 | _M_deallocate(__result, __n); |
1521 | __throw_exception_again; |
1522 | } |
1523 | } |
1524 | |
1525 | |
1526 | |
1527 | |
1528 | |
1529 | |
1530 | #if __cplusplus < 201103L |
1531 | |
1532 | |
1533 | template<typename _Integer> |
1534 | void |
1535 | _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) |
1536 | { |
1537 | this->_M_impl._M_start = _M_allocate(_S_check_init_len( |
1538 | static_cast<size_type>(__n), _M_get_Tp_allocator())); |
1539 | this->_M_impl._M_end_of_storage = |
1540 | this->_M_impl._M_start + static_cast<size_type>(__n); |
1541 | _M_fill_initialize(static_cast<size_type>(__n), __value); |
1542 | } |
1543 | |
1544 | |
1545 | template<typename _InputIterator> |
1546 | void |
1547 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |
1548 | __false_type) |
1549 | { |
1550 | _M_range_initialize(__first, __last, |
1551 | std::__iterator_category(__first)); |
1552 | } |
1553 | #endif |
1554 | |
1555 | |
1556 | template<typename _InputIterator> |
1557 | void |
1558 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |
1559 | std::input_iterator_tag) |
1560 | { |
1561 | __try { |
1562 | for (; __first != __last; ++__first) |
1563 | #if __cplusplus >= 201103L |
1564 | emplace_back(*__first); |
1565 | #else |
1566 | push_back(*__first); |
1567 | #endif |
1568 | } __catch(...) { |
1569 | clear(); |
1570 | __throw_exception_again; |
1571 | } |
1572 | } |
1573 | |
1574 | |
1575 | template<typename _ForwardIterator> |
1576 | void |
1577 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |
1578 | std::forward_iterator_tag) |
1579 | { |
1580 | const size_type __n = std::distance(__first, __last); |
1581 | this->_M_impl._M_start |
1582 | = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator())); |
1583 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; |
1584 | this->_M_impl._M_finish = |
1585 | std::__uninitialized_copy_a(__first, __last, |
1586 | this->_M_impl._M_start, |
1587 | _M_get_Tp_allocator()); |
1588 | } |
1589 | |
1590 | |
1591 | |
1592 | void |
1593 | _M_fill_initialize(size_type __n, const value_type& __value) |
1594 | { |
1595 | this->_M_impl._M_finish = |
1596 | std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, |
1597 | _M_get_Tp_allocator()); |
1598 | } |
1599 | |
1600 | #if __cplusplus >= 201103L |
1601 | |
1602 | void |
1603 | _M_default_initialize(size_type __n) |
1604 | { |
1605 | this->_M_impl._M_finish = |
1606 | std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, |
1607 | _M_get_Tp_allocator()); |
1608 | } |
1609 | #endif |
1610 | |
1611 | |
1612 | |
1613 | |
1614 | |
1615 | |
1616 | |
1617 | |
1618 | template<typename _Integer> |
1619 | void |
1620 | _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) |
1621 | { _M_fill_assign(__n, __val); } |
1622 | |
1623 | |
1624 | template<typename _InputIterator> |
1625 | void |
1626 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, |
1627 | __false_type) |
1628 | { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } |
1629 | |
1630 | |
1631 | template<typename _InputIterator> |
1632 | void |
1633 | _M_assign_aux(_InputIterator __first, _InputIterator __last, |
1634 | std::input_iterator_tag); |
1635 | |
1636 | |
1637 | template<typename _ForwardIterator> |
1638 | void |
1639 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |
1640 | std::forward_iterator_tag); |
1641 | |
1642 | |
1643 | |
1644 | void |
1645 | _M_fill_assign(size_type __n, const value_type& __val); |
1646 | |
1647 | |
1648 | |
1649 | |
1650 | |
1651 | |
1652 | |
1653 | template<typename _Integer> |
1654 | void |
1655 | _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, |
1656 | __true_type) |
1657 | { _M_fill_insert(__pos, __n, __val); } |
1658 | |
1659 | |
1660 | template<typename _InputIterator> |
1661 | void |
1662 | _M_insert_dispatch(iterator __pos, _InputIterator __first, |
1663 | _InputIterator __last, __false_type) |
1664 | { |
1665 | _M_range_insert(__pos, __first, __last, |
1666 | std::__iterator_category(__first)); |
1667 | } |
1668 | |
1669 | |
1670 | template<typename _InputIterator> |
1671 | void |
1672 | _M_range_insert(iterator __pos, _InputIterator __first, |
1673 | _InputIterator __last, std::input_iterator_tag); |
1674 | |
1675 | |
1676 | template<typename _ForwardIterator> |
1677 | void |
1678 | _M_range_insert(iterator __pos, _ForwardIterator __first, |
1679 | _ForwardIterator __last, std::forward_iterator_tag); |
1680 | |
1681 | |
1682 | |
1683 | void |
1684 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); |
1685 | |
1686 | #if __cplusplus >= 201103L |
1687 | |
1688 | void |
1689 | _M_default_append(size_type __n); |
1690 | |
1691 | bool |
1692 | _M_shrink_to_fit(); |
1693 | #endif |
1694 | |
1695 | #if __cplusplus < 201103L |
1696 | |
1697 | void |
1698 | _M_insert_aux(iterator __position, const value_type& __x); |
1699 | |
1700 | void |
1701 | _M_realloc_insert(iterator __position, const value_type& __x); |
1702 | #else |
1703 | |
1704 | |
1705 | struct _Temporary_value |
1706 | { |
1707 | template<typename... _Args> |
1708 | explicit |
1709 | _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec) |
1710 | { |
1711 | _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(), |
1712 | std::forward<_Args>(__args)...); |
1713 | } |
1714 | |
1715 | ~_Temporary_value() |
1716 | { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); } |
1717 | |
1718 | value_type& |
1719 | _M_val() { return *_M_ptr(); } |
1720 | |
1721 | private: |
1722 | _Tp* |
1723 | _M_ptr() { return reinterpret_cast<_Tp*>(&__buf); } |
1724 | |
1725 | vector* _M_this; |
1726 | typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf; |
1727 | }; |
1728 | |
1729 | |
1730 | |
1731 | template<typename _Arg> |
1732 | void |
1733 | _M_insert_aux(iterator __position, _Arg&& __arg); |
1734 | |
1735 | template<typename... _Args> |
1736 | void |
1737 | _M_realloc_insert(iterator __position, _Args&&... __args); |
1738 | |
1739 | |
1740 | iterator |
1741 | _M_insert_rval(const_iterator __position, value_type&& __v); |
1742 | |
1743 | |
1744 | template<typename... _Args> |
1745 | iterator |
1746 | _M_emplace_aux(const_iterator __position, _Args&&... __args); |
1747 | |
1748 | |
1749 | iterator |
1750 | _M_emplace_aux(const_iterator __position, value_type&& __v) |
1751 | { return _M_insert_rval(__position, std::move(__v)); } |
1752 | #endif |
1753 | |
1754 | |
1755 | size_type |
1756 | _M_check_len(size_type __n, const char* __s) const |
1757 | { |
1758 | if (max_size() - size() < __n) |
1759 | __throw_length_error(__N(__s)); |
1760 | |
1761 | const size_type __len = size() + (std::max)(size(), __n); |
1762 | return (__len < size() || __len > max_size()) ? max_size() : __len; |
1763 | } |
1764 | |
1765 | |
1766 | static size_type |
1767 | _S_check_init_len(size_type __n, const allocator_type& __a) |
1768 | { |
1769 | if (__n > _S_max_size(_Tp_alloc_type(__a))) |
1770 | __throw_length_error( |
1771 | __N("cannot create std::vector larger than max_size()")); |
1772 | return __n; |
1773 | } |
1774 | |
1775 | static size_type |
1776 | _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT |
1777 | { |
1778 | |
1779 | |
1780 | |
1781 | const size_t __diffmax |
1782 | = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp); |
1783 | const size_t __allocmax = _Alloc_traits::max_size(__a); |
1784 | return (std::min)(__diffmax, __allocmax); |
1785 | } |
1786 | |
1787 | |
1788 | |
1789 | |
1790 | |
1791 | void |
1792 | _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT |
1793 | { |
1794 | if (size_type __n = this->_M_impl._M_finish - __pos) |
1795 | { |
1796 | std::_Destroy(__pos, this->_M_impl._M_finish, |
1797 | _M_get_Tp_allocator()); |
1798 | this->_M_impl._M_finish = __pos; |
1799 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n); |
1800 | } |
1801 | } |
1802 | |
1803 | iterator |
1804 | _M_erase(iterator __position); |
1805 | |
1806 | iterator |
1807 | _M_erase(iterator __first, iterator __last); |
1808 | |
1809 | #if __cplusplus >= 201103L |
1810 | private: |
1811 | |
1812 | |
1813 | |
1814 | void |
1815 | _M_move_assign(vector&& __x, true_type) noexcept |
1816 | { |
1817 | vector __tmp(get_allocator()); |
1818 | this->_M_impl._M_swap_data(__x._M_impl); |
1819 | __tmp._M_impl._M_swap_data(__x._M_impl); |
1820 | std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); |
1821 | } |
1822 | |
1823 | |
1824 | |
1825 | void |
1826 | _M_move_assign(vector&& __x, false_type) |
1827 | { |
1828 | if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator()) |
1829 | _M_move_assign(std::move(__x), true_type()); |
1830 | else |
1831 | { |
1832 | |
1833 | |
1834 | this->_M_assign_aux(std::make_move_iterator(__x.begin()), |
1835 | std::make_move_iterator(__x.end()), |
1836 | std::random_access_iterator_tag()); |
1837 | __x.clear(); |
1838 | } |
1839 | } |
1840 | #endif |
1841 | |
1842 | template<typename _Up> |
1843 | _Up* |
1844 | _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT |
1845 | { return __ptr; } |
1846 | |
1847 | #if __cplusplus >= 201103L |
1848 | template<typename _Ptr> |
1849 | typename std::pointer_traits<_Ptr>::element_type* |
1850 | _M_data_ptr(_Ptr __ptr) const |
1851 | { return empty() ? nullptr : std::__to_address(__ptr); } |
1852 | #else |
1853 | template<typename _Up> |
1854 | _Up* |
1855 | _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT |
1856 | { return __ptr; } |
1857 | |
1858 | template<typename _Ptr> |
1859 | value_type* |
1860 | _M_data_ptr(_Ptr __ptr) |
1861 | { return empty() ? (value_type*)0 : __ptr.operator->(); } |
1862 | |
1863 | template<typename _Ptr> |
1864 | const value_type* |
1865 | _M_data_ptr(_Ptr __ptr) const |
1866 | { return empty() ? (const value_type*)0 : __ptr.operator->(); } |
1867 | #endif |
1868 | }; |
1869 | |
1870 | #if __cpp_deduction_guides >= 201606 |
1871 | template<typename _InputIterator, typename _ValT |
1872 | = typename iterator_traits<_InputIterator>::value_type, |
1873 | typename _Allocator = allocator<_ValT>, |
1874 | typename = _RequireInputIter<_InputIterator>, |
1875 | typename = _RequireAllocator<_Allocator>> |
1876 | vector(_InputIterator, _InputIterator, _Allocator = _Allocator()) |
1877 | -> vector<_ValT, _Allocator>; |
1878 | #endif |
1879 | |
1880 | |
1881 | |
1882 | |
1883 | |
1884 | |
1885 | |
1886 | |
1887 | |
1888 | |
1889 | |
1890 | template<typename _Tp, typename _Alloc> |
1891 | inline bool |
1892 | operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |
1893 | { return (__x.size() == __y.size() |
1894 | && std::equal(__x.begin(), __x.end(), __y.begin())); } |
1895 | |
1896 | #if __cpp_lib_three_way_comparison |
1897 | |
1898 | |
1899 | |
1900 | |
1901 | |
1902 | |
1903 | |
1904 | |
1905 | |
1906 | |
1907 | |
1908 | template<typename _Tp, typename _Alloc> |
1909 | inline __detail::__synth3way_t<_Tp> |
1910 | operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |
1911 | { |
1912 | return std::lexicographical_compare_three_way(__x.begin(), __x.end(), |
1913 | __y.begin(), __y.end(), |
1914 | __detail::__synth3way); |
1915 | } |
1916 | #else |
1917 | |
1918 | |
1919 | |
1920 | |
1921 | |
1922 | |
1923 | |
1924 | |
1925 | |
1926 | |
1927 | |
1928 | template<typename _Tp, typename _Alloc> |
1929 | inline bool |
1930 | operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |
1931 | { return std::lexicographical_compare(__x.begin(), __x.end(), |
1932 | __y.begin(), __y.end()); } |
1933 | |
1934 | |
1935 | template<typename _Tp, typename _Alloc> |
1936 | inline bool |
1937 | operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |
1938 | { return !(__x == __y); } |
1939 | |
1940 | |
1941 | template<typename _Tp, typename _Alloc> |
1942 | inline bool |
1943 | operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |
1944 | { return __y < __x; } |
1945 | |
1946 | |
1947 | template<typename _Tp, typename _Alloc> |
1948 | inline bool |
1949 | operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |
1950 | { return !(__y < __x); } |
1951 | |
1952 | |
1953 | template<typename _Tp, typename _Alloc> |
1954 | inline bool |
1955 | operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |
1956 | { return !(__x < __y); } |
1957 | #endif // three-way comparison |
1958 | |
1959 | |
1960 | template<typename _Tp, typename _Alloc> |
1961 | inline void |
1962 | swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) |
1963 | _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) |
1964 | { __x.swap(__y); } |
1965 | |
1966 | _GLIBCXX_END_NAMESPACE_CONTAINER |
1967 | |
1968 | #if __cplusplus >= 201703L |
1969 | namespace __detail::__variant |
1970 | { |
1971 | template<typename> struct _Never_valueless_alt; |
1972 | |
1973 | |
1974 | |
1975 | template<typename _Tp, typename _Alloc> |
1976 | struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> |
1977 | : std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> |
1978 | { }; |
1979 | } |
1980 | #endif // C++17 |
1981 | |
1982 | _GLIBCXX_END_NAMESPACE_VERSION |
1983 | } |
1984 | |
1985 | #endif /* _STL_VECTOR_H */ |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | #ifndef LLVM_MC_MCREGISTERINFO_H |
16 | #define LLVM_MC_MCREGISTERINFO_H |
17 | |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/ADT/iterator.h" |
20 | #include "llvm/ADT/iterator_range.h" |
21 | #include "llvm/MC/LaneBitmask.h" |
22 | #include "llvm/MC/MCRegister.h" |
23 | #include <cassert> |
24 | #include <cstdint> |
25 | #include <iterator> |
26 | #include <utility> |
27 | |
28 | namespace llvm { |
29 | |
30 | |
31 | class MCRegisterClass { |
32 | public: |
33 | using iterator = const MCPhysReg*; |
34 | using const_iterator = const MCPhysReg*; |
35 | |
36 | const iterator RegsBegin; |
37 | const uint8_t *const RegSet; |
38 | const uint32_t NameIdx; |
39 | const uint16_t RegsSize; |
40 | const uint16_t RegSetSize; |
41 | const uint16_t ID; |
42 | const uint16_t RegSizeInBits; |
43 | const int8_t CopyCost; |
44 | const bool Allocatable; |
45 | |
46 | |
47 | |
48 | unsigned getID() const { return ID; } |
49 | |
50 | |
51 | |
52 | iterator begin() const { return RegsBegin; } |
53 | iterator end() const { return RegsBegin + RegsSize; } |
54 | |
55 | |
56 | |
57 | unsigned getNumRegs() const { return RegsSize; } |
58 | |
59 | |
60 | |
61 | unsigned getRegister(unsigned i) const { |
62 | assert(i < getNumRegs() && "Register number out of range!"); |
63 | return RegsBegin[i]; |
64 | } |
65 | |
66 | |
67 | |
68 | bool contains(MCRegister Reg) const { |
69 | unsigned RegNo = unsigned(Reg); |
70 | unsigned InByte = RegNo % 8; |
71 | unsigned Byte = RegNo / 8; |
72 | if (Byte >= RegSetSize) |
73 | return false; |
74 | return (RegSet[Byte] & (1 << InByte)) != 0; |
75 | } |
76 | |
77 | |
78 | bool contains(MCRegister Reg1, MCRegister Reg2) const { |
79 | return contains(Reg1) && contains(Reg2); |
80 | } |
81 | |
82 | |
83 | |
84 | |
85 | |
86 | unsigned getSizeInBits() const { return RegSizeInBits; } |
87 | |
88 | |
89 | |
90 | |
91 | int getCopyCost() const { return CopyCost; } |
92 | |
93 | |
94 | |
95 | bool isAllocatable() const { return Allocatable; } |
96 | }; |
97 | |
98 | |
99 | |
100 | |
101 | |
102 | |
103 | |
104 | |
105 | struct MCRegisterDesc { |
106 | uint32_t Name; |
107 | uint32_t SubRegs; |
108 | uint32_t SuperRegs; |
109 | |
110 | |
111 | |
112 | uint32_t SubRegIndices; |
113 | |
114 | |
115 | |
116 | uint32_t RegUnits; |
117 | |
118 | |
119 | |
120 | uint16_t RegUnitLaneMasks; |
121 | }; |
122 | |
123 | |
124 | |
125 | |
126 | |
127 | |
128 | |
129 | |
130 | |
131 | |
132 | |
133 | |
134 | |
135 | class MCRegisterInfo { |
136 | public: |
137 | using regclass_iterator = const MCRegisterClass *; |
138 | |
139 | |
140 | |
141 | struct DwarfLLVMRegPair { |
142 | unsigned FromReg; |
143 | unsigned ToReg; |
144 | |
145 | bool operator<(DwarfLLVMRegPair RHS) const { return FromReg < RHS.FromReg; } |
146 | }; |
147 | |
148 | |
149 | |
150 | struct SubRegCoveredBits { |
151 | uint16_t Offset; |
152 | uint16_t Size; |
153 | }; |
154 | |
155 | private: |
156 | const MCRegisterDesc *Desc; |
157 | unsigned NumRegs; |
158 | MCRegister RAReg; |
159 | MCRegister PCReg; |
160 | const MCRegisterClass *Classes; |
161 | unsigned NumClasses; |
162 | unsigned NumRegUnits; |
163 | const MCPhysReg (*RegUnitRoots)[2]; |
164 | const MCPhysReg *DiffLists; |
165 | const LaneBitmask *RegUnitMaskSequences; |
166 | |
167 | const char *RegStrings; |
168 | const char *RegClassStrings; |
169 | const uint16_t *SubRegIndices; |
170 | |
171 | const SubRegCoveredBits *SubRegIdxRanges; |
172 | |
173 | unsigned NumSubRegIndices; |
174 | const uint16_t *RegEncodingTable; |
175 | |
176 | |
177 | unsigned L2DwarfRegsSize; |
178 | unsigned EHL2DwarfRegsSize; |
179 | unsigned Dwarf2LRegsSize; |
180 | unsigned EHDwarf2LRegsSize; |
181 | const DwarfLLVMRegPair *L2DwarfRegs; |
182 | const DwarfLLVMRegPair *EHL2DwarfRegs; |
183 | const DwarfLLVMRegPair *Dwarf2LRegs; |
184 | const DwarfLLVMRegPair *EHDwarf2LRegs; |
185 | DenseMap<MCRegister, int> L2SEHRegs; |
186 | DenseMap<MCRegister, int> L2CVRegs; |
187 | |
188 | public: |
189 | |
190 | template <class SubT> class mc_difflist_iterator; |
191 | |
192 | |
193 | |
194 | |
195 | |
196 | class DiffListIterator { |
197 | uint16_t Val = 0; |
198 | const MCPhysReg *List = nullptr; |
199 | |
200 | protected: |
201 | |
202 | DiffListIterator() = default; |
203 | |
204 | |
205 | |
206 | |
207 | void init(MCPhysReg InitVal, const MCPhysReg *DiffList) { |
208 | Val = InitVal; |
209 | List = DiffList; |
210 | } |
211 | |
212 | |
213 | |
214 | |
215 | MCRegister advance() { |
216 | assert(isValid() && "Cannot move off the end of the list."); |
217 | MCPhysReg D = *List++; |
| 40 | | Dereference of null pointer |
|
218 | Val += D; |
219 | return D; |
220 | } |
221 | |
222 | public: |
223 | |
224 | bool isValid() const { return List; } |
225 | |
226 | |
227 | MCRegister operator*() const { return Val; } |
228 | |
229 | |
230 | void operator++() { |
231 | |
232 | if (!advance()) |
| 39 | | Calling 'DiffListIterator::advance' | |
|
233 | List = nullptr; |
234 | } |
235 | |
236 | template <class SubT> friend class MCRegisterInfo::mc_difflist_iterator; |
237 | }; |
238 | |
239 | |
240 | template <class SubT> |
241 | class mc_difflist_iterator |
242 | : public iterator_facade_base<mc_difflist_iterator<SubT>, |
243 | std::forward_iterator_tag, MCPhysReg> { |
244 | MCRegisterInfo::DiffListIterator Iter; |
245 | |
246 | MCPhysReg Val; |
247 | |
248 | protected: |
249 | mc_difflist_iterator(MCRegisterInfo::DiffListIterator Iter) : Iter(Iter) {} |
250 | |
251 | |
252 | mc_difflist_iterator(MCRegister Reg, const MCPhysReg *DiffList) { |
253 | Iter.init(Reg, DiffList); |
254 | Val = *Iter; |
255 | } |
256 | |
257 | public: |
258 | |
259 | |
260 | mc_difflist_iterator() = default; |
261 | |
262 | |
263 | static SubT end() { |
264 | SubT End; |
265 | End.Iter.List = nullptr; |
266 | return End; |
267 | } |
268 | |
269 | bool operator==(const mc_difflist_iterator &Arg) const { |
270 | return Iter.List == Arg.Iter.List; |
271 | } |
272 | |
273 | const MCPhysReg &operator*() const { return Val; } |
274 | |
275 | using mc_difflist_iterator::iterator_facade_base::operator++; |
276 | void operator++() { |
277 | assert(Iter.List && "Cannot increment the end iterator!"); |
278 | ++Iter; |
279 | Val = *Iter; |
280 | } |
281 | }; |
282 | |
283 | |
284 | |
285 | class mc_subreg_iterator : public mc_difflist_iterator<mc_subreg_iterator> { |
286 | public: |
287 | mc_subreg_iterator(MCRegisterInfo::DiffListIterator Iter) |
288 | : mc_difflist_iterator(Iter) {} |
289 | mc_subreg_iterator() = default; |
290 | mc_subreg_iterator(MCRegister Reg, const MCRegisterInfo *MCRI) |
291 | : mc_difflist_iterator(Reg, MCRI->DiffLists + MCRI->get(Reg).SubRegs) {} |
292 | }; |
293 | |
294 | |
295 | |
296 | class mc_superreg_iterator |
297 | : public mc_difflist_iterator<mc_superreg_iterator> { |
298 | public: |
299 | mc_superreg_iterator(MCRegisterInfo::DiffListIterator Iter) |
300 | : mc_difflist_iterator(Iter) {} |
301 | mc_superreg_iterator() = default; |
302 | mc_superreg_iterator(MCRegister Reg, const MCRegisterInfo *MCRI) |
303 | : mc_difflist_iterator(Reg, |
304 | MCRI->DiffLists + MCRI->get(Reg).SuperRegs) {} |
305 | }; |
306 | |
307 | |
308 | |
309 | iterator_range<mc_subreg_iterator> subregs(MCRegister Reg) const { |
310 | return make_range(std::next(mc_subreg_iterator(Reg, this)), |
311 | mc_subreg_iterator::end()); |
312 | } |
313 | |
314 | |
315 | |
316 | iterator_range<mc_subreg_iterator> subregs_inclusive(MCRegister Reg) const { |
317 | return make_range({Reg, this}, mc_subreg_iterator::end()); |
318 | } |
319 | |
320 | |
321 | |
322 | iterator_range<mc_superreg_iterator> superregs(MCRegister Reg) const { |
323 | return make_range(std::next(mc_superreg_iterator(Reg, this)), |
324 | mc_superreg_iterator::end()); |
325 | } |
326 | |
327 | |
328 | |
329 | iterator_range<mc_superreg_iterator> |
330 | superregs_inclusive(MCRegister Reg) const { |
331 | return make_range({Reg, this}, mc_superreg_iterator::end()); |
332 | } |
333 | |
334 | |
335 | |
336 | detail::concat_range<const MCPhysReg, iterator_range<mc_subreg_iterator>, |
337 | iterator_range<mc_superreg_iterator>> |
338 | sub_and_superregs_inclusive(MCRegister Reg) const { |
339 | return concat<const MCPhysReg>(subregs_inclusive(Reg), superregs(Reg)); |
340 | } |
341 | |
342 | |
343 | |
344 | friend class MCSubRegIterator; |
345 | friend class MCSubRegIndexIterator; |
346 | friend class MCSuperRegIterator; |
347 | friend class MCRegUnitIterator; |
348 | friend class MCRegUnitMaskIterator; |
349 | friend class MCRegUnitRootIterator; |
350 | |
351 | |
352 | |
353 | void InitMCRegisterInfo(const MCRegisterDesc *D, unsigned NR, unsigned RA, |
354 | unsigned PC, |
355 | const MCRegisterClass *C, unsigned NC, |
356 | const MCPhysReg (*RURoots)[2], |
357 | unsigned NRU, |
358 | const MCPhysReg *DL, |
359 | const LaneBitmask *RUMS, |
360 | const char *Strings, |
361 | const char *ClassStrings, |
362 | const uint16_t *SubIndices, |
363 | unsigned NumIndices, |
364 | const SubRegCoveredBits *SubIdxRanges, |
365 | const uint16_t *RET) { |
366 | Desc = D; |
367 | NumRegs = NR; |
368 | RAReg = RA; |
369 | PCReg = PC; |
370 | Classes = C; |
371 | DiffLists = DL; |
372 | RegUnitMaskSequences = RUMS; |
373 | RegStrings = Strings; |
374 | RegClassStrings = ClassStrings; |
375 | NumClasses = NC; |
376 | RegUnitRoots = RURoots; |
377 | NumRegUnits = NRU; |
378 | SubRegIndices = SubIndices; |
379 | NumSubRegIndices = NumIndices; |
380 | SubRegIdxRanges = SubIdxRanges; |
381 | RegEncodingTable = RET; |
382 | |
383 | |
384 | EHL2DwarfRegs = nullptr; |
385 | EHL2DwarfRegsSize = 0; |
386 | L2DwarfRegs = nullptr; |
387 | L2DwarfRegsSize = 0; |
388 | EHDwarf2LRegs = nullptr; |
389 | EHDwarf2LRegsSize = 0; |
390 | Dwarf2LRegs = nullptr; |
391 | Dwarf2LRegsSize = 0; |
392 | } |
393 | |
394 | |
395 | |
396 | |
397 | void mapLLVMRegsToDwarfRegs(const DwarfLLVMRegPair *Map, unsigned Size, |
398 | bool isEH) { |
399 | if (isEH) { |
400 | EHL2DwarfRegs = Map; |
401 | EHL2DwarfRegsSize = Size; |
402 | } else { |
403 | L2DwarfRegs = Map; |
404 | L2DwarfRegsSize = Size; |
405 | } |
406 | } |
407 | |
408 | |
409 | |
410 | |
411 | void mapDwarfRegsToLLVMRegs(const DwarfLLVMRegPair *Map, unsigned Size, |
412 | bool isEH) { |
413 | if (isEH) { |
414 | EHDwarf2LRegs = Map; |
415 | EHDwarf2LRegsSize = Size; |
416 | } else { |
417 | Dwarf2LRegs = Map; |
418 | Dwarf2LRegsSize = Size; |
419 | } |
420 | } |
421 | |
422 | |
423 | |
424 | |
425 | |
426 | |
427 | void mapLLVMRegToSEHReg(MCRegister LLVMReg, int SEHReg) { |
428 | L2SEHRegs[LLVMReg] = SEHReg; |
429 | } |
430 | |
431 | void mapLLVMRegToCVReg(MCRegister LLVMReg, int CVReg) { |
432 | L2CVRegs[LLVMReg] = CVReg; |
433 | } |
434 | |
435 | |
436 | |
437 | MCRegister getRARegister() const { |
438 | return RAReg; |
439 | } |
440 | |
441 | |
442 | MCRegister getProgramCounter() const { |
443 | return PCReg; |
444 | } |
445 | |
446 | const MCRegisterDesc &operator[](MCRegister RegNo) const { |
447 | assert(RegNo < NumRegs && |
448 | "Attempting to access record for invalid register number!"); |
449 | return Desc[RegNo]; |
450 | } |
451 | |
452 | |
453 | |
454 | const MCRegisterDesc &get(MCRegister RegNo) const { |
455 | return operator[](RegNo); |
456 | } |
457 | |
458 | |
459 | |
460 | |
461 | MCRegister getSubReg(MCRegister Reg, unsigned Idx) const; |
462 | |
463 | |
464 | |
465 | MCRegister getMatchingSuperReg(MCRegister Reg, unsigned SubIdx, |
466 | const MCRegisterClass *RC) const; |
467 | |
468 | |
469 | |
470 | |
471 | unsigned getSubRegIndex(MCRegister RegNo, MCRegister SubRegNo) const; |
472 | |
473 | |
474 | |
475 | |
476 | unsigned getSubRegIdxSize(unsigned Idx) const; |
477 | |
478 | |
479 | |
480 | |
481 | unsigned getSubRegIdxOffset(unsigned Idx) const; |
482 | |
483 | |
484 | |
485 | const char *getName(MCRegister RegNo) const { |
486 | return RegStrings + get(RegNo).Name; |
487 | } |
488 | |
489 | |
490 | |
491 | unsigned getNumRegs() const { |
492 | return NumRegs; |
493 | } |
494 | |
495 | |
496 | |
497 | |
498 | unsigned getNumSubRegIndices() const { |
499 | return NumSubRegIndices; |
500 | } |
501 | |
502 | |
503 | |
504 | |
505 | unsigned getNumRegUnits() const { |
506 | return NumRegUnits; |
507 | } |
508 | |
509 | |
510 | |
511 | |
512 | |
513 | int getDwarfRegNum(MCRegister RegNum, bool isEH) const; |
514 | |
515 | |
516 | |
517 | Optional<unsigned> getLLVMRegNum(unsigned RegNum, bool isEH) const; |
518 | |
519 | |
520 | |
521 | int getDwarfRegNumFromDwarfEHRegNum(unsigned RegNum) const; |
522 | |
523 | |
524 | |
525 | int getSEHRegNum(MCRegister RegNum) const; |
526 | |
527 | |
528 | |
529 | int getCodeViewRegNum(MCRegister RegNum) const; |
530 | |
531 | regclass_iterator regclass_begin() const { return Classes; } |
532 | regclass_iterator regclass_end() const { return Classes+NumClasses; } |
533 | iterator_range<regclass_iterator> regclasses() const { |
534 | return make_range(regclass_begin(), regclass_end()); |
535 | } |
536 | |
537 | unsigned getNumRegClasses() const { |
538 | return (unsigned)(regclass_end()-regclass_begin()); |
539 | } |
540 | |
541 | |
542 | |
543 | const MCRegisterClass& getRegClass(unsigned i) const { |
544 | assert(i < getNumRegClasses() && "Register Class ID out of range"); |
545 | return Classes[i]; |
546 | } |
547 | |
548 | const char *getRegClassName(const MCRegisterClass *Class) const { |
549 | return RegClassStrings + Class->NameIdx; |
550 | } |
551 | |
552 | |
553 | uint16_t getEncodingValue(MCRegister RegNo) const { |
554 | assert(RegNo < NumRegs && |
555 | "Attempting to get encoding for invalid register number!"); |
556 | return RegEncodingTable[RegNo]; |
557 | } |
558 | |
559 | |
560 | bool isSubRegister(MCRegister RegA, MCRegister RegB) const { |
561 | return isSuperRegister(RegB, RegA); |
562 | } |
563 | |
564 | |
565 | bool isSuperRegister(MCRegister RegA, MCRegister RegB) const; |
566 | |
567 | |
568 | bool isSubRegisterEq(MCRegister RegA, MCRegister RegB) const { |
569 | return isSuperRegisterEq(RegB, RegA); |
570 | } |
571 | |
572 | |
573 | |
574 | bool isSuperRegisterEq(MCRegister RegA, MCRegister RegB) const { |
575 | return RegA == RegB || isSuperRegister(RegA, RegB); |
576 | } |
577 | |
578 | |
579 | |
580 | bool isSuperOrSubRegisterEq(MCRegister RegA, MCRegister RegB) const { |
581 | return isSubRegisterEq(RegA, RegB) || isSuperRegister(RegA, RegB); |
582 | } |
583 | }; |
584 | |
585 | |
586 | |
587 | |
588 | |
589 | |
590 | |
591 | |
592 | |
593 | |
594 | class MCSubRegIterator : public MCRegisterInfo::DiffListIterator { |
595 | public: |
596 | MCSubRegIterator(MCRegister Reg, const MCRegisterInfo *MCRI, |
597 | bool IncludeSelf = false) { |
598 | init(Reg, MCRI->DiffLists + MCRI->get(Reg).SubRegs); |
599 | |
600 | if (!IncludeSelf) |
601 | ++*this; |
602 | } |
603 | }; |
604 | |
605 | |
606 | |
607 | class MCSubRegIndexIterator { |
608 | MCSubRegIterator SRIter; |
609 | const uint16_t *SRIndex; |
610 | |
611 | public: |
612 | |
613 | |
614 | MCSubRegIndexIterator(MCRegister Reg, const MCRegisterInfo *MCRI) |
615 | : SRIter(Reg, MCRI) { |
616 | SRIndex = MCRI->SubRegIndices + MCRI->get(Reg).SubRegIndices; |
617 | } |
618 | |
619 | |
620 | MCRegister getSubReg() const { |
621 | return *SRIter; |
622 | } |
623 | |
624 | |
625 | unsigned getSubRegIndex() const { |
626 | return *SRIndex; |
627 | } |
628 | |
629 | |
630 | bool isValid() const { return SRIter.isValid(); } |
631 | |
632 | |
633 | void operator++() { |
634 | ++SRIter; |
635 | ++SRIndex; |
636 | } |
637 | }; |
638 | |
639 | |
640 | |
641 | class MCSuperRegIterator : public MCRegisterInfo::DiffListIterator { |
642 | public: |
643 | MCSuperRegIterator() = default; |
644 | |
645 | MCSuperRegIterator(MCRegister Reg, const MCRegisterInfo *MCRI, |
646 | bool IncludeSelf = false) { |
647 | init(Reg, MCRI->DiffLists + MCRI->get(Reg).SuperRegs); |
648 | |
649 | if (!IncludeSelf) |
| |
650 | ++*this; |
| 38 | | Calling 'DiffListIterator::operator++' | |
|
651 | } |
652 | }; |
653 | |
654 | |
655 | |
656 | inline bool MCRegisterInfo::isSuperRegister(MCRegister RegA, MCRegister RegB) const{ |
657 | for (MCSuperRegIterator I(RegA, this); I.isValid(); ++I) |
658 | if (*I == RegB) |
659 | return true; |
660 | return false; |
661 | } |
662 | |
663 | |
664 | |
665 | |
666 | |
667 | |
668 | |
669 | |
670 | |
671 | |
672 | |
673 | |
674 | |
675 | |
676 | |
677 | class MCRegUnitIterator : public MCRegisterInfo::DiffListIterator { |
678 | public: |
679 | |
680 | |
681 | MCRegUnitIterator() = default; |
682 | |
683 | MCRegUnitIterator(MCRegister Reg, const MCRegisterInfo *MCRI) { |
684 | assert(Reg && "Null register has no regunits"); |
685 | assert(MCRegister::isPhysicalRegister(Reg.id())); |
686 | |
687 | unsigned RU = MCRI->get(Reg).RegUnits; |
688 | unsigned Scale = RU & 15; |
689 | unsigned Offset = RU >> 4; |
690 | |
691 | |
692 | |
693 | init(Reg * Scale, MCRI->DiffLists + Offset); |
694 | |
695 | |
696 | |
697 | |
698 | |
699 | advance(); |
700 | } |
701 | }; |
702 | |
703 | |
704 | |
705 | |
706 | class MCRegUnitMaskIterator { |
707 | MCRegUnitIterator RUIter; |
708 | const LaneBitmask *MaskListIter; |
709 | |
710 | public: |
711 | MCRegUnitMaskIterator() = default; |
712 | |
713 | |
714 | |
715 | MCRegUnitMaskIterator(MCRegister Reg, const MCRegisterInfo *MCRI) |
716 | : RUIter(Reg, MCRI) { |
717 | uint16_t Idx = MCRI->get(Reg).RegUnitLaneMasks; |
718 | MaskListIter = &MCRI->RegUnitMaskSequences[Idx]; |
719 | } |
720 | |
721 | |
722 | std::pair<unsigned,LaneBitmask> operator*() const { |
723 | return std::make_pair(*RUIter, *MaskListIter); |
724 | } |
725 | |
726 | |
727 | bool isValid() const { return RUIter.isValid(); } |
728 | |
729 | |
730 | void operator++() { |
731 | ++MaskListIter; |
732 | ++RUIter; |
733 | } |
734 | }; |
735 | |
736 | |
737 | |
738 | |
739 | |
740 | |
741 | |
742 | |
743 | |
744 | |
745 | |
746 | class MCRegUnitRootIterator { |
747 | uint16_t Reg0 = 0; |
748 | uint16_t Reg1 = 0; |
749 | |
750 | public: |
751 | MCRegUnitRootIterator() = default; |
752 | |
753 | MCRegUnitRootIterator(unsigned RegUnit, const MCRegisterInfo *MCRI) { |
754 | assert(RegUnit < MCRI->getNumRegUnits() && "Invalid register unit"); |
755 | Reg0 = MCRI->RegUnitRoots[RegUnit][0]; |
756 | Reg1 = MCRI->RegUnitRoots[RegUnit][1]; |
757 | } |
758 | |
759 | |
760 | unsigned operator*() const { |
761 | return Reg0; |
762 | } |
763 | |
764 | |
765 | bool isValid() const { |
766 | return Reg0; |
767 | } |
768 | |
769 | |
770 | void operator++() { |
771 | assert(isValid() && "Cannot move off the end of the list."); |
772 | Reg0 = Reg1; |
773 | Reg1 = 0; |
774 | } |
775 | }; |
776 | |
777 | |
778 | |
779 | |
780 | class MCRegAliasIterator { |
781 | private: |
782 | MCRegister Reg; |
783 | const MCRegisterInfo *MCRI; |
784 | bool IncludeSelf; |
785 | |
786 | MCRegUnitIterator RI; |
787 | MCRegUnitRootIterator RRI; |
788 | MCSuperRegIterator SI; |
789 | |
790 | public: |
791 | MCRegAliasIterator(MCRegister Reg, const MCRegisterInfo *MCRI, |
792 | bool IncludeSelf) |
793 | : Reg(Reg), MCRI(MCRI), IncludeSelf(IncludeSelf) { |
794 | |
795 | for (RI = MCRegUnitIterator(Reg, MCRI); RI.isValid(); ++RI) { |
796 | for (RRI = MCRegUnitRootIterator(*RI, MCRI); RRI.isValid(); ++RRI) { |
797 | for (SI = MCSuperRegIterator(*RRI, MCRI, true); SI.isValid(); ++SI) { |
798 | if (!(!IncludeSelf && Reg == *SI)) |
799 | return; |
800 | } |
801 | } |
802 | } |
803 | } |
804 | |
805 | bool isValid() const { return RI.isValid(); } |
806 | |
807 | MCRegister operator*() const { |
808 | assert(SI.isValid() && "Cannot dereference an invalid iterator."); |
809 | return *SI; |
810 | } |
811 | |
812 | void advance() { |
813 | |
814 | ++SI; |
815 | if (SI.isValid()) return; |
816 | |
817 | ++RRI; |
818 | if (RRI.isValid()) { |
819 | SI = MCSuperRegIterator(*RRI, MCRI, true); |
820 | return; |
821 | } |
822 | |
823 | ++RI; |
824 | if (RI.isValid()) { |
825 | RRI = MCRegUnitRootIterator(*RI, MCRI); |
826 | SI = MCSuperRegIterator(*RRI, MCRI, true); |
827 | } |
828 | } |
829 | |
830 | void operator++() { |
831 | assert(isValid() && "Cannot move off the end of the list."); |
832 | do advance(); |
833 | while (!IncludeSelf && isValid() && *SI == Reg); |
834 | } |
835 | }; |
836 | |
837 | } |
838 | |
839 | #endif // LLVM_MC_MCREGISTERINFO_H |