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