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