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     unsigned Bits = NVT.getSizeInBits();
2189     unsigned HalfBits = Bits >> 1;
2190     SDValue Mask = DAG.getConstant(APInt::getLowBitsSet(Bits, HalfBits), dl,
2191                                    NVT);
2192     SDValue LLL = DAG.getNode(ISD::AND, dl, NVT, LL, Mask);
2193     SDValue RLL = DAG.getNode(ISD::AND, dl, NVT, RL, Mask);
2194
2195     SDValue T = DAG.getNode(ISD::MUL, dl, NVT, LLL, RLL);
2196     SDValue TL = DAG.getNode(ISD::AND, dl, NVT, T, Mask);
2197
2198     EVT ShiftAmtTy = TLI.getShiftAmountTy(NVT, DAG.getDataLayout());
2199     if (APInt::getMaxValue(ShiftAmtTy.getSizeInBits()).ult(HalfBits)) {
2200       // The type from TLI is too small to fit the shift amount we want.
2201       // Override it with i32. The shift will have to be legalized.
2202       ShiftAmtTy = MVT::i32;
2203     }
2204     SDValue Shift = DAG.getConstant(HalfBits, dl, ShiftAmtTy);
2205     SDValue TH = DAG.getNode(ISD::SRL, dl, NVT, T, Shift);
2206     SDValue LLH = DAG.getNode(ISD::SRL, dl, NVT, LL, Shift);
2207     SDValue RLH = DAG.getNode(ISD::SRL, dl, NVT, RL, Shift);
2208
2209     SDValue U = DAG.getNode(ISD::ADD, dl, NVT,
2210                             DAG.getNode(ISD::MUL, dl, NVT, LLH, RLL), TH);
2211     SDValue UL = DAG.getNode(ISD::AND, dl, NVT, U, Mask);
2212     SDValue UH = DAG.getNode(ISD::SRL, dl, NVT, U, Shift);
2213
2214     SDValue V = DAG.getNode(ISD::ADD, dl, NVT,
2215                             DAG.getNode(ISD::MUL, dl, NVT, LLL, RLH), UL);
2216     SDValue VH = DAG.getNode(ISD::SRL, dl, NVT, V, Shift);
2217
2218     SDValue W = DAG.getNode(ISD::ADD, dl, NVT,
2219                             DAG.getNode(ISD::MUL, dl, NVT, LLH, RLH),
2220                             DAG.getNode(ISD::ADD, dl, NVT, UH, VH));
2221     Lo = DAG.getNode(ISD::ADD, dl, NVT, TL,
2222                      DAG.getNode(ISD::SHL, dl, NVT, V, Shift));
2223
2224     Hi = DAG.getNode(ISD::ADD, dl, NVT, W,
2225                      DAG.getNode(ISD::ADD, dl, NVT,
2226                                  DAG.getNode(ISD::MUL, dl, NVT, RH, LL),
2227                                  DAG.getNode(ISD::MUL, dl, NVT, RL, LH)));
2228     return;
2229   }
2230
2231   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2232   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true/*irrelevant*/, dl).first,
2233                Lo, Hi);
2234 }
2235
2236 void DAGTypeLegalizer::ExpandIntRes_READCYCLECOUNTER(SDNode *N, SDValue &Lo,
2237                                                      SDValue &Hi) {
2238   SDLoc DL(N);
2239   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2240   SDVTList VTs = DAG.getVTList(NVT, NVT, MVT::Other);
2241   SDValue R = DAG.getNode(N->getOpcode(), DL, VTs, N->getOperand(0));
2242   Lo = R.getValue(0);
2243   Hi = R.getValue(1);
2244   ReplaceValueWith(SDValue(N, 1), R.getValue(2));
2245 }
2246
2247 void DAGTypeLegalizer::ExpandIntRes_SADDSUBO(SDNode *Node,
2248                                              SDValue &Lo, SDValue &Hi) {
2249   SDValue LHS = Node->getOperand(0);
2250   SDValue RHS = Node->getOperand(1);
2251   SDLoc dl(Node);
2252
2253   // Expand the result by simply replacing it with the equivalent
2254   // non-overflow-checking operation.
2255   SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ?
2256                             ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
2257                             LHS, RHS);
2258   SplitInteger(Sum, Lo, Hi);
2259
2260   // Compute the overflow.
2261   //
2262   //   LHSSign -> LHS >= 0
2263   //   RHSSign -> RHS >= 0
2264   //   SumSign -> Sum >= 0
2265   //
2266   //   Add:
2267   //   Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign)
2268   //   Sub:
2269   //   Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign)
2270   //
2271   EVT OType = Node->getValueType(1);
2272   SDValue Zero = DAG.getConstant(0, dl, LHS.getValueType());
2273
2274   SDValue LHSSign = DAG.getSetCC(dl, OType, LHS, Zero, ISD::SETGE);
2275   SDValue RHSSign = DAG.getSetCC(dl, OType, RHS, Zero, ISD::SETGE);
2276   SDValue SignsMatch = DAG.getSetCC(dl, OType, LHSSign, RHSSign,
2277                                     Node->getOpcode() == ISD::SADDO ?
2278                                     ISD::SETEQ : ISD::SETNE);
2279
2280   SDValue SumSign = DAG.getSetCC(dl, OType, Sum, Zero, ISD::SETGE);
2281   SDValue SumSignNE = DAG.getSetCC(dl, OType, LHSSign, SumSign, ISD::SETNE);
2282
2283   SDValue Cmp = DAG.getNode(ISD::AND, dl, OType, SignsMatch, SumSignNE);
2284
2285   // Use the calculated overflow everywhere.
2286   ReplaceValueWith(SDValue(Node, 1), Cmp);
2287 }
2288
2289 void DAGTypeLegalizer::ExpandIntRes_SDIV(SDNode *N,
2290                                          SDValue &Lo, SDValue &Hi) {
2291   EVT VT = N->getValueType(0);
2292   SDLoc dl(N);
2293   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2294
2295   if (TLI.getOperationAction(ISD::SDIVREM, VT) == TargetLowering::Custom) {
2296     SDValue Res = DAG.getNode(ISD::SDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2297     SplitInteger(Res.getValue(0), Lo, Hi);
2298     return;
2299   }
2300
2301   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2302   if (VT == MVT::i16)
2303     LC = RTLIB::SDIV_I16;
2304   else if (VT == MVT::i32)
2305     LC = RTLIB::SDIV_I32;
2306   else if (VT == MVT::i64)
2307     LC = RTLIB::SDIV_I64;
2308   else if (VT == MVT::i128)
2309     LC = RTLIB::SDIV_I128;
2310   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SDIV!");
2311
2312   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true, dl).first, Lo, Hi);
2313 }
2314
2315 void DAGTypeLegalizer::ExpandIntRes_Shift(SDNode *N,
2316                                           SDValue &Lo, SDValue &Hi) {
2317   EVT VT = N->getValueType(0);
2318   SDLoc dl(N);
2319
2320   // If we can emit an efficient shift operation, do so now.  Check to see if
2321   // the RHS is a constant.
2322   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2323     return ExpandShiftByConstant(N, CN->getAPIntValue(), Lo, Hi);
2324
2325   // If we can determine that the high bit of the shift is zero or one, even if
2326   // the low bits are variable, emit this shift in an optimized form.
2327   if (ExpandShiftWithKnownAmountBit(N, Lo, Hi))
2328     return;
2329
2330   // If this target supports shift_PARTS, use it.  First, map to the _PARTS opc.
2331   unsigned PartsOpc;
2332   if (N->getOpcode() == ISD::SHL) {
2333     PartsOpc = ISD::SHL_PARTS;
2334   } else if (N->getOpcode() == ISD::SRL) {
2335     PartsOpc = ISD::SRL_PARTS;
2336   } else {
2337     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
2338     PartsOpc = ISD::SRA_PARTS;
2339   }
2340
2341   // Next check to see if the target supports this SHL_PARTS operation or if it
2342   // will custom expand it.
2343   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
2344   TargetLowering::LegalizeAction Action = TLI.getOperationAction(PartsOpc, NVT);
2345   if ((Action == TargetLowering::Legal && TLI.isTypeLegal(NVT)) ||
2346       Action == TargetLowering::Custom) {
2347     // Expand the subcomponents.
2348     SDValue LHSL, LHSH;
2349     GetExpandedInteger(N->getOperand(0), LHSL, LHSH);
2350     EVT VT = LHSL.getValueType();
2351
2352     // If the shift amount operand is coming from a vector legalization it may
2353     // have an illegal type.  Fix that first by casting the operand, otherwise
2354     // the new SHL_PARTS operation would need further legalization.
2355     SDValue ShiftOp = N->getOperand(1);
2356     EVT ShiftTy = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
2357     assert(ShiftTy.getScalarType().getSizeInBits() >=
2358            Log2_32_Ceil(VT.getScalarType().getSizeInBits()) &&
2359            "ShiftAmountTy is too small to cover the range of this type!");
2360     if (ShiftOp.getValueType() != ShiftTy)
2361       ShiftOp = DAG.getZExtOrTrunc(ShiftOp, dl, ShiftTy);
2362
2363     SDValue Ops[] = { LHSL, LHSH, ShiftOp };
2364     Lo = DAG.getNode(PartsOpc, dl, DAG.getVTList(VT, VT), Ops);
2365     Hi = Lo.getValue(1);
2366     return;
2367   }
2368
2369   // Otherwise, emit a libcall.
2370   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2371   bool isSigned;
2372   if (N->getOpcode() == ISD::SHL) {
2373     isSigned = false; /*sign irrelevant*/
2374     if (VT == MVT::i16)
2375       LC = RTLIB::SHL_I16;
2376     else if (VT == MVT::i32)
2377       LC = RTLIB::SHL_I32;
2378     else if (VT == MVT::i64)
2379       LC = RTLIB::SHL_I64;
2380     else if (VT == MVT::i128)
2381       LC = RTLIB::SHL_I128;
2382   } else if (N->getOpcode() == ISD::SRL) {
2383     isSigned = false;
2384     if (VT == MVT::i16)
2385       LC = RTLIB::SRL_I16;
2386     else if (VT == MVT::i32)
2387       LC = RTLIB::SRL_I32;
2388     else if (VT == MVT::i64)
2389       LC = RTLIB::SRL_I64;
2390     else if (VT == MVT::i128)
2391       LC = RTLIB::SRL_I128;
2392   } else {
2393     assert(N->getOpcode() == ISD::SRA && "Unknown shift!");
2394     isSigned = true;
2395     if (VT == MVT::i16)
2396       LC = RTLIB::SRA_I16;
2397     else if (VT == MVT::i32)
2398       LC = RTLIB::SRA_I32;
2399     else if (VT == MVT::i64)
2400       LC = RTLIB::SRA_I64;
2401     else if (VT == MVT::i128)
2402       LC = RTLIB::SRA_I128;
2403   }
2404
2405   if (LC != RTLIB::UNKNOWN_LIBCALL && TLI.getLibcallName(LC)) {
2406     SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2407     SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, isSigned, dl).first, Lo, Hi);
2408     return;
2409   }
2410
2411   if (!ExpandShiftWithUnknownAmountBit(N, Lo, Hi))
2412     llvm_unreachable("Unsupported shift!");
2413 }
2414
2415 void DAGTypeLegalizer::ExpandIntRes_SIGN_EXTEND(SDNode *N,
2416                                                 SDValue &Lo, SDValue &Hi) {
2417   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2418   SDLoc dl(N);
2419   SDValue Op = N->getOperand(0);
2420   if (Op.getValueType().bitsLE(NVT)) {
2421     // The low part is sign extension of the input (degenerates to a copy).
2422     Lo = DAG.getNode(ISD::SIGN_EXTEND, dl, NVT, N->getOperand(0));
2423     // The high part is obtained by SRA'ing all but one of the bits of low part.
2424     unsigned LoSize = NVT.getSizeInBits();
2425     Hi = DAG.getNode(
2426         ISD::SRA, dl, NVT, Lo,
2427         DAG.getConstant(LoSize - 1, dl, TLI.getPointerTy(DAG.getDataLayout())));
2428   } else {
2429     // For example, extension of an i48 to an i64.  The operand type necessarily
2430     // promotes to the result type, so will end up being expanded too.
2431     assert(getTypeAction(Op.getValueType()) ==
2432            TargetLowering::TypePromoteInteger &&
2433            "Only know how to promote this result!");
2434     SDValue Res = GetPromotedInteger(Op);
2435     assert(Res.getValueType() == N->getValueType(0) &&
2436            "Operand over promoted?");
2437     // Split the promoted operand.  This will simplify when it is expanded.
2438     SplitInteger(Res, Lo, Hi);
2439     unsigned ExcessBits =
2440       Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
2441     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
2442                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
2443                                                         ExcessBits)));
2444   }
2445 }
2446
2447 void DAGTypeLegalizer::
2448 ExpandIntRes_SIGN_EXTEND_INREG(SDNode *N, SDValue &Lo, SDValue &Hi) {
2449   SDLoc dl(N);
2450   GetExpandedInteger(N->getOperand(0), Lo, Hi);
2451   EVT EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
2452
2453   if (EVT.bitsLE(Lo.getValueType())) {
2454     // sext_inreg the low part if needed.
2455     Lo = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Lo.getValueType(), Lo,
2456                      N->getOperand(1));
2457
2458     // The high part gets the sign extension from the lo-part.  This handles
2459     // things like sextinreg V:i64 from i8.
2460     Hi = DAG.getNode(ISD::SRA, dl, Hi.getValueType(), Lo,
2461                      DAG.getConstant(Hi.getValueType().getSizeInBits() - 1, dl,
2462                                      TLI.getPointerTy(DAG.getDataLayout())));
2463   } else {
2464     // For example, extension of an i48 to an i64.  Leave the low part alone,
2465     // sext_inreg the high part.
2466     unsigned ExcessBits =
2467       EVT.getSizeInBits() - Lo.getValueType().getSizeInBits();
2468     Hi = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, Hi.getValueType(), Hi,
2469                      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(),
2470                                                         ExcessBits)));
2471   }
2472 }
2473
2474 void DAGTypeLegalizer::ExpandIntRes_SREM(SDNode *N,
2475                                          SDValue &Lo, SDValue &Hi) {
2476   EVT VT = N->getValueType(0);
2477   SDLoc dl(N);
2478   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2479
2480   if (TLI.getOperationAction(ISD::SDIVREM, VT) == TargetLowering::Custom) {
2481     SDValue Res = DAG.getNode(ISD::SDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2482     SplitInteger(Res.getValue(1), Lo, Hi);
2483     return;
2484   }
2485
2486   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2487   if (VT == MVT::i16)
2488     LC = RTLIB::SREM_I16;
2489   else if (VT == MVT::i32)
2490     LC = RTLIB::SREM_I32;
2491   else if (VT == MVT::i64)
2492     LC = RTLIB::SREM_I64;
2493   else if (VT == MVT::i128)
2494     LC = RTLIB::SREM_I128;
2495   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported SREM!");
2496
2497   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, true, dl).first, Lo, Hi);
2498 }
2499
2500 void DAGTypeLegalizer::ExpandIntRes_TRUNCATE(SDNode *N,
2501                                              SDValue &Lo, SDValue &Hi) {
2502   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2503   SDLoc dl(N);
2504   Lo = DAG.getNode(ISD::TRUNCATE, dl, NVT, N->getOperand(0));
2505   Hi = DAG.getNode(ISD::SRL, dl, N->getOperand(0).getValueType(),
2506                    N->getOperand(0),
2507                    DAG.getConstant(NVT.getSizeInBits(), dl,
2508                                    TLI.getPointerTy(DAG.getDataLayout())));
2509   Hi = DAG.getNode(ISD::TRUNCATE, dl, NVT, Hi);
2510 }
2511
2512 void DAGTypeLegalizer::ExpandIntRes_UADDSUBO(SDNode *N,
2513                                              SDValue &Lo, SDValue &Hi) {
2514   SDValue LHS = N->getOperand(0);
2515   SDValue RHS = N->getOperand(1);
2516   SDLoc dl(N);
2517
2518   // Expand the result by simply replacing it with the equivalent
2519   // non-overflow-checking operation.
2520   SDValue Sum = DAG.getNode(N->getOpcode() == ISD::UADDO ?
2521                             ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
2522                             LHS, RHS);
2523   SplitInteger(Sum, Lo, Hi);
2524
2525   // Calculate the overflow: addition overflows iff a + b < a, and subtraction
2526   // overflows iff a - b > a.
2527   SDValue Ofl = DAG.getSetCC(dl, N->getValueType(1), Sum, LHS,
2528                              N->getOpcode () == ISD::UADDO ?
2529                              ISD::SETULT : ISD::SETUGT);
2530
2531   // Use the calculated overflow everywhere.
2532   ReplaceValueWith(SDValue(N, 1), Ofl);
2533 }
2534
2535 void DAGTypeLegalizer::ExpandIntRes_XMULO(SDNode *N,
2536                                           SDValue &Lo, SDValue &Hi) {
2537   EVT VT = N->getValueType(0);
2538   SDLoc dl(N);
2539
2540   // A divide for UMULO should be faster than a function call.
2541   if (N->getOpcode() == ISD::UMULO) {
2542     SDValue LHS = N->getOperand(0), RHS = N->getOperand(1);
2543
2544     SDValue MUL = DAG.getNode(ISD::MUL, dl, LHS.getValueType(), LHS, RHS);
2545     SplitInteger(MUL, Lo, Hi);
2546
2547     // A divide for UMULO will be faster than a function call. Select to
2548     // make sure we aren't using 0.
2549     SDValue isZero = DAG.getSetCC(dl, getSetCCResultType(VT),
2550                                   RHS, DAG.getConstant(0, dl, VT), ISD::SETEQ);
2551     SDValue NotZero = DAG.getSelect(dl, VT, isZero,
2552                                     DAG.getConstant(1, dl, VT), RHS);
2553     SDValue DIV = DAG.getNode(ISD::UDIV, dl, VT, MUL, NotZero);
2554     SDValue Overflow = DAG.getSetCC(dl, N->getValueType(1), DIV, LHS,
2555                                     ISD::SETNE);
2556     Overflow = DAG.getSelect(dl, N->getValueType(1), isZero,
2557                              DAG.getConstant(0, dl, N->getValueType(1)),
2558                              Overflow);
2559     ReplaceValueWith(SDValue(N, 1), Overflow);
2560     return;
2561   }
2562
2563   Type *RetTy = VT.getTypeForEVT(*DAG.getContext());
2564   EVT PtrVT = TLI.getPointerTy(DAG.getDataLayout());
2565   Type *PtrTy = PtrVT.getTypeForEVT(*DAG.getContext());
2566
2567   // Replace this with a libcall that will check overflow.
2568   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2569   if (VT == MVT::i32)
2570     LC = RTLIB::MULO_I32;
2571   else if (VT == MVT::i64)
2572     LC = RTLIB::MULO_I64;
2573   else if (VT == MVT::i128)
2574     LC = RTLIB::MULO_I128;
2575   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported XMULO!");
2576
2577   SDValue Temp = DAG.CreateStackTemporary(PtrVT);
2578   // Temporary for the overflow value, default it to zero.
2579   SDValue Chain =
2580       DAG.getStore(DAG.getEntryNode(), dl, DAG.getConstant(0, dl, PtrVT), Temp,
2581                    MachinePointerInfo());
2582
2583   TargetLowering::ArgListTy Args;
2584   TargetLowering::ArgListEntry Entry;
2585   for (const SDValue &Op : N->op_values()) {
2586     EVT ArgVT = Op.getValueType();
2587     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
2588     Entry.Node = Op;
2589     Entry.Ty = ArgTy;
2590     Entry.isSExt = true;
2591     Entry.isZExt = false;
2592     Args.push_back(Entry);
2593   }
2594
2595   // Also pass the address of the overflow check.
2596   Entry.Node = Temp;
2597   Entry.Ty = PtrTy->getPointerTo();
2598   Entry.isSExt = true;
2599   Entry.isZExt = false;
2600   Args.push_back(Entry);
2601
2602   SDValue Func = DAG.getExternalSymbol(TLI.getLibcallName(LC), PtrVT);
2603
2604   TargetLowering::CallLoweringInfo CLI(DAG);
2605   CLI.setDebugLoc(dl).setChain(Chain)
2606     .setCallee(TLI.getLibcallCallingConv(LC), RetTy, Func, std::move(Args))
2607     .setSExtResult();
2608
2609   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
2610
2611   SplitInteger(CallInfo.first, Lo, Hi);
2612   SDValue Temp2 =
2613       DAG.getLoad(PtrVT, dl, CallInfo.second, Temp, MachinePointerInfo());
2614   SDValue Ofl = DAG.getSetCC(dl, N->getValueType(1), Temp2,
2615                              DAG.getConstant(0, dl, PtrVT),
2616                              ISD::SETNE);
2617   // Use the overflow from the libcall everywhere.
2618   ReplaceValueWith(SDValue(N, 1), Ofl);
2619 }
2620
2621 void DAGTypeLegalizer::ExpandIntRes_UDIV(SDNode *N,
2622                                          SDValue &Lo, SDValue &Hi) {
2623   EVT VT = N->getValueType(0);
2624   SDLoc dl(N);
2625   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2626
2627   if (TLI.getOperationAction(ISD::UDIVREM, VT) == TargetLowering::Custom) {
2628     SDValue Res = DAG.getNode(ISD::UDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2629     SplitInteger(Res.getValue(0), Lo, Hi);
2630     return;
2631   }
2632
2633   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2634   if (VT == MVT::i16)
2635     LC = RTLIB::UDIV_I16;
2636   else if (VT == MVT::i32)
2637     LC = RTLIB::UDIV_I32;
2638   else if (VT == MVT::i64)
2639     LC = RTLIB::UDIV_I64;
2640   else if (VT == MVT::i128)
2641     LC = RTLIB::UDIV_I128;
2642   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UDIV!");
2643
2644   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, false, dl).first, Lo, Hi);
2645 }
2646
2647 void DAGTypeLegalizer::ExpandIntRes_UREM(SDNode *N,
2648                                          SDValue &Lo, SDValue &Hi) {
2649   EVT VT = N->getValueType(0);
2650   SDLoc dl(N);
2651   SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
2652
2653   if (TLI.getOperationAction(ISD::UDIVREM, VT) == TargetLowering::Custom) {
2654     SDValue Res = DAG.getNode(ISD::UDIVREM, dl, DAG.getVTList(VT, VT), Ops);
2655     SplitInteger(Res.getValue(1), Lo, Hi);
2656     return;
2657   }
2658
2659   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
2660   if (VT == MVT::i16)
2661     LC = RTLIB::UREM_I16;
2662   else if (VT == MVT::i32)
2663     LC = RTLIB::UREM_I32;
2664   else if (VT == MVT::i64)
2665     LC = RTLIB::UREM_I64;
2666   else if (VT == MVT::i128)
2667     LC = RTLIB::UREM_I128;
2668   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unsupported UREM!");
2669
2670   SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, false, dl).first, Lo, Hi);
2671 }
2672
2673 void DAGTypeLegalizer::ExpandIntRes_ZERO_EXTEND(SDNode *N,
2674                                                 SDValue &Lo, SDValue &Hi) {
2675   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));
2676   SDLoc dl(N);
2677   SDValue Op = N->getOperand(0);
2678   if (Op.getValueType().bitsLE(NVT)) {
2679     // The low part is zero extension of the input (degenerates to a copy).
2680     Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, N->getOperand(0));
2681     Hi = DAG.getConstant(0, dl, NVT);   // The high part is just a zero.
2682   } else {
2683     // For example, extension of an i48 to an i64.  The operand type necessarily
2684     // promotes to the result type, so will end up being expanded too.
2685     assert(getTypeAction(Op.getValueType()) ==
2686            TargetLowering::TypePromoteInteger &&
2687            "Only know how to promote this result!");
2688     SDValue Res = GetPromotedInteger(Op);
2689     assert(Res.getValueType() == N->getValueType(0) &&
2690            "Operand over promoted?");
2691     // Split the promoted operand.  This will simplify when it is expanded.
2692     SplitInteger(Res, Lo, Hi);
2693     unsigned ExcessBits =
2694       Op.getValueType().getSizeInBits() - NVT.getSizeInBits();
2695     Hi = DAG.getZeroExtendInReg(Hi, dl,
2696                                 EVT::getIntegerVT(*DAG.getContext(),
2697                                                   ExcessBits));
2698   }
2699 }
2700
2701 void DAGTypeLegalizer::ExpandIntRes_ATOMIC_LOAD(SDNode *N,
2702                                                 SDValue &Lo, SDValue &Hi) {
2703   SDLoc dl(N);
2704   EVT VT = cast<AtomicSDNode>(N)->getMemoryVT();
2705   SDVTList VTs = DAG.getVTList(VT, MVT::i1, MVT::Other);
2706   SDValue Zero = DAG.getConstant(0, dl, VT);
2707   SDValue Swap = DAG.getAtomicCmpSwap(
2708       ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS, dl,
2709       cast<AtomicSDNode>(N)->getMemoryVT(), VTs, N->getOperand(0),
2710       N->getOperand(1), Zero, Zero, cast<AtomicSDNode>(N)->getMemOperand(),
2711       cast<AtomicSDNode>(N)->getOrdering(),
2712       cast<AtomicSDNode>(N)->getOrdering(),
2713       cast<AtomicSDNode>(N)->getSynchScope());
2714
2715   ReplaceValueWith(SDValue(N, 0), Swap.getValue(0));
2716   ReplaceValueWith(SDValue(N, 1), Swap.getValue(2));
2717 }
2718
2719 //===----------------------------------------------------------------------===//
2720 //  Integer Operand Expansion
2721 //===----------------------------------------------------------------------===//
2722
2723 /// ExpandIntegerOperand - This method is called when the specified operand of
2724 /// the specified node is found to need expansion.  At this point, all of the
2725 /// result types of the node are known to be legal, but other operands of the
2726 /// node may need promotion or expansion as well as the specified one.
2727 bool DAGTypeLegalizer::ExpandIntegerOperand(SDNode *N, unsigned OpNo) {
2728   DEBUG(dbgs() << "Expand integer operand: "; N->dump(&DAG); dbgs() << "\n");
2729   SDValue Res = SDValue();
2730
2731   if (CustomLowerNode(N, N->getOperand(OpNo).getValueType(), false))
2732     return false;
2733
2734   switch (N->getOpcode()) {
2735   default:
2736   #ifndef NDEBUG
2737     dbgs() << "ExpandIntegerOperand Op #" << OpNo << ": ";
2738     N->dump(&DAG); dbgs() << "\n";
2739   #endif
2740     llvm_unreachable("Do not know how to expand this operator's operand!");
2741
2742   case ISD::BITCAST:           Res = ExpandOp_BITCAST(N); break;
2743   case ISD::BR_CC:             Res = ExpandIntOp_BR_CC(N); break;
2744   case ISD::BUILD_VECTOR:      Res = ExpandOp_BUILD_VECTOR(N); break;
2745   case ISD::EXTRACT_ELEMENT:   Res = ExpandOp_EXTRACT_ELEMENT(N); break;
2746   case ISD::INSERT_VECTOR_ELT: Res = ExpandOp_INSERT_VECTOR_ELT(N); break;
2747   case ISD::SCALAR_TO_VECTOR:  Res = ExpandOp_SCALAR_TO_VECTOR(N); break;
2748   case ISD::SELECT_CC:         Res = ExpandIntOp_SELECT_CC(N); break;
2749   case ISD::SETCC:             Res = ExpandIntOp_SETCC(N); break;
2750   case ISD::SETCCE:            Res = ExpandIntOp_SETCCE(N); break;
2751   case ISD::SINT_TO_FP:        Res = ExpandIntOp_SINT_TO_FP(N); break;
2752   case ISD::STORE:   Res = ExpandIntOp_STORE(cast<StoreSDNode>(N), OpNo); break;
2753   case ISD::TRUNCATE:          Res = ExpandIntOp_TRUNCATE(N); break;
2754   case ISD::UINT_TO_FP:        Res = ExpandIntOp_UINT_TO_FP(N); break;
2755
2756   case ISD::SHL:
2757   case ISD::SRA:
2758   case ISD::SRL:
2759   case ISD::ROTL:
2760   case ISD::ROTR:              Res = ExpandIntOp_Shift(N); break;
2761   case ISD::RETURNADDR:
2762   case ISD::FRAMEADDR:         Res = ExpandIntOp_RETURNADDR(N); break;
2763
2764   case ISD::ATOMIC_STORE:      Res = ExpandIntOp_ATOMIC_STORE(N); break;
2765   }
2766
2767   // If the result is null, the sub-method took care of registering results etc.
2768   if (!Res.getNode()) return false;
2769
2770   // If the result is N, the sub-method updated N in place.  Tell the legalizer
2771   // core about this.
2772   if (Res.getNode() == N)
2773     return true;
2774
2775   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
2776          "Invalid operand expansion");
2777
2778   ReplaceValueWith(SDValue(N, 0), Res);
2779   return false;
2780 }
2781
2782 /// IntegerExpandSetCCOperands - Expand the operands of a comparison.  This code
2783 /// is shared among BR_CC, SELECT_CC, and SETCC handlers.
2784 void DAGTypeLegalizer::IntegerExpandSetCCOperands(SDValue &NewLHS,
2785                                                   SDValue &NewRHS,
2786                                                   ISD::CondCode &CCCode,
2787                                                   const SDLoc &dl) {
2788   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
2789   GetExpandedInteger(NewLHS, LHSLo, LHSHi);
2790   GetExpandedInteger(NewRHS, RHSLo, RHSHi);
2791
2792   if (CCCode == ISD::SETEQ || CCCode == ISD::SETNE) {
2793     if (RHSLo == RHSHi) {
2794       if (ConstantSDNode *RHSCST = dyn_cast<ConstantSDNode>(RHSLo)) {
2795         if (RHSCST->isAllOnesValue()) {
2796           // Equality comparison to -1.
2797           NewLHS = DAG.getNode(ISD::AND, dl,
2798                                LHSLo.getValueType(), LHSLo, LHSHi);
2799           NewRHS = RHSLo;
2800           return;
2801         }
2802       }
2803     }
2804
2805     NewLHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSLo, RHSLo);
2806     NewRHS = DAG.getNode(ISD::XOR, dl, LHSLo.getValueType(), LHSHi, RHSHi);
2807     NewLHS = DAG.getNode(ISD::OR, dl, NewLHS.getValueType(), NewLHS, NewRHS);
2808     NewRHS = DAG.getConstant(0, dl, NewLHS.getValueType());
2809     return;
2810   }
2811
2812   // If this is a comparison of the sign bit, just look at the top part.
2813   // X > -1,  x < 0
2814   if (ConstantSDNode *CST = dyn_cast<ConstantSDNode>(NewRHS))
2815     if ((CCCode == ISD::SETLT && CST->isNullValue()) ||     // X < 0
2816         (CCCode == ISD::SETGT && CST->isAllOnesValue())) {  // X > -1
2817       NewLHS = LHSHi;
2818       NewRHS = RHSHi;
2819       return;
2820     }
2821
2822   // FIXME: This generated code sucks.
2823   ISD::CondCode LowCC;
2824   switch (CCCode) {
2825   default: llvm_unreachable("Unknown integer setcc!");
2826   case ISD::SETLT:
2827   case ISD::SETULT: LowCC = ISD::SETULT; break;
2828   case ISD::SETGT:
2829   case ISD::SETUGT: LowCC = ISD::SETUGT; break;
2830   case ISD::SETLE:
2831   case ISD::SETULE: LowCC = ISD::SETULE; break;
2832   case ISD::SETGE:
2833   case ISD::SETUGE: LowCC = ISD::SETUGE; break;
2834   }
2835
2836   // Tmp1 = lo(op1) < lo(op2)   // Always unsigned comparison
2837   // Tmp2 = hi(op1) < hi(op2)   // Signedness depends on operands
2838   // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2;
2839
2840   // NOTE: on targets without efficient SELECT of bools, we can always use
2841   // this identity: (B1 ? B2 : B3) --> (B1 & B2)|(!B1&B3)
2842   TargetLowering::DAGCombinerInfo DagCombineInfo(DAG, AfterLegalizeTypes, true,
2843                                                  nullptr);
2844   SDValue Tmp1, Tmp2;
2845   if (TLI.isTypeLegal(LHSLo.getValueType()) &&
2846       TLI.isTypeLegal(RHSLo.getValueType()))
2847     Tmp1 = TLI.SimplifySetCC(getSetCCResultType(LHSLo.getValueType()),
2848                              LHSLo, RHSLo, LowCC, false, DagCombineInfo, dl);
2849   if (!Tmp1.getNode())
2850     Tmp1 = DAG.getSetCC(dl, getSetCCResultType(LHSLo.getValueType()),
2851                         LHSLo, RHSLo, LowCC);
2852   if (TLI.isTypeLegal(LHSHi.getValueType()) &&
2853       TLI.isTypeLegal(RHSHi.getValueType()))
2854     Tmp2 = TLI.SimplifySetCC(getSetCCResultType(LHSHi.getValueType()),
2855                              LHSHi, RHSHi, CCCode, false, DagCombineInfo, dl);
2856   if (!Tmp2.getNode())
2857     Tmp2 = DAG.getNode(ISD::SETCC, dl,
2858                        getSetCCResultType(LHSHi.getValueType()),
2859                        LHSHi, RHSHi, DAG.getCondCode(CCCode));
2860
2861   ConstantSDNode *Tmp1C = dyn_cast<ConstantSDNode>(Tmp1.getNode());
2862   ConstantSDNode *Tmp2C = dyn_cast<ConstantSDNode>(Tmp2.getNode());
2863   if ((Tmp1C && Tmp1C->isNullValue()) ||
2864       (Tmp2C && Tmp2C->isNullValue() &&
2865        (CCCode == ISD::SETLE || CCCode == ISD::SETGE ||
2866         CCCode == ISD::SETUGE || CCCode == ISD::SETULE)) ||
2867       (Tmp2C && Tmp2C->getAPIntValue() == 1 &&
2868        (CCCode == ISD::SETLT || CCCode == ISD::SETGT ||
2869         CCCode == ISD::SETUGT || CCCode == ISD::SETULT))) {
2870     // low part is known false, returns high part.
2871     // For LE / GE, if high part is known false, ignore the low part.
2872     // For LT / GT, if high part is known true, ignore the low part.
2873     NewLHS = Tmp2;
2874     NewRHS = SDValue();
2875     return;
2876   }
2877
2878   if (LHSHi == RHSHi) {
2879     // Comparing the low bits is enough.
2880     NewLHS = Tmp1;
2881     NewRHS = SDValue();
2882     return;
2883   }
2884
2885   // Lower with SETCCE if the target supports it.
2886   // FIXME: Make all targets support this, then remove the other lowering.
2887   if (TLI.getOperationAction(
2888           ISD::SETCCE,
2889           TLI.getTypeToExpandTo(*DAG.getContext(), LHSLo.getValueType())) ==
2890       TargetLowering::Custom) {
2891     // SETCCE can detect < and >= directly. For > and <=, flip operands and
2892     // condition code.
2893     bool FlipOperands = false;
2894     switch (CCCode) {
2895     case ISD::SETGT:  CCCode = ISD::SETLT;  FlipOperands = true; break;
2896     case ISD::SETUGT: CCCode = ISD::SETULT; FlipOperands = true; break;
2897     case ISD::SETLE:  CCCode = ISD::SETGE;  FlipOperands = true; break;
2898     case ISD::SETULE: CCCode = ISD::SETUGE; FlipOperands = true; break;
2899     default: break;
2900     }
2901     if (FlipOperands) {
2902       std::swap(LHSLo, RHSLo);
2903       std::swap(LHSHi, RHSHi);
2904     }
2905     // Perform a wide subtraction, feeding the carry from the low part into
2906     // SETCCE. The SETCCE operation is essentially looking at the high part of
2907     // the result of LHS - RHS. It is negative iff LHS < RHS. It is zero or
2908     // positive iff LHS >= RHS.
2909     SDVTList VTList = DAG.getVTList(LHSLo.getValueType(), MVT::Glue);
2910     SDValue LowCmp = DAG.getNode(ISD::SUBC, dl, VTList, LHSLo, RHSLo);
2911     SDValue Res =
2912         DAG.getNode(ISD::SETCCE, dl, getSetCCResultType(LHSLo.getValueType()),
2913                     LHSHi, RHSHi, LowCmp.getValue(1), DAG.getCondCode(CCCode));
2914     NewLHS = Res;
2915     NewRHS = SDValue();
2916     return;
2917   }
2918
2919   NewLHS = TLI.SimplifySetCC(getSetCCResultType(LHSHi.getValueType()),
2920                              LHSHi, RHSHi, ISD::SETEQ, false,
2921                              DagCombineInfo, dl);
2922   if (!NewLHS.getNode())
2923     NewLHS = DAG.getSetCC(dl, getSetCCResultType(LHSHi.getValueType()),
2924                           LHSHi, RHSHi, ISD::SETEQ);
2925   NewLHS = DAG.getSelect(dl, Tmp1.getValueType(),
2926                          NewLHS, Tmp1, Tmp2);
2927   NewRHS = SDValue();
2928 }
2929
2930 SDValue DAGTypeLegalizer::ExpandIntOp_BR_CC(SDNode *N) {
2931   SDValue NewLHS = N->getOperand(2), NewRHS = N->getOperand(3);
2932   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(1))->get();
2933   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
2934
2935   // If ExpandSetCCOperands returned a scalar, we need to compare the result
2936   // against zero to select between true and false values.
2937   if (!NewRHS.getNode()) {
2938     NewRHS = DAG.getConstant(0, SDLoc(N), NewLHS.getValueType());
2939     CCCode = ISD::SETNE;
2940   }
2941
2942   // Update N to have the operands specified.
2943   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0),
2944                                 DAG.getCondCode(CCCode), NewLHS, NewRHS,
2945                                 N->getOperand(4)), 0);
2946 }
2947
2948 SDValue DAGTypeLegalizer::ExpandIntOp_SELECT_CC(SDNode *N) {
2949   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
2950   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(4))->get();
2951   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
2952
2953   // If ExpandSetCCOperands returned a scalar, we need to compare the result
2954   // against zero to select between true and false values.
2955   if (!NewRHS.getNode()) {
2956     NewRHS = DAG.getConstant(0, SDLoc(N), NewLHS.getValueType());
2957     CCCode = ISD::SETNE;
2958   }
2959
2960   // Update N to have the operands specified.
2961   return SDValue(DAG.UpdateNodeOperands(N, NewLHS, NewRHS,
2962                                 N->getOperand(2), N->getOperand(3),
2963                                 DAG.getCondCode(CCCode)), 0);
2964 }
2965
2966 SDValue DAGTypeLegalizer::ExpandIntOp_SETCC(SDNode *N) {
2967   SDValue NewLHS = N->getOperand(0), NewRHS = N->getOperand(1);
2968   ISD::CondCode CCCode = cast<CondCodeSDNode>(N->getOperand(2))->get();
2969   IntegerExpandSetCCOperands(NewLHS, NewRHS, CCCode, SDLoc(N));
2970
2971   // If ExpandSetCCOperands returned a scalar, use it.
2972   if (!NewRHS.getNode()) {
2973     assert(NewLHS.getValueType() == N->getValueType(0) &&
2974            "Unexpected setcc expansion!");
2975     return NewLHS;
2976   }
2977
2978   // Otherwise, update N to have the operands specified.
2979   return SDValue(DAG.UpdateNodeOperands(N, NewLHS, NewRHS,
2980                                 DAG.getCondCode(CCCode)), 0);
2981 }
2982
2983 SDValue DAGTypeLegalizer::ExpandIntOp_SETCCE(SDNode *N) {
2984   SDValue LHS = N->getOperand(0);
2985   SDValue RHS = N->getOperand(1);
2986   SDValue Carry = N->getOperand(2);
2987   SDValue Cond = N->getOperand(3);
2988   SDLoc dl = SDLoc(N);
2989
2990   SDValue LHSLo, LHSHi, RHSLo, RHSHi;
2991   GetExpandedInteger(LHS, LHSLo, LHSHi);
2992   GetExpandedInteger(RHS, RHSLo, RHSHi);
2993
2994   // Expand to a SUBE for the low part and a smaller SETCCE for the high.
2995   SDVTList VTList = DAG.getVTList(LHSLo.getValueType(), MVT::Glue);
2996   SDValue LowCmp = DAG.getNode(ISD::SUBE, dl, VTList, LHSLo, RHSLo, Carry);
2997   return DAG.getNode(ISD::SETCCE, dl, N->getValueType(0), LHSHi, RHSHi,
2998                      LowCmp.getValue(1), Cond);
2999 }
3000
3001 SDValue DAGTypeLegalizer::ExpandIntOp_Shift(SDNode *N) {
3002   // The value being shifted is legal, but the shift amount is too big.
3003   // It follows that either the result of the shift is undefined, or the
3004   // upper half of the shift amount is zero.  Just use the lower half.
3005   SDValue Lo, Hi;
3006   GetExpandedInteger(N->getOperand(1), Lo, Hi);
3007   return SDValue(DAG.UpdateNodeOperands(N, N->getOperand(0), Lo), 0);
3008 }
3009
3010 SDValue DAGTypeLegalizer::ExpandIntOp_RETURNADDR(SDNode *N) {
3011   // The argument of RETURNADDR / FRAMEADDR builtin is 32 bit contant.  This
3012   // surely makes pretty nice problems on 8/16 bit targets. Just truncate this
3013   // constant to valid type.
3014   SDValue Lo, Hi;
3015   GetExpandedInteger(N->getOperand(0), Lo, Hi);
3016   return SDValue(DAG.UpdateNodeOperands(N, Lo), 0);
3017 }
3018
3019 SDValue DAGTypeLegalizer::ExpandIntOp_SINT_TO_FP(SDNode *N) {
3020   SDValue Op = N->getOperand(0);
3021   EVT DstVT = N->getValueType(0);
3022   RTLIB::Libcall LC = RTLIB::getSINTTOFP(Op.getValueType(), DstVT);
3023   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
3024          "Don't know how to expand this SINT_TO_FP!");
3025   return TLI.makeLibCall(DAG, LC, DstVT, Op, true, SDLoc(N)).first;
3026 }
3027
3028 SDValue DAGTypeLegalizer::ExpandIntOp_STORE(StoreSDNode *N, unsigned OpNo) {
3029   if (ISD::isNormalStore(N))
3030     return ExpandOp_NormalStore(N, OpNo);
3031
3032   assert(ISD::isUNINDEXEDStore(N) && "Indexed store during type legalization!");
3033   assert(OpNo == 1 && "Can only expand the stored value so far");
3034
3035   EVT VT = N->getOperand(1).getValueType();
3036   EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3037   SDValue Ch  = N->getChain();
3038   SDValue Ptr = N->getBasePtr();
3039   unsigned Alignment = N->getAlignment();
3040   MachineMemOperand::Flags MMOFlags = N->getMemOperand()->getFlags();
3041   AAMDNodes AAInfo = N->getAAInfo();
3042   SDLoc dl(N);
3043   SDValue Lo, Hi;
3044
3045   assert(NVT.isByteSized() && "Expanded type not byte sized!");
3046
3047   if (N->getMemoryVT().bitsLE(NVT)) {
3048     GetExpandedInteger(N->getValue(), Lo, Hi);
3049     return DAG.getTruncStore(Ch, dl, Lo, Ptr, N->getPointerInfo(),
3050                              N->getMemoryVT(), Alignment, MMOFlags, AAInfo);
3051   }
3052
3053   if (DAG.getDataLayout().isLittleEndian()) {
3054     // Little-endian - low bits are at low addresses.
3055     GetExpandedInteger(N->getValue(), Lo, Hi);
3056
3057     Lo = DAG.getStore(Ch, dl, Lo, Ptr, N->getPointerInfo(), Alignment, MMOFlags,
3058                       AAInfo);
3059
3060     unsigned ExcessBits =
3061       N->getMemoryVT().getSizeInBits() - NVT.getSizeInBits();
3062     EVT NEVT = EVT::getIntegerVT(*DAG.getContext(), ExcessBits);
3063
3064     // Increment the pointer to the other half.
3065     unsigned IncrementSize = NVT.getSizeInBits()/8;
3066     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3067                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3068     Hi = DAG.getTruncStore(
3069         Ch, dl, Hi, Ptr, N->getPointerInfo().getWithOffset(IncrementSize), NEVT,
3070         MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
3071     return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
3072   }
3073
3074   // Big-endian - high bits are at low addresses.  Favor aligned stores at
3075   // the cost of some bit-fiddling.
3076   GetExpandedInteger(N->getValue(), Lo, Hi);
3077
3078   EVT ExtVT = N->getMemoryVT();
3079   unsigned EBytes = ExtVT.getStoreSize();
3080   unsigned IncrementSize = NVT.getSizeInBits()/8;
3081   unsigned ExcessBits = (EBytes - IncrementSize)*8;
3082   EVT HiVT = EVT::getIntegerVT(*DAG.getContext(),
3083                                ExtVT.getSizeInBits() - ExcessBits);
3084
3085   if (ExcessBits < NVT.getSizeInBits()) {
3086     // Transfer high bits from the top of Lo to the bottom of Hi.
3087     Hi = DAG.getNode(ISD::SHL, dl, NVT, Hi,
3088                      DAG.getConstant(NVT.getSizeInBits() - ExcessBits, dl,
3089                                      TLI.getPointerTy(DAG.getDataLayout())));
3090     Hi = DAG.getNode(
3091         ISD::OR, dl, NVT, Hi,
3092         DAG.getNode(ISD::SRL, dl, NVT, Lo,
3093                     DAG.getConstant(ExcessBits, dl,
3094                                     TLI.getPointerTy(DAG.getDataLayout()))));
3095   }
3096
3097   // Store both the high bits and maybe some of the low bits.
3098   Hi = DAG.getTruncStore(Ch, dl, Hi, Ptr, N->getPointerInfo(), HiVT, Alignment,
3099                          MMOFlags, AAInfo);
3100
3101   // Increment the pointer to the other half.
3102   Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
3103                     DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
3104   // Store the lowest ExcessBits bits in the second half.
3105   Lo = DAG.getTruncStore(Ch, dl, Lo, Ptr,
3106                          N->getPointerInfo().getWithOffset(IncrementSize),
3107                          EVT::getIntegerVT(*DAG.getContext(), ExcessBits),
3108                          MinAlign(Alignment, IncrementSize), MMOFlags, AAInfo);
3109   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
3110 }
3111
3112 SDValue DAGTypeLegalizer::ExpandIntOp_TRUNCATE(SDNode *N) {
3113   SDValue InL, InH;
3114   GetExpandedInteger(N->getOperand(0), InL, InH);
3115   // Just truncate the low part of the source.
3116   return DAG.getNode(ISD::TRUNCATE, SDLoc(N), N->getValueType(0), InL);
3117 }
3118
3119 SDValue DAGTypeLegalizer::ExpandIntOp_UINT_TO_FP(SDNode *N) {
3120   SDValue Op = N->getOperand(0);
3121   EVT SrcVT = Op.getValueType();
3122   EVT DstVT = N->getValueType(0);
3123   SDLoc dl(N);
3124
3125   // The following optimization is valid only if every value in SrcVT (when
3126   // treated as signed) is representable in DstVT.  Check that the mantissa
3127   // size of DstVT is >= than the number of bits in SrcVT -1.
3128   const fltSemantics &sem = DAG.EVTToAPFloatSemantics(DstVT);
3129   if (APFloat::semanticsPrecision(sem) >= SrcVT.getSizeInBits()-1 &&
3130       TLI.getOperationAction(ISD::SINT_TO_FP, SrcVT) == TargetLowering::Custom){
3131     // Do a signed conversion then adjust the result.
3132     SDValue SignedConv = DAG.getNode(ISD::SINT_TO_FP, dl, DstVT, Op);
3133     SignedConv = TLI.LowerOperation(SignedConv, DAG);
3134
3135     // The result of the signed conversion needs adjusting if the 'sign bit' of
3136     // the incoming integer was set.  To handle this, we dynamically test to see
3137     // if it is set, and, if so, add a fudge factor.
3138
3139     const uint64_t F32TwoE32  = 0x4F800000ULL;
3140     const uint64_t F32TwoE64  = 0x5F800000ULL;
3141     const uint64_t F32TwoE128 = 0x7F800000ULL;
3142
3143     APInt FF(32, 0);
3144     if (SrcVT == MVT::i32)
3145       FF = APInt(32, F32TwoE32);
3146     else if (SrcVT == MVT::i64)
3147       FF = APInt(32, F32TwoE64);
3148     else if (SrcVT == MVT::i128)
3149       FF = APInt(32, F32TwoE128);
3150     else
3151       llvm_unreachable("Unsupported UINT_TO_FP!");
3152
3153     // Check whether the sign bit is set.
3154     SDValue Lo, Hi;
3155     GetExpandedInteger(Op, Lo, Hi);
3156     SDValue SignSet = DAG.getSetCC(dl,
3157                                    getSetCCResultType(Hi.getValueType()),
3158                                    Hi,
3159                                    DAG.getConstant(0, dl, Hi.getValueType()),
3160                                    ISD::SETLT);
3161
3162     // Build a 64 bit pair (0, FF) in the constant pool, with FF in the lo bits.
3163     SDValue FudgePtr =
3164         DAG.getConstantPool(ConstantInt::get(*DAG.getContext(), FF.zext(64)),
3165                             TLI.getPointerTy(DAG.getDataLayout()));
3166
3167     // Get a pointer to FF if the sign bit was set, or to 0 otherwise.
3168     SDValue Zero = DAG.getIntPtrConstant(0, dl);
3169     SDValue Four = DAG.getIntPtrConstant(4, dl);
3170     if (DAG.getDataLayout().isBigEndian())
3171       std::swap(Zero, Four);
3172     SDValue Offset = DAG.getSelect(dl, Zero.getValueType(), SignSet,
3173                                    Zero, Four);
3174     unsigned Alignment = cast<ConstantPoolSDNode>(FudgePtr)->getAlignment();
3175     FudgePtr = DAG.getNode(ISD::ADD, dl, FudgePtr.getValueType(),
3176                            FudgePtr, Offset);
3177     Alignment = std::min(Alignment, 4u);
3178
3179     // Load the value out, extending it from f32 to the destination float type.
3180     // FIXME: Avoid the extend by constructing the right constant pool?
3181     SDValue Fudge = DAG.getExtLoad(
3182         ISD::EXTLOAD, dl, DstVT, DAG.getEntryNode(), FudgePtr,
3183         MachinePointerInfo::getConstantPool(DAG.getMachineFunction()), MVT::f32,
3184         Alignment);
3185     return DAG.getNode(ISD::FADD, dl, DstVT, SignedConv, Fudge);
3186   }
3187
3188   // Otherwise, use a libcall.
3189   RTLIB::Libcall LC = RTLIB::getUINTTOFP(SrcVT, DstVT);
3190   assert(LC != RTLIB::UNKNOWN_LIBCALL &&
3191          "Don't know how to expand this UINT_TO_FP!");
3192   return TLI.makeLibCall(DAG, LC, DstVT, Op, true, dl).first;
3193 }
3194
3195 SDValue DAGTypeLegalizer::ExpandIntOp_ATOMIC_STORE(SDNode *N) {
3196   SDLoc dl(N);
3197   SDValue Swap = DAG.getAtomic(ISD::ATOMIC_SWAP, dl,
3198                                cast<AtomicSDNode>(N)->getMemoryVT(),
3199                                N->getOperand(0),
3200                                N->getOperand(1), N->getOperand(2),
3201                                cast<AtomicSDNode>(N)->getMemOperand(),
3202                                cast<AtomicSDNode>(N)->getOrdering(),
3203                                cast<AtomicSDNode>(N)->getSynchScope());
3204   return Swap.getValue(1);
3205 }
3206
3207
3208 SDValue DAGTypeLegalizer::PromoteIntRes_EXTRACT_SUBVECTOR(SDNode *N) {
3209   SDValue InOp0 = N->getOperand(0);
3210   EVT InVT = InOp0.getValueType();
3211
3212   EVT OutVT = N->getValueType(0);
3213   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3214   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3215   unsigned OutNumElems = OutVT.getVectorNumElements();
3216   EVT NOutVTElem = NOutVT.getVectorElementType();
3217
3218   SDLoc dl(N);
3219   SDValue BaseIdx = N->getOperand(1);
3220
3221   SmallVector<SDValue, 8> Ops;
3222   Ops.reserve(OutNumElems);
3223   for (unsigned i = 0; i != OutNumElems; ++i) {
3224
3225     // Extract the element from the original vector.
3226     SDValue Index = DAG.getNode(ISD::ADD, dl, BaseIdx.getValueType(),
3227       BaseIdx, DAG.getConstant(i, dl, BaseIdx.getValueType()));
3228     SDValue Ext = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
3229       InVT.getVectorElementType(), N->getOperand(0), Index);
3230
3231     SDValue Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, Ext);
3232     // Insert the converted element to the new vector.
3233     Ops.push_back(Op);
3234   }
3235
3236   return DAG.getNode(ISD::BUILD_VECTOR, dl, NOutVT, Ops);
3237 }
3238
3239
3240 SDValue DAGTypeLegalizer::PromoteIntRes_VECTOR_SHUFFLE(SDNode *N) {
3241   ShuffleVectorSDNode *SV = cast<ShuffleVectorSDNode>(N);
3242   EVT VT = N->getValueType(0);
3243   SDLoc dl(N);
3244
3245   ArrayRef<int> NewMask = SV->getMask().slice(0, VT.getVectorNumElements());
3246
3247   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3248   SDValue V1 = GetPromotedInteger(N->getOperand(1));
3249   EVT OutVT = V0.getValueType();
3250
3251   return DAG.getVectorShuffle(OutVT, dl, V0, V1, NewMask);
3252 }
3253
3254
3255 SDValue DAGTypeLegalizer::PromoteIntRes_BUILD_VECTOR(SDNode *N) {
3256   EVT OutVT = N->getValueType(0);
3257   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3258   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3259   unsigned NumElems = N->getNumOperands();
3260   EVT NOutVTElem = NOutVT.getVectorElementType();
3261
3262   SDLoc dl(N);
3263
3264   SmallVector<SDValue, 8> Ops;
3265   Ops.reserve(NumElems);
3266   for (unsigned i = 0; i != NumElems; ++i) {
3267     SDValue Op;
3268     // BUILD_VECTOR integer operand types are allowed to be larger than the
3269     // result's element type. This may still be true after the promotion. For
3270     // example, we might be promoting (<v?i1> = BV <i32>, <i32>, ...) to
3271     // (v?i16 = BV <i32>, <i32>, ...), and we can't any_extend <i32> to <i16>.
3272     if (N->getOperand(i).getValueType().bitsLT(NOutVTElem))
3273       Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, N->getOperand(i));
3274     else
3275       Op = N->getOperand(i);
3276     Ops.push_back(Op);
3277   }
3278
3279   return DAG.getNode(ISD::BUILD_VECTOR, dl, NOutVT, Ops);
3280 }
3281
3282 SDValue DAGTypeLegalizer::PromoteIntRes_SCALAR_TO_VECTOR(SDNode *N) {
3283
3284   SDLoc dl(N);
3285
3286   assert(!N->getOperand(0).getValueType().isVector() &&
3287          "Input must be a scalar");
3288
3289   EVT OutVT = N->getValueType(0);
3290   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3291   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3292   EVT NOutVTElem = NOutVT.getVectorElementType();
3293
3294   SDValue Op = DAG.getNode(ISD::ANY_EXTEND, dl, NOutVTElem, N->getOperand(0));
3295
3296   return DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, NOutVT, Op);
3297 }
3298
3299 SDValue DAGTypeLegalizer::PromoteIntRes_CONCAT_VECTORS(SDNode *N) {
3300   SDLoc dl(N);
3301
3302   EVT OutVT = N->getValueType(0);
3303   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3304   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3305
3306   EVT InElemTy = OutVT.getVectorElementType();
3307   EVT OutElemTy = NOutVT.getVectorElementType();
3308
3309   unsigned NumElem = N->getOperand(0).getValueType().getVectorNumElements();
3310   unsigned NumOutElem = NOutVT.getVectorNumElements();
3311   unsigned NumOperands = N->getNumOperands();
3312   assert(NumElem * NumOperands == NumOutElem &&
3313          "Unexpected number of elements");
3314
3315   // Take the elements from the first vector.
3316   SmallVector<SDValue, 8> Ops(NumOutElem);
3317   for (unsigned i = 0; i < NumOperands; ++i) {
3318     SDValue Op = N->getOperand(i);
3319     for (unsigned j = 0; j < NumElem; ++j) {
3320       SDValue Ext = DAG.getNode(
3321           ISD::EXTRACT_VECTOR_ELT, dl, InElemTy, Op,
3322           DAG.getConstant(j, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3323       Ops[i * NumElem + j] = DAG.getNode(ISD::ANY_EXTEND, dl, OutElemTy, Ext);
3324     }
3325   }
3326
3327   return DAG.getNode(ISD::BUILD_VECTOR, dl, NOutVT, Ops);
3328 }
3329
3330 SDValue DAGTypeLegalizer::PromoteIntRes_INSERT_VECTOR_ELT(SDNode *N) {
3331   EVT OutVT = N->getValueType(0);
3332   EVT NOutVT = TLI.getTypeToTransformTo(*DAG.getContext(), OutVT);
3333   assert(NOutVT.isVector() && "This type must be promoted to a vector type");
3334
3335   EVT NOutVTElem = NOutVT.getVectorElementType();
3336
3337   SDLoc dl(N);
3338   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3339
3340   SDValue ConvElem = DAG.getNode(ISD::ANY_EXTEND, dl,
3341     NOutVTElem, N->getOperand(1));
3342   return DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, NOutVT,
3343     V0, ConvElem, N->getOperand(2));
3344 }
3345
3346 SDValue DAGTypeLegalizer::PromoteIntOp_EXTRACT_VECTOR_ELT(SDNode *N) {
3347   SDLoc dl(N);
3348   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3349   SDValue V1 = DAG.getZExtOrTrunc(N->getOperand(1), dl,
3350                                   TLI.getVectorIdxTy(DAG.getDataLayout()));
3351   SDValue Ext = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
3352     V0->getValueType(0).getScalarType(), V0, V1);
3353
3354   // EXTRACT_VECTOR_ELT can return types which are wider than the incoming
3355   // element types. If this is the case then we need to expand the outgoing
3356   // value and not truncate it.
3357   return DAG.getAnyExtOrTrunc(Ext, dl, N->getValueType(0));
3358 }
3359
3360 SDValue DAGTypeLegalizer::PromoteIntOp_EXTRACT_SUBVECTOR(SDNode *N) {
3361   SDLoc dl(N);
3362   SDValue V0 = GetPromotedInteger(N->getOperand(0));
3363   MVT InVT = V0.getValueType().getSimpleVT();
3364   MVT OutVT = MVT::getVectorVT(InVT.getVectorElementType(),
3365                                N->getValueType(0).getVectorNumElements());
3366   SDValue Ext = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, OutVT, V0, N->getOperand(1));
3367   return DAG.getNode(ISD::TRUNCATE, dl, N->getValueType(0), Ext);
3368 }
3369
3370 SDValue DAGTypeLegalizer::PromoteIntOp_CONCAT_VECTORS(SDNode *N) {
3371   SDLoc dl(N);
3372   unsigned NumElems = N->getNumOperands();
3373
3374   EVT RetSclrTy = N->getValueType(0).getVectorElementType();
3375
3376   SmallVector<SDValue, 8> NewOps;
3377   NewOps.reserve(NumElems);
3378
3379   // For each incoming vector
3380   for (unsigned VecIdx = 0; VecIdx != NumElems; ++VecIdx) {
3381     SDValue Incoming = GetPromotedInteger(N->getOperand(VecIdx));
3382     EVT SclrTy = Incoming->getValueType(0).getVectorElementType();
3383     unsigned NumElem = Incoming->getValueType(0).getVectorNumElements();
3384
3385     for (unsigned i=0; i<NumElem; ++i) {
3386       // Extract element from incoming vector
3387       SDValue Ex = DAG.getNode(
3388           ISD::EXTRACT_VECTOR_ELT, dl, SclrTy, Incoming,
3389           DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
3390       SDValue Tr = DAG.getNode(ISD::TRUNCATE, dl, RetSclrTy, Ex);
3391       NewOps.push_back(Tr);
3392     }
3393   }
3394
3395   return DAG.getNode(ISD::BUILD_VECTOR, dl,  N->getValueType(0), NewOps);
3396 }