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