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