X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FLegalizeDAG.cpp;h=793037930c0159f80c2cd75ff0f68cf86eec9dc2;hb=eb516e7f0aa3223eab7967f4c0f8132d82efd841;hp=d1aae309d2fb1861ef8ab3629b590d7bc7ec419d;hpb=f4b457987fca50a1dc86e1a60dad2cff2b060945;p=oota-llvm.git

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index d1aae309d2f..793037930c0 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -1,10 +1,10 @@
 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
-// 
+//
 //                     The LLVM Compiler Infrastructure
 //
 // This file was developed by the LLVM research group and is distributed under
 // the University of Illinois Open Source License. See LICENSE.TXT for details.
-// 
+//
 //===----------------------------------------------------------------------===//
 //
 // This file implements the SelectionDAG::Legalize method.
@@ -125,8 +125,12 @@ private:
                           SDOperand Source);
   bool ExpandShift(unsigned Opc, SDOperand Op, SDOperand Amt,
                    SDOperand &Lo, SDOperand &Hi);
-  void ExpandAddSub(bool isAdd, SDOperand Op, SDOperand Amt,
-                    SDOperand &Lo, SDOperand &Hi);
+  void ExpandShiftParts(unsigned NodeOp, SDOperand Op, SDOperand Amt,
+                        SDOperand &Lo, SDOperand &Hi);
+  void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
+                     SDOperand &Lo, SDOperand &Hi);
+
+  void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain);
 
   SDOperand getIntPtrConstant(uint64_t Val) {
     return DAG.getConstant(Val, TLI.getPointerTy());
@@ -158,12 +162,13 @@ void SelectionDAGLegalize::LegalizeDAG() {
 SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
   assert(getTypeAction(Op.getValueType()) == Legal &&
          "Caller should expand or promote operands that are not legal!");
+  SDNode *Node = Op.Val;
 
   // If this operation defines any values that cannot be represented in a
   // register on this target, make sure to expand or promote them.
-  if (Op.Val->getNumValues() > 1) {
-    for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i)
-      switch (getTypeAction(Op.Val->getValueType(i))) {
+  if (Node->getNumValues() > 1) {
+    for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
+      switch (getTypeAction(Node->getValueType(i))) {
       case Legal: break;  // Nothing to do.
       case Expand: {
         SDOperand T1, T2;
@@ -180,13 +185,14 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       }
   }
 
+  // Note that LegalizeOp may be reentered even from single-use nodes, which
+  // means that we always must cache transformed nodes.
   std::map<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
   if (I != LegalizedNodes.end()) return I->second;
 
   SDOperand Tmp1, Tmp2, Tmp3;
 
   SDOperand Result = Op;
-  SDNode *Node = Op.Val;
 
   switch (Node->getOpcode()) {
   default:
@@ -283,14 +289,15 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         VT = MVT::f32;
         Extend = true;
       }
-      
+
       SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC),
                                             TLI.getPointerTy());
       if (Extend) {
         Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx,
-                             MVT::f32);
+                             DAG.getSrcValue(NULL), MVT::f32);
       } else {
-        Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx);
+        Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx,
+                             DAG.getSrcValue(NULL));
       }
     }
     break;
@@ -301,6 +308,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
       SDOperand Op = Node->getOperand(i);
       // Fold single-use TokenFactor nodes into this token factor as we go.
+      // FIXME: This is something that the DAGCombiner should do!!
       if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
         Changed = true;
         for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
@@ -315,13 +323,26 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     break;
   }
 
-  case ISD::ADJCALLSTACKDOWN:
-  case ISD::ADJCALLSTACKUP:
+  case ISD::CALLSEQ_START:
+  case ISD::CALLSEQ_END:
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
-    // There is no need to legalize the size argument (Operand #1)
-    if (Tmp1 != Node->getOperand(0))
-      Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1,
-                           Node->getOperand(1));
+    // Do not try to legalize the target-specific arguments (#1+)
+    Tmp2 = Node->getOperand(0);
+    if (Tmp1 != Tmp2) {
+      Node->setAdjCallChain(Tmp1);
+
+      // If moving the operand from pointing to Tmp2 dropped its use count to 1,
+      // this will cause the maps used to memoize results to get confused.
+      // Create and add a dummy use, just to increase its use count.  This will
+      // be removed at the end of legalize when dead nodes are removed.
+      if (Tmp2.Val->hasOneUse())
+        DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp2,
+                    DAG.getConstant(0, MVT::i32));
+    }
+    // Note that we do not create new CALLSEQ_DOWN/UP nodes here.  These
+    // nodes are treated specially and are mutated in place.  This makes the dag
+    // legalization process more efficient and also makes libcall insertion
+    // easier.
     break;
   case ISD::DYNAMIC_STACKALLOC:
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
@@ -389,16 +410,51 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
                            Node->getOperand(2));
     break;
+  case ISD::BRCONDTWOWAY:
+    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
+    switch (getTypeAction(Node->getOperand(1).getValueType())) {
+    case Expand: assert(0 && "It's impossible to expand bools");
+    case Legal:
+      Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
+      break;
+    case Promote:
+      Tmp2 = PromoteOp(Node->getOperand(1));  // Promote the condition.
+      break;
+    }
+    // If this target does not support BRCONDTWOWAY, lower it to a BRCOND/BR
+    // pair.
+    switch (TLI.getOperationAction(ISD::BRCONDTWOWAY, MVT::Other)) {
+    case TargetLowering::Promote:
+    default: assert(0 && "This action is not supported yet!");
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) {
+        std::vector<SDOperand> Ops;
+        Ops.push_back(Tmp1);
+        Ops.push_back(Tmp2);
+        Ops.push_back(Node->getOperand(2));
+        Ops.push_back(Node->getOperand(3));
+        Result = DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops);
+      }
+      break;
+    case TargetLowering::Expand:
+      Result = DAG.getNode(ISD::BRCOND, MVT::Other, Tmp1, Tmp2,
+                           Node->getOperand(2));
+      Result = DAG.getNode(ISD::BR, MVT::Other, Result, Node->getOperand(3));
+      break;
+    }
+    break;
 
   case ISD::LOAD:
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
+
     if (Tmp1 != Node->getOperand(0) ||
         Tmp2 != Node->getOperand(1))
-      Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2);
+      Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2,
+                           Node->getOperand(2));
     else
       Result = SDOperand(Node, 0);
-    
+
     // Since loads produce two values, make sure to remember that we legalized
     // both of them.
     AddLegalizedOperand(SDOperand(Node, 0), Result);
@@ -407,22 +463,57 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 
   case ISD::EXTLOAD:
   case ISD::SEXTLOAD:
-  case ISD::ZEXTLOAD:
+  case ISD::ZEXTLOAD: {
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
     Tmp2 = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
-    if (Tmp1 != Node->getOperand(0) ||
-        Tmp2 != Node->getOperand(1))
-      Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2,
-                           cast<MVTSDNode>(Node)->getExtraValueType());
-    else
-      Result = SDOperand(Node, 0);
-    
-    // Since loads produce two values, make sure to remember that we legalized
-    // both of them.
-    AddLegalizedOperand(SDOperand(Node, 0), Result);
-    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
-    return Result.getValue(Op.ResNo);
 
+    MVT::ValueType SrcVT = cast<MVTSDNode>(Node)->getExtraValueType();
+    switch (TLI.getOperationAction(Node->getOpcode(), SrcVT)) {
+    default: assert(0 && "This action is not supported yet!");
+    case TargetLowering::Promote:
+      assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!");
+      Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0),
+                           Tmp1, Tmp2, Node->getOperand(2), MVT::i8);
+      // Since loads produce two values, make sure to remember that we legalized
+      // both of them.
+      AddLegalizedOperand(SDOperand(Node, 0), Result);
+      AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
+      return Result.getValue(Op.ResNo);
+
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0) ||
+          Tmp2 != Node->getOperand(1))
+        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0),
+                             Tmp1, Tmp2, Node->getOperand(2), SrcVT);
+      else
+        Result = SDOperand(Node, 0);
+
+      // Since loads produce two values, make sure to remember that we legalized
+      // both of them.
+      AddLegalizedOperand(SDOperand(Node, 0), Result);
+      AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
+      return Result.getValue(Op.ResNo);
+    case TargetLowering::Expand:
+      assert(Node->getOpcode() != ISD::EXTLOAD &&
+             "EXTLOAD should always be supported!");
+      // Turn the unsupported load into an EXTLOAD followed by an explicit
+      // zero/sign extend inreg.
+      Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
+                           Tmp1, Tmp2, Node->getOperand(2), SrcVT);
+      SDOperand ValRes;
+      if (Node->getOpcode() == ISD::SEXTLOAD)
+        ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
+                             Result, SrcVT);
+      else
+        ValRes = DAG.getZeroExtendInReg(Result, SrcVT);
+      AddLegalizedOperand(SDOperand(Node, 0), ValRes);
+      AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
+      if (Op.ResNo)
+        return Result.getValue(1);
+      return ValRes;
+    }
+    assert(0 && "Unreachable");
+  }
   case ISD::EXTRACT_ELEMENT:
     // Get both the low and high parts.
     ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
@@ -434,7 +525,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 
   case ISD::CopyToReg:
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
-    
+
     switch (getTypeAction(Node->getOperand(1).getValueType())) {
     case Legal:
       // Legalize the incoming value (must be legal).
@@ -448,7 +539,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       break;
     case Expand:
       SDOperand Lo, Hi;
-      ExpandOp(Node->getOperand(1), Lo, Hi);      
+      ExpandOp(Node->getOperand(1), Lo, Hi);
       unsigned Reg = cast<RegSDNode>(Node)->getReg();
       Lo = DAG.getCopyToReg(Tmp1, Lo, Reg);
       Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1);
@@ -474,7 +565,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         SDOperand Lo, Hi;
         ExpandOp(Node->getOperand(1), Lo, Hi);
         Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi);
-        break;                             
+        break;
       }
       case Promote:
         Tmp2 = PromoteOp(Node->getOperand(1));
@@ -499,7 +590,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
           ExpandOp(Node->getOperand(i), Lo, Hi);
           NewValues.push_back(Lo);
           NewValues.push_back(Hi);
-          break;                             
+          break;
         }
         case Promote:
           assert(0 && "Can't promote multiple return value yet!");
@@ -521,8 +612,9 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
           float    F;
         } V;
         V.F = CFP->getValue();
-        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
-                             DAG.getConstant(V.I, MVT::i32), Tmp2);
+        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 
+                             DAG.getConstant(V.I, MVT::i32), Tmp2,
+                             Node->getOperand(3));
       } else {
         assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!");
         union {
@@ -530,8 +622,9 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
           double   F;
         } V;
         V.F = CFP->getValue();
-        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1,
-                             DAG.getConstant(V.I, MVT::i64), Tmp2);
+        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, 
+                             DAG.getConstant(V.I, MVT::i64), Tmp2,
+                             Node->getOperand(3));
       }
       Node = Result.Val;
     }
@@ -541,14 +634,16 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       SDOperand Val = LegalizeOp(Node->getOperand(1));
       if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) ||
           Tmp2 != Node->getOperand(2))
-        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2);
+        Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2,
+                             Node->getOperand(3));
       break;
     }
     case Promote:
       // Truncate the value and store the result.
       Tmp3 = PromoteOp(Node->getOperand(1));
       Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2,
-                           Node->getOperand(1).getValueType());
+                           Node->getOperand(3),
+                           Node->getOperand(1).getValueType()); 
       break;
 
     case Expand:
@@ -558,21 +653,24 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       if (!TLI.isLittleEndian())
         std::swap(Lo, Hi);
 
-      Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2);
-
+      Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2,
+                       Node->getOperand(3));
       unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8;
       Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2,
                          getIntPtrConstant(IncrementSize));
       assert(isTypeLegal(Tmp2.getValueType()) &&
              "Pointers must be legal!");
-      Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2);
+      //Again, claiming both parts of the store came form the same Instr
+      Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2,
+                       Node->getOperand(3));
       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi);
       break;
     }
     break;
   case ISD::PCMARKER:
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
-    Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1, Node->getOperand(1));
+    if (Tmp1 != Node->getOperand(0))
+      Result = DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp1,Node->getOperand(1));
     break;
   case ISD::TRUNCSTORE:
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
@@ -584,6 +682,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
           Tmp3 != Node->getOperand(2))
         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3,
+                             Node->getOperand(3),
                              cast<MVTSDNode>(Node)->getExtraValueType());
       break;
     case Promote:
@@ -666,8 +765,8 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
           // ALL of these operations will work if we either sign or zero extend
           // the operands (including the unsigned comparisons!).  Zero extend is
           // usually a simpler/cheaper operation, so prefer it.
-          Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
-          Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
+          Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
+          Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
           break;
         case ISD::SETGE:
         case ISD::SETGT:
@@ -682,21 +781,41 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
                             Node->getValueType(0), Tmp1, Tmp2);
       break;
-    case Expand: 
+    case Expand:
       SDOperand LHSLo, LHSHi, RHSLo, RHSHi;
       ExpandOp(Node->getOperand(0), LHSLo, LHSHi);
       ExpandOp(Node->getOperand(1), RHSLo, RHSHi);
       switch (cast<SetCCSDNode>(Node)->getCondition()) {
       case ISD::SETEQ:
       case ISD::SETNE:
+        if (RHSLo == RHSHi)
+          if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo))
+            if (RHSCST->isAllOnesValue()) {
+              // Comparison to -1.
+              Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi);
+              Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
+                                    Node->getValueType(0), Tmp1, RHSLo);
+              break;
+            }
+
         Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo);
         Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi);
         Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2);
-        Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(), 
+        Result = DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
                               Node->getValueType(0), Tmp1,
                               DAG.getConstant(0, Tmp1.getValueType()));
         break;
       default:
+        // If this is a comparison of the sign bit, just look at the top part.
+        // X > -1,  x < 0
+        if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(Node->getOperand(1)))
+          if ((cast<SetCCSDNode>(Node)->getCondition() == ISD::SETLT &&
+               CST->getValue() == 0) ||              // X < 0
+              (cast<SetCCSDNode>(Node)->getCondition() == ISD::SETGT &&
+               (CST->isAllOnesValue())))             // X > -1
+            return DAG.getSetCC(cast<SetCCSDNode>(Node)->getCondition(),
+                                Node->getValueType(0), LHSHi, RHSHi);
+
         // FIXME: This generated code sucks.
         ISD::CondCode LowCC;
         switch (cast<SetCCSDNode>(Node)->getCondition()) {
@@ -710,7 +829,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         case ISD::SETGE:
         case ISD::SETUGE: LowCC = ISD::SETUGE; break;
         }
-        
+
         // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
         // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
         // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
@@ -745,7 +864,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         break;
       }
     } else {
-      Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer, 
+      Tmp3 = LegalizeOp(Node->getOperand(2));    // memcpy/move = pointer,
     }
 
     SDOperand Tmp4;
@@ -807,8 +926,9 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       } else {
         assert(0 && "Unknown op!");
       }
+
       std::pair<SDOperand,SDOperand> CallResult =
-        TLI.LowerCallTo(Tmp1, Type::VoidTy, false,
+        TLI.LowerCallTo(Tmp1, Type::VoidTy, false, 0,
                         DAG.getExternalSymbol(FnName, IntPtr), Args, DAG);
       Result = LegalizeOp(CallResult.second);
       break;
@@ -824,8 +944,86 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     }
     break;
   }
+
+  case ISD::READPORT:
+    Tmp1 = LegalizeOp(Node->getOperand(0));
+    Tmp2 = LegalizeOp(Node->getOperand(1));
+
+    if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
+      Result = DAG.getNode(ISD::READPORT, Node->getValueType(0), Tmp1, Tmp2);
+    else
+      Result = SDOperand(Node, 0);
+    // Since these produce two values, make sure to remember that we legalized
+    // both of them.
+    AddLegalizedOperand(SDOperand(Node, 0), Result);
+    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
+    return Result.getValue(Op.ResNo);
+  case ISD::WRITEPORT:
+    Tmp1 = LegalizeOp(Node->getOperand(0));
+    Tmp2 = LegalizeOp(Node->getOperand(1));
+    Tmp3 = LegalizeOp(Node->getOperand(2));
+    if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
+        Tmp3 != Node->getOperand(2))
+      Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
+    break;
+
+  case ISD::READIO:
+    Tmp1 = LegalizeOp(Node->getOperand(0));
+    Tmp2 = LegalizeOp(Node->getOperand(1));
+
+    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
+    case TargetLowering::Custom:
+    default: assert(0 && "This action not implemented for this operation!");
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1))
+        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0),
+                             Tmp1, Tmp2);
+      else
+        Result = SDOperand(Node, 0);
+      break;
+    case TargetLowering::Expand:
+      // Replace this with a load from memory.
+      Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0),
+                           Node->getOperand(1), DAG.getSrcValue(NULL));
+      Result = LegalizeOp(Result);
+      break;
+    }
+
+    // Since these produce two values, make sure to remember that we legalized
+    // both of them.
+    AddLegalizedOperand(SDOperand(Node, 0), Result);
+    AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1));
+    return Result.getValue(Op.ResNo);
+
+  case ISD::WRITEIO:
+    Tmp1 = LegalizeOp(Node->getOperand(0));
+    Tmp2 = LegalizeOp(Node->getOperand(1));
+    Tmp3 = LegalizeOp(Node->getOperand(2));
+
+    switch (TLI.getOperationAction(Node->getOpcode(),
+                                   Node->getOperand(1).getValueType())) {
+    case TargetLowering::Custom:
+    default: assert(0 && "This action not implemented for this operation!");
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) ||
+          Tmp3 != Node->getOperand(2))
+        Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3);
+      break;
+    case TargetLowering::Expand:
+      // Replace this with a store to memory.
+      Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0),
+                           Node->getOperand(1), Node->getOperand(2),
+                           DAG.getSrcValue(NULL));
+      Result = LegalizeOp(Result);
+      break;
+    }
+    break;
+
   case ISD::ADD_PARTS:
-  case ISD::SUB_PARTS: {
+  case ISD::SUB_PARTS:
+  case ISD::SHL_PARTS:
+  case ISD::SRA_PARTS:
+  case ISD::SRL_PARTS: {
     std::vector<SDOperand> Ops;
     bool Changed = false;
     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
@@ -834,15 +1032,22 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     }
     if (Changed)
       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Ops);
-    break;
+
+    // Since these produce multiple values, make sure to remember that we
+    // legalized all of them.
+    for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
+      AddLegalizedOperand(SDOperand(Node, i), Result.getValue(i));
+    return Result.getValue(Op.ResNo);
   }
+
+    // Binary operators
   case ISD::ADD:
   case ISD::SUB:
   case ISD::MUL:
+  case ISD::MULHS:
+  case ISD::MULHU:
   case ISD::UDIV:
   case ISD::SDIV:
-  case ISD::UREM:
-  case ISD::SREM:
   case ISD::AND:
   case ISD::OR:
   case ISD::XOR:
@@ -855,6 +1060,212 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         Tmp2 != Node->getOperand(1))
       Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2);
     break;
+
+  case ISD::UREM:
+  case ISD::SREM:
+    Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
+    Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
+    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0) ||
+          Tmp2 != Node->getOperand(1))
+        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
+                             Tmp2);
+      break;
+    case TargetLowering::Promote:
+    case TargetLowering::Custom:
+      assert(0 && "Cannot promote/custom handle this yet!");
+    case TargetLowering::Expand: {
+      MVT::ValueType VT = Node->getValueType(0);
+      unsigned Opc = (Node->getOpcode() == ISD::UREM) ? ISD::UDIV : ISD::SDIV;
+      Result = DAG.getNode(Opc, VT, Tmp1, Tmp2);
+      Result = DAG.getNode(ISD::MUL, VT, Result, Tmp2);
+      Result = DAG.getNode(ISD::SUB, VT, Tmp1, Result);
+      }
+      break;
+    }
+    break;
+
+  case ISD::CTPOP:
+  case ISD::CTTZ:
+  case ISD::CTLZ:
+    Tmp1 = LegalizeOp(Node->getOperand(0));   // Op
+    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0))
+        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
+      break;
+    case TargetLowering::Promote: {
+      MVT::ValueType OVT = Tmp1.getValueType();
+      MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
+
+      // Zero extend the argument.
+      Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
+      // Perform the larger operation, then subtract if needed.
+      Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
+      switch(Node->getOpcode())
+      {
+      case ISD::CTPOP:
+        Result = Tmp1;
+        break;
+      case ISD::CTTZ:
+        //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
+        Tmp2 = DAG.getSetCC(ISD::SETEQ, TLI.getSetCCResultTy(), Tmp1, 
+                            DAG.getConstant(getSizeInBits(NVT), NVT));
+        Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 
+                           DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
+        break;
+      case ISD::CTLZ:
+        //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
+        Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 
+                             DAG.getConstant(getSizeInBits(NVT) - 
+                                             getSizeInBits(OVT), NVT));
+        break;
+      }
+      break;
+    }
+    case TargetLowering::Custom:
+      assert(0 && "Cannot custom handle this yet!");
+    case TargetLowering::Expand:
+      switch(Node->getOpcode())
+      {
+      case ISD::CTPOP: {
+        static const uint64_t mask[6] = {
+          0x5555555555555555ULL, 0x3333333333333333ULL,
+          0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
+          0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
+        };
+        MVT::ValueType VT = Tmp1.getValueType();
+        MVT::ValueType ShVT = TLI.getShiftAmountTy();
+        unsigned len = getSizeInBits(VT);
+        for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
+          //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
+          Tmp2 = DAG.getConstant(mask[i], VT);
+          Tmp3 = DAG.getConstant(1ULL << i, ShVT);
+          Tmp1 = DAG.getNode(ISD::ADD, VT, 
+                             DAG.getNode(ISD::AND, VT, Tmp1, Tmp2),
+                             DAG.getNode(ISD::AND, VT,
+                                         DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3),
+                                         Tmp2));
+        }
+        Result = Tmp1;
+        break;
+      }
+      case ISD::CTLZ: {
+        /* for now, we do this:
+           x = x | (x >> 1);
+           x = x | (x >> 2);
+           ...
+           x = x | (x >>16);
+           x = x | (x >>32); // for 64-bit input 
+           return popcount(~x);
+        
+           but see also: http://www.hackersdelight.org/HDcode/nlz.cc */
+        MVT::ValueType VT = Tmp1.getValueType();
+        MVT::ValueType ShVT = TLI.getShiftAmountTy();
+        unsigned len = getSizeInBits(VT);
+        for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
+          Tmp3 = DAG.getConstant(1ULL << i, ShVT);
+          Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1,  
+                             DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3));
+        }
+        Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT));
+        Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
+        break;
+      }
+      case ISD::CTTZ: {
+        // for now, we use: { return popcount(~x & (x - 1)); } 
+        // unless the target has ctlz but not ctpop, in which case we use:
+        // { return 32 - nlz(~x & (x-1)); }
+        // see also http://www.hackersdelight.org/HDcode/ntz.cc
+        MVT::ValueType VT = Tmp1.getValueType();
+        Tmp2 = DAG.getConstant(~0ULL, VT);
+        Tmp3 = DAG.getNode(ISD::AND, VT, 
+                           DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2),
+                           DAG.getNode(ISD::SUB, VT, Tmp1,
+                                       DAG.getConstant(1, VT)));
+        // If ISD::CTLZ is legal and CTPOP isn't, then do that instead
+        if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal &&
+            TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) {
+          Result = LegalizeOp(DAG.getNode(ISD::SUB, VT, 
+                                        DAG.getConstant(getSizeInBits(VT), VT),
+                                        DAG.getNode(ISD::CTLZ, VT, Tmp3)));
+        } else {
+          Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
+        }
+        break;
+      }
+      default:
+        assert(0 && "Cannot expand this yet!");
+        break;
+      }
+      break;
+    }
+    break;
+    
+    // Unary operators
+  case ISD::FABS:
+  case ISD::FNEG:
+  case ISD::FSQRT:
+  case ISD::FSIN:
+  case ISD::FCOS:
+    Tmp1 = LegalizeOp(Node->getOperand(0));
+    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0))
+        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
+      break;
+    case TargetLowering::Promote:
+    case TargetLowering::Custom:
+      assert(0 && "Cannot promote/custom handle this yet!");
+    case TargetLowering::Expand:
+      switch(Node->getOpcode()) {
+      case ISD::FNEG: {
+        // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
+        Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0));
+        Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0),
+                                        Tmp2, Tmp1));
+        break;
+      }
+      case ISD::FABS: {
+        // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X).
+        MVT::ValueType VT = Node->getValueType(0);
+        Tmp2 = DAG.getConstantFP(0.0, VT);
+        Tmp2 = DAG.getSetCC(ISD::SETUGT, TLI.getSetCCResultTy(), Tmp1, Tmp2);
+        Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1);
+        Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3);
+        Result = LegalizeOp(Result);
+        break;
+      }
+      case ISD::FSQRT:
+      case ISD::FSIN:
+      case ISD::FCOS: {
+        MVT::ValueType VT = Node->getValueType(0);
+        Type *T = VT == MVT::f32 ? Type::FloatTy : Type::DoubleTy;
+        const char *FnName = 0;
+        switch(Node->getOpcode()) {
+        case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break;
+        case ISD::FSIN:  FnName = VT == MVT::f32 ? "sinf"  : "sin"; break;
+        case ISD::FCOS:  FnName = VT == MVT::f32 ? "cosf"  : "cos"; break;
+        default: assert(0 && "Unreachable!");
+        }
+        std::vector<std::pair<SDOperand, const Type*> > Args;
+        Args.push_back(std::make_pair(Tmp1, T));
+        // FIXME: should use ExpandLibCall!
+        std::pair<SDOperand,SDOperand> CallResult =
+          TLI.LowerCallTo(DAG.getEntryNode(), T, false, 0,
+                          DAG.getExternalSymbol(FnName, VT), Args, DAG);
+        Result = LegalizeOp(CallResult.first);
+        break;
+      }
+      default:
+        assert(0 && "Unreachable!");
+      }
+      break;
+    }
+    break;
+
+    // Conversion operators.  The source and destination have different types.
   case ISD::ZERO_EXTEND:
   case ISD::SIGN_EXTEND:
   case ISD::TRUNCATE:
@@ -875,19 +1286,18 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
           Node->getOpcode() == ISD::UINT_TO_FP) {
         Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP,
                                Node->getValueType(0), Node->getOperand(0));
-        Result = LegalizeOp(Result);
+        break;
+      } else if (Node->getOpcode() == ISD::TRUNCATE) {
+        // In the expand case, we must be dealing with a truncate, because
+        // otherwise the result would be larger than the source.
+        ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
+
+        // Since the result is legal, we should just be able to truncate the low
+        // part of the source.
+        Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
         break;
       }
-      // In the expand case, we must be dealing with a truncate, because
-      // otherwise the result would be larger than the source.
-      assert(Node->getOpcode() == ISD::TRUNCATE &&
-             "Shouldn't need to expand other operators here!");
-      ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
-
-      // Since the result is legal, we should just be able to truncate the low
-      // part of the source.
-      Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1);
-      break;
+      assert(0 && "Shouldn't need to expand other operators here!");
 
     case Promote:
       switch (Node->getOpcode()) {
@@ -895,8 +1305,8 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         Result = PromoteOp(Node->getOperand(0));
         // NOTE: Any extend would work here...
         Result = DAG.getNode(ISD::ZERO_EXTEND, Op.getValueType(), Result);
-        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Op.getValueType(),
-                             Result, Node->getOperand(0).getValueType());
+        Result = DAG.getZeroExtendInReg(Result,
+                                        Node->getOperand(0).getValueType());
         break;
       case ISD::SIGN_EXTEND:
         Result = PromoteOp(Node->getOperand(0));
@@ -929,16 +1339,15 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         break;
       case ISD::UINT_TO_FP:
         Result = PromoteOp(Node->getOperand(0));
-        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
-                             Result, Node->getOperand(0).getValueType());
+        Result = DAG.getZeroExtendInReg(Result,
+                                        Node->getOperand(0).getValueType());
         Result = DAG.getNode(ISD::UINT_TO_FP, Op.getValueType(), Result);
         break;
       }
     }
     break;
   case ISD::FP_ROUND_INREG:
-  case ISD::SIGN_EXTEND_INREG:
-  case ISD::ZERO_EXTEND_INREG: {
+  case ISD::SIGN_EXTEND_INREG: {
     Tmp1 = LegalizeOp(Node->getOperand(0));
     MVT::ValueType ExtraVT = cast<MVTSDNode>(Node)->getExtraValueType();
 
@@ -953,16 +1362,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
       break;
     case TargetLowering::Expand:
       // If this is an integer extend and shifts are supported, do that.
-      if (Node->getOpcode() == ISD::ZERO_EXTEND_INREG) {
-        // NOTE: we could fall back on load/store here too for targets without
-        // AND.  However, it is doubtful that any exist.
-        // AND out the appropriate bits.
-        SDOperand Mask =
-          DAG.getConstant((1ULL << MVT::getSizeInBits(ExtraVT))-1,
-                          Node->getValueType(0));
-        Result = DAG.getNode(ISD::AND, Node->getValueType(0),
-                             Node->getOperand(0), Mask);
-      } else if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
+      if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG) {
         // NOTE: we could fall back on load/store here too for targets without
         // SAR.  However, it is doubtful that any exist.
         unsigned BitsDiff = MVT::getSizeInBits(Node->getValueType(0)) -
@@ -983,13 +1383,14 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
         unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty);
         unsigned Align  = TLI.getTargetData().getTypeAlignment(Ty);
         MachineFunction &MF = DAG.getMachineFunction();
-        int SSFI = 
+        int SSFI =
           MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
         SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
         Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(),
-                             Node->getOperand(0), StackSlot, ExtraVT);
+                             Node->getOperand(0), StackSlot,
+                             DAG.getSrcValue(NULL), ExtraVT);
         Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0),
-                             Result, StackSlot, ExtraVT);
+                             Result, StackSlot, DAG.getSrcValue(NULL), ExtraVT);
       } else {
         assert(0 && "Unknown op");
       }
@@ -1000,9 +1401,9 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
   }
   }
 
-  if (!Op.Val->hasOneUse())
-    AddLegalizedOperand(Op, Result);
-
+  // Note that LegalizeOp may be reentered even from single-use nodes, which
+  // means that we always must cache transformed nodes.
+  AddLegalizedOperand(Op, Result);
   return Result;
 }
 
@@ -1018,14 +1419,18 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
   assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) &&
          "Cannot promote to smaller type!");
 
-  std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
-  if (I != PromotedNodes.end()) return I->second;
-
   SDOperand Tmp1, Tmp2, Tmp3;
 
   SDOperand Result;
   SDNode *Node = Op.Val;
 
+  if (!Node->hasOneUse()) {
+    std::map<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
+    if (I != PromotedNodes.end()) return I->second;
+  } else {
+    assert(!PromotedNodes.count(Op) && "Repromoted this node??");
+  }
+
   // Promotion needs an optimization step to clean up after it, and is not
   // careful to avoid operations the target does not support.  Make sure that
   // all generated operations are legalized in the next iteration.
@@ -1078,7 +1483,9 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
       Result = PromoteOp(Node->getOperand(0));
       break;
     case Expand:
-      assert(0 && "Cannot handle expand yet");
+      ExpandOp(Node->getOperand(0), Tmp1, Tmp2);
+      // Truncate the low part of the expanded value to the result type
+      Result = DAG.getNode(ISD::TRUNCATE, VT, Tmp1);
     }
     break;
   case ISD::SIGN_EXTEND:
@@ -1098,8 +1505,8 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Result,
                              Node->getOperand(0).getValueType());
       else
-        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Result,
-                             Node->getOperand(0).getValueType());
+        Result = DAG.getZeroExtendInReg(Result,
+                                        Node->getOperand(0).getValueType());
       break;
     }
     break;
@@ -1133,16 +1540,14 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
         Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(),
                              Result, Node->getOperand(0).getValueType());
       else
-        Result = DAG.getNode(ISD::ZERO_EXTEND_INREG, Result.getValueType(),
-                             Result, Node->getOperand(0).getValueType());
+        Result = DAG.getZeroExtendInReg(Result,
+                                        Node->getOperand(0).getValueType());
       // No extra round required here.
       Result = DAG.getNode(Node->getOpcode(), NVT, Result);
       break;
     case Expand:
       Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT,
                              Node->getOperand(0));
-      Result = LegalizeOp(Result);
-
       // Round if we cannot tolerate excess precision.
       if (NoExcessFPPrecision)
         Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
@@ -1167,6 +1572,26 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
     break;
 
+  case ISD::FABS:
+  case ISD::FNEG:
+    Tmp1 = PromoteOp(Node->getOperand(0));
+    assert(Tmp1.getValueType() == NVT);
+    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
+    // NOTE: we do not have to do any extra rounding here for
+    // NoExcessFPPrecision, because we know the input will have the appropriate
+    // precision, and these operations don't modify precision at all.
+    break;
+
+  case ISD::FSQRT:
+  case ISD::FSIN:
+  case ISD::FCOS:
+    Tmp1 = PromoteOp(Node->getOperand(0));
+    assert(Tmp1.getValueType() == NVT);
+    Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
+    if(NoExcessFPPrecision)
+      Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT);
+    break;
+
   case ISD::AND:
   case ISD::OR:
   case ISD::XOR:
@@ -1212,8 +1637,8 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
     Tmp1 = PromoteOp(Node->getOperand(0));
     Tmp2 = PromoteOp(Node->getOperand(1));
     assert(MVT::isInteger(NVT) && "Operators don't apply to FP!");
-    Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
-    Tmp2 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp2, VT);
+    Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
+    Tmp2 = DAG.getZeroExtendInReg(Tmp2, VT);
     Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1, Tmp2);
     break;
 
@@ -1232,14 +1657,20 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
   case ISD::SRL:
     // The input value must be properly zero extended.
     Tmp1 = PromoteOp(Node->getOperand(0));
-    Tmp1 = DAG.getNode(ISD::ZERO_EXTEND_INREG, NVT, Tmp1, VT);
+    Tmp1 = DAG.getZeroExtendInReg(Tmp1, VT);
     Tmp2 = LegalizeOp(Node->getOperand(1));
     Result = DAG.getNode(ISD::SRL, NVT, Tmp1, Tmp2);
     break;
   case ISD::LOAD:
     Tmp1 = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
     Tmp2 = LegalizeOp(Node->getOperand(1));   // Legalize the pointer.
-    Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT);
+    // FIXME: When the DAG combiner exists, change this to use EXTLOAD!
+    if (MVT::isInteger(NVT))
+      Result = DAG.getNode(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2),
+                           VT);
+    else
+      Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2),
+                           VT);
 
     // Remember that we legalized the chain.
     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
@@ -1278,7 +1709,35 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
     // Insert the new chain mapping.
     AddLegalizedOperand(Op.getValue(1), Result.getValue(1));
     break;
-  } 
+  }
+  case ISD::CTPOP:
+  case ISD::CTTZ:
+  case ISD::CTLZ:
+    Tmp1 = Node->getOperand(0);
+    //Zero extend the argument
+    Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
+    // Perform the larger operation, then subtract if needed.
+    Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1);
+    switch(Node->getOpcode())
+    {
+    case ISD::CTPOP:
+      Result = Tmp1;
+      break;
+    case ISD::CTTZ:
+      //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
+      Tmp2 = DAG.getSetCC(ISD::SETEQ, MVT::i1, Tmp1, 
+                          DAG.getConstant(getSizeInBits(NVT), NVT));
+      Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, 
+                           DAG.getConstant(getSizeInBits(VT),NVT), Tmp1);
+      break;
+    case ISD::CTLZ:
+      //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
+      Result = DAG.getNode(ISD::SUB, NVT, Tmp1, 
+                           DAG.getConstant(getSizeInBits(NVT) - 
+                                           getSizeInBits(VT), NVT));
+      break;
+    }
+    break;
   }
 
   assert(Result.Val && "Didn't set a result!");
@@ -1288,25 +1747,60 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) {
 
 /// ExpandAddSub - Find a clever way to expand this add operation into
 /// subcomponents.
-void SelectionDAGLegalize::ExpandAddSub(bool isAdd, SDOperand LHS,SDOperand RHS,
-                                        SDOperand &Lo, SDOperand &Hi) {
+void SelectionDAGLegalize::
+ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS,
+              SDOperand &Lo, SDOperand &Hi) {
   // Expand the subcomponents.
   SDOperand LHSL, LHSH, RHSL, RHSH;
   ExpandOp(LHS, LHSL, LHSH);
   ExpandOp(RHS, RHSL, RHSH);
 
-  // Convert this add to the appropriate ADDC pair.  The low part has no carry
-  // in.
-  unsigned Opc = isAdd ? ISD::ADD_PARTS : ISD::SUB_PARTS;
+  // FIXME: this should be moved to the dag combiner someday.
+  if (NodeOp == ISD::ADD_PARTS || NodeOp == ISD::SUB_PARTS)
+    if (LHSL.getValueType() == MVT::i32) {
+      SDOperand LowEl;
+      if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(LHSL))
+        if (C->getValue() == 0)
+          LowEl = RHSL;
+      if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHSL))
+        if (C->getValue() == 0)
+          LowEl = LHSL;
+      if (LowEl.Val) {
+        // Turn this into an add/sub of the high part only.
+        SDOperand HiEl =
+          DAG.getNode(NodeOp == ISD::ADD_PARTS ? ISD::ADD : ISD::SUB,
+                      LowEl.getValueType(), LHSH, RHSH);
+        Lo = LowEl;
+        Hi = HiEl;
+        return;
+      }
+    }
+
   std::vector<SDOperand> Ops;
   Ops.push_back(LHSL);
   Ops.push_back(LHSH);
   Ops.push_back(RHSL);
   Ops.push_back(RHSH);
-  Lo = DAG.getNode(Opc, LHSL.getValueType(), Ops);
+  Lo = DAG.getNode(NodeOp, LHSL.getValueType(), Ops);
+  Hi = Lo.getValue(1);
+}
+
+void SelectionDAGLegalize::ExpandShiftParts(unsigned NodeOp,
+                                            SDOperand Op, SDOperand Amt,
+                                            SDOperand &Lo, SDOperand &Hi) {
+  // Expand the subcomponents.
+  SDOperand LHSL, LHSH;
+  ExpandOp(Op, LHSL, LHSH);
+
+  std::vector<SDOperand> Ops;
+  Ops.push_back(LHSL);
+  Ops.push_back(LHSH);
+  Ops.push_back(Amt);
+  Lo = DAG.getNode(NodeOp, LHSL.getValueType(), Ops);
   Hi = Lo.getValue(1);
 }
 
+
 /// ExpandShift - Try to find a clever way to expand this shift operation out to
 /// smaller elements.  If we can't find a way that is more efficient than a
 /// libcall on this target, return false.  Otherwise, return true with the
@@ -1315,7 +1809,81 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
                                        SDOperand &Lo, SDOperand &Hi) {
   assert((Opc == ISD::SHL || Opc == ISD::SRA || Opc == ISD::SRL) &&
          "This is not a shift!");
+
   MVT::ValueType NVT = TLI.getTypeToTransformTo(Op.getValueType());
+  SDOperand ShAmt = LegalizeOp(Amt);
+  MVT::ValueType ShTy = ShAmt.getValueType();
+  unsigned VTBits = MVT::getSizeInBits(Op.getValueType());
+  unsigned NVTBits = MVT::getSizeInBits(NVT);
+
+  // Handle the case when Amt is an immediate.  Other cases are currently broken
+  // and are disabled.
+  if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Amt.Val)) {
+    unsigned Cst = CN->getValue();
+    // Expand the incoming operand to be shifted, so that we have its parts
+    SDOperand InL, InH;
+    ExpandOp(Op, InL, InH);
+    switch(Opc) {
+    case ISD::SHL:
+      if (Cst > VTBits) {
+        Lo = DAG.getConstant(0, NVT);
+        Hi = DAG.getConstant(0, NVT);
+      } else if (Cst > NVTBits) {
+        Lo = DAG.getConstant(0, NVT);
+        Hi = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst-NVTBits,ShTy));
+      } else if (Cst == NVTBits) {
+        Lo = DAG.getConstant(0, NVT);
+        Hi = InL;
+      } else {
+        Lo = DAG.getNode(ISD::SHL, NVT, InL, DAG.getConstant(Cst, ShTy));
+        Hi = DAG.getNode(ISD::OR, NVT,
+           DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(Cst, ShTy)),
+           DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(NVTBits-Cst, ShTy)));
+      }
+      return true;
+    case ISD::SRL:
+      if (Cst > VTBits) {
+        Lo = DAG.getConstant(0, NVT);
+        Hi = DAG.getConstant(0, NVT);
+      } else if (Cst > NVTBits) {
+        Lo = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst-NVTBits,ShTy));
+        Hi = DAG.getConstant(0, NVT);
+      } else if (Cst == NVTBits) {
+        Lo = InH;
+        Hi = DAG.getConstant(0, NVT);
+      } else {
+        Lo = DAG.getNode(ISD::OR, NVT,
+           DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
+           DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
+        Hi = DAG.getNode(ISD::SRL, NVT, InH, DAG.getConstant(Cst, ShTy));
+      }
+      return true;
+    case ISD::SRA:
+      if (Cst > VTBits) {
+        Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH,
+                              DAG.getConstant(NVTBits-1, ShTy));
+      } else if (Cst > NVTBits) {
+        Lo = DAG.getNode(ISD::SRA, NVT, InH,
+                           DAG.getConstant(Cst-NVTBits, ShTy));
+        Hi = DAG.getNode(ISD::SRA, NVT, InH,
+                              DAG.getConstant(NVTBits-1, ShTy));
+      } else if (Cst == NVTBits) {
+        Lo = InH;
+        Hi = DAG.getNode(ISD::SRA, NVT, InH,
+                              DAG.getConstant(NVTBits-1, ShTy));
+      } else {
+        Lo = DAG.getNode(ISD::OR, NVT,
+           DAG.getNode(ISD::SRL, NVT, InL, DAG.getConstant(Cst, ShTy)),
+           DAG.getNode(ISD::SHL, NVT, InH, DAG.getConstant(NVTBits-Cst, ShTy)));
+        Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst, ShTy));
+      }
+      return true;
+    }
+  }
+  // FIXME: The following code for expanding shifts using ISD::SELECT is buggy,
+  // so disable it for now.  Currently targets are handling this via SHL_PARTS
+  // and friends.
+  return false;
 
   // If we have an efficient select operation (or if the selects will all fold
   // away), lower to some complex code, otherwise just emit the libcall.
@@ -1325,10 +1893,6 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
 
   SDOperand InL, InH;
   ExpandOp(Op, InL, InH);
-  SDOperand ShAmt = LegalizeOp(Amt);
-  MVT::ValueType ShTy = ShAmt.getValueType();
-  
-  unsigned NVTBits = MVT::getSizeInBits(NVT);
   SDOperand NAmt = DAG.getNode(ISD::SUB, ShTy,           // NAmt = 32-ShAmt
                                DAG.getConstant(NVTBits, ShTy), ShAmt);
 
@@ -1348,7 +1912,7 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
                                DAG.getNode(ISD::SHL, NVT, InH, ShAmt),
                                DAG.getNode(ISD::SRL, NVT, InL, NAmt));
     SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31
-    
+
     Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1);
     Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2);
   } else {
@@ -1375,15 +1939,15 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
   return true;
 }
 
-/// FindLatestAdjCallStackDown - Scan up the dag to find the latest (highest
-/// NodeDepth) node that is an AdjCallStackDown operation and occurs later than
+/// FindLatestCallSeqStart - Scan up the dag to find the latest (highest
+/// NodeDepth) node that is an CallSeqStart operation and occurs later than
 /// Found.
-static void FindLatestAdjCallStackDown(SDNode *Node, SDNode *&Found) {
+static void FindLatestCallSeqStart(SDNode *Node, SDNode *&Found) {
   if (Node->getNodeDepth() <= Found->getNodeDepth()) return;
 
-  // If we found an ADJCALLSTACKDOWN, we already know this node occurs later
+  // If we found an CALLSEQ_START, we already know this node occurs later
   // than the Found node. Just remember this node and return.
-  if (Node->getOpcode() == ISD::ADJCALLSTACKDOWN) {
+  if (Node->getOpcode() == ISD::CALLSEQ_START) {
     Found = Node;
     return;
   }
@@ -1392,23 +1956,23 @@ static void FindLatestAdjCallStackDown(SDNode *Node, SDNode *&Found) {
   assert(Node->getNumOperands() != 0 &&
          "All leaves should have depth equal to the entry node!");
   for (unsigned i = 0, e = Node->getNumOperands()-1; i != e; ++i)
-    FindLatestAdjCallStackDown(Node->getOperand(i).Val, Found);
+    FindLatestCallSeqStart(Node->getOperand(i).Val, Found);
 
   // Tail recurse for the last iteration.
-  FindLatestAdjCallStackDown(Node->getOperand(Node->getNumOperands()-1).Val,
+  FindLatestCallSeqStart(Node->getOperand(Node->getNumOperands()-1).Val,
                              Found);
 }
 
 
-/// FindEarliestAdjCallStackUp - Scan down the dag to find the earliest (lowest
-/// NodeDepth) node that is an AdjCallStackUp operation and occurs more recent
+/// FindEarliestCallSeqEnd - Scan down the dag to find the earliest (lowest
+/// NodeDepth) node that is an CallSeqEnd operation and occurs more recent
 /// than Found.
-static void FindEarliestAdjCallStackUp(SDNode *Node, SDNode *&Found) {
+static void FindEarliestCallSeqEnd(SDNode *Node, SDNode *&Found) {
   if (Found && Node->getNodeDepth() >= Found->getNodeDepth()) return;
 
-  // If we found an ADJCALLSTACKUP, we already know this node occurs earlier
+  // If we found an CALLSEQ_END, we already know this node occurs earlier
   // than the Found node. Just remember this node and return.
-  if (Node->getOpcode() == ISD::ADJCALLSTACKUP) {
+  if (Node->getOpcode() == ISD::CALLSEQ_END) {
     Found = Node;
     return;
   }
@@ -1417,65 +1981,105 @@ static void FindEarliestAdjCallStackUp(SDNode *Node, SDNode *&Found) {
   SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
   if (UI == E) return;
   for (--E; UI != E; ++UI)
-    FindEarliestAdjCallStackUp(*UI, Found);
+    FindEarliestCallSeqEnd(*UI, Found);
 
   // Tail recurse for the last iteration.
-  FindEarliestAdjCallStackUp(*UI, Found);
+  FindEarliestCallSeqEnd(*UI, Found);
 }
 
-/// FindAdjCallStackUp - Given a chained node that is part of a call sequence,
-/// find the ADJCALLSTACKUP node that terminates the call sequence.
-static SDNode *FindAdjCallStackUp(SDNode *Node) {
-  if (Node->getOpcode() == ISD::ADJCALLSTACKUP)
+/// FindCallSeqEnd - Given a chained node that is part of a call sequence,
+/// find the CALLSEQ_END node that terminates the call sequence.
+static SDNode *FindCallSeqEnd(SDNode *Node) {
+  if (Node->getOpcode() == ISD::CALLSEQ_END)
     return Node;
   if (Node->use_empty())
-    return 0;   // No adjcallstackup
+    return 0;   // No CallSeqEnd
 
   if (Node->hasOneUse())  // Simple case, only has one user to check.
-    return FindAdjCallStackUp(*Node->use_begin());
-  
+    return FindCallSeqEnd(*Node->use_begin());
+
   SDOperand TheChain(Node, Node->getNumValues()-1);
   assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!");
-  
-  for (SDNode::use_iterator UI = Node->use_begin(), 
+
+  for (SDNode::use_iterator UI = Node->use_begin(),
          E = Node->use_end(); ; ++UI) {
-    assert(UI != E && "Didn't find a user of the tokchain, no ADJCALLSTACKUP!");
-    
+    assert(UI != E && "Didn't find a user of the tokchain, no CALLSEQ_END!");
+
     // Make sure to only follow users of our token chain.
     SDNode *User = *UI;
     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
       if (User->getOperand(i) == TheChain)
-        return FindAdjCallStackUp(User);
+        if (SDNode *Result = FindCallSeqEnd(User))
+          return Result;
   }
   assert(0 && "Unreachable");
   abort();
 }
 
+/// FindCallSeqStart - Given a chained node that is part of a call sequence,
+/// find the CALLSEQ_START node that initiates the call sequence.
+static SDNode *FindCallSeqStart(SDNode *Node) {
+  assert(Node && "Didn't find callseq_start for a call??");
+  if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
+
+  assert(Node->getOperand(0).getValueType() == MVT::Other &&
+         "Node doesn't have a token chain argument!");
+  return FindCallSeqStart(Node->getOperand(0).Val);
+}
+
+
 /// FindInputOutputChains - If we are replacing an operation with a call we need
 /// to find the call that occurs before and the call that occurs after it to
-/// properly serialize the calls in the block.
+/// properly serialize the calls in the block.  The returned operand is the
+/// input chain value for the new call (e.g. the entry node or the previous
+/// call), and OutChain is set to be the chain node to update to point to the
+/// end of the call chain.
 static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain,
                                        SDOperand Entry) {
-  SDNode *LatestAdjCallStackDown = Entry.Val;
-  FindLatestAdjCallStackDown(OpNode, LatestAdjCallStackDown);
-  //std::cerr << "Found node: "; LatestAdjCallStackDown->dump(); std::cerr <<"\n";
-
-  SDNode *LatestAdjCallStackUp = FindAdjCallStackUp(LatestAdjCallStackDown);
-
+  SDNode *LatestCallSeqStart = Entry.Val;
+  SDNode *LatestCallSeqEnd = 0;
+  FindLatestCallSeqStart(OpNode, LatestCallSeqStart);
+  //std::cerr<<"Found node: "; LatestCallSeqStart->dump(); std::cerr <<"\n";
+
+  // It is possible that no ISD::CALLSEQ_START was found because there is no
+  // previous call in the function.  LatestCallStackDown may in that case be
+  // the entry node itself.  Do not attempt to find a matching CALLSEQ_END
+  // unless LatestCallStackDown is an CALLSEQ_START.
+  if (LatestCallSeqStart->getOpcode() == ISD::CALLSEQ_START)
+    LatestCallSeqEnd = FindCallSeqEnd(LatestCallSeqStart);
+  else
+    LatestCallSeqEnd = Entry.Val;
+  assert(LatestCallSeqEnd && "NULL return from FindCallSeqEnd");
+
+  // Finally, find the first call that this must come before, first we find the
+  // CallSeqEnd that ends the call.
+  OutChain = 0;
+  FindEarliestCallSeqEnd(OpNode, OutChain);
+
+  // If we found one, translate from the adj up to the callseq_start.
+  if (OutChain)
+    OutChain = FindCallSeqStart(OutChain);
+
+  return SDOperand(LatestCallSeqEnd, 0);
+}
 
-  SDNode *EarliestAdjCallStackUp = 0;
-  FindEarliestAdjCallStackUp(OpNode, EarliestAdjCallStackUp);
+/// SpliceCallInto - Given the result chain of a libcall (CallResult), and a 
+void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult,
+                                          SDNode *OutChain) {
+  // Nothing to splice it into?
+  if (OutChain == 0) return;
 
-  if (EarliestAdjCallStackUp) {
-    //std::cerr << "Found node: "; 
-    //EarliestAdjCallStackUp->dump(); std::cerr <<"\n";
-  }
+  assert(OutChain->getOperand(0).getValueType() == MVT::Other);
+  //OutChain->dump();
 
-  return SDOperand(LatestAdjCallStackUp, 0);
+  // Form a token factor node merging the old inval and the new inval.
+  SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult,
+                                  OutChain->getOperand(0));
+  // Change the node to refer to the new token.
+  OutChain->setAdjCallChain(InToken);
 }
 
 
-
 // ExpandLibCall - Expand a node into a call to a libcall.  If the result value
 // does not fit into a register, return the lo part and set the hi part to the
 // by-reg argument.  If it does fit into a single register, return the result
@@ -1495,22 +2099,24 @@ SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node,
     Args.push_back(std::make_pair(Node->getOperand(i), ArgTy));
   }
   SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy());
-  
-  // We don't care about token chains for libcalls.  We just use the entry
-  // node as our input and ignore the output chain.  This allows us to place
-  // calls wherever we need them to satisfy data dependences.
+
+  // Splice the libcall in wherever FindInputOutputChains tells us to.
   const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0));
-  SDOperand Result = TLI.LowerCallTo(InChain, RetTy, false, Callee,
-                                     Args, DAG).first;
-  switch (getTypeAction(Result.getValueType())) {
+  std::pair<SDOperand,SDOperand> CallInfo =
+    TLI.LowerCallTo(InChain, RetTy, false, 0, Callee, Args, DAG);
+  SpliceCallInto(CallInfo.second, OutChain);
+
+  NeedsAnotherIteration = true;
+
+  switch (getTypeAction(CallInfo.first.getValueType())) {
   default: assert(0 && "Unknown thing");
   case Legal:
-    return Result;
+    return CallInfo.first;
   case Promote:
     assert(0 && "Cannot promote this yet!");
   case Expand:
     SDOperand Lo;
-    ExpandOp(Result, Lo, Hi);
+    ExpandOp(CallInfo.first, Lo, Hi);
     return Lo;
   }
 }
@@ -1525,39 +2131,81 @@ ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) {
          "This is not an expansion!");
   assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!");
 
-  SDNode *OutChain;
-  SDOperand InChain = FindInputOutputChains(Source.Val, OutChain,
-                                            DAG.getEntryNode());
+  if (!isSigned) {
+    assert(Source.getValueType() == MVT::i64 &&
+           "This only works for 64-bit -> FP");
+    // The 64-bit value loaded will be incorrectly if the 'sign bit' of the
+    // incoming integer is set.  To handle this, we dynamically test to see if
+    // it is set, and, if so, add a fudge factor.
+    SDOperand Lo, Hi;
+    ExpandOp(Source, Lo, Hi);
 
-  const char *FnName = 0;
-  if (isSigned) {
+    // If this is unsigned, and not supported, first perform the conversion to
+    // signed, then adjust the result if the sign bit is set.
+    SDOperand SignedConv = ExpandIntToFP(true, DestTy,
+                   DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), Lo, Hi));
+
+    SDOperand SignSet = DAG.getSetCC(ISD::SETLT, TLI.getSetCCResultTy(), Hi,
+                                     DAG.getConstant(0, Hi.getValueType()));
+    SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4);
+    SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(),
+                                      SignSet, Four, Zero);
+    uint64_t FF = 0x5f800000ULL;
+    if (TLI.isLittleEndian()) FF <<= 32;
+    static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF);
+
+    MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool();
+    SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor),
+                                          TLI.getPointerTy());
+    CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset);
+    SDOperand FudgeInReg;
     if (DestTy == MVT::f32)
-      FnName = "__floatdisf";
+      FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx,
+                               DAG.getSrcValue(NULL));
     else {
-      assert(DestTy == MVT::f64 && "Unknown fp value type!");
-      FnName = "__floatdidf";
+      assert(DestTy == MVT::f64 && "Unexpected conversion");
+      FudgeInReg = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(),
+                               CPIdx, DAG.getSrcValue(NULL), MVT::f32);
     }
-  } else {
-    // If this is unsigned, and not supported, first perform the conversion to
-    // signed, then adjust the result if the sign bit is set.
-    SDOperand SignedConv = ExpandIntToFP(false, DestTy, Source);
+    return DAG.getNode(ISD::ADD, DestTy, SignedConv, FudgeInReg);
+  }
+
+  // Expand the source, then glue it back together for the call.  We must expand
+  // the source in case it is shared (this pass of legalize must traverse it).
+  SDOperand SrcLo, SrcHi;
+  ExpandOp(Source, SrcLo, SrcHi);
+  Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi);
 
-    assert(0 && "Unsigned casts not supported yet!");
+  SDNode *OutChain = 0;
+  SDOperand InChain = FindInputOutputChains(Source.Val, OutChain,
+                                            DAG.getEntryNode());
+  const char *FnName = 0;
+  if (DestTy == MVT::f32)
+    FnName = "__floatdisf";
+  else {
+    assert(DestTy == MVT::f64 && "Unknown fp value type!");
+    FnName = "__floatdidf";
   }
+
   SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy());
 
   TargetLowering::ArgListTy Args;
   const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType());
+
   Args.push_back(std::make_pair(Source, ArgTy));
 
   // We don't care about token chains for libcalls.  We just use the entry
   // node as our input and ignore the output chain.  This allows us to place
   // calls wherever we need them to satisfy data dependences.
   const Type *RetTy = MVT::getTypeForValueType(DestTy);
-  return TLI.LowerCallTo(InChain, RetTy, false, Callee, Args, DAG).first;
-                         
+
+  std::pair<SDOperand,SDOperand> CallResult =
+    TLI.LowerCallTo(InChain, RetTy, false, 0, Callee, Args, DAG);
+
+  SpliceCallInto(CallResult.second, OutChain);
+  return CallResult.first;
 }
-                   
+
 
 
 /// ExpandOp - Expand the specified SDOperand into its two component pieces
@@ -1585,6 +2233,8 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
       Hi = I->second.second;
       return;
     }
+  } else {
+    assert(!ExpandedNodes.count(Op) && "Re-expanding a node!");
   }
 
   // Expanding to multiple registers needs to perform an optimization step, and
@@ -1613,7 +2263,7 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
     // Aggregate register values are always in consequtive pairs.
     Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0));
     Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1));
-    
+
     // Remember that we legalized the chain.
     AddLegalizedOperand(Op.getValue(1), Hi.getValue(1));
 
@@ -1629,22 +2279,62 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
     Hi = LegalizeOp(Node->getOperand(1));
     break;
 
+  case ISD::CTPOP:
+    ExpandOp(Node->getOperand(0), Lo, Hi);
+    Lo = DAG.getNode(ISD::ADD, NVT,          // ctpop(HL) -> ctpop(H)+ctpop(L)
+                     DAG.getNode(ISD::CTPOP, NVT, Lo),
+                     DAG.getNode(ISD::CTPOP, NVT, Hi));
+    Hi = DAG.getConstant(0, NVT);
+    break;
+
+  case ISD::CTLZ: {
+    // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32)
+    ExpandOp(Node->getOperand(0), Lo, Hi);
+    SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
+    SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
+    SDOperand TopNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(),
+                                        HLZ, BitsC);
+    SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo);
+    LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC);
+
+    Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart);
+    Hi = DAG.getConstant(0, NVT);
+    break;
+  }
+
+  case ISD::CTTZ: {
+    // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32)
+    ExpandOp(Node->getOperand(0), Lo, Hi);
+    SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT);
+    SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
+    SDOperand BotNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(),
+                                        LTZ, BitsC);
+    SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi);
+    HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC);
+
+    Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart);
+    Hi = DAG.getConstant(0, NVT);
+    break;
+  }
+
   case ISD::LOAD: {
     SDOperand Ch = LegalizeOp(Node->getOperand(0));   // Legalize the chain.
     SDOperand Ptr = LegalizeOp(Node->getOperand(1));  // Legalize the pointer.
-    Lo = DAG.getLoad(NVT, Ch, Ptr);
+    Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
 
     // Increment the pointer to the other half.
     unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8;
     Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
                       getIntPtrConstant(IncrementSize));
-    Hi = DAG.getLoad(NVT, Ch, Ptr);
+    //Is this safe?  declaring that the two parts of the split load  
+    //are from the same instruction?
+    Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2));
 
     // Build a factor node to remember that this load is independent of the
     // other one.
     SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1),
                                Hi.getValue(1));
-    
+
     // Remember that we legalized the chain.
     AddLegalizedOperand(Op.getValue(1), TF);
     if (!TLI.isLittleEndian())
@@ -1707,10 +2397,22 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
     break;
   }
   case ISD::SIGN_EXTEND: {
+    SDOperand In;
+    switch (getTypeAction(Node->getOperand(0).getValueType())) {
+    case Expand: assert(0 && "expand-expand not implemented yet!");
+    case Legal: In = LegalizeOp(Node->getOperand(0)); break;
+    case Promote:
+      In = PromoteOp(Node->getOperand(0));
+      // Emit the appropriate sign_extend_inreg to get the value we want.
+      In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(), In,
+                       Node->getOperand(0).getValueType());
+      break;
+    }
+
     // The low part is just a sign extension of the input (which degenerates to
     // a copy).
-    Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
-    
+    Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In);
+
     // The high part is obtained by SRA'ing all but one of the bits of the lo
     // part.
     unsigned LoSize = MVT::getSizeInBits(Lo.getValueType());
@@ -1718,15 +2420,26 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
                                                        TLI.getShiftAmountTy()));
     break;
   }
-  case ISD::ZERO_EXTEND:
+  case ISD::ZERO_EXTEND: {
+    SDOperand In;
+    switch (getTypeAction(Node->getOperand(0).getValueType())) {
+    case Expand: assert(0 && "expand-expand not implemented yet!");
+    case Legal: In = LegalizeOp(Node->getOperand(0)); break;
+    case Promote:
+      In = PromoteOp(Node->getOperand(0));
+      // Emit the appropriate zero_extend_inreg to get the value we want.
+      In = DAG.getZeroExtendInReg(In, Node->getOperand(0).getValueType());
+      break;
+    }
+
     // The low part is just a zero extension of the input (which degenerates to
     // a copy).
-    Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, LegalizeOp(Node->getOperand(0)));
-    
+    Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In);
+
     // The high part is just a zero.
     Hi = DAG.getConstant(0, NVT);
     break;
-
+  }
     // These operators cannot be expanded directly, emit them as calls to
     // library functions.
   case ISD::FP_TO_SINT:
@@ -1746,6 +2459,14 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
     // If we can emit an efficient shift operation, do so now.
     if (ExpandShift(ISD::SHL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
       break;
+
+    // If this target supports SHL_PARTS, use it.
+    if (TLI.getOperationAction(ISD::SHL_PARTS, NVT) == TargetLowering::Legal) {
+      ExpandShiftParts(ISD::SHL_PARTS, Node->getOperand(0), Node->getOperand(1),
+                       Lo, Hi);
+      break;
+    }
+
     // Otherwise, emit a libcall.
     Lo = ExpandLibCall("__ashldi3", Node, Hi);
     break;
@@ -1754,6 +2475,14 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
     // If we can emit an efficient shift operation, do so now.
     if (ExpandShift(ISD::SRA, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
       break;
+
+    // If this target supports SRA_PARTS, use it.
+    if (TLI.getOperationAction(ISD::SRA_PARTS, NVT) == TargetLowering::Legal) {
+      ExpandShiftParts(ISD::SRA_PARTS, Node->getOperand(0), Node->getOperand(1),
+                       Lo, Hi);
+      break;
+    }
+
     // Otherwise, emit a libcall.
     Lo = ExpandLibCall("__ashrdi3", Node, Hi);
     break;
@@ -1761,17 +2490,42 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
     // If we can emit an efficient shift operation, do so now.
     if (ExpandShift(ISD::SRL, Node->getOperand(0), Node->getOperand(1), Lo, Hi))
       break;
+
+    // If this target supports SRL_PARTS, use it.
+    if (TLI.getOperationAction(ISD::SRL_PARTS, NVT) == TargetLowering::Legal) {
+      ExpandShiftParts(ISD::SRL_PARTS, Node->getOperand(0), Node->getOperand(1),
+                       Lo, Hi);
+      break;
+    }
+
     // Otherwise, emit a libcall.
     Lo = ExpandLibCall("__lshrdi3", Node, Hi);
     break;
 
   case ISD::ADD:
-    ExpandAddSub(true, Node->getOperand(0), Node->getOperand(1), Lo, Hi);
+    ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1),
+                  Lo, Hi);
     break;
   case ISD::SUB:
-    ExpandAddSub(false, Node->getOperand(0), Node->getOperand(1), Lo, Hi);
+    ExpandByParts(ISD::SUB_PARTS, Node->getOperand(0), Node->getOperand(1),
+                  Lo, Hi);
     break;
-  case ISD::MUL:  Lo = ExpandLibCall("__muldi3" , Node, Hi); break;
+  case ISD::MUL: {
+    if (TLI.getOperationAction(ISD::MULHU, NVT) == TargetLowering::Legal) {
+      SDOperand LL, LH, RL, RH;
+      ExpandOp(Node->getOperand(0), LL, LH);
+      ExpandOp(Node->getOperand(1), RL, RH);
+      Hi = DAG.getNode(ISD::MULHU, NVT, LL, RL);
+      RH = DAG.getNode(ISD::MUL, NVT, LL, RH);
+      LH = DAG.getNode(ISD::MUL, NVT, LH, RL);
+      Hi = DAG.getNode(ISD::ADD, NVT, Hi, RH);
+      Hi = DAG.getNode(ISD::ADD, NVT, Hi, LH);
+      Lo = DAG.getNode(ISD::MUL, NVT, LL, RL);
+    } else {
+      Lo = ExpandLibCall("__muldi3" , Node, Hi); break;
+    }
+    break;
+  }
   case ISD::SDIV: Lo = ExpandLibCall("__divdi3" , Node, Hi); break;
   case ISD::UDIV: Lo = ExpandLibCall("__udivdi3", Node, Hi); break;
   case ISD::SREM: Lo = ExpandLibCall("__moddi3" , Node, Hi); break;