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