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