contrib/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

   1 //===----- LegalizeIntegerTypes.cpp - Legalization of integer types -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements integer type expansion and promotion for LegalizeTypes.
  11 // Promotion is the act of changing a computation in an illegal type into a
  12 // computation in a larger type.  For example, implementing i8 arithmetic in an
  13 // i32 register (often needed on powerpc).
  14 // Expansion is the act of changing a computation in an illegal type into a
  15 // computation in two identical registers of a smaller type.  For example,
  16 // implementing i64 arithmetic in two i32 registers (often needed on 32-bit
  17 // targets).
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "LegalizeTypes.h"
  22 #include "llvm/IR/DerivedTypes.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 using namespace llvm;
  26
  27 #define DEBUG_TYPE "legalize-types"
  28
  29 //===----------------------------------------------------------------------===//
  30 //  Integer Result Promotion
  31 //===----------------------------------------------------------------------===//
  32
  33 /// PromoteIntegerResult - This method is called when a result of a node is
  34 /// found to be in need of promotion to a larger type.  At this point, the node
  35 /// may also have invalid operands or may have other results that need
  36 /// expansion, we just know that (at least) one result needs promotion.
  37 void DAGTypeLegalizer::PromoteIntegerResult(SDNode *N, unsigned ResNo) {
  38   DEBUG(dbgs() << "Promote integer result: "; N->dump(&DAG); dbgs() << "\n");
  39   SDValue Res = SDValue();
  40
  41   // See if the target wants to custom expand this node.
  42   if (CustomLowerNode(N, N->getValueType(ResNo), true))
  43     return;
  44
  45   switch (N->getOpcode()) {
  46   default:
  47 #ifndef NDEBUG
  48     dbgs() << "PromoteIntegerResult #" << ResNo << ": ";
  49     N->dump(&DAG); dbgs() << "\n";
  50 #endif
  51     llvm_unreachable("Do not know how to promote this operator!");
  52   case ISD::MERGE_VALUES:Res = PromoteIntRes_MERGE_VALUES(N, ResNo); break;
  53   case ISD::AssertSext:  Res = PromoteIntRes_AssertSext(N); break;
  54   case ISD::AssertZext:  Res = PromoteIntRes_AssertZext(N); break;
  55   case ISD::BITCAST:     Res = PromoteIntRes_BITCAST(N); break;
  56   case ISD::BITREVERSE:  Res = PromoteIntRes_BITREVERSE(N); break;
  57   case ISD::BSWAP:       Res = PromoteIntRes_BSWAP(N); break;
  58   case ISD::BUILD_PAIR:  Res = PromoteIntRes_BUILD_PAIR(N); break;
  59   case ISD::Constant:    Res = PromoteIntRes_Constant(N); break;
  60   case ISD::CONVERT_RNDSAT:
  61                          Res = PromoteIntRes_CONVERT_RNDSAT(N); break;
  62   case ISD::CTLZ_ZERO_UNDEF:
  63   case ISD::CTLZ:        Res = PromoteIntRes_CTLZ(N); break;
  64   case ISD::CTPOP:       Res = PromoteIntRes_CTPOP(N); break;
  65   case ISD::CTTZ_ZERO_UNDEF:
  66   case ISD::CTTZ:        Res = PromoteIntRes_CTTZ(N); break;
  67   case ISD::EXTRACT_VECTOR_ELT:
  68                          Res = PromoteIntRes_EXTRACT_VECTOR_ELT(N); break;
  69   case ISD::LOAD:        Res = PromoteIntRes_LOAD(cast<LoadSDNode>(N)); break;
  70   case ISD::MLOAD:       Res = PromoteIntRes_MLOAD(cast<MaskedLoadSDNode>(N));
  71     break;
  72   case ISD::MGATHER:     Res = PromoteIntRes_MGATHER(cast<MaskedGatherSDNode>(N));
  73     break;
  74   case ISD::SELECT:      Res = PromoteIntRes_SELECT(N); break;
  75   case ISD::VSELECT:     Res = PromoteIntRes_VSELECT(N); break;
  76   case ISD::SELECT_CC:   Res = PromoteIntRes_SELECT_CC(N); break;
  77   case ISD::SETCC:       Res = PromoteIntRes_SETCC(N); break;
  78   case ISD::SMIN:
  79   case ISD::SMAX:        Res = PromoteIntRes_SExtIntBinOp(N); break;
  80   case ISD::UMIN:
  81   case ISD::UMAX:        Res = PromoteIntRes_ZExtIntBinOp(N); break;
  82
  83   case ISD::SHL:         Res = PromoteIntRes_SHL(N); break;
  84   case ISD::SIGN_EXTEND_INREG:
  85                          Res = PromoteIntRes_SIGN_EXTEND_INREG(N); break;
  86   case ISD::SRA:         Res = PromoteIntRes_SRA(N); break;
  87   case ISD::SRL:         Res = PromoteIntRes_SRL(N); break;
  88   case ISD::TRUNCATE:    Res = PromoteIntRes_TRUNCATE(N); break;
  89   case ISD::UNDEF:       Res = PromoteIntRes_UNDEF(N); break;
  90   case ISD::VAARG:       Res = PromoteIntRes_VAARG(N); break;
  91
  92   case ISD::EXTRACT_SUBVECTOR:
  93                          Res = PromoteIntRes_EXTRACT_SUBVECTOR(N); break;
  94   case ISD::VECTOR_SHUFFLE:
  95                          Res = PromoteIntRes_VECTOR_SHUFFLE(N); break;
  96   case ISD::INSERT_VECTOR_ELT:
  97                          Res = PromoteIntRes_INSERT_VECTOR_ELT(N); break;
  98   case ISD::BUILD_VECTOR:
  99                          Res = PromoteIntRes_BUILD_VECTOR(N); break;
 100   case ISD::SCALAR_TO_VECTOR:
 101                          Res = PromoteIntRes_SCALAR_TO_VECTOR(N); break;
 102   case ISD::CONCAT_VECTORS:
 103                          Res = PromoteIntRes_CONCAT_VECTORS(N); break;
 104
 105   case ISD::SIGN_EXTEND:
 106   case ISD::ZERO_EXTEND:
 107   case ISD::ANY_EXTEND:  Res = PromoteIntRes_INT_EXTEND(N); break;
 108
 109   case ISD::FP_TO_SINT:
 110   case ISD::FP_TO_UINT:  Res = PromoteIntRes_FP_TO_XINT(N); break;
 111
 112   case ISD::FP_TO_FP16:  Res = PromoteIntRes_FP_TO_FP16(N); break;
 113
 114   case ISD::AND:
 115   case ISD::OR:
 116   case ISD::XOR:
 117   case ISD::ADD:
 118   case ISD::SUB:
 119   case ISD::MUL:         Res = PromoteIntRes_SimpleIntBinOp(N); break;
 120
 121   case ISD::SDIV:
 122   case ISD::SREM:        Res = PromoteIntRes_SExtIntBinOp(N); break;
 123
 124   case ISD::UDIV:
 125   case ISD::UREM:        Res = PromoteIntRes_ZExtIntBinOp(N); break;
 126
 127   case ISD::SADDO:
 128   case ISD::SSUBO:       Res = PromoteIntRes_SADDSUBO(N, ResNo); break;
 129   case ISD::UADDO:
 130   case ISD::USUBO:       Res = PromoteIntRes_UADDSUBO(N, ResNo); break;
 131   case ISD::SMULO:
 132   case ISD::UMULO:       Res = PromoteIntRes_XMULO(N, ResNo); break;
 133
 134   case ISD::ATOMIC_LOAD:
 135     Res = PromoteIntRes_Atomic0(cast<AtomicSDNode>(N)); break;
 136
 137   case ISD::ATOMIC_LOAD_ADD:
 138   case ISD::ATOMIC_LOAD_SUB:
 139   case ISD::ATOMIC_LOAD_AND:
 140   case ISD::ATOMIC_LOAD_OR:
 141   case ISD::ATOMIC_LOAD_XOR:
 142   case ISD::ATOMIC_LOAD_NAND:
 143   case ISD::ATOMIC_LOAD_MIN:
 144   case ISD::ATOMIC_LOAD_MAX:
 145   case ISD::ATOMIC_LOAD_UMIN:
 146   case ISD::ATOMIC_LOAD_UMAX:
 147   case ISD::ATOMIC_SWAP:
 148     Res = PromoteIntRes_Atomic1(cast<AtomicSDNode>(N)); break;
 149
 150   case ISD::ATOMIC_CMP_SWAP:
 151   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
 152     Res = PromoteIntRes_AtomicCmpSwap(cast<AtomicSDNode>(N), ResNo);
 153     break;
 154   }
 155
 156   // If the result is null then the sub-method took care of registering it.
 157   if (Res.getNode())
 158     SetPromotedInteger(SDValue(N, ResNo), Res);
 159 }
 160
 161 SDValue DAGTypeLegalizer::PromoteIntRes_MERGE_VALUES(SDNode *N,
 162                                                      unsigned ResNo) {
 163   SDValue Op = DisintegrateMERGE_VALUES(N, ResNo);
 164   return GetPromotedInteger(Op);
 165 }
 166
 167 SDValue DAGTypeLegalizer::PromoteIntRes_AssertSext(SDNode *N) {
 168   // Sign-extend the new bits, and continue the assertion.
 169   SDValue Op = SExtPromotedInteger(N->getOperand(0));
 170   return DAG.getNode(ISD::AssertSext, SDLoc(N),
 171                      Op.getValueType(), Op, N->getOperand(1));
 172 }
 173
 174 SDValue DAGTypeLegalizer::PromoteIntRes_AssertZext(SDNode *N) {
 175   // Zero the new bits, and continue the assertion.
 176   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
 177   return DAG.getNode(ISD::AssertZext, SDLoc(N),
 178                      Op.getValueType(), Op, N->getOperand(1));
 179 }
 180
 181 SDValue DAGTypeLegalizer::PromoteIntRes_Atomic0(AtomicSDNode *N) {
 182   EVT ResVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 183   SDValue Res = DAG.getAtomic(N->getOpcode(), SDLoc(N),
 184                               N->getMemoryVT(), ResVT,
 185                               N->getChain(), N->getBasePtr(),
 186                               N->getMemOperand(), N->getOrdering(),
 187                               N->getSynchScope());
 188   // Legalize the chain result - switch anything that used the old chain to
 189   // use the new one.
 190   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 191   return Res;
 192 }
 193
 194 SDValue DAGTypeLegalizer::PromoteIntRes_Atomic1(AtomicSDNode *N) {
 195   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
 196   SDValue Res = DAG.getAtomic(N->getOpcode(), SDLoc(N),
 197                               N->getMemoryVT(),
 198                               N->getChain(), N->getBasePtr(),
 199                               Op2, N->getMemOperand(), N->getOrdering(),
 200                               N->getSynchScope());
 201   // Legalize the chain result - switch anything that used the old chain to
 202   // use the new one.
 203   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 204   return Res;
 205 }
 206
 207 SDValue DAGTypeLegalizer::PromoteIntRes_AtomicCmpSwap(AtomicSDNode *N,
 208                                                       unsigned ResNo) {
 209   if (ResNo == 1) {
 210     assert(N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
 211     EVT SVT = getSetCCResultType(N->getOperand(2).getValueType());
 212     EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(1));
 213
 214     // Only use the result of getSetCCResultType if it is legal,
 215     // otherwise just use the promoted result type (NVT).
 216     if (!TLI.isTypeLegal(SVT))
 217       SVT = NVT;
 218
 219     SDVTList VTs = DAG.getVTList(N->getValueType(0), SVT, MVT::Other);
 220     SDValue Res = DAG.getAtomicCmpSwap(
 221         ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS, SDLoc(N), N->getMemoryVT(), VTs,
 222         N->getChain(), N->getBasePtr(), N->getOperand(2), N->getOperand(3),
 223         N->getMemOperand(), N->getSuccessOrdering(), N->getFailureOrdering(),
 224         N->getSynchScope());
 225     ReplaceValueWith(SDValue(N, 0), Res.getValue(0));
 226     ReplaceValueWith(SDValue(N, 2), Res.getValue(2));
 227     return Res.getValue(1);
 228   }
 229
 230   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
 231   SDValue Op3 = GetPromotedInteger(N->getOperand(3));
 232   SDVTList VTs =
 233       DAG.getVTList(Op2.getValueType(), N->getValueType(1), MVT::Other);
 234   SDValue Res = DAG.getAtomicCmpSwap(
 235       N->getOpcode(), SDLoc(N), N->getMemoryVT(), VTs, N->getChain(),
 236       N->getBasePtr(), Op2, Op3, N->getMemOperand(), N->getSuccessOrdering(),
 237       N->getFailureOrdering(), N->getSynchScope());
 238   // Update the use to N with the newly created Res.
 239   for (unsigned i = 1, NumResults = N->getNumValues(); i < NumResults; ++i)
 240     ReplaceValueWith(SDValue(N, i), Res.getValue(i));
 241   return Res;
 242 }
 243
 244 SDValue DAGTypeLegalizer::PromoteIntRes_BITCAST(SDNode *N) {
 245   SDValue InOp = N->getOperand(0);
 246   EVT InVT = InOp.getValueType();
 247   EVT NInVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT);
 248   EVT OutVT = N->getValueType(0);
 249   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
 250   SDLoc dl(N);
 251
 252   switch (getTypeAction(InVT)) {
 253   case TargetLowering::TypeLegal:
 254     break;
 255   case TargetLowering::TypePromoteInteger:
 256     if (NOutVT.bitsEq(NInVT) && !NOutVT.isVector() && !NInVT.isVector())
 257       // The input promotes to the same size.  Convert the promoted value.
 258       return DAG.getNode(ISD::BITCAST, dl, NOutVT, GetPromotedInteger(InOp));
 259     break;
 260   case TargetLowering::TypeSoftenFloat:
 261     // Promote the integer operand by hand.
 262     return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT, GetSoftenedFloat(InOp));
 263   case TargetLowering::TypePromoteFloat: {
 264     // Convert the promoted float by hand.
 265     SDValue PromotedOp = GetPromotedFloat(InOp);
 266     return DAG.getNode(ISD::FP_TO_FP16, dl, NOutVT, PromotedOp);
 267     break;
 268   }
 269   case TargetLowering::TypeExpandInteger:
 270   case TargetLowering::TypeExpandFloat:
 271     break;
 272   case TargetLowering::TypeScalarizeVector:
 273     // Convert the element to an integer and promote it by hand.
 274     if (!NOutVT.isVector())
 275       return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT,
 276                          BitConvertToInteger(GetScalarizedVector(InOp)));
 277     break;
 278   case TargetLowering::TypeSplitVector: {
 279     // For example, i32 = BITCAST v2i16 on alpha.  Convert the split
 280     // pieces of the input into integers and reassemble in the final type.
 281     SDValue Lo, Hi;
 282     GetSplitVector(N->getOperand(0), Lo, Hi);
 283     Lo = BitConvertToInteger(Lo);
 284     Hi = BitConvertToInteger(Hi);
 285
 286     if (DAG.getDataLayout().isBigEndian())
 287       std::swap(Lo, Hi);
 288
 289     InOp = DAG.getNode(ISD::ANY_EXTEND, dl,
 290                        EVT::getIntegerVT(*DAG.getContext(),
 291                                          NOutVT.getSizeInBits()),
 292                        JoinIntegers(Lo, Hi));
 293     return DAG.getNode(ISD::BITCAST, dl, NOutVT, InOp);
 294   }
 295   case TargetLowering::TypeWidenVector:
 296     // The input is widened to the same size. Convert to the widened value.
 297     // Make sure that the outgoing value is not a vector, because this would
 298     // make us bitcast between two vectors which are legalized in different ways.
 299     if (NOutVT.bitsEq(NInVT) && !NOutVT.isVector())
 300       return DAG.getNode(ISD::BITCAST, dl, NOutVT, GetWidenedVector(InOp));
 301   }
 302
 303   return DAG.getNode(ISD::ANY_EXTEND, dl, NOutVT,
 304                      CreateStackStoreLoad(InOp, OutVT));
 305 }
 306
 307 SDValue DAGTypeLegalizer::PromoteIntRes_BSWAP(SDNode *N) {
 308   SDValue Op = GetPromotedInteger(N->getOperand(0));
 309   EVT OVT = N->getValueType(0);
 310   EVT NVT = Op.getValueType();
 311   SDLoc dl(N);
 312
 313   unsigned DiffBits = NVT.getScalarSizeInBits() - OVT.getScalarSizeInBits();
 314   return DAG.getNode(
 315       ISD::SRL, dl, NVT, DAG.getNode(ISD::BSWAP, dl, NVT, Op),
 316       DAG.getConstant(DiffBits, dl,
 317                       TLI.getShiftAmountTy(NVT, DAG.getDataLayout())));
 318 }
 319
 320 SDValue DAGTypeLegalizer::PromoteIntRes_BITREVERSE(SDNode *N) {
 321   SDValue Op = GetPromotedInteger(N->getOperand(0));
 322   EVT OVT = N->getValueType(0);
 323   EVT NVT = Op.getValueType();
 324   SDLoc dl(N);
 325
 326   unsigned DiffBits = NVT.getScalarSizeInBits() - OVT.getScalarSizeInBits();
 327   return DAG.getNode(
 328       ISD::SRL, dl, NVT, DAG.getNode(ISD::BITREVERSE, dl, NVT, Op),
 329       DAG.getConstant(DiffBits, dl,
 330                       TLI.getShiftAmountTy(NVT, DAG.getDataLayout())));
 331 }
 332
 333 SDValue DAGTypeLegalizer::PromoteIntRes_BUILD_PAIR(SDNode *N) {
 334   // The pair element type may be legal, or may not promote to the same type as
 335   // the result, for example i14 = BUILD_PAIR (i7, i7).  Handle all cases.
 336   return DAG.getNode(ISD::ANY_EXTEND, SDLoc(N),
 337                      TLI.getTypeToTransformTo(*DAG.getContext(),
 338                      N->getValueType(0)), JoinIntegers(N->getOperand(0),
 339                      N->getOperand(1)));
 340 }
 341
 342 SDValue DAGTypeLegalizer::PromoteIntRes_Constant(SDNode *N) {
 343   EVT VT = N->getValueType(0);
 344   // FIXME there is no actual debug info here
 345   SDLoc dl(N);
 346   // Zero extend things like i1, sign extend everything else.  It shouldn't
 347   // matter in theory which one we pick, but this tends to give better code?
 348   unsigned Opc = VT.isByteSized() ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
 349   SDValue Result = DAG.getNode(Opc, dl,
 350                                TLI.getTypeToTransformTo(*DAG.getContext(), VT),
 351                                SDValue(N, 0));
 352   assert(isa<ConstantSDNode>(Result) && "Didn't constant fold ext?");
 353   return Result;
 354 }
 355
 356 SDValue DAGTypeLegalizer::PromoteIntRes_CONVERT_RNDSAT(SDNode *N) {
 357   ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
 358   assert ((CvtCode == ISD::CVT_SS || CvtCode == ISD::CVT_SU ||
 359            CvtCode == ISD::CVT_US || CvtCode == ISD::CVT_UU ||
 360            CvtCode == ISD::CVT_SF || CvtCode == ISD::CVT_UF) &&
 361           "can only promote integers");
 362   EVT OutVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 363   return DAG.getConvertRndSat(OutVT, SDLoc(N), N->getOperand(0),
 364                               N->getOperand(1), N->getOperand(2),
 365                               N->getOperand(3), N->getOperand(4), CvtCode);
 366 }
 367
 368 SDValue DAGTypeLegalizer::PromoteIntRes_CTLZ(SDNode *N) {
 369   // Zero extend to the promoted type and do the count there.
 370   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
 371   SDLoc dl(N);
 372   EVT OVT = N->getValueType(0);
 373   EVT NVT = Op.getValueType();
 374   Op = DAG.getNode(N->getOpcode(), dl, NVT, Op);
 375   // Subtract off the extra leading bits in the bigger type.
 376   return DAG.getNode(
 377       ISD::SUB, dl, NVT, Op,
 378       DAG.getConstant(NVT.getScalarSizeInBits() - OVT.getScalarSizeInBits(), dl,
 379                       NVT));
 380 }
 381
 382 SDValue DAGTypeLegalizer::PromoteIntRes_CTPOP(SDNode *N) {
 383   // Zero extend to the promoted type and do the count there.
 384   SDValue Op = ZExtPromotedInteger(N->getOperand(0));
 385   return DAG.getNode(ISD::CTPOP, SDLoc(N), Op.getValueType(), Op);
 386 }
 387
 388 SDValue DAGTypeLegalizer::PromoteIntRes_CTTZ(SDNode *N) {
 389   SDValue Op = GetPromotedInteger(N->getOperand(0));
 390   EVT OVT = N->getValueType(0);
 391   EVT NVT = Op.getValueType();
 392   SDLoc dl(N);
 393   if (N->getOpcode() == ISD::CTTZ) {
 394     // The count is the same in the promoted type except if the original
 395     // value was zero.  This can be handled by setting the bit just off
 396     // the top of the original type.
 397     auto TopBit = APInt::getOneBitSet(NVT.getScalarSizeInBits(),
 398                                       OVT.getScalarSizeInBits());
 399     Op = DAG.getNode(ISD::OR, dl, NVT, Op, DAG.getConstant(TopBit, dl, NVT));
 400   }
 401   return DAG.getNode(N->getOpcode(), dl, NVT, Op);
 402 }
 403
 404 SDValue DAGTypeLegalizer::PromoteIntRes_EXTRACT_VECTOR_ELT(SDNode *N) {
 405   SDLoc dl(N);
 406   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 407   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, NVT, N->getOperand(0),
 408                      N->getOperand(1));
 409 }
 410
 411 SDValue DAGTypeLegalizer::PromoteIntRes_FP_TO_XINT(SDNode *N) {
 412   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 413   unsigned NewOpc = N->getOpcode();
 414   SDLoc dl(N);
 415
 416   // If we're promoting a UINT to a larger size and the larger FP_TO_UINT is
 417   // not Legal, check to see if we can use FP_TO_SINT instead.  (If both UINT
 418   // and SINT conversions are Custom, there is no way to tell which is
 419   // preferable. We choose SINT because that's the right thing on PPC.)
 420   if (N->getOpcode() == ISD::FP_TO_UINT &&
 421       !TLI.isOperationLegal(ISD::FP_TO_UINT, NVT) &&
 422       TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NVT))
 423     NewOpc = ISD::FP_TO_SINT;
 424
 425   SDValue Res = DAG.getNode(NewOpc, dl, NVT, N->getOperand(0));
 426
 427   // Assert that the converted value fits in the original type.  If it doesn't
 428   // (eg: because the value being converted is too big), then the result of the
 429   // original operation was undefined anyway, so the assert is still correct.
 430   return DAG.getNode(N->getOpcode() == ISD::FP_TO_UINT ?
 431                      ISD::AssertZext : ISD::AssertSext, dl, NVT, Res,
 432                      DAG.getValueType(N->getValueType(0).getScalarType()));
 433 }
 434
 435 SDValue DAGTypeLegalizer::PromoteIntRes_FP_TO_FP16(SDNode *N) {
 436   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 437   SDLoc dl(N);
 438
 439   return DAG.getNode(N->getOpcode(), dl, NVT, N->getOperand(0));
 440 }
 441
 442 SDValue DAGTypeLegalizer::PromoteIntRes_INT_EXTEND(SDNode *N) {
 443   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 444   SDLoc dl(N);
 445
 446   if (getTypeAction(N->getOperand(0).getValueType())
 447       == TargetLowering::TypePromoteInteger) {
 448     SDValue Res = GetPromotedInteger(N->getOperand(0));
 449     assert(Res.getValueType().bitsLE(NVT) && "Extension doesn't make sense!");
 450
 451     // If the result and operand types are the same after promotion, simplify
 452     // to an in-register extension.
 453     if (NVT == Res.getValueType()) {
 454       // The high bits are not guaranteed to be anything.  Insert an extend.
 455       if (N->getOpcode() == ISD::SIGN_EXTEND)
 456         return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NVT, Res,
 457                            DAG.getValueType(N->getOperand(0).getValueType()));
 458       if (N->getOpcode() == ISD::ZERO_EXTEND)
 459         return DAG.getZeroExtendInReg(Res, dl,
 460                       N->getOperand(0).getValueType().getScalarType());
 461       assert(N->getOpcode() == ISD::ANY_EXTEND && "Unknown integer extension!");
 462       return Res;
 463     }
 464   }
 465
 466   // Otherwise, just extend the original operand all the way to the larger type.
 467   return DAG.getNode(N->getOpcode(), dl, NVT, N->getOperand(0));
 468 }
 469
 470 SDValue DAGTypeLegalizer::PromoteIntRes_LOAD(LoadSDNode *N) {
 471   assert(ISD::isUNINDEXEDLoad(N) && "Indexed load during type legalization!");
 472   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 473   ISD::LoadExtType ExtType =
 474     ISD::isNON_EXTLoad(N) ? ISD::EXTLOAD : N->getExtensionType();
 475   SDLoc dl(N);
 476   SDValue Res = DAG.getExtLoad(ExtType, dl, NVT, N->getChain(), N->getBasePtr(),
 477                                N->getMemoryVT(), N->getMemOperand());
 478
 479   // Legalize the chain result - switch anything that used the old chain to
 480   // use the new one.
 481   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 482   return Res;
 483 }
 484
 485 SDValue DAGTypeLegalizer::PromoteIntRes_MLOAD(MaskedLoadSDNode *N) {
 486   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 487   SDValue ExtSrc0 = GetPromotedInteger(N->getSrc0());
 488
 489   SDLoc dl(N);
 490   SDValue Res = DAG.getMaskedLoad(NVT, dl, N->getChain(), N->getBasePtr(),
 491                                   N->getMask(), ExtSrc0, N->getMemoryVT(),
 492                                   N->getMemOperand(), ISD::SEXTLOAD);
 493   // Legalize the chain result - switch anything that used the old chain to
 494   // use the new one.
 495   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 496   return Res;
 497 }
 498
 499 SDValue DAGTypeLegalizer::PromoteIntRes_MGATHER(MaskedGatherSDNode *N) {
 500   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 501   SDValue ExtSrc0 = GetPromotedInteger(N->getValue());
 502   assert(NVT == ExtSrc0.getValueType() &&
 503       "Gather result type and the passThru agrument type should be the same");
 504
 505   SDLoc dl(N);
 506   SDValue Ops[] = {N->getChain(), ExtSrc0, N->getMask(), N->getBasePtr(),
 507                    N->getIndex()};
 508   SDValue Res = DAG.getMaskedGather(DAG.getVTList(NVT, MVT::Other),
 509                                     N->getMemoryVT(), dl, Ops,
 510                                     N->getMemOperand());
 511   // Legalize the chain result - switch anything that used the old chain to
 512   // use the new one.
 513   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 514   return Res;
 515 }
 516
 517 /// Promote the overflow flag of an overflowing arithmetic node.
 518 SDValue DAGTypeLegalizer::PromoteIntRes_Overflow(SDNode *N) {
 519   // Simply change the return type of the boolean result.
 520   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(1));
 521   EVT ValueVTs[] = { N->getValueType(0), NVT };
 522   SDValue Ops[] = { N->getOperand(0), N->getOperand(1) };
 523   SDValue Res = DAG.getNode(N->getOpcode(), SDLoc(N),
 524                             DAG.getVTList(ValueVTs), Ops);
 525
 526   // Modified the sum result - switch anything that used the old sum to use
 527   // the new one.
 528   ReplaceValueWith(SDValue(N, 0), Res);
 529
 530   return SDValue(Res.getNode(), 1);
 531 }
 532
 533 SDValue DAGTypeLegalizer::PromoteIntRes_SADDSUBO(SDNode *N, unsigned ResNo) {
 534   if (ResNo == 1)
 535     return PromoteIntRes_Overflow(N);
 536
 537   // The operation overflowed iff the result in the larger type is not the
 538   // sign extension of its truncation to the original type.
 539   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
 540   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
 541   EVT OVT = N->getOperand(0).getValueType();
 542   EVT NVT = LHS.getValueType();
 543   SDLoc dl(N);
 544
 545   // Do the arithmetic in the larger type.
 546   unsigned Opcode = N->getOpcode() == ISD::SADDO ? ISD::ADD : ISD::SUB;
 547   SDValue Res = DAG.getNode(Opcode, dl, NVT, LHS, RHS);
 548
 549   // Calculate the overflow flag: sign extend the arithmetic result from
 550   // the original type.
 551   SDValue Ofl = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NVT, Res,
 552                             DAG.getValueType(OVT));
 553   // Overflowed if and only if this is not equal to Res.
 554   Ofl = DAG.getSetCC(dl, N->getValueType(1), Ofl, Res, ISD::SETNE);
 555
 556   // Use the calculated overflow everywhere.
 557   ReplaceValueWith(SDValue(N, 1), Ofl);
 558
 559   return Res;
 560 }
 561
 562 SDValue DAGTypeLegalizer::PromoteIntRes_SELECT(SDNode *N) {
 563   SDValue LHS = GetPromotedInteger(N->getOperand(1));
 564   SDValue RHS = GetPromotedInteger(N->getOperand(2));
 565   return DAG.getSelect(SDLoc(N),
 566                        LHS.getValueType(), N->getOperand(0), LHS, RHS);
 567 }
 568
 569 SDValue DAGTypeLegalizer::PromoteIntRes_VSELECT(SDNode *N) {
 570   SDValue Mask = N->getOperand(0);
 571   EVT OpTy = N->getOperand(1).getValueType();
 572
 573   // Promote all the way up to the canonical SetCC type.
 574   Mask = PromoteTargetBoolean(Mask, OpTy);
 575   SDValue LHS = GetPromotedInteger(N->getOperand(1));
 576   SDValue RHS = GetPromotedInteger(N->getOperand(2));
 577   return DAG.getNode(ISD::VSELECT, SDLoc(N),
 578                      LHS.getValueType(), Mask, LHS, RHS);
 579 }
 580
 581 SDValue DAGTypeLegalizer::PromoteIntRes_SELECT_CC(SDNode *N) {
 582   SDValue LHS = GetPromotedInteger(N->getOperand(2));
 583   SDValue RHS = GetPromotedInteger(N->getOperand(3));
 584   return DAG.getNode(ISD::SELECT_CC, SDLoc(N),
 585                      LHS.getValueType(), N->getOperand(0),
 586                      N->getOperand(1), LHS, RHS, N->getOperand(4));
 587 }
 588
 589 SDValue DAGTypeLegalizer::PromoteIntRes_SETCC(SDNode *N) {
 590   EVT SVT = getSetCCResultType(N->getOperand(0).getValueType());
 591
 592   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 593
 594   // Only use the result of getSetCCResultType if it is legal,
 595   // otherwise just use the promoted result type (NVT).
 596   if (!TLI.isTypeLegal(SVT))
 597     SVT = NVT;
 598
 599   SDLoc dl(N);
 600   assert(SVT.isVector() == N->getOperand(0).getValueType().isVector() &&
 601          "Vector compare must return a vector result!");
 602
 603   SDValue LHS = N->getOperand(0);
 604   SDValue RHS = N->getOperand(1);
 605   if (LHS.getValueType() != RHS.getValueType()) {
 606     if (getTypeAction(LHS.getValueType()) == TargetLowering::TypePromoteInteger &&
 607         !LHS.getValueType().isVector())
 608       LHS = GetPromotedInteger(LHS);
 609     if (getTypeAction(RHS.getValueType()) == TargetLowering::TypePromoteInteger &&
 610         !RHS.getValueType().isVector())
 611       RHS = GetPromotedInteger(RHS);
 612   }
 613
 614   // Get the SETCC result using the canonical SETCC type.
 615   SDValue SetCC = DAG.getNode(N->getOpcode(), dl, SVT, LHS, RHS,
 616                               N->getOperand(2));
 617
 618   assert(NVT.bitsLE(SVT) && "Integer type overpromoted?");
 619   // Convert to the expected type.
 620   return DAG.getNode(ISD::TRUNCATE, dl, NVT, SetCC);
 621 }
 622
 623 SDValue DAGTypeLegalizer::PromoteIntRes_SHL(SDNode *N) {
 624   SDValue LHS = N->getOperand(0);
 625   SDValue RHS = N->getOperand(1);
 626   if (getTypeAction(LHS.getValueType()) == TargetLowering::TypePromoteInteger)
 627     LHS = GetPromotedInteger(LHS);
 628   if (getTypeAction(RHS.getValueType()) == TargetLowering::TypePromoteInteger)
 629     RHS = ZExtPromotedInteger(RHS);
 630   return DAG.getNode(ISD::SHL, SDLoc(N), LHS.getValueType(), LHS, RHS);
 631 }
 632
 633 SDValue DAGTypeLegalizer::PromoteIntRes_SIGN_EXTEND_INREG(SDNode *N) {
 634   SDValue Op = GetPromotedInteger(N->getOperand(0));
 635   return DAG.getNode(ISD::SIGN_EXTEND_INREG, SDLoc(N),
 636                      Op.getValueType(), Op, N->getOperand(1));
 637 }
 638
 639 SDValue DAGTypeLegalizer::PromoteIntRes_SimpleIntBinOp(SDNode *N) {
 640   // The input may have strange things in the top bits of the registers, but
 641   // these operations don't care.  They may have weird bits going out, but
 642   // that too is okay if they are integer operations.
 643   SDValue LHS = GetPromotedInteger(N->getOperand(0));
 644   SDValue RHS = GetPromotedInteger(N->getOperand(1));
 645   return DAG.getNode(N->getOpcode(), SDLoc(N),
 646                      LHS.getValueType(), LHS, RHS);
 647 }
 648
 649 SDValue DAGTypeLegalizer::PromoteIntRes_SExtIntBinOp(SDNode *N) {
 650   // Sign extend the input.
 651   SDValue LHS = SExtPromotedInteger(N->getOperand(0));
 652   SDValue RHS = SExtPromotedInteger(N->getOperand(1));
 653   return DAG.getNode(N->getOpcode(), SDLoc(N),
 654                      LHS.getValueType(), LHS, RHS);
 655 }
 656
 657 SDValue DAGTypeLegalizer::PromoteIntRes_ZExtIntBinOp(SDNode *N) {
 658   // Zero extend the input.
 659   SDValue LHS = ZExtPromotedInteger(N->getOperand(0));
 660   SDValue RHS = ZExtPromotedInteger(N->getOperand(1));
 661   return DAG.getNode(N->getOpcode(), SDLoc(N),
 662                      LHS.getValueType(), LHS, RHS);
 663 }
 664
 665 SDValue DAGTypeLegalizer::PromoteIntRes_SRA(SDNode *N) {
 666   SDValue LHS = N->getOperand(0);
 667   SDValue RHS = N->getOperand(1);
 668   // The input value must be properly sign extended.
 669   if (getTypeAction(LHS.getValueType()) == TargetLowering::TypePromoteInteger)
 670     LHS = SExtPromotedInteger(LHS);
 671   if (getTypeAction(RHS.getValueType()) == TargetLowering::TypePromoteInteger)
 672     RHS = ZExtPromotedInteger(RHS);
 673   return DAG.getNode(ISD::SRA, SDLoc(N), LHS.getValueType(), LHS, RHS);
 674 }
 675
 676 SDValue DAGTypeLegalizer::PromoteIntRes_SRL(SDNode *N) {
 677   SDValue LHS = N->getOperand(0);
 678   SDValue RHS = N->getOperand(1);
 679   // The input value must be properly zero extended.
 680   if (getTypeAction(LHS.getValueType()) == TargetLowering::TypePromoteInteger)
 681     LHS = ZExtPromotedInteger(LHS);
 682   if (getTypeAction(RHS.getValueType()) == TargetLowering::TypePromoteInteger)
 683     RHS = ZExtPromotedInteger(RHS);
 684   return DAG.getNode(ISD::SRL, SDLoc(N), LHS.getValueType(), LHS, RHS);
 685 }
 686
 687 SDValue DAGTypeLegalizer::PromoteIntRes_TRUNCATE(SDNode *N) {
 688   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 689   SDValue Res;
 690   SDValue InOp = N->getOperand(0);
 691   SDLoc dl(N);
 692
 693   switch (getTypeAction(InOp.getValueType())) {
 694   default: llvm_unreachable("Unknown type action!");
 695   case TargetLowering::TypeLegal:
 696   case TargetLowering::TypeExpandInteger:
 697     Res = InOp;
 698     break;
 699   case TargetLowering::TypePromoteInteger:
 700     Res = GetPromotedInteger(InOp);
 701     break;
 702   case TargetLowering::TypeSplitVector:
 703     EVT InVT = InOp.getValueType();
 704     assert(InVT.isVector() && "Cannot split scalar types");
 705     unsigned NumElts = InVT.getVectorNumElements();
 706     assert(NumElts == NVT.getVectorNumElements() &&
 707            "Dst and Src must have the same number of elements");
 708     assert(isPowerOf2_32(NumElts) &&
 709            "Promoted vector type must be a power of two");
 710
 711     SDValue EOp1, EOp2;
 712     GetSplitVector(InOp, EOp1, EOp2);
 713
 714     EVT HalfNVT = EVT::getVectorVT(*DAG.getContext(), NVT.getScalarType(),
 715                                    NumElts/2);
 716     EOp1 = DAG.getNode(ISD::TRUNCATE, dl, HalfNVT, EOp1);
 717     EOp2 = DAG.getNode(ISD::TRUNCATE, dl, HalfNVT, EOp2);
 718
 719     return DAG.getNode(ISD::CONCAT_VECTORS, dl, NVT, EOp1, EOp2);
 720   }
 721
 722   // Truncate to NVT instead of VT
 723   return DAG.getNode(ISD::TRUNCATE, dl, NVT, Res);
 724 }
 725
 726 SDValue DAGTypeLegalizer::PromoteIntRes_UADDSUBO(SDNode *N, unsigned ResNo) {
 727   if (ResNo == 1)
 728     return PromoteIntRes_Overflow(N);
 729
 730   // The operation overflowed iff the result in the larger type is not the
 731   // zero extension of its truncation to the original type.
 732   SDValue LHS = ZExtPromotedInteger(N->getOperand(0));
 733   SDValue RHS = ZExtPromotedInteger(N->getOperand(1));
 734   EVT OVT = N->getOperand(0).getValueType();
 735   EVT NVT = LHS.getValueType();
 736   SDLoc dl(N);
 737
 738   // Do the arithmetic in the larger type.
 739   unsigned Opcode = N->getOpcode() == ISD::UADDO ? ISD::ADD : ISD::SUB;
 740   SDValue Res = DAG.getNode(Opcode, dl, NVT, LHS, RHS);
 741
 742   // Calculate the overflow flag: zero extend the arithmetic result from
 743   // the original type.
 744   SDValue Ofl = DAG.getZeroExtendInReg(Res, dl, OVT);
 745   // Overflowed if and only if this is not equal to Res.
 746   Ofl = DAG.getSetCC(dl, N->getValueType(1), Ofl, Res, ISD::SETNE);
 747
 748   // Use the calculated overflow everywhere.
 749   ReplaceValueWith(SDValue(N, 1), Ofl);
 750
 751   return Res;
 752 }
 753
 754 SDValue DAGTypeLegalizer::PromoteIntRes_XMULO(SDNode *N, unsigned ResNo) {
 755   // Promote the overflow bit trivially.
 756   if (ResNo == 1)
 757     return PromoteIntRes_Overflow(N);
 758
 759   SDValue LHS = N->getOperand(0), RHS = N->getOperand(1);
 760   SDLoc DL(N);
 761   EVT SmallVT = LHS.getValueType();
 762
 763   // To determine if the result overflowed in a larger type, we extend the
 764   // input to the larger type, do the multiply (checking if it overflows),
 765   // then also check the high bits of the result to see if overflow happened
 766   // there.
 767   if (N->getOpcode() == ISD::SMULO) {
 768     LHS = SExtPromotedInteger(LHS);
 769     RHS = SExtPromotedInteger(RHS);
 770   } else {
 771     LHS = ZExtPromotedInteger(LHS);
 772     RHS = ZExtPromotedInteger(RHS);
 773   }
 774   SDVTList VTs = DAG.getVTList(LHS.getValueType(), N->getValueType(1));
 775   SDValue Mul = DAG.getNode(N->getOpcode(), DL, VTs, LHS, RHS);
 776
 777   // Overflow occurred if it occurred in the larger type, or if the high part
 778   // of the result does not zero/sign-extend the low part.  Check this second
 779   // possibility first.
 780   SDValue Overflow;
 781   if (N->getOpcode() == ISD::UMULO) {
 782     // Unsigned overflow occurred if the high part is non-zero.
 783     SDValue Hi = DAG.getNode(ISD::SRL, DL, Mul.getValueType(), Mul,
 784                              DAG.getIntPtrConstant(SmallVT.getSizeInBits(),
 785                                                    DL));
 786     Overflow = DAG.getSetCC(DL, N->getValueType(1), Hi,
 787                             DAG.getConstant(0, DL, Hi.getValueType()),
 788                             ISD::SETNE);
 789   } else {
 790     // Signed overflow occurred if the high part does not sign extend the low.
 791     SDValue SExt = DAG.getNode(ISD::SIGN_EXTEND_INREG, DL, Mul.getValueType(),
 792                                Mul, DAG.getValueType(SmallVT));
 793     Overflow = DAG.getSetCC(DL, N->getValueType(1), SExt, Mul, ISD::SETNE);
 794   }
 795
 796   // The only other way for overflow to occur is if the multiplication in the
 797   // larger type itself overflowed.
 798   Overflow = DAG.getNode(ISD::OR, DL, N->getValueType(1), Overflow,
 799                          SDValue(Mul.getNode(), 1));
 800
 801   // Use the calculated overflow everywhere.
 802   ReplaceValueWith(SDValue(N, 1), Overflow);
 803   return Mul;
 804 }
 805
 806 SDValue DAGTypeLegalizer::PromoteIntRes_UNDEF(SDNode *N) {
 807   return DAG.getUNDEF(TLI.getTypeToTransformTo(*DAG.getContext(),
 808                                                N->getValueType(0)));
 809 }
 810
 811 SDValue DAGTypeLegalizer::PromoteIntRes_VAARG(SDNode *N) {
 812   SDValue Chain = N->getOperand(0); // Get the chain.
 813   SDValue Ptr = N->getOperand(1); // Get the pointer.
 814   EVT VT = N->getValueType(0);
 815   SDLoc dl(N);
 816
 817   MVT RegVT = TLI.getRegisterType(*DAG.getContext(), VT);
 818   unsigned NumRegs = TLI.getNumRegisters(*DAG.getContext(), VT);
 819   // The argument is passed as NumRegs registers of type RegVT.
 820
 821   SmallVector<SDValue, 8> Parts(NumRegs);
 822   for (unsigned i = 0; i < NumRegs; ++i) {
 823     Parts[i] = DAG.getVAArg(RegVT, dl, Chain, Ptr, N->getOperand(2),
 824                             N->getConstantOperandVal(3));
 825     Chain = Parts[i].getValue(1);
 826   }
 827
 828   // Handle endianness of the load.
 829   if (DAG.getDataLayout().isBigEndian())
 830     std::reverse(Parts.begin(), Parts.end());
 831
 832   // Assemble the parts in the promoted type.
 833   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
 834   SDValue Res = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Parts[0]);
 835   for (unsigned i = 1; i < NumRegs; ++i) {
 836     SDValue Part = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Parts[i]);
 837     // Shift it to the right position and "or" it in.
 838     Part = DAG.getNode(ISD::SHL, dl, NVT, Part,
 839                        DAG.getConstant(i * RegVT.getSizeInBits(), dl,
 840                                        TLI.getPointerTy(DAG.getDataLayout())));
 841     Res = DAG.getNode(ISD::OR, dl, NVT, Res, Part);
 842   }
 843
 844   // Modified the chain result - switch anything that used the old chain to
 845   // use the new one.
 846   ReplaceValueWith(SDValue(N, 1), Chain);
 847
 848   return Res;
 849 }
 850
 851 //===----------------------------------------------------------------------===//
 852 //  Integer Operand Promotion
 853 //===----------------------------------------------------------------------===//
 854
 855 /// PromoteIntegerOperand - This method is called when the specified operand of
 856 /// the specified node is found to need promotion.  At this point, all of the
 857 /// result types of the node are known to be legal, but other operands of the
 858 /// node may need promotion or expansion as well as the specified one.
 859 bool DAGTypeLegalizer::PromoteIntegerOperand(SDNode *N, unsigned OpNo) {
 860   DEBUG(dbgs() << "Promote integer operand: "; N->dump(&DAG); dbgs() << "\n");
 861   SDValue Res = SDValue();
 862
 863   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
 864     return false;
 865
 866   switch (N->getOpcode()) {
 867     default:
 868   #ifndef NDEBUG
 869     dbgs() << "PromoteIntegerOperand Op #" << OpNo << ": ";
 870     N->dump(&DAG); dbgs() << "\n";
 871   #endif
 872     llvm_unreachable("Do not know how to promote this operator's operand!");
 873
 874   case ISD::ANY_EXTEND:   Res = PromoteIntOp_ANY_EXTEND(N); break;
 875   case ISD::ATOMIC_STORE:
 876     Res = PromoteIntOp_ATOMIC_STORE(cast<AtomicSDNode>(N));
 877     break;
 878   case ISD::BITCAST:      Res = PromoteIntOp_BITCAST(N); break;
 879   case ISD::BR_CC:        Res = PromoteIntOp_BR_CC(N, OpNo); break;
 880   case ISD::BRCOND:       Res = PromoteIntOp_BRCOND(N, OpNo); break;
 881   case ISD::BUILD_PAIR:   Res = PromoteIntOp_BUILD_PAIR(N); break;
 882   case ISD::BUILD_VECTOR: Res = PromoteIntOp_BUILD_VECTOR(N); break;
 883   case ISD::CONCAT_VECTORS: Res = PromoteIntOp_CONCAT_VECTORS(N); break;
 884   case ISD::EXTRACT_VECTOR_ELT: Res = PromoteIntOp_EXTRACT_VECTOR_ELT(N); break;
 885   case ISD::CONVERT_RNDSAT:
 886                           Res = PromoteIntOp_CONVERT_RNDSAT(N); break;
 887   case ISD::INSERT_VECTOR_ELT:
 888                           Res = PromoteIntOp_INSERT_VECTOR_ELT(N, OpNo);break;
 889   case ISD::SCALAR_TO_VECTOR:
 890                           Res = PromoteIntOp_SCALAR_TO_VECTOR(N); break;
 891   case ISD::VSELECT:
 892   case ISD::SELECT:       Res = PromoteIntOp_SELECT(N, OpNo); break;
 893   case ISD::SELECT_CC:    Res = PromoteIntOp_SELECT_CC(N, OpNo); break;
 894   case ISD::SETCC:        Res = PromoteIntOp_SETCC(N, OpNo); break;
 895   case ISD::SIGN_EXTEND:  Res = PromoteIntOp_SIGN_EXTEND(N); break;
 896   case ISD::SINT_TO_FP:   Res = PromoteIntOp_SINT_TO_FP(N); break;
 897   case ISD::STORE:        Res = PromoteIntOp_STORE(cast<StoreSDNode>(N),
 898                                                    OpNo); break;
 899   case ISD::MSTORE:       Res = PromoteIntOp_MSTORE(cast<MaskedStoreSDNode>(N),
 900                                                     OpNo); break;
 901   case ISD::MLOAD:        Res = PromoteIntOp_MLOAD(cast<MaskedLoadSDNode>(N),
 902                                                     OpNo); break;
 903   case ISD::MGATHER:  Res = PromoteIntOp_MGATHER(cast<MaskedGatherSDNode>(N),
 904                                                  OpNo); break;
 905   case ISD::MSCATTER: Res = PromoteIntOp_MSCATTER(cast<MaskedScatterSDNode>(N),
 906                                                   OpNo); break;
 907   case ISD::TRUNCATE:     Res = PromoteIntOp_TRUNCATE(N); break;
 908   case ISD::FP16_TO_FP:
 909   case ISD::UINT_TO_FP:   Res = PromoteIntOp_UINT_TO_FP(N); break;
 910   case ISD::ZERO_EXTEND:  Res = PromoteIntOp_ZERO_EXTEND(N); break;
 911   case ISD::EXTRACT_SUBVECTOR: Res = PromoteIntOp_EXTRACT_SUBVECTOR(N); break;
 912
 913   case ISD::SHL:
 914   case ISD::SRA:
 915   case ISD::SRL:
 916   case ISD::ROTL:
 917   case ISD::ROTR: Res = PromoteIntOp_Shift(N); break;
 918   }
 919
 920   // If the result is null, the sub-method took care of registering results etc.
 921   if (!Res.getNode()) return false;
 922
 923   // If the result is N, the sub-method updated N in place.  Tell the legalizer
 924   // core about this.
 925   if (Res.getNode() == N)
 926     return true;
 927
 928   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
 929          "Invalid operand expansion");
 930
 931   ReplaceValueWith(SDValue(N, 0), Res);
 932   return false;
 933 }
 934
 935 /// PromoteSetCCOperands - Promote the operands of a comparison.  This code is
 936 /// shared among BR_CC, SELECT_CC, and SETCC handlers.
 937 void DAGTypeLegalizer::PromoteSetCCOperands(SDValue &NewLHS,SDValue &NewRHS,
 938                                             ISD::CondCode CCCode) {
 939   // We have to insert explicit sign or zero extends.  Note that we could
 940   // insert sign extends for ALL conditions, but zero extend is cheaper on
 941   // many machines (an AND instead of two shifts), so prefer it.
 942   switch (CCCode) {
 943   default: llvm_unreachable("Unknown integer comparison!");
 944   case ISD::SETEQ:
 945   case ISD::SETNE: {
 946     SDValue OpL = GetPromotedInteger(NewLHS);
 947     SDValue OpR = GetPromotedInteger(NewRHS);
 948
 949     // We would prefer to promote the comparison operand with sign extension,
 950     // if we find the operand is actually to truncate an AssertSext. With this
 951     // optimization, we can avoid inserting real truncate instruction, which
 952     // is redudant eventually.
 953     if (OpL->getOpcode() == ISD::AssertSext &&
 954         cast<VTSDNode>(OpL->getOperand(1))->getVT() == NewLHS.getValueType() &&
 955         OpR->getOpcode() == ISD::AssertSext &&
 956         cast<VTSDNode>(OpR->getOperand(1))->getVT() == NewRHS.getValueType()) {
 957       NewLHS = OpL;
 958       NewRHS = OpR;
 959     } else {
 960       NewLHS = ZExtPromotedInteger(NewLHS);
 961       NewRHS = ZExtPromotedInteger(NewRHS);
 962     }
 963     break;
 964   }
 965   case ISD::SETUGE:
 966   case ISD::SETUGT:
 967   case ISD::SETULE:
 968   case ISD::SETULT:
 969     // ALL of these operations will work if we either sign or zero extend
 970     // the operands (including the unsigned comparisons!).  Zero extend is
 971     // usually a simpler/cheaper operation, so prefer it.
 972     NewLHS = ZExtPromotedInteger(NewLHS);
 973     NewRHS = ZExtPromotedInteger(NewRHS);
 974     break;
 975   case ISD::SETGE:
 976   case ISD::SETGT:
 977   case ISD::SETLT:
 978   case ISD::SETLE:
 979     NewLHS = SExtPromotedInteger(NewLHS);
 980     NewRHS = SExtPromotedInteger(NewRHS);
 981     break;
 982   }
 983 }
 984
 985 SDValue DAGTypeLegalizer::PromoteIntOp_ANY_EXTEND(SDNode *N) {
 986   SDValue Op = GetPromotedInteger(N->getOperand(0));
 987   return DAG.getNode(ISD::ANY_EXTEND, SDLoc(N), N->getValueType(0), Op);
 988 }
 989
 990 SDValue DAGTypeLegalizer::PromoteIntOp_ATOMIC_STORE(AtomicSDNode *N) {
 991   SDValue Op2 = GetPromotedInteger(N->getOperand(2));
 992   return DAG.getAtomic(N->getOpcode(), SDLoc(N), N->getMemoryVT(),
 993                        N->getChain(), N->getBasePtr(), Op2, N->getMemOperand(),
 994                        N->getOrdering(), N->getSynchScope());
 995 }
 996
 997 SDValue DAGTypeLegalizer::PromoteIntOp_BITCAST(SDNode *N) {
 998   // This should only occur in unusual situations like bitcasting to an
 999   // x86_fp80, so just turn it into a store+load
1000   return CreateStackStoreLoad(N->getOperand(0), N->getValueType(0));
1001 }
1002
1003 SDValue DAGTypeLegalizer::PromoteIntOp_BR_CC(SDNode *N, unsigned OpNo) {
1004   assert(OpNo == 2 && "Don't know how to promote this operand!");
1005
1006   SDValue LHS = N->getOperand(2);
1007   SDValue RHS = N->getOperand(3);
1008   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(1))->get());
1009
1010   // The chain (Op#0), CC (#1) and basic block destination (Op#4) are always
1011   // legal types.
1012   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1013                                 N->getOperand(1), LHS, RHS, N->getOperand(4)),
1014                  0);
1015 }
1016
1017 SDValue DAGTypeLegalizer::PromoteIntOp_BRCOND(SDNode *N, unsigned OpNo) {
1018   assert(OpNo == 1 && "only know how to promote condition");
1019
1020   // Promote all the way up to the canonical SetCC type.
1021   SDValue Cond = PromoteTargetBoolean(N->getOperand(1), MVT::Other);
1022
1023   // The chain (Op#0) and basic block destination (Op#2) are always legal types.
1024   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0), Cond,
1025                                         N->getOperand(2)), 0);
1026 }
1027
1028 SDValue DAGTypeLegalizer::PromoteIntOp_BUILD_PAIR(SDNode *N) {
1029   // Since the result type is legal, the operands must promote to it.
1030   EVT OVT = N->getOperand(0).getValueType();
1031   SDValue Lo = ZExtPromotedInteger(N->getOperand(0));
1032   SDValue Hi = GetPromotedInteger(N->getOperand(1));
1033   assert(Lo.getValueType() == N->getValueType(0) && "Operand over promoted?");
1034   SDLoc dl(N);
1035
1036   Hi = DAG.getNode(ISD::SHL, dl, N->getValueType(0), Hi,
1037                    DAG.getConstant(OVT.getSizeInBits(), dl,
1038                                    TLI.getPointerTy(DAG.getDataLayout())));
1039   return DAG.getNode(ISD::OR, dl, N->getValueType(0), Lo, Hi);
1040 }
1041
1042 SDValue DAGTypeLegalizer::PromoteIntOp_BUILD_VECTOR(SDNode *N) {
1043   // The vector type is legal but the element type is not.  This implies
1044   // that the vector is a power-of-two in length and that the element
1045   // type does not have a strange size (eg: it is not i1).
1046   EVT VecVT = N->getValueType(0);
1047   unsigned NumElts = VecVT.getVectorNumElements();
1048   assert(!((NumElts & 1) && (!TLI.isTypeLegal(VecVT))) &&
1049          "Legal vector of one illegal element?");
1050
1051   // Promote the inserted value.  The type does not need to match the
1052   // vector element type.  Check that any extra bits introduced will be
1053   // truncated away.
1054   assert(N->getOperand(0).getValueType().getSizeInBits() >=
1055          N->getValueType(0).getVectorElementType().getSizeInBits() &&
1056          "Type of inserted value narrower than vector element type!");
1057
1058   SmallVector<SDValue, 16> NewOps;
1059   for (unsigned i = 0; i < NumElts; ++i)
1060     NewOps.push_back(GetPromotedInteger(N->getOperand(i)));
1061
1062   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1063 }
1064
1065 SDValue DAGTypeLegalizer::PromoteIntOp_CONVERT_RNDSAT(SDNode *N) {
1066   ISD::CvtCode CvtCode = cast<CvtRndSatSDNode>(N)->getCvtCode();
1067   assert ((CvtCode == ISD::CVT_SS || CvtCode == ISD::CVT_SU ||
1068            CvtCode == ISD::CVT_US || CvtCode == ISD::CVT_UU ||
1069            CvtCode == ISD::CVT_FS || CvtCode == ISD::CVT_FU) &&
1070            "can only promote integer arguments");
1071   SDValue InOp = GetPromotedInteger(N->getOperand(0));
1072   return DAG.getConvertRndSat(N->getValueType(0), SDLoc(N), InOp,
1073                               N->getOperand(1), N->getOperand(2),
1074                               N->getOperand(3), N->getOperand(4), CvtCode);
1075 }
1076
1077 SDValue DAGTypeLegalizer::PromoteIntOp_INSERT_VECTOR_ELT(SDNode *N,
1078                                                          unsigned OpNo) {
1079   if (OpNo == 1) {
1080     // Promote the inserted value.  This is valid because the type does not
1081     // have to match the vector element type.
1082
1083     // Check that any extra bits introduced will be truncated away.
1084     assert(N->getOperand(1).getValueType().getSizeInBits() >=
1085            N->getValueType(0).getVectorElementType().getSizeInBits() &&
1086            "Type of inserted value narrower than vector element type!");
1087     return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1088                                   GetPromotedInteger(N->getOperand(1)),
1089                                   N->getOperand(2)),
1090                    0);
1091   }
1092
1093   assert(OpNo == 2 && "Different operand and result vector types?");
1094
1095   // Promote the index.
1096   SDValue Idx = DAG.getZExtOrTrunc(N->getOperand(2), SDLoc(N),
1097                                    TLI.getVectorIdxTy(DAG.getDataLayout()));
1098   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1099                                 N->getOperand(1), Idx), 0);
1100 }
1101
1102 SDValue DAGTypeLegalizer::PromoteIntOp_SCALAR_TO_VECTOR(SDNode *N) {
1103   // Integer SCALAR_TO_VECTOR operands are implicitly truncated, so just promote
1104   // the operand in place.
1105   return SDValue(DAG.UpdateNodeOperands(N,
1106                                 GetPromotedInteger(N->getOperand(0))), 0);
1107 }
1108
1109 SDValue DAGTypeLegalizer::PromoteIntOp_SELECT(SDNode *N, unsigned OpNo) {
1110   assert(OpNo == 0 && "Only know how to promote the condition!");
1111   SDValue Cond = N->getOperand(0);
1112   EVT OpTy = N->getOperand(1).getValueType();
1113
1114   // Promote all the way up to the canonical SetCC type.
1115   EVT OpVT = N->getOpcode() == ISD::SELECT ? OpTy.getScalarType() : OpTy;
1116   Cond = PromoteTargetBoolean(Cond, OpVT);
1117
1118   return SDValue(DAG.UpdateNodeOperands(N, Cond, N->getOperand(1),
1119                                         N->getOperand(2)), 0);
1120 }
1121
1122 SDValue DAGTypeLegalizer::PromoteIntOp_SELECT_CC(SDNode *N, unsigned OpNo) {
1123   assert(OpNo == 0 && "Don't know how to promote this operand!");
1124
1125   SDValue LHS = N->getOperand(0);
1126   SDValue RHS = N->getOperand(1);
1127   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(4))->get());
1128
1129   // The CC (#4) and the possible return values (#2 and #3) have legal types.
1130   return SDValue(DAG.UpdateNodeOperands(N, LHS, RHS, N->getOperand(2),
1131                                 N->getOperand(3), N->getOperand(4)), 0);
1132 }
1133
1134 SDValue DAGTypeLegalizer::PromoteIntOp_SETCC(SDNode *N, unsigned OpNo) {
1135   assert(OpNo == 0 && "Don't know how to promote this operand!");
1136
1137   SDValue LHS = N->getOperand(0);
1138   SDValue RHS = N->getOperand(1);
1139   PromoteSetCCOperands(LHS, RHS, cast<CondCodeSDNode>(N->getOperand(2))->get());
1140
1141   // The CC (#2) is always legal.
1142   return SDValue(DAG.UpdateNodeOperands(N, LHS, RHS, N->getOperand(2)), 0);
1143 }
1144
1145 SDValue DAGTypeLegalizer::PromoteIntOp_Shift(SDNode *N) {
1146   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
1147                                 ZExtPromotedInteger(N->getOperand(1))), 0);
1148 }
1149
1150 SDValue DAGTypeLegalizer::PromoteIntOp_SIGN_EXTEND(SDNode *N) {
1151   SDValue Op = GetPromotedInteger(N->getOperand(0));
1152   SDLoc dl(N);
1153   Op = DAG.getNode(ISD::ANY_EXTEND, dl, N->getValueType(0), Op);
1154   return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Op.getValueType(),
1155                      Op, DAG.getValueType(N->getOperand(0).getValueType()));
1156 }
1157
1158 SDValue DAGTypeLegalizer::PromoteIntOp_SINT_TO_FP(SDNode *N) {
1159   return SDValue(DAG.UpdateNodeOperands(N,
1160                                 SExtPromotedInteger(N->getOperand(0))), 0);
1161 }
1162
1163 SDValue DAGTypeLegalizer::PromoteIntOp_STORE(StoreSDNode *N, unsigned OpNo){
1164   assert(ISD::isUNINDEXEDStore(N) && "Indexed store during type legalization!");
1165   SDValue Ch = N->getChain(), Ptr = N->getBasePtr();
1166   SDLoc dl(N);
1167
1168   SDValue Val = GetPromotedInteger(N->getValue());  // Get promoted value.
1169
1170   // Truncate the value and store the result.
1171   return DAG.getTruncStore(Ch, dl, Val, Ptr,
1172                            N->getMemoryVT(), N->getMemOperand());
1173 }
1174
1175 SDValue DAGTypeLegalizer::PromoteIntOp_MSTORE(MaskedStoreSDNode *N,
1176                                               unsigned OpNo) {
1177
1178   SDValue DataOp = N->getValue();
1179   EVT DataVT = DataOp.getValueType();
1180   SDValue Mask = N->getMask();
1181   SDLoc dl(N);
1182
1183   bool TruncateStore = false;
1184   if (OpNo == 2) {
1185     // Mask comes before the data operand. If the data operand is legal, we just
1186     // promote the mask.
1187     // When the data operand has illegal type, we should legalize the data
1188     // operand first. The mask will be promoted/splitted/widened according to
1189     // the data operand type.
1190     if (TLI.isTypeLegal(DataVT))
1191       Mask = PromoteTargetBoolean(Mask, DataVT);
1192     else {
1193       if (getTypeAction(DataVT) == TargetLowering::TypePromoteInteger)
1194         return PromoteIntOp_MSTORE(N, 3);
1195
1196       else if (getTypeAction(DataVT) == TargetLowering::TypeWidenVector)
1197         return WidenVecOp_MSTORE(N, 3);
1198
1199       else {
1200         assert (getTypeAction(DataVT) == TargetLowering::TypeSplitVector);
1201         return SplitVecOp_MSTORE(N, 3);
1202       }
1203     }
1204   } else { // Data operand
1205     assert(OpNo == 3 && "Unexpected operand for promotion");
1206     DataOp = GetPromotedInteger(DataOp);
1207     Mask = PromoteTargetBoolean(Mask, DataOp.getValueType());
1208     TruncateStore = true;
1209   }
1210
1211   return DAG.getMaskedStore(N->getChain(), dl, DataOp, N->getBasePtr(), Mask,
1212                             N->getMemoryVT(), N->getMemOperand(),
1213                             TruncateStore);
1214 }
1215
1216 SDValue DAGTypeLegalizer::PromoteIntOp_MLOAD(MaskedLoadSDNode *N,
1217                                              unsigned OpNo) {
1218   assert(OpNo == 2 && "Only know how to promote the mask!");
1219   EVT DataVT = N->getValueType(0);
1220   SDValue Mask = PromoteTargetBoolean(N->getOperand(OpNo), DataVT);
1221   SmallVector<SDValue, 4> NewOps(N->op_begin(), N->op_end());
1222   NewOps[OpNo] = Mask;
1223   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1224 }
1225
1226 SDValue DAGTypeLegalizer::PromoteIntOp_MGATHER(MaskedGatherSDNode *N,
1227                                                unsigned OpNo) {
1228
1229   SmallVector<SDValue, 5> NewOps(N->op_begin(), N->op_end());
1230   if (OpNo == 2) {
1231     // The Mask
1232     EVT DataVT = N->getValueType(0);
1233     NewOps[OpNo] = PromoteTargetBoolean(N->getOperand(OpNo), DataVT);
1234   } else
1235     NewOps[OpNo] = GetPromotedInteger(N->getOperand(OpNo));
1236   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1237 }
1238
1239 SDValue DAGTypeLegalizer::PromoteIntOp_MSCATTER(MaskedScatterSDNode *N,
1240                                                 unsigned OpNo) {
1241   SmallVector<SDValue, 5> NewOps(N->op_begin(), N->op_end());
1242   if (OpNo == 2) {
1243     // The Mask
1244     EVT DataVT = N->getValue().getValueType();
1245     NewOps[OpNo] = PromoteTargetBoolean(N->getOperand(OpNo), DataVT);
1246   } else
1247     NewOps[OpNo] = GetPromotedInteger(N->getOperand(OpNo));
1248   return SDValue(DAG.UpdateNodeOperands(N, NewOps), 0);
1249 }
1250
1251 SDValue DAGTypeLegalizer::PromoteIntOp_TRUNCATE(SDNode *N) {
1252   SDValue Op = GetPromotedInteger(N->getOperand(0));
1253   return DAG.getNode(ISD::TRUNCATE, SDLoc(N), N->getValueType(0), Op);
1254 }
1255
1256 SDValue DAGTypeLegalizer::PromoteIntOp_UINT_TO_FP(SDNode *N) {
1257   return SDValue(DAG.UpdateNodeOperands(N,
1258                                 ZExtPromotedInteger(N->getOperand(0))), 0);
1259 }
1260
1261 SDValue DAGTypeLegalizer::PromoteIntOp_ZERO_EXTEND(SDNode *N) {
1262   SDLoc dl(N);
1263   SDValue Op = GetPromotedInteger(N->getOperand(0));
1264   Op = DAG.getNode(ISD::ANY_EXTEND, dl, N->getValueType(0), Op);
1265   return DAG.getZeroExtendInReg(Op, dl,
1266                                 N->getOperand(0).getValueType().getScalarType());
1267 }
1268
1269
1270 //===----------------------------------------------------------------------===//
1271 //  Integer Result Expansion
1272 //===----------------------------------------------------------------------===//
1273
1274 /// ExpandIntegerResult - This method is called when the specified result of the
1275 /// specified node is found to need expansion.  At this point, the node may also
1276 /// have invalid operands or may have other results that need promotion, we just
1277 /// know that (at least) one result needs expansion.
1278 void DAGTypeLegalizer::ExpandIntegerResult(SDNode *N, unsigned ResNo) {
1279   DEBUG(dbgs() << "Expand integer result: "; N->dump(&DAG); dbgs() << "\n");
1280   SDValue Lo, Hi;
1281   Lo = Hi = SDValue();
1282
1283   // See if the target wants to custom expand this node.
1284   if (CustomLowerNode(N, N->getValueType(ResNo), true))
1285     return;
1286
1287   switch (N->getOpcode()) {
1288   default:
1289 #ifndef NDEBUG
1290     dbgs() << "ExpandIntegerResult #" << ResNo << ": ";
1291     N->dump(&DAG); dbgs() << "\n";
1292 #endif
1293     llvm_unreachable("Do not know how to expand the result of this operator!");
1294
1295   case ISD::MERGE_VALUES: SplitRes_MERGE_VALUES(N, ResNo, Lo, Hi); break;
1296   case ISD::SELECT:       SplitRes_SELECT(N, Lo, Hi); break;
1297   case ISD::SELECT_CC:    SplitRes_SELECT_CC(N, Lo, Hi); break;
1298   case ISD::UNDEF:        SplitRes_UNDEF(N, Lo, Hi); break;
1299
1300   case ISD::BITCAST:            ExpandRes_BITCAST(N, Lo, Hi); break;
1301   case ISD::BUILD_PAIR:         ExpandRes_BUILD_PAIR(N, Lo, Hi); break;
1302   case ISD::EXTRACT_ELEMENT:    ExpandRes_EXTRACT_ELEMENT(N, Lo, Hi); break;
1303   case ISD::EXTRACT_VECTOR_ELT: ExpandRes_EXTRACT_VECTOR_ELT(N, Lo, Hi); break;
1304   case ISD::VAARG:              ExpandRes_VAARG(N, Lo, Hi); break;
1305
1306   case ISD::ANY_EXTEND:  ExpandIntRes_ANY_EXTEND(N, Lo, Hi); break;
1307   case ISD::AssertSext:  ExpandIntRes_AssertSext(N, Lo, Hi); break;
1308   case ISD::AssertZext:  ExpandIntRes_AssertZext(N, Lo, Hi); break;
1309   case ISD::BITREVERSE:  ExpandIntRes_BITREVERSE(N, Lo, Hi); break;
1310   case ISD::BSWAP:       ExpandIntRes_BSWAP(N, Lo, Hi); break;
1311   case ISD::Constant:    ExpandIntRes_Constant(N, Lo, Hi); break;
1312   case ISD::CTLZ_ZERO_UNDEF:
1313   case ISD::CTLZ:        ExpandIntRes_CTLZ(N, Lo, Hi); break;
1314   case ISD::CTPOP:       ExpandIntRes_CTPOP(N, Lo, Hi); break;
1315   case ISD::CTTZ_ZERO_UNDEF:
1316   case ISD::CTTZ:        ExpandIntRes_CTTZ(N, Lo, Hi); break;
1317   case ISD::FP_TO_SINT:  ExpandIntRes_FP_TO_SINT(N, Lo, Hi); break;
1318   case ISD::FP_TO_UINT:  ExpandIntRes_FP_TO_UINT(N, Lo, Hi); break;
1319   case ISD::LOAD:        ExpandIntRes_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
1320   case ISD::MUL:         ExpandIntRes_MUL(N, Lo, Hi); break;
1321   case ISD::READCYCLECOUNTER: ExpandIntRes_READCYCLECOUNTER(N, Lo, Hi); break;
1322   case ISD::SDIV:        ExpandIntRes_SDIV(N, Lo, Hi); break;
1323   case ISD::SIGN_EXTEND: ExpandIntRes_SIGN_EXTEND(N, Lo, Hi); break;
1324   case ISD::SIGN_EXTEND_INREG: ExpandIntRes_SIGN_EXTEND_INREG(N, Lo, Hi); break;
1325   case ISD::SREM:        ExpandIntRes_SREM(N, Lo, Hi); break;
1326   case ISD::TRUNCATE:    ExpandIntRes_TRUNCATE(N, Lo, Hi); break;
1327   case ISD::UDIV:        ExpandIntRes_UDIV(N, Lo, Hi); break;
1328   case ISD::UREM:        ExpandIntRes_UREM(N, Lo, Hi); break;
1329   case ISD::ZERO_EXTEND: ExpandIntRes_ZERO_EXTEND(N, Lo, Hi); break;
1330   case ISD::ATOMIC_LOAD: ExpandIntRes_ATOMIC_LOAD(N, Lo, Hi); break;
1331
1332   case ISD::ATOMIC_LOAD_ADD:
1333   case ISD::ATOMIC_LOAD_SUB:
1334   case ISD::ATOMIC_LOAD_AND:
1335   case ISD::ATOMIC_LOAD_OR:
1336   case ISD::ATOMIC_LOAD_XOR:
1337   case ISD::ATOMIC_LOAD_NAND:
1338   case ISD::ATOMIC_LOAD_MIN:
1339   case ISD::ATOMIC_LOAD_MAX:
1340   case ISD::ATOMIC_LOAD_UMIN:
1341   case ISD::ATOMIC_LOAD_UMAX:
1342   case ISD::ATOMIC_SWAP:
1343   case ISD::ATOMIC_CMP_SWAP: {
1344     std::pair<SDValue, SDValue> Tmp = ExpandAtomic(N);
1345     SplitInteger(Tmp.first, Lo, Hi);
1346     ReplaceValueWith(SDValue(N, 1), Tmp.second);
1347     break;
1348   }
1349   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS: {
1350     AtomicSDNode *AN = cast<AtomicSDNode>(N);
1351     SDVTList VTs = DAG.getVTList(N->getValueType(0), MVT::Other);
1352     SDValue Tmp = DAG.getAtomicCmpSwap(
1353         ISD::ATOMIC_CMP_SWAP, SDLoc(N), AN->getMemoryVT(), VTs,
1354         N->getOperand(0), N->getOperand(1), N->getOperand(2), N->getOperand(3),
1355         AN->getMemOperand(), AN->getSuccessOrdering(), AN->getFailureOrdering(),
1356         AN->getSynchScope());
1357
1358     // Expanding to the strong ATOMIC_CMP_SWAP node means we can determine
1359     // success simply by comparing the loaded value against the ingoing
1360     // comparison.
1361     SDValue Success = DAG.getSetCC(SDLoc(N), N->getValueType(1), Tmp,
1362                                    N->getOperand(2), ISD::SETEQ);
1363
1364     SplitInteger(Tmp, Lo, Hi);
1365     ReplaceValueWith(SDValue(N, 1), Success);
1366     ReplaceValueWith(SDValue(N, 2), Tmp.getValue(1));
1367     break;
1368   }
1369
1370   case ISD::AND:
1371   case ISD::OR:
1372   case ISD::XOR: ExpandIntRes_Logical(N, Lo, Hi); break;
1373
1374   case ISD::UMAX:
1375   case ISD::SMAX:
1376   case ISD::UMIN:
1377   case ISD::SMIN: ExpandIntRes_MINMAX(N, Lo, Hi); break;
1378
1379   case ISD::ADD:
1380   case ISD::SUB: ExpandIntRes_ADDSUB(N, Lo, Hi); break;
1381
1382   case ISD::ADDC:
1383   case ISD::SUBC: ExpandIntRes_ADDSUBC(N, Lo, Hi); break;
1384
1385   case ISD::ADDE:
1386   case ISD::SUBE: ExpandIntRes_ADDSUBE(N, Lo, Hi); break;
1387
1388   case ISD::SHL:
1389   case ISD::SRA:
1390   case ISD::SRL: ExpandIntRes_Shift(N, Lo, Hi); break;
1391
1392   case ISD::SADDO:
1393   case ISD::SSUBO: ExpandIntRes_SADDSUBO(N, Lo, Hi); break;
1394   case ISD::UADDO:
1395   case ISD::USUBO: ExpandIntRes_UADDSUBO(N, Lo, Hi); break;
1396   case ISD::UMULO:
1397   case ISD::SMULO: ExpandIntRes_XMULO(N, Lo, Hi); break;
1398   }
1399
1400   // If Lo/Hi is null, the sub-method took care of registering results etc.
1401   if (Lo.getNode())
1402     SetExpandedInteger(SDValue(N, ResNo), Lo, Hi);
1403 }
1404
1405 /// Lower an atomic node to the appropriate builtin call.
1406 std::pair <SDValue, SDValue> DAGTypeLegalizer::ExpandAtomic(SDNode *Node) {
1407   unsigned Opc = Node->getOpcode();
1408   MVT VT = cast<AtomicSDNode>(Node)->getMemoryVT().getSimpleVT();
1409   RTLIB::Libcall LC = RTLIB::getSYNC(Opc, VT);
1410   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected atomic op or value type!");
1411
1412   return ExpandChainLibCall(LC, Node, false);
1413 }
1414
1415 /// N is a shift by a value that needs to be expanded,
1416 /// and the shift amount is a constant 'Amt'.  Expand the operation.
1417 void DAGTypeLegalizer::ExpandShiftByConstant(SDNode *N, const APInt &Amt,
1418                                              SDValue &Lo, SDValue &Hi) {
1419   SDLoc DL(N);
1420   // Expand the incoming operand to be shifted, so that we have its parts
1421   SDValue InL, InH;
1422   GetExpandedInteger(N->getOperand(0), InL, InH);
1423
1424   // Though Amt shouldn't usually be 0, it's possible. E.g. when legalization
1425   // splitted a vector shift, like this: <op1, op2> SHL <0, 2>.
1426   if (!Amt) {
1427     Lo = InL;
1428     Hi = InH;
1429     return;
1430   }
1431
1432   EVT NVT = InL.getValueType();
1433   unsigned VTBits = N->getValueType(0).getSizeInBits();
1434   unsigned NVTBits = NVT.getSizeInBits();
1435   EVT ShTy = N->getOperand(1).getValueType();
1436
1437   if (N->getOpcode() == ISD::SHL) {
1438     if (Amt.ugt(VTBits)) {
1439       Lo = Hi = DAG.getConstant(0, DL, NVT);
1440     } else if (Amt.ugt(NVTBits)) {
1441       Lo = DAG.getConstant(0, DL, NVT);
1442       Hi = DAG.getNode(ISD::SHL, DL,
1443                        NVT, InL, DAG.getConstant(Amt - NVTBits, DL, ShTy));
1444     } else if (Amt == NVTBits) {
1445       Lo = DAG.getConstant(0, DL, NVT);
1446       Hi = InL;
1447     } else {
1448       Lo = DAG.getNode(ISD::SHL, DL, NVT, InL, DAG.getConstant(Amt, DL, ShTy));
1449       Hi = DAG.getNode(ISD::OR, DL, NVT,
1450                        DAG.getNode(ISD::SHL, DL, NVT, InH,
1451                                    DAG.getConstant(Amt, DL, ShTy)),
1452                        DAG.getNode(ISD::SRL, DL, NVT, InL,
1453                                    DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
1454     }
1455     return;
1456   }
1457
1458   if (N->getOpcode() == ISD::SRL) {
1459     if (Amt.ugt(VTBits)) {
1460       Lo = Hi = DAG.getConstant(0, DL, NVT);
1461     } else if (Amt.ugt(NVTBits)) {
1462       Lo = DAG.getNode(ISD::SRL, DL,
1463                        NVT, InH, DAG.getConstant(Amt - NVTBits, DL, ShTy));
1464       Hi = DAG.getConstant(0, DL, NVT);
1465     } else if (Amt == NVTBits) {
1466       Lo = InH;
1467       Hi = DAG.getConstant(0, DL, NVT);
1468     } else {
1469       Lo = DAG.getNode(ISD::OR, DL, NVT,
1470                        DAG.getNode(ISD::SRL, DL, NVT, InL,
1471                                    DAG.getConstant(Amt, DL, ShTy)),
1472                        DAG.getNode(ISD::SHL, DL, NVT, InH,
1473                                    DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
1474       Hi = DAG.getNode(ISD::SRL, DL, NVT, InH, DAG.getConstant(Amt, DL, ShTy));
1475     }
1476     return;
1477   }
1478
1479   assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
1480   if (Amt.ugt(VTBits)) {
1481     Hi = Lo = DAG.getNode(ISD::SRA, DL, NVT, InH,
1482                           DAG.getConstant(NVTBits - 1, DL, ShTy));
1483   } else if (Amt.ugt(NVTBits)) {
1484     Lo = DAG.getNode(ISD::SRA, DL, NVT, InH,
1485                      DAG.getConstant(Amt - NVTBits, DL, ShTy));
1486     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH,
1487                      DAG.getConstant(NVTBits - 1, DL, ShTy));
1488   } else if (Amt == NVTBits) {
1489     Lo = InH;
1490     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH,
1491                      DAG.getConstant(NVTBits - 1, DL, ShTy));
1492   } else {
1493     Lo = DAG.getNode(ISD::OR, DL, NVT,
1494                      DAG.getNode(ISD::SRL, DL, NVT, InL,
1495                                  DAG.getConstant(Amt, DL, ShTy)),
1496                      DAG.getNode(ISD::SHL, DL, NVT, InH,
1497                                  DAG.getConstant(-Amt + NVTBits, DL, ShTy)));
1498     Hi = DAG.getNode(ISD::SRA, DL, NVT, InH, DAG.getConstant(Amt, DL, ShTy));
1499   }
1500 }
1501
1502 /// ExpandShiftWithKnownAmountBit - Try to determine whether we can simplify
1503 /// this shift based on knowledge of the high bit of the shift amount.  If we
1504 /// can tell this, we know that it is >= 32 or < 32, without knowing the actual
1505 /// shift amount.
1506 bool DAGTypeLegalizer::
1507 ExpandShiftWithKnownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
1508   SDValue Amt = N->getOperand(1);
1509   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1510   EVT ShTy = Amt.getValueType();
1511   unsigned ShBits = ShTy.getScalarType().getSizeInBits();
1512   unsigned NVTBits = NVT.getScalarType().getSizeInBits();
1513   assert(isPowerOf2_32(NVTBits) &&
1514          "Expanded integer type size not a power of two!");
1515   SDLoc dl(N);
1516
1517   APInt HighBitMask = APInt::getHighBitsSet(ShBits, ShBits - Log2_32(NVTBits));
1518   APInt KnownZero, KnownOne;
1519   DAG.computeKnownBits(N->getOperand(1), KnownZero, KnownOne);
1520
1521   // If we don't know anything about the high bits, exit.
1522   if (((KnownZero|KnownOne) & HighBitMask) == 0)
1523     return false;
1524
1525   // Get the incoming operand to be shifted.
1526   SDValue InL, InH;
1527   GetExpandedInteger(N->getOperand(0), InL, InH);
1528
1529   // If we know that any of the high bits of the shift amount are one, then we
1530   // can do this as a couple of simple shifts.
1531   if (KnownOne.intersects(HighBitMask)) {
1532     // Mask out the high bit, which we know is set.
1533     Amt = DAG.getNode(ISD::AND, dl, ShTy, Amt,
1534                       DAG.getConstant(~HighBitMask, dl, ShTy));
1535
1536     switch (N->getOpcode()) {
1537     default: llvm_unreachable("Unknown shift");
1538     case ISD::SHL:
1539       Lo = DAG.getConstant(0, dl, NVT);              // Low part is zero.
1540       Hi = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt); // High part from Lo part.
1541       return true;
1542     case ISD::SRL:
1543       Hi = DAG.getConstant(0, dl, NVT);              // Hi part is zero.
1544       Lo = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt); // Lo part from Hi part.
1545       return true;
1546     case ISD::SRA:
1547       Hi = DAG.getNode(ISD::SRA, dl, NVT, InH,       // Sign extend high part.
1548                        DAG.getConstant(NVTBits - 1, dl, ShTy));
1549       Lo = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt); // Lo part from Hi part.
1550       return true;
1551     }
1552   }
1553
1554   // If we know that all of the high bits of the shift amount are zero, then we
1555   // can do this as a couple of simple shifts.
1556   if ((KnownZero & HighBitMask) == HighBitMask) {
1557     // Calculate 31-x. 31 is used instead of 32 to avoid creating an undefined
1558     // shift if x is zero.  We can use XOR here because x is known to be smaller
1559     // than 32.
1560     SDValue Amt2 = DAG.getNode(ISD::XOR, dl, ShTy, Amt,
1561                                DAG.getConstant(NVTBits - 1, dl, ShTy));
1562
1563     unsigned Op1, Op2;
1564     switch (N->getOpcode()) {
1565     default: llvm_unreachable("Unknown shift");
1566     case ISD::SHL:  Op1 = ISD::SHL; Op2 = ISD::SRL; break;
1567     case ISD::SRL:
1568     case ISD::SRA:  Op1 = ISD::SRL; Op2 = ISD::SHL; break;
1569     }
1570
1571     // When shifting right the arithmetic for Lo and Hi is swapped.
1572     if (N->getOpcode() != ISD::SHL)
1573       std::swap(InL, InH);
1574
1575     // Use a little trick to get the bits that move from Lo to Hi. First
1576     // shift by one bit.
1577     SDValue Sh1 = DAG.getNode(Op2, dl, NVT, InL, DAG.getConstant(1, dl, ShTy));
1578     // Then compute the remaining shift with amount-1.
1579     SDValue Sh2 = DAG.getNode(Op2, dl, NVT, Sh1, Amt2);
1580
1581     Lo = DAG.getNode(N->getOpcode(), dl, NVT, InL, Amt);
1582     Hi = DAG.getNode(ISD::OR, dl, NVT, DAG.getNode(Op1, dl, NVT, InH, Amt),Sh2);
1583
1584     if (N->getOpcode() != ISD::SHL)
1585       std::swap(Hi, Lo);
1586     return true;
1587   }
1588
1589   return false;
1590 }
1591
1592 /// ExpandShiftWithUnknownAmountBit - Fully general expansion of integer shift
1593 /// of any size.
1594 bool DAGTypeLegalizer::
1595 ExpandShiftWithUnknownAmountBit(SDNode *N, SDValue &Lo, SDValue &Hi) {
1596   SDValue Amt = N->getOperand(1);
1597   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1598   EVT ShTy = Amt.getValueType();
1599   unsigned NVTBits = NVT.getSizeInBits();
1600   assert(isPowerOf2_32(NVTBits) &&
1601          "Expanded integer type size not a power of two!");
1602   SDLoc dl(N);
1603
1604   // Get the incoming operand to be shifted.
1605   SDValue InL, InH;
1606   GetExpandedInteger(N->getOperand(0), InL, InH);
1607
1608   SDValue NVBitsNode = DAG.getConstant(NVTBits, dl, ShTy);
1609   SDValue AmtExcess = DAG.getNode(ISD::SUB, dl, ShTy, Amt, NVBitsNode);
1610   SDValue AmtLack = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);
1611   SDValue isShort = DAG.getSetCC(dl, getSetCCResultType(ShTy),
1612                                  Amt, NVBitsNode, ISD::SETULT);
1613   SDValue isZero = DAG.getSetCC(dl, getSetCCResultType(ShTy),
1614                                 Amt, DAG.getConstant(0, dl, ShTy),
1615                                 ISD::SETEQ);
1616
1617   SDValue LoS, HiS, LoL, HiL;
1618   switch (N->getOpcode()) {
1619   default: llvm_unreachable("Unknown shift");
1620   case ISD::SHL:
1621     // Short: ShAmt < NVTBits
1622     LoS = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt);
1623     HiS = DAG.getNode(ISD::OR, dl, NVT,
1624                       DAG.getNode(ISD::SHL, dl, NVT, InH, Amt),
1625                       DAG.getNode(ISD::SRL, dl, NVT, InL, AmtLack));
1626
1627     // Long: ShAmt >= NVTBits
1628     LoL = DAG.getConstant(0, dl, NVT);                    // Lo part is zero.
1629     HiL = DAG.getNode(ISD::SHL, dl, NVT, InL, AmtExcess); // Hi from Lo part.
1630
1631     Lo = DAG.getSelect(dl, NVT, isShort, LoS, LoL);
1632     Hi = DAG.getSelect(dl, NVT, isZero, InH,
1633                        DAG.getSelect(dl, NVT, isShort, HiS, HiL));
1634     return true;
1635   case ISD::SRL:
1636     // Short: ShAmt < NVTBits
1637     HiS = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt);
1638     LoS = DAG.getNode(ISD::OR, dl, NVT,
1639                       DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
1640     // FIXME: If Amt is zero, the following shift generates an undefined result
1641     // on some architectures.
1642                       DAG.getNode(ISD::SHL, dl, NVT, InH, AmtLack));
1643
1644     // Long: ShAmt >= NVTBits
1645     HiL = DAG.getConstant(0, dl, NVT);                    // Hi part is zero.
1646     LoL = DAG.getNode(ISD::SRL, dl, NVT, InH, AmtExcess); // Lo from Hi part.
1647
1648     Lo = DAG.getSelect(dl, NVT, isZero, InL,
1649                        DAG.getSelect(dl, NVT, isShort, LoS, LoL));
1650     Hi = DAG.getSelect(dl, NVT, isShort, HiS, HiL);
1651     return true;
1652   case ISD::SRA:
1653     // Short: ShAmt < NVTBits
1654     HiS = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt);
1655     LoS = DAG.getNode(ISD::OR, dl, NVT,
1656                       DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),
1657                       DAG.getNode(ISD::SHL, dl, NVT, InH, AmtLack));
1658
1659     // Long: ShAmt >= NVTBits
1660     HiL = DAG.getNode(ISD::SRA, dl, NVT, InH,             // Sign of Hi part.
1661                       DAG.getConstant(NVTBits - 1, dl, ShTy));
1662     LoL = DAG.getNode(ISD::SRA, dl, NVT, InH, AmtExcess); // Lo from Hi part.
1663
1664     Lo = DAG.getSelect(dl, NVT, isZero, InL,
1665                        DAG.getSelect(dl, NVT, isShort, LoS, LoL));
1666     Hi = DAG.getSelect(dl, NVT, isShort, HiS, HiL);
1667     return true;
1668   }
1669 }
1670
1671 static std::pair<ISD::CondCode, ISD::NodeType> getExpandedMinMaxOps(int Op) {
1672
1673   switch (Op) {
1674     default: llvm_unreachable("invalid min/max opcode");
1675     case ISD::SMAX:
1676       return std::make_pair(ISD::SETGT, ISD::UMAX);
1677     case ISD::UMAX:
1678       return std::make_pair(ISD::SETUGT, ISD::UMAX);
1679     case ISD::SMIN:
1680       return std::make_pair(ISD::SETLT, ISD::UMIN);
1681     case ISD::UMIN:
1682       return std::make_pair(ISD::SETULT, ISD::UMIN);
1683   }
1684 }
1685
1686 void DAGTypeLegalizer::ExpandIntRes_MINMAX(SDNode *N,
1687                                            SDValue &Lo, SDValue &Hi) {
1688   SDLoc DL(N);
1689   ISD::NodeType LoOpc;
1690   ISD::CondCode CondC;
1691   std::tie(CondC, LoOpc) = getExpandedMinMaxOps(N->getOpcode());
1692
1693   // Expand the subcomponents.
1694   SDValue LHSL, LHSH, RHSL, RHSH;
1695   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
1696   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
1697
1698   // Value types
1699   EVT NVT = LHSL.getValueType();
1700   EVT CCT = getSetCCResultType(NVT);
1701
1702   // Hi part is always the same op
1703   Hi = DAG.getNode(N->getOpcode(), DL, {NVT, NVT}, {LHSH, RHSH});
1704
1705   // We need to know whether to select Lo part that corresponds to 'winning'
1706   // Hi part or if Hi parts are equal.
1707   SDValue IsHiLeft = DAG.getSetCC(DL, CCT, LHSH, RHSH, CondC);
1708   SDValue IsHiEq = DAG.getSetCC(DL, CCT, LHSH, RHSH, ISD::SETEQ);
1709
1710   // Lo part corresponding to the 'winning' Hi part
1711   SDValue LoCmp = DAG.getSelect(DL, NVT, IsHiLeft, LHSL, RHSL);
1712
1713   // Recursed Lo part if Hi parts are equal, this uses unsigned version
1714   SDValue LoMinMax = DAG.getNode(LoOpc, DL, {NVT, NVT}, {LHSL, RHSL});
1715
1716   Lo = DAG.getSelect(DL, NVT, IsHiEq, LoMinMax, LoCmp);
1717 }
1718
1719 void DAGTypeLegalizer::ExpandIntRes_ADDSUB(SDNode *N,
1720                                            SDValue &Lo, SDValue &Hi) {
1721   SDLoc dl(N);
1722   // Expand the subcomponents.
1723   SDValue LHSL, LHSH, RHSL, RHSH;
1724   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
1725   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
1726
1727   EVT NVT = LHSL.getValueType();
1728   SDValue LoOps[2] = { LHSL, RHSL };
1729   SDValue HiOps[3] = { LHSH, RHSH };
1730
1731   // Do not generate ADDC/ADDE or SUBC/SUBE if the target does not support
1732   // them.  TODO: Teach operation legalization how to expand unsupported
1733   // ADDC/ADDE/SUBC/SUBE.  The problem is that these operations generate
1734   // a carry of type MVT::Glue, but there doesn't seem to be any way to
1735   // generate a value of this type in the expanded code sequence.
1736   bool hasCarry =
1737     TLI.isOperationLegalOrCustom(N->getOpcode() == ISD::ADD ?
1738                                    ISD::ADDC : ISD::SUBC,
1739                                  TLI.getTypeToExpandTo(*DAG.getContext(), NVT));
1740
1741   if (hasCarry) {
1742     SDVTList VTList = DAG.getVTList(NVT, MVT::Glue);
1743     if (N->getOpcode() == ISD::ADD) {
1744       Lo = DAG.getNode(ISD::ADDC, dl, VTList, LoOps);
1745       HiOps[2] = Lo.getValue(1);
1746       Hi = DAG.getNode(ISD::ADDE, dl, VTList, HiOps);
1747     } else {
1748       Lo = DAG.getNode(ISD::SUBC, dl, VTList, LoOps);
1749       HiOps[2] = Lo.getValue(1);
1750       Hi = DAG.getNode(ISD::SUBE, dl, VTList, HiOps);
1751     }
1752     return;
1753   }
1754
1755   bool hasOVF =
1756     TLI.isOperationLegalOrCustom(N->getOpcode() == ISD::ADD ?
1757                                    ISD::UADDO : ISD::USUBO,
1758                                  TLI.getTypeToExpandTo(*DAG.getContext(), NVT));
1759   if (hasOVF) {
1760     SDVTList VTList = DAG.getVTList(NVT, NVT);
1761     TargetLoweringBase::BooleanContent BoolType = TLI.getBooleanContents(NVT);
1762     int RevOpc;
1763     if (N->getOpcode() == ISD::ADD) {
1764       RevOpc = ISD::SUB;
1765       Lo = DAG.getNode(ISD::UADDO, dl, VTList, LoOps);
1766       Hi = DAG.getNode(ISD::ADD, dl, NVT, makeArrayRef(HiOps, 2));
1767     } else {
1768       RevOpc = ISD::ADD;
1769       Lo = DAG.getNode(ISD::USUBO, dl, VTList, LoOps);
1770       Hi = DAG.getNode(ISD::SUB, dl, NVT, makeArrayRef(HiOps, 2));
1771     }
1772     SDValue OVF = Lo.getValue(1);
1773
1774     switch (BoolType) {
1775     case TargetLoweringBase::UndefinedBooleanContent:
1776       OVF = DAG.getNode(ISD::AND, dl, NVT, DAG.getConstant(1, dl, NVT), OVF);
1777       // Fallthrough
1778     case TargetLoweringBase::ZeroOrOneBooleanContent:
1779       Hi = DAG.getNode(N->getOpcode(), dl, NVT, Hi, OVF);
1780       break;
1781     case TargetLoweringBase::ZeroOrNegativeOneBooleanContent:
1782       Hi = DAG.getNode(RevOpc, dl, NVT, Hi, OVF);
1783     }
1784     return;
1785   }
1786
1787   if (N->getOpcode() == ISD::ADD) {
1788     Lo = DAG.getNode(ISD::ADD, dl, NVT, LoOps);
1789     Hi = DAG.getNode(ISD::ADD, dl, NVT, makeArrayRef(HiOps, 2));
1790     SDValue Cmp1 = DAG.getSetCC(dl, getSetCCResultType(NVT), Lo, LoOps[0],
1791                                 ISD::SETULT);
1792     SDValue Carry1 = DAG.getSelect(dl, NVT, Cmp1,
1793                                    DAG.getConstant(1, dl, NVT),
1794                                    DAG.getConstant(0, dl, NVT));
1795     SDValue Cmp2 = DAG.getSetCC(dl, getSetCCResultType(NVT), Lo, LoOps[1],
1796                                 ISD::SETULT);
1797     SDValue Carry2 = DAG.getSelect(dl, NVT, Cmp2,
1798                                    DAG.getConstant(1, dl, NVT), Carry1);
1799     Hi = DAG.getNode(ISD::ADD, dl, NVT, Hi, Carry2);
1800   } else {
1801     Lo = DAG.getNode(ISD::SUB, dl, NVT, LoOps);
1802     Hi = DAG.getNode(ISD::SUB, dl, NVT, makeArrayRef(HiOps, 2));
1803     SDValue Cmp =
1804       DAG.getSetCC(dl, getSetCCResultType(LoOps[0].getValueType()),
1805                    LoOps[0], LoOps[1], ISD::SETULT);
1806     SDValue Borrow = DAG.getSelect(dl, NVT, Cmp,
1807                                    DAG.getConstant(1, dl, NVT),
1808                                    DAG.getConstant(0, dl, NVT));
1809     Hi = DAG.getNode(ISD::SUB, dl, NVT, Hi, Borrow);
1810   }
1811 }
1812
1813 void DAGTypeLegalizer::ExpandIntRes_ADDSUBC(SDNode *N,
1814                                             SDValue &Lo, SDValue &Hi) {
1815   // Expand the subcomponents.
1816   SDValue LHSL, LHSH, RHSL, RHSH;
1817   SDLoc dl(N);
1818   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
1819   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
1820   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Glue);
1821   SDValue LoOps[2] = { LHSL, RHSL };
1822   SDValue HiOps[3] = { LHSH, RHSH };
1823
1824   if (N->getOpcode() == ISD::ADDC) {
1825     Lo = DAG.getNode(ISD::ADDC, dl, VTList, LoOps);
1826     HiOps[2] = Lo.getValue(1);
1827     Hi = DAG.getNode(ISD::ADDE, dl, VTList, HiOps);
1828   } else {
1829     Lo = DAG.getNode(ISD::SUBC, dl, VTList, LoOps);
1830     HiOps[2] = Lo.getValue(1);
1831     Hi = DAG.getNode(ISD::SUBE, dl, VTList, HiOps);
1832   }
1833
1834   // Legalized the flag result - switch anything that used the old flag to
1835   // use the new one.
1836   ReplaceValueWith(SDValue(N, 1), Hi.getValue(1));
1837 }
1838
1839 void DAGTypeLegalizer::ExpandIntRes_ADDSUBE(SDNode *N,
1840                                             SDValue &Lo, SDValue &Hi) {
1841   // Expand the subcomponents.
1842   SDValue LHSL, LHSH, RHSL, RHSH;
1843   SDLoc dl(N);
1844   GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
1845   GetExpandedInteger(N->getOperand(1), RHSL, RHSH);
1846   SDVTList VTList = DAG.getVTList(LHSL.getValueType(), MVT::Glue);
1847   SDValue LoOps[3] = { LHSL, RHSL, N->getOperand(2) };
1848   SDValue HiOps[3] = { LHSH, RHSH };
1849
1850   Lo = DAG.getNode(N->getOpcode(), dl, VTList, LoOps);
1851   HiOps[2] = Lo.getValue(1);
1852   Hi = DAG.getNode(N->getOpcode(), dl, VTList, HiOps);
1853
1854   // Legalized the flag result - switch anything that used the old flag to
1855   // use the new one.
1856   ReplaceValueWith(SDValue(N, 1), Hi.getValue(1));
1857 }
1858
1859 void DAGTypeLegalizer::ExpandIntRes_ANY_EXTEND(SDNode *N,
1860                                                SDValue &Lo, SDValue &Hi) {
1861   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1862   SDLoc dl(N);
1863   SDValue Op = N->getOperand(0);
1864   if (Op.getValueType().bitsLE(NVT)) {
1865     // The low part is any extension of the input (which degenerates to a copy).
1866     Lo = DAG.getNode(ISD::ANY_EXTEND, dl, NVT, Op);
1867     Hi = DAG.getUNDEF(NVT);   // The high part is undefined.
1868   } else {
1869     // For example, extension of an i48 to an i64.  The operand type necessarily
1870     // promotes to the result type, so will end up being expanded too.
1871     assert(getTypeAction(Op.getValueType()) ==
1872            TargetLowering::TypePromoteInteger &&
1873            "Only know how to promote this result!");
1874     SDValue Res = GetPromotedInteger(Op);
1875     assert(Res.getValueType() == N->getValueType(0) &&
1876            "Operand over promoted?");
1877     // Split the promoted operand.  This will simplify when it is expanded.
1878     SplitInteger(Res, Lo, Hi);
1879   }
1880 }
1881
1882 void DAGTypeLegalizer::ExpandIntRes_AssertSext(SDNode *N,
1883                                                SDValue &Lo, SDValue &Hi) {
1884   SDLoc dl(N);
1885   GetExpandedInteger(N->getOperand(0), Lo, Hi);
1886   EVT NVT = Lo.getValueType();
1887   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
1888   unsigned NVTBits = NVT.getSizeInBits();
1889   unsigned EVTBits = EVT.getSizeInBits();
1890
1891   if (NVTBits < EVTBits) {
1892     Hi = DAG.getNode(ISD::AssertSext, dl, NVT, Hi,
1893                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
1894                                                         EVTBits - NVTBits)));
1895   } else {
1896     Lo = DAG.getNode(ISD::AssertSext, dl, NVT, Lo, DAG.getValueType(EVT));
1897     // The high part replicates the sign bit of Lo, make it explicit.
1898     Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
1899                      DAG.getConstant(NVTBits - 1, dl,
1900                                      TLI.getPointerTy(DAG.getDataLayout())));
1901   }
1902 }
1903
1904 void DAGTypeLegalizer::ExpandIntRes_AssertZext(SDNode *N,
1905                                                SDValue &Lo, SDValue &Hi) {
1906   SDLoc dl(N);
1907   GetExpandedInteger(N->getOperand(0), Lo, Hi);
1908   EVT NVT = Lo.getValueType();
1909   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
1910   unsigned NVTBits = NVT.getSizeInBits();
1911   unsigned EVTBits = EVT.getSizeInBits();
1912
1913   if (NVTBits < EVTBits) {
1914     Hi = DAG.getNode(ISD::AssertZext, dl, NVT, Hi,
1915                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
1916                                                         EVTBits - NVTBits)));
1917   } else {
1918     Lo = DAG.getNode(ISD::AssertZext, dl, NVT, Lo, DAG.getValueType(EVT));
1919     // The high part must be zero, make it explicit.
1920     Hi = DAG.getConstant(0, dl, NVT);
1921   }
1922 }
1923
1924 void DAGTypeLegalizer::ExpandIntRes_BITREVERSE(SDNode *N,
1925                                                SDValue &Lo, SDValue &Hi) {
1926   SDLoc dl(N);
1927   GetExpandedInteger(N->getOperand(0), Hi, Lo);  // Note swapped operands.
1928   Lo = DAG.getNode(ISD::BITREVERSE, dl, Lo.getValueType(), Lo);
1929   Hi = DAG.getNode(ISD::BITREVERSE, dl, Hi.getValueType(), Hi);
1930 }
1931
1932 void DAGTypeLegalizer::ExpandIntRes_BSWAP(SDNode *N,
1933                                           SDValue &Lo, SDValue &Hi) {
1934   SDLoc dl(N);
1935   GetExpandedInteger(N->getOperand(0), Hi, Lo);  // Note swapped operands.
1936   Lo = DAG.getNode(ISD::BSWAP, dl, Lo.getValueType(), Lo);
1937   Hi = DAG.getNode(ISD::BSWAP, dl, Hi.getValueType(), Hi);
1938 }
1939
1940 void DAGTypeLegalizer::ExpandIntRes_Constant(SDNode *N,
1941                                              SDValue &Lo, SDValue &Hi) {
1942   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
1943   unsigned NBitWidth = NVT.getSizeInBits();
1944   auto Constant = cast<ConstantSDNode>(N);
1945   const APInt &Cst = Constant->getAPIntValue();
1946   bool IsTarget = Constant->isTargetOpcode();
1947   bool IsOpaque = Constant->isOpaque();
1948   SDLoc dl(N);
1949   Lo = DAG.getConstant(Cst.trunc(NBitWidth), dl, NVT, IsTarget, IsOpaque);
1950   Hi = DAG.getConstant(Cst.lshr(NBitWidth).trunc(NBitWidth), dl, NVT, IsTarget,
1951                        IsOpaque);
1952 }
1953
1954 void DAGTypeLegalizer::ExpandIntRes_CTLZ(SDNode *N,
1955                                          SDValue &Lo, SDValue &Hi) {
1956   SDLoc dl(N);
1957   // ctlz (HiLo) -> Hi != 0 ? ctlz(Hi) : (ctlz(Lo)+32)
1958   GetExpandedInteger(N->getOperand(0), Lo, Hi);
1959   EVT NVT = Lo.getValueType();
1960
1961   SDValue HiNotZero = DAG.getSetCC(dl, getSetCCResultType(NVT), Hi,
1962                                    DAG.getConstant(0, dl, NVT), ISD::SETNE);
1963
1964   SDValue LoLZ = DAG.getNode(N->getOpcode(), dl, NVT, Lo);
1965   SDValue HiLZ = DAG.getNode(ISD::CTLZ_ZERO_UNDEF, dl, NVT, Hi);
1966
1967   Lo = DAG.getSelect(dl, NVT, HiNotZero, HiLZ,
1968                      DAG.getNode(ISD::ADD, dl, NVT, LoLZ,
1969                                  DAG.getConstant(NVT.getSizeInBits(), dl,
1970                                                  NVT)));
1971   Hi = DAG.getConstant(0, dl, NVT);
1972 }
1973
1974 void DAGTypeLegalizer::ExpandIntRes_CTPOP(SDNode *N,
1975                                           SDValue &Lo, SDValue &Hi) {
1976   SDLoc dl(N);
1977   // ctpop(HiLo) -> ctpop(Hi)+ctpop(Lo)
1978   GetExpandedInteger(N->getOperand(0), Lo, Hi);
1979   EVT NVT = Lo.getValueType();
1980   Lo = DAG.getNode(ISD::ADD, dl, NVT, DAG.getNode(ISD::CTPOP, dl, NVT, Lo),
1981                    DAG.getNode(ISD::CTPOP, dl, NVT, Hi));
1982   Hi = DAG.getConstant(0, dl, NVT);
1983 }
1984
1985 void DAGTypeLegalizer::ExpandIntRes_CTTZ(SDNode *N,
1986                                          SDValue &Lo, SDValue &Hi) {
1987   SDLoc dl(N);
1988   // cttz (HiLo) -> Lo != 0 ? cttz(Lo) : (cttz(Hi)+32)
1989   GetExpandedInteger(N->getOperand(0), Lo, Hi);
1990   EVT NVT = Lo.getValueType();
1991
1992   SDValue LoNotZero = DAG.getSetCC(dl, getSetCCResultType(NVT), Lo,
1993                                    DAG.getConstant(0, dl, NVT), ISD::SETNE);
1994
1995   SDValue LoLZ = DAG.getNode(ISD::CTTZ_ZERO_UNDEF, dl, NVT, Lo);
1996   SDValue HiLZ = DAG.getNode(N->getOpcode(), dl, NVT, Hi);
1997
1998   Lo = DAG.getSelect(dl, NVT, LoNotZero, LoLZ,
1999                      DAG.getNode(ISD::ADD, dl, NVT, HiLZ,
2000                                  DAG.getConstant(NVT.getSizeInBits(), dl,
2001                                                  NVT)));
2002   Hi = DAG.getConstant(0, dl, NVT);
2003 }
2004
2005 void DAGTypeLegalizer::ExpandIntRes_FP_TO_SINT(SDNode *N, SDValue &Lo,
2006                                                SDValue &Hi) {
2007   SDLoc dl(N);
2008   EVT VT = N->getValueType(0);
2009
2010   SDValue Op = N->getOperand(0);
2011   if (getTypeAction(Op.getValueType()) == TargetLowering::TypePromoteFloat)
2012     Op = GetPromotedFloat(Op);
2013
2014   RTLIB::Libcall LC = RTLIB::getFPTOSINT(Op.getValueType(), VT);
2015   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected fp-to-sint conversion!");
2016   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Op, true/*irrelevant*/, dl).first,
2017                Lo, Hi);
2018 }
2019
2020 void DAGTypeLegalizer::ExpandIntRes_FP_TO_UINT(SDNode *N, SDValue &Lo,
2021                                                SDValue &Hi) {
2022   SDLoc dl(N);
2023   EVT VT = N->getValueType(0);
2024
2025   SDValue Op = N->getOperand(0);
2026   if (getTypeAction(Op.getValueType()) == TargetLowering::TypePromoteFloat)
2027     Op = GetPromotedFloat(Op);
2028
2029   RTLIB::Libcall LC = RTLIB::getFPTOUINT(Op.getValueType(), VT);
2030   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected fp-to-uint conversion!");
2031   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Op, false/*irrelevant*/, dl).first,
2032                Lo, Hi);
2033 }
2034
2035 void DAGTypeLegalizer::ExpandIntRes_LOAD(LoadSDNode *N,
2036                                          SDValue &Lo, SDValue &Hi) {
2037   if (ISD::isNormalLoad(N)) {
2038     ExpandRes_NormalLoad(N, Lo, Hi);
2039     return;
2040   }
2041
2042   assert(ISD::isUNINDEXEDLoad(N) && "Indexed load during type legalization!");
2043
2044   EVT VT = N->getValueType(0);
2045   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2046   SDValue Ch  = N->getChain();
2047   SDValue Ptr = N->getBasePtr();
2048   ISD::LoadExtType ExtType = N->getExtensionType();
2049   unsigned Alignment = N->getAlignment();
2050   MachineMemOperand::Flags MMOFlags = N->getMemOperand()->getFlags();
2051   AAMDNodes AAInfo = N->getAAInfo();
2052   SDLoc dl(N);
2053
2054   assert(NVT.isByteSized() && "Expanded type not byte sized!");
2055
2056   if (N->getMemoryVT().bitsLE(NVT)) {
2057     EVT MemVT = N->getMemoryVT();
2058
2059     Lo = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr, N->getPointerInfo(), MemVT,
2060                         Alignment, MMOFlags, AAInfo);
2061
2062     // Remember the chain.
2063     Ch = Lo.getValue(1);
2064
2065     if (ExtType == ISD::SEXTLOAD) {
2066       // The high part is obtained by SRA'ing all but one of the bits of the
2067       // lo part.
2068       unsigned LoSize = Lo.getValueType().getSizeInBits();
2069       Hi = DAG.getNode(ISD::SRA, dl, NVT, Lo,
2070                        DAG.getConstant(LoSize - 1, dl,
2071                                        TLI.getPointerTy(DAG.getDataLayout())));
2072     } else if (ExtType == ISD::ZEXTLOAD) {
2073       // The high part is just a zero.
2074       Hi = DAG.getConstant(0, dl, NVT);
2075     } else {
2076       assert(ExtType == ISD::EXTLOAD && "Unknown extload!");
2077       // The high part is undefined.
2078       Hi = DAG.getUNDEF(NVT);
2079     }
2080   } else if (DAG.getDataLayout().isLittleEndian()) {
2081     // Little-endian - low bits are at low addresses.
2082     Lo = DAG.getLoad(NVT, dl, Ch, Ptr, N->getPointerInfo(), Alignment, MMOFlags,
2083                      AAInfo);
2084
2085     unsigned ExcessBits =
2086       N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
2087     EVT NEVT = EVT::getIntegerVT(*DAG.getContext(), ExcessBits);
2088
2089     // Increment the pointer to the other half.
2090     unsigned IncrementSize = NVT.getSizeInBits()/8;
2091     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
2092                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
2093     Hi = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr,
2094                         N->getPointerInfo().getWithOffset(IncrementSize), NEVT,
2095                         MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
2096
2097     // Build a factor node to remember that this load is independent of the
2098     // other one.
2099     Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
2100                      Hi.getValue(1));
2101   } else {
2102     // Big-endian - high bits are at low addresses.  Favor aligned loads at
2103     // the cost of some bit-fiddling.
2104     EVT MemVT = N->getMemoryVT();
2105     unsigned EBytes = MemVT.getStoreSize();
2106     unsigned IncrementSize = NVT.getSizeInBits()/8;
2107     unsigned ExcessBits = (EBytes - IncrementSize)*8;
2108
2109     // Load both the high bits and maybe some of the low bits.
2110     Hi = DAG.getExtLoad(ExtType, dl, NVT, Ch, Ptr, N->getPointerInfo(),
2111                         EVT::getIntegerVT(*DAG.getContext(),
2112                                           MemVT.getSizeInBits() - ExcessBits),
2113                         Alignment, MMOFlags, AAInfo);
2114
2115     // Increment the pointer to the other half.
2116     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
2117                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
2118     // Load the rest of the low bits.
2119     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, NVT, Ch, Ptr,
2120                         N->getPointerInfo().getWithOffset(IncrementSize),
2121                         EVT::getIntegerVT(*DAG.getContext(), ExcessBits),
2122                         MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
2123
2124     // Build a factor node to remember that this load is independent of the
2125     // other one.
2126     Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
2127                      Hi.getValue(1));
2128
2129     if (ExcessBits < NVT.getSizeInBits()) {
2130       // Transfer low bits from the bottom of Hi to the top of Lo.
2131       Lo = DAG.getNode(
2132           ISD::OR, dl, NVT, Lo,
2133           DAG.getNode(ISD::SHL, dl, NVT, Hi,
2134                       DAG.getConstant(ExcessBits, dl,
2135                                       TLI.getPointerTy(DAG.getDataLayout()))));
2136       // Move high bits to the right position in Hi.
2137       Hi = DAG.getNode(ExtType == ISD::SEXTLOAD ? ISD::SRA : ISD::SRL, dl, NVT,
2138                        Hi,
2139                        DAG.getConstant(NVT.getSizeInBits() - ExcessBits, dl,
2140                                        TLI.getPointerTy(DAG.getDataLayout())));
2141     }
2142   }
2143
2144   // Legalize the chain result - switch anything that used the old chain to
2145   // use the new one.
2146   ReplaceValueWith(SDValue(N, 1), Ch);
2147 }
2148
2149 void DAGTypeLegalizer::ExpandIntRes_Logical(SDNode *N,
2150                                             SDValue &Lo, SDValue &Hi) {
2151   SDLoc dl(N);
2152   SDValue LL, LH, RL, RH;
2153   GetExpandedInteger(N->getOperand(0), LL, LH);
2154   GetExpandedInteger(N->getOperand(1), RL, RH);
2155   Lo = DAG.getNode(N->getOpcode(), dl, LL.getValueType(), LL, RL);
2156   Hi = DAG.getNode(N->getOpcode(), dl, LL.getValueType(), LH, RH);
2157 }
2158
2159 void DAGTypeLegalizer::ExpandIntRes_MUL(SDNode *N,
2160                                         SDValue &Lo, SDValue &Hi) {
2161   EVT VT = N->getValueType(0);
2162   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2163   SDLoc dl(N);
2164
2165   SDValue LL, LH, RL, RH;
2166   GetExpandedInteger(N->getOperand(0), LL, LH);
2167   GetExpandedInteger(N->getOperand(1), RL, RH);
2168
2169   if (TLI.expandMUL(N, Lo, Hi, NVT, DAG, LL, LH, RL, RH))
2170     return;
2171
2172   // If nothing else, we can make a libcall.
2173   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2174   if (VT == MVT::i16)
2175     LC = RTLIB::MUL_I16;
2176   else if (VT == MVT::i32)
2177     LC = RTLIB::MUL_I32;
2178   else if (VT == MVT::i64)
2179     LC = RTLIB::MUL_I64;
2180   else if (VT == MVT::i128)
2181     LC = RTLIB::MUL_I128;
2182
2183   if (LC == RTLIB::UNKNOWN_LIBCALL) {
2184     // We'll expand the multiplication by brute force because we have no other
2185     // options. This is a trivially-generalized version of the code from
2186     // Hacker's Delight (itself derived from Knuth's Algorithm M from section
2187     // 4.3.1).
2188     SDValue Mask =
2189       DAG.getConstant(APInt::getLowBitsSet(NVT.getSizeInBits(),
2190                                            NVT.getSizeInBits() >> 1), dl, NVT);
2191     SDValue LLL = DAG.getNode(ISD::AND, dl, NVT, LL, Mask);
2192     SDValue RLL = DAG.getNode(ISD::AND, dl, NVT, RL, Mask);
2193
2194     SDValue T = DAG.getNode(ISD::MUL, dl, NVT, LLL, RLL);
2195     SDValue TL = DAG.getNode(ISD::AND, dl, NVT, T, Mask);
2196
2197     SDValue Shift =
2198       DAG.getConstant(NVT.getSizeInBits() >> 1, dl,
2199                       TLI.getShiftAmountTy(NVT, DAG.getDataLayout()));
2200     SDValue TH = DAG.getNode(ISD::SRL, dl, NVT, T, Shift);
2201     SDValue LLH = DAG.getNode(ISD::SRL, dl, NVT, LL, Shift);
2202     SDValue RLH = DAG.getNode(ISD::SRL, dl, NVT, RL, Shift);
2203
2204     SDValue U = DAG.getNode(ISD::ADD, dl, NVT,
2205                             DAG.getNode(ISD::MUL, dl, NVT, LLH, RLL), TL);
2206     SDValue UL = DAG.getNode(ISD::AND, dl, NVT, U, Mask);
2207     SDValue UH = DAG.getNode(ISD::SRL, dl, NVT, U, Shift);
2208
2209     SDValue V = DAG.getNode(ISD::ADD, dl, NVT,
2210                             DAG.getNode(ISD::MUL, dl, NVT, LLL, RLH), UL);
2211     SDValue VH = DAG.getNode(ISD::SRL, dl, NVT, V, Shift);
2212
2213     SDValue W = DAG.getNode(ISD::ADD, dl, NVT,
2214                             DAG.getNode(ISD::MUL, dl, NVT, LL, RL),
2215                             DAG.getNode(ISD::ADD, dl, NVT, UH, VH));
2216     Lo = DAG.getNode(ISD::ADD, dl, NVT, TH,
2217                      DAG.getNode(ISD::SHL, dl, NVT, V, Shift));
2218
2219     Hi = DAG.getNode(ISD::ADD, dl, NVT, W,
2220                      DAG.getNode(ISD::ADD, dl, NVT,
2221                                  DAG.getNode(ISD::MUL, dl, NVT, RH, LL),
2222                                  DAG.getNode(ISD::MUL, dl, NVT, RL, LH)));
2223     return;
2224   }
2225
2226   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2227   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true/*irrelevant*/, dl).first,
2228                Lo, Hi);
2229 }
2230
2231 void DAGTypeLegalizer::ExpandIntRes_READCYCLECOUNTER(SDNode *N, SDValue &Lo,
2232                                                      SDValue &Hi) {
2233   SDLoc DL(N);
2234   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2235   SDVTList VTs = DAG.getVTList(NVT, NVT, MVT::Other);
2236   SDValue R = DAG.getNode(N->getOpcode(), DL, VTs, N->getOperand(0));
2237   Lo = R.getValue(0);
2238   Hi = R.getValue(1);
2239   ReplaceValueWith(SDValue(N, 1), R.getValue(2));
2240 }
2241
2242 void DAGTypeLegalizer::ExpandIntRes_SADDSUBO(SDNode *Node,
2243                                              SDValue &Lo, SDValue &Hi) {
2244   SDValue LHS = Node->getOperand(0);
2245   SDValue RHS = Node->getOperand(1);
2246   SDLoc dl(Node);
2247
2248   // Expand the result by simply replacing it with the equivalent
2249   // non-overflow-checking operation.
2250   SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ?
2251                             ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
2252                             LHS, RHS);
2253   SplitInteger(Sum, Lo, Hi);
2254
2255   // Compute the overflow.
2256   //
2257   //   LHSSign -> LHS >= 0
2258   //   RHSSign -> RHS >= 0
2259   //   SumSign -> Sum >= 0
2260   //
2261   //   Add:
2262   //   Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign)
2263   //   Sub:
2264   //   Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign)
2265   //
2266   EVT OType = Node->getValueType(1);
2267   SDValue Zero = DAG.getConstant(0, dl, LHS.getValueType());
2268
2269   SDValue LHSSign = DAG.getSetCC(dl, OType, LHS, Zero, ISD::SETGE);
2270   SDValue RHSSign = DAG.getSetCC(dl, OType, RHS, Zero, ISD::SETGE);
2271   SDValue SignsMatch = DAG.getSetCC(dl, OType, LHSSign, RHSSign,
2272                                     Node->getOpcode() == ISD::SADDO ?
2273                                     ISD::SETEQ : ISD::SETNE);
2274
2275   SDValue SumSign = DAG.getSetCC(dl, OType, Sum, Zero, ISD::SETGE);
2276   SDValue SumSignNE = DAG.getSetCC(dl, OType, LHSSign, SumSign, ISD::SETNE);
2277
2278   SDValue Cmp = DAG.getNode(ISD::AND, dl, OType, SignsMatch, SumSignNE);
2279
2280   // Use the calculated overflow everywhere.
2281   ReplaceValueWith(SDValue(Node, 1), Cmp);
2282 }
2283
2284 void DAGTypeLegalizer::ExpandIntRes_SDIV(SDNode *N,
2285                                          SDValue &Lo, SDValue &Hi) {
2286   EVT VT = N->getValueType(0);
2287   SDLoc dl(N);
2288   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2289
2290   if (TLI.getOperationAction(ISD::SDIVREM, VT) == TargetLowering::Custom) {
2291     SDValue Res = DAG.getNode(ISD::SDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2292     SplitInteger(Res.getValue(0), Lo, Hi);
2293     return;
2294   }
2295
2296   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2297   if (VT == MVT::i16)
2298     LC = RTLIB::SDIV_I16;
2299   else if (VT == MVT::i32)
2300     LC = RTLIB::SDIV_I32;
2301   else if (VT == MVT::i64)
2302     LC = RTLIB::SDIV_I64;
2303   else if (VT == MVT::i128)
2304     LC = RTLIB::SDIV_I128;
2305   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SDIV!");
2306
2307   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true, dl).first, Lo, Hi);
2308 }
2309
2310 void DAGTypeLegalizer::ExpandIntRes_Shift(SDNode *N,
2311                                           SDValue &Lo, SDValue &Hi) {
2312   EVT VT = N->getValueType(0);
2313   SDLoc dl(N);
2314
2315   // If we can emit an efficient shift operation, do so now.  Check to see if
2316   // the RHS is a constant.
2317   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2318     return ExpandShiftByConstant(N, CN->getAPIntValue(), Lo, Hi);
2319
2320   // If we can determine that the high bit of the shift is zero or one, even if
2321   // the low bits are variable, emit this shift in an optimized form.
2322   if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
2323     return;
2324
2325   // If this target supports shift_PARTS, use it.  First, map to the _PARTS opc.
2326   unsigned PartsOpc;
2327   if (N->getOpcode() == ISD::SHL) {
2328     PartsOpc = ISD::SHL_PARTS;
2329   } else if (N->getOpcode() == ISD::SRL) {
2330     PartsOpc = ISD::SRL_PARTS;
2331   } else {
2332     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
2333     PartsOpc = ISD::SRA_PARTS;
2334   }
2335
2336   // Next check to see if the target supports this SHL_PARTS operation or if it
2337   // will custom expand it.
2338   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2339   TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
2340   if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
2341       Action == TargetLowering::Custom) {
2342     // Expand the subcomponents.
2343     SDValue LHSL, LHSH;
2344     GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
2345     EVT VT = LHSL.getValueType();
2346
2347     // If the shift amount operand is coming from a vector legalization it may
2348     // have an illegal type.  Fix that first by casting the operand, otherwise
2349     // the new SHL_PARTS operation would need further legalization.
2350     SDValue ShiftOp = N->getOperand(1);
2351     EVT ShiftTy = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
2352     assert(ShiftTy.getScalarType().getSizeInBits() >=
2353            Log2_32_Ceil(VT.getScalarType().getSizeInBits()) &&
2354            "ShiftAmountTy is too small to cover the range of this type!");
2355     if (ShiftOp.getValueType() != ShiftTy)
2356       ShiftOp = DAG.getZExtOrTrunc(ShiftOp, dl, ShiftTy);
2357
2358     SDValue Ops[] = { LHSL, LHSH, ShiftOp };
2359     Lo = DAG.getNode(PartsOpc, dl, DAG.getVTList(VT, VT), Ops);
2360     Hi = Lo.getValue(1);
2361     return;
2362   }
2363
2364   // Otherwise, emit a libcall.
2365   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2366   bool isSigned;
2367   if (N->getOpcode() == ISD::SHL) {
2368     isSigned = false; /*sign irrelevant*/
2369     if (VT == MVT::i16)
2370       LC = RTLIB::SHL_I16;
2371     else if (VT == MVT::i32)
2372       LC = RTLIB::SHL_I32;
2373     else if (VT == MVT::i64)
2374       LC = RTLIB::SHL_I64;
2375     else if (VT == MVT::i128)
2376       LC = RTLIB::SHL_I128;
2377   } else if (N->getOpcode() == ISD::SRL) {
2378     isSigned = false;
2379     if (VT == MVT::i16)
2380       LC = RTLIB::SRL_I16;
2381     else if (VT == MVT::i32)
2382       LC = RTLIB::SRL_I32;
2383     else if (VT == MVT::i64)
2384       LC = RTLIB::SRL_I64;
2385     else if (VT == MVT::i128)
2386       LC = RTLIB::SRL_I128;
2387   } else {
2388     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
2389     isSigned = true;
2390     if (VT == MVT::i16)
2391       LC = RTLIB::SRA_I16;
2392     else if (VT == MVT::i32)
2393       LC = RTLIB::SRA_I32;
2394     else if (VT == MVT::i64)
2395       LC = RTLIB::SRA_I64;
2396     else if (VT == MVT::i128)
2397       LC = RTLIB::SRA_I128;
2398   }
2399
2400   if (LC != RTLIB::UNKNOWN_LIBCALL && TLI.getLibcallName(LC)) {
2401     SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2402     SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, isSigned, dl).first, Lo, Hi);
2403     return;
2404   }
2405
2406   if (!ExpandShiftWithUnknownAmountBit(N, Lo, Hi))
2407     llvm_unreachable("Unsupported shift!");
2408 }
2409
2410 void DAGTypeLegalizer::ExpandIntRes_SIGN_EXTEND(SDNode *N,
2411                                                 SDValue &Lo, SDValue &Hi) {
2412   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2413   SDLoc dl(N);
2414   SDValue Op = N->getOperand(0);
2415   if (Op.getValueType().bitsLE(NVT)) {
2416     // The low part is sign extension of the input (degenerates to a copy).
2417     Lo = DAG.getNode(ISD::SIGN_EXTEND, dl, NVT, N->getOperand(0));
2418     // The high part is obtained by SRA'ing all but one of the bits of low part.
2419     unsigned LoSize = NVT.getSizeInBits();
2420     Hi = DAG.getNode(
2421         ISD::SRA, dl, NVT, Lo,
2422         DAG.getConstant(LoSize - 1, dl, TLI.getPointerTy(DAG.getDataLayout())));
2423   } else {
2424     // For example, extension of an i48 to an i64.  The operand type necessarily
2425     // promotes to the result type, so will end up being expanded too.
2426     assert(getTypeAction(Op.getValueType()) ==
2427            TargetLowering::TypePromoteInteger &&
2428            "Only know how to promote this result!");
2429     SDValue Res = GetPromotedInteger(Op);
2430     assert(Res.getValueType() == N->getValueType(0) &&
2431            "Operand over promoted?");
2432     // Split the promoted operand.  This will simplify when it is expanded.
2433     SplitInteger(Res, Lo, Hi);
2434     unsigned ExcessBits =
2435       Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
2436     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
2437                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
2438                                                         ExcessBits)));
2439   }
2440 }
2441
2442 void DAGTypeLegalizer::
2443 ExpandIntRes_SIGN_EXTEND_INREG(SDNode *N, SDValue &Lo, SDValue &Hi) {
2444   SDLoc dl(N);
2445   GetExpandedInteger(N->getOperand(0), Lo, Hi);
2446   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
2447
2448   if (EVT.bitsLE(Lo.getValueType())) {
2449     // sext_inreg the low part if needed.
2450     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Lo.getValueType(), Lo,
2451                      N->getOperand(1));
2452
2453     // The high part gets the sign extension from the lo-part.  This handles
2454     // things like sextinreg V:i64 from i8.
2455     Hi = DAG.getNode(ISD::SRA, dl, Hi.getValueType(), Lo,
2456                      DAG.getConstant(Hi.getValueType().getSizeInBits() - 1, dl,
2457                                      TLI.getPointerTy(DAG.getDataLayout())));
2458   } else {
2459     // For example, extension of an i48 to an i64.  Leave the low part alone,
2460     // sext_inreg the high part.
2461     unsigned ExcessBits =
2462       EVT.getSizeInBits() - Lo.getValueType().getSizeInBits();
2463     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
2464                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
2465                                                         ExcessBits)));
2466   }
2467 }
2468
2469 void DAGTypeLegalizer::ExpandIntRes_SREM(SDNode *N,
2470                                          SDValue &Lo, SDValue &Hi) {
2471   EVT VT = N->getValueType(0);
2472   SDLoc dl(N);
2473   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2474
2475   if (TLI.getOperationAction(ISD::SDIVREM, VT) == TargetLowering::Custom) {
2476     SDValue Res = DAG.getNode(ISD::SDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2477     SplitInteger(Res.getValue(1), Lo, Hi);
2478     return;
2479   }
2480
2481   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2482   if (VT == MVT::i16)
2483     LC = RTLIB::SREM_I16;
2484   else if (VT == MVT::i32)
2485     LC = RTLIB::SREM_I32;
2486   else if (VT == MVT::i64)
2487     LC = RTLIB::SREM_I64;
2488   else if (VT == MVT::i128)
2489     LC = RTLIB::SREM_I128;
2490   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SREM!");
2491
2492   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true, dl).first, Lo, Hi);
2493 }
2494
2495 void DAGTypeLegalizer::ExpandIntRes_TRUNCATE(SDNode *N,
2496                                              SDValue &Lo, SDValue &Hi) {
2497   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2498   SDLoc dl(N);
2499   Lo = DAG.getNode(ISD::TRUNCATE, dl, NVT, N->getOperand(0));
2500   Hi = DAG.getNode(ISD::SRL, dl, N->getOperand(0).getValueType(),
2501                    N->getOperand(0),
2502                    DAG.getConstant(NVT.getSizeInBits(), dl,
2503                                    TLI.getPointerTy(DAG.getDataLayout())));
2504   Hi = DAG.getNode(ISD::TRUNCATE, dl, NVT, Hi);
2505 }
2506
2507 void DAGTypeLegalizer::ExpandIntRes_UADDSUBO(SDNode *N,
2508                                              SDValue &Lo, SDValue &Hi) {
2509   SDValue LHS = N->getOperand(0);
2510   SDValue RHS = N->getOperand(1);
2511   SDLoc dl(N);
2512
2513   // Expand the result by simply replacing it with the equivalent
2514   // non-overflow-checking operation.
2515   SDValue Sum = DAG.getNode(N->getOpcode() == ISD::UADDO ?
2516                             ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
2517                             LHS, RHS);
2518   SplitInteger(Sum, Lo, Hi);
2519
2520   // Calculate the overflow: addition overflows iff a + b < a, and subtraction
2521   // overflows iff a - b > a.
2522   SDValue Ofl = DAG.getSetCC(dl, N->getValueType(1), Sum, LHS,
2523                              N->getOpcode () == ISD::UADDO ?
2524                              ISD::SETULT : ISD::SETUGT);
2525
2526   // Use the calculated overflow everywhere.
2527   ReplaceValueWith(SDValue(N, 1), Ofl);
2528 }
2529
2530 void DAGTypeLegalizer::ExpandIntRes_XMULO(SDNode *N,
2531                                           SDValue &Lo, SDValue &Hi) {
2532   EVT VT = N->getValueType(0);
2533   SDLoc dl(N);
2534
2535   // A divide for UMULO should be faster than a function call.
2536   if (N->getOpcode() == ISD::UMULO) {
2537     SDValue LHS = N->getOperand(0), RHS = N->getOperand(1);
2538
2539     SDValue MUL = DAG.getNode(ISD::MUL, dl, LHS.getValueType(), LHS, RHS);
2540     SplitInteger(MUL, Lo, Hi);
2541
2542     // A divide for UMULO will be faster than a function call. Select to
2543     // make sure we aren't using 0.
2544     SDValue isZero = DAG.getSetCC(dl, getSetCCResultType(VT),
2545                                   RHS, DAG.getConstant(0, dl, VT), ISD::SETEQ);
2546     SDValue NotZero = DAG.getSelect(dl, VT, isZero,
2547                                     DAG.getConstant(1, dl, VT), RHS);
2548     SDValue DIV = DAG.getNode(ISD::UDIV, dl, VT, MUL, NotZero);
2549     SDValue Overflow = DAG.getSetCC(dl, N->getValueType(1), DIV, LHS,
2550                                     ISD::SETNE);
2551     Overflow = DAG.getSelect(dl, N->getValueType(1), isZero,
2552                              DAG.getConstant(0, dl, N->getValueType(1)),
2553                              Overflow);
2554     ReplaceValueWith(SDValue(N, 1), Overflow);
2555     return;
2556   }
2557
2558   Type *RetTy = VT.getTypeForEVT(*DAG.getContext());
2559   EVT PtrVT = TLI.getPointerTy(DAG.getDataLayout());
2560   Type *PtrTy = PtrVT.getTypeForEVT(*DAG.getContext());
2561
2562   // Replace this with a libcall that will check overflow.
2563   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2564   if (VT == MVT::i32)
2565     LC = RTLIB::MULO_I32;
2566   else if (VT == MVT::i64)
2567     LC = RTLIB::MULO_I64;
2568   else if (VT == MVT::i128)
2569     LC = RTLIB::MULO_I128;
2570   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported XMULO!");
2571
2572   SDValue Temp = DAG.CreateStackTemporary(PtrVT);
2573   // Temporary for the overflow value, default it to zero.
2574   SDValue Chain =
2575       DAG.getStore(DAG.getEntryNode(), dl, DAG.getConstant(0, dl, PtrVT), Temp,
2576                    MachinePointerInfo());
2577
2578   TargetLowering::ArgListTy Args;
2579   TargetLowering::ArgListEntry Entry;
2580   for (const SDValue &Op : N->op_values()) {
2581     EVT ArgVT = Op.getValueType();
2582     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
2583     Entry.Node = Op;
2584     Entry.Ty = ArgTy;
2585     Entry.isSExt = true;
2586     Entry.isZExt = false;
2587     Args.push_back(Entry);
2588   }
2589
2590   // Also pass the address of the overflow check.
2591   Entry.Node = Temp;
2592   Entry.Ty = PtrTy->getPointerTo();
2593   Entry.isSExt = true;
2594   Entry.isZExt = false;
2595   Args.push_back(Entry);
2596
2597   SDValue Func = DAG.getExternalSymbol(TLI.getLibcallName(LC), PtrVT);
2598
2599   TargetLowering::CallLoweringInfo CLI(DAG);
2600   CLI.setDebugLoc(dl).setChain(Chain)
2601     .setCallee(TLI.getLibcallCallingConv(LC), RetTy, Func, std::move(Args))
2602     .setSExtResult();
2603
2604   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
2605
2606   SplitInteger(CallInfo.first, Lo, Hi);
2607   SDValue Temp2 =
2608       DAG.getLoad(PtrVT, dl, CallInfo.second, Temp, MachinePointerInfo());
2609   SDValue Ofl = DAG.getSetCC(dl, N->getValueType(1), Temp2,
2610                              DAG.getConstant(0, dl, PtrVT),
2611                              ISD::SETNE);
2612   // Use the overflow from the libcall everywhere.
2613   ReplaceValueWith(SDValue(N, 1), Ofl);
2614 }
2615
2616 void DAGTypeLegalizer::ExpandIntRes_UDIV(SDNode *N,
2617                                          SDValue &Lo, SDValue &Hi) {
2618   EVT VT = N->getValueType(0);
2619   SDLoc dl(N);
2620   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2621
2622   if (TLI.getOperationAction(ISD::UDIVREM, VT) == TargetLowering::Custom) {
2623     SDValue Res = DAG.getNode(ISD::UDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2624     SplitInteger(Res.getValue(0), Lo, Hi);
2625     return;
2626   }
2627
2628   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2629   if (VT == MVT::i16)
2630     LC = RTLIB::UDIV_I16;
2631   else if (VT == MVT::i32)
2632     LC = RTLIB::UDIV_I32;
2633   else if (VT == MVT::i64)
2634     LC = RTLIB::UDIV_I64;
2635   else if (VT == MVT::i128)
2636     LC = RTLIB::UDIV_I128;
2637   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UDIV!");
2638
2639   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, false, dl).first, Lo, Hi);
2640 }
2641
2642 void DAGTypeLegalizer::ExpandIntRes_UREM(SDNode *N,
2643                                          SDValue &Lo, SDValue &Hi) {
2644   EVT VT = N->getValueType(0);
2645   SDLoc dl(N);
2646   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2647
2648   if (TLI.getOperationAction(ISD::UDIVREM, VT) == TargetLowering::Custom) {
2649     SDValue Res = DAG.getNode(ISD::UDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2650     SplitInteger(Res.getValue(1), Lo, Hi);
2651     return;
2652   }
2653
2654   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2655   if (VT == MVT::i16)
2656     LC = RTLIB::UREM_I16;
2657   else if (VT == MVT::i32)
2658     LC = RTLIB::UREM_I32;
2659   else if (VT == MVT::i64)
2660     LC = RTLIB::UREM_I64;
2661   else if (VT == MVT::i128)
2662     LC = RTLIB::UREM_I128;
2663   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UREM!");
2664
2665   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, false, dl).first, Lo, Hi);
2666 }
2667
2668 void DAGTypeLegalizer::ExpandIntRes_ZERO_EXTEND(SDNode *N,
2669                                                 SDValue &Lo, SDValue &Hi) {
2670   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2671   SDLoc dl(N);
2672   SDValue Op = N->getOperand(0);
2673   if (Op.getValueType().bitsLE(NVT)) {
2674     // The low part is zero extension of the input (degenerates to a copy).
2675     Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, N->getOperand(0));
2676     Hi = DAG.getConstant(0, dl, NVT);   // The high part is just a zero.
2677   } else {
2678     // For example, extension of an i48 to an i64.  The operand type necessarily
2679     // promotes to the result type, so will end up being expanded too.
2680     assert(getTypeAction(Op.getValueType()) ==
2681            TargetLowering::TypePromoteInteger &&
2682            "Only know how to promote this result!");
2683     SDValue Res = GetPromotedInteger(Op);
2684     assert(Res.getValueType() == N->getValueType(0) &&
2685            "Operand over promoted?");
2686     // Split the promoted operand.  This will simplify when it is expanded.
2687     SplitInteger(Res, Lo, Hi);
2688     unsigned ExcessBits =
2689       Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
2690     Hi = DAG.getZeroExtendInReg(Hi, dl,
2691                                 EVT::getIntegerVT(*DAG.getContext(),
2692                                                   ExcessBits));
2693   }
2694 }
2695
2696 void DAGTypeLegalizer::ExpandIntRes_ATOMIC_LOAD(SDNode *N,
2697                                                 SDValue &Lo, SDValue &Hi) {
2698   SDLoc dl(N);
2699   EVT VT = cast<AtomicSDNode>(N)->getMemoryVT();
2700   SDVTList VTs = DAG.getVTList(VT, MVT::i1, MVT::Other);
2701   SDValue Zero = DAG.getConstant(0, dl, VT);
2702   SDValue Swap = DAG.getAtomicCmpSwap(
2703       ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS, dl,
2704       cast<AtomicSDNode>(N)->getMemoryVT(), VTs, N->getOperand(0),
2705       N->getOperand(1), Zero, Zero, cast<AtomicSDNode>(N)->getMemOperand(),
2706       cast<AtomicSDNode>(N)->getOrdering(),
2707       cast<AtomicSDNode>(N)->getOrdering(),
2708       cast<AtomicSDNode>(N)->getSynchScope());
2709
2710   ReplaceValueWith(SDValue(N, 0), Swap.getValue(0));
2711   ReplaceValueWith(SDValue(N, 1), Swap.getValue(2));
2712 }
2713
2714 //===----------------------------------------------------------------------===//
2715 //  Integer Operand Expansion
2716 //===----------------------------------------------------------------------===//
2717
2718 /// ExpandIntegerOperand - This method is called when the specified operand of
2719 /// the specified node is found to need expansion.  At this point, all of the
2720 /// result types of the node are known to be legal, but other operands of the
2721 /// node may need promotion or expansion as well as the specified one.
2722 bool DAGTypeLegalizer::ExpandIntegerOperand(SDNode *N, unsigned OpNo) {
2723   DEBUG(dbgs() << "Expand integer operand: "; N->dump(&DAG); dbgs() << "\n");
2724   SDValue Res = SDValue();
2725
2726   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
2727     return false;
2728
2729   switch (N->getOpcode()) {
2730   default:
2731   #ifndef NDEBUG
2732     dbgs() << "ExpandIntegerOperand Op #" << OpNo << ": ";
2733     N->dump(&DAG); dbgs() << "\n";
2734   #endif
2735     llvm_unreachable("Do not know how to expand this operator's operand!");
2736
2737   case ISD::BITCAST:           Res = ExpandOp_BITCAST(N); break;
2738   case ISD::BR_CC:             Res = ExpandIntOp_BR_CC(N); break;
2739   case ISD::BUILD_VECTOR:      Res = ExpandOp_BUILD_VECTOR(N); break;
2740   case ISD::EXTRACT_ELEMENT:   Res = ExpandOp_EXTRACT_ELEMENT(N); break;
2741   case ISD::INSERT_VECTOR_ELT: Res = ExpandOp_INSERT_VECTOR_ELT(N); break;
2742   case ISD::SCALAR_TO_VECTOR:  Res = ExpandOp_SCALAR_TO_VECTOR(N); break;
2743   case ISD::SELECT_CC:         Res = ExpandIntOp_SELECT_CC(N); break;
2744   case ISD::SETCC:             Res = ExpandIntOp_SETCC(N); break;
2745   case ISD::SETCCE:            Res = ExpandIntOp_SETCCE(N); break;
2746   case ISD::SINT_TO_FP:        Res = ExpandIntOp_SINT_TO_FP(N); break;
2747   case ISD::STORE:   Res = ExpandIntOp_STORE(cast<StoreSDNode>(N), OpNo); break;
2748   case ISD::TRUNCATE:          Res = ExpandIntOp_TRUNCATE(N); break;
2749   case ISD::UINT_TO_FP:        Res = ExpandIntOp_UINT_TO_FP(N); break;
2750
2751   case ISD::SHL:
2752   case ISD::SRA:
2753   case ISD::SRL:
2754   case ISD::ROTL:
2755   case ISD::ROTR:              Res = ExpandIntOp_Shift(N); break;
2756   case ISD::RETURNADDR:
2757   case ISD::FRAMEADDR:         Res = ExpandIntOp_RETURNADDR(N); break;
2758
2759   case ISD::ATOMIC_STORE:      Res = ExpandIntOp_ATOMIC_STORE(N); break;
2760   }
2761
2762   // If the result is null, the sub-method took care of registering results etc.
2763   if (!Res.getNode()) return false;
2764
2765   // If the result is N, the sub-method updated N in place.  Tell the legalizer
2766   // core about this.
2767   if (Res.getNode() == N)
2768     return true;
2769
2770   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
2771          "Invalid operand expansion");
2772
2773   ReplaceValueWith(SDValue(N, 0), Res);
2774   return false;
2775 }
2776
2777 /// IntegerExpandSetCCOperands - Expand the operands of a comparison.  This code
2778 /// is shared among BR_CC, SELECT_CC, and SETCC handlers.
2779 void DAGTypeLegalizer::IntegerExpandSetCCOperands(SDValue &NewLHS,
2780                                                   SDValue &NewRHS,
2781                                                   ISD::CondCode &CCCode,
2782                                                   const SDLoc &dl) {
2783   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
2784   GetExpandedInteger(NewLHS, LHSLo, LHSHi);
2785   GetExpandedInteger(NewRHS, RHSLo, RHSHi);
2786
2787   if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
2788     if (RHSLo == RHSHi) {
2789       if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) {
2790         if (RHSCST->isAllOnesValue()) {
2791           // Equality comparison to -1.
2792           NewLHS = DAG.getNode(ISD::AND, dl,
2793                                LHSLo.getValueType(), LHSLo, LHSHi);
2794           NewRHS = RHSLo;
2795           return;
2796         }
2797       }
2798     }
2799
2800     NewLHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSLo, RHSLo);
2801     NewRHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSHi, RHSHi);
2802     NewLHS = DAG.getNode(ISD::OR, dl, NewLHS.getValueType(), NewLHS, NewRHS);
2803     NewRHS = DAG.getConstant(0, dl, NewLHS.getValueType());
2804     return;
2805   }
2806
2807   // If this is a comparison of the sign bit, just look at the top part.
2808   // X > -1,  x < 0
2809   if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
2810     if ((CCCode == ISD::SETLT && CST->isNullValue()) ||     // X < 0
2811         (CCCode == ISD::SETGT && CST->isAllOnesValue())) {  // X > -1
2812       NewLHS = LHSHi;
2813       NewRHS = RHSHi;
2814       return;
2815     }
2816
2817   // FIXME: This generated code sucks.
2818   ISD::CondCode LowCC;
2819   switch (CCCode) {
2820   default: llvm_unreachable("Unknown integer setcc!");
2821   case ISD::SETLT:
2822   case ISD::SETULT: LowCC = ISD::SETULT; break;
2823   case ISD::SETGT:
2824   case ISD::SETUGT: LowCC = ISD::SETUGT; break;
2825   case ISD::SETLE:
2826   case ISD::SETULE: LowCC = ISD::SETULE; break;
2827   case ISD::SETGE:
2828   case ISD::SETUGE: LowCC = ISD::SETUGE; break;
2829   }
2830
2831   // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
2832   // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
2833   // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
2834
2835   // NOTE: on targets without efficient SELECT of bools, we can always use
2836   // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
2837   TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, AfterLegalizeTypes, true,
2838                                                  nullptr);
2839   SDValue Tmp1, Tmp2;
2840   if (TLI.isTypeLegal(LHSLo.getValueType()) &&
2841       TLI.isTypeLegal(RHSLo.getValueType()))
2842     Tmp1 = TLI.SimplifySetCC(getSetCCResultType(LHSLo.getValueType()),
2843                              LHSLo, RHSLo, LowCC, false, DagCombineInfo, dl);
2844   if (!Tmp1.getNode())
2845     Tmp1 = DAG.getSetCC(dl, getSetCCResultType(LHSLo.getValueType()),
2846                         LHSLo, RHSLo, LowCC);
2847   if (TLI.isTypeLegal(LHSHi.getValueType()) &&
2848       TLI.isTypeLegal(RHSHi.getValueType()))
2849     Tmp2 = TLI.SimplifySetCC(getSetCCResultType(LHSHi.getValueType()),
2850                              LHSHi, RHSHi, CCCode, false, DagCombineInfo, dl);
2851   if (!Tmp2.getNode())
2852     Tmp2 = DAG.getNode(ISD::SETCC, dl,
2853                        getSetCCResultType(LHSHi.getValueType()),
2854                        LHSHi, RHSHi, DAG.getCondCode(CCCode));
2855
2856   ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.getNode());
2857   ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.getNode());
2858   if ((Tmp1C && Tmp1C->isNullValue()) ||
2859       (Tmp2C && Tmp2C->isNullValue() &&
2860        (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
2861         CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) ||
2862       (Tmp2C && Tmp2C->getAPIntValue() == 1 &&
2863        (CCCode == ISD::SETLT || CCCode == ISD::SETGT ||
2864         CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) {
2865     // low part is known false, returns high part.
2866     // For LE / GE, if high part is known false, ignore the low part.
2867     // For LT / GT, if high part is known true, ignore the low part.
2868     NewLHS = Tmp2;
2869     NewRHS = SDValue();
2870     return;
2871   }
2872
2873   if (LHSHi == RHSHi) {
2874     // Comparing the low bits is enough.
2875     NewLHS = Tmp1;
2876     NewRHS = SDValue();
2877     return;
2878   }
2879
2880   // Lower with SETCCE if the target supports it.
2881   // FIXME: Make all targets support this, then remove the other lowering.
2882   if (TLI.getOperationAction(
2883           ISD::SETCCE,
2884           TLI.getTypeToExpandTo(*DAG.getContext(), LHSLo.getValueType())) ==
2885       TargetLowering::Custom) {
2886     // SETCCE can detect < and >= directly. For > and <=, flip operands and
2887     // condition code.
2888     bool FlipOperands = false;
2889     switch (CCCode) {
2890     case ISD::SETGT:  CCCode = ISD::SETLT;  FlipOperands = true; break;
2891     case ISD::SETUGT: CCCode = ISD::SETULT; FlipOperands = true; break;
2892     case ISD::SETLE:  CCCode = ISD::SETGE;  FlipOperands = true; break;
2893     case ISD::SETULE: CCCode = ISD::SETUGE; FlipOperands = true; break;
2894     default: break;
2895     }
2896     if (FlipOperands) {
2897       std::swap(LHSLo, RHSLo);
2898       std::swap(LHSHi, RHSHi);
2899     }
2900     // Perform a wide subtraction, feeding the carry from the low part into
2901     // SETCCE. The SETCCE operation is essentially looking at the high part of
2902     // the result of LHS - RHS. It is negative iff LHS < RHS. It is zero or
2903     // positive iff LHS >= RHS.
2904     SDVTList VTList = DAG.getVTList(LHSLo.getValueType(), MVT::Glue);
2905     SDValue LowCmp = DAG.getNode(ISD::SUBC, dl, VTList, LHSLo, RHSLo);
2906     SDValue Res =
2907         DAG.getNode(ISD::SETCCE, dl, getSetCCResultType(LHSLo.getValueType()),
2908                     LHSHi, RHSHi, LowCmp.getValue(1), DAG.getCondCode(CCCode));
2909     NewLHS = Res;
2910     NewRHS = SDValue();
2911     return;
2912   }
2913
2914   NewLHS = TLI.SimplifySetCC(getSetCCResultType(LHSHi.getValueType()),
2915                              LHSHi, RHSHi, ISD::SETEQ, false,
2916                              DagCombineInfo, dl);
2917   if (!NewLHS.getNode())
2918     NewLHS = DAG.getSetCC(dl, getSetCCResultType(LHSHi.getValueType()),
2919                           LHSHi, RHSHi, ISD::SETEQ);
2920   NewLHS = DAG.getSelect(dl, Tmp1.getValueType(),
2921                          NewLHS, Tmp1, Tmp2);
2922   NewRHS = SDValue();
2923 }
2924
2925 SDValue DAGTypeLegalizer::ExpandIntOp_BR_CC(SDNode *N) {
2926   SDValue NewLHS = N->getOperand(2), NewRHS = N->getOperand(3);
2927   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(1))->get();
2928   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
2929
2930   // If ExpandSetCCOperands returned a scalar, we need to compare the result
2931   // against zero to select between true and false values.
2932   if (!NewRHS.getNode()) {
2933     NewRHS = DAG.getConstant(0, SDLoc(N), NewLHS.getValueType());
2934     CCCode = ISD::SETNE;
2935   }
2936
2937   // Update N to have the operands specified.
2938   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
2939                                 DAG.getCondCode(CCCode), NewLHS, NewRHS,
2940                                 N->getOperand(4)), 0);
2941 }
2942
2943 SDValue DAGTypeLegalizer::ExpandIntOp_SELECT_CC(SDNode *N) {
2944   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
2945   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(4))->get();
2946   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
2947
2948   // If ExpandSetCCOperands returned a scalar, we need to compare the result
2949   // against zero to select between true and false values.
2950   if (!NewRHS.getNode()) {
2951     NewRHS = DAG.getConstant(0, SDLoc(N), NewLHS.getValueType());
2952     CCCode = ISD::SETNE;
2953   }
2954
2955   // Update N to have the operands specified.
2956   return SDValue(DAG.UpdateNodeOperands(N, NewLHS, NewRHS,
2957                                 N->getOperand(2), N->getOperand(3),
2958                                 DAG.getCondCode(CCCode)), 0);
2959 }
2960
2961 SDValue DAGTypeLegalizer::ExpandIntOp_SETCC(SDNode *N) {
2962   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
2963   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
2964   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
2965
2966   // If ExpandSetCCOperands returned a scalar, use it.
2967   if (!NewRHS.getNode()) {
2968     assert(NewLHS.getValueType() == N->getValueType(0) &&
2969            "Unexpected setcc expansion!");
2970     return NewLHS;
2971   }
2972
2973   // Otherwise, update N to have the operands specified.
2974   return SDValue(DAG.UpdateNodeOperands(N, NewLHS, NewRHS,
2975                                 DAG.getCondCode(CCCode)), 0);
2976 }
2977
2978 SDValue DAGTypeLegalizer::ExpandIntOp_SETCCE(SDNode *N) {
2979   SDValue LHS = N->getOperand(0);
2980   SDValue RHS = N->getOperand(1);
2981   SDValue Carry = N->getOperand(2);
2982   SDValue Cond = N->getOperand(3);
2983   SDLoc dl = SDLoc(N);
2984
2985   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
2986   GetExpandedInteger(LHS, LHSLo, LHSHi);
2987   GetExpandedInteger(RHS, RHSLo, RHSHi);
2988
2989   // Expand to a SUBE for the low part and a smaller SETCCE for the high.
2990   SDVTList VTList = DAG.getVTList(LHSLo.getValueType(), MVT::Glue);
2991   SDValue LowCmp = DAG.getNode(ISD::SUBE, dl, VTList, LHSLo, RHSLo, Carry);
2992   return DAG.getNode(ISD::SETCCE, dl, N->getValueType(0), LHSHi, RHSHi,
2993                      LowCmp.getValue(1), Cond);
2994 }
2995
2996 SDValue DAGTypeLegalizer::ExpandIntOp_Shift(SDNode *N) {
2997   // The value being shifted is legal, but the shift amount is too big.
2998   // It follows that either the result of the shift is undefined, or the
2999   // upper half of the shift amount is zero.  Just use the lower half.
3000   SDValue Lo, Hi;
3001   GetExpandedInteger(N->getOperand(1), Lo, Hi);
3002   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0), Lo), 0);
3003 }
3004
3005 SDValue DAGTypeLegalizer::ExpandIntOp_RETURNADDR(SDNode *N) {
3006   // The argument of RETURNADDR / FRAMEADDR builtin is 32 bit contant.  This
3007   // surely makes pretty nice problems on 8/16 bit targets. Just truncate this
3008   // constant to valid type.
3009   SDValue Lo, Hi;
3010   GetExpandedInteger(N->getOperand(0), Lo, Hi);
3011   return SDValue(DAG.UpdateNodeOperands(N, Lo), 0);
3012 }
3013
3014 SDValue DAGTypeLegalizer::ExpandIntOp_SINT_TO_FP(SDNode *N) {
3015   SDValue Op = N->getOperand(0);
3016   EVT DstVT = N->getValueType(0);
3017   RTLIB::Libcall LC = RTLIB::getSINTTOFP(Op.getValueType(), DstVT);
3018   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
3019          "Don't know how to expand this SINT_TO_FP!");
3020   return TLI.makeLibCall(DAG, LC, DstVT, Op, true, SDLoc(N)).first;
3021 }
3022
3023 SDValue DAGTypeLegalizer::ExpandIntOp_STORE(StoreSDNode *N, unsigned OpNo) {
3024   if (ISD::isNormalStore(N))
3025     return ExpandOp_NormalStore(N, OpNo);
3026
3027   assert(ISD::isUNINDEXEDStore(N) && "Indexed store during type legalization!");
3028   assert(OpNo == 1 && "Can only expand the stored value so far");
3029
3030   EVT VT = N->getOperand(1).getValueType();
3031   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3032   SDValue Ch  = N->getChain();
3033   SDValue Ptr = N->getBasePtr();
3034   unsigned Alignment = N->getAlignment();
3035   MachineMemOperand::Flags MMOFlags = N->getMemOperand()->getFlags();
3036   AAMDNodes AAInfo = N->getAAInfo();
3037   SDLoc dl(N);
3038   SDValue Lo, Hi;
3039
3040   assert(NVT.isByteSized() && "Expanded type not byte sized!");
3041
3042   if (N->getMemoryVT().bitsLE(NVT)) {
3043     GetExpandedInteger(N->getValue(), Lo, Hi);
3044     return DAG.getTruncStore(Ch, dl, Lo, Ptr, N->getPointerInfo(),
3045                              N->getMemoryVT(), Alignment, MMOFlags, AAInfo);
3046   }
3047
3048   if (DAG.getDataLayout().isLittleEndian()) {
3049     // Little-endian - low bits are at low addresses.
3050     GetExpandedInteger(N->getValue(), Lo, Hi);
3051
3052     Lo = DAG.getStore(Ch, dl, Lo, Ptr, N->getPointerInfo(), Alignment, MMOFlags,
3053                       AAInfo);
3054
3055     unsigned ExcessBits =
3056       N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
3057     EVT NEVT = EVT::getIntegerVT(*DAG.getContext(), ExcessBits);
3058
3059     // Increment the pointer to the other half.
3060     unsigned IncrementSize = NVT.getSizeInBits()/8;
3061     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3062                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3063     Hi = DAG.getTruncStore(
3064         Ch, dl, Hi, Ptr, N->getPointerInfo().getWithOffset(IncrementSize), NEVT,
3065         MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
3066     return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
3067   }
3068
3069   // Big-endian - high bits are at low addresses.  Favor aligned stores at
3070   // the cost of some bit-fiddling.
3071   GetExpandedInteger(N->getValue(), Lo, Hi);
3072
3073   EVT ExtVT = N->getMemoryVT();
3074   unsigned EBytes = ExtVT.getStoreSize();
3075   unsigned IncrementSize = NVT.getSizeInBits()/8;
3076   unsigned ExcessBits = (EBytes - IncrementSize)*8;
3077   EVT HiVT = EVT::getIntegerVT(*DAG.getContext(),
3078                                ExtVT.getSizeInBits() - ExcessBits);
3079
3080   if (ExcessBits < NVT.getSizeInBits()) {
3081     // Transfer high bits from the top of Lo to the bottom of Hi.
3082     Hi = DAG.getNode(ISD::SHL, dl, NVT, Hi,
3083                      DAG.getConstant(NVT.getSizeInBits() - ExcessBits, dl,
3084                                      TLI.getPointerTy(DAG.getDataLayout())));
3085     Hi = DAG.getNode(
3086         ISD::OR, dl, NVT, Hi,
3087         DAG.getNode(ISD::SRL, dl, NVT, Lo,
3088                     DAG.getConstant(ExcessBits, dl,
3089                                     TLI.getPointerTy(DAG.getDataLayout()))));
3090   }
3091
3092   // Store both the high bits and maybe some of the low bits.
3093   Hi = DAG.getTruncStore(Ch, dl, Hi, Ptr, N->getPointerInfo(), HiVT, Alignment,
3094                          MMOFlags, AAInfo);
3095
3096   // Increment the pointer to the other half.
3097   Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3098                     DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3099   // Store the lowest ExcessBits bits in the second half.
3100   Lo = DAG.getTruncStore(Ch, dl, Lo, Ptr,
3101                          N->getPointerInfo().getWithOffset(IncrementSize),
3102                          EVT::getIntegerVT(*DAG.getContext(), ExcessBits),
3103                          MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
3104   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
3105 }
3106
3107 SDValue DAGTypeLegalizer::ExpandIntOp_TRUNCATE(SDNode *N) {
3108   SDValue InL, InH;
3109   GetExpandedInteger(N->getOperand(0), InL, InH);
3110   // Just truncate the low part of the source.
3111   return DAG.getNode(ISD::TRUNCATE, SDLoc(N), N->getValueType(0), InL);
3112 }
3113
3114 SDValue DAGTypeLegalizer::ExpandIntOp_UINT_TO_FP(SDNode *N) {
3115   SDValue Op = N->getOperand(0);
3116   EVT SrcVT = Op.getValueType();
3117   EVT DstVT = N->getValueType(0);
3118   SDLoc dl(N);
3119
3120   // The following optimization is valid only if every value in SrcVT (when
3121   // treated as signed) is representable in DstVT.  Check that the mantissa
3122   // size of DstVT is >= than the number of bits in SrcVT -1.
3123   const fltSemantics &sem = DAG.EVTToAPFloatSemantics(DstVT);
3124   if (APFloat::semanticsPrecision(sem) >= SrcVT.getSizeInBits()-1 &&
3125       TLI.getOperationAction(ISD::SINT_TO_FP, SrcVT) == TargetLowering::Custom){
3126     // Do a signed conversion then adjust the result.
3127     SDValue SignedConv = DAG.getNode(ISD::SINT_TO_FP, dl, DstVT, Op);
3128     SignedConv = TLI.LowerOperation(SignedConv, DAG);
3129
3130     // The result of the signed conversion needs adjusting if the 'sign bit' of
3131     // the incoming integer was set.  To handle this, we dynamically test to see
3132     // if it is set, and, if so, add a fudge factor.
3133
3134     const uint64_t F32TwoE32  = 0x4F800000ULL;
3135     const uint64_t F32TwoE64  = 0x5F800000ULL;
3136     const uint64_t F32TwoE128 = 0x7F800000ULL;
3137
3138     APInt FF(32, 0);
3139     if (SrcVT == MVT::i32)
3140       FF = APInt(32, F32TwoE32);
3141     else if (SrcVT == MVT::i64)
3142       FF = APInt(32, F32TwoE64);
3143     else if (SrcVT == MVT::i128)
3144       FF = APInt(32, F32TwoE128);
3145     else
3146       llvm_unreachable("Unsupported UINT_TO_FP!");
3147
3148     // Check whether the sign bit is set.
3149     SDValue Lo, Hi;
3150     GetExpandedInteger(Op, Lo, Hi);
3151     SDValue SignSet = DAG.getSetCC(dl,
3152                                    getSetCCResultType(Hi.getValueType()),
3153                                    Hi,
3154                                    DAG.getConstant(0, dl, Hi.getValueType()),
3155                                    ISD::SETLT);
3156
3157     // Build a 64 bit pair (0, FF) in the constant pool, with FF in the lo bits.
3158     SDValue FudgePtr =
3159         DAG.getConstantPool(ConstantInt::get(*DAG.getContext(), FF.zext(64)),
3160                             TLI.getPointerTy(DAG.getDataLayout()));
3161
3162     // Get a pointer to FF if the sign bit was set, or to 0 otherwise.
3163     SDValue Zero = DAG.getIntPtrConstant(0, dl);
3164     SDValue Four = DAG.getIntPtrConstant(4, dl);
3165     if (DAG.getDataLayout().isBigEndian())
3166       std::swap(Zero, Four);
3167     SDValue Offset = DAG.getSelect(dl, Zero.getValueType(), SignSet,
3168                                    Zero, Four);
3169     unsigned Alignment = cast<ConstantPoolSDNode>(FudgePtr)->getAlignment();
3170     FudgePtr = DAG.getNode(ISD::ADD, dl, FudgePtr.getValueType(),
3171                            FudgePtr, Offset);
3172     Alignment = std::min(Alignment, 4u);
3173
3174     // Load the value out, extending it from f32 to the destination float type.
3175     // FIXME: Avoid the extend by constructing the right constant pool?
3176     SDValue Fudge = DAG.getExtLoad(
3177         ISD::EXTLOAD, dl, DstVT, DAG.getEntryNode(), FudgePtr,
3178         MachinePointerInfo::getConstantPool(DAG.getMachineFunction()), MVT::f32,
3179         Alignment);
3180     return DAG.getNode(ISD::FADD, dl, DstVT, SignedConv, Fudge);
3181   }
3182
3183   // Otherwise, use a libcall.
3184   RTLIB::Libcall LC = RTLIB::getUINTTOFP(SrcVT, DstVT);
3185   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
3186          "Don't know how to expand this UINT_TO_FP!");
3187   return TLI.makeLibCall(DAG, LC, DstVT, Op, true, dl).first;
3188 }
3189
3190 SDValue DAGTypeLegalizer::ExpandIntOp_ATOMIC_STORE(SDNode *N) {
3191   SDLoc dl(N);
3192   SDValue Swap = DAG.getAtomic(ISD::ATOMIC_SWAP, dl,
3193                                cast<AtomicSDNode>(N)->getMemoryVT(),
3194                                N->getOperand(0),
3195                                N->getOperand(1), N->getOperand(2),
3196                                cast<AtomicSDNode>(N)->getMemOperand(),
3197                                cast<AtomicSDNode>(N)->getOrdering(),
3198                                cast<AtomicSDNode>(N)->getSynchScope());
3199   return Swap.getValue(1);
3200 }
3201
3202
3203 SDValue DAGTypeLegalizer::PromoteIntRes_EXTRACT_SUBVECTOR(SDNode *N) {
3204   SDValue InOp0 = N->getOperand(0);
3205   EVT InVT = InOp0.getValueType();
3206
3207   EVT OutVT = N->getValueType(0);
3208   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3209   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3210   unsigned OutNumElems = OutVT.getVectorNumElements();
3211   EVT NOutVTElem = NOutVT.getVectorElementType();
3212
3213   SDLoc dl(N);
3214   SDValue BaseIdx = N->getOperand(1);
3215
3216   SmallVector<SDValue, 8> Ops;
3217   Ops.reserve(OutNumElems);
3218   for (unsigned i = 0; i != OutNumElems; ++i) {
3219
3220     // Extract the element from the original vector.
3221     SDValue Index = DAG.getNode(ISD::ADD, dl, BaseIdx.getValueType(),
3222       BaseIdx, DAG.getConstant(i, dl, BaseIdx.getValueType()));
3223     SDValue Ext = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
3224       InVT.getVectorElementType(), N->getOperand(0), Index);
3225
3226     SDValue Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, Ext);
3227     // Insert the converted element to the new vector.
3228     Ops.push_back(Op);
3229   }
3230
3231   return DAG.getNode(ISD::BUILD_VECTOR, dl, NOutVT, Ops);
3232 }
3233
3234
3235 SDValue DAGTypeLegalizer::PromoteIntRes_VECTOR_SHUFFLE(SDNode *N) {
3236   ShuffleVectorSDNode *SV = cast<ShuffleVectorSDNode>(N);
3237   EVT VT = N->getValueType(0);
3238   SDLoc dl(N);
3239
3240   ArrayRef<int> NewMask = SV->getMask().slice(0, VT.getVectorNumElements());
3241
3242   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3243   SDValue V1 = GetPromotedInteger(N->getOperand(1));
3244   EVT OutVT = V0.getValueType();
3245
3246   return DAG.getVectorShuffle(OutVT, dl, V0, V1, NewMask);
3247 }
3248
3249
3250 SDValue DAGTypeLegalizer::PromoteIntRes_BUILD_VECTOR(SDNode *N) {
3251   EVT OutVT = N->getValueType(0);
3252   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3253   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3254   unsigned NumElems = N->getNumOperands();
3255   EVT NOutVTElem = NOutVT.getVectorElementType();
3256
3257   SDLoc dl(N);
3258
3259   SmallVector<SDValue, 8> Ops;
3260   Ops.reserve(NumElems);
3261   for (unsigned i = 0; i != NumElems; ++i) {
3262     SDValue Op;
3263     // BUILD_VECTOR integer operand types are allowed to be larger than the
3264     // result's element type. This may still be true after the promotion. For
3265     // example, we might be promoting (<v?i1> = BV <i32>, <i32>, ...) to
3266     // (v?i16 = BV <i32>, <i32>, ...), and we can't any_extend <i32> to <i16>.
3267     if (N->getOperand(i).getValueType().bitsLT(NOutVTElem))
3268       Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, N->getOperand(i));
3269     else
3270       Op = N->getOperand(i);
3271     Ops.push_back(Op);
3272   }
3273
3274   return DAG.getNode(ISD::BUILD_VECTOR, dl, NOutVT, Ops);
3275 }
3276
3277 SDValue DAGTypeLegalizer::PromoteIntRes_SCALAR_TO_VECTOR(SDNode *N) {
3278
3279   SDLoc dl(N);
3280
3281   assert(!N->getOperand(0).getValueType().isVector() &&
3282          "Input must be a scalar");
3283
3284   EVT OutVT = N->getValueType(0);
3285   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3286   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3287   EVT NOutVTElem = NOutVT.getVectorElementType();
3288
3289   SDValue Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, N->getOperand(0));
3290
3291   return DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NOutVT, Op);
3292 }
3293
3294 SDValue DAGTypeLegalizer::PromoteIntRes_CONCAT_VECTORS(SDNode *N) {
3295   SDLoc dl(N);
3296
3297   EVT OutVT = N->getValueType(0);
3298   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3299   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3300
3301   EVT InElemTy = OutVT.getVectorElementType();
3302   EVT OutElemTy = NOutVT.getVectorElementType();
3303
3304   unsigned NumElem = N->getOperand(0).getValueType().getVectorNumElements();
3305   unsigned NumOutElem = NOutVT.getVectorNumElements();
3306   unsigned NumOperands = N->getNumOperands();
3307   assert(NumElem * NumOperands == NumOutElem &&
3308          "Unexpected number of elements");
3309
3310   // Take the elements from the first vector.
3311   SmallVector<SDValue, 8> Ops(NumOutElem);
3312   for (unsigned i = 0; i < NumOperands; ++i) {
3313     SDValue Op = N->getOperand(i);
3314     for (unsigned j = 0; j < NumElem; ++j) {
3315       SDValue Ext = DAG.getNode(
3316           ISD::EXTRACT_VECTOR_ELT, dl, InElemTy, Op,
3317           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3318       Ops[i * NumElem + j] = DAG.getNode(ISD::ANY_EXTEND, dl, OutElemTy, Ext);
3319     }
3320   }
3321
3322   return DAG.getNode(ISD::BUILD_VECTOR, dl, NOutVT, Ops);
3323 }
3324
3325 SDValue DAGTypeLegalizer::PromoteIntRes_INSERT_VECTOR_ELT(SDNode *N) {
3326   EVT OutVT = N->getValueType(0);
3327   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3328   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3329
3330   EVT NOutVTElem = NOutVT.getVectorElementType();
3331
3332   SDLoc dl(N);
3333   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3334
3335   SDValue ConvElem = DAG.getNode(ISD::ANY_EXTEND, dl,
3336     NOutVTElem, N->getOperand(1));
3337   return DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, NOutVT,
3338     V0, ConvElem, N->getOperand(2));
3339 }
3340
3341 SDValue DAGTypeLegalizer::PromoteIntOp_EXTRACT_VECTOR_ELT(SDNode *N) {
3342   SDLoc dl(N);
3343   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3344   SDValue V1 = DAG.getZExtOrTrunc(N->getOperand(1), dl,
3345                                   TLI.getVectorIdxTy(DAG.getDataLayout()));
3346   SDValue Ext = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
3347     V0->getValueType(0).getScalarType(), V0, V1);
3348
3349   // EXTRACT_VECTOR_ELT can return types which are wider than the incoming
3350   // element types. If this is the case then we need to expand the outgoing
3351   // value and not truncate it.
3352   return DAG.getAnyExtOrTrunc(Ext, dl, N->getValueType(0));
3353 }
3354
3355 SDValue DAGTypeLegalizer::PromoteIntOp_EXTRACT_SUBVECTOR(SDNode *N) {
3356   SDLoc dl(N);
3357   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3358   MVT InVT = V0.getValueType().getSimpleVT();
3359   MVT OutVT = MVT::getVectorVT(InVT.getVectorElementType(),
3360                                N->getValueType(0).getVectorNumElements());
3361   SDValue Ext = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, OutVT, V0, N->getOperand(1));
3362   return DAG.getNode(ISD::TRUNCATE, dl, N->getValueType(0), Ext);
3363 }
3364
3365 SDValue DAGTypeLegalizer::PromoteIntOp_CONCAT_VECTORS(SDNode *N) {
3366   SDLoc dl(N);
3367   unsigned NumElems = N->getNumOperands();
3368
3369   EVT RetSclrTy = N->getValueType(0).getVectorElementType();
3370
3371   SmallVector<SDValue, 8> NewOps;
3372   NewOps.reserve(NumElems);
3373
3374   // For each incoming vector
3375   for (unsigned VecIdx = 0; VecIdx != NumElems; ++VecIdx) {
3376     SDValue Incoming = GetPromotedInteger(N->getOperand(VecIdx));
3377     EVT SclrTy = Incoming->getValueType(0).getVectorElementType();
3378     unsigned NumElem = Incoming->getValueType(0).getVectorNumElements();
3379
3380     for (unsigned i=0; i<NumElem; ++i) {
3381       // Extract element from incoming vector
3382       SDValue Ex = DAG.getNode(
3383           ISD::EXTRACT_VECTOR_ELT, dl, SclrTy, Incoming,
3384           DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3385       SDValue Tr = DAG.getNode(ISD::TRUNCATE, dl, RetSclrTy, Ex);
3386       NewOps.push_back(Tr);
3387     }
3388   }
3389
3390   return DAG.getNode(ISD::BUILD_VECTOR, dl,  N->getValueType(0), NewOps);
3391 }