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