Add MULHU and MULHS nodes for the high part of an (un)signed 32x32=64b
[oota-llvm.git] / lib / CodeGen / SelectionDAG / SelectionDAG.cpp
1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
2 // 
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file 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/Assembly/Writer.h"
18 #include "llvm/CodeGen/MachineBasicBlock.h"
19 #include "llvm/Target/TargetLowering.h"
20 #include <iostream>
21 #include <set>
22 #include <cmath>
23 #include <algorithm>
24 using namespace llvm;
25
26 static bool isCommutativeBinOp(unsigned Opcode) {
27   switch (Opcode) {
28   case ISD::ADD:
29   case ISD::MUL:
30   case ISD::AND:
31   case ISD::OR:
32   case ISD::XOR: return true;
33   default: return false; // FIXME: Need commutative info for user ops!
34   }
35 }
36
37 static bool isAssociativeBinOp(unsigned Opcode) {
38   switch (Opcode) {
39   case ISD::ADD:
40   case ISD::MUL:
41   case ISD::AND:
42   case ISD::OR:
43   case ISD::XOR: return true;
44   default: return false; // FIXME: Need associative info for user ops!
45   }
46 }
47
48 static unsigned ExactLog2(uint64_t Val) {
49   unsigned Count = 0;
50   while (Val != 1) {
51     Val >>= 1;
52     ++Count;
53   }
54   return Count;
55 }
56
57 // isInvertibleForFree - Return true if there is no cost to emitting the logical
58 // inverse of this node.
59 static bool isInvertibleForFree(SDOperand N) {
60   if (isa<ConstantSDNode>(N.Val)) return true;
61   if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse())
62     return true;
63   return false;  
64 }
65
66
67 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
68 /// when given the operation for (X op Y).
69 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
70   // To perform this operation, we just need to swap the L and G bits of the
71   // operation.
72   unsigned OldL = (Operation >> 2) & 1;
73   unsigned OldG = (Operation >> 1) & 1;
74   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
75                        (OldL << 1) |       // New G bit
76                        (OldG << 2));        // New L bit.
77 }
78
79 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
80 /// 'op' is a valid SetCC operation.
81 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
82   unsigned Operation = Op;
83   if (isInteger)
84     Operation ^= 7;   // Flip L, G, E bits, but not U.
85   else
86     Operation ^= 15;  // Flip all of the condition bits.
87   if (Operation > ISD::SETTRUE2)
88     Operation &= ~8;     // Don't let N and U bits get set.
89   return ISD::CondCode(Operation);
90 }
91
92
93 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
94 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
95 /// if the operation does not depend on the sign of the input (setne and seteq).
96 static int isSignedOp(ISD::CondCode Opcode) {
97   switch (Opcode) {
98   default: assert(0 && "Illegal integer setcc operation!");
99   case ISD::SETEQ:
100   case ISD::SETNE: return 0;
101   case ISD::SETLT:
102   case ISD::SETLE:
103   case ISD::SETGT:
104   case ISD::SETGE: return 1;
105   case ISD::SETULT:
106   case ISD::SETULE:
107   case ISD::SETUGT:
108   case ISD::SETUGE: return 2;
109   }
110 }
111
112 /// getSetCCOrOperation - Return the result of a logical OR between different
113 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
114 /// returns SETCC_INVALID if it is not possible to represent the resultant
115 /// comparison.
116 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
117                                        bool isInteger) {
118   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
119     // Cannot fold a signed integer setcc with an unsigned integer setcc.
120     return ISD::SETCC_INVALID;
121   
122   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
123   
124   // If the N and U bits get set then the resultant comparison DOES suddenly
125   // care about orderedness, and is true when ordered.
126   if (Op > ISD::SETTRUE2)
127     Op &= ~16;     // Clear the N bit.
128   return ISD::CondCode(Op);
129 }
130
131 /// getSetCCAndOperation - Return the result of a logical AND between different
132 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
133 /// function returns zero if it is not possible to represent the resultant
134 /// comparison.
135 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
136                                         bool isInteger) {
137   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
138     // Cannot fold a signed setcc with an unsigned setcc.
139     return ISD::SETCC_INVALID; 
140
141   // Combine all of the condition bits.
142   return ISD::CondCode(Op1 & Op2);
143 }
144
145 const TargetMachine &SelectionDAG::getTarget() const {
146   return TLI.getTargetMachine();
147 }
148
149
150 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
151 /// SelectionDAG, including nodes (like loads) that have uses of their token
152 /// chain but no other uses and no side effect.  If a node is passed in as an
153 /// argument, it is used as the seed for node deletion.
154 void SelectionDAG::RemoveDeadNodes(SDNode *N) {
155   std::set<SDNode*> AllNodeSet(AllNodes.begin(), AllNodes.end());
156
157   // Create a dummy node (which is not added to allnodes), that adds a reference
158   // to the root node, preventing it from being deleted.
159   SDNode *DummyNode = new SDNode(ISD::EntryToken, getRoot());
160
161   DeleteNodeIfDead(N, &AllNodeSet);
162
163  Restart:
164   unsigned NumNodes = AllNodeSet.size();
165   for (std::set<SDNode*>::iterator I = AllNodeSet.begin(), E = AllNodeSet.end();
166        I != E; ++I) {
167     // Try to delete this node.
168     DeleteNodeIfDead(*I, &AllNodeSet);
169
170     // If we actually deleted any nodes, do not use invalid iterators in
171     // AllNodeSet.
172     if (AllNodeSet.size() != NumNodes)
173       goto Restart;
174   }
175
176   // Restore AllNodes.
177   if (AllNodes.size() != NumNodes)
178     AllNodes.assign(AllNodeSet.begin(), AllNodeSet.end());
179
180   // If the root changed (e.g. it was a dead load, update the root).
181   setRoot(DummyNode->getOperand(0));
182
183   // Now that we are done with the dummy node, delete it.
184   DummyNode->getOperand(0).Val->removeUser(DummyNode);
185   delete DummyNode;
186 }
187
188 void SelectionDAG::DeleteNodeIfDead(SDNode *N, void *NodeSet) {
189   if (!N->use_empty())
190     return;
191
192   // Okay, we really are going to delete this node.  First take this out of the
193   // appropriate CSE map.
194   switch (N->getOpcode()) {
195   case ISD::Constant:
196     Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
197                                    N->getValueType(0)));
198     break;
199   case ISD::ConstantFP: {
200     union {
201       double DV;
202       uint64_t IV;
203     };
204     DV = cast<ConstantFPSDNode>(N)->getValue();
205     ConstantFPs.erase(std::make_pair(IV, N->getValueType(0)));
206     break;
207   }
208   case ISD::GlobalAddress:
209     GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal());
210     break;
211   case ISD::FrameIndex:
212     FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
213     break;
214   case ISD::ConstantPool:
215     ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->getIndex());
216     break;
217   case ISD::BasicBlock:
218     BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
219     break;
220   case ISD::ExternalSymbol:
221     ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
222     break;
223
224   case ISD::LOAD:
225     Loads.erase(std::make_pair(N->getOperand(1),
226                                std::make_pair(N->getOperand(0),
227                                               N->getValueType(0))));
228     break;
229   case ISD::SETCC:
230     SetCCs.erase(std::make_pair(std::make_pair(N->getOperand(0),
231                                                N->getOperand(1)),
232                                 std::make_pair(
233                                      cast<SetCCSDNode>(N)->getCondition(),
234                                      N->getValueType(0))));
235     break;
236   case ISD::TRUNCSTORE:
237   case ISD::SIGN_EXTEND_INREG:
238   case ISD::ZERO_EXTEND_INREG:
239   case ISD::FP_ROUND_INREG:
240   case ISD::EXTLOAD:
241   case ISD::SEXTLOAD:
242   case ISD::ZEXTLOAD: {
243     EVTStruct NN;
244     NN.Opcode = ISD::TRUNCSTORE;
245     NN.VT = N->getValueType(0);
246     NN.EVT = cast<MVTSDNode>(N)->getExtraValueType();
247     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
248       NN.Ops.push_back(N->getOperand(i));
249     MVTSDNodes.erase(NN);
250     break;
251   }
252   default:
253     if (N->getNumOperands() == 1)
254       UnaryOps.erase(std::make_pair(N->getOpcode(),
255                                     std::make_pair(N->getOperand(0),
256                                                    N->getValueType(0))));
257     else if (N->getNumOperands() == 2)
258       BinaryOps.erase(std::make_pair(N->getOpcode(),
259                                      std::make_pair(N->getOperand(0),
260                                                     N->getOperand(1))));
261     break;
262   }
263
264   // Next, brutally remove the operand list.
265   while (!N->Operands.empty()) {
266     SDNode *O = N->Operands.back().Val;
267     N->Operands.pop_back();
268     O->removeUser(N);
269
270     // Now that we removed this operand, see if there are no uses of it left.
271     DeleteNodeIfDead(O, NodeSet);
272   }
273   
274   // Remove the node from the nodes set and delete it.
275   std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet;
276   AllNodeSet.erase(N);
277
278   // Now that the node is gone, check to see if any of the operands of this node
279   // are dead now.
280   delete N;
281 }
282
283
284 SelectionDAG::~SelectionDAG() {
285   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
286     delete AllNodes[i];
287 }
288
289 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
290   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
291   // Mask out any bits that are not valid for this constant.
292   if (VT != MVT::i64)
293     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
294   
295   SDNode *&N = Constants[std::make_pair(Val, VT)];
296   if (N) return SDOperand(N, 0);
297   N = new ConstantSDNode(Val, VT);
298   AllNodes.push_back(N);
299   return SDOperand(N, 0);
300 }
301
302 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
303   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
304   if (VT == MVT::f32)
305     Val = (float)Val;  // Mask out extra precision.
306
307   // Do the map lookup using the actual bit pattern for the floating point
308   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
309   // we don't have issues with SNANs.
310   union {
311     double DV;
312     uint64_t IV;
313   };
314   
315   DV = Val;
316
317   SDNode *&N = ConstantFPs[std::make_pair(IV, VT)];
318   if (N) return SDOperand(N, 0);
319   N = new ConstantFPSDNode(Val, VT);
320   AllNodes.push_back(N);
321   return SDOperand(N, 0);
322 }
323
324
325
326 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
327                                          MVT::ValueType VT) {
328   SDNode *&N = GlobalValues[GV];
329   if (N) return SDOperand(N, 0);
330   N = new GlobalAddressSDNode(GV,VT);
331   AllNodes.push_back(N);
332   return SDOperand(N, 0);
333 }
334
335 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
336   SDNode *&N = FrameIndices[FI];
337   if (N) return SDOperand(N, 0);
338   N = new FrameIndexSDNode(FI, VT);
339   AllNodes.push_back(N);
340   return SDOperand(N, 0);
341 }
342
343 SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) {
344   SDNode *N = ConstantPoolIndices[CPIdx];
345   if (N) return SDOperand(N, 0);
346   N = new ConstantPoolSDNode(CPIdx, VT);
347   AllNodes.push_back(N);
348   return SDOperand(N, 0);
349 }
350
351 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
352   SDNode *&N = BBNodes[MBB];
353   if (N) return SDOperand(N, 0);
354   N = new BasicBlockSDNode(MBB);
355   AllNodes.push_back(N);
356   return SDOperand(N, 0);
357 }
358
359 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
360   SDNode *&N = ExternalSymbols[Sym];
361   if (N) return SDOperand(N, 0);
362   N = new ExternalSymbolSDNode(Sym, VT);
363   AllNodes.push_back(N);
364   return SDOperand(N, 0);
365 }
366
367 SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, MVT::ValueType VT,
368                                  SDOperand N1, SDOperand N2) {
369   // These setcc operations always fold.
370   switch (Cond) {
371   default: break;
372   case ISD::SETFALSE:
373   case ISD::SETFALSE2: return getConstant(0, VT);
374   case ISD::SETTRUE:
375   case ISD::SETTRUE2:  return getConstant(1, VT);
376   }
377
378   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val))
379     if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
380       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
381       
382       // Sign extend the operands if required
383       if (ISD::isSignedIntSetCC(Cond)) {
384         C1 = N1C->getSignExtended();
385         C2 = N2C->getSignExtended();
386       }
387
388       switch (Cond) {
389       default: assert(0 && "Unknown integer setcc!");
390       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
391       case ISD::SETNE:  return getConstant(C1 != C2, VT);
392       case ISD::SETULT: return getConstant(C1 <  C2, VT);
393       case ISD::SETUGT: return getConstant(C1 >  C2, VT);
394       case ISD::SETULE: return getConstant(C1 <= C2, VT);
395       case ISD::SETUGE: return getConstant(C1 >= C2, VT);
396       case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
397       case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
398       case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
399       case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
400       }
401     } else {
402       // Ensure that the constant occurs on the RHS.
403       Cond = ISD::getSetCCSwappedOperands(Cond);
404       std::swap(N1, N2);
405     }
406
407   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
408     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
409       double C1 = N1C->getValue(), C2 = N2C->getValue();
410       
411       switch (Cond) {
412       default: break; // FIXME: Implement the rest of these!
413       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
414       case ISD::SETNE:  return getConstant(C1 != C2, VT);
415       case ISD::SETLT:  return getConstant(C1 < C2, VT);
416       case ISD::SETGT:  return getConstant(C1 > C2, VT);
417       case ISD::SETLE:  return getConstant(C1 <= C2, VT);
418       case ISD::SETGE:  return getConstant(C1 >= C2, VT);
419       }
420     } else {
421       // Ensure that the constant occurs on the RHS.
422       Cond = ISD::getSetCCSwappedOperands(Cond);
423       std::swap(N1, N2);
424     }
425
426   if (N1 == N2) {
427     // We can always fold X == Y for integer setcc's.
428     if (MVT::isInteger(N1.getValueType()))
429       return getConstant(ISD::isTrueWhenEqual(Cond), VT);
430     unsigned UOF = ISD::getUnorderedFlavor(Cond);
431     if (UOF == 2)   // FP operators that are undefined on NaNs.
432       return getConstant(ISD::isTrueWhenEqual(Cond), VT);
433     if (UOF == ISD::isTrueWhenEqual(Cond))
434       return getConstant(UOF, VT);
435     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
436     // if it is not already.
437     Cond = UOF == 0 ? ISD::SETUO : ISD::SETO;
438   }
439
440   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
441       MVT::isInteger(N1.getValueType())) {
442     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
443         N1.getOpcode() == ISD::XOR) {
444       // Simplify (X+Y) == (X+Z) -->  Y == Z
445       if (N1.getOpcode() == N2.getOpcode()) {
446         if (N1.getOperand(0) == N2.getOperand(0))
447           return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(1));
448         if (N1.getOperand(1) == N2.getOperand(1))
449           return getSetCC(Cond, VT, N1.getOperand(0), N2.getOperand(0));
450         if (isCommutativeBinOp(N1.getOpcode())) {
451           // If X op Y == Y op X, try other combinations.
452           if (N1.getOperand(0) == N2.getOperand(1))
453             return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(0));
454           if (N1.getOperand(1) == N2.getOperand(0))
455             return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(1));
456         }
457       }
458
459       // FIXME: move this stuff to the DAG Combiner when it exists!
460       
461       // Simplify (X+Z) == X -->  Z == 0
462       if (N1.getOperand(0) == N2)
463         return getSetCC(Cond, VT, N1.getOperand(1),
464                         getConstant(0, N1.getValueType()));
465       if (N1.getOperand(1) == N2) {
466         if (isCommutativeBinOp(N1.getOpcode()))
467           return getSetCC(Cond, VT, N1.getOperand(0),
468                           getConstant(0, N1.getValueType()));
469         else {
470           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
471           // (Z-X) == X  --> Z == X<<1
472           return getSetCC(Cond, VT, N1.getOperand(0),
473                           getNode(ISD::SHL, N2.getValueType(), 
474                                   N2, getConstant(1, TLI.getShiftAmountTy())));
475         }
476       }
477     }
478
479     if (N2.getOpcode() == ISD::ADD || N2.getOpcode() == ISD::SUB ||
480         N2.getOpcode() == ISD::XOR) {
481       // Simplify  X == (X+Z) -->  Z == 0
482       if (N2.getOperand(0) == N1)
483         return getSetCC(Cond, VT, N2.getOperand(1),
484                         getConstant(0, N2.getValueType()));
485       else if (N2.getOperand(1) == N1)
486         return getSetCC(Cond, VT, N2.getOperand(0),
487                         getConstant(0, N2.getValueType()));
488     }
489   }
490
491   SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2),
492                                           std::make_pair(Cond, VT))];
493   if (N) return SDOperand(N, 0);
494   N = new SetCCSDNode(Cond, N1, N2);
495   N->setValueTypes(VT);
496   AllNodes.push_back(N);
497   return SDOperand(N, 0);
498 }
499
500
501
502 /// getNode - Gets or creates the specified node.
503 ///
504 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
505   SDNode *N = new SDNode(Opcode, VT);
506   AllNodes.push_back(N);
507   return SDOperand(N, 0);
508 }
509
510 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
511                                 SDOperand Operand) {
512   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
513     uint64_t Val = C->getValue();
514     switch (Opcode) {
515     default: break;
516     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
517     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
518     case ISD::TRUNCATE:    return getConstant(Val, VT);
519     case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
520     case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
521     }
522   }
523
524   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
525     switch (Opcode) {
526     case ISD::FP_ROUND:
527     case ISD::FP_EXTEND:
528       return getConstantFP(C->getValue(), VT);
529     case ISD::FP_TO_SINT:
530       return getConstant((int64_t)C->getValue(), VT);
531     case ISD::FP_TO_UINT:
532       return getConstant((uint64_t)C->getValue(), VT);
533     }
534
535   unsigned OpOpcode = Operand.Val->getOpcode();
536   switch (Opcode) {
537   case ISD::TokenFactor:
538     return Operand;         // Factor of one node?  No factor.
539   case ISD::SIGN_EXTEND:
540     if (Operand.getValueType() == VT) return Operand;   // noop extension
541     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
542       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
543     break;
544   case ISD::ZERO_EXTEND:
545     if (Operand.getValueType() == VT) return Operand;   // noop extension
546     if (OpOpcode == ISD::ZERO_EXTEND)
547       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
548     break;
549   case ISD::TRUNCATE:
550     if (Operand.getValueType() == VT) return Operand;   // noop truncate
551     if (OpOpcode == ISD::TRUNCATE)
552       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
553     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) {
554       // If the source is smaller than the dest, we still need an extend.
555       if (Operand.Val->getOperand(0).getValueType() < VT)
556         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
557       else if (Operand.Val->getOperand(0).getValueType() > VT)
558         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
559       else
560         return Operand.Val->getOperand(0);
561     }
562     break;
563   }
564
565   SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
566   if (N) return SDOperand(N, 0);
567   N = new SDNode(Opcode, Operand);
568   N->setValueTypes(VT);
569   AllNodes.push_back(N);
570   return SDOperand(N, 0);
571 }
572
573 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
574                                 SDOperand N1, SDOperand N2) {
575 #ifndef NDEBUG
576   switch (Opcode) {
577   case ISD::TokenFactor:
578     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
579            N2.getValueType() == MVT::Other && "Invalid token factor!");
580     break;
581   case ISD::AND:
582   case ISD::OR:
583   case ISD::XOR:
584   case ISD::UDIV:
585   case ISD::UREM:
586     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
587     // fall through
588   case ISD::ADD:
589   case ISD::SUB:
590   case ISD::MUL:
591   case ISD::SDIV:
592   case ISD::SREM:
593     assert(N1.getValueType() == N2.getValueType() &&
594            N1.getValueType() == VT && "Binary operator types must match!");
595     break;
596
597   case ISD::SHL:
598   case ISD::SRA:
599   case ISD::SRL:
600     assert(VT == N1.getValueType() &&
601            "Shift operators return type must be the same as their first arg");
602     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
603            VT != MVT::i1 && "Shifts only work on integers");
604     break;
605   default: break;
606   }
607 #endif
608
609   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
610   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
611   if (N1C) {
612     if (N2C) {
613       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
614       switch (Opcode) {
615       case ISD::ADD: return getConstant(C1 + C2, VT);
616       case ISD::SUB: return getConstant(C1 - C2, VT);
617       case ISD::MUL: return getConstant(C1 * C2, VT);
618       case ISD::UDIV:
619         if (C2) return getConstant(C1 / C2, VT);
620         break;
621       case ISD::UREM :
622         if (C2) return getConstant(C1 % C2, VT);
623         break;
624       case ISD::SDIV :
625         if (C2) return getConstant(N1C->getSignExtended() /
626                                    N2C->getSignExtended(), VT);
627         break;
628       case ISD::SREM :
629         if (C2) return getConstant(N1C->getSignExtended() %
630                                    N2C->getSignExtended(), VT);
631         break;
632       case ISD::AND  : return getConstant(C1 & C2, VT);
633       case ISD::OR   : return getConstant(C1 | C2, VT);
634       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
635       case ISD::SHL  : return getConstant(C1 << (int)C2, VT);
636       case ISD::SRL  : return getConstant(C1 >> (unsigned)C2, VT);
637       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
638       default: break;
639       }
640
641     } else {      // Cannonicalize constant to RHS if commutative
642       if (isCommutativeBinOp(Opcode)) {
643         std::swap(N1C, N2C);
644         std::swap(N1, N2);
645       }
646     }
647
648     switch (Opcode) {
649     default: break;
650     case ISD::SHL:    // shl  0, X -> 0
651       if (N1C->isNullValue()) return N1;
652       break;
653     case ISD::SRL:    // srl  0, X -> 0
654       if (N1C->isNullValue()) return N1;
655       break;
656     case ISD::SRA:    // sra -1, X -> -1
657       if (N1C->isAllOnesValue()) return N1;
658       break;
659     }
660   }
661
662   if (N2C) {
663     uint64_t C2 = N2C->getValue();
664
665     switch (Opcode) {
666     case ISD::ADD:
667       if (!C2) return N1;         // add X, 0 -> X
668       break;
669     case ISD::SUB:
670       if (!C2) return N1;         // sub X, 0 -> X
671       break;
672     case ISD::MUL:
673       if (!C2) return N2;         // mul X, 0 -> 0
674       if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X
675         return getNode(ISD::SUB, VT, getConstant(0, VT), N1);
676
677       // FIXME: Move this to the DAG combiner when it exists.
678       if ((C2 & C2-1) == 0) {
679         SDOperand ShAmt = getConstant(ExactLog2(C2), TLI.getShiftAmountTy());
680         return getNode(ISD::SHL, VT, N1, ShAmt);
681       }
682       break;
683
684     case ISD::UDIV:
685       // FIXME: Move this to the DAG combiner when it exists.
686       if ((C2 & C2-1) == 0 && C2) {
687         SDOperand ShAmt = getConstant(ExactLog2(C2), TLI.getShiftAmountTy());
688         return getNode(ISD::SRL, VT, N1, ShAmt);
689       }
690       break;
691
692     case ISD::SHL:
693     case ISD::SRL:
694       // If the shift amount is bigger than the size of the data, simplify.
695       if (C2 >= MVT::getSizeInBits(N1.getValueType())) {
696         if (TLI.getShiftAmountFlavor() == TargetLowering::Mask) {
697           unsigned NewAmt =
698             C2 & ((1 << MVT::getSizeInBits(N1.getValueType()))-1);
699           return getNode(Opcode, VT, N1, getConstant(NewAmt,N2.getValueType()));
700         } else if (TLI.getShiftAmountFlavor() == TargetLowering::Extend) {
701           // Shifting all of the bits out?
702           return getConstant(0, N1.getValueType());
703         }
704       }
705       // FALL THROUGH.
706     case ISD::SRA:
707       if (C2 == 0) return N1;
708       break;
709
710     case ISD::AND:
711       if (!C2) return N2;         // X and 0 -> 0
712       if (N2C->isAllOnesValue())
713         return N1;                // X and -1 -> X
714       break;
715     case ISD::OR:
716       if (!C2)return N1;          // X or 0 -> X
717       if (N2C->isAllOnesValue())
718         return N2;                // X or -1 -> -1
719       break;
720     case ISD::XOR:
721       if (!C2) return N1;        // X xor 0 -> X
722       if (N2C->isAllOnesValue()) {
723         if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){
724           // !(X op Y) -> (X !op Y)
725           bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
726           return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger),
727                           SetCC->getValueType(0),
728                           SetCC->getOperand(0), SetCC->getOperand(1));
729         } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
730           SDNode *Op = N1.Val;
731           // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
732           // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
733           SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
734           if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
735             LHS = getNode(ISD::XOR, VT, LHS, N2);  // RHS = ~LHS
736             RHS = getNode(ISD::XOR, VT, RHS, N2);  // RHS = ~RHS
737             if (Op->getOpcode() == ISD::AND)
738               return getNode(ISD::OR, VT, LHS, RHS);
739             return getNode(ISD::AND, VT, LHS, RHS);
740           }
741         }
742         // X xor -1 -> not(x)  ?
743       }
744       break;
745     }
746
747     // Reassociate ((X op C1) op C2) if possible.
748     if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
749       if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
750         return getNode(Opcode, VT, N1.Val->getOperand(0),
751                        getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
752   }
753
754   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
755   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
756   if (N1CFP)
757     if (N2CFP) {
758       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
759       switch (Opcode) {
760       case ISD::ADD: return getConstantFP(C1 + C2, VT);
761       case ISD::SUB: return getConstantFP(C1 - C2, VT);
762       case ISD::MUL: return getConstantFP(C1 * C2, VT);
763       case ISD::SDIV:
764         if (C2) return getConstantFP(C1 / C2, VT);
765         break;
766       case ISD::SREM :
767         if (C2) return getConstantFP(fmod(C1, C2), VT);
768         break;
769       default: break;
770       }
771
772     } else {      // Cannonicalize constant to RHS if commutative
773       if (isCommutativeBinOp(Opcode)) {
774         std::swap(N1CFP, N2CFP);
775         std::swap(N1, N2);
776       }
777     }
778
779   // Finally, fold operations that do not require constants.
780   switch (Opcode) {
781   case ISD::TokenFactor:
782     if (N1.getOpcode() == ISD::EntryToken)
783       return N2;
784     if (N2.getOpcode() == ISD::EntryToken)
785       return N1;
786     break;
787
788   case ISD::AND:
789   case ISD::OR:
790     if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val))
791       if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) {
792         SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
793         SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
794         ISD::CondCode Op2 = RHS->getCondition();
795
796         // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
797         if (LL == RR && LR == RL) {
798           Op2 = ISD::getSetCCSwappedOperands(Op2);
799           goto MatchedBackwards;
800         }
801       
802         if (LL == RL && LR == RR) {
803         MatchedBackwards:
804           ISD::CondCode Result;
805           bool isInteger = MVT::isInteger(LL.getValueType());
806           if (Opcode == ISD::OR)
807             Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2,
808                                               isInteger);
809           else
810             Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2,
811                                                isInteger);
812           if (Result != ISD::SETCC_INVALID)
813             return getSetCC(Result, LHS->getValueType(0), LL, LR);
814         }
815       }
816     break;
817   case ISD::XOR:
818     if (N1 == N2) return getConstant(0, VT);  // xor X, Y -> 0
819     break;
820   case ISD::SUB:
821     if (N1.getOpcode() == ISD::ADD) {
822       if (N1.Val->getOperand(0) == N2)
823         return N1.Val->getOperand(1);         // (A+B)-A == B
824       if (N1.Val->getOperand(1) == N2)
825         return N1.Val->getOperand(0);         // (A+B)-B == A
826     }
827     break;
828   }
829
830   SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
831   if (N) return SDOperand(N, 0);
832   N = new SDNode(Opcode, N1, N2);
833   N->setValueTypes(VT);
834
835   AllNodes.push_back(N);
836   return SDOperand(N, 0);
837 }
838
839 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
840                                 SDOperand Chain, SDOperand Ptr) {
841   SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
842   if (N) return SDOperand(N, 0);
843   N = new SDNode(ISD::LOAD, Chain, Ptr);
844
845   // Loads have a token chain.
846   N->setValueTypes(VT, MVT::Other);
847   AllNodes.push_back(N);
848   return SDOperand(N, 0);
849 }
850
851
852 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
853                                 SDOperand N1, SDOperand N2, SDOperand N3) {
854   // Perform various simplifications.
855   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
856   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
857   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
858   switch (Opcode) {
859   case ISD::SELECT:
860     if (N1C)
861       if (N1C->getValue())
862         return N2;             // select true, X, Y -> X
863       else 
864         return N3;             // select false, X, Y -> Y
865
866     if (N2 == N3) return N2;   // select C, X, X -> X
867
868     if (VT == MVT::i1) {  // Boolean SELECT
869       if (N2C) {
870         if (N3C) {
871           if (N2C->getValue()) // select C, 1, 0 -> C
872             return N1;
873           return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C
874         }
875
876         if (N2C->getValue())   // select C, 1, X -> C | X
877           return getNode(ISD::OR, VT, N1, N3);
878         else                   // select C, 0, X -> ~C & X
879           return getNode(ISD::AND, VT,
880                          getNode(ISD::XOR, N1.getValueType(), N1,
881                                  getConstant(1, N1.getValueType())), N3);
882       } else if (N3C) {
883         if (N3C->getValue())   // select C, X, 1 -> ~C | X
884           return getNode(ISD::OR, VT,
885                          getNode(ISD::XOR, N1.getValueType(), N1,
886                                  getConstant(1, N1.getValueType())), N2);
887         else                   // select C, X, 0 -> C & X
888           return getNode(ISD::AND, VT, N1, N2);
889       }
890     }
891
892     break;
893   case ISD::BRCOND:
894     if (N2C)
895       if (N2C->getValue()) // Unconditional branch
896         return getNode(ISD::BR, MVT::Other, N1, N3);
897       else
898         return N1;         // Never-taken branch
899     break;
900   }
901
902   SDNode *N = new SDNode(Opcode, N1, N2, N3);
903   switch (Opcode) {
904   default: 
905     N->setValueTypes(VT);
906     break;
907   case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain
908     N->setValueTypes(VT, MVT::Other);
909     break;
910
911   case ISD::SRA_PARTS:
912   case ISD::SRL_PARTS:
913   case ISD::SHL_PARTS: {
914     std::vector<MVT::ValueType> V(N->getNumOperands()-1, VT);
915     N->setValueTypes(V);
916     break;
917   }
918   }
919
920   // FIXME: memoize NODES
921   AllNodes.push_back(N);
922   return SDOperand(N, 0);
923 }
924
925 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
926                                 std::vector<SDOperand> &Children) {
927   switch (Children.size()) {
928   case 0: return getNode(Opcode, VT);
929   case 1: return getNode(Opcode, VT, Children[0]);
930   case 2: return getNode(Opcode, VT, Children[0], Children[1]);
931   case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]);
932   default:
933     // FIXME: MEMOIZE!!
934     SDNode *N = new SDNode(Opcode, Children);
935     if (Opcode != ISD::ADD_PARTS && Opcode != ISD::SUB_PARTS) {
936       N->setValueTypes(VT);
937     } else {
938       std::vector<MVT::ValueType> V(N->getNumOperands()/2, VT);
939       N->setValueTypes(V);
940     }
941     AllNodes.push_back(N);
942     return SDOperand(N, 0);
943   }
944 }
945
946 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1,
947                                 MVT::ValueType EVT) {
948
949   switch (Opcode) {
950   default: assert(0 && "Bad opcode for this accessor!");
951   case ISD::FP_ROUND_INREG:
952     assert(VT == N1.getValueType() && "Not an inreg round!");
953     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
954            "Cannot FP_ROUND_INREG integer types");
955     if (EVT == VT) return N1;  // Not actually rounding
956     assert(EVT < VT && "Not rounding down!");
957
958     if (isa<ConstantFPSDNode>(N1))
959       return getNode(ISD::FP_EXTEND, VT, getNode(ISD::FP_ROUND, EVT, N1));
960     break;
961   case ISD::ZERO_EXTEND_INREG:
962   case ISD::SIGN_EXTEND_INREG:
963     assert(VT == N1.getValueType() && "Not an inreg extend!");
964     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
965            "Cannot *_EXTEND_INREG FP types");
966     if (EVT == VT) return N1;  // Not actually extending
967     assert(EVT < VT && "Not extending!");
968
969     // Extending a constant?  Just return the constant.
970     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
971       SDOperand Tmp = getNode(ISD::TRUNCATE, EVT, N1);
972       if (Opcode == ISD::ZERO_EXTEND_INREG)
973         return getNode(ISD::ZERO_EXTEND, VT, Tmp);
974       else
975         return getNode(ISD::SIGN_EXTEND, VT, Tmp);
976     }
977
978     // If we are sign extending an extension, use the original source.
979     if (N1.getOpcode() == ISD::ZERO_EXTEND_INREG ||
980         N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
981       if (N1.getOpcode() == Opcode &&
982           cast<MVTSDNode>(N1)->getExtraValueType() <= EVT)
983         return N1;
984     }
985
986     break;
987   }
988
989   EVTStruct NN;
990   NN.Opcode = Opcode;
991   NN.VT = VT;
992   NN.EVT = EVT;
993   NN.Ops.push_back(N1);
994
995   SDNode *&N = MVTSDNodes[NN];
996   if (N) return SDOperand(N, 0);
997   N = new MVTSDNode(Opcode, VT, N1, EVT);
998   AllNodes.push_back(N);
999   return SDOperand(N, 0);
1000 }
1001
1002 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1,
1003                                 SDOperand N2, MVT::ValueType EVT) {
1004   switch (Opcode) {
1005   default:  assert(0 && "Bad opcode for this accessor!");
1006   case ISD::EXTLOAD:
1007   case ISD::SEXTLOAD:
1008   case ISD::ZEXTLOAD:
1009     // If they are asking for an extending loat from/to the same thing, return a
1010     // normal load.
1011     if (VT == EVT)
1012       return getNode(ISD::LOAD, VT, N1, N2);
1013     assert(EVT < VT && "Should only be an extending load, not truncating!");
1014     assert((Opcode == ISD::EXTLOAD || MVT::isInteger(VT)) && 
1015            "Cannot sign/zero extend a FP load!");
1016     assert(MVT::isInteger(VT) == MVT::isInteger(EVT) &&
1017            "Cannot convert from FP to Int or Int -> FP!");
1018     break;
1019   }
1020
1021   EVTStruct NN;
1022   NN.Opcode = Opcode;
1023   NN.VT = VT;
1024   NN.EVT = EVT;
1025   NN.Ops.push_back(N1);
1026   NN.Ops.push_back(N2);
1027
1028   SDNode *&N = MVTSDNodes[NN];
1029   if (N) return SDOperand(N, 0);
1030   N = new MVTSDNode(Opcode, VT, MVT::Other, N1, N2, EVT);
1031   AllNodes.push_back(N);
1032   return SDOperand(N, 0);
1033 }
1034
1035 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1,
1036                                 SDOperand N2, SDOperand N3, MVT::ValueType EVT) {
1037   switch (Opcode) {
1038   default:  assert(0 && "Bad opcode for this accessor!");
1039   case ISD::TRUNCSTORE:
1040 #if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store
1041     // If this is a truncating store of a constant, convert to the desired type
1042     // and store it instead.
1043     if (isa<Constant>(N1)) {
1044       SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1);
1045       if (isa<Constant>(Op))
1046         N1 = Op;      
1047     }
1048     // Also for ConstantFP?
1049 #endif
1050     if (N1.getValueType() == EVT)       // Normal store?
1051       return getNode(ISD::STORE, VT, N1, N2, N3);
1052     assert(N2.getValueType() > EVT && "Not a truncation?");
1053     assert(MVT::isInteger(N2.getValueType()) == MVT::isInteger(EVT) &&
1054            "Can't do FP-INT conversion!");
1055     break;
1056   }
1057
1058   EVTStruct NN;
1059   NN.Opcode = Opcode;
1060   NN.VT = VT;
1061   NN.EVT = EVT;
1062   NN.Ops.push_back(N1);
1063   NN.Ops.push_back(N2);
1064   NN.Ops.push_back(N3);
1065
1066   SDNode *&N = MVTSDNodes[NN];
1067   if (N) return SDOperand(N, 0);
1068   N = new MVTSDNode(Opcode, VT, N1, N2, N3, EVT);
1069   AllNodes.push_back(N);
1070   return SDOperand(N, 0);
1071 }
1072
1073
1074 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
1075 /// indicated value.  This method ignores uses of other values defined by this
1076 /// operation.
1077 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) {
1078   assert(Value < getNumValues() && "Bad value!");
1079
1080   // If there is only one value, this is easy.
1081   if (getNumValues() == 1)
1082     return use_size() == NUses;
1083   if (Uses.size() < NUses) return false;
1084
1085   SDOperand TheValue(this, Value);
1086
1087   std::set<SDNode*> UsersHandled;
1088
1089   for (std::vector<SDNode*>::iterator UI = Uses.begin(), E = Uses.end();
1090        UI != E; ++UI) {
1091     SDNode *User = *UI;
1092     if (User->getNumOperands() == 1 ||
1093         UsersHandled.insert(User).second)     // First time we've seen this?
1094       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
1095         if (User->getOperand(i) == TheValue) {
1096           if (NUses == 0)
1097             return false;   // too many uses
1098           --NUses;
1099         }
1100   }
1101
1102   // Found exactly the right number of uses?
1103   return NUses == 0;
1104 }
1105
1106
1107 const char *SDNode::getOperationName() const {
1108   switch (getOpcode()) {
1109   default: return "<<Unknown>>";
1110   case ISD::PCMARKER:      return "PCMarker";
1111   case ISD::EntryToken:    return "EntryToken";
1112   case ISD::TokenFactor:   return "TokenFactor";
1113   case ISD::Constant:      return "Constant";
1114   case ISD::ConstantFP:    return "ConstantFP";
1115   case ISD::GlobalAddress: return "GlobalAddress";
1116   case ISD::FrameIndex:    return "FrameIndex";
1117   case ISD::BasicBlock:    return "BasicBlock";
1118   case ISD::ExternalSymbol: return "ExternalSymbol";
1119   case ISD::ConstantPool:  return "ConstantPoolIndex";
1120   case ISD::CopyToReg:     return "CopyToReg";
1121   case ISD::CopyFromReg:   return "CopyFromReg";
1122   case ISD::ImplicitDef:   return "ImplicitDef";
1123   case ISD::UNDEF:         return "undef";
1124
1125   // Unary operators
1126   case ISD::FABS:   return "fabs";
1127   case ISD::FNEG:   return "fneg";
1128
1129   // Binary operators
1130   case ISD::ADD:    return "add";
1131   case ISD::SUB:    return "sub";
1132   case ISD::MUL:    return "mul";
1133   case ISD::MULHU:  return "mulhu";
1134   case ISD::MULHS:  return "mulhs";
1135   case ISD::SDIV:   return "sdiv";
1136   case ISD::UDIV:   return "udiv";
1137   case ISD::SREM:   return "srem";
1138   case ISD::UREM:   return "urem";
1139   case ISD::AND:    return "and";
1140   case ISD::OR:     return "or";
1141   case ISD::XOR:    return "xor";
1142   case ISD::SHL:    return "shl";
1143   case ISD::SRA:    return "sra";
1144   case ISD::SRL:    return "srl";
1145
1146   case ISD::SELECT: return "select";
1147   case ISD::ADD_PARTS:   return "add_parts";
1148   case ISD::SUB_PARTS:   return "sub_parts";
1149   case ISD::SHL_PARTS:   return "shl_parts";
1150   case ISD::SRA_PARTS:   return "sra_parts";
1151   case ISD::SRL_PARTS:   return "srl_parts";
1152
1153     // Conversion operators.
1154   case ISD::SIGN_EXTEND: return "sign_extend";
1155   case ISD::ZERO_EXTEND: return "zero_extend";
1156   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
1157   case ISD::ZERO_EXTEND_INREG: return "zero_extend_inreg";
1158   case ISD::TRUNCATE:    return "truncate";
1159   case ISD::FP_ROUND:    return "fp_round";
1160   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
1161   case ISD::FP_EXTEND:   return "fp_extend";
1162
1163   case ISD::SINT_TO_FP:  return "sint_to_fp";
1164   case ISD::UINT_TO_FP:  return "uint_to_fp";
1165   case ISD::FP_TO_SINT:  return "fp_to_sint";
1166   case ISD::FP_TO_UINT:  return "fp_to_uint";
1167
1168     // Control flow instructions
1169   case ISD::BR:      return "br";
1170   case ISD::BRCOND:  return "brcond";
1171   case ISD::RET:     return "ret";
1172   case ISD::CALL:    return "call";
1173   case ISD::ADJCALLSTACKDOWN:  return "adjcallstackdown";
1174   case ISD::ADJCALLSTACKUP:    return "adjcallstackup";
1175
1176     // Other operators
1177   case ISD::LOAD:    return "load";
1178   case ISD::STORE:   return "store";
1179   case ISD::EXTLOAD:    return "extload";
1180   case ISD::SEXTLOAD:   return "sextload";
1181   case ISD::ZEXTLOAD:   return "zextload";
1182   case ISD::TRUNCSTORE: return "truncstore";
1183
1184   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
1185   case ISD::EXTRACT_ELEMENT: return "extract_element";
1186   case ISD::BUILD_PAIR: return "build_pair";
1187   case ISD::MEMSET:  return "memset";
1188   case ISD::MEMCPY:  return "memcpy";
1189   case ISD::MEMMOVE: return "memmove";
1190
1191   case ISD::SETCC:
1192     const SetCCSDNode *SetCC = cast<SetCCSDNode>(this);
1193     switch (SetCC->getCondition()) {
1194     default: assert(0 && "Unknown setcc condition!");
1195     case ISD::SETOEQ:  return "setcc:setoeq";
1196     case ISD::SETOGT:  return "setcc:setogt";
1197     case ISD::SETOGE:  return "setcc:setoge";
1198     case ISD::SETOLT:  return "setcc:setolt";
1199     case ISD::SETOLE:  return "setcc:setole";
1200     case ISD::SETONE:  return "setcc:setone";
1201       
1202     case ISD::SETO:    return "setcc:seto"; 
1203     case ISD::SETUO:   return "setcc:setuo";
1204     case ISD::SETUEQ:  return "setcc:setue";
1205     case ISD::SETUGT:  return "setcc:setugt";
1206     case ISD::SETUGE:  return "setcc:setuge";
1207     case ISD::SETULT:  return "setcc:setult";
1208     case ISD::SETULE:  return "setcc:setule";
1209     case ISD::SETUNE:  return "setcc:setune";
1210       
1211     case ISD::SETEQ:   return "setcc:seteq";
1212     case ISD::SETGT:   return "setcc:setgt";
1213     case ISD::SETGE:   return "setcc:setge";
1214     case ISD::SETLT:   return "setcc:setlt";
1215     case ISD::SETLE:   return "setcc:setle";
1216     case ISD::SETNE:   return "setcc:setne";
1217     }
1218   }
1219 }
1220
1221 void SDNode::dump() const {
1222   std::cerr << (void*)this << ": ";
1223
1224   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
1225     if (i) std::cerr << ",";
1226     if (getValueType(i) == MVT::Other)
1227       std::cerr << "ch";
1228     else
1229       std::cerr << MVT::getValueTypeString(getValueType(i));
1230   }
1231   std::cerr << " = " << getOperationName();
1232
1233   std::cerr << " ";
1234   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1235     if (i) std::cerr << ", ";
1236     std::cerr << (void*)getOperand(i).Val;
1237     if (unsigned RN = getOperand(i).ResNo)
1238       std::cerr << ":" << RN;
1239   }
1240
1241   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
1242     std::cerr << "<" << CSDN->getValue() << ">";
1243   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
1244     std::cerr << "<" << CSDN->getValue() << ">";
1245   } else if (const GlobalAddressSDNode *GADN = 
1246              dyn_cast<GlobalAddressSDNode>(this)) {
1247     std::cerr << "<";
1248     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
1249   } else if (const FrameIndexSDNode *FIDN =
1250              dyn_cast<FrameIndexSDNode>(this)) {
1251     std::cerr << "<" << FIDN->getIndex() << ">";
1252   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
1253     std::cerr << "<" << CP->getIndex() << ">";
1254   } else if (const BasicBlockSDNode *BBDN = 
1255              dyn_cast<BasicBlockSDNode>(this)) {
1256     std::cerr << "<";
1257     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
1258     if (LBB)
1259       std::cerr << LBB->getName() << " ";
1260     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
1261   } else if (const RegSDNode *C2V = dyn_cast<RegSDNode>(this)) {
1262     std::cerr << "<reg #" << C2V->getReg() << ">";
1263   } else if (const ExternalSymbolSDNode *ES =
1264              dyn_cast<ExternalSymbolSDNode>(this)) {
1265     std::cerr << "'" << ES->getSymbol() << "'";
1266   } else if (const MVTSDNode *M = dyn_cast<MVTSDNode>(this)) {
1267     std::cerr << " - Ty = " << MVT::getValueTypeString(M->getExtraValueType());
1268   }
1269 }
1270
1271 static void DumpNodes(SDNode *N, unsigned indent) {
1272   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1273     if (N->getOperand(i).Val->hasOneUse())
1274       DumpNodes(N->getOperand(i).Val, indent+2);
1275     else
1276       std::cerr << "\n" << std::string(indent+2, ' ')
1277                 << (void*)N->getOperand(i).Val << ": <multiple use>";
1278     
1279
1280   std::cerr << "\n" << std::string(indent, ' ');
1281   N->dump();
1282 }
1283
1284 void SelectionDAG::dump() const {
1285   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
1286   std::vector<SDNode*> Nodes(AllNodes);
1287   std::sort(Nodes.begin(), Nodes.end());
1288
1289   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
1290     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
1291       DumpNodes(Nodes[i], 2);
1292   }
1293
1294   DumpNodes(getRoot().Val, 2);
1295
1296   std::cerr << "\n\n";
1297 }
1298