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