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