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