SDAG: Give SDDbgValues their own allocator (and reset it)
[oota-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 //===----------------------------------------------------------------------===//
13
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
50 #include <algorithm>
51 #include <cmath>
52 #include <utility>
53
54 using namespace llvm;
55
56 /// makeVTList - Return an instance of the SDVTList struct initialized with the
57 /// specified members.
58 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59   SDVTList Res = {VTs, NumVTs};
60   return Res;
61 }
62
63 // Default null implementations of the callbacks.
64 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66
67 //===----------------------------------------------------------------------===//
68 //                              ConstantFPSDNode Class
69 //===----------------------------------------------------------------------===//
70
71 /// isExactlyValue - We don't rely on operator== working on double values, as
72 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73 /// As such, this method can be used to do an exact bit-for-bit comparison of
74 /// two floating point values.
75 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76   return getValueAPF().bitwiseIsEqual(V);
77 }
78
79 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80                                            const APFloat& Val) {
81   assert(VT.isFloatingPoint() && "Can only convert between FP types");
82
83   // convert modifies in place, so make a copy.
84   APFloat Val2 = APFloat(Val);
85   bool losesInfo;
86   (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87                       APFloat::rmNearestTiesToEven,
88                       &losesInfo);
89   return !losesInfo;
90 }
91
92 //===----------------------------------------------------------------------===//
93 //                              ISD Namespace
94 //===----------------------------------------------------------------------===//
95
96 /// isBuildVectorAllOnes - Return true if the specified node is a
97 /// BUILD_VECTOR where all of the elements are ~0 or undef.
98 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99   // Look through a bit convert.
100   while (N->getOpcode() == ISD::BITCAST)
101     N = N->getOperand(0).getNode();
102
103   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104
105   unsigned i = 0, e = N->getNumOperands();
106
107   // Skip over all of the undef values.
108   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
109     ++i;
110
111   // Do not accept an all-undef vector.
112   if (i == e) return false;
113
114   // Do not accept build_vectors that aren't all constants or which have non-~0
115   // elements. We have to be a bit careful here, as the type of the constant
116   // may not be the same as the type of the vector elements due to type
117   // legalization (the elements are promoted to a legal type for the target and
118   // a vector of a type may be legal when the base element type is not).
119   // We only want to check enough bits to cover the vector elements, because
120   // we care if the resultant vector is all ones, not whether the individual
121   // constants are.
122   SDValue NotZero = N->getOperand(i);
123   unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125     if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126       return false;
127   } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128     if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
129       return false;
130   } else
131     return false;
132
133   // Okay, we have at least one ~0 value, check to see if the rest match or are
134   // undefs. Even with the above element type twiddling, this should be OK, as
135   // the same type legalization should have applied to all the elements.
136   for (++i; i != e; ++i)
137     if (N->getOperand(i) != NotZero &&
138         N->getOperand(i).getOpcode() != ISD::UNDEF)
139       return false;
140   return true;
141 }
142
143
144 /// isBuildVectorAllZeros - Return true if the specified node is a
145 /// BUILD_VECTOR where all of the elements are 0 or undef.
146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147   // Look through a bit convert.
148   while (N->getOpcode() == ISD::BITCAST)
149     N = N->getOperand(0).getNode();
150
151   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152
153   bool IsAllUndef = true;
154   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
155     if (N->getOperand(i).getOpcode() == ISD::UNDEF)
156       continue;
157     IsAllUndef = false;
158     // Do not accept build_vectors that aren't all constants or which have non-0
159     // elements. We have to be a bit careful here, as the type of the constant
160     // may not be the same as the type of the vector elements due to type
161     // legalization (the elements are promoted to a legal type for the target
162     // and a vector of a type may be legal when the base element type is not).
163     // We only want to check enough bits to cover the vector elements, because
164     // we care if the resultant vector is all zeros, not whether the individual
165     // constants are.
166     SDValue Zero = N->getOperand(i);
167     unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
169       if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170         return false;
171     } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
172       if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
173         return false;
174     } else
175       return false;
176   }
177
178   // Do not accept an all-undef vector.
179   if (IsAllUndef)
180     return false;
181   return true;
182 }
183
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187   if (N->getOpcode() != ISD::BUILD_VECTOR)
188     return false;
189
190   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
191     SDValue Op = N->getOperand(i);
192     if (Op.getOpcode() == ISD::UNDEF)
193       continue;
194     if (!isa<ConstantSDNode>(Op))
195       return false;
196   }
197   return true;
198 }
199
200 /// \brief Return true if the specified node is a BUILD_VECTOR node of
201 /// all ConstantFPSDNode or undef.
202 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
203   if (N->getOpcode() != ISD::BUILD_VECTOR)
204     return false;
205
206   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
207     SDValue Op = N->getOperand(i);
208     if (Op.getOpcode() == ISD::UNDEF)
209       continue;
210     if (!isa<ConstantFPSDNode>(Op))
211       return false;
212   }
213   return true;
214 }
215
216 /// isScalarToVector - Return true if the specified node is a
217 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
218 /// element is not an undef.
219 bool ISD::isScalarToVector(const SDNode *N) {
220   if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
221     return true;
222
223   if (N->getOpcode() != ISD::BUILD_VECTOR)
224     return false;
225   if (N->getOperand(0).getOpcode() == ISD::UNDEF)
226     return false;
227   unsigned NumElems = N->getNumOperands();
228   if (NumElems == 1)
229     return false;
230   for (unsigned i = 1; i < NumElems; ++i) {
231     SDValue V = N->getOperand(i);
232     if (V.getOpcode() != ISD::UNDEF)
233       return false;
234   }
235   return true;
236 }
237
238 /// allOperandsUndef - Return true if the node has at least one operand
239 /// and all operands of the specified node are ISD::UNDEF.
240 bool ISD::allOperandsUndef(const SDNode *N) {
241   // Return false if the node has no operands.
242   // This is "logically inconsistent" with the definition of "all" but
243   // is probably the desired behavior.
244   if (N->getNumOperands() == 0)
245     return false;
246
247   for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
248     if (N->getOperand(i).getOpcode() != ISD::UNDEF)
249       return false;
250
251   return true;
252 }
253
254 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
255   switch (ExtType) {
256   case ISD::EXTLOAD:
257     return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
258   case ISD::SEXTLOAD:
259     return ISD::SIGN_EXTEND;
260   case ISD::ZEXTLOAD:
261     return ISD::ZERO_EXTEND;
262   default:
263     break;
264   }
265
266   llvm_unreachable("Invalid LoadExtType");
267 }
268
269 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
270 /// when given the operation for (X op Y).
271 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
272   // To perform this operation, we just need to swap the L and G bits of the
273   // operation.
274   unsigned OldL = (Operation >> 2) & 1;
275   unsigned OldG = (Operation >> 1) & 1;
276   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
277                        (OldL << 1) |       // New G bit
278                        (OldG << 2));       // New L bit.
279 }
280
281 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
282 /// 'op' is a valid SetCC operation.
283 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
284   unsigned Operation = Op;
285   if (isInteger)
286     Operation ^= 7;   // Flip L, G, E bits, but not U.
287   else
288     Operation ^= 15;  // Flip all of the condition bits.
289
290   if (Operation > ISD::SETTRUE2)
291     Operation &= ~8;  // Don't let N and U bits get set.
292
293   return ISD::CondCode(Operation);
294 }
295
296
297 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
298 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
299 /// if the operation does not depend on the sign of the input (setne and seteq).
300 static int isSignedOp(ISD::CondCode Opcode) {
301   switch (Opcode) {
302   default: llvm_unreachable("Illegal integer setcc operation!");
303   case ISD::SETEQ:
304   case ISD::SETNE: return 0;
305   case ISD::SETLT:
306   case ISD::SETLE:
307   case ISD::SETGT:
308   case ISD::SETGE: return 1;
309   case ISD::SETULT:
310   case ISD::SETULE:
311   case ISD::SETUGT:
312   case ISD::SETUGE: return 2;
313   }
314 }
315
316 /// getSetCCOrOperation - Return the result of a logical OR between different
317 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
318 /// returns SETCC_INVALID if it is not possible to represent the resultant
319 /// comparison.
320 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
321                                        bool isInteger) {
322   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
323     // Cannot fold a signed integer setcc with an unsigned integer setcc.
324     return ISD::SETCC_INVALID;
325
326   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
327
328   // If the N and U bits get set then the resultant comparison DOES suddenly
329   // care about orderedness, and is true when ordered.
330   if (Op > ISD::SETTRUE2)
331     Op &= ~16;     // Clear the U bit if the N bit is set.
332
333   // Canonicalize illegal integer setcc's.
334   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
335     Op = ISD::SETNE;
336
337   return ISD::CondCode(Op);
338 }
339
340 /// getSetCCAndOperation - Return the result of a logical AND between different
341 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
342 /// function returns zero if it is not possible to represent the resultant
343 /// comparison.
344 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
345                                         bool isInteger) {
346   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
347     // Cannot fold a signed setcc with an unsigned setcc.
348     return ISD::SETCC_INVALID;
349
350   // Combine all of the condition bits.
351   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
352
353   // Canonicalize illegal integer setcc's.
354   if (isInteger) {
355     switch (Result) {
356     default: break;
357     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
358     case ISD::SETOEQ:                                 // SETEQ  & SETU[LG]E
359     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
360     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
361     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
362     }
363   }
364
365   return Result;
366 }
367
368 //===----------------------------------------------------------------------===//
369 //                           SDNode Profile Support
370 //===----------------------------------------------------------------------===//
371
372 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
373 ///
374 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
375   ID.AddInteger(OpC);
376 }
377
378 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
379 /// solely with their pointer.
380 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
381   ID.AddPointer(VTList.VTs);
382 }
383
384 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
385 ///
386 static void AddNodeIDOperands(FoldingSetNodeID &ID,
387                               ArrayRef<SDValue> Ops) {
388   for (auto& Op : Ops) {
389     ID.AddPointer(Op.getNode());
390     ID.AddInteger(Op.getResNo());
391   }
392 }
393
394 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
395 ///
396 static void AddNodeIDOperands(FoldingSetNodeID &ID,
397                               ArrayRef<SDUse> Ops) {
398   for (auto& Op : Ops) {
399     ID.AddPointer(Op.getNode());
400     ID.AddInteger(Op.getResNo());
401   }
402 }
403
404 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
405                                   bool exact) {
406   ID.AddBoolean(nuw);
407   ID.AddBoolean(nsw);
408   ID.AddBoolean(exact);
409 }
410
411 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
412 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
413                                   bool nuw, bool nsw, bool exact) {
414   if (isBinOpWithFlags(Opcode))
415     AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
416 }
417
418 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
419                           SDVTList VTList, ArrayRef<SDValue> OpList) {
420   AddNodeIDOpcode(ID, OpC);
421   AddNodeIDValueTypes(ID, VTList);
422   AddNodeIDOperands(ID, OpList);
423 }
424
425 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
426 /// the NodeID data.
427 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
428   switch (N->getOpcode()) {
429   case ISD::TargetExternalSymbol:
430   case ISD::ExternalSymbol:
431     llvm_unreachable("Should only be used on nodes with operands");
432   default: break;  // Normal nodes don't need extra info.
433   case ISD::TargetConstant:
434   case ISD::Constant: {
435     const ConstantSDNode *C = cast<ConstantSDNode>(N);
436     ID.AddPointer(C->getConstantIntValue());
437     ID.AddBoolean(C->isOpaque());
438     break;
439   }
440   case ISD::TargetConstantFP:
441   case ISD::ConstantFP: {
442     ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
443     break;
444   }
445   case ISD::TargetGlobalAddress:
446   case ISD::GlobalAddress:
447   case ISD::TargetGlobalTLSAddress:
448   case ISD::GlobalTLSAddress: {
449     const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
450     ID.AddPointer(GA->getGlobal());
451     ID.AddInteger(GA->getOffset());
452     ID.AddInteger(GA->getTargetFlags());
453     ID.AddInteger(GA->getAddressSpace());
454     break;
455   }
456   case ISD::BasicBlock:
457     ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
458     break;
459   case ISD::Register:
460     ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
461     break;
462   case ISD::RegisterMask:
463     ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
464     break;
465   case ISD::SRCVALUE:
466     ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
467     break;
468   case ISD::FrameIndex:
469   case ISD::TargetFrameIndex:
470     ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
471     break;
472   case ISD::JumpTable:
473   case ISD::TargetJumpTable:
474     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
475     ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
476     break;
477   case ISD::ConstantPool:
478   case ISD::TargetConstantPool: {
479     const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
480     ID.AddInteger(CP->getAlignment());
481     ID.AddInteger(CP->getOffset());
482     if (CP->isMachineConstantPoolEntry())
483       CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
484     else
485       ID.AddPointer(CP->getConstVal());
486     ID.AddInteger(CP->getTargetFlags());
487     break;
488   }
489   case ISD::TargetIndex: {
490     const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
491     ID.AddInteger(TI->getIndex());
492     ID.AddInteger(TI->getOffset());
493     ID.AddInteger(TI->getTargetFlags());
494     break;
495   }
496   case ISD::LOAD: {
497     const LoadSDNode *LD = cast<LoadSDNode>(N);
498     ID.AddInteger(LD->getMemoryVT().getRawBits());
499     ID.AddInteger(LD->getRawSubclassData());
500     ID.AddInteger(LD->getPointerInfo().getAddrSpace());
501     break;
502   }
503   case ISD::STORE: {
504     const StoreSDNode *ST = cast<StoreSDNode>(N);
505     ID.AddInteger(ST->getMemoryVT().getRawBits());
506     ID.AddInteger(ST->getRawSubclassData());
507     ID.AddInteger(ST->getPointerInfo().getAddrSpace());
508     break;
509   }
510   case ISD::SDIV:
511   case ISD::UDIV:
512   case ISD::SRA:
513   case ISD::SRL:
514   case ISD::MUL:
515   case ISD::ADD:
516   case ISD::SUB:
517   case ISD::SHL: {
518     const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
519     AddBinaryNodeIDCustom(
520         ID, N->getOpcode(), BinNode->Flags.hasNoUnsignedWrap(),
521         BinNode->Flags.hasNoSignedWrap(), BinNode->Flags.hasExact());
522     break;
523   }
524   case ISD::ATOMIC_CMP_SWAP:
525   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
526   case ISD::ATOMIC_SWAP:
527   case ISD::ATOMIC_LOAD_ADD:
528   case ISD::ATOMIC_LOAD_SUB:
529   case ISD::ATOMIC_LOAD_AND:
530   case ISD::ATOMIC_LOAD_OR:
531   case ISD::ATOMIC_LOAD_XOR:
532   case ISD::ATOMIC_LOAD_NAND:
533   case ISD::ATOMIC_LOAD_MIN:
534   case ISD::ATOMIC_LOAD_MAX:
535   case ISD::ATOMIC_LOAD_UMIN:
536   case ISD::ATOMIC_LOAD_UMAX:
537   case ISD::ATOMIC_LOAD:
538   case ISD::ATOMIC_STORE: {
539     const AtomicSDNode *AT = cast<AtomicSDNode>(N);
540     ID.AddInteger(AT->getMemoryVT().getRawBits());
541     ID.AddInteger(AT->getRawSubclassData());
542     ID.AddInteger(AT->getPointerInfo().getAddrSpace());
543     break;
544   }
545   case ISD::PREFETCH: {
546     const MemSDNode *PF = cast<MemSDNode>(N);
547     ID.AddInteger(PF->getPointerInfo().getAddrSpace());
548     break;
549   }
550   case ISD::VECTOR_SHUFFLE: {
551     const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
552     for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
553          i != e; ++i)
554       ID.AddInteger(SVN->getMaskElt(i));
555     break;
556   }
557   case ISD::TargetBlockAddress:
558   case ISD::BlockAddress: {
559     const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
560     ID.AddPointer(BA->getBlockAddress());
561     ID.AddInteger(BA->getOffset());
562     ID.AddInteger(BA->getTargetFlags());
563     break;
564   }
565   } // end switch (N->getOpcode())
566
567   // Target specific memory nodes could also have address spaces to check.
568   if (N->isTargetMemoryOpcode())
569     ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
570 }
571
572 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
573 /// data.
574 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
575   AddNodeIDOpcode(ID, N->getOpcode());
576   // Add the return value info.
577   AddNodeIDValueTypes(ID, N->getVTList());
578   // Add the operand info.
579   AddNodeIDOperands(ID, N->ops());
580
581   // Handle SDNode leafs with special info.
582   AddNodeIDCustom(ID, N);
583 }
584
585 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
586 /// the CSE map that carries volatility, temporalness, indexing mode, and
587 /// extension/truncation information.
588 ///
589 static inline unsigned
590 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
591                      bool isNonTemporal, bool isInvariant) {
592   assert((ConvType & 3) == ConvType &&
593          "ConvType may not require more than 2 bits!");
594   assert((AM & 7) == AM &&
595          "AM may not require more than 3 bits!");
596   return ConvType |
597          (AM << 2) |
598          (isVolatile << 5) |
599          (isNonTemporal << 6) |
600          (isInvariant << 7);
601 }
602
603 //===----------------------------------------------------------------------===//
604 //                              SelectionDAG Class
605 //===----------------------------------------------------------------------===//
606
607 /// doNotCSE - Return true if CSE should not be performed for this node.
608 static bool doNotCSE(SDNode *N) {
609   if (N->getValueType(0) == MVT::Glue)
610     return true; // Never CSE anything that produces a flag.
611
612   switch (N->getOpcode()) {
613   default: break;
614   case ISD::HANDLENODE:
615   case ISD::EH_LABEL:
616     return true;   // Never CSE these nodes.
617   }
618
619   // Check that remaining values produced are not flags.
620   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
621     if (N->getValueType(i) == MVT::Glue)
622       return true; // Never CSE anything that produces a flag.
623
624   return false;
625 }
626
627 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
628 /// SelectionDAG.
629 void SelectionDAG::RemoveDeadNodes() {
630   // Create a dummy node (which is not added to allnodes), that adds a reference
631   // to the root node, preventing it from being deleted.
632   HandleSDNode Dummy(getRoot());
633
634   SmallVector<SDNode*, 128> DeadNodes;
635
636   // Add all obviously-dead nodes to the DeadNodes worklist.
637   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
638     if (I->use_empty())
639       DeadNodes.push_back(I);
640
641   RemoveDeadNodes(DeadNodes);
642
643   // If the root changed (e.g. it was a dead load, update the root).
644   setRoot(Dummy.getValue());
645 }
646
647 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
648 /// given list, and any nodes that become unreachable as a result.
649 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
650
651   // Process the worklist, deleting the nodes and adding their uses to the
652   // worklist.
653   while (!DeadNodes.empty()) {
654     SDNode *N = DeadNodes.pop_back_val();
655
656     for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
657       DUL->NodeDeleted(N, nullptr);
658
659     // Take the node out of the appropriate CSE map.
660     RemoveNodeFromCSEMaps(N);
661
662     // Next, brutally remove the operand list.  This is safe to do, as there are
663     // no cycles in the graph.
664     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
665       SDUse &Use = *I++;
666       SDNode *Operand = Use.getNode();
667       Use.set(SDValue());
668
669       // Now that we removed this operand, see if there are no uses of it left.
670       if (Operand->use_empty())
671         DeadNodes.push_back(Operand);
672     }
673
674     DeallocateNode(N);
675   }
676 }
677
678 void SelectionDAG::RemoveDeadNode(SDNode *N){
679   SmallVector<SDNode*, 16> DeadNodes(1, N);
680
681   // Create a dummy node that adds a reference to the root node, preventing
682   // it from being deleted.  (This matters if the root is an operand of the
683   // dead node.)
684   HandleSDNode Dummy(getRoot());
685
686   RemoveDeadNodes(DeadNodes);
687 }
688
689 void SelectionDAG::DeleteNode(SDNode *N) {
690   // First take this out of the appropriate CSE map.
691   RemoveNodeFromCSEMaps(N);
692
693   // Finally, remove uses due to operands of this node, remove from the
694   // AllNodes list, and delete the node.
695   DeleteNodeNotInCSEMaps(N);
696 }
697
698 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
699   assert(N != AllNodes.begin() && "Cannot delete the entry node!");
700   assert(N->use_empty() && "Cannot delete a node that is not dead!");
701
702   // Drop all of the operands and decrement used node's use counts.
703   N->DropOperands();
704
705   DeallocateNode(N);
706 }
707
708 void SDDbgInfo::erase(const SDNode *Node) {
709   DbgValMapType::iterator I = DbgValMap.find(Node);
710   if (I == DbgValMap.end())
711     return;
712   for (auto &Val: I->second)
713     Val->setIsInvalidated();
714   DbgValMap.erase(I);
715 }
716
717 void SelectionDAG::DeallocateNode(SDNode *N) {
718   if (N->OperandsNeedDelete)
719     delete[] N->OperandList;
720
721   // Set the opcode to DELETED_NODE to help catch bugs when node
722   // memory is reallocated.
723   N->NodeType = ISD::DELETED_NODE;
724
725   NodeAllocator.Deallocate(AllNodes.remove(N));
726
727   // If any of the SDDbgValue nodes refer to this SDNode, invalidate
728   // them and forget about that node.
729   DbgInfo->erase(N);
730 }
731
732 #ifndef NDEBUG
733 /// VerifySDNode - Sanity check the given SDNode.  Aborts if it is invalid.
734 static void VerifySDNode(SDNode *N) {
735   switch (N->getOpcode()) {
736   default:
737     break;
738   case ISD::BUILD_PAIR: {
739     EVT VT = N->getValueType(0);
740     assert(N->getNumValues() == 1 && "Too many results!");
741     assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
742            "Wrong return type!");
743     assert(N->getNumOperands() == 2 && "Wrong number of operands!");
744     assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
745            "Mismatched operand types!");
746     assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
747            "Wrong operand type!");
748     assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
749            "Wrong return type size");
750     break;
751   }
752   case ISD::BUILD_VECTOR: {
753     assert(N->getNumValues() == 1 && "Too many results!");
754     assert(N->getValueType(0).isVector() && "Wrong return type!");
755     assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
756            "Wrong number of operands!");
757     EVT EltVT = N->getValueType(0).getVectorElementType();
758     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
759       assert((I->getValueType() == EltVT ||
760              (EltVT.isInteger() && I->getValueType().isInteger() &&
761               EltVT.bitsLE(I->getValueType()))) &&
762             "Wrong operand type!");
763       assert(I->getValueType() == N->getOperand(0).getValueType() &&
764              "Operands must all have the same type");
765     }
766     break;
767   }
768   }
769 }
770 #endif // NDEBUG
771
772 /// \brief Insert a newly allocated node into the DAG.
773 ///
774 /// Handles insertion into the all nodes list and CSE map, as well as
775 /// verification and other common operations when a new node is allocated.
776 void SelectionDAG::InsertNode(SDNode *N) {
777   AllNodes.push_back(N);
778 #ifndef NDEBUG
779   VerifySDNode(N);
780 #endif
781 }
782
783 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
784 /// correspond to it.  This is useful when we're about to delete or repurpose
785 /// the node.  We don't want future request for structurally identical nodes
786 /// to return N anymore.
787 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
788   bool Erased = false;
789   switch (N->getOpcode()) {
790   case ISD::HANDLENODE: return false;  // noop.
791   case ISD::CONDCODE:
792     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
793            "Cond code doesn't exist!");
794     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
795     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
796     break;
797   case ISD::ExternalSymbol:
798     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
799     break;
800   case ISD::TargetExternalSymbol: {
801     ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
802     Erased = TargetExternalSymbols.erase(
803                std::pair<std::string,unsigned char>(ESN->getSymbol(),
804                                                     ESN->getTargetFlags()));
805     break;
806   }
807   case ISD::VALUETYPE: {
808     EVT VT = cast<VTSDNode>(N)->getVT();
809     if (VT.isExtended()) {
810       Erased = ExtendedValueTypeNodes.erase(VT);
811     } else {
812       Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
813       ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
814     }
815     break;
816   }
817   default:
818     // Remove it from the CSE Map.
819     assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
820     assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
821     Erased = CSEMap.RemoveNode(N);
822     break;
823   }
824 #ifndef NDEBUG
825   // Verify that the node was actually in one of the CSE maps, unless it has a
826   // flag result (which cannot be CSE'd) or is one of the special cases that are
827   // not subject to CSE.
828   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
829       !N->isMachineOpcode() && !doNotCSE(N)) {
830     N->dump(this);
831     dbgs() << "\n";
832     llvm_unreachable("Node is not in map!");
833   }
834 #endif
835   return Erased;
836 }
837
838 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
839 /// maps and modified in place. Add it back to the CSE maps, unless an identical
840 /// node already exists, in which case transfer all its users to the existing
841 /// node. This transfer can potentially trigger recursive merging.
842 ///
843 void
844 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
845   // For node types that aren't CSE'd, just act as if no identical node
846   // already exists.
847   if (!doNotCSE(N)) {
848     SDNode *Existing = CSEMap.GetOrInsertNode(N);
849     if (Existing != N) {
850       // If there was already an existing matching node, use ReplaceAllUsesWith
851       // to replace the dead one with the existing one.  This can cause
852       // recursive merging of other unrelated nodes down the line.
853       ReplaceAllUsesWith(N, Existing);
854
855       // N is now dead. Inform the listeners and delete it.
856       for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
857         DUL->NodeDeleted(N, Existing);
858       DeleteNodeNotInCSEMaps(N);
859       return;
860     }
861   }
862
863   // If the node doesn't already exist, we updated it.  Inform listeners.
864   for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
865     DUL->NodeUpdated(N);
866 }
867
868 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
869 /// were replaced with those specified.  If this node is never memoized,
870 /// return null, otherwise return a pointer to the slot it would take.  If a
871 /// node already exists with these operands, the slot will be non-null.
872 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
873                                            void *&InsertPos) {
874   if (doNotCSE(N))
875     return nullptr;
876
877   SDValue Ops[] = { Op };
878   FoldingSetNodeID ID;
879   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880   AddNodeIDCustom(ID, N);
881   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
882   return Node;
883 }
884
885 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
886 /// were replaced with those specified.  If this node is never memoized,
887 /// return null, otherwise return a pointer to the slot it would take.  If a
888 /// node already exists with these operands, the slot will be non-null.
889 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
890                                            SDValue Op1, SDValue Op2,
891                                            void *&InsertPos) {
892   if (doNotCSE(N))
893     return nullptr;
894
895   SDValue Ops[] = { Op1, Op2 };
896   FoldingSetNodeID ID;
897   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
898   AddNodeIDCustom(ID, N);
899   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
900   return Node;
901 }
902
903
904 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
905 /// were replaced with those specified.  If this node is never memoized,
906 /// return null, otherwise return a pointer to the slot it would take.  If a
907 /// node already exists with these operands, the slot will be non-null.
908 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
909                                            void *&InsertPos) {
910   if (doNotCSE(N))
911     return nullptr;
912
913   FoldingSetNodeID ID;
914   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
915   AddNodeIDCustom(ID, N);
916   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
917   return Node;
918 }
919
920 /// getEVTAlignment - Compute the default alignment value for the
921 /// given type.
922 ///
923 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
924   Type *Ty = VT == MVT::iPTR ?
925                    PointerType::get(Type::getInt8Ty(*getContext()), 0) :
926                    VT.getTypeForEVT(*getContext());
927
928   return TLI->getDataLayout()->getABITypeAlignment(Ty);
929 }
930
931 // EntryNode could meaningfully have debug info if we can find it...
932 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
933     : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
934       EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
935       Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
936       UpdateListeners(nullptr) {
937   AllNodes.push_back(&EntryNode);
938   DbgInfo = new SDDbgInfo();
939 }
940
941 void SelectionDAG::init(MachineFunction &mf) {
942   MF = &mf;
943   TLI = getSubtarget().getTargetLowering();
944   TSI = getSubtarget().getSelectionDAGInfo();
945   Context = &mf.getFunction()->getContext();
946 }
947
948 SelectionDAG::~SelectionDAG() {
949   assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
950   allnodes_clear();
951   delete DbgInfo;
952 }
953
954 void SelectionDAG::allnodes_clear() {
955   assert(&*AllNodes.begin() == &EntryNode);
956   AllNodes.remove(AllNodes.begin());
957   while (!AllNodes.empty())
958     DeallocateNode(AllNodes.begin());
959 }
960
961 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
962                                             SDVTList VTs, SDValue N1,
963                                             SDValue N2, bool nuw, bool nsw,
964                                             bool exact) {
965   if (isBinOpWithFlags(Opcode)) {
966     BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967         Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
968     FN->Flags.setNoUnsignedWrap(nuw);
969     FN->Flags.setNoSignedWrap(nsw);
970     FN->Flags.setExact(exact);
971
972     return FN;
973   }
974
975   BinarySDNode *N = new (NodeAllocator)
976       BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
977   return N;
978 }
979
980 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
981                                           void *&InsertPos) {
982   SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
983   if (N) {
984     switch (N->getOpcode()) {
985     default: break;
986     case ISD::Constant:
987     case ISD::ConstantFP:
988       llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
989                        "debug location.  Use another overload.");
990     }
991   }
992   return N;
993 }
994
995 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
996                                           DebugLoc DL, void *&InsertPos) {
997   SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
998   if (N) {
999     switch (N->getOpcode()) {
1000     default: break; // Process only regular (non-target) constant nodes.
1001     case ISD::Constant:
1002     case ISD::ConstantFP:
1003       // Erase debug location from the node if the node is used at several
1004       // different places to do not propagate one location to all uses as it
1005       // leads to incorrect debug info.
1006       if (N->getDebugLoc() != DL)
1007         N->setDebugLoc(DebugLoc());
1008       break;
1009     }
1010   }
1011   return N;
1012 }
1013
1014 void SelectionDAG::clear() {
1015   allnodes_clear();
1016   OperandAllocator.Reset();
1017   CSEMap.clear();
1018
1019   ExtendedValueTypeNodes.clear();
1020   ExternalSymbols.clear();
1021   TargetExternalSymbols.clear();
1022   std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1023             static_cast<CondCodeSDNode*>(nullptr));
1024   std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1025             static_cast<SDNode*>(nullptr));
1026
1027   EntryNode.UseList = nullptr;
1028   AllNodes.push_back(&EntryNode);
1029   Root = getEntryNode();
1030   DbgInfo->clear();
1031 }
1032
1033 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1034   return VT.bitsGT(Op.getValueType()) ?
1035     getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1036     getNode(ISD::TRUNCATE, DL, VT, Op);
1037 }
1038
1039 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1040   return VT.bitsGT(Op.getValueType()) ?
1041     getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1042     getNode(ISD::TRUNCATE, DL, VT, Op);
1043 }
1044
1045 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1046   return VT.bitsGT(Op.getValueType()) ?
1047     getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1048     getNode(ISD::TRUNCATE, DL, VT, Op);
1049 }
1050
1051 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1052                                         EVT OpVT) {
1053   if (VT.bitsLE(Op.getValueType()))
1054     return getNode(ISD::TRUNCATE, SL, VT, Op);
1055
1056   TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1057   return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1058 }
1059
1060 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1061   assert(!VT.isVector() &&
1062          "getZeroExtendInReg should use the vector element type instead of "
1063          "the vector type!");
1064   if (Op.getValueType() == VT) return Op;
1065   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1066   APInt Imm = APInt::getLowBitsSet(BitWidth,
1067                                    VT.getSizeInBits());
1068   return getNode(ISD::AND, DL, Op.getValueType(), Op,
1069                  getConstant(Imm, DL, Op.getValueType()));
1070 }
1071
1072 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1073   assert(VT.isVector() && "This DAG node is restricted to vector types.");
1074   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1075          "The sizes of the input and result must match in order to perform the "
1076          "extend in-register.");
1077   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1078          "The destination vector type must have fewer lanes than the input.");
1079   return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1080 }
1081
1082 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1083   assert(VT.isVector() && "This DAG node is restricted to vector types.");
1084   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1085          "The sizes of the input and result must match in order to perform the "
1086          "extend in-register.");
1087   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1088          "The destination vector type must have fewer lanes than the input.");
1089   return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1090 }
1091
1092 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1093   assert(VT.isVector() && "This DAG node is restricted to vector types.");
1094   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1095          "The sizes of the input and result must match in order to perform the "
1096          "extend in-register.");
1097   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1098          "The destination vector type must have fewer lanes than the input.");
1099   return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1100 }
1101
1102 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1103 ///
1104 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1105   EVT EltVT = VT.getScalarType();
1106   SDValue NegOne =
1107     getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1108   return getNode(ISD::XOR, DL, VT, Val, NegOne);
1109 }
1110
1111 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1112   EVT EltVT = VT.getScalarType();
1113   SDValue TrueValue;
1114   switch (TLI->getBooleanContents(VT)) {
1115     case TargetLowering::ZeroOrOneBooleanContent:
1116     case TargetLowering::UndefinedBooleanContent:
1117       TrueValue = getConstant(1, DL, VT);
1118       break;
1119     case TargetLowering::ZeroOrNegativeOneBooleanContent:
1120       TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1121                               VT);
1122       break;
1123   }
1124   return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1125 }
1126
1127 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1128                                   bool isO) {
1129   EVT EltVT = VT.getScalarType();
1130   assert((EltVT.getSizeInBits() >= 64 ||
1131          (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1132          "getConstant with a uint64_t value that doesn't fit in the type!");
1133   return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1134 }
1135
1136 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1137                                   bool isO)
1138 {
1139   return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1140 }
1141
1142 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1143                                   bool isT, bool isO) {
1144   assert(VT.isInteger() && "Cannot create FP integer constant!");
1145
1146   EVT EltVT = VT.getScalarType();
1147   const ConstantInt *Elt = &Val;
1148
1149   // In some cases the vector type is legal but the element type is illegal and
1150   // needs to be promoted, for example v8i8 on ARM.  In this case, promote the
1151   // inserted value (the type does not need to match the vector element type).
1152   // Any extra bits introduced will be truncated away.
1153   if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1154       TargetLowering::TypePromoteInteger) {
1155    EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1156    APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1157    Elt = ConstantInt::get(*getContext(), NewVal);
1158   }
1159   // In other cases the element type is illegal and needs to be expanded, for
1160   // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1161   // the value into n parts and use a vector type with n-times the elements.
1162   // Then bitcast to the type requested.
1163   // Legalizing constants too early makes the DAGCombiner's job harder so we
1164   // only legalize if the DAG tells us we must produce legal types.
1165   else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1166            TLI->getTypeAction(*getContext(), EltVT) ==
1167            TargetLowering::TypeExpandInteger) {
1168     APInt NewVal = Elt->getValue();
1169     EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1170     unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1171     unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1172     EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1173
1174     // Check the temporary vector is the correct size. If this fails then
1175     // getTypeToTransformTo() probably returned a type whose size (in bits)
1176     // isn't a power-of-2 factor of the requested type size.
1177     assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1178
1179     SmallVector<SDValue, 2> EltParts;
1180     for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1181       EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1182                                            .trunc(ViaEltSizeInBits), DL,
1183                                      ViaEltVT, isT, isO));
1184     }
1185
1186     // EltParts is currently in little endian order. If we actually want
1187     // big-endian order then reverse it now.
1188     if (TLI->isBigEndian())
1189       std::reverse(EltParts.begin(), EltParts.end());
1190
1191     // The elements must be reversed when the element order is different
1192     // to the endianness of the elements (because the BITCAST is itself a
1193     // vector shuffle in this situation). However, we do not need any code to
1194     // perform this reversal because getConstant() is producing a vector
1195     // splat.
1196     // This situation occurs in MIPS MSA.
1197
1198     SmallVector<SDValue, 8> Ops;
1199     for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1200       Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1201
1202     SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1203                              getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1204                                      Ops));
1205     return Result;
1206   }
1207
1208   assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1209          "APInt size does not match type size!");
1210   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1211   FoldingSetNodeID ID;
1212   AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1213   ID.AddPointer(Elt);
1214   ID.AddBoolean(isO);
1215   void *IP = nullptr;
1216   SDNode *N = nullptr;
1217   if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1218     if (!VT.isVector())
1219       return SDValue(N, 0);
1220
1221   if (!N) {
1222     N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1223                                            EltVT);
1224     CSEMap.InsertNode(N, IP);
1225     InsertNode(N);
1226   }
1227
1228   SDValue Result(N, 0);
1229   if (VT.isVector()) {
1230     SmallVector<SDValue, 8> Ops;
1231     Ops.assign(VT.getVectorNumElements(), Result);
1232     Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1233   }
1234   return Result;
1235 }
1236
1237 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1238   return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1239 }
1240
1241 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1242                                     bool isTarget) {
1243   return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1244 }
1245
1246 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1247                                     bool isTarget){
1248   assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1249
1250   EVT EltVT = VT.getScalarType();
1251
1252   // Do the map lookup using the actual bit pattern for the floating point
1253   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1254   // we don't have issues with SNANs.
1255   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1256   FoldingSetNodeID ID;
1257   AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1258   ID.AddPointer(&V);
1259   void *IP = nullptr;
1260   SDNode *N = nullptr;
1261   if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1262     if (!VT.isVector())
1263       return SDValue(N, 0);
1264
1265   if (!N) {
1266     N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1267                                              EltVT);
1268     CSEMap.InsertNode(N, IP);
1269     InsertNode(N);
1270   }
1271
1272   SDValue Result(N, 0);
1273   if (VT.isVector()) {
1274     SmallVector<SDValue, 8> Ops;
1275     Ops.assign(VT.getVectorNumElements(), Result);
1276     Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1277   }
1278   return Result;
1279 }
1280
1281 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1282                                     bool isTarget) {
1283   EVT EltVT = VT.getScalarType();
1284   if (EltVT==MVT::f32)
1285     return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1286   else if (EltVT==MVT::f64)
1287     return getConstantFP(APFloat(Val), DL, VT, isTarget);
1288   else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1289            EltVT==MVT::f16) {
1290     bool ignored;
1291     APFloat apf = APFloat(Val);
1292     apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1293                 &ignored);
1294     return getConstantFP(apf, DL, VT, isTarget);
1295   } else
1296     llvm_unreachable("Unsupported type in getConstantFP");
1297 }
1298
1299 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1300                                        EVT VT, int64_t Offset,
1301                                        bool isTargetGA,
1302                                        unsigned char TargetFlags) {
1303   assert((TargetFlags == 0 || isTargetGA) &&
1304          "Cannot set target flags on target-independent globals");
1305
1306   // Truncate (with sign-extension) the offset value to the pointer size.
1307   unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1308   if (BitWidth < 64)
1309     Offset = SignExtend64(Offset, BitWidth);
1310
1311   unsigned Opc;
1312   if (GV->isThreadLocal())
1313     Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1314   else
1315     Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1316
1317   FoldingSetNodeID ID;
1318   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1319   ID.AddPointer(GV);
1320   ID.AddInteger(Offset);
1321   ID.AddInteger(TargetFlags);
1322   ID.AddInteger(GV->getType()->getAddressSpace());
1323   void *IP = nullptr;
1324   if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1325     return SDValue(E, 0);
1326
1327   SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1328                                                       DL.getDebugLoc(), GV, VT,
1329                                                       Offset, TargetFlags);
1330   CSEMap.InsertNode(N, IP);
1331     InsertNode(N);
1332   return SDValue(N, 0);
1333 }
1334
1335 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1336   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1337   FoldingSetNodeID ID;
1338   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1339   ID.AddInteger(FI);
1340   void *IP = nullptr;
1341   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1342     return SDValue(E, 0);
1343
1344   SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1345   CSEMap.InsertNode(N, IP);
1346   InsertNode(N);
1347   return SDValue(N, 0);
1348 }
1349
1350 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1351                                    unsigned char TargetFlags) {
1352   assert((TargetFlags == 0 || isTarget) &&
1353          "Cannot set target flags on target-independent jump tables");
1354   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1355   FoldingSetNodeID ID;
1356   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1357   ID.AddInteger(JTI);
1358   ID.AddInteger(TargetFlags);
1359   void *IP = nullptr;
1360   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1361     return SDValue(E, 0);
1362
1363   SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1364                                                   TargetFlags);
1365   CSEMap.InsertNode(N, IP);
1366   InsertNode(N);
1367   return SDValue(N, 0);
1368 }
1369
1370 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1371                                       unsigned Alignment, int Offset,
1372                                       bool isTarget,
1373                                       unsigned char TargetFlags) {
1374   assert((TargetFlags == 0 || isTarget) &&
1375          "Cannot set target flags on target-independent globals");
1376   if (Alignment == 0)
1377     Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1378   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1379   FoldingSetNodeID ID;
1380   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1381   ID.AddInteger(Alignment);
1382   ID.AddInteger(Offset);
1383   ID.AddPointer(C);
1384   ID.AddInteger(TargetFlags);
1385   void *IP = nullptr;
1386   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1387     return SDValue(E, 0);
1388
1389   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1390                                                      Alignment, TargetFlags);
1391   CSEMap.InsertNode(N, IP);
1392   InsertNode(N);
1393   return SDValue(N, 0);
1394 }
1395
1396
1397 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1398                                       unsigned Alignment, int Offset,
1399                                       bool isTarget,
1400                                       unsigned char TargetFlags) {
1401   assert((TargetFlags == 0 || isTarget) &&
1402          "Cannot set target flags on target-independent globals");
1403   if (Alignment == 0)
1404     Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1405   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1406   FoldingSetNodeID ID;
1407   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1408   ID.AddInteger(Alignment);
1409   ID.AddInteger(Offset);
1410   C->addSelectionDAGCSEId(ID);
1411   ID.AddInteger(TargetFlags);
1412   void *IP = nullptr;
1413   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1414     return SDValue(E, 0);
1415
1416   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1417                                                      Alignment, TargetFlags);
1418   CSEMap.InsertNode(N, IP);
1419   InsertNode(N);
1420   return SDValue(N, 0);
1421 }
1422
1423 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1424                                      unsigned char TargetFlags) {
1425   FoldingSetNodeID ID;
1426   AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1427   ID.AddInteger(Index);
1428   ID.AddInteger(Offset);
1429   ID.AddInteger(TargetFlags);
1430   void *IP = nullptr;
1431   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1432     return SDValue(E, 0);
1433
1434   SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1435                                                     TargetFlags);
1436   CSEMap.InsertNode(N, IP);
1437   InsertNode(N);
1438   return SDValue(N, 0);
1439 }
1440
1441 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1442   FoldingSetNodeID ID;
1443   AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1444   ID.AddPointer(MBB);
1445   void *IP = nullptr;
1446   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1447     return SDValue(E, 0);
1448
1449   SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1450   CSEMap.InsertNode(N, IP);
1451   InsertNode(N);
1452   return SDValue(N, 0);
1453 }
1454
1455 SDValue SelectionDAG::getValueType(EVT VT) {
1456   if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1457       ValueTypeNodes.size())
1458     ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1459
1460   SDNode *&N = VT.isExtended() ?
1461     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1462
1463   if (N) return SDValue(N, 0);
1464   N = new (NodeAllocator) VTSDNode(VT);
1465   InsertNode(N);
1466   return SDValue(N, 0);
1467 }
1468
1469 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1470   SDNode *&N = ExternalSymbols[Sym];
1471   if (N) return SDValue(N, 0);
1472   N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1473   InsertNode(N);
1474   return SDValue(N, 0);
1475 }
1476
1477 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1478                                               unsigned char TargetFlags) {
1479   SDNode *&N =
1480     TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1481                                                                TargetFlags)];
1482   if (N) return SDValue(N, 0);
1483   N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1484   InsertNode(N);
1485   return SDValue(N, 0);
1486 }
1487
1488 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1489   if ((unsigned)Cond >= CondCodeNodes.size())
1490     CondCodeNodes.resize(Cond+1);
1491
1492   if (!CondCodeNodes[Cond]) {
1493     CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1494     CondCodeNodes[Cond] = N;
1495     InsertNode(N);
1496   }
1497
1498   return SDValue(CondCodeNodes[Cond], 0);
1499 }
1500
1501 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1502 // the shuffle mask M that point at N1 to point at N2, and indices that point
1503 // N2 to point at N1.
1504 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1505   std::swap(N1, N2);
1506   ShuffleVectorSDNode::commuteMask(M);
1507 }
1508
1509 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1510                                        SDValue N2, const int *Mask) {
1511   assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1512          "Invalid VECTOR_SHUFFLE");
1513
1514   // Canonicalize shuffle undef, undef -> undef
1515   if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1516     return getUNDEF(VT);
1517
1518   // Validate that all indices in Mask are within the range of the elements
1519   // input to the shuffle.
1520   unsigned NElts = VT.getVectorNumElements();
1521   SmallVector<int, 8> MaskVec;
1522   for (unsigned i = 0; i != NElts; ++i) {
1523     assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1524     MaskVec.push_back(Mask[i]);
1525   }
1526
1527   // Canonicalize shuffle v, v -> v, undef
1528   if (N1 == N2) {
1529     N2 = getUNDEF(VT);
1530     for (unsigned i = 0; i != NElts; ++i)
1531       if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1532   }
1533
1534   // Canonicalize shuffle undef, v -> v, undef.  Commute the shuffle mask.
1535   if (N1.getOpcode() == ISD::UNDEF)
1536     commuteShuffle(N1, N2, MaskVec);
1537
1538   // If shuffling a splat, try to blend the splat instead. We do this here so
1539   // that even when this arises during lowering we don't have to re-handle it.
1540   auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1541     BitVector UndefElements;
1542     SDValue Splat = BV->getSplatValue(&UndefElements);
1543     if (!Splat)
1544       return;
1545
1546     for (int i = 0; i < (int)NElts; ++i) {
1547       if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1548         continue;
1549
1550       // If this input comes from undef, mark it as such.
1551       if (UndefElements[MaskVec[i] - Offset]) {
1552         MaskVec[i] = -1;
1553         continue;
1554       }
1555
1556       // If we can blend a non-undef lane, use that instead.
1557       if (!UndefElements[i])
1558         MaskVec[i] = i + Offset;
1559     }
1560   };
1561   if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1562     BlendSplat(N1BV, 0);
1563   if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1564     BlendSplat(N2BV, NElts);
1565
1566   // Canonicalize all index into lhs, -> shuffle lhs, undef
1567   // Canonicalize all index into rhs, -> shuffle rhs, undef
1568   bool AllLHS = true, AllRHS = true;
1569   bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1570   for (unsigned i = 0; i != NElts; ++i) {
1571     if (MaskVec[i] >= (int)NElts) {
1572       if (N2Undef)
1573         MaskVec[i] = -1;
1574       else
1575         AllLHS = false;
1576     } else if (MaskVec[i] >= 0) {
1577       AllRHS = false;
1578     }
1579   }
1580   if (AllLHS && AllRHS)
1581     return getUNDEF(VT);
1582   if (AllLHS && !N2Undef)
1583     N2 = getUNDEF(VT);
1584   if (AllRHS) {
1585     N1 = getUNDEF(VT);
1586     commuteShuffle(N1, N2, MaskVec);
1587   }
1588   // Reset our undef status after accounting for the mask.
1589   N2Undef = N2.getOpcode() == ISD::UNDEF;
1590   // Re-check whether both sides ended up undef.
1591   if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1592     return getUNDEF(VT);
1593
1594   // If Identity shuffle return that node.
1595   bool Identity = true, AllSame = true;
1596   for (unsigned i = 0; i != NElts; ++i) {
1597     if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1598     if (MaskVec[i] != MaskVec[0]) AllSame = false;
1599   }
1600   if (Identity && NElts)
1601     return N1;
1602
1603   // Shuffling a constant splat doesn't change the result.
1604   if (N2Undef) {
1605     SDValue V = N1;
1606
1607     // Look through any bitcasts. We check that these don't change the number
1608     // (and size) of elements and just changes their types.
1609     while (V.getOpcode() == ISD::BITCAST)
1610       V = V->getOperand(0);
1611
1612     // A splat should always show up as a build vector node.
1613     if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1614       BitVector UndefElements;
1615       SDValue Splat = BV->getSplatValue(&UndefElements);
1616       // If this is a splat of an undef, shuffling it is also undef.
1617       if (Splat && Splat.getOpcode() == ISD::UNDEF)
1618         return getUNDEF(VT);
1619
1620       bool SameNumElts =
1621           V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1622
1623       // We only have a splat which can skip shuffles if there is a splatted
1624       // value and no undef lanes rearranged by the shuffle.
1625       if (Splat && UndefElements.none()) {
1626         // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1627         // number of elements match or the value splatted is a zero constant.
1628         if (SameNumElts)
1629           return N1;
1630         if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1631           if (C->isNullValue())
1632             return N1;
1633       }
1634
1635       // If the shuffle itself creates a splat, build the vector directly.
1636       if (AllSame && SameNumElts) {
1637         const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1638         SmallVector<SDValue, 8> Ops(NElts, Splatted);
1639
1640         EVT BuildVT = BV->getValueType(0);
1641         SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1642
1643         // We may have jumped through bitcasts, so the type of the
1644         // BUILD_VECTOR may not match the type of the shuffle.
1645         if (BuildVT != VT)
1646           NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1647         return NewBV;
1648       }
1649     }
1650   }
1651
1652   FoldingSetNodeID ID;
1653   SDValue Ops[2] = { N1, N2 };
1654   AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1655   for (unsigned i = 0; i != NElts; ++i)
1656     ID.AddInteger(MaskVec[i]);
1657
1658   void* IP = nullptr;
1659   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1660     return SDValue(E, 0);
1661
1662   // Allocate the mask array for the node out of the BumpPtrAllocator, since
1663   // SDNode doesn't have access to it.  This memory will be "leaked" when
1664   // the node is deallocated, but recovered when the NodeAllocator is released.
1665   int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1666   memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1667
1668   ShuffleVectorSDNode *N =
1669     new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1670                                             dl.getDebugLoc(), N1, N2,
1671                                             MaskAlloc);
1672   CSEMap.InsertNode(N, IP);
1673   InsertNode(N);
1674   return SDValue(N, 0);
1675 }
1676
1677 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1678   MVT VT = SV.getSimpleValueType(0);
1679   SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1680   ShuffleVectorSDNode::commuteMask(MaskVec);
1681
1682   SDValue Op0 = SV.getOperand(0);
1683   SDValue Op1 = SV.getOperand(1);
1684   return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1685 }
1686
1687 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1688                                        SDValue Val, SDValue DTy,
1689                                        SDValue STy, SDValue Rnd, SDValue Sat,
1690                                        ISD::CvtCode Code) {
1691   // If the src and dest types are the same and the conversion is between
1692   // integer types of the same sign or two floats, no conversion is necessary.
1693   if (DTy == STy &&
1694       (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1695     return Val;
1696
1697   FoldingSetNodeID ID;
1698   SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1699   AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1700   void* IP = nullptr;
1701   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1702     return SDValue(E, 0);
1703
1704   CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1705                                                            dl.getDebugLoc(),
1706                                                            Ops, Code);
1707   CSEMap.InsertNode(N, IP);
1708   InsertNode(N);
1709   return SDValue(N, 0);
1710 }
1711
1712 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1713   FoldingSetNodeID ID;
1714   AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1715   ID.AddInteger(RegNo);
1716   void *IP = nullptr;
1717   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1718     return SDValue(E, 0);
1719
1720   SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1721   CSEMap.InsertNode(N, IP);
1722   InsertNode(N);
1723   return SDValue(N, 0);
1724 }
1725
1726 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1727   FoldingSetNodeID ID;
1728   AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1729   ID.AddPointer(RegMask);
1730   void *IP = nullptr;
1731   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1732     return SDValue(E, 0);
1733
1734   SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1735   CSEMap.InsertNode(N, IP);
1736   InsertNode(N);
1737   return SDValue(N, 0);
1738 }
1739
1740 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1741   FoldingSetNodeID ID;
1742   SDValue Ops[] = { Root };
1743   AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1744   ID.AddPointer(Label);
1745   void *IP = nullptr;
1746   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1747     return SDValue(E, 0);
1748
1749   SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1750                                                 dl.getDebugLoc(), Root, Label);
1751   CSEMap.InsertNode(N, IP);
1752   InsertNode(N);
1753   return SDValue(N, 0);
1754 }
1755
1756
1757 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1758                                       int64_t Offset,
1759                                       bool isTarget,
1760                                       unsigned char TargetFlags) {
1761   unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1762
1763   FoldingSetNodeID ID;
1764   AddNodeIDNode(ID, Opc, getVTList(VT), None);
1765   ID.AddPointer(BA);
1766   ID.AddInteger(Offset);
1767   ID.AddInteger(TargetFlags);
1768   void *IP = nullptr;
1769   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1770     return SDValue(E, 0);
1771
1772   SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1773                                                      TargetFlags);
1774   CSEMap.InsertNode(N, IP);
1775   InsertNode(N);
1776   return SDValue(N, 0);
1777 }
1778
1779 SDValue SelectionDAG::getSrcValue(const Value *V) {
1780   assert((!V || V->getType()->isPointerTy()) &&
1781          "SrcValue is not a pointer?");
1782
1783   FoldingSetNodeID ID;
1784   AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1785   ID.AddPointer(V);
1786
1787   void *IP = nullptr;
1788   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1789     return SDValue(E, 0);
1790
1791   SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1792   CSEMap.InsertNode(N, IP);
1793   InsertNode(N);
1794   return SDValue(N, 0);
1795 }
1796
1797 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1798 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1799   FoldingSetNodeID ID;
1800   AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1801   ID.AddPointer(MD);
1802
1803   void *IP = nullptr;
1804   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1805     return SDValue(E, 0);
1806
1807   SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1808   CSEMap.InsertNode(N, IP);
1809   InsertNode(N);
1810   return SDValue(N, 0);
1811 }
1812
1813 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1814 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1815                                        unsigned SrcAS, unsigned DestAS) {
1816   SDValue Ops[] = {Ptr};
1817   FoldingSetNodeID ID;
1818   AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1819   ID.AddInteger(SrcAS);
1820   ID.AddInteger(DestAS);
1821
1822   void *IP = nullptr;
1823   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1824     return SDValue(E, 0);
1825
1826   SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1827                                                       dl.getDebugLoc(),
1828                                                       VT, Ptr, SrcAS, DestAS);
1829   CSEMap.InsertNode(N, IP);
1830   InsertNode(N);
1831   return SDValue(N, 0);
1832 }
1833
1834 /// getShiftAmountOperand - Return the specified value casted to
1835 /// the target's desired shift amount type.
1836 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1837   EVT OpTy = Op.getValueType();
1838   EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1839   if (OpTy == ShTy || OpTy.isVector()) return Op;
1840
1841   ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ?  ISD::TRUNCATE : ISD::ZERO_EXTEND;
1842   return getNode(Opcode, SDLoc(Op), ShTy, Op);
1843 }
1844
1845 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1846 /// specified value type.
1847 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1848   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1849   unsigned ByteSize = VT.getStoreSize();
1850   Type *Ty = VT.getTypeForEVT(*getContext());
1851   unsigned StackAlign =
1852   std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1853
1854   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1855   return getFrameIndex(FrameIdx, TLI->getPointerTy());
1856 }
1857
1858 /// CreateStackTemporary - Create a stack temporary suitable for holding
1859 /// either of the specified value types.
1860 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1861   unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1862                             VT2.getStoreSizeInBits())/8;
1863   Type *Ty1 = VT1.getTypeForEVT(*getContext());
1864   Type *Ty2 = VT2.getTypeForEVT(*getContext());
1865   const DataLayout *TD = TLI->getDataLayout();
1866   unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1867                             TD->getPrefTypeAlignment(Ty2));
1868
1869   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1870   int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1871   return getFrameIndex(FrameIdx, TLI->getPointerTy());
1872 }
1873
1874 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1875                                 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1876   // These setcc operations always fold.
1877   switch (Cond) {
1878   default: break;
1879   case ISD::SETFALSE:
1880   case ISD::SETFALSE2: return getConstant(0, dl, VT);
1881   case ISD::SETTRUE:
1882   case ISD::SETTRUE2: {
1883     TargetLowering::BooleanContent Cnt =
1884         TLI->getBooleanContents(N1->getValueType(0));
1885     return getConstant(
1886         Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1887         VT);
1888   }
1889
1890   case ISD::SETOEQ:
1891   case ISD::SETOGT:
1892   case ISD::SETOGE:
1893   case ISD::SETOLT:
1894   case ISD::SETOLE:
1895   case ISD::SETONE:
1896   case ISD::SETO:
1897   case ISD::SETUO:
1898   case ISD::SETUEQ:
1899   case ISD::SETUNE:
1900     assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1901     break;
1902   }
1903
1904   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1905     const APInt &C2 = N2C->getAPIntValue();
1906     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1907       const APInt &C1 = N1C->getAPIntValue();
1908
1909       switch (Cond) {
1910       default: llvm_unreachable("Unknown integer setcc!");
1911       case ISD::SETEQ:  return getConstant(C1 == C2, dl, VT);
1912       case ISD::SETNE:  return getConstant(C1 != C2, dl, VT);
1913       case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1914       case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1915       case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1916       case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1917       case ISD::SETLT:  return getConstant(C1.slt(C2), dl, VT);
1918       case ISD::SETGT:  return getConstant(C1.sgt(C2), dl, VT);
1919       case ISD::SETLE:  return getConstant(C1.sle(C2), dl, VT);
1920       case ISD::SETGE:  return getConstant(C1.sge(C2), dl, VT);
1921       }
1922     }
1923   }
1924   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1925     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1926       APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1927       switch (Cond) {
1928       default: break;
1929       case ISD::SETEQ:  if (R==APFloat::cmpUnordered)
1930                           return getUNDEF(VT);
1931                         // fall through
1932       case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1933       case ISD::SETNE:  if (R==APFloat::cmpUnordered)
1934                           return getUNDEF(VT);
1935                         // fall through
1936       case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1937                                            R==APFloat::cmpLessThan, dl, VT);
1938       case ISD::SETLT:  if (R==APFloat::cmpUnordered)
1939                           return getUNDEF(VT);
1940                         // fall through
1941       case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1942       case ISD::SETGT:  if (R==APFloat::cmpUnordered)
1943                           return getUNDEF(VT);
1944                         // fall through
1945       case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1946       case ISD::SETLE:  if (R==APFloat::cmpUnordered)
1947                           return getUNDEF(VT);
1948                         // fall through
1949       case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1950                                            R==APFloat::cmpEqual, dl, VT);
1951       case ISD::SETGE:  if (R==APFloat::cmpUnordered)
1952                           return getUNDEF(VT);
1953                         // fall through
1954       case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1955                                            R==APFloat::cmpEqual, dl, VT);
1956       case ISD::SETO:   return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1957       case ISD::SETUO:  return getConstant(R==APFloat::cmpUnordered, dl, VT);
1958       case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1959                                            R==APFloat::cmpEqual, dl, VT);
1960       case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1961       case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1962                                            R==APFloat::cmpLessThan, dl, VT);
1963       case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1964                                            R==APFloat::cmpUnordered, dl, VT);
1965       case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1966       case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1967       }
1968     } else {
1969       // Ensure that the constant occurs on the RHS.
1970       ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1971       MVT CompVT = N1.getValueType().getSimpleVT();
1972       if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1973         return SDValue();
1974
1975       return getSetCC(dl, VT, N2, N1, SwappedCond);
1976     }
1977   }
1978
1979   // Could not fold it.
1980   return SDValue();
1981 }
1982
1983 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1984 /// use this predicate to simplify operations downstream.
1985 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1986   // This predicate is not safe for vector operations.
1987   if (Op.getValueType().isVector())
1988     return false;
1989
1990   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1991   return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1992 }
1993
1994 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
1995 /// this predicate to simplify operations downstream.  Mask is known to be zero
1996 /// for bits that V cannot have.
1997 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1998                                      unsigned Depth) const {
1999   APInt KnownZero, KnownOne;
2000   computeKnownBits(Op, KnownZero, KnownOne, Depth);
2001   return (KnownZero & Mask) == Mask;
2002 }
2003
2004 /// Determine which bits of Op are known to be either zero or one and return
2005 /// them in the KnownZero/KnownOne bitsets.
2006 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2007                                     APInt &KnownOne, unsigned Depth) const {
2008   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2009
2010   KnownZero = KnownOne = APInt(BitWidth, 0);   // Don't know anything.
2011   if (Depth == 6)
2012     return;  // Limit search depth.
2013
2014   APInt KnownZero2, KnownOne2;
2015
2016   switch (Op.getOpcode()) {
2017   case ISD::Constant:
2018     // We know all of the bits for a constant!
2019     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2020     KnownZero = ~KnownOne;
2021     break;
2022   case ISD::AND:
2023     // If either the LHS or the RHS are Zero, the result is zero.
2024     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2025     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2026
2027     // Output known-1 bits are only known if set in both the LHS & RHS.
2028     KnownOne &= KnownOne2;
2029     // Output known-0 are known to be clear if zero in either the LHS | RHS.
2030     KnownZero |= KnownZero2;
2031     break;
2032   case ISD::OR:
2033     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2034     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2035
2036     // Output known-0 bits are only known if clear in both the LHS & RHS.
2037     KnownZero &= KnownZero2;
2038     // Output known-1 are known to be set if set in either the LHS | RHS.
2039     KnownOne |= KnownOne2;
2040     break;
2041   case ISD::XOR: {
2042     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2043     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2044
2045     // Output known-0 bits are known if clear or set in both the LHS & RHS.
2046     APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2047     // Output known-1 are known to be set if set in only one of the LHS, RHS.
2048     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2049     KnownZero = KnownZeroOut;
2050     break;
2051   }
2052   case ISD::MUL: {
2053     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2054     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2055
2056     // If low bits are zero in either operand, output low known-0 bits.
2057     // Also compute a conserative estimate for high known-0 bits.
2058     // More trickiness is possible, but this is sufficient for the
2059     // interesting case of alignment computation.
2060     KnownOne.clearAllBits();
2061     unsigned TrailZ = KnownZero.countTrailingOnes() +
2062                       KnownZero2.countTrailingOnes();
2063     unsigned LeadZ =  std::max(KnownZero.countLeadingOnes() +
2064                                KnownZero2.countLeadingOnes(),
2065                                BitWidth) - BitWidth;
2066
2067     TrailZ = std::min(TrailZ, BitWidth);
2068     LeadZ = std::min(LeadZ, BitWidth);
2069     KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2070                 APInt::getHighBitsSet(BitWidth, LeadZ);
2071     break;
2072   }
2073   case ISD::UDIV: {
2074     // For the purposes of computing leading zeros we can conservatively
2075     // treat a udiv as a logical right shift by the power of 2 known to
2076     // be less than the denominator.
2077     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2078     unsigned LeadZ = KnownZero2.countLeadingOnes();
2079
2080     KnownOne2.clearAllBits();
2081     KnownZero2.clearAllBits();
2082     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2083     unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2084     if (RHSUnknownLeadingOnes != BitWidth)
2085       LeadZ = std::min(BitWidth,
2086                        LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2087
2088     KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2089     break;
2090   }
2091   case ISD::SELECT:
2092     computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2093     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2094
2095     // Only known if known in both the LHS and RHS.
2096     KnownOne &= KnownOne2;
2097     KnownZero &= KnownZero2;
2098     break;
2099   case ISD::SELECT_CC:
2100     computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2101     computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2102
2103     // Only known if known in both the LHS and RHS.
2104     KnownOne &= KnownOne2;
2105     KnownZero &= KnownZero2;
2106     break;
2107   case ISD::SADDO:
2108   case ISD::UADDO:
2109   case ISD::SSUBO:
2110   case ISD::USUBO:
2111   case ISD::SMULO:
2112   case ISD::UMULO:
2113     if (Op.getResNo() != 1)
2114       break;
2115     // The boolean result conforms to getBooleanContents.
2116     // If we know the result of a setcc has the top bits zero, use this info.
2117     // We know that we have an integer-based boolean since these operations
2118     // are only available for integer.
2119     if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2120             TargetLowering::ZeroOrOneBooleanContent &&
2121         BitWidth > 1)
2122       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2123     break;
2124   case ISD::SETCC:
2125     // If we know the result of a setcc has the top bits zero, use this info.
2126     if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2127             TargetLowering::ZeroOrOneBooleanContent &&
2128         BitWidth > 1)
2129       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2130     break;
2131   case ISD::SHL:
2132     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
2133     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2134       unsigned ShAmt = SA->getZExtValue();
2135
2136       // If the shift count is an invalid immediate, don't do anything.
2137       if (ShAmt >= BitWidth)
2138         break;
2139
2140       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2141       KnownZero <<= ShAmt;
2142       KnownOne  <<= ShAmt;
2143       // low bits known zero.
2144       KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2145     }
2146     break;
2147   case ISD::SRL:
2148     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
2149     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2150       unsigned ShAmt = SA->getZExtValue();
2151
2152       // If the shift count is an invalid immediate, don't do anything.
2153       if (ShAmt >= BitWidth)
2154         break;
2155
2156       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2157       KnownZero = KnownZero.lshr(ShAmt);
2158       KnownOne  = KnownOne.lshr(ShAmt);
2159
2160       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2161       KnownZero |= HighBits;  // High bits known zero.
2162     }
2163     break;
2164   case ISD::SRA:
2165     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2166       unsigned ShAmt = SA->getZExtValue();
2167
2168       // If the shift count is an invalid immediate, don't do anything.
2169       if (ShAmt >= BitWidth)
2170         break;
2171
2172       // If any of the demanded bits are produced by the sign extension, we also
2173       // demand the input sign bit.
2174       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2175
2176       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2177       KnownZero = KnownZero.lshr(ShAmt);
2178       KnownOne  = KnownOne.lshr(ShAmt);
2179
2180       // Handle the sign bits.
2181       APInt SignBit = APInt::getSignBit(BitWidth);
2182       SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
2183
2184       if (KnownZero.intersects(SignBit)) {
2185         KnownZero |= HighBits;  // New bits are known zero.
2186       } else if (KnownOne.intersects(SignBit)) {
2187         KnownOne  |= HighBits;  // New bits are known one.
2188       }
2189     }
2190     break;
2191   case ISD::SIGN_EXTEND_INREG: {
2192     EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2193     unsigned EBits = EVT.getScalarType().getSizeInBits();
2194
2195     // Sign extension.  Compute the demanded bits in the result that are not
2196     // present in the input.
2197     APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2198
2199     APInt InSignBit = APInt::getSignBit(EBits);
2200     APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2201
2202     // If the sign extended bits are demanded, we know that the sign
2203     // bit is demanded.
2204     InSignBit = InSignBit.zext(BitWidth);
2205     if (NewBits.getBoolValue())
2206       InputDemandedBits |= InSignBit;
2207
2208     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2209     KnownOne &= InputDemandedBits;
2210     KnownZero &= InputDemandedBits;
2211
2212     // If the sign bit of the input is known set or clear, then we know the
2213     // top bits of the result.
2214     if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
2215       KnownZero |= NewBits;
2216       KnownOne  &= ~NewBits;
2217     } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
2218       KnownOne  |= NewBits;
2219       KnownZero &= ~NewBits;
2220     } else {                              // Input sign bit unknown
2221       KnownZero &= ~NewBits;
2222       KnownOne  &= ~NewBits;
2223     }
2224     break;
2225   }
2226   case ISD::CTTZ:
2227   case ISD::CTTZ_ZERO_UNDEF:
2228   case ISD::CTLZ:
2229   case ISD::CTLZ_ZERO_UNDEF:
2230   case ISD::CTPOP: {
2231     unsigned LowBits = Log2_32(BitWidth)+1;
2232     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2233     KnownOne.clearAllBits();
2234     break;
2235   }
2236   case ISD::LOAD: {
2237     LoadSDNode *LD = cast<LoadSDNode>(Op);
2238     // If this is a ZEXTLoad and we are looking at the loaded value.
2239     if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2240       EVT VT = LD->getMemoryVT();
2241       unsigned MemBits = VT.getScalarType().getSizeInBits();
2242       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2243     } else if (const MDNode *Ranges = LD->getRanges()) {
2244       computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2245     }
2246     break;
2247   }
2248   case ISD::ZERO_EXTEND: {
2249     EVT InVT = Op.getOperand(0).getValueType();
2250     unsigned InBits = InVT.getScalarType().getSizeInBits();
2251     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2252     KnownZero = KnownZero.trunc(InBits);
2253     KnownOne = KnownOne.trunc(InBits);
2254     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2255     KnownZero = KnownZero.zext(BitWidth);
2256     KnownOne = KnownOne.zext(BitWidth);
2257     KnownZero |= NewBits;
2258     break;
2259   }
2260   case ISD::SIGN_EXTEND: {
2261     EVT InVT = Op.getOperand(0).getValueType();
2262     unsigned InBits = InVT.getScalarType().getSizeInBits();
2263     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2264
2265     KnownZero = KnownZero.trunc(InBits);
2266     KnownOne = KnownOne.trunc(InBits);
2267     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2268
2269     // Note if the sign bit is known to be zero or one.
2270     bool SignBitKnownZero = KnownZero.isNegative();
2271     bool SignBitKnownOne  = KnownOne.isNegative();
2272
2273     KnownZero = KnownZero.zext(BitWidth);
2274     KnownOne = KnownOne.zext(BitWidth);
2275
2276     // If the sign bit is known zero or one, the top bits match.
2277     if (SignBitKnownZero)
2278       KnownZero |= NewBits;
2279     else if (SignBitKnownOne)
2280       KnownOne  |= NewBits;
2281     break;
2282   }
2283   case ISD::ANY_EXTEND: {
2284     EVT InVT = Op.getOperand(0).getValueType();
2285     unsigned InBits = InVT.getScalarType().getSizeInBits();
2286     KnownZero = KnownZero.trunc(InBits);
2287     KnownOne = KnownOne.trunc(InBits);
2288     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2289     KnownZero = KnownZero.zext(BitWidth);
2290     KnownOne = KnownOne.zext(BitWidth);
2291     break;
2292   }
2293   case ISD::TRUNCATE: {
2294     EVT InVT = Op.getOperand(0).getValueType();
2295     unsigned InBits = InVT.getScalarType().getSizeInBits();
2296     KnownZero = KnownZero.zext(InBits);
2297     KnownOne = KnownOne.zext(InBits);
2298     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2299     KnownZero = KnownZero.trunc(BitWidth);
2300     KnownOne = KnownOne.trunc(BitWidth);
2301     break;
2302   }
2303   case ISD::AssertZext: {
2304     EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2305     APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2306     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2307     KnownZero |= (~InMask);
2308     KnownOne  &= (~KnownZero);
2309     break;
2310   }
2311   case ISD::FGETSIGN:
2312     // All bits are zero except the low bit.
2313     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2314     break;
2315
2316   case ISD::SUB: {
2317     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2318       // We know that the top bits of C-X are clear if X contains less bits
2319       // than C (i.e. no wrap-around can happen).  For example, 20-X is
2320       // positive if we can prove that X is >= 0 and < 16.
2321       if (CLHS->getAPIntValue().isNonNegative()) {
2322         unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2323         // NLZ can't be BitWidth with no sign bit
2324         APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2325         computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2326
2327         // If all of the MaskV bits are known to be zero, then we know the
2328         // output top bits are zero, because we now know that the output is
2329         // from [0-C].
2330         if ((KnownZero2 & MaskV) == MaskV) {
2331           unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2332           // Top bits known zero.
2333           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2334         }
2335       }
2336     }
2337   }
2338   // fall through
2339   case ISD::ADD:
2340   case ISD::ADDE: {
2341     // Output known-0 bits are known if clear or set in both the low clear bits
2342     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
2343     // low 3 bits clear.
2344     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2345     unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2346
2347     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2348     KnownZeroOut = std::min(KnownZeroOut,
2349                             KnownZero2.countTrailingOnes());
2350
2351     if (Op.getOpcode() == ISD::ADD) {
2352       KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2353       break;
2354     }
2355
2356     // With ADDE, a carry bit may be added in, so we can only use this
2357     // information if we know (at least) that the low two bits are clear.  We
2358     // then return to the caller that the low bit is unknown but that other bits
2359     // are known zero.
2360     if (KnownZeroOut >= 2) // ADDE
2361       KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2362     break;
2363   }
2364   case ISD::SREM:
2365     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2366       const APInt &RA = Rem->getAPIntValue().abs();
2367       if (RA.isPowerOf2()) {
2368         APInt LowBits = RA - 1;
2369         computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2370
2371         // The low bits of the first operand are unchanged by the srem.
2372         KnownZero = KnownZero2 & LowBits;
2373         KnownOne = KnownOne2 & LowBits;
2374
2375         // If the first operand is non-negative or has all low bits zero, then
2376         // the upper bits are all zero.
2377         if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2378           KnownZero |= ~LowBits;
2379
2380         // If the first operand is negative and not all low bits are zero, then
2381         // the upper bits are all one.
2382         if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2383           KnownOne |= ~LowBits;
2384         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2385       }
2386     }
2387     break;
2388   case ISD::UREM: {
2389     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2390       const APInt &RA = Rem->getAPIntValue();
2391       if (RA.isPowerOf2()) {
2392         APInt LowBits = (RA - 1);
2393         computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2394
2395         // The upper bits are all zero, the lower ones are unchanged.
2396         KnownZero = KnownZero2 | ~LowBits;
2397         KnownOne = KnownOne2 & LowBits;
2398         break;
2399       }
2400     }
2401
2402     // Since the result is less than or equal to either operand, any leading
2403     // zero bits in either operand must also exist in the result.
2404     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2405     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2406
2407     uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2408                                 KnownZero2.countLeadingOnes());
2409     KnownOne.clearAllBits();
2410     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2411     break;
2412   }
2413   case ISD::EXTRACT_ELEMENT: {
2414     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2415     const unsigned Index =
2416       cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2417     const unsigned BitWidth = Op.getValueType().getSizeInBits();
2418
2419     // Remove low part of known bits mask
2420     KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2421     KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2422
2423     // Remove high part of known bit mask
2424     KnownZero = KnownZero.trunc(BitWidth);
2425     KnownOne = KnownOne.trunc(BitWidth);
2426     break;
2427   }
2428   case ISD::FrameIndex:
2429   case ISD::TargetFrameIndex:
2430     if (unsigned Align = InferPtrAlignment(Op)) {
2431       // The low bits are known zero if the pointer is aligned.
2432       KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2433       break;
2434     }
2435     break;
2436
2437   default:
2438     if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2439       break;
2440     // Fallthrough
2441   case ISD::INTRINSIC_WO_CHAIN:
2442   case ISD::INTRINSIC_W_CHAIN:
2443   case ISD::INTRINSIC_VOID:
2444     // Allow the target to implement this method for its nodes.
2445     TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2446     break;
2447   }
2448
2449   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2450 }
2451
2452 /// ComputeNumSignBits - Return the number of times the sign bit of the
2453 /// register is replicated into the other bits.  We know that at least 1 bit
2454 /// is always equal to the sign bit (itself), but other cases can give us
2455 /// information.  For example, immediately after an "SRA X, 2", we know that
2456 /// the top 3 bits are all equal to each other, so we return 3.
2457 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2458   EVT VT = Op.getValueType();
2459   assert(VT.isInteger() && "Invalid VT!");
2460   unsigned VTBits = VT.getScalarType().getSizeInBits();
2461   unsigned Tmp, Tmp2;
2462   unsigned FirstAnswer = 1;
2463
2464   if (Depth == 6)
2465     return 1;  // Limit search depth.
2466
2467   switch (Op.getOpcode()) {
2468   default: break;
2469   case ISD::AssertSext:
2470     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2471     return VTBits-Tmp+1;
2472   case ISD::AssertZext:
2473     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2474     return VTBits-Tmp;
2475
2476   case ISD::Constant: {
2477     const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2478     return Val.getNumSignBits();
2479   }
2480
2481   case ISD::SIGN_EXTEND:
2482     Tmp =
2483         VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2484     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2485
2486   case ISD::SIGN_EXTEND_INREG:
2487     // Max of the input and what this extends.
2488     Tmp =
2489       cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2490     Tmp = VTBits-Tmp+1;
2491
2492     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2493     return std::max(Tmp, Tmp2);
2494
2495   case ISD::SRA:
2496     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2497     // SRA X, C   -> adds C sign bits.
2498     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2499       Tmp += C->getZExtValue();
2500       if (Tmp > VTBits) Tmp = VTBits;
2501     }
2502     return Tmp;
2503   case ISD::SHL:
2504     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2505       // shl destroys sign bits.
2506       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2507       if (C->getZExtValue() >= VTBits ||      // Bad shift.
2508           C->getZExtValue() >= Tmp) break;    // Shifted all sign bits out.
2509       return Tmp - C->getZExtValue();
2510     }
2511     break;
2512   case ISD::AND:
2513   case ISD::OR:
2514   case ISD::XOR:    // NOT is handled here.
2515     // Logical binary ops preserve the number of sign bits at the worst.
2516     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2517     if (Tmp != 1) {
2518       Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2519       FirstAnswer = std::min(Tmp, Tmp2);
2520       // We computed what we know about the sign bits as our first
2521       // answer. Now proceed to the generic code that uses
2522       // computeKnownBits, and pick whichever answer is better.
2523     }
2524     break;
2525
2526   case ISD::SELECT:
2527     Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2528     if (Tmp == 1) return 1;  // Early out.
2529     Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2530     return std::min(Tmp, Tmp2);
2531
2532   case ISD::SADDO:
2533   case ISD::UADDO:
2534   case ISD::SSUBO:
2535   case ISD::USUBO:
2536   case ISD::SMULO:
2537   case ISD::UMULO:
2538     if (Op.getResNo() != 1)
2539       break;
2540     // The boolean result conforms to getBooleanContents.  Fall through.
2541     // If setcc returns 0/-1, all bits are sign bits.
2542     // We know that we have an integer-based boolean since these operations
2543     // are only available for integer.
2544     if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2545         TargetLowering::ZeroOrNegativeOneBooleanContent)
2546       return VTBits;
2547     break;
2548   case ISD::SETCC:
2549     // If setcc returns 0/-1, all bits are sign bits.
2550     if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2551         TargetLowering::ZeroOrNegativeOneBooleanContent)
2552       return VTBits;
2553     break;
2554   case ISD::ROTL:
2555   case ISD::ROTR:
2556     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2557       unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2558
2559       // Handle rotate right by N like a rotate left by 32-N.
2560       if (Op.getOpcode() == ISD::ROTR)
2561         RotAmt = (VTBits-RotAmt) & (VTBits-1);
2562
2563       // If we aren't rotating out all of the known-in sign bits, return the
2564       // number that are left.  This handles rotl(sext(x), 1) for example.
2565       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2566       if (Tmp > RotAmt+1) return Tmp-RotAmt;
2567     }
2568     break;
2569   case ISD::ADD:
2570     // Add can have at most one carry bit.  Thus we know that the output
2571     // is, at worst, one more bit than the inputs.
2572     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2573     if (Tmp == 1) return 1;  // Early out.
2574
2575     // Special case decrementing a value (ADD X, -1):
2576     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2577       if (CRHS->isAllOnesValue()) {
2578         APInt KnownZero, KnownOne;
2579         computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2580
2581         // If the input is known to be 0 or 1, the output is 0/-1, which is all
2582         // sign bits set.
2583         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2584           return VTBits;
2585
2586         // If we are subtracting one from a positive number, there is no carry
2587         // out of the result.
2588         if (KnownZero.isNegative())
2589           return Tmp;
2590       }
2591
2592     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2593     if (Tmp2 == 1) return 1;
2594     return std::min(Tmp, Tmp2)-1;
2595
2596   case ISD::SUB:
2597     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2598     if (Tmp2 == 1) return 1;
2599
2600     // Handle NEG.
2601     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2602       if (CLHS->isNullValue()) {
2603         APInt KnownZero, KnownOne;
2604         computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2605         // If the input is known to be 0 or 1, the output is 0/-1, which is all
2606         // sign bits set.
2607         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2608           return VTBits;
2609
2610         // If the input is known to be positive (the sign bit is known clear),
2611         // the output of the NEG has the same number of sign bits as the input.
2612         if (KnownZero.isNegative())
2613           return Tmp2;
2614
2615         // Otherwise, we treat this like a SUB.
2616       }
2617
2618     // Sub can have at most one carry bit.  Thus we know that the output
2619     // is, at worst, one more bit than the inputs.
2620     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2621     if (Tmp == 1) return 1;  // Early out.
2622     return std::min(Tmp, Tmp2)-1;
2623   case ISD::TRUNCATE:
2624     // FIXME: it's tricky to do anything useful for this, but it is an important
2625     // case for targets like X86.
2626     break;
2627   case ISD::EXTRACT_ELEMENT: {
2628     const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2629     const int BitWidth = Op.getValueType().getSizeInBits();
2630     const int Items =
2631       Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2632
2633     // Get reverse index (starting from 1), Op1 value indexes elements from
2634     // little end. Sign starts at big end.
2635     const int rIndex = Items - 1 -
2636       cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2637
2638     // If the sign portion ends in our element the substraction gives correct
2639     // result. Otherwise it gives either negative or > bitwidth result
2640     return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2641   }
2642   }
2643
2644   // If we are looking at the loaded value of the SDNode.
2645   if (Op.getResNo() == 0) {
2646     // Handle LOADX separately here. EXTLOAD case will fallthrough.
2647     if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2648       unsigned ExtType = LD->getExtensionType();
2649       switch (ExtType) {
2650         default: break;
2651         case ISD::SEXTLOAD:    // '17' bits known
2652           Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2653           return VTBits-Tmp+1;
2654         case ISD::ZEXTLOAD:    // '16' bits known
2655           Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2656           return VTBits-Tmp;
2657       }
2658     }
2659   }
2660
2661   // Allow the target to implement this method for its nodes.
2662   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2663       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2664       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2665       Op.getOpcode() == ISD::INTRINSIC_VOID) {
2666     unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2667     if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2668   }
2669
2670   // Finally, if we can prove that the top bits of the result are 0's or 1's,
2671   // use this information.
2672   APInt KnownZero, KnownOne;
2673   computeKnownBits(Op, KnownZero, KnownOne, Depth);
2674
2675   APInt Mask;
2676   if (KnownZero.isNegative()) {        // sign bit is 0
2677     Mask = KnownZero;
2678   } else if (KnownOne.isNegative()) {  // sign bit is 1;
2679     Mask = KnownOne;
2680   } else {
2681     // Nothing known.
2682     return FirstAnswer;
2683   }
2684
2685   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
2686   // the number of identical bits in the top of the input value.
2687   Mask = ~Mask;
2688   Mask <<= Mask.getBitWidth()-VTBits;
2689   // Return # leading zeros.  We use 'min' here in case Val was zero before
2690   // shifting.  We don't want to return '64' as for an i32 "0".
2691   return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2692 }
2693
2694 /// isBaseWithConstantOffset - Return true if the specified operand is an
2695 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2696 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2697 /// semantics as an ADD.  This handles the equivalence:
2698 ///     X|Cst == X+Cst iff X&Cst = 0.
2699 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2700   if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2701       !isa<ConstantSDNode>(Op.getOperand(1)))
2702     return false;
2703
2704   if (Op.getOpcode() == ISD::OR &&
2705       !MaskedValueIsZero(Op.getOperand(0),
2706                      cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2707     return false;
2708
2709   return true;
2710 }
2711
2712
2713 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2714   // If we're told that NaNs won't happen, assume they won't.
2715   if (getTarget().Options.NoNaNsFPMath)
2716     return true;
2717
2718   // If the value is a constant, we can obviously see if it is a NaN or not.
2719   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2720     return !C->getValueAPF().isNaN();
2721
2722   // TODO: Recognize more cases here.
2723
2724   return false;
2725 }
2726
2727 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2728   // If the value is a constant, we can obviously see if it is a zero or not.
2729   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2730     return !C->isZero();
2731
2732   // TODO: Recognize more cases here.
2733   switch (Op.getOpcode()) {
2734   default: break;
2735   case ISD::OR:
2736     if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2737       return !C->isNullValue();
2738     break;
2739   }
2740
2741   return false;
2742 }
2743
2744 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2745   // Check the obvious case.
2746   if (A == B) return true;
2747
2748   // For for negative and positive zero.
2749   if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2750     if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2751       if (CA->isZero() && CB->isZero()) return true;
2752
2753   // Otherwise they may not be equal.
2754   return false;
2755 }
2756
2757 /// getNode - Gets or creates the specified node.
2758 ///
2759 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2760   FoldingSetNodeID ID;
2761   AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2762   void *IP = nullptr;
2763   if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2764     return SDValue(E, 0);
2765
2766   SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2767                                          DL.getDebugLoc(), getVTList(VT));
2768   CSEMap.InsertNode(N, IP);
2769
2770   InsertNode(N);
2771   return SDValue(N, 0);
2772 }
2773
2774 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2775                               EVT VT, SDValue Operand) {
2776   // Constant fold unary operations with an integer constant operand. Even
2777   // opaque constant will be folded, because the folding of unary operations
2778   // doesn't create new constants with different values. Nevertheless, the
2779   // opaque flag is preserved during folding to prevent future folding with
2780   // other constants.
2781   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2782     const APInt &Val = C->getAPIntValue();
2783     switch (Opcode) {
2784     default: break;
2785     case ISD::SIGN_EXTEND:
2786       return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2787                          C->isTargetOpcode(), C->isOpaque());
2788     case ISD::ANY_EXTEND:
2789     case ISD::ZERO_EXTEND:
2790     case ISD::TRUNCATE:
2791       return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2792                          C->isTargetOpcode(), C->isOpaque());
2793     case ISD::UINT_TO_FP:
2794     case ISD::SINT_TO_FP: {
2795       APFloat apf(EVTToAPFloatSemantics(VT),
2796                   APInt::getNullValue(VT.getSizeInBits()));
2797       (void)apf.convertFromAPInt(Val,
2798                                  Opcode==ISD::SINT_TO_FP,
2799                                  APFloat::rmNearestTiesToEven);
2800       return getConstantFP(apf, DL, VT);
2801     }
2802     case ISD::BITCAST:
2803       if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2804         return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2805       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2806         return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2807       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2808         return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2809       break;
2810     case ISD::BSWAP:
2811       return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2812                          C->isOpaque());
2813     case ISD::CTPOP:
2814       return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2815                          C->isOpaque());
2816     case ISD::CTLZ:
2817     case ISD::CTLZ_ZERO_UNDEF:
2818       return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2819                          C->isOpaque());
2820     case ISD::CTTZ:
2821     case ISD::CTTZ_ZERO_UNDEF:
2822       return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2823                          C->isOpaque());
2824     }
2825   }
2826
2827   // Constant fold unary operations with a floating point constant operand.
2828   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2829     APFloat V = C->getValueAPF();    // make copy
2830     switch (Opcode) {
2831     case ISD::FNEG:
2832       V.changeSign();
2833       return getConstantFP(V, DL, VT);
2834     case ISD::FABS:
2835       V.clearSign();
2836       return getConstantFP(V, DL, VT);
2837     case ISD::FCEIL: {
2838       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2839       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2840         return getConstantFP(V, DL, VT);
2841       break;
2842     }
2843     case ISD::FTRUNC: {
2844       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2845       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2846         return getConstantFP(V, DL, VT);
2847       break;
2848     }
2849     case ISD::FFLOOR: {
2850       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2851       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2852         return getConstantFP(V, DL, VT);
2853       break;
2854     }
2855     case ISD::FP_EXTEND: {
2856       bool ignored;
2857       // This can return overflow, underflow, or inexact; we don't care.
2858       // FIXME need to be more flexible about rounding mode.
2859       (void)V.convert(EVTToAPFloatSemantics(VT),
2860                       APFloat::rmNearestTiesToEven, &ignored);
2861       return getConstantFP(V, DL, VT);
2862     }
2863     case ISD::FP_TO_SINT:
2864     case ISD::FP_TO_UINT: {
2865       integerPart x[2];
2866       bool ignored;
2867       static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2868       // FIXME need to be more flexible about rounding mode.
2869       APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2870                             Opcode==ISD::FP_TO_SINT,
2871                             APFloat::rmTowardZero, &ignored);
2872       if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
2873         break;
2874       APInt api(VT.getSizeInBits(), x);
2875       return getConstant(api, DL, VT);
2876     }
2877     case ISD::BITCAST:
2878       if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2879         return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2880       else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2881         return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2882       else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2883         return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2884       break;
2885     }
2886   }
2887
2888   // Constant fold unary operations with a vector integer or float operand.
2889   if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2890     if (BV->isConstant()) {
2891       switch (Opcode) {
2892       default:
2893         // FIXME: Entirely reasonable to perform folding of other unary
2894         // operations here as the need arises.
2895         break;
2896       case ISD::FNEG:
2897       case ISD::FABS:
2898       case ISD::FCEIL:
2899       case ISD::FTRUNC:
2900       case ISD::FFLOOR:
2901       case ISD::FP_EXTEND:
2902       case ISD::FP_TO_SINT:
2903       case ISD::FP_TO_UINT:
2904       case ISD::TRUNCATE:
2905       case ISD::UINT_TO_FP:
2906       case ISD::SINT_TO_FP: {
2907         EVT SVT = VT.getScalarType();
2908         EVT InVT = BV->getValueType(0);
2909         EVT InSVT = InVT.getScalarType();
2910
2911         // Find legal integer scalar type for constant promotion and
2912         // ensure that its scalar size is at least as large as source.
2913         EVT LegalSVT = SVT;
2914         if (SVT.isInteger()) {
2915           LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2916           if (LegalSVT.bitsLT(SVT)) break;
2917         }
2918
2919         // Let the above scalar folding handle the folding of each element.
2920         SmallVector<SDValue, 8> Ops;
2921         for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2922           SDValue OpN = BV->getOperand(i);
2923           EVT OpVT = OpN.getValueType();
2924
2925           // Build vector (integer) scalar operands may need implicit
2926           // truncation - do this before constant folding.
2927           if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2928             OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2929
2930           OpN = getNode(Opcode, DL, SVT, OpN);
2931
2932           // Legalize the (integer) scalar constant if necessary.
2933           if (LegalSVT != SVT)
2934             OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2935
2936           if (OpN.getOpcode() != ISD::UNDEF &&
2937               OpN.getOpcode() != ISD::Constant &&
2938               OpN.getOpcode() != ISD::ConstantFP)
2939             break;
2940           Ops.push_back(OpN);
2941         }
2942         if (Ops.size() == VT.getVectorNumElements())
2943           return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2944         break;
2945       }
2946       }
2947     }
2948   }
2949
2950   unsigned OpOpcode = Operand.getNode()->getOpcode();
2951   switch (Opcode) {
2952   case ISD::TokenFactor:
2953   case ISD::MERGE_VALUES:
2954   case ISD::CONCAT_VECTORS:
2955     return Operand;         // Factor, merge or concat of one node?  No need.
2956   case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2957   case ISD::FP_EXTEND:
2958     assert(VT.isFloatingPoint() &&
2959            Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2960     if (Operand.getValueType() == VT) return Operand;  // noop conversion.
2961     assert((!VT.isVector() ||
2962             VT.getVectorNumElements() ==
2963             Operand.getValueType().getVectorNumElements()) &&
2964            "Vector element count mismatch!");
2965     if (Operand.getOpcode() == ISD::UNDEF)
2966       return getUNDEF(VT);
2967     break;
2968   case ISD::SIGN_EXTEND:
2969     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2970            "Invalid SIGN_EXTEND!");
2971     if (Operand.getValueType() == VT) return Operand;   // noop extension
2972     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2973            "Invalid sext node, dst < src!");
2974     assert((!VT.isVector() ||
2975             VT.getVectorNumElements() ==
2976             Operand.getValueType().getVectorNumElements()) &&
2977            "Vector element count mismatch!");
2978     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2979       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2980     else if (OpOpcode == ISD::UNDEF)
2981       // sext(undef) = 0, because the top bits will all be the same.
2982       return getConstant(0, DL, VT);
2983     break;
2984   case ISD::ZERO_EXTEND:
2985     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2986            "Invalid ZERO_EXTEND!");
2987     if (Operand.getValueType() == VT) return Operand;   // noop extension
2988     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2989            "Invalid zext node, dst < src!");
2990     assert((!VT.isVector() ||
2991             VT.getVectorNumElements() ==
2992             Operand.getValueType().getVectorNumElements()) &&
2993            "Vector element count mismatch!");
2994     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
2995       return getNode(ISD::ZERO_EXTEND, DL, VT,
2996                      Operand.getNode()->getOperand(0));
2997     else if (OpOpcode == ISD::UNDEF)
2998       // zext(undef) = 0, because the top bits will be zero.
2999       return getConstant(0, DL, VT);
3000     break;
3001   case ISD::ANY_EXTEND:
3002     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3003            "Invalid ANY_EXTEND!");
3004     if (Operand.getValueType() == VT) return Operand;   // noop extension
3005     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3006            "Invalid anyext node, dst < src!");
3007     assert((!VT.isVector() ||
3008             VT.getVectorNumElements() ==
3009             Operand.getValueType().getVectorNumElements()) &&
3010            "Vector element count mismatch!");
3011
3012     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3013         OpOpcode == ISD::ANY_EXTEND)
3014       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
3015       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3016     else if (OpOpcode == ISD::UNDEF)
3017       return getUNDEF(VT);
3018
3019     // (ext (trunx x)) -> x
3020     if (OpOpcode == ISD::TRUNCATE) {
3021       SDValue OpOp = Operand.getNode()->getOperand(0);
3022       if (OpOp.getValueType() == VT)
3023         return OpOp;
3024     }
3025     break;
3026   case ISD::TRUNCATE:
3027     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3028            "Invalid TRUNCATE!");
3029     if (Operand.getValueType() == VT) return Operand;   // noop truncate
3030     assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3031            "Invalid truncate node, src < dst!");
3032     assert((!VT.isVector() ||
3033             VT.getVectorNumElements() ==
3034             Operand.getValueType().getVectorNumElements()) &&
3035            "Vector element count mismatch!");
3036     if (OpOpcode == ISD::TRUNCATE)
3037       return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3038     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3039         OpOpcode == ISD::ANY_EXTEND) {
3040       // If the source is smaller than the dest, we still need an extend.
3041       if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3042             .bitsLT(VT.getScalarType()))
3043         return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3044       if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3045         return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3046       return Operand.getNode()->getOperand(0);
3047     }
3048     if (OpOpcode == ISD::UNDEF)
3049       return getUNDEF(VT);
3050     break;
3051   case ISD::BITCAST:
3052     // Basic sanity checking.
3053     assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3054            && "Cannot BITCAST between types of different sizes!");
3055     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
3056     if (OpOpcode == ISD::BITCAST)  // bitconv(bitconv(x)) -> bitconv(x)
3057       return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3058     if (OpOpcode == ISD::UNDEF)
3059       return getUNDEF(VT);
3060     break;
3061   case ISD::SCALAR_TO_VECTOR:
3062     assert(VT.isVector() && !Operand.getValueType().isVector() &&
3063            (VT.getVectorElementType() == Operand.getValueType() ||
3064             (VT.getVectorElementType().isInteger() &&
3065              Operand.getValueType().isInteger() &&
3066              VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3067            "Illegal SCALAR_TO_VECTOR node!");
3068     if (OpOpcode == ISD::UNDEF)
3069       return getUNDEF(VT);
3070     // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3071     if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3072         isa<ConstantSDNode>(Operand.getOperand(1)) &&
3073         Operand.getConstantOperandVal(1) == 0 &&
3074         Operand.getOperand(0).getValueType() == VT)
3075       return Operand.getOperand(0);
3076     break;
3077   case ISD::FNEG:
3078     // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3079     if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3080       return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3081                      Operand.getNode()->getOperand(0));
3082     if (OpOpcode == ISD::FNEG)  // --X -> X
3083       return Operand.getNode()->getOperand(0);
3084     break;
3085   case ISD::FABS:
3086     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
3087       return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3088     break;
3089   }
3090
3091   SDNode *N;
3092   SDVTList VTs = getVTList(VT);
3093   if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3094     FoldingSetNodeID ID;
3095     SDValue Ops[1] = { Operand };
3096     AddNodeIDNode(ID, Opcode, VTs, Ops);
3097     void *IP = nullptr;
3098     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3099       return SDValue(E, 0);
3100
3101     N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3102                                         DL.getDebugLoc(), VTs, Operand);
3103     CSEMap.InsertNode(N, IP);
3104   } else {
3105     N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3106                                         DL.getDebugLoc(), VTs, Operand);
3107   }
3108
3109   InsertNode(N);
3110   return SDValue(N, 0);
3111 }
3112
3113 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3114                                         const APInt &C2) {
3115   switch (Opcode) {
3116   case ISD::ADD:  return std::make_pair(C1 + C2, true);
3117   case ISD::SUB:  return std::make_pair(C1 - C2, true);
3118   case ISD::MUL:  return std::make_pair(C1 * C2, true);
3119   case ISD::AND:  return std::make_pair(C1 & C2, true);
3120   case ISD::OR:   return std::make_pair(C1 | C2, true);
3121   case ISD::XOR:  return std::make_pair(C1 ^ C2, true);
3122   case ISD::SHL:  return std::make_pair(C1 << C2, true);
3123   case ISD::SRL:  return std::make_pair(C1.lshr(C2), true);
3124   case ISD::SRA:  return std::make_pair(C1.ashr(C2), true);
3125   case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3126   case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3127   case ISD::UDIV:
3128     if (!C2.getBoolValue())
3129       break;
3130     return std::make_pair(C1.udiv(C2), true);
3131   case ISD::UREM:
3132     if (!C2.getBoolValue())
3133       break;
3134     return std::make_pair(C1.urem(C2), true);
3135   case ISD::SDIV:
3136     if (!C2.getBoolValue())
3137       break;
3138     return std::make_pair(C1.sdiv(C2), true);
3139   case ISD::SREM:
3140     if (!C2.getBoolValue())
3141       break;
3142     return std::make_pair(C1.srem(C2), true);
3143   }
3144   return std::make_pair(APInt(1, 0), false);
3145 }
3146
3147 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3148                                              const ConstantSDNode *Cst1,
3149                                              const ConstantSDNode *Cst2) {
3150   if (Cst1->isOpaque() || Cst2->isOpaque())
3151     return SDValue();
3152
3153   std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3154                                             Cst2->getAPIntValue());
3155   if (!Folded.second)
3156     return SDValue();
3157   return getConstant(Folded.first, DL, VT);
3158 }
3159
3160 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3161                                              SDNode *Cst1, SDNode *Cst2) {
3162   // If the opcode is a target-specific ISD node, there's nothing we can
3163   // do here and the operand rules may not line up with the below, so
3164   // bail early.
3165   if (Opcode >= ISD::BUILTIN_OP_END)
3166     return SDValue();
3167
3168   // Handle the case of two scalars.
3169   if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3170     if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3171       if (SDValue Folded =
3172           FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3173         if (!VT.isVector())
3174           return Folded;
3175         SmallVector<SDValue, 4> Outputs;
3176         // We may have a vector type but a scalar result. Create a splat.
3177         Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3178         // Build a big vector out of the scalar elements we generated.
3179         return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3180       } else {
3181         return SDValue();
3182       }
3183     }
3184   }
3185
3186   // For vectors extract each constant element into Inputs so we can constant
3187   // fold them individually.
3188   BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3189   BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3190   if (!BV1 || !BV2)
3191     return SDValue();
3192
3193   assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3194
3195   EVT SVT = VT.getScalarType();
3196   SmallVector<SDValue, 4> Outputs;
3197   for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3198     ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3199     ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3200     if (!V1 || !V2) // Not a constant, bail.
3201       return SDValue();
3202
3203     if (V1->isOpaque() || V2->isOpaque())
3204       return SDValue();
3205
3206     // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3207     // FIXME: This is valid and could be handled by truncating the APInts.
3208     if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3209       return SDValue();
3210
3211     // Fold one vector element.
3212     std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3213                                               V2->getAPIntValue());
3214     if (!Folded.second)
3215       return SDValue();
3216     Outputs.push_back(getConstant(Folded.first, DL, SVT));
3217   }
3218
3219   assert(VT.getVectorNumElements() == Outputs.size() &&
3220          "Vector size mismatch!");
3221
3222   // We may have a vector type but a scalar result. Create a splat.
3223   Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3224
3225   // Build a big vector out of the scalar elements we generated.
3226   return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3227 }
3228
3229 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3230                               SDValue N2, bool nuw, bool nsw, bool exact) {
3231   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3232   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3233   switch (Opcode) {
3234   default: break;
3235   case ISD::TokenFactor:
3236     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3237            N2.getValueType() == MVT::Other && "Invalid token factor!");
3238     // Fold trivial token factors.
3239     if (N1.getOpcode() == ISD::EntryToken) return N2;
3240     if (N2.getOpcode() == ISD::EntryToken) return N1;
3241     if (N1 == N2) return N1;
3242     break;
3243   case ISD::CONCAT_VECTORS:
3244     // Concat of UNDEFs is UNDEF.
3245     if (N1.getOpcode() == ISD::UNDEF &&
3246         N2.getOpcode() == ISD::UNDEF)
3247       return getUNDEF(VT);
3248
3249     // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3250     // one big BUILD_VECTOR.
3251     if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3252         N2.getOpcode() == ISD::BUILD_VECTOR) {
3253       SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3254                                     N1.getNode()->op_end());
3255       Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3256
3257       // BUILD_VECTOR requires all inputs to be of the same type, find the
3258       // maximum type and extend them all.
3259       EVT SVT = VT.getScalarType();
3260       for (SDValue Op : Elts)
3261         SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3262       if (SVT.bitsGT(VT.getScalarType()))
3263         for (SDValue &Op : Elts)
3264           Op = TLI->isZExtFree(Op.getValueType(), SVT)
3265              ? getZExtOrTrunc(Op, DL, SVT)
3266              : getSExtOrTrunc(Op, DL, SVT);
3267
3268       return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3269     }
3270     break;
3271   case ISD::AND:
3272     assert(VT.isInteger() && "This operator does not apply to FP types!");
3273     assert(N1.getValueType() == N2.getValueType() &&
3274            N1.getValueType() == VT && "Binary operator types must match!");
3275     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
3276     // worth handling here.
3277     if (N2C && N2C->isNullValue())
3278       return N2;
3279     if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
3280       return N1;
3281     break;
3282   case ISD::OR:
3283   case ISD::XOR:
3284   case ISD::ADD:
3285   case ISD::SUB:
3286     assert(VT.isInteger() && "This operator does not apply to FP types!");
3287     assert(N1.getValueType() == N2.getValueType() &&
3288            N1.getValueType() == VT && "Binary operator types must match!");
3289     // (X ^|+- 0) -> X.  This commonly occurs when legalizing i64 values, so
3290     // it's worth handling here.
3291     if (N2C && N2C->isNullValue())
3292       return N1;
3293     break;
3294   case ISD::UDIV:
3295   case ISD::UREM:
3296   case ISD::MULHU:
3297   case ISD::MULHS:
3298   case ISD::MUL:
3299   case ISD::SDIV:
3300   case ISD::SREM:
3301     assert(VT.isInteger() && "This operator does not apply to FP types!");
3302     assert(N1.getValueType() == N2.getValueType() &&
3303            N1.getValueType() == VT && "Binary operator types must match!");
3304     break;
3305   case ISD::FADD:
3306   case ISD::FSUB:
3307   case ISD::FMUL:
3308   case ISD::FDIV:
3309   case ISD::FREM:
3310     if (getTarget().Options.UnsafeFPMath) {
3311       if (Opcode == ISD::FADD) {
3312         // 0+x --> x
3313         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3314           if (CFP->getValueAPF().isZero())
3315             return N2;
3316         // x+0 --> x
3317         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3318           if (CFP->getValueAPF().isZero())
3319             return N1;
3320       } else if (Opcode == ISD::FSUB) {
3321         // x-0 --> x
3322         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3323           if (CFP->getValueAPF().isZero())
3324             return N1;
3325       } else if (Opcode == ISD::FMUL) {
3326         ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3327         SDValue V = N2;
3328
3329         // If the first operand isn't the constant, try the second
3330         if (!CFP) {
3331           CFP = dyn_cast<ConstantFPSDNode>(N2);
3332           V = N1;
3333         }
3334
3335         if (CFP) {
3336           // 0*x --> 0
3337           if (CFP->isZero())
3338             return SDValue(CFP,0);
3339           // 1*x --> x
3340           if (CFP->isExactlyValue(1.0))
3341             return V;
3342         }
3343       }
3344     }
3345     assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3346     assert(N1.getValueType() == N2.getValueType() &&
3347            N1.getValueType() == VT && "Binary operator types must match!");
3348     break;
3349   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
3350     assert(N1.getValueType() == VT &&
3351            N1.getValueType().isFloatingPoint() &&
3352            N2.getValueType().isFloatingPoint() &&
3353            "Invalid FCOPYSIGN!");
3354     break;
3355   case ISD::SHL:
3356   case ISD::SRA:
3357   case ISD::SRL:
3358   case ISD::ROTL:
3359   case ISD::ROTR:
3360     assert(VT == N1.getValueType() &&
3361            "Shift operators return type must be the same as their first arg");
3362     assert(VT.isInteger() && N2.getValueType().isInteger() &&
3363            "Shifts only work on integers");
3364     assert((!VT.isVector() || VT == N2.getValueType()) &&