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"
44 #include "llvm/IR/Constant.h"
45 #include "llvm/IR/Constants.h"
46 #include "llvm/IR/DataLayout.h"
48 #include "llvm/IR/DebugLoc.h"
49 #include "llvm/IR/DerivedTypes.h"
50 #include "llvm/IR/Function.h"
51 #include "llvm/IR/GlobalValue.h"
52 #include "llvm/IR/Metadata.h"
53 #include "llvm/IR/Type.h"
54 #include "llvm/IR/Value.h"
55 #include "llvm/Support/Casting.h"
56 #include "llvm/Support/CodeGen.h"
57 #include "llvm/Support/Compiler.h"
58 #include "llvm/Support/Debug.h"
60 #include "llvm/Support/KnownBits.h"
63 #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 
93  DEBUG(
94  dbgs() << Msg;
95  V.getNode()->dump(G);
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().getScalarType() == 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: ", this);
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: ", this);
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: ", this);
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,
1490  [&](int M) { return M < (NElts * 2) && M >= -1; }) &&
1491  "Index out of range");
1492 
1493  // Copy the mask so we can do any needed cleanup.
1494  SmallVector<int, 8> MaskVec(Mask.begin(), Mask.end());
1495 
1496  // Canonicalize shuffle v, v -> v, undef
1497  if (N1 == N2) {
1498  N2 = getUNDEF(VT);
1499  for (int i = 0; i != NElts; ++i)
1500  if (MaskVec[i] >= NElts) MaskVec[i] -= NElts;
1501  }
1502 
1503  // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1504  if (N1.isUndef())
1505  commuteShuffle(N1, N2, MaskVec);
1506 
1507  // If shuffling a splat, try to blend the splat instead. We do this here so
1508  // that even when this arises during lowering we don't have to re-handle it.
1509  auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1510  BitVector UndefElements;
1511  SDValue Splat = BV->getSplatValue(&UndefElements);
1512  if (!Splat)
1513  return;
1514 
1515  for (int i = 0; i < NElts; ++i) {
1516  if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + NElts))
1517  continue;
1518 
1519  // If this input comes from undef, mark it as such.
1520  if (UndefElements[MaskVec[i] - Offset]) {
1521  MaskVec[i] = -1;
1522  continue;
1523  }
1524 
1525  // If we can blend a non-undef lane, use that instead.
1526  if (!UndefElements[i])
1527  MaskVec[i] = i + Offset;
1528  }
1529  };
1530  if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1531  BlendSplat(N1BV, 0);
1532  if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1533  BlendSplat(N2BV, NElts);
1534 
1535  // Canonicalize all index into lhs, -> shuffle lhs, undef
1536  // Canonicalize all index into rhs, -> shuffle rhs, undef
1537  bool AllLHS = true, AllRHS = true;
1538  bool N2Undef = N2.isUndef();
1539  for (int i = 0; i != NElts; ++i) {
1540  if (MaskVec[i] >= NElts) {
1541  if (N2Undef)
1542  MaskVec[i] = -1;
1543  else
1544  AllLHS = false;
1545  } else if (MaskVec[i] >= 0) {
1546  AllRHS = false;
1547  }
1548  }
1549  if (AllLHS && AllRHS)
1550  return getUNDEF(VT);
1551  if (AllLHS && !N2Undef)
1552  N2 = getUNDEF(VT);
1553  if (AllRHS) {
1554  N1 = getUNDEF(VT);
1555  commuteShuffle(N1, N2, MaskVec);
1556  }
1557  // Reset our undef status after accounting for the mask.
1558  N2Undef = N2.isUndef();
1559  // Re-check whether both sides ended up undef.
1560  if (N1.isUndef() && N2Undef)
1561  return getUNDEF(VT);
1562 
1563  // If Identity shuffle return that node.
1564  bool Identity = true, AllSame = true;
1565  for (int i = 0; i != NElts; ++i) {
1566  if (MaskVec[i] >= 0 && MaskVec[i] != i) Identity = false;
1567  if (MaskVec[i] != MaskVec[0]) AllSame = false;
1568  }
1569  if (Identity && NElts)
1570  return N1;
1571 
1572  // Shuffling a constant splat doesn't change the result.
1573  if (N2Undef) {
1574  SDValue V = N1;
1575 
1576  // Look through any bitcasts. We check that these don't change the number
1577  // (and size) of elements and just changes their types.
1578  while (V.getOpcode() == ISD::BITCAST)
1579  V = V->getOperand(0);
1580 
1581  // A splat should always show up as a build vector node.
1582  if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1583  BitVector UndefElements;
1584  SDValue Splat = BV->getSplatValue(&UndefElements);
1585  // If this is a splat of an undef, shuffling it is also undef.
1586  if (Splat && Splat.isUndef())
1587  return getUNDEF(VT);
1588 
1589  bool SameNumElts =
1591 
1592  // We only have a splat which can skip shuffles if there is a splatted
1593  // value and no undef lanes rearranged by the shuffle.
1594  if (Splat && UndefElements.none()) {
1595  // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1596  // number of elements match or the value splatted is a zero constant.
1597  if (SameNumElts)
1598  return N1;
1599  if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1600  if (C->isNullValue())
1601  return N1;
1602  }
1603 
1604  // If the shuffle itself creates a splat, build the vector directly.
1605  if (AllSame && SameNumElts) {
1606  EVT BuildVT = BV->getValueType(0);
1607  const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1608  SDValue NewBV = getSplatBuildVector(BuildVT, dl, Splatted);
1609 
1610  // We may have jumped through bitcasts, so the type of the
1611  // BUILD_VECTOR may not match the type of the shuffle.
1612  if (BuildVT != VT)
1613  NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1614  return NewBV;
1615  }
1616  }
1617  }
1618 
1620  SDValue Ops[2] = { N1, N2 };
1622  for (int i = 0; i != NElts; ++i)
1623  ID.AddInteger(MaskVec[i]);
1624 
1625  void* IP = nullptr;
1626  if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP))
1627  return SDValue(E, 0);
1628 
1629  // Allocate the mask array for the node out of the BumpPtrAllocator, since
1630  // SDNode doesn't have access to it. This memory will be "leaked" when
1631  // the node is deallocated, but recovered when the NodeAllocator is released.
1632  int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1633  std::copy(MaskVec.begin(), MaskVec.end(), MaskAlloc);
1634 
1635  auto *N = newSDNode<ShuffleVectorSDNode>(VT, dl.getIROrder(),
1636  dl.getDebugLoc(), MaskAlloc);
1637  createOperands(N, Ops);
1638 
1639  CSEMap.InsertNode(N, IP);
1640  InsertNode(N);
1641  return SDValue(N, 0);
1642 }
1643 
1645  MVT VT = SV.getSimpleValueType(0);
1646  SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1648 
1649  SDValue Op0 = SV.getOperand(0);
1650  SDValue Op1 = SV.getOperand(1);
1651  return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, MaskVec);
1652 }
1653 
1657  ID.AddInteger(RegNo);
1658  void *IP = nullptr;
1659  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1660  return SDValue(E, 0);
1661 
1662  auto *N = newSDNode<RegisterSDNode>(RegNo, VT);
1663  CSEMap.InsertNode(N, IP);
1664  InsertNode(N);
1665  return SDValue(N, 0);
1666 }
1667 
1671  ID.AddPointer(RegMask);
1672  void *IP = nullptr;
1673  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1674  return SDValue(E, 0);
1675 
1676  auto *N = newSDNode<RegisterMaskSDNode>(RegMask);
1677  CSEMap.InsertNode(N, IP);
1678  InsertNode(N);
1679  return SDValue(N, 0);
1680 }
1681 
1683  MCSymbol *Label) {
1684  return getLabelNode(ISD::EH_LABEL, dl, Root, Label);
1685 }
1686 
1687 SDValue SelectionDAG::getLabelNode(unsigned Opcode, const SDLoc &dl,
1688  SDValue Root, MCSymbol *Label) {
1690  SDValue Ops[] = { Root };
1691  AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), Ops);
1692  ID.AddPointer(Label);
1693  void *IP = nullptr;
1694  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1695  return SDValue(E, 0);
1696 
1697  auto *N = newSDNode<LabelSDNode>(dl.getIROrder(), dl.getDebugLoc(), Label);
1698  createOperands(N, Ops);
1699 
1700  CSEMap.InsertNode(N, IP);
1701  InsertNode(N);
1702  return SDValue(N, 0);
1703 }
1704 
1706  int64_t Offset,
1707  bool isTarget,
1708  unsigned char TargetFlags) {
1709  unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1710 
1712  AddNodeIDNode(ID, Opc, getVTList(VT), None);
1713  ID.AddPointer(BA);
1714  ID.AddInteger(Offset);
1715  ID.AddInteger(TargetFlags);
1716  void *IP = nullptr;
1717  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1718  return SDValue(E, 0);
1719 
1720  auto *N = newSDNode<BlockAddressSDNode>(Opc, VT, BA, Offset, TargetFlags);
1721  CSEMap.InsertNode(N, IP);
1722  InsertNode(N);
1723  return SDValue(N, 0);
1724 }
1725 
1727  assert((!V || V->getType()->isPointerTy()) &&
1728  "SrcValue is not a pointer?");
1729 
1732  ID.AddPointer(V);
1733 
1734  void *IP = nullptr;
1735  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1736  return SDValue(E, 0);
1737 
1738  auto *N = newSDNode<SrcValueSDNode>(V);
1739  CSEMap.InsertNode(N, IP);
1740  InsertNode(N);
1741  return SDValue(N, 0);
1742 }
1743 
1747  ID.AddPointer(MD);
1748 
1749  void *IP = nullptr;
1750  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1751  return SDValue(E, 0);
1752 
1753  auto *N = newSDNode<MDNodeSDNode>(MD);
1754  CSEMap.InsertNode(N, IP);
1755  InsertNode(N);
1756  return SDValue(N, 0);
1757 }
1758 
1760  if (VT == V.getValueType())
1761  return V;
1762 
1763  return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1764 }
1765 
1767  unsigned SrcAS, unsigned DestAS) {
1768  SDValue Ops[] = {Ptr};
1771  ID.AddInteger(SrcAS);
1772  ID.AddInteger(DestAS);
1773 
1774  void *IP = nullptr;
1775  if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP))
1776  return SDValue(E, 0);
1777 
1778  auto *N = newSDNode<AddrSpaceCastSDNode>(dl.getIROrder(), dl.getDebugLoc(),
1779  VT, SrcAS, DestAS);
1780  createOperands(N, Ops);
1781 
1782  CSEMap.InsertNode(N, IP);
1783  InsertNode(N);
1784  return SDValue(N, 0);
1785 }
1786 
1787 /// getShiftAmountOperand - Return the specified value casted to
1788 /// the target's desired shift amount type.
1790  EVT OpTy = Op.getValueType();
1791  EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1792  if (OpTy == ShTy || OpTy.isVector()) return Op;
1793 
1794  return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
1795 }
1796 
1798  SDLoc dl(Node);
1799  const TargetLowering &TLI = getTargetLoweringInfo();
1800  const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
1801  EVT VT = Node->getValueType(0);
1802  SDValue Tmp1 = Node->getOperand(0);
1803  SDValue Tmp2 = Node->getOperand(1);
1804  unsigned Align = Node->getConstantOperandVal(3);
1805 
1806  SDValue VAListLoad = getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1,
1807  Tmp2, MachinePointerInfo(V));
1808  SDValue VAList = VAListLoad;
1809 
1810  if (Align > TLI.getMinStackArgumentAlignment()) {
1811  assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
1812 
1813  VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1814  getConstant(Align - 1, dl, VAList.getValueType()));
1815 
1816  VAList = getNode(ISD::AND, dl, VAList.getValueType(), VAList,
1817  getConstant(-(int64_t)Align, dl, VAList.getValueType()));
1818  }
1819 
1820  // Increment the pointer, VAList, to the next vaarg
1821  Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1822  getConstant(getDataLayout().getTypeAllocSize(
1823  VT.getTypeForEVT(*getContext())),
1824  dl, VAList.getValueType()));
1825  // Store the incremented VAList to the legalized pointer
1826  Tmp1 =
1827  getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2, MachinePointerInfo(V));
1828  // Load the actual argument out of the pointer VAList
1829  return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo());
1830 }
1831 
1833  SDLoc dl(Node);
1834  const TargetLowering &TLI = getTargetLoweringInfo();
1835  // This defaults to loading a pointer from the input and storing it to the
1836  // output, returning the chain.
1837  const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
1838  const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
1839  SDValue Tmp1 =
1840  getLoad(TLI.getPointerTy(getDataLayout()), dl, Node->getOperand(0),
1841  Node->getOperand(2), MachinePointerInfo(VS));
1842  return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
1843  MachinePointerInfo(VD));
1844 }
1845 
1848  unsigned ByteSize = VT.getStoreSize();
1849  Type *Ty = VT.getTypeForEVT(*getContext());
1850  unsigned StackAlign =
1851  std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1852 
1853  int FrameIdx = MFI.CreateStackObject(ByteSize, StackAlign, false);
1854  return getFrameIndex(FrameIdx, TLI->getFrameIndexTy(getDataLayout()));
1855 }
1856 
1858  unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1859  Type *Ty1 = VT1.getTypeForEVT(*getContext());
1860  Type *Ty2 = VT2.getTypeForEVT(*getContext());
1861  const DataLayout &DL = getDataLayout();
1862  unsigned Align =
1864 
1866  int FrameIdx = MFI.CreateStackObject(Bytes, Align, false);
1867  return getFrameIndex(FrameIdx, TLI->getFrameIndexTy(getDataLayout()));
1868 }
1869 
1871  ISD::CondCode Cond, const SDLoc &dl) {
1872  // These setcc operations always fold.
1873  switch (Cond) {
1874  default: break;
1875  case ISD::SETFALSE:
1876  case ISD::SETFALSE2: return getConstant(0, dl, VT);
1877  case ISD::SETTRUE:
1878  case ISD::SETTRUE2: {
1880  TLI->getBooleanContents(N1->getValueType(0));
1881  return getConstant(
1882  Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1883  VT);
1884  }
1885 
1886  case ISD::SETOEQ:
1887  case ISD::SETOGT:
1888  case ISD::SETOGE:
1889  case ISD::SETOLT:
1890  case ISD::SETOLE:
1891  case ISD::SETONE:
1892  case ISD::SETO:
1893  case ISD::SETUO:
1894  case ISD::SETUEQ:
1895  case ISD::SETUNE:
1896  assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1897  break;
1898  }
1899 
1900  if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1901  const APInt &C2 = N2C->getAPIntValue();
1902  if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1903  const APInt &C1 = N1C->getAPIntValue();
1904 
1905  switch (Cond) {
1906  default: llvm_unreachable("Unknown integer setcc!");
1907  case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1908  case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1909  case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1910  case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1911  case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1912  case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1913  case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1914  case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1915  case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1916  case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1917  }
1918  }
1919  }
1920  if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1921  if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1922  APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1923  switch (Cond) {
1924  default: break;
1925  case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1926  return getUNDEF(VT);
1928  case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1929  case ISD::SETNE: if (R==APFloat::cmpUnordered)
1930  return getUNDEF(VT);
1933  R==APFloat::cmpLessThan, dl, VT);
1934  case ISD::SETLT: if (R==APFloat::cmpUnordered)
1935  return getUNDEF(VT);
1937  case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1938  case ISD::SETGT: if (R==APFloat::cmpUnordered)
1939  return getUNDEF(VT);
1941  case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1942  case ISD::SETLE: if (R==APFloat::cmpUnordered)
1943  return getUNDEF(VT);
1945  case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1946  R==APFloat::cmpEqual, dl, VT);
1947  case ISD::SETGE: if (R==APFloat::cmpUnordered)
1948  return getUNDEF(VT);
1951  R==APFloat::cmpEqual, dl, VT);
1952  case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1953  case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1954  case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1955  R==APFloat::cmpEqual, dl, VT);
1956  case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1957  case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1958  R==APFloat::cmpLessThan, dl, VT);
1960  R==APFloat::cmpUnordered, dl, VT);
1961  case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1962  case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1963  }
1964  } else {
1965  // Ensure that the constant occurs on the RHS.
1966  ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1967  MVT CompVT = N1.getValueType().getSimpleVT();
1968  if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1969  return SDValue();
1970 
1971  return getSetCC(dl, VT, N2, N1, SwappedCond);
1972  }
1973  }
1974 
1975  // Could not fold it.
1976  return SDValue();
1977 }
1978 
1979 /// See if the specified operand can be simplified with the knowledge that only
1980 /// the bits specified by Mask are used.
1982  switch (V.getOpcode()) {
1983  default:
1984  break;
1985  case ISD::Constant: {
1986  const ConstantSDNode *CV = cast<ConstantSDNode>(V.getNode());
1987  assert(CV && "Const value should be ConstSDNode.");
1988  const APInt &CVal = CV->getAPIntValue();
1989  APInt NewVal = CVal & Mask;
1990  if (NewVal != CVal)
1991  return getConstant(NewVal, SDLoc(V), V.getValueType());
1992  break;
1993  }
1994  case ISD::OR:
1995  case ISD::XOR:
1996  // If the LHS or RHS don't contribute bits to the or, drop them.
1997  if (MaskedValueIsZero(V.getOperand(0), Mask))
1998  return V.getOperand(1);
1999  if (MaskedValueIsZero(V.getOperand(1), Mask))
2000  return V.getOperand(0);
2001  break;
2002  case ISD::SRL:
2003  // Only look at single-use SRLs.
2004  if (!V.getNode()->hasOneUse())
2005  break;
2006  if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(V.getOperand(1))) {
2007  // See if we can recursively simplify the LHS.
2008  unsigned Amt = RHSC->getZExtValue();
2009 
2010  // Watch out for shift count overflow though.
2011  if (Amt >= Mask.getBitWidth())
2012  break;
2013  APInt NewMask = Mask << Amt;
2014  if (SDValue SimplifyLHS = GetDemandedBits(V.getOperand(0), NewMask))
2015  return getNode(ISD::SRL, SDLoc(V), V.getValueType(), SimplifyLHS,
2016  V.getOperand(1));
2017  }
2018  break;
2019  case ISD::AND: {
2020  // X & -1 -> X (ignoring bits which aren't demanded).
2022  if (AndVal && Mask.isSubsetOf(AndVal->getAPIntValue()))
2023  return V.getOperand(0);
2024  break;
2025  }
2026  case ISD::ANY_EXTEND: {
2027  SDValue Src = V.getOperand(0);
2028  unsigned SrcBitWidth = Src.getScalarValueSizeInBits();
2029  // Being conservative here - only peek through if we only demand bits in the
2030  // non-extended source (even though the extended bits are technically undef).
2031  if (Mask.getActiveBits() > SrcBitWidth)
2032  break;
2033  APInt SrcMask = Mask.trunc(SrcBitWidth);
2034  if (SDValue DemandedSrc = GetDemandedBits(Src, SrcMask))
2035  return getNode(ISD::ANY_EXTEND, SDLoc(V), V.getValueType(), DemandedSrc);
2036  break;
2037  }
2038  }
2039  return SDValue();
2040 }
2041 
2042 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2043 /// use this predicate to simplify operations downstream.
2044 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2045  unsigned BitWidth = Op.getScalarValueSizeInBits();
2046  return MaskedValueIsZero(Op, APInt::getSignMask(BitWidth), Depth);
2047 }
2048 
2049 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2050 /// this predicate to simplify operations downstream. Mask is known to be zero
2051 /// for bits that V cannot have.
2053  unsigned Depth) const {
2054  KnownBits Known;
2055  computeKnownBits(Op, Known, Depth);
2056  return Mask.isSubsetOf(Known.Zero);
2057 }
2058 
2059 /// Helper function that checks to see if a node is a constant or a
2060 /// build vector of splat constants at least within the demanded elts.
2062  const APInt &DemandedElts) {
2063  if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N))
2064  return CN;
2065  if (N.getOpcode() != ISD::BUILD_VECTOR)
2066  return nullptr;
2067  EVT VT = N.getValueType();
2068  ConstantSDNode *Cst = nullptr;
2069  unsigned NumElts = VT.getVectorNumElements();
2070  assert(DemandedElts.getBitWidth() == NumElts && "Unexpected vector size");
2071  for (unsigned i = 0; i != NumElts; ++i) {
2072  if (!DemandedElts[i])
2073  continue;
2075  if (!C || (Cst && Cst->getAPIntValue() != C->getAPIntValue()) ||
2076  C->getValueType(0) != VT.getScalarType())
2077  return nullptr;
2078  Cst = C;
2079  }
2080  return Cst;
2081 }
2082 
2083 /// If a SHL/SRA/SRL node has a constant or splat constant shift amount that
2084 /// is less than the element bit-width of the shift node, return it.
2086  if (ConstantSDNode *SA = isConstOrConstSplat(V.getOperand(1))) {
2087  // Shifting more than the bitwidth is not valid.
2088  const APInt &ShAmt = SA->getAPIntValue();
2089  if (ShAmt.ult(V.getScalarValueSizeInBits()))
2090  return &ShAmt;
2091  }
2092  return nullptr;
2093 }
2094 
2095 /// Determine which bits of Op are known to be either zero or one and return
2096 /// them in Known. For vectors, the known bits are those that are shared by
2097 /// every vector element.
2099  unsigned Depth) const {
2100  EVT VT = Op.getValueType();
2101  APInt DemandedElts = VT.isVector()
2103  : APInt(1, 1);
2104  computeKnownBits(Op, Known, DemandedElts, Depth);
2105 }
2106 
2107 /// Determine which bits of Op are known to be either zero or one and return
2108 /// them in Known. The DemandedElts argument allows us to only collect the known
2109 /// bits that are shared by the requested vector elements.
2111  const APInt &DemandedElts,
2112  unsigned Depth) const {
2113  unsigned BitWidth = Op.getScalarValueSizeInBits();
2114 
2115  Known = KnownBits(BitWidth); // Don't know anything.
2116 
2117  if (auto *C = dyn_cast<ConstantSDNode>(Op)) {
2118  // We know all of the bits for a constant!
2119  Known.One = C->getAPIntValue();
2120  Known.Zero = ~Known.One;
2121  return;
2122  }
2123  if (auto *C = dyn_cast<ConstantFPSDNode>(Op)) {
2124  // We know all of the bits for a constant fp!
2125  Known.One = C->getValueAPF().bitcastToAPInt();
2126  Known.Zero = ~Known.One;
2127  return;
2128  }
2129 
2130  if (Depth == 6)
2131  return; // Limit search depth.
2132 
2133  KnownBits Known2;
2134  unsigned NumElts = DemandedElts.getBitWidth();
2135 
2136  if (!DemandedElts)
2137  return; // No demanded elts, better to assume we don't know anything.
2138 
2139  unsigned Opcode = Op.getOpcode();
2140  switch (Opcode) {
2141  case ISD::BUILD_VECTOR:
2142  // Collect the known bits that are shared by every demanded vector element.
2143  assert(NumElts == Op.getValueType().getVectorNumElements() &&
2144  "Unexpected vector size");
2145  Known.Zero.setAllBits(); Known.One.setAllBits();
2146  for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
2147  if (!DemandedElts[i])
2148  continue;
2149 
2150  SDValue SrcOp = Op.getOperand(i);
2151  computeKnownBits(SrcOp, Known2, Depth + 1);
2152 
2153  // BUILD_VECTOR can implicitly truncate sources, we must handle this.
2154  if (SrcOp.getValueSizeInBits() != BitWidth) {
2155  assert(SrcOp.getValueSizeInBits() > BitWidth &&
2156  "Expected BUILD_VECTOR implicit truncation");
2157  Known2 = Known2.trunc(BitWidth);
2158  }
2159 
2160  // Known bits are the values that are shared by every demanded element.
2161  Known.One &= Known2.One;
2162  Known.Zero &= Known2.Zero;
2163 
2164  // If we don't know any bits, early out.
2165  if (Known.isUnknown())
2166  break;
2167  }
2168  break;
2169  case ISD::VECTOR_SHUFFLE: {
2170  // Collect the known bits that are shared by every vector element referenced
2171  // by the shuffle.
2172  APInt DemandedLHS(NumElts, 0), DemandedRHS(NumElts, 0);
2173  Known.Zero.setAllBits(); Known.One.setAllBits();
2174  const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(Op);
2175  assert(NumElts == SVN->getMask().size() && "Unexpected vector size");
2176  for (unsigned i = 0; i != NumElts; ++i) {
2177  if (!DemandedElts[i])
2178  continue;
2179 
2180  int M = SVN->getMaskElt(i);
2181  if (M < 0) {
2182  // For UNDEF elements, we don't know anything about the common state of
2183  // the shuffle result.
2184  Known.resetAll();
2185  DemandedLHS.clearAllBits();
2186  DemandedRHS.clearAllBits();
2187  break;
2188  }
2189 
2190  if ((unsigned)M < NumElts)
2191  DemandedLHS.setBit((unsigned)M % NumElts);
2192  else
2193  DemandedRHS.setBit((unsigned)M % NumElts);
2194  }
2195  // Known bits are the values that are shared by every demanded element.
2196  if (!!DemandedLHS) {
2197  SDValue LHS = Op.getOperand(0);
2198  computeKnownBits(LHS, Known2, DemandedLHS, Depth + 1);
2199  Known.One &= Known2.One;
2200  Known.Zero &= Known2.Zero;
2201  }
2202  // If we don't know any bits, early out.
2203  if (Known.isUnknown())
2204  break;
2205  if (!!DemandedRHS) {
2206  SDValue RHS = Op.getOperand(1);
2207  computeKnownBits(RHS, Known2, DemandedRHS, Depth + 1);
2208  Known.One &= Known2.One;
2209  Known.Zero &= Known2.Zero;
2210  }
2211  break;
2212  }
2213  case ISD::CONCAT_VECTORS: {
2214  // Split DemandedElts and test each of the demanded subvectors.
2215  Known.Zero.setAllBits(); Known.One.setAllBits();
2216  EVT SubVectorVT = Op.getOperand(0).getValueType();
2217  unsigned NumSubVectorElts = SubVectorVT.getVectorNumElements();
2218  unsigned NumSubVectors = Op.getNumOperands();
2219  for (unsigned i = 0; i != NumSubVectors; ++i) {
2220  APInt DemandedSub = DemandedElts.lshr(i * NumSubVectorElts);
2221  DemandedSub = DemandedSub.trunc(NumSubVectorElts);
2222  if (!!DemandedSub) {
2223  SDValue Sub = Op.getOperand(i);
2224  computeKnownBits(Sub, Known2, DemandedSub, Depth + 1);
2225  Known.One &= Known2.One;
2226  Known.Zero &= Known2.Zero;
2227  }
2228  // If we don't know any bits, early out.
2229  if (Known.isUnknown())
2230  break;
2231  }
2232  break;
2233  }
2234  case ISD::INSERT_SUBVECTOR: {
2235  // If we know the element index, demand any elements from the subvector and
2236  // the remainder from the src its inserted into, otherwise demand them all.
2237  SDValue Src = Op.getOperand(0);
2238  SDValue Sub = Op.getOperand(1);
2240  unsigned NumSubElts = Sub.getValueType().getVectorNumElements();
2241  if (SubIdx && SubIdx->getAPIntValue().ule(NumElts - NumSubElts)) {
2242  Known.One.setAllBits();
2243  Known.Zero.setAllBits();
2244  uint64_t Idx = SubIdx->getZExtValue();
2245  APInt DemandedSubElts = DemandedElts.extractBits(NumSubElts, Idx);
2246  if (!!DemandedSubElts) {
2247  computeKnownBits(Sub, Known, DemandedSubElts, Depth + 1);
2248  if (Known.isUnknown())
2249  break; // early-out.
2250  }
2251  APInt SubMask = APInt::getBitsSet(NumElts, Idx, Idx + NumSubElts);
2252  APInt DemandedSrcElts = DemandedElts & ~SubMask;
2253  if (!!DemandedSrcElts) {
2254  computeKnownBits(Src, Known2, DemandedSrcElts, Depth + 1);
2255  Known.One &= Known2.One;
2256  Known.Zero &= Known2.Zero;
2257  }
2258  } else {
2259  computeKnownBits(Sub, Known, Depth + 1);
2260  if (Known.isUnknown())
2261  break; // early-out.
2262  computeKnownBits(Src, Known2, Depth + 1);
2263  Known.One &= Known2.One;
2264  Known.Zero &= Known2.Zero;
2265  }
2266  break;
2267  }
2268  case ISD::EXTRACT_SUBVECTOR: {
2269  // If we know the element index, just demand that subvector elements,
2270  // otherwise demand them all.
2271  SDValue Src = Op.getOperand(0);
2273  unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
2274  if (SubIdx && SubIdx->getAPIntValue().ule(NumSrcElts - NumElts)) {
2275  // Offset the demanded elts by the subvector index.
2276  uint64_t Idx = SubIdx->getZExtValue();
2277  APInt DemandedSrc = DemandedElts.zext(NumSrcElts).shl(Idx);
2278  computeKnownBits(Src, Known, DemandedSrc, Depth + 1);
2279  } else {
2280  computeKnownBits(Src, Known, Depth + 1);
2281  }
2282  break;
2283  }
2284  case ISD::BITCAST: {
2285  SDValue N0 = Op.getOperand(0);
2286  EVT SubVT = N0.getValueType();
2287  unsigned SubBitWidth = SubVT.getScalarSizeInBits();
2288 
2289  // Ignore bitcasts from unsupported types.
2290  if (!(SubVT.isInteger() || SubVT.isFloatingPoint()))
2291  break;
2292 
2293  // Fast handling of 'identity' bitcasts.
2294  if (BitWidth == SubBitWidth) {
2295  computeKnownBits(N0, Known, DemandedElts, Depth + 1);
2296  break;
2297  }
2298 
2299  // Support big-endian targets when it becomes useful.
2300  bool IsLE = getDataLayout().isLittleEndian();
2301  if (!IsLE)
2302  break;
2303 
2304  // Bitcast 'small element' vector to 'large element' scalar/vector.
2305  if ((BitWidth % SubBitWidth) == 0) {
2306  assert(N0.getValueType().isVector() && "Expected bitcast from vector");
2307 
2308  // Collect known bits for the (larger) output by collecting the known
2309  // bits from each set of sub elements and shift these into place.
2310  // We need to separately call computeKnownBits for each set of
2311  // sub elements as the knownbits for each is likely to be different.
2312  unsigned SubScale = BitWidth / SubBitWidth;
2313  APInt SubDemandedElts(NumElts * SubScale, 0);
2314  for (unsigned i = 0; i != NumElts; ++i)
2315  if (DemandedElts[i])
2316  SubDemandedElts.setBit(i * SubScale);
2317 
2318  for (unsigned i = 0; i != SubScale; ++i) {
2319  computeKnownBits(N0, Known2, SubDemandedElts.shl(i),
2320  Depth + 1);
2321  Known.One |= Known2.One.zext(BitWidth).shl(SubBitWidth * i);
2322  Known.Zero |= Known2.Zero.zext(BitWidth).shl(SubBitWidth * i);
2323  }
2324  }
2325 
2326  // Bitcast 'large element' scalar/vector to 'small element' vector.
2327  if ((SubBitWidth % BitWidth) == 0) {
2328  assert(Op.getValueType().isVector() && "Expected bitcast to vector");
2329 
2330  // Collect known bits for the (smaller) output by collecting the known
2331  // bits from the overlapping larger input elements and extracting the
2332  // sub sections we actually care about.
2333  unsigned SubScale = SubBitWidth / BitWidth;
2334  APInt SubDemandedElts(NumElts / SubScale, 0);
2335  for (unsigned i = 0; i != NumElts; ++i)
2336  if (DemandedElts[i])
2337  SubDemandedElts.setBit(i / SubScale);
2338 
2339  computeKnownBits(N0, Known2, SubDemandedElts, Depth + 1);
2340 
2341  Known.Zero.setAllBits(); Known.One.setAllBits();
2342  for (unsigned i = 0; i != NumElts; ++i)
2343  if (DemandedElts[i]) {
2344  unsigned Offset = (i % SubScale) * BitWidth;
2345  Known.One &= Known2.One.lshr(Offset).trunc(BitWidth);
2346  Known.Zero &= Known2.Zero.lshr(Offset).trunc(BitWidth);
2347  // If we don't know any bits, early out.
2348  if (Known.isUnknown())
2349  break;
2350  }
2351  }
2352  break;
2353  }
2354  case ISD::AND:
2355  // If either the LHS or the RHS are Zero, the result is zero.
2356  computeKnownBits(Op.getOperand(1), Known, DemandedElts, Depth + 1);
2357  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2358 
2359  // Output known-1 bits are only known if set in both the LHS & RHS.
2360  Known.One &= Known2.One;
2361  // Output known-0 are known to be clear if zero in either the LHS | RHS.
2362  Known.Zero |= Known2.Zero;
2363  break;
2364  case ISD::OR:
2365  computeKnownBits(Op.getOperand(1), Known, DemandedElts, Depth + 1);
2366  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2367 
2368  // Output known-0 bits are only known if clear in both the LHS & RHS.
2369  Known.Zero &= Known2.Zero;
2370  // Output known-1 are known to be set if set in either the LHS | RHS.
2371  Known.One |= Known2.One;
2372  break;
2373  case ISD::XOR: {
2374  computeKnownBits(Op.getOperand(1), Known, DemandedElts, Depth + 1);
2375  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2376 
2377  // Output known-0 bits are known if clear or set in both the LHS & RHS.
2378  APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
2379  // Output known-1 are known to be set if set in only one of the LHS, RHS.
2380  Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
2381  Known.Zero = KnownZeroOut;
2382  break;
2383  }
2384  case ISD::MUL: {
2385  computeKnownBits(Op.getOperand(1), Known, DemandedElts, Depth + 1);
2386  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2387 
2388  // If low bits are zero in either operand, output low known-0 bits.
2389  // Also compute a conservative estimate for high known-0 bits.
2390  // More trickiness is possible, but this is sufficient for the
2391  // interesting case of alignment computation.
2392  unsigned TrailZ = Known.countMinTrailingZeros() +
2393  Known2.countMinTrailingZeros();
2394  unsigned LeadZ = std::max(Known.countMinLeadingZeros() +
2395  Known2.countMinLeadingZeros(),
2396  BitWidth) - BitWidth;
2397 
2398  Known.resetAll();
2399  Known.Zero.setLowBits(std::min(TrailZ, BitWidth));
2400  Known.Zero.setHighBits(std::min(LeadZ, BitWidth));
2401  break;
2402  }
2403  case ISD::UDIV: {
2404  // For the purposes of computing leading zeros we can conservatively
2405  // treat a udiv as a logical right shift by the power of 2 known to
2406  // be less than the denominator.
2407  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2408  unsigned LeadZ = Known2.countMinLeadingZeros();
2409 
2410  computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1);
2411  unsigned RHSMaxLeadingZeros = Known2.countMaxLeadingZeros();
2412  if (RHSMaxLeadingZeros != BitWidth)
2413  LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSMaxLeadingZeros - 1);
2414 
2415  Known.Zero.setHighBits(LeadZ);
2416  break;
2417  }
2418  case ISD::SELECT:
2419  case ISD::VSELECT:
2420  computeKnownBits(Op.getOperand(2), Known, DemandedElts, Depth+1);
2421  // If we don't know any bits, early out.
2422  if (Known.isUnknown())
2423  break;
2424  computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth+1);
2425 
2426  // Only known if known in both the LHS and RHS.
2427  Known.One &= Known2.One;
2428  Known.Zero &= Known2.Zero;
2429  break;
2430  case ISD::SELECT_CC:
2431  computeKnownBits(Op.getOperand(3), Known, DemandedElts, Depth+1);
2432  // If we don't know any bits, early out.
2433  if (Known.isUnknown())
2434  break;
2435  computeKnownBits(Op.getOperand(2), Known2, DemandedElts, Depth+1);
2436 
2437  // Only known if known in both the LHS and RHS.
2438  Known.One &= Known2.One;
2439  Known.Zero &= Known2.Zero;
2440  break;
2441  case ISD::SMULO:
2442  case ISD::UMULO:
2443  if (Op.getResNo() != 1)
2444  break;
2445  // The boolean result conforms to getBooleanContents.
2446  // If we know the result of a setcc has the top bits zero, use this info.
2447  // We know that we have an integer-based boolean since these operations
2448  // are only available for integer.
2449  if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2451  BitWidth > 1)
2452  Known.Zero.setBitsFrom(1);
2453  break;
2454  case ISD::SETCC:
2455  // If we know the result of a setcc has the top bits zero, use this info.
2456  if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2458  BitWidth > 1)
2459  Known.Zero.setBitsFrom(1);
2460  break;
2461  case ISD::SHL:
2462  if (const APInt *ShAmt = getValidShiftAmountConstant(Op)) {
2463  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2464  Known.Zero <<= *ShAmt;
2465  Known.One <<= *ShAmt;
2466  // Low bits are known zero.
2467  Known.Zero.setLowBits(ShAmt->getZExtValue());
2468  }
2469  break;
2470  case ISD::SRL:
2471  if (const APInt *ShAmt = getValidShiftAmountConstant(Op)) {
2472  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2473  Known.Zero.lshrInPlace(*ShAmt);
2474  Known.One.lshrInPlace(*ShAmt);
2475  // High bits are known zero.
2476  Known.Zero.setHighBits(ShAmt->getZExtValue());
2477  }
2478  break;
2479  case ISD::SRA:
2480  if (const APInt *ShAmt = getValidShiftAmountConstant(Op)) {
2481  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2482  // Sign extend known zero/one bit (else is unknown).
2483  Known.Zero.ashrInPlace(*ShAmt);
2484  Known.One.ashrInPlace(*ShAmt);
2485  }
2486  break;
2487  case ISD::SIGN_EXTEND_INREG: {
2488  EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2489  unsigned EBits = EVT.getScalarSizeInBits();
2490 
2491  // Sign extension. Compute the demanded bits in the result that are not
2492  // present in the input.
2493  APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2494 
2495  APInt InSignMask = APInt::getSignMask(EBits);
2496  APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2497 
2498  // If the sign extended bits are demanded, we know that the sign
2499  // bit is demanded.
2500  InSignMask = InSignMask.zext(BitWidth);
2501  if (NewBits.getBoolValue())
2502  InputDemandedBits |= InSignMask;
2503 
2504  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2505  Known.One &= InputDemandedBits;
2506  Known.Zero &= InputDemandedBits;
2507 
2508  // If the sign bit of the input is known set or clear, then we know the
2509  // top bits of the result.
2510  if (Known.Zero.intersects(InSignMask)) { // Input sign bit known clear
2511  Known.Zero |= NewBits;
2512  Known.One &= ~NewBits;
2513  } else if (Known.One.intersects(InSignMask)) { // Input sign bit known set
2514  Known.One |= NewBits;
2515  Known.Zero &= ~NewBits;
2516  } else { // Input sign bit unknown
2517  Known.Zero &= ~NewBits;
2518  Known.One &= ~NewBits;
2519  }
2520  break;
2521  }
2522  case ISD::CTTZ:
2523  case ISD::CTTZ_ZERO_UNDEF: {
2524  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2525  // If we have a known 1, its position is our upper bound.
2526  unsigned PossibleTZ = Known2.countMaxTrailingZeros();
2527  unsigned LowBits = Log2_32(PossibleTZ) + 1;
2528  Known.Zero.setBitsFrom(LowBits);
2529  break;
2530  }
2531  case ISD::CTLZ:
2532  case ISD::CTLZ_ZERO_UNDEF: {
2533  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2534  // If we have a known 1, its position is our upper bound.
2535  unsigned PossibleLZ = Known2.countMaxLeadingZeros();
2536  unsigned LowBits = Log2_32(PossibleLZ) + 1;
2537  Known.Zero.setBitsFrom(LowBits);
2538  break;
2539  }
2540  case ISD::CTPOP: {
2541  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2542  // If we know some of the bits are zero, they can't be one.
2543  unsigned PossibleOnes = Known2.countMaxPopulation();
2544  Known.Zero.setBitsFrom(Log2_32(PossibleOnes) + 1);
2545  break;
2546  }
2547  case ISD::LOAD: {
2548  LoadSDNode *LD = cast<LoadSDNode>(Op);
2549  // If this is a ZEXTLoad and we are looking at the loaded value.
2550  if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2551  EVT VT = LD->getMemoryVT();
2552  unsigned MemBits = VT.getScalarSizeInBits();
2553  Known.Zero.setBitsFrom(MemBits);
2554  } else if (const MDNode *Ranges = LD->getRanges()) {
2555  if (LD->getExtensionType() == ISD::NON_EXTLOAD)
2556  computeKnownBitsFromRangeMetadata(*Ranges, Known);
2557  }
2558  break;
2559  }
2561  EVT InVT = Op.getOperand(0).getValueType();
2562  APInt InDemandedElts = DemandedElts.zext(InVT.getVectorNumElements());
2563  computeKnownBits(Op.getOperand(0), Known, InDemandedElts, Depth + 1);
2564  Known = Known.zext(BitWidth);
2565  Known.Zero.setBitsFrom(InVT.getScalarSizeInBits());
2566  break;
2567  }
2568  case ISD::ZERO_EXTEND: {
2569  EVT InVT = Op.getOperand(0).getValueType();
2570  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2571  Known = Known.zext(BitWidth);
2572  Known.Zero.setBitsFrom(InVT.getScalarSizeInBits());
2573  break;
2574  }
2575  // TODO ISD::SIGN_EXTEND_VECTOR_INREG
2576  case ISD::SIGN_EXTEND: {
2577  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2578  // If the sign bit is known to be zero or one, then sext will extend
2579  // it to the top bits, else it will just zext.
2580  Known = Known.sext(BitWidth);
2581  break;
2582  }
2583  case ISD::ANY_EXTEND: {
2584  computeKnownBits(Op.getOperand(0), Known, Depth+1);
2585  Known = Known.zext(BitWidth);
2586  break;
2587  }
2588  case ISD::TRUNCATE: {
2589  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2590  Known = Known.trunc(BitWidth);
2591  break;
2592  }
2593  case ISD::AssertZext: {
2594  EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2595  APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2596  computeKnownBits(Op.getOperand(0), Known, Depth+1);
2597  Known.Zero |= (~InMask);
2598  Known.One &= (~Known.Zero);
2599  break;
2600  }
2601  case ISD::FGETSIGN:
2602  // All bits are zero except the low bit.
2603  Known.Zero.setBitsFrom(1);
2604  break;
2605  case ISD::USUBO:
2606  case ISD::SSUBO:
2607  if (Op.getResNo() == 1) {
2608  // If we know the result of a setcc has the top bits zero, use this info.
2609  if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2611  BitWidth > 1)
2612  Known.Zero.setBitsFrom(1);
2613  break;
2614  }
2616  case ISD::SUB:
2617  case ISD::SUBC: {
2618  if (ConstantSDNode *CLHS = isConstOrConstSplat(Op.getOperand(0))) {
2619  // We know that the top bits of C-X are clear if X contains less bits
2620  // than C (i.e. no wrap-around can happen). For example, 20-X is
2621  // positive if we can prove that X is >= 0 and < 16.
2622  if (CLHS->getAPIntValue().isNonNegative()) {
2623  unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2624  // NLZ can't be BitWidth with no sign bit
2625  APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2626  computeKnownBits(Op.getOperand(1), Known2, DemandedElts,
2627  Depth + 1);
2628 
2629  // If all of the MaskV bits are known to be zero, then we know the
2630  // output top bits are zero, because we now know that the output is
2631  // from [0-C].
2632  if ((Known2.Zero & MaskV) == MaskV) {
2633  unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2634  // Top bits known zero.
2635  Known.Zero.setHighBits(NLZ2);
2636  }
2637  }
2638  }
2639 
2640  // If low bits are know to be zero in both operands, then we know they are
2641  // going to be 0 in the result. Both addition and complement operations
2642  // preserve the low zero bits.
2643  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2644  unsigned KnownZeroLow = Known2.countMinTrailingZeros();
2645  if (KnownZeroLow == 0)
2646  break;
2647 
2648  computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1);
2649  KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
2650  Known.Zero.setLowBits(KnownZeroLow);
2651  break;
2652  }
2653  case ISD::UADDO:
2654  case ISD::SADDO:
2655  case ISD::ADDCARRY:
2656  if (Op.getResNo() == 1) {
2657  // If we know the result of a setcc has the top bits zero, use this info.
2658  if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2660  BitWidth > 1)
2661  Known.Zero.setBitsFrom(1);
2662  break;
2663  }
2665  case ISD::ADD:
2666  case ISD::ADDC:
2667  case ISD::ADDE: {
2668  // Output known-0 bits are known if clear or set in both the low clear bits
2669  // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2670  // low 3 bits clear.
2671  // Output known-0 bits are also known if the top bits of each input are
2672  // known to be clear. For example, if one input has the top 10 bits clear
2673  // and the other has the top 8 bits clear, we know the top 7 bits of the
2674  // output must be clear.
2675  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2676  unsigned KnownZeroHigh = Known2.countMinLeadingZeros();
2677  unsigned KnownZeroLow = Known2.countMinTrailingZeros();
2678 
2679  computeKnownBits(Op.getOperand(1), Known2, DemandedElts,
2680  Depth + 1);
2681  KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros());
2682  KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
2683 
2684  if (Opcode == ISD::ADDE || Opcode == ISD::ADDCARRY) {
2685  // With ADDE and ADDCARRY, a carry bit may be added in, so we can only
2686  // use this information if we know (at least) that the low two bits are
2687  // clear. We then return to the caller that the low bit is unknown but
2688  // that other bits are known zero.
2689  if (KnownZeroLow >= 2)
2690  Known.Zero.setBits(1, KnownZeroLow);
2691  break;
2692  }
2693 
2694  Known.Zero.setLowBits(KnownZeroLow);
2695  if (KnownZeroHigh > 1)
2696  Known.Zero.setHighBits(KnownZeroHigh - 1);
2697  break;
2698  }
2699  case ISD::SREM:
2700  if (ConstantSDNode *Rem = isConstOrConstSplat(Op.getOperand(1))) {
2701  const APInt &RA = Rem->getAPIntValue().abs();
2702  if (RA.isPowerOf2()) {
2703  APInt LowBits = RA - 1;
2704  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2705 
2706  // The low bits of the first operand are unchanged by the srem.
2707  Known.Zero = Known2.Zero & LowBits;
2708  Known.One = Known2.One & LowBits;
2709 
2710  // If the first operand is non-negative or has all low bits zero, then
2711  // the upper bits are all zero.
2712  if (Known2.Zero[BitWidth-1] || ((Known2.Zero & LowBits) == LowBits))
2713  Known.Zero |= ~LowBits;
2714 
2715  // If the first operand is negative and not all low bits are zero, then
2716  // the upper bits are all one.
2717  if (Known2.One[BitWidth-1] && ((Known2.One & LowBits) != 0))
2718  Known.One |= ~LowBits;
2719  assert((Known.Zero & Known.One) == 0&&"Bits known to be one AND zero?");
2720  }
2721  }
2722  break;
2723  case ISD::UREM: {
2724  if (ConstantSDNode *Rem = isConstOrConstSplat(Op.getOperand(1))) {
2725  const APInt &RA = Rem->getAPIntValue();
2726  if (RA.isPowerOf2()) {
2727  APInt LowBits = (RA - 1);
2728  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2729 
2730  // The upper bits are all zero, the lower ones are unchanged.
2731  Known.Zero = Known2.Zero | ~LowBits;
2732  Known.One = Known2.One & LowBits;
2733  break;
2734  }
2735  }
2736 
2737  // Since the result is less than or equal to either operand, any leading
2738  // zero bits in either operand must also exist in the result.
2739  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2740  computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1);
2741 
2742  uint32_t Leaders =
2744  Known.resetAll();
2745  Known.Zero.setHighBits(Leaders);
2746  break;
2747  }
2748  case ISD::EXTRACT_ELEMENT: {
2749  computeKnownBits(Op.getOperand(0), Known, Depth+1);
2750  const unsigned Index = Op.getConstantOperandVal(1);
2751  const unsigned BitWidth = Op.getValueSizeInBits();
2752 
2753  // Remove low part of known bits mask
2754  Known.Zero = Known.Zero.getHiBits(Known.Zero.getBitWidth() - Index * BitWidth);
2755  Known.One = Known.One.getHiBits(Known.One.getBitWidth() - Index * BitWidth);
2756 
2757  // Remove high part of known bit mask
2758  Known = Known.trunc(BitWidth);
2759  break;
2760  }
2761  case ISD::EXTRACT_VECTOR_ELT: {
2762  SDValue InVec = Op.getOperand(0);
2763  SDValue EltNo = Op.getOperand(1);
2764  EVT VecVT = InVec.getValueType();
2765  const unsigned BitWidth = Op.getValueSizeInBits();
2766  const unsigned EltBitWidth = VecVT.getScalarSizeInBits();
2767  const unsigned NumSrcElts = VecVT.getVectorNumElements();
2768  // If BitWidth > EltBitWidth the value is anyext:ed. So we do not know
2769  // anything about the extended bits.
2770  if (BitWidth > EltBitWidth)
2771  Known = Known.trunc(EltBitWidth);
2772  ConstantSDNode *ConstEltNo = dyn_cast<ConstantSDNode>(EltNo);
2773  if (ConstEltNo && ConstEltNo->getAPIntValue().ult(NumSrcElts)) {
2774  // If we know the element index, just demand that vector element.
2775  unsigned Idx = ConstEltNo->getZExtValue();
2776  APInt DemandedElt = APInt::getOneBitSet(NumSrcElts, Idx);
2777  computeKnownBits(InVec, Known, DemandedElt, Depth + 1);
2778  } else {
2779  // Unknown element index, so ignore DemandedElts and demand them all.
2780  computeKnownBits(InVec, Known, Depth + 1);
2781  }
2782  if (BitWidth > EltBitWidth)
2783  Known = Known.zext(BitWidth);
2784  break;
2785  }
2786  case ISD::INSERT_VECTOR_ELT: {
2787  SDValue InVec = Op.getOperand(0);
2788  SDValue InVal = Op.getOperand(1);
2789  SDValue EltNo = Op.getOperand(2);
2790 
2791  ConstantSDNode *CEltNo = dyn_cast<ConstantSDNode>(EltNo);
2792  if (CEltNo && CEltNo->getAPIntValue().ult(NumElts)) {
2793  // If we know the element index, split the demand between the
2794  // source vector and the inserted element.
2795  Known.Zero = Known.One = APInt::getAllOnesValue(BitWidth);
2796  unsigned EltIdx = CEltNo->getZExtValue();
2797 
2798  // If we demand the inserted element then add its common known bits.
2799  if (DemandedElts[EltIdx]) {
2800  computeKnownBits(InVal, Known2, Depth + 1);
2801  Known.One &= Known2.One.zextOrTrunc(Known.One.getBitWidth());
2802  Known.Zero &= Known2.Zero.zextOrTrunc(Known.Zero.getBitWidth());
2803  }
2804 
2805  // If we demand the source vector then add its common known bits, ensuring
2806  // that we don't demand the inserted element.
2807  APInt VectorElts = DemandedElts & ~(APInt::getOneBitSet(NumElts, EltIdx));
2808  if (!!VectorElts) {
2809  computeKnownBits(InVec, Known2, VectorElts, Depth + 1);
2810  Known.One &= Known2.One;
2811  Known.Zero &= Known2.Zero;
2812  }
2813  } else {
2814  // Unknown element index, so ignore DemandedElts and demand them all.
2815  computeKnownBits(InVec, Known, Depth + 1);
2816  computeKnownBits(InVal, Known2, Depth + 1);
2817  Known.One &= Known2.One.zextOrTrunc(Known.One.getBitWidth());
2818  Known.Zero &= Known2.Zero.zextOrTrunc(Known.Zero.getBitWidth());
2819  }
2820  break;
2821  }
2822  case ISD::BITREVERSE: {
2823  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2824  Known.Zero = Known2.Zero.reverseBits();
2825  Known.One = Known2.One.reverseBits();
2826  break;
2827  }
2828  case ISD::BSWAP: {
2829  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2830  Known.Zero = Known2.Zero.byteSwap();
2831  Known.One = Known2.One.byteSwap();
2832  break;
2833  }
2834  case ISD::ABS: {
2835  computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
2836 
2837  // If the source's MSB is zero then we know the rest of the bits already.
2838  if (Known2.isNonNegative()) {
2839  Known.Zero = Known2.Zero;
2840  Known.One = Known2.One;
2841  break;
2842  }
2843 
2844  // We only know that the absolute values's MSB will be zero iff there is
2845  // a set bit that isn't the sign bit (otherwise it could be INT_MIN).
2846  Known2.One.clearSignBit();
2847  if (Known2.One.getBoolValue()) {
2848  Known.Zero = APInt::getSignMask(BitWidth);
2849  break;
2850  }
2851  break;
2852  }
2853  case ISD::UMIN: {
2854  computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1);
2855  computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1);
2856 
2857  // UMIN - we know that the result will have the maximum of the
2858  // known zero leading bits of the inputs.
2859  unsigned LeadZero = Known.countMinLeadingZeros();
2860  LeadZero = std::max(LeadZero, Known2.countMinLeadingZeros());
2861 
2862  Known.Zero &= Known2.Zero;
2863  Known.One &= Known2.One;
2864  Known.Zero.setHighBits(LeadZero);
2865  break;
2866  }
2867  case ISD::UMAX: {
2868  computeKnownBits(Op.getOperand(0), Known, DemandedElts,
2869  Depth + 1);
2870  computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1);
2871 
2872  // UMAX - we know that the result will have the maximum of the
2873  // known one leading bits of the inputs.
2874  unsigned LeadOne = Known.countMinLeadingOnes();
2875  LeadOne = std::max(LeadOne, Known2.countMinLeadingOnes());
2876 
2877  Known.Zero &= Known2.Zero;
2878  Known.One &= Known2.One;
2879  Known.One.setHighBits(LeadOne);
2880  break;
2881  }
2882  case ISD::SMIN:
2883  case ISD::SMAX: {
2884  computeKnownBits(Op.getOperand(0), Known, DemandedElts,
2885  Depth + 1);
2886  // If we don't know any bits, early out.
2887  if (Known.isUnknown())
2888  break;
2889  computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1);
2890  Known.Zero &= Known2.Zero;
2891  Known.One &= Known2.One;
2892  break;
2893  }
2894  case ISD::FrameIndex:
2895  case ISD::TargetFrameIndex:
2896  TLI->computeKnownBitsForFrameIndex(Op, Known, DemandedElts, *this, Depth);
2897  break;
2898 
2899  default:
2900  if (Opcode < ISD::BUILTIN_OP_END)
2901  break;
2905  case ISD::INTRINSIC_VOID:
2906  // Allow the target to implement this method for its nodes.
2907  TLI->computeKnownBitsForTargetNode(Op, Known, DemandedElts, *this, Depth);
2908  break;
2909  }
2910 
2911  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
2912 }
2913 
2915  SDValue N1) const {
2916  // X + 0 never overflow
2917  if (isNullConstant(N1))
2918  return OFK_Never;
2919 
2920  KnownBits N1Known;
2921  computeKnownBits(N1, N1Known);
2922  if (N1Known.Zero.getBoolValue()) {
2923  KnownBits N0Known;
2924  computeKnownBits(N0, N0Known);
2925 
2926  bool overflow;
2927  (void)(~N0Known.Zero).uadd_ov(~N1Known.Zero, overflow);
2928  if (!overflow)
2929  return OFK_Never;
2930  }
2931 
2932  // mulhi + 1 never overflow
2933  if (N0.getOpcode() == ISD::UMUL_LOHI && N0.getResNo() == 1 &&
2934  (~N1Known.Zero & 0x01) == ~N1Known.Zero)
2935  return OFK_Never;
2936 
2937  if (N1.getOpcode() == ISD::UMUL_LOHI && N1.getResNo() == 1) {
2938  KnownBits N0Known;
2939  computeKnownBits(N0, N0Known);
2940 
2941  if ((~N0Known.Zero & 0x01) == ~N0Known.Zero)
2942  return OFK_Never;
2943  }
2944 
2945  return OFK_Sometime;
2946 }
2947 
2949  EVT OpVT = Val.getValueType();
2950  unsigned BitWidth = OpVT.getScalarSizeInBits();
2951 
2952  // Is the constant a known power of 2?
2953  if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(Val))
2954  return Const->getAPIntValue().zextOrTrunc(BitWidth).isPowerOf2();
2955 
2956  // A left-shift of a constant one will have exactly one bit set because
2957  // shifting the bit off the end is undefined.
2958  if (Val.getOpcode() == ISD::SHL) {
2959  auto *C = isConstOrConstSplat(Val.getOperand(0));
2960  if (C && C->getAPIntValue() == 1)
2961  return true;
2962  }
2963 
2964  // Similarly, a logical right-shift of a constant sign-bit will have exactly
2965  // one bit set.
2966  if (Val.getOpcode() == ISD::SRL) {
2967  auto *C = isConstOrConstSplat(Val.getOperand(0));
2968  if (C && C->getAPIntValue().isSignMask())
2969  return true;
2970  }
2971 
2972  // Are all operands of a build vector constant powers of two?
2973  if (Val.getOpcode() == ISD::BUILD_VECTOR)
2974  if (llvm::all_of(Val->ops(), [BitWidth](SDValue E) {
2975  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(E))
2976  return C->getAPIntValue().zextOrTrunc(BitWidth).isPowerOf2();
2977  return false;
2978  }))
2979  return true;
2980 
2981  // More could be done here, though the above checks are enough
2982  // to handle some common cases.
2983 
2984  // Fall back to computeKnownBits to catch other known cases.
2985  KnownBits Known;
2986  computeKnownBits(Val, Known);
2987  return (Known.countMaxPopulation() == 1) && (Known.countMinPopulation() == 1);
2988 }
2989 
2990 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const {
2991  EVT VT = Op.getValueType();
2992  APInt DemandedElts = VT.isVector()
2994  : APInt(1, 1);
2995  return ComputeNumSignBits(Op, DemandedElts, Depth);
2996 }
2997 
2998 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
2999  unsigned Depth) const {
3000  EVT VT = Op.getValueType();
3001  assert((VT.isInteger() || VT.isFloatingPoint()) && "Invalid VT!");
3002  unsigned VTBits = VT.getScalarSizeInBits();
3003  unsigned NumElts = DemandedElts.getBitWidth();
3004  unsigned Tmp, Tmp2;
3005  unsigned FirstAnswer = 1;
3006 
3007  if (auto *C = dyn_cast<ConstantSDNode>(Op)) {
3008  const APInt &Val = C->getAPIntValue();
3009  return Val.getNumSignBits();
3010  }
3011 
3012  if (Depth == 6)
3013  return 1; // Limit search depth.
3014 
3015  if (!DemandedElts)
3016  return 1; // No demanded elts, better to assume we don't know anything.
3017 
3018  switch (Op.getOpcode()) {
3019  default: break;
3020  case ISD::AssertSext:
3021  Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
3022  return VTBits-Tmp+1;
3023  case ISD::AssertZext:
3024  Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
3025  return VTBits-Tmp;
3026 
3027  case ISD::BUILD_VECTOR:
3028  Tmp = VTBits;
3029  for (unsigned i = 0, e = Op.getNumOperands(); (i < e) && (Tmp > 1); ++i) {
3030  if (!DemandedElts[i])
3031  continue;
3032 
3033  SDValue SrcOp = Op.getOperand(i);
3034  Tmp2 = ComputeNumSignBits(Op.getOperand(i), Depth + 1);
3035 
3036  // BUILD_VECTOR can implicitly truncate sources, we must handle this.
3037  if (SrcOp.getValueSizeInBits() != VTBits) {
3038  assert(SrcOp.getValueSizeInBits() > VTBits &&
3039  "Expected BUILD_VECTOR implicit truncation");
3040  unsigned ExtraBits = SrcOp.getValueSizeInBits() - VTBits;
3041  Tmp2 = (Tmp2 > ExtraBits ? Tmp2 - ExtraBits : 1);
3042  }
3043  Tmp = std::min(Tmp, Tmp2);
3044  }
3045  return Tmp;
3046 
3047  case ISD::VECTOR_SHUFFLE: {
3048  // Collect the minimum number of sign bits that are shared by every vector
3049  // element referenced by the shuffle.
3050  APInt DemandedLHS(NumElts, 0), DemandedRHS(NumElts, 0);
3051  const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(Op);
3052  assert(NumElts == SVN->getMask().size() && "Unexpected vector size");
3053  for (unsigned i = 0; i != NumElts; ++i) {
3054  int M = SVN->getMaskElt(i);
3055  if (!DemandedElts[i])
3056  continue;
3057  // For UNDEF elements, we don't know anything about the common state of
3058  // the shuffle result.
3059  if (M < 0)
3060  return 1;
3061  if ((unsigned)M < NumElts)
3062  DemandedLHS.setBit((unsigned)M % NumElts);
3063  else
3064  DemandedRHS.setBit((unsigned)M % NumElts);
3065  }
3067  if (!!DemandedLHS)
3068  Tmp = ComputeNumSignBits(Op.getOperand(0), DemandedLHS, Depth + 1);
3069  if (!!DemandedRHS) {
3070  Tmp2 = ComputeNumSignBits(Op.getOperand(1), DemandedRHS, Depth + 1);
3071  Tmp = std::min(Tmp, Tmp2);
3072  }
3073  // If we don't know anything, early out and try computeKnownBits fall-back.
3074  if (Tmp == 1)
3075  break;
3076  assert(Tmp <= VTBits && "Failed to determine minimum sign bits");
3077  return Tmp;
3078  }
3079 
3080  case ISD::BITCAST: {
3081  SDValue N0 = Op.getOperand(0);
3082  EVT SrcVT = N0.getValueType();
3083  unsigned SrcBits = SrcVT.getScalarSizeInBits();
3084 
3085  // Ignore bitcasts from unsupported types..
3086  if (!(SrcVT.isInteger() || SrcVT.isFloatingPoint()))
3087  break;
3088 
3089  // Fast handling of 'identity' bitcasts.
3090  if (VTBits == SrcBits)
3091  return ComputeNumSignBits(N0, DemandedElts, Depth + 1);
3092 
3093  // Bitcast 'large element' scalar/vector to 'small element' vector.
3094  // TODO: Handle cases other than 'sign splat' when we have a use case.
3095  // Requires handling of DemandedElts and Endianness.
3096  if ((SrcBits % VTBits) == 0) {
3097  assert(Op.getValueType().isVector() && "Expected bitcast to vector");
3098  Tmp = ComputeNumSignBits(N0, Depth + 1);
3099  if (Tmp == SrcBits)
3100  return VTBits;
3101  }
3102  break;
3103  }
3104 
3105  case ISD::SIGN_EXTEND:
3106  Tmp = VTBits - Op.getOperand(0).getScalarValueSizeInBits();
3107  return ComputeNumSignBits(Op.getOperand(0), DemandedElts, Depth+1) + Tmp;
3109  // Max of the input and what this extends.
3110  Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarSizeInBits();
3111  Tmp = VTBits-Tmp+1;
3112  Tmp2 = ComputeNumSignBits(Op.getOperand(0), DemandedElts, Depth+1);
3113  return std::max(Tmp, Tmp2);
3115  SDValue Src = Op.getOperand(0);
3116  EVT SrcVT = Src.getValueType();
3117  APInt DemandedSrcElts = DemandedElts.zext(SrcVT.getVectorNumElements());
3118  Tmp = VTBits - SrcVT.getScalarSizeInBits();
3119  return ComputeNumSignBits(Src, DemandedSrcElts, Depth+1) + Tmp;
3120  }
3121 
3122  case ISD::SRA:
3123  Tmp = ComputeNumSignBits(Op.getOperand(0), DemandedElts, Depth+1);
3124  // SRA X, C -> adds C sign bits.
3125  if (ConstantSDNode *C =
3126  isConstOrDemandedConstSplat(Op.getOperand(1), DemandedElts)) {
3127  APInt ShiftVal = C->getAPIntValue();
3128  ShiftVal += Tmp;
3129  Tmp = ShiftVal.uge(VTBits) ? VTBits : ShiftVal.getZExtValue();
3130  }
3131  return Tmp;
3132  case ISD::SHL:
3133  if (ConstantSDNode *C =
3134  isConstOrDemandedConstSplat(Op.getOperand(1), DemandedElts)) {
3135  // shl destroys sign bits.
3136  Tmp = ComputeNumSignBits(Op.getOperand(0), DemandedElts, Depth+1);
3137  if (C->getAPIntValue().uge(VTBits) || // Bad shift.
3138  C->getAPIntValue().uge(Tmp)) break; // Shifted all sign bits out.
3139  return Tmp - C->getZExtValue();
3140  }
3141  break;
3142  case ISD::AND:
3143  case ISD::OR:
3144  case ISD::XOR: // NOT is handled here.
3145  // Logical binary ops preserve the number of sign bits at the worst.
3146  Tmp = ComputeNumSignBits(Op.getOperand(0), DemandedElts, Depth+1);
3147  if (Tmp != 1) {
3148  Tmp2 = ComputeNumSignBits(Op.getOperand(1), DemandedElts, Depth+1);
3149  FirstAnswer = std::min(Tmp, Tmp2);
3150  // We computed what we know about the sign bits as our first
3151  // answer. Now proceed to the generic code that uses
3152  // computeKnownBits, and pick whichever answer is better.
3153  }
3154  break;
3155 
3156  case ISD::SELECT:
3157  case ISD::VSELECT:
3158  Tmp = ComputeNumSignBits(Op.getOperand(1), DemandedElts, Depth+1);
3159  if (Tmp == 1) return 1; // Early out.
3160  Tmp2 = ComputeNumSignBits(Op.getOperand(2), DemandedElts, Depth+1);
3161  return std::min(Tmp, Tmp2);
3162  case ISD::SELECT_CC:
3163  Tmp = ComputeNumSignBits(Op.getOperand(2), DemandedElts, Depth+1);
3164  if (Tmp == 1) return 1; // Early out.
3165  Tmp2 = ComputeNumSignBits(Op.getOperand(3), DemandedElts, Depth+1);
3166  return std::min(Tmp, Tmp2);
3167 
3168  case ISD::SMIN:
3169  case ISD::SMAX:
3170  case ISD::UMIN:
3171  case ISD::UMAX:
3172  Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
3173  if (Tmp == 1)
3174  return 1; // Early out.
3175  Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
3176  return std::min(Tmp, Tmp2);
3177  case ISD::SADDO:
3178  case ISD::UADDO:
3179  case ISD::SSUBO:
3180  case ISD::USUBO:
3181  case ISD::SMULO:
3182  case ISD::UMULO:
3183  if (Op.getResNo() != 1)
3184  break;
3185  // The boolean result conforms to getBooleanContents. Fall through.
3186  // If setcc returns 0/-1, all bits are sign bits.
3187  // We know that we have an integer-based boolean since these operations
3188  // are only available for integer.
3189  if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
3191  return VTBits;
3192  break;
3193  case ISD::SETCC:
3194  // If setcc returns 0/-1, all bits are sign bits.
3195  if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
3197  return VTBits;
3198  break;
3199  case ISD::ROTL:
3200  case ISD::ROTR:
3201  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
3202  unsigned RotAmt = C->getAPIntValue().urem(VTBits);
3203 
3204  // Handle rotate right by N like a rotate left by 32-N.
3205  if (Op.getOpcode() == ISD::ROTR)
3206  RotAmt = (VTBits - RotAmt) % VTBits;
3207 
3208  // If we aren't rotating out all of the known-in sign bits, return the
3209  // number that are left. This handles rotl(sext(x), 1) for example.
3210  Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
3211  if (Tmp > (RotAmt + 1)) return (Tmp - RotAmt);
3212  }
3213  break;
3214  case ISD::ADD:
3215  case ISD::ADDC:
3216  // Add can have at most one carry bit. Thus we know that the output
3217  // is, at worst, one more bit than the inputs.
3218  Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
3219  if (Tmp == 1) return 1; // Early out.
3220 
3221  // Special case decrementing a value (ADD X, -1):
3222  if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
3223  if (CRHS->isAllOnesValue()) {
3224  KnownBits Known;
3225  computeKnownBits(Op.getOperand(0), Known, Depth+1);
3226 
3227  // If the input is known to be 0 or 1, the output is 0/-1, which is all
3228  // sign bits set.
3229  if ((Known.Zero | 1).isAllOnesValue())
3230  return VTBits;
3231 
3232  // If we are subtracting one from a positive number, there is no carry
3233  // out of the result.
3234  if (Known.isNonNegative())
3235  return Tmp;
3236  }
3237 
3238  Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
3239  if (Tmp2 == 1) return 1;
3240  return std::min(Tmp, Tmp2)-1;
3241 
3242  case ISD::SUB:
3243  Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
3244  if (Tmp2 == 1) return 1;
3245 
3246  // Handle NEG.
3247  if (ConstantSDNode *CLHS = isConstOrConstSplat(Op.getOperand(0)))
3248  if (CLHS->isNullValue()) {
3249  KnownBits Known;
3250  computeKnownBits(Op.getOperand(1), Known, Depth+1);
3251  // If the input is known to be 0 or 1, the output is 0/-1, which is all
3252  // sign bits set.
3253  if ((Known.Zero | 1).isAllOnesValue())
3254  return VTBits;
3255 
3256  // If the input is known to be positive (the sign bit is known clear),
3257  // the output of the NEG has the same number of sign bits as the input.
3258  if (Known.isNonNegative())
3259  return Tmp2;
3260 
3261  // Otherwise, we treat this like a SUB.
3262  }
3263 
3264  // Sub can have at most one carry bit. Thus we know that the output
3265  // is, at worst, one more bit than the inputs.
3266  Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
3267  if (Tmp == 1) return 1; // Early out.
3268  return std::min(Tmp, Tmp2)-1;
3269  case ISD::TRUNCATE: {
3270  // Check if the sign bits of source go down as far as the truncated value.
3271  unsigned NumSrcBits = Op.getOperand(0).getScalarValueSizeInBits();
3272  unsigned NumSrcSignBits = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
3273  if (NumSrcSignBits > (NumSrcBits - VTBits))
3274  return NumSrcSignBits - (NumSrcBits - VTBits);
3275  break;
3276  }
3277  case ISD::EXTRACT_ELEMENT: {
3278  const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
3279  const int BitWidth = Op.getValueSizeInBits();
3280  const int Items = Op.getOperand(0).getValueSizeInBits() / BitWidth;
3281 
3282  // Get reverse index (starting from 1), Op1 value indexes elements from
3283  // little end. Sign starts at big end.
3284  const int rIndex = Items - 1 - Op.getConstantOperandVal(1);
3285 
3286  // If the sign portion ends in our element the subtraction gives correct
3287  // result. Otherwise it gives either negative or > bitwidth result
3288  return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
3289  }
3290  case ISD::INSERT_VECTOR_ELT: {
3291  SDValue InVec = Op.getOperand(0);
3292  SDValue InVal = Op.getOperand(1);
3293  SDValue EltNo = Op.getOperand(2);
3294  unsigned NumElts = InVec.getValueType().getVectorNumElements();
3295 
3296  ConstantSDNode *CEltNo = dyn_cast<ConstantSDNode>(EltNo);
3297  if (CEltNo && CEltNo->getAPIntValue().ult(NumElts)) {
3298  // If we know the element index, split the demand between the
3299  // source vector and the inserted element.
3300  unsigned EltIdx = CEltNo->getZExtValue();
3301 
3302  // If we demand the inserted element then get its sign bits.
3304  if (DemandedElts[EltIdx]) {
3305  // TODO - handle implicit truncation of inserted elements.
3306  if (InVal.getScalarValueSizeInBits() != VTBits)
3307  break;
3308  Tmp = ComputeNumSignBits(InVal, Depth + 1);
3309  }
3310 
3311  // If we demand the source vector then get its sign bits, and determine
3312  // the minimum.
3313  APInt VectorElts = DemandedElts;
3314  VectorElts.clearBit(EltIdx);
3315  if (!!VectorElts) {
3316  Tmp2 = ComputeNumSignBits(InVec, VectorElts, Depth + 1);
3317  Tmp = std::min(Tmp, Tmp2);
3318  }
3319  } else {
3320  // Unknown element index, so ignore DemandedElts and demand them all.
3321  Tmp = ComputeNumSignBits(InVec, Depth + 1);
3322  Tmp2 = ComputeNumSignBits(InVal, Depth + 1);
3323  Tmp = std::min(Tmp, Tmp2);
3324  }
3325  assert(Tmp <= VTBits && "Failed to determine minimum sign bits");
3326  return Tmp;
3327  }
3328  case ISD::EXTRACT_VECTOR_ELT: {
3329  SDValue InVec = Op.getOperand(0);
3330  SDValue EltNo = Op.getOperand(1);
3331  EVT VecVT = InVec.getValueType();
3332  const unsigned BitWidth = Op.getValueSizeInBits();
3333  const unsigned EltBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
3334  const unsigned NumSrcElts = VecVT.getVectorNumElements();
3335 
3336  // If BitWidth > EltBitWidth the value is anyext:ed, and we do not know
3337  // anything about sign bits. But if the sizes match we can derive knowledge
3338  // about sign bits from the vector operand.
3339  if (BitWidth != EltBitWidth)
3340  break;
3341 
3342  // If we know the element index, just demand that vector element, else for
3343  // an unknown element index, ignore DemandedElts and demand them all.
3344  APInt DemandedSrcElts = APInt::getAllOnesValue(NumSrcElts);
3345  ConstantSDNode *ConstEltNo = dyn_cast<ConstantSDNode>(EltNo);
3346  if (ConstEltNo && ConstEltNo->getAPIntValue().ult(NumSrcElts))
3347  DemandedSrcElts =
3348  APInt::getOneBitSet(NumSrcElts, ConstEltNo->getZExtValue());
3349 
3350  return ComputeNumSignBits(InVec, DemandedSrcElts, Depth + 1);
3351  }
3352  case ISD::EXTRACT_SUBVECTOR: {
3353  // If we know the element index, just demand that subvector elements,
3354  // otherwise demand them all.
3355  SDValue Src = Op.getOperand(0);
3357  unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
3358  if (SubIdx && SubIdx->getAPIntValue().ule(NumSrcElts - NumElts)) {
3359  // Offset the demanded elts by the subvector index.
3360  uint64_t Idx = SubIdx->getZExtValue();
3361  APInt DemandedSrc = DemandedElts.zext(NumSrcElts).shl(Idx);
3362  return ComputeNumSignBits(Src, DemandedSrc, Depth + 1);
3363  }
3364  return ComputeNumSignBits(Src, Depth + 1);
3365  }
3366  case ISD::CONCAT_VECTORS:
3367  // Determine the minimum number of sign bits across all demanded
3368  // elts of the input vectors. Early out if the result is already 1.
3370  EVT SubVectorVT = Op.getOperand(0).getValueType();
3371  unsigned NumSubVectorElts = SubVectorVT.getVectorNumElements();
3372  unsigned NumSubVectors = Op.getNumOperands();
3373  for (unsigned i = 0; (i < NumSubVectors) && (Tmp > 1); ++i) {
3374  APInt DemandedSub = DemandedElts.lshr(i * NumSubVectorElts);
3375  DemandedSub = DemandedSub.trunc(NumSubVectorElts);
3376  if (!DemandedSub)
3377  continue;
3378  Tmp2 = ComputeNumSignBits(Op.getOperand(i), DemandedSub, Depth + 1);
3379  Tmp = std::min(Tmp, Tmp2);
3380  }
3381  assert(Tmp <= VTBits && "Failed to determine minimum sign bits");
3382  return Tmp;
3383  }
3384 
3385  // If we are looking at the loaded value of the SDNode.
3386  if (Op.getResNo() == 0) {
3387  // Handle LOADX separately here. EXTLOAD case will fallthrough.
3388  if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
3389  unsigned ExtType = LD->getExtensionType();
3390  switch (ExtType) {
3391  default: break;
3392  case ISD::SEXTLOAD: // '17' bits known
3393  Tmp = LD->getMemoryVT().getScalarSizeInBits();
3394  return VTBits-Tmp+1;
3395  case ISD::ZEXTLOAD: // '16' bits known
3396  Tmp = LD->getMemoryVT().getScalarSizeInBits();
3397  return VTBits-Tmp;
3398  }
3399  }
3400  }
3401 
3402  // Allow the target to implement this method for its nodes.
3403  if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
3406  Op.getOpcode() == ISD::INTRINSIC_VOID) {
3407  unsigned NumBits =
3408  TLI->ComputeNumSignBitsForTargetNode(Op, DemandedElts, *this, Depth);
3409  if (NumBits > 1)
3410  FirstAnswer = std::max(FirstAnswer, NumBits);
3411  }
3412 
3413  // Finally, if we can prove that the top bits of the result are 0's or 1's,
3414  // use this information.
3415  KnownBits Known;
3416  computeKnownBits(Op, Known, DemandedElts, Depth);
3417 
3418  APInt Mask;
3419  if (Known.isNonNegative()) { // sign bit is 0
3420  Mask = Known.Zero;
3421  } else if (Known.isNegative()) { // sign bit is 1;
3422  Mask = Known.One;
3423  } else {
3424  // Nothing known.
3425  return FirstAnswer;
3426  }
3427 
3428  // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
3429  // the number of identical bits in the top of the input value.
3430  Mask = ~Mask;
3431  Mask <<= Mask.getBitWidth()-VTBits;
3432  // Return # leading zeros. We use 'min' here in case Val was zero before
3433  // shifting. We don't want to return '64' as for an i32 "0".
3434  return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
3435 }
3436 
3438  if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
3439  !isa<ConstantSDNode>(Op.getOperand(1)))
3440  return false;
3441 
3442  if (Op.getOpcode() == ISD::OR &&
3444  cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
3445  return false;
3446 
3447  return true;
3448 }
3449 
3451  // If we're told that NaNs won't happen, assume they won't.
3452  if (getTarget().Options.NoNaNsFPMath)
3453  return true;
3454 
3455  if (Op->getFlags().hasNoNaNs())
3456  return true;
3457 
3458  // If the value is a constant, we can obviously see if it is a NaN or not.
3459  if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
3460  return !C->getValueAPF().isNaN();
3461 
3462  // TODO: Recognize more cases here.
3463 
3464  return false;
3465 }
3466 
3468  // If the value is a constant, we can obviously see if it is a zero or not.
3469  if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
3470  return !C->isZero();
3471 
3472  // TODO: Recognize more cases here.
3473  switch (Op.getOpcode()) {
3474  default: break;
3475  case ISD::OR:
3476  if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
3477  return !C->isNullValue();
3478  break;
3479  }
3480 
3481  return false;
3482 }
3483 
3485  // Check the obvious case.
3486  if (A == B) return true;
3487 
3488  // For for negative and positive zero.
3489  if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
3490  if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
3491  if (CA->isZero() && CB->isZero()) return true;
3492 
3493  // Otherwise they may not be equal.
3494  return false;
3495 }
3496 
3498  assert(A.getValueType() == B.getValueType() &&
3499  "Values must have the same type");
3500  KnownBits AKnown, BKnown;
3501  computeKnownBits(A, AKnown);
3502  computeKnownBits(B, BKnown);
3503  return (AKnown.Zero | BKnown.Zero).isAllOnesValue();
3504 }
3505 
3506 static SDValue FoldCONCAT_VECTORS(const SDLoc &DL, EVT VT,
3507  ArrayRef<SDValue> Ops,
3508  SelectionDAG &DAG) {
3509  assert(!Ops.empty() && "Can't concatenate an empty list of vectors!");
3510  assert(llvm::all_of(Ops,
3511  [Ops](SDValue Op) {
3512  return Ops[0].getValueType() == Op.getValueType();
3513  }) &&
3514  "Concatenation of vectors with inconsistent value types!");
3515  assert((Ops.size() * Ops[0].getValueType().getVectorNumElements()) ==
3516  VT.getVectorNumElements() &&
3517  "Incorrect element count in vector concatenation!");
3518 
3519  if (Ops.size() == 1)
3520  return Ops[0];
3521 
3522  // Concat of UNDEFs is UNDEF.
3523  if (llvm::all_of(Ops, [](SDValue Op) { return Op.isUndef(); }))
3524  return DAG.getUNDEF(VT);
3525 
3526  // A CONCAT_VECTOR with all UNDEF/BUILD_VECTOR operands can be
3527  // simplified to one big BUILD_VECTOR.
3528  // FIXME: Add support for SCALAR_TO_VECTOR as well.
3529  EVT SVT = VT.getScalarType();
3531  for (SDValue Op : Ops) {
3532  EVT OpVT = Op.getValueType();
3533  if (Op.isUndef())
3534  Elts.append(OpVT.getVectorNumElements(), DAG.getUNDEF(SVT));
3535  else if (Op.getOpcode() == ISD::BUILD_VECTOR)
3536  Elts.append(Op->op_begin(), Op->op_end());
3537  else
3538  return SDValue();
3539  }
3540 
3541  // BUILD_VECTOR requires all inputs to be of the same type, find the
3542  // maximum type and extend them all.
3543  for (SDValue Op : Elts)
3544  SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3545 
3546  if (SVT.bitsGT(VT.getScalarType()))
3547  for (SDValue &Op : Elts)
3548  Op = DAG.getTargetLoweringInfo().isZExtFree(Op.getValueType(), SVT)
3549  ? DAG.getZExtOrTrunc(Op, DL, SVT)
3550  : DAG.getSExtOrTrunc(Op, DL, SVT);
3551 
3552  SDValue V = DAG.getBuildVector(VT, DL, Elts);
3553  NewSDValueDbgMsg(V, "New node fold concat vectors: ", &DAG);
3554  return V;
3555 }
3556 
3557 /// Gets or creates the specified node.
3558 SDValue SelectionDAG::getNode(unsigned Opcode, const SDLoc &DL, EVT VT) {
3560  AddNodeIDNode(ID, Opcode, getVTList(VT), None);
3561  void *IP = nullptr;
3562  if (SDNode *E = FindNodeOrInsertPos(ID, DL, IP))
3563  return SDValue(E, 0);
3564 
3565  auto *N = newSDNode<SDNode>(Opcode, DL.getIROrder(), DL.getDebugLoc(),
3566  getVTList(VT));
3567  CSEMap.InsertNode(N, IP);
3568 
3569  InsertNode(N);
3570  SDValue V = SDValue(N, 0);
3571  NewSDValueDbgMsg(V, "Creating new node: ", this);
3572  return V;
3573 }
3574 
3575 SDValue SelectionDAG::getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
3576  SDValue Operand, const SDNodeFlags Flags) {
3577  // Constant fold unary operations with an integer constant operand. Even
3578  // opaque constant will be folded, because the folding of unary operations
3579  // doesn't create new constants with different values. Nevertheless, the
3580  // opaque flag is preserved during folding to prevent future folding with
3581  // other constants.
3582  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
3583  const APInt &Val = C->getAPIntValue();
3584  switch (Opcode) {
3585  default: break;
3586  case ISD::SIGN_EXTEND:
3587  return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
3588  C->isTargetOpcode(), C->isOpaque());
3589  case ISD::ANY_EXTEND:
3590  case ISD::ZERO_EXTEND:
3591  case ISD::TRUNCATE:
3592  return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
3593  C->isTargetOpcode(), C->isOpaque());
3594  case ISD::UINT_TO_FP:
3595  case ISD::SINT_TO_FP: {
3598  (void)apf.convertFromAPInt(Val,
3599  Opcode==ISD::SINT_TO_FP,
3601  return getConstantFP(apf, DL, VT);
3602  }
3603  case ISD::BITCAST:
3604  if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
3605  return getConstantFP(APFloat(APFloat::IEEEhalf(), Val), DL, VT);
3606  if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
3607  return getConstantFP(APFloat(APFloat::IEEEsingle(), Val), DL, VT);
3608  if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
3609  return getConstantFP(APFloat(APFloat::IEEEdouble(), Val), DL, VT);
3610  if (VT == MVT::f128 && C->getValueType(0) == MVT::i128)
3611  return getConstantFP(APFloat(APFloat::IEEEquad(), Val), DL, VT);
3612  break;
3613  case ISD::ABS:
3614  return getConstant(Val.abs(), DL, VT, C->isTargetOpcode(),
3615  C->isOpaque());
3616  case ISD::BITREVERSE:
3617  return getConstant(Val.reverseBits(), DL, VT, C->isTargetOpcode(),
3618  C->isOpaque());
3619  case ISD::BSWAP:
3620  return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
3621  C->isOpaque());
3622  case ISD::CTPOP:
3623  return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
3624  C->isOpaque());
3625  case ISD::CTLZ:
3626  case ISD::CTLZ_ZERO_UNDEF:
3627  return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
3628  C->isOpaque());
3629  case ISD::CTTZ:
3630  case ISD::CTTZ_ZERO_UNDEF:
3631  return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
3632  C->isOpaque());
3633  case ISD::FP16_TO_FP: {
3634  bool Ignored;
3635  APFloat FPV(APFloat::IEEEhalf(),
3636  (Val.getBitWidth() == 16) ? Val : Val.trunc(16));
3637 
3638  // This can return overflow, underflow, or inexact; we don't care.
3639  // FIXME need to be more flexible about rounding mode.
3640  (void)FPV.convert(EVTToAPFloatSemantics(VT),
3641  APFloat::rmNearestTiesToEven, &Ignored);
3642  return getConstantFP(FPV, DL, VT);
3643  }
3644  }
3645  }
3646 
3647  // Constant fold unary operations with a floating point constant operand.
3648  if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
3649  APFloat V = C->getValueAPF(); // make copy
3650  switch (Opcode) {
3651  case ISD::FNEG:
3652  V.changeSign();
3653  return getConstantFP(V, DL, VT);
3654  case ISD::FABS:
3655  V.clearSign();
3656  return getConstantFP(V, DL, VT);
3657  case ISD::FCEIL: {
3659  if (fs == APFloat::opOK || fs == APFloat::opInexact)
3660  return getConstantFP(V, DL, VT);
3661  break;
3662  }
3663  case ISD::FTRUNC: {
3665  if (fs == APFloat::opOK || fs == APFloat::opInexact)
3666  return getConstantFP(V, DL, VT);
3667  break;
3668  }
3669  case ISD::FFLOOR: {
3671  if (fs == APFloat::opOK || fs == APFloat::opInexact)
3672  return getConstantFP(V, DL, VT);
3673  break;
3674  }
3675  case ISD::FP_EXTEND: {
3676  bool ignored;
3677  // This can return overflow, underflow, or inexact; we don't care.
3678  // FIXME need to be more flexible about rounding mode.
3679  (void)V.convert(EVTToAPFloatSemantics(VT),
3680  APFloat::rmNearestTiesToEven, &ignored);
3681  return getConstantFP(V, DL, VT);
3682  }
3683  case ISD::FP_TO_SINT:
3684  case ISD::FP_TO_UINT: {
3685  bool ignored;
3686  APSInt IntVal(VT.getSizeInBits(), Opcode == ISD::FP_TO_UINT);
3687  // FIXME need to be more flexible about rounding mode.
3688  APFloat::opStatus s =
3690  if (s == APFloat::opInvalidOp) // inexact is OK, in fact usual
3691  break;
3692  return getConstant(IntVal, DL, VT);
3693  }
3694  case ISD::BITCAST:
3695  if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
3696  return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
3697  else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
3698  return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
3699  else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
3700  return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
3701  break;
3702  case ISD::FP_TO_FP16: {
3703  bool Ignored;
3704  // This can return overflow, underflow, or inexact; we don't care.
3705  // FIXME need to be more flexible about rounding mode.
3706  (void)V.convert(APFloat::IEEEhalf(),
3707  APFloat::rmNearestTiesToEven, &Ignored);
3708  return getConstant(V.bitcastToAPInt(), DL, VT);
3709  }
3710  }
3711  }
3712 
3713  // Constant fold unary operations with a vector integer or float operand.
3714  if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
3715  if (BV->isConstant()) {
3716  switch (Opcode) {
3717  default:
3718  // FIXME: Entirely reasonable to perform folding of other unary
3719  // operations here as the need arises.
3720  break;
3721  case ISD::FNEG:
3722  case ISD::FABS:
3723  case ISD::FCEIL:
3724  case ISD::FTRUNC:
3725  case ISD::FFLOOR:
3726  case ISD::FP_EXTEND:
3727  case ISD::FP_TO_SINT:
3728  case ISD::FP_TO_UINT:
3729  case ISD::TRUNCATE:
3730  case ISD::UINT_TO_FP:
3731  case ISD::SINT_TO_FP:
3732  case ISD::ABS:
3733  case ISD::BITREVERSE:
3734  case ISD::BSWAP:
3735  case ISD::CTLZ:
3736  case ISD::CTLZ_ZERO_UNDEF:
3737  case ISD::CTTZ:
3738  case ISD::CTTZ_ZERO_UNDEF:
3739  case ISD::CTPOP: {
3740  SDValue Ops = { Operand };
3741  if (SDValue Fold = FoldConstantVectorArithmetic(Opcode, DL, VT, Ops))
3742  return Fold;
3743  }
3744  }
3745  }
3746  }
3747 
3748  unsigned OpOpcode = Operand.getNode()->getOpcode();
3749  switch (Opcode) {
3750  case ISD::TokenFactor:
3751  case ISD::MERGE_VALUES:
3752  case ISD::CONCAT_VECTORS:
3753  return Operand; // Factor, merge or concat of one node? No need.
3754  case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3755  case ISD::FP_EXTEND:
3756  assert(VT.isFloatingPoint() &&
3757  Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3758  if (Operand.getValueType() == VT) return Operand; // noop conversion.
3759  assert((!VT.isVector() ||
3760  VT.getVectorNumElements() ==
3761  Operand.getValueType().getVectorNumElements()) &&
3762  "Vector element count mismatch!");
3763  assert(Operand.getValueType().bitsLT(VT) &&
3764  "Invalid fpext node, dst < src!");
3765  if (Operand.isUndef())
3766  return getUNDEF(VT);
3767  break;
3768  case ISD::SIGN_EXTEND:
3769  assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3770  "Invalid SIGN_EXTEND!");
3771  if (Operand.getValueType() == VT) return Operand; // noop extension
3772  assert((!VT.isVector() ||
3773  VT.getVectorNumElements() ==
3774  Operand.getValueType().getVectorNumElements()) &&
3775  "Vector element count mismatch!");
3776  assert(Operand.getValueType().bitsLT(VT) &&
3777  "Invalid sext node, dst < src!");
3778  if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3779  return getNode(OpOpcode, DL, VT, Operand.getOperand(0));
3780  else if (OpOpcode == ISD::UNDEF)
3781  // sext(undef) = 0, because the top bits will all be the same.
3782  return getConstant(0, DL, VT);
3783  break;
3784  case ISD::ZERO_EXTEND:
3785  assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3786  "Invalid ZERO_EXTEND!");
3787  if (Operand.getValueType() == VT) return Operand; // noop extension
3788  assert((!VT.isVector() ||
3789  VT.getVectorNumElements() ==
3790  Operand.getValueType().getVectorNumElements()) &&
3791  "Vector element count mismatch!");
3792  assert(Operand.getValueType().bitsLT(VT) &&
3793  "Invalid zext node, dst < src!");
3794  if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3795  return getNode(ISD::ZERO_EXTEND, DL, VT, Operand.getOperand(0));
3796  else if (OpOpcode == ISD::UNDEF)
3797  // zext(undef) = 0, because the top bits will be zero.
3798  return getConstant(0, DL, VT);
3799  break;
3800  case ISD::ANY_EXTEND:
3801  assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3802  "Invalid ANY_EXTEND!");
3803  if (Operand.getValueType() == VT) return Operand; // noop extension
3804  assert((!VT.isVector() ||
3805  VT.getVectorNumElements() ==
3806  Operand.getValueType().getVectorNumElements()) &&
3807  "Vector element count mismatch!");
3808  assert(Operand.getValueType().bitsLT(VT) &&
3809  "Invalid anyext node, dst < src!");
3810 
3811  if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3812  OpOpcode == ISD::ANY_EXTEND)
3813  // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3814  return getNode(OpOpcode, DL, VT, Operand.getOperand(0));
3815  else if (OpOpcode == ISD::UNDEF)
3816  return getUNDEF(VT);
3817 
3818  // (ext (trunx x)) -> x
3819  if (OpOpcode == ISD::TRUNCATE) {
3820  SDValue OpOp = Operand.getOperand(0);
3821  if (OpOp.getValueType() == VT)
3822  return OpOp;
3823  }
3824  break;
3825  case ISD::TRUNCATE:
3826  assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3827  "Invalid TRUNCATE!");
3828  if (Operand.getValueType() == VT) return Operand; // noop truncate
3829  assert((!VT.isVector() ||
3830  VT.getVectorNumElements() ==
3831  Operand.getValueType().getVectorNumElements()) &&
3832  "Vector element count mismatch!");
3833  assert(Operand.getValueType().bitsGT(VT) &&
3834  "Invalid truncate node, src < dst!");
3835  if (OpOpcode == ISD::TRUNCATE)
3836  return getNode(ISD::TRUNCATE, DL, VT, Operand.getOperand(0));
3837  if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3838  OpOpcode == ISD::ANY_EXTEND) {
3839  // If the source is smaller than the dest, we still need an extend.
3840  if (Operand.getOperand(0).getValueType().getScalarType()
3841  .bitsLT(VT.getScalarType()))
3842  return getNode(OpOpcode, DL, VT, Operand.getOperand(0));
3843  if (Operand.getOperand(0).getValueType().bitsGT(VT))
3844  return getNode(ISD::TRUNCATE, DL, VT, Operand.getOperand(0));
3845  return Operand.getOperand(0);
3846  }
3847  if (OpOpcode == ISD::UNDEF)
3848  return getUNDEF(VT);
3849  break;
3850  case ISD::ABS:
3851  assert(VT.isInteger() && VT == Operand.getValueType() &&
3852  "Invalid ABS!");
3853  if (OpOpcode == ISD::UNDEF)
3854  return getUNDEF(VT);
3855  break;
3856  case ISD::BSWAP:
3857  assert(VT.isInteger() && VT == Operand.getValueType() &&
3858  "Invalid BSWAP!");
3859  assert((VT.getScalarSizeInBits() % 16 == 0) &&
3860  "BSWAP types must be a multiple of 16 bits!");
3861  if (OpOpcode == ISD::UNDEF)
3862  return getUNDEF(VT);
3863  break;
3864  case ISD::BITREVERSE:
3865  assert(VT.isInteger() && VT == Operand.getValueType() &&
3866  "Invalid BITREVERSE!");
3867  if (OpOpcode == ISD::UNDEF)
3868  return getUNDEF(VT);
3869  break;
3870  case ISD::BITCAST:
3871  // Basic sanity checking.
3872  assert(VT.getSizeInBits() == Operand.getValueSizeInBits() &&
3873  "Cannot BITCAST between types of different sizes!");
3874  if (VT == Operand.getValueType()) return Operand; // noop conversion.
3875  if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3876  return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3877  if (OpOpcode == ISD::UNDEF)
3878  return getUNDEF(VT);
3879  break;
3880  case ISD::SCALAR_TO_VECTOR:
3881  assert(VT.isVector() && !Operand.getValueType().isVector() &&
3882  (VT.getVectorElementType() == Operand.getValueType() ||
3883  (VT.getVectorElementType().isInteger() &&
3884  Operand.getValueType().isInteger() &&
3885  VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3886  "Illegal SCALAR_TO_VECTOR node!");
3887  if (OpOpcode == ISD::UNDEF)
3888  return getUNDEF(VT);
3889  // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3890  if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3891  isa<ConstantSDNode>(Operand.getOperand(1)) &&
3892  Operand.getConstantOperandVal(1) == 0 &&
3893  Operand.getOperand(0).getValueType() == VT)
3894  return Operand.getOperand(0);
3895  break;
3896  case ISD::FNEG:
3897  // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3898  if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3899  // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3900  return getNode(ISD::FSUB, DL, VT, Operand.getOperand(1),
3901  Operand.getOperand(0), Operand.getNode()->getFlags());
3902  if (OpOpcode == ISD::FNEG) // --X -> X
3903  return Operand.getOperand(0);
3904  break;
3905  case ISD::FABS:
3906  if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3907  return getNode(ISD::FABS, DL, VT, Operand.getOperand(0));
3908  break;
3909  }
3910 
3911  SDNode *N;
3912  SDVTList VTs = getVTList(VT);
3913  SDValue Ops[] = {Operand};
3914  if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3916  AddNodeIDNode(ID, Opcode, VTs, Ops);
3917  void *IP = nullptr;
3918  if (SDNode *E = FindNodeOrInsertPos(ID, DL, IP)) {
3919  E->intersectFlagsWith(Flags);
3920  return SDValue(E, 0);
3921  }
3922 
3923  N = newSDNode<SDNode>(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs);
3924  N->setFlags(Flags);
3925  createOperands(N, Ops);
3926  CSEMap.InsertNode(N, IP);
3927  } else {
3928  N = newSDNode<SDNode>(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs);
3929  createOperands(N, Ops);
3930  }
3931 
3932  InsertNode(N);
3933  SDValue V = SDValue(N, 0);
3934  NewSDValueDbgMsg(V, "Creating new node: ", this);
3935  return V;
3936 }
3937 
3938 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3939  const APInt &C2) {
3940  switch (Opcode) {
3941  case ISD::ADD: return std::make_pair(C1 + C2, true);
3942  case ISD::SUB: return std::make_pair(C1 - C2, true);
3943  case ISD::MUL: return std::make_pair(C1 * C2, true);
3944  case ISD::AND: return std::make_pair(C1 & C2, true);
3945  case ISD::OR: return std::make_pair(C1 | C2, true);
3946  case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3947  case ISD::SHL: return std::make_pair(C1 << C2, true);
3948  case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3949  case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3950  case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3951  case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3952  case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3953  case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3954  case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3955  case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3956  case ISD::UDIV:
3957  if (!C2.getBoolValue())
3958  break;
3959  return std::make_pair(C1.udiv(C2), true);
3960  case ISD::UREM:
3961  if (!C2.getBoolValue())
3962  break;
3963  return std::make_pair(C1.urem(C2), true);
3964  case ISD::SDIV:
3965  if (!C2.getBoolValue())
3966  break;
3967  return std::make_pair(C1.sdiv(C2), true);
3968  case ISD::SREM:
3969  if (!C2.getBoolValue())
3970  break;
3971  return std::make_pair(C1.srem(C2), true);
3972  }
3973  return std::make_pair(APInt(1, 0), false);
3974 }
3975 
3977  EVT VT, const ConstantSDNode *Cst1,
3978  const ConstantSDNode *Cst2) {
3979  if (Cst1->isOpaque() || Cst2->isOpaque())
3980  return SDValue();
3981 
3982  std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3983  Cst2->getAPIntValue());
3984  if (!Folded.second)
3985  return SDValue();
3986  return getConstant(Folded.first, DL, VT);
3987 }
3988 
3990  const GlobalAddressSDNode *GA,
3991  const SDNode *N2) {
3992  if (GA->getOpcode() != ISD::GlobalAddress)
3993  return SDValue();
3994  if (!TLI->isOffsetFoldingLegal(GA))
3995  return SDValue();
3996  const ConstantSDNode *Cst2 = dyn_cast<ConstantSDNode>(N2);
3997  if (!Cst2)
3998  return SDValue();
3999  int64_t Offset = Cst2->getSExtValue();
4000  switch (Opcode) {
4001  case ISD::ADD: break;
4002  case ISD::SUB: Offset = -uint64_t(Offset); break;
4003  default: return SDValue();
4004  }
4005  return getGlobalAddress(GA->getGlobal(), SDLoc(Cst2), VT,
4006  GA->getOffset() + uint64_t(Offset));
4007 }
4008 
4009 bool SelectionDAG::isUndef(unsigned Opcode, ArrayRef<SDValue> Ops) {
4010  switch (Opcode) {
4011  case ISD::SDIV:
4012  case ISD::UDIV:
4013  case ISD::SREM:
4014  case ISD::UREM: {
4015  // If a divisor is zero/undef or any element of a divisor vector is
4016  // zero/undef, the whole op is undef.
4017  assert(Ops.size() == 2 && "Div/rem should have 2 operands");
4018  SDValue Divisor = Ops[1];
4019  if (Divisor.isUndef() || isNullConstant(Divisor))
4020  return true;
4021 
4022  return ISD::isBuildVectorOfConstantSDNodes(Divisor.getNode()) &&
4023  llvm::any_of(Divisor->op_values(),
4024  [](SDValue V) { return V.isUndef() ||
4025  isNullConstant(V); });
4026  // TODO: Handle signed overflow.
4027  }
4028  // TODO: Handle oversized shifts.
4029  default:
4030  return false;
4031  }
4032 }
4033 
4035  EVT VT, SDNode *Cst1,
4036  SDNode *Cst2) {
4037  // If the opcode is a target-specific ISD node, there's nothing we can
4038  // do here and the operand rules may not line up with the below, so
4039  // bail early.
4040  if (Opcode >= ISD::BUILTIN_OP_END)
4041  return SDValue();
4042 
4043  if (isUndef(Opcode, {SDValue(Cst1, 0), SDValue(Cst2, 0)}))
4044  return getUNDEF(VT);
4045 
4046  // Handle the case of two scalars.
4047  if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
4048  if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
4049  SDValue Folded = FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2);
4050  assert((!Folded || !VT.isVector()) &&
4051  "Can't fold vectors ops with scalar operands");
4052  return Folded;
4053  }
4054  }
4055 
4056  // fold (add Sym, c) -> Sym+c
4057  if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Cst1))
4058  return FoldSymbolOffset(Opcode, VT, GA, Cst2);
4059  if (TLI->isCommutativeBinOp(Opcode))
4060  if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Cst2))
4061  return FoldSymbolOffset(Opcode, VT, GA, Cst1);
4062 
4063  // For vectors extract each constant element into Inputs so we can constant
4064  // fold them individually.
4067  if (!BV1 || !BV2)
4068  return SDValue();
4069 
4070  assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
4071 
4072  EVT SVT = VT.getScalarType();
4073  EVT LegalSVT = SVT;
4074  if (NewNodesMustHaveLegalTypes && LegalSVT.isInteger()) {
4075  LegalSVT = TLI->getTypeToTransformTo(*getContext(), LegalSVT);
4076  if (LegalSVT.bitsLT(SVT))
4077  return SDValue();
4078  }
4079  SmallVector<SDValue, 4> Outputs;
4080  for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
4081  SDValue V1 = BV1->getOperand(I);
4082  SDValue V2 = BV2->getOperand(I);
4083 
4084  if (SVT.isInteger()) {
4085  if (V1->getValueType(0).bitsGT(SVT))
4086  V1 = getNode(ISD::TRUNCATE, DL, SVT, V1);
4087  if (V2->getValueType(0).bitsGT(SVT))
4088  V2 = getNode(ISD::TRUNCATE, DL, SVT, V2);
4089  }
4090 
4091  if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
4092  return SDValue();
4093 
4094  // Fold one vector element.
4095  SDValue ScalarResult = getNode(Opcode, DL, SVT, V1, V2);
4096  if (LegalSVT != SVT)
4097  ScalarResult = getNode(ISD::SIGN_EXTEND, DL, LegalSVT, ScalarResult);
4098 
4099  // Scalar folding only succeeded if the result is a constant or UNDEF.
4100  if (!ScalarResult.isUndef() && ScalarResult.getOpcode() != ISD::Constant &&
4101  ScalarResult.getOpcode() != ISD::ConstantFP)
4102  return SDValue();
4103  Outputs.push_back(ScalarResult);
4104  }
4105 
4106  assert(VT.getVectorNumElements() == Outputs.size() &&
4107  "Vector size mismatch!");
4108 
4109  // We may have a vector type but a scalar result. Create a splat.
4110  Outputs.resize(VT.getVectorNumElements(), Outputs.back());
4111 
4112  // Build a big vector out of the scalar elements we generated.
4113  return getBuildVector(VT, SDLoc(), Outputs);
4114 }
4115 
4116 // TODO: Merge with FoldConstantArithmetic
4118  const SDLoc &DL, EVT VT,
4119  ArrayRef<SDValue> Ops,
4120  const SDNodeFlags Flags) {
4121  // If the opcode is a target-specific ISD node, there's nothing we can
4122  // do here and the operand rules may not line up with the below, so
4123  // bail early.
4124  if (Opcode >= ISD::BUILTIN_OP_END)
4125  return SDValue();
4126 
4127  if (isUndef(Opcode, Ops))
4128  return getUNDEF(VT);
4129 
4130  // We can only fold vectors - maybe merge with FoldConstantArithmetic someday?
4131  if (!VT.isVector())
4132  return SDValue();
4133 
4134  unsigned NumElts = VT.getVectorNumElements();
4135 
4136  auto IsScalarOrSameVectorSize = [&](const SDValue &Op) {
4137  return !Op.getValueType().isVector() ||
4138  Op.getValueType().getVectorNumElements() == NumElts;
4139  };
4140 
4141  auto IsConstantBuildVectorOrUndef = [&](const SDValue &Op) {
4143  return (Op.isUndef()) || (Op.getOpcode() == ISD::CONDCODE) ||
4144  (BV && BV->isConstant());
4145  };
4146 
4147  // All operands must be vector types with the same number of elements as
4148  // the result type and must be either UNDEF or a build vector of constant
4149  // or UNDEF scalars.
4150  if (!llvm::all_of(Ops, IsConstantBuildVectorOrUndef) ||
4151  !llvm::all_of(Ops, IsScalarOrSameVectorSize))
4152  return SDValue();
4153 
4154  // If we are comparing vectors, then the result needs to be a i1 boolean
4155  // that is then sign-extended back to the legal result type.
4156  EVT SVT = (Opcode == ISD::SETCC ? MVT::i1 : VT.getScalarType());
4157 
4158  // Find legal integer scalar type for constant promotion and
4159  // ensure that its scalar size is at least as large as source.
4160  EVT LegalSVT = VT.getScalarType();
4161  if (NewNodesMustHaveLegalTypes && LegalSVT.isInteger()) {
4162  LegalSVT = TLI->getTypeToTransformTo(*getContext(), LegalSVT);
4163  if (LegalSVT.bitsLT(VT.getScalarType()))
4164  return SDValue();
4165  }
4166 
4167  // Constant fold each scalar lane separately.
4168  SmallVector<SDValue, 4> ScalarResults;
4169  for (unsigned i = 0; i != NumElts; i++) {
4170  SmallVector<SDValue, 4> ScalarOps;
4171  for (SDValue Op : Ops) {
4172  EVT InSVT = Op.getValueType().getScalarType();
4174  if (!InBV) {
4175  // We've checked that this is UNDEF or a constant of some kind.
4176  if (Op.isUndef())
4177  ScalarOps.push_back(getUNDEF(InSVT));
4178  else
4179  ScalarOps.push_back(Op);
4180  continue;
4181  }
4182 
4183  SDValue ScalarOp = InBV->getOperand(i);
4184  EVT ScalarVT = ScalarOp.getValueType();
4185 
4186  // Build vector (integer) scalar operands may need implicit
4187  // truncation - do this before constant folding.
4188  if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT))
4189  ScalarOp = getNode(ISD::TRUNCATE, DL, InSVT, ScalarOp);
4190 
4191  ScalarOps.push_back(ScalarOp);
4192  }
4193 
4194  // Constant fold the scalar operands.
4195  SDValue ScalarResult = getNode(Opcode, DL, SVT, ScalarOps, Flags);
4196 
4197  // Legalize the (integer) scalar constant if necessary.
4198  if (LegalSVT != SVT)
4199  ScalarResult = getNode(ISD::SIGN_EXTEND, DL, LegalSVT, ScalarResult);
4200 
4201  // Scalar folding only succeeded if the result is a constant or UNDEF.
4202  if (!ScalarResult.isUndef() && ScalarResult.getOpcode() != ISD::Constant &&
4203  ScalarResult.getOpcode() != ISD::ConstantFP)
4204  return SDValue();
4205  ScalarResults.push_back(ScalarResult);
4206  }
4207 
4208  SDValue V = getBuildVector(VT, DL, ScalarResults);
4209  NewSDValueDbgMsg(V, "New node fold constant vector: ", this);
4210  return V;
4211 }
4212 
4213 SDValue SelectionDAG::getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
4214  SDValue N1, SDValue N2, const SDNodeFlags Flags) {
4219 
4220  // Canonicalize constant to RHS if commutative.
4221  if (TLI->isCommutativeBinOp(Opcode)) {
4222  if (N1C && !N2C) {
4223  std::swap(N1C, N2C);
4224  std::swap(N1, N2);
4225  } else if (N1CFP && !N2CFP) {
4226  std::swap(N1CFP, N2CFP);
4227  std::swap(N1, N2);
4228  }
4229  }
4230 
4231  switch (Opcode) {
4232  default: break;
4233  case ISD::TokenFactor:
4234  assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
4235  N2.getValueType() == MVT::Other && "Invalid token factor!");
4236  // Fold trivial token factors.
4237  if (N1.getOpcode() == ISD::EntryToken) return N2;
4238  if (N2.getOpcode() == ISD::EntryToken) return N1;
4239  if (N1 == N2) return N1;
4240  break;
4241  case ISD::CONCAT_VECTORS: {
4242  // Attempt to fold CONCAT_VECTORS into BUILD_VECTOR or UNDEF.
4243  SDValue Ops[] = {N1, N2};
4244  if (SDValue V = FoldCONCAT_VECTORS(DL, VT, Ops, *this))
4245  return V;
4246  break;
4247  }
4248  case ISD::AND:
4249  assert(VT.isInteger() && "This operator does not apply to FP types!");
4250  assert(N1.getValueType() == N2.getValueType() &&
4251  N1.getValueType() == VT && "Binary operator types must match!");
4252  // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
4253  // worth handling here.
4254  if (N2C && N2C->isNullValue())
4255  return N2;
4256  if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
4257  return N1;
4258  break;
4259  case ISD::OR:
4260  case ISD::XOR:
4261  case ISD::ADD:
4262  case ISD::SUB:
4263  assert(VT.isInteger() && "This operator does not apply to FP types!");
4264  assert(N1.getValueType() == N2.getValueType() &&
4265  N1.getValueType() == VT && "Binary operator types must match!");
4266  // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
4267  // it's worth handling here.
4268  if (N2C && N2C->isNullValue())
4269  return N1;
4270  break;
4271  case ISD::UDIV:
4272  case ISD::UREM:
4273  case ISD::MULHU:
4274  case ISD::MULHS:
4275  case ISD::MUL:
4276  case ISD::SDIV:
4277  case ISD::SREM:
4278  case ISD::SMIN:
4279  case ISD::SMAX:
4280  case ISD::UMIN:
4281  case ISD::UMAX:
4282  assert(VT.isInteger() && "This operator does not apply to FP types!");
4283  assert(N1.getValueType() == N2.getValueType() &&
4284  N1.getValueType() == VT && "Binary operator types must match!");
4285  break;
4286  case ISD::FADD:
4287  case ISD::FSUB:
4288  case ISD::FMUL:
4289  case ISD::FDIV:
4290  case ISD::FREM:
4291  if (getTarget().Options.UnsafeFPMath) {
4292  if (Opcode == ISD::FADD) {
4293  // x+0 --> x
4294  if (N2CFP && N2CFP->getValueAPF().isZero())
4295  return N1;
4296  } else if (Opcode == ISD::FSUB) {
4297  // x-0 --> x
4298  if (N2CFP && N2CFP->getValueAPF().isZero())
4299  return N1;
4300  } else if (Opcode == ISD::FMUL) {
4301  // x*0 --> 0
4302  if (N2CFP && N2CFP->isZero())
4303  return N2;
4304  // x*1 --> x
4305  if (N2CFP && N2CFP->isExactlyValue(1.0))
4306  return N1;
4307  }
4308  }
4309  assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
4310  assert(N1.getValueType() == N2.getValueType() &&
4311  N1.getValueType() == VT && "Binary operator types must match!");
4312  break;
4313  case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
4314  assert(N1.getValueType() == VT &&
4315  N1.getValueType().isFloatingPoint() &&
4316  N2.getValueType().isFloatingPoint() &&
4317  "Invalid FCOPYSIGN!");
4318  break;
4319  case ISD::SHL:
4320  case ISD::SRA:
4321  case ISD::SRL:
4322  case ISD::ROTL:
4323  case ISD::ROTR:
4324  assert(VT == N1.getValueType() &&
4325  "Shift operators return type must be the same as their first arg");
4326  assert(VT.isInteger() && N2.getValueType().isInteger() &&
4327  "Shifts only work on integers");
4328  assert((!VT.isVector() || VT == N2.getValueType()) &&
4329  "Vector shift amounts must be in the same as their first arg");
4330  // Verify that the shift amount VT is bit enough to hold valid shift
4331  // amounts. This catches things like trying to shift an i1024 value by an
4332  // i8, which is easy to fall into in generic code that uses
4333  // TLI.getShiftAmount().
4335  "Invalid use of small shift amount with oversized value!");
4336 
4337  // Always fold shifts of i1 values so the code generator doesn't need to
4338  // handle them. Since we know the size of the shift has to be less than the
4339  // size of the value, the shift/rotate count is guaranteed to be zero.
4340  if (VT == MVT::i1)
4341  return N1;
4342  if (N2C && N2C->isNullValue())
4343  return N1;
4344  break;
4345  case ISD::FP_ROUND_INREG: {
4346  EVT EVT = cast<VTSDNode>(N2)->getVT();
4347  assert(VT == N1.getValueType() && "Not an inreg round!");
4348  assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
4349  "Cannot FP_ROUND_INREG integer types");
4350  assert(EVT.isVector() == VT.isVector() &&
4351  "FP_ROUND_INREG type should be vector iff the operand "
4352  "type is vector!");
4353  assert((!EVT.isVector() ||
4354  EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
4355  "Vector element counts must match in FP_ROUND_INREG");
4356  assert(EVT.bitsLE(VT) && "Not rounding down!");
4357  (void)EVT;
4358  if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
4359  break;
4360  }
4361  case ISD::FP_ROUND:
4362  assert(VT.isFloatingPoint() &&
4363  N1.getValueType().isFloatingPoint() &&
4364  VT.bitsLE(N1.getValueType()) &&
4365  N2C && (N2C->getZExtValue() == 0 || N2C->getZExtValue() == 1) &&
4366  "Invalid FP_ROUND!");
4367  if (N1.getValueType() == VT) return N1; // noop conversion.
4368  break;
4369  case ISD::AssertSext:
4370  case ISD::AssertZext: {
4371  EVT EVT = cast<VTSDNode>(N2)->getVT();
4372  assert(VT == N1.getValueType() && "Not an inreg extend!");
4373  assert(VT.isInteger() && EVT.isInteger() &&
4374  "Cannot *_EXTEND_INREG FP types");
4375  assert(!EVT.isVector() &&
4376  "AssertSExt/AssertZExt type should be the vector element type "
4377  "rather than the vector type!");
4378  assert(EVT.bitsLE(VT) && "Not extending!");
4379  if (VT == EVT) return N1; // noop assertion.
4380  break;
4381  }
4382  case ISD::SIGN_EXTEND_INREG: {
4383  EVT EVT = cast<VTSDNode>(N2)->getVT();
4384  assert(VT == N1.getValueType() && "Not an inreg extend!");
4385  assert(VT.isInteger() && EVT.isInteger() &&
4386  "Cannot *_EXTEND_INREG FP types");
4387  assert(EVT.isVector() == VT.isVector() &&
4388  "SIGN_EXTEND_INREG type should be vector iff the operand "
4389  "type is vector!");
4390  assert((!EVT.isVector() ||
4391  EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
4392  "Vector element counts must match in SIGN_EXTEND_INREG");
4393  assert(EVT.bitsLE(VT) && "Not extending!");
4394  if (EVT == VT) return N1; // Not actually extending
4395 
4396  auto SignExtendInReg = [&](APInt Val, llvm::EVT ConstantVT) {
4397  unsigned FromBits = EVT.getScalarSizeInBits();
4398  Val <<= Val.getBitWidth() - FromBits;
4399  Val.ashrInPlace(Val.getBitWidth() - FromBits);
4400  return getConstant(Val, DL, ConstantVT);
4401  };
4402 
4403  if (N1C) {
4404  const APInt &Val = N1C->getAPIntValue();
4405  return SignExtendInReg(Val, VT);
4406  }
4409  llvm::EVT OpVT = N1.getOperand(0).getValueType();
4410  for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
4411  SDValue Op = N1.getOperand(i);
4412  if (Op.isUndef()) {
4413  Ops.push_back(getUNDEF(OpVT));
4414  continue;
4415  }
4416  ConstantSDNode *C = cast<ConstantSDNode>(Op);
4417  APInt Val = C->getAPIntValue();
4418  Ops.push_back(SignExtendInReg(Val, OpVT));
4419  }
4420  return getBuildVector(VT, DL, Ops);
4421  }
4422  break;
4423  }
4425  // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
4426  if (N1.isUndef())
4427  return getUNDEF(VT);
4428 
4429  // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
4430  if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
4431  return getUNDEF(VT);
4432 
4433  // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
4434  // expanding copies of large vectors from registers.
4435  if (N2C &&
4436  N1.getOpcode() == ISD::CONCAT_VECTORS &&
4437  N1.getNumOperands() > 0) {
4438  unsigned Factor =
4440  return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
4441  N1.getOperand(N2C->getZExtValue() / Factor),
4442  getConstant(N2C->getZExtValue() % Factor, DL,
4443  N2.getValueType()));
4444  }
4445 
4446  // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
4447  // expanding large vector constants.
4448  if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
4449  SDValue Elt = N1.getOperand(N2C->getZExtValue());
4450 
4451  if (VT != Elt.getValueType())
4452  // If the vector element type is not legal, the BUILD_VECTOR operands
4453  // are promoted and implicitly truncated, and the result implicitly
4454  // extended. Make that explicit here.
4455  Elt = getAnyExtOrTrunc(Elt, DL, VT);
4456 
4457  return Elt;
4458  }
4459 
4460  // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
4461  // operations are lowered to scalars.
4462  if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
4463  // If the indices are the same, return the inserted element else
4464  // if the indices are known different, extract the element from
4465  // the original vector.
4466  SDValue N1Op2 = N1.getOperand(2);
4467  ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
4468 
4469  if (N1Op2C && N2C) {
4470  if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
4471  if (VT == N1.getOperand(1).getValueType())
4472  return N1.getOperand(1);
4473  else
4474  return getSExtOrTrunc(N1.getOperand(1), DL, VT);
4475  }
4476 
4477  return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
4478  }
4479  }
4480 
4481  // EXTRACT_VECTOR_ELT of v1iX EXTRACT_SUBVECTOR could be formed
4482  // when vector types are scalarized and v1iX is legal.
4483  // vextract (v1iX extract_subvector(vNiX, Idx)) -> vextract(vNiX,Idx)
4484  if (N1.getOpcode() == ISD::EXTRACT_SUBVECTOR &&
4485  N1.getValueType().getVectorNumElements() == 1) {
4486  return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0),
4487  N1.getOperand(1));
4488  }
4489  break;
4490  case ISD::EXTRACT_ELEMENT:
4491  assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
4492  assert(!N1.getValueType().isVector() && !VT.isVector() &&
4493  (N1.getValueType().isInteger() == VT.isInteger()) &&
4494  N1.getValueType() != VT &&
4495  "Wrong types for EXTRACT_ELEMENT!");
4496 
4497  // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
4498  // 64-bit integers into 32-bit parts. Instead of building the extract of
4499  // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
4500  if (N1.getOpcode() == ISD::BUILD_PAIR)
4501  return N1.getOperand(N2C->getZExtValue());
4502 
4503  // EXTRACT_ELEMENT of a constant int is also very common.
4504  if (N1C) {
4505  unsigned ElementSize = VT.getSizeInBits();
4506  unsigned Shift = ElementSize * N2C->getZExtValue();
4507  APInt ShiftedVal = N1C->getAPIntValue().lshr(Shift);
4508  return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
4509  }
4510  break;
4512  if (VT.isSimple() && N1.getValueType().isSimple()) {
4513  assert(VT.isVector() && N1.getValueType().isVector() &&
4514  "Extract subvector VTs must be a vectors!");
4517  "Extract subvector VTs must have the same element type!");
4518  assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
4519  "Extract subvector must be from larger vector to smaller vector!");
4520 
4521  if (N2C) {
4522  assert((VT.getVectorNumElements() + N2C->getZExtValue()
4524  && "Extract subvector overflow!");
4525  }
4526 
4527  // Trivial extraction.
4528  if (VT.getSimpleVT() == N1.getSimpleValueType())
4529  return N1;
4530 
4531  // EXTRACT_SUBVECTOR of an UNDEF is an UNDEF.
4532  if (N1.isUndef())
4533  return getUNDEF(VT);
4534 
4535  // EXTRACT_SUBVECTOR of CONCAT_VECTOR can be simplified if the pieces of
4536  // the concat have the same type as the extract.
4537  if (N2C && N1.getOpcode() == ISD::CONCAT_VECTORS &&
4538  N1.getNumOperands() > 0 &&
4539  VT == N1.getOperand(0).getValueType()) {
4540  unsigned Factor = VT.getVectorNumElements();
4541  return N1.getOperand(N2C->getZExtValue() / Factor);
4542  }
4543 
4544  // EXTRACT_SUBVECTOR of INSERT_SUBVECTOR is often created
4545  // during shuffle legalization.
4546  if (N1.getOpcode() == ISD::INSERT_SUBVECTOR && N2 == N1.getOperand(2) &&
4547  VT == N1.getOperand(1).getValueType())
4548  return N1.getOperand(1);
4549  }
4550  break;
4551  }
4552 
4553  // Perform trivial constant folding.
4554  if (SDValue SV =
4555  FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
4556  return SV;
4557 
4558  // Constant fold FP operations.
4559  bool HasFPExceptions = TLI->hasFloatingPointExceptions();
4560  if (N1CFP) {
4561  if (N2CFP) {
4562  APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
4564  switch (Opcode) {
4565  case ISD::FADD:
4567  if (!HasFPExceptions || s != APFloat::opInvalidOp)
4568  return getConstantFP(V1, DL, VT);
4569  break;
4570  case ISD::FSUB:
4572  if (!HasFPExceptions || s!=APFloat::opInvalidOp)
4573  return getConstantFP(V1, DL, VT);
4574  break;
4575  case ISD::FMUL:
4577  if (!HasFPExceptions || s!=APFloat::opInvalidOp)
4578  return getConstantFP(V1, DL, VT);
4579  break;
4580  case ISD::FDIV:
4582  if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
4583  s!=APFloat::opDivByZero)) {
4584  return getConstantFP(V1, DL, VT);
4585  }
4586  break;
4587  case ISD::FREM :
4588  s = V1.mod(V2);
4589  if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
4590  s!=APFloat::opDivByZero)) {
4591  return getConstantFP(V1, DL, VT);
4592  }
4593  break;
4594  case ISD::FCOPYSIGN:
4595  V1.copySign(V2);
4596  return getConstantFP(V1, DL, VT);
4597  default: break;
4598  }
4599  }
4600 
4601  if (Opcode == ISD::FP_ROUND) {
4602  APFloat V = N1CFP->getValueAPF(); // make copy
4603  bool ignored;
4604  // This can return overflow, underflow, or inexact; we don't care.
4605  // FIXME need to be more flexible about rounding mode.
4606  (void)V.convert(EVTToAPFloatSemantics(VT),
4607  APFloat::rmNearestTiesToEven, &ignored);
4608  return getConstantFP(V, DL, VT);
4609  }
4610  }
4611 
4612  // Canonicalize an UNDEF to the RHS, even over a constant.
4613  if (N1.isUndef()) {
4614  if (TLI->isCommutativeBinOp(Opcode)) {
4615  std::swap(N1, N2);
4616  } else {
4617  switch (Opcode) {
4618  case ISD::FP_ROUND_INREG:
4620  case ISD::SUB:
4621  case ISD::FSUB:
4622  case ISD::FDIV:
4623  case ISD::FREM:
4624  case ISD::SRA:
4625  return N1; // fold op(undef, arg2) -> undef
4626  case ISD::UDIV:
4627  case ISD::SDIV:
4628  case ISD::UREM:
4629  case ISD::SREM:
4630  case ISD::SRL:
4631  case ISD::SHL:
4632  if (!VT.isVector())
4633  return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
4634  // For vectors, we can't easily build an all zero vector, just return
4635  // the LHS.
4636  return N2;
4637  }
4638  }
4639  }
4640 
4641  // Fold a bunch of operators when the RHS is undef.
4642  if (N2.isUndef()) {
4643  switch (Opcode) {
4644  case ISD::XOR:
4645  if (N1.isUndef())
4646  // Handle undef ^ undef -> 0 special case. This is a common
4647  // idiom (misuse).
4648  return getConstant(0, DL, VT);
4650  case ISD::ADD:
4651  case ISD::ADDC:
4652  case ISD::ADDE:
4653  case ISD::SUB:
4654  case ISD::UDIV:
4655  case ISD::SDIV:
4656  case ISD::UREM:
4657  case ISD::SREM:
4658  return N2; // fold op(arg1, undef) -> undef
4659  case ISD::FADD:
4660  case ISD::FSUB:
4661  case ISD::FMUL:
4662  case ISD::FDIV:
4663  case ISD::FREM:
4665  return N2;
4666  break;
4667  case ISD::MUL:
4668  case ISD::AND:
4669  case ISD::SRL:
4670  case ISD::SHL:
4671  if (!VT.isVector())
4672  return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
4673  // For vectors, we can't easily build an all zero vector, just return
4674  // the LHS.
4675  return N1;
4676  case ISD::OR:
4677  if (!VT.isVector())
4678  return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
4679  // For vectors, we can't easily build an all one vector, just return
4680  // the LHS.
4681  return N1;
4682  case ISD::SRA:
4683  return N1;
4684  }
4685  }
4686 
4687  // Memoize this node if possible.
4688  SDNode *N;
4689  SDVTList VTs = getVTList(VT);
4690  SDValue Ops[] = {N1, N2};
4691  if (VT != MVT::Glue) {
4693  AddNodeIDNode(ID, Opcode, VTs, Ops);
4694  void *IP = nullptr;
4695  if (SDNode *E = FindNodeOrInsertPos(ID, DL, IP)) {
4696  E->intersectFlagsWith(Flags);
4697  return SDValue(E, 0);
4698  }
4699 
4700  N = newSDNode<SDNode>(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs);
4701  N->setFlags(Flags);
4702  createOperands(N, Ops);
4703  CSEMap.InsertNode(N, IP);
4704  } else {
4705  N = newSDNode<SDNode>(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs);
4706  createOperands(N, Ops);
4707  }
4708 
4709  InsertNode(N);
4710  SDValue V = SDValue(N, 0);