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