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