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