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