LLVM API Documentation

LegalizeIntegerTypes.cpp

Go to the documentation of this file.
00001 //===----- LegalizeIntegerTypes.cpp - Legalization of integer types -------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements integer type expansion and promotion for LegalizeTypes.
00011 // Promotion is the act of changing a computation in an illegal type into a
00012 // computation in a larger type.  For example, implementing i8 arithmetic in an
00013 // i32 register (often needed on powerpc).
00014 // Expansion is the act of changing a computation in an illegal type into a
00015 // computation in two identical registers of a smaller type.  For example,
00016 // implementing i64 arithmetic in two i32 registers (often needed on 32-bit
00017 // targets).
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #include "LegalizeTypes.h"
00022 #include "llvm/CodeGen/PseudoSourceValue.h"
00023 #include "llvm/Support/ErrorHandling.h"
00024 #include "llvm/Support/raw_ostream.h"
00025 using namespace llvm;
00026 
00027 //===----------------------------------------------------------------------===//
00028 //  Integer Result Promotion
00029 //===----------------------------------------------------------------------===//
00030 
00031 /// PromoteIntegerResult - This method is called when a result of a node is
00032 /// found to be in need of promotion to a larger type.  At this point, the node
00033 /// may also have invalid operands or may have other results that need
00034 /// expansion, we just know that (at least) one result needs promotion.
00035 void DAGTypeLegalizer::PromoteIntegerResult(SDNode *N, unsigned ResNo) {
00036   DEBUG(errs() << "Promote integer result: "; N->dump(&DAG); errs() << "\n");
00037   SDValue Res = SDValue();
00038 
00039   // See if the target wants to custom expand this node.
00040   if (CustomLowerNode(N, N->getValueType(ResNo), true))
00041     return;
00042 
00043   switch (N->getOpcode()) {
00044   default:
00045 #ifndef NDEBUG
00046     errs() << "PromoteIntegerResult #" << ResNo << ": ";
00047     N->dump(&DAG); errs() << "\n";
00048 #endif
00049     llvm_unreachable("Do not know how to promote this operator!");
00050   case ISD::AssertSext:  Res = PromoteIntRes_AssertSext(N); break;
00051   case ISD::AssertZext:  Res = PromoteIntRes_AssertZext(N); break;
00052   case ISD::BIT_CONVERT: Res = PromoteIntRes_BIT_CONVERT(N); break;
00053   case ISD::BSWAP:       Res = PromoteIntRes_BSWAP(N); break;
00054   case ISD::BUILD_PAIR:  Res = PromoteIntRes_BUILD_PAIR(N); break;
00055   case ISD::Constant:    Res = PromoteIntRes_Constant(N); break;
00056   case ISD::CONVERT_RNDSAT:
00057                          Res = PromoteIntRes_CONVERT_RNDSAT(N); break;
00058   case ISD::CTLZ:        Res = PromoteIntRes_CTLZ(N); break;
00059   case ISD::CTPOP:       Res = PromoteIntRes_CTPOP(N); break;
00060   case ISD::CTTZ:        Res = PromoteIntRes_CTTZ(N); break;
00061   case ISD::EXTRACT_VECTOR_ELT:
00062                          Res = PromoteIntRes_EXTRACT_VECTOR_ELT(N); break;
00063   case ISD::LOAD:        Res = PromoteIntRes_LOAD(cast<LoadSDNode>(N));break;
00064   case ISD::SELECT:      Res = PromoteIntRes_SELECT(N); break;
00065   case ISD::SELECT_CC:   Res = PromoteIntRes_SELECT_CC(N); break;
00066   case ISD::SETCC:       Res = PromoteIntRes_SETCC(N); break;
00067   case ISD::SHL:         Res = PromoteIntRes_SHL(N); break;
00068   case ISD::SIGN_EXTEND_INREG:
00069                          Res = PromoteIntRes_SIGN_EXTEND_INREG(N); break;
00070   case ISD::SRA:         Res = PromoteIntRes_SRA(N); break;
00071   case ISD::SRL:         Res = PromoteIntRes_SRL(N); break;
00072   case ISD::TRUNCATE:    Res = PromoteIntRes_TRUNCATE(N); break;
00073   case ISD::UNDEF:       Res = PromoteIntRes_UNDEF(N); break;
00074   case ISD::VAARG:       Res = PromoteIntRes_VAARG(N); break;
00075 
00076   case ISD::SIGN_EXTEND:
00077   case ISD::ZERO_EXTEND:
00078   case ISD::ANY_EXTEND:  Res = PromoteIntRes_INT_EXTEND(N); break;
00079 
00080   case ISD::FP_TO_SINT:
00081   case ISD::FP_TO_UINT:  Res = PromoteIntRes_FP_TO_XINT(N); break;
00082 
00083   case ISD::AND:
00084   case ISD::OR:
00085   case ISD::XOR:
00086   case ISD::ADD:
00087   case ISD::SUB:
00088   case ISD::MUL:         Res = PromoteIntRes_SimpleIntBinOp(N); break;
00089 
00090   case ISD::SDIV:
00091   case ISD::SREM:        Res = PromoteIntRes_SDIV(N); break;
00092 
00093   case ISD::UDIV:
00094   case ISD::UREM:        Res = PromoteIntRes_UDIV(N); break;
00095 
00096   case ISD::SADDO:
00097   case ISD::SSUBO:       Res = PromoteIntRes_SADDSUBO(N, ResNo); break;
00098   case ISD::UADDO:
00099   case ISD::USUBO:       Res = PromoteIntRes_UADDSUBO(N, ResNo); break;
00100   case ISD::SMULO:
00101   case ISD::UMULO:       Res = PromoteIntRes_XMULO(N, ResNo); break;
00102 
00103   case ISD::ATOMIC_LOAD_ADD:
00104   case ISD::ATOMIC_LOAD_SUB:
00105   case ISD::ATOMIC_LOAD_AND:
00106   case ISD::ATOMIC_LOAD_OR:
00107   case ISD::ATOMIC_LOAD_XOR:
00108   case ISD::ATOMIC_LOAD_NAND:
00109   case ISD::ATOMIC_LOAD_MIN:
00110   case ISD::ATOMIC_LOAD_MAX:
00111   case ISD::ATOMIC_LOAD_UMIN:
00112   case ISD::ATOMIC_LOAD_UMAX:
00113   case ISD::ATOMIC_SWAP:
00114     Res = PromoteIntRes_Atomic1(cast<AtomicSDNode>(N)); break;
00115 
00116   case ISD::ATOMIC_CMP_SWAP:
00117     Res = PromoteIntRes_Atomic2(cast<AtomicSDNode>(N)); break;
00118   }
00119 
00120   // If the result is null then the sub-method took care of registering it.
00121   if (Res.getNode())
00122     SetPromotedInteger(SDValue(N, ResNo), Res);
00123 }
00124 
00125 SDValue DAGTypeLegalizer::PromoteIntRes_AssertSext(SDNode *N) {
00126   // Sign-extend the new bits, and continue the assertion.
00127   SDValue Op = SExtPromotedInteger(N->getOperand(0));
00128   return DAG.getNode(ISD::AssertSext, N->getDebugLoc(),
00129                      Op.getValueType(), Op, N->getOperand(1));
00130 }
00131 
00132 SDValue DAGTypeLegalizer::PromoteIntRes_AssertZext(SDNode *N) {
00133   // Zero the new bits, and continue the assertion.
00134   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
00135   return DAG.getNode(ISD::AssertZext, N->getDebugLoc(),
00136                      Op.getValueType(), Op, N->getOperand(1));
00137 }
00138 
00139 SDValue DAGTypeLegalizer::PromoteIntRes_Atomic1(AtomicSDNode *N) {
00140   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
00141   SDValue Res = DAG.getAtomic(N->getOpcode(), N->getDebugLoc(),
00142                               N->getMemoryVT(),
00143                               N->getChain(), N->getBasePtr(),
00144                               Op2, N->getSrcValue(), N->getAlignment());
00145   // Legalized the chain result - switch anything that used the old chain to
00146   // use the new one.
00147   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
00148   return Res;
00149 }
00150 
00151 SDValue DAGTypeLegalizer::PromoteIntRes_Atomic2(AtomicSDNode *N) {
00152   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
00153   SDValue Op3 = GetPromotedInteger(N->getOperand(3));
00154   SDValue Res = DAG.getAtomic(N->getOpcode(), N->getDebugLoc(),
00155                               N->getMemoryVT(), N->getChain(), N->getBasePtr(),
00156                               Op2, Op3, N->getSrcValue(), N->getAlignment());
00157   // Legalized the chain result - switch anything that used the old chain to
00158   // use the new one.
00159   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
00160   return Res;
00161 }
00162 
00163 SDValue DAGTypeLegalizer::PromoteIntRes_BIT_CONVERT(SDNode *N) {
00164   SDValue InOp = N->getOperand(0);
00165   EVT InVT = InOp.getValueType();
00166   EVT NInVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT);
00167   EVT OutVT = N->getValueType(0);
00168   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
00169   DebugLoc dl = N->getDebugLoc();
00170 
00171   switch (getTypeAction(InVT)) {
00172   default:
00173     assert(false && "Unknown type action!");
00174     break;
00175   case Legal:
00176     break;
00177   case PromoteInteger:
00178     if (NOutVT.bitsEq(NInVT))
00179       // The input promotes to the same size.  Convert the promoted value.
00180       return DAG.getNode(ISD::BIT_CONVERT, dl,
00181                          NOutVT, GetPromotedInteger(InOp));
00182     break;
00183   case SoftenFloat:
00184     // Promote the integer operand by hand.
00185     return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT, GetSoftenedFloat(InOp));
00186   case ExpandInteger:
00187   case ExpandFloat:
00188     break;
00189   case ScalarizeVector:
00190     // Convert the element to an integer and promote it by hand.
00191     return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT,
00192                        BitConvertToInteger(GetScalarizedVector(InOp)));
00193   case SplitVector: {
00194     // For example, i32 = BIT_CONVERT v2i16 on alpha.  Convert the split
00195     // pieces of the input into integers and reassemble in the final type.
00196     SDValue Lo, Hi;
00197     GetSplitVector(N->getOperand(0), Lo, Hi);
00198     Lo = BitConvertToInteger(Lo);
00199     Hi = BitConvertToInteger(Hi);
00200 
00201     if (TLI.isBigEndian())
00202       std::swap(Lo, Hi);
00203 
00204     InOp = DAG.getNode(ISD::ANY_EXTEND, dl,
00205                        EVT::getIntegerVT(*DAG.getContext(), NOutVT.getSizeInBits()),
00206                        JoinIntegers(Lo, Hi));
00207     return DAG.getNode(ISD::BIT_CONVERT, dl, NOutVT, InOp);
00208   }
00209   case WidenVector:
00210     if (OutVT.bitsEq(NInVT))
00211       // The input is widened to the same size.  Convert to the widened value.
00212       return DAG.getNode(ISD::BIT_CONVERT, dl, OutVT, GetWidenedVector(InOp));
00213   }
00214 
00215   return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT,
00216                      CreateStackStoreLoad(InOp, OutVT));
00217 }
00218 
00219 SDValue DAGTypeLegalizer::PromoteIntRes_BSWAP(SDNode *N) {
00220   SDValue Op = GetPromotedInteger(N->getOperand(0));
00221   EVT OVT = N->getValueType(0);
00222   EVT NVT = Op.getValueType();
00223   DebugLoc dl = N->getDebugLoc();
00224 
00225   unsigned DiffBits = NVT.getSizeInBits() - OVT.getSizeInBits();
00226   return DAG.getNode(ISD::SRL, dl, NVT, DAG.getNode(ISD::BSWAP, dl, NVT, Op),
00227                      DAG.getConstant(DiffBits, TLI.getPointerTy()));
00228 }
00229 
00230 SDValue DAGTypeLegalizer::PromoteIntRes_BUILD_PAIR(SDNode *N) {
00231   // The pair element type may be legal, or may not promote to the same type as
00232   // the result, for example i14 = BUILD_PAIR (i7, i7).  Handle all cases.
00233   return DAG.getNode(ISD::ANY_EXTEND, N->getDebugLoc(),
00234                      TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0)),
00235                      JoinIntegers(N->getOperand(0), N->getOperand(1)));
00236 }
00237 
00238 SDValue DAGTypeLegalizer::PromoteIntRes_Constant(SDNode *N) {
00239   EVT VT = N->getValueType(0);
00240   // FIXME there is no actual debug info here
00241   DebugLoc dl = N->getDebugLoc();
00242   // Zero extend things like i1, sign extend everything else.  It shouldn't
00243   // matter in theory which one we pick, but this tends to give better code?
00244   unsigned Opc = VT.isByteSized() ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
00245   SDValue Result = DAG.getNode(Opc, dl, TLI.getTypeToTransformTo(*DAG.getContext(), VT),
00246                                SDValue(N, 0));
00247   assert(isa<ConstantSDNode>(Result) && "Didn't constant fold ext?");
00248   return Result;
00249 }
00250 
00251 SDValue DAGTypeLegalizer::PromoteIntRes_CONVERT_RNDSAT(SDNode *N) {
00252   ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
00253   assert ((CvtCode == ISD::CVT_SS || CvtCode == ISD::CVT_SU ||
00254            CvtCode == ISD::CVT_US || CvtCode == ISD::CVT_UU ||
00255            CvtCode == ISD::CVT_SF || CvtCode == ISD::CVT_UF) &&
00256           "can only promote integers");
00257   EVT OutVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00258   return DAG.getConvertRndSat(OutVT, N->getDebugLoc(), N->getOperand(0),
00259                               N->getOperand(1), N->getOperand(2),
00260                               N->getOperand(3), N->getOperand(4), CvtCode);
00261 }
00262 
00263 SDValue DAGTypeLegalizer::PromoteIntRes_CTLZ(SDNode *N) {
00264   // Zero extend to the promoted type and do the count there.
00265   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
00266   DebugLoc dl = N->getDebugLoc();
00267   EVT OVT = N->getValueType(0);
00268   EVT NVT = Op.getValueType();
00269   Op = DAG.getNode(ISD::CTLZ, dl, NVT, Op);
00270   // Subtract off the extra leading bits in the bigger type.
00271   return DAG.getNode(ISD::SUB, dl, NVT, Op,
00272                      DAG.getConstant(NVT.getSizeInBits() -
00273                                      OVT.getSizeInBits(), NVT));
00274 }
00275 
00276 SDValue DAGTypeLegalizer::PromoteIntRes_CTPOP(SDNode *N) {
00277   // Zero extend to the promoted type and do the count there.
00278   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
00279   return DAG.getNode(ISD::CTPOP, N->getDebugLoc(), Op.getValueType(), Op);
00280 }
00281 
00282 SDValue DAGTypeLegalizer::PromoteIntRes_CTTZ(SDNode *N) {
00283   SDValue Op = GetPromotedInteger(N->getOperand(0));
00284   EVT OVT = N->getValueType(0);
00285   EVT NVT = Op.getValueType();
00286   DebugLoc dl = N->getDebugLoc();
00287   // The count is the same in the promoted type except if the original
00288   // value was zero.  This can be handled by setting the bit just off
00289   // the top of the original type.
00290   APInt TopBit(NVT.getSizeInBits(), 0);
00291   TopBit.set(OVT.getSizeInBits());
00292   Op = DAG.getNode(ISD::OR, dl, NVT, Op, DAG.getConstant(TopBit, NVT));
00293   return DAG.getNode(ISD::CTTZ, dl, NVT, Op);
00294 }
00295 
00296 SDValue DAGTypeLegalizer::PromoteIntRes_EXTRACT_VECTOR_ELT(SDNode *N) {
00297   DebugLoc dl = N->getDebugLoc();
00298   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00299   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, NVT, N->getOperand(0),
00300                      N->getOperand(1));
00301 }
00302 
00303 SDValue DAGTypeLegalizer::PromoteIntRes_FP_TO_XINT(SDNode *N) {
00304   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00305   unsigned NewOpc = N->getOpcode();
00306   DebugLoc dl = N->getDebugLoc();
00307 
00308   // If we're promoting a UINT to a larger size and the larger FP_TO_UINT is
00309   // not Legal, check to see if we can use FP_TO_SINT instead.  (If both UINT
00310   // and SINT conversions are Custom, there is no way to tell which is preferable.
00311   // We choose SINT because that's the right thing on PPC.)
00312   if (N->getOpcode() == ISD::FP_TO_UINT &&
00313       !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
00314       TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NVT))
00315     NewOpc = ISD::FP_TO_SINT;
00316 
00317   SDValue Res = DAG.getNode(NewOpc, dl, NVT, N->getOperand(0));
00318 
00319   // Assert that the converted value fits in the original type.  If it doesn't
00320   // (eg: because the value being converted is too big), then the result of the
00321   // original operation was undefined anyway, so the assert is still correct.
00322   return DAG.getNode(N->getOpcode() == ISD::FP_TO_UINT ?
00323                      ISD::AssertZext : ISD::AssertSext, dl,
00324                      NVT, Res, DAG.getValueType(N->getValueType(0)));
00325 }
00326 
00327 SDValue DAGTypeLegalizer::PromoteIntRes_INT_EXTEND(SDNode *N) {
00328   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00329   DebugLoc dl = N->getDebugLoc();
00330 
00331   if (getTypeAction(N->getOperand(0).getValueType()) == PromoteInteger) {
00332     SDValue Res = GetPromotedInteger(N->getOperand(0));
00333     assert(Res.getValueType().bitsLE(NVT) && "Extension doesn't make sense!");
00334 
00335     // If the result and operand types are the same after promotion, simplify
00336     // to an in-register extension.
00337     if (NVT == Res.getValueType()) {
00338       // The high bits are not guaranteed to be anything.  Insert an extend.
00339       if (N->getOpcode() == ISD::SIGN_EXTEND)
00340         return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NVT, Res,
00341                            DAG.getValueType(N->getOperand(0).getValueType()));
00342       if (N->getOpcode() == ISD::ZERO_EXTEND)
00343         return DAG.getZeroExtendInReg(Res, dl, N->getOperand(0).getValueType());
00344       assert(N->getOpcode() == ISD::ANY_EXTEND && "Unknown integer extension!");
00345       return Res;
00346     }
00347   }
00348 
00349   // Otherwise, just extend the original operand all the way to the larger type.
00350   return DAG.getNode(N->getOpcode(), dl, NVT, N->getOperand(0));
00351 }
00352 
00353 SDValue DAGTypeLegalizer::PromoteIntRes_LOAD(LoadSDNode *N) {
00354   assert(ISD::isUNINDEXEDLoad(N) && "Indexed load during type legalization!");
00355   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00356   ISD::LoadExtType ExtType =
00357     ISD::isNON_EXTLoad(N) ? ISD::EXTLOAD : N->getExtensionType();
00358   DebugLoc dl = N->getDebugLoc();
00359   SDValue Res = DAG.getExtLoad(ExtType, dl, NVT, N->getChain(), N->getBasePtr(),
00360                                N->getSrcValue(), N->getSrcValueOffset(),
00361                                N->getMemoryVT(), N->isVolatile(),
00362                                N->getAlignment());
00363 
00364   // Legalized the chain result - switch anything that used the old chain to
00365   // use the new one.
00366   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
00367   return Res;
00368 }
00369 
00370 /// Promote the overflow flag of an overflowing arithmetic node.
00371 SDValue DAGTypeLegalizer::PromoteIntRes_Overflow(SDNode *N) {
00372   // Simply change the return type of the boolean result.
00373   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(1));
00374   EVT ValueVTs[] = { N->getValueType(0), NVT };
00375   SDValue Ops[] = { N->getOperand(0), N->getOperand(1) };
00376   SDValue Res = DAG.getNode(N->getOpcode(), N->getDebugLoc(),
00377                             DAG.getVTList(ValueVTs, 2), Ops, 2);
00378 
00379   // Modified the sum result - switch anything that used the old sum to use
00380   // the new one.
00381   ReplaceValueWith(SDValue(N, 0), Res);
00382 
00383   return SDValue(Res.getNode(), 1);
00384 }
00385 
00386 SDValue DAGTypeLegalizer::PromoteIntRes_SADDSUBO(SDNode *N, unsigned ResNo) {
00387   if (ResNo == 1)
00388     return PromoteIntRes_Overflow(N);
00389 
00390   // The operation overflowed iff the result in the larger type is not the
00391   // sign extension of its truncation to the original type.
00392   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
00393   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
00394   EVT OVT = N->getOperand(0).getValueType();
00395   EVT NVT = LHS.getValueType();
00396   DebugLoc dl = N->getDebugLoc();
00397 
00398   // Do the arithmetic in the larger type.
00399   unsigned Opcode = N->getOpcode() == ISD::SADDO ? ISD::ADD : ISD::SUB;
00400   SDValue Res = DAG.getNode(Opcode, dl, NVT, LHS, RHS);
00401 
00402   // Calculate the overflow flag: sign extend the arithmetic result from
00403   // the original type.
00404   SDValue Ofl = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NVT, Res,
00405                             DAG.getValueType(OVT));
00406   // Overflowed if and only if this is not equal to Res.
00407   Ofl = DAG.getSetCC(dl, N->getValueType(1), Ofl, Res, ISD::SETNE);
00408 
00409   // Use the calculated overflow everywhere.
00410   ReplaceValueWith(SDValue(N, 1), Ofl);
00411 
00412   return Res;
00413 }
00414 
00415 SDValue DAGTypeLegalizer::PromoteIntRes_SDIV(SDNode *N) {
00416   // Sign extend the input.
00417   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
00418   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
00419   return DAG.getNode(N->getOpcode(), N->getDebugLoc(),
00420                      LHS.getValueType(), LHS, RHS);
00421 }
00422 
00423 SDValue DAGTypeLegalizer::PromoteIntRes_SELECT(SDNode *N) {
00424   SDValue LHS = GetPromotedInteger(N->getOperand(1));
00425   SDValue RHS = GetPromotedInteger(N->getOperand(2));
00426   return DAG.getNode(ISD::SELECT, N->getDebugLoc(),
00427                      LHS.getValueType(), N->getOperand(0),LHS,RHS);
00428 }
00429 
00430 SDValue DAGTypeLegalizer::PromoteIntRes_SELECT_CC(SDNode *N) {
00431   SDValue LHS = GetPromotedInteger(N->getOperand(2));
00432   SDValue RHS = GetPromotedInteger(N->getOperand(3));
00433   return DAG.getNode(ISD::SELECT_CC, N->getDebugLoc(),
00434                      LHS.getValueType(), N->getOperand(0),
00435                      N->getOperand(1), LHS, RHS, N->getOperand(4));
00436 }
00437 
00438 SDValue DAGTypeLegalizer::PromoteIntRes_SETCC(SDNode *N) {
00439   EVT SVT = TLI.getSetCCResultType(N->getOperand(0).getValueType());
00440   assert(isTypeLegal(SVT) && "Illegal SetCC type!");
00441   DebugLoc dl = N->getDebugLoc();
00442 
00443   // Get the SETCC result using the canonical SETCC type.
00444   SDValue SetCC = DAG.getNode(ISD::SETCC, dl, SVT, N->getOperand(0),
00445                               N->getOperand(1), N->getOperand(2));
00446 
00447   // Convert to the expected type.
00448   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00449   assert(NVT.bitsLE(SVT) && "Integer type overpromoted?");
00450   return DAG.getNode(ISD::TRUNCATE, dl, NVT, SetCC);
00451 }
00452 
00453 SDValue DAGTypeLegalizer::PromoteIntRes_SHL(SDNode *N) {
00454   return DAG.getNode(ISD::SHL, N->getDebugLoc(),
00455                      TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0)),
00456                      GetPromotedInteger(N->getOperand(0)), N->getOperand(1));
00457 }
00458 
00459 SDValue DAGTypeLegalizer::PromoteIntRes_SIGN_EXTEND_INREG(SDNode *N) {
00460   SDValue Op = GetPromotedInteger(N->getOperand(0));
00461   return DAG.getNode(ISD::SIGN_EXTEND_INREG, N->getDebugLoc(),
00462                      Op.getValueType(), Op, N->getOperand(1));
00463 }
00464 
00465 SDValue DAGTypeLegalizer::PromoteIntRes_SimpleIntBinOp(SDNode *N) {
00466   // The input may have strange things in the top bits of the registers, but
00467   // these operations don't care.  They may have weird bits going out, but
00468   // that too is okay if they are integer operations.
00469   SDValue LHS = GetPromotedInteger(N->getOperand(0));
00470   SDValue RHS = GetPromotedInteger(N->getOperand(1));
00471   return DAG.getNode(N->getOpcode(), N->getDebugLoc(),
00472                     LHS.getValueType(), LHS, RHS);
00473 }
00474 
00475 SDValue DAGTypeLegalizer::PromoteIntRes_SRA(SDNode *N) {
00476   // The input value must be properly sign extended.
00477   SDValue Res = SExtPromotedInteger(N->getOperand(0));
00478   return DAG.getNode(ISD::SRA, N->getDebugLoc(),
00479                      Res.getValueType(), Res, N->getOperand(1));
00480 }
00481 
00482 SDValue DAGTypeLegalizer::PromoteIntRes_SRL(SDNode *N) {
00483   // The input value must be properly zero extended.
00484   EVT VT = N->getValueType(0);
00485   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
00486   SDValue Res = ZExtPromotedInteger(N->getOperand(0));
00487   return DAG.getNode(ISD::SRL, N->getDebugLoc(), NVT, Res, N->getOperand(1));
00488 }
00489 
00490 SDValue DAGTypeLegalizer::PromoteIntRes_TRUNCATE(SDNode *N) {
00491   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00492   SDValue Res;
00493 
00494   switch (getTypeAction(N->getOperand(0).getValueType())) {
00495   default: llvm_unreachable("Unknown type action!");
00496   case Legal:
00497   case ExpandInteger:
00498     Res = N->getOperand(0);
00499     break;
00500   case PromoteInteger:
00501     Res = GetPromotedInteger(N->getOperand(0));
00502     break;
00503   }
00504 
00505   // Truncate to NVT instead of VT
00506   return DAG.getNode(ISD::TRUNCATE, N->getDebugLoc(), NVT, Res);
00507 }
00508 
00509 SDValue DAGTypeLegalizer::PromoteIntRes_UADDSUBO(SDNode *N, unsigned ResNo) {
00510   if (ResNo == 1)
00511     return PromoteIntRes_Overflow(N);
00512 
00513   // The operation overflowed iff the result in the larger type is not the
00514   // zero extension of its truncation to the original type.
00515   SDValue LHS = ZExtPromotedInteger(N->getOperand(0));
00516   SDValue RHS = ZExtPromotedInteger(N->getOperand(1));
00517   EVT OVT = N->getOperand(0).getValueType();
00518   EVT NVT = LHS.getValueType();
00519   DebugLoc dl = N->getDebugLoc();
00520 
00521   // Do the arithmetic in the larger type.
00522   unsigned Opcode = N->getOpcode() == ISD::UADDO ? ISD::ADD : ISD::SUB;
00523   SDValue Res = DAG.getNode(Opcode, dl, NVT, LHS, RHS);
00524 
00525   // Calculate the overflow flag: zero extend the arithmetic result from
00526   // the original type.
00527   SDValue Ofl = DAG.getZeroExtendInReg(Res, dl, OVT);
00528   // Overflowed if and only if this is not equal to Res.
00529   Ofl = DAG.getSetCC(dl, N->getValueType(1), Ofl, Res, ISD::SETNE);
00530 
00531   // Use the calculated overflow everywhere.
00532   ReplaceValueWith(SDValue(N, 1), Ofl);
00533 
00534   return Res;
00535 }
00536 
00537 SDValue DAGTypeLegalizer::PromoteIntRes_UDIV(SDNode *N) {
00538   // Zero extend the input.
00539   SDValue LHS = ZExtPromotedInteger(N->getOperand(0));
00540   SDValue RHS = ZExtPromotedInteger(N->getOperand(1));
00541   return DAG.getNode(N->getOpcode(), N->getDebugLoc(),
00542                      LHS.getValueType(), LHS, RHS);
00543 }
00544 
00545 SDValue DAGTypeLegalizer::PromoteIntRes_UNDEF(SDNode *N) {
00546   return DAG.getUNDEF(TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0)));
00547 }
00548 
00549 SDValue DAGTypeLegalizer::PromoteIntRes_VAARG(SDNode *N) {
00550   SDValue Chain = N->getOperand(0); // Get the chain.
00551   SDValue Ptr = N->getOperand(1); // Get the pointer.
00552   EVT VT = N->getValueType(0);
00553   DebugLoc dl = N->getDebugLoc();
00554 
00555   EVT RegVT = TLI.getRegisterType(*DAG.getContext(), VT);
00556   unsigned NumRegs = TLI.getNumRegisters(*DAG.getContext(), VT);
00557   // The argument is passed as NumRegs registers of type RegVT.
00558 
00559   SmallVector<SDValue, 8> Parts(NumRegs);
00560   for (unsigned i = 0; i < NumRegs; ++i) {
00561     Parts[i] = DAG.getVAArg(RegVT, dl, Chain, Ptr, N->getOperand(2));
00562     Chain = Parts[i].getValue(1);
00563   }
00564 
00565   // Handle endianness of the load.
00566   if (TLI.isBigEndian())
00567     std::reverse(Parts.begin(), Parts.end());
00568 
00569   // Assemble the parts in the promoted type.
00570   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
00571   SDValue Res = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Parts[0]);
00572   for (unsigned i = 1; i < NumRegs; ++i) {
00573     SDValue Part = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Parts[i]);
00574     // Shift it to the right position and "or" it in.
00575     Part = DAG.getNode(ISD::SHL, dl, NVT, Part,
00576                        DAG.getConstant(i * RegVT.getSizeInBits(),
00577                                        TLI.getPointerTy()));
00578     Res = DAG.getNode(ISD::OR, dl, NVT, Res, Part);
00579   }
00580 
00581   // Modified the chain result - switch anything that used the old chain to
00582   // use the new one.
00583   ReplaceValueWith(SDValue(N, 1), Chain);
00584 
00585   return Res;
00586 }
00587 
00588 SDValue DAGTypeLegalizer::PromoteIntRes_XMULO(SDNode *N, unsigned ResNo) {
00589   assert(ResNo == 1 && "Only boolean result promotion currently supported!");
00590   return PromoteIntRes_Overflow(N);
00591 }
00592 
00593 //===----------------------------------------------------------------------===//
00594 //  Integer Operand Promotion
00595 //===----------------------------------------------------------------------===//
00596 
00597 /// PromoteIntegerOperand - This method is called when the specified operand of
00598 /// the specified node is found to need promotion.  At this point, all of the
00599 /// result types of the node are known to be legal, but other operands of the
00600 /// node may need promotion or expansion as well as the specified one.
00601 bool DAGTypeLegalizer::PromoteIntegerOperand(SDNode *N, unsigned OpNo) {
00602   DEBUG(errs() << "Promote integer operand: "; N->dump(&DAG); errs() << "\n");
00603   SDValue Res = SDValue();
00604 
00605   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
00606     return false;
00607 
00608   switch (N->getOpcode()) {
00609     default:
00610   #ifndef NDEBUG
00611     errs() << "PromoteIntegerOperand Op #" << OpNo << ": ";
00612     N->dump(&DAG); errs() << "\n";
00613   #endif
00614     llvm_unreachable("Do not know how to promote this operator's operand!");
00615 
00616   case ISD::ANY_EXTEND:   Res = PromoteIntOp_ANY_EXTEND(N); break;
00617   case ISD::BIT_CONVERT:  Res = PromoteIntOp_BIT_CONVERT(N); break;
00618   case ISD::BR_CC:        Res = PromoteIntOp_BR_CC(N, OpNo); break;
00619   case ISD::BRCOND:       Res = PromoteIntOp_BRCOND(N, OpNo); break;
00620   case ISD::BUILD_PAIR:   Res = PromoteIntOp_BUILD_PAIR(N); break;
00621   case ISD::BUILD_VECTOR: Res = PromoteIntOp_BUILD_VECTOR(N); break;
00622   case ISD::CONVERT_RNDSAT:
00623                           Res = PromoteIntOp_CONVERT_RNDSAT(N); break;
00624   case ISD::INSERT_VECTOR_ELT:
00625                           Res = PromoteIntOp_INSERT_VECTOR_ELT(N, OpNo);break;
00626   case ISD::MEMBARRIER:   Res = PromoteIntOp_MEMBARRIER(N); break;
00627   case ISD::SCALAR_TO_VECTOR:
00628                           Res = PromoteIntOp_SCALAR_TO_VECTOR(N); break;
00629   case ISD::SELECT:       Res = PromoteIntOp_SELECT(N, OpNo); break;
00630   case ISD::SELECT_CC:    Res = PromoteIntOp_SELECT_CC(N, OpNo); break;
00631   case ISD::SETCC:        Res = PromoteIntOp_SETCC(N, OpNo); break;
00632   case ISD::SIGN_EXTEND:  Res = PromoteIntOp_SIGN_EXTEND(N); break;
00633   case ISD::SINT_TO_FP:   Res = PromoteIntOp_SINT_TO_FP(N); break;
00634   case ISD::STORE:        Res = PromoteIntOp_STORE(cast<StoreSDNode>(N),
00635                                                    OpNo); break;
00636   case ISD::TRUNCATE:     Res = PromoteIntOp_TRUNCATE(N); break;
00637   case ISD::UINT_TO_FP:   Res = PromoteIntOp_UINT_TO_FP(N); break;
00638   case ISD::ZERO_EXTEND:  Res = PromoteIntOp_ZERO_EXTEND(N); break;
00639 
00640   case ISD::SHL:
00641   case ISD::SRA:
00642   case ISD::SRL:
00643   case ISD::ROTL:
00644   case ISD::ROTR: Res = PromoteIntOp_Shift(N); break;
00645   }
00646 
00647   // If the result is null, the sub-method took care of registering results etc.
00648   if (!Res.getNode()) return false;
00649 
00650   // If the result is N, the sub-method updated N in place.  Tell the legalizer
00651   // core about this.
00652   if (Res.getNode() == N)
00653     return true;
00654 
00655   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
00656          "Invalid operand expansion");
00657 
00658   ReplaceValueWith(SDValue(N, 0), Res);
00659   return false;
00660 }
00661 
00662 /// PromoteSetCCOperands - Promote the operands of a comparison.  This code is
00663 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
00664 void DAGTypeLegalizer::PromoteSetCCOperands(SDValue &NewLHS,SDValue &NewRHS,
00665                                             ISD::CondCode CCCode) {
00666   // We have to insert explicit sign or zero extends.  Note that we could
00667   // insert sign extends for ALL conditions, but zero extend is cheaper on
00668   // many machines (an AND instead of two shifts), so prefer it.
00669   switch (CCCode) {
00670   default: llvm_unreachable("Unknown integer comparison!");
00671   case ISD::SETEQ:
00672   case ISD::SETNE:
00673   case ISD::SETUGE:
00674   case ISD::SETUGT:
00675   case ISD::SETULE:
00676   case ISD::SETULT:
00677     // ALL of these operations will work if we either sign or zero extend
00678     // the operands (including the unsigned comparisons!).  Zero extend is
00679     // usually a simpler/cheaper operation, so prefer it.
00680     NewLHS = ZExtPromotedInteger(NewLHS);
00681     NewRHS = ZExtPromotedInteger(NewRHS);
00682     break;
00683   case ISD::SETGE:
00684   case ISD::SETGT:
00685   case ISD::SETLT:
00686   case ISD::SETLE:
00687     NewLHS = SExtPromotedInteger(NewLHS);
00688     NewRHS = SExtPromotedInteger(NewRHS);
00689     break;
00690   }
00691 }
00692 
00693 SDValue DAGTypeLegalizer::PromoteIntOp_ANY_EXTEND(SDNode *N) {
00694   SDValue Op = GetPromotedInteger(N->getOperand(0));
00695   return DAG.getNode(ISD::ANY_EXTEND, N->getDebugLoc(), N->getValueType(0), Op);
00696 }
00697 
00698 SDValue DAGTypeLegalizer::PromoteIntOp_BIT_CONVERT(SDNode *N) {
00699   // This should only occur in unusual situations like bitcasting to an
00700   // x86_fp80, so just turn it into a store+load
00701   return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
00702 }
00703 
00704 SDValue DAGTypeLegalizer::PromoteIntOp_BR_CC(SDNode *N, unsigned OpNo) {
00705   assert(OpNo == 2 && "Don't know how to promote this operand!");
00706 
00707   SDValue LHS = N->getOperand(2);
00708   SDValue RHS = N->getOperand(3);
00709   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(1))->get());
00710 
00711   // The chain (Op#0), CC (#1) and basic block destination (Op#4) are always
00712   // legal types.
00713   return DAG.UpdateNodeOperands(SDValue(N, 0), N->getOperand(0),
00714                                 N->getOperand(1), LHS, RHS, N->getOperand(4));
00715 }
00716 
00717 SDValue DAGTypeLegalizer::PromoteIntOp_BRCOND(SDNode *N, unsigned OpNo) {
00718   assert(OpNo == 1 && "only know how to promote condition");
00719 
00720   // Promote all the way up to the canonical SetCC type.
00721   EVT SVT = TLI.getSetCCResultType(MVT::Other);
00722   SDValue Cond = PromoteTargetBoolean(N->getOperand(1), SVT);
00723 
00724   // The chain (Op#0) and basic block destination (Op#2) are always legal types.
00725   return DAG.UpdateNodeOperands(SDValue(N, 0), N->getOperand(0), Cond,
00726                                 N->getOperand(2));
00727 }
00728 
00729 SDValue DAGTypeLegalizer::PromoteIntOp_BUILD_PAIR(SDNode *N) {
00730   // Since the result type is legal, the operands must promote to it.
00731   EVT OVT = N->getOperand(0).getValueType();
00732   SDValue Lo = ZExtPromotedInteger(N->getOperand(0));
00733   SDValue Hi = GetPromotedInteger(N->getOperand(1));
00734   assert(Lo.getValueType() == N->getValueType(0) && "Operand over promoted?");
00735   DebugLoc dl = N->getDebugLoc();
00736 
00737   Hi = DAG.getNode(ISD::SHL, dl, N->getValueType(0), Hi,
00738                    DAG.getConstant(OVT.getSizeInBits(), TLI.getPointerTy()));
00739   return DAG.getNode(ISD::OR, dl, N->getValueType(0), Lo, Hi);
00740 }
00741 
00742 SDValue DAGTypeLegalizer::PromoteIntOp_BUILD_VECTOR(SDNode *N) {
00743   // The vector type is legal but the element type is not.  This implies
00744   // that the vector is a power-of-two in length and that the element
00745   // type does not have a strange size (eg: it is not i1).
00746   EVT VecVT = N->getValueType(0);
00747   unsigned NumElts = VecVT.getVectorNumElements();
00748   assert(!(NumElts & 1) && "Legal vector of one illegal element?");
00749 
00750   // Promote the inserted value.  The type does not need to match the
00751   // vector element type.  Check that any extra bits introduced will be
00752   // truncated away.
00753   assert(N->getOperand(0).getValueType().getSizeInBits() >=
00754          N->getValueType(0).getVectorElementType().getSizeInBits() &&
00755          "Type of inserted value narrower than vector element type!");
00756 
00757   SmallVector<SDValue, 16> NewOps;
00758   for (unsigned i = 0; i < NumElts; ++i)
00759     NewOps.push_back(GetPromotedInteger(N->getOperand(i)));
00760 
00761   return DAG.UpdateNodeOperands(SDValue(N, 0), &NewOps[0], NumElts);
00762 }
00763 
00764 SDValue DAGTypeLegalizer::PromoteIntOp_CONVERT_RNDSAT(SDNode *N) {
00765   ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
00766   assert ((CvtCode == ISD::CVT_SS || CvtCode == ISD::CVT_SU ||
00767            CvtCode == ISD::CVT_US || CvtCode == ISD::CVT_UU ||
00768            CvtCode == ISD::CVT_FS || CvtCode == ISD::CVT_FU) &&
00769            "can only promote integer arguments");
00770   SDValue InOp = GetPromotedInteger(N->getOperand(0));
00771   return DAG.getConvertRndSat(N->getValueType(0), N->getDebugLoc(), InOp,
00772                               N->getOperand(1), N->getOperand(2),
00773                               N->getOperand(3), N->getOperand(4), CvtCode);
00774 }
00775 
00776 SDValue DAGTypeLegalizer::PromoteIntOp_INSERT_VECTOR_ELT(SDNode *N,
00777                                                          unsigned OpNo) {
00778   if (OpNo == 1) {
00779     // Promote the inserted value.  This is valid because the type does not
00780     // have to match the vector element type.
00781 
00782     // Check that any extra bits introduced will be truncated away.
00783     assert(N->getOperand(1).getValueType().getSizeInBits() >=
00784            N->getValueType(0).getVectorElementType().getSizeInBits() &&
00785            "Type of inserted value narrower than vector element type!");
00786     return DAG.UpdateNodeOperands(SDValue(N, 0), N->getOperand(0),
00787                                   GetPromotedInteger(N->getOperand(1)),
00788                                   N->getOperand(2));
00789   }
00790 
00791   assert(OpNo == 2 && "Different operand and result vector types?");
00792 
00793   // Promote the index.
00794   SDValue Idx = ZExtPromotedInteger(N->getOperand(2));
00795   return DAG.UpdateNodeOperands(SDValue(N, 0), N->getOperand(0),
00796                                 N->getOperand(1), Idx);
00797 }
00798 
00799 SDValue DAGTypeLegalizer::PromoteIntOp_MEMBARRIER(SDNode *N) {
00800   SDValue NewOps[6];
00801   DebugLoc dl = N->getDebugLoc();
00802   NewOps[0] = N->getOperand(0);
00803   for (unsigned i = 1; i < array_lengthof(NewOps); ++i) {
00804     SDValue Flag = GetPromotedInteger(N->getOperand(i));
00805     NewOps[i] = DAG.getZeroExtendInReg(Flag, dl, MVT::i1);
00806   }
00807   return DAG.UpdateNodeOperands(SDValue (N, 0), NewOps,
00808                                 array_lengthof(NewOps));
00809 }
00810 
00811 SDValue DAGTypeLegalizer::PromoteIntOp_SCALAR_TO_VECTOR(SDNode *N) {
00812   // Integer SCALAR_TO_VECTOR operands are implicitly truncated, so just promote
00813   // the operand in place.
00814   return DAG.UpdateNodeOperands(SDValue(N, 0),
00815                                 GetPromotedInteger(N->getOperand(0)));
00816 }
00817 
00818 SDValue DAGTypeLegalizer::PromoteIntOp_SELECT(SDNode *N, unsigned OpNo) {
00819   assert(OpNo == 0 && "Only know how to promote condition");
00820 
00821   // Promote all the way up to the canonical SetCC type.
00822   EVT SVT = TLI.getSetCCResultType(N->getOperand(1).getValueType());
00823   SDValue Cond = PromoteTargetBoolean(N->getOperand(0), SVT);
00824 
00825   return DAG.UpdateNodeOperands(SDValue(N, 0), Cond,
00826                                 N->getOperand(1), N->getOperand(2));
00827 }
00828 
00829 SDValue DAGTypeLegalizer::PromoteIntOp_SELECT_CC(SDNode *N, unsigned OpNo) {
00830   assert(OpNo == 0 && "Don't know how to promote this operand!");
00831 
00832   SDValue LHS = N->getOperand(0);
00833   SDValue RHS = N->getOperand(1);
00834   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(4))->get());
00835 
00836   // The CC (#4) and the possible return values (#2 and #3) have legal types.
00837   return DAG.UpdateNodeOperands(SDValue(N, 0), LHS, RHS, N->getOperand(2),
00838                                 N->getOperand(3), N->getOperand(4));
00839 }
00840 
00841 SDValue DAGTypeLegalizer::PromoteIntOp_SETCC(SDNode *N, unsigned OpNo) {
00842   assert(OpNo == 0 && "Don't know how to promote this operand!");
00843 
00844   SDValue LHS = N->getOperand(0);
00845   SDValue RHS = N->getOperand(1);
00846   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(2))->get());
00847 
00848   // The CC (#2) is always legal.
00849   return DAG.UpdateNodeOperands(SDValue(N, 0), LHS, RHS, N->getOperand(2));
00850 }
00851 
00852 SDValue DAGTypeLegalizer::PromoteIntOp_Shift(SDNode *N) {
00853   return DAG.UpdateNodeOperands(SDValue(N, 0), N->getOperand(0),
00854                                 ZExtPromotedInteger(N->getOperand(1)));
00855 }
00856 
00857 SDValue DAGTypeLegalizer::PromoteIntOp_SIGN_EXTEND(SDNode *N) {
00858   SDValue Op = GetPromotedInteger(N->getOperand(0));
00859   DebugLoc dl = N->getDebugLoc();
00860   Op = DAG.getNode(ISD::ANY_EXTEND, dl, N->getValueType(0), Op);
00861   return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Op.getValueType(),
00862                      Op, DAG.getValueType(N->getOperand(0).getValueType()));
00863 }
00864 
00865 SDValue DAGTypeLegalizer::PromoteIntOp_SINT_TO_FP(SDNode *N) {
00866   return DAG.UpdateNodeOperands(SDValue(N, 0),
00867                                 SExtPromotedInteger(N->getOperand(0)));
00868 }
00869 
00870 SDValue DAGTypeLegalizer::PromoteIntOp_STORE(StoreSDNode *N, unsigned OpNo){
00871   assert(ISD::isUNINDEXEDStore(N) && "Indexed store during type legalization!");
00872   SDValue Ch = N->getChain(), Ptr = N->getBasePtr();
00873   int SVOffset = N->getSrcValueOffset();
00874   unsigned Alignment = N->getAlignment();
00875   bool isVolatile = N->isVolatile();
00876   DebugLoc dl = N->getDebugLoc();
00877 
00878   SDValue Val = GetPromotedInteger(N->getValue());  // Get promoted value.
00879 
00880   // Truncate the value and store the result.
00881   return DAG.getTruncStore(Ch, dl, Val, Ptr, N->getSrcValue(),
00882                            SVOffset, N->getMemoryVT(),
00883                            isVolatile, Alignment);
00884 }
00885 
00886 SDValue DAGTypeLegalizer::PromoteIntOp_TRUNCATE(SDNode *N) {
00887   SDValue Op = GetPromotedInteger(N->getOperand(0));
00888   return DAG.getNode(ISD::TRUNCATE, N->getDebugLoc(), N->getValueType(0), Op);
00889 }
00890 
00891 SDValue DAGTypeLegalizer::PromoteIntOp_UINT_TO_FP(SDNode *N) {
00892   return DAG.UpdateNodeOperands(SDValue(N, 0),
00893                                 ZExtPromotedInteger(N->getOperand(0)));
00894 }
00895 
00896 SDValue DAGTypeLegalizer::PromoteIntOp_ZERO_EXTEND(SDNode *N) {
00897   DebugLoc dl = N->getDebugLoc();
00898   SDValue Op = GetPromotedInteger(N->getOperand(0));
00899   Op = DAG.getNode(ISD::ANY_EXTEND, dl, N->getValueType(0), Op);
00900   return DAG.getZeroExtendInReg(Op, dl, N->getOperand(0).getValueType());
00901 }
00902 
00903 
00904 //===----------------------------------------------------------------------===//
00905 //  Integer Result Expansion
00906 //===----------------------------------------------------------------------===//
00907 
00908 /// ExpandIntegerResult - This method is called when the specified result of the
00909 /// specified node is found to need expansion.  At this point, the node may also
00910 /// have invalid operands or may have other results that need promotion, we just
00911 /// know that (at least) one result needs expansion.
00912 void DAGTypeLegalizer::ExpandIntegerResult(SDNode *N, unsigned ResNo) {
00913   DEBUG(errs() << "Expand integer result: "; N->dump(&DAG); errs() << "\n");
00914   SDValue Lo, Hi;
00915   Lo = Hi = SDValue();
00916 
00917   // See if the target wants to custom expand this node.
00918   if (CustomLowerNode(N, N->getValueType(ResNo), true))
00919     return;
00920 
00921   switch (N->getOpcode()) {
00922   default:
00923 #ifndef NDEBUG
00924     errs() << "ExpandIntegerResult #" << ResNo << ": ";
00925     N->dump(&DAG); errs() << "\n";
00926 #endif
00927     llvm_unreachable("Do not know how to expand the result of this operator!");
00928 
00929   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, Lo, Hi); break;
00930   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
00931   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
00932   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
00933 
00934   case ISD::BIT_CONVERT:        ExpandRes_BIT_CONVERT(N, Lo, Hi); break;
00935   case ISD::BUILD_PAIR:         ExpandRes_BUILD_PAIR(N, Lo, Hi); break;
00936   case ISD::EXTRACT_ELEMENT:    ExpandRes_EXTRACT_ELEMENT(N, Lo, Hi); break;
00937   case ISD::EXTRACT_VECTOR_ELT: ExpandRes_EXTRACT_VECTOR_ELT(N, Lo, Hi); break;
00938   case ISD::VAARG:              ExpandRes_VAARG(N, Lo, Hi); break;
00939 
00940   case ISD::ANY_EXTEND:  ExpandIntRes_ANY_EXTEND(N, Lo, Hi); break;
00941   case ISD::AssertSext:  ExpandIntRes_AssertSext(N, Lo, Hi); break;
00942   case ISD::AssertZext:  ExpandIntRes_AssertZext(N, Lo, Hi); break;
00943   case ISD::BSWAP:       ExpandIntRes_BSWAP(N, Lo, Hi); break;
00944   case ISD::Constant:    ExpandIntRes_Constant(N, Lo, Hi); break;
00945   case ISD::CTLZ:        ExpandIntRes_CTLZ(N, Lo, Hi); break;
00946   case ISD::CTPOP:       ExpandIntRes_CTPOP(N, Lo, Hi); break;
00947   case ISD::CTTZ:        ExpandIntRes_CTTZ(N, Lo, Hi); break;
00948   case ISD::FP_TO_SINT:  ExpandIntRes_FP_TO_SINT(N, Lo, Hi); break;
00949   case ISD::FP_TO_UINT:  ExpandIntRes_FP_TO_UINT(N, Lo, Hi); break;
00950   case ISD::LOAD:        ExpandIntRes_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
00951   case ISD::MUL:         ExpandIntRes_MUL(N, Lo, Hi); break;
00952   case ISD::SDIV:        ExpandIntRes_SDIV(N, Lo, Hi); break;
00953   case ISD::SIGN_EXTEND: ExpandIntRes_SIGN_EXTEND(N, Lo, Hi); break;
00954   case ISD::SIGN_EXTEND_INREG: ExpandIntRes_SIGN_EXTEND_INREG(N, Lo, Hi); break;
00955   case ISD::SREM:        ExpandIntRes_SREM(N, Lo, Hi); break;
00956   case ISD::TRUNCATE:    ExpandIntRes_TRUNCATE(N, Lo, Hi); break;
00957   case ISD::UDIV:        ExpandIntRes_UDIV(N, Lo, Hi); break;
00958   case ISD::UREM:        ExpandIntRes_UREM(N, Lo, Hi); break;
00959   case ISD::ZERO_EXTEND: ExpandIntRes_ZERO_EXTEND(N, Lo, Hi); break;
00960 
00961   case ISD::AND:
00962   case ISD::OR:
00963   case ISD::XOR: ExpandIntRes_Logical(N, Lo, Hi); break;
00964 
00965   case ISD::ADD:
00966   case ISD::SUB: ExpandIntRes_ADDSUB(N, Lo, Hi); break;
00967 
00968   case ISD::ADDC:
00969   case ISD::SUBC: ExpandIntRes_ADDSUBC(N, Lo, Hi); break;
00970 
00971   case ISD::ADDE:
00972   case ISD::SUBE: ExpandIntRes_ADDSUBE(N, Lo, Hi); break;
00973 
00974   case ISD::SHL:
00975   case ISD::SRA:
00976   case ISD::SRL: ExpandIntRes_Shift(N, Lo, Hi); break;
00977   }
00978 
00979   // If Lo/Hi is null, the sub-method took care of registering results etc.
00980   if (Lo.getNode())
00981     SetExpandedInteger(SDValue(N, ResNo), Lo, Hi);
00982 }
00983 
00984 /// ExpandShiftByConstant - N is a shift by a value that needs to be expanded,
00985 /// and the shift amount is a constant 'Amt'.  Expand the operation.
00986 void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, unsigned Amt,
00987                                              SDValue &Lo, SDValue &Hi) {
00988   DebugLoc dl = N->getDebugLoc();
00989   // Expand the incoming operand to be shifted, so that we have its parts
00990   SDValue InL, InH;
00991   GetExpandedInteger(N->getOperand(0), InL, InH);
00992 
00993   EVT NVT = InL.getValueType();
00994   unsigned VTBits = N->getValueType(0).getSizeInBits();
00995   unsigned NVTBits = NVT.getSizeInBits();
00996   EVT ShTy = N->getOperand(1).getValueType();
00997 
00998   if (N->getOpcode() == ISD::SHL) {
00999     if (Amt > VTBits) {
01000       Lo = Hi = DAG.getConstant(0, NVT);
01001     } else if (Amt > NVTBits) {
01002       Lo = DAG.getConstant(0, NVT);
01003       Hi = DAG.getNode(ISD::SHL, dl,
01004                        NVT, InL, DAG.getConstant(Amt-NVTBits,ShTy));
01005     } else if (Amt == NVTBits) {
01006       Lo = DAG.getConstant(0, NVT);
01007       Hi = InL;
01008     } else if (Amt == 1 &&
01009                TLI.isOperationLegalOrCustom(ISD::ADDC,
01010                                             TLI.getTypeToExpandTo(*DAG.getContext(), NVT))) {
01011       // Emit this X << 1 as X+X.
01012       SDVTList VTList = DAG.getVTList(NVT, MVT::Flag);
01013       SDValue LoOps[2] = { InL, InL };
01014       Lo = DAG.getNode(ISD::ADDC, dl, VTList, LoOps, 2);
01015       SDValue HiOps[3] = { InH, InH, Lo.getValue(1) };
01016       Hi = DAG.getNode(ISD::ADDE, dl, VTList, HiOps, 3);
01017     } else {
01018       Lo = DAG.getNode(ISD::SHL, dl, NVT, InL, DAG.getConstant(Amt, ShTy));
01019       Hi = DAG.getNode(ISD::OR, dl, NVT,
01020                        DAG.getNode(ISD::SHL, dl, NVT, InH,
01021                                    DAG.getConstant(Amt, ShTy)),
01022                        DAG.getNode(ISD::SRL, dl, NVT, InL,
01023                                    DAG.getConstant(NVTBits-Amt, ShTy)));
01024     }
01025     return;
01026   }
01027 
01028   if (N->getOpcode() == ISD::SRL) {
01029     if (Amt > VTBits) {
01030       Lo = DAG.getConstant(0, NVT);
01031       Hi = DAG.getConstant(0, NVT);
01032     } else if (Amt > NVTBits) {
01033       Lo = DAG.getNode(ISD::SRL, dl,
01034                        NVT, InH, DAG.getConstant(Amt-NVTBits,ShTy));
01035       Hi = DAG.getConstant(0, NVT);
01036     } else if (Amt == NVTBits) {
01037       Lo = InH;
01038       Hi = DAG.getConstant(0, NVT);
01039     } else {
01040       Lo = DAG.getNode(ISD::OR, dl, NVT,
01041                        DAG.getNode(ISD::SRL, dl, NVT, InL,
01042                                    DAG.getConstant(Amt, ShTy)),
01043                        DAG.getNode(ISD::SHL, dl, NVT, InH,
01044                                    DAG.getConstant(NVTBits-Amt, ShTy)));
01045       Hi = DAG.getNode(ISD::SRL, dl, NVT, InH, DAG.getConstant(Amt, ShTy));
01046     }
01047     return;
01048   }
01049 
01050   assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
01051   if (Amt > VTBits) {
01052     Hi = Lo = DAG.getNode(ISD::SRA, dl, NVT, InH,
01053                           DAG.getConstant(NVTBits-1, ShTy));
01054   } else if (Amt > NVTBits) {
01055     Lo = DAG.getNode(ISD::SRA, dl, NVT, InH,
01056                      DAG.getConstant(Amt-NVTBits, ShTy));
01057     Hi = DAG.getNode(ISD::SRA, dl, NVT, InH,
01058                      DAG.getConstant(NVTBits-1, ShTy));
01059   } else if (Amt == NVTBits) {
01060     Lo = InH;
01061     Hi = DAG.getNode(ISD::SRA, dl, NVT, InH,
01062                      DAG.getConstant(NVTBits-1, ShTy));
01063   } else {
01064     Lo = DAG.getNode(ISD::OR, dl, NVT,
01065                      DAG.getNode(ISD::SRL, dl, NVT, InL,
01066                                  DAG.getConstant(Amt, ShTy)),
01067                      DAG.getNode(ISD::SHL, dl, NVT, InH,
01068                                  DAG.getConstant(NVTBits-Amt, ShTy)));
01069     Hi = DAG.getNode(ISD::SRA, dl, NVT, InH, DAG.getConstant(Amt, ShTy));
01070   }
01071 }
01072 
01073 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
01074 /// this shift based on knowledge of the high bit of the shift amount.  If we
01075 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
01076 /// shift amount.
01077 bool DAGTypeLegalizer::
01078 ExpandShiftWithKnownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
01079   SDValue Amt = N->getOperand(1);
01080   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
01081   EVT ShTy = Amt.getValueType();
01082   unsigned ShBits = ShTy.getSizeInBits();
01083   unsigned NVTBits = NVT.getSizeInBits();
01084   assert(isPowerOf2_32(NVTBits) &&
01085          "Expanded integer type size not a power of two!");
01086   DebugLoc dl = N->getDebugLoc();
01087 
01088   APInt HighBitMask = APInt::getHighBitsSet(ShBits, ShBits - Log2_32(NVTBits));
01089   APInt KnownZero, KnownOne;
01090   DAG.ComputeMaskedBits(N->getOperand(1), HighBitMask, KnownZero, KnownOne);
01091 
01092   // If we don't know anything about the high bits, exit.
01093   if (((KnownZero|KnownOne) & HighBitMask) == 0)
01094     return false;
01095 
01096   // Get the incoming operand to be shifted.
01097   SDValue InL, InH;
01098   GetExpandedInteger(N->getOperand(0), InL, InH);
01099 
01100   // If we know that any of the high bits of the shift amount are one, then we
01101   // can do this as a couple of simple shifts.
01102   if (KnownOne.intersects(HighBitMask)) {
01103     // Mask out the high bit, which we know is set.
01104     Amt = DAG.getNode(ISD::AND, dl, ShTy, Amt,
01105                       DAG.getConstant(~HighBitMask, ShTy));
01106 
01107     switch (N->getOpcode()) {
01108     default: llvm_unreachable("Unknown shift");
01109     case ISD::SHL:
01110       Lo = DAG.getConstant(0, NVT);              // Low part is zero.
01111       Hi = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt); // High part from Lo part.
01112       return true;
01113     case ISD::SRL:
01114       Hi = DAG.getConstant(0, NVT);              // Hi part is zero.
01115       Lo = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt); // Lo part from Hi part.
01116       return true;
01117     case ISD::SRA:
01118       Hi = DAG.getNode(ISD::SRA, dl, NVT, InH,       // Sign extend high part.
01119                        DAG.getConstant(NVTBits-1, ShTy));
01120       Lo = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt); // Lo part from Hi part.
01121       return true;
01122     }
01123   }
01124 
01125 #if 0
01126   // FIXME: This code is broken for shifts with a zero amount!
01127   // If we know that all of the high bits of the shift amount are zero, then we
01128   // can do this as a couple of simple shifts.
01129   if ((KnownZero & HighBitMask) == HighBitMask) {
01130     // Compute 32-amt.
01131     SDValue Amt2 = DAG.getNode(ISD::SUB, ShTy,
01132                                  DAG.getConstant(NVTBits, ShTy),
01133                                  Amt);
01134     unsigned Op1, Op2;
01135     switch (N->getOpcode()) {
01136     default: llvm_unreachable("Unknown shift");
01137     case ISD::SHL:  Op1 = ISD::SHL; Op2 = ISD::SRL; break;
01138     case ISD::SRL:
01139     case ISD::SRA:  Op1 = ISD::SRL; Op2 = ISD::SHL; break;
01140     }
01141 
01142     Lo = DAG.getNode(N->getOpcode(), NVT, InL, Amt);
01143     Hi = DAG.getNode(ISD::OR, NVT,
01144                      DAG.getNode(Op1, NVT, InH, Amt),
01145                      DAG.getNode(Op2, NVT, InL, Amt2));
01146     return true;
01147   }
01148 #endif
01149 
01150   return false;
01151 }
01152 
01153 /// ExpandShiftWithUnknownAmountBit - Fully general expansion of integer shift
01154 /// of any size.
01155 bool DAGTypeLegalizer::
01156 ExpandShiftWithUnknownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
01157   SDValue Amt = N->getOperand(1);
01158   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
01159   EVT ShTy = Amt.getValueType();
01160   unsigned NVTBits = NVT.getSizeInBits();
01161   assert(isPowerOf2_32(NVTBits) &&
01162          "Expanded integer type size not a power of two!");
01163   DebugLoc dl = N->getDebugLoc();
01164 
01165   // Get the incoming operand to be shifted.
01166   SDValue InL, InH;
01167   GetExpandedInteger(N->getOperand(0), InL, InH);
01168 
01169   SDValue NVBitsNode = DAG.getConstant(NVTBits, ShTy);
01170   SDValue Amt2 = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);
01171   SDValue Cmp = DAG.getSetCC(dl, TLI.getSetCCResultType(ShTy),
01172                              Amt, NVBitsNode, ISD::SETULT);
01173 
01174   SDValue Lo1, Hi1, Lo2, Hi2;
01175   switch (N->getOpcode()) {
01176   default: llvm_unreachable("Unknown shift");
01177   case ISD::SHL:
01178     // ShAmt < NVTBits
01179     Lo1 = DAG.getConstant(0, NVT);                  // Low part is zero.
01180     Hi1 = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt); // High part from Lo part.
01181 
01182     // ShAmt >= NVTBits
01183     Lo2 = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt);
01184     Hi2 = DAG.getNode(ISD::OR, dl, NVT,
01185                       DAG.getNode(ISD::SHL, dl, NVT, InH, Amt),
01186                       DAG.getNode(ISD::SRL, dl, NVT, InL, Amt2));
01187 
01188     Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
01189     Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
01190     return true;
01191   case ISD::SRL:
01192     // ShAmt < NVTBits
01193     Hi1 = DAG.getConstant(0, NVT);                  // Hi part is zero.
01194     Lo1 = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt); // Lo part from Hi part.
01195 
01196     // ShAmt >= NVTBits
01197     Hi2 = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt);
01198     Lo2 = DAG.getNode(ISD::OR, dl, NVT,
01199                      DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
01200                      DAG.getNode(ISD::SHL, dl, NVT, InH, Amt2));
01201 
01202     Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
01203     Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
01204     return true;
01205   case ISD::SRA:
01206     // ShAmt < NVTBits
01207     Hi1 = DAG.getNode(ISD::SRA, dl, NVT, InH,       // Sign extend high part.
01208                        DAG.getConstant(NVTBits-1, ShTy));
01209     Lo1 = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt); // Lo part from Hi part.
01210 
01211     // ShAmt >= NVTBits
01212     Hi2 = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt);
01213     Lo2 = DAG.getNode(ISD::OR, dl, NVT,
01214                       DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
01215                       DAG.getNode(ISD::SHL, dl, NVT, InH, Amt2));
01216 
01217     Lo = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Lo1, Lo2);
01218     Hi = DAG.getNode(ISD::SELECT, dl, NVT, Cmp, Hi1, Hi2);
01219     return true;
01220   }
01221 
01222   return false;
01223 }
01224 
01225 void DAGTypeLegalizer::ExpandIntRes_ADDSUB(SDNode *N,
01226                                            SDValue &Lo, SDValue &Hi) {
01227   DebugLoc dl = N->getDebugLoc();
01228   // Expand the subcomponents.
01229   SDValue LHSL, LHSH, RHSL, RHSH;
01230   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
01231   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
01232 
01233   EVT NVT = LHSL.getValueType();
01234   SDValue LoOps[2] = { LHSL, RHSL };
01235   SDValue HiOps[3] = { LHSH, RHSH };
01236 
01237   // Do not generate ADDC/ADDE or SUBC/SUBE if the target does not support
01238   // them.  TODO: Teach operation legalization how to expand unsupported
01239   // ADDC/ADDE/SUBC/SUBE.  The problem is that these operations generate
01240   // a carry of type MVT::Flag, but there doesn't seem to be any way to
01241   // generate a value of this type in the expanded code sequence.
01242   bool hasCarry =
01243     TLI.isOperationLegalOrCustom(N->getOpcode() == ISD::ADD ?
01244                                    ISD::ADDC : ISD::SUBC,
01245                                  TLI.getTypeToExpandTo(*DAG.getContext(), NVT));
01246 
01247   if (hasCarry) {
01248     SDVTList VTList = DAG.getVTList(NVT, MVT::Flag);
01249     if (N->getOpcode() == ISD::ADD) {
01250       Lo = DAG.getNode(ISD::ADDC, dl, VTList, LoOps, 2);
01251       HiOps[2] = Lo.getValue(1);
01252       Hi = DAG.getNode(ISD::ADDE, dl, VTList, HiOps, 3);
01253     } else {
01254       Lo = DAG.getNode(ISD::SUBC, dl, VTList, LoOps, 2);
01255       HiOps[2] = Lo.getValue(1);
01256       Hi = DAG.getNode(ISD::SUBE, dl, VTList, HiOps, 3);
01257     }
01258   } else {
01259     if (N->getOpcode() == ISD::ADD) {
01260       Lo = DAG.getNode(ISD::ADD, dl, NVT, LoOps, 2);
01261       Hi = DAG.getNode(ISD::ADD, dl, NVT, HiOps, 2);
01262       SDValue Cmp1 = DAG.getSetCC(dl, TLI.getSetCCResultType(NVT), Lo, LoOps[0],
01263                                   ISD::SETULT);
01264       SDValue Carry1 = DAG.getNode(ISD::SELECT, dl, NVT, Cmp1,
01265                                    DAG.getConstant(1, NVT),
01266                                    DAG.getConstant(0, NVT));
01267       SDValue Cmp2 = DAG.getSetCC(dl, TLI.getSetCCResultType(NVT), Lo, LoOps[1],
01268                                   ISD::SETULT);
01269       SDValue Carry2 = DAG.getNode(ISD::SELECT, dl, NVT, Cmp2,
01270                                    DAG.getConstant(1, NVT), Carry1);
01271       Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, Carry2);
01272     } else {
01273       Lo = DAG.getNode(ISD::SUB, dl, NVT, LoOps, 2);
01274       Hi = DAG.getNode(ISD::SUB, dl, NVT, HiOps, 2);
01275       SDValue Cmp =
01276         DAG.getSetCC(dl, TLI.getSetCCResultType(LoOps[0].getValueType()),
01277                      LoOps[0], LoOps[1], ISD::SETULT);
01278       SDValue Borrow = DAG.getNode(ISD::SELECT, dl, NVT, Cmp,
01279                                    DAG.getConstant(1, NVT),
01280                                    DAG.getConstant(0, NVT));
01281       Hi = DAG.getNode(ISD::SUB, dl, NVT, Hi, Borrow);
01282     }
01283   }
01284 }
01285 
01286 void DAGTypeLegalizer::ExpandIntRes_ADDSUBC(SDNode *N,
01287                                             SDValue &Lo, SDValue &Hi) {
01288   // Expand the subcomponents.
01289   SDValue LHSL, LHSH, RHSL, RHSH;
01290   DebugLoc dl = N->getDebugLoc();
01291   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
01292   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
01293   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
01294   SDValue LoOps[2] = { LHSL, RHSL };
01295   SDValue HiOps[3] = { LHSH, RHSH };
01296 
01297   if (N->getOpcode() == ISD::ADDC) {
01298     Lo = DAG.getNode(ISD::ADDC, dl, VTList, LoOps, 2);
01299     HiOps[2] = Lo.getValue(1);
01300     Hi = DAG.getNode(ISD::ADDE, dl, VTList, HiOps, 3);
01301   } else {
01302     Lo = DAG.getNode(ISD::SUBC, dl, VTList, LoOps, 2);
01303     HiOps[2] = Lo.getValue(1);
01304     Hi = DAG.getNode(ISD::SUBE, dl, VTList, HiOps, 3);
01305   }
01306 
01307   // Legalized the flag result - switch anything that used the old flag to
01308   // use the new one.
01309   ReplaceValueWith(SDValue(N, 1), Hi.getValue(1));
01310 }
01311 
01312 void DAGTypeLegalizer::ExpandIntRes_ADDSUBE(SDNode *N,
01313                                             SDValue &Lo, SDValue &Hi) {
01314   // Expand the subcomponents.
01315   SDValue LHSL, LHSH, RHSL, RHSH;
01316   DebugLoc dl = N->getDebugLoc();
01317   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
01318   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
01319   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Flag);
01320   SDValue LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
01321   SDValue HiOps[3] = { LHSH, RHSH };
01322 
01323   Lo = DAG.getNode(N->getOpcode(), dl, VTList, LoOps, 3);
01324   HiOps[2] = Lo.getValue(1);
01325   Hi = DAG.getNode(N->getOpcode(), dl, VTList, HiOps, 3);
01326 
01327   // Legalized the flag result - switch anything that used the old flag to
01328   // use the new one.
01329   ReplaceValueWith(SDValue(N, 1), Hi.getValue(1));
01330 }
01331 
01332 void DAGTypeLegalizer::ExpandIntRes_ANY_EXTEND(SDNode *N,
01333                                                SDValue &Lo, SDValue &Hi) {
01334   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
01335   DebugLoc dl = N->getDebugLoc();
01336   SDValue Op = N->getOperand(0);
01337   if (Op.getValueType().bitsLE(NVT)) {
01338     // The low part is any extension of the input (which degenerates to a copy).
01339     Lo = DAG.getNode(ISD::ANY_EXTEND, dl, NVT, Op);
01340     Hi = DAG.getUNDEF(NVT);   // The high part is undefined.
01341   } else {
01342     // For example, extension of an i48 to an i64.  The operand type necessarily
01343     // promotes to the result type, so will end up being expanded too.
01344     assert(getTypeAction(Op.getValueType()) == PromoteInteger &&
01345            "Only know how to promote this result!");
01346     SDValue Res = GetPromotedInteger(Op);
01347     assert(Res.getValueType() == N->getValueType(0) &&
01348            "Operand over promoted?");
01349     // Split the promoted operand.  This will simplify when it is expanded.
01350     SplitInteger(Res, Lo, Hi);
01351   }
01352 }
01353 
01354 void DAGTypeLegalizer::ExpandIntRes_AssertSext(SDNode *N,
01355                                                SDValue &Lo, SDValue &Hi) {
01356   DebugLoc dl = N->getDebugLoc();
01357   GetExpandedInteger(N->getOperand(0), Lo, Hi);
01358   EVT NVT = Lo.getValueType();
01359   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
01360   unsigned NVTBits = NVT.getSizeInBits();
01361   unsigned EVTBits = EVT.getSizeInBits();
01362 
01363   if (NVTBits < EVTBits) {
01364     Hi = DAG.getNode(ISD::AssertSext, dl, NVT, Hi,
01365                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(), EVTBits - NVTBits)));
01366   } else {
01367     Lo = DAG.getNode(ISD::AssertSext, dl, NVT, Lo, DAG.getValueType(EVT));
01368     // The high part replicates the sign bit of Lo, make it explicit.
01369     Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
01370                      DAG.getConstant(NVTBits-1, TLI.getPointerTy()));
01371   }
01372 }
01373 
01374 void DAGTypeLegalizer::ExpandIntRes_AssertZext(SDNode *N,
01375                                                SDValue &Lo, SDValue &Hi) {
01376   DebugLoc dl = N->getDebugLoc();
01377   GetExpandedInteger(N->getOperand(0), Lo, Hi);
01378   EVT NVT = Lo.getValueType();
01379   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
01380   unsigned NVTBits = NVT.getSizeInBits();
01381   unsigned EVTBits = EVT.getSizeInBits();
01382 
01383   if (NVTBits < EVTBits) {
01384     Hi = DAG.getNode(ISD::AssertZext, dl, NVT, Hi,
01385                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(), EVTBits - NVTBits)));
01386   } else {
01387     Lo = DAG.getNode(ISD::AssertZext, dl, NVT, Lo, DAG.getValueType(EVT));
01388     // The high part must be zero, make it explicit.
01389     Hi = DAG.getConstant(0, NVT);
01390   }
01391 }
01392 
01393 void DAGTypeLegalizer::ExpandIntRes_BSWAP(SDNode *N,
01394                                           SDValue &Lo, SDValue &Hi) {
01395   DebugLoc dl = N->getDebugLoc();
01396   GetExpandedInteger(N->getOperand(0), Hi, Lo);  // Note swapped operands.
01397   Lo = DAG.getNode(ISD::BSWAP, dl, Lo.getValueType(), Lo);
01398   Hi = DAG.getNode(ISD::BSWAP, dl, Hi.getValueType(), Hi);
01399 }
01400 
01401 void DAGTypeLegalizer::ExpandIntRes_Constant(SDNode *N,
01402                                              SDValue &Lo, SDValue &Hi) {
01403   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
01404   unsigned NBitWidth = NVT.getSizeInBits();
01405   const APInt &Cst = cast<ConstantSDNode>(N)->getAPIntValue();
01406   Lo = DAG.getConstant(APInt(Cst).trunc(NBitWidth), NVT);
01407   Hi = DAG.getConstant(Cst.lshr(NBitWidth).trunc(NBitWidth), NVT);
01408 }
01409 
01410 void DAGTypeLegalizer::ExpandIntRes_CTLZ(SDNode *N,
01411                                          SDValue &Lo, SDValue &Hi) {
01412   DebugLoc dl = N->getDebugLoc();
01413   // ctlz (HiLo) -> Hi != 0 ? ctlz(Hi) : (ctlz(Lo)+32)
01414   GetExpandedInteger(N->getOperand(0), Lo, Hi);
01415   EVT NVT = Lo.getValueType();
01416 
01417   SDValue HiNotZero = DAG.getSetCC(dl, TLI.getSetCCResultType(NVT), Hi,
01418                                    DAG.getConstant(0, NVT), ISD::SETNE);
01419 
01420   SDValue LoLZ = DAG.getNode(ISD::CTLZ, dl, NVT, Lo);
01421   SDValue HiLZ = DAG.getNode(ISD::CTLZ, dl, NVT, Hi);
01422 
01423   Lo = DAG.getNode(ISD::SELECT, dl, NVT, HiNotZero, HiLZ,
01424                    DAG.getNode(ISD::ADD, dl, NVT, LoLZ,
01425                                DAG.getConstant(NVT.getSizeInBits(), NVT)));
01426   Hi = DAG.getConstant(0, NVT);
01427 }
01428 
01429 void DAGTypeLegalizer::ExpandIntRes_CTPOP(SDNode *N,
01430                                           SDValue &Lo, SDValue &Hi) {
01431   DebugLoc dl = N->getDebugLoc();
01432   // ctpop(HiLo) -> ctpop(Hi)+ctpop(Lo)
01433   GetExpandedInteger(N->getOperand(0), Lo, Hi);
01434   EVT NVT = Lo.getValueType();
01435   Lo = DAG.getNode(ISD::ADD, dl, NVT, DAG.getNode(ISD::CTPOP, dl, NVT, Lo),
01436                    DAG.getNode(ISD::CTPOP, dl, NVT, Hi));
01437   Hi = DAG.getConstant(0, NVT);
01438 }
01439 
01440 void DAGTypeLegalizer::ExpandIntRes_CTTZ(SDNode *N,
01441                                          SDValue &Lo, SDValue &Hi) {
01442   DebugLoc dl = N->getDebugLoc();
01443   // cttz (HiLo) -> Lo != 0 ? cttz(Lo) : (cttz(Hi)+32)
01444   GetExpandedInteger(N->getOperand(0), Lo, Hi);
01445   EVT NVT = Lo.getValueType();
01446 
01447   SDValue LoNotZero = DAG.getSetCC(dl, TLI.getSetCCResultType(NVT), Lo,
01448                                    DAG.getConstant(0, NVT), ISD::SETNE);
01449 
01450   SDValue LoLZ = DAG.getNode(ISD::CTTZ, dl, NVT, Lo);
01451   SDValue HiLZ = DAG.getNode(ISD::CTTZ, dl, NVT, Hi);
01452 
01453   Lo = DAG.getNode(ISD::SELECT, dl, NVT, LoNotZero, LoLZ,
01454                    DAG.getNode(ISD::ADD, dl, NVT, HiLZ,
01455                                DAG.getConstant(NVT.getSizeInBits(), NVT)));
01456   Hi = DAG.getConstant(0, NVT);
01457 }
01458 
01459 void DAGTypeLegalizer::ExpandIntRes_FP_TO_SINT(SDNode *N, SDValue &Lo,
01460                                                SDValue &Hi) {
01461   DebugLoc dl = N->getDebugLoc();
01462   EVT VT = N->getValueType(0);
01463   SDValue Op = N->getOperand(0);
01464   RTLIB::Libcall LC = RTLIB::getFPTOSINT(Op.getValueType(), VT);
01465   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected fp-to-sint conversion!");
01466   SplitInteger(MakeLibCall(LC, VT, &Op, 1, true/*irrelevant*/, dl), Lo, Hi);
01467 }
01468 
01469 void DAGTypeLegalizer::ExpandIntRes_FP_TO_UINT(SDNode *N, SDValue &Lo,
01470                                                SDValue &Hi) {
01471   DebugLoc dl = N->getDebugLoc();
01472   EVT VT = N->getValueType(0);
01473   SDValue Op = N->getOperand(0);
01474   RTLIB::Libcall LC = RTLIB::getFPTOUINT(Op.getValueType(), VT);
01475   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected fp-to-uint conversion!");
01476   SplitInteger(MakeLibCall(LC, VT, &Op, 1, false/*irrelevant*/, dl), Lo, Hi);
01477 }
01478 
01479 void DAGTypeLegalizer::ExpandIntRes_LOAD(LoadSDNode *N,
01480                                          SDValue &Lo, SDValue &Hi) {
01481   if (ISD::isNormalLoad(N)) {
01482     ExpandRes_NormalLoad(N, Lo, Hi);
01483     return;
01484   }
01485 
01486   assert(ISD::isUNINDEXEDLoad(N) && "Indexed load during type legalization!");
01487 
01488   EVT VT = N->getValueType(0);
01489   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
01490   SDValue Ch  = N->getChain();
01491   SDValue Ptr = N->getBasePtr();
01492   ISD::LoadExtType ExtType = N->getExtensionType();
01493   int SVOffset = N->getSrcValueOffset();
01494   unsigned Alignment = N->getAlignment();
01495   bool isVolatile = N->isVolatile();
01496   DebugLoc dl = N->getDebugLoc();
01497 
01498   assert(NVT.isByteSized() && "Expanded type not byte sized!");
01499 
01500   if (N->getMemoryVT().bitsLE(NVT)) {
01501     EVT EVT = N->getMemoryVT();
01502 
01503     Lo = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
01504                         EVT, isVolatile, Alignment);
01505 
01506     // Remember the chain.
01507     Ch = Lo.getValue(1);
01508 
01509     if (ExtType == ISD::SEXTLOAD) {
01510       // The high part is obtained by SRA'ing all but one of the bits of the
01511       // lo part.
01512       unsigned LoSize = Lo.getValueType().getSizeInBits();
01513       Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
01514                        DAG.getConstant(LoSize-1, TLI.getPointerTy()));
01515     } else if (ExtType == ISD::ZEXTLOAD) {
01516       // The high part is just a zero.
01517       Hi = DAG.getConstant(0, NVT);
01518     } else {
01519       assert(ExtType == ISD::EXTLOAD && "Unknown extload!");
01520       // The high part is undefined.
01521       Hi = DAG.getUNDEF(NVT);
01522     }
01523   } else if (TLI.isLittleEndian()) {
01524     // Little-endian - low bits are at low addresses.
01525     Lo = DAG.getLoad(NVT, dl, Ch, Ptr, N->getSrcValue(), SVOffset,
01526                      isVolatile, Alignment);
01527 
01528     unsigned ExcessBits =
01529       N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
01530     EVT NEVT = EVT::getIntegerVT(*DAG.getContext(), ExcessBits);
01531 
01532     // Increment the pointer to the other half.
01533     unsigned IncrementSize = NVT.getSizeInBits()/8;
01534     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
01535                       DAG.getIntPtrConstant(IncrementSize));
01536     Hi = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr, N->getSrcValue(),
01537                         SVOffset+IncrementSize, NEVT,
01538                         isVolatile, MinAlign(Alignment, IncrementSize));
01539 
01540     // Build a factor node to remember that this load is independent of the
01541     // other one.
01542     Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
01543                      Hi.getValue(1));
01544   } else {
01545     // Big-endian - high bits are at low addresses.  Favor aligned loads at
01546     // the cost of some bit-fiddling.
01547     EVT EVT = N->getMemoryVT();
01548     unsigned EBytes = EVT.getStoreSizeInBits()/8;
01549     unsigned IncrementSize = NVT.getSizeInBits()/8;
01550     unsigned ExcessBits = (EBytes - IncrementSize)*8;
01551 
01552     // Load both the high bits and maybe some of the low bits.
01553     Hi = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr, N->getSrcValue(), SVOffset,
01554                         EVT::getIntegerVT(*DAG.getContext(), EVT.getSizeInBits() - ExcessBits),
01555                         isVolatile, Alignment);
01556 
01557     // Increment the pointer to the other half.
01558     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
01559                       DAG.getIntPtrConstant(IncrementSize));
01560     // Load the rest of the low bits.
01561     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, NVT, Ch, Ptr, N->getSrcValue(),
01562                         SVOffset+IncrementSize,
01563                         EVT::getIntegerVT(*DAG.getContext(), ExcessBits),
01564                         isVolatile, MinAlign(Alignment, IncrementSize));
01565 
01566     // Build a factor node to remember that this load is independent of the
01567     // other one.
01568     Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
01569                      Hi.getValue(1));
01570 
01571     if (ExcessBits < NVT.getSizeInBits()) {
01572       // Transfer low bits from the bottom of Hi to the top of Lo.
01573       Lo = DAG.getNode(ISD::OR, dl, NVT, Lo,
01574                        DAG.getNode(ISD::SHL, dl, NVT, Hi,
01575                                    DAG.getConstant(ExcessBits,
01576                                                    TLI.getPointerTy())));
01577       // Move high bits to the right position in Hi.
01578       Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, dl,
01579                        NVT, Hi,
01580                        DAG.getConstant(NVT.getSizeInBits() - ExcessBits,
01581                                        TLI.getPointerTy()));
01582     }
01583   }
01584 
01585   // Legalized the chain result - switch anything that used the old chain to
01586   // use the new one.
01587   ReplaceValueWith(SDValue(N, 1), Ch);
01588 }
01589 
01590 void DAGTypeLegalizer::ExpandIntRes_Logical(SDNode *N,
01591                                             SDValue &Lo, SDValue &Hi) {
01592   DebugLoc dl = N->getDebugLoc();
01593   SDValue LL, LH, RL, RH;
01594   GetExpandedInteger(N->getOperand(0), LL, LH);
01595   GetExpandedInteger(N->getOperand(1), RL, RH);
01596   Lo = DAG.getNode(N->getOpcode(), dl, LL.getValueType(), LL, RL);
01597   Hi = DAG.getNode(N->getOpcode(), dl, LL.getValueType(), LH, RH);
01598 }
01599 
01600 void DAGTypeLegalizer::ExpandIntRes_MUL(SDNode *N,
01601                                         SDValue &Lo, SDValue &Hi) {
01602   EVT VT = N->getValueType(0);
01603   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
01604   DebugLoc dl = N->getDebugLoc();
01605 
01606   bool HasMULHS = TLI.isOperationLegalOrCustom(ISD::MULHS, NVT);
01607   bool HasMULHU = TLI.isOperationLegalOrCustom(ISD::MULHU, NVT);
01608   bool HasSMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::SMUL_LOHI, NVT);
01609   bool HasUMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::UMUL_LOHI, NVT);
01610   if (HasMULHU || HasMULHS || HasUMUL_LOHI || HasSMUL_LOHI) {
01611     SDValue LL, LH, RL, RH;
01612     GetExpandedInteger(N->getOperand(0), LL, LH);
01613     GetExpandedInteger(N->getOperand(1), RL, RH);
01614     unsigned OuterBitSize = VT.getSizeInBits();
01615     unsigned InnerBitSize = NVT.getSizeInBits();
01616     unsigned LHSSB = DAG.ComputeNumSignBits(N->getOperand(0));
01617     unsigned RHSSB = DAG.ComputeNumSignBits(N->getOperand(1));
01618 
01619     APInt HighMask = APInt::getHighBitsSet(OuterBitSize, InnerBitSize);
01620     if (DAG.MaskedValueIsZero(N->getOperand(0), HighMask) &&
01621         DAG.MaskedValueIsZero(N->getOperand(1), HighMask)) {
01622       // The inputs are both zero-extended.
01623       if (HasUMUL_LOHI) {
01624         // We can emit a umul_lohi.
01625         Lo = DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(NVT, NVT), LL, RL);
01626         Hi = SDValue(Lo.getNode(), 1);
01627         return;
01628       }
01629       if (HasMULHU) {
01630         // We can emit a mulhu+mul.
01631         Lo = DAG.getNode(ISD::MUL, dl, NVT, LL, RL);
01632         Hi = DAG.getNode(ISD::MULHU, dl, NVT, LL, RL);
01633         return;
01634       }
01635     }
01636     if (LHSSB > InnerBitSize && RHSSB > InnerBitSize) {
01637       // The input values are both sign-extended.
01638       if (HasSMUL_LOHI) {
01639         // We can emit a smul_lohi.
01640         Lo = DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(NVT, NVT), LL, RL);
01641         Hi = SDValue(Lo.getNode(), 1);
01642         return;
01643       }
01644       if (HasMULHS) {
01645         // We can emit a mulhs+mul.
01646         Lo = DAG.getNode(ISD::MUL, dl, NVT, LL, RL);
01647         Hi = DAG.getNode(ISD::MULHS, dl, NVT, LL, RL);
01648         return;
01649       }
01650     }
01651     if (HasUMUL_LOHI) {
01652       // Lo,Hi = umul LHS, RHS.
01653       SDValue UMulLOHI = DAG.getNode(ISD::UMUL_LOHI, dl,
01654                                        DAG.getVTList(NVT, NVT), LL, RL);
01655       Lo = UMulLOHI;
01656       Hi = UMulLOHI.getValue(1);
01657       RH = DAG.getNode(ISD::MUL, dl, NVT, LL, RH);
01658       LH = DAG.getNode(ISD::MUL, dl, NVT, LH, RL);
01659       Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, RH);
01660       Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, LH);
01661       return;
01662     }
01663     if (HasMULHU) {
01664       Lo = DAG.getNode(ISD::MUL, dl, NVT, LL, RL);
01665       Hi = DAG.getNode(ISD::MULHU, dl, NVT, LL, RL);
01666       RH = DAG.getNode(ISD::MUL, dl, NVT, LL, RH);
01667       LH = DAG.getNode(ISD::MUL, dl, NVT, LH, RL);
01668       Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, RH);
01669       Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, LH);
01670       return;
01671     }
01672   }
01673 
01674   // If nothing else, we can make a libcall.
01675   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
01676   if (VT == MVT::i16)
01677     LC = RTLIB::MUL_I16;
01678   else if (VT == MVT::i32)
01679     LC = RTLIB::MUL_I32;
01680   else if (VT == MVT::i64)
01681     LC = RTLIB::MUL_I64;
01682   else if (VT == MVT::i128)
01683     LC = RTLIB::MUL_I128;
01684   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported MUL!");
01685 
01686   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
01687   SplitInteger(MakeLibCall(LC, VT, Ops, 2, true/*irrelevant*/, dl), Lo, Hi);
01688 }
01689 
01690 void DAGTypeLegalizer::ExpandIntRes_SDIV(SDNode *N,
01691                                          SDValue &Lo, SDValue &Hi) {
01692   EVT VT = N->getValueType(0);
01693   DebugLoc dl = N->getDebugLoc();
01694 
01695   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
01696   if (VT == MVT::i16)
01697     LC = RTLIB::SDIV_I16;
01698   else if (VT == MVT::i32)
01699     LC = RTLIB::SDIV_I32;
01700   else if (VT == MVT::i64)
01701     LC = RTLIB::SDIV_I64;
01702   else if (VT == MVT::i128)
01703     LC = RTLIB::SDIV_I128;
01704   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SDIV!");
01705 
01706   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
01707   SplitInteger(MakeLibCall(LC, VT, Ops, 2, true, dl), Lo, Hi);
01708 }
01709 
01710 void DAGTypeLegalizer::ExpandIntRes_Shift(SDNode *N,
01711                                           SDValue &Lo, SDValue &Hi) {
01712   EVT VT = N->getValueType(0);
01713   DebugLoc dl = N->getDebugLoc();
01714 
01715   // If we can emit an efficient shift operation, do so now.  Check to see if
01716   // the RHS is a constant.
01717   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
01718     return ExpandShiftByConstant(N, CN->getZExtValue(), Lo, Hi);
01719 
01720   // If we can determine that the high bit of the shift is zero or one, even if
01721   // the low bits are variable, emit this shift in an optimized form.
01722   if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
01723     return;
01724 
01725   // If this target supports shift_PARTS, use it.  First, map to the _PARTS opc.
01726   unsigned PartsOpc;
01727   if (N->getOpcode() == ISD::SHL) {
01728     PartsOpc = ISD::SHL_PARTS;
01729   } else if (N->getOpcode() == ISD::SRL) {
01730     PartsOpc = ISD::SRL_PARTS;
01731   } else {
01732     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
01733     PartsOpc = ISD::SRA_PARTS;
01734   }
01735 
01736   // Next check to see if the target supports this SHL_PARTS operation or if it
01737   // will custom expand it.
01738   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
01739   TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
01740   if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
01741       Action == TargetLowering::Custom) {
01742     // Expand the subcomponents.
01743     SDValue LHSL, LHSH;
01744     GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
01745 
01746     SDValue Ops[] = { LHSL, LHSH, N->getOperand(1) };
01747     EVT VT = LHSL.getValueType();
01748     Lo = DAG.getNode(PartsOpc, dl, DAG.getVTList(VT, VT), Ops, 3);
01749     Hi = Lo.getValue(1);
01750     return;
01751   }
01752 
01753   // Otherwise, emit a libcall.
01754   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
01755   bool isSigned;
01756   if (N->getOpcode() == ISD::SHL) {
01757     isSigned = false; /*sign irrelevant*/
01758     if (VT == MVT::i16)
01759       LC = RTLIB::SHL_I16;
01760     else if (VT == MVT::i32)
01761       LC = RTLIB::SHL_I32;
01762     else if (VT == MVT::i64)
01763       LC = RTLIB::SHL_I64;
01764     else if (VT == MVT::i128)
01765       LC = RTLIB::SHL_I128;
01766   } else if (N->getOpcode() == ISD::SRL) {
01767     isSigned = false;
01768     if (VT == MVT::i16)
01769       LC = RTLIB::SRL_I16;
01770     else if (VT == MVT::i32)
01771       LC = RTLIB::SRL_I32;
01772     else if (VT == MVT::i64)
01773       LC = RTLIB::SRL_I64;
01774     else if (VT == MVT::i128)
01775       LC = RTLIB::SRL_I128;
01776   } else {
01777     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
01778     isSigned = true;
01779     if (VT == MVT::i16)
01780       LC = RTLIB::SRA_I16;
01781     else if (VT == MVT::i32)
01782       LC = RTLIB::SRA_I32;
01783     else if (VT == MVT::i64)
01784       LC = RTLIB::SRA_I64;
01785     else if (VT == MVT::i128)
01786       LC = RTLIB::SRA_I128;
01787   }
01788 
01789   if (LC != RTLIB::UNKNOWN_LIBCALL && TLI.getLibcallName(LC)) {
01790     SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
01791     SplitInteger(MakeLibCall(LC, VT, Ops, 2, isSigned, dl), Lo, Hi);
01792     return;
01793   }
01794 
01795   if (!ExpandShiftWithUnknownAmountBit(N, Lo, Hi))
01796     llvm_unreachable("Unsupported shift!");
01797 }
01798 
01799 void DAGTypeLegalizer::ExpandIntRes_SIGN_EXTEND(SDNode *N,
01800                                                 SDValue &Lo, SDValue &Hi) {
01801   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
01802   DebugLoc dl = N->getDebugLoc();
01803   SDValue Op = N->getOperand(0);
01804   if (Op.getValueType().bitsLE(NVT)) {
01805     // The low part is sign extension of the input (degenerates to a copy).
01806     Lo = DAG.getNode(ISD::SIGN_EXTEND, dl, NVT, N->getOperand(0));
01807     // The high part is obtained by SRA'ing all but one of the bits of low part.
01808     unsigned LoSize = NVT.getSizeInBits();
01809     Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
01810                      DAG.getConstant(LoSize-1, TLI.getPointerTy()));
01811   } else {
01812     // For example, extension of an i48 to an i64.  The operand type necessarily
01813     // promotes to the result type, so will end up being expanded too.
01814     assert(getTypeAction(Op.getValueType()) == PromoteInteger &&
01815            "Only know how to promote this result!");
01816     SDValue Res = GetPromotedInteger(Op);
01817     assert(Res.getValueType() == N->getValueType(0) &&
01818            "Operand over promoted?");
01819     // Split the promoted operand.  This will simplify when it is expanded.
01820     SplitInteger(Res, Lo, Hi);
01821     unsigned ExcessBits =
01822       Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
01823     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
01824                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(), ExcessBits)));
01825   }
01826 }
01827 
01828 void DAGTypeLegalizer::
01829 ExpandIntRes_SIGN_EXTEND_INREG(SDNode *N, SDValue &Lo, SDValue &Hi) {
01830   DebugLoc dl = N->getDebugLoc();
01831   GetExpandedInteger(N->getOperand(0), Lo, Hi);
01832   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
01833 
01834   if (EVT.bitsLE(Lo.getValueType())) {
01835     // sext_inreg the low part if needed.
01836     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Lo.getValueType(), Lo,
01837                      N->getOperand(1));
01838 
01839     // The high part gets the sign extension from the lo-part.  This handles
01840     // things like sextinreg V:i64 from i8.
01841     Hi = DAG.getNode(ISD::SRA, dl, Hi.getValueType(), Lo,
01842                      DAG.getConstant(Hi.getValueType().getSizeInBits()-1,
01843                                      TLI.getPointerTy()));
01844   } else {
01845     // For example, extension of an i48 to an i64.  Leave the low part alone,
01846     // sext_inreg the high part.
01847     unsigned ExcessBits =
01848       EVT.getSizeInBits() - Lo.getValueType().getSizeInBits();
01849     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
01850                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(), ExcessBits)));
01851   }
01852 }
01853 
01854 void DAGTypeLegalizer::ExpandIntRes_SREM(SDNode *N,
01855                                          SDValue &Lo, SDValue &Hi) {
01856   EVT VT = N->getValueType(0);
01857   DebugLoc dl = N->getDebugLoc();
01858 
01859   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
01860   if (VT == MVT::i16)
01861     LC = RTLIB::SREM_I16;
01862   else if (VT == MVT::i32)
01863     LC = RTLIB::SREM_I32;
01864   else if (VT == MVT::i64)
01865     LC = RTLIB::SREM_I64;
01866   else if (VT == MVT::i128)
01867     LC = RTLIB::SREM_I128;
01868   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SREM!");
01869 
01870   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
01871   SplitInteger(MakeLibCall(LC, VT, Ops, 2, true, dl), Lo, Hi);
01872 }
01873 
01874 void DAGTypeLegalizer::ExpandIntRes_TRUNCATE(SDNode *N,
01875                                              SDValue &Lo, SDValue &Hi) {
01876   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
01877   DebugLoc dl = N->getDebugLoc();
01878   Lo = DAG.getNode(ISD::TRUNCATE, dl, NVT, N->getOperand(0));
01879   Hi = DAG.getNode(ISD::SRL, dl,
01880                    N->getOperand(0).getValueType(), N->getOperand(0),
01881                    DAG.getConstant(NVT.getSizeInBits(), TLI.getPointerTy()));
01882   Hi = DAG.getNode(ISD::TRUNCATE, dl, NVT, Hi);
01883 }
01884 
01885 void DAGTypeLegalizer::ExpandIntRes_UDIV(SDNode *N,
01886                                          SDValue &Lo, SDValue &Hi) {
01887   EVT VT = N->getValueType(0);
01888   DebugLoc dl = N->getDebugLoc();
01889 
01890   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
01891   if (VT == MVT::i16)
01892     LC = RTLIB::UDIV_I16;
01893   else if (VT == MVT::i32)
01894     LC = RTLIB::UDIV_I32;
01895   else if (VT == MVT::i64)
01896     LC = RTLIB::UDIV_I64;
01897   else if (VT == MVT::i128)
01898     LC = RTLIB::UDIV_I128;
01899   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UDIV!");
01900 
01901   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
01902   SplitInteger(MakeLibCall(LC, VT, Ops, 2, false, dl), Lo, Hi);
01903 }
01904 
01905 void DAGTypeLegalizer::ExpandIntRes_UREM(SDNode *N,
01906                                          SDValue &Lo, SDValue &Hi) {
01907   EVT VT = N->getValueType(0);
01908   DebugLoc dl = N->getDebugLoc();
01909 
01910   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
01911   if (VT == MVT::i16)
01912     LC = RTLIB::UREM_I16;
01913   else if (VT == MVT::i32)
01914     LC = RTLIB::UREM_I32;
01915   else if (VT == MVT::i64)
01916     LC = RTLIB::UREM_I64;
01917   else if (VT == MVT::i128)
01918     LC = RTLIB::UREM_I128;
01919   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UREM!");
01920 
01921   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
01922   SplitInteger(MakeLibCall(LC, VT, Ops, 2, false, dl), Lo, Hi);
01923 }
01924 
01925 void DAGTypeLegalizer::ExpandIntRes_ZERO_EXTEND(SDNode *N,
01926                                                 SDValue &Lo, SDValue &Hi) {
01927   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
01928   DebugLoc dl = N->getDebugLoc();
01929   SDValue Op = N->getOperand(0);
01930   if (Op.getValueType().bitsLE(NVT)) {
01931     // The low part is zero extension of the input (degenerates to a copy).
01932     Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, N->getOperand(0));
01933     Hi = DAG.getConstant(0, NVT);   // The high part is just a zero.
01934   } else {
01935     // For example, extension of an i48 to an i64.  The operand type necessarily
01936     // promotes to the result type, so will end up being expanded too.
01937     assert(getTypeAction(Op.getValueType()) == PromoteInteger &&
01938            "Only know how to promote this result!");
01939     SDValue Res = GetPromotedInteger(Op);
01940     assert(Res.getValueType() == N->getValueType(0) &&
01941            "Operand over promoted?");
01942     // Split the promoted operand.  This will simplify when it is expanded.
01943     SplitInteger(Res, Lo, Hi);
01944     unsigned ExcessBits =
01945       Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
01946     Hi = DAG.getZeroExtendInReg(Hi, dl, EVT::getIntegerVT(*DAG.getContext(), ExcessBits));
01947   }
01948 }
01949 
01950 
01951 //===----------------------------------------------------------------------===//
01952 //  Integer Operand Expansion
01953 //===----------------------------------------------------------------------===//
01954 
01955 /// ExpandIntegerOperand - This method is called when the specified operand of
01956 /// the specified node is found to need expansion.  At this point, all of the
01957 /// result types of the node are known to be legal, but other operands of the
01958 /// node may need promotion or expansion as well as the specified one.
01959 bool DAGTypeLegalizer::ExpandIntegerOperand(SDNode *N, unsigned OpNo) {
01960   DEBUG(errs() << "Expand integer operand: "; N->dump(&DAG); errs() << "\n");
01961   SDValue Res = SDValue();
01962 
01963   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
01964     return false;
01965 
01966   switch (N->getOpcode()) {
01967   default:
01968   #ifndef NDEBUG
01969     errs() << "ExpandIntegerOperand Op #" << OpNo << ": ";
01970     N->dump(&DAG); errs() << "\n";
01971   #endif
01972     llvm_unreachable("Do not know how to expand this operator's operand!");
01973 
01974   case ISD::BIT_CONVERT:       Res = ExpandOp_BIT_CONVERT(N); break;
01975   case ISD::BR_CC:             Res = ExpandIntOp_BR_CC(N); break;
01976   case ISD::BUILD_VECTOR:      Res = ExpandOp_BUILD_VECTOR(N); break;
01977   case ISD::EXTRACT_ELEMENT:   Res = ExpandOp_EXTRACT_ELEMENT(N); break;
01978   case ISD::INSERT_VECTOR_ELT: Res = ExpandOp_INSERT_VECTOR_ELT(N); break;
01979   case ISD::SCALAR_TO_VECTOR:  Res = ExpandOp_SCALAR_TO_VECTOR(N); break;
01980   case ISD::SELECT_CC:         Res = ExpandIntOp_SELECT_CC(N); break;
01981   case ISD::SETCC:             Res = ExpandIntOp_SETCC(N); break;
01982   case ISD::SINT_TO_FP:        Res = ExpandIntOp_SINT_TO_FP(N); break;
01983   case ISD::STORE:   Res = ExpandIntOp_STORE(cast<StoreSDNode>(N), OpNo); break;
01984   case ISD::TRUNCATE:          Res = ExpandIntOp_TRUNCATE(N); break;
01985   case ISD::UINT_TO_FP:        Res = ExpandIntOp_UINT_TO_FP(N); break;
01986 
01987   case ISD::SHL:
01988   case ISD::SRA:
01989   case ISD::SRL:
01990   case ISD::ROTL:
01991   case ISD::ROTR: Res = ExpandIntOp_Shift(N); break;
01992   }
01993 
01994   // If the result is null, the sub-method took care of registering results etc.
01995   if (!Res.getNode()) return false;
01996 
01997   // If the result is N, the sub-method updated N in place.  Tell the legalizer
01998   // core about this.
01999   if (Res.getNode() == N)
02000     return true;
02001 
02002   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
02003          "Invalid operand expansion");
02004 
02005   ReplaceValueWith(SDValue(N, 0), Res);
02006   return false;
02007 }
02008 
02009 /// IntegerExpandSetCCOperands - Expand the operands of a comparison.  This code
02010 /// is shared among BR_CC, SELECT_CC, and SETCC handlers.
02011 void DAGTypeLegalizer::IntegerExpandSetCCOperands(SDValue &NewLHS,
02012                                                   SDValue &NewRHS,
02013                                                   ISD::CondCode &CCCode,
02014                                                   DebugLoc dl) {
02015   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
02016   GetExpandedInteger(NewLHS, LHSLo, LHSHi);
02017   GetExpandedInteger(NewRHS, RHSLo, RHSHi);
02018 
02019   EVT VT = NewLHS.getValueType();
02020 
02021   if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
02022     if (RHSLo == RHSHi) {
02023       if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) {
02024         if (RHSCST->isAllOnesValue()) {
02025           // Equality comparison to -1.
02026           NewLHS = DAG.getNode(ISD::AND, dl,
02027                                LHSLo.getValueType(), LHSLo, LHSHi);
02028           NewRHS = RHSLo;
02029           return;
02030         }
02031       }
02032     }
02033 
02034     NewLHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSLo, RHSLo);
02035     NewRHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSHi, RHSHi);
02036     NewLHS = DAG.getNode(ISD::OR, dl, NewLHS.getValueType(), NewLHS, NewRHS);
02037     NewRHS = DAG.getConstant(0, NewLHS.getValueType());
02038     return;
02039   }
02040 
02041   // If this is a comparison of the sign bit, just look at the top part.
02042   // X > -1,  x < 0
02043   if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
02044     if ((CCCode == ISD::SETLT && CST->isNullValue()) ||     // X < 0
02045         (CCCode == ISD::SETGT && CST->isAllOnesValue())) {  // X > -1
02046       NewLHS = LHSHi;
02047       NewRHS = RHSHi;
02048       return;
02049     }
02050 
02051   // FIXME: This generated code sucks.
02052   ISD::CondCode LowCC;
02053   switch (CCCode) {
02054   default: llvm_unreachable("Unknown integer setcc!");
02055   case ISD::SETLT:
02056   case ISD::SETULT: LowCC = ISD::SETULT; break;
02057   case ISD::SETGT:
02058   case ISD::SETUGT: LowCC = ISD::SETUGT; break;
02059   case ISD::SETLE:
02060   case ISD::SETULE: LowCC = ISD::SETULE; break;
02061   case ISD::SETGE:
02062   case ISD::SETUGE: LowCC = ISD::SETUGE; break;
02063   }
02064 
02065   // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
02066   // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
02067   // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
02068 
02069   // NOTE: on targets without efficient SELECT of bools, we can always use
02070   // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
02071   TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, false, true, true, NULL);
02072   SDValue Tmp1, Tmp2;
02073   Tmp1 = TLI.SimplifySetCC(TLI.getSetCCResultType(LHSLo.getValueType()),
02074                            LHSLo, RHSLo, LowCC, false, DagCombineInfo, dl);
02075   if (!Tmp1.getNode())
02076     Tmp1 = DAG.getSetCC(dl, TLI.getSetCCResultType(LHSLo.getValueType()),
02077                         LHSLo, RHSLo, LowCC);
02078   Tmp2 = TLI.SimplifySetCC(TLI.getSetCCResultType(LHSHi.getValueType()),
02079                            LHSHi, RHSHi, CCCode, false, DagCombineInfo, dl);
02080   if (!Tmp2.getNode())
02081     Tmp2 = DAG.getNode(ISD::SETCC, dl,
02082                        TLI.getSetCCResultType(LHSHi.getValueType()),
02083                        LHSHi, RHSHi, DAG.getCondCode(CCCode));
02084 
02085   ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.getNode());
02086   ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.getNode());
02087   if ((Tmp1C && Tmp1C->isNullValue()) ||
02088       (Tmp2C && Tmp2C->isNullValue() &&
02089        (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
02090         CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) ||
02091       (Tmp2C && Tmp2C->getAPIntValue() == 1 &&
02092        (CCCode == ISD::SETLT || CCCode == ISD::SETGT ||
02093         CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) {
02094     // low part is known false, returns high part.
02095     // For LE / GE, if high part is known false, ignore the low part.
02096     // For LT / GT, if high part is known true, ignore the low part.
02097     NewLHS = Tmp2;
02098     NewRHS = SDValue();
02099     return;
02100   }
02101 
02102   NewLHS = TLI.SimplifySetCC(TLI.getSetCCResultType(LHSHi.getValueType()),
02103                              LHSHi, RHSHi, ISD::SETEQ, false,
02104                              DagCombineInfo, dl);
02105   if (!NewLHS.getNode())
02106     NewLHS = DAG.getSetCC(dl, TLI.getSetCCResultType(LHSHi.getValueType()),
02107                           LHSHi, RHSHi, ISD::SETEQ);
02108   NewLHS = DAG.getNode(ISD::SELECT, dl, Tmp1.getValueType(),
02109                        NewLHS, Tmp1, Tmp2);
02110   NewRHS = SDValue();
02111 }
02112 
02113 SDValue DAGTypeLegalizer::ExpandIntOp_BR_CC(SDNode *N) {
02114   SDValue NewLHS = N->getOperand(2), NewRHS = N->getOperand(3);
02115   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(1))->get();
02116   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, N->getDebugLoc());
02117 
02118   // If ExpandSetCCOperands returned a scalar, we need to compare the result
02119   // against zero to select between true and false values.
02120   if (NewRHS.getNode() == 0) {
02121     NewRHS = DAG.getConstant(0, NewLHS.getValueType());
02122     CCCode = ISD::SETNE;
02123   }
02124 
02125   // Update N to have the operands specified.
02126   return DAG.UpdateNodeOperands(SDValue(N, 0), N->getOperand(0),
02127                                 DAG.getCondCode(CCCode), NewLHS, NewRHS,
02128                                 N->getOperand(4));
02129 }
02130 
02131 SDValue DAGTypeLegalizer::ExpandIntOp_SELECT_CC(SDNode *N) {
02132   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
02133   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(4))->get();
02134   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, N->getDebugLoc());
02135 
02136   // If ExpandSetCCOperands returned a scalar, we need to compare the result
02137   // against zero to select between true and false values.
02138   if (NewRHS.getNode() == 0) {
02139     NewRHS = DAG.getConstant(0, NewLHS.getValueType());
02140     CCCode = ISD::SETNE;
02141   }
02142 
02143   // Update N to have the operands specified.
02144   return DAG.UpdateNodeOperands(SDValue(N, 0), NewLHS, NewRHS,
02145                                 N->getOperand(2), N->getOperand(3),
02146                                 DAG.getCondCode(CCCode));
02147 }
02148 
02149 SDValue DAGTypeLegalizer::ExpandIntOp_SETCC(SDNode *N) {
02150   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
02151   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
02152   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, N->getDebugLoc());
02153 
02154   // If ExpandSetCCOperands returned a scalar, use it.
02155   if (NewRHS.getNode() == 0) {
02156     assert(NewLHS.getValueType() == N->getValueType(0) &&
02157            "Unexpected setcc expansion!");
02158     return NewLHS;
02159   }
02160 
02161   // Otherwise, update N to have the operands specified.
02162   return DAG.UpdateNodeOperands(SDValue(N, 0), NewLHS, NewRHS,
02163                                 DAG.getCondCode(CCCode));
02164 }
02165 
02166 SDValue DAGTypeLegalizer::ExpandIntOp_Shift(SDNode *N) {
02167   // The value being shifted is legal, but the shift amount is too big.
02168   // It follows that either the result of the shift is undefined, or the
02169   // upper half of the shift amount is zero.  Just use the lower half.
02170   SDValue Lo, Hi;
02171   GetExpandedInteger(N->getOperand(1), Lo, Hi);
02172   return DAG.UpdateNodeOperands(SDValue(N, 0), N->getOperand(0), Lo);
02173 }
02174 
02175 SDValue DAGTypeLegalizer::ExpandIntOp_SINT_TO_FP(SDNode *N) {
02176   SDValue Op = N->getOperand(0);
02177   EVT DstVT = N->getValueType(0);
02178   RTLIB::Libcall LC = RTLIB::getSINTTOFP(Op.getValueType(), DstVT);
02179   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
02180          "Don't know how to expand this SINT_TO_FP!");
02181   return MakeLibCall(LC, DstVT, &Op, 1, true, N->getDebugLoc());
02182 }
02183 
02184 SDValue DAGTypeLegalizer::ExpandIntOp_STORE(StoreSDNode *N, unsigned OpNo) {
02185   if (ISD::isNormalStore(N))
02186     return ExpandOp_NormalStore(N, OpNo);
02187 
02188   assert(ISD::isUNINDEXEDStore(N) && "Indexed store during type legalization!");
02189   assert(OpNo == 1 && "Can only expand the stored value so far");
02190 
02191   EVT VT = N->getOperand(1).getValueType();
02192   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
02193   SDValue Ch  = N->getChain();
02194   SDValue Ptr = N->getBasePtr();
02195   int SVOffset = N->getSrcValueOffset();
02196   unsigned Alignment = N->getAlignment();
02197   bool isVolatile = N->isVolatile();
02198   DebugLoc dl = N->getDebugLoc();
02199   SDValue Lo, Hi;
02200 
02201   assert(NVT.isByteSized() && "Expanded type not byte sized!");
02202 
02203   if (N->getMemoryVT().bitsLE(NVT)) {
02204     GetExpandedInteger(N->getValue(), Lo, Hi);
02205     return DAG.getTruncStore(Ch, dl, Lo, Ptr, N->getSrcValue(), SVOffset,
02206                              N->getMemoryVT(), isVolatile, Alignment);
02207   } else if (TLI.isLittleEndian()) {
02208     // Little-endian - low bits are at low addresses.
02209     GetExpandedInteger(N->getValue(), Lo, Hi);
02210 
02211     Lo = DAG.getStore(Ch, dl, Lo, Ptr, N->getSrcValue(), SVOffset,
02212                       isVolatile, Alignment);
02213 
02214     unsigned ExcessBits =
02215       N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
02216     EVT NEVT = EVT::getIntegerVT(*DAG.getContext(), ExcessBits);
02217 
02218     // Increment the pointer to the other half.
02219     unsigned IncrementSize = NVT.getSizeInBits()/8;
02220     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
02221                       DAG.getIntPtrConstant(IncrementSize));
02222     Hi = DAG.getTruncStore(Ch, dl, Hi, Ptr, N->getSrcValue(),
02223                            SVOffset+IncrementSize, NEVT,
02224                            isVolatile, MinAlign(Alignment, IncrementSize));
02225     return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
02226   } else {
02227     // Big-endian - high bits are at low addresses.  Favor aligned stores at
02228     // the cost of some bit-fiddling.
02229     GetExpandedInteger(N->getValue(), Lo, Hi);
02230 
02231     EVT ExtVT = N->getMemoryVT();
02232     unsigned EBytes = ExtVT.getStoreSizeInBits()/8;
02233     unsigned IncrementSize = NVT.getSizeInBits()/8;
02234     unsigned ExcessBits = (EBytes - IncrementSize)*8;
02235     EVT HiVT = EVT::getIntegerVT(*DAG.getContext(), ExtVT.getSizeInBits() - ExcessBits);
02236 
02237     if (ExcessBits < NVT.getSizeInBits()) {
02238       // Transfer high bits from the top of Lo to the bottom of Hi.
02239       Hi = DAG.getNode(ISD::SHL, dl, NVT, Hi,
02240                        DAG.getConstant(NVT.getSizeInBits() - ExcessBits,
02241                                        TLI.getPointerTy()));
02242       Hi = DAG.getNode(ISD::OR, dl, NVT, Hi,
02243                        DAG.getNode(ISD::SRL, dl, NVT, Lo,
02244                                    DAG.getConstant(ExcessBits,
02245                                                    TLI.getPointerTy())));
02246     }
02247 
02248     // Store both the high bits and maybe some of the low bits.
02249     Hi = DAG.getTruncStore(Ch, dl, Hi, Ptr, N->getSrcValue(),
02250                            SVOffset, HiVT, isVolatile, Alignment);
02251 
02252     // Increment the pointer to the other half.
02253     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
02254                       DAG.getIntPtrConstant(IncrementSize));
02255     // Store the lowest ExcessBits bits in the second half.
02256     Lo = DAG.getTruncStore(Ch, dl, Lo, Ptr, N->getSrcValue(),
02257                            SVOffset+IncrementSize,
02258                            EVT::getIntegerVT(*DAG.getContext(), ExcessBits),
02259                            isVolatile, MinAlign(Alignment, IncrementSize));
02260     return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
02261   }
02262 }
02263 
02264 SDValue DAGTypeLegalizer::ExpandIntOp_TRUNCATE(SDNode *N) {
02265   SDValue InL, InH;
02266   GetExpandedInteger(N->getOperand(0), InL, InH);
02267   // Just truncate the low part of the source.
02268   return DAG.getNode(ISD::TRUNCATE, N->getDebugLoc(), N->getValueType(0), InL);
02269 }
02270 
02271 SDValue DAGTypeLegalizer::ExpandIntOp_UINT_TO_FP(SDNode *N) {
02272   SDValue Op = N->getOperand(0);
02273   EVT SrcVT = Op.getValueType();
02274   EVT DstVT = N->getValueType(0);
02275   DebugLoc dl = N->getDebugLoc();
02276 
02277   if (TLI.getOperationAction(ISD::SINT_TO_FP, SrcVT) == TargetLowering::Custom){
02278     // Do a signed conversion then adjust the result.
02279     SDValue SignedConv = DAG.getNode(ISD::SINT_TO_FP, dl, DstVT, Op);
02280     SignedConv = TLI.LowerOperation(SignedConv, DAG);
02281 
02282     // The result of the signed conversion needs adjusting if the 'sign bit' of
02283     // the incoming integer was set.  To handle this, we dynamically test to see
02284     // if it is set, and, if so, add a fudge factor.
02285 
02286     const uint64_t F32TwoE32  = 0x4F800000ULL;
02287     const uint64_t F32TwoE64  = 0x5F800000ULL;
02288     const uint64_t F32TwoE128 = 0x7F800000ULL;
02289 
02290     APInt FF(32, 0);
02291     if (SrcVT == MVT::i32)
02292       FF = APInt(32, F32TwoE32);
02293     else if (SrcVT == MVT::i64)
02294       FF = APInt(32, F32TwoE64);
02295     else if (SrcVT == MVT::i128)
02296       FF = APInt(32, F32TwoE128);
02297     else
02298       assert(false && "Unsupported UINT_TO_FP!");
02299 
02300     // Check whether the sign bit is set.
02301     SDValue Lo, Hi;
02302     GetExpandedInteger(Op, Lo, Hi);
02303     SDValue SignSet = DAG.getSetCC(dl,
02304                                    TLI.getSetCCResultType(Hi.getValueType()),
02305                                    Hi, DAG.getConstant(0, Hi.getValueType()),
02306                                    ISD::SETLT);
02307 
02308     // Build a 64 bit pair (0, FF) in the constant pool, with FF in the lo bits.
02309     SDValue FudgePtr = DAG.getConstantPool(
02310                                ConstantInt::get(*DAG.getContext(), FF.zext(64)),
02311                                            TLI.getPointerTy());
02312 
02313     // Get a pointer to FF if the sign bit was set, or to 0 otherwise.
02314     SDValue Zero = DAG.getIntPtrConstant(0);
02315     SDValue Four = DAG.getIntPtrConstant(4);
02316     if (TLI.isBigEndian()) std::swap(Zero, Four);
02317     SDValue Offset = DAG.getNode(ISD::SELECT, dl, Zero.getValueType(), SignSet,
02318                                  Zero, Four);
02319     unsigned Alignment = cast<ConstantPoolSDNode>(FudgePtr)->getAlignment();
02320     FudgePtr = DAG.getNode(ISD::ADD, dl, TLI.getPointerTy(), FudgePtr, Offset);
02321     Alignment = std::min(Alignment, 4u);
02322 
02323     // Load the value out, extending it from f32 to the destination float type.
02324     // FIXME: Avoid the extend by constructing the right constant pool?
02325     SDValue Fudge = DAG.getExtLoad(ISD::EXTLOAD, dl, DstVT, DAG.getEntryNode(),
02326                                    FudgePtr, NULL, 0, MVT::f32,
02327                                    false, Alignment);
02328     return DAG.getNode(ISD::FADD, dl, DstVT, SignedConv, Fudge);
02329   }
02330 
02331   // Otherwise, use a libcall.
02332   RTLIB::Libcall LC = RTLIB::getUINTTOFP(SrcVT, DstVT);
02333   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
02334          "Don't know how to expand this UINT_TO_FP!");
02335   return MakeLibCall(LC, DstVT, &Op, 1, true, dl);
02336 }