Bug Summary

File:llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp
Warning:line 297, column 9
Assigned value is garbage or undefined

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name BPFISelDAGToDAG.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~++20210828111110+16086d47c0d0/build-llvm/lib/Target/BPF -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/Target/BPF -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Target/BPF -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-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~++20210828111110+16086d47c0d0/build-llvm/lib/Target/BPF -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0=. -ferror-limit 19 -fvisibility hidden -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-08-28-193554-24367-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp

1//===-- BPFISelDAGToDAG.cpp - A dag to dag inst selector for BPF ----------===//
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 a DAG pattern matching instruction selector for BPF,
10// converting from a legalized dag to a BPF dag.
11//
12//===----------------------------------------------------------------------===//
13
14#include "BPF.h"
15#include "BPFRegisterInfo.h"
16#include "BPFSubtarget.h"
17#include "BPFTargetMachine.h"
18#include "llvm/CodeGen/FunctionLoweringInfo.h"
19#include "llvm/CodeGen/MachineConstantPool.h"
20#include "llvm/CodeGen/MachineFrameInfo.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/CodeGen/SelectionDAGISel.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/IntrinsicInst.h"
27#include "llvm/IR/IntrinsicsBPF.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/Endian.h"
30#include "llvm/Support/ErrorHandling.h"
31#include "llvm/Support/raw_ostream.h"
32#include "llvm/Target/TargetMachine.h"
33
34using namespace llvm;
35
36#define DEBUG_TYPE"bpf-isel" "bpf-isel"
37
38// Instruction Selector Implementation
39namespace {
40
41class BPFDAGToDAGISel : public SelectionDAGISel {
42
43 /// Subtarget - Keep a pointer to the BPFSubtarget around so that we can
44 /// make the right decision when generating code for different subtargets.
45 const BPFSubtarget *Subtarget;
46
47public:
48 explicit BPFDAGToDAGISel(BPFTargetMachine &TM)
49 : SelectionDAGISel(TM), Subtarget(nullptr) {}
50
51 StringRef getPassName() const override {
52 return "BPF DAG->DAG Pattern Instruction Selection";
53 }
54
55 bool runOnMachineFunction(MachineFunction &MF) override {
56 // Reset the subtarget each time through.
57 Subtarget = &MF.getSubtarget<BPFSubtarget>();
58 return SelectionDAGISel::runOnMachineFunction(MF);
59 }
60
61 void PreprocessISelDAG() override;
62
63 bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode,
64 std::vector<SDValue> &OutOps) override;
65
66
67private:
68// Include the pieces autogenerated from the target description.
69#include "BPFGenDAGISel.inc"
70
71 void Select(SDNode *N) override;
72
73 // Complex Pattern for address selection.
74 bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
75 bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
76
77 // Node preprocessing cases
78 void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator &I);
79 void PreprocessCopyToReg(SDNode *Node);
80 void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator &I);
81
82 // Find constants from a constant structure
83 typedef std::vector<unsigned char> val_vec_type;
84 bool fillGenericConstant(const DataLayout &DL, const Constant *CV,
85 val_vec_type &Vals, uint64_t Offset);
86 bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA,
87 val_vec_type &Vals, int Offset);
88 bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA,
89 val_vec_type &Vals, int Offset);
90 bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS,
91 val_vec_type &Vals, int Offset);
92 bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset,
93 uint64_t Size, unsigned char *ByteSeq);
94 // Mapping from ConstantStruct global value to corresponding byte-list values
95 std::map<const void *, val_vec_type> cs_vals_;
96};
97} // namespace
98
99// ComplexPattern used on BPF Load/Store instructions
100bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
101 // if Address is FI, get the TargetFrameIndex.
102 SDLoc DL(Addr);
103 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
104 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
105 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
106 return true;
107 }
108
109 if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
110 Addr.getOpcode() == ISD::TargetGlobalAddress)
111 return false;
112
113 // Addresses of the form Addr+const or Addr|const
114 if (CurDAG->isBaseWithConstantOffset(Addr)) {
115 auto *CN = cast<ConstantSDNode>(Addr.getOperand(1));
116 if (isInt<16>(CN->getSExtValue())) {
117 // If the first operand is a FI, get the TargetFI Node
118 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
119 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
120 else
121 Base = Addr.getOperand(0);
122
123 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
124 return true;
125 }
126 }
127
128 Base = Addr;
129 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
130 return true;
131}
132
133// ComplexPattern used on BPF FI instruction
134bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base,
135 SDValue &Offset) {
136 SDLoc DL(Addr);
137
138 if (!CurDAG->isBaseWithConstantOffset(Addr))
139 return false;
140
141 // Addresses of the form Addr+const or Addr|const
142 auto *CN = cast<ConstantSDNode>(Addr.getOperand(1));
143 if (isInt<16>(CN->getSExtValue())) {
144 // If the first operand is a FI, get the TargetFI Node
145 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
146 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
147 else
148 return false;
149
150 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
151 return true;
152 }
153
154 return false;
155}
156
157bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand(
158 const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) {
159 SDValue Op0, Op1;
160 switch (ConstraintCode) {
161 default:
162 return true;
163 case InlineAsm::Constraint_m: // memory
164 if (!SelectAddr(Op, Op0, Op1))
165 return true;
166 break;
167 }
168
169 SDLoc DL(Op);
170 SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);;
171 OutOps.push_back(Op0);
172 OutOps.push_back(Op1);
173 OutOps.push_back(AluOp);
174 return false;
175}
176
177void BPFDAGToDAGISel::Select(SDNode *Node) {
178 unsigned Opcode = Node->getOpcode();
179
180 // If we have a custom node, we already have selected!
181 if (Node->isMachineOpcode()) {
182 LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "== "; Node->dump(CurDAG);
dbgs() << '\n'; } } while (false)
;
183 return;
184 }
185
186 // tablegen selection should be handled here.
187 switch (Opcode) {
188 default:
189 break;
190 case ISD::SDIV: {
191 DebugLoc Empty;
192 const DebugLoc &DL = Node->getDebugLoc();
193 if (DL != Empty)
194 errs() << "Error at line " << DL.getLine() << ": ";
195 else
196 errs() << "Error: ";
197 errs() << "Unsupport signed division for DAG: ";
198 Node->print(errs(), CurDAG);
199 errs() << "Please convert to unsigned div/mod.\n";
200 break;
201 }
202 case ISD::INTRINSIC_W_CHAIN: {
203 unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
204 switch (IntNo) {
205 case Intrinsic::bpf_load_byte:
206 case Intrinsic::bpf_load_half:
207 case Intrinsic::bpf_load_word: {
208 SDLoc DL(Node);
209 SDValue Chain = Node->getOperand(0);
210 SDValue N1 = Node->getOperand(1);
211 SDValue Skb = Node->getOperand(2);
212 SDValue N3 = Node->getOperand(3);
213
214 SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
215 Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
216 Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
217 break;
218 }
219 }
220 break;
221 }
222
223 case ISD::FrameIndex: {
224 int FI = cast<FrameIndexSDNode>(Node)->getIndex();
225 EVT VT = Node->getValueType(0);
226 SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
227 unsigned Opc = BPF::MOV_rr;
228 if (Node->hasOneUse()) {
229 CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
230 return;
231 }
232 ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
233 return;
234 }
235 }
236
237 // Select the default instruction
238 SelectCode(Node);
239}
240
241void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
242 SelectionDAG::allnodes_iterator &I) {
243 union {
244 uint8_t c[8];
245 uint16_t s;
246 uint32_t i;
247 uint64_t d;
248 } new_val; // hold up the constant values replacing loads.
249 bool to_replace = false;
250 SDLoc DL(Node);
251 const LoadSDNode *LD = cast<LoadSDNode>(Node);
5
'Node' is a 'LoadSDNode'
252 uint64_t size = LD->getMemOperand()->getSize();
6
Calling 'MachineMemOperand::getSize'
9
Returning from 'MachineMemOperand::getSize'
253
254 if (!size || size > 8 || (size & (size - 1)) || !LD->isSimple())
10
Assuming 'size' is not equal to 0
11
Assuming 'size' is <= 8
12
Assuming the condition is false
13
Calling 'MemSDNode::isSimple'
16
Returning from 'MemSDNode::isSimple'
17
Taking false branch
255 return;
256
257 SDNode *LDAddrNode = LD->getOperand(1).getNode();
258 // Match LDAddr against either global_addr or (global_addr + offset)
259 unsigned opcode = LDAddrNode->getOpcode();
260 if (opcode == ISD::ADD) {
18
Assuming 'opcode' is equal to ADD
19
Taking true branch
261 SDValue OP1 = LDAddrNode->getOperand(0);
262 SDValue OP2 = LDAddrNode->getOperand(1);
263
264 // We want to find the pattern global_addr + offset
265 SDNode *OP1N = OP1.getNode();
266 if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)
20
Assuming the condition is false
21
Assuming the condition is false
267 return;
268
269 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Check candidate load: "; LD->
dump(); dbgs() << '\n'; } } while (false)
;
22
Taking false branch
23
Assuming 'DebugFlag' is false
24
Loop condition is false. Exiting loop
270
271 const GlobalAddressSDNode *GADN =
272 dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());
25
Assuming the object is a 'GlobalAddressSDNode'
273 const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());
26
Assuming the object is a 'ConstantSDNode'
274 if (GADN
26.1
'GADN' is non-null
26.1
'GADN' is non-null
26.1
'GADN' is non-null
26.1
'GADN' is non-null
26.1
'GADN' is non-null
&& CDN
26.2
'CDN' is non-null
26.2
'CDN' is non-null
26.2
'CDN' is non-null
26.2
'CDN' is non-null
26.2
'CDN' is non-null
)
27
Taking true branch
275 to_replace =
276 getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);
28
Calling 'BPFDAGToDAGISel::getConstantFieldValue'
46
Returning from 'BPFDAGToDAGISel::getConstantFieldValue'
277 } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
278 LDAddrNode->getNumOperands() > 0) {
279 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Check candidate load: "; LD->
dump(); dbgs() << '\n'; } } while (false)
;
280
281 SDValue OP1 = LDAddrNode->getOperand(0);
282 if (const GlobalAddressSDNode *GADN =
283 dyn_cast<GlobalAddressSDNode>(OP1.getNode()))
284 to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);
285 }
286
287 if (!to_replace
46.1
'to_replace' is true
46.1
'to_replace' is true
46.1
'to_replace' is true
46.1
'to_replace' is true
46.1
'to_replace' is true
)
47
Taking false branch
288 return;
289
290 // replacing the old with a new value
291 uint64_t val;
292 if (size == 1)
48
Assuming 'size' is not equal to 1
49
Taking false branch
293 val = new_val.c[0];
294 else if (size == 2)
50
Assuming 'size' is not equal to 2
51
Taking false branch
295 val = new_val.s;
296 else if (size == 4)
52
Assuming 'size' is equal to 4
53
Taking true branch
297 val = new_val.i;
54
Assigned value is garbage or undefined
298 else {
299 val = new_val.d;
300 }
301
302 LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Replacing load of size " <<
size << " with constant " << val << '\n'; }
} while (false)
303 << val << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Replacing load of size " <<
size << " with constant " << val << '\n'; }
} while (false)
;
304 SDValue NVal = CurDAG->getConstant(val, DL, LD->getValueType(0));
305
306 // After replacement, the current node is dead, we need to
307 // go backward one step to make iterator still work
308 I--;
309 SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
310 SDValue To[] = {NVal, NVal};
311 CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);
312 I++;
313 // It is safe to delete node now
314 CurDAG->DeleteNode(Node);
315}
316
317void BPFDAGToDAGISel::PreprocessISelDAG() {
318 // Iterate through all nodes, interested in the following case:
319 //
320 // . loads from ConstantStruct or ConstantArray of constructs
321 // which can be turns into constant itself, with this we can
322 // avoid reading from read-only section at runtime.
323 //
324 // . Removing redundant AND for intrinsic narrow loads.
325 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
1
Loop condition is true. Entering loop body
326 E = CurDAG->allnodes_end();
327 I != E;) {
328 SDNode *Node = &*I++;
329 unsigned Opcode = Node->getOpcode();
330 if (Opcode == ISD::LOAD)
2
Assuming 'Opcode' is equal to LOAD
3
Taking true branch
331 PreprocessLoad(Node, I);
4
Calling 'BPFDAGToDAGISel::PreprocessLoad'
332 else if (Opcode == ISD::AND)
333 PreprocessTrunc(Node, I);
334 }
335}
336
337bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
338 uint64_t Offset, uint64_t Size,
339 unsigned char *ByteSeq) {
340 const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
29
Assuming the object is a 'GlobalVariable'
341
342 if (!V
29.1
'V' is non-null, which participates in a condition later
29.1
'V' is non-null, which participates in a condition later
29.1
'V' is non-null, which participates in a condition later
29.1
'V' is non-null, which participates in a condition later
29.1
'V' is non-null, which participates in a condition later
|| !V->hasInitializer() || !V->isConstant())
30
Calling 'GlobalVariable::hasInitializer'
33
Returning from 'GlobalVariable::hasInitializer'
34
Assuming the condition is false
35
Taking false branch
343 return false;
344
345 const Constant *Init = V->getInitializer();
346 const DataLayout &DL = CurDAG->getDataLayout();
347 val_vec_type TmpVal;
348
349 auto it = cs_vals_.find(static_cast<const void *>(Init));
350 if (it != cs_vals_.end()) {
36
Calling 'operator!='
39
Returning from 'operator!='
40
Taking true branch
351 TmpVal = it->second;
352 } else {
353 uint64_t total_size = 0;
354 if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
355 total_size =
356 DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
357 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
358 total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
359 CA->getNumOperands();
360 else
361 return false;
362
363 val_vec_type Vals(total_size, 0);
364 if (fillGenericConstant(DL, Init, Vals, 0) == false)
365 return false;
366 cs_vals_[static_cast<const void *>(Init)] = Vals;
367 TmpVal = std::move(Vals);
368 }
369
370 // test whether host endianness matches target
371 union {
372 uint8_t c[2];
373 uint16_t s;
374 } test_buf;
375 uint16_t test_val = 0x2345;
376 if (DL.isLittleEndian())
41
Taking false branch
377 support::endian::write16le(test_buf.c, test_val);
378 else
379 support::endian::write16be(test_buf.c, test_val);
380
381 bool endian_match = test_buf.s == test_val;
42
Assuming 'test_val' is not equal to field 's'
382 for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
43
Assuming the condition is false
44
Loop condition is false. Execution continues on line 385
383 ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
384
385 return true;
45
Returning the value 1, which participates in a condition later
386}
387
388bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
389 const Constant *CV,
390 val_vec_type &Vals, uint64_t Offset) {
391 uint64_t Size = DL.getTypeAllocSize(CV->getType());
392
393 if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
394 return true; // already done
395
396 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
397 uint64_t val = CI->getZExtValue();
398 LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Byte array at offset " <<
Offset << " with value " << val << '\n'; }
} while (false)
399 << val << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Byte array at offset " <<
Offset << " with value " << val << '\n'; }
} while (false)
;
400
401 if (Size > 8 || (Size & (Size - 1)))
402 return false;
403
404 // Store based on target endian
405 for (uint64_t i = 0; i < Size; ++i) {
406 Vals[Offset + i] = DL.isLittleEndian()
407 ? ((val >> (i * 8)) & 0xFF)
408 : ((val >> ((Size - i - 1) * 8)) & 0xFF);
409 }
410 return true;
411 }
412
413 if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
414 return fillConstantDataArray(DL, CDA, Vals, Offset);
415
416 if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
417 return fillConstantArray(DL, CA, Vals, Offset);
418
419 if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
420 return fillConstantStruct(DL, CVS, Vals, Offset);
421
422 return false;
423}
424
425bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
426 const ConstantDataArray *CDA,
427 val_vec_type &Vals, int Offset) {
428 for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
429 if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
430 false)
431 return false;
432 Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
433 }
434
435 return true;
436}
437
438bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
439 const ConstantArray *CA,
440 val_vec_type &Vals, int Offset) {
441 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
442 if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
443 return false;
444 Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
445 }
446
447 return true;
448}
449
450bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
451 const ConstantStruct *CS,
452 val_vec_type &Vals, int Offset) {
453 const StructLayout *Layout = DL.getStructLayout(CS->getType());
454 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
455 const Constant *Field = CS->getOperand(i);
456 uint64_t SizeSoFar = Layout->getElementOffset(i);
457 if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
458 return false;
459 }
460 return true;
461}
462
463void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
464 SelectionDAG::allnodes_iterator &I) {
465 ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
466 if (!MaskN)
467 return;
468
469 // The Reg operand should be a virtual register, which is defined
470 // outside the current basic block. DAG combiner has done a pretty
471 // good job in removing truncating inside a single basic block except
472 // when the Reg operand comes from bpf_load_[byte | half | word] for
473 // which the generic optimizer doesn't understand their results are
474 // zero extended.
475 SDValue BaseV = Node->getOperand(0);
476 if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN)
477 return;
478
479 unsigned IntNo = cast<ConstantSDNode>(BaseV->getOperand(1))->getZExtValue();
480 uint64_t MaskV = MaskN->getZExtValue();
481
482 if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) ||
483 (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) ||
484 (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF)))
485 return;
486
487 LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Remove the redundant AND operation in: "
; Node->dump(); dbgs() << '\n'; } } while (false)
488 Node->dump(); dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bpf-isel")) { dbgs() << "Remove the redundant AND operation in: "
; Node->dump(); dbgs() << '\n'; } } while (false)
;
489
490 I--;
491 CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
492 I++;
493 CurDAG->DeleteNode(Node);
494}
495
496FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
497 return new BPFDAGToDAGISel(TM);
498}

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/MachineMemOperand.h

1//==- llvm/CodeGen/MachineMemOperand.h - MachineMemOperand class -*- 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 contains the declaration of the MachineMemOperand class, which is a
10// description of a memory reference. It is used to help track dependencies
11// in the backend.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CODEGEN_MACHINEMEMOPERAND_H
16#define LLVM_CODEGEN_MACHINEMEMOPERAND_H
17
18#include "llvm/ADT/BitmaskEnum.h"
19#include "llvm/ADT/PointerUnion.h"
20#include "llvm/CodeGen/PseudoSourceValue.h"
21#include "llvm/IR/DerivedTypes.h"
22#include "llvm/IR/Value.h" // PointerLikeTypeTraits<Value*>
23#include "llvm/Support/AtomicOrdering.h"
24#include "llvm/Support/DataTypes.h"
25#include "llvm/Support/LowLevelTypeImpl.h"
26
27namespace llvm {
28
29class FoldingSetNodeID;
30class MDNode;
31class raw_ostream;
32class MachineFunction;
33class ModuleSlotTracker;
34
35/// This class contains a discriminated union of information about pointers in
36/// memory operands, relating them back to LLVM IR or to virtual locations (such
37/// as frame indices) that are exposed during codegen.
38struct MachinePointerInfo {
39 /// This is the IR pointer value for the access, or it is null if unknown.
40 /// If this is null, then the access is to a pointer in the default address
41 /// space.
42 PointerUnion<const Value *, const PseudoSourceValue *> V;
43
44 /// Offset - This is an offset from the base Value*.
45 int64_t Offset;
46
47 unsigned AddrSpace = 0;
48
49 uint8_t StackID;
50
51 explicit MachinePointerInfo(const Value *v, int64_t offset = 0,
52 uint8_t ID = 0)
53 : V(v), Offset(offset), StackID(ID) {
54 AddrSpace = v ? v->getType()->getPointerAddressSpace() : 0;
55 }
56
57 explicit MachinePointerInfo(const PseudoSourceValue *v, int64_t offset = 0,
58 uint8_t ID = 0)
59 : V(v), Offset(offset), StackID(ID) {
60 AddrSpace = v ? v->getAddressSpace() : 0;
61 }
62
63 explicit MachinePointerInfo(unsigned AddressSpace = 0, int64_t offset = 0)
64 : V((const Value *)nullptr), Offset(offset), AddrSpace(AddressSpace),
65 StackID(0) {}
66
67 explicit MachinePointerInfo(
68 PointerUnion<const Value *, const PseudoSourceValue *> v,
69 int64_t offset = 0,
70 uint8_t ID = 0)
71 : V(v), Offset(offset), StackID(ID) {
72 if (V) {
73 if (const auto *ValPtr = V.dyn_cast<const Value*>())
74 AddrSpace = ValPtr->getType()->getPointerAddressSpace();
75 else
76 AddrSpace = V.get<const PseudoSourceValue*>()->getAddressSpace();
77 }
78 }
79
80 MachinePointerInfo getWithOffset(int64_t O) const {
81 if (V.isNull())
82 return MachinePointerInfo(AddrSpace, Offset + O);
83 if (V.is<const Value*>())
84 return MachinePointerInfo(V.get<const Value*>(), Offset + O, StackID);
85 return MachinePointerInfo(V.get<const PseudoSourceValue*>(), Offset + O,
86 StackID);
87 }
88
89 /// Return true if memory region [V, V+Offset+Size) is known to be
90 /// dereferenceable.
91 bool isDereferenceable(unsigned Size, LLVMContext &C,
92 const DataLayout &DL) const;
93
94 /// Return the LLVM IR address space number that this pointer points into.
95 unsigned getAddrSpace() const;
96
97 /// Return a MachinePointerInfo record that refers to the constant pool.
98 static MachinePointerInfo getConstantPool(MachineFunction &MF);
99
100 /// Return a MachinePointerInfo record that refers to the specified
101 /// FrameIndex.
102 static MachinePointerInfo getFixedStack(MachineFunction &MF, int FI,
103 int64_t Offset = 0);
104
105 /// Return a MachinePointerInfo record that refers to a jump table entry.
106 static MachinePointerInfo getJumpTable(MachineFunction &MF);
107
108 /// Return a MachinePointerInfo record that refers to a GOT entry.
109 static MachinePointerInfo getGOT(MachineFunction &MF);
110
111 /// Stack pointer relative access.
112 static MachinePointerInfo getStack(MachineFunction &MF, int64_t Offset,
113 uint8_t ID = 0);
114
115 /// Stack memory without other information.
116 static MachinePointerInfo getUnknownStack(MachineFunction &MF);
117};
118
119
120//===----------------------------------------------------------------------===//
121/// A description of a memory reference used in the backend.
122/// Instead of holding a StoreInst or LoadInst, this class holds the address
123/// Value of the reference along with a byte size and offset. This allows it
124/// to describe lowered loads and stores. Also, the special PseudoSourceValue
125/// objects can be used to represent loads and stores to memory locations
126/// that aren't explicit in the regular LLVM IR.
127///
128class MachineMemOperand {
129public:
130 /// Flags values. These may be or'd together.
131 enum Flags : uint16_t {
132 // No flags set.
133 MONone = 0,
134 /// The memory access reads data.
135 MOLoad = 1u << 0,
136 /// The memory access writes data.
137 MOStore = 1u << 1,
138 /// The memory access is volatile.
139 MOVolatile = 1u << 2,
140 /// The memory access is non-temporal.
141 MONonTemporal = 1u << 3,
142 /// The memory access is dereferenceable (i.e., doesn't trap).
143 MODereferenceable = 1u << 4,
144 /// The memory access always returns the same value (or traps).
145 MOInvariant = 1u << 5,
146
147 // Reserved for use by target-specific passes.
148 // Targets may override getSerializableMachineMemOperandTargetFlags() to
149 // enable MIR serialization/parsing of these flags. If more of these flags
150 // are added, the MIR printing/parsing code will need to be updated as well.
151 MOTargetFlag1 = 1u << 6,
152 MOTargetFlag2 = 1u << 7,
153 MOTargetFlag3 = 1u << 8,
154
155 LLVM_MARK_AS_BITMASK_ENUM(/* LargestFlag = */ MOTargetFlag3)LLVM_BITMASK_LARGEST_ENUMERATOR = MOTargetFlag3
156 };
157
158private:
159 /// Atomic information for this memory operation.
160 struct MachineAtomicInfo {
161 /// Synchronization scope ID for this memory operation.
162 unsigned SSID : 8; // SyncScope::ID
163 /// Atomic ordering requirements for this memory operation. For cmpxchg
164 /// atomic operations, atomic ordering requirements when store occurs.
165 unsigned Ordering : 4; // enum AtomicOrdering
166 /// For cmpxchg atomic operations, atomic ordering requirements when store
167 /// does not occur.
168 unsigned FailureOrdering : 4; // enum AtomicOrdering
169 };
170
171 MachinePointerInfo PtrInfo;
172
173 /// Track the memory type of the access. An access size which is unknown or
174 /// too large to be represented by LLT should use the invalid LLT.
175 LLT MemoryType;
176
177 Flags FlagVals;
178 Align BaseAlign;
179 MachineAtomicInfo AtomicInfo;
180 AAMDNodes AAInfo;
181 const MDNode *Ranges;
182
183public:
184 /// Construct a MachineMemOperand object with the specified PtrInfo, flags,
185 /// size, and base alignment. For atomic operations the synchronization scope
186 /// and atomic ordering requirements must also be specified. For cmpxchg
187 /// atomic operations the atomic ordering requirements when store does not
188 /// occur must also be specified.
189 MachineMemOperand(MachinePointerInfo PtrInfo, Flags flags, uint64_t s,
190 Align a, const AAMDNodes &AAInfo = AAMDNodes(),
191 const MDNode *Ranges = nullptr,
192 SyncScope::ID SSID = SyncScope::System,
193 AtomicOrdering Ordering = AtomicOrdering::NotAtomic,
194 AtomicOrdering FailureOrdering = AtomicOrdering::NotAtomic);
195 MachineMemOperand(MachinePointerInfo PtrInfo, Flags flags, LLT type, Align a,
196 const AAMDNodes &AAInfo = AAMDNodes(),
197 const MDNode *Ranges = nullptr,
198 SyncScope::ID SSID = SyncScope::System,
199 AtomicOrdering Ordering = AtomicOrdering::NotAtomic,
200 AtomicOrdering FailureOrdering = AtomicOrdering::NotAtomic);
201
202 const MachinePointerInfo &getPointerInfo() const { return PtrInfo; }
203
204 /// Return the base address of the memory access. This may either be a normal
205 /// LLVM IR Value, or one of the special values used in CodeGen.
206 /// Special values are those obtained via
207 /// PseudoSourceValue::getFixedStack(int), PseudoSourceValue::getStack, and
208 /// other PseudoSourceValue member functions which return objects which stand
209 /// for frame/stack pointer relative references and other special references
210 /// which are not representable in the high-level IR.
211 const Value *getValue() const { return PtrInfo.V.dyn_cast<const Value*>(); }
212
213 const PseudoSourceValue *getPseudoValue() const {
214 return PtrInfo.V.dyn_cast<const PseudoSourceValue*>();
215 }
216
217 const void *getOpaqueValue() const { return PtrInfo.V.getOpaqueValue(); }
218
219 /// Return the raw flags of the source value, \see Flags.
220 Flags getFlags() const { return FlagVals; }
221
222 /// Bitwise OR the current flags with the given flags.
223 void setFlags(Flags f) { FlagVals |= f; }
224
225 /// For normal values, this is a byte offset added to the base address.
226 /// For PseudoSourceValue::FPRel values, this is the FrameIndex number.
227 int64_t getOffset() const { return PtrInfo.Offset; }
228
229 unsigned getAddrSpace() const { return PtrInfo.getAddrSpace(); }
230
231 /// Return the memory type of the memory reference. This should only be relied
232 /// on for GlobalISel G_* operation legalization.
233 LLT getMemoryType() const { return MemoryType; }
234
235 /// Return the size in bytes of the memory reference.
236 uint64_t getSize() const {
237 return MemoryType.isValid() ? MemoryType.getSizeInBytes() : ~UINT64_C(0)0UL;
7
'?' condition is true
8
Returning value, which participates in a condition later
238 }
239
240 /// Return the size in bits of the memory reference.
241 uint64_t getSizeInBits() const {
242 return MemoryType.isValid() ? MemoryType.getSizeInBits() : ~UINT64_C(0)0UL;
243 }
244
245 LLT getType() const {
246 return MemoryType;
247 }
248
249 /// Return the minimum known alignment in bytes of the actual memory
250 /// reference.
251 Align getAlign() const;
252
253 /// Return the minimum known alignment in bytes of the base address, without
254 /// the offset.
255 Align getBaseAlign() const { return BaseAlign; }
256
257 /// Return the AA tags for the memory reference.
258 AAMDNodes getAAInfo() const { return AAInfo; }
259
260 /// Return the range tag for the memory reference.
261 const MDNode *getRanges() const { return Ranges; }
262
263 /// Returns the synchronization scope ID for this memory operation.
264 SyncScope::ID getSyncScopeID() const {
265 return static_cast<SyncScope::ID>(AtomicInfo.SSID);
266 }
267
268 /// Return the atomic ordering requirements for this memory operation. For
269 /// cmpxchg atomic operations, return the atomic ordering requirements when
270 /// store occurs.
271 AtomicOrdering getSuccessOrdering() const {
272 return static_cast<AtomicOrdering>(AtomicInfo.Ordering);
273 }
274
275 /// For cmpxchg atomic operations, return the atomic ordering requirements
276 /// when store does not occur.
277 AtomicOrdering getFailureOrdering() const {
278 return static_cast<AtomicOrdering>(AtomicInfo.FailureOrdering);
279 }
280
281 /// Return a single atomic ordering that is at least as strong as both the
282 /// success and failure orderings for an atomic operation. (For operations
283 /// other than cmpxchg, this is equivalent to getSuccessOrdering().)
284 AtomicOrdering getMergedOrdering() const {
285 return getMergedAtomicOrdering(getSuccessOrdering(), getFailureOrdering());
286 }
287
288 bool isLoad() const { return FlagVals & MOLoad; }
289 bool isStore() const { return FlagVals & MOStore; }
290 bool isVolatile() const { return FlagVals & MOVolatile; }
291 bool isNonTemporal() const { return FlagVals & MONonTemporal; }
292 bool isDereferenceable() const { return FlagVals & MODereferenceable; }
293 bool isInvariant() const { return FlagVals & MOInvariant; }
294
295 /// Returns true if this operation has an atomic ordering requirement of
296 /// unordered or higher, false otherwise.
297 bool isAtomic() const {
298 return getSuccessOrdering() != AtomicOrdering::NotAtomic;
299 }
300
301 /// Returns true if this memory operation doesn't have any ordering
302 /// constraints other than normal aliasing. Volatile and (ordered) atomic
303 /// memory operations can't be reordered.
304 bool isUnordered() const {
305 return (getSuccessOrdering() == AtomicOrdering::NotAtomic ||
306 getSuccessOrdering() == AtomicOrdering::Unordered) &&
307 !isVolatile();
308 }
309
310 /// Update this MachineMemOperand to reflect the alignment of MMO, if it has a
311 /// greater alignment. This must only be used when the new alignment applies
312 /// to all users of this MachineMemOperand.
313 void refineAlignment(const MachineMemOperand *MMO);
314
315 /// Change the SourceValue for this MachineMemOperand. This should only be
316 /// used when an object is being relocated and all references to it are being
317 /// updated.
318 void setValue(const Value *NewSV) { PtrInfo.V = NewSV; }
319 void setValue(const PseudoSourceValue *NewSV) { PtrInfo.V = NewSV; }
320 void setOffset(int64_t NewOffset) { PtrInfo.Offset = NewOffset; }
321
322 /// Reset the tracked memory type.
323 void setType(LLT NewTy) {
324 MemoryType = NewTy;
325 }
326
327 /// Profile - Gather unique data for the object.
328 ///
329 void Profile(FoldingSetNodeID &ID) const;
330
331 /// Support for operator<<.
332 /// @{
333 void print(raw_ostream &OS, ModuleSlotTracker &MST,
334 SmallVectorImpl<StringRef> &SSNs, const LLVMContext &Context,
335 const MachineFrameInfo *MFI, const TargetInstrInfo *TII) const;
336 /// @}
337
338 friend bool operator==(const MachineMemOperand &LHS,
339 const MachineMemOperand &RHS) {
340 return LHS.getValue() == RHS.getValue() &&
341 LHS.getPseudoValue() == RHS.getPseudoValue() &&
342 LHS.getSize() == RHS.getSize() &&
343 LHS.getOffset() == RHS.getOffset() &&
344 LHS.getFlags() == RHS.getFlags() &&
345 LHS.getAAInfo() == RHS.getAAInfo() &&
346 LHS.getRanges() == RHS.getRanges() &&
347 LHS.getAlign() == RHS.getAlign() &&
348 LHS.getAddrSpace() == RHS.getAddrSpace();
349 }
350
351 friend bool operator!=(const MachineMemOperand &LHS,
352 const MachineMemOperand &RHS) {
353 return !(LHS == RHS);
354 }
355};
356
357} // End llvm namespace
358
359#endif

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h

1//===- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ----*- 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 declares the SDNode class and derived classes, which are used to
10// represent the nodes and operations present in a SelectionDAG. These nodes
11// and operations are machine code level operations, with some similarities to
12// the GCC RTL representation.
13//
14// Clients should include the SelectionDAG.h file instead of this file directly.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H
19#define LLVM_CODEGEN_SELECTIONDAGNODES_H
20
21#include "llvm/ADT/APFloat.h"
22#include "llvm/ADT/ArrayRef.h"
23#include "llvm/ADT/BitVector.h"
24#include "llvm/ADT/FoldingSet.h"
25#include "llvm/ADT/GraphTraits.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/ilist_node.h"
29#include "llvm/ADT/iterator.h"
30#include "llvm/ADT/iterator_range.h"
31#include "llvm/CodeGen/ISDOpcodes.h"
32#include "llvm/CodeGen/MachineMemOperand.h"
33#include "llvm/CodeGen/Register.h"
34#include "llvm/CodeGen/ValueTypes.h"
35#include "llvm/IR/Constants.h"
36#include "llvm/IR/DebugLoc.h"
37#include "llvm/IR/Instruction.h"
38#include "llvm/IR/Instructions.h"
39#include "llvm/IR/Metadata.h"
40#include "llvm/IR/Operator.h"
41#include "llvm/Support/AlignOf.h"
42#include "llvm/Support/AtomicOrdering.h"
43#include "llvm/Support/Casting.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/MachineValueType.h"
46#include "llvm/Support/TypeSize.h"
47#include <algorithm>
48#include <cassert>
49#include <climits>
50#include <cstddef>
51#include <cstdint>
52#include <cstring>
53#include <iterator>
54#include <string>
55#include <tuple>
56
57namespace llvm {
58
59class APInt;
60class Constant;
61template <typename T> struct DenseMapInfo;
62class GlobalValue;
63class MachineBasicBlock;
64class MachineConstantPoolValue;
65class MCSymbol;
66class raw_ostream;
67class SDNode;
68class SelectionDAG;
69class Type;
70class Value;
71
72void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr,
73 bool force = false);
74
75/// This represents a list of ValueType's that has been intern'd by
76/// a SelectionDAG. Instances of this simple value class are returned by
77/// SelectionDAG::getVTList(...).
78///
79struct SDVTList {
80 const EVT *VTs;
81 unsigned int NumVTs;
82};
83
84namespace ISD {
85
86 /// Node predicates
87
88/// If N is a BUILD_VECTOR or SPLAT_VECTOR node whose elements are all the
89/// same constant or undefined, return true and return the constant value in
90/// \p SplatValue.
91bool isConstantSplatVector(const SDNode *N, APInt &SplatValue);
92
93/// Return true if the specified node is a BUILD_VECTOR or SPLAT_VECTOR where
94/// all of the elements are ~0 or undef. If \p BuildVectorOnly is set to
95/// true, it only checks BUILD_VECTOR.
96bool isConstantSplatVectorAllOnes(const SDNode *N,
97 bool BuildVectorOnly = false);
98
99/// Return true if the specified node is a BUILD_VECTOR or SPLAT_VECTOR where
100/// all of the elements are 0 or undef. If \p BuildVectorOnly is set to true, it
101/// only checks BUILD_VECTOR.
102bool isConstantSplatVectorAllZeros(const SDNode *N,
103 bool BuildVectorOnly = false);
104
105/// Return true if the specified node is a BUILD_VECTOR where all of the
106/// elements are ~0 or undef.
107bool isBuildVectorAllOnes(const SDNode *N);
108
109/// Return true if the specified node is a BUILD_VECTOR where all of the
110/// elements are 0 or undef.
111bool isBuildVectorAllZeros(const SDNode *N);
112
113/// Return true if the specified node is a BUILD_VECTOR node of all
114/// ConstantSDNode or undef.
115bool isBuildVectorOfConstantSDNodes(const SDNode *N);
116
117/// Return true if the specified node is a BUILD_VECTOR node of all
118/// ConstantFPSDNode or undef.
119bool isBuildVectorOfConstantFPSDNodes(const SDNode *N);
120
121/// Return true if the node has at least one operand and all operands of the
122/// specified node are ISD::UNDEF.
123bool allOperandsUndef(const SDNode *N);
124
125} // end namespace ISD
126
127//===----------------------------------------------------------------------===//
128/// Unlike LLVM values, Selection DAG nodes may return multiple
129/// values as the result of a computation. Many nodes return multiple values,
130/// from loads (which define a token and a return value) to ADDC (which returns
131/// a result and a carry value), to calls (which may return an arbitrary number
132/// of values).
133///
134/// As such, each use of a SelectionDAG computation must indicate the node that
135/// computes it as well as which return value to use from that node. This pair
136/// of information is represented with the SDValue value type.
137///
138class SDValue {
139 friend struct DenseMapInfo<SDValue>;
140
141 SDNode *Node = nullptr; // The node defining the value we are using.
142 unsigned ResNo = 0; // Which return value of the node we are using.
143
144public:
145 SDValue() = default;
146 SDValue(SDNode *node, unsigned resno);
147
148 /// get the index which selects a specific result in the SDNode
149 unsigned getResNo() const { return ResNo; }
150
151 /// get the SDNode which holds the desired result
152 SDNode *getNode() const { return Node; }
153
154 /// set the SDNode
155 void setNode(SDNode *N) { Node = N; }
156
157 inline SDNode *operator->() const { return Node; }
158
159 bool operator==(const SDValue &O) const {
160 return Node == O.Node && ResNo == O.ResNo;
161 }
162 bool operator!=(const SDValue &O) const {
163 return !operator==(O);
164 }
165 bool operator<(const SDValue &O) const {
166 return std::tie(Node, ResNo) < std::tie(O.Node, O.ResNo);
167 }
168 explicit operator bool() const {
169 return Node != nullptr;
170 }
171
172 SDValue getValue(unsigned R) const {
173 return SDValue(Node, R);
174 }
175
176 /// Return true if this node is an operand of N.
177 bool isOperandOf(const SDNode *N) const;
178
179 /// Return the ValueType of the referenced return value.
180 inline EVT getValueType() const;
181
182 /// Return the simple ValueType of the referenced return value.
183 MVT getSimpleValueType() const {
184 return getValueType().getSimpleVT();
185 }
186
187 /// Returns the size of the value in bits.
188 ///
189 /// If the value type is a scalable vector type, the scalable property will
190 /// be set and the runtime size will be a positive integer multiple of the
191 /// base size.
192 TypeSize getValueSizeInBits() const {
193 return getValueType().getSizeInBits();
194 }
195
196 uint64_t getScalarValueSizeInBits() const {
197 return getValueType().getScalarType().getFixedSizeInBits();
198 }
199
200 // Forwarding methods - These forward to the corresponding methods in SDNode.
201 inline unsigned getOpcode() const;
202 inline unsigned getNumOperands() const;
203 inline const SDValue &getOperand(unsigned i) const;
204 inline uint64_t getConstantOperandVal(unsigned i) const;
205 inline const APInt &getConstantOperandAPInt(unsigned i) const;
206 inline bool isTargetMemoryOpcode() const;
207 inline bool isTargetOpcode() const;
208 inline bool isMachineOpcode() const;
209 inline bool isUndef() const;
210 inline unsigned getMachineOpcode() const;
211 inline const DebugLoc &getDebugLoc() const;
212 inline void dump() const;
213 inline void dump(const SelectionDAG *G) const;
214 inline void dumpr() const;
215 inline void dumpr(const SelectionDAG *G) const;
216
217 /// Return true if this operand (which must be a chain) reaches the
218 /// specified operand without crossing any side-effecting instructions.
219 /// In practice, this looks through token factors and non-volatile loads.
220 /// In order to remain efficient, this only
221 /// looks a couple of nodes in, it does not do an exhaustive search.
222 bool reachesChainWithoutSideEffects(SDValue Dest,
223 unsigned Depth = 2) const;
224
225 /// Return true if there are no nodes using value ResNo of Node.
226 inline bool use_empty() const;
227
228 /// Return true if there is exactly one node using value ResNo of Node.
229 inline bool hasOneUse() const;
230};
231
232template<> struct DenseMapInfo<SDValue> {
233 static inline SDValue getEmptyKey() {
234 SDValue V;
235 V.ResNo = -1U;
236 return V;
237 }
238
239 static inline SDValue getTombstoneKey() {
240 SDValue V;
241 V.ResNo = -2U;
242 return V;
243 }
244
245 static unsigned getHashValue(const SDValue &Val) {
246 return ((unsigned)((uintptr_t)Val.getNode() >> 4) ^
247 (unsigned)((uintptr_t)Val.getNode() >> 9)) + Val.getResNo();
248 }
249
250 static bool isEqual(const SDValue &LHS, const SDValue &RHS) {
251 return LHS == RHS;
252 }
253};
254
255/// Allow casting operators to work directly on
256/// SDValues as if they were SDNode*'s.
257template<> struct simplify_type<SDValue> {
258 using SimpleType = SDNode *;
259
260 static SimpleType getSimplifiedValue(SDValue &Val) {
261 return Val.getNode();
262 }
263};
264template<> struct simplify_type<const SDValue> {
265 using SimpleType = /*const*/ SDNode *;
266
267 static SimpleType getSimplifiedValue(const SDValue &Val) {
268 return Val.getNode();
269 }
270};
271
272/// Represents a use of a SDNode. This class holds an SDValue,
273/// which records the SDNode being used and the result number, a
274/// pointer to the SDNode using the value, and Next and Prev pointers,
275/// which link together all the uses of an SDNode.
276///
277class SDUse {
278 /// Val - The value being used.
279 SDValue Val;
280 /// User - The user of this value.
281 SDNode *User = nullptr;
282 /// Prev, Next - Pointers to the uses list of the SDNode referred by
283 /// this operand.
284 SDUse **Prev = nullptr;
285 SDUse *Next = nullptr;
286
287public:
288 SDUse() = default;
289 SDUse(const SDUse &U) = delete;
290 SDUse &operator=(const SDUse &) = delete;
291
292 /// Normally SDUse will just implicitly convert to an SDValue that it holds.
293 operator const SDValue&() const { return Val; }
294
295 /// If implicit conversion to SDValue doesn't work, the get() method returns
296 /// the SDValue.
297 const SDValue &get() const { return Val; }
298
299 /// This returns the SDNode that contains this Use.
300 SDNode *getUser() { return User; }
301
302 /// Get the next SDUse in the use list.
303 SDUse *getNext() const { return Next; }
304
305 /// Convenience function for get().getNode().
306 SDNode *getNode() const { return Val.getNode(); }
307 /// Convenience function for get().getResNo().
308 unsigned getResNo() const { return Val.getResNo(); }
309 /// Convenience function for get().getValueType().
310 EVT getValueType() const { return Val.getValueType(); }
311
312 /// Convenience function for get().operator==
313 bool operator==(const SDValue &V) const {
314 return Val == V;
315 }
316
317 /// Convenience function for get().operator!=
318 bool operator!=(const SDValue &V) const {
319 return Val != V;
320 }
321
322 /// Convenience function for get().operator<
323 bool operator<(const SDValue &V) const {
324 return Val < V;
325 }
326
327private:
328 friend class SelectionDAG;
329 friend class SDNode;
330 // TODO: unfriend HandleSDNode once we fix its operand handling.
331 friend class HandleSDNode;
332
333 void setUser(SDNode *p) { User = p; }
334
335 /// Remove this use from its existing use list, assign it the
336 /// given value, and add it to the new value's node's use list.
337 inline void set(const SDValue &V);
338 /// Like set, but only supports initializing a newly-allocated
339 /// SDUse with a non-null value.
340 inline void setInitial(const SDValue &V);
341 /// Like set, but only sets the Node portion of the value,
342 /// leaving the ResNo portion unmodified.
343 inline void setNode(SDNode *N);
344
345 void addToList(SDUse **List) {
346 Next = *List;
347 if (Next) Next->Prev = &Next;
348 Prev = List;
349 *List = this;
350 }
351
352 void removeFromList() {
353 *Prev = Next;
354 if (Next) Next->Prev = Prev;
355 }
356};
357
358/// simplify_type specializations - Allow casting operators to work directly on
359/// SDValues as if they were SDNode*'s.
360template<> struct simplify_type<SDUse> {
361 using SimpleType = SDNode *;
362
363 static SimpleType getSimplifiedValue(SDUse &Val) {
364 return Val.getNode();
365 }
366};
367
368/// These are IR-level optimization flags that may be propagated to SDNodes.
369/// TODO: This data structure should be shared by the IR optimizer and the
370/// the backend.
371struct SDNodeFlags {
372private:
373 bool NoUnsignedWrap : 1;
374 bool NoSignedWrap : 1;
375 bool Exact : 1;
376 bool NoNaNs : 1;
377 bool NoInfs : 1;
378 bool NoSignedZeros : 1;
379 bool AllowReciprocal : 1;
380 bool AllowContract : 1;
381 bool ApproximateFuncs : 1;
382 bool AllowReassociation : 1;
383
384 // We assume instructions do not raise floating-point exceptions by default,
385 // and only those marked explicitly may do so. We could choose to represent
386 // this via a positive "FPExcept" flags like on the MI level, but having a
387 // negative "NoFPExcept" flag here (that defaults to true) makes the flag
388 // intersection logic more straightforward.
389 bool NoFPExcept : 1;
390
391public:
392 /// Default constructor turns off all optimization flags.
393 SDNodeFlags()
394 : NoUnsignedWrap(false), NoSignedWrap(false), Exact(false), NoNaNs(false),
395 NoInfs(false), NoSignedZeros(false), AllowReciprocal(false),
396 AllowContract(false), ApproximateFuncs(false),
397 AllowReassociation(false), NoFPExcept(false) {}
398
399 /// Propagate the fast-math-flags from an IR FPMathOperator.
400 void copyFMF(const FPMathOperator &FPMO) {
401 setNoNaNs(FPMO.hasNoNaNs());
402 setNoInfs(FPMO.hasNoInfs());
403 setNoSignedZeros(FPMO.hasNoSignedZeros());
404 setAllowReciprocal(FPMO.hasAllowReciprocal());
405 setAllowContract(FPMO.hasAllowContract());
406 setApproximateFuncs(FPMO.hasApproxFunc());
407 setAllowReassociation(FPMO.hasAllowReassoc());
408 }
409
410 // These are mutators for each flag.
411 void setNoUnsignedWrap(bool b) { NoUnsignedWrap = b; }
412 void setNoSignedWrap(bool b) { NoSignedWrap = b; }
413 void setExact(bool b) { Exact = b; }
414 void setNoNaNs(bool b) { NoNaNs = b; }
415 void setNoInfs(bool b) { NoInfs = b; }
416 void setNoSignedZeros(bool b) { NoSignedZeros = b; }
417 void setAllowReciprocal(bool b) { AllowReciprocal = b; }
418 void setAllowContract(bool b) { AllowContract = b; }
419 void setApproximateFuncs(bool b) { ApproximateFuncs = b; }
420 void setAllowReassociation(bool b) { AllowReassociation = b; }
421 void setNoFPExcept(bool b) { NoFPExcept = b; }
422
423 // These are accessors for each flag.
424 bool hasNoUnsignedWrap() const { return NoUnsignedWrap; }
425 bool hasNoSignedWrap() const { return NoSignedWrap; }
426 bool hasExact() const { return Exact; }
427 bool hasNoNaNs() const { return NoNaNs; }
428 bool hasNoInfs() const { return NoInfs; }
429 bool hasNoSignedZeros() const { return NoSignedZeros; }
430 bool hasAllowReciprocal() const { return AllowReciprocal; }
431 bool hasAllowContract() const { return AllowContract; }
432 bool hasApproximateFuncs() const { return ApproximateFuncs; }
433 bool hasAllowReassociation() const { return AllowReassociation; }
434 bool hasNoFPExcept() const { return NoFPExcept; }
435
436 /// Clear any flags in this flag set that aren't also set in Flags. All
437 /// flags will be cleared if Flags are undefined.
438 void intersectWith(const SDNodeFlags Flags) {
439 NoUnsignedWrap &= Flags.NoUnsignedWrap;
440 NoSignedWrap &= Flags.NoSignedWrap;
441 Exact &= Flags.Exact;
442 NoNaNs &= Flags.NoNaNs;
443 NoInfs &= Flags.NoInfs;
444 NoSignedZeros &= Flags.NoSignedZeros;
445 AllowReciprocal &= Flags.AllowReciprocal;
446 AllowContract &= Flags.AllowContract;
447 ApproximateFuncs &= Flags.ApproximateFuncs;
448 AllowReassociation &= Flags.AllowReassociation;
449 NoFPExcept &= Flags.NoFPExcept;
450 }
451};
452
453/// Represents one node in the SelectionDAG.
454///
455class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
456private:
457 /// The operation that this node performs.
458 int16_t NodeType;
459
460protected:
461 // We define a set of mini-helper classes to help us interpret the bits in our
462 // SubclassData. These are designed to fit within a uint16_t so they pack
463 // with NodeType.
464
465#if defined(_AIX) && (!defined(__GNUC__4) || defined(__clang__1))
466// Except for GCC; by default, AIX compilers store bit-fields in 4-byte words
467// and give the `pack` pragma push semantics.
468#define BEGIN_TWO_BYTE_PACK() _Pragma("pack(2)")pack(2)
469#define END_TWO_BYTE_PACK() _Pragma("pack(pop)")pack(pop)
470#else
471#define BEGIN_TWO_BYTE_PACK()
472#define END_TWO_BYTE_PACK()
473#endif
474
475BEGIN_TWO_BYTE_PACK()
476 class SDNodeBitfields {
477 friend class SDNode;
478 friend class MemIntrinsicSDNode;
479 friend class MemSDNode;
480 friend class SelectionDAG;
481
482 uint16_t HasDebugValue : 1;
483 uint16_t IsMemIntrinsic : 1;
484 uint16_t IsDivergent : 1;
485 };
486 enum { NumSDNodeBits = 3 };
487
488 class ConstantSDNodeBitfields {
489 friend class ConstantSDNode;
490
491 uint16_t : NumSDNodeBits;
492
493 uint16_t IsOpaque : 1;
494 };
495
496 class MemSDNodeBitfields {
497 friend class MemSDNode;
498 friend class MemIntrinsicSDNode;
499 friend class AtomicSDNode;
500
501 uint16_t : NumSDNodeBits;
502
503 uint16_t IsVolatile : 1;
504 uint16_t IsNonTemporal : 1;
505 uint16_t IsDereferenceable : 1;
506 uint16_t IsInvariant : 1;
507 };
508 enum { NumMemSDNodeBits = NumSDNodeBits + 4 };
509
510 class LSBaseSDNodeBitfields {
511 friend class LSBaseSDNode;
512 friend class MaskedLoadStoreSDNode;
513 friend class MaskedGatherScatterSDNode;
514
515 uint16_t : NumMemSDNodeBits;
516
517 // This storage is shared between disparate class hierarchies to hold an
518 // enumeration specific to the class hierarchy in use.
519 // LSBaseSDNode => enum ISD::MemIndexedMode
520 // MaskedLoadStoreBaseSDNode => enum ISD::MemIndexedMode
521 // MaskedGatherScatterSDNode => enum ISD::MemIndexType
522 uint16_t AddressingMode : 3;
523 };
524 enum { NumLSBaseSDNodeBits = NumMemSDNodeBits + 3 };
525
526 class LoadSDNodeBitfields {
527 friend class LoadSDNode;
528 friend class MaskedLoadSDNode;
529 friend class MaskedGatherSDNode;
530
531 uint16_t : NumLSBaseSDNodeBits;
532
533 uint16_t ExtTy : 2; // enum ISD::LoadExtType
534 uint16_t IsExpanding : 1;
535 };
536
537 class StoreSDNodeBitfields {
538 friend class StoreSDNode;
539 friend class MaskedStoreSDNode;
540 friend class MaskedScatterSDNode;
541
542 uint16_t : NumLSBaseSDNodeBits;
543
544 uint16_t IsTruncating : 1;
545 uint16_t IsCompressing : 1;
546 };
547
548 union {
549 char RawSDNodeBits[sizeof(uint16_t)];
550 SDNodeBitfields SDNodeBits;
551 ConstantSDNodeBitfields ConstantSDNodeBits;
552 MemSDNodeBitfields MemSDNodeBits;
553 LSBaseSDNodeBitfields LSBaseSDNodeBits;
554 LoadSDNodeBitfields LoadSDNodeBits;
555 StoreSDNodeBitfields StoreSDNodeBits;
556 };
557END_TWO_BYTE_PACK()
558#undef BEGIN_TWO_BYTE_PACK
559#undef END_TWO_BYTE_PACK
560
561 // RawSDNodeBits must cover the entirety of the union. This means that all of
562 // the union's members must have size <= RawSDNodeBits. We write the RHS as
563 // "2" instead of sizeof(RawSDNodeBits) because MSVC can't handle the latter.
564 static_assert(sizeof(SDNodeBitfields) <= 2, "field too wide");
565 static_assert(sizeof(ConstantSDNodeBitfields) <= 2, "field too wide");
566 static_assert(sizeof(MemSDNodeBitfields) <= 2, "field too wide");
567 static_assert(sizeof(LSBaseSDNodeBitfields) <= 2, "field too wide");
568 static_assert(sizeof(LoadSDNodeBitfields) <= 2, "field too wide");
569 static_assert(sizeof(StoreSDNodeBitfields) <= 2, "field too wide");
570
571private:
572 friend class SelectionDAG;
573 // TODO: unfriend HandleSDNode once we fix its operand handling.
574 friend class HandleSDNode;
575
576 /// Unique id per SDNode in the DAG.
577 int NodeId = -1;
578
579 /// The values that are used by this operation.
580 SDUse *OperandList = nullptr;
581
582 /// The types of the values this node defines. SDNode's may
583 /// define multiple values simultaneously.
584 const EVT *ValueList;
585
586 /// List of uses for this SDNode.
587 SDUse *UseList = nullptr;
588
589 /// The number of entries in the Operand/Value list.
590 unsigned short NumOperands = 0;
591 unsigned short NumValues;
592
593 // The ordering of the SDNodes. It roughly corresponds to the ordering of the
594 // original LLVM instructions.
595 // This is used for turning off scheduling, because we'll forgo
596 // the normal scheduling algorithms and output the instructions according to
597 // this ordering.
598 unsigned IROrder;
599
600 /// Source line information.
601 DebugLoc debugLoc;
602
603 /// Return a pointer to the specified value type.
604 static const EVT *getValueTypeList(EVT VT);
605
606 SDNodeFlags Flags;
607
608public:
609 /// Unique and persistent id per SDNode in the DAG.
610 /// Used for debug printing.
611 uint16_t PersistentId;
612
613 //===--------------------------------------------------------------------===//
614 // Accessors
615 //
616
617 /// Return the SelectionDAG opcode value for this node. For
618 /// pre-isel nodes (those for which isMachineOpcode returns false), these
619 /// are the opcode values in the ISD and <target>ISD namespaces. For
620 /// post-isel opcodes, see getMachineOpcode.
621 unsigned getOpcode() const { return (unsigned short)NodeType; }
622
623 /// Test if this node has a target-specific opcode (in the
624 /// \<target\>ISD namespace).
625 bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
626
627 /// Test if this node has a target-specific opcode that may raise
628 /// FP exceptions (in the \<target\>ISD namespace and greater than
629 /// FIRST_TARGET_STRICTFP_OPCODE). Note that all target memory
630 /// opcode are currently automatically considered to possibly raise
631 /// FP exceptions as well.
632 bool isTargetStrictFPOpcode() const {
633 return NodeType >= ISD::FIRST_TARGET_STRICTFP_OPCODE;
634 }
635
636 /// Test if this node has a target-specific
637 /// memory-referencing opcode (in the \<target\>ISD namespace and
638 /// greater than FIRST_TARGET_MEMORY_OPCODE).
639 bool isTargetMemoryOpcode() const {
640 return NodeType >= ISD::FIRST_TARGET_MEMORY_OPCODE;
641 }
642
643 /// Return true if the type of the node type undefined.
644 bool isUndef() const { return NodeType == ISD::UNDEF; }
645
646 /// Test if this node is a memory intrinsic (with valid pointer information).
647 /// INTRINSIC_W_CHAIN and INTRINSIC_VOID nodes are sometimes created for
648 /// non-memory intrinsics (with chains) that are not really instances of
649 /// MemSDNode. For such nodes, we need some extra state to determine the
650 /// proper classof relationship.
651 bool isMemIntrinsic() const {
652 return (NodeType == ISD::INTRINSIC_W_CHAIN ||
653 NodeType == ISD::INTRINSIC_VOID) &&
654 SDNodeBits.IsMemIntrinsic;
655 }
656
657 /// Test if this node is a strict floating point pseudo-op.
658 bool isStrictFPOpcode() {
659 switch (NodeType) {
660 default:
661 return false;
662 case ISD::STRICT_FP16_TO_FP:
663 case ISD::STRICT_FP_TO_FP16:
664#define DAG_INSTRUCTION(NAME, NARG, ROUND_MODE, INTRINSIC, DAGN) \
665 case ISD::STRICT_##DAGN:
666#include "llvm/IR/ConstrainedOps.def"
667 return true;
668 }
669 }
670
671 /// Test if this node has a post-isel opcode, directly
672 /// corresponding to a MachineInstr opcode.
673 bool isMachineOpcode() const { return NodeType < 0; }
674
675 /// This may only be called if isMachineOpcode returns
676 /// true. It returns the MachineInstr opcode value that the node's opcode
677 /// corresponds to.
678 unsigned getMachineOpcode() const {
679 assert(isMachineOpcode() && "Not a MachineInstr opcode!")(static_cast <bool> (isMachineOpcode() && "Not a MachineInstr opcode!"
) ? void (0) : __assert_fail ("isMachineOpcode() && \"Not a MachineInstr opcode!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 679, __extension__ __PRETTY_FUNCTION__))
;
680 return ~NodeType;
681 }
682
683 bool getHasDebugValue() const { return SDNodeBits.HasDebugValue; }
684 void setHasDebugValue(bool b) { SDNodeBits.HasDebugValue = b; }
685
686 bool isDivergent() const { return SDNodeBits.IsDivergent; }
687
688 /// Return true if there are no uses of this node.
689 bool use_empty() const { return UseList == nullptr; }
690
691 /// Return true if there is exactly one use of this node.
692 bool hasOneUse() const { return hasSingleElement(uses()); }
693
694 /// Return the number of uses of this node. This method takes
695 /// time proportional to the number of uses.
696 size_t use_size() const { return std::distance(use_begin(), use_end()); }
697
698 /// Return the unique node id.
699 int getNodeId() const { return NodeId; }
700
701 /// Set unique node id.
702 void setNodeId(int Id) { NodeId = Id; }
703
704 /// Return the node ordering.
705 unsigned getIROrder() const { return IROrder; }
706
707 /// Set the node ordering.
708 void setIROrder(unsigned Order) { IROrder = Order; }
709
710 /// Return the source location info.
711 const DebugLoc &getDebugLoc() const { return debugLoc; }
712
713 /// Set source location info. Try to avoid this, putting
714 /// it in the constructor is preferable.
715 void setDebugLoc(DebugLoc dl) { debugLoc = std::move(dl); }
716
717 /// This class provides iterator support for SDUse
718 /// operands that use a specific SDNode.
719 class use_iterator {
720 friend class SDNode;
721
722 SDUse *Op = nullptr;
723
724 explicit use_iterator(SDUse *op) : Op(op) {}
725
726 public:
727 using iterator_category = std::forward_iterator_tag;
728 using value_type = SDUse;
729 using difference_type = std::ptrdiff_t;
730 using pointer = value_type *;
731 using reference = value_type &;
732
733 use_iterator() = default;
734 use_iterator(const use_iterator &I) : Op(I.Op) {}
735
736 bool operator==(const use_iterator &x) const {
737 return Op == x.Op;
738 }
739 bool operator!=(const use_iterator &x) const {
740 return !operator==(x);
741 }
742
743 /// Return true if this iterator is at the end of uses list.
744 bool atEnd() const { return Op == nullptr; }
745
746 // Iterator traversal: forward iteration only.
747 use_iterator &operator++() { // Preincrement
748 assert(Op && "Cannot increment end iterator!")(static_cast <bool> (Op && "Cannot increment end iterator!"
) ? void (0) : __assert_fail ("Op && \"Cannot increment end iterator!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 748, __extension__ __PRETTY_FUNCTION__))
;
749 Op = Op->getNext();
750 return *this;
751 }
752
753 use_iterator operator++(int) { // Postincrement
754 use_iterator tmp = *this; ++*this; return tmp;
755 }
756
757 /// Retrieve a pointer to the current user node.
758 SDNode *operator*() const {
759 assert(Op && "Cannot dereference end iterator!")(static_cast <bool> (Op && "Cannot dereference end iterator!"
) ? void (0) : __assert_fail ("Op && \"Cannot dereference end iterator!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 759, __extension__ __PRETTY_FUNCTION__))
;
760 return Op->getUser();
761 }
762
763 SDNode *operator->() const { return operator*(); }
764
765 SDUse &getUse() const { return *Op; }
766
767 /// Retrieve the operand # of this use in its user.
768 unsigned getOperandNo() const {
769 assert(Op && "Cannot dereference end iterator!")(static_cast <bool> (Op && "Cannot dereference end iterator!"
) ? void (0) : __assert_fail ("Op && \"Cannot dereference end iterator!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 769, __extension__ __PRETTY_FUNCTION__))
;
770 return (unsigned)(Op - Op->getUser()->OperandList);
771 }
772 };
773
774 /// Provide iteration support to walk over all uses of an SDNode.
775 use_iterator use_begin() const {
776 return use_iterator(UseList);
777 }
778
779 static use_iterator use_end() { return use_iterator(nullptr); }
780
781 inline iterator_range<use_iterator> uses() {
782 return make_range(use_begin(), use_end());
783 }
784 inline iterator_range<use_iterator> uses() const {
785 return make_range(use_begin(), use_end());
786 }
787
788 /// Return true if there are exactly NUSES uses of the indicated value.
789 /// This method ignores uses of other values defined by this operation.
790 bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
791
792 /// Return true if there are any use of the indicated value.
793 /// This method ignores uses of other values defined by this operation.
794 bool hasAnyUseOfValue(unsigned Value) const;
795
796 /// Return true if this node is the only use of N.
797 bool isOnlyUserOf(const SDNode *N) const;
798
799 /// Return true if this node is an operand of N.
800 bool isOperandOf(const SDNode *N) const;
801
802 /// Return true if this node is a predecessor of N.
803 /// NOTE: Implemented on top of hasPredecessor and every bit as
804 /// expensive. Use carefully.
805 bool isPredecessorOf(const SDNode *N) const {
806 return N->hasPredecessor(this);
807 }
808
809 /// Return true if N is a predecessor of this node.
810 /// N is either an operand of this node, or can be reached by recursively
811 /// traversing up the operands.
812 /// NOTE: This is an expensive method. Use it carefully.
813 bool hasPredecessor(const SDNode *N) const;
814
815 /// Returns true if N is a predecessor of any node in Worklist. This
816 /// helper keeps Visited and Worklist sets externally to allow unions
817 /// searches to be performed in parallel, caching of results across
818 /// queries and incremental addition to Worklist. Stops early if N is
819 /// found but will resume. Remember to clear Visited and Worklists
820 /// if DAG changes. MaxSteps gives a maximum number of nodes to visit before
821 /// giving up. The TopologicalPrune flag signals that positive NodeIds are
822 /// topologically ordered (Operands have strictly smaller node id) and search
823 /// can be pruned leveraging this.
824 static bool hasPredecessorHelper(const SDNode *N,
825 SmallPtrSetImpl<const SDNode *> &Visited,
826 SmallVectorImpl<const SDNode *> &Worklist,
827 unsigned int MaxSteps = 0,
828 bool TopologicalPrune = false) {
829 SmallVector<const SDNode *, 8> DeferredNodes;
830 if (Visited.count(N))
831 return true;
832
833 // Node Id's are assigned in three places: As a topological
834 // ordering (> 0), during legalization (results in values set to
835 // 0), new nodes (set to -1). If N has a topolgical id then we
836 // know that all nodes with ids smaller than it cannot be
837 // successors and we need not check them. Filter out all node
838 // that can't be matches. We add them to the worklist before exit
839 // in case of multiple calls. Note that during selection the topological id
840 // may be violated if a node's predecessor is selected before it. We mark
841 // this at selection negating the id of unselected successors and
842 // restricting topological pruning to positive ids.
843
844 int NId = N->getNodeId();
845 // If we Invalidated the Id, reconstruct original NId.
846 if (NId < -1)
847 NId = -(NId + 1);
848
849 bool Found = false;
850 while (!Worklist.empty()) {
851 const SDNode *M = Worklist.pop_back_val();
852 int MId = M->getNodeId();
853 if (TopologicalPrune && M->getOpcode() != ISD::TokenFactor && (NId > 0) &&
854 (MId > 0) && (MId < NId)) {
855 DeferredNodes.push_back(M);
856 continue;
857 }
858 for (const SDValue &OpV : M->op_values()) {
859 SDNode *Op = OpV.getNode();
860 if (Visited.insert(Op).second)
861 Worklist.push_back(Op);
862 if (Op == N)
863 Found = true;
864 }
865 if (Found)
866 break;
867 if (MaxSteps != 0 && Visited.size() >= MaxSteps)
868 break;
869 }
870 // Push deferred nodes back on worklist.
871 Worklist.append(DeferredNodes.begin(), DeferredNodes.end());
872 // If we bailed early, conservatively return found.
873 if (MaxSteps != 0 && Visited.size() >= MaxSteps)
874 return true;
875 return Found;
876 }
877
878 /// Return true if all the users of N are contained in Nodes.
879 /// NOTE: Requires at least one match, but doesn't require them all.
880 static bool areOnlyUsersOf(ArrayRef<const SDNode *> Nodes, const SDNode *N);
881
882 /// Return the number of values used by this operation.
883 unsigned getNumOperands() const { return NumOperands; }
884
885 /// Return the maximum number of operands that a SDNode can hold.
886 static constexpr size_t getMaxNumOperands() {
887 return std::numeric_limits<decltype(SDNode::NumOperands)>::max();
888 }
889
890 /// Helper method returns the integer value of a ConstantSDNode operand.
891 inline uint64_t getConstantOperandVal(unsigned Num) const;
892
893 /// Helper method returns the APInt of a ConstantSDNode operand.
894 inline const APInt &getConstantOperandAPInt(unsigned Num) const;
895
896 const SDValue &getOperand(unsigned Num) const {
897 assert(Num < NumOperands && "Invalid child # of SDNode!")(static_cast <bool> (Num < NumOperands && "Invalid child # of SDNode!"
) ? void (0) : __assert_fail ("Num < NumOperands && \"Invalid child # of SDNode!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 897, __extension__ __PRETTY_FUNCTION__))
;
898 return OperandList[Num];
899 }
900
901 using op_iterator = SDUse *;
902
903 op_iterator op_begin() const { return OperandList; }
904 op_iterator op_end() const { return OperandList+NumOperands; }
905 ArrayRef<SDUse> ops() const { return makeArrayRef(op_begin(), op_end()); }
906
907 /// Iterator for directly iterating over the operand SDValue's.
908 struct value_op_iterator
909 : iterator_adaptor_base<value_op_iterator, op_iterator,
910 std::random_access_iterator_tag, SDValue,
911 ptrdiff_t, value_op_iterator *,
912 value_op_iterator *> {
913 explicit value_op_iterator(SDUse *U = nullptr)
914 : iterator_adaptor_base(U) {}
915
916 const SDValue &operator*() const { return I->get(); }
917 };
918
919 iterator_range<value_op_iterator> op_values() const {
920 return make_range(value_op_iterator(op_begin()),
921 value_op_iterator(op_end()));
922 }
923
924 SDVTList getVTList() const {
925 SDVTList X = { ValueList, NumValues };
926 return X;
927 }
928
929 /// If this node has a glue operand, return the node
930 /// to which the glue operand points. Otherwise return NULL.
931 SDNode *getGluedNode() const {
932 if (getNumOperands() != 0 &&
933 getOperand(getNumOperands()-1).getValueType() == MVT::Glue)
934 return getOperand(getNumOperands()-1).getNode();
935 return nullptr;
936 }
937
938 /// If this node has a glue value with a user, return
939 /// the user (there is at most one). Otherwise return NULL.
940 SDNode *getGluedUser() const {
941 for (use_iterator UI = use_begin(), UE = use_end(); UI != UE; ++UI)
942 if (UI.getUse().get().getValueType() == MVT::Glue)
943 return *UI;
944 return nullptr;
945 }
946
947 SDNodeFlags getFlags() const { return Flags; }
948 void setFlags(SDNodeFlags NewFlags) { Flags = NewFlags; }
949
950 /// Clear any flags in this node that aren't also set in Flags.
951 /// If Flags is not in a defined state then this has no effect.
952 void intersectFlagsWith(const SDNodeFlags Flags);
953
954 /// Return the number of values defined/returned by this operator.
955 unsigned getNumValues() const { return NumValues; }
956
957 /// Return the type of a specified result.
958 EVT getValueType(unsigned ResNo) const {
959 assert(ResNo < NumValues && "Illegal result number!")(static_cast <bool> (ResNo < NumValues && "Illegal result number!"
) ? void (0) : __assert_fail ("ResNo < NumValues && \"Illegal result number!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 959, __extension__ __PRETTY_FUNCTION__))
;
960 return ValueList[ResNo];
961 }
962
963 /// Return the type of a specified result as a simple type.
964 MVT getSimpleValueType(unsigned ResNo) const {
965 return getValueType(ResNo).getSimpleVT();
966 }
967
968 /// Returns MVT::getSizeInBits(getValueType(ResNo)).
969 ///
970 /// If the value type is a scalable vector type, the scalable property will
971 /// be set and the runtime size will be a positive integer multiple of the
972 /// base size.
973 TypeSize getValueSizeInBits(unsigned ResNo) const {
974 return getValueType(ResNo).getSizeInBits();
975 }
976
977 using value_iterator = const EVT *;
978
979 value_iterator value_begin() const { return ValueList; }
980 value_iterator value_end() const { return ValueList+NumValues; }
981 iterator_range<value_iterator> values() const {
982 return llvm::make_range(value_begin(), value_end());
983 }
984
985 /// Return the opcode of this operation for printing.
986 std::string getOperationName(const SelectionDAG *G = nullptr) const;
987 static const char* getIndexedModeName(ISD::MemIndexedMode AM);
988 void print_types(raw_ostream &OS, const SelectionDAG *G) const;
989 void print_details(raw_ostream &OS, const SelectionDAG *G) const;
990 void print(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
991 void printr(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
992
993 /// Print a SelectionDAG node and all children down to
994 /// the leaves. The given SelectionDAG allows target-specific nodes
995 /// to be printed in human-readable form. Unlike printr, this will
996 /// print the whole DAG, including children that appear multiple
997 /// times.
998 ///
999 void printrFull(raw_ostream &O, const SelectionDAG *G = nullptr) const;
1000
1001 /// Print a SelectionDAG node and children up to
1002 /// depth "depth." The given SelectionDAG allows target-specific
1003 /// nodes to be printed in human-readable form. Unlike printr, this
1004 /// will print children that appear multiple times wherever they are
1005 /// used.
1006 ///
1007 void printrWithDepth(raw_ostream &O, const SelectionDAG *G = nullptr,
1008 unsigned depth = 100) const;
1009
1010 /// Dump this node, for debugging.
1011 void dump() const;
1012
1013 /// Dump (recursively) this node and its use-def subgraph.
1014 void dumpr() const;
1015
1016 /// Dump this node, for debugging.
1017 /// The given SelectionDAG allows target-specific nodes to be printed
1018 /// in human-readable form.
1019 void dump(const SelectionDAG *G) const;
1020
1021 /// Dump (recursively) this node and its use-def subgraph.
1022 /// The given SelectionDAG allows target-specific nodes to be printed
1023 /// in human-readable form.
1024 void dumpr(const SelectionDAG *G) const;
1025
1026 /// printrFull to dbgs(). The given SelectionDAG allows
1027 /// target-specific nodes to be printed in human-readable form.
1028 /// Unlike dumpr, this will print the whole DAG, including children
1029 /// that appear multiple times.
1030 void dumprFull(const SelectionDAG *G = nullptr) const;
1031
1032 /// printrWithDepth to dbgs(). The given
1033 /// SelectionDAG allows target-specific nodes to be printed in
1034 /// human-readable form. Unlike dumpr, this will print children
1035 /// that appear multiple times wherever they are used.
1036 ///
1037 void dumprWithDepth(const SelectionDAG *G = nullptr,
1038 unsigned depth = 100) const;
1039
1040 /// Gather unique data for the node.
1041 void Profile(FoldingSetNodeID &ID) const;
1042
1043 /// This method should only be used by the SDUse class.
1044 void addUse(SDUse &U) { U.addToList(&UseList); }
1045
1046protected:
1047 static SDVTList getSDVTList(EVT VT) {
1048 SDVTList Ret = { getValueTypeList(VT), 1 };
1049 return Ret;
1050 }
1051
1052 /// Create an SDNode.
1053 ///
1054 /// SDNodes are created without any operands, and never own the operand
1055 /// storage. To add operands, see SelectionDAG::createOperands.
1056 SDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs)
1057 : NodeType(Opc), ValueList(VTs.VTs), NumValues(VTs.NumVTs),
1058 IROrder(Order), debugLoc(std::move(dl)) {
1059 memset(&RawSDNodeBits, 0, sizeof(RawSDNodeBits));
1060 assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor")(static_cast <bool> (debugLoc.hasTrivialDestructor() &&
"Expected trivial destructor") ? void (0) : __assert_fail ("debugLoc.hasTrivialDestructor() && \"Expected trivial destructor\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1060, __extension__ __PRETTY_FUNCTION__))
;
1061 assert(NumValues == VTs.NumVTs &&(static_cast <bool> (NumValues == VTs.NumVTs &&
"NumValues wasn't wide enough for its operands!") ? void (0)
: __assert_fail ("NumValues == VTs.NumVTs && \"NumValues wasn't wide enough for its operands!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1062, __extension__ __PRETTY_FUNCTION__))
1062 "NumValues wasn't wide enough for its operands!")(static_cast <bool> (NumValues == VTs.NumVTs &&
"NumValues wasn't wide enough for its operands!") ? void (0)
: __assert_fail ("NumValues == VTs.NumVTs && \"NumValues wasn't wide enough for its operands!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1062, __extension__ __PRETTY_FUNCTION__))
;
1063 }
1064
1065 /// Release the operands and set this node to have zero operands.
1066 void DropOperands();
1067};
1068
1069/// Wrapper class for IR location info (IR ordering and DebugLoc) to be passed
1070/// into SDNode creation functions.
1071/// When an SDNode is created from the DAGBuilder, the DebugLoc is extracted
1072/// from the original Instruction, and IROrder is the ordinal position of
1073/// the instruction.
1074/// When an SDNode is created after the DAG is being built, both DebugLoc and
1075/// the IROrder are propagated from the original SDNode.
1076/// So SDLoc class provides two constructors besides the default one, one to
1077/// be used by the DAGBuilder, the other to be used by others.
1078class SDLoc {
1079private:
1080 DebugLoc DL;
1081 int IROrder = 0;
1082
1083public:
1084 SDLoc() = default;
1085 SDLoc(const SDNode *N) : DL(N->getDebugLoc()), IROrder(N->getIROrder()) {}
1086 SDLoc(const SDValue V) : SDLoc(V.getNode()) {}
1087 SDLoc(const Instruction *I, int Order) : IROrder(Order) {
1088 assert(Order >= 0 && "bad IROrder")(static_cast <bool> (Order >= 0 && "bad IROrder"
) ? void (0) : __assert_fail ("Order >= 0 && \"bad IROrder\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1088, __extension__ __PRETTY_FUNCTION__))
;
1089 if (I)
1090 DL = I->getDebugLoc();
1091 }
1092
1093 unsigned getIROrder() const { return IROrder; }
1094 const DebugLoc &getDebugLoc() const { return DL; }
1095};
1096
1097// Define inline functions from the SDValue class.
1098
1099inline SDValue::SDValue(SDNode *node, unsigned resno)
1100 : Node(node), ResNo(resno) {
1101 // Explicitly check for !ResNo to avoid use-after-free, because there are
1102 // callers that use SDValue(N, 0) with a deleted N to indicate successful
1103 // combines.
1104 assert((!Node || !ResNo || ResNo < Node->getNumValues()) &&(static_cast <bool> ((!Node || !ResNo || ResNo < Node
->getNumValues()) && "Invalid result number for the given node!"
) ? void (0) : __assert_fail ("(!Node || !ResNo || ResNo < Node->getNumValues()) && \"Invalid result number for the given node!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1105, __extension__ __PRETTY_FUNCTION__))
1105 "Invalid result number for the given node!")(static_cast <bool> ((!Node || !ResNo || ResNo < Node
->getNumValues()) && "Invalid result number for the given node!"
) ? void (0) : __assert_fail ("(!Node || !ResNo || ResNo < Node->getNumValues()) && \"Invalid result number for the given node!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1105, __extension__ __PRETTY_FUNCTION__))
;
1106 assert(ResNo < -2U && "Cannot use result numbers reserved for DenseMaps.")(static_cast <bool> (ResNo < -2U && "Cannot use result numbers reserved for DenseMaps."
) ? void (0) : __assert_fail ("ResNo < -2U && \"Cannot use result numbers reserved for DenseMaps.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1106, __extension__ __PRETTY_FUNCTION__))
;
1107}
1108
1109inline unsigned SDValue::getOpcode() const {
1110 return Node->getOpcode();
1111}
1112
1113inline EVT SDValue::getValueType() const {
1114 return Node->getValueType(ResNo);
1115}
1116
1117inline unsigned SDValue::getNumOperands() const {
1118 return Node->getNumOperands();
1119}
1120
1121inline const SDValue &SDValue::getOperand(unsigned i) const {
1122 return Node->getOperand(i);
1123}
1124
1125inline uint64_t SDValue::getConstantOperandVal(unsigned i) const {
1126 return Node->getConstantOperandVal(i);
1127}
1128
1129inline const APInt &SDValue::getConstantOperandAPInt(unsigned i) const {
1130 return Node->getConstantOperandAPInt(i);
1131}
1132
1133inline bool SDValue::isTargetOpcode() const {
1134 return Node->isTargetOpcode();
1135}
1136
1137inline bool SDValue::isTargetMemoryOpcode() const {
1138 return Node->isTargetMemoryOpcode();
1139}
1140
1141inline bool SDValue::isMachineOpcode() const {
1142 return Node->isMachineOpcode();
1143}
1144
1145inline unsigned SDValue::getMachineOpcode() const {
1146 return Node->getMachineOpcode();
1147}
1148
1149inline bool SDValue::isUndef() const {
1150 return Node->isUndef();
1151}
1152
1153inline bool SDValue::use_empty() const {
1154 return !Node->hasAnyUseOfValue(ResNo);
1155}
1156
1157inline bool SDValue::hasOneUse() const {
1158 return Node->hasNUsesOfValue(1, ResNo);
1159}
1160
1161inline const DebugLoc &SDValue::getDebugLoc() const {
1162 return Node->getDebugLoc();
1163}
1164
1165inline void SDValue::dump() const {
1166 return Node->dump();
1167}
1168
1169inline void SDValue::dump(const SelectionDAG *G) const {
1170 return Node->dump(G);
1171}
1172
1173inline void SDValue::dumpr() const {
1174 return Node->dumpr();
1175}
1176
1177inline void SDValue::dumpr(const SelectionDAG *G) const {
1178 return Node->dumpr(G);
1179}
1180
1181// Define inline functions from the SDUse class.
1182
1183inline void SDUse::set(const SDValue &V) {
1184 if (Val.getNode()) removeFromList();
1185 Val = V;
1186 if (V.getNode()) V.getNode()->addUse(*this);
1187}
1188
1189inline void SDUse::setInitial(const SDValue &V) {
1190 Val = V;
1191 V.getNode()->addUse(*this);
1192}
1193
1194inline void SDUse::setNode(SDNode *N) {
1195 if (Val.getNode()) removeFromList();
1196 Val.setNode(N);
1197 if (N) N->addUse(*this);
1198}
1199
1200/// This class is used to form a handle around another node that
1201/// is persistent and is updated across invocations of replaceAllUsesWith on its
1202/// operand. This node should be directly created by end-users and not added to
1203/// the AllNodes list.
1204class HandleSDNode : public SDNode {
1205 SDUse Op;
1206
1207public:
1208 explicit HandleSDNode(SDValue X)
1209 : SDNode(ISD::HANDLENODE, 0, DebugLoc(), getSDVTList(MVT::Other)) {
1210 // HandleSDNodes are never inserted into the DAG, so they won't be
1211 // auto-numbered. Use ID 65535 as a sentinel.
1212 PersistentId = 0xffff;
1213
1214 // Manually set up the operand list. This node type is special in that it's
1215 // always stack allocated and SelectionDAG does not manage its operands.
1216 // TODO: This should either (a) not be in the SDNode hierarchy, or (b) not
1217 // be so special.
1218 Op.setUser(this);
1219 Op.setInitial(X);
1220 NumOperands = 1;
1221 OperandList = &Op;
1222 }
1223 ~HandleSDNode();
1224
1225 const SDValue &getValue() const { return Op; }
1226};
1227
1228class AddrSpaceCastSDNode : public SDNode {
1229private:
1230 unsigned SrcAddrSpace;
1231 unsigned DestAddrSpace;
1232
1233public:
1234 AddrSpaceCastSDNode(unsigned Order, const DebugLoc &dl, EVT VT,
1235 unsigned SrcAS, unsigned DestAS);
1236
1237 unsigned getSrcAddressSpace() const { return SrcAddrSpace; }
1238 unsigned getDestAddressSpace() const { return DestAddrSpace; }
1239
1240 static bool classof(const SDNode *N) {
1241 return N->getOpcode() == ISD::ADDRSPACECAST;
1242 }
1243};
1244
1245/// This is an abstract virtual class for memory operations.
1246class MemSDNode : public SDNode {
1247private:
1248 // VT of in-memory value.
1249 EVT MemoryVT;
1250
1251protected:
1252 /// Memory reference information.
1253 MachineMemOperand *MMO;
1254
1255public:
1256 MemSDNode(unsigned Opc, unsigned Order, const DebugLoc &dl, SDVTList VTs,
1257 EVT memvt, MachineMemOperand *MMO);
1258
1259 bool readMem() const { return MMO->isLoad(); }
1260 bool writeMem() const { return MMO->isStore(); }
1261
1262 /// Returns alignment and volatility of the memory access
1263 Align getOriginalAlign() const { return MMO->getBaseAlign(); }
1264 Align getAlign() const { return MMO->getAlign(); }
1265 // FIXME: Remove once transition to getAlign is over.
1266 unsigned getAlignment() const { return MMO->getAlign().value(); }
1267
1268 /// Return the SubclassData value, without HasDebugValue. This contains an
1269 /// encoding of the volatile flag, as well as bits used by subclasses. This
1270 /// function should only be used to compute a FoldingSetNodeID value.
1271 /// The HasDebugValue bit is masked out because CSE map needs to match
1272 /// nodes with debug info with nodes without debug info. Same is about
1273 /// isDivergent bit.
1274 unsigned getRawSubclassData() const {
1275 uint16_t Data;
1276 union {
1277 char RawSDNodeBits[sizeof(uint16_t)];
1278 SDNodeBitfields SDNodeBits;
1279 };
1280 memcpy(&RawSDNodeBits, &this->RawSDNodeBits, sizeof(this->RawSDNodeBits));
1281 SDNodeBits.HasDebugValue = 0;
1282 SDNodeBits.IsDivergent = false;
1283 memcpy(&Data, &RawSDNodeBits, sizeof(RawSDNodeBits));
1284 return Data;
1285 }
1286
1287 bool isVolatile() const { return MemSDNodeBits.IsVolatile; }
1288 bool isNonTemporal() const { return MemSDNodeBits.IsNonTemporal; }
1289 bool isDereferenceable() const { return MemSDNodeBits.IsDereferenceable; }
1290 bool isInvariant() const { return MemSDNodeBits.IsInvariant; }
1291
1292 // Returns the offset from the location of the access.
1293 int64_t getSrcValueOffset() const { return MMO->getOffset(); }
1294
1295 /// Returns the AA info that describes the dereference.
1296 AAMDNodes getAAInfo() const { return MMO->getAAInfo(); }
1297
1298 /// Returns the Ranges that describes the dereference.
1299 const MDNode *getRanges() const { return MMO->getRanges(); }
1300
1301 /// Returns the synchronization scope ID for this memory operation.
1302 SyncScope::ID getSyncScopeID() const { return MMO->getSyncScopeID(); }
1303
1304 /// Return the atomic ordering requirements for this memory operation. For
1305 /// cmpxchg atomic operations, return the atomic ordering requirements when
1306 /// store occurs.
1307 AtomicOrdering getSuccessOrdering() const {
1308 return MMO->getSuccessOrdering();
1309 }
1310
1311 /// Return a single atomic ordering that is at least as strong as both the
1312 /// success and failure orderings for an atomic operation. (For operations
1313 /// other than cmpxchg, this is equivalent to getSuccessOrdering().)
1314 AtomicOrdering getMergedOrdering() const { return MMO->getMergedOrdering(); }
1315
1316 /// Return true if the memory operation ordering is Unordered or higher.
1317 bool isAtomic() const { return MMO->isAtomic(); }
1318
1319 /// Returns true if the memory operation doesn't imply any ordering
1320 /// constraints on surrounding memory operations beyond the normal memory
1321 /// aliasing rules.
1322 bool isUnordered() const { return MMO->isUnordered(); }
1323
1324 /// Returns true if the memory operation is neither atomic or volatile.
1325 bool isSimple() const { return !isAtomic() && !isVolatile(); }
14
Assuming the condition is true
15
Returning the value 1, which participates in a condition later
1326
1327 /// Return the type of the in-memory value.
1328 EVT getMemoryVT() const { return MemoryVT; }
1329
1330 /// Return a MachineMemOperand object describing the memory
1331 /// reference performed by operation.
1332 MachineMemOperand *getMemOperand() const { return MMO; }
1333
1334 const MachinePointerInfo &getPointerInfo() const {
1335 return MMO->getPointerInfo();
1336 }
1337
1338 /// Return the address space for the associated pointer
1339 unsigned getAddressSpace() const {
1340 return getPointerInfo().getAddrSpace();
1341 }
1342
1343 /// Update this MemSDNode's MachineMemOperand information
1344 /// to reflect the alignment of NewMMO, if it has a greater alignment.
1345 /// This must only be used when the new alignment applies to all users of
1346 /// this MachineMemOperand.
1347 void refineAlignment(const MachineMemOperand *NewMMO) {
1348 MMO->refineAlignment(NewMMO);
1349 }
1350
1351 const SDValue &getChain() const { return getOperand(0); }
1352
1353 const SDValue &getBasePtr() const {
1354 switch (getOpcode()) {
1355 case ISD::STORE:
1356 case ISD::MSTORE:
1357 return getOperand(2);
1358 case ISD::MGATHER:
1359 case ISD::MSCATTER:
1360 return getOperand(3);
1361 default:
1362 return getOperand(1);
1363 }
1364 }
1365
1366 // Methods to support isa and dyn_cast
1367 static bool classof(const SDNode *N) {
1368 // For some targets, we lower some target intrinsics to a MemIntrinsicNode
1369 // with either an intrinsic or a target opcode.
1370 switch (N->getOpcode()) {
1371 case ISD::LOAD:
1372 case ISD::STORE:
1373 case ISD::PREFETCH:
1374 case ISD::ATOMIC_CMP_SWAP:
1375 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
1376 case ISD::ATOMIC_SWAP:
1377 case ISD::ATOMIC_LOAD_ADD:
1378 case ISD::ATOMIC_LOAD_SUB:
1379 case ISD::ATOMIC_LOAD_AND:
1380 case ISD::ATOMIC_LOAD_CLR:
1381 case ISD::ATOMIC_LOAD_OR:
1382 case ISD::ATOMIC_LOAD_XOR:
1383 case ISD::ATOMIC_LOAD_NAND:
1384 case ISD::ATOMIC_LOAD_MIN:
1385 case ISD::ATOMIC_LOAD_MAX:
1386 case ISD::ATOMIC_LOAD_UMIN:
1387 case ISD::ATOMIC_LOAD_UMAX:
1388 case ISD::ATOMIC_LOAD_FADD:
1389 case ISD::ATOMIC_LOAD_FSUB:
1390 case ISD::ATOMIC_LOAD:
1391 case ISD::ATOMIC_STORE:
1392 case ISD::MLOAD:
1393 case ISD::MSTORE:
1394 case ISD::MGATHER:
1395 case ISD::MSCATTER:
1396 return true;
1397 default:
1398 return N->isMemIntrinsic() || N->isTargetMemoryOpcode();
1399 }
1400 }
1401};
1402
1403/// This is an SDNode representing atomic operations.
1404class AtomicSDNode : public MemSDNode {
1405public:
1406 AtomicSDNode(unsigned Opc, unsigned Order, const DebugLoc &dl, SDVTList VTL,
1407 EVT MemVT, MachineMemOperand *MMO)
1408 : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
1409 assert(((Opc != ISD::ATOMIC_LOAD && Opc != ISD::ATOMIC_STORE) ||(static_cast <bool> (((Opc != ISD::ATOMIC_LOAD &&
Opc != ISD::ATOMIC_STORE) || MMO->isAtomic()) && "then why are we using an AtomicSDNode?"
) ? void (0) : __assert_fail ("((Opc != ISD::ATOMIC_LOAD && Opc != ISD::ATOMIC_STORE) || MMO->isAtomic()) && \"then why are we using an AtomicSDNode?\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1410, __extension__ __PRETTY_FUNCTION__))
1410 MMO->isAtomic()) && "then why are we using an AtomicSDNode?")(static_cast <bool> (((Opc != ISD::ATOMIC_LOAD &&
Opc != ISD::ATOMIC_STORE) || MMO->isAtomic()) && "then why are we using an AtomicSDNode?"
) ? void (0) : __assert_fail ("((Opc != ISD::ATOMIC_LOAD && Opc != ISD::ATOMIC_STORE) || MMO->isAtomic()) && \"then why are we using an AtomicSDNode?\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1410, __extension__ __PRETTY_FUNCTION__))
;
1411 }
1412
1413 const SDValue &getBasePtr() const { return getOperand(1); }
1414 const SDValue &getVal() const { return getOperand(2); }
1415
1416 /// Returns true if this SDNode represents cmpxchg atomic operation, false
1417 /// otherwise.
1418 bool isCompareAndSwap() const {
1419 unsigned Op = getOpcode();
1420 return Op == ISD::ATOMIC_CMP_SWAP ||
1421 Op == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS;
1422 }
1423
1424 /// For cmpxchg atomic operations, return the atomic ordering requirements
1425 /// when store does not occur.
1426 AtomicOrdering getFailureOrdering() const {
1427 assert(isCompareAndSwap() && "Must be cmpxchg operation")(static_cast <bool> (isCompareAndSwap() && "Must be cmpxchg operation"
) ? void (0) : __assert_fail ("isCompareAndSwap() && \"Must be cmpxchg operation\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1427, __extension__ __PRETTY_FUNCTION__))
;
1428 return MMO->getFailureOrdering();
1429 }
1430
1431 // Methods to support isa and dyn_cast
1432 static bool classof(const SDNode *N) {
1433 return N->getOpcode() == ISD::ATOMIC_CMP_SWAP ||
1434 N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
1435 N->getOpcode() == ISD::ATOMIC_SWAP ||
1436 N->getOpcode() == ISD::ATOMIC_LOAD_ADD ||
1437 N->getOpcode() == ISD::ATOMIC_LOAD_SUB ||
1438 N->getOpcode() == ISD::ATOMIC_LOAD_AND ||
1439 N->getOpcode() == ISD::ATOMIC_LOAD_CLR ||
1440 N->getOpcode() == ISD::ATOMIC_LOAD_OR ||
1441 N->getOpcode() == ISD::ATOMIC_LOAD_XOR ||
1442 N->getOpcode() == ISD::ATOMIC_LOAD_NAND ||
1443 N->getOpcode() == ISD::ATOMIC_LOAD_MIN ||
1444 N->getOpcode() == ISD::ATOMIC_LOAD_MAX ||
1445 N->getOpcode() == ISD::ATOMIC_LOAD_UMIN ||
1446 N->getOpcode() == ISD::ATOMIC_LOAD_UMAX ||
1447 N->getOpcode() == ISD::ATOMIC_LOAD_FADD ||
1448 N->getOpcode() == ISD::ATOMIC_LOAD_FSUB ||
1449 N->getOpcode() == ISD::ATOMIC_LOAD ||
1450 N->getOpcode() == ISD::ATOMIC_STORE;
1451 }
1452};
1453
1454/// This SDNode is used for target intrinsics that touch
1455/// memory and need an associated MachineMemOperand. Its opcode may be
1456/// INTRINSIC_VOID, INTRINSIC_W_CHAIN, PREFETCH, or a target-specific opcode
1457/// with a value not less than FIRST_TARGET_MEMORY_OPCODE.
1458class MemIntrinsicSDNode : public MemSDNode {
1459public:
1460 MemIntrinsicSDNode(unsigned Opc, unsigned Order, const DebugLoc &dl,
1461 SDVTList VTs, EVT MemoryVT, MachineMemOperand *MMO)
1462 : MemSDNode(Opc, Order, dl, VTs, MemoryVT, MMO) {
1463 SDNodeBits.IsMemIntrinsic = true;
1464 }
1465
1466 // Methods to support isa and dyn_cast
1467 static bool classof(const SDNode *N) {
1468 // We lower some target intrinsics to their target opcode
1469 // early a node with a target opcode can be of this class
1470 return N->isMemIntrinsic() ||
1471 N->getOpcode() == ISD::PREFETCH ||
1472 N->isTargetMemoryOpcode();
1473 }
1474};
1475
1476/// This SDNode is used to implement the code generator
1477/// support for the llvm IR shufflevector instruction. It combines elements
1478/// from two input vectors into a new input vector, with the selection and
1479/// ordering of elements determined by an array of integers, referred to as
1480/// the shuffle mask. For input vectors of width N, mask indices of 0..N-1
1481/// refer to elements from the LHS input, and indices from N to 2N-1 the RHS.
1482/// An index of -1 is treated as undef, such that the code generator may put
1483/// any value in the corresponding element of the result.
1484class ShuffleVectorSDNode : public SDNode {
1485 // The memory for Mask is owned by the SelectionDAG's OperandAllocator, and
1486 // is freed when the SelectionDAG object is destroyed.
1487 const int *Mask;
1488
1489protected:
1490 friend class SelectionDAG;
1491
1492 ShuffleVectorSDNode(EVT VT, unsigned Order, const DebugLoc &dl, const int *M)
1493 : SDNode(ISD::VECTOR_SHUFFLE, Order, dl, getSDVTList(VT)), Mask(M) {}
1494
1495public:
1496 ArrayRef<int> getMask() const {
1497 EVT VT = getValueType(0);
1498 return makeArrayRef(Mask, VT.getVectorNumElements());
1499 }
1500
1501 int getMaskElt(unsigned Idx) const {
1502 assert(Idx < getValueType(0).getVectorNumElements() && "Idx out of range!")(static_cast <bool> (Idx < getValueType(0).getVectorNumElements
() && "Idx out of range!") ? void (0) : __assert_fail
("Idx < getValueType(0).getVectorNumElements() && \"Idx out of range!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1502, __extension__ __PRETTY_FUNCTION__))
;
1503 return Mask[Idx];
1504 }
1505
1506 bool isSplat() const { return isSplatMask(Mask, getValueType(0)); }
1507
1508 int getSplatIndex() const {
1509 assert(isSplat() && "Cannot get splat index for non-splat!")(static_cast <bool> (isSplat() && "Cannot get splat index for non-splat!"
) ? void (0) : __assert_fail ("isSplat() && \"Cannot get splat index for non-splat!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1509, __extension__ __PRETTY_FUNCTION__))
;
1510 EVT VT = getValueType(0);
1511 for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i)
1512 if (Mask[i] >= 0)
1513 return Mask[i];
1514
1515 // We can choose any index value here and be correct because all elements
1516 // are undefined. Return 0 for better potential for callers to simplify.
1517 return 0;
1518 }
1519
1520 static bool isSplatMask(const int *Mask, EVT VT);
1521
1522 /// Change values in a shuffle permute mask assuming
1523 /// the two vector operands have swapped position.
1524 static void commuteMask(MutableArrayRef<int> Mask) {
1525 unsigned NumElems = Mask.size();
1526 for (unsigned i = 0; i != NumElems; ++i) {
1527 int idx = Mask[i];
1528 if (idx < 0)
1529 continue;
1530 else if (idx < (int)NumElems)
1531 Mask[i] = idx + NumElems;
1532 else
1533 Mask[i] = idx - NumElems;
1534 }
1535 }
1536
1537 static bool classof(const SDNode *N) {
1538 return N->getOpcode() == ISD::VECTOR_SHUFFLE;
1539 }
1540};
1541
1542class ConstantSDNode : public SDNode {
1543 friend class SelectionDAG;
1544
1545 const ConstantInt *Value;
1546
1547 ConstantSDNode(bool isTarget, bool isOpaque, const ConstantInt *val, EVT VT)
1548 : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, 0, DebugLoc(),
1549 getSDVTList(VT)),
1550 Value(val) {
1551 ConstantSDNodeBits.IsOpaque = isOpaque;
1552 }
1553
1554public:
1555 const ConstantInt *getConstantIntValue() const { return Value; }
1556 const APInt &getAPIntValue() const { return Value->getValue(); }
1557 uint64_t getZExtValue() const { return Value->getZExtValue(); }
1558 int64_t getSExtValue() const { return Value->getSExtValue(); }
1559 uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX(18446744073709551615UL)) {
1560 return Value->getLimitedValue(Limit);
1561 }
1562 MaybeAlign getMaybeAlignValue() const { return Value->getMaybeAlignValue(); }
1563 Align getAlignValue() const { return Value->getAlignValue(); }
1564
1565 bool isOne() const { return Value->isOne(); }
1566 bool isNullValue() const { return Value->isZero(); }
1567 bool isAllOnesValue() const { return Value->isMinusOne(); }
1568 bool isMaxSignedValue() const { return Value->isMaxValue(true); }
1569 bool isMinSignedValue() const { return Value->isMinValue(true); }
1570
1571 bool isOpaque() const { return ConstantSDNodeBits.IsOpaque; }
1572
1573 static bool classof(const SDNode *N) {
1574 return N->getOpcode() == ISD::Constant ||
1575 N->getOpcode() == ISD::TargetConstant;
1576 }
1577};
1578
1579uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
1580 return cast<ConstantSDNode>(getOperand(Num))->getZExtValue();
1581}
1582
1583const APInt &SDNode::getConstantOperandAPInt(unsigned Num) const {
1584 return cast<ConstantSDNode>(getOperand(Num))->getAPIntValue();
1585}
1586
1587class ConstantFPSDNode : public SDNode {
1588 friend class SelectionDAG;
1589
1590 const ConstantFP *Value;
1591
1592 ConstantFPSDNode(bool isTarget, const ConstantFP *val, EVT VT)
1593 : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, 0,
1594 DebugLoc(), getSDVTList(VT)),
1595 Value(val) {}
1596
1597public:
1598 const APFloat& getValueAPF() const { return Value->getValueAPF(); }
1599 const ConstantFP *getConstantFPValue() const { return Value; }
1600
1601 /// Return true if the value is positive or negative zero.
1602 bool isZero() const { return Value->isZero(); }
1603
1604 /// Return true if the value is a NaN.
1605 bool isNaN() const { return Value->isNaN(); }
1606
1607 /// Return true if the value is an infinity
1608 bool isInfinity() const { return Value->isInfinity(); }
1609
1610 /// Return true if the value is negative.
1611 bool isNegative() const { return Value->isNegative(); }
1612
1613 /// We don't rely on operator== working on double values, as
1614 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
1615 /// As such, this method can be used to do an exact bit-for-bit comparison of
1616 /// two floating point values.
1617
1618 /// We leave the version with the double argument here because it's just so
1619 /// convenient to write "2.0" and the like. Without this function we'd
1620 /// have to duplicate its logic everywhere it's called.
1621 bool isExactlyValue(double V) const {
1622 return Value->getValueAPF().isExactlyValue(V);
1623 }
1624 bool isExactlyValue(const APFloat& V) const;
1625
1626 static bool isValueValidForType(EVT VT, const APFloat& Val);
1627
1628 static bool classof(const SDNode *N) {
1629 return N->getOpcode() == ISD::ConstantFP ||
1630 N->getOpcode() == ISD::TargetConstantFP;
1631 }
1632};
1633
1634/// Returns true if \p V is a constant integer zero.
1635bool isNullConstant(SDValue V);
1636
1637/// Returns true if \p V is an FP constant with a value of positive zero.
1638bool isNullFPConstant(SDValue V);
1639
1640/// Returns true if \p V is an integer constant with all bits set.
1641bool isAllOnesConstant(SDValue V);
1642
1643/// Returns true if \p V is a constant integer one.
1644bool isOneConstant(SDValue V);
1645
1646/// Return the non-bitcasted source operand of \p V if it exists.
1647/// If \p V is not a bitcasted value, it is returned as-is.
1648SDValue peekThroughBitcasts(SDValue V);
1649
1650/// Return the non-bitcasted and one-use source operand of \p V if it exists.
1651/// If \p V is not a bitcasted one-use value, it is returned as-is.
1652SDValue peekThroughOneUseBitcasts(SDValue V);
1653
1654/// Return the non-extracted vector source operand of \p V if it exists.
1655/// If \p V is not an extracted subvector, it is returned as-is.
1656SDValue peekThroughExtractSubvectors(SDValue V);
1657
1658/// Returns true if \p V is a bitwise not operation. Assumes that an all ones
1659/// constant is canonicalized to be operand 1.
1660bool isBitwiseNot(SDValue V, bool AllowUndefs = false);
1661
1662/// Returns the SDNode if it is a constant splat BuildVector or constant int.
1663ConstantSDNode *isConstOrConstSplat(SDValue N, bool AllowUndefs = false,
1664 bool AllowTruncation = false);
1665
1666/// Returns the SDNode if it is a demanded constant splat BuildVector or
1667/// constant int.
1668ConstantSDNode *isConstOrConstSplat(SDValue N, const APInt &DemandedElts,
1669 bool AllowUndefs = false,
1670 bool AllowTruncation = false);
1671
1672/// Returns the SDNode if it is a constant splat BuildVector or constant float.
1673ConstantFPSDNode *isConstOrConstSplatFP(SDValue N, bool AllowUndefs = false);
1674
1675/// Returns the SDNode if it is a demanded constant splat BuildVector or
1676/// constant float.
1677ConstantFPSDNode *isConstOrConstSplatFP(SDValue N, const APInt &DemandedElts,
1678 bool AllowUndefs = false);
1679
1680/// Return true if the value is a constant 0 integer or a splatted vector of
1681/// a constant 0 integer (with no undefs by default).
1682/// Build vector implicit truncation is not an issue for null values.
1683bool isNullOrNullSplat(SDValue V, bool AllowUndefs = false);
1684
1685/// Return true if the value is a constant 1 integer or a splatted vector of a
1686/// constant 1 integer (with no undefs).
1687/// Does not permit build vector implicit truncation.
1688bool isOneOrOneSplat(SDValue V, bool AllowUndefs = false);
1689
1690/// Return true if the value is a constant -1 integer or a splatted vector of a
1691/// constant -1 integer (with no undefs).
1692/// Does not permit build vector implicit truncation.
1693bool isAllOnesOrAllOnesSplat(SDValue V, bool AllowUndefs = false);
1694
1695/// Return true if \p V is either a integer or FP constant.
1696inline bool isIntOrFPConstant(SDValue V) {
1697 return isa<ConstantSDNode>(V) || isa<ConstantFPSDNode>(V);
1698}
1699
1700class GlobalAddressSDNode : public SDNode {
1701 friend class SelectionDAG;
1702
1703 const GlobalValue *TheGlobal;
1704 int64_t Offset;
1705 unsigned TargetFlags;
1706
1707 GlobalAddressSDNode(unsigned Opc, unsigned Order, const DebugLoc &DL,
1708 const GlobalValue *GA, EVT VT, int64_t o,
1709 unsigned TF);
1710
1711public:
1712 const GlobalValue *getGlobal() const { return TheGlobal; }
1713 int64_t getOffset() const { return Offset; }
1714 unsigned getTargetFlags() const { return TargetFlags; }
1715 // Return the address space this GlobalAddress belongs to.
1716 unsigned getAddressSpace() const;
1717
1718 static bool classof(const SDNode *N) {
1719 return N->getOpcode() == ISD::GlobalAddress ||
1720 N->getOpcode() == ISD::TargetGlobalAddress ||
1721 N->getOpcode() == ISD::GlobalTLSAddress ||
1722 N->getOpcode() == ISD::TargetGlobalTLSAddress;
1723 }
1724};
1725
1726class FrameIndexSDNode : public SDNode {
1727 friend class SelectionDAG;
1728
1729 int FI;
1730
1731 FrameIndexSDNode(int fi, EVT VT, bool isTarg)
1732 : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex,
1733 0, DebugLoc(), getSDVTList(VT)), FI(fi) {
1734 }
1735
1736public:
1737 int getIndex() const { return FI; }
1738
1739 static bool classof(const SDNode *N) {
1740 return N->getOpcode() == ISD::FrameIndex ||
1741 N->getOpcode() == ISD::TargetFrameIndex;
1742 }
1743};
1744
1745/// This SDNode is used for LIFETIME_START/LIFETIME_END values, which indicate
1746/// the offet and size that are started/ended in the underlying FrameIndex.
1747class LifetimeSDNode : public SDNode {
1748 friend class SelectionDAG;
1749 int64_t Size;
1750 int64_t Offset; // -1 if offset is unknown.
1751
1752 LifetimeSDNode(unsigned Opcode, unsigned Order, const DebugLoc &dl,
1753 SDVTList VTs, int64_t Size, int64_t Offset)
1754 : SDNode(Opcode, Order, dl, VTs), Size(Size), Offset(Offset) {}
1755public:
1756 int64_t getFrameIndex() const {
1757 return cast<FrameIndexSDNode>(getOperand(1))->getIndex();
1758 }
1759
1760 bool hasOffset() const { return Offset >= 0; }
1761 int64_t getOffset() const {
1762 assert(hasOffset() && "offset is unknown")(static_cast <bool> (hasOffset() && "offset is unknown"
) ? void (0) : __assert_fail ("hasOffset() && \"offset is unknown\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1762, __extension__ __PRETTY_FUNCTION__))
;
1763 return Offset;
1764 }
1765 int64_t getSize() const {
1766 assert(hasOffset() && "offset is unknown")(static_cast <bool> (hasOffset() && "offset is unknown"
) ? void (0) : __assert_fail ("hasOffset() && \"offset is unknown\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1766, __extension__ __PRETTY_FUNCTION__))
;
1767 return Size;
1768 }
1769
1770 // Methods to support isa and dyn_cast
1771 static bool classof(const SDNode *N) {
1772 return N->getOpcode() == ISD::LIFETIME_START ||
1773 N->getOpcode() == ISD::LIFETIME_END;
1774 }
1775};
1776
1777/// This SDNode is used for PSEUDO_PROBE values, which are the function guid and
1778/// the index of the basic block being probed. A pseudo probe serves as a place
1779/// holder and will be removed at the end of compilation. It does not have any
1780/// operand because we do not want the instruction selection to deal with any.
1781class PseudoProbeSDNode : public SDNode {
1782 friend class SelectionDAG;
1783 uint64_t Guid;
1784 uint64_t Index;
1785 uint32_t Attributes;
1786
1787 PseudoProbeSDNode(unsigned Opcode, unsigned Order, const DebugLoc &Dl,
1788 SDVTList VTs, uint64_t Guid, uint64_t Index, uint32_t Attr)
1789 : SDNode(Opcode, Order, Dl, VTs), Guid(Guid), Index(Index),
1790 Attributes(Attr) {}
1791
1792public:
1793 uint64_t getGuid() const { return Guid; }
1794 uint64_t getIndex() const { return Index; }
1795 uint32_t getAttributes() const { return Attributes; }
1796
1797 // Methods to support isa and dyn_cast
1798 static bool classof(const SDNode *N) {
1799 return N->getOpcode() == ISD::PSEUDO_PROBE;
1800 }
1801};
1802
1803class JumpTableSDNode : public SDNode {
1804 friend class SelectionDAG;
1805
1806 int JTI;
1807 unsigned TargetFlags;
1808
1809 JumpTableSDNode(int jti, EVT VT, bool isTarg, unsigned TF)
1810 : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable,
1811 0, DebugLoc(), getSDVTList(VT)), JTI(jti), TargetFlags(TF) {
1812 }
1813
1814public:
1815 int getIndex() const { return JTI; }
1816 unsigned getTargetFlags() const { return TargetFlags; }
1817
1818 static bool classof(const SDNode *N) {
1819 return N->getOpcode() == ISD::JumpTable ||
1820 N->getOpcode() == ISD::TargetJumpTable;
1821 }
1822};
1823
1824class ConstantPoolSDNode : public SDNode {
1825 friend class SelectionDAG;
1826
1827 union {
1828 const Constant *ConstVal;
1829 MachineConstantPoolValue *MachineCPVal;
1830 } Val;
1831 int Offset; // It's a MachineConstantPoolValue if top bit is set.
1832 Align Alignment; // Minimum alignment requirement of CP.
1833 unsigned TargetFlags;
1834
1835 ConstantPoolSDNode(bool isTarget, const Constant *c, EVT VT, int o,
1836 Align Alignment, unsigned TF)
1837 : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
1838 DebugLoc(), getSDVTList(VT)),
1839 Offset(o), Alignment(Alignment), TargetFlags(TF) {
1840 assert(Offset >= 0 && "Offset is too large")(static_cast <bool> (Offset >= 0 && "Offset is too large"
) ? void (0) : __assert_fail ("Offset >= 0 && \"Offset is too large\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1840, __extension__ __PRETTY_FUNCTION__))
;
1841 Val.ConstVal = c;
1842 }
1843
1844 ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v, EVT VT, int o,
1845 Align Alignment, unsigned TF)
1846 : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
1847 DebugLoc(), getSDVTList(VT)),
1848 Offset(o), Alignment(Alignment), TargetFlags(TF) {
1849 assert(Offset >= 0 && "Offset is too large")(static_cast <bool> (Offset >= 0 && "Offset is too large"
) ? void (0) : __assert_fail ("Offset >= 0 && \"Offset is too large\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1849, __extension__ __PRETTY_FUNCTION__))
;
1850 Val.MachineCPVal = v;
1851 Offset |= 1 << (sizeof(unsigned)*CHAR_BIT8-1);
1852 }
1853
1854public:
1855 bool isMachineConstantPoolEntry() const {
1856 return Offset < 0;
1857 }
1858
1859 const Constant *getConstVal() const {
1860 assert(!isMachineConstantPoolEntry() && "Wrong constantpool type")(static_cast <bool> (!isMachineConstantPoolEntry() &&
"Wrong constantpool type") ? void (0) : __assert_fail ("!isMachineConstantPoolEntry() && \"Wrong constantpool type\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1860, __extension__ __PRETTY_FUNCTION__))
;
1861 return Val.ConstVal;
1862 }
1863
1864 MachineConstantPoolValue *getMachineCPVal() const {
1865 assert(isMachineConstantPoolEntry() && "Wrong constantpool type")(static_cast <bool> (isMachineConstantPoolEntry() &&
"Wrong constantpool type") ? void (0) : __assert_fail ("isMachineConstantPoolEntry() && \"Wrong constantpool type\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 1865, __extension__ __PRETTY_FUNCTION__))
;
1866 return Val.MachineCPVal;
1867 }
1868
1869 int getOffset() const {
1870 return Offset & ~(1 << (sizeof(unsigned)*CHAR_BIT8-1));
1871 }
1872
1873 // Return the alignment of this constant pool object, which is either 0 (for
1874 // default alignment) or the desired value.
1875 Align getAlign() const { return Alignment; }
1876 unsigned getTargetFlags() const { return TargetFlags; }
1877
1878 Type *getType() const;
1879
1880 static bool classof(const SDNode *N) {
1881 return N->getOpcode() == ISD::ConstantPool ||
1882 N->getOpcode() == ISD::TargetConstantPool;
1883 }
1884};
1885
1886/// Completely target-dependent object reference.
1887class TargetIndexSDNode : public SDNode {
1888 friend class SelectionDAG;
1889
1890 unsigned TargetFlags;
1891 int Index;
1892 int64_t Offset;
1893
1894public:
1895 TargetIndexSDNode(int Idx, EVT VT, int64_t Ofs, unsigned TF)
1896 : SDNode(ISD::TargetIndex, 0, DebugLoc(), getSDVTList(VT)),
1897 TargetFlags(TF), Index(Idx), Offset(Ofs) {}
1898
1899 unsigned getTargetFlags() const { return TargetFlags; }
1900 int getIndex() const { return Index; }
1901 int64_t getOffset() const { return Offset; }
1902
1903 static bool classof(const SDNode *N) {
1904 return N->getOpcode() == ISD::TargetIndex;
1905 }
1906};
1907
1908class BasicBlockSDNode : public SDNode {
1909 friend class SelectionDAG;
1910
1911 MachineBasicBlock *MBB;
1912
1913 /// Debug info is meaningful and potentially useful here, but we create
1914 /// blocks out of order when they're jumped to, which makes it a bit
1915 /// harder. Let's see if we need it first.
1916 explicit BasicBlockSDNode(MachineBasicBlock *mbb)
1917 : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb)
1918 {}
1919
1920public:
1921 MachineBasicBlock *getBasicBlock() const { return MBB; }
1922
1923 static bool classof(const SDNode *N) {
1924 return N->getOpcode() == ISD::BasicBlock;
1925 }
1926};
1927
1928/// A "pseudo-class" with methods for operating on BUILD_VECTORs.
1929class BuildVectorSDNode : public SDNode {
1930public:
1931 // These are constructed as SDNodes and then cast to BuildVectorSDNodes.
1932 explicit BuildVectorSDNode() = delete;
1933
1934 /// Check if this is a constant splat, and if so, find the
1935 /// smallest element size that splats the vector. If MinSplatBits is
1936 /// nonzero, the element size must be at least that large. Note that the
1937 /// splat element may be the entire vector (i.e., a one element vector).
1938 /// Returns the splat element value in SplatValue. Any undefined bits in
1939 /// that value are zero, and the corresponding bits in the SplatUndef mask
1940 /// are set. The SplatBitSize value is set to the splat element size in
1941 /// bits. HasAnyUndefs is set to true if any bits in the vector are
1942 /// undefined. isBigEndian describes the endianness of the target.
1943 bool isConstantSplat(APInt &SplatValue, APInt &SplatUndef,
1944 unsigned &SplatBitSize, bool &HasAnyUndefs,
1945 unsigned MinSplatBits = 0,
1946 bool isBigEndian = false) const;
1947
1948 /// Returns the demanded splatted value or a null value if this is not a
1949 /// splat.
1950 ///
1951 /// The DemandedElts mask indicates the elements that must be in the splat.
1952 /// If passed a non-null UndefElements bitvector, it will resize it to match
1953 /// the vector width and set the bits where elements are undef.
1954 SDValue getSplatValue(const APInt &DemandedElts,
1955 BitVector *UndefElements = nullptr) const;
1956
1957 /// Returns the splatted value or a null value if this is not a splat.
1958 ///
1959 /// If passed a non-null UndefElements bitvector, it will resize it to match
1960 /// the vector width and set the bits where elements are undef.
1961 SDValue getSplatValue(BitVector *UndefElements = nullptr) const;
1962
1963 /// Find the shortest repeating sequence of values in the build vector.
1964 ///
1965 /// e.g. { u, X, u, X, u, u, X, u } -> { X }
1966 /// { X, Y, u, Y, u, u, X, u } -> { X, Y }
1967 ///
1968 /// Currently this must be a power-of-2 build vector.
1969 /// The DemandedElts mask indicates the elements that must be present,
1970 /// undemanded elements in Sequence may be null (SDValue()). If passed a
1971 /// non-null UndefElements bitvector, it will resize it to match the original
1972 /// vector width and set the bits where elements are undef. If result is
1973 /// false, Sequence will be empty.
1974 bool getRepeatedSequence(const APInt &DemandedElts,
1975 SmallVectorImpl<SDValue> &Sequence,
1976 BitVector *UndefElements = nullptr) const;
1977
1978 /// Find the shortest repeating sequence of values in the build vector.
1979 ///
1980 /// e.g. { u, X, u, X, u, u, X, u } -> { X }
1981 /// { X, Y, u, Y, u, u, X, u } -> { X, Y }
1982 ///
1983 /// Currently this must be a power-of-2 build vector.
1984 /// If passed a non-null UndefElements bitvector, it will resize it to match
1985 /// the original vector width and set the bits where elements are undef.
1986 /// If result is false, Sequence will be empty.
1987 bool getRepeatedSequence(SmallVectorImpl<SDValue> &Sequence,
1988 BitVector *UndefElements = nullptr) const;
1989
1990 /// Returns the demanded splatted constant or null if this is not a constant
1991 /// splat.
1992 ///
1993 /// The DemandedElts mask indicates the elements that must be in the splat.
1994 /// If passed a non-null UndefElements bitvector, it will resize it to match
1995 /// the vector width and set the bits where elements are undef.
1996 ConstantSDNode *
1997 getConstantSplatNode(const APInt &DemandedElts,
1998 BitVector *UndefElements = nullptr) const;
1999
2000 /// Returns the splatted constant or null if this is not a constant
2001 /// splat.
2002 ///
2003 /// If passed a non-null UndefElements bitvector, it will resize it to match
2004 /// the vector width and set the bits where elements are undef.
2005 ConstantSDNode *
2006 getConstantSplatNode(BitVector *UndefElements = nullptr) const;
2007
2008 /// Returns the demanded splatted constant FP or null if this is not a
2009 /// constant FP splat.
2010 ///
2011 /// The DemandedElts mask indicates the elements that must be in the splat.
2012 /// If passed a non-null UndefElements bitvector, it will resize it to match
2013 /// the vector width and set the bits where elements are undef.
2014 ConstantFPSDNode *
2015 getConstantFPSplatNode(const APInt &DemandedElts,
2016 BitVector *UndefElements = nullptr) const;
2017
2018 /// Returns the splatted constant FP or null if this is not a constant
2019 /// FP splat.
2020 ///
2021 /// If passed a non-null UndefElements bitvector, it will resize it to match
2022 /// the vector width and set the bits where elements are undef.
2023 ConstantFPSDNode *
2024 getConstantFPSplatNode(BitVector *UndefElements = nullptr) const;
2025
2026 /// If this is a constant FP splat and the splatted constant FP is an
2027 /// exact power or 2, return the log base 2 integer value. Otherwise,
2028 /// return -1.
2029 ///
2030 /// The BitWidth specifies the necessary bit precision.
2031 int32_t getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
2032 uint32_t BitWidth) const;
2033
2034 bool isConstant() const;
2035
2036 static bool classof(const SDNode *N) {
2037 return N->getOpcode() == ISD::BUILD_VECTOR;
2038 }
2039};
2040
2041/// An SDNode that holds an arbitrary LLVM IR Value. This is
2042/// used when the SelectionDAG needs to make a simple reference to something
2043/// in the LLVM IR representation.
2044///
2045class SrcValueSDNode : public SDNode {
2046 friend class SelectionDAG;
2047
2048 const Value *V;
2049
2050 /// Create a SrcValue for a general value.
2051 explicit SrcValueSDNode(const Value *v)
2052 : SDNode(ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {}
2053
2054public:
2055 /// Return the contained Value.
2056 const Value *getValue() const { return V; }
2057
2058 static bool classof(const SDNode *N) {
2059 return N->getOpcode() == ISD::SRCVALUE;
2060 }
2061};
2062
2063class MDNodeSDNode : public SDNode {
2064 friend class SelectionDAG;
2065
2066 const MDNode *MD;
2067
2068 explicit MDNodeSDNode(const MDNode *md)
2069 : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md)
2070 {}
2071
2072public:
2073 const MDNode *getMD() const { return MD; }
2074
2075 static bool classof(const SDNode *N) {
2076 return N->getOpcode() == ISD::MDNODE_SDNODE;
2077 }
2078};
2079
2080class RegisterSDNode : public SDNode {
2081 friend class SelectionDAG;
2082
2083 Register Reg;
2084
2085 RegisterSDNode(Register reg, EVT VT)
2086 : SDNode(ISD::Register, 0, DebugLoc(), getSDVTList(VT)), Reg(reg) {}
2087
2088public:
2089 Register getReg() const { return Reg; }
2090
2091 static bool classof(const SDNode *N) {
2092 return N->getOpcode() == ISD::Register;
2093 }
2094};
2095
2096class RegisterMaskSDNode : public SDNode {
2097 friend class SelectionDAG;
2098
2099 // The memory for RegMask is not owned by the node.
2100 const uint32_t *RegMask;
2101
2102 RegisterMaskSDNode(const uint32_t *mask)
2103 : SDNode(ISD::RegisterMask, 0, DebugLoc(), getSDVTList(MVT::Untyped)),
2104 RegMask(mask) {}
2105
2106public:
2107 const uint32_t *getRegMask() const { return RegMask; }
2108
2109 static bool classof(const SDNode *N) {
2110 return N->getOpcode() == ISD::RegisterMask;
2111 }
2112};
2113
2114class BlockAddressSDNode : public SDNode {
2115 friend class SelectionDAG;
2116
2117 const BlockAddress *BA;
2118 int64_t Offset;
2119 unsigned TargetFlags;
2120
2121 BlockAddressSDNode(unsigned NodeTy, EVT VT, const BlockAddress *ba,
2122 int64_t o, unsigned Flags)
2123 : SDNode(NodeTy, 0, DebugLoc(), getSDVTList(VT)),
2124 BA(ba), Offset(o), TargetFlags(Flags) {}
2125
2126public:
2127 const BlockAddress *getBlockAddress() const { return BA; }
2128 int64_t getOffset() const { return Offset; }
2129 unsigned getTargetFlags() const { return TargetFlags; }
2130
2131 static bool classof(const SDNode *N) {
2132 return N->getOpcode() == ISD::BlockAddress ||
2133 N->getOpcode() == ISD::TargetBlockAddress;
2134 }
2135};
2136
2137class LabelSDNode : public SDNode {
2138 friend class SelectionDAG;
2139
2140 MCSymbol *Label;
2141
2142 LabelSDNode(unsigned Opcode, unsigned Order, const DebugLoc &dl, MCSymbol *L)
2143 : SDNode(Opcode, Order, dl, getSDVTList(MVT::Other)), Label(L) {
2144 assert(LabelSDNode::classof(this) && "not a label opcode")(static_cast <bool> (LabelSDNode::classof(this) &&
"not a label opcode") ? void (0) : __assert_fail ("LabelSDNode::classof(this) && \"not a label opcode\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2144, __extension__ __PRETTY_FUNCTION__))
;
2145 }
2146
2147public:
2148 MCSymbol *getLabel() const { return Label; }
2149
2150 static bool classof(const SDNode *N) {
2151 return N->getOpcode() == ISD::EH_LABEL ||
2152 N->getOpcode() == ISD::ANNOTATION_LABEL;
2153 }
2154};
2155
2156class ExternalSymbolSDNode : public SDNode {
2157 friend class SelectionDAG;
2158
2159 const char *Symbol;
2160 unsigned TargetFlags;
2161
2162 ExternalSymbolSDNode(bool isTarget, const char *Sym, unsigned TF, EVT VT)
2163 : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, 0,
2164 DebugLoc(), getSDVTList(VT)),
2165 Symbol(Sym), TargetFlags(TF) {}
2166
2167public:
2168 const char *getSymbol() const { return Symbol; }
2169 unsigned getTargetFlags() const { return TargetFlags; }
2170
2171 static bool classof(const SDNode *N) {
2172 return N->getOpcode() == ISD::ExternalSymbol ||
2173 N->getOpcode() == ISD::TargetExternalSymbol;
2174 }
2175};
2176
2177class MCSymbolSDNode : public SDNode {
2178 friend class SelectionDAG;
2179
2180 MCSymbol *Symbol;
2181
2182 MCSymbolSDNode(MCSymbol *Symbol, EVT VT)
2183 : SDNode(ISD::MCSymbol, 0, DebugLoc(), getSDVTList(VT)), Symbol(Symbol) {}
2184
2185public:
2186 MCSymbol *getMCSymbol() const { return Symbol; }
2187
2188 static bool classof(const SDNode *N) {
2189 return N->getOpcode() == ISD::MCSymbol;
2190 }
2191};
2192
2193class CondCodeSDNode : public SDNode {
2194 friend class SelectionDAG;
2195
2196 ISD::CondCode Condition;
2197
2198 explicit CondCodeSDNode(ISD::CondCode Cond)
2199 : SDNode(ISD::CONDCODE, 0, DebugLoc(), getSDVTList(MVT::Other)),
2200 Condition(Cond) {}
2201
2202public:
2203 ISD::CondCode get() const { return Condition; }
2204
2205 static bool classof(const SDNode *N) {
2206 return N->getOpcode() == ISD::CONDCODE;
2207 }
2208};
2209
2210/// This class is used to represent EVT's, which are used
2211/// to parameterize some operations.
2212class VTSDNode : public SDNode {
2213 friend class SelectionDAG;
2214
2215 EVT ValueType;
2216
2217 explicit VTSDNode(EVT VT)
2218 : SDNode(ISD::VALUETYPE, 0, DebugLoc(), getSDVTList(MVT::Other)),
2219 ValueType(VT) {}
2220
2221public:
2222 EVT getVT() const { return ValueType; }
2223
2224 static bool classof(const SDNode *N) {
2225 return N->getOpcode() == ISD::VALUETYPE;
2226 }
2227};
2228
2229/// Base class for LoadSDNode and StoreSDNode
2230class LSBaseSDNode : public MemSDNode {
2231public:
2232 LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, const DebugLoc &dl,
2233 SDVTList VTs, ISD::MemIndexedMode AM, EVT MemVT,
2234 MachineMemOperand *MMO)
2235 : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
2236 LSBaseSDNodeBits.AddressingMode = AM;
2237 assert(getAddressingMode() == AM && "Value truncated")(static_cast <bool> (getAddressingMode() == AM &&
"Value truncated") ? void (0) : __assert_fail ("getAddressingMode() == AM && \"Value truncated\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2237, __extension__ __PRETTY_FUNCTION__))
;
2238 }
2239
2240 const SDValue &getOffset() const {
2241 return getOperand(getOpcode() == ISD::LOAD ? 2 : 3);
2242 }
2243
2244 /// Return the addressing mode for this load or store:
2245 /// unindexed, pre-inc, pre-dec, post-inc, or post-dec.
2246 ISD::MemIndexedMode getAddressingMode() const {
2247 return static_cast<ISD::MemIndexedMode>(LSBaseSDNodeBits.AddressingMode);
2248 }
2249
2250 /// Return true if this is a pre/post inc/dec load/store.
2251 bool isIndexed() const { return getAddressingMode() != ISD::UNINDEXED; }
2252
2253 /// Return true if this is NOT a pre/post inc/dec load/store.
2254 bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; }
2255
2256 static bool classof(const SDNode *N) {
2257 return N->getOpcode() == ISD::LOAD ||
2258 N->getOpcode() == ISD::STORE;
2259 }
2260};
2261
2262/// This class is used to represent ISD::LOAD nodes.
2263class LoadSDNode : public LSBaseSDNode {
2264 friend class SelectionDAG;
2265
2266 LoadSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2267 ISD::MemIndexedMode AM, ISD::LoadExtType ETy, EVT MemVT,
2268 MachineMemOperand *MMO)
2269 : LSBaseSDNode(ISD::LOAD, Order, dl, VTs, AM, MemVT, MMO) {
2270 LoadSDNodeBits.ExtTy = ETy;
2271 assert(readMem() && "Load MachineMemOperand is not a load!")(static_cast <bool> (readMem() && "Load MachineMemOperand is not a load!"
) ? void (0) : __assert_fail ("readMem() && \"Load MachineMemOperand is not a load!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2271, __extension__ __PRETTY_FUNCTION__))
;
2272 assert(!writeMem() && "Load MachineMemOperand is a store!")(static_cast <bool> (!writeMem() && "Load MachineMemOperand is a store!"
) ? void (0) : __assert_fail ("!writeMem() && \"Load MachineMemOperand is a store!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2272, __extension__ __PRETTY_FUNCTION__))
;
2273 }
2274
2275public:
2276 /// Return whether this is a plain node,
2277 /// or one of the varieties of value-extending loads.
2278 ISD::LoadExtType getExtensionType() const {
2279 return static_cast<ISD::LoadExtType>(LoadSDNodeBits.ExtTy);
2280 }
2281
2282 const SDValue &getBasePtr() const { return getOperand(1); }
2283 const SDValue &getOffset() const { return getOperand(2); }
2284
2285 static bool classof(const SDNode *N) {
2286 return N->getOpcode() == ISD::LOAD;
2287 }
2288};
2289
2290/// This class is used to represent ISD::STORE nodes.
2291class StoreSDNode : public LSBaseSDNode {
2292 friend class SelectionDAG;
2293
2294 StoreSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2295 ISD::MemIndexedMode AM, bool isTrunc, EVT MemVT,
2296 MachineMemOperand *MMO)
2297 : LSBaseSDNode(ISD::STORE, Order, dl, VTs, AM, MemVT, MMO) {
2298 StoreSDNodeBits.IsTruncating = isTrunc;
2299 assert(!readMem() && "Store MachineMemOperand is a load!")(static_cast <bool> (!readMem() && "Store MachineMemOperand is a load!"
) ? void (0) : __assert_fail ("!readMem() && \"Store MachineMemOperand is a load!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2299, __extension__ __PRETTY_FUNCTION__))
;
2300 assert(writeMem() && "Store MachineMemOperand is not a store!")(static_cast <bool> (writeMem() && "Store MachineMemOperand is not a store!"
) ? void (0) : __assert_fail ("writeMem() && \"Store MachineMemOperand is not a store!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2300, __extension__ __PRETTY_FUNCTION__))
;
2301 }
2302
2303public:
2304 /// Return true if the op does a truncation before store.
2305 /// For integers this is the same as doing a TRUNCATE and storing the result.
2306 /// For floats, it is the same as doing an FP_ROUND and storing the result.
2307 bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; }
2308 void setTruncatingStore(bool Truncating) {
2309 StoreSDNodeBits.IsTruncating = Truncating;
2310 }
2311
2312 const SDValue &getValue() const { return getOperand(1); }
2313 const SDValue &getBasePtr() const { return getOperand(2); }
2314 const SDValue &getOffset() const { return getOperand(3); }
2315
2316 static bool classof(const SDNode *N) {
2317 return N->getOpcode() == ISD::STORE;
2318 }
2319};
2320
2321/// This base class is used to represent MLOAD and MSTORE nodes
2322class MaskedLoadStoreSDNode : public MemSDNode {
2323public:
2324 friend class SelectionDAG;
2325
2326 MaskedLoadStoreSDNode(ISD::NodeType NodeTy, unsigned Order,
2327 const DebugLoc &dl, SDVTList VTs,
2328 ISD::MemIndexedMode AM, EVT MemVT,
2329 MachineMemOperand *MMO)
2330 : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
2331 LSBaseSDNodeBits.AddressingMode = AM;
2332 assert(getAddressingMode() == AM && "Value truncated")(static_cast <bool> (getAddressingMode() == AM &&
"Value truncated") ? void (0) : __assert_fail ("getAddressingMode() == AM && \"Value truncated\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2332, __extension__ __PRETTY_FUNCTION__))
;
2333 }
2334
2335 // MaskedLoadSDNode (Chain, ptr, offset, mask, passthru)
2336 // MaskedStoreSDNode (Chain, data, ptr, offset, mask)
2337 // Mask is a vector of i1 elements
2338 const SDValue &getOffset() const {
2339 return getOperand(getOpcode() == ISD::MLOAD ? 2 : 3);
2340 }
2341 const SDValue &getMask() const {
2342 return getOperand(getOpcode() == ISD::MLOAD ? 3 : 4);
2343 }
2344
2345 /// Return the addressing mode for this load or store:
2346 /// unindexed, pre-inc, pre-dec, post-inc, or post-dec.
2347 ISD::MemIndexedMode getAddressingMode() const {
2348 return static_cast<ISD::MemIndexedMode>(LSBaseSDNodeBits.AddressingMode);
2349 }
2350
2351 /// Return true if this is a pre/post inc/dec load/store.
2352 bool isIndexed() const { return getAddressingMode() != ISD::UNINDEXED; }
2353
2354 /// Return true if this is NOT a pre/post inc/dec load/store.
2355 bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; }
2356
2357 static bool classof(const SDNode *N) {
2358 return N->getOpcode() == ISD::MLOAD ||
2359 N->getOpcode() == ISD::MSTORE;
2360 }
2361};
2362
2363/// This class is used to represent an MLOAD node
2364class MaskedLoadSDNode : public MaskedLoadStoreSDNode {
2365public:
2366 friend class SelectionDAG;
2367
2368 MaskedLoadSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2369 ISD::MemIndexedMode AM, ISD::LoadExtType ETy,
2370 bool IsExpanding, EVT MemVT, MachineMemOperand *MMO)
2371 : MaskedLoadStoreSDNode(ISD::MLOAD, Order, dl, VTs, AM, MemVT, MMO) {
2372 LoadSDNodeBits.ExtTy = ETy;
2373 LoadSDNodeBits.IsExpanding = IsExpanding;
2374 }
2375
2376 ISD::LoadExtType getExtensionType() const {
2377 return static_cast<ISD::LoadExtType>(LoadSDNodeBits.ExtTy);
2378 }
2379
2380 const SDValue &getBasePtr() const { return getOperand(1); }
2381 const SDValue &getOffset() const { return getOperand(2); }
2382 const SDValue &getMask() const { return getOperand(3); }
2383 const SDValue &getPassThru() const { return getOperand(4); }
2384
2385 static bool classof(const SDNode *N) {
2386 return N->getOpcode() == ISD::MLOAD;
2387 }
2388
2389 bool isExpandingLoad() const { return LoadSDNodeBits.IsExpanding; }
2390};
2391
2392/// This class is used to represent an MSTORE node
2393class MaskedStoreSDNode : public MaskedLoadStoreSDNode {
2394public:
2395 friend class SelectionDAG;
2396
2397 MaskedStoreSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2398 ISD::MemIndexedMode AM, bool isTrunc, bool isCompressing,
2399 EVT MemVT, MachineMemOperand *MMO)
2400 : MaskedLoadStoreSDNode(ISD::MSTORE, Order, dl, VTs, AM, MemVT, MMO) {
2401 StoreSDNodeBits.IsTruncating = isTrunc;
2402 StoreSDNodeBits.IsCompressing = isCompressing;
2403 }
2404
2405 /// Return true if the op does a truncation before store.
2406 /// For integers this is the same as doing a TRUNCATE and storing the result.
2407 /// For floats, it is the same as doing an FP_ROUND and storing the result.
2408 bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; }
2409
2410 /// Returns true if the op does a compression to the vector before storing.
2411 /// The node contiguously stores the active elements (integers or floats)
2412 /// in src (those with their respective bit set in writemask k) to unaligned
2413 /// memory at base_addr.
2414 bool isCompressingStore() const { return StoreSDNodeBits.IsCompressing; }
2415
2416 const SDValue &getValue() const { return getOperand(1); }
2417 const SDValue &getBasePtr() const { return getOperand(2); }
2418 const SDValue &getOffset() const { return getOperand(3); }
2419 const SDValue &getMask() const { return getOperand(4); }
2420
2421 static bool classof(const SDNode *N) {
2422 return N->getOpcode() == ISD::MSTORE;
2423 }
2424};
2425
2426/// This is a base class used to represent
2427/// MGATHER and MSCATTER nodes
2428///
2429class MaskedGatherScatterSDNode : public MemSDNode {
2430public:
2431 friend class SelectionDAG;
2432
2433 MaskedGatherScatterSDNode(ISD::NodeType NodeTy, unsigned Order,
2434 const DebugLoc &dl, SDVTList VTs, EVT MemVT,
2435 MachineMemOperand *MMO, ISD::MemIndexType IndexType)
2436 : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
2437 LSBaseSDNodeBits.AddressingMode = IndexType;
2438 assert(getIndexType() == IndexType && "Value truncated")(static_cast <bool> (getIndexType() == IndexType &&
"Value truncated") ? void (0) : __assert_fail ("getIndexType() == IndexType && \"Value truncated\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2438, __extension__ __PRETTY_FUNCTION__))
;
2439 }
2440
2441 /// How is Index applied to BasePtr when computing addresses.
2442 ISD::MemIndexType getIndexType() const {
2443 return static_cast<ISD::MemIndexType>(LSBaseSDNodeBits.AddressingMode);
2444 }
2445 void setIndexType(ISD::MemIndexType IndexType) {
2446 LSBaseSDNodeBits.AddressingMode = IndexType;
2447 }
2448 bool isIndexScaled() const {
2449 return (getIndexType() == ISD::SIGNED_SCALED) ||
2450 (getIndexType() == ISD::UNSIGNED_SCALED);
2451 }
2452 bool isIndexSigned() const {
2453 return (getIndexType() == ISD::SIGNED_SCALED) ||
2454 (getIndexType() == ISD::SIGNED_UNSCALED);
2455 }
2456
2457 // In the both nodes address is Op1, mask is Op2:
2458 // MaskedGatherSDNode (Chain, passthru, mask, base, index, scale)
2459 // MaskedScatterSDNode (Chain, value, mask, base, index, scale)
2460 // Mask is a vector of i1 elements
2461 const SDValue &getBasePtr() const { return getOperand(3); }
2462 const SDValue &getIndex() const { return getOperand(4); }
2463 const SDValue &getMask() const { return getOperand(2); }
2464 const SDValue &getScale() const { return getOperand(5); }
2465
2466 static bool classof(const SDNode *N) {
2467 return N->getOpcode() == ISD::MGATHER ||
2468 N->getOpcode() == ISD::MSCATTER;
2469 }
2470};
2471
2472/// This class is used to represent an MGATHER node
2473///
2474class MaskedGatherSDNode : public MaskedGatherScatterSDNode {
2475public:
2476 friend class SelectionDAG;
2477
2478 MaskedGatherSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2479 EVT MemVT, MachineMemOperand *MMO,
2480 ISD::MemIndexType IndexType, ISD::LoadExtType ETy)
2481 : MaskedGatherScatterSDNode(ISD::MGATHER, Order, dl, VTs, MemVT, MMO,
2482 IndexType) {
2483 LoadSDNodeBits.ExtTy = ETy;
2484 }
2485
2486 const SDValue &getPassThru() const { return getOperand(1); }
2487
2488 ISD::LoadExtType getExtensionType() const {
2489 return ISD::LoadExtType(LoadSDNodeBits.ExtTy);
2490 }
2491
2492 static bool classof(const SDNode *N) {
2493 return N->getOpcode() == ISD::MGATHER;
2494 }
2495};
2496
2497/// This class is used to represent an MSCATTER node
2498///
2499class MaskedScatterSDNode : public MaskedGatherScatterSDNode {
2500public:
2501 friend class SelectionDAG;
2502
2503 MaskedScatterSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2504 EVT MemVT, MachineMemOperand *MMO,
2505 ISD::MemIndexType IndexType, bool IsTrunc)
2506 : MaskedGatherScatterSDNode(ISD::MSCATTER, Order, dl, VTs, MemVT, MMO,
2507 IndexType) {
2508 StoreSDNodeBits.IsTruncating = IsTrunc;
2509 }
2510
2511 /// Return true if the op does a truncation before store.
2512 /// For integers this is the same as doing a TRUNCATE and storing the result.
2513 /// For floats, it is the same as doing an FP_ROUND and storing the result.
2514 bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; }
2515
2516 const SDValue &getValue() const { return getOperand(1); }
2517
2518 static bool classof(const SDNode *N) {
2519 return N->getOpcode() == ISD::MSCATTER;
2520 }
2521};
2522
2523/// An SDNode that represents everything that will be needed
2524/// to construct a MachineInstr. These nodes are created during the
2525/// instruction selection proper phase.
2526///
2527/// Note that the only supported way to set the `memoperands` is by calling the
2528/// `SelectionDAG::setNodeMemRefs` function as the memory management happens
2529/// inside the DAG rather than in the node.
2530class MachineSDNode : public SDNode {
2531private:
2532 friend class SelectionDAG;
2533
2534 MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc &DL, SDVTList VTs)
2535 : SDNode(Opc, Order, DL, VTs) {}
2536
2537 // We use a pointer union between a single `MachineMemOperand` pointer and
2538 // a pointer to an array of `MachineMemOperand` pointers. This is null when
2539 // the number of these is zero, the single pointer variant used when the
2540 // number is one, and the array is used for larger numbers.
2541 //
2542 // The array is allocated via the `SelectionDAG`'s allocator and so will
2543 // always live until the DAG is cleaned up and doesn't require ownership here.
2544 //
2545 // We can't use something simpler like `TinyPtrVector` here because `SDNode`
2546 // subclasses aren't managed in a conforming C++ manner. See the comments on
2547 // `SelectionDAG::MorphNodeTo` which details what all goes on, but the
2548 // constraint here is that these don't manage memory with their constructor or
2549 // destructor and can be initialized to a good state even if they start off
2550 // uninitialized.
2551 PointerUnion<MachineMemOperand *, MachineMemOperand **> MemRefs = {};
2552
2553 // Note that this could be folded into the above `MemRefs` member if doing so
2554 // is advantageous at some point. We don't need to store this in most cases.
2555 // However, at the moment this doesn't appear to make the allocation any
2556 // smaller and makes the code somewhat simpler to read.
2557 int NumMemRefs = 0;
2558
2559public:
2560 using mmo_iterator = ArrayRef<MachineMemOperand *>::const_iterator;
2561
2562 ArrayRef<MachineMemOperand *> memoperands() const {
2563 // Special case the common cases.
2564 if (NumMemRefs == 0)
2565 return {};
2566 if (NumMemRefs == 1)
2567 return makeArrayRef(MemRefs.getAddrOfPtr1(), 1);
2568
2569 // Otherwise we have an actual array.
2570 return makeArrayRef(MemRefs.get<MachineMemOperand **>(), NumMemRefs);
2571 }
2572 mmo_iterator memoperands_begin() const { return memoperands().begin(); }
2573 mmo_iterator memoperands_end() const { return memoperands().end(); }
2574 bool memoperands_empty() const { return memoperands().empty(); }
2575
2576 /// Clear out the memory reference descriptor list.
2577 void clearMemRefs() {
2578 MemRefs = nullptr;
2579 NumMemRefs = 0;
2580 }
2581
2582 static bool classof(const SDNode *N) {
2583 return N->isMachineOpcode();
2584 }
2585};
2586
2587/// An SDNode that records if a register contains a value that is guaranteed to
2588/// be aligned accordingly.
2589class AssertAlignSDNode : public SDNode {
2590 Align Alignment;
2591
2592public:
2593 AssertAlignSDNode(unsigned Order, const DebugLoc &DL, EVT VT, Align A)
2594 : SDNode(ISD::AssertAlign, Order, DL, getSDVTList(VT)), Alignment(A) {}
2595
2596 Align getAlign() const { return Alignment; }
2597
2598 static bool classof(const SDNode *N) {
2599 return N->getOpcode() == ISD::AssertAlign;
2600 }
2601};
2602
2603class SDNodeIterator {
2604 const SDNode *Node;
2605 unsigned Operand;
2606
2607 SDNodeIterator(const SDNode *N, unsigned Op) : Node(N), Operand(Op) {}
2608
2609public:
2610 using iterator_category = std::forward_iterator_tag;
2611 using value_type = SDNode;
2612 using difference_type = std::ptrdiff_t;
2613 using pointer = value_type *;
2614 using reference = value_type &;
2615
2616 bool operator==(const SDNodeIterator& x) const {
2617 return Operand == x.Operand;
2618 }
2619 bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
2620
2621 pointer operator*() const {
2622 return Node->getOperand(Operand).getNode();
2623 }
2624 pointer operator->() const { return operator*(); }
2625
2626 SDNodeIterator& operator++() { // Preincrement
2627 ++Operand;
2628 return *this;
2629 }
2630 SDNodeIterator operator++(int) { // Postincrement
2631 SDNodeIterator tmp = *this; ++*this; return tmp;
2632 }
2633 size_t operator-(SDNodeIterator Other) const {
2634 assert(Node == Other.Node &&(static_cast <bool> (Node == Other.Node && "Cannot compare iterators of two different nodes!"
) ? void (0) : __assert_fail ("Node == Other.Node && \"Cannot compare iterators of two different nodes!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2635, __extension__ __PRETTY_FUNCTION__))
2635 "Cannot compare iterators of two different nodes!")(static_cast <bool> (Node == Other.Node && "Cannot compare iterators of two different nodes!"
) ? void (0) : __assert_fail ("Node == Other.Node && \"Cannot compare iterators of two different nodes!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/SelectionDAGNodes.h"
, 2635, __extension__ __PRETTY_FUNCTION__))
;
2636 return Operand - Other.Operand;
2637 }
2638
2639 static SDNodeIterator begin(const SDNode *N) { return SDNodeIterator(N, 0); }
2640 static SDNodeIterator end (const SDNode *N) {
2641 return SDNodeIterator(N, N->getNumOperands());
2642 }
2643
2644 unsigned getOperand() const { return Operand; }
2645 const SDNode *getNode() const { return Node; }
2646};
2647
2648template <> struct GraphTraits<SDNode*> {
2649 using NodeRef = SDNode *;
2650 using ChildIteratorType = SDNodeIterator;
2651
2652 static NodeRef getEntryNode(SDNode *N) { return N; }
2653
2654 static ChildIteratorType child_begin(NodeRef N) {
2655 return SDNodeIterator::begin(N);
2656 }
2657
2658 static ChildIteratorType child_end(NodeRef N) {
2659 return SDNodeIterator::end(N);
2660 }
2661};
2662
2663/// A representation of the largest SDNode, for use in sizeof().
2664///
2665/// This needs to be a union because the largest node differs on 32 bit systems
2666/// with 4 and 8 byte pointer alignment, respectively.
2667using LargestSDNode = AlignedCharArrayUnion<AtomicSDNode, TargetIndexSDNode,
2668 BlockAddressSDNode,
2669 GlobalAddressSDNode,
2670 PseudoProbeSDNode>;
2671
2672/// The SDNode class with the greatest alignment requirement.
2673using MostAlignedSDNode = GlobalAddressSDNode;
2674
2675namespace ISD {
2676
2677 /// Returns true if the specified node is a non-extending and unindexed load.
2678 inline bool isNormalLoad(const SDNode *N) {
2679 const LoadSDNode *Ld = dyn_cast<LoadSDNode>(N);
2680 return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD &&
2681 Ld->getAddressingMode() == ISD::UNINDEXED;
2682 }
2683
2684 /// Returns true if the specified node is a non-extending load.
2685 inline bool isNON_EXTLoad(const SDNode *N) {
2686 return isa<LoadSDNode>(N) &&
2687 cast<LoadSDNode>(N)->getExtensionType() == ISD::NON_EXTLOAD;
2688 }
2689
2690 /// Returns true if the specified node is a EXTLOAD.
2691 inline bool isEXTLoad(const SDNode *N) {
2692 return isa<LoadSDNode>(N) &&
2693 cast<LoadSDNode>(N)->getExtensionType() == ISD::EXTLOAD;
2694 }
2695
2696 /// Returns true if the specified node is a SEXTLOAD.
2697 inline bool isSEXTLoad(const SDNode *N) {
2698 return isa<LoadSDNode>(N) &&
2699 cast<LoadSDNode>(N)->getExtensionType() == ISD::SEXTLOAD;
2700 }
2701
2702 /// Returns true if the specified node is a ZEXTLOAD.
2703 inline bool isZEXTLoad(const SDNode *N) {
2704 return isa<LoadSDNode>(N) &&
2705 cast<LoadSDNode>(N)->getExtensionType() == ISD::ZEXTLOAD;
2706 }
2707
2708 /// Returns true if the specified node is an unindexed load.
2709 inline bool isUNINDEXEDLoad(const SDNode *N) {
2710 return isa<LoadSDNode>(N) &&
2711 cast<LoadSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2712 }
2713
2714 /// Returns true if the specified node is a non-truncating
2715 /// and unindexed store.
2716 inline bool isNormalStore(const SDNode *N) {
2717 const StoreSDNode *St = dyn_cast<StoreSDNode>(N);
2718 return St && !St->isTruncatingStore() &&
2719 St->getAddressingMode() == ISD::UNINDEXED;
2720 }
2721
2722 /// Returns true if the specified node is an unindexed store.
2723 inline bool isUNINDEXEDStore(const SDNode *N) {
2724 return isa<StoreSDNode>(N) &&
2725 cast<StoreSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2726 }
2727
2728 /// Attempt to match a unary predicate against a scalar/splat constant or
2729 /// every element of a constant BUILD_VECTOR.
2730 /// If AllowUndef is true, then UNDEF elements will pass nullptr to Match.
2731 bool matchUnaryPredicate(SDValue Op,
2732 std::function<bool(ConstantSDNode *)> Match,
2733 bool AllowUndefs = false);
2734
2735 /// Attempt to match a binary predicate against a pair of scalar/splat
2736 /// constants or every element of a pair of constant BUILD_VECTORs.
2737 /// If AllowUndef is true, then UNDEF elements will pass nullptr to Match.
2738 /// If AllowTypeMismatch is true then RetType + ArgTypes don't need to match.
2739 bool matchBinaryPredicate(
2740 SDValue LHS, SDValue RHS,
2741 std::function<bool(ConstantSDNode *, ConstantSDNode *)> Match,
2742 bool AllowUndefs = false, bool AllowTypeMismatch = false);
2743
2744 /// Returns true if the specified value is the overflow result from one
2745 /// of the overflow intrinsic nodes.
2746 inline bool isOverflowIntrOpRes(SDValue Op) {
2747 unsigned Opc = Op.getOpcode();
2748 return (Op.getResNo() == 1 &&
2749 (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
2750 Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO));
2751 }
2752
2753} // end namespace ISD
2754
2755} // end namespace llvm
2756
2757#endif // LLVM_CODEGEN_SELECTIONDAGNODES_H

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/IR/GlobalVariable.h

1//===-- llvm/GlobalVariable.h - GlobalVariable class ------------*- 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 contains the declaration of the GlobalVariable class, which
10// represents a single global variable (or constant) in the VM.
11//
12// Global variables are constant pointers that refer to hunks of space that are
13// allocated by either the VM, or by the linker in a static compiler. A global
14// variable may have an initial value, which is copied into the executables .data
15// area. Global Constants are required to have initializers.
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_IR_GLOBALVARIABLE_H
20#define LLVM_IR_GLOBALVARIABLE_H
21
22#include "llvm/ADT/Twine.h"
23#include "llvm/ADT/ilist_node.h"
24#include "llvm/IR/Attributes.h"
25#include "llvm/IR/GlobalObject.h"
26#include "llvm/IR/OperandTraits.h"
27#include "llvm/IR/Value.h"
28#include <cassert>
29#include <cstddef>
30
31namespace llvm {
32
33class Constant;
34class Module;
35
36template <typename ValueSubClass> class SymbolTableListTraits;
37class DIGlobalVariable;
38class DIGlobalVariableExpression;
39
40class GlobalVariable : public GlobalObject, public ilist_node<GlobalVariable> {
41 friend class SymbolTableListTraits<GlobalVariable>;
42
43 AttributeSet Attrs;
44 bool isConstantGlobal : 1; // Is this a global constant?
45 bool isExternallyInitializedConstant : 1; // Is this a global whose value
46 // can change from its initial
47 // value before global
48 // initializers are run?
49
50public:
51 /// GlobalVariable ctor - If a parent module is specified, the global is
52 /// automatically inserted into the end of the specified modules global list.
53 GlobalVariable(Type *Ty, bool isConstant, LinkageTypes Linkage,
54 Constant *Initializer = nullptr, const Twine &Name = "",
55 ThreadLocalMode = NotThreadLocal, unsigned AddressSpace = 0,
56 bool isExternallyInitialized = false);
57 /// GlobalVariable ctor - This creates a global and inserts it before the
58 /// specified other global.
59 GlobalVariable(Module &M, Type *Ty, bool isConstant, LinkageTypes Linkage,
60 Constant *Initializer, const Twine &Name = "",
61 GlobalVariable *InsertBefore = nullptr,
62 ThreadLocalMode = NotThreadLocal,
63 Optional<unsigned> AddressSpace = None,
64 bool isExternallyInitialized = false);
65 GlobalVariable(const GlobalVariable &) = delete;
66 GlobalVariable &operator=(const GlobalVariable &) = delete;
67
68 ~GlobalVariable() {
69 dropAllReferences();
70 }
71
72 // allocate space for exactly one operand
73 void *operator new(size_t s) {
74 return User::operator new(s, 1);
75 }
76
77 // delete space for exactly one operand as created in the corresponding new operator
78 void operator delete(void *ptr){
79 assert(ptr != nullptr && "must not be nullptr")(static_cast <bool> (ptr != nullptr && "must not be nullptr"
) ? void (0) : __assert_fail ("ptr != nullptr && \"must not be nullptr\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/IR/GlobalVariable.h"
, 79, __extension__ __PRETTY_FUNCTION__))
;
80 User *Obj = static_cast<User *>(ptr);
81 // Number of operands can be set to 0 after construction and initialization. Make sure
82 // that number of operands is reset to 1, as this is needed in User::operator delete
83 Obj->setGlobalVariableNumOperands(1);
84 User::operator delete(Obj);
85 }
86
87 /// Provide fast operand accessors
88 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value)public: inline Value *getOperand(unsigned) const; inline void
setOperand(unsigned, Value*); inline op_iterator op_begin();
inline const_op_iterator op_begin() const; inline op_iterator
op_end(); inline const_op_iterator op_end() const; protected
: template <int> inline Use &Op(); template <int
> inline const Use &Op() const; public: inline unsigned
getNumOperands() const
;
89
90 /// Definitions have initializers, declarations don't.
91 ///
92 inline bool hasInitializer() const { return !isDeclaration(); }
31
Assuming the condition is true
32
Returning the value 1, which participates in a condition later
93
94 /// hasDefinitiveInitializer - Whether the global variable has an initializer,
95 /// and any other instances of the global (this can happen due to weak
96 /// linkage) are guaranteed to have the same initializer.
97 ///
98 /// Note that if you want to transform a global, you must use
99 /// hasUniqueInitializer() instead, because of the *_odr linkage type.
100 ///
101 /// Example:
102 ///
103 /// @a = global SomeType* null - Initializer is both definitive and unique.
104 ///
105 /// @b = global weak SomeType* null - Initializer is neither definitive nor
106 /// unique.
107 ///
108 /// @c = global weak_odr SomeType* null - Initializer is definitive, but not
109 /// unique.
110 inline bool hasDefinitiveInitializer() const {
111 return hasInitializer() &&
112 // The initializer of a global variable may change to something arbitrary
113 // at link time.
114 !isInterposable() &&
115 // The initializer of a global variable with the externally_initialized
116 // marker may change at runtime before C++ initializers are evaluated.
117 !isExternallyInitialized();
118 }
119
120 /// hasUniqueInitializer - Whether the global variable has an initializer, and
121 /// any changes made to the initializer will turn up in the final executable.
122 inline bool hasUniqueInitializer() const {
123 return
124 // We need to be sure this is the definition that will actually be used
125 isStrongDefinitionForLinker() &&
126 // It is not safe to modify initializers of global variables with the
127 // external_initializer marker since the value may be changed at runtime
128 // before C++ initializers are evaluated.
129 !isExternallyInitialized();
130 }
131
132 /// getInitializer - Return the initializer for this global variable. It is
133 /// illegal to call this method if the global is external, because we cannot
134 /// tell what the value is initialized to!
135 ///
136 inline const Constant *getInitializer() const {
137 assert(hasInitializer() && "GV doesn't have initializer!")(static_cast <bool> (hasInitializer() && "GV doesn't have initializer!"
) ? void (0) : __assert_fail ("hasInitializer() && \"GV doesn't have initializer!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/IR/GlobalVariable.h"
, 137, __extension__ __PRETTY_FUNCTION__))
;
138 return static_cast<Constant*>(Op<0>().get());
139 }
140 inline Constant *getInitializer() {
141 assert(hasInitializer() && "GV doesn't have initializer!")(static_cast <bool> (hasInitializer() && "GV doesn't have initializer!"
) ? void (0) : __assert_fail ("hasInitializer() && \"GV doesn't have initializer!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/IR/GlobalVariable.h"
, 141, __extension__ __PRETTY_FUNCTION__))
;
142 return static_cast<Constant*>(Op<0>().get());
143 }
144 /// setInitializer - Sets the initializer for this global variable, removing
145 /// any existing initializer if InitVal==NULL. If this GV has type T*, the
146 /// initializer must have type T.
147 void setInitializer(Constant *InitVal);
148
149 /// If the value is a global constant, its value is immutable throughout the
150 /// runtime execution of the program. Assigning a value into the constant
151 /// leads to undefined behavior.
152 ///
153 bool isConstant() const { return isConstantGlobal; }
154 void setConstant(bool Val) { isConstantGlobal = Val; }
155
156 bool isExternallyInitialized() const {
157 return isExternallyInitializedConstant;
158 }
159 void setExternallyInitialized(bool Val) {
160 isExternallyInitializedConstant = Val;
161 }
162
163 /// copyAttributesFrom - copy all additional attributes (those not needed to
164 /// create a GlobalVariable) from the GlobalVariable Src to this one.
165 void copyAttributesFrom(const GlobalVariable *Src);
166
167 /// removeFromParent - This method unlinks 'this' from the containing module,
168 /// but does not delete it.
169 ///
170 void removeFromParent();
171
172 /// eraseFromParent - This method unlinks 'this' from the containing module
173 /// and deletes it.
174 ///
175 void eraseFromParent();
176
177 /// Drop all references in preparation to destroy the GlobalVariable. This
178 /// drops not only the reference to the initializer but also to any metadata.
179 void dropAllReferences();
180
181 /// Attach a DIGlobalVariableExpression.
182 void addDebugInfo(DIGlobalVariableExpression *GV);
183
184 /// Fill the vector with all debug info attachements.
185 void getDebugInfo(SmallVectorImpl<DIGlobalVariableExpression *> &GVs) const;
186
187 /// Add attribute to this global.
188 void addAttribute(Attribute::AttrKind Kind) {
189 Attrs = Attrs.addAttribute(getContext(), Kind);
190 }
191
192 /// Add attribute to this global.
193 void addAttribute(StringRef Kind, StringRef Val = StringRef()) {
194 Attrs = Attrs.addAttribute(getContext(), Kind, Val);
195 }
196
197 /// Return true if the attribute exists.
198 bool hasAttribute(Attribute::AttrKind Kind) const {
199 return Attrs.hasAttribute(Kind);
200 }
201
202 /// Return true if the attribute exists.
203 bool hasAttribute(StringRef Kind) const {
204 return Attrs.hasAttribute(Kind);
205 }
206
207 /// Return true if any attributes exist.
208 bool hasAttributes() const {
209 return Attrs.hasAttributes();
210 }
211
212 /// Return the attribute object.
213 Attribute getAttribute(Attribute::AttrKind Kind) const {
214 return Attrs.getAttribute(Kind);
215 }
216
217 /// Return the attribute object.
218 Attribute getAttribute(StringRef Kind) const {
219 return Attrs.getAttribute(Kind);
220 }
221
222 /// Return the attribute set for this global
223 AttributeSet getAttributes() const {
224 return Attrs;
225 }
226
227 /// Return attribute set as list with index.
228 /// FIXME: This may not be required once ValueEnumerators
229 /// in bitcode-writer can enumerate attribute-set.
230 AttributeList getAttributesAsList(unsigned index) const {
231 if (!hasAttributes())
232 return AttributeList();
233 std::pair<unsigned, AttributeSet> AS[1] = {{index, Attrs}};
234 return AttributeList::get(getContext(), AS);
235 }
236
237 /// Set attribute list for this global
238 void setAttributes(AttributeSet A) {
239 Attrs = A;
240 }
241
242 /// Check if section name is present
243 bool hasImplicitSection() const {
244 return getAttributes().hasAttribute("bss-section") ||
245 getAttributes().hasAttribute("data-section") ||
246 getAttributes().hasAttribute("relro-section") ||
247 getAttributes().hasAttribute("rodata-section");
248 }
249
250 // Methods for support type inquiry through isa, cast, and dyn_cast:
251 static bool classof(const Value *V) {
252 return V->getValueID() == Value::GlobalVariableVal;
253 }
254};
255
256template <>
257struct OperandTraits<GlobalVariable> :
258 public OptionalOperandTraits<GlobalVariable> {
259};
260
261DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GlobalVariable, Value)GlobalVariable::op_iterator GlobalVariable::op_begin() { return
OperandTraits<GlobalVariable>::op_begin(this); } GlobalVariable
::const_op_iterator GlobalVariable::op_begin() const { return
OperandTraits<GlobalVariable>::op_begin(const_cast<
GlobalVariable*>(this)); } GlobalVariable::op_iterator GlobalVariable
::op_end() { return OperandTraits<GlobalVariable>::op_end
(this); } GlobalVariable::const_op_iterator GlobalVariable::op_end
() const { return OperandTraits<GlobalVariable>::op_end
(const_cast<GlobalVariable*>(this)); } Value *GlobalVariable
::getOperand(unsigned i_nocapture) const { (static_cast <bool
> (i_nocapture < OperandTraits<GlobalVariable>::operands
(this) && "getOperand() out of range!") ? void (0) : __assert_fail
("i_nocapture < OperandTraits<GlobalVariable>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/IR/GlobalVariable.h"
, 261, __extension__ __PRETTY_FUNCTION__)); return cast_or_null
<Value>( OperandTraits<GlobalVariable>::op_begin(
const_cast<GlobalVariable*>(this))[i_nocapture].get());
} void GlobalVariable::setOperand(unsigned i_nocapture, Value
*Val_nocapture) { (static_cast <bool> (i_nocapture <
OperandTraits<GlobalVariable>::operands(this) &&
"setOperand() out of range!") ? void (0) : __assert_fail ("i_nocapture < OperandTraits<GlobalVariable>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/IR/GlobalVariable.h"
, 261, __extension__ __PRETTY_FUNCTION__)); OperandTraits<
GlobalVariable>::op_begin(this)[i_nocapture] = Val_nocapture
; } unsigned GlobalVariable::getNumOperands() const { return OperandTraits
<GlobalVariable>::operands(this); } template <int Idx_nocapture
> Use &GlobalVariable::Op() { return this->OpFrom<
Idx_nocapture>(this); } template <int Idx_nocapture>
const Use &GlobalVariable::Op() const { return this->
OpFrom<Idx_nocapture>(this); }
262
263} // end namespace llvm
264
265#endif // LLVM_IR_GLOBALVARIABLE_H

/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_tree.h

1// RB tree implementation -*- C++ -*-
2
3// Copyright (C) 2001-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1994
40 * Hewlett-Packard Company
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Hewlett-Packard Company makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 *
50 *
51 */
52
53/** @file bits/stl_tree.h
54 * This is an internal header file, included by other library headers.
55 * Do not attempt to use it directly. @headername{map,set}
56 */
57
58#ifndef _STL_TREE_H1
59#define _STL_TREE_H1 1
60
61#pragma GCC system_header
62
63#include <bits/stl_algobase.h>
64#include <bits/allocator.h>
65#include <bits/stl_function.h>
66#include <bits/cpp_type_traits.h>
67#include <ext/alloc_traits.h>
68#if __cplusplus201402L >= 201103L
69# include <ext/aligned_buffer.h>
70#endif
71#if __cplusplus201402L > 201402L
72# include <bits/node_handle.h>
73#endif
74
75namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
76{
77_GLIBCXX_BEGIN_NAMESPACE_VERSION
78
79#if __cplusplus201402L > 201103L
80# define __cpp_lib_generic_associative_lookup201304 201304
81#endif
82
83 // Red-black tree class, designed for use in implementing STL
84 // associative containers (set, multiset, map, and multimap). The
85 // insertion and deletion algorithms are based on those in Cormen,
86 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
87 // 1990), except that
88 //
89 // (1) the header cell is maintained with links not only to the root
90 // but also to the leftmost node of the tree, to enable constant
91 // time begin(), and to the rightmost node of the tree, to enable
92 // linear time performance when used with the generic set algorithms
93 // (set_union, etc.)
94 //
95 // (2) when a node being deleted has two children its successor node
96 // is relinked into its place, rather than copied, so that the only
97 // iterators invalidated are those referring to the deleted node.
98
99 enum _Rb_tree_color { _S_red = false, _S_black = true };
100
101 struct _Rb_tree_node_base
102 {
103 typedef _Rb_tree_node_base* _Base_ptr;
104 typedef const _Rb_tree_node_base* _Const_Base_ptr;
105
106 _Rb_tree_color _M_color;
107 _Base_ptr _M_parent;
108 _Base_ptr _M_left;
109 _Base_ptr _M_right;
110
111 static _Base_ptr
112 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
113 {
114 while (__x->_M_left != 0) __x = __x->_M_left;
115 return __x;
116 }
117
118 static _Const_Base_ptr
119 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
120 {
121 while (__x->_M_left != 0) __x = __x->_M_left;
122 return __x;
123 }
124
125 static _Base_ptr
126 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
127 {
128 while (__x->_M_right != 0) __x = __x->_M_right;
129 return __x;
130 }
131
132 static _Const_Base_ptr
133 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
134 {
135 while (__x->_M_right != 0) __x = __x->_M_right;
136 return __x;
137 }
138 };
139
140 // Helper type offering value initialization guarantee on the compare functor.
141 template<typename _Key_compare>
142 struct _Rb_tree_key_compare
143 {
144 _Key_compare _M_key_compare;
145
146 _Rb_tree_key_compare()
147 _GLIBCXX_NOEXCEPT_IF(noexcept(is_nothrow_default_constructible<_Key_compare>
::value)
148 is_nothrow_default_constructible<_Key_compare>::value)noexcept(is_nothrow_default_constructible<_Key_compare>
::value)
149 : _M_key_compare()
150 { }
151
152 _Rb_tree_key_compare(const _Key_compare& __comp)
153 : _M_key_compare(__comp)
154 { }
155
156#if __cplusplus201402L >= 201103L
157 // Copy constructor added for consistency with C++98 mode.
158 _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
159
160 _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
161 noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
162 : _M_key_compare(__x._M_key_compare)
163 { }
164#endif
165 };
166
167 // Helper type to manage default initialization of node count and header.
168 struct _Rb_tree_header
169 {
170 _Rb_tree_node_base _M_header;
171 size_t _M_node_count; // Keeps track of size of tree.
172
173 _Rb_tree_header() _GLIBCXX_NOEXCEPTnoexcept
174 {
175 _M_header._M_color = _S_red;
176 _M_reset();
177 }
178
179#if __cplusplus201402L >= 201103L
180 _Rb_tree_header(_Rb_tree_header&& __x) noexcept
181 {
182 if (__x._M_header._M_parent != nullptr)
183 _M_move_data(__x);
184 else
185 {
186 _M_header._M_color = _S_red;
187 _M_reset();
188 }
189 }
190#endif
191
192 void
193 _M_move_data(_Rb_tree_header& __from)
194 {
195 _M_header._M_color = __from._M_header._M_color;
196 _M_header._M_parent = __from._M_header._M_parent;
197 _M_header._M_left = __from._M_header._M_left;
198 _M_header._M_right = __from._M_header._M_right;
199 _M_header._M_parent->_M_parent = &_M_header;
200 _M_node_count = __from._M_node_count;
201
202 __from._M_reset();
203 }
204
205 void
206 _M_reset()
207 {
208 _M_header._M_parent = 0;
209 _M_header._M_left = &_M_header;
210 _M_header._M_right = &_M_header;
211 _M_node_count = 0;
212 }
213 };
214
215 template<typename _Val>
216 struct _Rb_tree_node : public _Rb_tree_node_base
217 {
218 typedef _Rb_tree_node<_Val>* _Link_type;
219
220#if __cplusplus201402L < 201103L
221 _Val _M_value_field;
222
223 _Val*
224 _M_valptr()
225 { return std::__addressof(_M_value_field); }
226
227 const _Val*
228 _M_valptr() const
229 { return std::__addressof(_M_value_field); }
230#else
231 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
232
233 _Val*
234 _M_valptr()
235 { return _M_storage._M_ptr(); }
236
237 const _Val*
238 _M_valptr() const
239 { return _M_storage._M_ptr(); }
240#endif
241 };
242
243 _GLIBCXX_PURE__attribute__ ((__pure__)) _Rb_tree_node_base*
244 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
245
246 _GLIBCXX_PURE__attribute__ ((__pure__)) const _Rb_tree_node_base*
247 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
248
249 _GLIBCXX_PURE__attribute__ ((__pure__)) _Rb_tree_node_base*
250 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
251
252 _GLIBCXX_PURE__attribute__ ((__pure__)) const _Rb_tree_node_base*
253 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
254
255 template<typename _Tp>
256 struct _Rb_tree_iterator
257 {
258 typedef _Tp value_type;
259 typedef _Tp& reference;
260 typedef _Tp* pointer;
261
262 typedef bidirectional_iterator_tag iterator_category;
263 typedef ptrdiff_t difference_type;
264
265 typedef _Rb_tree_iterator<_Tp> _Self;
266 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
267 typedef _Rb_tree_node<_Tp>* _Link_type;
268
269 _Rb_tree_iterator() _GLIBCXX_NOEXCEPTnoexcept
270 : _M_node() { }
271
272 explicit
273 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
274 : _M_node(__x) { }
275
276 reference
277 operator*() const _GLIBCXX_NOEXCEPTnoexcept
278 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
279
280 pointer
281 operator->() const _GLIBCXX_NOEXCEPTnoexcept
282 { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
283
284 _Self&
285 operator++() _GLIBCXX_NOEXCEPTnoexcept
286 {
287 _M_node = _Rb_tree_increment(_M_node);
288 return *this;
289 }
290
291 _Self
292 operator++(int) _GLIBCXX_NOEXCEPTnoexcept
293 {
294 _Self __tmp = *this;
295 _M_node = _Rb_tree_increment(_M_node);
296 return __tmp;
297 }
298
299 _Self&
300 operator--() _GLIBCXX_NOEXCEPTnoexcept
301 {
302 _M_node = _Rb_tree_decrement(_M_node);
303 return *this;
304 }
305
306 _Self
307 operator--(int) _GLIBCXX_NOEXCEPTnoexcept
308 {
309 _Self __tmp = *this;
310 _M_node = _Rb_tree_decrement(_M_node);
311 return __tmp;
312 }
313
314 friend bool
315 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
316 { return __x._M_node == __y._M_node; }
317
318#if ! __cpp_lib_three_way_comparison
319 friend bool
320 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
321 { return __x._M_node != __y._M_node; }
37
Assuming '__x._M_node' is not equal to '__y._M_node'
38
Returning the value 1, which participates in a condition later
322#endif
323
324 _Base_ptr _M_node;
325 };
326
327 template<typename _Tp>
328 struct _Rb_tree_const_iterator
329 {
330 typedef _Tp value_type;
331 typedef const _Tp& reference;
332 typedef const _Tp* pointer;
333
334 typedef _Rb_tree_iterator<_Tp> iterator;
335
336 typedef bidirectional_iterator_tag iterator_category;
337 typedef ptrdiff_t difference_type;
338
339 typedef _Rb_tree_const_iterator<_Tp> _Self;
340 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
341 typedef const _Rb_tree_node<_Tp>* _Link_type;
342
343 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPTnoexcept
344 : _M_node() { }
345
346 explicit
347 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
348 : _M_node(__x) { }
349
350 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPTnoexcept
351 : _M_node(__it._M_node) { }
352
353 iterator
354 _M_const_cast() const _GLIBCXX_NOEXCEPTnoexcept
355 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
356
357 reference
358 operator*() const _GLIBCXX_NOEXCEPTnoexcept
359 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
360
361 pointer
362 operator->() const _GLIBCXX_NOEXCEPTnoexcept
363 { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
364
365 _Self&
366 operator++() _GLIBCXX_NOEXCEPTnoexcept
367 {
368 _M_node = _Rb_tree_increment(_M_node);
369 return *this;
370 }
371
372 _Self
373 operator++(int) _GLIBCXX_NOEXCEPTnoexcept
374 {
375 _Self __tmp = *this;
376 _M_node = _Rb_tree_increment(_M_node);
377 return __tmp;
378 }
379
380 _Self&
381 operator--() _GLIBCXX_NOEXCEPTnoexcept
382 {
383 _M_node = _Rb_tree_decrement(_M_node);
384 return *this;
385 }
386
387 _Self
388 operator--(int) _GLIBCXX_NOEXCEPTnoexcept
389 {
390 _Self __tmp = *this;
391 _M_node = _Rb_tree_decrement(_M_node);
392 return __tmp;
393 }
394
395 friend bool
396 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
397 { return __x._M_node == __y._M_node; }
398
399#if ! __cpp_lib_three_way_comparison
400 friend bool
401 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
402 { return __x._M_node != __y._M_node; }
403#endif
404
405 _Base_ptr _M_node;
406 };
407
408 void
409 _Rb_tree_insert_and_rebalance(const bool __insert_left,
410 _Rb_tree_node_base* __x,
411 _Rb_tree_node_base* __p,
412 _Rb_tree_node_base& __header) throw ();
413
414 _Rb_tree_node_base*
415 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
416 _Rb_tree_node_base& __header) throw ();
417
418#if __cplusplus201402L >= 201402L
419 template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
420 struct __has_is_transparent
421 { };
422
423 template<typename _Cmp, typename _SfinaeType>
424 struct __has_is_transparent<_Cmp, _SfinaeType,
425 __void_t<typename _Cmp::is_transparent>>
426 { typedef void type; };
427
428 template<typename _Cmp, typename _SfinaeType>
429 using __has_is_transparent_t
430 = typename __has_is_transparent<_Cmp, _SfinaeType>::type;
431#endif
432
433#if __cplusplus201402L > 201402L
434 template<typename _Tree1, typename _Cmp2>
435 struct _Rb_tree_merge_helper { };
436#endif
437
438 template<typename _Key, typename _Val, typename _KeyOfValue,
439 typename _Compare, typename _Alloc = allocator<_Val> >
440 class _Rb_tree
441 {
442 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
443 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
444
445 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
446
447 protected:
448 typedef _Rb_tree_node_base* _Base_ptr;
449 typedef const _Rb_tree_node_base* _Const_Base_ptr;
450 typedef _Rb_tree_node<_Val>* _Link_type;
451 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
452
453 private:
454 // Functor recycling a pool of nodes and using allocation once the pool
455 // is empty.
456 struct _Reuse_or_alloc_node
457 {
458 _Reuse_or_alloc_node(_Rb_tree& __t)
459 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
460 {
461 if (_M_root)
462 {
463 _M_root->_M_parent = 0;
464
465 if (_M_nodes->_M_left)
466 _M_nodes = _M_nodes->_M_left;
467 }
468 else
469 _M_nodes = 0;
470 }
471
472#if __cplusplus201402L >= 201103L
473 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
474#endif
475
476 ~_Reuse_or_alloc_node()
477 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
478
479 template<typename _Arg>
480 _Link_type
481#if __cplusplus201402L < 201103L
482 operator()(const _Arg& __arg)
483#else
484 operator()(_Arg&& __arg)
485#endif
486 {
487 _Link_type __node = static_cast<_Link_type>(_M_extract());
488 if (__node)
489 {
490 _M_t._M_destroy_node(__node);
491 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)std::forward<_Arg>(__arg));
492 return __node;
493 }
494
495 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)std::forward<_Arg>(__arg));
496 }
497
498 private:
499 _Base_ptr
500 _M_extract()
501 {
502 if (!_M_nodes)
503 return _M_nodes;
504
505 _Base_ptr __node = _M_nodes;
506 _M_nodes = _M_nodes->_M_parent;
507 if (_M_nodes)
508 {
509 if (_M_nodes->_M_right == __node)
510 {
511 _M_nodes->_M_right = 0;
512
513 if (_M_nodes->_M_left)
514 {
515 _M_nodes = _M_nodes->_M_left;
516
517 while (_M_nodes->_M_right)
518 _M_nodes = _M_nodes->_M_right;
519
520 if (_M_nodes->_M_left)
521 _M_nodes = _M_nodes->_M_left;
522 }
523 }
524 else // __node is on the left.
525 _M_nodes->_M_left = 0;
526 }
527 else
528 _M_root = 0;
529
530 return __node;
531 }
532
533 _Base_ptr _M_root;
534 _Base_ptr _M_nodes;
535 _Rb_tree& _M_t;
536 };
537
538 // Functor similar to the previous one but without any pool of nodes to
539 // recycle.
540 struct _Alloc_node
541 {
542 _Alloc_node(_Rb_tree& __t)
543 : _M_t(__t) { }
544
545 template<typename _Arg>
546 _Link_type
547#if __cplusplus201402L < 201103L
548 operator()(const _Arg& __arg) const
549#else
550 operator()(_Arg&& __arg) const
551#endif
552 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)std::forward<_Arg>(__arg)); }
553
554 private:
555 _Rb_tree& _M_t;
556 };
557
558 public:
559 typedef _Key key_type;
560 typedef _Val value_type;
561 typedef value_type* pointer;
562 typedef const value_type* const_pointer;
563 typedef value_type& reference;
564 typedef const value_type& const_reference;
565 typedef size_t size_type;
566 typedef ptrdiff_t difference_type;
567 typedef _Alloc allocator_type;
568
569 _Node_allocator&
570 _M_get_Node_allocator() _GLIBCXX_NOEXCEPTnoexcept
571 { return this->_M_impl; }
572
573 const _Node_allocator&
574 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPTnoexcept
575 { return this->_M_impl; }
576
577 allocator_type
578 get_allocator() const _GLIBCXX_NOEXCEPTnoexcept
579 { return allocator_type(_M_get_Node_allocator()); }
580
581 protected:
582 _Link_type
583 _M_get_node()
584 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
585
586 void
587 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPTnoexcept
588 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
589
590#if __cplusplus201402L < 201103L
591 void
592 _M_construct_node(_Link_type __node, const value_type& __x)
593 {
594 __tryif (true)
595 { get_allocator().construct(__node->_M_valptr(), __x); }
596 __catch(...)if (false)
597 {
598 _M_put_node(__node);
599 __throw_exception_again;
600 }
601 }
602
603 _Link_type
604 _M_create_node(const value_type& __x)
605 {
606 _Link_type __tmp = _M_get_node();
607 _M_construct_node(__tmp, __x);
608 return __tmp;
609 }
610#else
611 template<typename... _Args>
612 void
613 _M_construct_node(_Link_type __node, _Args&&... __args)
614 {
615 __tryif (true)
616 {
617 ::new(__node) _Rb_tree_node<_Val>;
618 _Alloc_traits::construct(_M_get_Node_allocator(),
619 __node->_M_valptr(),
620 std::forward<_Args>(__args)...);
621 }
622 __catch(...)if (false)
623 {
624 __node->~_Rb_tree_node<_Val>();
625 _M_put_node(__node);
626 __throw_exception_again;
627 }
628 }
629
630 template<typename... _Args>
631 _Link_type
632 _M_create_node(_Args&&... __args)
633 {
634 _Link_type __tmp = _M_get_node();
635 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
636 return __tmp;
637 }
638#endif
639
640 void
641 _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPTnoexcept
642 {
643#if __cplusplus201402L < 201103L
644 get_allocator().destroy(__p->_M_valptr());
645#else
646 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
647 __p->~_Rb_tree_node<_Val>();
648#endif
649 }
650
651 void
652 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPTnoexcept
653 {
654 _M_destroy_node(__p);
655 _M_put_node(__p);
656 }
657
658 template<typename _NodeGen>
659 _Link_type
660 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
661 {
662 _Link_type __tmp = __node_gen(*__x->_M_valptr());
663 __tmp->_M_color = __x->_M_color;
664 __tmp->_M_left = 0;
665 __tmp->_M_right = 0;
666 return __tmp;
667 }
668
669 protected:
670#if _GLIBCXX_INLINE_VERSION0
671 template<typename _Key_compare>
672#else
673 // Unused _Is_pod_comparator is kept as it is part of mangled name.
674 template<typename _Key_compare,
675 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
676#endif
677 struct _Rb_tree_impl
678 : public _Node_allocator
679 , public _Rb_tree_key_compare<_Key_compare>
680 , public _Rb_tree_header
681 {
682 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
683
684 _Rb_tree_impl()
685 _GLIBCXX_NOEXCEPT_IF(noexcept(is_nothrow_default_constructible<_Node_allocator>
::value && is_nothrow_default_constructible<_Base_key_compare
>::value)
686 is_nothrow_default_constructible<_Node_allocator>::valuenoexcept(is_nothrow_default_constructible<_Node_allocator>
::value && is_nothrow_default_constructible<_Base_key_compare
>::value)
687 && is_nothrow_default_constructible<_Base_key_compare>::value )noexcept(is_nothrow_default_constructible<_Node_allocator>
::value && is_nothrow_default_constructible<_Base_key_compare
>::value)
688 : _Node_allocator()
689 { }
690
691 _Rb_tree_impl(const _Rb_tree_impl& __x)
692 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
693 , _Base_key_compare(__x._M_key_compare)
694 { }
695
696#if __cplusplus201402L < 201103L
697 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
698 : _Node_allocator(__a), _Base_key_compare(__comp)
699 { }
700#else
701 _Rb_tree_impl(_Rb_tree_impl&&) = default;
702
703 explicit
704 _Rb_tree_impl(_Node_allocator&& __a)
705 : _Node_allocator(std::move(__a))
706 { }
707
708 _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
709 : _Node_allocator(std::move(__a)),
710 _Base_key_compare(std::move(__x)),
711 _Rb_tree_header(std::move(__x))
712 { }
713
714 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
715 : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
716 { }
717#endif
718 };
719
720 _Rb_tree_impl<_Compare> _M_impl;
721
722 protected:
723 _Base_ptr&
724 _M_root() _GLIBCXX_NOEXCEPTnoexcept
725 { return this->_M_impl._M_header._M_parent; }
726
727 _Const_Base_ptr
728 _M_root() const _GLIBCXX_NOEXCEPTnoexcept
729 { return this->_M_impl._M_header._M_parent; }
730
731 _Base_ptr&
732 _M_leftmost() _GLIBCXX_NOEXCEPTnoexcept
733 { return this->_M_impl._M_header._M_left; }
734
735 _Const_Base_ptr
736 _M_leftmost() const _GLIBCXX_NOEXCEPTnoexcept
737 { return this->_M_impl._M_header._M_left; }
738
739 _Base_ptr&
740 _M_rightmost() _GLIBCXX_NOEXCEPTnoexcept
741 { return this->_M_impl._M_header._M_right; }
742
743 _Const_Base_ptr
744 _M_rightmost() const _GLIBCXX_NOEXCEPTnoexcept
745 { return this->_M_impl._M_header._M_right; }
746
747 _Link_type
748 _M_begin() _GLIBCXX_NOEXCEPTnoexcept
749 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
750
751 _Const_Link_type
752 _M_begin() const _GLIBCXX_NOEXCEPTnoexcept
753 {
754 return static_cast<_Const_Link_type>
755 (this->_M_impl._M_header._M_parent);
756 }
757
758 _Base_ptr
759 _M_end() _GLIBCXX_NOEXCEPTnoexcept
760 { return &this->_M_impl._M_header; }
761
762 _Const_Base_ptr
763 _M_end() const _GLIBCXX_NOEXCEPTnoexcept
764 { return &this->_M_impl._M_header; }
765
766 static const _Key&
767 _S_key(_Const_Link_type __x)
768 {
769#if __cplusplus201402L >= 201103L
770 // If we're asking for the key we're presumably using the comparison
771 // object, and so this is a good place to sanity check it.
772 static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
773 "comparison object must be invocable "
774 "with two arguments of key type");
775# if __cplusplus201402L >= 201703L
776 // _GLIBCXX_RESOLVE_LIB_DEFECTS
777 // 2542. Missing const requirements for associative containers
778 if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
779 static_assert(
780 is_invocable_v<const _Compare&, const _Key&, const _Key&>,
781 "comparison object must be invocable as const");
782# endif // C++17
783#endif // C++11
784
785 return _KeyOfValue()(*__x->_M_valptr());
786 }
787
788 static _Link_type
789 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
790 { return static_cast<_Link_type>(__x->_M_left); }
791
792 static _Const_Link_type
793 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
794 { return static_cast<_Const_Link_type>(__x->_M_left); }
795
796 static _Link_type
797 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
798 { return static_cast<_Link_type>(__x->_M_right); }
799
800 static _Const_Link_type
801 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
802 { return static_cast<_Const_Link_type>(__x->_M_right); }
803
804 static const _Key&
805 _S_key(_Const_Base_ptr __x)
806 { return _S_key(static_cast<_Const_Link_type>(__x)); }
807
808 static _Base_ptr
809 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
810 { return _Rb_tree_node_base::_S_minimum(__x); }
811
812 static _Const_Base_ptr
813 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
814 { return _Rb_tree_node_base::_S_minimum(__x); }
815
816 static _Base_ptr
817 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
818 { return _Rb_tree_node_base::_S_maximum(__x); }
819
820 static _Const_Base_ptr
821 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
822 { return _Rb_tree_node_base::_S_maximum(__x); }
823
824 public:
825 typedef _Rb_tree_iterator<value_type> iterator;
826 typedef _Rb_tree_const_iterator<value_type> const_iterator;
827
828 typedef std::reverse_iterator<iterator> reverse_iterator;
829 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
830
831#if __cplusplus201402L > 201402L
832 using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
833 using insert_return_type = _Node_insert_return<
834 conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
835 node_type>;
836#endif
837
838 pair<_Base_ptr, _Base_ptr>
839 _M_get_insert_unique_pos(const key_type& __k);
840
841 pair<_Base_ptr, _Base_ptr>
842 _M_get_insert_equal_pos(const key_type& __k);
843
844 pair<_Base_ptr, _Base_ptr>
845 _M_get_insert_hint_unique_pos(const_iterator __pos,
846 const key_type& __k);
847
848 pair<_Base_ptr, _Base_ptr>
849 _M_get_insert_hint_equal_pos(const_iterator __pos,
850 const key_type& __k);
851
852 private:
853#if __cplusplus201402L >= 201103L
854 template<typename _Arg, typename _NodeGen>
855 iterator
856 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
857
858 iterator
859 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
860
861 template<typename _Arg>
862 iterator
863 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
864
865 template<typename _Arg>
866 iterator
867 _M_insert_equal_lower(_Arg&& __x);
868
869 iterator
870 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
871
872 iterator
873 _M_insert_equal_lower_node(_Link_type __z);
874#else
875 template<typename _NodeGen>
876 iterator
877 _M_insert_(_Base_ptr __x, _Base_ptr __y,
878 const value_type& __v, _NodeGen&);
879
880 // _GLIBCXX_RESOLVE_LIB_DEFECTS
881 // 233. Insertion hints in associative containers.
882 iterator
883 _M_insert_lower(_Base_ptr __y, const value_type& __v);
884
885 iterator
886 _M_insert_equal_lower(const value_type& __x);
887#endif
888
889 template<typename _NodeGen>
890 _Link_type
891 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
892
893 template<typename _NodeGen>
894 _Link_type
895 _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
896 {
897 _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
898 _M_leftmost() = _S_minimum(__root);
899 _M_rightmost() = _S_maximum(__root);
900 _M_impl._M_node_count = __x._M_impl._M_node_count;
901 return __root;
902 }
903
904 _Link_type
905 _M_copy(const _Rb_tree& __x)
906 {
907 _Alloc_node __an(*this);
908 return _M_copy(__x, __an);
909 }
910
911 void
912 _M_erase(_Link_type __x);
913
914 iterator
915 _M_lower_bound(_Link_type __x, _Base_ptr __y,
916 const _Key& __k);
917
918 const_iterator
919 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
920 const _Key& __k) const;
921
922 iterator
923 _M_upper_bound(_Link_type __x, _Base_ptr __y,
924 const _Key& __k);
925
926 const_iterator
927 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
928 const _Key& __k) const;
929
930 public:
931 // allocation/deallocation
932#if __cplusplus201402L < 201103L
933 _Rb_tree() { }
934#else
935 _Rb_tree() = default;
936#endif
937
938 _Rb_tree(const _Compare& __comp,
939 const allocator_type& __a = allocator_type())
940 : _M_impl(__comp, _Node_allocator(__a)) { }
941
942 _Rb_tree(const _Rb_tree& __x)
943 : _M_impl(__x._M_impl)
944 {
945 if (__x._M_root() != 0)
946 _M_root() = _M_copy(__x);
947 }
948
949#if __cplusplus201402L >= 201103L
950 _Rb_tree(const allocator_type& __a)
951 : _M_impl(_Node_allocator(__a))
952 { }
953
954 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
955 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
956 {
957 if (__x._M_root() != nullptr)
958 _M_root() = _M_copy(__x);
959 }
960
961 _Rb_tree(_Rb_tree&&) = default;
962
963 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
964 : _Rb_tree(std::move(__x), _Node_allocator(__a))
965 { }
966
967 private:
968 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
969 noexcept(is_nothrow_default_constructible<_Compare>::value)
970 : _M_impl(std::move(__x._M_impl), std::move(__a))
971 { }
972
973 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
974 : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
975 {
976 if (__x._M_root() != nullptr)
977 _M_move_data(__x, false_type{});
978 }
979
980 public:
981 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
982 noexcept( noexcept(
983 _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
984 std::declval<typename _Alloc_traits::is_always_equal>())) )
985 : _Rb_tree(std::move(__x), std::move(__a),
986 typename _Alloc_traits::is_always_equal{})
987 { }
988#endif
989
990 ~_Rb_tree() _GLIBCXX_NOEXCEPTnoexcept
991 { _M_erase(_M_begin()); }
992
993 _Rb_tree&
994 operator=(const _Rb_tree& __x);
995
996 // Accessors.
997 _Compare
998 key_comp() const
999 { return _M_impl._M_key_compare; }
1000
1001 iterator
1002 begin() _GLIBCXX_NOEXCEPTnoexcept
1003 { return iterator(this->_M_impl._M_header._M_left); }
1004
1005 const_iterator
1006 begin() const _GLIBCXX_NOEXCEPTnoexcept
1007 { return const_iterator(this->_M_impl._M_header._M_left); }
1008
1009 iterator
1010 end() _GLIBCXX_NOEXCEPTnoexcept
1011 { return iterator(&this->_M_impl._M_header); }
1012
1013 const_iterator
1014 end() const _GLIBCXX_NOEXCEPTnoexcept
1015 { return const_iterator(&this->_M_impl._M_header); }
1016
1017 reverse_iterator
1018 rbegin() _GLIBCXX_NOEXCEPTnoexcept
1019 { return reverse_iterator(end()); }
1020
1021 const_reverse_iterator
1022 rbegin() const _GLIBCXX_NOEXCEPTnoexcept
1023 { return const_reverse_iterator(end()); }
1024
1025 reverse_iterator
1026 rend() _GLIBCXX_NOEXCEPTnoexcept
1027 { return reverse_iterator(begin()); }
1028
1029 const_reverse_iterator
1030 rend() const _GLIBCXX_NOEXCEPTnoexcept
1031 { return const_reverse_iterator(begin()); }
1032
1033 _GLIBCXX_NODISCARD bool
1034 empty() const _GLIBCXX_NOEXCEPTnoexcept
1035 { return _M_impl._M_node_count == 0; }
1036
1037 size_type
1038 size() const _GLIBCXX_NOEXCEPTnoexcept
1039 { return _M_impl._M_node_count; }
1040
1041 size_type
1042 max_size() const _GLIBCXX_NOEXCEPTnoexcept
1043 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1044
1045 void
1046 swap(_Rb_tree& __t)
1047 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)noexcept(__is_nothrow_swappable<_Compare>::value);
1048
1049 // Insert/erase.
1050#if __cplusplus201402L >= 201103L
1051 template<typename _Arg>
1052 pair<iterator, bool>
1053 _M_insert_unique(_Arg&& __x);
1054
1055 template<typename _Arg>
1056 iterator
1057 _M_insert_equal(_Arg&& __x);
1058
1059 template<typename _Arg, typename _NodeGen>
1060 iterator
1061 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1062
1063 template<typename _Arg>
1064 iterator
1065 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1066 {
1067 _Alloc_node __an(*this);
1068 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1069 }
1070
1071 template<typename _Arg, typename _NodeGen>
1072 iterator
1073 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1074
1075 template<typename _Arg>
1076 iterator
1077 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1078 {
1079 _Alloc_node __an(*this);
1080 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1081 }
1082
1083 template<typename... _Args>
1084 pair<iterator, bool>
1085 _M_emplace_unique(_Args&&... __args);
1086
1087 template<typename... _Args>
1088 iterator
1089 _M_emplace_equal(_Args&&... __args);
1090
1091 template<typename... _Args>
1092 iterator
1093 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1094
1095 template<typename... _Args>
1096 iterator
1097 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1098
1099 template<typename _Iter>
1100 using __same_value_type
1101 = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
1102
1103 template<typename _InputIterator>
1104 __enable_if_t<__same_value_type<_InputIterator>::value>
1105 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1106 {
1107 _Alloc_node __an(*this);
1108 for (; __first != __last; ++__first)
1109 _M_insert_unique_(end(), *__first, __an);
1110 }
1111
1112 template<typename _InputIterator>
1113 __enable_if_t<!__same_value_type<_InputIterator>::value>
1114 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1115 {
1116 for (; __first != __last; ++__first)
1117 _M_emplace_unique(*__first);
1118 }
1119
1120 template<typename _InputIterator>
1121 __enable_if_t<__same_value_type<_InputIterator>::value>
1122 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1123 {
1124 _Alloc_node __an(*this);
1125 for (; __first != __last; ++__first)
1126 _M_insert_equal_(end(), *__first, __an);
1127 }
1128
1129 template<typename _InputIterator>
1130 __enable_if_t<!__same_value_type<_InputIterator>::value>
1131 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1132 {
1133 _Alloc_node __an(*this);
1134 for (; __first != __last; ++__first)
1135 _M_emplace_equal(*__first);
1136 }
1137#else
1138 pair<iterator, bool>
1139 _M_insert_unique(const value_type& __x);
1140
1141 iterator
1142 _M_insert_equal(const value_type& __x);
1143
1144 template<typename _NodeGen>
1145 iterator
1146 _M_insert_unique_(const_iterator __pos, const value_type& __x,
1147 _NodeGen&);
1148
1149 iterator
1150 _M_insert_unique_(const_iterator __pos, const value_type& __x)
1151 {
1152 _Alloc_node __an(*this);
1153 return _M_insert_unique_(__pos, __x, __an);
1154 }
1155
1156 template<typename _NodeGen>
1157 iterator
1158 _M_insert_equal_(const_iterator __pos, const value_type& __x,
1159 _NodeGen&);
1160 iterator
1161 _M_insert_equal_(const_iterator __pos, const value_type& __x)
1162 {
1163 _Alloc_node __an(*this);
1164 return _M_insert_equal_(__pos, __x, __an);
1165 }
1166
1167 template<typename _InputIterator>
1168 void
1169 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1170 {
1171 _Alloc_node __an(*this);
1172 for (; __first != __last; ++__first)
1173 _M_insert_unique_(end(), *__first, __an);
1174 }
1175
1176 template<typename _InputIterator>
1177 void
1178 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1179 {
1180 _Alloc_node __an(*this);
1181 for (; __first != __last; ++__first)
1182 _M_insert_equal_(end(), *__first, __an);
1183 }
1184#endif
1185
1186 private:
1187 void
1188 _M_erase_aux(const_iterator __position);
1189
1190 void
1191 _M_erase_aux(const_iterator __first, const_iterator __last);
1192
1193 public:
1194#if __cplusplus201402L >= 201103L
1195 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1196 // DR 130. Associative erase should return an iterator.
1197 _GLIBCXX_ABI_TAG_CXX11__attribute ((__abi_tag__ ("cxx11")))
1198 iterator
1199 erase(const_iterator __position)
1200 {
1201 __glibcxx_assert(__position != end());
1202 const_iterator __result = __position;
1203 ++__result;
1204 _M_erase_aux(__position);
1205 return __result._M_const_cast();
1206 }
1207
1208 // LWG 2059.
1209 _GLIBCXX_ABI_TAG_CXX11__attribute ((__abi_tag__ ("cxx11")))
1210 iterator
1211 erase(iterator __position)
1212 {
1213 __glibcxx_assert(__position != end());
1214 iterator __result = __position;
1215 ++__result;
1216 _M_erase_aux(__position);
1217 return __result;
1218 }
1219#else
1220 void
1221 erase(iterator __position)
1222 {
1223 __glibcxx_assert(__position != end());
1224 _M_erase_aux(__position);
1225 }
1226
1227 void
1228 erase(const_iterator __position)
1229 {
1230 __glibcxx_assert(__position != end());
1231 _M_erase_aux(__position);
1232 }
1233#endif
1234
1235 size_type
1236 erase(const key_type& __x);
1237
1238#if __cplusplus201402L >= 201103L
1239 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1240 // DR 130. Associative erase should return an iterator.
1241 _GLIBCXX_ABI_TAG_CXX11__attribute ((__abi_tag__ ("cxx11")))
1242 iterator
1243 erase(const_iterator __first, const_iterator __last)
1244 {
1245 _M_erase_aux(__first, __last);
1246 return __last._M_const_cast();
1247 }
1248#else
1249 void
1250 erase(iterator __first, iterator __last)
1251 { _M_erase_aux(__first, __last); }
1252
1253 void
1254 erase(const_iterator __first, const_iterator __last)
1255 { _M_erase_aux(__first, __last); }
1256#endif
1257
1258 void
1259 clear() _GLIBCXX_NOEXCEPTnoexcept
1260 {
1261 _M_erase(_M_begin());
1262 _M_impl._M_reset();
1263 }
1264
1265 // Set operations.
1266 iterator
1267 find(const key_type& __k);
1268
1269 const_iterator
1270 find(const key_type& __k) const;
1271
1272 size_type
1273 count(const key_type& __k) const;
1274
1275 iterator
1276 lower_bound(const key_type& __k)
1277 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1278
1279 const_iterator
1280 lower_bound(const key_type& __k) const
1281 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1282
1283 iterator
1284 upper_bound(const key_type& __k)
1285 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1286
1287 const_iterator
1288 upper_bound(const key_type& __k) const
1289 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1290
1291 pair<iterator, iterator>
1292 equal_range(const key_type& __k);
1293
1294 pair<const_iterator, const_iterator>
1295 equal_range(const key_type& __k) const;
1296
1297#if __cplusplus201402L >= 201402L
1298 template<typename _Kt,
1299 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1300 iterator
1301 _M_find_tr(const _Kt& __k)
1302 {
1303 const _Rb_tree* __const_this = this;
1304 return __const_this->_M_find_tr(__k)._M_const_cast();
1305 }
1306
1307 template<typename _Kt,
1308 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1309 const_iterator
1310 _M_find_tr(const _Kt& __k) const
1311 {
1312 auto __j = _M_lower_bound_tr(__k);
1313 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1314 __j = end();
1315 return __j;
1316 }
1317
1318 template<typename _Kt,
1319 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1320 size_type
1321 _M_count_tr(const _Kt& __k) const
1322 {
1323 auto __p = _M_equal_range_tr(__k);
1324 return std::distance(__p.first, __p.second);
1325 }
1326
1327 template<typename _Kt,
1328 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1329 iterator
1330 _M_lower_bound_tr(const _Kt& __k)
1331 {
1332 const _Rb_tree* __const_this = this;
1333 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1334 }
1335
1336 template<typename _Kt,
1337 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1338 const_iterator
1339 _M_lower_bound_tr(const _Kt& __k) const
1340 {
1341 auto __x = _M_begin();
1342 auto __y = _M_end();
1343 while (__x != 0)
1344 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1345 {
1346 __y = __x;
1347 __x = _S_left(__x);
1348 }
1349 else
1350 __x = _S_right(__x);
1351 return const_iterator(__y);
1352 }
1353
1354 template<typename _Kt,
1355 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1356 iterator
1357 _M_upper_bound_tr(const _Kt& __k)
1358 {
1359 const _Rb_tree* __const_this = this;
1360 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1361 }
1362
1363 template<typename _Kt,
1364 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1365 const_iterator
1366 _M_upper_bound_tr(const _Kt& __k) const
1367 {
1368 auto __x = _M_begin();
1369 auto __y = _M_end();
1370 while (__x != 0)
1371 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1372 {
1373 __y = __x;
1374 __x = _S_left(__x);
1375 }
1376 else
1377 __x = _S_right(__x);
1378 return const_iterator(__y);
1379 }
1380
1381 template<typename _Kt,
1382 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1383 pair<iterator, iterator>
1384 _M_equal_range_tr(const _Kt& __k)
1385 {
1386 const _Rb_tree* __const_this = this;
1387 auto __ret = __const_this->_M_equal_range_tr(__k);
1388 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1389 }
1390
1391 template<typename _Kt,
1392 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1393 pair<const_iterator, const_iterator>
1394 _M_equal_range_tr(const _Kt& __k) const
1395 {
1396 auto __low = _M_lower_bound_tr(__k);
1397 auto __high = __low;
1398 auto& __cmp = _M_impl._M_key_compare;
1399 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1400 ++__high;
1401 return { __low, __high };
1402 }
1403#endif
1404
1405 // Debugging.
1406 bool
1407 __rb_verify() const;
1408
1409#if __cplusplus201402L >= 201103L
1410 _Rb_tree&
1411 operator=(_Rb_tree&&)
1412 noexcept(_Alloc_traits::_S_nothrow_move()
1413 && is_nothrow_move_assignable<_Compare>::value);
1414
1415 template<typename _Iterator>
1416 void
1417 _M_assign_unique(_Iterator, _Iterator);
1418
1419 template<typename _Iterator>
1420 void
1421 _M_assign_equal(_Iterator, _Iterator);
1422
1423 private:
1424 // Move elements from container with equal allocator.
1425 void
1426 _M_move_data(_Rb_tree& __x, true_type)
1427 { _M_impl._M_move_data(__x._M_impl); }
1428
1429 // Move elements from container with possibly non-equal allocator,
1430 // which might result in a copy not a move.
1431 void
1432 _M_move_data(_Rb_tree&, false_type);
1433
1434 // Move assignment from container with equal allocator.
1435 void
1436 _M_move_assign(_Rb_tree&, true_type);
1437
1438 // Move assignment from container with possibly non-equal allocator,
1439 // which might result in a copy not a move.
1440 void
1441 _M_move_assign(_Rb_tree&, false_type);
1442#endif
1443
1444#if __cplusplus201402L > 201402L
1445 public:
1446 /// Re-insert an extracted node.
1447 insert_return_type
1448 _M_reinsert_node_unique(node_type&& __nh)
1449 {
1450 insert_return_type __ret;
1451 if (__nh.empty())
1452 __ret.position = end();
1453 else
1454 {
1455 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1456
1457 auto __res = _M_get_insert_unique_pos(__nh._M_key());
1458 if (__res.second)
1459 {
1460 __ret.position
1461 = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1462 __nh._M_ptr = nullptr;
1463 __ret.inserted = true;
1464 }
1465 else
1466 {
1467 __ret.node = std::move(__nh);
1468 __ret.position = iterator(__res.first);
1469 __ret.inserted = false;
1470 }
1471 }
1472 return __ret;
1473 }
1474
1475 /// Re-insert an extracted node.
1476 iterator
1477 _M_reinsert_node_equal(node_type&& __nh)
1478 {
1479 iterator __ret;
1480 if (__nh.empty())
1481 __ret = end();
1482 else
1483 {
1484 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1485 auto __res = _M_get_insert_equal_pos(__nh._M_key());
1486 if (__res.second)
1487 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1488 else
1489 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1490 __nh._M_ptr = nullptr;
1491 }
1492 return __ret;
1493 }
1494
1495 /// Re-insert an extracted node.
1496 iterator
1497 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
1498 {
1499 iterator __ret;
1500 if (__nh.empty())
1501 __ret = end();
1502 else
1503 {
1504 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1505 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
1506 if (__res.second)
1507 {
1508 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1509 __nh._M_ptr = nullptr;
1510 }
1511 else
1512 __ret = iterator(__res.first);
1513 }
1514 return __ret;
1515 }
1516
1517 /// Re-insert an extracted node.
1518 iterator
1519 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
1520 {
1521 iterator __ret;
1522 if (__nh.empty())
1523 __ret = end();
1524 else
1525 {
1526 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1527 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
1528 if (__res.second)
1529 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1530 else
1531 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1532 __nh._M_ptr = nullptr;
1533 }
1534 return __ret;
1535 }
1536
1537 /// Extract a node.
1538 node_type
1539 extract(const_iterator __pos)
1540 {
1541 auto __ptr = _Rb_tree_rebalance_for_erase(
1542 __pos._M_const_cast()._M_node, _M_impl._M_header);
1543 --_M_impl._M_node_count;
1544 return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
1545 }
1546
1547 /// Extract a node.
1548 node_type
1549 extract(const key_type& __k)
1550 {
1551 node_type __nh;
1552 auto __pos = find(__k);
1553 if (__pos != end())
1554 __nh = extract(const_iterator(__pos));
1555 return __nh;
1556 }
1557
1558 template<typename _Compare2>
1559 using _Compatible_tree
1560 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
1561
1562 template<typename, typename>
1563 friend class _Rb_tree_merge_helper;
1564
1565 /// Merge from a compatible container into one with unique keys.
1566 template<typename _Compare2>
1567 void
1568 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
1569 {
1570 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1571 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1572 {
1573 auto __pos = __i++;
1574 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
1575 if (__res.second)
1576 {
1577 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1578 auto __ptr = _Rb_tree_rebalance_for_erase(
1579 __pos._M_node, __src_impl._M_header);
1580 --__src_impl._M_node_count;
1581 _M_insert_node(__res.first, __res.second,
1582 static_cast<_Link_type>(__ptr));
1583 }
1584 }
1585 }
1586
1587 /// Merge from a compatible container into one with equivalent keys.
1588 template<typename _Compare2>
1589 void
1590 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
1591 {
1592 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1593 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1594 {
1595 auto __pos = __i++;
1596 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
1597 if (__res.second)
1598 {
1599 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1600 auto __ptr = _Rb_tree_rebalance_for_erase(
1601 __pos._M_node, __src_impl._M_header);
1602 --__src_impl._M_node_count;
1603 _M_insert_node(__res.first, __res.second,
1604 static_cast<_Link_type>(__ptr));
1605 }
1606 }
1607 }
1608#endif // C++17
1609
1610 friend bool
1611 operator==(const _Rb_tree& __x, const _Rb_tree& __y)
1612 {
1613 return __x.size() == __y.size()
1614 && std::equal(__x.begin(), __x.end(), __y.begin());
1615 }
1616
1617#if __cpp_lib_three_way_comparison
1618 friend auto
1619 operator<=>(const _Rb_tree& __x, const _Rb_tree& __y)
1620 {
1621 if constexpr (requires { typename __detail::__synth3way_t<_Val>; })
1622 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1623 __y.begin(), __y.end(),
1624 __detail::__synth3way);
1625 }
1626#else
1627 friend bool
1628 operator<(const _Rb_tree& __x, const _Rb_tree& __y)
1629 {
1630 return std::lexicographical_compare(__x.begin(), __x.end(),
1631 __y.begin(), __y.end());
1632 }
1633
1634 friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
1635 operator!=(const _Rb_tree& __x, const _Rb_tree& __y)
1636 { return !(__x == __y); }
1637
1638 friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
1639 operator>(const _Rb_tree& __x, const _Rb_tree& __y)
1640 { return __y < __x; }
1641
1642 friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
1643 operator<=(const _Rb_tree& __x, const _Rb_tree& __y)
1644 { return !(__y < __x); }
1645
1646 friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
1647 operator>=(const _Rb_tree& __x, const _Rb_tree& __y)
1648 { return !(__x < __y); }
1649#endif
1650 };
1651
1652 template<typename _Key, typename _Val, typename _KeyOfValue,
1653 typename _Compare, typename _Alloc>
1654 inline void
1655 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1656 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1657 { __x.swap(__y); }
1658
1659#if __cplusplus201402L >= 201103L
1660 template<typename _Key, typename _Val, typename _KeyOfValue,
1661 typename _Compare, typename _Alloc>
1662 void
1663 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1664 _M_move_data(_Rb_tree& __x, false_type)
1665 {
1666 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1667 _M_move_data(__x, true_type());
1668 else
1669 {
1670 _Alloc_node __an(*this);
1671 auto __lbd =
1672 [&__an](const value_type& __cval)
1673 {
1674 auto& __val = const_cast<value_type&>(__cval);
1675 return __an(std::move_if_noexcept(__val));
1676 };
1677 _M_root() = _M_copy(__x, __lbd);
1678 }
1679 }
1680
1681 template<typename _Key, typename _Val, typename _KeyOfValue,
1682 typename _Compare, typename _Alloc>
1683 inline void
1684 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1685 _M_move_assign(_Rb_tree& __x, true_type)
1686 {
1687 clear();
1688 if (__x._M_root() != nullptr)
1689 _M_move_data(__x, true_type());
1690 std::__alloc_on_move(_M_get_Node_allocator(),
1691 __x._M_get_Node_allocator());
1692 }
1693
1694 template<typename _Key, typename _Val, typename _KeyOfValue,
1695 typename _Compare, typename _Alloc>
1696 void
1697 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1698 _M_move_assign(_Rb_tree& __x, false_type)
1699 {
1700 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1701 return _M_move_assign(__x, true_type{});
1702
1703 // Try to move each node reusing existing nodes and copying __x nodes
1704 // structure.
1705 _Reuse_or_alloc_node __roan(*this);
1706 _M_impl._M_reset();
1707 if (__x._M_root() != nullptr)
1708 {
1709 auto __lbd =
1710 [&__roan](const value_type& __cval)
1711 {
1712 auto& __val = const_cast<value_type&>(__cval);
1713 return __roan(std::move(__val));
1714 };
1715 _M_root() = _M_copy(__x, __lbd);
1716 __x.clear();
1717 }
1718 }
1719
1720 template<typename _Key, typename _Val, typename _KeyOfValue,
1721 typename _Compare, typename _Alloc>
1722 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1723 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1724 operator=(_Rb_tree&& __x)
1725 noexcept(_Alloc_traits::_S_nothrow_move()
1726 && is_nothrow_move_assignable<_Compare>::value)
1727 {
1728 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
1729 _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
1730 return *this;
1731 }
1732
1733 template<typename _Key, typename _Val, typename _KeyOfValue,
1734 typename _Compare, typename _Alloc>
1735 template<typename _Iterator>
1736 void
1737 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1738 _M_assign_unique(_Iterator __first, _Iterator __last)
1739 {
1740 _Reuse_or_alloc_node __roan(*this);
1741 _M_impl._M_reset();
1742 for (; __first != __last; ++__first)
1743 _M_insert_unique_(end(), *__first, __roan);
1744 }
1745
1746 template<typename _Key, typename _Val, typename _KeyOfValue,
1747 typename _Compare, typename _Alloc>
1748 template<typename _Iterator>
1749 void
1750 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1751 _M_assign_equal(_Iterator __first, _Iterator __last)
1752 {
1753 _Reuse_or_alloc_node __roan(*this);
1754 _M_impl._M_reset();
1755 for (; __first != __last; ++__first)
1756 _M_insert_equal_(end(), *__first, __roan);
1757 }
1758#endif
1759
1760 template<typename _Key, typename _Val, typename _KeyOfValue,
1761 typename _Compare, typename _Alloc>
1762 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1763 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1764 operator=(const _Rb_tree& __x)
1765 {
1766 if (this != &__x)
1767 {
1768 // Note that _Key may be a constant type.
1769#if __cplusplus201402L >= 201103L
1770 if (_Alloc_traits::_S_propagate_on_copy_assign())
1771 {
1772 auto& __this_alloc = this->_M_get_Node_allocator();
1773 auto& __that_alloc = __x._M_get_Node_allocator();
1774 if (!_Alloc_traits::_S_always_equal()
1775 && __this_alloc != __that_alloc)
1776 {
1777 // Replacement allocator cannot free existing storage, we need
1778 // to erase nodes first.
1779 clear();
1780 std::__alloc_on_copy(__this_alloc, __that_alloc);
1781 }
1782 }
1783#endif
1784
1785 _Reuse_or_alloc_node __roan(*this);
1786 _M_impl._M_reset();
1787 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1788 if (__x._M_root() != 0)
1789 _M_root() = _M_copy(__x, __roan);
1790 }
1791
1792 return *this;
1793 }
1794
1795 template<typename _Key, typename _Val, typename _KeyOfValue,
1796 typename _Compare, typename _Alloc>
1797#if __cplusplus201402L >= 201103L
1798 template<typename _Arg, typename _NodeGen>
1799#else
1800 template<typename _NodeGen>
1801#endif
1802 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1803 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1804 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1805#if __cplusplus201402L >= 201103L
1806 _Arg&& __v,
1807#else
1808 const _Val& __v,
1809#endif
1810 _NodeGen& __node_gen)
1811 {
1812 bool __insert_left = (__x != 0 || __p == _M_end()
1813 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1814 _S_key(__p)));
1815
1816 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));
1817
1818 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1819 this->_M_impl._M_header);
1820 ++_M_impl._M_node_count;
1821 return iterator(__z);
1822 }
1823
1824 template<typename _Key, typename _Val, typename _KeyOfValue,
1825 typename _Compare, typename _Alloc>
1826#if __cplusplus201402L >= 201103L
1827 template<typename _Arg>
1828#endif
1829 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1830 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1831#if __cplusplus201402L >= 201103L
1832 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1833#else
1834 _M_insert_lower(_Base_ptr __p, const _Val& __v)
1835#endif
1836 {
1837 bool __insert_left = (__p == _M_end()
1838 || !_M_impl._M_key_compare(_S_key(__p),
1839 _KeyOfValue()(__v)));
1840
1841 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));
1842
1843 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1844 this->_M_impl._M_header);
1845 ++_M_impl._M_node_count;
1846 return iterator(__z);
1847 }
1848
1849 template<typename _Key, typename _Val, typename _KeyOfValue,
1850 typename _Compare, typename _Alloc>
1851#if __cplusplus201402L >= 201103L
1852 template<typename _Arg>
1853#endif
1854 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1855 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1856#if __cplusplus201402L >= 201103L
1857 _M_insert_equal_lower(_Arg&& __v)
1858#else
1859 _M_insert_equal_lower(const _Val& __v)
1860#endif
1861 {
1862 _Link_type __x = _M_begin();
1863 _Base_ptr __y = _M_end();
1864 while (__x != 0)
1865 {
1866 __y = __x;
1867 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1868 _S_left(__x) : _S_right(__x);
1869 }
1870 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));
1871 }
1872
1873 template<typename _Key, typename _Val, typename _KoV,
1874 typename _Compare, typename _Alloc>
1875 template<typename _NodeGen>
1876 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1877 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1878 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1879 {
1880 // Structural copy. __x and __p must be non-null.
1881 _Link_type __top = _M_clone_node(__x, __node_gen);
1882 __top->_M_parent = __p;
1883
1884 __tryif (true)
1885 {
1886 if (__x->_M_right)
1887 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1888 __p = __top;
1889 __x = _S_left(__x);
1890
1891 while (__x != 0)
1892 {
1893 _Link_type __y = _M_clone_node(__x, __node_gen);
1894 __p->_M_left = __y;
1895 __y->_M_parent = __p;
1896 if (__x->_M_right)
1897 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1898 __p = __y;
1899 __x = _S_left(__x);
1900 }
1901 }
1902 __catch(...)if (false)
1903 {
1904 _M_erase(__top);
1905 __throw_exception_again;
1906 }
1907 return __top;
1908 }
1909
1910 template<typename _Key, typename _Val, typename _KeyOfValue,
1911 typename _Compare, typename _Alloc>
1912 void
1913 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1914 _M_erase(_Link_type __x)
1915 {
1916 // Erase without rebalancing.
1917 while (__x != 0)
1918 {
1919 _M_erase(_S_right(__x));
1920 _Link_type __y = _S_left(__x);
1921 _M_drop_node(__x);
1922 __x = __y;
1923 }
1924 }
1925
1926 template<typename _Key, typename _Val, typename _KeyOfValue,
1927 typename _Compare, typename _Alloc>
1928 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1929 _Compare, _Alloc>::iterator
1930 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1931 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1932 const _Key& __k)
1933 {
1934 while (__x != 0)
1935 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1936 __y = __x, __x = _S_left(__x);
1937 else
1938 __x = _S_right(__x);
1939 return iterator(__y);
1940 }
1941
1942 template<typename _Key, typename _Val, typename _KeyOfValue,
1943 typename _Compare, typename _Alloc>
1944 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1945 _Compare, _Alloc>::const_iterator
1946 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1947 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1948 const _Key& __k) const
1949 {
1950 while (__x != 0)
1951 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1952 __y = __x, __x = _S_left(__x);
1953 else
1954 __x = _S_right(__x);
1955 return const_iterator(__y);
1956 }
1957
1958 template<typename _Key, typename _Val, typename _KeyOfValue,
1959 typename _Compare, typename _Alloc>
1960 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1961 _Compare, _Alloc>::iterator
1962 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1963 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1964 const _Key& __k)
1965 {
1966 while (__x != 0)
1967 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1968 __y = __x, __x = _S_left(__x);
1969 else
1970 __x = _S_right(__x);
1971 return iterator(__y);
1972 }
1973
1974 template<typename _Key, typename _Val, typename _KeyOfValue,
1975 typename _Compare, typename _Alloc>
1976 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1977 _Compare, _Alloc>::const_iterator
1978 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1979 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1980 const _Key& __k) const
1981 {
1982 while (__x != 0)
1983 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1984 __y = __x, __x = _S_left(__x);
1985 else
1986 __x = _S_right(__x);
1987 return const_iterator(__y);
1988 }
1989
1990 template<typename _Key, typename _Val, typename _KeyOfValue,
1991 typename _Compare, typename _Alloc>
1992 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1993 _Compare, _Alloc>::iterator,
1994 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1995 _Compare, _Alloc>::iterator>
1996 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1997 equal_range(const _Key& __k)
1998 {
1999 _Link_type __x = _M_begin();
2000 _Base_ptr __y = _M_end();
2001 while (__x != 0)
2002 {
2003 if (_M_impl._M_key_compare(_S_key(__x), __k))
2004 __x = _S_right(__x);
2005 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2006 __y = __x, __x = _S_left(__x);
2007 else
2008 {
2009 _Link_type __xu(__x);
2010 _Base_ptr __yu(__y);
2011 __y = __x, __x = _S_left(__x);
2012 __xu = _S_right(__xu);
2013 return pair<iterator,
2014 iterator>(_M_lower_bound(__x, __y, __k),
2015 _M_upper_bound(__xu, __yu, __k));
2016 }
2017 }
2018 return pair<iterator, iterator>(iterator(__y),
2019 iterator(__y));
2020 }
2021
2022 template<typename _Key, typename _Val, typename _KeyOfValue,
2023 typename _Compare, typename _Alloc>
2024 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2025 _Compare, _Alloc>::const_iterator,
2026 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2027 _Compare, _Alloc>::const_iterator>
2028 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2029 equal_range(const _Key& __k) const
2030 {
2031 _Const_Link_type __x = _M_begin();
2032 _Const_Base_ptr __y = _M_end();
2033 while (__x != 0)
2034 {
2035 if (_M_impl._M_key_compare(_S_key(__x), __k))
2036 __x = _S_right(__x);
2037 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2038 __y = __x, __x = _S_left(__x);
2039 else
2040 {
2041 _Const_Link_type __xu(__x);
2042 _Const_Base_ptr __yu(__y);
2043 __y = __x, __x = _S_left(__x);
2044 __xu = _S_right(__xu);
2045 return pair<const_iterator,
2046 const_iterator>(_M_lower_bound(__x, __y, __k),
2047 _M_upper_bound(__xu, __yu, __k));
2048 }
2049 }
2050 return pair<const_iterator, const_iterator>(const_iterator(__y),
2051 const_iterator(__y));
2052 }
2053
2054 template<typename _Key, typename _Val, typename _KeyOfValue,
2055 typename _Compare, typename _Alloc>
2056 void
2057 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2058 swap(_Rb_tree& __t)
2059 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)noexcept(__is_nothrow_swappable<_Compare>::value)
2060 {
2061 if (_M_root() == 0)
2062 {
2063 if (__t._M_root() != 0)
2064 _M_impl._M_move_data(__t._M_impl);
2065 }
2066 else if (__t._M_root() == 0)
2067 __t._M_impl._M_move_data(_M_impl);
2068 else
2069 {
2070 std::swap(_M_root(),__t._M_root());
2071 std::swap(_M_leftmost(),__t._M_leftmost());
2072 std::swap(_M_rightmost(),__t._M_rightmost());
2073
2074 _M_root()->_M_parent = _M_end();
2075 __t._M_root()->_M_parent = __t._M_end();
2076 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2077 }
2078 // No need to swap header's color as it does not change.
2079 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2080
2081 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2082 __t._M_get_Node_allocator());
2083 }
2084
2085 template<typename _Key, typename _Val, typename _KeyOfValue,
2086 typename _Compare, typename _Alloc>
2087 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2088 _Compare, _Alloc>::_Base_ptr,
2089 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2090 _Compare, _Alloc>::_Base_ptr>
2091 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2092 _M_get_insert_unique_pos(const key_type& __k)
2093 {
2094 typedef pair<_Base_ptr, _Base_ptr> _Res;
2095 _Link_type __x = _M_begin();
2096 _Base_ptr __y = _M_end();
2097 bool __comp = true;
2098 while (__x != 0)
2099 {
2100 __y = __x;
2101 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2102 __x = __comp ? _S_left(__x) : _S_right(__x);
2103 }
2104 iterator __j = iterator(__y);
2105 if (__comp)
2106 {
2107 if (__j == begin())
2108 return _Res(__x, __y);
2109 else
2110 --__j;
2111 }
2112 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2113 return _Res(__x, __y);
2114 return _Res(__j._M_node, 0);
2115 }
2116
2117 template<typename _Key, typename _Val, typename _KeyOfValue,
2118 typename _Compare, typename _Alloc>
2119 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2120 _Compare, _Alloc>::_Base_ptr,
2121 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2122 _Compare, _Alloc>::_Base_ptr>
2123 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2124 _M_get_insert_equal_pos(const key_type& __k)
2125 {
2126 typedef pair<_Base_ptr, _Base_ptr> _Res;
2127 _Link_type __x = _M_begin();
2128 _Base_ptr __y = _M_end();
2129 while (__x != 0)
2130 {
2131 __y = __x;
2132 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2133 _S_left(__x) : _S_right(__x);
2134 }
2135 return _Res(__x, __y);
2136 }
2137
2138 template<typename _Key, typename _Val, typename _KeyOfValue,
2139 typename _Compare, typename _Alloc>
2140#if __cplusplus201402L >= 201103L
2141 template<typename _Arg>
2142#endif
2143 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2144 _Compare, _Alloc>::iterator, bool>
2145 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2146#if __cplusplus201402L >= 201103L
2147 _M_insert_unique(_Arg&& __v)
2148#else
2149 _M_insert_unique(const _Val& __v)
2150#endif
2151 {
2152 typedef pair<iterator, bool> _Res;
2153 pair<_Base_ptr, _Base_ptr> __res
2154 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2155
2156 if (__res.second)
2157 {
2158 _Alloc_node __an(*this);
2159 return _Res(_M_insert_(__res.first, __res.second,
2160 _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v), __an),
2161 true);
2162 }
2163
2164 return _Res(iterator(__res.first), false);
2165 }
2166
2167 template<typename _Key, typename _Val, typename _KeyOfValue,
2168 typename _Compare, typename _Alloc>
2169#if __cplusplus201402L >= 201103L
2170 template<typename _Arg>
2171#endif
2172 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2173 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2174#if __cplusplus201402L >= 201103L
2175 _M_insert_equal(_Arg&& __v)
2176#else
2177 _M_insert_equal(const _Val& __v)
2178#endif
2179 {
2180 pair<_Base_ptr, _Base_ptr> __res
2181 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2182 _Alloc_node __an(*this);
2183 return _M_insert_(__res.first, __res.second,
2184 _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v), __an);
2185 }
2186
2187 template<typename _Key, typename _Val, typename _KeyOfValue,
2188 typename _Compare, typename _Alloc>
2189 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2190 _Compare, _Alloc>::_Base_ptr,
2191 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2192 _Compare, _Alloc>::_Base_ptr>
2193 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2194 _M_get_insert_hint_unique_pos(const_iterator __position,
2195 const key_type& __k)
2196 {
2197 iterator __pos = __position._M_const_cast();
2198 typedef pair<_Base_ptr, _Base_ptr> _Res;
2199
2200 // end()
2201 if (__pos._M_node == _M_end())
2202 {
2203 if (size() > 0
2204 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2205 return _Res(0, _M_rightmost());
2206 else
2207 return _M_get_insert_unique_pos(__k);
2208 }
2209 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
2210 {
2211 // First, try before...
2212 iterator __before = __pos;
2213 if (__pos._M_node == _M_leftmost()) // begin()
2214 return _Res(_M_leftmost(), _M_leftmost());
2215 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2216 {
2217 if (_S_right(__before._M_node) == 0)
2218 return _Res(0, __before._M_node);
2219 else
2220 return _Res(__pos._M_node, __pos._M_node);
2221 }
2222 else
2223 return _M_get_insert_unique_pos(__k);
2224 }
2225 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2226 {
2227 // ... then try after.
2228 iterator __after = __pos;
2229 if (__pos._M_node == _M_rightmost())
2230 return _Res(0, _M_rightmost());
2231 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2232 {
2233 if (_S_right(__pos._M_node) == 0)
2234 return _Res(0, __pos._M_node);
2235 else
2236 return _Res(__after._M_node, __after._M_node);
2237 }
2238 else
2239 return _M_get_insert_unique_pos(__k);
2240 }
2241 else
2242 // Equivalent keys.
2243 return _Res(__pos._M_node, 0);
2244 }
2245
2246 template<typename _Key, typename _Val, typename _KeyOfValue,
2247 typename _Compare, typename _Alloc>
2248#if __cplusplus201402L >= 201103L
2249 template<typename _Arg, typename _NodeGen>
2250#else
2251 template<typename _NodeGen>
2252#endif
2253 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2254 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2255 _M_insert_unique_(const_iterator __position,
2256#if __cplusplus201402L >= 201103L
2257 _Arg&& __v,
2258#else
2259 const _Val& __v,
2260#endif
2261 _NodeGen& __node_gen)
2262 {
2263 pair<_Base_ptr, _Base_ptr> __res
2264 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2265
2266 if (__res.second)
2267 return _M_insert_(__res.first, __res.second,
2268 _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v),
2269 __node_gen);
2270 return iterator(__res.first);
2271 }
2272
2273 template<typename _Key, typename _Val, typename _KeyOfValue,
2274 typename _Compare, typename _Alloc>
2275 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2276 _Compare, _Alloc>::_Base_ptr,
2277 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2278 _Compare, _Alloc>::_Base_ptr>
2279 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2280 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2281 {
2282 iterator __pos = __position._M_const_cast();
2283 typedef pair<_Base_ptr, _Base_ptr> _Res;
2284
2285 // end()
2286 if (__pos._M_node == _M_end())
2287 {
2288 if (size() > 0
2289 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2290 return _Res(0, _M_rightmost());
2291 else
2292 return _M_get_insert_equal_pos(__k);
2293 }
2294 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2295 {
2296 // First, try before...
2297 iterator __before = __pos;
2298 if (__pos._M_node == _M_leftmost()) // begin()
2299 return _Res(_M_leftmost(), _M_leftmost());
2300 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2301 {
2302 if (_S_right(__before._M_node) == 0)
2303 return _Res(0, __before._M_node);
2304 else
2305 return _Res(__pos._M_node, __pos._M_node);
2306 }
2307 else
2308 return _M_get_insert_equal_pos(__k);
2309 }
2310 else
2311 {
2312 // ... then try after.
2313 iterator __after = __pos;
2314 if (__pos._M_node == _M_rightmost())
2315 return _Res(0, _M_rightmost());
2316 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2317 {
2318 if (_S_right(__pos._M_node) == 0)
2319 return _Res(0, __pos._M_node);
2320 else
2321 return _Res(__after._M_node, __after._M_node);
2322 }
2323 else
2324 return _Res(0, 0);
2325 }
2326 }
2327
2328 template<typename _Key, typename _Val, typename _KeyOfValue,
2329 typename _Compare, typename _Alloc>
2330#if __cplusplus201402L >= 201103L
2331 template<typename _Arg, typename _NodeGen>
2332#else
2333 template<typename _NodeGen>
2334#endif
2335 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2336 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2337 _M_insert_equal_(const_iterator __position,
2338#if __cplusplus201402L >= 201103L
2339 _Arg&& __v,
2340#else
2341 const _Val& __v,
2342#endif
2343 _NodeGen& __node_gen)
2344 {
2345 pair<_Base_ptr, _Base_ptr> __res
2346 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2347
2348 if (__res.second)
2349 return _M_insert_(__res.first, __res.second,
2350 _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v),
2351 __node_gen);
2352
2353 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));
2354 }
2355
2356#if __cplusplus201402L >= 201103L
2357 template<typename _Key, typename _Val, typename _KeyOfValue,
2358 typename _Compare, typename _Alloc>
2359 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2360 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2361 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2362 {
2363 bool __insert_left = (__x != 0 || __p == _M_end()
2364 || _M_impl._M_key_compare(_S_key(__z),
2365 _S_key(__p)));
2366
2367 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2368 this->_M_impl._M_header);
2369 ++_M_impl._M_node_count;
2370 return iterator(__z);
2371 }
2372
2373 template<typename _Key, typename _Val, typename _KeyOfValue,
2374 typename _Compare, typename _Alloc>
2375 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2376 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2377 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2378 {
2379 bool __insert_left = (__p == _M_end()
2380 || !_M_impl._M_key_compare(_S_key(__p),
2381 _S_key(__z)));
2382
2383 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2384 this->_M_impl._M_header);
2385 ++_M_impl._M_node_count;
2386 return iterator(__z);
2387 }
2388
2389 template<typename _Key, typename _Val, typename _KeyOfValue,
2390 typename _Compare, typename _Alloc>
2391 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2392 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2393 _M_insert_equal_lower_node(_Link_type __z)
2394 {
2395 _Link_type __x = _M_begin();
2396 _Base_ptr __y = _M_end();
2397 while (__x != 0)
2398 {
2399 __y = __x;
2400 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2401 _S_left(__x) : _S_right(__x);
2402 }
2403 return _M_insert_lower_node(__y, __z);
2404 }
2405
2406 template<typename _Key, typename _Val, typename _KeyOfValue,
2407 typename _Compare, typename _Alloc>
2408 template<typename... _Args>
2409 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2410 _Compare, _Alloc>::iterator, bool>
2411 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2412 _M_emplace_unique(_Args&&... __args)
2413 {
2414 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2415
2416 __tryif (true)
2417 {
2418 typedef pair<iterator, bool> _Res;
2419 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2420 if (__res.second)
2421 return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2422
2423 _M_drop_node(__z);
2424 return _Res(iterator(__res.first), false);
2425 }
2426 __catch(...)if (false)
2427 {
2428 _M_drop_node(__z);
2429 __throw_exception_again;
2430 }
2431 }
2432
2433 template<typename _Key, typename _Val, typename _KeyOfValue,
2434 typename _Compare, typename _Alloc>
2435 template<typename... _Args>
2436 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2437 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2438 _M_emplace_equal(_Args&&... __args)
2439 {
2440 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2441
2442 __tryif (true)
2443 {
2444 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2445 return _M_insert_node(__res.first, __res.second, __z);
2446 }
2447 __catch(...)if (false)
2448 {
2449 _M_drop_node(__z);
2450 __throw_exception_again;
2451 }
2452 }
2453
2454 template<typename _Key, typename _Val, typename _KeyOfValue,
2455 typename _Compare, typename _Alloc>
2456 template<typename... _Args>
2457 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2458 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2459 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2460 {
2461 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2462
2463 __tryif (true)
2464 {
2465 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2466
2467 if (__res.second)
2468 return _M_insert_node(__res.first, __res.second, __z);
2469
2470 _M_drop_node(__z);
2471 return iterator(__res.first);
2472 }
2473 __catch(...)if (false)
2474 {
2475 _M_drop_node(__z);
2476 __throw_exception_again;
2477 }
2478 }
2479
2480 template<typename _Key, typename _Val, typename _KeyOfValue,
2481 typename _Compare, typename _Alloc>
2482 template<typename... _Args>
2483 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2484 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2485 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2486 {
2487 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2488
2489 __tryif (true)
2490 {
2491 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2492
2493 if (__res.second)
2494 return _M_insert_node(__res.first, __res.second, __z);
2495
2496 return _M_insert_equal_lower_node(__z);
2497 }
2498 __catch(...)if (false)
2499 {
2500 _M_drop_node(__z);
2501 __throw_exception_again;
2502 }
2503 }
2504#endif
2505
2506
2507 template<typename _Key, typename _Val, typename _KeyOfValue,
2508 typename _Compare, typename _Alloc>
2509 void
2510 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2511 _M_erase_aux(const_iterator __position)
2512 {
2513 _Link_type __y =
2514 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2515 (const_cast<_Base_ptr>(__position._M_node),
2516 this->_M_impl._M_header));
2517 _M_drop_node(__y);
2518 --_M_impl._M_node_count;
2519 }
2520
2521 template<typename _Key, typename _Val, typename _KeyOfValue,
2522 typename _Compare, typename _Alloc>
2523 void
2524 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2525 _M_erase_aux(const_iterator __first, const_iterator __last)
2526 {
2527 if (__first == begin() && __last == end())
2528 clear();
2529 else
2530 while (__first != __last)
2531 _M_erase_aux(__first++);
2532 }
2533
2534 template<typename _Key, typename _Val, typename _KeyOfValue,
2535 typename _Compare, typename _Alloc>
2536 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2537 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2538 erase(const _Key& __x)
2539 {
2540 pair<iterator, iterator> __p = equal_range(__x);
2541 const size_type __old_size = size();
2542 _M_erase_aux(__p.first, __p.second);
2543 return __old_size - size();
2544 }
2545
2546 template<typename _Key, typename _Val, typename _KeyOfValue,
2547 typename _Compare, typename _Alloc>
2548 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2549 _Compare, _Alloc>::iterator
2550 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2551 find(const _Key& __k)
2552 {
2553 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2554 return (__j == end()
2555 || _M_impl._M_key_compare(__k,
2556 _S_key(__j._M_node))) ? end() : __j;
2557 }
2558
2559 template<typename _Key, typename _Val, typename _KeyOfValue,
2560 typename _Compare, typename _Alloc>
2561 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2562 _Compare, _Alloc>::const_iterator
2563 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2564 find(const _Key& __k) const
2565 {
2566 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2567 return (__j == end()
2568 || _M_impl._M_key_compare(__k,
2569 _S_key(__j._M_node))) ? end() : __j;
2570 }
2571
2572 template<typename _Key, typename _Val, typename _KeyOfValue,
2573 typename _Compare, typename _Alloc>
2574 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2575 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2576 count(const _Key& __k) const
2577 {
2578 pair<const_iterator, const_iterator> __p = equal_range(__k);
2579 const size_type __n = std::distance(__p.first, __p.second);
2580 return __n;
2581 }
2582
2583 _GLIBCXX_PURE__attribute__ ((__pure__)) unsigned int
2584 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2585 const _Rb_tree_node_base* __root) throw ();
2586
2587 template<typename _Key, typename _Val, typename _KeyOfValue,
2588 typename _Compare, typename _Alloc>
2589 bool
2590 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2591 {
2592 if (_M_impl._M_node_count == 0 || begin() == end())
2593 return _M_impl._M_node_count == 0 && begin() == end()
2594 && this->_M_impl._M_header._M_left == _M_end()
2595 && this->_M_impl._M_header._M_right == _M_end();
2596
2597 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2598 for (const_iterator __it = begin(); __it != end(); ++__it)
2599 {
2600 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2601 _Const_Link_type __L = _S_left(__x);
2602 _Const_Link_type __R = _S_right(__x);
2603
2604 if (__x->_M_color == _S_red)
2605 if ((__L && __L->_M_color == _S_red)
2606 || (__R && __R->_M_color == _S_red))
2607 return false;
2608
2609 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2610 return false;
2611 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2612 return false;
2613
2614 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2615 return false;
2616 }
2617
2618 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2619 return false;
2620 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2621 return false;
2622 return true;
2623 }
2624
2625#if __cplusplus201402L > 201402L
2626 // Allow access to internals of compatible _Rb_tree specializations.
2627 template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
2628 typename _Alloc, typename _Cmp2>
2629 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
2630 _Cmp2>
2631 {
2632 private:
2633 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
2634
2635 static auto&
2636 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
2637 { return __tree._M_impl; }
2638 };
2639#endif // C++17
2640
2641_GLIBCXX_END_NAMESPACE_VERSION
2642} // namespace
2643
2644#endif