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