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