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