1//===- SelectionDAG.cpp - Implement the SelectionDAG data structures ------===//
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 implements the SelectionDAG class.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/SelectionDAG.h"
14#include "SDNodeDbgValue.h"
15#include "llvm/ADT/APFloat.h"
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/APSInt.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/BitVector.h"
20#include "llvm/ADT/FoldingSet.h"
21#include "llvm/ADT/None.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SmallPtrSet.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Triple.h"
26#include "llvm/ADT/Twine.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/CodeGen/ISDOpcodes.h"
29#include "llvm/CodeGen/MachineBasicBlock.h"
30#include "llvm/CodeGen/MachineConstantPool.h"
31#include "llvm/CodeGen/MachineFrameInfo.h"
32#include "llvm/CodeGen/MachineFunction.h"
33#include "llvm/CodeGen/MachineMemOperand.h"
34#include "llvm/CodeGen/RuntimeLibcalls.h"
35#include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
36#include "llvm/CodeGen/SelectionDAGNodes.h"
37#include "llvm/CodeGen/SelectionDAGTargetInfo.h"
38#include "llvm/CodeGen/TargetLowering.h"
39#include "llvm/CodeGen/TargetRegisterInfo.h"
40#include "llvm/CodeGen/TargetSubtargetInfo.h"
41#include "llvm/CodeGen/ValueTypes.h"
42#include "llvm/IR/Constant.h"
43#include "llvm/IR/Constants.h"
44#include "llvm/IR/DataLayout.h"
45#include "llvm/IR/DebugInfoMetadata.h"
46#include "llvm/IR/DebugLoc.h"
47#include "llvm/IR/DerivedTypes.h"
48#include "llvm/IR/Function.h"
49#include "llvm/IR/GlobalValue.h"
50#include "llvm/IR/Metadata.h"
51#include "llvm/IR/Type.h"
52#include "llvm/IR/Value.h"
53#include "llvm/Support/Casting.h"
54#include "llvm/Support/CodeGen.h"
55#include "llvm/Support/Compiler.h"
56#include "llvm/Support/Debug.h"
57#include "llvm/Support/ErrorHandling.h"
58#include "llvm/Support/KnownBits.h"
59#include "llvm/Support/MachineValueType.h"
60#include "llvm/Support/ManagedStatic.h"
61#include "llvm/Support/MathExtras.h"
62#include "llvm/Support/Mutex.h"
63#include "llvm/Support/raw_ostream.h"
64#include "llvm/Target/TargetMachine.h"
65#include "llvm/Target/TargetOptions.h"
66#include <algorithm>
67#include <cassert>
68#include <cstdint>
69#include <cstdlib>
70#include <limits>
71#include <set>
72#include <string>
73#include <utility>
74#include <vector>
75
76using namespace llvm;
77
78/// makeVTList - Return an instance of the SDVTList struct initialized with the
79/// specified members.
80static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
81 SDVTList Res = {VTs, NumVTs};
82 return Res;
83}
84
85// Default null implementations of the callbacks.
86void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
87void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
88
89void SelectionDAG::DAGNodeDeletedListener::anchor() {}
90
91#define DEBUG_TYPE "selectiondag"
92
93static cl::opt<bool> EnableMemCpyDAGOpt("enable-memcpy-dag-opt",
94 cl::Hidden, cl::init(true),
95 cl::desc("Gang up loads and stores generated by inlining of memcpy"));
96
97static cl::opt<int> MaxLdStGlue("ldstmemcpy-glue-max",
98 cl::desc("Number limit for gluing ld/st of memcpy."),
99 cl::Hidden, cl::init(0));
100
101static void NewSDValueDbgMsg(SDValue V, StringRef Msg, SelectionDAG *G) {
102 LLVM_DEBUG(dbgs() << Msg; V.getNode()->dump(G););
103}
104
105//===----------------------------------------------------------------------===//
106// ConstantFPSDNode Class
107//===----------------------------------------------------------------------===//
108
109/// isExactlyValue - We don't rely on operator== working on double values, as
110/// it returns true for things that are clearly not equal, like -0.0 and 0.0.
111/// As such, this method can be used to do an exact bit-for-bit comparison of
112/// two floating point values.
113bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
114 return getValueAPF().bitwiseIsEqual(V);
115}
116
117bool ConstantFPSDNode::isValueValidForType(EVT VT,
118 const APFloat& Val) {
119 assert(VT.isFloatingPoint() && "Can only convert between FP types");
120
121 // convert modifies in place, so make a copy.
122 APFloat Val2 = APFloat(Val);
123 bool losesInfo;
124 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
125 APFloat::rmNearestTiesToEven,
126 &losesInfo);
127 return !losesInfo;
128}
129
130//===----------------------------------------------------------------------===//
131// ISD Namespace
132//===----------------------------------------------------------------------===//
133
134bool ISD::isConstantSplatVector(const SDNode *N, APInt &SplatVal) {
135 auto *BV = dyn_cast<BuildVectorSDNode>(N);
136 if (!BV)
137 return false;
138
139 APInt SplatUndef;
140 unsigned SplatBitSize;
141 bool HasUndefs;
142 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
143 return BV->isConstantSplat(SplatVal, SplatUndef, SplatBitSize, HasUndefs,
144 EltSize) &&
145 EltSize == SplatBitSize;
146}
147
148// FIXME: AllOnes and AllZeros duplicate a lot of code. Could these be
149// specializations of the more general isConstantSplatVector()?
150
151bool ISD::isBuildVectorAllOnes(const SDNode *N) {
152 // Look through a bit convert.
153 while (N->getOpcode() == ISD::BITCAST)
154 N = N->getOperand(0).getNode();
155
156 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
157
158 unsigned i = 0, e = N->getNumOperands();
159
160 // Skip over all of the undef values.
161 while (i != e && N->getOperand(i).isUndef())
162 ++i;
163
164 // Do not accept an all-undef vector.
165 if (i == e) return false;
166
167 // Do not accept build_vectors that aren't all constants or which have non-~0
168 // elements. We have to be a bit careful here, as the type of the constant
169 // may not be the same as the type of the vector elements due to type
170 // legalization (the elements are promoted to a legal type for the target and
171 // a vector of a type may be legal when the base element type is not).
172 // We only want to check enough bits to cover the vector elements, because
173 // we care if the resultant vector is all ones, not whether the individual
174 // constants are.
175 SDValue NotZero = N->getOperand(i);
176 unsigned EltSize = N->getValueType(0).getScalarSizeInBits();
177 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
178 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
179 return false;
180 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
181 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
182 return false;
183 } else
184 return false;
185
186 // Okay, we have at least one ~0 value, check to see if the rest match or are
187 // undefs. Even with the above element type twiddling, this should be OK, as
188 // the same type legalization should have applied to all the elements.
189 for (++i; i != e; ++i)
190 if (N->getOperand(i) != NotZero && !N->getOperand(i).isUndef())
191 return false;
192 return true;
193}
194
195bool ISD::isBuildVectorAllZeros(const SDNode *N) {
196 // Look through a bit convert.
197 while (N->getOpcode() == ISD::BITCAST)
198 N = N->getOperand(0).getNode();
199
200 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
201
202 bool IsAllUndef = true;
203 for (const SDValue &Op : N->op_values()) {
204 if (Op.isUndef())
205 continue;
206 IsAllUndef = false;
207 // Do not accept build_vectors that aren't all constants or which have non-0
208 // elements. We have to be a bit careful here, as the type of the constant
209 // may not be the same as the type of the vector elements due to type
210 // legalization (the elements are promoted to a legal type for the target
211 // and a vector of a type may be legal when the base element type is not).
212 // We only want to check enough bits to cover the vector elements, because
213 // we care if the resultant vector is all zeros, not whether the individual
214 // constants are.
215 unsigned EltSize = N->getValueType(0).getScalarSizeInBits();
216 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
217 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
218 return false;
219 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Op)) {
220 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
221 return false;
222 } else
223 return false;
224 }
225
226 // Do not accept an all-undef vector.
227 if (IsAllUndef)
228 return false;
229 return true;
230}
231
232bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
233 if (N->getOpcode() != ISD::BUILD_VECTOR)
234 return false;
235
236 for (const SDValue &Op : N->op_values()) {
237 if (Op.isUndef())
238 continue;
239 if (!isa<ConstantSDNode>(Op))
240 return false;
241 }
242 return true;
243}
244
245bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
246 if (N->getOpcode() != ISD::BUILD_VECTOR)
247 return false;
248
249 for (const SDValue &Op : N->op_values()) {
250 if (Op.isUndef())
251 continue;
252 if (!isa<ConstantFPSDNode>(Op))
253 return false;
254 }
255 return true;
256}
257
258bool ISD::allOperandsUndef(const SDNode *N) {
259 // Return false if the node has no operands.
260 // This is "logically inconsistent" with the definition of "all" but
261 // is probably the desired behavior.
262 if (N->getNumOperands() == 0)
263 return false;
264
265 for (const SDValue &Op : N->op_values())
266 if (!Op.isUndef())
267 return false;
268
269 return true;
270}
271
272bool ISD::matchUnaryPredicate(SDValue Op,
273 std::function<bool(ConstantSDNode *)> Match,
274 bool AllowUndefs) {
275 // FIXME: Add support for scalar UNDEF cases?
276 if (auto *Cst = dyn_cast<ConstantSDNode>(Op))
277 return Match(Cst);
278
279 // FIXME: Add support for vector UNDEF cases?
280 if (ISD::BUILD_VECTOR != Op.getOpcode())
281 return false;
282
283 EVT SVT = Op.getValueType().getScalarType();
284 for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
285 if (AllowUndefs && Op.getOperand(i).isUndef()) {
286 if (!Match(nullptr))
287 return false;
288 continue;
289 }
290
291 auto *Cst = dyn_cast<ConstantSDNode>(Op.getOperand(i));
292 if (!Cst || Cst->getValueType(0) != SVT || !Match(Cst))
293 return false;
294 }
295 return true;
296}
297
298bool ISD::matchBinaryPredicate(
299 SDValue LHS, SDValue RHS,
300 std::function<bool(ConstantSDNode *, ConstantSDNode *)> Match,
301 bool AllowUndefs) {
302 if (LHS.getValueType() != RHS.getValueType())
303 return false;
304
305 // TODO: Add support for scalar UNDEF cases?
306 if (auto *LHSCst = dyn_cast<ConstantSDNode>(LHS))
307 if (auto *RHSCst = dyn_cast<ConstantSDNode>(RHS))
308 return Match(LHSCst, RHSCst);
309
310 // TODO: Add support for vector UNDEF cases?
311 if (ISD::BUILD_VECTOR != LHS.getOpcode() ||
312 ISD::BUILD_VECTOR != RHS.getOpcode())
313 return false;
314
315 EVT SVT = LHS.getValueType().getScalarType();
316 for (unsigned i = 0, e = LHS.getNumOperands(); i != e; ++i) {
317 SDValue LHSOp = LHS.getOperand(i);
318 SDValue RHSOp = RHS.getOperand(i);
319 bool LHSUndef = AllowUndefs && LHSOp.isUndef();
320 bool RHSUndef = AllowUndefs && RHSOp.isUndef();
321 auto *LHSCst = dyn_cast<ConstantSDNode>(LHSOp);
322 auto *RHSCst = dyn_cast<ConstantSDNode>(RHSOp);
323 if ((!LHSCst && !LHSUndef) || (!RHSCst && !RHSUndef))
324 return false;
325 if (LHSOp.getValueType() != SVT ||
326 LHSOp.getValueType() != RHSOp.getValueType())
327 return false;
328 if (!Match(LHSCst, RHSCst))
329 return false;
330 }
331 return true;
332}
333
334ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
335 switch (ExtType) {
336 case ISD::EXTLOAD:
337 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
338 case ISD::SEXTLOAD:
339 return ISD::SIGN_EXTEND;
340 case ISD::ZEXTLOAD:
341 return ISD::ZERO_EXTEND;
342 default:
343 break;
344 }
345
346 llvm_unreachable("Invalid LoadExtType");
347}
348
349ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
350 // To perform this operation, we just need to swap the L and G bits of the
351 // operation.
352 unsigned OldL = (Operation >> 2) & 1;
353 unsigned OldG = (Operation >> 1) & 1;
354 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
355 (OldL << 1) | // New G bit
356 (OldG << 2)); // New L bit.
357}
358
359ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
360 unsigned Operation = Op;
361 if (isInteger)
362 Operation ^= 7; // Flip L, G, E bits, but not U.
363 else
364 Operation ^= 15; // Flip all of the condition bits.
365
366 if (Operation > ISD::SETTRUE2)
367 Operation &= ~8; // Don't let N and U bits get set.
368
369 return ISD::CondCode(Operation);
370}
371
372/// For an integer comparison, return 1 if the comparison is a signed operation
373/// and 2 if the result is an unsigned comparison. Return zero if the operation
374/// does not depend on the sign of the input (setne and seteq).
375static int isSignedOp(ISD::CondCode Opcode) {
376 switch (Opcode) {
377 default: llvm_unreachable("Illegal integer setcc operation!");
378 case ISD::SETEQ:
379 case ISD::SETNE: return 0;
380 case ISD::SETLT:
381 case ISD::SETLE:
382 case ISD::SETGT:
383 case ISD::SETGE: return 1;
384 case ISD::SETULT:
385 case ISD::SETULE:
386 case ISD::SETUGT:
387 case ISD::SETUGE: return 2;
388 }
389}
390
391ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
392 bool IsInteger) {
393 if (IsInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
394 // Cannot fold a signed integer setcc with an unsigned integer setcc.
395 return ISD::SETCC_INVALID;
396
397 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
398
399 // If the N and U bits get set, then the resultant comparison DOES suddenly
400 // care about orderedness, and it is true when ordered.
401 if (Op > ISD::SETTRUE2)
402 Op &= ~16; // Clear the U bit if the N bit is set.
403
404 // Canonicalize illegal integer setcc's.
405 if (IsInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
406 Op = ISD::SETNE;
407
408 return ISD::CondCode(Op);
409}
410
411ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
412 bool IsInteger) {
413 if (IsInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
414 // Cannot fold a signed setcc with an unsigned setcc.
415 return ISD::SETCC_INVALID;
416
417 // Combine all of the condition bits.
418 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
419
420 // Canonicalize illegal integer setcc's.
421 if (IsInteger) {
422 switch (Result) {
423 default: break;
424 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
425 case ISD::SETOEQ: // SETEQ & SETU[LG]E
426 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
427 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
428 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
429 }
430 }
431
432 return Result;
433}
434
435//===----------------------------------------------------------------------===//
436// SDNode Profile Support
437//===----------------------------------------------------------------------===//
438
439/// AddNodeIDOpcode - Add the node opcode to the NodeID data.
440static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
441 ID.AddInteger(OpC);
442}
443
444/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
445/// solely with their pointer.
446static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
447 ID.AddPointer(VTList.VTs);
448}
449
450/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
451static void AddNodeIDOperands(FoldingSetNodeID &ID,
452 ArrayRef<SDValue> Ops) {
453 for (auto& Op : Ops) {
454 ID.AddPointer(Op.getNode());
455 ID.AddInteger(Op.getResNo());
456 }
457}
458
459/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
460static void AddNodeIDOperands(FoldingSetNodeID &ID,
461 ArrayRef<SDUse> Ops) {
462 for (auto& Op : Ops) {
463 ID.AddPointer(Op.getNode());
464 ID.AddInteger(Op.getResNo());
465 }
466}
467
468static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
469 SDVTList VTList, ArrayRef<SDValue> OpList) {
470 AddNodeIDOpcode(ID, OpC);
471 AddNodeIDValueTypes(ID, VTList);
472 AddNodeIDOperands(ID, OpList);
473}
474
475/// If this is an SDNode with special info, add this info to the NodeID data.
476static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
477 switch (N->getOpcode()) {
478 case ISD::TargetExternalSymbol:
479 case ISD::ExternalSymbol:
480 case ISD::MCSymbol:
481 llvm_unreachable("Should only be used on nodes with operands");
482 default: break; // Normal nodes don't need extra info.
483 case ISD::TargetConstant:
484 case ISD::Constant: {
485 const ConstantSDNode *C = cast<ConstantSDNode>(N);
486 ID.AddPointer(C->getConstantIntValue());
487 ID.AddBoolean(C->isOpaque());
488 break;
489 }
490 case ISD::TargetConstantFP:
491 case ISD::ConstantFP:
492 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
493 break;
494 case ISD::TargetGlobalAddress:
495 case ISD::GlobalAddress:
496 case ISD::TargetGlobalTLSAddress:
497 case ISD::GlobalTLSAddress: {
498 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
499 ID.AddPointer(GA->getGlobal());
500 ID.AddInteger(GA->getOffset());
501 ID.AddInteger(GA->getTargetFlags());
502 break;
503 }
504 case ISD::BasicBlock:
505 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
506 break;
507 case ISD::Register:
508 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
509 break;
510 case ISD::RegisterMask:
511 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
512 break;
513 case ISD::SRCVALUE:
514 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
515 break;
516 case ISD::FrameIndex:
517 case ISD::TargetFrameIndex:
518 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
519 break;
520 case ISD::JumpTable:
521 case ISD::TargetJumpTable:
522 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
523 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
524 break;
525 case ISD::ConstantPool:
526 case ISD::TargetConstantPool: {
527 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
528 ID.AddInteger(CP->getAlignment());
529 ID.AddInteger(CP->getOffset());
530 if (CP->isMachineConstantPoolEntry())
531 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
532 else
533 ID.AddPointer(CP->getConstVal());
534 ID.AddInteger(CP->getTargetFlags());
535 break;
536 }
537 case ISD::TargetIndex: {
538 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
539 ID.AddInteger(TI->getIndex());
540 ID.AddInteger(TI->getOffset());
541 ID.AddInteger(TI->getTargetFlags());
542 break;
543 }
544 case ISD::LOAD: {
545 const LoadSDNode *LD = cast<LoadSDNode>(N);
546 ID.AddInteger(LD->getMemoryVT().getRawBits());
547 ID.AddInteger(LD->getRawSubclassData());
548 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
549 break;
550 }
551 case ISD::STORE: {
552 const StoreSDNode *ST = cast<StoreSDNode>(N);
553 ID.AddInteger(ST->getMemoryVT().getRawBits());
554 ID.AddInteger(ST->getRawSubclassData());
555 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
556 break;
557 }
558 case ISD::MLOAD: {
559 const MaskedLoadSDNode *MLD = cast<MaskedLoadSDNode>(N);
560 ID.AddInteger(MLD->getMemoryVT().getRawBits());
561 ID.AddInteger(MLD->getRawSubclassData());
562 ID.AddInteger(MLD->getPointerInfo().getAddrSpace());
563 break;
564 }
565 case ISD::MSTORE: {
566 const MaskedStoreSDNode *MST = cast<MaskedStoreSDNode>(N);
567 ID.AddInteger(MST->getMemoryVT().getRawBits());
568 ID.AddInteger(MST->getRawSubclassData());
569 ID.AddInteger(MST->getPointerInfo().getAddrSpace());
570 break;
571 }
572 case ISD::MGATHER: {
573 const MaskedGatherSDNode *MG = cast<MaskedGatherSDNode>(N);
574 ID.AddInteger(MG->getMemoryVT().getRawBits());
575 ID.AddInteger(MG->getRawSubclassData());
576 ID.AddInteger(MG->getPointerInfo().getAddrSpace());
577 break;
578 }
579 case ISD::MSCATTER: {
580 const MaskedScatterSDNode *MS = cast<MaskedScatterSDNode>(N);
581 ID.AddInteger(MS->getMemoryVT().getRawBits());
582 ID.AddInteger(MS->getRawSubclassData());
583 ID.AddInteger(MS->getPointerInfo().getAddrSpace());
584 break;
585 }
586 case ISD::ATOMIC_CMP_SWAP:
587 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
588 case ISD::ATOMIC_SWAP:
589 case ISD::ATOMIC_LOAD_ADD:
590 case ISD::ATOMIC_LOAD_SUB:
591 case ISD::ATOMIC_LOAD_AND:
592 case ISD::ATOMIC_LOAD_CLR:
593 case ISD::ATOMIC_LOAD_OR:
594 case ISD::ATOMIC_LOAD_XOR:
595 case ISD::ATOMIC_LOAD_NAND:
596 case ISD::ATOMIC_LOAD_MIN:
597 case ISD::ATOMIC_LOAD_MAX:
598 case ISD::ATOMIC_LOAD_UMIN:
599 case ISD::ATOMIC_LOAD_UMAX:
600 case ISD::ATOMIC_LOAD:
601 case ISD::ATOMIC_STORE: {
602 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
603 ID.AddInteger(AT->getMemoryVT().getRawBits());
604 ID.AddInteger(AT->getRawSubclassData());
605 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
606 break;
607 }
608 case ISD::PREFETCH: {
609 const MemSDNode *PF = cast<MemSDNode>(N);
610 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
611 break;
612 }
613 case ISD::VECTOR_SHUFFLE: {
614 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
615 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
616 i != e; ++i)
617 ID.AddInteger(SVN->getMaskElt(i));
618 break;
619 }
620 case ISD::TargetBlockAddress:
621 case ISD::BlockAddress: {
622 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
623 ID.AddPointer(BA->getBlockAddress());
624 ID.AddInteger(BA->getOffset());
625 ID.AddInteger(BA->getTargetFlags());
626 break;
627 }
628 } // end switch (N->getOpcode())
629
630 // Target specific memory nodes could also have address spaces to check.
631 if (N->isTargetMemoryOpcode())
632 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
633}
634
635/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
636/// data.
637static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
638 AddNodeIDOpcode(ID, N->getOpcode());
639 // Add the return value info.
640 AddNodeIDValueTypes(ID, N->getVTList());
641 // Add the operand info.
642 AddNodeIDOperands(ID, N->ops());
643
644 // Handle SDNode leafs with special info.
645 AddNodeIDCustom(ID, N);
646}
647
648//===----------------------------------------------------------------------===//
649// SelectionDAG Class
650//===----------------------------------------------------------------------===//
651
652/// doNotCSE - Return true if CSE should not be performed for this node.
653static bool doNotCSE(SDNode *N) {
654 if (N->getValueType(0) == MVT::Glue)
655 return true; // Never CSE anything that produces a flag.
656
657 switch (N->getOpcode()) {
658 default: break;
659 case ISD::HANDLENODE:
660 case ISD::EH_LABEL:
661 return true; // Never CSE these nodes.
662 }
663
664 // Check that remaining values produced are not flags.
665 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
666 if (N->getValueType(i) == MVT::Glue)
667 return true; // Never CSE anything that produces a flag.
668
669 return false;
670}
671
672/// RemoveDeadNodes - This method deletes all unreachable nodes in the
673/// SelectionDAG.
674void SelectionDAG::RemoveDeadNodes() {
675 // Create a dummy node (which is not added to allnodes), that adds a reference
676 // to the root node, preventing it from being deleted.
677 HandleSDNode Dummy(getRoot());
678
679 SmallVector<SDNode*, 128> DeadNodes;
680
681 // Add all obviously-dead nodes to the DeadNodes worklist.
682 for (SDNode &Node : allnodes())
683 if (Node.use_empty())
684 DeadNodes.push_back(&Node);
685
686 RemoveDeadNodes(DeadNodes);
687
688 // If the root changed (e.g. it was a dead load, update the root).
689 setRoot(Dummy.getValue());
690}
691
692/// RemoveDeadNodes - This method deletes the unreachable nodes in the
693/// given list, and any nodes that become unreachable as a result.
694void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
695
696 // Process the worklist, deleting the nodes and adding their uses to the
697 // worklist.
698 while (!DeadNodes.empty()) {
699 SDNode *N = DeadNodes.pop_back_val();
700 // Skip to next node if we've already managed to delete the node. This could
701 // happen if replacing a node causes a node previously added to the node to
702 // be deleted.
703 if (N->getOpcode() == ISD::DELETED_NODE)
704 continue;
705
706 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
707 DUL->NodeDeleted(N, nullptr);
708
709 // Take the node out of the appropriate CSE map.
710 RemoveNodeFromCSEMaps(N);
711
712 // Next, brutally remove the operand list. This is safe to do, as there are
713 // no cycles in the graph.
714 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
715 SDUse &Use = *I++;
716 SDNode *Operand = Use.getNode();
717 Use.set(SDValue());
718
719 // Now that we removed this operand, see if there are no uses of it left.
720 if (Operand->use_empty())
721 DeadNodes.push_back(Operand);
722 }
723
724 DeallocateNode(N);
725 }
726}
727
728void SelectionDAG::RemoveDeadNode(SDNode *N){
729 SmallVector<SDNode*, 16> DeadNodes(1, N);
730
731 // Create a dummy node that adds a reference to the root node, preventing
732 // it from being deleted. (This matters if the root is an operand of the
733 // dead node.)
734 HandleSDNode Dummy(getRoot());
735
736 RemoveDeadNodes(DeadNodes);
737}
738
739void SelectionDAG::DeleteNode(SDNode *N) {
740 // First take this out of the appropriate CSE map.
741 RemoveNodeFromCSEMaps(N);
742
743 // Finally, remove uses due to operands of this node, remove from the
744 // AllNodes list, and delete the node.
745 DeleteNodeNotInCSEMaps(N);
746}
747
748void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
749 assert(N->getIterator() != AllNodes.begin() &&
750 "Cannot delete the entry node!");
751 assert(N->use_empty() && "Cannot delete a node that is not dead!");
752
753 // Drop all of the operands and decrement used node's use counts.
754 N->DropOperands();
755
756 DeallocateNode(N);
757}
758
759void SDDbgInfo::erase(const SDNode *Node) {
760 DbgValMapType::iterator I = DbgValMap.find(Node);
761 if (I == DbgValMap.end())
762 return;
763 for (auto &Val: I->second)
764 Val->setIsInvalidated();
765 DbgValMap.erase(I);
766}
767
768void SelectionDAG::DeallocateNode(SDNode *N) {
769 // If we have operands, deallocate them.
770 removeOperands(N);
771
772 NodeAllocator.Deallocate(AllNodes.remove(N));
773
774 // Set the opcode to DELETED_NODE to help catch bugs when node
775 // memory is reallocated.
776 // FIXME: There are places in SDag that have grown a dependency on the opcode
777 // value in the released node.
778 __asan_unpoison_memory_region(&N->NodeType, sizeof(N->NodeType));
779 N->NodeType = ISD::DELETED_NODE;
780
781 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
782 // them and forget about that node.
783 DbgInfo->erase(N);
784}
785
786#ifndef NDEBUG
787/// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
788static void VerifySDNode(SDNode *N) {
789 switch (N->getOpcode()) {
790 default:
791 break;
792 case ISD::BUILD_PAIR: {
793 EVT VT = N->getValueType(0);
794 assert(N->getNumValues() == 1 && "Too many results!");
795 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
796 "Wrong return type!");
797 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
798 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
799 "Mismatched operand types!");
800 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
801 "Wrong operand type!");
802 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
803 "Wrong return type size");
804 break;
805 }
806 case ISD::BUILD_VECTOR: {
807 assert(N->getNumValues() == 1 && "Too many results!");
808 assert(N->getValueType(0).isVector() && "Wrong return type!");
809 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
810 "Wrong number of operands!");
811 EVT EltVT = N->getValueType(0).getVectorElementType();
812 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
813 assert((I->getValueType() == EltVT ||
814 (EltVT.isInteger() && I->getValueType().isInteger() &&
815 EltVT.bitsLE(I->getValueType()))) &&
816 "Wrong operand type!");
817 assert(I->getValueType() == N->getOperand(0).getValueType() &&
818 "Operands must all have the same type");
819 }
820 break;
821 }
822 }
823}
824#endif // NDEBUG
825
826/// Insert a newly allocated node into the DAG.
827///
828/// Handles insertion into the all nodes list and CSE map, as well as
829/// verification and other common operations when a new node is allocated.
830void SelectionDAG::InsertNode(SDNode *N) {
831 AllNodes.push_back(N);
832#ifndef NDEBUG
833 N->PersistentId = NextPersistentId++;
834 VerifySDNode(N);
835#endif
836}
837
838/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
839/// correspond to it. This is useful when we're about to delete or repurpose
840/// the node. We don't want future request for structurally identical nodes
841/// to return N anymore.
842bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
843 bool Erased = false;
844 switch (N->getOpcode()) {
845 case ISD::HANDLENODE: return false; // noop.
846 case ISD::CONDCODE:
847 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
848 "Cond code doesn't exist!");
849 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
850 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
851 break;
852 case ISD::ExternalSymbol:
853 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
854 break;
855 case ISD::TargetExternalSymbol: {
856 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
857 Erased = TargetExternalSymbols.erase(
858 std::pair<std::string,unsigned char>(ESN->getSymbol(),
859 ESN->getTargetFlags()));
860 break;
861 }
862 case ISD::MCSymbol: {
863 auto *MCSN = cast<MCSymbolSDNode>(N);
864 Erased = MCSymbols.erase(MCSN->getMCSymbol());
865 break;
866 }
867 case ISD::VALUETYPE: {
868 EVT VT = cast<VTSDNode>(N)->getVT();
869 if (VT.isExtended()) {
870 Erased = ExtendedValueTypeNodes.erase(VT);
871 } else {
872 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
873 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
874 }
875 break;
876 }
877 default:
878 // Remove it from the CSE Map.
879 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
880 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
881 Erased = CSEMap.RemoveNode(N);
882 break;
883 }
884#ifndef NDEBUG
885 // Verify that the node was actually in one of the CSE maps, unless it has a
886 // flag result (which cannot be CSE'd) or is one of the special cases that are
887 // not subject to CSE.
888 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
889 !N->isMachineOpcode() && !doNotCSE(N)) {
890 N->dump(this);
891 dbgs() << "\n";
892 llvm_unreachable("Node is not in map!");
893 }
894#endif
895 return Erased;
896}
897
898/// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
899/// maps and modified in place. Add it back to the CSE maps, unless an identical
900/// node already exists, in which case transfer all its users to the existing
901/// node. This transfer can potentially trigger recursive merging.
902void
903SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
904 // For node types that aren't CSE'd, just act as if no identical node
905 // already exists.
906 if (!doNotCSE(N)) {
907 SDNode *Existing = CSEMap.GetOrInsertNode(N);
908 if (Existing != N) {
909 // If there was already an existing matching node, use ReplaceAllUsesWith
910 // to replace the dead one with the existing one. This can cause
911 // recursive merging of other unrelated nodes down the line.
912 ReplaceAllUsesWith(N, Existing);
913
914 // N is now dead. Inform the listeners and delete it.
915 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
916 DUL->NodeDeleted(N, Existing);
917 DeleteNodeNotInCSEMaps(N);
918 return;
919 }
920 }
921
922 // If the node doesn't already exist, we updated it. Inform listeners.
923 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
924 DUL->NodeUpdated(N);
925}
926
927/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
928/// were replaced with those specified. If this node is never memoized,
929/// return null, otherwise return a pointer to the slot it would take. If a
930/// node already exists with these operands, the slot will be non-null.
931SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
932 void *&InsertPos) {
933 if (doNotCSE(N))
934 return nullptr;
935
936 SDValue Ops[] = { Op };
937 FoldingSetNodeID ID;
938 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
939 AddNodeIDCustom(ID, N);
940 SDNode *Node = FindNodeOrInsertPos(ID, SDLoc(N), InsertPos);
941 if (Node)
942 Node->intersectFlagsWith(N->getFlags());
943 return Node;
944}
945
946/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
947/// were replaced with those specified. If this node is never memoized,
948/// return null, otherwise return a pointer to the slot it would take. If a
949/// node already exists with these operands, the slot will be non-null.
950SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
951 SDValue Op1, SDValue Op2,
952 void *&InsertPos) {
953 if (doNotCSE(N))
954 return nullptr;
955
956 SDValue Ops[] = { Op1, Op2 };
957 FoldingSetNodeID ID;
958 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
959 AddNodeIDCustom(ID, N);
960 SDNode *Node = FindNodeOrInsertPos(ID, SDLoc(N), InsertPos);
961 if (Node)
962 Node->intersectFlagsWith(N->getFlags());
963 return Node;
964}
965
966/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
967/// were replaced with those specified. If this node is never memoized,
968/// return null, otherwise return a pointer to the slot it would take. If a
969/// node already exists with these operands, the slot will be non-null.
970SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
971 void *&InsertPos) {
972 if (doNotCSE(N))
973 return nullptr;
974
975 FoldingSetNodeID ID;
976 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
977 AddNodeIDCustom(ID, N);
978 SDNode *Node = FindNodeOrInsertPos(ID, SDLoc(N), InsertPos);
979 if (Node)
980 Node->intersectFlagsWith(N->getFlags());
981 return Node;
982}
983
984unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
985 Type *Ty = VT == MVT::iPTR ?
986 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
987 VT.getTypeForEVT(*getContext());
988
989 return getDataLayout().getABITypeAlignment(Ty);
990}
991
992// EntryNode could meaningfully have debug info if we can find it...
993SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
994 : TM(tm), OptLevel(OL),
995 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
996 Root(getEntryNode()) {
997 InsertNode(&EntryNode);
998 DbgInfo = new SDDbgInfo();
999}
1000
1001void SelectionDAG::init(MachineFunction &NewMF,
1002 OptimizationRemarkEmitter &NewORE,
1003 Pass *PassPtr, const TargetLibraryInfo *LibraryInfo,
1004 LegacyDivergenceAnalysis * Divergence) {
1005 MF = &NewMF;
1006 SDAGISelPass = PassPtr;
1007 ORE = &NewORE;
1008 TLI = getSubtarget().getTargetLowering();
1009 TSI = getSubtarget().getSelectionDAGInfo();
1010 LibInfo = LibraryInfo;
1011 Context = &MF->getFunction().getContext();
1012 DA = Divergence;
1013}
1014
1015SelectionDAG::~SelectionDAG() {
1016 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
1017 allnodes_clear();
1018 OperandRecycler.clear(OperandAllocator);
1019 delete DbgInfo;
1020}
1021
1022void SelectionDAG::allnodes_clear() {
1023 assert(&*AllNodes.begin() == &EntryNode);
1024 AllNodes.remove(AllNodes.begin());
1025 while (!AllNodes.empty())
1026 DeallocateNode(&AllNodes.front());
1027#ifndef NDEBUG
1028 NextPersistentId = 0;
1029#endif
1030}
1031
1032SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
1033 void *&InsertPos) {
1034 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
1035 if (N) {
1036 switch (N->getOpcode()) {
1037 default: break;
1038 case ISD::Constant:
1039 case ISD::ConstantFP:
1040 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
1041 "debug location. Use another overload.");
1042 }
1043 }
1044 return N;
1045}
1046
1047SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
1048 const SDLoc &DL, void *&InsertPos) {
1049 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
1050 if (N) {
1051 switch (N->getOpcode()) {
1052 case ISD::Constant:
1053 case ISD::ConstantFP:
1054 // Erase debug location from the node if the node is used at several
1055 // different places. Do not propagate one location to all uses as it
1056 // will cause a worse single stepping debugging experience.
1057 if (N->getDebugLoc() != DL.getDebugLoc())
1058 N->setDebugLoc(DebugLoc());
1059 break;
1060 default:
1061 // When the node's point of use is located earlier in the instruction
1062 // sequence than its prior point of use, update its debug info to the
1063 // earlier location.
1064 if (DL.getIROrder() && DL.getIROrder() < N->getIROrder())
1065 N->setDebugLoc(DL.getDebugLoc());
1066 break;
1067 }
1068 }
1069 return N;
1070}
1071
1072void SelectionDAG::clear() {
1073 allnodes_clear();
1074 OperandRecycler.clear(OperandAllocator);
1075 OperandAllocator.Reset();
1076 CSEMap.clear();
1077
1078 ExtendedValueTypeNodes.clear();
1079 ExternalSymbols.clear();
1080 TargetExternalSymbols.clear();
1081 MCSymbols.clear();
1082 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1083 static_cast<CondCodeSDNode*>(nullptr));
1084 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1085 static_cast<SDNode*>(nullptr));
1086
1087 EntryNode.UseList = nullptr;
1088 InsertNode(&EntryNode);
1089 Root = getEntryNode();
1090 DbgInfo->clear();
1091}
1092
1093SDValue SelectionDAG::getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT) {
1094 return VT.bitsGT(Op.getValueType())
1095 ? getNode(ISD::FP_EXTEND, DL, VT, Op)
1096 : getNode(ISD::FP_ROUND, DL, VT, Op, getIntPtrConstant(0, DL));
1097}
1098
1099SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT) {
1100 return VT.bitsGT(Op.getValueType()) ?
1101 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1102 getNode(ISD::TRUNCATE, DL, VT, Op);
1103}
1104
1105SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT) {
1106 return VT.bitsGT(Op.getValueType()) ?
1107 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1108 getNode(ISD::TRUNCATE, DL, VT, Op);
1109}
1110
1111SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT) {
1112 return VT.bitsGT(Op.getValueType()) ?
1113 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1114 getNode(ISD::TRUNCATE, DL, VT, Op);
1115}
1116
1117SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT,
1118 EVT OpVT) {
1119 if (VT.bitsLE(Op.getValueType()))
1120 return getNode(ISD::TRUNCATE, SL, VT, Op);
1121
1122 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1123 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1124}
1125
1126SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT VT) {
1127 assert(!VT.isVector() &&
1128 "getZeroExtendInReg should use the vector element type instead of "
1129 "the vector type!");
1130 if (Op.getValueType().getScalarType() == VT) return Op;
1131 unsigned BitWidth = Op.getScalarValueSizeInBits();
1132 APInt Imm = APInt::getLowBitsSet(BitWidth,
1133 VT.getSizeInBits());
1134 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1135 getConstant(Imm, DL, Op.getValueType()));
1136}
1137
1138/// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1139SDValue SelectionDAG::getNOT(const SDLoc &DL, SDValue Val, EVT VT) {
1140 EVT EltVT = VT.getScalarType();
1141 SDValue NegOne =
1142 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1143 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1144}
1145
1146SDValue SelectionDAG::getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT) {
1147 SDValue TrueValue = getBoolConstant(true, DL, VT, VT);
1148 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1149}
1150
1151SDValue SelectionDAG::getBoolConstant(bool V, const SDLoc &DL, EVT VT,
1152 EVT OpVT) {
1153 if (!V)
1154 return getConstant(0, DL, VT);
1155
1156 switch (TLI->getBooleanContents(OpVT)) {
1157 case TargetLowering::ZeroOrOneBooleanContent:
1158 case TargetLowering::UndefinedBooleanContent:
1159 return getConstant(1, DL, VT);
1160 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1161 return getAllOnesConstant(DL, VT);
1162 }
1163 llvm_unreachable("Unexpected boolean content enum!");
1164}
1165
1166SDValue SelectionDAG::getConstant(uint64_t Val, const SDLoc &DL, EVT VT,
1167 bool isT, bool isO) {
1168 EVT EltVT = VT.getScalarType();
1169 assert((EltVT.getSizeInBits() >= 64 ||
1170 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1171 "getConstant with a uint64_t value that doesn't fit in the type!");
1172 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1173}
1174
1175SDValue SelectionDAG::getConstant(const APInt &Val, const SDLoc &DL, EVT VT,
1176 bool isT, bool isO) {
1177 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1178}
1179
1180SDValue SelectionDAG::getConstant(const ConstantInt &Val, const SDLoc &DL,
1181 EVT VT, bool isT, bool isO) {
1182 assert(VT.isInteger() && "Cannot create FP integer constant!");
1183
1184 EVT EltVT = VT.getScalarType();
1185 const ConstantInt *Elt = &Val;
1186
1187 // In some cases the vector type is legal but the element type is illegal and
1188 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1189 // inserted value (the type does not need to match the vector element type).
1190 // Any extra bits introduced will be truncated away.
1191 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1192 TargetLowering::TypePromoteInteger) {
1193 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1194 APInt NewVal = Elt->getValue().zextOrTrunc(EltVT.getSizeInBits());
1195 Elt = ConstantInt::get(*getContext(), NewVal);
1196 }
1197 // In other cases the element type is illegal and needs to be expanded, for
1198 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1199 // the value into n parts and use a vector type with n-times the elements.
1200 // Then bitcast to the type requested.
1201 // Legalizing constants too early makes the DAGCombiner's job harder so we
1202 // only legalize if the DAG tells us we must produce legal types.
1203 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1204 TLI->getTypeAction(*getContext(), EltVT) ==
1205 TargetLowering::TypeExpandInteger) {
1206 const APInt &NewVal = Elt->getValue();
1207 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1208 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1209 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1210 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1211
1212 // Check the temporary vector is the correct size. If this fails then
1213 // getTypeToTransformTo() probably returned a type whose size (in bits)
1214 // isn't a power-of-2 factor of the requested type size.
1215 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1216
1217 SmallVector<SDValue, 2> EltParts;
1218 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1219 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1220 .zextOrTrunc(ViaEltSizeInBits), DL,
1221 ViaEltVT, isT, isO));
1222 }
1223
1224 // EltParts is currently in little endian order. If we actually want
1225 // big-endian order then reverse it now.
1226 if (getDataLayout().isBigEndian())
1227 std::reverse(EltParts.begin(), EltParts.end());
1228
1229 // The elements must be reversed when the element order is different
1230 // to the endianness of the elements (because the BITCAST is itself a
1231 // vector shuffle in this situation). However, we do not need any code to
1232 // perform this reversal because getConstant() is producing a vector
1233 // splat.
1234 // This situation occurs in MIPS MSA.
1235
1236 SmallVector<SDValue, 8> Ops;
1237 for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i)
1238 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1239
1240 SDValue V = getNode(ISD::BITCAST, DL, VT, getBuildVector(ViaVecVT, DL, Ops));
1241 return V;
1242 }
1243
1244 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1245 "APInt size does not match type size!");
1246 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1247 FoldingSetNodeID ID;
1248 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1249 ID.AddPointer(Elt);
1250 ID.AddBoolean(isO);
1251 void *IP = nullptr;
1252 SDNode *N = nullptr;
1253 if ((N = FindNodeOrInsertPos(ID, DL, IP)))
1254 if (!VT.isVector())
1255 return SDValue(N, 0);
1256
1257 if (!N) {
1258 N = newSDNode<ConstantSDNode>(isT, isO, Elt, EltVT);
1259 CSEMap.InsertNode(N, IP);
1260 InsertNode(N);
1261 NewSDValueDbgMsg(SDValue(N, 0), "Creating constant: ", this);
1262 }
1263
1264 SDValue Result(N, 0);
1265 if (VT.isVector())
1266 Result = getSplatBuildVector(VT, DL, Result);
1267
1268 return Result;
1269}
1270
1271SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, const SDLoc &DL,
1272 bool isTarget) {
1273 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1274}
1275
1276SDValue SelectionDAG::getConstantFP(const APFloat &V, const SDLoc &DL, EVT VT,
1277 bool isTarget) {
1278 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1279}
1280
1281SDValue SelectionDAG::getConstantFP(const ConstantFP &V, const SDLoc &DL,
1282 EVT VT, bool isTarget) {
1283 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1284
1285 EVT EltVT = VT.getScalarType();
1286
1287 // Do the map lookup using the actual bit pattern for the floating point
1288 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1289 // we don't have issues with SNANs.
1290 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1291 FoldingSetNodeID ID;
1292 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1293 ID.AddPointer(&V);
1294 void *IP = nullptr;
1295 SDNode *N = nullptr;
1296 if ((N = FindNodeOrInsertPos(ID, DL, IP)))
1297 if (!VT.isVector())
1298 return SDValue(N, 0);
1299
1300 if (!N) {
1301 N = newSDNode<ConstantFPSDNode>(isTarget, &V, EltVT);
1302 CSEMap.InsertNode(N, IP);
1303 InsertNode(N);
1304 }
1305
1306 SDValue Result(N, 0);
1307 if (VT.isVector())
1308 Result = getSplatBuildVector(VT, DL, Result);
1309 NewSDValueDbgMsg(Result, "Creating fp constant: ", this);
1310 return Result;
1311}
1312
1313SDValue SelectionDAG::getConstantFP(double Val, const SDLoc &DL, EVT VT,
1314 bool isTarget) {
1315 EVT EltVT = VT.getScalarType();
1316 if (EltVT == MVT::f32)
1317 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1318 else if (EltVT == MVT::f64)
1319 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1320 else if (EltVT == MVT::f80 || EltVT == MVT::f128 || EltVT == MVT::ppcf128 ||
1321 EltVT == MVT::f16) {
1322 bool Ignored;
1323 APFloat APF = APFloat(Val);
1324 APF.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1325 &Ignored);
1326 return getConstantFP(APF, DL, VT, isTarget);
1327 } else
1328 llvm_unreachable("Unsupported type in getConstantFP");
1329}
1330
1331SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, const SDLoc &DL,
1332 EVT VT, int64_t Offset, bool isTargetGA,
1333 unsigned char TargetFlags) {
1334 assert((TargetFlags == 0 || isTargetGA) &&
1335 "Cannot set target flags on target-independent globals");
1336
1337 // Truncate (with sign-extension) the offset value to the pointer size.
1338 unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1339 if (BitWidth < 64)
1340 Offset = SignExtend64(Offset, BitWidth);
1341
1342 unsigned Opc;
1343 if (GV->isThreadLocal())
1344 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1345 else
1346 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1347
1348 FoldingSetNodeID ID;
1349 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1350 ID.AddPointer(GV);
1351 ID.AddInteger(Offset);
1352 ID.AddInteger(TargetFlags);
1353 void *IP = nullptr;
1354 if (SDNode *E = FindNodeOrInsertPos(ID, DL, IP))
1355 return SDValue(E, 0);
1356
1357 auto *N = newSDNode<GlobalAddressSDNode>(
1358 Opc, DL.getIROrder(), DL.getDebugLoc(), GV, VT, Offset, TargetFlags);
1359 CSEMap.InsertNode(N, IP);
1360 InsertNode(N);
1361 return SDValue(N, 0);
1362}
1363
1364SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1365 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1366 FoldingSetNodeID ID;
1367 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1368 ID.AddInteger(FI);
1369 void *IP = nullptr;
1370 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1371 return SDValue(E, 0);
1372
1373 auto *N = newSDNode<FrameIndexSDNode>(FI, VT, isTarget);
1374 CSEMap.InsertNode(N, IP);
1375 InsertNode(N);
1376 return SDValue(N, 0);
1377}
1378
1379SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1380 unsigned char TargetFlags) {
1381 assert((TargetFlags == 0 || isTarget) &&
1382 "Cannot set target flags on target-independent jump tables");
1383 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1384 FoldingSetNodeID ID;
1385 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1386 ID.AddInteger(JTI);
1387 ID.AddInteger(TargetFlags);
1388 void *IP = nullptr;
1389 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1390 return SDValue(E, 0);
1391
1392 auto *N = newSDNode<JumpTableSDNode>(JTI, VT, isTarget, TargetFlags);
1393 CSEMap.InsertNode(N, IP);
1394 InsertNode(N);
1395 return SDValue(N, 0);
1396}
1397
1398SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1399 unsigned Alignment, int Offset,
1400 bool isTarget,
1401 unsigned char TargetFlags) {
1402 assert((TargetFlags == 0 || isTarget) &&
1403 "Cannot set target flags on target-independent globals");
1404 if (Alignment == 0)
1405 Alignment = MF->getFunction().optForSize()
1406 ? getDataLayout().getABITypeAlignment(C->getType())
1407 : getDataLayout().getPrefTypeAlignment(C->getType());
1408 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1409 FoldingSetNodeID ID;
1410 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1411 ID.AddInteger(Alignment);
1412 ID.AddInteger(Offset);
1413 ID.AddPointer(C);
1414 ID.AddInteger(TargetFlags);
1415 void *IP = nullptr;
1416 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1417 return SDValue(E, 0);
1418
1419 auto *N = newSDNode<ConstantPoolSDNode>(isTarget, C, VT, Offset, Alignment,
1420 TargetFlags);
1421 CSEMap.InsertNode(N, IP);
1422 InsertNode(N);
1423 return SDValue(N, 0);
1424}
1425
1426SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1427 unsigned Alignment, int Offset,
1428 bool isTarget,
1429 unsigned char TargetFlags) {
1430 assert((TargetFlags == 0 || isTarget) &&
1431 "Cannot set target flags on target-independent globals");
1432 if (Alignment == 0)
1433 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1434 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1435 FoldingSetNodeID ID;
1436 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1437 ID.AddInteger(Alignment);
1438 ID.AddInteger(Offset);
1439 C->addSelectionDAGCSEId(ID);
1440 ID.AddInteger(TargetFlags);
1441 void *IP = nullptr;
1442 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1443 return SDValue(E, 0);
1444
1445 auto *N = newSDNode<ConstantPoolSDNode>(isTarget, C, VT, Offset, Alignment,
1446 TargetFlags);
1447 CSEMap.InsertNode(N, IP);
1448 InsertNode(N);
1449 return SDValue(N, 0);
1450}
1451
1452SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1453 unsigned char TargetFlags) {
1454 FoldingSetNodeID ID;
1455 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1456 ID.AddInteger(Index);
1457 ID.AddInteger(Offset);
1458 ID.AddInteger(TargetFlags);
1459 void *IP = nullptr;
1460 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1461 return SDValue(E, 0);
1462
1463 auto *N = newSDNode<TargetIndexSDNode>(Index, VT, Offset, TargetFlags);
1464 CSEMap.InsertNode(N, IP);
1465 InsertNode(N);
1466 return SDValue(N, 0);
1467}
1468
1469SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1470 FoldingSetNodeID ID;
1471 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1472 ID.AddPointer(MBB);
1473 void *IP = nullptr;
1474 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1475 return SDValue(E, 0);
1476
1477 auto *N = newSDNode<BasicBlockSDNode>(MBB);
1478 CSEMap.InsertNode(N, IP);
1479 InsertNode(N);
1480 return SDValue(N, 0);
1481}
1482
1483SDValue SelectionDAG::getValueType(EVT VT) {
1484 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1485 ValueTypeNodes.size())
1486 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1487
1488 SDNode *&N = VT.isExtended() ?
1489 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1490
1491 if (N) return SDValue(N, 0);
1492 N = newSDNode<VTSDNode>(VT);
1493 InsertNode(N);
1494 return SDValue(N, 0);
1495}
1496
1497SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1498 SDNode *&N = ExternalSymbols[Sym];
1499 if (N) return SDValue(N, 0);
1500 N = newSDNode<ExternalSymbolSDNode>(false, Sym, 0, VT);
1501 InsertNode(N);
1502 return SDValue(N, 0);
1503}
1504
1505SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1506 SDNode *&N = MCSymbols[Sym];
1507 if (N)
1508 return SDValue(N, 0);
1509 N = newSDNode<MCSymbolSDNode>(Sym, VT);
1510 InsertNode(N);
1511 return SDValue(N, 0);
1512}
1513
1514SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1515 unsigned char TargetFlags) {
1516 SDNode *&N =
1517 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1518 TargetFlags)];
1519 if (N) return SDValue(N, 0);
1520 N = newSDNode<ExternalSymbolSDNode>(true, Sym, TargetFlags, VT);
1521 InsertNode(N);
1522 return SDValue(N, 0);
1523}
1524
1525SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1526 if ((unsigned)Cond >= CondCodeNodes.size())
1527 CondCodeNodes.resize(Cond+1);
1528
1529 if (!CondCodeNodes[Cond]) {
1530 auto *N = newSDNode<CondCodeSDNode>(Cond);
1531 CondCodeNodes[Cond] = N;
1532 InsertNode(N);
1533 }
1534
1535 return SDValue(CondCodeNodes[Cond], 0);
1536}
1537
1538/// Swaps the values of N1 and N2. Swaps all indices in the shuffle mask M that
1539/// point at N1 to point at N2 and indices that point at N2 to point at N1.
1540static void commuteShuffle(SDValue &N1, SDValue &N2, MutableArrayRef<int> M) {
1541 std::swap(N1, N2);
1542 ShuffleVectorSDNode::commuteMask(M);
1543}
1544
1545SDValue SelectionDAG::getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1,
1546 SDValue N2, ArrayRef<int> Mask) {
1547 assert(VT.getVectorNumElements() == Mask.size() &&
1548 "Must have the same number of vector elements as mask elements!");
1549 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1550 "Invalid VECTOR_SHUFFLE");
1551
1552 // Canonicalize shuffle undef, undef -> undef
1553 if (N1.isUndef() && N2.isUndef())
1554 return getUNDEF(VT);
1555
1556 // Validate that all indices in Mask are within the range of the elements
1557 // input to the shuffle.
1558 int NElts = Mask.size();
1559 assert(llvm::all_of(Mask,
1560 [&](int M) { return M < (NElts * 2) && M >= -1; }) &&
1561 "Index out of range");
1562
1563 // Copy the mask so we can do any needed cleanup.
1564 SmallVector<int, 8> MaskVec(Mask.begin(), Mask.end());
1565
1566 // Canonicalize shuffle v, v -> v, undef
1567 if (N1 == N2) {
1568 N2 = getUNDEF(VT);
1569 for (int i = 0; i != NElts; ++i)
1570 if (MaskVec[i] >= NElts) MaskVec[i] -= NElts;
1571 }
1572
1573 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1574 if (N1.isUndef())
1575 commuteShuffle(N1, N2, MaskVec);
1576
1577 if (TLI->hasVectorBlend()) {
1578 // If shuffling a splat, try to blend the splat instead. We do this here so
1579 // that even when this arises during lowering we don't have to re-handle it.
1580 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1581 BitVector UndefElements;
1582 SDValue Splat = BV->getSplatValue(&UndefElements);
1583 if (!Splat)
1584 return;
1585
1586 for (int i = 0; i < NElts; ++i) {
1587 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + NElts))
1588 continue;
1589
1590 // If this input comes from undef, mark it as such.
1591 if (UndefElements[MaskVec[i] - Offset]) {
1592 MaskVec[i] = -1;
1593 continue;
1594 }
1595
1596 // If we can blend a non-undef lane, use that instead.
1597 if (!UndefElements[i])
1598 MaskVec[i] = i + Offset;
1599 }
1600 };
1601 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1602 BlendSplat(N1BV, 0);
1603 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1604 BlendSplat(N2BV, NElts);
1605 }
1606
1607 // Canonicalize all index into lhs, -> shuffle lhs, undef
1608 // Canonicalize all index into rhs, -> shuffle rhs, undef
1609 bool AllLHS = true, AllRHS = true;
1610 bool N2Undef = N2.isUndef();
1611 for (int i = 0; i != NElts; ++i) {
1612 if (MaskVec[i] >= NElts) {
1613 if (N2Undef)
1614 MaskVec[i] = -1;
1615 else
1616 AllLHS = false;
1617 } else if (MaskVec[i] >= 0) {
1618 AllRHS = false;
1619 }
1620 }
1621 if (AllLHS && AllRHS)
1622 return getUNDEF(VT);
1623 if (AllLHS && !N2Undef)
1624 N2 = getUNDEF(VT);
1625 if (AllRHS) {
1626 N1 = getUNDEF(VT);
1627 commuteShuffle(N1, N2, MaskVec);
1628 }
1629 // Reset our undef status after accounting for the mask.
1630 N2Undef = N2.isUndef();
1631 // Re-check whether both sides ended up undef.
1632 if (N1.isUndef() && N2Undef)
1633 return getUNDEF(VT);
1634
1635 // If Identity shuffle return that node.
1636 bool Identity = true, AllSame = true;
1637 for (int i = 0; i != NElts; ++i) {
1638 if (MaskVec[i] >= 0 && MaskVec[i] != i) Identity = false;
1639 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1640 }
1641 if (Identity && NElts)
1642 return N1;
1643
1644 // Shuffling a constant splat doesn't change the result.
1645 if (N2Undef) {
1646 SDValue V = N1;
1647
1648 // Look through any bitcasts. We check that these don't change the number
1649 // (and size) of elements and just changes their types.
1650 while (V.getOpcode() == ISD::BITCAST)
1651 V = V->getOperand(0);
1652
1653 // A splat should always show up as a build vector node.
1654 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1655 BitVector UndefElements;
1656 SDValue Splat = BV->getSplatValue(&UndefElements);
1657 // If this is a splat of an undef, shuffling it is also undef.
1658 if (Splat && Splat.isUndef())
1659 return getUNDEF(VT);
1660
1661 bool SameNumElts =
1662 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1663
1664 // We only have a splat which can skip shuffles if there is a splatted
1665 // value and no undef lanes rearranged by the shuffle.
1666 if (Splat && UndefElements.none()) {
1667 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1668 // number of elements match or the value splatted is a zero constant.
1669 if (SameNumElts)
1670 return N1;
1671 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1672 if (C->isNullValue())
1673 return N1;
1674 }
1675
1676 // If the shuffle itself creates a splat, build the vector directly.
1677 if (AllSame && SameNumElts) {
1678 EVT BuildVT = BV->getValueType(0);
1679 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1680 SDValue NewBV = getSplatBuildVector(BuildVT, dl, Splatted);
1681
1682 // We may have jumped through bitcasts, so the type of the
1683 // BUILD_VECTOR may not match the type of the shuffle.
1684 if (BuildVT != VT)
1685 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1686 return NewBV;
1687 }
1688 }
1689 }
1690
1691 FoldingSetNodeID ID;
1692 SDValue Ops[2] = { N1, N2 };
1693 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1694 for (int i = 0; i != NElts; ++i)
1695 ID.AddInteger(MaskVec[i]);
1696
1697 void* IP = nullptr;
1698 if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP))
1699 return SDValue(E, 0);
1700
1701 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1702 // SDNode doesn't have access to it. This memory will be "leaked" when
1703 // the node is deallocated, but recovered when the NodeAllocator is released.
1704 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1705 llvm::copy(MaskVec, MaskAlloc);
1706
1707 auto *N = newSDNode<ShuffleVectorSDNode>(VT, dl.getIROrder(),
1708 dl.getDebugLoc(), MaskAlloc);
1709 createOperands(N, Ops);
1710
1711 CSEMap.InsertNode(N, IP);
1712 InsertNode(N);
1713 SDValue V = SDValue(N, 0);
1714 NewSDValueDbgMsg(V, "Creating new node: ", this);
1715 return V;
1716}
1717
1718SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1719 EVT VT = SV.getValueType(0);
1720 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1721 ShuffleVectorSDNode::commuteMask(MaskVec);
1722
1723 SDValue Op0 = SV.getOperand(0);
1724 SDValue Op1 = SV.getOperand(1);
1725 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, MaskVec);
1726}
1727
1728SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1729 FoldingSetNodeID ID;
1730 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1731 ID.AddInteger(RegNo);
1732 void *IP = nullptr;
1733 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1734 return SDValue(E, 0);
1735
1736 auto *N = newSDNode<RegisterSDNode>(RegNo, VT);
1737 N->SDNodeBits.IsDivergent = TLI->isSDNodeSourceOfDivergence(N, FLI, DA);
1738 CSEMap.InsertNode(N, IP);
1739 InsertNode(N);
1740 return SDValue(N, 0);
1741}
1742
1743SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1744 FoldingSetNodeID ID;
1745 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1746 ID.AddPointer(RegMask);
1747 void *IP = nullptr;
1748 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1749 return SDValue(E, 0);
1750
1751 auto *N = newSDNode<RegisterMaskSDNode>(RegMask);
1752 CSEMap.InsertNode(N, IP);
1753 InsertNode(N);
1754 return SDValue(N, 0);
1755}
1756
1757SDValue SelectionDAG::getEHLabel(const SDLoc &dl, SDValue Root,
1758 MCSymbol *Label) {
1759 return getLabelNode(ISD::EH_LABEL, dl, Root, Label);
1760}
1761
1762SDValue SelectionDAG::getLabelNode(unsigned Opcode, const SDLoc &dl,
1763 SDValue Root, MCSymbol *Label) {
1764 FoldingSetNodeID ID;
1765 SDValue Ops[] = { Root };
1766 AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), Ops);
1767 ID.AddPointer(Label);
1768 void *IP = nullptr;
1769 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1770 return SDValue(E, 0);
1771
1772 auto *N = newSDNode<LabelSDNode>(dl.getIROrder(), dl.getDebugLoc(), Label);
1773 createOperands(N, Ops);
1774
1775 CSEMap.InsertNode(N, IP);
1776 InsertNode(N);
1777 return SDValue(N, 0);
1778}
1779
1780SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1781 int64_t Offset,
1782 bool isTarget,
1783 unsigned char TargetFlags) {
1784 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1785
1786 FoldingSetNodeID ID;
1787 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1788 ID.AddPointer(BA);
1789 ID.AddInteger(Offset);
1790 ID.AddInteger(TargetFlags);
1791 void *IP = nullptr;
1792 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1793 return SDValue(E, 0);
1794
1795 auto *N = newSDNode<BlockAddressSDNode>(Opc, VT, BA, Offset, TargetFlags);
1796 CSEMap.InsertNode(N, IP);
1797 InsertNode(N);
1798 return SDValue(N, 0);
1799}
1800
1801SDValue SelectionDAG::getSrcValue(const Value *V) {
1802 assert((!V || V->getType()->isPointerTy()) &&
1803 "SrcValue is not a pointer?");
1804
1805 FoldingSetNodeID ID;
1806 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1807 ID.AddPointer(V);
1808
1809 void *IP = nullptr;
1810 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1811 return SDValue(E, 0);
1812
1813 auto *N = newSDNode<SrcValueSDNode>(V);
1814 CSEMap.InsertNode(N, IP);
1815 InsertNode(N);
1816 return SDValue(N, 0);
1817}
1818
1819SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1820 FoldingSetNodeID ID;
1821 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1822 ID.AddPointer(MD);
1823
1824 void *IP = nullptr;
1825 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1826 return SDValue(E, 0);
1827
1828 auto *N = newSDNode<MDNodeSDNode>(MD);
1829 CSEMap.InsertNode(N, IP);
1830 InsertNode(N);
1831 return SDValue(N, 0);
1832}
1833
1834SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1835 if (VT == V.getValueType())
1836 return V;
1837
1838 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1839}
1840
1841SDValue SelectionDAG::getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr,
1842 unsigned SrcAS, unsigned DestAS) {
1843 SDValue Ops[] = {Ptr};
1844 FoldingSetNodeID ID;
1845 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1846 ID.AddInteger(SrcAS);
1847 ID.AddInteger(DestAS);
1848
1849 void *IP = nullptr;
1850 if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP))
1851 return SDValue(E, 0);
1852
1853 auto *N = newSDNode<AddrSpaceCastSDNode>(dl.getIROrder(), dl.getDebugLoc(),
1854 VT, SrcAS, DestAS);
1855 createOperands(N, Ops);
1856
1857 CSEMap.InsertNode(N, IP);
1858 InsertNode(N);
1859 return SDValue(N, 0);
1860}
1861
1862/// getShiftAmountOperand - Return the specified value casted to
1863/// the target's desired shift amount type.
1864SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1865 EVT OpTy = Op.getValueType();
1866 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1867 if (OpTy == ShTy || OpTy.isVector()) return Op;
1868
1869 return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
1870}
1871
1872SDValue SelectionDAG::expandVAArg(SDNode *Node) {
1873 SDLoc dl(Node);
1874 const TargetLowering &TLI = getTargetLoweringInfo();
1875 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
1876 EVT VT = Node->getValueType(0);
1877 SDValue Tmp1 = Node->getOperand(0);
1878 SDValue Tmp2 = Node->getOperand(1);
1879 unsigned Align = Node->getConstantOperandVal(3);
1880
1881 SDValue VAListLoad = getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1,
1882 Tmp2, MachinePointerInfo(V));
1883 SDValue VAList = VAListLoad;
1884
1885 if (Align > TLI.getMinStackArgumentAlignment()) {
1886 assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
1887
1888 VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1889 getConstant(Align - 1, dl, VAList.getValueType()));
1890
1891 VAList = getNode(ISD::AND, dl, VAList.getValueType(), VAList,
1892 getConstant(-(int64_t)Align, dl, VAList.getValueType()));
1893 }
1894
1895 // Increment the pointer, VAList, to the next vaarg
1896 Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1897 getConstant(getDataLayout().getTypeAllocSize(
1898 VT.getTypeForEVT(*getContext())),
1899 dl, VAList.getValueType()));
1900 // Store the incremented VAList to the legalized pointer
1901 Tmp1 =
1902 getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2, MachinePointerInfo(V));
1903 // Load the actual argument out of the pointer VAList
1904 return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo());
1905}
1906
1907SDValue SelectionDAG::expandVACopy(SDNode *Node) {
1908 SDLoc dl(Node);
1909 const TargetLowering &TLI = getTargetLoweringInfo();
1910 // This defaults to loading a pointer from the input and storing it to the
1911 // output, returning the chain.
1912 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
1913 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
1914 SDValue Tmp1 =
1915 getLoad(TLI.getPointerTy(getDataLayout()), dl, Node->getOperand(0),
1916 Node->getOperand(2), MachinePointerInfo(VS));
1917 return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
1918 MachinePointerInfo(VD));
1919}
1920
1921SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1922 MachineFrameInfo &MFI = getMachineFunction().getFrameInfo();
1923 unsigned ByteSize = VT.getStoreSize();
1924 Type *Ty = VT.getTypeForEVT(*getContext());
1925 unsigned StackAlign =
1926 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1927
1928 int FrameIdx = MFI.CreateStackObject(ByteSize, StackAlign, false);
1929 return getFrameIndex(FrameIdx, TLI->getFrameIndexTy(getDataLayout()));
1930}
1931
1932SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1933 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1934 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1935 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1936 const DataLayout &DL = getDataLayout();
1937 unsigned Align =
1938 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1939
1940 MachineFrameInfo &MFI = getMachineFunction().getFrameInfo();
1941 int FrameIdx = MFI.CreateStackObject(Bytes, Align, false);
1942 return getFrameIndex(FrameIdx, TLI->getFrameIndexTy(getDataLayout()));
1943}
1944
1945SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1, SDValue N2,
1946 ISD::CondCode Cond, const SDLoc &dl) {
1947 EVT OpVT = N1.getValueType();
1948
1949 // These setcc operations always fold.
1950 switch (Cond) {
1951 default: break;
1952 case ISD::SETFALSE:
1953 case ISD::SETFALSE2: return getBoolConstant(false, dl, VT, OpVT);
1954 case ISD::SETTRUE:
1955 case ISD::SETTRUE2: return getBoolConstant(true, dl, VT, OpVT);
1956
1957 case ISD::SETOEQ:
1958 case ISD::SETOGT:
1959 case ISD::SETOGE:
1960 case ISD::SETOLT:
1961 case ISD::SETOLE:
1962 case ISD::SETONE:
1963 case ISD::SETO:
1964 case ISD::SETUO:
1965 case ISD::SETUEQ:
1966 case ISD::SETUNE:
1967 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1968 break;
1969 }
1970
1971 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1972 const APInt &C2 = N2C->getAPIntValue();
1973 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1974 const APInt &C1 = N1C->getAPIntValue();
1975
1976 switch (Cond) {
1977 default: llvm_unreachable("Unknown integer setcc!");
1978 case ISD::SETEQ: return getBoolConstant(C1 == C2, dl, VT, OpVT);
1979 case ISD::SETNE: return getBoolConstant(C1 != C2, dl, VT, OpVT);
1980 case ISD::SETULT: return getBoolConstant(C1.ult(C2), dl, VT, OpVT);
1981 case ISD::SETUGT: return getBoolConstant(C1.ugt(C2), dl, VT, OpVT);
1982 case ISD::SETULE: return getBoolConstant(C1.ule(C2), dl, VT, OpVT);
1983 case ISD::SETUGE: return getBoolConstant(C1.uge(C2), dl, VT, OpVT);
1984 case ISD::SETLT: return getBoolConstant(C1.slt(C2), dl, VT, OpVT);
1985 case ISD::SETGT: return getBoolConstant(C1.sgt(C2), dl, VT, OpVT);
1986 case ISD::SETLE: return getBoolConstant(C1.sle(C2), dl, VT, OpVT);
1987 case ISD::SETGE: return getBoolConstant(C1.sge(C2), dl, VT, OpVT);
1988 }
1989 }
1990 }
1991 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1992 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1993 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1994 switch (Cond) {
1995 default: break;
1996 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1997 return getUNDEF(VT);
1998 LLVM_FALLTHROUGH;
1999 case ISD::SETOEQ: return getBoolConstant(R==APFloat::cmpEqual, dl, VT,
2000 OpVT);
2001 case ISD::SETNE: if (R==APFloat::cmpUnordered)
2002 return getUNDEF(VT);
2003 LLVM_FALLTHROUGH;
2004 case ISD::SETONE: return getBoolConstant(R==APFloat::cmpGreaterThan ||
2005 R==APFloat::cmpLessThan, dl, VT,
2006 OpVT);
2007 case ISD::SETLT: if (R==APFloat::cmpUnordered)
2008 return getUNDEF(VT);
2009 LLVM_FALLTHROUGH;
2010 case ISD::SETOLT: return getBoolConstant(R==APFloat::cmpLessThan, dl, VT,
2011 OpVT);
2012 case ISD::SETGT: if (R==APFloat::cmpUnordered)
2013 return getUNDEF(VT);
2014 LLVM_FALLTHROUGH;
2015 case ISD::SETOGT: return getBoolConstant(R==APFloat::cmpGreaterThan, dl,
2016 VT, OpVT);
2017 case ISD::SETLE: if (R==APFloat::cmpUnordered)
2018 return getUNDEF(VT);
2019 LLVM_FALLTHROUGH;
2020 case ISD::SETOLE: return getBoolConstant(R==APFloat::cmpLessThan ||
2021 R==APFloat::cmpEqual, dl, VT,
2022 OpVT);
2023 case ISD::SETGE: if (R==APFloat::cmpUnordered)
2024 return getUNDEF(VT);
2025 LLVM_FALLTHROUGH;
2026 case ISD::SETOGE: return getBoolConstant(R==APFloat::cmpGreaterThan ||
2027 R==APFloat::cmpEqual, dl, VT, OpVT);
2028 case ISD::SETO: return getBoolConstant(R!=APFloat::cmpUnordered, dl, VT,
2029 OpVT);
2030 case ISD::SETUO: return getBoolConstant(R==APFloat::cmpUnordered, dl, VT,
2031 OpVT);
2032 case ISD::SETUEQ: return getBoolConstant(R==APFloat::cmpUnordered ||
2033 R==APFloat::cmpEqual, dl, VT,
2034 OpVT);
2035 case ISD::SETUNE: return getBoolConstant(R!=APFloat::cmpEqual, dl, VT,
2036 OpVT);
2037 case ISD::SETULT: return getBoolConstant(R==APFloat::cmpUnordered ||
2038 R==APFloat::cmpLessThan, dl, VT,
2039 OpVT);
2040 case ISD::SETUGT: return getBoolConstant(R==APFloat::cmpGreaterThan ||
2041 R==APFloat::cmpUnordered, dl, VT,
2042 OpVT);
2043 case ISD::SETULE: return getBoolConstant(R!=APFloat::cmpGreaterThan, dl,
2044 VT, OpVT);
2045 case ISD::SETUGE: return getBoolConstant(R!=APFloat::cmpLessThan, dl, VT,
2046 OpVT);
2047 }
2048 } else {
2049 // Ensure that the constant occurs on the RHS.
2050 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
2051 MVT CompVT = N1.getValueType().getSimpleVT();
2052 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
2053 return SDValue();
2054
2055 return getSetCC(dl, VT, N2, N1, SwappedCond);
2056 }
2057 }
2058
2059 // Could not fold it.
2060 return SDValue();
2061}
2062
2063/// See if the specified operand can be simplified with the knowledge that only
2064/// the bits specified by Mask are used.
2065SDValue SelectionDAG::GetDemandedBits(SDValue V, const APInt &Mask) {
2066 switch (V.getOpcode()) {
2067 default:
2068 break;
2069 case ISD::Constant: {
2070 const ConstantSDNode *CV = cast<ConstantSDNode>(V.getNode());
2071 assert(CV && "Const value should be ConstSDNode.");
2072 const APInt &CVal = CV->getAPIntValue();
2073 APInt NewVal = CVal & Mask;
2074 if (NewVal != CVal)
2075 return getConstant(NewVal, SDLoc(V), V.getValueType());
2076 break;
2077 }
2078 case ISD::OR:
2079 case ISD::XOR:
2080 // If the LHS or RHS don't contribute bits to the or, drop them.
2081 if (MaskedValueIsZero(V.getOperand(0), Mask))
2082 return V.getOperand(1);
2083 if (MaskedValueIsZero(V.getOperand(1), Mask))
2084 return V.getOperand(0);