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