SelectionDAG.cpp revision 5cdcc58d51c792d329202bab97c34aefbc043b15
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 <iostream>
20#include <set>
21#include <cmath>
22#include <algorithm>
23using namespace llvm;
24
25static bool isCommutativeBinOp(unsigned Opcode) {
26  switch (Opcode) {
27  case ISD::ADD:
28  case ISD::MUL:
29  case ISD::AND:
30  case ISD::OR:
31  case ISD::XOR: return true;
32  default: return false; // FIXME: Need commutative info for user ops!
33  }
34}
35
36static bool isAssociativeBinOp(unsigned Opcode) {
37  switch (Opcode) {
38  case ISD::ADD:
39  case ISD::MUL:
40  case ISD::AND:
41  case ISD::OR:
42  case ISD::XOR: return true;
43  default: return false; // FIXME: Need associative info for user ops!
44  }
45}
46
47static unsigned ExactLog2(uint64_t Val) {
48  unsigned Count = 0;
49  while (Val != 1) {
50    Val >>= 1;
51    ++Count;
52  }
53  return Count;
54}
55
56// isInvertibleForFree - Return true if there is no cost to emitting the logical
57// inverse of this node.
58static bool isInvertibleForFree(SDOperand N) {
59  if (isa<ConstantSDNode>(N.Val)) return true;
60  if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse())
61    return true;
62  return false;
63}
64
65
66/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
67/// when given the operation for (X op Y).
68ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
69  // To perform this operation, we just need to swap the L and G bits of the
70  // operation.
71  unsigned OldL = (Operation >> 2) & 1;
72  unsigned OldG = (Operation >> 1) & 1;
73  return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
74                       (OldL << 1) |       // New G bit
75                       (OldG << 2));        // New L bit.
76}
77
78/// getSetCCInverse - Return the operation corresponding to !(X op Y), where
79/// 'op' is a valid SetCC operation.
80ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
81  unsigned Operation = Op;
82  if (isInteger)
83    Operation ^= 7;   // Flip L, G, E bits, but not U.
84  else
85    Operation ^= 15;  // Flip all of the condition bits.
86  if (Operation > ISD::SETTRUE2)
87    Operation &= ~8;     // Don't let N and U bits get set.
88  return ISD::CondCode(Operation);
89}
90
91
92/// isSignedOp - For an integer comparison, return 1 if the comparison is a
93/// signed operation and 2 if the result is an unsigned comparison.  Return zero
94/// if the operation does not depend on the sign of the input (setne and seteq).
95static int isSignedOp(ISD::CondCode Opcode) {
96  switch (Opcode) {
97  default: assert(0 && "Illegal integer setcc operation!");
98  case ISD::SETEQ:
99  case ISD::SETNE: return 0;
100  case ISD::SETLT:
101  case ISD::SETLE:
102  case ISD::SETGT:
103  case ISD::SETGE: return 1;
104  case ISD::SETULT:
105  case ISD::SETULE:
106  case ISD::SETUGT:
107  case ISD::SETUGE: return 2;
108  }
109}
110
111/// getSetCCOrOperation - Return the result of a logical OR between different
112/// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
113/// returns SETCC_INVALID if it is not possible to represent the resultant
114/// comparison.
115ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
116                                       bool isInteger) {
117  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
118    // Cannot fold a signed integer setcc with an unsigned integer setcc.
119    return ISD::SETCC_INVALID;
120
121  unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
122
123  // If the N and U bits get set then the resultant comparison DOES suddenly
124  // care about orderedness, and is true when ordered.
125  if (Op > ISD::SETTRUE2)
126    Op &= ~16;     // Clear the N bit.
127  return ISD::CondCode(Op);
128}
129
130/// getSetCCAndOperation - Return the result of a logical AND between different
131/// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
132/// function returns zero if it is not possible to represent the resultant
133/// comparison.
134ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
135                                        bool isInteger) {
136  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
137    // Cannot fold a signed setcc with an unsigned setcc.
138    return ISD::SETCC_INVALID;
139
140  // Combine all of the condition bits.
141  return ISD::CondCode(Op1 & Op2);
142}
143
144/// RemoveDeadNodes - This method deletes all unreachable nodes in the
145/// SelectionDAG, including nodes (like loads) that have uses of their token
146/// chain but no other uses and no side effect.  If a node is passed in as an
147/// argument, it is used as the seed for node deletion.
148void SelectionDAG::RemoveDeadNodes(SDNode *N) {
149  std::set<SDNode*> AllNodeSet(AllNodes.begin(), AllNodes.end());
150
151  // Create a dummy node (which is not added to allnodes), that adds a reference
152  // to the root node, preventing it from being deleted.
153  SDNode *DummyNode = new SDNode(ISD::EntryToken, getRoot());
154
155  DeleteNodeIfDead(N, &AllNodeSet);
156
157 Restart:
158  unsigned NumNodes = AllNodeSet.size();
159  for (std::set<SDNode*>::iterator I = AllNodeSet.begin(), E = AllNodeSet.end();
160       I != E; ++I) {
161    // Try to delete this node.
162    DeleteNodeIfDead(*I, &AllNodeSet);
163
164    // If we actually deleted any nodes, do not use invalid iterators in
165    // AllNodeSet.
166    if (AllNodeSet.size() != NumNodes)
167      goto Restart;
168  }
169
170  // Restore AllNodes.
171  if (AllNodes.size() != NumNodes)
172    AllNodes.assign(AllNodeSet.begin(), AllNodeSet.end());
173
174  // If the root changed (e.g. it was a dead load, update the root).
175  setRoot(DummyNode->getOperand(0));
176
177  // Now that we are done with the dummy node, delete it.
178  DummyNode->getOperand(0).Val->removeUser(DummyNode);
179  delete DummyNode;
180}
181
182void SelectionDAG::DeleteNodeIfDead(SDNode *N, void *NodeSet) {
183  if (!N->use_empty())
184    return;
185
186  // Okay, we really are going to delete this node.  First take this out of the
187  // appropriate CSE map.
188  switch (N->getOpcode()) {
189  case ISD::Constant:
190    Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
191                                   N->getValueType(0)));
192    break;
193  case ISD::ConstantFP:
194    ConstantFPs.erase(std::make_pair(cast<ConstantFPSDNode>(N)->getValue(),
195                                     N->getValueType(0)));
196    break;
197  case ISD::GlobalAddress:
198    GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal());
199    break;
200  case ISD::FrameIndex:
201    FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
202    break;
203  case ISD::ConstantPool:
204    ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->getIndex());
205    break;
206  case ISD::BasicBlock:
207    BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
208    break;
209  case ISD::ExternalSymbol:
210    ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
211    break;
212
213  case ISD::LOAD:
214    Loads.erase(std::make_pair(N->getOperand(1),
215                               std::make_pair(N->getOperand(0),
216                                              N->getValueType(0))));
217    break;
218  case ISD::SETCC:
219    SetCCs.erase(std::make_pair(std::make_pair(N->getOperand(0),
220                                               N->getOperand(1)),
221                                cast<SetCCSDNode>(N)->getCondition()));
222    break;
223  default:
224    if (N->getNumOperands() == 1)
225      UnaryOps.erase(std::make_pair(N->getOpcode(),
226                                    std::make_pair(N->getOperand(0),
227                                                   N->getValueType(0))));
228    else if (N->getNumOperands() == 2)
229      BinaryOps.erase(std::make_pair(N->getOpcode(),
230                                     std::make_pair(N->getOperand(0),
231                                                    N->getOperand(1))));
232    break;
233  }
234
235  // Next, brutally remove the operand list.
236  while (!N->Operands.empty()) {
237    SDNode *O = N->Operands.back().Val;
238    N->Operands.pop_back();
239    O->removeUser(N);
240
241    // Now that we removed this operand, see if there are no uses of it left.
242    DeleteNodeIfDead(O, NodeSet);
243  }
244
245  // Remove the node from the nodes set and delete it.
246  std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet;
247  AllNodeSet.erase(N);
248
249  // Now that the node is gone, check to see if any of the operands of this node
250  // are dead now.
251  delete N;
252}
253
254
255SelectionDAG::~SelectionDAG() {
256  for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
257    delete AllNodes[i];
258}
259
260SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
261  assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
262  // Mask out any bits that are not valid for this constant.
263  if (VT != MVT::i64)
264    Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
265
266  SDNode *&N = Constants[std::make_pair(Val, VT)];
267  if (N) return SDOperand(N, 0);
268  N = new ConstantSDNode(Val, VT);
269  AllNodes.push_back(N);
270  return SDOperand(N, 0);
271}
272
273SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
274  assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
275  if (VT == MVT::f32)
276    Val = (float)Val;  // Mask out extra precision.
277
278  SDNode *&N = ConstantFPs[std::make_pair(Val, VT)];
279  if (N) return SDOperand(N, 0);
280  N = new ConstantFPSDNode(Val, VT);
281  AllNodes.push_back(N);
282  return SDOperand(N, 0);
283}
284
285
286
287SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
288                                         MVT::ValueType VT) {
289  SDNode *&N = GlobalValues[GV];
290  if (N) return SDOperand(N, 0);
291  N = new GlobalAddressSDNode(GV,VT);
292  AllNodes.push_back(N);
293  return SDOperand(N, 0);
294}
295
296SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
297  SDNode *&N = FrameIndices[FI];
298  if (N) return SDOperand(N, 0);
299  N = new FrameIndexSDNode(FI, VT);
300  AllNodes.push_back(N);
301  return SDOperand(N, 0);
302}
303
304SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) {
305  SDNode *N = ConstantPoolIndices[CPIdx];
306  if (N) return SDOperand(N, 0);
307  N = new ConstantPoolSDNode(CPIdx, VT);
308  AllNodes.push_back(N);
309  return SDOperand(N, 0);
310}
311
312SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
313  SDNode *&N = BBNodes[MBB];
314  if (N) return SDOperand(N, 0);
315  N = new BasicBlockSDNode(MBB);
316  AllNodes.push_back(N);
317  return SDOperand(N, 0);
318}
319
320SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
321  SDNode *&N = ExternalSymbols[Sym];
322  if (N) return SDOperand(N, 0);
323  N = new ExternalSymbolSDNode(Sym, VT);
324  AllNodes.push_back(N);
325  return SDOperand(N, 0);
326}
327
328SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1,
329                                 SDOperand N2) {
330  // These setcc operations always fold.
331  switch (Cond) {
332  default: break;
333  case ISD::SETFALSE:
334  case ISD::SETFALSE2: return getConstant(0, MVT::i1);
335  case ISD::SETTRUE:
336  case ISD::SETTRUE2:  return getConstant(1, MVT::i1);
337  }
338
339  if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val))
340    if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
341      uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
342
343      // Sign extend the operands if required
344      if (ISD::isSignedIntSetCC(Cond)) {
345        C1 = N1C->getSignExtended();
346        C2 = N2C->getSignExtended();
347      }
348
349      switch (Cond) {
350      default: assert(0 && "Unknown integer setcc!");
351      case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
352      case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
353      case ISD::SETULT: return getConstant(C1 <  C2, MVT::i1);
354      case ISD::SETUGT: return getConstant(C1 >  C2, MVT::i1);
355      case ISD::SETULE: return getConstant(C1 <= C2, MVT::i1);
356      case ISD::SETUGE: return getConstant(C1 >= C2, MVT::i1);
357      case ISD::SETLT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
358      case ISD::SETGT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
359      case ISD::SETLE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
360      case ISD::SETGE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
361      }
362    } else {
363      // Ensure that the constant occurs on the RHS.
364      Cond = ISD::getSetCCSwappedOperands(Cond);
365      std::swap(N1, N2);
366    }
367
368  if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
369    if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
370      double C1 = N1C->getValue(), C2 = N2C->getValue();
371
372      switch (Cond) {
373      default: break; // FIXME: Implement the rest of these!
374      case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
375      case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
376      case ISD::SETLT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
377      case ISD::SETGT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
378      case ISD::SETLE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
379      case ISD::SETGE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
380      }
381    } else {
382      // Ensure that the constant occurs on the RHS.
383      Cond = ISD::getSetCCSwappedOperands(Cond);
384      std::swap(N1, N2);
385    }
386
387  if (N1 == N2) {
388    // We can always fold X == Y for integer setcc's.
389    if (MVT::isInteger(N1.getValueType()))
390      return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
391    unsigned UOF = ISD::getUnorderedFlavor(Cond);
392    if (UOF == 2)   // FP operators that are undefined on NaNs.
393      return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
394    if (UOF == ISD::isTrueWhenEqual(Cond))
395      return getConstant(UOF, MVT::i1);
396    // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
397    // if it is not already.
398    Cond = UOF == 0 ? ISD::SETUO : ISD::SETO;
399  }
400
401  // Simplify (X+Y) == (X+Z) -->  Y == Z
402  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
403      N1.getOpcode() == N2.getOpcode() && MVT::isInteger(N1.getValueType()))
404    if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB) {
405      if (N1.getOperand(0) == N2.getOperand(0))
406        return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1));
407      if (N1.getOperand(1) == N2.getOperand(1))
408        return getSetCC(Cond, N1.getOperand(0), N2.getOperand(0));
409      if (isCommutativeBinOp(N1.getOpcode())) {
410        // If X op Y == Y op X, try other combinations.
411        if (N1.getOperand(0) == N2.getOperand(1))
412          return getSetCC(Cond, N1.getOperand(1), N2.getOperand(0));
413        if (N1.getOperand(1) == N2.getOperand(0))
414          return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1));
415      }
416    }
417
418
419  SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)];
420  if (N) return SDOperand(N, 0);
421  N = new SetCCSDNode(Cond, N1, N2);
422  AllNodes.push_back(N);
423  return SDOperand(N, 0);
424}
425
426
427
428/// getNode - Gets or creates the specified node.
429///
430SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
431  SDNode *N = new SDNode(Opcode, VT);
432  AllNodes.push_back(N);
433  return SDOperand(N, 0);
434}
435
436static const Type *getTypeFor(MVT::ValueType VT) {
437  switch (VT) {
438  default: assert(0 && "Unknown MVT!");
439  case MVT::i1: return Type::BoolTy;
440  case MVT::i8: return Type::UByteTy;
441  case MVT::i16: return Type::UShortTy;
442  case MVT::i32: return Type::UIntTy;
443  case MVT::i64: return Type::ULongTy;
444  case MVT::f32: return Type::FloatTy;
445  case MVT::f64: return Type::DoubleTy;
446  }
447}
448
449SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
450                                SDOperand Operand) {
451  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
452    uint64_t Val = C->getValue();
453    switch (Opcode) {
454    default: break;
455    case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
456    case ISD::ZERO_EXTEND: return getConstant(Val, VT);
457    case ISD::TRUNCATE:    return getConstant(Val, VT);
458    case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
459    case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
460    }
461  }
462
463  if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
464    switch (Opcode) {
465    case ISD::FP_ROUND:
466    case ISD::FP_EXTEND:
467      return getConstantFP(C->getValue(), VT);
468    case ISD::FP_TO_SINT:
469      return getConstant((int64_t)C->getValue(), VT);
470    case ISD::FP_TO_UINT:
471      return getConstant((uint64_t)C->getValue(), VT);
472    }
473
474  unsigned OpOpcode = Operand.Val->getOpcode();
475  switch (Opcode) {
476  case ISD::SIGN_EXTEND:
477    if (Operand.getValueType() == VT) return Operand;   // noop extension
478    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
479      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
480    break;
481  case ISD::ZERO_EXTEND:
482    if (Operand.getValueType() == VT) return Operand;   // noop extension
483    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
484      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
485    break;
486  case ISD::TRUNCATE:
487    if (Operand.getValueType() == VT) return Operand;   // noop truncate
488    if (OpOpcode == ISD::TRUNCATE)
489      return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
490    else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) {
491      // If the source is smaller than the dest, we still need an extend.
492      if (Operand.Val->getOperand(0).getValueType() < VT)
493        return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
494      else if (Operand.Val->getOperand(0).getValueType() > VT)
495        return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
496      else
497        return Operand.Val->getOperand(0);
498    }
499    break;
500  }
501
502  SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
503  if (N) return SDOperand(N, 0);
504  N = new SDNode(Opcode, Operand);
505  N->setValueTypes(VT);
506  AllNodes.push_back(N);
507  return SDOperand(N, 0);
508}
509
510SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
511                                SDOperand N1, SDOperand N2) {
512  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
513  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
514  if (N1C) {
515    if (N2C) {
516      uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
517      switch (Opcode) {
518      case ISD::ADD: return getConstant(C1 + C2, VT);
519      case ISD::SUB: return getConstant(C1 - C2, VT);
520      case ISD::MUL: return getConstant(C1 * C2, VT);
521      case ISD::UDIV:
522        if (C2) return getConstant(C1 / C2, VT);
523        break;
524      case ISD::UREM :
525        if (C2) return getConstant(C1 % C2, VT);
526        break;
527      case ISD::SDIV :
528        if (C2) return getConstant(N1C->getSignExtended() /
529                                   N2C->getSignExtended(), VT);
530        break;
531      case ISD::SREM :
532        if (C2) return getConstant(N1C->getSignExtended() %
533                                   N2C->getSignExtended(), VT);
534        break;
535      case ISD::AND  : return getConstant(C1 & C2, VT);
536      case ISD::OR   : return getConstant(C1 | C2, VT);
537      case ISD::XOR  : return getConstant(C1 ^ C2, VT);
538      default: break;
539      }
540
541    } else {      // Cannonicalize constant to RHS if commutative
542      if (isCommutativeBinOp(Opcode)) {
543        std::swap(N1C, N2C);
544        std::swap(N1, N2);
545      }
546    }
547  }
548
549  if (N2C) {
550    uint64_t C2 = N2C->getValue();
551
552    switch (Opcode) {
553    case ISD::ADD:
554      if (!C2) return N1;         // add X, 0 -> X
555      break;
556    case ISD::SUB:
557      if (!C2) return N1;         // sub X, 0 -> X
558      break;
559    case ISD::MUL:
560      if (!C2) return N2;         // mul X, 0 -> 0
561      if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X
562        return getNode(ISD::SUB, VT, getConstant(0, VT), N1);
563
564      // FIXME: This should only be done if the target supports shift
565      // operations.
566      if ((C2 & C2-1) == 0) {
567        SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
568        return getNode(ISD::SHL, VT, N1, ShAmt);
569      }
570      break;
571
572    case ISD::UDIV:
573      // FIXME: This should only be done if the target supports shift
574      // operations.
575      if ((C2 & C2-1) == 0 && C2) {
576        SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
577        return getNode(ISD::SRL, VT, N1, ShAmt);
578      }
579      break;
580
581    case ISD::AND:
582      if (!C2) return N2;         // X and 0 -> 0
583      if (N2C->isAllOnesValue())
584	return N1;                // X and -1 -> X
585      break;
586    case ISD::OR:
587      if (!C2)return N1;          // X or 0 -> X
588      if (N2C->isAllOnesValue())
589	return N2;                // X or -1 -> -1
590      break;
591    case ISD::XOR:
592      if (!C2) return N1;        // X xor 0 -> X
593      if (N2C->isAllOnesValue()) {
594        if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){
595          // !(X op Y) -> (X !op Y)
596          bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
597          return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger),
598                          SetCC->getOperand(0), SetCC->getOperand(1));
599        } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
600          SDNode *Op = N1.Val;
601          // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
602          // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
603          SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
604          if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
605            LHS = getNode(ISD::XOR, VT, LHS, N2);  // RHS = ~LHS
606            RHS = getNode(ISD::XOR, VT, RHS, N2);  // RHS = ~RHS
607            if (Op->getOpcode() == ISD::AND)
608              return getNode(ISD::OR, VT, LHS, RHS);
609            return getNode(ISD::AND, VT, LHS, RHS);
610          }
611        }
612	// X xor -1 -> not(x)  ?
613      }
614      break;
615    }
616
617    // Reassociate ((X op C1) op C2) if possible.
618    if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
619      if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
620        return getNode(Opcode, VT, N1.Val->getOperand(0),
621                       getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
622  }
623
624  ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
625  ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
626  if (N1CFP)
627    if (N2CFP) {
628      double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
629      switch (Opcode) {
630      case ISD::ADD: return getConstantFP(C1 + C2, VT);
631      case ISD::SUB: return getConstantFP(C1 - C2, VT);
632      case ISD::MUL: return getConstantFP(C1 * C2, VT);
633      case ISD::SDIV:
634        if (C2) return getConstantFP(C1 / C2, VT);
635        break;
636      case ISD::SREM :
637        if (C2) return getConstantFP(fmod(C1, C2), VT);
638        break;
639      default: break;
640      }
641
642    } else {      // Cannonicalize constant to RHS if commutative
643      if (isCommutativeBinOp(Opcode)) {
644        std::swap(N1CFP, N2CFP);
645        std::swap(N1, N2);
646      }
647    }
648
649  // Finally, fold operations that do not require constants.
650  switch (Opcode) {
651  case ISD::AND:
652  case ISD::OR:
653    if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val))
654      if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) {
655        SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
656        SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
657        ISD::CondCode Op2 = RHS->getCondition();
658
659        // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
660        if (LL == RR && LR == RL) {
661          Op2 = ISD::getSetCCSwappedOperands(Op2);
662          goto MatchedBackwards;
663        }
664
665        if (LL == RL && LR == RR) {
666        MatchedBackwards:
667          ISD::CondCode Result;
668          bool isInteger = MVT::isInteger(LL.getValueType());
669          if (Opcode == ISD::OR)
670            Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2,
671                                              isInteger);
672          else
673            Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2,
674                                               isInteger);
675          if (Result != ISD::SETCC_INVALID)
676            return getSetCC(Result, LL, LR);
677        }
678      }
679    break;
680  case ISD::XOR:
681    if (N1 == N2) return getConstant(0, VT);  // xor X, Y -> 0
682    break;
683  case ISD::SUB:
684    if (N1.getOpcode() == ISD::ADD) {
685      if (N1.Val->getOperand(0) == N2)
686        return N1.Val->getOperand(1);         // (A+B)-A == B
687      if (N1.Val->getOperand(1) == N2)
688        return N1.Val->getOperand(0);         // (A+B)-B == A
689    }
690    break;
691  }
692
693  SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
694  if (N) return SDOperand(N, 0);
695  N = new SDNode(Opcode, N1, N2);
696  N->setValueTypes(VT);
697
698  AllNodes.push_back(N);
699  return SDOperand(N, 0);
700}
701
702SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
703                                SDOperand Chain, SDOperand Ptr) {
704  SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
705  if (N) return SDOperand(N, 0);
706  N = new SDNode(ISD::LOAD, Chain, Ptr);
707
708  // Loads have a token chain.
709  N->setValueTypes(VT, MVT::Other);
710  AllNodes.push_back(N);
711  return SDOperand(N, 0);
712}
713
714
715SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
716                                SDOperand N1, SDOperand N2, SDOperand N3) {
717  // Perform various simplifications.
718  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
719  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
720  ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
721  switch (Opcode) {
722  case ISD::SELECT:
723    if (N1C)
724      if (N1C->getValue())
725        return N2;             // select true, X, Y -> X
726      else
727        return N3;             // select false, X, Y -> Y
728
729    if (N2 == N3) return N2;   // select C, X, X -> X
730
731    if (VT == MVT::i1) {  // Boolean SELECT
732      if (N2C) {
733        if (N3C) {
734          if (N2C->getValue()) // select C, 1, 0 -> C
735            return N1;
736          return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C
737        }
738
739        if (N2C->getValue())   // select C, 1, X -> C | X
740          return getNode(ISD::OR, VT, N1, N3);
741        else                   // select C, 0, X -> ~C & X
742          return getNode(ISD::AND, VT,
743                         getNode(ISD::XOR, N1.getValueType(), N1,
744                                 getConstant(1, N1.getValueType())), N3);
745      } else if (N3C) {
746        if (N3C->getValue())   // select C, X, 1 -> ~C | X
747          return getNode(ISD::OR, VT,
748                         getNode(ISD::XOR, N1.getValueType(), N1,
749                                 getConstant(1, N1.getValueType())), N2);
750        else                   // select C, X, 0 -> C & X
751          return getNode(ISD::AND, VT, N1, N2);
752      }
753    }
754
755    break;
756  case ISD::BRCOND:
757    if (N2C)
758      if (N2C->getValue()) // Unconditional branch
759        return getNode(ISD::BR, MVT::Other, N1, N3);
760      else
761        return N1;         // Never-taken branch
762    break;
763  }
764
765  SDNode *N = new SDNode(Opcode, N1, N2, N3);
766  switch (Opcode) {
767  default:
768    N->setValueTypes(VT);
769    break;
770  case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain
771    N->setValueTypes(VT, MVT::Other);
772    break;
773  }
774
775  // FIXME: memoize NODES
776  AllNodes.push_back(N);
777  return SDOperand(N, 0);
778}
779
780SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
781                                std::vector<SDOperand> &Children) {
782  switch (Children.size()) {
783  case 0: return getNode(Opcode, VT);
784  case 1: return getNode(Opcode, VT, Children[0]);
785  case 2: return getNode(Opcode, VT, Children[0], Children[1]);
786  case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]);
787  default:
788    // FIXME: MEMOIZE!!
789    SDNode *N = new SDNode(Opcode, Children);
790    N->setValueTypes(VT);
791    AllNodes.push_back(N);
792    return SDOperand(N, 0);
793  }
794}
795
796
797
798void SDNode::dump() const {
799  std::cerr << (void*)this << ": ";
800
801  for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
802    if (i) std::cerr << ",";
803    switch (getValueType(i)) {
804    default: assert(0 && "Unknown value type!");
805    case MVT::i1:    std::cerr << "i1"; break;
806    case MVT::i8:    std::cerr << "i8"; break;
807    case MVT::i16:   std::cerr << "i16"; break;
808    case MVT::i32:   std::cerr << "i32"; break;
809    case MVT::i64:   std::cerr << "i64"; break;
810    case MVT::f32:   std::cerr << "f32"; break;
811    case MVT::f64:   std::cerr << "f64"; break;
812    case MVT::Other: std::cerr << "ch"; break;
813    }
814  }
815  std::cerr << " = ";
816
817  switch (getOpcode()) {
818  default: std::cerr << "<<Unknown>>"; break;
819  case ISD::EntryToken:    std::cerr << "EntryToken"; break;
820  case ISD::Constant:      std::cerr << "Constant"; break;
821  case ISD::ConstantFP:    std::cerr << "ConstantFP"; break;
822  case ISD::GlobalAddress: std::cerr << "GlobalAddress"; break;
823  case ISD::FrameIndex:    std::cerr << "FrameIndex"; break;
824  case ISD::BasicBlock:    std::cerr << "BasicBlock"; break;
825  case ISD::ExternalSymbol: std::cerr << "ExternalSymbol"; break;
826  case ISD::ConstantPool:  std::cerr << "ConstantPoolIndex"; break;
827  case ISD::CopyToReg:     std::cerr << "CopyToReg"; break;
828  case ISD::CopyFromReg:   std::cerr << "CopyFromReg"; break;
829
830  case ISD::ADD:    std::cerr << "add"; break;
831  case ISD::SUB:    std::cerr << "sub"; break;
832  case ISD::MUL:    std::cerr << "mul"; break;
833  case ISD::SDIV:   std::cerr << "sdiv"; break;
834  case ISD::UDIV:   std::cerr << "udiv"; break;
835  case ISD::SREM:   std::cerr << "srem"; break;
836  case ISD::UREM:   std::cerr << "urem"; break;
837  case ISD::AND:    std::cerr << "and"; break;
838  case ISD::OR:     std::cerr << "or"; break;
839  case ISD::XOR:    std::cerr << "xor"; break;
840  case ISD::SHL:    std::cerr << "shl"; break;
841  case ISD::SRA:    std::cerr << "sra"; break;
842  case ISD::SRL:    std::cerr << "srl"; break;
843
844  case ISD::SETCC:  std::cerr << "setcc"; break;
845  case ISD::SELECT: std::cerr << "select"; break;
846  case ISD::ADDC:   std::cerr << "addc"; break;
847  case ISD::SUBB:   std::cerr << "subb"; break;
848
849    // Conversion operators.
850  case ISD::SIGN_EXTEND: std::cerr << "sign_extend"; break;
851  case ISD::ZERO_EXTEND: std::cerr << "zero_extend"; break;
852  case ISD::TRUNCATE:    std::cerr << "truncate"; break;
853  case ISD::FP_ROUND:    std::cerr << "fp_round"; break;
854  case ISD::FP_EXTEND:   std::cerr << "fp_extend"; break;
855
856  case ISD::SINT_TO_FP:  std::cerr << "sint_to_fp"; break;
857  case ISD::UINT_TO_FP:  std::cerr << "uint_to_fp"; break;
858  case ISD::FP_TO_SINT:  std::cerr << "fp_to_sint"; break;
859  case ISD::FP_TO_UINT:  std::cerr << "fp_to_uint"; break;
860
861    // Control flow instructions
862  case ISD::BR:      std::cerr << "br"; break;
863  case ISD::BRCOND:  std::cerr << "brcond"; break;
864  case ISD::RET:     std::cerr << "ret"; break;
865  case ISD::CALL:    std::cerr << "call"; break;
866  case ISD::ADJCALLSTACKDOWN:  std::cerr << "adjcallstackdown"; break;
867  case ISD::ADJCALLSTACKUP:    std::cerr << "adjcallstackup"; break;
868
869    // Other operators
870  case ISD::LOAD:    std::cerr << "load"; break;
871  case ISD::STORE:   std::cerr << "store"; break;
872  case ISD::DYNAMIC_STACKALLOC: std::cerr << "dynamic_stackalloc"; break;
873  case ISD::EXTRACT_ELEMENT: std::cerr << "extract_element"; break;
874  case ISD::BUILD_PAIR: std::cerr << "build_pair"; break;
875  }
876
877  std::cerr << " ";
878  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
879    if (i) std::cerr << ", ";
880    std::cerr << (void*)getOperand(i).Val;
881    if (unsigned RN = getOperand(i).ResNo)
882      std::cerr << ":" << RN;
883  }
884
885  if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
886    std::cerr << "<" << CSDN->getValue() << ">";
887  } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
888    std::cerr << "<" << CSDN->getValue() << ">";
889  } else if (const GlobalAddressSDNode *GADN =
890             dyn_cast<GlobalAddressSDNode>(this)) {
891    std::cerr << "<";
892    WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
893  } else if (const FrameIndexSDNode *FIDN =
894	     dyn_cast<FrameIndexSDNode>(this)) {
895    std::cerr << "<" << FIDN->getIndex() << ">";
896  } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
897    std::cerr << "<" << CP->getIndex() << ">";
898  } else if (const BasicBlockSDNode *BBDN =
899	     dyn_cast<BasicBlockSDNode>(this)) {
900    std::cerr << "<";
901    const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
902    if (LBB)
903      std::cerr << LBB->getName() << " ";
904    std::cerr << (const void*)BBDN->getBasicBlock() << ">";
905  } else if (const CopyRegSDNode *C2V = dyn_cast<CopyRegSDNode>(this)) {
906    std::cerr << "<reg #" << C2V->getReg() << ">";
907  } else if (const ExternalSymbolSDNode *ES =
908             dyn_cast<ExternalSymbolSDNode>(this)) {
909    std::cerr << "'" << ES->getSymbol() << "'";
910  } else if (const SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(this)) {
911    std::cerr << " - condition = ";
912    switch (SetCC->getCondition()) {
913    default: assert(0 && "Unknown setcc condition!");
914    case ISD::SETOEQ:  std::cerr << "setoeq"; break;
915    case ISD::SETOGT:  std::cerr << "setogt"; break;
916    case ISD::SETOGE:  std::cerr << "setoge"; break;
917    case ISD::SETOLT:  std::cerr << "setolt"; break;
918    case ISD::SETOLE:  std::cerr << "setole"; break;
919    case ISD::SETONE:  std::cerr << "setone"; break;
920
921    case ISD::SETO:    std::cerr << "seto";  break;
922    case ISD::SETUO:   std::cerr << "setuo"; break;
923    case ISD::SETUEQ:  std::cerr << "setue"; break;
924    case ISD::SETUGT:  std::cerr << "setugt"; break;
925    case ISD::SETUGE:  std::cerr << "setuge"; break;
926    case ISD::SETULT:  std::cerr << "setult"; break;
927    case ISD::SETULE:  std::cerr << "setule"; break;
928    case ISD::SETUNE:  std::cerr << "setune"; break;
929
930    case ISD::SETEQ:   std::cerr << "seteq"; break;
931    case ISD::SETGT:   std::cerr << "setgt"; break;
932    case ISD::SETGE:   std::cerr << "setge"; break;
933    case ISD::SETLT:   std::cerr << "setlt"; break;
934    case ISD::SETLE:   std::cerr << "setle"; break;
935    case ISD::SETNE:   std::cerr << "setne"; break;
936    }
937  }
938
939}
940
941static void DumpNodes(SDNode *N, unsigned indent) {
942  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
943    if (N->getOperand(i).Val->hasOneUse())
944      DumpNodes(N->getOperand(i).Val, indent+2);
945    else
946      std::cerr << "\n" << std::string(indent+2, ' ')
947                << (void*)N->getOperand(i).Val << ": <multiple use>";
948
949
950  std::cerr << "\n" << std::string(indent, ' ');
951  N->dump();
952}
953
954void SelectionDAG::dump() const {
955  std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
956  std::vector<SDNode*> Nodes(AllNodes);
957  std::sort(Nodes.begin(), Nodes.end());
958
959  for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
960    if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
961      DumpNodes(Nodes[i], 2);
962  }
963
964  DumpNodes(getRoot().Val, 2);
965
966  std::cerr << "\n\n";
967}
968
969