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