SelectionDAG.cpp revision ba726ab3ec88b3b149b4caa34dec5ade5a3a7f89
1//===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This implements the SelectionDAG class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/SelectionDAG.h"
15#include "llvm/Constants.h"
16#include "llvm/GlobalValue.h"
17#include "llvm/Intrinsics.h"
18#include "llvm/Assembly/Writer.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineConstantPool.h"
21#include "llvm/Support/MathExtras.h"
22#include "llvm/Target/MRegisterInfo.h"
23#include "llvm/Target/TargetLowering.h"
24#include "llvm/Target/TargetInstrInfo.h"
25#include "llvm/Target/TargetMachine.h"
26#include "llvm/ADT/SetVector.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/StringExtras.h"
29#include <iostream>
30#include <set>
31#include <cmath>
32#include <algorithm>
33using namespace llvm;
34
35/// makeVTList - Return an instance of the SDVTList struct initialized with the
36/// specified members.
37static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
38  SDVTList Res = {VTs, NumVTs};
39  return Res;
40}
41
42// isInvertibleForFree - Return true if there is no cost to emitting the logical
43// inverse of this node.
44static bool isInvertibleForFree(SDOperand N) {
45  if (isa<ConstantSDNode>(N.Val)) return true;
46  if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse())
47    return true;
48  return false;
49}
50
51//===----------------------------------------------------------------------===//
52//                              ConstantFPSDNode Class
53//===----------------------------------------------------------------------===//
54
55/// isExactlyValue - We don't rely on operator== working on double values, as
56/// it returns true for things that are clearly not equal, like -0.0 and 0.0.
57/// As such, this method can be used to do an exact bit-for-bit comparison of
58/// two floating point values.
59bool ConstantFPSDNode::isExactlyValue(double V) const {
60  return DoubleToBits(V) == DoubleToBits(Value);
61}
62
63//===----------------------------------------------------------------------===//
64//                              ISD Namespace
65//===----------------------------------------------------------------------===//
66
67/// isBuildVectorAllOnes - Return true if the specified node is a
68/// BUILD_VECTOR where all of the elements are ~0 or undef.
69bool ISD::isBuildVectorAllOnes(const SDNode *N) {
70  // Look through a bit convert.
71  if (N->getOpcode() == ISD::BIT_CONVERT)
72    N = N->getOperand(0).Val;
73
74  if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
75
76  unsigned i = 0, e = N->getNumOperands();
77
78  // Skip over all of the undef values.
79  while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
80    ++i;
81
82  // Do not accept an all-undef vector.
83  if (i == e) return false;
84
85  // Do not accept build_vectors that aren't all constants or which have non-~0
86  // elements.
87  SDOperand NotZero = N->getOperand(i);
88  if (isa<ConstantSDNode>(NotZero)) {
89    if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
90      return false;
91  } else if (isa<ConstantFPSDNode>(NotZero)) {
92    MVT::ValueType VT = NotZero.getValueType();
93    if (VT== MVT::f64) {
94      if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
95          (uint64_t)-1)
96        return false;
97    } else {
98      if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
99          (uint32_t)-1)
100        return false;
101    }
102  } else
103    return false;
104
105  // Okay, we have at least one ~0 value, check to see if the rest match or are
106  // undefs.
107  for (++i; i != e; ++i)
108    if (N->getOperand(i) != NotZero &&
109        N->getOperand(i).getOpcode() != ISD::UNDEF)
110      return false;
111  return true;
112}
113
114
115/// isBuildVectorAllZeros - Return true if the specified node is a
116/// BUILD_VECTOR where all of the elements are 0 or undef.
117bool ISD::isBuildVectorAllZeros(const SDNode *N) {
118  // Look through a bit convert.
119  if (N->getOpcode() == ISD::BIT_CONVERT)
120    N = N->getOperand(0).Val;
121
122  if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
123
124  unsigned i = 0, e = N->getNumOperands();
125
126  // Skip over all of the undef values.
127  while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
128    ++i;
129
130  // Do not accept an all-undef vector.
131  if (i == e) return false;
132
133  // Do not accept build_vectors that aren't all constants or which have non-~0
134  // elements.
135  SDOperand Zero = N->getOperand(i);
136  if (isa<ConstantSDNode>(Zero)) {
137    if (!cast<ConstantSDNode>(Zero)->isNullValue())
138      return false;
139  } else if (isa<ConstantFPSDNode>(Zero)) {
140    if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0))
141      return false;
142  } else
143    return false;
144
145  // Okay, we have at least one ~0 value, check to see if the rest match or are
146  // undefs.
147  for (++i; i != e; ++i)
148    if (N->getOperand(i) != Zero &&
149        N->getOperand(i).getOpcode() != ISD::UNDEF)
150      return false;
151  return true;
152}
153
154/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
155/// when given the operation for (X op Y).
156ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
157  // To perform this operation, we just need to swap the L and G bits of the
158  // operation.
159  unsigned OldL = (Operation >> 2) & 1;
160  unsigned OldG = (Operation >> 1) & 1;
161  return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
162                       (OldL << 1) |       // New G bit
163                       (OldG << 2));        // New L bit.
164}
165
166/// getSetCCInverse - Return the operation corresponding to !(X op Y), where
167/// 'op' is a valid SetCC operation.
168ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
169  unsigned Operation = Op;
170  if (isInteger)
171    Operation ^= 7;   // Flip L, G, E bits, but not U.
172  else
173    Operation ^= 15;  // Flip all of the condition bits.
174  if (Operation > ISD::SETTRUE2)
175    Operation &= ~8;     // Don't let N and U bits get set.
176  return ISD::CondCode(Operation);
177}
178
179
180/// isSignedOp - For an integer comparison, return 1 if the comparison is a
181/// signed operation and 2 if the result is an unsigned comparison.  Return zero
182/// if the operation does not depend on the sign of the input (setne and seteq).
183static int isSignedOp(ISD::CondCode Opcode) {
184  switch (Opcode) {
185  default: assert(0 && "Illegal integer setcc operation!");
186  case ISD::SETEQ:
187  case ISD::SETNE: return 0;
188  case ISD::SETLT:
189  case ISD::SETLE:
190  case ISD::SETGT:
191  case ISD::SETGE: return 1;
192  case ISD::SETULT:
193  case ISD::SETULE:
194  case ISD::SETUGT:
195  case ISD::SETUGE: return 2;
196  }
197}
198
199/// getSetCCOrOperation - Return the result of a logical OR between different
200/// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
201/// returns SETCC_INVALID if it is not possible to represent the resultant
202/// comparison.
203ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
204                                       bool isInteger) {
205  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
206    // Cannot fold a signed integer setcc with an unsigned integer setcc.
207    return ISD::SETCC_INVALID;
208
209  unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
210
211  // If the N and U bits get set then the resultant comparison DOES suddenly
212  // care about orderedness, and is true when ordered.
213  if (Op > ISD::SETTRUE2)
214    Op &= ~16;     // Clear the U bit if the N bit is set.
215
216  // Canonicalize illegal integer setcc's.
217  if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
218    Op = ISD::SETNE;
219
220  return ISD::CondCode(Op);
221}
222
223/// getSetCCAndOperation - Return the result of a logical AND between different
224/// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
225/// function returns zero if it is not possible to represent the resultant
226/// comparison.
227ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
228                                        bool isInteger) {
229  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
230    // Cannot fold a signed setcc with an unsigned setcc.
231    return ISD::SETCC_INVALID;
232
233  // Combine all of the condition bits.
234  ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
235
236  // Canonicalize illegal integer setcc's.
237  if (isInteger) {
238    switch (Result) {
239    default: break;
240    case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
241    case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
242    case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
243    case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
244    }
245  }
246
247  return Result;
248}
249
250const TargetMachine &SelectionDAG::getTarget() const {
251  return TLI.getTargetMachine();
252}
253
254//===----------------------------------------------------------------------===//
255//                           SDNode Profile Support
256//===----------------------------------------------------------------------===//
257
258/// getNodeIDOpcode - Return the opcode that has been set for this NodeID.
259///
260static unsigned getNodeIDOpcode(FoldingSetNodeID &ID)  {
261  return ID.getRawData(0);
262}
263
264/// AddNodeIDOpcode - Add the node opcode to the NodeID data.
265///
266static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
267  ID.AddInteger(OpC);
268}
269
270/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
271/// solely with their pointer.
272void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
273  ID.AddPointer(VTList.VTs);
274}
275
276/// AddNodeIDOperand - Add an operands data to the NodeID data.
277///
278static void AddNodeIDOperand(FoldingSetNodeID &ID, SDOperand Op) {
279  ID.AddPointer(Op.Val);
280  ID.AddInteger(Op.ResNo);
281}
282
283/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
284///
285static void AddNodeIDOperands(FoldingSetNodeID &ID) {
286}
287static void AddNodeIDOperands(FoldingSetNodeID &ID, SDOperand Op) {
288  AddNodeIDOperand(ID, Op);
289}
290static void AddNodeIDOperands(FoldingSetNodeID &ID,
291                             SDOperand Op1, SDOperand Op2) {
292  AddNodeIDOperand(ID, Op1);
293  AddNodeIDOperand(ID, Op2);
294}
295static void AddNodeIDOperands(FoldingSetNodeID &ID,
296                              SDOperand Op1, SDOperand Op2, SDOperand Op3) {
297  AddNodeIDOperand(ID, Op1);
298  AddNodeIDOperand(ID, Op2);
299  AddNodeIDOperand(ID, Op3);
300}
301static void AddNodeIDOperands(FoldingSetNodeID &ID,
302                              const SDOperand *Ops, unsigned NumOps) {
303  for (; NumOps; --NumOps, ++Ops)
304    AddNodeIDOperand(ID, *Ops);
305}
306
307/// AddNodeIDOperands - Various routines for adding node info to the NodeID
308/// data.
309static void AddNodeIDNode(FoldingSetNodeID &ID,
310                          unsigned short OpC, SDVTList VTList) {
311  AddNodeIDOpcode(ID, OpC);
312  AddNodeIDValueTypes(ID, VTList);
313  AddNodeIDOperands(ID);
314}
315static void AddNodeIDNode(FoldingSetNodeID &ID,
316                          unsigned short OpC, SDVTList VTList,
317                          SDOperand Op) {
318  AddNodeIDOpcode(ID, OpC);
319  AddNodeIDValueTypes(ID, VTList);
320  AddNodeIDOperands(ID, Op);
321}
322static void AddNodeIDNode(FoldingSetNodeID &ID,
323                          unsigned short OpC, SDVTList VTList,
324                          SDOperand Op1, SDOperand Op2) {
325  AddNodeIDOpcode(ID, OpC);
326  AddNodeIDValueTypes(ID, VTList);
327  AddNodeIDOperands(ID, Op1, Op2);
328}
329static void AddNodeIDNode(FoldingSetNodeID &ID,
330                          unsigned short OpC, SDVTList VTList,
331                          SDOperand Op1, SDOperand Op2, SDOperand Op3) {
332  AddNodeIDOpcode(ID, OpC);
333  AddNodeIDValueTypes(ID, VTList);
334  AddNodeIDOperands(ID, Op1, Op2, Op3);
335}
336static void AddNodeIDNode(FoldingSetNodeID &ID,
337                          unsigned short OpC, SDVTList VTList,
338                          const SDOperand *OpList, unsigned N) {
339  AddNodeIDOpcode(ID, OpC);
340  AddNodeIDValueTypes(ID, VTList);
341  AddNodeIDOperands(ID, OpList, N);
342}
343
344/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
345/// data.
346static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
347  AddNodeIDOpcode(ID, N->getOpcode());
348  // Add the return value info.
349  AddNodeIDValueTypes(ID, N->getVTList());
350  // Add the operand info.
351  AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
352
353  // Handle SDNode leafs with special info.
354  if (N->getNumOperands() == 0) {
355    switch (N->getOpcode()) {
356    default: break;  // Normal nodes don't need extra info.
357    case ISD::TargetConstant:
358    case ISD::Constant:
359      ID.AddInteger(cast<ConstantSDNode>(N)->getValue());
360      break;
361    case ISD::TargetConstantFP:
362    case ISD::ConstantFP:
363      ID.AddDouble(cast<ConstantFPSDNode>(N)->getValue());
364      break;
365    case ISD::TargetGlobalAddress:
366    case ISD::GlobalAddress: {
367      GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
368      ID.AddPointer(GA->getGlobal());
369      ID.AddInteger(GA->getOffset());
370      break;
371    }
372    case ISD::BasicBlock:
373      ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
374      break;
375    case ISD::Register:
376      ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
377      break;
378    case ISD::SRCVALUE: {
379      SrcValueSDNode *SV = cast<SrcValueSDNode>(N);
380      ID.AddPointer(SV->getValue());
381      ID.AddInteger(SV->getOffset());
382      break;
383    }
384    case ISD::FrameIndex:
385    case ISD::TargetFrameIndex:
386      ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
387      break;
388    case ISD::JumpTable:
389    case ISD::TargetJumpTable:
390      ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
391      break;
392    case ISD::ConstantPool:
393    case ISD::TargetConstantPool: {
394      ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
395      ID.AddInteger(CP->getAlignment());
396      ID.AddInteger(CP->getOffset());
397      if (CP->isMachineConstantPoolEntry())
398        CP->getMachineCPVal()->AddSelectionDAGCSEId(ID);
399      else
400        ID.AddPointer(CP->getConstVal());
401      break;
402    }
403    case ISD::LOAD: {
404      LoadSDNode *LD = cast<LoadSDNode>(N);
405      ID.AddInteger(LD->getAddressingMode());
406      ID.AddInteger(LD->getExtensionType());
407      ID.AddInteger(LD->getLoadedVT());
408      ID.AddPointer(LD->getSrcValue());
409      ID.AddInteger(LD->getSrcValueOffset());
410      ID.AddInteger(LD->getAlignment());
411      ID.AddInteger(LD->isVolatile());
412      break;
413    }
414    case ISD::STORE: {
415      StoreSDNode *ST = cast<StoreSDNode>(N);
416      ID.AddInteger(ST->getAddressingMode());
417      ID.AddInteger(ST->isTruncatingStore());
418      ID.AddInteger(ST->getStoredVT());
419      ID.AddPointer(ST->getSrcValue());
420      ID.AddInteger(ST->getSrcValueOffset());
421      ID.AddInteger(ST->getAlignment());
422      ID.AddInteger(ST->isVolatile());
423      break;
424    }
425    }
426  }
427}
428
429//===----------------------------------------------------------------------===//
430//                              SelectionDAG Class
431//===----------------------------------------------------------------------===//
432
433/// RemoveDeadNodes - This method deletes all unreachable nodes in the
434/// SelectionDAG.
435void SelectionDAG::RemoveDeadNodes() {
436  // Create a dummy node (which is not added to allnodes), that adds a reference
437  // to the root node, preventing it from being deleted.
438  HandleSDNode Dummy(getRoot());
439
440  SmallVector<SDNode*, 128> DeadNodes;
441
442  // Add all obviously-dead nodes to the DeadNodes worklist.
443  for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
444    if (I->use_empty())
445      DeadNodes.push_back(I);
446
447  // Process the worklist, deleting the nodes and adding their uses to the
448  // worklist.
449  while (!DeadNodes.empty()) {
450    SDNode *N = DeadNodes.back();
451    DeadNodes.pop_back();
452
453    // Take the node out of the appropriate CSE map.
454    RemoveNodeFromCSEMaps(N);
455
456    // Next, brutally remove the operand list.  This is safe to do, as there are
457    // no cycles in the graph.
458    for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
459      SDNode *Operand = I->Val;
460      Operand->removeUser(N);
461
462      // Now that we removed this operand, see if there are no uses of it left.
463      if (Operand->use_empty())
464        DeadNodes.push_back(Operand);
465    }
466    delete[] N->OperandList;
467    N->OperandList = 0;
468    N->NumOperands = 0;
469
470    // Finally, remove N itself.
471    AllNodes.erase(N);
472  }
473
474  // If the root changed (e.g. it was a dead load, update the root).
475  setRoot(Dummy.getValue());
476}
477
478void SelectionDAG::RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted) {
479  SmallVector<SDNode*, 16> DeadNodes;
480  DeadNodes.push_back(N);
481
482  // Process the worklist, deleting the nodes and adding their uses to the
483  // worklist.
484  while (!DeadNodes.empty()) {
485    SDNode *N = DeadNodes.back();
486    DeadNodes.pop_back();
487
488    // Take the node out of the appropriate CSE map.
489    RemoveNodeFromCSEMaps(N);
490
491    // Next, brutally remove the operand list.  This is safe to do, as there are
492    // no cycles in the graph.
493    for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
494      SDNode *Operand = I->Val;
495      Operand->removeUser(N);
496
497      // Now that we removed this operand, see if there are no uses of it left.
498      if (Operand->use_empty())
499        DeadNodes.push_back(Operand);
500    }
501    delete[] N->OperandList;
502    N->OperandList = 0;
503    N->NumOperands = 0;
504
505    // Finally, remove N itself.
506    Deleted.push_back(N);
507    AllNodes.erase(N);
508  }
509}
510
511void SelectionDAG::DeleteNode(SDNode *N) {
512  assert(N->use_empty() && "Cannot delete a node that is not dead!");
513
514  // First take this out of the appropriate CSE map.
515  RemoveNodeFromCSEMaps(N);
516
517  // Finally, remove uses due to operands of this node, remove from the
518  // AllNodes list, and delete the node.
519  DeleteNodeNotInCSEMaps(N);
520}
521
522void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
523
524  // Remove it from the AllNodes list.
525  AllNodes.remove(N);
526
527  // Drop all of the operands and decrement used nodes use counts.
528  for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
529    I->Val->removeUser(N);
530  delete[] N->OperandList;
531  N->OperandList = 0;
532  N->NumOperands = 0;
533
534  delete N;
535}
536
537/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
538/// correspond to it.  This is useful when we're about to delete or repurpose
539/// the node.  We don't want future request for structurally identical nodes
540/// to return N anymore.
541void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
542  bool Erased = false;
543  switch (N->getOpcode()) {
544  case ISD::HANDLENODE: return;  // noop.
545  case ISD::STRING:
546    Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue());
547    break;
548  case ISD::CONDCODE:
549    assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
550           "Cond code doesn't exist!");
551    Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
552    CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
553    break;
554  case ISD::ExternalSymbol:
555    Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
556    break;
557  case ISD::TargetExternalSymbol:
558    Erased =
559      TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
560    break;
561  case ISD::VALUETYPE:
562    Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0;
563    ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0;
564    break;
565  default:
566    // Remove it from the CSE Map.
567    Erased = CSEMap.RemoveNode(N);
568    break;
569  }
570#ifndef NDEBUG
571  // Verify that the node was actually in one of the CSE maps, unless it has a
572  // flag result (which cannot be CSE'd) or is one of the special cases that are
573  // not subject to CSE.
574  if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
575      !N->isTargetOpcode()) {
576    N->dump();
577    std::cerr << "\n";
578    assert(0 && "Node is not in map!");
579  }
580#endif
581}
582
583/// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
584/// has been taken out and modified in some way.  If the specified node already
585/// exists in the CSE maps, do not modify the maps, but return the existing node
586/// instead.  If it doesn't exist, add it and return null.
587///
588SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
589  assert(N->getNumOperands() && "This is a leaf node!");
590  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
591    return 0;    // Never add these nodes.
592
593  // Check that remaining values produced are not flags.
594  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
595    if (N->getValueType(i) == MVT::Flag)
596      return 0;   // Never CSE anything that produces a flag.
597
598  SDNode *New = CSEMap.GetOrInsertNode(N);
599  if (New != N) return New;  // Node already existed.
600  return 0;
601}
602
603/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
604/// were replaced with those specified.  If this node is never memoized,
605/// return null, otherwise return a pointer to the slot it would take.  If a
606/// node already exists with these operands, the slot will be non-null.
607SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
608                                           void *&InsertPos) {
609  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
610    return 0;    // Never add these nodes.
611
612  // Check that remaining values produced are not flags.
613  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
614    if (N->getValueType(i) == MVT::Flag)
615      return 0;   // Never CSE anything that produces a flag.
616
617  FoldingSetNodeID ID;
618  AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op);
619  return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
620}
621
622/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
623/// were replaced with those specified.  If this node is never memoized,
624/// return null, otherwise return a pointer to the slot it would take.  If a
625/// node already exists with these operands, the slot will be non-null.
626SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
627                                           SDOperand Op1, SDOperand Op2,
628                                           void *&InsertPos) {
629  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
630    return 0;    // Never add these nodes.
631
632  // Check that remaining values produced are not flags.
633  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
634    if (N->getValueType(i) == MVT::Flag)
635      return 0;   // Never CSE anything that produces a flag.
636
637  FoldingSetNodeID ID;
638  AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op1, Op2);
639  return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
640}
641
642
643/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
644/// were replaced with those specified.  If this node is never memoized,
645/// return null, otherwise return a pointer to the slot it would take.  If a
646/// node already exists with these operands, the slot will be non-null.
647SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
648                                           const SDOperand *Ops,unsigned NumOps,
649                                           void *&InsertPos) {
650  if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
651    return 0;    // Never add these nodes.
652
653  // Check that remaining values produced are not flags.
654  for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
655    if (N->getValueType(i) == MVT::Flag)
656      return 0;   // Never CSE anything that produces a flag.
657
658  FoldingSetNodeID ID;
659  AddNodeIDNode(ID, N->getOpcode(), N->getVTList());
660
661  if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
662    ID.AddInteger(LD->getAddressingMode());
663    ID.AddInteger(LD->getExtensionType());
664    ID.AddInteger(LD->getLoadedVT());
665    ID.AddPointer(LD->getSrcValue());
666    ID.AddInteger(LD->getSrcValueOffset());
667    ID.AddInteger(LD->getAlignment());
668    ID.AddInteger(LD->isVolatile());
669  } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
670    ID.AddInteger(ST->getAddressingMode());
671    ID.AddInteger(ST->isTruncatingStore());
672    ID.AddInteger(ST->getStoredVT());
673    ID.AddPointer(ST->getSrcValue());
674    ID.AddInteger(ST->getSrcValueOffset());
675    ID.AddInteger(ST->getAlignment());
676    ID.AddInteger(ST->isVolatile());
677  }
678
679  AddNodeIDOperands(ID, Ops, NumOps);
680  return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
681}
682
683
684SelectionDAG::~SelectionDAG() {
685  while (!AllNodes.empty()) {
686    SDNode *N = AllNodes.begin();
687    N->SetNextInBucket(0);
688    delete [] N->OperandList;
689    N->OperandList = 0;
690    N->NumOperands = 0;
691    AllNodes.pop_front();
692  }
693}
694
695SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
696  if (Op.getValueType() == VT) return Op;
697  int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT));
698  return getNode(ISD::AND, Op.getValueType(), Op,
699                 getConstant(Imm, Op.getValueType()));
700}
701
702SDOperand SelectionDAG::getString(const std::string &Val) {
703  StringSDNode *&N = StringNodes[Val];
704  if (!N) {
705    N = new StringSDNode(Val);
706    AllNodes.push_back(N);
707  }
708  return SDOperand(N, 0);
709}
710
711SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) {
712  assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
713  assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!");
714
715  // Mask out any bits that are not valid for this constant.
716  Val &= MVT::getIntVTBitMask(VT);
717
718  unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
719  FoldingSetNodeID ID;
720  AddNodeIDNode(ID, Opc, getVTList(VT));
721  ID.AddInteger(Val);
722  void *IP = 0;
723  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
724    return SDOperand(E, 0);
725  SDNode *N = new ConstantSDNode(isT, Val, VT);
726  CSEMap.InsertNode(N, IP);
727  AllNodes.push_back(N);
728  return SDOperand(N, 0);
729}
730
731
732SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT,
733                                      bool isTarget) {
734  assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
735  if (VT == MVT::f32)
736    Val = (float)Val;  // Mask out extra precision.
737
738  // Do the map lookup using the actual bit pattern for the floating point
739  // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
740  // we don't have issues with SNANs.
741  unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
742  FoldingSetNodeID ID;
743  AddNodeIDNode(ID, Opc, getVTList(VT));
744  ID.AddDouble(Val);
745  void *IP = 0;
746  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
747    return SDOperand(E, 0);
748  SDNode *N = new ConstantFPSDNode(isTarget, Val, VT);
749  CSEMap.InsertNode(N, IP);
750  AllNodes.push_back(N);
751  return SDOperand(N, 0);
752}
753
754SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
755                                         MVT::ValueType VT, int Offset,
756                                         bool isTargetGA) {
757  unsigned Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
758  FoldingSetNodeID ID;
759  AddNodeIDNode(ID, Opc, getVTList(VT));
760  ID.AddPointer(GV);
761  ID.AddInteger(Offset);
762  void *IP = 0;
763  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
764   return SDOperand(E, 0);
765  SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
766  CSEMap.InsertNode(N, IP);
767  AllNodes.push_back(N);
768  return SDOperand(N, 0);
769}
770
771SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT,
772                                      bool isTarget) {
773  unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
774  FoldingSetNodeID ID;
775  AddNodeIDNode(ID, Opc, getVTList(VT));
776  ID.AddInteger(FI);
777  void *IP = 0;
778  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
779    return SDOperand(E, 0);
780  SDNode *N = new FrameIndexSDNode(FI, VT, isTarget);
781  CSEMap.InsertNode(N, IP);
782  AllNodes.push_back(N);
783  return SDOperand(N, 0);
784}
785
786SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){
787  unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
788  FoldingSetNodeID ID;
789  AddNodeIDNode(ID, Opc, getVTList(VT));
790  ID.AddInteger(JTI);
791  void *IP = 0;
792  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
793    return SDOperand(E, 0);
794  SDNode *N = new JumpTableSDNode(JTI, VT, isTarget);
795  CSEMap.InsertNode(N, IP);
796  AllNodes.push_back(N);
797  return SDOperand(N, 0);
798}
799
800SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
801                                        unsigned Alignment, int Offset,
802                                        bool isTarget) {
803  unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
804  FoldingSetNodeID ID;
805  AddNodeIDNode(ID, Opc, getVTList(VT));
806  ID.AddInteger(Alignment);
807  ID.AddInteger(Offset);
808  ID.AddPointer(C);
809  void *IP = 0;
810  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
811    return SDOperand(E, 0);
812  SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
813  CSEMap.InsertNode(N, IP);
814  AllNodes.push_back(N);
815  return SDOperand(N, 0);
816}
817
818
819SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C,
820                                        MVT::ValueType VT,
821                                        unsigned Alignment, int Offset,
822                                        bool isTarget) {
823  unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
824  FoldingSetNodeID ID;
825  AddNodeIDNode(ID, Opc, getVTList(VT));
826  ID.AddInteger(Alignment);
827  ID.AddInteger(Offset);
828  C->AddSelectionDAGCSEId(ID);
829  void *IP = 0;
830  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
831    return SDOperand(E, 0);
832  SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
833  CSEMap.InsertNode(N, IP);
834  AllNodes.push_back(N);
835  return SDOperand(N, 0);
836}
837
838
839SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
840  FoldingSetNodeID ID;
841  AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other));
842  ID.AddPointer(MBB);
843  void *IP = 0;
844  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
845    return SDOperand(E, 0);
846  SDNode *N = new BasicBlockSDNode(MBB);
847  CSEMap.InsertNode(N, IP);
848  AllNodes.push_back(N);
849  return SDOperand(N, 0);
850}
851
852SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
853  if ((unsigned)VT >= ValueTypeNodes.size())
854    ValueTypeNodes.resize(VT+1);
855  if (ValueTypeNodes[VT] == 0) {
856    ValueTypeNodes[VT] = new VTSDNode(VT);
857    AllNodes.push_back(ValueTypeNodes[VT]);
858  }
859
860  return SDOperand(ValueTypeNodes[VT], 0);
861}
862
863SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
864  SDNode *&N = ExternalSymbols[Sym];
865  if (N) return SDOperand(N, 0);
866  N = new ExternalSymbolSDNode(false, Sym, VT);
867  AllNodes.push_back(N);
868  return SDOperand(N, 0);
869}
870
871SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym,
872                                                MVT::ValueType VT) {
873  SDNode *&N = TargetExternalSymbols[Sym];
874  if (N) return SDOperand(N, 0);
875  N = new ExternalSymbolSDNode(true, Sym, VT);
876  AllNodes.push_back(N);
877  return SDOperand(N, 0);
878}
879
880SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
881  if ((unsigned)Cond >= CondCodeNodes.size())
882    CondCodeNodes.resize(Cond+1);
883
884  if (CondCodeNodes[Cond] == 0) {
885    CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
886    AllNodes.push_back(CondCodeNodes[Cond]);
887  }
888  return SDOperand(CondCodeNodes[Cond], 0);
889}
890
891SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
892  FoldingSetNodeID ID;
893  AddNodeIDNode(ID, ISD::Register, getVTList(VT));
894  ID.AddInteger(RegNo);
895  void *IP = 0;
896  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
897    return SDOperand(E, 0);
898  SDNode *N = new RegisterSDNode(RegNo, VT);
899  CSEMap.InsertNode(N, IP);
900  AllNodes.push_back(N);
901  return SDOperand(N, 0);
902}
903
904SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) {
905  assert((!V || isa<PointerType>(V->getType())) &&
906         "SrcValue is not a pointer?");
907
908  FoldingSetNodeID ID;
909  AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other));
910  ID.AddPointer(V);
911  ID.AddInteger(Offset);
912  void *IP = 0;
913  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
914    return SDOperand(E, 0);
915  SDNode *N = new SrcValueSDNode(V, Offset);
916  CSEMap.InsertNode(N, IP);
917  AllNodes.push_back(N);
918  return SDOperand(N, 0);
919}
920
921SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1,
922                                  SDOperand N2, ISD::CondCode Cond) {
923  // These setcc operations always fold.
924  switch (Cond) {
925  default: break;
926  case ISD::SETFALSE:
927  case ISD::SETFALSE2: return getConstant(0, VT);
928  case ISD::SETTRUE:
929  case ISD::SETTRUE2:  return getConstant(1, VT);
930
931  case ISD::SETOEQ:
932  case ISD::SETOGT:
933  case ISD::SETOGE:
934  case ISD::SETOLT:
935  case ISD::SETOLE:
936  case ISD::SETONE:
937  case ISD::SETO:
938  case ISD::SETUO:
939  case ISD::SETUEQ:
940  case ISD::SETUNE:
941    assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!");
942    break;
943  }
944
945  if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
946    uint64_t C2 = N2C->getValue();
947    if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
948      uint64_t C1 = N1C->getValue();
949
950      // Sign extend the operands if required
951      if (ISD::isSignedIntSetCC(Cond)) {
952        C1 = N1C->getSignExtended();
953        C2 = N2C->getSignExtended();
954      }
955
956      switch (Cond) {
957      default: assert(0 && "Unknown integer setcc!");
958      case ISD::SETEQ:  return getConstant(C1 == C2, VT);
959      case ISD::SETNE:  return getConstant(C1 != C2, VT);
960      case ISD::SETULT: return getConstant(C1 <  C2, VT);
961      case ISD::SETUGT: return getConstant(C1 >  C2, VT);
962      case ISD::SETULE: return getConstant(C1 <= C2, VT);
963      case ISD::SETUGE: return getConstant(C1 >= C2, VT);
964      case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
965      case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
966      case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
967      case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
968      }
969    }
970  }
971  if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
972    if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
973      double C1 = N1C->getValue(), C2 = N2C->getValue();
974
975      switch (Cond) {
976      default: break; // FIXME: Implement the rest of these!
977      case ISD::SETEQ:  return getConstant(C1 == C2, VT);
978      case ISD::SETNE:  return getConstant(C1 != C2, VT);
979      case ISD::SETLT:  return getConstant(C1 < C2, VT);
980      case ISD::SETGT:  return getConstant(C1 > C2, VT);
981      case ISD::SETLE:  return getConstant(C1 <= C2, VT);
982      case ISD::SETGE:  return getConstant(C1 >= C2, VT);
983      }
984    } else {
985      // Ensure that the constant occurs on the RHS.
986      return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
987    }
988
989  // Could not fold it.
990  return SDOperand();
991}
992
993
994/// getNode - Gets or creates the specified node.
995///
996SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
997  FoldingSetNodeID ID;
998  AddNodeIDNode(ID, Opcode, getVTList(VT));
999  void *IP = 0;
1000  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1001    return SDOperand(E, 0);
1002  SDNode *N = new SDNode(Opcode, VT);
1003  CSEMap.InsertNode(N, IP);
1004
1005  AllNodes.push_back(N);
1006  return SDOperand(N, 0);
1007}
1008
1009SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1010                                SDOperand Operand) {
1011  unsigned Tmp1;
1012  // Constant fold unary operations with an integer constant operand.
1013  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
1014    uint64_t Val = C->getValue();
1015    switch (Opcode) {
1016    default: break;
1017    case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
1018    case ISD::ANY_EXTEND:
1019    case ISD::ZERO_EXTEND: return getConstant(Val, VT);
1020    case ISD::TRUNCATE:    return getConstant(Val, VT);
1021    case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
1022    case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
1023    case ISD::BIT_CONVERT:
1024      if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
1025        return getConstantFP(BitsToFloat(Val), VT);
1026      else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
1027        return getConstantFP(BitsToDouble(Val), VT);
1028      break;
1029    case ISD::BSWAP:
1030      switch(VT) {
1031      default: assert(0 && "Invalid bswap!"); break;
1032      case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT);
1033      case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT);
1034      case MVT::i64: return getConstant(ByteSwap_64(Val), VT);
1035      }
1036      break;
1037    case ISD::CTPOP:
1038      switch(VT) {
1039      default: assert(0 && "Invalid ctpop!"); break;
1040      case MVT::i1: return getConstant(Val != 0, VT);
1041      case MVT::i8:
1042        Tmp1 = (unsigned)Val & 0xFF;
1043        return getConstant(CountPopulation_32(Tmp1), VT);
1044      case MVT::i16:
1045        Tmp1 = (unsigned)Val & 0xFFFF;
1046        return getConstant(CountPopulation_32(Tmp1), VT);
1047      case MVT::i32:
1048        return getConstant(CountPopulation_32((unsigned)Val), VT);
1049      case MVT::i64:
1050        return getConstant(CountPopulation_64(Val), VT);
1051      }
1052    case ISD::CTLZ:
1053      switch(VT) {
1054      default: assert(0 && "Invalid ctlz!"); break;
1055      case MVT::i1: return getConstant(Val == 0, VT);
1056      case MVT::i8:
1057        Tmp1 = (unsigned)Val & 0xFF;
1058        return getConstant(CountLeadingZeros_32(Tmp1)-24, VT);
1059      case MVT::i16:
1060        Tmp1 = (unsigned)Val & 0xFFFF;
1061        return getConstant(CountLeadingZeros_32(Tmp1)-16, VT);
1062      case MVT::i32:
1063        return getConstant(CountLeadingZeros_32((unsigned)Val), VT);
1064      case MVT::i64:
1065        return getConstant(CountLeadingZeros_64(Val), VT);
1066      }
1067    case ISD::CTTZ:
1068      switch(VT) {
1069      default: assert(0 && "Invalid cttz!"); break;
1070      case MVT::i1: return getConstant(Val == 0, VT);
1071      case MVT::i8:
1072        Tmp1 = (unsigned)Val | 0x100;
1073        return getConstant(CountTrailingZeros_32(Tmp1), VT);
1074      case MVT::i16:
1075        Tmp1 = (unsigned)Val | 0x10000;
1076        return getConstant(CountTrailingZeros_32(Tmp1), VT);
1077      case MVT::i32:
1078        return getConstant(CountTrailingZeros_32((unsigned)Val), VT);
1079      case MVT::i64:
1080        return getConstant(CountTrailingZeros_64(Val), VT);
1081      }
1082    }
1083  }
1084
1085  // Constant fold unary operations with an floating point constant operand.
1086  if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
1087    switch (Opcode) {
1088    case ISD::FNEG:
1089      return getConstantFP(-C->getValue(), VT);
1090    case ISD::FABS:
1091      return getConstantFP(fabs(C->getValue()), VT);
1092    case ISD::FP_ROUND:
1093    case ISD::FP_EXTEND:
1094      return getConstantFP(C->getValue(), VT);
1095    case ISD::FP_TO_SINT:
1096      return getConstant((int64_t)C->getValue(), VT);
1097    case ISD::FP_TO_UINT:
1098      return getConstant((uint64_t)C->getValue(), VT);
1099    case ISD::BIT_CONVERT:
1100      if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
1101        return getConstant(FloatToBits(C->getValue()), VT);
1102      else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
1103        return getConstant(DoubleToBits(C->getValue()), VT);
1104      break;
1105    }
1106
1107  unsigned OpOpcode = Operand.Val->getOpcode();
1108  switch (Opcode) {
1109  case ISD::TokenFactor:
1110    return Operand;         // Factor of one node?  No factor.
1111  case ISD::SIGN_EXTEND:
1112    if (Operand.getValueType() == VT) return Operand;   // noop extension
1113    assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!");
1114    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
1115      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1116    break;
1117  case ISD::ZERO_EXTEND:
1118    if (Operand.getValueType() == VT) return Operand;   // noop extension
1119    assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!");
1120    if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
1121      return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
1122    break;
1123  case ISD::ANY_EXTEND:
1124    if (Operand.getValueType() == VT) return Operand;   // noop extension
1125    assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!");
1126    if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
1127      // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
1128      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1129    break;
1130  case ISD::TRUNCATE:
1131    if (Operand.getValueType() == VT) return Operand;   // noop truncate
1132    assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!");
1133    if (OpOpcode == ISD::TRUNCATE)
1134      return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1135    else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
1136             OpOpcode == ISD::ANY_EXTEND) {
1137      // If the source is smaller than the dest, we still need an extend.
1138      if (Operand.Val->getOperand(0).getValueType() < VT)
1139        return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1140      else if (Operand.Val->getOperand(0).getValueType() > VT)
1141        return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1142      else
1143        return Operand.Val->getOperand(0);
1144    }
1145    break;
1146  case ISD::BIT_CONVERT:
1147    // Basic sanity checking.
1148    assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType())
1149           && "Cannot BIT_CONVERT between two different types!");
1150    if (VT == Operand.getValueType()) return Operand;  // noop conversion.
1151    if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
1152      return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
1153    if (OpOpcode == ISD::UNDEF)
1154      return getNode(ISD::UNDEF, VT);
1155    break;
1156  case ISD::SCALAR_TO_VECTOR:
1157    assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) &&
1158           MVT::getVectorBaseType(VT) == Operand.getValueType() &&
1159           "Illegal SCALAR_TO_VECTOR node!");
1160    break;
1161  case ISD::FNEG:
1162    if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
1163      return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
1164                     Operand.Val->getOperand(0));
1165    if (OpOpcode == ISD::FNEG)  // --X -> X
1166      return Operand.Val->getOperand(0);
1167    break;
1168  case ISD::FABS:
1169    if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
1170      return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
1171    break;
1172  }
1173
1174  SDNode *N;
1175  SDVTList VTs = getVTList(VT);
1176  if (VT != MVT::Flag) { // Don't CSE flag producing nodes
1177    FoldingSetNodeID ID;
1178    AddNodeIDNode(ID, Opcode, VTs, Operand);
1179    void *IP = 0;
1180    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1181      return SDOperand(E, 0);
1182    N = new SDNode(Opcode, Operand);
1183    N->setValueTypes(VTs);
1184    CSEMap.InsertNode(N, IP);
1185  } else {
1186    N = new SDNode(Opcode, Operand);
1187    N->setValueTypes(VTs);
1188  }
1189  AllNodes.push_back(N);
1190  return SDOperand(N, 0);
1191}
1192
1193
1194
1195SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1196                                SDOperand N1, SDOperand N2) {
1197#ifndef NDEBUG
1198  switch (Opcode) {
1199  case ISD::TokenFactor:
1200    assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
1201           N2.getValueType() == MVT::Other && "Invalid token factor!");
1202    break;
1203  case ISD::AND:
1204  case ISD::OR:
1205  case ISD::XOR:
1206  case ISD::UDIV:
1207  case ISD::UREM:
1208  case ISD::MULHU:
1209  case ISD::MULHS:
1210    assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
1211    // fall through
1212  case ISD::ADD:
1213  case ISD::SUB:
1214  case ISD::MUL:
1215  case ISD::SDIV:
1216  case ISD::SREM:
1217    assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops");
1218    // fall through.
1219  case ISD::FADD:
1220  case ISD::FSUB:
1221  case ISD::FMUL:
1222  case ISD::FDIV:
1223  case ISD::FREM:
1224    assert(N1.getValueType() == N2.getValueType() &&
1225           N1.getValueType() == VT && "Binary operator types must match!");
1226    break;
1227  case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
1228    assert(N1.getValueType() == VT &&
1229           MVT::isFloatingPoint(N1.getValueType()) &&
1230           MVT::isFloatingPoint(N2.getValueType()) &&
1231           "Invalid FCOPYSIGN!");
1232    break;
1233  case ISD::SHL:
1234  case ISD::SRA:
1235  case ISD::SRL:
1236  case ISD::ROTL:
1237  case ISD::ROTR:
1238    assert(VT == N1.getValueType() &&
1239           "Shift operators return type must be the same as their first arg");
1240    assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
1241           VT != MVT::i1 && "Shifts only work on integers");
1242    break;
1243  case ISD::FP_ROUND_INREG: {
1244    MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1245    assert(VT == N1.getValueType() && "Not an inreg round!");
1246    assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
1247           "Cannot FP_ROUND_INREG integer types");
1248    assert(EVT <= VT && "Not rounding down!");
1249    break;
1250  }
1251  case ISD::AssertSext:
1252  case ISD::AssertZext:
1253  case ISD::SIGN_EXTEND_INREG: {
1254    MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1255    assert(VT == N1.getValueType() && "Not an inreg extend!");
1256    assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
1257           "Cannot *_EXTEND_INREG FP types");
1258    assert(EVT <= VT && "Not extending!");
1259  }
1260
1261  default: break;
1262  }
1263#endif
1264
1265  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1266  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1267  if (N1C) {
1268    if (Opcode == ISD::SIGN_EXTEND_INREG) {
1269      int64_t Val = N1C->getValue();
1270      unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT());
1271      Val <<= 64-FromBits;
1272      Val >>= 64-FromBits;
1273      return getConstant(Val, VT);
1274    }
1275
1276    if (N2C) {
1277      uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
1278      switch (Opcode) {
1279      case ISD::ADD: return getConstant(C1 + C2, VT);
1280      case ISD::SUB: return getConstant(C1 - C2, VT);
1281      case ISD::MUL: return getConstant(C1 * C2, VT);
1282      case ISD::UDIV:
1283        if (C2) return getConstant(C1 / C2, VT);
1284        break;
1285      case ISD::UREM :
1286        if (C2) return getConstant(C1 % C2, VT);
1287        break;
1288      case ISD::SDIV :
1289        if (C2) return getConstant(N1C->getSignExtended() /
1290                                   N2C->getSignExtended(), VT);
1291        break;
1292      case ISD::SREM :
1293        if (C2) return getConstant(N1C->getSignExtended() %
1294                                   N2C->getSignExtended(), VT);
1295        break;
1296      case ISD::AND  : return getConstant(C1 & C2, VT);
1297      case ISD::OR   : return getConstant(C1 | C2, VT);
1298      case ISD::XOR  : return getConstant(C1 ^ C2, VT);
1299      case ISD::SHL  : return getConstant(C1 << C2, VT);
1300      case ISD::SRL  : return getConstant(C1 >> C2, VT);
1301      case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
1302      case ISD::ROTL :
1303        return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)),
1304                           VT);
1305      case ISD::ROTR :
1306        return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)),
1307                           VT);
1308      default: break;
1309      }
1310    } else {      // Cannonicalize constant to RHS if commutative
1311      if (isCommutativeBinOp(Opcode)) {
1312        std::swap(N1C, N2C);
1313        std::swap(N1, N2);
1314      }
1315    }
1316  }
1317
1318  ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
1319  ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
1320  if (N1CFP) {
1321    if (N2CFP) {
1322      double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
1323      switch (Opcode) {
1324      case ISD::FADD: return getConstantFP(C1 + C2, VT);
1325      case ISD::FSUB: return getConstantFP(C1 - C2, VT);
1326      case ISD::FMUL: return getConstantFP(C1 * C2, VT);
1327      case ISD::FDIV:
1328        if (C2) return getConstantFP(C1 / C2, VT);
1329        break;
1330      case ISD::FREM :
1331        if (C2) return getConstantFP(fmod(C1, C2), VT);
1332        break;
1333      case ISD::FCOPYSIGN: {
1334        union {
1335          double   F;
1336          uint64_t I;
1337        } u1;
1338        union {
1339          double  F;
1340          int64_t I;
1341        } u2;
1342        u1.F = C1;
1343        u2.F = C2;
1344        if (u2.I < 0)  // Sign bit of RHS set?
1345          u1.I |= 1ULL << 63;      // Set the sign bit of the LHS.
1346        else
1347          u1.I &= (1ULL << 63)-1;  // Clear the sign bit of the LHS.
1348        return getConstantFP(u1.F, VT);
1349      }
1350      default: break;
1351      }
1352    } else {      // Cannonicalize constant to RHS if commutative
1353      if (isCommutativeBinOp(Opcode)) {
1354        std::swap(N1CFP, N2CFP);
1355        std::swap(N1, N2);
1356      }
1357    }
1358  }
1359
1360  // Canonicalize an UNDEF to the RHS, even over a constant.
1361  if (N1.getOpcode() == ISD::UNDEF) {
1362    if (isCommutativeBinOp(Opcode)) {
1363      std::swap(N1, N2);
1364    } else {
1365      switch (Opcode) {
1366      case ISD::FP_ROUND_INREG:
1367      case ISD::SIGN_EXTEND_INREG:
1368      case ISD::SUB:
1369      case ISD::FSUB:
1370      case ISD::FDIV:
1371      case ISD::FREM:
1372      case ISD::SRA:
1373        return N1;     // fold op(undef, arg2) -> undef
1374      case ISD::UDIV:
1375      case ISD::SDIV:
1376      case ISD::UREM:
1377      case ISD::SREM:
1378      case ISD::SRL:
1379      case ISD::SHL:
1380        return getConstant(0, VT);    // fold op(undef, arg2) -> 0
1381      }
1382    }
1383  }
1384
1385  // Fold a bunch of operators when the RHS is undef.
1386  if (N2.getOpcode() == ISD::UNDEF) {
1387    switch (Opcode) {
1388    case ISD::ADD:
1389    case ISD::SUB:
1390    case ISD::FADD:
1391    case ISD::FSUB:
1392    case ISD::FMUL:
1393    case ISD::FDIV:
1394    case ISD::FREM:
1395    case ISD::UDIV:
1396    case ISD::SDIV:
1397    case ISD::UREM:
1398    case ISD::SREM:
1399    case ISD::XOR:
1400      return N2;       // fold op(arg1, undef) -> undef
1401    case ISD::MUL:
1402    case ISD::AND:
1403    case ISD::SRL:
1404    case ISD::SHL:
1405      return getConstant(0, VT);  // fold op(arg1, undef) -> 0
1406    case ISD::OR:
1407      return getConstant(MVT::getIntVTBitMask(VT), VT);
1408    case ISD::SRA:
1409      return N1;
1410    }
1411  }
1412
1413  // Fold operations.
1414  switch (Opcode) {
1415  case ISD::AND:
1416    // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
1417    // worth handling here.
1418    if (N2C && N2C->getValue() == 0)
1419      return N2;
1420    break;
1421  case ISD::OR:
1422  case ISD::XOR:
1423    // (X ^| 0) -> X.  This commonly occurs when legalizing i64 values, so it's
1424    // worth handling here.
1425    if (N2C && N2C->getValue() == 0)
1426      return N1;
1427    break;
1428  case ISD::FP_ROUND_INREG:
1429    if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
1430    break;
1431  case ISD::SIGN_EXTEND_INREG: {
1432    MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1433    if (EVT == VT) return N1;  // Not actually extending
1434    break;
1435  }
1436  case ISD::EXTRACT_ELEMENT:
1437    assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!");
1438
1439    // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
1440    // 64-bit integers into 32-bit parts.  Instead of building the extract of
1441    // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
1442    if (N1.getOpcode() == ISD::BUILD_PAIR)
1443      return N1.getOperand(N2C->getValue());
1444
1445    // EXTRACT_ELEMENT of a constant int is also very common.
1446    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
1447      unsigned Shift = MVT::getSizeInBits(VT) * N2C->getValue();
1448      return getConstant(C->getValue() >> Shift, VT);
1449    }
1450    break;
1451
1452  // FIXME: figure out how to safely handle things like
1453  // int foo(int x) { return 1 << (x & 255); }
1454  // int bar() { return foo(256); }
1455#if 0
1456  case ISD::SHL:
1457  case ISD::SRL:
1458  case ISD::SRA:
1459    if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1460        cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1)
1461      return getNode(Opcode, VT, N1, N2.getOperand(0));
1462    else if (N2.getOpcode() == ISD::AND)
1463      if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) {
1464        // If the and is only masking out bits that cannot effect the shift,
1465        // eliminate the and.
1466        unsigned NumBits = MVT::getSizeInBits(VT);
1467        if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1468          return getNode(Opcode, VT, N1, N2.getOperand(0));
1469      }
1470    break;
1471#endif
1472  }
1473
1474  // Memoize this node if possible.
1475  SDNode *N;
1476  SDVTList VTs = getVTList(VT);
1477  if (VT != MVT::Flag) {
1478    FoldingSetNodeID ID;
1479    AddNodeIDNode(ID, Opcode, VTs, N1, N2);
1480    void *IP = 0;
1481    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1482      return SDOperand(E, 0);
1483    N = new SDNode(Opcode, N1, N2);
1484    N->setValueTypes(VTs);
1485    CSEMap.InsertNode(N, IP);
1486  } else {
1487    N = new SDNode(Opcode, N1, N2);
1488    N->setValueTypes(VTs);
1489  }
1490
1491  AllNodes.push_back(N);
1492  return SDOperand(N, 0);
1493}
1494
1495SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1496                                SDOperand N1, SDOperand N2, SDOperand N3) {
1497  // Perform various simplifications.
1498  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1499  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1500  //ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
1501  switch (Opcode) {
1502  case ISD::SETCC: {
1503    // Use FoldSetCC to simplify SETCC's.
1504    SDOperand Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
1505    if (Simp.Val) return Simp;
1506    break;
1507  }
1508  case ISD::SELECT:
1509    if (N1C)
1510      if (N1C->getValue())
1511        return N2;             // select true, X, Y -> X
1512      else
1513        return N3;             // select false, X, Y -> Y
1514
1515    if (N2 == N3) return N2;   // select C, X, X -> X
1516    break;
1517  case ISD::BRCOND:
1518    if (N2C)
1519      if (N2C->getValue()) // Unconditional branch
1520        return getNode(ISD::BR, MVT::Other, N1, N3);
1521      else
1522        return N1;         // Never-taken branch
1523    break;
1524  case ISD::VECTOR_SHUFFLE:
1525    assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1526           MVT::isVector(VT) && MVT::isVector(N3.getValueType()) &&
1527           N3.getOpcode() == ISD::BUILD_VECTOR &&
1528           MVT::getVectorNumElements(VT) == N3.getNumOperands() &&
1529           "Illegal VECTOR_SHUFFLE node!");
1530    break;
1531  }
1532
1533  // Memoize node if it doesn't produce a flag.
1534  SDNode *N;
1535  SDVTList VTs = getVTList(VT);
1536  if (VT != MVT::Flag) {
1537    FoldingSetNodeID ID;
1538    AddNodeIDNode(ID, Opcode, VTs, N1, N2, N3);
1539    void *IP = 0;
1540    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1541      return SDOperand(E, 0);
1542    N = new SDNode(Opcode, N1, N2, N3);
1543    N->setValueTypes(VTs);
1544    CSEMap.InsertNode(N, IP);
1545  } else {
1546    N = new SDNode(Opcode, N1, N2, N3);
1547    N->setValueTypes(VTs);
1548  }
1549  AllNodes.push_back(N);
1550  return SDOperand(N, 0);
1551}
1552
1553SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1554                                SDOperand N1, SDOperand N2, SDOperand N3,
1555                                SDOperand N4) {
1556  SDOperand Ops[] = { N1, N2, N3, N4 };
1557  return getNode(Opcode, VT, Ops, 4);
1558}
1559
1560SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1561                                SDOperand N1, SDOperand N2, SDOperand N3,
1562                                SDOperand N4, SDOperand N5) {
1563  SDOperand Ops[] = { N1, N2, N3, N4, N5 };
1564  return getNode(Opcode, VT, Ops, 5);
1565}
1566
1567SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
1568                                SDOperand Chain, SDOperand Ptr,
1569                                const Value *SV, int SVOffset,
1570                                bool isVolatile) {
1571  // FIXME: Alignment == 1 for now.
1572  unsigned Alignment = 1;
1573  SDVTList VTs = getVTList(VT, MVT::Other);
1574  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
1575  FoldingSetNodeID ID;
1576  AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef);
1577  ID.AddInteger(ISD::UNINDEXED);
1578  ID.AddInteger(ISD::NON_EXTLOAD);
1579  ID.AddInteger(VT);
1580  ID.AddPointer(SV);
1581  ID.AddInteger(SVOffset);
1582  ID.AddInteger(Alignment);
1583  ID.AddInteger(isVolatile);
1584  void *IP = 0;
1585  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1586    return SDOperand(E, 0);
1587  SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ISD::UNINDEXED,
1588                             ISD::NON_EXTLOAD, VT, SV, SVOffset, Alignment,
1589                             isVolatile);
1590  N->setValueTypes(VTs);
1591  CSEMap.InsertNode(N, IP);
1592  AllNodes.push_back(N);
1593  return SDOperand(N, 0);
1594}
1595
1596SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT,
1597                                   SDOperand Chain, SDOperand Ptr, const Value *SV,
1598                                   int SVOffset, MVT::ValueType EVT,
1599                                   bool isVolatile) {
1600  // If they are asking for an extending load from/to the same thing, return a
1601  // normal load.
1602  if (VT == EVT)
1603    ExtType = ISD::NON_EXTLOAD;
1604
1605  if (MVT::isVector(VT))
1606    assert(EVT == MVT::getVectorBaseType(VT) && "Invalid vector extload!");
1607  else
1608    assert(EVT < VT && "Should only be an extending load, not truncating!");
1609  assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) &&
1610         "Cannot sign/zero extend a FP/Vector load!");
1611  assert(MVT::isInteger(VT) == MVT::isInteger(EVT) &&
1612         "Cannot convert from FP to Int or Int -> FP!");
1613
1614  // FIXME: Alignment == 1 for now.
1615  unsigned Alignment = 1;
1616  SDVTList VTs = getVTList(VT, MVT::Other);
1617  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
1618  FoldingSetNodeID ID;
1619  AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef);
1620  ID.AddInteger(ISD::UNINDEXED);
1621  ID.AddInteger(ExtType);
1622  ID.AddInteger(EVT);
1623  ID.AddPointer(SV);
1624  ID.AddInteger(SVOffset);
1625  ID.AddInteger(Alignment);
1626  ID.AddInteger(isVolatile);
1627  void *IP = 0;
1628  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1629    return SDOperand(E, 0);
1630  SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ISD::UNINDEXED, ExtType, EVT,
1631                             SV, SVOffset, Alignment, isVolatile);
1632  N->setValueTypes(VTs);
1633  CSEMap.InsertNode(N, IP);
1634  AllNodes.push_back(N);
1635  return SDOperand(N, 0);
1636}
1637
1638SDOperand SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base,
1639                                       SDOperand Offset, ISD::MemOpAddrMode AM){
1640  LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
1641  assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
1642         "Load is already a indexed load!");
1643  MVT::ValueType VT = OrigLoad.getValueType();
1644  SDVTList VTs = getVTList(VT, Base.getValueType(), MVT::Other);
1645  FoldingSetNodeID ID;
1646  AddNodeIDNode(ID, ISD::LOAD, VTs, LD->getChain(), Base, Offset);
1647  ID.AddInteger(AM);
1648  ID.AddInteger(LD->getExtensionType());
1649  ID.AddInteger(LD->getLoadedVT());
1650  ID.AddPointer(LD->getSrcValue());
1651  ID.AddInteger(LD->getSrcValueOffset());
1652  ID.AddInteger(LD->getAlignment());
1653  ID.AddInteger(LD->isVolatile());
1654  void *IP = 0;
1655  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1656    return SDOperand(E, 0);
1657  SDNode *N = new LoadSDNode(LD->getChain(), Base, Offset, AM,
1658                             LD->getExtensionType(), LD->getLoadedVT(),
1659                             LD->getSrcValue(), LD->getSrcValueOffset(),
1660                             LD->getAlignment(), LD->isVolatile());
1661  N->setValueTypes(VTs);
1662  CSEMap.InsertNode(N, IP);
1663  AllNodes.push_back(N);
1664  return SDOperand(N, 0);
1665}
1666
1667SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT,
1668                                   SDOperand Chain, SDOperand Ptr,
1669                                   SDOperand SV) {
1670  SDOperand Ops[] = { Chain, Ptr, SV, getConstant(Count, MVT::i32),
1671                      getValueType(EVT) };
1672  return getNode(ISD::VLOAD, getVTList(MVT::Vector, MVT::Other), Ops, 5);
1673}
1674
1675SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Value,
1676                                 SDOperand Ptr, const Value *SV, int SVOffset,
1677                                 bool isVolatile) {
1678  MVT::ValueType VT = Value.getValueType();
1679
1680  // FIXME: Alignment == 1 for now.
1681  unsigned Alignment = 1;
1682  SDVTList VTs = getVTList(MVT::Other);
1683  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
1684  SDOperand Ops[] = { Chain, Value, Ptr, Undef };
1685  FoldingSetNodeID ID;
1686  AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
1687  ID.AddInteger(ISD::UNINDEXED);
1688  ID.AddInteger(false);
1689  ID.AddInteger(VT);
1690  ID.AddPointer(SV);
1691  ID.AddInteger(SVOffset);
1692  ID.AddInteger(Alignment);
1693  ID.AddInteger(isVolatile);
1694  void *IP = 0;
1695  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1696    return SDOperand(E, 0);
1697  SDNode *N = new StoreSDNode(Chain, Value, Ptr, Undef, ISD::UNINDEXED, false,
1698                              VT, SV, SVOffset, Alignment, isVolatile);
1699  N->setValueTypes(VTs);
1700  CSEMap.InsertNode(N, IP);
1701  AllNodes.push_back(N);
1702  return SDOperand(N, 0);
1703}
1704
1705SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Value,
1706                                      SDOperand Ptr, const Value *SV,
1707                                      int SVOffset, MVT::ValueType SVT,
1708                                      bool isVolatile) {
1709  MVT::ValueType VT = Value.getValueType();
1710  bool isTrunc = VT != SVT;
1711
1712  assert(VT > SVT && "Not a truncation?");
1713  assert(MVT::isInteger(VT) == MVT::isInteger(SVT) &&
1714         "Can't do FP-INT conversion!");
1715
1716  // FIXME: Alignment == 1 for now.
1717  unsigned Alignment = 1;
1718  SDVTList VTs = getVTList(MVT::Other);
1719  SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
1720  SDOperand Ops[] = { Chain, Value, Ptr, Undef };
1721  FoldingSetNodeID ID;
1722  AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
1723  ID.AddInteger(ISD::UNINDEXED);
1724  ID.AddInteger(isTrunc);
1725  ID.AddInteger(SVT);
1726  ID.AddPointer(SV);
1727  ID.AddInteger(SVOffset);
1728  ID.AddInteger(Alignment);
1729  ID.AddInteger(isVolatile);
1730  void *IP = 0;
1731  if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1732    return SDOperand(E, 0);
1733  SDNode *N = new StoreSDNode(Chain, Value, Ptr, Undef, ISD::UNINDEXED, isTrunc,
1734                              SVT, SV, SVOffset, Alignment, isVolatile);
1735  N->setValueTypes(VTs);
1736  CSEMap.InsertNode(N, IP);
1737  AllNodes.push_back(N);
1738  return SDOperand(N, 0);
1739}
1740
1741SDOperand SelectionDAG::getVAArg(MVT::ValueType VT,
1742                                 SDOperand Chain, SDOperand Ptr,
1743                                 SDOperand SV) {
1744  SDOperand Ops[] = { Chain, Ptr, SV };
1745  return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3);
1746}
1747
1748SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1749                                const SDOperand *Ops, unsigned NumOps) {
1750  switch (NumOps) {
1751  case 0: return getNode(Opcode, VT);
1752  case 1: return getNode(Opcode, VT, Ops[0]);
1753  case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
1754  case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
1755  default: break;
1756  }
1757
1758  switch (Opcode) {
1759  default: break;
1760  case ISD::SELECT_CC: {
1761    assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
1762    assert(Ops[0].getValueType() == Ops[1].getValueType() &&
1763           "LHS and RHS of condition must have same type!");
1764    assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1765           "True and False arms of SelectCC must have same type!");
1766    assert(Ops[2].getValueType() == VT &&
1767           "select_cc node must be of same type as true and false value!");
1768    break;
1769  }
1770  case ISD::BR_CC: {
1771    assert(NumOps == 5 && "BR_CC takes 5 operands!");
1772    assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1773           "LHS/RHS of comparison should match types!");
1774    break;
1775  }
1776  }
1777
1778  // Memoize nodes.
1779  SDNode *N;
1780  SDVTList VTs = getVTList(VT);
1781  if (VT != MVT::Flag) {
1782    FoldingSetNodeID ID;
1783    AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
1784    void *IP = 0;
1785    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1786      return SDOperand(E, 0);
1787    N = new SDNode(Opcode, Ops, NumOps);
1788    N->setValueTypes(VTs);
1789    CSEMap.InsertNode(N, IP);
1790  } else {
1791    N = new SDNode(Opcode, Ops, NumOps);
1792    N->setValueTypes(VTs);
1793  }
1794  AllNodes.push_back(N);
1795  return SDOperand(N, 0);
1796}
1797
1798SDOperand SelectionDAG::getNode(unsigned Opcode,
1799                                std::vector<MVT::ValueType> &ResultTys,
1800                                const SDOperand *Ops, unsigned NumOps) {
1801  return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(),
1802                 Ops, NumOps);
1803}
1804
1805SDOperand SelectionDAG::getNode(unsigned Opcode,
1806                                const MVT::ValueType *VTs, unsigned NumVTs,
1807                                const SDOperand *Ops, unsigned NumOps) {
1808  if (NumVTs == 1)
1809    return getNode(Opcode, VTs[0], Ops, NumOps);
1810  return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps);
1811}
1812
1813SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
1814                                const SDOperand *Ops, unsigned NumOps) {
1815  if (VTList.NumVTs == 1)
1816    return getNode(Opcode, VTList.VTs[0], Ops, NumOps);
1817
1818  switch (Opcode) {
1819  // FIXME: figure out how to safely handle things like
1820  // int foo(int x) { return 1 << (x & 255); }
1821  // int bar() { return foo(256); }
1822#if 0
1823  case ISD::SRA_PARTS:
1824  case ISD::SRL_PARTS:
1825  case ISD::SHL_PARTS:
1826    if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1827        cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
1828      return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1829    else if (N3.getOpcode() == ISD::AND)
1830      if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
1831        // If the and is only masking out bits that cannot effect the shift,
1832        // eliminate the and.
1833        unsigned NumBits = MVT::getSizeInBits(VT)*2;
1834        if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1835          return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1836      }
1837    break;
1838#endif
1839  }
1840
1841  // Memoize the node unless it returns a flag.
1842  SDNode *N;
1843  if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
1844    FoldingSetNodeID ID;
1845    AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
1846    void *IP = 0;
1847    if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1848      return SDOperand(E, 0);
1849    N = new SDNode(Opcode, Ops, NumOps);
1850    N->setValueTypes(VTList);
1851    CSEMap.InsertNode(N, IP);
1852  } else {
1853    N = new SDNode(Opcode, Ops, NumOps);
1854    N->setValueTypes(VTList);
1855  }
1856  AllNodes.push_back(N);
1857  return SDOperand(N, 0);
1858}
1859
1860SDVTList SelectionDAG::getVTList(MVT::ValueType VT) {
1861  return makeVTList(SDNode::getValueTypeList(VT), 1);
1862}
1863
1864SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) {
1865  for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1866       E = VTList.end(); I != E; ++I) {
1867    if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
1868      return makeVTList(&(*I)[0], 2);
1869  }
1870  std::vector<MVT::ValueType> V;
1871  V.push_back(VT1);
1872  V.push_back(VT2);
1873  VTList.push_front(V);
1874  return makeVTList(&(*VTList.begin())[0], 2);
1875}
1876SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2,
1877                                 MVT::ValueType VT3) {
1878  for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1879       E = VTList.end(); I != E; ++I) {
1880    if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 &&
1881        (*I)[2] == VT3)
1882      return makeVTList(&(*I)[0], 3);
1883  }
1884  std::vector<MVT::ValueType> V;
1885  V.push_back(VT1);
1886  V.push_back(VT2);
1887  V.push_back(VT3);
1888  VTList.push_front(V);
1889  return makeVTList(&(*VTList.begin())[0], 3);
1890}
1891
1892SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
1893  switch (NumVTs) {
1894    case 0: assert(0 && "Cannot have nodes without results!");
1895    case 1: return makeVTList(SDNode::getValueTypeList(VTs[0]), 1);
1896    case 2: return getVTList(VTs[0], VTs[1]);
1897    case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
1898    default: break;
1899  }
1900
1901  for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1902       E = VTList.end(); I != E; ++I) {
1903    if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue;
1904
1905    bool NoMatch = false;
1906    for (unsigned i = 2; i != NumVTs; ++i)
1907      if (VTs[i] != (*I)[i]) {
1908        NoMatch = true;
1909        break;
1910      }
1911    if (!NoMatch)
1912      return makeVTList(&*I->begin(), NumVTs);
1913  }
1914
1915  VTList.push_front(std::vector<MVT::ValueType>(VTs, VTs+NumVTs));
1916  return makeVTList(&*VTList.begin()->begin(), NumVTs);
1917}
1918
1919
1920/// UpdateNodeOperands - *Mutate* the specified node in-place to have the
1921/// specified operands.  If the resultant node already exists in the DAG,
1922/// this does not modify the specified node, instead it returns the node that
1923/// already exists.  If the resultant node does not exist in the DAG, the
1924/// input node is returned.  As a degenerate case, if you specify the same
1925/// input operands as the node already has, the input node is returned.
1926SDOperand SelectionDAG::
1927UpdateNodeOperands(SDOperand InN, SDOperand Op) {
1928  SDNode *N = InN.Val;
1929  assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
1930
1931  // Check to see if there is no change.
1932  if (Op == N->getOperand(0)) return InN;
1933
1934  // See if the modified node already exists.
1935  void *InsertPos = 0;
1936  if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
1937    return SDOperand(Existing, InN.ResNo);
1938
1939  // Nope it doesn't.  Remove the node from it's current place in the maps.
1940  if (InsertPos)
1941    RemoveNodeFromCSEMaps(N);
1942
1943  // Now we update the operands.
1944  N->OperandList[0].Val->removeUser(N);
1945  Op.Val->addUser(N);
1946  N->OperandList[0] = Op;
1947
1948  // If this gets put into a CSE map, add it.
1949  if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1950  return InN;
1951}
1952
1953SDOperand SelectionDAG::
1954UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
1955  SDNode *N = InN.Val;
1956  assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
1957
1958  // Check to see if there is no change.
1959  bool AnyChange = false;
1960  if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
1961    return InN;   // No operands changed, just return the input node.
1962
1963  // See if the modified node already exists.
1964  void *InsertPos = 0;
1965  if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
1966    return SDOperand(Existing, InN.ResNo);
1967
1968  // Nope it doesn't.  Remove the node from it's current place in the maps.
1969  if (InsertPos)
1970    RemoveNodeFromCSEMaps(N);
1971
1972  // Now we update the operands.
1973  if (N->OperandList[0] != Op1) {
1974    N->OperandList[0].Val->removeUser(N);
1975    Op1.Val->addUser(N);
1976    N->OperandList[0] = Op1;
1977  }
1978  if (N->OperandList[1] != Op2) {
1979    N->OperandList[1].Val->removeUser(N);
1980    Op2.Val->addUser(N);
1981    N->OperandList[1] = Op2;
1982  }
1983
1984  // If this gets put into a CSE map, add it.
1985  if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1986  return InN;
1987}
1988
1989SDOperand SelectionDAG::
1990UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
1991  SDOperand Ops[] = { Op1, Op2, Op3 };
1992  return UpdateNodeOperands(N, Ops, 3);
1993}
1994
1995SDOperand SelectionDAG::
1996UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
1997                   SDOperand Op3, SDOperand Op4) {
1998  SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
1999  return UpdateNodeOperands(N, Ops, 4);
2000}
2001
2002SDOperand SelectionDAG::
2003UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
2004                   SDOperand Op3, SDOperand Op4, SDOperand Op5) {
2005  SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
2006  return UpdateNodeOperands(N, Ops, 5);
2007}
2008
2009
2010SDOperand SelectionDAG::
2011UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
2012  SDNode *N = InN.Val;
2013  assert(N->getNumOperands() == NumOps &&
2014         "Update with wrong number of operands");
2015
2016  // Check to see if there is no change.
2017  bool AnyChange = false;
2018  for (unsigned i = 0; i != NumOps; ++i) {
2019    if (Ops[i] != N->getOperand(i)) {
2020      AnyChange = true;
2021      break;
2022    }
2023  }
2024
2025  // No operands changed, just return the input node.
2026  if (!AnyChange) return InN;
2027
2028  // See if the modified node already exists.
2029  void *InsertPos = 0;
2030  if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
2031    return SDOperand(Existing, InN.ResNo);
2032
2033  // Nope it doesn't.  Remove the node from it's current place in the maps.
2034  if (InsertPos)
2035    RemoveNodeFromCSEMaps(N);
2036
2037  // Now we update the operands.
2038  for (unsigned i = 0; i != NumOps; ++i) {
2039    if (N->OperandList[i] != Ops[i]) {
2040      N->OperandList[i].Val->removeUser(N);
2041      Ops[i].Val->addUser(N);
2042      N->OperandList[i] = Ops[i];
2043    }
2044  }
2045
2046  // If this gets put into a CSE map, add it.
2047  if (InsertPos) CSEMap.InsertNode(N, InsertPos);
2048  return InN;
2049}
2050
2051
2052
2053
2054/// SelectNodeTo - These are used for target selectors to *mutate* the
2055/// specified node to have the specified return type, Target opcode, and
2056/// operands.  Note that target opcodes are stored as
2057/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
2058///
2059/// Note that SelectNodeTo returns the resultant node.  If there is already a
2060/// node of the specified opcode and operands, it returns that node instead of
2061/// the current one.
2062SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2063                                   MVT::ValueType VT) {
2064  SDVTList VTs = getVTList(VT);
2065  FoldingSetNodeID ID;
2066  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs);
2067  void *IP = 0;
2068  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2069    return ON;
2070
2071  RemoveNodeFromCSEMaps(N);
2072
2073  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2074  N->setValueTypes(VTs);
2075
2076  CSEMap.InsertNode(N, IP);
2077  return N;
2078}
2079
2080SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2081                                   MVT::ValueType VT, SDOperand Op1) {
2082  // If an identical node already exists, use it.
2083  SDVTList VTs = getVTList(VT);
2084  FoldingSetNodeID ID;
2085  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1);
2086  void *IP = 0;
2087  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2088    return ON;
2089
2090  RemoveNodeFromCSEMaps(N);
2091  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2092  N->setValueTypes(VTs);
2093  N->setOperands(Op1);
2094  CSEMap.InsertNode(N, IP);
2095  return N;
2096}
2097
2098SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2099                                   MVT::ValueType VT, SDOperand Op1,
2100                                   SDOperand Op2) {
2101  // If an identical node already exists, use it.
2102  SDVTList VTs = getVTList(VT);
2103  FoldingSetNodeID ID;
2104  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs,  Op1, Op2);
2105  void *IP = 0;
2106  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2107    return ON;
2108
2109  RemoveNodeFromCSEMaps(N);
2110  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2111  N->setValueTypes(VTs);
2112  N->setOperands(Op1, Op2);
2113
2114  CSEMap.InsertNode(N, IP);   // Memoize the new node.
2115  return N;
2116}
2117
2118SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2119                                   MVT::ValueType VT, SDOperand Op1,
2120                                   SDOperand Op2, SDOperand Op3) {
2121  // If an identical node already exists, use it.
2122  SDVTList VTs = getVTList(VT);
2123  FoldingSetNodeID ID;
2124  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs,  Op1, Op2, Op3);
2125  void *IP = 0;
2126  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2127    return ON;
2128
2129  RemoveNodeFromCSEMaps(N);
2130  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2131  N->setValueTypes(VTs);
2132  N->setOperands(Op1, Op2, Op3);
2133
2134  CSEMap.InsertNode(N, IP);   // Memoize the new node.
2135  return N;
2136}
2137
2138SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2139                                   MVT::ValueType VT, const SDOperand *Ops,
2140                                   unsigned NumOps) {
2141  // If an identical node already exists, use it.
2142  SDVTList VTs = getVTList(VT);
2143  FoldingSetNodeID ID;
2144  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
2145  void *IP = 0;
2146  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2147    return ON;
2148
2149  RemoveNodeFromCSEMaps(N);
2150  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2151  N->setValueTypes(VTs);
2152  N->setOperands(Ops, NumOps);
2153
2154  CSEMap.InsertNode(N, IP);   // Memoize the new node.
2155  return N;
2156}
2157
2158SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2159                                   MVT::ValueType VT1, MVT::ValueType VT2,
2160                                   SDOperand Op1, SDOperand Op2) {
2161  SDVTList VTs = getVTList(VT1, VT2);
2162  FoldingSetNodeID ID;
2163  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
2164  void *IP = 0;
2165  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2166    return ON;
2167
2168  RemoveNodeFromCSEMaps(N);
2169  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2170  N->setValueTypes(VTs);
2171  N->setOperands(Op1, Op2);
2172
2173  CSEMap.InsertNode(N, IP);   // Memoize the new node.
2174  return N;
2175}
2176
2177SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2178                                   MVT::ValueType VT1, MVT::ValueType VT2,
2179                                   SDOperand Op1, SDOperand Op2,
2180                                   SDOperand Op3) {
2181  // If an identical node already exists, use it.
2182  SDVTList VTs = getVTList(VT1, VT2);
2183  FoldingSetNodeID ID;
2184  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2, Op3);
2185  void *IP = 0;
2186  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2187    return ON;
2188
2189  RemoveNodeFromCSEMaps(N);
2190  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2191  N->setValueTypes(VTs);
2192  N->setOperands(Op1, Op2, Op3);
2193
2194  CSEMap.InsertNode(N, IP);   // Memoize the new node.
2195  return N;
2196}
2197
2198
2199/// getTargetNode - These are used for target selectors to create a new node
2200/// with specified return type(s), target opcode, and operands.
2201///
2202/// Note that getTargetNode returns the resultant node.  If there is already a
2203/// node of the specified opcode and operands, it returns that node instead of
2204/// the current one.
2205SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) {
2206  return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
2207}
2208SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2209                                    SDOperand Op1) {
2210  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
2211}
2212SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2213                                    SDOperand Op1, SDOperand Op2) {
2214  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
2215}
2216SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2217                                    SDOperand Op1, SDOperand Op2, SDOperand Op3) {
2218  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
2219}
2220SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2221                                    const SDOperand *Ops, unsigned NumOps) {
2222  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
2223}
2224SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2225                                    MVT::ValueType VT2, SDOperand Op1) {
2226  const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2227  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val;
2228}
2229SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2230                                    MVT::ValueType VT2, SDOperand Op1,
2231                                    SDOperand Op2) {
2232  const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2233  SDOperand Ops[] = { Op1, Op2 };
2234  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val;
2235}
2236SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2237                                    MVT::ValueType VT2, SDOperand Op1,
2238                                    SDOperand Op2, SDOperand Op3) {
2239  const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2240  SDOperand Ops[] = { Op1, Op2, Op3 };
2241  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
2242}
2243SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2244                                    MVT::ValueType VT2,
2245                                    const SDOperand *Ops, unsigned NumOps) {
2246  const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2247  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
2248}
2249SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2250                                    MVT::ValueType VT2, MVT::ValueType VT3,
2251                                    SDOperand Op1, SDOperand Op2) {
2252  const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
2253  SDOperand Ops[] = { Op1, Op2 };
2254  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val;
2255}
2256SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2257                                    MVT::ValueType VT2, MVT::ValueType VT3,
2258                                    const SDOperand *Ops, unsigned NumOps) {
2259  const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
2260  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val;
2261}
2262
2263/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2264/// This can cause recursive merging of nodes in the DAG.
2265///
2266/// This version assumes From/To have a single result value.
2267///
2268void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN,
2269                                      std::vector<SDNode*> *Deleted) {
2270  SDNode *From = FromN.Val, *To = ToN.Val;
2271  assert(From->getNumValues() == 1 && To->getNumValues() == 1 &&
2272         "Cannot replace with this method!");
2273  assert(From != To && "Cannot replace uses of with self");
2274
2275  while (!From->use_empty()) {
2276    // Process users until they are all gone.
2277    SDNode *U = *From->use_begin();
2278
2279    // This node is about to morph, remove its old self from the CSE maps.
2280    RemoveNodeFromCSEMaps(U);
2281
2282    for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2283         I != E; ++I)
2284      if (I->Val == From) {
2285        From->removeUser(U);
2286        I->Val = To;
2287        To->addUser(U);
2288      }
2289
2290    // Now that we have modified U, add it back to the CSE maps.  If it already
2291    // exists there, recursively merge the results together.
2292    if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2293      ReplaceAllUsesWith(U, Existing, Deleted);
2294      // U is now dead.
2295      if (Deleted) Deleted->push_back(U);
2296      DeleteNodeNotInCSEMaps(U);
2297    }
2298  }
2299}
2300
2301/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2302/// This can cause recursive merging of nodes in the DAG.
2303///
2304/// This version assumes From/To have matching types and numbers of result
2305/// values.
2306///
2307void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
2308                                      std::vector<SDNode*> *Deleted) {
2309  assert(From != To && "Cannot replace uses of with self");
2310  assert(From->getNumValues() == To->getNumValues() &&
2311         "Cannot use this version of ReplaceAllUsesWith!");
2312  if (From->getNumValues() == 1) {  // If possible, use the faster version.
2313    ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted);
2314    return;
2315  }
2316
2317  while (!From->use_empty()) {
2318    // Process users until they are all gone.
2319    SDNode *U = *From->use_begin();
2320
2321    // This node is about to morph, remove its old self from the CSE maps.
2322    RemoveNodeFromCSEMaps(U);
2323
2324    for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2325         I != E; ++I)
2326      if (I->Val == From) {
2327        From->removeUser(U);
2328        I->Val = To;
2329        To->addUser(U);
2330      }
2331
2332    // Now that we have modified U, add it back to the CSE maps.  If it already
2333    // exists there, recursively merge the results together.
2334    if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2335      ReplaceAllUsesWith(U, Existing, Deleted);
2336      // U is now dead.
2337      if (Deleted) Deleted->push_back(U);
2338      DeleteNodeNotInCSEMaps(U);
2339    }
2340  }
2341}
2342
2343/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2344/// This can cause recursive merging of nodes in the DAG.
2345///
2346/// This version can replace From with any result values.  To must match the
2347/// number and types of values returned by From.
2348void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
2349                                      const SDOperand *To,
2350                                      std::vector<SDNode*> *Deleted) {
2351  if (From->getNumValues() == 1 && To[0].Val->getNumValues() == 1) {
2352    // Degenerate case handled above.
2353    ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted);
2354    return;
2355  }
2356
2357  while (!From->use_empty()) {
2358    // Process users until they are all gone.
2359    SDNode *U = *From->use_begin();
2360
2361    // This node is about to morph, remove its old self from the CSE maps.
2362    RemoveNodeFromCSEMaps(U);
2363
2364    for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2365         I != E; ++I)
2366      if (I->Val == From) {
2367        const SDOperand &ToOp = To[I->ResNo];
2368        From->removeUser(U);
2369        *I = ToOp;
2370        ToOp.Val->addUser(U);
2371      }
2372
2373    // Now that we have modified U, add it back to the CSE maps.  If it already
2374    // exists there, recursively merge the results together.
2375    if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2376      ReplaceAllUsesWith(U, Existing, Deleted);
2377      // U is now dead.
2378      if (Deleted) Deleted->push_back(U);
2379      DeleteNodeNotInCSEMaps(U);
2380    }
2381  }
2382}
2383
2384/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
2385/// uses of other values produced by From.Val alone.  The Deleted vector is
2386/// handled the same was as for ReplaceAllUsesWith.
2387void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
2388                                             std::vector<SDNode*> &Deleted) {
2389  assert(From != To && "Cannot replace a value with itself");
2390  // Handle the simple, trivial, case efficiently.
2391  if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) {
2392    ReplaceAllUsesWith(From, To, &Deleted);
2393    return;
2394  }
2395
2396  // Get all of the users in a nice, deterministically ordered, uniqued set.
2397  SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end());
2398
2399  while (!Users.empty()) {
2400    // We know that this user uses some value of From.  If it is the right
2401    // value, update it.
2402    SDNode *User = Users.back();
2403    Users.pop_back();
2404
2405    for (SDOperand *Op = User->OperandList,
2406         *E = User->OperandList+User->NumOperands; Op != E; ++Op) {
2407      if (*Op == From) {
2408        // Okay, we know this user needs to be updated.  Remove its old self
2409        // from the CSE maps.
2410        RemoveNodeFromCSEMaps(User);
2411
2412        // Update all operands that match "From".
2413        for (; Op != E; ++Op) {
2414          if (*Op == From) {
2415            From.Val->removeUser(User);
2416            *Op = To;
2417            To.Val->addUser(User);
2418          }
2419        }
2420
2421        // Now that we have modified User, add it back to the CSE maps.  If it
2422        // already exists there, recursively merge the results together.
2423        if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) {
2424          unsigned NumDeleted = Deleted.size();
2425          ReplaceAllUsesWith(User, Existing, &Deleted);
2426
2427          // User is now dead.
2428          Deleted.push_back(User);
2429          DeleteNodeNotInCSEMaps(User);
2430
2431          // We have to be careful here, because ReplaceAllUsesWith could have
2432          // deleted a user of From, which means there may be dangling pointers
2433          // in the "Users" setvector.  Scan over the deleted node pointers and
2434          // remove them from the setvector.
2435          for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i)
2436            Users.remove(Deleted[i]);
2437        }
2438        break;   // Exit the operand scanning loop.
2439      }
2440    }
2441  }
2442}
2443
2444
2445/// AssignNodeIds - Assign a unique node id for each node in the DAG based on
2446/// their allnodes order. It returns the maximum id.
2447unsigned SelectionDAG::AssignNodeIds() {
2448  unsigned Id = 0;
2449  for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
2450    SDNode *N = I;
2451    N->setNodeId(Id++);
2452  }
2453  return Id;
2454}
2455
2456/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
2457/// based on their topological order. It returns the maximum id and a vector
2458/// of the SDNodes* in assigned order by reference.
2459unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
2460  unsigned DAGSize = AllNodes.size();
2461  std::vector<unsigned> InDegree(DAGSize);
2462  std::vector<SDNode*> Sources;
2463
2464  // Use a two pass approach to avoid using a std::map which is slow.
2465  unsigned Id = 0;
2466  for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
2467    SDNode *N = I;
2468    N->setNodeId(Id++);
2469    unsigned Degree = N->use_size();
2470    InDegree[N->getNodeId()] = Degree;
2471    if (Degree == 0)
2472      Sources.push_back(N);
2473  }
2474
2475  TopOrder.clear();
2476  while (!Sources.empty()) {
2477    SDNode *N = Sources.back();
2478    Sources.pop_back();
2479    TopOrder.push_back(N);
2480    for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
2481      SDNode *P = I->Val;
2482      unsigned Degree = --InDegree[P->getNodeId()];
2483      if (Degree == 0)
2484        Sources.push_back(P);
2485    }
2486  }
2487
2488  // Second pass, assign the actual topological order as node ids.
2489  Id = 0;
2490  for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
2491       TI != TE; ++TI)
2492    (*TI)->setNodeId(Id++);
2493
2494  return Id;
2495}
2496
2497
2498
2499//===----------------------------------------------------------------------===//
2500//                              SDNode Class
2501//===----------------------------------------------------------------------===//
2502
2503// Out-of-line virtual method to give class a home.
2504void SDNode::ANCHOR() {
2505}
2506
2507/// Profile - Gather unique data for the node.
2508///
2509void SDNode::Profile(FoldingSetNodeID &ID) {
2510  AddNodeIDNode(ID, this);
2511}
2512
2513/// getValueTypeList - Return a pointer to the specified value type.
2514///
2515MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
2516  static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
2517  VTs[VT] = VT;
2518  return &VTs[VT];
2519}
2520
2521/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
2522/// indicated value.  This method ignores uses of other values defined by this
2523/// operation.
2524bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
2525  assert(Value < getNumValues() && "Bad value!");
2526
2527  // If there is only one value, this is easy.
2528  if (getNumValues() == 1)
2529    return use_size() == NUses;
2530  if (Uses.size() < NUses) return false;
2531
2532  SDOperand TheValue(const_cast<SDNode *>(this), Value);
2533
2534  std::set<SDNode*> UsersHandled;
2535
2536  for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) {
2537    SDNode *User = *UI;
2538    if (User->getNumOperands() == 1 ||
2539        UsersHandled.insert(User).second)     // First time we've seen this?
2540      for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
2541        if (User->getOperand(i) == TheValue) {
2542          if (NUses == 0)
2543            return false;   // too many uses
2544          --NUses;
2545        }
2546  }
2547
2548  // Found exactly the right number of uses?
2549  return NUses == 0;
2550}
2551
2552
2553// isOnlyUse - Return true if this node is the only use of N.
2554bool SDNode::isOnlyUse(SDNode *N) const {
2555  bool Seen = false;
2556  for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2557    SDNode *User = *I;
2558    if (User == this)
2559      Seen = true;
2560    else
2561      return false;
2562  }
2563
2564  return Seen;
2565}
2566
2567// isOperand - Return true if this node is an operand of N.
2568bool SDOperand::isOperand(SDNode *N) const {
2569  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
2570    if (*this == N->getOperand(i))
2571      return true;
2572  return false;
2573}
2574
2575bool SDNode::isOperand(SDNode *N) const {
2576  for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
2577    if (this == N->OperandList[i].Val)
2578      return true;
2579  return false;
2580}
2581
2582uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
2583  assert(Num < NumOperands && "Invalid child # of SDNode!");
2584  return cast<ConstantSDNode>(OperandList[Num])->getValue();
2585}
2586
2587const char *SDNode::getOperationName(const SelectionDAG *G) const {
2588  switch (getOpcode()) {
2589  default:
2590    if (getOpcode() < ISD::BUILTIN_OP_END)
2591      return "<<Unknown DAG Node>>";
2592    else {
2593      if (G) {
2594        if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
2595          if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
2596            return TII->getName(getOpcode()-ISD::BUILTIN_OP_END);
2597
2598        TargetLowering &TLI = G->getTargetLoweringInfo();
2599        const char *Name =
2600          TLI.getTargetNodeName(getOpcode());
2601        if (Name) return Name;
2602      }
2603
2604      return "<<Unknown Target Node>>";
2605    }
2606
2607  case ISD::PCMARKER:      return "PCMarker";
2608  case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
2609  case ISD::SRCVALUE:      return "SrcValue";
2610  case ISD::EntryToken:    return "EntryToken";
2611  case ISD::TokenFactor:   return "TokenFactor";
2612  case ISD::AssertSext:    return "AssertSext";
2613  case ISD::AssertZext:    return "AssertZext";
2614
2615  case ISD::STRING:        return "String";
2616  case ISD::BasicBlock:    return "BasicBlock";
2617  case ISD::VALUETYPE:     return "ValueType";
2618  case ISD::Register:      return "Register";
2619
2620  case ISD::Constant:      return "Constant";
2621  case ISD::ConstantFP:    return "ConstantFP";
2622  case ISD::GlobalAddress: return "GlobalAddress";
2623  case ISD::FrameIndex:    return "FrameIndex";
2624  case ISD::JumpTable:     return "JumpTable";
2625  case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE";
2626  case ISD::ConstantPool:  return "ConstantPool";
2627  case ISD::ExternalSymbol: return "ExternalSymbol";
2628  case ISD::INTRINSIC_WO_CHAIN: {
2629    unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
2630    return Intrinsic::getName((Intrinsic::ID)IID);
2631  }
2632  case ISD::INTRINSIC_VOID:
2633  case ISD::INTRINSIC_W_CHAIN: {
2634    unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
2635    return Intrinsic::getName((Intrinsic::ID)IID);
2636  }
2637
2638  case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
2639  case ISD::TargetConstant: return "TargetConstant";
2640  case ISD::TargetConstantFP:return "TargetConstantFP";
2641  case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
2642  case ISD::TargetFrameIndex: return "TargetFrameIndex";
2643  case ISD::TargetJumpTable:  return "TargetJumpTable";
2644  case ISD::TargetConstantPool:  return "TargetConstantPool";
2645  case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
2646
2647  case ISD::CopyToReg:     return "CopyToReg";
2648  case ISD::CopyFromReg:   return "CopyFromReg";
2649  case ISD::UNDEF:         return "undef";
2650  case ISD::MERGE_VALUES:  return "mergevalues";
2651  case ISD::INLINEASM:     return "inlineasm";
2652  case ISD::HANDLENODE:    return "handlenode";
2653  case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
2654  case ISD::CALL:          return "call";
2655
2656  // Unary operators
2657  case ISD::FABS:   return "fabs";
2658  case ISD::FNEG:   return "fneg";
2659  case ISD::FSQRT:  return "fsqrt";
2660  case ISD::FSIN:   return "fsin";
2661  case ISD::FCOS:   return "fcos";
2662  case ISD::FPOWI:  return "fpowi";
2663
2664  // Binary operators
2665  case ISD::ADD:    return "add";
2666  case ISD::SUB:    return "sub";
2667  case ISD::MUL:    return "mul";
2668  case ISD::MULHU:  return "mulhu";
2669  case ISD::MULHS:  return "mulhs";
2670  case ISD::SDIV:   return "sdiv";
2671  case ISD::UDIV:   return "udiv";
2672  case ISD::SREM:   return "srem";
2673  case ISD::UREM:   return "urem";
2674  case ISD::AND:    return "and";
2675  case ISD::OR:     return "or";
2676  case ISD::XOR:    return "xor";
2677  case ISD::SHL:    return "shl";
2678  case ISD::SRA:    return "sra";
2679  case ISD::SRL:    return "srl";
2680  case ISD::ROTL:   return "rotl";
2681  case ISD::ROTR:   return "rotr";
2682  case ISD::FADD:   return "fadd";
2683  case ISD::FSUB:   return "fsub";
2684  case ISD::FMUL:   return "fmul";
2685  case ISD::FDIV:   return "fdiv";
2686  case ISD::FREM:   return "frem";
2687  case ISD::FCOPYSIGN: return "fcopysign";
2688  case ISD::VADD:   return "vadd";
2689  case ISD::VSUB:   return "vsub";
2690  case ISD::VMUL:   return "vmul";
2691  case ISD::VSDIV:  return "vsdiv";
2692  case ISD::VUDIV:  return "vudiv";
2693  case ISD::VAND:   return "vand";
2694  case ISD::VOR:    return "vor";
2695  case ISD::VXOR:   return "vxor";
2696
2697  case ISD::SETCC:       return "setcc";
2698  case ISD::SELECT:      return "select";
2699  case ISD::SELECT_CC:   return "select_cc";
2700  case ISD::VSELECT:     return "vselect";
2701  case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
2702  case ISD::VINSERT_VECTOR_ELT:  return "vinsert_vector_elt";
2703  case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
2704  case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt";
2705  case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
2706  case ISD::VBUILD_VECTOR:       return "vbuild_vector";
2707  case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
2708  case ISD::VVECTOR_SHUFFLE:     return "vvector_shuffle";
2709  case ISD::VBIT_CONVERT:        return "vbit_convert";
2710  case ISD::ADDC:        return "addc";
2711  case ISD::ADDE:        return "adde";
2712  case ISD::SUBC:        return "subc";
2713  case ISD::SUBE:        return "sube";
2714  case ISD::SHL_PARTS:   return "shl_parts";
2715  case ISD::SRA_PARTS:   return "sra_parts";
2716  case ISD::SRL_PARTS:   return "srl_parts";
2717
2718  // Conversion operators.
2719  case ISD::SIGN_EXTEND: return "sign_extend";
2720  case ISD::ZERO_EXTEND: return "zero_extend";
2721  case ISD::ANY_EXTEND:  return "any_extend";
2722  case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
2723  case ISD::TRUNCATE:    return "truncate";
2724  case ISD::FP_ROUND:    return "fp_round";
2725  case ISD::FP_ROUND_INREG: return "fp_round_inreg";
2726  case ISD::FP_EXTEND:   return "fp_extend";
2727
2728  case ISD::SINT_TO_FP:  return "sint_to_fp";
2729  case ISD::UINT_TO_FP:  return "uint_to_fp";
2730  case ISD::FP_TO_SINT:  return "fp_to_sint";
2731  case ISD::FP_TO_UINT:  return "fp_to_uint";
2732  case ISD::BIT_CONVERT: return "bit_convert";
2733
2734    // Control flow instructions
2735  case ISD::BR:      return "br";
2736  case ISD::BRIND:   return "brind";
2737  case ISD::BRCOND:  return "brcond";
2738  case ISD::BR_CC:   return "br_cc";
2739  case ISD::RET:     return "ret";
2740  case ISD::CALLSEQ_START:  return "callseq_start";
2741  case ISD::CALLSEQ_END:    return "callseq_end";
2742
2743    // Other operators
2744  case ISD::LOAD:               return "load";
2745  case ISD::STORE:              return "store";
2746  case ISD::VLOAD:              return "vload";
2747  case ISD::VAARG:              return "vaarg";
2748  case ISD::VACOPY:             return "vacopy";
2749  case ISD::VAEND:              return "vaend";
2750  case ISD::VASTART:            return "vastart";
2751  case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
2752  case ISD::EXTRACT_ELEMENT:    return "extract_element";
2753  case ISD::BUILD_PAIR:         return "build_pair";
2754  case ISD::STACKSAVE:          return "stacksave";
2755  case ISD::STACKRESTORE:       return "stackrestore";
2756
2757  // Block memory operations.
2758  case ISD::MEMSET:  return "memset";
2759  case ISD::MEMCPY:  return "memcpy";
2760  case ISD::MEMMOVE: return "memmove";
2761
2762  // Bit manipulation
2763  case ISD::BSWAP:   return "bswap";
2764  case ISD::CTPOP:   return "ctpop";
2765  case ISD::CTTZ:    return "cttz";
2766  case ISD::CTLZ:    return "ctlz";
2767
2768  // Debug info
2769  case ISD::LOCATION: return "location";
2770  case ISD::DEBUG_LOC: return "debug_loc";
2771  case ISD::DEBUG_LABEL: return "debug_label";
2772
2773  case ISD::CONDCODE:
2774    switch (cast<CondCodeSDNode>(this)->get()) {
2775    default: assert(0 && "Unknown setcc condition!");
2776    case ISD::SETOEQ:  return "setoeq";
2777    case ISD::SETOGT:  return "setogt";
2778    case ISD::SETOGE:  return "setoge";
2779    case ISD::SETOLT:  return "setolt";
2780    case ISD::SETOLE:  return "setole";
2781    case ISD::SETONE:  return "setone";
2782
2783    case ISD::SETO:    return "seto";
2784    case ISD::SETUO:   return "setuo";
2785    case ISD::SETUEQ:  return "setue";
2786    case ISD::SETUGT:  return "setugt";
2787    case ISD::SETUGE:  return "setuge";
2788    case ISD::SETULT:  return "setult";
2789    case ISD::SETULE:  return "setule";
2790    case ISD::SETUNE:  return "setune";
2791
2792    case ISD::SETEQ:   return "seteq";
2793    case ISD::SETGT:   return "setgt";
2794    case ISD::SETGE:   return "setge";
2795    case ISD::SETLT:   return "setlt";
2796    case ISD::SETLE:   return "setle";
2797    case ISD::SETNE:   return "setne";
2798    }
2799  }
2800}
2801
2802const char *SDNode::getAddressingModeName(ISD::MemOpAddrMode AM) {
2803  switch (AM) {
2804  default:
2805    return "";
2806  case ISD::PRE_INC:
2807    return "<pre-inc>";
2808  case ISD::PRE_DEC:
2809    return "<pre-dec>";
2810  case ISD::POST_INC:
2811    return "<post-inc>";
2812  case ISD::POST_DEC:
2813    return "<post-dec>";
2814  }
2815}
2816
2817void SDNode::dump() const { dump(0); }
2818void SDNode::dump(const SelectionDAG *G) const {
2819  std::cerr << (void*)this << ": ";
2820
2821  for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
2822    if (i) std::cerr << ",";
2823    if (getValueType(i) == MVT::Other)
2824      std::cerr << "ch";
2825    else
2826      std::cerr << MVT::getValueTypeString(getValueType(i));
2827  }
2828  std::cerr << " = " << getOperationName(G);
2829
2830  std::cerr << " ";
2831  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
2832    if (i) std::cerr << ", ";
2833    std::cerr << (void*)getOperand(i).Val;
2834    if (unsigned RN = getOperand(i).ResNo)
2835      std::cerr << ":" << RN;
2836  }
2837
2838  if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
2839    std::cerr << "<" << CSDN->getValue() << ">";
2840  } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
2841    std::cerr << "<" << CSDN->getValue() << ">";
2842  } else if (const GlobalAddressSDNode *GADN =
2843             dyn_cast<GlobalAddressSDNode>(this)) {
2844    int offset = GADN->getOffset();
2845    std::cerr << "<";
2846    WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
2847    if (offset > 0)
2848      std::cerr << " + " << offset;
2849    else
2850      std::cerr << " " << offset;
2851  } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
2852    std::cerr << "<" << FIDN->getIndex() << ">";
2853  } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
2854    int offset = CP->getOffset();
2855    if (CP->isMachineConstantPoolEntry())
2856      std::cerr << "<" << *CP->getMachineCPVal() << ">";
2857    else
2858      std::cerr << "<" << *CP->getConstVal() << ">";
2859    if (offset > 0)
2860      std::cerr << " + " << offset;
2861    else
2862      std::cerr << " " << offset;
2863  } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
2864    std::cerr << "<";
2865    const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
2866    if (LBB)
2867      std::cerr << LBB->getName() << " ";
2868    std::cerr << (const void*)BBDN->getBasicBlock() << ">";
2869  } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
2870    if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) {
2871      std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg());
2872    } else {
2873      std::cerr << " #" << R->getReg();
2874    }
2875  } else if (const ExternalSymbolSDNode *ES =
2876             dyn_cast<ExternalSymbolSDNode>(this)) {
2877    std::cerr << "'" << ES->getSymbol() << "'";
2878  } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
2879    if (M->getValue())
2880      std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">";
2881    else
2882      std::cerr << "<null:" << M->getOffset() << ">";
2883  } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
2884    std::cerr << ":" << getValueTypeString(N->getVT());
2885  } else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
2886    bool doExt = true;
2887    switch (LD->getExtensionType()) {
2888    default: doExt = false; break;
2889    case ISD::EXTLOAD:
2890      std::cerr << " <anyext ";
2891      break;
2892    case ISD::SEXTLOAD:
2893      std::cerr << " <sext ";
2894      break;
2895    case ISD::ZEXTLOAD:
2896      std::cerr << " <zext ";
2897      break;
2898    }
2899    if (doExt)
2900      std::cerr << MVT::getValueTypeString(LD->getLoadedVT()) << ">";
2901
2902    const char *AM = getAddressingModeName(LD->getAddressingMode());
2903    if (AM != "")
2904      std::cerr << " " << AM;
2905  } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) {
2906    if (ST->isTruncatingStore())
2907      std::cerr << " <trunc "
2908                << MVT::getValueTypeString(ST->getStoredVT()) << ">";
2909
2910    const char *AM = getAddressingModeName(ST->getAddressingMode());
2911    if (AM != "")
2912      std::cerr << " " << AM;
2913  }
2914}
2915
2916static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
2917  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
2918    if (N->getOperand(i).Val->hasOneUse())
2919      DumpNodes(N->getOperand(i).Val, indent+2, G);
2920    else
2921      std::cerr << "\n" << std::string(indent+2, ' ')
2922                << (void*)N->getOperand(i).Val << ": <multiple use>";
2923
2924
2925  std::cerr << "\n" << std::string(indent, ' ');
2926  N->dump(G);
2927}
2928
2929void SelectionDAG::dump() const {
2930  std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
2931  std::vector<const SDNode*> Nodes;
2932  for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
2933       I != E; ++I)
2934    Nodes.push_back(I);
2935
2936  std::sort(Nodes.begin(), Nodes.end());
2937
2938  for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
2939    if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
2940      DumpNodes(Nodes[i], 2, this);
2941  }
2942
2943  if (getRoot().Val) DumpNodes(getRoot().Val, 2, this);
2944
2945  std::cerr << "\n\n";
2946}
2947
2948const Type *ConstantPoolSDNode::getType() const {
2949  if (isMachineConstantPoolEntry())
2950    return Val.MachineCPVal->getType();
2951  return Val.ConstVal->getType();
2952}
2953