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