SelectionDAG.cpp revision 68dc3109420f38d639fb2e9fed6f1a29df60795b
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  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
402      MVT::isInteger(N1.getValueType())) {
403    if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
404        N1.getOpcode() == ISD::XOR) {
405      // Simplify (X+Y) == (X+Z) -->  Y == Z
406      if (N1.getOpcode() == N2.getOpcode()) {
407        if (N1.getOperand(0) == N2.getOperand(0))
408          return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1));
409        if (N1.getOperand(1) == N2.getOperand(1))
410          return getSetCC(Cond, N1.getOperand(0), N2.getOperand(0));
411        if (isCommutativeBinOp(N1.getOpcode())) {
412          // If X op Y == Y op X, try other combinations.
413          if (N1.getOperand(0) == N2.getOperand(1))
414            return getSetCC(Cond, N1.getOperand(1), N2.getOperand(0));
415          if (N1.getOperand(1) == N2.getOperand(0))
416            return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1));
417        }
418      }
419
420      // Simplify (X+Z) == X -->  Z == 0
421      if (N1.getOperand(0) == N2)
422        return getSetCC(Cond, N1.getOperand(1),
423                        getConstant(0, N1.getValueType()));
424      if (N1.getOperand(1) == N2) {
425        if (isCommutativeBinOp(N1.getOpcode()))
426          return getSetCC(Cond, N1.getOperand(0),
427                          getConstant(0, N1.getValueType()));
428        else {
429          assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
430          // (Z-X) == X  --> Z == X<<1
431          return getSetCC(Cond, N1.getOperand(0),
432                          getNode(ISD::SHL, N2.getValueType(),
433                                  N2, getConstant(1, MVT::i8)));
434        }
435      }
436    }
437
438    if (N2.getOpcode() == ISD::ADD || N2.getOpcode() == ISD::SUB ||
439        N2.getOpcode() == ISD::XOR) {
440      // Simplify  X == (X+Z) -->  Z == 0
441      if (N2.getOperand(0) == N1)
442        return getSetCC(Cond, N2.getOperand(1),
443                        getConstant(0, N2.getValueType()));
444      else if (N2.getOperand(1) == N1)
445        return getSetCC(Cond, N2.getOperand(0),
446                        getConstant(0, N2.getValueType()));
447    }
448  }
449
450  SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)];
451  if (N) return SDOperand(N, 0);
452  N = new SetCCSDNode(Cond, N1, N2);
453  AllNodes.push_back(N);
454  return SDOperand(N, 0);
455}
456
457
458
459/// getNode - Gets or creates the specified node.
460///
461SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
462  SDNode *N = new SDNode(Opcode, VT);
463  AllNodes.push_back(N);
464  return SDOperand(N, 0);
465}
466
467static const Type *getTypeFor(MVT::ValueType VT) {
468  switch (VT) {
469  default: assert(0 && "Unknown MVT!");
470  case MVT::i1: return Type::BoolTy;
471  case MVT::i8: return Type::UByteTy;
472  case MVT::i16: return Type::UShortTy;
473  case MVT::i32: return Type::UIntTy;
474  case MVT::i64: return Type::ULongTy;
475  case MVT::f32: return Type::FloatTy;
476  case MVT::f64: return Type::DoubleTy;
477  }
478}
479
480SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
481                                SDOperand Operand) {
482  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
483    uint64_t Val = C->getValue();
484    switch (Opcode) {
485    default: break;
486    case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
487    case ISD::ZERO_EXTEND: return getConstant(Val, VT);
488    case ISD::TRUNCATE:    return getConstant(Val, VT);
489    case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
490    case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
491    }
492  }
493
494  if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
495    switch (Opcode) {
496    case ISD::FP_ROUND:
497    case ISD::FP_EXTEND:
498      return getConstantFP(C->getValue(), VT);
499    case ISD::FP_TO_SINT:
500      return getConstant((int64_t)C->getValue(), VT);
501    case ISD::FP_TO_UINT:
502      return getConstant((uint64_t)C->getValue(), VT);
503    }
504
505  unsigned OpOpcode = Operand.Val->getOpcode();
506  switch (Opcode) {
507  case ISD::SIGN_EXTEND:
508    if (Operand.getValueType() == VT) return Operand;   // noop extension
509    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
510      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
511    break;
512  case ISD::ZERO_EXTEND:
513    if (Operand.getValueType() == VT) return Operand;   // noop extension
514    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
515      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
516    break;
517  case ISD::TRUNCATE:
518    if (Operand.getValueType() == VT) return Operand;   // noop truncate
519    if (OpOpcode == ISD::TRUNCATE)
520      return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
521    else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) {
522      // If the source is smaller than the dest, we still need an extend.
523      if (Operand.Val->getOperand(0).getValueType() < VT)
524        return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
525      else if (Operand.Val->getOperand(0).getValueType() > VT)
526        return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
527      else
528        return Operand.Val->getOperand(0);
529    }
530    break;
531  }
532
533  SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
534  if (N) return SDOperand(N, 0);
535  N = new SDNode(Opcode, Operand);
536  N->setValueTypes(VT);
537  AllNodes.push_back(N);
538  return SDOperand(N, 0);
539}
540
541SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
542                                SDOperand N1, SDOperand N2) {
543  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
544  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
545  if (N1C) {
546    if (N2C) {
547      uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
548      switch (Opcode) {
549      case ISD::ADD: return getConstant(C1 + C2, VT);
550      case ISD::SUB: return getConstant(C1 - C2, VT);
551      case ISD::MUL: return getConstant(C1 * C2, VT);
552      case ISD::UDIV:
553        if (C2) return getConstant(C1 / C2, VT);
554        break;
555      case ISD::UREM :
556        if (C2) return getConstant(C1 % C2, VT);
557        break;
558      case ISD::SDIV :
559        if (C2) return getConstant(N1C->getSignExtended() /
560                                   N2C->getSignExtended(), VT);
561        break;
562      case ISD::SREM :
563        if (C2) return getConstant(N1C->getSignExtended() %
564                                   N2C->getSignExtended(), VT);
565        break;
566      case ISD::AND  : return getConstant(C1 & C2, VT);
567      case ISD::OR   : return getConstant(C1 | C2, VT);
568      case ISD::XOR  : return getConstant(C1 ^ C2, VT);
569      case ISD::SHL  : return getConstant(C1 << (int)C2, VT);
570      case ISD::SRL  : return getConstant(C1 >> (unsigned)C2, VT);
571      case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
572      default: break;
573      }
574
575    } else {      // Cannonicalize constant to RHS if commutative
576      if (isCommutativeBinOp(Opcode)) {
577        std::swap(N1C, N2C);
578        std::swap(N1, N2);
579      }
580    }
581  }
582
583  if (N2C) {
584    uint64_t C2 = N2C->getValue();
585
586    switch (Opcode) {
587    case ISD::ADD:
588      if (!C2) return N1;         // add X, 0 -> X
589      break;
590    case ISD::SUB:
591      if (!C2) return N1;         // sub X, 0 -> X
592      break;
593    case ISD::MUL:
594      if (!C2) return N2;         // mul X, 0 -> 0
595      if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X
596        return getNode(ISD::SUB, VT, getConstant(0, VT), N1);
597
598      // FIXME: This should only be done if the target supports shift
599      // operations.
600      if ((C2 & C2-1) == 0) {
601        SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
602        return getNode(ISD::SHL, VT, N1, ShAmt);
603      }
604      break;
605
606    case ISD::UDIV:
607      // FIXME: This should only be done if the target supports shift
608      // operations.
609      if ((C2 & C2-1) == 0 && C2) {
610        SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
611        return getNode(ISD::SRL, VT, N1, ShAmt);
612      }
613      break;
614
615    case ISD::AND:
616      if (!C2) return N2;         // X and 0 -> 0
617      if (N2C->isAllOnesValue())
618	return N1;                // X and -1 -> X
619      break;
620    case ISD::OR:
621      if (!C2)return N1;          // X or 0 -> X
622      if (N2C->isAllOnesValue())
623	return N2;                // X or -1 -> -1
624      break;
625    case ISD::XOR:
626      if (!C2) return N1;        // X xor 0 -> X
627      if (N2C->isAllOnesValue()) {
628        if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){
629          // !(X op Y) -> (X !op Y)
630          bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
631          return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger),
632                          SetCC->getOperand(0), SetCC->getOperand(1));
633        } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
634          SDNode *Op = N1.Val;
635          // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
636          // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
637          SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
638          if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
639            LHS = getNode(ISD::XOR, VT, LHS, N2);  // RHS = ~LHS
640            RHS = getNode(ISD::XOR, VT, RHS, N2);  // RHS = ~RHS
641            if (Op->getOpcode() == ISD::AND)
642              return getNode(ISD::OR, VT, LHS, RHS);
643            return getNode(ISD::AND, VT, LHS, RHS);
644          }
645        }
646	// X xor -1 -> not(x)  ?
647      }
648      break;
649    }
650
651    // Reassociate ((X op C1) op C2) if possible.
652    if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
653      if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
654        return getNode(Opcode, VT, N1.Val->getOperand(0),
655                       getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
656  }
657
658  ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
659  ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
660  if (N1CFP)
661    if (N2CFP) {
662      double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
663      switch (Opcode) {
664      case ISD::ADD: return getConstantFP(C1 + C2, VT);
665      case ISD::SUB: return getConstantFP(C1 - C2, VT);
666      case ISD::MUL: return getConstantFP(C1 * C2, VT);
667      case ISD::SDIV:
668        if (C2) return getConstantFP(C1 / C2, VT);
669        break;
670      case ISD::SREM :
671        if (C2) return getConstantFP(fmod(C1, C2), VT);
672        break;
673      default: break;
674      }
675
676    } else {      // Cannonicalize constant to RHS if commutative
677      if (isCommutativeBinOp(Opcode)) {
678        std::swap(N1CFP, N2CFP);
679        std::swap(N1, N2);
680      }
681    }
682
683  // Finally, fold operations that do not require constants.
684  switch (Opcode) {
685  case ISD::AND:
686  case ISD::OR:
687    if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val))
688      if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) {
689        SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
690        SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
691        ISD::CondCode Op2 = RHS->getCondition();
692
693        // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
694        if (LL == RR && LR == RL) {
695          Op2 = ISD::getSetCCSwappedOperands(Op2);
696          goto MatchedBackwards;
697        }
698
699        if (LL == RL && LR == RR) {
700        MatchedBackwards:
701          ISD::CondCode Result;
702          bool isInteger = MVT::isInteger(LL.getValueType());
703          if (Opcode == ISD::OR)
704            Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2,
705                                              isInteger);
706          else
707            Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2,
708                                               isInteger);
709          if (Result != ISD::SETCC_INVALID)
710            return getSetCC(Result, LL, LR);
711        }
712      }
713    break;
714  case ISD::XOR:
715    if (N1 == N2) return getConstant(0, VT);  // xor X, Y -> 0
716    break;
717  case ISD::SUB:
718    if (N1.getOpcode() == ISD::ADD) {
719      if (N1.Val->getOperand(0) == N2)
720        return N1.Val->getOperand(1);         // (A+B)-A == B
721      if (N1.Val->getOperand(1) == N2)
722        return N1.Val->getOperand(0);         // (A+B)-B == A
723    }
724    break;
725  }
726
727  SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
728  if (N) return SDOperand(N, 0);
729  N = new SDNode(Opcode, N1, N2);
730  N->setValueTypes(VT);
731
732  AllNodes.push_back(N);
733  return SDOperand(N, 0);
734}
735
736SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
737                                SDOperand Chain, SDOperand Ptr) {
738  SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
739  if (N) return SDOperand(N, 0);
740  N = new SDNode(ISD::LOAD, Chain, Ptr);
741
742  // Loads have a token chain.
743  N->setValueTypes(VT, MVT::Other);
744  AllNodes.push_back(N);
745  return SDOperand(N, 0);
746}
747
748
749SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
750                                SDOperand N1, SDOperand N2, SDOperand N3) {
751  // Perform various simplifications.
752  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
753  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
754  ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
755  switch (Opcode) {
756  case ISD::SELECT:
757    if (N1C)
758      if (N1C->getValue())
759        return N2;             // select true, X, Y -> X
760      else
761        return N3;             // select false, X, Y -> Y
762
763    if (N2 == N3) return N2;   // select C, X, X -> X
764
765    if (VT == MVT::i1) {  // Boolean SELECT
766      if (N2C) {
767        if (N3C) {
768          if (N2C->getValue()) // select C, 1, 0 -> C
769            return N1;
770          return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C
771        }
772
773        if (N2C->getValue())   // select C, 1, X -> C | X
774          return getNode(ISD::OR, VT, N1, N3);
775        else                   // select C, 0, X -> ~C & X
776          return getNode(ISD::AND, VT,
777                         getNode(ISD::XOR, N1.getValueType(), N1,
778                                 getConstant(1, N1.getValueType())), N3);
779      } else if (N3C) {
780        if (N3C->getValue())   // select C, X, 1 -> ~C | X
781          return getNode(ISD::OR, VT,
782                         getNode(ISD::XOR, N1.getValueType(), N1,
783                                 getConstant(1, N1.getValueType())), N2);
784        else                   // select C, X, 0 -> C & X
785          return getNode(ISD::AND, VT, N1, N2);
786      }
787    }
788
789    break;
790  case ISD::BRCOND:
791    if (N2C)
792      if (N2C->getValue()) // Unconditional branch
793        return getNode(ISD::BR, MVT::Other, N1, N3);
794      else
795        return N1;         // Never-taken branch
796    break;
797  }
798
799  SDNode *N = new SDNode(Opcode, N1, N2, N3);
800  switch (Opcode) {
801  default:
802    N->setValueTypes(VT);
803    break;
804  case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain
805    N->setValueTypes(VT, MVT::Other);
806    break;
807  }
808
809  // FIXME: memoize NODES
810  AllNodes.push_back(N);
811  return SDOperand(N, 0);
812}
813
814SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
815                                std::vector<SDOperand> &Children) {
816  switch (Children.size()) {
817  case 0: return getNode(Opcode, VT);
818  case 1: return getNode(Opcode, VT, Children[0]);
819  case 2: return getNode(Opcode, VT, Children[0], Children[1]);
820  case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]);
821  default:
822    // FIXME: MEMOIZE!!
823    SDNode *N = new SDNode(Opcode, Children);
824    N->setValueTypes(VT);
825    AllNodes.push_back(N);
826    return SDOperand(N, 0);
827  }
828}
829
830
831
832void SDNode::dump() const {
833  std::cerr << (void*)this << ": ";
834
835  for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
836    if (i) std::cerr << ",";
837    switch (getValueType(i)) {
838    default: assert(0 && "Unknown value type!");
839    case MVT::i1:    std::cerr << "i1"; break;
840    case MVT::i8:    std::cerr << "i8"; break;
841    case MVT::i16:   std::cerr << "i16"; break;
842    case MVT::i32:   std::cerr << "i32"; break;
843    case MVT::i64:   std::cerr << "i64"; break;
844    case MVT::f32:   std::cerr << "f32"; break;
845    case MVT::f64:   std::cerr << "f64"; break;
846    case MVT::Other: std::cerr << "ch"; break;
847    }
848  }
849  std::cerr << " = ";
850
851  switch (getOpcode()) {
852  default: std::cerr << "<<Unknown>>"; break;
853  case ISD::EntryToken:    std::cerr << "EntryToken"; break;
854  case ISD::Constant:      std::cerr << "Constant"; break;
855  case ISD::ConstantFP:    std::cerr << "ConstantFP"; break;
856  case ISD::GlobalAddress: std::cerr << "GlobalAddress"; break;
857  case ISD::FrameIndex:    std::cerr << "FrameIndex"; break;
858  case ISD::BasicBlock:    std::cerr << "BasicBlock"; break;
859  case ISD::ExternalSymbol: std::cerr << "ExternalSymbol"; break;
860  case ISD::ConstantPool:  std::cerr << "ConstantPoolIndex"; break;
861  case ISD::CopyToReg:     std::cerr << "CopyToReg"; break;
862  case ISD::CopyFromReg:   std::cerr << "CopyFromReg"; break;
863
864  case ISD::ADD:    std::cerr << "add"; break;
865  case ISD::SUB:    std::cerr << "sub"; break;
866  case ISD::MUL:    std::cerr << "mul"; break;
867  case ISD::SDIV:   std::cerr << "sdiv"; break;
868  case ISD::UDIV:   std::cerr << "udiv"; break;
869  case ISD::SREM:   std::cerr << "srem"; break;
870  case ISD::UREM:   std::cerr << "urem"; break;
871  case ISD::AND:    std::cerr << "and"; break;
872  case ISD::OR:     std::cerr << "or"; break;
873  case ISD::XOR:    std::cerr << "xor"; break;
874  case ISD::SHL:    std::cerr << "shl"; break;
875  case ISD::SRA:    std::cerr << "sra"; break;
876  case ISD::SRL:    std::cerr << "srl"; break;
877
878  case ISD::SETCC:  std::cerr << "setcc"; break;
879  case ISD::SELECT: std::cerr << "select"; break;
880  case ISD::ADDC:   std::cerr << "addc"; break;
881  case ISD::SUBB:   std::cerr << "subb"; break;
882
883    // Conversion operators.
884  case ISD::SIGN_EXTEND: std::cerr << "sign_extend"; break;
885  case ISD::ZERO_EXTEND: std::cerr << "zero_extend"; break;
886  case ISD::TRUNCATE:    std::cerr << "truncate"; break;
887  case ISD::FP_ROUND:    std::cerr << "fp_round"; break;
888  case ISD::FP_EXTEND:   std::cerr << "fp_extend"; break;
889
890  case ISD::SINT_TO_FP:  std::cerr << "sint_to_fp"; break;
891  case ISD::UINT_TO_FP:  std::cerr << "uint_to_fp"; break;
892  case ISD::FP_TO_SINT:  std::cerr << "fp_to_sint"; break;
893  case ISD::FP_TO_UINT:  std::cerr << "fp_to_uint"; break;
894
895    // Control flow instructions
896  case ISD::BR:      std::cerr << "br"; break;
897  case ISD::BRCOND:  std::cerr << "brcond"; break;
898  case ISD::RET:     std::cerr << "ret"; break;
899  case ISD::CALL:    std::cerr << "call"; break;
900  case ISD::ADJCALLSTACKDOWN:  std::cerr << "adjcallstackdown"; break;
901  case ISD::ADJCALLSTACKUP:    std::cerr << "adjcallstackup"; break;
902
903    // Other operators
904  case ISD::LOAD:    std::cerr << "load"; break;
905  case ISD::STORE:   std::cerr << "store"; break;
906  case ISD::DYNAMIC_STACKALLOC: std::cerr << "dynamic_stackalloc"; break;
907  case ISD::EXTRACT_ELEMENT: std::cerr << "extract_element"; break;
908  case ISD::BUILD_PAIR: std::cerr << "build_pair"; break;
909  }
910
911  std::cerr << " ";
912  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
913    if (i) std::cerr << ", ";
914    std::cerr << (void*)getOperand(i).Val;
915    if (unsigned RN = getOperand(i).ResNo)
916      std::cerr << ":" << RN;
917  }
918
919  if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
920    std::cerr << "<" << CSDN->getValue() << ">";
921  } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
922    std::cerr << "<" << CSDN->getValue() << ">";
923  } else if (const GlobalAddressSDNode *GADN =
924             dyn_cast<GlobalAddressSDNode>(this)) {
925    std::cerr << "<";
926    WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
927  } else if (const FrameIndexSDNode *FIDN =
928	     dyn_cast<FrameIndexSDNode>(this)) {
929    std::cerr << "<" << FIDN->getIndex() << ">";
930  } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
931    std::cerr << "<" << CP->getIndex() << ">";
932  } else if (const BasicBlockSDNode *BBDN =
933	     dyn_cast<BasicBlockSDNode>(this)) {
934    std::cerr << "<";
935    const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
936    if (LBB)
937      std::cerr << LBB->getName() << " ";
938    std::cerr << (const void*)BBDN->getBasicBlock() << ">";
939  } else if (const CopyRegSDNode *C2V = dyn_cast<CopyRegSDNode>(this)) {
940    std::cerr << "<reg #" << C2V->getReg() << ">";
941  } else if (const ExternalSymbolSDNode *ES =
942             dyn_cast<ExternalSymbolSDNode>(this)) {
943    std::cerr << "'" << ES->getSymbol() << "'";
944  } else if (const SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(this)) {
945    std::cerr << " - condition = ";
946    switch (SetCC->getCondition()) {
947    default: assert(0 && "Unknown setcc condition!");
948    case ISD::SETOEQ:  std::cerr << "setoeq"; break;
949    case ISD::SETOGT:  std::cerr << "setogt"; break;
950    case ISD::SETOGE:  std::cerr << "setoge"; break;
951    case ISD::SETOLT:  std::cerr << "setolt"; break;
952    case ISD::SETOLE:  std::cerr << "setole"; break;
953    case ISD::SETONE:  std::cerr << "setone"; break;
954
955    case ISD::SETO:    std::cerr << "seto";  break;
956    case ISD::SETUO:   std::cerr << "setuo"; break;
957    case ISD::SETUEQ:  std::cerr << "setue"; break;
958    case ISD::SETUGT:  std::cerr << "setugt"; break;
959    case ISD::SETUGE:  std::cerr << "setuge"; break;
960    case ISD::SETULT:  std::cerr << "setult"; break;
961    case ISD::SETULE:  std::cerr << "setule"; break;
962    case ISD::SETUNE:  std::cerr << "setune"; break;
963
964    case ISD::SETEQ:   std::cerr << "seteq"; break;
965    case ISD::SETGT:   std::cerr << "setgt"; break;
966    case ISD::SETGE:   std::cerr << "setge"; break;
967    case ISD::SETLT:   std::cerr << "setlt"; break;
968    case ISD::SETLE:   std::cerr << "setle"; break;
969    case ISD::SETNE:   std::cerr << "setne"; break;
970    }
971  }
972
973}
974
975static void DumpNodes(SDNode *N, unsigned indent) {
976  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
977    if (N->getOperand(i).Val->hasOneUse())
978      DumpNodes(N->getOperand(i).Val, indent+2);
979    else
980      std::cerr << "\n" << std::string(indent+2, ' ')
981                << (void*)N->getOperand(i).Val << ": <multiple use>";
982
983
984  std::cerr << "\n" << std::string(indent, ' ');
985  N->dump();
986}
987
988void SelectionDAG::dump() const {
989  std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
990  std::vector<SDNode*> Nodes(AllNodes);
991  std::sort(Nodes.begin(), Nodes.end());
992
993  for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
994    if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
995      DumpNodes(Nodes[i], 2);
996  }
997
998  DumpNodes(getRoot().Val, 2);
999
1000  std::cerr << "\n\n";
1001}
1002
1003