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