Make APFloat constructor require explicit semantics.
[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 "SDNodeOrdering.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/TargetTransformInfo.h"
23 #include "llvm/Analysis/ValueTracking.h"
24 #include "llvm/Assembly/Writer.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/MachineConstantPool.h"
27 #include "llvm/CodeGen/MachineFrameInfo.h"
28 #include "llvm/CodeGen/MachineModuleInfo.h"
29 #include "llvm/DebugInfo.h"
30 #include "llvm/IR/CallingConv.h"
31 #include "llvm/IR/Constants.h"
32 #include "llvm/IR/DataLayout.h"
33 #include "llvm/IR/DerivedTypes.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/GlobalAlias.h"
36 #include "llvm/IR/GlobalVariable.h"
37 #include "llvm/IR/Intrinsics.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/ErrorHandling.h"
41 #include "llvm/Support/ManagedStatic.h"
42 #include "llvm/Support/MathExtras.h"
43 #include "llvm/Support/Mutex.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Target/TargetInstrInfo.h"
46 #include "llvm/Target/TargetIntrinsicInfo.h"
47 #include "llvm/Target/TargetLowering.h"
48 #include "llvm/Target/TargetMachine.h"
49 #include "llvm/Target/TargetOptions.h"
50 #include "llvm/Target/TargetRegisterInfo.h"
51 #include "llvm/Target/TargetSelectionDAGInfo.h"
52 #include <algorithm>
53 #include <cmath>
54 using namespace llvm;
55
56 /// makeVTList - Return an instance of the SDVTList struct initialized with the
57 /// specified members.
58 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59   SDVTList Res = {VTs, NumVTs};
60   return Res;
61 }
62
63 // Default null implementations of the callbacks.
64 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66
67 //===----------------------------------------------------------------------===//
68 //                              ConstantFPSDNode Class
69 //===----------------------------------------------------------------------===//
70
71 /// isExactlyValue - We don't rely on operator== working on double values, as
72 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73 /// As such, this method can be used to do an exact bit-for-bit comparison of
74 /// two floating point values.
75 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76   return getValueAPF().bitwiseIsEqual(V);
77 }
78
79 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80                                            const APFloat& Val) {
81   assert(VT.isFloatingPoint() && "Can only convert between FP types");
82
83   // convert modifies in place, so make a copy.
84   APFloat Val2 = APFloat(Val);
85   bool losesInfo;
86   (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87                       APFloat::rmNearestTiesToEven,
88                       &losesInfo);
89   return !losesInfo;
90 }
91
92 //===----------------------------------------------------------------------===//
93 //                              ISD Namespace
94 //===----------------------------------------------------------------------===//
95
96 /// isBuildVectorAllOnes - Return true if the specified node is a
97 /// BUILD_VECTOR where all of the elements are ~0 or undef.
98 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99   // Look through a bit convert.
100   if (N->getOpcode() == ISD::BITCAST)
101     N = N->getOperand(0).getNode();
102
103   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104
105   unsigned i = 0, e = N->getNumOperands();
106
107   // Skip over all of the undef values.
108   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
109     ++i;
110
111   // Do not accept an all-undef vector.
112   if (i == e) return false;
113
114   // Do not accept build_vectors that aren't all constants or which have non-~0
115   // elements. We have to be a bit careful here, as the type of the constant
116   // may not be the same as the type of the vector elements due to type
117   // legalization (the elements are promoted to a legal type for the target and
118   // a vector of a type may be legal when the base element type is not).
119   // We only want to check enough bits to cover the vector elements, because
120   // we care if the resultant vector is all ones, not whether the individual
121   // constants are.
122   SDValue NotZero = N->getOperand(i);
123   unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125     if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126       return false;
127   } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128     if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
129       return false;
130   } else
131     return false;
132
133   // Okay, we have at least one ~0 value, check to see if the rest match or are
134   // undefs. Even with the above element type twiddling, this should be OK, as
135   // the same type legalization should have applied to all the elements.
136   for (++i; i != e; ++i)
137     if (N->getOperand(i) != NotZero &&
138         N->getOperand(i).getOpcode() != ISD::UNDEF)
139       return false;
140   return true;
141 }
142
143
144 /// isBuildVectorAllZeros - Return true if the specified node is a
145 /// BUILD_VECTOR where all of the elements are 0 or undef.
146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147   // Look through a bit convert.
148   if (N->getOpcode() == ISD::BITCAST)
149     N = N->getOperand(0).getNode();
150
151   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152
153   unsigned i = 0, e = N->getNumOperands();
154
155   // Skip over all of the undef values.
156   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
157     ++i;
158
159   // Do not accept an all-undef vector.
160   if (i == e) return false;
161
162   // Do not accept build_vectors that aren't all constants or which have non-0
163   // elements.
164   SDValue Zero = N->getOperand(i);
165   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
166     if (!CN->isNullValue())
167       return false;
168   } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
169     if (!CFPN->getValueAPF().isPosZero())
170       return false;
171   } else
172     return false;
173
174   // Okay, we have at least one 0 value, check to see if the rest match or are
175   // undefs.
176   for (++i; i != e; ++i)
177     if (N->getOperand(i) != Zero &&
178         N->getOperand(i).getOpcode() != ISD::UNDEF)
179       return false;
180   return true;
181 }
182
183 /// isScalarToVector - Return true if the specified node is a
184 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
185 /// element is not an undef.
186 bool ISD::isScalarToVector(const SDNode *N) {
187   if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
188     return true;
189
190   if (N->getOpcode() != ISD::BUILD_VECTOR)
191     return false;
192   if (N->getOperand(0).getOpcode() == ISD::UNDEF)
193     return false;
194   unsigned NumElems = N->getNumOperands();
195   if (NumElems == 1)
196     return false;
197   for (unsigned i = 1; i < NumElems; ++i) {
198     SDValue V = N->getOperand(i);
199     if (V.getOpcode() != ISD::UNDEF)
200       return false;
201   }
202   return true;
203 }
204
205 /// allOperandsUndef - Return true if the node has at least one operand
206 /// and all operands of the specified node are ISD::UNDEF.
207 bool ISD::allOperandsUndef(const SDNode *N) {
208   // Return false if the node has no operands.
209   // This is "logically inconsistent" with the definition of "all" but
210   // is probably the desired behavior.
211   if (N->getNumOperands() == 0)
212     return false;
213
214   for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
215     if (N->getOperand(i).getOpcode() != ISD::UNDEF)
216       return false;
217
218   return true;
219 }
220
221 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
222 /// when given the operation for (X op Y).
223 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
224   // To perform this operation, we just need to swap the L and G bits of the
225   // operation.
226   unsigned OldL = (Operation >> 2) & 1;
227   unsigned OldG = (Operation >> 1) & 1;
228   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
229                        (OldL << 1) |       // New G bit
230                        (OldG << 2));       // New L bit.
231 }
232
233 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
234 /// 'op' is a valid SetCC operation.
235 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
236   unsigned Operation = Op;
237   if (isInteger)
238     Operation ^= 7;   // Flip L, G, E bits, but not U.
239   else
240     Operation ^= 15;  // Flip all of the condition bits.
241
242   if (Operation > ISD::SETTRUE2)
243     Operation &= ~8;  // Don't let N and U bits get set.
244
245   return ISD::CondCode(Operation);
246 }
247
248
249 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
250 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
251 /// if the operation does not depend on the sign of the input (setne and seteq).
252 static int isSignedOp(ISD::CondCode Opcode) {
253   switch (Opcode) {
254   default: llvm_unreachable("Illegal integer setcc operation!");
255   case ISD::SETEQ:
256   case ISD::SETNE: return 0;
257   case ISD::SETLT:
258   case ISD::SETLE:
259   case ISD::SETGT:
260   case ISD::SETGE: return 1;
261   case ISD::SETULT:
262   case ISD::SETULE:
263   case ISD::SETUGT:
264   case ISD::SETUGE: return 2;
265   }
266 }
267
268 /// getSetCCOrOperation - Return the result of a logical OR between different
269 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
270 /// returns SETCC_INVALID if it is not possible to represent the resultant
271 /// comparison.
272 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
273                                        bool isInteger) {
274   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
275     // Cannot fold a signed integer setcc with an unsigned integer setcc.
276     return ISD::SETCC_INVALID;
277
278   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
279
280   // If the N and U bits get set then the resultant comparison DOES suddenly
281   // care about orderedness, and is true when ordered.
282   if (Op > ISD::SETTRUE2)
283     Op &= ~16;     // Clear the U bit if the N bit is set.
284
285   // Canonicalize illegal integer setcc's.
286   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
287     Op = ISD::SETNE;
288
289   return ISD::CondCode(Op);
290 }
291
292 /// getSetCCAndOperation - Return the result of a logical AND between different
293 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
294 /// function returns zero if it is not possible to represent the resultant
295 /// comparison.
296 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
297                                         bool isInteger) {
298   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
299     // Cannot fold a signed setcc with an unsigned setcc.
300     return ISD::SETCC_INVALID;
301
302   // Combine all of the condition bits.
303   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
304
305   // Canonicalize illegal integer setcc's.
306   if (isInteger) {
307     switch (Result) {
308     default: break;
309     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
310     case ISD::SETOEQ:                                 // SETEQ  & SETU[LG]E
311     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
312     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
313     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
314     }
315   }
316
317   return Result;
318 }
319
320 //===----------------------------------------------------------------------===//
321 //                           SDNode Profile Support
322 //===----------------------------------------------------------------------===//
323
324 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
325 ///
326 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
327   ID.AddInteger(OpC);
328 }
329
330 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
331 /// solely with their pointer.
332 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
333   ID.AddPointer(VTList.VTs);
334 }
335
336 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
337 ///
338 static void AddNodeIDOperands(FoldingSetNodeID &ID,
339                               const SDValue *Ops, unsigned NumOps) {
340   for (; NumOps; --NumOps, ++Ops) {
341     ID.AddPointer(Ops->getNode());
342     ID.AddInteger(Ops->getResNo());
343   }
344 }
345
346 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
347 ///
348 static void AddNodeIDOperands(FoldingSetNodeID &ID,
349                               const SDUse *Ops, unsigned NumOps) {
350   for (; NumOps; --NumOps, ++Ops) {
351     ID.AddPointer(Ops->getNode());
352     ID.AddInteger(Ops->getResNo());
353   }
354 }
355
356 static void AddNodeIDNode(FoldingSetNodeID &ID,
357                           unsigned short OpC, SDVTList VTList,
358                           const SDValue *OpList, unsigned N) {
359   AddNodeIDOpcode(ID, OpC);
360   AddNodeIDValueTypes(ID, VTList);
361   AddNodeIDOperands(ID, OpList, N);
362 }
363
364 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
365 /// the NodeID data.
366 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
367   switch (N->getOpcode()) {
368   case ISD::TargetExternalSymbol:
369   case ISD::ExternalSymbol:
370     llvm_unreachable("Should only be used on nodes with operands");
371   default: break;  // Normal nodes don't need extra info.
372   case ISD::TargetConstant:
373   case ISD::Constant:
374     ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
375     break;
376   case ISD::TargetConstantFP:
377   case ISD::ConstantFP: {
378     ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
379     break;
380   }
381   case ISD::TargetGlobalAddress:
382   case ISD::GlobalAddress:
383   case ISD::TargetGlobalTLSAddress:
384   case ISD::GlobalTLSAddress: {
385     const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
386     ID.AddPointer(GA->getGlobal());
387     ID.AddInteger(GA->getOffset());
388     ID.AddInteger(GA->getTargetFlags());
389     ID.AddInteger(GA->getAddressSpace());
390     break;
391   }
392   case ISD::BasicBlock:
393     ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
394     break;
395   case ISD::Register:
396     ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
397     break;
398   case ISD::RegisterMask:
399     ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
400     break;
401   case ISD::SRCVALUE:
402     ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
403     break;
404   case ISD::FrameIndex:
405   case ISD::TargetFrameIndex:
406     ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
407     break;
408   case ISD::JumpTable:
409   case ISD::TargetJumpTable:
410     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
411     ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
412     break;
413   case ISD::ConstantPool:
414   case ISD::TargetConstantPool: {
415     const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
416     ID.AddInteger(CP->getAlignment());
417     ID.AddInteger(CP->getOffset());
418     if (CP->isMachineConstantPoolEntry())
419       CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
420     else
421       ID.AddPointer(CP->getConstVal());
422     ID.AddInteger(CP->getTargetFlags());
423     break;
424   }
425   case ISD::TargetIndex: {
426     const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
427     ID.AddInteger(TI->getIndex());
428     ID.AddInteger(TI->getOffset());
429     ID.AddInteger(TI->getTargetFlags());
430     break;
431   }
432   case ISD::LOAD: {
433     const LoadSDNode *LD = cast<LoadSDNode>(N);
434     ID.AddInteger(LD->getMemoryVT().getRawBits());
435     ID.AddInteger(LD->getRawSubclassData());
436     ID.AddInteger(LD->getPointerInfo().getAddrSpace());
437     break;
438   }
439   case ISD::STORE: {
440     const StoreSDNode *ST = cast<StoreSDNode>(N);
441     ID.AddInteger(ST->getMemoryVT().getRawBits());
442     ID.AddInteger(ST->getRawSubclassData());
443     ID.AddInteger(ST->getPointerInfo().getAddrSpace());
444     break;
445   }
446   case ISD::ATOMIC_CMP_SWAP:
447   case ISD::ATOMIC_SWAP:
448   case ISD::ATOMIC_LOAD_ADD:
449   case ISD::ATOMIC_LOAD_SUB:
450   case ISD::ATOMIC_LOAD_AND:
451   case ISD::ATOMIC_LOAD_OR:
452   case ISD::ATOMIC_LOAD_XOR:
453   case ISD::ATOMIC_LOAD_NAND:
454   case ISD::ATOMIC_LOAD_MIN:
455   case ISD::ATOMIC_LOAD_MAX:
456   case ISD::ATOMIC_LOAD_UMIN:
457   case ISD::ATOMIC_LOAD_UMAX:
458   case ISD::ATOMIC_LOAD:
459   case ISD::ATOMIC_STORE: {
460     const AtomicSDNode *AT = cast<AtomicSDNode>(N);
461     ID.AddInteger(AT->getMemoryVT().getRawBits());
462     ID.AddInteger(AT->getRawSubclassData());
463     ID.AddInteger(AT->getPointerInfo().getAddrSpace());
464     break;
465   }
466   case ISD::PREFETCH: {
467     const MemSDNode *PF = cast<MemSDNode>(N);
468     ID.AddInteger(PF->getPointerInfo().getAddrSpace());
469     break;
470   }
471   case ISD::VECTOR_SHUFFLE: {
472     const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
473     for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
474          i != e; ++i)
475       ID.AddInteger(SVN->getMaskElt(i));
476     break;
477   }
478   case ISD::TargetBlockAddress:
479   case ISD::BlockAddress: {
480     const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
481     ID.AddPointer(BA->getBlockAddress());
482     ID.AddInteger(BA->getOffset());
483     ID.AddInteger(BA->getTargetFlags());
484     break;
485   }
486   } // end switch (N->getOpcode())
487
488   // Target specific memory nodes could also have address spaces to check.
489   if (N->isTargetMemoryOpcode())
490     ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
491 }
492
493 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
494 /// data.
495 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
496   AddNodeIDOpcode(ID, N->getOpcode());
497   // Add the return value info.
498   AddNodeIDValueTypes(ID, N->getVTList());
499   // Add the operand info.
500   AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
501
502   // Handle SDNode leafs with special info.
503   AddNodeIDCustom(ID, N);
504 }
505
506 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
507 /// the CSE map that carries volatility, temporalness, indexing mode, and
508 /// extension/truncation information.
509 ///
510 static inline unsigned
511 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
512                      bool isNonTemporal, bool isInvariant) {
513   assert((ConvType & 3) == ConvType &&
514          "ConvType may not require more than 2 bits!");
515   assert((AM & 7) == AM &&
516          "AM may not require more than 3 bits!");
517   return ConvType |
518          (AM << 2) |
519          (isVolatile << 5) |
520          (isNonTemporal << 6) |
521          (isInvariant << 7);
522 }
523
524 //===----------------------------------------------------------------------===//
525 //                              SelectionDAG Class
526 //===----------------------------------------------------------------------===//
527
528 /// doNotCSE - Return true if CSE should not be performed for this node.
529 static bool doNotCSE(SDNode *N) {
530   if (N->getValueType(0) == MVT::Glue)
531     return true; // Never CSE anything that produces a flag.
532
533   switch (N->getOpcode()) {
534   default: break;
535   case ISD::HANDLENODE:
536   case ISD::EH_LABEL:
537     return true;   // Never CSE these nodes.
538   }
539
540   // Check that remaining values produced are not flags.
541   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
542     if (N->getValueType(i) == MVT::Glue)
543       return true; // Never CSE anything that produces a flag.
544
545   return false;
546 }
547
548 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
549 /// SelectionDAG.
550 void SelectionDAG::RemoveDeadNodes() {
551   // Create a dummy node (which is not added to allnodes), that adds a reference
552   // to the root node, preventing it from being deleted.
553   HandleSDNode Dummy(getRoot());
554
555   SmallVector<SDNode*, 128> DeadNodes;
556
557   // Add all obviously-dead nodes to the DeadNodes worklist.
558   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
559     if (I->use_empty())
560       DeadNodes.push_back(I);
561
562   RemoveDeadNodes(DeadNodes);
563
564   // If the root changed (e.g. it was a dead load, update the root).
565   setRoot(Dummy.getValue());
566 }
567
568 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
569 /// given list, and any nodes that become unreachable as a result.
570 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
571
572   // Process the worklist, deleting the nodes and adding their uses to the
573   // worklist.
574   while (!DeadNodes.empty()) {
575     SDNode *N = DeadNodes.pop_back_val();
576
577     for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
578       DUL->NodeDeleted(N, 0);
579
580     // Take the node out of the appropriate CSE map.
581     RemoveNodeFromCSEMaps(N);
582
583     // Next, brutally remove the operand list.  This is safe to do, as there are
584     // no cycles in the graph.
585     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
586       SDUse &Use = *I++;
587       SDNode *Operand = Use.getNode();
588       Use.set(SDValue());
589
590       // Now that we removed this operand, see if there are no uses of it left.
591       if (Operand->use_empty())
592         DeadNodes.push_back(Operand);
593     }
594
595     DeallocateNode(N);
596   }
597 }
598
599 void SelectionDAG::RemoveDeadNode(SDNode *N){
600   SmallVector<SDNode*, 16> DeadNodes(1, N);
601
602   // Create a dummy node that adds a reference to the root node, preventing
603   // it from being deleted.  (This matters if the root is an operand of the
604   // dead node.)
605   HandleSDNode Dummy(getRoot());
606
607   RemoveDeadNodes(DeadNodes);
608 }
609
610 void SelectionDAG::DeleteNode(SDNode *N) {
611   // First take this out of the appropriate CSE map.
612   RemoveNodeFromCSEMaps(N);
613
614   // Finally, remove uses due to operands of this node, remove from the
615   // AllNodes list, and delete the node.
616   DeleteNodeNotInCSEMaps(N);
617 }
618
619 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
620   assert(N != AllNodes.begin() && "Cannot delete the entry node!");
621   assert(N->use_empty() && "Cannot delete a node that is not dead!");
622
623   // Drop all of the operands and decrement used node's use counts.
624   N->DropOperands();
625
626   DeallocateNode(N);
627 }
628
629 void SelectionDAG::DeallocateNode(SDNode *N) {
630   if (N->OperandsNeedDelete)
631     delete[] N->OperandList;
632
633   // Set the opcode to DELETED_NODE to help catch bugs when node
634   // memory is reallocated.
635   N->NodeType = ISD::DELETED_NODE;
636
637   NodeAllocator.Deallocate(AllNodes.remove(N));
638
639   // Remove the ordering of this node.
640   Ordering->remove(N);
641
642   // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
643   ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
644   for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
645     DbgVals[i]->setIsInvalidated();
646 }
647
648 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
649 /// correspond to it.  This is useful when we're about to delete or repurpose
650 /// the node.  We don't want future request for structurally identical nodes
651 /// to return N anymore.
652 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
653   bool Erased = false;
654   switch (N->getOpcode()) {
655   case ISD::HANDLENODE: return false;  // noop.
656   case ISD::CONDCODE:
657     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
658            "Cond code doesn't exist!");
659     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
660     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
661     break;
662   case ISD::ExternalSymbol:
663     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
664     break;
665   case ISD::TargetExternalSymbol: {
666     ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
667     Erased = TargetExternalSymbols.erase(
668                std::pair<std::string,unsigned char>(ESN->getSymbol(),
669                                                     ESN->getTargetFlags()));
670     break;
671   }
672   case ISD::VALUETYPE: {
673     EVT VT = cast<VTSDNode>(N)->getVT();
674     if (VT.isExtended()) {
675       Erased = ExtendedValueTypeNodes.erase(VT);
676     } else {
677       Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
678       ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
679     }
680     break;
681   }
682   default:
683     // Remove it from the CSE Map.
684     assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
685     assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
686     Erased = CSEMap.RemoveNode(N);
687     break;
688   }
689 #ifndef NDEBUG
690   // Verify that the node was actually in one of the CSE maps, unless it has a
691   // flag result (which cannot be CSE'd) or is one of the special cases that are
692   // not subject to CSE.
693   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
694       !N->isMachineOpcode() && !doNotCSE(N)) {
695     N->dump(this);
696     dbgs() << "\n";
697     llvm_unreachable("Node is not in map!");
698   }
699 #endif
700   return Erased;
701 }
702
703 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
704 /// maps and modified in place. Add it back to the CSE maps, unless an identical
705 /// node already exists, in which case transfer all its users to the existing
706 /// node. This transfer can potentially trigger recursive merging.
707 ///
708 void
709 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
710   // For node types that aren't CSE'd, just act as if no identical node
711   // already exists.
712   if (!doNotCSE(N)) {
713     SDNode *Existing = CSEMap.GetOrInsertNode(N);
714     if (Existing != N) {
715       // If there was already an existing matching node, use ReplaceAllUsesWith
716       // to replace the dead one with the existing one.  This can cause
717       // recursive merging of other unrelated nodes down the line.
718       ReplaceAllUsesWith(N, Existing);
719
720       // N is now dead. Inform the listeners and delete it.
721       for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
722         DUL->NodeDeleted(N, Existing);
723       DeleteNodeNotInCSEMaps(N);
724       return;
725     }
726   }
727
728   // If the node doesn't already exist, we updated it.  Inform listeners.
729   for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
730     DUL->NodeUpdated(N);
731 }
732
733 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
734 /// were replaced with those specified.  If this node is never memoized,
735 /// return null, otherwise return a pointer to the slot it would take.  If a
736 /// node already exists with these operands, the slot will be non-null.
737 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
738                                            void *&InsertPos) {
739   if (doNotCSE(N))
740     return 0;
741
742   SDValue Ops[] = { Op };
743   FoldingSetNodeID ID;
744   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
745   AddNodeIDCustom(ID, N);
746   SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
747   return Node;
748 }
749
750 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
751 /// were replaced with those specified.  If this node is never memoized,
752 /// return null, otherwise return a pointer to the slot it would take.  If a
753 /// node already exists with these operands, the slot will be non-null.
754 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
755                                            SDValue Op1, SDValue Op2,
756                                            void *&InsertPos) {
757   if (doNotCSE(N))
758     return 0;
759
760   SDValue Ops[] = { Op1, Op2 };
761   FoldingSetNodeID ID;
762   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
763   AddNodeIDCustom(ID, N);
764   SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
765   return Node;
766 }
767
768
769 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
770 /// were replaced with those specified.  If this node is never memoized,
771 /// return null, otherwise return a pointer to the slot it would take.  If a
772 /// node already exists with these operands, the slot will be non-null.
773 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
774                                            const SDValue *Ops,unsigned NumOps,
775                                            void *&InsertPos) {
776   if (doNotCSE(N))
777     return 0;
778
779   FoldingSetNodeID ID;
780   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
781   AddNodeIDCustom(ID, N);
782   SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
783   return Node;
784 }
785
786 #ifndef NDEBUG
787 /// VerifyNodeCommon - Sanity check the given node.  Aborts if it is invalid.
788 static void VerifyNodeCommon(SDNode *N) {
789   switch (N->getOpcode()) {
790   default:
791     break;
792   case ISD::BUILD_PAIR: {
793     EVT VT = N->getValueType(0);
794     assert(N->getNumValues() == 1 && "Too many results!");
795     assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
796            "Wrong return type!");
797     assert(N->getNumOperands() == 2 && "Wrong number of operands!");
798     assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
799            "Mismatched operand types!");
800     assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
801            "Wrong operand type!");
802     assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
803            "Wrong return type size");
804     break;
805   }
806   case ISD::BUILD_VECTOR: {
807     assert(N->getNumValues() == 1 && "Too many results!");
808     assert(N->getValueType(0).isVector() && "Wrong return type!");
809     assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
810            "Wrong number of operands!");
811     EVT EltVT = N->getValueType(0).getVectorElementType();
812     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
813       assert((I->getValueType() == EltVT ||
814              (EltVT.isInteger() && I->getValueType().isInteger() &&
815               EltVT.bitsLE(I->getValueType()))) &&
816             "Wrong operand type!");
817       assert(I->getValueType() == N->getOperand(0).getValueType() &&
818              "Operands must all have the same type");
819     }
820     break;
821   }
822   }
823 }
824
825 /// VerifySDNode - Sanity check the given SDNode.  Aborts if it is invalid.
826 static void VerifySDNode(SDNode *N) {
827   // The SDNode allocators cannot be used to allocate nodes with fields that are
828   // not present in an SDNode!
829   assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
830   assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
831   assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
832   assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
833   assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
834   assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
835   assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
836   assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
837   assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
838   assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
839   assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
840   assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
841   assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
842   assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
843   assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
844   assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
845   assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
846   assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
847   assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
848
849   VerifyNodeCommon(N);
850 }
851
852 /// VerifyMachineNode - Sanity check the given MachineNode.  Aborts if it is
853 /// invalid.
854 static void VerifyMachineNode(SDNode *N) {
855   // The MachineNode allocators cannot be used to allocate nodes with fields
856   // that are not present in a MachineNode!
857   // Currently there are no such nodes.
858
859   VerifyNodeCommon(N);
860 }
861 #endif // NDEBUG
862
863 /// getEVTAlignment - Compute the default alignment value for the
864 /// given type.
865 ///
866 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
867   Type *Ty = VT == MVT::iPTR ?
868                    PointerType::get(Type::getInt8Ty(*getContext()), 0) :
869                    VT.getTypeForEVT(*getContext());
870
871   return TLI.getDataLayout()->getABITypeAlignment(Ty);
872 }
873
874 // EntryNode could meaningfully have debug info if we can find it...
875 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
876   : TM(tm), TLI(*tm.getTargetLowering()), TSI(*tm.getSelectionDAGInfo()),
877     TTI(0), OptLevel(OL), EntryNode(ISD::EntryToken, DebugLoc(),
878                                     getVTList(MVT::Other)),
879     Root(getEntryNode()), Ordering(0), UpdateListeners(0) {
880   AllNodes.push_back(&EntryNode);
881   Ordering = new SDNodeOrdering();
882   DbgInfo = new SDDbgInfo();
883 }
884
885 void SelectionDAG::init(MachineFunction &mf, const TargetTransformInfo *tti) {
886   MF = &mf;
887   TTI = tti;
888   Context = &mf.getFunction()->getContext();
889 }
890
891 SelectionDAG::~SelectionDAG() {
892   assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
893   allnodes_clear();
894   delete Ordering;
895   delete DbgInfo;
896 }
897
898 void SelectionDAG::allnodes_clear() {
899   assert(&*AllNodes.begin() == &EntryNode);
900   AllNodes.remove(AllNodes.begin());
901   while (!AllNodes.empty())
902     DeallocateNode(AllNodes.begin());
903 }
904
905 void SelectionDAG::clear() {
906   allnodes_clear();
907   OperandAllocator.Reset();
908   CSEMap.clear();
909
910   ExtendedValueTypeNodes.clear();
911   ExternalSymbols.clear();
912   TargetExternalSymbols.clear();
913   std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
914             static_cast<CondCodeSDNode*>(0));
915   std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
916             static_cast<SDNode*>(0));
917
918   EntryNode.UseList = 0;
919   AllNodes.push_back(&EntryNode);
920   Root = getEntryNode();
921   Ordering->clear();
922   DbgInfo->clear();
923 }
924
925 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
926   return VT.bitsGT(Op.getValueType()) ?
927     getNode(ISD::ANY_EXTEND, DL, VT, Op) :
928     getNode(ISD::TRUNCATE, DL, VT, Op);
929 }
930
931 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
932   return VT.bitsGT(Op.getValueType()) ?
933     getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
934     getNode(ISD::TRUNCATE, DL, VT, Op);
935 }
936
937 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
938   return VT.bitsGT(Op.getValueType()) ?
939     getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
940     getNode(ISD::TRUNCATE, DL, VT, Op);
941 }
942
943 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) {
944   assert(!VT.isVector() &&
945          "getZeroExtendInReg should use the vector element type instead of "
946          "the vector type!");
947   if (Op.getValueType() == VT) return Op;
948   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
949   APInt Imm = APInt::getLowBitsSet(BitWidth,
950                                    VT.getSizeInBits());
951   return getNode(ISD::AND, DL, Op.getValueType(), Op,
952                  getConstant(Imm, Op.getValueType()));
953 }
954
955 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
956 ///
957 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) {
958   EVT EltVT = VT.getScalarType();
959   SDValue NegOne =
960     getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
961   return getNode(ISD::XOR, DL, VT, Val, NegOne);
962 }
963
964 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
965   EVT EltVT = VT.getScalarType();
966   assert((EltVT.getSizeInBits() >= 64 ||
967          (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
968          "getConstant with a uint64_t value that doesn't fit in the type!");
969   return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
970 }
971
972 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
973   return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
974 }
975
976 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
977   assert(VT.isInteger() && "Cannot create FP integer constant!");
978
979   EVT EltVT = VT.getScalarType();
980   const ConstantInt *Elt = &Val;
981
982   // In some cases the vector type is legal but the element type is illegal and
983   // needs to be promoted, for example v8i8 on ARM.  In this case, promote the
984   // inserted value (the type does not need to match the vector element type).
985   // Any extra bits introduced will be truncated away.
986   if (VT.isVector() && TLI.getTypeAction(*getContext(), EltVT) ==
987       TargetLowering::TypePromoteInteger) {
988    EltVT = TLI.getTypeToTransformTo(*getContext(), EltVT);
989    APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
990    Elt = ConstantInt::get(*getContext(), NewVal);
991   }
992
993   assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
994          "APInt size does not match type size!");
995   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
996   FoldingSetNodeID ID;
997   AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
998   ID.AddPointer(Elt);
999   void *IP = 0;
1000   SDNode *N = NULL;
1001   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1002     if (!VT.isVector())
1003       return SDValue(N, 0);
1004
1005   if (!N) {
1006     N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1007     CSEMap.InsertNode(N, IP);
1008     AllNodes.push_back(N);
1009   }
1010
1011   SDValue Result(N, 0);
1012   if (VT.isVector()) {
1013     SmallVector<SDValue, 8> Ops;
1014     Ops.assign(VT.getVectorNumElements(), Result);
1015     Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1016   }
1017   return Result;
1018 }
1019
1020 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1021   return getConstant(Val, TLI.getPointerTy(), isTarget);
1022 }
1023
1024
1025 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1026   return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1027 }
1028
1029 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1030   assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1031
1032   EVT EltVT = VT.getScalarType();
1033
1034   // Do the map lookup using the actual bit pattern for the floating point
1035   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1036   // we don't have issues with SNANs.
1037   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1038   FoldingSetNodeID ID;
1039   AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1040   ID.AddPointer(&V);
1041   void *IP = 0;
1042   SDNode *N = NULL;
1043   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1044     if (!VT.isVector())
1045       return SDValue(N, 0);
1046
1047   if (!N) {
1048     N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1049     CSEMap.InsertNode(N, IP);
1050     AllNodes.push_back(N);
1051   }
1052
1053   SDValue Result(N, 0);
1054   if (VT.isVector()) {
1055     SmallVector<SDValue, 8> Ops;
1056     Ops.assign(VT.getVectorNumElements(), Result);
1057     // FIXME DebugLoc info might be appropriate here
1058     Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1059   }
1060   return Result;
1061 }
1062
1063 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1064   EVT EltVT = VT.getScalarType();
1065   if (EltVT==MVT::f32)
1066     return getConstantFP(APFloat((float)Val), VT, isTarget);
1067   else if (EltVT==MVT::f64)
1068     return getConstantFP(APFloat(Val), VT, isTarget);
1069   else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1070            EltVT==MVT::f16) {
1071     bool ignored;
1072     APFloat apf = APFloat(Val);
1073     apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1074                 &ignored);
1075     return getConstantFP(apf, VT, isTarget);
1076   } else
1077     llvm_unreachable("Unsupported type in getConstantFP");
1078 }
1079
1080 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, DebugLoc DL,
1081                                        EVT VT, int64_t Offset,
1082                                        bool isTargetGA,
1083                                        unsigned char TargetFlags) {
1084   assert((TargetFlags == 0 || isTargetGA) &&
1085          "Cannot set target flags on target-independent globals");
1086
1087   // Truncate (with sign-extension) the offset value to the pointer size.
1088   unsigned BitWidth = TLI.getPointerTy().getSizeInBits();
1089   if (BitWidth < 64)
1090     Offset = SignExtend64(Offset, BitWidth);
1091
1092   const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1093   if (!GVar) {
1094     // If GV is an alias then use the aliasee for determining thread-localness.
1095     if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1096       GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1097   }
1098
1099   unsigned Opc;
1100   if (GVar && GVar->isThreadLocal())
1101     Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1102   else
1103     Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1104
1105   FoldingSetNodeID ID;
1106   AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1107   ID.AddPointer(GV);
1108   ID.AddInteger(Offset);
1109   ID.AddInteger(TargetFlags);
1110   ID.AddInteger(GV->getType()->getAddressSpace());
1111   void *IP = 0;
1112   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1113     return SDValue(E, 0);
1114
1115   SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL, GV, VT,
1116                                                       Offset, TargetFlags);
1117   CSEMap.InsertNode(N, IP);
1118   AllNodes.push_back(N);
1119   return SDValue(N, 0);
1120 }
1121
1122 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1123   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1124   FoldingSetNodeID ID;
1125   AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1126   ID.AddInteger(FI);
1127   void *IP = 0;
1128   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1129     return SDValue(E, 0);
1130
1131   SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1132   CSEMap.InsertNode(N, IP);
1133   AllNodes.push_back(N);
1134   return SDValue(N, 0);
1135 }
1136
1137 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1138                                    unsigned char TargetFlags) {
1139   assert((TargetFlags == 0 || isTarget) &&
1140          "Cannot set target flags on target-independent jump tables");
1141   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1142   FoldingSetNodeID ID;
1143   AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1144   ID.AddInteger(JTI);
1145   ID.AddInteger(TargetFlags);
1146   void *IP = 0;
1147   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1148     return SDValue(E, 0);
1149
1150   SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1151                                                   TargetFlags);
1152   CSEMap.InsertNode(N, IP);
1153   AllNodes.push_back(N);
1154   return SDValue(N, 0);
1155 }
1156
1157 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1158                                       unsigned Alignment, int Offset,
1159                                       bool isTarget,
1160                                       unsigned char TargetFlags) {
1161   assert((TargetFlags == 0 || isTarget) &&
1162          "Cannot set target flags on target-independent globals");
1163   if (Alignment == 0)
1164     Alignment = TLI.getDataLayout()->getPrefTypeAlignment(C->getType());
1165   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1166   FoldingSetNodeID ID;
1167   AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1168   ID.AddInteger(Alignment);
1169   ID.AddInteger(Offset);
1170   ID.AddPointer(C);
1171   ID.AddInteger(TargetFlags);
1172   void *IP = 0;
1173   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1174     return SDValue(E, 0);
1175
1176   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1177                                                      Alignment, TargetFlags);
1178   CSEMap.InsertNode(N, IP);
1179   AllNodes.push_back(N);
1180   return SDValue(N, 0);
1181 }
1182
1183
1184 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1185                                       unsigned Alignment, int Offset,
1186                                       bool isTarget,
1187                                       unsigned char TargetFlags) {
1188   assert((TargetFlags == 0 || isTarget) &&
1189          "Cannot set target flags on target-independent globals");
1190   if (Alignment == 0)
1191     Alignment = TLI.getDataLayout()->getPrefTypeAlignment(C->getType());
1192   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1193   FoldingSetNodeID ID;
1194   AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1195   ID.AddInteger(Alignment);
1196   ID.AddInteger(Offset);
1197   C->addSelectionDAGCSEId(ID);
1198   ID.AddInteger(TargetFlags);
1199   void *IP = 0;
1200   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1201     return SDValue(E, 0);
1202
1203   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1204                                                      Alignment, TargetFlags);
1205   CSEMap.InsertNode(N, IP);
1206   AllNodes.push_back(N);
1207   return SDValue(N, 0);
1208 }
1209
1210 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1211                                      unsigned char TargetFlags) {
1212   FoldingSetNodeID ID;
1213   AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1214   ID.AddInteger(Index);
1215   ID.AddInteger(Offset);
1216   ID.AddInteger(TargetFlags);
1217   void *IP = 0;
1218   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1219     return SDValue(E, 0);
1220
1221   SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1222                                                     TargetFlags);
1223   CSEMap.InsertNode(N, IP);
1224   AllNodes.push_back(N);
1225   return SDValue(N, 0);
1226 }
1227
1228 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1229   FoldingSetNodeID ID;
1230   AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1231   ID.AddPointer(MBB);
1232   void *IP = 0;
1233   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1234     return SDValue(E, 0);
1235
1236   SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1237   CSEMap.InsertNode(N, IP);
1238   AllNodes.push_back(N);
1239   return SDValue(N, 0);
1240 }
1241
1242 SDValue SelectionDAG::getValueType(EVT VT) {
1243   if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1244       ValueTypeNodes.size())
1245     ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1246
1247   SDNode *&N = VT.isExtended() ?
1248     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1249
1250   if (N) return SDValue(N, 0);
1251   N = new (NodeAllocator) VTSDNode(VT);
1252   AllNodes.push_back(N);
1253   return SDValue(N, 0);
1254 }
1255
1256 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1257   SDNode *&N = ExternalSymbols[Sym];
1258   if (N) return SDValue(N, 0);
1259   N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1260   AllNodes.push_back(N);
1261   return SDValue(N, 0);
1262 }
1263
1264 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1265                                               unsigned char TargetFlags) {
1266   SDNode *&N =
1267     TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1268                                                                TargetFlags)];
1269   if (N) return SDValue(N, 0);
1270   N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1271   AllNodes.push_back(N);
1272   return SDValue(N, 0);
1273 }
1274
1275 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1276   if ((unsigned)Cond >= CondCodeNodes.size())
1277     CondCodeNodes.resize(Cond+1);
1278
1279   if (CondCodeNodes[Cond] == 0) {
1280     CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1281     CondCodeNodes[Cond] = N;
1282     AllNodes.push_back(N);
1283   }
1284
1285   return SDValue(CondCodeNodes[Cond], 0);
1286 }
1287
1288 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1289 // the shuffle mask M that point at N1 to point at N2, and indices that point
1290 // N2 to point at N1.
1291 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1292   std::swap(N1, N2);
1293   int NElts = M.size();
1294   for (int i = 0; i != NElts; ++i) {
1295     if (M[i] >= NElts)
1296       M[i] -= NElts;
1297     else if (M[i] >= 0)
1298       M[i] += NElts;
1299   }
1300 }
1301
1302 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1,
1303                                        SDValue N2, const int *Mask) {
1304   assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE");
1305   assert(VT.isVector() && N1.getValueType().isVector() &&
1306          "Vector Shuffle VTs must be a vectors");
1307   assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType()
1308          && "Vector Shuffle VTs must have same element type");
1309
1310   // Canonicalize shuffle undef, undef -> undef
1311   if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1312     return getUNDEF(VT);
1313
1314   // Validate that all indices in Mask are within the range of the elements
1315   // input to the shuffle.
1316   unsigned NElts = VT.getVectorNumElements();
1317   SmallVector<int, 8> MaskVec;
1318   for (unsigned i = 0; i != NElts; ++i) {
1319     assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1320     MaskVec.push_back(Mask[i]);
1321   }
1322
1323   // Canonicalize shuffle v, v -> v, undef
1324   if (N1 == N2) {
1325     N2 = getUNDEF(VT);
1326     for (unsigned i = 0; i != NElts; ++i)
1327       if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1328   }
1329
1330   // Canonicalize shuffle undef, v -> v, undef.  Commute the shuffle mask.
1331   if (N1.getOpcode() == ISD::UNDEF)
1332     commuteShuffle(N1, N2, MaskVec);
1333
1334   // Canonicalize all index into lhs, -> shuffle lhs, undef
1335   // Canonicalize all index into rhs, -> shuffle rhs, undef
1336   bool AllLHS = true, AllRHS = true;
1337   bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1338   for (unsigned i = 0; i != NElts; ++i) {
1339     if (MaskVec[i] >= (int)NElts) {
1340       if (N2Undef)
1341         MaskVec[i] = -1;
1342       else
1343         AllLHS = false;
1344     } else if (MaskVec[i] >= 0) {
1345       AllRHS = false;
1346     }
1347   }
1348   if (AllLHS && AllRHS)
1349     return getUNDEF(VT);
1350   if (AllLHS && !N2Undef)
1351     N2 = getUNDEF(VT);
1352   if (AllRHS) {
1353     N1 = getUNDEF(VT);
1354     commuteShuffle(N1, N2, MaskVec);
1355   }
1356
1357   // If Identity shuffle, or all shuffle in to undef, return that node.
1358   bool AllUndef = true;
1359   bool Identity = true;
1360   for (unsigned i = 0; i != NElts; ++i) {
1361     if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1362     if (MaskVec[i] >= 0) AllUndef = false;
1363   }
1364   if (Identity && NElts == N1.getValueType().getVectorNumElements())
1365     return N1;
1366   if (AllUndef)
1367     return getUNDEF(VT);
1368
1369   FoldingSetNodeID ID;
1370   SDValue Ops[2] = { N1, N2 };
1371   AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1372   for (unsigned i = 0; i != NElts; ++i)
1373     ID.AddInteger(MaskVec[i]);
1374
1375   void* IP = 0;
1376   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1377     return SDValue(E, 0);
1378
1379   // Allocate the mask array for the node out of the BumpPtrAllocator, since
1380   // SDNode doesn't have access to it.  This memory will be "leaked" when
1381   // the node is deallocated, but recovered when the NodeAllocator is released.
1382   int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1383   memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1384
1385   ShuffleVectorSDNode *N =
1386     new (NodeAllocator) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc);
1387   CSEMap.InsertNode(N, IP);
1388   AllNodes.push_back(N);
1389   return SDValue(N, 0);
1390 }
1391
1392 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl,
1393                                        SDValue Val, SDValue DTy,
1394                                        SDValue STy, SDValue Rnd, SDValue Sat,
1395                                        ISD::CvtCode Code) {
1396   // If the src and dest types are the same and the conversion is between
1397   // integer types of the same sign or two floats, no conversion is necessary.
1398   if (DTy == STy &&
1399       (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1400     return Val;
1401
1402   FoldingSetNodeID ID;
1403   SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1404   AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1405   void* IP = 0;
1406   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1407     return SDValue(E, 0);
1408
1409   CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl, Ops, 5,
1410                                                            Code);
1411   CSEMap.InsertNode(N, IP);
1412   AllNodes.push_back(N);
1413   return SDValue(N, 0);
1414 }
1415
1416 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1417   FoldingSetNodeID ID;
1418   AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1419   ID.AddInteger(RegNo);
1420   void *IP = 0;
1421   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1422     return SDValue(E, 0);
1423
1424   SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1425   CSEMap.InsertNode(N, IP);
1426   AllNodes.push_back(N);
1427   return SDValue(N, 0);
1428 }
1429
1430 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1431   FoldingSetNodeID ID;
1432   AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1433   ID.AddPointer(RegMask);
1434   void *IP = 0;
1435   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1436     return SDValue(E, 0);
1437
1438   SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1439   CSEMap.InsertNode(N, IP);
1440   AllNodes.push_back(N);
1441   return SDValue(N, 0);
1442 }
1443
1444 SDValue SelectionDAG::getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label) {
1445   FoldingSetNodeID ID;
1446   SDValue Ops[] = { Root };
1447   AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1448   ID.AddPointer(Label);
1449   void *IP = 0;
1450   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1451     return SDValue(E, 0);
1452
1453   SDNode *N = new (NodeAllocator) EHLabelSDNode(dl, Root, Label);
1454   CSEMap.InsertNode(N, IP);
1455   AllNodes.push_back(N);
1456   return SDValue(N, 0);
1457 }
1458
1459
1460 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1461                                       int64_t Offset,
1462                                       bool isTarget,
1463                                       unsigned char TargetFlags) {
1464   unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1465
1466   FoldingSetNodeID ID;
1467   AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1468   ID.AddPointer(BA);
1469   ID.AddInteger(Offset);
1470   ID.AddInteger(TargetFlags);
1471   void *IP = 0;
1472   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1473     return SDValue(E, 0);
1474
1475   SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1476                                                      TargetFlags);
1477   CSEMap.InsertNode(N, IP);
1478   AllNodes.push_back(N);
1479   return SDValue(N, 0);
1480 }
1481
1482 SDValue SelectionDAG::getSrcValue(const Value *V) {
1483   assert((!V || V->getType()->isPointerTy()) &&
1484          "SrcValue is not a pointer?");
1485
1486   FoldingSetNodeID ID;
1487   AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1488   ID.AddPointer(V);
1489
1490   void *IP = 0;
1491   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1492     return SDValue(E, 0);
1493
1494   SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1495   CSEMap.InsertNode(N, IP);
1496   AllNodes.push_back(N);
1497   return SDValue(N, 0);
1498 }
1499
1500 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1501 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1502   FoldingSetNodeID ID;
1503   AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1504   ID.AddPointer(MD);
1505
1506   void *IP = 0;
1507   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1508     return SDValue(E, 0);
1509
1510   SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1511   CSEMap.InsertNode(N, IP);
1512   AllNodes.push_back(N);
1513   return SDValue(N, 0);
1514 }
1515
1516
1517 /// getShiftAmountOperand - Return the specified value casted to
1518 /// the target's desired shift amount type.
1519 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1520   EVT OpTy = Op.getValueType();
1521   MVT ShTy = TLI.getShiftAmountTy(LHSTy);
1522   if (OpTy == ShTy || OpTy.isVector()) return Op;
1523
1524   ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ?  ISD::TRUNCATE : ISD::ZERO_EXTEND;
1525   return getNode(Opcode, Op.getDebugLoc(), ShTy, Op);
1526 }
1527
1528 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1529 /// specified value type.
1530 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1531   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1532   unsigned ByteSize = VT.getStoreSize();
1533   Type *Ty = VT.getTypeForEVT(*getContext());
1534   unsigned StackAlign =
1535   std::max((unsigned)TLI.getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1536
1537   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1538   return getFrameIndex(FrameIdx, TLI.getPointerTy());
1539 }
1540
1541 /// CreateStackTemporary - Create a stack temporary suitable for holding
1542 /// either of the specified value types.
1543 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1544   unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1545                             VT2.getStoreSizeInBits())/8;
1546   Type *Ty1 = VT1.getTypeForEVT(*getContext());
1547   Type *Ty2 = VT2.getTypeForEVT(*getContext());
1548   const DataLayout *TD = TLI.getDataLayout();
1549   unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1550                             TD->getPrefTypeAlignment(Ty2));
1551
1552   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1553   int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1554   return getFrameIndex(FrameIdx, TLI.getPointerTy());
1555 }
1556
1557 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1558                                 SDValue N2, ISD::CondCode Cond, DebugLoc dl) {
1559   // These setcc operations always fold.
1560   switch (Cond) {
1561   default: break;
1562   case ISD::SETFALSE:
1563   case ISD::SETFALSE2: return getConstant(0, VT);
1564   case ISD::SETTRUE:
1565   case ISD::SETTRUE2:  return getConstant(1, VT);
1566
1567   case ISD::SETOEQ:
1568   case ISD::SETOGT:
1569   case ISD::SETOGE:
1570   case ISD::SETOLT:
1571   case ISD::SETOLE:
1572   case ISD::SETONE:
1573   case ISD::SETO:
1574   case ISD::SETUO:
1575   case ISD::SETUEQ:
1576   case ISD::SETUNE:
1577     assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1578     break;
1579   }
1580
1581   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1582     const APInt &C2 = N2C->getAPIntValue();
1583     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1584       const APInt &C1 = N1C->getAPIntValue();
1585
1586       switch (Cond) {
1587       default: llvm_unreachable("Unknown integer setcc!");
1588       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
1589       case ISD::SETNE:  return getConstant(C1 != C2, VT);
1590       case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1591       case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1592       case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1593       case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1594       case ISD::SETLT:  return getConstant(C1.slt(C2), VT);
1595       case ISD::SETGT:  return getConstant(C1.sgt(C2), VT);
1596       case ISD::SETLE:  return getConstant(C1.sle(C2), VT);
1597       case ISD::SETGE:  return getConstant(C1.sge(C2), VT);
1598       }
1599     }
1600   }
1601   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1602     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1603       APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1604       switch (Cond) {
1605       default: break;
1606       case ISD::SETEQ:  if (R==APFloat::cmpUnordered)
1607                           return getUNDEF(VT);
1608                         // fall through
1609       case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1610       case ISD::SETNE:  if (R==APFloat::cmpUnordered)
1611                           return getUNDEF(VT);
1612                         // fall through
1613       case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1614                                            R==APFloat::cmpLessThan, VT);
1615       case ISD::SETLT:  if (R==APFloat::cmpUnordered)
1616                           return getUNDEF(VT);
1617                         // fall through
1618       case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1619       case ISD::SETGT:  if (R==APFloat::cmpUnordered)
1620                           return getUNDEF(VT);
1621                         // fall through
1622       case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1623       case ISD::SETLE:  if (R==APFloat::cmpUnordered)
1624                           return getUNDEF(VT);
1625                         // fall through
1626       case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1627                                            R==APFloat::cmpEqual, VT);
1628       case ISD::SETGE:  if (R==APFloat::cmpUnordered)
1629                           return getUNDEF(VT);
1630                         // fall through
1631       case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1632                                            R==APFloat::cmpEqual, VT);
1633       case ISD::SETO:   return getConstant(R!=APFloat::cmpUnordered, VT);
1634       case ISD::SETUO:  return getConstant(R==APFloat::cmpUnordered, VT);
1635       case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1636                                            R==APFloat::cmpEqual, VT);
1637       case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1638       case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1639                                            R==APFloat::cmpLessThan, VT);
1640       case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1641                                            R==APFloat::cmpUnordered, VT);
1642       case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1643       case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1644       }
1645     } else {
1646       // Ensure that the constant occurs on the RHS.
1647       return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1648     }
1649   }
1650
1651   // Could not fold it.
1652   return SDValue();
1653 }
1654
1655 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1656 /// use this predicate to simplify operations downstream.
1657 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1658   // This predicate is not safe for vector operations.
1659   if (Op.getValueType().isVector())
1660     return false;
1661
1662   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1663   return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1664 }
1665
1666 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
1667 /// this predicate to simplify operations downstream.  Mask is known to be zero
1668 /// for bits that V cannot have.
1669 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1670                                      unsigned Depth) const {
1671   APInt KnownZero, KnownOne;
1672   ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1673   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1674   return (KnownZero & Mask) == Mask;
1675 }
1676
1677 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1678 /// known to be either zero or one and return them in the KnownZero/KnownOne
1679 /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
1680 /// processing.
1681 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1682                                      APInt &KnownOne, unsigned Depth) const {
1683   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1684
1685   KnownZero = KnownOne = APInt(BitWidth, 0);   // Don't know anything.
1686   if (Depth == 6)
1687     return;  // Limit search depth.
1688
1689   APInt KnownZero2, KnownOne2;
1690
1691   switch (Op.getOpcode()) {
1692   case ISD::Constant:
1693     // We know all of the bits for a constant!
1694     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1695     KnownZero = ~KnownOne;
1696     return;
1697   case ISD::AND:
1698     // If either the LHS or the RHS are Zero, the result is zero.
1699     ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1700     ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1701     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1702     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1703
1704     // Output known-1 bits are only known if set in both the LHS & RHS.
1705     KnownOne &= KnownOne2;
1706     // Output known-0 are known to be clear if zero in either the LHS | RHS.
1707     KnownZero |= KnownZero2;
1708     return;
1709   case ISD::OR:
1710     ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1711     ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1712     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1713     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1714
1715     // Output known-0 bits are only known if clear in both the LHS & RHS.
1716     KnownZero &= KnownZero2;
1717     // Output known-1 are known to be set if set in either the LHS | RHS.
1718     KnownOne |= KnownOne2;
1719     return;
1720   case ISD::XOR: {
1721     ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1722     ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1723     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1724     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1725
1726     // Output known-0 bits are known if clear or set in both the LHS & RHS.
1727     APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1728     // Output known-1 are known to be set if set in only one of the LHS, RHS.
1729     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1730     KnownZero = KnownZeroOut;
1731     return;
1732   }
1733   case ISD::MUL: {
1734     ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1735     ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1736     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1737     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1738
1739     // If low bits are zero in either operand, output low known-0 bits.
1740     // Also compute a conserative estimate for high known-0 bits.
1741     // More trickiness is possible, but this is sufficient for the
1742     // interesting case of alignment computation.
1743     KnownOne.clearAllBits();
1744     unsigned TrailZ = KnownZero.countTrailingOnes() +
1745                       KnownZero2.countTrailingOnes();
1746     unsigned LeadZ =  std::max(KnownZero.countLeadingOnes() +
1747                                KnownZero2.countLeadingOnes(),
1748                                BitWidth) - BitWidth;
1749
1750     TrailZ = std::min(TrailZ, BitWidth);
1751     LeadZ = std::min(LeadZ, BitWidth);
1752     KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1753                 APInt::getHighBitsSet(BitWidth, LeadZ);
1754     return;
1755   }
1756   case ISD::UDIV: {
1757     // For the purposes of computing leading zeros we can conservatively
1758     // treat a udiv as a logical right shift by the power of 2 known to
1759     // be less than the denominator.
1760     ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1761     unsigned LeadZ = KnownZero2.countLeadingOnes();
1762
1763     KnownOne2.clearAllBits();
1764     KnownZero2.clearAllBits();
1765     ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1766     unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1767     if (RHSUnknownLeadingOnes != BitWidth)
1768       LeadZ = std::min(BitWidth,
1769                        LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1770
1771     KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1772     return;
1773   }
1774   case ISD::SELECT:
1775     ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1776     ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1777     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1778     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1779
1780     // Only known if known in both the LHS and RHS.
1781     KnownOne &= KnownOne2;
1782     KnownZero &= KnownZero2;
1783     return;
1784   case ISD::SELECT_CC:
1785     ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1786     ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1787     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1788     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1789
1790     // Only known if known in both the LHS and RHS.
1791     KnownOne &= KnownOne2;
1792     KnownZero &= KnownZero2;
1793     return;
1794   case ISD::SADDO:
1795   case ISD::UADDO:
1796   case ISD::SSUBO:
1797   case ISD::USUBO:
1798   case ISD::SMULO:
1799   case ISD::UMULO:
1800     if (Op.getResNo() != 1)
1801       return;
1802     // The boolean result conforms to getBooleanContents.  Fall through.
1803   case ISD::SETCC:
1804     // If we know the result of a setcc has the top bits zero, use this info.
1805     if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
1806         TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1807       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1808     return;
1809   case ISD::SHL:
1810     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
1811     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1812       unsigned ShAmt = SA->getZExtValue();
1813
1814       // If the shift count is an invalid immediate, don't do anything.
1815       if (ShAmt >= BitWidth)
1816         return;
1817
1818       ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1819       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1820       KnownZero <<= ShAmt;
1821       KnownOne  <<= ShAmt;
1822       // low bits known zero.
1823       KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1824     }
1825     return;
1826   case ISD::SRL:
1827     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
1828     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1829       unsigned ShAmt = SA->getZExtValue();
1830
1831       // If the shift count is an invalid immediate, don't do anything.
1832       if (ShAmt >= BitWidth)
1833         return;
1834
1835       ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1836       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1837       KnownZero = KnownZero.lshr(ShAmt);
1838       KnownOne  = KnownOne.lshr(ShAmt);
1839
1840       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1841       KnownZero |= HighBits;  // High bits known zero.
1842     }
1843     return;
1844   case ISD::SRA:
1845     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1846       unsigned ShAmt = SA->getZExtValue();
1847
1848       // If the shift count is an invalid immediate, don't do anything.
1849       if (ShAmt >= BitWidth)
1850         return;
1851
1852       // If any of the demanded bits are produced by the sign extension, we also
1853       // demand the input sign bit.
1854       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1855
1856       ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1857       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1858       KnownZero = KnownZero.lshr(ShAmt);
1859       KnownOne  = KnownOne.lshr(ShAmt);
1860
1861       // Handle the sign bits.
1862       APInt SignBit = APInt::getSignBit(BitWidth);
1863       SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
1864
1865       if (KnownZero.intersects(SignBit)) {
1866         KnownZero |= HighBits;  // New bits are known zero.
1867       } else if (KnownOne.intersects(SignBit)) {
1868         KnownOne  |= HighBits;  // New bits are known one.
1869       }
1870     }
1871     return;
1872   case ISD::SIGN_EXTEND_INREG: {
1873     EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1874     unsigned EBits = EVT.getScalarType().getSizeInBits();
1875
1876     // Sign extension.  Compute the demanded bits in the result that are not
1877     // present in the input.
1878     APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1879
1880     APInt InSignBit = APInt::getSignBit(EBits);
1881     APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1882
1883     // If the sign extended bits are demanded, we know that the sign
1884     // bit is demanded.
1885     InSignBit = InSignBit.zext(BitWidth);
1886     if (NewBits.getBoolValue())
1887       InputDemandedBits |= InSignBit;
1888
1889     ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1890     KnownOne &= InputDemandedBits;
1891     KnownZero &= InputDemandedBits;
1892     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1893
1894     // If the sign bit of the input is known set or clear, then we know the
1895     // top bits of the result.
1896     if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
1897       KnownZero |= NewBits;
1898       KnownOne  &= ~NewBits;
1899     } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
1900       KnownOne  |= NewBits;
1901       KnownZero &= ~NewBits;
1902     } else {                              // Input sign bit unknown
1903       KnownZero &= ~NewBits;
1904       KnownOne  &= ~NewBits;
1905     }
1906     return;
1907   }
1908   case ISD::CTTZ:
1909   case ISD::CTTZ_ZERO_UNDEF:
1910   case ISD::CTLZ:
1911   case ISD::CTLZ_ZERO_UNDEF:
1912   case ISD::CTPOP: {
1913     unsigned LowBits = Log2_32(BitWidth)+1;
1914     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1915     KnownOne.clearAllBits();
1916     return;
1917   }
1918   case ISD::LOAD: {
1919     LoadSDNode *LD = cast<LoadSDNode>(Op);
1920     if (ISD::isZEXTLoad(Op.getNode())) {
1921       EVT VT = LD->getMemoryVT();
1922       unsigned MemBits = VT.getScalarType().getSizeInBits();
1923       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
1924     } else if (const MDNode *Ranges = LD->getRanges()) {
1925       computeMaskedBitsLoad(*Ranges, KnownZero);
1926     }
1927     return;
1928   }
1929   case ISD::ZERO_EXTEND: {
1930     EVT InVT = Op.getOperand(0).getValueType();
1931     unsigned InBits = InVT.getScalarType().getSizeInBits();
1932     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1933     KnownZero = KnownZero.trunc(InBits);
1934     KnownOne = KnownOne.trunc(InBits);
1935     ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1936     KnownZero = KnownZero.zext(BitWidth);
1937     KnownOne = KnownOne.zext(BitWidth);
1938     KnownZero |= NewBits;
1939     return;
1940   }
1941   case ISD::SIGN_EXTEND: {
1942     EVT InVT = Op.getOperand(0).getValueType();
1943     unsigned InBits = InVT.getScalarType().getSizeInBits();
1944     APInt InSignBit = APInt::getSignBit(InBits);
1945     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1946
1947     KnownZero = KnownZero.trunc(InBits);
1948     KnownOne = KnownOne.trunc(InBits);
1949     ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1950
1951     // Note if the sign bit is known to be zero or one.
1952     bool SignBitKnownZero = KnownZero.isNegative();
1953     bool SignBitKnownOne  = KnownOne.isNegative();
1954     assert(!(SignBitKnownZero && SignBitKnownOne) &&
1955            "Sign bit can't be known to be both zero and one!");
1956
1957     KnownZero = KnownZero.zext(BitWidth);
1958     KnownOne = KnownOne.zext(BitWidth);
1959
1960     // If the sign bit is known zero or one, the top bits match.
1961     if (SignBitKnownZero)
1962       KnownZero |= NewBits;
1963     else if (SignBitKnownOne)
1964       KnownOne  |= NewBits;
1965     return;
1966   }
1967   case ISD::ANY_EXTEND: {
1968     EVT InVT = Op.getOperand(0).getValueType();
1969     unsigned InBits = InVT.getScalarType().getSizeInBits();
1970     KnownZero = KnownZero.trunc(InBits);
1971     KnownOne = KnownOne.trunc(InBits);
1972     ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1973     KnownZero = KnownZero.zext(BitWidth);
1974     KnownOne = KnownOne.zext(BitWidth);
1975     return;
1976   }
1977   case ISD::TRUNCATE: {
1978     EVT InVT = Op.getOperand(0).getValueType();
1979     unsigned InBits = InVT.getScalarType().getSizeInBits();
1980     KnownZero = KnownZero.zext(InBits);
1981     KnownOne = KnownOne.zext(InBits);
1982     ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1983     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1984     KnownZero = KnownZero.trunc(BitWidth);
1985     KnownOne = KnownOne.trunc(BitWidth);
1986     break;
1987   }
1988   case ISD::AssertZext: {
1989     EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1990     APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
1991     ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1992     KnownZero |= (~InMask);
1993     KnownOne  &= (~KnownZero);
1994     return;
1995   }
1996   case ISD::FGETSIGN:
1997     // All bits are zero except the low bit.
1998     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1999     return;
2000
2001   case ISD::SUB: {
2002     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2003       // We know that the top bits of C-X are clear if X contains less bits
2004       // than C (i.e. no wrap-around can happen).  For example, 20-X is
2005       // positive if we can prove that X is >= 0 and < 16.
2006       if (CLHS->getAPIntValue().isNonNegative()) {
2007         unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2008         // NLZ can't be BitWidth with no sign bit
2009         APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2010         ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2011
2012         // If all of the MaskV bits are known to be zero, then we know the
2013         // output top bits are zero, because we now know that the output is
2014         // from [0-C].
2015         if ((KnownZero2 & MaskV) == MaskV) {
2016           unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2017           // Top bits known zero.
2018           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2019         }
2020       }
2021     }
2022   }
2023   // fall through
2024   case ISD::ADD:
2025   case ISD::ADDE: {
2026     // Output known-0 bits are known if clear or set in both the low clear bits
2027     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
2028     // low 3 bits clear.
2029     ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2030     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2031     unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2032
2033     ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2034     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2035     KnownZeroOut = std::min(KnownZeroOut,
2036                             KnownZero2.countTrailingOnes());
2037
2038     if (Op.getOpcode() == ISD::ADD) {
2039       KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2040       return;
2041     }
2042
2043     // With ADDE, a carry bit may be added in, so we can only use this
2044     // information if we know (at least) that the low two bits are clear.  We
2045     // then return to the caller that the low bit is unknown but that other bits
2046     // are known zero.
2047     if (KnownZeroOut >= 2) // ADDE
2048       KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2049     return;
2050   }
2051   case ISD::SREM:
2052     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2053       const APInt &RA = Rem->getAPIntValue().abs();
2054       if (RA.isPowerOf2()) {
2055         APInt LowBits = RA - 1;
2056         APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2057         ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2058
2059         // The low bits of the first operand are unchanged by the srem.
2060         KnownZero = KnownZero2 & LowBits;
2061         KnownOne = KnownOne2 & LowBits;
2062
2063         // If the first operand is non-negative or has all low bits zero, then
2064         // the upper bits are all zero.
2065         if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2066           KnownZero |= ~LowBits;
2067
2068         // If the first operand is negative and not all low bits are zero, then
2069         // the upper bits are all one.
2070         if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2071           KnownOne |= ~LowBits;
2072         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2073       }
2074     }
2075     return;
2076   case ISD::UREM: {
2077     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2078       const APInt &RA = Rem->getAPIntValue();
2079       if (RA.isPowerOf2()) {
2080         APInt LowBits = (RA - 1);
2081         KnownZero |= ~LowBits;
2082         ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2083         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2084         break;
2085       }
2086     }
2087
2088     // Since the result is less than or equal to either operand, any leading
2089     // zero bits in either operand must also exist in the result.
2090     ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2091     ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2092
2093     uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2094                                 KnownZero2.countLeadingOnes());
2095     KnownOne.clearAllBits();
2096     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2097     return;
2098   }
2099   case ISD::FrameIndex:
2100   case ISD::TargetFrameIndex:
2101     if (unsigned Align = InferPtrAlignment(Op)) {
2102       // The low bits are known zero if the pointer is aligned.
2103       KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2104       return;
2105     }
2106     break;
2107
2108   default:
2109     if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2110       break;
2111     // Fallthrough
2112   case ISD::INTRINSIC_WO_CHAIN:
2113   case ISD::INTRINSIC_W_CHAIN:
2114   case ISD::INTRINSIC_VOID:
2115     // Allow the target to implement this method for its nodes.
2116     TLI.computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2117     return;
2118   }
2119 }
2120
2121 /// ComputeNumSignBits - Return the number of times the sign bit of the
2122 /// register is replicated into the other bits.  We know that at least 1 bit
2123 /// is always equal to the sign bit (itself), but other cases can give us
2124 /// information.  For example, immediately after an "SRA X, 2", we know that
2125 /// the top 3 bits are all equal to each other, so we return 3.
2126 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2127   EVT VT = Op.getValueType();
2128   assert(VT.isInteger() && "Invalid VT!");
2129   unsigned VTBits = VT.getScalarType().getSizeInBits();
2130   unsigned Tmp, Tmp2;
2131   unsigned FirstAnswer = 1;
2132
2133   if (Depth == 6)
2134     return 1;  // Limit search depth.
2135
2136   switch (Op.getOpcode()) {
2137   default: break;
2138   case ISD::AssertSext:
2139     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2140     return VTBits-Tmp+1;
2141   case ISD::AssertZext:
2142     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2143     return VTBits-Tmp;
2144
2145   case ISD::Constant: {
2146     const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2147     return Val.getNumSignBits();
2148   }
2149
2150   case ISD::SIGN_EXTEND:
2151     Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2152     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2153
2154   case ISD::SIGN_EXTEND_INREG:
2155     // Max of the input and what this extends.
2156     Tmp =
2157       cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2158     Tmp = VTBits-Tmp+1;
2159
2160     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2161     return std::max(Tmp, Tmp2);
2162
2163   case ISD::SRA:
2164     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2165     // SRA X, C   -> adds C sign bits.
2166     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2167       Tmp += C->getZExtValue();
2168       if (Tmp > VTBits) Tmp = VTBits;
2169     }
2170     return Tmp;
2171   case ISD::SHL:
2172     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2173       // shl destroys sign bits.
2174       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2175       if (C->getZExtValue() >= VTBits ||      // Bad shift.
2176           C->getZExtValue() >= Tmp) break;    // Shifted all sign bits out.
2177       return Tmp - C->getZExtValue();
2178     }
2179     break;
2180   case ISD::AND:
2181   case ISD::OR:
2182   case ISD::XOR:    // NOT is handled here.
2183     // Logical binary ops preserve the number of sign bits at the worst.
2184     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2185     if (Tmp != 1) {
2186       Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2187       FirstAnswer = std::min(Tmp, Tmp2);
2188       // We computed what we know about the sign bits as our first
2189       // answer. Now proceed to the generic code that uses
2190       // ComputeMaskedBits, and pick whichever answer is better.
2191     }
2192     break;
2193
2194   case ISD::SELECT:
2195     Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2196     if (Tmp == 1) return 1;  // Early out.
2197     Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2198     return std::min(Tmp, Tmp2);
2199
2200   case ISD::SADDO:
2201   case ISD::UADDO:
2202   case ISD::SSUBO:
2203   case ISD::USUBO:
2204   case ISD::SMULO:
2205   case ISD::UMULO:
2206     if (Op.getResNo() != 1)
2207       break;
2208     // The boolean result conforms to getBooleanContents.  Fall through.
2209   case ISD::SETCC:
2210     // If setcc returns 0/-1, all bits are sign bits.
2211     if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2212         TargetLowering::ZeroOrNegativeOneBooleanContent)
2213       return VTBits;
2214     break;
2215   case ISD::ROTL:
2216   case ISD::ROTR:
2217     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2218       unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2219
2220       // Handle rotate right by N like a rotate left by 32-N.
2221       if (Op.getOpcode() == ISD::ROTR)
2222         RotAmt = (VTBits-RotAmt) & (VTBits-1);
2223
2224       // If we aren't rotating out all of the known-in sign bits, return the
2225       // number that are left.  This handles rotl(sext(x), 1) for example.
2226       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2227       if (Tmp > RotAmt+1) return Tmp-RotAmt;
2228     }
2229     break;
2230   case ISD::ADD:
2231     // Add can have at most one carry bit.  Thus we know that the output
2232     // is, at worst, one more bit than the inputs.
2233     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2234     if (Tmp == 1) return 1;  // Early out.
2235
2236     // Special case decrementing a value (ADD X, -1):
2237     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2238       if (CRHS->isAllOnesValue()) {
2239         APInt KnownZero, KnownOne;
2240         ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2241
2242         // If the input is known to be 0 or 1, the output is 0/-1, which is all
2243         // sign bits set.
2244         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2245           return VTBits;
2246
2247         // If we are subtracting one from a positive number, there is no carry
2248         // out of the result.
2249         if (KnownZero.isNegative())
2250           return Tmp;
2251       }
2252
2253     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2254     if (Tmp2 == 1) return 1;
2255     return std::min(Tmp, Tmp2)-1;
2256
2257   case ISD::SUB:
2258     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2259     if (Tmp2 == 1) return 1;
2260
2261     // Handle NEG.
2262     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2263       if (CLHS->isNullValue()) {
2264         APInt KnownZero, KnownOne;
2265         ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2266         // If the input is known to be 0 or 1, the output is 0/-1, which is all
2267         // sign bits set.
2268         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2269           return VTBits;
2270
2271         // If the input is known to be positive (the sign bit is known clear),
2272         // the output of the NEG has the same number of sign bits as the input.
2273         if (KnownZero.isNegative())
2274           return Tmp2;
2275
2276         // Otherwise, we treat this like a SUB.
2277       }
2278
2279     // Sub can have at most one carry bit.  Thus we know that the output
2280     // is, at worst, one more bit than the inputs.
2281     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2282     if (Tmp == 1) return 1;  // Early out.
2283     return std::min(Tmp, Tmp2)-1;
2284   case ISD::TRUNCATE:
2285     // FIXME: it's tricky to do anything useful for this, but it is an important
2286     // case for targets like X86.
2287     break;
2288   }
2289
2290   // Handle LOADX separately here. EXTLOAD case will fallthrough.
2291   if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2292     unsigned ExtType = LD->getExtensionType();
2293     switch (ExtType) {
2294     default: break;
2295     case ISD::SEXTLOAD:    // '17' bits known
2296       Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2297       return VTBits-Tmp+1;
2298     case ISD::ZEXTLOAD:    // '16' bits known
2299       Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2300       return VTBits-Tmp;
2301     }
2302   }
2303
2304   // Allow the target to implement this method for its nodes.
2305   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2306       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2307       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2308       Op.getOpcode() == ISD::INTRINSIC_VOID) {
2309     unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2310     if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2311   }
2312
2313   // Finally, if we can prove that the top bits of the result are 0's or 1's,
2314   // use this information.
2315   APInt KnownZero, KnownOne;
2316   ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2317
2318   APInt Mask;
2319   if (KnownZero.isNegative()) {        // sign bit is 0
2320     Mask = KnownZero;
2321   } else if (KnownOne.isNegative()) {  // sign bit is 1;
2322     Mask = KnownOne;
2323   } else {
2324     // Nothing known.
2325     return FirstAnswer;
2326   }
2327
2328   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
2329   // the number of identical bits in the top of the input value.
2330   Mask = ~Mask;
2331   Mask <<= Mask.getBitWidth()-VTBits;
2332   // Return # leading zeros.  We use 'min' here in case Val was zero before
2333   // shifting.  We don't want to return '64' as for an i32 "0".
2334   return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2335 }
2336
2337 /// isBaseWithConstantOffset - Return true if the specified operand is an
2338 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2339 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2340 /// semantics as an ADD.  This handles the equivalence:
2341 ///     X|Cst == X+Cst iff X&Cst = 0.
2342 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2343   if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2344       !isa<ConstantSDNode>(Op.getOperand(1)))
2345     return false;
2346
2347   if (Op.getOpcode() == ISD::OR &&
2348       !MaskedValueIsZero(Op.getOperand(0),
2349                      cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2350     return false;
2351
2352   return true;
2353 }
2354
2355
2356 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2357   // If we're told that NaNs won't happen, assume they won't.
2358   if (getTarget().Options.NoNaNsFPMath)
2359     return true;
2360
2361   // If the value is a constant, we can obviously see if it is a NaN or not.
2362   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2363     return !C->getValueAPF().isNaN();
2364
2365   // TODO: Recognize more cases here.
2366
2367   return false;
2368 }
2369
2370 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2371   // If the value is a constant, we can obviously see if it is a zero or not.
2372   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2373     return !C->isZero();
2374
2375   // TODO: Recognize more cases here.
2376   switch (Op.getOpcode()) {
2377   default: break;
2378   case ISD::OR:
2379     if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2380       return !C->isNullValue();
2381     break;
2382   }
2383
2384   return false;
2385 }
2386
2387 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2388   // Check the obvious case.
2389   if (A == B) return true;
2390
2391   // For for negative and positive zero.
2392   if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2393     if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2394       if (CA->isZero() && CB->isZero()) return true;
2395
2396   // Otherwise they may not be equal.
2397   return false;
2398 }
2399
2400 /// getNode - Gets or creates the specified node.
2401 ///
2402 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2403   FoldingSetNodeID ID;
2404   AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2405   void *IP = 0;
2406   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2407     return SDValue(E, 0);
2408
2409   SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2410   CSEMap.InsertNode(N, IP);
2411
2412   AllNodes.push_back(N);
2413 #ifndef NDEBUG
2414   VerifySDNode(N);
2415 #endif
2416   return SDValue(N, 0);
2417 }
2418
2419 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2420                               EVT VT, SDValue Operand) {
2421   // Constant fold unary operations with an integer constant operand.
2422   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2423     const APInt &Val = C->getAPIntValue();
2424     switch (Opcode) {
2425     default: break;
2426     case ISD::SIGN_EXTEND:
2427       return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2428     case ISD::ANY_EXTEND:
2429     case ISD::ZERO_EXTEND:
2430     case ISD::TRUNCATE:
2431       return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2432     case ISD::UINT_TO_FP:
2433     case ISD::SINT_TO_FP: {
2434       APFloat apf(EVTToAPFloatSemantics(VT),
2435                   APInt::getNullValue(VT.getSizeInBits()));
2436       (void)apf.convertFromAPInt(Val,
2437                                  Opcode==ISD::SINT_TO_FP,
2438                                  APFloat::rmNearestTiesToEven);
2439       return getConstantFP(apf, VT);
2440     }
2441     case ISD::BITCAST:
2442       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2443         return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2444       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2445         return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2446       break;
2447     case ISD::BSWAP:
2448       return getConstant(Val.byteSwap(), VT);
2449     case ISD::CTPOP:
2450       return getConstant(Val.countPopulation(), VT);
2451     case ISD::CTLZ:
2452     case ISD::CTLZ_ZERO_UNDEF:
2453       return getConstant(Val.countLeadingZeros(), VT);
2454     case ISD::CTTZ:
2455     case ISD::CTTZ_ZERO_UNDEF:
2456       return getConstant(Val.countTrailingZeros(), VT);
2457     }
2458   }
2459
2460   // Constant fold unary operations with a floating point constant operand.
2461   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2462     APFloat V = C->getValueAPF();    // make copy
2463     switch (Opcode) {
2464     case ISD::FNEG:
2465       V.changeSign();
2466       return getConstantFP(V, VT);
2467     case ISD::FABS:
2468       V.clearSign();
2469       return getConstantFP(V, VT);
2470     case ISD::FCEIL: {
2471       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2472       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2473         return getConstantFP(V, VT);
2474       break;
2475     }
2476     case ISD::FTRUNC: {
2477       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2478       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2479         return getConstantFP(V, VT);
2480       break;
2481     }
2482     case ISD::FFLOOR: {
2483       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2484       if (fs == APFloat::opOK || fs == APFloat::opInexact)
2485         return getConstantFP(V, VT);
2486       break;
2487     }
2488     case ISD::FP_EXTEND: {
2489       bool ignored;
2490       // This can return overflow, underflow, or inexact; we don't care.
2491       // FIXME need to be more flexible about rounding mode.
2492       (void)V.convert(EVTToAPFloatSemantics(VT),
2493                       APFloat::rmNearestTiesToEven, &ignored);
2494       return getConstantFP(V, VT);
2495     }
2496     case ISD::FP_TO_SINT:
2497     case ISD::FP_TO_UINT: {
2498       integerPart x[2];
2499       bool ignored;
2500       assert(integerPartWidth >= 64);
2501       // FIXME need to be more flexible about rounding mode.
2502       APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2503                             Opcode==ISD::FP_TO_SINT,
2504                             APFloat::rmTowardZero, &ignored);
2505       if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
2506         break;
2507       APInt api(VT.getSizeInBits(), x);
2508       return getConstant(api, VT);
2509     }
2510     case ISD::BITCAST:
2511       if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2512         return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2513       else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2514         return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2515       break;
2516     }
2517   }
2518
2519   unsigned OpOpcode = Operand.getNode()->getOpcode();
2520   switch (Opcode) {
2521   case ISD::TokenFactor:
2522   case ISD::MERGE_VALUES:
2523   case ISD::CONCAT_VECTORS:
2524     return Operand;         // Factor, merge or concat of one node?  No need.
2525   case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2526   case ISD::FP_EXTEND:
2527     assert(VT.isFloatingPoint() &&
2528            Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2529     if (Operand.getValueType() == VT) return Operand;  // noop conversion.
2530     assert((!VT.isVector() ||
2531             VT.getVectorNumElements() ==
2532             Operand.getValueType().getVectorNumElements()) &&
2533            "Vector element count mismatch!");
2534     if (Operand.getOpcode() == ISD::UNDEF)
2535       return getUNDEF(VT);
2536     break;
2537   case ISD::SIGN_EXTEND:
2538     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2539            "Invalid SIGN_EXTEND!");
2540     if (Operand.getValueType() == VT) return Operand;   // noop extension
2541     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2542            "Invalid sext node, dst < src!");
2543     assert((!VT.isVector() ||
2544             VT.getVectorNumElements() ==
2545             Operand.getValueType().getVectorNumElements()) &&
2546            "Vector element count mismatch!");
2547     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2548       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2549     else if (OpOpcode == ISD::UNDEF)
2550       // sext(undef) = 0, because the top bits will all be the same.
2551       return getConstant(0, VT);
2552     break;
2553   case ISD::ZERO_EXTEND:
2554     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2555            "Invalid ZERO_EXTEND!");
2556     if (Operand.getValueType() == VT) return Operand;   // noop extension
2557     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2558            "Invalid zext node, dst < src!");
2559     assert((!VT.isVector() ||
2560             VT.getVectorNumElements() ==
2561             Operand.getValueType().getVectorNumElements()) &&
2562            "Vector element count mismatch!");
2563     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
2564       return getNode(ISD::ZERO_EXTEND, DL, VT,
2565                      Operand.getNode()->getOperand(0));
2566     else if (OpOpcode == ISD::UNDEF)
2567       // zext(undef) = 0, because the top bits will be zero.
2568       return getConstant(0, VT);
2569     break;
2570   case ISD::ANY_EXTEND:
2571     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2572            "Invalid ANY_EXTEND!");
2573     if (Operand.getValueType() == VT) return Operand;   // noop extension
2574     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2575            "Invalid anyext node, dst < src!");
2576     assert((!VT.isVector() ||
2577             VT.getVectorNumElements() ==
2578             Operand.getValueType().getVectorNumElements()) &&
2579            "Vector element count mismatch!");
2580
2581     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2582         OpOpcode == ISD::ANY_EXTEND)
2583       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
2584       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2585     else if (OpOpcode == ISD::UNDEF)
2586       return getUNDEF(VT);
2587
2588     // (ext (trunx x)) -> x
2589     if (OpOpcode == ISD::TRUNCATE) {
2590       SDValue OpOp = Operand.getNode()->getOperand(0);
2591       if (OpOp.getValueType() == VT)
2592         return OpOp;
2593     }
2594     break;
2595   case ISD::TRUNCATE:
2596     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2597            "Invalid TRUNCATE!");
2598     if (Operand.getValueType() == VT) return Operand;   // noop truncate
2599     assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2600            "Invalid truncate node, src < dst!");
2601     assert((!VT.isVector() ||
2602             VT.getVectorNumElements() ==
2603             Operand.getValueType().getVectorNumElements()) &&
2604            "Vector element count mismatch!");
2605     if (OpOpcode == ISD::TRUNCATE)
2606       return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2607     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2608         OpOpcode == ISD::ANY_EXTEND) {
2609       // If the source is smaller than the dest, we still need an extend.
2610       if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2611             .bitsLT(VT.getScalarType()))
2612         return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2613       if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2614         return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2615       return Operand.getNode()->getOperand(0);
2616     }
2617     if (OpOpcode == ISD::UNDEF)
2618       return getUNDEF(VT);
2619     break;
2620   case ISD::BITCAST:
2621     // Basic sanity checking.
2622     assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2623            && "Cannot BITCAST between types of different sizes!");
2624     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
2625     if (OpOpcode == ISD::BITCAST)  // bitconv(bitconv(x)) -> bitconv(x)
2626       return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2627     if (OpOpcode == ISD::UNDEF)
2628       return getUNDEF(VT);
2629     break;
2630   case ISD::SCALAR_TO_VECTOR:
2631     assert(VT.isVector() && !Operand.getValueType().isVector() &&
2632            (VT.getVectorElementType() == Operand.getValueType() ||
2633             (VT.getVectorElementType().isInteger() &&
2634              Operand.getValueType().isInteger() &&
2635              VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2636            "Illegal SCALAR_TO_VECTOR node!");
2637     if (OpOpcode == ISD::UNDEF)
2638       return getUNDEF(VT);
2639     // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2640     if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2641         isa<ConstantSDNode>(Operand.getOperand(1)) &&
2642         Operand.getConstantOperandVal(1) == 0 &&
2643         Operand.getOperand(0).getValueType() == VT)
2644       return Operand.getOperand(0);
2645     break;
2646   case ISD::FNEG:
2647     // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2648     if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2649       return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2650                      Operand.getNode()->getOperand(0));
2651     if (OpOpcode == ISD::FNEG)  // --X -> X
2652       return Operand.getNode()->getOperand(0);
2653     break;
2654   case ISD::FABS:
2655     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
2656       return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2657     break;
2658   }
2659
2660   SDNode *N;
2661   SDVTList VTs = getVTList(VT);
2662   if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2663     FoldingSetNodeID ID;
2664     SDValue Ops[1] = { Operand };
2665     AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2666     void *IP = 0;
2667     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2668       return SDValue(E, 0);
2669
2670     N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2671     CSEMap.InsertNode(N, IP);
2672   } else {
2673     N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2674   }
2675
2676   AllNodes.push_back(N);
2677 #ifndef NDEBUG
2678   VerifySDNode(N);
2679 #endif
2680   return SDValue(N, 0);
2681 }
2682
2683 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2684                                              EVT VT,
2685                                              ConstantSDNode *Cst1,
2686                                              ConstantSDNode *Cst2) {
2687   const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2688
2689   switch (Opcode) {
2690   case ISD::ADD:  return getConstant(C1 + C2, VT);
2691   case ISD::SUB:  return getConstant(C1 - C2, VT);
2692   case ISD::MUL:  return getConstant(C1 * C2, VT);
2693   case ISD::UDIV:
2694     if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2695     break;
2696   case ISD::UREM:
2697     if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2698     break;
2699   case ISD::SDIV:
2700     if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2701     break;
2702   case ISD::SREM:
2703     if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2704     break;
2705   case ISD::AND:  return getConstant(C1 & C2, VT);
2706   case ISD::OR:   return getConstant(C1 | C2, VT);
2707   case ISD::XOR:  return getConstant(C1 ^ C2, VT);
2708   case ISD::SHL:  return getConstant(C1 << C2, VT);
2709   case ISD::SRL:  return getConstant(C1.lshr(C2), VT);
2710   case ISD::SRA:  return getConstant(C1.ashr(C2), VT);
2711   case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2712   case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2713   default: break;
2714   }
2715
2716   return SDValue();
2717 }
2718
2719 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2720                               SDValue N1, SDValue N2) {
2721   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2722   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2723   switch (Opcode) {
2724   default: break;
2725   case ISD::TokenFactor:
2726     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2727            N2.getValueType() == MVT::Other && "Invalid token factor!");
2728     // Fold trivial token factors.
2729     if (N1.getOpcode() == ISD::EntryToken) return N2;
2730     if (N2.getOpcode() == ISD::EntryToken) return N1;
2731     if (N1 == N2) return N1;
2732     break;
2733   case ISD::CONCAT_VECTORS:
2734     // Concat of UNDEFs is UNDEF.
2735     if (N1.getOpcode() == ISD::UNDEF &&
2736         N2.getOpcode() == ISD::UNDEF)
2737       return getUNDEF(VT);
2738
2739     // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2740     // one big BUILD_VECTOR.
2741     if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2742         N2.getOpcode() == ISD::BUILD_VECTOR) {
2743       SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2744                                     N1.getNode()->op_end());
2745       Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2746       return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2747     }
2748     break;
2749   case ISD::AND:
2750     assert(VT.isInteger() && "This operator does not apply to FP types!");
2751     assert(N1.getValueType() == N2.getValueType() &&
2752            N1.getValueType() == VT && "Binary operator types must match!");
2753     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
2754     // worth handling here.
2755     if (N2C && N2C->isNullValue())
2756       return N2;
2757     if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
2758       return N1;
2759     break;
2760   case ISD::OR:
2761   case ISD::XOR:
2762   case ISD::ADD:
2763   case ISD::SUB:
2764     assert(VT.isInteger() && "This operator does not apply to FP types!");
2765     assert(N1.getValueType() == N2.getValueType() &&
2766            N1.getValueType() == VT && "Binary operator types must match!");
2767     // (X ^|+- 0) -> X.  This commonly occurs when legalizing i64 values, so
2768     // it's worth handling here.
2769     if (N2C && N2C->isNullValue())
2770       return N1;
2771     break;
2772   case ISD::UDIV:
2773   case ISD::UREM:
2774   case ISD::MULHU:
2775   case ISD::MULHS:
2776   case ISD::MUL:
2777   case ISD::SDIV:
2778   case ISD::SREM:
2779     assert(VT.isInteger() && "This operator does not apply to FP types!");
2780     assert(N1.getValueType() == N2.getValueType() &&
2781            N1.getValueType() == VT && "Binary operator types must match!");
2782     break;
2783   case ISD::FADD:
2784   case ISD::FSUB:
2785   case ISD::FMUL:
2786   case ISD::FDIV:
2787   case ISD::FREM:
2788     if (getTarget().Options.UnsafeFPMath) {
2789       if (Opcode == ISD::FADD) {
2790         // 0+x --> x
2791         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2792           if (CFP->getValueAPF().isZero())
2793             return N2;
2794         // x+0 --> x
2795         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2796           if (CFP->getValueAPF().isZero())
2797             return N1;
2798       } else if (Opcode == ISD::FSUB) {
2799         // x-0 --> x
2800         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2801           if (CFP->getValueAPF().isZero())
2802             return N1;
2803       } else if (Opcode == ISD::FMUL) {
2804         ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2805         SDValue V = N2;
2806
2807         // If the first operand isn't the constant, try the second
2808         if (!CFP) {
2809           CFP = dyn_cast<ConstantFPSDNode>(N2);
2810           V = N1;
2811         }
2812
2813         if (CFP) {
2814           // 0*x --> 0
2815           if (CFP->isZero())
2816             return SDValue(CFP,0);
2817           // 1*x --> x
2818           if (CFP->isExactlyValue(1.0))
2819             return V;
2820         }
2821       }
2822     }
2823     assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2824     assert(N1.getValueType() == N2.getValueType() &&
2825            N1.getValueType() == VT && "Binary operator types must match!");
2826     break;
2827   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
2828     assert(N1.getValueType() == VT &&
2829            N1.getValueType().isFloatingPoint() &&
2830            N2.getValueType().isFloatingPoint() &&
2831            "Invalid FCOPYSIGN!");
2832     break;
2833   case ISD::SHL:
2834   case ISD::SRA:
2835   case ISD::SRL:
2836   case ISD::ROTL:
2837   case ISD::ROTR:
2838     assert(VT == N1.getValueType() &&
2839            "Shift operators return type must be the same as their first arg");
2840     assert(VT.isInteger() && N2.getValueType().isInteger() &&
2841            "Shifts only work on integers");
2842     // Verify that the shift amount VT is bit enough to hold valid shift
2843     // amounts.  This catches things like trying to shift an i1024 value by an
2844     // i8, which is easy to fall into in generic code that uses
2845     // TLI.getShiftAmount().
2846     assert(N2.getValueType().getSizeInBits() >=
2847                    Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2848            "Invalid use of small shift amount with oversized value!");
2849
2850     // Always fold shifts of i1 values so the code generator doesn't need to
2851     // handle them.  Since we know the size of the shift has to be less than the
2852     // size of the value, the shift/rotate count is guaranteed to be zero.
2853     if (VT == MVT::i1)
2854       return N1;
2855     if (N2C && N2C->isNullValue())
2856       return N1;
2857     break;
2858   case ISD::FP_ROUND_INREG: {
2859     EVT EVT = cast<VTSDNode>(N2)->getVT();
2860     assert(VT == N1.getValueType() && "Not an inreg round!");
2861     assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2862            "Cannot FP_ROUND_INREG integer types");
2863     assert(EVT.isVector() == VT.isVector() &&
2864            "FP_ROUND_INREG type should be vector iff the operand "
2865            "type is vector!");
2866     assert((!EVT.isVector() ||
2867             EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2868            "Vector element counts must match in FP_ROUND_INREG");
2869     assert(EVT.bitsLE(VT) && "Not rounding down!");
2870     (void)EVT;
2871     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
2872     break;
2873   }
2874   case ISD::FP_ROUND:
2875     assert(VT.isFloatingPoint() &&
2876            N1.getValueType().isFloatingPoint() &&
2877            VT.bitsLE(N1.getValueType()) &&
2878            isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2879     if (N1.getValueType() == VT) return N1;  // noop conversion.
2880     break;
2881   case ISD::AssertSext:
2882   case ISD::AssertZext: {
2883     EVT EVT = cast<VTSDNode>(N2)->getVT();
2884     assert(VT == N1.getValueType() && "Not an inreg extend!");
2885     assert(VT.isInteger() && EVT.isInteger() &&
2886            "Cannot *_EXTEND_INREG FP types");
2887     assert(!EVT.isVector() &&
2888            "AssertSExt/AssertZExt type should be the vector element type "
2889            "rather than the vector type!");
2890     assert(EVT.bitsLE(VT) && "Not extending!");
2891     if (VT == EVT) return N1; // noop assertion.
2892     break;
2893   }
2894   case ISD::SIGN_EXTEND_INREG: {
2895     EVT EVT = cast<VTSDNode>(N2)->getVT();
2896     assert(VT == N1.getValueType() && "Not an inreg extend!");
2897     assert(VT.isInteger() && EVT.isInteger() &&
2898            "Cannot *_EXTEND_INREG FP types");
2899     assert(EVT.isVector() == VT.isVector() &&
2900            "SIGN_EXTEND_INREG type should be vector iff the operand "
2901            "type is vector!");
2902     assert((!EVT.isVector() ||
2903             EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2904            "Vector element counts must match in SIGN_EXTEND_INREG");
2905     assert(EVT.bitsLE(VT) && "Not extending!");
2906     if (EVT == VT) return N1;  // Not actually extending
2907
2908     if (N1C) {
2909       APInt Val = N1C->getAPIntValue();
2910       unsigned FromBits = EVT.getScalarType().getSizeInBits();
2911       Val <<= Val.getBitWidth()-FromBits;
2912       Val = Val.ashr(Val.getBitWidth()-FromBits);
2913       return getConstant(Val, VT);
2914     }
2915     break;
2916   }
2917   case ISD::EXTRACT_VECTOR_ELT:
2918     // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2919     if (N1.getOpcode() == ISD::UNDEF)
2920       return getUNDEF(VT);
2921
2922     // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2923     // expanding copies of large vectors from registers.
2924     if (N2C &&
2925         N1.getOpcode() == ISD::CONCAT_VECTORS &&
2926         N1.getNumOperands() > 0) {
2927       unsigned Factor =
2928         N1.getOperand(0).getValueType().getVectorNumElements();
2929       return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2930                      N1.getOperand(N2C->getZExtValue() / Factor),
2931                      getConstant(N2C->getZExtValue() % Factor,
2932                                  N2.getValueType()));
2933     }
2934
2935     // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2936     // expanding large vector constants.
2937     if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2938       SDValue Elt = N1.getOperand(N2C->getZExtValue());
2939
2940       if (VT != Elt.getValueType())
2941         // If the vector element type is not legal, the BUILD_VECTOR operands
2942         // are promoted and implicitly truncated, and the result implicitly
2943         // extended. Make that explicit here.
2944         Elt = getAnyExtOrTrunc(Elt, DL, VT);
2945
2946       return Elt;
2947     }
2948
2949     // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2950     // operations are lowered to scalars.
2951     if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2952       // If the indices are the same, return the inserted element else
2953       // if the indices are known different, extract the element from
2954       // the original vector.
2955       SDValue N1Op2 = N1.getOperand(2);
2956       ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2957
2958       if (N1Op2C && N2C) {
2959         if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2960           if (VT == N1.getOperand(1).getValueType())
2961             return N1.getOperand(1);
2962           else
2963             return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2964         }
2965
2966         return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2967       }
2968     }
2969     break;
2970   case ISD::EXTRACT_ELEMENT:
2971     assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2972     assert(!N1.getValueType().isVector() && !VT.isVector() &&
2973            (N1.getValueType().isInteger() == VT.isInteger()) &&
2974            N1.getValueType() != VT &&
2975            "Wrong types for EXTRACT_ELEMENT!");
2976
2977     // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2978     // 64-bit integers into 32-bit parts.  Instead of building the extract of
2979     // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2980     if (N1.getOpcode() == ISD::BUILD_PAIR)
2981       return N1.getOperand(N2C->getZExtValue());
2982
2983     // EXTRACT_ELEMENT of a constant int is also very common.
2984     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2985       unsigned ElementSize = VT.getSizeInBits();
2986       unsigned Shift = ElementSize * N2C->getZExtValue();
2987       APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2988       return getConstant(ShiftedVal.trunc(ElementSize), VT);
2989     }
2990     break;
2991   case ISD::EXTRACT_SUBVECTOR: {
2992     SDValue Index = N2;
2993     if (VT.isSimple() && N1.getValueType().isSimple()) {
2994       assert(VT.isVector() && N1.getValueType().isVector() &&
2995              "Extract subvector VTs must be a vectors!");
2996       assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
2997              "Extract subvector VTs must have the same element type!");
2998       assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
2999              "Extract subvector must be from larger vector to smaller vector!");
3000
3001       if (isa<ConstantSDNode>(Index.getNode())) {
3002         assert((VT.getVectorNumElements() +
3003                 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3004                 <= N1.getValueType().getVectorNumElements())
3005                && "Extract subvector overflow!");
3006       }
3007
3008       // Trivial extraction.
3009       if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
3010         return N1;
3011     }
3012     break;
3013   }
3014   }
3015
3016   if (N1C) {
3017     if (N2C) {
3018       SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
3019       if (SV.getNode()) return SV;
3020     } else {      // Cannonicalize constant to RHS if commutative
3021       if (isCommutativeBinOp(Opcode)) {
3022         std::swap(N1C, N2C);
3023         std::swap(N1, N2);
3024       }
3025     }
3026   }
3027
3028   // Constant fold FP operations.
3029   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3030   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3031   if (N1CFP) {
3032     if (!N2CFP && isCommutativeBinOp(Opcode)) {
3033       // Cannonicalize constant to RHS if commutative
3034       std::swap(N1CFP, N2CFP);
3035       std::swap(N1, N2);
3036     } else if (N2CFP) {
3037       APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3038       APFloat::opStatus s;
3039       switch (Opcode) {
3040       case ISD::FADD:
3041         s = V1.add(V2, APFloat::rmNearestTiesToEven);
3042         if (s != APFloat::opInvalidOp)
3043           return getConstantFP(V1, VT);
3044         break;
3045       case ISD::FSUB:
3046         s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3047         if (s!=APFloat::opInvalidOp)
3048           return getConstantFP(V1, VT);
3049         break;
3050       case ISD::FMUL:
3051         s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3052         if (s!=APFloat::opInvalidOp)
3053           return getConstantFP(V1, VT);
3054         break;
3055       case ISD::FDIV:
3056         s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3057         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3058           return getConstantFP(V1, VT);
3059         break;
3060       case ISD::FREM :
3061         s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3062         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3063           return getConstantFP(V1, VT);
3064         break;
3065       case ISD::FCOPYSIGN:
3066         V1.copySign(V2);
3067         return getConstantFP(V1, VT);
3068       default: break;
3069       }
3070     }
3071
3072     if (Opcode == ISD::FP_ROUND) {
3073       APFloat V = N1CFP->getValueAPF();    // make copy
3074       bool ignored;
3075       // This can return overflow, underflow, or inexact; we don't care.
3076       // FIXME need to be more flexible about rounding mode.
3077       (void)V.convert(EVTToAPFloatSemantics(VT),
3078                       APFloat::rmNearestTiesToEven, &ignored);
3079       return getConstantFP(V, VT);
3080     }
3081   }
3082
3083   // Canonicalize an UNDEF to the RHS, even over a constant.
3084   if (N1.getOpcode() == ISD::UNDEF) {
3085     if (isCommutativeBinOp(Opcode)) {
3086       std::swap(N1, N2);
3087     } else {
3088       switch (Opcode) {
3089       case ISD::FP_ROUND_INREG:
3090       case ISD::SIGN_EXTEND_INREG:
3091       case ISD::SUB:
3092       case ISD::FSUB:
3093       case ISD::FDIV:
3094       case ISD::FREM:
3095       case ISD::SRA:
3096         return N1;     // fold op(undef, arg2) -> undef
3097       case ISD::UDIV:
3098       case ISD::SDIV:
3099       case ISD::UREM:
3100       case ISD::SREM:
3101       case ISD::SRL:
3102       case ISD::SHL:
3103         if (!VT.isVector())
3104           return getConstant(0, VT);    // fold op(undef, arg2) -> 0
3105         // For vectors, we can't easily build an all zero vector, just return
3106         // the LHS.
3107         return N2;
3108       }
3109     }
3110   }
3111
3112   // Fold a bunch of operators when the RHS is undef.
3113   if (N2.getOpcode() == ISD::UNDEF) {
3114     switch (Opcode) {
3115     case ISD::XOR:
3116       if (N1.getOpcode() == ISD::UNDEF)
3117         // Handle undef ^ undef -> 0 special case. This is a common
3118         // idiom (misuse).
3119         return getConstant(0, VT);
3120       // fallthrough
3121     case ISD::ADD:
3122     case ISD::ADDC:
3123     case ISD::ADDE:
3124     case ISD::SUB:
3125     case ISD::UDIV:
3126     case ISD::SDIV:
3127     case ISD::UREM:
3128     case ISD::SREM:
3129       return N2;       // fold op(arg1, undef) -> undef
3130     case ISD::FADD:
3131     case ISD::FSUB:
3132     case ISD::FMUL:
3133     case ISD::FDIV:
3134     case ISD::FREM:
3135       if (getTarget().Options.UnsafeFPMath)
3136         return N2;
3137       break;
3138     case ISD::MUL:
3139     case ISD::AND:
3140     case ISD::SRL:
3141     case ISD::SHL:
3142       if (!VT.isVector())
3143         return getConstant(0, VT);  // fold op(arg1, undef) -> 0
3144       // For vectors, we can't easily build an all zero vector, just return
3145       // the LHS.
3146       return N1;
3147     case ISD::OR:
3148       if (!VT.isVector())
3149         return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3150       // For vectors, we can't easily build an all one vector, just return
3151       // the LHS.
3152       return N1;
3153     case ISD::SRA:
3154       return N1;
3155     }
3156   }
3157
3158   // Memoize this node if possible.
3159   SDNode *N;
3160   SDVTList VTs = getVTList(VT);
3161   if (VT != MVT::Glue) {
3162     SDValue Ops[] = { N1, N2 };
3163     FoldingSetNodeID ID;
3164     AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3165     void *IP = 0;
3166     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3167       return SDValue(E, 0);
3168
3169     N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3170     CSEMap.InsertNode(N, IP);
3171   } else {
3172     N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3173   }
3174
3175   AllNodes.push_back(N);
3176 #ifndef NDEBUG
3177   VerifySDNode(N);
3178 #endif
3179   return SDValue(N, 0);
3180 }
3181
3182 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3183                               SDValue N1, SDValue N2, SDValue N3) {
3184   // Perform various simplifications.
3185   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3186   switch (Opcode) {
3187   case ISD::CONCAT_VECTORS:
3188     // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3189     // one big BUILD_VECTOR.
3190     if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3191         N2.getOpcode() == ISD::BUILD_VECTOR &&
3192         N3.getOpcode() == ISD::BUILD_VECTOR) {
3193       SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3194                                     N1.getNode()->op_end());
3195       Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3196       Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3197       return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3198     }
3199     break;
3200   case ISD::SETCC: {
3201     // Use FoldSetCC to simplify SETCC's.
3202     SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3203     if (Simp.getNode()) return Simp;
3204     break;
3205   }
3206   case ISD::SELECT:
3207     if (N1C) {
3208      if (N1C->getZExtValue())
3209        return N2;             // select true, X, Y -> X
3210      return N3;             // select false, X, Y -> Y
3211     }
3212
3213     if (N2 == N3) return N2;   // select C, X, X -> X
3214     break;
3215   case ISD::VECTOR_SHUFFLE:
3216     llvm_unreachable("should use getVectorShuffle constructor!");
3217   case ISD::INSERT_SUBVECTOR: {
3218     SDValue Index = N3;
3219     if (VT.isSimple() && N1.getValueType().isSimple()
3220         && N2.getValueType().isSimple()) {
3221       assert(VT.isVector() && N1.getValueType().isVector() &&
3222              N2.getValueType().isVector() &&
3223              "Insert subvector VTs must be a vectors");
3224       assert(VT == N1.getValueType() &&
3225              "Dest and insert subvector source types must match!");
3226       assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3227              "Insert subvector must be from smaller vector to larger vector!");
3228       if (isa<ConstantSDNode>(Index.getNode())) {
3229         assert((N2.getValueType().getVectorNumElements() +
3230                 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3231                 <= VT.getVectorNumElements())
3232                && "Insert subvector overflow!");
3233       }
3234
3235       // Trivial insertion.
3236       if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3237         return N2;
3238     }
3239     break;
3240   }
3241   case ISD::BITCAST:
3242     // Fold bit_convert nodes from a type to themselves.
3243     if (N1.getValueType() == VT)
3244       return N1;
3245     break;
3246   }
3247
3248   // Memoize node if it doesn't produce a flag.
3249   SDNode *N;
3250   SDVTList VTs = getVTList(VT);
3251   if (VT != MVT::Glue) {
3252     SDValue Ops[] = { N1, N2, N3 };
3253     FoldingSetNodeID ID;
3254     AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3255     void *IP = 0;
3256     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3257       return SDValue(E, 0);
3258
3259     N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3260     CSEMap.InsertNode(N, IP);
3261   } else {
3262     N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3263   }
3264
3265   AllNodes.push_back(N);
3266 #ifndef NDEBUG
3267   VerifySDNode(N);
3268 #endif
3269   return SDValue(N, 0);
3270 }
3271
3272 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3273                               SDValue N1, SDValue N2, SDValue N3,
3274                               SDValue N4) {
3275   SDValue Ops[] = { N1, N2, N3, N4 };
3276   return getNode(Opcode, DL, VT, Ops, 4);
3277 }
3278
3279 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3280                               SDValue N1, SDValue N2, SDValue N3,
3281                               SDValue N4, SDValue N5) {
3282   SDValue Ops[] = { N1, N2, N3, N4, N5 };
3283   return getNode(Opcode, DL, VT, Ops, 5);
3284 }
3285
3286 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3287 /// the incoming stack arguments to be loaded from the stack.
3288 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3289   SmallVector<SDValue, 8> ArgChains;
3290
3291   // Include the original chain at the beginning of the list. When this is
3292   // used by target LowerCall hooks, this helps legalize find the
3293   // CALLSEQ_BEGIN node.
3294   ArgChains.push_back(Chain);
3295
3296   // Add a chain value for each stack argument.
3297   for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3298        UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3299     if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3300       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3301         if (FI->getIndex() < 0)
3302           ArgChains.push_back(SDValue(L, 1));
3303
3304   // Build a tokenfactor for all the chains.
3305   return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3306                  &ArgChains[0], ArgChains.size());
3307 }
3308
3309 /// SplatByte - Distribute ByteVal over NumBits bits.
3310 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3311   APInt Val = APInt(NumBits, ByteVal);
3312   unsigned Shift = 8;
3313   for (unsigned i = NumBits; i > 8; i >>= 1) {
3314     Val = (Val << Shift) | Val;
3315     Shift <<= 1;
3316   }
3317   return Val;
3318 }
3319
3320 /// getMemsetValue - Vectorized representation of the memset value
3321 /// operand.
3322 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3323                               DebugLoc dl) {
3324   assert(Value.getOpcode() != ISD::UNDEF);
3325
3326   unsigned NumBits = VT.getScalarType().getSizeInBits();
3327   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3328     APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3329     if (VT.isInteger())
3330       return DAG.getConstant(Val, VT);
3331     return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3332   }
3333
3334   Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3335   if (NumBits > 8) {
3336     // Use a multiplication with 0x010101... to extend the input to the
3337     // required length.
3338     APInt Magic = SplatByte(NumBits, 0x01);
3339     Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3340   }
3341
3342   return Value;
3343 }
3344
3345 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3346 /// used when a memcpy is turned into a memset when the source is a constant
3347 /// string ptr.
3348 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3349                                   const TargetLowering &TLI, StringRef Str) {
3350   // Handle vector with all elements zero.
3351   if (Str.empty()) {
3352     if (VT.isInteger())
3353       return DAG.getConstant(0, VT);
3354     else if (VT == MVT::f32 || VT == MVT::f64)
3355       return DAG.getConstantFP(0.0, VT);
3356     else if (VT.isVector()) {
3357       unsigned NumElts = VT.getVectorNumElements();
3358       MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3359       return DAG.getNode(ISD::BITCAST, dl, VT,
3360                          DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3361                                                              EltVT, NumElts)));
3362     } else
3363       llvm_unreachable("Expected type!");
3364   }
3365
3366   assert(!VT.isVector() && "Can't handle vector type here!");
3367   unsigned NumVTBits = VT.getSizeInBits();
3368   unsigned NumVTBytes = NumVTBits / 8;
3369   unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3370
3371   APInt Val(NumVTBits, 0);
3372   if (TLI.isLittleEndian()) {
3373     for (unsigned i = 0; i != NumBytes; ++i)
3374       Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3375   } else {
3376     for (unsigned i = 0; i != NumBytes; ++i)
3377       Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3378   }
3379
3380   // If the "cost" of materializing the integer immediate is 1 or free, then
3381   // it is cost effective to turn the load into the immediate.
3382   const TargetTransformInfo *TTI = DAG.getTargetTransformInfo();
3383   if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) < 2)
3384     return DAG.getConstant(Val, VT);
3385   return SDValue(0, 0);
3386 }
3387
3388 /// getMemBasePlusOffset - Returns base and offset node for the
3389 ///
3390 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3391                                       SelectionDAG &DAG) {
3392   EVT VT = Base.getValueType();
3393   return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3394                      VT, Base, DAG.getConstant(Offset, VT));
3395 }
3396
3397 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3398 ///
3399 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3400   unsigned SrcDelta = 0;
3401   GlobalAddressSDNode *G = NULL;
3402   if (Src.getOpcode() == ISD::GlobalAddress)
3403     G = cast<GlobalAddressSDNode>(Src);
3404   else if (Src.getOpcode() == ISD::ADD &&
3405            Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3406            Src.getOperand(1).getOpcode() == ISD::Constant) {
3407     G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3408     SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3409   }
3410   if (!G)
3411     return false;
3412
3413   return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3414 }
3415
3416 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3417 /// to replace the memset / memcpy. Return true if the number of memory ops
3418 /// is below the threshold. It returns the types of the sequence of
3419 /// memory ops to perform memset / memcpy by reference.
3420 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3421                                      unsigned Limit, uint64_t Size,
3422                                      unsigned DstAlign, unsigned SrcAlign,
3423                                      bool IsMemset,
3424                                      bool ZeroMemset,
3425                                      bool MemcpyStrSrc,
3426                                      bool AllowOverlap,
3427                                      SelectionDAG &DAG,
3428                                      const TargetLowering &TLI) {
3429   assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3430          "Expecting memcpy / memset source to meet alignment requirement!");
3431   // If 'SrcAlign' is zero, that means the memory operation does not need to
3432   // load the value, i.e. memset or memcpy from constant string. Otherwise,
3433   // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3434   // is the specified alignment of the memory operation. If it is zero, that
3435   // means it's possible to change the alignment of the destination.
3436   // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3437   // not need to be loaded.
3438   EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3439                                    IsMemset, ZeroMemset, MemcpyStrSrc,
3440                                    DAG.getMachineFunction());
3441
3442   if (VT == MVT::Other) {
3443     if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment() ||
3444         TLI.allowsUnalignedMemoryAccesses(VT)) {
3445       VT = TLI.getPointerTy();
3446     } else {
3447       switch (DstAlign & 7) {
3448       case 0:  VT = MVT::i64; break;
3449       case 4:  VT = MVT::i32; break;
3450       case 2:  VT = MVT::i16; break;
3451       default: VT = MVT::i8;  break;
3452       }
3453     }
3454
3455     MVT LVT = MVT::i64;
3456     while (!TLI.isTypeLegal(LVT))
3457       LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3458     assert(LVT.isInteger());
3459
3460     if (VT.bitsGT(LVT))
3461       VT = LVT;
3462   }
3463
3464   unsigned NumMemOps = 0;
3465   while (Size != 0) {
3466     unsigned VTSize = VT.getSizeInBits() / 8;
3467     while (VTSize > Size) {
3468       // For now, only use non-vector load / store's for the left-over pieces.
3469       EVT NewVT = VT;
3470       unsigned NewVTSize;
3471
3472       bool Found = false;
3473       if (VT.isVector() || VT.isFloatingPoint()) {
3474         NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3475         if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3476             TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3477           Found = true;
3478         else if (NewVT == MVT::i64 &&
3479                  TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3480                  TLI.isSafeMemOpType(MVT::f64)) {
3481           // i64 is usually not legal on 32-bit targets, but f64 may be.
3482           NewVT = MVT::f64;
3483           Found = true;
3484         }
3485       }
3486
3487       if (!Found) {
3488         do {
3489           NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3490           if (NewVT == MVT::i8)
3491             break;
3492         } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3493       }
3494       NewVTSize = NewVT.getSizeInBits() / 8;
3495
3496       // If the new VT cannot cover all of the remaining bits, then consider
3497       // issuing a (or a pair of) unaligned and overlapping load / store.
3498       // FIXME: Only does this for 64-bit or more since we don't have proper
3499       // cost model for unaligned load / store.
3500       bool Fast;
3501       if (NumMemOps && AllowOverlap &&
3502           VTSize >= 8 && NewVTSize < Size &&
3503           TLI.allowsUnalignedMemoryAccesses(VT, &Fast) && Fast)
3504         VTSize = Size;
3505       else {
3506         VT = NewVT;
3507         VTSize = NewVTSize;
3508       }
3509     }
3510
3511     if (++NumMemOps > Limit)
3512       return false;
3513
3514     MemOps.push_back(VT);
3515     Size -= VTSize;
3516   }
3517
3518   return true;
3519 }
3520
3521 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3522                                        SDValue Chain, SDValue Dst,
3523                                        SDValue Src, uint64_t Size,
3524                                        unsigned Align, bool isVol,
3525                                        bool AlwaysInline,
3526                                        MachinePointerInfo DstPtrInfo,
3527                                        MachinePointerInfo SrcPtrInfo) {
3528   // Turn a memcpy of undef to nop.
3529   if (Src.getOpcode() == ISD::UNDEF)
3530     return Chain;
3531
3532   // Expand memcpy to a series of load and store ops if the size operand falls
3533   // below a certain threshold.
3534   // TODO: In the AlwaysInline case, if the size is big then generate a loop
3535   // rather than maybe a humongous number of loads and stores.
3536   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3537   std::vector<EVT> MemOps;
3538   bool DstAlignCanChange = false;
3539   MachineFunction &MF = DAG.getMachineFunction();
3540   MachineFrameInfo *MFI = MF.getFrameInfo();
3541   bool OptSize =
3542     MF.getFunction()->getAttributes().
3543       hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3544   FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3545   if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3546     DstAlignCanChange = true;
3547   unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3548   if (Align > SrcAlign)
3549     SrcAlign = Align;
3550   StringRef Str;
3551   bool CopyFromStr = isMemSrcFromString(Src, Str);
3552   bool isZeroStr = CopyFromStr && Str.empty();
3553   unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3554
3555   if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3556                                 (DstAlignCanChange ? 0 : Align),
3557                                 (isZeroStr ? 0 : SrcAlign),
3558                                 false, false, CopyFromStr, true, DAG, TLI))
3559     return SDValue();
3560
3561   if (DstAlignCanChange) {
3562     Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3563     unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3564     if (NewAlign > Align) {
3565       // Give the stack frame object a larger alignment if needed.
3566       if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3567         MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3568       Align = NewAlign;
3569     }
3570   }
3571
3572   SmallVector<SDValue, 8> OutChains;
3573   unsigned NumMemOps = MemOps.size();
3574   uint64_t SrcOff = 0, DstOff = 0;
3575   for (unsigned i = 0; i != NumMemOps; ++i) {
3576     EVT VT = MemOps[i];
3577     unsigned VTSize = VT.getSizeInBits() / 8;
3578     SDValue Value, Store;
3579
3580     if (VTSize > Size) {
3581       // Issuing an unaligned load / store pair  that overlaps with the previous
3582       // pair. Adjust the offset accordingly.
3583       assert(i == NumMemOps-1 && i != 0);
3584       SrcOff -= VTSize - Size;
3585       DstOff -= VTSize - Size;
3586     }
3587
3588     if (CopyFromStr &&
3589         (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3590       // It's unlikely a store of a vector immediate can be done in a single
3591       // instruction. It would require a load from a constantpool first.
3592       // We only handle zero vectors here.
3593       // FIXME: Handle other cases where store of vector immediate is done in
3594       // a single instruction.
3595       Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3596       if (Value.getNode())
3597         Store = DAG.getStore(Chain, dl, Value,
3598                              getMemBasePlusOffset(Dst, DstOff, DAG),
3599                              DstPtrInfo.getWithOffset(DstOff), isVol,
3600                              false, Align);
3601     }
3602
3603     if (!Store.getNode()) {
3604       // The type might not be legal for the target.  This should only happen
3605       // if the type is smaller than a legal type, as on PPC, so the right
3606       // thing to do is generate a LoadExt/StoreTrunc pair.  These simplify
3607       // to Load/Store if NVT==VT.
3608       // FIXME does the case above also need this?
3609       EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3610       assert(NVT.bitsGE(VT));
3611       Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3612                              getMemBasePlusOffset(Src, SrcOff, DAG),
3613                              SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3614                              MinAlign(SrcAlign, SrcOff));
3615       Store = DAG.getTruncStore(Chain, dl, Value,
3616                                 getMemBasePlusOffset(Dst, DstOff, DAG),
3617                                 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3618                                 false, Align);
3619     }
3620     OutChains.push_back(Store);
3621     SrcOff += VTSize;
3622     DstOff += VTSize;
3623     Size -= VTSize;
3624   }
3625
3626   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3627                      &OutChains[0], OutChains.size());
3628 }
3629
3630 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3631                                         SDValue Chain, SDValue Dst,
3632                                         SDValue Src, uint64_t Size,
3633                                         unsigned Align,  bool isVol,
3634                                         bool AlwaysInline,
3635                                         MachinePointerInfo DstPtrInfo,
3636                                         MachinePointerInfo SrcPtrInfo) {
3637   // Turn a memmove of undef to nop.
3638   if (Src.getOpcode() == ISD::UNDEF)
3639     return Chain;
3640
3641   // Expand memmove to a series of load and store ops if the size operand falls
3642   // below a certain threshold.
3643   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3644   std::vector<EVT> MemOps;
3645   bool DstAlignCanChange = false;
3646   MachineFunction &MF = DAG.getMachineFunction();
3647   MachineFrameInfo *MFI = MF.getFrameInfo();
3648   bool OptSize = MF.getFunction()->getAttributes().
3649     hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3650   FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3651   if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3652     DstAlignCanChange = true;
3653   unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3654   if (Align > SrcAlign)
3655     SrcAlign = Align;
3656   unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3657
3658   if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3659                                 (DstAlignCanChange ? 0 : Align), SrcAlign,
3660                                 false, false, false, false, DAG, TLI))
3661     return SDValue();
3662
3663   if (DstAlignCanChange) {
3664     Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3665     unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3666     if (NewAlign > Align) {
3667       // Give the stack frame object a larger alignment if needed.
3668       if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3669         MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3670       Align = NewAlign;
3671     }
3672   }
3673
3674   uint64_t SrcOff = 0, DstOff = 0;
3675   SmallVector<SDValue, 8> LoadValues;
3676   SmallVector<SDValue, 8> LoadChains;
3677   SmallVector<SDValue, 8> OutChains;
3678   unsigned NumMemOps = MemOps.size();
3679   for (unsigned i = 0; i < NumMemOps; i++) {
3680     EVT VT = MemOps[i];
3681     unsigned VTSize = VT.getSizeInBits() / 8;
3682     SDValue Value, Store;
3683
3684     Value = DAG.getLoad(VT, dl, Chain,
3685                         getMemBasePlusOffset(Src, SrcOff, DAG),
3686                         SrcPtrInfo.getWithOffset(SrcOff), isVol,
3687                         false, false, SrcAlign);
3688     LoadValues.push_back(Value);
3689     LoadChains.push_back(Value.getValue(1));
3690     SrcOff += VTSize;
3691   }
3692   Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3693                       &LoadChains[0], LoadChains.size());
3694   OutChains.clear();
3695   for (unsigned i = 0; i < NumMemOps; i++) {
3696     EVT VT = MemOps[i];
3697     unsigned VTSize = VT.getSizeInBits() / 8;
3698     SDValue Value, Store;
3699
3700     Store = DAG.getStore(Chain, dl, LoadValues[i],
3701                          getMemBasePlusOffset(Dst, DstOff, DAG),
3702                          DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3703     OutChains.push_back(Store);
3704     DstOff += VTSize;
3705   }
3706
3707   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3708                      &OutChains[0], OutChains.size());
3709 }
3710
3711 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3712                                SDValue Chain, SDValue Dst,
3713                                SDValue Src, uint64_t Size,
3714                                unsigned Align, bool isVol,
3715                                MachinePointerInfo DstPtrInfo) {
3716   // Turn a memset of undef to nop.
3717   if (Src.getOpcode() == ISD::UNDEF)
3718     return Chain;
3719
3720   // Expand memset to a series of load/store ops if the size operand
3721   // falls below a certain threshold.
3722   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3723   std::vector<EVT> MemOps;
3724   bool DstAlignCanChange = false;
3725   MachineFunction &MF = DAG.getMachineFunction();
3726   MachineFrameInfo *MFI = MF.getFrameInfo();
3727   bool OptSize = MF.getFunction()->getAttributes().
3728     hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3729   FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3730   if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3731     DstAlignCanChange = true;
3732   bool IsZeroVal =
3733     isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3734   if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3735                                 Size, (DstAlignCanChange ? 0 : Align), 0,
3736                                 true, IsZeroVal, false, true, DAG, TLI))
3737     return SDValue();
3738
3739   if (DstAlignCanChange) {
3740     Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3741     unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3742     if (NewAlign > Align) {
3743       // Give the stack frame object a larger alignment if needed.
3744       if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3745         MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3746       Align = NewAlign;
3747     }
3748   }
3749
3750   SmallVector<SDValue, 8> OutChains;
3751   uint64_t DstOff = 0;
3752   unsigned NumMemOps = MemOps.size();
3753
3754   // Find the largest store and generate the bit pattern for it.
3755   EVT LargestVT = MemOps[0];
3756   for (unsigned i = 1; i < NumMemOps; i++)
3757     if (MemOps[i].bitsGT(LargestVT))
3758       LargestVT = MemOps[i];
3759   SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3760
3761   for (unsigned i = 0; i < NumMemOps; i++) {
3762     EVT VT = MemOps[i];
3763     unsigned VTSize = VT.getSizeInBits() / 8;
3764     if (VTSize > Size) {
3765       // Issuing an unaligned load / store pair  that overlaps with the previous
3766       // pair. Adjust the offset accordingly.
3767       assert(i == NumMemOps-1 && i != 0);
3768       DstOff -= VTSize - Size;
3769     }
3770
3771     // If this store is smaller than the largest store see whether we can get
3772     // the smaller value for free with a truncate.
3773     SDValue Value = MemSetValue;
3774     if (VT.bitsLT(LargestVT)) {
3775       if (!LargestVT.isVector() && !VT.isVector() &&
3776           TLI.isTruncateFree(LargestVT, VT))
3777         Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3778       else
3779         Value = getMemsetValue(Src, VT, DAG, dl);
3780     }
3781     assert(Value.getValueType() == VT && "Value with wrong type.");
3782     SDValue Store = DAG.getStore(Chain, dl, Value,
3783                                  getMemBasePlusOffset(Dst, DstOff, DAG),
3784                                  DstPtrInfo.getWithOffset(DstOff),
3785                                  isVol, false, Align);
3786     OutChains.push_back(Store);
3787     DstOff += VT.getSizeInBits() / 8;
3788     Size -= VTSize;
3789   }
3790
3791   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3792                      &OutChains[0], OutChains.size());
3793 }
3794
3795 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3796                                 SDValue Src, SDValue Size,
3797                                 unsigned Align, bool isVol, bool AlwaysInline,
3798                                 MachinePointerInfo DstPtrInfo,
3799                                 MachinePointerInfo SrcPtrInfo) {
3800
3801   // Check to see if we should lower the memcpy to loads and stores first.
3802   // For cases within the target-specified limits, this is the best choice.
3803   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3804   if (ConstantSize) {
3805     // Memcpy with size zero? Just return the original chain.
3806     if (ConstantSize->isNullValue())
3807       return Chain;
3808
3809     SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3810                                              ConstantSize->getZExtValue(),Align,
3811                                 isVol, false, DstPtrInfo, SrcPtrInfo);
3812     if (Result.getNode())
3813       return Result;
3814   }
3815
3816   // Then check to see if we should lower the memcpy with target-specific
3817   // code. If the target chooses to do this, this is the next best.
3818   SDValue Result =
3819     TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3820                                 isVol, AlwaysInline,
3821                                 DstPtrInfo, SrcPtrInfo);
3822   if (Result.getNode())
3823     return Result;
3824
3825   // If we really need inline code and the target declined to provide it,
3826   // use a (potentially long) sequence of loads and stores.
3827   if (AlwaysInline) {
3828     assert(ConstantSize && "AlwaysInline requires a constant size!");
3829     return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3830                                    ConstantSize->getZExtValue(), Align, isVol,
3831                                    true, DstPtrInfo, SrcPtrInfo);
3832   }
3833
3834   // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3835   // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3836   // respect volatile, so they may do things like read or write memory
3837   // beyond the given memory regions. But fixing this isn't easy, and most
3838   // people don't care.
3839
3840   // Emit a library call.
3841   TargetLowering::ArgListTy Args;
3842   TargetLowering::ArgListEntry Entry;
3843   Entry.Ty = TLI.getDataLayout()->getIntPtrType(*getContext());
3844   Entry.Node = Dst; Args.push_back(Entry);
3845   Entry.Node = Src; Args.push_back(Entry);
3846   Entry.Node = Size; Args.push_back(Entry);
3847   // FIXME: pass in DebugLoc
3848   TargetLowering::
3849   CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3850                     false, false, false, false, 0,
3851                     TLI.getLibcallCallingConv(RTLIB::MEMCPY),
3852                     /*isTailCall=*/false,
3853                     /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3854                     getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3855                                       TLI.getPointerTy()),
3856                     Args, *this, dl);
3857   std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3858
3859   return CallResult.second;
3860 }
3861
3862 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3863                                  SDValue Src, SDValue Size,
3864                                  unsigned Align, bool isVol,
3865                                  MachinePointerInfo DstPtrInfo,
3866                                  MachinePointerInfo SrcPtrInfo) {
3867
3868   // Check to see if we should lower the memmove to loads and stores first.
3869   // For cases within the target-specified limits, this is the best choice.
3870   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3871   if (ConstantSize) {
3872     // Memmove with size zero? Just return the original chain.
3873     if (ConstantSize->isNullValue())
3874       return Chain;
3875
3876     SDValue Result =
3877       getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3878                                ConstantSize->getZExtValue(), Align, isVol,
3879                                false, DstPtrInfo, SrcPtrInfo);
3880     if (Result.getNode())
3881       return Result;
3882   }
3883
3884   // Then check to see if we should lower the memmove with target-specific
3885   // code. If the target chooses to do this, this is the next best.
3886   SDValue Result =
3887     TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3888                                  DstPtrInfo, SrcPtrInfo);
3889   if (Result.getNode())
3890     return Result;
3891
3892   // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3893   // not be safe.  See memcpy above for more details.
3894
3895   // Emit a library call.
3896   TargetLowering::ArgListTy Args;
3897   TargetLowering::ArgListEntry Entry;
3898   Entry.Ty = TLI.getDataLayout()->getIntPtrType(*getContext());
3899   Entry.Node = Dst; Args.push_back(Entry);
3900   Entry.Node = Src; Args.push_back(Entry);
3901   Entry.Node = Size; Args.push_back(Entry);
3902   // FIXME:  pass in DebugLoc
3903   TargetLowering::
3904   CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3905                     false, false, false, false, 0,
3906                     TLI.getLibcallCallingConv(RTLIB::MEMMOVE),
3907                     /*isTailCall=*/false,
3908                     /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3909                     getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3910                                       TLI.getPointerTy()),
3911                     Args, *this, dl);
3912   std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3913
3914   return CallResult.second;
3915 }
3916
3917 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3918                                 SDValue Src, SDValue Size,
3919                                 unsigned Align, bool isVol,
3920                                 MachinePointerInfo DstPtrInfo) {
3921
3922   // Check to see if we should lower the memset to stores first.
3923   // For cases within the target-specified limits, this is the best choice.
3924   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3925   if (ConstantSize) {
3926     // Memset with size zero? Just return the original chain.
3927     if (ConstantSize->isNullValue())
3928       return Chain;
3929
3930     SDValue Result =
3931       getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3932                       Align, isVol, DstPtrInfo);
3933
3934     if (Result.getNode())
3935       return Result;
3936   }
3937
3938   // Then check to see if we should lower the memset with target-specific
3939   // code. If the target chooses to do this, this is the next best.
3940   SDValue Result =
3941     TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3942                                 DstPtrInfo);
3943   if (Result.getNode())
3944     return Result;
3945
3946   // Emit a library call.
3947   Type *IntPtrTy = TLI.getDataLayout()->getIntPtrType(*getContext());
3948   TargetLowering::ArgListTy Args;
3949   TargetLowering::ArgListEntry Entry;
3950   Entry.Node = Dst; Entry.Ty = IntPtrTy;
3951   Args.push_back(Entry);
3952   // Extend or truncate the argument to be an i32 value for the call.
3953   if (Src.getValueType().bitsGT(MVT::i32))
3954     Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3955   else
3956     Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3957   Entry.Node = Src;
3958   Entry.Ty = Type::getInt32Ty(*getContext());
3959   Entry.isSExt = true;
3960   Args.push_back(Entry);
3961   Entry.Node = Size;
3962   Entry.Ty = IntPtrTy;
3963   Entry.isSExt = false;
3964   Args.push_back(Entry);
3965   // FIXME: pass in DebugLoc
3966   TargetLowering::
3967   CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3968                     false, false, false, false, 0,
3969                     TLI.getLibcallCallingConv(RTLIB::MEMSET),
3970                     /*isTailCall=*/false,
3971                     /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3972                     getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3973                                       TLI.getPointerTy()),
3974                     Args, *this, dl);
3975   std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3976
3977   return CallResult.second;
3978 }
3979
3980 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3981                                 SDValue Chain, SDValue Ptr, SDValue Cmp,
3982                                 SDValue Swp, MachinePointerInfo PtrInfo,
3983                                 unsigned Alignment,
3984                                 AtomicOrdering Ordering,
3985                                 SynchronizationScope SynchScope) {
3986   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
3987     Alignment = getEVTAlignment(MemVT);
3988
3989   MachineFunction &MF = getMachineFunction();
3990
3991   // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
3992   // For now, atomics are considered to be volatile always.
3993   // FIXME: Volatile isn't really correct; we should keep track of atomic
3994   // orderings in the memoperand.
3995   unsigned Flags = MachineMemOperand::MOVolatile;
3996   if (Opcode != ISD::ATOMIC_STORE)
3997     Flags |= MachineMemOperand::MOLoad;
3998   if (Opcode != ISD::ATOMIC_LOAD)
3999     Flags |= MachineMemOperand::MOStore;
4000
4001   MachineMemOperand *MMO =
4002     MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4003
4004   return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4005                    Ordering, SynchScope);
4006 }
4007
4008 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4009                                 SDValue Chain,
4010                                 SDValue Ptr, SDValue Cmp,
4011                                 SDValue Swp, MachineMemOperand *MMO,
4012                                 AtomicOrdering Ordering,
4013                                 SynchronizationScope SynchScope) {
4014   assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4015   assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4016
4017   EVT VT = Cmp.getValueType();
4018
4019   SDVTList VTs = getVTList(VT, MVT::Other);
4020   FoldingSetNodeID ID;
4021   ID.AddInteger(MemVT.getRawBits());
4022   SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4023   AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
4024   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4025   void* IP = 0;
4026   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4027     cast<AtomicSDNode>(E)->refineAlignment(MMO);
4028     return SDValue(E, 0);
4029   }
4030   SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4031                                                Ptr, Cmp, Swp, MMO, Ordering,
4032                                                SynchScope);
4033   CSEMap.InsertNode(N, IP);
4034   AllNodes.push_back(N);
4035   return SDValue(N, 0);
4036 }
4037
4038 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4039                                 SDValue Chain,
4040                                 SDValue Ptr, SDValue Val,
4041                                 const Value* PtrVal,
4042                                 unsigned Alignment,
4043                                 AtomicOrdering Ordering,
4044                                 SynchronizationScope SynchScope) {
4045   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
4046     Alignment = getEVTAlignment(MemVT);
4047
4048   MachineFunction &MF = getMachineFunction();
4049   // An atomic store does not load. An atomic load does not store.
4050   // (An atomicrmw obviously both loads and stores.)
4051   // For now, atomics are considered to be volatile always, and they are
4052   // chained as such.
4053   // FIXME: Volatile isn't really correct; we should keep track of atomic
4054   // orderings in the memoperand.
4055   unsigned Flags = MachineMemOperand::MOVolatile;
4056   if (Opcode != ISD::ATOMIC_STORE)
4057     Flags |= MachineMemOperand::MOLoad;
4058   if (Opcode != ISD::ATOMIC_LOAD)
4059     Flags |= MachineMemOperand::MOStore;
4060
4061   MachineMemOperand *MMO =
4062     MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4063                             MemVT.getStoreSize(), Alignment);
4064
4065   return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4066                    Ordering, SynchScope);
4067 }
4068
4069 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4070                                 SDValue Chain,
4071                                 SDValue Ptr, SDValue Val,
4072                                 MachineMemOperand *MMO,
4073                                 AtomicOrdering Ordering,
4074                                 SynchronizationScope SynchScope) {
4075   assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4076           Opcode == ISD::ATOMIC_LOAD_SUB ||
4077           Opcode == ISD::ATOMIC_LOAD_AND ||
4078           Opcode == ISD::ATOMIC_LOAD_OR ||
4079           Opcode == ISD::ATOMIC_LOAD_XOR ||
4080           Opcode == ISD::ATOMIC_LOAD_NAND ||
4081           Opcode == ISD::ATOMIC_LOAD_MIN ||
4082           Opcode == ISD::ATOMIC_LOAD_MAX ||
4083           Opcode == ISD::ATOMIC_LOAD_UMIN ||
4084           Opcode == ISD::ATOMIC_LOAD_UMAX ||
4085           Opcode == ISD::ATOMIC_SWAP ||
4086           Opcode == ISD::ATOMIC_STORE) &&
4087          "Invalid Atomic Op");
4088
4089   EVT VT = Val.getValueType();
4090
4091   SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4092                                                getVTList(VT, MVT::Other);
4093   FoldingSetNodeID ID;
4094   ID.AddInteger(MemVT.getRawBits());
4095   SDValue Ops[] = {Chain, Ptr, Val};
4096   AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
4097   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4098   void* IP = 0;
4099   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4100     cast<AtomicSDNode>(E)->refineAlignment(MMO);
4101     return SDValue(E, 0);
4102   }
4103   SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4104                                                Ptr, Val, MMO,
4105                                                Ordering, SynchScope);
4106   CSEMap.InsertNode(N, IP);
4107   AllNodes.push_back(N);
4108   return SDValue(N, 0);
4109 }
4110
4111 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4112                                 EVT VT, SDValue Chain,
4113                                 SDValue Ptr,
4114                                 const Value* PtrVal,
4115                                 unsigned Alignment,
4116                                 AtomicOrdering Ordering,
4117                                 SynchronizationScope SynchScope) {
4118   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
4119     Alignment = getEVTAlignment(MemVT);
4120
4121   MachineFunction &MF = getMachineFunction();
4122   // An atomic store does not load. An atomic load does not store.
4123   // (An atomicrmw obviously both loads and stores.)
4124   // For now, atomics are considered to be volatile always, and they are
4125   // chained as such.
4126   // FIXME: Volatile isn't really correct; we should keep track of atomic
4127   // orderings in the memoperand.
4128   unsigned Flags = MachineMemOperand::MOVolatile;
4129   if (Opcode != ISD::ATOMIC_STORE)
4130     Flags |= MachineMemOperand::MOLoad;
4131   if (Opcode != ISD::ATOMIC_LOAD)
4132     Flags |= MachineMemOperand::MOStore;
4133
4134   MachineMemOperand *MMO =
4135     MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4136                             MemVT.getStoreSize(), Alignment);
4137
4138   return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4139                    Ordering, SynchScope);
4140 }
4141
4142 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4143                                 EVT VT, SDValue Chain,
4144                                 SDValue Ptr,
4145                                 MachineMemOperand *MMO,
4146                                 AtomicOrdering Ordering,
4147                                 SynchronizationScope SynchScope) {
4148   assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4149
4150   SDVTList VTs = getVTList(VT, MVT::Other);
4151   FoldingSetNodeID ID;
4152   ID.AddInteger(MemVT.getRawBits());
4153   SDValue Ops[] = {Chain, Ptr};
4154   AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4155   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4156   void* IP = 0;
4157   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4158     cast<AtomicSDNode>(E)->refineAlignment(MMO);
4159     return SDValue(E, 0);
4160   }
4161   SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4162                                                Ptr, MMO, Ordering, SynchScope);
4163   CSEMap.InsertNode(N, IP);
4164   AllNodes.push_back(N);
4165   return SDValue(N, 0);
4166 }
4167
4168 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4169 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4170                                      DebugLoc dl) {
4171   if (NumOps == 1)
4172     return Ops[0];
4173
4174   SmallVector<EVT, 4> VTs;
4175   VTs.reserve(NumOps);
4176   for (unsigned i = 0; i < NumOps; ++i)
4177     VTs.push_back(Ops[i].getValueType());
4178   return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4179                  Ops, NumOps);
4180 }
4181
4182 SDValue
4183 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4184                                   const EVT *VTs, unsigned NumVTs,
4185                                   const SDValue *Ops, unsigned NumOps,
4186                                   EVT MemVT, MachinePointerInfo PtrInfo,
4187                                   unsigned Align, bool Vol,
4188                                   bool ReadMem, bool WriteMem) {
4189   return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4190                              MemVT, PtrInfo, Align, Vol,
4191                              ReadMem, WriteMem);
4192 }
4193
4194 SDValue
4195 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4196                                   const SDValue *Ops, unsigned NumOps,
4197                                   EVT MemVT, MachinePointerInfo PtrInfo,
4198                                   unsigned Align, bool Vol,
4199                                   bool ReadMem, bool WriteMem) {
4200   if (Align == 0)  // Ensure that codegen never sees alignment 0
4201     Align = getEVTAlignment(MemVT);
4202
4203   MachineFunction &MF = getMachineFunction();
4204   unsigned Flags = 0;
4205   if (WriteMem)
4206     Flags |= MachineMemOperand::MOStore;
4207   if (ReadMem)
4208     Flags |= MachineMemOperand::MOLoad;
4209   if (Vol)
4210     Flags |= MachineMemOperand::MOVolatile;
4211   MachineMemOperand *MMO =
4212     MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4213
4214   return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4215 }
4216
4217 SDValue
4218 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4219                                   const SDValue *Ops, unsigned NumOps,
4220                                   EVT MemVT, MachineMemOperand *MMO) {
4221   assert((Opcode == ISD::INTRINSIC_VOID ||
4222           Opcode == ISD::INTRINSIC_W_CHAIN ||
4223           Opcode == ISD::PREFETCH ||
4224           Opcode == ISD::LIFETIME_START ||
4225           Opcode == ISD::LIFETIME_END ||
4226           (Opcode <= INT_MAX &&
4227            (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4228          "Opcode is not a memory-accessing opcode!");
4229
4230   // Memoize the node unless it returns a flag.
4231   MemIntrinsicSDNode *N;
4232   if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4233     FoldingSetNodeID ID;
4234     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4235     ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4236     void *IP = 0;
4237     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4238       cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4239       return SDValue(E, 0);
4240     }
4241
4242     N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4243                                                MemVT, MMO);
4244     CSEMap.InsertNode(N, IP);
4245   } else {
4246     N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4247                                                MemVT, MMO);
4248   }
4249   AllNodes.push_back(N);
4250   return SDValue(N, 0);
4251 }
4252
4253 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4254 /// MachinePointerInfo record from it.  This is particularly useful because the
4255 /// code generator has many cases where it doesn't bother passing in a
4256 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4257 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4258   // If this is FI+Offset, we can model it.
4259   if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4260     return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4261
4262   // If this is (FI+Offset1)+Offset2, we can model it.
4263   if (Ptr.getOpcode() != ISD::ADD ||
4264       !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4265       !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4266     return MachinePointerInfo();
4267
4268   int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4269   return MachinePointerInfo::getFixedStack(FI, Offset+
4270                        cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4271 }
4272
4273 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4274 /// MachinePointerInfo record from it.  This is particularly useful because the
4275 /// code generator has many cases where it doesn't bother passing in a
4276 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4277 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4278   // If the 'Offset' value isn't a constant, we can't handle this.
4279   if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4280     return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4281   if (OffsetOp.getOpcode() == ISD::UNDEF)
4282     return InferPointerInfo(Ptr);
4283   return MachinePointerInfo();
4284 }
4285
4286
4287 SDValue
4288 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4289                       EVT VT, DebugLoc dl, SDValue Chain,
4290                       SDValue Ptr, SDValue Offset,
4291                       MachinePointerInfo PtrInfo, EVT MemVT,
4292                       bool isVolatile, bool isNonTemporal, bool isInvariant,
4293                       unsigned Alignment, const MDNode *TBAAInfo,
4294                       const MDNode *Ranges) {
4295   assert(Chain.getValueType() == MVT::Other &&
4296         "Invalid chain type");
4297   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
4298     Alignment = getEVTAlignment(VT);
4299
4300   unsigned Flags = MachineMemOperand::MOLoad;
4301   if (isVolatile)
4302     Flags |= MachineMemOperand::MOVolatile;
4303   if (isNonTemporal)
4304     Flags |= MachineMemOperand::MONonTemporal;
4305   if (isInvariant)
4306     Flags |= MachineMemOperand::MOInvariant;
4307
4308   // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4309   // clients.
4310   if (PtrInfo.V == 0)
4311     PtrInfo = InferPointerInfo(Ptr, Offset);
4312
4313   MachineFunction &MF = getMachineFunction();
4314   MachineMemOperand *MMO =
4315     MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4316                             TBAAInfo, Ranges);
4317   return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4318 }
4319
4320 SDValue
4321 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4322                       EVT VT, DebugLoc dl, SDValue Chain,
4323                       SDValue Ptr, SDValue Offset, EVT MemVT,
4324                       MachineMemOperand *MMO) {
4325   if (VT == MemVT) {
4326     ExtType = ISD::NON_EXTLOAD;
4327   } else if (ExtType == ISD::NON_EXTLOAD) {
4328     assert(VT == MemVT && "Non-extending load from different memory type!");
4329   } else {
4330     // Extending load.
4331     assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4332            "Should only be an extending load, not truncating!");
4333     assert(VT.isInteger() == MemVT.isInteger() &&
4334            "Cannot convert from FP to Int or Int -> FP!");
4335     assert(VT.isVector() == MemVT.isVector() &&
4336            "Cannot use trunc store to convert to or from a vector!");
4337     assert((!VT.isVector() ||
4338             VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4339            "Cannot use trunc store to change the number of vector elements!");
4340   }
4341
4342   bool Indexed = AM != ISD::UNINDEXED;
4343   assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4344          "Unindexed load with an offset!");
4345
4346   SDVTList VTs = Indexed ?
4347     getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4348   SDValue Ops[] = { Chain, Ptr, Offset };
4349   FoldingSetNodeID ID;
4350   AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4351   ID.AddInteger(MemVT.getRawBits());
4352   ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4353                                      MMO->isNonTemporal(),
4354                                      MMO->isInvariant()));
4355   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4356   void *IP = 0;
4357   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4358     cast<LoadSDNode>(E)->refineAlignment(MMO);
4359     return SDValue(E, 0);
4360   }
4361   SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4362                                              MemVT, MMO);
4363   CSEMap.InsertNode(N, IP);
4364   AllNodes.push_back(N);
4365   return SDValue(N, 0);
4366 }
4367
4368 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4369                               SDValue Chain, SDValue Ptr,
4370                               MachinePointerInfo PtrInfo,
4371                               bool isVolatile, bool isNonTemporal,
4372                               bool isInvariant, unsigned Alignment,
4373                               const MDNode *TBAAInfo,
4374                               const MDNode *Ranges) {
4375   SDValue Undef = getUNDEF(Ptr.getValueType());
4376   return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4377                  PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4378                  TBAAInfo, Ranges);
4379 }
4380
4381 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4382                                  SDValue Chain, SDValue Ptr,
4383                                  MachinePointerInfo PtrInfo, EVT MemVT,
4384                                  bool isVolatile, bool isNonTemporal,
4385                                  unsigned Alignment, const MDNode *TBAAInfo) {
4386   SDValue Undef = getUNDEF(Ptr.getValueType());
4387   return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4388                  PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4389                  TBAAInfo);
4390 }
4391
4392
4393 SDValue
4394 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4395                              SDValue Offset, ISD::MemIndexedMode AM) {
4396   LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4397   assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4398          "Load is already a indexed load!");
4399   return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4400                  LD->getChain(), Base, Offset, LD->getPointerInfo(),
4401                  LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4402                  false, LD->getAlignment());
4403 }
4404
4405 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4406                                SDValue Ptr, MachinePointerInfo PtrInfo,
4407                                bool isVolatile, bool isNonTemporal,
4408                                unsigned Alignment, const MDNode *TBAAInfo) {
4409   assert(Chain.getValueType() == MVT::Other &&
4410         "Invalid chain type");
4411   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
4412     Alignment = getEVTAlignment(Val.getValueType());
4413
4414   unsigned Flags = MachineMemOperand::MOStore;
4415   if (isVolatile)
4416     Flags |= MachineMemOperand::MOVolatile;
4417   if (isNonTemporal)
4418     Flags |= MachineMemOperand::MONonTemporal;
4419
4420   if (PtrInfo.V == 0)
4421     PtrInfo = InferPointerInfo(Ptr);
4422
4423   MachineFunction &MF = getMachineFunction();
4424   MachineMemOperand *MMO =
4425     MF.getMachineMemOperand(PtrInfo, Flags,
4426                             Val.getValueType().getStoreSize(), Alignment,
4427                             TBAAInfo);
4428
4429   return getStore(Chain, dl, Val, Ptr, MMO);
4430 }
4431
4432 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4433                                SDValue Ptr, MachineMemOperand *MMO) {
4434   assert(Chain.getValueType() == MVT::Other &&
4435         "Invalid chain type");
4436   EVT VT = Val.getValueType();
4437   SDVTList VTs = getVTList(MVT::Other);
4438   SDValue Undef = getUNDEF(Ptr.getValueType());
4439   SDValue Ops[] = { Chain, Val, Ptr, Undef };
4440   FoldingSetNodeID ID;
4441   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4442   ID.AddInteger(VT.getRawBits());
4443   ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4444                                      MMO->isNonTemporal(), MMO->isInvariant()));
4445   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4446   void *IP = 0;
4447   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4448     cast<StoreSDNode>(E)->refineAlignment(MMO);
4449     return SDValue(E, 0);
4450   }
4451   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4452                                               false, VT, MMO);
4453   CSEMap.InsertNode(N, IP);
4454   AllNodes.push_back(N);
4455   return SDValue(N, 0);
4456 }
4457
4458 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4459                                     SDValue Ptr, MachinePointerInfo PtrInfo,
4460                                     EVT SVT,bool isVolatile, bool isNonTemporal,
4461                                     unsigned Alignment,
4462                                     const MDNode *TBAAInfo) {
4463   assert(Chain.getValueType() == MVT::Other &&
4464         "Invalid chain type");
4465   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
4466     Alignment = getEVTAlignment(SVT);
4467
4468   unsigned Flags = MachineMemOperand::MOStore;
4469   if (isVolatile)
4470     Flags |= MachineMemOperand::MOVolatile;
4471   if (isNonTemporal)
4472     Flags |= MachineMemOperand::MONonTemporal;
4473
4474   if (PtrInfo.V == 0)
4475     PtrInfo = InferPointerInfo(Ptr);
4476
4477   MachineFunction &MF = getMachineFunction();
4478   MachineMemOperand *MMO =
4479     MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4480                             TBAAInfo);
4481
4482   return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4483 }
4484
4485 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4486                                     SDValue Ptr, EVT SVT,
4487                                     MachineMemOperand *MMO) {
4488   EVT VT = Val.getValueType();
4489
4490   assert(Chain.getValueType() == MVT::Other &&
4491         "Invalid chain type");
4492   if (VT == SVT)
4493     return getStore(Chain, dl, Val, Ptr, MMO);
4494
4495   assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4496          "Should only be a truncating store, not extending!");
4497   assert(VT.isInteger() == SVT.isInteger() &&
4498          "Can't do FP-INT conversion!");
4499   assert(VT.isVector() == SVT.isVector() &&
4500          "Cannot use trunc store to convert to or from a vector!");
4501   assert((!VT.isVector() ||
4502           VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4503          "Cannot use trunc store to change the number of vector elements!");
4504
4505   SDVTList VTs = getVTList(MVT::Other);
4506   SDValue Undef = getUNDEF(Ptr.getValueType());
4507   SDValue Ops[] = { Chain, Val, Ptr, Undef };
4508   FoldingSetNodeID ID;
4509   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4510   ID.AddInteger(SVT.getRawBits());
4511   ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4512                                      MMO->isNonTemporal(), MMO->isInvariant()));
4513   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4514   void *IP = 0;
4515   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4516     cast<StoreSDNode>(E)->refineAlignment(MMO);
4517     return SDValue(E, 0);
4518   }
4519   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4520                                               true, SVT, MMO);
4521   CSEMap.InsertNode(N, IP);
4522   AllNodes.push_back(N);
4523   return SDValue(N, 0);
4524 }
4525
4526 SDValue
4527 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4528                               SDValue Offset, ISD::MemIndexedMode AM) {
4529   StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4530   assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4531          "Store is already a indexed store!");
4532   SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4533   SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4534   FoldingSetNodeID ID;
4535   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4536   ID.AddInteger(ST->getMemoryVT().getRawBits());
4537   ID.AddInteger(ST->getRawSubclassData());
4538   ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4539   void *IP = 0;
4540   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4541     return SDValue(E, 0);
4542
4543   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4544                                               ST->isTruncatingStore(),
4545                                               ST->getMemoryVT(),
4546                                               ST->getMemOperand());
4547   CSEMap.InsertNode(N, IP);
4548   AllNodes.push_back(N);
4549   return SDValue(N, 0);
4550 }
4551
4552 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4553                                SDValue Chain, SDValue Ptr,
4554                                SDValue SV,
4555                                unsigned Align) {
4556   SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4557   return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4558 }
4559
4560 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4561                               const SDUse *Ops, unsigned NumOps) {
4562   switch (NumOps) {
4563   case 0: return getNode(Opcode, DL, VT);
4564   case 1: return getNode(Opcode, DL, VT, Ops[0]);
4565   case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4566   case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4567   default: break;
4568   }
4569
4570   // Copy from an SDUse array into an SDValue array for use with
4571   // the regular getNode logic.
4572   SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4573   return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4574 }
4575
4576 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4577                               const SDValue *Ops, unsigned NumOps) {
4578   switch (NumOps) {
4579   case 0: return getNode(Opcode, DL, VT);
4580   case 1: return getNode(Opcode, DL, VT, Ops[0]);
4581   case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4582   case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4583   default: break;
4584   }
4585
4586   switch (Opcode) {
4587   default: break;
4588   case ISD::SELECT_CC: {
4589     assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4590     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4591            "LHS and RHS of condition must have same type!");
4592     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4593            "True and False arms of SelectCC must have same type!");
4594     assert(Ops[2].getValueType() == VT &&
4595            "select_cc node must be of same type as true and false value!");
4596     break;
4597   }
4598   case ISD::BR_CC: {
4599     assert(NumOps == 5 && "BR_CC takes 5 operands!");
4600     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4601            "LHS/RHS of comparison should match types!");
4602     break;
4603   }
4604   }
4605
4606   // Memoize nodes.
4607   SDNode *N;
4608   SDVTList VTs = getVTList(VT);
4609
4610   if (VT != MVT::Glue) {
4611     FoldingSetNodeID ID;
4612     AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4613     void *IP = 0;
4614
4615     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4616       return SDValue(E, 0);
4617
4618     N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4619     CSEMap.InsertNode(N, IP);
4620   } else {
4621     N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4622   }
4623
4624   AllNodes.push_back(N);
4625 #ifndef NDEBUG
4626   VerifySDNode(N);
4627 #endif
4628   return SDValue(N, 0);
4629 }
4630
4631 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4632                               const std::vector<EVT> &ResultTys,
4633                               const SDValue *Ops, unsigned NumOps) {
4634   return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4635                  Ops, NumOps);
4636 }
4637
4638 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4639                               const EVT *VTs, unsigned NumVTs,
4640                               const SDValue *Ops, unsigned NumOps) {
4641   if (NumVTs == 1)
4642     return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4643   return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4644 }
4645
4646 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4647                               const SDValue *Ops, unsigned NumOps) {
4648   if (VTList.NumVTs == 1)
4649     return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4650
4651 #if 0
4652   switch (Opcode) {
4653   // FIXME: figure out how to safely handle things like
4654   // int foo(int x) { return 1 << (x & 255); }
4655   // int bar() { return foo(256); }
4656   case ISD::SRA_PARTS:
4657   case ISD::SRL_PARTS:
4658   case ISD::SHL_PARTS:
4659     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4660         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4661       return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4662     else if (N3.getOpcode() == ISD::AND)
4663       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4664         // If the and is only masking out bits that cannot effect the shift,
4665         // eliminate the and.
4666         unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4667         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4668           return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4669       }
4670     break;
4671   }
4672 #endif
4673
4674   // Memoize the node unless it returns a flag.
4675   SDNode *N;
4676   if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4677     FoldingSetNodeID ID;
4678     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4679     void *IP = 0;
4680     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4681       return SDValue(E, 0);
4682
4683     if (NumOps == 1) {
4684       N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4685     } else if (NumOps == 2) {
4686       N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4687     } else if (NumOps == 3) {
4688       N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4689                                             Ops[2]);
4690     } else {
4691       N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4692     }
4693     CSEMap.InsertNode(N, IP);
4694   } else {
4695     if (NumOps == 1) {
4696       N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4697     } else if (NumOps == 2) {
4698       N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4699     } else if (NumOps == 3) {
4700       N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4701                                             Ops[2]);
4702     } else {
4703       N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4704     }
4705   }
4706   AllNodes.push_back(N);
4707 #ifndef NDEBUG
4708   VerifySDNode(N);
4709 #endif
4710   return SDValue(N, 0);
4711 }
4712
4713 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4714   return getNode(Opcode, DL, VTList, 0, 0);
4715 }
4716
4717 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4718                               SDValue N1) {
4719   SDValue Ops[] = { N1 };
4720   return getNode(Opcode, DL, VTList, Ops, 1);
4721 }
4722
4723 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4724                               SDValue N1, SDValue N2) {
4725   SDValue Ops[] = { N1, N2 };
4726   return getNode(Opcode, DL, VTList, Ops, 2);
4727 }
4728
4729 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4730                               SDValue N1, SDValue N2, SDValue N3) {
4731   SDValue Ops[] = { N1, N2, N3 };
4732   return getNode(Opcode, DL, VTList, Ops, 3);
4733 }
4734
4735 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4736                               SDValue N1, SDValue N2, SDValue N3,
4737                               SDValue N4) {
4738   SDValue Ops[] = { N1, N2, N3, N4 };
4739   return getNode(Opcode, DL, VTList, Ops, 4);
4740 }
4741
4742 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4743                               SDValue N1, SDValue N2, SDValue N3,
4744                               SDValue N4, SDValue N5) {
4745   SDValue Ops[] = { N1, N2, N3, N4, N5 };
4746   return getNode(Opcode, DL, VTList, Ops, 5);
4747 }
4748
4749 SDVTList SelectionDAG::getVTList(EVT VT) {
4750   return makeVTList(SDNode::getValueTypeList(VT), 1);
4751 }
4752
4753 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4754   for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4755        E = VTList.rend(); I != E; ++I)
4756     if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4757       return *I;
4758
4759   EVT *Array = Allocator.Allocate<EVT>(2);
4760   Array[0] = VT1;
4761   Array[1] = VT2;
4762   SDVTList Result = makeVTList(Array, 2);
4763   VTList.push_back(Result);
4764   return Result;
4765 }
4766
4767 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4768   for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4769        E = VTList.rend(); I != E; ++I)
4770     if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4771                           I->VTs[2] == VT3)
4772       return *I;
4773
4774   EVT *Array = Allocator.Allocate<EVT>(3);
4775   Array[0] = VT1;
4776   Array[1] = VT2;
4777   Array[2] = VT3;
4778   SDVTList Result = makeVTList(Array, 3);
4779   VTList.push_back(Result);
4780   return Result;
4781 }
4782
4783 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4784   for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4785        E = VTList.rend(); I != E; ++I)
4786     if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4787                           I->VTs[2] == VT3 && I->VTs[3] == VT4)
4788       return *I;
4789
4790   EVT *Array = Allocator.Allocate<EVT>(4);
4791   Array[0] = VT1;
4792   Array[1] = VT2;
4793   Array[2] = VT3;
4794   Array[3] = VT4;
4795   SDVTList Result = makeVTList(Array, 4);
4796   VTList.push_back(Result);
4797   return Result;
4798 }
4799
4800 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4801   switch (NumVTs) {
4802     case 0: llvm_unreachable("Cannot have nodes without results!");
4803     case 1: return getVTList(VTs[0]);
4804     case 2: return getVTList(VTs[0], VTs[1]);
4805     case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4806     case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4807     default: break;
4808   }
4809
4810   for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4811        E = VTList.rend(); I != E; ++I) {
4812     if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4813       continue;
4814
4815     if (std::equal(&VTs[2], &VTs[NumVTs], &I->VTs[2]))
4816       return *I;
4817   }
4818
4819   EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4820   std::copy(VTs, VTs+NumVTs, Array);
4821   SDVTList Result = makeVTList(Array, NumVTs);
4822   VTList.push_back(Result);
4823   return Result;
4824 }
4825
4826
4827 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4828 /// specified operands.  If the resultant node already exists in the DAG,
4829 /// this does not modify the specified node, instead it returns the node that
4830 /// already exists.  If the resultant node does not exist in the DAG, the
4831 /// input node is returned.  As a degenerate case, if you specify the same
4832 /// input operands as the node already has, the input node is returned.
4833 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4834   assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4835
4836   // Check to see if there is no change.
4837   if (Op == N->getOperand(0)) return N;
4838
4839   // See if the modified node already exists.
4840   void *InsertPos = 0;
4841   if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4842     return Existing;
4843
4844   // Nope it doesn't.  Remove the node from its current place in the maps.
4845   if (InsertPos)
4846     if (!RemoveNodeFromCSEMaps(N))
4847       InsertPos = 0;
4848
4849   // Now we update the operands.
4850   N->OperandList[0].set(Op);
4851
4852   // If this gets put into a CSE map, add it.
4853   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4854   return N;
4855 }
4856
4857 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4858   assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4859
4860   // Check to see if there is no change.
4861   if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4862     return N;   // No operands changed, just return the input node.
4863
4864   // See if the modified node already exists.
4865   void *InsertPos = 0;
4866   if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4867     return Existing;
4868
4869   // Nope it doesn't.  Remove the node from its current place in the maps.
4870   if (InsertPos)
4871     if (!RemoveNodeFromCSEMaps(N))
4872       InsertPos = 0;
4873
4874   // Now we update the operands.
4875   if (N->OperandList[0] != Op1)
4876     N->OperandList[0].set(Op1);
4877   if (N->OperandList[1] != Op2)
4878     N->OperandList[1].set(Op2);
4879
4880   // If this gets put into a CSE map, add it.
4881   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4882   return N;
4883 }
4884
4885 SDNode *SelectionDAG::
4886 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4887   SDValue Ops[] = { Op1, Op2, Op3 };
4888   return UpdateNodeOperands(N, Ops, 3);
4889 }
4890
4891 SDNode *SelectionDAG::
4892 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4893                    SDValue Op3, SDValue Op4) {
4894   SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4895   return UpdateNodeOperands(N, Ops, 4);
4896 }
4897
4898 SDNode *SelectionDAG::
4899 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4900                    SDValue Op3, SDValue Op4, SDValue Op5) {
4901   SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4902   return UpdateNodeOperands(N, Ops, 5);
4903 }
4904
4905 SDNode *SelectionDAG::
4906 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4907   assert(N->getNumOperands() == NumOps &&
4908          "Update with wrong number of operands");
4909
4910   // Check to see if there is no change.
4911   bool AnyChange = false;
4912   for (unsigned i = 0; i != NumOps; ++i) {
4913     if (Ops[i] != N->getOperand(i)) {
4914       AnyChange = true;
4915       break;
4916     }
4917   }
4918
4919   // No operands changed, just return the input node.
4920   if (!AnyChange) return N;
4921
4922   // See if the modified node already exists.
4923   void *InsertPos = 0;
4924   if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4925     return Existing;
4926
4927   // Nope it doesn't.  Remove the node from its current place in the maps.
4928   if (InsertPos)
4929     if (!RemoveNodeFromCSEMaps(N))
4930       InsertPos = 0;
4931
4932   // Now we update the operands.
4933   for (unsigned i = 0; i != NumOps; ++i)
4934     if (N->OperandList[i] != Ops[i])
4935       N->OperandList[i].set(Ops[i]);
4936
4937   // If this gets put into a CSE map, add it.
4938   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4939   return N;
4940 }
4941
4942 /// DropOperands - Release the operands and set this node to have
4943 /// zero operands.
4944 void SDNode::DropOperands() {
4945   // Unlike the code in MorphNodeTo that does this, we don't need to
4946   // watch for dead nodes here.
4947   for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4948     SDUse &Use = *I++;
4949     Use.set(SDValue());
4950   }
4951 }
4952
4953 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4954 /// machine opcode.
4955 ///
4956 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4957                                    EVT VT) {
4958   SDVTList VTs = getVTList(VT);
4959   return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4960 }
4961
4962 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4963                                    EVT VT, SDValue Op1) {
4964   SDVTList VTs = getVTList(VT);
4965   SDValue Ops[] = { Op1 };
4966   return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4967 }
4968
4969 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4970                                    EVT VT, SDValue Op1,
4971                                    SDValue Op2) {
4972   SDVTList VTs = getVTList(VT);
4973   SDValue Ops[] = { Op1, Op2 };
4974   return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4975 }
4976
4977 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4978                                    EVT VT, SDValue Op1,
4979                                    SDValue Op2, SDValue Op3) {
4980   SDVTList VTs = getVTList(VT);
4981   SDValue Ops[] = { Op1, Op2, Op3 };
4982   return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4983 }
4984
4985 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4986                                    EVT VT, const SDValue *Ops,
4987                                    unsigned NumOps) {
4988   SDVTList VTs = getVTList(VT);
4989   return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4990 }
4991
4992 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4993                                    EVT VT1, EVT VT2, const SDValue *Ops,
4994                                    unsigned NumOps) {
4995   SDVTList VTs = getVTList(VT1, VT2);
4996   return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4997 }
4998
4999 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5000                                    EVT VT1, EVT VT2) {
5001   SDVTList VTs = getVTList(VT1, VT2);
5002   return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5003 }
5004
5005 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5006                                    EVT VT1, EVT VT2, EVT VT3,
5007                                    const SDValue *Ops, unsigned NumOps) {
5008   SDVTList VTs = getVTList(VT1, VT2, VT3);
5009   return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5010 }
5011
5012 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5013                                    EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5014                                    const SDValue *Ops, unsigned NumOps) {
5015   SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5016   return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5017 }
5018
5019 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5020                                    EVT VT1, EVT VT2,
5021                                    SDValue Op1) {
5022   SDVTList VTs = getVTList(VT1, VT2);
5023   SDValue Ops[] = { Op1 };
5024   return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5025 }
5026
5027 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5028                                    EVT VT1, EVT VT2,
5029                                    SDValue Op1, SDValue Op2) {
5030   SDVTList VTs = getVTList(VT1, VT2);
5031   SDValue Ops[] = { Op1, Op2 };
5032   return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5033 }
5034
5035 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5036                                    EVT VT1, EVT VT2,
5037                                    SDValue Op1, SDValue Op2,
5038                                    SDValue Op3) {
5039   SDVTList VTs = getVTList(VT1, VT2);
5040   SDValue Ops[] = { Op1, Op2, Op3 };
5041   return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5042 }
5043
5044 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5045                                    EVT VT1, EVT VT2, EVT VT3,
5046                                    SDValue Op1, SDValue Op2,
5047                                    SDValue Op3) {
5048   SDVTList VTs = getVTList(VT1, VT2, VT3);
5049   SDValue Ops[] = { Op1, Op2, Op3 };
5050   return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5051 }
5052
5053 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5054                                    SDVTList VTs, const SDValue *Ops,
5055                                    unsigned NumOps) {
5056   N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5057   // Reset the NodeID to -1.
5058   N->setNodeId(-1);
5059   return N;
5060 }
5061
5062 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
5063 /// the line number information on the merged node since it is not possible to
5064 /// preserve the information that operation is associated with multiple lines.
5065 /// This will make the debugger working better at -O0, were there is a higher
5066 /// probability having other instructions associated with that line.
5067 ///
5068 SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) {
5069   DebugLoc NLoc = N->getDebugLoc();
5070   if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) {
5071     N->setDebugLoc(DebugLoc());
5072   }
5073   return N;
5074 }
5075
5076 /// MorphNodeTo - This *mutates* the specified node to have the specified
5077 /// return type, opcode, and operands.
5078 ///
5079 /// Note that MorphNodeTo returns the resultant node.  If there is already a
5080 /// node of the specified opcode and operands, it returns that node instead of
5081 /// the current one.  Note that the DebugLoc need not be the same.
5082 ///
5083 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5084 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5085 /// node, and because it doesn't require CSE recalculation for any of
5086 /// the node's users.
5087 ///
5088 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5089                                   SDVTList VTs, const SDValue *Ops,
5090                                   unsigned NumOps) {
5091   // If an identical node already exists, use it.
5092   void *IP = 0;
5093   if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5094     FoldingSetNodeID ID;
5095     AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5096     if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5097       return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc());
5098   }
5099
5100   if (!RemoveNodeFromCSEMaps(N))
5101     IP = 0;
5102
5103   // Start the morphing.
5104   N->NodeType = Opc;
5105   N->ValueList = VTs.VTs;
5106   N->NumValues = VTs.NumVTs;
5107
5108   // Clear the operands list, updating used nodes to remove this from their
5109   // use list.  Keep track of any operands that become dead as a result.
5110   SmallPtrSet<SDNode*, 16> DeadNodeSet;
5111   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5112     SDUse &Use = *I++;
5113     SDNode *Used = Use.getNode();
5114     Use.set(SDValue());
5115     if (Used->use_empty())
5116       DeadNodeSet.insert(Used);
5117   }
5118
5119   if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5120     // Initialize the memory references information.
5121     MN->setMemRefs(0, 0);
5122     // If NumOps is larger than the # of operands we can have in a
5123     // MachineSDNode, reallocate the operand list.
5124     if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5125       if (MN->OperandsNeedDelete)
5126         delete[] MN->OperandList;
5127       if (NumOps > array_lengthof(MN->LocalOperands))
5128         // We're creating a final node that will live unmorphed for the
5129         // remainder of the current SelectionDAG iteration, so we can allocate
5130         // the operands directly out of a pool with no recycling metadata.
5131         MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5132                          Ops, NumOps);
5133       else
5134         MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5135       MN->OperandsNeedDelete = false;
5136     } else
5137       MN->InitOperands(MN->OperandList, Ops, NumOps);
5138   } else {
5139     // If NumOps is larger than the # of operands we currently have, reallocate
5140     // the operand list.
5141     if (NumOps > N->NumOperands) {
5142       if (N->OperandsNeedDelete)
5143         delete[] N->OperandList;
5144       N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5145       N->OperandsNeedDelete = true;
5146     } else
5147       N->InitOperands(N->OperandList, Ops, NumOps);
5148   }
5149
5150   // Delete any nodes that are still dead after adding the uses for the
5151   // new operands.
5152   if (!DeadNodeSet.empty()) {
5153     SmallVector<SDNode *, 16> DeadNodes;
5154     for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5155          E = DeadNodeSet.end(); I != E; ++I)
5156       if ((*I)->use_empty())
5157         DeadNodes.push_back(*I);
5158     RemoveDeadNodes(DeadNodes);
5159   }
5160
5161   if (IP)
5162     CSEMap.InsertNode(N, IP);   // Memoize the new node.
5163   return N;
5164 }
5165
5166
5167 /// getMachineNode - These are used for target selectors to create a new node
5168 /// with specified return type(s), MachineInstr opcode, and operands.
5169 ///
5170 /// Note that getMachineNode returns the resultant node.  If there is already a
5171 /// node of the specified opcode and operands, it returns that node instead of
5172 /// the current one.
5173 MachineSDNode *
5174 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5175   SDVTList VTs = getVTList(VT);
5176   return getMachineNode(Opcode, dl, VTs, 0, 0);
5177 }
5178
5179 MachineSDNode *
5180 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5181   SDVTList VTs = getVTList(VT);
5182   SDValue Ops[] = { Op1 };
5183   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5184 }
5185
5186 MachineSDNode *
5187 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5188                              SDValue Op1, SDValue Op2) {
5189   SDVTList VTs = getVTList(VT);
5190   SDValue Ops[] = { Op1, Op2 };
5191   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5192 }
5193
5194 MachineSDNode *
5195 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5196                              SDValue Op1, SDValue Op2, SDValue Op3) {
5197   SDVTList VTs = getVTList(VT);
5198   SDValue Ops[] = { Op1, Op2, Op3 };
5199   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5200 }
5201
5202 MachineSDNode *
5203 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5204                              const SDValue *Ops, unsigned NumOps) {
5205   SDVTList VTs = getVTList(VT);
5206   return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5207 }
5208
5209 MachineSDNode *
5210 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5211   SDVTList VTs = getVTList(VT1, VT2);
5212   return getMachineNode(Opcode, dl, VTs, 0, 0);
5213 }
5214
5215 MachineSDNode *
5216 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5217                              EVT VT1, EVT VT2, SDValue Op1) {
5218   SDVTList VTs = getVTList(VT1, VT2);
5219   SDValue Ops[] = { Op1 };
5220   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5221 }
5222
5223 MachineSDNode *
5224 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5225                              EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5226   SDVTList VTs = getVTList(VT1, VT2);
5227   SDValue Ops[] = { Op1, Op2 };
5228   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5229 }
5230
5231 MachineSDNode *
5232 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5233                              EVT VT1, EVT VT2, SDValue Op1,
5234                              SDValue Op2, SDValue Op3) {
5235   SDVTList VTs = getVTList(VT1, VT2);
5236   SDValue Ops[] = { Op1, Op2, Op3 };
5237   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5238 }
5239
5240 MachineSDNode *
5241 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5242                              EVT VT1, EVT VT2,
5243                              const SDValue *Ops, unsigned NumOps) {
5244   SDVTList VTs = getVTList(VT1, VT2);
5245   return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5246 }
5247
5248 MachineSDNode *
5249 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5250                              EVT VT1, EVT VT2, EVT VT3,
5251                              SDValue Op1, SDValue Op2) {
5252   SDVTList VTs = getVTList(VT1, VT2, VT3);
5253   SDValue Ops[] = { Op1, Op2 };
5254   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5255 }
5256
5257 MachineSDNode *
5258 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5259                              EVT VT1, EVT VT2, EVT VT3,
5260                              SDValue Op1, SDValue Op2, SDValue Op3) {
5261   SDVTList VTs = getVTList(VT1, VT2, VT3);
5262   SDValue Ops[] = { Op1, Op2, Op3 };
5263   return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5264 }
5265
5266 MachineSDNode *
5267 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5268                              EVT VT1, EVT VT2, EVT VT3,
5269                              const SDValue *Ops, unsigned NumOps) {
5270   SDVTList VTs = getVTList(VT1, VT2, VT3);
5271   return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5272 }
5273
5274 MachineSDNode *
5275 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5276                              EVT VT2, EVT VT3, EVT VT4,
5277                              const SDValue *Ops, unsigned NumOps) {
5278   SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5279   return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5280 }
5281
5282 MachineSDNode *
5283 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5284                              const std::vector<EVT> &ResultTys,
5285                              const SDValue *Ops, unsigned NumOps) {
5286   SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5287   return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5288 }
5289
5290 MachineSDNode *
5291 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5292                              const SDValue *Ops, unsigned NumOps) {
5293   bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5294   MachineSDNode *N;
5295   void *IP = 0;
5296
5297   if (DoCSE) {
5298     FoldingSetNodeID ID;
5299     AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5300     IP = 0;
5301     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5302       return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL));
5303     }
5304   }
5305
5306   // Allocate a new MachineSDNode.
5307   N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5308
5309   // Initialize the operands list.
5310   if (NumOps > array_lengthof(N->LocalOperands))
5311     // We're creating a final node that will live unmorphed for the
5312     // remainder of the current SelectionDAG iteration, so we can allocate
5313     // the operands directly out of a pool with no recycling metadata.
5314     N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5315                     Ops, NumOps);
5316   else
5317     N->InitOperands(N->LocalOperands, Ops, NumOps);
5318   N->OperandsNeedDelete = false;
5319
5320   if (DoCSE)
5321     CSEMap.InsertNode(N, IP);
5322
5323   AllNodes.push_back(N);
5324 #ifndef NDEBUG
5325   VerifyMachineNode(N);
5326 #endif
5327   return N;
5328 }
5329
5330 /// getTargetExtractSubreg - A convenience function for creating
5331 /// TargetOpcode::EXTRACT_SUBREG nodes.
5332 SDValue
5333 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5334                                      SDValue Operand) {
5335   SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5336   SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5337                                   VT, Operand, SRIdxVal);
5338   return SDValue(Subreg, 0);
5339 }
5340
5341 /// getTargetInsertSubreg - A convenience function for creating
5342 /// TargetOpcode::INSERT_SUBREG nodes.
5343 SDValue
5344 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5345                                     SDValue Operand, SDValue Subreg) {
5346   SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5347   SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5348                                   VT, Operand, Subreg, SRIdxVal);
5349   return SDValue(Result, 0);
5350 }
5351
5352 /// getNodeIfExists - Get the specified node if it's already available, or
5353 /// else return NULL.
5354 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5355                                       const SDValue *Ops, unsigned NumOps) {
5356   if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5357     FoldingSetNodeID ID;
5358     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5359     void *IP = 0;
5360     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5361       return E;
5362   }
5363   return NULL;
5364 }
5365
5366 /// getDbgValue - Creates a SDDbgValue node.
5367 ///
5368 SDDbgValue *
5369 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5370                           DebugLoc DL, unsigned O) {
5371   return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5372 }
5373
5374 SDDbgValue *
5375 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5376                           DebugLoc DL, unsigned O) {
5377   return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5378 }
5379
5380 SDDbgValue *
5381 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5382                           DebugLoc DL, unsigned O) {
5383   return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5384 }
5385
5386 namespace {
5387
5388 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5389 /// pointed to by a use iterator is deleted, increment the use iterator
5390 /// so that it doesn't dangle.
5391 ///
5392 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5393   SDNode::use_iterator &UI;
5394   SDNode::use_iterator &UE;
5395
5396   virtual void NodeDeleted(SDNode *N, SDNode *E) {
5397     // Increment the iterator as needed.
5398     while (UI != UE && N == *UI)
5399       ++UI;
5400   }
5401
5402 public:
5403   RAUWUpdateListener(SelectionDAG &d,
5404                      SDNode::use_iterator &ui,
5405                      SDNode::use_iterator &ue)
5406     : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5407 };
5408
5409 }
5410
5411 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5412 /// This can cause recursive merging of nodes in the DAG.
5413 ///
5414 /// This version assumes From has a single result value.
5415 ///
5416 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5417   SDNode *From = FromN.getNode();
5418   assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5419          "Cannot replace with this method!");
5420   assert(From != To.getNode() && "Cannot replace uses of with self");
5421
5422   // Iterate over all the existing uses of From. New uses will be added
5423   // to the beginning of the use list, which we avoid visiting.
5424   // This specifically avoids visiting uses of From that arise while the
5425   // replacement is happening, because any such uses would be the result
5426   // of CSE: If an existing node looks like From after one of its operands
5427   // is replaced by To, we don't want to replace of all its users with To
5428   // too. See PR3018 for more info.
5429   SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5430   RAUWUpdateListener Listener(*this, UI, UE);
5431   while (UI != UE) {
5432     SDNode *User = *UI;
5433
5434     // This node is about to morph, remove its old self from the CSE maps.
5435     RemoveNodeFromCSEMaps(User);
5436
5437     // A user can appear in a use list multiple times, and when this
5438     // happens the uses are usually next to each other in the list.
5439     // To help reduce the number of CSE recomputations, process all
5440     // the uses of this user that we can find this way.
5441     do {
5442       SDUse &Use = UI.getUse();
5443       ++UI;
5444       Use.set(To);
5445     } while (UI != UE && *UI == User);
5446
5447     // Now that we have modified User, add it back to the CSE maps.  If it
5448     // already exists there, recursively merge the results together.
5449     AddModifiedNodeToCSEMaps(User);
5450   }
5451
5452   // If we just RAUW'd the root, take note.
5453   if (FromN == getRoot())
5454     setRoot(To);
5455 }
5456
5457 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5458 /// This can cause recursive merging of nodes in the DAG.
5459 ///
5460 /// This version assumes that for each value of From, there is a
5461 /// corresponding value in To in the same position with the same type.
5462 ///
5463 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5464 #ifndef NDEBUG
5465   for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5466     assert((!From->hasAnyUseOfValue(i) ||
5467             From->getValueType(i) == To->getValueType(i)) &&
5468            "Cannot use this version of ReplaceAllUsesWith!");
5469 #endif
5470
5471   // Handle the trivial case.
5472   if (From == To)
5473     return;
5474
5475   // Iterate over just the existing users of From. See the comments in
5476   // the ReplaceAllUsesWith above.
5477   SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5478   RAUWUpdateListener Listener(*this, UI, UE);
5479   while (UI != UE) {
5480     SDNode *User = *UI;
5481
5482     // This node is about to morph, remove its old self from the CSE maps.
5483     RemoveNodeFromCSEMaps(User);
5484
5485     // A user can appear in a use list multiple times, and when this
5486     // happens the uses are usually next to each other in the list.
5487     // To help reduce the number of CSE recomputations, process all
5488     // the uses of this user that we can find this way.
5489     do {
5490       SDUse &Use = UI.getUse();
5491       ++UI;
5492       Use.setNode(To);
5493     } while (UI != UE && *UI == User);
5494
5495     // Now that we have modified User, add it back to the CSE maps.  If it
5496     // already exists there, recursively merge the results together.
5497     AddModifiedNodeToCSEMaps(User);
5498   }
5499
5500   // If we just RAUW'd the root, take note.
5501   if (From == getRoot().getNode())
5502     setRoot(SDValue(To, getRoot().getResNo()));
5503 }
5504
5505 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5506 /// This can cause recursive merging of nodes in the DAG.
5507 ///
5508 /// This version can replace From with any result values.  To must match the
5509 /// number and types of values returned by From.
5510 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5511   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
5512     return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5513
5514   // Iterate over just the existing users of From. See the comments in
5515   // the ReplaceAllUsesWith above.
5516   SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5517   RAUWUpdateListener Listener(*this, UI, UE);
5518   while (UI != UE) {
5519     SDNode *User = *UI;
5520
5521     // This node is about to morph, remove its old self from the CSE maps.
5522     RemoveNodeFromCSEMaps(User);
5523
5524     // A user can appear in a use list multiple times, and when this
5525     // happens the uses are usually next to each other in the list.
5526     // To help reduce the number of CSE recomputations, process all
5527     // the uses of this user that we can find this way.
5528     do {
5529       SDUse &Use = UI.getUse();
5530       const SDValue &ToOp = To[Use.getResNo()];
5531       ++UI;
5532       Use.set(ToOp);
5533     } while (UI != UE && *UI == User);
5534
5535     // Now that we have modified User, add it back to the CSE maps.  If it
5536     // already exists there, recursively merge the results together.
5537     AddModifiedNodeToCSEMaps(User);
5538   }
5539
5540   // If we just RAUW'd the root, take note.
5541   if (From == getRoot().getNode())
5542     setRoot(SDValue(To[getRoot().getResNo()]));
5543 }
5544
5545 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5546 /// uses of other values produced by From.getNode() alone.  The Deleted
5547 /// vector is handled the same way as for ReplaceAllUsesWith.
5548 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5549   // Handle the really simple, really trivial case efficiently.
5550   if (From == To) return;
5551
5552   // Handle the simple, trivial, case efficiently.
5553   if (From.getNode()->getNumValues() == 1) {
5554     ReplaceAllUsesWith(From, To);
5555     return;
5556   }
5557
5558   // Iterate over just the existing users of From. See the comments in
5559   // the ReplaceAllUsesWith above.
5560   SDNode::use_iterator UI = From.getNode()->use_begin(),
5561                        UE = From.getNode()->use_end();
5562   RAUWUpdateListener Listener(*this, UI, UE);
5563   while (UI != UE) {
5564     SDNode *User = *UI;
5565     bool UserRemovedFromCSEMaps = false;
5566
5567     // A user can appear in a use list multiple times, and when this
5568     // happens the uses are usually next to each other in the list.
5569     // To help reduce the number of CSE recomputations, process all
5570     // the uses of this user that we can find this way.
5571     do {
5572       SDUse &Use = UI.getUse();
5573
5574       // Skip uses of different values from the same node.
5575       if (Use.getResNo() != From.getResNo()) {
5576         ++UI;
5577         continue;
5578       }
5579
5580       // If this node hasn't been modified yet, it's still in the CSE maps,
5581       // so remove its old self from the CSE maps.
5582       if (!UserRemovedFromCSEMaps) {
5583         RemoveNodeFromCSEMaps(User);
5584         UserRemovedFromCSEMaps = true;
5585       }
5586
5587       ++UI;
5588       Use.set(To);
5589     } while (UI != UE && *UI == User);
5590
5591     // We are iterating over all uses of the From node, so if a use
5592     // doesn't use the specific value, no changes are made.
5593     if (!UserRemovedFromCSEMaps)
5594       continue;
5595
5596     // Now that we have modified User, add it back to the CSE maps.  If it
5597     // already exists there, recursively merge the results together.
5598     AddModifiedNodeToCSEMaps(User);
5599   }
5600
5601   // If we just RAUW'd the root, take note.
5602   if (From == getRoot())
5603     setRoot(To);
5604 }
5605
5606 namespace {
5607   /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5608   /// to record information about a use.
5609   struct UseMemo {
5610     SDNode *User;
5611     unsigned Index;
5612     SDUse *Use;
5613   };
5614
5615   /// operator< - Sort Memos by User.
5616   bool operator<(const UseMemo &L, const UseMemo &R) {
5617     return (intptr_t)L.User < (intptr_t)R.User;
5618   }
5619 }
5620
5621 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5622 /// uses of other values produced by From.getNode() alone.  The same value
5623 /// may appear in both the From and To list.  The Deleted vector is
5624 /// handled the same way as for ReplaceAllUsesWith.
5625 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5626                                               const SDValue *To,
5627                                               unsigned Num){
5628   // Handle the simple, trivial case efficiently.
5629   if (Num == 1)
5630     return ReplaceAllUsesOfValueWith(*From, *To);
5631
5632   // Read up all the uses and make records of them. This helps
5633   // processing new uses that are introduced during the
5634   // replacement process.
5635   SmallVector<UseMemo, 4> Uses;
5636   for (unsigned i = 0; i != Num; ++i) {
5637     unsigned FromResNo = From[i].getResNo();
5638     SDNode *FromNode = From[i].getNode();
5639     for (SDNode::use_iterator UI = FromNode->use_begin(),
5640          E = FromNode->use_end(); UI != E; ++UI) {
5641       SDUse &Use = UI.getUse();
5642       if (Use.getResNo() == FromResNo) {
5643         UseMemo Memo = { *UI, i, &Use };
5644         Uses.push_back(Memo);
5645       }
5646     }
5647   }
5648
5649   // Sort the uses, so that all the uses from a given User are together.
5650   std::sort(Uses.begin(), Uses.end());
5651
5652   for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5653        UseIndex != UseIndexEnd; ) {
5654     // We know that this user uses some value of From.  If it is the right
5655     // value, update it.
5656     SDNode *User = Uses[UseIndex].User;
5657
5658     // This node is about to morph, remove its old self from the CSE maps.
5659     RemoveNodeFromCSEMaps(User);
5660
5661     // The Uses array is sorted, so all the uses for a given User
5662     // are next to each other in the list.
5663     // To help reduce the number of CSE recomputations, process all
5664     // the uses of this user that we can find this way.
5665     do {
5666       unsigned i = Uses[UseIndex].Index;
5667       SDUse &Use = *Uses[UseIndex].Use;
5668       ++UseIndex;
5669
5670       Use.set(To[i]);
5671     } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5672
5673     // Now that we have modified User, add it back to the CSE maps.  If it
5674     // already exists there, recursively merge the results together.
5675     AddModifiedNodeToCSEMaps(User);
5676   }
5677 }
5678
5679 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5680 /// based on their topological order. It returns the maximum id and a vector
5681 /// of the SDNodes* in assigned order by reference.
5682 unsigned SelectionDAG::AssignTopologicalOrder() {
5683
5684   unsigned DAGSize = 0;
5685
5686   // SortedPos tracks the progress of the algorithm. Nodes before it are
5687   // sorted, nodes after it are unsorted. When the algorithm completes
5688   // it is at the end of the list.
5689   allnodes_iterator SortedPos = allnodes_begin();
5690
5691   // Visit all the nodes. Move nodes with no operands to the front of
5692   // the list immediately. Annotate nodes that do have operands with their
5693   // operand count. Before we do this, the Node Id fields of the nodes
5694   // may contain arbitrary values. After, the Node Id fields for nodes
5695   // before SortedPos will contain the topological sort index, and the
5696   // Node Id fields for nodes At SortedPos and after will contain the
5697   // count of outstanding operands.
5698   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5699     SDNode *N = I++;
5700     checkForCycles(N);
5701     unsigned Degree = N->getNumOperands();
5702     if (Degree == 0) {
5703       // A node with no uses, add it to the result array immediately.
5704       N->setNodeId(DAGSize++);
5705       allnodes_iterator Q = N;
5706       if (Q != SortedPos)
5707         SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5708       assert(SortedPos != AllNodes.end() && "Overran node list");
5709       ++SortedPos;
5710     } else {
5711       // Temporarily use the Node Id as scratch space for the degree count.
5712       N->setNodeId(Degree);
5713     }
5714   }
5715
5716   // Visit all the nodes. As we iterate, move nodes into sorted order,
5717   // such that by the time the end is reached all nodes will be sorted.
5718   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5719     SDNode *N = I;
5720     checkForCycles(N);
5721     // N is in sorted position, so all its uses have one less operand
5722     // that needs to be sorted.
5723     for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5724          UI != UE; ++UI) {
5725       SDNode *P = *UI;
5726       unsigned Degree = P->getNodeId();
5727       assert(Degree != 0 && "Invalid node degree");
5728       --Degree;
5729       if (Degree == 0) {
5730         // All of P's operands are sorted, so P may sorted now.
5731         P->setNodeId(DAGSize++);
5732         if (P != SortedPos)
5733           SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5734         assert(SortedPos != AllNodes.end() && "Overran node list");
5735         ++SortedPos;
5736       } else {
5737         // Update P's outstanding operand count.
5738         P->setNodeId(Degree);
5739       }
5740     }
5741     if (I == SortedPos) {
5742 #ifndef NDEBUG
5743       SDNode *S = ++I;
5744       dbgs() << "Overran sorted position:\n";
5745       S->dumprFull();
5746 #endif
5747       llvm_unreachable(0);
5748     }
5749   }
5750
5751   assert(SortedPos == AllNodes.end() &&
5752          "Topological sort incomplete!");
5753   assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5754          "First node in topological sort is not the entry token!");
5755   assert(AllNodes.front().getNodeId() == 0 &&
5756          "First node in topological sort has non-zero id!");
5757   assert(AllNodes.front().getNumOperands() == 0 &&
5758          "First node in topological sort has operands!");
5759   assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5760          "Last node in topologic sort has unexpected id!");
5761   assert(AllNodes.back().use_empty() &&
5762          "Last node in topologic sort has users!");
5763   assert(DAGSize == allnodes_size() && "Node count mismatch!");
5764   return DAGSize;
5765 }
5766
5767 /// AssignOrdering - Assign an order to the SDNode.
5768 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5769   assert(SD && "Trying to assign an order to a null node!");
5770   Ordering->add(SD, Order);
5771 }
5772
5773 /// GetOrdering - Get the order for the SDNode.
5774 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5775   assert(SD && "Trying to get the order of a null node!");
5776   return Ordering->getOrder(SD);
5777 }
5778
5779 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5780 /// value is produced by SD.
5781 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5782   DbgInfo->add(DB, SD, isParameter);
5783   if (SD)
5784     SD->setHasDebugValue(true);
5785 }
5786
5787 /// TransferDbgValues - Transfer SDDbgValues.
5788 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5789   if (From == To || !From.getNode()->getHasDebugValue())
5790     return;
5791   SDNode *FromNode = From.getNode();
5792   SDNode *ToNode = To.getNode();
5793   ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5794   SmallVector<SDDbgValue *, 2> ClonedDVs;
5795   for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5796        I != E; ++I) {
5797     SDDbgValue *Dbg = *I;
5798     if (Dbg->getKind() == SDDbgValue::SDNODE) {
5799       SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5800                                       Dbg->getOffset(), Dbg->getDebugLoc(),
5801                                       Dbg->getOrder());
5802       ClonedDVs.push_back(Clone);
5803     }
5804   }
5805   for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5806          E = ClonedDVs.end(); I != E; ++I)
5807     AddDbgValue(*I, ToNode, false);
5808 }
5809
5810 //===----------------------------------------------------------------------===//
5811 //                              SDNode Class
5812 //===----------------------------------------------------------------------===//
5813
5814 HandleSDNode::~HandleSDNode() {
5815   DropOperands();
5816 }
5817
5818 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5819                                          const GlobalValue *GA,
5820                                          EVT VT, int64_t o, unsigned char TF)
5821   : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5822   TheGlobal = GA;
5823 }
5824
5825 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5826                      MachineMemOperand *mmo)
5827  : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5828   SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5829                                       MMO->isNonTemporal(), MMO->isInvariant());
5830   assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5831   assert(isNonTemporal() == MMO->isNonTemporal() &&
5832          "Non-temporal encoding error!");
5833   assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5834 }
5835
5836 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5837                      const SDValue *Ops, unsigned NumOps, EVT memvt,
5838                      MachineMemOperand *mmo)
5839    : SDNode(Opc, dl, VTs, Ops, NumOps),
5840      MemoryVT(memvt), MMO(mmo) {
5841   SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5842                                       MMO->isNonTemporal(), MMO->isInvariant());
5843   assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5844   assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5845 }
5846
5847 /// Profile - Gather unique data for the node.
5848 ///
5849 void SDNode::Profile(FoldingSetNodeID &ID) const {
5850   AddNodeIDNode(ID, this);
5851 }
5852
5853 namespace {
5854   struct EVTArray {
5855     std::vector<EVT> VTs;
5856
5857     EVTArray() {
5858       VTs.reserve(MVT::LAST_VALUETYPE);
5859       for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5860         VTs.push_back(MVT((MVT::SimpleValueType)i));
5861     }
5862   };
5863 }
5864
5865 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5866 static ManagedStatic<EVTArray> SimpleVTArray;
5867 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5868
5869 /// getValueTypeList - Return a pointer to the specified value type.
5870 ///
5871 const EVT *SDNode::getValueTypeList(EVT VT) {
5872   if (VT.isExtended()) {
5873     sys::SmartScopedLock<true> Lock(*VTMutex);
5874     return &(*EVTs->insert(VT).first);
5875   } else {
5876     assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5877            "Value type out of range!");
5878     return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5879   }
5880 }
5881
5882 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5883 /// indicated value.  This method ignores uses of other values defined by this
5884 /// operation.
5885 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5886   assert(Value < getNumValues() && "Bad value!");
5887
5888   // TODO: Only iterate over uses of a given value of the node
5889   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5890     if (UI.getUse().getResNo() == Value) {
5891       if (NUses == 0)
5892         return false;
5893       --NUses;
5894     }
5895   }
5896
5897   // Found exactly the right number of uses?
5898   return NUses == 0;
5899 }
5900
5901
5902 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5903 /// value. This method ignores uses of other values defined by this operation.
5904 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5905   assert(Value < getNumValues() && "Bad value!");
5906
5907   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5908     if (UI.getUse().getResNo() == Value)
5909       return true;
5910
5911   return false;
5912 }
5913
5914
5915 /// isOnlyUserOf - Return true if this node is the only use of N.
5916 ///
5917 bool SDNode::isOnlyUserOf(SDNode *N) const {
5918   bool Seen = false;
5919   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5920     SDNode *User = *I;
5921     if (User == this)
5922       Seen = true;
5923     else
5924       return false;
5925   }
5926
5927   return Seen;
5928 }
5929
5930 /// isOperand - Return true if this node is an operand of N.
5931 ///
5932 bool SDValue::isOperandOf(SDNode *N) const {
5933   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5934     if (*this == N->getOperand(i))
5935       return true;
5936   return false;
5937 }
5938
5939 bool SDNode::isOperandOf(SDNode *N) const {
5940   for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5941     if (this == N->OperandList[i].getNode())
5942       return true;
5943   return false;
5944 }
5945
5946 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5947 /// be a chain) reaches the specified operand without crossing any
5948 /// side-effecting instructions on any chain path.  In practice, this looks
5949 /// through token factors and non-volatile loads.  In order to remain efficient,
5950 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5951 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5952                                                unsigned Depth) const {
5953   if (*this == Dest) return true;
5954
5955   // Don't search too deeply, we just want to be able to see through
5956   // TokenFactor's etc.
5957   if (Depth == 0) return false;
5958
5959   // If this is a token factor, all inputs to the TF happen in parallel.  If any
5960   // of the operands of the TF does not reach dest, then we cannot do the xform.
5961   if (getOpcode() == ISD::TokenFactor) {
5962     for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5963       if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5964         return false;
5965     return true;
5966   }
5967
5968   // Loads don't have side effects, look through them.
5969   if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5970     if (!Ld->isVolatile())
5971       return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5972   }
5973   return false;
5974 }
5975
5976 /// hasPredecessor - Return true if N is a predecessor of this node.
5977 /// N is either an operand of this node, or can be reached by recursively
5978 /// traversing up the operands.
5979 /// NOTE: This is an expensive method. Use it carefully.
5980 bool SDNode::hasPredecessor(const SDNode *N) const {
5981   SmallPtrSet<const SDNode *, 32> Visited;
5982   SmallVector<const SDNode *, 16> Worklist;
5983   return hasPredecessorHelper(N, Visited, Worklist);
5984 }
5985
5986 bool SDNode::hasPredecessorHelper(const SDNode *N,
5987                                   SmallPtrSet<const SDNode *, 32> &Visited,
5988                                   SmallVector<const SDNode *, 16> &Worklist) const {
5989   if (Visited.empty()) {
5990     Worklist.push_back(this);
5991   } else {
5992     // Take a look in the visited set. If we've already encountered this node
5993     // we needn't search further.
5994     if (Visited.count(N))
5995       return true;
5996   }
5997
5998   // Haven't visited N yet. Continue the search.
5999   while (!Worklist.empty()) {
6000     const SDNode *M = Worklist.pop_back_val();
6001     for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6002       SDNode *Op = M->getOperand(i).getNode();
6003       if (Visited.insert(Op))
6004         Worklist.push_back(Op);
6005       if (Op == N)
6006         return true;
6007     }
6008   }
6009
6010   return false;
6011 }
6012
6013 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6014   assert(Num < NumOperands && "Invalid child # of SDNode!");
6015   return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6016 }
6017
6018 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6019   assert(N->getNumValues() == 1 &&
6020          "Can't unroll a vector with multiple results!");
6021
6022   EVT VT = N->getValueType(0);
6023   unsigned NE = VT.getVectorNumElements();
6024   EVT EltVT = VT.getVectorElementType();
6025   DebugLoc dl = N->getDebugLoc();
6026
6027   SmallVector<SDValue, 8> Scalars;
6028   SmallVector<SDValue, 4> Operands(N->getNumOperands());
6029
6030   // If ResNE is 0, fully unroll the vector op.
6031   if (ResNE == 0)
6032     ResNE = NE;
6033   else if (NE > ResNE)
6034     NE = ResNE;
6035
6036   unsigned i;
6037   for (i= 0; i != NE; ++i) {
6038     for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6039       SDValue Operand = N->getOperand(j);
6040       EVT OperandVT = Operand.getValueType();
6041       if (OperandVT.isVector()) {
6042         // A vector operand; extract a single element.
6043         EVT OperandEltVT = OperandVT.getVectorElementType();
6044         Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6045                               OperandEltVT,
6046                               Operand,
6047                               getConstant(i, TLI.getPointerTy()));
6048       } else {
6049         // A scalar operand; just use it as is.
6050         Operands[j] = Operand;
6051       }
6052     }
6053
6054     switch (N->getOpcode()) {
6055     default:
6056       Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6057                                 &Operands[0], Operands.size()));
6058       break;
6059     case ISD::VSELECT:
6060       Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6061                                 &Operands[0], Operands.size()));
6062       break;
6063     case ISD::SHL:
6064     case ISD::SRA:
6065     case ISD::SRL:
6066     case ISD::ROTL:
6067     case ISD::ROTR:
6068       Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6069                                 getShiftAmountOperand(Operands[0].getValueType(),
6070                                                       Operands[1])));
6071       break;
6072     case ISD::SIGN_EXTEND_INREG:
6073     case ISD::FP_ROUND_INREG: {
6074       EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6075       Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6076                                 Operands[0],
6077                                 getValueType(ExtVT)));
6078     }
6079     }
6080   }
6081
6082   for (; i < ResNE; ++i)
6083     Scalars.push_back(getUNDEF(EltVT));
6084
6085   return getNode(ISD::BUILD_VECTOR, dl,
6086                  EVT::getVectorVT(*getContext(), EltVT, ResNE),
6087                  &Scalars[0], Scalars.size());
6088 }
6089
6090
6091 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6092 /// location that is 'Dist' units away from the location that the 'Base' load
6093 /// is loading from.
6094 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6095                                      unsigned Bytes, int Dist) const {
6096   if (LD->getChain() != Base->getChain())
6097     return false;
6098   EVT VT = LD->getValueType(0);
6099   if (VT.getSizeInBits() / 8 != Bytes)
6100     return false;
6101
6102   SDValue Loc = LD->getOperand(1);
6103   SDValue BaseLoc = Base->getOperand(1);
6104   if (Loc.getOpcode() == ISD::FrameIndex) {
6105     if (BaseLoc.getOpcode() != ISD::FrameIndex)
6106       return false;
6107     const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6108     int FI  = cast<FrameIndexSDNode>(Loc)->getIndex();
6109     int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6110     int FS  = MFI->getObjectSize(FI);
6111     int BFS = MFI->getObjectSize(BFI);
6112     if (FS != BFS || FS != (int)Bytes) return false;
6113     return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6114   }
6115
6116   // Handle X+C
6117   if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6118       cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6119     return true;
6120
6121   const GlobalValue *GV1 = NULL;
6122   const GlobalValue *GV2 = NULL;
6123   int64_t Offset1 = 0;
6124   int64_t Offset2 = 0;
6125   bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6126   bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6127   if (isGA1 && isGA2 && GV1 == GV2)
6128     return Offset1 == (Offset2 + Dist*Bytes);
6129   return false;
6130 }
6131
6132
6133 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6134 /// it cannot be inferred.
6135 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6136   // If this is a GlobalAddress + cst, return the alignment.
6137   const GlobalValue *GV;
6138   int64_t GVOffset = 0;
6139   if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6140     unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6141     APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6142     llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6143                             TLI.getDataLayout());
6144     unsigned AlignBits = KnownZero.countTrailingOnes();
6145     unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6146     if (Align)
6147       return MinAlign(Align, GVOffset);
6148   }
6149
6150   // If this is a direct reference to a stack slot, use information about the
6151   // stack slot's alignment.
6152   int FrameIdx = 1 << 31;
6153   int64_t FrameOffset = 0;
6154   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6155     FrameIdx = FI->getIndex();
6156   } else if (isBaseWithConstantOffset(Ptr) &&
6157              isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6158     // Handle FI+Cst
6159     FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6160     FrameOffset = Ptr.getConstantOperandVal(1);
6161   }
6162
6163   if (FrameIdx != (1 << 31)) {
6164     const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6165     unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6166                                     FrameOffset);
6167     return FIInfoAlign;
6168   }
6169
6170   return 0;
6171 }
6172
6173 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6174 unsigned GlobalAddressSDNode::getAddressSpace() const {
6175   return getGlobal()->getType()->getAddressSpace();
6176 }
6177
6178
6179 Type *ConstantPoolSDNode::getType() const {
6180   if (isMachineConstantPoolEntry())
6181     return Val.MachineCPVal->getType();
6182   return Val.ConstVal->getType();
6183 }
6184
6185 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6186                                         APInt &SplatUndef,
6187                                         unsigned &SplatBitSize,
6188                                         bool &HasAnyUndefs,
6189                                         unsigned MinSplatBits,
6190                                         bool isBigEndian) {
6191   EVT VT = getValueType(0);
6192   assert(VT.isVector() && "Expected a vector type");
6193   unsigned sz = VT.getSizeInBits();
6194   if (MinSplatBits > sz)
6195     return false;
6196
6197   SplatValue = APInt(sz, 0);
6198   SplatUndef = APInt(sz, 0);
6199
6200   // Get the bits.  Bits with undefined values (when the corresponding element
6201   // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6202   // in SplatValue.  If any of the values are not constant, give up and return
6203   // false.
6204   unsigned int nOps = getNumOperands();
6205   assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6206   unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6207
6208   for (unsigned j = 0; j < nOps; ++j) {
6209     unsigned i = isBigEndian ? nOps-1-j : j;
6210     SDValue OpVal = getOperand(i);
6211     unsigned BitPos = j * EltBitSize;
6212
6213     if (OpVal.getOpcode() == ISD::UNDEF)
6214       SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6215     else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6216       SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6217                     zextOrTrunc(sz) << BitPos;
6218     else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6219       SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6220      else
6221       return false;
6222   }
6223
6224   // The build_vector is all constants or undefs.  Find the smallest element
6225   // size that splats the vector.
6226
6227   HasAnyUndefs = (SplatUndef != 0);
6228   while (sz > 8) {
6229
6230     unsigned HalfSize = sz / 2;
6231     APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6232     APInt LowValue = SplatValue.trunc(HalfSize);
6233     APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6234     APInt LowUndef = SplatUndef.trunc(HalfSize);
6235
6236     // If the two halves do not match (ignoring undef bits), stop here.
6237     if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6238         MinSplatBits > HalfSize)
6239       break;
6240
6241     SplatValue = HighValue | LowValue;
6242     SplatUndef = HighUndef & LowUndef;
6243
6244     sz = HalfSize;
6245   }
6246
6247   SplatBitSize = sz;
6248   return true;
6249 }
6250
6251 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6252   // Find the first non-undef value in the shuffle mask.
6253   unsigned i, e;
6254   for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6255     /* search */;
6256
6257   assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6258
6259   // Make sure all remaining elements are either undef or the same as the first
6260   // non-undef value.
6261   for (int Idx = Mask[i]; i != e; ++i)
6262     if (Mask[i] >= 0 && Mask[i] != Idx)
6263       return false;
6264   return true;
6265 }
6266
6267 #ifdef XDEBUG
6268 static void checkForCyclesHelper(const SDNode *N,
6269                                  SmallPtrSet<const SDNode*, 32> &Visited,
6270                                  SmallPtrSet<const SDNode*, 32> &Checked) {
6271   // If this node has already been checked, don't check it again.
6272   if (Checked.count(N))
6273     return;
6274
6275   // If a node has already been visited on this depth-first walk, reject it as
6276   // a cycle.
6277   if (!Visited.insert(N)) {
6278     dbgs() << "Offending node:\n";
6279     N->dumprFull();
6280     errs() << "Detected cycle in SelectionDAG\n";
6281     abort();
6282   }
6283
6284   for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6285     checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6286
6287   Checked.insert(N);
6288   Visited.erase(N);
6289 }
6290 #endif
6291
6292 void llvm::checkForCycles(const llvm::SDNode *N) {
6293 #ifdef XDEBUG
6294   assert(N && "Checking nonexistant SDNode");
6295   SmallPtrSet<const SDNode*, 32> visited;
6296   SmallPtrSet<const SDNode*, 32> checked;
6297   checkForCyclesHelper(N, visited, checked);
6298 #endif
6299 }
6300
6301 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6302   checkForCycles(DAG->getRoot().getNode());
6303 }