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