Complete rewrite of the SelectionDAG class.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@19327 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 864 insertions, 425 deletions

diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 796ee13535..ce5deecf38 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -1,4 +1,4 @@
-//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===//
+//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
 // 
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,364 +7,151 @@
 // 
 //===----------------------------------------------------------------------===//
 // 
-// This file declares the SelectionDAG class, which is used to represent an LLVM
-// function in a low-level representation suitable for instruction selection.
-// This DAG is constructed as the first step of instruction selection in order
-// to allow implementation of machine specific optimizations and code
-// simplifications.
-//
-// The representation used by the SelectionDAG is a target-independent
-// representation, which is loosly modeled after the GCC RTL representation, but
-// is significantly simpler.
+// This file declares the SelectionDAG class, and transitively defines the
+// SDNode class and subclasses.
 //   
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
 #define LLVM_CODEGEN_SELECTIONDAG_H
 
-#include "llvm/CodeGen/ValueTypes.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/CodeGen/SelectionDAGNodes.h"
 #include <map>
-#include <vector>
-#include <cassert>
+#include <string> // FIXME remove eventually, turning map into const char* map.
 
 namespace llvm {
-
-class Value;
-class Type;
-class Instruction;
-class CallInst;
-class BasicBlock;
-class MachineBasicBlock;
-class MachineFunction;
-class TargetMachine;
-class SelectionDAGNode;
-class SelectionDAGBlock;
-class SelectionDAGBuilder;
-class SelectionDAGTargetBuilder;
-
-/// ISD namespace - This namespace contains an enum which represents all of the
-/// SelectionDAG node types and value types.
+  class TargetLowering;
+  class TargetMachine;
+  class MachineFunction;
+
+/// SelectionDAG class - This is used to represent a portion of an LLVM function
+/// in a low-level Data Dependence DAG representation suitable for instruction
+/// selection.  This DAG is constructed as the first step of instruction
+/// selection in order to allow implementation of machine specific optimizations
+/// and code simplifications.
+///
+/// The representation used by the SelectionDAG is a target-independent
+/// representation, which has some similarities to the GCC RTL representation,
+/// but is significantly more simple, powerful, and is a graph form instead of a
+/// linear form.
 ///
-namespace ISD {
-  enum NodeType {
-    // ChainNode nodes are used to sequence operations within a basic block
-    // which cannot be reordered (such as loads, stores, calls, etc).
-    // BlockChainNodes are used to connect the DAG's for different basic blocks
-    // into one big DAG.
-    ChainNode, BlockChainNode,
-
-    // ProtoNodes are nodes that are only half way constructed.
-    ProtoNode,
-
-    // Leaf nodes
-    Constant, FrameIndex, BasicBlock,
-
-    // Simple binary arithmetic operators
-    Plus, Minus, Times, SDiv, UDiv, SRem, URem,
-
-    // Bitwise operators
-    And, Or, Xor,
-
-    // Comparisons
-    SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE,
-
-    // Control flow instructions
-    Br, BrCond, Switch, Ret, RetVoid,
-
-    // Other operators
-    Load, Store, PHI, Call,
-
-    // Unknown operators, of a specified arity
-    Unspec1, Unspec2
-  };
-}
-
 class SelectionDAG {
-  friend class SelectionDAGBuilder;
-  MachineFunction &F;
   const TargetMachine &TM;
-  MVT::ValueType PointerType;    // The ValueType the target uses for pointers
+  MachineFunction &MF;
 
-  // ValueMap - The SelectionDAGNode for each LLVM value in the function.
-  std::map<const Value*, SelectionDAGNode*> ValueMap;
-
-  // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock
-  std::map<const BasicBlock*, MachineBasicBlock*> BlockMap;
-
-  // Root - The root of the entire DAG
-  SelectionDAGNode *Root;
+  // Root - The root of the entire DAG.  EntryNode - The starting token.
+  SDOperand Root, EntryNode;
 
   // AllNodes - All of the nodes in the DAG
-  std::vector<SelectionDAGNode*> AllNodes;
+  std::vector<SDNode*> AllNodes;
+
+  // Maps to auto-CSE operations.
+  std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >,
+           SDNode *> UnaryOps;
+  std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >,
+           SDNode *> BinaryOps;
+
+  std::map<std::pair<std::pair<SDOperand, SDOperand>, ISD::CondCode>,
+           SetCCSDNode*> SetCCs;
+
+  std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >,
+           SDNode *> Loads;
+
+  std::map<const GlobalValue*, SDNode*> GlobalValues;
+  std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants;
+  std::map<std::pair<double, MVT::ValueType>, SDNode*> ConstantFPs;
+  std::map<int, SDNode*> FrameIndices;
+  std::map<unsigned, SDNode*> ConstantPoolIndices;
+  std::map<MachineBasicBlock *, SDNode*> BBNodes;
+  std::map<std::string, SDNode*> ExternalSymbols;
 public:
-  /// SelectionDAG constructor - Build a SelectionDAG for the specified
-  /// function.  Implemented in DAGBuilder.cpp
-  ///
-  SelectionDAG(MachineFunction &F, const TargetMachine &TM,
-               SelectionDAGTargetBuilder &SDTB);
+  SelectionDAG(const TargetMachine &tm, MachineFunction &mf) : TM(tm), MF(mf) {
+    EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
+  }
   ~SelectionDAG();
 
-  /// getValueType - Return the ValueType for the specified LLVM type.  This
-  /// method works on all scalar LLVM types.
-  ///
-  MVT::ValueType getValueType(const Type *Ty) const;
-
-  /// getRoot - Return the root of the current SelectionDAG.
-  ///
-  SelectionDAGNode *getRoot() const { return Root; }
+  MachineFunction &getMachineFunction() const { return MF; }
+  const TargetMachine &getTarget() { return TM; }
 
-  /// getMachineFunction - Return the MachineFunction object that this
-  /// SelectionDAG corresponds to.
+  /// getRoot - Return the root tag of the SelectionDAG.
   ///
-  MachineFunction &getMachineFunction() const { return F; }
+  const SDOperand &getRoot() const { return Root; }
 
-  //===--------------------------------------------------------------------===//
-  // Addition and updating methods
-  //
+  /// getEntryNode - Return the token chain corresponding to the entry of the
+  /// function.
+  const SDOperand &getEntryNode() const { return EntryNode; }
 
-  /// addNode - Add the specified node to the SelectionDAG so that it will be
-  /// deleted when the DAG is...
+  /// setRoot - Set the current root tag of the SelectionDAG.
   ///
-  SelectionDAGNode *addNode(SelectionDAGNode *N) {
-    AllNodes.push_back(N);
-    return N;
-  }
+  const SDOperand &setRoot(SDOperand N) { return Root = N; }
 
-  /// addNodeForValue - Add the specified node to the SelectionDAG so that it
-  /// will be deleted when the DAG is... and update the value map to indicate
-  /// that the specified DAG node computes the value.  Note that it is an error
-  /// to specify multiple DAG nodes that compute the same value.
+  /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
+  /// compatible with the target instruction selector, as indicated by the
+  /// TargetLowering object.
   ///
-  SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) {
-    assert(ValueMap.count(V) == 0 && "Value already has a DAG node!");
-    return addNode(ValueMap[V] = N);
+  /// Note that this is an involved process that may invalidate pointers into
+  /// the graph.
+  void Legalize(TargetLowering &TLI);
+
+  SDOperand getConstant(uint64_t Val, MVT::ValueType VT);
+  SDOperand getConstantFP(double Val, MVT::ValueType VT);
+  SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT);
+  SDOperand getFrameIndex(int FI, MVT::ValueType VT);
+  SDOperand getConstantPool(unsigned CPIdx, MVT::ValueType VT);
+  SDOperand getBasicBlock(MachineBasicBlock *MBB);
+  SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT);
+
+  SDOperand getCopyToReg(SDOperand Chain, SDOperand N, unsigned VReg) {
+    // Note: these are auto-CSE'd because the caller doesn't make requests that
+    // could cause duplicates to occur.
+    SDNode *NN = new CopyRegSDNode(Chain, N, VReg);
+    AllNodes.push_back(NN);
+    return SDOperand(NN, 0);
   }
 
-  void dump() const;
-private:
-  void addInstructionToDAG(const Instruction &I, const BasicBlock &BB);
-};
-
-
-/// SelectionDAGReducedValue - During the reducer pass we need the ability to
-/// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to
-/// the selection DAG.  Because of this, we represent these values as a singly
-/// linked list of values attached to the DAGNode.  We end up putting the
-/// arbitrary state for the value in subclasses of this node.
-///
-/// Note that this class does not have a virtual dtor, this is because we know
-/// that the subclasses will not hold state that needs to be destroyed.
-///
-class SelectionDAGReducedValue {
-  unsigned Code;
-  SelectionDAGReducedValue *Next;
-public:
-  SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {}
-
-  /// getValueCode - Return the code for this reducer value...
-  ///
-  unsigned getValueCode() const { return Code; }
-  
-  /// getNext - Return the next value in the list
-  ///
-  const SelectionDAGReducedValue *getNext() const { return Next; }
-  void setNext(SelectionDAGReducedValue *N) { Next = N; }
-
-  SelectionDAGReducedValue *getNext() { return Next; }
-};
-
-
-
-/// SelectionDAGNode - Represents one node in the selection DAG.
-///
-class SelectionDAGNode {
-  std::vector<SelectionDAGNode*> Uses;
-  ISD::NodeType  NodeType;
-  MVT::ValueType ValueType;
-  MachineBasicBlock *BB;
-  SelectionDAGReducedValue *ValList;
-
-  /// Costs - Each pair of elements of 'Costs' contains the cost of producing
-  /// the value with the target specific slot number and the production number
-  /// to use to produce it.  A zero value for the production number indicates
-  /// that the cost has not yet been computed.
-  unsigned *Costs;
-public:
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT,
-                   MachineBasicBlock *bb = 0) 
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {}
-
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
-                   SelectionDAGNode *N)
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
-    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
-    Uses.reserve(1); Uses.push_back(N);
-  }
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
-                   SelectionDAGNode *N1, SelectionDAGNode *N2)
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
-    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
-    Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2);
-  }
-  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
-                   SelectionDAGNode *N1, SelectionDAGNode *N2,
-                   SelectionDAGNode *N3)
-    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
-    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
-    Uses.reserve(3); Uses.push_back(N1); Uses.push_back(N2); Uses.push_back(N3);
-  }
-
-  ~SelectionDAGNode() { delete [] Costs; delete ValList; }
-
-  void setNode(ISD::NodeType NT, MachineBasicBlock *bb) {
-    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
-    NodeType = NT; BB = bb;
-  }
-  void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) {
-    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
-    NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N);
-  }
-  void setNode(ISD::NodeType NT, MachineBasicBlock *bb, 
-               SelectionDAGNode *N1, SelectionDAGNode *N2) {
-    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
-    NodeType = NT; BB = bb;
-    Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2);
+  SDOperand getCopyFromReg(unsigned VReg, MVT::ValueType VT) {
+    // Note: These nodes are auto-CSE'd by the caller of this method.
+    SDNode *NN = new CopyRegSDNode(VReg, VT);
+    AllNodes.push_back(NN);
+    return SDOperand(NN, 0);
   }
 
-  //===--------------------------------------------------------------------===//
-  //  Accessors
-  //
-  ISD::NodeType  getNodeType()  const { return NodeType; }
-  MVT::ValueType getValueType() const { return ValueType; }
-  MachineBasicBlock *getBB() const { return BB; }
-
-  SelectionDAGNode *getUse(unsigned Num) {
-    assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!");
-    return Uses[Num];
-  }
-
-  template<class Type>
-  Type *getValue(unsigned Code) const {
-    SelectionDAGReducedValue *Vals = ValList;
-    while (1) {
-      assert(Vals && "Code does not exist in this list!");
-      if (Vals->getValueCode() == Code)
-        return (Type*)Vals;
-      Vals = Vals->getNext();
-    }
-  }
-
-  template<class Type>
-  Type *hasValue(unsigned Code) const {
-    SelectionDAGReducedValue *Vals = ValList;
-    while (Vals) {
-      if (Vals->getValueCode() == Code)
-        return (Type*)Vals;
-      Vals = Vals->getNext();
-    }
-    return false;
-  }
-
-  void addValue(SelectionDAGReducedValue *New) {
-    assert(New->getNext() == 0);
-    New->setNext(ValList);
-    ValList = New;
+  /// getCall - Note that this destroys the vector of RetVals passed in.
+  ///
+  SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
+                  SDOperand Callee) {
+    SDNode *NN = new SDNode(ISD::CALL, Chain, Callee);
+    NN->setValueTypes(RetVals);
+    AllNodes.push_back(NN);
+    return NN;
   }
 
-  //===--------------------------------------------------------------------===//
-  // Utility methods used by the pattern matching instruction selector
-  //
+  SDOperand getSetCC(ISD::CondCode, SDOperand LHS, SDOperand RHS);
 
-  /// getPatternFor - Return the pattern selected to compute the specified slot,
-  /// or zero if there is no pattern yet.
+  /// getNode - Gets or creates the specified node.
   ///
-  unsigned getPatternFor(unsigned Slot) const {
-    return Costs ? Costs[Slot*2] : 0;
-  }
-
-  /// getCostFor - Return the cost to compute the value corresponding to Slot.
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
+                    SDOperand N1, SDOperand N2);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
+                    SDOperand N1, SDOperand N2, SDOperand N3);
+  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
+                    std::vector<SDOperand> &Children);
+
+  /// getLoad - Loads are not normal binary operators: their result type is not
+  /// determined by their operands, and they produce a value AND a token chain.
   ///
-  unsigned getCostFor(unsigned Slot) const {
-    return Costs ? Costs[Slot*2+1] : 0;
-  }
+  SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr);
 
-  /// setPatternCostFor - Sets the pattern and the cost for the specified slot
-  /// to the specified values.  This allocates the Costs vector if necessary, so
-  /// you must specify the maximum number of slots that may be used.
-  ///
-  void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost,
-                         unsigned NumSlots) {
-    if (Costs == 0) {
-      Costs = new unsigned[NumSlots*2];
-      for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0;
-    }
-    Costs[Slot*2] = Pattern;
-    Costs[Slot*2+1] = Cost;
+  void replaceAllUsesWith(SDOperand Old, SDOperand New) {
+    assert(Old != New && "RAUW self!");
+    assert(0 && "Unimplemented!");
   }
 
   void dump() const;
-private:
-  void printit(unsigned Offset, unsigned &LastID,
-               std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const;
 };
 
-
-/// SelectionDAGTargetBuilder - This class must be implemented by the target, to
-/// indicate how to perform the extremely target-specific tasks of building DAG
-/// nodes to represent the calling convention used by the target.
-///
-struct SelectionDAGTargetBuilder {
-  /// expandArguments - This method is called once by the SelectionDAG
-  /// construction mechanisms to add DAG nodes for each formal argument to the
-  /// current function.  If any of the incoming arguments lives on the stack,
-  /// this method should also create the stack slots for the arguments as
-  /// necessary.
-  virtual void expandArguments(SelectionDAG &SD) = 0;
-
-  /// expandCall - This method is called once per function call by the
-  /// SelectionDAG construction algorithm.  It must add DAG nodes to the
-  /// SelectionDAG specified to perform that call.
-  virtual void expandCall(SelectionDAG &SD, CallInst &CI) = 0;
-};
-
-namespace ISD {
-  enum {   // Builtin Slot numbers
-    Constant_i1_Slot,
-    Constant_i8_Slot,
-    Constant_i16_Slot,
-    Constant_i32_Slot,
-    Constant_i64_Slot,
-    Constant_f32_Slot,
-    Constant_f64_Slot,
-
-    FrameIndex_i32_Slot,
-    FrameIndex_i64_Slot,
-    BasicBlock_i32_Slot,
-    BasicBlock_i64_Slot,
-    NumBuiltinSlots
-  };
 }
 
-template<typename ValType, unsigned NodeCode>
-struct ReducedValue : public SelectionDAGReducedValue {
-  ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {}
-  ValType Val;
-};
-
-typedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32;
-typedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64;
-typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i32_Slot > ReducedValue_BasicBlock_i32;
-typedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i64_Slot > ReducedValue_BasicBlock_i64;
-
-typedef ReducedValue<bool          , ISD::Constant_i1_Slot > ReducedValue_Constant_i1;
-typedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8;
-typedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16;
-typedef ReducedValue<unsigned      , ISD::Constant_i32_Slot> ReducedValue_Constant_i32;
-typedef ReducedValue<uint64_t      , ISD::Constant_i64_Slot> ReducedValue_Constant_i64;
-typedef ReducedValue<float         , ISD::Constant_f32_Slot> ReducedValue_Constant_f32;
-typedef ReducedValue<double        , ISD::Constant_f64_Slot> ReducedValue_Constant_f64;
-
-} // End llvm namespace
-
 #endif
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index acf3daa32f..f02bdcd95b 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -1,4 +1,4 @@
-//===-- SelectionDAG.cpp - Implement the SelectionDAG* classes ------------===//
+//===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
 // 
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,125 +7,777 @@
 // 
 //===----------------------------------------------------------------------===//
 //
-// This file implements the SelectionDAG* classes, which are used to perform
-// DAG-based instruction selection in a target-specific manner.
+// This implements the SelectionDAG class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/SelectionDAG.h"
-#include "llvm/Type.h"
+#include "llvm/Constants.h"
+#include "llvm/GlobalValue.h"
+#include "llvm/Assembly/Writer.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include <iostream>
-
+#include <cmath>
 using namespace llvm;
 
+/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
+/// when given the operation for (X op Y).
+ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
+  // To perform this operation, we just need to swap the L and G bits of the
+  // operation.
+  unsigned OldL = (Operation >> 2) & 1;
+  unsigned OldG = (Operation >> 1) & 1;
+  return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
+                       (OldL << 1) |       // New G bit
+                       (OldG << 2));        // New L bit.
+}
+
+/// getSetCCInverse - Return the operation corresponding to !(X op Y), where
+/// 'op' is a valid SetCC operation.
+ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
+  unsigned Operation = Op;
+  if (isInteger)
+    Operation ^= 7;   // Flip L, G, E bits, but not U.
+  else
+    Operation ^= 15;  // Flip all of the condition bits.
+  if (Operation > ISD::SETTRUE2)
+    Operation &= ~8;     // Don't let N and U bits get set.
+  return ISD::CondCode(Operation);
+}
+
+
+/// isSignedOp - For an integer comparison, return 1 if the comparison is a
+/// signed operation and 2 if the result is an unsigned comparison.  Return zero
+/// if the operation does not depend on the sign of the input (setne and seteq).
+static int isSignedOp(ISD::CondCode Opcode) {
+  switch (Opcode) {
+  default: assert(0 && "Illegal integer setcc operation!");
+  case ISD::SETEQ:
+  case ISD::SETNE: return 0;
+  case ISD::SETLT:
+  case ISD::SETLE:
+  case ISD::SETGT:
+  case ISD::SETGE: return 1;
+  case ISD::SETULT:
+  case ISD::SETULE:
+  case ISD::SETUGT:
+  case ISD::SETUGE: return 2;
+  }
+}
+
+/// getSetCCOrOperation - Return the result of a logical OR between different
+/// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
+/// returns SETCC_INVALID if it is not possible to represent the resultant
+/// comparison.
+ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
+                                       bool isInteger) {
+  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
+    // Cannot fold a signed integer setcc with an unsigned integer setcc.
+    return ISD::SETCC_INVALID;
+  
+  unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
+  
+  // If the N and U bits get set then the resultant comparison DOES suddenly
+  // care about orderedness, and is true when ordered.
+  if (Op > ISD::SETTRUE2)
+    Op &= ~16;     // Clear the N bit.
+  return ISD::CondCode(Op);
+}
+
+/// getSetCCAndOperation - Return the result of a logical AND between different
+/// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
+/// function returns zero if it is not possible to represent the resultant
+/// comparison.
+ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
+                                        bool isInteger) {
+  if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
+    // Cannot fold a signed setcc with an unsigned setcc.
+    return ISD::SETCC_INVALID; 
+
+  // Combine all of the condition bits.
+  return ISD::CondCode(Op1 & Op2);
+}
+
 SelectionDAG::~SelectionDAG() {
   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
     delete AllNodes[i];
 }
 
+SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
+  assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
+  // Mask out any bits that are not valid for this constant.
+  Val &= (1ULL << MVT::getSizeInBits(VT)) - 1;
 
-/// dump - Print out the current Selection DAG...
-void SelectionDAG::dump() const {
-  Root->dump();  // Print from the root...
+  SDNode *&N = Constants[std::make_pair(Val, VT)];
+  if (N) return SDOperand(N, 0);
+  N = new ConstantSDNode(Val, VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
 }
 
-/// getValueType - Return the ValueType for the specified LLVM type.  This
-/// method works on all scalar LLVM types.
+SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
+  assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
+  if (VT == MVT::f32)
+    Val = (float)Val;  // Mask out extra precision.
+
+  SDNode *&N = ConstantFPs[std::make_pair(Val, VT)];
+  if (N) return SDOperand(N, 0);
+  N = new ConstantFPSDNode(Val, VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+
+
+SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
+                                         MVT::ValueType VT) {
+  SDNode *&N = GlobalValues[GV];
+  if (N) return SDOperand(N, 0);
+  N = new GlobalAddressSDNode(GV,VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
+  SDNode *&N = FrameIndices[FI];
+  if (N) return SDOperand(N, 0);
+  N = new FrameIndexSDNode(FI, VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) {
+  SDNode *N = ConstantPoolIndices[CPIdx];
+  if (N) return SDOperand(N, 0);
+  N = new ConstantPoolSDNode(CPIdx, VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
+  SDNode *&N = BBNodes[MBB];
+  if (N) return SDOperand(N, 0);
+  N = new BasicBlockSDNode(MBB);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
+  SDNode *&N = ExternalSymbols[Sym];
+  if (N) return SDOperand(N, 0);
+  N = new ExternalSymbolSDNode(Sym, VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1,
+                                 SDOperand N2) {
+  // These setcc operations always fold.
+  switch (Cond) {
+  default: break;
+  case ISD::SETFALSE:
+  case ISD::SETFALSE2: return getConstant(0, MVT::i1);
+  case ISD::SETTRUE:
+  case ISD::SETTRUE2:  return getConstant(1, MVT::i1);
+  }
+
+  if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val))
+    if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
+      uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
+      
+      // Sign extend the operands if required
+      if (ISD::isSignedIntSetCC(Cond)) {
+        C1 = N1C->getSignExtended();
+        C2 = N2C->getSignExtended();
+      }
+
+      switch (Cond) {
+      default: assert(0 && "Unknown integer setcc!");
+      case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
+      case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
+      case ISD::SETULT: return getConstant(C1 <  C2, MVT::i1);
+      case ISD::SETUGT: return getConstant(C1 >  C2, MVT::i1);
+      case ISD::SETULE: return getConstant(C1 <= C2, MVT::i1);
+      case ISD::SETUGE: return getConstant(C1 >= C2, MVT::i1);
+      case ISD::SETLT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      case ISD::SETGT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      case ISD::SETLE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      case ISD::SETGE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      }
+    } else {
+      // Ensure that the constant occurs on the RHS.
+      Cond = ISD::getSetCCSwappedOperands(Cond);
+      std::swap(N1, N2);
+    }
+
+  if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
+    if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
+      double C1 = N1C->getValue(), C2 = N2C->getValue();
+      
+      switch (Cond) {
+      default: break; // FIXME: Implement the rest of these!
+      case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
+      case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
+      case ISD::SETLT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      case ISD::SETGT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      case ISD::SETLE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      case ISD::SETGE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
+      }
+    } else {
+      // Ensure that the constant occurs on the RHS.
+      Cond = ISD::getSetCCSwappedOperands(Cond);
+      std::swap(N1, N2);
+    }
+
+  if (N1 == N2) {
+    // We can always fold X == Y for integer setcc's.
+    if (MVT::isInteger(N1.getValueType()))
+      return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
+    unsigned UOF = ISD::getUnorderedFlavor(Cond);
+    if (UOF == 2)   // FP operators that are undefined on NaNs.
+      return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
+    if (UOF == ISD::isTrueWhenEqual(Cond))
+      return getConstant(UOF, MVT::i1);
+    // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
+    // if it is not already.
+    Cond = UOF == 0 ? ISD::SETUO : ISD::SETO;
+  }
+
+
+  SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)];
+  if (N) return SDOperand(N, 0);
+  N = new SetCCSDNode(Cond, N1, N2);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+
+
+/// getNode - Gets or creates the specified node.
 ///
-MVT::ValueType SelectionDAG::getValueType(const Type *Ty) const {
-  switch (Ty->getTypeID()) {
-  case Type::VoidTyID: assert(0 && "Void type object in getValueType!");
-  default: assert(0 && "Unknown type in DAGBuilder!\n");
-  case Type::BoolTyID:    return MVT::i1;
-  case Type::SByteTyID:
-  case Type::UByteTyID:   return MVT::i8;
-  case Type::ShortTyID:
-  case Type::UShortTyID:  return MVT::i16;
-  case Type::IntTyID:
-  case Type::UIntTyID:    return MVT::i32;
-  case Type::LongTyID:
-  case Type::ULongTyID:   return MVT::i64;
-  case Type::FloatTyID:   return MVT::f32;
-  case Type::DoubleTyID:  return MVT::f64;
-  case Type::LabelTyID:
-  case Type::PointerTyID: return PointerType;
-  }
-}
-
-void SelectionDAGNode::dump() const {
-  // Print out the DAG in post-order
-  std::map<const SelectionDAGNode*, unsigned> NodeIDs;
-  unsigned ID = 0;
-  printit(0, ID, NodeIDs);
-}
-
-void SelectionDAGNode::printit(unsigned Offset, unsigned &LastID,
-                               std::map<const SelectionDAGNode*,
-                                        unsigned> &NodeIDs) const {
-  if (!NodeIDs.count(this)) {
-    // Emit all of the uses first...
-    for (unsigned i = 0, e = Uses.size(); i != e; ++i)
-      Uses[i]->printit(Offset+1, LastID, NodeIDs);
-
-    NodeIDs[this] = LastID++;
-
-    std::cerr << std::string(Offset, ' ') << "#" << LastID-1 << " ";
-  } else {
-    // Node has already been emitted...
-    std::cerr << std::string(Offset, ' ') << "#" << NodeIDs[this] << " ";
-  }
-
-  switch (ValueType) {
-  case MVT::isVoid: std::cerr << "V:"; break;
-  case MVT::i1:   std::cerr << "i1:"; break;
-  case MVT::i8:   std::cerr << "i8:"; break;
-  case MVT::i16:  std::cerr << "i16:"; break;
-  case MVT::i32:  std::cerr << "i32:"; break;
-  case MVT::i64:  std::cerr << "i64:"; break;
-  case MVT::f32:  std::cerr << "f32:"; break;
-  case MVT::f64:  std::cerr << "f64:"; break;
-  default: assert(0 && "Invalid node ValueType!");
-  }
-  switch (NodeType) {
-  case ISD::ChainNode:      std::cerr << "ChainNode"; break;
-  case ISD::BlockChainNode: std::cerr << "BlockChainNode"; break;
-  case ISD::ProtoNode:      std::cerr << "ProtoNode"; break;
-
-  case ISD::Constant:       std::cerr << "Constant"; break;
-  case ISD::FrameIndex:     std::cerr << "FrameIndex"; break;
-  case ISD::BasicBlock:     std::cerr << "BasicBlock"; break;
-
-  case ISD::Plus:           std::cerr << "Plus"; break;
-  case ISD::Minus:          std::cerr << "Minus"; break;
-  case ISD::Times:          std::cerr << "Times"; break;
-  case ISD::SDiv:           std::cerr << "SDiv"; break;
-  case ISD::UDiv:           std::cerr << "UDiv"; break;
-  case ISD::SRem:           std::cerr << "SRem"; break;
-  case ISD::URem:           std::cerr << "URem"; break;
-  case ISD::And:            std::cerr << "And"; break;
-  case ISD::Or:             std::cerr << "Or"; break;
-  case ISD::Xor:            std::cerr << "Xor"; break;
-
-  case ISD::SetEQ:          std::cerr << "SetEQ"; break;
-  case ISD::SetNE:          std::cerr << "SetNE"; break;
-  case ISD::SetLT:          std::cerr << "SetLT"; break;
-  case ISD::SetLE:          std::cerr << "SetLE"; break;
-  case ISD::SetGT:          std::cerr << "SetGT"; break;
-  case ISD::SetGE:          std::cerr << "SetGE"; break;
-
-  case ISD::Br:             std::cerr << "Br"; break;
-  case ISD::BrCond:         std::cerr << "BrCond"; break;
-  case ISD::Switch:         std::cerr << "Switch"; break;
-  case ISD::Ret:            std::cerr << "Ret"; break;
-  case ISD::RetVoid:        std::cerr << "RetVoid"; break;
-  case ISD::Load:           std::cerr << "Load"; break;
-  case ISD::Store:          std::cerr << "Store"; break;
-  case ISD::PHI:            std::cerr << "PHI"; break;
-  case ISD::Call:           std::cerr << "Call"; break;
-
-  case ISD::Unspec1:        std::cerr << "Unspec1"; break;
-  case ISD::Unspec2:        std::cerr << "Unspec2"; break;
-  }
-
-  std::cerr << "\n";
+SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
+  SDNode *N = new SDNode(Opcode, VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+static const Type *getTypeFor(MVT::ValueType VT) {
+  switch (VT) {
+  default: assert(0 && "Unknown MVT!");
+  case MVT::i1: return Type::BoolTy;
+  case MVT::i8: return Type::UByteTy;
+  case MVT::i16: return Type::UShortTy;
+  case MVT::i32: return Type::UIntTy;
+  case MVT::i64: return Type::ULongTy;
+  case MVT::f32: return Type::FloatTy;
+  case MVT::f64: return Type::DoubleTy;
+  }
+}
+
+SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
+                                SDOperand Operand) {
+  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
+    uint64_t Val = C->getValue();
+    switch (Opcode) {
+    default: break;
+    case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
+    case ISD::ZERO_EXTEND: return getConstant(Val, VT);
+    case ISD::TRUNCATE:    return getConstant(Val, VT);
+    }
+  }
+
+  if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
+    switch (Opcode) {
+    case ISD::FP_ROUND:
+    case ISD::FP_EXTEND:
+      return getConstantFP(C->getValue(), VT);
+    }
+
+  unsigned OpOpcode = Operand.Val->getOpcode();
+  switch (Opcode) {
+  case ISD::SIGN_EXTEND:
+    if (Operand.getValueType() == VT) return Operand;   // noop extension
+    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
+      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
+    break;
+  case ISD::ZERO_EXTEND:
+    if (Operand.getValueType() == VT) return Operand;   // noop extension
+    if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
+      return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
+    break;
+  case ISD::TRUNCATE:
+    if (Operand.getValueType() == VT) return Operand;   // noop truncate
+    if (OpOpcode == ISD::TRUNCATE)
+      return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
+    break;
+  }
+
+  SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
+  if (N) return SDOperand(N, 0);
+  N = new SDNode(Opcode, Operand);
+  N->setValueTypes(VT);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+static bool isCommutativeBinOp(unsigned Opcode) {
+  switch (Opcode) {
+  case ISD::ADD:
+  case ISD::MUL:
+  case ISD::AND:
+  case ISD::OR:
+  case ISD::XOR: return true;
+  default: return false; // FIXME: Need commutative info for user ops!
+  }
+}
+
+static bool isAssociativeBinOp(unsigned Opcode) {
+  switch (Opcode) {
+  case ISD::ADD:
+  case ISD::MUL:
+  case ISD::AND:
+  case ISD::OR:
+  case ISD::XOR: return true;
+  default: return false; // FIXME: Need associative info for user ops!
+  }
+}
+
+static unsigned ExactLog2(uint64_t Val) {
+  unsigned Count = 0;
+  while (Val != 1) {
+    Val >>= 1;
+    ++Count;
+  }
+  return Count;
 }
+
+// isInvertibleForFree - Return true if there is no cost to emitting the logical
+// inverse of this node.
+static bool isInvertibleForFree(SDOperand N) {
+  if (isa<ConstantSDNode>(N.Val)) return true;
+  if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse())
+    return true;
+  return false;  
+}
+
+
+SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
+                                SDOperand N1, SDOperand N2) {
+  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
+  ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
+  if (N1C) {
+    if (N2C) {
+      uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
+      switch (Opcode)