SelectionDAG.cpp revision 079a27a0deca2501485da55701632cf9ebe4e8c4
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/Support/MathExtras.h"
20#include "llvm/Target/TargetLowering.h"
21#include <iostream>
22#include <set>
23#include <cmath>
24#include <algorithm>
25using namespace llvm;
26
27static bool isCommutativeBinOp(unsigned Opcode) {
28  switch (Opcode) {
29  case ISD::ADD:
30  case ISD::MUL:
31  case ISD::AND:
32  case ISD::OR:
33  case ISD::XOR: return true;
34  default: return false; // FIXME: Need commutative info for user ops!
35  }
36}
37
38static bool isAssociativeBinOp(unsigned Opcode) {
39  switch (Opcode) {
40  case ISD::ADD:
41  case ISD::MUL:
42  case ISD::AND:
43  case ISD::OR:
44  case ISD::XOR: return true;
45  default: return false; // FIXME: Need associative info for user ops!
46  }
47}
48
49// isInvertibleForFree - Return true if there is no cost to emitting the logical
50// inverse of this node.
51static bool isInvertibleForFree(SDOperand N) {
52  if (isa<ConstantSDNode>(N.Val)) return true;
53  if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse())
54    return true;
55  return false;
56}
57
58
59/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
60/// when given the operation for (X op Y).
61ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
62  // To perform this operation, we just need to swap the L and G bits of the
63  // operation.
64  unsigned OldL = (Operation >> 2) & 1;
65  unsigned OldG = (Operation >> 1) & 1;
66  return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
67                       (OldL << 1) |       // New G bit
68                       (OldG << 2));        // New L bit.
69}
70
71/// getSetCCInverse - Return the operation corresponding to !(X op Y), where
72/// 'op' is a valid SetCC operation.
73ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
74  unsigned Operation = Op;
75  if (isInteger)
76    Operation ^= 7;   // Flip L, G, E bits, but not U.
77  else
78    Operation ^= 15;  // Flip all of the condition bits.
79  if (Operation > ISD::SETTRUE2)
80    Operation &= ~8;     // Don't let N and U bits get set.
81  return ISD::CondCode(Operation);
82}
83
84
85/// isSignedOp - For an integer comparison, return 1 if the comparison is a
86/// signed operation and 2 if the result is an unsigned comparison.  Return zero
87/// if the operation does not depend on the sign of the input (setne and seteq).
88static int isSignedOp(ISD::CondCode Opcode) {
89  switch (Opcode) {
90  default: assert(0 && "Illegal integer setcc operation!");
91  case ISD::SETEQ:
92  case ISD::SETNE: return 0;
93  case ISD::SETLT:
94  case ISD::SETLE:
95  case ISD::SETGT:
96  case ISD::SETGE: return 1;
97  case ISD::SETULT:
98  case ISD::SETULE:
99  case ISD::SETUGT:
100  case ISD::SETUGE: return 2;
101  }
102}
103
104/// getSetCCOrOperation - Return the result of a logical OR between different
105/// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
106/// returns SETCC_INVALID if it is not possible to represent the resultant
107/// comparison.
108ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
109                                       bool isInteger) {
110  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
111    // Cannot fold a signed integer setcc with an unsigned integer setcc.
112    return ISD::SETCC_INVALID;
113
114  unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
115
116  // If the N and U bits get set then the resultant comparison DOES suddenly
117  // care about orderedness, and is true when ordered.
118  if (Op > ISD::SETTRUE2)
119    Op &= ~16;     // Clear the N bit.
120  return ISD::CondCode(Op);
121}
122
123/// getSetCCAndOperation - Return the result of a logical AND between different
124/// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
125/// function returns zero if it is not possible to represent the resultant
126/// comparison.
127ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
128                                        bool isInteger) {
129  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
130    // Cannot fold a signed setcc with an unsigned setcc.
131    return ISD::SETCC_INVALID;
132
133  // Combine all of the condition bits.
134  return ISD::CondCode(Op1 & Op2);
135}
136
137const TargetMachine &SelectionDAG::getTarget() const {
138  return TLI.getTargetMachine();
139}
140
141
142/// RemoveDeadNodes - This method deletes all unreachable nodes in the
143/// SelectionDAG, including nodes (like loads) that have uses of their token
144/// chain but no other uses and no side effect.  If a node is passed in as an
145/// argument, it is used as the seed for node deletion.
146void SelectionDAG::RemoveDeadNodes(SDNode *N) {
147  std::set<SDNode*> AllNodeSet(AllNodes.begin(), AllNodes.end());
148
149  // Create a dummy node (which is not added to allnodes), that adds a reference
150  // to the root node, preventing it from being deleted.
151  SDNode *DummyNode = new SDNode(ISD::EntryToken, getRoot());
152
153  DeleteNodeIfDead(N, &AllNodeSet);
154
155 Restart:
156  unsigned NumNodes = AllNodeSet.size();
157  for (std::set<SDNode*>::iterator I = AllNodeSet.begin(), E = AllNodeSet.end();
158       I != E; ++I) {
159    // Try to delete this node.
160    DeleteNodeIfDead(*I, &AllNodeSet);
161
162    // If we actually deleted any nodes, do not use invalid iterators in
163    // AllNodeSet.
164    if (AllNodeSet.size() != NumNodes)
165      goto Restart;
166  }
167
168  // Restore AllNodes.
169  if (AllNodes.size() != NumNodes)
170    AllNodes.assign(AllNodeSet.begin(), AllNodeSet.end());
171
172  // If the root changed (e.g. it was a dead load, update the root).
173  setRoot(DummyNode->getOperand(0));
174
175  // Now that we are done with the dummy node, delete it.
176  DummyNode->getOperand(0).Val->removeUser(DummyNode);
177  delete DummyNode;
178}
179
180void SelectionDAG::DeleteNodeIfDead(SDNode *N, void *NodeSet) {
181  if (!N->use_empty())
182    return;
183
184  // Okay, we really are going to delete this node.  First take this out of the
185  // appropriate CSE map.
186  switch (N->getOpcode()) {
187  case ISD::Constant:
188    Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
189                                   N->getValueType(0)));
190    break;
191  case ISD::ConstantFP: {
192    union {
193      double DV;
194      uint64_t IV;
195    };
196    DV = cast<ConstantFPSDNode>(N)->getValue();
197    ConstantFPs.erase(std::make_pair(IV, N->getValueType(0)));
198    break;
199  }
200  case ISD::CONDCODE:
201    assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
202           "Cond code doesn't exist!");
203    CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
204    break;
205  case ISD::GlobalAddress:
206    GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal());
207    break;
208  case ISD::FrameIndex:
209    FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
210    break;
211  case ISD::ConstantPool:
212    ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->getIndex());
213    break;
214  case ISD::BasicBlock:
215    BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
216    break;
217  case ISD::ExternalSymbol:
218    ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
219    break;
220  case ISD::VALUETYPE:
221    ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0;
222    break;
223  case ISD::SRCVALUE: {
224    SrcValueSDNode *SVN = cast<SrcValueSDNode>(N);
225    ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset()));
226    break;
227  }
228  case ISD::LOAD:
229    Loads.erase(std::make_pair(N->getOperand(1),
230                               std::make_pair(N->getOperand(0),
231                                              N->getValueType(0))));
232    break;
233  default:
234    if (N->getNumOperands() == 1)
235      UnaryOps.erase(std::make_pair(N->getOpcode(),
236                                    std::make_pair(N->getOperand(0),
237                                                   N->getValueType(0))));
238    else if (N->getNumOperands() == 2)
239      BinaryOps.erase(std::make_pair(N->getOpcode(),
240                                     std::make_pair(N->getOperand(0),
241                                                    N->getOperand(1))));
242    else if (N->getNumValues() == 1) {
243      std::vector<SDOperand> Ops(N->op_begin(), N->op_end());
244      OneResultNodes.erase(std::make_pair(N->getOpcode(),
245                                          std::make_pair(N->getValueType(0),
246                                                         Ops)));
247    } else {
248      // Remove the node from the ArbitraryNodes map.
249      std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
250      std::vector<SDOperand>     Ops(N->op_begin(), N->op_end());
251      ArbitraryNodes.erase(std::make_pair(N->getOpcode(),
252                                          std::make_pair(RV, Ops)));
253    }
254    break;
255  }
256
257  // Next, brutally remove the operand list.
258  while (!N->Operands.empty()) {
259    SDNode *O = N->Operands.back().Val;
260    N->Operands.pop_back();
261    O->removeUser(N);
262
263    // Now that we removed this operand, see if there are no uses of it left.
264    DeleteNodeIfDead(O, NodeSet);
265  }
266
267  // Remove the node from the nodes set and delete it.
268  std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet;
269  AllNodeSet.erase(N);
270
271  // Now that the node is gone, check to see if any of the operands of this node
272  // are dead now.
273  delete N;
274}
275
276
277SelectionDAG::~SelectionDAG() {
278  for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
279    delete AllNodes[i];
280}
281
282SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
283  if (Op.getValueType() == VT) return Op;
284  int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT));
285  return getNode(ISD::AND, Op.getValueType(), Op,
286                 getConstant(Imm, Op.getValueType()));
287}
288
289SDOperand 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
302SDOperand 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
326SDOperand 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
335SDOperand 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
343SDOperand 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
351SDOperand 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
359SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
360  if ((unsigned)VT >= ValueTypeNodes.size())
361    ValueTypeNodes.resize(VT+1);
362  if (ValueTypeNodes[VT] == 0) {
363    ValueTypeNodes[VT] = new VTSDNode(VT);
364    AllNodes.push_back(ValueTypeNodes[VT]);
365  }
366
367  return SDOperand(ValueTypeNodes[VT], 0);
368}
369
370SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
371  SDNode *&N = ExternalSymbols[Sym];
372  if (N) return SDOperand(N, 0);
373  N = new ExternalSymbolSDNode(Sym, VT);
374  AllNodes.push_back(N);
375  return SDOperand(N, 0);
376}
377
378SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
379  if ((unsigned)Cond >= CondCodeNodes.size())
380    CondCodeNodes.resize(Cond+1);
381
382  if (CondCodeNodes[Cond] == 0) {
383    CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
384    AllNodes.push_back(CondCodeNodes[Cond]);
385  }
386  return SDOperand(CondCodeNodes[Cond], 0);
387}
388
389SDOperand SelectionDAG::SimplfySetCC(MVT::ValueType VT, SDOperand N1,
390                                     SDOperand N2, ISD::CondCode Cond) {
391  // These setcc operations always fold.
392  switch (Cond) {
393  default: break;
394  case ISD::SETFALSE:
395  case ISD::SETFALSE2: return getConstant(0, VT);
396  case ISD::SETTRUE:
397  case ISD::SETTRUE2:  return getConstant(1, VT);
398  }
399
400  if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
401    uint64_t C2 = N2C->getValue();
402    if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
403      uint64_t C1 = N1C->getValue();
404
405      // Sign extend the operands if required
406      if (ISD::isSignedIntSetCC(Cond)) {
407        C1 = N1C->getSignExtended();
408        C2 = N2C->getSignExtended();
409      }
410
411      switch (Cond) {
412      default: assert(0 && "Unknown integer setcc!");
413      case ISD::SETEQ:  return getConstant(C1 == C2, VT);
414      case ISD::SETNE:  return getConstant(C1 != C2, VT);
415      case ISD::SETULT: return getConstant(C1 <  C2, VT);
416      case ISD::SETUGT: return getConstant(C1 >  C2, VT);
417      case ISD::SETULE: return getConstant(C1 <= C2, VT);
418      case ISD::SETUGE: return getConstant(C1 >= C2, VT);
419      case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
420      case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
421      case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
422      case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
423      }
424    } else {
425      // If the LHS is a ZERO_EXTEND and if this is an ==/!= comparison, perform
426      // the comparison on the input.
427      if (N1.getOpcode() == ISD::ZERO_EXTEND) {
428        unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType());
429
430        // If the comparison constant has bits in the upper part, the
431        // zero-extended value could never match.
432        if (C2 & (~0ULL << InSize)) {
433          unsigned VSize = MVT::getSizeInBits(N1.getValueType());
434          switch (Cond) {
435          case ISD::SETUGT:
436          case ISD::SETUGE:
437          case ISD::SETEQ: return getConstant(0, VT);
438          case ISD::SETULT:
439          case ISD::SETULE:
440          case ISD::SETNE: return getConstant(1, VT);
441          case ISD::SETGT:
442          case ISD::SETGE:
443            // True if the sign bit of C2 is set.
444            return getConstant((C2 & (1ULL << VSize)) != 0, VT);
445          case ISD::SETLT:
446          case ISD::SETLE:
447            // True if the sign bit of C2 isn't set.
448            return getConstant((C2 & (1ULL << VSize)) == 0, VT);
449          default:
450            break;
451          }
452        }
453
454        // Otherwise, we can perform the comparison with the low bits.
455        switch (Cond) {
456        case ISD::SETEQ:
457        case ISD::SETNE:
458        case ISD::SETUGT:
459        case ISD::SETUGE:
460        case ISD::SETULT:
461        case ISD::SETULE:
462          return getSetCC(VT, N1.getOperand(0),
463                          getConstant(C2, N1.getOperand(0).getValueType()),
464                          Cond);
465        default:
466          break;   // todo, be more careful with signed comparisons
467        }
468      }
469
470      uint64_t MinVal, MaxVal;
471      unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0));
472      if (ISD::isSignedIntSetCC(Cond)) {
473        MinVal = 1ULL << (OperandBitSize-1);
474        if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
475          MaxVal = ~0ULL >> (65-OperandBitSize);
476        else
477          MaxVal = 0;
478      } else {
479        MinVal = 0;
480        MaxVal = ~0ULL >> (64-OperandBitSize);
481      }
482
483      // Canonicalize GE/LE comparisons to use GT/LT comparisons.
484      if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
485        if (C2 == MinVal) return getConstant(1, VT);   // X >= MIN --> true
486        --C2;                                          // X >= C1 --> X > (C1-1)
487        Cond = (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT;
488        N2 = getConstant(C2, N2.getValueType());
489        N2C = cast<ConstantSDNode>(N2.Val);
490      }
491
492      if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
493        if (C2 == MaxVal) return getConstant(1, VT);   // X <= MAX --> true
494        ++C2;                                          // X <= C1 --> X < (C1+1)
495        Cond = (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT;
496        N2 = getConstant(C2, N2.getValueType());
497        N2C = cast<ConstantSDNode>(N2.Val);
498      }
499
500      if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal)
501        return getConstant(0, VT);      // X < MIN --> false
502
503      // Canonicalize setgt X, Min --> setne X, Min
504      if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal)
505        return getSetCC(VT, N1, N2, ISD::SETNE);
506
507      // If we have setult X, 1, turn it into seteq X, 0
508      if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1)
509        return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()),
510                        ISD::SETEQ);
511      // If we have setugt X, Max-1, turn it into seteq X, Max
512      else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1)
513        return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()),
514                        ISD::SETEQ);
515
516      // If we have "setcc X, C1", check to see if we can shrink the immediate
517      // by changing cc.
518
519      // SETUGT X, SINTMAX  -> SETLT X, 0
520      if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
521          C2 == (~0ULL >> (65-OperandBitSize)))
522        return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT);
523
524      // FIXME: Implement the rest of these.
525
526
527      // Fold bit comparisons when we can.
528      if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
529          VT == N1.getValueType() && N1.getOpcode() == ISD::AND)
530        if (ConstantSDNode *AndRHS =
531                    dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
532          if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
533            // Perform the xform if the AND RHS is a single bit.
534            if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
535              return getNode(ISD::SRL, VT, N1,
536                             getConstant(Log2_64(AndRHS->getValue()),
537                                                   TLI.getShiftAmountTy()));
538            }
539          } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) {
540            // (X & 8) == 8  -->  (X & 8) >> 3
541            // Perform the xform if C2 is a single bit.
542            if ((C2 & (C2-1)) == 0) {
543              return getNode(ISD::SRL, VT, N1,
544                             getConstant(Log2_64(C2),TLI.getShiftAmountTy()));
545            }
546          }
547        }
548    }
549  } else if (isa<ConstantSDNode>(N1.Val)) {
550      // Ensure that the constant occurs on the RHS.
551    return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
552  }
553
554  if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
555    if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
556      double C1 = N1C->getValue(), C2 = N2C->getValue();
557
558      switch (Cond) {
559      default: break; // FIXME: Implement the rest of these!
560      case ISD::SETEQ:  return getConstant(C1 == C2, VT);
561      case ISD::SETNE:  return getConstant(C1 != C2, VT);
562      case ISD::SETLT:  return getConstant(C1 < C2, VT);
563      case ISD::SETGT:  return getConstant(C1 > C2, VT);
564      case ISD::SETLE:  return getConstant(C1 <= C2, VT);
565      case ISD::SETGE:  return getConstant(C1 >= C2, VT);
566      }
567    } else {
568      // Ensure that the constant occurs on the RHS.
569      Cond = ISD::getSetCCSwappedOperands(Cond);
570      std::swap(N1, N2);
571    }
572
573  if (N1 == N2) {
574    // We can always fold X == Y for integer setcc's.
575    if (MVT::isInteger(N1.getValueType()))
576      return getConstant(ISD::isTrueWhenEqual(Cond), VT);
577    unsigned UOF = ISD::getUnorderedFlavor(Cond);
578    if (UOF == 2)   // FP operators that are undefined on NaNs.
579      return getConstant(ISD::isTrueWhenEqual(Cond), VT);
580    if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
581      return getConstant(UOF, VT);
582    // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
583    // if it is not already.
584    Cond = UOF == 0 ? ISD::SETUO : ISD::SETO;
585  }
586
587  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
588      MVT::isInteger(N1.getValueType())) {
589    if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
590        N1.getOpcode() == ISD::XOR) {
591      // Simplify (X+Y) == (X+Z) -->  Y == Z
592      if (N1.getOpcode() == N2.getOpcode()) {
593        if (N1.getOperand(0) == N2.getOperand(0))
594          return getSetCC(VT, N1.getOperand(1), N2.getOperand(1), Cond);
595        if (N1.getOperand(1) == N2.getOperand(1))
596          return getSetCC(VT, N1.getOperand(0), N2.getOperand(0), Cond);
597        if (isCommutativeBinOp(N1.getOpcode())) {
598          // If X op Y == Y op X, try other combinations.
599          if (N1.getOperand(0) == N2.getOperand(1))
600            return getSetCC(VT, N1.getOperand(1), N2.getOperand(0), Cond);
601          if (N1.getOperand(1) == N2.getOperand(0))
602            return getSetCC(VT, N1.getOperand(1), N2.getOperand(1), Cond);
603        }
604      }
605
606      // FIXME: move this stuff to the DAG Combiner when it exists!
607
608      // Simplify (X+Z) == X -->  Z == 0
609      if (N1.getOperand(0) == N2)
610        return getSetCC(VT, N1.getOperand(1),
611                        getConstant(0, N1.getValueType()), Cond);
612      if (N1.getOperand(1) == N2) {
613        if (isCommutativeBinOp(N1.getOpcode()))
614          return getSetCC(VT, N1.getOperand(0),
615                          getConstant(0, N1.getValueType()), Cond);
616        else {
617          assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
618          // (Z-X) == X  --> Z == X<<1
619          return getSetCC(VT, N1.getOperand(0),
620                          getNode(ISD::SHL, N2.getValueType(),
621                                  N2, getConstant(1, TLI.getShiftAmountTy())),
622                          Cond);
623        }
624      }
625    }
626
627    if (N2.getOpcode() == ISD::ADD || N2.getOpcode() == ISD::SUB ||
628        N2.getOpcode() == ISD::XOR) {
629      // Simplify  X == (X+Z) -->  Z == 0
630      if (N2.getOperand(0) == N1)
631        return getSetCC(VT, N2.getOperand(1),
632                        getConstant(0, N2.getValueType()), Cond);
633      else if (N2.getOperand(1) == N1)
634        return getSetCC(VT, N2.getOperand(0), getConstant(0, N2.getValueType()),
635                        Cond);
636    }
637  }
638
639  // Fold away ALL boolean setcc's.
640  if (N1.getValueType() == MVT::i1) {
641    switch (Cond) {
642    default: assert(0 && "Unknown integer setcc!");
643    case ISD::SETEQ:  // X == Y  -> (X^Y)^1
644      N1 = getNode(ISD::XOR, MVT::i1,
645                   getNode(ISD::XOR, MVT::i1, N1, N2),
646                   getConstant(1, MVT::i1));
647      break;
648    case ISD::SETNE:  // X != Y   -->  (X^Y)
649      N1 = getNode(ISD::XOR, MVT::i1, N1, N2);
650      break;
651    case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  X^1 & Y
652    case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  X^1 & Y
653      N1 = getNode(ISD::AND, MVT::i1, N2,
654                   getNode(ISD::XOR, MVT::i1, N1, getConstant(1, MVT::i1)));
655      break;
656    case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  Y^1 & X
657    case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  Y^1 & X
658      N1 = getNode(ISD::AND, MVT::i1, N1,
659                   getNode(ISD::XOR, MVT::i1, N2, getConstant(1, MVT::i1)));
660      break;
661    case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  X^1 | Y
662    case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  X^1 | Y
663      N1 = getNode(ISD::OR, MVT::i1, N2,
664                   getNode(ISD::XOR, MVT::i1, N1, getConstant(1, MVT::i1)));
665      break;
666    case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  Y^1 | X
667    case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  Y^1 | X
668      N1 = getNode(ISD::OR, MVT::i1, N1,
669                   getNode(ISD::XOR, MVT::i1, N2, getConstant(1, MVT::i1)));
670      break;
671    }
672    if (VT != MVT::i1)
673      N1 = getNode(ISD::ZERO_EXTEND, VT, N1);
674    return N1;
675  }
676
677  // Could not fold it.
678  return SDOperand();
679}
680
681
682
683/// getNode - Gets or creates the specified node.
684///
685SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
686  SDNode *N = new SDNode(Opcode, VT);
687  AllNodes.push_back(N);
688  return SDOperand(N, 0);
689}
690
691SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
692                                SDOperand Operand) {
693  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
694    uint64_t Val = C->getValue();
695    switch (Opcode) {
696    default: break;
697    case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
698    case ISD::ZERO_EXTEND: return getConstant(Val, VT);
699    case ISD::TRUNCATE:    return getConstant(Val, VT);
700    case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
701    case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
702    }
703  }
704
705  if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
706    switch (Opcode) {
707    case ISD::FNEG:
708      return getConstantFP(-C->getValue(), VT);
709    case ISD::FP_ROUND:
710    case ISD::FP_EXTEND:
711      return getConstantFP(C->getValue(), VT);
712    case ISD::FP_TO_SINT:
713      return getConstant((int64_t)C->getValue(), VT);
714    case ISD::FP_TO_UINT:
715      return getConstant((uint64_t)C->getValue(), VT);
716    }
717
718  unsigned OpOpcode = Operand.Val->getOpcode();
719  switch (Opcode) {
720  case ISD::TokenFactor:
721    return Operand;         // Factor of one node?  No factor.
722  case ISD::SIGN_EXTEND:
723    if (Operand.getValueType() == VT) return Operand;   // noop extension
724    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
725      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
726    break;
727  case ISD::ZERO_EXTEND:
728    if (Operand.getValueType() == VT) return Operand;   // noop extension
729    if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
730      return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
731    break;
732  case ISD::TRUNCATE:
733    if (Operand.getValueType() == VT) return Operand;   // noop truncate
734    if (OpOpcode == ISD::TRUNCATE)
735      return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
736    else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) {
737      // If the source is smaller than the dest, we still need an extend.
738      if (Operand.Val->getOperand(0).getValueType() < VT)
739        return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
740      else if (Operand.Val->getOperand(0).getValueType() > VT)
741        return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
742      else
743        return Operand.Val->getOperand(0);
744    }
745    break;
746  case ISD::FNEG:
747    if (OpOpcode == ISD::SUB)   // -(X-Y) -> (Y-X)
748      return getNode(ISD::SUB, VT, Operand.Val->getOperand(1),
749                     Operand.Val->getOperand(0));
750    if (OpOpcode == ISD::FNEG)  // --X -> X
751      return Operand.Val->getOperand(0);
752    break;
753  case ISD::FABS:
754    if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
755      return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
756    break;
757  }
758
759  SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
760  if (N) return SDOperand(N, 0);
761  N = new SDNode(Opcode, Operand);
762  N->setValueTypes(VT);
763  AllNodes.push_back(N);
764  return SDOperand(N, 0);
765}
766
767/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
768/// this predicate to simplify operations downstream.  V and Mask are known to
769/// be the same type.
770static bool MaskedValueIsZero(const SDOperand &Op, uint64_t Mask,
771                              const TargetLowering &TLI) {
772  unsigned SrcBits;
773  if (Mask == 0) return true;
774
775  // If we know the result of a setcc has the top bits zero, use this info.
776  switch (Op.getOpcode()) {
777  case ISD::Constant:
778    return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0;
779
780  case ISD::SETCC:
781    return ((Mask & 1) == 0) &&
782           TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult;
783
784  case ISD::ZEXTLOAD:
785    SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
786    return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
787  case ISD::ZERO_EXTEND:
788    SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType());
789    return MaskedValueIsZero(Op.getOperand(0),Mask & ((1ULL << SrcBits)-1),TLI);
790
791  case ISD::AND:
792    // (X & C1) & C2 == 0   iff   C1 & C2 == 0.
793    if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
794      return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask, TLI);
795
796    // FALL THROUGH
797  case ISD::OR:
798  case ISD::XOR:
799    return MaskedValueIsZero(Op.getOperand(0), Mask, TLI) &&
800           MaskedValueIsZero(Op.getOperand(1), Mask, TLI);
801  case ISD::SELECT:
802    return MaskedValueIsZero(Op.getOperand(1), Mask, TLI) &&
803           MaskedValueIsZero(Op.getOperand(2), Mask, TLI);
804
805  case ISD::SRL:
806    // (ushr X, C1) & C2 == 0   iff  X & (C2 << C1) == 0
807    if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
808      uint64_t NewVal = Mask << ShAmt->getValue();
809      SrcBits = MVT::getSizeInBits(Op.getValueType());
810      if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1;
811      return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
812    }
813    return false;
814  case ISD::SHL:
815    // (ushl X, C1) & C2 == 0   iff  X & (C2 >> C1) == 0
816    if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
817      uint64_t NewVal = Mask >> ShAmt->getValue();
818      return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
819    }
820    return false;
821    // TODO we could handle some SRA cases here.
822  default: break;
823  }
824
825  return false;
826}
827
828
829
830SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
831                                SDOperand N1, SDOperand N2) {
832#ifndef NDEBUG
833  switch (Opcode) {
834  case ISD::TokenFactor:
835    assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
836           N2.getValueType() == MVT::Other && "Invalid token factor!");
837    break;
838  case ISD::AND:
839  case ISD::OR:
840  case ISD::XOR:
841  case ISD::UDIV:
842  case ISD::UREM:
843  case ISD::MULHU:
844  case ISD::MULHS:
845    assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
846    // fall through
847  case ISD::ADD:
848  case ISD::SUB:
849  case ISD::MUL:
850  case ISD::SDIV:
851  case ISD::SREM:
852    assert(N1.getValueType() == N2.getValueType() &&
853           N1.getValueType() == VT && "Binary operator types must match!");
854    break;
855
856  case ISD::SHL:
857  case ISD::SRA:
858  case ISD::SRL:
859    assert(VT == N1.getValueType() &&
860           "Shift operators return type must be the same as their first arg");
861    assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
862           VT != MVT::i1 && "Shifts only work on integers");
863    break;
864  case ISD::FP_ROUND_INREG: {
865    MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
866    assert(VT == N1.getValueType() && "Not an inreg round!");
867    assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
868           "Cannot FP_ROUND_INREG integer types");
869    assert(EVT <= VT && "Not rounding down!");
870    break;
871  }
872  case ISD::SIGN_EXTEND_INREG: {
873    MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
874    assert(VT == N1.getValueType() && "Not an inreg extend!");
875    assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
876           "Cannot *_EXTEND_INREG FP types");
877    assert(EVT <= VT && "Not extending!");
878  }
879
880  default: break;
881  }
882#endif
883
884  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
885  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
886  if (N1C) {
887    if (N2C) {
888      uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
889      switch (Opcode) {
890      case ISD::ADD: return getConstant(C1 + C2, VT);
891      case ISD::SUB: return getConstant(C1 - C2, VT);
892      case ISD::MUL: return getConstant(C1 * C2, VT);
893      case ISD::UDIV:
894        if (C2) return getConstant(C1 / C2, VT);
895        break;
896      case ISD::UREM :
897        if (C2) return getConstant(C1 % C2, VT);
898        break;
899      case ISD::SDIV :
900        if (C2) return getConstant(N1C->getSignExtended() /
901                                   N2C->getSignExtended(), VT);
902        break;
903      case ISD::SREM :
904        if (C2) return getConstant(N1C->getSignExtended() %
905                                   N2C->getSignExtended(), VT);
906        break;
907      case ISD::AND  : return getConstant(C1 & C2, VT);
908      case ISD::OR   : return getConstant(C1 | C2, VT);
909      case ISD::XOR  : return getConstant(C1 ^ C2, VT);
910      case ISD::SHL  : return getConstant(C1 << (int)C2, VT);
911      case ISD::SRL  : return getConstant(C1 >> (unsigned)C2, VT);
912      case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
913      default: break;
914      }
915
916    } else {      // Cannonicalize constant to RHS if commutative
917      if (isCommutativeBinOp(Opcode)) {
918        std::swap(N1C, N2C);
919        std::swap(N1, N2);
920      }
921    }
922
923    switch (Opcode) {
924    default: break;
925    case ISD::SHL:    // shl  0, X -> 0
926      if (N1C->isNullValue()) return N1;
927      break;
928    case ISD::SRL:    // srl  0, X -> 0
929      if (N1C->isNullValue()) return N1;
930      break;
931    case ISD::SRA:    // sra -1, X -> -1
932      if (N1C->isAllOnesValue()) return N1;
933      break;
934    case ISD::SIGN_EXTEND_INREG:  // SIGN_EXTEND_INREG N1C, EVT
935      // Extending a constant?  Just return the extended constant.
936      SDOperand Tmp = getNode(ISD::TRUNCATE, cast<VTSDNode>(N2)->getVT(), N1);
937      return getNode(ISD::SIGN_EXTEND, VT, Tmp);
938    }
939  }
940
941  if (N2C) {
942    uint64_t C2 = N2C->getValue();
943
944    switch (Opcode) {
945    case ISD::ADD:
946      if (!C2) return N1;         // add X, 0 -> X
947      break;
948    case ISD::SUB:
949      if (!C2) return N1;         // sub X, 0 -> X
950      return getNode(ISD::ADD, VT, N1, getConstant(-C2, VT));
951    case ISD::MUL:
952      if (!C2) return N2;         // mul X, 0 -> 0
953      if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X
954        return getNode(ISD::SUB, VT, getConstant(0, VT), N1);
955
956      // FIXME: Move this to the DAG combiner when it exists.
957      if ((C2 & C2-1) == 0) {
958        SDOperand ShAmt = getConstant(Log2_64(C2), TLI.getShiftAmountTy());
959        return getNode(ISD::SHL, VT, N1, ShAmt);
960      }
961      break;
962
963    case ISD::MULHU:
964    case ISD::MULHS:
965      if (!C2) return N2;         // mul X, 0 -> 0
966
967      if (C2 == 1)                // 0X*01 -> 0X  hi(0X) == 0
968        return getConstant(0, VT);
969
970      // Many others could be handled here, including -1, powers of 2, etc.
971      break;
972
973    case ISD::UDIV:
974      // FIXME: Move this to the DAG combiner when it exists.
975      if ((C2 & C2-1) == 0 && C2) {
976        SDOperand ShAmt = getConstant(Log2_64(C2), TLI.getShiftAmountTy());
977        return getNode(ISD::SRL, VT, N1, ShAmt);
978      }
979      break;
980
981    case ISD::SHL:
982    case ISD::SRL:
983    case ISD::SRA:
984      // If the shift amount is bigger than the size of the data, then all the
985      // bits are shifted out.  Simplify to undef.
986      if (C2 >= MVT::getSizeInBits(N1.getValueType())) {
987        return getNode(ISD::UNDEF, N1.getValueType());
988      }
989      if (C2 == 0) return N1;
990
991      if (Opcode == ISD::SHL && N1.getNumOperands() == 2)
992        if (ConstantSDNode *OpSA = dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
993          unsigned OpSAC = OpSA->getValue();
994          if (N1.getOpcode() == ISD::SHL) {
995            if (C2+OpSAC >= MVT::getSizeInBits(N1.getValueType()))
996              return getConstant(0, N1.getValueType());
997            return getNode(ISD::SHL, N1.getValueType(), N1.getOperand(0),
998                           getConstant(C2+OpSAC, N2.getValueType()));
999          } else if (N1.getOpcode() == ISD::SRL) {
1000            // (X >> C1) << C2:  if C2 > C1, ((X & ~0<<C1) << C2-C1)
1001            SDOperand Mask = getNode(ISD::AND, VT, N1.getOperand(0),
1002                                     getConstant(~0ULL << OpSAC, VT));
1003            if (C2 > OpSAC) {
1004              return getNode(ISD::SHL, VT, Mask,
1005                             getConstant(C2-OpSAC, N2.getValueType()));
1006            } else {
1007              // (X >> C1) << C2:  if C2 <= C1, ((X & ~0<<C1) >> C1-C2)
1008              return getNode(ISD::SRL, VT, Mask,
1009                             getConstant(OpSAC-C2, N2.getValueType()));
1010            }
1011          } else if (N1.getOpcode() == ISD::SRA) {
1012            // if C1 == C2, just mask out low bits.
1013            if (C2 == OpSAC)
1014              return getNode(ISD::AND, VT, N1.getOperand(0),
1015                             getConstant(~0ULL << C2, VT));
1016          }
1017        }
1018      break;
1019
1020    case ISD::AND:
1021      if (!C2) return N2;         // X and 0 -> 0
1022      if (N2C->isAllOnesValue())
1023        return N1;                // X and -1 -> X
1024
1025      if (MaskedValueIsZero(N1, C2, TLI))  // X and 0 -> 0
1026        return getConstant(0, VT);
1027
1028      {
1029        uint64_t NotC2 = ~C2;
1030        if (VT != MVT::i64)
1031          NotC2 &= (1ULL << MVT::getSizeInBits(VT))-1;
1032
1033        if (MaskedValueIsZero(N1, NotC2, TLI))
1034          return N1;                // if (X & ~C2) -> 0, the and is redundant
1035      }
1036
1037      // FIXME: Should add a corresponding version of this for
1038      // ZERO_EXTEND/SIGN_EXTEND by converting them to an ANY_EXTEND node which
1039      // we don't have yet.
1040
1041      // and (sign_extend_inreg x:16:32), 1 -> and x, 1
1042      if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
1043        // If we are masking out the part of our input that was extended, just
1044        // mask the input to the extension directly.
1045        unsigned ExtendBits =
1046          MVT::getSizeInBits(cast<VTSDNode>(N1.getOperand(1))->getVT());
1047        if ((C2 & (~0ULL << ExtendBits)) == 0)
1048          return getNode(ISD::AND, VT, N1.getOperand(0), N2);
1049      } else if (N1.getOpcode() == ISD::OR) {
1050        if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N1.getOperand(1)))
1051          if ((ORI->getValue() & C2) == C2) {
1052            // If the 'or' is setting all of the bits that we are masking for,
1053            // we know the result of the AND will be the AND mask itself.
1054            return N2;
1055          }
1056      }
1057      break;
1058    case ISD::OR:
1059      if (!C2)return N1;          // X or 0 -> X
1060      if (N2C->isAllOnesValue())
1061        return N2;                // X or -1 -> -1
1062      break;
1063    case ISD::XOR:
1064      if (!C2) return N1;        // X xor 0 -> X
1065      if (N2C->isAllOnesValue()) {
1066        if (N1.Val->getOpcode() == ISD::SETCC){
1067          SDNode *SetCC = N1.Val;
1068          // !(X op Y) -> (X !op Y)
1069          bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
1070          ISD::CondCode CC = cast<CondCodeSDNode>(SetCC->getOperand(2))->get();
1071          return getSetCC(SetCC->getValueType(0),
1072                          SetCC->getOperand(0), SetCC->getOperand(1),
1073                          ISD::getSetCCInverse(CC, isInteger));
1074        } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
1075          SDNode *Op = N1.Val;
1076          // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
1077          // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
1078          SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
1079          if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
1080            LHS = getNode(ISD::XOR, VT, LHS, N2);  // RHS = ~LHS
1081            RHS = getNode(ISD::XOR, VT, RHS, N2);  // RHS = ~RHS
1082            if (Op->getOpcode() == ISD::AND)
1083              return getNode(ISD::OR, VT, LHS, RHS);
1084            return getNode(ISD::AND, VT, LHS, RHS);
1085          }
1086        }
1087        // X xor -1 -> not(x)  ?
1088      }
1089      break;
1090    }
1091
1092    // Reassociate ((X op C1) op C2) if possible.
1093    if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
1094      if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
1095        return getNode(Opcode, VT, N1.Val->getOperand(0),
1096                       getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
1097  }
1098
1099  ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
1100  ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
1101  if (N1CFP) {
1102    if (N2CFP) {
1103      double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
1104      switch (Opcode) {
1105      case ISD::ADD: return getConstantFP(C1 + C2, VT);
1106      case ISD::SUB: return getConstantFP(C1 - C2, VT);
1107      case ISD::MUL: return getConstantFP(C1 * C2, VT);
1108      case ISD::SDIV:
1109        if (C2) return getConstantFP(C1 / C2, VT);
1110        break;
1111      case ISD::SREM :
1112        if (C2) return getConstantFP(fmod(C1, C2), VT);
1113        break;
1114      default: break;
1115      }
1116
1117    } else {      // Cannonicalize constant to RHS if commutative
1118      if (isCommutativeBinOp(Opcode)) {
1119        std::swap(N1CFP, N2CFP);
1120        std::swap(N1, N2);
1121      }
1122    }
1123
1124    if (Opcode == ISD::FP_ROUND_INREG)
1125      return getNode(ISD::FP_EXTEND, VT,
1126                     getNode(ISD::FP_ROUND, cast<VTSDNode>(N2)->getVT(), N1));
1127  }
1128
1129  // Finally, fold operations that do not require constants.
1130  switch (Opcode) {
1131  case ISD::TokenFactor:
1132    if (N1.getOpcode() == ISD::EntryToken)
1133      return N2;
1134    if (N2.getOpcode() == ISD::EntryToken)
1135      return N1;
1136    break;
1137
1138  case ISD::AND:
1139  case ISD::OR:
1140    if (N1.Val->getOpcode() == ISD::SETCC && N2.Val->getOpcode() == ISD::SETCC){
1141      SDNode *LHS = N1.Val, *RHS = N2.Val;
1142      SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
1143      SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
1144      ISD::CondCode Op1 = cast<CondCodeSDNode>(LHS->getOperand(2))->get();
1145      ISD::CondCode Op2 = cast<CondCodeSDNode>(RHS->getOperand(2))->get();
1146
1147      if (LR == RR && isa<ConstantSDNode>(LR) &&
1148          Op2 == Op1 && MVT::isInteger(LL.getValueType())) {
1149        // (X != 0) | (Y != 0) -> (X|Y != 0)
1150        // (X == 0) & (Y == 0) -> (X|Y == 0)
1151        // (X <  0) | (Y <  0) -> (X|Y < 0)
1152        if (cast<ConstantSDNode>(LR)->getValue() == 0 &&
1153            ((Op2 == ISD::SETEQ && Opcode == ISD::AND) ||
1154             (Op2 == ISD::SETNE && Opcode == ISD::OR) ||
1155             (Op2 == ISD::SETLT && Opcode == ISD::OR)))
1156          return getSetCC(VT, getNode(ISD::OR, LR.getValueType(), LL, RL), LR,
1157                          Op2);
1158
1159        if (cast<ConstantSDNode>(LR)->isAllOnesValue()) {
1160          // (X == -1) & (Y == -1) -> (X&Y == -1)
1161          // (X != -1) | (Y != -1) -> (X&Y != -1)
1162          // (X >  -1) | (Y >  -1) -> (X&Y >  -1)
1163          if ((Opcode == ISD::AND && Op2 == ISD::SETEQ) ||
1164              (Opcode == ISD::OR  && Op2 == ISD::SETNE) ||
1165              (Opcode == ISD::OR  && Op2 == ISD::SETGT))
1166            return getSetCC(VT, getNode(ISD::AND, LR.getValueType(), LL, RL),
1167                            LR, Op2);
1168          // (X >  -1) & (Y >  -1) -> (X|Y > -1)
1169          if (Opcode == ISD::AND && Op2 == ISD::SETGT)
1170            return getSetCC(VT, getNode(ISD::OR, LR.getValueType(), LL, RL),
1171                            LR, Op2);
1172        }
1173      }
1174
1175      // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
1176      if (LL == RR && LR == RL) {
1177        Op2 = ISD::getSetCCSwappedOperands(Op2);
1178        goto MatchedBackwards;
1179      }
1180
1181      if (LL == RL && LR == RR) {
1182      MatchedBackwards:
1183        ISD::CondCode Result;
1184        bool isInteger = MVT::isInteger(LL.getValueType());
1185        if (Opcode == ISD::OR)
1186          Result = ISD::getSetCCOrOperation(Op1, Op2, isInteger);
1187        else
1188          Result = ISD::getSetCCAndOperation(Op1, Op2, isInteger);
1189
1190        if (Result != ISD::SETCC_INVALID)
1191          return getSetCC(LHS->getValueType(0), LL, LR, Result);
1192      }
1193    }
1194
1195    // and/or zext(a), zext(b) -> zext(and/or a, b)
1196    if (N1.getOpcode() == ISD::ZERO_EXTEND &&
1197        N2.getOpcode() == ISD::ZERO_EXTEND &&
1198        N1.getOperand(0).getValueType() == N2.getOperand(0).getValueType())
1199      return getNode(ISD::ZERO_EXTEND, VT,
1200                     getNode(Opcode, N1.getOperand(0).getValueType(),
1201                             N1.getOperand(0), N2.getOperand(0)));
1202    break;
1203  case ISD::XOR:
1204    if (N1 == N2) return getConstant(0, VT);  // xor X, Y -> 0
1205    break;
1206  case ISD::ADD:
1207    if (N2.getOpcode() == ISD::FNEG)          // (A+ (-B) -> A-B
1208      return getNode(ISD::SUB, VT, N1, N2.getOperand(0));
1209    if (N1.getOpcode() == ISD::FNEG)          // ((-A)+B) -> B-A
1210      return getNode(ISD::SUB, VT, N2, N1.getOperand(0));
1211    if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) &&
1212        cast<ConstantSDNode>(N1.getOperand(0))->getValue() == 0)
1213      return getNode(ISD::SUB, VT, N2, N1.getOperand(1)); // (0-A)+B -> B-A
1214    if (N2.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N2.getOperand(0)) &&
1215        cast<ConstantSDNode>(N2.getOperand(0))->getValue() == 0)
1216      return getNode(ISD::SUB, VT, N1, N2.getOperand(1)); // A+(0-B) -> A-B
1217    if (N2.getOpcode() == ISD::SUB && N1 == N2.Val->getOperand(1) &&
1218        !MVT::isFloatingPoint(N2.getValueType()))
1219      return N2.Val->getOperand(0); // A+(B-A) -> B
1220    break;
1221  case ISD::SUB:
1222    if (N1.getOpcode() == ISD::ADD) {
1223      if (N1.Val->getOperand(0) == N2 &&
1224          !MVT::isFloatingPoint(N2.getValueType()))
1225        return N1.Val->getOperand(1);         // (A+B)-A == B
1226      if (N1.Val->getOperand(1) == N2 &&
1227          !MVT::isFloatingPoint(N2.getValueType()))
1228        return N1.Val->getOperand(0);         // (A+B)-B == A
1229    }
1230    if (N2.getOpcode() == ISD::FNEG)          // (A- (-B) -> A+B
1231      return getNode(ISD::ADD, VT, N1, N2.getOperand(0));
1232    break;
1233  case ISD::FP_ROUND_INREG:
1234    if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
1235    break;
1236  case ISD::SIGN_EXTEND_INREG: {
1237    MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1238    if (EVT == VT) return N1;  // Not actually extending
1239
1240    // If we are sign extending an extension, use the original source.
1241    if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG)
1242      if (cast<VTSDNode>(N1.getOperand(1))->getVT() <= EVT)
1243        return N1;
1244
1245    // If we are sign extending a sextload, return just the load.
1246    if (N1.getOpcode() == ISD::SEXTLOAD)
1247      if (cast<VTSDNode>(N1.getOperand(3))->getVT() <= EVT)
1248        return N1;
1249
1250    // If we are extending the result of a setcc, and we already know the
1251    // contents of the top bits, eliminate the extension.
1252    if (N1.getOpcode() == ISD::SETCC &&
1253        TLI.getSetCCResultContents() ==
1254                        TargetLowering::ZeroOrNegativeOneSetCCResult)
1255      return N1;
1256
1257    // If we are sign extending the result of an (and X, C) operation, and we
1258    // know the extended bits are zeros already, don't do the extend.
1259    if (N1.getOpcode() == ISD::AND)
1260      if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
1261        uint64_t Mask = N1C->getValue();
1262        unsigned NumBits = MVT::getSizeInBits(EVT);
1263        if ((Mask & (~0ULL << (NumBits-1))) == 0)
1264          return N1;
1265      }
1266    break;
1267  }
1268
1269  // FIXME: figure out how to safely handle things like
1270  // int foo(int x) { return 1 << (x & 255); }
1271  // int bar() { return foo(256); }
1272#if 0
1273  case ISD::SHL:
1274  case ISD::SRL:
1275  case ISD::SRA:
1276    if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1277        cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1)
1278      return getNode(Opcode, VT, N1, N2.getOperand(0));
1279    else if (N2.getOpcode() == ISD::AND)
1280      if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) {
1281        // If the and is only masking out bits that cannot effect the shift,
1282        // eliminate the and.
1283        unsigned NumBits = MVT::getSizeInBits(VT);
1284        if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1285          return getNode(Opcode, VT, N1, N2.getOperand(0));
1286      }
1287    break;
1288#endif
1289  }
1290
1291  // Memoize this node if possible.
1292  SDNode *N;
1293  if (Opcode != ISD::CALLSEQ_START && Opcode != ISD::CALLSEQ_END) {
1294    SDNode *&BON = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
1295    if (BON) return SDOperand(BON, 0);
1296
1297    BON = N = new SDNode(Opcode, N1, N2);
1298  } else {
1299    N = new SDNode(Opcode, N1, N2);
1300  }
1301
1302  N->setValueTypes(VT);
1303  AllNodes.push_back(N);
1304  return SDOperand(N, 0);
1305}
1306
1307// setAdjCallChain - This method changes the token chain of an
1308// CALLSEQ_START/END node to be the specified operand.
1309void SDNode::setAdjCallChain(SDOperand N) {
1310  assert(N.getValueType() == MVT::Other);
1311  assert((getOpcode() == ISD::CALLSEQ_START ||
1312          getOpcode() == ISD::CALLSEQ_END) && "Cannot adjust this node!");
1313
1314  Operands[0].Val->removeUser(this);
1315  Operands[0] = N;
1316  N.Val->Uses.push_back(this);
1317}
1318
1319
1320
1321SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
1322                                SDOperand Chain, SDOperand Ptr,
1323                                SDOperand SV) {
1324  SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
1325  if (N) return SDOperand(N, 0);
1326  N = new SDNode(ISD::LOAD, Chain, Ptr, SV);
1327
1328  // Loads have a token chain.
1329  N->setValueTypes(VT, MVT::Other);
1330  AllNodes.push_back(N);
1331  return SDOperand(N, 0);
1332}
1333
1334
1335SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT,
1336                                   SDOperand Chain, SDOperand Ptr, SDOperand SV,
1337                                   MVT::ValueType EVT) {
1338  std::vector<SDOperand> Ops;
1339  Ops.reserve(4);
1340  Ops.push_back(Chain);
1341  Ops.push_back(Ptr);
1342  Ops.push_back(SV);
1343  Ops.push_back(getValueType(EVT));
1344  std::vector<MVT::ValueType> VTs;
1345  VTs.reserve(2);
1346  VTs.push_back(VT); VTs.push_back(MVT::Other);  // Add token chain.
1347  return getNode(Opcode, VTs, Ops);
1348}
1349
1350SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1351                                SDOperand N1, SDOperand N2, SDOperand N3) {
1352  // Perform various simplifications.
1353  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1354  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1355  ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
1356  switch (Opcode) {
1357  case ISD::SETCC: {
1358    // Use SimplifySetCC  to simplify SETCC's.
1359    SDOperand Simp = SimplfySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
1360    if (Simp.Val) return Simp;
1361    break;
1362  }
1363  case ISD::SELECT:
1364    if (N1C)
1365      if (N1C->getValue())
1366        return N2;             // select true, X, Y -> X
1367      else
1368        return N3;             // select false, X, Y -> Y
1369
1370    if (N2 == N3) return N2;   // select C, X, X -> X
1371
1372    if (VT == MVT::i1) {  // Boolean SELECT
1373      if (N2C) {
1374        if (N2C->getValue())   // select C, 1, X -> C | X
1375          return getNode(ISD::OR, VT, N1, N3);
1376        else                   // select C, 0, X -> ~C & X
1377          return getNode(ISD::AND, VT,
1378                         getNode(ISD::XOR, N1.getValueType(), N1,
1379                                 getConstant(1, N1.getValueType())), N3);
1380      } else if (N3C) {
1381        if (N3C->getValue())   // select C, X, 1 -> ~C | X
1382          return getNode(ISD::OR, VT,
1383                         getNode(ISD::XOR, N1.getValueType(), N1,
1384                                 getConstant(1, N1.getValueType())), N2);
1385        else                   // select C, X, 0 -> C & X
1386          return getNode(ISD::AND, VT, N1, N2);
1387      }
1388
1389      if (N1 == N2)   // X ? X : Y --> X ? 1 : Y --> X | Y
1390        return getNode(ISD::OR, VT, N1, N3);
1391      if (N1 == N3)   // X ? Y : X --> X ? Y : 0 --> X & Y
1392        return getNode(ISD::AND, VT, N1, N2);
1393    }
1394
1395    // If this is a selectcc, check to see if we can simplify the result.
1396    if (N1.Val->getOpcode() == ISD::SETCC) {
1397      SDNode *SetCC = N1.Val;
1398      ISD::CondCode CC = cast<CondCodeSDNode>(SetCC->getOperand(2))->get();
1399      if (ConstantFPSDNode *CFP =
1400          dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1)))
1401        if (CFP->getValue() == 0.0) {   // Allow either -0.0 or 0.0
1402          // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs
1403          if ((CC == ISD::SETGE || CC == ISD::SETGT) &&
1404              N2 == SetCC->getOperand(0) && N3.getOpcode() == ISD::FNEG &&
1405              N3.getOperand(0) == N2)
1406            return getNode(ISD::FABS, VT, N2);
1407
1408          // select (setl[te] X, +/-0.0), fneg(X), X -> fabs
1409          if ((CC == ISD::SETLT || CC == ISD::SETLE) &&
1410              N3 == SetCC->getOperand(0) && N2.getOpcode() == ISD::FNEG &&
1411              N2.getOperand(0) == N3)
1412            return getNode(ISD::FABS, VT, N3);
1413        }
1414      // select (setlt X, 0), A, 0 -> and (sra X, size(X)-1), A
1415      if (ConstantSDNode *CN =
1416          dyn_cast<ConstantSDNode>(SetCC->getOperand(1)))
1417        if (CN->getValue() == 0 && N3C && N3C->getValue() == 0)
1418          if (CC == ISD::SETLT) {
1419            MVT::ValueType XType = SetCC->getOperand(0).getValueType();
1420            MVT::ValueType AType = N2.getValueType();
1421            if (XType >= AType) {
1422              // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a
1423              // single-bit constant.  FIXME: remove once the dag combiner
1424              // exists.
1425              if (ConstantSDNode *AC = dyn_cast<ConstantSDNode>(N2))
1426                if ((AC->getValue() & (AC->getValue()-1)) == 0) {
1427                  unsigned ShCtV = Log2_64(AC->getValue());
1428                  ShCtV = MVT::getSizeInBits(XType)-ShCtV-1;
1429                  SDOperand ShCt = getConstant(ShCtV, TLI.getShiftAmountTy());
1430                  SDOperand Shift = getNode(ISD::SRL, XType,
1431                                            SetCC->getOperand(0), ShCt);
1432                  if (XType > AType)
1433                    Shift = getNode(ISD::TRUNCATE, AType, Shift);
1434                  return getNode(ISD::AND, AType, Shift, N2);
1435                }
1436
1437
1438              SDOperand Shift = getNode(ISD::SRA, XType, SetCC->getOperand(0),
1439                getConstant(MVT::getSizeInBits(XType)-1,
1440                            TLI.getShiftAmountTy()));
1441              if (XType > AType)
1442                Shift = getNode(ISD::TRUNCATE, AType, Shift);
1443              return getNode(ISD::AND, AType, Shift, N2);
1444            }
1445          }
1446    }
1447    break;
1448  case ISD::BRCOND:
1449    if (N2C)
1450      if (N2C->getValue()) // Unconditional branch
1451        return getNode(ISD::BR, MVT::Other, N1, N3);
1452      else
1453        return N1;         // Never-taken branch
1454    break;
1455  }
1456
1457  std::vector<SDOperand> Ops;
1458  Ops.reserve(3);
1459  Ops.push_back(N1);
1460  Ops.push_back(N2);
1461  Ops.push_back(N3);
1462
1463  // Memoize nodes.
1464  SDNode *&N = OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))];
1465  if (N) return SDOperand(N, 0);
1466
1467  N = new SDNode(Opcode, N1, N2, N3);
1468  N->setValueTypes(VT);
1469  AllNodes.push_back(N);
1470  return SDOperand(N, 0);
1471}
1472
1473SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1474                                SDOperand N1, SDOperand N2, SDOperand N3,
1475                                SDOperand N4) {
1476  std::vector<SDOperand> Ops;
1477  Ops.reserve(4);
1478  Ops.push_back(N1);
1479  Ops.push_back(N2);
1480  Ops.push_back(N3);
1481  Ops.push_back(N4);
1482  return getNode(Opcode, VT, Ops);
1483}
1484
1485SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1486                                SDOperand N1, SDOperand N2, SDOperand N3,
1487                                SDOperand N4, SDOperand N5) {
1488  std::vector<SDOperand> Ops;
1489  Ops.reserve(5);
1490  Ops.push_back(N1);
1491  Ops.push_back(N2);
1492  Ops.push_back(N3);
1493  Ops.push_back(N4);
1494  Ops.push_back(N5);
1495  return getNode(Opcode, VT, Ops);
1496}
1497
1498
1499SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) {
1500  assert((!V || isa<PointerType>(V->getType())) &&
1501         "SrcValue is not a pointer?");
1502  SDNode *&N = ValueNodes[std::make_pair(V, Offset)];
1503  if (N) return SDOperand(N, 0);
1504
1505  N = new SrcValueSDNode(V, Offset);
1506  AllNodes.push_back(N);
1507  return SDOperand(N, 0);
1508}
1509
1510SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1511                                std::vector<SDOperand> &Ops) {
1512  switch (Ops.size()) {
1513  case 0: return getNode(Opcode, VT);
1514  case 1: return getNode(Opcode, VT, Ops[0]);
1515  case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
1516  case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
1517  default: break;
1518  }
1519
1520  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(Ops[1].Val);
1521  switch (Opcode) {
1522  default: break;
1523  case ISD::BRCONDTWOWAY:
1524    if (N1C)
1525      if (N1C->getValue()) // Unconditional branch to true dest.
1526        return getNode(ISD::BR, MVT::Other, Ops[0], Ops[2]);
1527      else                 // Unconditional branch to false dest.
1528        return getNode(ISD::BR, MVT::Other, Ops[0], Ops[3]);
1529    break;
1530
1531  case ISD::TRUNCSTORE: {
1532    assert(Ops.size() == 5 && "TRUNCSTORE takes 5 operands!");
1533    MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT();
1534#if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store
1535    // If this is a truncating store of a constant, convert to the desired type
1536    // and store it instead.
1537    if (isa<Constant>(Ops[0])) {
1538      SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1);
1539      if (isa<Constant>(Op))
1540        N1 = Op;
1541    }
1542    // Also for ConstantFP?
1543#endif
1544    if (Ops[0].getValueType() == EVT)       // Normal store?
1545      return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]);
1546    assert(Ops[1].getValueType() > EVT && "Not a truncation?");
1547    assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) &&
1548           "Can't do FP-INT conversion!");
1549    break;
1550  }
1551  }
1552
1553  // Memoize nodes.
1554  SDNode *&N = OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))];
1555  if (N) return SDOperand(N, 0);
1556  N = new SDNode(Opcode, Ops);
1557  N->setValueTypes(VT);
1558  AllNodes.push_back(N);
1559  return SDOperand(N, 0);
1560}
1561
1562SDOperand SelectionDAG::getNode(unsigned Opcode,
1563                                std::vector<MVT::ValueType> &ResultTys,
1564                                std::vector<SDOperand> &Ops) {
1565  if (ResultTys.size() == 1)
1566    return getNode(Opcode, ResultTys[0], Ops);
1567
1568  switch (Opcode) {
1569  case ISD::EXTLOAD:
1570  case ISD::SEXTLOAD:
1571  case ISD::ZEXTLOAD: {
1572    MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT();
1573    assert(Ops.size() == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!");
1574    // If they are asking for an extending load from/to the same thing, return a
1575    // normal load.
1576    if (ResultTys[0] == EVT)
1577      return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]);
1578    assert(EVT < ResultTys[0] &&
1579           "Should only be an extending load, not truncating!");
1580    assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) &&
1581           "Cannot sign/zero extend a FP load!");
1582    assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) &&
1583           "Cannot convert from FP to Int or Int -> FP!");
1584    break;
1585  }
1586
1587  // FIXME: figure out how to safely handle things like
1588  // int foo(int x) { return 1 << (x & 255); }
1589  // int bar() { return foo(256); }
1590#if 0
1591  case ISD::SRA_PARTS:
1592  case ISD::SRL_PARTS:
1593  case ISD::SHL_PARTS:
1594    if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1595        cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
1596      return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1597    else if (N3.getOpcode() == ISD::AND)
1598      if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
1599        // If the and is only masking out bits that cannot effect the shift,
1600        // eliminate the and.
1601        unsigned NumBits = MVT::getSizeInBits(VT)*2;
1602        if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1603          return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1604      }
1605    break;
1606#endif
1607  }
1608
1609  // Memoize the node.
1610  SDNode *&N = ArbitraryNodes[std::make_pair(Opcode, std::make_pair(ResultTys,
1611                                                                    Ops))];
1612  if (N) return SDOperand(N, 0);
1613  N = new SDNode(Opcode, Ops);
1614  N->setValueTypes(ResultTys);
1615  AllNodes.push_back(N);
1616  return SDOperand(N, 0);
1617}
1618
1619/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
1620/// indicated value.  This method ignores uses of other values defined by this
1621/// operation.
1622bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) {
1623  assert(Value < getNumValues() && "Bad value!");
1624
1625  // If there is only one value, this is easy.
1626  if (getNumValues() == 1)
1627    return use_size() == NUses;
1628  if (Uses.size() < NUses) return false;
1629
1630  SDOperand TheValue(this, Value);
1631
1632  std::set<SDNode*> UsersHandled;
1633
1634  for (std::vector<SDNode*>::iterator UI = Uses.begin(), E = Uses.end();
1635       UI != E; ++UI) {
1636    SDNode *User = *UI;
1637    if (User->getNumOperands() == 1 ||
1638        UsersHandled.insert(User).second)     // First time we've seen this?
1639      for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
1640        if (User->getOperand(i) == TheValue) {
1641          if (NUses == 0)
1642            return false;   // too many uses
1643          --NUses;
1644        }
1645  }
1646
1647  // Found exactly the right number of uses?
1648  return NUses == 0;
1649}
1650
1651
1652const char *SDNode::getOperationName() const {
1653  switch (getOpcode()) {
1654  default: return "<<Unknown>>";
1655  case ISD::PCMARKER:      return "PCMarker";
1656  case ISD::SRCVALUE:      return "SrcValue";
1657  case ISD::EntryToken:    return "EntryToken";
1658  case ISD::TokenFactor:   return "TokenFactor";
1659  case ISD::Constant:      return "Constant";
1660  case ISD::ConstantFP:    return "ConstantFP";
1661  case ISD::GlobalAddress: return "GlobalAddress";
1662  case ISD::FrameIndex:    return "FrameIndex";
1663  case ISD::BasicBlock:    return "BasicBlock";
1664  case ISD::ExternalSymbol: return "ExternalSymbol";
1665  case ISD::ConstantPool:  return "ConstantPoolIndex";
1666  case ISD::CopyToReg:     return "CopyToReg";
1667  case ISD::CopyFromReg:   return "CopyFromReg";
1668  case ISD::ImplicitDef:   return "ImplicitDef";
1669  case ISD::UNDEF:         return "undef";
1670
1671  // Unary operators
1672  case ISD::FABS:   return "fabs";
1673  case ISD::FNEG:   return "fneg";
1674  case ISD::FSQRT:  return "fsqrt";
1675  case ISD::FSIN:   return "fsin";
1676  case ISD::FCOS:   return "fcos";
1677
1678  // Binary operators
1679  case ISD::ADD:    return "add";
1680  case ISD::SUB:    return "sub";
1681  case ISD::MUL:    return "mul";
1682  case ISD::MULHU:  return "mulhu";
1683  case ISD::MULHS:  return "mulhs";
1684  case ISD::SDIV:   return "sdiv";
1685  case ISD::UDIV:   return "udiv";
1686  case ISD::SREM:   return "srem";
1687  case ISD::UREM:   return "urem";
1688  case ISD::AND:    return "and";
1689  case ISD::OR:     return "or";
1690  case ISD::XOR:    return "xor";
1691  case ISD::SHL:    return "shl";
1692  case ISD::SRA:    return "sra";
1693  case ISD::SRL:    return "srl";
1694
1695  case ISD::SETCC:       return "setcc";
1696  case ISD::SELECT:      return "select";
1697  case ISD::ADD_PARTS:   return "add_parts";
1698  case ISD::SUB_PARTS:   return "sub_parts";
1699  case ISD::SHL_PARTS:   return "shl_parts";
1700  case ISD::SRA_PARTS:   return "sra_parts";
1701  case ISD::SRL_PARTS:   return "srl_parts";
1702
1703  // Conversion operators.
1704  case ISD::SIGN_EXTEND: return "sign_extend";
1705  case ISD::ZERO_EXTEND: return "zero_extend";
1706  case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
1707  case ISD::TRUNCATE:    return "truncate";
1708  case ISD::FP_ROUND:    return "fp_round";
1709  case ISD::FP_ROUND_INREG: return "fp_round_inreg";
1710  case ISD::FP_EXTEND:   return "fp_extend";
1711
1712  case ISD::SINT_TO_FP:  return "sint_to_fp";
1713  case ISD::UINT_TO_FP:  return "uint_to_fp";
1714  case ISD::FP_TO_SINT:  return "fp_to_sint";
1715  case ISD::FP_TO_UINT:  return "fp_to_uint";
1716
1717    // Control flow instructions
1718  case ISD::BR:      return "br";
1719  case ISD::BRCOND:  return "brcond";
1720  case ISD::BRCONDTWOWAY:  return "brcondtwoway";
1721  case ISD::RET:     return "ret";
1722  case ISD::CALL:    return "call";
1723  case ISD::TAILCALL:return "tailcall";
1724  case ISD::CALLSEQ_START:  return "callseq_start";
1725  case ISD::CALLSEQ_END:    return "callseq_end";
1726
1727    // Other operators
1728  case ISD::LOAD:    return "load";
1729  case ISD::STORE:   return "store";
1730  case ISD::EXTLOAD:    return "extload";
1731  case ISD::SEXTLOAD:   return "sextload";
1732  case ISD::ZEXTLOAD:   return "zextload";
1733  case ISD::TRUNCSTORE: return "truncstore";
1734
1735  case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
1736  case ISD::EXTRACT_ELEMENT: return "extract_element";
1737  case ISD::BUILD_PAIR: return "build_pair";
1738  case ISD::MEMSET:  return "memset";
1739  case ISD::MEMCPY:  return "memcpy";
1740  case ISD::MEMMOVE: return "memmove";
1741
1742  // Bit counting
1743  case ISD::CTPOP:   return "ctpop";
1744  case ISD::CTTZ:    return "cttz";
1745  case ISD::CTLZ:    return "ctlz";
1746
1747  // IO Intrinsics
1748  case ISD::READPORT: return "readport";
1749  case ISD::WRITEPORT: return "writeport";
1750  case ISD::READIO: return "readio";
1751  case ISD::WRITEIO: return "writeio";
1752
1753  case ISD::CONDCODE:
1754    switch (cast<CondCodeSDNode>(this)->get()) {
1755    default: assert(0 && "Unknown setcc condition!");
1756    case ISD::SETOEQ:  return "setoeq";
1757    case ISD::SETOGT:  return "setogt";
1758    case ISD::SETOGE:  return "setoge";
1759    case ISD::SETOLT:  return "setolt";
1760    case ISD::SETOLE:  return "setole";
1761    case ISD::SETONE:  return "setone";
1762
1763    case ISD::SETO:    return "seto";
1764    case ISD::SETUO:   return "setuo";
1765    case ISD::SETUEQ:  return "setue";
1766    case ISD::SETUGT:  return "setugt";
1767    case ISD::SETUGE:  return "setuge";
1768    case ISD::SETULT:  return "setult";
1769    case ISD::SETULE:  return "setule";
1770    case ISD::SETUNE:  return "setune";
1771
1772    case ISD::SETEQ:   return "seteq";
1773    case ISD::SETGT:   return "setgt";
1774    case ISD::SETGE:   return "setge";
1775    case ISD::SETLT:   return "setlt";
1776    case ISD::SETLE:   return "setle";
1777    case ISD::SETNE:   return "setne";
1778    }
1779  }
1780}
1781
1782void SDNode::dump() const {
1783  std::cerr << (void*)this << ": ";
1784
1785  for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
1786    if (i) std::cerr << ",";
1787    if (getValueType(i) == MVT::Other)
1788      std::cerr << "ch";
1789    else
1790      std::cerr << MVT::getValueTypeString(getValueType(i));
1791  }
1792  std::cerr << " = " << getOperationName();
1793
1794  std::cerr << " ";
1795  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1796    if (i) std::cerr << ", ";
1797    std::cerr << (void*)getOperand(i).Val;
1798    if (unsigned RN = getOperand(i).ResNo)
1799      std::cerr << ":" << RN;
1800  }
1801
1802  if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
1803    std::cerr << "<" << CSDN->getValue() << ">";
1804  } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
1805    std::cerr << "<" << CSDN->getValue() << ">";
1806  } else if (const GlobalAddressSDNode *GADN =
1807             dyn_cast<GlobalAddressSDNode>(this)) {
1808    std::cerr << "<";
1809    WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
1810  } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
1811    std::cerr << "<" << FIDN->getIndex() << ">";
1812  } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
1813    std::cerr << "<" << CP->getIndex() << ">";
1814  } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
1815    std::cerr << "<";
1816    const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
1817    if (LBB)
1818      std::cerr << LBB->getName() << " ";
1819    std::cerr << (const void*)BBDN->getBasicBlock() << ">";
1820  } else if (const RegSDNode *C2V = dyn_cast<RegSDNode>(this)) {
1821    std::cerr << "<reg #" << C2V->getReg() << ">";
1822  } else if (const ExternalSymbolSDNode *ES =
1823             dyn_cast<ExternalSymbolSDNode>(this)) {
1824    std::cerr << "'" << ES->getSymbol() << "'";
1825  } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
1826    if (M->getValue())
1827      std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">";
1828    else
1829      std::cerr << "<null:" << M->getOffset() << ">";
1830  }
1831}
1832
1833static void DumpNodes(SDNode *N, unsigned indent) {
1834  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1835    if (N->getOperand(i).Val->hasOneUse())
1836      DumpNodes(N->getOperand(i).Val, indent+2);
1837    else
1838      std::cerr << "\n" << std::string(indent+2, ' ')
1839                << (void*)N->getOperand(i).Val << ": <multiple use>";
1840
1841
1842  std::cerr << "\n" << std::string(indent, ' ');
1843  N->dump();
1844}
1845
1846void SelectionDAG::dump() const {
1847  std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
1848  std::vector<SDNode*> Nodes(AllNodes);
1849  std::sort(Nodes.begin(), Nodes.end());
1850
1851  for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
1852    if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
1853      DumpNodes(Nodes[i], 2);
1854  }
1855
1856  DumpNodes(getRoot().Val, 2);
1857
1858  std::cerr << "\n\n";
1859}
1860
1861