LLVM 19.0.0git
SelectionDAG.cpp
Go to the documentation of this file.
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
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/DenseSet.h"
21#include "llvm/ADT/FoldingSet.h"
22#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/Twine.h"
50#include "llvm/IR/Constant.h"
52#include "llvm/IR/Constants.h"
53#include "llvm/IR/DataLayout.h"
55#include "llvm/IR/DebugLoc.h"
57#include "llvm/IR/Function.h"
58#include "llvm/IR/GlobalValue.h"
59#include "llvm/IR/Metadata.h"
60#include "llvm/IR/Type.h"
64#include "llvm/Support/Debug.h"
68#include "llvm/Support/Mutex.h"
74#include <algorithm>
75#include <cassert>
76#include <cstdint>
77#include <cstdlib>
78#include <limits>
79#include <set>
80#include <string>
81#include <utility>
82#include <vector>
83
84using namespace llvm;
85using namespace llvm::SDPatternMatch;
86
87/// makeVTList - Return an instance of the SDVTList struct initialized with the
88/// specified members.
89static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
90 SDVTList Res = {VTs, NumVTs};
91 return Res;
92}
93
94// Default null implementations of the callbacks.
98
99void SelectionDAG::DAGNodeDeletedListener::anchor() {}
100void SelectionDAG::DAGNodeInsertedListener::anchor() {}
101
102#define DEBUG_TYPE "selectiondag"
103
104static cl::opt<bool> EnableMemCpyDAGOpt("enable-memcpy-dag-opt",
105 cl::Hidden, cl::init(true),
106 cl::desc("Gang up loads and stores generated by inlining of memcpy"));
107
108static cl::opt<int> MaxLdStGlue("ldstmemcpy-glue-max",
109 cl::desc("Number limit for gluing ld/st of memcpy."),
110 cl::Hidden, cl::init(0));
111
113 LLVM_DEBUG(dbgs() << Msg; V.getNode()->dump(G););
114}
115
116//===----------------------------------------------------------------------===//
117// ConstantFPSDNode Class
118//===----------------------------------------------------------------------===//
119
120/// isExactlyValue - We don't rely on operator== working on double values, as
121/// it returns true for things that are clearly not equal, like -0.0 and 0.0.
122/// As such, this method can be used to do an exact bit-for-bit comparison of
123/// two floating point values.
125 return getValueAPF().bitwiseIsEqual(V);
126}
127
129 const APFloat& Val) {
130 assert(VT.isFloatingPoint() && "Can only convert between FP types");
131
132 // convert modifies in place, so make a copy.
133 APFloat Val2 = APFloat(Val);
134 bool losesInfo;
137 &losesInfo);
138 return !losesInfo;
139}
140
141//===----------------------------------------------------------------------===//
142// ISD Namespace
143//===----------------------------------------------------------------------===//
144
145bool ISD::isConstantSplatVector(const SDNode *N, APInt &SplatVal) {
146 if (N->getOpcode() == ISD::SPLAT_VECTOR) {
147 unsigned EltSize =
148 N->getValueType(0).getVectorElementType().getSizeInBits();
149 if (auto *Op0 = dyn_cast<ConstantSDNode>(N->getOperand(0))) {
150 SplatVal = Op0->getAPIntValue().trunc(EltSize);
151 return true;
152 }
153 if (auto *Op0 = dyn_cast<ConstantFPSDNode>(N->getOperand(0))) {
154 SplatVal = Op0->getValueAPF().bitcastToAPInt().trunc(EltSize);
155 return true;
156 }
157 }
158
159 auto *BV = dyn_cast<BuildVectorSDNode>(N);
160 if (!BV)
161 return false;
162
163 APInt SplatUndef;
164 unsigned SplatBitSize;
165 bool HasUndefs;
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 // Endianness does not matter here. We are checking for a splat given the
168 // element size of the vector, and if we find such a splat for little endian
169 // layout, then that should be valid also for big endian (as the full vector
170 // size is known to be a multiple of the element size).
171 const bool IsBigEndian = false;
172 return BV->isConstantSplat(SplatVal, SplatUndef, SplatBitSize, HasUndefs,
173 EltSize, IsBigEndian) &&
174 EltSize == SplatBitSize;
175}
176
177// FIXME: AllOnes and AllZeros duplicate a lot of code. Could these be
178// specializations of the more general isConstantSplatVector()?
179
180bool ISD::isConstantSplatVectorAllOnes(const SDNode *N, bool BuildVectorOnly) {
181 // Look through a bit convert.
182 while (N->getOpcode() == ISD::BITCAST)
183 N = N->getOperand(0).getNode();
184
185 if (!BuildVectorOnly && N->getOpcode() == ISD::SPLAT_VECTOR) {
186 APInt SplatVal;
187 return isConstantSplatVector(N, SplatVal) && SplatVal.isAllOnes();
188 }
189
190 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
191
192 unsigned i = 0, e = N->getNumOperands();
193
194 // Skip over all of the undef values.
195 while (i != e && N->getOperand(i).isUndef())
196 ++i;
197
198 // Do not accept an all-undef vector.
199 if (i == e) return false;
200
201 // Do not accept build_vectors that aren't all constants or which have non-~0
202 // elements. We have to be a bit careful here, as the type of the constant
203 // may not be the same as the type of the vector elements due to type
204 // legalization (the elements are promoted to a legal type for the target and
205 // a vector of a type may be legal when the base element type is not).
206 // We only want to check enough bits to cover the vector elements, because
207 // we care if the resultant vector is all ones, not whether the individual
208 // constants are.
209 SDValue NotZero = N->getOperand(i);
210 unsigned EltSize = N->getValueType(0).getScalarSizeInBits();
211 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
212 if (CN->getAPIntValue().countr_one() < EltSize)
213 return false;
214 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
215 if (CFPN->getValueAPF().bitcastToAPInt().countr_one() < EltSize)
216 return false;
217 } else
218 return false;
219
220 // Okay, we have at least one ~0 value, check to see if the rest match or are
221 // undefs. Even with the above element type twiddling, this should be OK, as
222 // the same type legalization should have applied to all the elements.
223 for (++i; i != e; ++i)
224 if (N->getOperand(i) != NotZero && !N->getOperand(i).isUndef())
225 return false;
226 return true;
227}
228
229bool ISD::isConstantSplatVectorAllZeros(const SDNode *N, bool BuildVectorOnly) {
230 // Look through a bit convert.
231 while (N->getOpcode() == ISD::BITCAST)
232 N = N->getOperand(0).getNode();
233
234 if (!BuildVectorOnly && N->getOpcode() == ISD::SPLAT_VECTOR) {
235 APInt SplatVal;
236 return isConstantSplatVector(N, SplatVal) && SplatVal.isZero();
237 }
238
239 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
240
241 bool IsAllUndef = true;
242 for (const SDValue &Op : N->op_values()) {
243 if (Op.isUndef())
244 continue;
245 IsAllUndef = false;
246 // Do not accept build_vectors that aren't all constants or which have non-0
247 // elements. We have to be a bit careful here, as the type of the constant
248 // may not be the same as the type of the vector elements due to type
249 // legalization (the elements are promoted to a legal type for the target
250 // and a vector of a type may be legal when the base element type is not).
251 // We only want to check enough bits to cover the vector elements, because
252 // we care if the resultant vector is all zeros, not whether the individual
253 // constants are.
254 unsigned EltSize = N->getValueType(0).getScalarSizeInBits();
255 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
256 if (CN->getAPIntValue().countr_zero() < EltSize)
257 return false;
258 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Op)) {
259 if (CFPN->getValueAPF().bitcastToAPInt().countr_zero() < EltSize)
260 return false;
261 } else
262 return false;
263 }
264
265 // Do not accept an all-undef vector.
266 if (IsAllUndef)
267 return false;
268 return true;
269}
270
272 return isConstantSplatVectorAllOnes(N, /*BuildVectorOnly*/ true);
273}
274
276 return isConstantSplatVectorAllZeros(N, /*BuildVectorOnly*/ true);
277}
278
280 if (N->getOpcode() != ISD::BUILD_VECTOR)
281 return false;
282
283 for (const SDValue &Op : N->op_values()) {
284 if (Op.isUndef())
285 continue;
286 if (!isa<ConstantSDNode>(Op))
287 return false;
288 }
289 return true;
290}
291
293 if (N->getOpcode() != ISD::BUILD_VECTOR)
294 return false;
295
296 for (const SDValue &Op : N->op_values()) {
297 if (Op.isUndef())
298 continue;
299 if (!isa<ConstantFPSDNode>(Op))
300 return false;
301 }
302 return true;
303}
304
305bool ISD::isVectorShrinkable(const SDNode *N, unsigned NewEltSize,
306 bool Signed) {
307 assert(N->getValueType(0).isVector() && "Expected a vector!");
308
309 unsigned EltSize = N->getValueType(0).getScalarSizeInBits();
310 if (EltSize <= NewEltSize)
311 return false;
312
313 if (N->getOpcode() == ISD::ZERO_EXTEND) {
314 return (N->getOperand(0).getValueType().getScalarSizeInBits() <=
315 NewEltSize) &&
316 !Signed;
317 }
318 if (N->getOpcode() == ISD::SIGN_EXTEND) {
319 return (N->getOperand(0).getValueType().getScalarSizeInBits() <=
320 NewEltSize) &&
321 Signed;
322 }
323 if (N->getOpcode() != ISD::BUILD_VECTOR)
324 return false;
325
326 for (const SDValue &Op : N->op_values()) {
327 if (Op.isUndef())
328 continue;
329 if (!isa<ConstantSDNode>(Op))
330 return false;
331
332 APInt C = Op->getAsAPIntVal().trunc(EltSize);
333 if (Signed && C.trunc(NewEltSize).sext(EltSize) != C)
334 return false;
335 if (!Signed && C.trunc(NewEltSize).zext(EltSize) != C)
336 return false;
337 }
338
339 return true;
340}
341
343 // Return false if the node has no operands.
344 // This is "logically inconsistent" with the definition of "all" but
345 // is probably the desired behavior.
346 if (N->getNumOperands() == 0)
347 return false;
348 return all_of(N->op_values(), [](SDValue Op) { return Op.isUndef(); });
349}
350
352 return N->getOpcode() == ISD::FREEZE && N->getOperand(0).isUndef();
353}
354
355template <typename ConstNodeType>
357 std::function<bool(ConstNodeType *)> Match,
358 bool AllowUndefs) {
359 // FIXME: Add support for scalar UNDEF cases?
360 if (auto *C = dyn_cast<ConstNodeType>(Op))
361 return Match(C);
362
363 // FIXME: Add support for vector UNDEF cases?
364 if (ISD::BUILD_VECTOR != Op.getOpcode() &&
365 ISD::SPLAT_VECTOR != Op.getOpcode())
366 return false;
367
368 EVT SVT = Op.getValueType().getScalarType();
369 for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
370 if (AllowUndefs && Op.getOperand(i).isUndef()) {
371 if (!Match(nullptr))
372 return false;
373 continue;
374 }
375
376 auto *Cst = dyn_cast<ConstNodeType>(Op.getOperand(i));
377 if (!Cst || Cst->getValueType(0) != SVT || !Match(Cst))
378 return false;
379 }
380 return true;
381}
382// Build used template types.
383template bool ISD::matchUnaryPredicateImpl<ConstantSDNode>(
384 SDValue, std::function<bool(ConstantSDNode *)>, bool);
385template bool ISD::matchUnaryPredicateImpl<ConstantFPSDNode>(
386 SDValue, std::function<bool(ConstantFPSDNode *)>, bool);
387
389 SDValue LHS, SDValue RHS,
390 std::function<bool(ConstantSDNode *, ConstantSDNode *)> Match,
391 bool AllowUndefs, bool AllowTypeMismatch) {
392 if (!AllowTypeMismatch && LHS.getValueType() != RHS.getValueType())
393 return false;
394
395 // TODO: Add support for scalar UNDEF cases?
396 if (auto *LHSCst = dyn_cast<ConstantSDNode>(LHS))
397 if (auto *RHSCst = dyn_cast<ConstantSDNode>(RHS))
398 return Match(LHSCst, RHSCst);
399
400 // TODO: Add support for vector UNDEF cases?
401 if (LHS.getOpcode() != RHS.getOpcode() ||
402 (LHS.getOpcode() != ISD::BUILD_VECTOR &&
403 LHS.getOpcode() != ISD::SPLAT_VECTOR))
404 return false;
405
406 EVT SVT = LHS.getValueType().getScalarType();
407 for (unsigned i = 0, e = LHS.getNumOperands(); i != e; ++i) {
408 SDValue LHSOp = LHS.getOperand(i);
409 SDValue RHSOp = RHS.getOperand(i);
410 bool LHSUndef = AllowUndefs && LHSOp.isUndef();
411 bool RHSUndef = AllowUndefs && RHSOp.isUndef();
412 auto *LHSCst = dyn_cast<ConstantSDNode>(LHSOp);
413 auto *RHSCst = dyn_cast<ConstantSDNode>(RHSOp);
414 if ((!LHSCst && !LHSUndef) || (!RHSCst && !RHSUndef))
415 return false;
416 if (!AllowTypeMismatch && (LHSOp.getValueType() != SVT ||
417 LHSOp.getValueType() != RHSOp.getValueType()))
418 return false;
419 if (!Match(LHSCst, RHSCst))
420 return false;
421 }
422 return true;
423}
424
426 switch (VecReduceOpcode) {
427 default:
428 llvm_unreachable("Expected VECREDUCE opcode");
431 case ISD::VP_REDUCE_FADD:
432 case ISD::VP_REDUCE_SEQ_FADD:
433 return ISD::FADD;
436 case ISD::VP_REDUCE_FMUL:
437 case ISD::VP_REDUCE_SEQ_FMUL:
438 return ISD::FMUL;
440 case ISD::VP_REDUCE_ADD:
441 return ISD::ADD;
443 case ISD::VP_REDUCE_MUL:
444 return ISD::MUL;
446 case ISD::VP_REDUCE_AND:
447 return ISD::AND;
449 case ISD::VP_REDUCE_OR:
450 return ISD::OR;
452 case ISD::VP_REDUCE_XOR:
453 return ISD::XOR;
455 case ISD::VP_REDUCE_SMAX:
456 return ISD::SMAX;
458 case ISD::VP_REDUCE_SMIN:
459 return ISD::SMIN;
461 case ISD::VP_REDUCE_UMAX:
462 return ISD::UMAX;
464 case ISD::VP_REDUCE_UMIN:
465 return ISD::UMIN;
467 case ISD::VP_REDUCE_FMAX:
468 return ISD::FMAXNUM;
470 case ISD::VP_REDUCE_FMIN:
471 return ISD::FMINNUM;
473 case ISD::VP_REDUCE_FMAXIMUM:
474 return ISD::FMAXIMUM;
476 case ISD::VP_REDUCE_FMINIMUM:
477 return ISD::FMINIMUM;
478 }
479}
480
481bool ISD::isVPOpcode(unsigned Opcode) {
482 switch (Opcode) {
483 default:
484 return false;
485#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) \
486 case ISD::VPSD: \
487 return true;
488#include "llvm/IR/VPIntrinsics.def"
489 }
490}
491
492bool ISD::isVPBinaryOp(unsigned Opcode) {
493 switch (Opcode) {
494 default:
495 break;
496#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) case ISD::VPSD:
497#define VP_PROPERTY_BINARYOP return true;
498#define END_REGISTER_VP_SDNODE(VPSD) break;
499#include "llvm/IR/VPIntrinsics.def"
500 }
501 return false;
502}
503
504bool ISD::isVPReduction(unsigned Opcode) {
505 switch (Opcode) {
506 default:
507 break;
508#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) case ISD::VPSD:
509#define VP_PROPERTY_REDUCTION(STARTPOS, ...) return true;
510#define END_REGISTER_VP_SDNODE(VPSD) break;
511#include "llvm/IR/VPIntrinsics.def"
512 }
513 return false;
514}
515
516/// The operand position of the vector mask.
517std::optional<unsigned> ISD::getVPMaskIdx(unsigned Opcode) {
518 switch (Opcode) {
519 default:
520 return std::nullopt;
521#define BEGIN_REGISTER_VP_SDNODE(VPSD, LEGALPOS, TDNAME, MASKPOS, ...) \
522 case ISD::VPSD: \
523 return MASKPOS;
524#include "llvm/IR/VPIntrinsics.def"
525 }
526}
527
528/// The operand position of the explicit vector length parameter.
529std::optional<unsigned> ISD::getVPExplicitVectorLengthIdx(unsigned Opcode) {
530 switch (Opcode) {
531 default:
532 return std::nullopt;
533#define BEGIN_REGISTER_VP_SDNODE(VPSD, LEGALPOS, TDNAME, MASKPOS, EVLPOS) \
534 case ISD::VPSD: \
535 return EVLPOS;
536#include "llvm/IR/VPIntrinsics.def"
537 }
538}
539
540std::optional<unsigned> ISD::getBaseOpcodeForVP(unsigned VPOpcode,
541 bool hasFPExcept) {
542 // FIXME: Return strict opcodes in case of fp exceptions.
543 switch (VPOpcode) {
544 default:
545 return std::nullopt;
546#define BEGIN_REGISTER_VP_SDNODE(VPOPC, ...) case ISD::VPOPC:
547#define VP_PROPERTY_FUNCTIONAL_SDOPC(SDOPC) return ISD::SDOPC;
548#define END_REGISTER_VP_SDNODE(VPOPC) break;
549#include "llvm/IR/VPIntrinsics.def"
550 }
551 return std::nullopt;
552}
553
554unsigned ISD::getVPForBaseOpcode(unsigned Opcode) {
555 switch (Opcode) {
556 default:
557 llvm_unreachable("can not translate this Opcode to VP.");
558#define BEGIN_REGISTER_VP_SDNODE(VPOPC, ...) break;
559#define VP_PROPERTY_FUNCTIONAL_SDOPC(SDOPC) case ISD::SDOPC:
560#define END_REGISTER_VP_SDNODE(VPOPC) return ISD::VPOPC;
561#include "llvm/IR/VPIntrinsics.def"
562 }
563}
564
566 switch (ExtType) {
567 case ISD::EXTLOAD:
568 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
569 case ISD::SEXTLOAD:
570 return ISD::SIGN_EXTEND;
571 case ISD::ZEXTLOAD:
572 return ISD::ZERO_EXTEND;
573 default:
574 break;
575 }
576
577 llvm_unreachable("Invalid LoadExtType");
578}
579
581 // To perform this operation, we just need to swap the L and G bits of the
582 // operation.
583 unsigned OldL = (Operation >> 2) & 1;
584 unsigned OldG = (Operation >> 1) & 1;
585 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
586 (OldL << 1) | // New G bit
587 (OldG << 2)); // New L bit.
588}
589
591 unsigned Operation = Op;
592 if (isIntegerLike)
593 Operation ^= 7; // Flip L, G, E bits, but not U.
594 else
595 Operation ^= 15; // Flip all of the condition bits.
596
598 Operation &= ~8; // Don't let N and U bits get set.
599
600 return ISD::CondCode(Operation);
601}
602
604 return getSetCCInverseImpl(Op, Type.isInteger());
605}
606
608 bool isIntegerLike) {
609 return getSetCCInverseImpl(Op, isIntegerLike);
610}
611
612/// For an integer comparison, return 1 if the comparison is a signed operation
613/// and 2 if the result is an unsigned comparison. Return zero if the operation
614/// does not depend on the sign of the input (setne and seteq).
615static int isSignedOp(ISD::CondCode Opcode) {
616 switch (Opcode) {
617 default: llvm_unreachable("Illegal integer setcc operation!");
618 case ISD::SETEQ:
619 case ISD::SETNE: return 0;
620 case ISD::SETLT:
621 case ISD::SETLE:
622 case ISD::SETGT:
623 case ISD::SETGE: return 1;
624 case ISD::SETULT:
625 case ISD::SETULE:
626 case ISD::SETUGT:
627 case ISD::SETUGE: return 2;
628 }
629}
630
632 EVT Type) {
633 bool IsInteger = Type.isInteger();
634 if (IsInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
635 // Cannot fold a signed integer setcc with an unsigned integer setcc.
636 return ISD::SETCC_INVALID;
637
638 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
639
640 // If the N and U bits get set, then the resultant comparison DOES suddenly
641 // care about orderedness, and it is true when ordered.
642 if (Op > ISD::SETTRUE2)
643 Op &= ~16; // Clear the U bit if the N bit is set.
644
645 // Canonicalize illegal integer setcc's.
646 if (IsInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
647 Op = ISD::SETNE;
648
649 return ISD::CondCode(Op);
650}
651
653 EVT Type) {
654 bool IsInteger = Type.isInteger();
655 if (IsInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
656 // Cannot fold a signed setcc with an unsigned setcc.
657 return ISD::SETCC_INVALID;
658
659 // Combine all of the condition bits.
660 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
661
662 // Canonicalize illegal integer setcc's.
663 if (IsInteger) {
664 switch (Result) {
665 default: break;
666 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
667 case ISD::SETOEQ: // SETEQ & SETU[LG]E
668 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
669 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
670 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
671 }
672 }
673
674 return Result;
675}
676
677//===----------------------------------------------------------------------===//
678// SDNode Profile Support
679//===----------------------------------------------------------------------===//
680
681/// AddNodeIDOpcode - Add the node opcode to the NodeID data.
682static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
683 ID.AddInteger(OpC);
684}
685
686/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
687/// solely with their pointer.
689 ID.AddPointer(VTList.VTs);
690}
691
692/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
694 ArrayRef<SDValue> Ops) {
695 for (const auto &Op : Ops) {
696 ID.AddPointer(Op.getNode());
697 ID.AddInteger(Op.getResNo());
698 }
699}
700
701/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
703 ArrayRef<SDUse> Ops) {
704 for (const auto &Op : Ops) {
705 ID.AddPointer(Op.getNode());
706 ID.AddInteger(Op.getResNo());
707 }
708}
709
710static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned OpC,
711 SDVTList VTList, ArrayRef<SDValue> OpList) {
712 AddNodeIDOpcode(ID, OpC);
713 AddNodeIDValueTypes(ID, VTList);
714 AddNodeIDOperands(ID, OpList);
715}
716
717/// If this is an SDNode with special info, add this info to the NodeID data.
719 switch (N->getOpcode()) {
722 case ISD::MCSymbol:
723 llvm_unreachable("Should only be used on nodes with operands");
724 default: break; // Normal nodes don't need extra info.
726 case ISD::Constant: {
727 const ConstantSDNode *C = cast<ConstantSDNode>(N);
728 ID.AddPointer(C->getConstantIntValue());
729 ID.AddBoolean(C->isOpaque());
730 break;
731 }
733 case ISD::ConstantFP:
734 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
735 break;
740 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
741 ID.AddPointer(GA->getGlobal());
742 ID.AddInteger(GA->getOffset());
743 ID.AddInteger(GA->getTargetFlags());
744 break;
745 }
746 case ISD::BasicBlock:
747 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
748 break;
749 case ISD::Register:
750 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
751 break;
753 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
754 break;
755 case ISD::SRCVALUE:
756 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
757 break;
758 case ISD::FrameIndex:
760 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
761 break;
764 if (cast<LifetimeSDNode>(N)->hasOffset()) {
765 ID.AddInteger(cast<LifetimeSDNode>(N)->getSize());
766 ID.AddInteger(cast<LifetimeSDNode>(N)->getOffset());
767 }
768 break;
770 ID.AddInteger(cast<PseudoProbeSDNode>(N)->getGuid());
771 ID.AddInteger(cast<PseudoProbeSDNode>(N)->getIndex());
772 ID.AddInteger(cast<PseudoProbeSDNode>(N)->getAttributes());
773 break;
774 case ISD::JumpTable:
776 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
777 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
778 break;
781 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
782 ID.AddInteger(CP->getAlign().value());
783 ID.AddInteger(CP->getOffset());
784 if (CP->isMachineConstantPoolEntry())
785 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
786 else
787 ID.AddPointer(CP->getConstVal());
788 ID.AddInteger(CP->getTargetFlags());
789 break;
790 }
791 case ISD::TargetIndex: {
792 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
793 ID.AddInteger(TI->getIndex());
794 ID.AddInteger(TI->getOffset());
795 ID.AddInteger(TI->getTargetFlags());
796 break;
797 }
798 case ISD::LOAD: {
799 const LoadSDNode *LD = cast<LoadSDNode>(N);
800 ID.AddInteger(LD->getMemoryVT().getRawBits());
801 ID.AddInteger(LD->getRawSubclassData());
802 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
803 ID.AddInteger(LD->getMemOperand()->getFlags());
804 break;
805 }
806 case ISD::STORE: {
807 const StoreSDNode *ST = cast<StoreSDNode>(N);
808 ID.AddInteger(ST->getMemoryVT().getRawBits());
809 ID.AddInteger(ST->getRawSubclassData());
810 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
811 ID.AddInteger(ST->getMemOperand()->getFlags());
812 break;
813 }
814 case ISD::VP_LOAD: {
815 const VPLoadSDNode *ELD = cast<VPLoadSDNode>(N);
816 ID.AddInteger(ELD->getMemoryVT().getRawBits());
817 ID.AddInteger(ELD->getRawSubclassData());
818 ID.AddInteger(ELD->getPointerInfo().getAddrSpace());
819 ID.AddInteger(ELD->getMemOperand()->getFlags());
820 break;
821 }
822 case ISD::VP_STORE: {
823 const VPStoreSDNode *EST = cast<VPStoreSDNode>(N);
824 ID.AddInteger(EST->getMemoryVT().getRawBits());
825 ID.AddInteger(EST->getRawSubclassData());
826 ID.AddInteger(EST->getPointerInfo().getAddrSpace());
827 ID.AddInteger(EST->getMemOperand()->getFlags());
828 break;
829 }
830 case ISD::EXPERIMENTAL_VP_STRIDED_LOAD: {
831 const VPStridedLoadSDNode *SLD = cast<VPStridedLoadSDNode>(N);
832 ID.AddInteger(SLD->getMemoryVT().getRawBits());
833 ID.AddInteger(SLD->getRawSubclassData());
834 ID.AddInteger(SLD->getPointerInfo().getAddrSpace());
835 break;
836 }
837 case ISD::EXPERIMENTAL_VP_STRIDED_STORE: {
838 const VPStridedStoreSDNode *SST = cast<VPStridedStoreSDNode>(N);
839 ID.AddInteger(SST->getMemoryVT().getRawBits());
840 ID.AddInteger(SST->getRawSubclassData());
841 ID.AddInteger(SST->getPointerInfo().getAddrSpace());
842 break;
843 }
844 case ISD::VP_GATHER: {
845 const VPGatherSDNode *EG = cast<VPGatherSDNode>(N);
846 ID.AddInteger(EG->getMemoryVT().getRawBits());
847 ID.AddInteger(EG->getRawSubclassData());
848 ID.AddInteger(EG->getPointerInfo().getAddrSpace());
849 ID.AddInteger(EG->getMemOperand()->getFlags());
850 break;
851 }
852 case ISD::VP_SCATTER: {
853 const VPScatterSDNode *ES = cast<VPScatterSDNode>(N);
854 ID.AddInteger(ES->getMemoryVT().getRawBits());
855 ID.AddInteger(ES->getRawSubclassData());
856 ID.AddInteger(ES->getPointerInfo().getAddrSpace());
857 ID.AddInteger(ES->getMemOperand()->getFlags());
858 break;
859 }
860 case ISD::MLOAD: {
861 const MaskedLoadSDNode *MLD = cast<MaskedLoadSDNode>(N);
862 ID.AddInteger(MLD->getMemoryVT().getRawBits());
863 ID.AddInteger(MLD->getRawSubclassData());
864 ID.AddInteger(MLD->getPointerInfo().getAddrSpace());
865 ID.AddInteger(MLD->getMemOperand()->getFlags());
866 break;
867 }
868 case ISD::MSTORE: {
869 const MaskedStoreSDNode *MST = cast<MaskedStoreSDNode>(N);
870 ID.AddInteger(MST->getMemoryVT().getRawBits());
871 ID.AddInteger(MST->getRawSubclassData());
872 ID.AddInteger(MST->getPointerInfo().getAddrSpace());
873 ID.AddInteger(MST->getMemOperand()->getFlags());
874 break;
875 }
876 case ISD::MGATHER: {
877 const MaskedGatherSDNode *MG = cast<MaskedGatherSDNode>(N);
878 ID.AddInteger(MG->getMemoryVT().getRawBits());
879 ID.AddInteger(MG->getRawSubclassData());
880 ID.AddInteger(MG->getPointerInfo().getAddrSpace());
881 ID.AddInteger(MG->getMemOperand()->getFlags());
882 break;
883 }
884 case ISD::MSCATTER: {
885 const MaskedScatterSDNode *MS = cast<MaskedScatterSDNode>(N);
886 ID.AddInteger(MS->getMemoryVT().getRawBits());
887 ID.AddInteger(MS->getRawSubclassData());
888 ID.AddInteger(MS->getPointerInfo().getAddrSpace());
889 ID.AddInteger(MS->getMemOperand()->getFlags());
890 break;
891 }
894 case ISD::ATOMIC_SWAP:
906 case ISD::ATOMIC_LOAD:
907 case ISD::ATOMIC_STORE: {
908 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
909 ID.AddInteger(AT->getMemoryVT().getRawBits());
910 ID.AddInteger(AT->getRawSubclassData());
911 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
912 ID.AddInteger(AT->getMemOperand()->getFlags());
913 break;
914 }
915 case ISD::VECTOR_SHUFFLE: {
916 ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(N)->getMask();
917 for (int M : Mask)
918 ID.AddInteger(M);
919 break;
920 }
922 case ISD::BlockAddress: {
923 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
924 ID.AddPointer(BA->getBlockAddress());
925 ID.AddInteger(BA->getOffset());
926 ID.AddInteger(BA->getTargetFlags());
927 break;
928 }
929 case ISD::AssertAlign:
930 ID.AddInteger(cast<AssertAlignSDNode>(N)->getAlign().value());
931 break;
932 case ISD::PREFETCH:
935 // Handled by MemIntrinsicSDNode check after the switch.
936 break;
937 } // end switch (N->getOpcode())
938
939 // MemIntrinsic nodes could also have subclass data, address spaces, and flags
940 // to check.
941 if (auto *MN = dyn_cast<MemIntrinsicSDNode>(N)) {
942 ID.AddInteger(MN->getRawSubclassData());
943 ID.AddInteger(MN->getPointerInfo().getAddrSpace());
944 ID.AddInteger(MN->getMemOperand()->getFlags());
945 ID.AddInteger(MN->getMemoryVT().getRawBits());
946 }
947}
948
949/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
950/// data.
951static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
952 AddNodeIDOpcode(ID, N->getOpcode());
953 // Add the return value info.
954 AddNodeIDValueTypes(ID, N->getVTList());
955 // Add the operand info.
956 AddNodeIDOperands(ID, N->ops());
957
958 // Handle SDNode leafs with special info.
960}
961
962//===----------------------------------------------------------------------===//
963// SelectionDAG Class
964//===----------------------------------------------------------------------===//
965
966/// doNotCSE - Return true if CSE should not be performed for this node.
967static bool doNotCSE(SDNode *N) {
968 if (N->getValueType(0) == MVT::Glue)
969 return true; // Never CSE anything that produces a glue result.
970
971 switch (N->getOpcode()) {
972 default: break;
973 case ISD::HANDLENODE:
974 case ISD::EH_LABEL:
975 return true; // Never CSE these nodes.
976 }
977
978 // Check that remaining values produced are not flags.
979 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
980 if (N->getValueType(i) == MVT::Glue)
981 return true; // Never CSE anything that produces a glue result.
982
983 return false;
984}
985
986/// RemoveDeadNodes - This method deletes all unreachable nodes in the
987/// SelectionDAG.
989 // Create a dummy node (which is not added to allnodes), that adds a reference
990 // to the root node, preventing it from being deleted.
991 HandleSDNode Dummy(getRoot());
992
994
995 // Add all obviously-dead nodes to the DeadNodes worklist.
996 for (SDNode &Node : allnodes())
997 if (Node.use_empty())
998 DeadNodes.push_back(&Node);
999
1000 RemoveDeadNodes(DeadNodes);
1001
1002 // If the root changed (e.g. it was a dead load, update the root).
1003 setRoot(Dummy.getValue());
1004}
1005
1006/// RemoveDeadNodes - This method deletes the unreachable nodes in the
1007/// given list, and any nodes that become unreachable as a result.
1009
1010 // Process the worklist, deleting the nodes and adding their uses to the
1011 // worklist.
1012 while (!DeadNodes.empty()) {
1013 SDNode *N = DeadNodes.pop_back_val();
1014 // Skip to next node if we've already managed to delete the node. This could
1015 // happen if replacing a node causes a node previously added to the node to
1016 // be deleted.
1017 if (N->getOpcode() == ISD::DELETED_NODE)
1018 continue;
1019
1020 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1021 DUL->NodeDeleted(N, nullptr);
1022
1023 // Take the node out of the appropriate CSE map.
1024 RemoveNodeFromCSEMaps(N);
1025
1026 // Next, brutally remove the operand list. This is safe to do, as there are
1027 // no cycles in the graph.
1028 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
1029 SDUse &Use = *I++;
1030 SDNode *Operand = Use.getNode();
1031 Use.set(SDValue());
1032
1033 // Now that we removed this operand, see if there are no uses of it left.
1034 if (Operand->use_empty())
1035 DeadNodes.push_back(Operand);
1036 }
1037
1038 DeallocateNode(N);
1039 }
1040}
1041
1043 SmallVector<SDNode*, 16> DeadNodes(1, N);
1044
1045 // Create a dummy node that adds a reference to the root node, preventing
1046 // it from being deleted. (This matters if the root is an operand of the
1047 // dead node.)
1048 HandleSDNode Dummy(getRoot());
1049
1050 RemoveDeadNodes(DeadNodes);
1051}
1052
1054 // First take this out of the appropriate CSE map.
1055 RemoveNodeFromCSEMaps(N);
1056
1057 // Finally, remove uses due to operands of this node, remove from the
1058 // AllNodes list, and delete the node.
1059 DeleteNodeNotInCSEMaps(N);
1060}
1061
1062void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
1063 assert(N->getIterator() != AllNodes.begin() &&
1064 "Cannot delete the entry node!");
1065 assert(N->use_empty() && "Cannot delete a node that is not dead!");
1066
1067 // Drop all of the operands and decrement used node's use counts.
1068 N->DropOperands();
1069
1070 DeallocateNode(N);
1071}
1072
1073void SDDbgInfo::add(SDDbgValue *V, bool isParameter) {
1074 assert(!(V->isVariadic() && isParameter));
1075 if (isParameter)
1076 ByvalParmDbgValues.push_back(V);
1077 else
1078 DbgValues.push_back(V);
1079 for (const SDNode *Node : V->getSDNodes())
1080 if (Node)
1081 DbgValMap[Node].push_back(V);
1082}
1083
1084void SDDbgInfo::erase(const SDNode *Node) {
1085 DbgValMapType::iterator I = DbgValMap.find(Node);
1086 if (I == DbgValMap.end())
1087 return;
1088 for (auto &Val: I->second)
1089 Val->setIsInvalidated();
1090 DbgValMap.erase(I);
1091}
1092
1093void SelectionDAG::DeallocateNode(SDNode *N) {
1094 // If we have operands, deallocate them.
1095 removeOperands(N);
1096
1097 NodeAllocator.Deallocate(AllNodes.remove(N));
1098
1099 // Set the opcode to DELETED_NODE to help catch bugs when node
1100 // memory is reallocated.
1101 // FIXME: There are places in SDag that have grown a dependency on the opcode
1102 // value in the released node.
1103 __asan_unpoison_memory_region(&N->NodeType, sizeof(N->NodeType));
1104 N->NodeType = ISD::DELETED_NODE;
1105
1106 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
1107 // them and forget about that node.
1108 DbgInfo->erase(N);
1109
1110 // Invalidate extra info.
1111 SDEI.erase(N);
1112}
1113
1114#ifndef NDEBUG
1115/// VerifySDNode - Check the given SDNode. Aborts if it is invalid.
1116static void VerifySDNode(SDNode *N, const TargetLowering *TLI) {
1117 switch (N->getOpcode()) {
1118 default:
1119 if (N->getOpcode() > ISD::BUILTIN_OP_END)
1120 TLI->verifyTargetSDNode(N);
1121 break;
1122 case ISD::BUILD_PAIR: {
1123 EVT VT = N->getValueType(0);
1124 assert(N->getNumValues() == 1 && "Too many results!");
1125 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
1126 "Wrong return type!");
1127 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
1128 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
1129 "Mismatched operand types!");
1130 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
1131 "Wrong operand type!");
1132 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
1133 "Wrong return type size");
1134 break;
1135 }
1136 case ISD::BUILD_VECTOR: {
1137 assert(N->getNumValues() == 1 && "Too many results!");
1138 assert(N->getValueType(0).isVector() && "Wrong return type!");
1139 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
1140 "Wrong number of operands!");
1141 EVT EltVT = N->getValueType(0).getVectorElementType();
1142 for (const SDUse &Op : N->ops()) {
1143 assert((Op.getValueType() == EltVT ||
1144 (EltVT.isInteger() && Op.getValueType().isInteger() &&
1145 EltVT.bitsLE(Op.getValueType()))) &&
1146 "Wrong operand type!");
1147 assert(Op.getValueType() == N->getOperand(0).getValueType() &&
1148 "Operands must all have the same type");
1149 }
1150 break;
1151 }
1152 }
1153}
1154#endif // NDEBUG
1155
1156/// Insert a newly allocated node into the DAG.
1157///
1158/// Handles insertion into the all nodes list and CSE map, as well as
1159/// verification and other common operations when a new node is allocated.
1160void SelectionDAG::InsertNode(SDNode *N) {
1161 AllNodes.push_back(N);
1162#ifndef NDEBUG
1163 N->PersistentId = NextPersistentId++;
1164 VerifySDNode(N, TLI);
1165#endif
1166 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1167 DUL->NodeInserted(N);
1168}
1169
1170/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
1171/// correspond to it. This is useful when we're about to delete or repurpose
1172/// the node. We don't want future request for structurally identical nodes
1173/// to return N anymore.
1174bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
1175 bool Erased = false;
1176 switch (N->getOpcode()) {
1177 case ISD::HANDLENODE: return false; // noop.
1178 case ISD::CONDCODE:
1179 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
1180 "Cond code doesn't exist!");
1181 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
1182 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
1183 break;
1185 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
1186 break;
1188 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
1189 Erased = TargetExternalSymbols.erase(std::pair<std::string, unsigned>(
1190 ESN->getSymbol(), ESN->getTargetFlags()));
1191 break;
1192 }
1193 case ISD::MCSymbol: {
1194 auto *MCSN = cast<MCSymbolSDNode>(N);
1195 Erased = MCSymbols.erase(MCSN->getMCSymbol());
1196 break;
1197 }
1198 case ISD::VALUETYPE: {
1199 EVT VT = cast<VTSDNode>(N)->getVT();
1200 if (VT.isExtended()) {
1201 Erased = ExtendedValueTypeNodes.erase(VT);
1202 } else {
1203 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
1204 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
1205 }
1206 break;
1207 }
1208 default:
1209 // Remove it from the CSE Map.
1210 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
1211 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
1212 Erased = CSEMap.RemoveNode(N);
1213 break;
1214 }
1215#ifndef NDEBUG
1216 // Verify that the node was actually in one of the CSE maps, unless it has a
1217 // glue result (which cannot be CSE'd) or is one of the special cases that are
1218 // not subject to CSE.
1219 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
1220 !N->isMachineOpcode() && !doNotCSE(N)) {
1221 N->dump(this);
1222 dbgs() << "\n";
1223 llvm_unreachable("Node is not in map!");
1224 }
1225#endif
1226 return Erased;
1227}
1228
1229/// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
1230/// maps and modified in place. Add it back to the CSE maps, unless an identical
1231/// node already exists, in which case transfer all its users to the existing
1232/// node. This transfer can potentially trigger recursive merging.
1233void
1234SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
1235 // For node types that aren't CSE'd, just act as if no identical node
1236 // already exists.
1237 if (!doNotCSE(N)) {
1238 SDNode *Existing = CSEMap.GetOrInsertNode(N);
1239 if (Existing != N) {
1240 // If there was already an existing matching node, use ReplaceAllUsesWith
1241 // to replace the dead one with the existing one. This can cause
1242 // recursive merging of other unrelated nodes down the line.
1243 ReplaceAllUsesWith(N, Existing);
1244
1245 // N is now dead. Inform the listeners and delete it.
1246 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1247 DUL->NodeDeleted(N, Existing);
1248 DeleteNodeNotInCSEMaps(N);
1249 return;
1250 }
1251 }
1252
1253 // If the node doesn't already exist, we updated it. Inform listeners.
1254 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1255 DUL->NodeUpdated(N);
1256}
1257
1258/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
1259/// were replaced with those specified. If this node is never memoized,
1260/// return null, otherwise return a pointer to the slot it would take. If a
1261/// node already exists with these operands, the slot will be non-null.
1262SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
1263 void *&InsertPos) {
1264 if (doNotCSE(N))
1265 return nullptr;
1266
1267 SDValue Ops[] = { Op };
1269 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
1271 SDNode *Node = FindNodeOrInsertPos(ID, SDLoc(N), InsertPos);
1272 if (Node)
1273 Node->intersectFlagsWith(N->getFlags());
1274 return Node;
1275}
1276
1277/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
1278/// were replaced with those specified. If this node is never memoized,
1279/// return null, otherwise return a pointer to the slot it would take. If a
1280/// node already exists with these operands, the slot will be non-null.
1281SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
1282 SDValue Op1, SDValue Op2,
1283 void *&InsertPos) {
1284 if (doNotCSE(N))
1285 return nullptr;
1286
1287 SDValue Ops[] = { Op1, Op2 };
1289 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
1291 SDNode *Node = FindNodeOrInsertPos(ID, SDLoc(N), InsertPos);
1292 if (Node)
1293 Node->intersectFlagsWith(N->getFlags());
1294 return Node;
1295}
1296
1297/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
1298/// were replaced with those specified. If this node is never memoized,
1299/// return null, otherwise return a pointer to the slot it would take. If a
1300/// node already exists with these operands, the slot will be non-null.
1301SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1302 void *&InsertPos) {
1303 if (doNotCSE(N))
1304 return nullptr;
1305
1307 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
1309 SDNode *Node = FindNodeOrInsertPos(ID, SDLoc(N), InsertPos);
1310 if (Node)
1311 Node->intersectFlagsWith(N->getFlags());
1312 return Node;
1313}
1314
1316 Type *Ty = VT == MVT::iPTR ? PointerType::get(*getContext(), 0)
1317 : VT.getTypeForEVT(*getContext());
1318
1319 return getDataLayout().getABITypeAlign(Ty);
1320}
1321
1322// EntryNode could meaningfully have debug info if we can find it...
1324 : TM(tm), OptLevel(OL), EntryNode(ISD::EntryToken, 0, DebugLoc(),
1325 getVTList(MVT::Other, MVT::Glue)),
1326 Root(getEntryNode()) {
1327 InsertNode(&EntryNode);
1328 DbgInfo = new SDDbgInfo();
1329}
1330
1332 OptimizationRemarkEmitter &NewORE, Pass *PassPtr,
1333 const TargetLibraryInfo *LibraryInfo,
1334 UniformityInfo *NewUA, ProfileSummaryInfo *PSIin,
1335 BlockFrequencyInfo *BFIin,
1336 FunctionVarLocs const *VarLocs) {
1337 MF = &NewMF;
1338 SDAGISelPass = PassPtr;
1339 ORE = &NewORE;
1342 LibInfo = LibraryInfo;
1343 Context = &MF->getFunction().getContext();
1344 UA = NewUA;
1345 PSI = PSIin;
1346 BFI = BFIin;
1347 FnVarLocs = VarLocs;
1348}
1349
1351 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
1352 allnodes_clear();
1353 OperandRecycler.clear(OperandAllocator);
1354 delete DbgInfo;
1355}
1356
1358 return MF->getFunction().hasOptSize() ||
1360}
1361
1362void SelectionDAG::allnodes_clear() {
1363 assert(&*AllNodes.begin() == &EntryNode);
1364 AllNodes.remove(AllNodes.begin());
1365 while (!AllNodes.empty())
1366 DeallocateNode(&AllNodes.front());
1367#ifndef NDEBUG
1368 NextPersistentId = 0;
1369#endif
1370}
1371
1372SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
1373 void *&InsertPos) {
1374 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
1375 if (N) {
1376 switch (N->getOpcode()) {
1377 default: break;
1378 case ISD::Constant:
1379 case ISD::ConstantFP:
1380 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
1381 "debug location. Use another overload.");
1382 }
1383 }
1384 return N;
1385}
1386
1387SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
1388 const SDLoc &DL, void *&InsertPos) {
1389 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
1390 if (N) {
1391 switch (N->getOpcode()) {
1392 case ISD::Constant:
1393 case ISD::ConstantFP:
1394 // Erase debug location from the node if the node is used at several
1395 // different places. Do not propagate one location to all uses as it
1396 // will cause a worse single stepping debugging experience.
1397 if (N->getDebugLoc() != DL.getDebugLoc())
1398 N->setDebugLoc(DebugLoc());
1399 break;
1400 default:
1401 // When the node's point of use is located earlier in the instruction
1402 // sequence than its prior point of use, update its debug info to the
1403 // earlier location.
1404 if (DL.getIROrder() && DL.getIROrder() < N->getIROrder())
1405 N->setDebugLoc(DL.getDebugLoc());
1406 break;
1407 }
1408 }
1409 return N;
1410}
1411
1413 allnodes_clear();
1414 OperandRecycler.clear(OperandAllocator);
1415 OperandAllocator.Reset();
1416 CSEMap.clear();
1417
1418 ExtendedValueTypeNodes.clear();
1419 ExternalSymbols.clear();
1420 TargetExternalSymbols.clear();
1421 MCSymbols.clear();
1422 SDEI.clear();
1423 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(), nullptr);
1424 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(), nullptr);
1425
1426 EntryNode.UseList = nullptr;
1427 InsertNode(&EntryNode);
1428 Root = getEntryNode();
1429 DbgInfo->clear();
1430}
1431
1433 return VT.bitsGT(Op.getValueType())
1434 ? getNode(ISD::FP_EXTEND, DL, VT, Op)
1435 : getNode(ISD::FP_ROUND, DL, VT, Op,
1436 getIntPtrConstant(0, DL, /*isTarget=*/true));
1437}
1438
1439std::pair<SDValue, SDValue>
1441 const SDLoc &DL, EVT VT) {
1442 assert(!VT.bitsEq(Op.getValueType()) &&
1443 "Strict no-op FP extend/round not allowed.");
1444 SDValue Res =
1445 VT.bitsGT(Op.getValueType())
1446 ? getNode(ISD::STRICT_FP_EXTEND, DL, {VT, MVT::Other}, {Chain, Op})
1447 : getNode(ISD::STRICT_FP_ROUND, DL, {VT, MVT::Other},
1448 {Chain, Op, getIntPtrConstant(0, DL)});
1449
1450 return std::pair<SDValue, SDValue>(Res, SDValue(Res.getNode(), 1));
1451}
1452
1454 return VT.bitsGT(Op.getValueType()) ?
1455 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1456 getNode(ISD::TRUNCATE, DL, VT, Op);
1457}
1458
1460 return VT.bitsGT(Op.getValueType()) ?
1461 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1462 getNode(ISD::TRUNCATE, DL, VT, Op);
1463}
1464
1466 return VT.bitsGT(Op.getValueType()) ?
1467 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1468 getNode(ISD::TRUNCATE, DL, VT, Op);
1469}
1470
1472 EVT VT) {
1473 assert(!VT.isVector());
1474 auto Type = Op.getValueType();
1475 SDValue DestOp;
1476 if (Type == VT)
1477 return Op;
1478 auto Size = Op.getValueSizeInBits();
1479 DestOp = getBitcast(MVT::getIntegerVT(Size), Op);
1480 if (DestOp.getValueType() == VT)
1481 return DestOp;
1482
1483 return getAnyExtOrTrunc(DestOp, DL, VT);
1484}
1485
1487 EVT VT) {
1488 assert(!VT.isVector());
1489 auto Type = Op.getValueType();
1490 SDValue DestOp;
1491 if (Type == VT)
1492 return Op;
1493 auto Size = Op.getValueSizeInBits();
1494 DestOp = getBitcast(MVT::getIntegerVT(Size), Op);
1495 if (DestOp.getValueType() == VT)
1496 return DestOp;
1497
1498 return getSExtOrTrunc(DestOp, DL, VT);
1499}
1500
1502 EVT VT) {
1503 assert(!VT.isVector());
1504 auto Type = Op.getValueType();
1505 SDValue DestOp;
1506 if (Type == VT)
1507 return Op;
1508 auto Size = Op.getValueSizeInBits();
1509 DestOp = getBitcast(MVT::getIntegerVT(Size), Op);
1510 if (DestOp.getValueType() == VT)
1511 return DestOp;
1512
1513 return getZExtOrTrunc(DestOp, DL, VT);
1514}
1515
1517 EVT OpVT) {
1518 if (VT.bitsLE(Op.getValueType()))
1519 return getNode(ISD::TRUNCATE, SL, VT, Op);
1520
1522 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1523}
1524
1526 EVT OpVT = Op.getValueType();
1527 assert(VT.isInteger() && OpVT.isInteger() &&
1528 "Cannot getZeroExtendInReg FP types");
1529 assert(VT.isVector() == OpVT.isVector() &&
1530 "getZeroExtendInReg type should be vector iff the operand "
1531 "type is vector!");
1532 assert((!VT.isVector() ||
1534 "Vector element counts must match in getZeroExtendInReg");
1535 assert(VT.bitsLE(OpVT) && "Not extending!");
1536 if (OpVT == VT)
1537 return Op;
1539 VT.getScalarSizeInBits());
1540 return getNode(ISD::AND, DL, OpVT, Op, getConstant(Imm, DL, OpVT));
1541}
1542
1544 // Only unsigned pointer semantics are supported right now. In the future this
1545 // might delegate to TLI to check pointer signedness.
1546 return getZExtOrTrunc(Op, DL, VT);
1547}
1548
1550 // Only unsigned pointer semantics are supported right now. In the future this
1551 // might delegate to TLI to check pointer signedness.
1552 return getZeroExtendInReg(Op, DL, VT);
1553}
1554
1556 return getNode(ISD::SUB, DL, VT, getConstant(0, DL, VT), Val);
1557}
1558
1559/// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1561 return getNode(ISD::XOR, DL, VT, Val, getAllOnesConstant(DL, VT));
1562}
1563
1565 SDValue TrueValue = getBoolConstant(true, DL, VT, VT);
1566 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1567}
1568
1570 SDValue Mask, SDValue EVL, EVT VT) {
1571 SDValue TrueValue = getBoolConstant(true, DL, VT, VT);
1572 return getNode(ISD::VP_XOR, DL, VT, Val, TrueValue, Mask, EVL);
1573}
1574
1576 SDValue Mask, SDValue EVL) {
1577 return getVPZExtOrTrunc(DL, VT, Op, Mask, EVL);
1578}
1579
1581 SDValue Mask, SDValue EVL) {
1582 if (VT.bitsGT(Op.getValueType()))
1583 return getNode(ISD::VP_ZERO_EXTEND, DL, VT, Op, Mask, EVL);
1584 if (VT.bitsLT(Op.getValueType()))
1585 return getNode(ISD::VP_TRUNCATE, DL, VT, Op, Mask, EVL);
1586 return Op;
1587}
1588
1590 EVT OpVT) {
1591 if (!V)
1592 return getConstant(0, DL, VT);
1593
1594 switch (TLI->getBooleanContents(OpVT)) {
1597 return getConstant(1, DL, VT);
1599 return getAllOnesConstant(DL, VT);
1600 }
1601 llvm_unreachable("Unexpected boolean content enum!");
1602}
1603
1605 bool isT, bool isO) {
1606 EVT EltVT = VT.getScalarType();
1607 assert((EltVT.getSizeInBits() >= 64 ||
1608 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1609 "getConstant with a uint64_t value that doesn't fit in the type!");
1610 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1611}
1612
1614 bool isT, bool isO) {
1615 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1616}
1617
1619 EVT VT, bool isT, bool isO) {
1620 assert(VT.isInteger() && "Cannot create FP integer constant!");
1621
1622 EVT EltVT = VT.getScalarType();
1623 const ConstantInt *Elt = &Val;
1624
1625 // In some cases the vector type is legal but the element type is illegal and
1626 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1627 // inserted value (the type does not need to match the vector element type).
1628 // Any extra bits introduced will be truncated away.
1629 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1631 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1632 APInt NewVal;
1633 if (TLI->isSExtCheaperThanZExt(VT.getScalarType(), EltVT))
1634 NewVal = Elt->getValue().sextOrTrunc(EltVT.getSizeInBits());
1635 else
1636 NewVal = Elt->getValue().zextOrTrunc(EltVT.getSizeInBits());
1637 Elt = ConstantInt::get(*getContext(), NewVal);
1638 }
1639 // In other cases the element type is illegal and needs to be expanded, for
1640 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1641 // the value into n parts and use a vector type with n-times the elements.
1642 // Then bitcast to the type requested.
1643 // Legalizing constants too early makes the DAGCombiner's job harder so we
1644 // only legalize if the DAG tells us we must produce legal types.
1645 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1646 TLI->getTypeAction(*getContext(), EltVT) ==
1648 const APInt &NewVal = Elt->getValue();
1649 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1650 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1651
1652 // For scalable vectors, try to use a SPLAT_VECTOR_PARTS node.
1653 if (VT.isScalableVector() ||
1655 assert(EltVT.getSizeInBits() % ViaEltSizeInBits == 0 &&
1656 "Can only handle an even split!");
1657 unsigned Parts = EltVT.getSizeInBits() / ViaEltSizeInBits;
1658
1659 SmallVector<SDValue, 2> ScalarParts;
1660 for (unsigned i = 0; i != Parts; ++i)
1661 ScalarParts.push_back(getConstant(
1662 NewVal.extractBits(ViaEltSizeInBits, i * ViaEltSizeInBits), DL,
1663 ViaEltVT, isT, isO));
1664
1665 return getNode(ISD::SPLAT_VECTOR_PARTS, DL, VT, ScalarParts);
1666 }
1667
1668 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1669 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1670
1671 // Check the temporary vector is the correct size. If this fails then
1672 // getTypeToTransformTo() probably returned a type whose size (in bits)
1673 // isn't a power-of-2 factor of the requested type size.
1674 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1675
1676 SmallVector<SDValue, 2> EltParts;
1677 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i)
1678 EltParts.push_back(getConstant(
1679 NewVal.extractBits(ViaEltSizeInBits, i * ViaEltSizeInBits), DL,
1680 ViaEltVT, isT, isO));
1681
1682 // EltParts is currently in little endian order. If we actually want
1683 // big-endian order then reverse it now.
1684 if (getDataLayout().isBigEndian())
1685 std::reverse(EltParts.begin(), EltParts.end());
1686
1687 // The elements must be reversed when the element order is different
1688 // to the endianness of the elements (because the BITCAST is itself a
1689 // vector shuffle in this situation). However, we do not need any code to
1690 // perform this reversal because getConstant() is producing a vector
1691 // splat.
1692 // This situation occurs in MIPS MSA.
1693
1695 for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i)
1696 llvm::append_range(Ops, EltParts);
1697
1698 SDValue V =
1699 getNode(ISD::BITCAST, DL, VT, getBuildVector(ViaVecVT, DL, Ops));
1700 return V;
1701 }
1702
1703 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1704 "APInt size does not match type size!");
1705 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1706 SDVTList VTs = getVTList(EltVT);
1708 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
1709 ID.AddPointer(Elt);
1710 ID.AddBoolean(isO);
1711 void *IP = nullptr;
1712 SDNode *N = nullptr;
1713 if ((N = FindNodeOrInsertPos(ID, DL, IP)))
1714 if (!VT.isVector())
1715 return SDValue(N, 0);
1716
1717 if (!N) {
1718 N = newSDNode<ConstantSDNode>(isT, isO, Elt, VTs);
1719 CSEMap.InsertNode(N, IP);
1720 InsertNode(N);
1721 NewSDValueDbgMsg(SDValue(N, 0), "Creating constant: ", this);
1722 }
1723
1724 SDValue Result(N, 0);
1725 if (VT.isVector())
1726 Result = getSplat(VT, DL, Result);
1727 return Result;
1728}
1729
1731 bool isTarget) {
1732 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1733}
1734
1736 const SDLoc &DL, bool LegalTypes) {
1737 assert(VT.isInteger() && "Shift amount is not an integer type!");
1738 EVT ShiftVT = TLI->getShiftAmountTy(VT, getDataLayout(), LegalTypes);
1739 return getConstant(Val, DL, ShiftVT);
1740}
1741
1743 const SDLoc &DL, bool LegalTypes) {
1744 assert(Val.ult(VT.getScalarSizeInBits()) && "Out of range shift");
1745 return getShiftAmountConstant(Val.getZExtValue(), VT, DL, LegalTypes);
1746}
1747
1749 bool isTarget) {
1750 return getConstant(Val, DL, TLI->getVectorIdxTy(getDataLayout()), isTarget);
1751}
1752
1754 bool isTarget) {
1755 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1756}
1757
1759 EVT VT, bool isTarget) {
1760 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1761
1762 EVT EltVT = VT.getScalarType();
1763
1764 // Do the map lookup using the actual bit pattern for the floating point
1765 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1766 // we don't have issues with SNANs.
1767 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1768 SDVTList VTs = getVTList(EltVT);
1770 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
1771 ID.AddPointer(&V);
1772 void *IP = nullptr;
1773 SDNode *N = nullptr;
1774 if ((N = FindNodeOrInsertPos(ID, DL, IP)))
1775 if (!VT.isVector())
1776 return SDValue(N, 0);
1777
1778 if (!N) {
1779 N = newSDNode<ConstantFPSDNode>(isTarget, &V, VTs);
1780 CSEMap.InsertNode(N, IP);
1781 InsertNode(N);
1782 }
1783
1784 SDValue Result(N, 0);
1785 if (VT.isVector())
1786 Result = getSplat(VT, DL, Result);
1787 NewSDValueDbgMsg(Result, "Creating fp constant: ", this);
1788 return Result;
1789}
1790
1792 bool isTarget) {
1793 EVT EltVT = VT.getScalarType();
1794 if (EltVT == MVT::f32)
1795 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1796 if (EltVT == MVT::f64)
1797 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1798 if (EltVT == MVT::f80 || EltVT == MVT::f128 || EltVT == MVT::ppcf128 ||
1799 EltVT == MVT::f16 || EltVT == MVT::bf16) {
1800 bool Ignored;
1801 APFloat APF = APFloat(Val);
1803 &Ignored);
1804 return getConstantFP(APF, DL, VT, isTarget);
1805 }
1806 llvm_unreachable("Unsupported type in getConstantFP");
1807}
1808
1810 EVT VT, int64_t Offset, bool isTargetGA,
1811 unsigned TargetFlags) {
1812 assert((TargetFlags == 0 || isTargetGA) &&
1813 "Cannot set target flags on target-independent globals");
1814
1815 // Truncate (with sign-extension) the offset value to the pointer size.
1817 if (BitWidth < 64)
1819
1820 unsigned Opc;
1821 if (GV->isThreadLocal())
1823 else
1824 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1825
1826 SDVTList VTs = getVTList(VT);
1828 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
1829 ID.AddPointer(GV);
1830 ID.AddInteger(Offset);
1831 ID.AddInteger(TargetFlags);
1832 void *IP = nullptr;
1833 if (SDNode *E = FindNodeOrInsertPos(ID, DL, IP))
1834 return SDValue(E, 0);
1835
1836 auto *N = newSDNode<GlobalAddressSDNode>(
1837 Opc, DL.getIROrder(), DL.getDebugLoc(), GV, VTs, Offset, TargetFlags);
1838 CSEMap.InsertNode(N, IP);
1839 InsertNode(N);
1840 return SDValue(N, 0);
1841}
1842
1843SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1844 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1845 SDVTList VTs = getVTList(VT);
1847 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
1848 ID.AddInteger(FI);
1849 void *IP = nullptr;
1850 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1851 return SDValue(E, 0);
1852
1853 auto *N = newSDNode<FrameIndexSDNode>(FI, VTs, isTarget);
1854 CSEMap.InsertNode(N, IP);
1855 InsertNode(N);
1856 return SDValue(N, 0);
1857}
1858
1859SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1860 unsigned TargetFlags) {
1861 assert((TargetFlags == 0 || isTarget) &&
1862 "Cannot set target flags on target-independent jump tables");
1863 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1864 SDVTList VTs = getVTList(VT);
1866 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
1867 ID.AddInteger(JTI);
1868 ID.AddInteger(TargetFlags);
1869 void *IP = nullptr;
1870 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1871 return SDValue(E, 0);
1872
1873 auto *N = newSDNode<JumpTableSDNode>(JTI, VTs, isTarget, TargetFlags);
1874 CSEMap.InsertNode(N, IP);
1875 InsertNode(N);
1876 return SDValue(N, 0);
1877}
1878
1880 const SDLoc &DL) {
1882 return getNode(ISD::JUMP_TABLE_DEBUG_INFO, DL, MVT::Glue, Chain,
1883 getTargetConstant(static_cast<uint64_t>(JTI), DL, PTy, true));
1884}
1885
1887 MaybeAlign Alignment, int Offset,
1888 bool isTarget, unsigned TargetFlags) {
1889 assert((TargetFlags == 0 || isTarget) &&
1890 "Cannot set target flags on target-independent globals");
1891 if (!Alignment)
1892 Alignment = shouldOptForSize()
1893 ? getDataLayout().getABITypeAlign(C->getType())
1894 : getDataLayout().getPrefTypeAlign(C->getType());
1895 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1896 SDVTList VTs = getVTList(VT);
1898 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
1899 ID.AddInteger(Alignment->value());
1900 ID.AddInteger(Offset);
1901 ID.AddPointer(C);
1902 ID.AddInteger(TargetFlags);
1903 void *IP = nullptr;
1904 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1905 return SDValue(E, 0);
1906
1907 auto *N = newSDNode<ConstantPoolSDNode>(isTarget, C, VTs, Offset, *Alignment,
1908 TargetFlags);
1909 CSEMap.InsertNode(N, IP);
1910 InsertNode(N);
1911 SDValue V = SDValue(N, 0);
1912 NewSDValueDbgMsg(V, "Creating new constant pool: ", this);
1913 return V;
1914}
1915
1917 MaybeAlign Alignment, int Offset,
1918 bool isTarget, unsigned TargetFlags) {
1919 assert((TargetFlags == 0 || isTarget) &&
1920 "Cannot set target flags on target-independent globals");
1921 if (!Alignment)
1922 Alignment = getDataLayout().getPrefTypeAlign(C->getType());
1923 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1924 SDVTList VTs = getVTList(VT);
1926 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
1927 ID.AddInteger(Alignment->value());
1928 ID.AddInteger(Offset);
1929 C->addSelectionDAGCSEId(ID);
1930 ID.AddInteger(TargetFlags);
1931 void *IP = nullptr;
1932 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1933 return SDValue(E, 0);
1934
1935 auto *N = newSDNode<ConstantPoolSDNode>(isTarget, C, VTs, Offset, *Alignment,
1936 TargetFlags);
1937 CSEMap.InsertNode(N, IP);
1938 InsertNode(N);
1939 return SDValue(N, 0);
1940}
1941
1944 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), std::nullopt);
1945 ID.AddPointer(MBB);
1946 void *IP = nullptr;
1947 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1948 return SDValue(E, 0);
1949
1950 auto *N = newSDNode<BasicBlockSDNode>(MBB);
1951 CSEMap.InsertNode(N, IP);
1952 InsertNode(N);
1953 return SDValue(N, 0);
1954}
1955
1957 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1958 ValueTypeNodes.size())
1959 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1960
1961 SDNode *&N = VT.isExtended() ?
1962 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1963
1964 if (N) return SDValue(N, 0);
1965 N = newSDNode<VTSDNode>(VT);
1966 InsertNode(N);
1967 return SDValue(N, 0);
1968}
1969
1971 SDNode *&N = ExternalSymbols[Sym];
1972 if (N) return SDValue(N, 0);
1973 N = newSDNode<ExternalSymbolSDNode>(false, Sym, 0, getVTList(VT));
1974 InsertNode(N);
1975 return SDValue(N, 0);
1976}
1977
1979 SDNode *&N = MCSymbols[Sym];
1980 if (N)
1981 return SDValue(N, 0);
1982 N = newSDNode<MCSymbolSDNode>(Sym, getVTList(VT));
1983 InsertNode(N);
1984 return SDValue(N, 0);
1985}
1986
1988 unsigned TargetFlags) {
1989 SDNode *&N =
1990 TargetExternalSymbols[std::pair<std::string, unsigned>(Sym, TargetFlags)];
1991 if (N) return SDValue(N, 0);
1992 N = newSDNode<ExternalSymbolSDNode>(true, Sym, TargetFlags, getVTList(VT));
1993 InsertNode(N);
1994 return SDValue(N, 0);
1995}
1996
1998 if ((unsigned)Cond >= CondCodeNodes.size())
1999 CondCodeNodes.resize(Cond+1);
2000
2001 if (!CondCodeNodes[Cond]) {
2002 auto *N = newSDNode<CondCodeSDNode>(Cond);
2003 CondCodeNodes[Cond] = N;
2004 InsertNode(N);
2005 }
2006
2007 return SDValue(CondCodeNodes[Cond], 0);
2008}
2009
2011 bool ConstantFold) {
2012 assert(MulImm.getBitWidth() == VT.getSizeInBits() &&
2013 "APInt size does not match type size!");
2014
2015 if (MulImm == 0)
2016 return getConstant(0, DL, VT);
2017
2018 if (ConstantFold) {
2019 const MachineFunction &MF = getMachineFunction();
2020 const Function &F = MF.getFunction();
2021 ConstantRange CR = getVScaleRange(&F, 64);
2022 if (const APInt *C = CR.getSingleElement())
2023 return getConstant(MulImm * C->getZExtValue(), DL, VT);
2024 }
2025
2026 return getNode(ISD::VSCALE, DL, VT, getConstant(MulImm, DL, VT));
2027}
2028
2030 bool ConstantFold) {
2031 if (EC.isScalable())
2032 return getVScale(DL, VT,
2033 APInt(VT.getSizeInBits(), EC.getKnownMinValue()));
2034
2035 return getConstant(EC.getKnownMinValue(), DL, VT);
2036}
2037
2039 APInt One(ResVT.getScalarSizeInBits(), 1);
2040 return getStepVector(DL, ResVT, One);
2041}
2042
2044 const APInt &StepVal) {
2045 assert(ResVT.getScalarSizeInBits() == StepVal.getBitWidth());
2046 if (ResVT.isScalableVector())
2047 return getNode(
2048 ISD::STEP_VECTOR, DL, ResVT,
2049 getTargetConstant(StepVal, DL, ResVT.getVectorElementType()));
2050
2051 SmallVector<SDValue, 16> OpsStepConstants;
2052 for (uint64_t i = 0; i < ResVT.getVectorNumElements(); i++)
2053 OpsStepConstants.push_back(
2054 getConstant(StepVal * i, DL, ResVT.getVectorElementType()));
2055 return getBuildVector(ResVT, DL, OpsStepConstants);
2056}
2057
2058/// Swaps the values of N1 and N2. Swaps all indices in the shuffle mask M that
2059/// point at N1 to point at N2 and indices that point at N2 to point at N1.
2061 std::swap(N1, N2);
2063}
2064
2066 SDValue N2, ArrayRef<int> Mask) {
2067 assert(VT.getVectorNumElements() == Mask.size() &&
2068 "Must have the same number of vector elements as mask elements!");
2069 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
2070 "Invalid VECTOR_SHUFFLE");
2071
2072 // Canonicalize shuffle undef, undef -> undef
2073 if (N1.isUndef() && N2.isUndef())
2074 return getUNDEF(VT);
2075
2076 // Validate that all indices in Mask are within the range of the elements
2077 // input to the shuffle.
2078 int NElts = Mask.size();
2079 assert(llvm::all_of(Mask,
2080 [&](int M) { return M < (NElts * 2) && M >= -1; }) &&
2081 "Index out of range");
2082
2083 // Copy the mask so we can do any needed cleanup.
2084 SmallVector<int, 8> MaskVec(Mask);
2085
2086 // Canonicalize shuffle v, v -> v, undef
2087 if (N1 == N2) {
2088 N2 = getUNDEF(VT);
2089 for (int i = 0; i != NElts; ++i)
2090 if (MaskVec[i] >= NElts) MaskVec[i] -= NElts;
2091 }
2092
2093 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
2094 if (N1.isUndef())
2095 commuteShuffle(N1, N2, MaskVec);
2096
2097 if (TLI->hasVectorBlend()) {
2098 // If shuffling a splat, try to blend the splat instead. We do this here so
2099 // that even when this arises during lowering we don't have to re-handle it.
2100 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
2101 BitVector UndefElements;
2102 SDValue Splat = BV->getSplatValue(&UndefElements);
2103 if (!Splat)
2104 return;
2105
2106 for (int i = 0; i < NElts; ++i) {
2107 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + NElts))
2108 continue;
2109
2110 // If this input comes from undef, mark it as such.
2111 if (UndefElements[MaskVec[i] - Offset]) {
2112 MaskVec[i] = -1;
2113 continue;
2114 }
2115
2116 // If we can blend a non-undef lane, use that instead.
2117 if (!UndefElements[i])
2118 MaskVec[i] = i + Offset;
2119 }
2120 };
2121 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
2122 BlendSplat(N1BV, 0);
2123 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
2124 BlendSplat(N2BV, NElts);
2125 }
2126
2127 // Canonicalize all index into lhs, -> shuffle lhs, undef
2128 // Canonicalize all index into rhs, -> shuffle rhs, undef
2129 bool AllLHS = true, AllRHS = true;
2130 bool N2Undef = N2.isUndef();
2131 for (int i = 0; i != NElts; ++i) {
2132 if (MaskVec[i] >= NElts) {
2133 if (N2Undef)
2134 MaskVec[i] = -1;
2135 else
2136 AllLHS = false;
2137 } else if (MaskVec[i] >= 0) {
2138 AllRHS = false;
2139 }
2140 }
2141 if (AllLHS && AllRHS)
2142 return getUNDEF(VT);
2143 if (AllLHS && !N2Undef)
2144 N2 = getUNDEF(VT);
2145 if (AllRHS) {
2146 N1 = getUNDEF(VT);
2147 commuteShuffle(N1, N2, MaskVec);
2148 }
2149 // Reset our undef status after accounting for the mask.
2150 N2Undef = N2.isUndef();
2151 // Re-check whether both sides ended up undef.
2152 if (N1.isUndef() && N2Undef)
2153 return getUNDEF(VT);
2154
2155 // If Identity shuffle return that node.
2156 bool Identity = true, AllSame = true;
2157 for (int i = 0; i != NElts; ++i) {
2158 if (MaskVec[i] >= 0 && MaskVec[i] != i) Identity = false;
2159 if (MaskVec[i] != MaskVec[0]) AllSame = false;
2160 }
2161 if (Identity && NElts)
2162 return N1;
2163
2164 // Shuffling a constant splat doesn't change the result.
2165 if (N2Undef) {
2166 SDValue V = N1;
2167
2168 // Look through any bitcasts. We check that these don't change the number
2169 // (and size) of elements and just changes their types.
2170 while (V.getOpcode() == ISD::BITCAST)
2171 V = V->getOperand(0);
2172
2173 // A splat should always show up as a build vector node.
2174 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
2175 BitVector UndefElements;
2176 SDValue Splat = BV->getSplatValue(&UndefElements);
2177 // If this is a splat of an undef, shuffling it is also undef.
2178 if (Splat && Splat.isUndef())
2179 return getUNDEF(VT);
2180
2181 bool SameNumElts =
2182 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
2183
2184 // We only have a splat which can skip shuffles if there is a splatted
2185 // value and no undef lanes rearranged by the shuffle.
2186 if (Splat && UndefElements.none()) {
2187 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
2188 // number of elements match or the value splatted is a zero constant.
2189 if (SameNumElts || isNullConstant(Splat))
2190 return N1;
2191 }
2192
2193 // If the shuffle itself creates a splat, build the vector directly.
2194 if (AllSame && SameNumElts) {
2195 EVT BuildVT = BV->getValueType(0);
2196 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
2197 SDValue NewBV = getSplatBuildVector(BuildVT, dl, Splatted);
2198
2199 // We may have jumped through bitcasts, so the type of the
2200 // BUILD_VECTOR may not match the type of the shuffle.
2201 if (BuildVT != VT)
2202 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
2203 return NewBV;
2204 }
2205 }
2206 }
2207
2208 SDVTList VTs = getVTList(VT);
2210 SDValue Ops[2] = { N1, N2 };
2212 for (int i = 0; i != NElts; ++i)
2213 ID.AddInteger(MaskVec[i]);
2214
2215 void* IP = nullptr;
2216 if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP))
2217 return SDValue(E, 0);
2218
2219 // Allocate the mask array for the node out of the BumpPtrAllocator, since
2220 // SDNode doesn't have access to it. This memory will be "leaked" when
2221 // the node is deallocated, but recovered when the NodeAllocator is released.
2222 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
2223 llvm::copy(MaskVec, MaskAlloc);
2224
2225 auto *N = newSDNode<ShuffleVectorSDNode>(VTs, dl.getIROrder(),
2226 dl.getDebugLoc(), MaskAlloc);
2227 createOperands(N, Ops);
2228
2229 CSEMap.InsertNode(N, IP);
2230 InsertNode(N);
2231 SDValue V = SDValue(N, 0);
2232 NewSDValueDbgMsg(V, "Creating new node: ", this);
2233 return V;
2234}
2235
2237 EVT VT = SV.getValueType(0);
2238 SmallVector<int, 8> MaskVec(SV.getMask());
2240
2241 SDValue Op0 = SV.getOperand(0);
2242 SDValue Op1 = SV.getOperand(1);
2243 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, MaskVec);
2244}
2245
2247 SDVTList VTs = getVTList(VT);
2249 AddNodeIDNode(ID, ISD::Register, VTs, std::nullopt);
2250 ID.AddInteger(RegNo);
2251 void *IP = nullptr;
2252 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
2253 return SDValue(E, 0);
2254
2255 auto *N = newSDNode<RegisterSDNode>(RegNo, VTs);
2256 N->SDNodeBits.IsDivergent = TLI->isSDNodeSourceOfDivergence(N, FLI, UA);
2257 CSEMap.InsertNode(N, IP);
2258 InsertNode(N);
2259 return SDValue(N, 0);
2260}
2261
2264 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), std::nullopt);
2265 ID.AddPointer(RegMask);
2266 void *IP = nullptr;
2267 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
2268 return SDValue(E, 0);
2269
2270 auto *N = newSDNode<RegisterMaskSDNode>(RegMask);
2271 CSEMap.InsertNode(N, IP);
2272 InsertNode(N);
2273 return SDValue(N, 0);
2274}
2275
2277 MCSymbol *Label) {
2278 return getLabelNode(ISD::EH_LABEL, dl, Root, Label);
2279}
2280
2281SDValue SelectionDAG::getLabelNode(unsigned Opcode, const SDLoc &dl,
2282 SDValue Root, MCSymbol *Label) {
2284 SDValue Ops[] = { Root };
2285 AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), Ops);
2286 ID.AddPointer(Label);
2287 void *IP = nullptr;
2288 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
2289 return SDValue(E, 0);
2290
2291 auto *N =
2292 newSDNode<LabelSDNode>(Opcode, dl.getIROrder(), dl.getDebugLoc(), Label);
2293 createOperands(N, Ops);
2294
2295 CSEMap.InsertNode(N, IP);
2296 InsertNode(N);
2297 return SDValue(N, 0);
2298}
2299
2301 int64_t Offset, bool isTarget,
2302 unsigned TargetFlags) {
2303 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
2304 SDVTList VTs = getVTList(VT);
2305
2307 AddNodeIDNode(ID, Opc, VTs, std::nullopt);
2308 ID.AddPointer(BA);
2309 ID.AddInteger(Offset);
2310 ID.AddInteger(TargetFlags);
2311 void *IP = nullptr;
2312 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
2313 return SDValue(E, 0);
2314
2315 auto *N = newSDNode<BlockAddressSDNode>(Opc, VTs, BA, Offset, TargetFlags);
2316 CSEMap.InsertNode(N, IP);
2317 InsertNode(N);
2318 return SDValue(N, 0);
2319}
2320
2323 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), std::nullopt);
2324 ID.AddPointer(V);
2325
2326 void *IP = nullptr;
2327 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
2328 return SDValue(E, 0);
2329
2330 auto *N = newSDNode<SrcValueSDNode>(V);
2331 CSEMap.InsertNode(N, IP);
2332 InsertNode(N);
2333 return SDValue(N, 0);
2334}
2335
2338 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), std::nullopt);
2339 ID.AddPointer(MD);
2340
2341 void *IP = nullptr;
2342 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
2343 return SDValue(E, 0);
2344
2345 auto *N = newSDNode<MDNodeSDNode>(MD);
2346 CSEMap.InsertNode(N, IP);
2347 InsertNode(N);
2348 return SDValue(N, 0);
2349}
2350
2352 if (VT == V.getValueType())
2353 return V;
2354
2355 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
2356}
2357
2359 unsigned SrcAS, unsigned DestAS) {
2360 SDVTList VTs = getVTList(VT);
2361 SDValue Ops[] = {Ptr};
2364 ID.AddInteger(SrcAS);
2365 ID.AddInteger(DestAS);
2366
2367 void *IP = nullptr;
2368 if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP))
2369 return SDValue(E, 0);
2370
2371 auto *N = newSDNode<AddrSpaceCastSDNode>(dl.getIROrder(), dl.getDebugLoc(),
2372 VTs, SrcAS, DestAS);
2373 createOperands(N, Ops);
2374
2375 CSEMap.InsertNode(N, IP);
2376 InsertNode(N);
2377 return SDValue(N, 0);
2378}
2379
2381 return getNode(ISD::FREEZE, SDLoc(V), V.getValueType(), V);
2382}
2383
2384/// getShiftAmountOperand - Return the specified value casted to
2385/// the target's desired shift amount type.
2387 EVT OpTy = Op.getValueType();
2388 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
2389 if (OpTy == ShTy || OpTy.isVector()) return Op;
2390
2391 return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
2392}
2393
2395 SDLoc dl(Node);
2397 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
2398 EVT VT = Node->getValueType(0);
2399 SDValue Tmp1 = Node->getOperand(0);
2400 SDValue Tmp2 = Node->getOperand(1);
2401 const MaybeAlign MA(Node->getConstantOperandVal(3));
2402
2403 SDValue VAListLoad = getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1,
2404 Tmp2, MachinePointerInfo(V));
2405 SDValue VAList = VAListLoad;
2406
2407 if (MA && *MA > TLI.getMinStackArgumentAlignment()) {
2408 VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
2409 getConstant(MA->value() - 1, dl, VAList.getValueType()));
2410
2411 VAList =
2412 getNode(ISD::AND, dl, VAList.getValueType(), VAList,
2413 getConstant(-(int64_t)MA->value(), dl, VAList.getValueType()));
2414 }
2415
2416 // Increment the pointer, VAList, to the next vaarg
2417 Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
2418 getConstant(getDataLayout().getTypeAllocSize(
2419 VT.getTypeForEVT(*getContext())),
2420 dl, VAList.getValueType()));
2421 // Store the incremented VAList to the legalized pointer
2422 Tmp1 =
2423 getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2, MachinePointerInfo(V));
2424 // Load the actual argument out of the pointer VAList
2425 return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo());
2426}
2427
2429 SDLoc dl(Node);
2431 // This defaults to loading a pointer from the input and storing it to the
2432 // output, returning the chain.
2433 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
2434 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
2435 SDValue Tmp1 =
2436 getLoad(TLI.getPointerTy(getDataLayout()), dl, Node->getOperand(0),
2437 Node->getOperand(2), MachinePointerInfo(VS));
2438 return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
2439 MachinePointerInfo(VD));
2440}
2441
2443 const DataLayout &DL = getDataLayout();
2444 Type *Ty = VT.getTypeForEVT(*getContext());
2445 Align RedAlign = UseABI ? DL.getABITypeAlign(Ty) : DL.getPrefTypeAlign(Ty);
2446
2447 if (TLI->isTypeLegal(VT) || !VT.isVector())
2448 return RedAlign;
2449
2451 const Align StackAlign = TFI->getStackAlign();
2452
2453 // See if we can choose a smaller ABI alignment in cases where it's an
2454 // illegal vector type that will get broken down.
2455 if (RedAlign > StackAlign) {
2456 EVT IntermediateVT;
2457 MVT RegisterVT;
2458 unsigned NumIntermediates;
2459 TLI->getVectorTypeBreakdown(*getContext(), VT, IntermediateVT,
2460 NumIntermediates, RegisterVT);
2461 Ty = IntermediateVT.getTypeForEVT(*getContext());
2462 Align RedAlign2 = UseABI ? DL.getABITypeAlign(Ty) : DL.getPrefTypeAlign(Ty);
2463 if (RedAlign2 < RedAlign)
2464 RedAlign = RedAlign2;
2465 }
2466
2467 return RedAlign;
2468}
2469
2471 MachineFrameInfo &MFI = MF->getFrameInfo();
2473 int StackID = 0;
2474 if (Bytes.isScalable())
2475 StackID = TFI->getStackIDForScalableVectors();
2476 // The stack id gives an indication of whether the object is scalable or
2477 // not, so it's safe to pass in the minimum size here.
2478 int FrameIdx = MFI.CreateStackObject(Bytes.getKnownMinValue(), Alignment,
2479 false, nullptr, StackID);
2480 return getFrameIndex(FrameIdx, TLI->getFrameIndexTy(getDataLayout()));
2481}
2482
2484 Type *Ty = VT.getTypeForEVT(*getContext());
2485 Align StackAlign =
2486 std::max(getDataLayout().getPrefTypeAlign(Ty), Align(minAlign));
2487 return CreateStackTemporary(VT.getStoreSize(), StackAlign);
2488}
2489
2491 TypeSize VT1Size = VT1.getStoreSize();
2492 TypeSize VT2Size = VT2.getStoreSize();
2493 assert(VT1Size.isScalable() == VT2Size.isScalable() &&
2494 "Don't know how to choose the maximum size when creating a stack "
2495 "temporary");
2496 TypeSize Bytes = VT1Size.getKnownMinValue() > VT2Size.getKnownMinValue()
2497 ? VT1Size
2498 : VT2Size;
2499
2500 Type *Ty1 = VT1.getTypeForEVT(*getContext());
2501 Type *Ty2 = VT2.getTypeForEVT(*getContext());
2502 const DataLayout &DL = getDataLayout();
2503 Align Align = std::max(DL.getPrefTypeAlign(Ty1), DL.getPrefTypeAlign(Ty2));
2504 return CreateStackTemporary(Bytes, Align);
2505}
2506
2508 ISD::CondCode Cond, const SDLoc &dl) {
2509 EVT OpVT = N1.getValueType();
2510
2511 auto GetUndefBooleanConstant = [&]() {
2512 if (VT.getScalarType() == MVT::i1 ||
2513 TLI->getBooleanContents(OpVT) ==
2515 return getUNDEF(VT);
2516 // ZeroOrOne / ZeroOrNegative require specific values for the high bits,
2517 // so we cannot use getUNDEF(). Return zero instead.
2518 return getConstant(0, dl, VT);
2519 };
2520
2521 // These setcc operations always fold.
2522 switch (Cond) {
2523 default: break;
2524 case ISD::SETFALSE:
2525 case ISD::SETFALSE2: return getBoolConstant(false, dl, VT, OpVT);
2526 case ISD::SETTRUE:
2527 case ISD::SETTRUE2: return getBoolConstant(true, dl, VT, OpVT);
2528
2529 case ISD::SETOEQ:
2530 case ISD::SETOGT:
2531 case ISD::SETOGE:
2532 case ISD::SETOLT:
2533 case ISD::SETOLE:
2534 case ISD::SETONE:
2535 case ISD::SETO:
2536 case ISD::SETUO:
2537 case ISD::SETUEQ:
2538 case ISD::SETUNE:
2539 assert(!OpVT.isInteger() && "Illegal setcc for integer!");
2540 break;
2541 }
2542
2543 if (OpVT.isInteger()) {
2544 // For EQ and NE, we can always pick a value for the undef to make the
2545 // predicate pass or fail, so we can return undef.
2546 // Matches behavior in llvm::ConstantFoldCompareInstruction.
2547 // icmp eq/ne X, undef -> undef.
2548 if ((N1.isUndef() || N2.isUndef()) &&
2549 (Cond == ISD::SETEQ || Cond == ISD::SETNE))
2550 return GetUndefBooleanConstant();
2551
2552 // If both operands are undef, we can return undef for int comparison.
2553 // icmp undef, undef -> undef.
2554 if (N1.isUndef() && N2.isUndef())
2555 return GetUndefBooleanConstant();
2556
2557 // icmp X, X -> true/false
2558 // icmp X, undef -> true/false because undef could be X.
2559 if (N1.isUndef() || N2.isUndef() || N1 == N2)
2560 return getBoolConstant(ISD::isTrueWhenEqual(Cond), dl, VT, OpVT);
2561 }
2562
2563 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
2564 const APInt &C2 = N2C->getAPIntValue();
2565 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
2566 const APInt &C1 = N1C->getAPIntValue();
2567
2569 dl, VT, OpVT);
2570 }
2571 }
2572
2573 auto *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2574 auto *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
2575
2576 if (N1CFP && N2CFP) {
2577 APFloat::cmpResult R = N1CFP->getValueAPF().compare(N2CFP->getValueAPF());
2578 switch (Cond) {
2579 default: break;
2580 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
2581 return GetUndefBooleanConstant();
2582 [[fallthrough]];
2583 case ISD::SETOEQ: return getBoolConstant(R==APFloat::cmpEqual, dl, VT,
2584 OpVT);
2585 case ISD::SETNE: if (R==APFloat::cmpUnordered)
2586 return GetUndefBooleanConstant();
2587 [[fallthrough]];
2589 R==APFloat::cmpLessThan, dl, VT,
2590 OpVT);
2591 case ISD::SETLT: if (R==APFloat::cmpUnordered)
2592 return GetUndefBooleanConstant();
2593 [[fallthrough]];
2594 case ISD::SETOLT: return getBoolConstant(R==APFloat::cmpLessThan, dl, VT,
2595 OpVT);
2596 case ISD::SETGT: if (R==APFloat::cmpUnordered)
2597 return GetUndefBooleanConstant();
2598 [[fallthrough]];
2600 VT, OpVT);
2601 case ISD::SETLE: if (R==APFloat::cmpUnordered)
2602 return GetUndefBooleanConstant();
2603 [[fallthrough]];
2605 R==APFloat::cmpEqual, dl, VT,
2606 OpVT);
2607 case ISD::SETGE: if (R==APFloat::cmpUnordered)
2608 return GetUndefBooleanConstant();
2609 [[fallthrough]];
2611 R==APFloat::cmpEqual, dl, VT, OpVT);
2612 case ISD::SETO: return getBoolConstant(R!=APFloat::cmpUnordered, dl, VT,
2613 OpVT);
2614 case ISD::SETUO: return getBoolConstant(R==APFloat::cmpUnordered, dl, VT,
2615 OpVT);
2617 R==APFloat::cmpEqual, dl, VT,
2618 OpVT);
2619 case ISD::SETUNE: return getBoolConstant(R!=APFloat::cmpEqual, dl, VT,
2620 OpVT);
2622 R==APFloat::cmpLessThan, dl, VT,
2623 OpVT);
2625 R==APFloat::cmpUnordered, dl, VT,
2626 OpVT);
2628 VT, OpVT);
2629 case ISD::SETUGE: return getBoolConstant(R!=APFloat::cmpLessThan, dl, VT,
2630 OpVT);
2631 }
2632 } else if (N1CFP && OpVT.isSimple() && !N2.isUndef()) {
2633 // Ensure that the constant occurs on the RHS.
2635 if (!TLI->isCondCodeLegal(SwappedCond, OpVT.getSimpleVT()))
2636 return SDValue();
2637 return getSetCC(dl, VT, N2, N1, SwappedCond);
2638 } else if ((N2CFP && N2CFP->getValueAPF().isNaN()) ||
2639 (OpVT.isFloatingPoint() && (N1.isUndef() || N2.isUndef()))) {
2640 // If an operand is known to be a nan (or undef that could be a nan), we can
2641 // fold it.
2642 // Choosing NaN for the undef will always make unordered comparison succeed
2643 // and ordered comparison fails.
2644 // Matches behavior in llvm::ConstantFoldCompareInstruction.
2645 switch (ISD::getUnorderedFlavor(Cond)) {
2646 default:
2647 llvm_unreachable("Unknown flavor!");
2648 case 0: // Known false.
2649 return getBoolConstant(false, dl, VT, OpVT);
2650 case 1: // Known true.
2651 return getBoolConstant(true, dl, VT, OpVT);
2652 case 2: // Undefined.
2653 return GetUndefBooleanConstant();
2654 }
2655 }
2656
2657 // Could not fold it.
2658 return SDValue();
2659}
2660
2661/// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2662/// use this predicate to simplify operations downstream.
2664 unsigned BitWidth = Op.getScalarValueSizeInBits();
2666}
2667
2668/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2669/// this predicate to simplify operations downstream. Mask is known to be zero
2670/// for bits that V cannot have.
2672 unsigned Depth) const {
2673 return Mask.isSubsetOf(computeKnownBits(V, Depth).Zero);
2674}
2675
2676/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero in
2677/// DemandedElts. We use this predicate to simplify operations downstream.
2678/// Mask is known to be zero for bits that V cannot have.
2680 const APInt &DemandedElts,
2681 unsigned Depth) const {
2682 return Mask.isSubsetOf(computeKnownBits(V, DemandedElts, Depth).Zero);
2683}
2684
2685/// MaskedVectorIsZero - Return true if 'Op' is known to be zero in
2686/// DemandedElts. We use this predicate to simplify operations downstream.
2688 unsigned Depth /* = 0 */) const {
2689 return computeKnownBits(V, DemandedElts, Depth).isZero();
2690}
2691
2692/// MaskedValueIsAllOnes - Return true if '(Op & Mask) == Mask'.
2694 unsigned Depth) const {
2695 return Mask.isSubsetOf(computeKnownBits(V, Depth).One);
2696}
2697
2699 const APInt &DemandedElts,
2700 unsigned Depth) const {
2701 EVT VT = Op.getValueType();
2702 assert(VT.isVector() && !VT.isScalableVector() && "Only for fixed vectors!");
2703
2704 unsigned NumElts = VT.getVectorNumElements();
2705 assert(DemandedElts.getBitWidth() == NumElts && "Unexpected demanded mask.");
2706
2707 APInt KnownZeroElements = APInt::getZero(NumElts);
2708 for (unsigned EltIdx = 0; EltIdx != NumElts; ++EltIdx) {
2709 if (!DemandedElts[EltIdx])
2710 continue; // Don't query elements that are not demanded.
2711 APInt Mask = APInt::getOneBitSet(NumElts, EltIdx);
2712 if (MaskedVectorIsZero(Op, Mask, Depth))
2713 KnownZeroElements.setBit(EltIdx);
2714 }
2715 return KnownZeroElements;
2716}
2717
2718/// isSplatValue - Return true if the vector V has the same value
2719/// across all DemandedElts. For scalable vectors, we don't know the
2720/// number of lanes at compile time. Instead, we use a 1 bit APInt
2721/// to represent a conservative value for all lanes; that is, that
2722/// one bit value is implicitly splatted across all lanes.
2723bool SelectionDAG::isSplatValue(SDValue V, const APInt &DemandedElts,
2724 APInt &UndefElts, unsigned Depth) const {
2725 unsigned Opcode = V.getOpcode();
2726 EVT VT = V.getValueType();
2727 assert(VT.isVector() && "Vector type expected");
2728 assert((!VT.isScalableVector() || DemandedElts.getBitWidth() == 1) &&
2729 "scalable demanded bits are ignored");
2730
2731 if (!DemandedElts)
2732 return false; // No demanded elts, better to assume we don't know anything.
2733
2734 if (Depth >= MaxRecursionDepth)
2735 return false; // Limit search depth.
2736
2737 // Deal with some common cases here that work for both fixed and scalable
2738 // vector types.
2739 switch (Opcode) {
2740 case ISD::SPLAT_VECTOR:
2741 UndefElts = V.getOperand(0).isUndef()
2742 ? APInt::getAllOnes(DemandedElts.getBitWidth())
2743 : APInt(DemandedElts.getBitWidth(), 0);
2744 return true;
2745 case ISD::ADD:
2746 case ISD::SUB:
2747 case ISD::AND:
2748 case ISD::XOR:
2749 case ISD::OR: {
2750 APInt UndefLHS, UndefRHS;
2751 SDValue LHS = V.getOperand(0);
2752 SDValue RHS = V.getOperand(1);
2753 if (isSplatValue(LHS, DemandedElts, UndefLHS, Depth + 1) &&
2754 isSplatValue(RHS, DemandedElts, UndefRHS, Depth + 1)) {
2755 UndefElts = UndefLHS | UndefRHS;
2756 return true;
2757 }
2758 return false;
2759 }
2760 case ISD::ABS:
2761 case ISD::TRUNCATE:
2762 case ISD::SIGN_EXTEND:
2763 case ISD::ZERO_EXTEND:
2764 return isSplatValue(V.getOperand(0), DemandedElts, UndefElts, Depth + 1);
2765 default:
2766 if (Opcode >= ISD::BUILTIN_OP_END || Opcode == ISD::INTRINSIC_WO_CHAIN ||
2767 Opcode == ISD::INTRINSIC_W_CHAIN || Opcode == ISD::INTRINSIC_VOID)
2768 return TLI->isSplatValueForTargetNode(V, DemandedElts, UndefElts, *this,
2769 Depth);
2770 break;
2771}
2772
2773 // We don't support other cases than those above for scalable vectors at
2774 // the moment.
2775 if (VT.isScalableVector())
2776 return false;
2777
2778 unsigned NumElts = VT.getVectorNumElements();
2779 assert(NumElts == DemandedElts.getBitWidth() && "Vector size mismatch");
2780 UndefElts = APInt::getZero(NumElts);
2781
2782 switch (Opcode) {
2783 case ISD::BUILD_VECTOR: {
2784 SDValue Scl;
2785 for (unsigned i = 0; i != NumElts; ++i) {
2786 SDValue Op = V.getOperand(i);
2787 if (Op.isUndef()) {
2788 UndefElts.setBit(i);
2789 continue;
2790 }
2791 if (!DemandedElts[i])
2792 continue;
2793 if (Scl && Scl != Op)
2794 return false;
2795 Scl = Op;
2796 }
2797 return true;
2798 }
2799 case ISD::VECTOR_SHUFFLE: {
2800 // Check if this is a shuffle node doing a splat or a shuffle of a splat.
2801 APInt DemandedLHS = APInt::getZero(NumElts);
2802 APInt DemandedRHS = APInt::getZero(NumElts);
2803 ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(V)->getMask();
2804 for (int i = 0; i != (int)NumElts; ++i) {
2805 int M = Mask[i];
2806 if (M < 0) {
2807 UndefElts.setBit(i);
2808 continue;
2809 }
2810 if (!DemandedElts[i])
2811 continue;
2812 if (M < (int)NumElts)
2813 DemandedLHS.setBit(M);
2814 else
2815 DemandedRHS.setBit(M - NumElts);
2816 }
2817
2818 // If we aren't demanding either op, assume there's no splat.
2819 // If we are demanding both ops, assume there's no splat.
2820 if ((DemandedLHS.isZero() && DemandedRHS.isZero()) ||
2821 (!DemandedLHS.isZero() && !DemandedRHS.isZero()))
2822 return false;
2823
2824 // See if the demanded elts of the source op is a splat or we only demand
2825 // one element, which should always be a splat.
2826 // TODO: Handle source ops splats with undefs.
2827 auto CheckSplatSrc = [&](SDValue Src, const APInt &SrcElts) {
2828 APInt SrcUndefs;
2829 return (SrcElts.popcount() == 1) ||
2830 (isSplatValue(Src, SrcElts, SrcUndefs, Depth + 1) &&
2831 (SrcElts & SrcUndefs).isZero());
2832 };
2833 if (!DemandedLHS.isZero())
2834 return CheckSplatSrc(V.getOperand(0), DemandedLHS);
2835 return CheckSplatSrc(V.getOperand(1), DemandedRHS);
2836 }
2838 // Offset the demanded elts by the subvector index.
2839 SDValue Src = V.getOperand(0);
2840 // We don't support scalable vectors at the moment.
2841 if (Src.getValueType().isScalableVector())
2842 return false;
2843 uint64_t Idx = V.getConstantOperandVal(1);
2844 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
2845 APInt UndefSrcElts;
2846 APInt DemandedSrcElts = DemandedElts.zext(NumSrcElts).shl(Idx);
2847 if (isSplatValue(Src, DemandedSrcElts, UndefSrcElts, Depth + 1)) {
2848 UndefElts = UndefSrcElts.extractBits(NumElts, Idx);
2849 return true;
2850 }
2851 break;
2852 }
2856 // Widen the demanded elts by the src element count.
2857 SDValue Src = V.getOperand(0);
2858 // We don't support scalable vectors at the moment.
2859 if (Src.getValueType().isScalableVector())
2860 return false;
2861 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
2862 APInt UndefSrcElts;
2863 APInt DemandedSrcElts = DemandedElts.zext(NumSrcElts);
2864 if (isSplatValue(Src, DemandedSrcElts, UndefSrcElts, Depth + 1)) {
2865 UndefElts = UndefSrcElts.trunc(NumElts);
2866 return true;
2867 }
2868 break;
2869 }
2870 case ISD::BITCAST: {
2871 SDValue Src = V.getOperand(0);
2872 EVT SrcVT = Src.getValueType();
2873 unsigned SrcBitWidth = SrcVT.getScalarSizeInBits();
2874 unsigned BitWidth = VT.getScalarSizeInBits();
2875
2876 // Ignore bitcasts from unsupported types.
2877 // TODO: Add fp support?
2878 if (!SrcVT.isVector() || !SrcVT.isInteger() || !VT.isInteger())
2879 break;
2880
2881 // Bitcast 'small element' vector to 'large element' vector.
2882 if ((BitWidth % SrcBitWidth) == 0) {
2883 // See if each sub element is a splat.
2884 unsigned Scale = BitWidth / SrcBitWidth;
2885 unsigned NumSrcElts = SrcVT.getVectorNumElements();
2886 APInt ScaledDemandedElts =
2887 APIntOps::ScaleBitMask(DemandedElts, NumSrcElts);
2888 for (unsigned I = 0; I != Scale; ++I) {
2889 APInt SubUndefElts;
2890 APInt SubDemandedElt = APInt::getOneBitSet(Scale, I);
2891 APInt SubDemandedElts = APInt::getSplat(NumSrcElts, SubDemandedElt);
2892 SubDemandedElts &= ScaledDemandedElts;
2893 if (!isSplatValue(Src, SubDemandedElts, SubUndefElts, Depth + 1))
2894 return false;
2895 // TODO: Add support for merging sub undef elements.
2896 if (!SubUndefElts.isZero())
2897 return false;
2898 }
2899 return true;
2900 }
2901 break;
2902 }
2903 }
2904
2905 return false;
2906}
2907
2908/// Helper wrapper to main isSplatValue function.
2909bool SelectionDAG::isSplatValue(SDValue V, bool AllowUndefs) const {
2910 EVT VT = V.getValueType();
2911 assert(VT.isVector() && "Vector type expected");
2912
2913 APInt UndefElts;
2914 // Since the number of lanes in a scalable vector is unknown at compile time,
2915 // we track one bit which is implicitly broadcast to all lanes. This means
2916 // that all lanes in a scalable vector are considered demanded.
2917 APInt DemandedElts
2919 return isSplatValue(V, DemandedElts, UndefElts) &&
2920 (AllowUndefs || !UndefElts);
2921}
2922
2925
2926 EVT VT = V.getValueType();
2927 unsigned Opcode = V.getOpcode();
2928 switch (Opcode) {
2929 default: {
2930 APInt UndefElts;
2931 // Since the number of lanes in a scalable vector is unknown at compile time,
2932 // we track one bit which is implicitly broadcast to all lanes. This means
2933 // that all lanes in a scalable vector are considered demanded.
2934 APInt DemandedElts
2936
2937 if (isSplatValue(V, DemandedElts, UndefElts)) {
2938 if (VT.isScalableVector()) {
2939 // DemandedElts and UndefElts are ignored for scalable vectors, since
2940 // the only supported cases are SPLAT_VECTOR nodes.
2941 SplatIdx = 0;
2942 } else {
2943 // Handle case where all demanded elements are UNDEF.
2944 if (DemandedElts.isSubsetOf(UndefElts)) {
2945 SplatIdx = 0;
2946 return getUNDEF(VT);
2947 }
2948 SplatIdx = (UndefElts & DemandedElts).countr_one();
2949 }
2950 return V;
2951 }
2952 break;
2953 }
2954 case ISD::SPLAT_VECTOR:
2955 SplatIdx = 0;
2956 return V;
2957 case ISD::VECTOR_SHUFFLE: {
2958 assert(!VT.isScalableVector());
2959 // Check if this is a shuffle node doing a splat.
2960 // TODO - remove this and rely purely on SelectionDAG::isSplatValue,
2961 // getTargetVShiftNode currently struggles without the splat source.
2962 auto *SVN = cast<ShuffleVectorSDNode>(V);
2963 if (!SVN->isSplat())
2964 break;
2965 int Idx = SVN->getSplatIndex();
2966 int NumElts = V.getValueType().getVectorNumElements();
2967 SplatIdx = Idx % NumElts;
2968 return V.getOperand(Idx / NumElts);
2969 }
2970 }
2971
2972 return SDValue();
2973}
2974
2976 int SplatIdx;
2977 if (SDValue SrcVector = getSplatSourceVector(V, SplatIdx)) {
2978 EVT SVT = SrcVector.getValueType().getScalarType();
2979 EVT LegalSVT = SVT;
2980 if (LegalTypes && !TLI->isTypeLegal(SVT)) {
2981 if (!SVT.isInteger())
2982 return SDValue();
2983 LegalSVT = TLI->getTypeToTransformTo(*getContext(), LegalSVT);
2984 if (LegalSVT.bitsLT(SVT))
2985 return SDValue();
2986 }
2987 return getNode(ISD::EXTRACT_VECTOR_ELT, SDLoc(V), LegalSVT, SrcVector,
2988 getVectorIdxConstant(SplatIdx, SDLoc(V)));
2989 }
2990 return SDValue();
2991}
2992
2993const APInt *
2995 const APInt &DemandedElts) const {
2996 assert((V.getOpcode() == ISD::SHL || V.getOpcode() == ISD::SRL ||
2997 V.getOpcode() == ISD::SRA) &&
2998 "Unknown shift node");
2999 unsigned BitWidth = V.getScalarValueSizeInBits();
3000 if (ConstantSDNode *SA = isConstOrConstSplat(V.getOperand(1), DemandedElts)) {
3001 // Shifting more than the bitwidth is not valid.
3002 const APInt &ShAmt = SA->getAPIntValue();
3003 if (ShAmt.ult(BitWidth))
3004 return &ShAmt;
3005 }
3006 return nullptr;
3007}
3008
3010 EVT VT = V.getValueType();
3011 APInt DemandedElts = VT.isFixedLengthVector()
3013 : APInt(1, 1);
3014 return getValidShiftAmountConstant(V, DemandedElts);
3015}
3016
3018 SDValue V, const APInt &DemandedElts) const {
3019 assert((V.getOpcode() == ISD::SHL || V.getOpcode() == ISD::SRL ||
3020 V.getOpcode() == ISD::SRA) &&
3021 "Unknown shift node");
3022 if (const APInt *ValidAmt = getValidShiftAmountConstant(V, DemandedElts))
3023 return ValidAmt;
3024 unsigned BitWidth = V.getScalarValueSizeInBits();
3025 auto *BV = dyn_cast<BuildVectorSDNode>(V.getOperand(1));
3026 if (!BV)
3027 return nullptr;
3028 const APInt *MinShAmt = nullptr;
3029 for (unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
3030 if (!DemandedElts[i])
3031 continue;
3032 auto *SA = dyn_cast<ConstantSDNode>(BV->getOperand(i));
3033 if (!SA)
3034 return nullptr;
3035 // Shifting more than the bitwidth is not valid.
3036 const APInt &ShAmt = SA->getAPIntValue();
3037 if (ShAmt.uge(BitWidth))
3038 return nullptr;
3039 if (MinShAmt && MinShAmt->ule(ShAmt))
3040 continue;
3041 MinShAmt = &ShAmt;
3042 }
3043 return MinShAmt;
3044}
3045
3047 EVT VT = V.getValueType();
3048 APInt DemandedElts = VT.isFixedLengthVector()
3050 : APInt(1, 1);
3051 return getValidMinimumShiftAmountConstant(V, DemandedElts);
3052}
3053
3055 SDValue V, const APInt &DemandedElts) const {
3056 assert((V.getOpcode() == ISD::SHL || V.getOpcode() == ISD::SRL ||
3057 V.getOpcode() == ISD::SRA) &&
3058 "Unknown shift node");
3059 if (const APInt *ValidAmt = getValidShiftAmountConstant(V, DemandedElts))
3060 return ValidAmt;
3061 unsigned BitWidth = V.getScalarValueSizeInBits();
3062 auto *BV = dyn_cast<BuildVectorSDNode>(V.getOperand(1));
3063 if (!BV)
3064 return nullptr;
3065 const APInt *MaxShAmt = nullptr;
3066 for (unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
3067 if (!DemandedElts[i])
3068 continue;
3069 auto *SA = dyn_cast<ConstantSDNode>(BV->getOperand(i));
3070 if (!SA)
3071 return nullptr;
3072 // Shifting more than the bitwidth is not valid.
3073 const APInt &ShAmt = SA->getAPIntValue();
3074 if (ShAmt.uge(BitWidth))
3075 return nullptr;
3076 if (MaxShAmt && MaxShAmt->uge(ShAmt))
3077 continue;
3078 MaxShAmt = &ShAmt;
3079 }
3080 return MaxShAmt;
3081}
3082
3084 EVT VT = V.getValueType();
3085 APInt DemandedElts = VT.isFixedLengthVector()
3087 : APInt(1, 1);
3088 return getValidMaximumShiftAmountConstant(V, DemandedElts);
3089}
3090
3091/// Determine which bits of Op are known to be either zero or one and return
3092/// them in Known. For vectors, the known bits are those that are shared by
3093/// every vector element.
3095 EVT VT = Op.getValueType();
3096
3097 // Since the number of lanes in a scalable vector is unknown at compile time,
3098 // we track one bit which is implicitly broadcast to all lanes. This means
3099 // that all lanes in a scalable vector are considered demanded.
3100 APInt DemandedElts = VT.isFixedLengthVector()
3102 : APInt(1, 1);
3103 return computeKnownBits(Op, DemandedElts, Depth);
3104}
3105
3106/// Determine which bits of Op are known to be either zero or one and return
3107/// them in Known. The DemandedElts argument allows us to only collect the known
3108/// bits that are shared by the requested vector elements.
3110 unsigned Depth) const {
3111 unsigned BitWidth = Op.getScalarValueSizeInBits();
3112
3113 KnownBits Known(BitWidth); // Don't know anything.
3114
3115 if (auto *C = dyn_cast<ConstantSDNode>(Op)) {
3116 // We know all of the bits for a constant!
3117 return KnownBits::makeConstant(C->getAPIntValue());
3118 }
3119 if (auto *C = dyn_cast<ConstantFPSDNode>(Op)) {
3120 // We know all of the bits for a constant fp!
3121 return KnownBits::makeConstant(C->getValueAPF().bitcastToAPInt());
3122 }
3123
3124 if (Depth >= MaxRecursionDepth)
3125 return Known; // Limit search depth.
3126
3127 KnownBits Known2;
3128 unsigned NumElts = DemandedElts.getBitWidth();
3129 assert((!Op.getValueType().isFixedLengthVector() ||
3130 NumElts == Op.getValueType().getVectorNumElements()) &&
3131 "Unexpected vector size");
3132
3133 if (!DemandedElts)
3134 return Known; // No demanded elts, better to assume we don't know anything.
3135
3136 unsigned Opcode = Op.getOpcode();
3137 switch (Opcode) {
3138 case ISD::MERGE_VALUES:
3139 return computeKnownBits(Op.getOperand(Op.getResNo()), DemandedElts,
3140 Depth + 1);
3141 case ISD::SPLAT_VECTOR: {
3142 SDValue SrcOp = Op.getOperand(0);
3143 assert(SrcOp.getValueSizeInBits() >= BitWidth &&
3144 "Expected SPLAT_VECTOR implicit truncation");
3145 // Implicitly truncate the bits to match the official semantics of
3146 // SPLAT_VECTOR.
3147 Known = computeKnownBits(SrcOp, Depth + 1).trunc(BitWidth);
3148 break;
3149 }
3151 unsigned ScalarSize = Op.getOperand(0).getScalarValueSizeInBits();
3152 assert(ScalarSize * Op.getNumOperands() == BitWidth &&
3153 "Expected SPLAT_VECTOR_PARTS scalars to cover element width");
3154 for (auto [I, SrcOp] : enumerate(Op->ops())) {
3155 Known.insertBits(computeKnownBits(SrcOp, Depth + 1), ScalarSize * I);
3156 }
3157 break;
3158 }
3159 case ISD::STEP_VECTOR: {
3160 const APInt &Step = Op.getConstantOperandAPInt(0);
3161
3162 if (Step.isPowerOf2())
3163 Known.Zero.setLowBits(Step.logBase2());
3164
3166
3167 if (!isUIntN(BitWidth, Op.getValueType().getVectorMinNumElements()))
3168 break;
3169 const APInt MinNumElts =
3170 APInt(BitWidth, Op.getValueType().getVectorMinNumElements());
3171
3172 bool Overflow;
3173 const APInt MaxNumElts = getVScaleRange(&F, BitWidth)
3175 .umul_ov(MinNumElts, Overflow);
3176 if (Overflow)
3177 break;
3178
3179 const APInt MaxValue = (MaxNumElts - 1).umul_ov(Step, Overflow);
3180 if (Overflow)
3181 break;
3182
3183 Known.Zero.setHighBits(MaxValue.countl_zero());
3184 break;
3185 }
3186 case ISD::BUILD_VECTOR:
3187 assert(!Op.getValueType().isScalableVector());
3188 // Collect the known bits that are shared by every demanded vector element.
3189 Known.Zero.setAllBits(); Known.One.setAllBits();
3190 for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
3191 if (!DemandedElts[i])
3192 continue;
3193
3194 SDValue SrcOp = Op.getOperand(i);
3195 Known2 = computeKnownBits(SrcOp, Depth + 1);
3196
3197 // BUILD_VECTOR can implicitly truncate sources, we must handle this.
3198 if (SrcOp.getValueSizeInBits() != BitWidth) {
3199 assert(SrcOp.getValueSizeInBits() > BitWidth &&
3200 "Expected BUILD_VECTOR implicit truncation");
3201 Known2 = Known2.trunc(BitWidth);
3202 }
3203
3204 // Known bits are the values that are shared by every demanded element.
3205 Known = Known.intersectWith(Known2);
3206
3207 // If we don't know any bits, early out.
3208 if (Known.isUnknown())
3209 break;
3210 }
3211 break;
3212 case ISD::VECTOR_SHUFFLE: {
3213 assert(!Op.getValueType().isScalableVector());
3214 // Collect the known bits that are shared by every vector element referenced
3215 // by the shuffle.
3216 APInt DemandedLHS, DemandedRHS;
3217 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(Op);
3218 assert(NumElts == SVN->getMask().size() && "Unexpected vector size");
3219 if (!getShuffleDemandedElts(NumElts, SVN->getMask(), DemandedElts,
3220 DemandedLHS, DemandedRHS))
3221 break;
3222
3223 // Known bits are the values that are shared by every demanded element.
3224 Known.Zero.setAllBits(); Known.One.setAllBits();
3225 if (!!DemandedLHS) {
3226 SDValue LHS = Op.getOperand(0);
3227 Known2 = computeKnownBits(LHS, DemandedLHS, Depth + 1);
3228 Known = Known.intersectWith(Known2);
3229 }
3230 // If we don't know any bits, early out.
3231 if (Known.isUnknown())
3232 break;
3233 if (!!DemandedRHS) {
3234 SDValue RHS = Op.getOperand(1);
3235 Known2 = computeKnownBits(RHS, DemandedRHS, Depth + 1);
3236 Known = Known.intersectWith(Known2);
3237 }
3238 break;
3239 }
3240 case ISD::VSCALE: {
3242 const APInt &Multiplier = Op.getConstantOperandAPInt(0);
3243 Known = getVScaleRange(&F, BitWidth).multiply(Multiplier).toKnownBits();
3244 break;
3245 }
3246 case ISD::CONCAT_VECTORS: {
3247 if (Op.getValueType().isScalableVector())
3248 break;
3249 // Split DemandedElts and test each of the demanded subvectors.
3250 Known.Zero.setAllBits(); Known.One.setAllBits();
3251 EVT SubVectorVT = Op.getOperand(0).getValueType();
3252 unsigned NumSubVectorElts = SubVectorVT.getVectorNumElements();
3253 unsigned NumSubVectors = Op.getNumOperands();
3254 for (unsigned i = 0; i != NumSubVectors; ++i) {
3255 APInt DemandedSub =
3256 DemandedElts.extractBits(NumSubVectorElts, i * NumSubVectorElts);
3257 if (!!DemandedSub) {
3258 SDValue Sub = Op.getOperand(i);
3259 Known2 = computeKnownBits(Sub, DemandedSub, Depth + 1);
3260 Known = Known.intersectWith(Known2);
3261 }
3262 // If we don't know any bits, early out.
3263 if (Known.isUnknown())
3264 break;
3265 }
3266 break;
3267 }
3268 case ISD::INSERT_SUBVECTOR: {
3269 if (Op.getValueType().isScalableVector())
3270 break;
3271 // Demand any elements from the subvector and the remainder from the src its
3272 // inserted into.
3273 SDValue Src = Op.getOperand(0);
3274 SDValue Sub = Op.getOperand(1);
3275 uint64_t Idx = Op.getConstantOperandVal(2);
3276 unsigned NumSubElts = Sub.getValueType().getVectorNumElements();
3277 APInt DemandedSubElts = DemandedElts.extractBits(NumSubElts, Idx);
3278 APInt DemandedSrcElts = DemandedElts;
3279 DemandedSrcElts.insertBits(APInt::getZero(NumSubElts), Idx);
3280
3281 Known.One.setAllBits();
3282 Known.Zero.setAllBits();
3283 if (!!DemandedSubElts) {
3284 Known = computeKnownBits(Sub, DemandedSubElts, Depth + 1);
3285 if (Known.isUnknown())
3286 break; // early-out.
3287 }
3288 if (!!DemandedSrcElts) {
3289 Known2 = computeKnownBits(Src, DemandedSrcElts, Depth + 1);
3290 Known = Known.intersectWith(Known2);
3291 }
3292 break;
3293 }
3295 // Offset the demanded elts by the subvector index.
3296 SDValue Src = Op.getOperand(0);
3297 // Bail until we can represent demanded elements for scalable vectors.
3298 if (Op.getValueType().isScalableVector() || Src.getValueType().isScalableVector())
3299 break;
3300 uint64_t Idx = Op.getConstantOperandVal(1);
3301 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
3302 APInt DemandedSrcElts = DemandedElts.zext(NumSrcElts).shl(Idx);
3303 Known = computeKnownBits(Src, DemandedSrcElts, Depth + 1);
3304 break;
3305 }
3306 case ISD::SCALAR_TO_VECTOR: {
3307 if (Op.getValueType().isScalableVector())
3308 break;
3309 // We know about scalar_to_vector as much as we know about it source,
3310 // which becomes the first element of otherwise unknown vector.
3311 if (DemandedElts != 1)
3312 break;
3313
3314 SDValue N0 = Op.getOperand(0);
3315 Known = computeKnownBits(N0, Depth + 1);
3316 if (N0.getValueSizeInBits() != BitWidth)
3317 Known = Known.trunc(BitWidth);
3318
3319 break;
3320 }
3321 case ISD::BITCAST: {
3322 if (Op.getValueType().isScalableVector())
3323 break;
3324
3325 SDValue N0 = Op.getOperand(0);
3326 EVT SubVT = N0.getValueType();
3327 unsigned SubBitWidth = SubVT.getScalarSizeInBits();
3328
3329 // Ignore bitcasts from unsupported types.
3330 if (!(SubVT.isInteger() || SubVT.isFloatingPoint()))
3331 break;
3332
3333 // Fast handling of 'identity' bitcasts.
3334 if (BitWidth == SubBitWidth) {
3335 Known = computeKnownBits(N0, DemandedElts, Depth + 1);
3336 break;
3337 }
3338
3339 bool IsLE = getDataLayout().isLittleEndian();
3340
3341 // Bitcast 'small element' vector to 'large element' scalar/vector.
3342 if ((BitWidth % SubBitWidth) == 0) {
3343 assert(N0.getValueType().isVector() && "Expected bitcast from vector");
3344
3345 // Collect known bits for the (larger) output by collecting the known
3346 // bits from each set of sub elements and shift these into place.
3347 // We need to separately call computeKnownBits for each set of
3348 // sub elements as the knownbits for each is likely to be different.
3349 unsigned SubScale = BitWidth / SubBitWidth;
3350 APInt SubDemandedElts(NumElts * SubScale, 0);
3351 for (unsigned i = 0; i != NumElts; ++i)
3352 if (DemandedElts[i])
3353 SubDemandedElts.setBit(i * SubScale);
3354
3355 for (unsigned i = 0; i != SubScale; ++i) {
3356 Known2 = computeKnownBits(N0, SubDemandedElts.shl(i),
3357 Depth + 1);
3358 unsigned Shifts = IsLE ? i : SubScale - 1 - i;
3359 Known.insertBits(Known2, SubBitWidth * Shifts);
3360 }
3361 }
3362
3363 // Bitcast 'large element' scalar/vector to 'small element' vector.
3364 if ((SubBitWidth % BitWidth) == 0) {
3365 assert(Op.getValueType().isVector() && "Expected bitcast to vector");
3366
3367 // Collect known bits for the (smaller) output by collecting the known
3368 // bits from the overlapping larger input elements and extracting the
3369 // sub sections we actually care about.
3370 unsigned SubScale = SubBitWidth / BitWidth;
3371 APInt SubDemandedElts =
3372 APIntOps::ScaleBitMask(DemandedElts, NumElts / SubScale);
3373 Known2 = computeKnownBits(N0, SubDemandedElts, Depth + 1);
3374
3375 Known.Zero.setAllBits(); Known.One.setAllBits();
3376 for (unsigned i = 0; i != NumElts; ++i)
3377 if (DemandedElts[i]) {
3378 unsigned Shifts = IsLE ? i : NumElts - 1 - i;
3379 unsigned Offset = (Shifts % SubScale) * BitWidth;
3380 Known = Known.intersectWith(Known2.extractBits(BitWidth, Offset));
3381 // If we don't know any bits, early out.
3382 if (Known.isUnknown())
3383 break;
3384 }
3385 }
3386 break;
3387 }
3388 case ISD::AND:
3389 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3390 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3391
3392 Known &= Known2;
3393 break;
3394 case ISD::OR:
3395 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3396 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3397
3398 Known |= Known2;
3399 break;
3400 case ISD::XOR:
3401 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3402 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3403
3404 Known ^= Known2;
3405 break;
3406 case ISD::MUL: {
3407 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3408 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3409 bool SelfMultiply = Op.getOperand(0) == Op.getOperand(1);
3410 // TODO: SelfMultiply can be poison, but not undef.
3411 if (SelfMultiply)
3412 SelfMultiply &= isGuaranteedNotToBeUndefOrPoison(
3413 Op.getOperand(0), DemandedElts, false, Depth + 1);
3414 Known = KnownBits::mul(Known, Known2, SelfMultiply);
3415
3416 // If the multiplication is known not to overflow, the product of a number
3417 // with itself is non-negative. Only do this if we didn't already computed
3418 // the opposite value for the sign bit.
3419 if (Op->getFlags().hasNoSignedWrap() &&
3420 Op.getOperand(0) == Op.getOperand(1) &&
3421 !Known.isNegative())
3422 Known.makeNonNegative();
3423 break;
3424 }
3425 case ISD::MULHU: {
3426 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3427 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3428 Known = KnownBits::mulhu(Known, Known2);
3429 break;
3430 }
3431 case ISD::MULHS: {
3432 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3433 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3434 Known = KnownBits::mulhs(Known, Known2);
3435 break;
3436 }
3437 case ISD::ABDU: {
3438 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3439 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3440 Known = KnownBits::abdu(Known, Known2);
3441 break;
3442 }
3443 case ISD::ABDS: {
3444 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3445 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3446 Known = KnownBits::abds(Known, Known2);
3447 break;
3448 }
3449 case ISD::UMUL_LOHI: {
3450 assert((Op.getResNo() == 0 || Op.getResNo() == 1) && "Unknown result");
3451 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3452 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3453 bool SelfMultiply = Op.getOperand(0) == Op.getOperand(1);
3454 if (Op.getResNo() == 0)
3455 Known = KnownBits::mul(Known, Known2, SelfMultiply);
3456 else
3457 Known = KnownBits::mulhu(Known, Known2);
3458 break;
3459 }
3460 case ISD::SMUL_LOHI: {
3461 assert((Op.getResNo() == 0 || Op.getResNo() == 1) && "Unknown result");
3462 Known = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3463 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3464 bool SelfMultiply = Op.getOperand(0) == Op.getOperand(1);
3465 if (Op.getResNo() == 0)
3466 Known = KnownBits::mul(Known, Known2, SelfMultiply);
3467 else
3468 Known = KnownBits::mulhs(Known, Known2);
3469 break;
3470 }
3471 case ISD::AVGFLOORU:
3472 case ISD::AVGCEILU:
3473 case ISD::AVGFLOORS:
3474 case ISD::AVGCEILS: {
3475 bool IsCeil = Opcode == ISD::AVGCEILU || Opcode == ISD::AVGCEILS;
3476 bool IsSigned = Opcode == ISD::AVGFLOORS || Opcode == ISD::AVGCEILS;
3477 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3478 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3479 Known = IsSigned ? Known.sext(BitWidth + 1) : Known.zext(BitWidth + 1);
3480 Known2 = IsSigned ? Known2.sext(BitWidth + 1) : Known2.zext(BitWidth + 1);
3481 KnownBits Carry = KnownBits::makeConstant(APInt(1, IsCeil ? 1 : 0));
3482 Known = KnownBits::computeForAddCarry(Known, Known2, Carry);
3483 Known = Known.extractBits(BitWidth, 1);
3484 break;
3485 }
3486 case ISD::SELECT:
3487 case ISD::VSELECT:
3488 Known = computeKnownBits(Op.getOperand(2), DemandedElts, Depth+1);
3489 // If we don't know any bits, early out.
3490 if (Known.isUnknown())
3491 break;
3492 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth+1);
3493
3494 // Only known if known in both the LHS and RHS.
3495 Known = Known.intersectWith(Known2);
3496 break;
3497 case ISD::SELECT_CC:
3498 Known = computeKnownBits(Op.getOperand(3), DemandedElts, Depth+1);
3499 // If we don't know any bits, early out.
3500 if (Known.isUnknown())
3501 break;
3502 Known2 = computeKnownBits(Op.getOperand(2), DemandedElts, Depth+1);
3503
3504 // Only known if known in both the LHS and RHS.
3505 Known = Known.intersectWith(Known2);
3506 break;
3507 case ISD::SMULO:
3508 case ISD::UMULO:
3509 if (Op.getResNo() != 1)
3510 break;
3511 // The boolean result conforms to getBooleanContents.
3512 // If we know the result of a setcc has the top bits zero, use this info.
3513 // We know that we have an integer-based boolean since these operations
3514 // are only available for integer.
3515 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
3517 BitWidth > 1)
3518 Known.Zero.setBitsFrom(1);
3519 break;
3520 case ISD::SETCC:
3521 case ISD::SETCCCARRY:
3522 case ISD::STRICT_FSETCC:
3523 case ISD::STRICT_FSETCCS: {
3524 unsigned OpNo = Op->isStrictFPOpcode() ? 1 : 0;
3525 // If we know the result of a setcc has the top bits zero, use this info.
3526 if (TLI->getBooleanContents(Op.getOperand(OpNo).getValueType()) ==
3528 BitWidth > 1)
3529 Known.Zero.setBitsFrom(1);
3530 break;
3531 }
3532 case ISD::SHL: {
3533 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3534 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3535
3536 bool NUW = Op->getFlags().hasNoUnsignedWrap();
3537 bool NSW = Op->getFlags().hasNoSignedWrap();
3538
3539 bool ShAmtNonZero = Known2.isNonZero();
3540
3541 Known = KnownBits::shl(Known, Known2, NUW, NSW, ShAmtNonZero);
3542
3543 // Minimum shift low bits are known zero.
3544 if (const APInt *ShMinAmt =
3546 Known.Zero.setLowBits(ShMinAmt->getZExtValue());
3547 break;
3548 }
3549 case ISD::SRL:
3550 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3551 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3552 Known = KnownBits::lshr(Known, Known2, /*ShAmtNonZero=*/false,
3553 Op->getFlags().hasExact());
3554
3555 // Minimum shift high bits are known zero.
3556 if (const APInt *ShMinAmt =
3558 Known.Zero.setHighBits(ShMinAmt->getZExtValue());
3559 break;
3560 case ISD::SRA:
3561 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3562 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3563 Known = KnownBits::ashr(Known, Known2, /*ShAmtNonZero=*/false,
3564 Op->getFlags().hasExact());
3565 break;
3566 case ISD::FSHL:
3567 case ISD::FSHR:
3568 if (ConstantSDNode *C = isConstOrConstSplat(Op.getOperand(2), DemandedElts)) {
3569 unsigned Amt = C->getAPIntValue().urem(BitWidth);
3570
3571 // For fshl, 0-shift returns the 1st arg.
3572 // For fshr, 0-shift returns the 2nd arg.
3573 if (Amt == 0) {
3574 Known = computeKnownBits(Op.getOperand(Opcode == ISD::FSHL ? 0 : 1),
3575 DemandedElts, Depth + 1);
3576 break;
3577 }
3578
3579 // fshl: (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
3580 // fshr: (X << (BW - (Z % BW))) | (Y >> (Z % BW))
3581 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3582 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3583 if (Opcode == ISD::FSHL) {
3584 Known.One <<= Amt;
3585 Known.Zero <<= Amt;
3586 Known2.One.lshrInPlace(BitWidth - Amt);
3587 Known2.Zero.lshrInPlace(BitWidth - Amt);
3588 } else {
3589 Known.One <<= BitWidth - Amt;
3590 Known.Zero <<= BitWidth - Amt;
3591 Known2.One.lshrInPlace(Amt);
3592 Known2.Zero.lshrInPlace(Amt);
3593 }
3594 Known = Known.unionWith(Known2);
3595 }
3596 break;
3597 case ISD::SHL_PARTS:
3598 case ISD::SRA_PARTS:
3599 case ISD::SRL_PARTS: {
3600 assert((Op.getResNo() == 0 || Op.getResNo() == 1) && "Unknown result");
3601
3602 // Collect lo/hi source values and concatenate.
3603 unsigned LoBits = Op.getOperand(0).getScalarValueSizeInBits();
3604 unsigned HiBits = Op.getOperand(1).getScalarValueSizeInBits();
3605 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3606 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3607 Known = Known2.concat(Known);
3608
3609 // Collect shift amount.
3610 Known2 = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
3611
3612 if (Opcode == ISD::SHL_PARTS)
3613 Known = KnownBits::shl(Known, Known2);
3614 else if (Opcode == ISD::SRA_PARTS)
3615 Known = KnownBits::ashr(Known, Known2);
3616 else // if (Opcode == ISD::SRL_PARTS)
3617 Known = KnownBits::lshr(Known, Known2);
3618
3619 // TODO: Minimum shift low/high bits are known zero.
3620
3621 if (Op.getResNo() == 0)
3622 Known = Known.extractBits(LoBits, 0);
3623 else
3624 Known = Known.extractBits(HiBits, LoBits);
3625 break;
3626 }
3628 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3629 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
3630 Known = Known.sextInReg(EVT.getScalarSizeInBits());
3631 break;
3632 }
3633 case ISD::CTTZ:
3634 case ISD::CTTZ_ZERO_UNDEF: {
3635 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3636 // If we have a known 1, its position is our upper bound.
3637 unsigned PossibleTZ = Known2.countMaxTrailingZeros();
3638 unsigned LowBits = llvm::bit_width(PossibleTZ);
3639 Known.Zero.setBitsFrom(LowBits);
3640 break;
3641 }
3642 case ISD::CTLZ:
3643 case ISD::CTLZ_ZERO_UNDEF: {
3644 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3645 // If we have a known 1, its position is our upper bound.
3646 unsigned PossibleLZ = Known2.countMaxLeadingZeros();
3647 unsigned LowBits = llvm::bit_width(PossibleLZ);
3648 Known.Zero.setBitsFrom(LowBits);
3649 break;
3650 }
3651 case ISD::CTPOP: {
3652 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3653 // If we know some of the bits are zero, they can't be one.
3654 unsigned PossibleOnes = Known2.countMaxPopulation();
3655 Known.Zero.setBitsFrom(llvm::bit_width(PossibleOnes));
3656 break;
3657 }
3658 case ISD::PARITY: {
3659 // Parity returns 0 everywhere but the LSB.
3660 Known.Zero.setBitsFrom(1);
3661 break;
3662 }
3663 case ISD::LOAD: {
3664 LoadSDNode *LD = cast<LoadSDNode>(Op);
3665 const Constant *Cst = TLI->getTargetConstantFromLoad(LD);
3666 if (ISD::isNON_EXTLoad(LD) && Cst) {
3667 // Determine any common known bits from the loaded constant pool value.
3668 Type *CstTy = Cst->getType();
3669 if ((NumElts * BitWidth) == CstTy->getPrimitiveSizeInBits() &&
3670 !Op.getValueType().isScalableVector()) {
3671 // If its a vector splat, then we can (quickly) reuse the scalar path.
3672 // NOTE: We assume all elements match and none are UNDEF.
3673 if (CstTy->isVectorTy()) {
3674 if (const Constant *Splat = Cst->getSplatValue()) {
3675 Cst = Splat;
3676 CstTy = Cst->getType();
3677 }
3678 }
3679 // TODO - do we need to handle different bitwidths?
3680 if (CstTy->isVectorTy() && BitWidth == CstTy->getScalarSizeInBits()) {
3681 // Iterate across all vector elements finding common known bits.
3682 Known.One.setAllBits();
3683 Known.Zero.setAllBits();
3684 for (unsigned i = 0; i != NumElts; ++i) {
3685 if (!DemandedElts[i])
3686 continue;
3687 if (Constant *Elt = Cst->getAggregateElement(i)) {
3688 if (auto *CInt = dyn_cast<ConstantInt>(Elt)) {
3689 const APInt &Value = CInt->getValue();
3690 Known.One &= Value;
3691 Known.Zero &= ~Value;
3692 continue;
3693 }
3694 if (auto *CFP = dyn_cast<ConstantFP>(Elt)) {
3695 APInt Value = CFP->getValueAPF().bitcastToAPInt();
3696 Known.One &= Value;
3697 Known.Zero &= ~Value;
3698 continue;
3699 }
3700 }
3701 Known.One.clearAllBits();
3702 Known.Zero.clearAllBits();
3703 break;
3704 }
3705 } else if (BitWidth == CstTy->getPrimitiveSizeInBits()) {
3706 if (auto *CInt = dyn_cast<ConstantInt>(Cst)) {
3707 Known = KnownBits::makeConstant(CInt->getValue());
3708 } else if (auto *CFP = dyn_cast<ConstantFP>(Cst)) {
3709 Known =
3710 KnownBits::makeConstant(CFP->getValueAPF().bitcastToAPInt());
3711 }
3712 }
3713 }
3714 } else if (Op.getResNo() == 0) {
3715 KnownBits Known0(!LD->getMemoryVT().isScalableVT()
3716 ? LD->getMemoryVT().getFixedSizeInBits()
3717 : BitWidth);
3718 EVT VT = Op.getValueType();
3719 // Fill in any known bits from range information. There are 3 types being
3720 // used. The results VT (same vector elt size as BitWidth), the loaded
3721 // MemoryVT (which may or may not be vector) and the range VTs original
3722 // type. The range matadata needs the full range (i.e
3723 // MemoryVT().getSizeInBits()), which is truncated to the correct elt size
3724 // if it is know. These are then extended to the original VT sizes below.
3725 if (const MDNode *MD = LD->getRanges()) {
3727 if (VT.isVector()) {
3728 // Handle truncation to the first demanded element.
3729 // TODO: Figure out which demanded elements are covered
3730 if (DemandedElts != 1 || !getDataLayout().isLittleEndian())
3731 break;
3732 Known0 = Known0.trunc(BitWidth);
3733 }
3734 }
3735
3736 if (LD->getMemoryVT().isVector())
3737 Known0 = Known0.trunc(LD->getMemoryVT().getScalarSizeInBits());
3738
3739 // Extend the Known bits from memory to the size of the result.
3740 if (ISD::isZEXTLoad(Op.getNode()))
3741 Known = Known0.zext(BitWidth);
3742 else if (ISD::isSEXTLoad(Op.getNode()))
3743 Known = Known0.sext(BitWidth);
3744 else if (ISD::isEXTLoad(Op.getNode()))
3745 Known = Known0.anyext(BitWidth);
3746 else
3747 Known = Known0;
3748 assert(Known.getBitWidth() == BitWidth);
3749 return Known;
3750 }
3751 break;
3752 }
3754 if (Op.getValueType().isScalableVector())
3755 break;
3756 EVT InVT = Op.getOperand(0).getValueType();
3757 APInt InDemandedElts = DemandedElts.zext(InVT.getVectorNumElements());
3758 Known = computeKnownBits(Op.getOperand(0), InDemandedElts, Depth + 1);
3759 Known = Known.zext(BitWidth);
3760 break;
3761 }
3762 case ISD::ZERO_EXTEND: {
3763 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3764 Known = Known.zext(BitWidth);
3765 break;
3766 }
3768 if (Op.getValueType().isScalableVector())
3769 break;
3770 EVT InVT = Op.getOperand(0).getValueType();
3771 APInt InDemandedElts = DemandedElts.zext(InVT.getVectorNumElements());
3772 Known = computeKnownBits(Op.getOperand(0), InDemandedElts, Depth + 1);
3773 // If the sign bit is known to be zero or one, then sext will extend
3774 // it to the top bits, else it will just zext.
3775 Known = Known.sext(BitWidth);
3776 break;
3777 }
3778 case ISD::SIGN_EXTEND: {
3779 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3780 // If the sign bit is known to be zero or one, then sext will extend
3781 // it to the top bits, else it will just zext.
3782 Known = Known.sext(BitWidth);
3783 break;
3784 }
3786 if (Op.getValueType().isScalableVector())
3787 break;
3788 EVT InVT = Op.getOperand(0).getValueType();
3789 APInt InDemandedElts = DemandedElts.zext(InVT.getVectorNumElements());
3790 Known = computeKnownBits(Op.getOperand(0), InDemandedElts, Depth + 1);
3791 Known = Known.anyext(BitWidth);
3792 break;
3793 }
3794 case ISD::ANY_EXTEND: {
3795 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3796 Known = Known.anyext(BitWidth);
3797 break;
3798 }
3799 case ISD::TRUNCATE: {
3800 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3801 Known = Known.trunc(BitWidth);
3802 break;
3803 }
3804 case ISD::AssertZext: {
3805 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
3807 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3808 Known.Zero |= (~InMask);
3809 Known.One &= (~Known.Zero);
3810 break;
3811 }
3812 case ISD::AssertAlign: {
3813 unsigned LogOfAlign = Log2(cast<AssertAlignSDNode>(Op)->getAlign());
3814 assert(LogOfAlign != 0);
3815
3816 // TODO: Should use maximum with source
3817 // If a node is guaranteed to be aligned, set low zero bits accordingly as
3818 // well as clearing one bits.
3819 Known.Zero.setLowBits(LogOfAlign);
3820 Known.One.clearLowBits(LogOfAlign);
3821 break;
3822 }
3823 case ISD::FGETSIGN:
3824 // All bits are zero except the low bit.
3825 Known.Zero.setBitsFrom(1);
3826 break;
3827 case ISD::ADD:
3828 case ISD::SUB: {
3829 SDNodeFlags Flags = Op.getNode()->getFlags();
3830 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3831 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3833 Op.getOpcode() == ISD::ADD, Flags.hasNoSignedWrap(),
3834 Flags.hasNoUnsignedWrap(), Known, Known2);
3835 break;
3836 }
3837 case ISD::USUBO:
3838 case ISD::SSUBO:
3839 case ISD::USUBO_CARRY:
3840 case ISD::SSUBO_CARRY:
3841 if (Op.getResNo() == 1) {
3842 // If we know the result of a setcc has the top bits zero, use this info.
3843 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
3845 BitWidth > 1)
3846 Known.Zero.setBitsFrom(1);
3847 break;
3848 }
3849 [[fallthrough]];
3850 case ISD::SUBC: {
3851 assert(Op.getResNo() == 0 &&
3852 "We only compute knownbits for the difference here.");
3853
3854 // With USUBO_CARRY and SSUBO_CARRY a borrow bit may be added in.
3855 KnownBits Borrow(1);
3856 if (Opcode == ISD::USUBO_CARRY || Opcode == ISD::SSUBO_CARRY) {
3857 Borrow = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
3858 // Borrow has bit width 1
3859 Borrow = Borrow.trunc(1);
3860 } else {
3861 Borrow.setAllZero();
3862 }
3863
3864 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3865 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3866 Known = KnownBits::computeForSubBorrow(Known, Known2, Borrow);
3867 break;
3868 }
3869 case ISD::UADDO:
3870 case ISD::SADDO:
3871 case ISD::UADDO_CARRY:
3872 case ISD::SADDO_CARRY:
3873 if (Op.getResNo() == 1) {
3874 // If we know the result of a setcc has the top bits zero, use this info.
3875 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
3877 BitWidth > 1)
3878 Known.Zero.setBitsFrom(1);
3879 break;
3880 }
3881 [[fallthrough]];
3882 case ISD::ADDC:
3883 case ISD::ADDE: {
3884 assert(Op.getResNo() == 0 && "We only compute knownbits for the sum here.");
3885
3886 // With ADDE and UADDO_CARRY, a carry bit may be added in.
3887 KnownBits Carry(1);
3888 if (Opcode == ISD::ADDE)
3889 // Can't track carry from glue, set carry to unknown.
3890 Carry.resetAll();
3891 else if (Opcode == ISD::UADDO_CARRY || Opcode == ISD::SADDO_CARRY) {
3892 Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
3893 // Carry has bit width 1
3894 Carry = Carry.trunc(1);
3895 } else {
3896 Carry.setAllZero();
3897 }
3898
3899 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3900 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3901 Known = KnownBits::computeForAddCarry(Known, Known2, Carry);
3902 break;
3903 }
3904 case ISD::UDIV: {
3905 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3906 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3907 Known = KnownBits::udiv(Known, Known2, Op->getFlags().hasExact());
3908 break;
3909 }
3910 case ISD::SDIV: {
3911 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3912 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3913 Known = KnownBits::sdiv(Known, Known2, Op->getFlags().hasExact());
3914 break;
3915 }
3916 case ISD::SREM: {
3917 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3918 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3919 Known = KnownBits::srem(Known, Known2);
3920 break;
3921 }
3922 case ISD::UREM: {
3923 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
3924 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
3925 Known = KnownBits::urem(Known, Known2);
3926 break;
3927 }
3928 case ISD::EXTRACT_ELEMENT: {
3929 Known = computeKnownBits(Op.getOperand(0), Depth+1);
3930 const unsigned Index = Op.getConstantOperandVal(1);
3931 const unsigned EltBitWidth = Op.getValueSizeInBits();
3932
3933 // Remove low part of known bits mask
3934 Known.Zero = Known.Zero.getHiBits(Known.getBitWidth() - Index * EltBitWidth);
3935 Known.One = Known.One.getHiBits(Known.getBitWidth() - Index * EltBitWidth);
3936
3937 // Remove high part of known bit mask
3938 Known = Known.trunc(EltBitWidth);
3939 break;
3940 }
3942 SDValue InVec = Op.getOperand(0);
3943 SDValue EltNo = Op.getOperand(1);
3944 EVT VecVT = InVec.getValueType();
3945 // computeKnownBits not yet implemented for scalable vectors.
3946 if (VecVT.isScalableVector())
3947 break;
3948 const unsigned EltBitWidth = VecVT.getScalarSizeInBits();
3949 const unsigned NumSrcElts = VecVT.getVectorNumElements();
3950
3951 // If BitWidth > EltBitWidth the value is anyext:ed. So we do not know
3952 // anything about the extended bits.
3953 if (BitWidth > EltBitWidth)
3954 Known = Known.trunc(EltBitWidth);
3955
3956 // If we know the element index, just demand that vector element, else for
3957 // an unknown element index, ignore DemandedElts and demand them all.
3958 APInt DemandedSrcElts = APInt::getAllOnes(NumSrcElts);
3959 auto *ConstEltNo = dyn_cast<ConstantSDNode>(EltNo);
3960 if (ConstEltNo && ConstEltNo->getAPIntValue().ult(NumSrcElts))
3961 DemandedSrcElts =
3962 APInt::getOneBitSet(NumSrcElts, ConstEltNo->getZExtValue());
3963
3964 Known = computeKnownBits(InVec, DemandedSrcElts, Depth + 1);
3965 if (BitWidth > EltBitWidth)
3966 Known = Known.anyext(BitWidth);
3967 break;
3968 }
3970 if (Op.getValueType().isScalableVector())
3971 break;
3972
3973 // If we know the element index, split the demand between the
3974 // source vector and the inserted element, otherwise assume we need
3975 // the original demanded vector elements and the value.
3976 SDValue InVec = Op.getOperand(0);
3977 SDValue InVal = Op.getOperand(1);
3978 SDValue EltNo = Op.getOperand(2);
3979 bool DemandedVal = true;
3980 APInt DemandedVecElts = DemandedElts;
3981 auto *CEltNo = dyn_cast<ConstantSDNode>(EltNo);
3982 if (CEltNo && CEltNo->getAPIntValue().ult(NumElts)) {
3983 unsigned EltIdx = CEltNo->getZExtValue();
3984 DemandedVal = !!DemandedElts[EltIdx];
3985 DemandedVecElts.clearBit(EltIdx);
3986 }
3987 Known.One.setAllBits();
3988 Known.Zero.setAllBits();
3989 if (DemandedVal) {
3990 Known2 = computeKnownBits(InVal, Depth + 1);
3991 Known = Known.intersectWith(Known2.zextOrTrunc(BitWidth));
3992 }
3993 if (!!DemandedVecElts) {
3994 Known2 = computeKnownBits(InVec, DemandedVecElts, Depth + 1);
3995 Known = Known.intersectWith(Known2);
3996 }
3997 break;
3998 }
3999 case ISD::BITREVERSE: {
4000 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4001 Known = Known2.reverseBits();
4002 break;
4003 }
4004 case ISD::BSWAP: {
4005 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4006 Known = Known2.byteSwap();
4007 break;
4008 }
4009 case ISD::ABS: {
4010 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4011 Known = Known2.abs();
4012 break;
4013 }
4014 case ISD::USUBSAT: {
4015 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4016 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
4017 Known = KnownBits::usub_sat(Known, Known2);
4018 break;
4019 }
4020 case ISD::UMIN: {
4021 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4022 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
4023 Known = KnownBits::umin(Known, Known2);
4024 break;
4025 }
4026 case ISD::UMAX: {
4027 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4028 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
4029 Known = KnownBits::umax(Known, Known2);
4030 break;
4031 }
4032 case ISD::SMIN:
4033 case ISD::SMAX: {
4034 // If we have a clamp pattern, we know that the number of sign bits will be
4035 // the minimum of the clamp min/max range.
4036 bool IsMax = (Opcode == ISD::SMAX);
4037 ConstantSDNode *CstLow = nullptr, *CstHigh = nullptr;
4038 if ((CstLow = isConstOrConstSplat(Op.getOperand(1), DemandedElts)))
4039 if (Op.getOperand(0).getOpcode() == (IsMax ? ISD::SMIN : ISD::SMAX))
4040 CstHigh =
4041 isConstOrConstSplat(Op.getOperand(0).getOperand(1), DemandedElts);
4042 if (CstLow && CstHigh) {
4043 if (!IsMax)
4044 std::swap(CstLow, CstHigh);
4045
4046 const APInt &ValueLow = CstLow->getAPIntValue();
4047 const APInt &ValueHigh = CstHigh->getAPIntValue();
4048 if (ValueLow.sle(ValueHigh)) {
4049 unsigned LowSignBits = ValueLow.getNumSignBits();
4050 unsigned HighSignBits = ValueHigh.getNumSignBits();
4051 unsigned MinSignBits = std::min(LowSignBits, HighSignBits);
4052 if (ValueLow.isNegative() && ValueHigh.isNegative()) {
4053 Known.One.setHighBits(MinSignBits);
4054 break;
4055 }
4056 if (ValueLow.isNonNegative() && ValueHigh.isNonNegative()) {
4057 Known.Zero.setHighBits(MinSignBits);
4058 break;
4059 }
4060 }
4061 }
4062
4063 Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4064 Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
4065 if (IsMax)
4066 Known = KnownBits::smax(Known, Known2);
4067 else
4068 Known = KnownBits::smin(Known, Known2);
4069
4070 // For SMAX, if CstLow is non-negative we know the result will be
4071 // non-negative and thus all sign bits are 0.
4072 // TODO: There's an equivalent of this for smin with negative constant for
4073 // known ones.
4074 if (IsMax && CstLow) {
4075 const APInt &ValueLow = CstLow->getAPIntValue();
4076 if (ValueLow.isNonNegative()) {
4077 unsigned SignBits = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
4078 Known.Zero.setHighBits(std::min(SignBits, ValueLow.getNumSignBits()));
4079 }
4080 }
4081
4082 break;
4083 }
4084 case ISD::UINT_TO_FP: {
4085 Known.makeNonNegative();
4086 break;
4087 }
4088 case ISD::SINT_TO_FP: {
4089 Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
4090 if (Known2.isNonNegative())
4091 Known.makeNonNegative();
4092 else if (Known2.isNegative())
4093 Known.makeNegative();
4094 break;
4095 }
4096 case ISD::FP_TO_UINT_SAT: {
4097 // FP_TO_UINT_SAT produces an unsigned value that fits in the saturating VT.
4098 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
4100 break;
4101 }
4103 if (Op.getResNo() == 1) {
4104 // The boolean result conforms to getBooleanContents.
4105 // If we know the result of a setcc has the top bits zero, use this info.
4106 // We know that we have an integer-based boolean since these operations
4107 // are only available for integer.
4108 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
4110 BitWidth > 1)
4111 Known.Zero.setBitsFrom(1);
4112 break;
4113 }
4114 [[fallthrough]];
4116 case ISD::ATOMIC_SWAP:
4128 case ISD::ATOMIC_LOAD: {
4129 unsigned MemBits =
4130 cast<AtomicSDNode>(Op)->getMemoryVT().getScalarSizeInBits();
4131 // If we are looking at the loaded value.
4132 if (Op.getResNo() == 0) {
4134 Known.Zero.setBitsFrom(MemBits);
4135 else if (Op->getOpcode() == ISD::ATOMIC_LOAD &&
4136 cast<AtomicSDNode>(Op)->getExtensionType() == ISD::ZEXTLOAD)
4137 Known.Zero.setBitsFrom(MemBits);
4138 }
4139 break;
4140 }
4141 case ISD::FrameIndex:
4143 TLI->computeKnownBitsForFrameIndex(cast<FrameIndexSDNode>(Op)->getIndex(),
4144 Known, getMachineFunction());
4145 break;
4146
4147 default:
4148 if (Opcode < ISD::BUILTIN_OP_END)
4149 break;
4150 [[fallthrough]];
4154 // TODO: Probably okay to remove after audit; here to reduce change size
4155 // in initial enablement patch for scalable vectors
4156 if (Op.getValueType().isScalableVector())
4157 break;
4158
4159 // Allow the target to implement this method for its nodes.
4160 TLI->computeKnownBitsForTargetNode(Op, Known, DemandedElts, *this, Depth);
4161 break;
4162 }
4163
4164 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
4165 return Known;
4166}
4167
4168/// Convert ConstantRange OverflowResult into SelectionDAG::OverflowKind.
4170 switch (OR) {
4178 }
4179 llvm_unreachable("Unknown OverflowResult");
4180}
4181
4184 // X + 0 never overflow
4185 if (isNullConstant(N1))
4186 return OFK_Never;
4187
4188 // If both operands each have at least two sign bits, the addition
4189 // cannot overflow.
4190 if (ComputeNumSignBits(N0) > 1 && ComputeNumSignBits(N1) > 1)
4191 return OFK_Never;
4192
4193 // TODO: Add ConstantRange::signedAddMayOverflow handling.
4194 return OFK_Sometime;
4195}
4196
4199 // X + 0 never overflow
4200 if (isNullConstant(N1))
4201 return OFK_Never;
4202
4203 // mulhi + 1 never overflow
4204 KnownBits N1Known = computeKnownBits(N1);
4205 if (N0.getOpcode() == ISD::UMUL_LOHI && N0.getResNo() == 1 &&
4206 N1Known.getMaxValue().ult(2))
4207 return OFK_Never;
4208
4209 KnownBits N0Known = computeKnownBits(N0);
4210 if (N1.getOpcode() == ISD::UMUL_LOHI && N1.getResNo() == 1 &&
4211 N0Known.getMaxValue().ult(2))
4212 return OFK_Never;
4213
4214 // Fallback to ConstantRange::unsignedAddMayOverflow handling.
4215 ConstantRange N0Range = ConstantRange::fromKnownBits(N0Known, false);
4216 ConstantRange N1Range = ConstantRange::fromKnownBits(N1Known, false);
4217 return mapOverflowResult(N0Range.unsignedAddMayOverflow(N1Range));
4218}
4219
4222 // X - 0 never overflow
4223 if (isNullConstant(N1))
4224 return OFK_Never;
4225
4226 // If both operands each have at least two sign bits, the subtraction
4227 // cannot overflow.
4228 if (ComputeNumSignBits(N0) > 1 && ComputeNumSignBits(N1) > 1)
4229 return OFK_Never;
4230
4231 KnownBits N0Known = computeKnownBits(N0);
4232 KnownBits N1Known = computeKnownBits(N1);
4233 ConstantRange N0Range = ConstantRange::fromKnownBits(N0Known, true);
4234 ConstantRange N1Range = ConstantRange::fromKnownBits(N1Known, true);
4235 return mapOverflowResult(N0Range.signedSubMayOverflow(N1Range));
4236}
4237
4240 // X - 0 never overflow
4241 if (isNullConstant(N1))
4242 return OFK_Never;
4243
4244 KnownBits N0Known = computeKnownBits(N0);
4245 KnownBits N1Known = computeKnownBits(N1);
4246 ConstantRange N0Range = ConstantRange::fromKnownBits(N0Known, false);
4247 ConstantRange N1Range = ConstantRange::fromKnownBits(N1Known, false);
4248 return mapOverflowResult(N0Range.unsignedSubMayOverflow(N1Range));
4249}
4250
4253 // X * 0 and X * 1 never overflow.
4254 if (isNullConstant(N1) || isOneConstant(N1))
4255 return OFK_Never;
4256
4257 KnownBits N0Known = computeKnownBits(N0);
4258 KnownBits N1Known = computeKnownBits(N1);
4259 ConstantRange N0Range = ConstantRange::fromKnownBits(N0Known, false);
4260 ConstantRange N1Range = ConstantRange::fromKnownBits(N1Known, false);
4261 return mapOverflowResult(N0Range.unsignedMulMayOverflow(N1Range));
4262}
4263
4266 // X * 0 and X * 1 never overflow.
4267 if (isNullConstant(N1) || isOneConstant(N1))
4268 return OFK_Never;
4269
4270 // Get the size of the result.
4271 unsigned BitWidth = N0.getScalarValueSizeInBits();
4272
4273 // Sum of the sign bits.
4274 unsigned SignBits = ComputeNumSignBits(N0) + ComputeNumSignBits(N1);
4275
4276 // If we have enough sign bits, then there's no overflow.
4277 if (SignBits > BitWidth + 1)
4278 return OFK_Never;
4279
4280 if (SignBits == BitWidth + 1) {
4281 // The overflow occurs when the true multiplication of the
4282 // the operands is the minimum negative number.
4283 KnownBits N0Known = computeKnownBits(N0);
4284 KnownBits N1Known = computeKnownBits(N1);
4285 // If one of the operands is non-negative, then there's no
4286 // overflow.
4287 if (N0Known.isNonNegative() || N1Known.isNonNegative())
4288 return OFK_Never;
4289 }
4290
4291 return OFK_Sometime;
4292}
4293
4295 if (Depth >= MaxRecursionDepth)
4296 return false; // Limit search depth.
4297
4298 EVT OpVT = Val.getValueType();
4299 unsigned BitWidth = OpVT.getScalarSizeInBits();
4300
4301 // Is the constant a known power of 2?
4303 return C->getAPIntValue().zextOrTrunc(BitWidth).isPowerOf2();
4304 }))
4305 return true;
4306
4307 // A left-shift of a constant one will have exactly one bit set because
4308 // shifting the bit off the end is undefined.
4309 if (Val.getOpcode() == ISD::SHL) {
4310 auto *C = isConstOrConstSplat(Val.getOperand(0));
4311 if (C && C->getAPIntValue() == 1)
4312 return true;
4313 return isKnownToBeAPowerOfTwo(Val.getOperand(0), Depth + 1) &&
4314 isKnownNeverZero(Val, Depth);
4315 }
4316
4317 // Similarly, a logical right-shift of a constant sign-bit will have exactly
4318 // one bit set.
4319 if (Val.getOpcode() == ISD::SRL) {
4320 auto *C = isConstOrConstSplat(Val.getOperand(0));
4321