Split type expansion into ExpandInteger and ExpandFloat

rather than bundling them together.  Rename FloatToInt
to PromoteFloat (better, if not perfect).  Reorganize
files by types rather than by operations.


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

1 files changed, 2174 insertions, 0 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
new file mode 100644
index 0000000000..4b927fec08
--- /dev/null
+++ b/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
@@ -0,0 +1,2174 @@
+//===----- LegalizeIntegerTypes.cpp - Legalization of integer types -------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements integer type expansion and promotion for LegalizeTypes.
+// Promotion is the act of changing a computation in an illegal type into a
+// computation in a larger type.  For example, implementing i8 arithmetic in an
+// i32 register (often needed on powerpc).
+// Expansion is the act of changing a computation in an illegal type into a
+// computation in multiple registers of a smaller type.  For example,
+// implementing i64 arithmetic in two i32 registers (often needed on 32-bit
+// targets).
+//
+//===----------------------------------------------------------------------===//
+
+#include "LegalizeTypes.h"
+#include "llvm/Constants.h"
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+//  Integer Result Promotion
+//===----------------------------------------------------------------------===//
+
+/// PromoteIntegerResult - This method is called when a result of a node is
+/// found to be in need of promotion to a larger type.  At this point, the node
+/// may also have invalid operands or may have other results that need
+/// expansion, we just know that (at least) one result needs promotion.
+void DAGTypeLegalizer::PromoteIntegerResult(SDNode *N, unsigned ResNo) {
+  DEBUG(cerr << "Promote integer result: "; N->dump(&DAG); cerr << "\n");
+  SDOperand Result = SDOperand();
+
+  switch (N->getOpcode()) {
+  default:
+#ifndef NDEBUG
+    cerr << "PromoteIntegerResult #" << ResNo << ": ";
+    N->dump(&DAG); cerr << "\n";
+#endif
+    assert(0 && "Do not know how to promote this operator!");
+    abort();
+  case ISD::UNDEF:    Result = PromoteIntRes_UNDEF(N); break;
+  case ISD::Constant: Result = PromoteIntRes_Constant(N); break;
+
+  case ISD::TRUNCATE:    Result = PromoteIntRes_TRUNCATE(N); break;
+  case ISD::SIGN_EXTEND:
+  case ISD::ZERO_EXTEND:
+  case ISD::ANY_EXTEND:  Result = PromoteIntRes_INT_EXTEND(N); break;
+  case ISD::FP_ROUND:    Result = PromoteIntRes_FP_ROUND(N); break;
+  case ISD::FP_TO_SINT:
+  case ISD::FP_TO_UINT:  Result = PromoteIntRes_FP_TO_XINT(N); break;
+  case ISD::SETCC:    Result = PromoteIntRes_SETCC(N); break;
+  case ISD::LOAD:     Result = PromoteIntRes_LOAD(cast<LoadSDNode>(N)); break;
+  case ISD::BUILD_PAIR:  Result = PromoteIntRes_BUILD_PAIR(N); break;
+  case ISD::BIT_CONVERT: Result = PromoteIntRes_BIT_CONVERT(N); break;
+
+  case ISD::AND:
+  case ISD::OR:
+  case ISD::XOR:
+  case ISD::ADD:
+  case ISD::SUB:
+  case ISD::MUL:      Result = PromoteIntRes_SimpleIntBinOp(N); break;
+
+  case ISD::SDIV:
+  case ISD::SREM:     Result = PromoteIntRes_SDIV(N); break;
+
+  case ISD::UDIV:
+  case ISD::UREM:     Result = PromoteIntRes_UDIV(N); break;
+
+  case ISD::SHL:      Result = PromoteIntRes_SHL(N); break;
+  case ISD::SRA:      Result = PromoteIntRes_SRA(N); break;
+  case ISD::SRL:      Result = PromoteIntRes_SRL(N); break;
+
+  case ISD::SELECT:    Result = PromoteIntRes_SELECT(N); break;
+  case ISD::SELECT_CC: Result = PromoteIntRes_SELECT_CC(N); break;
+
+  case ISD::CTLZ:     Result = PromoteIntRes_CTLZ(N); break;
+  case ISD::CTPOP:    Result = PromoteIntRes_CTPOP(N); break;
+  case ISD::CTTZ:     Result = PromoteIntRes_CTTZ(N); break;
+
+  case ISD::EXTRACT_VECTOR_ELT:
+    Result = PromoteIntRes_EXTRACT_VECTOR_ELT(N);
+    break;
+  }
+
+  // If Result is null, the sub-method took care of registering the result.
+  if (Result.Val)
+    SetPromotedInteger(SDOperand(N, ResNo), Result);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_UNDEF(SDNode *N) {
+  return DAG.getNode(ISD::UNDEF, TLI.getTypeToTransformTo(N->getValueType(0)));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_Constant(SDNode *N) {
+  MVT VT = N->getValueType(0);
+  // Zero extend things like i1, sign extend everything else.  It shouldn't
+  // matter in theory which one we pick, but this tends to give better code?
+  unsigned Opc = VT.isByteSized() ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
+  SDOperand Result = DAG.getNode(Opc, TLI.getTypeToTransformTo(VT),
+                                 SDOperand(N, 0));
+  assert(isa<ConstantSDNode>(Result) && "Didn't constant fold ext?");
+  return Result;
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_TRUNCATE(SDNode *N) {
+  SDOperand Res;
+
+  switch (getTypeAction(N->getOperand(0).getValueType())) {
+  default: assert(0 && "Unknown type action!");
+  case Legal:
+  case ExpandInteger:
+    Res = N->getOperand(0);
+    break;
+  case PromoteInteger:
+    Res = GetPromotedInteger(N->getOperand(0));
+    break;
+  }
+
+  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
+  assert(Res.getValueType().getSizeInBits() >= NVT.getSizeInBits() &&
+         "Truncation doesn't make sense!");
+  if (Res.getValueType() == NVT)
+    return Res;
+
+  // Truncate to NVT instead of VT
+  return DAG.getNode(ISD::TRUNCATE, NVT, Res);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_INT_EXTEND(SDNode *N) {
+  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
+
+  if (getTypeAction(N->getOperand(0).getValueType()) == PromoteInteger) {
+    SDOperand Res = GetPromotedInteger(N->getOperand(0));
+    assert(Res.getValueType().getSizeInBits() <= NVT.getSizeInBits() &&
+           "Extension doesn't make sense!");
+
+    // If the result and operand types are the same after promotion, simplify
+    // to an in-register extension.
+    if (NVT == Res.getValueType()) {
+      // The high bits are not guaranteed to be anything.  Insert an extend.
+      if (N->getOpcode() == ISD::SIGN_EXTEND)
+        return DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Res,
+                           DAG.getValueType(N->getOperand(0).getValueType()));
+      if (N->getOpcode() == ISD::ZERO_EXTEND)
+        return DAG.getZeroExtendInReg(Res, N->getOperand(0).getValueType());
+      assert(N->getOpcode() == ISD::ANY_EXTEND && "Unknown integer extension!");
+      return Res;
+    }
+  }
+
+  // Otherwise, just extend the original operand all the way to the larger type.
+  return DAG.getNode(N->getOpcode(), NVT, N->getOperand(0));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_FP_ROUND(SDNode *N) {
+  // NOTE: Assumes input is legal.
+  if (N->getConstantOperandVal(1) == 0)
+    return DAG.getNode(ISD::FP_ROUND_INREG, N->getOperand(0).getValueType(),
+                       N->getOperand(0), DAG.getValueType(N->getValueType(0)));
+  // If the precision discard isn't needed, just return the operand unrounded.
+  return N->getOperand(0);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_FP_TO_XINT(SDNode *N) {
+  unsigned NewOpc = N->getOpcode();
+  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
+
+  // If we're promoting a UINT to a larger size, check to see if the new node
+  // will be legal.  If it isn't, check to see if FP_TO_SINT is legal, since
+  // we can use that instead.  This allows us to generate better code for
+  // FP_TO_UINT for small destination sizes on targets where FP_TO_UINT is not
+  // legal, such as PowerPC.
+  if (N->getOpcode() == ISD::FP_TO_UINT) {
+    if (!TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
+        (TLI.isOperationLegal(ISD::FP_TO_SINT, NVT) ||
+         TLI.getOperationAction(ISD::FP_TO_SINT, NVT)==TargetLowering::Custom))
+      NewOpc = ISD::FP_TO_SINT;
+  }
+
+  return DAG.getNode(NewOpc, NVT, N->getOperand(0));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SETCC(SDNode *N) {
+  assert(isTypeLegal(TLI.getSetCCResultType(N->getOperand(0)))
+         && "SetCC type is not legal??");
+  return DAG.getNode(ISD::SETCC, TLI.getSetCCResultType(N->getOperand(0)),
+                     N->getOperand(0), N->getOperand(1), N->getOperand(2));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_LOAD(LoadSDNode *N) {
+  // FIXME: Add support for indexed loads.
+  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
+  ISD::LoadExtType ExtType =
+    ISD::isNON_EXTLoad(N) ? ISD::EXTLOAD : N->getExtensionType();
+  SDOperand Res = DAG.getExtLoad(ExtType, NVT, N->getChain(), N->getBasePtr(),
+                                 N->getSrcValue(), N->getSrcValueOffset(),
+                                 N->getMemoryVT(), N->isVolatile(),
+                                 N->getAlignment());
+
+  // Legalized the chain result - switch anything that used the old chain to
+  // use the new one.
+  ReplaceValueWith(SDOperand(N, 1), Res.getValue(1));
+  return Res;
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_BUILD_PAIR(SDNode *N) {
+  // The pair element type may be legal, or may not promote to the same type as
+  // the result, for example i14 = BUILD_PAIR (i7, i7).  Handle all cases.
+  return DAG.getNode(ISD::ANY_EXTEND,
+                     TLI.getTypeToTransformTo(N->getValueType(0)),
+                     JoinIntegers(N->getOperand(0), N->getOperand(1)));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_BIT_CONVERT(SDNode *N) {
+  SDOperand InOp = N->getOperand(0);
+  MVT InVT = InOp.getValueType();
+  MVT NInVT = TLI.getTypeToTransformTo(InVT);
+  MVT OutVT = TLI.getTypeToTransformTo(N->getValueType(0));
+
+  switch (getTypeAction(InVT)) {
+  default:
+    assert(false && "Unknown type action!");
+    break;
+  case Legal:
+    break;
+  case PromoteInteger:
+    if (OutVT.getSizeInBits() == NInVT.getSizeInBits())
+      // The input promotes to the same size.  Convert the promoted value.
+      return DAG.getNode(ISD::BIT_CONVERT, OutVT, GetPromotedInteger(InOp));
+    break;
+  case PromoteFloat:
+    // Promote the integer operand by hand.
+    return DAG.getNode(ISD::ANY_EXTEND, OutVT, GetPromotedFloat(InOp));
+  case ExpandInteger:
+  case ExpandFloat:
+    break;
+  case Scalarize:
+    // Convert the element to an integer and promote it by hand.
+    return DAG.getNode(ISD::ANY_EXTEND, OutVT,
+                       BitConvertToInteger(GetScalarizedVector(InOp)));
+  case Split:
+    // For example, i32 = BIT_CONVERT v2i16 on alpha.  Convert the split
+    // pieces of the input into integers and reassemble in the final type.
+    SDOperand Lo, Hi;
+    GetSplitVector(N->getOperand(0), Lo, Hi);
+    Lo = BitConvertToInteger(Lo);
+    Hi = BitConvertToInteger(Hi);
+
+    if (TLI.isBigEndian())
+      std::swap(Lo, Hi);
+
+    InOp = DAG.getNode(ISD::ANY_EXTEND,
+                       MVT::getIntegerVT(OutVT.getSizeInBits()),
+                       JoinIntegers(Lo, Hi));
+    return DAG.getNode(ISD::BIT_CONVERT, OutVT, InOp);
+  }
+
+  // Otherwise, lower the bit-convert to a store/load from the stack, then
+  // promote the load.
+  SDOperand Op = CreateStackStoreLoad(InOp, N->getValueType(0));
+  return PromoteIntRes_LOAD(cast<LoadSDNode>(Op.Val));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SimpleIntBinOp(SDNode *N) {
+  // The input may have strange things in the top bits of the registers, but
+  // these operations don't care.  They may have weird bits going out, but
+  // that too is okay if they are integer operations.
+  SDOperand LHS = GetPromotedInteger(N->getOperand(0));
+  SDOperand RHS = GetPromotedInteger(N->getOperand(1));
+  return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SDIV(SDNode *N) {
+  // Sign extend the input.
+  SDOperand LHS = GetPromotedInteger(N->getOperand(0));
+  SDOperand RHS = GetPromotedInteger(N->getOperand(1));
+  MVT VT = N->getValueType(0);
+  LHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, LHS.getValueType(), LHS,
+                    DAG.getValueType(VT));
+  RHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, RHS.getValueType(), RHS,
+                    DAG.getValueType(VT));
+
+  return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_UDIV(SDNode *N) {
+  // Zero extend the input.
+  SDOperand LHS = GetPromotedInteger(N->getOperand(0));
+  SDOperand RHS = GetPromotedInteger(N->getOperand(1));
+  MVT VT = N->getValueType(0);
+  LHS = DAG.getZeroExtendInReg(LHS, VT);
+  RHS = DAG.getZeroExtendInReg(RHS, VT);
+
+  return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SHL(SDNode *N) {
+  return DAG.getNode(ISD::SHL, TLI.getTypeToTransformTo(N->getValueType(0)),
+                     GetPromotedInteger(N->getOperand(0)), N->getOperand(1));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SRA(SDNode *N) {
+  // The input value must be properly sign extended.
+  MVT VT = N->getValueType(0);
+  MVT NVT = TLI.getTypeToTransformTo(VT);
+  SDOperand Res = GetPromotedInteger(N->getOperand(0));
+  Res = DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Res, DAG.getValueType(VT));
+  return DAG.getNode(ISD::SRA, NVT, Res, N->getOperand(1));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SRL(SDNode *N) {
+  // The input value must be properly zero extended.
+  MVT VT = N->getValueType(0);
+  MVT NVT = TLI.getTypeToTransformTo(VT);
+  SDOperand Res = ZExtPromotedInteger(N->getOperand(0));
+  return DAG.getNode(ISD::SRL, NVT, Res, N->getOperand(1));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SELECT(SDNode *N) {
+  SDOperand LHS = GetPromotedInteger(N->getOperand(1));
+  SDOperand RHS = GetPromotedInteger(N->getOperand(2));
+  return DAG.getNode(ISD::SELECT, LHS.getValueType(), N->getOperand(0),LHS,RHS);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_SELECT_CC(SDNode *N) {
+  SDOperand LHS = GetPromotedInteger(N->getOperand(2));
+  SDOperand RHS = GetPromotedInteger(N->getOperand(3));
+  return DAG.getNode(ISD::SELECT_CC, LHS.getValueType(), N->getOperand(0),
+                     N->getOperand(1), LHS, RHS, N->getOperand(4));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_CTLZ(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  MVT OVT = N->getValueType(0);
+  MVT NVT = Op.getValueType();
+  // Zero extend to the promoted type and do the count there.
+  Op = DAG.getNode(ISD::CTLZ, NVT, DAG.getZeroExtendInReg(Op, OVT));
+  // Subtract off the extra leading bits in the bigger type.
+  return DAG.getNode(ISD::SUB, NVT, Op,
+                     DAG.getConstant(NVT.getSizeInBits() -
+                                     OVT.getSizeInBits(), NVT));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_CTPOP(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  MVT OVT = N->getValueType(0);
+  MVT NVT = Op.getValueType();
+  // Zero extend to the promoted type and do the count there.
+  return DAG.getNode(ISD::CTPOP, NVT, DAG.getZeroExtendInReg(Op, OVT));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_CTTZ(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  MVT OVT = N->getValueType(0);
+  MVT NVT = Op.getValueType();
+  // The count is the same in the promoted type except if the original
+  // value was zero.  This can be handled by setting the bit just off
+  // the top of the original type.
+  Op = DAG.getNode(ISD::OR, NVT, Op,
+                   // FIXME: Do this using an APINT constant.
+                   DAG.getConstant(1UL << OVT.getSizeInBits(), NVT));
+  return DAG.getNode(ISD::CTTZ, NVT, Op);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntRes_EXTRACT_VECTOR_ELT(SDNode *N) {
+  MVT OldVT = N->getValueType(0);
+  SDOperand OldVec = N->getOperand(0);
+  unsigned OldElts = OldVec.getValueType().getVectorNumElements();
+
+  if (OldElts == 1) {
+    assert(!isTypeLegal(OldVec.getValueType()) &&
+           "Legal one-element vector of a type needing promotion!");
+    // It is tempting to follow GetScalarizedVector by a call to
+    // GetPromotedInteger, but this would be wrong because the
+    // scalarized value may not yet have been processed.
+    return DAG.getNode(ISD::ANY_EXTEND, TLI.getTypeToTransformTo(OldVT),
+                       GetScalarizedVector(OldVec));
+  }
+
+  // Convert to a vector half as long with an element type of twice the width,
+  // for example <4 x i16> -> <2 x i32>.
+  assert(!(OldElts & 1) && "Odd length vectors not supported!");
+  MVT NewVT = MVT::getIntegerVT(2 * OldVT.getSizeInBits());
+  assert(OldVT.isSimple() && NewVT.isSimple());
+
+  SDOperand NewVec = DAG.getNode(ISD::BIT_CONVERT,
+                                 MVT::getVectorVT(NewVT, OldElts / 2),
+                                 OldVec);
+
+  // Extract the element at OldIdx / 2 from the new vector.
+  SDOperand OldIdx = N->getOperand(1);
+  SDOperand NewIdx = DAG.getNode(ISD::SRL, OldIdx.getValueType(), OldIdx,
+                                 DAG.getConstant(1, TLI.getShiftAmountTy()));
+  SDOperand Elt = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, NewVT, NewVec, NewIdx);
+
+  // Select the appropriate half of the element: Lo if OldIdx was even,
+  // Hi if it was odd.
+  SDOperand Lo = Elt;
+  SDOperand Hi = DAG.getNode(ISD::SRL, NewVT, Elt,
+                             DAG.getConstant(OldVT.getSizeInBits(),
+                                             TLI.getShiftAmountTy()));
+  if (TLI.isBigEndian())
+    std::swap(Lo, Hi);
+
+  SDOperand Odd = DAG.getNode(ISD::AND, OldIdx.getValueType(), OldIdx,
+                              DAG.getConstant(1, TLI.getShiftAmountTy()));
+  return DAG.getNode(ISD::SELECT, NewVT, Odd, Hi, Lo);
+}
+
+//===----------------------------------------------------------------------===//
+//  Integer Operand Promotion
+//===----------------------------------------------------------------------===//
+
+/// PromoteIntegerOperand - This method is called when the specified operand of
+/// the specified node is found to need promotion.  At this point, all of the
+/// result types of the node are known to be legal, but other operands of the
+/// node may need promotion or expansion as well as the specified one.
+bool DAGTypeLegalizer::PromoteIntegerOperand(SDNode *N, unsigned OpNo) {
+  DEBUG(cerr << "Promote integer operand: "; N->dump(&DAG); cerr << "\n");
+  SDOperand Res;
+  switch (N->getOpcode()) {
+    default:
+#ifndef NDEBUG
+    cerr << "PromoteIntegerOperand Op #" << OpNo << ": ";
+    N->dump(&DAG); cerr << "\n";
+#endif
+    assert(0 && "Do not know how to promote this operator's operand!");
+    abort();
+
+  case ISD::ANY_EXTEND:  Res = PromoteIntOp_ANY_EXTEND(N); break;
+  case ISD::ZERO_EXTEND: Res = PromoteIntOp_ZERO_EXTEND(N); break;
+  case ISD::SIGN_EXTEND: Res = PromoteIntOp_SIGN_EXTEND(N); break;
+  case ISD::TRUNCATE:    Res = PromoteIntOp_TRUNCATE(N); break;
+  case ISD::FP_EXTEND:   Res = PromoteIntOp_FP_EXTEND(N); break;
+  case ISD::FP_ROUND:    Res = PromoteIntOp_FP_ROUND(N); break;
+  case ISD::SINT_TO_FP:
+  case ISD::UINT_TO_FP:  Res = PromoteIntOp_INT_TO_FP(N); break;
+  case ISD::BUILD_PAIR:  Res = PromoteIntOp_BUILD_PAIR(N); break;
+
+  case ISD::SELECT:      Res = PromoteIntOp_SELECT(N, OpNo); break;
+  case ISD::BRCOND:      Res = PromoteIntOp_BRCOND(N, OpNo); break;
+  case ISD::BR_CC:       Res = PromoteIntOp_BR_CC(N, OpNo); break;
+  case ISD::SETCC:       Res = PromoteIntOp_SETCC(N, OpNo); break;
+
+  case ISD::STORE:       Res = PromoteIntOp_STORE(cast<StoreSDNode>(N),
+                                                    OpNo); break;
+
+  case ISD::BUILD_VECTOR: Res = PromoteIntOp_BUILD_VECTOR(N); break;
+  case ISD::INSERT_VECTOR_ELT:
+    Res = PromoteIntOp_INSERT_VECTOR_ELT(N, OpNo);
+    break;
+
+  case ISD::MEMBARRIER:  Res = PromoteIntOp_MEMBARRIER(N); break;
+  }
+
+  // If the result is null, the sub-method took care of registering results etc.
+  if (!Res.Val) return false;
+  // If the result is N, the sub-method updated N in place.
+  if (Res.Val == N) {
+    // Mark N as new and remark N and its operands.  This allows us to correctly
+    // revisit N if it needs another step of promotion and allows us to visit
+    // any new operands to N.
+    ReanalyzeNode(N);
+    return true;
+  }
+
+  assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
+         "Invalid operand expansion");
+
+  ReplaceValueWith(SDOperand(N, 0), Res);
+  return false;
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_ANY_EXTEND(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  return DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_ZERO_EXTEND(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  Op = DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op);
+  return DAG.getZeroExtendInReg(Op, N->getOperand(0).getValueType());
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_SIGN_EXTEND(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  Op = DAG.getNode(ISD::ANY_EXTEND, N->getValueType(0), Op);
+  return DAG.getNode(ISD::SIGN_EXTEND_INREG, Op.getValueType(),
+                     Op, DAG.getValueType(N->getOperand(0).getValueType()));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_TRUNCATE(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  return DAG.getNode(ISD::TRUNCATE, N->getValueType(0), Op);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_FP_EXTEND(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  return DAG.getNode(ISD::FP_EXTEND, N->getValueType(0), Op);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_FP_ROUND(SDNode *N) {
+  SDOperand Op = GetPromotedInteger(N->getOperand(0));
+  return DAG.getNode(ISD::FP_ROUND, N->getValueType(0), Op,
+                     DAG.getIntPtrConstant(0));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_INT_TO_FP(SDNode *N) {
+  SDOperand In = GetPromotedInteger(N->getOperand(0));
+  MVT OpVT = N->getOperand(0).getValueType();
+  if (N->getOpcode() == ISD::UINT_TO_FP)
+    In = DAG.getZeroExtendInReg(In, OpVT);
+  else
+    In = DAG.getNode(ISD::SIGN_EXTEND_INREG, In.getValueType(),
+                     In, DAG.getValueType(OpVT));
+
+  return DAG.UpdateNodeOperands(SDOperand(N, 0), In);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_BUILD_PAIR(SDNode *N) {
+  // Since the result type is legal, the operands must promote to it.
+  MVT OVT = N->getOperand(0).getValueType();
+  SDOperand Lo = GetPromotedInteger(N->getOperand(0));
+  SDOperand Hi = GetPromotedInteger(N->getOperand(1));
+  assert(Lo.getValueType() == N->getValueType(0) && "Operand over promoted?");
+
+  Lo = DAG.getZeroExtendInReg(Lo, OVT);
+  Hi = DAG.getNode(ISD::SHL, N->getValueType(0), Hi,
+                   DAG.getConstant(OVT.getSizeInBits(),
+                                   TLI.getShiftAmountTy()));
+  return DAG.getNode(ISD::OR, N->getValueType(0), Lo, Hi);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_SELECT(SDNode *N, unsigned OpNo) {
+  assert(OpNo == 0 && "Only know how to promote condition");
+  SDOperand Cond = GetPromotedInteger(N->getOperand(0));  // Promote condition.
+
+  // The top bits of the promoted condition are not necessarily zero, ensure
+  // that the value is properly zero extended.
+  unsigned BitWidth = Cond.getValueSizeInBits();
+  if (!DAG.MaskedValueIsZero(Cond,
+                             APInt::getHighBitsSet(BitWidth, BitWidth-1)))
+    Cond = DAG.getZeroExtendInReg(Cond, MVT::i1);
+
+  // The chain (Op#0) and basic block destination (Op#2) are always legal types.
+  return DAG.UpdateNodeOperands(SDOperand(N, 0), Cond, N->getOperand(1),
+                                N->getOperand(2));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_BRCOND(SDNode *N, unsigned OpNo) {
+  assert(OpNo == 1 && "only know how to promote condition");
+  SDOperand Cond = GetPromotedInteger(N->getOperand(1));  // Promote condition.
+
+  // The top bits of the promoted condition are not necessarily zero, ensure
+  // that the value is properly zero extended.
+  unsigned BitWidth = Cond.getValueSizeInBits();
+  if (!DAG.MaskedValueIsZero(Cond,
+                             APInt::getHighBitsSet(BitWidth, BitWidth-1)))
+    Cond = DAG.getZeroExtendInReg(Cond, MVT::i1);
+
+  // The chain (Op#0) and basic block destination (Op#2) are always legal types.
+  return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0), Cond,
+                                N->getOperand(2));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_BR_CC(SDNode *N, unsigned OpNo) {
+  assert(OpNo == 2 && "Don't know how to promote this operand");
+
+  SDOperand LHS = N->getOperand(2);
+  SDOperand RHS = N->getOperand(3);
+  PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(1))->get());
+
+  // The chain (Op#0), CC (#1) and basic block destination (Op#4) are always
+  // legal types.
+  return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0),
+                                N->getOperand(1), LHS, RHS, N->getOperand(4));
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_SETCC(SDNode *N, unsigned OpNo) {
+  assert(OpNo == 0 && "Don't know how to promote this operand");
+
+  SDOperand LHS = N->getOperand(0);
+  SDOperand RHS = N->getOperand(1);
+  PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(2))->get());
+
+  // The CC (#2) is always legal.
+  return DAG.UpdateNodeOperands(SDOperand(N, 0), LHS, RHS, N->getOperand(2));
+}
+
+/// PromoteSetCCOperands - Promote the operands of a comparison.  This code is
+/// shared among BR_CC, SELECT_CC, and SETCC handlers.
+void DAGTypeLegalizer::PromoteSetCCOperands(SDOperand &NewLHS,SDOperand &NewRHS,
+                                            ISD::CondCode CCCode) {
+  MVT VT = NewLHS.getValueType();
+
+  // Get the promoted values.
+  NewLHS = GetPromotedInteger(NewLHS);
+  NewRHS = GetPromotedInteger(NewRHS);
+
+  // If this is an FP compare, the operands have already been extended.
+  if (!NewLHS.getValueType().isInteger())
+    return;
+
+  // Otherwise, we have to insert explicit sign or zero extends.  Note
+  // that we could insert sign extends for ALL conditions, but zero extend
+  // is cheaper on many machines (an AND instead of two shifts), so prefer
+  // it.
+  switch (CCCode) {
+  default: assert(0 && "Unknown integer comparison!");
+  case ISD::SETEQ:
+  case ISD::SETNE:
+  case ISD::SETUGE:
+  case ISD::SETUGT:
+  case ISD::SETULE:
+  case ISD::SETULT:
+    // 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.
+    NewLHS = DAG.getZeroExtendInReg(NewLHS, VT);
+    NewRHS = DAG.getZeroExtendInReg(NewRHS, VT);
+    return;
+  case ISD::SETGE:
+  case ISD::SETGT:
+  case ISD::SETLT:
+  case ISD::SETLE:
+    NewLHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, NewLHS.getValueType(), NewLHS,
+                         DAG.getValueType(VT));
+    NewRHS = DAG.getNode(ISD::SIGN_EXTEND_INREG, NewRHS.getValueType(), NewRHS,
+                         DAG.getValueType(VT));
+    return;
+  }
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_STORE(StoreSDNode *N, unsigned OpNo){
+  // FIXME: Add support for indexed stores.
+  SDOperand Ch = N->getChain(), Ptr = N->getBasePtr();
+  int SVOffset = N->getSrcValueOffset();
+  unsigned Alignment = N->getAlignment();
+  bool isVolatile = N->isVolatile();
+
+  SDOperand Val = GetPromotedInteger(N->getValue());  // Get promoted value.
+
+  assert(!N->isTruncatingStore() && "Cannot promote this store operand!");
+
+  // Truncate the value and store the result.
+  return DAG.getTruncStore(Ch, Val, Ptr, N->getSrcValue(),
+                           SVOffset, N->getMemoryVT(),
+                           isVolatile, Alignment);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_BUILD_VECTOR(SDNode *N) {
+  // The vector type is legal but the element type is not.  This implies
+  // that the vector is a power-of-two in length and that the element
+  // type does not have a strange size (eg: it is not i1).
+  MVT VecVT = N->getValueType(0);
+  unsigned NumElts = VecVT.getVectorNumElements();
+  assert(!(NumElts & 1) && "Legal vector of one illegal element?");
+
+  // Build a vector of half the length out of elements of twice the bitwidth.
+  // For example <4 x i16> -> <2 x i32>.
+  MVT OldVT = N->getOperand(0).getValueType();
+  MVT NewVT = MVT::getIntegerVT(2 * OldVT.getSizeInBits());
+  assert(OldVT.isSimple() && NewVT.isSimple());
+
+  std::vector<SDOperand> NewElts;
+  NewElts.reserve(NumElts/2);
+
+  for (unsigned i = 0; i < NumElts; i += 2) {
+    // Combine two successive elements into one promoted element.
+    SDOperand Lo = N->getOperand(i);
+    SDOperand Hi = N->getOperand(i+1);
+    if (TLI.isBigEndian())
+      std::swap(Lo, Hi);
+    NewElts.push_back(JoinIntegers(Lo, Hi));
+  }
+
+  SDOperand NewVec = DAG.getNode(ISD::BUILD_VECTOR,
+                                 MVT::getVectorVT(NewVT, NewElts.size()),
+                                 &NewElts[0], NewElts.size());
+
+  // Convert the new vector to the old vector type.
+  return DAG.getNode(ISD::BIT_CONVERT, VecVT, NewVec);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_INSERT_VECTOR_ELT(SDNode *N,
+                                                             unsigned OpNo) {
+  if (OpNo == 1) {
+    // Promote the inserted value.  This is valid because the type does not
+    // have to match the vector element type.
+
+    // Check that any extra bits introduced will be truncated away.
+    assert(N->getOperand(1).getValueType().getSizeInBits() >=
+           N->getValueType(0).getVectorElementType().getSizeInBits() &&
+           "Type of inserted value narrower than vector element type!");
+    return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0),
+                                  GetPromotedInteger(N->getOperand(1)),
+                                  N->getOperand(2));
+  }
+
+  assert(OpNo == 2 && "Different operand and result vector types?");
+
+  // Promote the index.
+  SDOperand Idx = N->getOperand(2);
+  Idx = DAG.getZeroExtendInReg(GetPromotedInteger(Idx), Idx.getValueType());
+  return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0),
+                                N->getOperand(1), Idx);
+}
+
+SDOperand DAGTypeLegalizer::PromoteIntOp_MEMBARRIER(SDNode *N) {
+  SDOperand NewOps[6];
+  NewOps[0] = N->getOperand(0);
+  for (unsigned i = 1; i < array_lengthof(NewOps); ++i) {
+    SDOperand Flag = GetPromotedInteger(N->getOperand(i));
+    NewOps[i] = DAG.getZeroExtendInReg(Flag, MVT::i1);
+  }
+  return DAG.UpdateNodeOperands(SDOperand (N, 0), NewOps,
+                                array_lengthof(NewOps));
+}
+
+
+//===----------------------------------------------------------------------===//
+//  Integer Result Expansion
+//===----------------------------------------------------------------------===//
+
+/// ExpandIntegerResult - This method is called when the specified result of the
+/// specified node is found to need expansion.  At this point, the node may also
+/// have invalid operands or may have other results that need promotion, we just
+/// know that (at least) one result needs expansion.
+void DAGTypeLegalizer::ExpandIntegerResult(SDNode *N, unsigned ResNo) {
+  DEBUG(cerr << "Expand integer result: "; N->dump(&DAG); cerr << "\n");
+  SDOperand Lo, Hi;
+  Lo = Hi = SDOperand();
+
+  // See if the target wants to custom expand this node.
+  if (TLI.getOperationAction(N->getOpcode(), N->getValueType(0)) ==
+          TargetLowering::Custom) {
+    // If the target wants to, allow it to lower this itself.
+    if (SDNode *P = TLI.ExpandOperationResult(N, DAG)) {
+      // Everything that once used N now uses P.  We are guaranteed that the
+      // result value types of N and the result value types of P match.
+      ReplaceNodeWith(N, P);
+      return;
+    }
+  }
+
+  switch (N->getOpcode()) {
+  default:
+#ifndef NDEBUG
+    cerr << "ExpandIntegerResult #" << ResNo << ": ";
+    N->dump(&DAG); cerr << "\n";
+#endif
+    assert(0&&"Do not know how to expand the result of this operator!");
+    abort();
+
+  case ISD::UNDEF:       ExpandIntRes_UNDEF(N, Lo, Hi); break;
+  case ISD::Constant:    ExpandIntRes_Constant(N, Lo, Hi); break;
+  case ISD::BUILD_PAIR:  ExpandIntRes_BUILD_PAIR(N, Lo, Hi); break;
+  case ISD::MERGE_VALUES: ExpandIntRes_MERGE_VALUES(N, Lo, Hi); break;
+  case ISD::ANY_EXTEND:  ExpandIntRes_ANY_EXTEND(N, Lo, Hi); break;
+  case ISD::ZERO_EXTEND: ExpandIntRes_ZERO_EXTEND(N, Lo, Hi); break;
+  case ISD::SIGN_EXTEND: ExpandIntRes_SIGN_EXTEND(N, Lo, Hi); break;
+  case ISD::AssertZext:  ExpandIntRes_AssertZext(N, Lo, Hi); break;
+  case ISD::TRUNCATE:    ExpandIntRes_TRUNCATE(N, Lo, Hi); break;
+  case ISD::BIT_CONVERT: ExpandIntRes_BIT_CONVERT(N, Lo, Hi); break;
+  case ISD::SIGN_EXTEND_INREG: ExpandIntRes_SIGN_EXTEND_INREG(N, Lo, Hi); break;
+  case ISD::FP_TO_SINT:  ExpandIntRes_FP_TO_SINT(N, Lo, Hi); break;
+  case ISD::FP_TO_UINT:  ExpandIntRes_FP_TO_UINT(N, Lo, Hi); break;
+  case ISD::LOAD:        ExpandIntRes_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
+
+  case ISD::AND:
+  case ISD::OR:
+  case ISD::XOR:         ExpandIntRes_Logical(N, Lo, Hi); break;
+  case ISD::BSWAP:       ExpandIntRes_BSWAP(N, Lo, Hi); break;
+  case ISD::ADD:
+  case ISD::SUB:         ExpandIntRes_ADDSUB(N, Lo, Hi); break;
+  case ISD::ADDC:
+  case ISD::SUBC:        ExpandIntRes_ADDSUBC(N, Lo, Hi); break;
+  case ISD::ADDE:
+  case ISD::SUBE:        ExpandIntRes_ADDSUBE(N, Lo, Hi); break;
+  case ISD::SELECT:      ExpandIntRes_SELECT(N, Lo, Hi); break;
+  case ISD::SELECT_CC:   ExpandIntRes_SELECT_CC(N, Lo, Hi); break;
+  case ISD::MUL:         ExpandIntRes_MUL(N, Lo, Hi); break;
+  case ISD::SDIV:        ExpandIntRes_SDIV(N, Lo, Hi); break;
+  case ISD::SREM:        ExpandIntRes_SREM(N, Lo, Hi); break;
+  case ISD::UDIV:        ExpandIntRes_UDIV(N, Lo, Hi); break;
+  case ISD::UREM:        ExpandIntRes_UREM(N, Lo, Hi); break;
+  case ISD::SHL:
+  case ISD::SRA:
+  case ISD::SRL:         ExpandIntRes_Shift(N, Lo, Hi); break;
+
+  case ISD::CTLZ:        ExpandIntRes_CTLZ(N, Lo, Hi); break;
+  case ISD::CTPOP:       ExpandIntRes_CTPOP(N, Lo, Hi); break;
+  case ISD::CTTZ:        ExpandIntRes_CTTZ(N, Lo, Hi); break;
+
+  case ISD::EXTRACT_VECTOR_ELT:
+    ExpandIntRes_EXTRACT_VECTOR_ELT(N, Lo, Hi);
+    break;
+  }
+
+  // If Lo/Hi is null, the sub-method took care of registering results etc.
+  if (Lo.Val)
+    SetExpandedInteger(SDOperand(N, ResNo), Lo, Hi);
+}
+
+void DAGTypeLegalizer::ExpandIntRes_UNDEF(SDNode *N,
+                                          SDOperand &Lo, SDOperand &Hi) {
+  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
+  Lo = Hi = DAG.getNode(ISD::UNDEF, NVT);
+}
+
+void DAGTypeLegalizer::ExpandIntRes_Constant(SDNode *N,
+                                             SDOperand &Lo, SDOperand &Hi) {
+  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
+  unsigned NBitWidth = NVT.getSizeInBits();
+  const APInt &Cst = cast<ConstantSDNode>(N)->getAPIntValue();
+  Lo = DAG.getConstant(APInt(Cst).trunc(NBitWidth), NVT);
+  Hi = DAG.getConstant(Cst.lshr(NBitWidth).trunc(NBitWidth), NVT);
+}
+
+void DAGTypeLegalizer::ExpandIntRes_BUILD_PAIR(SDNode *N,
+                                               SDOperand &Lo, SDOperand &Hi) {
+  // Return the operands.
+  Lo = N->getOperand(0);
+  Hi = N->getOperand(1);
+}
+
+void DAGTypeLegalizer::ExpandIntRes_MERGE_VALUES(SDNode *N,
+                                                 SDOperand &Lo, SDOperand &Hi) {
+  // A MERGE_VALUES node can produce any number of values.  We know that the
+  // first illegal one needs to be expanded into Lo/Hi.
+  unsigned i;
+
+  // The string of legal results gets turns into the input operands, which have
+  // the same type.
+  for (i = 0; isTypeLegal(N->getValueType(i)); ++i)
+    ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
+
+  // The first illegal result must be the one that needs to be expanded.
+  GetExpandedInteger(N->getOperand(i), Lo, Hi);
+
+  // Legalize the rest of the results into the input operands whether they are
+  // legal or not.
+  unsigned e = N->getNumValues();
+  for (++i; i != e; ++i)
+    ReplaceValueWith(SDOperand(N, i), SDOperand(N->getOperand(i)));
+}
+
+void DAGTypeLegalizer::ExpandIntRes_ANY_EXTEND(SDNode *N,
+                                               SDOperand &Lo, SDOperand &Hi) {
+  MVT NVT = TLI.getTypeToTransformTo(N->getValueType(0));
+  SDOperand Op = N->getOperand(0);
+  if (Op.getValueType().bitsLE(NVT)) {
+    // The low part is any extension of the input (which degenerates to a copy).
+    Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, Op);
+    Hi = DAG.g