c819516eca04b3986b51d57889daad905f6206ac
[opencl/llvm.git] / lib / CodeGen / SelectionDAG / SelectionDAG.cpp
1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This implements the SelectionDAG class.
11 //
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
50 #include <algorithm>
51 #include <cmath>
53 using namespace llvm;
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58   SDVTList Res = {VTs, NumVTs};
59   return Res;
60 }
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 //                              ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75   return getValueAPF().bitwiseIsEqual(V);
76 }
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
79                                            const APFloat& Val) {
80   assert(VT.isFloatingPoint() && "Can only convert between FP types");
82   // convert modifies in place, so make a copy.
83   APFloat Val2 = APFloat(Val);
84   bool losesInfo;
85   (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86                       APFloat::rmNearestTiesToEven,
87                       &losesInfo);
88   return !losesInfo;
89 }
91 //===----------------------------------------------------------------------===//
92 //                              ISD Namespace
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98   // Look through a bit convert.
99   while (N->getOpcode() == ISD::BITCAST)
100     N = N->getOperand(0).getNode();
102   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104   unsigned i = 0, e = N->getNumOperands();
106   // Skip over all of the undef values.
107   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
108     ++i;
110   // Do not accept an all-undef vector.
111   if (i == e) return false;
113   // Do not accept build_vectors that aren't all constants or which have non-~0
114   // elements. We have to be a bit careful here, as the type of the constant
115   // may not be the same as the type of the vector elements due to type
116   // legalization (the elements are promoted to a legal type for the target and
117   // a vector of a type may be legal when the base element type is not).
118   // We only want to check enough bits to cover the vector elements, because
119   // we care if the resultant vector is all ones, not whether the individual
120   // constants are.
121   SDValue NotZero = N->getOperand(i);
122   unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124     if (CN->getAPIntValue().countTrailingOnes() < EltSize)
125       return false;
126   } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127     if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
128       return false;
129   } else
130     return false;
132   // Okay, we have at least one ~0 value, check to see if the rest match or are
133   // undefs. Even with the above element type twiddling, this should be OK, as
134   // the same type legalization should have applied to all the elements.
135   for (++i; i != e; ++i)
136     if (N->getOperand(i) != NotZero &&
137         N->getOperand(i).getOpcode() != ISD::UNDEF)
138       return false;
139   return true;
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146   // Look through a bit convert.
147   while (N->getOpcode() == ISD::BITCAST)
148     N = N->getOperand(0).getNode();
150   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152   bool IsAllUndef = true;
153   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154     if (N->getOperand(i).getOpcode() == ISD::UNDEF)
155       continue;
156     IsAllUndef = false;
157     // Do not accept build_vectors that aren't all constants or which have non-0
158     // elements. We have to be a bit careful here, as the type of the constant
159     // may not be the same as the type of the vector elements due to type
160     // legalization (the elements are promoted to a legal type for the target
161     // and a vector of a type may be legal when the base element type is not).
162     // We only want to check enough bits to cover the vector elements, because
163     // we care if the resultant vector is all zeros, not whether the individual
164     // constants are.
165     SDValue Zero = N->getOperand(i);
166     unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168       if (CN->getAPIntValue().countTrailingZeros() < EltSize)
169         return false;
170     } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171       if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
172         return false;
173     } else
174       return false;
175   }
177   // Do not accept an all-undef vector.
178   if (IsAllUndef)
179     return false;
180   return true;
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186   if (N->getOpcode() != ISD::BUILD_VECTOR)
187     return false;
189   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190     SDValue Op = N->getOperand(i);
191     if (Op.getOpcode() == ISD::UNDEF)
192       continue;
193     if (!isa<ConstantSDNode>(Op))
194       return false;
195   }
196   return true;
199 /// isScalarToVector - Return true if the specified node is a
200 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
201 /// element is not an undef.
202 bool ISD::isScalarToVector(const SDNode *N) {
203   if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
204     return true;
206   if (N->getOpcode() != ISD::BUILD_VECTOR)
207     return false;
208   if (N->getOperand(0).getOpcode() == ISD::UNDEF)
209     return false;
210   unsigned NumElems = N->getNumOperands();
211   if (NumElems == 1)
212     return false;
213   for (unsigned i = 1; i < NumElems; ++i) {
214     SDValue V = N->getOperand(i);
215     if (V.getOpcode() != ISD::UNDEF)
216       return false;
217   }
218   return true;
221 /// allOperandsUndef - Return true if the node has at least one operand
222 /// and all operands of the specified node are ISD::UNDEF.
223 bool ISD::allOperandsUndef(const SDNode *N) {
224   // Return false if the node has no operands.
225   // This is "logically inconsistent" with the definition of "all" but
226   // is probably the desired behavior.
227   if (N->getNumOperands() == 0)
228     return false;
230   for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
231     if (N->getOperand(i).getOpcode() != ISD::UNDEF)
232       return false;
234   return true;
237 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
238   switch (ExtType) {
239   case ISD::EXTLOAD:
240     return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
241   case ISD::SEXTLOAD:
242     return ISD::SIGN_EXTEND;
243   case ISD::ZEXTLOAD:
244     return ISD::ZERO_EXTEND;
245   default:
246     break;
247   }
249   llvm_unreachable("Invalid LoadExtType");
252 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
253 /// when given the operation for (X op Y).
254 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
255   // To perform this operation, we just need to swap the L and G bits of the
256   // operation.
257   unsigned OldL = (Operation >> 2) & 1;
258   unsigned OldG = (Operation >> 1) & 1;
259   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
260                        (OldL << 1) |       // New G bit
261                        (OldG << 2));       // New L bit.
264 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
265 /// 'op' is a valid SetCC operation.
266 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
267   unsigned Operation = Op;
268   if (isInteger)
269     Operation ^= 7;   // Flip L, G, E bits, but not U.
270   else
271     Operation ^= 15;  // Flip all of the condition bits.
273   if (Operation > ISD::SETTRUE2)
274     Operation &= ~8;  // Don't let N and U bits get set.
276   return ISD::CondCode(Operation);
280 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
281 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
282 /// if the operation does not depend on the sign of the input (setne and seteq).
283 static int isSignedOp(ISD::CondCode Opcode) {
284   switch (Opcode) {
285   default: llvm_unreachable("Illegal integer setcc operation!");
286   case ISD::SETEQ:
287   case ISD::SETNE: return 0;
288   case ISD::SETLT:
289   case ISD::SETLE:
290   case ISD::SETGT:
291   case ISD::SETGE: return 1;
292   case ISD::SETULT:
293   case ISD::SETULE:
294   case ISD::SETUGT:
295   case ISD::SETUGE: return 2;
296   }
299 /// getSetCCOrOperation - Return the result of a logical OR between different
300 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
301 /// returns SETCC_INVALID if it is not possible to represent the resultant
302 /// comparison.
303 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
304                                        bool isInteger) {
305   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
306     // Cannot fold a signed integer setcc with an unsigned integer setcc.
307     return ISD::SETCC_INVALID;
309   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
311   // If the N and U bits get set then the resultant comparison DOES suddenly
312   // care about orderedness, and is true when ordered.
313   if (Op > ISD::SETTRUE2)
314     Op &= ~16;     // Clear the U bit if the N bit is set.
316   // Canonicalize illegal integer setcc's.
317   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
318     Op = ISD::SETNE;
320   return ISD::CondCode(Op);
323 /// getSetCCAndOperation - Return the result of a logical AND between different
324 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
325 /// function returns zero if it is not possible to represent the resultant
326 /// comparison.
327 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
328                                         bool isInteger) {
329   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
330     // Cannot fold a signed setcc with an unsigned setcc.
331     return ISD::SETCC_INVALID;
333   // Combine all of the condition bits.
334   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
336   // Canonicalize illegal integer setcc's.
337   if (isInteger) {
338     switch (Result) {
339     default: break;
340     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
341     case ISD::SETOEQ:                                 // SETEQ  & SETU[LG]E
342     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
343     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
344     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
345     }
346   }
348   return Result;
351 //===----------------------------------------------------------------------===//
352 //                           SDNode Profile Support
353 //===----------------------------------------------------------------------===//
355 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
356 ///
357 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
358   ID.AddInteger(OpC);
361 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
362 /// solely with their pointer.
363 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
364   ID.AddPointer(VTList.VTs);
367 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
368 ///
369 static void AddNodeIDOperands(FoldingSetNodeID &ID,
370                               ArrayRef<SDValue> Ops) {
371   for (auto& Op : Ops) {
372     ID.AddPointer(Op.getNode());
373     ID.AddInteger(Op.getResNo());
374   }
377 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
378 ///
379 static void AddNodeIDOperands(FoldingSetNodeID &ID,
380                               ArrayRef<SDUse> Ops) {
381   for (auto& Op : Ops) {
382     ID.AddPointer(Op.getNode());
383     ID.AddInteger(Op.getResNo());
384   }
387 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
388                                   bool exact) {
389   ID.AddBoolean(nuw);
390   ID.AddBoolean(nsw);
391   ID.AddBoolean(exact);
394 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
395 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
396                                   bool nuw, bool nsw, bool exact) {
397   if (isBinOpWithFlags(Opcode))
398     AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
401 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
402                           SDVTList VTList, ArrayRef<SDValue> OpList) {
403   AddNodeIDOpcode(ID, OpC);
404   AddNodeIDValueTypes(ID, VTList);
405   AddNodeIDOperands(ID, OpList);
408 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
409 /// the NodeID data.
410 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
411   switch (N->getOpcode()) {
412   case ISD::TargetExternalSymbol:
413   case ISD::ExternalSymbol:
414     llvm_unreachable("Should only be used on nodes with operands");
415   default: break;  // Normal nodes don't need extra info.
416   case ISD::TargetConstant:
417   case ISD::Constant: {
418     const ConstantSDNode *C = cast<ConstantSDNode>(N);
419     ID.AddPointer(C->getConstantIntValue());
420     ID.AddBoolean(C->isOpaque());
421     break;
422   }
423   case ISD::TargetConstantFP:
424   case ISD::ConstantFP: {
425     ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
426     break;
427   }
428   case ISD::TargetGlobalAddress:
429   case ISD::GlobalAddress:
430   case ISD::TargetGlobalTLSAddress:
431   case ISD::GlobalTLSAddress: {
432     const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
433     ID.AddPointer(GA->getGlobal());
434     ID.AddInteger(GA->getOffset());
435     ID.AddInteger(GA->getTargetFlags());
436     ID.AddInteger(GA->getAddressSpace());
437     break;
438   }
439   case ISD::BasicBlock:
440     ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
441     break;
442   case ISD::Register:
443     ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
444     break;
445   case ISD::RegisterMask:
446     ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
447     break;
448   case ISD::SRCVALUE:
449     ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
450     break;
451   case ISD::FrameIndex:
452   case ISD::TargetFrameIndex:
453     ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
454     break;
455   case ISD::JumpTable:
456   case ISD::TargetJumpTable:
457     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
458     ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
459     break;
460   case ISD::ConstantPool:
461   case ISD::TargetConstantPool: {
462     const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
463     ID.AddInteger(CP->getAlignment());
464     ID.AddInteger(CP->getOffset());
465     if (CP->isMachineConstantPoolEntry())
466       CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
467     else
468       ID.AddPointer(CP->getConstVal());
469     ID.AddInteger(CP->getTargetFlags());
470     break;
471   }
472   case ISD::TargetIndex: {
473     const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
474     ID.AddInteger(TI->getIndex());
475     ID.AddInteger(TI->getOffset());
476     ID.AddInteger(TI->getTargetFlags());
477     break;
478   }
479   case ISD::LOAD: {
480     const LoadSDNode *LD = cast<LoadSDNode>(N);
481     ID.AddInteger(LD->getMemoryVT().getRawBits());
482     ID.AddInteger(LD->getRawSubclassData());
483     ID.AddInteger(LD->getPointerInfo().getAddrSpace());
484     break;
485   }
486   case ISD::STORE: {
487     const StoreSDNode *ST = cast<StoreSDNode>(N);
488     ID.AddInteger(ST->getMemoryVT().getRawBits());
489     ID.AddInteger(ST->getRawSubclassData());
490     ID.AddInteger(ST->getPointerInfo().getAddrSpace());
491     break;
492   }
493   case ISD::SDIV:
494   case ISD::UDIV:
495   case ISD::SRA:
496   case ISD::SRL:
497   case ISD::MUL:
498   case ISD::ADD:
499   case ISD::SUB:
500   case ISD::SHL: {
501     const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
502     AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
503                           BinNode->hasNoSignedWrap(), BinNode->isExact());
504     break;
505   }
506   case ISD::ATOMIC_CMP_SWAP:
507   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
508   case ISD::ATOMIC_SWAP:
509   case ISD::ATOMIC_LOAD_ADD:
510   case ISD::ATOMIC_LOAD_SUB:
511   case ISD::ATOMIC_LOAD_AND:
512   case ISD::ATOMIC_LOAD_OR:
513   case ISD::ATOMIC_LOAD_XOR:
514   case ISD::ATOMIC_LOAD_NAND:
515   case ISD::ATOMIC_LOAD_MIN:
516   case ISD::ATOMIC_LOAD_MAX:
517   case ISD::ATOMIC_LOAD_UMIN:
518   case ISD::ATOMIC_LOAD_UMAX:
519   case ISD::ATOMIC_LOAD:
520   case ISD::ATOMIC_STORE: {
521     const AtomicSDNode *AT = cast<AtomicSDNode>(N);
522     ID.AddInteger(AT->getMemoryVT().getRawBits());
523     ID.AddInteger(AT->getRawSubclassData());
524     ID.AddInteger(AT->getPointerInfo().getAddrSpace());
525     break;
526   }
527   case ISD::PREFETCH: {
528     const MemSDNode *PF = cast<MemSDNode>(N);
529     ID.AddInteger(PF->getPointerInfo().getAddrSpace());
530     break;
531   }
532   case ISD::VECTOR_SHUFFLE: {
533     const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
534     for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
535          i != e; ++i)
536       ID.AddInteger(SVN->getMaskElt(i));
537     break;
538   }
539   case ISD::TargetBlockAddress:
540   case ISD::BlockAddress: {
541     const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
542     ID.AddPointer(BA->getBlockAddress());
543     ID.AddInteger(BA->getOffset());
544     ID.AddInteger(BA->getTargetFlags());
545     break;
546   }
547   } // end switch (N->getOpcode())
549   // Target specific memory nodes could also have address spaces to check.
550   if (N->isTargetMemoryOpcode())
551     ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
554 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
555 /// data.
556 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
557   AddNodeIDOpcode(ID, N->getOpcode());
558   // Add the return value info.
559   AddNodeIDValueTypes(ID, N->getVTList());
560   // Add the operand info.
561   AddNodeIDOperands(ID, N->ops());
563   // Handle SDNode leafs with special info.
564   AddNodeIDCustom(ID, N);
567 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
568 /// the CSE map that carries volatility, temporalness, indexing mode, and
569 /// extension/truncation information.
570 ///
571 static inline unsigned
572 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
573                      bool isNonTemporal, bool isInvariant) {
574   assert((ConvType & 3) == ConvType &&
575          "ConvType may not require more than 2 bits!");
576   assert((AM & 7) == AM &&
577          "AM may not require more than 3 bits!");
578   return ConvType |
579          (AM << 2) |
580          (isVolatile << 5) |
581          (isNonTemporal << 6) |
582          (isInvariant << 7);
585 //===----------------------------------------------------------------------===//
586 //                              SelectionDAG Class
587 //===----------------------------------------------------------------------===//
589 /// doNotCSE - Return true if CSE should not be performed for this node.
590 static bool doNotCSE(SDNode *N) {
591   if (N->getValueType(0) == MVT::Glue)
592     return true; // Never CSE anything that produces a flag.
594   switch (N->getOpcode()) {
595   default: break;
596   case ISD::HANDLENODE:
597   case ISD::EH_LABEL:
598     return true;   // Never CSE these nodes.
599   }
601   // Check that remaining values produced are not flags.
602   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
603     if (N->getValueType(i) == MVT::Glue)
604       return true; // Never CSE anything that produces a flag.
606   return false;
609 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
610 /// SelectionDAG.
611 void SelectionDAG::RemoveDeadNodes() {
612   // Create a dummy node (which is not added to allnodes), that adds a reference
613   // to the root node, preventing it from being deleted.
614   HandleSDNode Dummy(getRoot());
616   SmallVector<SDNode*, 128> DeadNodes;
618   // Add all obviously-dead nodes to the DeadNodes worklist.
619   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
620     if (I->use_empty())
621       DeadNodes.push_back(I);
623   RemoveDeadNodes(DeadNodes);
625   // If the root changed (e.g. it was a dead load, update the root).
626   setRoot(Dummy.getValue());
629 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
630 /// given list, and any nodes that become unreachable as a result.
631 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
633   // Process the worklist, deleting the nodes and adding their uses to the
634   // worklist.
635   while (!DeadNodes.empty()) {
636     SDNode *N = DeadNodes.pop_back_val();
638     for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
639       DUL->NodeDeleted(N, nullptr);
641     // Take the node out of the appropriate CSE map.
642     RemoveNodeFromCSEMaps(N);
644     // Next, brutally remove the operand list.  This is safe to do, as there are
645     // no cycles in the graph.
646     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
647       SDUse &Use = *I++;
648       SDNode *Operand = Use.getNode();
649       Use.set(SDValue());
651       // Now that we removed this operand, see if there are no uses of it left.
652       if (Operand->use_empty())
653         DeadNodes.push_back(Operand);
654     }
656     DeallocateNode(N);
657   }
660 void SelectionDAG::RemoveDeadNode(SDNode *N){
661   SmallVector<SDNode*, 16> DeadNodes(1, N);
663   // Create a dummy node that adds a reference to the root node, preventing
664   // it from being deleted.  (This matters if the root is an operand of the
665   // dead node.)
666   HandleSDNode Dummy(getRoot());
668   RemoveDeadNodes(DeadNodes);
671 void SelectionDAG::DeleteNode(SDNode *N) {
672   // First take this out of the appropriate CSE map.
673   RemoveNodeFromCSEMaps(N);
675   // Finally, remove uses due to operands of this node, remove from the
676   // AllNodes list, and delete the node.
677   DeleteNodeNotInCSEMaps(N);
680 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
681   assert(N != AllNodes.begin() && "Cannot delete the entry node!");
682   assert(N->use_empty() && "Cannot delete a node that is not dead!");
684   // Drop all of the operands and decrement used node's use counts.
685   N->DropOperands();
687   DeallocateNode(N);
690 void SDDbgInfo::erase(const SDNode *Node) {
691   DbgValMapType::iterator I = DbgValMap.find(Node);
692   if (I == DbgValMap.end())
693     return;
694   for (auto &Val: I->second)
695     Val->setIsInvalidated();
696   DbgValMap.erase(I);
699 void SelectionDAG::DeallocateNode(SDNode *N) {
700   if (N->OperandsNeedDelete)
701     delete[] N->OperandList;
703   // Set the opcode to DELETED_NODE to help catch bugs when node
704   // memory is reallocated.
705   N->NodeType = ISD::DELETED_NODE;
707   NodeAllocator.Deallocate(AllNodes.remove(N));
709   // If any of the SDDbgValue nodes refer to this SDNode, invalidate
710   // them and forget about that node.
711   DbgInfo->erase(N);
714 #ifndef NDEBUG
715 /// VerifySDNode - Sanity check the given SDNode.  Aborts if it is invalid.
716 static void VerifySDNode(SDNode *N) {
717   switch (N->getOpcode()) {
718   default:
719     break;
720   case ISD::BUILD_PAIR: {
721     EVT VT = N->getValueType(0);
722     assert(N->getNumValues() == 1 && "Too many results!");
723     assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
724            "Wrong return type!");
725     assert(N->getNumOperands() == 2 && "Wrong number of operands!");
726     assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
727            "Mismatched operand types!");
728     assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
729            "Wrong operand type!");
730     assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
731            "Wrong return type size");
732     break;
733   }
734   case ISD::BUILD_VECTOR: {
735     assert(N->getNumValues() == 1 && "Too many results!");
736     assert(N->getValueType(0).isVector() && "Wrong return type!");
737     assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
738            "Wrong number of operands!");
739     EVT EltVT = N->getValueType(0).getVectorElementType();
740     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
741       assert((I->getValueType() == EltVT ||
742              (EltVT.isInteger() && I->getValueType().isInteger() &&
743               EltVT.bitsLE(I->getValueType()))) &&
744             "Wrong operand type!");
745       assert(I->getValueType() == N->getOperand(0).getValueType() &&
746              "Operands must all have the same type");
747     }
748     break;
749   }
750   }
752 #endif // NDEBUG
754 /// \brief Insert a newly allocated node into the DAG.
755 ///
756 /// Handles insertion into the all nodes list and CSE map, as well as
757 /// verification and other common operations when a new node is allocated.
758 void SelectionDAG::InsertNode(SDNode *N) {
759   AllNodes.push_back(N);
760 #ifndef NDEBUG
761   VerifySDNode(N);
762 #endif
765 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
766 /// correspond to it.  This is useful when we're about to delete or repurpose
767 /// the node.  We don't want future request for structurally identical nodes
768 /// to return N anymore.
769 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
770   bool Erased = false;
771   switch (N->getOpcode()) {
772   case ISD::HANDLENODE: return false;  // noop.
773   case ISD::CONDCODE:
774     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
775            "Cond code doesn't exist!");
776     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
777     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
778     break;
779   case ISD::ExternalSymbol:
780     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
781     break;
782   case ISD::TargetExternalSymbol: {
783     ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
784     Erased = TargetExternalSymbols.erase(
785                std::pair<std::string,unsigned char>(ESN->getSymbol(),
786                                                     ESN->getTargetFlags()));
787     break;
788   }
789   case ISD::VALUETYPE: {
790     EVT VT = cast<VTSDNode>(N)->getVT();
791     if (VT.isExtended()) {
792       Erased = ExtendedValueTypeNodes.erase(VT);
793     } else {
794       Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
795       ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
796     }
797     break;
798   }
799   default:
800     // Remove it from the CSE Map.
801     assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
802     assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
803     Erased = CSEMap.RemoveNode(N);
804     break;
805   }
806 #ifndef NDEBUG
807   // Verify that the node was actually in one of the CSE maps, unless it has a
808   // flag result (which cannot be CSE'd) or is one of the special cases that are
809   // not subject to CSE.
810   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
811       !N->isMachineOpcode() && !doNotCSE(N)) {
812     N->dump(this);
813     dbgs() << "\n";
814     llvm_unreachable("Node is not in map!");
815   }
816 #endif
817   return Erased;
820 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
821 /// maps and modified in place. Add it back to the CSE maps, unless an identical
822 /// node already exists, in which case transfer all its users to the existing
823 /// node. This transfer can potentially trigger recursive merging.
824 ///
825 void
826 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
827   // For node types that aren't CSE'd, just act as if no identical node
828   // already exists.
829   if (!doNotCSE(N)) {
830     SDNode *Existing = CSEMap.GetOrInsertNode(N);
831     if (Existing != N) {
832       // If there was already an existing matching node, use ReplaceAllUsesWith
833       // to replace the dead one with the existing one.  This can cause
834       // recursive merging of other unrelated nodes down the line.
835       ReplaceAllUsesWith(N, Existing);
837       // N is now dead. Inform the listeners and delete it.
838       for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
839         DUL->NodeDeleted(N, Existing);
840       DeleteNodeNotInCSEMaps(N);
841       return;
842     }
843   }
845   // If the node doesn't already exist, we updated it.  Inform listeners.
846   for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
847     DUL->NodeUpdated(N);
850 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
851 /// were replaced with those specified.  If this node is never memoized,
852 /// return null, otherwise return a pointer to the slot it would take.  If a
853 /// node already exists with these operands, the slot will be non-null.
854 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
855                                            void *&InsertPos) {
856   if (doNotCSE(N))
857     return nullptr;
859   SDValue Ops[] = { Op };
860   FoldingSetNodeID ID;
861   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
862   AddNodeIDCustom(ID, N);
863   SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
864   return Node;
867 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
868 /// were replaced with those specified.  If this node is never memoized,
869 /// return null, otherwise return a pointer to the slot it would take.  If a
870 /// node already exists with these operands, the slot will be non-null.
871 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
872                                            SDValue Op1, SDValue Op2,
873                                            void *&InsertPos) {
874   if (doNotCSE(N))
875     return nullptr;
877   SDValue Ops[] = { Op1, Op2 };
878   FoldingSetNodeID ID;
879   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880   AddNodeIDCustom(ID, N);
881   SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
882   return Node;
886 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
887 /// were replaced with those specified.  If this node is never memoized,
888 /// return null, otherwise return a pointer to the slot it would take.  If a
889 /// node already exists with these operands, the slot will be non-null.
890 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
891                                            void *&InsertPos) {
892   if (doNotCSE(N))
893     return nullptr;
895   FoldingSetNodeID ID;
896   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
897   AddNodeIDCustom(ID, N);
898   SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
899   return Node;
902 /// getEVTAlignment - Compute the default alignment value for the
903 /// given type.
904 ///
905 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
906   Type *Ty = VT == MVT::iPTR ?
907                    PointerType::get(Type::getInt8Ty(*getContext()), 0) :
908                    VT.getTypeForEVT(*getContext());
910   return TLI->getDataLayout()->getABITypeAlignment(Ty);
913 // EntryNode could meaningfully have debug info if we can find it...
914 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
915     : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
916       EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
917       Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
918       UpdateListeners(nullptr) {
919   AllNodes.push_back(&EntryNode);
920   DbgInfo = new SDDbgInfo();
923 void SelectionDAG::init(MachineFunction &mf) {
924   MF = &mf;
925   TLI = getSubtarget().getTargetLowering();
926   TSI = getSubtarget().getSelectionDAGInfo();
927   Context = &mf.getFunction()->getContext();
930 SelectionDAG::~SelectionDAG() {
931   assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
932   allnodes_clear();
933   delete DbgInfo;
936 void SelectionDAG::allnodes_clear() {
937   assert(&*AllNodes.begin() == &EntryNode);
938   AllNodes.remove(AllNodes.begin());
939   while (!AllNodes.empty())
940     DeallocateNode(AllNodes.begin());
943 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
944                                             SDVTList VTs, SDValue N1,
945                                             SDValue N2, bool nuw, bool nsw,
946                                             bool exact) {
947   if (isBinOpWithFlags(Opcode)) {
948     BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
949         Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
950     FN->setHasNoUnsignedWrap(nuw);
951     FN->setHasNoSignedWrap(nsw);
952     FN->setIsExact(exact);
954     return FN;
955   }
957   BinarySDNode *N = new (NodeAllocator)
958       BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
959   return N;
962 void SelectionDAG::clear() {
963   allnodes_clear();
964   OperandAllocator.Reset();
965   CSEMap.clear();
967   ExtendedValueTypeNodes.clear();
968   ExternalSymbols.clear();
969   TargetExternalSymbols.clear();
970   std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
971             static_cast<CondCodeSDNode*>(nullptr));
972   std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
973             static_cast<SDNode*>(nullptr));
975   EntryNode.UseList = nullptr;
976   AllNodes.push_back(&EntryNode);
977   Root = getEntryNode();
978   DbgInfo->clear();
981 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
982   return VT.bitsGT(Op.getValueType()) ?
983     getNode(ISD::ANY_EXTEND, DL, VT, Op) :
984     getNode(ISD::TRUNCATE, DL, VT, Op);
987 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
988   return VT.bitsGT(Op.getValueType()) ?
989     getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
990     getNode(ISD::TRUNCATE, DL, VT, Op);
993 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
994   return VT.bitsGT(Op.getValueType()) ?
995     getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
996     getNode(ISD::TRUNCATE, DL, VT, Op);
999 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1000                                         EVT OpVT) {
1001   if (VT.bitsLE(Op.getValueType()))
1002     return getNode(ISD::TRUNCATE, SL, VT, Op);
1004   TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1005   return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1008 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1009   assert(!VT.isVector() &&
1010          "getZeroExtendInReg should use the vector element type instead of "
1011          "the vector type!");
1012   if (Op.getValueType() == VT) return Op;
1013   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1014   APInt Imm = APInt::getLowBitsSet(BitWidth,
1015                                    VT.getSizeInBits());
1016   return getNode(ISD::AND, DL, Op.getValueType(), Op,
1017                  getConstant(Imm, Op.getValueType()));
1020 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1021   assert(VT.isVector() && "This DAG node is restricted to vector types.");
1022   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1023          "The sizes of the input and result must match in order to perform the "
1024          "extend in-register.");
1025   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1026          "The destination vector type must have fewer lanes than the input.");
1027   return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1030 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1031   assert(VT.isVector() && "This DAG node is restricted to vector types.");
1032   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1033          "The sizes of the input and result must match in order to perform the "
1034          "extend in-register.");
1035   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1036          "The destination vector type must have fewer lanes than the input.");
1037   return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1040 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1041   assert(VT.isVector() && "This DAG node is restricted to vector types.");
1042   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1043          "The sizes of the input and result must match in order to perform the "
1044          "extend in-register.");
1045   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1046          "The destination vector type must have fewer lanes than the input.");
1047   return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1050 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1051 ///
1052 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1053   EVT EltVT = VT.getScalarType();
1054   SDValue NegOne =
1055     getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1056   return getNode(ISD::XOR, DL, VT, Val, NegOne);
1059 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1060   EVT EltVT = VT.getScalarType();
1061   SDValue TrueValue;
1062   switch (TLI->getBooleanContents(VT)) {
1063     case TargetLowering::ZeroOrOneBooleanContent:
1064     case TargetLowering::UndefinedBooleanContent:
1065       TrueValue = getConstant(1, VT);
1066       break;
1067     case TargetLowering::ZeroOrNegativeOneBooleanContent:
1068       TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1069                               VT);
1070       break;
1071   }
1072   return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1075 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1076   EVT EltVT = VT.getScalarType();
1077   assert((EltVT.getSizeInBits() >= 64 ||
1078          (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1079          "getConstant with a uint64_t value that doesn't fit in the type!");
1080   return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1083 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1085   return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1088 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1089                                   bool isO) {
1090   assert(VT.isInteger() && "Cannot create FP integer constant!");
1092   EVT EltVT = VT.getScalarType();
1093   const ConstantInt *Elt = &Val;
1095   // In some cases the vector type is legal but the element type is illegal and
1096   // needs to be promoted, for example v8i8 on ARM.  In this case, promote the
1097   // inserted value (the type does not need to match the vector element type).
1098   // Any extra bits introduced will be truncated away.
1099   if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1100       TargetLowering::TypePromoteInteger) {
1101    EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1102    APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1103    Elt = ConstantInt::get(*getContext(), NewVal);
1104   }
1105   // In other cases the element type is illegal and needs to be expanded, for
1106   // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1107   // the value into n parts and use a vector type with n-times the elements.
1108   // Then bitcast to the type requested.
1109   // Legalizing constants too early makes the DAGCombiner's job harder so we
1110   // only legalize if the DAG tells us we must produce legal types.
1111   else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1112            TLI->getTypeAction(*getContext(), EltVT) ==
1113            TargetLowering::TypeExpandInteger) {
1114     APInt NewVal = Elt->getValue();
1115     EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1116     unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1117     unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1118     EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1120     // Check the temporary vector is the correct size. If this fails then
1121     // getTypeToTransformTo() probably returned a type whose size (in bits)
1122     // isn't a power-of-2 factor of the requested type size.
1123     assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1125     SmallVector<SDValue, 2> EltParts;
1126     for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1127       EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1128                                            .trunc(ViaEltSizeInBits),
1129                                      ViaEltVT, isT, isO));
1130     }
1132     // EltParts is currently in little endian order. If we actually want
1133     // big-endian order then reverse it now.
1134     if (TLI->isBigEndian())
1135       std::reverse(EltParts.begin(), EltParts.end());
1137     // The elements must be reversed when the element order is different
1138     // to the endianness of the elements (because the BITCAST is itself a
1139     // vector shuffle in this situation). However, we do not need any code to
1140     // perform this reversal because getConstant() is producing a vector
1141     // splat.
1142     // This situation occurs in MIPS MSA.
1144     SmallVector<SDValue, 8> Ops;
1145     for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1146       Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1148     SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1149                              getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1150                                      Ops));
1151     return Result;
1152   }
1154   assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1155          "APInt size does not match type size!");
1156   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1157   FoldingSetNodeID ID;
1158   AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1159   ID.AddPointer(Elt);
1160   ID.AddBoolean(isO);
1161   void *IP = nullptr;
1162   SDNode *N = nullptr;
1163   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1164     if (!VT.isVector())
1165       return SDValue(N, 0);
1167   if (!N) {
1168     N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1169     CSEMap.InsertNode(N, IP);
1170     InsertNode(N);
1171   }
1173   SDValue Result(N, 0);
1174   if (VT.isVector()) {
1175     SmallVector<SDValue, 8> Ops;
1176     Ops.assign(VT.getVectorNumElements(), Result);
1177     Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1178   }
1179   return Result;
1182 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1183   return getConstant(Val, TLI->getPointerTy(), isTarget);
1187 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1188   return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1191 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1192   assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1194   EVT EltVT = VT.getScalarType();
1196   // Do the map lookup using the actual bit pattern for the floating point
1197   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1198   // we don't have issues with SNANs.
1199   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1200   FoldingSetNodeID ID;
1201   AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1202   ID.AddPointer(&V);
1203   void *IP = nullptr;
1204   SDNode *N = nullptr;
1205   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1206     if (!VT.isVector())
1207       return SDValue(N, 0);
1209   if (!N) {
1210     N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1211     CSEMap.InsertNode(N, IP);
1212     InsertNode(N);
1213   }
1215   SDValue Result(N, 0);
1216   if (VT.isVector()) {
1217     SmallVector<SDValue, 8> Ops;
1218     Ops.assign(VT.getVectorNumElements(), Result);
1219     // FIXME SDLoc info might be appropriate here
1220     Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1221   }
1222   return Result;
1225 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1226   EVT EltVT = VT.getScalarType();
1227   if (EltVT==MVT::f32)
1228     return getConstantFP(APFloat((float)Val), VT, isTarget);
1229   else if (EltVT==MVT::f64)
1230     return getConstantFP(APFloat(Val), VT, isTarget);
1231   else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1232            EltVT==MVT::f16) {
1233     bool ignored;
1234     APFloat apf = APFloat(Val);
1235     apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1236                 &ignored);
1237     return getConstantFP(apf, VT, isTarget);
1238   } else
1239     llvm_unreachable("Unsupported type in getConstantFP");
1242 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1243                                        EVT VT, int64_t Offset,
1244                                        bool isTargetGA,
1245                                        unsigned char TargetFlags) {
1246   assert((TargetFlags == 0 || isTargetGA) &&
1247          "Cannot set target flags on target-independent globals");
1249   // Truncate (with sign-extension) the offset value to the pointer size.
1250   unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1251   if (BitWidth < 64)
1252     Offset = SignExtend64(Offset, BitWidth);
1254   unsigned Opc;
1255   if (GV->isThreadLocal())
1256     Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1257   else
1258     Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1260   FoldingSetNodeID ID;
1261   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1262   ID.AddPointer(GV);
1263   ID.AddInteger(Offset);
1264   ID.AddInteger(TargetFlags);
1265   ID.AddInteger(GV->getType()->getAddressSpace());
1266   void *IP = nullptr;
1267   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1268     return SDValue(E, 0);
1270   SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1271                                                       DL.getDebugLoc(), GV, VT,
1272                                                       Offset, TargetFlags);
1273   CSEMap.InsertNode(N, IP);
1274     InsertNode(N);
1275   return SDValue(N, 0);
1278 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1279   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1280   FoldingSetNodeID ID;
1281   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1282   ID.AddInteger(FI);
1283   void *IP = nullptr;
1284   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1285     return SDValue(E, 0);
1287   SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1288   CSEMap.InsertNode(N, IP);
1289   InsertNode(N);
1290   return SDValue(N, 0);
1293 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1294                                    unsigned char TargetFlags) {
1295   assert((TargetFlags == 0 || isTarget) &&
1296          "Cannot set target flags on target-independent jump tables");
1297   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1298   FoldingSetNodeID ID;
1299   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1300   ID.AddInteger(JTI);
1301   ID.AddInteger(TargetFlags);
1302   void *IP = nullptr;
1303   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1304     return SDValue(E, 0);
1306   SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1307                                                   TargetFlags);
1308   CSEMap.InsertNode(N, IP);
1309   InsertNode(N);
1310   return SDValue(N, 0);
1313 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1314                                       unsigned Alignment, int Offset,
1315                                       bool isTarget,
1316                                       unsigned char TargetFlags) {
1317   assert((TargetFlags == 0 || isTarget) &&
1318          "Cannot set target flags on target-independent globals");
1319   if (Alignment == 0)
1320     Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1321   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1322   FoldingSetNodeID ID;
1323   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1324   ID.AddInteger(Alignment);
1325   ID.AddInteger(Offset);
1326   ID.AddPointer(C);
1327   ID.AddInteger(TargetFlags);
1328   void *IP = nullptr;
1329   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1330     return SDValue(E, 0);
1332   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1333                                                      Alignment, TargetFlags);
1334   CSEMap.InsertNode(N, IP);
1335   InsertNode(N);
1336   return SDValue(N, 0);
1340 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1341                                       unsigned Alignment, int Offset,
1342                                       bool isTarget,
1343                                       unsigned char TargetFlags) {
1344   assert((TargetFlags == 0 || isTarget) &&
1345          "Cannot set target flags on target-independent globals");
1346   if (Alignment == 0)
1347     Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1348   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1349   FoldingSetNodeID ID;
1350   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1351   ID.AddInteger(Alignment);
1352   ID.AddInteger(Offset);
1353   C->addSelectionDAGCSEId(ID);
1354   ID.AddInteger(TargetFlags);
1355   void *IP = nullptr;
1356   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1357     return SDValue(E, 0);
1359   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1360                                                      Alignment, TargetFlags);
1361   CSEMap.InsertNode(N, IP);
1362   InsertNode(N);
1363   return SDValue(N, 0);
1366 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1367                                      unsigned char TargetFlags) {
1368   FoldingSetNodeID ID;
1369   AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1370   ID.AddInteger(Index);
1371   ID.AddInteger(Offset);
1372   ID.AddInteger(TargetFlags);
1373   void *IP = nullptr;
1374   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1375     return SDValue(E, 0);
1377   SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1378                                                     TargetFlags);
1379   CSEMap.InsertNode(N, IP);
1380   InsertNode(N);
1381   return SDValue(N, 0);
1384 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1385   FoldingSetNodeID ID;
1386   AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1387   ID.AddPointer(MBB);
1388   void *IP = nullptr;
1389   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1390     return SDValue(E, 0);
1392   SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1393   CSEMap.InsertNode(N, IP);
1394   InsertNode(N);
1395   return SDValue(N, 0);
1398 SDValue SelectionDAG::getValueType(EVT VT) {
1399   if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1400       ValueTypeNodes.size())
1401     ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1403   SDNode *&N = VT.isExtended() ?
1404     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1406   if (N) return SDValue(N, 0);
1407   N = new (NodeAllocator) VTSDNode(VT);
1408   InsertNode(N);
1409   return SDValue(N, 0);
1412 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1413   SDNode *&N = ExternalSymbols[Sym];
1414   if (N) return SDValue(N, 0);
1415   N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1416   InsertNode(N);
1417   return SDValue(N, 0);
1420 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1421                                               unsigned char TargetFlags) {
1422   SDNode *&N =
1423     TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1424                                                                TargetFlags)];
1425   if (N) return SDValue(N, 0);
1426   N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1427   InsertNode(N);
1428   return SDValue(N, 0);
1431 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1432   if ((unsigned)Cond >= CondCodeNodes.size())
1433     CondCodeNodes.resize(Cond+1);
1435   if (!CondCodeNodes[Cond]) {
1436     CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1437     CondCodeNodes[Cond] = N;
1438     InsertNode(N);
1439   }
1441   return SDValue(CondCodeNodes[Cond], 0);
1444 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1445 // the shuffle mask M that point at N1 to point at N2, and indices that point
1446 // N2 to point at N1.
1447 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1448   std::swap(N1, N2);
1449   int NElts = M.size();
1450   for (int i = 0; i != NElts; ++i) {
1451     if (M[i] >= NElts)
1452       M[i] -= NElts;
1453     else if (M[i] >= 0)
1454       M[i] += NElts;
1455   }
1458 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1459                                        SDValue N2, const int *Mask) {
1460   assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1461          "Invalid VECTOR_SHUFFLE");
1463   // Canonicalize shuffle undef, undef -> undef
1464   if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1465     return getUNDEF(VT);
1467   // Validate that all indices in Mask are within the range of the elements
1468   // input to the shuffle.
1469   unsigned NElts = VT.getVectorNumElements();
1470   SmallVector<int, 8> MaskVec;
1471   for (unsigned i = 0; i != NElts; ++i) {
1472     assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1473     MaskVec.push_back(Mask[i]);
1474   }
1476   // Canonicalize shuffle v, v -> v, undef
1477   if (N1 == N2) {
1478     N2 = getUNDEF(VT);
1479     for (unsigned i = 0; i != NElts; ++i)
1480       if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1481   }
1483   // Canonicalize shuffle undef, v -> v, undef.  Commute the shuffle mask.
1484   if (N1.getOpcode() == ISD::UNDEF)
1485     commuteShuffle(N1, N2, MaskVec);
1487   // Canonicalize all index into lhs, -> shuffle lhs, undef
1488   // Canonicalize all index into rhs, -> shuffle rhs, undef
1489   bool AllLHS = true, AllRHS = true;
1490   bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1491   for (unsigned i = 0; i != NElts; ++i) {
1492     if (MaskVec[i] >= (int)NElts) {
1493       if (N2Undef)
1494         MaskVec[i] = -1;
1495       else
1496         AllLHS = false;
1497     } else if (MaskVec[i] >= 0) {
1498       AllRHS = false;
1499     }
1500   }
1501   if (AllLHS && AllRHS)
1502     return getUNDEF(VT);
1503   if (AllLHS && !N2Undef)
1504     N2 = getUNDEF(VT);
1505   if (AllRHS) {
1506     N1 = getUNDEF(VT);
1507     commuteShuffle(N1, N2, MaskVec);
1508   }
1509   // Reset our undef status after accounting for the mask.
1510   N2Undef = N2.getOpcode() == ISD::UNDEF;
1511   // Re-check whether both sides ended up undef.
1512   if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1513     return getUNDEF(VT);
1515   // If Identity shuffle return that node.
1516   bool Identity = true;
1517   for (unsigned i = 0; i != NElts; ++i) {
1518     if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1519   }
1520   if (Identity && NElts)
1521     return N1;
1523   // Shuffling a constant splat doesn't change the result.
1524   if (N2Undef) {
1525     SDValue V = N1;
1527     // Look through any bitcasts. We check that these don't change the number
1528     // (and size) of elements and just changes their types.
1529     while (V.getOpcode() == ISD::BITCAST)
1530       V = V->getOperand(0);
1532     // A splat should always show up as a build vector node.
1533     if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1534       BitVector UndefElements;
1535       SDValue Splat = BV->getSplatValue(&UndefElements);
1536       // If this is a splat of an undef, shuffling it is also undef.
1537       if (Splat && Splat.getOpcode() == ISD::UNDEF)
1538         return getUNDEF(VT);
1540       // We only have a splat which can skip shuffles if there is a splatted
1541       // value and no undef lanes rearranged by the shuffle.
1542       if (Splat && UndefElements.none()) {
1543         // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1544         // number of elements match or the value splatted is a zero constant.
1545         if (V.getValueType().getVectorNumElements() ==
1546             VT.getVectorNumElements())
1547           return N1;
1548         if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1549           if (C->isNullValue())
1550             return N1;
1551       }
1552     }
1553   }
1555   FoldingSetNodeID ID;
1556   SDValue Ops[2] = { N1, N2 };
1557   AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1558   for (unsigned i = 0; i != NElts; ++i)
1559     ID.AddInteger(MaskVec[i]);
1561   void* IP = nullptr;
1562   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1563     return SDValue(E, 0);
1565   // Allocate the mask array for the node out of the BumpPtrAllocator, since
1566   // SDNode doesn't have access to it.  This memory will be "leaked" when
1567   // the node is deallocated, but recovered when the NodeAllocator is released.
1568   int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1569   memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1571   ShuffleVectorSDNode *N =
1572     new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1573                                             dl.getDebugLoc(), N1, N2,
1574                                             MaskAlloc);
1575   CSEMap.InsertNode(N, IP);
1576   InsertNode(N);
1577   return SDValue(N, 0);
1580 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1581   MVT VT = SV.getSimpleValueType(0);
1582   unsigned NumElems = VT.getVectorNumElements();
1583   SmallVector<int, 8> MaskVec;
1585   for (unsigned i = 0; i != NumElems; ++i) {
1586     int Idx = SV.getMaskElt(i);
1587     if (Idx >= 0) {
1588       if (Idx < (int)NumElems)
1589         Idx += NumElems;
1590       else
1591         Idx -= NumElems;
1592     }
1593     MaskVec.push_back(Idx);
1594   }
1596   SDValue Op0 = SV.getOperand(0);
1597   SDValue Op1 = SV.getOperand(1);
1598   return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1601 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1602                                        SDValue Val, SDValue DTy,
1603                                        SDValue STy, SDValue Rnd, SDValue Sat,
1604                                        ISD::CvtCode Code) {
1605   // If the src and dest types are the same and the conversion is between
1606   // integer types of the same sign or two floats, no conversion is necessary.
1607   if (DTy == STy &&
1608       (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1609     return Val;
1611   FoldingSetNodeID ID;
1612   SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1613   AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1614   void* IP = nullptr;
1615   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1616     return SDValue(E, 0);
1618   CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1619                                                            dl.getDebugLoc(),
1620                                                            Ops, Code);
1621   CSEMap.InsertNode(N, IP);
1622   InsertNode(N);
1623   return SDValue(N, 0);
1626 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1627   FoldingSetNodeID ID;
1628   AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1629   ID.AddInteger(RegNo);
1630   void *IP = nullptr;
1631   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1632     return SDValue(E, 0);
1634   SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1635   CSEMap.InsertNode(N, IP);
1636   InsertNode(N);
1637   return SDValue(N, 0);
1640 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1641   FoldingSetNodeID ID;
1642   AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1643   ID.AddPointer(RegMask);
1644   void *IP = nullptr;
1645   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1646     return SDValue(E, 0);
1648   SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1649   CSEMap.InsertNode(N, IP);
1650   InsertNode(N);
1651   return SDValue(N, 0);
1654 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1655   FoldingSetNodeID ID;
1656   SDValue Ops[] = { Root };
1657   AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1658   ID.AddPointer(Label);
1659   void *IP = nullptr;
1660   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1661     return SDValue(E, 0);
1663   SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1664                                                 dl.getDebugLoc(), Root, Label);
1665   CSEMap.InsertNode(N, IP);
1666   InsertNode(N);
1667   return SDValue(N, 0);
1671 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1672                                       int64_t Offset,
1673                                       bool isTarget,
1674                                       unsigned char TargetFlags) {
1675   unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1677   FoldingSetNodeID ID;
1678   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1679   ID.AddPointer(BA);
1680   ID.AddInteger(Offset);
1681   ID.AddInteger(TargetFlags);
1682   void *IP = nullptr;
1683   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1684     return SDValue(E, 0);
1686   SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1687                                                      TargetFlags);
1688   CSEMap.InsertNode(N, IP);
1689   InsertNode(N);
1690   return SDValue(N, 0);
1693 SDValue SelectionDAG::getSrcValue(const Value *V) {
1694   assert((!V || V->getType()->isPointerTy()) &&
1695          "SrcValue is not a pointer?");
1697   FoldingSetNodeID ID;
1698   AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1699   ID.AddPointer(V);
1701   void *IP = nullptr;
1702   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1703     return SDValue(E, 0);
1705   SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1706   CSEMap.InsertNode(N, IP);
1707   InsertNode(N);
1708   return SDValue(N, 0);
1711 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1712 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1713   FoldingSetNodeID ID;
1714   AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1715   ID.AddPointer(MD);
1717   void *IP = nullptr;
1718   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1719     return SDValue(E, 0);
1721   SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1722   CSEMap.InsertNode(N, IP);
1723   InsertNode(N);
1724   return SDValue(N, 0);
1727 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1728 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1729                                        unsigned SrcAS, unsigned DestAS) {
1730   SDValue Ops[] = {Ptr};
1731   FoldingSetNodeID ID;
1732   AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1733   ID.AddInteger(SrcAS);
1734   ID.AddInteger(DestAS);
1736   void *IP = nullptr;
1737   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1738     return SDValue(E, 0);
1740   SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1741                                                       dl.getDebugLoc(),
1742                                                       VT, Ptr, SrcAS, DestAS);
1743   CSEMap.InsertNode(N, IP);
1744   InsertNode(N);
1745   return SDValue(N, 0);
1748 /// getShiftAmountOperand - Return the specified value casted to
1749 /// the target's desired shift amount type.
1750 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1751   EVT OpTy = Op.getValueType();
1752   EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1753   if (OpTy == ShTy || OpTy.isVector()) return Op;
1755   ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ?  ISD::TRUNCATE : ISD::ZERO_EXTEND;
1756   return getNode(Opcode, SDLoc(Op), ShTy, Op);
1759 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1760 /// specified value type.
1761 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1762   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1763   unsigned ByteSize = VT.getStoreSize();
1764   Type *Ty = VT.getTypeForEVT(*getContext());
1765   unsigned StackAlign =
1766   std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1768   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1769   return getFrameIndex(FrameIdx, TLI->getPointerTy());
1772 /// CreateStackTemporary - Create a stack temporary suitable for holding
1773 /// either of the specified value types.
1774 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1775   unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1776                             VT2.getStoreSizeInBits())/8;
1777   Type *Ty1 = VT1.getTypeForEVT(*getContext());
1778   Type *Ty2 = VT2.getTypeForEVT(*getContext());
1779   const DataLayout *TD = TLI->getDataLayout();
1780   unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1781                             TD->getPrefTypeAlignment(Ty2));
1783   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1784   int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1785   return getFrameIndex(FrameIdx, TLI->getPointerTy());
1788 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1789                                 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1790   // These setcc operations always fold.
1791   switch (Cond) {
1792   default: break;
1793   case ISD::SETFALSE:
1794   case ISD::SETFALSE2: return getConstant(0, VT);
1795   case ISD::SETTRUE:
1796   case ISD::SETTRUE2: {
1797     TargetLowering::BooleanContent Cnt =
1798         TLI->getBooleanContents(N1->getValueType(0));
1799     return getConstant(
1800         Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1801   }
1803   case ISD::SETOEQ:
1804   case ISD::SETOGT:
1805   case ISD::SETOGE:
1806   case ISD::SETOLT:
1807   case ISD::SETOLE:
1808   case ISD::SETONE:
1809   case ISD::SETO:
1810   case ISD::SETUO:
1811   case ISD::SETUEQ:
1812   case ISD::SETUNE:
1813     assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1814     break;
1815   }
1817   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1818     const APInt &C2 = N2C->getAPIntValue();
1819     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1820       const APInt &C1 = N1C->getAPIntValue();
1822       switch (Cond) {
1823       default: llvm_unreachable("Unknown integer setcc!");
1824       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
1825       case ISD::SETNE:  return getConstant(C1 != C2, VT);
1826       case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1827       case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1828       case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1829       case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1830       case ISD::SETLT:  return getConstant(C1.slt(C2), VT);
1831       case ISD::SETGT:  return getConstant(C1.sgt(C2), VT);
1832       case ISD::SETLE:  return getConstant(C1.sle(C2), VT);
1833       case ISD::SETGE:  return getConstant(C1.sge(C2), VT);
1834       }
1835     }
1836   }
1837   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1838     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1839       APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1840       switch (Cond) {
1841       default: break;
1842       case ISD::SETEQ:  if (R==APFloat::cmpUnordered)
1843                           return getUNDEF(VT);
1844                         // fall through
1845       case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1846       case ISD::SETNE:  if (R==APFloat::cmpUnordered)
1847                           return getUNDEF(VT);
1848                         // fall through
1849       case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1850                                            R==APFloat::cmpLessThan, VT);
1851       case ISD::SETLT:  if (R==APFloat::cmpUnordered)
1852                           return getUNDEF(VT);
1853                         // fall through
1854       case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1855       case ISD::SETGT:  if (R==APFloat::cmpUnordered)
1856                           return getUNDEF(VT);
1857                         // fall through
1858       case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1859       case ISD::SETLE:  if (R==APFloat::cmpUnordered)
1860                           return getUNDEF(VT);
1861                         // fall through
1862       case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1863                                            R==APFloat::cmpEqual, VT);
1864       case ISD::SETGE:  if (R==APFloat::cmpUnordered)
1865                           return getUNDEF(VT);
1866                         // fall through
1867       case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1868                                            R==APFloat::cmpEqual, VT);
1869       case ISD::SETO:   return getConstant(R!=APFloat::cmpUnordered, VT);
1870       case ISD::SETUO:  return getConstant(R==APFloat::cmpUnordered, VT);
1871       case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1872                                            R==APFloat::cmpEqual, VT);
1873       case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1874       case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1875                                            R==APFloat::cmpLessThan, VT);
1876       case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1877                                            R==APFloat::cmpUnordered, VT);
1878       case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1879       case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1880       }
1881     } else {
1882       // Ensure that the constant occurs on the RHS.
1883       ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1884       MVT CompVT = N1.getValueType().getSimpleVT();
1885       if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1886         return SDValue();
1888       return getSetCC(dl, VT, N2, N1, SwappedCond);
1889     }
1890   }
1892   // Could not fold it.
1893   return SDValue();
1896 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1897 /// use this predicate to simplify operations downstream.
1898 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1899   // This predicate is not safe for vector operations.
1900   if (Op.getValueType().isVector())
1901     return false;
1903   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1904   return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1907 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
1908 /// this predicate to simplify operations downstream.  Mask is known to be zero
1909 /// for bits that V cannot have.
1910 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1911                                      unsigned Depth) const {
1912   APInt KnownZero, KnownOne;
1913   computeKnownBits(Op, KnownZero, KnownOne, Depth);
1914   return (KnownZero & Mask) == Mask;
1917 /// Determine which bits of Op are known to be either zero or one and return
1918 /// them in the KnownZero/KnownOne bitsets.
1919 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1920                                     APInt &KnownOne, unsigned Depth) const {
1921   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1923   KnownZero = KnownOne = APInt(BitWidth, 0);   // Don't know anything.
1924   if (Depth == 6)
1925     return;  // Limit search depth.
1927   APInt KnownZero2, KnownOne2;
1929   switch (Op.getOpcode()) {
1930   case ISD::Constant:
1931     // We know all of the bits for a constant!
1932     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1933     KnownZero = ~KnownOne;
1934     break;
1935   case ISD::AND:
1936     // If either the LHS or the RHS are Zero, the result is zero.
1937     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1938     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1940     // Output known-1 bits are only known if set in both the LHS & RHS.
1941     KnownOne &= KnownOne2;
1942     // Output known-0 are known to be clear if zero in either the LHS | RHS.
1943     KnownZero |= KnownZero2;
1944     break;
1945   case ISD::OR:
1946     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1947     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1949     // Output known-0 bits are only known if clear in both the LHS & RHS.
1950     KnownZero &= KnownZero2;
1951     // Output known-1 are known to be set if set in either the LHS | RHS.
1952     KnownOne |= KnownOne2;
1953     break;
1954   case ISD::XOR: {
1955     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1956     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1958     // Output known-0 bits are known if clear or set in both the LHS & RHS.
1959     APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1960     // Output known-1 are known to be set if set in only one of the LHS, RHS.
1961     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1962     KnownZero = KnownZeroOut;
1963     break;
1964   }
1965   case ISD::MUL: {
1966     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1967     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1969     // If low bits are zero in either operand, output low known-0 bits.
1970     // Also compute a conserative estimate for high known-0 bits.
1971     // More trickiness is possible, but this is sufficient for the
1972     // interesting case of alignment computation.
1973     KnownOne.clearAllBits();
1974     unsigned TrailZ = KnownZero.countTrailingOnes() +
1975                       KnownZero2.countTrailingOnes();
1976     unsigned LeadZ =  std::max(KnownZero.countLeadingOnes() +
1977                                KnownZero2.countLeadingOnes(),
1978                                BitWidth) - BitWidth;
1980     TrailZ = std::min(TrailZ, BitWidth);
1981     LeadZ = std::min(LeadZ, BitWidth);
1982     KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1983                 APInt::getHighBitsSet(BitWidth, LeadZ);
1984     break;
1985   }
1986   case ISD::UDIV: {
1987     // For the purposes of computing leading zeros we can conservatively
1988     // treat a udiv as a logical right shift by the power of 2 known to
1989     // be less than the denominator.
1990     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1991     unsigned LeadZ = KnownZero2.countLeadingOnes();
1993     KnownOne2.clearAllBits();
1994     KnownZero2.clearAllBits();
1995     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1996     unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1997     if (RHSUnknownLeadingOnes != BitWidth)
1998       LeadZ = std::min(BitWidth,
1999                        LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2001     KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2002     break;
2003   }
2004   case ISD::SELECT:
2005     computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2006     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2008     // Only known if known in both the LHS and RHS.
2009     KnownOne &= KnownOne2;
2010     KnownZero &= KnownZero2;
2011     break;
2012   case ISD::SELECT_CC:
2013     computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2014     computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2016     // Only known if known in both the LHS and RHS.
2017     KnownOne &= KnownOne2;
2018     KnownZero &= KnownZero2;
2019     break;
2020   case ISD::SADDO:
2021   case ISD::UADDO:
2022   case ISD::SSUBO:
2023   case ISD::USUBO:
2024   case ISD::SMULO:
2025   case ISD::UMULO:
2026     if (Op.getResNo() != 1)
2027       break;
2028     // The boolean result conforms to getBooleanContents.
2029     // If we know the result of a setcc has the top bits zero, use this info.
2030     // We know that we have an integer-based boolean since these operations
2031     // are only available for integer.
2032     if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2033             TargetLowering::ZeroOrOneBooleanContent &&
2034         BitWidth > 1)
2035       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2036     break;
2037   case ISD::SETCC:
2038     // If we know the result of a setcc has the top bits zero, use this info.
2039     if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2040             TargetLowering::ZeroOrOneBooleanContent &&
2041         BitWidth > 1)
2042       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2043     break;
2044   case ISD::SHL:
2045     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
2046     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2047       unsigned ShAmt = SA->getZExtValue();
2049       // If the shift count is an invalid immediate, don't do anything.
2050       if (ShAmt >= BitWidth)
2051         break;
2053       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2054       KnownZero <<= ShAmt;
2055       KnownOne  <<= ShAmt;
2056       // low bits known zero.
2057       KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2058     }
2059     break;
2060   case ISD::SRL:
2061     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
2062     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2063       unsigned ShAmt = SA->getZExtValue();
2065       // If the shift count is an invalid immediate, don't do anything.
2066       if (ShAmt >= BitWidth)
2067         break;
2069       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2070       KnownZero = KnownZero.lshr(ShAmt);
2071       KnownOne  = KnownOne.lshr(ShAmt);
2073       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2074       KnownZero |= HighBits;  // High bits known zero.
2075     }
2076     break;
2077   case ISD::SRA:
2078     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2079       unsigned ShAmt = SA->getZExtValue();
2081       // If the shift count is an invalid immediate, don't do anything.
2082       if (ShAmt >= BitWidth)
2083         break;
2085       // If any of the demanded bits are produced by the sign extension, we also
2086       // demand the input sign bit.
2087       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2089       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2090       KnownZero = KnownZero.lshr(ShAmt);
2091       KnownOne  = KnownOne.lshr(ShAmt);
2093       // Handle the sign bits.
2094       APInt SignBit = APInt::getSignBit(BitWidth);
2095       SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
2097       if (KnownZero.intersects(SignBit)) {
2098         KnownZero |= HighBits;  // New bits are known zero.
2099       } else if (KnownOne.intersects(SignBit)) {
2100         KnownOne  |= HighBits;  // New bits are known one.
2101       }
2102     }
2103     break;
2104   case ISD::SIGN_EXTEND_INREG: {
2105     EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2106     unsigned EBits = EVT.getScalarType().getSizeInBits();
2108     // Sign extension.  Compute the demanded bits in the result that are not
2109     // present in the input.
2110     APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2112     APInt InSignBit = APInt::getSignBit(EBits);
2113     APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2115     // If the sign extended bits are demanded, we know that the sign
2116     // bit is demanded.
2117     InSignBit = InSignBit.zext(BitWidth);
2118     if (NewBits.getBoolValue())
2119       InputDemandedBits |= InSignBit;
2121     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2122     KnownOne &= InputDemandedBits;
2123     KnownZero &= InputDemandedBits;
2125     // If the sign bit of the input is known set or clear, then we know the
2126     // top bits of the result.
2127     if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
2128       KnownZero |= NewBits;
2129       KnownOne  &= ~NewBits;
2130     } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
2131       KnownOne  |= NewBits;
2132       KnownZero &= ~NewBits;
2133     } else {                              // Input sign bit unknown
2134       KnownZero &= ~NewBits;
2135       KnownOne  &= ~NewBits;
2136     }
2137     break;
2138   }
2139   case ISD::CTTZ:
2140   case ISD::CTTZ_ZERO_UNDEF:
2141   case ISD::CTLZ:
2142   case ISD::CTLZ_ZERO_UNDEF:
2143   case ISD::CTPOP: {
2144     unsigned LowBits = Log2_32(BitWidth)+1;
2145     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2146     KnownOne.clearAllBits();
2147     break;
2148   }
2149   case ISD::LOAD: {
2150     LoadSDNode *LD = cast<LoadSDNode>(Op);
2151     // If this is a ZEXTLoad and we are looking at the loaded value.
2152     if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2153       EVT VT = LD->getMemoryVT();
2154       unsigned MemBits = VT.getScalarType().getSizeInBits();
2155       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2156     } else if (const MDNode *Ranges = LD->getRanges()) {
2157       computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2158     }
2159     break;
2160   }
2161   case ISD::ZERO_EXTEND: {
2162     EVT InVT = Op.getOperand(0).getValueType();
2163     unsigned InBits = InVT.getScalarType().getSizeInBits();
2164     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2165     KnownZero = KnownZero.trunc(InBits);
2166     KnownOne = KnownOne.trunc(InBits);
2167     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2168     KnownZero = KnownZero.zext(BitWidth);
2169     KnownOne = KnownOne.zext(BitWidth);
2170     KnownZero |= NewBits;
2171     break;
2172   }
2173   case ISD::SIGN_EXTEND: {
2174     EVT InVT = Op.getOperand(0).getValueType();
2175     unsigned InBits = InVT.getScalarType().getSizeInBits();
2176     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2178     KnownZero = KnownZero.trunc(InBits);
2179     KnownOne = KnownOne.trunc(InBits);
2180     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2182     // Note if the sign bit is known to be zero or one.
2183     bool SignBitKnownZero = KnownZero.isNegative();
2184     bool SignBitKnownOne  = KnownOne.isNegative();
2186     KnownZero = KnownZero.zext(BitWidth);
2187     KnownOne = KnownOne.zext(BitWidth);
2189     // If the sign bit is known zero or one, the top bits match.
2190     if (SignBitKnownZero)
2191       KnownZero |= NewBits;
2192     else if (SignBitKnownOne)
2193       KnownOne  |= NewBits;
2194     break;
2195   }
2196   case ISD::ANY_EXTEND: {
2197     EVT InVT = Op.getOperand(0).getValueType();
2198     unsigned InBits = InVT.getScalarType().getSizeInBits();
2199     KnownZero = KnownZero.trunc(InBits);
2200     KnownOne = KnownOne.trunc(InBits);
2201     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2202     KnownZero = KnownZero.zext(BitWidth);
2203     KnownOne = KnownOne.zext(BitWidth);
2204     break;
2205   }
2206   case ISD::TRUNCATE: {
2207     EVT InVT = Op.getOperand(0).getValueType();
2208     unsigned InBits = InVT.getScalarType().getSizeInBits();
2209     KnownZero = KnownZero.zext(InBits);
2210     KnownOne = KnownOne.zext(InBits);
2211     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2212     KnownZero = KnownZero.trunc(BitWidth);
2213     KnownOne = KnownOne.trunc(BitWidth);
2214     break;
2215   }
2216   case ISD::AssertZext: {
2217     EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2218     APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2219     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2220     KnownZero |= (~InMask);
2221     KnownOne  &= (~KnownZero);
2222     break;
2223   }
2224   case ISD::FGETSIGN:
2225     // All bits are zero except the low bit.
2226     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2227     break;
2229   case ISD::SUB: {
2230     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2231       // We know that the top bits of C-X are clear if X contains less bits
2232       // than C (i.e. no wrap-around can happen).  For example, 20-X is
2233       // positive if we can prove that X is >= 0 and < 16.
2234       if (CLHS->getAPIntValue().isNonNegative()) {
2235         unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2236         // NLZ can't be BitWidth with no sign bit
2237         APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2238         computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2240         // If all of the MaskV bits are known to be zero, then we know the
2241         // output top bits are zero, because we now know that the output is
2242         // from [0-C].
2243         if ((KnownZero2 & MaskV) == MaskV) {
2244           unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2245           // Top bits known zero.
2246           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2247         }
2248       }
2249     }
2250   }
2251   // fall through
2252   case ISD::ADD:
2253   case ISD::ADDE: {
2254     // Output known-0 bits are known if clear or set in both the low clear bits
2255     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
2256     // low 3 bits clear.
2257     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2258     unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2260     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2261     KnownZeroOut = std::min(KnownZeroOut,
2262                             KnownZero2.countTrailingOnes());
2264     if (Op.getOpcode() == ISD::ADD) {
2265       KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2266       break;
2267     }
2269     // With ADDE, a carry bit may be added in, so we can only use this
2270     // information if we know (at least) that the low two bits are clear.  We
2271     // then return to the caller that the low bit is unknown but that other bits
2272     // are known zero.
2273     if (KnownZeroOut >= 2) // ADDE
2274       KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2275     break;
2276   }
2277   case ISD::SREM:
2278     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2279       const APInt &RA = Rem->getAPIntValue().abs();
2280       if (RA.isPowerOf2()) {
2281         APInt LowBits = RA - 1;
2282         computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2284         // The low bits of the first operand are unchanged by the srem.
2285         KnownZero = KnownZero2 & LowBits;
2286         KnownOne = KnownOne2 & LowBits;
2288         // If the first operand is non-negative or has all low bits zero, then
2289         // the upper bits are all zero.
2290         if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2291           KnownZero |= ~LowBits;
2293         // If the first operand is negative and not all low bits are zero, then
2294         // the upper bits are all one.
2295         if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2296           KnownOne |= ~LowBits;
2297         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2298       }
2299     }
2300     break;
2301   case ISD::UREM: {
2302     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2303       const APInt &RA = Rem->getAPIntValue();
2304       if (RA.isPowerOf2()) {
2305         APInt LowBits = (RA - 1);
2306         computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2308         // The upper bits are all zero, the lower ones are unchanged.
2309         KnownZero = KnownZero2 | ~LowBits;
2310         KnownOne = KnownOne2 & LowBits;
2311         break;
2312       }
2313     }
2315     // Since the result is less than or equal to either operand, any leading
2316     // zero bits in either operand must also exist in the result.
2317     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2318     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2320     uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2321                                 KnownZero2.countLeadingOnes());
2322     KnownOne.clearAllBits();
2323     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2324     break;
2325   }
2326   case ISD::FrameIndex:
2327   case ISD::TargetFrameIndex:
2328     if (unsigned Align = InferPtrAlignment(Op)) {
2329       // The low bits are known zero if the pointer is aligned.
2330       KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2331       break;
2332     }
2333     break;
2335   default:
2336     if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2337       break;
2338     // Fallthrough
2339   case ISD::INTRINSIC_WO_CHAIN:
2340   case ISD::INTRINSIC_W_CHAIN:
2341   case ISD::INTRINSIC_VOID:
2342     // Allow the target to implement this method for its nodes.
2343     TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2344     break;
2345   }
2347   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2350 /// ComputeNumSignBits - Return the number of times the sign bit of the
2351 /// register is replicated into the other bits.  We know that at least 1 bit
2352 /// is always equal to the sign bit (itself), but other cases can give us
2353 /// information.  For example, immediately after an "SRA X, 2", we know that
2354 /// the top 3 bits are all equal to each other, so we return 3.
2355 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2356   EVT VT = Op.getValueType();
2357   assert(VT.isInteger() && "Invalid VT!");
2358   unsigned VTBits = VT.getScalarType().getSizeInBits();
2359   unsigned Tmp, Tmp2;
2360   unsigned FirstAnswer = 1;
2362   if (Depth == 6)
2363     return 1;  // Limit search depth.
2365   switch (Op.getOpcode()) {
2366   default: break;
2367   case ISD::AssertSext:
2368     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2369     return VTBits-Tmp+1;
2370   case ISD::AssertZext:
2371     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2372     return VTBits-Tmp;
2374   case ISD::Constant: {
2375     const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2376     return Val.getNumSignBits();
2377   }
2379   case ISD::SIGN_EXTEND:
2380     Tmp =
2381         VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2382     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2384   case ISD::SIGN_EXTEND_INREG:
2385     // Max of the input and what this extends.
2386     Tmp =
2387       cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2388     Tmp = VTBits-Tmp+1;
2390     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2391     return std::max(Tmp, Tmp2);
2393   case ISD::SRA:
2394     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2395     // SRA X, C   -> adds C sign bits.
2396     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2397       Tmp += C->getZExtValue();
2398       if (Tmp > VTBits) Tmp = VTBits;
2399     }
2400     return Tmp;
2401   case ISD::SHL:
2402     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2403       // shl destroys sign bits.
2404       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2405       if (C->getZExtValue() >= VTBits ||      // Bad shift.
2406           C->getZExtValue() >= Tmp) break;    // Shifted all sign bits out.
2407       return Tmp - C->getZExtValue();
2408     }
2409     break;
2410   case ISD::AND:
2411   case ISD::OR:
2412   case ISD::XOR:    // NOT is handled here.
2413     // Logical binary ops preserve the number of sign bits at the worst.
2414     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2415     if (Tmp != 1) {
2416       Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2417       FirstAnswer = std::min(Tmp, Tmp2);
2418       // We computed what we know about the sign bits as our first
2419       // answer. Now proceed to the generic code that uses
2420       // computeKnownBits, and pick whichever answer is better.
2421     }
2422     break;
2424   case ISD::SELECT:
2425     Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2426     if (Tmp == 1) return 1;  // Early out.
2427     Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2428     return std::min(Tmp, Tmp2);
2430   case ISD::SADDO:
2431   case ISD::UADDO:
2432   case ISD::SSUBO:
2433   case ISD::USUBO:
2434   case ISD::SMULO:
2435   case ISD::UMULO:
2436     if (Op.getResNo() != 1)
2437       break;
2438     // The boolean result conforms to getBooleanContents.  Fall through.
2439     // If setcc returns 0/-1, all bits are sign bits.
2440     // We know that we have an integer-based boolean since these operations
2441     // are only available for integer.
2442     if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2443         TargetLowering::ZeroOrNegativeOneBooleanContent)
2444       return VTBits;
2445     break;
2446   case ISD::SETCC:
2447     // If setcc returns 0/-1, all bits are sign bits.
2448     if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2449         TargetLowering::ZeroOrNegativeOneBooleanContent)
2450       return VTBits;
2451     break;
2452   case ISD::ROTL:
2453   case ISD::ROTR:
2454     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2455       unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2457       // Handle rotate right by N like a rotate left by 32-N.
2458       if (Op.getOpcode() == ISD::ROTR)
2459         RotAmt = (VTBits-RotAmt) & (VTBits-1);
2461       // If we aren't rotating out all of the known-in sign bits, return the
2462       // number that are left.  This handles rotl(sext(x), 1) for example.
2463       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2464       if (Tmp > RotAmt+1) return Tmp-RotAmt;
2465     }
2466     break;
2467   case ISD::ADD:
2468     // Add can have at most one carry bit.  Thus we know that the output
2469     // is, at worst, one more bit than the inputs.
2470     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2471     if (Tmp == 1) return 1;  // Early out.
2473     // Special case decrementing a value (ADD X, -1):
2474     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2475       if (CRHS->isAllOnesValue()) {
2476         APInt KnownZero, KnownOne;
2477         computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2479         // If the input is known to be 0 or 1, the output is 0/-1, which is all
2480         // sign bits set.
2481         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2482           return VTBits;
2484         // If we are subtracting one from a positive number, there is no carry
2485         // out of the result.
2486         if (KnownZero.isNegative())
2487           return Tmp;
2488       }
2490     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2491     if (Tmp2 == 1) return 1;
2492     return std::min(Tmp, Tmp2)-1;
2494   case ISD::SUB:
2495     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2496     if (Tmp2 == 1) return 1;
2498     // Handle NEG.
2499     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2500       if (CLHS->isNullValue()) {
2501         APInt KnownZero, KnownOne;
2502         computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2503         // If the input is known to be 0 or 1, the output is 0/-1, which is all
2504         // sign bits set.
2505         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2506           return VTBits;
2508         // If the input is known to be positive (the sign bit is known clear),
2509         // the output of the NEG has the same number of sign bits as the input.
2510         if (KnownZero.isNegative())
2511           return Tmp2;
2513         // Otherwise, we treat this like a SUB.
2514       }
2516     // Sub can have at most one carry bit.  Thus we know that the output
2517     // is, at worst, one more bit than the inputs.
2518     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2519     if (Tmp == 1) return 1;  // Early out.
2520     return std::min(Tmp, Tmp2)-1;
2521   case ISD::TRUNCATE:
2522     // FIXME: it's tricky to do anything useful for this, but it is an important
2523     // case for targets like X86.
2524     break;
2525   }
2527   // If we are looking at the loaded value of the SDNode.
2528   if (Op.getResNo() == 0) {
2529     // Handle LOADX separately here. EXTLOAD case will fallthrough.
2530     if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2531       unsigned ExtType = LD->getExtensionType();
2532       switch (ExtType) {
2533         default: break;
2534         case ISD::SEXTLOAD:    // '17' bits known
2535           Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2536           return VTBits-Tmp+1;
2537         case ISD::ZEXTLOAD:    // '16' bits known
2538           Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2539           return VTBits-Tmp;
2540       }
2541     }
2542   }
2544   // Allow the target to implement this method for its nodes.
2545   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2546       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2547       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2548       Op.getOpcode() == ISD::INTRINSIC_VOID) {
2549     unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2550     if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2551   }
2553   // Finally, if we can prove that the top bits of the result are 0's or 1's,
2554   // use this information.
2555   APInt KnownZero, KnownOne;
2556   computeKnownBits(Op, KnownZero, KnownOne, Depth);
2558   APInt Mask;
2559   if (KnownZero.isNegative()) {        // sign bit is 0
2560     Mask = KnownZero;
2561   } else if (KnownOne.isNegative()) {  // sign bit is 1;
2562     Mask = KnownOne;
2563   } else {
2564     // Nothing known.
2565     return FirstAnswer;
2566   }
2568   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
2569   // the number of identical bits in the top of the input value.
2570   Mask = ~Mask;
2571   Mask <<= Mask.getBitWidth()-VTBits;
2572   // Return # leading zeros.  We use 'min' here in case Val was zero before
2573   // shifting.  We don't want to return '64' as for an i32 "0".
2574   return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2577 /// isBaseWithConstantOffset - Return true if the specified operand is an
2578 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2579 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2580 /// semantics as an ADD.  This handles the equivalence:
2581 ///     X|Cst == X+Cst iff X&Cst = 0.
2582 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2583   if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2584       !isa<ConstantSDNode>(Op.getOperand(1)))
2585     return false;
2587   if (Op.getOpcode() == ISD::OR &&
2588       !MaskedValueIsZero(Op.getOperand(0),
2589                      cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2590     return false;
2592   return true;
2596 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2597   // If we're told that NaNs won't happen, assume they won't.
2598   if (getTarget().Options.NoNaNsFPMath)
2599     return true;
2601   // If the value is a constant, we can obviously see if it is a NaN or not.
2602   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2603     return !C->getValueAPF().isNaN();
2605   // TODO: Recognize more cases here.
2607   return false;
2610 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2611   // If the value is a constant, we can obviously see if it is a zero or not.
2612   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2613     return !C->isZero();
2615   // TODO: Recognize more cases here.
2616   switch (Op.getOpcode()) {
2617   default: break;
2618   case ISD::OR:
2619     if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2620       return !C->isNullValue();
2621     break;
2622   }
2624   return false;
2627 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2628   // Check the obvious case.
2629   if (A == B) return true;
2631   // For for negative and positive zero.
2632   if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2633     if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2634       if (CA->isZero() && CB->isZero()) return true;
2636   // Otherwise they may not be equal.
2637   return false;
2640 /// getNode - Gets or creates the specified node.
2641 ///
2642 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2643   FoldingSetNodeID ID;
2644   AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2645   void *IP = nullptr;
2646   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2647     return SDValue(E, 0);
2649   SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2650                                          DL.getDebugLoc(), getVTList(VT));
2651   CSEMap.InsertNode(N, IP);
2653   InsertNode(N);
2654   return SDValue(N, 0);
2657 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2658                               EVT VT, SDValue Operand) {
2659   // Constant fold unary operations with an integer constant operand. Even
2660   // opaque constant will be folded, because the folding of unary operations
2661   // doesn't create new constants with different values. Nevertheless, the
2662   // opaque flag is preserved during folding to prevent future folding with
2663   // other constants.
2664   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2665     const APInt &Val = C->getAPIntValue();
2666     switch (Opcode) {
2667     default: break;
2668     case ISD::SIGN_EXTEND:
2669       return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2670                          C->isTargetOpcode(), C->isOpaque());
2671     case ISD::ANY_EXTEND:
2672     case ISD::ZERO_EXTEND:
2673     case ISD::TRUNCATE:
2674       return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2675                          C->isTargetOpcode(), C->isOpaque());
2676     case ISD::UINT_TO_FP:
2677     case ISD::SINT_TO_FP: {
2678       APFloat apf(EVTToAPFloatSemantics(VT),
2679                   APInt::getNullValue(VT.getSizeInBits()));
2680       (void)apf.convertFromAPInt(Val,
2681                                  Opcode==ISD::SINT_TO_FP,
2682                                  APFloat::rmNearestTiesToEven);
2683       return getConstantFP(apf, VT);
2684     }
2685     case ISD::BITCAST:
2686       if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2687         return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2688       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2689         return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2690       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2691         return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2692       break;
2693     case ISD::BSWAP:
2694       return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2695                          C->isOpaque());
2696     case ISD::CTPOP:
2697       return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2698                          C->isOpaque());
2699     case ISD::CTLZ:
2700     case ISD::CTLZ_ZERO_UNDEF:
2701       return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2702                          C->isOpaque());
2703     case ISD::CTTZ:
2704     case ISD::CTTZ_ZERO_UNDEF:
2705       return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2706                          C->isOpaque());
2707     }
2708   }
2710   // Constant fold unary operations with a floating point constant operand.
2711   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2712     APFloat V = C->getValueAPF();    // make copy
2713     switch (Opcode) {
2714     case ISD::FNEG:
2715       V.changeSign();
2716       return getConstantFP(V, VT);
2717     case ISD::FABS:
2718       V.clearSign();
2719       return getConstantFP(V, VT);
2720     case ISD::FCEIL: {
2721       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2722       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2723         return getConstantFP(V, VT);
2724       break;
2725     }
2726     case ISD::FTRUNC: {
2727       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2728       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2729         return getConstantFP(V, VT);
2730       break;
2731     }
2732     case ISD::FFLOOR: {
2733       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2734       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2735         return getConstantFP(V, VT);
2736       break;
2737     }
2738     case ISD::FP_EXTEND: {
2739       bool ignored;
2740       // This can return overflow, underflow, or inexact; we don't care.
2741       // FIXME need to be more flexible about rounding mode.
2742       (void)V.convert(EVTToAPFloatSemantics(VT),
2743                       APFloat::rmNearestTiesToEven, &ignored);
2744       return getConstantFP(V, VT);
2745     }
2746     case ISD::FP_TO_SINT:
2747     case ISD::FP_TO_UINT: {
2748       integerPart x[2];
2749       bool ignored;
2750       static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2751       // FIXME need to be more flexible about rounding mode.
2752       APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2753                             Opcode==ISD::FP_TO_SINT,
2754                             APFloat::rmTowardZero, &ignored);
2755       if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
2756         break;
2757       APInt api(VT.getSizeInBits(), x);
2758       return getConstant(api, VT);
2759     }
2760     case ISD::BITCAST:
2761       if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2762         return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2763       else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2764         return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2765       else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2766         return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2767       break;
2768     }
2769   }
2771   // Constant fold unary operations with a vector integer operand.
2772   if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2773     if (BV->isConstant()) {
2774       switch (Opcode) {
2775       default:
2776         // FIXME: Entirely reasonable to perform folding of other unary
2777         // operations here as the need arises.
2778         break;
2779       case ISD::UINT_TO_FP:
2780       case ISD::SINT_TO_FP: {
2781         SmallVector<SDValue, 8> Ops;
2782         for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2783           SDValue OpN = BV->getOperand(i);
2784           // Let the above scalar folding handle the conversion of each
2785           // element.
2786           OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2787                         OpN);
2788           Ops.push_back(OpN);
2789         }
2790         return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2791       }
2792       }
2793     }
2794   }
2796   unsigned OpOpcode = Operand.getNode()->getOpcode();
2797   switch (Opcode) {
2798   case ISD::TokenFactor:
2799   case ISD::MERGE_VALUES:
2800   case ISD::CONCAT_VECTORS:
2801     return Operand;         // Factor, merge or concat of one node?  No need.
2802   case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2803   case ISD::FP_EXTEND:
2804     assert(VT.isFloatingPoint() &&
2805            Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2806     if (Operand.getValueType() == VT) return Operand;  // noop conversion.
2807     assert((!VT.isVector() ||
2808             VT.getVectorNumElements() ==
2809             Operand.getValueType().getVectorNumElements()) &&
2810            "Vector element count mismatch!");
2811     if (Operand.getOpcode() == ISD::UNDEF)
2812       return getUNDEF(VT);
2813     break;
2814   case ISD::SIGN_EXTEND:
2815     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2816            "Invalid SIGN_EXTEND!");
2817     if (Operand.getValueType() == VT) return Operand;   // noop extension
2818     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2819            "Invalid sext node, dst < src!");
2820     assert((!VT.isVector() ||
2821             VT.getVectorNumElements() ==
2822             Operand.getValueType().getVectorNumElements()) &&
2823            "Vector element count mismatch!");
2824     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2825       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2826     else if (OpOpcode == ISD::UNDEF)
2827       // sext(undef) = 0, because the top bits will all be the same.
2828       return getConstant(0, VT);
2829     break;
2830   case ISD::ZERO_EXTEND:
2831     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2832            "Invalid ZERO_EXTEND!");
2833     if (Operand.getValueType() == VT) return Operand;   // noop extension
2834     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2835            "Invalid zext node, dst < src!");
2836     assert((!VT.isVector() ||
2837             VT.getVectorNumElements() ==
2838             Operand.getValueType().getVectorNumElements()) &&
2839            "Vector element count mismatch!");
2840     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
2841       return getNode(ISD::ZERO_EXTEND, DL, VT,
2842                      Operand.getNode()->getOperand(0));
2843     else if (OpOpcode == ISD::UNDEF)
2844       // zext(undef) = 0, because the top bits will be zero.
2845       return getConstant(0, VT);
2846     break;
2847   case ISD::ANY_EXTEND:
2848     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2849            "Invalid ANY_EXTEND!");
2850     if (Operand.getValueType() == VT) return Operand;   // noop extension
2851     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2852            "Invalid anyext node, dst < src!");
2853     assert((!VT.isVector() ||
2854             VT.getVectorNumElements() ==
2855             Operand.getValueType().getVectorNumElements()) &&
2856            "Vector element count mismatch!");
2858     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2859         OpOpcode == ISD::ANY_EXTEND)
2860       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
2861       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2862     else if (OpOpcode == ISD::UNDEF)
2863       return getUNDEF(VT);
2865     // (ext (trunx x)) -> x
2866     if (OpOpcode == ISD::TRUNCATE) {
2867       SDValue OpOp = Operand.getNode()->getOperand(0);
2868       if (OpOp.getValueType() == VT)
2869         return OpOp;
2870     }
2871     break;
2872   case ISD::TRUNCATE:
2873     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2874            "Invalid TRUNCATE!");
2875     if (Operand.getValueType() == VT) return Operand;   // noop truncate
2876     assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2877            "Invalid truncate node, src < dst!");
2878     assert((!VT.isVector() ||
2879             VT.getVectorNumElements() ==
2880             Operand.getValueType().getVectorNumElements()) &&
2881            "Vector element count mismatch!");
2882     if (OpOpcode == ISD::TRUNCATE)
2883       return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2884     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2885         OpOpcode == ISD::ANY_EXTEND) {
2886       // If the source is smaller than the dest, we still need an extend.
2887       if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2888             .bitsLT(VT.getScalarType()))
2889         return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2890       if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2891         return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2892       return Operand.getNode()->getOperand(0);
2893     }
2894     if (OpOpcode == ISD::UNDEF)
2895       return getUNDEF(VT);
2896     break;
2897   case ISD::BITCAST:
2898     // Basic sanity checking.
2899     assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2900            && "Cannot BITCAST between types of different sizes!");
2901     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
2902     if (OpOpcode == ISD::BITCAST)  // bitconv(bitconv(x)) -> bitconv(x)
2903       return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2904     if (OpOpcode == ISD::UNDEF)
2905       return getUNDEF(VT);
2906     break;
2907   case ISD::SCALAR_TO_VECTOR:
2908     assert(VT.isVector() && !Operand.getValueType().isVector() &&
2909            (VT.getVectorElementType() == Operand.getValueType() ||
2910             (VT.getVectorElementType().isInteger() &&
2911              Operand.getValueType().isInteger() &&
2912              VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2913            "Illegal SCALAR_TO_VECTOR node!");
2914     if (OpOpcode == ISD::UNDEF)
2915       return getUNDEF(VT);
2916     // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2917     if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2918         isa<ConstantSDNode>(Operand.getOperand(1)) &&
2919         Operand.getConstantOperandVal(1) == 0 &&
2920         Operand.getOperand(0).getValueType() == VT)
2921       return Operand.getOperand(0);
2922     break;
2923   case ISD::FNEG:
2924     // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2925     if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2926       return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2927                      Operand.getNode()->getOperand(0));
2928     if (OpOpcode == ISD::FNEG)  // --X -> X
2929       return Operand.getNode()->getOperand(0);
2930     break;
2931   case ISD::FABS:
2932     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
2933       return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2934     break;
2935   }
2937   SDNode *N;
2938   SDVTList VTs = getVTList(VT);
2939   if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2940     FoldingSetNodeID ID;
2941     SDValue Ops[1] = { Operand };
2942     AddNodeIDNode(ID, Opcode, VTs, Ops);
2943     void *IP = nullptr;
2944     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2945       return SDValue(E, 0);
2947     N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2948                                         DL.getDebugLoc(), VTs, Operand);
2949     CSEMap.InsertNode(N, IP);
2950   } else {
2951     N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2952                                         DL.getDebugLoc(), VTs, Operand);
2953   }
2955   InsertNode(N);
2956   return SDValue(N, 0);
2959 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2960                                              SDNode *Cst1, SDNode *Cst2) {
2961   // If the opcode is a target-specific ISD node, there's nothing we can
2962   // do here and the operand rules may not line up with the below, so
2963   // bail early.
2964   if (Opcode >= ISD::BUILTIN_OP_END)
2965     return SDValue();
2967   SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2968   SmallVector<SDValue, 4> Outputs;
2969   EVT SVT = VT.getScalarType();
2971   ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2972   ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2973   if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2974     return SDValue();
2976   if (Scalar1 && Scalar2)
2977     // Scalar instruction.
2978     Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2979   else {
2980     // For vectors extract each constant element into Inputs so we can constant
2981     // fold them individually.
2982     BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2983     BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2984     if (!BV1 || !BV2)
2985       return SDValue();
2987     assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2989     for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2990       ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2991       ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2992       if (!V1 || !V2) // Not a constant, bail.
2993         return SDValue();
2995       if (V1->isOpaque() || V2->isOpaque())
2996         return SDValue();
2998       // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2999       // FIXME: This is valid and could be handled by truncating the APInts.
3000       if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3001         return SDValue();
3003       Inputs.push_back(std::make_pair(V1, V2));
3004     }
3005   }
3007   // We have a number of constant values, constant fold them element by element.
3008   for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3009     const APInt &C1 = Inputs[I].first->getAPIntValue();
3010     const APInt &C2 = Inputs[I].second->getAPIntValue();
3012     switch (Opcode) {
3013     case ISD::ADD:
3014       Outputs.push_back(getConstant(C1 + C2, SVT));
3015       break;
3016     case ISD::SUB:
3017       Outputs.push_back(getConstant(C1 - C2, SVT));
3018       break;
3019     case ISD::MUL:
3020       Outputs.push_back(getConstant(C1 * C2, SVT));
3021       break;
3022     case ISD::UDIV:
3023       if (!C2.getBoolValue())
3024         return SDValue();
3025       Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3026       break;
3027     case ISD::UREM:
3028       if (!C2.getBoolValue())
3029         return SDValue();
3030       Outputs.push_back(getConstant(C1.urem(C2), SVT));
3031       break;
3032     case ISD::SDIV:
3033       if (!C2.getBoolValue())
3034         return SDValue();
3035       Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3036       break;
3037     case ISD::SREM:
3038       if (!C2.getBoolValue())
3039         return SDValue();
3040       Outputs.push_back(getConstant(C1.srem(C2), SVT));
3041       break;
3042     case ISD::AND:
3043       Outputs.push_back(getConstant(C1 & C2, SVT));
3044       break;
3045     case ISD::OR:
3046       Outputs.push_back(getConstant(C1 | C2, SVT));
3047       break;
3048     case ISD::XOR:
3049       Outputs.push_back(getConstant(C1 ^ C2, SVT));
3050       break;
3051     case ISD::SHL:
3052       Outputs.push_back(getConstant(C1 << C2, SVT));
3053       break;
3054     case ISD::SRL:
3055       Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3056       break;
3057     case ISD::SRA:
3058       Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3059       break;
3060     case ISD::ROTL:
3061       Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3062       break;
3063     case ISD::ROTR:
3064       Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3065       break;
3066     default:
3067       return SDValue();
3068     }
3069   }
3071   assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3072                                   "Expected a scalar or vector!"));
3074   // Handle the scalar case first.
3075   if (!VT.isVector())
3076     return Outputs.back();
3078   // We may have a vector type but a scalar result. Create a splat.
3079   Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3081   // Build a big vector out of the scalar elements we generated.
3082   return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3085 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3086                               SDValue N2, bool nuw, bool nsw, bool exact) {
3087   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3088   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3089   switch (Opcode) {
3090   default: break;
3091   case ISD::TokenFactor:
3092     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3093            N2.getValueType() == MVT::Other && "Invalid token factor!");
3094     // Fold trivial token factors.
3095     if (N1.getOpcode() == ISD::EntryToken) return N2;
3096     if (N2.getOpcode() == ISD::EntryToken) return N1;
3097     if (N1 == N2) return N1;
3098     break;
3099   case ISD::CONCAT_VECTORS:
3100     // Concat of UNDEFs is UNDEF.
3101     if (N1.getOpcode() == ISD::UNDEF &&
3102         N2.getOpcode() == ISD::UNDEF)
3103       return getUNDEF(VT);
3105     // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3106     // one big BUILD_VECTOR.
3107     if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3108         N2.getOpcode() == ISD::BUILD_VECTOR) {
3109       SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3110                                     N1.getNode()->op_end());
3111       Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3112       return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3113     }
3114     break;
3115   case ISD::AND:
3116     assert(VT.isInteger() && "This operator does not apply to FP types!");
3117     assert(N1.getValueType() == N2.getValueType() &&
3118            N1.getValueType() == VT && "Binary operator types must match!");
3119     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
3120     // worth handling here.
3121     if (N2C && N2C->isNullValue())
3122       return N2;
3123     if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
3124       return N1;
3125     break;
3126   case ISD::OR:
3127   case ISD::XOR:
3128   case ISD::ADD:
3129   case ISD::SUB:
3130     assert(VT.isInteger() && "This operator does not apply to FP types!");
3131     assert(N1.getValueType() == N2.getValueType() &&
3132            N1.getValueType() == VT && "Binary operator types must match!");
3133     // (X ^|+- 0) -> X.  This commonly occurs when legalizing i64 values, so
3134     // it's worth handling here.
3135     if (N2C && N2C->isNullValue())
3136       return N1;
3137     break;
3138   case ISD::UDIV:
3139   case ISD::UREM:
3140   case ISD::MULHU:
3141   case ISD::MULHS:
3142   case ISD::MUL:
3143   case ISD::SDIV:
3144   case ISD::SREM:
3145     assert(VT.isInteger() && "This operator does not apply to FP types!");
3146     assert(N1.getValueType() == N2.getValueType() &&
3147            N1.getValueType() == VT && "Binary operator types must match!");
3148     break;
3149   case ISD::FADD:
3150   case ISD::FSUB:
3151   case ISD::FMUL:
3152   case ISD::FDIV:
3153   case ISD::FREM:
3154     if (getTarget().Options.UnsafeFPMath) {
3155       if (Opcode == ISD::FADD) {
3156         // 0+x --> x
3157         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3158           if (CFP->getValueAPF().isZero())
3159             return N2;
3160         // x+0 --> x
3161         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3162           if (CFP->getValueAPF().isZero())
3163             return N1;
3164       } else if (Opcode == ISD::FSUB) {
3165         // x-0 --> x
3166         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3167           if (CFP->getValueAPF().isZero())
3168             return N1;
3169       } else if (Opcode == ISD::FMUL) {
3170         ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3171         SDValue V = N2;
3173         // If the first operand isn't the constant, try the second
3174         if (!CFP) {
3175           CFP = dyn_cast<ConstantFPSDNode>(N2);
3176           V = N1;
3177         }
3179         if (CFP) {
3180           // 0*x --> 0
3181           if (CFP->isZero())
3182             return SDValue(CFP,0);
3183           // 1*x --> x
3184           if (CFP->isExactlyValue(1.0))
3185             return V;
3186         }
3187       }
3188     }
3189     assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3190     assert(N1.getValueType() == N2.getValueType() &&
3191            N1.getValueType() == VT && "Binary operator types must match!");
3192     break;
3193   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
3194     assert(N1.getValueType() == VT &&
3195            N1.getValueType().isFloatingPoint() &&
3196            N2.getValueType().isFloatingPoint() &&
3197            "Invalid FCOPYSIGN!");
3198     break;
3199   case ISD::SHL:
3200   case ISD::SRA:
3201   case ISD::SRL:
3202   case ISD::ROTL:
3203   case ISD::ROTR:
3204     assert(VT == N1.getValueType() &&
3205            "Shift operators return type must be the same as their first arg");
3206     assert(VT.isInteger() && N2.getValueType().isInteger() &&
3207            "Shifts only work on integers");
3208     assert((!VT.isVector() || VT == N2.getValueType()) &&
3209            "Vector shift amounts must be in the same as their first arg");
3210     // Verify that the shift amount VT is bit enough to hold valid shift
3211     // amounts.  This catches things like trying to shift an i1024 value by an
3212     // i8, which is easy to fall into in generic code that uses
3213     // TLI.getShiftAmount().
3214     assert(N2.getValueType().getSizeInBits() >=
3215                    Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3216            "Invalid use of small shift amount with oversized value!");
3218     // Always fold shifts of i1 values so the code generator doesn't need to
3219     // handle them.  Since we know the size of the shift has to be less than the
3220     // size of the value, the shift/rotate count is guaranteed to be zero.
3221     if (VT == MVT::i1)
3222       return N1;
3223     if (N2C && N2C->isNullValue())
3224       return N1;
3225     break;
3226   case ISD::FP_ROUND_INREG: {
3227     EVT EVT = cast<VTSDNode>(N2)->getVT();
3228     assert(VT == N1.getValueType() && "Not an inreg round!");
3229     assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3230            "Cannot FP_ROUND_INREG integer types");
3231     assert(EVT.isVector() == VT.isVector() &&
3232            "FP_ROUND_INREG type should be vector iff the operand "
3233            "type is vector!");
3234     assert((!EVT.isVector() ||
3235             EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3236            "Vector element counts must match in FP_ROUND_INREG");
3237     assert(EVT.bitsLE(VT) && "Not rounding down!");
3238     (void)EVT;
3239     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
3240     break;
3241   }
3242   case ISD::FP_ROUND:
3243     assert(VT.isFloatingPoint() &&
3244            N1.getValueType().isFloatingPoint() &&
3245            VT.bitsLE(N1.getValueType()) &&
3246            isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3247     if (N1.getValueType() == VT) return N1;  // noop conversion.
3248     break;
3249   case ISD::AssertSext:
3250   case ISD::AssertZext: {
3251     EVT EVT = cast<VTSDNode>(N2)->getVT();
3252     assert(VT == N1.getValueType() && "Not an inreg extend!");
3253     assert(VT.isInteger() && EVT.isInteger() &&
3254            "Cannot *_EXTEND_INREG FP types");
3255     assert(!EVT.isVector() &&
3256            "AssertSExt/AssertZExt type should be the vector element type "
3257            "rather than the vector type!");
3258     assert(EVT.bitsLE(VT) && "Not extending!");
3259     if (VT == EVT) return N1; // noop assertion.
3260     break;
3261   }
3262   case ISD::SIGN_EXTEND_INREG: {
3263     EVT EVT = cast<VTSDNode>(N2)->getVT();
3264     assert(VT == N1.getValueType() && "Not an inreg extend!");
3265     assert(VT.isInteger() && EVT.isInteger() &&
3266            "Cannot *_EXTEND_INREG FP types");
3267     assert(EVT.isVector() == VT.isVector() &&
3268            "SIGN_EXTEND_INREG type should be vector iff the operand "
3269            "type is vector!");
3270     assert((!EVT.isVector() ||
3271             EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3272            "Vector element counts must match in SIGN_EXTEND_INREG");
3273     assert(EVT.bitsLE(VT) && "Not extending!");
3274     if (EVT == VT) return N1;  // Not actually extending
3276     if (N1C) {
3277       APInt Val = N1C->getAPIntValue();
3278       unsigned FromBits = EVT.getScalarType().getSizeInBits();
3279       Val <<= Val.getBitWidth()-FromBits;
3280       Val = Val.ashr(Val.getBitWidth()-FromBits);
3281       return getConstant(Val, VT);
3282     }
3283     break;
3284   }
3285   case ISD::EXTRACT_VECTOR_ELT:
3286     // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3287     if (N1.getOpcode() == ISD::UNDEF)
3288       return getUNDEF(VT);
3290     // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3291     // expanding copies of large vectors from registers.
3292     if (N2C &&
3293         N1.getOpcode() == ISD::CONCAT_VECTORS &&
3294         N1.getNumOperands() > 0) {
3295       unsigned Factor =
3296         N1.getOperand(0).getValueType().getVectorNumElements();
3297       return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3298                      N1.getOperand(N2C->getZExtValue() / Factor),
3299                      getConstant(N2C->getZExtValue() % Factor,
3300                                  N2.getValueType()));
3301     }
3303     // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3304     // expanding large vector constants.
3305     if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3306       SDValue Elt = N1.getOperand(N2C->getZExtValue());
3308       if (VT != Elt.getValueType())
3309         // If the vector element type is not legal, the BUILD_VECTOR operands
3310         // are promoted and implicitly truncated, and the result implicitly
3311         // extended. Make that explicit here.
3312         Elt = getAnyExtOrTrunc(Elt, DL, VT);
3314       return Elt;
3315     }
3317     // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3318     // operations are lowered to scalars.
3319     if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3320       // If the indices are the same, return the inserted element else
3321       // if the indices are known different, extract the element from
3322       // the original vector.
3323       SDValue N1Op2 = N1.getOperand(2);
3324       ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3326       if (N1Op2C && N2C) {
3327         if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3328           if (VT == N1.getOperand(1).getValueType())
3329             return N1.getOperand(1);
3330           else
3331             return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3332         }
3334         return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3335       }
3336     }
3337     break;
3338   case ISD::EXTRACT_ELEMENT:
3339     assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3340     assert(!N1.getValueType().isVector() && !VT.isVector() &&
3341            (N1.getValueType().isInteger() == VT.isInteger()) &&
3342            N1.getValueType() != VT &&
3343            "Wrong types for EXTRACT_ELEMENT!");
3345     // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3346     // 64-bit integers into 32-bit parts.  Instead of building the extract of
3347     // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3348     if (N1.getOpcode() == ISD::BUILD_PAIR)
3349       return N1.getOperand(N2C->getZExtValue());
3351     // EXTRACT_ELEMENT of a constant int is also very common.
3352     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3353       unsigned ElementSize = VT.getSizeInBits();
3354       unsigned Shift = ElementSize * N2C->getZExtValue();
3355       APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3356       return getConstant(ShiftedVal.trunc(ElementSize), VT);
3357     }
3358     break;
3359   case ISD::EXTRACT_SUBVECTOR: {
3360     SDValue Index = N2;
3361     if (VT.isSimple() && N1.getValueType().isSimple()) {
3362       assert(VT.isVector() && N1.getValueType().isVector() &&
3363              "Extract subvector VTs must be a vectors!");
3364       assert(VT.getVectorElementType() ==
3365              N1.getValueType().getVectorElementType() &&
3366              "Extract subvector VTs must have the same element type!");
3367       assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3368              "Extract subvector must be from larger vector to smaller vector!");
3370       if (isa<ConstantSDNode>(Index.getNode())) {
3371         assert((VT.getVectorNumElements() +
3372                 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3373                 <= N1.getValueType().getVectorNumElements())
3374                && "Extract subvector overflow!");
3375       }
3377       // Trivial extraction.
3378       if (VT.getSimpleVT() == N1.getSimpleValueType())
3379         return N1;
3380     }
3381     break;
3382   }
3383   }
3385   // Perform trivial constant folding.
3386   if (SDValue SV =
3387           FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3388     return SV;
3390   // Canonicalize constant to RHS if commutative.
3391   if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3392     std::swap(N1C, N2C);
3393     std::swap(N1, N2);
3394   }
3396   // Constant fold FP operations.
3397   bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3398   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3399   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3400   if (N1CFP) {
3401     if (!N2CFP && isCommutativeBinOp(Opcode)) {
3402       // Canonicalize constant to RHS if commutative.
3403       std::swap(N1CFP, N2CFP);
3404       std::swap(N1, N2);
3405     } else if (N2CFP) {
3406       APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3407       APFloat::opStatus s;
3408       switch (Opcode) {
3409       case ISD::FADD:
3410         s = V1.add(V2, APFloat::rmNearestTiesToEven);
3411         if (!HasFPExceptions || s != APFloat::opInvalidOp)
3412           return getConstantFP(V1, VT);
3413         break;
3414       case ISD::FSUB:
3415         s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3416         if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3417           return getConstantFP(V1, VT);
3418         break;
3419       case ISD::FMUL:
3420         s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3421         if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3422           return getConstantFP(V1, VT);
3423         break;
3424       case ISD::FDIV:
3425         s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3426         if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3427                                  s!=APFloat::opDivByZero)) {
3428           return getConstantFP(V1, VT);
3429         }
3430         break;
3431       case ISD::FREM :
3432         s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3433         if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3434                                  s!=APFloat::opDivByZero)) {
3435           return getConstantFP(V1, VT);
3436         }
3437         break;
3438       case ISD::FCOPYSIGN:
3439         V1.copySign(V2);
3440         return getConstantFP(V1, VT);
3441       default: break;
3442       }
3443     }
3445     if (Opcode == ISD::FP_ROUND) {
3446       APFloat V = N1CFP->getValueAPF();    // make copy
3447       bool ignored;
3448       // This can return overflow, underflow, or inexact; we don't care.
3449       // FIXME need to be more flexible about rounding mode.
3450       (void)V.convert(EVTToAPFloatSemantics(VT),
3451                       APFloat::rmNearestTiesToEven, &ignored);
3452       return getConstantFP(V, VT);
3453     }
3454   }
3456   // Canonicalize an UNDEF to the RHS, even over a constant.
3457   if (N1.getOpcode() == ISD::UNDEF) {
3458     if (isCommutativeBinOp(Opcode)) {
3459       std::swap(N1, N2);
3460     } else {
3461       switch (Opcode) {
3462       case ISD::FP_ROUND_INREG:
3463       case ISD::SIGN_EXTEND_INREG:
3464       case ISD::SUB:
3465       case ISD::FSUB:
3466       case ISD::FDIV:
3467       case ISD::FREM:
3468       case ISD::SRA:
3469         return N1;     // fold op(undef, arg2) -> undef
3470       case ISD::UDIV:
3471       case ISD::SDIV:
3472       case ISD::UREM:
3473       case ISD::SREM:
3474       case ISD::SRL:
3475       case ISD::SHL:
3476         if (!VT.isVector())
3477           return getConstant(0, VT);    // fold op(undef, arg2) -> 0
3478         // For vectors, we can't easily build an all zero vector, just return
3479         // the LHS.
3480         return N2;
3481       }
3482     }
3483   }
3485   // Fold a bunch of operators when the RHS is undef.
3486   if (N2.getOpcode() == ISD::UNDEF) {
3487     switch (Opcode) {
3488     case ISD::XOR:
3489       if (N1.getOpcode() == ISD::UNDEF)
3490         // Handle undef ^ undef -> 0 special case. This is a common
3491         // idiom (misuse).
3492         return getConstant(0, VT);
3493       // fallthrough
3494     case ISD::ADD:
3495     case ISD::ADDC:
3496     case ISD::ADDE:
3497     case ISD::SUB:
3498     case ISD::UDIV:
3499     case ISD::SDIV:
3500     case ISD::UREM:
3501     case ISD::SREM:
3502       return N2;       // fold op(arg1, undef) -> undef
3503     case ISD::FADD:
3504     case ISD::FSUB:
3505     case ISD::FMUL:
3506     case ISD::FDIV:
3507     case ISD::FREM:
3508       if (getTarget().Options.UnsafeFPMath)
3509         return N2;
3510       break;
3511     case ISD::MUL:
3512     case ISD::AND:
3513     case ISD::SRL:
3514     case ISD::SHL:
3515       if (!VT.isVector())
3516         return getConstant(0, VT);  // fold op(arg1, undef) -> 0
3517       // For vectors, we can't easily build an all zero vector, just return
3518       // the LHS.
3519       return N1;
3520     case ISD::OR:
3521       if (!VT.isVector())
3522         return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3523       // For vectors, we can't easily build an all one vector, just return
3524       // the LHS.
3525       return N1;
3526     case ISD::SRA:
3527       return N1;
3528     }
3529   }
3531   // Memoize this node if possible.
3532   BinarySDNode *N;
3533   SDVTList VTs = getVTList(VT);
3534   const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3535   if (VT != MVT::Glue) {
3536     SDValue Ops[] = {N1, N2};
3537     FoldingSetNodeID ID;
3538     AddNodeIDNode(ID, Opcode, VTs, Ops);
3539     if (BinOpHasFlags)
3540       AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3541     void *IP = nullptr;
3542     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3543       return SDValue(E, 0);
3545     N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3547     CSEMap.InsertNode(N, IP);
3548   } else {
3550     N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3551   }
3553   InsertNode(N);
3554   return SDValue(N, 0);
3557 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3558                               SDValue N1, SDValue N2, SDValue N3) {
3559   // Perform various simplifications.
3560   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3561   switch (Opcode) {
3562   case ISD::FMA: {
3563     ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3564     ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3565     ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3566     if (N1CFP && N2CFP && N3CFP) {
3567       APFloat  V1 = N1CFP->getValueAPF();
3568       const APFloat &V2 = N2CFP->getValueAPF();
3569       const APFloat &V3 = N3CFP->getValueAPF();
3570       APFloat::opStatus s =
3571         V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3572       if (s != APFloat::opInvalidOp)
3573         return getConstantFP(V1, VT);
3574     }
3575     break;
3576   }
3577   case ISD::CONCAT_VECTORS:
3578     // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3579     // one big BUILD_VECTOR.
3580     if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3581         N2.getOpcode() == ISD::BUILD_VECTOR &&
3582         N3.getOpcode() == ISD::BUILD_VECTOR) {
3583       SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3584                                     N1.getNode()->op_end());
3585       Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3586       Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3587       return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3588     }
3589     break;
3590   case ISD::SETCC: {
3591     // Use FoldSetCC to simplify SETCC's.
3592     SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3593     if (Simp.getNode()) return Simp;
3594     break;
3595   }
3596   case ISD::SELECT:
3597     if (N1C) {
3598      if (N1C->getZExtValue())
3599        return N2;             // select true, X, Y -> X
3600      return N3;             // select false, X, Y -> Y
3601     }
3603     if (N2 == N3) return N2;   // select C, X, X -> X
3604     break;
3605   case ISD::VECTOR_SHUFFLE:
3606     llvm_unreachable("should use getVectorShuffle constructor!");
3607   case ISD::INSERT_SUBVECTOR: {
3608     SDValue Index = N3;
3609     if (VT.isSimple() && N1.getValueType().isSimple()
3610         && N2.getValueType().isSimple()) {
3611       assert(VT.isVector() && N1.getValueType().isVector() &&
3612              N2.getValueType().isVector() &&
3613              "Insert subvector VTs must be a vectors");
3614       assert(VT == N1.getValueType() &&
3615              "Dest and insert subvector source types must match!");
3616       assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3617              "Insert subvector must be from smaller vector to larger vector!");
3618       if (isa<ConstantSDNode>(Index.getNode())) {
3619         assert((N2.getValueType().getVectorNumElements() +
3620                 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3621                 <= VT.getVectorNumElements())
3622                && "Insert subvector overflow!");
3623       }
3625       // Trivial insertion.
3626       if (VT.getSimpleVT() == N2.getSimpleValueType())
3627         return N2;
3628     }
3629     break;
3630   }
3631   case ISD::BITCAST:
3632     // Fold bit_convert nodes from a type to themselves.
3633     if (N1.getValueType() == VT)
3634       return N1;
3635     break;
3636   }
3638   // Memoize node if it doesn't produce a flag.
3639   SDNode *N;
3640   SDVTList VTs = getVTList(VT);
3641   if (VT != MVT::Glue) {
3642     SDValue Ops[] = { N1, N2, N3 };
3643     FoldingSetNodeID ID;
3644     AddNodeIDNode(ID, Opcode, VTs, Ops);
3645     void *IP = nullptr;
3646     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3647       return SDValue(E, 0);
3649     N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3650                                           DL.getDebugLoc(), VTs, N1, N2, N3);
3651     CSEMap.InsertNode(N, IP);
3652   } else {
3653     N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3654                                           DL.getDebugLoc(), VTs, N1, N2, N3);
3655   }
3657   InsertNode(N);
3658   return SDValue(N, 0);
3661 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3662                               SDValue N1, SDValue N2, SDValue N3,
3663                               SDValue N4) {
3664   SDValue Ops[] = { N1, N2, N3, N4 };
3665   return getNode(Opcode, DL, VT, Ops);
3668 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3669                               SDValue N1, SDValue N2, SDValue N3,
3670                               SDValue N4, SDValue N5) {
3671   SDValue Ops[] = { N1, N2, N3, N4, N5 };
3672   return getNode(Opcode, DL, VT, Ops);
3675 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3676 /// the incoming stack arguments to be loaded from the stack.
3677 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3678   SmallVector<SDValue, 8> ArgChains;
3680   // Include the original chain at the beginning of the list. When this is
3681   // used by target LowerCall hooks, this helps legalize find the
3682   // CALLSEQ_BEGIN node.
3683   ArgChains.push_back(Chain);
3685   // Add a chain value for each stack argument.
3686   for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3687        UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3688     if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3689       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3690         if (FI->getIndex() < 0)
3691           ArgChains.push_back(SDValue(L, 1));
3693   // Build a tokenfactor for all the chains.
3694   return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3697 /// getMemsetValue - Vectorized representation of the memset value
3698 /// operand.
3699 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3700                               SDLoc dl) {
3701   assert(Value.getOpcode() != ISD::UNDEF);
3703   unsigned NumBits = VT.getScalarType().getSizeInBits();
3704   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3705     assert(C->getAPIntValue().getBitWidth() == 8);
3706     APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3707     if (VT.isInteger())
3708       return DAG.getConstant(Val, VT);
3709     return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3710   }
3712   Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3713   if (NumBits > 8) {
3714     // Use a multiplication with 0x010101... to extend the input to the
3715     // required length.
3716     APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3717     Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3718   }
3720   return Value;
3723 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3724 /// used when a memcpy is turned into a memset when the source is a constant
3725 /// string ptr.
3726 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3727                                   const TargetLowering &TLI, StringRef Str) {
3728   // Handle vector with all elements zero.
3729   if (Str.empty()) {
3730     if (VT.isInteger())
3731       return DAG.getConstant(0, VT);
3732     else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3733       return DAG.getConstantFP(0.0, VT);
3734     else if (VT.isVector()) {
3735       unsigned NumElts = VT.getVectorNumElements();
3736       MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3737       return DAG.getNode(ISD::BITCAST, dl, VT,
3738                          DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3739                                                              EltVT, NumElts)));
3740     } else
3741       llvm_unreachable("Expected type!");
3742   }
3744   assert(!VT.isVector() && "Can't handle vector type here!");
3745   unsigned NumVTBits = VT.getSizeInBits();
3746   unsigned NumVTBytes = NumVTBits / 8;
3747   unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3749   APInt Val(NumVTBits, 0);
3750   if (TLI.isLittleEndian()) {
3751     for (unsigned i = 0; i != NumBytes; ++i)
3752       Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3753   } else {
3754     for (unsigned i = 0; i != NumBytes; ++i)
3755       Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3756   }
3758   // If the "cost" of materializing the integer immediate is less than the cost
3759   // of a load, then it is cost effective to turn the load into the immediate.
3760   Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3761   if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3762     return DAG.getConstant(Val, VT);
3763   return SDValue(nullptr, 0);
3766 /// getMemBasePlusOffset - Returns base and offset node for the
3767 ///
3768 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3769                                       SelectionDAG &DAG) {
3770   EVT VT = Base.getValueType();
3771   return DAG.getNode(ISD::ADD, dl,
3772                      VT, Base, DAG.getConstant(Offset, VT));
3775 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3776 ///
3777 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3778   unsigned SrcDelta = 0;
3779   GlobalAddressSDNode *G = nullptr;
3780   if (Src.getOpcode() == ISD::GlobalAddress)
3781     G = cast<GlobalAddressSDNode>(Src);
3782   else if (Src.getOpcode() == ISD::ADD &&
3783            Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3784            Src.getOperand(1).getOpcode() == ISD::Constant) {
3785     G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3786     SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3787   }
3788   if (!G)
3789     return false;
3791   return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3794 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3795 /// to replace the memset / memcpy. Return true if the number of memory ops
3796 /// is below the threshold. It returns the types of the sequence of
3797 /// memory ops to perform memset / memcpy by reference.
3798 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3799                                      unsigned Limit, uint64_t Size,
3800                                      unsigned DstAlign, unsigned SrcAlign,
3801                                      bool IsMemset,
3802                                      bool ZeroMemset,
3803                                      bool MemcpyStrSrc,
3804                                      bool AllowOverlap,
3805                                      SelectionDAG &DAG,
3806                                      const TargetLowering &TLI) {
3807   assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3808          "Expecting memcpy / memset source to meet alignment requirement!");
3809   // If 'SrcAlign' is zero, that means the memory operation does not need to
3810   // load the value, i.e. memset or memcpy from constant string. Otherwise,
3811   // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3812   // is the specified alignment of the memory operation. If it is zero, that
3813   // means it's possible to change the alignment of the destination.
3814   // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3815   // not need to be loaded.
3816   EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3817                                    IsMemset, ZeroMemset, MemcpyStrSrc,
3818                                    DAG.getMachineFunction());
3820   if (VT == MVT::Other) {
3821     unsigned AS = 0;
3822     if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3823         TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3824       VT = TLI.getPointerTy();
3825     } else {
3826       switch (DstAlign & 7) {
3827       case 0:  VT = MVT::i64; break;
3828       case 4:  VT = MVT::i32; break;
3829       case 2:  VT = MVT::i16; break;
3830       default: VT = MVT::i8;  break;
3831       }
3832     }
3834     MVT LVT = MVT::i64;
3835     while (!TLI.isTypeLegal(LVT))
3836       LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3837     assert(LVT.isInteger());
3839     if (VT.bitsGT(LVT))
3840       VT = LVT;
3841   }
3843   unsigned NumMemOps = 0;
3844   while (Size != 0) {
3845     unsigned VTSize = VT.getSizeInBits() / 8;
3846     while (VTSize > Size) {
3847       // For now, only use non-vector load / store's for the left-over pieces.
3848       EVT NewVT = VT;
3849       unsigned NewVTSize;
3851       bool Found = false;
3852       if (VT.isVector() || VT.isFloatingPoint()) {
3853         NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3854         if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3855             TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3856           Found = true;
3857         else if (NewVT == MVT::i64 &&
3858                  TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&