SelectionDAG.cpp revision 492f276cbc7be564c6af7b302618ee5436e4619c
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#include "llvm/CodeGen/SelectionDAG.h"
14#include "llvm/Constants.h"
15#include "llvm/Analysis/ValueTracking.h"
16#include "llvm/GlobalAlias.h"
17#include "llvm/GlobalVariable.h"
18#include "llvm/Intrinsics.h"
19#include "llvm/DerivedTypes.h"
20#include "llvm/Assembly/Writer.h"
21#include "llvm/CallingConv.h"
22#include "llvm/CodeGen/MachineBasicBlock.h"
23#include "llvm/CodeGen/MachineConstantPool.h"
24#include "llvm/CodeGen/MachineFrameInfo.h"
25#include "llvm/CodeGen/MachineModuleInfo.h"
26#include "llvm/CodeGen/PseudoSourceValue.h"
27#include "llvm/Support/MathExtras.h"
28#include "llvm/Target/TargetRegisterInfo.h"
29#include "llvm/Target/TargetData.h"
30#include "llvm/Target/TargetLowering.h"
31#include "llvm/Target/TargetInstrInfo.h"
32#include "llvm/Target/TargetMachine.h"
33#include "llvm/ADT/SetVector.h"
34#include "llvm/ADT/SmallPtrSet.h"
35#include "llvm/ADT/SmallSet.h"
36#include "llvm/ADT/SmallVector.h"
37#include "llvm/ADT/StringExtras.h"
38#include <algorithm>
39#include <cmath>
40using namespace llvm;
41
42/// makeVTList - Return an instance of the SDVTList struct initialized with the
43/// specified members.
44static SDVTList makeVTList(const MVT *VTs, unsigned NumVTs) {
45  SDVTList Res = {VTs, NumVTs};
46  return Res;
47}
48
49static const fltSemantics *MVTToAPFloatSemantics(MVT VT) {
50  switch (VT.getSimpleVT()) {
51  default: assert(0 && "Unknown FP format");
52  case MVT::f32:     return &APFloat::IEEEsingle;
53  case MVT::f64:     return &APFloat::IEEEdouble;
54  case MVT::f80:     return &APFloat::x87DoubleExtended;
55  case MVT::f128:    return &APFloat::IEEEquad;
56  case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
57  }
58}
59
60SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {}
61
62//===----------------------------------------------------------------------===//
63//                              ConstantFPSDNode Class
64//===----------------------------------------------------------------------===//
65
66/// isExactlyValue - We don't rely on operator== working on double values, as
67/// it returns true for things that are clearly not equal, like -0.0 and 0.0.
68/// As such, this method can be used to do an exact bit-for-bit comparison of
69/// two floating point values.
70bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
71  return Value.bitwiseIsEqual(V);
72}
73
74bool ConstantFPSDNode::isValueValidForType(MVT VT,
75                                           const APFloat& Val) {
76  assert(VT.isFloatingPoint() && "Can only convert between FP types");
77
78  // PPC long double cannot be converted to any other type.
79  if (VT == MVT::ppcf128 ||
80      &Val.getSemantics() == &APFloat::PPCDoubleDouble)
81    return false;
82
83  // convert modifies in place, so make a copy.
84  APFloat Val2 = APFloat(Val);
85  return Val2.convert(*MVTToAPFloatSemantics(VT),
86                      APFloat::rmNearestTiesToEven) == APFloat::opOK;
87}
88
89//===----------------------------------------------------------------------===//
90//                              ISD Namespace
91//===----------------------------------------------------------------------===//
92
93/// isBuildVectorAllOnes - Return true if the specified node is a
94/// BUILD_VECTOR where all of the elements are ~0 or undef.
95bool ISD::isBuildVectorAllOnes(const SDNode *N) {
96  // Look through a bit convert.
97  if (N->getOpcode() == ISD::BIT_CONVERT)
98    N = N->getOperand(0).Val;
99
100  if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
101
102  unsigned i = 0, e = N->getNumOperands();
103
104  // Skip over all of the undef values.
105  while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
106    ++i;
107
108  // Do not accept an all-undef vector.
109  if (i == e) return false;
110
111  // Do not accept build_vectors that aren't all constants or which have non-~0
112  // elements.
113  SDOperand NotZero = N->getOperand(i);
114  if (isa<ConstantSDNode>(NotZero)) {
115    if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
116      return false;
117  } else if (isa<ConstantFPSDNode>(NotZero)) {
118    if (!cast<ConstantFPSDNode>(NotZero)->getValueAPF().
119                convertToAPInt().isAllOnesValue())
120      return false;
121  } else
122    return false;
123
124  // Okay, we have at least one ~0 value, check to see if the rest match or are
125  // undefs.
126  for (++i; i != e; ++i)
127    if (N->getOperand(i) != NotZero &&
128        N->getOperand(i).getOpcode() != ISD::UNDEF)
129      return false;
130  return true;
131}
132
133
134/// isBuildVectorAllZeros - Return true if the specified node is a
135/// BUILD_VECTOR where all of the elements are 0 or undef.
136bool ISD::isBuildVectorAllZeros(const SDNode *N) {
137  // Look through a bit convert.
138  if (N->getOpcode() == ISD::BIT_CONVERT)
139    N = N->getOperand(0).Val;
140
141  if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
142
143  unsigned i = 0, e = N->getNumOperands();
144
145  // Skip over all of the undef values.
146  while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
147    ++i;
148
149  // Do not accept an all-undef vector.
150  if (i == e) return false;
151
152  // Do not accept build_vectors that aren't all constants or which have non-~0
153  // elements.
154  SDOperand Zero = N->getOperand(i);
155  if (isa<ConstantSDNode>(Zero)) {
156    if (!cast<ConstantSDNode>(Zero)->isNullValue())
157      return false;
158  } else if (isa<ConstantFPSDNode>(Zero)) {
159    if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
160      return false;
161  } else
162    return false;
163
164  // Okay, we have at least one ~0 value, check to see if the rest match or are
165  // undefs.
166  for (++i; i != e; ++i)
167    if (N->getOperand(i) != Zero &&
168        N->getOperand(i).getOpcode() != ISD::UNDEF)
169      return false;
170  return true;
171}
172
173/// isScalarToVector - Return true if the specified node is a
174/// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
175/// element is not an undef.
176bool ISD::isScalarToVector(const SDNode *N) {
177  if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
178    return true;
179
180  if (N->getOpcode() != ISD::BUILD_VECTOR)
181    return false;
182  if (N->getOperand(0).getOpcode() == ISD::UNDEF)
183    return false;
184  unsigned NumElems = N->getNumOperands();
185  for (unsigned i = 1; i < NumElems; ++i) {
186    SDOperand V = N->getOperand(i);
187    if (V.getOpcode() != ISD::UNDEF)
188      return false;
189  }
190  return true;
191}
192
193
194/// isDebugLabel - Return true if the specified node represents a debug
195/// label (i.e. ISD::DBG_LABEL or TargetInstrInfo::DBG_LABEL node).
196bool ISD::isDebugLabel(const SDNode *N) {
197  SDOperand Zero;
198  if (N->getOpcode() == ISD::DBG_LABEL)
199    return true;
200  if (N->isTargetOpcode() &&
201      N->getTargetOpcode() == TargetInstrInfo::DBG_LABEL)
202    return true;
203  return false;
204}
205
206/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
207/// when given the operation for (X op Y).
208ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
209  // To perform this operation, we just need to swap the L and G bits of the
210  // operation.
211  unsigned OldL = (Operation >> 2) & 1;
212  unsigned OldG = (Operation >> 1) & 1;
213  return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
214                       (OldL << 1) |       // New G bit
215                       (OldG << 2));        // New L bit.
216}
217
218/// getSetCCInverse - Return the operation corresponding to !(X op Y), where
219/// 'op' is a valid SetCC operation.
220ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
221  unsigned Operation = Op;
222  if (isInteger)
223    Operation ^= 7;   // Flip L, G, E bits, but not U.
224  else
225    Operation ^= 15;  // Flip all of the condition bits.
226  if (Operation > ISD::SETTRUE2)
227    Operation &= ~8;     // Don't let N and U bits get set.
228  return ISD::CondCode(Operation);
229}
230
231
232/// isSignedOp - For an integer comparison, return 1 if the comparison is a
233/// signed operation and 2 if the result is an unsigned comparison.  Return zero
234/// if the operation does not depend on the sign of the input (setne and seteq).
235static int isSignedOp(ISD::CondCode Opcode) {
236  switch (Opcode) {
237  default: assert(0 && "Illegal integer setcc operation!");
238  case ISD::SETEQ:
239  case ISD::SETNE: return 0;
240  case ISD::SETLT:
241  case ISD::SETLE:
242  case ISD::SETGT:
243  case ISD::SETGE: return 1;
244  case ISD::SETULT:
245  case ISD::SETULE:
246  case ISD::SETUGT:
247  case ISD::SETUGE: return 2;
248  }
249}
250
251/// getSetCCOrOperation - Return the result of a logical OR between different
252/// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
253/// returns SETCC_INVALID if it is not possible to represent the resultant
254/// comparison.
255ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
256                                       bool isInteger) {
257  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
258    // Cannot fold a signed integer setcc with an unsigned integer setcc.
259    return ISD::SETCC_INVALID;
260
261  unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
262
263  // If the N and U bits get set then the resultant comparison DOES suddenly
264  // care about orderedness, and is true when ordered.
265  if (Op > ISD::SETTRUE2)
266    Op &= ~16;     // Clear the U bit if the N bit is set.
267
268  // Canonicalize illegal integer setcc's.
269  if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
270    Op = ISD::SETNE;
271
272  return ISD::CondCode(Op);
273}
274
275/// getSetCCAndOperation - Return the result of a logical AND between different
276/// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
277/// function returns zero if it is not possible to represent the resultant
278/// comparison.
279ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
280                                        bool isInteger) {
281  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
282    // Cannot fold a signed setcc with an unsigned setcc.
283    return ISD::SETCC_INVALID;
284
285  // Combine all of the condition bits.
286  ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
287
288  // Canonicalize illegal integer setcc's.
289  if (isInteger) {
290    switch (Result) {
291    default: break;
292    case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
293    case ISD::SETOEQ:                                 // SETEQ  & SETU[LG]E
294    case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
295    case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
296    case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
297    }
298  }
299
300  return Result;
301}
302
303const TargetMachine &SelectionDAG::getTarget() const {
304  return TLI.getTargetMachine();
305}
306
307//===----------------------------------------------------------------------===//
308//                           SDNode Profile Support
309//===----------------------------------------------------------------------===//
310
311/// AddNodeIDOpcode - Add the node opcode to the NodeID data.
312///
313static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
314  ID.AddInteger(OpC);
315}
316
317/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
318/// solely with their pointer.
319static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
320  ID.AddPointer(VTList.VTs);
321}
322
323/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
324///
325static void AddNodeIDOperands(FoldingSetNodeID &ID,
326                              const SDOperand *Ops, unsigned NumOps) {
327  for (; NumOps; --NumOps, ++Ops) {
328    ID.AddPointer(Ops->Val);
329    ID.AddInteger(Ops->ResNo);
330  }
331}
332
333/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
334///
335static void AddNodeIDOperands(FoldingSetNodeID &ID,
336                              const SDUse *Ops, unsigned NumOps) {
337  for (; NumOps; --NumOps, ++Ops) {
338    ID.AddPointer(Ops->getSDOperand().Val);
339    ID.AddInteger(Ops->getSDOperand().ResNo);
340  }
341}
342
343static void AddNodeIDNode(FoldingSetNodeID &ID,
344                          unsigned short OpC, SDVTList VTList,
345                          const SDOperand *OpList, unsigned N) {
346  AddNodeIDOpcode(ID, OpC);
347  AddNodeIDValueTypes(ID, VTList);
348  AddNodeIDOperands(ID, OpList, N);
349}
350
351
352/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
353/// data.
354static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
355  AddNodeIDOpcode(ID, N->getOpcode());
356  // Add the return value info.
357  AddNodeIDValueTypes(ID, N->getVTList());
358  // Add the operand info.
359  AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
360
361  // Handle SDNode leafs with special info.
362  switch (N->getOpcode()) {
363  default: break;  // Normal nodes don't need extra info.
364  case ISD::ARG_FLAGS:
365    ID.AddInteger(cast<ARG_FLAGSSDNode>(N)->getArgFlags().getRawBits());
366    break;
367  case ISD::TargetConstant:
368  case ISD::Constant:
369    ID.Add(cast<ConstantSDNode>(N)->getAPIntValue());
370    break;
371  case ISD::TargetConstantFP:
372  case ISD::ConstantFP: {
373    ID.Add(cast<ConstantFPSDNode>(N)->getValueAPF());
374    break;
375  }
376  case ISD::TargetGlobalAddress:
377  case ISD::GlobalAddress:
378  case ISD::TargetGlobalTLSAddress:
379  case ISD::GlobalTLSAddress: {
380    GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
381    ID.AddPointer(GA->getGlobal());
382    ID.AddInteger(GA->getOffset());
383    break;
384  }
385  case ISD::BasicBlock:
386    ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
387    break;
388  case ISD::Register:
389    ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
390    break;
391  case ISD::DBG_STOPPOINT: {
392    const DbgStopPointSDNode *DSP = cast<DbgStopPointSDNode>(N);
393    ID.AddInteger(DSP->getLine());
394    ID.AddInteger(DSP->getColumn());
395    ID.AddPointer(DSP->getCompileUnit());
396    break;
397  }
398  case ISD::SRCVALUE:
399    ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
400    break;
401  case ISD::MEMOPERAND: {
402    const MachineMemOperand &MO = cast<MemOperandSDNode>(N)->MO;
403    ID.AddPointer(MO.getValue());
404    ID.AddInteger(MO.getFlags());
405    ID.AddInteger(MO.getOffset());
406    ID.AddInteger(MO.getSize());
407    ID.AddInteger(MO.getAlignment());
408    break;
409  }
410  case ISD::FrameIndex:
411  case ISD::TargetFrameIndex:
412    ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
413    break;
414  case ISD::JumpTable:
415  case ISD::TargetJumpTable:
416    ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
417    break;
418  case ISD::ConstantPool:
419  case ISD::TargetConstantPool: {
420    ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
421    ID.AddInteger(CP->getAlignment());
422    ID.AddInteger(CP->getOffset());
423    if (CP->isMachineConstantPoolEntry())
424      CP->getMachineCPVal()->AddSelectionDAGCSEId(ID);
425    else
426      ID.AddPointer(CP->getConstVal());
427    break;
428  }
429  case ISD::LOAD: {
430    LoadSDNode *LD = cast<LoadSDNode>(N);
431    ID.AddInteger(LD->getAddressingMode());
432    ID.AddInteger(LD->getExtensionType());
433    ID.AddInteger(LD->getMemoryVT().getRawBits());
434    ID.AddInteger(LD->getAlignment());
435    ID.AddInteger(LD->isVolatile());
436    break;
437  }
438  case ISD::STORE: {
439    StoreSDNode *ST = cast<StoreSDNode>(N);
440    ID.AddInteger(ST->getAddressingMode());
441    ID.AddInteger(ST->isTruncatingStore());
442    ID.AddInteger(ST->getMemoryVT().getRawBits());
443    ID.AddInteger(ST->getAlignment());
444    ID.AddInteger(ST->isVolatile());
445    break;
446  }
447  case ISD::ATOMIC_CMP_SWAP:
448  case ISD::ATOMIC_LOAD_ADD:
449  case ISD::ATOMIC_SWAP:
450  case ISD::ATOMIC_LOAD_SUB:
451  case ISD::ATOMIC_LOAD_AND:
452  case ISD::ATOMIC_LOAD_OR:
453  case ISD::ATOMIC_LOAD_XOR:
454  case ISD::ATOMIC_LOAD_NAND:
455  case ISD::ATOMIC_LOAD_MIN:
456  case ISD::ATOMIC_LOAD_MAX:
457  case ISD::ATOMIC_LOAD_UMIN:
458  case ISD::ATOMIC_LOAD_UMAX: {
459    AtomicSDNode *AT = cast<AtomicSDNode>(N);
460    ID.AddInteger(AT->getAlignment());
461    ID.AddInteger(AT->isVolatile());
462    break;
463  }
464  } // end switch (N->getOpcode())
465}
466
467//===----------------------------------------------------------------------===//
468//                              SelectionDAG Class
469//===----------------------------------------------------------------------===//
470
471inline alist_traits<SDNode, LargestSDNode>::AllocatorType &
472SelectionDAG::getAllocator() {
473  return AllNodes.getTraits().Allocator;
474}
475
476/// RemoveDeadNodes - This method deletes all unreachable nodes in the
477/// SelectionDAG.
478void SelectionDAG::RemoveDeadNodes() {
479  // Create a dummy node (which is not added to allnodes), that adds a reference
480  // to the root node, preventing it from being deleted.
481  HandleSDNode Dummy(getRoot());
482
483  SmallVector<SDNode*, 128> DeadNodes;
484
485  // Add all obviously-dead nodes to the DeadNodes worklist.
486  for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
487    if (I->use_empty())
488      DeadNodes.push_back(I);
489
490  RemoveDeadNodes(DeadNodes);
491
492  // If the root changed (e.g. it was a dead load, update the root).
493  setRoot(Dummy.getValue());
494}
495
496/// RemoveDeadNodes - This method deletes the unreachable nodes in the
497/// given list, and any nodes that become unreachable as a result.
498void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
499                                   DAGUpdateListener *UpdateListener) {
500
501  // Process the worklist, deleting the nodes and adding their uses to the
502  // worklist.
503  while (!DeadNodes.empty()) {
504    SDNode *N = DeadNodes.back();
505    DeadNodes.pop_back();
506
507    if (UpdateListener)
508      UpdateListener->NodeDeleted(N, 0);
509
510    // Take the node out of the appropriate CSE map.
511    RemoveNodeFromCSEMaps(N);
512
513    // Next, brutally remove the operand list.  This is safe to do, as there are
514    // no cycles in the graph.
515    for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
516      SDNode *Operand = I->getVal();
517      Operand->removeUser(std::distance(N->op_begin(), I), N);
518
519      // Now that we removed this operand, see if there are no uses of it left.
520      if (Operand->use_empty())
521        DeadNodes.push_back(Operand);
522    }
523    if (N->OperandsNeedDelete) {
524      delete[] N->OperandList;
525    }
526    N->OperandList = 0;
527    N->NumOperands = 0;
528
529    // Finally, remove N itself.
530    AllNodes.erase(N);
531  }
532}
533
534void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
535  SmallVector<SDNode*, 16> DeadNodes;
536  DeadNodes.push_back(N);
537  RemoveDeadNodes(DeadNodes, UpdateListener);
538}
539
540void SelectionDAG::DeleteNode(SDNode *N) {
541  assert(N->use_empty() && "Cannot delete a node that is not dead!");
542
543  // First take this out of the appropriate CSE map.
544  RemoveNodeFromCSEMaps(N);
545
546  // Finally, remove uses due to operands of this node, remove from the
547  // AllNodes list, and delete the node.
548  DeleteNodeNotInCSEMaps(N);
549}
550
551void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
552
553  // Drop all of the operands and decrement used nodes use counts.
554  for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
555    I->getVal()->removeUser(std::distance(N->op_begin(), I), N);
556  if (N->OperandsNeedDelete) {
557    delete[] N->OperandList;
558  }
559  N->OperandList = 0;
560  N->NumOperands = 0;
561
562  AllNodes.erase(N);
563}
564
565/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
566/// correspond to it.  This is useful when we're about to delete or repurpose
567/// the node.  We don't want future request for structurally identical nodes
568/// to return N anymore.
569void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
570  bool Erased = false;
571  switch (N->getOpcode()) {
572  case ISD::HANDLENODE: return;  // noop.
573  case ISD::CONDCODE:
574    assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
575           "Cond code doesn't exist!");
576    Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
577    CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
578    break;
579  case ISD::ExternalSymbol:
580    Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
581    break;
582  case ISD::TargetExternalSymbol:
583    Erased =
584      TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
585    break;
586  case ISD::VALUETYPE: {
587    MVT VT = cast<VTSDNode>(N)->getVT();
588    if (VT.isExtended()) {
589      Erased = ExtendedValueTypeNodes.erase(VT);
590    } else {
591      Erased = ValueTypeNodes[VT.getSimpleVT()] != 0;
592      ValueTypeNodes[VT.getSimpleVT()] = 0;
593    }
594    break;
595  }
596  default:
597    // Remove it from the CSE Map.
598    Erased = CSEMap.RemoveNode(N);
599    break;
600  }
601#ifndef NDEBUG
602  // Verify that the node was actually in one of the CSE maps, unless it has a
603  // flag result (which cannot be CSE'd) or is one of the special cases that are
604  // not subject to CSE.
605  if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
606      !N->isTargetOpcode() &&
607      N->getOpcode() != ISD::DBG_LABEL &&
608      N->getOpcode() != ISD::DBG_STOPPOINT &&
609      N->getOpcode() != ISD::EH_LABEL &&
610      N->getOpcode() != ISD::DECLARE) {
611    N->dump(this);
612    cerr << "\n";
613    assert(0 && "Node is not in map!");
614  }
615#endif
616}
617
618/// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
619/// has been taken out and modified in some way.  If the specified node already
620/// exists in the CSE maps, do not modify the maps, but return the existing node
621/// instead.  If it doesn't exist, add it and return null.
622///
623SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
624  assert(N->getNumOperands() && "This is a leaf node!");
625
626  if (N->getValueType(0) == MVT::Flag)
627    return 0;   // Never CSE anything that produces a flag.
628
629  switch (N->getOpcode()) {
630  default: break;
631  case ISD::HANDLENODE:
632  case ISD::DBG_LABEL:
633  case ISD::DBG_STOPPOINT:
634  case ISD::EH_LABEL:
635  case ISD::DECLARE:
636    return 0;    // Never add these nodes.
637  }
638
639  // Check that remaining values produced are not flags.
640  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
641    if (N->getValueType(i) == MVT::Flag)
642      return 0;   // Never CSE anything that produces a flag.
643
644  SDNode *New = CSEMap.GetOrInsertNode(N);
645  if (New != N) return New;  // Node already existed.
646  return 0;
647}
648
649/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
650/// were replaced with those specified.  If this node is never memoized,
651/// return null, otherwise return a pointer to the slot it would take.  If a
652/// node already exists with these operands, the slot will be non-null.
653SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
654                                           void *&InsertPos) {
655  if (N->getValueType(0) == MVT::Flag)
656    return 0;   // Never CSE anything that produces a flag.
657
658  switch (N->getOpcode()) {
659  default: break;
660  case ISD::HANDLENODE:
661  case ISD::DBG_LABEL:
662  case ISD::DBG_STOPPOINT:
663  case ISD::EH_LABEL:
664    return 0;    // Never add these nodes.
665  }
666
667  // Check that remaining values produced are not flags.
668  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
669    if (N->getValueType(i) == MVT::Flag)
670      return 0;   // Never CSE anything that produces a flag.
671
672  SDOperand Ops[] = { Op };
673  FoldingSetNodeID ID;
674  AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
675  return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
676}
677
678/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
679/// were replaced with those specified.  If this node is never memoized,
680/// return null, otherwise return a pointer to the slot it would take.  If a
681/// node already exists with these operands, the slot will be non-null.
682SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
683                                           SDOperand Op1, SDOperand Op2,
684                                           void *&InsertPos) {
685  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
686
687  // Check that remaining values produced are not flags.
688  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
689    if (N->getValueType(i) == MVT::Flag)
690      return 0;   // Never CSE anything that produces a flag.
691
692  SDOperand Ops[] = { Op1, Op2 };
693  FoldingSetNodeID ID;
694  AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
695  return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
696}
697
698
699/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
700/// were replaced with those specified.  If this node is never memoized,
701/// return null, otherwise return a pointer to the slot it would take.  If a
702/// node already exists with these operands, the slot will be non-null.
703SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
704                                           const SDOperand *Ops,unsigned NumOps,
705                                           void *&InsertPos) {
706  if (N->getValueType(0) == MVT::Flag)
707    return 0;   // Never CSE anything that produces a flag.
708
709  switch (N->getOpcode()) {
710  default: break;
711  case ISD::HANDLENODE:
712  case ISD::DBG_LABEL:
713  case ISD::DBG_STOPPOINT:
714  case ISD::EH_LABEL:
715  case ISD::DECLARE:
716    return 0;    // Never add these nodes.
717  }
718
719  // Check that remaining values produced are not flags.
720  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
721    if (N->getValueType(i) == MVT::Flag)
722      return 0;   // Never CSE anything that produces a flag.
723
724  FoldingSetNodeID ID;
725  AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
726
727  if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
728    ID.AddInteger(LD->getAddressingMode());
729    ID.AddInteger(LD->getExtensionType());
730    ID.AddInteger(LD->getMemoryVT().getRawBits());
731    ID.AddInteger(LD->getAlignment());
732    ID.AddInteger(LD->isVolatile());
733  } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
734    ID.AddInteger(ST->getAddressingMode());
735    ID.AddInteger(ST->isTruncatingStore());
736    ID.AddInteger(ST->getMemoryVT().getRawBits());
737    ID.AddInteger(ST->getAlignment());
738    ID.AddInteger(ST->isVolatile());
739  }
740
741  return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
742}
743
744/// getMVTAlignment - Compute the default alignment value for the
745/// given type.
746///
747unsigned SelectionDAG::getMVTAlignment(MVT VT) const {
748  const Type *Ty = VT == MVT::iPTR ?
749                   PointerType::get(Type::Int8Ty, 0) :
750                   VT.getTypeForMVT();
751
752  return TLI.getTargetData()->getABITypeAlignment(Ty);
753}
754
755SelectionDAG::~SelectionDAG() {
756  while (!AllNodes.empty()) {
757    SDNode *N = AllNodes.begin();
758    N->SetNextInBucket(0);
759    if (N->OperandsNeedDelete) {
760      delete [] N->OperandList;
761    }
762    N->OperandList = 0;
763    N->NumOperands = 0;
764    AllNodes.pop_front();
765  }
766}
767
768SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT VT) {
769  if (Op.getValueType() == VT) return Op;
770  APInt Imm = APInt::getLowBitsSet(Op.getValueSizeInBits(),
771                                   VT.getSizeInBits());
772  return getNode(ISD::AND, Op.getValueType(), Op,
773                 getConstant(Imm, Op.getValueType()));
774}
775
776SDOperand SelectionDAG::getConstant(uint64_t Val, MVT VT, bool isT) {
777  MVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT;
778  return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
779}
780
781SDOperand SelectionDAG::getConstant(const APInt &Val, MVT VT, bool isT) {
782  assert(VT.isInteger() && "Cannot create FP integer constant!");
783
784  MVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT;
785  assert(Val.getBitWidth() == EltVT.getSizeInBits() &&
786         "APInt size does not match type size!");
787
788  unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
789  FoldingSetNodeID ID;
790  AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
791  ID.Add(Val);
792  void *IP = 0;
793  SDNode *N = NULL;
794  if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
795    if (!VT.isVector())
796      return SDOperand(N, 0);
797  if (!N) {
798    N = getAllocator().Allocate<ConstantSDNode>();
799    new (N) ConstantSDNode(isT, Val, EltVT);
800    CSEMap.InsertNode(N, IP);
801    AllNodes.push_back(N);
802  }
803
804  SDOperand Result(N, 0);
805  if (VT.isVector()) {
806    SmallVector<SDOperand, 8> Ops;
807    Ops.assign(VT.getVectorNumElements(), Result);
808    Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
809  }
810  return Result;
811}
812
813SDOperand SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
814  return getConstant(Val, TLI.getPointerTy(), isTarget);
815}
816
817
818SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT VT, bool isTarget) {
819  assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
820
821  MVT EltVT =
822    VT.isVector() ? VT.getVectorElementType() : VT;
823
824  // Do the map lookup using the actual bit pattern for the floating point
825  // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
826  // we don't have issues with SNANs.
827  unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
828  FoldingSetNodeID ID;
829  AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
830  ID.Add(V);
831  void *IP = 0;
832  SDNode *N = NULL;
833  if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
834    if (!VT.isVector())
835      return SDOperand(N, 0);
836  if (!N) {
837    N = getAllocator().Allocate<ConstantFPSDNode>();
838    new (N) ConstantFPSDNode(isTarget, V, EltVT);
839    CSEMap.InsertNode(N, IP);
840    AllNodes.push_back(N);
841  }
842
843  SDOperand Result(N, 0);
844  if (VT.isVector()) {
845    SmallVector<SDOperand, 8> Ops;
846    Ops.assign(VT.getVectorNumElements(), Result);
847    Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
848  }
849  return Result;
850}
851
852SDOperand SelectionDAG::getConstantFP(double Val, MVT VT, bool isTarget) {
853  MVT EltVT =
854    VT.isVector() ? VT.getVectorElementType() : VT;
855  if (EltVT==MVT::f32)
856    return getConstantFP(APFloat((float)Val), VT, isTarget);
857  else
858    return getConstantFP(APFloat(Val), VT, isTarget);
859}
860
861SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
862                                         MVT VT, int Offset,
863                                         bool isTargetGA) {
864  unsigned Opc;
865
866  const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
867  if (!GVar) {
868    // If GV is an alias then use the aliasee for determining thread-localness.
869    if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
870      GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal());
871  }
872
873  if (GVar && GVar->isThreadLocal())
874    Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
875  else
876    Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
877
878  FoldingSetNodeID ID;
879  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
880  ID.AddPointer(GV);
881  ID.AddInteger(Offset);
882  void *IP = 0;
883  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
884   return SDOperand(E, 0);
885  SDNode *N = getAllocator().Allocate<GlobalAddressSDNode>();
886  new (N) GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
887  CSEMap.InsertNode(N, IP);
888  AllNodes.push_back(N);
889  return SDOperand(N, 0);
890}
891
892SDOperand SelectionDAG::getFrameIndex(int FI, MVT VT, bool isTarget) {
893  unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
894  FoldingSetNodeID ID;
895  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
896  ID.AddInteger(FI);
897  void *IP = 0;
898  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
899    return SDOperand(E, 0);
900  SDNode *N = getAllocator().Allocate<FrameIndexSDNode>();
901  new (N) FrameIndexSDNode(FI, VT, isTarget);
902  CSEMap.InsertNode(N, IP);
903  AllNodes.push_back(N);
904  return SDOperand(N, 0);
905}
906
907SDOperand SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){
908  unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
909  FoldingSetNodeID ID;
910  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
911  ID.AddInteger(JTI);
912  void *IP = 0;
913  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
914    return SDOperand(E, 0);
915  SDNode *N = getAllocator().Allocate<JumpTableSDNode>();
916  new (N) JumpTableSDNode(JTI, VT, isTarget);
917  CSEMap.InsertNode(N, IP);
918  AllNodes.push_back(N);
919  return SDOperand(N, 0);
920}
921
922SDOperand SelectionDAG::getConstantPool(Constant *C, MVT VT,
923                                        unsigned Alignment, int Offset,
924                                        bool isTarget) {
925  unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
926  FoldingSetNodeID ID;
927  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
928  ID.AddInteger(Alignment);
929  ID.AddInteger(Offset);
930  ID.AddPointer(C);
931  void *IP = 0;
932  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
933    return SDOperand(E, 0);
934  SDNode *N = getAllocator().Allocate<ConstantPoolSDNode>();
935  new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
936  CSEMap.InsertNode(N, IP);
937  AllNodes.push_back(N);
938  return SDOperand(N, 0);
939}
940
941
942SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT,
943                                        unsigned Alignment, int Offset,
944                                        bool isTarget) {
945  unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
946  FoldingSetNodeID ID;
947  AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
948  ID.AddInteger(Alignment);
949  ID.AddInteger(Offset);
950  C->AddSelectionDAGCSEId(ID);
951  void *IP = 0;
952  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
953    return SDOperand(E, 0);
954  SDNode *N = getAllocator().Allocate<ConstantPoolSDNode>();
955  new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
956  CSEMap.InsertNode(N, IP);
957  AllNodes.push_back(N);
958  return SDOperand(N, 0);
959}
960
961
962SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
963  FoldingSetNodeID ID;
964  AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
965  ID.AddPointer(MBB);
966  void *IP = 0;
967  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
968    return SDOperand(E, 0);
969  SDNode *N = getAllocator().Allocate<BasicBlockSDNode>();
970  new (N) BasicBlockSDNode(MBB);
971  CSEMap.InsertNode(N, IP);
972  AllNodes.push_back(N);
973  return SDOperand(N, 0);
974}
975
976SDOperand SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) {
977  FoldingSetNodeID ID;
978  AddNodeIDNode(ID, ISD::ARG_FLAGS, getVTList(MVT::Other), 0, 0);
979  ID.AddInteger(Flags.getRawBits());
980  void *IP = 0;
981  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
982    return SDOperand(E, 0);
983  SDNode *N = getAllocator().Allocate<ARG_FLAGSSDNode>();
984  new (N) ARG_FLAGSSDNode(Flags);
985  CSEMap.InsertNode(N, IP);
986  AllNodes.push_back(N);
987  return SDOperand(N, 0);
988}
989
990SDOperand SelectionDAG::getValueType(MVT VT) {
991  if (VT.isSimple() && (unsigned)VT.getSimpleVT() >= ValueTypeNodes.size())
992    ValueTypeNodes.resize(VT.getSimpleVT()+1);
993
994  SDNode *&N = VT.isExtended() ?
995    ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT()];
996
997  if (N) return SDOperand(N, 0);
998  N = getAllocator().Allocate<VTSDNode>();
999  new (N) VTSDNode(VT);
1000  AllNodes.push_back(N);
1001  return SDOperand(N, 0);
1002}
1003
1004SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) {
1005  SDNode *&N = ExternalSymbols[Sym];
1006  if (N) return SDOperand(N, 0);
1007  N = getAllocator().Allocate<ExternalSymbolSDNode>();
1008  new (N) ExternalSymbolSDNode(false, Sym, VT);
1009  AllNodes.push_back(N);
1010  return SDOperand(N, 0);
1011}
1012
1013SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT VT) {
1014  SDNode *&N = TargetExternalSymbols[Sym];
1015  if (N) return SDOperand(N, 0);
1016  N = getAllocator().Allocate<ExternalSymbolSDNode>();
1017  new (N) ExternalSymbolSDNode(true, Sym, VT);
1018  AllNodes.push_back(N);
1019  return SDOperand(N, 0);
1020}
1021
1022SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
1023  if ((unsigned)Cond >= CondCodeNodes.size())
1024    CondCodeNodes.resize(Cond+1);
1025
1026  if (CondCodeNodes[Cond] == 0) {
1027    CondCodeSDNode *N = getAllocator().Allocate<CondCodeSDNode>();
1028    new (N) CondCodeSDNode(Cond);
1029    CondCodeNodes[Cond] = N;
1030    AllNodes.push_back(N);
1031  }
1032  return SDOperand(CondCodeNodes[Cond], 0);
1033}
1034
1035SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT VT) {
1036  FoldingSetNodeID ID;
1037  AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1038  ID.AddInteger(RegNo);
1039  void *IP = 0;
1040  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1041    return SDOperand(E, 0);
1042  SDNode *N = getAllocator().Allocate<RegisterSDNode>();
1043  new (N) RegisterSDNode(RegNo, VT);
1044  CSEMap.InsertNode(N, IP);
1045  AllNodes.push_back(N);
1046  return SDOperand(N, 0);
1047}
1048
1049SDOperand SelectionDAG::getDbgStopPoint(SDOperand Root,
1050                                        unsigned Line, unsigned Col,
1051                                        const CompileUnitDesc *CU) {
1052  SDNode *N = getAllocator().Allocate<DbgStopPointSDNode>();
1053  new (N) DbgStopPointSDNode(Root, Line, Col, CU);
1054  AllNodes.push_back(N);
1055  return SDOperand(N, 0);
1056}
1057
1058SDOperand SelectionDAG::getLabel(unsigned Opcode,
1059                                 SDOperand Root,
1060                                 unsigned LabelID) {
1061  FoldingSetNodeID ID;
1062  SDOperand Ops[] = { Root };
1063  AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), &Ops[0], 1);
1064  ID.AddInteger(LabelID);
1065  void *IP = 0;
1066  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1067    return SDOperand(E, 0);
1068  SDNode *N = getAllocator().Allocate<LabelSDNode>();
1069  new (N) LabelSDNode(Opcode, Root, LabelID);
1070  CSEMap.InsertNode(N, IP);
1071  AllNodes.push_back(N);
1072  return SDOperand(N, 0);
1073}
1074
1075SDOperand SelectionDAG::getSrcValue(const Value *V) {
1076  assert((!V || isa<PointerType>(V->getType())) &&
1077         "SrcValue is not a pointer?");
1078
1079  FoldingSetNodeID ID;
1080  AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1081  ID.AddPointer(V);
1082
1083  void *IP = 0;
1084  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1085    return SDOperand(E, 0);
1086
1087  SDNode *N = getAllocator().Allocate<SrcValueSDNode>();
1088  new (N) SrcValueSDNode(V);
1089  CSEMap.InsertNode(N, IP);
1090  AllNodes.push_back(N);
1091  return SDOperand(N, 0);
1092}
1093
1094SDOperand SelectionDAG::getMemOperand(const MachineMemOperand &MO) {
1095  const Value *v = MO.getValue();
1096  assert((!v || isa<PointerType>(v->getType())) &&
1097         "SrcValue is not a pointer?");
1098
1099  FoldingSetNodeID ID;
1100  AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), 0, 0);
1101  ID.AddPointer(v);
1102  ID.AddInteger(MO.getFlags());
1103  ID.AddInteger(MO.getOffset());
1104  ID.AddInteger(MO.getSize());
1105  ID.AddInteger(MO.getAlignment());
1106
1107  void *IP = 0;
1108  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1109    return SDOperand(E, 0);
1110
1111  SDNode *N = getAllocator().Allocate<MemOperandSDNode>();
1112  new (N) MemOperandSDNode(MO);
1113  CSEMap.InsertNode(N, IP);
1114  AllNodes.push_back(N);
1115  return SDOperand(N, 0);
1116}
1117
1118/// CreateStackTemporary - Create a stack temporary, suitable for holding the
1119/// specified value type.
1120SDOperand SelectionDAG::CreateStackTemporary(MVT VT, unsigned minAlign) {
1121  MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1122  unsigned ByteSize = VT.getSizeInBits()/8;
1123  const Type *Ty = VT.getTypeForMVT();
1124  unsigned StackAlign =
1125  std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
1126
1127  int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign);
1128  return getFrameIndex(FrameIdx, TLI.getPointerTy());
1129}
1130
1131SDOperand SelectionDAG::FoldSetCC(MVT VT, SDOperand N1,
1132                                  SDOperand N2, ISD::CondCode Cond) {
1133  // These setcc operations always fold.
1134  switch (Cond) {
1135  default: break;
1136  case ISD::SETFALSE:
1137  case ISD::SETFALSE2: return getConstant(0, VT);
1138  case ISD::SETTRUE:
1139  case ISD::SETTRUE2:  return getConstant(1, VT);
1140
1141  case ISD::SETOEQ:
1142  case ISD::SETOGT:
1143  case ISD::SETOGE:
1144  case ISD::SETOLT:
1145  case ISD::SETOLE:
1146  case ISD::SETONE:
1147  case ISD::SETO:
1148  case ISD::SETUO:
1149  case ISD::SETUEQ:
1150  case ISD::SETUNE:
1151    assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1152    break;
1153  }
1154
1155  if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
1156    const APInt &C2 = N2C->getAPIntValue();
1157    if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
1158      const APInt &C1 = N1C->getAPIntValue();
1159
1160      switch (Cond) {
1161      default: assert(0 && "Unknown integer setcc!");
1162      case ISD::SETEQ:  return getConstant(C1 == C2, VT);
1163      case ISD::SETNE:  return getConstant(C1 != C2, VT);
1164      case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1165      case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1166      case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1167      case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1168      case ISD::SETLT:  return getConstant(C1.slt(C2), VT);
1169      case ISD::SETGT:  return getConstant(C1.sgt(C2), VT);
1170      case ISD::SETLE:  return getConstant(C1.sle(C2), VT);
1171      case ISD::SETGE:  return getConstant(C1.sge(C2), VT);
1172      }
1173    }
1174  }
1175  if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) {
1176    if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
1177      // No compile time operations on this type yet.
1178      if (N1C->getValueType(0) == MVT::ppcf128)
1179        return SDOperand();
1180
1181      APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1182      switch (Cond) {
1183      default: break;
1184      case ISD::SETEQ:  if (R==APFloat::cmpUnordered)
1185                          return getNode(ISD::UNDEF, VT);
1186                        // fall through
1187      case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1188      case ISD::SETNE:  if (R==APFloat::cmpUnordered)
1189                          return getNode(ISD::UNDEF, VT);
1190                        // fall through
1191      case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1192                                           R==APFloat::cmpLessThan, VT);
1193      case ISD::SETLT:  if (R==APFloat::cmpUnordered)
1194                          return getNode(ISD::UNDEF, VT);
1195                        // fall through
1196      case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1197      case ISD::SETGT:  if (R==APFloat::cmpUnordered)
1198                          return getNode(ISD::UNDEF, VT);
1199                        // fall through
1200      case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1201      case ISD::SETLE:  if (R==APFloat::cmpUnordered)
1202                          return getNode(ISD::UNDEF, VT);
1203                        // fall through
1204      case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1205                                           R==APFloat::cmpEqual, VT);
1206      case ISD::SETGE:  if (R==APFloat::cmpUnordered)
1207                          return getNode(ISD::UNDEF, VT);
1208                        // fall through
1209      case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1210                                           R==APFloat::cmpEqual, VT);
1211      case ISD::SETO:   return getConstant(R!=APFloat::cmpUnordered, VT);
1212      case ISD::SETUO:  return getConstant(R==APFloat::cmpUnordered, VT);
1213      case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1214                                           R==APFloat::cmpEqual, VT);
1215      case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1216      case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1217                                           R==APFloat::cmpLessThan, VT);
1218      case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1219                                           R==APFloat::cmpUnordered, VT);
1220      case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1221      case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1222      }
1223    } else {
1224      // Ensure that the constant occurs on the RHS.
1225      return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1226    }
1227  }
1228
1229  // Could not fold it.
1230  return SDOperand();
1231}
1232
1233/// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1234/// use this predicate to simplify operations downstream.
1235bool SelectionDAG::SignBitIsZero(SDOperand Op, unsigned Depth) const {
1236  unsigned BitWidth = Op.getValueSizeInBits();
1237  return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1238}
1239
1240/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
1241/// this predicate to simplify operations downstream.  Mask is known to be zero
1242/// for bits that V cannot have.
1243bool SelectionDAG::MaskedValueIsZero(SDOperand Op, const APInt &Mask,
1244                                     unsigned Depth) const {
1245  APInt KnownZero, KnownOne;
1246  ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1247  assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1248  return (KnownZero & Mask) == Mask;
1249}
1250
1251/// ComputeMaskedBits - Determine which of the bits specified in Mask are
1252/// known to be either zero or one and return them in the KnownZero/KnownOne
1253/// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
1254/// processing.
1255void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask,
1256                                     APInt &KnownZero, APInt &KnownOne,
1257                                     unsigned Depth) const {
1258  unsigned BitWidth = Mask.getBitWidth();
1259  assert(BitWidth == Op.getValueType().getSizeInBits() &&
1260         "Mask size mismatches value type size!");
1261
1262  KnownZero = KnownOne = APInt(BitWidth, 0);   // Don't know anything.
1263  if (Depth == 6 || Mask == 0)
1264    return;  // Limit search depth.
1265
1266  APInt KnownZero2, KnownOne2;
1267
1268  switch (Op.getOpcode()) {
1269  case ISD::Constant:
1270    // We know all of the bits for a constant!
1271    KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & Mask;
1272    KnownZero = ~KnownOne & Mask;
1273    return;
1274  case ISD::AND:
1275    // If either the LHS or the RHS are Zero, the result is zero.
1276    ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1277    ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownZero,
1278                      KnownZero2, KnownOne2, Depth+1);
1279    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1280    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1281
1282    // Output known-1 bits are only known if set in both the LHS & RHS.
1283    KnownOne &= KnownOne2;
1284    // Output known-0 are known to be clear if zero in either the LHS | RHS.
1285    KnownZero |= KnownZero2;
1286    return;
1287  case ISD::OR:
1288    ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1289    ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownOne,
1290                      KnownZero2, KnownOne2, Depth+1);
1291    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1292    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1293
1294    // Output known-0 bits are only known if clear in both the LHS & RHS.
1295    KnownZero &= KnownZero2;
1296    // Output known-1 are known to be set if set in either the LHS | RHS.
1297    KnownOne |= KnownOne2;
1298    return;
1299  case ISD::XOR: {
1300    ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1301    ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
1302    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1303    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1304
1305    // Output known-0 bits are known if clear or set in both the LHS & RHS.
1306    APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1307    // Output known-1 are known to be set if set in only one of the LHS, RHS.
1308    KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1309    KnownZero = KnownZeroOut;
1310    return;
1311  }
1312  case ISD::MUL: {
1313    APInt Mask2 = APInt::getAllOnesValue(BitWidth);
1314    ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero, KnownOne, Depth+1);
1315    ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1316    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1317    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1318
1319    // If low bits are zero in either operand, output low known-0 bits.
1320    // Also compute a conserative estimate for high known-0 bits.
1321    // More trickiness is possible, but this is sufficient for the
1322    // interesting case of alignment computation.
1323    KnownOne.clear();
1324    unsigned TrailZ = KnownZero.countTrailingOnes() +
1325                      KnownZero2.countTrailingOnes();
1326    unsigned LeadZ =  std::max(KnownZero.countLeadingOnes() +
1327                               KnownZero2.countLeadingOnes(),
1328                               BitWidth) - BitWidth;
1329
1330    TrailZ = std::min(TrailZ, BitWidth);
1331    LeadZ = std::min(LeadZ, BitWidth);
1332    KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1333                APInt::getHighBitsSet(BitWidth, LeadZ);
1334    KnownZero &= Mask;
1335    return;
1336  }
1337  case ISD::UDIV: {
1338    // For the purposes of computing leading zeros we can conservatively
1339    // treat a udiv as a logical right shift by the power of 2 known to
1340    // be less than the denominator.
1341    APInt AllOnes = APInt::getAllOnesValue(BitWidth);
1342    ComputeMaskedBits(Op.getOperand(0),
1343                      AllOnes, KnownZero2, KnownOne2, Depth+1);
1344    unsigned LeadZ = KnownZero2.countLeadingOnes();
1345
1346    KnownOne2.clear();
1347    KnownZero2.clear();
1348    ComputeMaskedBits(Op.getOperand(1),
1349                      AllOnes, KnownZero2, KnownOne2, Depth+1);
1350    unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1351    if (RHSUnknownLeadingOnes != BitWidth)
1352      LeadZ = std::min(BitWidth,
1353                       LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1354
1355    KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask;
1356    return;
1357  }
1358  case ISD::SELECT:
1359    ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
1360    ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
1361    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1362    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1363
1364    // Only known if known in both the LHS and RHS.
1365    KnownOne &= KnownOne2;
1366    KnownZero &= KnownZero2;
1367    return;
1368  case ISD::SELECT_CC:
1369    ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
1370    ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
1371    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1372    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1373
1374    // Only known if known in both the LHS and RHS.
1375    KnownOne &= KnownOne2;
1376    KnownZero &= KnownZero2;
1377    return;
1378  case ISD::SETCC:
1379    // If we know the result of a setcc has the top bits zero, use this info.
1380    if (TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult &&
1381        BitWidth > 1)
1382      KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1383    return;
1384  case ISD::SHL:
1385    // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
1386    if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1387      unsigned ShAmt = SA->getValue();
1388
1389      // If the shift count is an invalid immediate, don't do anything.
1390      if (ShAmt >= BitWidth)
1391        return;
1392
1393      ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt),
1394                        KnownZero, KnownOne, Depth+1);
1395      assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1396      KnownZero <<= ShAmt;
1397      KnownOne  <<= ShAmt;
1398      // low bits known zero.
1399      KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1400    }
1401    return;
1402  case ISD::SRL:
1403    // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
1404    if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1405      unsigned ShAmt = SA->getValue();
1406
1407      // If the shift count is an invalid immediate, don't do anything.
1408      if (ShAmt >= BitWidth)
1409        return;
1410
1411      ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt),
1412                        KnownZero, KnownOne, Depth+1);
1413      assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1414      KnownZero = KnownZero.lshr(ShAmt);
1415      KnownOne  = KnownOne.lshr(ShAmt);
1416
1417      APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1418      KnownZero |= HighBits;  // High bits known zero.
1419    }
1420    return;
1421  case ISD::SRA:
1422    if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1423      unsigned ShAmt = SA->getValue();
1424
1425      // If the shift count is an invalid immediate, don't do anything.
1426      if (ShAmt >= BitWidth)
1427        return;
1428
1429      APInt InDemandedMask = (Mask << ShAmt);
1430      // If any of the demanded bits are produced by the sign extension, we also
1431      // demand the input sign bit.
1432      APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1433      if (HighBits.getBoolValue())
1434        InDemandedMask |= APInt::getSignBit(BitWidth);
1435
1436      ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne,
1437                        Depth+1);
1438      assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1439      KnownZero = KnownZero.lshr(ShAmt);
1440      KnownOne  = KnownOne.lshr(ShAmt);
1441
1442      // Handle the sign bits.
1443      APInt SignBit = APInt::getSignBit(BitWidth);
1444      SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
1445
1446      if (KnownZero.intersects(SignBit)) {
1447        KnownZero |= HighBits;  // New bits are known zero.
1448      } else if (KnownOne.intersects(SignBit)) {
1449        KnownOne  |= HighBits;  // New bits are known one.
1450      }
1451    }
1452    return;
1453  case ISD::SIGN_EXTEND_INREG: {
1454    MVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1455    unsigned EBits = EVT.getSizeInBits();
1456
1457    // Sign extension.  Compute the demanded bits in the result that are not
1458    // present in the input.
1459    APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask;
1460
1461    APInt InSignBit = APInt::getSignBit(EBits);
1462    APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits);
1463
1464    // If the sign extended bits are demanded, we know that the sign
1465    // bit is demanded.
1466    InSignBit.zext(BitWidth);
1467    if (NewBits.getBoolValue())
1468      InputDemandedBits |= InSignBit;
1469
1470    ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
1471                      KnownZero, KnownOne, Depth+1);
1472    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1473
1474    // If the sign bit of the input is known set or clear, then we know the
1475    // top bits of the result.
1476    if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
1477      KnownZero |= NewBits;
1478      KnownOne  &= ~NewBits;
1479    } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
1480      KnownOne  |= NewBits;
1481      KnownZero &= ~NewBits;
1482    } else {                              // Input sign bit unknown
1483      KnownZero &= ~NewBits;
1484      KnownOne  &= ~NewBits;
1485    }
1486    return;
1487  }
1488  case ISD::CTTZ:
1489  case ISD::CTLZ:
1490  case ISD::CTPOP: {
1491    unsigned LowBits = Log2_32(BitWidth)+1;
1492    KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1493    KnownOne.clear();
1494    return;
1495  }
1496  case ISD::LOAD: {
1497    if (ISD::isZEXTLoad(Op.Val)) {
1498      LoadSDNode *LD = cast<LoadSDNode>(Op);
1499      MVT VT = LD->getMemoryVT();
1500      unsigned MemBits = VT.getSizeInBits();
1501      KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask;
1502    }
1503    return;
1504  }
1505  case ISD::ZERO_EXTEND: {
1506    MVT InVT = Op.getOperand(0).getValueType();
1507    unsigned InBits = InVT.getSizeInBits();
1508    APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1509    APInt InMask    = Mask;
1510    InMask.trunc(InBits);
1511    KnownZero.trunc(InBits);
1512    KnownOne.trunc(InBits);
1513    ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1514    KnownZero.zext(BitWidth);
1515    KnownOne.zext(BitWidth);
1516    KnownZero |= NewBits;
1517    return;
1518  }
1519  case ISD::SIGN_EXTEND: {
1520    MVT InVT = Op.getOperand(0).getValueType();
1521    unsigned InBits = InVT.getSizeInBits();
1522    APInt InSignBit = APInt::getSignBit(InBits);
1523    APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1524    APInt InMask = Mask;
1525    InMask.trunc(InBits);
1526
1527    // If any of the sign extended bits are demanded, we know that the sign
1528    // bit is demanded. Temporarily set this bit in the mask for our callee.
1529    if (NewBits.getBoolValue())
1530      InMask |= InSignBit;
1531
1532    KnownZero.trunc(InBits);
1533    KnownOne.trunc(InBits);
1534    ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1535
1536    // Note if the sign bit is known to be zero or one.
1537    bool SignBitKnownZero = KnownZero.isNegative();
1538    bool SignBitKnownOne  = KnownOne.isNegative();
1539    assert(!(SignBitKnownZero && SignBitKnownOne) &&
1540           "Sign bit can't be known to be both zero and one!");
1541
1542    // If the sign bit wasn't actually demanded by our caller, we don't
1543    // want it set in the KnownZero and KnownOne result values. Reset the
1544    // mask and reapply it to the result values.
1545    InMask = Mask;
1546    InMask.trunc(InBits);
1547    KnownZero &= InMask;
1548    KnownOne  &= InMask;
1549
1550    KnownZero.zext(BitWidth);
1551    KnownOne.zext(BitWidth);
1552
1553    // If the sign bit is known zero or one, the top bits match.
1554    if (SignBitKnownZero)
1555      KnownZero |= NewBits;
1556    else if (SignBitKnownOne)
1557      KnownOne  |= NewBits;
1558    return;
1559  }
1560  case ISD::ANY_EXTEND: {
1561    MVT InVT = Op.getOperand(0).getValueType();
1562    unsigned InBits = InVT.getSizeInBits();
1563    APInt InMask = Mask;
1564    InMask.trunc(InBits);
1565    KnownZero.trunc(InBits);
1566    KnownOne.trunc(InBits);
1567    ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1568    KnownZero.zext(BitWidth);
1569    KnownOne.zext(BitWidth);
1570    return;
1571  }
1572  case ISD::TRUNCATE: {
1573    MVT InVT = Op.getOperand(0).getValueType();
1574    unsigned InBits = InVT.getSizeInBits();
1575    APInt InMask = Mask;
1576    InMask.zext(InBits);
1577    KnownZero.zext(InBits);
1578    KnownOne.zext(InBits);
1579    ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1580    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1581    KnownZero.trunc(BitWidth);
1582    KnownOne.trunc(BitWidth);
1583    break;
1584  }
1585  case ISD::AssertZext: {
1586    MVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1587    APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
1588    ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
1589                      KnownOne, Depth+1);
1590    KnownZero |= (~InMask) & Mask;
1591    return;
1592  }
1593  case ISD::FGETSIGN:
1594    // All bits are zero except the low bit.
1595    KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1596    return;
1597
1598  case ISD::SUB: {
1599    if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1600      // We know that the top bits of C-X are clear if X contains less bits
1601      // than C (i.e. no wrap-around can happen).  For example, 20-X is
1602      // positive if we can prove that X is >= 0 and < 16.
1603      if (CLHS->getAPIntValue().isNonNegative()) {
1604        unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1605        // NLZ can't be BitWidth with no sign bit
1606        APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1607        ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero2, KnownOne2,
1608                          Depth+1);
1609
1610        // If all of the MaskV bits are known to be zero, then we know the
1611        // output top bits are zero, because we now know that the output is
1612        // from [0-C].
1613        if ((KnownZero2 & MaskV) == MaskV) {
1614          unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
1615          // Top bits known zero.
1616          KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
1617        }
1618      }
1619    }
1620  }
1621  // fall through
1622  case ISD::ADD: {
1623    // Output known-0 bits are known if clear or set in both the low clear bits
1624    // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
1625    // low 3 bits clear.
1626    APInt Mask2 = APInt::getLowBitsSet(BitWidth, Mask.countTrailingOnes());
1627    ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1628    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1629    unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
1630
1631    ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1);
1632    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1633    KnownZeroOut = std::min(KnownZeroOut,
1634                            KnownZero2.countTrailingOnes());
1635
1636    KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
1637    return;
1638  }
1639  case ISD::SREM:
1640    if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1641      const APInt &RA = Rem->getAPIntValue();
1642      if (RA.isPowerOf2() || (-RA).isPowerOf2()) {
1643        APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA;
1644        APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
1645        ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1);
1646
1647        // The sign of a remainder is equal to the sign of the first
1648        // operand (zero being positive).
1649        if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
1650          KnownZero2 |= ~LowBits;
1651        else if (KnownOne2[BitWidth-1])
1652          KnownOne2 |= ~LowBits;
1653
1654        KnownZero |= KnownZero2 & Mask;
1655        KnownOne |= KnownOne2 & Mask;
1656
1657        assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
1658      }
1659    }
1660    return;
1661  case ISD::UREM: {
1662    if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1663      const APInt &RA = Rem->getAPIntValue();
1664      if (RA.isPowerOf2()) {
1665        APInt LowBits = (RA - 1);
1666        APInt Mask2 = LowBits & Mask;
1667        KnownZero |= ~LowBits & Mask;
1668        ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero, KnownOne,Depth+1);
1669        assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
1670        break;
1671      }
1672    }
1673
1674    // Since the result is less than or equal to either operand, any leading
1675    // zero bits in either operand must also exist in the result.
1676    APInt AllOnes = APInt::getAllOnesValue(BitWidth);
1677    ComputeMaskedBits(Op.getOperand(0), AllOnes, KnownZero, KnownOne,
1678                      Depth+1);
1679    ComputeMaskedBits(Op.getOperand(1), AllOnes, KnownZero2, KnownOne2,
1680                      Depth+1);
1681
1682    uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
1683                                KnownZero2.countLeadingOnes());
1684    KnownOne.clear();
1685    KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
1686    return;
1687  }
1688  default:
1689    // Allow the target to implement this method for its nodes.
1690    if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
1691  case ISD::INTRINSIC_WO_CHAIN:
1692  case ISD::INTRINSIC_W_CHAIN:
1693  case ISD::INTRINSIC_VOID:
1694      TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this);
1695    }
1696    return;
1697  }
1698}
1699
1700/// ComputeNumSignBits - Return the number of times the sign bit of the
1701/// register is replicated into the other bits.  We know that at least 1 bit
1702/// is always equal to the sign bit (itself), but other cases can give us
1703/// information.  For example, immediately after an "SRA X, 2", we know that
1704/// the top 3 bits are all equal to each other, so we return 3.
1705unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1706  MVT VT = Op.getValueType();
1707  assert(VT.isInteger() && "Invalid VT!");
1708  unsigned VTBits = VT.getSizeInBits();
1709  unsigned Tmp, Tmp2;
1710  unsigned FirstAnswer = 1;
1711
1712  if (Depth == 6)
1713    return 1;  // Limit search depth.
1714
1715  switch (Op.getOpcode()) {
1716  default: break;
1717  case ISD::AssertSext:
1718    Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
1719    return VTBits-Tmp+1;
1720  case ISD::AssertZext:
1721    Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
1722    return VTBits-Tmp;
1723
1724  case ISD::Constant: {
1725    const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
1726    // If negative, return # leading ones.
1727    if (Val.isNegative())
1728      return Val.countLeadingOnes();
1729
1730    // Return # leading zeros.
1731    return Val.countLeadingZeros();
1732  }
1733
1734  case ISD::SIGN_EXTEND:
1735    Tmp = VTBits-Op.getOperand(0).getValueType().getSizeInBits();
1736    return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1737
1738  case ISD::SIGN_EXTEND_INREG:
1739    // Max of the input and what this extends.
1740    Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
1741    Tmp = VTBits-Tmp+1;
1742
1743    Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1744    return std::max(Tmp, Tmp2);
1745
1746  case ISD::SRA:
1747    Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1748    // SRA X, C   -> adds C sign bits.
1749    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1750      Tmp += C->getValue();
1751      if (Tmp > VTBits) Tmp = VTBits;
1752    }
1753    return Tmp;
1754  case ISD::SHL:
1755    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1756      // shl destroys sign bits.
1757      Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1758      if (C->getValue() >= VTBits ||      // Bad shift.
1759          C->getValue() >= Tmp) break;    // Shifted all sign bits out.
1760      return Tmp - C->getValue();
1761    }
1762    break;
1763  case ISD::AND:
1764  case ISD::OR:
1765  case ISD::XOR:    // NOT is handled here.
1766    // Logical binary ops preserve the number of sign bits at the worst.
1767    Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1768    if (Tmp != 1) {
1769      Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1770      FirstAnswer = std::min(Tmp, Tmp2);
1771      // We computed what we know about the sign bits as our first
1772      // answer. Now proceed to the generic code that uses
1773      // ComputeMaskedBits, and pick whichever answer is better.
1774    }
1775    break;
1776
1777  case ISD::SELECT:
1778    Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1779    if (Tmp == 1) return 1;  // Early out.
1780    Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
1781    return std::min(Tmp, Tmp2);
1782
1783  case ISD::SETCC:
1784    // If setcc returns 0/-1, all bits are sign bits.
1785    if (TLI.getSetCCResultContents() ==
1786        TargetLowering::ZeroOrNegativeOneSetCCResult)
1787      return VTBits;
1788    break;
1789  case ISD::ROTL:
1790  case ISD::ROTR:
1791    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1792      unsigned RotAmt = C->getValue() & (VTBits-1);
1793
1794      // Handle rotate right by N like a rotate left by 32-N.
1795      if (Op.getOpcode() == ISD::ROTR)
1796        RotAmt = (VTBits-RotAmt) & (VTBits-1);
1797
1798      // If we aren't rotating out all of the known-in sign bits, return the
1799      // number that are left.  This handles rotl(sext(x), 1) for example.
1800      Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1801      if (Tmp > RotAmt+1) return Tmp-RotAmt;
1802    }
1803    break;
1804  case ISD::ADD:
1805    // Add can have at most one carry bit.  Thus we know that the output
1806    // is, at worst, one more bit than the inputs.
1807    Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1808    if (Tmp == 1) return 1;  // Early out.
1809
1810    // Special case decrementing a value (ADD X, -1):
1811    if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1812      if (CRHS->isAllOnesValue()) {
1813        APInt KnownZero, KnownOne;
1814        APInt Mask = APInt::getAllOnesValue(VTBits);
1815        ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1816
1817        // If the input is known to be 0 or 1, the output is 0/-1, which is all
1818        // sign bits set.
1819        if ((KnownZero | APInt(VTBits, 1)) == Mask)
1820          return VTBits;
1821
1822        // If we are subtracting one from a positive number, there is no carry
1823        // out of the result.
1824        if (KnownZero.isNegative())
1825          return Tmp;
1826      }
1827
1828    Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1829    if (Tmp2 == 1) return 1;
1830      return std::min(Tmp, Tmp2)-1;
1831    break;
1832
1833  case ISD::SUB:
1834    Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1835    if (Tmp2 == 1) return 1;
1836
1837    // Handle NEG.
1838    if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1839      if (CLHS->isNullValue()) {
1840        APInt KnownZero, KnownOne;
1841        APInt Mask = APInt::getAllOnesValue(VTBits);
1842        ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1843        // If the input is known to be 0 or 1, the output is 0/-1, which is all
1844        // sign bits set.
1845        if ((KnownZero | APInt(VTBits, 1)) == Mask)
1846          return VTBits;
1847
1848        // If the input is known to be positive (the sign bit is known clear),
1849        // the output of the NEG has the same number of sign bits as the input.
1850        if (KnownZero.isNegative())
1851          return Tmp2;
1852
1853        // Otherwise, we treat this like a SUB.
1854      }
1855
1856    // Sub can have at most one carry bit.  Thus we know that the output
1857    // is, at worst, one more bit than the inputs.
1858    Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1859    if (Tmp == 1) return 1;  // Early out.
1860      return std::min(Tmp, Tmp2)-1;
1861    break;
1862  case ISD::TRUNCATE:
1863    // FIXME: it's tricky to do anything useful for this, but it is an important
1864    // case for targets like X86.
1865    break;
1866  }
1867
1868  // Handle LOADX separately here. EXTLOAD case will fallthrough.
1869  if (Op.getOpcode() == ISD::LOAD) {
1870    LoadSDNode *LD = cast<LoadSDNode>(Op);
1871    unsigned ExtType = LD->getExtensionType();
1872    switch (ExtType) {
1873    default: break;
1874    case ISD::SEXTLOAD:    // '17' bits known
1875      Tmp = LD->getMemoryVT().getSizeInBits();
1876      return VTBits-Tmp+1;
1877    case ISD::ZEXTLOAD:    // '16' bits known
1878      Tmp = LD->getMemoryVT().getSizeInBits();
1879      return VTBits-Tmp;
1880    }
1881  }
1882
1883  // Allow the target to implement this method for its nodes.
1884  if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1885      Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1886      Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1887      Op.getOpcode() == ISD::INTRINSIC_VOID) {
1888    unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
1889    if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
1890  }
1891
1892  // Finally, if we can prove that the top bits of the result are 0's or 1's,
1893  // use this information.
1894  APInt KnownZero, KnownOne;
1895  APInt Mask = APInt::getAllOnesValue(VTBits);
1896  ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1897
1898  if (KnownZero.isNegative()) {        // sign bit is 0
1899    Mask = KnownZero;
1900  } else if (KnownOne.isNegative()) {  // sign bit is 1;
1901    Mask = KnownOne;
1902  } else {
1903    // Nothing known.
1904    return FirstAnswer;
1905  }
1906
1907  // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
1908  // the number of identical bits in the top of the input value.
1909  Mask = ~Mask;
1910  Mask <<= Mask.getBitWidth()-VTBits;
1911  // Return # leading zeros.  We use 'min' here in case Val was zero before
1912  // shifting.  We don't want to return '64' as for an i32 "0".
1913  return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
1914}
1915
1916
1917bool SelectionDAG::isVerifiedDebugInfoDesc(SDOperand Op) const {
1918  GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
1919  if (!GA) return false;
1920  GlobalVariable *GV = dyn_cast<GlobalVariable>(GA->getGlobal());
1921  if (!GV) return false;
1922  MachineModuleInfo *MMI = getMachineModuleInfo();
1923  return MMI && MMI->hasDebugInfo() && MMI->isVerified(GV);
1924}
1925
1926
1927/// getShuffleScalarElt - Returns the scalar element that will make up the ith
1928/// element of the result of the vector shuffle.
1929SDOperand SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned i) {
1930  MVT VT = N->getValueType(0);
1931  SDOperand PermMask = N->getOperand(2);
1932  SDOperand Idx = PermMask.getOperand(i);
1933  if (Idx.getOpcode() == ISD::UNDEF)
1934    return getNode(ISD::UNDEF, VT.getVectorElementType());
1935  unsigned Index = cast<ConstantSDNode>(Idx)->getValue();
1936  unsigned NumElems = PermMask.getNumOperands();
1937  SDOperand V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1);
1938  Index %= NumElems;
1939
1940  if (V.getOpcode() == ISD::BIT_CONVERT) {
1941    V = V.getOperand(0);
1942    if (V.getValueType().getVectorNumElements() != NumElems)
1943      return SDOperand();
1944  }
1945  if (V.getOpcode() == ISD::SCALAR_TO_VECTOR)
1946    return (Index == 0) ? V.getOperand(0)
1947                      : getNode(ISD::UNDEF, VT.getVectorElementType());
1948  if (V.getOpcode() == ISD::BUILD_VECTOR)
1949    return V.getOperand(Index);
1950  if (V.getOpcode() == ISD::VECTOR_SHUFFLE)
1951    return getShuffleScalarElt(V.Val, Index);
1952  return SDOperand();
1953}
1954
1955
1956/// getNode - Gets or creates the specified node.
1957///
1958SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT) {
1959  FoldingSetNodeID ID;
1960  AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
1961  void *IP = 0;
1962  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1963    return SDOperand(E, 0);
1964  SDNode *N = getAllocator().Allocate<SDNode>();
1965  new (N) SDNode(Opcode, SDNode::getSDVTList(VT));
1966  CSEMap.InsertNode(N, IP);
1967
1968  AllNodes.push_back(N);
1969  return SDOperand(N, 0);
1970}
1971
1972SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT, SDOperand Operand) {
1973  // Constant fold unary operations with an integer constant operand.
1974  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
1975    const APInt &Val = C->getAPIntValue();
1976    unsigned BitWidth = VT.getSizeInBits();
1977    switch (Opcode) {
1978    default: break;
1979    case ISD::SIGN_EXTEND:
1980      return getConstant(APInt(Val).sextOrTrunc(BitWidth), VT);
1981    case ISD::ANY_EXTEND:
1982    case ISD::ZERO_EXTEND:
1983    case ISD::TRUNCATE:
1984      return getConstant(APInt(Val).zextOrTrunc(BitWidth), VT);
1985    case ISD::UINT_TO_FP:
1986    case ISD::SINT_TO_FP: {
1987      const uint64_t zero[] = {0, 0};
1988      // No compile time operations on this type.
1989      if (VT==MVT::ppcf128)
1990        break;
1991      APFloat apf = APFloat(APInt(BitWidth, 2, zero));
1992      (void)apf.convertFromAPInt(Val,
1993                                 Opcode==ISD::SINT_TO_FP,
1994                                 APFloat::rmNearestTiesToEven);
1995      return getConstantFP(apf, VT);
1996    }
1997    case ISD::BIT_CONVERT:
1998      if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
1999        return getConstantFP(Val.bitsToFloat(), VT);
2000      else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2001        return getConstantFP(Val.bitsToDouble(), VT);
2002      break;
2003    case ISD::BSWAP:
2004      return getConstant(Val.byteSwap(), VT);
2005    case ISD::CTPOP:
2006      return getConstant(Val.countPopulation(), VT);
2007    case ISD::CTLZ:
2008      return getConstant(Val.countLeadingZeros(), VT);
2009    case ISD::CTTZ:
2010      return getConstant(Val.countTrailingZeros(), VT);
2011    }
2012  }
2013
2014  // Constant fold unary operations with a floating point constant operand.
2015  if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) {
2016    APFloat V = C->getValueAPF();    // make copy
2017    if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2018      switch (Opcode) {
2019      case ISD::FNEG:
2020        V.changeSign();
2021        return getConstantFP(V, VT);
2022      case ISD::FABS:
2023        V.clearSign();
2024        return getConstantFP(V, VT);
2025      case ISD::FP_ROUND:
2026      case ISD::FP_EXTEND:
2027        // This can return overflow, underflow, or inexact; we don't care.
2028        // FIXME need to be more flexible about rounding mode.
2029        (void)V.convert(*MVTToAPFloatSemantics(VT),
2030                        APFloat::rmNearestTiesToEven);
2031        return getConstantFP(V, VT);
2032      case ISD::FP_TO_SINT:
2033      case ISD::FP_TO_UINT: {
2034        integerPart x;
2035        assert(integerPartWidth >= 64);
2036        // FIXME need to be more flexible about rounding mode.
2037        APFloat::opStatus s = V.convertToInteger(&x, 64U,
2038                              Opcode==ISD::FP_TO_SINT,
2039                              APFloat::rmTowardZero);
2040        if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
2041          break;
2042        return getConstant(x, VT);
2043      }
2044      case ISD::BIT_CONVERT:
2045        if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2046          return getConstant((uint32_t)V.convertToAPInt().getZExtValue(), VT);
2047        else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2048          return getConstant(V.convertToAPInt().getZExtValue(), VT);
2049        break;
2050      }
2051    }
2052  }
2053
2054  unsigned OpOpcode = Operand.Val->getOpcode();
2055  switch (Opcode) {
2056  case ISD::TokenFactor:
2057    return Operand;         // Factor of one node?  No need.
2058  case ISD::FP_ROUND: assert(0 && "Invalid method to make FP_ROUND node");
2059  case ISD::FP_EXTEND:
2060    assert(VT.isFloatingPoint() &&
2061           Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2062    if (Operand.getValueType() == VT) return Operand;  // noop conversion.
2063    if (Operand.getOpcode() == ISD::UNDEF)
2064      return getNode(ISD::UNDEF, VT);
2065    break;
2066  case ISD::SIGN_EXTEND:
2067    assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2068           "Invalid SIGN_EXTEND!");
2069    if (Operand.getValueType() == VT) return Operand;   // noop extension
2070    assert(Operand.getValueType().bitsLT(VT)
2071           && "Invalid sext node, dst < src!");
2072    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2073      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
2074    break;
2075  case ISD::ZERO_EXTEND:
2076    assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2077           "Invalid ZERO_EXTEND!");
2078    if (Operand.getValueType() == VT) return Operand;   // noop extension
2079    assert(Operand.getValueType().bitsLT(VT)
2080           && "Invalid zext node, dst < src!");
2081    if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
2082      return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
2083    break;
2084  case ISD::ANY_EXTEND:
2085    assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2086           "Invalid ANY_EXTEND!");
2087    if (Operand.getValueType() == VT) return Operand;   // noop extension
2088    assert(Operand.getValueType().bitsLT(VT)
2089           && "Invalid anyext node, dst < src!");
2090    if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
2091      // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
2092      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
2093    break;
2094  case ISD::TRUNCATE:
2095    assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2096           "Invalid TRUNCATE!");
2097    if (Operand.getValueType() == VT) return Operand;   // noop truncate
2098    assert(Operand.getValueType().bitsGT(VT)
2099           && "Invalid truncate node, src < dst!");
2100    if (OpOpcode == ISD::TRUNCATE)
2101      return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
2102    else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2103             OpOpcode == ISD::ANY_EXTEND) {
2104      // If the source is smaller than the dest, we still need an extend.
2105      if (Operand.Val->getOperand(0).getValueType().bitsLT(VT))
2106        return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
2107      else if (Operand.Val->getOperand(0).getValueType().bitsGT(VT))
2108        return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
2109      else
2110        return Operand.Val->getOperand(0);
2111    }
2112    break;
2113  case ISD::BIT_CONVERT:
2114    // Basic sanity checking.
2115    assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2116           && "Cannot BIT_CONVERT between types of different sizes!");
2117    if (VT == Operand.getValueType()) return Operand;  // noop conversion.
2118    if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
2119      return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
2120    if (OpOpcode == ISD::UNDEF)
2121      return getNode(ISD::UNDEF, VT);
2122    break;
2123  case ISD::SCALAR_TO_VECTOR:
2124    assert(VT.isVector() && !Operand.getValueType().isVector() &&
2125           VT.getVectorElementType() == Operand.getValueType() &&
2126           "Illegal SCALAR_TO_VECTOR node!");
2127    if (OpOpcode == ISD::UNDEF)
2128      return getNode(ISD::UNDEF, VT);
2129    // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2130    if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2131        isa<ConstantSDNode>(Operand.getOperand(1)) &&
2132        Operand.getConstantOperandVal(1) == 0 &&
2133        Operand.getOperand(0).getValueType() == VT)
2134      return Operand.getOperand(0);
2135    break;
2136  case ISD::FNEG:
2137    if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
2138      return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
2139                     Operand.Val->getOperand(0));
2140    if (OpOpcode == ISD::FNEG)  // --X -> X
2141      return Operand.Val->getOperand(0);
2142    break;
2143  case ISD::FABS:
2144    if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
2145      return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
2146    break;
2147  }
2148
2149  SDNode *N;
2150  SDVTList VTs = getVTList(VT);
2151  if (VT != MVT::Flag) { // Don't CSE flag producing nodes
2152    FoldingSetNodeID ID;
2153    SDOperand Ops[1] = { Operand };
2154    AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2155    void *IP = 0;
2156    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2157      return SDOperand(E, 0);
2158    N = getAllocator().Allocate<UnarySDNode>();
2159    new (N) UnarySDNode(Opcode, VTs, Operand);
2160    CSEMap.InsertNode(N, IP);
2161  } else {
2162    N = getAllocator().Allocate<UnarySDNode>();
2163    new (N) UnarySDNode(Opcode, VTs, Operand);
2164  }
2165  AllNodes.push_back(N);
2166  return SDOperand(N, 0);
2167}
2168
2169
2170
2171SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
2172                                SDOperand N1, SDOperand N2) {
2173  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
2174  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
2175  switch (Opcode) {
2176  default: break;
2177  case ISD::TokenFactor:
2178    assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2179           N2.getValueType() == MVT::Other && "Invalid token factor!");
2180    // Fold trivial token factors.
2181    if (N1.getOpcode() == ISD::EntryToken) return N2;
2182    if (N2.getOpcode() == ISD::EntryToken) return N1;
2183    break;
2184  case ISD::AND:
2185    assert(VT.isInteger() && N1.getValueType() == N2.getValueType() &&
2186           N1.getValueType() == VT && "Binary operator types must match!");
2187    // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
2188    // worth handling here.
2189    if (N2C && N2C->isNullValue())
2190      return N2;
2191    if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
2192      return N1;
2193    break;
2194  case ISD::OR:
2195  case ISD::XOR:
2196  case ISD::ADD:
2197  case ISD::SUB:
2198    assert(VT.isInteger() && N1.getValueType() == N2.getValueType() &&
2199           N1.getValueType() == VT && "Binary operator types must match!");
2200    // (X ^|+- 0) -> X.  This commonly occurs when legalizing i64 values, so
2201    // it's worth handling here.
2202    if (N2C && N2C->isNullValue())
2203      return N1;
2204    break;
2205  case ISD::UDIV:
2206  case ISD::UREM:
2207  case ISD::MULHU:
2208  case ISD::MULHS:
2209    assert(VT.isInteger() && "This operator does not apply to FP types!");
2210    // fall through
2211  case ISD::MUL:
2212  case ISD::SDIV:
2213  case ISD::SREM:
2214  case ISD::FADD:
2215  case ISD::FSUB:
2216  case ISD::FMUL:
2217  case ISD::FDIV:
2218  case ISD::FREM:
2219    assert(N1.getValueType() == N2.getValueType() &&
2220           N1.getValueType() == VT && "Binary operator types must match!");
2221    break;
2222  case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
2223    assert(N1.getValueType() == VT &&
2224           N1.getValueType().isFloatingPoint() &&
2225           N2.getValueType().isFloatingPoint() &&
2226           "Invalid FCOPYSIGN!");
2227    break;
2228  case ISD::SHL:
2229  case ISD::SRA:
2230  case ISD::SRL:
2231  case ISD::ROTL:
2232  case ISD::ROTR:
2233    assert(VT == N1.getValueType() &&
2234           "Shift operators return type must be the same as their first arg");
2235    assert(VT.isInteger() && N2.getValueType().isInteger() &&
2236           "Shifts only work on integers");
2237
2238    // Always fold shifts of i1 values so the code generator doesn't need to
2239    // handle them.  Since we know the size of the shift has to be less than the
2240    // size of the value, the shift/rotate count is guaranteed to be zero.
2241    if (VT == MVT::i1)
2242      return N1;
2243    break;
2244  case ISD::FP_ROUND_INREG: {
2245    MVT EVT = cast<VTSDNode>(N2)->getVT();
2246    assert(VT == N1.getValueType() && "Not an inreg round!");
2247    assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2248           "Cannot FP_ROUND_INREG integer types");
2249    assert(EVT.bitsLE(VT) && "Not rounding down!");
2250    if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
2251    break;
2252  }
2253  case ISD::FP_ROUND:
2254    assert(VT.isFloatingPoint() &&
2255           N1.getValueType().isFloatingPoint() &&
2256           VT.bitsLE(N1.getValueType()) &&
2257           isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2258    if (N1.getValueType() == VT) return N1;  // noop conversion.
2259    break;
2260  case ISD::AssertSext:
2261  case ISD::AssertZext: {
2262    MVT EVT = cast<VTSDNode>(N2)->getVT();
2263    assert(VT == N1.getValueType() && "Not an inreg extend!");
2264    assert(VT.isInteger() && EVT.isInteger() &&
2265           "Cannot *_EXTEND_INREG FP types");
2266    assert(EVT.bitsLE(VT) && "Not extending!");
2267    if (VT == EVT) return N1; // noop assertion.
2268    break;
2269  }
2270  case ISD::SIGN_EXTEND_INREG: {
2271    MVT EVT = cast<VTSDNode>(N2)->getVT();
2272    assert(VT == N1.getValueType() && "Not an inreg extend!");
2273    assert(VT.isInteger() && EVT.isInteger() &&
2274           "Cannot *_EXTEND_INREG FP types");
2275    assert(EVT.bitsLE(VT) && "Not extending!");
2276    if (EVT == VT) return N1;  // Not actually extending
2277
2278    if (N1C) {
2279      APInt Val = N1C->getAPIntValue();
2280      unsigned FromBits = cast<VTSDNode>(N2)->getVT().getSizeInBits();
2281      Val <<= Val.getBitWidth()-FromBits;
2282      Val = Val.ashr(Val.getBitWidth()-FromBits);
2283      return getConstant(Val, VT);
2284    }
2285    break;
2286  }
2287  case ISD::EXTRACT_VECTOR_ELT:
2288    assert(N2C && "Bad EXTRACT_VECTOR_ELT!");
2289
2290    // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2291    if (N1.getOpcode() == ISD::UNDEF)
2292      return getNode(ISD::UNDEF, VT);
2293
2294    // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2295    // expanding copies of large vectors from registers.
2296    if (N1.getOpcode() == ISD::CONCAT_VECTORS &&
2297        N1.getNumOperands() > 0) {
2298      unsigned Factor =
2299        N1.getOperand(0).getValueType().getVectorNumElements();
2300      return getNode(ISD::EXTRACT_VECTOR_ELT, VT,
2301                     N1.getOperand(N2C->getValue() / Factor),
2302                     getConstant(N2C->getValue() % Factor, N2.getValueType()));
2303    }
2304
2305    // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2306    // expanding large vector constants.
2307    if (N1.getOpcode() == ISD::BUILD_VECTOR)
2308      return N1.getOperand(N2C->getValue());
2309
2310    // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2311    // operations are lowered to scalars.
2312    if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT)
2313      if (ConstantSDNode *IEC = dyn_cast<ConstantSDNode>(N1.getOperand(2))) {
2314        if (IEC == N2C)
2315          return N1.getOperand(1);
2316        else
2317          return getNode(ISD::EXTRACT_VECTOR_ELT, VT, N1.getOperand(0), N2);
2318      }
2319    break;
2320  case ISD::EXTRACT_ELEMENT:
2321    assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!");
2322    assert(!N1.getValueType().isVector() && !VT.isVector() &&
2323           (N1.getValueType().isInteger() == VT.isInteger()) &&
2324           "Wrong types for EXTRACT_ELEMENT!");
2325
2326    // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2327    // 64-bit integers into 32-bit parts.  Instead of building the extract of
2328    // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2329    if (N1.getOpcode() == ISD::BUILD_PAIR)
2330      return N1.getOperand(N2C->getValue());
2331
2332    // EXTRACT_ELEMENT of a constant int is also very common.
2333    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2334      unsigned ElementSize = VT.getSizeInBits();
2335      unsigned Shift = ElementSize * N2C->getValue();
2336      APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2337      return getConstant(ShiftedVal.trunc(ElementSize), VT);
2338    }
2339    break;
2340  case ISD::EXTRACT_SUBVECTOR:
2341    if (N1.getValueType() == VT) // Trivial extraction.
2342      return N1;
2343    break;
2344  }
2345
2346  if (N1C) {
2347    if (N2C) {
2348      const APInt &C1 = N1C->getAPIntValue(), &C2 = N2C->getAPIntValue();
2349      switch (Opcode) {
2350      case ISD::ADD: return getConstant(C1 + C2, VT);
2351      case ISD::SUB: return getConstant(C1 - C2, VT);
2352      case ISD::MUL: return getConstant(C1 * C2, VT);
2353      case ISD::UDIV:
2354        if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2355        break;
2356      case ISD::UREM :
2357        if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2358        break;
2359      case ISD::SDIV :
2360        if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2361        break;
2362      case ISD::SREM :
2363        if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2364        break;
2365      case ISD::AND  : return getConstant(C1 & C2, VT);
2366      case ISD::OR   : return getConstant(C1 | C2, VT);
2367      case ISD::XOR  : return getConstant(C1 ^ C2, VT);
2368      case ISD::SHL  : return getConstant(C1 << C2, VT);
2369      case ISD::SRL  : return getConstant(C1.lshr(C2), VT);
2370      case ISD::SRA  : return getConstant(C1.ashr(C2), VT);
2371      case ISD::ROTL : return getConstant(C1.rotl(C2), VT);
2372      case ISD::ROTR : return getConstant(C1.rotr(C2), VT);
2373      default: break;
2374      }
2375    } else {      // Cannonicalize constant to RHS if commutative
2376      if (isCommutativeBinOp(Opcode)) {
2377        std::swap(N1C, N2C);
2378        std::swap(N1, N2);
2379      }
2380    }
2381  }
2382
2383  // Constant fold FP operations.
2384  ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
2385  ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
2386  if (N1CFP) {
2387    if (!N2CFP && isCommutativeBinOp(Opcode)) {
2388      // Cannonicalize constant to RHS if commutative
2389      std::swap(N1CFP, N2CFP);
2390      std::swap(N1, N2);
2391    } else if (N2CFP && VT != MVT::ppcf128) {
2392      APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2393      APFloat::opStatus s;
2394      switch (Opcode) {
2395      case ISD::FADD:
2396        s = V1.add(V2, APFloat::rmNearestTiesToEven);
2397        if (s != APFloat::opInvalidOp)
2398          return getConstantFP(V1, VT);
2399        break;
2400      case ISD::FSUB:
2401        s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
2402        if (s!=APFloat::opInvalidOp)
2403          return getConstantFP(V1, VT);
2404        break;
2405      case ISD::FMUL:
2406        s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
2407        if (s!=APFloat::opInvalidOp)
2408          return getConstantFP(V1, VT);
2409        break;
2410      case ISD::FDIV:
2411        s = V1.divide(V2, APFloat::rmNearestTiesToEven);
2412        if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2413          return getConstantFP(V1, VT);
2414        break;
2415      case ISD::FREM :
2416        s = V1.mod(V2, APFloat::rmNearestTiesToEven);
2417        if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2418          return getConstantFP(V1, VT);
2419        break;
2420      case ISD::FCOPYSIGN:
2421        V1.copySign(V2);
2422        return getConstantFP(V1, VT);
2423      default: break;
2424      }
2425    }
2426  }
2427
2428  // Canonicalize an UNDEF to the RHS, even over a constant.
2429  if (N1.getOpcode() == ISD::UNDEF) {
2430    if (isCommutativeBinOp(Opcode)) {
2431      std::swap(N1, N2);
2432    } else {
2433      switch (Opcode) {
2434      case ISD::FP_ROUND_INREG:
2435      case ISD::SIGN_EXTEND_INREG:
2436      case ISD::SUB:
2437      case ISD::FSUB:
2438      case ISD::FDIV:
2439      case ISD::FREM:
2440      case ISD::SRA:
2441        return N1;     // fold op(undef, arg2) -> undef
2442      case ISD::UDIV:
2443      case ISD::SDIV:
2444      case ISD::UREM:
2445      case ISD::SREM:
2446      case ISD::SRL:
2447      case ISD::SHL:
2448        if (!VT.isVector())
2449          return getConstant(0, VT);    // fold op(undef, arg2) -> 0
2450        // For vectors, we can't easily build an all zero vector, just return
2451        // the LHS.
2452        return N2;
2453      }
2454    }
2455  }
2456
2457  // Fold a bunch of operators when the RHS is undef.
2458  if (N2.getOpcode() == ISD::UNDEF) {
2459    switch (Opcode) {
2460    case ISD::XOR:
2461      if (N1.getOpcode() == ISD::UNDEF)
2462        // Handle undef ^ undef -> 0 special case. This is a common
2463        // idiom (misuse).
2464        return getConstant(0, VT);
2465      // fallthrough
2466    case ISD::ADD:
2467    case ISD::ADDC:
2468    case ISD::ADDE:
2469    case ISD::SUB:
2470    case ISD::FADD:
2471    case ISD::FSUB:
2472    case ISD::FMUL:
2473    case ISD::FDIV:
2474    case ISD::FREM:
2475    case ISD::UDIV:
2476    case ISD::SDIV:
2477    case ISD::UREM:
2478    case ISD::SREM:
2479      return N2;       // fold op(arg1, undef) -> undef
2480    case ISD::MUL:
2481    case ISD::AND:
2482    case ISD::SRL:
2483    case ISD::SHL:
2484      if (!VT.isVector())
2485        return getConstant(0, VT);  // fold op(arg1, undef) -> 0
2486      // For vectors, we can't easily build an all zero vector, just return
2487      // the LHS.
2488      return N1;
2489    case ISD::OR:
2490      if (!VT.isVector())
2491        return getConstant(VT.getIntegerVTBitMask(), VT);
2492      // For vectors, we can't easily build an all one vector, just return
2493      // the LHS.
2494      return N1;
2495    case ISD::SRA:
2496      return N1;
2497    }
2498  }
2499
2500  // Memoize this node if possible.
2501  SDNode *N;
2502  SDVTList VTs = getVTList(VT);
2503  if (VT != MVT::Flag) {
2504    SDOperand Ops[] = { N1, N2 };
2505    FoldingSetNodeID ID;
2506    AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
2507    void *IP = 0;
2508    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2509      return SDOperand(E, 0);
2510    N = getAllocator().Allocate<BinarySDNode>();
2511    new (N) BinarySDNode(Opcode, VTs, N1, N2);
2512    CSEMap.InsertNode(N, IP);
2513  } else {
2514    N = getAllocator().Allocate<BinarySDNode>();
2515    new (N) BinarySDNode(Opcode, VTs, N1, N2);
2516  }
2517
2518  AllNodes.push_back(N);
2519  return SDOperand(N, 0);
2520}
2521
2522SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
2523                                SDOperand N1, SDOperand N2, SDOperand N3) {
2524  // Perform various simplifications.
2525  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
2526  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
2527  switch (Opcode) {
2528  case ISD::SETCC: {
2529    // Use FoldSetCC to simplify SETCC's.
2530    SDOperand Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
2531    if (Simp.Val) return Simp;
2532    break;
2533  }
2534  case ISD::SELECT:
2535    if (N1C) {
2536     if (N1C->getValue())
2537        return N2;             // select true, X, Y -> X
2538      else
2539        return N3;             // select false, X, Y -> Y
2540    }
2541
2542    if (N2 == N3) return N2;   // select C, X, X -> X
2543    break;
2544  case ISD::BRCOND:
2545    if (N2C) {
2546      if (N2C->getValue()) // Unconditional branch
2547        return getNode(ISD::BR, MVT::Other, N1, N3);
2548      else
2549        return N1;         // Never-taken branch
2550    }
2551    break;
2552  case ISD::VECTOR_SHUFFLE:
2553    assert(VT == N1.getValueType() && VT == N2.getValueType() &&
2554           VT.isVector() && N3.getValueType().isVector() &&
2555           N3.getOpcode() == ISD::BUILD_VECTOR &&
2556           VT.getVectorNumElements() == N3.getNumOperands() &&
2557           "Illegal VECTOR_SHUFFLE node!");
2558    break;
2559  case ISD::BIT_CONVERT:
2560    // Fold bit_convert nodes from a type to themselves.
2561    if (N1.getValueType() == VT)
2562      return N1;
2563    break;
2564  }
2565
2566  // Memoize node if it doesn't produce a flag.
2567  SDNode *N;
2568  SDVTList VTs = getVTList(VT);
2569  if (VT != MVT::Flag) {
2570    SDOperand Ops[] = { N1, N2, N3 };
2571    FoldingSetNodeID ID;
2572    AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
2573    void *IP = 0;
2574    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2575      return SDOperand(E, 0);
2576    N = getAllocator().Allocate<TernarySDNode>();
2577    new (N) TernarySDNode(Opcode, VTs, N1, N2, N3);
2578    CSEMap.InsertNode(N, IP);
2579  } else {
2580    N = getAllocator().Allocate<TernarySDNode>();
2581    new (N) TernarySDNode(Opcode, VTs, N1, N2, N3);
2582  }
2583  AllNodes.push_back(N);
2584  return SDOperand(N, 0);
2585}
2586
2587SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
2588                                SDOperand N1, SDOperand N2, SDOperand N3,
2589                                SDOperand N4) {
2590  SDOperand Ops[] = { N1, N2, N3, N4 };
2591  return getNode(Opcode, VT, Ops, 4);
2592}
2593
2594SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
2595                                SDOperand N1, SDOperand N2, SDOperand N3,
2596                                SDOperand N4, SDOperand N5) {
2597  SDOperand Ops[] = { N1, N2, N3, N4, N5 };
2598  return getNode(Opcode, VT, Ops, 5);
2599}
2600
2601/// getMemsetValue - Vectorized representation of the memset value
2602/// operand.
2603static SDOperand getMemsetValue(SDOperand Value, MVT VT, SelectionDAG &DAG) {
2604  unsigned NumBits = VT.isVector() ?
2605    VT.getVectorElementType().getSizeInBits() : VT.getSizeInBits();
2606  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
2607    APInt Val = APInt(NumBits, C->getValue() & 255);
2608    unsigned Shift = 8;
2609    for (unsigned i = NumBits; i > 8; i >>= 1) {
2610      Val = (Val << Shift) | Val;
2611      Shift <<= 1;
2612    }
2613    if (VT.isInteger())
2614      return DAG.getConstant(Val, VT);
2615    return DAG.getConstantFP(APFloat(Val), VT);
2616  }
2617
2618  Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
2619  unsigned Shift = 8;
2620  for (unsigned i = NumBits; i > 8; i >>= 1) {
2621    Value = DAG.getNode(ISD::OR, VT,
2622                        DAG.getNode(ISD::SHL, VT, Value,
2623                                    DAG.getConstant(Shift, MVT::i8)), Value);
2624    Shift <<= 1;
2625  }
2626
2627  return Value;
2628}
2629
2630/// getMemsetStringVal - Similar to getMemsetValue. Except this is only
2631/// used when a memcpy is turned into a memset when the source is a constant
2632/// string ptr.
2633static SDOperand getMemsetStringVal(MVT VT, SelectionDAG &DAG,
2634                                    const TargetLowering &TLI,
2635                                    std::string &Str, unsigned Offset) {
2636  // Handle vector with all elements zero.
2637  if (Str.empty()) {
2638    if (VT.isInteger())
2639      return DAG.getConstant(0, VT);
2640    unsigned NumElts = VT.getVectorNumElements();
2641    MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
2642    return DAG.getNode(ISD::BIT_CONVERT, VT,
2643                       DAG.getConstant(0, MVT::getVectorVT(EltVT, NumElts)));
2644  }
2645
2646  assert(!VT.isVector() && "Can't handle vector type here!");
2647  unsigned NumBits = VT.getSizeInBits();
2648  unsigned MSB = NumBits / 8;
2649  uint64_t Val = 0;
2650  if (TLI.isLittleEndian())
2651    Offset = Offset + MSB - 1;
2652  for (unsigned i = 0; i != MSB; ++i) {
2653    Val = (Val << 8) | (unsigned char)Str[Offset];
2654    Offset += TLI.isLittleEndian() ? -1 : 1;
2655  }
2656  return DAG.getConstant(Val, VT);
2657}
2658
2659/// getMemBasePlusOffset - Returns base and offset node for the
2660///
2661static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
2662                                      SelectionDAG &DAG) {
2663  MVT VT = Base.getValueType();
2664  return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
2665}
2666
2667/// isMemSrcFromString - Returns true if memcpy source is a string constant.
2668///
2669static bool isMemSrcFromString(SDOperand Src, std::string &Str) {
2670  unsigned SrcDelta = 0;
2671  GlobalAddressSDNode *G = NULL;
2672  if (Src.getOpcode() == ISD::GlobalAddress)
2673    G = cast<GlobalAddressSDNode>(Src);
2674  else if (Src.getOpcode() == ISD::ADD &&
2675           Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
2676           Src.getOperand(1).getOpcode() == ISD::Constant) {
2677    G = cast<GlobalAddressSDNode>(Src.getOperand(0));
2678    SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getValue();
2679  }
2680  if (!G)
2681    return false;
2682
2683  GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
2684  if (GV && GetConstantStringInfo(GV, Str, SrcDelta, false))
2685    return true;
2686
2687  return false;
2688}
2689
2690/// MeetsMaxMemopRequirement - Determines if the number of memory ops required
2691/// to replace the memset / memcpy is below the threshold. It also returns the
2692/// types of the sequence of memory ops to perform memset / memcpy.
2693static
2694bool MeetsMaxMemopRequirement(std::vector<MVT> &MemOps,
2695                              SDOperand Dst, SDOperand Src,
2696                              unsigned Limit, uint64_t Size, unsigned &Align,
2697                              std::string &Str, bool &isSrcStr,
2698                              SelectionDAG &DAG,
2699                              const TargetLowering &TLI) {
2700  isSrcStr = isMemSrcFromString(Src, Str);
2701  bool isSrcConst = isa<ConstantSDNode>(Src);
2702  bool AllowUnalign = TLI.allowsUnalignedMemoryAccesses();
2703  MVT VT= TLI.getOptimalMemOpType(Size, Align, isSrcConst, isSrcStr);
2704  if (VT != MVT::iAny) {
2705    unsigned NewAlign = (unsigned)
2706      TLI.getTargetData()->getABITypeAlignment(VT.getTypeForMVT());
2707    // If source is a string constant, this will require an unaligned load.
2708    if (NewAlign > Align && (isSrcConst || AllowUnalign)) {
2709      if (Dst.getOpcode() != ISD::FrameIndex) {
2710        // Can't change destination alignment. It requires a unaligned store.
2711        if (AllowUnalign)
2712          VT = MVT::iAny;
2713      } else {
2714        int FI = cast<FrameIndexSDNode>(Dst)->getIndex();
2715        MachineFrameInfo *MFI = DAG.getMachineFunction().getFrameInfo();
2716        if (MFI->isFixedObjectIndex(FI)) {
2717          // Can't change destination alignment. It requires a unaligned store.
2718          if (AllowUnalign)
2719            VT = MVT::iAny;
2720        } else {
2721          // Give the stack frame object a larger alignment if needed.
2722          if (MFI->getObjectAlignment(FI) < NewAlign)
2723            MFI->setObjectAlignment(FI, NewAlign);
2724          Align = NewAlign;
2725        }
2726      }
2727    }
2728  }
2729
2730  if (VT == MVT::iAny) {
2731    if (AllowUnalign) {
2732      VT = MVT::i64;
2733    } else {
2734      switch (Align & 7) {
2735      case 0:  VT = MVT::i64; break;
2736      case 4:  VT = MVT::i32; break;
2737      case 2:  VT = MVT::i16; break;
2738      default: VT = MVT::i8;  break;
2739      }
2740    }
2741
2742    MVT LVT = MVT::i64;
2743    while (!TLI.isTypeLegal(LVT))
2744      LVT = (MVT::SimpleValueType)(LVT.getSimpleVT() - 1);
2745    assert(LVT.isInteger());
2746
2747    if (VT.bitsGT(LVT))
2748      VT = LVT;
2749  }
2750
2751  unsigned NumMemOps = 0;
2752  while (Size != 0) {
2753    unsigned VTSize = VT.getSizeInBits() / 8;
2754    while (VTSize > Size) {
2755      // For now, only use non-vector load / store's for the left-over pieces.
2756      if (VT.isVector()) {
2757        VT = MVT::i64;
2758        while (!TLI.isTypeLegal(VT))
2759          VT = (MVT::SimpleValueType)(VT.getSimpleVT() - 1);
2760        VTSize = VT.getSizeInBits() / 8;
2761      } else {
2762        VT = (MVT::SimpleValueType)(VT.getSimpleVT() - 1);
2763        VTSize >>= 1;
2764      }
2765    }
2766
2767    if (++NumMemOps > Limit)
2768      return false;
2769    MemOps.push_back(VT);
2770    Size -= VTSize;
2771  }
2772
2773  return true;
2774}
2775
2776static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG,
2777                                         SDOperand Chain, SDOperand Dst,
2778                                         SDOperand Src, uint64_t Size,
2779                                         unsigned Align, bool AlwaysInline,
2780                                         const Value *DstSV, uint64_t DstSVOff,
2781                                         const Value *SrcSV, uint64_t SrcSVOff){
2782  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2783
2784  // Expand memcpy to a series of load and store ops if the size operand falls
2785  // below a certain threshold.
2786  std::vector<MVT> MemOps;
2787  uint64_t Limit = -1;
2788  if (!AlwaysInline)
2789    Limit = TLI.getMaxStoresPerMemcpy();
2790  unsigned DstAlign = Align;  // Destination alignment can change.
2791  std::string Str;
2792  bool CopyFromStr;
2793  if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign,
2794                                Str, CopyFromStr, DAG, TLI))
2795    return SDOperand();
2796
2797
2798  bool isZeroStr = CopyFromStr && Str.empty();
2799  SmallVector<SDOperand, 8> OutChains;
2800  unsigned NumMemOps = MemOps.size();
2801  uint64_t SrcOff = 0, DstOff = 0;
2802  for (unsigned i = 0; i < NumMemOps; i++) {
2803    MVT VT = MemOps[i];
2804    unsigned VTSize = VT.getSizeInBits() / 8;
2805    SDOperand Value, Store;
2806
2807    if (CopyFromStr && (isZeroStr || !VT.isVector())) {
2808      // It's unlikely a store of a vector immediate can be done in a single
2809      // instruction. It would require a load from a constantpool first.
2810      // We also handle store a vector with all zero's.
2811      // FIXME: Handle other cases where store of vector immediate is done in
2812      // a single instruction.
2813      Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
2814      Store = DAG.getStore(Chain, Value,
2815                           getMemBasePlusOffset(Dst, DstOff, DAG),
2816                           DstSV, DstSVOff + DstOff, false, DstAlign);
2817    } else {
2818      Value = DAG.getLoad(VT, Chain,
2819                          getMemBasePlusOffset(Src, SrcOff, DAG),
2820                          SrcSV, SrcSVOff + SrcOff, false, Align);
2821      Store = DAG.getStore(Chain, Value,
2822                           getMemBasePlusOffset(Dst, DstOff, DAG),
2823                           DstSV, DstSVOff + DstOff, false, DstAlign);
2824    }
2825    OutChains.push_back(Store);
2826    SrcOff += VTSize;
2827    DstOff += VTSize;
2828  }
2829
2830  return DAG.getNode(ISD::TokenFactor, MVT::Other,
2831                     &OutChains[0], OutChains.size());
2832}
2833
2834static SDOperand getMemmoveLoadsAndStores(SelectionDAG &DAG,
2835                                          SDOperand Chain, SDOperand Dst,
2836                                          SDOperand Src, uint64_t Size,
2837                                          unsigned Align, bool AlwaysInline,
2838                                          const Value *DstSV, uint64_t DstSVOff,
2839                                          const Value *SrcSV, uint64_t SrcSVOff){
2840  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2841
2842  // Expand memmove to a series of load and store ops if the size operand falls
2843  // below a certain threshold.
2844  std::vector<MVT> MemOps;
2845  uint64_t Limit = -1;
2846  if (!AlwaysInline)
2847    Limit = TLI.getMaxStoresPerMemmove();
2848  unsigned DstAlign = Align;  // Destination alignment can change.
2849  std::string Str;
2850  bool CopyFromStr;
2851  if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign,
2852                                Str, CopyFromStr, DAG, TLI))
2853    return SDOperand();
2854
2855  uint64_t SrcOff = 0, DstOff = 0;
2856
2857  SmallVector<SDOperand, 8> LoadValues;
2858  SmallVector<SDOperand, 8> LoadChains;
2859  SmallVector<SDOperand, 8> OutChains;
2860  unsigned NumMemOps = MemOps.size();
2861  for (unsigned i = 0; i < NumMemOps; i++) {
2862    MVT VT = MemOps[i];
2863    unsigned VTSize = VT.getSizeInBits() / 8;
2864    SDOperand Value, Store;
2865
2866    Value = DAG.getLoad(VT, Chain,
2867                        getMemBasePlusOffset(Src, SrcOff, DAG),
2868                        SrcSV, SrcSVOff + SrcOff, false, Align);
2869    LoadValues.push_back(Value);
2870    LoadChains.push_back(Value.getValue(1));
2871    SrcOff += VTSize;
2872  }
2873  Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
2874                      &LoadChains[0], LoadChains.size());
2875  OutChains.clear();
2876  for (unsigned i = 0; i < NumMemOps; i++) {
2877    MVT VT = MemOps[i];
2878    unsigned VTSize = VT.getSizeInBits() / 8;
2879    SDOperand Value, Store;
2880
2881    Store = DAG.getStore(Chain, LoadValues[i],
2882                         getMemBasePlusOffset(Dst, DstOff, DAG),
2883                         DstSV, DstSVOff + DstOff, false, DstAlign);
2884    OutChains.push_back(Store);
2885    DstOff += VTSize;
2886  }
2887
2888  return DAG.getNode(ISD::TokenFactor, MVT::Other,
2889                     &OutChains[0], OutChains.size());
2890}
2891
2892static SDOperand getMemsetStores(SelectionDAG &DAG,
2893                                 SDOperand Chain, SDOperand Dst,
2894                                 SDOperand Src, uint64_t Size,
2895                                 unsigned Align,
2896                                 const Value *DstSV, uint64_t DstSVOff) {
2897  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2898
2899  // Expand memset to a series of load/store ops if the size operand
2900  // falls below a certain threshold.
2901  std::vector<MVT> MemOps;
2902  std::string Str;
2903  bool CopyFromStr;
2904  if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, TLI.getMaxStoresPerMemset(),
2905                                Size, Align, Str, CopyFromStr, DAG, TLI))
2906    return SDOperand();
2907
2908  SmallVector<SDOperand, 8> OutChains;
2909  uint64_t DstOff = 0;
2910
2911  unsigned NumMemOps = MemOps.size();
2912  for (unsigned i = 0; i < NumMemOps; i++) {
2913    MVT VT = MemOps[i];
2914    unsigned VTSize = VT.getSizeInBits() / 8;
2915    SDOperand Value = getMemsetValue(Src, VT, DAG);
2916    SDOperand Store = DAG.getStore(Chain, Value,
2917                                   getMemBasePlusOffset(Dst, DstOff, DAG),
2918                                   DstSV, DstSVOff + DstOff);
2919    OutChains.push_back(Store);
2920    DstOff += VTSize;
2921  }
2922
2923  return DAG.getNode(ISD::TokenFactor, MVT::Other,
2924                     &OutChains[0], OutChains.size());
2925}
2926
2927SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand Dst,
2928                                  SDOperand Src, SDOperand Size,
2929                                  unsigned Align, bool AlwaysInline,
2930                                  const Value *DstSV, uint64_t DstSVOff,
2931                                  const Value *SrcSV, uint64_t SrcSVOff) {
2932
2933  // Check to see if we should lower the memcpy to loads and stores first.
2934  // For cases within the target-specified limits, this is the best choice.
2935  ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2936  if (ConstantSize) {
2937    // Memcpy with size zero? Just return the original chain.
2938    if (ConstantSize->isNullValue())
2939      return Chain;
2940
2941    SDOperand Result =
2942      getMemcpyLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(),
2943                              Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff);
2944    if (Result.Val)
2945      return Result;
2946  }
2947
2948  // Then check to see if we should lower the memcpy with target-specific
2949  // code. If the target chooses to do this, this is the next best.
2950  SDOperand Result =
2951    TLI.EmitTargetCodeForMemcpy(*this, Chain, Dst, Src, Size, Align,
2952                                AlwaysInline,
2953                                DstSV, DstSVOff, SrcSV, SrcSVOff);
2954  if (Result.Val)
2955    return Result;
2956
2957  // If we really need inline code and the target declined to provide it,
2958  // use a (potentially long) sequence of loads and stores.
2959  if (AlwaysInline) {
2960    assert(ConstantSize && "AlwaysInline requires a constant size!");
2961    return getMemcpyLoadsAndStores(*this, Chain, Dst, Src,
2962                                   ConstantSize->getValue(), Align, true,
2963                                   DstSV, DstSVOff, SrcSV, SrcSVOff);
2964  }
2965
2966  // Emit a library call.
2967  TargetLowering::ArgListTy Args;
2968  TargetLowering::ArgListEntry Entry;
2969  Entry.Ty = TLI.getTargetData()->getIntPtrType();
2970  Entry.Node = Dst; Args.push_back(Entry);
2971  Entry.Node = Src; Args.push_back(Entry);
2972  Entry.Node = Size; Args.push_back(Entry);
2973  std::pair<SDOperand,SDOperand> CallResult =
2974    TLI.LowerCallTo(Chain, Type::VoidTy,
2975                    false, false, false, CallingConv::C, false,
2976                    getExternalSymbol("memcpy", TLI.getPointerTy()),
2977                    Args, *this);
2978  return CallResult.second;
2979}
2980
2981SDOperand SelectionDAG::getMemmove(SDOperand Chain, SDOperand Dst,
2982                                   SDOperand Src, SDOperand Size,
2983                                   unsigned Align,
2984                                   const Value *DstSV, uint64_t DstSVOff,
2985                                   const Value *SrcSV, uint64_t SrcSVOff) {
2986
2987  // Check to see if we should lower the memmove to loads and stores first.
2988  // For cases within the target-specified limits, this is the best choice.
2989  ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2990  if (ConstantSize) {
2991    // Memmove with size zero? Just return the original chain.
2992    if (ConstantSize->isNullValue())
2993      return Chain;
2994
2995    SDOperand Result =
2996      getMemmoveLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(),
2997                               Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff);
2998    if (Result.Val)
2999      return Result;
3000  }
3001
3002  // Then check to see if we should lower the memmove with target-specific
3003  // code. If the target chooses to do this, this is the next best.
3004  SDOperand Result =
3005    TLI.EmitTargetCodeForMemmove(*this, Chain, Dst, Src, Size, Align,
3006                                 DstSV, DstSVOff, SrcSV, SrcSVOff);
3007  if (Result.Val)
3008    return Result;
3009
3010  // Emit a library call.
3011  TargetLowering::ArgListTy Args;
3012  TargetLowering::ArgListEntry Entry;
3013  Entry.Ty = TLI.getTargetData()->getIntPtrType();
3014  Entry.Node = Dst; Args.push_back(Entry);
3015  Entry.Node = Src; Args.push_back(Entry);
3016  Entry.Node = Size; Args.push_back(Entry);
3017  std::pair<SDOperand,SDOperand> CallResult =
3018    TLI.LowerCallTo(Chain, Type::VoidTy,
3019                    false, false, false, CallingConv::C, false,
3020                    getExternalSymbol("memmove", TLI.getPointerTy()),
3021                    Args, *this);
3022  return CallResult.second;
3023}
3024
3025SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst,
3026                                  SDOperand Src, SDOperand Size,
3027                                  unsigned Align,
3028                                  const Value *DstSV, uint64_t DstSVOff) {
3029
3030  // Check to see if we should lower the memset to stores first.
3031  // For cases within the target-specified limits, this is the best choice.
3032  ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3033  if (ConstantSize) {
3034    // Memset with size zero? Just return the original chain.
3035    if (ConstantSize->isNullValue())
3036      return Chain;
3037
3038    SDOperand Result =
3039      getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getValue(), Align,
3040                      DstSV, DstSVOff);
3041    if (Result.Val)
3042      return Result;
3043  }
3044
3045  // Then check to see if we should lower the memset with target-specific
3046  // code. If the target chooses to do this, this is the next best.
3047  SDOperand Result =
3048    TLI.EmitTargetCodeForMemset(*this, Chain, Dst, Src, Size, Align,
3049                                DstSV, DstSVOff);
3050  if (Result.Val)
3051    return Result;
3052
3053  // Emit a library call.
3054  const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType();
3055  TargetLowering::ArgListTy Args;
3056  TargetLowering::ArgListEntry Entry;
3057  Entry.Node = Dst; Entry.Ty = IntPtrTy;
3058  Args.push_back(Entry);
3059  // Extend or truncate the argument to be an i32 value for the call.
3060  if (Src.getValueType().bitsGT(MVT::i32))
3061    Src = getNode(ISD::TRUNCATE, MVT::i32, Src);
3062  else
3063    Src = getNode(ISD::ZERO_EXTEND, MVT::i32, Src);
3064  Entry.Node = Src; Entry.Ty = Type::Int32Ty; Entry.isSExt = true;
3065  Args.push_back(Entry);
3066  Entry.Node = Size; Entry.Ty = IntPtrTy; Entry.isSExt = false;
3067  Args.push_back(Entry);
3068  std::pair<SDOperand,SDOperand> CallResult =
3069    TLI.LowerCallTo(Chain, Type::VoidTy,
3070                    false, false, false, CallingConv::C, false,
3071                    getExternalSymbol("memset", TLI.getPointerTy()),
3072                    Args, *this);
3073  return CallResult.second;
3074}
3075
3076SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
3077                                  SDOperand Ptr, SDOperand Cmp,
3078                                  SDOperand Swp, const Value* PtrVal,
3079                                  unsigned Alignment) {
3080  assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3081  assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3082
3083  MVT VT = Cmp.getValueType();
3084
3085  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
3086    Alignment = getMVTAlignment(VT);
3087
3088  SDVTList VTs = getVTList(VT, MVT::Other);
3089  FoldingSetNodeID ID;
3090  SDOperand Ops[] = {Chain, Ptr, Cmp, Swp};
3091  AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3092  void* IP = 0;
3093  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3094    return SDOperand(E, 0);
3095  SDNode* N = getAllocator().Allocate<AtomicSDNode>();
3096  new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, PtrVal, Alignment);
3097  CSEMap.InsertNode(N, IP);
3098  AllNodes.push_back(N);
3099  return SDOperand(N, 0);
3100}
3101
3102SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
3103                                  SDOperand Ptr, SDOperand Val,
3104                                  const Value* PtrVal,
3105                                  unsigned Alignment) {
3106  assert((   Opcode == ISD::ATOMIC_LOAD_ADD || Opcode == ISD::ATOMIC_LOAD_SUB
3107          || Opcode == ISD::ATOMIC_SWAP || Opcode == ISD::ATOMIC_LOAD_AND
3108          || Opcode == ISD::ATOMIC_LOAD_OR || Opcode == ISD::ATOMIC_LOAD_XOR
3109          || Opcode == ISD::ATOMIC_LOAD_NAND
3110          || Opcode == ISD::ATOMIC_LOAD_MIN || Opcode == ISD::ATOMIC_LOAD_MAX
3111          || Opcode == ISD::ATOMIC_LOAD_UMIN || Opcode == ISD::ATOMIC_LOAD_UMAX)
3112         && "Invalid Atomic Op");
3113
3114  MVT VT = Val.getValueType();
3115
3116  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
3117    Alignment = getMVTAlignment(VT);
3118
3119  SDVTList VTs = getVTList(VT, MVT::Other);
3120  FoldingSetNodeID ID;
3121  SDOperand Ops[] = {Chain, Ptr, Val};
3122  AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3123  void* IP = 0;
3124  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3125    return SDOperand(E, 0);
3126  SDNode* N = getAllocator().Allocate<AtomicSDNode>();
3127  new (N) AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, PtrVal, Alignment);
3128  CSEMap.InsertNode(N, IP);
3129  AllNodes.push_back(N);
3130  return SDOperand(N, 0);
3131}
3132
3133/// getMergeValues - Create a MERGE_VALUES node from the given operands.
3134/// Allowed to return something different (and simpler) if Simplify is true.
3135SDOperand SelectionDAG::getMergeValues(const SDOperand *Ops, unsigned NumOps,
3136                                       bool Simplify) {
3137  if (Simplify && NumOps == 1)
3138    return Ops[0];
3139
3140  SmallVector<MVT, 4> VTs;
3141  VTs.reserve(NumOps);
3142  for (unsigned i = 0; i < NumOps; ++i)
3143    VTs.push_back(Ops[i].getValueType());
3144  return getNode(ISD::MERGE_VALUES, getVTList(&VTs[0], NumOps), Ops, NumOps);
3145}
3146
3147SDOperand
3148SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
3149                      MVT VT, SDOperand Chain,
3150                      SDOperand Ptr, SDOperand Offset,
3151                      const Value *SV, int SVOffset, MVT EVT,
3152                      bool isVolatile, unsigned Alignment) {
3153  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
3154    Alignment = getMVTAlignment(VT);
3155
3156  if (VT == EVT) {
3157    ExtType = ISD::NON_EXTLOAD;
3158  } else if (ExtType == ISD::NON_EXTLOAD) {
3159    assert(VT == EVT && "Non-extending load from different memory type!");
3160  } else {
3161    // Extending load.
3162    if (VT.isVector())
3163      assert(EVT == VT.getVectorElementType() && "Invalid vector extload!");
3164    else
3165      assert(EVT.bitsLT(VT) &&
3166             "Should only be an extending load, not truncating!");
3167    assert((ExtType == ISD::EXTLOAD || VT.isInteger()) &&
3168           "Cannot sign/zero extend a FP/Vector load!");
3169    assert(VT.isInteger() == EVT.isInteger() &&
3170           "Cannot convert from FP to Int or Int -> FP!");
3171  }
3172
3173  bool Indexed = AM != ISD::UNINDEXED;
3174  assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
3175         "Unindexed load with an offset!");
3176
3177  SDVTList VTs = Indexed ?
3178    getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
3179  SDOperand Ops[] = { Chain, Ptr, Offset };
3180  FoldingSetNodeID ID;
3181  AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
3182  ID.AddInteger(AM);
3183  ID.AddInteger(ExtType);
3184  ID.AddInteger(EVT.getRawBits());
3185  ID.AddInteger(Alignment);
3186  ID.AddInteger(isVolatile);
3187  void *IP = 0;
3188  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3189    return SDOperand(E, 0);
3190  SDNode *N = getAllocator().Allocate<LoadSDNode>();
3191  new (N) LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset,
3192                     Alignment, isVolatile);
3193  CSEMap.InsertNode(N, IP);
3194  AllNodes.push_back(N);
3195  return SDOperand(N, 0);
3196}
3197
3198SDOperand SelectionDAG::getLoad(MVT VT,
3199                                SDOperand Chain, SDOperand Ptr,
3200                                const Value *SV, int SVOffset,
3201                                bool isVolatile, unsigned Alignment) {
3202  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
3203  return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef,
3204                 SV, SVOffset, VT, isVolatile, Alignment);
3205}
3206
3207SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT VT,
3208                                   SDOperand Chain, SDOperand Ptr,
3209                                   const Value *SV,
3210                                   int SVOffset, MVT EVT,
3211                                   bool isVolatile, unsigned Alignment) {
3212  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
3213  return getLoad(ISD::UNINDEXED, ExtType, VT, Chain, Ptr, Undef,
3214                 SV, SVOffset, EVT, isVolatile, Alignment);
3215}
3216
3217SDOperand
3218SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base,
3219                             SDOperand Offset, ISD::MemIndexedMode AM) {
3220  LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
3221  assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
3222         "Load is already a indexed load!");
3223  return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(),
3224                 LD->getChain(), Base, Offset, LD->getSrcValue(),
3225                 LD->getSrcValueOffset(), LD->getMemoryVT(),
3226                 LD->isVolatile(), LD->getAlignment());
3227}
3228
3229SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val,
3230                                 SDOperand Ptr, const Value *SV, int SVOffset,
3231                                 bool isVolatile, unsigned Alignment) {
3232  MVT VT = Val.getValueType();
3233
3234  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
3235    Alignment = getMVTAlignment(VT);
3236
3237  SDVTList VTs = getVTList(MVT::Other);
3238  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
3239  SDOperand Ops[] = { Chain, Val, Ptr, Undef };
3240  FoldingSetNodeID ID;
3241  AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
3242  ID.AddInteger(ISD::UNINDEXED);
3243  ID.AddInteger(false);
3244  ID.AddInteger(VT.getRawBits());
3245  ID.AddInteger(Alignment);
3246  ID.AddInteger(isVolatile);
3247  void *IP = 0;
3248  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3249    return SDOperand(E, 0);
3250  SDNode *N = getAllocator().Allocate<StoreSDNode>();
3251  new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, false,
3252                      VT, SV, SVOffset, Alignment, isVolatile);
3253  CSEMap.InsertNode(N, IP);
3254  AllNodes.push_back(N);
3255  return SDOperand(N, 0);
3256}
3257
3258SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val,
3259                                      SDOperand Ptr, const Value *SV,
3260                                      int SVOffset, MVT SVT,
3261                                      bool isVolatile, unsigned Alignment) {
3262  MVT VT = Val.getValueType();
3263
3264  if (VT == SVT)
3265    return getStore(Chain, Val, Ptr, SV, SVOffset, isVolatile, Alignment);
3266
3267  assert(VT.bitsGT(SVT) && "Not a truncation?");
3268  assert(VT.isInteger() == SVT.isInteger() &&
3269         "Can't do FP-INT conversion!");
3270
3271  if (Alignment == 0)  // Ensure that codegen never sees alignment 0
3272    Alignment = getMVTAlignment(VT);
3273
3274  SDVTList VTs = getVTList(MVT::Other);
3275  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
3276  SDOperand Ops[] = { Chain, Val, Ptr, Undef };
3277  FoldingSetNodeID ID;
3278  AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
3279  ID.AddInteger(ISD::UNINDEXED);
3280  ID.AddInteger(1);
3281  ID.AddInteger(SVT.getRawBits());
3282  ID.AddInteger(Alignment);
3283  ID.AddInteger(isVolatile);
3284  void *IP = 0;
3285  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3286    return SDOperand(E, 0);
3287  SDNode *N = getAllocator().Allocate<StoreSDNode>();
3288  new (N) StoreSDNode(Ops, VTs, ISD::UNINDEXED, true,
3289                      SVT, SV, SVOffset, Alignment, isVolatile);
3290  CSEMap.InsertNode(N, IP);
3291  AllNodes.push_back(N);
3292  return SDOperand(N, 0);
3293}
3294
3295SDOperand
3296SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base,
3297                              SDOperand Offset, ISD::MemIndexedMode AM) {
3298  StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
3299  assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
3300         "Store is already a indexed store!");
3301  SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
3302  SDOperand Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
3303  FoldingSetNodeID ID;
3304  AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
3305  ID.AddInteger(AM);
3306  ID.AddInteger(ST->isTruncatingStore());
3307  ID.AddInteger(ST->getMemoryVT().getRawBits());
3308  ID.AddInteger(ST->getAlignment());
3309  ID.AddInteger(ST->isVolatile());
3310  void *IP = 0;
3311  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3312    return SDOperand(E, 0);
3313  SDNode *N = getAllocator().Allocate<StoreSDNode>();
3314  new (N) StoreSDNode(Ops, VTs, AM,
3315                      ST->isTruncatingStore(), ST->getMemoryVT(),
3316                      ST->getSrcValue(), ST->getSrcValueOffset(),
3317                      ST->getAlignment(), ST->isVolatile());
3318  CSEMap.InsertNode(N, IP);
3319  AllNodes.push_back(N);
3320  return SDOperand(N, 0);
3321}
3322
3323SDOperand SelectionDAG::getVAArg(MVT VT,
3324                                 SDOperand Chain, SDOperand Ptr,
3325                                 SDOperand SV) {
3326  SDOperand Ops[] = { Chain, Ptr, SV };
3327  return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3);
3328}
3329
3330SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
3331                                const SDUse *Ops, unsigned NumOps) {
3332  switch (NumOps) {
3333  case 0: return getNode(Opcode, VT);
3334  case 1: return getNode(Opcode, VT, Ops[0].getSDOperand());
3335  case 2: return getNode(Opcode, VT, Ops[0].getSDOperand(),
3336                         Ops[1].getSDOperand());
3337  case 3: return getNode(Opcode, VT, Ops[0].getSDOperand(),
3338                         Ops[1].getSDOperand(), Ops[2].getSDOperand());
3339  default: break;
3340  }
3341
3342  // Copy from an SDUse array into an SDOperand array for use with
3343  // the regular getNode logic.
3344  SmallVector<SDOperand, 8> NewOps;
3345  NewOps.reserve(NumOps);
3346  for (unsigned i = 0; i != NumOps; ++i)
3347    NewOps.push_back(Ops[i].getSDOperand());
3348  return getNode(Opcode, VT, Ops, NumOps);
3349}
3350
3351SDOperand SelectionDAG::getNode(unsigned Opcode, MVT VT,
3352                                const SDOperand *Ops, unsigned NumOps) {
3353  switch (NumOps) {
3354  case 0: return getNode(Opcode, VT);
3355  case 1: return getNode(Opcode, VT, Ops[0]);
3356  case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
3357  case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
3358  default: break;
3359  }
3360
3361  switch (Opcode) {
3362  default: break;
3363  case ISD::SELECT_CC: {
3364    assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
3365    assert(Ops[0].getValueType() == Ops[1].getValueType() &&
3366           "LHS and RHS of condition must have same type!");
3367    assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3368           "True and False arms of SelectCC must have same type!");
3369    assert(Ops[2].getValueType() == VT &&
3370           "select_cc node must be of same type as true and false value!");
3371    break;
3372  }
3373  case ISD::BR_CC: {
3374    assert(NumOps == 5 && "BR_CC takes 5 operands!");
3375    assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3376           "LHS/RHS of comparison should match types!");
3377    break;
3378  }
3379  }
3380
3381  // Memoize nodes.
3382  SDNode *N;
3383  SDVTList VTs = getVTList(VT);
3384  if (VT != MVT::Flag) {
3385    FoldingSetNodeID ID;
3386    AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
3387    void *IP = 0;
3388    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3389      return SDOperand(E, 0);
3390    N = getAllocator().Allocate<SDNode>();
3391    new (N) SDNode(Opcode, VTs, Ops, NumOps);
3392    CSEMap.InsertNode(N, IP);
3393  } else {
3394    N = getAllocator().Allocate<SDNode>();
3395    new (N) SDNode(Opcode, VTs, Ops, NumOps);
3396  }
3397  AllNodes.push_back(N);
3398  return SDOperand(N, 0);
3399}
3400
3401SDOperand SelectionDAG::getNode(unsigned Opcode,
3402                                const std::vector<MVT> &ResultTys,
3403                                const SDOperand *Ops, unsigned NumOps) {
3404  return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(),
3405                 Ops, NumOps);
3406}
3407
3408SDOperand SelectionDAG::getNode(unsigned Opcode,
3409                                const MVT *VTs, unsigned NumVTs,
3410                                const SDOperand *Ops, unsigned NumOps) {
3411  if (NumVTs == 1)
3412    return getNode(Opcode, VTs[0], Ops, NumOps);
3413  return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps);
3414}
3415
3416SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3417                                const SDOperand *Ops, unsigned NumOps) {
3418  if (VTList.NumVTs == 1)
3419    return getNode(Opcode, VTList.VTs[0], Ops, NumOps);
3420
3421  switch (Opcode) {
3422  // FIXME: figure out how to safely handle things like
3423  // int foo(int x) { return 1 << (x & 255); }
3424  // int bar() { return foo(256); }
3425#if 0
3426  case ISD::SRA_PARTS:
3427  case ISD::SRL_PARTS:
3428  case ISD::SHL_PARTS:
3429    if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
3430        cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
3431      return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3432    else if (N3.getOpcode() == ISD::AND)
3433      if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
3434        // If the and is only masking out bits that cannot effect the shift,
3435        // eliminate the and.
3436        unsigned NumBits = VT.getSizeInBits()*2;
3437        if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
3438          return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3439      }
3440    break;
3441#endif
3442  }
3443
3444  // Memoize the node unless it returns a flag.
3445  SDNode *N;
3446  if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3447    FoldingSetNodeID ID;
3448    AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3449    void *IP = 0;
3450    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3451      return SDOperand(E, 0);
3452    if (NumOps == 1) {
3453      N = getAllocator().Allocate<UnarySDNode>();
3454      new (N) UnarySDNode(Opcode, VTList, Ops[0]);
3455    } else if (NumOps == 2) {
3456      N = getAllocator().Allocate<BinarySDNode>();
3457      new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3458    } else if (NumOps == 3) {
3459      N = getAllocator().Allocate<TernarySDNode>();
3460      new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3461    } else {
3462      N = getAllocator().Allocate<SDNode>();
3463      new (N) SDNode(Opcode, VTList, Ops, NumOps);
3464    }
3465    CSEMap.InsertNode(N, IP);
3466  } else {
3467    if (NumOps == 1) {
3468      N = getAllocator().Allocate<UnarySDNode>();
3469      new (N) UnarySDNode(Opcode, VTList, Ops[0]);
3470    } else if (NumOps == 2) {
3471      N = getAllocator().Allocate<BinarySDNode>();
3472      new (N) BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3473    } else if (NumOps == 3) {
3474      N = getAllocator().Allocate<TernarySDNode>();
3475      new (N) TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3476    } else {
3477      N = getAllocator().Allocate<SDNode>();
3478      new (N) SDNode(Opcode, VTList, Ops, NumOps);
3479    }
3480  }
3481  AllNodes.push_back(N);
3482  return SDOperand(N, 0);
3483}
3484
3485SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList) {
3486  return getNode(Opcode, VTList, 0, 0);
3487}
3488
3489SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3490                                SDOperand N1) {
3491  SDOperand Ops[] = { N1 };
3492  return getNode(Opcode, VTList, Ops, 1);
3493}
3494
3495SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3496                                SDOperand N1, SDOperand N2) {
3497  SDOperand Ops[] = { N1, N2 };
3498  return getNode(Opcode, VTList, Ops, 2);
3499}
3500
3501SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3502                                SDOperand N1, SDOperand N2, SDOperand N3) {
3503  SDOperand Ops[] = { N1, N2, N3 };
3504  return getNode(Opcode, VTList, Ops, 3);
3505}
3506
3507SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3508                                SDOperand N1, SDOperand N2, SDOperand N3,
3509                                SDOperand N4) {
3510  SDOperand Ops[] = { N1, N2, N3, N4 };
3511  return getNode(Opcode, VTList, Ops, 4);
3512}
3513
3514SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3515                                SDOperand N1, SDOperand N2, SDOperand N3,
3516                                SDOperand N4, SDOperand N5) {
3517  SDOperand Ops[] = { N1, N2, N3, N4, N5 };
3518  return getNode(Opcode, VTList, Ops, 5);
3519}
3520
3521SDVTList SelectionDAG::getVTList(MVT VT) {
3522  return makeVTList(SDNode::getValueTypeList(VT), 1);
3523}
3524
3525SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2) {
3526  for (std::list<std::vector<MVT> >::iterator I = VTList.begin(),
3527       E = VTList.end(); I != E; ++I) {
3528    if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
3529      return makeVTList(&(*I)[0], 2);
3530  }
3531  std::vector<MVT> V;
3532  V.push_back(VT1);
3533  V.push_back(VT2);
3534  VTList.push_front(V);
3535  return makeVTList(&(*VTList.begin())[0], 2);
3536}
3537SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2,
3538                                 MVT VT3) {
3539  for (std::list<std::vector<MVT> >::iterator I = VTList.begin(),
3540       E = VTList.end(); I != E; ++I) {
3541    if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 &&
3542        (*I)[2] == VT3)
3543      return makeVTList(&(*I)[0], 3);
3544  }
3545  std::vector<MVT> V;
3546  V.push_back(VT1);
3547  V.push_back(VT2);
3548  V.push_back(VT3);
3549  VTList.push_front(V);
3550  return makeVTList(&(*VTList.begin())[0], 3);
3551}
3552
3553SDVTList SelectionDAG::getVTList(const MVT *VTs, unsigned NumVTs) {
3554  switch (NumVTs) {
3555    case 0: assert(0 && "Cannot have nodes without results!");
3556    case 1: return getVTList(VTs[0]);
3557    case 2: return getVTList(VTs[0], VTs[1]);
3558    case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
3559    default: break;
3560  }
3561
3562  for (std::list<std::vector<MVT> >::iterator I = VTList.begin(),
3563       E = VTList.end(); I != E; ++I) {
3564    if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue;
3565
3566    bool NoMatch = false;
3567    for (unsigned i = 2; i != NumVTs; ++i)
3568      if (VTs[i] != (*I)[i]) {
3569        NoMatch = true;
3570        break;
3571      }
3572    if (!NoMatch)
3573      return makeVTList(&*I->begin(), NumVTs);
3574  }
3575
3576  VTList.push_front(std::vector<MVT>(VTs, VTs+NumVTs));
3577  return makeVTList(&*VTList.begin()->begin(), NumVTs);
3578}
3579
3580
3581/// UpdateNodeOperands - *Mutate* the specified node in-place to have the
3582/// specified operands.  If the resultant node already exists in the DAG,
3583/// this does not modify the specified node, instead it returns the node that
3584/// already exists.  If the resultant node does not exist in the DAG, the
3585/// input node is returned.  As a degenerate case, if you specify the same
3586/// input operands as the node already has, the input node is returned.
3587SDOperand SelectionDAG::
3588UpdateNodeOperands(SDOperand InN, SDOperand Op) {
3589  SDNode *N = InN.Val;
3590  assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
3591
3592  // Check to see if there is no change.
3593  if (Op == N->getOperand(0)) return InN;
3594
3595  // See if the modified node already exists.
3596  void *InsertPos = 0;
3597  if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
3598    return SDOperand(Existing, InN.ResNo);
3599
3600  // Nope it doesn't.  Remove the node from it's current place in the maps.
3601  if (InsertPos)
3602    RemoveNodeFromCSEMaps(N);
3603
3604  // Now we update the operands.
3605  N->OperandList[0].getVal()->removeUser(0, N);
3606  N->OperandList[0] = Op;
3607  N->OperandList[0].setUser(N);
3608  Op.Val->addUser(0, N);
3609
3610  // If this gets put into a CSE map, add it.
3611  if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3612  return InN;
3613}
3614
3615SDOperand SelectionDAG::
3616UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
3617  SDNode *N = InN.Val;
3618  assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
3619
3620  // Check to see if there is no change.
3621  if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
3622    return InN;   // No operands changed, just return the input node.
3623
3624  // See if the modified node already exists.
3625  void *InsertPos = 0;
3626  if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
3627    return SDOperand(Existing, InN.ResNo);
3628
3629  // Nope it doesn't.  Remove the node from it's current place in the maps.
3630  if (InsertPos)
3631    RemoveNodeFromCSEMaps(N);
3632
3633  // Now we update the operands.
3634  if (N->OperandList[0] != Op1) {
3635    N->OperandList[0].getVal()->removeUser(0, N);
3636    N->OperandList[0] = Op1;
3637    N->OperandList[0].setUser(N);
3638    Op1.Val->addUser(0, N);
3639  }
3640  if (N->OperandList[1] != Op2) {
3641    N->OperandList[1].getVal()->removeUser(1, N);
3642    N->OperandList[1] = Op2;
3643    N->OperandList[1].setUser(N);
3644    Op2.Val->addUser(1, N);
3645  }
3646
3647  // If this gets put into a CSE map, add it.
3648  if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3649  return InN;
3650}
3651
3652SDOperand SelectionDAG::
3653UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
3654  SDOperand Ops[] = { Op1, Op2, Op3 };
3655  return UpdateNodeOperands(N, Ops, 3);
3656}
3657
3658SDOperand SelectionDAG::
3659UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3660                   SDOperand Op3, SDOperand Op4) {
3661  SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
3662  return UpdateNodeOperands(N, Ops, 4);
3663}
3664
3665SDOperand SelectionDAG::
3666UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3667                   SDOperand Op3, SDOperand Op4, SDOperand Op5) {
3668  SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
3669  return UpdateNodeOperands(N, Ops, 5);
3670}
3671
3672SDOperand SelectionDAG::
3673UpdateNodeOperands(SDOperand InN, const SDOperand *Ops, unsigned NumOps) {
3674  SDNode *N = InN.Val;
3675  assert(N->getNumOperands() == NumOps &&
3676         "Update with wrong number of operands");
3677
3678  // Check to see if there is no change.
3679  bool AnyChange = false;
3680  for (unsigned i = 0; i != NumOps; ++i) {
3681    if (Ops[i] != N->getOperand(i)) {
3682      AnyChange = true;
3683      break;
3684    }
3685  }
3686
3687  // No operands changed, just return the input node.
3688  if (!AnyChange) return InN;
3689
3690  // See if the modified node already exists.
3691  void *InsertPos = 0;
3692  if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
3693    return SDOperand(Existing, InN.ResNo);
3694
3695  // Nope it doesn't.  Remove the node from its current place in the maps.
3696  if (InsertPos)
3697    RemoveNodeFromCSEMaps(N);
3698
3699  // Now we update the operands.
3700  for (unsigned i = 0; i != NumOps; ++i) {
3701    if (N->OperandList[i] != Ops[i]) {
3702      N->OperandList[i].getVal()->removeUser(i, N);
3703      N->OperandList[i] = Ops[i];
3704      N->OperandList[i].setUser(N);
3705      Ops[i].Val->addUser(i, N);
3706    }
3707  }
3708
3709  // If this gets put into a CSE map, add it.
3710  if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3711  return InN;
3712}
3713
3714/// MorphNodeTo - This frees the operands of the current node, resets the
3715/// opcode, types, and operands to the specified value.  This should only be
3716/// used by the SelectionDAG class.
3717void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
3718                         const SDOperand *Ops, unsigned NumOps,
3719                         SmallVectorImpl<SDNode *> &DeadNodes) {
3720  NodeType = Opc;
3721  ValueList = L.VTs;
3722  NumValues = L.NumVTs;
3723
3724  // Clear the operands list, updating used nodes to remove this from their
3725  // use list.  Keep track of any operands that become dead as a result.
3726  SmallPtrSet<SDNode*, 16> DeadNodeSet;
3727  for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) {
3728    SDNode *N = I->getVal();
3729    N->removeUser(std::distance(op_begin(), I), this);
3730    if (N->use_empty())
3731      DeadNodeSet.insert(N);
3732  }
3733
3734  // If NumOps is larger than the # of operands we currently have, reallocate
3735  // the operand list.
3736  if (NumOps > NumOperands) {
3737    if (OperandsNeedDelete) {
3738      delete [] OperandList;
3739    }
3740    OperandList = new SDUse[NumOps];
3741    OperandsNeedDelete = true;
3742  }
3743
3744  // Assign the new operands.
3745  NumOperands = NumOps;
3746
3747  for (unsigned i = 0, e = NumOps; i != e; ++i) {
3748    OperandList[i] = Ops[i];
3749    OperandList[i].setUser(this);
3750    SDNode *N = OperandList[i].getVal();
3751    N->addUser(i, this);
3752    ++N->UsesSize;
3753    DeadNodeSet.erase(N);
3754  }
3755
3756  // Clean up any nodes that are still dead after adding the uses for the
3757  // new operands.
3758  for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
3759       E = DeadNodeSet.end(); I != E; ++I)
3760    DeadNodes.push_back(*I);
3761}
3762
3763/// DropOperands - Release the operands and set this node to have
3764/// zero operands.  This should only be used by HandleSDNode to clear
3765/// its operand list.
3766void SDNode::DropOperands() {
3767  assert(NodeType == ISD::HANDLENODE &&
3768         "DropOperands is for HANDLENODE only!");
3769
3770  // Unlike the code in MorphNodeTo that does this, we don't need to
3771  // watch for dead nodes here.
3772  for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
3773    I->getVal()->removeUser(std::distance(op_begin(), I), this);
3774
3775  NumOperands = 0;
3776}
3777
3778/// SelectNodeTo - These are used for target selectors to *mutate* the
3779/// specified node to have the specified return type, Target opcode, and
3780/// operands.  Note that target opcodes are stored as
3781/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
3782///
3783/// Note that SelectNodeTo returns the resultant node.  If there is already a
3784/// node of the specified opcode and operands, it returns that node instead of
3785/// the current one.
3786SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3787                                   MVT VT) {
3788  SDVTList VTs = getVTList(VT);
3789  return SelectNodeTo(N, TargetOpc, VTs, 0, 0);
3790}
3791
3792SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3793                                   MVT VT, SDOperand Op1) {
3794  SDVTList VTs = getVTList(VT);
3795  SDOperand Ops[] = { Op1 };
3796  return SelectNodeTo(N, TargetOpc, VTs, Ops, 1);
3797}
3798
3799SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3800                                   MVT VT, SDOperand Op1,
3801                                   SDOperand Op2) {
3802  SDVTList VTs = getVTList(VT);
3803  SDOperand Ops[] = { Op1, Op2 };
3804  return SelectNodeTo(N, TargetOpc, VTs, Ops, 2);
3805}
3806
3807SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3808                                   MVT VT, SDOperand Op1,
3809                                   SDOperand Op2, SDOperand Op3) {
3810  SDVTList VTs = getVTList(VT);
3811  SDOperand Ops[] = { Op1, Op2, Op3 };
3812  return SelectNodeTo(N, TargetOpc, VTs, Ops, 3);
3813}
3814
3815SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3816                                   MVT VT, const SDOperand *Ops,
3817                                   unsigned NumOps) {
3818  SDVTList VTs = getVTList(VT);
3819  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
3820}
3821
3822SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3823                                   MVT VT1, MVT VT2, const SDOperand *Ops,
3824                                   unsigned NumOps) {
3825  SDVTList VTs = getVTList(VT1, VT2);
3826  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
3827}
3828
3829SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3830                                   MVT VT1, MVT VT2) {
3831  SDVTList VTs = getVTList(VT1, VT2);
3832  return SelectNodeTo(N, TargetOpc, VTs, (SDOperand *)0, 0);
3833}
3834
3835SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3836                                   MVT VT1, MVT VT2, MVT VT3,
3837                                   const SDOperand *Ops, unsigned NumOps) {
3838  SDVTList VTs = getVTList(VT1, VT2, VT3);
3839  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
3840}
3841
3842SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3843                                   MVT VT1, MVT VT2,
3844                                   SDOperand Op1) {
3845  SDVTList VTs = getVTList(VT1, VT2);
3846  SDOperand Ops[] = { Op1 };
3847  return SelectNodeTo(N, TargetOpc, VTs, Ops, 1);
3848}
3849
3850SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3851                                   MVT VT1, MVT VT2,
3852                                   SDOperand Op1, SDOperand Op2) {
3853  SDVTList VTs = getVTList(VT1, VT2);
3854  SDOperand Ops[] = { Op1, Op2 };
3855  return SelectNodeTo(N, TargetOpc, VTs, Ops, 2);
3856}
3857
3858SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3859                                   MVT VT1, MVT VT2,
3860                                   SDOperand Op1, SDOperand Op2,
3861                                   SDOperand Op3) {
3862  SDVTList VTs = getVTList(VT1, VT2);
3863  SDOperand Ops[] = { Op1, Op2, Op3 };
3864  return SelectNodeTo(N, TargetOpc, VTs, Ops, 3);
3865}
3866
3867SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3868                                   SDVTList VTs, const SDOperand *Ops,
3869                                   unsigned NumOps) {
3870  // If an identical node already exists, use it.
3871  FoldingSetNodeID ID;
3872  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
3873  void *IP = 0;
3874  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3875    return ON;
3876
3877  RemoveNodeFromCSEMaps(N);
3878
3879  SmallVector<SDNode *, 16> DeadNodes;
3880  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps, DeadNodes);
3881  RemoveDeadNodes(DeadNodes);
3882
3883  CSEMap.InsertNode(N, IP);   // Memoize the new node.
3884  return N;
3885}
3886
3887
3888/// getTargetNode - These are used for target selectors to create a new node
3889/// with specified return type(s), target opcode, and operands.
3890///
3891/// Note that getTargetNode returns the resultant node.  If there is already a
3892/// node of the specified opcode and operands, it returns that node instead of
3893/// the current one.
3894SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT) {
3895  return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
3896}
3897SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1) {
3898  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
3899}
3900SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
3901                                    SDOperand Op1, SDOperand Op2) {
3902  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
3903}
3904SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
3905                                    SDOperand Op1, SDOperand Op2,
3906                                    SDOperand Op3) {
3907  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
3908}
3909SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
3910                                    const SDOperand *Ops, unsigned NumOps) {
3911  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
3912}
3913SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2) {
3914  const MVT *VTs = getNodeValueTypes(VT1, VT2);
3915  SDOperand Op;
3916  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op, 0).Val;
3917}
3918SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
3919                                    MVT VT2, SDOperand Op1) {
3920  const MVT *VTs = getNodeValueTypes(VT1, VT2);
3921  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val;
3922}
3923SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
3924                                    MVT VT2, SDOperand Op1,
3925                                    SDOperand Op2) {
3926  const MVT *VTs = getNodeValueTypes(VT1, VT2);
3927  SDOperand Ops[] = { Op1, Op2 };
3928  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val;
3929}
3930SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
3931                                    MVT VT2, SDOperand Op1,
3932                                    SDOperand Op2, SDOperand Op3) {
3933  const MVT *VTs = getNodeValueTypes(VT1, VT2);
3934  SDOperand Ops[] = { Op1, Op2, Op3 };
3935  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
3936}
3937SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2,
3938                                    const SDOperand *Ops, unsigned NumOps) {
3939  const MVT *VTs = getNodeValueTypes(VT1, VT2);
3940  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
3941}
3942SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
3943                                    SDOperand Op1, SDOperand Op2) {
3944  const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3);
3945  SDOperand Ops[] = { Op1, Op2 };
3946  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val;
3947}
3948SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
3949                                    SDOperand Op1, SDOperand Op2,
3950                                    SDOperand Op3) {
3951  const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3);
3952  SDOperand Ops[] = { Op1, Op2, Op3 };
3953  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val;
3954}
3955SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
3956                                    const SDOperand *Ops, unsigned NumOps) {
3957  const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3);
3958  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val;
3959}
3960SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
3961                                    MVT VT2, MVT VT3, MVT VT4,
3962                                    const SDOperand *Ops, unsigned NumOps) {
3963  std::vector<MVT> VTList;
3964  VTList.push_back(VT1);
3965  VTList.push_back(VT2);
3966  VTList.push_back(VT3);
3967  VTList.push_back(VT4);
3968  const MVT *VTs = getNodeValueTypes(VTList);
3969  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 4, Ops, NumOps).Val;
3970}
3971SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
3972                                    const std::vector<MVT> &ResultTys,
3973                                    const SDOperand *Ops, unsigned NumOps) {
3974  const MVT *VTs = getNodeValueTypes(ResultTys);
3975  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, ResultTys.size(),
3976                 Ops, NumOps).Val;
3977}
3978
3979/// getNodeIfExists - Get the specified node if it's already available, or
3980/// else return NULL.
3981SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
3982                                      const SDOperand *Ops, unsigned NumOps) {
3983  if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3984    FoldingSetNodeID ID;
3985    AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3986    void *IP = 0;
3987    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3988      return E;
3989  }
3990  return NULL;
3991}
3992
3993
3994/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3995/// This can cause recursive merging of nodes in the DAG.
3996///
3997/// This version assumes From has a single result value.
3998///
3999void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
4000                                      DAGUpdateListener *UpdateListener) {
4001  SDNode *From = FromN.Val;
4002  assert(From->getNumValues() == 1 && FromN.ResNo == 0 &&
4003         "Cannot replace with this method!");
4004  assert(From != To.Val && "Cannot replace uses of with self");
4005
4006  while (!From->use_empty()) {
4007    SDNode::use_iterator UI = From->use_begin();
4008    SDNode *U = UI->getUser();
4009
4010    // This node is about to morph, remove its old self from the CSE maps.
4011    RemoveNodeFromCSEMaps(U);
4012    int operandNum = 0;
4013    for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
4014         I != E; ++I, ++operandNum)
4015      if (I->getVal() == From) {
4016        From->removeUser(operandNum, U);
4017        *I = To;
4018        I->setUser(U);
4019        To.Val->addUser(operandNum, U);
4020      }
4021
4022    // Now that we have modified U, add it back to the CSE maps.  If it already
4023    // exists there, recursively merge the results together.
4024    if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
4025      ReplaceAllUsesWith(U, Existing, UpdateListener);
4026      // U is now dead.  Inform the listener if it exists and delete it.
4027      if (UpdateListener)
4028        UpdateListener->NodeDeleted(U, Existing);
4029      DeleteNodeNotInCSEMaps(U);
4030    } else {
4031      // If the node doesn't already exist, we updated it.  Inform a listener if
4032      // it exists.
4033      if (UpdateListener)
4034        UpdateListener->NodeUpdated(U);
4035    }
4036  }
4037}
4038
4039/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
4040/// This can cause recursive merging of nodes in the DAG.
4041///
4042/// This version assumes From/To have matching types and numbers of result
4043/// values.
4044///
4045void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
4046                                      DAGUpdateListener *UpdateListener) {
4047  assert(From != To && "Cannot replace uses of with self");
4048  assert(From->getNumValues() == To->getNumValues() &&
4049         "Cannot use this version of ReplaceAllUsesWith!");
4050  if (From->getNumValues() == 1)   // If possible, use the faster version.
4051    return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
4052                              UpdateListener);
4053
4054  while (!From->use_empty()) {
4055    SDNode::use_iterator UI = From->use_begin();
4056    SDNode *U = UI->getUser();
4057
4058    // This node is about to morph, remove its old self from the CSE maps.
4059    RemoveNodeFromCSEMaps(U);
4060    int operandNum = 0;
4061    for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
4062         I != E; ++I, ++operandNum)
4063      if (I->getVal() == From) {
4064        From->removeUser(operandNum, U);
4065        I->getVal() = To;
4066        To->addUser(operandNum, U);
4067      }
4068
4069    // Now that we have modified U, add it back to the CSE maps.  If it already
4070    // exists there, recursively merge the results together.
4071    if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
4072      ReplaceAllUsesWith(U, Existing, UpdateListener);
4073      // U is now dead.  Inform the listener if it exists and delete it.
4074      if (UpdateListener)
4075        UpdateListener->NodeDeleted(U, Existing);
4076      DeleteNodeNotInCSEMaps(U);
4077    } else {
4078      // If the node doesn't already exist, we updated it.  Inform a listener if
4079      // it exists.
4080      if (UpdateListener)
4081        UpdateListener->NodeUpdated(U);
4082    }
4083  }
4084}
4085
4086/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
4087/// This can cause recursive merging of nodes in the DAG.
4088///
4089/// This version can replace From with any result values.  To must match the
4090/// number and types of values returned by From.
4091void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
4092                                      const SDOperand *To,
4093                                      DAGUpdateListener *UpdateListener) {
4094  if (From->getNumValues() == 1)  // Handle the simple case efficiently.
4095    return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
4096
4097  while (!From->use_empty()) {
4098    SDNode::use_iterator UI = From->use_begin();
4099    SDNode *U = UI->getUser();
4100
4101    // This node is about to morph, remove its old self from the CSE maps.
4102    RemoveNodeFromCSEMaps(U);
4103    int operandNum = 0;
4104    for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
4105         I != E; ++I, ++operandNum)
4106      if (I->getVal() == From) {
4107        const SDOperand &ToOp = To[I->getSDOperand().ResNo];
4108        From->removeUser(operandNum, U);
4109        *I = ToOp;
4110        I->setUser(U);
4111        ToOp.Val->addUser(operandNum, U);
4112      }
4113
4114    // Now that we have modified U, add it back to the CSE maps.  If it already
4115    // exists there, recursively merge the results together.
4116    if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
4117      ReplaceAllUsesWith(U, Existing, UpdateListener);
4118      // U is now dead.  Inform the listener if it exists and delete it.
4119      if (UpdateListener)
4120        UpdateListener->NodeDeleted(U, Existing);
4121      DeleteNodeNotInCSEMaps(U);
4122    } else {
4123      // If the node doesn't already exist, we updated it.  Inform a listener if
4124      // it exists.
4125      if (UpdateListener)
4126        UpdateListener->NodeUpdated(U);
4127    }
4128  }
4129}
4130
4131namespace {
4132  /// ChainedSetUpdaterListener - This class is a DAGUpdateListener that removes
4133  /// any deleted nodes from the set passed into its constructor and recursively
4134  /// notifies another update listener if specified.
4135  class ChainedSetUpdaterListener :
4136  public SelectionDAG::DAGUpdateListener {
4137    SmallSetVector<SDNode*, 16> &Set;
4138    SelectionDAG::DAGUpdateListener *Chain;
4139  public:
4140    ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
4141                              SelectionDAG::DAGUpdateListener *chain)
4142      : Set(set), Chain(chain) {}
4143
4144    virtual void NodeDeleted(SDNode *N, SDNode *E) {
4145      Set.remove(N);
4146      if (Chain) Chain->NodeDeleted(N, E);
4147    }
4148    virtual void NodeUpdated(SDNode *N) {
4149      if (Chain) Chain->NodeUpdated(N);
4150    }
4151  };
4152}
4153
4154/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
4155/// uses of other values produced by From.Val alone.  The Deleted vector is
4156/// handled the same way as for ReplaceAllUsesWith.
4157void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
4158                                             DAGUpdateListener *UpdateListener){
4159  assert(From != To && "Cannot replace a value with itself");
4160
4161  // Handle the simple, trivial, case efficiently.
4162  if (From.Val->getNumValues() == 1) {
4163    ReplaceAllUsesWith(From, To, UpdateListener);
4164    return;
4165  }
4166
4167  if (From.use_empty()) return;
4168
4169  // Get all of the users of From.Val.  We want these in a nice,
4170  // deterministically ordered and uniqued set, so we use a SmallSetVector.
4171  SmallSetVector<SDNode*, 16> Users;
4172  for (SDNode::use_iterator UI = From.Val->use_begin(),
4173      E = From.Val->use_end(); UI != E; ++UI) {
4174    SDNode *User = UI->getUser();
4175    Users.insert(User);
4176  }
4177
4178  // When one of the recursive merges deletes nodes from the graph, we need to
4179  // make sure that UpdateListener is notified *and* that the node is removed
4180  // from Users if present.  CSUL does this.
4181  ChainedSetUpdaterListener CSUL(Users, UpdateListener);
4182
4183  while (!Users.empty()) {
4184    // We know that this user uses some value of From.  If it is the right
4185    // value, update it.
4186    SDNode *User = Users.back();
4187    Users.pop_back();
4188
4189    // Scan for an operand that matches From.
4190    SDNode::op_iterator Op = User->op_begin(), E = User->op_end();
4191    for (; Op != E; ++Op)
4192      if (*Op == From) break;
4193
4194    // If there are no matches, the user must use some other result of From.
4195    if (Op == E) continue;
4196
4197    // Okay, we know this user needs to be updated.  Remove its old self
4198    // from the CSE maps.
4199    RemoveNodeFromCSEMaps(User);
4200
4201    // Update all operands that match "From" in case there are multiple uses.
4202    for (; Op != E; ++Op) {
4203      if (*Op == From) {
4204        From.Val->removeUser(Op-User->op_begin(), User);
4205        *Op = To;
4206        Op->setUser(User);
4207        To.Val->addUser(Op-User->op_begin(), User);
4208      }
4209    }
4210
4211    // Now that we have modified User, add it back to the CSE maps.  If it
4212    // already exists there, recursively merge the results together.
4213    SDNode *Existing = AddNonLeafNodeToCSEMaps(User);
4214    if (!Existing) {
4215      if (UpdateListener) UpdateListener->NodeUpdated(User);
4216      continue;  // Continue on to next user.
4217    }
4218
4219    // If there was already an existing matching node, use ReplaceAllUsesWith
4220    // to replace the dead one with the existing one.  This can cause
4221    // recursive merging of other unrelated nodes down the line.  The merging
4222    // can cause deletion of nodes that used the old value.  To handle this, we
4223    // use CSUL to remove them from the Users set.
4224    ReplaceAllUsesWith(User, Existing, &CSUL);
4225
4226    // User is now dead.  Notify a listener if present.
4227    if (UpdateListener) UpdateListener->NodeDeleted(User, Existing);
4228    DeleteNodeNotInCSEMaps(User);
4229  }
4230}
4231
4232/// AssignNodeIds - Assign a unique node id for each node in the DAG based on
4233/// their allnodes order. It returns the maximum id.
4234unsigned SelectionDAG::AssignNodeIds() {
4235  unsigned Id = 0;
4236  for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
4237    SDNode *N = I;
4238    N->setNodeId(Id++);
4239  }
4240  return Id;
4241}
4242
4243/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
4244/// based on their topological order. It returns the maximum id and a vector
4245/// of the SDNodes* in assigned order by reference.
4246unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
4247  unsigned DAGSize = AllNodes.size();
4248  std::vector<unsigned> InDegree(DAGSize);
4249  std::vector<SDNode*> Sources;
4250
4251  // Use a two pass approach to avoid using a std::map which is slow.
4252  unsigned Id = 0;
4253  for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
4254    SDNode *N = I;
4255    N->setNodeId(Id++);
4256    unsigned Degree = N->use_size();
4257    InDegree[N->getNodeId()] = Degree;
4258    if (Degree == 0)
4259      Sources.push_back(N);
4260  }
4261
4262  TopOrder.clear();
4263  TopOrder.reserve(DAGSize);
4264  while (!Sources.empty()) {
4265    SDNode *N = Sources.back();
4266    Sources.pop_back();
4267    TopOrder.push_back(N);
4268    for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
4269      SDNode *P = I->getVal();
4270      unsigned Degree = --InDegree[P->getNodeId()];
4271      if (Degree == 0)
4272        Sources.push_back(P);
4273    }
4274  }
4275
4276  // Second pass, assign the actual topological order as node ids.
4277  Id = 0;
4278  for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
4279       TI != TE; ++TI)
4280    (*TI)->setNodeId(Id++);
4281
4282  return Id;
4283}
4284
4285
4286
4287//===----------------------------------------------------------------------===//
4288//                              SDNode Class
4289//===----------------------------------------------------------------------===//
4290
4291// Out-of-line virtual method to give class a home.
4292void SDNode::ANCHOR() {}
4293void UnarySDNode::ANCHOR() {}
4294void BinarySDNode::ANCHOR() {}
4295void TernarySDNode::ANCHOR() {}
4296void HandleSDNode::ANCHOR() {}
4297void ConstantSDNode::ANCHOR() {}
4298void ConstantFPSDNode::ANCHOR() {}
4299void GlobalAddressSDNode::ANCHOR() {}
4300void FrameIndexSDNode::ANCHOR() {}
4301void JumpTableSDNode::ANCHOR() {}
4302void ConstantPoolSDNode::ANCHOR() {}
4303void BasicBlockSDNode::ANCHOR() {}
4304void SrcValueSDNode::ANCHOR() {}
4305void MemOperandSDNode::ANCHOR() {}
4306void RegisterSDNode::ANCHOR() {}
4307void DbgStopPointSDNode::ANCHOR() {}
4308void LabelSDNode::ANCHOR() {}
4309void ExternalSymbolSDNode::ANCHOR() {}
4310void CondCodeSDNode::ANCHOR() {}
4311void ARG_FLAGSSDNode::ANCHOR() {}
4312void VTSDNode::ANCHOR() {}
4313void MemSDNode::ANCHOR() {}
4314void LoadSDNode::ANCHOR() {}
4315void StoreSDNode::ANCHOR() {}
4316void AtomicSDNode::ANCHOR() {}
4317
4318HandleSDNode::~HandleSDNode() {
4319  DropOperands();
4320}
4321
4322GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA,
4323                                         MVT VT, int o)
4324  : SDNode(isa<GlobalVariable>(GA) &&
4325           cast<GlobalVariable>(GA)->isThreadLocal() ?
4326           // Thread Local
4327           (isTarget ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress) :
4328           // Non Thread Local
4329           (isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress),
4330           getSDVTList(VT)), Offset(o) {
4331  TheGlobal = const_cast<GlobalValue*>(GA);
4332}
4333
4334MemSDNode::MemSDNode(unsigned Opc, SDVTList VTs,
4335                     const Value *srcValue, int SVO,
4336                     unsigned alignment, bool vol)
4337 : SDNode(Opc, VTs), SrcValue(srcValue), SVOffset(SVO),
4338   Flags(vol | ((Log2_32(alignment) + 1) << 1)) {
4339
4340  assert(isPowerOf2_32(alignment) && "Alignment is not a power of 2!");
4341  assert(getAlignment() == alignment && "Alignment representation error!");
4342  assert(isVolatile() == vol && "Volatile representation error!");
4343}
4344
4345/// getMemOperand - Return a MachineMemOperand object describing the memory
4346/// reference performed by this atomic.
4347MachineMemOperand AtomicSDNode::getMemOperand() const {
4348  int Size = (getValueType(0).getSizeInBits() + 7) >> 3;
4349  int Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore;
4350  if (isVolatile()) Flags |= MachineMemOperand::MOVolatile;
4351
4352  // Check if the atomic references a frame index
4353  const FrameIndexSDNode *FI =
4354  dyn_cast<const FrameIndexSDNode>(getBasePtr().Val);
4355  if (!getSrcValue() && FI)
4356    return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags,
4357                             FI->getIndex(), Size, getAlignment());
4358  else
4359    return MachineMemOperand(getSrcValue(), Flags, getSrcValueOffset(),
4360                             Size, getAlignment());
4361}
4362
4363/// getMemOperand - Return a MachineMemOperand object describing the memory
4364/// reference performed by this load or store.
4365MachineMemOperand LSBaseSDNode::getMemOperand() const {
4366  int Size = (getMemoryVT().getSizeInBits() + 7) >> 3;
4367  int Flags =
4368    getOpcode() == ISD::LOAD ? MachineMemOperand::MOLoad :
4369                               MachineMemOperand::MOStore;
4370  if (isVolatile()) Flags |= MachineMemOperand::MOVolatile;
4371
4372  // Check if the load references a frame index, and does not have
4373  // an SV attached.
4374  const FrameIndexSDNode *FI =
4375    dyn_cast<const FrameIndexSDNode>(getBasePtr().Val);
4376  if (!getSrcValue() && FI)
4377    return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags,
4378                             FI->getIndex(), Size, getAlignment());
4379  else
4380    return MachineMemOperand(getSrcValue(), Flags,
4381                             getSrcValueOffset(), Size, getAlignment());
4382}
4383
4384/// Profile - Gather unique data for the node.
4385///
4386void SDNode::Profile(FoldingSetNodeID &ID) {
4387  AddNodeIDNode(ID, this);
4388}
4389
4390/// getValueTypeList - Return a pointer to the specified value type.
4391///
4392const MVT *SDNode::getValueTypeList(MVT VT) {
4393  if (VT.isExtended()) {
4394    static std::set<MVT, MVT::compareRawBits> EVTs;
4395    return &(*EVTs.insert(VT).first);
4396  } else {
4397    static MVT VTs[MVT::LAST_VALUETYPE];
4398    VTs[VT.getSimpleVT()] = VT;
4399    return &VTs[VT.getSimpleVT()];
4400  }
4401}
4402
4403/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
4404/// indicated value.  This method ignores uses of other values defined by this
4405/// operation.
4406bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
4407  assert(Value < getNumValues() && "Bad value!");
4408
4409  // If there is only one value, this is easy.
4410  if (getNumValues() == 1)
4411    return use_size() == NUses;
4412  if (use_size() < NUses) return false;
4413
4414  SDOperand TheValue(const_cast<SDNode *>(this), Value);
4415
4416  SmallPtrSet<SDNode*, 32> UsersHandled;
4417
4418  // TODO: Only iterate over uses of a given value of the node
4419  for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4420    if (*UI == TheValue) {
4421      if (NUses == 0)
4422        return false;
4423      --NUses;
4424    }
4425  }
4426
4427  // Found exactly the right number of uses?
4428  return NUses == 0;
4429}
4430
4431
4432/// hasAnyUseOfValue - Return true if there are any use of the indicated
4433/// value. This method ignores uses of other values defined by this operation.
4434bool SDNode::hasAnyUseOfValue(unsigned Value) const {
4435  assert(Value < getNumValues() && "Bad value!");
4436
4437  if (use_empty()) return false;
4438
4439  SDOperand TheValue(const_cast<SDNode *>(this), Value);
4440
4441  SmallPtrSet<SDNode*, 32> UsersHandled;
4442
4443  for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4444    SDNode *User = UI->getUser();
4445    if (User->getNumOperands() == 1 ||
4446        UsersHandled.insert(User))     // First time we've seen this?
4447      for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
4448        if (User->getOperand(i) == TheValue) {
4449          return true;
4450        }
4451  }
4452
4453  return false;
4454}
4455
4456
4457/// isOnlyUseOf - Return true if this node is the only use of N.
4458///
4459bool SDNode::isOnlyUseOf(SDNode *N) const {
4460  bool Seen = false;
4461  for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
4462    SDNode *User = I->getUser();
4463    if (User == this)
4464      Seen = true;
4465    else
4466      return false;
4467  }
4468
4469  return Seen;
4470}
4471
4472/// isOperand - Return true if this node is an operand of N.
4473///
4474bool SDOperand::isOperandOf(SDNode *N) const {
4475  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4476    if (*this == N->getOperand(i))
4477      return true;
4478  return false;
4479}
4480
4481bool SDNode::isOperandOf(SDNode *N) const {
4482  for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
4483    if (this == N->OperandList[i].getVal())
4484      return true;
4485  return false;
4486}
4487
4488/// reachesChainWithoutSideEffects - Return true if this operand (which must
4489/// be a chain) reaches the specified operand without crossing any
4490/// side-effecting instructions.  In practice, this looks through token
4491/// factors and non-volatile loads.  In order to remain efficient, this only
4492/// looks a couple of nodes in, it does not do an exhaustive search.
4493bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest,
4494                                               unsigned Depth) const {
4495  if (*this == Dest) return true;
4496
4497  // Don't search too deeply, we just want to be able to see through
4498  // TokenFactor's etc.
4499  if (Depth == 0) return false;
4500
4501  // If this is a token factor, all inputs to the TF happen in parallel.  If any
4502  // of the operands of the TF reach dest, then we can do the xform.
4503  if (getOpcode() == ISD::TokenFactor) {
4504    for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
4505      if (getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
4506        return true;
4507    return false;
4508  }
4509
4510  // Loads don't have side effects, look through them.
4511  if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
4512    if (!Ld->isVolatile())
4513      return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
4514  }
4515  return false;
4516}
4517
4518
4519static void findPredecessor(SDNode *N, const SDNode *P, bool &found,
4520                            SmallPtrSet<SDNode *, 32> &Visited) {
4521  if (found || !Visited.insert(N))
4522    return;
4523
4524  for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) {
4525    SDNode *Op = N->getOperand(i).Val;
4526    if (Op == P) {
4527      found = true;
4528      return;
4529    }
4530    findPredecessor(Op, P, found, Visited);
4531  }
4532}
4533
4534/// isPredecessorOf - Return true if this node is a predecessor of N. This node
4535/// is either an operand of N or it can be reached by recursively traversing
4536/// up the operands.
4537/// NOTE: this is an expensive method. Use it carefully.
4538bool SDNode::isPredecessorOf(SDNode *N) const {
4539  SmallPtrSet<SDNode *, 32> Visited;
4540  bool found = false;
4541  findPredecessor(N, this, found, Visited);
4542  return found;
4543}
4544
4545uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
4546  assert(Num < NumOperands && "Invalid child # of SDNode!");
4547  return cast<ConstantSDNode>(OperandList[Num])->getValue();
4548}
4549
4550std::string SDNode::getOperationName(const SelectionDAG *G) const {
4551  switch (getOpcode()) {
4552  default:
4553    if (getOpcode() < ISD::BUILTIN_OP_END)
4554      return "<<Unknown DAG Node>>";
4555    else {
4556      if (G) {
4557        if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
4558          if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
4559            return TII->get(getOpcode()-ISD::BUILTIN_OP_END).getName();
4560
4561        TargetLowering &TLI = G->getTargetLoweringInfo();
4562        const char *Name =
4563          TLI.getTargetNodeName(getOpcode());
4564        if (Name) return Name;
4565      }
4566
4567      return "<<Unknown Target Node>>";
4568    }
4569
4570  case ISD::PREFETCH:      return "Prefetch";
4571  case ISD::MEMBARRIER:    return "MemBarrier";
4572  case ISD::ATOMIC_CMP_SWAP:  return "AtomicCmpSwap";
4573  case ISD::ATOMIC_LOAD_ADD:  return "AtomicLoadAdd";
4574  case ISD::ATOMIC_LOAD_SUB:  return "AtomicLoadSub";
4575  case ISD::ATOMIC_LOAD_AND:  return "AtomicLoadAnd";
4576  case ISD::ATOMIC_LOAD_OR:   return "AtomicLoadOr";
4577  case ISD::ATOMIC_LOAD_XOR:  return "AtomicLoadXor";
4578  case ISD::ATOMIC_LOAD_NAND: return "AtomicLoadNand";
4579  case ISD::ATOMIC_LOAD_MIN:  return "AtomicLoadMin";
4580  case ISD::ATOMIC_LOAD_MAX:  return "AtomicLoadMax";
4581  case ISD::ATOMIC_LOAD_UMIN: return "AtomicLoadUMin";
4582  case ISD::ATOMIC_LOAD_UMAX: return "AtomicLoadUMax";
4583  case ISD::ATOMIC_SWAP:   return "AtomicSWAP";
4584  case ISD::PCMARKER:      return "PCMarker";
4585  case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
4586  case ISD::SRCVALUE:      return "SrcValue";
4587  case ISD::MEMOPERAND:    return "MemOperand";
4588  case ISD::EntryToken:    return "EntryToken";
4589  case ISD::TokenFactor:   return "TokenFactor";
4590  case ISD::AssertSext:    return "AssertSext";
4591  case ISD::AssertZext:    return "AssertZext";
4592
4593  case ISD::BasicBlock:    return "BasicBlock";
4594  case ISD::ARG_FLAGS:     return "ArgFlags";
4595  case ISD::VALUETYPE:     return "ValueType";
4596  case ISD::Register:      return "Register";
4597
4598  case ISD::Constant:      return "Constant";
4599  case ISD::ConstantFP:    return "ConstantFP";
4600  case ISD::GlobalAddress: return "GlobalAddress";
4601  case ISD::GlobalTLSAddress: return "GlobalTLSAddress";
4602  case ISD::FrameIndex:    return "FrameIndex";
4603  case ISD::JumpTable:     return "JumpTable";
4604  case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE";
4605  case ISD::RETURNADDR: return "RETURNADDR";
4606  case ISD::FRAMEADDR: return "FRAMEADDR";
4607  case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET";
4608  case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR";
4609  case ISD::EHSELECTION: return "EHSELECTION";
4610  case ISD::EH_RETURN: return "EH_RETURN";
4611  case ISD::ConstantPool:  return "ConstantPool";
4612  case ISD::ExternalSymbol: return "ExternalSymbol";
4613  case ISD::INTRINSIC_WO_CHAIN: {
4614    unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
4615    return Intrinsic::getName((Intrinsic::ID)IID);
4616  }
4617  case ISD::INTRINSIC_VOID:
4618  case ISD::INTRINSIC_W_CHAIN: {
4619    unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
4620    return Intrinsic::getName((Intrinsic::ID)IID);
4621  }
4622
4623  case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
4624  case ISD::TargetConstant: return "TargetConstant";
4625  case ISD::TargetConstantFP:return "TargetConstantFP";
4626  case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
4627  case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress";
4628  case ISD::TargetFrameIndex: return "TargetFrameIndex";
4629  case ISD::TargetJumpTable:  return "TargetJumpTable";
4630  case ISD::TargetConstantPool:  return "TargetConstantPool";
4631  case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
4632
4633  case ISD::CopyToReg:     return "CopyToReg";
4634  case ISD::CopyFromReg:   return "CopyFromReg";
4635  case ISD::UNDEF:         return "undef";
4636  case ISD::MERGE_VALUES:  return "merge_values";
4637  case ISD::INLINEASM:     return "inlineasm";
4638  case ISD::DBG_LABEL:     return "dbg_label";
4639  case ISD::EH_LABEL:      return "eh_label";
4640  case ISD::DECLARE:       return "declare";
4641  case ISD::HANDLENODE:    return "handlenode";
4642  case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
4643  case ISD::CALL:          return "call";
4644
4645  // Unary operators
4646  case ISD::FABS:   return "fabs";
4647  case ISD::FNEG:   return "fneg";
4648  case ISD::FSQRT:  return "fsqrt";
4649  case ISD::FSIN:   return "fsin";
4650  case ISD::FCOS:   return "fcos";
4651  case ISD::FPOWI:  return "fpowi";
4652  case ISD::FPOW:   return "fpow";
4653
4654  // Binary operators
4655  case ISD::ADD:    return "add";
4656  case ISD::SUB:    return "sub";
4657  case ISD::MUL:    return "mul";
4658  case ISD::MULHU:  return "mulhu";
4659  case ISD::MULHS:  return "mulhs";
4660  case ISD::SDIV:   return "sdiv";
4661  case ISD::UDIV:   return "udiv";
4662  case ISD::SREM:   return "srem";
4663  case ISD::UREM:   return "urem";
4664  case ISD::SMUL_LOHI:  return "smul_lohi";
4665  case ISD::UMUL_LOHI:  return "umul_lohi";
4666  case ISD::SDIVREM:    return "sdivrem";
4667  case ISD::UDIVREM:    return "divrem";
4668  case ISD::AND:    return "and";
4669  case ISD::OR:     return "or";
4670  case ISD::XOR:    return "xor";
4671  case ISD::SHL:    return "shl";
4672  case ISD::SRA:    return "sra";
4673  case ISD::SRL:    return "srl";
4674  case ISD::ROTL:   return "rotl";
4675  case ISD::ROTR:   return "rotr";
4676  case ISD::FADD:   return "fadd";
4677  case ISD::FSUB:   return "fsub";
4678  case ISD::FMUL:   return "fmul";
4679  case ISD::FDIV:   return "fdiv";
4680  case ISD::FREM:   return "frem";
4681  case ISD::FCOPYSIGN: return "fcopysign";
4682  case ISD::FGETSIGN:  return "fgetsign";
4683
4684  case ISD::SETCC:       return "setcc";
4685  case ISD::VSETCC:      return "vsetcc";
4686  case ISD::SELECT:      return "select";
4687  case ISD::SELECT_CC:   return "select_cc";
4688  case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
4689  case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
4690  case ISD::CONCAT_VECTORS:      return "concat_vectors";
4691  case ISD::EXTRACT_SUBVECTOR:   return "extract_subvector";
4692  case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
4693  case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
4694  case ISD::CARRY_FALSE:         return "carry_false";
4695  case ISD::ADDC:        return "addc";
4696  case ISD::ADDE:        return "adde";
4697  case ISD::SUBC:        return "subc";
4698  case ISD::SUBE:        return "sube";
4699  case ISD::SHL_PARTS:   return "shl_parts";
4700  case ISD::SRA_PARTS:   return "sra_parts";
4701  case ISD::SRL_PARTS:   return "srl_parts";
4702
4703  case ISD::EXTRACT_SUBREG:     return "extract_subreg";
4704  case ISD::INSERT_SUBREG:      return "insert_subreg";
4705
4706  // Conversion operators.
4707  case ISD::SIGN_EXTEND: return "sign_extend";
4708  case ISD::ZERO_EXTEND: return "zero_extend";
4709  case ISD::ANY_EXTEND:  return "any_extend";
4710  case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
4711  case ISD::TRUNCATE:    return "truncate";
4712  case ISD::FP_ROUND:    return "fp_round";
4713  case ISD::FLT_ROUNDS_: return "flt_rounds";
4714  case ISD::FP_ROUND_INREG: return "fp_round_inreg";
4715  case ISD::FP_EXTEND:   return "fp_extend";
4716
4717  case ISD::SINT_TO_FP:  return "sint_to_fp";
4718  case ISD::UINT_TO_FP:  return "uint_to_fp";
4719  case ISD::FP_TO_SINT:  return "fp_to_sint";
4720  case ISD::FP_TO_UINT:  return "fp_to_uint";
4721  case ISD::BIT_CONVERT: return "bit_convert";
4722
4723    // Control flow instructions
4724  case ISD::BR:      return "br";
4725  case ISD::BRIND:   return "brind";
4726  case ISD::BR_JT:   return "br_jt";
4727  case ISD::BRCOND:  return "brcond";
4728  case ISD::BR_CC:   return "br_cc";
4729  case ISD::RET:     return "ret";
4730  case ISD::CALLSEQ_START:  return "callseq_start";
4731  case ISD::CALLSEQ_END:    return "callseq_end";
4732
4733    // Other operators
4734  case ISD::LOAD:               return "load";
4735  case ISD::STORE:              return "store";
4736  case ISD::VAARG:              return "vaarg";
4737  case ISD::VACOPY:             return "vacopy";
4738  case ISD::VAEND:              return "vaend";
4739  case ISD::VASTART:            return "vastart";
4740  case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
4741  case ISD::EXTRACT_ELEMENT:    return "extract_element";
4742  case ISD::BUILD_PAIR:         return "build_pair";
4743  case ISD::STACKSAVE:          return "stacksave";
4744  case ISD::STACKRESTORE:       return "stackrestore";
4745  case ISD::TRAP:               return "trap";
4746
4747  // Bit manipulation
4748  case ISD::BSWAP:   return "bswap";
4749  case ISD::CTPOP:   return "ctpop";
4750  case ISD::CTTZ:    return "cttz";
4751  case ISD::CTLZ:    return "ctlz";
4752
4753  // Debug info
4754  case ISD::DBG_STOPPOINT: return "dbg_stoppoint";
4755  case ISD::DEBUG_LOC: return "debug_loc";
4756
4757  // Trampolines
4758  case ISD::TRAMPOLINE: return "trampoline";
4759
4760  case ISD::CONDCODE:
4761    switch (cast<CondCodeSDNode>(this)->get()) {
4762    default: assert(0 && "Unknown setcc condition!");
4763    case ISD::SETOEQ:  return "setoeq";
4764    case ISD::SETOGT:  return "setogt";
4765    case ISD::SETOGE:  return "setoge";
4766    case ISD::SETOLT:  return "setolt";
4767    case ISD::SETOLE:  return "setole";
4768    case ISD::SETONE:  return "setone";
4769
4770    case ISD::SETO:    return "seto";
4771    case ISD::SETUO:   return "setuo";
4772    case ISD::SETUEQ:  return "setue";
4773    case ISD::SETUGT:  return "setugt";
4774    case ISD::SETUGE:  return "setuge";
4775    case ISD::SETULT:  return "setult";
4776    case ISD::SETULE:  return "setule";
4777    case ISD::SETUNE:  return "setune";
4778
4779    case ISD::SETEQ:   return "seteq";
4780    case ISD::SETGT:   return "setgt";
4781    case ISD::SETGE:   return "setge";
4782    case ISD::SETLT:   return "setlt";
4783    case ISD::SETLE:   return "setle";
4784    case ISD::SETNE:   return "setne";
4785    }
4786  }
4787}
4788
4789const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) {
4790  switch (AM) {
4791  default:
4792    return "";
4793  case ISD::PRE_INC:
4794    return "<pre-inc>";
4795  case ISD::PRE_DEC:
4796    return "<pre-dec>";
4797  case ISD::POST_INC:
4798    return "<post-inc>";
4799  case ISD::POST_DEC:
4800    return "<post-dec>";
4801  }
4802}
4803
4804std::string ISD::ArgFlagsTy::getArgFlagsString() {
4805  std::string S = "< ";
4806
4807  if (isZExt())
4808    S += "zext ";
4809  if (isSExt())
4810    S += "sext ";
4811  if (isInReg())
4812    S += "inreg ";
4813  if (isSRet())
4814    S += "sret ";
4815  if (isByVal())
4816    S += "byval ";
4817  if (isNest())
4818    S += "nest ";
4819  if (getByValAlign())
4820    S += "byval-align:" + utostr(getByValAlign()) + " ";
4821  if (getOrigAlign())
4822    S += "orig-align:" + utostr(getOrigAlign()) + " ";
4823  if (getByValSize())
4824    S += "byval-size:" + utostr(getByValSize()) + " ";
4825  return S + ">";
4826}
4827
4828void SDNode::dump() const { dump(0); }
4829void SDNode::dump(const SelectionDAG *G) const {
4830  cerr << (void*)this << ": ";
4831
4832  for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
4833    if (i) cerr << ",";
4834    if (getValueType(i) == MVT::Other)
4835      cerr << "ch";
4836    else
4837      cerr << getValueType(i).getMVTString();
4838  }
4839  cerr << " = " << getOperationName(G);
4840
4841  cerr << " ";
4842  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
4843    if (i) cerr << ", ";
4844    cerr << (void*)getOperand(i).Val;
4845    if (unsigned RN = getOperand(i).ResNo)
4846      cerr << ":" << RN;
4847  }
4848
4849  if (!isTargetOpcode() && getOpcode() == ISD::VECTOR_SHUFFLE) {
4850    SDNode *Mask = getOperand(2).Val;
4851    cerr << "<";
4852    for (unsigned i = 0, e = Mask->getNumOperands(); i != e; ++i) {
4853      if (i) cerr << ",";
4854      if (Mask->getOperand(i).getOpcode() == ISD::UNDEF)
4855        cerr << "u";
4856      else
4857        cerr << cast<ConstantSDNode>(Mask->getOperand(i))->getValue();
4858    }
4859    cerr << ">";
4860  }
4861
4862  if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
4863    cerr << "<" << CSDN->getValue() << ">";
4864  } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
4865    if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle)
4866      cerr << "<" << CSDN->getValueAPF().convertToFloat() << ">";
4867    else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble)
4868      cerr << "<" << CSDN->getValueAPF().convertToDouble() << ">";
4869    else {
4870      cerr << "<APFloat(";
4871      CSDN->getValueAPF().convertToAPInt().dump();
4872      cerr << ")>";
4873    }
4874  } else if (const GlobalAddressSDNode *GADN =
4875             dyn_cast<GlobalAddressSDNode>(this)) {
4876    int offset = GADN->getOffset();
4877    cerr << "<";
4878    WriteAsOperand(*cerr.stream(), GADN->getGlobal()) << ">";
4879    if (offset > 0)
4880      cerr << " + " << offset;
4881    else
4882      cerr << " " << offset;
4883  } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
4884    cerr << "<" << FIDN->getIndex() << ">";
4885  } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) {
4886    cerr << "<" << JTDN->getIndex() << ">";
4887  } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
4888    int offset = CP->getOffset();
4889    if (CP->isMachineConstantPoolEntry())
4890      cerr << "<" << *CP->getMachineCPVal() << ">";
4891    else
4892      cerr << "<" << *CP->getConstVal() << ">";
4893    if (offset > 0)
4894      cerr << " + " << offset;
4895    else
4896      cerr << " " << offset;
4897  } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
4898    cerr << "<";
4899    const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
4900    if (LBB)
4901      cerr << LBB->getName() << " ";
4902    cerr << (const void*)BBDN->getBasicBlock() << ">";
4903  } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
4904    if (G && R->getReg() &&
4905        TargetRegisterInfo::isPhysicalRegister(R->getReg())) {
4906      cerr << " " << G->getTarget().getRegisterInfo()->getName(R->getReg());
4907    } else {
4908      cerr << " #" << R->getReg();
4909    }
4910  } else if (const ExternalSymbolSDNode *ES =
4911             dyn_cast<ExternalSymbolSDNode>(this)) {
4912    cerr << "'" << ES->getSymbol() << "'";
4913  } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
4914    if (M->getValue())
4915      cerr << "<" << M->getValue() << ">";
4916    else
4917      cerr << "<null>";
4918  } else if (const MemOperandSDNode *M = dyn_cast<MemOperandSDNode>(this)) {
4919    if (M->MO.getValue())
4920      cerr << "<" << M->MO.getValue() << ":" << M->MO.getOffset() << ">";
4921    else
4922      cerr << "<null:" << M->MO.getOffset() << ">";
4923  } else if (const ARG_FLAGSSDNode *N = dyn_cast<ARG_FLAGSSDNode>(this)) {
4924    cerr << N->getArgFlags().getArgFlagsString();
4925  } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
4926    cerr << ":" << N->getVT().getMVTString();
4927  }
4928  else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
4929    const Value *SrcValue = LD->getSrcValue();
4930    int SrcOffset = LD->getSrcValueOffset();
4931    cerr << " <";
4932    if (SrcValue)
4933      cerr << SrcValue;
4934    else
4935      cerr << "null";
4936    cerr << ":" << SrcOffset << ">";
4937
4938    bool doExt = true;
4939    switch (LD->getExtensionType()) {
4940    default: doExt = false; break;
4941    case ISD::EXTLOAD:
4942      cerr << " <anyext ";
4943      break;
4944    case ISD::SEXTLOAD:
4945      cerr << " <sext ";
4946      break;
4947    case ISD::ZEXTLOAD:
4948      cerr << " <zext ";
4949      break;
4950    }
4951    if (doExt)
4952      cerr << LD->getMemoryVT().getMVTString() << ">";
4953
4954    const char *AM = getIndexedModeName(LD->getAddressingMode());
4955    if (*AM)
4956      cerr << " " << AM;
4957    if (LD->isVolatile())
4958      cerr << " <volatile>";
4959    cerr << " alignment=" << LD->getAlignment();
4960  } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) {
4961    const Value *SrcValue = ST->getSrcValue();
4962    int SrcOffset = ST->getSrcValueOffset();
4963    cerr << " <";
4964    if (SrcValue)
4965      cerr << SrcValue;
4966    else
4967      cerr << "null";
4968    cerr << ":" << SrcOffset << ">";
4969
4970    if (ST->isTruncatingStore())
4971      cerr << " <trunc "
4972           << ST->getMemoryVT().getMVTString() << ">";
4973
4974    const char *AM = getIndexedModeName(ST->getAddressingMode());
4975    if (*AM)
4976      cerr << " " << AM;
4977    if (ST->isVolatile())
4978      cerr << " <volatile>";
4979    cerr << " alignment=" << ST->getAlignment();
4980  } else if (const AtomicSDNode* AT = dyn_cast<AtomicSDNode>(this)) {
4981    const Value *SrcValue = AT->getSrcValue();
4982    int SrcOffset = AT->getSrcValueOffset();
4983    cerr << " <";
4984    if (SrcValue)
4985      cerr << SrcValue;
4986    else
4987      cerr << "null";
4988    cerr << ":" << SrcOffset << ">";
4989    if (AT->isVolatile())
4990      cerr << " <volatile>";
4991    cerr << " alignment=" << AT->getAlignment();
4992  }
4993}
4994
4995static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
4996  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4997    if (N->getOperand(i).Val->hasOneUse())
4998      DumpNodes(N->getOperand(i).Val, indent+2, G);
4999    else
5000      cerr << "\n" << std::string(indent+2, ' ')
5001           << (void*)N->getOperand(i).Val << ": <multiple use>";
5002
5003
5004  cerr << "\n" << std::string(indent, ' ');
5005  N->dump(G);
5006}
5007
5008void SelectionDAG::dump() const {
5009  cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
5010  std::vector<const SDNode*> Nodes;
5011  for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
5012       I != E; ++I)
5013    Nodes.push_back(I);
5014
5015  std::sort(Nodes.begin(), Nodes.end());
5016
5017  for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
5018    if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
5019      DumpNodes(Nodes[i], 2, this);
5020  }
5021
5022  if (getRoot().Val) DumpNodes(getRoot().Val, 2, this);
5023
5024  cerr << "\n\n";
5025}
5026
5027const Type *ConstantPoolSDNode::getType() const {
5028  if (isMachineConstantPoolEntry())
5029    return Val.MachineCPVal->getType();
5030  return Val.ConstVal->getType();
5031}
5032