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